Previous: Controlled Nondeterminism Up: Atomicity Next: Inheritance

Deadlock

The execution of an atomic function represents a significant control over the rest of the computation. No other threads of control will be permitted to begin execution of an atomic function on the same object as the executing atomic function, until that executing atomic function terminates. Thus, it is possible to write an atomic function that prevents the rest of the computation from proceeding by preventing any other atomic functions from executing. This is an example of deadlock.

Fortunately, there is a small collection of simple rules for avoiding deadlock. The following rules guarantee that an atomic function will not cause a computation to deadlock:

1. atomic functions must terminate.
2. atomic functions must not suspend (suspension is discussed in Chapter ).
3. atomic functions must not contain parallel blocks or parfor statements.
4. atomic functions must not call other functions.

Notice that the above collection of rules is a stronger set of requirements than strictly required. It is possible to write a program that violates one or more of these rules and yet will not deadlock. Following these rules, however, guarantees that no atomic function will cause a deadlock.

Let us examine each of these requirements in turn.

The first two rules prevent a single atomic function from monopolizing the computation by preventing any other atomic function from executing. It is possible, however, to write a program with a nonterminating atomic function which is deadlock-free. For example, if no other threads of control require atomic access to the same object as the nonterminating atomic function, no deadlock will occur. Of course, in this case, declaring the function atomic has no effect.

The third rule prevents deadlock at a nested level of scope within an atomic function. Certainly if an atomic function does not contain a parallel block or a parfor, no deadlock between concurrent threads of control within the atomic function is possible. Again, however, it is possible to write programs that violate this rule and yet will not result in deadlock. For example, an atomic function that contains a parallel block that can be guaranteed not to deadlock is perfectly safe.

The last rule prevents an atomic function from not terminating due to a deadlock in a function called by the atomic function. Clearly if no functions are called from within an atomic function, such deadlock cannot occur. Again this requirement is too strong, and it is possible to write atomic functions that do call member functions and yet will never deadlock.

Though it is possible to write deadlock-free programs that violate the rules given above, this programming style is strongly discouraged. Such programs can easily contain subtle errors that, because of various timing or dependency issues, may go undetected for a long time.

As a general rule, atomic functions should be used sparingly, and then only to do the most fundamental operations.