TweetFollow Us on Twitter

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)
n
>>> (define (loop1)
      (set! n (+ n 1))
      (loop1))
loop1
>>> (define t1 (start-task loop1))
t1

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)
#t
>>> 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 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

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

Community Search:
MacTech Search:

Software Updates via MacUpdate

Bookends 12.8 - Reference management and...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more
Adobe Creative Cloud 4.0.0.185 - Access...
Adobe Creative Cloud costs $19.99/month for a single app, or $49.99/month for the entire suite. Introducing Adobe Creative Cloud desktop applications, including Adobe Photoshop CC and Illustrator CC... Read more
Default Folder X 5.1.4 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
Amazon Chime 4.1.5587 - Amazon-based com...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more
Persecond 1.0.9 - Timelapse video made e...
Persecond is the easy, fun way to create a beautiful timelapse video. Import an image sequence from any camera, trim the length of your video, adjust the speed and playback direction, and you’re done... Read more
CrossOver 16.2 - Run Windows apps on you...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
MegaSeg 6.0.2 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
Apple iTunes 12.6 - Play Apple Music and...
Apple iTunes lets you organize and stream Apple Music, download and watch video and listen to Podcasts. It can automatically download new music, app, and book purchases across all your devices and... Read more
GraphicConverter 10.4 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
OpenEmu 2.0.5 - Open Source game-emulati...
OpenEmu is about to change the world of video game emulation, one console at a time... For the first time, the 'It just works' philosophy now extends to open source video game emulation on the Mac.... Read more

Orphan Black: The Game (Games)
Orphan Black: The Game 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dive into a dark and twisted puzzle-adventure that retells the pivotal events of Orphan Black. | Read more »
The Elder Scrolls: Legends is now availa...
| Read more »
Ticket to Earth beginner's guide: H...
Robot Circus launched Ticket to Earth as part of the App Store's indie games event last week. If you're not quite digging the space operatics Mass Effect: Andromeda is serving up, you'll be pleased to know that there's a surprising alternative on... | Read more »
Leap to victory in Nexx Studios new plat...
You’re always a hop, skip, and a jump away from a fiery death in Temple Jump, a new platformer-cum-endless runner from Nexx Studio. It’s out now on both iOS and Android if you’re an adventurer seeking treasure in a crumbling, pixel-laden temple. | Read more »
Failbetter Games details changes coming...
Sunless Sea, Failbetter Games' dark and gloomy sea explorer, sets sail for the iPad tomorrow. Ahead of the game's launch, Failbetter took to Twitter to discuss what will be different in the mobile version of the game. Many of the changes make... | Read more »
Splish, splash! The Pokémon GO Water Fes...
Niantic is back with a new festival for dedicated Pokémon GO collectors. The Water Festival officially kicks off today at 1 P.M. PDT and runs through March 29. Magikarp, Squirtle, Totodile, and their assorted evolved forms will be appearing at... | Read more »
Death Road to Canada (Games)
Death Road to Canada 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: Get it now at the low launch price! Price will go up a dollar every major update. Update news at the bottom of this... | Read more »
Bean's Quest Beginner's Guide:...
Bean's Quest is a new take on both the classic platformer and the endless runner, and it's free on the App Store for the time being. Instead of running constantly, you can't stop jumping. That adds a surprising new level of challenge to the game... | Read more »
How to rake in the cash in Bit City
Our last Bit City guide covered the basics. Now it's time to get into some of the more advanced techniques. In the later cities, cash flow becomes much more difficult, so you'll want to develop some strategies if you want to complete each level.... | Read more »
PixelTerra (Games)
PixelTerra 1.1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1.1 (iTunes) Description: The world of PixelTerra is quite dangerous so you need to build a shelter, find some food supply and get ready to protect... | Read more »

Price Scanner via MacPrices.net

SSD Speeder RAM Disk SSD Life Extender App Fo...
Fehraltorf, Switzerland based B-Eng has announced they are making their SSD Speeder app for macOS publicly available for purchase on their website. SSD Speeder is a RAM disk utility that prevents... Read more
iPhone Scores Highest Overall in Smartphone D...
Customer satisfaction is much higher among smartphone owners who use their device to operate other connected home services such as smart thermostats and smart appliances, according to the J.D. Power... Read more
Swipe CRM Free Photo-Centric CRM Sales DEal C...
Swipe CRM LLC has introduced Swipe CRM: Visual Sales 1.0 for iPad, an app for creating, managing, and sharing visually stunning sales deals. Swipe CRM is targeted to small-and-medium creative... Read more
13-inch 2.0GHz Apple MacBook Pros on sale for...
B&H has the non-Touch Bar 13″ 2.0GHz MacBook Pros in stock today and on sale for $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (... Read more
15-inch Touch Bar MacBook Pros on sale for up...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Apple’s iPhone 6s Tops Best-Selling Smartphon...
In terms of shipments, the iPhone 6s from Apple bested all competitors for sales in 2016, according to new analysis from IHS Markit, a world leader in critical information, analytics and solutions.... Read more
Logitech Rugged Combo Protective iPad Case an...
Logitech has announced its Logitech Rugged Combo, Logitech Rugged Case, and Logitech Add-on Keyboard for Rugged Case for Apple’s new, more affordable $329 9.7-inch iPad, a complete solution designed... Read more
T-Mobile To Offer iPhone 7 and iPhone 7 Plus...
T-Mobile has announced it will offer iPhone 7 and iPhone 7 Plus (PRODUCT)RED Special Edition in a vibrant red aluminum finish. The introduction of this special edition iPhone celebrates Apple’s 10... Read more
9-inch 128GB iPad Pros on sale for $50-$70 of...
B&H Photo has 9.7″ 128GB Apple WiFi iPad Pros on sale for up to $70 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 9″ Space Gray 128GB WiFi iPad Pro: $649 $50... Read more
27-inch iMacs on sale for up to $200 off MSRP...
B&H Photo has 27″ Apple iMacs on sale for up to $200 off MSRP, each including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2099 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $... Read more

Jobs Board

*Apple* Retail - Multiple Positions- Chicago...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
Starte Dein Karriere-Abenteuer in den Hauptst...
…mehrsprachigen Teams betreust Du Kunden von bekannten globale Marken wie Apple , Mercedes, Facebook, Expedia, und vielen anderen! Funktion Du wolltest schon Read more
*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.