# How many pages does the page table require?

I have found this exercise on the Internet but I´m having problems with sections 4 and 5, because I don´t understand where do the solutions appear from.

Example: Mapping VAs to PAs

Suppose
- Virtual memory of 2^32 bytes
- Physical memory of 2^24 bytes
- Page size is 2^10 (1K) bytes

1. How many pages can be stored in physical memory at once?

2^(24-10) = 2^14

2. How many entries are ther in the page table?

2^22

3. How many bits are necessary per entry in the page table? (Assume each entry has PPN, residentbit, dirty bit)

16

4. How many pages does the table require?

2^23 bytes = 2^13 pages

5. What is the largest fraction of VM that might be resident?

1/(2^8)

6. A portion of the page table is given to the left. What is the physical address for virtual address 0x1804?

VPN = 6 --> PPN = 2 --> PA = 0x804

$$\begin{array}{c|c|c|} \text{VPN} & \text{D} & \text{R} & \text{PPN} \\ \hline \text{0} & 0 & 0 & 7 \\ \hline \text{1} & 1 & 1 & 9 \\ \hline \text{2} & 1 & 0 & 0 \\ \hline \text{3} & 0 & 0 & 5 \\ \hline \text{4} & 1 & 0 & 5 \\ \hline \text{5} & 0 & 0 & 3 \\ \hline \text{6} & 1 & 1 & 2 \\ \hline \text{7} & 1 & 0 & 4 \\ \hline \text{8} & 1 & 0 & 1 \\ \hline \text{...} & ... & ... & ... \\ \hline \end{array}$$

Could you help me with this two exercises?

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – adrianN Jun 20 '16 at 15:04
• There are many numbers here (at least 9 of them). Please ask a specific question. – Martin Kochanski Jun 21 '16 at 1:07

Here some of the answers seem incorrect to me.

3] Number of bits required for a page table entry.

Page table Entry=> R==D==PPN

R ==>1bit

D ==>1bit

Number of frames =2^14 ==>14 bits

Number of bits in a page table entry= 1+1+14=16

4] Number of pages required by page table

As the page table itself will be stored in main memory it will require some pages.

Amount of memory required for page table =size of an entry * Number of entries

                                     =16 bits * 2^22

=67108864 bits =8388608 bytes

=8192= 2^13 pages (: 1 page=1024 bytes)


5] What is the largest fraction of virtual memory resident:

i.e. the amount of virtual memory that can reside in RAM.

i.e Total Physical memory / Total Virtual memory

                                     =2^24 /2^32

=1 / 2^8

=0.39% of virtual memory can be in RAM ant an instant of time.


Please go through Virtual memory from Charles C. Lin.

I hope this may help....

• After rethinking section 3 a while I think it is correct, since we can use the virtual page number as an index (it doesn´t necessarily have to be included in the page table). So instead of 38 bits I would use the first result of 16 bits both in section 3 and 4. And now I understand section 5! – chick3n0x07CC Jun 21 '16 at 11:53
• Bingo!!! I have updated my post accordingly.Thanks... – Maharaj Jun 21 '16 at 12:07