$(5\mathrm{.}20\mathrm{.}20)$ In this exercise, we will examine how replacement policies affect miss rate. Assume a two$-$way set associative cache with four one$-$word blocks. Consider the following word address sequence: $0,1,2,3,4,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0.$

Consider the following address sequence: $0,2,4,8,10,12,14,16,0.$

Assuming an LRU replacement policy, which accesses are hits?

Assuming an MRU $($most recently used$)$ replacement policy, which accesses are hits?

Simulate a random replacement policy by flipping 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?

Describe an optimal replacement policy for this sequence. Which accesses are hits using this policy?

Describe why it is difficult to implement a cache replacement policy that is optimal for all address sequences.

Assume you could make a decision upon each memory reference whether or not you want the requested address to be cached. What impact could this have on miss rate?