operating system feb 28

292 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

use of both resources for a certain period of time. Two processes, P and Q, have the following general form:

Process P Process Q

• • • • • • Get A Get B • • • • • • Get B Get A • • • • • • Release A Release B • • • • • • Release B Release A • • • • • •

In Figure 6.2, the x-axis represents progress in the execution of P and the y-axis represents progress in the execution of Q. The joint progress of the two processes is therefore represented by a path that progresses from the origin in a northeasterly direction. For a uniprocessor system, only one process at a time may execute, and the path consists of alternating horizontal and vertical segments, with a horizontal

Figure 6.2 Example of Deadlock

Progress of Q

Progress of PGet A

Get A

Get B

Get B

B Required

A Required

A Required

Release A

Release A

Release B

Release B

Deadlock inevitable

P and Q want A

P and Q want B

1 2

3

4

5

6

5 Possible progress path of P and Q. Horizontal portion of path indicates P is executing and Q is waiting. Vertical portion of path indicates Q is executing and P is waiting.

5 Both P and Q want resource A

5 Both P and Q want resource B

5 Deadlock-inevitable region

B Required

6.1 / prinCipleS oF DeaDloCk 293

segment representing a period when P executes, and Q waits, and a vertical segment representing a period when Q executes and P waits. The figure indicates areas in which both P and Q require resource A (upward slanted lines); both P and Q require resource B (downward slanted lines); and both P and Q require both resources. Because we assume that each process requires exclusive control of any resource, these are all forbidden regions; that is, it is impossible for any path representing the joint execution progress of P and Q to enter these regions.

The figure shows six different execution paths. These can be summarized as follows:

1. Q acquires B then A, then releases B and A. When P resumes execution, it will be able to acquire both resources.

2. Q acquires B then A. P executes and blocks on a request for A. Q releases B and A. When P resumes execution, it will be able to acquire both resources.

3. Q acquires B then P acquires A. Deadlock is inevitable, because as execution proceeds, Q will block on A and P will block on B.

4. P acquires A then Q acquires B. Deadlock is inevitable, because as execution proceeds, Q will block on A and P will block on B.

5. P acquires A then B. Q executes and blocks on a request for B. P releases A and B. When Q resumes execution, it will be able to acquire both resources.

6. P acquires A then B, then releases A and B. When Q resumes execution, it will be able to acquire both resources.

The gray-shaded area of Figure 6.2, which can be referred to as a fatal region, applies to the commentary on paths 3 and 4. If an execution path enters this fatal region, then deadlock is inevitable. Note the existence of a fatal region depends on the logic of the two processes. However, deadlock is only inevitable if the joint prog- ress of the two processes creates a path that enters the fatal region.

Whether or not deadlock occurs depends on both the dynamics of the execu- tion and on the details of the application. For example, suppose P does not need both resources at the same time so the two processes have the following form:

Process P Process Q

• • • • • • Get A Get B • • • • • • Release A Get A • • • • • • Get B Release B • • • • • • Release B Release A • • • • • •

This situation is reflected in Figure 6.3. Some thought should convince you that regardless of the relative timing of the two processes, deadlock cannot occur.

As shown, the joint progress diagram can be used to record the execution history of two processes that share resources. In cases where more than two

294 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

processes may compete for the same resource, a higher-dimensional diagram would be required. The principles concerning fatal regions and deadlock would remain the same.

Reusable Resources

Two general categories of resources can be distinguished: reusable and consumable. A reusable resource is one that can be safely used by only one process at a time and is not depleted by that use. Processes obtain resource units that they later release for reuse by other processes. Examples of reusable resources include processors, I/O channels, main and secondary memory, devices, and data structures (such as files, databases, and semaphores).

As an example of deadlock involving reusable resources, consider two pro- cesses that compete for exclusive access to a disk file D and a tape drive T. The programs engage in the operations depicted in Figure 6.4. Deadlock occurs if each process holds one resource and requests the other. For example, deadlock occurs if the multiprogramming system interleaves the execution of the two processes as follows:

p0 p1 q0 q1 p2 q2

Figure 6.3 Example of No Deadlock [BACO03]

Progress of PGet A Get B

A Required B Required

5 Both P and Q want resource A

5 Both P and Q want resource B

Release A Release B

1 2 3

4

5

6

P and Q want A

P and Q want B

5 Possible progress path of P and Q. Horizontal portion of path indicates P is executing and Q is waiting. Vertical portion of path indicates Q is executing and P is waiting.

Progress of Q

Get A

Get B

A Required

Release A

Release B

B Required