UNIT – II CS403PC: OPERATING SYSTEMS

CPU scheduling
CPU scheduling is the process of deciding which process will own the
CPU to use while another process is suspended. The main function of the CPU
scheduling is to ensure that whenever the CPU remains idle, the OS has at least
selected one of the processes available in the ready-to-use line.
In Multiprogramming, if the long-term scheduler selects multiple I / O
binding processes then most of the time, the CPU remains an idle. The function
of an effective program is to improve resource utilization.
If most operating systems change their status from performance to waiting
then there may always be a chance of failure in the system. So in order to
minimize this excess, the OS needs to schedule tasks in order to make full use of
the CPU and avoid the possibility of deadlock.
Objectives of Process Scheduling Algorithm
 Utilization of CPU at maximum level. Keep CPU as busy as possible.
 Allocation of CPU should be fair.
 Throughput should be Maximum. i.e. Number of processes that complete
their execution per time unit should be maximized.
 Minimum turnaround time, i.e. time taken by a process to finish execution
should be the least.
 There should be a minimum waiting time and the process should not
starve in the ready queue.
 Minimum response time. It means that the time when a process produces
the first response should be as less as possible.

Terminologies
 Arrival Time: Time at which the process arrives in the ready queue.
 Completion Time: Time at which process completes its execution.
 Burst Time: Time required by a process for CPU execution.
 Turn Around Time: Time Difference between completion time and
arrival time.
Turn Around Time = Completion Time – Arrival Time
 Waiting Time(W.T): Time Difference between turn around time and
burst time.
Waiting Time = Turn Around Time – Burst Time

Page 1
UNIT – II CS403PC: OPERATING SYSTEMS

THE SCHEDULING CRITERIA

CPU utilization:
The main purpose of any CPU algorithm is to keep the CPU as busy as
possible. Theoretically, CPU usage can range from 0 to 100 but in a real-time
system, it varies from 40 to 90 percent depending on the system load.

Throughput:
The average CPU performance is the number of processes performed and
completed during each unit. This is called throughput. The output may vary
depending on the length or duration of the processes.

Turn round Time:

For a particular process, the important conditions are how long it takes to
perform that process. The time elapsed from the time of process delivery to
the time of completion is known as the conversion time. Conversion time is
the amount of time spent waiting for memory access, waiting in line, using
CPU, and waiting for I / O.

Waiting Time:
The Scheduling algorithm does not affect the time required to complete
the process once it has started performing. It only affects the waiting time of
the process i.e. the time spent in the waiting process in the ready queue.

Response Time:
In a collaborative system, turn around time is not the best option. The
process may produce something early and continue to computing the new
results while the previous results are released to the user. Therefore another
method is the time taken in the submission of the application process until the
first response is issued. This measure is called response time.

Types of CPU Scheduling Algorithms

There are mainly two types of scheduling methods:
Preemptive Scheduling:
Preemptive scheduling is used when a process switches from running state
to ready state or from the waiting state to the ready state.
Non-Preemptive Scheduling:
Non-Preemptive scheduling is used when a process terminates , or when a
process switches from running state to waiting state.

Page 2
UNIT – II CS403PC: OPERATING SYSTEMS

1. First Come First Serve Scheduling:

FCFS considered to be the simplest of all operating system scheduling
algorithms. First come first serve scheduling algorithm states that the process
that requests the CPU first is allocated the CPU first and is implemented by
using FIFO queue.
Characteristics:
 FCFS supports non-preemptive and preemptive CPU scheduling
algorithms.
 Tasks are always executed on a First-come, First-serve concept.
 FCFS is easy to implement and use.
 This algorithm is not much efficient in performance, and the wait time is
quite high.
Advantages:
 Easy to implement
 First come, first serve method
Disadvantages:
 FCFS suffers from Convoy effect.
 The average waiting time is much higher than the other algorithms.
 FCFS is very simple and easy to implement and hence not much efficient.

Page 3
UNIT – II CS403PC: OPERATING SYSTEMS

2. Shortest Job First(SJF) Scheduling:

Shortest job first (SJF) is a scheduling process that selects the waiting
process with the smallest execution time to execute next. This scheduling method
may or may not be preemptive. Significantly reduces the average waiting time
for other processes waiting to be executed. The full form of SJF is Shortest Job
First.

Characteristics:
 Shortest Job first has the advantage of having a minimum average waiting
time among all operating system scheduling algorithms.
 It is associated with each task as a unit of time to complete.
 It may cause starvation if shorter processes keep coming. This problem
can be solved using the concept of ageing.
Advantages:
 As SJF reduces the average waiting time thus, it is better than the first
come first serve scheduling algorithm.
 SJF is generally used for long term scheduling
Disadvantages:
 One of the demerit SJF has is starvation.
 Many times it becomes complicated to predict the length of the upcoming
CPU request

Page 4
UNIT – II CS403PC: OPERATING SYSTEMS

3. Longest Job First(LJF) Scheduling:

This is just opposite of shortest job first (SJF), as the name suggests this
algorithm is based upon the fact that the process with the largest burst time is
processed first. Longest Job First is non-preemptive in nature.
Characteristics:
 Among all the processes waiting in a waiting queue, CPU is always
assigned to the process having largest burst time.
 If two processes have the same burst time then the tie is broken
using FCFS i.e. the process that arrived first is processed first.
 LJF CPU Scheduling can be of both preemptive and non-preemptive
types.
Advantages:
 No other task can schedule until the longest job or process executes
completely.
 All the jobs or processes finish at the same time approximately.
Disadvantages:
 Generally, the LJF algorithm gives a very high average waiting
time and average turn-around time for a given set of processes.
 This may lead to convoy effect.

4. Priority Scheduling:
Preemptive Priority CPU Scheduling Algorithm is a pre-emptive
method of CPU scheduling algorithm that works based on the priority of a
process. In this algorithm, the editor sets the functions to be as important,
meaning that the most important process must be done first. In the case of any
conflict, that is, where there are more than one processor with equal value, then
the most important CPU planning algorithm works on the basis of the FCFS
Characteristics:
 Schedules tasks based on priority.
 When the higher priority work arrives while a task with less priority is
executed, the higher priority work takes the place of the less priority one
and
 The latter is suspended until the execution is complete.
 Lower is the number assigned, higher is the priority level of a process.
