edited by
23,634 views
83 votes
83 votes

A processor uses $\text{2-level}$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most significant bits of the virtual address are used as index into the first level page table while the next $10$ bits are used as index into the second level page table. The $12$ least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are $4$ bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of $\text{96%}$. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of $\text{90%}$. Main memory access time is $10$ ns, cache access time is $1$ ns, and TLB access time is also $1$ ns.

Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address $0x00000000$, two contiguous data pages starting at virtual address $0x00400000$, and a stack page starting at virtual address $0xFFFFF000$. The amount of memory required for storing the page tables of this process is

  1. $\text{8 KB}$
  2. $\text{12 KB}$
  3. $\text{16 KB}$
  4. $\text{20 KB}$
edited by

6 Answers

Best answer
100 votes
100 votes

First level page table is addressed using $10$ bits and hence contains $2^{10}$ entries. Each entry is $4$ bytes and hence this table requires $4$ KB. Now, the process uses only $3$ unique entries from this $1024$ possible entries (two code pages starting from $0x00000000$ and two data pages starting from $0x00400000$ have same first $10$ bits). Hence, there are only $3$ second level page tables. Each of these second level page tables are also addressed using $10$ bits and hence of size $4$ KB. So,

total page table size of the process 
= 4 KB + 3 * 4 KB
= 16 KB

Correct Answer: $C$

edited by
18 votes
18 votes

IN ABOVE IMAGE T1 IS TABLE1 AND T2 IS TABLE2

18 votes
18 votes
Breakup of given addresses into bit form:-
$32$ bits are broken up as $10 bits (L2) | 10 bits (L1) | 12bits (offset)$

first code page:
$0x00000000 = 0000 0000 00 | 00 0000 0000 | 0000 0000 0000$

so next code page will start from
$0x00001000 = 0000 0000 00 | 00 0000 0001 | 0000 0000 0000$

first data page:
$0x00400000 = 0000 0000 01 | 00 0000 0000 | 0000 0000 0000$

so next data page will start from
$0x00401000 = 0000 0000 01 | 00 0000 0001 | 0000 0000 0000$

only one stack page:
$0xFFFFF000 = 1111 1111 11 | 11 1111 1111 | 0000 0000 0000$

Now, for second level page table, we will just require 1 Page which will contain following 3 distinct entries i.e. $0000 0000 00$, $0000 0000 01$, $1111 1111 11$.
Now, for each of these distinct entries, we will have $1$ page each in Level-1.

Hence, we will have in total $4$ pages and page size = $2^{12} = 4KB$.
Therefore, Memory required to store page table = $4*4KB = 16KB$.
16 votes
16 votes

This problem demonstrates a very important concept of how multilevel paging helps us to save page table size in the memory. The virtual address space generally contains a lot of empty pages. However, if we have a single page table, it requires us to store the page table entries for the empty pages us well. This can be avoided in multilevel paging.

The virtual address split is given as follows:

We can infer the following from this split :

  1. In level 1, there are $2^{10}$ page tables each having $2^{10}$ page table entries.
  2. In level 2, there is 1 page table having $2^{10}$ page table entries.

Now, it is given that we need to store 5 pages in the physical memory. This means that there will be only 5 useful entries (containing frame number for these 5 pages) in the level 1 page tables. Therefore, in the level 1, will keep only those page tables who have these 5 entries. The rest page tables, have all their entries invalid and need not be stored (their vacancy can be indicated by an invalid bit in outer page). This is how multilevel paging helps us to save the page table size.

Firstly, will find out where the entries corresponding to the code pages are in the level 1 page tables. The code pages begins at address 0 and are two contiguous pages. The entry for these will be the first two entries in the first page table among the level 1 page tables. Since, it has $2^{10}$ entries, the rest will be invalid but we have to store this page table. This is show in the diagram below.

Now, we need to figure out the page table having the entries for data pages. We can achieve this by finding where the starting address of first page pointed by the first entry in second page table in level 1. This can be compared to the given starting address to figure out whether the entries are in page table 1 or in some page table below. We have skipped $2^{10}$ entries of the first page table in this level. This means we have skipped $2^{10}$ pages, i.e $2^{10} * 2^{12} = 2^{22} B$ which is $0x00400000$. Therefore, the page table entries for data pages lie in the second page table of level 1. This is show in the diagram below. 

The stack page is clearly pretty below and hence will require some other page table below the first two page tables in level 1 (precisely it is the last page and will require the last page table in this level). We require 3 page tables in the level 1. The outermost page table must also be stored completely. Therefore, in total we require 4 page tables. (3 in level 1 and 1 in level 2).

Also, all the page tables have the same size, i.e. $2^{10} entries * {4}\;Bytes =  4KB$

Therefore, the amount of memory required for storing the page tables of this process is

$4\;page tables * 4KB = 16KB$

edited by
Answer:

Related questions

55 votes
55 votes
7 answers
3
go_editor asked Apr 24, 2016
14,672 views
Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.$$\begin{ar...