Synchronization #

The behavior of a program that runs multiple threads can be hard to predict. In particular, two threads may compete to access a same resource (e.g. the value of some object’s attribute), without guarantee on the order in which they access it. This may lead (among other things) to a race condition

Programming languages that support multithreading also allow expressing constraints on the order of execution of some instructions. For instance, we saw earlier that a thread can be forced to wait for a child thread to terminate before resuming its execution.

In this section, we review two additional mechanisms (mutual exclusion and condition variables) that allow synchronizing the behaviors of threads.

For a more exhaustive overview of the possibilities offered by Java in that regard, we refer to the Javadoc of the package java.util.concurrent. In particular, it summarizes the situations where a Java statement must be executed before another (in Java’s terminology, this binary relation over statements is called the “happens before” relation).

Mutual exclusion #

Mutual exclusion prevents two threads to access a same resource concurrently. This is generally achieved via some kind of lock (sometimes called a mutex or semaphore).

Most programming languages that support concurrency provide mechanisms for mutual exclusion. These languages include C/C++, C#, Go, Java, PHP, Python, or Rust.

in Java #

Java associates to each object a so-called intrinsic lock (also called monitor lock or simply monitor).

If a thread $t_1$ acquires the intrinsic lock of an object, then a different thread $t_2$ cannot acquire this lock until $t_1$ has released it (however, a thread can reacquire a lock that it already owns).

The Java keyword synchronized enforces mutual exclusion via an intrinsic lock. In can be used in two ways:

Synchronized statement #

A synchronized statement associates an object $o$ to a block of code (called a synchronized block).

A thread that enters this block acquires the intrinsic lock of $o$, and releases it when exits the block.

The syntax is the following:

synchronized(<object>){
    <code block>
}

Example. Consider the two following classes:

public class Counter {

    int value;

    public Counter(int value){
        this.value = value;
    }
}

public class Lock {

}

The method increment below uses an instance of Lock to ensure that a counter is only incremented by one thread at a time:

void increment(Counter counter, Lock lock){

    synchronized(lock){
        counter.value++;
    }
}

As a result, the following program is free of race condition:

Counter counter = new Counter(0);
Lock lock = new Lock();

Thread t1 = new Thread( () -> { increment(counter, lock); } );
Thread t2 = new Thread( () -> { increment(counter, lock); } );

t1.start();
t2.start();

Observe that in the example above, any object could be used as a lock. In particular, the object counter itself. So the program below is equivalent:

void increment(Counter counter){

    synchronized(counter){
        counter.value++;
    }
}

Counter counter = new Counter(0);

Thread t1 = new Thread( () -> { increment(counter); } );
Thread t2 = new Thread( () -> { increment(counter); } );

t1.start();
t2.start();

Synchronized method #

A synchronized instance method uses the intrinsic lock of the object for which this method is called.

The syntax is the following:

public synchronized int myMethod() {
    ...
}

In other words, the two following classes are equivalent:

public class MyClass {

    synchronized int myMethod(){
        <method body>
    }
}

public class MyClass {

    int myMethod(){
        synchronized(this){
            <method body>
        }
    }
}

Warning. A constructor cannot be synchronized (the program will not compile).

Observation. Let $m$ be a synchronized instance method, let $o$ be an object, let $t_1$ and $t_2$ be two different threads, and let us assume that $t_1$ executes $o.m$ (i.e. $t_1$ executes the method $m$ for the object $o$).

Then $t_2$ cannot execute any synchronized method for $o$ before the termination of $o.m$ (since $t_1$ acquired the lock on the object $o$).

Observation. We mentioned above that a thread can reacquire a lock that it already owns.

As a consequence, for the same object, a synchronized method can call another, as long as they are executed by the same thread.

public class Counter {

    int value;

    public Counter(int value){
        this.value = value;
    }

    synchronized void inc(int delta){
        value += delta;
    }

    synchronized void doubleDec(int delta){
        value -= delta;
        value -= delta;
    }

    synchronized int getValue(){
        return value;
    }
}

Counter counter = new Counter(0);

Thread t1 = new Thread( () -> { counter.doubleDec(2); } );
t1.start();

Thread t2 = new Thread( () -> { counter.inc(5); } );
t2.start();

System.out.println(counter.getValue());

try {
    t1.join();
    t2.join();
} catch (InterruptedException e) {
    throw new RuntimeException(e);
}

System.out.println(counter.getValue());

A synchronized static method uses the intrinsic lock of the object that represents the class itself (this object is an instance of Class).

In other words, the two following classes are equivalent:

public class MyClass {

    static synchronized void myMethod(){
        <method body>
    }
}

public class MyClass {

    static void myMethod(){
        synchronized(Class.forName("my.project.name.MyClass")){
            <method body>
        }
    }
}

Condition variables #

We saw earlier that a thread $t_1$ can wait for another thread $t_2$ to terminate (e.g. with the pseudocode keyword sync in our abstract model, or in Java with the instance method Thread.join).

