diff options
| author | Andy Wingo <wingo@pobox.com> | 2016-12-12 23:20:35 +0100 |
|---|---|---|
| committer | Andy Wingo <wingo@pobox.com> | 2016-12-12 23:22:13 +0100 |
| commit | 5bf19089e17b50600b515baf93165817184a96e2 (patch) | |
| tree | 7563f97409a93dc3cfb3b4b7b44ae405373fb3b1 | |
| parent | Minor documentation tweak (diff) | |
| download | guile-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.am | 3 | ||||
| -rw-r--r-- | TODO.md | 16 | ||||
| -rw-r--r-- | fibers.scm | 2 | ||||
| -rw-r--r-- | fibers.texi | 32 | ||||
| -rw-r--r-- | fibers/internal.scm | 67 | ||||
| -rw-r--r-- | tests/preemption.scm | 81 |
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 += \ @@ -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 @@ -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)) |
