Columns

CUG Product Focus

C++ SIM

Victor R. Volkman

Victor R. Volkman received a BS in Computer Science from Michigan Technological University. He has been a frequent contributor to The C Users Journal since 1987. He is currently employed as Senior Analyst at H.C.I.A. of Ann Arbor, Michigan. He can be reached by dial-in at the HAL 9000 BBS (313) 663-4173 or by Usenet mail to sysop@hal95.com.

Introduction

This month's product focus is derived from documentation written by M.C. Little and D.L. McCue. Little and McCue have provided this documentation, which describes their C++ SIM simulation class library, expressly for reprint in The C Users Journal.

C++ SIM is a class library which provides discrete process-based simulation similar to that provided by SIMULA [Birtwhistle 73][Dahl 70] and has been used in the work presented in [McCue 92]. Based on the facilities provided in SIMULA, C++ SIM provides active objects (instances of C++ classes) as the units of simulation using the type-inheritance facilities of C++ to convey the notion of "activity."

C++ SIM is designed to be used with a user-supplied threads package. C++ SIM's authors use Sun Microsystem's lightweight process (thread) package; however, they have added this package to the simulation class hierarchy through an abstract class definition so that other lightweight process packages can be used instead with very little modification. Users of this framework can replace existing classes as long as the replacements conform [Black 86] to the original class definition.

This article describes the C++ SIM class hierarchy, and shows how it can be used to further refine the simulation package [1].

The Class Hierarchy

Figure 2 illustrates the main class hierarchy within the simulation package. The base class is Thread, which provides the minimum functionality required of a threads library. Two classes, GNU-Thread and LWP_Thread, derive from the Thread class to support the threads packages that were available to C++ SIM's authors at the time of this writing. These classes are Sun's own lightweight process package, and the GNU threads library. Class Thread_Type provides a (relatively) transparent way to change from one thread implementation to another. Class Process provides all operations required by the simulator to control execution of all processes in the simulation. These classes are described in the following sections.

The Threads Base Class

In keeping with the C++ programming model, classes obtain the thread characteristic, necessary to convey the notion of "activity" within the simulation environment, by inheriting an appropriate base class (in simulation terms they become processes). In C++ SIM, all classes that provide the abstraction of threads must be derived from the Thread base class. This base class forces the derived class to provide a minimum set of operations required for the management of threads. (The base class defines these operations as pure virtual functions, and C++ requires that a deriving class define such functions before an instance of the class can be declared.) These operations are shown in the Thread class as follows:

class Thread
{
public:
    virtual void Suspend() = 0; // pure virtual function
    virtual void Resume() = 0;
    
    virtual void Body() = 0;
    virtual long Current_Thread() = 0;
    
    virtual long Identity();
    static Thread* Self();
};
When defined, the Suspend and Resume methods will give the thread package specific ways of suspending and resuming execution of a thread respectively.

Body represents the controlling code for each object, i.e., the scope within which the controlling thread will execute.

Current_Thread must be defined by the derived class, since it returns the identity of the currently executing thread, which is specific to the thread package used.

The base class itself implements the operations Identity and Self because some threads packages do not provide similar functionality. Identity returns the unique identity of the thread associated with a given object, and Self returns the currently executing thread. Because Self is a static member function programs can invoke it without creating an instance of the Thread class, i.e., programs may call Thread::Self().

The Class LWP_Thread

User classes which require separate threads of control using the Sun thread package can be derived from the LWP_Thread class shown as follows:

class LWP_Thread : public Thread
{
public:
    virtual void Suspend();
    virtual void Resume();
    virtual void Body() = 0;

    virtual long Current_Thread();
    
    thread_t Thread_ID();
    static void Initialize();
    
protected:
    static const int MaxPriority;
    LWP_Thread(int priority = MaxPriority);
};
The MaxPriority constant represents the maximum priority at which a thread may execute (by default all threads derived from this class execute at this priority). Class LWP_Thread defines all of the pure virtual functions declared in Thread except Body, which must be defined by the deriving class.

Initialize initializes the threads package prior to use. (Obviously the operations performed within this method are thread package specific.)

Thread_ID returns more detailed (package-specific) information about the associated thread.

The Process Class