Advantages:
 The average waiting time is less than FCFS
 Less complex

Page 5
UNIT – II CS403PC: OPERATING SYSTEMS

Disadvantages:
 One of the most common demerits of the Preemptive priority CPU
scheduling algorithm is the Starvation Problem. This is the problem in
which a process has to wait for a longer amount of time to get scheduled
into the CPU. This condition is called the starvation problem.

5. Round Robin Scheduling:

Round Robin is a CPU scheduling algorithm where each process is
cyclically assigned a fixed time slot. It is the preemptive version of First come
First Serve CPU Scheduling algorithm. Round Robin CPU Algorithm generally
focuses on Time Sharing technique.
Characteristics:
 It’s simple, easy to use, and starvation-free as all processes get the
balanced CPU allocation.
 One of the most widely used methods in CPU scheduling as a core.
 It is considered preemptive as the processes are given to the CPU for a
very limited time.
Advantages:
 Round robin seems to be fair as every process gets an equal share of CPU.
 The newly created process is added to the end of the ready queue.

6. Shortest Remaining Time First Scheduling (SRTF):

SRTF is the preemptive version of the Shortest job first which we have
discussed earlier where the processor is allocated to the job closest to
completion. In SRTF the process with the smallest amount of time remaining
until completion is selected to execute.
Characteristics:
 SRTF algorithm makes the processing of the jobs faster than SJF
algorithm, given it’s overhead charges are not counted.
 The context switch is done a lot more times in SRTF than in SJF and
consumes the CPU’s valuable time for processing. This adds up to its
processing time and diminishes its advantage of fast processing.
Advantages:
 In SRTF the short processes are handled very fast.
 The system also requires very little overhead since it only makes a
decision when a process completes or a new process is added.

Page 6
UNIT – II CS403PC: OPERATING SYSTEMS

Disadvantages:
 Like the shortest job first, it also has the potential for process starvation.
 Long processes may be held off indefinitely if short processes are
continually added.

7. Longest Remaining Time First:

The longest remaining time first is a preemptive version of the longest
job first scheduling algorithm. This scheduling algorithm is used by the
operating system to program incoming processes for use in a systematic way.
This algorithm schedules those processes first which have the longest processing
time remaining for completion.
Characteristics:
 Among all the processes waiting in a waiting queue, the CPU is always
assigned to the process having the largest burst time.
 If two processes have the same burst time then the tie is broken
using FCFS i.e. the process that arrived first is processed first.
 LJF CPU Scheduling can be of both preemptive and non-preemptive
types.
Advantages:
 No other process can execute until the longest task executes completely.
 All the jobs or processes finish at the same time approximately.
Disadvantages:
 This algorithm gives a very high average waiting time and average turn-
around time for a given set of processes.
 This may lead to a convoy effect.

8. Highest Response Ratio Next:

Highest Response Ratio Next is a non-preemptive CPU Scheduling
algorithm and it is considered as one of the most optimal scheduling algorithms.
The name itself states that we need to find the response ratio of all available
processes and select the one with the highest Response Ratio. A process once
selected will run till completion.
Characteristics:
 The criteria for HRRN is Response Ratio and the mode is Non
Preemptive.
 HRRN is considered as the modification of Shortest Job First to reduce
the problem of starvation.

Page 7
UNIT – II CS403PC: OPERATING SYSTEMS

 In comparison with SJF, during the HRRN scheduling algorithm, the CPU
is allotted to the next process which has the highest response ratio and
not to the process having less burst time.
Response Ratio = (W + S)/S
Here, W - Waiting time of the process
S - Burst time of the process.
Advantages:
 HRRN Scheduling algorithm generally gives better performance than
the shortest job first Scheduling.
 There is a reduction in waiting time for longer jobs and also it encourages
shorter jobs.
Disadvantages:
 The implementation of HRRN scheduling is not possible as it is not
possible to know the burst time of every job in advance.
 In this scheduling, there may occur an overload on the CPU.

9. Multiple Queue Scheduling:

Processes in the ready queue can be divided into different classes where
each class has its own scheduling needs. For example, a common division is
a foreground (interactive) process and a background (batch) process. These
two classes have different scheduling needs. For this kind of situation Multilevel
Queue Scheduling is used.

The description of the processes in the above diagram is as follows:

 System Processes: The CPU itself has its process to run, generally termed
as System Process.
 Interactive Processes: An Interactive Process is a type of process in
which there should be the same type of interaction.

Page 8
UNIT – II CS403PC: OPERATING SYSTEMS

 Batch Processes: Batch processing is generally a technique in the

Operating system that collects the programs and data together in the form
of a batch before the processing starts.
Advantages:
 The main merit of the multilevel queue is that it has a low scheduling
overhead.
Disadvantages:
 Starvation problem
 It is inflexible in nature

10. Multilevel Feedback Queue Scheduling:

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is
like Multilevel Queue Scheduling but in this process can move between the
queues. And thus, much more efficient than multilevel queue scheduling.
Characteristics:
 In a multilevel queue-scheduling algorithm, processes are permanently
assigned to a queue on entry to the system, and processes are not allowed
to move between queues.
 As the processes are permanently assigned to the queue, this setup has the
advantage of low scheduling overhead,
 But on the other hand disadvantage of being inflexible.
Advantages:
 It is more flexible
 It allows different processes to move between different queues
Disadvantages:
 It also produces CPU overheads
 It is the most complex algorithm.

Page 9
UNIT – II CS403PC: OPERATING SYSTEMS

Comparison between various CPU Scheduling algorithms

Here is a brief comparison between different CPU scheduling algorithms:

Average Pre Star

Algorithm Allocation is Complexity waiting time emp vatio Performa
(AWT) tion n nce

According to the
Simple and
arrival time of the
FCFS easy to Large. No No Slow
processes, the CPU
implement
is allocated.

Based on the lowest More

Smaller than
SJF CPU burst time complex No Yes Good
FCFS
(BT). than FCFS

Same as SJF the

allocation of the Depending
More
CPU is based on the on arrival
SRTF complex Yes Yes Good
lowest CPU burst time, process
than FCFS
time (BT). But it is size
preemptive.

According to the The Large than

order of the process complexity SJF and Yes
RR No Fair
arrives with fixed depends on Priority
time quantum (TQ) TQ scheduling.

