我正在努力学习考试……我找到了这个例子,但不明白他们是如何得到答案的。谁能解释一下吗?
题:
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?
谢谢!!
最佳答案
假设您的系统为您的进程分配了两个帧,使得 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 程序结构。
关于arrays - 计算二维数组的页面错误数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15961582/