Applications could derive from the Thread base class to provide active objects in C++ outside of the simulation package. However, to become a process in the simulation environment, a class must be derived from the Process base class.

This class is shown as follows:

class Process : public LWP_Thread
{
public:
    virtual ~Process ();
    
    static double CurrentTime ();
    
    void ActivateBefore (Process&);
    void ActivateAfter (Process&);
    void ActivateAt (double AtTime = CurrentTime());
    void ActivateDelay (double AtTime = CurrentTime());
    void Activate();

    void ReActivateBefore (Process&);
    void ReActivateAfter (Process&);
    void ReActivateAt (double AtTime = CurrentTime());
    void ReActivateDelay (double AtTime = CurrentTime());
    void ReActivate ();
    
    void Cancel ();
    double evtime ();
    void set_evtime (double);
    
    boolean idle ();
    boolean terminated ();
    
    virtual void Body () = 0;
    
protected:
    Process ();
    
    void Hold (double t);
    void Passivate ();
};
idle returns either TRUE or FALSE depending upon whether the process is currently in the simulation queue.

terminated returns either TRUE or FALSE depending upon whether the process is terminated.

evtime returns the simulation time at which a process is due to be reactivated; set_evtime enables a program to change this time.

The Hold method removes the active process from the head of the event queue and schedules it to become active a specified number of time units later.

Passivate removes the currently active process from the event queue altogether. If the process is to execute again the program must recreate it.

Cancel removes the process from the simulation queue or simply suspends it indefinitely if it is currently not in the queue.

At any point in time, a process can be in one (and only one) of the following states:

There are five ways to activate a process, and similarly five ways to reactivate a waiting process:

(Note that if a process is already scheduled, reactivation will simply re-schedule the process.)

The Current Time method returns the current simulation time; programs typically call Curren time to control action relative to a given time period.

The Simulation Scheduler

As in SIMULA, simulation processes (entities) execute at their assigned simulation time, which is typically determined by an appropriate distribution function. Only one process executes in any instance of real time, but many processes may execute at any instance of simulation time. Programs place currently inactive processes in a simulation queue (the event queue), which is arranged in order of increasing simulation time.

To coordinate the execution of these processes, the scheduler manages the simulation queue as follows: when no process is currently active, the scheduler selects a process to run from the head of the queue and (re-) activates it. When no processes are left to execute, i.e., the queue is empty, the simulation ends.

The simulation queue is organized as a tree to improve the efficiency of the scheduling algorithm. All nodes (processes) at the same level of the tree are assigned to the same simulation time, as shown in Figure 1.

Because the scheduler manages processes in the simulation environment it cannot itself be a simulation process. Like the main thread to be described later, the scheduler is a priority thread within the environment and as such must be controlled in a slightly different manner than the other simulation entities. The structure of the scheduler is extremely simple and is shown as follows:

class Scheduler : public LWP_Thread
{
public:
    Scheduler ();
    ~Scheduler ();
    void Body ();
    double CurrentTime ();
};
Every simulation application must start one scheduler before the simulation can begin. The example to be described near the end of this article illustrates use of the scheduler.

Priority Threads

C++ SIM executes two "priority" threads which cannot be derived from the Process base class and therefore must be activated and deactivated separately. These threads are as follows:

Distribution Functions

Simulations often require distribution functions of various events (e.g., the rate of arrivals of jobs at a processor, or the time between failures for a node). C++ SIM provides a set of classes which give access to various useful distribution functions, including the following: RandomStream, UniformStream, Draw, Exponentialstream, ErlangStream, HyperExponentialStream, and NormalStream. By creating instances of these classes the simulation processes can gain access to the appropriate distribution function. Figure 3 shows the class hierarchy of the distribution functions.

RandomStream and NormalStream

Classes RandomStream and NormalStream illustrate how the distribution functions are derived and show how further functions could be built. RandomStream (from which all other distribution functions are derived) is shown as follows:

class RandomStream
{
public:
    RandomStream (long MGSeed = 772531L.
                long LCGSeed = 1878892440L);
    virtual double operator() () = 0;
    double Error ();

protected:
    double Uniform ();

private:
    double MGen ();
    double series[128];
    long MSeed, LSeed;
};
The Error method returns a chi-square error measure on the uniform distribution function. The Uniform method generates random numbers; Uniform uses the linear congruential generator based on the algorithm from [Knuth Vol2], and shuffles the results of the linear generator with the multiplicative generator as suggested by [Knuth Vol2] [3] to obtain a sufficiently uniform random distribution.

