Features

An Object-Based Real-Time Executive

Michel de Champlain

Michel de Champlain is president of Cnapse, which specializes in C & C+ + training, real-time executives, and reusable software components. He is a faculty member in the Computer Science Department at College Militaire Royal St-Jean. He has an M.S. in computer science and is currently completing a Ph.D. at Ecole Polytechnique, Montreal. You can contact him at Cnapse, 11 Laurier, Suite 102, Chambly, Quebec, Canada J3L 9Z7, (514) 447-7221.

Introduction

The Synapse[1][2] Real-Time eXecutive[3] is a small object-based real-time executive library that is easy to learn and use, where each object is a task. Small real-time systems and device drivers are its main application area.

The concurrent programming model is asynchronous message passing via interrupts. Tasks communicate by sending interrupt messages to handlers (also called methods). This inter-task communication concept is in fact a natural extension of the hardware and software interrupts uniformly available in high-level systemcall facilities. SynRTX also provides dynamic priority and time slice options, along with task identifiers, to allow the control of scheduling and dispatching decisions. SynRTX's actual implementation runs on IBM PCs and compatibles.

SynRTX requires an encapsulation mechanism, which structures an application by separating it into compilation units. The compilation unit (or task unit) describes abstract object type (AOT) that operates by a fixed set of operations (or methods) executed by handlers. A SynRTX real-time application is composed of one or more task units, where each task unit is in a file that defines one task and must be compiled separately.

The name of a task and its handlers are the only exportable entry points. Constants, variables, devices, and handlers are declared and referenced locally (using static class) in the task unit. Modularity in a real-time application in SynRTX is achieved through information hiding, which enforces a rigorous separation between tasks.

Figure 1 shows a task symbol that emphasizes the only visible interface of a task unit: the task name and its handler entry points.

Input/Output In A Multitasking Context

Input and output statements have been implemented in the SynRTX library for three reasons:

Here is an example program. It reads the following three lines of input:

A
65535
Hello!
The example program is:

typedef unsigned short word;
char aChar;
word aWord;
char aString[7];
io_getc (&aChar);
io_getw(&aWord);
io_gets(aString);
*/ aChar  =  'A', aWord = 65535, and aString
   = "Hello!" */
io_puts("\naChar = "); io_putc(aChar);
io_puts("\naWord = "); io_putw(aWord);
io_puts("\naString = "); io_puts(aString);
io_get* statements read items from the keyboard (c for a character, w for a word, and s for a string). An io_get* item is a variable reference. io_put* statements write items to the screen. An io_put* item is an expression or a string constant. There is also a printf equivalent:

io_putf("\naChar = %c aWord = %w aStrin9 = %s",
        aChar, aWord, aString);

Scheduling And Communication

A task is a separate "thread of control" that executes concurrently with other tasks. It is an independent active entity with a collection of statements executed strictly in sequence that goes into action automatically when the task is started. A task ends by executing a task_terminate statement in its body. Concurrent execution of a task is created and scheduled by the task_start statement, with actual parameters if required.

To meet performance requirements, some real-time applications use explicit control over the scheduling and dispatching regime. SynRTX specifies the time slice and the priority of tasks during the creation of a task, a desirable feature in many applications. When dealing with excessive loads, an application needs to control scheduling and dispatching decisions along with dynamic adjustment of priorities and time slices. Listing 1 shows most of the scheduling control statements in one task.

A real-time application must respond to a series of external asynchronous hardware interrupts, which may occur at any time. On the software side, multitasking independently executes tasks that send messages to other tasks via software interrupts. SynRTX supports both hardware and software interrupts, as well as the handlers that serve them. This notion is completely CPU independent. It brings a uniform degree of abstraction to interruptios and handlers. This uniform abstraction is seldom available in traditional operating systems.

Inter-task communication requires that asynchronous tasks be allowed to exchange messages (information) or signals (synchronization only) with each other. SynRTX's concurrent programming model is built around asynchronous message passing via interrupts. Communication between tasks is effected by sending interrupt messages to handlers. This flexibility of this mechanism allows both asynchronous and synchronous message passing. It also offers unidirectional or bidirectional information transfer, where and when required.

Handlers are intended to receive asynchronous interrupt messages. A handler is an interrupt service routine (ISR). It is declared solely in the task unit that it is dedicated to serve. Once an interrupt call has been sent, the handler body is executed to assure mutual exclusion in the body during its execution. Although there are two kinds of handlers, software and hardware, only software handlers can receive parameters from interrupts. A handler behaves like a "critical section procedure." It returns to the point of interrupt when the service is completed.

SynRTX also supports an interface to hardware interrupts. These interrupts are similar to inter-task communication between a driver task and a hardware device task.

