Features

C++, Coroutines, and Simulation

Trond Akerbaek

Trond Akerbaek is teaching at a college in Halden, Norway. Current interests include computer communications, neural networks, and fuzzy systems. He can be contacted at Ostfold DH; N-1757 Halden; Norway; e-mail:tronda@dhhalden.no.

Introduction

Object-oriented programming is not a new concept. The Simula67 Language, developed in the late sixties, contains all the basic concepts found in modern object-oriented languages such as C++. An important part of Simula not found in C++ is the support for quasi-parallel processes and simulation. Very few programmers ever use parallel functions or coroutines in their programs, even if it will lead to more elegant designs. There are several reasons: few languages have ample support, coroutines may otherwise be cumbersome to implement, and it is possible to solve most problems without.

C programmers may use setjmp and longjmp and functions based on these to implement quasi-parallell routines. With C++ and some assembly instructions it is possible to create a set of functions which makes coroutines easier to comprehend and use. Using coroutines, implementing simple tools for simulation modelled after the Simula67 tools, is a fairly easy matter.

In this article I will give a brief introduction to coroutines and describe an implementation in Borland C++ 2.0, with a single assembly function in Turbo Assembler. Based on the coroutine concept, the article will discuss simulation and how to implement it in C++.

Quasi-Parallel Functions and Coroutines

Due to the single-processor constraint, computer programming has traditionally been sequentially-oriented with a single thread of operations. Multitasking operating systems give us the opportunity to create programs consisting of several sequential processes operating in parallel on a timesharing basis. The operating system controls the task switching, with little or no influence from the programmer.

The object-oriented approach is still basically sequential, even if it makes it easier to describe real processes which are interacting and operating in parallel. Parallel processes cannot directly be modelled in a sequential language. The process descriptions are running on a single processor, and must switch back and forth, imitating real parallel behavior, hence the expression quasi-parallel.

It would be another situation if the model were running on a multiprocessor machine, with one processor for each process. In that case the model would be described in a language designed for such environments.

The Coroutine Extensions

In order to support the coroutine concept I have created a few extensions to C++:

• A base-class coroutine for all classes describing coroutines.
• A virtual function main in coroutine subclasses containing the actions of the coroutine.
• The primitive resume(coroutine*) which freezes the current coroutines actions, and transfers control to the indicated coroutine, resuming its actions at the freesing point.
• A new coroutine instance is initially frozen at the start of its main function.
• A primitive detach is available, which freezes the current coroutine actions and transfers control to the main program.
• A coroutine is terminated when its main function is terminated normally (not frozen by resume or detach). Resuming a terminated object leads to a runtime error.

Automatic variables declared in a class method and alllocated on the stack are not availablee outside the couroutine instance. A variable declared in the main function of the program, is not available within the other coroutines. The main program is in fact a coroutine with the main function defining its actions.

There must be no register variables, because registers will not be preserved changing coroutines.

Implementation

The implementation consists of the coroutine class, the two primitives resume and detach, and a few functions for internal use. Each coroutine, as the main program, has its own stack. Switching between coroutines is done by switching stacks. Whenever a coroutine is activated, the activating coroutine's stack is saved in memory, and the activated coroutine's previously stored stack is copied to the stack segment.

Listing 1 contains the definitions. The variables of the coroutine class are used for keeping track of the passive stack. stkSegment and stkOffset are the segment and offset address of the area where the stack is stored, while stkSize holds the size of the used part of the stack.

Listing 2 shows the implementation. There are three internal pointers in the implementation file: PREVIOUS referencing the coroutine to switch from, CURRENT referencing the new and active coroutine, and MAINC referencing the main program.

When a new process is created as a coroutine subclass instance, the stack of the new process is initialized by coroutine::coroutine(). Space for the initial stack is allocated on the heap, and the addresses and the size are stored in the base class variables. This stack is initialized, so that on activation, the stack is copied from the heap, and control is passed to the superMain function.

The trick is to store the address of the starting function (startProcess) on the stack as a return address. When the stack-switching function terminates, control returns to this address as if it was calling the function. This function in turn starts the superMain function, which calls the main function of the subclass. The superMain function also takes care of necessary terminating actions. A coroutine may be deleted. In that case the coroutine::~coroutine() method releases the stack area.

The resume primitive switches control from the active coroutine to the new current specified as parameter to the primitve. At first, the size of the current stack is computed, and space for storage is allocated on the heap. The PREVIOUS and CURRENT variables are set, pointing to the two coroutines involved. The assembler function ctxtswc is callled to do the actual stack chnge. On return, the new coroutine is CURRENT and active, and the area for stack storoage is released. The detach primitive resumes MAINC, the main program.