According to the
Priority
priority. The bigger Less Smaller than
Pre- Yes Yes Well
priority task complex FCFS
emptive
executes first

According to the Most

Priority Less
priority with beneficial
non- complex Smaller than
monitoring the new No Yes with
preemp than Priority FCFS
incoming higher batch
tive preemptive
priority jobs systems

Page 10
UNIT – II CS403PC: OPERATING SYSTEMS

Average Pre Star

Algorithm Allocation is Complexity waiting time emp vatio Performa
(AWT) tion n nce

According to the More

process that resides complex Smaller than
MLQ No Yes Good
in the bigger queue than the FCFS
priority priority

According to the Smaller than

It is the most
MLFQ process of a bigger all No No Good
Complex
priority queue. scheduling

Example 1 (FCFS)

1. Process ID Process Name Burst Time (ms)

______ ________ _______
P1 A 6
P2 B 2
P3 C 1
P4 D 9
P5 E 8

Gantt Chart

Process Arrival Burst Completion Turn Around Waiting

ID Time Time Time (ms) Time (ms) Time
(ms) (ms) (ns)

P1 0 6 6 6 0

P2 2 2 8 8 6

P3 3 1 9 9 8

P4 4 9 18 18 9

P5 5 8 26 26 18
Average Turn Around Time = ( 6 + 8 + 9 +18 +26 ) / 5 = 67 / 5 = 13.4 ms
Average Waiting Time = ( 0 + 6 + 8 + 9 + 18 ) / 5 = 41 / 5 = 8.2 ms

Page 11
UNIT – II CS403PC: OPERATING SYSTEMS

Example 2 (FCFS)

ProcessID Process Name Burst Time

______ _______ _______
P1 A 79
P2 B 2
P3 C 3
P4 D 1
P5 E 25
P6 F 3

Process Burst Completion Turn Waiting

Id Time (BT) Time (CT) Around Time (WT)
Time (TAT)

P1 79 79 79 0

P2 2 81 81 79

P3 3 84 84 81

P4 1 85 85 84

P5 25 110 110 85

P6 3 113 113 110

Avg Waiting Time = ( 0 + 79 + 81 + 84 + 85 + 110 ) /6 = 73.17 ms

Avg Turn Around Time = ( 79 + 81 + 84 + 85 + 110 +113 ) / 6 = 92 ms

Page 12
UNIT – II CS403PC: OPERATING SYSTEMS

Example 3 (SJF)

Process ID Arrival Time Burst Time

______ _______ _______
P0 1 3
P1 2 6
P2 1 2
P3 3 7
P4 2 4
P5 5 5

Non Pre-Emptive Shortest Job First CPU Scheduling

Gantt Chart:

Process Arrival Burst Completion Turn Waiting

ID Time Time Time Around Time
Time WT=CT–BT
TAT=CT–AT

P0 1 3 5 4 1

P1 2 6 20 18 12

P2 0 2 2 2 0

P3 3 7 27 24 17

P4 2 4 9 7 4

P5 5 5 14 10 5
Average Waiting Time = ( 1 + 12 + 17 + 0 + 5 + 4 ) / 6 = 39 / 6 = 6.5 ms
Average Turn Around Time = ( 4 +18 + 2 +24 + 7 + 10 ) / 6 = 65 / 6 = 10.83 ms

Page 13
UNIT – II CS403PC: OPERATING SYSTEMS

Pre Emptive Shortest Job First CPU Scheduling

Gantt chart:

Proce Arrival Burst Comple Turn Around Time Waiting

ss ID Time Time tion TAT=CT-AT Time
Time WT=CT–BT

P0 1 3 5 4 1

P1 2 6 17 15 9

P2 0 2 2 2 0

P3 3 7 24 21 14

P4 2 4 11 9 5

P5 6 2 8 2 0
Average Turn Around Time = ( 4 +15 + 2 + 21 + 9 + 2 ) / 6 = 53 / 6 = 8.83 ms
Average Waiting Time = ( 1 + 9 + 0 + 14 + 5 + 0 ) /6 = 29 / 6 = 4.83 ms

Page 14
UNIT – II CS403PC: OPERATING SYSTEMS

Example 4 (PRIORITY)

S. No Process ID Arrival Time Burst Time Priority

___ ______ _______ _______ _______
1 P1 0 5 5
2 P2 1 6 4
3 P3 2 2 0
4 P4 3 1 2
5 P5 4 7 1
6 P6 4 6 3

(5 has the least priority and 0 has the highest priority)

Solution:

Gantt Chart:

Process Arrival Burst Priority Completion Turn Around Waiting

Id Time Time Time Time Time
TAT=CT-AT WT=TAT-BT

P1 0 5 5 5 5 0

P2 1 6 4 27 26 20

P3 2 2 0 7 5 3

P4 3 1 2 15 12 11

P5 4 7 1 14 10 3

P6 4 6 3 21 17 11
Avg Waiting Time = ( 0 + 20 + 3 + 11 + 3 + 11 ) / 6 = 48 / 6 = 8 ms
Avg Turn Around Time = ( 5 + 26 + 5 + 11 + 10 + 17 ) / 6 = 74 / 6 = 12.33 ms

Page 15
UNIT – III CS403PC: OPERATING SYSTEMS

Example 5 (Round Robin)

Time Quantum = 1 ms

Process ID Arrival Time Burst Time

P0 1 3

P1 0 5

P2 3 2

P3 4 3

P4 2 1

Solution:

Gantt
Chart:

Process Arrival Burst Completion Turn Waiting

ID Time Time Time Around Time
Time

P0 1 3 5 4 1

P1 0 5 14 14 9

P2 3 2 7 4 2

P3 4 3 10 6 3

P4 2 1 3 1 0

Avg Turn Around Time = (4+14+4+6+1) / 5 = 5.8 ms

Avg Waiting Time = (1+9+2+3+0) / 5 = 3 ms

Page 1
UNIT – III CS403PC: OPERATING SYSTEMS

Multiple – processor scheduling:

When multiple processes are available, then the scheduling gets more complicated, because
there is more than one CPU which must be kept busy and in effective use at all times.
Load sharing resolves around balancing the load between multiple processors. Multi
processor systems may be heterogeneous (It contains different kinds of CPU’s) ( or )
Homogeneous(all the same kind of CPU).

1) Approaches to multiple-processor scheduling

