2
$\begingroup$

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      repeat forever
V (X) ;             P(X) ;
Compute ;          Compute ;                  
P(X) ;              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.

My attempt:

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.


Another method: Since word possible is used. So,

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.

Now, I agree second method since possible. we need to find that situation so can be possible.

Can you explain it in a formal way?


I'd posted on SO $4$ days ago, but that is put on hold today, So, I posted on here, since CS.SE is better place for this problem.

$\endgroup$
  • $\begingroup$ Are the semaphores regulated by a FIFO policy? I think this is important here. Concretely, if two $P$s are tried, will the first one be woken up by the next $V$? $\endgroup$ – chi Jun 29 '16 at 8:56
  • $\begingroup$ @chi, The problem is badly defined. This was from GATE exam. $\endgroup$ – 1 0 Jun 29 '16 at 10:52
  • 1
    $\begingroup$ If a FIFO policy is not assumed, your second method looks correct. P1 can get stuck on its P, while P2 loops forever. The dual is also possible: P2 gets stuck on its P while P1 loops forever. I think just showing an interleaved execution where starvation happens is enough. $\endgroup$ – chi Jun 29 '16 at 11:08
  • $\begingroup$ Process P2 can't enter into critical section until P1 has entered at least once,so statement II is correct "It is possible for process P1 to starve." $\endgroup$ – Maharaj Jun 29 '16 at 11:26
  • $\begingroup$ Both process P1 and P2 may starve. $\endgroup$ – Mayank Deora Jun 29 '16 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.