Page 213 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 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.
How do you keep track of which event to simulate next? Each event (arrival or departure) occurs
at a discrete point in simulation time. In order to ensure that the simulation program is correct,
it must compute the events in order. This is called the causality constraint–events cannot change
the past.
In our model, when the server begins to serve a customer you can compute the departure time of
that customer. So, when a customer arrives at the server I schedule an event in the future which
corresponds to the departure of that customer. In order to ensure that events are processed in
order, you keep them in a priority queue in which the time of the event is its priority. Since you
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.

10.3.2 Implementation

This section presents the simulation of a system comprised of a single queue and server as shown
in Figure 10.5. Program 10.5 defi nes the class Event which represents events in the simulation.
There are two parts to an event, a type (either arrival or departure), and a time.

public class Simulation
{
static class Event
extends Association
{
public static final int arrival = 0;
public static final int departure = 1;
Event (int type, double time)
{super (new Db1 (time), new Int (type)); }
double getTime ()
{return ((Db1) getKey ()).doubleValue ();}
int getType ()
{return ((Int) getValue ()).intValue ();}
}
// ...
}
Program 10.5: Event Class

An association is an ordered pair comprised of a key and a value. In the case of the Event class,
the key is the time of the event and the value is the type of the event. Therefore, the events in a
priority queue are prioritized by their times.

Program 10.6 defi nes the run method which implements the discrete event simulation. This method
takes one argument, timeLimit, which specifies the total amount of time to be simulated.

The Simulation class contains a single fi eld, called eventList, which is a priority queue. This
priority queue is used to hold the events during the course of the simulation.
public class Simulation
{
PriorityQueue eventList = new LeftistHeap ();
public void run (double timeLimit)

208 LOVELY PROFESSIONAL UNIVERSITY