22. The Event Set

Part of CS:2820 Object Oriented Software Development Notes, Spring 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

The Event Set

The key to discrete-event simulation is a data structure called the pending-event set. This holds the set of all future events, events that have not yet been simulated, that will occur as a result of all events that have already been simulated.

The simulator operates by picking events out of the pending event set in chronological order. Simulating any particular event can involve any combination of changing variables that represent the state of the simulation model, on the one hand, and scheduling future events by adding them to the pending event set.

Some events may only change state variables without scheduling any future events. Other events may schedule future events without making any change to state variables. We can summarize the basic discrete-event simulation algorithm with the following pseudo-code:

// Initialize
PendingEventSet eventSet = new PendingEventSet()
for each event e that we know will happen {
        schedule e on eventSet to happen at time e.time
{
while (eventSet not empty) {
        Event e = next event from eventSet in chronological order
        simulate e by {
                update simulation state variables to account for e at e.time
                schedule zero or more new events at future times
                if appropriate, terminate simulation
        }
}

Note that the above code gives two different ways to terminate the simulation, one by running out of events, and the other involving a specific event, probably one that was scheduled as part of the initialization, that terminates the simulation.

Either approach to termination works equally well. If we have a global constant endOfTime, we can make the event set become empty at that time by checking, as each event is scheduled, to see if it happens before or after the end of time. If it happens before, schedule it. If it happens after, simply discard the event notice.

So what is the event set? It is a priority queue sorted on the time that events are scheduled to happen. The order in which events are supposed to happen has nothing to do with the times at which it can be accurately predicted that they will happen, so the order in which events are placed in the queue has nothing to do with the order in which they are extracted.

Java provides several prioirty queue classes. Class PriorityQueue is based on a heap implementation. ConcurrentSkipListSet is another. We'll luse PriorityQueue here. Unfortunately, the different Java classes that can be used to implement priority queues aren't interchangable.

One of the big differences between the Java alternatives that may concern you is whether the ordering is stable. Stable priority queues guarantee that two elements inserted with equal priority will be dequeued in the order in which they were enqueued. For well formulated simulation models, stable priority queues are not necessary because the order in which simultaneous events are simulated should not matter. In the real world, if two outcomes are possible from simultaneous events, it is highly likely that eithr outcome is correct. Stability may be useful to endure repeatability and easy debugging, but it may also be misleading in cases where the real world behavior is not repeatable because both outcomes are possible.

Simulation Frameworks

There are many different ways of using discrete event simulation. We can describe these as simulation frameworks. They change the way we write the code to schedule events, but they do not change the underlying simulation model.

/** Framework for discrete event simulation.
 */
class Simulator {

	public static abstract class Event {
		public float time;       // the time of this event
		abstract void trigger(); // the action to take
	}

	private static PriorityQueue <Event> eventSet
	= new PriorityQueue <Event> (
		(Event e1, Event e2) -> Float.compare( e1.time, e2.time )
	);

	/** Call schedule(e) to make e happen at its time.
	 */
	static void schedule( Event e ) {
		eventSet.add( e );
	}

	/** Call run() after scheduling some initial events
	 *  to run the simulation.
	 */
	static void run() {
		while (!eventSet.isEmpty()) {
			Event e = eventSet.remove();
			e.trigger();
		}
	}
}

The problem with the above framework is that it requires the user to create large numbers of subclasses of events, where each subclass includes a trigger method that does the required computation. Scheduling an event is actually an example of a delayed computation, and Java provides a tool that allows delayed computation and implicit creation of anonymous subclasses, the lambda expression.

The following simulation framework uses lambda expressions:

/** Framework for discrete event simulation.
 */
class Simulator {

        public interface Action {
                // actions contain the specific code of each event
                void trigger( float time );
        }

        private static class Event {
                public float time; // the time of this event
                public Action act; // what to do at that time
        }

        private static PriorityQueue <Event> eventSet
        = new PriorityQueue <Event> (
                (Event e1, Event e2) -> Float.compare( e1.time, e2.time )
        );

	/** Call schedule to make act happen at time.
	 *  Users typically pass the action as a lambda expression:
	 *  <PRE>
	 *  Simulator.schedule(t,(float time)->method(params,time))
	 *  </PRE>
	 */
        static void schedule( float time, Action act ) {
                Event e = new Event();
                e.time = time;
                e.act = act;
                eventSet.add( e );
        }

	/** Call run() after scheduling some initial events
	 *  to run the simulation.
	 */
        static void run() {
                while (!eventSet.isEmpty()) {
                        Event e = eventSet.remove();
                        e.act.trigger( e.time );
                }
        }
}

When writing a simulation, it is important to begin by settling on a framework, because that determines the sturcture of the simulation code. Changing the framework after you have begun writing code can be messy, but it is not impossible.