First In First Out (FIFO)
This is the simplest algorithm. It processes requests in the same order as they arrive. This technique improves the response time. However, the throughput is not efficient. It involves a lot of near random head and disk movements. This algorithm is used only in small systems where I/O efficiency is not very important.
- FIFO assumes oldest page allocated is the one least likely to be needed.
- OS keeps a list of pages in allocation order: head is oldest, tail is most recently allocated.
- FIFO chooses head page (i.e oldest) to copy to disk.
- Simple to implement, but doesn't check page use, so a heavily used page may be paged out.
- Gives poor paging performance. Often the page that was paged out must be immediately paged back in. Lots of disk I/O.
- Second chance is a variation on FIFO. When a page is needed, look at the oldest page.
- If A bit is 0 (i.e no recent access), use it. Otherwise, set A to 0 and put it on the tail (as if it had just been allocated).
- Aim here: find any page not accessed in a long time.
- If all pages have been accessed, 2nd chance degenerates to FIFO.
- Both FIFO and 2nd chance sare simple, perform worse than NRU: an old page not the same as an unused page.
|