6.4k views

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

$\begin{array}{|l|l|}\hline \text{$P1$} & \text{$P2$} \\\hline \text{repeat forever } & \text{repeat forever} \\ \text{$V (X) ;$} & \text{$ P(X) ;$} \\ \text{Compute; } & \text{Compute;}\\ \text{$P(X) ;$} & \text{$V(X) ;$} \\\hline \end{array}$

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

edited | 6.4k views
+1
how?
0

@reena+kandari Question says It is possible, it doesn't says that it is always right.

+2
@reena Before 2011 there were no official GATE keys :)
0
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)
0
in worst case both can starve foreever, if possible..
0
@Bikram Sir and @Arjun Sir pls explain this

The main function of up operation is to wake up the blocked process from queue and put into the critical section .In this question if we start from p1 it can go into the critical section becoz for up operation even the x=0 it not matters and new value of x is still 0, after going into cs if P2 wants to enter or perform down operation it will be blocked ,it still wait for p1 to come out from cs .My doubt ,is after this how p1 will perform up operation? is this unambiguous?

P1 will starve for come out from cs and P2 will starve to go into the critical section .Is this fine ?
+1

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

0

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 ?

+2
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.
0
@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 ?
+2

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.

+15

Mutual exclusion is not satisfied.

Suppose P1 executes V(x) and enter compute and gets preempted. Now P2 can execute P(x) and enter Compute.

Progress is not satisfied.

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. The decision of who will enter critical section is dependent on p1 who is not interested to enter CS.

Bounded Waiting is not satisfied.

Suppose p1 executes completely and gets preempted. P2 can't enter CS since X = 0. Again P1 executes completely and gets preempted. Again P2 can't enter CS.

+3
@shivam chauhan

Yes, Mutual exclusion and progress are not satisfied here. But bounding waiting is satisfied.

When P2 show the desire to go into CS and got sleep. Then, when P1 do V(X) then it will wake up the P2 to go into CS.
0
Wake up operation is done only if we have a blocked list of processes maintained. And by default, there is no queue associated with counting semaphore. So P1 after executing V(x) does not necessarily preempt and can move into compute.

See the answer both P1 and P2 can starve.
+5

Hi @Shivam Chauhan ji

And by default, there is no queue associated with counting semaphore

Could you please mention some reference for this ?

I think, after V(S) of $P_{2}$, $P_{1}$ will also come in ready state (If in case it was waiting for V(S) operation) but $P_{2}$ could be selected for execution again. Due to which $P_{1}$ could be moved back to blocked list of respective semaphore.

@Hemant Parihar and @Shivam Chauhan ji What is your opinion ?

+3
Doubt regarding bounded waiting

Considering the case in which P1 is executing the CS, P2 enters the CS (as mutual exclusion not satisfied here), suppose P1 wants to exit first, it will be blocked at P(X). It will only be unblocked when P2 comes out of the CS and finishes the remaining code i.e V(X). So value of X will be 1 again. Thus, either P1 can finish the remaining code by using X value or P2 can use X value to again enter CS. Here, we cannot say when will that happen as there might be a case in which P2 keeps on coming. So, bounded waiting not satisfied. Is this approach correct?

Also, is there a relation between starvation and bounded waiting?
+1
there is no bounded waiting  otherwise process executes infinitely long.
0
@Arjun Sir, Can you please confirm in this case bounded waiting is satisfied or not? Because any process can go infinitely long, So no bounded waiting.
+1
P1 P2
repeat forever
1.V(X);
Compute ;
2.P(X);
repeat forever
3.P(X);
Compute ;
4.V(X);
1. It is possible for process P1 to starve.

yes this can be happen here x=0; In P1:1,compute,2 (here after V (x) operation x=1 so P(x) will also be execute again line no 1 is up operaton it will execute..... like this it can go infinitly so P2 have to starve. )

2.It is possible for process P2 to starve

if we start our execution from P2 then X=0, so  P(x) will not be performed because it is down operation and mutex value is 0 , now it will go to process P1 then V(x) operation will performed so X=1 Now Assume after v(x) p1 preempted then it will go to P2 here x=0 so down condition of p2 will performed again v(x) of p2 like...

