1. Deadlock (“deadly embrace”) is a system-wide tangle of resource requests that begins when 2 or more jobs are put on hold.

• Each job is waiting for a vital resource to become available. • Needed resources are held by other jobs also waiting to run but can’t because they’re waiting for other unavailable resources. • The jobs come to a standstill. • The deadlock is complete if remainder of system comes to a standstill as well.

• The resources can be categorized into physical and logical resources. The physical resources are printer, disk drive, cpu, memory, scanner etc. The logical resources are files.

• Deadlock is more serious than indefinite postponement or starvation because it affects more than one job.

• Because resources are being tied up, the entire system (not just a few programs) is affected.

• Requires outside intervention (e.g., operators or users terminate a job) to resolved the deadlock.

2. Seven Cases of Deadlocks

Case 1 Deadlocks on file requests

Case 2 Deadlocks in databases

Case 3 Deadlocks in dedicated device allocation

Case 4 Deadlocks in multiple device allocation

Case 5 Deadlocks in spooling

Case 7 Deadlocks in disk sharing

Case 8 Deadlocks in a network

Case 1: Deadlocks on File Requests

| |If jobs can request and hold files for duration of their |
| |execution, deadlock can occur. |
| | |
| |Any other programs that require F1 or F2 are put on hold as long |
| |as this situation continues. |
| | |
| |Deadlock remains until a program is withdrawn or forcibly removed|
| |and its file is released. |
| | |
| | |
| | |

Case 2: Deadlocks in Databases

|P1 accesses R1 and locks it. |Deadlock can occur if 2 processes access & lock records in |
| |database. |
|P2 accesses R2 and locks it. | |
| |3 different levels of locking : |
|P1 requests R2, which is locked by P2. |Entire database for duration of request |
| |A subsection of the database |
|P2 requests R1, which is locked by P1. |Individual record until process is completed. |
| | |
| |If don’t use locks, can lead to a race condition. |

Case 3: Deadlocks in Dedicated Device Allocation

|P1 requests tape drive 1 and gets it. |Deadlock can occur when there is a limited number of dedicated |
| |devices. |
|P2 requests tape drive 2 and gets it. | |
| |E.g., printers, plotters or tape drives. |
|P1 requests tape drives 2 but is blocked. | |
| | |
|A P2 requests tape drive 1 but is blocked. | |

Case 4: Deadlocks in Multiple Device Allocation

| |Deadlocks can happen when several processes request, and hold on |
| |to, dedicated devices while other processes act in a similar |
| |manner. |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |

Case 5: Deadlocks in Spooling

• Most systems have transformed dedicated devices such as a printer into a sharable device by installing a high-speed device, a disk, between it and the CPU. • Disk accepts output from several users and acts as a temporary storage area for all output until printer is ready to accept it (spooling). • If printer needs all of a job's output before it will begin printing, but spooling system fills available disk space with only partially completed output, then a deadlock can occur.

Case 6: Deadlocks in Disk Sharing
[pic]

• Disks are designed to be shared, so it’s not uncommon for 2 processes to access different areas of the same disk. • Without controls to regulate use of disk drive, competing processes could send conflicting commands and deadlock the system. • Process P1 wishes to show a payment so it issues a command to read the balance, which is stored in cylinder 20 of a disk. • While the control unit is moving the arm to cylinder 20, P1 is put on hold and the I/O channel is free to process the next I/O request. • P2 gains control of the I/O channel and issues a command to write someone else’s payment to a record stored in cylinder 310. If the command is not locked out, P2 will put on hold while the control unit moves the arm to cylinder 310. • Because P2 is on hold, the channel is free to be captured again by P1, which reconfirms its command to read from cylinder 20. • Since the last command from P2 forced the arm mechanism to cylinder 310, the disk control unit begins to reposition the arm to cylinder 20 to satisfy P1. The I/O channel would be released because P1 is once again put on hold, so it could be captured by P2, which issues a WRITE command only to discover that the arm mechanism needs to reposition.

Case 7: Deadlocks in a Network

