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 otherand can therefore be performed in any order. This is to say that of any two concurrent actions 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 actions have taken place is invariant against execution orders, i.e., the occurrence of both actions is non-deterministic but the result is determinate.

Things are getting a bit more complicated if two or more actions 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 actions 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 actions, then some notion of fairness must enter the game which ensures that all actions 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 action tests and changes the state of (a value held by) the resource. Then the outcome after all actions 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) actions 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 certain rules of the game that need to be obeyed: