CSE 131 Lecture Notes - Lecture 17: Cache Replacement Policies, Fifo (Computing And Electronics), Freebsd
Document Summary
Maintain a linked list of all pages. Maintain the order in which they entered memory. Disadvantage: page in memory the longest may be often used. This algorithm forces pages out regardless of usage. Modify fifo to avoid throwing out heavily used pages. If reference bit is 0, throw the page out. Move page to tail of the list. Still easy to implement and better than plain fifo. Question: if all the pages are referenced, and you keep giving a second chance to every page, we will eventually pick a because it"s the first one that will be unreferenced. What if you add a to the back of the list, there was a reference to a. Will you keep looking for a page with an unreferenced bit and never find it. Clock hand points to next page to replace. If r=1, set r=0 and advance the clock hand. Continue until page with r=0 is found.
