Multitask: A Realtime, Multitasking Operating System Emulator

Hal Bredbenner
Raleigh, NC

Most home applications of microprocessors are very basic and straightforward with the micros spending 99% of their existence in loops waiting for a key depression or an interrupt. The majority of systems with interrupts use them just for utilitarian functions such as screen refreshes, clock increments, and keyboard scans. If you have a PET, Apple, Atari, etc., you know how the machine really cannot do more than one operation at a time, and it also has a hard time responding quickly to outside inputs. The BASIC program described by this article emulates a way to allow many seemingly concurrent operations to occur with a fast system response time to the outside world. Keep in mind that this is an emulator. To actually be realized, the concept would have to be written in machine code form; however, the model shows the concept on the screen where it can be analyzed and easily understood.

There are two terms which should be understood before we continue. The first is realtime. An ideal realtime system is one that responds to a changed input immediately. This response will be a change in an output condition or an internal recognition of the input change. Ideally, this response is immediate. However, in reality, some time elapses before the realtime system can respond. The faster the response time, the more efficient the system.

The second term to be defined is multitasking. An ideal multitasking system is one that allows multiple operations to take place simultaneously in one system. Obviously, a single micro can do only one thing at a time, but through scheduling of desired tasks and assigning priorities to each operation, the appearance of more than one action at a time is accomplished.

For example, let's design a hypothetical simple realtime, multitasking system. The system will be a home security system that logs all its data and, upon command from a keyboard, produces a paper tape output of this data. It also has a CRT display and a battery back-up power system. The system must scan various inputs from the house and control outputs which would be interfaced to lights, alarms, and an electric fence. Since the electric fence poses a safety problem (for the good guys!), an Emergency Stop input would be needed. Internal DC power supplies should be monitored to detect system tampering and, if incoming AC power is out of tolerance (for example, a brownout), an alarm should be sounded. Prior to the back-up power system running out, the system should be shut down. When properly programmed, the system should monitor and accomplish all these tasks concurrently (if required) with a fast response time.

Logically breaking down the system software requirements, we can see that some tasks need to be done on a regular basis while others only need to be done upon command from the keyboard or other input. The regular tasks we will call Auto Rescheduling tasks. The tasks are called:

10 DRIVER	Reads inputs and writes outputs
AC PWR CK	Tests incoming AC power
DC PWR CK	Tests internal DC power
READ KYBD	Scans the system keyboard
REFRESH	Refreshes the CRT display

These Auto Rescheduling tasks are regularly performed by the system and scheduled to be done again once they have been completed.

The remaining tasks are to be performed only when an outside input requires them. In our emulation, we can schedule one of these tasks by pressing its number on the numeric keys of the keyboard. In the hypothetical system, they would be initiated by the power fail detect circuitry, the system keyboard, or perhaps the Emergency Stop button. These tasks are called:

E-STOP	Starts an emergency sequence
PWR FAIL	Initiates power down sequence
MOVE FILE	Transfers data to output buffer
MEM TEST	Exercise and test RAM memory
PUNCH DATA	Produces a paper tape

The system would require at least these ten operations and, through the use of the emulator, we can see how the tasks are prioritized, scheduled, and executed.

In our system, we would require one master interrupt signal to drive the entire process. Each time this interrupt occurs, the operating system would perform the same actions. The first action is to read the status of all the system inputs and write, from a RAM buffer area, any new output data. The next action of the operating system (OS) will be to determine if the inputs demand the scheduling of any tasks. For example, let's suppose the person using the system entered a request for a memory test from the keyboard by pressing an "M." The OS would recognize this as a MEM TEST request and read, from a lookup table, three things about the task: the task location, its execution time, and a basic priority value.

The three pieces of data about the task and the time of its request would then be entered into a queue table. This queue table is a list of all the tasks that are scheduled in the system at any one time. When all the required new tasks are entered into the queue, the OS then assigns a calculated priority to each task. This is done in various ways, some extremely complex; however, the most basic way is to make the calculated priority a function of both the task's basic priority and its elapsed time in the queue. This simple calculation is done in our emulator. After a new calculated priority value has been entered into the queue for each pending task, the OS then looks again at the calculated priorities and merely selects the most urgent task, the one with the highest priority, to be performed. The OS then passes control to that task. The selected task runs on the micro until it finishes or another interrupt occurs and, in either case, a return to the OS is made and a new task begun.

An OS like the one we have just described will respond quickly to any input and that is the main design goal for a realtime system.

Notice that if a task is running and another task is calculated to have a greater priority, the first task can be suspended while the more urgent task runs. This can happen if one task has been waiting in the queue for some time while another executing task has most of the processor time. Again, this determination of task suspension can be extremely complex, yet in our emulator it is made solely on the basis of the calculated priorities of the tasks. It also should be noted that because of memory resources, scheduling queues are limited in size. Because of this, any tasks that are requested when the queue is full are ignored and must be requested again later.

