I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm.
could anyone help me understand?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Clock is second chance. Given the same input they will both produce the same replacements at the same points in time. The only difference is the details of implementation. Second chance is usually described in terms of a "fifo" which is assumed to be a linked list where there is a pointer to the
tail and every node contains a pointer to
next. Then when you remove a page from the head of the fifo you do it by setting
head = head->next. When you insert a page on the tail of the fifo you do it by setting
tail->next = new_node,
tail = new_node,
new_node->next = NULL.
Clock is just a simpler (and slightly faster) implementation of a fifo where you keep a circular linked list.
tail->next points to what was the head in our old structure. We only need one pointer, the pointer to
tail. Now removing a node from head is simply
tail->next=tail->next->next and inserting a node on the tail is
new_node->next = tail->next,
tail->next = new_node,
tail = new_node. This is all about the same as the non-circular version. The efficiency comes when you need to move a node from the head to the tail. That's just
tail = tail->next with the circular list.
By adding a second clock hand to the clock algorithm you get an extremely low-cost approximation of not-recently-used (which is an approximation of least-recently-used.)
In the two-handed clock algorithm you have two clock hands. One of the hands is just like before, it points at the next page being considered for replacement. When a replacement is required we just keep moving this clock hand (clearing reference bits) until we find a page with the reference bit cleared, and that's the page that gets replaced. (So this clock hand is just doing the clock implementation of second chance.)
The second clock hand is another pointer into the circularly linked list. The purpose of the second hand is to clear reference bits. Every once in a while you clear the reference bit on the linked-list node that the second hand is pointing to, and set
second_hand = second_hand->next. This eliminates one of the problems with second chance, which is that when a page is only used a small amount right after it is first fetched then second-chance will require two cycles through the fifo before that page gets replaced. In the two-handed clock algorithm those "short-term usage" pages get replaced after just one cycle through the fifo.
Another replacement algorithm you might look at is WSClock of Carr and Hennessy. It is a combination of the two-handed clock with a bunch of heuristics that are helpful in practice.