P2:line 1(blocked)|P1:line1(preempted)|P2 line1,(compute), line 2(Vx) so after it it value of X=1 so again P2 will executed again compute and v(X)....... INFINITLY. THATS WHY A is the correct option

0

Another possibility :

since the P1 & P2 are spawed after executing fork() hence by the concept of fork(), both P1 & P2  will now get their separate variable  x initiaized to 0. In that case

For P1:

P1 will execute once and go in infinite waiting. Since P2 can't execute signal on P1 's X.

For P2:

Similarly P2 will have its own X=0 hence it will also go in infinte waiting.

Therefore both processes will starve. hence option A

0

" Since P2 can't execute signal on P1 's X. "

0
0
yes, bounded waiting will not satisfied by this code.

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.

by Boss (30.6k points)
edited
+3

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.

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

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 .

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

By default, semaphores do not have queue implementation right??
+1
@Arjun
I went through all the comments, and i am unable to understand onething, when both processes can wake to each other up, then why will even they starve?
+1
we are considering worst case ...
+2

Hi @sushmita ji,

By default, semaphores do not have queue implementation right?

Could you please mention some reference ?

0

Hi @Manu Thakur ji,

I went through all the comments, and i am unable to understand onething, when both processes can wake to each other up, then why will even they starve?

0
Later, i understood that part. Anyway,Thanks @Chhotu ji,
0

@Manu Thakur ji

Later, i understood that part

0

Executes infinitely long

this means while computing it takes infinitely long time right ?

0
P1 never be starve because in the beginning it do not wait it directly enter into critical section but it is possible that if P1 size is large then p2 suffer from starvation
0

@Arjun

sir by default binary semaphores also do not have queue?

0

1."If a process enter CS at least once then No starvation"   is False. ???    i think correct one will be "Execute cs completely" means no starvation am i right?

2.There may be case when though Process is in CS and pre-emted then after that it is not able to enter that might lead to Starvation" ??

3.I read somewhere "Starvation for Pi if and only by all means Pi never get chance to execute CS "

This is False???

0

@Bikram sir

@Arjun Sir

my only doubt is which implementation of semaphore is to be considered in such questions?

the one with queue implementation or other one with spinlock ( busy waiting with no queue )

0
0

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
by Boss (31.2k points)
edited
+2
actually we are not told to ensure mutual exclusion. The given code does not ensure it.
0

1."If a process enter CS at least once then No starvation"   is False. ???    i think correct one will be "Execute cs completely" means no starvation am i right?

2.There may be case when though Process is in CS and pre-emted then after that it is not able to enter that might lead to Starvation" ??

0

There may be case when though Process is in CS and pre-emted then after that it is not able to enter that might lead to Starvation" ??

yes  bounded waiting can cause starvation and it can cause deadlock too.

0

Can you give example where bounded waiting lead to deadlock & starvation?

0

Check this line of selected ans.

Here P2 can go in infinite waiting while process P1 executes infinitely long.

This itself means a chance of deadlock.

Option A (If we consider the Classical Busy Waiting Definition of Semaphores (Such Semaphores are called Spinlocks, Given in Galvin Book))

or

Option D (If we consider the Blocking Definition of Semaphores(Queue implementation as some Students call it)).

NOTE that Galvin provides both the definitions and calls both the definitions (Busy Waiting definition and Blocking Queue Definition) as Semaphores. Hence, the confusion arises which definition to use. But....

Many other authors(William Stallings or Tanenbaum) use the term semaphore only for blocking solutions(Queue implementation as some Students call it) and would call Busy waiting solutions spin locks.

Let's see everything in detail.

Semaphores can be of one of the Two types : Binary Semaphores or Counting Semaphores(General Semaphore)

Furthermore, There are Two definitions of Semaphores, One is with busy waiting (Called Classical Definition) and One with Blocking solutions. Some authors use the term semaphore only for blocking solutions and would call Busy waiting solutions spin locks.

So, We have Four possible scenarios here regarding Semaphores.

