Q1. Assume that a virtual address is 24 bits: 14 bits for the virtual page number, and 10 bits for the offset. Also assume that each page table entry is 4 bytes in size.

If we use simple paging, what is the size of a page table, in bytes? (Make sure you get this right -- the following problems depend on it.) _____________

If we break the page table into page-sized chunks, how many chunks are there in the entire page table? ____________

If only 25% of the page-sized chunks of the page table are used, what is the total size, in bytes, of all the chunks that are used? _____________

Assume we move to multi-level paging, and split the VPN part of the virtual address into two parts of 6 bits and 8 bits, where the page directory index is the 6 bit part. Also assume that each page directory entry is 4 bytes in size. What is the total size of the page directory, in bytes? ____________

Following on from questions a-d above, how much memory is saved if we move from simple paging to multi-level paging? Express your answer as a decimal number between 0 and 1 that equals the number of bytes needed with multi-level paging divided by the number of bytes needed with simple paging. ___________.

Q2.

Using the LRU replacement policy, fill in the blanks in the table below. The cache size is 3.

access hit? evict resulting cache

0 no - 0

1 no - 0,1

1 yes - 0,1

2 no - 0,1,2

0 yes - 1,2,0

3 no 1 2,0,3

1 ____ ____ ____

0 ____ ____ ____

2 ____ ____ ____

Using the FIFO replacement policy, fill in the blanks in the table below. The cache size is 3.

access hit? evict resulting cache

0 no - 0

1 no - 0,1

1 yes - 0,1

2 no - 0,1,2

0 yes - 0,1,2

3 no 0 1,2,3

1 ____ ____ ____

0 ____ ____ ____

2 ____ ____ ____