Question

Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:__________.
A. The maximum need of each process is between 1 and m resources
B. The sum of all maximum needs is less than m+n.

Answer 1

Answer:

Explanation:

The system will be deadlock free if the below two conditions holds :

Proof below:

Suppose N = Summation of all Need(i), A = Addition of all Allocation(i), M = Addition of all Max(i). Use contradiction to prove.

Suppose this system isn't deadlock free. If a deadlock state exists, then A = m due to the fact that there's only one kind of resource and resources can be requested and released only one at a time.

Condition B, N + A equals M < m + n. Equals N + m < m + n. And we get N < n. It means that at least one process i that Need(i) = 0.

Condition A, Pi can let out at least 1 resource. So there will be n-1 processes sharing m resources now, Condition a and b still hold. In respect to the argument, No process will wait forever or permanently, so there's no deadlock.