In this case, when it terminates, $t_2$ wakes up $t_1$, which can resume its execution.

A similar but more flexible mechanism is the notion of condition variable. Intuitively, it allows putting a thread to sleep, and waking it up when a certain condition is verified.

A variety of programming languages support condition variables. These include C++, C#, Go, Java, Python or Rust.

The producer/consumer pattern #

A prototypical application of condition variables is the so-called producer/consumer pattern. In this scenario, two pools of threads (usually with fixed sizes) communicate via a queue.

1. A pool of producer threads, which create elements and add (a.k.a. enqueue) them to the queue,
2. A pool of consumer threads, which receive (a.k.a. dequeue) these elements and process them.

Two situations may occur where threads should be put to sleep:

• the queue is empty (e.g. because the process just started, or because elements have been consumed faster than they were produced): consumers should be put to sleep until a new element is produced.
• the queue is full (e.g. because elements have been produced faster than they were consumed): producers should be put to sleep until an element is consumed.

in Java #

Reminder. As discussed above, a thread can acquire the intrinsic lock of an object by:

• entering a synchronized block that has this object as lock, or
• executing a synchronized method for this object.

A condition variable in Java can be simulated with a combination of the instance methods Object.wait() and Object.notify() (or Object.notifyAll()).

wait #

The instance method $o$.wait() can only be called by a thread that acquired the intrinsic lock of the object $o$. It has the effect of releasing this lock, and putting the current thread to sleep, until another thread executes $o$.notify() (or $o$.notifyAll()) (for the same object $o$).

notify #

Similarly to $o$.wait(), the instance method $o$.notify() can only be called by a thread that acquired the intrinsic lock of the object. It has the effect of attempting to wake up one thread (if any) that is waiting for the lock of this object. The awakened thread will only proceed (i.e. actually wake up) after the notifying thread releases the lock of the object.

notifyAll #

The instance method $o$.notifyAll() is identical to $o$.notify(), but attempts to wake up all threads that are waiting for the lock of this object.

Example. The following example is an implementation of the producer-consumer pattern borrowed from the Oracle tutorials.

For simplicity:

• we will use a queue with a capacity of 1 (so that the queue is either empty of full),
• we assume a single producer and a single consumer.

pulic class MyQueue<T> {

    T item;
    boolean isEmpty = true;

    synchronized void enqueue(T item){
        while(!isEmpty){
            try {
                wait();
            } catch (InterruptedException e) {}
        }
        this.item = item;
        isEmpty = false;
        notify();
    }
}

When the producer thread $p$ executes the method enqueue, it acquires the intrinsic lock of the queue (because the method is synchronized). If the queue is full, it releases the lock and waits for the consumer thread to wake it up. If this happens, thread $p$:

• adds the produced item to the queue,
• indicates that the queue should now be considered nonempty (a.k.a. full, since the queue has capacity 1),
• wakes up the consumer thread (which was waiting for the queue to be nonempty),
• releases the intrinsic lock on the queue (by exiting the synchronized method).

The method dequeue is symmetric:

public class MyQueue<T> {

    ...

    synchronized T dequeue(){
        while(isEmpty){
            try {
                wait();
            } catch (InterruptedException e) {}
        }
        isEmpty = true;
        notify();
        return item;
    }
}

A producer thread could be implemented as follows:

public class Producer implements Runnable {

    private MyQueue<Item> queue;

    public Producer(MyQueue<Item> queue){
        this.queue = queue;
    }

    @Override
    public void run() {
        while(true){
            queue.enqueue(produceItem());
        }
    }

    Item produceItem(){
        ...
    }
}

And a consumer thread could be implemented as follows:

public class Consumer implements Runnable {

    private MyQueue<Item> queue;

    public Consumer(MyQueue<Item> queue){
        this.queue = queue;
    }

    @Override
    public void run() {
        while(true){
            consumeItem(queue.dequeue());
        }
    }

    void consumeItem(Item item){
        ...
    }
}

Finally, the main thread may spawn one producer and one consumer, as follows:

    MyQueue<Item> queue = new MyQueue<>();
    Thread p = new Thread(new Producer(queue));
    Thread c = new Thread(new Consumer(queue));
    p.start();
    c.start();

Spurious wakeup #

In the example above, the loop while(!isEmpty) (in the method enqueue) seems unnecessary, in the sense that it could be replaced with the conditional statements if(!isEmpty). And similarly for the loop in the method dequeue.

The purpose of this loop is to handle the abnormal case where a consumer (resp. producer) is awaken while the condition variable isEmpty has value false (resp. true). Such a situation is called a spurious wakeup, and may have a variety of causes. For instance, in the example above, if we had two producer threads, then one producer thread could wake up the other (instead of waking up the consumer thread), when it exits the method enqueue.

To avoid spurious wakeups, it is customary to write:

while(<condition>){
    wait();
}

rather than:

if(<condition>){
    wait();
}