Deadlock

Principle of Deadlock

- Deadlock is defined OS the condition for a set of processes exhibits id each process in a set is waiting for an event that only if each process in the set can cause but as all the processes are waiting name of them will ever cause any of the events to wake up other processes resulting all the processes to wait forever.
- For eg: Consider a system running two processes A and B. suppose A requested for CD-ROM and gets it while B requested a printer and gets it. Now, A quested for printer and blocks waiting for it. Finally, B requested for CD-ROM and also blocks. Here, both processes are blocked and will remain so forever. This condition is called deadlock.

- Resource is defined as hardware or a piece of information that is granted to a process such that it can be used by only a single process at any instant.
- Preemptable resource is the resource that can be taken away from its current owner and given back later without any effects. Eg: memory.
- Non-preemption resource is the resource that can not be taken away from its current owner without causing failure in computation. eg: printer.
- To use a resource, a process must request for it. If the resource is granted, the process can operate on the resource and after completion of task, it must release that resource. If the resource is unavailable immediately, the process must wait until it acquires the resources.
- The conditions that must hold for having a deadlock are as follows: -
a) Mutual exclusion: Each resource is either currently hold by exactly one process or is available.
b) Hold and wait: A process holding at least one resource is waiting to acquire other resources held by other processes.
c) No preemption: A resource can not be taken over from its current owner by any other processes.
d) Circular wait: Thera must be a circular chain of two or more processes, each of which is waiting for a resource held by next member of the chain.
- Deadlock can be modeled using directed graphs as shown in fig:
- If the graph have cycle and the cycle involves resources with only a single instance, then a deadlock has occurred.

---

Ostrich Algorithm

- Simplest approach to deal with deadlock.
- Pretend there is no problem at all.
- If there deadlock occurrence have less probability, it is ignored for convenience and to lower the cost.
- For eg. Consider a UNIX system with 100 process slots with 10 process running, each of which needs to create 12 sub processes. After each process has created 9 processes, the slot becomes full. Noe, the 10 original processes sits in an endless loop forking and dialing resulting a headlock. The probability of occurrence of such condition is every rare so, it is just neglected.

---

Deadlock Prevention

- It is a strategy to impose suitable restrictions am processes so that deadlock are impossible.
- Deadlock can be prevented by ensuring that at least one of the four conditions for deadlock is denied.

---

Deny mutual exclusion

- If no resource were assigned exclusively to asingle process, no deadlock may occur.
- To any mutual exclusion, spooling can be done.
- Eg: by spooling printer, only process that request printer is printer daemon which never requests other resources, we eliminated deadlock.
- All devices can not be spooled.
- Deadlock may occur due to competition for disk space for spooling.

---

Deny hold and wait

- If we prevent processes that hold resources from waiting for other resources, we can eliminate deadlock.
- All processes must request all resources before exclusion. If everything were available, the process would be allowed with all required resources and run to completion. Otherwise, nothing would be allocated and the process must wait.
- No optimal use of resources
- Process do not know what resource they will need before execution.

---

Deny no preemption

- If a process holding some resources requests another resource that can not be allocated, all resources currently holding are released.
- The process may lose all its work to that point.
- Starvation may occur.

---

Deny circular wait

- Provide global numbering to all resources
- Process can request resources at any time but all requests must be made in numerical order.
- Difficult to implement.

---

Deadlock Avoidance

Deadlock can be avoided by careful analysis of each resources request to determine if it could be safely granted.

---

Banker’s Algorithm for single resource

- It is a resource allocated and deadlock avoidance algorithm that tests for safety by simulating the allocated of pre-determined max. passible amounts of all resources and them makes a “safe-state” check to test for possible deadlock conditions for all pending process, before deciding whether allocation should be allowed.

- For eg:
Process Has Max Has Max
A 0 6 A 1 6
B 0 5 B 1 5
C 0 7 C 2 4
D 0 7 D 4 7
Free – 10 Free – 2
(safe state) (safe state)

Has Max
A 1 6
B 2 5
C 2 4
D 4 7
Free -1
(unsafe state)

---

Banker’s Algorithm for multiple resources

- Let, E = Existing resource, P = Possessed resource, AV = available resource

