1.1k views

A system has 10 identical resources and N processes competing for them. Each process can request atmost 3 resources but by grouping of first 3 processes needs only 6 resources. Then, the maximum value of ‘N’ is _______.

closed

closed | 1.1k views
0

$6 \ should \ be \ the \ answer !$ Similiar question : https://gateoverflow.in/171647/%23testseries

+3
First 3 processes 2,2,2

then 4 resources are remaining

Give that 4 resources to 3 processes then 1R is remaining.

give that one remaining resource to any of first 3 process and then that process will be done and release resources and so on

+1
thanks
0

https://gateoverflow.in/171647/%23testseries

here ans is 14 right?

8+5+1=14

0
So to deal with such questions we need to allocate peak demand to one of the process from the group, and processes other than group processes, allocate them peak - 1,

like (P1,P2,P3) P4, P5, P6 -->> (3,2,1),2,2,2.

max(3,2,1) = 3

then 3 + 6 + 1 = 10.
0

Ashwin Kulkarni i have a doubt here .

can't we do like this?

 P1 P2 P3 P4 P5 P6 P7 1 1 1 1 1 1 1 1 1 1

as it is given that atmost 3 is needed.   so p1,p2,p3 gets 2 each and p4 ,p5,p6,p7 gets 1 each .

so 7 processes.

what point am i missing?

0

If each one needed at most 3 resources then by distributing all 10, nothing is remaining to complete at least one process among first 3. We have to make sure that one resource should remain their to complete anyone among first 3 processes.
0
so basically we don't know the exact requirement... hence any one of the first 3 can require 3 resources at max to finish.

Eg: P1 - 3

P2-  2

P3 - 1

Hence my solution fails if the above example is implemented.

Thanks :)
+1

@Ashwin

Then, the maximum value of ‘N’ is _______.

Here the question is not clear. It is not mentioned that "max value of N" for what? Either never deadlock occurs, or deadlock can occur?

I am assuming that they are asking for max value of N such that deadlock is guaranteed to NEVER occur. Since if it was the other case, it should ask for minimum value of N.

So now let's see if N=6 is correct or not. i.e. for whatever allocation, the system should not get deadlocked.

So, here are our 6 processes:

P1 P2 P3  P4 P5 P6

__ __ __  __ __ __

Where, each will require at max 3 resources at any time. And the group of first 3 (together) will require at max 6 resources.

Now, Suppose at some time, P4, P5 and P6, each is allocated 2 resources.

P1 P2 P3 P4 P5 P6

__ __ __  2  2  2

Now, we have left with 4 (10 - 2*3) resources.

And P1, P2 and P3 are allocated as follows:

P1 P2 P3 P4 P5 P6

2  1  1  2  2  2 

2 1 1  2 2 2

Now all the 10 resources are allocated. And the system is in DEADLOCK. You can verify it. Now, none of the 6 process can continue, assuming they all are waiting to get max resources they require. Each of the process can't continue since it requires 3 resources, and all have less than 3. Group of P1, P2 and P3 can't continue since that group in total must have atleast 6 resources, but it only have 4. So, this concludes that the system is in deadlock.

So, with N=6, we CAN have a deadlock. And is incorrect.

According to me, answer should be 5.

0
See
when P4,P5,P6 executed
then there are 3 process remaining and 4 resources remaining
Now, We know Need of processes= no of processes+no of resources
So, to make deadlock free , atleast 1 processes must execute
we can give resource of 3 processes like this
2,2,2
or
3,2,1
right?
we can first allocate 1 resource to each process
Now, 4-3=1 resource remaining in hand
If we give this resource to any 1 process, then it will execute
And after execution it releases resorce
So, other waiting process also executes
got it??
0

But I still didn't get it.

To make the system deadlock free, atleast one process must be able to execute, at ANY scenario. That is in whatever way the OS allocates resources, processes must be able to run and compete. i.e. there should be a safe sequence, i.e. it must remain in safe state.

Now, if current allocation is like this (2, 1, 1, 2, 2, 2). As shown in my previous comment. The system is in deadlock. Right?

