GATE CSE 1996 | Question: 7

Question

A demand paged virtual memory system uses $16$ bit virtual address, page size of $256$ bytes, and has $1$ Kbyte of main memory. $\text{LRU}$ page replacement is implemented using the list, whose current status (page number is decimal) is

For each hexadecimal address in the address sequence given below,

$\text{00FF}, \text{010D}, \text{10FF}, \text{11B0}$

indicate

1. the new status of the list

2. page faults, if any, and

3. page replacements, if any.

Comments

If anyone please explain how hexadecimal 00,01,10,11 numbers are converted into 0,1,16,17?

---

if your ques is that how 11 is written as 17, it is simple hexadecimal to decimal conversion.

11 = 0001 0001 = 17

if you are asking that if there are only 4 pages then how the page no. became 16, 17, then these are the page nos. of the process, taken from virtual address, and these will further be mapped to physical address may be 0,1,2,3.

a process can be bigger than physical memory and hence may have more pages.

---

suppose for (11)= 1*((16)^1)+1*16^0

simple hexa to decimal conversion

---

How lru is performing i mean how i know 17 is replaced by 16 and similarly 17 By 63 @Srestha @arjun

Answer 1

Given that page size is $256$ bytes $(2^8)$ and Main memory (MM) is 1KB $(2^{10}).$

So total number of pages that can be accommodated in MM $= \frac{2^{10}}{2^8} = 4.$

So, essentially, there are $4$ frames that can be used for paging (or page replacements).

The current sequence of pages in memory shows $3$ pages $(17, 1, 63).$ So, there is $1$ empty frame left. It also says that the least recently used page is $17.$

Now, since page size given is $8$ bits wide $(256\; B),$ and virtual memory is of $16$ bit, we can say that $8$ bits are used for offset. The given address sequence is hexadecimal can be divided accordingly:$$\small \begin{array}{|c|c|c|}\hline \textbf{Page Number} & \textbf{Offset}  & \textbf{Page Number}\\
\textbf{in Hexadecimal} & \textbf{}  & \textbf{in Decimal}
\\\hline  \text{00} & \text{FF}  & \text{0}\\   \text{01} & \text{0D}  & \text{1} \\ \text{10} & \text{FF}  & \text{16} \\ \text{11} & \text{B0}  & \text{17} \\\hline \end{array}$$
We only need the Page numbers, which can be represented in decimal as: $0, 1, 16, 17.$

Now, if we apply LRU algorithm to the existing frame with these incoming pages, we get the following states:
$$\begin{array}{c|c}
0 & \text{Miss}&17\quad 1 \quad 63 \quad \bf{0}\\
1 & \text{Hit}&17\quad \textbf{1} \quad 63 \quad 0\\
16 & \text{Miss}&\textbf{16}\quad 1 \quad 63 \quad {0}\\
17 & \text{Miss}&16\quad 1 \quad \textbf{17} \quad {0}\\
\end{array}$$

1. New status of the list is $\mathbf{16 \ 1  \ 17 \ 0}$.
2. Number of page faults $\mathbf{= 3}$.
3. Page replacements are indicated above.

Comments

Well explained!!!. But shouldn't the order of elements in the list reflect their recency of usage? I mean the new status of the list will be

0 1 16 17

rt?

---

Question says that the LRU page is 17 (Marked by an arrow). So replacements will start from there (if needed). 0 will not cause a replacement (since one more space is available). 16 will cause the first replacement followed by 17. I have shown which pages require replacement and which ones don't.

LRU uses separate data structures like counters and stacks to store the recency of use. Here we are only showing the state of memory of the pages - relative order of pages does not change with recency. Question shows the current status only that is not necessarily sorted in order of recency.

---

In the question it is mentioned that LRU is implemented using "list". So, the order in the list should reflect the recency. Otherwise, suppose the page references where 0, 5 and 6. 5 will replace 17 but we can't say if 6 will replace 1 or 63. 

http://www.informit.com/articles/article.aspx?p=25260&seqNum=7

---

If you see the question, the page references are "carefully" chosen so that there is only 1 way that it can happen. Of course if the incoming page request sequence was different from this, there would have been more than one way of doing it. But this is a cleverly designed case. Why?:

1. 0 comes first, whatever be the sequence, it has to go to the last frame.

2. 1 comes next. It is a hit. Clearly, it cannot be replaced after this unless 17 and/or 63 are gone - again sequence independent.

3. 16 comes next. We know that 17 is LRU page. 1 and 0 have got a hit recently. 63 cannot get replaced since 17 was declared LRU. Again - whatever be the sequence, you must replace 17.

4. When 17 comes, we know that 1 and 0 have had a hit recently. So the most likely candidate is 63. And there you go - 63 is replaced with 17.

So in this particular case, there is no way that you can come up with an alternate sequence.

---

Yes. That is true. But my point is that

"if LRU is implemented using list, the order of elements must reflect the recency."

---

Ya, according to the link you have provided, it says about "linked list" implementation where order is maintained. If it the same thing here then we should show it in the order of recency of reference.

---

How did 10 and 11 n Hex became 16 and 17 in Decimal

---

Just a simple conversion from hexadecimal to decimal. :D

---

So #page replacements  = 2.

---

is page replacements same as page faults

---

Page fault is the action part while page replacement is the reaction part. Page has to be replaced due to page fault. Both are different.

---

I also got the sequence of list: 0,1,16,17 where 0 is Least Recently used page.

after reading the comments got satisfied.

Nice explanation.

---

What will be the final status of the list 0 1 16 17 OR 16 1 17 0 ??

---

why we are taking window size as 4 we need 1 page for page table entry also, shouldn't it be 3

---

how FF = 0 AND

        FF=  16  CAME?

---

You are seeing only the offest part which is FF and its page no is 00, leading to page no 0 in decimal.

In second line of your comment, offest remains the same, but page no is 10 which results in 16 in decimal.

(00)to base16=(0)to base10. And (10)to base16= (16)to base 10.

I hope it helps.

Answer 2

number of frames$=\frac{2^{10}B}{2^8B}=4$

$VA=16-bits$

$page\ \#$	$word-offset$
$8-bits$	$8-bits$

$\underbrace{00000000}|11111111=00|FF$

Page $0$

$\underbrace{00000001}|00001101=01|0D$

Page $1$

$\underbrace{00010000}|11111111=10|FF$

Page $16$

$\underbrace{00010001}|10110000=11|B0$

Page $17$

$page-references\Rightarrow$	$17$	$1$	$63$	$0$	$1$	$16$	$17$
$4^{th}-Frame$				$0$	$0$	$0$	$0$
$3^{rd}-Frame$			$63$	$63$	$63$	$63$	$17$
$2^{nd}-Frame$		$1$	$1$	$1$	$1$	$1$	$1$
$1^{st}-Frame$	$17$	$17$	$17$	$17$	$17$	$16$	$16$
				$Fault$		$Fault$	$Fault$

$a)\Rightarrow 16,1,17,0$

$b)\ 3$

Comments

0,1,16,17;

---

c) 2. Because page numbers 17 and 63 were replaced with 16 and 17 (in the 1^st and 3^rd frames).