Clock Page Replacement

Simulate the clock (second-chance) page replacement algorithm.

Function

func ClockSim(frames int, accesses []int) (faults int, final []int)

Rules

• frames is the number of physical frames.
• accesses is the sequence of nonnegative page numbers; -1 is reserved for an empty frame.
• Use a circular clock hand starting at index 0.
• On hit: set reference bit to 1 without moving the hand or incrementing faults.
• On miss:
  • If the current hand points to an empty frame, use it.
  • Otherwise, advance hand while ref bit is 1, clearing each to 0.
  • Replace the first frame with ref bit 0.
• After inserting a page, set its ref bit to 1 and advance hand by 1.

Output

Return the number of page faults and the final frame contents. Empty frames should be -1.

For frames <= 0, this API returns zero faults and an empty slice. With positive frames and no accesses, return zero faults and all frames empty. Do not modify accesses.

Worked example

ClockSim(3, []int{2,4,2,6,8,4,9}) returns 5 and [8,4,9].

After filling the frames, bits are [1,1,1] and the hand is 0. The miss for 8 clears all three bits and replaces slot 0. The hit on 4 restores slot 1's bit without moving the hand. The miss for 9 therefore clears slot 1 and replaces slot 2. Final order is physical frame order, not recency order.