summaryrefslogtreecommitdiff
path: root/fibers
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2017-02-11 11:32:44 +0100
committerAndy Wingo <wingo@pobox.com>2017-02-11 12:17:32 +0100
commit1e2bd7c6d67947a277c92eed9ba26a4d75f06cb3 (patch)
tree4d57f6681d90fd7068f2cda1d0aae106c43fcff8 /fibers
parentFix channel CAS logic (diff)
downloadguile-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.scm104
-rw-r--r--fibers/timers.scm6
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)))