a)Asymmetric multiprocessing
One processor is the master, controlling all activities and running all kernel code, while the
other runs only user code.
b)Symmetric multiprocessing:
Each processor schedules its own job. Each processor may have its own private queue of
readyprocesses.

2) Processor Affinity
Successive memory accesses by the process are often satisfied in cache memory. what
happens if the process migrates to another processor. the contents of cache memory must be
invalidated for the first processor, cache for the second processor must be repopulated. Most
Symmetric multi processor systems try to avoid migration of processes from one processor
to another processor, keep a process running on the same processor. This is called processor
affinity.

a) Soft affinity:
Soft affinity occurs when the system attempts to keep processes on the same processor but
makes no guarantees.

b) Hard affinity:
Process specifies that it is not to be moved between processors.

3) Load balancing:

One processor wont be sitting idle while another is overloaded. Balancing can be
achived through push migration or pull migration.
Push migration:
Push migration involves a separate process that runs periodically(e.g every 200 ms)

Page 2
 UNIT – III CS403PC: OPERATING SYSTEMS

and moves processes from heavily loaded processors onto less loaded processors.
Pull migration:
Pull migration involves idle processors taking processes from the ready queues of
the otherprocessors.

Multiple-Level Queues Scheduling

Multiple-level queues are not an independent scheduling algorithm. They make use of other existing
algorithms to group and schedule jobs with common characteristics.

 Multiple queues are maintained for processes with common characteristics.

 Each queue can have its own scheduling algorithms.

 Priorities are assigned to each queue.

For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another queue.
The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU
based on the algorithm assigned to the queue.

Multiple Processor Scheduling

In multiple-processor scheduling multiple CPU’s are available and hence Load Sharing becomes
possible. However multiple processor scheduling is more complex as compared to single processor
scheduling. In multiple processor scheduling there are cases when the processors are identical i.e.
HOMOGENEOUS, in terms of their functionality, we can use any processor available to run any
process in the queue.

Approaches to Multiple-Processor Scheduling –

One approach is when all the scheduling decisions and I/O processing are handled by a single processor
which is called the Master Server and the other processors executes only the user code. This is simple
and reduces the need of data sharing. This entire scenario is called Asymmetric Multiprocessing.

Page 3
 UNIT – III CS403PC: OPERATING SYSTEMS

A second approach uses Symmetric Multiprocessing where each processor is self scheduling. All
processes may be in a common ready queue or each processor may have its own private queue for ready
processes. The scheduling proceeds further by having the scheduler for each processor examine the
ready queue and select a process to execute.

Real-Time Scheduling
Real time system means that the system is subjected to real time, i.e., response should be guaranteed
within a specified timing constraint or system should meet the specified deadline. For example: flight
control system, real time monitors etc.

Types of real time systems based on timing constraints:

1. Hard real time system –

This type of sytem can never miss its deadline. Missing the deadline may have disastrous
[Link] usefulness of result produced by a hard real time system decreases abruptly
and may become negative if tardiness increases. Tardiness means how late a real time system
completes its task with respect to its deadline. Example: Flight controller system.
2. Soft real time system –
This type of system can miss its deadline occasionally with some acceptably low probability.
Missing the deadline have no disastrous consequences. The usefulness of result produced by a
soft real time system decreases gradually with increase in tardiness. Example: Telephone
switches.

Thread Scheduling

Every thread has a thread priority assigned to it. Threads created within the common language runtime
are initially assigned the priority of [Link]. Threads created outside the runtime retain
the priority they had before they entered the managed environment. You can get or set the priority of
any thread with the [Link] property.

Threads are scheduled for execution based on their priority. Even though threads are executing within
the runtime, all threads are assigned processor time slices by the operating system. The details of the
scheduling algorithm used to determine the order in which threads are executed varies with each

Page 4
 UNIT – III CS403PC: OPERATING SYSTEMS

operating system. Under some operating systems, the thread with the highest priority (of those threads
that can be executed) is always scheduled to run first.

If multiple threads with the same priority are all available, the scheduler cycles through the threads at
that priority, giving each thread a fixed time slice in which to execute. As long as a thread with a higher
priority is available to run, lower priority threads do not get to execute. When there are no more
runnable threads at a given priority, the scheduler moves to the next lower priority and schedules the
threads at that priority for execution. If a higher priority thread becomes runnable, the lower priority
thread is preempted and the higher priority thread is allowed to execute once again.

On top of all that, the operating system can also adjust thread priorities dynamically as an application's
user interface is moved between foreground and background. Other operating systems might choose to
use a different scheduling algorithm.

Page 5
 UNIT – III CS403PC: OPERATING SYSTEMS

SYSTEM CALL INTERFACE FOR PROCESS MANAGEMENT

System call provides an interface between user program and operating system. The structure of system

all is as follows −

When the user wants to give an instruction to the OS then it will do it through system calls. Or a user
program can access the kernel which is a part of the OS through system calls.

It is a programmatic way in which a computer program requests a service from the kernel of the
operating system.

Types of system calls

The different system calls are as follows −

 System calls for Process management

 System calls for File management
 System calls for Directory management

Now let us discuss process management system calls.

System calls for Process management

A system is used to create a new process or a duplicate process called a fork.

The duplicate process consists of all data in the file description and registers common. The original
process is also called the parent process and the duplicate is called the child process.

The fork call returns a value, which is zero in the child and equal to the child’s PID (Process Identifier)
in the parent. The system calls like exit would request the services for terminating a process.

Page 6
 UNIT – III CS403PC: OPERATING SYSTEMS

Loading of programs or changing of the original image with duplicate needs execution of exec. Pid
would help to distinguish between child and parent processes.

Example

Process management system calls in Linux.

 fork − For creating a duplicate process from the parent process.

 wait − Processes are supposed to wait for other processes to complete their work.
 exec − Loads the selected program into the memory.
 exit − Terminates the process.

The pictorial representation of process management system calls is as follows −

fork() − A parent process always uses a fork for creating a new child process. The child process is
generally called a copy of the parent. After execution of fork, both parent and child execute the same
program in separate processes.

exec() − This function is used to replace the program executed by a process. The child sometimes may
use exec after a fork for replacing the process memory space with a new program executable making
the child execute a different program than the parent.

exit() − This function is used to terminate the process.

Page 7
 UNIT – III CS403PC: OPERATING SYSTEMS

