Program: Computer Engineering (NBA Accredited)

E-Notes

Operating System (22516) Ch-4 CPU Scheduling and Algorithms Marks: 14

Q. Explain Scheduling Model

CPU scheduling is the process of selecting a process from the ready queue and assigning the CPU to it. CPU
scheduling algorithms decides which of the processes in the ready queue is to be allocated to the CPU.
Every process in OS that requests CPU service carries out the following sequence of actions:
 In first action, join the ready queue and wait for CPU service.
 In second action, execute (receive CPU service) for the duration of the current CPU burst or for the
duration of the time slice (timeout).
 In third action, join the I/O queue to wait for I/O service or return to the ready queue to wait for more
CPU service.
 In fourth action, terminate and exit if service is completed i.e., if there are no more CPU or I/O bursts.
If more service is required, return to the ready queue to wait for more CPU service.

Q. Describe CPU and I/O burst cycle with the help of diagram – 4m
Processes require alternate use of processor and I/O in a repetitive fashion. Each cycle consist of a CPU burst
followed by an I/O burst. A process terminates on a CPU burst. CPU-bound processes have longer CPU bursts
than I/O-bound processes.
 I/O bound process: The process which spends more time in I/O operation than computation (time
spends with CPU) is I/O bound process.
 CPU bound process: The process which spends more time in computations or with CPU and very
rarely with the I/O devices is called as CPU bound process.

VTP-SAV Operating System (22516) Chapter-4

1
Program: Computer Engineering (NBA Accredited)
E-Notes

Q. State any four criteria in CPU scheduling – 4m

 CPU Utilization: We want to keep to CPU as busy as possible; CPU Utilization may range from 0 to 100
percent. In a real system it should range from 40 percent to 90 percent.
 Throughput: If the CPU is busy executing processes, then work is being done. One measure of work is
the number of processes that are completed per time unit called Throughput. For long processes, this
rate may be one process per hour, for short transactions, throughput might be 10 processes per
second.
 Turnaround Time: The interval from the time of submission of a process to the time of completion is
the turnaround time. Turnaround Time is the sum; of the periods spent waiting to get into memory
writing in the ready queue, executing on the CPU and doing I/O.
Turnaround Time = Waiting Time + Burst Time or End Time – ArrivalTime
 Waiting Time: The CPU scheduling algorithm does not affect the amount of time during which a
process executes of does I/O, if affects only the amount of time that a process spends waiting in the
ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.
 Response Time: In an interactive system TAT (Turn Around Time) may not be best criterion. Often a
process can produce some output early and can continue computing new results while previous
results are being output to the user. Thus another measure is the time from submission of a request
until the first response is produced. This measure called response time is the amount of time it takes
to start responding, but not the time that it takes to output that response.

Q. Define the following terms: i) Preemptive scheduling ii) Non-preemptive scheduling

Pre-emptive scheduling: If a higher priority process is entering the system, the currently running process is
stopped and the CPU transfers the control to the higher priority process. The currently running process may
be interrupted and moved to the ready state by the operating system. The pre-emptive scheduling is based on
priority where a scheduler may pre-empt a low priority running process anytime when a high priority process
enters into a ready state.
Circumstances for pre-emptive:
 process switch from running to ready state
 process switch from waiting to ready state
Example of Pre-emptive Scheduling: SJF (Shortest Job First), Priority, RR (Round Robin)

Non pre-emptive scheduling: Once the CPU has been allocated to a process the process keeps the CPU until
releases CPU either by terminating or by switching to waiting state Non-pre-emptive algorithms are designed
so that once a process enters the running state, it cannot be pre-empted until it completes its allotted time,
Circumstances for Non pre-emptive:
 When process switches from running to waiting state
 When process terminates
Example: FCFS (First Come First Serve)

When pre-emptive and Non-pre-emptive type Scheduling is used:

Non-pre-emptive:
Circumstances for Non pre-emptive:
 When process switches from running to waiting state
 When process terminates

Pre-emptive Scheduling:
Circumstances for pre-emptive:
• process switch from running to ready state
• process switch from waiting to ready state

VTP-SAV Operating System (22516) Chapter-4

2
Program: Computer Engineering (NBA Accredited)
E-Notes

Q. Differentiate between pre-emptive and non-pre-emptive scheduling (any 4 points) – 4m

Pre-emptive Scheduling Non Pre-emptive Scheduling
Even if CPU is allocated to one process, CPU can be Once the CPU has been allocated to a process the
preempted to other process if other process is process keeps the CPU until it releases CPU either by
having higher priority or some other fulfilling terminating or by switching to waiting state.
criteria.
Throughput is less Throughput is high.
Only the processes having higher priority are Processes having any priority can get scheduled.
scheduled.
It doesn’t treat all processes as equal. It treats all process as equal
Algorithm design is complex. Algorithm design is simple
Circumstances for preemptive Circumstances for Non-preemptive Process switches
(i) Process switch from running to ready state from running to waiting state Process terminates
(ii) Process switch from waiting to ready state
For e.g.: Round Robin, Priority Algorithms For e.g.: FCFS Algorithm

