Generalizing the cost function
-
Replace "accessing the
i-th item costsi" with costf(i)(44:08). -
f(i) = irecovers plain list update; paging is the choice (45:12):f(i) = 0 if i ≤ k,f(i) = 1 otherwise -
Extra rule in the paging model: when accessing item
iwithi > k, you must transpose it down to a position ≤ k (46:10). -
Interpretation: the first
klist positions are memory/cache; everything past them is disk, and accessing memory is free (48:27).
The paging problem itself
- Two levels of storage:
kcache lines of fast memory, and an effectively infinite disk split into blocks of one cache line (20:13,47:00). - A hit is free; a miss costs 1 to fetch from disk, after which the page stays free to access (
47:43). - If memory is full, the fetch forces an eviction — this choice is the entire decision problem (
20:41,48:04).
flowchart TD
R["request page p"] --> H{"p in cache?"}
H -- yes --> F["cost 0"]
H -- no --> C{"cache full?"}
C -- no --> L["load p, cost 1"]
C -- yes --> E["choose victim (replacement policy)"] --> L
Cache replacement heuristics and their list-update twins
| Policy | Rule | List-update analogue |
|---|---|---|
| LRU | Evict the least recently accessed page (49:06) | Exactly move-to-front (49:35) |
| LFU | Evict the least frequently accessed page over all history so far (49:35, 50:05) | Not frequency count — a student points out that a forced fetch of a cold page distorts the distribution, and the lecturer agrees (50:05, 50:37) |
| FIFO | Evict the page brought in longest ago (50:54) | — |
| Most-recently-fetched | Evict the page most recently brought in; listed in the Sleator–Tarjan paper, and the lecturer says he doesn't understand why anyone would use it (50:54, 51:42) | — |