SyntaxPilot
Courses/Low-Level Design/Lesson 49
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 49 of 90

Concurrency 4: concurrent collections and coordination

ConcurrentHashMapcompute and merge atomicsCopyOnWriteArrayListBlockingQueueArrayBlockingQueueLinkedBlockingQueueDelayQueueproducer-consumerSemaphoreCountDownLatchCyclicBarrierCompletableFuturethenApply thenCombinevirtual threads

These are the notes for Low-Level Design (LLD) episode 49. Last time we built locks, atomic variables and thread pools. Real programs also share whole collections (maps, lists, queues) between threads, and threads must coordinate: hand work to each other, take turns, and wait for each other. We invent ConcurrentHashMap with its atomic merge and compute, CopyOnWriteArrayList, BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue, DelayQueue) and the producer-consumer pattern, Semaphore, CountDownLatch, CyclicBarrier, CompletableFuture with thenApply and thenCombine, and virtual threads. Every program was actually run with javac Main.java && java -cp . Main (Java 21). Outputs are real; timings are rounded by the programs, and the order of thread output (and the wrong counts of the broken programs) varies from run to run.

1. The real-life idea

In the cafe In java.util.concurrent
The ticket rail: the cook clips plates on, the waiter takes them off; full rail = cook waits, empty rail = waiter waits BlockingQueue: put() waits while full, take() waits while empty
Two ovens: a third cook waits until one is free Semaphore: a fixed number of permits
The shutter goes up only when all three staff have arrived CountDownLatch: await() until the count reaches 0
Friends at one table: the next course comes when all have finished CyclicBarrier: threads wait for each other, again and again
A token: "when my order is ready, pack it" CompletableFuture: chain steps on a result that comes later

Two words we use all the time:

  • Thread-safe: a class or method that keeps working correctly when many threads use it at the same time, with no extra locking by the caller. HashMap is not thread-safe; ConcurrentHashMap is.
  • Coordination: making threads wait for, signal, or hand work to each other in a planned way.

2. The problem: a shared HashMap

Two cashiers (two threads) count orders per dish in one map. Each does 50,000 chai and 50,000 samosa orders, so we expect 100,000 of each.

import java.util.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> orders = new HashMap<>();        // shared by both cashiers
        Runnable cashier = () -> {
            for (int i = 0; i < 100_000; i++) {
                String dish = (i % 2 == 0) ? "Chai" : "Samosa";
                Integer old = orders.get(dish);               // read...
                orders.put(dish, old == null ? 1 : old + 1);  // ...then write
            }
        };
        Thread a = new Thread(cashier), b = new Thread(cashier);
        a.start(); b.start(); a.join(); b.join();
        System.out.println(orders + "  (expected 100000 each)");
    }
}

Output (real; different on every run):

{Samosa=84098, Chai=54191}  (expected 100000 each)

Two separate problems:

  1. HashMap is not thread-safe. When two threads change it at the same time its internal arrays can be corrupted: entries can disappear, and in bad cases the map can even break.
  2. Read-then-write is two steps. Both threads can read 41, both write 42: one order is lost (the lost update from episode 46).

3. Thread-safe maps: synchronizedMap vs ConcurrentHashMap

Collections.synchronizedMap(new HashMap<>()) new ConcurrentHashMap<>()
How it is safe Every method takes one lock for the whole map Reads take no lock; a write locks only the small bin (bucket) that holds that key
Many threads at once Queue for that one lock, even to read Read and write in parallel
Iterating You must hold the map's lock yourself while looping Safe; the loop sees a weakly consistent view and never throws ConcurrentModificationException
null keys/values Allowed Not allowed (NullPointerException)

A bin is one slot of the map's internal array; keys whose hashes land in the same slot share a bin. Cashiers updating different dishes usually touch different bins, so they don't block each other.

But a safe map only makes each single call safe. get followed by put is still two calls, and another thread can run between them.

4. merge and compute: check-and-act in one step

import java.util.*;
import java.util.concurrent.*;
public class Main {
    static void race(Runnable job) throws InterruptedException {
        Thread a = new Thread(job), b = new Thread(job);
        a.start(); b.start(); a.join(); b.join();
    }
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> slow = new ConcurrentHashMap<>();
        race(() -> { for (int i = 0; i < 100_000; i++) {
            Integer old = slow.get("Chai");                          // safe map, but read...
            slow.put("Chai", old == null ? 1 : old + 1);             // ...then write: 2 steps
        } });
        System.out.println("get + put: " + slow);
        Map<String, Integer> orders = new ConcurrentHashMap<>();
        race(() -> { for (int i = 0; i < 100_000; i++)
            orders.merge("Chai", 1, Integer::sum);                   // read-add-write in ONE step
        });
        System.out.println("merge:     " + orders);
        orders.compute("Chai", (dish, n) -> n == null ? 1 : n * 2);  // any update, atomically
        System.out.println("compute:   " + orders);
    }
}

