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

Question

我正在努力学习考试......我找到了这个例子但却无法理解他们是如何得到答案的.有人能解释一下吗？

题:

考虑二维数组A:int A [] [] = new int [100] [100]; 其中A [0] [0]位于页面大小为200的分页存储器系统中的位置200处.操作矩阵的小进程驻留在页面0(位置0到199)中.因此,每次取指令都来自第0页.对于两个页面帧,下面的数组初始化循环产生了多少页面错误,使用LRU替换并假设第一个页面帧包含进程而另一个最初是空的？

A:

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

B:

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

给出的正确答案是:a:100 x 50 = 5000 b: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.

其中第二个代码A[i][j]:

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.

我们可以通过另一种方式理解它:
在行专业中,行索引更改的次数我们需要新页面访问因为页面数量很小所以每个备选索引的页面错误在第一个循环行索引中更改为100*100次如在B循环行索引中更改100次,因此A/B = 100*100/100 = 100时页面错误率,如果页面错误数发生在A = 50,00,则B页错误数= 50, 00/100 = 50.

类似地,您可以计算列主要顺序的页面错误数,因为矩阵具有相同数量的行,而cols结果将相同.

类似的例子在我的书中给出:
下载pdf:操作系统书籍Galvin阅读第9章:虚拟内存部分:9.9.5程序结构.