Clock: A Second Chance for Pages

The story

LRU is the ideal page replacement policy for programs with locality, but updating an exact "last used" timestamp on every memory access would make the CPU crawl. Real kernels settle for a cheap approximation: the Clock algorithm, also called second chance.

The hardware sets one reference bit per page whenever the page is touched. The OS arranges the frames in a circle and keeps a hand pointing at the next candidate for eviction. A page that was used since the hand last passed gets a second chance instead of being thrown out.

The task

Write a function that returns the number of page faults a Clock-managed memory suffers for a reference string.

• Python: clock_faults(k, refs)
• JavaScript: clockFaults(k, refs)

k is the number of frames (an integer, at least 1) and refs is the list of page numbers referenced in order (integers, at least 0; it may be empty). Return an integer. The tests call your function for you: just define it, do not read input or print anything.

The rules

Memory starts empty: k empty frames, all reference bits 0, and the hand on frame 0.

For every reference, in order:

1. Hit (the page is in a frame): set that frame's reference bit to 1. The hand does not move.
2. Fault (the page is not in memory): count one fault, then repeat the following until the page is placed:
   • If the frame under the hand is empty or its reference bit is 0: put the new page there, set its reference bit to 1, advance the hand to the next frame (wrapping around) and stop.
   • Otherwise (the bit is 1): clear the bit to 0 and advance the hand. This is the second chance.

The loop always ends: after at most one full turn every bit is 0.

Example

For k = 3 and the reference string 1 2 3 4 1 2 5 1 2 3 4 5 the tests feed your function this input (first line k, then the references):

3
1 2 3 4 1 2 5 1 2 3 4 5

The expected result is 9. Replaying the start: pages 1, 2 and 3 fill the frames (3 faults) and the hand wraps to frame 0. Reference 4 faults and clears the bits of 1, 2 and 3 while the hand goes around once, then evicts page 1 from frame 0. Reference 1 then evicts page 2 (its bit is already 0), and so on.

3
1 2 3 4 1 2 5 1 2 3 4 5