| | |
|A network that’s congested (or have filled large percentage of | |
|its I/O buffer space) can become deadlocked if it doesn’t have | |
|protocols to control flow of messages through network. | |
| | |
|For example: | |
|A medium-sized word processing center has seven computers on a | |
|network, each on different nodes. C1 receives messages from nodes| |
|C2, C6, C7 and sends messages only to C1. | |
| | |
|C2 receives message from C1, C3 and C4 and sends messages only to| |
|C1 and C3. | |
| | |
|Messages received by C1 from C6 and C7 and destined for C2 are | |
|buffered in an output queue. | |
| | |
|Messages received by C2 from C3 and C4 and destined for C1 are | |
|buffered on an output queue. | |
| | |
|As the traffic increases, and both buffer space is filled. At | |
|this point, C1 can’t accept any more messages (from C2 or any | |
|other computer) because there’s no more buffer space available to| |
|store them. | |
| | |
| | |
|For the same reason, C2 can’t accept any messages from C1 or any | |
|other computer, not even a request to send. | |
|The communication path between C1 and C2 become deadlocked and | |
|since C1 and receive message only from C6 and C7 those routes | |
|also become deadlocked. | |

3. Four Conditions for Deadlock

• Deadlock preceded by simultaneous occurrence of four conditions that operating system could have recognized:

a) Mutual exclusion b) Resource holding c) No preemption d) Circular wait

a) Mutual exclusion The act of allowing only one process to have access to a dedicated resource.

[pic]

b) Resource holding The act of holding a resource and not releasing it; waiting for the other job to retreat. [pic]

c) No preemption The lack of temporary reallocation of resources; once a job gets a resource it can hold on to it for as long as it needs.

[pic]

d) Circular wait Each process involved in impasse is waiting for another to voluntarily release the resource so that at least one will be able to continue.

[pic]

4. Modeling Deadlocks Using Directed Graphs (Holt, 1972)

• Processes represented by circles. • Resources represented by squares. • Solid line from a resource to a process means that process is holding that resource. • Solid line from a process to a resource means that process is waiting for that resource. • Direction of arrow indicates flow. • If there’s a cycle in the graph then there’s a deadlock involving the processes and the resources in the cycle.

Directed Graph Examples

[pic]

• Resource types R1, R2, . . ., Rm • eg : CPU cycles, memory space, I/O devices

• Each resource type Ri has Wi instances. • R1 has 4 instances eg 4 printers in a system • R2 has 2 instances eg 2 disk drive in a system • R3 has 1 instance eg 1 CPU in a system

R1 R2 R1

5. Reducing Directed Resource Graphs

i. Find a process that is currently using a resource and not waiting for one. Remove this process from graph and return resource to “available list.” ii. Find a process that’s waiting only for resource classes that aren’t fully allocated. – Process isn’t contributing to deadlock since eventually gets resource it’s waiting for, finish its work, and return resource to “available list.” iii. Go back to Step 1 and continue the loop until all lines connecting resources to processes have been removed.

5.1.

[pic]

No deadlock, because P3 has no requests, after P3 has finish its execution will release the resource R3 to P2 for execution progress. When P2 has finish, P2 will release the resources R2 and R3, finally the process P1 can gain the R2 for its execution.

5.2.
[pic]

Deadlock, because the all processes (P1, P2 and P3) in the system are waiting a resource which held by each process in the system. Every process is waiting each other process’s resource in the system.

5.3.

[pic]

Deadlock, because the all processes (P1, P2, P3 and P4) in the system are waiting a resource which held by each process in the system. Every process is waiting each other process’s resource in the system.

5.4.
[pic]

No deadlock, because all the processes (P1, P2 and P3) have no requests, so all the processes can make its execution progress.

5.5.
[pic]

Deadlock, because the all processes (P1, P2, and P3) in the system are waiting a resource instance which held by each process in the system. Every process is waiting each other process’s resource instance in the system.

5.6.

[pic]

No Deadlock, P2 has no request, after P2 finish, the process will release an instance of R2 to P3 for progression after P3 finish, it will release the instance of R1 to P1 for execution, finally all the processes request in the system have been served.
7. Converting the system scenario below into directed resource graphs

Consider a system of 4 processes, P = {P1, P2, P3, P4} and 4 resources types, R = {R1, R2, R3, R4}. Assume all the resources are non-sharable and the numbers of instances for each resource type are 4, 2, 2 and 2 respectively. Given the process states as follows:

