Sunday, 29 September 2013

FIFO Page Replacement

//ALL there are three possibileties 
//first-: All frames are occupied and fault occurs, in such case we need to first deque and then enqueue the required page and variable counting the fault will be incremented
//second-: Some Frame is empty and fault occurs, in such we will enqueue the required page and increment the fault variable
//third-: if fault does not occur,in such case we will  move to next page 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct que
{
       int data;
       struct que *next;
       };
     
        void enque(struct que **q,int a)
       {
                      struct que *t,*r;
                   
                      if(*q==NULL)
                      {        
                        t=(struct que*)malloc(sizeof(struct que));
                        t->data=a;
                        t->next=NULL;
                        *q=t;        
                               
                                  }
                                  else
                                  {
                                      t=*q;
                                      while(t->next!=NULL)
                                      t=t->next;
                                      r=(struct que*)malloc(sizeof(struct que));
                                      r->data=a;
                                      r->next=NULL;
                                      t->next=r;
                                      }
                     
                     
                             }
                                             
                     
     
 int deque(struct que **q)
{
     if(*q==NULL)
     {
     printf("que is underflow");
     return -999;
     }
     struct que *r;
     r=*q;
     int x;
     x=r->data;
     *q=r->next;
     free(r);
     return x;
   
 }
 int ifexist(struct que **q,int i)
 {
     struct que *t,*r;
     t=*q;
                                      while(t!=NULL)
                                      {
                                     
                                       if(t->data==i)
                                       return 1;                
                                      t=t->next;
                                      }
                                      return 0;
 }
main()
{
     int a[100];//page sequence;
     int n;
     int Frame_size;
     puts("Eneter the number of pages to be entered");//number of pages
     scanf("%d",&n);
     int i=0;
     for(i=0;i<n;i++)
     scanf("%d",&a[i]);
     puts("\nEnter the size of Frame");//number of frames
     scanf("%d",&Frame_size);
     struct que *p;
     p=NULL;
     int j=0;
     int counter=0;//to count the number of frames
     enque(&p,a[j]);//first element is to insert without any condition
     j=j+1;
     int fault=1;//first element will always produce fault
     counter=counter+1;
     while(j<n)
     {
      if((counter==Frame_size)&&(!ifexist(&p,a[j])))//if all frames are filled and fault occurs
      {
      deque(&p);
      enque(&p,a[j]);
                     j++;
                     fault=fault+1;
   
                                       
     }
                                       
     if(ifexist(&p,a[j]))//if no fault occurs
     j++;
   
     if((counter!=Frame_size)&&(!ifexist(&p,a[j])))//if all frame not filled and fault occurs
     {
     enque(&p,a[j]);
     j++;
     fault=fault+1;
     counter=counter+1;
     }                                  
                                       
                                         }                                                    
      printf("\nNumber of Page fault occurs %d",fault);
      getch();
   
   
   
      }

No comments:

Post a Comment