Deadlocks

A Deadlock is a situation where process $A$ waiting for a resource but process $B$ is holding onto it. The process $B$ needs another process that is acquired by another one. This goes in a cycle and no one can really do any work.

4 Conditions for Deadlocks to happen (Coffman Conditions)

for a deadlock to happen, all four of these must happen simultaneously.

Mutual Exclusion: At least one resource must be held in a non-shareable mode (only one process can use it at a time, e.g., a printer).
Hold and Wait: A process is currently holding at least one resource and actively waiting to acquire additional resources that are held by other processes.
No Preemption: Resources cannot be forcibly taken away from a process; they can only be released voluntarily after the process has finished its task.
Circular Wait: A closed loop of processes exists such that $P_0$ waits for a resource held by $P_1$ , $P_1$ waits for $P_2$ , and $P_n$ waits for $P_0$ .

Resource allocation graph

In these, arrow pointing direction tells if a process is "given" resource or "asking" for resource.

\text{Process} \underbrace{\longrightarrow}_{\text{asking}} \text{Resource}

\text{Process} \underbrace{\longleftarrow}_{\text{given}} \text{Resource}

A deadlock occur when there is a cycle formed in a resource allocation graph but just because there is a cycle that does not mean there is a deadlock. If there is a cycle, there is a high chance of a deadlock.

Deadlock	No Deadlock
![[deadlock.png]]	![[no-deadlock.png]]
$T_3$ cannot be completed since $R_2$ is holding by a circular waiting processes	$T_3$ can be finished since a instance of $R_2$ can be released when $T_4$ is finished.

No Cycles in The Graph $\implies$ No Deadlocks

Strategies for Preventing deadlocks

Strategy	Approach	How it Works
Ignorance	Ignore the problem	Assumes deadlocks occur rarely. If one happens, the user/admin manually kills processes or reboots. Used by Linux, Windows, and macOS for general desktop use due to low overhead.
Prevention	Eliminate one of 4 conditions	Restricts how resources are requested so that at least one Coffman condition is impossible (e.g., forcing processes to request all resources at once to break Hold & Wait).
Avoidance	Dynamic checking	The OS checks if allocating a resource leads to a "Unsafe State". Uses algorithms like Banker's Algorithm to grant resources only if a safe sequence exists.
Detection & Recovery	Allow deadlocks, then fix them	The OS periodically runs a graph algorithm to detect cycles. Upon detection, it recovers by preempting resources or killing processes involved in the loop.

Algorithms to Prevent Deadlocks

Ostrich Algorithm

This uses a Ignorance Approach. Basically pretend as the deadlock might not occur. lol this is the whole algorithm. Named after the ostrich effect which is defined as "to stick one's head in the sand and pretend there is no problem".

This is used when,

Probability of the deadlock is extremely low
Preventing the deadlock costs a lot
Detecting the deadlock requires complex solutions and its difficult.

Banker's Algorithm

This algo uses a avoidance approach. This uses a credit card kind of analogy. Each process will get an amount of credit they can use for "buying" resources.

Detection and Recovery Algorithms

After a deadlock happens, we can use some algorithms to detect it first. Then another algorithm can be implemented to recover from the deadlock state.

Detection Can be detected by traversing the resource allocation graphs and find if there is a cycle.

Recover

can be recovered from deadlock by forcefully pre-empting the resource from the process.
another way is completely aborting all processes that has been affected.

When the number of processes and resources increase in huge numbers, this is very inefficient. So this should be only done considering how often the frequency a deadlock happens or how much other processes will get affected from it.