Class NormalStream is defined as follows:

class NormalStream : public RandomStream
{
public:
    NormalStream (double Mean, double StandardDeviation);
    virtual double operator() ();

private:
    double Mean, StandardDeviation;
    double z;
};
The operator() uses the polar method in [Knuth Vol2] [4] to implement the NormalStream by making use of the Uniform method of RandomStream.

SIMSET

C++ SIM also provides entity and set manipulation facilities similar to those provided by the SIMSET classes of SIMULA. These facilities break down into two classes:

Class link is defined as follows:

class Link
{
public:
    virtual Link ();
    
    Link* Suc () const;
    Link* Pred () const;
    
    Link* Out ();
    void InTo (head*);
    
    void Precede (Link*);
    void Precede (Head*);
    void Follow (Link*);
    void Follow (Head*);

protected:
    Link ();
};
Because it makes no sense to create instances of Link objects, the constructor for Link is protected — programs must derive a class from Link to benefit from its functionality.

Suc and Pred return the successor and predecessor of this list element respectively. These functions return 0 if no such element exists.

Out removes the object to which it currently belongs (if any) from the linked list. InTo makes this object the last element in a linked list if the list exists; If the list doesn't exist Out attempts to remove the object from any linked list to which it may belong.

Precede also places an object in a linked list. If Precede is passed another Link element, say L, then if L is a member of a linked list, this object is placed into the same linked list and immediately preceding L. If L isn't a member of a linked list, the result is the same as for Out. If Precede is passed a Head object it produces the same result as InTo.

Follow acts similarly to Precede, except that L.Follow(L1) inserts L immediately after L1, and L.Follow(H), places L as the first element in H, where H is a Head object.

Note that as in SIMULA, Link elements can only belong to one linked list at a time.

Class Head is defined as follows:

class Head
{
public:
    Head ();
    virtual ~Head ();
    
    Link* First () const;
    Link* Last () const;
    
    long Cardinal () const;
    boolean Empty () const;
    
    void Clear ();
}
First and Last return references to the first and last Link objects in the list respectively. If the list is empty then these functions return 0.

Cardinal returns the number of Link objects in the list, and Empty returns TRUE if the list is empty, FALSE otherwise. Clear removes all Link objects from the list.

Example: Job Service Simulation

This example is taken from [Mitrani 82] and simulates a process scheduler for a machine which attempts to execute as many process (jobs) as possible. The machine can only process one job at a time and queues job requests until it can deal with them. The machine is prone to failures, so started jobs will be interrupted by such failures and delayed until the machine has been repaired (reactivated), at which point it is forced to restart execution from the beginning (i.e., it is placed at the head of the job queue). The main processes within this example are:

Arrivals

The Arrivals class definition is relatively simple since none of the other processes invoke operations on it. Arrivals is defined as follows:

class Arrivals : public Process
{
public:
    Arrivals (double);
    ~Arrivals ();

    void Body ();

private:
    Exponential Stream* InterArrival Time;
};
The constructor initializes the stream from which the rate of Job arrivals is drawn and the destructor simply cleans up before the object is destroyed:

Arrivals::Arrivals (double mean)
{
    InterArrivalTime = new ExponentialStream(mean);
}
Arrivals::~Arrivals () { delete InterArrivalTime; }
The main body of Arrivals (shown below) simply waits for an amount of time dictated by the rate of arrivals stream and then creates another Job. This procedure is repeated until the simulation ends.

void Arrivals::Body ()
{
    for (;;)                         // inifinite loop
    {
        Hold((*InterArrivalTime) ());
        Job* work = new Job();
    }
}

Job

Unlike Arrivals, which is an active entity within the simulation, the Job class does not need to be a separate process, since it is simply enqueued when it is created and dequeued by the Machine when it can be executed. All a given Job must do is calculate how long it took to be "processed":

class Job
{
public:
    Job ();
    ~Job ();

private:
    double ArrivalTime;
    double ResponseTime;
};
Because no operations are invoked on instances of the Job class, its constructor and destructor perform all of its work:

