Slip solution operating system-I

Q.1 Write the simulation program to implement demand paging and show the page scheduling and
total number of page faults according to the LFU page replacement algorithm. Assume the memory
of n frames. 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;
}

Output:

Enter no.of frames:2

Enter no.of references:15

Enter reference string:

[0]= 3,4,5,4,3,4,7,2,4,5,6,7,2,4,6

[1]=[2]=[3]=[4]=[5]=[6]=[7]=[8]=[9]=[10]=[11]=[12]=[13]=[14]= 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3

Total Page Faults: 1

Q.2 Write a C program to implement the shell which displays the command prompt “myshell$”. It
accepts the command, tokenize the command line and execute it by creating the child process. Also
implement the additional command ‘typeline’ as typeline +n filename :- To print first n lines in the file.
typeline -a filename :- To print all lines in the file.
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include <unistd.h>
int make_toks(char *s, char *tok[]) {
int i = 0;
char *p;
p = strtok(s, " ");
while(p != NULL) {
tok[i++] = p;
p = strtok(NULL, " ");
}
tok[i] = NULL;
return i;
}
void typeline(char *op, char *fn) {
int fh,
i,
j,
n;
char c;
fh = open(fn, O_RDONLY);
if(fh == -1) {
printf("File %s not found.\n", fn);
return;
}
if(strcmp(op, "a") == 0) {
while(read(fh, &c, 1) > 0)
printf("%c", c);
close(fh);
return;
}
n = atoi(op);
if(n > 0) {
i = 0;
while(read(fh, &c, 1) > 0) {
printf("%c", c);
if(c == '\n') i++;
if(i == n) break;
}
}
if(n < 0) {
i = 0;
while(read(fh, &c, 1) > 0) {
if(c == '\n') i++;
}
lseek(fh, 0, SEEK_SET);
j = 0;
while(read(fh, &c, 1) > 0) {
if(c == '\n') j++;
if(j == i+n+1) break;
}
while(read(fh, &c, 1) > 0) {
printf("%c", c);
}
}
close(fh);
}
int main() {
char buff[80],
*args[10];
while(1) {
printf ("\n");
printf("\nmyshell$ ");
fgets(buff, 80, stdin);
buff[strlen(buff)-1] = '\0';
int n = make_toks(buff, args);
switch (n) {
case 1:
if(strcmp(args[0], "exit") == 0)
exit(1);
if (!fork())
execlp (args [0], args[0], NULL);
break;
case 2:
if (!fork ())
execlp (args [0], args[0], args[1], NULL);
break;
case 3:
if (strcmp(args[0], "typeline") == 0)
typeline (args[1], args[2]);
else {
if (!fork ())
execlp (args [0], args[0], args[1], args[2], NULL);
}
break;
case 4:
if (!fork ())
execlp (args [0], args [0], args [1], args [2], args [3], NULL);
break;
}
}
return 0;
}

Output:
myshell$ typeline a text.txt
pune
kolkata
doremon
mumbai
vadapav
chandigarh
pune
prisonbreak
pogo
misalpav
gogo
pune
\0
myshell$ typeline 3 text.txt
pune
kolkata
doremon
myshell$ typeline -5 text.txt
pogo
misalpav
gogo
pune

Q. Write the simulation program for demand paging and show the page scheduling and total number
of page faults according the FIFO page replacement algorithm. Assume the memory of n frames.
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;
}

Output:

Enter no.of frames:2

Enter no.of references:2
Enter reference string:
[0]=3, 4, 5, 6, 3, 4, 7, 3, 4, 5, 6, 7, 2, 4, 6
[1]= 3 0
3
Total Page Faults: 1
Q. Write a program to implement the shell. It should display the command prompt “myshell$”.
Tokenize the command line and execute the given command by creating the child process.
Additionally it should interpret the following ‘list’ commands as myshell$ list f dirname :- To print
names of all the files in current directory. myshell$ list n dirname :- To print the number of all entries
in the current directory
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>

