9.11. Multitasking with Engines

Engines are a high-level process abstraction supporting timed preemption [6, 10]. Engines may be used to simulate multiprocessing, implement light-weight threads, implement operating system kernels, and perform nondeterministic computations. The engine implementation is one of the more interesting applications of continuations in Scheme.

An engine is created by passing a thunk (procedure of no arguments) to make-engine. The body of the thunk is the computation to be performed by the engine. An engine itself is a procedure of three arguments:

ticks, a positive integer that specifies the amount of fuel to be given to the engine. An engine executes until this fuel runs out or until its computation finishes.
complete, a procedure of two arguments that specifies what to do if the computation finishes. Its arguments will be the amount of fuel left over and the result of the computation.
expire, a procedure of one argument that specifies what to do if the fuel runs out before the computation finishes. Its argument will be a new engine capable of continuing the computation from the point of interruption.

When an engine is applied to its arguments, it sets up a timer to fire in ticks time units. If the engine computation completes before the timer goes off, the system invokes complete, passing it the number of ticks left over and the value of the computation. If, on the other hand, the timer goes off before the engine computation completes, the system creates a new engine from the continuation of the interrupted computation and passes this engine to expire. complete and expire are invoked in the continuation of the engine invocation.

The following example creates an engine from a trivial computation, 3, and gives the engine 10 ticks.

 (define eng   (make-engine     (lambda () 3))) (eng 10   (lambda (ticks value) value)   (lambda (x) x)) ⇒ 3

It is often useful to pass list as the complete procedure to an engine, causing the engine to return a list of the ticks remaining and the value if the computation completes.

 (eng 10   list   (lambda (x) x)) ⇒ (9 3)

In the example above, the value was 3 and there were 9 ticks left over, i.e., it took only one unit of fuel to evaluate 3. (The fuel amounts given here are for illustration only. The actual amount may differ.)

Typically, the engine computation does not finish in one try. The following example displays the use of an engine to compute the 10th Fibonacci number (see Section 3.2) in steps.

 (define fibonacci   (lambda (n)     (if (< n 2)         n         (+ (fibonacci (- n 1))            (fibonacci (- n 2)))))) (define eng   (make-engine     (lambda ()       (fibonacci 10)))) (eng 50   list   (lambda (new-eng)     (set! eng new-eng)     "expired")) ⇒ "expired" (eng 50   list   (lambda (new-eng)     (set! eng new-eng)     "expired")) ⇒ "expired" (eng 50   list   (lambda (new-eng)     (set! eng new-eng)     "expired")) ⇒ "expired" (eng 50   list   (lambda (new-eng)     (set! eng new-eng)     "expired")) ⇒ (23 55)

Each time the engine's fuel ran out, the expire procedure assigned eng to the new engine. The entire computation required four allotments of 50 ticks to complete; of the last 50 it used all but 23. Thus, the total amount of fuel used was 177 ticks. This leads us to the following procedure, mileage, which uses engines to "time" a computation.

 (define mileage   (lambda (thunk)     (let loop ((eng (make-engine thunk)) (total-ticks 0))       (eng 50         (lambda (ticks value)           (+ total-ticks (- 50 ticks)))         (lambda (new-eng)           (loop new-eng (+ total-ticks 50))))))) (mileage (lambda () (fibonacci 10))) ⇒ 177

The choice of 50 for the number of ticks to use each time is arbitrary, of course. It might make more sense to pass a much larger number, say 10000, in order to reduce the number of times the computation is interrupted.

