Project: audit eviction, admission, and expiry

Acceptance trace

In a three-frame CLOCK cache, read 47 after filling 47, 19, and 61; inserting 83 evicts 19. In a two-plus-two segmented cache, the read sequence promotes 47, 61, and 19, leaving 61 and 19 protected and 47 on probation. In a two-entry frequency-admission cache, a cold 83 is rejected but a repeatedly observed 61 replaces 19. In an eight-slot wheel, replacing 47's tick-three review with a tick-five review prevents the old event and leaves incident 19 until tick eleven.

Expected review record

clock-victim=19
protected=[61, 19]
cold-admitted=False
wheel-tick-3=[]
wheel-tick-5=[47]

Boundary and cost review

Force a CLOCK sweep in which every reference bit is set, and count all inspected frames. Overfill both segmented groups and test that a demoted record does not exist in protected and probation at once. Cause a sketch counter to age and verify no estimate increases solely from aging; record a rejected candidate's later requests before retrying. Schedule timers farther than one wheel revolution, replace and cancel keys, then advance across empty ticks. State the difference between an average map operation and a worst-case sweep, sketch reset, or large timer advance.

Common Mistakes

• Do not present a second-chance bit as an exact last-access timestamp.
• Do not promote a probation write when this policy promotes only reads.
• Do not call sketch estimates exact counts.
• Do not fire a timer based only on its wheel slot.

Connected lessons

• CLOCK caches: revisit pages through reference bits
• Segmented LRU: separate probation from protected reuse
• Frequency admission: compare an arrival with an eviction victim
• Hashed timing wheels: bucket incident expiries by tick
• Projects
• Quizzes
• Data Structures