Concurrency basics

Why this matters here

In an LLD interview, once you finish the design, the next question is almost always "what happens if two users do this at the same time?" Every system in this repo has that problem somewhere: two people booking the same seat, two cars taking the same parking spot, two threads calling getInstance().

This note covers the minimum you need to answer that question. The examples use Java 17 APIs.

Concurrency means several tasks are in progress during the same period, taking turns or overlapping. Parallelism means tasks really run at the same instant, on different CPU cores. This note is about concurrency: making sure tasks that overlap do not damage each other's work.

The problem: shared mutable state

A thread is one path of execution inside a program. Several threads can run in the same program at the same time. When two of them change the same object, things break in ways that are hard to repeat.

private int count = 0;

public void increment() {
    count++;     // looks like one step, is actually three
}

count++ is really:

1. read count from memory      (thread A reads 5)
2. add 1                       (thread A computes 6)
3. write it back               (thread A writes 6)

Say thread B does step 1 before A has done step 3. Both read 5 and both write 6. Two increments, but the count went up by only one. This is a race condition: the result depends on which thread wins the race.

The rule: if threads share data and any of them changes it, you must protect it.

If nothing is shared, or nothing changes, there is no problem. That is why immutable objects (objects that never change after they are built) are the easiest way to be thread safe.

synchronized

synchronized means "only one thread inside this at a time". Every Java object has a built in lock. A thread must take the lock to enter, and other threads wait until it is released.

public synchronized boolean lockSeat(Screening screening, Seat seat, String userId) {
    // only one thread can be in here at once
}

That is from SeatLockManager in the movie booking system. If two users click the same seat at the same moment, only one gets through the check at a time.

Four forms:

// method level, locks on 'this'
public synchronized void increment() { count++; }

// block level, locks on 'this', shorter critical section
public void increment() {
    doSomeSlowThingOutsideTheLock();
    synchronized (this) {
        count++;
    }
}

// lock on a private object, better because outsiders cannot grab your lock
private final Object lock = new Object();
public void increment() {
    synchronized (lock) {
        count++;
    }
}

// static method, locks on the class object, not an instance
public static synchronized void register() { }

Keep the synchronized region as small as you can. Threads go through it one by one, so a slow call inside makes every other thread wait.

volatile

volatile solves a different problem: visibility. Each CPU core may keep its own cached copy of a field. Without volatile, one thread can change the field and another thread may never see the new value.

private volatile boolean running = true;

public void stop() {
    running = false;
}

public void run() {
    while (running) {      // without volatile this can loop forever
        doWork();
    }
}

What volatile does and does not do:

Use it for a flag that one thread sets and others read. If you increment a value, or check it and then set it, you need synchronized or an atomic.

Atomic classes

AtomicInteger, AtomicLong, AtomicReference and friends do read, change and write back as one step that no other thread can interrupt. They need no lock.

private final AtomicInteger runCount = new AtomicInteger(0);

public void countRun() {
    runCount.incrementAndGet();   // safe, no synchronized needed
}

public int getRunCount() {
    return runCount.get();
}

Useful methods:

counter.incrementAndGet();          // ++x
counter.getAndIncrement();          // x++
counter.addAndGet(5);
counter.compareAndSet(expected, newValue);   // only sets if the value is still what you expect

compareAndSet is how optimistic locking works (more on that below). It means: "change it only if nobody else changed it since I looked." If it returns false, read again and retry.

For a single counter, atomics are faster than synchronized, because threads never have to wait. To update several fields together, you still need a lock.

Concurrent collections

ArrayList and HashMap are not thread safe. If two threads write to a HashMap at the same time, its inner structure can get damaged. In older Java versions it could even hang forever.

private final Map<String, SeatLock> lockedSeats = new ConcurrentHashMap<>();

That is SeatLockManager again. Reads never wait, and a write locks only a small part of the map, not the whole map.

A ConcurrentHashMap is not automatically enough

Each single operation is safe. Two operations in a row are not, because another thread can slip in between them.

// NOT safe, even on a ConcurrentHashMap
if (!map.containsKey(key)) {      // thread A checks, says no
    map.put(key, value);          // thread B does the same, both put
}

// safe, one atomic operation
map.putIfAbsent(key, value);

// also safe
map.computeIfAbsent(key, k -> new ArrayList<>());

This "check then act" gap is the most common concurrency bug. SeatLockManager also marks its methods synchronized for this reason: it checks and then puts.

ReentrantLock

A thread waiting on synchronized cannot give up after a time limit and cannot be interrupted. ReentrantLock allows both.

