In this post, we present an object-oriented design and implementation of an event-driven G/G/1 queue model simulation using Java. The lecture notes on Computer System Analysis by Raj Jain were very helpful and are highly recommended. In particular, we would like to reference the introductory lectures on Simulation Modeling and Queueing Theory.
Please note that this implementation is provided as a guide/starting point and is not, by any means, complete. We preferred a simple design while keeping in mind where you may wish to extend it.
Update: Download the Eclipse project here.
An event-driven simulation operates by generating and processing events through time. For our queue model, we have two types of events: arrivals and departures or service completion. It is also necessary to determine which events should happen first.
public class Event implements Comparable<Event> {
protected double time;
protected int code;
...
public int compareTo(Event e) {
return Double.compare(time, e.time);
}
}While the design will not make any assumptions about the interarrival or service time distributions, we still need a suitable way to represent them and a couple of concrete implementations for testing.
public abstract class Distribution {
public abstract double generateRV();
}
public class UniformDistribution extends Distribution {
double a, b;
...
public double generateRV() {
return a + rand.nextDouble() * (b - a);
}
}
public class ExponentialDistribution extends Distribution {
double lambda;
...
// Generating exponential variates.
public double generateRV() {
return -1/lambda * Math.log(rand.nextDouble());
}
}
public class NormalDistribution extends Distribution {
double mu, segma;
...
public double generateRV() {
return mu + rand.nextGaussian() * segma;
}
}Now, we should be ready to implement the queue class. We preferred to keep the queue simple by moving data collection into a separate arbitrary observer.
/**
* @author Ahmed Abdelkader
* Licensed under Creative Commons Attribution 3.0
* <http://creativecommons.org/licenses/by/3.0/us/>
*/
public class GG1Q {
protected Distribution arrivalDistribution;
protected Distribution serviceDistribution;
protected double t;
protected PriorityQueue<Event> eventQueue = new PriorityQueue<Event>();
protected int customers;
protected QueueObserver observer;
...
public void run(double duration) {
eventQueue.add(new Event(t + arrivalDistribution.generateRV(), Event.ARRIVAL));
while(t < duration) {
Event e = eventQueue.poll();
t = e.time;
switch(e.code) {
case Event.ARRIVAL:
customers++;
eventQueue.add(new Event(t + arrivalDistribution.generateRV(), Event.ARRIVAL));
if(customers == 1)
eventQueue.add(new Event(t + serviceDistribution.generateRV(), Event.SERVICE));
break;
case Event.SERVICE:
customers--;
if(customers > 0)
eventQueue.add(new Event(t + serviceDistribution.generateRV(), Event.SERVICE));
break;
}
if(observer != null)
observer.stateChanged(this, e);
}
}
...
}
We define the observer interface and implement two sample observers: one for estimating the queue length
PDF and the other for the waiting time
CDF. A composite observer allows more than one observer to collect data of a single run.
public interface QueueObserver {
void stateChanged(GG1Q q, Event e);
void printStats();
}
public class CompositeQueueObserver implements QueueObserver {
protected ArrayList<QueueObserver> observers = new ArrayList<QueueObserver>();
public void addObserver(QueueObserver observer) {
observers.add(observer);
}
public void stateChanged(GG1Q q, Event e) {
for(QueueObserver observer : observers)
observer.stateChanged(q, e);
}
public void printStats() {
for(QueueObserver observer : observers)
observer.printStats();
}
}
public class QueueLengthQueueObserver implements QueueObserver {
protected TreeMap<Integer, Integer> lengthFrequencies = new TreeMap<Integer, Integer>();
protected int total;
public void stateChanged(GG1Q q, Event e) {
if(e.getCode() != Event.ARRIVAL) return;
Integer length = lengthFrequencies.get(q.getLength());
if(length == null) length = 0;
lengthFrequencies.put(q.getLength(), length + 1);
total++;
}
public void printStats() {
System.out.println(getClass().getSimpleName());
for(int length : lengthFrequencies.keySet())
System.out.println(length + "\t" + 1.0*lengthFrequencies.get(length)/total);
}
}
public class WaitingTimeQueueObserver implements QueueObserver {
protected ArrayList<Double> waitingTimes = new ArrayList<Double>();
protected int arrivalIndex, serviceIndex;
protected HashMap<Integer, Double> arrivalTimes = new HashMap<Integer, Double>();
public void stateChanged(GG1Q q, Event e) {
switch(e.getCode()) {
case Event.ARRIVAL:
arrivalTimes.put(arrivalIndex++, e.getTime());
break;
case Event.SERVICE:
waitingTimes.add(e.getTime() - arrivalTimes.get(serviceIndex++));
break;
}
}
public void printStats() {
System.out.println(getClass().getSimpleName());
if(waitingTimes.size() == 0) return;
double acc = 0;
Collections.sort(waitingTimes);
for(int i = 1, j = 0; i <= 10; i++) {
while(acc < i/10.0 && j < waitingTimes.size()) {
acc += 1.0/waitingTimes.size();
j++;
}
System.out.println(waitingTimes.get(j-1) + "\t" + i/10.0);
}
}
}The following test program produced the output below:
public class Main {
public static void main(String[] args) {
GG1Q q = new GG1Q(new ExponentialDistribution(100.0/3600), new UniformDistribution(1, 10));
QueueObserver observer = new QueueLengthQueueObserver();
q.setObserver(observer);
q.run(1000);
observer.printStats();
}
}
QueueLengthQueueObserver
Queue length PDF:
1 0.47058823529411764
2 0.23529411764705882
3 0.058823529411764705
4 0.058823529411764705
5 0.11764705882352941
6 0.058823529411764705
