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

FotoMagico 6.2.2 - Powerful slideshow cr...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Default Folder X 5.7 - Enhances Open and...
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
f.lux 42.1 - Adjusts the color of your d...
f.lux makes the color of your computer's display adapt to the time of day, warm at night and like sunlight during the day. Ever notice how people texting at night have that eerie blue glow? Or wake... Read more
Spotify 1.1.94.872 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Vitamin-R 4.15 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
OfficeTime 2.0.628 - Easy time and expen...
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
Slack 4.28.182 - Collaborative communica...
Slack brings team communication and collaboration into one place so you can get more work done, whether you belong to a large enterprise or a small business. Check off your to-do list and move your... Read more
DEVONthink Pro 3.8.6 - Knowledge base, i...
DEVONthink is DEVONtechnologies' document and information management solution. It supports a large variety of file formats and stores them in a database enhanced by artificial intelligence (AI). Many... Read more
FileMaker Pro 19.5.4 - Quickly build cus...
FileMaker Pro is the tool you use to create a custom app. You also use FileMaker Pro to access your app on a computer. Start by importing data from a spreadsheet or using a built-in Starter app to... Read more
Backblaze 8.5.0.628 - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac. With unlimited storage available for $6 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more

Latest Forum Discussions

See All

SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for September 26th, 2022. In today’s article, we kick off the week with a bang. And by “bang", I mean four reviews. Family Man, Radiant Silvergun, The Legend of Heroes: Trails from Zero... | Read more »
‘Romancing SaGa: Minstrel Song Remastere...
Following its showing at TGS 2022, Square Enix has released a new gameplay trailer for the previously announced remaster of the PS2 remake of the Super Famicom original (yes) Romancing SaGa game, Romancing SaGa: Minstrel Song Remastered. | Read more »
Gamabilis reveal release date for realis...
Realistic Sims are very fun experiences and give gamers an excellent chance to experience other walks of life, and Gamabilis has released its hyper-real farm management game Roots of Tomorrow. Whilst the more arcade-type games like Stardew Valley... | Read more »
Best iPhone Game Updates: ‘Streets of Ra...
Hello everyone, and welcome to the week! It’s time once again for our look back at the noteworthy updates of the last seven days. We’ve got a nice mix of Apple Arcade, free-to-play, and even a proper paid game. We don’t see those often! So yes, a... | Read more »
The House of Da Vinci 3 launches on Andr...
Following its earlier release on iOS this year, The House of Da Vinci 3 has also officially launched on Android devices. Blue Brain Games' 3D puzzle adventure boasts an average rating of 4.9/5 and will give players the much-awaited conclusion to... | Read more »
‘Oxenfree: Netflix Edition’ Is Out Now o...
Over the weekend, Netflix and Nightschool Studio announced and released Oxenfree: Netflix Edition (Free) worldwide on iOS and Android. This new version of Oxenfree: Netflix Edition is a separate release, and the prior version that I own, is no... | Read more »
‘Genshin Impact’ Version 3.1 Update Pre-...
Genshin Impact (Free) version 3.1 ‘King Deshret and the Three Magi’ goes live in a few days across iOS, Android, PC, PS5, and PS4. As with prior updates, pre-installation for the upcate has just gone live a few days before release. | Read more »
We’re Digging ‘Shovel Knight Dig’ – The...
We spend the bulk of this week’s podcast talking about the new iPhone 14. Specifically, the iPhone 14 Pro Max which both Eli and myself picked up. The consensus seems to be: They’re great! They’re iPhones! We do lay down our hot takes on all the new... | Read more »
TouchArcade Game of the Week: ‘Loose Noz...
There aren’t a lot of stories like that of the development of Loose Nozzles, and of those games that do have an interesting development story, even fewer are actually decent games to play. Loose Nozzles nails both, though. The way it was created is... | Read more »
SwitchArcade Round-Up: ‘Shovel Knight Di...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for September 23rd, 2022. In today’s article, we’ve got the rest of this week’s releases to look at. There are actually a few big games today, including the hot-hot-hot Shovel Knight Dig... | Read more »

Price Scanner via MacPrices.net

13-inch Apple MacBook Airs with M2 processors...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $1099. Shipping is free. Their prices are $100 off Apple’s MSRP, and they are the lowest prices available for M2-powered Macs... Read more
AR Glasses That Work With Apple’s Hardware? T...
NEWS – Lenovo has created quite the spectacle(s) with its latest product. “Apple Glass” — the purported name of Apple’s forthcoming AR glasses — is not expected to be released until 2025 (at the... Read more
New today at Apple: 13-inch M2 MacBook Pros f...
Apple 13″ MacBook Pros with M2 CPUs in stock and available today starting at $1169, Certified Refurbished, and ranging up to $150 off original MSRP. These are the cheapest 13″ M2 MacBook Pros for... Read more
Sunday Sale: 13″ Apple M1 MacBook Air availab...
Amazon has Space Gray Apple 13″ M1 MacBook Airs on sale for $690.95 for an extremely limited time. Other models are on sale for $849. Their price for the Space Gray model is the cheapest we’ve ever... Read more
Use our exclusive Apple Price Trackers to fin...
Our Apple award-winning price trackers are the best place to look for the lowest prices and latest sales on all the latest Apple gear this season. Scan our price trackers for the latest information... Read more
New promo at Verizon: Get Apple Watch Series...
Purchase a new iPhone 14 at Verizon, and get an Apple Watch Series 8 for as low as $5 per month. $120 in promo credits for the Watch are spread over a 36 month term, reducing the price of the Watch... Read more
Visible drops prices on Apple iPhone 13 model...
Verizon’s low-cost wireless cell service, Visible has dropped prices on iPhone 13 models to new low prices starting at $599: – iPhone 13 Pro Max: starting at $980 + free $200 gift card – iPhone 13... Read more
Back in stock! 14″ MacBook Pros with Apple M1...
Amazon has restocked 14″ MacBook Pros M1 Pro CPUs for $400 off MSRP, starting at only $1599. Shipping is free. Be sure to make your purchase from Amazon rather than a third-party seller. Their prices... Read more
This is the final week to take advantage of A...
Apple’s Back to School promotion for 2022 ends on September 26, 2022. As part of this promotion, Apple will include a free $150 Apple Gift Card with the purchase of any MacBook Air, MacBook Pro, or... Read more
Mac Studio with M1 Max CPU back in stock toda...
Apple has the base standard-configuration Mac Studio available again in their Certified Refurbished section for $1799, and it’s in stock today. Each Mac Studio comes with Apple’s one-year warranty,... Read more

Jobs Board

Physician Assistant, Primary Care, *Apple*...
Physician Assistant, Primary Care, Apple Valley (1.07FTE) + Job ID: 65766 + Department: AV Primary Care + City: Apple Valley, MN + Location: HP - Apple Read more
Operations Manager - Mac/ *Apple* Engineerin...
…Responsible for the day-to-day activities relating to the engineering of Apple Macs in a complex, multi-platform environment. Demonstrates strong leadership, Read more
Lead Developer - *Apple* tvOS - Rumble (Uni...
…earnings, and positive sentiment About the role: We are looking for a Lead Apple tvOS Developer to join our application engineering team to expand our video centric Read more
Systems Administrator - *Apple* Devices / J...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Sr Product Manager, *Apple* TV Platforms -...
…an experienced senior product manager to drive the strategy and requirements for our Apple TV devices, acting as the champion and owner of the holistic experience in Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.