Q. Define Dispatcher
 Dispatcher is a component which involves in the CPU scheduling. The dispatcher is the module that
actually gives control of the CPU to the process selected by the short term scheduler.
 The module of the operating system that performs the function of setting up the execution of the
selected process on the CPU is known as dispatcher.

Q. Explain first come first served (FCFS) algorithm. Give one example. State any one advantages and one
disadvantage. – 8m
 First-Come - First-Served (FCFS) Scheduling FCFS scheduling is non-preemptive algorithm.
 Once the CPU is allocated to a process, it keeps the CPU until it releases the CPU, either by
terminating or by requesting I/O.
 In this algorithm, a process, that a request the CPU first, is allocated the CPU first. FCFS scheduling is
implemented with a FIFO queue.
 When a process enters the ready queue, its PCB is linked to the tail of the queue.
 When the CPU is available, it is allocated to the process at the head of the queue. Once the CPU is
allocated to a process, that process is removed from the queue.
 The process releases the CPU by its own.
Example:
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1, P2, P3
Gantt Chart:

VTP-SAV Operating System (22516) Chapter-4

3
Program: Computer Engineering (NBA Accredited)
E-Notes

Process Waiting Time Turn Around Time -TAT

P1 0 24
P2 24 27
P3 27 30
Average (0 + 24 + 27)/3 = 17 (24 + 27 + 30)/3 = 27

Advantage:
 It is simple to implement.
Disadvantage:
 This scheduling method is non-preemptive, that is, the process will run until it finishes. Because of this
non-preemptive scheduling, short processes which are at the back of the queue have
 to wait for the long process at the front to finish.
 It is not suitable for real time systems.
 Average waiting time and average turnaround time is more comparatively.

Q. Explain Shortest Job First (SJF) Scheduling Algorithm with example

This algorithm associates with each process the length of latter’s next CPU burst. When CPU is available it is
assigned to process that has the smallest next CPU burst. If two processes have the same length next CPU
burst, FCFS scheduling algorithm is used to select the next process. Most appropriate term would be shortest
next CPU burst, because the scheduling is done by examining the length of next CPU burst of a process, rather
than its total length. For example consider the following set of processes with the length of CPU burst time
given in milliseconds.
Problem: Consider the following processes, with the CPU burst time given in milliseconds. Calculate average
waiting time and turnaround time. (Consider all jobs arrived at same time)
Process Burst Time
P1 6
P2 8
P3 7
P4 3
Sol:
Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 3 TAT of process P1= 9
Waiting time of Process P2= 16 TAT of process P2= 24
Waiting time of Process P3= 9 TAT of process P3= 16
Waiting time of Process P4= 0 TAT of process P4= 3
Average Waiting Time=(3+16+9+0)/4 = 28/4 = 7 msec Average TAT=(9+24+16+3)/4 = 52/4 =13 msec

Advantages of SJF algorithm:

 Overall performance is significantly improve in terms of response time

Disadvantages of SJF algorithm:

 There is a risk of starvation of longer processes.
 It is very difficult to know the length of next CPU burst.

VTP-SAV Operating System (22516) Chapter-4

4
Program: Computer Engineering (NBA Accredited)
E-Notes

Q. Explain Shortest Remaining Time Next (SRTN) scheduling algorithm with example – 4m
SRTN: Shortest Remaining Time Next or Shortest job first (SJF)
A Shortest remaining Time Next scheduling algorithm is also referred as preemptive SJF scheduling algorithm.
When a new process arrives at ready queue while one process is still executing then SRTN algorithm is
performed to decide which process will execute next. This algorithm compare CPU burst time of newly arrived
process with remaining (left) CPU burst time of currently executing process. If CPU burst time of new process
is less than remaining time of current process, then SRTN algorithm preempts current process execution and
starts executing new process.
Example: Consider four processes with arrival time and burst time mentioned below in table.
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Gantt Chart

 As P1 is the only process in ready queue at time 0, P1 will start execution first.
 At time 1, process P2 arrives. The Burst time of P2 i.e. 4 ms is less than remaining burst time of process
P1 i.e.7 ms, so process P1 is preempted and process P2 starts executing.
 At time 2, process P3 arrives. The Burst time of P3 i.e. 9 ms is greater than remaining burst time of
process P2 i.e. 3 ms, so Process P2 continues its execution.
 At time 3, process P4 arrives. The Burst time of P4 i.e. 5 ms is greater than remaining burst time of
process P2 i.e. 2 ms, so Process P2 continues its execution.
 When P2 process completes its execution, all remaining processes execute with shortest job first
algorithm.
Waiting time of processes:
P1: 9 ms
P2: 0 ms
P3: 15 ms
P4: 2 ms
Average waiting time= (9+0+15+2)/4=26/4=6.5 ms

