Deadlock Characterization

Deadlocks can be characterized by four cond,·t·ions, known as Coff d' •

for a deadlock to occur: man con it,ons, which must hold
a) Mutual Exclusion: A resource can be used by a t most one process at a time
.
b) Hold and Wait: A process is currently holding at least one reso _-.
currently being held by other processes. urce and waiting for resources

c) No Preempti~n: Resources cannot be preempted from a process. They must be released by the
process holding them.
d) · · processes such that PO is waiting fo
Circular Wait: There must be a set (PO , Pl , •··, p n ) of waiting
a resource held by Pl, Pl is waiting for a resource held by P2, and so on, with Pn waiting f r
resource held by PO. or a

Methods for Handling Deadlocks

Deadlocks can be handled in three ways: prevention1 avoidance1 and detection & recovery.
a) Deadlock Prevention: This method negates one of the Coffman conditions to prevent deadlocks.
For example, a system could use resource hierarchy to prevent circular wait.
b) Deadlock Avoidance: This method involves dynamic checks to ensure that a system remains in a
safe state (where no deadlocks can occur) when a resource is requested. The· Banker's algorithm
is a common technique used for deadlock avoidance. ·
r -

c) Deadlock Detection and Recovery: In this method, the system does not prevent or avoid
deadlocks, but instead, it detects when a deadlock has occurred and then recovers from it. This
can involve identifying and terminating one or more processes involved in the deadlock, or
progressively rolling back processes to a safe state.

Deadlock Prevention
Deadlock prevention is a set of strategies to ensure that at least one of the Coffman conditions
(Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) is not met, and hence, deadlocks
cannot occur. Here's how each of these conditions can be addressed:
a) Mutual Exclusion: This condition is often necessary for correct behavior, so it's hard to prevent.
However, careful design can sometimes limit the need for mutual exclusion.
b) Hold and Wait: This condition can be prevented by requiring that a process request all its
resources at once before it begins execution, or by requiring that a process release all its
resources before it requests another. Both strategies can be too restrictive and can lead to other
problems like low resource utilization.
c) No Preemption: This condition can be prevented by allowing resources to be forcibly taken from
a process if it requests another resource that is already held by another process. However, this
can be difficult to implement, especially if the resource has some internal state or data that

needs to be saved and restored.

d) Circular Wait: This cond 1·t·
ion can be prevent db d f · ·
and requiring that e Y e ming a linear ordering of resource types
a process request re . . .
prevent circular wait b t ·t sources rn an increasing order of enumeration. This can
, u , can also be t · -
res nct,ve and may result in resource underutilization.

Deadlock Avoidance
Deadlock av0 1· d · .
ance 1s a dynamic strate th t · I •
state whenever a re . gy a invo ves making sure that a system remains in a safe
rocesses that f~~urce is requested. A safe state is one in which there exists a sequence of
P can in1sh even if all oth .
algorithm . II k ~r processes request their maximum resources. The Banker's
15
a we - nown deadlock avoidance algorithm
It is called "Banker" b · • l'k · · ·
. ecause its I e a bank deciding whether to grant a loan to a customer based on
avai lable resources and th • ·
e customers maximum needs, such that the bank remains solvent.

Banker's Algorithm
The Banker's Algorithm is a resource allocation and deadlock avoidance algorithm developed by
Edsger Dijkstra. It tests for safety by simulating the allocation of predefined maximum possible
amounts of all resources and then makes a state test to check for possible deadlock conditions for all
other pending activities, before deciding whether allocation should be allowed to continue.
. .

The Banker's Algorithm involves three data structures:

• Available: It is a 10 array that tells how many resources are available of each type.
• Max: It is a 20 array that defines the maximum demand of each customer.
• Allocation: It is a 2D array that defines the number of resources of each type currently allocated
to each customer.
• Need: It is a 20 array that indicates the remaining resource need of each customer, where
Need(i]U] = Max[i][j] -Allocation[i]U].
The Banker's Algorithm works as follows:

Calculate the Need matrix.

• Find a process whose needs can be satisfied by the available resources.
• If such a process is found, pretend to allocate the resources to this process, and add the resources
of this process to the available resources.
• Repeat steps 2 and 3 until either all processes are finished or no process can proceed.
• If all processes finish, the system is in a safe state. If not, the system is in an unsafe st ate and
could result in deadlock.

Example: · cD d
Example banker's algorithm with following snapshot of a system with resources A, B, 1
an
process PO to P4
Max
ABCD
PO 601 2
p11 7 5 2
p2 2 3 5 6
p3 16 5 3
p416 5 6

Allocation
ABCD
PO 4001
Pl 110 0
P212 5 4
P3 O 6 3 3
P40 212

Available
ABCD
3211
Max matrix:

Answer:
Calculate the Need matrix:
Need[i}U] = Max[i}[j] - Allocation[i]U]

ABCD
PO 2011
Pl O 6 5 2
P2110 2
P3 10 2 0
P4 l 444