Output (real; the first number varies):

get + put: {Chai=195303}
merge:     {Chai=200000}
compute:   {Chai=400000}
  • merge(key, value, fn): if the key is missing, put value; otherwise put fn(oldValue, value). merge("Chai", 1, Integer::sum) means "add 1, starting from 1". The whole read-add-write is atomic: one indivisible step that no other thread can interrupt.
  • compute(key, (k, old) -> new): the general form. The function receives the key and the old value (or null) and returns the new value (or null to remove the key). Atomic for that key.
  • Related atomic one-call methods: computeIfAbsent(key, k -> new ...) (create a value only if missing, e.g. a list per customer), computeIfPresent, putIfAbsent(key, value) (returns the old value, or null if it inserted), remove(key, value) and replace(key, old, new) (only if the current value matches).

Rule: on a concurrent map never write if (!map.containsKey(k)) map.put(k, v) or map.put(k, map.get(k) + 1). Use the one-call method. Keep the functions you pass short, and never change other keys of the same map inside them.

5. The problem: changing a list while looping

The cafe announces "order 7 is ready" on every screen. While announcing, a customer's phone app joins the list.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        List<String> screens = new ArrayList<>(List.of("kitchen", "counter"));
        for (String s : screens) {                        // announce to every screen
            System.out.println(s + ": order 7 is ready");
            if (s.equals("kitchen")) screens.add("app");  // a new screen joins mid-loop
        }
    }
}

Output (real):

kitchen: order 7 is ready
Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
    at Main.main(Main.java:5)

A for-each loop uses an iterator: a small object that walks through a collection one element at a time (hasNext(), next()). ArrayList's iterator remembers how many times the list was changed (its modCount). When it sees an unexpected change it fails fast: it throws ConcurrentModificationException at once rather than give wrong results. Here one thread did it; with two threads (one looping, one adding) you get the same crash at random moments.

6. CopyOnWriteArrayList: loop over a snapshot

import java.util.*;
import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) {
        List<String> screens = new CopyOnWriteArrayList<>(List.of("kitchen", "counter"));
        for (String s : screens) {                        // loops over a snapshot
            System.out.println(s + ": order 7 is ready");
            if (s.equals("kitchen")) screens.add("app");  // add = copy the array
        }
        System.out.println("screens now: " + screens);
    }
}

Output (real):

kitchen: order 7 is ready
counter: order 7 is ready
screens now: [kitchen, counter, app]

Every add, set or remove on a CopyOnWriteArrayList makes a fresh copy of its internal array and swaps it in. An iterator walks over the snapshot: the array exactly as it was when the loop started, which never changes. So loops never throw, never need a lock, and never see half-made changes.

The price: every write copies the whole array. Use it when reads and loops vastly outnumber writes, for example a list of listeners (objects that want to be told when something happens), configuration, or a list of screens. Don't use it for a list that changes on every order. (CopyOnWriteArraySet is the set version.)

7. The problem: handing work over

import java.util.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Queue<String> rail = new LinkedList<>();           // the ticket rail, plain queue
        Thread cook = new Thread(() -> {
            sleep(300);                                    // cooking takes time
            rail.add("Masala Dosa");
        });
        cook.start();
        System.out.println("waiter got: " + rail.poll());  // nothing there yet!
        cook.join();
    }
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}

Output (real):

waiter got: null

Queue.poll() returns null when the queue is empty, and the cook hadn't finished. Polling again and again in a loop (while (rail.isEmpty()) { }) is busy waiting: the thread uses 100% of a processor core doing nothing useful. And LinkedList is not thread-safe anyway. We want a thread to sleep until work arrives.

8. BlockingQueue and the producer-consumer pattern

A BlockingQueue is a thread-safe queue whose put and take can block (wait without using the processor):