wait() − The parent uses a wait function to suspend execution till a child terminates. Using wait the
parent can obtain the exit status of a terminated child.

waitpid( ):

The waitpid() system call

This system call waits for a specific process to finish its execution. This system call can be accessed
using our C programs' library sys/wait.h.

Let's understand how the waitpid() function works with the help of a diagram.

The diagram shows that we have a parent process with 3 child processes, namely, Child1, Child2, and
Child3. If we want the parent to wait for a specific child, we could use the waitpid() function.

In the diagram above, we made the parent process wait for Child1 to finish its execution using the
function. When the parent process is called, the waitpid() function gets blocked by the operating
system and can't continue its execution till the specified child process Child1 is terminated.

If we were to replace the process in the waitpid() function with Child3, then the parent would only
continue when Child3 had terminated.

Hence, we see that we can use the waitpid() function to make parent processes wait for a specific
child process before continuing execution.

Page 8
 UNIT – III CS403PC: OPERATING SYSTEMS

Syntax

Below, we can see the syntax for the waitpid() system call.

pid_t waitpid(pid_t pid, int *status_ptr, int options);

Let's discuss the three arguments that we provide to the system call.

 pid: Here, we provide the process ID of the process we want to wait for. If the provided pid is
0, it will wait for any arbitrary child to finish.
 status_ptr: This is an integer pointer used to access the child's exit value. If we want to ignore
the exit value, we can use NULL here.
o options: Here, we can add additional flags to modify the function's behavior. The
various flags are discussed below:

Return value

Now that we have gone through the syntax, let's discuss what the system call returns after executing.

The system call will return the process ID of the child process that was terminated. If there is any error
while waiting for the child process via the waitpid() system call, it will return -1, which corresponds
to an error.

Page 9
UNIT – III CS403PC: OPERATING SYSTEMS

DEADLOCK
A process in operating system uses resources in the following way.
(i) Requests a resource
(ii) Use the resource
(iii) Releases the resource
A deadlock is a situation where a set of processes are blocked because
each process is holding a resource and waiting for another resource
acquired by some other process.
Consider an example when two trains are coming toward each other on
the same track and there is only one track, none of the trains can move
once they arein front of each other.
A similar situation occurs in operating
systems when there are two or more
processes that hold some resources and
wait for resources held by other(s). For
example, in the below diagram, Process1 is
holding Resource1 and waiting for Rsource2
which is acquired by Process2, and Process2
is waiting for Resource1.

Examples of Deadlock
1. The system has 2 tape drives. P1 and P2 each hold one tape drive and each
needs another one.
2. Semaphores A and B, initialized to 1, P0, and P1 are
P0 P1
in deadlock as follows:
P0 executes wait(A) and preempts.
wait(A); wait(B)
P1 executes wait(B).
Now P0 and P1 enter in deadlock.
wait(B); wait(A)

Page 10
UNIT – III CS403PC: OPERATING SYSTEMS

3. Assume the space is available for allocation of 200K bytes, and the
following sequence of events occurs.
P0 P1

Request Request
80KB; 70KB;

Request Request
60KB; 80KB;

Page 11
UNIT – III CS403PC: OPERATING SYSTEMS

NECESSARY CONDITIONS FOR DEADLOCK

 Mutual Exclusion
Two or more resources are non-shareable (Only one process can
use at a time)
 Hold and Wait
A process is holding at least one resource and waiting for
resources.
 No Pre-emption
A resource cannot be taken from a process unless the process
releases the resource.
 Circular Wait
A set of processes waiting for each other in circular form.

Resource Allocation Graph

The resource allocation graph is the pictorial representation of the
state of a system. As its name suggests, the resource allocation graph is the
complete information about all the processes which are holding some
resources or waiting for some resources.
It also contains the information about all the instances of all the
resources whether they are available or being used by the processes.
In Resource allocation graph, the process is represented by a Circle
while the Resource is represented by a rectangle.
Vertices are mainly of two types, Resource and Process. Each of
them will be represented by a different shape. Circle represents process
while rectangle represents resource. A resource can have more than one
instance. Each instance will be represented by a dot inside the rectangle.
Edges in RAG are also of two
types, one represents Assignment
Edge and other represents the wait of
a process for a resource [Link]
Edge.
A resource is shown as
assigned to a process if the tail of the
arrow is attached to an instance to the
resource and the head is attached to a
process.
A process is shown as waiting for a resource if the tail of an arrow is
attached to the process while the head is pointing towards the resource.
Page 12
UNIT – III CS403PC: OPERATING SYSTEMS

Example
Consider 3 processes P1, P2 and P3
and two types of resources R1 and R2. The
resources are having 1 instance each.
According to the graph, R1 is being
used by P1, P2 is holding R2 and waiting for
R1, P3 iswaiting for R1 as well as R2.
The graph is deadlock free since no
cycle is being formed in the graph.

Using Resource Allocation Graph, it can be easily detected whether

systemis in a Deadlock state or not. The rules are

Rule-01: In a Resource Allocation Graph where all the resources are single
instance,
 If a cycle is being formed, then system is in a deadlock state.
 If no cycle is being formed, then system is not in a deadlock state.

Rule-02: In a Resource Allocation Graph where all the resources are

NOT singleinstance,
 If a cycle is being formed, then system may be in a deadlock state.
 Banker’s Algorithm is applied to confirm whether system is in a deadlock
state or not.
 If no cycle is being formed, then system is not in a deadlock state.
 Presence of a cycle is a necessary but not a sufficient condition for the
occurrence of deadlock.

Page 13
UNIT – III CS403PC: OPERATING SYSTEMS

METHODS FOR HANDLING DEADLOCK

There are three ways to handle deadlock
1) Deadlock prevention or avoidance
PREVENTION
The idea is to not let the system into a deadlock state. This
system will make sure that above mentioned four conditions will not arise.
These techniques are very costly so we use this in cases where our priority
is making a system deadlock-free.
One can zoom into each category individually, Prevention is done
by negating one of the four necessary conditions for deadlock.

Eliminate mutual exclusion

It is not possible to dis-satisfy the mutual exclusion because some
resources, such as the tape drive and printer, are inherently non-shareable.

Solve hold and Wait

