Information Technology Reference
In-Depth Information
is structured to prevent at least one of the conditions, then the system can
not deadlock. Considering these conditions in the context of a given system
often points to a viable deadlock prevention strategy. Below, we discuss some
commonly-used approaches.
Bounded resources: Provide sucient resources. One way to ensure
deadlock freedom is to have sucient resources to satisfy all threads' demands.
For example, suppose an operating system allows a maximum of 10 open files
per process, 10 processes, and 50 open files total; this system could deadlock for
some workloads. On the other hand, if this system increases the global limit to
100 open files, then the open files resource cannot cause a deadlock.
No preemption: Preempt resources. Another technique is to allow the
runtime system to forcibly reclaim resources held by a thread. For example,
an operating system can preempt a page of memory from a running process
by copying it to disk in order to prevent applications from deadlocking as they
acquire memory pages.
No wait while holding: Abort request. Programs can choose not to wait
for resources and abort a request that cannot immediately get all of the resources
it needs. Although this approach sounds extreme, it can provide acceptable
performance and can be much simpler than other alternatives for engineering
deadlock out of a system.
For example, in old-style circuit-switched telephone netoworks, a call would
have to reserve a circuit at a series of switches along its path. If the connection
setup fails to find a free circuit at any hop, rather than wait for a circuit at the
next hop to become free, it cancels the connection attempt, giving the user an
error message (\All circuits are busy. Please try again later.")
Similarly, when a router in the modern Internet is overloaded and runs out
of packet buffers, it drops incoming packets. An alternative would be for each
router to wait to send a packet until the next router has a buffer for it, but such
an approach could deadlock.
No wait while holding: Atomically acquire all resources. Rather than
acquiring resouces in a sequence of steps, programs can be structured so that
threads wait until all required resources are available and then acquire them all
atomically. For example, a dining pilosopher might wait until the two neighbor-
ing chopsticks are available and then simultaneously grab them both.
A thread may not know exactly which resources it will need to complete its
work, but it can still acquire all resources that it might need when it begins
work. For example, in an operating system for mobile phones where memory
is constrained and where memory cannot be preempted by copying it to disk,
