MEMORY MANAGEMENT SCHEME II - OPTIMAL PAGE REPLACEMENT ALGORITHMS

Ex. No. :9(ii)

MEMORY MANAGEMENT SCHEME II   -    OPTIMAL PAGE  REPLACEMENT ALGORITHMS

AIM:

         To write a program in C to implement page replacement algorithm FIFO

PROBLEM DESCRIPTION:

          Page replacement algorithms are used to decide what pages to page out when a page needs to be allocated. This happens when a page fault occurs and free page cannot be used to satisfy allocation

OPTIMAL:

        

          “Replace the page, which will not be used for a longer sequence of time”. The frames are empty in the beginning and initially no page fault occurs so it is set to zero. When a page fault occurs the page reference string is brought into the memory. The operating system keeps track of all the pages in memory, thereby keeping track of most recently arrived and page there will not be used for a longer sequence of time is replaced. If the page in the page reference string is not in memory, the page fault is incremented and the one that will not be used for a longer sequence of time is replaced. If the page in the page reference string is in the memory, take the next page without calculating the page fault. Take the next page in the page reference string and check if the page is already present in the memory or not. Repeat the process until all the pages are referred and calculate page fault for all those pages in the page reference string for the number of available frames.

Algorithm

Algorithm

Step1: Start the program

Step2: Declare the required variables and initialize it.

Step3; Get the frame size and reference string from the user

Step4:  Keep track of entered  data elements

Step5:Accommodate a new element look for the element that is not likely to be used in future replace.

Step6: Count the number of page fault and display the value

Step7: Terminate the program

Program: //Program for optimal page replacement algorithm

#include<stdio.h>

int frames[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};

int nf,pf=0,pageno[50],np=0,location[10];

int search(int i);

void replace(int i);

void print(int i);

int main()

{

  int i=0;

  printf("Optimal Page Replacement Algorithm :\n");

  printf("-----------------------------------\n\n");

  printf("Enter the number of frames : ");

  scanf("%d",&nf);

  printf("Enter the page numbers one by one.");

  printf("Enter -1 when finished : \n");

  do

  {

    scanf("%d",&pageno[i]);

    np++;

    i++;

  }

  while(pageno[i-1] != -1);

  i=0;np--;

  printf("\nInput       Frame Status\n");

  printf("------------------------\n");

  while(pageno[i] != -1)

  {

    if(!search(i))

    {

      replace(i);

      pf++;

      print(i);

    }

    else

    {

      print(i);

    }

    i++;

  }

  printf("\n\nPage faults : %d",pf);

}

int search(int i)

{

  int j;

  for(j=0;j<nf;j++)

  {

    if(frames[j] == pageno[i])

       return 1;

  }

  return 0;

}

void replace(int i)

{

  int j,k,max;

  for(j=0;j<nf;j++)

  {

    if(frames[j] == -1)

    {

      frames[j] = pageno[i];

      return 0;

    }

  }

  for(j=0;j<nf;j++)

  {

    for(k=i+1;k<np;k++)

    {

      location[j] = np+1;

      if(pageno[k] == frames[j])

      {

        location[j] = k;

        break;

      }

    }

  }

  max = 0;

  for(j=0;j<nf;j++)

  {

    if(location[j] > location[max])

       max = j;

  }

  frames[max] = pageno[i];

}

void print(int i)

{

  int j;

  printf("\n  %d   -  ",pageno[i]);

  for(j=0;j<nf;j++)

     printf("  %2d",frames[j]);

}

"opt.c" 97L, 1499C written

[anandh@localhost ~]$ cc opt.c

 [anandh@localhost ~]$ ./a.out

Optimal Page Replacement Algoritm :

-----------------------------------

Enter the number of frames : 3

Enter the page numbers one by one.Enter -1 when finished :

1

2

5

6

2

4

5

1

2

4

1

2

-1

Input       Frame Status

------------------------

  1   -     1  -1  -1

  2   -     1   2  -1

  5   -     1   2   5

  6   -     6   2   5

  2   -     6   2   5

  4   -     4   2   5

  5   -     4   2   5

  1   -     4   2   1

  2   -     4   2   1

  4   -     4   2   1

  1   -     4   2   1

  2   -     4   2   1

Page faults : 6 

RESULT:

       Thus the C programs to implement the Page Replacement algorithms namely FIFO algorithms were written and executed. The obtained outputs were verified.