- A condition variable is used to delay a process until the monitor's state satisfies some
Boolean condition and/or to awaken a delayed process when the condition becomes true
- Condition variables, being a new data type, may be declared and used only within monitors, e.g.,
cond cv;
The value of cv, not directly visible to the programmer, is a queue (initially empty and by default of the
FIFO type) of delayed processes. It is also possible to declare arrays of condition
variables (likewise it was possible to declare arrays of semaphores).
Note that there is also another queue of processes waiting to enter the monitor
For synchronization of processes using monitors, condition variables
are accessed and manipulated generally by three operations:
- empty(cv)
- returning true if cv's queue is empty; otherwise it returns false
- wait(cv)
- wait at end of queue; it causes the calling process to block at the rear
of cv's queue, and to release the exclusive access to monitor
so that some other process can eventually enter the monitor to awaken
the delayed process
- signal(cv)-
awaken process at front of queue; it examines cv's delay
queue
and awakens one of the processes. If the queue is empty, signal
has no effect, otherwise the signal awakens the process at
the
front of the cv's queue. There are two standards:
- SW/SU signaling (Signal and Wait
/ Signal and Urgent Wait - due to Hoare, SU used in Tanenbaum's
OS textbook) awakens (unblocks) signalled process, and suspends process which sends signal from monitor,
putting it either at the back (for SW) or at the front (for SU) of the
queue of processes waiting for the monitor lock in the entry queue
- SC signaling (Signal and Continue
- due to Brinch Hansen, used in Andrews' textbook, Silberschatz's OS textbook,
Unix, Java, Pthreads) - process which sends a signal continues execution
in monitor, and appends signalled/awakened process to the back of the queue
of processes waiting for the monitor lock in the entry queue
- Three additional operations on condition variables allow to accommodate priorities or to broadcast awaken signals:
- wait(cv,rank)
- wait in order of increasing value of rank; processes are delayed on cv
in ascending order of rank, and hence they get awakened in this
order (instead of default FIFO, i.e., a process with the highest rank will
be awakened first); the process delayed the longest is awakened in the case of a tie.
- signal_all(cv)
- awaken all processes on cv queue; each awaken process resumes
execution in the monitor at some time in the future waiting on the entry
queue to the monitior, subject to the usual mutual exclusion constraint.
- minrank(cv)
- returns the value of rank of process at front of wait cv
queue
- Condition Variables and Signaling in UNIX
: The Unix OS kernel implements mutual exclusion by performing context switches only when user
processes block or exit the kernel and by inhibiting external interrupts at critical
points. The Unix equivalent of a condition variable is called an event
- an arbitrary integer that is typically the address of a descriptor such
a process or file descriptor. Within the kernel, a process blocks by
executing sleep(e). It is awakened when another process executes wakeup(e).
The wakeup has Signal and Continue semantics and is equivalent of signall_all
primitive, i.e., it awakens all processes blocked on process e.
Unix has no equivalent of signal primitive to awaken just one
process. Thus if more that one process could be waiting for an event,
each has to check if the condition it was waiting for, is still true, and go
back to sleep if it is not.