What is the correct implementation of UP operation in a binary semaphore

Question

these are the codes for down and up operations in a binary semaphore. The down operation's code seems to be correct, but I am having some doubt in the UP's code.
Suppose a process p1 arrives and executes down. the initial value of "value" is 1. now p1 will decrement it to 0 ,  and then proceed to execute CS. Suppose, during this time another process p2 arrives and executes down. now it will be forced to sleep as value==0. Lets assume the same for another arriving process p3.
 Now if P1 finishes its CS, it will execute UP, and find that L is not empty, so it will select a process from it and wake it up. BUT, p1 has not changed the value of "value". So even if p2 wakes up and executes down, it will be forced to sleep again.. Am I missing something, or is the above implementation incorrect ?

Answer 1

Implementation is correct

when  process p2 goes to sleep() then it is placed in the suspended List   - At this point it is executing the last statement of the down operation.

so, when it will wake up , it will resume from this point and go to critical section directly without re-executing down operation.

Comments

I think P2 immediately enters CS as soon as P2 gets scheduled again . I think P2 wont immediately enter CS after being awaken.

Answer 2

Whenever Binary Semaphores are used to synchronize the Critical Section by a Binary Semaphore Variable lets take it "S".Generally the code structure will be like below

P(s) // Entry Section

Critical Section

V(s) // Exit Section

we do down operation to achieve mutual exclusion i.e once a process its entered into the critical section and executing it, meanwhile no other process is allowed to execute the critical section and more on it will be suspended and it's PCB will be kept into the suspended list of semaphore variable i.e. S.

After execution of critical section the process will perform up operation on S inside exit section and binary semaphore does not always make S value to 1. It makes the S.value = 1 once the S.list is empty and it will simply wake up a process from the S.list and allocate the critical section to it when S.list is not empty.

Now your confusion is, "Why UP() operation is not performing S.value = 1 when S.list is not empty ?"

Lets do it first, once we will make S.value  =1 when S.list is not empty. There will be chance of process P2 may enter into starvation.Because once the S.value is 1 any process can come and perform down operation and execute critical section. This the process P2 may not get chance to execute the critical section.

Comments

As given in question P₂ & P₃ both are in the suspended list then which one will wake up first.

Is there a fixed order or anyone in the suspended list can wake up ?

---

Actually Semaphore maintain a waiting queue for process. So they will be wake up in the same order they arrived.

---

Suspended list is nothing but a queue.

Ref : https://en.wikipedia.org/wiki/Semaphore_(programming)#Semantics_and_implementation

---

Can u try this - https://gateoverflow.in/364/how-to-check-for-starvation#c25887

Here Arjun Sir said that it is not necessary for it to be a Queue.

Answer 3

Semaphore implementation contains Queue. While performing the DOWN() operation if it is unsuccessful then process goes and sleep into this queue. DOWN() fail because of the some other process is in CS. While performing the UP() operation it will check the list is empty or not. If list is empty then it simply assign the vale 1 to semaphore. If list is not empty then it will wake the process from the list and allow that process to enter into CS. So UP() just wake the process from the list and allowed to enter that process into CS. Hope this is clear.