16. A Simulation Framework
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
We concluded that the pending event set should be declared as follows:
PriorityQueue <Event> eventSet = new PriorityQueue <Event> (
(Event e1, Event e2) -> Float.compare( e1.time, e2.time )
);
Where does this declaration go? We could make it global, but it makes more sense to try to package the entire simulation framework in a class.
Let's call our simulation framework class Simulator:
class Simulator {
static PriorityQueue <Event> eventSet
= new PriorityQueue <Event> (
(Event e1, Event e2) -> Float.compare( e1.time, e2.time )
);
static void schedule( float time, Action a ) {
eventSet.add( new Event( time, a ) );
}
static void run() {
// run the simulation
while (!eventSet.isEmpty()) {
eventSet.remove().trigger();
}
}
}
This framework is incomplete, but it makes clear that outsiders schedule events using schedule() where each event consists of an action and the time at which that action is to be done.
The main simulation method extracts successive events from the event set and triggers them. Presumable, triggering an event causes it to take the specified action.
The question is, where should the class Event be declared? As the above code is structured, events are never seen outside of class Simulator, so we can make class Event a local class. The above code relies on the event initializer to set the fields of each event, and it relies on a method, trigger() to cause the event to trigger the associated action.
That leads us to the following:
class Simulator {
private static class Event {
public float time; // the time of this event
public Action act; // what to do at that time
Event( float t, Action a ) {
time = t;
act = a;
}
void trigger() {
act.trigger( time );
}
}
static PriorityQueue <Event> eventSet =
...
The inner class her is declared to be static. Why? Declaring it to be static makes it illegal for any code in the inner class to reference instance variables of the outer class (of which, in this case, there are none). The Java compiler forbids references to non-static inner classes from static methods, just in case the inner class happens to reference an instance variable of the outer class. If you omit this keyword, the code does not compile.
This works, but as always, there are other ways of expressing the same thing. For example, we could write the code like this, cutting down on the use of object-oriented programming and using the inner class Event just as a data container, with all the logic in the methods of class Simulator:
class Simulator {
private class Event {
public float time; // the time of this event
public Action act; // what to do at that time
}
static PriorityQueue <Event> eventSet
= new PriorityQueue <Event> (
(Event e1, Event e2) -> Float.compare( e1.time, e2.time )
);
static void schedule( float time, Action act ) {
Event e = new Event();
e.time = time;
e.act = act;
eventSet.add( e );
}
static void run() {
// run the simulation
while (!eventSet.isEmpty()) {
Event e = eventSet.remove();
e.act.trigger( e.time );
}
}
}
The above code may be a bit easier to understand, but it is also a bit longer. It may also be slightly faster because it relies on local computations in the methods of class Simulation instead of calls to methods of class Event. Parameter passing to a method that then does the assignment before returning is generally slower than simply doing the assignment.
The difference between these two versions is so small that it hardly matters. Both fit comfortably on one page, even if you bulk them up with comments.
To use this framework, we must have some way of encoding acitons for simulation. The above framework assumes an interface called Action, where each action has a method called trigger() that takes a time as a parameter. There are many potential types of events involving a wide variety of objects and parameters; for each type of event, we can create a subclass of Action that deals with those details. Here is the basic Action interface:
interface Action {
void trigger( float time );
}
Because this is a single-method interface, we can create anonymous subclasses using lambda notation. Consider the following bug notice from our road network example:
// Bug: must schedule this.exit( v, t + travelTime )
We can rewrite this as:
Simulator.schedule(
t + travelTime,
(float time) -> this.exit( v, time )
);
Where does the interface Action belong? We could put it outside class Simulator, or we could make it a public inner class, The latter makes some sense because the interface is only used in the context of scheduling events, and because when it is used with lambda notation, no user ever needs to explicitly name the interface class.
The mechanisms outlined above will generally work exactly as you might expect, but sometimes you may get some very strange results. Consider the above call to Simulator.schedule(), embedded into code that canges the variable v (a reference to a vehicle):
v = vehicle1;
Simulator.schedule(
t + travelTime,
(float time) -> this.exit( v, time )
);
v = vehicle2;
Here, the question is: Which vehicle will the newly scheduled event use? You might hope it is vehicle1, but this is wrong because the action you have scheduled at time t + travelTime is passed by name. The actual parameter v is not evaluated at the time you schedule the event, but rather, it is evaluated later, when the event is triggered. By that time, the value of v has been changed to vehicle2, unless other assignments have been done.
This is easier to understand if you look closely at this line:
(float time) -> this.exit( v, time )
This line is really the definition of the trigger method of an anonymous implementation of subclass of Action. This method is not called by scheduling an event, but just set aside. Only when the event is triggered does the variable v get used.
This raises another question? Does the variable v still exist? Consider this context:
void someMethod( float t, Vehicle v ) {
Simulator.schedule(
t + travelTime,
(float time) -> this.exit( v, time )
);
}
Here, by the time the event scheduled by someMethod() is triggered, someMethod() has returned. You might think that when someMethod() returns, its local variables and parameters, in this case, t and v are deallocated. Conceptually yes, when a method returns, its local variables are usually thought of as being deallocated, but Java uses a garbage collector for storage management.
Using a garbage collector means that memory is not reclaimed until that memory is irrelevant. In the above code, the memory allocated in order to call someMethod() remains relevant until the event is triggered because it is referenced from the action that is referenced by the event that is held in the pending event set. Only when that event is forgotten will the garbage collector be able to reclaim the memory for other uses.
Garbage collection algorithms operate by defining a relation "is reachable from" or "is referenced by" that links individual objects in your program. There is an anonymous root object that references every static variable in your program and that references the local variables of the main method. When one method calls another method, there is (in effect) a reference from the caller to the called method that lasts as long as the call.
The simplest garbage collectors for a language like Java wait until the Java run-time system runs out of memory. At that point, they compute the transitive closure of the is-referenced-by relation, starting from the root object in memory. Everything in the set of objects reached during this computation is not garbage and is saved. The collector then collects all of the memory occupied by objects that are outside the reachable set and uses that to allocate new objects.
Simulating the road network needs some initial events. In the case of the network we have defined up to this point, the initial events will be to inject cars into the network from each source. Eventually, sources might inject multiple cars, perhaps using a Poisson arrival distribution for cars, or perhaps one car every 4 seconds, simulating a toll gate with an infinite queue injecting cars onto a toll-road. Initially, however, it will suffice to have each source inject a car. Here is the code for this, added to the initializer for source intersections in the road network:
// initializer
public Source( Scanner sc ) {
super( sc );
Simulator.schedule(
0.0f, // the first car leaves here immediately
(float time)->this.exit(
new Vehicle(),
time
)
);
}
If we wanted, we could make the initializer schedule the first departure from each intersection at some other time, perhaps at the travel time of the source. We could also use the intersection's travel time as the mean time between successive cars generated by the source, but these refinements are matters of making the simulation more accurately model the real world, and that is not the focus of this course.
The second method we need to flesh out in the source intersection is the method for exiting the intersection -- the method that will be called when the event scheduled above is triggered:
public void exit( Vehicle v, float t ) {
/** Simulate v exiting this intersection at time t.
*/
Road d = v.pickRoad( outgoing );
Simulator.schedule( t, (float time)->d.enter( v, time ) );
// Bug: Add code here to schedule the next to leave here.
}
As each vehicle exits the intersection, we have an opportunity to schedule another vehicle to exit.