Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Storage 2 Exercise

Today's exercise is going to be a little different -- you can complete the exercises using a whiteboard and marker or pencil and paper or some other writing implement. You should record the answers to the problems so you can enter them on the survey that you fill out at the end of class.

Practice with different replacement policies

We're going to give you some practice simulating cache eviction policies. For the problems below, assume that the following is an ordered string of references to blocks in a cache.

   A B C A D C A F C F

Let's say that we have a cache with three slots.

1. What is the hit rate using the FIFO replacement policy? (Express hit rate as a fraction H/T.)

2. What three blocks are in the cache at the end of the simulation?

3. What is the hit rate using the LRU replacement policy?

4. What three blocks are in the cache at the end of the simulation?

5. What is the hit rate using the LFU replacement policy? (If two blocks have the same frequency and you need to evict one, evict the one that entered the cache last.)

6. What three blocks are in the cache at the end of the simulation?

7. If we increase the number of slots in our cache from three to four, do you think the hit rates will go up or down?

OK, let's try it! Let's say that we now have four slots.

8. What is the hit rate using FIFO?

9. What is the hit rate using LRU?

10. What is the hit rate using LFU?

11. In general, if you increase the number of slots, do you expect the hit rate to increase or decrease?

12. Do you think your answer to #11 is always the same?

Consider the following access string:

    1 2 3 4 1 2 5 1 2 3 4 5

Assume a 3-slot cache

13. What is the hit rate for FIFO?

14. What is the hit rate for LRU?

Now assume a 4-slot cache

15. What is the hit rate for FIFO?

16. What is the hit rate for LRU?

We are assuming you find these hit rates surprising! This is called Belady's anomaly and is worth a quick read.

The Ideal Replacement Policy

It turns out that our friend Belady was a very clever fellow. He figured out that if you were omniscient and knew the entire reference string in advance, there was a provably optimal algorithm you could use to select pages to evict from a cache. Spend some time and see if you can figure out what that algorithm is. If you cannot, read about it here.

Survey

Please complete the survey, including your answers to the questions above.