24. More Building a Simulation
Part of
CS:2820 Object Oriented Software Development Notes, Spring 2017
|
We were in the middle of adding class Source to our simulation model. Source intersections are places where new cars arrive in the simulation model. The following code describes a source in the description of a traffic network. The first number is the number of cars this source will produce, the second number is the inter-car arrival interval:
interseciton X source 10 3.5
We wrote code to parse this format, and at the end of the initializer, the following stub code was included:
class Source extends Intersection {
int carCount = 99;
float arrivalInterval = 99.99f;
// initializer
public Source( Scanner sc, String name ) throws IllegalName {
...
// BUG: schedule the first arrival
}
// simulation methods
void arrivalEvent() {
// BUG new vehicle arrives
}
...
}
So, how do we flesh out the above. The key comment to note is a comment in our simulation framework describing how to schedule an event:
/** 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 );
}
Our goal today is to flesh out the details of class Source and then start adding detail to the other classes as needed to build on this start.
Suppose we had this code in our model description file file:
interseciton X source 10 0.5
This means that we will schedule 10 cars to arrive at location X, one car every 0.5 time units. Specifically, we will schedule cars to arrive at the following times:
There are two ways to do this. First, we could schedule all of these events from the initializer:
public Source( Scanner sc, String name ) throws IllegalName {
...
for (int i = 1; i <= carCount; i++) {
Simulator.schedule(
i * arrivalInterval,
(float time)->Source.this.arrivalEvent( time )
);
}
}
The disadvantage of scheduling all of the events at the start of time is that it could clutter up the pending event set with large numbers of events. While the best pending event set implementations have execution times that increase as the log of the number of events in the set, the simulation will run at least somewhat slower if the event set is unnecessarily large. Therefore, it makes sense to keep the number of future events small.
One way to do this is to reognize that each source intersection can be thought of logically as a process where each scheduled event causes the next event in the sequence of events at that source. In that case, we write something like the following:
// initializer
public Source( Scanner sc, String name ) throws IllegalName {
...
Simulator.schedule(
arrivalInterval,
(float time)->Source.this.arrivalEvent( time )
);
}
// simulation methods
void arrivalEvent( float t ) {
// BUG: new vehicle arrives at time t
carCount = carCount - 1;
if (carCount > 0) {
Simulator.schedule(
t + arrivalInterval,
(float time)->Source.this.arrivalEvent( time )
);
}
}
In the above code, the initializer just scheduled the first arrivalEvent() and each subsequent arrivalEvent() is scheduled as a side effect of triggering one of the already scheduled events.
Why did we write Source.this.arrivalEvent instead of this.arrivalEvent? To understand this, it is necessary to recall that λ notation in Java is a shorthand for creating an anonymous instance of an anonymous subclass of an abstract class. In this case, using our simulation framework, we are creating an anonymous subclass of class Simulator.Action, and the body of the λ expression is actually the body of the subclass's trigger() method. So, when we wrote:
Simulator.schedule(
arrivalInterval,
(float time)->Source.this.arrivalEvent( time )
);
Class MyAction implements Action {
void trigger( float time ) {
Source.this.arrivalEvent( time )
}
}
MyAction act = new MyAction();
Simulator.schedule( arrivalInterval, act );
In the above long-wided version of the code, where nothing is anonymous, had we written just this instead of Source.this, it would have referred to a field of the object act, which is a member of classmyAction. In the lambda expression, that object and its class still exist, so the meaning of this can still be interpreted as a reference to the anonymous object instead of the object we intend.
We used the term process to refer to the chain of events that is triggered by scheduling the first arrival event in the initializer and all of the arrival events that follow from that initial event at any particular source intersection.
We can similarly describe a stop-light intersection as a process where the light repeatedly changes state, where each state change allows traffic to flow through the intersection from a different incoming road. That process would be an infinite loop.
Similarly, we can describe the sequence of events that follow an individual vehicle through the simulation as a process. That is the view most natural for a driver to take.
The term process used here is extremely similar to the term as used in the field of operating systems, where a process is the sequence of actions taken by one processor as it interprets a program. This is also a sequence of events, where each event is the execution of one machine instruction.
The parallel between discrete event simulation and operating systems is actually a fairly deep parallel. The pending event set in a simulator is very similar to the process scheduling queue in an operating system. The same data structures apply.
Our code for an arrival event at a source intersection has a big hole in it:
// BUG: new vehicle arrives at time t
How do we create a new vehicle? We could create an object of class Vehicle, and then pass this along through the simulation, and if we wanted vehicles to have attributes such as travel itineraries, fuel consumption records or weight, we would need to do this. On the other hand, if vehicles travel at random and retain no memory, we need not create any data objects to represent them, but we still need to deliver notification of the vehicles' travels to the roads and intersections they visit.
This leads us to the following minimal code for the arrival event at a source intersection:
// simulation methods
void arrivalEvent( float t ) {
// new vehicle arrives at time t
// BUG: We could create a vehicle object here.
this.pickRoad().entryEvent( t );
carCount = carCount - 1;
if (carCount > 0) {
Simulator.schedule(
t + arrivalInterval,
(float time)->Source.this.arrivalEvent( time )
);
}
}
In the above code, this.pickRoad() is the code that determines what road the vehicle will follow. If vehicles have plans, pickRoad() will need a parameter so that it can look at the travel plan of the vehicle, but if vehicles are stupid, as in our initial model, no parameters are needed.
Here is an outline of the pickRoad() method. The code makes no pretense of being correct, but rather, outlies the steps we know we need to follow in order to randomly select a road from the list of outgoing roads in an intersection. First, we need to know how many roads there are, then we need to pick a random number in the range of outgoing roads, and then we need to select that road. It takes research to find how to do each of these steps. We will defer that, leaving the job for later, with bug comments marking our unifinished work:
Road pickRoad() {
// BUG: Should return a random road from outgoing list.
int size = outgoing.sizeOf();
int roadNumber = randomIntegerBetween( 0, size-1 );
return outgoing.memberNumber( roadNumber );
// Bug: end of buggy code!
}
After using pickRoad() to find a road, we send our vehicle to it with a call to the entryEvent() method of that road. If we had actually created a vehicle object, we would have to pass that vehicle to the road, but here, we leave out that detail.
We have two choices when it comes to the road entry event. We could schedule that event at the current time, that is, we could write this:
schedule( t, (float time)->this.pickRoad().entryEvent( time ) );
Or we could write the code already given:
this.pickRoad().entryEvent( t );
Some authors of simulation code seem to like scheduling everything, so that there are no naked calls to simulation methods in the code. Basically, this programming approach uses the scheduler as the primary control structure. The useful result of this is that all code in each event service routine is guaranteed to run to completion before any other event service routine runs, so you don't have to worry about partially completed work.
In our object-oriented framework, however, the entryEvent() method we are calling operates on roads, while the call is from within an intersection. Because of our object-oriented programming rules, there is no direct access to the fields of a road from within an intersection, so the fact that we may not be done working on this intersection event has no effect on the code for the road. As long as we are sure of this, we can safely make direct calls to the road entry event instead of scheduling that event to occur at the current time.
What does a road entry event do? We won't finish the job today, but we can create a skeleton with some bug messages:
void entryEvent( float t ) {
//Bug: A vehicle arrives here at time t
Simulator.schedule( t+travelTime, exitEvent() );
//Bug: End of buggy code
}
Here, we commit to only one detail: When a vehicle enters a road, that means that it will leave that road at the end of the road's travel time. We'll leave the details of this until later.