Real Time Operating System “OSCAR”

In 1969 I worked at an industrial research laboratory designing factory automation systems using mainly TTL IC hardware. I was interested in doing some of this work in software using the newly emerging mini-computers. To come up to speed I studied at night for a Masters degree in computer science at the University of NSW (UNSW) in Sydney, Australia.

As part of this course, I designed and programmed a “Real-Time Operating System” for programming Real-Time Control Systems. It was called a Monitor at the time. The first version of this program was implemented on a PDP-8 minicomputer in the Electrical Engineering department of the university. Afterwards, I ported the software to a Data General NOVA mini-computer for my then employer (which was not a good idea I discovered later). I gave the system the acronym OSCAR for Operating System CSR Automation Research.

For the 50th anniversary, I obtained a PDP-8/I kit from Oscar Vermeulen in Holland, which works beautifully. The kit has an exact facsimile of a PDP-8/I front panel with working switches and lights. In the back is a Raspberry Pi running the SIMH PDP-8 emulator software with all major PDP-8 system programs on a simulated RK05 disc. I was able to reconstitute all the OSCAR sources from printouts I have and assemble and run it all, as I did 50 years ago (see PDP-8 sources).

The main impetus for doing this work came from a publication by Digital Equipment Corporation – INTRODUCTION TO PROGRAMMING PDP-8 Family Computers published in 1968. A scanned version of this book is available, but there are many scanning mistakes and program texts are jumbled. Nevertheless, I was able to reconstitute the two programs below from this source.

This book contains two versions of the same program. The first version is called Sample Program (SAMPLE.PA) on pages 5-17.

Sample Program

The previously described routines for typing text and numeric translation are combined in the following program example which is similar to the final program of Chapter 3. This program performs the same numeric sort; however, the numbers to be placed in order are supplied from the keyboard.
Any number of elements may be supplied; the end of input is signalled by typing a dollar sign ($). The program includes routines to exclude any non-octal digits from input and type a question mark. Only positive octal numbers (0-3777) are allowed as input to the program. 

The program is presented in four illustrations. The following flowchart diagrams the program. 

This version has a Keyboard input routine called LISN and an output routine called TYPE, both of which use busy loops for waiting for completion of the input or output as follows:

LISN,	0	        / INPUT SUBROUTINE       
	KSF	        / TEST INPUT DONE
	JMP .-1	        / BUSY WAIT
	KRB	        / GET CHARACTER
	TLS	        / ECHO CHARACTER
	JMP I LISN

TYPE,   0               / OUTPUT SUBROUTINE
        TSF	        / TEST DONE
        JMP .-1	        / BUSY WAIT
        TLS	        / PRINT CHARACTER IN AC
        CLA
        JMP I TYPE

LISN is called once to accept a character and TYPE is called numerous times in different parts of the program to build up a clear algorithm.

The 2nd version (SAMPLI.PA) on pages 5-32 uses TTY keyboard and TTY output interrupts and is described as follows:

Program Interrupt Demonstration Program 

The program presented in Figures 5-16A through 5-16F is a demonstration program to run on the program interrupt facility. It contains a bit rotating program, the speed and direction of which is determined by the switch register settings. (This same program is presented in Exercise 10 of Chapter 3.) The foreground program is the ordering program which was given in Figure 5-14. This program has the capacity to accept 4-digit positive octal input from the Teletype keyboard, automatically terminating each 4-digit number with a carriage return and line feed. Upon receipt of a typed dollar sign ($), the program  will place the data in increasing order, and type the ordered data on the printer. The program will not accept negative numbers or non-octal digits. 

The example is useful as a demonstration and illustration of the power of program interrupt as the computer will seem to be performing two tasks at the same time. The programmer knows that this is not possible and that the two tasks are sharing the computer time; however, the appearance indicates simultaneous actions. 

The following flowchart shows that the implementation is completely different to the simple 1st version with busy wait I/O.

The whole algorithm is embedded in the interrupt handler and is structured as a state machine using 4 state variables MODE, SW1, SW2 and SW3. The functionality of the program is completely hidden and it would be very difficult to modify – like adding another task or another device. The sorting is done in the interrupt handler, which means if the sort takes a significant amount of time, no other devices could be serviced during sorting.

