locks and AQS

the picture

synchronized is the door with a built-in lock: simple, automatic, can't forget to unlock it, can't do anything clever. ReentrantLock is the same door with a keypad. you have to remember to lock it on your way out (there's no block to do it for you), but you get options: "try the door and walk away if it's locked", "wait at most 100 ms", "stop waiting if someone calls me", "first come, first served".

the rule that comes with the keypad: unlock in finally, every time.

private final ReentrantLock lock = new ReentrantLock();
private int count;
 
void increment() {
    lock.lock();
    try {
        count++;
    } finally {
        lock.unlock();   // runs even if the body throws
    }
}

forget the finally, throw once, and that lock is held forever by a thread that's moved on with its life. every other thread that touches it parks for good.

what you get over synchronized

two of those, for real. the lock is held by main the whole time:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;
 
void main() throws InterruptedException {
    ReentrantLock lock = new ReentrantLock();
    lock.lock();                                         // main holds it and never lets go
    Thread impatient = Thread.ofPlatform().start(() -> {
        try {
            boolean got = lock.tryLock(100, TimeUnit.MILLISECONDS);
            IO.println("got the lock? " + got);          // false, after 100 ms
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    });
    impatient.join();
 
    Thread stuck = Thread.ofPlatform().start(() -> {
        try {
            lock.lockInterruptibly();                    // waits... until interrupted
        } catch (InterruptedException e) {
            IO.println("gave up waiting: interrupted");
        }
    });
    Thread.sleep(100);
    stuck.interrupt();
    stuck.join();
    lock.unlock();
}

got the lock? false
gave up waiting: interrupted

a thread stuck entering a synchronized block ignores interrupts completely. that difference is what lets you build deadlock escape hatches and cancellable work with explicit locks.

the queue underneath: AQS

ReentrantLock, ReentrantReadWriteLock, Semaphore, CountDownLatch and even the worker threads inside ThreadPoolExecutor all extend one class, AbstractQueuedSynchronizer. it holds:

• state, a single volatile int. what it means is up to the subclass: hold count for a lock, permits for a semaphore, the remaining count for a latch.
• a wait queue, a linked list of nodes for threads that couldn't get in, based on the CLH lock (Craig, Landin and Hagersten). enqueueing is one CAS on tail.
• park / unpark (LockSupport) to put queued threads to sleep and wake them, with no synchronized anywhere.

acquiring is "CAS the state, and if that fails, join the queue and park". releasing is "update the state, and unpark the first one in line". here's a ReentrantLock, opened up:

that barge is not a bug. it's why the default lock is non-fair: the thread that's already running can take a free lock immediately, while waking a parked thread takes microseconds. letting the runner in keeps throughput up. a fair lock hands the lock over in queue order every time, which means a context switch on almost every handoff. it's much slower under contention, and it still doesn't guarantee fair scheduling: the OS decides who actually runs.

many readers, one writer

lots of shared state is read constantly and written rarely (config, caches, routing tables). a plain lock makes readers wait for each other for no reason. a ReadWriteLock has two locks that cooperate: any number of threads can hold the read lock together, but the write lock is exclusive, against readers and other writers.

private final ReadWriteLock rw = new ReentrantReadWriteLock();
private Map<String, String> settings = new HashMap<>();
 
String get(String key) {
    rw.readLock().lock();
    try { return settings.get(key); }
    finally { rw.readLock().unlock(); }
}
 
void put(String key, String value) {
    rw.writeLock().lock();
    try { settings.put(key, value); }
    finally { rw.writeLock().unlock(); }
}

the read lock isn't free (every acquire still CASes a shared count, which bounces a cache line between cores), so it only pays off when reads are long or very frequent compared to writes. for a map, a ConcurrentHashMap usually beats both. and for "read often, replace rarely", a volatile reference to an immutable map beats everything.

StampedLock: read first, check later

StampedLock (java 8) adds an optimistic read: don't lock at all, copy the fields you need, then ask "did any writer get in while I was reading?". if not, you're done, having written nothing to shared memory. if yes, retry with a real read lock.

import java.util.concurrent.locks.StampedLock;
 
class Point {
    private final StampedLock lock = new StampedLock();
    private double x, y;
 
    void move(double dx, double dy) {
        long stamp = lock.writeLock();
        try {
            x += dx;
            y += dy;
        } finally {
            lock.unlockWrite(stamp);
        }
    }
 
    double distanceFromOrigin() {
        long stamp = lock.tryOptimisticRead();   // no lock taken, just a version number
        double cx = x, cy = y;                   // copy the fields
        if (!lock.validate(stamp)) {             // did a writer sneak in?
            stamp = lock.readLock();             // yes: fall back to a real read lock
            try {
                cx = x;
                cy = y;
            } finally {
                lock.unlockRead(stamp);
            }
        }
        return Math.sqrt(cx * cx + cy * cy);
    }
}
 
void main() {
    Point p = new Point();
    p.move(3, 4);
    IO.println(p.distanceFromOrigin());
}

5.0

conditions: wait sets with names

a monitor has exactly one wait set, which is why the bounded buffer needed notifyAll. a Lock can create as many Condition objects as you need, each its own queue: await() is wait(), signal() is notify(), signalAll() is notifyAll().

private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
 
void put(T item) throws InterruptedException {
    lock.lock();
    try {
        while (items.size() == capacity) notFull.await();
        items.addLast(item);
        notEmpty.signal();          // wake one consumer, never a producer
    } finally {
        lock.unlock();
    }
}

the same rules as wait() apply: you must hold the lock, and await() belongs in a while loop.

which one

• start with synchronized. it's simpler, it can't leak a lock, and it's not slower anymore.
• reach for ReentrantLock when you need tryLock, a timeout, interruptibility, fairness or several conditions.
• ReadWriteLock when reads are long and dominate. measure first.
• StampedLock for tiny, hot, read-mostly data (coordinates, counters, small value pairs), and only if you're careful.
• before any of them: can the state be immutable, confined to one thread, or inside a concurrent collection?