LRU in C Plus Plus

LRU in C++ Language

Operating systems use paging for memory management. Paging is a method to store or retrieve processes from the secondary memory into the main memory in the form of pages. Paging happens when a page fault occurs, and a free page cannot be used to satisfy the allocation. It is because there are none or the number of free pages is lower than the threshold. It generates the need of page replacement algorithm which can lessen the waiting time for pages in. The Least Recently Used (LRU) page replacement algorithm, needs to decide which page is to be replaced when the new page comes in.

This LRU algorithm manages page fault. The algorithm maintains a linked list of all the pages in the memory, it keeps the most recently used page in the front and the least recently used page at the rear position. Let us understand LRU with an example.

Example

Pages = 2 3 4 2 1 3 7 5 4 3
Number of iteration = 10
Memory size = 3

The sequence can be represented diagrammatically as follows.

2342137543

We will sequentially put the first three pages in the order given as we have sufficient space.

12345678910
222       
 33       
  4       

Now, comes 2. We will not replace 2 as it is already there.

2342137543

We will sequentially put the first three pages in the order given as we have sufficient space.

12345678910
2222      
 333      
  44      

Now remove 3 as it the least recent page used.

12345678910
22222     
 3331     
  444     

Now remove 4 as it the least recent page used out of all.

12345678910
222222    
 33311    
  4443    

Now remove 2 as it the least recent page used out of all.

12345678910
2222227   
 333111   
  44433   

Now remove 1 as it is the least recent page used out of all.

12345678910
22222277  
 3331115  
  444333  

Similarly, remove 3 as it is the least recent page used.

12345678910
22222277  
 33311155 
  444334  

Last we will remove 7 as it is least recent page used.

12345678910
2222227773
 333111555
  44433344
#include
using namespace std;
#include
int main()
 {
          int nopages, nofaults, page[20],i ,count=0;
          cout<<"\n\t Enter no of pages for which you want to calculate page faults:>"; 
          cin>> nopages;  //it will store the number of Pages
          <<"\n\t Enter the Reference String:";
          for(i=0;i< nopages;i++)
          {
          <<"\t"; cin>>page[i];
          }   
          <<"\n\t Enter the Number of frames:"; cin>> nofaults;
         int frame[nofaults],fcount[nofaults];
          for(i=0;i< nofaults;i++)
          {
          frame[i]=-1;
          fcount[i]=0; //it will keep the track of when the page was last used
          }
          i=0;
          while(i< nopages)
          {
            int j=0,flag=0;
            while(j< nofaults)
            {
               if(page[i]==frame[j]){  //it will check whether the page already exist in frames or not
               flag=1;
               fcount[j]=i+1;
               }
               j++;
            }   
            j=0;  
            <<"\n\t***\n";
            <<"\t"<<page[i]<<"-->";   
            if(flag==0)
            {
             int min=0,k=0;
              while(k<nof-1) { if(fcount[min]>fcount[k+1]) //It will calculate the page which is least recently used
                   min=k+1;
                  k++;
                }
               frame[min]=page[i]; 
               fcount[min]=i+1;  //Increasing the time
               count++;           //it will count the total Page Fault
            while(j< nofaults)
            {
               <<"\t|"<<frame[j]<<"|";
               j++;
            }
             }
           i++; 
          }
          <<"\n\t***\n";
          <<"\n\t Page Fault:"<<count;
          getch();
           0;
} 

Output

Enter no of pages for which you want to calculate page faults: 8
Enter the Reference String: 7
0
1
2
0
3
0
5
Enter the Number of frames: 3
7 7 -1 -1
0 7 0 -1
1 7 0 1
2 2 0 1
0
3 2 0 3
0
5 4 0 3
Page faults: 6

Please Login/Signup to comment