Project #1 FAQ

Frequently Asked Questions

  1. What's the acceptable time complexity of Victim function of the Clock Replacer?

O(init_size)

  1. What's the difference between Unpin/Pin and Pin/Victim?

    Pin/Unpin: When a page is unpinned from the buffer pool. There are two scenarios: the page is no longer needed by any threads or the page is needed by at least one thread. If a page is needed by at least one thread, then the frame containing it is not a candidate for replacement. However, if a page is no longer needed by any thread, the frame containing it should be added to the Clock Replacer with a call to Unpin. Unpin should set some kind of ref bit to indicate that it is recently accessed, but overall the name is just to indicate that it is potentially an action following an unpin from the buffer pool. Similarly, Pin in Clock Replacer is an action following pinning a page in the buffer pool. What you should do in Pin for the Clock Replacer should depend on whether the Clock Replacer contains the frame being pinned in the buffer pool or not.

    Pin/Victim: These two operations are similar, but not totally the same. Pin is just an action following pinning a page in the buffer pool. So when a frame get unpinned (assume no other thread is accessing it) then pinned, it first get added to the clock replacer (Unpin) then removed (Pin) because a thread is accessing its content again. Victim is different because it returns a frame to be replaced, but still no thread is accessing its content. Overall, both Pin and Victim remove candidates from the clock replacer. When you call Victim, there's nobody for you to kill, then you would return false.