Operating Systems

A Non-Preemptive Multitasking Executive In C++

Michel de Champlain

Michel de Champlain is president of Cnapse, which specializes in C & C++ training, real-time programming and reusable software components. He is a faculty member in the Computer Science department at College Militaire Royal St-Jean. He has a MS in computer science and is completing a PhD at Ecole Polytechnique, Montreal. He can be contacted at Cnapse, 11 Laurier, Suite 102, Chambly, Qc, CANADA J3L 9Z7, tel: (514) 447-7221, fax: (514) 447-7297.

This article focuses on designing and implementing a non-reemptive multitasking executive using the object-oriented features of C++. I've tested this implementation on an AT clone using Zortech C++ v2.0 (small model). One source file must be in assembly language to implement context switching between tasks.

Object-oriented Versus Procedural

Object-oriented design (OOD) represents a different way of thinking compared to the classical procedural approach. OOD focuses on the data to be manipulated rather than on the procedures that do the manipulating. So the data forms the basis for the software decomposition. In OOD, an abstract data (or object) type is a class that defines a type and an associated set of operations. These operations characterize the behavior of the underlying type. OOD is not top down — the resulting classes are more independent and easier to reuse. One of the nicest aspects of OOD is the extensibility of object types through inheritance. The original class remains untouched as new functionality is added in a derived type. Basic classes are general object types that can easily be reused for many extensions of a design.

Non-preemptive Multitasking Executive

I've presented an executive that is a multitasking, non-reemptive kernel with a cooperative scheduling discipline. Tasks pass control from one to another much like relay runners pass the baton. A task continues to run until it calls ReSchedule. This function saves the tasks's context, determines the next running (active) task, and transfers control to the new running task.

Executive Services

One of the executive's primary functions is overseeing the execution of tasks that make up a multitasking application. The executive offers many services, also named system calls. These include:

• Start - Create and schedule a task to run.
• Terminate - Delete the specified task (or itself).
• ReSchedule - Move the running task onto the ready queue, complete every detail of scheduling and context switching, select a new task to run, move it from the ready queue, mark it running, and finally, restore the context of the new task.
• Suspend - Suspend execution of the specified task (or itself). A suspended task will not resume execution until a Resume is issued. This method starts the rescheduling method if the running task suspends.
• Resume - Resume execution of the specified task (previously suspended). This method starts the rescheduling method.
• Self - Return the running task identification.
• Parent - Return the task identification of the task's parent (creator).

Besides these system calls, the specification also includes:

• Schedule - Schedule is a method private to the executive that encapsulates the scheduling algorithm. Packaging it as a method lets you change the scheduling algorithm without affecting the rest of the executive.

Task States And State Transitions

In a multitasking application based on this executive, tasks exist in one of four states: Running, Ready, Suspended or Terminated:

• Running - The task has control of the CPU and is executing.
• Ready - The task is ready for execution but cannot gain control of the CPU (enter the Running state) until a task in the Running state passes control to it by terminating or suspending.
• Suspended - The task suspends in mid-xecution and waits to be readied by a Resume call.
• Terminated - The task is not yet started or its execution is complete.

Figure 1 shows all the state transitions and how system calls change states.

The C+ + Implementation

Every state is an object, and all transitions are methods (system calls). The first base class in the executive is StateQ (Listing 4) , an abstract class that hides all the doubly linked list management functions. An instance of the class StateQ contains a First-n First-ut (FIFO) queue that can be accessed by the insert method. Another method called transfer allows the executive to remove a task from any queue (at any position) and reinsert it in another.

A second base class Task (Listing 3) is needed to construct tasks as separate, sequential programs. Even though the tasks run concurrently, each task must have a private context. The base class Task is the abstract class that hides (and saves) that context for each of its instances. This private task context is a snapshot of its own state that remains undisturbed while other tasks run. A state consists of a stack pointer, a stack size, a stack base, an id, a parent id, and a starting address.

In addition to these base classes, the class ReadyQ (derived from the base class StateQ) has a specialized method called GetNextRunning. This method retrieves the next ready task at the head of the ready queue. A next ready task corresponds to the next running (active) task.

class ReadyQ : StateQ {
public:
 ReadyQ( ) : StateQ(0, READY) { }
 void GetNextRunning(void);
};

Starting From Main

A multitasking application is normally composed of several user tasks. You specify these by providing your own verson of StartUpUserTasks. Listing 5 shows an example. All user tasks (Background, Task0, and Task1) are implemented in the same file suuser. cpp. In a real application you would more likely compile each user task separately.

Compare the output generated (in Figure 2) with the code in Listing 5. After the version message printed, main (in Listing 4) creates three queues: terminatedQ, suspendedQ, and readyQ. It also starts StartUpUserTasks task with these statements:

(new Task (StartUpUserTasks,
         1024))->Start();
readyQ->GetNext Running();
RunNext ();

Control now passes to StartUpUserTasks (Listing 5) where the Background, Task0, and Task1 tasks are started:

(new Task(Background, 1024))->
          Start();
(t0 = new Task(Task0, 1024))->
             Start ();
(t1 = new Task(Task1, 1024))->
             Start();

Remember, starting a task means creating and scheduling a task to run in the readyQ so StartUpUserTasks can maintain control until it reschedules itself. Thus, from this point, the execution involves 20 consecutive context switches, allowing StartUpUserTasks, Background, Task0, and Task1 to print S. 01 in sequence. (See the output in Figure 2. ) This sequence will break when Task0 suicides (you can see when Task0 stops printing). StartUpUserTasks then suspends Task1 before doing five consecutive context switches, printing five sequences of S. in a row.

The controlling task resumes Task1, restarts Task0 and suicides gracefully. Again, Task0 suicides, and the final printing sequence that will run forever (until control-C is pressed) is 1., illustrating that Task1 and Background are sharing the rest of the processor time.

Conclusion

This is not a complete executive, but it is a practical implementation using inheritance in a multitasking programming context. Every system call is localized and implemented through a method without changing any others. The private Schedule method is isolated to allow an easy replacement by a more sophisticated task scheduling mechanism. A black-ox scheduler gives complete flexibility to the developer during all phases of the application. (See "Practical Schedulers for RealTime Applications" by Robert Ward, CUJ April 1990.) No inter-ask communication has been covered. I hope to cover this topic (as well as some real multitasking applications) in a future article. In this article, I've concentrated mostly on design and C+ + programming techniques. If you're interested in reusable software components and several applications that exercise the executive, contact the author.

Listing 1

Listing 2

Listing 6