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. How many pages are in the virtual address space?
2. What is the maximum size of addressable physical memory in this system?
3. If the average process size is 8GB, would you use a one-level, two-level, or three-level page table? Why?
4. Compute the average size of a page table in part c above

Answer 1

(a) How many pages are in the virtual address space?

Normally a 36-bit Virtual Address Space could address

2³⁶ Bytes

The Page size given is 8KB. i.e., 1 KB = 1000 bytes which is equivalent to 2¹⁰ bytes

Then for 8KB = 2¹ x 2¹ x 2¹ x 2¹⁰ = 2¹³ Bytes

The number of pages in the Virtual Address Space for the Page size of 8KB = 2³⁶ / 2¹³ = 2²³

(b) What is the maximum size of addressable physical memory in this system?

For 4 bytes per Page Table Entry, the number of pages that can be referred to is 2³² pages. As each page size is now 2¹³ Bytes, the maximum size of addressable physical memory in this system is 2³² x 2¹³ = 2⁴⁵ Bytes.

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

(d) Compute the average size of a page table in part c above

Average Process Size = 8GB, and we are having 2³³ pages.

One-level page table:

Available Virtual Address Space = 2²³ pages.

We are using 4B for each Page Table Entry.

Now the Page Table Size = 2²³ x 4 = 2²³ x 2²= 2²⁵. = 33.554432 MB

As it is not cost-effective, it cannot be considered. It is taking 1 in 242 times of its memory space.

Two-level page table:

Average Process Size = 2³³ pages with 8GB data. As the Page Size given is 2¹³ pages.

We can assume that the overall size of all the varying pages is 2³³ Bytes.

Accordingly, we now get 2³³ / 2¹³ = 2²⁰ Pages.

Here the address shall be partitioned into 12, 11, and 13.

It can be shown that the size of one low-level piece of the Page Table is 2¹¹. Hence, it is needed 2²⁰ / 2¹¹ = 2⁹

Accordingly, now the total size of the Page Table shall be given as

The total size of the page table is then:

Size of the External page table = 1x2¹²x2² added with Size of the Internal Page Table = 2⁹ x 2¹¹ x 2² , we could get the result as 2¹⁴ + 2²² which is roughly 4.210688 megabytes

Three-Level Page Table:

Here the address shall be partitioned into 8,8,7, and 13.

As above, it is needed 2²⁰ / 2⁷ = 2¹³.

It can be seen that the Two-level Page table would reference 2⁸ Three-level Page Table. Hence it is needed 2¹³/ 2⁸ = 2⁵ Two-level pages. Now the overall size of the Page Table is given as

for the External page table:

1 x 2⁸ x 2²

for the Two-level page table:

2⁵ x 2⁸ x 2²

for the Internal page table:

2¹³ x 2⁷ x 2²

which is roughly equivalent to 4 megabytes.

From the above calculations, Two-level and Three-level page table requires less space than One-level Page table. As our Virtual address space is small, and based on the cost-effective solution, it's better to choose the Two-level Page Table.