Method When full / empty Use
put(x) waits while full producer that must not drop work
take() waits while empty consumer
offer(x) / poll() return false / null at once "try, don't wait"
offer(x, time, unit) / poll(time, unit) wait at most that long with a timeout
add(x) / remove() throw an exception rarely what you want
import java.util.concurrent.*;
public class Main {
    static final long T0 = System.currentTimeMillis();
    static void log(String s) {
        System.out.println((System.currentTimeMillis() - T0) / 100 * 100 + " ms  " + s);
    }
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<String> rail = new ArrayBlockingQueue<>(2);  // room for only 2 plates
        Thread cook = new Thread(() -> {                           // the PRODUCER: fast
            try {
                for (String d : new String[]{"Dosa", "Idli", "Vada", "Upma"}) {
                    rail.put(d);                                   // blocks while the rail is full
                    log("cook put " + d);
                }
            } catch (InterruptedException e) { }
        });
        cook.start();
        for (int i = 0; i < 4; i++) {                              // main = the CONSUMER: slow
            Thread.sleep(500);
            log("waiter took " + rail.take());                     // blocks while it is empty
        }
    }
}

Output (real; lines with the same time can swap):

0 ms  cook put Dosa
0 ms  cook put Idli
500 ms  cook put Vada
500 ms  waiter took Dosa
1000 ms  waiter took Idli
1000 ms  cook put Upma
1500 ms  waiter took Vada
2000 ms  waiter took Upma

At 0 ms the rail (capacity 2) is full, so the fast cook waits; it can put Vada only after the waiter takes Dosa at 500 ms. The fast side is slowed to the speed of the slow side automatically.

Producer-consumer pattern: producers put work into a shared queue, consumers take it out. The queue decouples them: neither knows the other, you can add more of either, and their speeds can differ. It's how thread pools work inside (ExecutorService keeps a BlockingQueue of tasks), and how logging, order processing and message systems are built.

 Producer(s) --put()--> [ BlockingQueue ] --take()--> Consumer(s)
   cook, counter          the ticket rail              waiters, cooks

Which BlockingQueue?

Class What it is Example
ArrayBlockingQueue(n) Fixed-size array; bounded (has a maximum size) A rail with room for 2 plates
LinkedBlockingQueue / LinkedBlockingQueue(n) Linked nodes; limit optional; without one it is effectively unbounded (Integer.MAX_VALUE) Fixed thread pools use this for their task queue
DelayQueue<E extends Delayed> An element can be taken only when its delay has expired; ordered by time Reminders, retry-later jobs, cache expiry
PriorityBlockingQueue Takes the highest-priority element first; unbounded VIP orders first
SynchronousQueue Capacity 0: every put waits for a take (a direct hand-over) Used by cached thread pools

Back-pressure: with a bounded queue, when consumers fall behind, producers are forced to slow down (they block in put) instead of filling memory until the program dies with OutOfMemoryError. That push back is called back-pressure, and it's why bounded queues are the safe default.

DelayQueue example

import java.util.concurrent.*;
class Reminder implements Delayed {
    final String text; final long at;                          // when it becomes due
    Reminder(String text, long ms) { this.text = text; this.at = System.currentTimeMillis() + ms; }
    public long getDelay(TimeUnit u) { return u.convert(at - System.currentTimeMillis(), TimeUnit.MILLISECONDS); }
    public int compareTo(Delayed o) { return Long.compare(at, ((Reminder) o).at); }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        DelayQueue<Reminder> q = new DelayQueue<>();
        q.put(new Reminder("check table 4", 600));
        q.put(new Reminder("refill chai", 200));
        System.out.println("poll now: " + q.poll());              // nothing is due yet -> null
        System.out.println(q.take().text);                        // waits ~200 ms
        System.out.println(q.take().text);                        // waits until ~600 ms
    }
}

Output (real):

poll now: null
refill chai
check table 4

getDelay says how long is left; compareTo orders items by due time. take() waits until the earliest item is due.

9. Semaphore: at most N at a time

A lock lets in one thread. A semaphore holds a number of permits: acquire() takes one (waiting if none is free), release() gives one back. With 2 permits, at most 2 threads are inside at once.

import java.util.concurrent.*;
public class Main {
    static final long T0 = System.currentTimeMillis();
    static void log(String s) {
        System.out.println((System.currentTimeMillis() - T0) / 100 * 100 + " ms  " + s);
    }
    public static void main(String[] args) throws InterruptedException {
        Semaphore ovens = new Semaphore(2);                       // 2 permits = 2 ovens
        ExecutorService cooks = Executors.newFixedThreadPool(4);  // 4 cooks want to bake
        for (String pizza : new String[]{"Paneer", "Corn", "Veggie", "Cheese"}) {
            cooks.submit(() -> {
                try {
                    ovens.acquire();                              // take a permit, or wait
                    try { log(pizza + " in the oven"); Thread.sleep(500); }
                    finally { ovens.release(); }                  // give the permit back
                } catch (InterruptedException e) { }
            });
        }
        cooks.shutdown(); cooks.awaitTermination(5, TimeUnit.SECONDS);
        log("all baked, free ovens: " + ovens.availablePermits());
    }
}

