Discrete-Event Simulation: Looking Under The Hood

Yesterday I mentioned a few constructs that a discrete-event simulation system would have to have. They are:

• A time-ordered future events queue where events are created and entered into the queue, and then processed one by one in time order. The clock is incremented to the next time whenever an event completes.
• The ability to suspend a process for a specified amount of time, whereupon the process continues.
• The ability to suspend a process until an external condition becomes true, whereupon the process continues.

The first feature is pretty basic and can be implemented in any language. The events have to have some kind of structure that gets stored in a future events queue. The future events queue can be implemented in a number of ways, though a splay tree appears to be most often chosen. If you are using a dedicated language or tool the details of this implementation will be hidden from you. If you are using a general purpose language you will have to implement this feature.

The items stored in the future events queue have to support access to two important pieces of information: the entity with which the event is associated and the time of the event. If two or more events are scheduled to take place at the same time the items may also have to support access to information that will determine priority. One possible implementation of such an item would be a structure or object consisting of a pointer to an entity, a floating point value for the time, and an integer value for the priority. Many variations on this theme are possible. The ultimate point of processing an event is to be able to jump to a desired piece of code that performs some action.

Note that however long it takes for any piece of code to run, each piece of code performs calculations associated with an instant in time having zero duration. Events handled by the future events queue are associated with the beginning and end of any modeled action that takes non-zero time to complete. If the event is associated with the end of a wait state, either because a specified amount of time elapsed or because some condition finally became true, then another piece of code will run that takes zero time and places the entity into another wait state.

I usually use the term entity to describe something in a model that either acts or is acted upon, but it’s also possible to have events that are just part of the program’s mechanism. For example, a program may fire a process at regular intervals that collects statistics or generates a smoothly advancing time display, but the process isn’t associated with anything being modeled per se. In the case of a modeled entity control of the program will pass to a piece of code associated with a structure or object (you can see why object-orientation might be handy here). In the case of a purely programmatic entity control of the program might pass to a piece of code associated with a standalone procedure or function.

So what should a chunk of event code look like?

In the case of a purely programmatic entity the code might be straightforward. If the code is meant to update a time the code might simply do so (by writing to a display or an event file or both) and return. If the code is meant to gather statistics it might have to scan a list of entities to determine how many are in a given state and either reset or update an increment counter.

In the case of a modeled entity the behavior might be quite complex. Each entity may have a list of destinations to visit or actions to perform. The list of things to accomplish might itself by modular and variable (e.g., different types of entities might have different lists of destinations and the lists may themselves vary under different conditions). It may have to follow a set of rules in order to move from place to place. Regardless of the implementation control of the program has to pass to a desired piece of code that will be dependent on the state of the entity with which the event is associated.

How those pieces of code get written and divided up can vary greatly with different implementations. We know that actions are carried out at various times and take specified amounts of time to complete. Remembering that all code executes in zero-time increments, the trick to designing discrete-event simulation code is to break the sections of code up across wait states. A pseudo-code implementation might look like this:

The point is that you have to specify actions for every possible state and its transitions to every other possible state. That may or may not be easy to do, but at least the implementation in a general purpose language or canned tool is easy to understand. What might be more difficult to understand is an implementation that allows you to write code that looks like normal, procedural code but that has waits embedded directly in it. The SLX language supports writing code in this way and I’ve spent a lot of time thinking about what must be going on under the hood.

The code looks like entire chunks of behavior for an entity are defined as single functions which can have multiple waits. When the waits complete the function’s execution continues at the next statement. I am used to a function calling convention where a current code pointer is pushed onto the stack along with parameters and local variables for the new function. When that function completes the process is unwound by popping all of those items off the stack in reverse order. As each event is peeled off the future events queue the function associated with the active entity gets called. The tricky part of this call is that it might not begin at the first statement but instead some mechanism would have to exist that allowed the code to jump to the statement just after the wait. Similarly, all of the local variables defined within the function would have to be restored from someplace other than the stack. As a practical matter the local variables would actually have to be state variables associated with the entity, and those would likely be stored with the entity’s representation on the heap.

I can’t say for sure what the underlying implementation of SLX or similar languages is, but it’s interesting to contemplate. Its possible that the compiler reorganizes the written code to work as I described in the pseudo-code above, but the execution looks pretty continuous when you step through it in the integrated debugger so that’s probably not what happens. It is certainly interesting to think about how the mechanism would be implemented in a general purpose language. It seems to me that the jump from the beginning of the function to the continuation point could be replicated with goto statements (possibly in combination with case or switch statements). I know, I know, goto‘s are evil… Anyway, such a mechanism would preclude implementation in a general purpose language that does not support them (e.g., Java). Clearly a dedicated store, retrieve, and jump operation would be easy to implement in assembly language generated by a high-level language compiler or interpreter.

An entity may be active in the sense that it carries all of its own logic, state data, and history, or it may be passive in the sense that its behavior is determined entirely by other entities with which it interacts. Different entities in a model might be both active and passive at different times; it’s all up to the implementation.

In a flock of birds it’s probably best to implement each bird as an active entity whose behavior is determined by a (hopefully simple) set of rules based partly on its own motivations and partly based on those of one or more nearby birds.

A pool of maintenance personnel might be represented in an entirely passive way. They start off in the pool and get called away to perform some action for a period of time determined by some other entity or process, and are then returned to the pool. While statistics might be kept on the usage rate of the pool as a whole the behavior and history of each entity might be of no specific interest.

Travelers crossing a land border might have to undergo various kinds of inspections. For example, all travelers of one type might have to go to a dedicated primary inspection, whereupon some of them will go to the port exit or one or more secondary inspections. The traveler’s next destination might be determined by rules associated with the traveling entity while the time each inspection takes might be determined according to roles associated with the inspection station. This would be an example of a hybrid architecture.