Allocate all required resources to the process before the start of its
execution, this way hold and wait condition is eliminated but it will lead to
low device utilization. for example, if a process requires a printer at a later
time and we have allocated a printer before the start of its execution
printer will remain blocked till it has completed its execution. The process
will make a new request for resources after releasing the current set of
resources. This solution may lead to starvation.

Allow pre-emption
Preempt resources from the process when resources are required by
otherhigh-priority processes.

Circular wait Solution

Each resource will be assigned a numerical number. A process can
request the resources to increase/decrease. order of numbering. For
Example, if the P1 process is allocated R5 resources, now next time if P1
asks for R4, R3 lesser than R5 such a request will not be granted, only a
request for resources more than R5 will be granted.

AVOIDANCE
Avoidance is kind of futuristic. By using the strategy of
“Avoidance”, we have to make an assumption. We need to ensure that all
information about resources that the process will need is known to us

Page 14
UNIT – III CS403PC: OPERATING SYSTEMS

before the execution of the process.

Page 15
UNIT – III CS403PC: OPERATING SYSTEMS

Resource Allocation Graph

The resource allocation graph (RAG) is used to visualize the
system‟s current state as a graph. The Graph includes all processes, the
resources that are assigned to them, as well as the resources that each
Process requests. Sometimes, if there are fewer processes, we can quickly
spot a deadlock in the system by looking at the graph rather than the tables
we use in Banker‟s algorithm.
Banker’s Algorithm
Bankers‟s Algorithm is a resource allocation and deadlock
avoidance algorithm which test all the request made by processes for
resources, it checks for the safe state, and after granting a request system
remains in the safe state it allows the request, and if there is no safe state it
doesn‟t allow the request madeby the process.

In prevention and avoidance, we get the correctness of data but

performance decreases.

2) Deadlock detection and recovery

If Deadlock prevention or avoidance is not applied to the software
then wecan handle this by deadlock detection and recovery, which consist
of two phases.
In the first phase, we examine the state of the process and check
whether there is a deadlock or not in the system.
If found deadlock in the first phase then we apply the algorithm for
recovery of the deadlock.

3) Deadlock ignorance:
If a deadlock is very rare, then let it happen and reboot the system.
This is the approach that both Windows and UNIX take. We use the
ostrich algorithmfor deadlock ignorance.
In Deadlock, ignorance performance is better than the above two
methods but not the correctness of data.

SAFE STATE
A safe state can be defined as a state in which there is no deadlock.
It is achievable if:
 If a process needs an unavailable resource, it may wait until the same has
been released by a process to which it has already been allocated. if such a
sequence does not exist, it is an unsafe state.
Page 16
UNIT – III CS403PC: OPERATING SYSTEMS

 All the requested resources are allocated to the process.

Page 17
UNIT – III CS403PC: OPERATING SYSTEMS

BANKER'S ALGORITHM
It is a banker algorithm used to avoid deadlock and allocate
resources safely to each process in the computer system. The 'S-State'
examines all possible tests or activities before deciding whether the
allocation should be allowed to each process. It also helps the operating
system to successfully sharethe resources between all the processes.
The banker's algorithm is named because it checks whether a person
should be sanctioned a loan amount or not to help the bank system safely
simulate allocation resources.
Suppose the number of account holders in a particular bank is 'n',
and the total money in a bank is 'T'. If an account holder applies for a loan;
first, the bank subtracts the loan amount from full cash and then estimates
the cash difference is greater than T to approve the loan amount. These
steps are taken because if another person applies for a loan or withdraws
some amount from the bank, it helps the bank manage and operate all
things without any restriction in the functionality of the banking system.
Similarly, it works in an operating system. When a new process is
created in a computer system, the process must provide all types of
information to the operating system like upcoming processes, requests for
their resources, counting them, and delays.
Based on these criteria, the operating system decides which process
sequence should be executed or waited so that no deadlock occurs in a
system. Therefore, it is also known as deadlock avoidance algorithm or
deadlock detection in the operating system.

When working with a banker's algorithm, it requests to know

about threethings:
1. How much each process can request for each resource in the system. It is
denoted by the [MAX] request.
2. How much each process is currently holding each resource in a system. It is
denoted by the [ALLOCATED] resource.
3. It represents the number of each resource currently available in the system.
It is denoted by the [AVAILABLE] resource.

Page 18
UNIT – III CS403PC: OPERATING SYSTEMS

Following are the important data structures terms applied in the banker's
algorithm as follows:
Suppose n is the number of processes, and m is the number of each type
of resource used in a computer system.
1. Available: It is an array of length 'm' that defines each type of resource
available in the system. When Available[j] = K, means that 'K' instances of
Resources type R[j] are available in the system.
2. Max: It is a [n x m] matrix that indicates each process P[i] can store the
maximum number of resources R[j] (each type) in a system.
3. Allocation: It is a matrix of m x n orders that indicates the type of
resources currently allocated to each process in the system. When
Allocation [i, j] = K, it means that process P[i] is currently allocated K
instances of Resources type R[j] in the system.
4. Need: It is an M x N matrix sequence representing the number of
remaining resources for each process. When the Need[i] [j] = k, then
process P[i] may require K more instances of resources type Rj to complete
the assigned work.
Need[i][j] = Max[i][j] - Allocation[i][j].
5. Finish: It is the vector of the order m. It includes a Boolean value
(true/false) indicating whether the process has been allocated to the
requested resources, and all resources have been released after finishing its
task.

The Banker's Algorithm is the combination of the safety algorithm

and theresource request algorithm to control the processes and avoid
deadlock.
Safety Algorithm
It is a safety algorithm used to check whether or not a system is in
a safestate or follows the safe sequence in a banker's algorithm:
Step1:
There are two vectors Wok and Finish of length m and n in a
safetyalgorithm.
Initialize: Work = Available
Finish[i] = false; for I = 0, 1, 2, 3, 4… n - 1.
Step2:
Check the availability status for each type of resources [i], such as:
Need[i] <= Work
Finish[i] == false
Page 19
 UNIT – III CS403PC: OPERATING SYSTEMS

Step3:
Work = Work +Allocation(i) // to get new resource allocation
Finish[i] = true
Go to step2 to check the status of resource availability for the next process.
Step4:
If Finish[i] == true; it means that the system is safe for all processes.

Resource Request Algorithm