1. Binary semaphores with Busy Waiting

2. Binary semaphores with Blocking Solution

3. Counting semaphores with Busy Waiting

4. Counting semaphores with Blocking Solution

Let's analyze the given Question using each of the above definitions.

1. Considering Binary semaphores with Busy Waiting :

Definition of "Binary Semaphores with Busy Waiting" :

In classical definition of Binary Semaphore, Binary semaphore is just a simple Boolean Variable.

A binary semaphore $S$ takes on two possible values 1(Open/Available)' and 0(Closed/Unavailable)''

• Two usual Atomic semaphore operations are supported $P,V$
• $P(S)$ is
   P(S) {
while (S==0) {}  // Loop as long as S is 0.
S = 0 ;   // This is NOT the body of the while, It means Set S with value 0 if S was 1 earlier.
}
• V(S) is simply S<-- 1

i.e. $V(S) \{$

$S = 1;$

$\}$

Analyzing the given Program using this Definition :

In this case i.e. When Considering Binary Semaphore with Busy Waiting, It is possible for both processes to Starve.

It is possible for $P2$ to starve :

Let me show you a possibility of $P2$ getting starved for CS.

Run $P2$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P2$ will be stuck in the loop. Now, When $P1's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, $P1$ will enter into CS. And Let it execute $P(X)$ and now $X$ will become 0. Now at this moment, preempt $P1$ and run $P2.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P1$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P1$ after executing $P(X)$ and run $P2.$ and so on.. So, $P2$ will starve for Critical Section(CS) this way.

It is possible for $P1$ to starve :

We can make a similar situation for $P1$ as well.

Let me show you a possibility of $P1$ getting starved for CS.

Run $P1$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $V$ operation, $X$ will become 1. Now, $P1$ will enter into CS. And Now preempt it and run $P2.$ Let it execute $P(X)$ and now $X$ will become 0. Now $P2$ will enter into CS. Now preempt $P2$ and let $P1$ run.  Since the value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P1$ will be stuck in the loop. Now, When $P2's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, let $P2$  execute $P(X)$ and now $X$ will become 0. And $P2$ will enter into CS. Now at this moment, preempt $P2$ and run $P1.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P2$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P2$ after executing $P(X)$ and run $P1.$ and so on.. So, $P1$ will starve for Critical Section(CS) this way.

So, When Binary Semaphores with Busy Waiting Considered, Answer will be Option $A.$

2. Considering Binary Semaphores with Blocking Solution.

Definition of "Binary Semaphores with Blocking Solution" :

The main disadvantage of the semaphore definition with busy waiting given above is that it requires Busy Waiting. While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code. This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that some other process might be able to use productively. This type of semaphore is also called a Spinlock because the process "spins" while waiting for the lock.

To overcome the need for busy waiting, we can modify the definition of the wait() and signal() semaphore operations. When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute.

A process that is blocked, waiting on a semaphore S, should be restarted when some other process executes a signal() operation. The process is restarted by a wakeup () operation, which changes the process from the waiting state to the ready state. The process is then placed in the ready queue. (The CPU may or may not be switched from the running process to the newly ready process, depending on the CPU-scheduling algorithm.) To implement semaphores under this definition, we define a semaphore as a "C' structure :

Each semaphore has a Boolean value and a list of processes list. When a process must wait on a semaphore, it is added to the list of processes. A signal() operation removes one process from the list of waiting processes and awakens that process.

The wait(), and Signal() semaphore operations can now be defined as following (Image source : William Stallings Book) :

The block() operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a blocked process P. These two operations are provided by the operating system as basic system calls.

Analyzing the given program using this definition :

In this case i.e. When Considering Binary Semaphore with Blocking Solution, It is NOT possible for any process to Starve.

The Idea/Hint is that If a process blocks itself on Semaphore $X$ then the other process will wake it up. And Hence, as soon as a process shows interest in accessing CS by executing its Entry code, It will get into CS within a bound of 1. So, Here, Bounded Waiting is Also Satisfied. So, If you analyze the given program using Blocking solution definition of Binary semaphore little bit more, you'll find that Starvation, Deadlock etc are Not possible and BW is Satisfied.

