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

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).