17

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

问题：

考虑二维数组 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;

乙：

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？

谢谢！！

4

4 回答 4

9

假设您的系统为您的进程分配了两个帧，这样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 顺序的页面错误数，因为矩阵具有相同的行数，并且 cols 结果将相同。

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

于 2013-04-12T01:55:01.980 回答
2

这里的关键是查看从线性内存地址读取时所有数组访问的外观。还必须假设行优先 (C) 顺序才能使答案有意义。该问题还遗漏了单位，我们假设它们是字节（因此 A 必须以 1 字节类型保存）。

char *B = &(A[0][0]); (memory address 200)

访问A[i][j]现在等同于B[i*100 + j]或*(200 + i*100+j)（行主要顺序）。两页可以放入内存。一个由程序获取（字节 0-199 - 也是 C 约定）。另一种是访问A，跨越100*100字节/（200字节/页）=50页。

由于 0-199 始终在内存中，因此另一页将寻址 n*200 到 (n+1)*200-1，其中 n 是某个整数——一次对应于 A 的 2 行。

最后，在页面错误时，最近最少使用 (LRU) 算法将刚刚从页面 0-199 读取一条指令，因此总是会丢弃保存 A 的旧部分的页面以读取 A 的新部分（当 n 更改时） ，每 2 行）。

因此，您可以通过读取 100x100 矩阵的行轻松查看发生了什么——每 2 行交换一个页面，并且在外部循环中重复 100 次（从左到右跨行）。这会导致 100x50 的页面错误。

在现实世界中，您可以使用linux 命令或getrusage跟踪页面错误。

于 2013-11-29T05:04:37.213 回答
1

因此，二维数组中总共有 50 页，逐行或逐列存储。

如果您逐行存储页面并逐行访问它们，那么您将一遍又一遍地访问同一页面，直到到达下一页，因此您仅切换页面（导致页面错误）50次，因为有50页。

如果您逐行存储页面，并逐列（或虎钳）访问它们，您将从一个页面获取一个元素，切换页面，从另一页面获取一个元素，切换页面等。所以您仍然会经历50 页，但每页切换 100 次。

想象你正在阅读一篇论文。如果您一次阅读一页，那么您将每页翻一次。如果您从每一页中读取一行，然后重新开始并阅读第二行，第三行等。您将不得不一遍又一遍地翻阅整张纸，对于页面上的每一行（假设所有页面的编号相同）像数组一样的行数）...每次翻页都是页面错误。

于 2014-04-24T21:38:49.353 回答
1

让我们看一个人为但内容丰富的例子。假设页面大小为 128 个字。考虑一个 C 程序，其功能是将 128×128 数组的每个元素初始化为 0。以下代码是典型的：

int i, j;
int[128][128] data;
for (j = 0; j < 128; j++)
  for (i = 0; i < 128; i++)
data[i][j] = 0;

请注意，该数组存储的主要是行；即数组存储data[0][0],data[0][1],···,data[0][127],data[1][0],data[1][1] ，···，数据[127][127]。对于 128 个单词的页面，每行占一页。因此，前面的代码将每一页中的一个字归零，然后每一页中的另一个字归零，以此类推。如果操作系统为整个程序分配的帧少于 128 个，那么它的执行将导致 128 × 128 = 16,384 个页面错误。

相反，假设我们将代码更改为

int i, j;
int[128][128] data;
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i][j] = 0;

此代码在开始下一页之前将一页上的所有单词归零，从而将页面错误的数量减少到 128。

于 2014-11-13T03:28:42.613 回答