All Databases MacTech Vol 03-1987

Multitasking

Volume Number: 3

Issue Number: 12

Column Tag: The Visiting Developer

Multitasking in MacScheme+Toolsmith™

By William Clinger, Tektronix Laboratories

Thanks to MultiFinder, everyone knows that multitasking lets you run more than

one thing at once. In an operating system like MultiFinder, multitasking means that

you can run more than one application at once. In a programming language,

multitasking means that you can run several parts of your program at once. This

article explains why you might want to use multitasking within a single program, and

warns against a class of bugs that you must guard against when you do use multitasking.

It also surveys the multitasking facilities in MacScheme+Toolsmith™, which are

probably the best developed of any language for the Macintosh.

The Macintosh contains only one 68000 or 68020, but there will come a day

when most computers contain many such processors. Then multitasking will make

programs run faster because the processors will work as a team, with each processor

working on its part of the problem to be solved. These pieces of a problem are of

course called tasks.

A single hardware processor can work on only one task at a time. To get the effect

of working on multiple tasks at once, the processor must switch between tasks. In

MultiFinder, these switches occur only when a task calls GetNextEvent or

WaitNextEvent. If a task were to get into an infinite loop where it never calls one of

these routines, that would be the end of the multitasking. This is what people mean

when they say that MultiFinder does non-preemptive multitasking. It never

interrupts, or preempts, a running task. Task switches can occur only when a task

yields control by calling GetNextEvent or WaitNextEvent. Applications are supposed to

call these traps fairly often, so MultiFinder works well in practice.

MacScheme+Toolsmith, on the other hand, does preemptive multitasking.

MacScheme programs do not have to call GetNextEvent or WaitNextEvent, because there

is a separate task that calls these traps. Every so often, MacScheme+Toolsmith simply

interrupts the currently executing task and switches to a new task. Preemptive

multitasking is more reliable than non-preemptive multitasking because it works

even when a buggy task gets into an infinite loop. This kind of reliability isn’t very

important for an operating system like MultiFinder because applications aren’t

supposed to be buggy, but it matters a lot for a development system like

MacScheme+Toolsmith because all programs are buggy when you’re trying to debug

them.

Why would anyone want to use multiple tasks within a single program? Why not

perform the tasks sequentially--that is, one after the other? A good question. It turns

out that multiple concurrent tasks within a single program are much more useful on

the Macintosh than on most other computers. Consider, for example, the task of

blinking the insertion point within a text window. That task lasts as long as the

window is open. You can’t run tasks like that in sequence, because once you’ve started

such a task you’d never get to any other tasks.

Does this seem artificial? How about the task that changes the cursor’s shape in

response to its position on the screen? How about the task that updates the time

displayed on the alarm clock? A considerable part of the Macintosh user interface

really consists of concurrent tasks. Because the original concept of the Macintosh did

not include real concurrent tasks, however, these features of the user interface have

generally been programmed using such clumsy mechanisms as event loops and desk

accessories.

An alternative is to use the vertical retrace manager to perform preemptive task

scheduling. The operating system task that performs mouse tracking is one of the tasks

that is programmed this way. The vertical retrace manager is not generally useful,

though, because tasks that run during a vertical retrace interrupt are very restricted

in what they can do and must yield control of the processor within a very short time.

The most general alternative is to use a language that supports concurrent tasks.

User interface chores are routinely implemented as concurrent tasks by programmers

using MacScheme+Toolsmith. To create a task in MacScheme+Toolsmith, you first

create a procedure of no arguments that will perform the task. Then you pass that

procedure as an argument to start-task. For example, you can define a task that

perpetually increments a global variable n as follows:

>>> (define n 0)

>>> (define (loop1)

(set! n (+ n 1))

(loop1))

loop1

>>> (define t1 (start-task loop1))

The call to start-task begins the concurrent task. You can observe its progress

by checking on the value of n.

>>> n

46954

>>> n

103925

>>> n

165850

>>> n

184428

The value returned by start-task is a task object. You can kill the task by calling

kill-task.

>>> n

718335

>>> n

728243

>>> (kill-task t1)

>>> n

821130

>>> n

821130

If the procedure that was passed to start-task ever returns, the task will kill

itself automatically. A task can kill itself explicitly by calling the kill- current-task

procedure. If all tasks die, then a warning message will appear and a new task will be

created for the read/eval/print loop. The kill-all-tasks procedure will track down

and kill all tasks, including runaways, which is useful for debugging.

If an error occurs, task switches are disabled while you investigate the problem

using the MacScheme debugger. This keeps variables from changing on you until

you’ve figured out what’s going on. Tasking resumes when you’ve repaired the

problem and continue the computation from the debugger.

You can improve the overall performance of a program by having your tasks call

