CAOS 03

As mentioned before, a deadlock occurs when all processes in a set are waiting for events that only another process can trigger. Another way of phrasing this is that a Waiting process cannot exit from Waiting because it is waiting for another resource held by another Waiting process.
A resource in a system can be anything from Memory, to CPU cycles, files and I/O devices. A resource can have multiple instances. For example, a multiple processor system has multiple instances of the CPU resource. Typically a process only needs to request for a resource TYPE, and it will be allocated any of those INSTANCES.

The usage of a process can be summarized as follows:
Request - The process request for the resource. If it is granted, the resource is locked. If it is not granted immediately, the process is put into Waiting state.

Use - The process operates and uses the resource.

Release - The process releases the resource.

The Request and Release can represent the requesting and releasing of devices, opening and closing of files and allocation and freeding of memory. These requests and releases can be accomplished using wait and signal of Semaphores.

A Deadlock requires four conditions to hold true simultaneously to occur:
Mutual Exclusion - At least one resource is held in a non-sharable mode. Another requesting process must wait for this resource to be released.

Hold and Wait - A process holding a resource is waiting for another resource held by another process.

No Preemption - Held resources cannot be preempted.

Circular Wait - In an example set of three processes, P0 waits for P1, while P1 wait for P2, and P2 wait for P0. This also implies the Hold and Wait condition.

A resource-allocation graph is defined by a set of vertices (dots) and a set of edges (lines).

An example of a resource-allocation graph is as follows (taken from Seminar Slide 5-36):


In this case, the Boxes represent Resource TYPEs, and the Dots (Vertices) in the Boxes represent INSTANCES of that resource. The Circles (Vertices) represent Processes. The edge P -> R is a request edge, and the edge R -> P is an assignment edge. A request edge is transformed into an assignment edge once the previous process has released it.

Notice that a request is always for a TYPE, so it points to the square. INSTANCES are always assigned, so it comes from a Dot instead of a Square.

In the diagram:

P1 has 1xR2, and needs 1xR1 held by P2. P1 is waiting for P2.
P2 has 1xR1, 1xR2, and needs 1xR3 held by P3. P2 is waiting for P3.
P3 has 1xR3. It does not need anything else.

From the definition of a deadlock, no processes are deadlocked because there is #1 Mutual Exclusion, #2 Hold and Wait, #3 No Preemption but there is no #4 Circular Wait. Therefore, it is only a matter of time before P3 releases R3 for P2, which allows P2 to complete its operations and release R2 for P1.

Note that a cycle may not mean that a Deadlock has occurred. If there are multiple instances of a resource and a cycle exists, there may not be a deadlock. Consider the following diagram:



We observe the following cycle:
P1 -> R1 -> P3 -> R2 -> P1

However, the cycle may be resolved through:
P1 -> R1 -> P2
P3 -> R2 -> P4

Deadlock only occurs when ALL processes in a set are under Circular Wait. In this case, even though P1 and P3 are under circular wait, P2 and P4 may release the resources. There is therefore no Deadlock.