summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2016-10-11 15:29:06 +0200
committerAndy Wingo <wingo@pobox.com>2016-10-11 15:29:06 +0200
commit94fcac03caea4c11375ff66721a28388fe4de735 (patch)
treef6bcfe642d67e1c1b7674fb5e14b8e5d0046b332
parentFactor out deque implementation (diff)
downloadguile-fibers-94fcac03caea4c11375ff66721a28388fe4de735.tar.gz
Runnables refactor
* fibers/deque.scm (empty-deque?, dequeue-all, dequeue-all!): New interfaces. (update!): New helper. (enqueue!): Use new helper. * fibers/internal.scm: Use deque instead of stack for runnables.
-rw-r--r--fibers/deque.scm37
-rw-r--r--fibers/internal.scm35
2 files changed, 45 insertions, 27 deletions
diff --git a/fibers/deque.scm b/fibers/deque.scm
index 309072b..8e65d61 100644
--- a/fibers/deque.scm
+++ b/fibers/deque.scm
@@ -22,10 +22,13 @@
#:use-module (ice-9 match)
#:export (make-deque
make-empty-deque
+ empty-deque?
enqueue
dequeue
+ dequeue-all
dequeue-match
undequeue
+ dequeue-all!
enqueue!))
;; A functional double-ended queue ("deque") has a head and a tail,
@@ -37,6 +40,11 @@
(define (make-empty-deque)
(make-deque '() '()))
+(define (empty-deque? dq)
+ (match dq
+ ((() . ()) #t)
+ (_ #f)))
+
(define (enqueue dq item)
(match dq
((head . tail)
@@ -51,6 +59,11 @@
(((item . head) . tail)
(values (make-deque head tail) item))))
+(define (dequeue-all dq)
+ (match dq
+ ((head . ()) head)
+ ((head . tail) (append head (reverse tail)))))
+
(define (dequeue-match dq pred)
(match dq
((() . ()) (values #f #f))
@@ -68,9 +81,21 @@
((head . tail)
(make-deque (cons item head) tail))))
-(define (enqueue! qbox item)
- (let spin ((q (atomic-box-ref qbox)))
- (let* ((q* (enqueue q item))
- (q** (atomic-box-compare-and-swap! qbox q q*)))
- (unless (eq? q q**)
- (spin q**)))))
+(define-inlinable (update! box f)
+ (let spin ((x (atomic-box-ref box)))
+ (call-with-values (lambda () (f x))
+ (lambda (x* ret)
+ (let ((x** (atomic-box-compare-and-swap! box x x*)))
+ (if (eq? x x**)
+ ret
+ (spin x**)))))))
+
+(define (dequeue-all! dqbox)
+ (update! dqbox (lambda (dq)
+ (values (make-empty-deque)
+ (dequeue-all dq)))))
+
+(define (enqueue! dqbox item)
+ (update! dqbox (lambda (dq)
+ (values (enqueue dq item)
+ #f))))
diff --git a/fibers/internal.scm b/fibers/internal.scm
index 81a0c60..ed755e6 100644
--- a/fibers/internal.scm
+++ b/fibers/internal.scm
@@ -18,8 +18,8 @@
;;;;
(define-module (fibers internal)
- #:use-module ((srfi srfi-1) #:select (append-reverse!))
#:use-module (srfi srfi-9)
+ #:use-module (fibers deque)
#:use-module (fibers epoll)
#:use-module (fibers psq)
#:use-module (fibers nameset)
@@ -68,7 +68,7 @@
(nameset-ref fibers-nameset name))
(define-record-type <scheduler>
- (%make-scheduler name epfd active-fd-count prompt-tag runnables
+ (%make-scheduler name epfd active-fd-count prompt-tag runqueue
sources timers inbox inbox-state wake-pipe
kernel-thread)
scheduler?
@@ -76,8 +76,8 @@
(epfd scheduler-epfd)
(active-fd-count scheduler-active-fd-count set-scheduler-active-fd-count!)
(prompt-tag scheduler-prompt-tag)
- ;; (fiber ...)
- (runnables scheduler-runnables set-scheduler-runnables!)
+ ;; atomic box of deque of fiber
+ (runqueue scheduler-runqueue)
;; fd -> ((total-events . min-expiry) #(events expiry fiber) ...)
(sources scheduler-sources)
;; PSQ of thunk -> expiry
@@ -131,7 +131,7 @@
(let ((epfd (epoll-create))
(active-fd-count 0)
(prompt-tag (make-prompt-tag "fibers"))
- (runnables '())
+ (runqueue (make-atomic-box (make-empty-deque)))
(sources (make-hash-table))
(timers (make-psq (match-lambda*
(((t1 . c1) (t2 . c2)) (< t1 t2)))
@@ -144,7 +144,7 @@
((read-pipe . _)
(epoll-add! epfd (fileno read-pipe) EPOLLIN)))
(let ((sched (%make-scheduler #f epfd active-fd-count prompt-tag
- runnables sources timers
+ runqueue sources timers
inbox inbox-state wake-pipe kernel-thread)))
(set-scheduler-name! sched (nameset-add! schedulers-nameset sched))
sched)))
@@ -190,8 +190,7 @@
(when (eq? (fiber-state fiber) 'suspended)
(set-fiber-state! fiber 'runnable)
(set-fiber-data! fiber thunk)
- (set-scheduler-runnables! sched
- (cons fiber (scheduler-runnables sched)))))
+ (enqueue! (scheduler-runqueue sched) fiber)))
(define (schedule/remote)
(atomic-box-prepend! (scheduler-inbox sched) (cons fiber thunk))
(match (atomic-box-ref (scheduler-inbox-state sched))
@@ -250,8 +249,9 @@
;; There are pending requests in our inbox, so we don't need to
;; sleep at all.
0)
- ((not (null? (scheduler-runnables sched)))
- ;; Likewise, don't sleep if there are runnables scheduled already.
+ ((not (empty-deque? (atomic-box-ref (scheduler-runqueue sched))))
+ ;; Likewise, don't sleep if there are fibers in the runqueue
+ ;; already.
0)
((psq-empty? (scheduler-timers sched))
-1)
@@ -265,10 +265,7 @@
internal-time-units-per-millisecond))))))))
(define (run-timers sched)
- ;; Run expired timer thunks. Do it in such a way that the one with
- ;; the earliest expiry is called last, so that if a timer ends up
- ;; resuming a fiber, the earliest one will end up first on the
- ;; runnable list.
+ ;; Run expired timer thunks in the order that they expired.
(let ((now (get-internal-real-time)))
(let run-timers ((timers (scheduler-timers sched)))
(cond
@@ -279,8 +276,8 @@
(call-with-values (lambda () (psq-pop timers))
(match-lambda*
(((_ . thunk) timers)
- (run-timers timers)
- (thunk)))))))))
+ (thunk)
+ (run-timers timers)))))))))
(define (handle-inbox sched)
(for-each (match-lambda
@@ -298,9 +295,6 @@
;; their corresponding fibers. Also run any timers that have timed
;; out, and process the inbox that receives requests-to-schedule
;; from remote threads.
- ;;
- ;; FIXME: use a deque instead
- (set-scheduler-runnables! sched (reverse (scheduler-runnables sched)))
(let ((timeout (scheduler-poll-timeout sched)))
(unless (and (not (zero? timeout))
(zero? (scheduler-active-fd-count sched)))
@@ -341,7 +335,7 @@
(define* (run-scheduler sched #:key join-fiber)
(let lp ()
(schedule-runnables-for-next-turn sched)
- (match (scheduler-runnables 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
@@ -352,7 +346,6 @@
((not (eq? (fiber-state join-fiber) 'finished)) (lp))
(else (apply values (fiber-data join-fiber)))))
(runnables
- (set-scheduler-runnables! sched '())
(for-each run-fiber runnables)
(lp)))))