OS-(I) Assignment 4: Set A- 1)

(1) Write the simulation program to implement demand paging and show the page scheduling and total number of page faults for the following given page reference string. Give input n as the number of memory frames.

Reference String : 12,15,12,18,6,8,11,12,19,12,6,8,12,15,19,8
1) Implement FIFO
2) Implement LRU.

Solution:

#include<stdio.h>

#define MAX 20

int frames[MAX], mem[MAX][MAX],time[MAX],faults,sp,n;

int ref[]={12,15,12,18,6,8,11,12,19,12,6,8,12,15,19,8};

int m=16;

int sp=0;

void disp()

{

int i,j;

for(i=0;i<m;i++)

printf("%d ",ref[i]);

printf("\n\n");

for(i=0;i<n;i++)

{

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

{

if(mem[i][j]>=0)

   printf("%d ",mem[i][j]);

else

   printf(" ");

  }

printf("\n");

}

printf("Total Page Faults: %d\n",faults);

}

int search(int pno)

{

int i;

for(i=0;i<n;i++)

{

if(frames[i]==pno)

    return i;

}

return -1;

}

void fifo()

{

int i,j;

for(i=0;i<m;i++)

{

  if(search(ref[i])==-1)

{

frames[sp]=ref[i];

sp=(sp+1)%n;

faults++;

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

mem[j][i]=frames[j];

}

}

}

int get_lru()

{

int i,min_i,min=9999;

for(i=0;i<n;i++)

{

if(time[i]<min)

{

min=time[i];

min_i=i;

}

}

return min_i;

}

void lru()

{

        int i,j,k;

        for(i=0;i<m && sp<n;i++)

        {

            k=search(ref[i]);

if(k==-1)

{

frames[sp]=ref[i];

                time[sp]=i;

                faults++;

sp++;

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

                   mem[j][i]=frames[j];

                }

        else

      time[k]=i;

}

        for(;i<m;i++)

        {

            k=search(ref[i]);

            if(k==-1)

            {

                sp=get_lru();

                frames[sp]=ref[i];

                time[sp]=i;

                faults++;

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

                    mem[j][i]=frames[j];

            }

            else

                time[k]=i;

}

}

int main()

{

int ch,i,j;

do

{

       printf("\n\t\tMENU\n1.FIFO\n2.LRU\n3.Exit\n");

printf("\nEnter your choice\n");

scanf("%d",&ch);

switch(ch)

{

case 1: faults=0;

printf("Enter no. of frames: ");

        scanf("%d",&n);

for(i=0;i<n;i++)

{

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

                {

                    mem[i][j]=-1;

}

}

for(i=0;i<n;i++)

                        {

frames[i]=-1;

}

fifo();

disp();

break;

case 2: printf("Enter no. of frames: ");

scanf("%d",&n);

faults=0;

for(i=0;i<n;i++)

                        {

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

                        {

                            mem[i][j]=-1;

                        }

                        }

                        for(i=0;i<n;i++)

                        {

                            frames[i]=-1;

                        }

lru();

disp();

break;

case 3:

exit(0);

default:

printf("Wrong choice!\n");

}

}

while(ch<4);

return 0;

}