Output (real; which two pizzas go first varies):

0 ms  Paneer in the oven
0 ms  Corn in the oven
500 ms  Veggie in the oven
500 ms  Cheese in the oven
1000 ms  all baked, free ovens: 2
  • Always release() in finally, or an exception leaks the permit; leak both and every cook waits forever.
  • tryAcquire() takes a permit only if one is free (returns true/false), optionally with a timeout.
  • A semaphore doesn't remember who took a permit: any thread can release, and releasing too often adds permits (new Semaphore(1), one tryAcquire, two release calls leaves availablePermits() == 2, real output).
  • Typical uses: limit 10 database connections, 5 downloads at once, 3 calls per second to a partner API.

10. The problem: opening too early

public class Main {
    public static void main(String[] args) throws InterruptedException {
        for (String who : new String[]{"cashier", "cook", "cleaner"}) {
            int ms = who.length() * 100;  // each arrives at a different time
            new Thread(() -> { sleep(ms); System.out.println(who + " is ready"); }).start();
        }
        Thread.sleep(500);                // guess: "everyone is surely ready"
        System.out.println("Cafe is OPEN!");
    }
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}

Output (real):

cook is ready
Cafe is OPEN!
cashier is ready
cleaner is ready

Sleeping is guessing the time: too short and it breaks, too long and you waste time. join() would work only if each staff thread ends when ready; real threads (a server, a cache loader) keep running. We need "wait until exactly 3 events have happened".

11. CountDownLatch

import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        CountDownLatch ready = new CountDownLatch(3);  // count starts at 3
        for (String who : new String[]{"cashier", "cook", "cleaner"}) {
            int ms = who.length() * 100;
            new Thread(() -> {
                sleep(ms); System.out.println(who + " is ready");
                ready.countDown();                     // 3 -> 2 -> 1 -> 0
            }).start();
        }
        ready.await();                                 // wait until the count is 0
        System.out.println("Cafe is OPEN!");
    }
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}

Output (real; the first three lines can be in any order, "OPEN" is always last):

cook is ready
cashier is ready
cleaner is ready
Cafe is OPEN!

A CountDownLatch(n) starts at n. Any thread calls countDown() (n → n−1). await() blocks until the count reaches 0, then lets everyone through, forever after. It is single-use: it can't be reset. Uses: start serving only after all parts have loaded; in tests, wait until background work finished (await(5, SECONDS) returns false on timeout).

12. CyclicBarrier

import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) {
        CyclicBarrier table = new CyclicBarrier(3,  // 3 friends at one table
            () -> System.out.println("-- all 3 done: serve the next course --"));
        for (String friend : new String[]{"Asha", "Ravi", "Neha"}) {
            new Thread(() -> {
                try {
                    for (String course : new String[]{"soup", "thali"}) {
                        Thread.sleep(friend.length() * 100 + (int) (Math.random() * 300));
                        System.out.println(friend + " finished " + course);
                        table.await();              // wait for the other two
                    }
                } catch (Exception e) { }
            }).start();
        }
    }
}

Output (real; the order within each course varies):

Ravi finished soup
Asha finished soup
Neha finished soup
-- all 3 done: serve the next course --
Asha finished thali
Neha finished thali
Ravi finished thali
-- all 3 done: serve the next course --

A CyclicBarrier(n, action) is a meeting point for n threads. Each calls await(); the first n−1 wait; when the nth arrives, the optional barrier action runs once, all are released, and the barrier resets for the next round ("cyclic"). If one waiting thread is interrupted or times out, the others get a BrokenBarrierException.

CountDownLatch CyclicBarrier
Who waits Any threads wait for events The same n threads wait for each other
Who counts Others call countDown() (can be one thread, many times) Each participant's own await()
Reusable No Yes, resets after each round
Example Open when 3 staff are ready Next course when all 3 friends finish

(Phaser is a more flexible barrier whose number of parties can change.)

13. The problem: waiting in a line

import java.util.concurrent.*;
public class Main {
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
    static int callService(int ms, int value) { sleep(ms); return value; }
    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        int price = callService(1000, 250);    // ask the menu service: 1 s
        int discount = callService(1000, 30);  // then the offers service: 1 s
        System.out.println("Bill: Rs " + (price - discount));
        System.out.println("took about " + (System.currentTimeMillis() - t0) / 100 * 100 + " ms");
    }
}

