MEMORY MANAGEMENT SCHEME II - PAGE REPLACEMENT ALGORITHMS

Ex. No. :9(i)

MEMORY MANAGEMENT SCHEME II                  -    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

FIFO:

         The frames are empty in the beginning and initially no page fault occurs so it is set to minus one. When a page fault occurs the page reference string is brought into memory. The operating system keeps track of all the pages in memory, herby keeping track of the most recently arrived and the oldest one. If the page in the page reference string is not in memory, the page fault is incremented and the oldest page 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 the 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: To accommodate a new element remove first entered element.

Step5: Repetition of elements avoid page fault.

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

Step7: Terminate the program

Program:

/*FIFO - Page replacement algorithm:

 -----------------------------------*/

#include<stdio.h>

#include<conio.h>

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

int nf,pf=0,ptr=0,pageno[50];

int search(int i);

void replace(int i);

void print(int i);

void main()

{

  int i=0;

  clrscr();

  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]);

   i++;

  }

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

  i=0;

  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);

  getch();

}

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)

{

  frames[ptr] = pageno[i];

  if(ptr == nf-1)

    ptr = 0;

  else

    ptr++;

}

void print(int i)

{

  int j;

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

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

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

}

[anandh@localhost ~]$ cc fifo.c

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

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   -     6   4   5

  5   -     6   4   5

  1   -     6   4   1

  2   -     2   4   1

  4   -     2   4   1

  1   -     2   4   1

  2   -     2   4   1

Page faults : 7