o P1 holds all instances of R1, an instance of R3 and an instance of R4 and requests an instance of R2 o P2 holds an instance of R2 and requests an instance of R4 o P3 holds an instance of R2 and requests an instance of R3 o P4 holds an instance of R3 and R4

6. Strategies for Handling Deadlocks

• Prevent one of the four conditions from occurring.

• Avoid the deadlock if it becomes probable.

• Detect the deadlock when it occurs and recover from it gracefully.

7. Prevention of Deadlock

• To prevent a deadlock OS must eliminate 1 out of 4 necessary conditions. o Same condition can’t be eliminated from every resource.

a. Mutual exclusion is necessary in any computer system because some resources (memory, CPU, dedicated devices) must be exclusively allocated to 1 user at a time. o Might be able to use spooling for some devices. o May trade 1 type of deadlock (Case 3) for another (Case 5).

b. Resource holding can be avoided by forcing each job to request, at creation time, every resource it will need to run to completion. o Significantly decreases degree of multiprogramming. o Peripheral devices would be idle because allocated to a job even though they wouldn't be used all the time.

c. No preemption could be bypassed by allowing OS to deallocate resources from jobs. o OK if state of job can be easily saved and restored. o Bad if preempt dedicated I/O device or files during modification.

d. Prevention of Circular Wait o Circular wait can be bypassed if OS prevents formation of a circle. o Havender’s solution (1968) is based on a numbering system for resources such as:

Printer = 1, Disk = 2, Tape= 3.

– Forces each job to request its resources in ascending order. – Any “number one” devices required by job requested first; any “number two” devices requested next …

o Require that jobs anticipate order in which they will request resources.

Disk (2) Printer (1)

8. Deadlock Avoidance

• Even if OS can’t remove 1 condition for deadlock, it can avoid one if system knows ahead of time sequence of requests associated with each of the active processes.

• Dijkstra’s Bankers Algorithm (1965) used to regulate resources allocation to avoid deadlock.

• Safe state o If there exists a safe sequence of all processes where they can all get the resources needed. • Unsafe state o Doesn’t necessarily lead to deadlock, but it does indicate that system is an excellent candidate for one.

8.1 Banker’s Algorithm

• Based on a bank with a fixed amount of capital that operates on the following principles: – No customer will be granted a loan exceeding bank’s total capital. – All customers will be given a maximum credit limit when opening an account. – No customer will be allowed to borrow over the limit. – The sum of all loans won’t exceed the bank’s total capital.

• OS (bank) must be sure never to satisfy a request that moves it from a safe state to an unsafe one. • Job with smallest number of remaining resources < = number of available resources
8.2 A Bank’s Safe and Unsafe States

Safe

Unsafe

Example 1

Magnetic tape drives

To illustrate, we consider a system with 12 magnetic tape drives and 3 processes: P0, P1 and P2. P0 requires 10 tape drives, P1 may needs as many as 4 tape drives and P2 may need up to 9 tape drives.

Suppose that, at time t0, process P0 is holding 5 tape drives, P1 is holding 2 tape drives and P2 is holding 2 tape drives. (Thus, there are 3 free tape drives)

Processes Allocation (Alloc) Maximum needs (Max) Current Needs(Max – Alloc) P0 5 10 5 P1 2 4 2 P2 2 9 7

Banker’s Algorithm

| |Allocation (Alloc) |Maximum |Current Need |Availability |
|Processes |(Tape drive) |(Max) |(Max-Alloc) |(Avai) |
| | |(Tape drive) |(Tape drive) |(Tape drive) |
|P0 |5 |10 |5 |3 |
|P1 |2 |4 |2 |10 |
|P2 |2 |9 |7 |12 |

