The action prefix operator "->" always has an action on its left and a process on its right. In FSP, identifiers beginning with a lowercase letter denote actions and identifiers beginning with an uppercase letter denote processes. The following example illustrates a process that engages in the action once and then stops:

ONESHOT = (once->STOP).

Figure 2.2 illustrates the equivalent LTS state machine description for ONESHOT. It shows that the action prefix in FSP describes a transition in the corresponding state machine description. STOP is a special predefined process that engages in no further actions, as is clear in Figure 2.2. Process definitions are terminated by ".".

Figure 2.2. ONESHOT state machine.

Repetitive behavior is described in FSP using recursion. The following FSP process describes the light switch of Figure 2.1:

SWITCH = OFF,
OFF    = (on  ->ON),
ON     = (off->OFF).

As indicated by the "," separators, the process definitions for ON and OFF are part of and local to the definition for SWITCH. It should be noted that these local process definitions correspond to states in Figure 2.1. OFF defines state (0) and ON defines state(1). A more succinct definition of SWITCH can be achieved by substituting the definition of ON in the definition of OFF:

SWITCH = OFF,
OFF    = (on ->(off->OFF)).

Finally, by substituting SWITCH for OFF, since they are defined to be equivalent, and dropping the internal parentheses we get:

SWITCH = (on->off->SWITCH).

These three definitions for SWITCH generate identical state machines (Figure 2.1). The reader can verify this using the LTS analysis tool, LTSA, to draw the state machine that corresponds to each FSP definition. The definitions may also be animated using the LTSA Animator to produce a sequence of actions. Figure 2.3 shows a screen shot of the LTSA Animator window. The animator lets the user control the actions offered by a model to its environment. Those actions that can be chosen for execution are ticked. In Figure 2.3, the previous sequence of actions, shown on the left, has put the SWITCH in a state where only the on action can occur next. We refer to the sequence of actions produced by the execution of a process (or set of processes) as a trace.

Figure 2.3. LTSA Animator window for SWITCH.

The process TRAFFICLIGHT is defined below with its equivalent state machine representation depicted in Figure 2.4.

TRAFFICLIGHT =
    (red->orange->green->orange->TRAFFICLIGHT).

Figure 2.4. TRAFFICLIGHT.

In general, processes have many possible execution traces. However, the only possible trace of the execution of TRAFFICLIGHT is:

red→orange→green→orange→red→orange→green ...

To allow a process to describe more than a single execution trace, we introduce the choice operator.

The following example describes a drinks dispensing machine which dispenses hot coffee if the red button is pressed and iced tea if the blue button is pressed.

DRINKS = (red->coffee->DRINKS
         |blue->tea->DRINKS
         ).

Figure 2.5. DRINKS state machine.

Figure 2.5 depicts the graphical state machine description of the drinks dispenser. Choice is represented as a state with more than one outgoing transition. The initial state has two possible outgoing transitions labeled red and blue. Who or what makes the choice as to which action is executed? In this example, the environment makes the choice – someone presses a button. We will see later that a choice may also be made internally within a process. The reader may also question at this point if there is a distinction between input and output actions. In fact, there is no semantic difference between an input action and an output action in the models we use. However, input actions are usually distinguished by forming part of a choice offered to the environment while outputs offer no choice. In the example, red and blue model input actions and coffee and tea model output actions. Possible traces of DRINKS include:

red→coffee→red→coffee→red→coffee......
    blue→tea→blue→tea→blue→tea......
    blue→tea→red→coffee→blue→tea→blue→tea......

As before, the LTSA Animator can be used to animate the model and produce a trace, as indicated in Figure 2.6. In this case, both red and blue actions are ticked as both are offered for selection.

Figure 2.6. LTSA Animator window for DRINKS.

A state may have more than two outgoing transitions; hence the choice operator "|" can express a choice of more than two actions. For example, the following process describes a machine that has four colored buttons only one of which produces an output.

FAULTY = (red ->FAULTY
              |blue ->FAULTY
              |green->FAULTY
              |yellow->candy->FAULTY
              ).

The order of elements in the choice has no significance. The FAULTY process may be expressed more succinctly using a set of action labels. The set is interpreted as being a choice of one of its members. Both definitions of FAULTY generate exactly the same state machine graph as depicted in Figure 2.7. Note that red, blue and green label the same transition back to state (0).

FAULTY = ({red,blue,green}-> FAULTY
              |yellow -> candy -> FAULTY
              ).

Figure 2.7. FAULTY.

Non-Deterministic Choice

The process (x->P|x->Q) is said to be non-deterministic since after the action x, it may behave as either P or Q. The COIN process defined below and drawn as a state machine in Figure 2.8 is an example of a non-deterministic process.

COIN = (toss -> heads -> COIN
            |toss -> tails -> COIN
            ).

