Question

1. Multi-level page tables. Assume a virtual address machine with a 32 bit address. Assume the address is divided into 4 parts a,b,c,d with the first three parts used to index into a three-level page table, and the fourth is used to index into the location on the page. Assume the values for a,b,c,d are 4,6,6,16 respectively resulting in a 64 KB sized page. What is the total size in bytes of the page tables for the smallest program, which is a program containing a single page of text and heap, starting at location 0, and a separate page for the stack, starting at location 0xFFFFFFFF and running downwards? Assume all page table entries are 4 bytes each.

Answer 1

To calculate the total size of the page tables for a 32-bit virtual address space and a smallest program occupying two pages, we consider only the necessary page table entries. With 4 bytes per entry and part sizes of 4, 6, 6, 16 bits, the total size is 1028 bytes for the first-level, second-level, and third-level tables.

Step-by-step explanation:

To calculate the total size of the page tables for the smallest program in a virtual address space using multi-level page tables, we must consider the virtual address split into four parts: a, b, c, d, with lengths 4, 6, 6, 16 bits respectively. Since each entry is 4 bytes and we are dealing with a 64 KB page size, only two pages are needed: one for the text and heap and another for the stack. As this is the smallest program, we need to only account for the page tables that would point to these pages.

Since 'a' is 4 bits, the first level table will have 2^4 entries. However, we only need one entry for the text/heap and one possible entry for the stack. Considering the stack starts at the the top of the virtual memory space, which means it will require entries in the first-level and second-level page table to point to the third, but only the last entry in each table will be used. We can conclude that:

• 
  
• First-level table size: 2^4 * 4 bytes (but only one entry is used)
• 
  
• Second-level table size: 2^6 * 4 bytes associated with the first-level entry for the text/heap and similarly for stack, so two second-level tables.
• 
  
• Third-level table size: 2^6 * 4 bytes associated with the second-level entry for each. Hence, we have two third-level tables as well.

Total size = 1 * 4 bytes (first-level) + 2 * (2^6 * 4 bytes) (second-level) + 2 * (2^6 * 4 bytes) (third-level) = 4 bytes + 2 * (64 * 4 bytes) + 2 * (64 * 4 bytes) = 4 + 512 + 512 = 1028 bytes. Therefore, the total size in bytes of the page tables for the smallest program is 1028 bytes.

Answer 2

The total size in bytes of the page tables for the smallest program is 4MB.

Step-by-step explanation:

The virtual address space of the machine is 32 bits, which means that the maximum addressable memory is 2^32 bytes.

The page size is 64 KB, which means that each page contains 2^16 bytes. The address is divided into 4 parts a, b, c, and d, with the first three parts used to index into a three-level page table, and the fourth is used to index into the location on the page.

The values for a, b, c, and d are 4, 6, 6, and 16, respectively, resulting in a 64 KB sized page.

The smallest program contains a single page of text and heap, starting at location 0, and a separate page for the stack, starting at location 0xFFFFFFFF and running downwards.

Therefore, the program requires two pages of memory. Each page requires three levels of page tables, and each page table entry is 4 bytes.

Therefore, the total size of the page tables for the smallest program is:

2 * 3 * (2^16 / 2^9) * 4 = 2^22 bytes = 4 MB