Question

Determine for the following code how many pages are transferred between disk and main memory. Assume each page has 1024 words, the active memory set size is 512 (i. e., at any time no more than 512 pages may be in main memory), and the replacement strategy is LRU (the Least Recently Used page is always replaced); also assume that all 2D arrays are of size (1:2048, 1:2048), with each array element occupying one word, for I := 1 to 2048 do for J :=1 to 2048 do { A[J,I]:=A[J,I]*B[I,J] } provided the arrays are mapped into the main memory space in column-major order,

Answer 1

SOLUTION -

Since the arrays are mapped into the main memory space in coulmn-major order. Hence element A[I, J] , A[I+1,J], A[I+2,J],... are contiguosly located.

Now in array A, once A[I, J] is loaded into a page for the first time, then the elements A[I, J] , A[I+1,J],...,A[I+1023,J] will also be loaded into the main memory space. But since the next element to access after A[I, J] will be A[I, J+1] which is not in the main memory. Hence every access to A[I, J] with 1 <= I <=2048 will cause a page-fault.

Also since there are only 512 pages but there are 2048 possible index of column and row numbers, hence once a page holding element A[I, J] is loaded into the main memory, then it will not persist till the requirement of A[I, J+1] because of being replaced by that time using LRU replacement strategy.

Hence total number of page fault due to array A will be 2048*2048= 2²² page faults

Now since array B is accesses column-wise. Hence once element B[I,J] is loaded for first time then B[ I+1023, J] will also be in same page if B[I, J] is starting element in a page.

Hence our of 2²² accesses to array B, total number of page faults = 2²² / 1024 =2¹² page faults

Hence, total number of page transfer between disk and main memory =

2²² +  2¹² = 2¹² * (1024 + 1 ) = 1024 * 2¹²    

IF YOU HAVE ANY DOUBT PLEASE COMMENT DOWN BELOW I WILL SOLVE IT FOR YOU:)
----------------PLEASE RATE THE ANSWER-----------THANK YOU!!!!!!!!----------