Figure 2.8. COIN.

Figure 2.9. LTSA Animator window for COIN.

After a toss action, the next action may be either heads or tails. Figure 2.9 gives a sample trace for the COIN process.

In order to model processes and actions that can take multiple values, both local processes and action labels may be indexed in FSP. This greatly increases the expressive power of the notation. Indices always have a finite range of values that they can take. This ensures that the models we describe in FSP are finite and thus potentially mechanically analyzable. The process below is a buffer that can contain a single value – a single-slot buffer. It inputs a value in the range 0 to 3 and then outputs that value.

BUFF = (in[i:0..3]->out[i]-> BUFF).

The above process has an exactly equivalent definition in which the choice between input values is stated explicitly. The state machine for both of these definitions is depicted in Figure 2.10. Note that each index is translated into a dot notation "." for the transition label, so that in[0] becomes in.0, and soon.

BUFF = (in[0]->out[0]->BUFF
        |in[1]->out[1]->BUFF
        |in[2]->out[2]->BUFF
        |in[3]->out[3]->BUFF
        ).

Figure 2.10. BUFF.

Another equivalent definition, which uses an indexed local process, is shown below. Since this uses two index variables with the same range, we declare a range type.

range T = 0..3

BUFF       = (in[i:T]->STORE[i]),
STORE[i:T] = (out[i] ->BUFF).

The scope of a process index variable is the process definition. The scope of an action label index is the choice element in which it occurs. Consequently, the two definitions of the index variable i in BUFF above do not conflict. Both processes and action labels may have more than one index. The next example illustrates this for a process which inputs two values, a and b, and outputs their sum. Note that the usual arithmetic operations are supported on index variables.

const N = 1
range T = 0..N
range R = 0..2*N

SUM        = (in[a:T][b:T]->TOTAL[a+b]),
TOTAL[s:R] = (out[s]->SUM).

We have chosen a small value for the constant N in the definition of SUM to ensure that the graphic representation of Figure 2.11 remains readable. The reader should generate the SUM state machine for larger values of N to see the limitation of graphic representation.

Figure 2.11. SUM.

Processes may be parameterized so that they may be described in a general form and modeled for a particular parameter value. For instance, the single-slot buffer described in section 2.1.3 and illustrated in Figure 2.10 can be described as a parameterized process for values in the range 0 to N as follows:

BUFF(N=3) = (in[i:0..N]->out[i]-> BUFF).

Parameters must be given a default value and must start with an uppercase letter. The scope of the parameter is the process definition. Alternatively, N may be given a fixed, constant value. This may be more appropriate if N is to be used in more than one process description.

const N = 3
BUFF = (in[i:0..N]->out[i]-> BUFF).

It is often useful to define particular actions as conditional, depending on the current state of the machine. We use Boolean guards to indicate that a particular action can only be selected if its guard is satisfied.

The example below (with its state machine depicted in Figure 2.12) is a process that encapsulates a count variable. The count can be increased by inc operations and decreased by dec operations. The count is not allowed to exceed N or be less than zero.

COUNT (N=3)   = COUNT[0],
     COUNT[i:0..N] = (when(i<N)  inc->COUNT[i+1]
                     |when(i>0)  dec->COUNT[i-1]
                     ).

Figure 2.12. COUNT.

FSP supports only integer expressions; consequently, the value zero is used to represent false and any non-zero value represents true. Expression syntax is the same as C, C++ and Java.

In section 2.2, which describes how processes can be implemented in Java, we outline the implementation of a countdown timer. The timer, once started, outputs a tick sound each time it decrements the count and a beep when it reaches zero. At any point, the countdown may be aborted by a stop action. The model for the countdown timer is depicted below; the state machine is in Figure 2.13.

COUNTDOWN (N=3)   = (start-> COUNTDOWN[N]),
    COUNTDOWN[i:0..N] = (when(i>0) tick-> COUNTDOWN[i-1]
                        |when(i==0) beep-> STOP
                        |stop-> STOP
                        ).

Figure 2.13. COUNTDOWN.

The set of possible traces of COUNTDOWN are as given below.

start→stop
     start→tick→stop
     start→tick→tick→stop
     start→tick→tick→tick→stop
     start→tick→tick→tick→beep

(Note that the LTSA Animator reports the STOP state as DEADLOCK. Deadlock is a more general situation where a system of processes can engage in no further actions. It is discussed later, in Chapter 6.)

For example, the alphabet of the COUNTDOWN process of the previous section is {start, stop, tick, beep}. A process may only engage in the actions in its alphabet; however, it may have actions in its alphabet in which it never engages. For example, a process that writes to a store location may potentially write any 32-bit value to that location; however, it will usually write a more restricted set of values. In FSP, the alphabet of a process is determined implicitly by the set of actions referenced in its definition. We will see later in the book that it is important to be precise about the alphabet of a process.