Output (real):

Bill: Rs 220
took about 2000 ms

The two calls don't depend on each other, yet the second waits for the first. A Future from episode 48 can run them in parallel, but get() blocks: the calling thread sits idle. We want to describe what happens when results arrive.

14. CompletableFuture

import java.util.concurrent.*;
public class Main {
    static int sleep(int ms, int value) {
        try { Thread.sleep(ms); } catch (InterruptedException e) { }
        return value;
    }
    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        CompletableFuture<Integer> price =                         // ask the menu service
            CompletableFuture.supplyAsync(() -> sleep(1000, 250));
        CompletableFuture<Integer> discount =                      // ask the offers service
            CompletableFuture.supplyAsync(() -> sleep(1000, 30));  // both run AT THE SAME TIME
        CompletableFuture<String> bill = price
            .thenCombine(discount, (p, d) -> p - d)                // when BOTH are ready
            .thenApply(total -> "Bill: Rs " + total);              // then transform the result
        System.out.println("main is free while we wait...");
        System.out.println(bill.join());                           // wait for the final value
        System.out.println("took about " + (System.currentTimeMillis() - t0) / 100 * 100 + " ms");
    }
}

Output (real):

main is free while we wait...
Bill: Rs 220
took about 1000 ms
  • Asynchronous means "start it and return at once; the result comes later". CompletableFuture.supplyAsync(supplier) runs the supplier in the background (by default on the shared ForkJoinPool.commonPool(); on a machine with very few cores Java uses a new thread per task instead, which is why our test machine printed Thread-0; or on an Executor you pass as a second argument) and returns a CompletableFuture immediately.
  • thenApply(fn): when this result is ready, transform it (like map).
  • thenCombine(other, (a, b) -> ...): when both are ready, combine them.
  • thenAccept(consumer): use the result, return nothing. thenCompose(fn): chain a step that itself returns a CompletableFuture (like flatMap). exceptionally(fn): replace a failure with a fallback value.
  • join(): wait for the result, like get(), but throws an unchecked CompletionException instead of checked exceptions. allOf(...) / anyOf(...) wait for all / the first of many.
import java.util.concurrent.*;
public class Main {
    static int slow(int ms, int v) { try { Thread.sleep(ms); } catch (InterruptedException e) { } return v; }
    public static void main(String[] args) {
        CompletableFuture<Integer> price = CompletableFuture.supplyAsync(() -> slow(300, 250));
        CompletableFuture<Integer> tax = CompletableFuture.supplyAsync(() -> slow(300, 13));
        CompletableFuture<Integer> discount = CompletableFuture.supplyAsync(() -> slow(300, 30));
        int bill = price.thenCombine(tax, Integer::sum).thenCombine(discount, (a, b) -> a - b).join();
        System.out.println("bill = " + bill);
        CompletableFuture.supplyAsync(() -> "order-7")
            .thenCompose(id -> CompletableFuture.supplyAsync(() -> id + " is ready"))   // a call that returns a future
            .thenAccept(msg -> System.out.println("screen: " + msg))                    // consume, return nothing
            .join();
        int safe = CompletableFuture.supplyAsync(() -> 100 / 0)
            .exceptionally(ex -> { System.out.println("failed: " + ex.getCause()); return -1; })
            .join();
        System.out.println("fallback = " + safe);
    }
}

Output (real):

bill = 233
screen: order-7 is ready
failed: java.lang.ArithmeticException: / by zero
fallback = -1

15. Virtual threads

import java.util.concurrent.*;
public class Main {
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
    static long run(ExecutorService pool) throws InterruptedException {
        long t0 = System.currentTimeMillis();
        for (int i = 0; i < 2_000; i++) pool.submit(() -> sleep(200));  // each task WAITS 0.2 s
        pool.shutdown(); pool.awaitTermination(1, TimeUnit.MINUTES);
        return System.currentTimeMillis() - t0;
    }
    public static void main(String[] args) throws InterruptedException {
        long fixed = run(Executors.newFixedThreadPool(100));  // 100 OS threads
        System.out.println("fixed pool of 100: about " + fixed / 100 * 100 + " ms");
        long virt = run(Executors.newVirtualThreadPerTaskExecutor());  // 1 per task
        System.out.println("virtual threads:   about " + virt / 100 * 100 + " ms");
        Thread v = Thread.ofVirtual().start(() -> { });
        System.out.println("is it virtual? " + v.isVirtual());
    }
}

