---

1. Cache Management

Replacement policy to minimize cache misses (maximize cache hits):

  when cache is full, replace the page that will be accessed furthest in the future.

Requires unrealistic knowledge of the future, but useful for comparisons.

Example, cache size 3, page access: 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1

6 hits, 5 misses, hit rate = 6/(6+5) = 54.5%

Excluding compulsory misses (first access): 6 hits, 1 miss, hit rate = 6/(6+1) = 85.7%

---

2. FIFO Policy

first-in, first-out

4 hits, 7 misses, hit rate = 4/(4+7) = 36.4%

Excluding compulsory misses: 4 hits, 3 miss, hit rate = 4/(4+3) = 57.1%

---

3. Random Policy

---

4. LRU Policy

consider frequency, recency --> Least-Frequently-Used (LFU), Least-Recently-Used (LRU)

6 hits, 5 misses, hit rate = 6/(6+5) = 54.5%

Excluding compulsory misses: 6 hits, 1 miss, hit rate = 6/(6+1) = 85.7%

Same hit rate as optimal for this example.

---

5. No-Locality Workload

each reference is to a random page

---

6. 80-20 Workload

80% of the references are made to 20% of the pages

---

7. Looping Sequential Workload

access pages 0, 1, ..., 49, 0, 1, ...

---

8. Approximating LRU

1-bit "reference bit" and clock algorithm: scan pages, if reference bit is 1, set to 0; else evict.

Other considerations: dirty vs. clean pages, demand paging vs. prefetching

---

9. Exercises

See the book for exercises using paging-policy.py

$ python ./paging-policy.py -m 6 -c -s 10

Access: 3  MISS FirstIn ->          [3] <- Lastin  Replaced:- [Hits:0 Misses:1]
Access: 2  MISS FirstIn ->       [3, 2] <- Lastin  Replaced:- [Hits:0 Misses:2]
Access: 3  HIT  FirstIn ->       [3, 2] <- Lastin  Replaced:- [Hits:1 Misses:2]
Access: 1  MISS FirstIn ->    [3, 2, 1] <- Lastin  Replaced:- [Hits:1 Misses:3]
Access: 4  MISS FirstIn ->    [2, 1, 4] <- Lastin  Replaced:3 [Hits:1 Misses:4]
Access: 4  HIT  FirstIn ->    [2, 1, 4] <- Lastin  Replaced:- [Hits:2 Misses:4]
Access: 3  MISS FirstIn ->    [1, 4, 3] <- Lastin  Replaced:2 [Hits:2 Misses:5]
Access: 0  MISS FirstIn ->    [4, 3, 0] <- Lastin  Replaced:1 [Hits:2 Misses:6]
Access: 3  HIT  FirstIn ->    [4, 3, 0] <- Lastin  Replaced:- [Hits:3 Misses:6]
Access: 1  MISS FirstIn ->    [3, 0, 1] <- Lastin  Replaced:4 [Hits:3 Misses:7]

FINALSTATS hits 3   misses 7   hitrate 30.00

Compare with LRU.