The Gateway to Computer Science Excellence
+9 votes
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
in Operating System by Active (4k points)
closed by | 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

hence answer is 6.
+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
@gari you have made a deadlock condition.

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.

is it wrong anywhere? PLEASE HELP ME BRO. _/\_

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?
So, to make deadlock free
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
And system becomes deadlock free
got it??
0

@srestha Thanks for replying.

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?

P4,P5,P6 already executed

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

Where is deadlock?

In which case u got deadlock?
0
@Rishabh I got your point.

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?

P4,P5,P6 already executed

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.

so deadlock.
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

3 Answers

+11 votes
Best answer
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 by
+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?

@Arjun sir @srestha help please.
0

please explain this formula 

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

+2 votes

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

by Boss (44.1k points)
edited by
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.
+2 votes

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 doesn`t 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 doesn`t 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

@saxena0612 

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

@saxena0612 

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 ?

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
198,402 comments
105,158 users