...

• Q: what is relationship between LRU and OPT?
• Q: how could LRU be implemented? Cost?
• Tradeoff between implementation cost and performance
• Q: how could LRU be approximated?
• See H&P pp.379 for comparison of LRU and random replacement
  • Random is nearly as good as LRU, especially for larger caches
  • Random is considerably easier to implement