O perating s ystems t hree e asy p ieces

22 Beyond Physical Memory: Policies

227

22.1 Cache Management

. . . . . . . . . . . . . . . . . . . . . . . 227

22.2 The Optimal Replacement Policy

. . . . . . . . . . . . . . . 228

22.3 A Simple Policy: FIFO

. . . . . . . . . . . . . . . . . . . . . 230

22.4 Another Simple Policy: Random

. . . . . . . . . . . . . . . . 232

22.5 Using History: LRU

. . . . . . . . . . . . . . . . . . . . . . . 233

22.6 Workload Examples

. . . . . . . . . . . . . . . . . . . . . . . 234

22.7 Implementing Historical Algorithms

. . . . . . . . . . . . . 237

22.8 Approximating LRU

. . . . . . . . . . . . . . . . . . . . . . 238

22.9 Considering Dirty Pages

. . . . . . . . . . . . . . . . . . . . 239

22.10 Other VM Policies

. . . . . . . . . . . . . . . . . . . . . . . . 240

22.11 Thrashing

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

22.12 Summary

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

References

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Homework

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244