How do we replace pages or segments in cache ?

• Fetch and Replacement policies
• Consider this scenario : Primary (main) memory is full. No more vacancies. BUT need to store a page in it - need to get it from secondary store ... where do we put it ?
• Answer : We don't, we've got to take another page out to make room (c.f. CD or tape stacking problem)
• Segment placement more difficult - as segments can be of variable size
• Most obvious : Random : Take some page out at random and replace with incoming page May replace the newest page !
• More obvious : First In First Out : Take out page that has been in primary store for the longest period Most referenced page is oldest!

  
Figure 12: Page Replacement - where to place ?

• Least Recently Used : Get rid of page not used over the recent past (locality of reference) - Pages need to be timestamped
• Least Frequently Used : Replace page according to frequency of usage
• Not-Used-Recently : When page was last modified - has a dirty bit - approximates LRU
• Second Chance replacement FIFO : Have a queue of processes - and load in a particular order when space become available - based on the presence of a referenced bit being set. Idea = active pages will have referenced bit set, and move to the head of the queue
• Locality of reference : temporal or spatial : temporal (locality in time e.g. loops subroutines, stacks), spatial (locality in terms of neighbours - in space, e.g. arrays, sequential code generation).
• Locality implies : Processes tend to access some pages more than others (these are usually adjacent to each other (in virtual address space), or are related temporally), subset of most referenced pages for a process - hence the working set model

  
Figure 13: Page Replacement - FIFO ?