Object-oriented simulation

Historically, there is a close connection between simulation and object-orientation. The first object-oriented language, SIMULA, was a programming language meant for discrete event simulation, see [DaNy66].

In [Hill96], an overview is given of what is required for complex system modeling, and more in particular how object-oriented analysis and design may aid in defining models that lend themselves to performance evaluation by means of simulation studies. Performance evaluation belongs traditionally to the field of statistics and operations research. However, according to [Hill96], for a clear understanding of the behavior of complex systems and the interpretation of measurement results, we need to derive our action models, which are used to perform the simulations, from domain and system object models, describing the structure of the system and its relation to reality. In other words, an object-oriented approach may help us in arriving at better models, provided that we have the stochastic support needed to perform reliable performance studies.

In this section, we will briefly discuss the SIM library, as an example of object-oriented support for discrete event simulation. See [Hill96] for a great many alternatives.

The SIM library

SIM is a C++ library offering classes supporting discrete event simulation, based on standard simulation techniques described in [Watkins93]. In discrete event simulation, the components of the model consists of events, which are activated at certain points in time and in this way affect the overall state of the system. The simulation library consists of the classes as listed in slide sim-classes.

Simulation classes

simulation -- the scheduler
event -- representing the events
entity -- process consisting of events
generator -- random distributions
resource -- to model passive objects
queue -- to hold waiting events
histogram -- to plot the results
analysis -- for statistical analyses

slide: Simulation classes

The SIM library is integrated with the hush library, which may be used for defining a script interface to the simulation package, for developing a graphical user interface and for visualizing simulation models.

The event scheduling strategy

In its most simple form, a simulation runs until there are no events left. Events are user-defined objects that represent the functionality of the system to be modeled. At the time an event is due to be activated, it is extracted from the scheduler and the main simulation routine executes the code from the operator() method of that event.

slide: State diagram for event

The scheduling algorithm extracts all events with the same activation time. It activates the events in priority order with the highest scheduling priority first. Before executing the events, the simulation clock is updated to the activation time of the current events. Furthermore, a FIFO conditional list (containing events that occur when some condition is met) is traversed in priority order with highest scheduling priority first. Events that can run now are executed. Events that are not used anymore should be terminated to prevent the system from overflow.

Event states

passive - currently not available for any processing
active - this is the event currently being processed
queued - the event is in a queue
pending - the event is in the scheduler
conditional - the event is on the conditional list
closed - on the conditional list but unavailable

slide: Event states

In slide sim-event a state-diagram is given, which depicts the states (see slide sim-states) an event object can be in. The state of an event can be affected both by the scheduler as well as from within the user-defined methods of the event. The labels on the arrows indicate the methods that result in a state transition. (As a convention, the methods above the arrows indicate a transition from left to right, the methods below the arrow a transition from right to left, in case of a bi-directional relation between states.)

Example -- dining philosophers

Consider the following (classical) problem. Five philosophers sit around a table with five chopsticks in between. They think, and if they are hungry and if two chopsticks are available, they eat. If a philosopher gets hungry and s/he cannot acquire a chopstick, the philosopher waits until s/he can. The philosopher does not think, if s/he is waiting or eating. We are interested in the fraction of the time, that a philosopher actually thinks.

slide: Dining philosophers

In slide sim-dining a graphical rendering is given of a simulation at work. The applet displayed in the hush browser is written with the Tcl/Tk command binding to the SIM library.

We will now look at two methods to define the actual simulation mode, an event-based method and a process-based method.

The event-based approach

With the event-based approach of writing a simulation program we first identify the events in the model. The behavior of an event is implemented by deriving it from the class event and overriding the function operator of this class.

We develop this program in the following steps. First, the library is included as sim.h. The declarations of the global variables and constants follow after that. The time unit in this simulation is an hour, so a philosopher has a mean eating time of two hours and a mean thinking time of five hours. The duration of the simulation is a year. After that, we define the various events.


  #include <sim/sim.h>
   
  const double duration = 52*7*24.0;        a year


  const int number = 5;                     philosophers


  const int eatingtime = 2;                 2 hours


  const int thinkingtime = 5;               5 hours


  simulation* sim;
  generator* g;
  resource* chopstick[number];
  histogram* thinking;

After defining the global variables, we define the actual event classes. To model this problem, three events can be identified, eat, think and await. The corresponding classes are derived from the class event. Furthermore we need a chopstick for every philosopher. These are represented as a resource. The thinking times are gathered in an instance of the class histogram and the generator takes care of the variations in the time needed to think and eat.


  class eat : public event
  {
  public :
    eat(int i);                  constructor, taking identity


    virtual int operator()();    function operator


  private :
    int id;                      identity of the philosopher


  };
   
  class think : public event
  {
  public : 
    think(int i);                constructor, taking identity


    virtual int operator()();    function operator


  private :
    int id;                      identity of the philosopher


  };
   
  class await : public event
  {
  public :
    await(int i);                constructor, taking identity


    virtual int operator()();    function operator


  private :
    int id;                      identity of the philosopher


  };

Next, we implement the various events. An event is given its functionality by deriving it from the class event and overriding its function operator.

The logic of the eat event is that the philosopher eats for a random time, exponentially distributed with a mean eating time. So, we first determine the actual eating time and schedule a think event to be activated after this eating time. The eat event can be terminated.


  eat::eat(int i) : event()
  {
    id = i;                                   set identity


  }
   
  int eat::operator()()
  {
    double t = g -> exponential(eatingtime);  eating time


    think* th = new think(id);                create a thinking event


    sim -> schedule(th,t);                    schedule thinking


    sim -> terminate(this);                   terminate this eat event


    return OK;
  }

