Copyright Dr. Marek Suchenek 1999... 2025


This document contains an operating system level implementation (a pseudocode)
of conditional wait and signal on a non-negative semaphore.

Additionally, it contains implementation of check on a non-negative semaphore  

A system call  cond_wait(S, C) will suspend the issuing process if the value of
S is 0 or condition C evaluates to FALSE; otherwise it will decrement the value
of S. 

A system call to cond_signal(S) will increment the value of S and release at
most S.value waiting processes whose conditions evaluate to TRUE, decrementing
the value of S after each released process.

A system call to cond_check(S) will work like cond_signal(S) except that it 
will not increment the value of S.


TYPE semaphore = RECORD
                     value: INTEGER; {non-negative values only}
                     list: ^PCB {waiting queue}
                 END;

PROCEDURE cond_wait (S: semaphore; C: expression);

{A system call. No context switch to a user process will occur.}

BEGIN
  IF S.value > 0 AND true(C) THEN S.value := S.value - 1
    ELSE
      BEGIN
        delete the PCB of the process P that issued this cond_wait
          from the ready queue;
        insert the PCB of P to the end of S.list queue;
        store the condition C in the PCB of P
      END;
END;

{wait(S) = cond_wait(S, TRUE)}


PROCEDURE cond_signal (S: semaphore); {C is stored already in a PCB}

{A system call. No context switch to a user process will occur.}

VAR found: Boolean;

BEGIN
  find the first process P in the queue S.list for which the condition stored
    in the PCB of P evaluates to true;
  IF found THEN
             BEGIN
               delete the PCB of P from the queue S.list;
               insert the PCB of P into the ready queue;
               {incrementation and decrementation of S.value cancel each other}
             END
           ELSE S.value := S.value + 1; {since no process was released
                                         from wait in this case}
  WHILE found and S.value > 0 {more processes are allowed to be released
                               from wait} DO
    BEGIN
      find the next process P in the queue S.list for which the condition
        stored in the PCB of P evaluates to true;
      IF found THEN
                 BEGIN
                   delete the PCB of P from the queue S.list;
                   insert the PCB of P into the ready queue;
                   S.value := S.value - 1; {since another process was
                                            released from wait}
                 END;
    END;
END;

PROCEDURE cond_check (S: semaphore); {C is stored already in a PCB}

{A system call. No context switch to a user process will occur.}

VAR found: Boolean;

BEGIN
	IF S.value > 0 THEN
	BEGIN
  		find the first process P in the queue S.list for which the condition stored
    			in the PCB of P evaluates to true;
  		WHILE found and S.value > 0 {processes will be released
                               from wait} DO
    			BEGIN
            			delete the PCB of P from the queue S.list;
                   		insert the PCB of P into the ready queue;
                   		S.value := S.value - 1; {since another process was
                                            released from wait}
              			find the next process P in the queue S.list for which the condition
        				stored in the PCB of P evaluates to true;
         		END;
	END;

END;




{wait(C) = initialize S.value to +infty;
           ...
           cond_wait(S, C); // S.value doesn't change since +infty - 1 = +infty
           ...

When a variable occurring in C is modified, a call to cond_signal(S) is
issued. For the same reason as above, S.value doesn't change.}