Transcript Event - Systems and Computer Engineering

Discrete Event Simulation
Discrete Event Simulation
• Purpose
– Used to study quantitative system behaviour
when analytic queueing theory is difficult to
apply or when analytic modelling assumptions
are not valid
• Relies on Queues and Lists
Queue ADT Revisited
• ADT Review
– Lists were positional
– Stacks were last in first out
– Queues
• Queues are first-in-first-out
• Can have variants, priority queues etc..
• Methods
–
–
–
–
–
queue() // constructor, create an empty queue
queueIsEmpty() // Determine whether queue is empty
queueAdd(newItem, Success) // Add newItem to Queue
queueRemove(success) // Remove item from front of queue
getQueueFront(success) // Return front item but leave it in the
queue (Peek)
Queue ADT
•
•
•
•
Implementations
Array, or list
Like stack, you can use a List ADT
Why distinguish between these ADTs at all?
– If you only use the properties of a stack, then
calling it a stack helps others understand the
program better
• Same with lists and queues in general
• The ADTs are building blocks
Discrete Event Simulation
• Simulation
– Develop an abstract model of a system that includes:
• Entities:
– Customers (for ex: people that need to fill their cars with gas)
– Resources (queues and service centres) (for ex: gas pump)
• Events
– Events cause changes in system state, usually things that cause the movement of
customers between queues
– Arrival, completions
• Attributes of entities
– Time between customer arrivals
– Resource demands of customers at resources (for ex: the time needed for fill-up:
pump gas and pay)
– Use the model to answer questions
• What is the mean response time of customers that stop for gas?
• What percentage of the time is the pump in use for fill-up?
• Types of models
– Open models
• Infinite number of customers, they arrive with a certain rate
regardless of how long it takes to get service
• Gas station on the 401
– Closed models
• Fixed number of customers, rate of arrivals is affected by
customer response times
• Gas station for a taxi fleet with 10 taxis
Open single server queue
(Simulation terminology)
Entity: building block that describe,
customers, queues, and servers
Events: cause movement of customers
between queues, or other changes
to system state
Customer Arrival Event
(Car arrives for gas)
Customer Entity:
Arrivals
Attributes:
Mean Service time
(for fill-up, could be
expressed in litres)
Mean interarrival time
(Time between arrivals
of cars)
Server Entity:
Attributes:
Scheduling Discipline (Fifo, could be others)
Service Rate
(Different pumps can serve a different
number of litres per second and
different systems for paying)
Server
Queue Entity:
Attributes:
Max Size
(Is there a limit
on how many
cars can queue?)
Departures
Device Completion Event
(Customer has filled-up and
leaves)
Discrete event simulation process
• Events are maintained in a future event list ordered by time
• Discrete event simulation only considers time instants at which
events occur
– System state remains unchanged between events
• Simulation clock used to keep track of simulated time
• To process the next event
– Advance clock to time of event
– Change the system state to reflect the impact of the event
• For example if a customer arrives it must be enqueued
• Generate future events caused by this event
– If the server is idle , the server starts to serve the customer so a device
completion event must be enqueued at the appropriate place in the
future event list
Event scheduling approach
• Keep track of all known future events in an event
list
• Simulation divided into three parts
1. Initialization
• Data structures reflect system state at time zero
2. Main loop
• Take next event from event list
– Event includes time, type, and optional parameters
• Set clock to time of the event
• Call a function to handle event (and cause future events)
– Enqueue a customer or update the event list further
• Quit when termination condition is met
3. Output routine
• Output metrics collected in main loop
Flow chart for events of open single server
queue
Get next event
Advance clock to the time of the event
?
Arrival event
N=N+1
Departure event
Set server idle
Schedule arrival event for future customer
Enqueue this customer
Server
Busy
?
N=N-1
Number of customers in system
Queue Not
Empty
Server Idle
Start service event
Deque this customer, set server busy
Schedule departure event for this customer
?
Queue
Empty
Single server queue pseudo-code
• Initialization:
– Let N be the number of customers in the system,
set N=0
– Set queue to empty
– Set server to idle
– Set event list to empty
– Set clock to zero
– Schedule first arrival event at time zero
– Enter main loop
Event subroutine pseudo-code
• Arrival event
– Increment N by 1 (N is the number of customers queued or in
service)
– Schedule next arrival event: event time = clock + interarrival time
– Enqueue arriving customer
– If server is idle, call subroutine "start service" event
• Start service event
– Dequeue customer
– Set server to busy
– Schedule a departure event: event time = clock + service time
• Departure event
– Decrement N by 1
– Set server to idle
– If queue is non-empty, call subroutine for "start service event"
Options for terminating the simulation
• To leave the main loop and go to step 3
– Call output routine when N exceeds some prespecified quantity
– Schedule "end of simulation" event during
initialization
• Event time equal to desired termination time
• Call output routine when event occurs
– Stop scheduling arrivals after some prespecified time
• Call output routine if no events remain in event list
Closed model exercise
• Consider a closed model with a single server
• Customers think for an average of Z time units between
visits to the server
• How do we adapt the open model simulation pseudo-code
for this purpose?
• Solution:
– Initialization, start with N customers instead of zero, generate an
arrival event for each with a mean inter-arrival time of Z time units
(put them in the future event list)
– Arrival subroutine: don’t generate a future arrival
– Departure subroutine: generate an arrival event with mean value Z
for the customer
Using distributions for generating psuedorandom variates (numbers) for service and
inter-arrival times
• Using distributions
1
– Service times, sleeping times, inter-arrival
times etc
– Can come from many possible distributions
•
•
•
•
Deterministic
Uniform
Normal
Exponential
Cummulative
Density
1
Function
(CDF)
0
Value of variate
Inverse transformation method
• Use a pseudo-random number generator to generate
number between 0 and 1, then compute random variate
using a known inverse function for the CDF
– y = Math.random() returns a psuedo-random double
number betwewn 0.0 and 1.0, the numbers are pseudorandom because they eventually repeat themselves
– Inverse CDFs are well known for many distributions
Deterministic
Uniform
Normal
Exponential
1
0
x=x
Value of variate
x=y
x=
x = - ln y
Examples
• For the exponential distribution: x = - mean ln(y)
• Say random returns the values y = 0.1, 0.5, and 0.3
• Suppose we want an exponentially distributed
random variable with a mean of 4 then:
–
–
–
–
x = - 4 * ln(0.1) = 9.21
x = -4 * ln(0.5) = 2.77
x = -4 * ln(0.3) = 4.81
After a very large number of independent uniformly
distributed values for y, the mean of x will approach 4
Histogram method
• Observe inter-arrival times and service times
• Record them in a table such as follows:
Value
0
1
Probability
• Chose a uniformly distributed pseudo random
variable between 0 and 1, match with appropriate
value
• Better for multi-modal distributions or for values
of unknown distribution
Collection of metrics
• Once we are able to step through a
simulation we can collect metrics
• Suppose we are interested in the following
– The average number of customers waiting for
service
– The standard deviation of the number of
customers waiting for service
– The utilization of the server
• We now consider how to modify the
simulator for this purpose
Collection of metrics for open single server
queue
Get next event
Advance clock
?
Arrival event
N=N+1
Schedule arrival event for future customer
Enqueue this customer
Server
Busy
Departure event
busytime = busytime +
(clock - busystart)
save time of arrival
N=N-1
Set server idle
Queue Not
Empty
Server Idle
Start service event
Deque customer, set server busy
Schedule departure event for this customer
Queue
Empty
busystart = clock
waiting time = clock time of arrival
NWAIT = NWAIT + 1
SWAIT = SWAIT + waiting time
SQWAIT = SQWAIT +
sqr(waiting time)
Collection of metrics
• Mean and variance of customer waiting time
• Initialization
– NWAIT = 0 (Total number of customers that have waited)
– SWAIT = 0 (Sum of waiting times)
– SQWAIT = 0 (Sum of squares of waiting times)
• Waiting time computed when customer begins service
–
–
–
–
–
Remove first customer from queue and get its time of arrival
waiting time = clock - time of arrival
NWAIT = NWAIT + 1
SWAIT = SWAIT + waiting time
SQWAIT = SQWAIT + sqr(waiting time)
• At end of simulation
– Mean waiting time = SWAIT/NWAIT
– Population variance in waiting time = (SQWAIT - sqr(SWAIT)/NWAIT)/NWAIT
– Standard deviation of waiting time is therefore sqrt(population variance)
Utilization
• Start service event
– Busy start = clock time
• Departure event
– Busy time = Busy time + (clock time - Busy
start)
• Output Results
– Utilization = Busy time / Total time
• Where Total time is the final value on the simulation
clock
Instrumenting to collect metrics
• Tedious and error prone
– Need to verify your instrumentation code
• One of the advantages of simulation
packages is that they provide automatic
support for many metrics
Example of Results
• Suppose we have an open model with arrival rate  = 1, 2,
3, 4 arrivals per second
• The time between arrivals (interarrival times are
exponentially distributed)
• The service times have a mean of S = 0.18 seconds and are
exponentially distributed