void make_toks(char *s, char *tok[])

{
int i=0;
char *p;

p = strtok(s," ");
while(p!=NULL)
{
tok[i++]=p;
p=strtok(NULL," ");
}

tok[i]=NULL;
}

void list(char *dn, char op)

{
DIR *dp;
struct dirent *entry;
int dc=0,fc=0;

dp = opendir(dn);
if(dp==NULL)
{
printf("Dir %s not found.\n",dn);
return;
}

switch(op)
{
case 'f':
while(entry=readdir(dp))
{
 if(entry->d_type==DT_REG)
printf("%s\n",entry->d_name);
}
break;
case 'n':
while(entry=readdir(dp))
{
if(entry->d_type==DT_DIR) dc++;
if(entry->d_type==DT_REG) fc++;
}

printf("%d Dir(s)\t%d File(s)\n",dc,fc);

break;
case 'i':
while(entry=readdir(dp))
{
if(entry->d_type==DT_REG)
printf("%s\t%d\n",entry->d_name,entry->d_fileno);
}
}

closedir(dp);
}

int main()
{
char buff[80],*args[10];
int pid;

while(1)
{
printf("myshell$");
fflush(stdin);
fgets(buff,80,stdin);
buff[strlen(buff)-1]='\0';
make_toks(buff,args);
if(strcmp(args[0],"list")==0)
list(args[2],args[1][0]);
else
{
pid = fork();
if(pid>0)
wait();
else
{
if(execvp(args[0],args)==-1)
printf("Bad command.\n");
}
}
}

return 0;
}

Q. Write the simulation program to implement demand paging and show the page scheduling and
total number of page faults according to the LRU (using counter method) page replacement
algorithm. Assume the memory of n frames. Reference String : 3,5,7,2,5,1,2,3,1,3,5,3,1,6,2

#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;
}

Q.2 Write a programto implement the toy shell. It should display the command prompt “myshell$”.
Tokenize the command line and execute the given command by creating the child process.
Additionally it should interpret the following commands. count c filename :- To print number of
characters in the file. count w filename :- To print number of words in the file. count l filename :- To
print number of lines in the file.
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void make_toks(char *s, char *tok[])

{
int i=0;
char *p;

p = strtok(s," ");
while(p!=NULL)
{
tok[i++]=p;
p=strtok(NULL," ");
}

tok[i]=NULL;
}

void count(char *fn, char op)

{
int fh,cc=0,wc=0,lc=0;
char c;

fh = open(fn,O_RDONLY);
if(fh==-1)
{
printf("File %s not found.\n",fn);
return;
}

while(read(fh,&c,1)>0)
{
if(c==' ') wc++;
else if(c=='\n')
{
wc++;
lc++;
}
cc++;
}

close(fh);

switch(op)
{
case 'c':
printf("No.of characters:%d\n",cc);
break;
case 'w':
printf("No.of words:%d\n",wc);
 break;
case 'l':
printf("No.of lines:%d\n",lc);
break;
}
}

int main()
{
char buff[80],*args[10];
int pid;

while(1)
{
printf("myshell$");
fflush(stdin);
fgets(buff,80,stdin);
buff[strlen(buff)-1]='\0';
make_toks(buff,args);
if(strcmp(args[0],"count")==0)
count(args[2],args[1][0]);
else
{
pid = fork();
if(pid>0)
wait();
else
{
if(execvp(args[0],args)==-1)
printf("Bad command.\n");
}
}
}

return 0;
}

Q.1 Write the simulation program for demand paging and show the page scheduling and total
number of page faults according the MFU page replacement algorithm. Assume the memory of n
frames. 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;
}

Q. Write a program to implement the shell. It should display the command prompt “myshell$”.
Tokenize the command line and execute the given command by creating the child process.
Additionally it should interpret the following commands. myshell$ search a filename pattern :- To
search all the occurrence of pattern in the file. myshell$ search c filename pattern :- To count the
number of occurrence of pattern in the file.
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void make_toks(char *s, char *tok[])

