On Monday I described the different ways time and events are handled in continuous and discrete-event simulations. Today I want to go into a little more detail about how those things work in a discrete-event simulation because the internal architecture is more complex–and more interesting.
In order to have something to simulate the model will have to be populated with entities that either change or perform actions. They may all exist at the beginning of the simulation run, they may be introduced into the system during the course of the run, or a combination of these methods can be used. If the simulation is at all interesting or complex the state of each entity will be updated many times during its existence in the model. The state of each entity can be defined by one or more characteristics of the entity, and any number of those characteristics can be examined or modified during each simulated event.
Events are generated in a number of ways. The arrival of an entity into the system is an obvious example but other examples have to do with movement, the start or completion of some action, an entity’s removal from or placement into a pool or queue, a scheduled event, or some other mechanism. Each event causes a timing entry to be generated in the model and those are stored in a time-ordered structure that holds all events that are set to occur as the simulation runs. The simulation continually picks the first entry in the event list and performs actions defined to occur at that time. Events can change any characteristic of an entity, spawn or destroy other entities, begin a process, end a process, modify some value, or place the entity in a queue or pool where it needs to wait for something.
Roughly speaking there are two things an entity can be doing at any given time. It can be waiting to complete an action in which it is involved or it can be waiting for the completion of an action in which some other entity or process is involved. Examples of the former are performing an operation or undergoing an operation. Moving from one place to another may be thought of as one of those two possibilities. Examples of the latter are waiting in a queue for entities ahead of it to complete processes or waiting for some resource to become available or waiting in a pool to be called for a scheduled event or an event generated as part of some other process.
Let’s look at each of these in turn.
Wait for an action to complete in which the entity is involved: Suppose an entity enters the system at some time. It then needs to move to some place (this can be physical or logical) and the movement will take some amount of time. Assuming the arrival event is currently being processed, the action of the simulation will be to create a new event, assign it the details of the new location, assign it a future time when the action will be completed, and place the event in the future events queue. The simulation will then stop processing the current event, retrieve the next event from the future events queue, and process that. Eventually the simulation will come to the event designating the end of the original event and process that.
Wait for an action to complete in which some other entity or process is involved: The result of completing an operation may result in an entity being placed in a queue or pool. In this case the entity simply waits somewhere for other events to happen. Eventually, one of those events will involve the entity in question, and some other process will begin. The change in a specific value may also spawn a new action.
The mechanisms described define a need for a few constructs to manage events. I’ll use the same ones James O. Henriksen defined in his SLX language, which is an extremely powerful, general purpose, C-based programming language that includes features to handle discrete-event mechanisms.
- When an event completes the clock advances to the time of the next event in the future events queue. The next event is then retrieved from the head of the queue.
- When a process needs to wait for a known period of time. This means that the current event finishes and a new event is defined and placed in the future events queue at the known future time (current time plus elapsed time increment). When the simulation finally processes the new event the process is complete.
-
When a condition defined by one or more variables becomes true an event is fired. This means that the program must evaluate the expression when any of the variables is modified, which can get complex. This construct may be thought of as wait… until. The program must maintain its own structure of entities waiting for specified conditions to become true. Advanced languages like SLX do this automatically. Note that the condition might be based on the availability of other entities. For example, if a pool of ten maintenance workers has been defined, and a process needs five to begin, but only three are available, the process in question will have to wait. Some other event will be processed instead and then the condition can be reevaluated.
Events are shown as triangles while the related entities are shown as circles.
The mechanism of waiting in a queue does not need to be handled by a dedicated language construct. It is handled using the mechanisms already described.
