What are the Concepts of Page Replacement Algorithms by Allowing them to Implement Page-replacement Algorithms?

page replacement algorithm
page replacement algorithm

1. Objectives
This programming assignment is designed to help students understand the concepts of page replacement algorithms by allowing them to implement page-replacement algorithms and measure the performance of these algorithms.
2. Program Description
In this assignment, students will implement two page-replacement algorithms: FIFO and LRU algorithms. In particular, students are asked to implement the FIFO algorithm using the timer-based implementation method (See slide for details), and the LRU algorithm using the stack-based implementation method. Students are encouraged to review class textbook and/or course slides for details of these algorithms.
3. Program Requirements
– The FIFO and LRU algorithms will be implemented on top of the memory manager that students have implemented in their programming assignment 3. Specifically, when the main memory is full, a page replacement algorithm will run to swap out/in a page from/to the main memory. As pages are swapped in and out, the page tables and the free frame list need to be updated.
– Students will implement the FIFO algorithm using a timer. Recall that in this timer-based implementation, a timer is associated with each frame; and this timer is used to find the oldest page, i.e., the page to be replaced. To implement the timer, students may want to use a system call, gettimeofday(), to obtain the current time.
JAVA function to retrieve the current system time.
– Students will implement the LRU algorithm using a stack. In this stack-based implementation, a stack is used to keep track of the least recently used page, i.e., when a page is referenced, the page is moved to the top of the stack.
– Three more user commands are included and need to be implemented in this programming
assignment as follows:
SET FIFO – this command is used to set the FIFO page-replacement algorithm as the default page replacement algorithm
SET LRU – this command is used to set the LRU page-replacement algorithm as the default page replacement algorithm
PRINT PF – this command is used to print the total number of page faults.

Solution:

#include<stdio.h>
#include <string>
#include <iostream>
#include<conio.h>
#include <sys/time.h>
#include <sys/types.h>
using namespace std;
void lru();
void fifo();
main()
{int op=0;
    do {    cout << “\nMenu \n”;
            cout << “1- LRU  \n” ;
            cout << “2- FIFO  \n” ;
             cout << “3- quit  \n” ;
            cout << “Options :  “;
            cin>>op;
          switch (op)
          {
        case 1:
            lru();
        break;
         case 2:
             fifo();
        break;
         case 3:
         exit(1);
        break;
        default:
            cout << “Invalid option ” <<endl;
        }
    }while(op != 3);
 
}
void lru(){
    
    int q[20],p[50],c=0,c1,d,f,i,j,k=0,n,r,t,b[20],c2[20];
printf(“Enter no of pages:”);
scanf(“%d”,&n);
printf(“Enter the reference string:”);
for(i=0;i<n;i++)
            scanf(“%d”,&p[i]);
printf(“Enter no of frames:”);
scanf(“%d”,&f);
q[k]=p[k];
printf(“\n\t%d\n”,q[k]);
c++;
k++;
for(i=1;i<n;i++)
            {
                c1=0;
                        for(j=0;j<f;j++)
                        {
                                    if(p[i]!=q[j])
                                    c1++;
                        }
                        if(c1==f)
                        {
                                    c++;
                                    if(k<f)
                                    {
                                                q[k]=p[i];
                                                k++;
                                                for(j=0;j<k;j++)
                                                printf(“\t%d”,q[j]);
                                                printf(“\n”);
                                    }
                                    else
                                    {
                                                for(r=0;r<f;r++)
                                                {
                                                            c2[r]=0;
                                                            for(j=i-1;j<n;j–)
                                                            {
                                                            if(q[r]!=p[j])
                                                            c2[r]++;
                                                            else
                                                            break;
                                                }
                                    }
                                    for(r=0;r<f;r++)
                                     b[r]=c2[r];
                                    for(r=0;r<f;r++)
                                    {
                                                for(j=r;j<f;j++)
                                                {
                                                            if(b[r]<b[j])
                                                            {
                                                                        t=b[r];
                                                                        b[r]=b[j];
                                                                        b[j]=t;
                                                            }
                                                }
                                    }
                                    for(r=0;r<f;r++)
                                    {
                                                if(c2[r]==b[0])
                                                q[r]=p[i];
                                                printf(“\t%d”,q[r]);
                                    }
                                    printf(“\n”);
                        }
            }
}
printf(“\nThe no of page faults is %d”,c);
    
}

void fifo(){
    int alloc_frames ;
    printf(“\n no of page frame is :\n”);
     cin>>alloc_frames;
int orig_str[alloc_frames] ;
int  n = alloc_frames, is,str_size = alloc_frames;
 
printf(“\n str :\n”);
            for(is=1;is<=n;is++)
            scanf(“%d”,&orig_str[is]);
    int page_table[alloc_frames];
    int index,flag,i, j=0,fault_count=0;
    for (i=0;i<str_size;i++) {
        flag=0;
        for(index=0;index<alloc_frames;index++) {
            if(orig_str[i] == page_table[index]) {
                flag=1;
            }
        }
        if(flag==0) {
                        page_table[j%alloc_frames]= orig_str[i];
                        fault_count++;
                        j++;
                            }
    }

    int replace_count= fault_count- alloc_frames;
    printf(“\nThe no of page replace count is %d”,replace_count);
     printf(“\nThe no of page faults is %d”,fault_count);
    
}

Report:

In this assignment concepts of page replacement algorithms were learned and implemented and their performance was measured. Two different algorithms were implemented in this assignment: FIFO and LRU algorithms.

How to Run the Program?

We implement the FIFO algorithm using a timer and LRU was implemented using ques.

In FIFO a timer is associated with each frame; and this timer is used to find the oldest page, i.e., the page to be replaced. As per user input pages are swapped in and out, the page tables and the free frame list is updated likewise. Whereas LRU is implemented using push & pop operation on stack.

  • When a user runs “PageRep.exe” file he’s presented with three options 1 for LRU, 2 for FIFO and 3 for Exit.
  • When a user chooses 1 for LRU, he’s then asked to enter no. of pages, after user inputs no. of pages, the program asks the user to reference string and then frame number. After taking input results are displayed.
  • When a user chooses 2 for FIFO, he’s then asked to enter no. of page frames, and string. After taking input results are displayed.

The following commands were used to achieve successful implementation:

  • SET FIFO: this command was used to set the FIFO page-replacement algorithm as the default page replacement algorithm
  • SET LRU: this command was used to set the LRU page-replacement algorithm as the default page replacement algorithm
  • PRINT PF: this command was used to print the total number of page faults.

Output Screenshot:

What are the Concepts of Page Replacement Algorithms by Allowing them to Implement Page-replacement Algorithms?
Output of Implementation

 

Challenges Faced:

The project is implemented with the help of studying different algorithm techniques. The project is ended with the great hands on C++ and tools as well as come across with the issues face during the implementation as well as development of the project. This project gives the level of confidence which has no match. Project gives the experience to manage team, to manage work load and to achieve the goal without any more delay in committed deadline.

During the development and implementation of project, come across with the new thing that is a planning plays the main role in any project, how to move forward in it is the main cause of success. The one method of solving LRU is implemented in the project but there are more than one ways to implement and solve the LRU algorithm as we discussed in the project.  So the main focus is to implement the different as discussed in paper for algorithms and compare the results with the existing system in terms of correctness, efficiency etc.

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here