World's most popular travel blog for travel bloggers.

# [Solved]: Can this question be solved without knowing the Page Table Entry?

, ,
Problem Detail:

I'm preparing for the exams and this question came up -

Consider a machine with $64MB$ physical memory and a $32$-bit virtual address space. If the page size is $4KB$, what is the approximate size of the page table?
(A) 16MB
(B) 8MB
(C) 2MB
(D) 24MB

The way I've solved it -
Physical Address Space = $64MB = 2^{26}B$
Virtual Address = $32$-bits, $\therefore$ Virtual Address Space = $2^{32}B$
Page Size = $4KB=2^{12}B$
Number of pages =$\,\Large\frac{2^{32}}{2^{12}}$$=2^{20} pages. Number of frames =\,\Large\frac{2^{26}}{2^{12}}$$=2^{14}$ frames.

$\therefore$ Page Table Size = $2^{20}\times 14\,bits \approx 2^{20}\times 16\,bits\approx 2^{20}\times 2B= 2MB.$

Some books claim the answer to be $8MB$ and I don't see why, but that confuses me.
Is this the correct way to solve it? Is the answer correct?

###### Asked By : Siddharth Thevaril

Your answer and calculation is correct, if we used a one-level page table.

However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like.

A two-level page table is probably a more likely implementation strategy. The first 9 bits of the virtual address will be used as an index into the first-level table; they yield the entry in the second level. The next 11 bits of the virtual address will be used as an index into the second-level table.

With this strategy, the size of the entire page table is $1+k$ pages, or $(1+k) \times 2^{12}$ bytes, where $k$ is the number of second-level table entries. The worst case is $k=2^9$, in which case the entire page table takes up approximately $2^9 \times 2^{12} = 2^{21}$ bytes, i.e., 2 MB. In other words, the worst case for a two-level page table is approximately the same as the size of a one-level page table. However, the best case is much less.

I don't know how the books got 8 KB, but that seems clearly wrong, absent further assumptions; that would only allow 4096 entries in the entire page table, which clearly isn't enough to maintain a virtual-to-physical mapping for all of virtual memory.