Page 215 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes The state of the system being simulated is represented by the two variables serverBusy and
numberInQueue. The first is a boolean value which indicates whether the server is busy. The

second keeps track of the number of customers in the queue.
In addition to the state variables, there are two instances of the class ExponentialRV. It implements
the RandomVariable interface defi ned in Program 10.6. This interface defi nes a method called
nextDouble which is used to sample the random number generator. Every time nextDouble is
called, a different (random) result is returned. The random values are exponentially distributed

around a mean value which is specified in the constructor. For example, in this case both
serviceTime and interArrivalTime produce random distributions with the mean value of 100
(lines 9-11).
It is assumed that the eventList priority queue is initially empty. The simulation begins by
enqueueing a customer arrival at time zero (line 12). The while loop (lines 13-44) constitutes the
main simulation loop. This loop continues as long as the eventList is not empty, i.e., as long as
there is an event to be simulated.
Each iteration of the simulation loop begins by dequeuing the next event in the event list (line 15).
If the time of that event exceeds timeLimit, the event is discarded, the eventList is purged, and
the simulation is terminated. Otherwise, the simulation proceeds.
The simulation of an event depends on the type of that event. The switch statement (line 19)
invokes the appropriate code for the given event. If the event is a customer arrival and the
server is not busy, serverBusy is set to true and the serviceTime random number generator is
sampled to determine the amount of time required to service the customer. A customer departure
is scheduled at the appropriate time in the future (lines 24-26). On the other hand, if the server is
already busy when the customer arrives, I add one to the numberInQueue variable (line 29).

Another customer arrival is scheduled after every customer arrival. The interArrivalTime
random number generator is sampled, and the arrival is scheduled at the appropriate time in the
future (lines 30-31).
If the event is a customer departure and the queue is empty, the server becomes idle (lines 34-35).
When a customer departs and there are still customers in the queue, the next customer in the
queue is served. Therefore, numberInQueue is decreased by one and the serviceTime random
number generator is sampled to determine the amount of time required to service the next
customer. A customer departure is scheduled at the appropriate time in the future (lines 38-40).
Clearly the execution of the Simulation method given in Program 10.6 mimics the modeled
system. Of course, the program given produces no output. For it to be of any practical value, the
simulation program should be instrumented to allow the user to study its behavior.

Example: The user may be interested in knowing statistics such as the average queue
length and the average waiting time that a customer waits for service. And such instrumentation
can be easily incorporated into the given framework.

10.4 d-Heaps

The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in
which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap.
The d-ary heap consists of an array of n items, each of which has a priority associated with it.
These items may be viewed as the nodes in a complete d-ary tree, listed in breadth fi rst traversal
order: the item at position 0 of the array forms the root of the tree, the items at positions 1–d are
its children, the next d2 items are its grandchildren, etc. Thus, the parent of the item at position
i (for any i > 0) is the item at position ceiling((i − 1)/d) and its children are the items at positions
di + 1 through di + d. According to the heap property, in a min-heap, each item has a priority

210 LOVELY PROFESSIONAL UNIVERSITY