From 94fcac03caea4c11375ff66721a28388fe4de735 Mon Sep 17 00:00:00 2001 From: Andy Wingo Date: Tue, 11 Oct 2016 15:29:06 +0200 Subject: 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. --- fibers/deque.scm | 37 +++++++++++++++++++++++++++++++------ fibers/internal.scm | 35 ++++++++++++++--------------------- 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 - (%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))))) -- cgit v1.3