CLOCK-Pro. We can improve CLOCK page replacement effective

Introduction

When we speak about page replacement algorithms immediately come to mind well-known algorithms such as: LRU, MRU, CLOCK, LIRS, however, each of them has its disadvantages about virtual memory (VM) management and other things (more about this algorithms).

Let's speak about improvement of CLOCK algorithm which called CLOCK-Pro. This page replacement algorithm bring all valuable advantages of LIRS algorithm into CLOCK algorithm and this improvement positive effect on execution times of some programs.

Brief basic concepts of CLOCK-Pro

CLOCK-Pro uses basic concepts of LIRS and CLOCK;
For replacement decision CLOCK-Pro uses reuse distance instead of recency;
There are three hands of CLOCK-Pro: Hand-cold, Hand-hot and Hand-test;
Since Memory = Hot pages memory + Cold pages memory therefore allocation of memory pages is adaptively adjusted;
CLOCK-Pro algorithm keep track of recently replaced pages. Hot pages all resident, cold pages also resident.

General description of the algorithm

As we noted above memory allocations for hot and cold pages are fixed. All hot pages (mh) in algorithm are cached. Before replacing hot page must changed into cold page. All other pages except the hot get cold status. Some cold pages (mc) also cached, but about another m non-resident cold we have cached only their access information. Like in CLOCK algorithm all pages organised as a circular linked list and each page has it's status (cold or hot). All cold pages has flag which indicated if cold page is in test period.

CLOCK-Pro has 3 types of hands:

Hand-hot: find a hot page to be changed into a cold page;
Hand-cold: find cold pages and note flag if reuse distance of cold page is too large, or note the fresh access of cold page;
Hand-test: determines whether a cold page become a hot or remove non-resident cold page out of clock;

All the hands move in the clockwise direction. Cold page can be resident if it was demoted from hot page or it had fresh access (replacement). The basic algorithm is shown in Figure 1.

Figure 1

CLOCK-Pro in action

Implementation of CLOCK-Pro

There is CLOCK-Pro algorithm implementation on C# on Github

Let's discuss about methods and classes of this implementation.

ClockProItem class contains key of item and type of item (hot,cold,test) it's represents page of CLOCK-Pro algorithm.

ClockPro class contains all methods and variables which describe CLOCK-Pro cache algorithm.

Main methods are:

GetItem
SetItem
RemoveItemFromCache
IsCached
HandHotAction, HandColdAction, HandTestAction
EvictItems
AddMetadata, DeleteMetadata

All methods and variables has full documentation in source code on GitHub.

The behavior of the algorithm for different memory allocations for the hot and cold pages

It's interesting to see that the relatively cold pages algorithm CLOCK-Pro behaves similar to the algorithm CLOCK or even identical. Hand-cold CLOCK-Pro performs the same action as the hand in the algorithm CLOCK: It passes the page to the flag 1 and replaces the page with the flag of 0. Thus, we can see that the increase mc doing action CLOCK-Pro algorithm similar to the actions of a CLOCK .

So how do you change the performance of the algorithm CLOCK-Pro by varying the memory usage of hot and cold pages. Reducing the number of pages of the cold affects the rapid replacement of the cold pages and reduce the impact of hot pages in the cold. However, with high access rate, we will have little re-use distances and cold pages will be cleaned immediately after downloading from memory. This actually generates unnecessary mistakes for pages with small distances reuse. Increasing mc allow store these pages in the cache for a longer period of time and make it more accessible and re-converted into hot pages without replacement. Thus, they can save the additional page faults.

However mnozhno do CLOCK-Pro adaptive and adjust the value of mc depending on the behavior of the algorithm (more here)

Bibliography

Xiaodong Zhang CLOCK-Pro: An effective Improvement of CLOCK replacement. Presentation

Song Jiang An effective Improvement of CLOCK replacement. Artice

Images for CLOCK-Pro in action from: http://www.slideshare.net/huliang64/clockpro