A two-dimensional 512 x 512 array is stored in row major order in a paged virtua

Question

A two-dimensional 512 x 512 array is stored in row major order in a paged virtual memory system with page size 512. Row-major order means the array is laid out in memory row after row, with the first row first. All elements of the array must be accessed sequentially. Initially, the entire array is on disk. There are 16 frames of physical memory available for processing the array. (a) For the FIFO page replacement discipline, how many page faults will be generated when accessing all elements of the array sequentially: i. in row major order (i.e., row after row) ii. in column major order (i.e., column after column) (b) Would the number of page faults be different under the LRU policy?

Explanation / Answer

A. In FIFO page replacement, the oldest page is replaced first when a page fault occurs.

i) With 16 frames of page size 512, each frame can hold one row. Therefore when the array is accessed in row major order, like a[i][j], the value of j changes in each iteration and i value remains the same in the inner loop as shown below

for(int i=0;i<512;i++) ----> outer loop

for(int j=0;j<512;j++) ----> inner loop

a[i][j]

Initially the entire array is on disk. So when the first element of array(a[0][0]) is accessed it results in page fault. So the first row(0th row) is placed on the first frame. The following 511 elements from a[0][1] to a[0][511] are available in the first frame. So there is no page fault for the next 511 elements. The next page fault occurs when the row value changes to 1. Like that for each next row(outer loop) page fault occurs. When all the 16 frames are placed with rows from 0 to 15, when next 16th row has to be placed, the first frame having 0th row is replaced with 16th row, like that 1th row replaced with 17th row, 2nd row replaced with 18th row. Therefore in total 512 page faults will be generated while accessing the array in row major order.

ii) When the array is accessed in column major order, the loop will be :

for(int j=0;j<512;j++) ----> outer loop

for(int i =0; i<512;i++) ----> inner loop

a[i][j]

value of i changes in each iteration and j value remains the same in the inner loop as shown above. When first element is accessed a[0][0], it. results in a page fault. The first frame is placed with the 0th row as the array is placed in row major order in the disk. When the next element a[1][0] is accessed, it results in a page fault. So for each element accessed in inner loop(a[0][0] to a[511][0]), it results in page fault. So the total number of page faults for inner loop is 512 for the first iteration (j=0) of outer loop.

For the second iteration of outer loop where j=1, the frames contains data from a[496][0] to a[511][511](1st frame has a[496][0] to a[496][511] and so on till last 16th frame having from a[511][0] to a[511][511]). So when a[0][1] has to be accessed it results in page fault. Hence again for each element to be accessed in inner loop results in same 512 page faults for that second iteration of outer loop.

Like that for all iterations of outer loop 512 page faults occurs in column major order. Therefore in total there are 512*512 = 262144 page faults, when array is accessed in column major order.

b. In Least Recently Used page replacement algorithm, the page which is not used recently is replaced. In sequential access of array, the oldest page(page having array elements that are refered earlier in previous iterations) is the page which is not recently used. Hence that page is replaced with new one. Therefore it is same as FIFO page replacement for array access. Hence number of page faults will not be different for LRU when compared with FIFO in this array access scenario.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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