You find ctxtswc in Listing 3. The global variables CURRENT and PREVIOUS are imported by ctxtswc. Through these pointers, the stack storage area of the two coroutines involved, are accessible.

ctxtswc works by copying the current system stack to the area referenced in the PREVIOUS coroutine instance. This copy of the stack now contains the return address from the ctxtswc call. Then the stack of the new CURRENT coroutine is copied from the storage area to the system stack area, and the SP register is reset. This stack now contains the return address from the ctxtswc call, last time it was called by the coroutine. Therefore, when ctxtswc returns, program execution continues where the resumed coroutine was stopped.

This version is written for the compact memory model. Minor changes in ctxtswc and some of the C++ functions are necessary for other memory models.

Simulation

With the tools described in the previous sections it is possible to model interacting real-world processes in a quasi-parallel program. In such a model you can experiment. By changing the number of processes, the behavior of each, and the input data you can test the model to gain insight into how the real system would perform under different circumstances.

Simulating real processes in a computer model is often cheaper than doing real life experiments. In some cases it is not even possible to experiment with the real system. Consider the case of a nuclear reactor. In order to study the behavior of the reactor operators in stress situations, e.g. when serious problems occur, it would be necessary to induce problems in the reactor. We cannot do that, for obvious reasons. Instead a control room connected to a computer model, simulating the reactor, is used in experiments and training.

Real systems are often very complex. When creating a model, it is necessary to include those features that are crucial to the model's operation, and avoid insignificant details. Otherwise the simulation results may be of no value.

The time aspect of simulation, which is very important in most real systems, is not handled within the coroutine concept. In the next sections, I will introduce a set of tools for modelling processes in simulated time with C++.

An Example

This is a hypothetical system consisting of a number of physicians working together in a clinic receiving patients. The system is simplified in order to keep the example reasonably small in size.

The physicians receive patients from 8 A.M. until 4 P.M. Then the physicians work until no more patients are waiting. The patients arrive one at a time. On arrival the patient goes to the waiting room. If there is a physician in the lunchroom, he is summoned at once. Otherwise the patient waits for his turn. When a patient leaves the clinic, the physician will see the next patient. If nobody is waiting, he will go to the lunchroom for a coffee break.

The physicians, observing that most of the day the waiting room is full, want to know if another physician should be invited to join the group. They are losing business because the patients must wait too long, but they are not sure if this might lead to an increasing number of coffee breaks.

The model of this system consists of a clinic object, a number of physician objects, and the patients. For each of these objects, there is a set of actions controlling the objects and their interactions. As the objects operate in simulated time, their classes are derived from the class process, a subclass of the class coroutine, which contains the information necessary to support the time concept. Instead of the resume and detach primitives, a small set of more advanced primitives will be used. These are based on resume and detach, but are more suitable for simulations in time.

Most simulation models depend on some kind of input data that specifies when the significant events occur. In this case, the important events are the arrivals of patients, and the duration of a consultation. It is possible to collect real data and use the information directly as input to the simulation model. Another solution is to analyze the input data and find the events' probability distributions. Input data may then be generated using random generators. The physicians have observed the arrival pattern of patients and found that patients arrive according to a Poisson distribution, and they have found the expected number of patients each minute. They have also found that the duration of each consultation is uniformly distributed over an interval.

A simulation model should always be validated by comparing the results of a simulation with real input data to real system results. If there are discrepancies, the model must be modified.

The implementation of the clinic system is found in Listing 4. The implementation consist of three kinds of processes, defined by the classes clinic, physician, and patient derived from the process base class. Each class has a constructor, and a main function describing the process actions. There is a main program which creates the process instances, starts the simulation and presents the results. This example just finds the average waiting time of the patients. Two functions are used to generate input to the model. The treatmentPeriod function returns a randomly-chosen value indicating the duration of a consultation, while periodBeforeNextArrival returns the randomly-chosen period between two arrivals.

The clinic class references two FIFO queues, chain lunchRoom and waitingRoom, where the physicians and patients are kept while waiting. In addition, there are variables used for collecting statistical data. The physician and patient classes have a pointer to the clinic, and variables for statistical data.

The physician and patient constructors set the clinic pointer. The clinic constructor creates the physician processes and schedules them to run at once. The constructors also initialize statistical variables.

The clinic main function describes the clinic actions. The main task is generating new patients. Its main loop will run until simulated time (currentTime) reaches the clinic's closing time. In the loop a new patient is created, sent to the waiting room, and activated. If there is a physician in the lunchRoom she is summoned and activated. Then the clinic process reschedules itself and waits until the next patient arrives, with the hold primitive.

