2k views

Given below is a program which when executed spawns two concurrent processes :
semaphore X : = 0 ;
/* Process now forks into concurrent processes P1 & P2 */

P1 P2
repeat forever
V (X) ;
Compute ;
P(X) ;
repeat forever
P(X) ;
Compute ;
V(X) ;

Consider the following statements about processes P1 and P2:

1. It is possible for process P1 to starve.
2. It is possible for process P2 to starve.

Which of the following holds?

1. Both I and II are true.
2. I is true but II is false.
3. II is true but I is false
4. Both I and II are false

The main function of down operation is to wake up the blocked process from queue and put into the critical section

what you have written is a function of V(S) i.e is up operation..

joshi_nitish  thnq for correcting me ,now my question is event value of x=0,process p1 can enter in cs then in this case the value of x is o still .if process p2 comes it will wait for p1 infinitely long time ?Am I right ?

Down operation means P ( wait) , it means if the value of semaphore variable is not negative, decrement the value by 1. If the semaphore variable is now negative, the process executing wait is blocked (i.e., added to the semaphore's queue) until the value is greater or equal to 1.

And Up operation (Signal ) V means : First increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

Here P1 is performing up and P2 performing down operation.

if we start from P1, initially x ==0 , so after V(x) it's new value would be x==1

and for P2 ,  x==0 so it need to wait until x become 1.
@bikram sir if the value of x==1 .after up operation for p1 it will do nothing or according to question it will go into critical section ?and if this time  p2 wants to enter in cs it will go becoz value of x is 1 for p2 ?

if the value of x==1 .after up operation for p1 , according to question it will go into critical section .

if this time  p2 wants to enter in cs it will go becoz value of x is 1 for p2

It may be possible p1 keep looping so that makes the possibility of starvation for p2.

Another possibility is p2 can enter and keep looping so p1 can starve .

So both are possible.

Check : What is Starvation?

Here $P_2$ can go in infinite waiting while process $P_1$ executes infinitely long.

Also, it can be the case that the Process $P_1$ starves for $\infty$ long time on the semaphore S, after it has successfully executed its critical section once, while $P_2$ executes infinitely long.

Both $P_1$ and $P_2$ can starve for $\infty$ long period of time.

selected by

p1,p1,p1,p2,p2,p1,p1,p2 etc is also  strict alteration only as there are only two processes.

yes, correct assumption ..

@srestha see this as Next entry is reseved for only p2 so it is strict alternation.

@Bikram Sir,
A process executing up operation never gets blocked. Is it correct statement ??

Up operation ( Signal V )  transfers a blocked process from the semaphore's waiting queue to the ready queue.

So yes , executing up operation never gets blocked.  It is correct statement .

but is it guaranteed to have a queue?
@ Bikram sir

By default, semaphores do not have queue implementation right??

Case 1:Here P1 is performing signal operation so it is first one to start...Now it may happen that after executing CS it makes X=0 again tries to enter CS my making X=1 so it is possible that P2 can starve(just a possibility)

Case 2:If P1 executes signal operation and its execution is suspended temporarily, P2 executes wait and enter CS  and then execute signal operation making X=1 now P2 can enter critical section by executing wait operation..this may happen for infinite amount of time..so in this P1 may starve
edited
actually we are not told to ensure mutual exclusion. The given code does not ensure it.

I. Case: P1 will enter its critical section once at the beginning and then only P2 keeps on entering its critical section again and again. Thus, making P1 starve.

II. Case: P1 will enter its critical section once at the beginning and then only P1 keeps on entering its critical section again and again. Thus, making P2 starve.

after process P1 run for one time  ;

when process P2 into critical section , process P1 can enter into critical section every time ...so it is not possible process P1 to starve ....

when process P1 into critical section , process P2 can enter into critical section every time ...so it is not possible process P2 to starve ....
Please elaborate more on this with the help of examples.

Ans A)

P1 starts , and go infinitely . So P2 starves here.

P2 cannot start process any time.right?

Now, P1 starts and makes semaphore value X=1 and executes CS once. Now, P2 takes this semaphore and executes infinitely. So, P1 starves here

