Recovery from
Deadlock
There are three basic approaches
to recovery from deadlock:
- Inform
the system operator, and allow him/her to take manual intervention.
- Terminate
one or more processes involved in the deadlock
- Preempt
resources.
Process
Termination
Two basic approaches, both of
which recover resources allocated to terminated processes:
- Terminate
all processes involved in the deadlock. This definitely solves the
deadlock, but at the expense of terminating more processes than would be
absolutely necessary.
- Terminate
processes one by one until the deadlock is broken. This is more
conservative, but requires doing deadlock detection after each step. In
this case there are many factors that can go into deciding which processes
to terminate next.
Resource
Preemption
When preempting resources to
relieve deadlock, there are three important issues to be addressed:
- Selecting a victim - Deciding
which resources to preempt from which processes involves many of the same
decision criteria outlined above.
- Rollback - Ideally one would like to
roll back a preempted process to a safe state prior to the point at which
that resource was originally allocated to the process. Unfortunately it
can be difficult or impossible to determine what such a safe state is, and
so the only safe rollback is to roll back all the way back to the
beginning. ( I.e. abort the process and make it start over. )
- Starvation - How do
you guarantee that a process won't starve because its resources are
constantly being preempted? One option would be to use a priority system,
and increase the priority of a process every time its resources get
preempted. Eventually it should get a high enough priority that it won't
get preempted any more.
No comments:
Post a Comment