c - 虚拟内存系统、页表和TLB

Question

我正在努力解决这个问题，甚至无法进行一步，问题是这样的：

考虑以下 C 程序：

int X[N];
int i;
int step = M; // M is some predefined constant
for (i = 0; i < N; i += step) X[i] = X[i] + 1;

如果该程序运行在具有 4 KB 页大小和 64 项 TLB 的机器上，那么 M 和 N 的什么值会导致每次执行内循环时 TLB 未命中？

谁能给我一些提示，我该如何解决？

Answer 1

很简单。首先，您必须了解 TLB 究竟是做什么的？提示是它是一个缓存，有助于转换virtual address为physical address. 所以你知道页面大小是 4 KB。因此，如果有一个数组，可以说无限长。您在 for 循环中从 0 到无穷大访问它。数组 X[0] 的第一次访问将导致 TLB 未命中并加载第一个 TLB。那么对于接下来的 4095 次访问，它不会丢失，因为它存在于 TLB 中（请记住，这是因为页面大小为 4096 = 4KB）。那么下一个地址是 X[4096]，这将导致 TLB 未命中。因此，您会看到，对于每 4096 个地址增量，您将有一个 TLB 未命中。所以我们确信M = 4096/sizeof(int)。

现在您还知道您有 64 项 TLB 缓存。因此，在加载了 64 个 TLB 条目后，您将拥有一个完整的 TLB。要加载第 65 个条目，您必须删除第一个条目。（请注意，可以有不同的替换机制。我们在这里假设它是一些简单的机制）。因此，在加载第 65 个条目后，访问 X[0] 时的第一个条目已被删除。因此，如果您现在尝试访问 X[0]，将会有一个 TLB 未命中替换 X[4096] 所需的条目，依此类推。所以你需要 , 的大小64 * 4096 = 256 KBytes来充分利用 TLB 缓存。但是，您希望每一步都有一个 TLB 缓存未命中。因此，对于 64 条目 TLB 缓存，您需要相当于 65 个条目的数组大小。因此N = 65 * 4096 / sizeof(int)。

希望这能给一些提示！

Answer 2

当页面的虚拟地址不在 TLB 中时，就会发生 TLB 未命中。

给定一个有 64 个条目的 TLB，如果你用虚拟地址 0*4096、1*4096、2*4096、...、63*4096 完全预填充它（你通过访问相关页面中的内存来填充它）然后请求访问从 64*4096 到 64*4096+4095 的虚拟地址，该访问将导致 TLB 未命中（因为 64*4096 尚未在 TLB 中）。

然后，如果现在存储地址 64*4096 的条目（在 TLB 未命中之后，驱逐 64 个条目之一并将其替换为虚拟地址 64*4096 和与其对应的物理地址）之前有虚拟地址 0*4096，然后访问虚拟地址从 0 到 4095 的内存将导致另一个 TLB 未命中（因为虚拟地址 0*4096 的条目已从 TLB 中逐出并替换为 VA 64*4096 的条目）。

基于 TLB 的这种行为，您应该想出M并且N满足要求。