An Introduction to Discrete-Event
Note: This material is based on the
web page discreteEventSim.html,
Copyright © 2000, H. Conrad Cunningham, who in turn credits
"Chapter 3 of the book Practical Process Simulation: Using
Object-Oriented Techniques and C++ by Jose' M. Garrido
(Artech House, 1999)." I make no claims of any substantial change
or additions to Cunningham's or Garrido's works, but my purpose in
changing the earlier documents is to tailor the material to a
particular syllabus. If there is anything you question here,
please blame me and not the original authors, or refer back to the
original works. -Roger Dannenberg
Modeling of Dynamic Systems
- Assumption for our study:
- Our models will execute on sequential computers in a single
The techniques used on parallel computers may differ.
- dynamic stochastic systems:
- systems whose behavior changes with time and have some
- can be expressed as a function of time
- an instantaneous occurrence that changes the state of the
- an event initiates a corresponding operation ...
- a sequence of activities that changes the state of the system
- the smallest unit of work
activities have finite durations
observable state changes are assumed to happen at the
beginning or ending of activities
- a sequence of events, operationsm, and activities in
chronological order corresponding to the behavior of an entity
in the real system
Structure of Simulation Software
- model program:
- a computer program that implements a simulation model of a
Model programs consist of three levels of software:
- simulation executive
- also called simulation control program or simulator
- controls execution of the model program
- sequences the operations
- modularity issue: separate generic control from details of
- model program
- implements the simulation model
- executed by the simulation executive
- utility routines
- generate random numbers from common probability
- gather statistics
- modularity issue: separate generic functions from
Time in Simulation
In a simulation we deal with two notions of time:
- simulation time -- the time on the simulation clock
-- the virtual time or logical time in the simulated world
- run time -- the amount of processor time consumed
We require run times small enough to get a result within the
However, the simulation time is more important in terms of the
result and how the simulation is organized.
- event time:
- the simulation time at which an event occurs
Techniques for changing the time on the simulation clock:
- fixed time increment -- time slicing -- periodic scan
- variable time increment -- event scan
Synchronous Simulation Executives
while simulation time not at end
increment time by predetermined unit
if events occurred during time interval
simulate those events
- Event executed at end of interval rather than at precise time
- Some intervals may have no events, wasting CPU time
while event list not empty and simulation time not at end
get unsimulated event with earliest time
advance simulation clock to time of event
simulate the event
Both synchronous and event-scanning techniques simulate
parallelism of the processes.
Implementation of Discrete Event Simulation
Operationally, a discrete-event simulation is a chronologically
nondecreasing sequence of event occurrences.
- event record:
- a pairing of an event with its event time
- future event list (FEL) (or just event
- a list ordered by nondecreasing simulation time (e.g., in a
- event (list) driven simulation:
- simulation where time is advanced to the time given by the
first event record from the event list
Requirements for support of discrete-event simulation:
- maintain a future event list
- enable event record creation and insertion into and deletion
from event list
- maintain simulation clock
- (for stochastic simulations) provide utilities to generate
random numbers from common probability distributions
Approaches to Discrete Event Simulation
Three general approaches:
- activity scanning
- event scheduling
- process interaction
- Basic building block is the activity
- Model program's code segments consist of sequences of
activities (operations) waiting to be executed
- An activity sequence's conditions must be satisfied before it
- Simulation executive moves from event to event executing
those activity sequences whose conditions are satisfied
- Basic building block is the event
- Model program's code segments consist of event routines
waiting to be executed
- Event routine associated with each event type -- performs
required operations for that type
- Simulation executive moves from event to event executing the
corresponding event routines
- Basic building block is the process
- System consists of a set of interacting processes
- Model program's code for each process includes the operations
that it carries out throughout its lifetime
- Event sequence for system consists of merging of event
sequences for all processes
- Future event list consists of a sequence of event nodes
- Each event node indicates the event time and process to which
- Simulation executive carries out the following tasks:
- placement of processes at particular points of time in
- removal of processes from the event list
- activation of the process corresponding to the next event
node from the event list
- rescheduling of processes in the event list
- Typically, a process object can be in one of several states:
- active -- process is currently executing
There is only one such process in a system.
- ready -- process is in event list, waiting for
activation at a certain time
- idle (or blocked) -- process is not
in event list, but eligible to be be reactivated by some
other entity (e.g., waiting for a passive resource)
- terminated -- process has completed its
sequence of actions, is not in event list, and cannot be
Implementing Process Simulation
- A code segment represents a process
- Every such code segment is implemented as a coroutine.
A coroutine is a sequential routine that suspends itself and
can be resumed at defined points. A set of coroutines thus
execute together cooperatively, but no more than one is active
at a time.
In languages with thread (lightweight process) support
(e.g., Java), threads will likely be used instead of
coroutines. Unlike coroutines, threads can actually execute
simultaneously if parallel hardware is available.
- Simulation executive activates coroutines one at a time to
carry out operations at a simulation time
- Several process activations with same event time done in
order appearing in event list
While event list not empty and simulation time not at end
get next event notice from event list
advance simulation clock to time of event
activate the coroutine for current process in the
execute the corresponding operation's activities
update process reactivation indicator to indicate
next phase of process and insert event notice
into future event list
deactivate current coroutine
- The reactivation points of a given coroutine (process) are
starting points for different sequences of activities at
different event times.
Each sequence is a phase of the process.
- Each phase will be executed at a different simulation time --
unless they represent simultaneous activities..
Object-Oriented Modeling and Process Simulation
- Active entities are modeled by objects.
- A process type in the model is represented as a class that
implements appropriate process behaviors.
Example: In a traffic simulation, a
Auto class may
implement the behaviors of the automobile process in the model.
- Process-implementing classes will likely need to inherit from
an appropriate "process" base class in the simulation package
- Instances of processes are represented by instances (objects)
of the class.
- The attributes of a process are represented as attributes
(instance variables) of the class.
- The behaviors of a process are represented as methods that
can be performed by instances of the class.
- Resources (i.e., passive entities) of the model are
represented as classes that do not exhibit the process
- Resource-implementing classes will not inherit from the
"process" base class, but may need to inherit from other
appropriate "resource" base classes or interfaces.
- The simulation program will likely include instances or
subclasses of appropriate utility classes (e.g., statistics or
Discrete Event Simulation Languages
Discrete event simulation packages and languages must provide at
least the following facilities:
- Generation of random numbers from various probability
- A timing executive or time flow mechanism to provide an
explicit representation of time
- List processing mechanisms to create, delete, and manipulate
objects as sets or members of sets
- Statistical analysis routines to provide a descriptive
summary of model behavior
- simulation package:
- a set of routines written in a conventional programming
language that can be called by a model program to request
services in the above list
- simulation language:
- a special purpose language that provides high-level language
abstractions and operations to support convenient expression of
simulation model programs
Processes, Coroutines, Objects, and Events
A simulation can use different implementation techniques (+
indicates advantages, − indicates drawbacks in the following
+ "natural" translation from real process descriptions to code,
e.g. sequential behavior translates to sequential code.
− overhead of process switching,
− avoiding unintended interactions through shared variables.
+ similar to processes but lighter-weight
+ programmer controls context switching (when simulation time
advances), avoiding some problems of true concurrency.
− coroutines may not be available
− overhead of stacks and other state.
+ lighter-weight than coroutines.
− activity phases must be implemented separately
− object must store state indicating the next activity since
there is only one entry point where the object is activated.
+ still lighter-weight
+ avoid the need to explicitly allocate/deallocate storage to
represent a process, coroutine, or object.
− all simulated process state must be passed through event
parameters since there is no object or other entity that can
retain state information.