C++ program to implement LRU page replacement algorithm

C++ program to implement Least Recently Used page replacement algorithm using circular queue.

C++ program to implement Least Recently Used page replacement algorithm using Linked list

#include<iostream>
using namespace std;
struct node
{
    char data;
    node *next;
};
class lru_alg
{
    char ref[100];
    int frame,count,fault;
    node *front,*rear;
public:
    lru_alg()
    {
        front=rear=NULL;
        fault=count=0;
    }
    void getdata();
    void page_fault();
};
void lru_alg::getdata()
{
    cout<<"Enter Page reference string : ";
    cin.getline(ref,50);
    cout<<"Enter no. of frames : ";
    cin>>frame;
}
void lru_alg::page_fault()
{
    int flag=0;
    for(int i=0;ref[i]!=0;i++)
    {
        if(ref[i]==' ')
            continue;
        if(front==NULL)
        {
            front=rear=new node;
            front->data=ref[i];
            front->next=NULL;
            fault=count=1;
        }
        else
        {
            node *temp=front,*prev=NULL;
            while(temp!=NULL)
            {
                if(temp->data==ref[i])
                {
                        flag=1;
                        if(prev==NULL)
                        {
                            rear=rear->next=front;
                            front=front->next;
                            rear->next=NULL;
                        }
                        else if(temp!=rear)
                        {
                            prev->next=temp->next;
                            rear=rear->next=temp;
                            temp->next=NULL;
                        }
                        break;
                }
                prev=temp;
                temp=temp->next;
            }
            if(flag==0)
            {
                if(count==frame)
                {
                    rear=rear->next=front;
                    front=front->next;
                    rear->data=ref[i];
                    rear->next=NULL;
                }
                else
                {
                    rear=rear->next=new node;
                    rear->data=ref[i];
                    rear->next=NULL;
                    count++;
                }
                fault++;
            }
            flag=0;
        }
    }
    cout<<"Number of page faults : "<<fault;
}
int main()
{
    lru_alg page;
    page.getdata();
    page.page_fault();
    return 0;
}

C++ program to implement Least Recently Used page replacement algorithm with graphical representation

Following program uses BGI graphics and compiled it using TurboC/C++ 3.0 compiler.

#include<iostream.h>
#include<graphics.h>
#include<conio.h>
struct node
{
    char data;
    node *next;
};
class lru_alg
{
    char ref[100];
    int frame,count,fault,x,y;
    node *front,*rear;
public:
    lru_alg()
    {
front=rear=NULL;
fault=count=0;
x=5,y=50;
    }
    void getdata();
    void chart();
    void page_fault();
};
void lru_alg::chart()
{
   char d[2];
   node *temp=front;
   for(int i=0;i<frame;i++)
   {
      if(temp!=NULL)
      {
 d[0]=temp->data;
 temp=temp->next;
 d[1]=0;
      }
      else
d[0]=0;
      rectangle(x,y+i*20,x+20,y+(i+1)*20);
      outtextxy(x+10,y+i*20+10,d);
   }
}

void lru_alg::getdata()
{
    cout<<"Enter Page reference string : ";
    cin.getline(ref,50);
    cout<<"Enter no. of frames : ";
    cin>>frame;
}
void lru_alg::page_fault()
{
    int flag=0,x1=getmaxx();
    for(int i=0;ref[i]!=0;i++)
    {
if(ref[i]==' ')
   continue;
if(front==NULL)
{
   front=rear=new node;
   front->data=ref[i];
   front->next=NULL;
   fault=count=1;
   chart();
}
else
{
   node *temp=front,*prev=NULL;
   while(temp!=NULL)
   {
if(temp->data==ref[i])
{
flag=1;
if(prev==NULL)
{
   rear=rear->next=front;
   front=front->next;
   rear->next=NULL;
}
else if(temp!=rear)
{
   prev->next=temp->next;
   rear=rear->next=temp;
   temp->next=NULL;
}
break;
}
prev=temp;
temp=temp->next;
   }
   if(flag==0)
   {
if(count==frame)
{
   rear=rear->next=front;
   front=front->next;
   rear->data=ref[i];
   rear->next=NULL;
}
else
{
   rear=rear->next=new node;
   rear->data=ref[i];
   rear->next=NULL;
   count++;
}
chart();
fault++;
   }
   flag=0;
}
char d[2];
d[0]=ref[i],d[1]=0;
outtextxy(x+10,y-15,d);
x+=20;
if(x>x1)
{
  x=5;
  y+=frame*20+30;
}
    }
    cout<<"Number of page faults : "<<fault;
}
int main()
{
    lru_alg page;
    page.getdata();
    int gdriver = DETECT,gmode;
    initgraph(&gdriver, &gmode, "");
    page.page_fault();
    getch();
    return 0;
}

OUTPUT