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

calibre 4.17.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
MacPilot 11.1.4 - $15.96
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
Transmission 3.00 - Popular BitTorrent c...
Transmission is a fast, easy, and free multi-platform BitTorrent client. Transmission sets initial preferences so things "just work", while advanced features like watch directories, bad peer blocking... Read more
Doom 3 1.3.1 - First-person shooter acti...
A massive demonic invasion has overwhelmed the Union Aerospace Corporation's (UAC) Mars Research Facility, leaving only chaos and horror in its wake. As one of only a few survivors, you must fight... Read more
Box Sync 4.0.8004 - Online synchronizati...
Box Sync gives you a hard-drive in the Cloud for online storage. Note: You must first sign up to use Box. What if the files you need are on your laptop -- but you're on the road with your iPhone? No... Read more
LibreOffice 6.4.4.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Day One 4.14 - Maintain a daily journal.
Day One is an easy, great-looking way to use a journal / diary / text-logging application. Day One is well designed and extremely focused to encourage you to write more through quick Menu Bar entry,... Read more
Doxie 2.12.2 - Scan, share, and store do...
Introducing Doxie, the new, modern paper scanner that's so simple, it'll revolutionize the way you think about sharing and storing docs and photos forever. Doxie is ultra-portable, fully automatic,... Read more
Tinderbox 8.7.0 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
Viber 13.0.0 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more

Latest Forum Discussions

See All

SINoALICE, Yoko Taro and Pokelabo's...
Yoko Taro and developer Pokelabo's SINoALICE has now opened for pre-registration over on the App Store. It's already amassed 1.5 million Android pre-registrations, and it's currently slated to launch on July 1st. [Read more] | Read more »
Masketeers: Idle Has Fallen's lates...
Masketeers: Idle Has Fallen is the latest endeavour from Appxplore, the folks behind Crab War, Thor: War of Tapnarok and Light A Way. It's an idle RPG that's currently available for Android in Early Access and will head to iOS at a later date. [... | Read more »
Evil Hunter Tycoon celebrates 2 million...
Evil Hunter Tycoon has proved to be quite the hit since launching back in March, with its most recent milestone being 2 million downloads. To celebrate the achievement, developer Super Planet has released a new updated called Darkness' Front Yard... | Read more »
Peak's Edge is an intriguing roguel...
Peak's Edge is an upcoming roguelike puzzle game from developer Kenny Sun that's heading for both iOS and Android on June 4th as a free-to-play title. It will see players rolling a pyramid shape through a variety of different levels. [Read more] | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »
The Magic Gladiator class arrives in MU...
The Magic Gladiator class is now available in MU Origin 2 following the most recent patch. It also marks the start of Abyss Season 11 and the introduction of Couple Skills and Couple Dungeons. [Read more] | Read more »
The 5 Best Racing Games
With KartRider Rush+ making a splash this past week, we figured it was high time we updated our list of the best mobile racing games out there. From realistic racing sims to futuristic arcade racers (and even racing management games!), check out... | Read more »
KartRider Rush+ Guide - Tips for new rac...
KartRider Rush+ continues to be a surprisingly refreshing and fun kart racer that's entirely free-to-play. The main reason for this is just how high its skill ceiling is. Check out the video above if you're curious to know what top level play looks... | Read more »
KartRider Rush+ might be good, actually?
It's hard to find good racing games on mobile. Most of them are free-to-play, and free-to-play racers generally suck. Even Nintendo couldn't put together a competent Mario Kart game, opting instead for a weird score chaser that resembles--but feels... | Read more »
LifeAfter, NetEase's popular surviv...
A new map will be making its way into NetEase's popular survival game LifeAfter. The map is set to arrive on May 28th and will introduce a volcano that's teetering on the verge of eruption, bringing a host of added challenges to the game. [Read... | Read more »

Price Scanner via MacPrices.net

Memorial Day Weekend Sale: Take $300 off thes...
Apple resellers are offering $300 discounts on select 16″ MacBook Pros as part of their Memorial Day Weekend 2020 sales. Prices start at $2099: – 16″ 2.6GHz 6-Core Space Gray MacBook Pro: $2099 at... Read more
Best Memorial Day Weekend 2020 Apple AirPods...
Apple resellers are offering discounts ranging up to $50 off MSRP on AirPods as part of their Memorial Day Weekend 2020 sales. These are the best deals today on various AirPods models. See our... Read more
Memorial Day Weekend Sale: 10″ Apple iPads fo...
Amazon is offering new 10.2″ iPads for $80-$100 off Apple’s MSRP as part of their Memorial Day Weekend 2020 sale, with prices starting at only $249. These are the same iPads sold by Apple in their... Read more
Memorial Day Weekend Sale: 2020 Apple iPhone...
Sprint is offering Apple’s new 2020 64GB iPhone SE for $0 per month for 18 months as part of their Memorial Day Weekend 2020 sale. New line of service and trade-in required. Offer is valid from 5/22/... Read more
Amazon’s popular $100 Apple Watch Series 5 di...
Amazon has Apple Watch Series 5 GPS + Cellular models on sale for up to $100 off Apple’s MSRP today. Shipping is free. These are the same Apple Watch models sold by Apple in their retail and online... Read more
2020 13″ 4-Core MacBook Air on sale for $949,...
Apple reseller Adorama has the new 2020 13″ 1.1GHz 4-Core Space Gray MacBook Air on sale today for $949 shipped. Their price is $50 off Apple’s MSRP, and it’s the lowest price currently available for... Read more
Apple Retail Chief Announces Staggered Reopen...
NEWS: 05.20.20 – In the midst of a global pandemic, after its retail outlets were shuttered temporarily in mid-March as a mitigation measure enacted by Apple during the peak of the spread of COVID-19... Read more
Apple’s Pro Display XDR models in stock today...
Abt Electronics has Apple’s new 32″ Pro Display XDR models in stock and on sale today for up to $305 off MSRP. Shipping is free. Their prices are currently the lowest available for these new models... Read more
Apple restocks refurbished iPhone 8 for $339
Apple has restocked Apple Certified Refurbished 64GB iPhone 8 models for only $339. Apple dropped their price on this phone last month by $160, from $499 to $339. Each refurbished iPhone comes with a... Read more
New at AT&T: 50% off iPhone 11 for new cu...
AT&T is offering a 50% off the 64GB iPhone 11 for new customers who switch to AT&T and open a new line of service. Discount applied over a 30 month period The fine print: “iPhone 11 64GB for... Read more

Jobs Board

Cub Foods - *Apple* Valley - Now Hiring Par...
Cub Foods - Apple Valley - Now Hiring Part Time! United States of America, Minnesota, Apple Valley New Retail Operations Post Date 5 days ago Requisition # Read more
Senior Data Engineer - *Apple* - Theorem, L...
Job Summary Apple is seeking an experienced, detail-minded data engineeringconsultant to join our worldwide business development and strategy team. If you are Read more
Cub Foods - *Apple* Valley - Now Hiring Par...
Cub Foods - Apple Valley - Now Hiring Part Time! United States of America, Minnesota, Apple Valley New Retail Operations Post Date 4 days ago Requisition # Read more
Medical Screener - *Apple* Hill - Evenings...
Medical Screener - Apple Hill - Evenings Tracking Code D-MS-AH-E Job Description Medical Screener - Temporary We Are Hiring: WellSpan Health has a temporary Medical Read more
*Apple* Systems Administrator - Solidus Tech...
Solidus is searching for an Apple Systems Engineer. The engineer will be responsible for desktop and server infrastructure. This includes support for operating Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.