Let create a resource request array R[i] for each process P[i].
Step1:
When the number of requested resources of each type is less than
the Need resources, go to step2 and if the condition fails, which means that
the process P[i] exceeds its maximum claim for the resource. As the
expressionsuggests:
If Request(i) <= Need, then go to step2, Else raise an error message.
Step2:
And when the number of requested resources of each type is less than the
available resource for each process, go to step (3). As the expression suggests:
If Request(i) <= Available, then go to step3.
Else Process P[i] must wait for the resource.
Step3:
When the requested resource is allocated to the process by changing state:
Available = Available – Request
Allocation(i) = Allocation(i) + Request (i)
Needi = Needi - Requesti

When the resource allocation state is safe, its resources are allocated
to the process P(i). And if the new state is unsafe, the Process P (i) has to
wait for each type of Request R(i) and restore the old resource-allocation
state.

Page 20
UNIT – III CS403PC: OPERATING SYSTEMS

Example:
Consider a system that contains five processes P1, P2, P3, P4, P5
and the three resource types A, B and C. Following are the resources types:
A has 10, B has 5 and the resource type C has 7 instances.

Process Allocation Max Available

A B C A B C A B C
P1 0 1 0 7 5 3 3 3 2

P2 2 0 0 3 2 2

P3 3 0 2 9 0 2

P4 2 1 1 2 2 2

P5 0 0 2 4 3 3
Answer the following questions using the banker's algorithm:
1. What is the reference of the need matrix?
2. Determine if the system is safe or not.
3. What will happen if the resource request (1, 0, 2) for process P1 can the
system accept this request immediately?
4. What will happen if the resource request (3, 3, 0) for process P5?
5. What will happen if the resource request (0, 2, 0) for process P1?

Ans.1:
Context of the need matrix is as Need [i] = Max [i] - Allocation [i]
Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2 Process Need
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0 A B C
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
P1 7 4 3
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

P2 1 2 2
P3 6 0 0

P4 0 1 1
P5 4 3 1

Page 21
UNIT – III CS403PC: OPERATING SYSTEMS

Ans.2: Apply the Banker's Algorithm:

Available Resources of A, B and C are 3, 3, and 2.
Now we check if each type of resource request is available for each
process.
Step 1:
For Process P1:
Need <= Available
7, 4, 3 <= 3, 3, 2 condition is false.
So, we examine another process, P2.
Step 2:
For Process P2:
Need <= Available
1, 2, 2 <= 3, 3, 2 condition true
New available = available + Allocation
(3, 3, 2) + (2, 0, 0) => 5, 3, 2
Similarly, we examine another process P3.
Step 3:
For Process P3:
P3 Need <= Available
6, 0, 0 < = 5, 3, 2 condition is false.
Similarly, we examine another process, P4.
Step 4:
For Process P4:
P4 Need <= Available
0, 1, 1 <= 5, 3, 2 condition is true
New Available resource = Available + Allocation
5, 3, 2 + 2, 1, 1 => 7, 4, 3
Similarly, we examine another process P5.
Step 5:
For Process P5:
P5 Need <= Available
4, 3, 1 <= 7, 4, 3 condition is true
New available resource = Available + Allocation
7, 4, 3 + 0, 0, 2 => 7, 4, 5
Now, we again examine each type of resource request for
processes P1 and P3.

Page 22
UNIT – III CS403PC: OPERATING SYSTEMS

Step 6:
For Process P1:
P1 Need <= Available
7, 4, 3 <= 7, 4, 5 condition is true
New Available Resource = Available + Allocation
7, 4, 5 + 0, 1, 0 => 7, 5, 5
So, we examine another process P2.
Step 7:
For Process P3:
P3 Need <= Available
6, 0, 0 <= 7, 5, 5 condition is true
New Available Resource = Available + Allocation
7, 5, 5 + 3, 0, 2 => 10, 5, 7
Hence, we execute the banker's algorithm to find the safe state and
the safesequence like P2, P4, P5, P1 and P3.

Ans. 3:
For granting the Request (1, 0, 2), first we have to check that
Request <= Available, that is (1, 0, 2) <= (3, 3, 2),
Since the condition is true, the process
P2 may get the request immediately.
Process Need
Allocation for P2 is (3,0,2) and new A B C
Availableis (2, 3, 0)
Context of the need matrix is as follows: P1 7 4 3
Need [i] = Max [i] - Allocation [i] P2 0 2 0
Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (3, 0, 2) = 0, 2, 0 P3 6 0 0
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
P4 0 1 1
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1 P5 4 3 1

Apply the Banker's Algorithm:

Available Resources of A, B and C are 2, 3, and 0.
Now we check if each type of resource request is available for each
process.

Page 23
UNIT – III CS403PC: OPERATING SYSTEMS

Step 1:
For Process P1:
Need <= Available
7, 4, 3 <= 2, 3, 0 condition is false.
So, we examine another process, P2.
Step 2:
For Process P2:
Need <= Available
1, 2, 2 <= 2, 3, 0 condition true
New available = available + Allocation
(2, 3, 0) + (3, 0, 2) => 5, 3, 2
Similarly, we examine another process P3.
Step 3:
For Process P3:
P3 Need <= Available
6, 0, 0 < = 5, 3, 2 condition is false.
Similarly, we examine another process, P4.
Step 4:
For Process P4:
P4 Need <= Available
0, 1, 1 <= 5, 3, 2 condition is true
New Available resource = Available + Allocation
5, 3, 2 + 2, 1, 1 => 7, 4, 3
Similarly, we examine another process P5.
Step 5:
For Process P5:
P5 Need <= Available
4, 3, 1 <= 7, 4, 3 condition is true
New available resource = Available + Allocation
7, 4, 3 + 0, 0, 2 => 7, 4, 5
Now, we again examine for processes P1 and P3.
Step 6:
For Process P1:
P1 Need <= Available
7, 4, 3 <= 7, 4, 5 condition is true
New Available Resource = Available + Allocation
7, 4, 5 + 0, 1, 0 => 7, 5, 5
So, we examine another process P2.
Page 24
UNIT – III CS403PC: OPERATING SYSTEMS

Step 7:
For Process P3:
P3 Need <= Available
6, 0, 0 <= 7, 5, 5 condition is true
New Available Resource = Available + Allocation
7, 5, 5 + 3, 0, 2 => 10, 5, 7
Hence, P2 granted immediately and the safe sequence like P2, P4,
P5, P1and P3.