How do we deal with the situation described above in which the set of actions in the alphabet is larger than the set of actions referenced in its definition? The answer is to use the alphabet extension construct provided by FSP. The process WRITER defined below uses the actions write[1] and write[3] in its definition but defines an alphabet extension "+{...}" of the actions write[0..3]. The alphabet of a process is the union of its implicit alphabet and any extension specified. Consequently, the alphabet of WRITER is write[0..3].

WRITER = (write[1]->write[3]->WRITER)
              +{write[0..3]}.

It should be noted that where a process is defined using one or more local process definitions, the alphabet of each local process is exactly the same as that of the enclosing process. The alphabet of the enclosing process is simply the union of the set of actions referenced in all local definitions together with any explicitly specified alphabet extension.

The term process, meaning the execution of a program, originates in the literature on the design of operating systems. A process in an operating system is a unit of resource allocation both for CPU time and for memory. A process is represented by its code, data and the state of the machine registers. The data of the process is divided into global variables and local variables organized as a stack. Generally, each process in an operating system has its own address space and some special action must be taken to allow different processes to access shared data. The execution of an application program in an operating system like Unix involves the following activities: allocating memory (global data and stack) for the process, loading some or all of its code into memory and running the code by loading the address of the initial instruction into the program counter register, the address of its stack into the stack pointer register and so on. The operating system maintains an internal data structure called a process descriptor which records details such as scheduling priority, allocated memory and the values of machine registers when the process is not running.

The above description does not conflict with our previous conception of a process, it is simply more concrete. This traditional operating system process has a single thread of control – it has no internal concurrency. With the advent of shared memory multiprocessors, operating system designers have catered for the requirement that a process might require internal concurrency by providing lightweight processes or threads. The name thread comes from the expression "thread of control". Modern operating systems like Windows NT permit an operating system process to have multiple threads of control.

The relationship between heavyweight operating system (OS) processes and lightweight processes or threads is depicted in Figure 2.14. The OS process has a data segment and a code segment; however, it has multiple stacks, one for each thread. The code for a thread is included in the OS process code segment and all the threads in a process can access the data segment. The Java Virtual Machine, which of course usually executes as a process under some operating system, supports multiple threads as depicted in Figure 2.14. Each Java thread has its own local variables organized as a stack and threads can access shared variables.

In the previous section, we modeled processes as state machines. Since threads are simply a particular implementation of the general idea of a process as an executing program, they too can be modeled as state machines. They have a state, which they transform by performing actions (executing instructions). To avoid confusion in the rest of the book, we will use the term process when referring to models of concurrent programs and the term thread when referring to implementations of processes in Java.

Figure 2.14. Operating system threads.

The operations to create and initialize threads and to subsequently control their execution are provided by the Java class Thread in the package java.lang. The program code executed by a thread is provided by the method run(). The actual code executed depends on the implementation provided for run() in a derived class, as depicted in the class diagram of Figure 2.15.

Figure 2.15. Implementing run() using inheritance.

The class diagrams we use in this book are a subset of the Unified Modeling Language, UML (Fowler and Scott, 1997; Booch, Rumbaugh and Jacobson, 1998). For those unfamiliar with this notation, a key may be found in Appendix D.

Since Java does not permit multiple inheritance, it is sometimes more convenient to implement the run() method in a class not derived from Thread but from the interface Runnable as depicted in Figure 2.16.

Figure 2.16. Implementing run() using the Runnable interface.

A Java Thread object is created by a call to new in the same way that any other Java object is constructed. The two ways of creating a thread corresponding to Figures 2.15 and 2.16 respectively are:

Thread a = new MyThread();
     Thread b = new Thread(new MyRun());

The thread constructor may optionally take a string argument to name the thread. This can be useful for debugging but has no other role. The following outlines the states (in italics) in which a thread may exist and the operations provided by the Thread class to control a thread.

This is not a complete list of operations provided by the Thread class. For example, threads may be given a scheduling priority. We will introduce these extra operations later in the book, as they are required.

We can use FSP to give a concise description of the thread life cycle as shown below. The actions shown in italics are not methods from class Thread. Taking them in order of appearance: end represents the action of the run() method returning or exiting, run represents a set of application actions from the run() method and dispatch represents an action by the Java Virtual Machine to run a thread on the processor.

THREAD       = CREATED,
   CREATED      = (start          ->RUNNABLE
                  |stop           ->TERMINATED),
   RUNNING      = ({suspend,sleep}->NON_RUNNABLE
                  |yield          ->RUNNABLE
                  |{stop, end}     ->TERMINATED
                  |run            ->RUNNING),
   RUNNABLE     = (suspend        ->NON_RUNNABLE

|dispatch       ->RUNNING
                  |stop           ->TERMINATED),
   NON_RUNNABLE = (resume         ->RUNNABLE
                  |stop           ->TERMINATED),
   TERMINATED   = STOP.

