GATE IT 2008 | Question: 41

Question

Assume that a main memory with only $4$ pages, each of $16$ bytes, is initially empty. The CPU generates the following sequence of virtual addresses and uses the Least Recently Used (LRU) page replacement policy.

$\text{0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92}$

How many page faults does this sequence cause? What are the page numbers of the pages present in the main memory at the end of the sequence?

• A. $6$ and $1, 2, 3, 4$
• B. $7$ and $1, 2, 4, 5$
• C. $8$ and $1, 2, 4, 5$
• D. $9$ and $1, 2, 3, 5$

Comments

Why we are taking more than p3 considering main memory with only 4 pages given in question?? can someone explain

---

bro it means there are 4 frames not it means just 4 pages bcoz they told mm pages not disk pages

---

$$\text{page number} = \left\lfloor \frac{\text{virtual address}}{\text{page size}} \right\rfloor$$

Answer 1

At first we have to translate the given virtual addresses (which addresses a byte) to page addresses (which again is virtual but addresses a page). This can be done simply by dividing the virtual addresses by page size and taking the floor value (equivalently by removing the page offset bits).  Here, page size is $16$ bytes which requires $4$ offset bits. So,

$0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92 \implies \ 0,0,0,1,1,2,2,0,4,4,5,5,1,2,5,5$

We have $4$ spaces for a page and there will be a replacement only when a $5^{th}$ distinct page comes. Lets see what happens for the sequence of memory accesses:$$\small \begin{array}{|c|c|c|clc|}\hline\textbf{Incoming}&\textbf{Page Address} & \textbf{No. of Page Faults}& \textbf{Pages in Memory}\\ 
\textbf{Virtual Address}&&&\textbf{in LRU Order} \\ \hline
0  & 0&1&0 \\ \hline
4  & 0&1&0 \\ \hline
8  & 0&1&0 \\ \hline
20  & 1&2&0,1 \\ \hline
24  & 1&2&0,1 \\ \hline
36  & 2&3&0,1,2 \\ \hline
44  & 2&3&0,1,2 \\ \hline
12  & 0&3&1,2,0 \\ \hline
68  & 4&4&1,2,0,4 \\ \hline
72 & 4&4&1,2,0,4 \\ \hline
80  & 5&5&2,0,4,5 \\ \hline
84  & 5&5&2,0,4,5 \\ \hline
28  & 1&6&0,4,5,1 \\ \hline
32  & 2&7&4,5,1,2 \\ \hline
88  & 5&7&4,1,2,5 \\ \hline
92  & 5&7&4,1,2,5 \\ \hline
\end{array}$$So, (B) choice.

Comments

Thank you Arjun sir

---

Why we are taking more than p3 considering main memory with only 4 pages given in question?? can someone explain

---

Not answered properly.

Answer 2

The page size is 16B, So in virtual address, the page offset takes  4bits.
 

Page_number

Offset(4bits)

So in a virtual address, the 4 LSBs are for offset.
For page number, we should focus on rest bits.

Now lets see the binary of those addresses and lets exclude the 4 LSBs.
0:    0 | 0000
4:    0 | 0100
8:    0 | 1000
20:  1 | 0100
24:  1 | 1000
36:  10 | 0100
44:  10 | 1100
12:  0  | 1100
68:  100 | 0100
72:  100 | 1000
80:  101 | 0000
84:  101 | 0100
28:  1 | 1100
32:  10 | 0000
88:  101 | 1000
92:  101 | 1100

So we can say the requests came for page 0, 0 ,0 ,1 ,1 ,10 ,10 ,0 ,100 ,100, 101 ,101 ,1 ,10 ,101 , 101 
Now just take a frame with size 4 and answer this question using LRU page replacement policy.


LRU Page replacement:

0 (X)	10
1 (X)	101
10 (X)	1
100

Clearly the number of page-faults = 7
The elements which are in memory at the end of the sequence are 10,101,1,100  ...i.e 2,5,1,4
So option B is the answer.

