1
$\begingroup$

I know that unsafe state does not always mean deadlock. That is a situation that banker's algorithm does not detect deadlock accurately. I am just wondering if there is any example of a safe state that deadlocks?

$\endgroup$
1
$\begingroup$

No deadlock as long as you keep running the Banker's algorithm.

By definition, a state is considered safe if it is possible for all processes to finish executing, which means there is no deadlock.

In order to avoid triviality, the question should be asking whether a safe state might change into deadlock. Assume the system is in a safe state (or the system is safe in short) initially. If you are able to run the Banker's algorithm, then

  1. each time a request for resources is raised, the system will

    • either reject the request so the state will not change, meaning the system is still safe of course.
    • or it will grant the request after it have been verified that after the requesting process has obtained those resources the system will still be safe, meaning the system is still safe.
  2. each time some resources is returned, the system will obviously still be safe.

So, you can see that almost by definition and design, a safe state never goes into deadlock under the Banker's algorithm.

A more interesting question might be whether the system guarantees to make progress. The answer is yes, too. For any process, it is assumed that maximum number of instances of each resource type may not exceed the total number of resources in the system. It is also assumed that when a process gets all its requested resources it must return them in a finite amount of time. Suppose at some point of time, no process is able to run yet because of its lack of resources. Since the system is safe, resources will be allocated upon requests continuously until one of process is able to get all the resources it needs, meaning that process will start to run and progress will be made. After some finite amount of time, that process, having made some progress, must return all its requested resources to the system. Now the system is sort of back to square one but with progress made.

For a more rigorous analysis, you can check Selected Writings on Computing: A Personal Perspective , Springer-Verlag, 1982, by the algorithm's designer Edsger W. Dijkstra.

$\endgroup$
  • $\begingroup$ Thanks so much for such precise analysis. I have one more followup question. Is there any case that Banker's algorithm fail to prevent deadlock? Or maybe the question should be is there any deadlock case cannot be prevented by Banker's algorithm? $\endgroup$ – MChotdog Sep 28 '18 at 21:18
  • $\begingroup$ No deadlock can occur, as long as the Banker's algorithm is running continuously under its required assumptions. However, it is impossible to keep those assumptions all the time in practice because of the influx of new processes and the dynamic change of existing processes. So sometimes deadlock cannot be prevented since we cannot run Banker's algorithm successfully any more. That is why we need deadlock detection and deadlock recovery. You can check the Wikipedia entry on its limitations. $\endgroup$ – Apass.Jack Sep 28 '18 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.