38. Process Oriented Simulation

Part of CS:2820 Object Oriented Software Development Notes, Spring 2016
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

A Problem

As the last class ended, we had something like this event driven framework, from the vehicle's perspective, on the board:

class Vehicle {
    Intersection currentIntersection
    Road currentRoad = null;
    Vehicle( float t, Intersection i ) { // initializer
        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]
/**/    [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 is potentially a process, so this is an example of inter-process interaction.

Inter-Process Interaction

What we have here is an inter-process interaction, where one process must wait for some other process 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 intersectio 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.

Using the Scheduler

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 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 ) {
        ...
    }
}