Question

1. Implement the frame replacement algorithm for virtual memory

Assume a computer system have 10 memory frames available inside the physical memory and is required to execute a process containing 20 pages. Assume a process P has been executed in the system and produced a sequence of 40 page demands as follows:

Page demands trace of process P

Demand	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	cont.
Page	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	below

	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
	1	2	1	1	2	6	7	8	9	1	5	6	7	7	11	15	16	11	20	2

Implement the following frame replacement algorithms (either in separated or a single Java program):

• First-in-first-out (FIFO) – select the candidate that is the first one that entered a frame
• Least-recently-used (LRU) – select the candidate that is the least referred / demanded
• Optimal – select the candidate based on future reference which such process will be the least immediately referred / demanded.

The program for each algorithm should allow the user to specify:

• the total of frames provided in memory (F)
• the total of page demands (N)
• a list of N page demands.

Use the demands’ sequence to calculate the number of page faults produced by each algorithm (or your program may ask the input once and use the same input for all the algorithms).

Using the example given (10 frames, 40 page demands), compare which of the algorithms produce the least amount of page faults for process P.

Answer 1

FIFO Algorithm

#include <stdio.h>
main(){
   int reference_string[100],i=0;
   printf("Enter Reference String:\nEnter -1 to exit:\nEnter No:");
   scanf("%d",&reference_string[i]);
   while(reference_string[i]!=-1){
          i++;
          printf("Enter No:");
          scanf("%d",&reference_string[i]);
   }
   int n,j=0,k,a[n],pf=0,ph=0,flag=0;
   printf("Enter no of frames:");
   scanf("%d",&n);
   printf("\t\t\n\n----------------\n\t\t reference string ");
   i = 0;
   while(reference_string[i] != -1){
           printf("%d ",reference_string[i]);
           i++;
   }
   printf("\n\n");
   for(i=0;i<n;i++){
       a[i]=-1;
   }
   printf("   |");
   for(i=0;i<n;i++){
      printf(" F%d",i+1);
   }
   printf(" status\n");
   for(i=0;reference_string[i] != -1;i++){
           flag = 0;
           for(k=0;k<n;k++){
               if(a[k]!=-1)
                printf("%2d ",a[k]);
               else
                printf("   ");
               if(a[k]==reference_string[i]){
                   flag=1;
                   ph++;
               }
           }
           if(flag==0){
               printf("PF\n");
               pf++;
               a[j]=reference_string[i];
               j=(j+1)%n;
           }else{
                  printf("PH\n");
           }
   }
   printf("No of page faults = %d\n",pf);
    printf("No of page hits = %d",ph);
}

LRU Algorithm

#include <stdio.h>
#include <string.h>
main(){
   int reference_string[100],i=0,min,full=0;
   printf("Enter Reference String:\nEnter -1 to exit:\nEnter No:");
   scanf("%d",&reference_string[i]);
   while(reference_string[i]!=-1){
       i++;
       printf("Enter No:");
       scanf("%d",&reference_string[i]);
   }
   int n,j=0,k;
   printf("Enter no of frames:");
   scanf("%d",&n);
   int a[n],st[n],pf=0,ph=0,flag=0;
   for(i=0;i<n;i++){
       a[i]=-10;
   }
   printf("Enter Reference String:\t");
   for(i=0;reference_string[i]!=-1;i++){
       printf("%d ",reference_string[i]);
   }
   printf("\n\n\n");
   for(i=0;i<n;i++){
       printf(" F%d",i+1);
   }
   printf(" status\n");
   int g,pos;
   for(i=0;reference_string[i]!=-1;i++){
       flag=0;
       for(k=0;k<n;k++){
           if(a[k]!=-10){
               printf("%2d ",a[k]);
           }
           else
               printf("   ");
           if(a[k]==reference_string[i]){
               flag=1;
               ph++;
           }
       }
       if(flag==0){
           printf("PF\n");
               for(g=0;g<n;g++){
                       st[g] = -1;
                       for(k=i;k>0;k--) {
                           if(a[g] == reference_string[k]){
                               st[g] = k;
                               break;      
                           }  
                       }
                   }
               min=st[0];
               pos = 0;
               for(k=0;k<n;k++){
                   if(st[k]<min){
                       min = st[k];
                       pos=k;
                   }
               }
           pf++;
           a[pos]=reference_string[i];
       }else{
           printf("PH\n");
       }
   }
   printf("No of page faults = %d\n",pf);
   printf("No of page hits = %d",ph);
}

OPT Algorithm

#include <stdio.h>
#include <string.h>
main(){
   int reference_string[100],i=0,min,full=0;
   printf("Enter Reference String:\nEnter -1 to exit:\nEnter No:");
   scanf("%d",&reference_string[i]);
   int z =0;
   while(reference_string[i]!=-1){
       i++;
       z++;
       printf("Enter No:");
       scanf("%d",&reference_string[i]);
   }
   int n,j=0,k;
   printf("Enter no of frames:");
   scanf("%d",&n);
   int a[n],st[n],pf=0,ph=0,flag=0;
   for(i=0;i<n;i++){
       a[i]=-10;
   }
   printf("Enter Reference String:\t");
   for(i=0;reference_string[i]!=-1;i++){
       printf("%d ",reference_string[i]);
   }
   printf("\n\n\n");
   for(i=0;i<n;i++){
       printf(" F%d",i+1);
   }
   printf(" status\n");
   int g,pos;
   for(i=0;reference_string[i]!=-1;i++){
       flag=0;
       int flag3 = 0;
       for(k=0;k<n;k++){
           if(a[k]!=-10){
               printf("%2d ",a[k]);
           }
           else
               printf("   ");
           if(a[k]==reference_string[i]){
               flag=1;
               ph++;
           }
       }
       if(flag==0){
           printf("PF\n");
               for(g=0;g<n;g++){
                       st[g] = -1;
                       for(k=i+1;k<z;k++) {
                           if(a[g] == reference_string[k]){
                               st[g] = k;
                               break;      
                           }  
                       }
                   }
               for(j = 0; j < n; j++){
                    if(st[j] == -1){
                        pos = j;
                        flag3 = 1;
                        break;
                    }
                }
                if(flag3 == 0) {
                   min=st[0];
                   pos = 0;
                   for(k=0;k<n;k++){
                       if(st[k]>min){
                           min = st[k];
                           pos=k;
                       }
                   }
               }
           pf++;
           a[pos]=reference_string[i];
       }else{
           printf("PH\n");
       }
   }
   printf("No of page faults = %d\n",pf);
   printf("No of page hits = %d",ph);
}