Note that Bounded Waiting is Not related to Starvation/Deadlock in any way.

So, When Binary Semaphores with Blocking Solution is Considered, Answer will be Option $D.$

3 . Considering Counting Semaphore with Busy Waiting :

Definition of "Counting Semaphores with Busy Waiting" :

In this scenario, A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal ().

The definition of wait () is as follows:

$P(S)$ is

•    P(S) {
while (S<=0) {}  // Loop as long as S is 0.
S-- ;   // This is NOT the body of the while, It means decrment S if S was > 0 earlier.
}
• V(S) is simply S++

i.e. $V(S) \{$

$S++;$

$\}$

Analyzing the given Program using this Definition :

In this case i.e. When Considering Counting Semaphore with Busy Waiting, It is possible for both processes to Starve.

It is possible for $P2$ to starve :

Let me show you a possibility of $P2$ getting starved for CS.

Run $P2$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P2$ will be stuck in the loop. Now, When $P1's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, $P1$ will enter into CS. And Let it execute $P(X)$ and now $X$ will become 0. Now at this moment, preempt $P1$ and run $P2.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P1$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P1$ after executing $P(X)$ and run $P2.$ and so on.. So, $P2$ will starve for Critical Section(CS) this way.

It is possible for $P1$ to starve :

We can make a similar situation for $P1$ as well.

Let me show you a possibility of $P1$ getting starved for CS.

Run $P1$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $V$ operation, $X$ will become 1. Now, $P1$ will enter into CS. And Now preempt it and run $P2.$ Let it execute $P(X)$ and now $X$ will become 0. Now $P2$ will enter into CS. Now preempt $P2$ and let $P1$ run.  Since the value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P1$ will be stuck in the loop. Now, When $P2's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, let $P2$  execute $P(X)$ and now $X$ will become 0. And $P2$ will enter into CS. Now at this moment, preempt $P2$ and run $P1.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P2$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P2$ after executing $P(X)$ and run $P1.$ and so on.. So, $P1$ will starve for Critical Section(CS) this way.

So, When Counting Semaphores with Busy Waiting Considered, Answer will be Option $A.$

4. Considering Counting Semaphore with Blocking Solutions :

Definition of "Counting Semaphores with Blocking Solution" :

Analyzing the given program using this definition :

In this case i.e. When Considering Counting Semaphore with Blocking Solution, It is NOT possible for any process to Starve.

The Idea/Hint is that If a process blocks itself on Semaphore $X$ then the other process will wake it up. And Hence, as soon as a process shows interest in accessing CS by executing its Entry code, It will get into CS within a bound of 1. So, Here, Bounded Waiting is Also Satisfied. So, If you analyze the given program using Blocking solution definition of Counting semaphore little bit more, you'll find that Starvation, Deadlock etc are Not possible and BW is Satisfied.

Note that Bounded Waiting is Not related to Starvation/Deadlock in any way.

So, When Counting Semaphores with Blocking Solution is Considered, Answer will be Option $D.$

P.S. :

Note 1 : By default, Semaphore means Counting Semaphore.

Note 2 : The above codes are not real, i.e., it is not an implementation of P/V. It is, instead, a definition of the effect P/V is to have.

Note 3 : Answer could be any of A, D. Both are correct. I do not know which was the official answer of GATE that year Or was it $A\,\,or\,\,D.$

Note 4 : Though both options $A$ or $D$ are correct depending on which definition of Semaphore is considered, But in my opinion, better answer should be Option $D$ (i.e. Blocking Queue definition considered) Because most authors like William Stallings or Tanenbaum consider the Blocking queue definition only for Semaphores. The busy waiting definition is called Spinlock according to most authors (even Galvin also calls the Busy waiting definition of Semaphores as Spinlocks)

Note 5 : Some students analyze the program for Starvation or Bounded waiting by arguing that "A process could run continuously and thus other process will starve.." .. Well, this is Not a correct analysis. Refer the definitions of Bounded waiting or Starvation in Galvin and you'll find that the concept that such students are missing is "" A Process is $"willing"$ to enter the CS""

