mips42

"Stuff your friends simply don't understand!"

Concurrency and distribution in Java, part one

Foreword

Let us get back to IT for a while, shall we? That is what we are here for.
Ever written a concurrent or distributed piece of software? Well, if you did, you will know that it is a vast topic with a distinctive interesting concepts overload, well worth discussing, so I thought I could write about it. And there you go.
This is part one of a series of two essays, and will only cover concurrency.

The purpose of this document

This essay aims to be an introduction to the concepts and problems related to concurrency and distribution in software. Example Java code will accompany the discussion of these subjects, which, in itself, is language-indipendent. I will also cover the Java-only RMI technology, both conceptually and implementationally (hoping this word exists :); that chapter will be designed to help the understanding of similar technologies, too.

Concurrency: processes and threads

Firstly, we need to define two important concepts in programming, processes and threads. Let us begin with processes:
A process is an instance of a computer program. What a computer program is, you should know. While a program is a dead list of instructions, a process is those instructions when alive, i.e. being executed. Thus, when you run a program, what happens is the operating system creates a process and then starts it. In Java, a program (and a corresponding process) start at the main() method:class Process {
  public static void main(String[] args) {
    // instructions here
  }
}
A single process may have multiple threads, and it always has at least one (the main thread). A thread (or thread of execution) is a single flow of sequential execution within a process. You are probably familiar with multiple processes running at the same time (multitasking); imagine that inside a single process. This mechanism allows programmers to write code that does more than one thing "at once", without the hassle of having to schedule the activities. Of course, the hardware beneath (especially the CPU), cannot actually execute multiple instructions at once (well let us leave out multicore CPUs for today). What actually happens is that the operating system schedules the execution of the threads. This has pros (e.g. when one thread is waiting for I/O, another one can run) and cons (e.g. preemption), but we will get to that later. Here is a very simple multithreaded Java program:class MyThread extends Thread {
  public void run() {
    for (int i = 0; i < 100; i++)
      System.out.println("MYTHREAD");
  }
}

class Multithreaded {
  public static void main(String[] args) {
    MyThread myThread = new MyThread();
    myThread.start();
    for (int i = 0; i < 100; i++)
      System.out.println("MAINTHREAD");
  }
}
As you can see, in this example we create a MyThread class that extends Thread. Extending Thread means that every object of the class is a thread, and that the class must have a void run() method, which contains the code that the thread will execute. A Thread (like our MyThread) is created just like any other object, and it is started (not surprisingly) by calling the start() method on it. This method will actually cause the execution of the run() method of the Thread object, but will return immediately (i.e. will not wait for the run() method to return). Thus, this program has two threads: the main thread, which is automatically created when executing the main() method of a class, and the myThread thread. Our main() creates and starts the myThread. At this point, the two for loops are executed "at the same time", or concurrently. Just by reading the program we can be sure that it will print both "MYTHREAD" and "MAINTHREAD" exactly 100 times. What is less clear, is the order in which those strings will be printed. More on that later. Here is another way to create a thread, this time without extending Thread:class MyRunnable implements Runnable {
  public void run() {
    for (int i = 0; i < 100; i++)
      System.out.println("RUNNABLETHREAD");
  }
}

class RunnableExample {
  public static void main(String[] args) {
    MyRunnable myRunnable = new MyRunnable();
    Thread myThread = new Thread(myRunnable);
    myThread.start();
    for (int i = 0; i < 100; i++)
      System.out.println("MAINTHREAD");
  }
}
This RunnableExample does the same thing as the previous example, without the need to extend Thread. So, if you just need to override the run() method, implementing Runnable is preferable. To get the Thread object inside of the MyRunnable run(), just call Thread.currentThread().

Shared resources and preemption

