# Andrew S. Tanenbaum (OS) Edition 4 Exercise 3 Question 38 (Page No. 258)

1 vote
88 views

Consider the following two-dimensional array:

int X[64][64];

Suppose that a system has four page frames and each frame is $128$ words (an integer occupies one word). Programs that manipulate the $X$ array fit into exactly one page and always occupy page $0.$ The data are swapped in and out of the other three frames. The $X$ array is stored in row-major order $(i.e., X[0][1]$ follows $X[0][0]$ in memory$).$ Which of the two code fragments shown below will generate the lowest number of page faults? Explain and compute the total number of page faults.

Fragment A
for (int j = 0; j < 64; j++)
for (int i = 0; i < 64; i++) X[i][j] = 0;

Fragment B
for (int i = 0; i < 64; i++)
for (int j = 0; j < 64; j++) X[i][j] = 0;


(B) If you are accessing  through ROW major order then for every 128 entries there is only 1 page fault

EX: in frame 2:

X[0][0],X[0][1]..........X[0][64], X[1][0],X[1][1]..........X[1][64].

only  X[0][0] is page fault

and total references are 64*64

so total page faults are  (64*64)/128=32

OR you can say that The inner loop causes only one page fault for every other iteration of the outer loop. Hence, 32 page faults occur.

(A)  If you are accessing  through COLUMN major order then for every 2 entries there is only 1 page fault

EX: in frame 2:

X[0][0]X[0][1]..........X[0][64], X[1][0],X[1][1]..........X[1][64].

only  X[1][0] is hit

and total reference are 64*64

so total page faults are  (64*64)/2=2048

OR you can say that The inner loop causes 32 page faults for every iteration of the outer loop. Hence, 2048 page faults occur.

## Related questions

1
71 views
Suppose that two processes $A$ and $B$ share a page that is not in memory. If process $A$ faults on the shared page, the page table entry for process $A$ must be updated once the page is read into memory. Under what conditions should the page table update ... of process $A's$ page fault will bring the shared page into memory? Explain. What is the potential cost of delaying the page table update?
1 vote
A computer has four page frames. The time of loading, time of last access, and the $R$ and $M$ bits for each page are as shown below (the times are in clock ticks): Which page will NRU replace? Which page will FIFO replace? Which page will LRU replace? Which page will second chance replace?
How long does it take to load a $64-KB$ program from a disk whose average seek time is $5\: msec,$ whose rotation time is $5 msec,$ and whose tracks hold $1\: MB$ for a $2-KB$ page size? for a $4-KB$ page size? The pages are spread randomly around the disk and the number of cylinders is so large that the chance of two pages being on the same cylinder is negligible.
Write a program that will demonstrate the difference between using a local page replacement policy and a global one for the simple case of two processes. You will need a routine that can generate a page reference string based on a statistical model. This model has $N$ ... a global policy instead of a local one. Also, contrast the per-process page fault rate with that of the local policy approach.