Transcript Overview

系统仿真
System Simulation
2008
Dept. Computer Science,
Tianjin Uni.
What’s simulation
A simulation is
The imitation of the operation of a real-world
process or system over time.
A technique, whereby a model of a system, is
run in compressed time, to perform
experimentation for analyzing system
performance.
Whether done by hand or on a computer,
simulation involves the generation of an artificial
history of a system, and the observation of that
artificial history to draw inferences concerning the
operating characteristics of the real system.
Discrete system simulation
Simulation Category
General-purpose programming languages
 FORTRAN, C, C++
“build your own, use someone else’s“
Simulation programming languages
 ns-2, QualNet/GloMoSim, Opnet, RTSS
 GPSS/H, SIMAN V
Simulation technology
 Time-driven simulation
 They work on a strictly unit-time basis
 automatically scanning thousands of fixed time
units to discover the next significant change
 Event-driven simulation
 automatically skip to the next known event
 saving execute-time
Model Queuing System
Customers
Queue
Server
Queuing System
Use Queuing models to
 Describe the behavior of queuing systems
 Evaluate system performance
Customer n
Arrival
event
Delay
Begin
service
Activity
End
service
Time
Interarrival
Arrival
event
Begin
service
Delay
End
service
Activity
Time
Customer n+1
example
Single-server queue simulation
 Mean Interarrival time
4.5
 Mean Service Time
3.2
 Standard Deviation of Service Times 0.6
 Number of Customers served 1000
 Server Utilization
0.68362
Maximum Line Length
9
Average Response Time 6.739
Proportion who Spend Four Minutes or More in
System 0.663
Simulation RunLength 4677.74
Number of Departures
1000
RTSS Simulator
-- A model contains two parts
First, a set of processors
 The simulation software stores the processor
parameters, such as service rate etc., in a set
of arrays – “the processor table”.
 Each processor has his own queue to store
waiting jobs.
Second, the characterization of the workload (i.e.
jobs)
 The job parameters, such as job arriving time,
job length of a job etc., are stored in a set of
arrays - ”the job table”.
 The job parameters can be either deterministic
or probabilistic.
RTSS Simulator
events
All events can be divided into three types
 Type 1 marks the arrival of a job in the system
 Type 2 corresponds to a job’s entering a server
 Type 3 corresponds to a job’s exiting from a server
The event service routines are the arrival routine, the
incoming routine and the outgoing routine
There is an event list to drive the simulation process
Each event has 3 elements in the event list
 One element is an event identifier which is used for
identifying the event type.
 The second element is the event time
 The third element is a pointer to the job table
control routine
The control routine is the heart of the simulator,
its loop is executed once for each event handled
At the start of each loop, the control routine
 selects the earliest event in the event list
 calls the corresponding event service routine
 advances the simulation clock to the event
time, removes the event from the event list
The event service routine
 performs the required processing for the job
 determines its next event, calculates the event
time and inserts the next event in the event list
 returns control to the control routine
arrival routine
the arrival routine corresponds to event type 1,
and does the following things:
1. The next event (type 2) for the arriving job is
inserted in the event list.
2. If the arriving job belongs to a job sequence
and it is not the last job of the sequence, a new
job of the sequence is generated and inserted in
the job table.
3. The event (type 1) for the new job is inserted in
the event list.
Random-variant generators
 Routines to generate samples from desired
probability distributions
incoming routine
The incoming routine corresponds to event type 2,
and simulates a job entering a processor; it does
the following things:
1. If the processor is busy, the input job enters a
processor queue.
2. If the processor is not busy, it serves the input
job. The next event (type 3) to occur for the input
job is inserted in the event list.
3. The states of the job and processor are updated
Random-variant generators
 Routines to generate samples from desired
probability distributions
outgoing routine
The outgoing routine corresponds to event type 3,
and simulates a job exiting from a processor; it
does the following things:
1. The processor is released by the output job,
2. Then, the queue of the released processor is
examined; if there are jobs waiting, the one which
has the highest priority is selected from the queue
and scheduled to be served
report routine
A group of variables describes the simulator state
when the simulation clock is advanced by the
occurrence of a series of events.
The report routine records these variables, so
that analysis and statistic programs give the final
simulation result.
Simulation in C++
Main program
 Provides overall control of the eventscheduling algorithm
Clock
 A variable defining simulated time
Initialization subroutine
 A routine to define the system state at
time 0
Min-time event subroutine
 A routine that identifies the imminent
event, FEL
Simulation in C++
Event subroutines
 For each event type, a subroutine to
update system state (and cumulative
statistics) when that event occurs
Random-variant generators
 Routines to generate samples from
desired probability distributions
Report generator
 A routine that computers summary
