Replacement Algorithms

• Least Recently used (LRU)


• e.g. in 2 way set associative
  
  
  
  • Which of the 2 block is lru?
  
  
  
  


• First in first out (FIFO)
  
  
  
  • replace block that has been in cache longest
  
  
  
  


• Least frequently used (LFU)




• replace block which has had fewest hits

Write Policy

• Must not overwrite a cache block unless main memory is up to date


• Multiple CPUs may have individual caches


• I/O may address main memory directly

Write through

• All writes go to main memory as well as cache


• Multiple CPUs can monitor main memory traffic to keep local (to CPU) cache up to date


• Lots of traffic


• Slows down writes


• Remember bogus write through caches!

Write back

• Updates initially made in cache only


• Update bit for cache slot is set when update occurs


• If block is to be replaced, write to main memory only if update bit is set


• Other caches get out of sync


• I/O must access main memory through cache

Paging

• Split memory into equal sized, small chunks -page frames


• Split programs (processes) into equal sized small chunks - pages


• Allocate the required number page frames to a process


• Operating System maintains list of free frames


• A process does not require contiguous page frames


• Use page table to keep track

Logical and Physical Addresses - Paging