24. Building a Simulation
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2020
|
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.
Suppose we had this code in our model description file file:
interseciton X 4 source 20
This means that intersection X, a source intersection, can pass one car every 4 seconds, and has a median inter-arrival time of 20 seconds. To do this, we construct the source intersection so that each event that generates a new vehicle also schedules the generation of the next one:
// Constructor
private void produce( double time ) {
Simulator.schedule(
time + period, // BUG -- need to randomize time of next production
(double t)-> this.produce( t )
);
// BUG -- produce a vehicle v
// BUG -- what is the travel time of a source intersection?
// BUG -- pick an outgoing road r
// BUG -- r.enter( time, v );
System.out.println( this.toString() +": produces at t ="+ time );
}
Here, each production event injects one car into the road network and also schedules the next event. We have several problems with this. First how do we randomize the production times? Second where is the bottleneck implicit in the travel time of the interesection? Third, how do cars select a road and leave the interesection?
The Java library provides a class, Random, where each instance of that class is a stream of pseudo-random numbers. The key word here is pseudorandom. No algorithm can generate truly random numbers. Algorithms are, by their very nature, deterministic unless they rely on an external source of randomness.
Pseudo-random number generators have outputs that appear random, but they are really deterministic. A typical pseudo-random number generator is based on the following skeleton:
SeedType seed = initialValue;
int next() {
seed = f(seed);
return g(seed);
}
The key parts of this are the type of seed, the initial value of seed, the function used to update seed, and how values of seed are converted to the values returned to the user.
Some pseudo-random number generators keep the seed as an array of integers, but most use a integer seed. Java's class Random defines itself as using a 48-bit seed and a linear congruential function. All linear congruential pseudo-random number generators can be described as variations on this function:
int f(int i) {
return (A*i + B) % C;
}
Of course, we need to use an appropriate number of bits for the type int, 48 bits in the case of Java's Random. The key thing is, with the right constants A, B and C, the sequence of values that go in seed appears to be entirely random, except that it recycles after some number of numbers are drawn from the generator. A generator with a 48 bit seed will have a period no longer than 248, and with the right A, B and C, it can have a period longer than 247. That is, the period is longer than 10 ×14. This makes it unlikely that a program will ever see a repeat, so long as it has only one random number stream.
The initial value of seed does not add any randomness. All it does is change where in the cycle we start. By default, Java harvests some randomness from the environment, for example, using the time of day, how many processes have been started on this computer since it was turned on, the time interval between the two most recent Internet transactions, or things like that. This harvested randomness is used to decide where to start in the cycle in order to give greater apparent randomness.
Users can start the generator at any user-selected point, however, in order to get truly deterministic behavior. This is useful primarily during debugging, in order to make it possible to re-run a program after a change and see what that change did without the impact being hidden by randomness.
Note that the values of seed given by a linear congruential pseudo-random number generator are integers uniformly distributed over the range 0 to C–1. Java's class Random always returns the top bits of the number, since the least significant bits output by linear congruential generators tend to be more predictable, and when you ask for a long integer, it concatenates two consecutive 32-bit values.
Java creates floating-point random values between 0.0 and 1.0 by drawing an appropriate integer and then dividing by the range to scale the value into the range required.
The big problem with Java's class Random is that Java allows users to create multiple instances. Each instance has its own seed, but all of them run the same algorithm. As a result, the sequences of values drawn from two different instances of Random can easily end up overlapping. The more streams you create and the more numbers you draw from each stream, the more likely it is that there will be an overlap.
The standard advice for avoiding this problem is: Never ever use more than one instance of a pseudo-random number stream. Seed that stream well, and draw all the random numbers you need from the same stream.
Note, multiplicative congreuence pseudo-random number generators should never be used for cryptography or other secure applications. Good pseudo-random number generators are very hard to build, and ones that are good enough for secure applications are even more difficult. Java's class Random is good enough for simulation applications like ours, and good enough for gaming, but it has its limits.
The first practical consequence of the above is that we should create a single global class that encapsulates the pseudo-random number stream we need. One way to do this is with a class that is never used to construct objects, all it does is group static variables and methods:
class MyRandom {
private MyRandom() {} // constructor only to prevent instantiation
public Random rand = new Random(); // the only random stream
// for repeatable debugging, use Random( 1 ) (or any other fixed constant)
...
}
This works. We've already used this approach to group our error handling methods in class Error. This has the disadvantage that we have to write long winded code like MyRandom.rand.nextInt() whenever we want a random number, and it also prevents us from passing this source of randomness as a parameter.
There's another approach, a classic design pattern called the singleton class:
Class MyRandom extends Random {
private MyRandom() {
super(); // the Random() constructor
// during debugging, we can pass a seed above
}
private final Myrandom stream = MyRandom();
// the only way a user can get access to the only instance of MyRandom
public static MyRandom stream() {
return myStream;
}
// all methods of class Random are available to the user
// new methods
/** exponential distribution
* @param mean -- the mean value of the distribution
* @return a positive exponentially distributed random value
public double nextExponential( double mean ) {
return mean * -math.log( this.nextDouble() );
}
}
Here, werever in our application, we need random values, we write code like this:
static MyRandom rand = Myrandom.stream();
This one line of code looks like it might be calling a factory method to construct a new stream, but it is not. Instead, every single call to MyRandom.stream() will return the same object, whether the declaration is static or not. There is no point in making it anything but static because it will always be the same stream, but if someone forgets and makes this an instance variable, nothing will break, the only cost of this error is an increased cost of object construction.
Had we made stream public, we could have also allowed direct user access to the stream like this:
static MyRandom rand = Myrandom.stream;
So long as the stream is final, this works, but for some singleton objects, static initialization of the singleton does not work, so methods must be provided to allow the user to control the initialization. In that case, the wrapped object cannot be final.
The class declaration above includes one new method to extend Java's class Random and that is a method to return a random number with an exponential distribution. The exponential distribution is the expected distribution of the intervals between events that occur independently. So, the intervals between successive raindrops, the intervals between successive customers arriving at a bank, and the intervals between successive cars on a freeway all tend to obey this distribution until the density of events is so high that they influence each other. Once the raindrops start to collide with each other, once the customers start to jostle, and once the drivers of the cars start to have to adjust their speeds to avoid collisions, the distribution will change.
Log normal distributions are also probably good models of many things in a population model. People's decisions to shop at stores they do not frequently visit may well be best modeled using such a distribution, although the decision to go to a store and the day of the actual visit might not be directly coupled. People may put off many such trips until a weekend.
Returning to the traffic simulation problem, we can now begin to make sense of source intersections:
// Constructor
static MyRandom rand = Myrandom.stream();
private void produce( double time ) {
Simulator.schedule(
time + rand.nextExponential( period );
(double t)-> Source.this.produce( t )
);
System.out.println( this.toString() +": produces at t ="+ time );
}
Here, each production event injects one car into this intersection, where it may travel right through, if no car is in the intersection, or it may have to wait if the intersection is occupied. The mechanism for handling the vehicle after it arrives at the intersection is handled by the arrive method. This can be the same for all intersections, since whatever intersection a vehicle arrives at, it must wait to pass through the intersection if it is already occupied.
Why did we write Source.this.produce instead of this.produce? It turns out that both work, but in early versions of Java, they did not. 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(
time + rand.nextExponential( period ),
(double t)-> Source.this.produce( t )
);
Class MyAction implements Action {
void trigger( float time ) {
Source.this.produce( time )
}
}
MyAction act = new MyAction();
Simulator.schedule(
time + rand.nextExponential( period ),
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 and has no methods named produce. In the lambda expression, that object and its class still exist, but Java hides this fact and allows us to use this, but that happened late in the development of the language.
We use the term process to refer to the chain of events that is triggered by scheduling the first produce event in the initializer and all of the produce 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.
Our code for a produce event at a source intersection has a big hole in it:
// BUG -- produce a vehicle v // BUG -- what is the travel time of a source intersection? // BUG -- pick an outgoing road r // BUG -- r.enter( time, v );
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.
Note that when a vehicle enters a source intersection, the outcome in terms of travel through the source intersection is largely the same as the outcome when a vehicle enters an uncontrolled intersection. In both, the vehicle must wait. This suggests that class Source should be a subclass of NoStop (the class for uncontrolled intersections).
This leads us to the following minimal code for the vehicle production event at a source intersection:
// simulation methods
void produce( float time ) {
// new vehicle enters this intersection at this time
// BUG: We could create a vehicle object here.
this.waiting = this.waiting + 1;
// now see if this vehicle can go through now
if (this.waiting <= 1) { // this is the only vehicle
Simulator.schedule(
time + this.travelTime, // the vehicle drives through
(float t)->Source.this.depart( time )
);
}
Simulator.schedule(
time + rand.nextExponential( period ),
(float t)->Source.this.produce( time )
);
}
In the above code, we assumed that no-stop intersections (including source intersections) count the number of vehicles waiting to get through.
We also assumed a method for vehicle departure. This can be a methof of class noStop:.
void depart( float time ) {
// vehicle departs this intersection at this time
// count vehicles on their way through this intersection
this.waiting = this.waiting - 1;
// now see if any vehicles were waiting and let one through
if (this.waiting >= 1) { // there is another vehicle
Simulator.schedule(
time + this.travelTime, // the vehicle drives through
(float t)->this.depart( time )
);
}
// the departing vehicle picks one of the outgoing roads and enters it
this.pickRoad().enter( time );
}
In the above, we assume that each road object has an enter(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() {
return outgoing.get( rand.nextInt( outgoing.size() );
}
The above code can go in class Intersection, since vehicle navigation decisions do not depend on the class of intersection.