The conceptual background
The track system
The operating principle
The interbus system
The control program
Some photographs

The model train system

The conceptual background

Concurrency is a phenomenon that is pretty hard to understand as it may have implications on the overall behavior of complex systems with distributed activities which come in various forms. Standard text books try to explain what is at stake here using some kind of abstract program notation which cannot be comprehended without mentally executing it - an undertaking that is decidedly more difficult than doing the same with sequential programs, often requiring a lot of handwaving. Petri nets have at least the advantage of exposing structural properties of concurrency in graphical form, but again, there is no way around playing the token game, i.e., executing the nets, in order to understand their dynamics.

Concurrency is a relation between two or more activities which are completely independent of each other and can therefore be performed in any order. This is to say that of any two concurrent activities a and b, a may take place before b, b may take place before a, or both may take place at nearly the same time. The interesting part about this is that the state of affairs after both activities have taken place is invariant against execution orders, i.e., the occurrence of both activities is non-deterministic but the result is determinate.

Things are getting a bit more complicated if two or more activities have to use the same resource in a mutually exclusive manner, i.e., only one of them at a time. Then we may have a conflict (of interest) wrt which of the contending activities gets a hold of this resource, or has the conflict resolved in its favor and can proceed. Conflict resolution may be left to arbitration, but if the conflict occurs repeatedly (cyclically) among the same activities, then some notion of fairness must enter the game which ensures that all activities take possession of the resource at about the same rate (or at ratios which all parties involved consider acceptable), or that none of the actions is unduly delayed (or starving to death).

An additional problem arises if each activities tests and changes the state of (a value held by) the resource. Then the outcome after all activities have taken place may critically depend on the order in which they get the resource allocated.

An even more severe problem occurs if the two (or more) activities involved get the same set of resources allocated in incremental steps. Then there may develop constellations in which some activity a holds on to a resource r1 while trying to get another resource r2 which is held in possession by an activity b trying to get a hold of resource r1. Here we have a classical deadlock with both activities coming to a grinding halt.

In order to avoid such unpleasant phenomena as deadlocks and starvation, and to ensure an orderly overall behavior of the entire set of activities, there are known to be certain rules of the game that need to be obeyed:

a critical resource may be taken in possession by at most one activity at a time (the mutual exclusion principle);
an activity must not terminate while in possession of a critical resource as otherwise the resource remains permanently blocked for other activities;
if several activities compete for the allocation of a critical resource, then one of them must succeed eventually, in particular there must be no cyclic waits, to prevent deadlocks;
if an activity applies repeatedly for the allocation of a resource, then the request must be satisfied after finitely many attempts to prevent starvation or, put differently, to enforce fairness.
an activity applying for the allocation of a critical resource must be granted immediate access if no other activity is competing for it;

A single track railway line, partitioned into several consecutive sections or blocks, is the classical example of a system in which these rules of the game must be strictly enforced. Here the moving trains are the activities and the track sections are the critical resources. For the sake of safe operation, each section of the track may be occupied by at most one train at a time. A train entering a section must also leave it again after some finite intervall of time has ellapsed as the entire track would otherwise be blocked. A train trying to enter the next section must be given permission to do so eventually, which excludes situations in which two trains move in opposite directions, with each one of them holding on to a track section claimed by the other one. However, several trains may be in different sections of the track as long as they move in the same direction, which may bring about another problem: trains moving in one direction may monopolize the track while trains trying to move in the other direction may be starving. In order to prevent such situations from occurring, there must be some fairness mechanism controlling the entry from both sides of the track so that both directions are served at about the same rate.

The measures involved in solving this non-trivial organizational problem are described in a Petri net model of a single track system. This net model was the starting point for the construction of our model train system as the perfect vehicle to familiarize students by hands-on experience with the intricacies of controlling complex systems with concurrent activities. This single bidirectionally operated track had to be embedded in an elaborate network of other tracks, including sidings, which would render it possible to repeatedly feed it from both sides with trains, following some pre-specified schedule, to create train constellations which challenge the above rules of the game.

A full coloured Petri net model of an earlier version of our model train system can be found under this link

Jürgen Noss
22.07.2003