surrender-timeslice to force an immediate task switch whenever they don’t need to

run again for a while. For example, a task that is blinking the insertion point in a

window can afford to wait for a substantial fraction of a second before it blinks again.

The surrender-timeslice procedure is analogous to the WaitNextEvent trap, which

improves the tasking performance of MultiFinder when applications call it in

preference to GetNextEvent.

Because it takes time to switch between tasks, you might think that on a single

processor system such as the Macintosh programs that don’t use concurrent tasks

would run faster than otherwise equivalent programs that are organized as con current

tasks. That’s usually true, but not always. Figure 1 shows a procedure that takes a

pattern x and arbitrarily many additional arguments, and tries to find one of them that

is not equal to the pattern. If the program is such that most of the arguments are equal

to the pattern, and the arguments are large structures (so it takes a long time to

compare them against the pattern if they are equal), but there is usually one argument

that is so different that it can quickly be determined to be unequal once the procedure

gets around to trying it, then the procedure in Figure 2 will run faster on the average.

The reason is that it conducts a breadth-first search using concurrent tasks instead of

a sequential, depth-first search.

A breadth-first search could be programmed explicitly without using tasks, but

that would make it much more complicated, and the resulting procedure might well run

slower than the procedure in Figure 2 because the programmer would probably not be

able to spend as much time optimizing the breadth-first search as was spent on the

multitasking facilities of MacScheme+Toolsmith.

The procedure in Figure 2 works by creating a task for each argument except the

first. Whenever a task finds that its argument is not equal to the pattern, then it

stores its argument in a variable named ans. Meanwhile the procedure that created

these tasks just waits for one of them to find the answer or for all of them to finish.

How does it know when all of the tasks have finished? The task-count variable holds

the number of tasks that have not yet finished. When it gets to zero, then either all the

tasks have finished, or else one of the tasks has found an answer and has set the

task-count to zero to indicate that the remaining tasks are irrelevant. When the

task-count gets to zero, the main procedure kills all the tasks it has created, just in

case some of them are still alive (it doesn’t hurt to kill a task twice), and returns the

answer.

Actually, there is a very interesting bug in Figure 2. It has to do with the

assignment

(set! task-count (- task-count 1))

that is executed whenever a task has found that its argument is equal to the pattern.

Suppose two concurrent tasks, t1 and t2, try to execute this assignment at the same

time. Suppose further that the value of task-count is 2, so that task-count should be 0

after both t1 and t2 have executed the assignment. If we’re extremely unlucky, then

t1 might fetch the value of task-count, and then t2 might also fetch the value of

task-count while t1 is still subtracting 1 from 2. Then t1 would store a 1 back in the

variable, and so would t2. The variable would never reach zero, so the procedure

would never return.

How do we fix this bug? The assignment must be executed as an uninterruptible

atomic action, so that only one task at a time can execute any part of it. To accomplish

this, MacScheme+Toolsmith supplies a procedure named call-without-interrupts that

takes a procedure of no arguments and calls it uninterruptibly. We can therefore fix

the bug by changing the assignment to

(call-without-interrupts

(lambda ()

(set! task-count (- task-count 1))))

This bug is typical of a new class of bugs that you must watch out for when using

multitasking. At the operating system level, file i/o is the analog of assignment.

Developers need to watch out for this class of bugs, which may show up whenever an

application writes to a file that another application might read.

The worst thing about this kind of bug is that it never seems to show up when you

test your program. It only shows up when your customers use it. The only way I know

to avoid making mistakes like this is to gain lots of experience with multitasking, and

to be fanatically careful about assignments, file i/o, and all other side effects (changes

to shared state). Because this whole class of bugs is caused by side effects, many

re searchers believe that languages without side effects, such as pure Lisp, and

languages like Scheme that encourage programmers to develop a style that uses

relatively few side effects, will be the most practical languages for programming the

powerful multiprocessor systems that are expected in the future.

MacScheme is a registered trademark of Semantic Micro systems, Inc.

MacScheme+Toolsmith is a trademark of Semantic Micro systems, Inc.

===================================================

Figure 1.
(define (unequal1 x . lists)
  (cond ((null? lists) #f)
       ((equal? x (car lists))
        (apply unequal1 (cons x (cdr lists))))
       (else (car lists))))
===================================================
Figure 2.
(begin-tasking)
(define (unequal2 x . objects)
  (let* ((ans #f)
      (task-count (length objects))
      (tasks (map (lambda (y)
             (start-task
              (lambda ()
                (if (not (equal? x y))
                    (begin (set! ans y)
                           (set! task-count 0)))
                (set! task-count (- task-count 1)))))
           objects)))
   (while (> task-count 0)
          (surrender-timeslice))
   (for-each kill-task tasks)
   ans))

Referenced by (14):