{
int i=0;
char *p;

p = strtok(s," ");
while(p!=NULL)
{
tok[i++]=p;
p=strtok(NULL," ");
}
 tok[i]=NULL;
}

void search(char *fn, char op, char *pattern)

{
int fh,count=0,i=0,j=0;
char buff[255],c,*p;

fh = open(fn,O_RDONLY);
if(fh==-1)
{
printf("File %s Not Found\n",fn);
return;
}

switch(op)
{
case 'f':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
j=0;
i++;
if(strstr(buff,pattern))
{
printf("%d: %s",i,buff);
break;
}
}
}
break;
case 'c':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
j=0;
p = buff;
while(p=strstr(p,pattern))
{
count++;
p++;
}
}
 }
printf("Total No.of Occurrences = %d\n",count);
break;
case 'a':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
j = 0;
i++;
if(strstr(buff,pattern))
printf("%d: %s",i,buff);
}
}
}//switch
close(fh);
}//search

int main()
{
char buff[80],*args[10];
int pid;

while(1)
{
printf("myshell$");
fflush(stdin);
fgets(buff,80,stdin);
buff[strlen(buff)-1]='\0';
make_toks(buff,args);
if(strcmp(args[0],"search")==0)
search(args[3],args[1][0],args[2]);
else
{
pid = fork();
if(pid>0)
wait();
else
{
if(execvp(args[0],args)==-1)
printf("Bad command.\n");
}
}
}

return 0;
}
Q.2 Write a program to implement the shell. It should display the command prompt “myshell$”.
Tokenize the command line and execute the given command by creating the child process.
Additionally it should interpret the following commands. myshell$ search f filename pattern :- To
display first occurrence of pattern in the file. myshell$ search c filename pattern :- To count the
number of occurrence of pattern in the file.
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void make_toks(char *s, char *tok[])

{
int i=0;
char *p;

p = strtok(s," ");
while(p!=NULL)
{
tok[i++]=p;
p=strtok(NULL," ");
}

tok[i]=NULL;
}

void search(char *fn, char op, char *pattern)

{
int fh,count=0,i=0,j=0;
char buff[255],c,*p;

fh = open(fn,O_RDONLY);
if(fh==-1)
{
printf("File %s Not Found\n",fn);
return;
}

switch(op)
{
case 'f':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
 j=0;
i++;
if(strstr(buff,pattern))
{
printf("%d: %s",i,buff);
break;
}
}
}
break;
case 'c':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
j=0;
p = buff;
while(p=strstr(p,pattern))
{
count++;
p++;
}
}
}
printf("Total No.of Occurrences = %d\n",count);
break;
case 'a':
while(read(fh,&c,1))
{
buff[j++]=c;
if(c=='\n')
{
buff[j]='\0';
j = 0;
i++;
if(strstr(buff,pattern))
printf("%d: %s",i,buff);
}
}
}//switch
close(fh);
}//search

int main()
{
char buff[80],*args[10];
int pid;
while(1)
{
printf("myshell$");
fflush(stdin);
fgets(buff,80,stdin);
buff[strlen(buff)-1]='\0';
make_toks(buff,args);
if(strcmp(args[0],"search")==0)
search(args[3],args[1][0],args[2]);
else
{
pid = fork();
if(pid>0)
wait();
else
{
if(execvp(args[0],args)==-1)
printf("Bad command.\n");
}
}
}

return 0;
}

Q.Write the simulation program for Round Robin scheduling for given time quantum. The arrival time
and first CPU-burst of different jobs should be input to the system. Accept no. of Processes, arrival
time and burst time. The output should give the Gantt chart, turnaround time and waiting time for
each process. Also display the average turnaround time and average waiting time. #include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct process_info

{
char pname[20];
int at,bt,ct,bt1;
struct process_info *next;
}NODE;

int n,ts;
NODE *first,*last;