For what it is worth, the above program has a serious bug. Unless you enter at least 2 numbers, TALLY in the sorting section does not start with a negative value and the algorithm will sort the whole of memory, including the Disk Operating System code in high memory, thereby trashing it and itself.

Real-Time Operating System OSCAR (OSCAR8.PA)

When I studied the above interrupt handling version in 1969 I decided to follow a different strategy to implement the core of a simple Real-Time Operating System. It was based on a task structure – each task representing a virtual CPU. Each task has a Task Control Block (TCB), which can store the main registers of the CPU plus a number of useful memory locations. For the PDP-8 these include the PC, Link and Accumulator as well as an initial PC, which sets the starting point for each task. Tasks can be in one of three states:

1. ACTIVE – a task is active when a central processor is executing instructions in a program belonging to the task, or shared with other tasks and with data also belonging to the task, or shared with other tasks. To mark this state the address of the currently active TCB is stored in a known location (ATP).
2. READY – a task is in this state when it is ready to use a central processor but is not active because higher priority tasks or system programs are using all physical processors. The registers of this task are saved in its TCB.
3. SUSPENDED – a task is in the suspended state whenever it must wait for the occurrence of an event. Such an event may be the completion of an Input/Output operation or the execution of one of the synchronising macro-instructions in another task which can re-activate a task.

The modified sample program SAMPL8.PA, which runs with interrupts under OSCAR, only needs two functions from OSCAR – GET a character (RKGET) and PUT a character (RTPUT). These use the OSCAR primitives WAIT for an event and POST an event:

RKGET,	0
	IOF             / DISABLE INTERRUPTS
	JMS I WAIT      / WAIT FOR AN EVENT
	KECW            / KEYBOARD EVENT CONTROL WORD
	KRB		/ READ CHARACTER (no echo)
	JMP I RKGET     / CHARACTER RETURNED IN AC

RTPUT,	0		/ CHARACTER PASSED IN AC
	IOF
	JMS I WAIT      / WAIT FOR AN EVENT
	TECW            / TTY OUTPUT EVENT CONTROL WORD
	TPC		/ PRINT CHARACTER IN AC
	CLA
	JMP I RTPUT

The RKGET and RTPUT are very similar to LISN and TYPE in SAMPLE.PA. The two busy loop statements are replaced by the WAIT call, which has an EVENT CONTROL WORD address as a parameter. These are the only difference between SAMPL8.PA and SAMPLE.PA. When running SAMPL8 it must be loaded after OSCAR8 as an overlay to add the extra task to the task queue as follows:

.R ABSLDR
*OSCAR8,SAMPL8/G

WAIT and POST are linked by an EVENT CONTROL WORD (ECW), which can be in one of 3 states:

1. ZERO (0) – the event has not happened yet and no task is waiting for this event.
2. Address of a TCB – the event has not happened yet, but the task pointed to by the TCB is suspended, waiting for the event.
3. ALL ONES (7777) – the event has happened, but no task is waiting for this event.

When a WAIT call is executed the ECW parameter is tested. If the event has already occurred (7777), the call returns immediately after setting the ECW to 0. If the ECW is 0 (event has not yet happened) the TCB address of the currently active task is stored in the TCB and the task is marked SUSPENDED in the Task Queue. This is followed by a scan of the Task Queue and the next highest priority READY task on the queue is made ACTIVE by transferring the state of registers, including the PC in its TCB to the hardware registers.

When an event occurs, POST is called, which tests whether a task is waiting or not. If the ECW is 0 (or 7777), no task is waiting and 7777 is stored in the ECW followed by a return. Otherwise, a task is waiting. The task pointed to by the TCB address in the ECW is made READY on the Task Queue. This is also followed by a scan of the Task Queue and the highest priority task on the queue is made ACTIVE. When the task just posted becomes active, it will start executing just after the WAIT call which caused the task to be suspended.

There are two entry points to the POST routine in OSCAR. One for events in a task and the other for events generated in an interrupt handler. The modified program SAMPL8.PA only uses the latter, which is part of the OSCAR code and is normally not touched by application programmers:

/ INTERRUPT SERVICE
INTS,	DCA I ATP	/ SAVE ACCUMULATOR IN TCB
	KSF		/ IS IT TTY IN ?
	JMP TSFT	/ NO
	KCC		/ YES - CLEAR FLAG (ALSO AC)
	JMS IPOST       / POST THE EVENT
	KECW            / KEYBOARD EVENT CONTROL WORD
 
