retagged by
1,199 views
5 votes
5 votes

Consider the $2$ dimensional array $A$:

int A[][]=new int[100][100];

where $A[0][0]$ is at location $800$ in a paged memory system with pages of size $800 bytes$. Each int type needs 4 bytes and A is stored in row-major order. A small process that manipulates the matrix resides in page $0$ (Locations 0 to 799). Thus every instruction fetch will be from page $0$. For $3$ 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 other $2$ are initially empty?

for (int i=0;i<100;i++)
for (int j=0;j<100; j++)
    A[j][i]=1;
retagged by

1 Answer

Best answer
8 votes
8 votes
There are are $100*100 = 10,000$ elements in the array.

Page size $= 800$ bytes, int size $= 4$ Bytes, hence each page can contain $800/4 = 200$ int elements

Array is accessed column wise and array is stored in the memory row wise. for example $A[0][0], A[1][0], A[2][0]$ an so on elements are accessed.

A single memory page can contain 200 elements (or) 2 rows on single access to memory

1. From $A[0][0] to A[0][99]$ and from $A[1][0] to A[1][99]$

2. From $A[2][0] to A[2][99]$ and from $A[3][0] to A[3][99]$, and so on..

It means every first access is miss and every second access is hit, so miss rate $= 50%$, hit rate$=50%$.

There are $10,000$ elements in the array, hence there will be $5000$ miss.
selected by
Answer:

Related questions