What's the difference between Clock and Second Chance Page-Replacement Algorithm?

Problem Detail: 

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?

Asked By : Sino Ka

Answered By : Wandering Logic

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 head and 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.

Two-handed clock

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29092