edited by
7,760 views
34 votes
34 votes

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.

edited by

2 Answers

Best answer
81 votes
81 votes

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.
edited by
8 votes
8 votes

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$

Related questions

38 votes
38 votes
2 answers
1
Kathleen asked Oct 9, 2014
9,810 views
A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ bytes. The disk is used as follows:$$\begin{array}{|l|}\hline \te...