A simple algorithm for paging in a virtual memory system. It is supposed to give a very crude approximation of the least recently used algorithm, while using very little memory or time.
Every physical page has a "
mark" bit associated with it. Any access to that page sets
mark. Also, the operating system stores the last page scanned ("
last") in some reasonably-persistant manner (it is not local to the swap-out algorithm).
Now suppose a page needs to be swapped out. Here's how to select it: commence scanning pages from
last+1 in a cyclic manner (i.e. after the highest numbered page continue with the first page):
last = (last+1) % NUM_PAGES; (in practice, a faster method might be used than to divide by
NUM_PAGES). If page
mark bit is clear, we pick
last to swap out. Otherwise, we clear
mark bit, and continue.
The name "second chance" comes from the fact that after being accessed, a page will only be swapped out the second time the
last pointer reaches it.
Better methods for paging are known (and used in all major operating systems).