Output (real):

fixed pool of 100: about 4100 ms
virtual threads:   about 200 ms
is it virtual? true
  • A platform thread (the normal new Thread) is a thin wrapper around an operating-system thread. Each has a large stack reserved and costs the OS real bookkeeping, so a program can have thousands, not millions. In a pool of 100, only 100 tasks can be waiting at the same time: 2,000 tasks × 0.2 s / 100 = about 4 s.
  • A virtual thread is a lightweight thread managed by the JVM itself. When it blocks (sleep, network, file, BlockingQueue.take), the JVM parks it (saves its small stack in memory) and runs another virtual thread on the same OS thread. The OS thread underneath is called the carrier thread. Millions of virtual threads can exist.
  • Virtual threads became a final feature in JDK 21 (released 19 September 2023; JEP 444). Create them with Thread.ofVirtual().start(r), Thread.startVirtualThread(r) or Executors.newVirtualThreadPerTaskExecutor() (one new virtual thread per task).
  • They are cheap, so you don't pool them: one per task. To limit how many use a scarce resource (database connections), use a Semaphore, not a small pool.
  • They make waiting cheap, not computing fast: CPU-heavy work is still limited by the number of cores, and a fixed pool sized to the cores is still right for it.

Common mistakes

Mistake What you see (real) Why Fix
map.put(k, map.get(k) + 1) on a ConcurrentHashMap No error: lost updates ({Chai=195303}) Two calls, not atomic map.merge(k, 1, Integer::sum)
Sharing a plain HashMap between threads No error: wrong counts, possible corruption Not thread-safe ConcurrentHashMap
map.put("Chai", null) on ConcurrentHashMap java.lang.NullPointerException Nulls not allowed Use a real value or remove
Adding to an ArrayList inside its for-each java.util.ConcurrentModificationException The iterator saw a change CopyOnWriteArrayList, Iterator.remove(), or collect changes and apply after
while (q.isEmpty()) { } No error: 100% CPU Busy waiting BlockingQueue.take()
add() on a full ArrayBlockingQueue java.lang.IllegalStateException: Queue full add throws instead of waiting put (wait) or offer (returns false)
acquire() without finally { release(); } No error: permits leak, everyone waits An exception skipped release try { ... } finally { release(); }
Thread.sleep(500) to wait for other threads No error: sometimes too early Guessing the time CountDownLatch.await()
Pooling virtual threads in a small fixed pool No speed-up Pool size limits waiting tasks newVirtualThreadPerTaskExecutor() + a Semaphore if you must limit

Mini project: an order pipeline

A counter (producer) feeds a bounded rail; 4 cooks (consumers, on virtual threads) share 2 stoves (semaphore), count dishes in a ConcurrentHashMap, and a latch says when every order is done.

import java.util.*;
import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        List<String> orders = List.of("Chai", "Dosa", "Chai", "Idli", "Chai", "Dosa", "Vada", "Chai");
        BlockingQueue<String> rail = new ArrayBlockingQueue<>(3);  // bounded: back-pressure
        Map<String, Integer> cooked = new ConcurrentHashMap<>();
        Semaphore stoves = new Semaphore(2);                       // only 2 stoves
        CountDownLatch allDone = new CountDownLatch(orders.size());
        try (ExecutorService kitchen = Executors.newVirtualThreadPerTaskExecutor()) {
            for (int c = 0; c < 4; c++) kitchen.submit(() -> {     // 4 cooks (consumers)
                try {
                    while (true) {
                        String dish = rail.take();
                        stoves.acquire();
                        try { Thread.sleep(50); cooked.merge(dish, 1, Integer::sum); }
                        finally { stoves.release(); }
                        allDone.countDown();
                    }
                } catch (InterruptedException e) { }               // interrupted = kitchen closing
                return null;
            });
            for (String o : orders) rail.put(o);                   // the counter (producer)
            allDone.await();                                       // every order cooked
            System.out.println("cooked: " + new TreeMap<>(cooked));
            kitchen.shutdownNow();                                 // interrupt the idle cooks
        }
    }
}

Output (real):

cooked: {Chai=4, Dosa=2, Idli=1, Vada=1}

shutdownNow() interrupts the cooks idling in take(), so they leave their loop; the try-with-resources close() then waits for them.

Practice

1. Count words in customer reviews from 4 threads.

