...

• 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