Rclient = S/(1-U), Userver =  D (from queueing theory)
1
0.2
0.19
2
0.3
0.38
3
0.4
0.57
4
0.8
0.76
5
3.8
0.95
Response time
Response time in Seconds
4
3.5
3
2.5
2
1.5
1
0.5
0
Series1
1
2
3
4
Labmda, arrivals per second
5
Notes
• For this simple system we can use queueing theory
– Simulation will only approximate the exact results of the
queueing theory (because of pseudo random numbers and
finite number of events)
– As U increases we will have to simulate longer and longer
– We always repeat simulations many times with different initial
seeds
• Math.setSeed(long seed) to start the sequence of numbers at a specific
value
– The mean of the mean results of each run is normally
distributed (central limit theorem), therefore we can take a
confidence interval to assess the statistical significance of the
results
• As we vary our assumptions about distributions and sequences
requests for queues -- simulation can give more accurate results
How can OO support simulation?
• Various types of queues can be subclasses of a
Queue class
– First come first served
– Multiple server queues
– Processor sharing
• Each of n queued customers gets 1/nth of the server
• Various types of events can be subclasses of an
Event class
– Arrival events, departure events, other events if they are
needed
• Customer objects can keep track of their own state
as they flow through the system
Simulating Program Behaviour
• Consider the following graph
that describes a program’s
logic
• The edges are annotated with
branching probabilities for
going from one vertex to the
next
• The nodes are labeled with a
service (S) demand at a
processor
Customer starts
1
1
If
2
0.3 0.7
13
1
Loop
3
1
4
1
5
0.1
0.9
6
Customer ends