Information Technology Reference
In-Depth Information
in one user's queries or unexpected interactions between two users' queries to
create deadlocks that permanently make some data inaccessible.
For this approach to work, we need ways to break deadlocks when they occur,
ideally with minimal harm to programs, and we need ways to detect deadlocks
so that we know when to invoke the recovery mechanisms. We now talk about
each of these challenges:
Breaking deadlocks
Breaking a deadlock once it has occurred generally requires forcibly taking
resources away from some or all of the deadlocked threads. Because the re-
sources by definition are not revokable, this process generally damages the victim
threads in some way, but it hopefully allows the rest of the system to continue
to function.
As a simple example, when some operating systems decide that a process is
part of a deadlock, they simpy kill the process and release the process's resources.
Although this sounds drastic, if a deadlocked process cannot make any progress
anyhow, killing it does not make it much worse off.
Notice, however, that under the lock-based shared object programming ab-
stractions we have discussed, it is seldom possible to kill deadlocked threads
within a process and allow the other threads sharing the process's shared ob-
jects to continue to function. If the deadlocked threads hold locks on shared
objects, simply killing the threads and marking the locks as free could leave the
objects in an inconsistent state.
Transactions. To allow deadlocks to be broken with minimal disruption in
systems that use locks, we would like to do two things.
First, we would like to ensure that revoking locks from one thread does
not leave the system's objects in an inconsistent state. To do this, we
would like to be able to undo a deadlocked thread's actions. Then, to x
a deadlock, we can choose one or more victem threads, stop them, undo
their actions, and let other threads proceed.
Second, once the deadlock is broken and other threads have completed
some or all of their work, we would like to be able to restart the victem
threads. If these threads can now complete, the system operates as if the
victem threads never caused a deadlock but, instead, just had the start of
their executions delayed.
Transactions, which we discuss in detail in Chapter ??, are widely used in
databases and provide these two properties.
