Discrete event simulator

This is a project that I did some years ago for performing computer simulations based on discrete events. The program pretends to be versatile and very configurable in order to allow the user to simulate anything. By the way, using Python as its extension language, the user can define very complex scenarios with event triggers and processing functions. The result is a powerful simulation engine focused in the richness of scene definition rather speed. Therefore, it is a nice tool to try experimental simulation models before building a more specific simulator program.

First at all, I will explain how the simulator works. On the one hand, there is an event scheduler that processes the existing events by chronological order. On the other hand, there is an interface between the simulator core and the extension language interpreter, so it is possible to run some code associated to an event when processed. Following that explanation come a sample script and some concluding remarks.

How it works

When we talk about computer simulators, we can distinguish between continuous or discrete models. Regarding the last ones, the operation of the modelled system is represented as a chronological sequence of events.

Every event in that sequence has a timestamp, this is, the time instant when the event occours. All the events, when generated, are pushed into a special queue type called priority queue, waiting to be processed.

The program core

The core of the program is a class called Scheduler, and its mission is to run the event actions by the order imposed by the timestamp. This class uses the STL’s template for the priority queues, called priority_queue; and defines a comparison function in order to determine, given two events e1 and e2, which of these must be processed first. Thus, the events are stored in the priority queue as they are generated and the scheduler gets them, one by one, ordered by timestamp.

In order to model the events to be processed by the scheduler, there is a C++ class called Event. That is an abstract class, with no more functionality than to serve as basis for other classes derived from Event. Therefore, the simulator can handle many types of events; this is done by extending the base class and defining new event subclases with new behaviors.

Types of events

At this time, there are two types of events defined with their correspondent classes: CallbackEvent and CREvent. The first one is just handles a callback function that is called by the scheduler in the right instant. The last one is used to schedule pieces of code from a coroutine: a special function definition that stops its execution several times along its code to simulate pauses or time lapses of any kind.

The callback-type events

A callback is a function, defined in the extension language (Python), that models the behavior of an event. The user can use an event of this type to run arbitrary code in a given simulation time instant. When the simulator clock reaches that time, the scheduler will call that function.

The coroutine-type events

A coroutine is also a function, but there is a big difference between a callback event and a coroutine event: the first one will call a function and all is done, while the last one schedules an event for each pause -i.e. each yield statement- the coroutine does.

The CREvent class models an event of this type. Each time a coroutine executes a yield statement, a new event is scheduled just to awake again the coroutine function at the end of the time lapse. Then, the coroutine yields the execution control to the simulator core. Thus, the scheduler can now continue dispatching events.

The extension language

This simulator embeds a Python interpreter in order to serve the modelling needs by the user. The Python language became very popular in the last years and now it is being used in a lot of disciplines, from scientific applications to web development. This reason and the ease of the programming in this language qualify Python as a preferent choice for the extension language of this simulator. Additionally, the API for extending and embedding the language is clear and easy to understand.

Defining the primitive functions

There are four functions defined in this version; these are C++ static functions that use an special type called PyObject for their arguments and returning value. These functions must be registered in a table by the Py_InitModule function. They will appear into the Python interpreter as a module named simul.

The four functions defined are:

• start(): Starts the scheduler; the simulation begins.
• schedule_process(g): Schedules the coroutine g.
• schedule_callback(t, fn, data): Schedules the callback function fn to be called at time t and passing data as argument to it.
• clock(): Returns the current simulation time value.

Ending words

I have developed a tool quite simple. It is a versatile discrete event simulator very suitable for building preliminary simulation scenarios with no care of optimization nor speed issues. By the way, it is also a technical demonstration of the architecture of these type of simulation tools, so the simplicity is a desired feature.

There are several software packages for doing discrete event simulations: a good example is the SimPy package. People often develop their own simulation tools; these are very efficient and specialized programs. Finally, the added value of some of the most popular open source simulation tools is debt to the contributions of a community; these projects started as a simple but extensible tool and a lot of people began using it for their work by adding custom modules.

In future posts, I will extend this simulator with some useful features and I will expose some typical uses of this kind of tools.

Resources

Source code