The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 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++)
in Others by Active (2.5k points)
edited by | 180 views

@Magma  @akash.dinkar12explain this please.

1 Answer

+5 votes
Best answer
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.
by Active (4.5k points)
selected by
But I have a doubt. Page0 contains code from 0-199. Now 600 Bytes left.In this 600 Bytes, 150 elements of array can be stored and hence since A[0][0] is stored from 200, so full 1st row of 100 elements plus 50 elements of Row 2 are in the Page0(A[1][0]..A[1][49]). Accesses to 0th-row elements and first 50 elements of the 1st row(A[1][0]...A[1][49]) won't cause page faults as the code is continuously accessed from page 0 and hence Page 0 will never be swapped out of memory.

Don't you think the answer would change?
yes, but it was a typo in question. Fixed now
ahhhh thank you so much sir. That was making my head go round in counting misses. :)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,729 answers
79,935 users