The Art of

Chapter Nineteen (Part 8)

Table of Content

Chapter Nineteen (Part 10)

19.4 - Multitasking
19.4.1 - Lightweight and HeavyWeight Processes
19.4 Multitasking

Coroutines provide a reasonable mechanism for switching between processes that must take turns. For example the maze generation program in the previous section would generate poor mazes if the daemon processes didn't take turns removing one cell at a time from the maze. However the coroutine paradigm isn't always suitable; not all processes need to take turns. For example suppose you are writing an action game where the user plays against the computer. In addition the computer player operates independently of the user in real time. This could be for example a space war game or a flight simulator game (where you are dog fighting other pilots). Ideally we would like to have two computers. One to handle the user interaction and one for the computer player. Both systems would communicate their moves to one another during the game. If the (human) player simply sits and watches the screen the computer player would win since it is active and the human player is not. Of course it would considerably limit the marketability of your game were it to require two computers to play. However you can use multitasking to simulate two separate computer systems on a single CPU.

The basic idea behind multitasking is that one process runs for a period of time (the time quantum or time slice ) and then a timer interrupts the process. The timer ISR saves the state of the process and then switches control to another process. That process runs for its time slice and then the timer interrupt switches to another process. In this manner each process gets some amount of computer time. Note that multitasking is very easy to implement if you have a coroutine package. All you need to do is write a timer ISR that cocalls the various processes one per timer interrupt A timer interrupt that switches between processes is a dispatcher.

One decision you will need to make when designing a dispatcher is a policy for the process selection algorithm. A simple policy is to place all processes in a queue and then rotate among them. This is known as the round-robin policy. Since this is the policy the UCR Standard Library process package uses we will adopt it as well. However there are other process selection criteria generally involving the priority of a process available as well. See a good text on operating systems for details.

The choice of the time quantum can have a big impact on performance. Generally you would like the time quantum to be small. The time sharing (switching between processes based on the clock) will be much smoother if you use small time quanta. For example suppose you choose five second time quanta and you were running four processes concurrently. Each process would get five seconds; it would run very fast during those five seconds. However at the end of its time slice it would have to wait for the other three process' turns 15 seconds before it ran again. The users of such programs would get very frustrated with them users like programs whose performance is relatively consistent from one moment to the next.

If we make the time slice one millisecond instead of five seconds each process would run for one millisecond and then switch to the next processes. This means that each processes gets one millisecond out of five. This is too small a time quantum for the user to notice the pause between processes.

Since smaller time quanta seem to be better you might wonder "why not make them as small as possible?" For example the PC supports a one millisecond timer interrupt. Why not use that to switch between processes? The problem is that there is a fair amount of overhead required to switch from one processes to another. The smaller you make the time quantum the larger will be the overhead of using time slicing. Therefore you want to pick a time quantum that is a good balance between smooth process switching and too much overhead. As it turns out the 1/18th second clock is probably fine for most multitasking requirements.

19.4.1 Lightweight and HeavyWeight Processes

There are two major types of processes in the world of multitasking: lightweight processes also known as threads and heavyweight processes. These two types of processes differ mainly in the details of memory management. A heavyweight process swaps memory management tables and moves lots of data around. Threads only swap the stack and CPU registers. Threads have much less overhead cost than heavyweight processes.

We will not consider heavyweight processes in this text. Heavyweight processes appear in protected mode operating systems like UNIX Linux OS/2 or Windows NT. Since there is rarely any memory management (at the hardware level) going on under DOS the issue of changing memory management tables around is moot. Switching from one heavyweight application to another generally corresponds to switching from one application to another.

Using lightweight processes (threads) is perfectly reasonable under DOS. Threads (short for "execution thread" or "thread of execution") correspond to two or more concurrent execution paths within the same program. For example we could think of each of the demons in the maze generation program as being a separate thread of execution.

Although threads have different stacks and machine states they share code and data memory. There is no need to use a "shared memory TSR" to provide global shared memory (see "Shared Memory"). Instead maintaining local variables is the difficult task. You must either allocate local variables on the process' stack (which is separate for each process) or you've got to make sure that no other process uses the variables you declare in the data segment specifically for one thread.

We could easily write our own threads package but we don't have to; the UCR Standard Library provides this capability in the processes package. To see how to incorporate threads into your programs keep reading...

Chapter Nineteen (Part 8)

Table of Content

Chapter Nineteen (Part 10)

Chapter Nineteen: Processes Coroutines and Concurrency (Part 9)
29 SEP 1996