To be actually designed in a system, this type of OS requires careful planning. One consideration is the frequency of occurrence of the master interrupt signal. The maximum response time to any input would be one cycle of the interrupt and yet too fast an interrupt will tend to bind the processor down with OS tasks instead of real life tasks. Another consideration is that separate stack pointers should be kept for all active, scheduled, or suspended tasks so that, at any time, resumption of that task's execution will not be ruined by some other task's dealings. The use of a RAM buffer for output storage allows any programmed task to see what is in an output port and, if that RAM output buffer location is changed or modified during next interrupt cycle, the OS will automatically write that new data to the port. This is a good way of synchronizing output and also preventing interference between different program modules.

This emulator program is a model of the operating system required by the hypothetical home security system we talked of earlier. The emulator is written in BASIC and obviously is not as fast as the machine code OS would be. However, the basic design of the OS is graphically shown and is simple to understand. When run, the emulator displays the active task, its time of execution, the average time of response to those tasks in the queue, the entire scheduling queue, and a list of the available system tasks (See Figure 1). The Auto Rescheduling tasks are initially placed in the queue and the OS begins highlighting the active task as it "executes." At any time, by pressing one of the available task numbers (0-3 and 7), a new task will be added to the queue and serviced as the OS permits. The queue in the emulator will hold only 10 entries and then a "QUEUE FULL" response will be given to further inputs. Notice that the Auto Rescheduling tasks are added again to the queue as they are completed. Line 2335 of the program is the algorithm used to calculate the priority of the tasks in the queue. Experimentation with different prioritizing schemes will produce some very interesting results. Try your own algorithm and compare the average response times.

The realtime, multitasking Operating System Emulator given here requires less than 4K of memory and can be run on any Commodore system (most other systems would only require the modification of the cursor positioning characters). It is an excellent tutorial program that graphically shows how some of the most complex OS actually do what they do. Microcomputers can become as powerful as minis and mainframes with this kind of programming. I urge you to try to accomplish this type of OS in machine code. The resulting power of the microprocessor would be amazing.

Program 1.

