search
Log In
55 votes
12.2k views

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
12.2k views
0

Just one variation in the given question -->

Although it is given in the question that page table entry size is 4B. But assume that it is not given, then what will be page table entry size ?

PS: For hint check - https://gateoverflow.in/490/gate2008-67

0
In that case I can think of 1 page in page table 1 is pointing to 3 pages in page table two as entries are consecutive so I can assume that to utilize spatial locality of reference consecutive locations are loaded into same page making it 1+ 3= 4 pages in all. And offset bits are 12 that gives me 4 kb for each page. Hence 4 X 4kb makes it 16 kb.

 

Can I think like this while evaluating such questions? Or this is not correct approch if page table entry size is not given.
0
What would be the answer if had it been a 3-level paging ?

Then will 2nd level page tables be all possible count of it and only 3 page tables for 3rd level ?

 

@MiNiPanda

@Ahwan
0
Can anyone explain me the concept?

I stuck in the inner page and address locations!
0
Please recommend some good quality video lectures to understand this topic ( Paging, Multilevel paging) fully.

5 Answers

73 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
0
What would be the change if the memory were nibble addressable ?
64

@pc see this video.

0
Sir,I am confused that next or 2nd code page address will be 0x00000001 or 0x00001000 as first 20 bits will be taken page no. in virtual memory or physical memory. page size or 12 bits of lsb wont be changed.
What do you suggest??
2

@gateasp17
The last 12 bits are offset so addresses for pages are
For Code pages:
0x00000000 and 0x00001000 (Note: only 10 bits are for addressing 2nd level page table). So these 10 bits will be:

For code page 0x00000000 2nd level PT offset is  (00 0000 0000)2

For code page 0x00001000 2nd level PT offset is  (00 0000 0001)2

For Data pages
0x00400000 and 0x00401000

For data page 0x00400000 2nd level PT offset is  (00 0000 0000)2

For data page 0x00401000 2nd level PT offset is  (00 0000 0001)2

:)

0
Yaahh.... I got it THAT here for page size or frame size 12 bits (LSB). So remaining 32-12=20 bits will be assigned for no. Of pages that's why changes will be made to these 20 bits only, for contiguous pages of code data and stack..

Thanks.. :-)
37

..........................

Links from second level page tables are not pointers rather they represents coverage in the logical address space.

0

@Debashish Deka why there a red arrow from 3 block of first to the logical address space?Second level 1st page table should have only two enteries as it is used to point to two pages.What is thirst arrow representing?

0

Second level 1st page table should have only two enteries as it is used to point to two pages.What is thirst arrow representing?

Yes, it has two contiguous words within the same page,i.e the first page in logical address space but the 3rd arrow indicates last address that is covered by the 1st inner page table. It is shown just to indicate that the 1st inner page table cannot access page at address: 0x00400000

0
I've a doubt.

Is the sequence of Page no-frame no entry in Page table same as the sequence of pages stored in Main memory?
0
@Tuhin.I did not get the point.Even for second level second table has only one arrow.It should have two.
0
@Rahul, I told about the blue arrow from address 0x00400000. Regarding your query about 2 links or arrows from the 2nd inner page table, yes there should have been two arrows but I think it is not shown because of keeping clarity in the diagram.  The arrow from the last PTE of the 1st inner page table shows that it points to the starting location of the last page that the 1st inner page table can address, just for our understanding. Now you should have observed the green colored consecutive pages shown in logical address space. For each of these pages, inner page tables must have pointers to them.
0
If I want to figure out what will be page size based on given data?? How will I do that? Or can I simply say page size is nos of offset bits?

12 bits are used for offset hence page size is 2^12 , 4 kb?
0
There could be variable partition used in main memory

0x00400000 can be pointed by inner page table.
0
@Arjun Sir

Sir, you have considered full outer page table & partial inner page table(pages for which the second set of 10 most significant digit is changing) while calculating the memory required to stored the page table for the process.Can we load partial inner page table?

if we can load partial page tables then is it only the inner most tables that we can load partial or at any level considering an  'n' level paging.

Thanks
1
@Arjun Sir,

my doubt got cleared after referring the solved problem enclosed in ur expiation.

:)
0
Nice explanation
0

 Now, the process uses only 33 unique entries from this 10241024 possible entries (two code pages starting from 0x00000000 and two data pages starting from 0x00400000 have same first 1010 bits). 

explain this, please! 

0

@Arjun Sir and @dd  I am not getting, how the addresses are ranged from 0x00000000 to 0x00000FFF

Lightbox

0

@dd

@srestha

it is always necessary to load entire outer level page table.

and for inner level page table we load according to requirement.

Am I correct?

1

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

0
This link should be considered as the best answer!
16 votes

IN ABOVE IMAGE T1 IS TABLE1 AND T2 IS TABLE2

0
Is this correct solution or the cancelled ?
0
How u figured out what is page size??
0
"The 12 least significant bits of the virtual address are used as offset within the page."
given in ques.
2 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$.
1 vote

.

PO : Page Offset

PTi : Inner Page Table

PTo: Outer Page Table

 

 

 

 

 

 

ago
–3 votes

Since page offset is of size 12 bit and memory is byte addressable. So we can say that page size=2^12 Byte=4KB.

Now process needs 5 pages of page no.

0x 00000 and 0x 00001 for code,

0x 00400 and 0x 00401 for data, and

0x FFFFF for stack.

Now for mapping above pages in to frames we need one outer page table and two inner page tables(One  inner page table needed for mapping all these four pages

0x 00000, 0x 00001, 0x 00400 and 0x 00401, and another inner page needed for mapping 0x FFFFF).

So, total no of page table needed for above process is 3.

The amount of memory required for storing the page tables of this process is 3*4KB = 12KB 


edited by
8

0x 00000, 0x 00001 are in one inner page table and 0x 00400 and 0x 00401 in another inner page table,because their first 10 bits are different (4 is 0100 and so 01 is the part of ist 10 bits).So a total of 3 inner tables and 1 outer page table are required. so 4*4KB=16KB .

0
Hi navnit, can you plz explain me how inner and outer page tables can be decided??
0
@iqra islam

one for code one for stack one for data and  one for  the outer most 1 st level table
Answer:

Related questions

18 votes
6 answers
1
8.3k views
In a system with $\text{32 bit}$ virtual addresses and $\text{1 KB}$ page size, use of one-level page tables for virtual to physical address translation is not practical because of the large amount of internal fragmentation the large amount of external fragmentation the large memory overhead in maintaining page tables the large computation overhead in the translation process
asked Sep 16, 2014 in Operating System Kathleen 8.3k views
87 votes
12 answers
2
21.8k views
A processor uses $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 ... access a virtual address is approximately (to the nearest $0.5$ ns) $1.5$ ns $2$ ns $3$ ns $4$ ns
asked Sep 15, 2014 in Operating System gatecse 21.8k views
42 votes
5 answers
3
6.2k 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$ ... $Z, S$ initially $1$ $V(S)$ at $W, V(T)$ at $X, P(S)$ at $Y, P(T)$ at $Z, S$ and $T$ initially $1$
asked Apr 24, 2016 in Operating System jothee 6.2k views
21 votes
3 answers
4
3.5k 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. Process P: Process Q: while(1) { while(1) { W: Y: print '0'; print '1'; print '0'; print '1'; X: Z: } } Synchronization statements can be ... $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ initially $1$ , and $T$ initially $0$
asked Sep 17, 2014 in Operating System Kathleen 3.5k views
...