Next: The Working Set
Up: No Title
Previous: Paging
- 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!
![figure162](img13.gif)
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
![figure178](img14.gif)
Figure 13: Page Replacement - FIFO ?
Next: The Working Set
Up: No Title
Previous: Paging
Omer F Rana
Thu Feb 13 12:31:55 GMT 1997