24. Building a Simulation

Using the Scheduler

Recall the interface to our scheduler in package Simulator:

/** 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 here 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.

Scheduling the departures from a source intersection

Suppose we had this code in our model description file file:

interseciton X source 100 10 0.5

This means that, starting at time 100, we will schedule 10 cars to depart from location X, one car every 0.5 time units. Specifically, we will schedule cars to depart 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 = 0; i < carCount; i++) {
        Simulator.schedule(
            startTime + i * departureInterval,
            (float time)->Source.this.departureEvent( 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 ) {
    ...

    Simulator.schedule(
	startTime,
	(float time)->Source.this.departureEvent( time )
    );
}

This second alternative assumes that each departure event will inject one car into the road network and also schedule the next departure event, if there are any more cars. Here is a start at writing code for this more complex version of an departure event:

// simulation methods
void departureEvent( float t ) {
    // BUG: Must simulate the departure of a new vehicle at time t

    // schedule the next departure, if there is one
    carCount = carCount - 1;
    if (carCount > 0) {
        Simulator.schedule(
            t + departureInterval,
            (float time)->Source.this.departureEvent( time )
        );
    }
}

In the above code, the initializer just scheduled the first departureEvent() and each subsequent departureEvent() is scheduled as a side effect of triggering the previously scheduled event.

Why Source.this.departureEvent?

Why did we write Source.this.departureEvent instead of this.departureEvent? 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(
    departureInterval,
    (float time)->Source.this.departureEvent( time )
);

Class MyAction implements Action {
    void trigger( float time ) {
        Source.this.departureEvent( time )
    }
}

MyAction act = new MyAction();
Simulator.schedule( departureInterval, act );

In this 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.

The Concept of a Process

We use the term process to refer to the chain of events that is triggered by scheduling the first departure event in the initializer and all of the departure 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 particular 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 fairly deep. The pending event set in a simulator is very similar to the process scheduling queue in an operating system. The same data structures apply.

Creating Vehicles

Our code for a departure event at a source intersection has a big hole in it:

// BUG: Must simulate the departure of a new vehicle 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 departure event at a source intersection:

// simulation methods
void departureEvent( float t ) {
    // new vehicle departs at time t
    // BUG: We could create a vehicle object here.
    this.pickRoad().entryEvent( t );

    carCount = carCount - 1;
    if (carCount > 0) {
        Simulator.schedule(
            t + departureInterval,
            (float time)->Source.this.departureEvent( time )
        );
    }
}

In the above code, this.pickRoad() is the code that determines what road the vehicle will follow as it leaves this intersection. 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. We can simply pick an outgoing road at random.

In the above, we assume that each road object has an entryEvent(t) method that is used to tell that road that an intersection has injected a vehicle into that road at time t. If we had actually created vehicle objects, we would have to pass the vehicle itself to the road's entry event.

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!
}

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)->Intersection.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? As usual, we'll start by creating a a skeleton with some bug messages:

void entryEvent( float t ) {
    //Bug:  A vehicle arrives here at time t
    Simulator.schedule( t+travelTime, ()->Road.this.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.