search
Log In
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;
in Operating System 88 views

1 Answer

0 votes

(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

0 votes
0 answers
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?
asked Oct 26, 2019 in Operating System Lakshman Patel RJIT 71 views
1 vote
1 answer
2
389 views
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?
asked Oct 26, 2019 in Operating System Lakshman Patel RJIT 389 views
1 vote
0 answers
3
46 views
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.
asked Oct 26, 2019 in Operating System Lakshman Patel RJIT 46 views
0 votes
0 answers
4
51 views
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.
asked Oct 26, 2019 in Operating System Lakshman Patel RJIT 51 views
...