OPERATING SYSTEMS AND LINUX PROGRAMMING LAB
List of Experiments:
1. Simulate
the following CPU scheduling algorithms
a) Round Robin b) SJF c)
FCFS d)Priority
2. Multiprogramming Memory management Implementation of fork (),
wait (), exec () and exit (),
system calls
3.
Simulate the following
a) Multiprogramming with
a fixed number of tasks (MFT)
b) Multiprogramming with
a variable number of tasks (MVT)
4. Simulate the Banker’s algorithm for Dead Lock Avoidance
5. Simulate the Banker’s algorithm for Dead Lock Prevention
6.
Simulate the following Page Replacement algorithms
a) FIFO b) LRU c) LFU
7. Simulate the following File allocation
strategies
a) Sequenced b) Indexed c) Linked
EXERCISE-1
AIM: Simulate the following CPU
scheduling algorithms
a) ROUND ROBIN:
DESCRIPTION:
·
Round
Robin is the preemptive process scheduling algorithm.
·
Each
process is provided a fix time to execute, it is called a quantum.
·
Once
a process is executed for a given time period, it is preempted and other
process executes for a given time period.
·
Context
switching is used to save states of preempted processes.
PROGRAM:
/* C
Program to implement Round Robin CPU Scheduling Algorithm */
#include<stdio.h>
int main()
{
int
count,j,n,time,remain,flag=0,time_quantum;
int
wait_time=0,turnaround_time=0,at[10],bt[10],rt[10];
printf("Enter
Total Process:\t ");
scanf("%d",&n);
remain=n;
for(count=0;count<n;count++)
{
printf("Enter
Arrival Time and Burst Time for Process Process Number %d :",count+1);
scanf("%d",&at[count]);
scanf("%d",&bt[count]);
rt[count]=bt[count];
}
printf("Enter
Time Quantum:\t");
scanf("%d",&time_quantum);
printf("\n\nProcess\t|Turnaround
Time|Waiting Time\n\n");
for(time=0,count=0;remain!=0;)
{
if(rt[count]<=time_quantum
&& rt[count]>0)
{
time+=rt[count];
rt[count]=0;
flag=1;
}
else
if(rt[count]>0)
{
rt[count]-=time_quantum;
time+=time_quantum;
}
if(rt[count]==0
&& flag==1)
{
remain--;
printf("P[%d]\t|\t%d\t|\t%d\n",count+1,time-at[count],time-at[count]-bt[count]);
wait_time+=time-at[count]-bt[count];
turnaround_time+=time-at[count];
flag=0;
}
if(count==n-1)
count=0;
else
if(at[count+1]<=time)
count++;
else
count=0;
}
printf("\nAverage
Waiting Time= %f\n",wait_time*1.0/n);
printf("Avg
Turnaround Time = %f",turnaround_time*1.0/n);
return 0;
}
OUTPUT:
Enter
Total Process: 4
Enter
Arrival Time and Burst Time for Process Process Number 1 : 0
9
Enter
Arrival Time and Burst Time for Process Process Number 2 : 1
5
Enter
Arrival Time and Burst Time for Process Process Number 3 : 2
3
Enter
Arrival Time and Burst Time for Process Process Number 4 : 3
4
Enter
Time Quantum: 5
Process
Turnaround Time Waiting Time
P[2] 9 4
P[3] 11 8
P[4]
14 10
P[1] 21 12
Average Waiting Time=
8.500000
Avg Turnaround Time =
13.70000
|
b) SJF:
DESCRIPTION:
·
This
is also known as shortest job first, or SJF
·
This
is a non-preemptive, pre-emptive scheduling algorithm.
·
Best
approach to minimize waiting time.
·
Easy
to implement in Batch systems where required CPU time is known in advance.
·
Impossible
to implement in interactive systems where required CPU time is not known.
·
The
processer should know in advance how much time process will take.
PROGRAM:
/* C Program to implement
SJF CPU Scheduling Algorithm */
#include<stdio.h>
void main()
{
int
bt[20],p[20],wt[20],tat[20],i,j,n,total=0,pos,temp;
float
avg_wt,avg_tat;
printf("Enter
number of process:");
scanf("%d",&n);
printf("\nEnter
Burst Time:\n");
for(i=0;i<n;i++)
{
printf("p%d:",i+1);
scanf("%d",&bt[i]);
p[i]=i+1;
}
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(bt[j]<bt[pos])
pos=j;
}
temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;
temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}
wt[0]=0;
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];
total+=wt[i];
}
avg_wt=(float)total/n;
total=0;
printf("\nProcess\t Burst
Time \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
total+=tat[i];
printf("\np%d\t\t %d\t\t %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
}
avg_tat=(float)total/n;
printf("\n\nAverage
Waiting Time=%f",avg_wt);
printf("\nAverage
Turnaround Time=%f\n",avg_tat);
}
OUTPUT:
Enter number of
process: 4
Enter Burst Time:
P1:4
P2:8
P3:3
P4:7
Process Burst
Time
Waiting Time Turnaround
Time
P3 3 0 3
P1 4 3 7
P4 7 7 14
P2 8 14 22
Average Waiting
Time=6.000000
Average Turnaround
Time=11.500000
c) FCFS:
DESCRIPTION:
PROGRAM:
/* C Program to implement FCFS CPU
Scheduling Algorithm */
#include<stdio.h>
main()
{
int
n,a[10],b[10],t[10],w[10],g[10],i,m;
float
att=0,awt=0;
for(i=0;i<10;i++)
{
a[i]=0; b[i]=0; w[i]=0;
g[i]=0;
}
printf("enter
the number of process");
scanf("%d",&n);
printf("enter
the burst times");
for(i=0;i<n;i++)
scanf("%d",&b[i]);
printf("\nenter the
arrival times");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
g[0]=0;
for(i=0;i<10;i++)
g[i+1]=g[i]+b[i];
for(i=0;i<n;i++)
{
w[i]=g[i]-a[i];
t[i]=g[i+1]-a[i];
awt=awt+w[i];
att=att+t[i];
}
awt =awt/n;
att=att/n;
printf("\n\tprocess\twaiting
time\tturn arround time\n");
for(i=0;i<n;i++)
{
printf("\tp%d\t\t%d\t\t%d\n",i,w[i],t[i]);
}
printf("the
average waiting time is %f\n",awt);
printf("the
average turn around time is %f\n",att);
}
OUTPUT:
enter the number of
process 4
enter the burst times
4
9
8
3
enter the arrival times
0
2
4
3
process waiting
time turn arround time
p0 0 4
p1 2 11
p2 9 17
p3 18 21
the average waiting time
is 7.250000
the average turn around
time is 13.250000
d) PRIORITY:
DESCRIPTION:
·
Priority
scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
·
Each
process is assigned a priority. Process with highest priority is to be
executed first and so on.
·
Processes
with same priority are executed on first come first served basis.
·
Priority
can be decided based on memory requirements, time requirements or any other
resource requirement.
PROGRAM:
/* C Program to implement
Priority CPU Scheduling Algorithm */
int main()
{
int
bt[20],p[20],wt[20],tat[20],pr[20],i,j,n,total=0,pos,temp,avg_wt,avg_tat;
printf("Enter
Total Number of Process:");
scanf("%d",&n);
printf("\nEnter
Burst Time and Priority\n");
for(i=0;i<n;i++)
{
printf("\nP[%d]\n",i+1);
printf("Burst
Time:");
scanf("%d",&bt[i]);
printf("Priority:");
scanf("%d",&pr[i]);
p[i]=i+1;
}
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(pr[j]<pr[pos])
pos=j;
}
temp=pr[i];
pr[i]=pr[pos];
pr[pos]=temp;
temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;
temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}
wt[0]=0;
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];
total+=wt[i];
}
avg_wt=total/n;
total=0;
printf("\nProcess\t Burst
Time \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
total+=tat[i];
printf("\nP[%d]\t\t %d\t\t %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
}
avg_tat=total/n;
printf("\n\nAverage
Waiting Time=%d",avg_wt);
printf("\nAverage
Turnaround Time=%d\n",avg_tat);
return 0;
}
OUTPUT:
Enter Total Number
of Process: 4
Enter Burst Time
and Priority:
P[1]
Burst Time: 6
Priority:3
P[2]
Burst Time: 2
Priority:2
P[3]
Burst Time: 14
Priority:1
P[4]
Burst Time: 6
Priority:4
Process Burst Time Waiting Time Turnaround Time
P[3] 14 0 14
P[2] 2 14 16
P[1] 6 16 22
P[4] 6 22 28
Average Waiting
Time=13
Average Turnaround
Time=20
EXERCISE-2
AIM:
Multiprogramming Memory management Implementation of
fork(),wait(),exec() and exit(),system calls
DESCRIPTION:
FORK():
Fork system call use
for creates a new process, which is called child process, which runs concurrently with
process (which process called system call fork) and this process is
called parent process. After a new
child process created, both processes will execute the next instruction
following the fork() system call. A child process uses the same pc(program
counter), same CPU registers, same open files which use in the parent
process.
EXEC():
The exec family of
functions replaces the current running process with a new process. It can be
used to run a C program by using another C program. It comes under the header
file unistd.h. There are many members in the exec
family which are shown below with examples.
·
execvp :
Using this command, the created child process does not have to run the same
program as the parent process does. The exec type
system calls allow a process to run any program files, which include a binary
executable or a shell script .
Syntax:
int execvp (const char
*file, char *const argv[]);
file: points to the file name associated with the file being
executed.
argv: is a null terminated array of character pointers.
·
execv : This is very similar to execvp() function in terms of
syntax as well. The syntax of execv() is as
shown below:
Syntax:
int execv(const char
*path, char *const argv[]);
path: should
point to the path of the file being executed.
argv[]: is a null terminated array of character pointers.
·
execlp and
execl : These two also serve the same purpose but the
syntax of of them are a bit different which is as shown below:Syntax:
int execlp(const char
*file, const char *arg,.../* (char *)
NULL */);
int execl(const char
*path, const char *arg,.../* (char *)
NULL */);
·
execvpe and
execle : These two also serve the same purpose but the
syntax of them are a bit different from all the above members of exec family.
The synatxes of both of them are shown below :
Syntax:
int execvpe(const char
*file, char *const argv[],char *const envp[]);
Syntax:
int execle(const char
*path, const char *arg, .../*, (char *) NULL,
char * const envp[] */);
WAIT()
:
A call to wait() blocks
the calling process until one of its child processes exits or a signal is
received. After child process terminates, parent continues its
execution after wait system call instruction.
Child process may terminate due to any of these:
·
It calls exit();
·
It returns (an int) from main
·
It receives a signal (from the OS or another
process) whose default action is to terminate.
It terminates the calling process without executing the rest code
which is after the exit() function.
 
FORK():
PROGRAM:
/* C Program to implement Fork() system calls */
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
void forkexample()
{
if (fork() == 0)
printf("Hello
from Child!\n");
else
printf("Hello
from Parent!\n");
}
int main()
{
forkexample();
return 0;
}
OUTPUT:
Hello from Child!
Hello from Parent!
EXEC():
/*
C Program to implement Exec() system calls */
PROGRAM:
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/wait.h>
int main()
{
pid_t pid;
int ret = 1;
int status;
pid = fork();
if (pid == -1)
{
printf("can't
fork, error occured\n");
exit(EXIT_FAILURE);
}
else if (pid == 0)
{
printf("child
process, pid = %u\n",getpid());
execv("ls",argv_list);
exit(0);
}
else{
printf("parent process, pid =
%u\n",getppid());
if (waitpid(pid, &status,
0) > 0)
{
if (WIFEXITED(status) &&
!WEXITSTATUS(status))
printf("program
execution successfull\n");
else
if (WIFEXITED(status) && WEXITSTATUS(status))
{
if (WEXITSTATUS(status) ==
127)
{
printf("execv
failed\n");
}
else
printf("program
terminated normally,"
"
but returned a non-zero
status\n");
}
else
printf("program didn't
terminate
normally\n");
}
else
{
printf("waitpid() failed\n");
}
exit(0);
}
return 0;
}
OUTPUT:
parent process, pid = 11523
child process, pid = 14188
Program execution successfull
WAIT()
:
PROGRAM:
/*
C Program to implement Wait() system
calls */
#include<stdio.h>
#include<stdlib.h>
#include<sys/wait.h>
#include<unistd.h>
int main()
{
pid_t cpid;
if (fork()== 0)
exit(0);
else
cpid =
wait(NULL);
printf("Parent pid = %d\n",
getpid());
printf("Child pid = %d\n",
cpid);
return 0;
}
EXIT():
PROGRAM:
/* C Program to implement Exit() system calls */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
printf("START");
exit(0);
printf("End of program");
}
OUTPUT:
START
EXERCISE-3
AIM: Simulate the
following
a) Multiprogramming
with a fixed number of tasks (MFT)
b) Multiprogramming
with a variable number of tasks (MVT)
DESCRIPTION:
MFT
: Multiprogramming with a Fixed number of Tasks is one of the old memory management
techniques in which the memory is partitioned into fixed size partitions and
each job is assigned to a partition. The memory assigned to a partition does
not change.
MVT :
Multiprogramming with a Variable number of Tasks is the memory management
technique in which each job gets just the amount of memory it needs. That is,
the partitioning of memory is dynamic and changes as jobs enter and leave the
system. MVT is a more ``efficient'' user of resources. MFT suffers with the
problem of internal fragmentation and MVT suffers with external
fragmentation.
PROGRAM
/*
C Program to implement Multiprogramming
with a fixed number of tasks (MFT)*/
#include<stdio.h>
#include<conio.h>
main()
{
int ms, bs, nob, ef,n, mp[10],tif=0;
int i,p=0;
clrscr();
printf("Enter the total memory available (in Bytes) --
");
scanf("%d",&ms);
printf("Enter the block size (in Bytes) -- ");
scanf("%d", &bs);
nob=ms/bs;
ef=ms - nob*bs;
printf("\nEnter the number of processes -- ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter memory required for process %d (in Bytes)--
",i+1);
scanf("%d",&mp[i]);
}
printf("\nNo. of Blocks available in memory --
%d",nob);
printf("\n\nPROCESS\tMEMORY REQUIRED\t ALLOCATED\tINTERNAL
FRAGMENTATION");
for(i=0;i<n && p<nob;i++)
{
printf("\n %d\t\t%d",i+1,mp[i]);
if(mp[i] > bs)
printf("\t\tNO\t\t---");
else
{
printf("\t\tYES\t%d",bs-mp[i]);
tif = tif + bs-mp[i];
p++;
}
}
if(i<n)
printf("\nMemory is Full, Remaining Processes cannot be
accomodated");
printf("\n\nTotal Internal Fragmentation is %d",tif);
printf("\nTotal External Fragmentation is %d",ef);
getch();
}
OUTPUT:
Enter the total memory available (in Bytes) -- 1000
Enter the block size (in Bytes)-- 300
Enter the number of processes – 5
Enter memory required for process 1 (in Bytes) -- 275
Enter memory required for process 2 (in Bytes) -- 400
Enter memory required for process 3 (in Bytes) -- 290
Enter memory required for process 4 (in Bytes) -- 293
Enter memory required for process 5 (in Bytes) -- 100
No. of Blocks available in memory -- 3
PROCESS MEMORY-REQUIRED ALLOCATED INTERNAL-FRAGMENTATION
1
275
YES
25
2
400
NO
-----
3
290
YES
10
4
293
YES
7
Memory is Full, Remaining Processes cannot be accommodated
Total Internal Fragmentation is 42
Total External Fragmentation is 100
MVT :
PROGRAM:
/*
C Program to implement Multiprogramming
with a variable number of tasks (MVT)*/
#include<stdio.h>
#include<conio.h>
main()
{
int ms,mp[10],i, temp,n=0;
char ch = 'y';
clrscr();
printf("\nEnter the total memory available (in Bytes)--
");
scanf("%d",&ms);
temp=ms;
for(i=0;ch=='y';i++,n++)
{
printf("\nEnter memory required for process %d (in Bytes)
-- ",i+1);
scanf("%d",&mp[i]);
if(mp[i]<=temp)
{
printf("\nMemory is allocated for Process %d ",i+1);
temp = temp - mp[i];
}
else
{
printf("\nMemory is Full");
break;
}
printf("\nDo you want to continue(y/n) -- ");
scanf(" %c", &ch);
}
printf("\n\nTotal Memory Available -- %d", ms);
printf("\n\n\tPROCESS\t\t MEMORY ALLOCATED ");
for(i=0;i<n;i++)
printf("\n \t%d\t\t%d",i+1,mp[i]);
printf("\n\nTotal Memory Allocated is %d",ms-temp);
printf("\nTotal External Fragmentation is %d",temp);
getch();
}
OUTPUT
Enter the total memory available (in Bytes) -- 1000
Enter memory required for process 1 (in Bytes) -- 400
Memory is allocated for Process 1
Do you want to continue(y/n) -- y
Enter memory required for process 2 (in Bytes) -- 275
Memory is allocated for Process 2
Do you want to continue(y/n) -- y
Enter memory required for process 3 (in Bytes) -- 550
Memory is Full
Total Memory Available -- 1000
PROCESS MEMORY-ALLOCATED
1
400
2
275
Total Memory Allocated is 675
Total External Fragmentation is 325
EXERCISE-4
AIM:
Simulate the Banker’s algorithm for Dead Lock Avoidance
DESCRIPTION:
The banker’s algorithm is a resource
allocation and deadlock avoidance algorithm that tests for safety by
simulating the allocation for predetermined maximum possible amounts of all
resources, then makes an “s-state” check to test for possible activities,
before deciding whether allocation should be allowed to continue.
Following Data
structures are used to implement the Banker’s Algorithm:
Let ‘n’ be
the number of processes in the system and ‘m’ be the number
of resources types.
Available :
·
It is a 1-d array of size ‘m’ indicating
the number of available resources of each type.
·
Available[ j ] = k means there
are ‘k’ instances of resource type Rj
Max :
·
It is a 2-d array of size ‘n*m’ that
defines the maximum demand of each process in a system.
·
Max[ i, j ] = k means process Pi may
request at most ‘k’ instances of resource type Rj.
Allocation :
·
It is a 2-d array of size ‘n*m’ that
defines the number of resources of each type currently allocated to each
process.
·
Allocation[ i, j ] = k means
process Pi is currently allocated ‘k’ instances
of resource type Rj
Need :
·
It is a 2-d array of size ‘n*m’ that
indicates the remaining resource need of each process.
·
Need [ i, j ] = k means
process Pi currently allocated ‘k’ instances
of resource type Rj
·
Need [ i, j ] = Max [ i, j
] – Allocation [ i, j ]
PROGRAM:
/*
C Program to implement Dead Lock
Avoidance using Banker’s algorithm */
#include <stdio.h> #include <stdlib.h> int main() { int Max[10][10], need[10][10], alloc[10][10], avail[10], completed[10], safeSequence[10]; int p, r, i, j, process, count; count = 0; printf("Enter the no of processes : "); scanf("%d", &p); for(i = 0; i< p; i++) completed[i] = 0; printf("\n\nEnter the no of resources : "); scanf("%d", &r); printf("\n\nEnter the Max Matrix for each process : "); for(i = 0; i < p; i++) { printf("\nFor process %d : ", i + 1); for(j = 0; j < r; j++) scanf("%d", &Max[i][j]); } printf("\n\nEnter the allocation for each process : "); for(i = 0; i < p; i++) { printf("\nFor process %d : ",i + 1); for(j = 0; j < r; j++) scanf("%d", &alloc[i][j]); } printf("\n\nEnter the Available Resources : "); for(i = 0; i < r; i++) scanf("%d", &avail[i]); for(i = 0; i < p; i++) for(j = 0; j < r; j++) need[i][j] = Max[i][j] - alloc[i][j]; do { printf("\n Max matrix:\tAllocation matrix:\n"); for(i = 0; i < p; i++) { for( j = 0; j < r; j++) printf("%d ", Max[i][j]); printf("\t\t"); for( j = 0; j < r; j++) printf("%d ", alloc[i][j]); printf("\n"); } process = -1; for(i = 0; i < p; i++) { if(completed[i] == 0)//if not completed { process = i ; for(j = 0; j < r; j++) { if(avail[j] < need[i][j]) { process = -1; break; } } } if(process != -1) break; } if(process != -1) { printf("\nProcess %d runs to completion!", process + 1); safeSequence[count] = process + 1; count++; for(j = 0; j < r; j++) { avail[j] += alloc[process][j]; alloc[process][j] = 0; Max[process][j] = 0; completed[process] = 1; } } } while(count != p && process != -1); if(count == p) { printf("\nThe system is in a safe state!!\n"); printf("Safe Sequence : < "); for( i = 0; i < p; i++) printf("%d ", safeSequence[i]); printf(">\n"); } else printf("\nThe system is in an unsafe state!!"); }
OUTPUT:
Enter the no of processes : 5 Enter the no of resources : 3 Enter the Max Matrix for each process : For process 1 : 7 5 3 For process 2 : 3 2 2 For process 3 : 7 0 2 For process 4 : 2 2 2 For process 5 : 4 3 3 Enter the allocation for each process : For process 1 : 0 1 0 For process 2 : 2 0 0 For process 3 : 3 0 2 For process 4 : 2 1 1 For process 5 : 0 0 2 Enter the Available Resources : 3 3 2 Max matrix: Allocation matrix: 7 5 3 0 1 0 3 2 2 2 0 0 7 0 2 3 0 2 2 2 2 2 1 1 4 3 3 0 0 2 Process 2 runs to completion! Max matrix: Allocation matrix: 7 5 3 0 1 0 0 0 0 0 0 0 7 0 2 3 0 2 2 2 2 2 1 1 4 3 3 0 0 2 Process 3 runs to completion! Max matrix: Allocation matrix: 7 5 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 1 1 4 3 3 0 0 2 Process 4 runs to completion! Max matrix: Allocation matrix: 7 5 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 3 0 0 2 Process 1 runs to completion! Max matrix: Allocation matrix: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 3 0 0 2 Process 5 runs to completion! The system is in a safe state!! Safe Sequence : < 2 3 4 1 5 >
EXERCISE-5
AIM: Simulate the
Banker’s algorithm for Dead Lock Prevention
DESCRIPTION: We can prevent
Deadlock by eliminating any of the above four condition.
·
Eliminate Mutual Exclusion : It is not possible to dis-satisfy the
mutual exclusion because some resources, such as the tap drive and printer,
are inherently non-shareable.
·
Eliminate Hold and wait: Allocate
all required resources to the process before start of its execution, this way
hold and wait condition is eliminated but it will lead to low device
utilization.
·
Eliminate No Preemption: Preempt
resources from process when resources required by other high priority
process.
·
Eliminate Circular Wait: Each
resource will be assigned with a numerical number. A process can request for
the resources only in increasing order of numbering.
PROGRAM:
/*
C Program to implement Dead Lock
Prevention using Banker’s algorithm */
#include<stdio.h>
void
main()
{
int
max[10][10],a1[10][10],av[10],i,j,k,m,n,ne[10][10],flag=0;
printf("\nEnter the matrix
dimensions:");
scanf("%d%d",&m,&n);
printf("\n Enter the maximum
matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&max[i][j]);
}
}
printf("\n Enter allocated
matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a1[i][j]);
}
}
printf("\n The need matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
ne[i][j]=max[i][j]-a1[i][j];
printf("\t%d",ne[i][j]);
}
printf("\n");
}
printf("\n Enter available
matrix:\n");
for(i=0;i<n;i++)
scanf("%d",&av[i]);
printf("\n Maximum matrix\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("\t%d",max[i][j]);
}
printf("\n");
}
printf("\n Allocated matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("\t%d",a1[i][j]);
}
printf("\n");
}
printf("\n Available matrix:\n");
for(i=0;i<n;i++)
{
printf("%d\t",av[i]);
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(av[i]>=ne[i][j])
flag=1;
else
flag=0;
}
}
if(flag==0)
printf("\n Unsafe state");
else
printf("\n safe state");
}
OUTPUT:
Enter
the matrix dimensions:3 3
Enter
the maximum matrix:
3 6 8
4 3 3
3 4 4
Enter
allocated matrix:
2 2 3
2 0 3
1 2 4
The
need matrix:
1 4 5
2 3 0
2 2 0
Enter
available matix:
2 3 0
Maximum
matrix:
3 6 8
4 3 3
3 4 4
Allocated
matrix:
2 2 3
2 0 3
1 2 4
Available
matrix:
2 3 0
safe
state
EXERCISE-6
AIM:
Simulate the following Page Replacement algorithms
a) FIFO b)LRU c)LFU
DESCRIPTION:
a) FIFO :
This is the simplest page replacement algorithm.
In this algorithm, operating system keeps track of all pages in the memory in
a queue, oldest page is in the front of the queue. When a page needs to be
replaced page in the front of the queue is selected for removal.
PROGRAM:
/*
C Program to implement FIFO
Page Replacement algorithms */
#include<stdio.h>
int main()
{
int
i,j,n,a[50],frame[10],no,k,avail,count=0;
printf("\n
ENTER THE NUMBER OF PAGES:\n");
scanf("%d",&n);
printf("\n
ENTER THE PAGE NUMBER :\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\n
ENTER THE NUMBER OF FRAMES :");
scanf("%d",&no);
for(i=0;i<no;i++)
frame[i]=
-1;
j=0;
printf("\tref
string\t page frames\n");
for(i=1;i<=n;i++)
{
printf("%d\t\t",a[i]);
avail=0;
for(k=0;k<no;k++)
if(frame[k]==a[i])
avail=1;
if (avail==0)
{
frame[j]=a[i];
j=(j+1)%no;
count++;
for(k=0;k<no;k++)
printf("%d\t",frame[k]);
}
printf("\n");
}
printf("Page
Fault Is %d",count);
return
0;
}
OUTPUT:
ENTER THE NUMBER OF PAGES: 20
ENTER THE PAGE NUMBER
: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
7 0 1
ENTER THE NUMBER OF FRAMES : 3
Ref string Page frames
7 7 -1 -1
0 7 0 -1
1 7 0 1
2 2 0 1
0
3 2 3 1
0 2 3 0
4 4 3 0
2 4 2 0
3 4 2 3
0 0 2 3
3
2
1 0 1 3
2 0 1 2
0
1
7 7 1 2
0 7 0 2
1 7 0 1
Page Fault Is 15
b)LRU:
On a page fault, the frame that was least
recently used in replaced.
PROGRAM:
/*
C Program to implement LRU
Page Replacement algorithms */
#include<stdio.h>
main()
{
int q[20],p[50],c=0,c1,d,f,i,j,k=0,n,r,t,b[20],c2[20];
printf("Enter no of
pages:");
scanf("%d",&n);
printf("Enter the
reference string:");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("Enter no of
frames:");
scanf("%d",&f);
q[k]=p[k];
printf("\n\t%d\n",q[k]);
c++;
k++;
for(i=1;i<n;i++)
{
c1=0;
for(j=0;j<f;j++)
{
if(p[i]!=q[j])
c1++;
}
if(c1==f)
{
c++;
if(k<f)
{
q[k]=p[i];
k++;
for(j=0;j<k;j++)
printf("\t%d",q[j]);
printf("\n");
}
else
{
for(r=0;r<f;r++)
{
c2[r]=0;
for(j=i-1;j<n;j--)
{
if(q[r]!=p[j])
c2[r]++;
else
break;
}
}
for(r=0;r<f;r++)
b[r]=c2[r];
for(r=0;r<f;r++)
{
for(j=r;j<f;j++)
{
if(b[r]<b[j])
{
t=b[r];
b[r]=b[j];
b[j]=t;
}
}
}
for(r=0;r<f;r++)
{
if(c2[r]==b[0])
q[r]=p[i];
printf("\t%d",q[r]);
}
printf("\n");
}
}
}
printf("\nThe no of page faults is %d",c);
}
OUTPUT:
Enter no of pages:10
Enter the reference string:7 5 9 4 3 7 9 6 2 1
Enter no of frames:3
7
7 5
7 5 9
4 5 9
4 3 9
4 3 7
9 3 7
9 6 7
9 6 2
1 6 2
The no of page faults is 10
c) LFU:
Pages with a current copy on disk are first choice for
pages to be removed when more memory is needed. To facilitate Page Replacement Algorithms, a table of valid or invalid bits (also
called dirty bits) is maintained.
PROGRAM:
/*
C Program to implement LFU
Page Replacement algorithms */
OUTPUT
:
2 -1 -1 2 3 -1 2 3 -1 2 3 1 2 5 1 2 5 1 2 5 4 2 5 4 3 5 4 3 5 2 3 5 2 3 5 2 no of page faults : 4
EXERCISE-7
AIM: Simulate
the following File allocation strategies
a) SEQUENCED
DESCRIPTION:
Each file occupies a contiguous set of
blocks on the disk. For example, if a file requires n blocks and is given a
block b as the starting location, then the blocks assigned to the file will
be: b, b+1, b+2,……b+n-1. This means that given the starting
block address and the length of the file (in terms of blocks required), we
can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
·
Address of starting block
·
Length of the allocated portion.
PROGRAM:
/* C Program to implement Sequenced File allocation strategies */
#include < stdio.h>
#include<conio.h> void main() { int f[50], i, st, len, j, c, k, count = 0; clrscr(); for(i=0;i<50;i++) f[i]=0; printf("Files Allocated are : \n"); x: count=0; printf(“Enter starting block and length of files: ”); scanf("%d%d", &st,&len); for(k=st;k<(st+len);k++) if(f[k]==0) count++; if(len==count) { for(j=st;j<(st+len);j++) if(f[j]==0) { f[j]=1; printf("%d\t%d\n",j,f[j]); } if(j!=(st+len-1)) printf(” The file is allocated to disk\n"); } else printf(” The file is not allocated \n"); printf("Do you want to enter more file(Yes - 1/No - 0)"); scanf("%d", &c); if(c==1) goto x; else exit(); getch(); }
OUTPUT:
Files
Allocated are :
Enter
starting block and length of files:17
4
17 1
18 1
19 1
20 1
The file
is allocated to disk
Do you
want to enter more file(Yes - 1/No – 0)
1
Enter
starting block and length of files:21
3
21 1
22 1
23 1
The file
is allocated to disk
Do you
want to enter more file(Yes - 1/No – 0)
0
b)INDEXED :
A special block known as the Index block contains the pointers to all
the blocks occupied by a file. Each file has its own index block. The ith
entry in the index block contains the disk address of the ith file block. The
directory entry contains the address of the index block as shown in the image
PROGRAM:
/* C Program to implement Indexed
File allocation strategies */
#include<stdio.h>
#include<conio.h> #include<stdlib.h> void main() { int f[50], index[50],i, n, st, len, j, c, k, ind,count=0; clrscr(); for(i=0;i<50;i++) f[i]=0; x:printf("Enter the index block: "); scanf("%d",&ind); if(f[ind]!=1) { printf("Enter no of blocks needed and no of files for the index %d on the disk : \n", ind); scanf("%d",&n); } else { printf("%d index is already allocated \n",ind); goto x; } y: count=0; for(i=0;i<n;i++) { scanf("%d", &index[i]); if(f[index[i]]==0) count++; } if(count==n) { for(j=0;j<n;j++) f[index[j]]=1; printf("Allocated\n"); printf("File Indexed\n"); for(k=0;k<n;k++) printf("%d-------->%d : %d\n",ind,index[k],f[index[k]]); } else { printf("File in the index is already allocated \n"); printf("Enter another file indexed"); goto y; } printf("Do you want to enter more file(Yes - 1/No - 0)"); scanf("%d", &c); if(c==1) goto x; else exit(0); getch(); }
OUTPUT:
Enter the
index block: 5
Enter no
of blocks needed and no of files for the index 5 on the disk :
4
1 2
3 4
Allocated
File
Indexed
5----------->
1 :
1
5----------->
2 :
1
5----------->
3 :
1
5----------->
4 :
1
Do you
want to enter more file(Yes - 1/No - 0)
1
Enter the
index block: 4
4 index is already allocated
Enter the
index block: 6
Enter no
of blocks needed and no of files for the index 6 on the disk :
1
2
File in
the index is already allocated
Enter
another file indexed 6
Allocated
File
Indexed
6----------->
6 :
1
Do you
want to enter more file(Yes - 1/No - 0)
0
c)LINKED
:
Each file
is a linked list of disk blocks which need not be contiguous.
The disk blocks can be scattered anywhere on the disk. The directory entry contains a pointer to the
starting and the ending file block. Each block contains a pointer to the next
block occupied by the file.
PROGRAM:
/* C Program to implement Linked
File allocation strategies */
#include<stdio.h>
#include<conio.h> #include<stdlib.h> void main() { int f[50], p,i, st, len, j, c, k, a; clrscr(); for(i=0;i<50;i++) f[i]=0; printf("Enter how many blocks already allocated: "); scanf("%d",&p); printf("Enter blocks already allocated: "); for(i=0;i<p;i++) { scanf("%d",&a); f[a]=1; } x: printf("Enter index starting block and length: "); scanf("%d%d", &st,&len); k=len; if(f[st]==0) { for(j=st;j<(st+k);j++) { if(f[j]==0) { f[j]=1; printf("%d-------->%d\n",j,f[j]); } else { printf("%d Block is already allocated \n",j); k++; } } } else printf("%d starting block is already allocated \n",st); printf("Do you want to enter more file(Yes - 1/No - 0)"); scanf("%d", &c); if(c==1) goto x; else exit(0); getch(); }
OUTPUT:
Enter how
many blocks already allocated: 3
Enter
blocks already allocated:1 3 5
Enter
index starting block and length: 2
4
2----------->
1
3 Block is already allocated
4----------->
1
5 Block is already allocated
6----------->
1
7----------->
1
Do you
want to enter more file(Yes - 1/No - 0) 0
|
