the second-chance algorithm
Plain FIFO evicts the oldest page even if you just used it — clearly too harsh. The second-chance algorithm softens FIFO with one mercy: before throwing out an old page, check whether it has been used recently, and if so, give it another lap before it can be evicted. It is FIFO that pauses to ask 'have you been useful lately?' and forgives the page that has.
The common implementation is the clock algorithm. Picture all the frames arranged in a circle with a single hand (pointer) sweeping around, like a clock. When a victim is needed, the hand inspects the page it points at. If that page's reference bit is 0, it has not been touched since last checked — evict it and advance the hand. If the reference bit is 1, the page got used recently, so we do not evict it; instead we clear its reference bit to 0 (using up its second chance) and advance the hand to the next page. The hand keeps sweeping, clearing 1s to 0s, until it finds a page whose bit is already 0, which becomes the victim. A page that keeps getting referenced keeps getting its bit re-set to 1 and survives; a truly idle page is found on the next sweep.
Why it matters: the clock gives a good LRU-like result using only the single reference bit and a moving pointer — cheap enough that real operating systems use variants of it. The enhanced second-chance algorithm goes further by also reading the dirty bit, ranking pages into four classes from (not referenced, not modified) — the best, cheapest victim — up to (referenced, modified) — the worst — and preferring to evict clean, unreferenced pages so it avoids a write-back. The honest caveat: it only approximates LRU; in the worst case where every bit is 1, the hand makes a full sweep clearing everything and then behaves like plain FIFO.
The clock hand points at a page with reference bit 1. Instead of evicting it, the OS clears the bit to 0 and moves on. It points at the next page, whose bit is already 0 — that page is the victim. The first page earned a second chance because it had been used recently.
Reference bit 1 buys a reprieve (cleared to 0); the first page found at 0 is evicted.
If every page's reference bit is 1, the clock sweeps all the way around clearing them and then degenerates into plain FIFO. The enhanced version also uses the dirty bit to prefer clean victims and skip a write-back.