Paging

Question

A computer system has a 36-bit virtual address space with a page size of 8K, and 4 bytes per page table entry.

1. If the average process size is 8GB, would you use a one-level, two-level, or three-level page table? Why?

Answer 1

36 bit virtual address space. But each process uses on average 8GB only.

Consider 1 level paging:

Size of page table = no. of PTE entries * PTE size

= Address Space * PTE size/Page size

$=\frac{2^{36} \times 4B}{8\times 2^{10}} = 2^{25} B= 32 MB$.

So, size of pagetable is 32 MB for a process using on average 8GB. This is $\frac{1}{256}$ of the total memory usage.

Consider 2 level paging:

We can do this is many ways, but we try to divide the index bits equally among all levels and also give extra bit if any to higher levels to give more chance of lower level pagetable size to be same as a page size. So, out of 36 bits, we have 13 offset bits. Remaining 23 bits can be divided to 12 bits for first level and 11 for second. Now, size of first level page table

$=2^{12} \times 4B= 16 KB$

We have 11 bits for indexing to second level page table. So, size of each second level page table $=2^{11} \times 4B = 8 KB$ - this is exactly the page size

Now, we need to see how many second level page tables will be in memory (first level page table is always in memory). To address 8GB, we need $2^{20}$ pages. And each second level page table addresses $2^{11}$ pages and thus we require $\frac{2^{20}}{2^{11}} = 512$ second level page tables. So, total memory requirement

$= 16KB + 8KB \times 512 = 16KB + 4 MB \approx 4MB$

Consider 3 level paging:

Now we have 23 bits to be divided among the 3 levels and this can be done as 8 -- 8 -- 7. So, size of first level page table $= 2^8 \times 4B = 1KB$.

Similarly size of second level page table = 1KB.

Size of third level page table $= 2^7 \times 4B = 512 B$

To address $2^{20}$ pages, sum of the no. of entries in third level page tables $=2^{20}$. 
Since each third level page table addresses 128 pages, we need no. of third level page tables $= \frac{2^{20}}{2^7} = 8K$

Now, we need a second level PTE for each of them which means a total of $8K$ entries. Each second level page table has 256 entries, meaning a total of $\frac{2^{13}}{2^8} = 32$ second level page tables.

So, total memory taken by page tables $= 1KB + 32 \times 1KB + 8K \times 0.5 KB \approx 4MB$

So, 2 level page table is taking same space as 3 level page table and we really do not need a 3 level implementation.

PS: Suppose the average memory usage per process is $64GB$, then what would be the answer?

Comments

Thank you sir thanks a lot. You just saved my day. :)

---

@Arjun sir

but we we divide it like 10|13|13 we get approximate page table size as 1 MB. Why cant we do it like that?

---

if we divide V.A as  6 6 11 in three level paging we will get page table overhead(size) as 1 MB

so three level paging would be better. Am i correct here ?

Answer 2

Let us calculate 1st level page table size..

We know page table size  =  (Logical address space / Page size) * Page table entry size

But we have page table meant for a process and a process size = 8 GB whereas the virtual address space = 2³⁶ B  = 64 GB..So if we consider the process size for which we make page table, then we have :

So 1 st level page table size  =  (2³³ / 2¹³) * 2² bytes  [Assuming byte addressable]

                                           =  2²² bytes

As this is larger than 1 page size , so we go to 2nd level paging..

So 2nd level page table size  = (2²² / 2¹³) * 2² bytes

                                           = 2¹¹  bytes which is less than 2¹³ bytes which is the page size.So we stop here and do not do further level of paging.This is the goal of multilevel paging..

So no of paging levels required  = 2 ..Hence 2 level paging is used..

Comments

See the size of page table used in 2 level =4KB

size of page table size in 3 rd level also 4 KB

that is why we not use 3rd level.

It is mentioned Arjun sir in chat,see once.

but I cannot understand how in 3rd level it is dividing like 7,8,8

Could u understand this portion?

---

@srestha just try another split.

---

in 2 level paging, how can outermost page table be 16KB whereas page size given is 8KB because outermost page table has to fit inside one page?? can someone resolve this doubt of mine. :(