Numerical of Operating System
7 February, 2025
process scheduling algorithm (FCFS)
SJF (Shortest Job First)
Average TAT = Total of TAT/Number of processes = 25/4 = 6.25 unit
Average WT = Total of WT/Number of processes = 12/4 = 3 unit
** Asked in btech exam **
NWT (Normalized Waiting Time) = Waiting Time (WT) / Burst Time (BT)
NTAT (Normalized Turn around time) = Turnaround time (TAT) / Burst Time (BT)
SRTF (Shortest Remaining Time First)
0
0
1
6
0
Round Robin Scheduling
priority non-preemptive
priority preemptive
Best-Fit First-Fit Worst-Fit
Resource Allocation graph
Resource Allocation Graph (RAG) is a graph that represents the state of a system
pictorially.
There are two major components of a Resource Allocation Graph-
1. Vertices
2. Edges
There are following types of vertices in a Resource Allocation Graph-
Process Vertices-
Process vertices represent the processes.
They are drawn as a circle by mentioning the name of process inside the circle.
Resource Vertices-
Resource vertices represent the resources.
Depending on the number of instances that exists in the system, resource vertices
may be single instance or multiple instance.
They are drawn as a rectangle by mentioning the dots inside the rectangle.
The number of dots inside the rectangle indicates the number of instances of that
resource existing in the system.
There are two types of edges in a Resource Allocation Graph-
1. Assign Edges
2. Request Edges
Assign Edges-
Assign edges represent the assignment of resources to the processes.
They are drawn as an arrow where the head of the arrow points to the process and tail of the
process points to the instance of the resource.
Request Edges-
Request edges represent the waiting state of processes for the resources.
They are drawn as an arrow where the head of the arrow points to the instance of the
resource and tail of the process points to the process.
If a process requires ‘n’ instances of a resource type, then ‘n’ assign edges will be drawn.
There exist three processes in the system namely P1, P2
and P3.
There exist two resources in the system namely R1 and R2.
There exists a single instance of resource R1 and two
instances of resource R2.
Process P1 holds one instance of resource R1 and is
waiting for an instance of resource R2.
Process P2 holds one instance of resource R2 and is
waiting for an instance of resource R1.
Process P3 holds one instance of resource R2 and is not
waiting for anything.
Step-01:
With the instances available currently, only the requirement of the process P2 can be satisfied.
So, process P2 is allocated the requested resources.
It completes its execution and then free up the instances of resources held by it.
Then-
Available
=[001]+[010]
=[011]
Step-02:
With the instances available currently, only the requirement of the process P0 can be satisfied.
So, process P0 is allocated the requested resources.
It completes its execution and then free up the instances of resources held by it.
Then-
Available
=[011]+[101]
=[112]
Step-03:
With the instances available currently, only the requirement of the process P1 can be satisfied.
So, process P1 is allocated the requested resources.
It completes its execution and then free up the instances of resources held by it.
Then- Available
=[112]+[110]
=[222]
Step-04:
With the instances available currently, the requirement of the process P3 can be satisfied.
So, process P3 is allocated the requested resources.
It completes its execution and then free up the instances of resources held by it.
Then-Available
=[222]+[010]
=[232]
Thus,
There exists a safe sequence P2, P0, P1, P3 in which all the processes can be executed.
So, the system is in a safe state.
There are following 4 necessary conditions for the occurrence of deadlock-
1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait
1. Mutual Exclusion-
By this condition,
There must exist at least one resource in the system which can be used by only one
process at a time.
If there exists no such resource, then deadlock will never occur.
Printer is an example of a resource that can be used by only one process at a time.
2. Hold and Wait-
By this condition,
There must exist a process which holds some resource and waits for another resource held
by some other process.
3. No Preemption-
By this condition,
Once the resource has been allocated to the process, it can not be
preempted.
It means resource can not be snatched forcefully from one process and
given to the other process.
The process must release the resource voluntarily by itself.
4. Circular Wait-
By this condition,
All the processes must wait for the resource in a cyclic manner where the
last process waits for the resource held by the first process.
Here,
Process P1 waits for a resource held by process
P2.
Process P2 waits for a resource held by process
P3.
Process P3 waits for a resource held by process
P4.
Process P4 waits for a resource held by process
P1.
All these 4 conditions must hold simultaneously for the occurrence of deadlock.
If any of these conditions fail, then the system can be ensured deadlock free.