The next procedure, round-robin, could be the basis for a simple time-sharing operating system. round-robin maintains a queue of processes (a list of engines) and cycles through the queue in a round-robin fashion, allowing each process to run for a set amount of time. round-robin returns a list of the values returned by the engine computations in the order that the computations complete.

 (define round-robin   (lambda (engs)     (if (null? engs)         '()         ((car engs) 1           (lambda (ticks value)             (cons value (round-robin (cdr engs))))           (lambda (eng)             (round-robin               (append (cdr engs) (list eng))))))))

Assuming the amount of computation corresponding to one tick is constant, the effect of round-robin is to return a list of the values sorted from the quickest to complete to the slowest to complete. Thus, when we call round-robin on a list of engines, each computing one of the Fibonacci numbers, the output list is sorted with the earlier Fibonacci numbers first, regardless of the order of the input list.

 (round-robin   (map (lambda (x)          (make-engine            (lambda ()               (fibonacci x))))        '(4 5 2 8 3 7 6 2))) ⇒ (1 1 2 3 5 8 13 21)

More interesting things could happen if the amount of fuel varied each time through the loop. In this case, the computation would be nondeterministic, i.e., the results would vary from call to call.

The following syntactic form, por (parallel-or), returns the first of its expressions to complete with a true value. por is implemented with the procedure first-true, which is similar to round-robin but quits when any of the engines completes with a true value. If all of the engines complete, but none with a true value, first-true (and hence por) returns #f.

 (define-syntax por   (syntax-rules ()     (( x ...)      (first-true        (list (make-engine (lambda () x)) ...))))) (define first-true   (lambda (engs)     (if (null? engs)         #f         ((car engs) 1           (lambda (ticks value)              (or value (first-true (cdr engs))))           (lambda (eng)             (first-true                (append (cdr engs) (list eng))))))))

Even if one of the expressions is an infinite loop, por can still finish (as long as one of the other expressions completes and returns a true value).

 (por 1 2) ⇒ 1 (por ((lambda (x) (x x)) (lambda (x) (x x)))      (fibonacci 10)) ⇒ 55

The first subexpression of the second por expression is nonterminating, so the answer is the value of the second subexpression.

Let's turn to the implementation of engines. Any preemptive multitasking primitive must have the ability to interrupt a running process after a given amount of computation. This ability is provided by a primitive timer interrupt mechanism in some Scheme implementations. We will construct a suitable one here.

Our timer system defines three procedures: start-timer, stop-timer, and decrement-timer, which can be described operationally as follows.

(start-timer ticks handler) sets the timer to ticks and installs handler as the procedure to be invoked (without arguments) when the timer expires, i.e., reaches zero.
(stop-timer) resets the timer and returns the number of ticks remaining.
(decrement-timer) decrements the timer by one tick if the timer is on, i.e., if it is not zero. When the timer reaches zero, decrement-timer invokes the saved handler. If the timer has already reached zero, decrement-timer returns without changing the timer.

Code to implement these procedures is given along with the engine implementation below.

Using the timer system requires inserting calls to decrement-timer in appropriate places. Consuming a timer tick on entry to a procedure usually provides a sufficient level of granularity. This can be accomplished by using timed-lambda as defined below in place of lambda. timed-lambda simply invokes decrement-timer before executing the expressions in its body.

 (define-syntax timed-lambda   (syntax-rules ()     (( formals exp1 exp2 ...)      (lambda formals (decrement-timer) exp1 exp2 ...))))

It may be useful to redefine named let and do to use timed-lambda as well, so that recursions expressed with these constructs are timed. If you use this mechanism, do not forget to use the timed versions of lambda and other forms in code run within an engine, or no ticks will be consumed.

Now that we have a suitable timer, we can implement engines in terms of the timer and continuations. We use call/cc in two places in the engine implementation: (1) to obtain the continuation of the computation that invokes the engine so that we can return to that continuation when the engine computation completes or the timer expires, and (2) to obtain the continuation of the engine computation when the timer expires so that we can return to this computation if the newly created engine is subsequently run.

The state of the engine system is contained in two variables local to the engine system: do-complete and do-expire. When an engine is started, the engine assigns to do-complete and do-expire procedures that, when invoked, return to the continuation of the engine's caller to invoke complete or expire. The engine starts (or restarts) the computation by invoking the procedure passed as an argument to make-engine with the specified number of ticks. The ticks and the local procedure timer-handler are then used to start the timer.

Suppose that the timer expires before the engine computation completes. The procedure timer-handler is then invoked. It initiates a call to start-timer but obtains the ticks by calling call/cc with do-expire. Consequently, do-expire is called with a continuation that, if invoked, will restart the timer and continue the interrupted computation. do-expire creates a new engine from this continuation and arranges for the engine's expire procedure to be invoked with the new engine in the correct continuation.

If, on the other hand, the engine computation completes before the timer expires, the timer is stopped and the number of ticks remaining is passed along with the value to do-complete; do-complete arranges for the engine's complete procedure to be invoked with the ticks and value in the correct continuation.

Let's discuss a couple of subtle aspects to this code. The first concerns the method used to start the timer when an engine is invoked. The code would apparently be simplified by letting new-engine start the timer before it initiates or resumes the engine computation, instead of passing the ticks to the computation and letting it start the timer. Starting the timer within the computation, however, prevents ticks from being consumed prematurely. If the engine system itself consumes fuel, then an engine provided with a small amount of fuel may not progress toward completion. (It may, in fact, make negative progress.) If the software timer described above is used, this problem is actually avoided by compiling the engine-making code with the untimed version of lambda.

The second subtlety concerns the procedures created by do-complete and do-expire and subsequently applied by the continuation of the call/cc application. It may appear that do-complete could first invoke the engine's complete procedure, then pass the result to the continuation (and similarly for do-expire) as follows.

 (escape (complete value ticks))

This would result in improper treatment of tail recursion, however. The problem is that the current continuation would not be replaced with the continuation stored in escape until the call to the complete procedure returns. Consequently, both the continuation of the running engine and the continuation of the engine invocation could be retained for an indefinite period of time, when in fact the actual engine invocation may appear to be tail-recursive. This is especially inappropriate because the engine interface encourages use of continuation-passing style and hence tail recursion. The round-robin scheduler and first-true provide good examples of this, since the expire procedure in each invokes engines tail-recursively.

We maintain proper treatment of tail recursion by arranging for do-complete and do-expire to escape from the continuation of the running engine before invoking the complete or expire procedures. Since the continuation of the engine invocation is a procedure application, passing it a procedure of no arguments results in application of the procedure in the continuation of the engine invocation.

 (define start-timer #f) (define stop-timer #f) (define decrement-timer #f) (let ((clock 0) (handler #f))   (set! start-timer     (lambda (ticks new-handler)        (set! handler new-handler)        (set! clock ticks)))   (set! stop-timer     (lambda ()        (let ((time-left clock))          (set! clock 0)           time-left)))   (set! decrement-timer     (lambda ()       (if (> clock 0)           (begin             (set! clock (- clock 1))             (if (= clock 0) (handler))))))) (define make-engine   (let ((do-complete #f) (do-expire #f))     (define timer-handler       (lambda ()          (start-timer (call/cc do-expire) timer-handler)))     (define new-engine       (lambda (resume)        (lambda (ticks complete expire)          ((call/cc             (lambda (escape)               (set! do-complete                 (lambda (ticks value)                   (escape (lambda () (complete ticks value)))))               (set! do-expire                 (lambda (resume)                   (escape (lambda ()                             (expire (new-engine resume))))))               (resume ticks)))))))     (lambda (proc)       (new-engine         (lambda (ticks)            (start-timer ticks timer-handler)            (let ((value (proc)))              (let ((ticks (stop-timer)))                (do-complete ticks value))))))))

Exercise 9.11.1.

It may appear that the nested let expressions in the body of make-engine:

 (let ((value (proc)))   (let ((ticks (stop-timer)))     (do-complete ticks value)))

could be replaced with:

 (let ((value (proc)) (ticks (stop-timer)))   (do-complete value ticks))

Why is this not correct?

Exercise 9.11.2.

It would also be incorrect to replace the nested let expressions discussed in the preceding exercise with:

 (let ((value (proc)))   (do-complete value (stop-timer)))

Why?

Exercise 9.11.3.

Modify the engine implementation to provide a procedure, engine-return, that returns immediately from an engine.

Exercise 9.11.4.

Implement the kernel of a small operating system using engines for processes. Processes should request services (such as reading input from the user) by evaluating an expression of the form (trap 'request). Use call/cc and engine-return from the preceding exercise to implement trap.

Exercise 9.11.5.

Write the same operating-system kernel without using engines, building instead from continuations and timer interrupts.

Exercise 9.11.6.

This implementation of engines does not allow one engine to call another, i.e., nested engines [6]. Modify the implementation to allow nested engines.