2.2 Implementing Processes

2.2 Implementing Processes

At the beginning of this chapter, we introduced a process as being the execution of a program or subprogram. In the previous section, we described how a process could be modeled as a finite state machine. In this section, we will see how processes are represented in computing systems. In particular, we describe how processes are programmed in Java.

2.2.1 Operating System Processes

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.

Figure 2.14: Operating system threads.

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.

2.2.2 Threads in Java

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.

2.2.3 Thread Life Cycle

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.

• Once created, start() causes a thread to call its run() method and execute it as an independent activity, concurrent with the thread which called start().

• A thread terminates when the run() method returns or when it is stopped by stop(). A terminated thread may not be restarted. A thread object is only garbage collected when there are no references to it and it has terminated.

• The predicate isAlive() returns true if a thread has been started but has not yet terminated.

• When started, a thread may be currently running on the processor, or it may be runnable but waiting to be scheduled. A running process may explicitly give up the processor using yield().

• A thread may be non-runnable as a result of being suspended using suspend(). It can be made runnable again using resume().

• sleep() causes a thread to be suspended (made non-runnable) for a given time (specified in milliseconds) and then automatically resume (be made runnable).

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.

2.2.4 Countdown Timer Example

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.

Figure 2.18: Countdown timer class diagram.

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

Program 2.1: NumberCanvas class.

 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.

Program 2.2: CountDown applet class.

 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], so the 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.