Answer
import java.util.*;
import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) throws InterruptedException {
        List<String> reviews = List.of("good chai", "good dosa good chai", "cold chai", "good service");
        Map<String, Integer> words = new ConcurrentHashMap<>();
        try (ExecutorService pool = Executors.newFixedThreadPool(4)) {
            for (String r : reviews)
                pool.submit(() -> { for (String w : r.split(" ")) words.merge(w, 1, Integer::sum); });
        }                                                          // close() waits for the tasks
        System.out.println(new TreeMap<>(words));
    }
}

Output (real):

{chai=3, cold=1, dosa=1, good=4, service=1}

2. 2 cooks and 3 waiters share one BlockingQueue. How do the waiters know when to stop?

Answer

Send one poison pill (a special "no more work" item) per consumer after the producers finish.

import java.util.concurrent.*;
public class Main {
    static final String DONE = "DONE";                             // a "poison pill": no more work
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<String> rail = new LinkedBlockingQueue<>(5);
        Thread[] waiters = new Thread[3];
        for (int w = 0; w < 3; w++) {
            String name = "waiter-" + (w + 1);
            waiters[w] = new Thread(() -> {
                try {
                    while (true) {
                        String dish = rail.take();
                        if (dish.equals(DONE)) return;
                        System.out.println(name + " served " + dish);
                    }
                } catch (InterruptedException e) { }
            });
            waiters[w].start();
        }
        Thread cook1 = new Thread(() -> { for (int i = 1; i <= 3; i++) put(rail, "dosa-" + i); });
        Thread cook2 = new Thread(() -> { for (int i = 1; i <= 3; i++) put(rail, "idli-" + i); });
        cook1.start(); cook2.start(); cook1.join(); cook2.join();
        for (int w = 0; w < 3; w++) rail.put(DONE);                // one pill per waiter
        for (Thread t : waiters) t.join();
        System.out.println("kitchen closed, rail empty: " + rail.isEmpty());
    }
    static void put(BlockingQueue<String> q, String s) { try { q.put(s); } catch (InterruptedException e) { } }
}

Output (real; who serves what varies):

waiter-3 served dosa-3
waiter-3 served idli-1
waiter-3 served idli-2
waiter-3 served idli-3
waiter-1 served dosa-1
waiter-2 served dosa-2
kitchen closed, rail empty: true

3. Allow at most 3 downloads at the same time. Which tool, and where do you release?

Answer

Semaphore downloads = new Semaphore(3); then in each task downloads.acquire(); try { download(); } finally { downloads.release(); }.

4. Price, tax and discount come from three slow services. Compute price + tax - discount with all three calls running at once.

Answer

See the first part of the CompletableFuture example in section 14: price.thenCombine(tax, Integer::sum).thenCombine(discount, (a, b) -> a - b).join() printed bill = 233 in about 300 ms, not 900 ms.

5. Latch or barrier? (a) Start a game when 4 players have joined. (b) 4 simulation threads must all finish step k before any starts step k+1, for 100 steps.

Answer

(a) CountDownLatch(4) (one-time event). (b) CyclicBarrier(4) (threads wait for each other, every step).

Quick quiz

var q = new ArrayBlockingQueue<String>(2);
System.out.println(q.offer("Dosa"));
System.out.println(q.offer("Idli"));
System.out.println(q.offer("Vada"));

What is printed? (a) true true true (b) true true false (c) true true, then it waits forever (d) true false false

Answer

(b) true true false. The queue holds 2; offer never waits, so the third returns false at once. put would wait forever here (nobody takes), and add would throw IllegalStateException: Queue full.

Interview questions

  1. HashMap vs Collections.synchronizedMap vs ConcurrentHashMap? Not thread-safe / one lock for everything / lock-free reads and per-bin locking for writes, atomic merge/compute, no nulls, weakly consistent iterators.
  2. Is ConcurrentHashMap enough to make if (!m.containsKey(k)) m.put(k, v) safe? No: two calls. Use putIfAbsent or computeIfAbsent.
  3. When would you use CopyOnWriteArrayList? Many reads/iterations, rare writes (listener lists). Never for write-heavy lists.
  4. Explain producer-consumer and how to implement it in Java. Producers put, consumers take on a shared BlockingQueue; bounded for back-pressure; poison pills or interrupts to stop.
  5. ArrayBlockingQueue vs LinkedBlockingQueue? Fixed array and one lock, always bounded / linked nodes with separate put and take locks, optionally bounded.
  6. What does a Semaphore do that a lock can't? Allows up to N holders; permits aren't owned, so another thread may release.
  7. CountDownLatch vs CyclicBarrier? Events counted by anyone, single use / n parties waiting for each other, reusable, with a barrier action.
  8. Future vs CompletableFuture? Future only lets you block on get(); CompletableFuture lets you chain (thenApply, thenCombine, thenCompose), handle errors (exceptionally) and complete it manually.
  9. What are virtual threads and when do they help? JVM-managed lightweight threads (final in Java 21); great for many blocking, I/O-bound tasks with simple thread-per-task code; no help for CPU-bound work.
  10. Why shouldn't you pool virtual threads? They are cheap to create; pooling only limits concurrency. Limit access to scarce resources with a semaphore instead.

