The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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}$
asked in Operating System by Veteran (105k points)
edited by | 4.9k views

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 -

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




3 Answers

+36 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
answered by Veteran (362k points)
edited by
What would be the change if the memory were nibble addressable ?

@pc see this video.

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??

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


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.. :-)


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


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


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

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?
@Tuhin.I did not get the point.Even for second level second table has only one arrow.It should have two.
@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.
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?
There could be variable partition used in main memory

0x00400000 can be pointed by inner page table.
@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.

@Arjun Sir,

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

+10 votes


answered by Active (2k points)
Is this correct solution or the cancelled ?
How u figured out what is page size??
–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 

answered by (39 points)
edited by

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 .

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,516 questions
48,528 answers
63,381 users