Resources :

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html

https://cs.nyu.edu/courses/spring02/V22.0202-002/lecture-06.html

Operating System Concepts, written by Peter B. Galvin, Greg Gagne and Abraham Silberschatz.

Modern Operating Systems by AS Tanenbaum

Operating Systems: Internals and Design Principles  Book by William Stallings (Best Resource for Semaphores in my opinion)

by Boss (26.1k points)
edited
0
Great Explanation.

Thanks
0
Godd Explanation.

Thanks
0
What a great explanation....
0
Thank you so much sir

What a Great explanation
0
Thank you sir.

This should be the best answer.
0

Can u please explain more about what you've said in Note 5

I've studied Galvin, accoeding to Galvin if queue is FIFO order then no starvation, but in case of LIFO order the 1st process will be starved.

what is the correct way to check starvation

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

by Veteran (117k points)
0
if bounded waiting has been satisfied then , there will be no starvation...

BW is not satisfied here..
0

Here

ME is satisfied.

BW is satisfied .

Progress is violated.

0

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?

0
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?
+1
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.
0
@Bikram sir, How ME is satisfied? Both processes can be in their CS at the same time.
–1

ME satisfies here

reason:when p1 enter CS we cant preempt  in between Thus P2 will never comes into between

+1

set2018 as soon as V(x); P1 enters CS and at the same moment in P2 P(X); happens so both are in CS
explain how ME is satisfied?

0

1."If a process enter CS at least once then No starvation"   is False. ???    i think correct one will be "Execute cs completely" means no starvation am i right?

2.There may be case when though Process is in CS and pre-emted then after that it is not able to enter that might lead to Starvation" ??

3. "Starvation for Pi if and only if Pi never get chance to execute CS by trying all possible means"

This is False???

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.
by Boss (33.8k points)
+5

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 ....
+8
0
Please elaborate more on this with the help of examples.

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??
by Loyal (7k points)
0
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?
+3

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)

0
@Arjun Suresh Sir, is it necessary for P1 to enter CS first? The wait condition blocks for a semaphore value less than 0, not equal to 0..

Equal to 0 holds in bin semaphores or mutexes. Normal semaphores have a condition of <0 for wait and <=0 for signal.

Excerpt from Galvin et al; Operating Systems Concepts : ed. 7 Pg 202-203

wait(semaphore *S) {
S->value—;
if (S->value < 0) {
block();

signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);

The semaphore has a value of 0 in the beginning, either process can enter.

Now, if P1 enters and P2 tries to execute, it enters directly, because there is no way P1 can mutually exclude P2, because it increases the semaphore whenever it enters .

If P2 enters , and is interrupted , and P2 wishes to enter while the semaphore value is less than 0, it doesn't matter because signal doesn't block a process.

If P2 enters after P1, it faces no problems at all.

Even if mutex is taken into account, I can't see how P1 starves. P2 can starve because P1 might take infinite time to set mutex to 1, but for P1, it never has a lock condition because mutex signal does not have a lock condition. P1 can never starve either way, because there is no busy waiting or block in Signal, in any definition.
+1 vote

Starvation describes a situation where a thread (or a process) is unable to gain regular access to shared resources and is unable to make progress.

In the given question, $P2$ can't enter critical section (CS) unless $P1$ executes V(X) once. Thus, $P1$ stops progress of $P2$.  (Even when $P2$ wants to execute CS it can't do so). So, $P2$ can starve until $P1$ starts execution.

After $P1$ executes V(X), it enters CS and now $P2$ which was initially blocked on P(X) can also enter CS. Now, in this situation when both processes are in CS, even if $P1$ has completed it's execution it can't exit CS until $P2$ exits once. It gets blocked at P(X) until $P2$ executes V(X). Thus, here $P2$ stops progress of $P1$ and so, $P1$ can starve until $P2$ exits the CS.

$\therefore$   Ans is $(a)$.

by Junior (879 points)
0
among all answers this is most simple and straight forward and I think we can only think this at actual exam.