TSFT,	TSF		/ IS IT TTY OUT ?
	JMP UINT	/ NO
	TCF		/ YES - CLEAR FLAG
	JMS IPOST       / POST THE EVENT
	TECW            / TTY OUTPUT EVENT CONTROL WORD

UINT,	HLT		/ UNKNOWN INTERRUPT
	JMP RTI

The only actions in the interrupt handlers are to clear the relevant hardware flags and to POST the ECW’s waited for in RKGET and RTPUT, which are also part of OSCAR, which means interrupt handling is completely hidden. The actual interrupt handlers and drivers in OSCAR also deal with the high-speed paper tape reader and punch in a nearly identical way. Other devices could be added very easily.

The concept of WAIT and POST routines was inspired by the IBM OPERATING SYSTEM/360 as described in “Programming Systems and Languages”, ed Saul Rosen, 1966, p. 639. That book describes this facility as follows:

Event synchronization is the delaying of task execution until some specified event occurs. The synchronization has two aspects.

• The requirement for synchronization is stated explicitly by the WAIT routine.
• After the event has occurred, notice to the requesting task is given so it can proceed past the WAIT point.

The notification required is performed by the POST routine. When the event is known to the control program (for example the completion of a read operation), the control program issues the POST. If the event is known only to the user’s program, the user’s program must issue it.

All these aspects have been implemented in OSCAR8. Another form of event synchronization is possible, which allows “cooperating” tasks to share certain resources defined by the user. Rather than use the ENQ and DEQ primitives defined in OPERATING SYSTEM/360, OSCAR8 implements Semaphores as described by E.W. Dijkstra in his seminal paper “Cooperating Sequential Processes” in Programming Languages, ed F. Genuys, 1968, p. 67:

Semaphores are essentially non-negative integers. When used only to solve the mutual exclusion problem the range of their values is restricted to “0” and “1”. These are called binary semaphores. There are many applications for semaphores with larger values, which are known as general semaphores.

Apart from initialisation, only two operations are allowed on semaphores: LOWER and RAISE (Dijkstra calls them P and V, which are the first letters of lower and raise in Dutch).

LOWER and RAISE are linked by a SEMAPHORE BLOCK, which has the following structure:

COUNT,  0
LINK,   0

• The LOWER operation decrements COUNT by 1. If COUNT remains positive or zero (>= 0) this operation returns immediately. If COUNT becomes negative (<0) the task making the call SUSPENDS, first linking the address of its own TCB to the end of a list starting with the semaphore LINK. The negative COUNT records the number of tasks suspended on the semaphore.
• The RAISE operation increments COUNT by 1. If COUNT remains positive (not zero) (> 0) this operation returns immediately. If COUNT becomes zero or remains negative (<= 0) one or more tasks are suspended on the semaphore. The task pointed to by the TCB at the top of the LINK list is made READY. The LINK list entry is also removed.

The zero or positive count of a general semaphore may be used as a counter for recording the amount of a resource controlled by it – e.g. the number of blocks held by a buffer linking two tasks. When that semaphore is LOWERED from 1 to 0 the buffer becomes empty. When LOWERED again the task blocks, because you cannot obtain a block from an empty buffer.

The small application TEST8.PA has a high priority task, which allows you to enter the digits 1, 2 or 3 at the keyboard without echo (entering any other character returns control back to OS/8). Each of the 3 inputs POSTS a different EVENT CONTROL WORD, which are WAITED for in 3 other lower priority tasks. These tasks print out a line of 120 1’s, 2’s or 3’s each followed by a CR LF. The lines are each printed in a mutually exclusive section guarded by a common semaphore. This means that if two different characters are typed before a line has finished printing, the printing is blocked until one line has been completely printed. A feature of this application is, that the program for the 3 printing tasks is the same – it is re-entrant. Only the TASK CONTROL BLOCKS differ. This demo worked well with a slow teleprinter. The SIMH emulation output is so fast, that it is hard to enter a second character before a 120 character line has been output. One way to do it is to type a sequence e.g. 132321 in another window, mark it with the mouse and left mouse button and then paste it into the pidp8i window with the middle mouse button. The output will be:

