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 last's mark bit is clear, we pick last to swap out. Otherwise, we clear last's 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).

Log in or register to write something here or to contact authors.