diff options
| author | Andy Wingo <wingo@pobox.com> | 2017-02-11 11:32:44 +0100 |
|---|---|---|
| committer | Andy Wingo <wingo@pobox.com> | 2017-02-11 12:17:32 +0100 |
| commit | 1e2bd7c6d67947a277c92eed9ba26a4d75f06cb3 (patch) | |
| tree | 4d57f6681d90fd7068f2cda1d0aae106c43fcff8 /fibers | |
| parent | Fix channel CAS logic (diff) | |
| download | guile-fibers-1e2bd7c6d67947a277c92eed9ba26a4d75f06cb3.tar.gz | |
Add condition variable implementation
* fibers/conditions.scm:
* tests/conditions.scm: New files.
* Makefile.am: Add new files.
* fibers.texi (Conditions): New section.
* fibers/timers.scm (sleep-operation): Rename from wait-operation.
* tests/foreign.scm: Adapt to sleep-operation change.
Diffstat (limited to 'fibers')
| -rw-r--r-- | fibers/conditions.scm | 104 | ||||
| -rw-r--r-- | fibers/timers.scm | 6 |
2 files changed, 107 insertions, 3 deletions
diff --git a/fibers/conditions.scm b/fibers/conditions.scm new file mode 100644 index 0000000..5501135 --- /dev/null +++ b/fibers/conditions.scm @@ -0,0 +1,104 @@ +;; Conditions + +;;;; Copyright (C) 2017 Andy Wingo <wingo@pobox.com> +;;;; +;;;; This library is free software; you can redistribute it and/or +;;;; modify it under the terms of the GNU Lesser General Public +;;;; License as published by the Free Software Foundation; either +;;;; version 3 of the License, or (at your option) any later version. +;;;; +;;;; This library is distributed in the hope that it will be useful, +;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +;;;; Lesser General Public License for more details. +;;;; +;;;; You should have received a copy of the GNU Lesser General Public +;;;; License along with this library; if not, write to the Free Software +;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +;;; Condition variable (cvar) implementation following the 2009 ICFP +;;; paper "Parallel Concurrent ML" by John Reppy, Claudio V. Russo, +;;; and Yingqui Xiao. See channels.scm for additional commentary. +;;; +;;; Besides the general ways in which this implementation differs from +;;; the paper, this channel implementation avoids locks entirely. +;;; Still, we should disable interrupts while any operation is in a +;;; "claimed" state to avoid excess latency due to pre-emption. It +;;; would be great if we could verify our protocol though; the +;;; parallel channel operations are still gnarly. + +(define-module (fibers conditions) + #:use-module (srfi srfi-9) + #:use-module (ice-9 atomic) + #:use-module (ice-9 match) + #:use-module (fibers stack) + #:use-module (fibers operations) + #:export (make-condition + condition? + signal-condition! + wait-operation + wait)) + +(define-record-type <condition> + (%make-condition signalled? waiters) + condition? + ;; atomic box of bool + (signalled? condition-signalled?) + ;; stack of flag+resume pairs + (waiters channel-waiters)) + +(define (make-condition) + "Make a fresh condition variable." + (%make-condition (make-atomic-box #f) (make-empty-stack))) + +(define (resume-waiters! waiters) + (define (resume-one flag resume) + (match (atomic-box-compare-and-swap! flag 'W 'S) + ('W (resume values)) + ('C (resume-one flag resume)) + ('S #f))) + ;; Non-tail-recursion to resume waiters in the order they were added + ;; to the waiters stack. + (let lp ((waiters (stack-pop-all! waiters))) + (match waiters + (() #f) + (((flag . resume) . waiters) + (lp waiters) + (resume-one flag resume))))) + +(define (signal-condition! cvar) + "Mark @var{cvar} as having been signalled. Resume any fiber or +thread waiting for @var{cvar}. If @var{cvar} is already signalled, +calling @code{signal-condition!} does nothing and returns @code{#f}; +returns @code{#t} otherwise." + (match cvar + (($ <condition> signalled? waiters) + (match (atomic-box-compare-and-swap! signalled? #f #t) + (#f ;; We signalled the cvar. + (resume-waiters! waiters) + #t) + (#t ;; Cvar already signalled. + #f))))) + +(define (wait-operation cvar) + "Make an operation that will complete when @var{cvar} is signalled." + (match cvar + (($ <condition> signalled? waiters) + (define (try-fn) (and (atomic-box-ref signalled?) values)) + (define (block-fn flag sched resume) + ;; We have suspended the current fiber or thread; arrange for + ;; signal-condition! to call resume-get by adding the flag and + ;; resume callback to the cvar's waiters stack. + (stack-push! waiters (cons flag resume)) + ;; It could be that the cvar was actually signalled in between + ;; the calls to try-fn and block-fn. In that case it could be + ;; that resume-waiters! was called before our push above. In + ;; that case, call resume-waiters! to resolve the race. + (when (atomic-box-ref signalled?) + (resume-waiters! waiters)) + (values)) + (make-base-operation #f try-fn block-fn)))) + +(define (wait cvar) + "Wait until @var{cvar} has been signalled." + (perform-operation (wait-operation cvar))) diff --git a/fibers/timers.scm b/fibers/timers.scm index 1ccd088..505939f 100644 --- a/fibers/timers.scm +++ b/fibers/timers.scm @@ -23,7 +23,7 @@ #:use-module (ice-9 atomic) #:use-module (ice-9 match) #:use-module (ice-9 threads) - #:export (wait-operation + #:export (sleep-operation timer-operation) #:replace (sleep)) @@ -63,7 +63,7 @@ units. The operation will succeed with no values." (perform-operation (timer-operation expiry)) (timer))))))) -(define (wait-operation seconds) +(define (sleep-operation seconds) "Make an operation that will succeed with no values when @var{seconds} have elapsed." (timer-operation @@ -73,4 +73,4 @@ units. The operation will succeed with no values." (define (sleep seconds) "Block the calling fiber until @var{seconds} have elapsed." - (perform-operation (wait-operation seconds))) + (perform-operation (sleep-operation seconds))) |