A resource, as far as this article is concerned, is merely an object. Other examples of resources are files, memory, network connections.. and the list goes on. Now we will deal with multithreaded programs whose threads need to access the same resource (the same object).
Since there can only be one thread running on the CPU at one given time, some sort of mechanism must exist in order to simulate real multithreading. A running thread can be subject to preemption when the operating system is able to interrupt it, in order to start or carry on with the execution of another thread. A programmer must not make any assumptions about when a given thread will be interrupted. It can happen between any two atomic instructions. Thus, the examples I presented in the previous paragraph will print their strings in an unforeseeable order, and all possible combinations are possible (though not equally likely). The presence of preemption forces the programmer to deal with problems which simply do not exist in a non-preemptive environment.
A module (i.e. a piece of code, like a Java class) is said to be thread safe if it does not present problems when run in a multithreaded (preemptive) environment. The realistic version of this definition is: a module can be claimed to be thread safe by its author if he thinks that the problems it has cannot grow in number or get worse in a preemptive environment.

Race conditions

A program is subject to a race condition if its output is dependant on the timing of some events (e.g. when a given thread is preempted). Consider this scenario: we are running a program in which two threads are concurrently trying to increment a certain integer variable, which is stored in memory and has a current value of 0. The output of this program (i.e. the final value of that variable in memory) should be 2. Unfortunately, incrementing a variable in memory is generally not an atomic instruction, since we must read that value into a register, increment the register, and then write the contents of the register back into memory. This sequence of instructions has to be executed by both threads. Now, what happens if one thread is preempted just after reading the value (0) into its register? The other thread will read the same value (0). If this happens, both threads will increment their register obtaining the value 1, and will write this value back into memory, which gives us a final value of 1. The output of this program changes depending on when thread preemption occurs, and so it is flawed with a race condition.

TOCTTOU issues

Time-Of-Check-To-Time-Of-Use, or TOCTTOU (read "tock too") issues are a kind of race condition. The scenario is as follows: a program needs to check the status of a resource before actually using it. The problem is as follows: the status of the resource can change in the time between the check and the use. Consider this example, in pseudocode:if ( checkIfAvailable( resource ) == true ) {
  // at this point the resource vanishes
  use( resource ); // this will fail
}
The resource in the example could be a file that is deleted after checking if it is available but before using (opening) it. Some TOCTTOU flaws can be exploited to change the intended behaviour of a program, besides causing it to fail, but I leave that to your imagination :)

Solutions, part one: obtaining mutual exclusion

Consider the following program, a Java class representing a stack, clearly not thread safe:class MyStack {
  public MyStack() { elements = new Object[max_size]; }
  public void push(Object p) {
    if (counter < (max_size-1)) {
      elements[counter] = p;
      counter++;
    }
  }
  public Object pop() {
    if (counter != 0) {
      counter--;
      return elements[counter+1];
    } else return null;
  }
  private int counter = 0;
  private Object[] elements;
  private final int max_size = 10;
}
The problem with this class is that it cannot change its state atomically: both in push() and in pop() it takes two instructions to take the object to a consistent state. If the stack has zero elements, the object we are pushing needs to be added to the elements array, *and* the counter needs to be increased (this variable basically counts the number of elements in the stack). Likewise, when popping an element, we need to decrease the counter *and* then return the topmost element. The danger with this code is that it is possible that, for example, right in the middle of a push() one thread is preempted and another calls pop(), finding the object in an inconsistent state, and possibly accessing a non-existent array element.
This is some example code (much simpler than it looks) that uses the MyStack class:class PushingThread implements Runnable {
  public PushingThread(MyStack myStack) { stack = myStack; }
  public void run() {
    for (int i = 0; i < 100000; i++) stack.push( new Object() );
  }
  private MyStack stack;
}

class PoppingThread implements Runnable {
  public PoppingThread(MyStack myStack) { stack = myStack; }
  public void run() {
    for (int i = 0; i < 100000; i++) stack.pop();
  }
  private MyStack stack;
}

class StackUser {
  public static void main(String[] args) {
    MyStack myStack = new MyStack();
    PushingThread t1 = new PushingThread(myStack);
    PoppingThread t2 = new PoppingThread(myStack);
    new Thread(t1).start(); new Thread(t2).start();
  }
}
It basically creates two threads that concurrently push() and pop() on the same MyStack; they do so one hundred thousand times each, just to improve our chances to actually trigger the race condition. Let us run it and see what happens:$ java StackUser
$ java StackUser
Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 10
  at MyStack.pop(MyStack.java:12)
  at PoppingThread.run(StackUser.java:12)
  at java.lang.Thread.run(Thread.java:619)