void accept_info()
{
NODE *p;
int i;

printf("Enter no.of process:");

scanf("%d",&n);
for(i=0;i<n;i++)
{
p = (NODE*)malloc(sizeof(NODE));

printf("Enter process name:");

scanf("%s",p->pname);

printf("Enter arrival time:");

scanf("%d",&p->at);

printf("Enter first CPU burst time:");

scanf("%d",&p->bt);

p->bt1 = p->bt;

p->next = NULL;

if(first==NULL)
first=p;
else
last->next=p;

last = p;
}

printf("Enter time slice:");

scanf("%d",&ts);
}

void print_output()
{
NODE *p;
float avg_tat=0,avg_wt=0;

printf("pname\tat\tbt\tct\ttat\twt\n");

p = first;
while(p!=NULL)
{
int tat = p->ct-p->at;
int wt = tat-p->bt;

avg_tat+=tat;
avg_wt+=wt;

printf("%s\t%d\t%d\t%d\t%d\t%d\n",
p->pname,p->at,p->bt,p->ct,tat,wt);

p=p->next;
}

printf("Avg TAT=%f\tAvg WT=%f\n",

avg_tat/n,avg_wt/n);
}
void print_input()
{
NODE *p;

p = first;

printf("pname\tat\tbt\n");
while(p!=NULL)
{
printf("%s\t%d\t%d\n",
p->pname,p->at,p->bt1);
p = p->next;
}
}

void sort()
{
NODE *p,*q;
int t;
char name[20];

p = first;
while(p->next!=NULL)
{
q=p->next;
while(q!=NULL)
{
if(p->at > q->at)
{
strcpy(name,p->pname);
strcpy(p->pname,q->pname);
strcpy(q->pname,name);

t = p->at;
p->at = q->at;
q->at = t;

t = p->bt;
p->bt = q->bt;
q->bt = t;

t = p->ct;
p->ct = q->ct;
q->ct = t;

t = p->bt1;
p->bt1 = q->bt1;
q->bt1 = t;
}

q=q->next;
}
 p=p->next;
}
}

int time;

int is_arrived()
{
NODE *p;

p = first;
while(p!=NULL)
{
if(p->at<=time && p->bt1!=0)
return 1;

p=p->next;
}

return 0;
}

NODE * delq()
{
NODE *t;

t = first;
first = first->next;
t->next=NULL;

return t;
}

void addq(NODE *t)

{
last->next = t;
last = t;
}

struct gantt_chart
{
int start;
char pname[30];
int end;
}s[100],s1[100];

int k;

void rr()
{
int prev=0,n1=0;
NODE *p;

while(n1!=n)
{
if(!is_arrived())
{
time++;
s[k].start = prev;
strcpy(s[k].pname,"*");
s[k].end = time;
k++;
prev=time;
}
else
{
p = first;
while(1)
{
if(p->at<=time && p->bt1!=0)
break;

p = delq();
addq(p);
p = first;
}

if(p->bt1<=ts)
{
time+=p->bt1;
p->bt1=0;
}
else
{
time+=ts;
p->bt1-=ts;
}

p->ct = time;

s[k].start = prev;
strcpy(s[k].pname,p->pname);
s[k].end = time;

k++;
prev = time;

if(p->bt1==0) n1++;

p = delq();
addq(p);
}

print_input();
}
}

void print_gantt_chart()
{
int i,j,m;

s1[0] = s[0];

for(i=1,j=0;i<k;i++)
{
if(strcmp(s[i].pname,s1[j].pname)==0)
s1[j].end = s[i].end;
else
s1[++j] = s[i];
}

printf("%d",s1[0].start);
for(i=0;i<=j;i++)
{
m = (s1[i].end - s1[i].start);

for(k=0;k<m/2;k++)
printf("-");

printf("%s",s1[i].pname);

for(k=0;k<(m+1)/2;k++)
printf("-");

printf("%d",s1[i].end);
}
}

int main()
{
accept_info();
sort();
rr();
print_output();
print_gantt_chart();

return 0;
}