Ans. 4:
For granting the Request (3, 3, 0) by P5, first we have to check that
Request <= Available, that is (3, 3, 0) <= (2, 3, 0),
Since the condition is false. So the request for (3, 3, 0) by
process P5cannot be granted.

Ans. 5:
For granting the Request (0, 2, 0) by P1, first we have to check that
Request <= Available, that is (0, 2, 0) <= (2, 3, 0),
Since the condition is true. So the request for (0, 2, 0) by process P1
may be granted.
Allocation for P1 is (0, 3, 0) Process Need
Context of the need matrix is as A B
follows:Need [i] = Max [i] - Allocation C
[i]
P1 7 2 3
Need for P1: (7, 5, 3) - (0, 3, 0) = 7, 2, 3
P2 0 2 0

Apply the Banker's Algorithm:

P3 6 0 0
Available Resources of A, B and C are 2, 1,
and 0. P4 0 1 1

P5
For Process P1: 7, 2, 3<= 2, 1, 0 condition is false. 4 3 1
For Process P2: 0, 2, 0<= 2, 1, 0 condition is false.
For Process P3: 6, 0, 0<= 2, 1, 0 condition is false.
For Process P4: 0, 1, 1 <= 2, 1, 0 condition is false.
For Process P5: 4, 3, 1 <= 2, 1, 0 condition is false.

Hence, the state is unsafe, P1 cannot be granted immediately.

Page 25
UNIT – III CS403PC: OPERATING SYSTEMS

DEADLOCK DETECTION
If a system does not employ either a deadlock prevention or
deadlockavoidance algorithm then a deadlock situation may occur. In this
case-
 Apply an algorithm to examine the system‟s state to determine whether
deadlock has occurred.
 Apply an algorithm to recover from the deadlock.

A deadlock detection algorithm is a technique used by an operating

system to identify deadlocks in the system. This algorithm checks the status
of processes and resources to determine whether any deadlock has occurred
and takes appropriate actions to recover from the deadlock.
The algorithm employs several times varying data structures:
Available – A vector of length m indicates the number of available resources
of each type.
Allocation – An n*m matrix defines the number of resources of each type
currently allocated to a process. The column represents resource and rows
represent a process.
Request – An n*m matrix indicates the current request of each process. If
request[i][j] equals k then process Pi is requesting k more instances of resource
type Rj.

The Bankers algorithm includes a Safety Algorithm / Deadlock Detection

Algorithm. The algorithm for finding out whether a system is in a safe state can
be described as follows:
Steps of Algorithm:
1. Let Work and Finish be vectors of length m and n respectively.
Initialize Work= Available. For i=0, 1, …., n-1,
if Requesti = 0, then Finish[i] = true;
otherwise, Finish[i]= false.
2. Find an index i such that both
a) Finish[i] == false
b) Requesti <= Work
If no such i exists go to step 4.
3. Work= Work+ Allocationi
Finish[i]= true
Go to Step 2.
4. If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked

Page 26
UNIT – III CS403PC: OPERATING SYSTEMS

state. Moreover, if Finish[i]==false the process Pi is deadlocked.

Page 27
UNIT – III CS403PC: OPERATING SYSTEMS

For example,

1. In this, Work = [0, 0, 0] &

Finish = [false, false, false, false, false]

2. i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].

3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].

4. i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0,

1, 0].5. Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].

6. i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3,

1, 3].7. Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].

8. i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5,

1, 3].9. Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].

10. i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7,

2, 4].11. Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].

12. Since Finish is a vector of all true it means there is no deadlock in this
example.

Page 28
UNIT – III CS403PC: OPERATING SYSTEMS

There are several algorithms for detecting deadlocks in an operating

system,including:

1. Wait-For Graph:
A graphical representation of the system‟s processes and resources. A
directed edge is created from a process to a resource if the process is
waiting for that resource. A cycle in the graph indicates a deadlock.

2. Banker’s Algorithm:
A resource allocation algorithm that ensures that the system is always in
a safe state, where deadlocks cannot occur.

3. Resource Allocation Graph:

A graphical representation of processes and resources, where a directed
edge from a process to a resource means that the process is currently
holding that resource. Deadlocks can be detected by looking for cycles in
the graph.

4. Detection by System Modeling:

A mathematical model of the system is created, and deadlocks can be
detected by finding a state in the model where no process can continue to
make progress.

5. Timestamping:
Each process is assigned a timestamp, and the system checks to see
if any process is waiting for a resource that is held by a process with a
lower timestamp.

These algorithms are used in different operating systems and

systems with different resource allocation and synchronization
requirements. The choice of algorithm depends on the specific requirements
of the system and the trade-offs between performance, complexity and
accuracy.

Page 29
UNIT – III CS403PC: OPERATING SYSTEMS

RECOVERY FROM DEADLOCK

The OS will use various recovery techniques to restore the system if
it encounters any deadlocks. When a Deadlock Detection Algorithm
determines that a deadlock has occurred in the system, the system must
recover from that deadlock.

Approaches to Breaking a Deadlock

(a) Process Termination

To eliminate the deadlock, we can simply kill one or more processes.
For this, we use two methods:
1. Abort all the Deadlocked Processes:
Aborting all the processes will certainly break the deadlock but at a great
expense. The deadlocked processes may have been computed for a long time,
and the result of those partial computations must be discarded and there is a
probability of recalculating them later.
2. Abort one process at a time until the deadlock is eliminated:
Abort one deadlocked process at a time, until the deadlock cycle is
eliminated from the system. Due to this method, there may be considerable
overhead, because, after aborting each process, we have to run a deadlock
detection algorithm to check whether any processes are still deadlocked.

(b) Resource Preemption

To eliminate deadlocks using resource preemption, we preempt some
resources from processes and give those resources to other processes. This
method will raise three issues –
1. Selecting a victim:
We must determine which resources and which processes are to be
preempted and also in order to minimize the cost.
2. Rollback:
We must determine what should be done with the process from which
resources are preempted. One simple idea is total rollback. That means
aborting the process and restarting it.
3. Starvation:
In a system, it may happen that the same process is always picked as a
victim. As a result, that process will never complete its designated task. This
situation is called Starvation and must be avoided. One solution is that a
process must be picked as a victim only a finite number of times.

Page 30
UNIT – III CS403PC: OPERATING SYSTEMS

Page 31