1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
2222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222
3333333333333333333333333333333333333333333333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333

TEST8 must be loaded and run as follows:

.R ABSLDR
*OSCAR8,TEST8/G

The full text of A MONITOR FOR REAL-TIME  CONTROL SYSTEMS, the Masters’ Thesis from 1972, has a more extensive implementation of OSCAR on the Data General NOVA computer.

Debug Task

An important application implemented for the NOVA version of OSCAR is a debugger running as a task in parallel with any factory control applications. The need for such a debugger in the control environment was very important because conventional debuggers do not work well in an environment with interrupts. The PDP-8 debugger ODT cannot be used at all with interrupts turned on.

DEBUG TASK may be linked in with OSCAR systems to provide an online debugging facility. It uses the Teletype for input and output. If the Teletype is also required by other tasks the semaphore SENDT defined in DEBUG TASK provides mutual exclusion of the Teletype as a facility in different tasks. Unless output is taking place through the Teletype in another task, the Teletype keyboard is always receptive to DEBUG TASK commands. These follow the standard pattern of Nova Debug programs. Any memory location may be inspected and/or modified. A sequence of memory locations may be searched for a particular word after it is masked. This operation also allows the listing of a sequence of memory locations. A Breakpoint may be entered at any memory location. Since DEBUG TASK is always active with other tasks this may be done even when the system has been set running. When the Breakpoint instruction is executed the task mode of operation is frozen and DEBUG TASK is run as a stand-alone program. This means that the instantaneous description of all other tasks which includes all variables and also private registers in TCB’s may be inspected and modified. Because of the logical processor concept of tasks this scheme makes debugging of real-time systems very tractable. The task mode may be resumed with the continue operation of DEBUG TASK.

This dual-mode of DEBUG TASK makes it a very powerful debugging tool. To the user, the action of most operations looks the same, whether DEBUG TASK is in task mode or at a breakpoint. The inspection of variables, while a system is running, is particularly useful. For example, the register which stores the value from an A/D converter may be monitored at any time without first stopping at a breakpoint. This is important when a system is controlling a factory process. It is then undesirable to stop the system. DEBUG TASK allows effective debugging even in this situation. The following is a case study of a typical debugging session.

By observation of the behaviour of certain variables and by inspection of the program listing it was determined that a control algorithm was faulty. This became evident because one control loop in a system containing a number of control loops was unstable. The system was running online and the unstable behaviour was not severe enough to warrant a shutdown. A modification to the control algorithm program was written and checked on paper to make reasonably sure that it would work. Then the modification was entered into a spare section of the computer memory as a patch. The memory modifying function of DEBUG TASK was used for this purpose. The whole patch was typed in and checked while the rest of the system operated with the old algorithm.

Then a statement in the control algorithm was overwritten with a branch instruction to the patch. The next execution of that algorithm then executed the patch. The effect of the patch may then be observed. If the action of the patch makes the system worse the branch instruction is again overwritten with the old instruction. This restores the old algorithm. If the patch causes wild operation then the system will of course crash. But this kind of modification was carried out repeatedly on an online system and very few mistakes were made. The final operation, if a patch is successful, is to list it and also to punch out a binary tape of the patch. This may again be done while the rest of the system is online.

Conclusion

The time involved in planning and coding the first version of OSCAR took 4 months during the latter part of 1970. During the next 2 years, a number of modifications to the system were made. In particular Semaphores and Double-Ended Queues were added. Experience with the system has shown that it is easily picked up by programmers. The functions, particularly the synchronising primitives, are at first unfamiliar but with a little practice, they are used as intended. Thus parallel programming as against uni-programming comes naturally to most programmers when a task structured system such as OSCAR is available to them. There is still a certain amount of resistance to going all the way with the parallel approach. Programmers traditionally join their real-time jobs into a sequence that is polled at regular intervals – the ubiquitous event loop. In the parallel approach, each job would be coded as a separate task with its activation tied precisely to the occurrence of events, which do not have to be polled.

This early work with computer-controlled automation systems using an interrupt-driven real-time operating system strongly influenced the later work with immediate C, in which every input event produces an immediate action initiated by an interrupt, rather than by polling inputs in an event loop, which is the common way of handling events in software systems today.