Q. Explain how priority scheduling algorithm works with suitable explain, also list advantages and
disadvantages – 8m
Q. Explain Priority Scheduling Algorithm with Example
Priority scheduling algorithm: In priority scheduling algorithm, Number (integer) indicating priority is
associated with each process. The CPU is allocated to a process with the highest priority. A priority algorithm
will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently
running process. A major problem with priority scheduling is indefinite blocking or starvation. A solution to the
problem of indefinite blockage of the low-priority process is aging. Aging is a technique of gradually increasing
the priority of processes that wait in the system for a long period of time.

VTP-SAV Operating System (22516) Chapter-4

5
Program: Computer Engineering (NBA Accredited)
E-Notes

Advantage of Priority Scheduling

• Simplicity.
• Reasonable support for priority.
Suitable for applications with varying time and resource requirements.

Disadvantages of Priority Scheduling:

• Indefinite blocking or starvation.
• A priority scheduling can leave some low priority processes waiting indefinitely for CPU.

Example: Consider the following set of processes assumed to have arrived at time 0, in the order P1, P2, P3,
----- P5, with the length of the CPU burst time given in milliseconds. Calculate the average TAT and Waiting
Time
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Using priority scheduling, we would schedule these processes according to the following Gantt Chart:

Waiting Time Turnaround Time

Waiting time of Process P1= 6 TAT of process P1= 16
Waiting time of Process P2= 0 TAT of process P2= 1
Waiting time of Process P3= 16 TAT of process P3= 18
Waiting time of Process P4= 18 TAT of process P4= 19
Waiting time of Process P5= 1 TAT of process P5= 6
Average Waiting Time=(6+0+16+18+1)/4 = 41/5 = 8.2 Average TAT=(16+1+18+19+6)/5 = 60/5 =12 msec

Describe Round Robin Algorithm with suitable example – 4m

 The Round–Robin (RR) scheduling algorithm is designed especially for time sharing systems.
 It is similar to FCFS scheduling, but preemption is added to enable the system to switch between
processes.
 A small unit of time, called as time quantum or time slice, is defined. A time quantum is generally from
10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler
goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time
quantum.
 To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes
are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready
queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
 One of two things will then happen. The process may have a CPU burst of less than 1 time quantum. In
this case, the process itself will release the CPU voluntarily. The scheduler will then process to the next
process in the ready queue. Otherwise, if the CPU burst of the currently running process is longer than
1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context
switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler
will then select the next process in the ready queue.
 The average waiting time under the RR policy is often long.

VTP-SAV Operating System (22516) Chapter-4

6
Program: Computer Engineering (NBA Accredited)
E-Notes

 Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in
milliseconds:
Process Burst Time
P1 24
P2 3
P3 3

If we use a time quantum of 4 milliseconds, then process P1 gets the first 4 milliseconds. Since it requires
another 20 milliseconds, it is preempted after the first time quantum. And the CPU is given to the next process
in the queue, process P2. process P2 does not need 4 milliseconds, so it quits before its time quantum expires.
The CPU is then given to the next process, process P3. Once each process has received 1 time quantum, the
CPU is returns to process P1 for an additional time quantum.
The resulting RR schedule is as follows:

Advantages of RR scheduling:
 Round robin is particularly effective in a general purpose time sharing system or transaction
processing system.
Disadvantages of RR scheduling:
 If there is a mix of processor bound and I/O bound processes then processor bound process tend to
receive an unfair portion of processor time, which result in poor performance for I/O bound
processes, inefficient use of I/O devices and an increase in the variance of response time.

Q. Comparison of various scheduling algorithms

Parameter FCFS algorithm SJF algorithm Priority Algorithm RR Algorithm

Preemption This scheduling This scheduling This scheduling This scheduling

algorithm is non algorithm is algorithm is also algorithm is also
preemptive. preemptive. preemptive. preemptive.
Complexity This is simplest This algorithm is This algorithm is In this scheduling
scheduling difficult to also difficult to algorithm
algorithm. understand and understand. performance heavily
code. depends upon the size
of time quantum.
Allocation In this scheduling In this scheduling This scheduling In this scheduling
algorithm it algorithm CPU is algorithm is based algorithm the
allocates the CPU in allocated to the on priority the preemption take place
the order in which process with least higher priority job after a fixed interval
the processes arrive. CPU burst time. can run first. of time.
Application This scheduling This scheduling This scheduling This scheduling
algorithm is good for algorithm is also algorithm is also algorithm is good for
non-interactive good for non- good for non- interactive system.
system. interactive system. interactive system.
Waiting Time In this scheduling In this scheduling In this scheduling In this scheduling
algorithm the algorithm the algorithm the algorithm the Average
Average waiting Average waiting Average waiting waiting time is large
time is large. time is small as time is small as as compare to all the

VTP-SAV Operating System (22516) Chapter-4

7
Program: Computer Engineering (NBA Accredited)
E-Notes

compare to FCFS compare to FCFS three scheduling

