in Operating System edited by
18,168 views
74 votes
74 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}$
in Operating System edited by
18.2k views

4 Comments

https://www.youtube.com/watch?v=tP7LYbFrk10 refer this and related videos on youtube 

search → Udacity high performance computer architecture 

part 4 is recommended for you (@)

3
3

@Mohitdas

you made my day.

video is easy to understand.

Looking like just made for this question only.

0
0
0
0

5 Answers

91 votes
91 votes
Best answer

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
by

4 Comments

@jlimbasiya

Yes inner level page tables are loaded as per the requirement , if there is reference from outer level page table.

Thus the amount of memory needed for the page table is not dictated by the size of the address space, but by the amount of memory that the process is using.

2
2
This link should be considered as the best answer!
1
1
Just to add one thing:

In the second-level page table, there will be 3 blocks useful.

1st block will contain the “code” and every block has $2^{10}$ entries. So maximum this block can point  $2^{10}$  pages. So, the address will start from 0x 0000 0000 to 003F FFFF.

2nd block will contain the “data” and every block has $2^{10}$ entries. So maximum this block can point  $2^{10}$  pages. So, the address will start from 0x 0040 0000 to 007F FFFF.

Why I mentioned these two blocks bcz after 003F FFFF , 0040 0000 is starting. Differ by 1.Therefore in exam just cross verify once. It might happen that code and data can be pointed by a single chunk.
0
0
18 votes
18 votes

IN ABOVE IMAGE T1 IS TABLE1 AND T2 IS TABLE2

4 Comments

Is this correct solution or the cancelled ?
0
0
How u figured out what is page size??
0
0
"The 12 least significant bits of the virtual address are used as offset within the page."
given in ques.
0
0
I think this and ans by gupta731 along with arjun sir’s ans r basically saying the same thing. Suppose the page entry size wasnt given in the question then how would we have calculated it? We would have taken a page table size to be equal to one page as we only use multilevel pging if the inner page table gets too big for one page.

One page size given is $2^{12} B$ (Cause offset is given as $12$ bits) = $4 KB$

And each page table (whether inner or outer) has $2^{10}$ entries.

Hence even without the entry size given we will get the entry size = $\frac{PageSize}{NoOfEntriesPerPage}$=  $\frac{4 KB}{2^{10}}$= $4B$

And as is explained by the answers we need $4$ such pages. Hence total required size for pg tables = $4*4$= $16KB$
0
0
14 votes
14 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$.
5 votes
5 votes

.

PO : Page Offset

PTi : Inner Page Table

PTo: Outer Page Table

 

 

 

 

 

 

Answer:

Related questions