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

NTFS 15.0.911 - $19.95
NTFS breaks down the barriers between Windows and macOS. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS. Write, edit, copy, move, delete files on NTFS... Read more
Airfoil 5.6.3 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
ExpanDrive 6.0.16 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Smultron 9.4.2 - Easy-to-use, powerful t...
Smultron 9 is an elegant and powerful text editor that is easy to use. Use it to create or edit any text document. Everything from a web page, a note or a script to any single piece of text or code.... Read more
Typinator 7.3 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
coconutBattery 3.6.4 - Displays info abo...
With coconutBattery you're always aware of your current battery health. It shows you live information about your battery such as how often it was charged and how is the current maximum capacity in... Read more
iShowU Instant 1.2.0 - Full-featured scr...
iShowU Instant gives you real-time screen recording like you've never seen before! It is the fastest, most feature-filled real-time screen capture tool from shinywhitebox yet. All of the features you... Read more
TrailRunner 3.8.1840 - Route planning fo...
TrailRunner is the perfect companion for runners, bikers, hikers, and all people wandering under the sky. Plan routes on a geographical map. Import GPS or workout recordings and journalize your... Read more
NetShade 7.1 - Browse privately using an...
NetShade is an anonymous proxy and VPN app+service for Mac. Unblock your Internet through NetShade's high-speed proxy and VPN servers spanning seven countries. NetShade masks your IP address as you... Read more
1Password 6.8.2 - Powerful password mana...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more

Thimbleweed Park (Games)
Thimbleweed Park 1.0.0 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.0 (iTunes) Description: A brand new adventure game from Ron Gilbert and Gary Winnick, creators of the classics Monkey Island and Maniac Mansion!... | Read more »
The best simulation games on mobile
There's nothing like a good sim -- from the seemingly ridiculous to the incredibly mundane, you can be there's a simulation game out there for your every whim. [Read more] | Read more »
INKS guide - how to create works of pinb...
INKS puts a clever new spin on everyone's favorite classic arcade game, pinball. The core mechanics are the same -- keep a little ball pinging around the board for as long as possible without letting it fall into the precarious holes in the board.... | Read more »
Warbands: Bushido (Games)
Warbands: Bushido 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: Warbands:Bushido is a miniatures board game with cards, miniatures, dice and beautiful terrains to fight on, with both... | Read more »
The best mobile games like Divinity: Ori...
Divinity: Original Sin 2 launched this week to the excitement of RPG fans everywhere. The game, which derives a lot of of its story and mechanics from old-school isometric RPGs and Dungeons & Dragons, has unseated PlayerUnknown's... | Read more »
Iron Marines guide - beginner tips and t...
Iron Marines is a brilliant RTS title that feels a bit like Starcraft. It's got a sci-fi setting and some of the most spectacular strategy mechanics we've seen in mobile games to date. With that said, the RTS genre can be a bit tricky to break... | Read more »
The best new games we played this week -...
The work week can be tough, but on the bright side, it's almost overandthere are bunches of brand new games to try out this weekend. This week definitely makes up for last week's sleepiness ten-fold. We've got one of the finest RTS game on mobile... | Read more »
Through the Ages (Games)
Through the Ages 1.0.60 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.60 (iTunes) Description: The offical adaptation of Vlaada Chvátil’s strategy classic, the second best board game ever by Board Game Geek website... | Read more »
The best RTS games like Iron Marines
Iron Marines launched today, and it's definitely taking the mobile gaming world by storm. In fact, our reviews editor Campbell says it's "quite possibly the best real-time strategy game on the App Store." If you're looking for more real-time... | Read more »
Uri: The Sprout of Lotus Creek (Games)
Uri: The Sprout of Lotus Creek 1.0.5 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.5 (iTunes) Description: Published by Fantastic Games IntroductionDesigned by DreamTree Games(An indie games studio in Malaysia ) | Read more »

Price Scanner via MacPrices.net

12-inch and 9-inch Apple iPad Pros, Certified...
Apple has Certified Refurbished 2016 12″ WiFi iPad Pros available starting at $589. An Apple one-year warranty is included with each model, and shipping is free: – 32GB 12″ iPad Pro WiFi: $589... Read more
QuickerTek Announces Solar PV Chargers for US...
Wichita, Kansas based QuickerTek has announced its new 30 Watt and 60 Watt USB Type-C Solar Juicz Chargers. These solar panels are the only products of their kind, featuring the USB 3.1 adapter cable... Read more
Apple refurbished 128GB iPhone 6s and 6s Plus...
Apple has Certified Refurbished 128GB iPhone 6s and 6s Plus’ available for up to $100 off the price of new models. Space Gray, Silver, Gold, and Rose Gold models are available. Each phone comes... Read more
13-inch 2.3GHz Silver MacBook Pros on sale fo...
B&H Photo has 2017 13″ 2.3GHz Silver MacBook Pros in stock today and on sale for $100 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Silver... Read more
12-inch 64GB iPad Pros available for $749, $5...
MacMall has 12″ 64GB iPad Pros on sale for $749 including free shipping. Their price is $50 off MSRP. Read more
Sunday deal: 10-inch 256GB iPad Pros for $699...
MacMall has 10.5″ 256GB WiFi iPad Pros on sale today for $699 including free shipping. That’s $100 off MSRP. Read more
2017 12-inch 1.2GHz Retina MacBooks on sale f...
Amazon has 2017 12″ 1.2GHz Retina MacBooks on sale for $100 off MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $1199 $100 off MSRP 12″ 1.2GHz Silver MacBook: $1199 $100 off MSRP 12″ 1.2GHz... Read more
Apple Certified Refurbished 21-inch and 27-in...
Apple is now offering a full line of Certified Refurbished 2017 21″ and 27″ iMacs. Models start at $1019 and range up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is... Read more
Apple now offering Certified Refurbished 2017...
Apple is now offering Certified Refurbished 2017 12″ Retina MacBooks for up to $240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free... Read more
Steve Jobs’ Democratization Of The Smartphone...
Can it be only ten years since Steve Jobs introduced the world to the iPhone and changed everything? Jobs and Apple didn’t invent the smartphone. IBM designed a primitive one called SIMON in 1992,... Read more

Jobs Board

*Apple* Solutions Consultant - Apple Inc. (U...
…about helping others on a team while also delighting customers? As an Apple Solutions Consultant (ASC), you will discover customers needs and help connect them Read more
Software/Data Engineer, *Apple* Media Produ...
Job Summary Apple Media Products is the team behind the App Store, Apple Music, iTunes, and many other high profile products on iPhone, Mac and AppleTV. Our Data Read more
SW Engineer , *Apple* Media - Apple Inc. (U...
Job Summary Our team is responsible for exposing Apple Media content and services to the world, and building the infrastructure for next generation internal and Read more
*Apple* Data Center Site Selection and Strat...
Job Summary As Apple 's products and services scale the globe, the Data Center Affairs team works behind the scenes to secure infrastructure for Apple 's data Read more
*Apple* Professional Learning Specialist - A...
Job Summary The Apple Professional Learning Specialist is a full-time position for one year with Apple in the Yuma, AZ area. This position requires a high Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.