Dojo (HowTo)







  Easter Eggs




  Martial Arts

How does MultiTasking Work?
Scheduling basics

By:David K. Every
©Copyright 1999

MultiTasking is pretty basic stuff. Think of it like a debate or congress. You have a bunch of windbags that all want to get in their two cents (or a bunch of programs that all want to share the attention of the processor -- and each wants their turn. In the case of the Politicians it is because it makes them feel important and so they can dupe the public into thinking that they are actually doing something productive -- in the case of programs, it is so that they can all appear to be running at the same time, because dozens or hundreds of times a second, they are getting a small amount of time to do something. So how do you manage it?

Cooperative assumes that they will all follow the rules. You know, if you made a debate/speaking rule where after 5 minutes you relinquish the floor to someone else. Of course this works very well and efficiently if people follow the rules. But one pompous windbag who won't obey (or one bad program), and you have to hear them out and wait until they are done.

Preemption has a more formal scheduler (moderator), to say, "Now it is your turn". When the 5 minute timer goes off, the scheduler pulls the power from the Windbag's mic. (or pounds his gavel until the big-mouth shuts up) and you go on to the next person. Or of course the scheduler program yanks control (the processor) away from one program, and gives control to another -- kinda like watching T.V when you get that message, "Congratulations, your favorite show (processor time) has been preempted so that you can tune into more of the Clinton Trials".

So it all sounds pretty easy. Technically, if people (programs) are paying attention to all the rules, then Cooperative could theoretically have less overhead (time wasted by the moderator / scheduler themself). Functionally, because the moderator is doing the switching, and because some people (programs) don't pay attention to the rules, the Preemptive model allows for more switching. More switching means that each Application (speaker) gets more turns (which are smaller), so things run smoother. Engineering is always about tradeoffs.

It's all as clear as a frosted glass

So now it seems clear right? In practical circumstances the moderated debate, or preemptive scheduler, is smoother and allows for finer granularity (more turns) so everything runs better (smoother) -- right? Well in theory. Once again that comes crashing into the walls of reality.

WindowsNT has a prioritized scheduler (as many preemptive schedulers do), which means that Applications decide what priority they are. This is like giving certain important people more time to speak than others -- which makes sense, since I really care about what some people have to say more than others. The problem is that it is those people that decide how important they are. Do you see a problem? Joe Windbag comes up and decides that he is really, really important, and schedules his priority accordingly, and he gets more time than others. Guess what? That pompous person (Application) still gets more time than anyone else. Usually the next person comes along and decides that he is just as important as the last guy, so bumps up his priority, and so on. So even preemptive schedulers require cooperation and good behavior. Bad Applications (Speakers) still hog more time than others, and do rude things -- just not quite as often.

There are many flavors of Unix. Some basically just give everyone a fixed amount of time -- whether they need it or not. They don't have a lot of Application setable prioritization. But many times you want things to have different amounts of time - the forground Application (the one with the user interface), you probably want to get more time so that it is fast and responsive. Even if you are running so many things that the background Applications are "bogging down" (running slower), you want the frontmost App to pig out on the processor a little, so that the App you are working with is always responsive. And some background tasks really only need a minimal amount of time (or almost none). Giving all of them a fixed amount of time, isn't perfect either. They need to know when to give up their time to someone else -- preemptively scheduled or not -- so they need to cooperate as well.

Any system of scheduling has holes where you are either wasting time, someone is pigging out on time when they shouldn't, or someone will not be of the right priority. That is life. Despite all that, having the moderator is still better than complete anarchy, most of the time. But either way, it is still up to the quality of the Applications (people in the debate) to follow rules. You are always at the mercy of the lowest common denominator. But in a best case situation a good cooperative debate (or scheduler) COULD go better than a worst case moderated debate (preemptive scheduler).

Clearer Still

So who is what? What System uses what type of scheduling?

NT has a Preemptive Scheduler -- but they let each Application decide what priority they are at. It is a mediocre implementation of scheduling that isn't too bad, but isn't that great as well. It also does some quirky things with some lower level parts. Some flavors of Unix are better, and usually Unix is more a forced prioritization scheme, so the System itself decides that all pigs are equal (except for the System Resources and Party Members themselves, which usually get preferred treatment) -- just think of Communism and the Communist Party Members.

Win98 gets very tricky. It has a preemptive scheduler (but a pretty hacky implementation), unless you are one of the many legacy 16 bit Applications that is left around (like any DOS or Win3.1 Application and most games). Then each of those Apps have to cooperate and give up time, and can either hold everyone else up, or only hold up all the other 16 bit Applications (depending on type of App and many other variables). Since it was these older 16 bit Applications that have the biggest problem with "not playing well with others", it is like saying, "we'll have a moderator, except for the really immature and over emotional people". In best conditions it works alright, in some conditions it does not.

Mac OS is greyer still. It has a very small preemptive scheduler (called a NanoKernel -- which implies very small) that will schedule interupts and some low level tasks. This is used so that drivers (software that talks to devices like the keyboard, mouse, serial ports, etc.) always get the needed amount of time.

The User Interface part of Mac Applications is Cooperative -- sort of. A program has to give up time to others -- but it does that by just trying to find out what the next thing it has to do is. Every time a program tries to see if the mouse has been moved or the keyboard touched, or a menu selected or any event has happened (which they need to do all the time), the System gives time to other Apps. The OS can even change the amount of time that is given over to other Apps to help "tune things" and make sure Apps are getting a more fair share (1). Plus, just calling some System calls besides the WaitNextEvent() call (which you do a lot in the Mac) can give the System a chance to give others their fair share of time (2). This would be like allowing a speaker to talk as long as they want, but as soon as you take a breath or check their notes, the other guys get their chance to butt-in and take over. It is sort of a Forced Cooperative System.

(1) Copland had an interesting Dynamic Tuning capability. Where if you didn't give up enough time, or too much, it would just sort of change your code so that you worked better. I think some of that has leaked into Mac OS 8, but I'm not 100% sure.

(2) In the Mac OS I think there is currently on one or two other calls besides WaitNextEvent() that will give time to others. But they are there. Apple could add more, and make the Mac OS more and more forced cooperative.

But wait, there's more. Mac Applications can spin off low level preemptive threads (TimeManager or VBL Tasks) to do some things. So for example, if you want to download something in the background like compress, decompress, print, do a filter, render or compile and so on (the most likely background type of tasks), you can spawn part (or all) that functionality into one of these low-level preemptive tasks. The Interface may be held up while some piggy App pontificates, but as soon as the App gets it's time again, it turns out his page (assistant) has been doing research, preparing his notes, and basically been helpful during all that time.

These tasks are annoyingly low-level, and a tad more difficult to work with than higher-level tasks in other systems -- but they work. And it would probably only add like 2 - 5% more work in an Application overall to develop them right. The problem is that too few are actually using them well.

The fact is that many parts of the Mac are Preemptive, and many parts of Windows are not (and other parts are often just a really poor implementation). The fact that you can Force-Quit (Option-Command-Escape) a Mac Application that is "hung" (poorly behaving) proves that at least some parts of the OS are being run preemptively. Of course the Mac has some ugly parts as well (like some programs that use out-of-date Mac Toolbox routines that won't release time until completed -- even when there are better routines available).


Both machines at the mercy of bad Applications. Just the Mac is slightly more so than Windows -- but I think Windows has more bad Application to make up for it. Internet Explorer is a great example of this on the Mac -- it makes itself faster by not releasing as much time to other programs as it should (even when it is in the background). If you are only running that one App, it doesn't really matter. But if you try to do something like compile in the forground while just having Explorer running in the background, your machine slows down an amazing amount. But I think it does about the same thing on Windows by just bumping it's priority up -- effectively doing the same thing (or it could).

In general, I think the Win95/Win98 scheduler works slightly better than the current Mac Scheduler over all (or at least in the best case). But it is very slight advantage, and it only applies if you are running all well behaved 32 Bit Apps. Once you throw in bad Apps, of which there are many, it kinda goes to hell. I've had many more problems with serious performance degradation or ugly artifacts with Windows Apps. So much so that it is my opinion that while I believe that a great configuration of Windows95/98 will just barely out-perform a great configuration of Mac, I also know that on average it is almost undecernable, and a bad configuration of both seems to have Windows behaving far worse than a similar Mac.

The whole point of this article is just to give a very basic explanation of how MultiTasking and Scheduling works in general and on various platforms. In a later article I can go into the more technical and specific explanations.

Created: 12/19/98
Updated: 11/09/02

Top of page

Top of Section