Comments

this is well explained..

---

this should be the best answer

---

nice explanation@ Ahwan

---

@Ahwan,

Very well explained.

---

Best explanation.

---

why this is not included in best answer ?

---

nicely explaned

---

Thanks!! Nicely explained!!

---

thanks , very well explained !!

---

this is the best answer i come across

---

Such presence of mind is needed during exam. :(

---

Add it to best answer plz

 

---

Great analysis @Ahwan !!!

---

Great Answer

Answer 3

I hope this will be  the easiest solution for you 

All virtual address page wise ( page numbering start from zero )

                             Cpu address requests

page 0 : 0-15          ( 0,4,8,12)

page 1: 16-31          (20,24,28)

page 2: 32-47          (32,36,44)

page 3: 48-63          No address request 

page 4: 64-79         (68,72)

page 5: 80-95         ( 80,84,88,92 )

So our new request is like this page wise

0,0,0,1,1,2,2,0,4,4,5,5,1,2,5,5

---

LRU working 

0x  2

1x  5

2x  1

4

Total page faults are 7.

2,5,1,4 are the elements remaining in the final state.

ANSWER (B)

Note: 0x 2 means page number 0 is replaced with page number 2  according to the LRU algorithm.

 

Comments

this was the easiest indeed thank you !

---

BEAUTIFULLY EXPALINED. THANKS

---

Thanks for this short and easiest answer

Answer 4

The page size is 16B, So in virtual address, the page offset takes  4bits. 
So in a virtual address, the 4 LSBs are for offset. 
For page number, we should focus on rest bits. Here one thing to notice is, every virtual address request is to fetch only single byte from main memory so if 1 page fault occurs all 16 byte or whole page will be stored into main memory so another request from same byte range will not cause page fault
0:  page no(0)  0 | 0000 
4:  page no(0)  0 | 0100 
8:  page no(0)  0 | 1000 
20: page no(1)  1 | 0100 
24: page no(1)  1 | 1000 
36: page no(2) 10 | 0100 
44: page no(2) 10 | 1100 
12: page no(0) 0  | 1100 
68: page no(4) 100 | 0100 
72: page no(4) 100 | 1000 
80: page no(5) 101 | 0000 
84: page no(5) 101 | 0100 
28: page no(1)   1 | 1100 
32: page no(2 ) 10 | 0000 
88: page no(5) 101 | 1000 
92: page no(5) 101 | 1100

So our new request is like this page wise
0,0,0,1,1,2,2,0,4,4,5,5,1,2,5,5
initially main memory is empty so map it sequentially into empty slots and for replacement use LRU.

The shortcut method is page 0 of main memory can hold 16 bytes so virtual address generated between 0-15 could be directly mapped to page 0(initially any page of process could be stored into any page of main memory), similarly for others.
page 0 : 0-15          ( 0,4,8,12)

page 1: 16-31          (20,24,28)

page 2: 32-47          (32,36,44)

page 3: 48-63          No address request 

page 4: 64-79         (68,72)

page 5: 80-95         ( 80,84,88,92 )

here also the sequence is 0,0,0,1,1,2,2,0,4,4,5,5,1,2,5,5

I deliberately stored page 0,1,2,4 inverted just to let you know that process page could be stored any where in the main memory.

0,1,2,4,5,1,2 are the page fault.

Answer 5

Word addresses are given in decimal(2 bits) therefore 10^2 words are possible by the process (0-99) . Assuming memory to be byte addressable 100 words = 100 bytes. Now each line contains 16 bytes, hence to find the page number where the word belong to, just divide the word generated by line size(16) floor (word/16) will give us page number. Further the task becomes easy, just apply algorithm given according to page numbers.

Answer 6

answer that I am getting is 7 page faults and 3,6,2,5 pages in main memory :(

Comments

There is no pages 3, 6, 2, 5.. we are missing some concept.. Please Arjun sir help!!

---

I counted from 1 instead of 0...