Now, P1 starts and makes semaphore value X=1 and executes CS once. Now, P2 takes that semaphore and it also executes it's critical section then Pagain takes this semaphore and looks which one executes next V(s) of P1 or P(s) of P1 or P(x) for P2 .

So, more than one process can be in CS here

So, Mutual Exclusion violated , But Progress and Bounded Waiting satisfied here

if bounded waiting has been satisfied then , there will be no starvation...

BW is not satisfied here..

Here

ME is satisfied.

BW is satisfied .

Progress is violated.

See this comment

Initially x = 0

p1 ups --- x = 1

p2 downs --- x= 0

--Now both are in critical section----

p2 ups first this time-- ( x = 1 , no one blocked till now)

p2 downs again (x= 0 )

Now p1 downs (x = 0, p1 blocked --- now whenever x ups p1 will wake up first..)

p2 ups (x= 0 , p1 unbloked and resumes so, no starvation here)

Can p1 be down any time?

Can we tell it is like producer consumer problem.

there can be many cases like this

P(X)        V(X)

P(X)         V(X)

or

P(X)       P(X)

V(X)        V(X)

What is the starvation or deadlock for these too. If one could be solved, other can be solve also.rt?
Yes, there are many possibilities.. here starvation possible so progress can not satisfy either for p1 or for p2.

And in 2 process CS problem with strict alternation BW is satisfied.
I think no process will starve but mutual exclusion may not be possible.

And option D is correct.
As x is 0 process p1 will compute first. While p1 is in critical section(compute) x=1 then process p2 can execute p(x) and be in compute too.

Right or not??
It is clear that P1 will go to CS first. Now what is starvation? If P1 goes to CS a finite number of times and then just wait indefinitely, is this starvation?

Yes talking about possibility then yes it is possible for both P1 and P2 to starve.

Case 1:

Intially P1 executes V(x) and makes  x=1. P1 is in CS.

then P2 executes P(x) and makes x=0 and  P2 is also in CS. P2 executes several times and not letting P1 complete even a single times. (P1 starves)

Case 2:

Intially P1 executes V(x) and makes  x=1. and P1 is in CS. Now instead of P2, P1 completes its execution  with P(x) of P1. P1 goes into CS several times and not letting P2 into CS even a single times. (P2 starves)

+1 vote
Ans is A.
edited

As  semaphore x , value is 0

So , if p2 executes then deadlock occurs. So, P1 executes first , the value of x increments and p1 entries in the critical section ,suppose P2 preempts the execution of P1 . After the complete execution of P2 , the rest code of P1 executes. Therefore , P1 and P2 both will get a chance to enter its critical section at once . They both will not starve for infinite time . So answer D is correct

C

Consider a situation such that process P2 never preempt process P1 then process P2 will starve.

If semaphore was a binary semaphore the process P1 could also starve but here nothing is give so we'll take it to be a general semaphore.

why cant p1 starve ?
p1:v(x)   x=0 to 1

p1:compute

p2:p(x)    x=1 to 0

p1:p(x)    wait

p2:compute

p2:v(x) x=0 to 1

p2:p(x) x=1 to 0

and so on

in this case p1 will starve isnt it ?
Here mutual exclusion, progress and bounded wait, all 3 are not guaranteed.

However process p2 can starve if P1 keeps on executing forever. Note that p2  cannot execute forever in any case so P1 can never starve. So ans is C.
progress is guaranteed rt?

@mojo: p2 can also execute forever.

I think progress not guaranteed..suppose initially only P2 wants to enter the CS..not P1.Then P2 cant enter the CS.It has to wait for P1 to enter the CS as X=0.

So decision of who will enter into CS is depended on P1 who is not interested to enter(in this situation).

So its against progress statement.

correct me if i m wrong
@kishalay here we can't maked any assumption as p1,2:repeat forever is used
what does it prove??..progress satisfied?
progress defination says, one process should not stop other process from entering the CS, & that forever,

here its temporary due to starvation,

here a possibility haas been asked, its like there exists,(_OR_ OR..) so we only need to proove 1 possibility in which the statements turns out to be true(A)... if cant find any such case then all false (D)
Sorry Nitin i did not get what are u trying to say
check now?