Start the algorithm to check for a safe sequence.

The algorithm goes through the processes and checks if any of them has a Need that is less than or
equal to the available resources. If it finds such a process, it assumes that the process finishes and
adds its resources to the available resources. It then checks again. This is repeated until a safe
sequence is found or no more processes can finish.

After executing the algorithm, the safe sequence is: Pl-> P3 ->PO-> P2 -> P4.

So, the system Is In a safe state with this resource allocation.

Deadlock Detection
Deadlock detection involves periodically checking the system's state to see if a deadlock has
occurred. This is typically done using a wait-for graph, which is a directed graph where the nodes
represent processes, and the edges represent resource allocation and requests. If the graph contains
a cycle, a deadlock exists. The algorithm to detect a cycle in the graph can be the Depth First Search
{OFS) algorithm or similar algorithms. Deadlock detection is more permissive than deadlock
avoidance or prevention, as it allows more concurrency. However, it also requires additional
computation to detect deadlocks and possibly roll back or restart processes.

Recovery from Deadlock

Once a deadlock is detected, the system must recover from it. There are several strategies for
recovery:
a) Process Termination: This involves terminating one or more processes involved in the deadlock.
This could be random, or based on some criteria like priority, how long the process has been
running, or how much progress it has made.
b) Resource Preemption: This involves forcibly taking resources from a process involved in the
deadlock and allocating them to other processes. This can be risky because it might lead to
inconsistent states.
c) Process Rollback: This involves rolling back one or more processes to some previously defined
safe state (checkpoint), and then restarting them. This is safer than· resource preemption but
requires that the system maintains checkpoints and state information.
d) Killing and Restarting Processes: This involves killing all processes involved in the deadlock and
restarting them. This is the simplest method but may result in loss of data or work.

Device management
Devices and their Characteristics
Devices in computer systems are classified into different categories based on their characteristics.
They can be input devices, output devices, storage devices, communication devices, etc. Each device
has its own set of characteristics:
a) Device Speed: The speed at which a device can operate and transfer data. For example, a hard
drive will be slower than RAM.
b) Doto Rote: The rate at which data can be transferred between the device and the computer
system. For example, USB 3.0 has a higher data rate than USB 2.0.
c) Volatility: Whether the device retains data when power is turned off. RAM is volatile, while hard
drives are non-volatile.
d) Random vs. Sequential Access: Some devices allow random access of data {like hard drives),
while others are sequential (like tape drives).
e) Block vs. Character Devices: Block devices transfer data in blocks and are suitable for random
access. Character devices transfer data one character at a time and are suitable for sequential
access.
Device Drivers
Device drivers are software programs that communicate bNween thc> operating system and the
hardware devices. They provide a set of functions that the operating ~ystem can use to control the
device, such as reading, writing, initializing, t1nd manJging device ~pecific operations. Device drivers
serve as an abstraction layer bt'tween the hardware and the higher level software, making it easier
to write applications without worrying about the specifics of how each device works.

Device Handling
Device handling refers to how the operating system manages devices, allocates resources to them,
and schedules their use. The operating system uses a device management subsystem to keep track
of all the devices connected to the system, their types, status, and the drivers that control them. It
handles requests from applications to access devices, translates them into device-specific
commands, and manages any contention for resources.

Disk Scheduling Algorithms

Disk scheduling algorithms are used by the operating system to decide the order in which_disk 1/0
requests should be served to optimize performance. Some common disk scheduling algorithms
include: .
, First-Come First-Served (FCFS): Requests are processed in the order they arnve.
:; Shortest s:ek Time First (SSTF): The request with the shortest seek time (the smallest move for
the disk head) is processed next. _. h
c) SCAN (or Elevator): The disk arm moves in one direction and services requests until it reac es

the end,St~e~I it rtevSeCrAseNs ~::~~:n~isk arm moves in only one direction and jumps to the other
d) c-SCAN: 1m1 ar o ,

end when it reaches th~ ~nd of the disk. d C-SCAN that stop moving in a direction if there are no
e) LOOK and C-LOOK: Va nations of SCAN an
more requests in that direction.

Swap Space Management ·1 h Id data that doesn't fit into RAM. The
. k th tis used to temporan y o
Swap space is a space on dis a RAM and the swap space as needed. Swap sp~ce .
operating system swaps data between t to disk and which data to bnng back into
. . h. h data to swap ou ' . s
management involves deciding w ic ent and page replacement algorithms. ome
d virtual memory managem . .
RAM This is closely relate to . ace management include.
. 'th s used in swap sp . . I d
common page replacement algon m h 't been used for the longest time is rep ace .
U) Th page that asn
a) Least Recently Used (LR_ : o~dest page is replaced.
b) First-In, First-Out (FIFO). The
c) Optimal Page Replacement: The page that will not be used for the longest time in the future is
replaced . This is an idealized algorithm and is not implementable in practice.
di Clock: A variation of LRU that approximates the LRU algorithm using a circular list and a hand
that moves through it.