📄 page382.html
字号:
<HTML><HEAD><TITLE>Discrete Event Simulation</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5588" HREF="page383.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5586" HREF="page381.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5580" HREF="page381.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5590" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011510000000000000000">Discrete Event Simulation</A></H2><P>One of the most important applications of priority queuesis in <em>discrete event simulation</em>.Simulation is a tool which is usedto 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 programmimics the system we are studying.<P>The systems studied using<em>discrete event simulation</em><A NAME=27080> </A>have the following characteristics:The system has a <em>state</em><A NAME=27082> </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 theservice 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 discreteevent process as shown in Figure <A HREF="page382.html#figqueueing"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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 customerand the departure of a customer.<P><P><A NAME="27281"> </A><A NAME="figqueueing"> </A> <IMG WIDTH=575 HEIGHT=120 ALIGN=BOTTOM ALT="figure27085" SRC="img1525.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 customerand therefore changes its state 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 pointin <em>simulation time</em><A NAME=27285> </A><A NAME=27286> </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 customerwe can compute the departure time of that customer.So, when a customer arrives at the serverwe <em>schedule</em> an event in the future which corresponds to the departureof that customer.In order to ensure that events are processed in order,we keep them in a priority queue in whichthe time of the event is its priority.Since we always process the pending event with the smallest time nextand since an event can schedule new events only in the future,the causality constraint will not be violated.<P><HR><A NAME="tex2html5588" HREF="page383.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5586" HREF="page381.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5580" HREF="page381.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5590" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -