- What is an Event
- It is an an action that occurs at an instant in time and changes the state
of a system. For example, in our homework, the arrival of a new patient it is
an event. When it occurs the state of the system changes and we have to take
a number of actions, like: if this patient goes to the nurse or to the doctor;
once there, if it waits in the queue or starts service. Another event is the
completion of service at the nurse [same for the doctor]. When that happens
we have to decide if the patient goes out or to the doctor; if to the doctor
we have to determine if he goes in the queue or starts service. Here is
something that is not an event: the routing decision for a patient at Switch 2
if to go or not to go to the doctor. It is so since the routing decision is
an integral part of what is done for the event when the patient leaves the
nurse. Note that there is a distinction between "Event type" and "Event
instance". "Arrival of a Patient" is an Event type. "Arrival of John Doe" is
an Event instance.
- What is Discrete Event Simulation
- It is a way of simulating [i.e. of analysing models of] systems. It can
be done for systems whose behavior can be expressed in terms of what they do
in correspondence to a certain number of event types. For example, the example
in your homework can be described in terms of what the system does when there
is an Arrival event, or a Nurse Service completion event [departure], or a
Doctor Service completion event [departure]. [It may be convenient to treat
the termination of the simulation also as an event.]
Discrete event simulation is used extensively when trying to predict or analyze
the behavior of computer systems. Systems like chemical plants where the
process being carried out is continuous [i.e. does not have discrete times
where the state changes] cannot be simulated this way.
- Simulation and Global Time
- The simulation starts at at some time G0 equal to INITTIME.
The first event that can occur is the
arrival of the first customer. [Certainly no patient can complete service at
the nurse or doctor since initially no patient is in the clinic.] When will
this arrival take place? Let's assume that it happens after some time interval
whose value is between AMIN and AMAX, say, A1. Thus the first arrival is at
time G1 equal to INITTIME+A1. During the time interval from G0 to G1 nothing
has happened in the system. Thus we say that the "global time" of the system
has advanced from G0 to G1. Now that the first event, the first arrival, has
occurred, what will happen next? Two things are going to happen:
- There will be a next arrival. When? At time G1 plus a random value A2
between AMIN and AMAX.
- The first patient will terminate service at the nurse after a random time
interval S1 in the range S1MIN .. S1MAX, or at the doctor after a random time
interval S1' in the range S2MIN .. S2MAX. Service will terminate at the nurse
or at the doctor depending on the routing decision at SWITCH1. Let's call
S1* the time when the appropriate service will terminate.
Then the two events are going to happen, respectively, at time G1+A2 and
G1+S1*. Say that G2 is the smaller of these two values [if the two values are
equal one is chosen in some fashion].
Then the next event occurs at time G2 and the global time
jumps from G1 to G2. No change of state is possible between two successive
events.
This is how the simulation proceeds. We consider what events are going
to happen
next, we choose the next event that will occur the sooner, and we advance the
global clock to the time of this next event. When an event occurs we do all the
things implied by that event.
- Event Queue and Server Queues
We have seen that we keep in a queue the events that are expected to occur
next. And we have seen that patients wait in a queue to be served by the
nurse or by the doctor. BUT the two kinds of queues are very different.
The queue for events, called Event Queue or Agenda, is a priority
queue where events are kept in sorted order for ascending time stamps of
expected occurrence. New events will be enqueued in the agenda at the
place indicated by the time stamp of the event. We dequeue the
event that has the smallest time stamp.
Instead server queues are FIFOs where we store "patients" in the order
of arrival.
- Generating Random Numbers
Random numbers are used extensively when programming. Thus each system,
application, and language has some means to generate random number.
The random number generators that we usually find produce numbers that
are uniformly distributed in some specified range. For example we may find
a generator of real numbers uniformly distributed in the interval
(0.0, 1.0) or a generator of integer numbers uniformly distributed in the
range (0, MAXVAL), where MAXVAL is a user specified value.
If in Unix you execute
you will be told about the functions rand, rand_r,
and srand.
If you execute
you will be told about the functions random, srandom,
initstate, and setstate.
If you decide to use the function random, you will get integer
values uniformly distributed in the interval (0, (2**31)-1).
Using random you can easily define a function, say,myrandom, that returns
real numbers in the interval (0.0, 1.0). You just call random, float its
result and divide it by (2**31)-1.
Once you have a value in the interval (0.0, 1.0) you can determine a random
number uniformly distributed in any interval (a,b) with the formula
