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:

A=Sum of all needs

B=Sum of all allocations

C=Sum of all max need

Let's say that our system is not deadlock free right now. If the system is in deadlock then sum of all allocations should be equal to the total number of resources i.e. B = m

Now the statement (b) says that sum of all maximum needs is less than m+ n i.e. A + B = C < m + n.

As from above deduction B = m so, A + m < m + n

or A < n, which means that there is one process for which need it zero as number of processes it greater than need and a process can request and release only one resource at a time. So, there are n-1 processes sharing m resources currently. But no process will wait permanently, hence there is a contradiction and there is no deadlock.