虚拟内存系统，页面表和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;

如果在一个4KB页面大小和64个条目的TLB的机器上运行此程序，什么样的M和N值会导致内部循环的每次执行都发生TLB缺失？

请问有人能给我一些提示如何解决这个问题吗？

- Mr.Anubis

Answer 1

很简单。首先，你必须了解TLB的确切作用是什么？提示是它是一个缓存，可以帮助将虚拟地址转换为物理地址。所以你知道页面大小是4 Kbytes。假设有一个无限长度的数组。你正在通过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）。

希望这些提示有所帮助！

- Raj

---

TLB大小为64个页面条目，我猜。 - Mr.Anubis

是的，你说得对。但我指的是通过使用65个条目使TLB缓存未命中。我已更新说明。 - Raj

看到你这行代码 它不会被错过，因为它存在于TLB中（记住这是因为TLB大小为4096 = 4KB）。 - Mr.Anubis

抱歉，应该是页面大小。这是一个笔误。 - Raj

你的意思是 M = 4096/sizeof(int)。 - ugoren

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。

- Alexey Frunze