The first time we ran it, it had no problems. The second time, it threw an ArrayIndexOutOfBoundsException: 10, meaning that the elements array was accessed at index 10 which is higher then its highest index in the bounds, 9. What happened? Picture this. At some point, the value of counter is 9. Thread t2 calls pop(), and is preempted just after pop() has decreased the counter (now = 8). Now, thread t1 calls push(), which fills position 8 in the array, and increases the counter (now = 9). Thread t1 calls push() a lot of times, obtaining no effect since the counter is not < 9, until it is preempted. The execution of thread t2 is resumed at the return instruction, which tries to access element counter+1 = 10, out of the array bounds, triggering the exception and causing the program to fail.

We understand that, in order to solve this problem, we need a mechanism which enables us to obtain exclusive access to a shared resource. If we could add a marker to our push() and pop() methods which assures us that they will not be called at the same time, we would eliminate the race condition. Here is how we can accomplish that in a Java program:class MyStack {
  public MyStack() { elements = new Object[max_size]; }
  public synchronized void push(Object p) {
    if (counter < (max_size-1)) {
      elements[counter] = p;
      counter++;
    }
  }
  public synchronized Object pop() {
    if (counter != 0) {
      counter--;
      return elements[counter+1];
    } else return null;
  }
  private int counter = 0;
  private Object[] elements;
  private final int max_size = 10;
}
The only difference with the old version of MyStack is that now its methods have the synchronized keyword in their signature. The synchronized keyword, when applied to a method, means that that method will wait until it obtains mutually exclusive access to the object it is called onto before executing. Obtaining mutually exclusive access to an object is usually called acquiring the lock on that object, or just locking it. If a thread tries to acquire the lock on a locked object, it has to wait until the thread who locked it releases the lock. When using the synchronized keyword on a method, the lock is released when the method returns, so in the full body of the method we know that we are alone in the object. This allows us to take the object to a consistent state before it can be accessed by some other thread.

We can also use the synchronized keyword inside of method bodies. Here is a code snip demonstrating this:  public void method() {
    synchronized(this) {
      // this is locked here
    }
  }
This is roughly equivalent to adding the synchronized keyword to the method's signature (but less elegant). Anyway, we can choose to lock this on a code section smaller than the full method body:  public void method() {
    // this is not locked
    synchronized(this) {
      // this is locked
    }
    // this is not locked
  }
This construct also allows us to acquire the lock on something else than this, for example a method parameter:  public void method(Object param) {
    // param is not locked (this is not locked)
    synchronized(param) {
      // param is locked (this is not locked)
    }
    // param is not locked (this is not locked)
  }
You can use synchronized to lock any object, but remember that the keyword's argument can only be an object reference. If you need to lock a reference extracted from an expression, you must first assign the expression's value to a reference variable, and then synchronize on that variable.

Deadlocks

Unfortunately, introducing mutual exclusion carries within itself a whole new batch of problems. The first I will cover, and the deadliest (as the name suggests), is the so-called deadlock.

The simplest deadlock situation occurs when two (threads or) processes (P1 and P2) are competing for two resources (R1 and R2). Both processes need to exclusively control both resources to complete their task. Free resources are coloured green in the diagram.Our actors.Now, suppose that P1 takes control of R1 and that P2 takes control of R2. Locked resources are coloured red in the diagram.Fine so far..P1 will now ask for R2, P2 for R1. Waiting for a resource is represented with dotted arrows.Deadlock!This results in infinite waiting, because neither P1 nor P2 will release their resource before they obtain the other. There is no logical mistake in what P1 and P2 do; in fact, if we decide to run them separately (in sequence), no deadlock will ever occur, and both processes will terminate. The problem arises from the situation of concurrency our processes are in.

The two processes and two resources problem is just a simple case of a more general problem called circular waiting. Let us try with three and three, and see what happens.Guess what? Another deadlock!Looks familiar. No process will continue until some other frees a resource. Of course, no process can free a resource, because they are all waiting. Circular waiting is usually illustrated with the dining philosophers problem. Imagine n philosophers sitting at a circular table. On the table are n dishes and n forks. The dishes are in front of every philosopher, while the forks are between two of them. A philosopher needs two forks at once to eat from his dish (the one at his left, and the one at his right). Philosophers think or eat, never both at once. Now, if the n philosophers are thinking and then decide to eat all at once, they will all pick the fork at their left, and wait for the philosopher at their right to stop using the other fork (which, of course, will never happen).

