# Can this question be solved without knowing the Page Table Entry?

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?

• Did you mean "claim the answer to be 8 MB"? (8KB was not one of the provided answer choices.) – Paul A. Clayton Jan 23 '15 at 2:57

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.

• Since 8KB was not a possible answer (multiple choice question), the O.P. presumably meant 8MB (really 8 MiB ☺). Since the PTE would typically include validity, permissions, and other metadata (more than 2 bits total), each PTE might be 32 bits. (32-bit PTEs also allow memory expansion without changes to the PTE format.) With 32-bit PTEs, the worst case would be 4+ MiB, but that is not one of the (multiple choice) answers. – Paul A. Clayton Jan 23 '15 at 2:56
• @PaulA.Clayton, yup, good points. I guess we can't know without more information, and ultimately, this may not be an answerable question (please guess why this answer that I got from an unnamed source with no justification might be right). – D.W. Jan 23 '15 at 4:15
• @D.W. How to calculate '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.'? – kauray May 15 '17 at 15:47

obvious it can be solved. u can calculate the size of page table entry easily.

size of page table entry = No. of bits used for frame number(convert it into byte), here bits in frame no. is 14 bits so it is approximately equal to 2 byte. so size of each entry of page table be 2B.