In your example you have considered a specific case, that is when you allocated 9 resources and left 1 resource with yourself (unallocated).

we can give resource of 3 processes like this
2,2,2
or
3,2,1

For the system to be guaranteed deadlock free, we need to consider all the cases.

?

0
(2, 1, 1, 2, 2, 2) where is deadlock?

now, 4 resources in ur hand for P1,P2,P3

u give 1 resources to each process

Now, u have 4-3=1 process in hand

rt?

give tha 1 resource to P1

So, P1 execute [As P1 requires maximum 2 resouces]

Now, after executing P1 ,P1 release all resouce

Now give that 2 resource to P2 and P3

So, P2 and P3 also will execute

In which case u got deadlock?
0

take any case when we allocated 3,2,1 resources or 2,2,2

To satisfy any combination we need at most 2 resource allocated to each process and 1 should be the backup resource. And this backup resource will help to run any process out of 3.

2 2 2 1 1 1 + 1 backup resource.
0

@srestha

(2, 1, 1, 2, 2, 2) where is deadlock?

We can group only first 3, not last 3. rt?

0
yes

first 3

there is a concept , if 1 execute it's resource, it release it resouce

just put that concept
0
Arrey bhai I know that concept.

But (2, 1, 1, 2, 2, 2) mein koi bhi process nahi ho payega.

minimum requirement is 3, as given in the question.
0
why??
0
(2, 1, 1, 2, 2, 2)

Given each process would require atmost 3 resources. => No process have 3 resources, so none can execute.

Given group of first 3 process together requires 6 resources. => first 3 processes together have only 2 + 1 + 1 = 4 resources. So they also can't execute.

0

u have not read my prev comment properly

atmost 3 resouces are requirement

but not at same time all 3 process require 9 requirement

because We know Need of processes= no of processes+no of resources

for (2, 1, 1, 2, 2, 2) after giving 6 resource to last 3 process

we can first allocate 1 resource to each process
Now, 4-3=1 resource remaining in hand, can give anyone to make it deadlock free

got it??

0

@Shaik

if checking for not having deadlock

first see 3 process needs 6 resources

individually they need 2 resources to be deadlock free.

So, first we are allocating 1,1,1 resource to them...................i

Now remaining 7 resources

give 2,2,2 resources to 3 more processes..................ii

Now, last 1 resource give to any one process and it will be deadlock free

https://gateoverflow.in/66218/go2017-os-6

0

it is incomplete because

It is not mentioned that "max value of N" for what? Either never deadlock occurs, or deadlock can occur?

0

@srestha, Thank u mam....

0
Consider the following case where 6 processes will go into deadlock.

P1 and P2 need max 3 resource each but they are given only 2 each

P3 doesnt need any resource.

At this point first three processes still require a max of 6 resource(3+3+0)

P4,P5,P6 needs 3 but oly 2 are given.

I satisfied all constraints in question but still system is in deadlock

pld help

First, 3 processes combined demand is 6.

Let combined they needed a, b, c resources.

a + b + c <= 6.

And every other process will require 3 resources. Let these processes be x.

By applying pigeonhole principle.

(a - 1) + (b -1) + (c-1) + x(3 - 1) + 1 <= 10.

a + b + c - 3 + 2x  + 1 <= 10

6 - 3 + 1 + 2x  <= 10

4 + 2x <= 10

2x <= 6

x = 3.

So total no. of processes will be x + 3 = 6 processes.
by Boss (16.5k points)
edited
+1
correct but calculation mistake
0
Corrected.
0

@Hemant Parihar may you explain resource allocation?

0
Answer should be 6 or 5 as explained by @VS in the last answer?

0

(a - 1) + (b -1) + (c-1) + x(3 - 1) + 1 <= 10

answer should be 6. In worst case more than 6  processes accessing resources simultaneously may lead to deadlock.

by Boss (44.1k points)
edited
0
@Manu thakur, see this example.

P1 = 3, P2 = 3, P3 = 0, P4 = 3 , P5, = 3, P6 = 3.

