40. Process Oriented Simulation
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2017
|
From the point of view of the vehicle in our traffic simulation, a trip looks something like this:
vehicle created at source intersection
loop
pick outgoing road
enter outgoing road
reach end of outgoing road
arrive at intersection
while it is not a sink intersection
vehicle destroyed at sink
in more detail:
Intersection currentIntersection
Road currentRoad = null;
[vehicle created at source intersection, setting currentIntersection]
loop
[consult road network to pick outgoing road, setting currentRoad]
[tell currentIntersection that this car is leaving it]
currentIntersection = null;
[tell currentRoad that we are entering it, setting travelTime]
wait for travel time
[tell currentRoad that we're exiting it, setting currentIntersection]
[tell currentIntersection that we've arrived, it may make us wait]
currentRoad = null;
while it is not a sink intersection
vehicle destroyed
The material in square brackets above involves interaction between the code for the vehicle and the code for the road network. We're focusing on the vehicle here, so we'll ignore the details of this interaction.
From the point of view of the infection in our epidemic simulation, the course of infection looks something like this:
Person currentPerson
[infection created at currentPerson]
currentPerson.diseaseState = latent;
wait for random latency time
if (!recover from latent) {
currentPerson.diseaseState = asymptomatic;
wait for random asymptomatic time
if (!recover from asymptomatic) {
currentPerson.diseaseState = symptomatic;
wait for random symptomatic time
if (!recover from symptomatic) {
currentPerson.diseaseState = bedridden;
wait for random bedridden time
if (!recover from bedridden) {
currentPerson.diseaseState = dead;
} else {
currentPerson.diseaseState = recovered;
}
} else {
currentPerson.diseaseState = recovered;
}
} else {
currentPerson.diseaseState = recovered;
}
} else {
currentPerson.diseaseState = recovered;
}
Similarly from the point of view of a simulated person, the world works like this:
currentPerson.diseaseState = uninfected;
currentPerson.place = currentPerson.homePlace;
tell myHomePlace currentPerson is there
while (diseaseState != dead) {
Schedule s = person's next relevant schedule
wait until s.startTime
if (currentPerson.diseaseState not one of bedridden, dead) {
tell currentPerson.homePlace currentPerson is not there
currentPerson.place = s.place;
tell s.place currentPerson is there
wait until s.endTime
tell s.place currentPerson is not there
currentPerson.place = currentPerson.homePlace;
tell currentPerson.homePlace currentPerson is there
}
}
In our event driven framework, we had to chop logical processes like those illustrated above into sequences of events, where each event in the sequence of events representing a logical process schedules the next event in that sequence. That's miserable, but it worked. For class Vehicle we wrote code like this:
class Vehicle {
Intersection currentIntersection
Road currentRoad = null;
Vehicle( float t, Intersection i ) { // constructor
currentIntersection = i;
schedule( t, (float time)->this.pickOutgoing( time ) );
}
// head of loop
void pickOutgoing( float t ) {
// called when vehicle is in an intersection
[consult road network to pick outgoing road, setting currentRoad]
[tell currentIntersection that this car is leaving it]
currentIntersection = null;
[tell currentRoad that we are entering it, setting travelTime]
schedule( t + travelTime, (float time)->this.leaveRoad( time ) );
}
// tail of loop
void leaveRoad( float t ) {
// called when vehicle arrives at the end of a road
[tell currentRoad that we're exiting it, setting currentIntersection]
currentRoad = null;
[tell currentIntersection that we've arrived, it may make us wait]
if is not a sink intersection {
schedule( t, (float time)->this.pickOutgoing( time ) );
} else {
vehicle destroyed
}
}
}
We the events marking the stages of infection were similarly broken into separate events in the epidemic simulator.
It's useful to think in terms of logical sequences of events as processes when designing event-driven programs, but it would be nice to be able to express them as processes.
Languages that support coroutines and threads allow you to write code in terms of explicit processes. We have not covered that here because interprocess communication is its own advanced topic, worth a full semester of work. Courses like operating systems and computer networks provide one introduction into progrmming with processes, while courses on parallel algorithms provide another.
Consider the following bit of code from the process-oriented version of the traffic simulator:
class Vehicle {
... details omitted ...
// tail of loop
void leaveRoad( float t ) {
// called when vehicle arrives at the end of a road
[tell currentRoad that we're exiting it, setting currentIntersection]
/**/ [tell currentIntersection we're here, it may make us wait ]
currentRoad = null;
if is not a sink intersection {
schedule( t, (float time)->this.pickOutgoing( time ) );
} else {
vehicle destroyed
}
}
}
Most of the above code is easy to expand into Java. Consider this bit:
[tell currentRoad that we're exiting it, setting currentIntersection]
Assuming that we write the appropriate methods in the Road class, we can translate this to Java code something like the following:
currentIntersection = currentRoad.exit();
The one piece of code above that does not give way to this simple interpretation is the following:
/**/ [tell currentIntersection we're here, it may make us wait ]
The problem with this code is that it involves inter-process interaction. Each intersection can be seen as a process, waiting for one vehicle to clear the intersection before the next enters, or waiting for the stoplight to change, and each vehicle is similarly a process, traveling down roads and through intersections. These processes must interact each time a vehicle reaches an intersection, so this is an example of inter-process interaction.
The most fundamental of inter-process interaction involves one processfwaiting for some other process to do something before it continues. Interprocess interactions are common in many contexts: multithreaded programs, interaction between programs running under an operating system, interaction between programs running on a multiprocessor computer or a computer with a multicore processor, and interaction between programs that communicate over a computer network.
For example, in a network, a client program may send a message to a server, requesting a service. Typically, the client then waits for the server to reply. In our case the vehicle is acting in the role of the client, asking the intersection for permission to proceed, but we have no message passing facility.
On a multicore or multiprocessor computer, or in a multithreaded programming environment, one way for one process to wait for another is to use a shared variable:
Process A {
...
v = true;
while (v) { /* wait */ }
...
}
Process B {
...
v = false; /* signal that A can continue */
...
}
In general, this is extremely unsafe. Roll-your-own solutions to interprocess interaction are very difficult to debug. This kind of code was typical of how people worked in the 1960s, before general frameworks for interprocess interaction were developed. Sadly, relics of this kind of thinking are still common on today's systems because significant parts of the operating systems we use today were pinned down before general solutions were well understood.
In our case, we have a scheduler in our simulation framework, and we can use its interface in a sensible way. When a logical process has to wait, for another process, the code for that process must be broken at the point where the wait occurs so that the second half may be scheduled when it is supposed to occur. Here is what this does to the code we began with:
class Vehicle {
... mostly unchanged ...
// tail of loop, first half
void leaveRoad( float t ) {
// called when vehicle arrives at the end of a road
currentIntersection = currentRoad.exit( t, v );
currentIntersection.enter( t, currentRoad, /* WHAT GOES HERE */ );
}
// tail of loop, second half
void finishLeaveRoad( float t ) {
currentRoad = null;
if is not a sink intersection {
schedule( t, (float time)->this.pickOutgoing( time ) );
} else {
vehicle destroyed
}
}
}
The comment /* WHAT GOES HERE */ in the above code is best answered by looking in the code we'll need inside implementations of Intersection:
class SomeKindOfIntersection extends Intersection {
...
void enter( float t, Road r, Something s ) {
// A vehicle wants to enter this intersection from road r at time t
if (allowed) {
// the intersection is clear
Simulator.schedule( t, s );
} else {
// the intersection is blocked
getqueue( r ).add( s );
}
}
}
Here, we see that, if the intersection is clear, whatever was passed as a parameter is scheduled, while if it is blocked, that same thing is queued up in some queue that depends on the incoming road until such time as the intersection is clear. Clearing the intersection will depend, for example, on some other vehicle leaving the intersection, or on the state of the stoplight changing, or on some similar detail.
So, the thing we pass to the intersection will be the same as the thing we pass to the scheduler! This means the code in class vehicle will look like this:
// tail of loop, first half
void leaveRoad( float t ) {
// called when vehicle arrives at the end of a road
currentIntersection = currentRoad.exit( t, v );
currentIntersection.enter( t, currentRoad,
(float time)->finishLeaveRoad( t )
);
}
And, it means that the type of the class of the final parameter to the Intersection.enter method is Simulator.Action. That, is, the correct header for that method is:
class SomeKindOfIntersection extends Intersection {
...
void enter( float t, Road r, Simulator.Action s ) {
...
}
}
It took a long time for people to invent a systematic way of doing this back in the late 1960s. Sadly, the general solution, invented by a student of E. W. Dijkstra in the Netherlands, was published in 1968, but did not achieve significant traction until after significant parts of Unix were developed. As a result, these ideas made it into Unix (and Linux, which is Unix compatible) as afterthoughts. Design by afterthought almost always produces messy results that are never used in many applications that need them.
What we really ought to do is introduce tools into our class Simulation to package the ideas above. The classic packaging, dating back to the time of Dijkstra, is as a new public scheduler class, Semaphore (named after railroad semaphore signals) with two methods, wait() and signal().
If s is a semaphore and a is a semaphore action, then s.wait(a) either schedules a immediately or it sets a aside until it can be done. s.signal() tells the semaphore that if some action is waiting, it can go. What Dijkstra's student discovered is that the semaphore should behave, logically, like an integer. To a user, it is as if the wait operaiton decrements the integer, guaranteeing that it will never go negative by waiting. To a user, it is as if the signal operation increments the integer, which might allow a blocked action to continue.
Much more can be said about semaphores, and if you take an operating systems course or a parallel programming course, you will see more on this.
In fact, in the code we wrote for the road-network simulator, the logic of semaphores is hidden inside class StopLight. We did not call it a semaphore, nor did we make a general mechanism, but we could have done so.
Here is a proposed implementation of this idea as it might be added to the λ expression version of class Simulator:
public abstract class Simulator {
public interface Action {
void trigger( double time );
}
static void schedule( double time, Action act ) {
Event e = new Event();
e.time = time;
e.act = act;
eventSet.add( e );
}
// other parts of the framework are omitted above
public class Semaphore {
private int count; // count of excess signals
private final LinkedList queue; // queue of excess waits
public Semaphore( int c ) {
count = 1;
queue = new LinkedList();
}
public void signal( double time ) {
if (!queue.isEmpty()) {
schedule( time, queue.remove() );
} else {
count++;
}
}
public void wait( double time, Action act ) {
if (count > 0) {
count--;
schedule( time, act );
} else {
queue.add( act );
}
}
}
This addition to the simulation framework allows, for example, intersections to have a semaphore used to allow just one vehicle in the intersection at a time. This semaphore would have a count that is initially one. To enter the intersection, a vehicle waits on this semaphore. Once the vehicle is unblocked by this semaphore, it signals when it leaves the intersection. That signal either sets the count back to one or lets the next vehicle in.
Packaging that logic as part of the framework reduces the complexity of intersections significantly.
We won't go there, but if you take an operating system course or a parallel programming course, you will most likely see lots more of this!