SYSTEM PROGRAMMING
Q)WRITE A PROGRAM TO IMPLEMENT A DFA DRIVER FOR ANY GIVEN LANGUAGE. ACCEPT NUMBER OF STATES, NUMBER OF INPUT SYMBOLS,SET OF INPUT SYMBOLS,NUMBER OF FINAL STATES. SET OF FINAL STATES AND TRANSITION TABLE AS INPUT. (INPUT LANGUAGE SHUOLD BE GIVEN BY EXAMINER). WRITE MENU DRIVEN PROGRAM THAT WILL HAVE OPTIONS AS.
A)READ DFA
B)SHOW TRANSITION TABLE
C)CHECK ACCEPTANCE OF THE GIVEN STRING
D)EXIT.
---->
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int nos,noi,nof,finals[MAX],trans[MAX][MAX];
char input_symb[MAX],input_str[100];
void read_dfa()
{
int i,j;
printf("Enter no.of states:");
scanf("%d",&nos);
printf("Enter no.of input symbols:");
scanf("%d",&noi);
printf("Enter input symbols:");
scanf("%s",input_symb);
printf("Enter no.of finals:");
scanf("%d",&nof);
printf("Enter finals states:");
for(i=0;i<nof;i++)
scanf("%d",&finals[i]);
printf("Enter transition table:\n");
for(i=0;i<nos;i++)
{
for(j=0;j<noi;j++)
{
printf("d(q%d,%c)=",
i,input_symb[j]);
scanf("%d",&trans[i][j]);
}
}
}
void show_trans()
{
int i,j;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={");
for(i=0;i<nof;i++)
printf("q%d,",finals[i]);
printf("\b}\nd:\n\t");
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",trans[i][j]);
printf("\n");
}
}
void check()
{
int i,j,curr;
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,input_str+i);
curr = trans[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
for(i=0;i<nof;i++)
{
if(finals[i]==curr)
{
printf("Accept\n");
return;
}
}
printf("Reject\n");
}
int main()
{
int ch;
while(1)
{
printf("1.Read DFA\n2.Show Transition Table\n3.Check acceptance of given string\n4.Exit\n");
printf("Enter choice (1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1:
read_dfa();
break;
case 2:
show_trans();
break;
case 3:
check();
break;
case 4:
exit(0);
}
}
return 0;
}
---------------------------------------------
Q) WRITE A PROGRAM TO IMPLEMENT DFA DRIVER FOR THE LANGUAGE L="SET OF ALL STRING THAT STARTS WITH A,ENDING WITH B " OVER{A,B}.
--->
#include<stdio.h>
int nos=4;
int noi=2;
char input_symb[]={'a','b'};
int nof=1,final=2;
int d[][2]={{1,3},{1,2},{1,2},{3,3}};
char input_str[100];
int main()
{
int i,j,curr;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={q%d}\nd:\n\t",final);
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",d[i][j]);
printf("\n");
}
do
{
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,
input_str+i);
curr=d[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
if(curr==final)
printf("Accept\n");
else
printf("Reject\n");
printf("Continue Y(1)/N(0)?");
scanf("%d",&j);
}while(j==1);
return 0;
}
----------------------------------------
Q) WRITE A PROGRAM TO IMPLEMENT DFA DRIVER FOR THE LANGUAGE L="SET OF ALL STRING THAT CONTAINING 101 AS SUBSTRING" OVER{0,1}.
--->
#include<stdio.h>
int nos=4;
int noi=2;
char input_symb[]={'0','1'};
int nof=1,final=3;
int d[][2]={{0,1},{2,1},{0,3},{3,3}};
char input_str[100];
int main()
{
int i,j,curr;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={q%d}\nd:\n\t",final);
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",d[i][j]);
printf("\n");
}
do
{
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,
input_str+i);
curr=d[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
if(curr==final)
printf("Accept\n");
else
printf("Reject\n");
printf("Continue Y(1)/N(0)?");
scanf("%d",&j);
}while(j==1);
return 0;
}
--------------------------------------------------------------------------------------
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING FIFO PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FALUTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
PAGE REFERENCE STRING: 3,4,5,6,3,4,7,3,4,5,6,7,2,4,6.
--->
#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;
}
------------------------------------------------------------------------------------------
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING LFU PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FAULTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
#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_lfu(int sp)
{
int i,min_i,min=9999;
i=sp;
do
{
if(count[i]<min)
{
min = count[i];
min_i = i;
}
i=(i+1)%n;
}while(i!=sp);
return min_i;
}
void lfu()
{
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_lfu(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();
lfu();
disp();
return 0;
}
----------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING MFU PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FAULTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
----->
#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; }
-------------------------------------------------------------------------------------
DFA
Q)WRITE A PROGRAM TO IMPLEMENT A DFA DRIVER FOR ANY GIVEN LANGUAGE. ACCEPT NUMBER OF STATES, NUMBER OF INPUT SYMBOLS,SET OF INPUT SYMBOLS,NUMBER OF FINAL STATES. SET OF FINAL STATES AND TRANSITION TABLE AS INPUT. (INPUT LANGUAGE SHUOLD BE GIVEN BY EXAMINER). WRITE MENU DRIVEN PROGRAM THAT WILL HAVE OPTIONS AS.
A)READ DFA
B)SHOW TRANSITION TABLE
C)CHECK ACCEPTANCE OF THE GIVEN STRING
D)EXIT.
---->
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int nos,noi,nof,finals[MAX],trans[MAX][MAX];
char input_symb[MAX],input_str[100];
void read_dfa()
{
int i,j;
printf("Enter no.of states:");
scanf("%d",&nos);
printf("Enter no.of input symbols:");
scanf("%d",&noi);
printf("Enter input symbols:");
scanf("%s",input_symb);
printf("Enter no.of finals:");
scanf("%d",&nof);
printf("Enter finals states:");
for(i=0;i<nof;i++)
scanf("%d",&finals[i]);
printf("Enter transition table:\n");
for(i=0;i<nos;i++)
{
for(j=0;j<noi;j++)
{
printf("d(q%d,%c)=",
i,input_symb[j]);
scanf("%d",&trans[i][j]);
}
}
}
void show_trans()
{
int i,j;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={");
for(i=0;i<nof;i++)
printf("q%d,",finals[i]);
printf("\b}\nd:\n\t");
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",trans[i][j]);
printf("\n");
}
}
void check()
{
int i,j,curr;
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,input_str+i);
curr = trans[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
for(i=0;i<nof;i++)
{
if(finals[i]==curr)
{
printf("Accept\n");
return;
}
}
printf("Reject\n");
}
int main()
{
int ch;
while(1)
{
printf("1.Read DFA\n2.Show Transition Table\n3.Check acceptance of given string\n4.Exit\n");
printf("Enter choice (1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1:
read_dfa();
break;
case 2:
show_trans();
break;
case 3:
check();
break;
case 4:
exit(0);
}
}
return 0;
}
---------------------------------------------
Q) WRITE A PROGRAM TO IMPLEMENT DFA DRIVER FOR THE LANGUAGE L="SET OF ALL STRING THAT STARTS WITH A,ENDING WITH B " OVER{A,B}.
--->
#include<stdio.h>
int nos=4;
int noi=2;
char input_symb[]={'a','b'};
int nof=1,final=2;
int d[][2]={{1,3},{1,2},{1,2},{3,3}};
char input_str[100];
int main()
{
int i,j,curr;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={q%d}\nd:\n\t",final);
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",d[i][j]);
printf("\n");
}
do
{
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,
input_str+i);
curr=d[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
if(curr==final)
printf("Accept\n");
else
printf("Reject\n");
printf("Continue Y(1)/N(0)?");
scanf("%d",&j);
}while(j==1);
return 0;
}
----------------------------------------
Q) WRITE A PROGRAM TO IMPLEMENT DFA DRIVER FOR THE LANGUAGE L="SET OF ALL STRING THAT CONTAINING 101 AS SUBSTRING" OVER{0,1}.
--->
#include<stdio.h>
int nos=4;
int noi=2;
char input_symb[]={'0','1'};
int nof=1,final=3;
int d[][2]={{0,1},{2,1},{0,3},{3,3}};
char input_str[100];
int main()
{
int i,j,curr;
printf("M=(Q,E,d,q0,F)\n");
printf("Q={");
for(i=0;i<nos;i++)
printf("q%d,",i);
printf("\b}\nE={");
for(i=0;i<noi;i++)
printf("%c,",input_symb[i]);
printf("\b}\nq0=q0\nF={q%d}\nd:\n\t",final);
for(i=0;i<noi;i++)
printf("%c\t",input_symb[i]);
printf("\n");
for(i=0;i<nos;i++)
{
printf("q%d\t",i);
for(j=0;j<noi;j++)
printf("q%d\t",d[i][j]);
printf("\n");
}
do
{
printf("Enter input string:");
scanf("%s",input_str);
curr = 0;
for(i=0;input_str[i]!='\0';i++)
{
printf("d(q%d,%s)\n",curr,
input_str+i);
curr=d[curr][input_str[i]-input_symb[0]];
}
printf("q%d\n",curr);
if(curr==final)
printf("Accept\n");
else
printf("Reject\n");
printf("Continue Y(1)/N(0)?");
scanf("%d",&j);
}while(j==1);
return 0;
}
--------------------------------------------------------------------------------------
DEMAND PAGING
FIFO
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING FIFO PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FALUTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
PAGE REFERENCE STRING: 3,4,5,6,3,4,7,3,4,5,6,7,2,4,6.
--->
#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;
}
------------------------------------------------------------------------------------------
LFU
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING LFU PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FAULTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
PAGE REFERENCE STRING - 3,4,5,4,3,4,7,2,4,5,6,7,2,4,6.
--->
#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_lfu(int sp)
{
int i,min_i,min=9999;
i=sp;
do
{
if(count[i]<min)
{
min = count[i];
min_i = i;
}
i=(i+1)%n;
}while(i!=sp);
return min_i;
}
void lfu()
{
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_lfu(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();
lfu();
disp();
return 0;
}
----------------------------------------------------------------------------------------
LRU
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING LRU(USING COUNTER) PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FAULTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
PAGE REFERENCE STRING - 12,15,12,18,6,8,11,12,19,12,6,8,12,15,19,8.
---->
#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;
}
------------------------------------------------------------------------------------------
MFU
Q)WRITE THE SIMULATION PROGRAM TO IMPLEMENT DEMAND PAGING USING MFU PAGE REPLACEMENT ALGORITHM. ASSUME THE MEMORY OF "n" FRAMES. SHOW THE CONTENTS OF PAGE AFTER EVERY PAGE REPLACEMENT IN A FRAME AND AT END SHOW THE TOTAL NUMBER OF PAGE FAULTS ACCORDINGLY. INPUT THE FOLLOWING PAGE REFERENCE STRING.
PAGE REFERENCE STRING - 8,5,7,8,5,7,2,3,7,3,5,9,4,6,2.
----->
#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; }
-------------------------------------------------------------------------------------
0 Comments