Question

Write a program to implement various page replacement policies

Answer 1

#include<stdio.h>
 
int main()
{
    int frames[100], pages[100], n, m, i, j, k, flag, fault = 0;
 
    printf("Enter number of frames : ");
    scanf("%d",&n);
 
    printf("Enter number of pages : ");
    scanf("%d",&m);
 
    printf("Enter the reference string : ");
    for(i=0;i<m;i++)
        scanf("%d",&pages[i]);
 
    for(i=0;i<n;i++)
        frames[i] = -1;
 
    printf("Page Replacement Policy: \n");
    printf("1. FIFO\n");
    printf("2. LRU\n");
    printf("3. Optimal\n");
    printf("Enter your choice : ");
    scanf("%d",&k);
 
    switch(k)
    {
        case 1: // FIFO
            j = 0;
            for(i=0;i<m;i++)
            {
                flag = 0;
                for(k=0;k<n;k++)
                {
                    if(frames[k] == pages[i])
                    {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0)
                {
                    frames[j] = pages[i];
                    j = (j+1)%n;
                    fault++;
                }
            }
            break;
 
        case 2: // LRU
            for(i=0;i<m;i++)
            {
                flag = 0;
                for(j=0;j<n;j++)
                {
                    if(frames[j] == pages[i])
                    {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0)
                {
                    int min = 9999, pos;
                    for(j=0;j<n;j++)
                    {
                        if(min > frames[j])
                        {
                            min = frames[j];
                            pos = j;
                        }
                    }
                    frames[pos] = pages[i];
                    fault++;
                }
            }
            break;
 
        case 3: // Optimal
            for(i=0;i<m;i++)
            {
                flag = 0;
                for(j=0;j<n;j++)
                {
                    if(frames[j] == pages[i])
                    {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0)
                {
                    int max = -1, pos;
                    for(j=0;j<n;j++)
                    {
                        int dist = 0;
                        for(k=i+1;k<m;k++)
                        {
                            if(frames[j] == pages[k])
                                break;
                            else
                                dist++;
                        }
                        if(dist > max)
                        {
                            max = dist;
                            pos = j;
                        }
                    }
                    frames[pos] = pages[i];
                    fault++;
                }
            }
            break;
    }
 
    printf("Number of page faults = %d\n",fault);
    return 0;
}

 

 

 

 

 

Output :

Enter number of frames : 3
Enter number of pages : 10
Enter the reference string : 1 2 3 4 1 2 5 1 2 3
Page Replacement Policy: 
1. FIFO
2. LRU
3. Optimal
Enter your choice : 1
Number of page faults = 7