A) Design a virtual memory system that has the following characteristics:

1.1) A page size of 32K bytes

2.2) An address word of 72 bits

Given this system, what is the maximum number of disk access required to obtain any stored page? Justify your answer.

B) Describe how your system would handle addresses x and y where x-y = 2**53

C) How could you modify the system so that you had at most a total of two memory accesses to get to any page currently stored in memory

Assume that we use 16 byte page table entry. Note that a 8 byte page table entry will only allow us to address 2**64 bits of address space. Since 32K is 2**15, and 16 is 2**4, we have 2**11 or 2K entries per table. Each page gives us 2**15 of address space, our system of page tables and directories must supply us with 57 more bits of address space.

With 6 levels of page tables/page directories we can address 2*66 pages or 2**81 bits of address space.

Thus, if no page tables or page directories were in memory, we would have to access the disk 7 times to obtain the necessary data. (Of course, one would clearly want to store at least the outer level directory in memory).

B) Let the innermost level of page tables (bits 15:25 of the address) be called L1, the next levels of page tables and page directories and the corresponding address bits are:

• L2 bits 26:36
• L3 bits 37:47
• L4 bits 48:58
• L5 bits 59:69
• L6 bits 70:71

References to x and y are resolved using the same L5 and L6 page tables/directories. The two references use different entries in page table L4. The different entries in L4 point to different L3 tables, but in tables in levels L3, L2, L1 the entries associated with x and y occupy the same relative position in the tables. X and y also have the same page offset (although x and y are stored in different pages).

C) Inverted page table - use a hash table to map virtual address space to physical address space. Actually, this two reference business is a bit optimistic as it assumes no collisions in the hash table. On the other hand, in principal we could regenerate the hash table when a page is brought in, in order to ensure that the data could be located in a single memory access.