If a philosopher starts to think, the philosopher first releases both chopsticks. The thinking time is determined and a sample is made of the percentage of this thinking time towards the total time. An await event is scheduled and the think event is terminated.


  think::think(int i) : event()
  {
    id = i;                                 set identity


  }
   
  int think::operator()()
  { 
    chopstick[id] -> release();             release left chopstick


    chopstick[(id+1) % number] -> release();  release right


    double t = g -> exponential(thinkingtime);     thinking time


    thinking -> sample(id,t/duration*100);  add a sample (%)


    await* aw = new await(id);              create await event


    sim -> schedule(aw,t);                  schedule waiting


    sim -> terminate(this);                 terminate thinking


    return OK;   
  }

The await event acquires the left and right chopstick and schedules an eat event immediately, if both chopsticks are available. The await event is passivated as it could be on the conditional list. If no chopsticks are available, the await event stays on the conditional list or, if it was not conditional as is the case the first time it is activated, it is added to the conditional list.


  await::await(int i) : event()
  {
    id = i;                                  set identity


  }
   
  int await::operator()()
  {
    if ( (chopstick[id] -> available()) &&       available ?


       (chopstick[(id+1) % number] -> available()) )
    {
      chopstick[id] -> acquire();                acquire left


      chopstick[(id+1) % number] -> acquire();     acquire right


      eat* e = new eat(id);
      sim -> passivate(this);       extract from conditional list


      sim -> schedule(e,0);         schedule eat event immediately


      sim -> terminate(this);       terminate await event


    }
    else if (!conditional())        not on conditional list


      sim -> hold(this);            add to conditional list


    return OK;
  }

The following step is the definition and implementation of an application, which is derived from session. The application::main function first creates the simulation object. Furthermore, a frequency histogram and five resources that represent the chopsticks are created. The histogram is created with its widget path and with its (default) options. Afterwards it is packed to the display. The simulation starts with all philosophers waiting and runs for a year (52*7*24 hours). After running the simulation, the resulting histogram is printed.


  int application::main()    tk is an instance variable of session


  {
    sim = new simulation(); 
    g = new generator(80,20,19);           gets three seeds


    thinking = new histogram(".h","-columns 5 -title thinkingtime");
    tk -> pack(thinking);                  add to display;


    tk -> update();                        update display;


    for (int i=0;i create chopsticks

      await* aw = new await(i);            schedule each


      sim -> schedule(aw,0);               philosopher waiting


    }
    sim -> run(duration);                  run for duration


    cout << (*thinking) << endl;           print resulting histogram


    delete thinking;
    delete sim;
    return 0;                              successful termination


  }

The process-oriented approach

With the process-oriented approach the components of the model consist of entities, which represent the existence of some object in the system such as a philosopher. An entity receives a user-defined phase that determines the behavior of the entity.

The entity class is derived from the event class. It may be regarded as a compound event, that is it maintains an additional phase variable to record the actual phase it is in.

We first identify the entities (or the types) in the model. The events are represented as methods of an entity. The function operator calls these events based on the phase the entity is in, as illustrated in the definition of a philosopher.


  enum {EATING,THINKING,WAITING};       phases of a philosopher


    
  class philosopher : public entity
  {
  public :
    philosopher(int ph,int i);   constructor, taking phase and id


    virtual int operator()();    function operator


    int eat();                   eat event


    int think();                 think event


    int await();                 await event


  private :
    int id;
    generator* g;
  };
    
  philosopher::philosopher(int ph,int i) : entity(ph)
  {
    id = i;                   set phase and identity


    g = new generator(20,10,999);
  }
    
  int philosopher::operator()()
  {
    switch (phase())          what phase is the philosopher in?


    {
    case EATING :
      return eat();           the philosopher eats


    case THINKING :
      return think();         the philosopher thinks


    case WAITING :
      return await();         the philosopher waits


    }
    return FALSE;
  }
    
  int philosopher::eat()
  {
    double t = g -> exponential(eatingtime);     determine eating time


    sim -> wait(t);             schedule this philosopher thinking


    phase(THINKING);                    set phase to thinking


    return OK;
  }
    
  int philosopher::think()
  {
    chopstick[id] -> release();             release left chopstick


    chopstick[(id+1) % number] -> release();  release right


    double t = g -> exponential(thinkingtime);    determine thinking time


    thinking -> sample(id,t/duration*100);        sample (%)


    sim -> wait(t);               schedule this philosopher waiting


    phase(WAITING);                         set phase on waiting


    return OK;
  }
   
  int philosopher::await()
  {
    if ( (chopstick[id] -> available()) &&     available?


       (chopstick[(id+1) % number] -> available()) )
    {
      chopstick[id] -> acquire();           acquire left chopstick


      chopstick[(id+1) % number] -> acquire();       acquire right


      sim -> passivate(this);          make passive


      sim -> activate(this);           activate as eating


      phase(EATING);                   set phase on eating


    }
    else if (!conditional())       
      sim -> hold(this);                   add to conditional


    return OK;
  }

Dependent on the phase the philosopher is in, the appropriate action on the simulation environment is taken. These actions closely resemble the events, described in the event-based approach of this problem. The main difference is in the use of phase. If, for example, a philosopher finishes eating, his/her phase is set to THINKING and he/she is scheduled after t time units, whereas in the event-based approach a think event is scheduled and the eat event is explicitly terminated. So, in the process-oriented solution a philosopher exists for the entire simulation. In the application::main function the simulation is set up by scheduling the five philosophers, initially waiting, instead of scheduling five await events.

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.