Job::Job ()
{
    boolean empty;
    
    ResponseTime = 0;
    ArrivalTime = sc->CurrentTime();
    empty = JobQ.IsEmpty();
    JobQ.Enqueue(this);  // place this Job on to the queue
    Total Jobs++;
    
    if (empty && !M->Processing() && M->IsOperational())
        M->Activate();  // Machine idle as no Jobs in queue
                     // and not broken
}

Job::~Job ()
{
    ResponseTime = sc->CurrentTime() - ArrivalTime;
    TotalResponseTime += ResponseTime;
}

Queue

The program places jobs which are not being serviced in a job queue. As with the Job class, an instance of Queue is not required to be active, and as such Queue is not derived from the Process class.

Queue is defined as follows:

class Queue
{
public:
    Queue ();
    ~Queue ();
    
    boolean IsEmpty ();
    // returns TRUE if no Jobs in queue
    long QueueSize ();
    // returns number of Jobs in queue
    Job* DeQueue ();
    // returns head of queue
    void Enqueue (Job*);
    // places Job at tail of queue
};

Machine

The Machine process obtains Jobs from the queue and processes them. Since Machine is prone to failures Jobs can take extended periods of time to complete. Other simulation processes invoke various operations on the machine (for example to determine whether or not it has failed):

class Machine : public Process
{
public:
    Machine (double);
    ~Machine ();
    
    void Body ();
    
    void Broken ();
    void Fixed ();
    boolean IsOperational ();
    boolean Processing ();
    double ServiceTime ();

private:
    ExponentialStream* STime;
    boolean operational;
    boolean working;
};
As with the Breaks and Arrivals processes, Machine's constructor and destructor initialize and delete the stream that dictates the time required to process a Job.

Processing returns the current status of the machine, i.e., whether or not it is executing a job:

boolean Machine::Processing () { return working; }
Broken and Fixed de-activate (crash) and re-activate the machine respectively:

void Machine::Broken () { operational = false; }
void Machine::Fixed () { operational = true; }
IsOperational indicates whether or not the machine is currently active (i.e., whether it has "crashed"):

boolean Machine::IsOperational () { return operational; }
ServiceTime returns the time required to service a given job based on the relevant distribution function initialized within the constructor:

double Machine::ServiceTime () { return (*STime)(); }
The main body of the Machine gets a Job from the job queue (if one is available) and attempts to process it before looping again:

void Machine::Body ()
{
    for(;;)
    {
       working = true;

       while (!JobQ.IsEmpty())
       // continue as long as Jobs are available
       {
          Hold(ServiceTime());
          Job* J = JobQ.Dequeue();
          
          ProcessedJobs++;
          // keep track of number of completed Jobs
          delete J;             // remove finished Job
       }
       
       working = false;
       // no Jobs in queue so become idle
       Cancel();
    }
}

Breaks

The Breaks class defines a process which simply waits for a specific period of time before "killing" the Machine process. This process then waits again before re-activating the machine. The Breaks class definition is relatively simple:

class Breaks : public Process
{
public:
    Breaks ();
    ~Breaks ();
    
    void Body ();

private:
    UniformStream* RepairTime;
    UniformStream* OperativeTime;
    boolean interrupted_service;
};
The constructor and destructor simply initialize and delete the streams used by the Breaks process respectively.

The main body of the Breaks process activates and deactivates the Machine process. The Machine fails and recovers according to the OperativeTime and RepairTime distribution functions respectively. The body is defined as follows:

extern Machine* M; // This is the machine used to
                // service requests
extern Queue JobQ; // This is the queue from which
                // Jobs are drawn

void Breaks::Body ()
{
    for(;;)
    {
       Hold((*OperativeTime)());
       M->Broken();
       // de-activate the Machine
       M->Cancel();
       // remove Machine from Scheduler queue

       if (!JobQ.IsEmpty())
           interrupted_service = true;
       
       Hold((*RepairTime)());
       M->Fixed();    // re-activate the Machine
       if (interrupted_service)
       {
           interrupted_service = false;
           M->ActivateAt(M->ServiceTime() +
                        CurrentTime());
       }
       else
           M->ActivateAt();
    }
}

MachineShop

