C program for LRU page replacement algorithm

OUTPUT :
2 -1 -1
2  3 -1
2  3 -1
2  3  1
2  5  1
2  5  1
2  5  4
2  5  4
3  5  4
3  5  2
3  5  2
3  5  2
no of page faults : 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<conio.h>
int fr[3];
void main()
{
void display();
int p[12]={2,3,2,1,5,2,4,5,3,2,5,2},i,j,fs[3];
int index,k,l,flag1=0,flag2=0,pf=0,frsize=3;
clrscr();
for(i=0;i<3;i++)
{
fr[i]=-1;
}
for(j=0;j<12;j++)
{
flag1=0,flag2=0;
for(i=0;i<3;i++)
{
if(fr[i]==p[j])
{
flag1=1;
flag2=1;
break;
}
}
if(flag1==0)
{
for(i=0;i<3;i++)
{
if(fr[i]==-1)
{
fr[i]=p[j];
flag2=1;
break;
}
}
}
if(flag2==0)
{
for(i=0;i<3;i++)
fs[i]=0;
for(k=j-1,l=1;l<=frsize-1;l++,k--)
{
for(i=0;i<3;i++)
{
if(fr[i]==p[k])
fs[i]=1;
}
}
for(i=0;i<3;i++)
{
if(fs[i]==0)
index=i;
}
fr[index]=p[j];
pf++;
}
display();
}
printf("\n no of page faults :%d",pf);
getch();
}
void display()
{
int i;
printf("\n");
for(i=0;i<3;i++)
printf("\t%d",fr[i]);
}

OUTPUT :
2 -1 -1
2  3 -1
2  3 -1
2  3  1
2  5  1
2  5  1
2  5  4
2  5  4
3  5  4
3  5  2
3  5  2
3  5  2
no of page faults : 4


30 Responses to “C program for LRU page replacement algorithm”

  1. This program gives wrong output. I guess 7 page faults according to given input.

    Reply
  2. Hello, can u give the C code for MRU page replement algorithm?. Pls…

    Reply
  3. Banani Medhi

    Totally wrong program. If two pages come in continuum, gives wrong output.

    Reply
  4. Abhishek

    #include
    void display(int fr[])
    {

    printf(“\n%d %d %d”,fr[0],fr[1],fr[2]);
    }

    int main()
    {int p[12]={2,3,2,1,5,2,4,5,3,2,5,2};
    int i,j;
    int flag1,flag2;
    int found;
    int pf=0;
    int fr[3]={-1,-1,-1};

    for(i=0;i<12;i++)
    { flag1=0;flag2=0;
    for(j=0;j<3;j++)
    {
    if(fr[j]==p[i])
    {flag1=flag2=1;
    break;
    }}

    if(flag1==0)
    {
    for(j=0;j<3;j++)

    if(fr[j]==-1)
    {
    fr[j]=p[i];
    flag2=1;
    pf++;
    break;
    }
    }
    int max,k;
    int l[3]={99,99,99};

    if(flag2==0)
    {
    for(j=0;j<3;j++)
    {
    for(k=0;k<i;k++)
    {if(fr[j]==p[k])
    l[j]=k;
    }

    }found=0;
    for(j=0;j<3;j++)
    {
    if(l[j]==99)
    {fr[j]=p[i];
    pf++;
    found=1;
    }}

    if(found==0)
    {
    max=0;
    for(j=0;j<3;j++)
    if(l[j]<l[max])
    max=j;

    fr[max]=p[i];
    pf++;
    }
    }
    found=0;
    display(fr);
    } printf("\nNo of Page faults: %d",pf);
    }

    Reply
    • #include
      #include
      #include

      using namespace std;
      using namespace stdext;

      template
      struct LRUCacheEntry
      {
      K key;
      T data;
      LRUCacheEntry* prev;
      LRUCacheEntry* next;
      };

      template
      class LRUCache
      {
      private:
      hash_map< K, LRUCacheEntry* > _mapping;
      vector< LRUCacheEntry* > _freeEntries;
      LRUCacheEntry * head;
      LRUCacheEntry * tail;
      LRUCacheEntry * entries;
      public:
      LRUCache(size_t size){
      entries = new LRUCacheEntry[size];
      for (int i=0; i<size; i++)
      _freeEntries.push_back(entries+i);
      head = new LRUCacheEntry;
      tail = new LRUCacheEntry;
      head->prev = NULL;
      head->next = tail;
      tail->next = NULL;
      tail->prev = head;
      }
      ~LRUCache()
      {
      delete head;
      delete tail;
      delete [] entries;
      }
      void put(K key, T data)
      {
      LRUCacheEntry* node = _mapping[key];
      if(node)
      {
      // refresh the link list
      detach(node);
      node->data = data;
      attach(node);
      }
      else{
      if ( _freeEntries.empty() )
      {
      node = tail->prev;
      detach(node);
      _mapping.erase(node->key);
      node->data = data;
      node->key = key;
      attach(node);
      }
      else{
      node = _freeEntries.back();
      _freeEntries.pop_back();
      node->key = key;
      node->data = data;
      _mapping[key] = node;
      attach(node);
      }
      }
      }

      T get(K key)
      {
      LRUCacheEntry* node = _mapping[key];
      if(node)
      {
      detach(node);
      attach(node);
      return node->data;
      }
      else return NULL;
      }

      private:
      void detach(LRUCacheEntry* node)
      {
      node->prev->next = node->next;
      node->next->prev = node->prev;
      }
      void attach(LRUCacheEntry* node)
      {
      node->next = head->next;
      node->prev = head;
      head->next = node;
      node->next->prev = node;
      }
      };

      Source:- http://tech.queryhome.com/17389/how-to-implement-least-recently-used-algorithm-using-c-c

      Reply
  5. ANJAN MUKHERJEE

    #include
    #include
    #include
    #include

    using namespace std;

    int main()
    {
    int p[12]={2,3,2,1,5,2,4,5,3,2,5,2},f=3,frame[3]={-1,-1,-1};
    int arr[3]={0,0,0},flag=0,pos,counter=1,m;

    for(int i=0;i<12;i++)
    { pos=0;
    for(int j=0;j<3;j++)
    {
    if(p[i]==frame[j])
    {
    flag=1;
    pos=j;
    }
    }

    if(flag==1)
    {
    arr[pos]=counter;

    }

    if(flag==0)
    {
    m=arr[0];

    for(int j=0;jarr[j])
    {
    m=arr[j];
    pos=j;
    }
    }

    frame[pos]=p[i];
    arr[pos]=counter;
    }

    counter++;

    cout<<frame[0]<<frame[1]<<frame[2]<<"tt";
    cout<<arr[0]<<arr[1]<<arr[2]<<"n";
    flag=0;

    }
    return 0;

    }

    Reply

Leave a Reply