scheduling scheduling algorithm.
algorithm. algorithm.
Usability This scheduling In this scheduling This scheduling In this scheduling
algorithm is never algorithm the algorithm is the algorithm if the
recommended problem is to know sometime becomes quantum size is large
whenever the length of time the biggest cause of then this algorithm
performance is a for which the CPU is starvation. become same as FCFS
major issue. needed by the algorithm and its
process. performance degrade.

Type of System This scheduling This scheduling This scheduling This scheduling
algorithm is suitable algorithm is also algorithm is based algorithm is suitable
for Batch system. suitable for Batch upon priority. for time sharing
system. system.

Q. Explain multilevel queue scheduling – 4m

Multilevel queue scheduling classifies processes into different groups. It partitions the ready queue into
several separate queues. The processes are permanently assigned to one queue based on some properties
such as memory size, priority, process type, etc. Each queue has its own scheduling algorithm. In a system
there are foreground processes and background processes. So system can divide processes into two queues:
one for background and other for foreground. Foreground queue can be scheduled with Round Robin
algorithm where as background queue can be scheduled by First Come First Serve algorithm. Scheduling is
done for all the processes inside the queue as well as for all separate queues.
Example: Consider all the processes in the system are divided into four groups: system, interactive, interactive
editing, batch and student processes queue. Each queue contains processes. CPU is first scheduled for all
queues on may be priority, total burst time or process type. (Any relevant diagram shall be considered)

Q. Define deadlock – 2m
A deadlock consists of a set of blocked processes, each holding a resource and waiting to acquire a resource
held by another process in the set

VTP-SAV Operating System (22516) Chapter-4

8
Program: Computer Engineering (NBA Accredited)
E-Notes

Q. Write Steps of banker’s algorithm to avoid deadlock 4 m

Steps of Banker’s Algorithm:
This algorithm calculates resources allocated, required and available before allocating resources to any
process to avoid deadlock. It contains two matrices on a dynamic basis. Matrix A contains resources allocated
to different processes at a given time. Matrix B maintains the resources which are still required by different
processes at the same time.
Algorithm F: Free resources
Step 1: When a process requests for a resource, the OS allocates it on a trial basis.
Step 2: After trial allocation, the OS updates all the matrices and vectors. This updating can be done by the OS
in a separate work area in the memory.
Step 3: It compares F vector with each row of matrix B on a vector to vector basis.
Step 4: If F is smaller than each of the row in Matrix B i.e. even if all free resources are allocated to any
process in Matrix B and not a single process can complete its task then OS concludes that the system is in
unstable state.
Step 5: If F is greater than any row for a process in Matrix B the OS allocates all required resources for that
process on a trial basis. It assumes that after completion of process, it will release all the recourses allocated
to it. These resources can be added to the free vector.
Step 6: After execution of a process, it removes the row indicating executed process from both matrices.
Step 7: This algorithm will repeat the procedure step 3 for each process from the matrices and finds that all
processes can complete execution without entering unsafe state. For each request for any resource by a
process OS goes through all these trials of imaginary allocation and updation. After this if the system remains
in the safe state, and then changes can be made in actual matrices.

Q. Enlist and describe in details conditions leading to Deadlocks – 8m

Q. Describe any four condition for deadlock – 4m
 Mutual Exclusion: The resources involved are non-shareable. At least one resource (thread) must be
held in a non-shareable mode, that is, only one process at a time claims exclusive control of the
resource. If another process requests that resource, the requesting process must be delayed until the
resource has been released. A disk drive can be shared by two processes simultaneously. This will not
cause deadlock, but printers, tape drives, plotters etc. have to be allocated to a process in an exclusive
manner until the process completely finishes its work with it, which normally happens when the
process ends. This will cause deadlock.
 Hold and Wait: Requesting process already holds resources while waiting for requested resources.
Even if a process holds certain resources at any moment, it is possible for it to request for new
resource. There must exist a process that is holding a resource already allocated to it while waiting for
additional resource that are currently being held by other processes. It will not give the resource
already held and request for new one. If it is true, deadlock will take place and if this is not true, a
deadlock can never take place.
 No-Preemption: Resources cannot be pre-empted i.e a resource can be released only voluntarily by
the process holding it. Once the resources are allocated to the process, system cannot forcefully
deallocate the resources from a process even though that process goes into the waiting state for
additional resources.
 Circular Wait: The processes in the system form a circular list or chain where each process in the list is
waiting for a resource held by the next process in the list. The set of waiting processes P0, P1, P2,
P3…..Pn waiting for resources which are already held by the next process. In this example, P0 is
waiting for the resource already held by P1, P1 waiting for the resource already held by P2, P2 waiting
for the resource already held by P3, Pn-1 waiting for the resource which is held by Pn and Pn waiting
for the resource which is held by P0.
 It is necessary to understand that all these four conditions have to be satisfied simultaneously for
deadlock.
VTP-SAV Operating System (22516) Chapter-4
9
Program: Computer Engineering (NBA Accredited)
E-Notes

Q. Explain in detail how deadlock can be handled – 4m

