Classic Computer Magazine Archive CREATIVE COMPUTING VOL. 11, NO. 1 / JANUARY 1985 / PAGE 96

Teaching your computer to juggle; this program will make your Apple II into a multitasking system. Robert A. Quinn.

It never fails. You spend three months creating your "Monster That Ate Cincinnati" game. Everyone loves it, but someone always asks, "Can't you put two monsters in there?" or three, or eighteen. But being the simple beast that it is, the actual processor can handle only one task at a time. It can go fast enough, however, to appear to be doing many things simultaneously. The multitasking system (don't let the word scare you) described here will let you program your computer to "jungle" several tasks at once.

Why is it necessary, or even desirable, to do such a thing? After all, many programs get away without multiasking, and it does tie up some computer time with overhead. What are the advantages?

Take, for example, the problem of adding another monster to munch on Cincinnati. With the "straight line" method of programming games, adding this new code is a great deal of boring work involving tables and pointers. The multitasking system (from now on, I'll call it a job system) makes it a tenminute, one-reassembly job! Or how about adding printer spooling to that text editor you have been working on and never worrying about missing a keystroke or dropping a character.

Here's how it's done. First, let's take a look at the flow of a typical program. Structured programming, modularity, and the like aside, many programs execute in a long loop as shown in Figure 1. Notice I said execute; even though the program may make many detours, at one time or another it usually goes back to the top and starts over again.

As the program gets longer and more complex, it becomes difficult to understand. Errors can easily creep in, and the program loses its modularity and clarity. The job system can help this proglem by breaking the long loop into a series of smaller connected loops.

For example, Listing 1 is an English language version of a program to move a dot across the screen. It is pretty straightforward. But what happens if we decide to move to dots? Well, the program in Listing 2 is one way to do it--probably not the best. It takes twice as much code and spends a great deal of time waiting around, not to mention how diffucult it would be to add another dot. Another way is the program shown in Listing 3. The dot positions are arranged in an array, and the program steps through them one at a time, plotting each dot, waiting, erasing, and moving it. But it still wastes a lot of time.

What if we used that time to plot the other dots? With just a little rearrangement of Listing 3 you will have a program that wastes very little time. This program is shown in Listing 4. If you trace this program you will notice that it plots dot 1, then plots dot 2, then 3, and so on until all the dots (N) have been plotted. It then waits just once, instead of N times, for the dots to be seen. After the wait, the program erases, moves and plots dot 1, then dot 2 all over again.

Look at the subroutine WAIT. It doesn't really wait at all. It goes ahead and plots the next dot. Then, when all the dots have been plotted, it restarts at the top and does them all again. Also notice that the array index is changed each time. This is very important. The same little loop of code is actually doing N dots at once.

Big deal, you say, "anyone can write a program loop that works off an array." The important thing is that the loop executes with different data each time. Those data are kept separate from the other executions of the loop.

In fact, as long as the data are kept separate, it doesn't matter what kind of program loop is executed. You can have one program loop plotting dots, another checking the keyboard, another calculating pi, or whatever else you want.

For example, let's add the data array used in Listing 4. In addition to the x and y coordinates, we'll also keep track of the program counter. Why? Because then you can leave off at any point in the program, return to the same place later on, and pick up where you left off. But in the meantime the processor can be off doing other tasks (hence the name multitasking). Adding Different Program Loops

Now look at the program in Listing 5. Here we have added a second program loop. If, for example, you set N to 1 and jump to LEFTLOOP, you will get a dot moving to the left. If you then set N to 2 and jump to RITELOOP you will have a dot moving to the right and a dot moving to the left (the other loop is still running). Try it out.

You can have one dot going left and N-1 going right or three going right and N-3 going left. Or any combination you like. (You don't have to move dots with all the jobs. Instead of x and y, and data can be pointers, addresses, dates, or anything else). The WAIT routine (some people like to call it a supervisor or a task manager) moves a pointer to the next block of data, extracts the previously saved program counter and jumps to it. The loop then uses its own personal data from its data block.

All you have to do is write your program in small modular loops, and somewhere in the loop call the WAIT subroutine. WAIT will save your program counter, get the next data block, get the next program counter, execute from where that job loop left off, and return to you when all the other job loops have executed. Design

Listing 6 illustrates a practical version of the job system for an Apple, although the principles can be used for any processor. Starting at the variable definitions, here is how it works.

If you look around line 34 of Listing 6, you will see a section called job data block equates. Our old friends PC, X, and Y are there along with some others (LO and HI are used to access 16-bit quantities 8-bits at a time). A status byte stands at the beginning of each block of data. Status is used mainly to determine whether its data block is in use or not. This way, when a job loop finishes using a data block, it can release the block for some other job loop to use. The job routines use only bit 0 of the status byte; all the others are free for the job loop to use for data.

The counter byte lets you skip execution of a job loop. For most jobs, the counter is set to 1, and they execute on every pass. But, if you have one job that is not very important or depends on some relatively infrequently changing data (say, the keyboard), just set the counter byte to 2, and it will be executed every other time through. Or set it to 8 to have it executed every eight time.

These four bytes (PCLO, PCHI, STATUS, COUNTER) are the only ones necessary for the job routines to work properly. All the others are just data bytes, and you can add or delete them as you please. I have added some extra bytes to save the x and y positions, (XPOS, YPOS) and also the velocities (XVEL, YVEL) of the dots. These are not important to the functioning of the job subroutines. It is important that the length of job data block be correct. Put in or take out bytes as you will, but the routines use JOBLEN to determine the starting address of the next job data block. Figure 2 shows how the memory looks to the job system.

Notice also that the bytes in the job are defined as offsets. There are no absolute addresses here. Everytime WAIT returns to a job loop, a variable called JOBPTR points to the top of its data block. The offsets are used to get data from the data block. JOBPTR + 0 points to the status byte; JOBPTR + 1 points to the low byte of the saved program counter; and so on. This allows the indirect indexed addressing mode of the 6502 to access the data. You just load register Y with the offset of the byte in the data block you need and LDA (JOBPRT), Y to get a byte or STA (JOBPRT), Y to store a byte in the data block.

If you wanted to increment the Y coordinate of some dot, it would go like this: Load the offset of the data block byte you want into register Y. Load the accumulator with the Y coordinate using indirect indexed addressing mode. Increment the accumulator and store it back in the same place using indirect indexed addressing again. It is quite simple once you get the hang of it. Multitasking and the Real World

There are some things to watch out for when using a system like this.

1. The loop must call the WAIT for subroutine somewhere. If the program loop branches to Guatemala or goes into an infinite loop, none of the other jobs will ever be executed.

2. Since there may be many users of one small piece of code, each job loop must have its own private variables. I usually just extend the data block until I have more than I can use (by making the equate JOBLEN bigger). This sometimes leads to inefficient memory usage.

3. While any job loop can use the stack as much as it pleases, no loop can leave anything on the stack (or in the registers, either) and expect it to be there when control returns after calling WAIT. Unfortunately, this means you can't call WAIT from a subroutine, as your return address won't be on the stack when you come back. (The routines could be written to include a stack for each job.) The Routines

The following is a brief description of how the routines in the listing work.

INITJOB (line 265) is a simple routine that initializes all the job data blocks not used. It does this by zeroing the status byte of the data block. It is usually called before any jobs are used to make sure all the data blocks are free and to prevent job routines from using a data block that has garbage in it.

GETJOB (line 405) is the routine that finds the first unused data block in the data block area. It does this by starting at the top of the data block area and looking for a zero status byte (Figure 3). When it finds one, it marks the data block as used by setting the bit 0 of the status byte (all of the other bits are available to the user). It then stores the starting address of the job loop (passed in the two-byte variable JOBTEMP) in the job data block and sets the computer byte to 1 so the job will be executed next time through (Figure 4). The address of the data block is returned in JOBTEMP so the calling routine can initialize other parts of the data block if it wants to.

When your job has done its job and you want to stop it from ever executing again (when one of the space invaders gets shot by the player, for example) you simply call ZAP. ZAP zeroes the jobs status byte so it becomes a free data block, then executes the next job. Even though ZAP is called like a subroutine, it never returns to the caller.

If you want to stop all the jobs call ZAPALL. ZAPALL differs from INIT.JOB in that it zaps all the jobs except the job that called it. This is very convenient at times. When one of the space invaders shoots the player, for example, the player's job can call ZAPALL to stop all the space invaders' jobs. The player's job will still execute--to decrement his lives left or maybe start a new rack. (ZAPALL does return to the caller.)

All the job system routines call ERROR if there are problems. ERROR is an infinite loop that stops all the jobs from executing, making the program freeze. You can find the offending routine by looking at the top two bytes of stack. (The error that occurs most often is the "trying to run 21 job loops when there are only 20 job data blocks available" error.)

The WAIT (line 333) routine is the key to the whole system. This routine saves the program counter of the calling job, gets the next data block, retrieves the program counter from the new data block, and jumps to it. This is how it works. WAIT expects the number of passes to skip execution in the accumulator. The first thing it does is store this count in the job data block. It also expects the program counter on the stack. This is automatically done when WAIT is called as a subroutine. WAIT pulls the program counter off the stack and stores it in the job data block. This completes saving the state of the current job (Figure 5).

Now WAIT looks for the next active job data block. It does this by adding the length of the job data blocks (JOBLEN) to the address of the current job data block (JOBPTR). It then checks to see if this address is beyond the end of the job area. If it is, then it jumps to LASTJOB to reset the pointer to the beginning of the job area and starts again. If the job address is valid, WAIT checks to see if this job block is being used (status not equal to 0).

If the job data block is active, WAIT decrements the skip counter. If the skip counter is not zero (or the job is inactive) WAIT will go to NEXTJOB to try the next job data block in the list.

When the counter is 0, WAIT fetches the program counter of this job from the data block and pushes it onto the stack. It then does an RTS to jump to the job and start it running. We can't do a regular indirect jump here because of the way the 6502 handles subroutine calls. A 6502 indirect jump would land us one byte short of the place we wanted to go. Also using an RTS avoids the infamous 6502 indirect-jump-on-a-page-boundary bug. Some Sample Jobs

Starting on line 75 Listing 6 shows an example of one way to use the job system. In the example, every time the Apple paddle 0 button is pressed a dot travels from left to right across the screen. Every time the paddle 1 button is pressed a dot travels the opposite way. Dots can be generated as fast as you can press the buttons--and remember each dot is a separate task. If you press the spacebar, the jobs will all be stopped by ZAPALL, and after a short delay, the screen will be erased.

Let's take a look at how it works. The whole things begins at BEGIN (line 75). After some preliminary setup of the stack and clearing the screen, the program initializes all the job data blocks to zero with INITJOB. It then starts a job called FIREDOT and jumps to LASTJOB to start the job system running. FIREDOT checks the keyboard and the paddle buttons. If a key was pressed, it checks to see if it was the spacebar. If it was a space, it kills all the jobs (except itself, of course), waits a short time, (illustrating how to use WAIT to delay one job while the rest run unimpeded), clears the screen and resumes checking.

TRYFIRE checks to see if either paddle button has been pressed. Paddle button 0 causes a jump to FIRELEFT, paddle button 1 to FIRERIGHT. These segments are identical except for the velocities given to the dots. They also show how to pass parameters to job loops. BUTDOWN checks for the release of both paddle buttons before returning to the checking loop.

DOTPLOT and VELOCITY are just the implementations of the routines discussed before. They erase the dot, move it, plot it, and call the WAIT routine (actually NEXT, which just a WAIT 'til next time through).

So there you have it. Although the example shown is small, it illustrates a powerful tool you can use to make your programming job faster and easier.