📄 page383.html
字号:
<HTML>
<HEAD>
<TITLE>Discrete Event Simulation</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html6661" HREF="page384.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page384.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6659" HREF="page382.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page382.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6653" HREF="page382.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page382.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6663" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6664" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0012510000000000000000">Discrete Event Simulation</A></H2>
<P>
One of the most important applications of priority queues
is in <em>discrete event simulation</em>.
Simulation is a tool which is used
to study the behavior of complex systems.
The first step in simulation is <em>modeling</em>.
We construct a mathematical model of the system we wish to study.
Then we write a computer program to evaluate the model.
In a sense the behavior of the computer program
mimics the system we are studying.
<P>
The systems studied using
<em>discrete event simulation</em><A NAME=27660> </A>
have the following characteristics:
The system has a <em>state</em><A NAME=27662> </A>
which evolves or changes with time.
Changes in state occur at distinct points in simulation time.
A state change moves the system from one state to another instantaneously.
State changes are called <em>events</em>.
<P>
For example, suppose we wish to study the
service received by customers in a bank.
Suppose a single teller is serving customers.
If the teller is not busy when a customer arrives at the bank,
the that customer is immediately served.
On the other hand,
if the teller is busy when another customer arrives,
that customer joins a queue and waits to be served.
<P>
We can model this system as a discrete
event process as shown in Figure <A HREF="page383.html#figqueueing" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page383.html#figqueueing"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
The state of the system is characterized by the state of the server
(the teller),
which is either busy or idle,
and by the number of customers in the queue.
The events which cause state changes are the arrival of a customer
and the departure of a customer.
<P>
<P><A NAME="27868"> </A><A NAME="figqueueing"> </A> <IMG WIDTH=575 HEIGHT=117 ALIGN=BOTTOM ALT="figure27665" SRC="img1577.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1577.gif" ><BR>
<STRONG>Figure:</STRONG> A Simple Queueing System<BR>
<P>
<P>
If the server is idle when a customer arrives,
the server immediately begins to serve the customer
and therefore changes state its to busy.
If the server is busy when a customer arrives,
that customer joins the queue.
<P>
When the server finishes serving the customer,
that customer departs.
If the queue is not empty,
the server immediately commences serving the next customer.
Otherwise, the server becomes idle.
<P>
How do we keep track of which event to simulate next?
Each event (arrival or departure) occurs at a discrete point
in <em>simulation time</em><A NAME=27872> </A><A NAME=27873> </A>.
In order to ensure that the simulation program is correct,
it must compute the events in order.
This is called the <em>causality constraint</em>--events cannot change the past.
<P>
In our model, when the server begins to serve a customer
we can compute the departure time of that customer.
So, when a customer arrives at the server
we <em>schedule</em> an event in the future which corresponds to the departure
of that customer.
In order to ensure that events are processed in order,
we keep them in a priority queue in which
the time of the event is its priority.
Since we always process the pending event with the smallest time next
and since an event can schedule new events only in the future,
the causality constraint will not be violated.
<P>
<HR><A NAME="tex2html6661" HREF="page384.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page384.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6659" HREF="page382.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page382.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6653" HREF="page382.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page382.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6663" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6664" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -