March 2006
Preventing Deadlocks
Overview
This document covers an obvious and elegant multithreaded paradigm that avoids deadlocks.
Deadlocks Require a Fertile Environment to Exist
- Mutual exclusion condition. Each resource is either currently assigned to exactly one process or is available.
- Hold and wait condition. Processes currently holding resources granted earlier can request new resources.
- No preemption condition. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
- Circular wait condition. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.
According to Tanenbaum* (referring to an article by Coffman), deadlocks are only possible when ALL four of the following conditions are met:
Upon review of these conditions, we realize that deadlocks can be quite rare beasts not worthy of study, IF it was not for the fact the computer scientists have managed to direct the "advancement" of computing systems to provide a fertile environment for deadlocks to appear. Lets undo this mistake and relegate deadlocks into history.
Poor Solutions
- Remove circular wait condition: Results in a laborious situation trying to identify possible circular dependencies and checking that they do not occur.
- Remove the no preemption condition: This just results in race conditions; threads preempting each other, or there is one indiscriminate master thread that creates starvation situations.
- Remove the hold and wait condition: Creates a bottleneck in performance as all threads have to register at a central mutex in order to acquire all needed resources at once.
Here are some poor solutions to the deadlock problem that have been tried.
Resources Do Not Need to Exist
Without loss of generality, a resource as a thing that "is either currently assigned to exactly one process or is available". The core reason that deadlocks occur is because the computer science experts over-abstracted, and created something that does not exist and called it a "resource". A mutitude of web pages do not discuss the mutual exclusion condition, but instead post a single line to the effect: "...there will always be intrinsically non-sharable resources" and provide no proof, or credible examples to support the claim. By ridding ourselves of this dead-end meme called "resource" we can prevent deadlocks from occuring.
We propose using an "actor paradigm" which is built on the premise that every object is threaded (called an actor), and all objects communicate via messages. In order to provide the services of a resource, it must be encapsulated in an actor that meets the conditions of the actor paradigm.
This may appear to be impossible to do in theory, because of the mismatch between the concepts of "resource" and "actor", but in reality all resources have properties that easily allow an interpretation as an actor. The idea here is took look at the "service" the recource is providing, and provide that service in an actor form.
Examples
Files
Files as actors act very much like CICS datasets (files); where the file does not change until the writer releases the handle to it. In detail: Opening a file indicates a message is started, writing to a file is appending to the message, and closing the file sends the message to the file for update. File readers will always have access to a complete and available file because they read the complete file on opening, and subsequent reads are done on that copy. This is all done efficiently by using file name indirection.
Sound Card
Sound cards are easy to model as actors. Each object that would like to use the sound card services sends a message concerning what sound to generate at what time. These are simply added to all other sounds that also have to be generated at that same time. Sound input can be set up so that objects register as users of sound input, and will receive a message from the sound card regarding the input signal when appropriate.
Tape Drive
A tape drive is used to store and save files. An actor should be made that provides those services to the layers that need them. The benefit to this scheme is that the "tape backup actor" can keep information about what is on the tape and optimize requests made of it.
Implementation Concerns
The semantics of the actor paradigm are meant to help the programmer communicate intent in a simpler and less bug prone way. The threading of every object and the use of messages is not the intended machine-level implementation. Implementation details should be left up to the compiler and the system to decide the optimal traditional implementation for the given specification.
* Modern Operating Systems (1992) by Andrew S. Tanenbaum, pg 242
First draft - April 2003
Changed "threaded object" to "actor" - July 2003