- The algorithm to check if a state is safe is:
a) Look for a new, R, whose unmet resource needs are all smaller than or equal to A. If no such now exists, the system will lead to deadlock as no process can run to completion.
b) Assume the process of the row chosen requests all the resources it needs as finishes. Mark that process as terminated and add its resources to A vector.
c) Repeat and until all processes are marked terminated. (safe state) or until a deadlock occurs (Unsafe state)

---

Example :

E = (6 3 4 2)
P = (5 3 2 2)
AV = (1 0 2 0)

No of Processes = 5 (A, B, C, D, E)
No of Resorces = 4 (R1, R2, R3, R4)

Allocation matrix:
3 0 1 1
0 1 0 0
1 1 1 0
1 1 0 1
0 0 0 0

Still Need Matrix:
1 1 0 0
0 1 1 2
3 1 0 0
0 0 1 0
2 1 1 0

For above example:
Loop 1 -> D < AV.
-> D terminates
-> Av = (2 1 2 1)

Loop 2 -> A < Av
-> A terminates
-> Av = (5 1 3 1)

Loop 3 -> B -> B terminates
-> Av = (5 2 3 2)

Loop 4 -> C < Av
-> C terminates
-> Av = (6 3 4 2)

Loop 5 -> E < Av
-> E terminates
-> Av = (6 3 4 2)

Hence, the given state is safe state.

---

Deadlock Detection

Deadlock detection is the process of monitoring the requests for possible deadlock condition.

---

Single instance of each resource type

- A wait – for graphs is used. It is the resource allocation graph without the nodes of type resource and collapsing of appropriate edges.
- If wait – for graph has any cycle, then there is a deadlock.
- The system maintains wait – for graph and periodically searches for a cycle in the graphs.

---

Multiple instance of a resource type

- Available: vector of length ‘m’
- Allocation: n * m matrix
- Request: n * m matrix

---

Deadlock detection algorithm

1. Initialize available
2. For I = 1, 2,….n; if allocation i ‡ 0, finish [i] = FALSE; else finish [i] = TRUE
3. Find an index i such that;
Finish [i] = = false and request; <= available
4. If no such i exists, go to step 5
Else, available = available + allocation
Finish [i] = true
Go to step 3
4. If finish [i] = = false, for some i, 1 < i < n, the system is in deadlock state.

---

Q) Suppose at t₀ time, we have following state for processes P0, P1, P2, P3, P4 and resources A, B, C.

Av = (0 0 0)

Allocation Matrix:
0 1 0
2 0 0
3 0 3
2 1 1
0 0 2

Request Matrix:
0 0 0
2 0 2
0 0 0
1 0 0
0 0 2

Is the system in deadlock state?

Answer:::

Following deadlock detection algorithm.

1. Available = 0 0 0

2. Finish [0] = FALSE
Finish [1] = FALSE
Finish [2] = FALSE
Finish [3] = FALSE
Finish [4] = FALSE

3. PO has finish [0] = false and request 0 =< available
Available = 0 1 0
Finish [0] = TRUE

4. P2 has finish [2] = false and request 2 =< available
Available = 3 1 3
Finish [2] = TRUE

5. P1
Available = 5 1 3
Finish [1] = TRUE

6.. P3
Available = 7 2 4
Finish [3] = TRUE

7. P4
Available = 7 2 6
Finish [4] = TRUE

Since, all the processes can run to completion, the system is not in a deadline state.

---

Deadlock Recovery

Deadline recovery is the mechanism of recovering of the system after the deadlock detection detects the system deadlock.

---

Methods:

i. Through preemption
- Temporarily take a resource away from its current owner and give it to another process.

ii. Through rollback
- Periodically making a checkpoint of a process
- If deadlocked, the process is rolled back to some earlier check points.

iii. Through Killing
- Forcibly kill one of the processes in the deadline cycle.
- The process to kill should be chosen so that it would not affect the entire system.

---

Two Phase Locking

- The process tires to lock all the records it needs, one at a time.
- If superseded, performs modification and finally releases locks.
- No process is ever in a state where it is holding some shared resources.

---

Communication Deadlock, Livelock and Starvation

Communication Deadlock

If each process in the set is waiting to communicate with another process in same set and no process ever initiates any communication until it receives communication for which it is waiting.

---

Live lock

Same as deadlock but the states of the processes constantly changes with regard to one another without progress.

---

Starvation

Starvation is the situation where a process is unable to gain regard access to shared resources and is unable to make progress.

 

-by SURAJ AWAL