CSci 405: Computer Simulation
Spring Semester 2000
Lecture Notes

Introduction to Discrete-Event Simulation

These notes are based, in part, on material from:

1. Chapter 3 of the book Practical Process Simulation: Using Object-Oriented Techniques and C++ by Jose' M. Garrido (Artech House, 1999)

Modeling of Dynamic Systems

Assumption for our study:

Our models will execute on sequential computers.

The techniques used on a parallel computer may differ.

Focus of our study:

dynamic stochastic systems -- systems whose behavior changes with time and have some uncertainty

state:

expressed as a function of time

event:

an instantaneous occurrence that changes the state of the system

-- initiates the corresponding operation

operation:

a sequence of activities that changes the state of the system

activity:

the smallest unit of work -- executed in finite time

process:

a sequence of events in chronological order

-- the set of activities needed to carry out the state changes corresponding to the events

Processes represent the life of entities 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

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

3. utility routines
   • generate random numbers from common probability distributions
   • gather statistics

Time in Simulation

In a simulation we deal with two notions of time:

• simulation time -- the time on the simulation clock -- the virtual 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

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

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

• Each coroutine typically has a current phase attribute which indicates the phase to execute next.

Object-Oriented Modeling and Process Simulation

• Active entities are modeled as processes.

• A process type in the model is represented as a class that implements appropriate process (coroutine) 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 of the class.

• The behaviors of a process are represented as operations that can be performed by or performed on objects of the class.

• Resources (i.e., passive entities) of the model are represented as classes that do not exhibit the process (coroutine) 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

UP to CSCI 405 Lecture Notes root document?