Deadlock

Question

A computer system has 6 tape drives with n processes competing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlock free is

a) 1 b) 2 c) 3 d)4

Ans given is 2....But for 4 processes also there will be no deadlock ....If we initially allocate 1 to each process 2 will be available...and we can allocate those 2 to the first process...after its execution 3 tape drives will be free..and 2 could be allocated to next process...so continuing in this way we can allocate resources to each process without any deadlock......

Plz explain why answer given is b)

Answer 1

For a system to be deadlock free, Sum of max need of processes < No. of processes + No. of resources

3n < n + 6

=> 2n < 6

=> n < 3

so the maximum value of n for which the system is guaranteed to be deadlock free is  2 [ n is less than 3 means max value for n is 2 ]

Answer 2

We have to guarantee that the system will be deadlock free in every condition. So first of all we can't invent easy ways to allocate resources to the process, we have to see that even in worst condition, there is no deadlock (as per given question). So in case of 2 processes there may never be possibility of deadlock. In case of 4 processes, not with your scheme of allocation but with some other allocation- for ex, give 2 resource to P, 1 to Q, 2  to R and 1 to S-- results in deadlock-- so it is not guaranteeing no-deadlock in 4 processes,, while in case of 2 processes , system is guaranteed to be deadlock free.

Comments

Yes. With 2 processes a deadlock cannot be formed as 2*3 = 6 resources are available and all requests from all processes can always be satisfied. With 3 processes onwards, MAX requests can exceed AVAIL resources, and there is a POSSIBILITY of deadlock. 

---

@Prateeksha Keshari @Arjun @Bikram @srestha

But, Safe State (Banker's Algorithm) means that there is atleast one way we can assign resources to processes such that there is no Deadlock.

Answer 3

Each process needs 3 tape drives to run to completion.

P1 P2 P3

2    2   2                    This is a deadlock state.as each of the process is                                  waiting for one resource at the same time, the                                         system has reached max of its available                                              resources and there are no resources available which can be taken by any process and can run to completion,.

Any number of process which is <3 ,is deadlock free scenario.

If there are 0,1,2 processes then there would be no  deadlock.As in the maximum scenario of 2 processes running ,both utilizing 4 resources we still have 2 more resources left which can be taken by either of P1 or p2,and can run to completion,.

Ans is 2.

Answer 4

Each process may need 3 resources. Let's pull 1 resource back from each.

=> $2n$ resources.

Let's throw in 1 extra resource such that one process' max needs are definitely served at any given time. (Pigeonhole principle)

=> $2n+1$ resources.

 

So, at least $2n+1$ resources are needed to stay away from deadlock.

ie, $2n+1 \leq 6$

 

Let's take the worst case.

$2n+1 = 6$

=> $n=2.5$

So, we can have maximum $2.5$ processes in the given system to keep it deadlock free.

Can we have $2.5$ processes? No.

So, $2$ processes.