计算页面错误数2-D阵列 [英] Calculating number of page faults for 2-d array

问题描述

我想学习的exam..and我发现这个例子，但无法理解他们是如何得到的答案。谁能解释一下吗？

I am trying to study for an exam..and I found this example but can't understand how they got the answer. Can anyone explain it please?

问：

考虑二维数组A：
  int类型的[] [] =新INT [100] [100];
  其中A [0] [0]是在位置200与200尺寸小的过程，操纵矩阵驻留在0页（地址0到199）的页面分页内存系统。因此，每一个取指令将从0页。
  两页帧，页故障多少由以下数组初始化环路产生，使用LRU替换和假定第一页帧包含过程和其它最初是空

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?

答：

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

A：

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

给出的正确答案是：
答：100×50 = 5000
A：50

The correct answer given is : a: 100 x 50 = 5000 b: 50

我有所了解的第一部分。总共有50个页面。 （200分之10000= 50），每一个时刻j的变化，缺页occurs..so共100页的faults..but这是为什么乘以50？为什么是第二个50？

I somewhat understand the first part. There are total of 50 pages. (10000/200=50) and every time j changes, a page fault occurs..so a total of 100 page faults..but why is that multiplied by 50? and why is the second one 50?

谢谢！

推荐答案

假设你的系统分配的两帧为您处理，这样， 200 * sizeof的（INT）矩阵可以被保留在内存在的时间。与分配的矩阵发生在行优先顺序。

Suppose your systems allocated Two Frames for your process such that 200 * sizeof(int) of matrix can be keep in memory at a time. And allocation for matrix happens in Row Major Order.

在第一循环的 A

In first loop A:

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

循环存取记忆体细胞矩阵列明智的，如：

loop access memory cells for matrix column-wise like:

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

在每次迭代中的行更改并分配行重大，每行需要一个页面。因此code A 将导致页错误每个备选A [i] [j]的页面错误的访问，使总数为= 100 * 100/2）= 5000

At each iteration Row changes and allocation is in row major and each row takes one page. so code A will causes page fault for each alternative A[i][j] access so total number of page faults are = 100 * 100 / 2) = 5000.

在哪里为第二code B ：

Where as second code B: :

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

循环存取记忆体细胞矩阵在每次迭代行明智的，如：

loop access memory cells for matrix row-wise on each iteration, like:

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。

Access row wise(columns changes at read read row changes only after 100 read), One row loaded at time so page fault happens when row changes (for outer loop) and for each alternative row access a page fault happens so number of page faults = 100/2 = 50.

我们可以把它理解像另一个途径：结果
在排专业，次排指数的变化数，我们需要新的页面来访问，因为页数是每个替代指数的变化很小它缺页第一环路排指数的变化100 * 100次，其中作为B中环行索引改变100时间，以便在页面故障配给两个A / B = 100 * 100/100 = 100，并且如果页面错误的数目发生在A = 50,00然后在页面故障的数量为B ​​= 50,00 / 100 = 50

we can understand it another ways like:
In row major, Number of times row index changes we need new page to access because number of pages are small it page fault on each alternative index change in first A loop row index changes 100*100 times where as in B loop row index changes 100 times so page fault ration in both A/B = 100*100/100 = 100, and if number of page faults happens in A = 50,00 then in B number of page faults = 50,00/100 = 50.

同样可以计算页面故障数列主顺序因为矩阵具有行相等数目和COLS导致将相同。

Similarly you can calculate number of page-faults for Column-major order and because matrix has equal numbers of rows and cols result will be same.

类似的例子在我的书中给出：结果
下载pdf文件：<一href=\"http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC4QFjAA&url=http://it325blog.files.word$p$pss.com/2012/09/operating-system-concepts-7-th-edition.pdf&ei=8GlnUZSFNc3rrQe4qYDgDg&usg=AFQjCNHvytXcx-0_2TSlqbsj94nEd0JyKw&bvm=bv.45107431,bs.1,d.bmk\"相对=nofollow>操作系统书高尔文阅读第9章：虚拟内存部分：9.9.5程序结构。

The similar example is given in my book:
Download a pdf: operating system book Galvin Read chapter 9: Virtual Memory Section: 9.9.5 Program Structure.

这篇关于计算页面错误数2-D阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！