OS replacement policies: which page to evict?

This is considered ONLY when there are insufficient page frames.

Cache management

The main memory holds some subset of the pages, so it can be viewed as a cache for virtual memory pages. Then the goal is to minimize cache misses, and to maximize cache hits.

Knowing the number of cache hits and misses, we can calculate Average Memory Access Time（平均内存访问时间）:

$$ AMAT=(Hit_\% \cdot T_M)+(Miss_\%\cdot T_D) $$

$T_M$ represents the cost of accessing memory, $T_D$ represents the cost of accessing disk.

The optimal replacement policy

The optimal policy (OPT) is simple but hard to implement. It replaces the page that will be accessed furthest in the future.

The optimal policy can be used as a comparison to evaluate if an algorithm is efficient.

Types of cache misses:

• Compulsory miss (强制未命中, or colds tart miss 冷启动未命中): the cache is empty at the beginning.
• Capacity miss（容量未命中）: the cache is full, and it has to evict out something.
• Conflict miss（冲突未命中）: some other limit.

A simple policy: FIFO

The pages are placed in a queue, and when a replacement occurs, the first-in page is evicted.

Belady’s anomaly: the bigger the RAM is, the worse cache hit rate is when using FIFO.

Another simple policy: random

Simply pick a random page to replace under memory pressure.