In computer science, Deadlock is a naughty boy aroused by compete for resources. Even now,
there isn't a valid method to deal with it. This is amazing. You know, we have many excellent
scientists, not all of issues can fight with us so many years. Fortunately, we can still do something
by sacrifice some system efficiency. Those methods can be divided into three categories:
Preventation, avoidance, and detection. Let us examine them at the following text.
1.Deadlock Preventation
Deadlock preventation is aim to solve this problem radically. From some point of view, the
deadlock is weak. It must satisfy some conditions:
a). the use of resource is mutual exclusive.
b). No preemptive.
c). some processes hold the resource that another process waiting.
d). circle waiting. i.e: P1 wait P2 release a special resource, P2 wait P3, and P3 wait P1.
Those are necessary conditions. If only we can break one of them, we can win this war. That
naughty boy will never occur again. The condition (a) is hard to break since we need mutual
exclusion to ensure the safe of data access, this is reasonable. Now, let us see the remainder.
condition b -- request all required resources at one time. If the process can't get all of them,
then release all of them, and try again.
condition c -- If we can rob a resource from the process and restore it easily. This will be
good choice.
condition d -- by some ingenious arrangement , we can overcome a circle waiting.
2.Deadlock Aviodance
Deadlock Avoidance is aim to dynamically avoid a deadlock. From some point of view, this is
possible. But there are some restriction in this method. Now, the problem is how can we ensure
a action is safe when a process want to allocate some resources. can we ?
we can. As we all know,one of the reason that aroused a deadlock is that the required resource
has been exceed the exist resources. So we can know whether a action lead to a deadlock
potentially by this rule. First at all, we need save some information about the status of resouces.
The following item is necessary. How many resources in this system? How many resouces is
available? the list of processes which need to those resources? The list of resources which has
been allocated by processes?
There must be have many solutions. A common method to record those information as following:
A vector for available resources. i.e:
[1,2,3]
that means resource R1 have 1 unit in current system status; In a similar way, R2 have 2 units,
and R3 have 3 units.
A vector for the total amount of resources.
[2,3,4]
that means the total of resources R1 is 2 units, R2 is 3, and R3 is 4.
A matrix for the amount of allocated resources.
R1 R2 R3
P1 1 0 0
P2 0 1 1
P3 0 0 0
That means P1 has allocated a R1, P2 has been allocate a R2 and R3, and P3 has
allocated nothing.
A matrix for the amount of resources what required by process. i.e:
R1 R2 R3
P1 1 1 1
P2 1 1 1
P3 1 0 1
That means, if process P1 want to complete it's work, it need one R1, one R2 and one R3.
Based on our convention above, There are some strategies.
solution 1:
Don't start a process if it's demand may lead to a deadlock.This is conservative strategy.
we always assume the worst situation. In other words, every process allocate all required
resources when it start. So if we want to start a process X,we need to know whether this
condition can be satisfied.(if the process 1~n has running)
C[1][i] + C[2][i] +.... C[n][i] + C[x][i] < R[i] (for all of i)
Athough it is work, but there are some problems here because not all of resources are
required all the time. Some of them may be used rarely.
solution 2:
if all of processes are independent, except for the use of some common resources.
we could use a more effective method--nest. In this strategy, we grant the request of a
process only if this process could be completed by current available resources .Think
about this situation:
At the beginning. The status of system is,
V(available) = (5);
R(Resources) = (10);
A(Allocated) = { {2},
{3},
{0} };
C(Claim) = { {8},
{5},
{5} };
Based on this status, we could get
C - A = { {6},
{2},
{5} };
we can know P1 can't working because they need 6 uint of resouces and that is out
of the system's league.In contrast, P2 and P3 is good. In this situation, what should
we do?
The answer is refuse the request from P1, because P1 maybe lead to a deadlock.
Based on our analysis above,If we get a request from P2 about request 1 unit of
resource, that request should be granted. Then status will become
V(available) = (4);
R(Resources) = (10);
A(Allocated) = { {2},
{4},
{0} };
C(Claim) = { {8},
{5},
{5} };
and
C - A = { {6},
{1},
{5} };
In this status, P1 and P3 is not a nice guy. we should refuse both them....
This strategy was called Banker's Algorithm. As we can see, if all of processes is independent,
it will work more better than the above one.
3. Deadlock Detection
The method above is working by add some restriction to the process. But Deadlock Detection
is different. It didn't work untill a deadlock occur. In this strategy, the system will grant all of
request , but will detect whether a deadlock has occur. If a deadlock has been found, the system
will deal with it by some method. There are two problems here:
Q: How can we detect a deadlock?
A: Actually, this is easy. Recall the banker's algorithm, in there we avoid a deadlock by ensure
every request is come from a safe process. If we reverse the progress of the banker's
algorithm, we can get what we want.
a). detect all running processes whether there is a safe process in system. If success,
go to next step, Or ,terminate this detection.
b). find a safe process which can working by current available resources.
c). Assume this process has been completed and release all of resources what it allocated.
d). return to step a.
when we terminate this detection, the remainder process,which is unlabeled, maybe involve
a deadlock.
Q: How can we recover it?
A: Actually,there isn't a valid method to do this. That is awful.Fortunately,some method,which
are not so valid,can working .For example:1).we could set some restore points.But the problem
is where should be the point;2).Re-assign resource; and so on. we can choice them based on
where it is.
Deadlock preventation, Deadlock avoidance, and Deadlock detection is aim to deal with a
deadlock from the point of view of system. But it is the responsibility of the programmer also.