The Gateway to Computer Science Excellence

0 votes

Assuming pages of size 128 words each and array is stored in row major, how many page faults will be generated in the following C program?

int A[128][128];

for(int j=0;j<128;j++)

for(int i=0;i<128;i++)

A[i][j]=0;

a)128

b)16384

c)0

d)None

int A[128][128];

for(int j=0;j<128;j++)

for(int i=0;i<128;i++)

A[i][j]=0;

a)128

b)16384

c)0

d)None

+1

@ mini panda yes it would be B as for every element we need new page so page fault would be 128*128=16384....if i would have been first loop than size thing must have created problem but here in this qsn its okk

0

But how? Then each page will contain 256 array elements right? That is 2 rows(128*2). Then the answer would get halved right?

+1

look when you have each element of size 2 bytes than as array is store row wise in one page you will have 64 elements i.e a[0][0].....a[0][64]...so we are accessing a[0][0] first ..................than a[1][0] so that will be stored in 3rd page i.e a[1][0]...a[1][64] so you need to bring new page in that will cause page fault............ now siilalrly for every i value you will need page fault ...

0

@ MiNiPanda and @ Shubham Shukla 6

consider word size is = size of int, otherwise you can get many answer

how can you say how many page faults without giving how many frames are allocated?

if no.of frames allocated =128 ====> it produce 128 page faults only

if no.of frames allocated < 128 ====> it produce 128^{2} page faults only

+1

@shaikmasthan here page size= 128 byte

now whether int element take 2 bytes or 4 bytes in abve qsn our page fault would be 128*128 only

But what if i would have been outer loop and j would have been inner loop than page fault would have been different and that would have dpend on integr size taken

if it would have been 2 than 1 page could have 64 elements so than page fault would have been 2*128 as for every i value you will get max 2 page fault

if size would have been 4 bytes than 1 page would have contained 32 elements than page fault would have been 4*128=512...as for every i value page fault would have been 4.

now whether int element take 2 bytes or 4 bytes in abve qsn our page fault would be 128*128 only

But what if i would have been outer loop and j would have been inner loop than page fault would have been different and that would have dpend on integr size taken

if it would have been 2 than 1 page could have 64 elements so than page fault would have been 2*128 as for every i value you will get max 2 page fault

if size would have been 4 bytes than 1 page would have contained 32 elements than page fault would have been 4*128=512...as for every i value page fault would have been 4.

0

Whatever be the size of int but it has to be equal to word size for this Q to get 2^{14} as answer.

And by default word size is taken as 4B(or 2B sometimes) and not 1B as far as i know after studying CO..

0

@ Shubham Shukla 6 ,

for generalizing those two implementations, i considered as word size is = size of int

not only for implementation given in this question...

i know what you said.... and more over how people arguing take int size=4 Bytes by default, like that people arguing that word = 4 Bytes...

0

0

not that here is a controversy with size of int, therefore you can't assume by default...

in your case, there is no controversy.... therefore you can assume by default as your wish..

in your case, there is no controversy.... therefore you can assume by default as your wish..

+1

In gate you can't guess anything by yourself untill it is mentioned ...and in gate they will surely mention the mapping...

so i thing any answer according to the guessing will correct in this senario

so i thing any answer according to the guessing will correct in this senario

+1 vote

Best answer

The answer seems to be $none\space of\space these$ to me, but trying to reach one of the other options by taking some assumptions.

Given that $128$ x $128$ words are stored in $row\space major$ order, ie; elements are stored row by row. so there are total $128$ pages, each page containing elements $A[i][0]$ to $A[i][127]$. [Word addressible memory is taken because the size of a word and integer are not given in bytes.]

Now in the loop of the program, the words are accessed in $column\space major$ order $\rightarrow A[0][0]$, $A[1][0]$, $A[2][0]$.. (inner loop is $i$).

Therefore a new page has to be accessed each time $A[i][j]$ is accessed.[Another assumption here, number of pages in memory at a time $<= 128$]

Hence the total number of page faults $= 128 * 128 = 16384$

So, the answer is $(B)$

Given that $128$ x $128$ words are stored in $row\space major$ order, ie; elements are stored row by row. so there are total $128$ pages, each page containing elements $A[i][0]$ to $A[i][127]$. [Word addressible memory is taken because the size of a word and integer are not given in bytes.]

Now in the loop of the program, the words are accessed in $column\space major$ order $\rightarrow A[0][0]$, $A[1][0]$, $A[2][0]$.. (inner loop is $i$).

Therefore a new page has to be accessed each time $A[i][j]$ is accessed.[Another assumption here, number of pages in memory at a time $<= 128$]

Hence the total number of page faults $= 128 * 128 = 16384$

So, the answer is $(B)$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,373 answers

198,513 comments

105,289 users