An Introduction to Discrete-Event Simulation

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 process.

The techniques used on parallel computers may differ.

dynamic stochastic systems:

systems whose behavior changes with time and have some uncertainty.

state:

can be expressed as a function of time

event:

an instantaneous occurrence that changes the state of the system

an event initiates a corresponding operation ...

operation:

a sequence of activities that changes the state of the system

activity:

the smallest unit of work

activities have finite durations

observable state changes are assumed to happen at the beginning or ending of activities

process:

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 system

Model programs consist of three levels of software:

1. 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 the model
     

2. model program
   • implements the simulation model
   • executed by the simulation executive

3. utility routines
   • generate random numbers from common probability distributions
   • gather statistics
   • modularity issue: separate generic functions from model-specific behavior
     

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 resources available.

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

General algorithm:

    while simulation time not at end
       increment time by predetermined unit
       if events occurred during time interval
           simulate those events 

Limitations:

• Event executed at end of interval rather than at precise time
• Some intervals may have no events, wasting CPU time

Event-Scanning Executives

General algorithm:

    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 list):

a list ordered by nondecreasing simulation time (e.g., in a priority queue)

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:

1. activity scanning
2. event scheduling
3. process interaction

Activity Scanning

• 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 is executed
• Simulation executive moves from event to event executing those activity sequences whose conditions are satisfied

Event Scheduling

• 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

Process Interaction

• 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 (or notices)
• Each event node indicates the event time and process to which it belongs
• Simulation executive carries out the following tasks:
  • placement of processes at particular points of time in the list
  • 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 reactivated

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
• Algorithm:

      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
              event notice
          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 library.
• 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 behaviors.
• 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 reports).

Discrete Event Simulation Languages

Discrete event simulation packages and languages must provide at least the following facilities:

1. Generation of random numbers from various probability distributions
2. A timing executive or time flow mechanism to provide an explicit representation of time
3. List processing mechanisms to create, delete, and manipulate objects as sets or members of sets
4. 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 lists):

• Processes
  + "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.
• Coroutines
  + 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.
• Objects
  + 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.
• Events
  + 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.