PLEASE READ THE ENTIRE QUESTION, THIS IS FOR 50 PAGE FRAMES, NOT 2. Consider the

Question

PLEASE READ THE ENTIRE QUESTION, THIS IS FOR 50 PAGE FRAMES, NOT 2.

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 page
0 (locations 0 to 199). Thus, every instruction fetch will be from page 0.
For 50  page frames, how many page faults are generated by
the following array-initialization loops, using LRU replacement and
assuming that page frame 1 contains the process and the other two
are initially empty?

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;

Explanation / Answer

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.

In first loop A:

loop access memory cells for matrix column-wise like:

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

Where as second code B: :

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

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/50 = 2.

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 = 200 then in B number of page faults = 200/100 = 2.

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.

The similar example is given in my book:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.