The MachineShop class is the core of the simulation; it starts up all of the main processes involved, and when the simulation ends it prints out the results.

class MachineShop : public Process
{
public:
    MachineShop ();
    ~MachineShop ();

    void Body ();
    void Await ();
};
The Body method starts up the other processes, such as the Machine, and then waits until the number of processed Jobs is at least 100,000:

void MachineShop::Body ()
{
    sc= new Scheduler();       // create the simulation
                          // queue scheduler
    Arrivals* A = new Arrivals(10);
    M = new Machine(8);
    Job* J = new Job;
    Breaks* B = new Breaks;
    
    // activate the relevant simulation processes
    
    B->Activate();
    A->Activate();
    sc->Resume();             // start up the scheduler
                          // - it is not a process
    
    while (ProcessedJobs < 100000)
        Hold(10000);

cout << "Total number of jobs processed"
<< TotalJobs << endl;
cout << "Total response time" << TotalResponseTime << endl;
cout << "Avge response" <<
(TotalResponseTime/ProcessedJobs) << endl;
cout << "Avge number jobs present"
<< (JobsInQueue/CheckFreq) << endl;

    // end simulation by suspending processes
    
    sc->Suspend();
    A->Suspend();
    B->Suspend();
}
It isn't necessary to explicitly activate the Machine process because the Breaks or Jobs process will do this.

The Await method suspends the thread associated with main, thus allowing the other simulation threads to execute:

void MachineShop::Await()
{
    Resume();
    Thread::Self()->Suspend();
}

Main

The main part of the simulation code initializes the various thread-specific variables used (e.g., the maximum priority of a thread), creates the main body of the simulation code (in this case MachineShop) and then suspends the thread associated with main:

void main ()
{
    LWP_Thread::Initialize();
    
    MachineShop m;
    m. Await();        // Suspend main's thread
                    // (NOTE: this MUST be done by all applications).
}

Conclusions

The authors of C++ SIM have endeavoured to provide a simulation package which provides similar functionality to that of SIMULA, since SIMULA has fulfilled the needs of users over many years. From their experiences of using SIMULA, both as a general programming language and as a simulation tool, they believe they have been successful. As a result of using C++ they also believe that they have produced a simulation package having several advantages over SIMULA, for example:

Acknowledgements

The authors would like to thank Professor Isi Mitrani for the help he has given them in the development of this simulation package and the time he has devoted to listening to their thoughts and problems. They would also like to thank Ron Kerr for his help with the SIMULA language, and Dr. Graham Partington for his comments on drafts of this article. The work reported here has been supported by SERC/MOD Grant GR/H81078 and Esprit Broadcast (Basic Research Project Number 6360).

References

[Birtwhistle 73] G. M. Birtwhistle, O-J. Dahl, B. Myhrhaug, K. Nygaard, Simula Begin, Academic Press, 1973.

[Black 86] A. Black et al, "Object Structure in the Emerald System", Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, October 1986.

[Dahl 70] O-J. Dahl, B. Myhrhaug, K. Nygaard, "SIMULA Common Base Language," Technical Report S-22, Norwegian Computing Centre, 1970.

[Knuth Vol2] Knuth Vol2, Seminumerical Algorithms, Addison-Wesley: p. 117.

[McCue 92] D. L. McCue and M. C. Little, "Computing Replica Placement in Distributed Systems," Proceedings of the 2nd Workshop on the Management of Replicated Data, November 1992: pp. 58-61.

[Mitrani 82] I. Mitrani, Simulation Techniques for Discrete Event Systems, Cambridge University Press, Cambridge, 1982: p. 22.

[Sedgewick 83] R. Sedgewick, Algorithms, Addison-Wesley, Reading MA, 1983: pp. 36-38.

[Stroustrup 86] B. Stroustrup, The C++ Programming Language, Addison Wesley: 1986.

Footnotes

[1] The software to be described in this paper is available via anonymous ftp from arjuna. ncl. ac. uk

[2] The authors would like to thank Professor I. Mitrani for his help in developing the multiplicative generator used in the simulation. It is based on the following algorithm: Y[i+1] = Y[i] * 5^5 mod 2^26, where the period is 2^24, and the initial seed must be odd.

[3] As suggested by Maclaren and Marsaglia.

[4] Due to Box, Mullers and Marsaglia