Operating Systems Course Outline

7. Deadlocks

Resources

devices like floppy drive, printer, CD , HD. When avoiding deadlock, what concerns us is non-sharable resources. Four Necessary Conditions for Deadlock to occur

1. Mutual Exclusion

At least one resource must be held in a non-sharable state forcing other requesting processes to wait for its release.

2. Hold and wait

At least one process must be holding a resource and waiting for another resource to be released.

3. No Preemption

Only way to free a resource is by the process releasing it. No preemption.

4. Circular wait

A waiting for B who is waiting for C who is waiting for A again.

Resource allocation Graph

Deadlock Prevention

Do not allow one of the 4 conditions to occur.

Deadlock Avoidance

On the fly, the OS keeps making sure that a deadlock does not occur. For example, the OS gets a list of resources that each process will ever require and the OS decides how to allocate them as they are requested.

Deadlock Detection

Allow deadlocks to occur but check for them and recover.

Ignore Deadlock Problem

Since deadlocks are rare, we can rely on rebooting to deal with them. Most common solution.

Methods of Deadlock Prevention

Deny Mutual Exclusion: not a viable since some resources (printers) are inherently exclusive.
Deny Hold and Wait: 1. Require all resources that a process needs to be allocated at the start. If not all its resources can be allocated, then don't start the process. 2. Allow a process to request resources only if it holds none. There are two problems with these methods: low resource utilization (process may hold resources in idle) and starvation (a process may wait forever for all its resources to be available at the same time).
Allow Preemption: Two solutions: Either free all resources of a process waiting for some resource or when a process requests a resource which a second process is using, check if that process is waiting for some resource, if it is then preempt the desired resource for the first process from the second. Must continually check if the second process ever goes to wait mode.
Prevent Circular Wait: Create a hierarchial ordering of all resources, then allow processes to request only resources of a higher order than the other resources they already are assigned. For example CD might be 1 HD might be 5 and printer might be 13. If a process is assigned a HD , he can no longer be assigned a CD (until he releases the HD).

Deadlock Avoidance

Safe State

OS gets information from processes about their potential resource needs. The OS guarantees that needs can be met and thereby maintain the system in a safe state. A safe state is one in which there exists an order in which all the processes can complete one by one and each will receive its maximal needs. To start with, all the potential requests of at least one process must be able to be met currently. This means that this process will complete and free up his resources. These resources can then be used by other processes allowing them to complete. At every point there must exists at least one process which can get all its needed resources or else the state is not safe.
For example, on a system with 12 printers:

Process	Max Needs	Current Allocation
P0	10	5
P1	4	2
P2	9	2

This table represents a safe state since we can still service P1 all its future needs. And upon his completion we can service P0. And then P2. We cannot have a deadlock in the current state. At worst we will have to wait for P1 to finish and free its printers and then P0 will be able to have its Max Needs met. But, if P0 would request 2 more printers we would have to deny this request since that would leave only one free printer and a potential deadlock. Obviously this scheme will cause resource under-utilization since we are reserving a pool of unused resources.

Resource Allocation Graph Algorithm

Know ahead of time all potential resource claims (requests). Only grant a request if it will not create a potential cycle. We use a dotted line to indicate a claim edge (i.e. a potential future request). We need to examine all process claim edges before granting a request. Only works if there is just one resource of each type.

Banker's Algorithm

Check that a stafe state exists for multiple resources by checking if there is any process order by which all the processes can get all their resources and finish. If no such order exists, then the state is not safe. Make a "Need" table which is simply the Max_Needs - Current_Allocation. Then compare that to the table of Available resources. Look for a process that can finish, if one exists, then add its resources to Available resources, and continue. If all processes can finish, you have a safe state.

Process	Allocation A	Allocation B	Allocation C	Max Needs A	Max Needs B	Max Needs C
P0	1	1	1	3	2	2
P1	2	2	1	3	4	1
P2	2	1	0	3	1	0

Total Amount of A = 6, B = 5, C =2. Is this system in a safe state? Yes. Can we satisfy the request from P0 for one more of resource A? No. What about the same request from P2? Yes, because the path to completion starts with P2.

Wait for Graph

Like a resource allocation graph, but where the resources have been removed. It shows which process are waiting for which other processes. If a circle exists, you have detected a deadlock.

Deadlock detection

use Bankers algorithm to detect deadlock where multiple resources are in use.

Deadlock recover

1. abort all deadlocked process. 2. Abort one deadlocked process and check for deadlock state, if still deadlocked, abort another process.

Resource preemption

Select a process to have its resource(s) freed. May need to roll back to state before that process requested the resource (requires state overhead). If resource is a file, it may get currupted. a certain process may get starved if selection of victim is based on some criteria

another tutorial