Semaphore doubt

Question

wait(S);

Critical section

wait(S);

S is a binary semaphore initialised to 1. Suppose there are n processes competing for the CS. Only one can enter into it. Is this the situation of deadlock or starvation?

I think it's deadlock because other processes are made to wait infinitely. But someone told me that since at least one process is getting executed so it's not deadlock as in case of deadlock none of the processes can proceed.

Please clarify.

Comments

Starvation is long waiting.Deadlock is infinite waiting

But in the above question, even after coming out of the CS the process is performing wait(S)

So only one process could ever enter the CS, so I'm pretty sure it's deadlock

If after CS the action was signal(S), then the sys is not free from starvation(i think)

refer to this : https://gateoverflow.in/38610/does-deadlock-imply-no-bounded-waiting-progress-both-these

---

Okay thank you :)

And if there was signal(S) at the end then there might be starvation i think, because some process can keep on entering the CS as much no. Of times as it wants depriving some other process to enter. Is there bounded waiting in case of semaphore? ( this doubt just struck me while writing this comment :p ) .

---

Yes, starvation will be present

Bounded waiting means there is a bound to the time a process will wait, so existence of bounded waiting implies no starvation. (i think of them as opposites)

(Side note : Semaphore is also implementation dependant, if a queue is maintained for all unsuccessful wait(S) operations then there is no starvation)

---

so existence of bounded waiting implies no starvation

This is not true. Rather,

Bounded waiting + deadlock freedom -> starvation freedom

---

Okay, but also Deadlock alone implies Starvation

---

Yes, deadlock->starvation

---

Can't we say like this $\text{! Starvation} \leftarrow\rightarrow \text{Bounded Waiting}$

---

Shubhanshu NO it is one way. Deadlock -> Starvation i.e. starvation freedom -> no deadlock

---

Bounded waiting:- it is the factor of the number of processes.

Starvation:- It is the factor of time.

I think that's why we can't say that BW $\leftarrow\rightarrow$ Starvation.

---

@Anu007 and @Subhanshu

But can you give example to show that

1. There is no starvation but still there is bounded waiting

2. There is bounded waiting but still process may suffer from starvation.

I couldn't think of such example so I thought what Shubhanshu said was correct.