In operating system design, the clock algorithm is a replacement policy for page tables. Core premise: we might have more physical pages we need to refer to than we have in memory. To rectify this, we need to swap pages in and out of secondary storage and memory.
implemented in hardware by MMU. basically free. approximation of LRU
data structures:
- circular list of pages in memory
- haha looks like a clock
- uses a reference bit for each page in memory
- has a “hand” iterator pointing to the last element examined
algorithm to insert a new page:
- check hand reference bit, if 0 then place the page and advance hand
- if reference bit is 1, set to 0, advance hand then repeat
- for page accesses, set ref bit to 1 — if already 1, no need to change
- two strike system