statistics from cumulative statistics and
prints a report at the end of the
simulation
Start simulation
Obtain input parameters
Initialize subroutine:
Call the time-advance
subroutine
A
B
A
Call appropriate
event subroutine
Simulation
over?
Yes
Report
generator
No
B
Initialize subroutine:
1. Set CLOCK = 0
2. Set cumulative statistics to 0
3. Generate initial events and
place on FEL
4. Define initial system state
Time-advance subroutine:
1. Find imminent event, say i
2. Advance CLOCK to imminent
event time
Event subroutine i :
1. Execute event i : update
system state, entity
2. Collect cumulative statistics
3. Generate future events and
place on FEL
Report generator:
1. Compute summary
statistics
2. print report
example
Single-server queue simulation
main() program
Start simulation
Call Initialization()
Initialize the model
Remove Imminent event
from FutureEventList
Advance time to event time
A
B
A
Call event routine
based on event type
No
Simulation over?
Yes
Call ReportGeneration()
Generate final report
B
Definitions tab. 4.6, p. 108
Variables
 System state
 QueueLength
 NumberInService
 Entity attributes and sets
 Customers
Variables(cont’d)


Future event list
 FutureEventList
Activity duration
 Service time
Variables(cont’d)

Input Parameters
 MeanInterarrivalTime
 MeanServiceTime
 SIGMA, Standard deviation of service
time
 TotalCustomers, stopping criteria
Variables(cont’d)


Simulation variables
 Clock
Statistical Accumulators
 LastEventTime
 TotalBusy
 MaxQueueLength
Statistical Accumulators
 SumResponseTime
 NumberOfDepartures
 LongService, Number of customers who
spend 4 or more minutes
Variables(cont’d)
Summary statistics
 RHO = BusyTime/Clock
 AVGR : average response time
 PC4 : Proportion of customers who spend 4
or more minutes at the checkout counter
Functions
exponential ( mu )
normal ( xmu, SIGMA )
Subroutines
Initialization
ProcessArrival
ProcessDeparture
ReportGeneration
Class Event{
Friend bool operator < (const Event& e1, const
Event& e2);
Friend bool operator == (const Event& e1, const
Event& e2);
public:
Event(){};
enum EvtType { arrival, departure };
Event ( EvtType type, double etime) : _type(type),
_etime(etime){};
EvtType get_type() { return _type;}
double get_time() { return _etime;}
protected:
EvtType _type;
double _etime;
};
……
priority_queue<Event> FutureEventList
Queue<Event> Customers
Main( int argc, char* argv[ ] ){
MeanInterArrivalTime = 4.5
……
Long seed = atoi ( argv[1] );
SetSeed(seed);
Initialization();
While ( NumberOfDeparture < TotalCustomers ){
Event evt = FutureEventList.top();
FutureEventList.pop();
Clock = evt.get_time();
If ( evt.get_type() == Event::arrival )
ProcessArrival ( evt );
Else ProcessDeparture ( evt );
}
ReportGeneration();}
Void Initialization (){
Clock = 0;
QueueLength = 0;
……
Event evt( Event::arrival, exponential
( MeanInterArrivalTime ) );
FutureEventList.push ( evt );
}
Void ProcessArrival( Event evt ){
Customer.push ( evt );
QueueLength ++;
If ( NumberInService == 0 )
ScheduleDeparture ();
Else TotalBusy += ( Clock – LastEventTime );
If ( MaxQueueLength < QueueLength )
MaxQueueLength = QueueLength;
Event next_arrival ( Event::arrival, Clock +
exponential
( MeanInterArrivalTime )
);
FutureEventList.push ( next_arrival );
LastEventTime = Clock;
}
Void scheduleDeparture () {
double ServiceTime;
while( ( ServiceTime = normal
( MeanServiceTime, SIGMA ))
< 0 );
Event depart ( Event::departure, Clock +
ServiceTime );
FutureEventList.push ( depart );
NumberInservice = 1;
QueueLength --;
}
Void ProcessDeparture ( Evevt evt) {
Event finished =
Customers.front ();
Customers.pop ();
if ( QueueLength )
ScheduleDeparture ();
else NumberInService = 0;
double response = Clock – finished.get_time ();
SumResponseTime + = response;
……
NumberOfDepartures ++;
LastEventTime = Clock;
}
Void ReportGeneration (){
double RHO = TotalBusy/Clock;
double AVGR = SumResponseTime/
TotalCustomers;
double PC4 =
((double)LongService)/
TotalCustomers;
……
}
Mean Interarrival time
4.5
Mean Service Time
3.2
Standard Deviation of Service Times
0.6
Number of Customers served
1000
Server Utilization
0.68362
Maximum Line Length
9
Average Response Time 6.739
Proportion who Spend Four Minutes or More in
System
0.663
Simulation RunLength 4677.74
Number of Departures
1000