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.

Rohit Bairwa February 16, 2022



Assignment No. 4: Demand Paging


Demand paging the one of the most commonly used method of implanting the Virtual
Memory Management scheme. Virtual memory management scheme has the following
advantages:

1) System can execute the process of larger size than the size of available physical memory.
2) Reduced disk IO operations.
3) More numbers of processes can be loaded into memory.
4) Performance of multi-programming and multi-tasking can be improved.



SET A


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


#include<stdio.h>
#define MAX 20
int frames[MAX],ref[MAX],mem[MAX][MAX],faults,sp,m,n;
void accept()
{
int i;
printf("Enter no.of frames:");
scanf("%d", &n);
printf("Enter no.of references:");
scanf("%d", &m);
printf("Enter reference string:\n");
for(i=0;i<m;i++)
{
printf("[%d]=",i);
scanf("%d",&ref[i]);
}
}
void disp()
{
int i,j;
for(i=0;i<m;i++)
printf("%3d",ref[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mem[i][j])
printf("%3d",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 main()
{
accept();
fifo();
disp();
return 0;
}


Output :

@kali-linux:~/Desktop/Ty$ cc a4fifo.c 
@kali-linux:~/Desktop/Ty$ ./a.out
Enter no.of frames:4
Enter no.of references:12 15 12 18 6 8 11 12 19 12 6 8 12 15 19 8        
Enter reference string:
[0]=[1]=[2]=[3]=[4]=[5]=[6]=[7]=[8]=[9]=[10]=[11]= 15 12 18  6  8 11 12 19 12  6  8 12

 15 15 15 15  8  8  8  8     6  6   
    12 12 12 12 11 11 11    11  8   
       18 18 18 18 12 12    12 12   
           6  6  6  6 19    19 19   
Total Page Faults: 10

Short Explaination :

FIFO:

In this page replacement algorithm the order in which pages are loaded in memory, in same order they are replaced. We can associate a simple counter value with each frame when a page is loaded in memory. 
Whenever page is loaded in free frame a next counter value is also set to it. When page is to be replaced, select that page which has least counter value.It is most simple page replacement algorithm.


LRU :

This algorithm replaces that page from physical memory which is used least recently.
To implement this algorithm we associate a next counter value or timer value with each
frame/page in physical memory wherever it is loaded or referenced from physical
memory. When page replacement is to be performed, it will replace that frame in physical
memory which has smallest counter value.

Program (LRU):


#include<stdio.h>
#define MAX 20

int frames[MAX],ref[MAX],mem[MAX][MAX],faults,
sp,m,n,time[MAX];
void accept()
{
int i;
printf("Enter no.of frames:");
scanf("%d", &n);
printf("Enter no.of references:");
scanf("%d", &m);
printf("Enter reference string:\n");
for(i=0;i<m;i++)
{
printf("[%d]=",i);
scanf("%d",&ref[i]);
}
}
void disp()
{
int i,j;
for(i=0;i<m;i++)
printf("%3d",ref[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mem[i][j])
printf("%3d",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;
}
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()
{
accept();
lru();
disp();
return 0;
}


Output:


@kali-linux:~/Desktop/Ty$ cc a4lru1.c
@kali-linux:~/Desktop/Ty$ ./a.out
Enter no.of frames:4
Enter no.of references:12 15 12 18 6 8 11 12 19 12 6 8 12 15 19 8
Enter reference string:
[0]=[1]=[2]=[3]=[4]=[5]=[6]=[7]=[8]=[9]=[10]=[11]= 15 12 18  6  8 11 12 19 12  6  8 12

 15 15 15 15  8  8  8  8     6  6   
    12 12 12 12 11 11 11    11  8   
       18 18 18 18 12 12    12 12   
           6  6  6  6 19    19 19   
Total Page Faults: 10




SET B

Q.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 OPT
2) Implement MFU

Program :

#include<stdio.h>
int main()
{
    int no_of_frames, no_of_pages, frames[10], pages[30], temp[10], flag1, flag2, flag3, i, j, k, pos, max, faults = 0;
    printf("Enter number of frames: ");
    scanf("%d", &no_of_frames);
    
    printf("Enter number of pages: ");
    scanf("%d", &no_of_pages);
    
    printf("Enter page reference string: ");
    
    for(i = 0; i < no_of_pages; ++i){
        scanf("%d", &pages[i]);
    }
    
    for(i = 0; i < no_of_frames; ++i){
        frames[i] = -1;
    }
    
    for(i = 0; i < no_of_pages; ++i){
        flag1 = flag2 = 0;
        
        for(j = 0; j < no_of_frames; ++j){
            if(frames[j] == pages[i]){
                   flag1 = flag2 = 1;
                   break;
               }
        }
        
        if(flag1 == 0){
            for(j = 0; j < no_of_frames; ++j){
                if(frames[j] == -1){
                    faults++;
                    frames[j] = pages[i];
                    flag2 = 1;
                    break;
                }
            }    
        }
        
        if(flag2 == 0){
         flag3 =0;
        
            for(j = 0; j < no_of_frames; ++j){
             temp[j] = -1;
            
             for(k = i + 1; k < no_of_pages; ++k){
             if(frames[j] == pages[k]){
             temp[j] = k;
             break;
             }
             }
            }
            
            for(j = 0; j < no_of_frames; ++j){
             if(temp[j] == -1){
             pos = j;
             flag3 = 1;
             break;
             }
            }
            
            if(flag3 ==0){
             max = temp[0];
             pos = 0;
            
             for(j = 1; j < no_of_frames; ++j){
             if(temp[j] > max){
             max = temp[j];
             pos = j;
             }
             }            
            }
frames[pos] = pages[i];
faults++;
        }
        
        printf("\n");
        
        for(j = 0; j < no_of_frames; ++j){
            printf("%d\t", frames[j]);
        }
    }
    
    printf("\n\nTotal Page Faults = %d", faults);
    
    return 0;
}

Output:

 
@kali-linux:~/Desktop/Ty$ cc a4opt.c 
@kali-linux:~/Desktop/Ty$ ./a.out
Enter number of frames: 4
Enter number of pages: 12 15 12 18 6 8 11 12 19 12 6 8 12 15 19 8
Enter page reference string: 
15	-1	-1	-1	
15	12	-1	-1	
15	12	18	-1	
15	12	18	6	
8	12	18	6	
8	12	11	6	
8	12	11	6	
8	12	19	6	
8	12	19	6	
8	12	19	6	
8	12	19	6	
8	12	19	6	

Total Page Faults = 7



MFU :

  • This algorithm replaces that page from physical memory which is used most frequently.
  • This algorithm is bit complex to implement.
  • To implement this algorithm we have to maintain the history of each page that how many times it is used (frequency count) so far whenever it is loaded in physical memory or referenced from physical memory. When page replacement is to be performed, it will replace that frame in physical memory of which frequency count is greatest.
  • If frequency count is same for two or more pages then it will apply FCFS.
Program :


#include<stdio.h>
#define MAX 20

int frames[MAX],ref[MAX],mem[MAX][MAX],faults,
 sp,m,n,count[MAX];

void accept()
{
 int i;

 printf("Enter no.of frames:");
 scanf("%d", &n);

 printf("Enter no.of references:");
 scanf("%d", &m);

 printf("Enter reference string:\n");
 for(i=0;i<m;i++)
 {
  printf("[%d]=",i);
  scanf("%d",&ref[i]);
 }
}

void disp()
{
 int i,j;

 for(i=0;i<m;i++)
  printf("%3d",ref[i]);

 printf("\n\n");

 for(i=0;i<n;i++)
 {
  for(j=0;j<m;j++)
  {
   if(mem[i][j])
    printf("%3d",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;
}

int get_mfu(int sp)
{
 int i,max_i,max=-9999;

 i=sp;
 do
 {
  if(count[i]>max)
  {
   max = count[i];
   max_i = i;
  }
  i=(i+1)%n;
 }while(i!=sp);

 return max_i;
}

void mfu()
{
 int i,j,k;

 for(i=0;i<m && sp<n;i++)
 {
  k=search(ref[i]);
  if(k==-1)
  {
   frames[sp]=ref[i];
   count[sp]++;
   faults++;
   sp++;

   for(j=0;j<n;j++)
    mem[j][i]=frames[j];
  }
  else
   count[k]++;
  
 }

 sp=0;
 for(;i<m;i++)
 {
  k = search(ref[i]);
  if(k==-1)
  {
   sp = get_mfu(sp);
   frames[sp] = ref[i];
   count[sp]=1;
   faults++;
   sp = (sp+1)%n;

   for(j=0;j<n;j++)
    mem[j][i] = frames[j];
  }
  else
   count[k]++;
 }
}
      

int main()
{
 accept();
 mfu();
 disp();

 return 0;
}

Output :


@kali-linux:~/Desktop/Ty$ ./a.out
Enter no.of frames:4
Enter no.of references:12 15 12 18 6 8 11 12 19 12 6 8 12 15 19 8
Enter reference string:
[0]=[1]=[2]=[3]=[4]=[5]=[6]=[7]=[8]=[9]=[10]=[11]= 15 12 18  6  8 11 12 19 12  6  8 12

 15 15 15 15  8  8  8  8     8    12
    12 12 12 12 11 11 11    11    11
       18 18 18 18 12 12     6     6
           6  6  6  6 19    19    19
Total Page Faults: 10


Download PDF : Click here!


Related Post : 

Tags
Rohit Bairwa

Posted by Rohit Bairwa

Post a Comment

1 Comments

Thanks,To visit this blog.