A.2.1 Threads

A thread executes a single, sequential program. In Java, a thread is usually a subclass of java.lang.Thread, which provides methods for creating threads, starting them, suspending them, and waiting for them to finish.

First, create a class that implements the runnable interface. The class’s run() method does all the work. For example, here is a simple thread that prints a string.

public class HelloWorld implements Runnable {

  String message;

  public HelloWorld(String m) {

     message = m;

  }

  public void run() {

     System.out.println(message);

  }

}

A Runnable object can be turned into a thread by calling the Thread class constructor that takes a Runnable object as its argument, like this:

String m = "Hello World from Thread" + i;

Thread thread = new Thread(new HelloWorld(m));

Java provides a syntactic shortcut, called an anonymous inner class, that allows you to avoid defining an explicit HelloWorld class:

final String m = "Hello world from thread" + i;

thread = new Thread(new Runnable() {

   public void run() {

      System.out.println(m);

   }

});

This snippet creates an anonymous class implementing the runnable interface, whose run() method behaves as shown.

After a thread has been created, it must be started:

thread.start();

This method causes the thread to run. The thread that calls this method returns immediately. If the caller wants to wait for the thread to finish, it must join the thread:

thread.join();

The caller is blocked until the thread’s run() method returns.

Fig. A.1 shows a method that initializes multiple threads, starts them, waits for them to finish, and then prints out a message. The method creates an array of threads, and initializes them in Lines 2 – 10, using the anonymous inner class syntax. At the end of this loop, it has created an array of dormant threads. In Lines 11 – 13, it starts the threads, and each thread executes its run() method, displaying its message. Finally, in Lines 14 – 16, it waits for each thread to finish, and displays a message when they are done.

Figure A.1 This method initializes a number of Java threads, starts them, and then waits for them to finish.

A.2.2 Monitors

Java provides a number of ways to synchronize access to shared data, both built-in and through packages. Here we describe the built-in model, called the monitor model, which is the simplest and most commonly used approach. We discuss monitors in Chapter 8.

Imagine you are in charge of software for a call center. During peak hours, calls arrive faster than they can be answered. When a call arrives, your switchboard software places that call in a queue, and it plays a recorded announcement assuring the caller that you consider this call to be very important, and that calls will be answered in the order received. An employee in charge of answering a call is called an operator. Each operator dispatches an operator thread to dequeue and answer the next call. When an operator has finished with one call, he or she dequeues the next call from the queue and answers it.

Fig. A.2 is a simple (but incorrect) queue class. The calls are kept in an array Calls, where head is the index of the next call to remove, and tail is the index of the next free slot in the array.

Figure A.2 An incorrect queue class.

It is easy to see that this class does not work correctly if two operators try to dequeue a call at the same time. The expression

return calls[(head++)% QSIZE]

does not happen as an indivisible, atomic step. Instead, the compiler produces code that looks something like this:

int temp0 = head;

head = temp0 + 1;

int temp1 = (temp0 % QSIZE);

return calls[temp1];

Two operators might execute these statements together: they execute Line at the same time, then Line, and so on. In the end, both operators dequeue and answer the same call, possibly annoying the customer.

To make this queue work correctly, we must ensure that only one operator at a time can dequeue the next call, a property called mutual exclusion. Java provides a useful built-in mechanism to support mutual exclusion. Each object has an (implicit) lock. If a thread A acquires the object’s lock (or, equivalently, locks that object), then no other thread can acquire that lock until A releases the lock (or, equivalently, until it unlocks that object). If a class declares a method to be Synchronized, then that method implicitly acquires the lock when it is called, and releases it when it returns.

Here is one way to ensure mutual exclusion for the enq() and deq() methods:

public synchronized T deq() {

  return call[(head++) % QSIZE]

}

public synchronized enq(T x) {

  call[(tail++) % QSIZE] = x;

}

Once a call to a synchronized method has acquired the object’s lock, any call to another synchronized method for that object is blocked until the lock is released. (Calls to other objects, subject to other locks, are not blocked.) The body of a synchronized method is often called a critical section.

There is more to synchronization than mutual exclusion. What should an operator do if he or she tries to dequeue a call, but there are no calls waiting in the queue? The call might throw an exception or return Null, but what could the operator do then, other than try again? Instead, it makes sense for the operator to wait for a call to appear. Here is a first attempt at a solution:

public synchronized T deq() {

  while (head == tail) {};  // spin while empty

  call[(head++) % QSIZE];

}