What follows is a Java program with a very high chance of deadlocking.class Deadlock extends Thread {
  private Deadlock other;
  public void run() { doTheTrick(); }
  public void setOther(Deadlock d) { other = d; }
  public synchronized void doTheTrick() {
    for(int i=0; i<1000000; i++);
    other.doTheTrick();
  }
  public static void main(String[] args) {
    Deadlock d1 = new Deadlock(), d2 = new Deadlock();
    d1.setOther(d2); d2.setOther(d1);
    d1.start(); d2.start();
  }
}
Its behaviour is similar to the two processes/two resources example we saw before, but the objects p1 and p2 represent both the processes and the resources. While one thread is in the long, empty for loop, it is very likely that the system will interrupt it, allowing the other, too, to call the synchronized doTheTrick() method on itself. At this point both p1 and p2 have locked themselves. When they get out of the loops, they try to call doTheTrick() on each other, which will cause them to wait forever. The situation is illustrated in this diagram:The example program, in a deadlock

Livelocks

As the name suggests, livelocks and deadlocks are similar situations. The difference is, in a livelock the involved processes/threads change their states, but none of them really progresses. Often, livelocks are metaphorically explained using the mamihlapinatapai example.

Starvation

As the name suggests (yes, in IT we like to give things meaningful names), resource starvation - or just starvation - implies that some processes or threads are not able to acquire the resources they need in order to complete, because these resources are locked.
For example, in a system we can have some processes running and trying to access a certain set of resources. If we have starvation, then at least one of these processes cannot complete because the resources it needs are always locked when it tries to acquire them. The starving processes are never assigned the resources they need in order to finish their tasks, while the other non-starving processes are behaving exactly as planned. Put in these words, it is clear that starvation is a problem that arises because of concurrency.

Solutions, part two: know your enemy

Let us start with deadlocks. E. G. Coffman described the four conditions necessary for a deadlock to occur. In case you did not know, necessary means that these conditions must all happen in order for a deadlock to exist, and not that they alone always cause a deadlock. Here they are:
  1. Mutual exclusion
    A resource is either assigned to one thread or it is available
  2. Hold and wait
    Threads already holding resources may request new resources
  3. No preemption
    Only a thread holding a resource may release it
  4. Circular wait
    Two or more threads form a circular chain where each thread waits for a resource that the next thread in the chain holds
You can avoid deadlocks in your code if you make sure than one - or more - of these conditions never happen.

Unfortunately, there is often no way out of the first three; so we will focus on the fourth, and discuss a general strategy which can be used to prevent circular waiting in some cases, and which is generally very easy to understand and implement: total ordering. Let us recall the deadlock diagram from above:How can we avoid this deadlock?In this example the resources are already named, but it is often fairly easy to obtain a unique identifier for an object, either by using some ad-hoc mechanism provided by the language or framework, adding an identification field to its class or by examining the object's address in memory. Once we are sure that our objects have unique identifiers (addresses, integers, strings..) we can choose a total order (numerical, alphabetical..) for our resource objects. Now we can modify our programs so that when they need to access multiple resources they always do so orderly, from the lowest identifier to the highest, and this solves our little deadlock problem. Think about it. This is not the silver bullet of deadlocks, but it does come handy thanks to its simplicity. If you know about other approaches to concurrency problems simple enough to be included in this essay, let me know.

Solutions, part three: automated checking

Suppose we have a software which automatically detects whether our program is going to deadlock. It would be a really great software, because it would accidentally solve the undecidable halting problem. Anyway, just as we decided whether the above examples were subject to deadlock, we can write some software which helps us test our programs. Do not underestimate the help that automated tools can give you while dealing with these issues.

Final words

The actual final words will be in part two, which will cover distribution.
Just so you know, the diagrams were generated using the Graphviz tool dot.
If you want to talk, head on to the contact page.
See you next essay... part. Bye.
Top
This web site is written in XHTML 1.0 Strict and CSS 2.
It is licensed under a Creative Commons Attribution-Noncommercial 3.0 License.