summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2016-12-12 23:20:35 +0100
committerAndy Wingo <wingo@pobox.com>2016-12-12 23:22:13 +0100
commit5bf19089e17b50600b515baf93165817184a96e2 (patch)
tree7563f97409a93dc3cfb3b4b7b44ae405373fb3b1
parentMinor documentation tweak (diff)
downloadguile-fibers-5bf19089e17b50600b515baf93165817184a96e2.tar.gz
Add support for preemption
* Makefile.am: Add new test. * TODO.md: Remove stale TODO entries. * fibers.scm (run-fibers): Add #:hz parameter. * fibers.texi (Design): Mention that we support preemption. (Using Fibers): Update for preemption. * fibers/internal.scm (<scheduler>): Add hz field. (make-scheduler): Add #:hz initarg. (maybe-preemptive): New helper. (run-scheduler): Use maybe-preemptive. * tests/preemption.scm: New test.
-rw-r--r--Makefile.am3
-rw-r--r--TODO.md16
-rw-r--r--fibers.scm2
-rw-r--r--fibers.texi32
-rw-r--r--fibers/internal.scm67
-rw-r--r--tests/preemption.scm81
6 files changed, 154 insertions, 47 deletions
diff --git a/Makefile.am b/Makefile.am
index 5b45034..d2db6b5 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -48,7 +48,8 @@ epoll_la_LDFLAGS = -export-dynamic -module
TESTS = \
tests/basic.scm \
tests/channels.scm \
- tests/parameters.scm
+ tests/parameters.scm \
+ tests/preemption.scm
TESTS_ENVIRONMENT=top_srcdir="$(abs_top_srcdir)" ./env $(GUILE) -s
EXTRA_DIST += \
diff --git a/TODO.md b/TODO.md
index 1e4153c..113671b 100644
--- a/TODO.md
+++ b/TODO.md
@@ -71,11 +71,6 @@ channels would be sufficient. At the same time, something like what
Concurrent ML does by making events first-class solves this problem
nicely.
-## Documentation
-
-The implementation is useful enough that its public interfaces should
-be documented :)
-
## What if a fiber throws an exception?
In batch mode, probably the exception should be caught by the
@@ -109,17 +104,6 @@ We need to provide API for things like:
Also, how would we do it?
-## `select()` or similar
-
-We should certainly provide a `select-message` interface that returns
-the first readable message, along with the channel that it came from.
-For asynchronous sends that will never block, just spawning a fiber to
-do the send is suffient. This leaves out the case of wanting to wait
-on the first readable or writable channel, and points to the
-conclusion that we really need to look at Concurrent ML to see if we
-can integrate first-class events into fibers. See also
-https://www.cs.utah.edu/plt/publications/pldi04-ff.pdf.
-
## Readline? REPL over channels
Currently the REPL runs in a blocking mode that basically takes over
diff --git a/fibers.scm b/fibers.scm
index c40dbe0..21a56a6 100644
--- a/fibers.scm
+++ b/fibers.scm
@@ -39,7 +39,7 @@
(resume-on-writable-fd (port-read-wait-fd port) fiber))))
(define* (run-fibers #:optional (init #f)
- #:key (scheduler (make-scheduler))
+ #:key (hz 0) (scheduler (make-scheduler #:hz hz))
(install-suspendable-ports? #t)
(keep-scheduler? (eq? scheduler (current-scheduler))))
(when install-suspendable-ports? (install-suspendable-ports!))
diff --git a/fibers.texi b/fibers.texi
index 5eb168c..8c23577 100644
--- a/fibers.texi
+++ b/fibers.texi
@@ -348,13 +348,14 @@ backpressure support than Erlang, blocking when no receiver is
available to handle a message instead of letting the sender keep
sending many messages.
-On the other hand, currently fibers are not preemptively scheduled. A
-fiber will only suspend when it would block on channel receive or
-send, or on read or write on a port. This would be an OK point in the
-design space if only one kernel thread could be running fibers at
-once, as in Node.js. However given that this is not the case, Fibers
-does not have many of the concurrency invariants that such systems
-enjoy, so perhaps we should support preemption in the future.
+On the other hand, currently fibers default to not being preemptively
+scheduled. A fiber will only suspend when it would block on channel
+receive or send, or on read or write on a port. This would be an OK
+point in the design space if only one kernel thread could be running
+fibers at once, as in Node.js. However given that this is not the
+case, Fibers does not have many of the concurrency invariants that
+such systems enjoy, so perhaps we should default to enabling
+preemption.
To avoid starvation, a fiber can only run once within a ``turn''.
Each turn starts with a poll on file descriptors of interest and marks
@@ -402,7 +403,7 @@ import the @code{(fibers)} module:
To create a new fibers scheduler and run it in the current Guile
thread, use @code{run-fibers}.
-@defun run-fibers [init-thunk=@code{#f}] [#:install-suspendable-ports?=@code{#t}] [#:scheduler=@code{(make-scheduler)}] [#:keep-scheduler?]
+@defun run-fibers [init-thunk=@code{#f}] [#:install-suspendable-ports?=@code{#t}] [#:scheduler=@code{(make-scheduler)}] [#:keep-scheduler?] [#:hz=0]
Run @var{init-thunk} within a fiber in a fresh scheduler, blocking
until the scheduler has no more runnable fibers. Return the value(s)
returned by the call to @var{init-thunk}.
@@ -428,7 +429,12 @@ or writes to prevent other fibers from running, pass @code{#f} as the
By default, @code{run-fibers} will create a fresh scheduler. If you
happen to have a pre-existing scheduler (because you used the
internals interface to create one), you can pass it to
-@code{run-fibers} using the @code{#:scheduler} keyword argument.
+@code{run-fibers} using the @code{#:scheduler} keyword argument. If
+@code{run-fibers} creates a new scheduler, it will pass @var{hz} to
+the @code{make-scheduler} invocation. By default @var{hz} is 0,
+indicating that the scheduler should not be pre-emptive. Pass a
+higher value to cause computationally expensive tasks to be preempted
+if possible.
The scheduler will be destroyed when @code{run-fibers} finishes,
unless the scheduler was already ``current'' (@pxref{Internals}). If
@@ -610,8 +616,12 @@ point, but for now this section is a stub.
(use-modules (fibers internal))
@end example
-@defun make-scheduler
-Make a new scheduler in which to run fibers.
+@defun make-scheduler [#:hz hz=0]
+Make a new scheduler in which to run fibers. @var{hz} indicates the
+frequency at which fibers should be preempted. By default @var{hz} is
+0, indicating that the scheduler should not be preempt fibers that hog
+the CPU. Note that preemption will only occur if the fiber can
+actually be suspended; @xref{Barriers}, for more information.
@end defun
@defspec with-scheduler scheduler body ...
diff --git a/fibers/internal.scm b/fibers/internal.scm
index bff342a..a80e478 100644
--- a/fibers/internal.scm
+++ b/fibers/internal.scm
@@ -78,7 +78,7 @@ name is known."
(define-record-type <scheduler>
(%make-scheduler name epfd active-fd-count prompt-tag runqueue
- sources timers kernel-thread)
+ sources timers kernel-thread hz)
scheduler?
(name scheduler-name set-scheduler-name!)
(epfd scheduler-epfd)
@@ -91,7 +91,8 @@ name is known."
;; PSQ of thunk -> expiry
(timers scheduler-timers set-scheduler-timers!)
;; atomic parameter of thread
- (kernel-thread scheduler-kernel-thread))
+ (kernel-thread scheduler-kernel-thread)
+ (hz scheduler-hz))
(define-record-type <fiber>
(make-fiber scheduler continuation)
@@ -114,7 +115,7 @@ name is known."
(unless (eq? prev init)
(error "owned by other thread" prev))))))))
-(define (make-scheduler)
+(define* (make-scheduler #:key (hz 0))
"Make a new scheduler in which to run fibers."
(let ((epfd (epoll-create))
(active-fd-count 0)
@@ -126,7 +127,8 @@ name is known."
<))
(kernel-thread (make-atomic-parameter #f)))
(let ((sched (%make-scheduler #f epfd active-fd-count prompt-tag
- runqueue sources timers kernel-thread)))
+ runqueue sources timers kernel-thread
+ hz)))
(set-scheduler-name! sched (nameset-add! schedulers-nameset sched))
sched)))
@@ -266,24 +268,53 @@ current."
(set-fiber-continuation! fiber k)
(after-suspend fiber)))))
+;; Using SIGPROF for preemption prevents using it for other purposes
+;; like profiling. A better solution would be clock_nanosleep on the
+;; CLOCK_PROCESS_CPUTIME_ID clock from a separate thread.
+(define (maybe-preemptive sched thunk)
+ (let ((hz (scheduler-hz sched))
+ (tag (scheduler-prompt-tag sched))
+ (prev #f))
+ (define (sigprof-handler _)
+ (when (suspendable-continuation? tag)
+ (suspend-current-fiber
+ (lambda (fiber)
+ (resume-fiber fiber (lambda () (values)))))))
+
+ (define (start-preemption!)
+ (let ((period-usecs (inexact->exact (round (/ 1e6 hz)))))
+ (set! prev (car (sigaction SIGPROF sigprof-handler)))
+ (setitimer ITIMER_PROF 0 period-usecs 0 period-usecs)))
+
+ (define (stop-preemption!)
+ (setitimer ITIMER_PROF 0 0 0 0)
+ (sigaction SIGPROF prev))
+
+ (if (zero? hz)
+ (thunk)
+ (dynamic-wind start-preemption! thunk stop-preemption!))))
+
(define* (run-scheduler sched)
"Run @var{sched} until there are no more fibers ready to run, no
file descriptors being waited on, and no more timers pending to run.
Return zero values."
- (let lp ()
- (schedule-runnables-for-next-turn sched)
- (match (dequeue-all! (scheduler-runqueue sched))
- (()
- ;; Could be the scheduler is stopping, or it could be that we
- ;; got a spurious wakeup. In any case, this is the place to
- ;; check to see whether the scheduler is really done.
- (cond
- ((not (zero? (scheduler-active-fd-count sched))) (lp))
- ((not (psq-empty? (scheduler-timers sched))) (lp))
- (else (values))))
- (runnables
- (for-each run-fiber runnables)
- (lp)))))
+ (maybe-preemptive
+ sched
+ (lambda ()
+ (let lp ()
+ (schedule-runnables-for-next-turn sched)
+ (match (dequeue-all! (scheduler-runqueue sched))
+ (()
+ ;; Could be the scheduler is stopping, or it could be that we
+ ;; got a spurious wakeup. In any case, this is the place to
+ ;; check to see whether the scheduler is really done.
+ (cond
+ ((not (zero? (scheduler-active-fd-count sched))) (lp))
+ ((not (psq-empty? (scheduler-timers sched))) (lp))
+ (else (values))))
+ (runnables
+ (for-each run-fiber runnables)
+ (lp)))))))
(define (destroy-scheduler sched)
"Release any resources associated with @var{sched}."
diff --git a/tests/preemption.scm b/tests/preemption.scm
new file mode 100644
index 0000000..1886560
--- /dev/null
+++ b/tests/preemption.scm
@@ -0,0 +1,81 @@
+;; Fibers: cooperative, event-driven user-space threads.
+
+;;;; Copyright (C) 2016 Free Software Foundation, Inc.
+;;;;
+;;;; 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
+;;;;
+
+(define-module (tests parameters)
+ #:use-module (ice-9 atomic)
+ #:use-module (fibers)
+ #:use-module (fibers internal))
+
+(define failed? #f)
+
+(define-syntax-rule (assert-equal expected actual)
+ (let ((x expected))
+ (format #t "assert ~s equal to ~s: " 'actual x)
+ (force-output)
+ (let ((y actual))
+ (cond
+ ((equal? x y) (format #t "ok\n"))
+ (else
+ (format #t "no (got ~s)\n" y)
+ (set! failed? #t))))))
+
+(define-syntax-rule (assert-run-fibers-terminates exp)
+ (begin
+ (format #t "assert run-fibers on ~s terminates: " 'exp)
+ (force-output)
+ (let ((start (get-internal-real-time)))
+ (call-with-values (lambda () (run-fibers (lambda () exp) #:hz 1000))
+ (lambda vals
+ (format #t "ok (~a s)\n" (/ (- (get-internal-real-time) start)
+ 1.0 internal-time-units-per-second))
+ (apply values vals))))))
+
+(define-syntax-rule (assert-run-fibers-returns (expected ...) exp)
+ (begin
+ (call-with-values (lambda () (assert-run-fibers-terminates exp))
+ (lambda run-fiber-return-vals
+ (assert-equal '(expected ...) run-fiber-return-vals)))))
+
+(assert-run-fibers-terminates
+ (let lp ((n 0))
+ (when (< n #e1e8) (lp (1+ n)))))
+
+(define (race-until n)
+ (let ((box (make-atomic-box 0)))
+ (spawn-fiber (lambda ()
+ (let lp ()
+ (let ((x (atomic-box-ref box)))
+ (unless (= x n)
+ (when (even? x)
+ (atomic-box-set! box (1+ x)))
+ (lp))))))
+ (spawn-fiber (lambda ()
+ (let lp ()
+ (let ((x (atomic-box-ref box)))
+ (unless (= x n)
+ (when (odd? x)
+ (atomic-box-set! box (1+ x)))
+ (lp))))))
+ (let lp ()
+ (if (equal? (atomic-box-ref box) n)
+ n
+ (lp)))))
+(assert-run-fibers-returns (100) (race-until 100))
+
+(exit (if failed? 1 0))