1. (15 points) Page Allocation and Replacement.

As shown below, the optimal algorithm would result in only 9 page faults for a string of page references (7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1) for a process with 3 physical frames.

For a different string of page references (4, 5, 4, 3, 7, 4, 6, 7, 5, 4, 7, 4, 6, 7), draw a similar figure to show the frame allocation and replacement under the following replacement policies:

a. FIFO (first-in-first-out)

b. LRU (least recently used)

c. Optimal (assume the page reference string continues with 4, 3, 7, 4, 5)

d. List the total number of page faults and the miss rate for each policy.

2. (15 points) Segment Table, Hierarchical Table, Hash page table with logical addresses.

A two-level page table is created to enable paging for a 4GB logical address space. In this scheme, the page size is 4 KB, and each page table entry has a size of 4 bytes. The root page table can fit in a single 4 KB page.

a. How much memory space is needed in total for this two-level page table?

b. Assume you want to implement a hashed page table for the same addressing scheme, using a hash function that maps the 20-bit page number into a 12-bit hash value. The table entry has a size of 8 bytes, containing the page number, the frame number, and a chain pointer. How much memory space does the hashed page table take? Compared to the two-level page table, how much memory space has been saved with the hashed page table? Hint: a 12-bit hash value means that the hashed page table has a total of 212 entries.

c. Suppose that the page size and the size of page table entries stay the same, how many levels of page tables would be required to map a 64-bit address space, if the top-level page table still needs to fit into a single page?

reference string page frames