edited by
23,533 views
63 votes
63 votes

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?

  1. $6$ and $1, 2, 3, 4$
  2. $7$ and $1, 2, 4, 5$
  3. $8$ and $1, 2, 4, 5$
  4. $9$ and $1, 2, 3, 5$
edited by

6 Answers

Best answer
79 votes
79 votes

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.

edited by
136 votes
136 votes

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.

8 votes
8 votes

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.

 

5 votes
5 votes

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:

Related questions

35 votes
35 votes
5 answers
3