Notes and Further Reading

One of the first proposals for thread creation was the fork L command, which transfers control to the statement labeled L and also allows control to pass to the statement after fork. In this way, two concurrently executing threads of control are created. A join command was provided to allow the two threads to rejoin execution. The first thread to reach join blocks until the second thread also executes the command. Only a single thread executes after the join. Unstructured use of fork and join leads to extremely complex multi-threaded programs. The UNIX operating system has a version of the fork command with no label. The fork operating system call creates a complete copy of the calling process and starts it executing. The fork call returns a result, which lets a process determine whether it is the parent or child.

To resolve the problems caused by unstructured use of fork and join, Dijkstra (1965) proposed what later became the cobegin..coend construct:

• cobegin P; Q coend

P and Q are executed concurrently as separate threads until both have terminated. The construct can easily be generalized to more than two threads. It was proposed for use in block-structured languages such as Algol. In these languages, the main structuring tools are procedures and procedure activations rather than classes and objects. Storage for procedure activations is managed as a stack in these languages and the addition of threads created using the cobegin..coend construct requires a tree of stacks, sometimes called a “cactus” stack.

The Java thread model does not enforce this degree of structure on thread execution. A thread can continue executing after the thread that created it has terminated. This is more appropriate in an object-oriented language where we are generally less concerned with the lifetime of objects. Storage is managed by a heap structure. Objects exist until they are garbage collected and threads exist until they terminate, at which point their storage can also be garbage collected. Java provides the ThreadGroup class to manage collections of threads and to enforce security policies by dynamically restricting access to Thread operations. For example, a thread may only stop() another thread if both are in the same group. By default, each thread is created in the same ThreadGroup as its creator. We have been able to ignore ThreadGroups in the examples since all threads are created in the default group provided by browsers for applet execution.

In this chapter, we have dealt with programs where dynamic thread creation and termination can be modeled by a fixed set of cyclic processes. The more general problem is to model programs in which the configuration of threads and monitors evolves as execution proceeds. For this sort of program, using FSP, each configuration must be enumerated. The program can then be modeled as the composition of its possible configurations. To address the problem of describing concurrent systems in which configuration changes dynamically, Robin Milner introduced the π-calculus (Milner, Parrow and Walker, 1992). This permits an elegant and concise description of dynamic systems. However, in general, these π-calculus descriptions are not amenable to the form of state exploration analysis that we use for FSP descriptions.

The idea of bounded delays to provide a class of resource allocation strategies is due to Dijkstra (1972a). These strategies can be characterized as satisfying a set of safe scheduling rules for resource allocation to a fixed pool of m processes from a pool of n reusable resources:

1. No process should wait for resources unless some other process is using resources.

2. If process i has requested resources, not more than k other processes can be given their requested resources before satisfying process i (for some bound k ≥ m – 2).

3. The number of resources in the pool plus the sum of the number allocated to processes equals n.

The first two rules avoid resource starvation for an individual process and the third rule preserves resource integrity. Allocation from a pool of reusable resources was used as an exercise in rigorous program design at Imperial College in the late 1970s. Students were required to design, verify and implement a resource allocator in SIMULA (Birtwistle, Dahl, Myhrhaug, et al., 1973). The rules were used by Cunningham and Kramer (1978) as an invariant to guide the development and verification of the program. Rule two was subsequently modified as follows to permit simpler implementations and to cater for dynamic systems where there is no bound on the number of processes (Kramer and Cunningham, 1979):

• 2′. If process i has requested resources, not more than k′ subsequently arriving requests can be serviced before i (for some bound k′ ≥ 0).

The golf club problem and the particular formulation described in this book evolved from that experience.

We are grateful to Alexander Höher for his insight into potential problems with the implementation given in the first edition of this book.