arrays - 计算二维数组的页面错误数

Question

我正在努力学习考试……我找到了这个例子，但不明白他们是如何得到答案的。谁能解释一下吗？

题:

Consider the two-dimensional array A: int A[][] = new int[100][100]; where A[0][0] is at location 200 in a paged memory system with pages of size 200. A small process that manipulates the matrix resides in the page 0 (location 0 to 199). Thus every instruction fetch will be from page 0. For two page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that the first page frame contains the process and the other is initially empty?

A:

for (int j=0;j<100;j++)
   for (int i=0; i<100; i++)
     A[i][j] = 0;

乙:

for(int i=0; i<100; i++)
  for (int j=0; j<100; j++)
      A[i][j] = 0;

给出的正确答案是:
一:100 x 50 = 5000
乙:50

我有点理解第一部分。共有 50 页。 (10000/200=50) 并且每次 j 更改时，都会发生页面错误..所以总共有 100 个页面错误..但是为什么乘以 50？为什么第二个是 50？

谢谢!!

Answer 1

假设您的系统为您的进程分配了两个帧，使得 200 * sizeof(int)矩阵可以一次保存在内存中。矩阵的分配发生在 Row Major Order .

在第一个循环中 A :

for (int j=0;j<100;j++)
   for (int i=0; i<100; i++)
     A[i][j] = 0;

矩阵列方式的循环访问存储器单元，如:

A[0][0], A[2][0], A[3][0], ...A[0][2], A[0][3], A[0][4], ......
  ^        ^        ^   
      row changes               

在每次迭代 行更改 并且分配在行主要并且每行占用一页。所以代码 A将导致每个替代项的页面错误 A[i][j]访问所以页面错误总数 = 100 * 100/2) = 5000。

其中第二个代码 B :

for(int i=0; i<100; i++)
  for (int j=0; j<100; j++)
      A[i][j] = 0;

在每次迭代中按行循环访问矩阵的内存单元，例如:

A[0][0], A[0][5], A[0][6],...,A[1][0], A[1][7], A[1][8],...,A[2][0], A[2][9],
     ^        ^        ^  
  column changes, row are same 

逐行访问(读取时列更改 行更改仅在 100 次读取后才更改 )，一次加载一行，因此在行更改时发生页面错误(对于外循环)，并且对于每个替代行访问都会发生页面错误所以页面错误数 = 100/2 = 50。

我们可以通过另一种方式理解它，例如:
在行主要中，行索引更改的次数我们需要新页面来访问，因为页数很小，第一个 A 循环行索引更改 100*100 次，而 B 循环行索引更改 100 次。倍所以 A/B 中的缺页率 = 100*100/100 = 100，如果 A 中的缺页次数 = 50,00，那么 B 中的缺页次数 = 50,00/100 = 50。

同样，您可以计算 Column-major order 的页面错误数并且因为矩阵具有相同的行数并且 cols 结果将相同。

我的书中给出了类似的例子:
下载pdf: operating system book Galvin阅读第 9 章:虚拟内存部分:9.9.5 程序结构。