Asynchronous inter-task communication is a natural mechanism based on the importance of interrupts in real-time systems. SynRTX offers asynchronous message passing as a general communication construct.

In Figure 2, a single arrow indicates an asynchronous interrupt with no information (data) in the message from the calling task to the interrupted task.

Listing 2 and Listing 3 show a task Receiver that awaits the reception of an interruption from task Sender, via the statement task_enableWait in the task entry of Receiver.

Synchronous of inter-task communication requires a rendezvous between tasks that desire to transfer data unidirectionally or bidirectionally. The sender is blocked until the other task (the receiver) sends back an interrupt. Then both tasks continue.

In Figure 3, a single arrow with a small circle represents an asynchronous interrupt with information (data) in the message.

Listing 5 shows a task Receiver that waits to receive an interruption with data from another task Sender, shown in Listing 4, by means of the task_enableWait statement in Receiver.

Mutual Exclusion Among Tasks

Mutual exclusion among tasks requires that access by asynchronous tasks to the same critical section of code be serialized. When tasks need to update common data, the data may be corrupted if more than one update takes place in parallel. In SynRTX, handlers guarantee mutually exclusive access to global data in a task. A handler guarantees that only one task is active inside a handler at a given time.

Figure 4 shows how mutual exclusion is achieved using handlers. The task Observer (Listing 8) waits for an event, and increments the eventCount in task Update (Listing 7) when it sees one. The task Reporter (Listing 9) waits for a while, then prints and resets the eventCount in the Update task. The task Update is started first to initialize count with the value zero and give fair access to the Reporter and the Observer by rotating interrupt priorities.

Tasks competing for shared devices must synchronize their accesses. Once a resource is acquired by a task, another task claiming the device should be blocked until the owner task releases it. Figure 5 illustrates a basic device driver. Each task must follow the same access protocol: acquire the device, use it, and finally release it.

The task BasicDeviceDriver (Listing 10) blocks itself by the task_enableWait statement when the device is available. The Acquire handler keeps the task identification (the caller) in owner, and acknowledges it by sending an interrupt to the caller's Grant handler. The owner can use the device, and is the sole task that can release it. The Release handler verifies whether the task attempting to release the device is really the owner, then frees the device by assigning NOBODY to the owner. Otherwise, an exception (implemented as a local handler to the server task) is raised to indicate which task does not respect the access protocol.

A Simple Keyboard Device Driver Example

The keyboard device driver shown in Figure 6 is composed of two tasks: a keyboard client and a keyboard server. The server task has five handlers (one hardware and four software).

The Keyboard hardware handler (see Listing 11) serves every keyboard interrupt at vector 9. A hardware interrupt service routine should be as fast as possible, reducing latency to a minimum. You achieve this goal by sending a software interrupt to the keyboard server task itself through Getchar handler, allowing a fast return from the hardware interrupt. The three software handlers Acquire, Release, and Exception support the device driver access protocol explained earlier. Finally, the Hit handler polls the first-in first-out character buffer and returns (via an interrupt) one character to the keyboard client task if the buffer is not empty.

The keyboard client task in Listing 12 is a straightforward server exerciser that repeats forever the following protocol: acquire the keyboard, echo every character typed on the screen, release the keyboard when a character r is hit, and free the server for 10 seconds.

Several keyboard client tasks can be created. These tasks compete for the keyboard trying to acquire it every time they are run. In fact, every keyboard client is a potential "virtual keyboard" that could be (in a windowing application, for example) attached to a specific window.

Conclusion

I have described the SynRTX real-time executive designed on an explicit inter-task communication primitive, the interrupt. The mutual exclusion embedded in handlers is a simple, high- level, and easy-to-build rapid device driver prototype in C (certainly more readable than low-level semaphores). A handler in SynRTX achieves its mutual exclusion because only one task at a time can be running in a handler. Several classical task coordinate problems [1] like readers/writers, bounded-buffer, dining philosophers, event timer, and robot arm controller have been solved elegantly and implemented successfully.

Device driver programming is not easy. SynRTX helps to make application development quicker and reduces the complexity of multitasking. The bottom line is that a task unit implemented as an object operated on by a set of handlers is suitably comprehensive.

References

[1] de Champlain, M., "Synapse: A Real-Time Programming Language," M.S. Thesis, Computer Science Department, Concordia University, September 1989. Synapse is a real-time programming language designed by the author as part of his M.S. Thesis. SynRTX is the library that provides all services needed by the language.

[2] de Champlain, "Synapse: A Small and Expressive Object-based Real-Time Programming Language," ACM SIGPLAN Notices, May 1990.

[3] Cnapse, "SynRTX/PC - Synapse Real-Time eXecutive for the IBM/PC and Compatibles," Programmer's Manual v2.03, August 1990.

Listing 6