Welcome to the threads-standard-discuss mailing list. It was created as a result of discussion at the Libre Software Meeting in Bordeaux in July 2004, as a venue for creating a portable de facto standard for use by multithreaded Common Lisp code.
I have prepared an initial draft specification entitled BORDEAUX-MP, based on CLIM-SYS (and the needs of McCLIM, which are in fact not quite the same), which is available at
http://cvs.telent.net/cgi-bin/viewcvs.cgi/bordeaux-mp/Specification?view=mar...
Eventually there will also be a sample implementation to go with it, using code borrowed from McCLIM.
I invite comments/feedback/flames from all interested parties. Points which have been raised so far include
1) behaviour of specials in a new thread: "did you just make it undefined so that the SBCL implementation would be simpler?"
I propose to add a list of specials which automatically get thread-local bindings in each new process: something like ACL's *cl-default-special-bindings*
2) "condition variable" is an unfortunate name as there is already a similarly named but entirely different CONDITION object in CL
I don't have any good ideas about this one.
3) A process-state reader might be nice
I personally don't see the point, much, unless the semantics of its allowable values are also defined.
(Personal position: I'm far more concerned about the ability to write real threaded applications than I am about writing a replacement for top(1) in CL)
4) Some form of control over process priority
This might be useful if you have for example a foreground display process that you wish to remain responsive, and a background computation task that only needs to run when nothing else is happening.
On the other hand, it might be a fast track to priority inversion and some form of starvation. Discuss.
A handy summary of some of the various terms involved is at URL:http://www.cs.columbia.edu/~hgs/os/sync.html, for anyone wanting definitions
-dan
Daniel Barlow writes:
* Process Creation
make-process function &key name [Function]
Creates a process named NAME. The new process will evaluate the function FUNCTION. On systems that do not support multi-processing, make-process will signal an error.
Three problems. First, the function is not evaluated but called (I suppose). Second, we should specify how the function is called. Third, we should say what the return value is. For instance:
* Process Creation
make-process function &key name [Function]
Creates a process named NAME. The new process will call the function FUNCTION with no arguments. The default value for name is NIL. The value returned is the newly created process. On systems that do not support multi-processing, make-process will signal an error.
*default-special-bindings*
This variable holds an alist associating special variable symbols with forms to evaluate for binding values. Special variables named in this list will be locally bound in the new process.
This may be rebound around calls to MAKE-PROCESS to add/alter default
Preferable: This variable may...
bindings. The effect of mutating this list is undefined, but earlier forms take precedence over later forms for the same symbol, so defaults may be overridden by consing to the head of the list.
[ Forms are evaluated in the new thread or in the calling thread? ]
I suggest in the old process so that the new process can have its behavior modified by the creating process.
[ Standard contents of this list: print/reader control, etc. Can borrow the franz equivalent? ]
Initial values of other special variables are implementation-defined. For example, they may be the same as in the process that called make-process, or set from the global values of the variables.
Well, it would be useful to standardize what happens to variables that are not rebound by the process that called make-process. For instance:
Initial values of other special variables that have not been bound by the process calling make-process preserve their values. Initial values of other special variables that have been bound by the process calling make-process are implementation-defined. For example ...
The new thread may rebind special variables: the new bindings are local to that thread. If it assigns to special variables that have not been bound (either at process creation time or subsequently), the effect is implementation-defined.
I would think relying on the global binding to be shared would be an important programming technique so that you can communicate between processes. No?
process-name process [Function]
Returns the name of the process, as supplied to MAKE-PROCESS
"or NIL if no name was supplied to MAKE-PROCESS." ?
- Atomic operations
atomic-incf reference [Function] atomic-decf reference [Function]
Were these meant to be "[Macro]"?
What is a reference? The same thing as a place? Less general?
Increments (or decrements) the fixnum value referred to by reference as a single, atomic operation. If the operation would take the value out of fixnum range, behaviour is undefined.
We should specify what value is returned, for instance:
The value of the call is the fixnum after incrementation.
- Resource contention: locks and recursive locks
make-lock &optional name [Function]
Creates a lock (a mutex) whose name is NAME. If the system does not support multiple processes this will still return some object, but it may not be used for very much.
[ in CLIM-SYS this is a freshly consed list (NIL). I don't know if there's some good reason it should be said structure or that it be freshly consed - EQ comparison of locks? ]
I do not think there is a good reason to specify what is returned.
acquire-lock lock &optional (wait-p t) [Function]
Acquire the lock LOCK for the calling process. If the lock is not available, and if WAIT-P is non-NIL, wait until it is.
Specify return values and what happens when WAIT-P is NIL:
Acquire the lock LOCK for the calling process. Return true if the lock was successfully acquired, and NIL otherwise. If the lock is not available, and if WAIT-P is non-NIL, wait until it is. Thus if WAIT-P is non-NIL, ACQUIRE-LOCK will always return true (if it returns at all). If WAIT-P is NIL and the lock is not available, ACQUIRE-LOCK immediately returns NIL.
This specification does not define what happens if a process attempts to acquire a lock that it already holds. For applications that require locks to be safe when acquired recursively, see instead MAKE-RECURSIVE-LOCK and friends.
release-lock lock [Function]
Release LOCK. It is an error to call this unless the lock has previously been acquired (and not released) by the same process. If other processes are waiting for the lock, the ACQUIRE-LOCK call in one of them will now be able to continue.
Specify return value?
with-lock-held (place) &body body [Macro]
Evaluates BODY with the lock named by PLACE, which is a reference to a lock created by MAKE-LOCK.
Evaluates BODY with the lock named by PLACE, the value of which is a lock created by MAKE-LOCK. Before the forms in BODY are evaluated, the lock is acquired using ACQUIRE-LOCK. After the forms in BODY have been evaluated, the lock is released using RELEASE-LOCK.
The lock will still be released even if a non-local control transfer (e.g. by THROW or SIGNAL) is signalled, but
I suspect one does not say that a throw is "signalled" (which is my book is spelled "signaled" so as to avoid an emphasis on the `a'). Perhaps :
The lock will still be released even if a non-local control transfer (e.g. by THROW or SIGNAL) terminates the execution of BODY, but
note that if the debugger is entered, the lock may only be released /after/ execution has been restarted.
"may" is an unfortunate word in English. It could mean that the programmer does not have the right to release it, or that it might be released.
If the process is unable to acquire the lock, BODY will not be evaluated.
This phrase seems superfluous.
Perhaps we should allow for a value of WAIT-P to be passed to ACQUIRE-LOCK? If so, specify what happens when WAIT-P is nil and the lock could not be acquired.
make-recursive-lock &optional name [Function]
Creates a recursive lock whose name is NAME. A recursive lock differs from an ordinary lock in that a process that already holds the recursive lock can acquire it again without blocking. The process must then release the lock twice before it becomes available for another process.
Specify return value.
acquire-recursive-lock lock [Function]
Perhaps use different return values depending on whether the lock is already held or not.
Why do we need a different function here?
As for ACQUIRE-LOCK, but for recursive locks.
release-recursive-lock lock [Function]
Idem.
Release the recursive LOCK. The lock will only become free after as many Release operations as there have been Acquire operations. See RELEASE-LOCK for other information.
with-recursive-lock-held (place &key timeout) &body body [Macro]
Idem.
Evaluates BODY with the recursive lock named by PLACE, which is a reference to a recursive lock created by MAKE-RECURSIVE-LOCK. See WITH-LOCK-HELD etc etc
I am having a hard time understanding condition variables.
- 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.
What determines whether one or more than one process gets resumed?
Since it is a queue (FIFO), is the first process in always resumed?
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.
OK, I follow this far.
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.
I do not see how having a "release lock and sleep" operation fixes the "lost notification" problem. Who would use the operation? The reader or the writer or both?
make-condition-variable () [function]
Returns a new condition-variable object for use with CONDITION-WAIT and CONDITION-NOTIFY.
condition-wait (condition-variable lock) [function]
Atomically release LOCK and enqueue the calling process waiting for CONDITION-VARIABLE. The process will resume when another thread has
You probably mean `process' as opposed to `thread'.
notified it using CONDITION-NOTIFY, or we are interrupted,
How would we get interrupted?
or in other implementation-dependent circumstances: the caller must always test on waking that it can proceed, before continuing normal processing.
How does it test that it can proceed? Doesn't that test reintroduce the problem that condition-variables were designed to avoid?
However and for whatever reason the process is resumed, the system always reacquires LOCK before returning to the caller. It is an error to call this unless from the thread that holds LOCK.
In an implementation that does not support multiple processes, this function signals an error.
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.
There has been no mention of "lock associated with condition variable" before. How is this association determined?
In an implementation that does not support multiple processes, this function has no effect.
Robert Strandh writes:
I am having a hard time understanding condition variables.
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.
I do not see how having a "release lock and sleep" operation fixes the "lost notification" problem. Who would use the operation? The reader or the writer or both?
The common use case is like this:
(defun reader () (with-lock-held (*lock*) (loop (condition-wait *condvar* *lock*) (when <something there> <consume>))))
(defun writer () (loop (with-lock-held (*lock*) <add something to be consumed> (condition-notify *condvar*))))
The notification cannot be lost since entering CONDITION-WAIT is while the lock is held at which point the writer cannot have it. Only after things are set up within the deep magic of CONDITION-WAIT to actually wait for the condition to be notified the lock is released.
Or put the other way round: The reader only releases the lock while being blocked within CONDITION-WAIT. The writer can only notify while holding the lock.
=> CONDITION-NOTIFY can only be called when the reader is blocked in CONDITION-WAIT => no notifications get lost.
qed :)
Hello,
Gilbert Baumann writes:
The common use case is like this:
(defun reader () (with-lock-held (*lock*) (loop (condition-wait *condvar* *lock*) (when <something there> <consume>))))
Hmmm... This is not what the new version of the API seems to be saying, but instead
(defun reader () (acquire-lock *lock*) (loop while <something there> do <consume>) (condition-wait *condvar* *lock*))
In fact, I think in your version, release-lock will be called when it is already released (provided that with-lock-held calls release lock.
Also, you version seems to release the lock (through calling condition-wait) before consumption starts.
Perhaps we need a macro that captures the preceding idiom, like:
(defun reader () (with-condition-variable-and-lock (*condvar* *lock*) (loop while <something there> do <consume>)))
(defun writer () (loop (with-lock-held (*lock*) <add something to be consumed> (condition-notify *condvar*))))
This also does not correspond. I interpret the new version of the API like this:
(defun writer () (loop (with-lock-held (*lock*) <add something>) (condition-notify *condvar*)))
The notification cannot be lost since entering CONDITION-WAIT is while the lock is held at which point the writer cannot have it. Only after things are set up within the deep magic of CONDITION-WAIT to actually wait for the condition to be notified the lock is released.
OK, I think I got it.
Or put the other way round: The reader only releases the lock while being blocked within CONDITION-WAIT. The writer can only notify while holding the lock.
=> CONDITION-NOTIFY can only be called when the reader is blocked in CONDITION-WAIT => no notifications get lost.
qed :)
Thanks for the explanation.
I found this during my postponed-folder cleanup. It's ages past this was last talked about... but what the more general point remains valid:
--snip-- On Fri, 9 Jul 2004, Daniel Barlow wrote:
atomic-incf reference [Function] atomic-decf reference [Function]
Increments (or decrements) the fixnum value referred to by reference as a single, atomic operation. If the operation would take the value out of fixnum range, behaviour is undefined.
I'd propose "unspecified behaviour" instead, the essential difference being that heap corruption, crashes, etc aren't allowed. Implementations would still be allowed to wrap, zero the reference, signal an error, etc. --snap--
The "general point" being that "unspecified" and "undefined" have a nice distinction, and specifying something as unspecified behaviour instead of defining as undefined (sorry, couldn't resist) gives a useful promise of "not destrying the world" to the user.
Whether that promise is something that can be given in this case, I do not know.
Cheers,
-- Nikodemus "Not as clumsy or random as a C++ or Java. An elegant weapon for a more civilized time."
threads-standard-discuss@common-lisp.net
-
Daniel Barlow -
Gilbert Baumann -
Nikodemus Siivola -
Robert Strandh