P1 + p2 + p3 = 6. (so condition statisfied).
Now suppose p1, p2, p4, p5, p6 takes 2 resources each. Totally they occupied 10 resources. No resources are left.

we can execute p3 but it doesn't release any resources.

Now the processes are in a deadlock.

CORRECT APPROACH

We need to break the resource requirements of P1,P2,P3 keeping in mind 2 things :

1) Each process can request atmost 3 resources

2)By grouping of first 3 processes needs only 6 resources

Possible pairs:(P1,P2,P3)

(0,3,3) , (1,2,3), (2,2,2), (and consider possible permutations of these)

Max resources that ensure deadlock : 2+2 =4 ,  0+1+2=3 , 1+1+1=3

Let the allocation be as follows : (#resources=10)

P1,P2,P3 --> Allocation=4

P4  ---> Allocation=2

P5  ---> Allocation=2

P6  ---> Allocation=2

Now, There is DEADLOCK In the system .Why?

P1,P2,P3 need one more resource to complete in WORST CASE(0,3,3)

P4 need one resource to complete

P5 need one resource to complete

P6 need one resources to complete

As a result all are waiting onto each other and no one continues execution further and Hence,Deadlock !

Now, Whats the correct answer then ?

Maximum processes allowed should  be 5.

P1,P2,P3 --> Max requirement=6

P4  ---> Max requirement=3

P5  ---> Max requirement=3

Let the allocation be as follows : (#resources=10)

P1,P2,P3 --> Allocation=4

P4  ---> Allocation=2

P5  ---> Allocation=2

Now,Till now #resources used =8 , #resources remaining=2

This remaining resource can be allocated to any process P1,P2,P3 or P4 or P5

In either case , that set to whom we allocate the last resource is compelled to complete and release all its resources and hence other processes may then complete their executions.Now, ABSOLUTELY NO POSSIBILITY OF DEADLOCK NO MATTER HOW THE PROCESSES ARE REQUESTING AND HOW THE ALLOCATION IS DONE.

CORRECT ANS=5 processes

by Boss (10.8k points)
edited by
0

Answer is 6 only ! your reasoning is absolutely correct but one flaw ! You are assigning the resources collectively and adjusting you system resources accordingly which OS doesnt follow.Instead no matter how grouping is done collective resources for system is based on individual requirement which ensure no deadlock .
Here in you reasoning you are allocating 5 to(P1,P2,P3) but that doesnt give an insight about which process gets how much if its (3,2,0) then its a wrong way which you have included because at starting no matter what Os has to assign resources irrespective of grouping therefore.
(3,2,1) or (1,2,3) or (1,3,2) this should be scenario through which we can conclude that this subsytem only need 3+1 resources to finish.
https://gateoverflow.in/171647/%23testseries refer analogy part.

0

Again P1:P2:P3 = (6,0,0) (Possible)

Then , Worst case = 5 resources allocated implies Deadlock

by grouping of first 3 processes needs only 6 resources.

It is nowhere written in question that each process has to be allocated atleast one resource as you are assuming.

0

Can you check now ! I edited the answer :)

0
"$\color{Red}{(0,3,3)}$ , (1,2,3), (2,2,2), (and consider possible permutations of these)"
If a process need 0 resource for its computation then why its considered at first place?
0
But, its nowhere written that each process needs atleast one .
And A process needing zero resource can be there eg
If resource under consideration is Printer then its possible that A process doesnot need a printer.
0
You went for charity and decided to give away 3 pens (resources) to each group of 3 childrens.Now there is one group in which one of the guy already has a pen and doesn`t require another.Would you consider it as group of 3?
0
I get your point but still that scenario of a process requiring 0 resource is possible.

Can you give some satisfactory and concrete reason for Neglecting that possibility.
+1
This answer seems correct. 6 is definitely wrong.
0

Now,Till now #resources used =9 , #resources remaining=2

@VS shouldn't #resources remaining  be 1?

+2

In the question it is mentioned  "N processes competing for them"..if at all a process has 0 demand of resource why would it compete ?