Update of /usr/local/src/cvs/bordeaux-mp In directory loaclhost.telent.net:/tmp/cvs-serv21191 Modified Files: Specification Log Message: rewrite condition variables section Index: Specification =================================================================== RCS file: /usr/local/src/cvs/bordeaux-mp/Specification,v retrieving revision 1.5 retrieving revision 1.6 diff -u -d -r1.5 -r1.6 --- Specification 12 Jul 2004 18:45:15 -0000 1.5 +++ Specification 12 Jul 2004 23:28:43 -0000 1.6 @@ -194,20 +194,36 @@ * Resource contention: condition variables -A condition variable is a queue of processes which are waiting for -some event. When the event occurs, the queue will be notified, -causing one or more of the stopped processes to be resumed. +A condition variable provides a mechanism for processes to put +themselves to sleep while waiting for the state of something to +change, then to be subsequently woken by another process which +has changed the state. -[ It's not a queue really ] +A condition variable must be used in conjunction with a lock to +protect access to the state of the object of interest. The procedure +is as follows: -Condition variables are used to signal events when the state of some -shared resource changes: for example, consider a buffer with readers -and a writer, where the readers can only run when there is data in the -buffer, and the writer can only refill the buffer when it is empty. -By providing an atomic "release lock and sleep" operation, a condition -variable guards against the "lost notification" problem, which is -where the writer adds data to the buffer in between the time that a -reader tests it (finding it empty) and goes to sleep. +Suppose two processs A and B, and some kind of notional event channel +C. A is consuming events in C, and B is producing them. CV is a +condition-variable + +1) A acquires the lock that safeguards access to C +2) A processes and removes all events that are present +3) When the channel is empty, A calls CONDITION-WAIT, which atomically + releases the lock and puts A to sleep on CV +4) Loop back to step 1, for as long as processing should continue + +When B generates an event E, it +1) acquires the lock guarding C +2) adds E to the channel +3) releases the lock +4) calls CONDITION-NOTIFY on CV to wake any sleeping process + +The implementation must guarantee that CONDITION-WAIT in process A +atomically release the lock and sleeps. If this does not happen, and +process B can add an event an call CONDITION-NOTIFY between the lock +release and the sleep, the notify call will not see A. This is the +"lost wakeup" problem. make-condition-variable () [function] @@ -220,8 +236,8 @@ CONDITION-VARIABLE. The process will resume when another process has notified it using CONDITION-NOTIFY; it may also resume if interrupted by some external event or in other implementation-dependent -circumstances: the caller must always test on waking that it can -proceed, before continuing normal processing. +circumstances: the caller must always test on waking that there is +processing to be done, instead of assuming that it can go ahead. However and for whatever reason the process is resumed, the system always reacquires LOCK before returning to the caller. It is an error @@ -232,16 +248,16 @@ condition-notify (condition-variable) [function] -Notify one or more of the processes waiting for CONDITION-VARIABLE. -The caller needs to acquire the lock associated with the condition -variable before calling this. - -[ wake-one vs wake-all: when does >1 process get woken ] - - +Notify at least one of the processes waiting for CONDITION-VARIABLE. +It is implementation-dependent whether one or more than one (and +possibly all) processes are woken, but if the implementation is +capable of waking only a single process (not all are) this is probably +preferable for efficiency reasons. The order of wakeup is unspecified +and does not necessarily relate to the order that the processes went +to sleep in. -In an implementation that does not support multiple processes, this -function has no effect. +CONDITION-NOTIFY has no useful return value. In an implementation +that does not support multiple processes, it has no effect. * Miscellaneous @@ -252,7 +268,6 @@ processes automatically. On systems that do not support multi-processing, this does nothing. - * Introspection/debugging The following functions may be provided for debugging purposes, but