TweetFollow Us on Twitter

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))
>>> (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
>>> n
>>> n
>>> n

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

>>> n
>>> n
>>> (kill-task t1)
>>> n
>>> n

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 concurrent 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

  (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 researchers 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 Microsystems, Inc. MacScheme+Toolsmith is a trademark of Semantic Microsystems, 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.

(define (unequal2 x . objects)
  (let* ((ans #f)
      (task-count (length objects))
      (tasks (map (lambda (y)
              (lambda ()
                (if (not (equal? x y))
                    (begin (set! ans y)
                           (set! task-count 0)))
                (set! task-count (- task-count 1)))))
   (while (> task-count 0)
   (for-each kill-task tasks)

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniOutliner Essentials 5.3 - Organize y...
OmniOutliner Essentials (was OmniOutliner) is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually... Read more
OfficeTime 1.8.2 - Easy time and expense...
OfficeTime is time and expense tracking that is easy, elegant and focused. Other time keepers are clumsy or oversimplified. OfficeTime balances features and ease of use, allowing you to easily track... Read more
Dash 4.1.6 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Civilization VI 1.1.0 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
Network Radar 2.3.3 - $17.99
Network Radar is an advanced network scanning and managing tool. Featuring an easy-to-use and streamlined design, the all-new Network Radar 2 has been engineered from the ground up as a modern Mac... Read more
Quicken 5.5.6 - Complete personal financ...
Quicken makes managing your money easier than ever. Whether paying bills, upgrading from Windows, enjoying more reliable downloads, or getting expert product help, Quicken's new and improved features... Read more
Civilization VI 1.1.0 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
Network Radar 2.3.3 - $17.99
Network Radar is an advanced network scanning and managing tool. Featuring an easy-to-use and streamlined design, the all-new Network Radar 2 has been engineered from the ground up as a modern Mac... Read more
Printopia 3.0.8 - Share Mac printers wit...
Run Printopia on your Mac to share its printers to any capable iPhone, iPad, or iPod Touch. Printopia will also add virtual printers, allowing you to save print-outs to your Mac and send to apps.... Read more
ForkLift 3.2.1 - Powerful file manager:...
ForkLift is a powerful file manager and ferociously fast FTP client clothed in a clean and versatile UI that offers the combination of absolute simplicity and raw power expected from a well-executed... Read more

Latest Forum Discussions

See All

Construction Simulator 2 reaches its fir...
Construction Simulator 2 debuted iOS and Android devices exactly one year ago, and publisher Astragon is marking the game’s first anniversary with a range of time-limited discounts. It’s been a successful debut for the civil engineering sim, which... | Read more »
All the best games on sale for iPhone an...
This week's list of games on sale for the iPhone and iPad isn't too bad really. There's some gems on here, as well as some games that have had their prices cut low enough that you can look past the rough edges and questionable decisions. [Read... | Read more »
The best games that came out for iPhone...
It's not a huge surprise that there's not a massive influx of new, must-buy games on the App Store this week. After all, GDC is happening, so everyone's busy at parties and networking and dying from a sinister form of jetlag. That said, there are... | Read more »
Destiny meets its mobile match - Everyth...
Shadowgun Legends is the latest game in the Shadowgun series, and it's taking the franchise in some interesting new directions. Which is good news. The even better news is that it's coming out tomorrow, so if you didn't make it into the beta you... | Read more »
How PUBG, Fortnite, and the battle royal...
The history of the battle royale genre isn't a long one. While the nascent parts of the experience have existed ever since players first started killing one another online, it's really only in the past six years that the genre has coalesced into... | Read more »
Around the Empire: What have you missed...
Oh hi nice reader, and thanks for popping in to check out our weekly round-up of all the stuff that you might have missed across the Steel Media network. Yeah, that's right, it's a big ol' network. Obviously 148Apps is the best, but there are some... | Read more »
All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming Device: iOS Universal Category: Games Price: $1.99, Version: (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »

Price Scanner via

Apple restocks clearance 2016 13-inch MacBook...
Apple has Certified Refurbished 2016 13″ MacBook Airs available starting at $809. An Apple one-year warranty is included with each MacBook, and shipping is free: – 13″ 1.6GHz/8GB/128GB MacBook Air: $... Read more
Thursday roundup of the best 13″ MacBook Pro...
B&H Photo has new 2017 13″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only. Their prices are the lowest available for... Read more
Sale: 9.7-inch 2017 WiFi iPads starting at $2...
B&H Photo has 9.7″ 2017 WiFi Apple iPads on sale for $40 off MSRP for a limited time. Shipping is free, and pay sales tax in NY & NJ only: – 32GB iPad WiFi: $289, $40 off – 128GB iPad WiFi: $... Read more
Roundup of Certified Refurbished iPads, iPad...
Apple has Certified Refurbished 9.7″ WiFi iPads available for $50-$80 off the cost of new models. An Apple one-year warranty is included with each iPad, and shipping is free: – 9″ 32GB WiFi iPad: $... Read more
Back in stock! Apple’s full line of Certified...
Save $300-$300 on the purchase of a 2017 13″ MacBook Pro today with Certified Refurbished models at Apple. Apple’s refurbished prices are the lowest available for each model from any reseller. A... Read more
Wednesday deals: Huge sale on Apple 15″ MacBo...
Adorama has new 2017 15″ MacBook Pros on sale for $250-$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): $... Read more
Apple offers Certified Refurbished Series 3 A...
Apple has Certified Refurbished Series 3 Apple Watch GPS models available for $50, or 13%, off the cost of new models. Apple’s standard 1-year warranty is included, and shipping is free. Numerous... Read more
12″ 1.2GHz Space Gray MacBook on sale for $11...
B&H Photo has the Space Gray 12″ 1.2GHz MacBook on sale for $100 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 12″ 1.2GHz Space Gray MacBook: $1199 $... Read more
Mac minis available for up to $150 off MSRP w...
Apple has restocked Certified Refurbished Mac minis starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: – 1.4GHz Mac mini: $419 $80 off MSRP – 2.6GHz Mac... Read more
Back in stock: 13-inch 2.5GHz MacBook Pro (Ce...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros (MD101LL/A) available for $829, or $270 off original MSRP. Apple’s one-year warranty is standard, and shipping is free: – 13″ 2.5GHz MacBook... Read more

Jobs Board

*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113587340 Hialeah, Florida, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
Art Director, *Apple* Music + Beats1 Market...
# Art Director, Apple Music + Beats1 Marketing Design Job Number: 113258081 Culver City, California, United States Posted: 07-Mar-2018 Weekly Hours: 40.00 **Job Read more
*Apple* Manager - Retail Manager - Apple, In...
Job Description: Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as an Apple Retail Manager, you're a master of them Read more
*Apple* Watch HW Engineering Program Special...
# Apple Watch HW Engineering Program Specialist Job Number: 113466877 Santa Clara Valley, California, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Read more
*Apple* Media Products (AMP) Engineering Man...
# Apple Media Products (AMP) Engineering Manager Job Number: 86497853 Santa Clara Valley, California, United States Posted: 07-Mar-2018 Weekly Hours: 40.00 **Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.