There are three different methods for dealing with the deadlock problem:
 We can use a protocol to ensure that the system will never enter a deadlock state
 We can allow the system to enter a deadlock state and then recover.
 We can ignore the problem all together, and pretend that deadlocks never occur in system. This
solution is the one used by most operating systems, including UNIX.

1. To ensure that deadlocks never occur, the system can be use either a deadlock prevention or a
deadlock-avoidance scheme. Deadlock prevention is a set of methods for ensuring that at least one of
the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests
for resources can be made.
2. Deadlock avoidance, on the other hand, requires that the operating system be given in advance
additional information concerning which resources a process will request and use during its lifetime.
with this additional knowledge, we can decide for each request whether or not the process, and the
future requests and releases of each process, to decide whether the current request can be satisfied
or must be delayed.
3. If the system does not employ either a deadlock-prevention or deadlock – avoidance algorithm, then a
deadlock situation may occur .in this environment, the system can provide an algorithm that examines
the state of the system to determine whether a deadlock has occurred, and an algorithm to recover
from the deadlock.
4. If a system does not ensure that a deadlock will never occur, and also does not provide a mechanism
for deadlock detection and recovery, then we may arrive at a situation where the system is in a
deadlock state yet has no way of recognizing what has happened

Q. Explain Deadlock Avoidance with example – 4m

Most prevention algorithms have poor resource utilization, and hence result in reduced throughputs. Instead,
we can try to avoid deadlocks by making use prior knowledge about the usage of resources by processes
including resources available, resources allocated, future requests and future releases by processes. Most
deadlock avoidance algorithms need every process to tell in advance the maximum number of resources of
each type that it may need. Based on all this info we may decide if a process should wait for a resource or not
and thus avoid chances for circular wait.
Deadlock can be avoided by following algorithms:
Safe State: If a system is already in a safe state, we can try to stay away from an unsafe state and avoid
deadlock. Deadlocks cannot be avoided in an unsafe state. A system can be considered to be in safe state if it
is not in a state of deadlock and can allocate resources up to the maximum available. A safe sequence of
processes and allocation of resources ensures a safe state. Deadlock avoidance algorithms try not to allocate
resources to a process if it will make the system in an unsafe state. Since resource allocation is not done right
away in some cases, deadlock avoidance algorithms also suffer from low resource utilization problem.
Resource Allocation Graph: A resource allocation graph is generally used to avoid deadlocks. If there are no
cycles in the resource allocation graph, then there are no deadlocks. If there are cycles, there may be a
deadlock. If there is only one instance of every resource, then a cycle implies a deadlock. Vertices of the
resource allocation graph are resources and processes. The resource allocation graph has request edges and
assignment edges. An edge from a process to resource is a request edge and an edge from a resource to
process is an allocation edge. A calm edge denotes that a request may be made in future and is represented as
a dashed line. Based on calm edges we can see if there is a chance for a cycle and then grant requests if the
system will again be in a safe state.
Example:

VTP-SAV Operating System (22516) Chapter-4

10
Program: Computer Engineering (NBA Accredited)
E-Notes

If R2 is allocated to P2 and if P1 is request for R2, there will be a deadlock

Bankers Algorithm: The resource allocation graph is not much useful if there are multiple instances for a
resource. In such a case, we can use Banker‟s algorithm. In this algorithm, every process must tell upfront the
maximum resource of each type it need, subject to the maximum available instances for each type. Allocation
of resources is made only, if the allocation ensures a safe state; else the processes need to wait. The Banker‟s
algorithm can be divided into two parts: Safety algorithm if a system is in a safe state or not. The resource
request algorithm make an assumption of allocation and see if the system will be in a safe state. If the new
state is unsafe, the resources are not allocated and the data structures are restored to their previous state; in
this case the processes must wait for the resource.
Example:
5 processes P0 through P4;
3 Resources types: A (10 Instances), B(5 Instances) and C(7 Instances)

Allocation Max Available

ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433

ABC
P0 743
P1 122
P2 600
P3 011
P4 431

The system in a safe state since the sequence <P1, P3, P4, P2, P0> satisfies safety criteria.

Q. Write steps for Bankers algorithm to avoid deadlock -4m

Banker’s Algorithm:
This algorithm calculates resources allocated, required and available before allocating resources to any
process to avoid deadlock. It contains two matrices on a dynamic basis. Matrix A contains resources allocated
to different processes at a given time. Matrix B maintains the resources which are still required by different
processes at the same time.
Algorithm F: Free resources

VTP-SAV Operating System (22516) Chapter-4

11
Program: Computer Engineering (NBA Accredited)
E-Notes

