2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Did you mean "claim the answer to be 8 MB"? (8KB was not one of the provided answer choices.) $\endgroup$
    – user4577
    Commented Jan 23, 2015 at 2:57

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – user4577
    Commented Jan 23, 2015 at 2:56
  • 1
    $\begingroup$ @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). $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2015 at 4:15
  • $\begingroup$ @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.'? $\endgroup$
    – kauray
    Commented May 15, 2017 at 15:47
-3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.