110 REM MULTITASKER EMULATOR
111 REM WRITTEN BY HAL BREDBENNER
120 REM
130 FOR TN = 0 TO 9
140 READAR (TN), EX (TN), PR (TN), TN$ (TN)
150 NEXT TN
160 DATA 0, 100, 1, "E-STOP ", 0, 100, 1, "PWR FAIL ", 0, 90, 3, MOVE FILE
170 DATA 0, 50, 8, "MEM TEST ", 1, 30, 3, IO DRIVER, 1, 30, 9, AC, PWR, CK 180 DATA 1, 30, 9, DC PWR CK, 0, 90, 7, PUNCHDATA, 1, 30, 2 READ KYBD
190 DATA 1, 30, 3, "REFRESH"
200 REM
210 FOR QN = 0 TO 4
220 READ QT (QN), QT$(QN), QE(QN), QP(QN), QA(QN), QW(QN)
230 PT(QN) = INT ((QW(QN)/QP(QN))*100)
240 NEXT QN
250 DATA 9, "REFRESH ", 30, 2, 1, 0, 8, READ KYBD, 30, 2, 1, 0
260 DATA 6, DC PWR CK, 30, 9, 1, 0, 5, AC PWR CK, 30, 9, 1, 0
270 DATA 4, IO DRIVER, 30, 2, 1, 0
290 PRINT" {CLEAR} {REV} MULTI-TASKING OPERATING SYSTEM EMULATOR"
300 PRINT" {03 DOWN} {REV} SCHEDULER {OFF}
310 PRINT" {14 DOWN} {REV} AVAILABLE TASKS...{DOWN}
320 PRINT" 0- E-STOP      1-PWR FAIL 2-MOVE FILE
330 PRINT" 3-MEM TEST      4-IO DRIVER* 5-AC PWR CK*
340 PRINT" 6-DC PWR CK*    7-PUNCH DATA 8-READ KYBD*
345 PRINT" 9-REFRESH*      *-AUTO RESCHEDULING{02 UP}
350 PRINT" {HOME} {05 DOWN} {REV} TASK NAME{OFF} {REV} TIME LEFT{OFF} {REV} PRIORITY {OFF} {REV} TIME IN QUEUE{OFF}
1000 REM-------------------
1010 REM REAL OPERATING SYSTEM AREA
1020 REM-------------------
1025 Q = 0
1030 GOSUB 2800 : REM ADVANCE ACTIVE TASK
1040 GOSUB 2500 : GOSUB 2700: REM ADVANCE QUEUE
1070 GOSUB 2500 : REM GET TASK AND ADD
1080 IFQE (Q) < 10 THEN 1300
1085 GOSUB 2400 : REM PACK QUEUE TABLE
1090 GOSUB 2500 : GOSUB 2300 : REM DETERMINE HIGHEST
1100 IF PT (XP) > PT(Q) THEN Q = XP
1110 GOSUB 2500 : GOSUB 2000 : GOTO 1030
1300 REM-------------------
1310 REM DELETE FINISHED TASK
1320 REM-------------------
1322 CC = CC + 1 : TC = TC + QW(Q) : AC = INT(TC/CC*100)/100
1325 FT$ = QT$ (Q) + " " + STR$ (AC) + "MSEC."
1330 QTS (Q) = " "
1335 IF QA(Q) = 1 THEN TN = QT (Q) : GOSUB 2570
1337 GOTO 1085
2000 REM------------------------
2010 REM DISPLAY QUEUE 2020 REM-----------------------
2025 GOSUB 2100
2030 PRINT" {HOME} {05 DOWN}
2050 FOR QN = 0 TO 9
2060 IFQTS (QN) = ""THENPRINT" " : GOTO 2080
2065 PRINTTAB (10) " {UP}"
2066 PT (QN) = INT ((QW(QN) / QP (QN)) *100)
2067 IF QN = Q THEN X$ = "{REV}" : GOTO 2070
2068 X$ = "{OFF}"
2070 PRINTX$QT$ (QN) "{OFF}", " " QE(QN), " "PT(QN)," "QW(QN)
2080 NEXT QN
2085 PRINT QF$
2090 RETURN
2100 REM------------------------
2110 REM DISPLAY ACTIVE TASK
2120 REM------------------------
2130 PRINT"{HOME} {02 DOWN} {REV} ACTIVE TASK : {OFF} "QT$ (Q)" {REV} TIME LEFT : {OFF} {09 LEFT} "QE (Q)
2135 PRINTTAB (10) " {REV} AVERAGE RESPONSE : {OFF} {07 LEFT}"AC
2140 RETURN
2200 REM-------------------------
2210 REM    DISPLAY TIME
2220 REM-------------------------
2230 PRINT"{HOME} {04 DOWN} "TAB (27) " {REV} TIME : {OFF} ";
2240 PRINTLEFT$ (TI$, 2) +" : " + MID$(TI$, 3, 2)+" : " + RIGHT$(TI$, 2)
2250 RETURN
2300 REM-------------------------
2310 REM DETERMINE HIGHEST Q PRIORITY
2320 REM-------------------------
2330 X = 0 : FOR QN = 0 TO 9
2333 IF QP (QN) = 0 THEN GOTO 2350
2335 PT (QN) = INT ((QW(QN)/QP (QN))*100)
2340 IFPT (QN)>X THEN X = PT (QN) : XP = QN
2350 NEXT QN
2360 REM EXIT WITH XP = HIGHEST PRIORITY
2370 RETURN
2400 REM-------------------------
2410 REM PACK QUEUE TABLE
2420 REM-------------------------
2430 FOR QN = 0 TO 9
2440 IF QT$ (QN) = " "THEN QT (QN) = 0 : QE (QN) = 0 : QP (QN) = 0 : QA (QN) = 0 : PT (QN) = 0 : QW(Q N) = 0
2450 NEXT QN
2460 FOR QN = 0 TO 9
2470 IF QTS (QN) <> ""THENNEXTQN : GOTO 2490
2480 QTS (QN) = QTS (QN + 1) : QT (QN) = QT (QN + 1) : QE (QN) = QE (QN + 1) : QP (QN) = QP (QN + 1)
2485 QA (QN) = QA (QN + 1) : QW (QN) = QW (QN + 1)
2486 QTS (QN + 1) = ""
2487 NEXT QN
2490 REM TABLE IS NOW PACKED
2495 RETURN
2500 REM------------------------
2510 REM GET TASK AND ADD TO QUEUE
2520 REM------------------------
2525 QF$ = "			"
2530 GET X$ : IF X$ = ""THENRETURN
2535 IF X$ = "4"OR X$ = "5"OR X$ = "6"OR X$ = "8" ORX$= "9"THENRETURN
2540 REM ADD TASK TO QUEUE
2550 IFVAL (X$) <0 ORVAL (X$)> 9 THENRETURN
2560 TN = VAL (X$)
2570 GOSUB2400 : REM PACK QUEUE TABLE
2580 I = 0
2590 IFI < 9 THEN QF$ = "{REV} QUEUE FULL! {OFF} " : GOTO 2620
2595 IF QT$ (I) <> ""THEN I = I + 1 : GOTO 2590
2600 QT (I) = TN : QT$ (I) = TN$ (TN) : QE (I) = EX (TN) : QP(I) = PR (TN) : QA (I) = AR (TN)
2610 QW (I) = 0 : PT (I) = INT ((QW(I)/QP(I)).*100)
2620 GOSUB 2000
2630 RETURN
2700 REM-----------------------
2710 REM INC QUEUE AND PRIORITIES
2720 REM-----------------------
2730 FOR QN = 0 TO 9
2740 IF QT$ (QN) = ""THENNEXT QN : GOTO 2780
2750 QW(QN) = QW(QN) + 1
2760 PT (QN) = INT ((QW(QN) /QP(QN))*100)
2770 NEXT QN
2780 RETURN
2800 REM-----------------------
2810 REM ADVANCE ACTIVE TASK
2820 REM-----------------------
2830 QE (Q) = QE(Q) - 10
2850 PT(Q) = INT ((QW(Q) /QP(Q))*100)
2860 RETURN
READY.

Figure 1.