Commit | Line | Data |
---|---|---|
6a4d3cfd JB |
1 | ;;;; runq.scm --- the runq data structure |
2 | ;;;; | |
cd5fea8d | 3 | ;;;; Copyright (C) 1996, 2001, 2006 Free Software Foundation, Inc. |
64705682 | 4 | ;;;; |
73be1d9e MV |
5 | ;;;; This library is free software; you can redistribute it and/or |
6 | ;;;; modify it under the terms of the GNU Lesser General Public | |
7 | ;;;; License as published by the Free Software Foundation; either | |
53befeb7 | 8 | ;;;; version 3 of the License, or (at your option) any later version. |
73be1d9e MV |
9 | ;;;; |
10 | ;;;; This library is distributed in the hope that it will be useful, | |
a6401ee0 | 11 | ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
73be1d9e MV |
12 | ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | ;;;; Lesser General Public License for more details. | |
14 | ;;;; | |
15 | ;;;; You should have received a copy of the GNU Lesser General Public | |
16 | ;;;; License along with this library; if not, write to the Free Software | |
92205699 | 17 | ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
a482f2cc | 18 | ;;;; |
a6401ee0 | 19 | |
64705682 | 20 | ;;; Commentary: |
6a4d3cfd | 21 | |
a6401ee0 JB |
22 | ;;; One way to schedule parallel computations in a serial environment is |
23 | ;;; to explicitly divide each task up into small, finite execution time, | |
24 | ;;; strips. Then you interleave the execution of strips from various | |
25 | ;;; tasks to achieve a kind of parallelism. Runqs are a handy data | |
26 | ;;; structure for this style of programming. | |
64705682 | 27 | ;;; |
a6401ee0 JB |
28 | ;;; We use thunks (nullary procedures) and lists of thunks to represent |
29 | ;;; strips. By convention, the return value of a strip-thunk must either | |
30 | ;;; be another strip or the value #f. | |
64705682 | 31 | ;;; |
a6401ee0 JB |
32 | ;;; A runq is a procedure that manages a queue of strips. Called with no |
33 | ;;; arguments, it processes one strip from the queue. Called with | |
34 | ;;; arguments, the arguments form a control message for the queue. The | |
35 | ;;; first argument is a symbol which is the message selector. | |
64705682 | 36 | ;;; |
a6401ee0 JB |
37 | ;;; A strip is processed this way: If the strip is a thunk, the thunk is |
38 | ;;; called -- if it returns a strip, that strip is added back to the | |
39 | ;;; queue. To process a strip which is a list of thunks, the CAR of that | |
40 | ;;; list is called. After a call to that CAR, there are 0, 1, or 2 strips | |
41 | ;;; -- perhaps one returned by the thunk, and perhaps the CDR of the | |
42 | ;;; original strip if that CDR is not nil. The runq puts whichever of | |
43 | ;;; these strips exist back on the queue. (The exact order in which | |
44 | ;;; strips are put back on the queue determines the scheduling behavior of | |
45 | ;;; a particular queue -- it's a parameter.) | |
a6401ee0 | 46 | |
64705682 | 47 | ;;; Code: |
a6401ee0 | 48 | |
64705682 | 49 | (define-module (ice-9 runq) |
1a179b03 MD |
50 | :use-module (ice-9 q) |
51 | :export (runq-control make-void-runq make-fair-runq | |
52 | make-exclusive-runq make-subordinate-runq-to strip-sequence | |
53 | fair-strip-subtask)) | |
a6401ee0 JB |
54 | |
55 | ;;;; | |
56 | ;;; (runq-control q msg . args) | |
64705682 | 57 | ;;; |
a6401ee0 JB |
58 | ;;; processes in the default way the control messages that |
59 | ;;; can be sent to a runq. Q should be an ordinary | |
60 | ;;; Q (see utils/q.scm). | |
64705682 | 61 | ;;; |
a6401ee0 | 62 | ;;; The standard runq messages are: |
64705682 | 63 | ;;; |
a6401ee0 JB |
64 | ;;; 'add! strip0 strip1... ;; to enqueue one or more strips |
65 | ;;; 'enqueue! strip0 strip1... ;; to enqueue one or more strips | |
66 | ;;; 'push! strip0 ... ;; add strips to the front of the queue | |
67 | ;;; 'empty? ;; true if it is | |
68 | ;;; 'length ;; how many strips in the queue? | |
69 | ;;; 'kill! ;; empty the queue | |
70 | ;;; else ;; throw 'not-understood | |
64705682 | 71 | ;;; |
1a179b03 | 72 | (define (runq-control q msg . args) |
a6401ee0 JB |
73 | (case msg |
74 | ((add!) (for-each (lambda (t) (enq! q t)) args) '*unspecified*) | |
608cf70c | 75 | ((enqueue!) (for-each (lambda (t) (enq! q t)) args) '*unspecified*) |
a6401ee0 JB |
76 | ((push!) (for-each (lambda (t) (q-push! q t)) args) '*unspecified*) |
77 | ((empty?) (q-empty? q)) | |
78 | ((length) (q-length q)) | |
79 | ((kill!) (set! q (make-q))) | |
80 | (else (throw 'not-understood msg args)))) | |
81 | ||
82 | (define (run-strip thunk) (catch #t thunk (lambda ign (warn 'runq-strip thunk ign) #f))) | |
83 | ||
84 | ;;;; | |
85 | ;;; make-void-runq | |
86 | ;;; | |
87 | ;;; Make a runq that discards all messages except "length", for which | |
88 | ;;; it returns 0. | |
89 | ;;; | |
1a179b03 | 90 | (define (make-void-runq) |
a6401ee0 JB |
91 | (lambda opts |
92 | (and opts | |
93 | (apply-to-args opts | |
94 | (lambda (msg . args) | |
95 | (case msg | |
96 | ((length) 0) | |
97 | (else #f))))))) | |
98 | ||
64705682 | 99 | ;;;; |
a6401ee0 | 100 | ;;; (make-fair-runq) |
64705682 | 101 | ;;; |
a6401ee0 JB |
102 | ;;; Returns a runq procedure. |
103 | ;;; Called with no arguments, the procedure processes one strip from the queue. | |
104 | ;;; Called with arguments, it uses runq-control. | |
64705682 | 105 | ;;; |
a6401ee0 JB |
106 | ;;; In a fair runq, if a strip returns a new strip X, X is added |
107 | ;;; to the end of the queue, meaning it will be the last to execute | |
108 | ;;; of all the remaining procedures. | |
64705682 | 109 | ;;; |
1a179b03 | 110 | (define (make-fair-runq) |
a6401ee0 | 111 | (letrec ((q (make-q)) |
64705682 | 112 | (self |
a6401ee0 JB |
113 | (lambda ctl |
114 | (if ctl | |
115 | (apply runq-control q ctl) | |
116 | (and (not (q-empty? q)) | |
117 | (let ((next-strip (deq! q))) | |
118 | (cond | |
119 | ((procedure? next-strip) (let ((k (run-strip next-strip))) | |
120 | (and k (enq! q k)))) | |
121 | ((pair? next-strip) (let ((k (run-strip (car next-strip)))) | |
122 | (and k (enq! q k))) | |
123 | (if (not (null? (cdr next-strip))) | |
124 | (enq! q (cdr next-strip))))) | |
125 | self)))))) | |
126 | self)) | |
127 | ||
128 | ||
64705682 | 129 | ;;;; |
a6401ee0 | 130 | ;;; (make-exclusive-runq) |
64705682 | 131 | ;;; |
a6401ee0 JB |
132 | ;;; Returns a runq procedure. |
133 | ;;; Called with no arguments, the procedure processes one strip from the queue. | |
134 | ;;; Called with arguments, it uses runq-control. | |
64705682 | 135 | ;;; |
a6401ee0 JB |
136 | ;;; In an exclusive runq, if a strip W returns a new strip X, X is added |
137 | ;;; to the front of the queue, meaning it will be the next to execute | |
138 | ;;; of all the remaining procedures. | |
64705682 | 139 | ;;; |
a6401ee0 JB |
140 | ;;; An exception to this occurs if W was the CAR of a list of strips. |
141 | ;;; In that case, after the return value of W is pushed onto the front | |
142 | ;;; of the queue, the CDR of the list of strips is pushed in front | |
143 | ;;; of that (if the CDR is not nil). This way, the rest of the thunks | |
144 | ;;; in the list that contained W have priority over the return value of W. | |
64705682 | 145 | ;;; |
1a179b03 | 146 | (define (make-exclusive-runq) |
a6401ee0 | 147 | (letrec ((q (make-q)) |
64705682 | 148 | (self |
a6401ee0 JB |
149 | (lambda ctl |
150 | (if ctl | |
151 | (apply runq-control q ctl) | |
152 | (and (not (q-empty? q)) | |
153 | (let ((next-strip (deq! q))) | |
154 | (cond | |
155 | ((procedure? next-strip) (let ((k (run-strip next-strip))) | |
156 | (and k (q-push! q k)))) | |
157 | ((pair? next-strip) (let ((k (run-strip (car next-strip)))) | |
158 | (and k (q-push! q k))) | |
159 | (if (not (null? (cdr next-strip))) | |
160 | (q-push! q (cdr next-strip))))) | |
161 | self)))))) | |
162 | self)) | |
163 | ||
164 | ||
64705682 | 165 | ;;;; |
a6401ee0 | 166 | ;;; (make-subordinate-runq-to superior basic-inferior) |
64705682 | 167 | ;;; |
a6401ee0 | 168 | ;;; Returns a runq proxy for the runq basic-inferior. |
64705682 | 169 | ;;; |
a6401ee0 | 170 | ;;; The proxy watches for operations on the basic-inferior that cause |
64705682 | 171 | ;;; a transition from a queue length of 0 to a non-zero length and |
a6401ee0 JB |
172 | ;;; vice versa. While the basic-inferior queue is not empty, |
173 | ;;; the proxy installs a task on the superior runq. Each strip | |
174 | ;;; of that task processes N strips from the basic-inferior where | |
175 | ;;; N is the length of the basic-inferior queue when the proxy | |
64705682 TTN |
176 | ;;; strip is entered. [Countless scheduling variations are possible.] |
177 | ;;; | |
1a179b03 | 178 | (define (make-subordinate-runq-to superior-runq basic-runq) |
a6401ee0 JB |
179 | (let ((runq-task (cons #f #f))) |
180 | (set-car! runq-task | |
181 | (lambda () | |
182 | (if (basic-runq 'empty?) | |
183 | (set-cdr! runq-task #f) | |
184 | (do ((n (basic-runq 'length) (1- n))) | |
185 | ((<= n 0) #f) | |
186 | (basic-runq))))) | |
187 | (letrec ((self | |
188 | (lambda ctl | |
189 | (if (not ctl) | |
190 | (let ((answer (basic-runq))) | |
191 | (self 'empty?) | |
192 | answer) | |
193 | (begin | |
194 | (case (car ctl) | |
195 | ((suspend) (set-cdr! runq-task #f)) | |
196 | (else (let ((answer (apply basic-runq ctl))) | |
197 | (if (and (not (cdr runq-task)) (not (basic-runq 'empty?))) | |
198 | (begin | |
199 | (set-cdr! runq-task runq-task) | |
200 | (superior-runq 'add! runq-task))) | |
201 | answer)))))))) | |
202 | self))) | |
203 | ||
204 | ;;;; | |
205 | ;;; (define fork-strips (lambda args args)) | |
64705682 | 206 | ;;; Return a strip that starts several strips in |
a6401ee0 JB |
207 | ;;; parallel. If this strip is enqueued on a fair |
208 | ;;; runq, strips of the parallel subtasks will run | |
209 | ;;; round-robin style. | |
210 | ;;; | |
211 | (define fork-strips (lambda args args)) | |
212 | ||
213 | ||
64705682 | 214 | ;;;; |
a6401ee0 | 215 | ;;; (strip-sequence . strips) |
64705682 | 216 | ;;; |
a6401ee0 | 217 | ;;; Returns a new strip which is the concatenation of the argument strips. |
64705682 | 218 | ;;; |
99b1dd09 AW |
219 | (define (strip-sequence . strips) |
220 | (lambda () | |
221 | (let loop ((st (let ((a strips)) (set! strips #f) a))) | |
222 | (and (not (null? st)) | |
223 | (let ((then ((car st)))) | |
224 | (if then | |
225 | (lambda () (loop (cons then (cdr st)))) | |
226 | (lambda () (loop (cdr st))))))))) | |
a6401ee0 JB |
227 | |
228 | ||
229 | ;;;; | |
230 | ;;; (fair-strip-subtask . initial-strips) | |
64705682 | 231 | ;;; |
a6401ee0 JB |
232 | ;;; Returns a new strip which is the synchronos, fair, |
233 | ;;; parallel execution of the argument strips. | |
64705682 TTN |
234 | ;;; |
235 | ;;; | |
a6401ee0 | 236 | ;;; |
1a179b03 | 237 | (define (fair-strip-subtask . initial-strips) |
a6401ee0 JB |
238 | (let ((st (make-fair-runq))) |
239 | (apply st 'add! initial-strips) | |
240 | st)) | |
241 | ||
64705682 | 242 | ;;; runq.scm ends here |