retagged by
7,697 views
6 votes
6 votes
A virtual memory system is able to support virtual address space of 256 GB. An entry
in the page table is 4 bytes long.
(i) Calculate the minimum page size required for a three-level paging scheme.
(ii) Draw a diagram indicating how the bits of a virtual address will be interpreted by
the address translation mechanism. Indicate which bits (and how many) are used to
index the page tables at each level, and which bits form the page offset for the case
above.
retagged by

4 Answers

Best answer
8 votes
8 votes

Let size of a page be  2P bytes - requires P bits for addressing.
Page Table Entry Size (PTES) = 4 Byte
Logical Address Space = 256 GB = 238B

Size of page table = (LAS/page size)*PTES

Size of 1st level page table = (238/2​​P)*4
Size of 2nd level page table = (238/2​​2P)*42
Size of 3rd level page table = (238/2​​3P)*43

Size of 3rd level page table should occupy in one page.

(238/2​​3P)*43 <= 2P
244 <= 24P
P >= 11 bit

Size of page = 2=211 B = 2KB

selected by
1 votes
1 votes

Given : VAS = 38 bits, 

Let page size consists of ‘d’ bits.

Here we can assume that each page table MUST fit into a frame as told by Bikram Sir, it implies that irrespective of which level’s page table we are referring to, the page table size must get fit into a frame. We will consider the best case which is we must remove internal fragmentation which is caused by paging, so we take page table size = frame size rather than page table size <= frame size. As we know that frame size = page size (by default). So, by transitivity page table size = page size.

Here, we are asked to use 3 level paging. So, considering the outer level page table, the Size of the outer page table = frame size = page size, where page size = 2^d. Ultimately, outer page table = 2^d bytes. 

Size of outer page table = number of pages x size of page entry, computing which we get 

The number of pages in the outer table = 2^(d – 2).

Now, considering the 2nd level page table, the Size of the 2nd page table = frame size = page size, where page size = 2^d. Ultimately, 2nd page table = 2^d bytes. 

Size of 2nd page table = number of pages x size of page entry, computing which we get 

The number of pages in the 2nd table = 2^(d – 2).

Further moving on to the inner level page table, its size too would be considered equivalent to 2^d bytes because each page table MUST fit into a frame. So, the inner page table = 2^d Bytes.

Size of inner page table = number of pages x size of page entry, computing which we get 

Number of pages in inner table = 2^(d – 2).

Summing up, we get the total size of 3 level paging as 2^(d-2) x 2^(d-2) x 2^(d-2) = 2^(3d – 6) number of pages, consider this is as equation 1.

The total number of pages in the page table :

Size of VAS/ page size = 2^38/2^d = 2^(38 – d), consider this is as equation 2

On comparing the powers of equation 1 and equation 2

3d – 6 = 38 – d

4d = 44

d = 11 bits.

So, page size = 11 bits, which is equal to 2 KB.

Hope it helps.

0 votes
0 votes

Virtual address space = 256GB ; in other words , size of process = 256 GB = 2* 2^ 30 = 2^38 bytes .

Page table Entry is 4 bytes which mean 2^5 bits 

Now since they said 3 level scheme , its a multilvel paging 

Then the  page Table size of ( outermost level) <= page size ,.........................equation 0 

Let page size be p ,

We know that Page table size = No of page * Page table entry .....................equation 1 

No of pages = size of process / page size = 2^38/ p.......equation 2 

put value of equation 2 in equation 1 

then Page table size =(2^38/ p )* 2^5 ...............equation 4 

put value of equation 4 n equation 0

(2^38/ p )* 2^5 <=p 

2^38 * 2 ^5 = p^2

2^43 = P^2

i wont get proper bit for this .!!

Where i am wrong ?

reshown by
0 votes
0 votes
Sir according to me it should be like

2^38 = 2^(2x)*4 M

Means every table is paged so total 18 bits is used for addressing a page table which can be divided into 6 bit each
Answer:

Related questions

0 votes
0 votes
1 answer
3
Markzuck asked Dec 22, 2018
1,326 views
for memory overhead in Multi level paging, for innermost table only 1 page size shall be counted na? and NOT the complete page table size?please explain the concept, than...
0 votes
0 votes
1 answer
4