This solution is not just wrong, it is disastrously wrong. The dequeuing thread waits inside a synchronized method, locking out every other thread, including the switchboard thread that could be trying to enqueue a call. This is a deadlock: the dequeuing thread holds the lock waiting for an enqueuing thread, while the enqueuing thread waits for the dequeuing thread to release the lock. Nothing will ever happen.

From this we learn that if a thread executing a synchronized method needs to wait for something to happen, then it must unlock the object while it waits. The waiting thread should periodically reacquire the lock to test whether it can proceed. If so, it proceeds, and if not, it releases the lock and goes back to waiting.

In Java, each object provides a wait() method that unlocks the object and suspends the caller. While that thread is waiting, another thread can lock and change the object. Later, when the suspended thread resumes, it locks the object again before it returns from the wait() call. Here is a revised (but still not correct) dequeue method²

public synchronized T deq() {

  while (head == tail) {wait();}

  return call[(head++) % QSIZE];

}

Here, each operator thread, seeking a call to answer, repeatedly tests whether the queue is empty. If so, it releases the lock and waits, and if not, it removes and returns the item. In a similar way, an enqueuing thread checks whether the buffer is full.

When does a waiting thread wake up? It is the programmer’s responsibility to notify waiting threads when something significant happens. The notify() method wakes up one waiting thread, eventually, chosen arbitrarily from the set of waiting threads. When that thread awakens, it competes for the lock like any other thread. When that thread reacquires the lock, it returns from its wait() call. You cannot control which waiting thread is chosen. By contrast, the notifyAll() method wakes up all waiting threads, eventually. Each time the object is unlocked, one of these newly awakened threads will reacquire the lock and return from its wait() call. You cannot control the order in which the threads reacquire the lock.

In the call center example, there are multiple operators and one switchboard. Suppose the switchboard software decides to optimize its use of notify() as follows. If it adds a call to an empty queue, then it should notify only one blocked dequeuer, since there is only one call to consume. While this optimization may seem reasonable, it is flawed. Suppose the operator threads A and B discover the queue is empty, and block waiting for calls to answer. The switchboard thread S puts a call in the queue, and calls notify() to wake up one operator thread. Because the notification is asynchronous, however, there is a delay. S then returns and places another call in the queue, and because the queue already had a waiting call, it does not notify other threads. The switchboard’s notify() finally takes effect, waking up A, but not B, even though there is a call for B to answer. This pitfall is called the lost wakeup problem: one or more waiting threads fail to be notified that the condition for which they are waiting has become true. See Section 8.2.2 (Chapter 8) for a more detailed discussion.

A.2.3 Yielding and Sleeping

In addition to the wait() method, which allows a thread holding a lock to release the lock and pause, Java provides other ways for a thread that does not hold a lock to pause. A yield() call pauses the thread, asking the schedule to run something else. The scheduler decides whether to pause the thread, and when to restart it. If there are no other threads to run, the schedule may ignore the yield() call. Section 16.4.1 in Chapter 16 describes how yielding can be an effective way to prevent livelock. A call to Sleep(t), where t is a time value, instructs the scheduler not to run that thread for that duration. The scheduler is free to restart the thread at any later time.

A.2.4 Thread-Local Objects

Often it is useful for each thread to have its own private instance of a variable. Java supports such thread-local objects through the ThreadLocal<T> class, which manages a collection of objects of type T, one for each thread. Because thread-local variables were not built into Java, they have a somewhat complicated and awkward interface. Nevertheless, they are extremely useful, and we use them often, so we review how to use them here.

The ThreadLocal<T> class provides get() and set() methods that read and update the thread’s local value. The initialValue() method is called the first time a thread tries to get the value of a thread-local object. We cannot use the ThreadLocal<T> class directly. Instead, we must define a thread-local variable as a subclass of ThreadLocal<T> that overrides the parent’s initialValue() method to initialize each thread’s object appropriately.

This mechanism is best illustrated by an example. In many of our algorithms, we assume that each of n concurrent threads has a unique thread-local identifier between 0 and n − 1. To provide such an identifier, we show how to define a ThreadID class with a single static method: get() returns the calling thread’s identifier. When a thread calls get() for the first time, it is assigned the next unused identifier. Each subsequent call by that thread returns that thread’s identifier.

Fig. A.3 shows the simplest way to use a thread-local object to implement this useful class. Line declares an integer nextID field that holds the next identifier to be issued. Lines through define an inner class accessible only within the body of the enclosing ThreadID class. This inner class manages the thread’s identifier. It is a subclass of ThreadLocal<Integer> that overrides the InitialValue() method to assign the next unused identifier to the current thread.

