Question

Consider a system having p processes, where each process needs a maximum of m instances of resource type R1. Given that there are r instances of resource type R1 in total, what is the minimum value of r as a function of p and m to ensure that the system is deadlock free?(An explanation in addition to the formula would be very helpful, thanks)

Answer 1

Answer:

Consider a system consisting of 4 resources of same type that are share by 3 processes each of which needs at most two resources.Now we will show that the system is deadlock free.

If the system is deadlocked, it implies that each process is holding one resource and is waiting for one more. Since there are 3 processes and 4 resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

Consider a system with m resources of same type being shared by n processes. Resources can be requested and released by processes only on at a time. The system is deadlock free if and only if The sum of all max needs is < m+n .

We can understand the notion of a deadlock from the following simple real-life example.To be able to write a letter one needs a letter pad and a pen. Suppose there in one letterpad and one pen on a table with two persons seated around the table. We shall identify these two persons as Mr. A and Ms. B. Both Mr. A and Ms. B are desirous of writing a letter. So both try to acquire the resources they need. Suppose Mr. A was able to get the letter pad. In the meantime, Ms. B was able to grab the pen. Note that each of them has one of the two resources they need to proceed to write a letter. If they hold on to the resource they possess and await the release of the resource by the other, then neither of them can proceed. They are deadlocked. We can transcribe this example for processes seeking resources to proceed with their execution. Consider an example in which process P1 needs three resources r1 ; r2, and r3 before it can make any further progress. Similarly, process P2 needs two resources r2 and r3 Also, let us assume that these resources are such that once granted, the permission to use is not withdrawn till the processes release these resources. The processes proceed to acquire these resources. Suppose process P1 gets resources r1 and r3 and process P2 is able to get resource r2 only. Now we have a situation in which process P1 is waiting for process P2 to release r2 before it can proceed. Similarly, process P2is waiting for process P1 to release resource r3 before it can proceed. Clearly, this situation can be recognized as a deadlock condition as neither process P1 nor process P2 can make progress. Formally, a deadlock is a condition that may involve two or more processes in a state such that each is waiting for release of a resource which is currently held by some other process.