Understanding Paging and Virtual Memory in Computer Architecture

5. A machine has a 32-bit address space and an 8-KB page. The page table is entirely in hardware, with one 32-bit word per entry. When a process starts, the page table is copied to the hardware from memory, at one word every 100 nsec. Lf each process runs for 100 msec (including the time to load the page table), what fraction of the CPU time is devoted to loading the page tables?

The page table contains 232 /213 entries, which is 524,288.  Loading the page table takes 52 msec. If a process gets 100 msec, this consists of 52 msec for loading the page table and 48 msec for running. Thus 52% of the time is spent loading page tables.

6. Suppose that a machine has 48-bit virtual addresses and 32-bit physical addresses. If pages are 4 KB, how many entries are in the page table if it has only a single-level? We need one entry for each page, or 236 = 64 x 1024 x 1024 x 1024 entries, since there are 36 = (48-12) bits in the page number field. 

7. Suppose that a machine has 38-bit virtual addresses and 32-bit physical addresses.
(a) What is the main advantage of a multilevel page table over a single-level one?
(b) With a two-level page table, 16-KB pages, and 4-byte entries, how many bits should be allocated for the top-level page table field and how many for the next level page table field? 

(a) A multilevel page table reduces the number of actual pages of the page table that need to be in memory because of its hierarchical structure. In fact, in a program with lots of instruction and data locality, we only need the top-level page table (one page), one instruction page and one data page. 

(b) The offset field requires 14 bits to address 16 KB. That leaves 24 bits for the page fields. Since each entry is 4 bytes, one page can hold 212 page table entries and therefore requires 12 bits to index one page. So, allocating 12 bits for each of the page fields will address all 238 bytes. 

8. A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset. How large are the pages and how many are there in the address space?

Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This yields a 4-KB page. Twenty bits for the virtual page implies 220 pages. 

9.  Suppose that a 32-bit virtual address is broken up into four fields, a, b, c, and d. The first three are used for a three-level page table system. The fourth field, d, is the offset. Does the number of pages depend on the sizes of all four fields? If not, which ones matter and which ones do not? 

The number of pages depends on the total number of bits in a, b, and c combined. How they are split among the fields does not matter.

10. A computer has 32-bit virtual addresses and 4-KB pages. The program and data together fit in the lowest page (0-4095). The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?

For a one-level page table, there are 232 /212 or 1M pages needed. Thus, the page table must have 1M entries. For two-level paging, the main page table has 1K entries, each of which points to a second page table. Only two of these are used. Thus, in total only three-page table entries are needed, one in the top-level table and one in each of the lower-level tables

11. A computer whose processes have 1024 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to reduce the mean overhead to 2 nsec?

The effective instruction time is 1h +5(1-h), where h is the hit rate. If we equate this formula with 2 and solve for h, we find that h must be at least 0.75. [Note: You will need to explain a bit more]. 

12. The TLB on the VAX does not contain an R bit, Why?
The R bit is never needed in the TLB. The mere presence of a page there means the page has been referenced; otherwise it would not be there. Thus, the bit is completely redundant. When the entry is written back to memory, however, the R bit in the memory page table is set.