Glossary

Term Meaning, with an example
Thread-safe Works correctly when many threads use it at once, with no extra locking by the caller: ConcurrentHashMap
Concurrent collection A collection from java.util.concurrent designed for many threads: ConcurrentHashMap, CopyOnWriteArrayList, BlockingQueue
ConcurrentHashMap A thread-safe hash map: lock-free reads, per-bin locking for writes
Bin One slot (bucket) of a hash map's internal array; keys with the same slot share it
Collections.synchronizedMap Wraps a map so every method uses one lock: safe but everyone queues
merge Atomic "put if absent, otherwise combine": merge("Chai", 1, Integer::sum)
compute Atomic "new value = f(key, old value)" for one key
computeIfAbsent / putIfAbsent Create / insert a value only if the key is missing, in one atomic call
Atomic Done as one indivisible step that no other thread can interrupt
Check-then-act Read something, then act on it, in two steps: unsafe unless made atomic
Iterator An object that walks a collection one element at a time; used by for-each
ConcurrentModificationException Thrown by fail-fast iterators when the collection changed during the loop
Fail-fast Stopping with an error at the first sign of a problem instead of continuing wrongly
CopyOnWriteArrayList A list that copies its array on every write; loops see a snapshot
Snapshot A frozen copy of the data as it was at one moment
Listener An object that wants to be told when something happens: a screen showing "order ready"
Busy waiting Looping and checking a condition again and again, burning CPU
BlockingQueue A thread-safe queue whose put waits while full and take waits while empty
Block Wait without using the processor until something happens
Bounded queue A queue with a maximum size: new ArrayBlockingQueue<>(2)
ArrayBlockingQueue A bounded blocking queue backed by a fixed array
LinkedBlockingQueue A blocking queue of linked nodes, optionally bounded
DelayQueue A blocking queue whose items can be taken only after their delay expires
Producer-consumer Pattern: producers put work into a shared queue, consumers take it out
Poison pill A special item that tells a consumer "no more work, stop"
Back-pressure A slow consumer forcing producers to slow down (a full bounded queue blocks put)
Semaphore A counter of permits: acquire() takes one or waits, release() returns one
Permit One "right to enter" held by a semaphore: one oven
CountDownLatch A one-time gate that opens when its count reaches 0; countDown(), await()
CyclicBarrier A reusable meeting point where n threads wait for each other
Barrier action Code that runs once each time all parties reach the barrier
Asynchronous Started now, finishes later, without the caller waiting
CompletableFuture A future you can chain steps onto and complete later
supplyAsync Run a value-returning task in the background, returning a CompletableFuture at once
thenApply When the result is ready, transform it
thenCombine When two results are both ready, combine them
thenCompose / thenAccept / exceptionally Chain a future-returning step / consume the result / recover from a failure
join() Wait for a CompletableFuture's result (unchecked exceptions)
Platform thread A Java thread backed one-to-one by an operating-system thread
Virtual thread A lightweight JVM-managed thread (final in Java 21) that is parked while it waits
Carrier thread The OS-backed thread that a virtual thread runs on at a given moment
I/O-bound vs CPU-bound Mostly waiting for input/output (network, disk) vs mostly computing

Summary

  • ConcurrentHashMap is safe for many threads; do check-then-act with merge, compute, computeIfAbsent, putIfAbsent.
  • CopyOnWriteArrayList loops over a snapshot: for many reads, few writes.
  • BlockingQueue (put/take) is the heart of producer-consumer; bounded queues give back-pressure.
  • Semaphore: at most N at once. CountDownLatch: wait for N events, once. CyclicBarrier: N threads meet, again and again.
  • CompletableFuture runs independent work at the same time and chains steps with thenApply / thenCombine.
  • Virtual threads (Java 21) make thread-per-task cheap for waiting work.

Next episode: Concurrency 5: deadlocks, the Coffman conditions, livelock and starvation, thread dumps, optimistic vs pessimistic locking, idempotency, concurrency patterns and designing thread-safe classes.