Simulate a random replacement policy by lipping a coin. For example, “heads” means to evict the first block in a set and “tails” means to evict the second block in a set. How many hits does this address sequence exhibit?

In this exercise, we will examine how replacement policies impact miss rate. Assume a 2-way set associative cache with 4 blocks. You may find it helpful to draw a table like those found on page 482 to solve the problems in this exercise, as demonstrated below on the address sequence "0, 1, 2, 3, 4."

Address of Memory Hit or Evicted Block Accessed Miss Block a. 0 1 2 3 4 b. Miss Miss Miss Miss Miss 0 0, 2, 4, 8, 10, 12, 14, 16, 0 1, 3, 5, 1, 3, 1, 3, 5, 3 Contents of Cache Blocks after Reference The following table shows address sequences. Set 0 Mem[0] Mem[0] Mem[0] Mem[0] Mem[4] Set 0 Mem[2] Mem[2] Mem[2] Address Sequence Set 1 Mem[1] Mem[1] Mem[1] Mem[1] Set 1 Mem[3] Mem[3]