The corresponding state machine is depicted in Figure 2.17. States 0 to 4 correspond to CREATED, TERMINATED, RUNNABLE, RUNNING and NON_RUNNABLE respectively.

Figure 2.17. THREAD life cycle.

The model for a timer which counts down to zero and then beeps was described in section 2.1.5 (Figure 2.13). In this section, we describe the implementation of the countdown timer as a thread that is created by a Java applet. The class diagram for the timer is depicted in Figure 2.18.

NumberCanvas is a display canvas that paints an integer value on the screen. An outline of the class, describing the methods available to users, is presented in Program 2.1. It is the first of a set of display classes that will be used throughout the book. The full code for these classes can be found on the website that accompanies this book (http://www.wileyeurope.com/college/magee).

Figure 2.18. Countdown timer class diagram.

public class NumberCanvas extends Canvas {
    // create canvas with title and optionally set background color
    public NumberCanvas(String title) {...}
    public NumberCanvas(String title, Color c) {...}

    //set background color
    public void setcolor(Color c){...}

    //display newval on screen
    public void setvalue(int newval){...}
  }

The code for the CountDown applet is listed in Program 2.2.

public class CountDown extends Applet
                       implements Runnable {
    Thread counter; int i;
    final static int N = 10;
    AudioClip beepSound, tickSound;
    NumberCanvas display;

    public void init() {
      add(display=new NumberCanvas("CountDown"));

display.resize(150,100);
      tickSound =
        getAudioClip(getDocumentBase(),"sound/tick.au");
      beepSound =
        getAudioClip(getDocumentBase(),"sound/beep.au");
    }

    public void start() {
      counter = new Thread(this);
      i = N; counter.start();
    }

    public void stop() {
      counter = null;
    }

    public void run() {
      while(true) {
        if (counter == null) return;
        if (i>0)  { tick(); --i; }
        if (i==0) { beep(); return;}
      }
    }

    private void tick(){
      display.setvalue(i); tickSound.play();
      try{ Thread.sleep(1000);}
      catch (InterruptedException e){}
    }

    private void beep(){
      display.setvalue(i); beepSound.play();
    }
  }

The counter thread is created and started running by the start() method when the CountDown applet is started by the Web browser in which it executes. CountDown implements the Runnable interface by providing the method run() which defines the behavior of the thread. To permit easy comparison between the COUNTDOWN model and the behavior implemented by the run() method, the model is repeated below:

COUNTDOWN (N=3)   = (start-> COUNTDOWN[N]),
     COUNTDOWN[i:0..N] = (when(i>0) tick-> COUNTDOWN[i-1]
                         |when(i==0) beep-> STOP
                         |stop-> STOP
                         ).

The thread counter.start() method causes the run() method to be invoked. Hence, just as the start action in the model is followed by COUNTDOWN[i], sothe run() method is an implementation of the COUNTDOWN[i] process. The index of the process COUNTDOWN[i] is represented by the integer field i. The recursion in the model is implemented as a Java while loop. Guarded choice in COUNTDOWN[i] is implemented by Java if statements. Note that we have reordered the conditions from the model, since in the implementation, they are evaluated sequentially. If the thread is stopped, it must not perform any further actions. In Chapters 4 and 5, we will see a different way of implementing choice when a model process is not implemented as a thread.

When run() returns the thread terminates – this corresponds to the model process STOP. This can happen for two reasons: either i==0 or the thread reference counter becomes null. It can become null if the browser invokes the stop() method – usually as a result of a user requesting a change from the Web page in which the applet is active. The stop() method sets counter to null. This method of stopping a thread is preferable to using the Thread.stop() method since it allows a thread to terminate gracefully, performing cleanup actions if necessary. Thread.stop() terminates a thread whatever state it is in, giving it no opportunity to release resources. Melodramatically, we may think of Thread.stop() as killing the thread and the technique we have used as equivalent to requesting the thread to commit suicide! For these reasons, Sun have suggested that Thread.stop() be "deprecated". This means that it may not be supported by future Java releases.

The implementation of tick() displays the value of i, plays the tick sound and then delays the calling thread for 1000 milliseconds (one second) using Thread.sleep(). This is a class method since it always operates on the currently running thread. The method sleep() can terminate abnormally with an InterruptedException. The code of Program 2.2 simply provides an exception handler that does nothing.

The implementation of beep() displays i and plays the beep sound. The tick() and beep() methods correspond to the tick and beep actions of the model. An implementation must fill in the details that are abstracted in a model.