通过循环交换最小化页面错误的数量

Question

假定页面大小为1024个单词，并且每一行存储在一页中。如果操作系统为程序分配512帧并使用LRU页面替换算法，以下程序中的页面错误数量是多少？

int A[][] = new int[1024][1024];

Program 1:
for (j = 0; j < A.length; j++)
    for (i = 0; i < A.length; i++) 
        A[i][j] = 0;

Program 2:
for (i = 0; i < A.length; i++)
    for(j = 0; j < A.length; j++) 
        A[i][j] = 0;

我认为按行进行分页要比按列进行分页好，但是我不能支持我的主张。您能帮我计算页面错误数吗？

Answer 1

一种解决方法是通过仿真。您可以更改循环以输出分配的地址，而不是将其设置为零：

printf("%p\n", &A[i][j]);

然后，编写第二个模拟页面放置的程序，因此它将执行以下操作：

    uintptr_t h;
    uintptr_t work[NWORKING_SET] = {0};
    int lru = 0;
    int fault = 0;
    while (gethex(&h)) {
        h /= pagesize;
        int i;
        for (i = 0; i < NWORKING_SET && work[i] != h; i++) {
        }
        if (i == NWORKING_SET) {
              work[lru] = h;
              fault++;
              lru = (lru+1) % NWORKING_SET;
        }
   }
   printf("%d\n", fault);

有了该程序，您可以尝试多种遍历策略。 PS：我的lru刚好可以工作；我相信您可以做得更好。

Answer 2

对于第二个程序； CPU访问导致页面错误的行中的第一个int，然后在页面已经存在时访问该行中的其他int。这意味着（如果行从页面边界开始），每行将出现页面错误，可能是第一次启动该程序的代码时会出现一个页面错误，加上第一次使用该程序的堆栈时可能会出现另一个错误（如果是数组，则可能会出现另一个错误）。未在页面边界上对齐）；这可能会导致1026或1027页面错误。

对于第一个程序； CPU访问连续的第一个int，从而导致页面错误；但是当它访问同一行中的第二个int时，该页面已被逐出（成为“最近最少使用”并替换为另一个页面）。这意味着您在访问数组时将遇到1024 * 1024个页面错误（加上一个用于程序代码，堆栈等的错误）。这很可能会解决1048578页错误（只要阵列的开头对准“ sizeof(int)”）。

但是；所有这些都假定编译器无法优化任何东西。实际上，任何值得使用的编译器都极有可能将两个程序都转换为更像“ memset(array, 0, sizeof(int)*1024*1024);”的代码，它可以连续写入（如果基础CPU支持较大的写入，则可以在一个较大的写入中写入多个int ）。这意味着这两个程序都可能会导致1026或1027页面错误。