Figure A.3 The ThreadID class: give each thread a unique identifier.

Because the inner ThreadLocalID class is used exactly once, it makes little sense to give it a name (for the same reason that it makes little sense to name your Thanks-giving turkey). Instead, it is more common to use an anonymous class as described earlier.

Here is an example how the ThreadID class might be used:

thread = new Thread(new Runnable() {

  public void run() {

     System.out.println("Hello world from thread" + ThreadID.get());

  }

});

A.3.1 Threads

C# provides a threading model similar to Java’s. C# threads are implemented by the System.Threading.Thread class. When you create a thread, you tell it what to do by passing it a ThreadStart delegate, a kind of pointer to the method you want to call. For example, here is a method that prints a simple message:

void HelloWorld()

  {

     Console.WriteLine("Hello World");

  }

We then turn this method into a ThreadStart delegate, and pass that delegate to the thread constructor.

ThreadStart hello = new ThreadStart(HelloWorld);

Thread thread = new Thread(hello);

C# provides a syntactic shortcut, called an anonymous method, that allows you to define a delegate directly, for example, by combining the previous steps into a single expression:

Thread thread = new Thread(delegate()

  {

      Console.WriteLine("Hello World");

  });

As in Java, after a thread has been created, it must be started:

thread.Start();

This call causes the thread to run, while the caller returns immediately. If the caller wants to wait for the thread to finish, it must join the thread:

thread.Join();

The caller is blocked until the thread’s method returns.

Fig. A.4 shows a method that initializes a number of threads, starts them, waits for them to finish, and then prints out a message. The method creates an array of threads, initializing each thread with its own ThreadStart delegate. We then start the threads, and each thread executes its delegate, displaying its message. Finally, we wait for each thread to finish, and display a message when they are all done. Except for minor syntactic differences, this code is similar to what you would write in Java.

Figure A.4 This method initializes a number of C# threads, starts them, waits for them to finish, and then prints out a message.

A.3.2 Monitors

For simple mutual exclusion, C# provides the ability to lock an object much like the synchronized modifier in Java:

int GetAndIncrement()

{

     lock (this)

     {

        return value++;

     }

}

Unlike Java, C# does not allow you to use a lock statement to modify a method directly. Instead, the lock statement is used to enclose the method body.

Concurrent data structures require more than mutual exclusion: they also require the ability to wait and signal conditions. Unlike in Java, where every object is an implicit monitor, in C# you must explicitly create the monitor associated with an object. To acquire a monitor lock, call Monitor.Enter(this), and to release the lock, call Monitor.Exit(this). Each monitor has a single implicit condition, which is waited upon by Monitor.Wait(this), and signaled by Monitor.Pulse(this) or Monitor.PulseAll(this), which respectively wake up one or all sleeping threads. Figs. A.5 and A.6 show how to implement a simple bounded queue using C# monitor calls.

Figure A.5 A bounded Queue class: fields and enq() method.

Figure A.6 A bounded Queue class: the deq() method.

A.3.3 Thread-Local Objects

C# provides a very simple way to make a static field thread-local: simply prefix the field declaration with the attribute [ThreadStatic].

[ThreadStatic]

static int value;

Do not provide an initial value for a [ThreadStatic] field, because the initialization happens once, not once per thread. Instead, each thread will find the field initially has that type’s default value: zero for integers, null for references, and so on.

Fig. A.7 shows how to implement the ThreadID class (Java version in Fig. A.3). There is one point about this program that may require comment. The first time a thread inspects its [ThreadStatic] identifier, that field will be zero, the default value for integers. To distinguish between an uninitialized zero and a thread ID zero, this field holds the thread ID displaced by one: thread 0 has field value 1, and so on.

Figure A.7 The ThreadID class provides each thread a unique identifier implemented using [ThreadStatic].

A.4.1 Thread-Local Storage

Fig. A.10 illustrates how Pthreads manages thread-local storage. The Pthreads library associates a thread-specific value with a key, which is declared at Line 1 and initialized at Line 6. The value is a pointer, initially Null. A thread acquires an ID by calling threadID_get(). This method looks up the thread-local value bound to the key (Line 10). On the first call, that value is null (Line 11), so the thread must take a new unique ID by incrementing the counter variable. Here, we use a mutex to synchronize access to a counter (Lines 12 – 16).

Figure A.10 This program provides each thread a unique identifier using Pthreads thread-local storage management calls.