Step 1: When a process requests for a resource, the OS allocates it on a trial basis.
Step 2: After trial allocation, the OS updates all the matrices and vectors. This updating can be done by the OS
in a separate work area in the memory.
Step 3: It compares F vector with each row of matrix B on a vector to vector basis.
Step 4: If F is smaller than each of the row in Matrix B i.e. even if all free resources are allocated to any
process in Matrix B and not a single process can complete its task then OS concludes that the system is in
unstable state.
Step 5: If F is greater than any row for a process in Matrix B the OS allocates all required resources for that
process on a trial basis. It assumes that after completion of process, it will release all the recourses allocated
to it. These resources can be added to the free vector.
Step 6: After execution of a process, it removes the row indicating executed process from both matrices.
Step 7: This algorithm will repeat the procedure step 3 for each process from the matrices and finds that all
processes can complete execution without entering unsafe state. For each request for any resource by a
process OS goes through all these trials of imaginary allocation and updation. After this if the system remains
in the safe state, and then changes can be made in actual matrices.

Solved Problems
1. Calculate Average locating Time for SJF (Shortest Job First) and Round Robin (RR) algorithm for following
table: (Time Slice 4 msec)
Process Burst Time
P1 10
P2 4
P3 9
P4 6

SJF (Shortest Job First)

Gantt Chart

Waiting Time and Turn Around Time Table:

Process Waiting Time Turn Around Time -TAT
P1 19 29
P2 0 4
P3 10 19
P4 4 10
Average (19 + 0 + 10 + 4)/4=8.25 msec (29 + 4 + 19 + 10)/4 = 15.5

Round Robin (RR)

Gantt Chart

VTP-SAV Operating System (22516) Chapter-4

12
Program: Computer Engineering (NBA Accredited)
E-Notes

Process Waiting Time Turn Around Time -TAT

P1 18 58
P2 4 8
P3 20 29
P4 20 26
Average (18 + 04 + 20 + 20)/4 = 15.5 (28 + 08 + 29 + 26)/4 = 22.75

2. Assume we have the workload shown below. All five jobs arrive at time 0 in the order given.
Job Burst Time
1 10
2 29
3 3
4 7
5 12
Considering FCFS, Shortest Job First and Round Robin (quantum=10) scheduling algorithms for this set of jobs
which algorithms would give the minimum average waiting time?

Solution:
For FCFS:
1 2 3 4 5
0 10 39 42 49 61

Average Waiting Time is = 0 + 10 + 39 + 42 + 49

= 140 / 5
= 28 milliseconds
Shortest Job First (Non pre-emptive)
3 4 1 5 2
0 3 10 20 32 61

Average Waiting Time is = 10 + 32 + 0 + 3 + 20

= 65 / 5
= 13 milliseconds
Round Robin (Quantum = 10)
1 2 3 4 5 2 5 2
0 10 20 23 30 40 50 52 61

Average Waiting Time is = 1 + 32 + 20 + 23 + 40

= 115 / 5
= 23 milliseconds
We see that in this case shortest job first has less than half the average waiting time of FCFS. round robin has
an intermediate value.

VTP-SAV Operating System (22516) Chapter-4

13
Program: Computer Engineering (NBA Accredited)
E-Notes

3) Five jobs A through E arrives at a computer center at all most same time. They have estimated running
time of 10, 6, 2, 4, 8 minutes. Their priorities are 3, 5, 2, 1, 4 resp. for each of the following scheduling
algorithm determine Turn-Around-Time and Average Waiting Time by: Round Robin Scheduling Algorithm,
Shortest Job First Scheduling, FCFS scheduling and Priority method
Job Running Time Priority
A 10 3
B 6 5
C 2 2
D 4 1
E 8 4
Sol:
Using FCFS Scheduling Algorithm
Gantt chart

Waiting Time Turnaround Time

Waiting time of Process A= 0 TAT of Process A= 10
Waiting time of Process B= 10 TAT of Process B= 16
Waiting time of Process C= 16 TAT of Process C= 18
Waiting time of Process D= 18 TAT of Process D= 22
Waiting time of Process E= 22 TAT of Process E= 30
Average Waiting Time= (0+10+16+18+22)/5=66/5=13.2 Average TAT= (10+16+18+22+30)/5=96/5=19.2

Using SJF Scheduling Algorithm

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process A= 20 TAT of Process A= 30
Waiting time of Process B= 6 TAT of Process B= 12
Waiting time of Process C= 0 TAT of Process C= 2
Waiting time of Process D= 2 TAT of Process D= 6
Waiting time of Process E= 12 TAT of Process E= 20
Average Waiting Time=(20+6+0+2+12)/5=40/5=8 Average TAT=(30+12+2+6+20)/5=70/5=14

Using Priority Scheduling Algorithm

Gantt chart

VTP-SAV Operating System (22516) Chapter-4

14
Program: Computer Engineering (NBA Accredited)
E-Notes

Waiting Time Turnaround Time

Waiting time of Process A= 6 TAT of Process A= 16
Waiting time of Process B= 24 TAT of Process B= 30
Waiting time of Process C= 4 TAT of Process C= 6
Waiting time of Process D= 0 TAT of Process D= 4
Waiting time of Process E= 16 TAT of Process E= 24
Average Waiting Time=(6+24+4+0+16)/5=50/5=10 Average TAT=(16+30+6+4+24)/5=80/5=16

