Locking

Code in:JavaC#PythonJavaScript

In short: A lock (mutex) lets only one thread at a time into the critical section; in Java this is synchronized or ReentrantLock, and only the little that must be there goes under it.

Problem

How to stop the other till

In the lesson "Race condition" the sale lost sales: two threads did "read, subtract, write" at once and one overwrote the other. The three steps have to be one whole: while one thread is inside, the other has to wait outside.

That is exactly what a lock does.

The idea

The lock

A lock (mutex, from "mutual exclusion") is an object with one owner. A thread takes it, does its work and releases it. Another thread that asks for it in the meantime waits. The code between taking and releasing is the critical section: at most one thread is in it.

In Java any object can be a lock. synchronized (lock) { … } takes it when entering the block and releases it when leaving, even with an exception:

class Stock {
    private final Object lock = new Object();
    private int left;

    Stock(int left) {
        this.left = left;
    }

    void sell() {
        synchronized (lock) {
            left--;
        }
    }

    int left() {
        synchronized (lock) {
            return left;
        }
    }
}

The two tills from the last lesson, with the same 100,000 sales each:

Stock stock = new Stock(200_000);
Runnable checkout = () -> {
    for (int i = 0; i < 100_000; i++) {
        stock.sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.start();
b.start();
a.join();
b.join();
System.out.println("Orders: " + 2 * 100_000);
System.out.println("Sold according to the stock:");
System.out.println(200_000 - stock.left());

Output

Orders: 200000
Sold according to the stock:
200000

Exact, on every run. The lock is a field created once: both tills lock the same one.

The lock object is a separate private field and not this. That way no code outside can lock the same object and stop your tills.

See it

The last item, fixed

The check "is there one" and taking it are in one and the same critical section. If someone is inside checking, the other cannot check before the first has taken:

class Stock {
    private final Object lock = new Object();
    private int left;

    Stock(int left) {
        this.left = left;
    }

    boolean reserve() {
        synchronized (lock) {
            if (left == 0) {
                return false;   // none left: refuse
            }
            left--;             // there is one: take it
            return true;
        }
    }

    int left() {
        synchronized (lock) {
            return left;
        }
    }
}

Step by step, in words

1. 3 items are left, and 4 buyers call reserve() at the same moment.
2. Only one gets through synchronized; the other three wait in front of it. Buyer 1 goes in, sees 3 and takes one: 2 left.
3. Buyer 1 leaves and releases the lock. Buyer 2 goes in, sees 2 and takes one: 1 left.
4. Buyer 2 leaves and releases the lock. Buyer 3 goes in, sees 1 and takes one: 0 left.
5. Buyer 4 goes in last and sees 0: refused. No one saw a number that someone else was in the middle of changing.
6. 3 sold, 1 refused, 0 in stock: correct. The price: the buyers waited for each other at the turnstile.

Four buyers, three items, all at once:

Stock stock = new Stock(3);
boolean[] ok = new boolean[4];
List<Thread> buyers = new ArrayList<>();
for (int b = 0; b < 4; b++) {
    int buyer = b;
    Thread t = new Thread(() -> ok[buyer] = stock.reserve());
    buyers.add(t);
    t.start();
}
for (Thread t : buyers) {
    t.join();
}
int sold = 0;
for (boolean o : ok) {
    if (o) sold++;
}
System.out.println("Sold: " + sold);
System.out.println("Refused: " + (4 - sold));
System.out.println("In stock: " + stock.left());

Output

Sold: 3
Refused: 1
In stock: 0

And here are the two buyers from the last lesson who were buying the last item. Charging the card (~100 ms) is after the lock: the item is reserved, and the card is charged without the other one waiting:

Stock stock = new Stock(1);
boolean[] bought = new boolean[2];
Runnable[] buyers = new Runnable[2];
for (int b = 0; b < 2; b++) {
    int buyer = b;
    buyers[b] = () -> {
        if (stock.reserve()) {
            pause(100);   // charging the card, ~100 ms
            bought[buyer] = true;
        }
    };
}
Thread first = new Thread(buyers[0]);
Thread second = new Thread(buyers[1]);
first.start();
second.start();
first.join();
second.join();
int sold = (bought[0] ? 1 : 0) + (bought[1] ? 1 : 0);
System.out.println("In stock before: 1");
System.out.println("Sold: " + sold);
System.out.println("Refused: " + (2 - sold));
System.out.println("In stock: " + stock.left());

Output

In stock before: 1
Sold: 1
Refused: 1
In stock: 0

One sold, one refused, 0 in stock. On every run.

Try it

Don't forget to release

Besides synchronized, Java has a lock object, ReentrantLock: lock() takes it, unlock() releases it. The release is in finally, so it happens even with an exception:

class Stock {
    private final ReentrantLock lock = new ReentrantLock();
    private int left;

    Stock(int left) {
        this.left = left;
    }

    void sell() {
        lock.lock();
        try {
            left--;
        } finally {
            lock.unlock();
        }
    }

    int left() {
        lock.lock();
        try {
            return left;
        } finally {
            lock.unlock();
        }
    }
}

What releases the lock?

void sell() {
    lock.lock();
    try {
        left--;
    } finally {
        
    }
}

Check

Try it

The lock that does not lock

A colleague added a lock, but the tills still lose sales. Which line is wrong?

Pick the line with the bug.

1class Stock {2 private int left;34 Stock(int left) {5 this.left = left;6 }78 void sell() {9 synchronized (new Object()) {10 left--;11 }12 }1314 int left() {15 return left;16 }17}

Check

The idea

What a lock costs

A lock works by making threads wait for each other. The longer one thread stays inside, the longer the others wait. That is contention for the lock.

A shop with 10 items and four orders at once. Each order takes an item and sends an e-mail (~200 ms), and Network from the lesson "Why threads" counts the rounds of waiting:

class Network {
    private int inFlight = 0;
    private int rounds = 0;

    // Asks a service over the network: the answer comes after ~200 ms.
    String call(String service, String answer) {
        synchronized (this) {
            if (inFlight == 0) rounds++;   // nobody is waiting: a new round
            inFlight++;
        }
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        synchronized (this) {
            inFlight--;
        }
        return service + ": " + answer;
    }

    synchronized int rounds() {
        return rounds;
    }
}

class Shop {
    private final Object lock = new Object();
    private final Network net;
    private int left = 10;

    Shop(Network net) {
        this.net = net;
    }

    // Bad: the e-mail goes out while the lock is held.
    void orderSlow(String customer) {
        synchronized (lock) {
            left--;
            net.call("e-mail", customer);
        }
    }

    // Good: only the stock is under the lock.
    void order(String customer) {
        synchronized (lock) {
            left--;
        }
        net.call("e-mail", customer);
    }

    int left() {
        synchronized (lock) {
            return left;
        }
    }
}

With orderSlow the e-mail is under the lock:

Network net = new Network();
Shop shop = new Shop(net);
List<Thread> orders = new ArrayList<>();
for (int c = 1; c <= 4; c++) {
    String customer = "customer " + c;
    Thread t = new Thread(() -> shop.orderSlow(customer));
    orders.add(t);
    t.start();
}
for (Thread t : orders) {
    t.join();
}
System.out.println("Orders: 4, in stock: " + shop.left());
System.out.println("Rounds of waiting: " + net.rounds());

Output

Orders: 4, in stock: 6
Rounds of waiting: 4

Four rounds: the e-mails go out one by one, and the last customer waits about 800 ms. With order only the stock is under the lock:

Network net = new Network();
Shop shop = new Shop(net);
List<Thread> orders = new ArrayList<>();
for (int c = 1; c <= 4; c++) {
    String customer = "customer " + c;
    Thread t = new Thread(() -> shop.order(customer));
    orders.add(t);
    t.start();
}
for (Thread t : orders) {
    t.join();
}
System.out.println("Orders: 4, in stock: " + shop.left());
System.out.println("Rounds of waiting: " + net.rounds());

Output

Orders: 4, in stock: 6
Rounds of waiting: 1

The same stock, one round. The rules:

• Only the shared data under the lock. Compute, format and wait outside. Inside, only read and write.
• Never wait under a lock: network, disk, database, sleep. Take what you need, release the lock and then wait.
• One lock for one piece of data. The stock and the revenue are separate: each with its own lock, so that tills touching only one of them do not wait for each other.

More precisely, if you are curious

• synchronized is reentrant: a thread that already holds the lock can enter another block with the same lock again without waiting for itself. So is ReentrantLock, hence the name.
• ReentrantLock can do more than synchronized: tryLock() (take it if it is free, otherwise do something else), tryLock(100, TimeUnit.MILLISECONDS) and a fair queue with new ReentrantLock(true).
• Without the lock left() could also return an old number: the lock also guarantees the visibility from the last lesson.

A lock is not the only way. For one counter there are atomic operations, which do not make threads wait at all, and data that nobody changes needs no lock: the lesson "Atomic operations and immutable objects". And two locks that two threads take in a different order can stop the program forever: the lesson "Deadlock".

Exercise

The revenue and an order of several items

Solve the tasks in your editor.

The revenue. Fix the task from the last lesson: two tills with 50,000 sales each at €3, and Revenue protects total with a lock. Run the program several times: the revenue has to be the same every time.

Expect

Till 1: 50000 sales
Till 2: 50000 sales
Revenue (€):
300000

An order of several items. There are 5 items in stock. Write reserve(count): if there are at least count, it takes them and returns true, otherwise it takes nothing and returns false. Three customers want 2 items each at once, each in their own thread.

Expect

Ordered: 3
Accepted: 2
Refused: 1
In stock: 1

More tasks

• The price of a lock. Run the two tills with 1,000,000 sales each, with and without the lock, and time them. How much slower is it with the lock? And with 8 tills?
• Two locks. Add revenue to the stock, with its own lock. A sale subtracts from the stock and adds to the revenue. Do the two stay together if someone reads the stock and the revenue between the two locks? - tryLock. Make a sale that waits for the lock at most 50 ms with tryLock, and if it fails, returns "try again".

Test

Test yourself

1. Two threads call sell(), which does left-- under one and the same lock. What happens when the second reaches the lock while the first is inside?

It goes in right away, because the code is the sameIt throws an exceptionIt waits until the first leaves, and only then goes in

2. The check "are there items" is under the lock, and the subtraction is in a separate block under the same lock. Two people buy the last item. What happens?

The second always waits for the first to payIt is correct: both blocks are lockedThey can still sell two: between the two blocks the lock is free

3. Under the lock are the stock subtraction and sending an e-mail (~200 ms). Four orders come at once. How long does the last one wait?

Almost nothing: the lock is fastAbout 200 ms: the e-mails go out togetherAbout 800 ms: the e-mails go out one by one

4. What is wrong with synchronized (new Object()) { left--; }? (C#: lock (new object()), Python: with threading.Lock())

Every call makes its own lock, so the threads do not wait for each otherThe lock is never releasedNothing: any object can be a lock

Check

Start the lesson over

Related lessons

• Builds on: Lambdas · Threads · Why threads · Race condition
• Continues in: Atomic operations and immutable objects · Deadlock · Producer and consumer · async is not a thread
• Tasks on this topic: Concurrency and race conditions