Locking

Interleavings

Interleaving is a possible way in which a series of statements could be executed. This concept is important because in concurrent programming the interleaving of a program could influence the result. Choosing the interleaving is however not up to us but the scheduler.

The picture above shows some possible interleaving of a program split up between two threads.

class Counter {
    private int i = 0;
    public void inc() { i++; }
    public int getCount() { return i; }
}
class R implements Runnable {
    private Counter c;
    public R(Counter c) { this.c = c; }
    public void run() {
        for (int i = 0; i < 100000; i++) {
            c.inc();
        }
    }
}
public class CounterTest {
    public static void main(String[] args) {
        Counter c = new Counter();
        Runnable r = new R(c);
        Thread t1 = new Thread(r); Thread t2 = new Thread(r);
        Thread t3 = new Thread(r); Thread t4 = new Thread(r);
        t1.start(); t2.start(); t3.start(); t4.start();
        try {
            t1.join(); t2.join(); t3.join(); t4.join();
        } catch (InterruptedException e) {}
        System.out.println(c.getCount());
    }
}

If we execute the above code we could expect the result to be 400000 because there are 4 threads and each thread increases the counter 100000 times and we only output the result once all threads have terminated. However, when executing this program this is not the case we might see something like 108600 and if we execute it another time 118127. These results happen because the scheduler is allowed to switch context between every CPU operation. So we can see that read and write operations are not guaranteed to be atomic meaning it is done as one instruction by the CPU. Even writing to a value of the type double might be done in 2 parts, it might assign the first 32 bits and then the next 32 bits. In the example, the scenario below happend a few times which causes modifications to get lost.

Interleaving Model

The interleaving model is used to calculate the number of possible interleavings (size of the set of possible interleavings) depending on the number of threads $n$ and the number of atomic instructions $m$.

For example, if there are 2 threads and a program with 3 atomic instructions then there are 20 possible ways the program could be executed across the 2 threads. Just by increasing the number of threads to 4 the number of possible interleavings skyrockets to 369'600.

Race Conditions

A race condition can happen when a result depends on the interleaving of the program across two or more threads. Critically race conditions can also happen when two or more threads are accessing shared data and at least one of them is modifying the data. This leads to unpredictable results as thread scheduling is nondeterministic.

Synchronization

Synchronization is a technique of managing access to shared mutable data to prevent race conditions.

Locks

A lock or mutex (from mutual exclusion) is a mechanism to enforce mutual exclusion i.e limits access to a resource when multiple threads want to access the resource. Mutual exclusion prevents simultaneous access by only allowing one thread at a time to access a shared resource and therefore guarding critical sections against concurrent execution. By locking a certain section you are also forcing atomicity as no other thread can enter that section of code whilst another thread holds it. This can be a double-edged as it makes the program thread-safe but also means that we are not making use of concurrency.

Built-in Locking in Java

Java has a built-in locking mechanism, the synchronized keyword. Locking consists of two parts: The object that will serve as a lock and a block of code, the critical section, that is guarded by the lock. When a thread reaches the synchronized block and the lock is not in use the thread can acquire the lock to the block. However, if the lock is not available because it has already been taken then the thread enters the waiting list. When a thread exits a synchronized section the lock is released and there is a race to which thread gets to acquire the lock next. Often the lock is just on the current instance (this) or class in a static context. This is what Java does by default if you do not specify a certain lock object. Something to be careful of is using String literals as a lock as it can cause some big issues (opens in a new tab) because according to Section 3.10.5 of the Java Language Specification (opens in a new tab): Literal strings within different classes in different packages likewise represent references to the same String object.

The above example could be fixed by doing one of the following:

class Counter {
    private int i = 0;
    private final Object lock = new Object();
    public synchronized void inc() { i++; }
    // OR public void inc() { synchronized(this){ i++; } }
    // OR public void inc() { synchronized(lock){ i++; } }
    public int getCount() { return i; }
}

Deadlock

A Deadlock is a situation where at least one thread is blocked because it is holding a resource and is waiting for another resource which is already being held by another thread that wants the other resource being held. So in other words the necessary conditions for a deadlock to happen are:

• Mutual Exclusion
• Hold and Wait, threads are requesting additional resources whilst also holding other resources.
• No Preemption, resources are released exclusively by threads.
• 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.

Global Ordering

One way of avoiding deadlocks is to order the way the locks are obtained so instead of having the following situation:

We can acquire the locks in lexicographical order.

Reentrancy

Synchronized is also reentrant. Meaning that the same lock can be acquired multiple times by the same thread. Java does this by keeping a counter for each lock with the initial value being 0. When a thread then acquires initially acquires the lock it sets the lock-id to the current thread and increments the counter. For each further acquisition of that lock, the counter is just further incremented. Each lock release then decrements the counter and once the counter reaches 0 again the lock is completely released and made available again to the other threads. The following examples do not cause a deadlock.

synchronized f() { g(); }
synchronized g() {
    /* no deadlock */
    synchronized(x) {
        synchronized(x) { /* still no deadlock */ }
    }
}

java.util Locks

Additionally to the synchronized keyword Java also offers some lock implementations that are more flexible. It is important to use these locks with a try block so that the lock can be released in the finally block in case any exceptions occur.

interface Lock{
    void lock() // Acquires the lock.
    void lockInterruptibly() // Acquires the lock unless the current thread is interrupted.
    Condition newCondition() // Returns a new Condition instance that is bound to this Lock instance.
    boolean tryLock() // Acquires the lock only if it is free at the time of invocation.
    boolean tryLock(long time, TimeUnit unit) // Acquires the lock if it is free within the given waiting time and the current thread has not been interrupted.
    void unlock() // Releases the lock.
}

Usage Pattern:

public synchronized void inc() {
    Lock lock = ...;
    ...
    lock.lock();
    try {
        // access resources protected by this lock
    }
    finally {
        lock.unlock(); // by the same thread!
    }
}

Reentrant Lock

The class ReeentrantLock implements the Lock interface. It offers the same functionality as when using the synchronized mechanism with some extra functions:

• int getHoldCount() queries the number of holds on this lock by the current thread.
• Thread getOwner() returns the thread that currently owns the lock, or null if not owned.
• Collection<Thread> getQueuedThreads() returns a collection containing threads that are waiting to acquire this lock.
• int getQueueLength() returns an estimate of the number of threads waiting to acquire this lock.

A fairness parameter can also be passed with the constructor to define whether the lock is fair or not. Fair locks let threads acquire the lock in the order it was requested i.e. the longest waiting thread always gets the lock (FIFO). An unfair lock is how synchronized works it lets the threads race to acquire the lock.