Suggest edit — clock algorithm

Title

Name

Note

---
title: "clock algorithm"
type: concept
related: [Demand Paging]
source: https://www.jemoka.com/posts/kbhclock_algorthium/
confidence: high
status: active
---

in demand paging, if we have to kick out a page, which one do we kick?
possible basic approaches random page (this works surprisingly well) throw out the page that&rsquo;s the longest in memory (this is BAD because if a page is there for a long time, its probably accessed a lot) oracle (pick the page whose next accesses is farest in the future&hellip; we can&rsquo;t predict the future) LRU (replace the page that&rsquo;s accessed longest time ago) LRU sounds decently good, but recall that \(2^{36}\) wall times to store wall time for each page are needed which is bad
clock algorithm rotate through all pages until we find one that hasn&rsquo;t been referenced since last time
we add a reference bit to the page table&mdash;its set to \(1\) if the program wrote or read each page, otherwise its set to \(0\) when page kick is needed, clock algorithm starts where it left off before and scan through physical pages each page it checks with reference bit 1, it sets the reference bit as 0 if it checked a page and its reference bit is 0, we kick it out (because we&rsquo;ve gone through two ) We now save the position of the hand&mdash;we want to begin checking with the page that hasn&rsquo;t been checked for the longest time.
If every page has a reference bit is one, running this algorithm doesn&rsquo;t break because it would set its immediately next bit of memory.
page replacement model per-process replacement THIS IS NOT USED: we only kick out our own pages (but&hellip; how would we know how many pages we allocate max per process before we start kicking?).
global replacement THIS IS USED: a page fault in one process can kick out a page from another process. all pages from all processes in a single pool.
recall: demand paging get space:
pick a page to kick out write it to disk mark the old page map entry as &ldquo;not present&rdquo; update the new page map entry for the new process + point to our reused page restore kicked page:
trigger page fault check swap (if it isn&rsquo;t present, page fault end) get a new physical page by kicking another page out load the data from disk into that reused page update page map yet again