private final ReentrantLock lock = new ReentrantLock();

public void book() {
    lock.lock();
    try {
        // critical section
    } finally {
        lock.unlock();     // must be in finally, or a thrown exception leaks the lock
    }
}

// give up rather than wait forever
// tryLock with a time limit throws InterruptedException, so declare or catch it
if (lock.tryLock(2, TimeUnit.SECONDS)) {
    try {
        // got it
    } finally {
        lock.unlock();
    }
} else {
    // busy, do something else
}

Use synchronized by default. Choose ReentrantLock when you need tryLock, a timeout, or fairness (the longest waiting thread goes first).

There is also ReadWriteLock. It lets many readers in at once but only one writer. It helps when reads far outnumber writes.

Deadlock

A deadlock happens when two threads each hold a lock the other one wants, so both wait forever.

Thread A: holds lock on Seat 1, wants Seat 2
Thread B: holds lock on Seat 2, wants Seat 1
Both wait. Nothing moves.

The usual fix is lock ordering: every thread takes locks in the same order. Then nobody can hold the second lock while waiting for the first.

// Always lock the lower seat id first, whoever you are
Seat first  = seatA.getId() < seatB.getId() ? seatA : seatB;
Seat second = seatA.getId() < seatB.getId() ? seatB : seatA;

synchronized (first) {
    synchronized (second) {
        // safe
    }
}

Other options: use tryLock with a timeout and back off if it fails, or take one bigger lock instead of two small ones.

Optimistic vs pessimistic locking

There are two ways to handle conflicts. The movie booking system has a good comment on this. Know both.

SeatLockManager is pessimistic, with an expiry on the lock so an abandoned cart releases the seat.

Thread safe singleton

A Singleton must have only one instance, so it is where most people first meet this problem.

// BROKEN under threads: two threads can both see null and both create one
public static Singleton getInstance() {
    if (instance == null) {
        instance = new Singleton();
    }
    return instance;
}

Three correct versions:

// 1. Eager. Simple. Created at class load whether you use it or not.
private static final Singleton INSTANCE = new Singleton();

// 2. Static holder. Lazy and thread safe, no locking at all.
//    The JVM guarantees a class is initialised once.
private static class Holder {
    private static final Singleton INSTANCE = new Singleton();
}
public static Singleton getInstance() {
    return Holder.INSTANCE;
}

// 3. Double checked locking. Works only with volatile.
private static volatile Singleton instance;
public static Singleton getInstance() {
    if (instance == null) {
        synchronized (Singleton.class) {
            if (instance == null) {
                instance = new Singleton();
            }
        }
    }
    return instance;
}

Version 2 is what SingletonDesignPattern/After/JudgeAnalytics.java uses, and it is the one to recommend. Version 3 without volatile is a classic broken answer, because another thread can see a half built object.

In that class the counters are thread safe too: countRun() calls incrementAndGet() on an AtomicInteger. A plain run++ would lose counts.

Running work on threads

Do not create threads by hand. Use a thread pool, which is a fixed group of worker threads that take tasks one after another.

ExecutorService pool = Executors.newFixedThreadPool(4);

pool.submit(() -> processOrder(order));      // fire and forget

Future<BigDecimal> future = pool.submit(() -> calculateTotal(order));
BigDecimal total = future.get();             // blocks until it is done

pool.shutdown();                             // always shut down

Creating a thread is expensive, and too many threads can crash a machine. A pool reuses the same few threads.

Common mistakes

• Thinking volatile makes count++ safe. It does not. Use AtomicInteger or synchronized.
• Check then act on a concurrent collection. Use putIfAbsent or computeIfAbsent.
• Locking on a mutable field. If the field is reassigned, threads end up locking different objects, so they no longer block each other.
• Locking on a String or a boxed Integer. These are cached and shared across the whole JVM, so unrelated code can block you.
• unlock() outside a finally. One exception and the lock is never released.
• Synchronizing a huge method. Correct but slow. Shrink the critical section.
• Forgetting shutdown() on an executor. Its threads keep the JVM (the running Java program) alive.

Where you see it in this repo

• SeatLockManager in OOOD/02-movie-ticket-booking: ConcurrentHashMap plus synchronized methods plus lock expiry. The most complete example here
• ScreeningManager in the same system: bookSeatOptimistically checks at booking time and throws on a conflict
• JudgeAnalytics in SingletonDesignPattern/After: static holder singleton, with AtomicInteger counters

Related: 17-Collections.md for the concurrent collections, and 06-StaticAndFinal.md since final fields are safely published to other threads.