Using RR Scheduling Algorithm (Time Slice=4)

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process A=(18-4)+(28-22)=14+6=20 TAT of Process A= 30
Waiting time of Process B=4+(22-8)=4+14=18 TAT of Process B= 24
Waiting time of Process C= 8 TAT of Process C= 10
Waiting time of Process D= 10 TAT of Process D= 14
Waiting time of Process E= 14+(24-18)=14+6=20 TAT of Process E= 28
Average Waiting Time=(20+18+8+10+20)/5=76/5=15.2 Average TAT= (30+24+10+14+28)/5=106/5=21.2

4) The jobs are scheduled for execution as follows:

Process Arrival Time Burst Time
P1 0 7
P2 1 4
P3 2 9
P4 3 6
P5 4 8
Solve the problem using 1) FCFS 2)SJF. Also find average waiting time using Gantt chart (Dec-2013)

Solution:
Using FCFS Scheduling algorithm
Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0 TAT of process P1= 7
Waiting time of Process P2= 7-1 = 6 TAT of process P2= 11-1 = 10
Waiting time of Process P3= 11-2 = 9 TAT of process P3= 20-2 = 18
Waiting time of Process P4= 20-3 = 17 TAT of process P4= 26-3 = 23
Waiting time of Process P5= 26-4 = 22 TAT of process P5= 34-4 = 30
Average Waiting Time= (0+6+9+17+22)/5=54/5= Average TAT=(7+10+18+23+30)/5=88/5=17.6
10.8
VTP-SAV Operating System (22516) Chapter-4
15
Program: Computer Engineering (NBA Accredited)
E-Notes

Using Non-Preemptive SJF scheduling algorithm

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0 TAT of process P1= 7
Waiting time of Process P2= 7-1 = 6 TAT of process P2= 11-1 = 10
Waiting time of Process P3= 25-2= 23 TAT of process P3= 34-2 = 32
Waiting time of Process P4= 11-3 = 8 TAT of process P4= 17-3 = 14
Waiting time of Process P5= 17-4 = 13 TAT of process P5= 25-4 = 21
Average Waiting Time=(0+6+23+8+13)/5=50/5=10 Average TAT=(7+10+32+14+21)/5=84/5=16.8

Using Preemptive SJF scheduling algorithm

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0+(5-1)=4 TAT of process P1= 11
Waiting time of Process P2= 1-1=0 TAT of process P2= 5-1 = 4
Waiting time of Process P3= 25-2 = 23 TAT of process P3= 34-2 = 32
Waiting time of Process P4= 11-3 = 8 TAT of process P4= 17-3 = 14
Waiting time of Process P5= 17-4 = 13 TAT of process P5= 25-4 = 21
Average Waiting Time=(4+0+23+8+13)5=48/5=9.6 Average TAT=(11+4+32+14+21)/5=82/5=16.4

5) Consider the following set of processes with arrival time as shown below:
Process Priority Arrival time CPU Burst Time (in ms)
P1 2 0 8
P2 3 1 4
P3 1 2 9
P4 4 3 5
Find out Average Waiting Time by using FCFS, SJF, Priority Scheduling algorithm (May-12)

Solution:
Using FCFS Scheduling Algorithm
Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0 TAT of process P1= 8
Waiting time of Process P2= 8-1= 7 TAT of process P2= 12-1 = 11
Waiting time of Process P3= 12-2 =10 TAT of process P3= 21-2 = 19
Waiting time of Process P4= 21-3 = 18 TAT of process P4= 26-3 = 23
Average Waiting Time=(0+7+10+18)/4=35/4=8.75 ms Average TAT=(8+11+19+23)/4=61/4=15.25 ms

VTP-SAV Operating System (22516) Chapter-4

16
Program: Computer Engineering (NBA Accredited)
E-Notes

Using Non-Preemptive SJF Scheduling Algorithm

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0 TAT of process P1= 8
Waiting time of Process P2= 8-1 = 7 TAT of process P2= 12-1 = 11
Waiting time of Process P3= 17-2 = 15 TAT of process P3= 26-2 = 24
Waiting time of Process P4= 12-3 = 9 TAT of process P4= 17-3 = 15
Average Waiting Time=(0+7+15+9)/4=31/4=7.75 ms Average TAT=(8+11+24+15)/4=58/4=14.5 ms
Using Preemptive SJF Scheduling Algorithm
Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 10-1 = 9 TAT of process P1= 17
Waiting time of Process P2= 1-1 = 0 TAT of process P2= 5-1 = 4
Waiting time of Process P3= 17-2 = 15 TAT of process P3= 26-2 = 24
Waiting time of Process P4= 5-3 = 2 TAT of process P4= 10-3 = 7
Average Waiting Time=(9+0+15+2)/4=26/4=6.5 ms Average TAT=(17+4+24+7)/4=52/4=13 ms

Using Non-Preemptive Priority Scheduling Algorithm

Gantt chart

Waiting Time Turnaround Time