The physician process is an eternal loop. Each time the physician process checks if the waitingRoom is empty. If so, she goes to the lunchRoom and has a break by calling the passivate primitive. This primitive will suspend the process until some other process activates it. If there are patients in the waitingRoom, the physician gets the next patient, activates him and suspends herself with the hold primitive while helping the patient. When the consultation ends, she will see the patient out, activating him, and repeat the loop.

The patient process is simple. It is activated three times, first by the clinic process when the patient is sent to the waitingRoom, then by the physician on leaving the waitingRoom, and last by the physician when the consultation is over. Each time, the patient process records the time of the event for statistical purposes before passivating itself. (When the patient main function terminates, there is an implicit passivate call.)

The main program of the system first initializes the random generator functions and the process library by calling initProcesses. Then it suspends itself until opening hours when a clinic process is created and activated. The main program again suspends itself for a long period, until the clinic is closed and all patients have left. At last statistical data are processed and displayed.

In this model, each process acts on its own, performing actions. Between events, the processes are suspended waiting to be restarted, either automatically as with the hold primitive, or by another process with the activate primitive. It is much easier to understand the sequence of events for each process and to describe each process separately as in this example, than to describe the whole system in one piece. Besides, you can modify the model to include other objects such as secretaries, surgeons, several patient types, and other action sequences.

After validating the model, you can simulate and investigate different scenarios by changing the number of physicians, the arrival pattern of patients, consultation time etc. It is easy to include statements to collect other types of statistical data, such as the number of minutes spent in the lunchroom, and the distribution of patient waiting times.

The Process Extensions

I created the following extensions supporting processes:

• Each process is defined as a subclass of the process base class.
• A function initProcesses initializes the process library.
• A virtual function main in descendants of the process class contains the actions of the process.
• activate(process*,float) schedules the indicated process to run at the specified point of time. If it is already scheduled to run, it is rescheduled. If the current process is activated, it is suspended and rescheduled.
• hold(float) suspends and reschedules the current process to run after the indicated period of time.
• passivate suspends the current process without rescheduling.
• currentTime returns current simulated time.

Whenever the current process is suspended, simulated time is increased to the time of the next scheduled process, and this process is restarted. If no process is scheduled to run, a runtime error occurs. In this way simulated time grows from 0 in varying steps as controls are switched from process to process.

In addition, a few primitives not used in this example, are available

• cancel(process *) deschedules the process indicated. Cancelling the current process is the same as passivate.
• currentProcess returns a pointer to the current process object.
• mainProcess returns a pointer to the main program process object. The main program in itself is a process, and can be treated as such.
• resume(coroutine*) and detach may be used with processes as the process class is derived from the coroutine class. Avoid this, it might lead to unexpected activation sequences.

Implementation

In Listing 5 you find the process class definition. The process class is a coroutine subclass with a single time variable which contains scheduled time to run. It is initially set by the process constructor.

Listing 6 contains the implementation of the process library. The data structure of the process module is a priority queue SOS (The Sequence Set) where the scheduled processes are kept sorted in ascending order on the time variable. The current executing process is always the first object in the SOS. There is a process* MAINP which is used for referencing the main program as a process. CURRENT and MAINC are imported from the coroutine module. The initProcesses function initializes the data structure. A process object referencing the main program is created and inserted at the head of the SQS. MAINC and CURRENT used for referencing the main program and the current coroutine, are set to reference this main program process.

The four scheduling primitives activate, hold, passivate, and cancel are implemented as functions manipulating the SQS. activate inserts a process in the priority queue, hold removes and reinserts the current process, cancel removes any process, and passivate removes the current process. Whenever the current process is suspended, control is transferred to the next.

The three information primitives mainProcess, currentProcess, and currentTime just return state information: which is the main program process, which is currently executing, and what is the current simulated time.

The internal superMain function is called from startProcess to manage the user-defined main function. On termination, the process is removed from the SQS and cannot be activated again.

Some Comments on the Code listings

As shown, the implementations of the process primitives are very simple, once the coroutine primitives are in place. If the need arise, you can create other scheduling primitives of your own design.

The code shown in the listings has been compiled and tested using Borland's Turbo C++ 2.0 and Turbo Assembler 2.5, compact memory model. It is easy to modify the system for other memory models. I have removed some include statements referring to system functions and the description of the priority type class chain. You may implement this yourself, otherwise a complete system is available from the author on request.

References

Birtwistle, Dahl, Myhrhaug, Nygaard: "SIMULA BEGIN," Auerbach, Phil., 1973. (contains an introduction to the SIMULA programming language)