retagged by
28,149 views
61 votes
61 votes

Consider a three-level page table to translate a $39-$bit virtual address to a physical address as shown below:

The page size is $\text{4 KB} \;(1\text{KB}=2^{10}$ bytes$)$ and page table entry size at every level is $8$ bytes. A process $P$ is currently using $2\text{GB}\;(1 \text{GB}=2^{30}$ bytes$)$ virtual memory which is mapped to $2\text{GB}$ of physical memory. The minimum amount of memory required for the page table of $P$ across all levels is _________ $\text{KB}$.

retagged by

4 Answers

Best answer
86 votes
86 votes

Given :

  • Virtual address $\text{(VA)}= 39$ bits
  • Page size $= 4 \text{KB}$
  • Physical address $\text{(PA)} = 2 \text{GB}$
  • Page table entry size $\text{(PTE)} = 8 \text{B}$
  • Three level pages tables with address division $(9,9,9,12)$

Three level pages tables with address division $(9,9,9,12)$  means:

  • $9$ most significant bits for indexing into the level-1(outer level),
  • $9$ bits for the level-2 index,
  • $9$ bits for the level-3 index, and
  • $12$ bits for the offset within a page.

The entries of the level-1 page table are pointers to a level-$2$ page table, the entries of the level-$2$ page table are pointers to a level-$3$ page table, and the entries of the level-$3$ page table are PTEs that contain actual frame number where our desired word resides.

$9$ bits for a level means $2^9$ entries in one-page table of that level.

For our process $P :$

$P$ is using $2\;\text{GB}$ of its VM. The rest of its VM is unused.

$2\;\text{GB}$  VM will have $2\;\text{GB} / 4\;\text{KB} = 2^{19} \;\text{Pages}.$

But level $3$ page table has only $2^9$ entries. So, one-page table of level $3$ can point to $2^9$ pages of VM only, So, we need $2^{10}$ level-$3$ page tables of process $P.$

So, at level-$3,$ we have $2^{10}$ page tables, So, we need $2^{10}$ entries in Level-$2$ But level $2$ page table has only $2^9$ entries, so, one-page table of level $2$ can only point to $2^9$ page tables of level-$3$, So, we need $2$ level-$2$ page tables.

So, we need $1$ Level-$1$ page table to point to level-$2$ page tables.

So, for process $P,$ we need only $1$ Level-$1$  page table, $2$  level-$2$ page tables, and $2^{10}$ level-$3$ page tables.

Note that All the page tables, at every level, have same size which is $2^{9} \times 8\;\text{B} = 2^{12}\;\text{B} = 4\;\text{KB}$

$($Because every page table at every level has $2^9$ entries and Page table entry size at every level is $8\;\text{B})$

So, in total, we need $1+2+2^{10}$ page tables $(1$ Level-$1, 2$ Level-$2, 2^{10} $ level-$3),$ and each page table size is $4\;\text{KB}$

So, total page tables size $= 1027 \times 4\;\text{KB} =  4108\;\text{KB}$

So, the answer is $4108.$



NOTE :

In this question, in place of Multilevel paging, If we had used Single Level Page table (also known as Flat level page table OR linear page table), then size of page table would be $1\;\text{GB}.$

Single Level Page Table :

Single-Level Page Tables are single linear array of page-table entries (PTEs). Each PTE contains information about the page, such as its physical page number (“frame” number) as well as status bits, such as whether or not the page is valid, and other bits. the $ith$ entry in the array gives the frame number in which the $ith$ page is stored.

  • Virtual address(VA) $= 39$ bits
  • Page size  $= 4\;\text{KB}$

So, number of pages in Virtual address space (VAS) of each process $ =2^{39}B / 4KB = 2^{27} $

So, we need $2^{27} $ entries in the page table. Each PTE size $= 8\;\text{B}$

So, size of page table for the process $= 2^{27}  \times 8\;\text{B} = 1\;\text{GB}$

NOTE that Single level paging CANNOT take advantage of the unused space by the process. The single level page table needs one entry per page. Furthermore, since the process has a very sparse virtual address space, so, the vast majority of these PTEs would simply be marked invalid. BUT space taken by single level page table will be 1GB only. It only depends on the virtual address space, NOT depend on the used memory of process. 

A Common Mistake that students make :

In this question, if in place of Multilevel paging, If we had used Single Level Page table, then what would be size of page table ??

The mistake is that some students will consider $2\;\text{GB}$ memory that the process is using, and will get answer $(2\;\text{GB} / 4\;\text{KB}) \times 8\;\text{B} = 4\;\text{MB}$ which is wrong. 

Remember that the CORE reason why we use multilevel paging in place of single level paging is that we want to reduce size of page table by taking advantage of unused space of process and making most entries in the outer level page table as invalid entries. 

edited by
30 votes
30 votes

Given that Process P is using 2GB of physical memory and page size is $2^{12}$ Bytes,Number of pages$=2^{31}/2^{12}=2^{19}$

Each page need a entry in 3rd level and there are $2^9$ entries per page table in 3rd level.

So we need $2^{19}/2^9 =2^{10}$ page tables in 3rd level.

This implies there are $2^{10}$ entries in 2nd level and there are 2^9 entries per page table in 2nd level.

So we need  $2^{10}/2^9=2$ page tables in 2nd level.

Now we have 2 entries in 1st level and hence,we need only 1 page table in 1st level.

So on total we need ,

$2^{10} +2 +1=1027$ page tables each with 2^9 entries of size 8 bytes.

Total size of page tables $=1027*2^9*8$ Bytes

$=1027*2^{12}$ Bytes

$=1027*4$ KB

$=4108$ KB.

edited by
5 votes
5 votes

....………………..…………………………….………………………….

2 votes
2 votes
Virtual Address consists of 39 bits, but a process P is using only 2GB of its virtual memory. For the amount of memory required for the page table of process to be minimum , the address range generated for the 2GB should be continuous in the Virtual address space, otherwise if the address sequence referenced is scattered then more memory would have been required.

Coming to data provided – Page size  = 4KB.

No. of entries required at 3rd level will be= 2GB/4KB = 2^19 entries

No. of pages required at 3rd level will be = 2^19/2^9 = 2 ^10Pages (One page can hold 2^9 entries as given in breakup of VA)
Similarly No. of pages required at 2nd level will be = 2 , as 1 page can hold 2^9 entries here too.

And at 1st level there will be 2 entries for mapping the entries of second level and this will require 1 Page.

Total Pages required = 1+2+ 1024 = 1027.

Total size in KB will be 1027 * 4 KB = 4108 KB.
Answer:

Related questions

25 votes
25 votes
6 answers
2
Arjun asked Feb 18, 2021
11,785 views
Let $S$ be a set of consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________
8 votes
8 votes
1 answer
3
Arjun asked Feb 18, 2021
6,467 views
Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \r...
24 votes
24 votes
3 answers
4