Page replacement algorithm in C++

Quote from Wikipedia:

In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold. When the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the quality of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself. The page replacing problem is a typical online problem from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known.

In this article are going to implement clock algorithm.

Clock is a more efficient version of FIFO than Second-chance because pages don't have to be constantly pushed to the back of the list, but it performs the same general function as Second-Chance. The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the last examined page frame in the list. When a page fault occurs and no empty frames exist, then the R (referenced) bit is inspected at the hand's location. If R is 0, the new page is put in place of the page the "hand" points to, otherwise the R bit is cleared. Then, the clock hand is incremented and the process is repeated until a page is replaced.

Variants of Clock

• GCLOCK: Generalized clock page replacement algorithm.

• Clock-Pro keeps a circular list of information about recently referenced pages, including all M pages in memory as well as the most recent M pages that have been paged out. This extra information on paged-out pages, like the similar information maintained by ARC, helps it work better than LRU on large loops and one-time scans.

• WSclock. The "aging" algorithm and the "WSClock" algorithm are probably the most important page replacement algorithms in practice.

• Clock with Adaptive Replacement (CAR) is a page replacement algorithm that has performance comparable to ARC, and substantially outperforms both LRU and CLOCK. The algorithm CAR is self-tuning and requires no user-specified magic parameters.

Important : CLOCK is a conservative algorithm.

#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <list>


using namespace std;


class Process{
 private:
        string state;
        string name;
 int R;
 public:
        Process(string state, string name, int R){
 this->state = state;
 this->name = name;
 this->R = R;
        }
 
 void setState(string state){
 this->state = state;
        }

        string getState() {
 return this->state;
        }

 void setName(string name){
 this->name = name;
        }

        string getName() {
 return this->name;
        }

 void setR(int R){
 this->R = R;
        }

 int getR() {
 return this->R;
        }

 void toString() {
            cout<<"process "<<this->name<<": "<<this->state<<"\t";
        }
};


int main(int argc, char* argv[]) {
    //create a list
    //create sample processes from A to G
    Process processA = Process("new", "A", 0);
    list<Process> l(7, processA);
    list<Process>::iterator it = l.begin();
    Process processB= Process("new", "B", 1);
    it++;
    *it = processB;
    Process processC = Process("new", "C", 0);
    it++;
    *it = processC;
    Process processD = Process("new", "D", 1);
    it++;
    *it = processD;
    Process processE = Process("new", "E", 0);
    it++;
    *it = processE;
    Process processF = Process("new", "F", 1);
    it++;
    *it = processF;
    Process processG = Process("new", "G", 1);
    it++;
    *it = processG;


 for (list<Process>::iterator item = l.begin(); item != l.end(); item++) {
        cout<<item->getName()<<endl;
 if (item->getR() == 0) {
            list<Process>::iterator iter = l.begin();
            advance(iter, rand()%6);
            *item = *iter;
            cout<<item->getName()<<" "<<item->getR()<<endl;
        } else {
            item->setR(0);
            cout<<item->getName()<<" "<<item->getR()<<endl;
        }
    }


    system ("pause");
 return 0;
}

Hope this was helpful.