sim-din topical media & game development
topical media & game development

talk show tell print

object-oriented programming

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

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;

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.

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

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

set phase on waiting

return OK; } int philosopher::await() { if ( (chopstick[id] -> 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

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.

(C) Æliens 04/09/2009

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.