At time t0 ( the system is in a safe state

Because if with the sequence satisfies the safety condition. P1 can immediately be allocated all its tape drives and then return them (the system will then have 5 available tape drives); then P0 can get all its tape drives and return them (the system will then have 10 available tape drives); and finally P2 can get all its tape drives and return them (the system will then have all 12 tape drives available)

Magnetic tape drives

Banker’s Algorithm

| |Allocation (Alloc) |Maximum |Current Need |Availability |
|Processes |(Tape drive) |(Max) |(Max-Alloc) |(Avai) |
| | |(Tape drive) |(Tape drive) |(Tape drive) |
|P0 |5 |10 |5 |2 |
|P1 |2 |4 |2 |4 |
|P2 |3 |9 |6 | |

At time t1 (P2 requests and is allocated one more tape drive) ( the system in an unsafe state.

Because at this point, only P1 can be allocates all its tape drives. When it returns them, the system will have only 4 available tape drives. Since P0 is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives. Since they are unavailable, P0 must wait, and this resulting in a deadlock.
Example 2

Consider a system with 5 processes P0 through P4 and 3 resources types A, B and C. Resources type A has 10 instances, resource B has 5 and resource C has 7. Suppose that, at time T0, the following snapshot of the system has been taken:

|Pn |Allocation |Max |Availability |
| |(A B C) |(A B C) |(A B C) |
|P0 |0 1 0 |7 5 3 |3 3 2 |
|P1 |2 0 0 |3 2 2 | |
|P2 |3 0 2 |9 0 2 | |
|P3 |2 1 1 |2 2 2 | |
|P4 |0 0 2 |4 3 3 | |

Answer the following questions using the banker’s algorithm:

a. What is the content of the matrix Need?

b. Is the system in a safe state, if yes states the process sequence? Justify your answer.
a.

|Pn |Allocation |Max |Current Need |Availability |
| |(A B C) |(A B C) |(A B C) |(A B C) |
|P0 |0 1 0 |7 5 3 | |3 3 2 |
|P1 |2 0 0 |3 2 2 | | |
|P2 |3 0 2 |9 0 2 | | |
|P3 |2 1 1 |2 2 2 | | |
|P4 |0 0 2 |4 3 3 | | |

9. Starvation

• Starvation -- Result of conservative allocation of resources where a single job is prevented from execution because it’s kept waiting for resources that never become available.

• Starvation occurs when one or more threads in your program are blocked from gaining access to a resource and, as a result, cannot make progress. Deadlock, the ultimate form of starvation, occurs when two or more processes/threads are waiting on a condition that cannot be satisfied. Deadlock most often occurs when two (or more) processes/threads are each waiting for the other(s) to do something.

• “The dining philosophers” Dijkstra (1968).

Figure 9.1
| |
|Five philosophers meet to think and to eat spaghetti. There are forks on the table - one between |
|each philosopher. Local custom dictates that each philosopher must use two forks to eat the |
|spaghetti, but there are only five forks available instead of ten. |
| |
|Unless the resources are allocated fairly, some philosophers will starve. |
| |
|[pic] |

• 5 philosophers are sitting at around table, each deep in thought and in the center lays a bowl of spaghetti that is accessible to everyone. Refer Figure 9.1. • Assume that each philosopher must use two forks to eat the spaghetti. There are only five forks. • When they sit down to dinner, Philosopher 1 (P1) is the first to take the two forks (F1 and F5) on either side of the plate and begins to eat. Inspired by his colleague, Philosopher 3 (P3) does likewise , using F2 and F3 • Now philosopher 2 (P2) decided to begin the meal but is unable to start because no forks are available. • F1 has been allocated to P1and F2 has been allocated to P3. The remaining fork can be used by P4 or P5, So Philosopher 2 must wait. • P4 and P5 are quietly thinking and P1 still eating when P3 (who should be full) decides to eat some more and because the resources are free, he is able to take F2 and F3 one again. Soon thereafter, P1 finishes and release F1 and F5 but P2 is still not able to eat because F2 is now allocated. • This scenario could continue forever and as long as P1 and P3 alternate their use of the available resources, P2 must wait. P1 and P3 can eat any time they wish while P2 starves.

• Avoid starvation via algorithm designed to detect starving jobs which tracks how long each job has been waiting for resources (aging).

-----------------------
[pic]

[pic]

Disk control unit

I/O Channel

P1 Read records at cylinder 20

P2 Write to file at cylinder 310

[pic]

P2

P1

P0

P2

P1

P0

[pic]

[pic]

P1

P21