Waiting time of Process P1= 0 TAT of process P1= 8
Waiting time of Process P2= 17-1 = 16 TAT of process P2= 21-1 = 20
Waiting time of Process P3= 8-2 = 6 TAT of process P3= 17-2 = 15
Waiting time of Process P4= 21-3 = 18 TAT of process P4= 26-3 = 23
Average Waiting Time=(0+16+6+18)/4=40/4=10 ms Average TAT=(8+20+15+23)/4=66/4=16.5 ms

Using Preemptive Priority Scheduling Algorithm

Gantt chart

VTP-SAV Operating System (22516) Chapter-4

17
Program: Computer Engineering (NBA Accredited)
E-Notes

Waiting Time Turnaround Time

Waiting time of Process P1= 11-2 = 9 TAT of process P1= 17
Waiting time of Process P2= 17-1 = 16 TAT of process P2= 21-1 = 20
Waiting time of Process P3= 2-2 = 0 TAT of process P3=11-2 = 9
Waiting time of Process P4= 21-3 = 18 TAT of process P4= 26-3 = 23
Average Waiting Time=(9+16+0+18)/4=43/4=10.75 Average TAT=(17+20+9+23)/4=69/4=17.25 ms
ms

6) System consists of five processes (P1, P2, P3, P4, P5) and three resources (R1, R2, R3). Resource type R1
has 10 Instances, resource type R2 has 5 instances, and R3 has 7 instances. Is the system in a safe state?

Sol:
Calculate Need=Max-allocation

Currently the system is in safe state.

Safe sequence:
Need of each process is compared with available. If needi≤availablei, then the resources are allocated to that
process and process will release the resource. In above example process P1 is (7,4,3) and available is (3,3,2)
Need ≥available -> False
So system will move for next process.
 Need of process P2 is (1,2,2) and available is (3,3,2) so need ≤ available=(1,2,2)≤(3,3,2)=True
Request of P2 is granted and processes p2 is release the resource to the system.
Work=work+allocation=(3,3,2)+(2,0,0)=(5,3,2)
This procedure is continuing for all processes.
 Need of process P3 needs (6,0,0) is compared with new available (5,3,2) so
need > available=(6,0,0)>(5,3,2)=False
 Process P4 need (0,1,1) is compared with new available (5,3,2)
Need < available=(0,1,1)<(5,3,2)=True, Request of Process P4 is granted.
Available=available+Allocation=(5,3,2)+(2,1,1)=(7,4,3)
 Process P5 needs (4,3,1) is compared with (7,4,3)
Need<available=(4,3,1)<(7,4,3)=True, Request of Process P5 is granted.
Available=available+Allocation=(7,4,3)+(0,0,2)=(7,4,5)
 Process Pi needs (7,4,3) and available is (7,4,5). If this request is granted then the system may be in
the deadlock state. After granting the request, available resource is (0,0,2) so the system is in unsafe
state.
 Process P3 need (6,0,0) and available is (7,4,5)\
Need<available=(6,0,0)<(7,4,5)=True, Request of Process P3 is granted.

VTP-SAV Operating System (22516) Chapter-4

18
Program: Computer Engineering (NBA Accredited)
E-Notes

Available=available+Allocation=(7,4,5)+(3,0,2)=(10,4,7) (new available)

 Last process P1 needs (7,4,3) and available is (10,4,7)
Need<available=(7,4,3)<(10,4,7)=True, Request of Process P1 is granted.
Available=available+Allocation=(10,4,7)+(0,1,0)=(10,5,7)
 Safe sequence is <P2, P4, P5, P3, P1>

7) The operating system contains 3 resources, the number of instance of each resource type are 7,7,10. The
current resource allocation state is shown below:

 Is the current allocation in a safe state?

 Can the request made by process P1(1,1,0) is granted.
Sol:
1) First find the available resource in the system.
Available=no. of instances - sum of allocation

Available=(7,7,10)-(5,4,10)=(2,3,0)
Need matrix is

Safe sequence is =<P3, P2, P1>

The system is in safe state.
2) Process P1 request (1,1,0), this request is less than need.
Need of process P1 is(1,4,5),
Available resources is (2,3,0)
And request is (1,1,0)
Request<available i.e. (1,1,0)<(2,3,0)
After allocating (1,1,0) to process P1 the need becomes as follows:

VTP-SAV Operating System (22516) Chapter-4

19
Program: Computer Engineering (NBA Accredited)
E-Notes

And available resources is (1,2,0). Need of any process is never satisfied after granting the process P1 request
(1,1,0). So the system will be blocked. Therefore request of process P1(1,1,0) cannot be granted.

8) Consider the following allocation chart. Check whether the system is safe or unsafe?

Sol: Need=Max-allocation

System is in safe state with safe sequence <P2, P4, P1, P3>. System will complete its operation in this
sequence.

9) Consider the following allocation table. Calculate the need matrix and check whether the system is safe
or unsafe?

Sol: Need=Max-allocation

System is unsafe state. Resources are not available for processes P1 and P2 to complete their operation.
VTP-SAV Operating System (22516) Chapter-4
Copy protected with Online-PDF-No-Copy.com 20