Syllabus · E3
Lock granularity and acquisition order — a deadlock needs two locks and two orders
The idea
A deadlock needs two locks and two orders
Your limiter gives every budget its own lock, so two callers never queue behind each other. Then the interviewer adds a shared cap: each request must fit its caller's budget and the estate-wide one. It must hold both locks across check-then-charge, or it can be allowed by a budget that is spent before it is charged.
tryAcquire takes own-then-cap. A reporting method takes cap-then-own. worked/Main.java pins that shape: stopped on 10 of 10 runs. Unpinned, it hung in 50 of 50 trials, within 18 acquire-release laps. jstack prints Found one Java-level deadlock and names who holds what. Nothing throws. CPU falls to zero.
A cycle needs two locks, both held while asking for the other, in opposite orders. Delete any ingredient and the hang is impossible, and that ranks the fixes. First, make the second lock not exist: one lock over everything, the choice corpus/lru-cache defends, get included. Second, when two locks are genuinely needed, compute one canonical order from the keys, in the one method that acquires. Sorted, not "own budget first": an agreed order lives in convention, and the next method forgets it. Third, tryLock with a timeout, which trades the hang for retry storms plus a partial-failure path you now own.
Measured in contrast/: per-key locks beat one lock by 1.9x to 3.5x on the base problem. Then the cap serialises every request anyway — one lock 15.8M ops/s, per-key with ordering 9.4M. The finer grain lost its own race. node lessons/E3/contrast/bench.mjs reproduces both numbers.
Worked walkthrough
NOTES — three files, one deadlock, and the line that prevents it
Run it first
..\..\..\..\.toolchain\jdk-21\bin\javac.exe -Xlint:all -d out src\*.java
..\..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Mainjavac -Xlint:all prints nothing and exits 0. Real output, verbatim, from one run:
1. two locks, two orders, pinned: the deadlock every run
"tryAcquire(acme)" waits for ReentrantLock$NonfairSync@4783da3f held by "remaining(acme)"
"remaining(acme)" waits for ReentrantLock$NonfairSync@254989ff held by "tryAcquire(acme)"
dismantled by interrupt -- possible only because the demo used lockInterruptibly()
2. the same two locks, unpinned: acquisitions survived before the hang
trial 1: hung; own-then-cap survived 1 laps, cap-then-own 1
trial 2: hung; own-then-cap survived 7 laps, cap-then-own 0
trial 3: hung; own-then-cap survived 1 laps, cap-then-own 1
trial 4: hung; own-then-cap survived 6 laps, cap-then-own 0
trial 5: hung; own-then-cap survived 0 laps, cap-then-own 0
3. Limiter: one method takes the locks, in the order the keys give
lockOrder(acme) = [__cap__, acme]
lockOrder(zeta) = [__cap__, zeta]
128 threads, cap 16: allowed = 16, every thread returned = true
remaining(acme) = 0, remaining(zeta) = 0
4. reentrancy is not deadlock immunity
same lock taken twice by one thread: holdCount = 2, no hang
blocks 1 and 2 deadlocked with ReentrantLocks -- the cycle is between threads, not within oneTwo threads that would each finish in microseconds alone stop each other forever. Nothing throws. Nothing logs. CPU drops to zero and stays there, which is why this failure reaches production more often than a crash does.
The observed rates, so "it hangs" is a measurement and not a mood
Block 1 pins the interleaving with a latch: each thread takes its first lock, then both go for their second. Ten consecutive runs of Main: the JVM's own detector reported the cycle in 10 of 10.
Block 2 removes the pin, which makes it the honest version — production threads are not latched. Fifty trials across those ten runs: hung in 50 of 50, after between 0 and 18 acquire-release laps. Most trials died inside 3 laps. Do not conclude the race is always this hot. The window here is two adjacent acquisitions with nothing between them; a real limiter does work between its locks, and a colder race can survive for weeks. The corpus's own version, corpus/rate-limiter/curveballs/02-global-backstop-cap, needs 128 threads across two callers to make the same shape stop in a test's lifetime.
What a thread dump says, because you will be reading one someday
The same two-lock shape was left hanging in a separate process (plain lock(), nothing interruptible) and jstack <pid> was pointed at it. Real output, trimmed to the verdict:
Found one Java-level deadlock:
=============================
"tryAcquire(acme)":
waiting for ownable synchronizer 0x0000000660dc8060,
(a java.util.concurrent.locks.ReentrantLock$NonfairSync),
which is held by "remaining(acme)"
"remaining(acme)":
waiting for ownable synchronizer 0x0000000660dc8030,
(a java.util.concurrent.locks.ReentrantLock$NonfairSync),
which is held by "tryAcquire(acme)"
...
Found 1 deadlock.The JVM names the cycle for you: who holds what, who waits for what. Block 1 reads the same facts programmatically through ThreadMXBean.findDeadlockedThreads(), which is how a test can assert on a deadlock without hanging itself.
Why block 1 cannot fail to deadlock
A deadlock needs a cycle: thread 1 holds A and wants B, thread 2 holds B and wants A. Usually you race for it, which is block 2. Block 1 removes the race: the latch releases neither thread into its second acquisition until both hold their first. After the latch, the cycle is not likely; it is the only reachable state. That is worth internalising in the other direction too. Every ingredient is necessary. Two locks, both held while asking for the other, in opposite orders. Delete any one ingredient and the hang is not rare — it is impossible. Each of the three fixes below deletes a different one.
The three fixes, ranked, and why this order
Fix 1: make the second lock not exist. contrast/a-backstop/ serves the same contract with one lock over everything. At most one lock means no cycle, provably, with nothing to remember and nothing to review. This is usually available in an LLD round, and it is what corpus/lru-cache/reference/src/LruCache.java chose. One monitor covers the map and the eviction policy together, get included, because that contract says a read mutates eviction standing. That is a defensible level-3 answer, not a compromise. Say what the lock protects and why one is enough. The cost is real and measured below: callers serialise. Pay it knowingly — at this problem's size it is nowhere near the bottleneck.
Fix 2: one canonical order, computed, in one method. When the design genuinely needs two locks at once, Limiter is the shape: scopeOf sorts the budgets by key, and locked is the only code that acquires. Canonical beats agreed. "Take your own budget before the cap" is an agreement. It lives in the heads of whoever wrote today's call sites, and the next method starts the clock on forgetting it. scope.sort(comparing(Budget::key)) is a computation; any future code path derives the same order from the same data. C++ has std::lock(a, b) to dodge this; Java has no equivalent, so the order is yours to state. State it somewhere a test can reach (lockOrder() here), because an order you cannot query is an order a review cannot check.
Fix 3: tryLock with a timeout, then back off and retry. Last, and not because it fails — because of what it converts the problem into. A hang becomes a retry storm at exactly the moment the system is busiest. You now own new failure modes. A request that gives up half-acquired must release what it holds and report something. Two polite threads can back off in lockstep and starve, which is livelock. Every caller needs a policy for "busy". Reach for it when you do not control all the locking code, so no canonical order can be imposed. When you do control it, fixes 1 and 2 make the failure impossible instead of survivable.
Budget.java, line by line
private final ReentrantLock lock — one lock per budget, not per limiter. The granularity choice. Two callers share nothing, so they should not queue behind each other. contrast/ measures what that is worth before you pay for it: 1.9x at 2 hot callers, 3.5x at 8. Then the shared cap arrives and takes it all back. Read contrast/curveball.md before copying this grain.
lock() / unlock() exposed, methods not self-locking — because check-then-charge spans several budgets, and only the caller knows the whole set. A budget that locked itself per method would make each call atomic and the request torn. Same reasoning, at full scale, in corpus/rate-limiter/reference/src/KeyBudget.java's javadoc.
requireLocked() — the precondition, checked rather than trusted. Without it, a forgotten lock() is a lost update under load. It passes every single-threaded test. With it, the same mistake is an AssertionError at the offending line on the first call. AssertionError and not IllegalStateException, because no caller of Limiter can trigger this; only a bug in these two files can, and the two cases deserve different words.
Limiter.java, the lines that carry the design
scopeOf adds the cap once — a request under the cap's own key draws on that budget once, not twice. The double lock() would not even hang, because the lock is reentrant with holdCount 2. It would double-charge, silently, which is worse than hanging.
scope.sort(Comparator.comparing(Budget::key)) — the one line this lesson exists for. See fix 2.
locked counts acquired — release in reverse, and release exactly what was taken. If acquisition throws part-way, the finally must not unlock() a lock this thread never got: that throws IllegalMonitorStateException at best and corrupts accounting at worst.
allow checks everything, then charges everything — all-or-nothing under every lock at once. A loop that locks, checks and charges one budget at a time leaks: the caller's own budget gets spent by requests the cap then refuses. faded/GapTest.java measures that wrong answer at 75 remaining where the honest figure is 95.
remaining goes through the same locked and the same scope — a second reader is a second chance to invent a second order. The corpus reference shipped exactly this bug, invisibly, until a second scope existed; corpus/rate-limiter/reference/DECISION_LOG.md tells it in full.
Block 4, the reentrancy line
getHoldCount() returning 2 surprises a C++ developer, where relocking a held std::mutex is undefined behaviour. J12 measured this; it is why a public method calling another public method of the same class does not self-deadlock in Java. Note the boundary of the favour: reentrancy is one thread re-entering one lock. Blocks 1 and 2 deadlocked using ReentrantLock throughout, because a cycle is two threads and two locks.
When not to
When not to split the lock
This lesson teaches the discipline that makes many locks safe. The counterweight is that the discipline has a price, and most LLD problems never earn it. STANDARD v1.0's D3 level 3 asks for a minimal seam set; the concurrency version of that symmetry is a minimal lock set. Machinery for a contention problem you have not measured is the over-engineered tag wearing a ReentrantLock.
The concrete bad example
An LRU cache, written by someone who has read about lock striping. Split into files next to a map and a recency list, it compiles clean under javac -Xlint:all:
public final class StripedLruCache {
private final Object[] stripes = new Object[16];
private final Map<String, Object> values = new HashMap<>();
private final LinkedHashMap<String, Boolean> recency = new LinkedHashMap<>();
public StripedLruCache() {
for (int i = 0; i < stripes.length; i++) stripes[i] = new Object();
}
public Object get(String key) {
synchronized (stripes[Math.floorMod(key.hashCode(), 16)]) {
recency.remove(key);
recency.put(key, Boolean.TRUE);
return values.get(key);
}
}
}Sixteen locks, and not one invariant protected. values and recency must move together on every call, whatever the key. Two keys on different stripes mutate both structures at once. Under load this corrupts exactly as if it had no locks, while reading as carefully tuned. The stripes partition the keys; the state was never partitioned.
What the design actually needed is one lock, which is what corpus/lru-cache/reference/src/LruCache.java ships: one monitor over both structures, get included, because a read mutates recency. Its decision log records the broken alternative being built and caught: an unsynchronized get produced expected: <20> but was: <119> under a mixed storm. One lock was not the cautious option there. It was the correct one, and it is a level-3 answer when you can say what the lock protects.
The threshold, from both sides
Split the lock when both halves hold. The state partitions cleanly (per-key counters with no cross-key invariant, like Budget here), and a measured or stated load says callers actually collide. The rate limiter's contract names 200-thread contention as the point; that is a stated load.
Keep one lock when any invariant spans the pieces, or when nobody has named the contention. The bench in contrast/ is the honest scale: the single-lock design served 26 million tryAcquire calls a second under 128 threads. If your round's workload is below that, and it is, the split buys latency percentiles nobody asked about and costs the ordering problem this whole lesson exists to solve.
The quieter costs, named
Fine grain is not one cost but three. Every multi-budget operation now needs the canonical-order machinery — measured in contrast/: 83 lines against 49 to absorb the same requirement. Whole-structure questions get harder. "How many callers are over half their budget" has no consistent answer without taking every lock, in order. That is a new operation the coarse design gets for free. And the failure mode changes species. A coarse-lock bug is slowness a profiler shows you; a lock-order bug is a hang that needs a thread dump at 3 a.m. to even name.
tryLock deserves its own line, because it looks like prudence. Wrapping acquisitions in tryLock-with-timeout when a canonical order was available converts an impossible failure into a retry path you must now design, test and explain. Reach for it when the locks are not all yours to order. Otherwise it is fix 3 doing fix 2's job, at fix 3's price.
The contrast pair
The measured pair: one lock against per-key locks, before and after the cap
Two limiters with the same surface. a/ guards everything with one monitor. b/ gives every budget its own ReentrantLock. Both compile, and both pass BaseTest.java — the comparison is between two working designs, not between good code and code nobody would write.
Then the requirement that earns E3's tag arrives, and the two designs pay for it differently.
The change, in the interviewer's words
Condensed from corpus/rate-limiter/curveballs/02-global-backstop-cap/REQUIREMENT-CHANGE.md:
Per-client limits did what we asked and the database still fell over. Four hundred clients, most on 100 a minute, and nothing anywhere says what happens when three hundred of them are busy at once. Every one of them was inside its own limits the whole way down. So there is now a shared ceiling on top of the per-client ones: a total the whole estate draws on together. A request has to be inside its own client's limits and inside that. If either refuses, neither is charged.
CurveballTest.java asserts those rules, plus the one that makes this an E3 lesson. Its last test runs 128 threads across two callers, so every request needs the cap's lock and a different second lock, and every request must return. It passes against a-backstop/ and b-backstop/.
The absorption cost, measured
Run it yourself:
node lessons/E3/contrast/measure.mjsReal output, from exactly these directories:
shared backstop cap into A (one lock) a -> a-backstop diffLines 49 touched 1 new 0 [Limiter.java +41/-8]
shared backstop cap into B (per-key lock) b -> b-backstop diffLines 83 touched 1 new 0 [Limiter.java +66/-17]
size of a 2 file(s) 67 normalised lines
size of b 2 file(s) 89 normalised linesmeasureChange is the same function that scores D4 in a graded attempt. Both counts include the new methods' javadoc, so read the shape rather than the digits: B pays about 1.7x A's lines for the same requirement.
The line count is the smaller half of the difference. A's 49 lines are a scope loop under the same single lock it already had; the deadlock question does not exist in that design, because at most one lock exists. B's 83 lines include the machinery this whole lesson teaches (a sorted scope, a single acquisition point, reverse release), and every one of those lines is load-bearing. worked/Main.java block 1 is what B looks like when two of them are written by hand in two methods.
The throughput question, measured both ways
Per-key locks exist to buy throughput, so the honest question is how much they buy at this problem's size. Run it yourself (about two minutes):
node lessons/E3/contrast/bench.mjsReal output from this machine — 128 threads, 50,000 tryAcquire calls each, five trials, fresh JVM per trial, min/median/max ops per second:
--- 128 threads, 2 callers, 50000 ops/thread, 5 trials
A one lock min 24.2M median 26.9M max 27.2M ops/s
B per-key locks min 44.9M median 51.4M max 78.0M ops/s
A+cap one lock min 15.7M median 15.8M max 16.1M ops/s
B+cap per-key + order min 9.2M median 9.4M max 9.9M ops/s
--- 128 threads, 8 callers, 50000 ops/thread, 5 trials
A one lock min 24.4M median 26.0M max 26.6M ops/s
B per-key locks min 81.5M median 91.6M max 98.2M ops/s
A+cap one lock min 15.7M median 16.3M max 16.4M ops/s
B+cap per-key + order min 7.2M median 7.3M max 7.8M ops/sOn the base problem the finer grain is real. 1.9x at two hot callers, 3.5x at eight. More callers means fewer collisions per lock, so the gap widens exactly as the theory says.
Then the cap takes it all back, and more. Every request now passes through the cap's lock, so B's parallelism is gone. What remains is B's overhead against A's one monitor: two acquisitions, a scope list and a sort per request. The design that was 3.5x faster is now 2.2x slower. The requirement that created the deadlock hazard also deleted the reason the second lock existed.
And the absolute numbers matter more than the ratios. The slowest row still serves 7 million requests a second. No LLD-round workload is within orders of magnitude of that, which is why "one lock, and here is what it protects" scores as a decision rather than a shortcut.
What this pair does not show
These are ops/s for a counter update inside the lock. A limiter that did real work under its locks would shift every number down and shrink A's disadvantage on the base problem further. The digits also move a few percent between machines and runs (the spread above is from five trials), but the ordering of the rows did not move once. The verdict changes when a critical section is long enough, or hot enough, for the base-problem ratio to matter at your actual request rate. Then B's grain earns its 83 lines, and fix 2's ordering machinery is the price of admission.
The corpus reference paid the machinery cost up front instead: its Scopes interface owned the lock order before any second budget existed, so the same curveball measured reference_diff = 0. corpus/rate-limiter/reference/DECISION_LOG.md calls it "the one genuine up-front bet in this design" and prices it honestly. That is the level-3 version of design B. It is not free either — the bet costs a list where a value would do, and its own javadoc apologising for itself.
Worked source
The 3 files of the worked design
Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.
worked/src/Budget.java85 linesworked/src/Limiter.java171 linesworked/src/Main.java240 lines
worked/src/Budget.java85 lines
import java.util.concurrent.locks.ReentrantLock;
/**
* One caller's allowance: a limit, a used count, and the lock that guards them. The shape is
* {@code corpus/rate-limiter/reference/src/KeyBudget.java}, cut down to what this lesson needs.
*
* <p><b>The lock is per budget, not per limiter.</b> That is the granularity decision. Two callers
* have nothing in common, so they must not queue behind each other — and the price of that choice
* is the whole rest of this lesson, because a request that needs two budgets now holds two locks.
* {@code contrast/} measures what the finer grain actually buys before you pay for it.
*
* <h2>The caller acquires, because only the caller knows the whole set</h2>
* {@link #lock()} and {@link #unlock()} are exposed rather than every method being wrapped in its
* own acquire/release. A single request may have to hold <b>several</b> budgets at once, and
* check-then-charge across them is only atomic if every one is held for the whole of it. A budget
* cannot know what else is in the set, so it cannot order the acquisition. {@link Limiter} can,
* and does, in one method.
*
* <p>The three methods below therefore state a precondition instead of taking the lock
* themselves: <b>the calling thread holds this budget's lock.</b> The precondition is checked, not
* trusted — a missed lock produces lost updates under load and passes every single-threaded test,
* which is the worst combination a bug can have.
*/
final class Budget {
private final String key;
private final long limit;
private long used;
private final ReentrantLock lock = new ReentrantLock();
Budget(String key, long limit) {
if (limit < 0) {
throw new IllegalArgumentException("limit cannot be negative, got " + limit);
}
this.key = key;
this.limit = limit;
}
/** The identity the lock order is derived from. Stable for the life of the budget. */
String key() {
return key;
}
void lock() {
lock.lock();
}
void unlock() {
lock.unlock();
}
/** True when one more unit fits. Charges nothing. Caller holds the lock. */
boolean hasRoom() {
requireLocked();
return used < limit;
}
/** Spend one unit. Only called after {@link #hasRoom()} under the same uninterrupted hold. */
void charge() {
requireLocked();
used++;
}
/** Units left before this budget refuses. Caller holds the lock. */
long remaining() {
requireLocked();
return limit - used;
}
/**
* The precondition of the three methods above, checked rather than trusted.
*
* <p>{@link ReentrantLock#isHeldByCurrentThread()} makes the check one field read. What it
* buys is loud failure at the exact line where a lock was forgotten — an unlocked read is an
* {@link AssertionError} on the first call, not a wrong number three weeks into production.
* An {@code AssertionError} and not {@code IllegalStateException}, because this cannot fire
* in response to anything a caller of {@link Limiter} does. Only a bug in these two files
* reaches it, and the two cases deserve different words.
*/
private void requireLocked() {
if (!lock.isHeldByCurrentThread()) {
throw new AssertionError("this budget must be locked by the calling thread first");
}
}
}worked/src/Limiter.java171 lines
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.function.Supplier;
/**
* A rate limiter with a shared backstop cap: every request must fit inside its caller's own
* budget <b>and</b> inside a cap the whole estate draws on together. The requirement is
* {@code corpus/rate-limiter/curveballs/02-global-backstop-cap}, with the clock and the rule
* vocabulary stripped so only the locking is left.
*
* <p>A request therefore touches <b>two</b> locks, and it has to hold both for the whole of
* check-then-charge — otherwise it can be allowed by a budget that is exhausted by the time it is
* charged. Two locks held at once is where deadlocks come from, so this class is built around one
* rule:
*
* <h2>One method takes the locks, in one order the keys themselves give</h2>
* {@link #locked(List, Supplier)} is the only code here that acquires anything, and it takes the
* scope in the order {@link #scopeOf(String)} produced: <b>sorted by key</b>. Not "own budget
* first" and not "the cap first" — those are conventions, and a convention lives in the heads of
* whoever wrote the current call sites. An order computed from a stable property of the lock
* itself is <i>canonical</i>: any future method that needs the same two budgets derives the same
* order from the same keys, without reading the others. That is the difference between an order
* that is agreed and one that cannot be disagreed with.
*
* <p>{@code worked/Main.java} shows what the alternative costs: two methods, two hand-written
* orders, and a pair of threads that stop forever. Then it runs this class under the same load.
*
* <p>The order is a stated property, so it is queryable: {@link #lockOrder(String)} answers with
* the exact acquisition sequence for a request, which is what {@code faded/GapTest.java} asserts
* on. A lock order you cannot ask about is a lock order a review cannot check.
*/
final class Limiter {
/** Key to budget. Absent means "no budget", which this design treats as unlimited. */
private final ConcurrentMap<String, Budget> budgets = new ConcurrentHashMap<>();
private final String sharedKey;
/** @param sharedKey the cap everybody draws on together, configured like any other key */
Limiter(String sharedKey) {
this.sharedKey = sharedKey;
}
/**
* Set or replace the allowance for {@code key}. A replacement is a whole new {@link Budget} —
* new counter, new lock — published through the concurrent map, so no request ever sees half
* an old budget and half a new one, and no lock is held across the swap.
*/
void configure(String key, long limit) {
budgets.put(key, new Budget(key, limit));
}
/**
* Charge one unit against every budget in the request's scope, or charge nothing at all.
*
* <p>Check everything, then charge everything, under every lock in the scope at once. A loop
* that locked, checked and charged one budget at a time would leak: the caller's own budget
* would be spent by requests the shared cap went on to refuse.
*/
boolean tryAcquire(String caller) {
List<Budget> scope = scopeOf(caller);
if (scope.isEmpty()) {
return true; // no budget anywhere says no
}
return locked(scope, () -> allow(scope));
}
/**
* The tightest figure across <b>the same scope {@link #tryAcquire(String)} would charge</b>.
*
* <p>Same scope, same helper, same lock order. The reference this is cut down from shipped a
* version of this method that read one budget directly, and the base suite passed 28/28 with
* the bug in place — see {@code corpus/rate-limiter/reference/DECISION_LOG.md}. A second
* method that answers questions about the scope is a second chance to invent a second order,
* which is why it goes through {@link #locked(List, Supplier)} like everything else.
*/
long remaining(String caller) {
List<Budget> scope = scopeOf(caller);
if (scope.isEmpty()) {
return Long.MAX_VALUE;
}
return locked(scope, () -> fewestRemaining(scope));
}
/**
* The exact lock acquisition sequence for a request from {@code caller}, as key names.
* Exposed because the order is a design commitment, not an implementation accident.
*/
List<String> lockOrder(String caller) {
List<String> keys = new ArrayList<>();
for (Budget budget : scopeOf(caller)) {
keys.add(budget.key());
}
return keys;
}
/**
* The budgets a request from {@code caller} must satisfy, in lock order.
*
* <p>Two decisions live here. The shared cap joins the scope <b>once</b> — a request made
* under the cap's own key draws on that budget once, not twice. And the scope is sorted by
* key before it is returned, which is the one line that makes the acquisition order a
* property of the data rather than of whoever wrote this method. Today the scope is at most
* two budgets and "own first" would happen to be safe; the day a tenant tier lands between
* caller and cap, "own first" is two different orders and this line is still one.
*/
private List<Budget> scopeOf(String caller) {
List<Budget> scope = new ArrayList<>(2);
addIfConfigured(scope, caller);
if (!caller.equals(sharedKey)) {
addIfConfigured(scope, sharedKey);
}
scope.sort(Comparator.comparing(Budget::key));
return scope;
}
private void addIfConfigured(List<Budget> scope, String key) {
Budget budget = budgets.get(key);
if (budget != null) {
scope.add(budget);
}
}
/** True when every budget has room; charges every budget only then. Locks are held. */
private static boolean allow(List<Budget> scope) {
for (Budget budget : scope) {
if (!budget.hasRoom()) {
return false;
}
}
for (Budget budget : scope) {
budget.charge();
}
return true;
}
/** The smallest remaining count in the scope. Locks are held. */
private static long fewestRemaining(List<Budget> scope) {
long fewest = Long.MAX_VALUE;
for (Budget budget : scope) {
fewest = Math.min(fewest, budget.remaining());
}
return fewest;
}
/**
* Run {@code body} with every budget in {@code scope} locked, acquiring in list order and
* releasing in reverse.
*
* <p><b>The only multi-lock acquisition in this design.</b> One method means one order; one
* order means no cycle. {@code acquired} is counted rather than assumed, so if acquisition
* fails part-way the {@code finally} releases exactly what was taken and nothing else.
*/
private static <T> T locked(List<Budget> scope, Supplier<T> body) {
int acquired = 0;
try {
for (Budget budget : scope) {
budget.lock();
acquired++;
}
return body.get();
} finally {
for (int i = acquired - 1; i >= 0; i--) {
scope.get(i).unlock();
}
}
}
}worked/src/Main.java240 lines
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;
/**
* Four demonstrations, in the order the argument runs.
*
* <p>Block 1 builds a real deadlock and pins it so it happens on every run: two locks, two
* threads, opposite orders. Block 2 removes the pin and races the same shape, reporting how many
* acquisitions each trial survived before it stopped. Block 3 runs {@link Limiter} — one method,
* one order — under 128 threads and gets the exact number the cap promised. Block 4 is the one
* line about reentrancy.
*
* <p>The demo threads take their <b>second</b> lock with {@code lockInterruptibly()}, for one
* reason only: so this program can dismantle its own deadlock and terminate. Production code
* written with {@code lock()} has no interruption to receive, and stays exactly where block 1
* puts it, forever.
*/
public final class Main {
private static final ThreadMXBean THREADS = ManagementFactory.getThreadMXBean();
public static void main(String[] args) throws Exception {
pinnedDeadlock();
racedDeadlocks();
orderedLimiterUnderLoad();
reentrancy();
}
// --- block 1: the deadlock, pinned so it is certain -------------------------------------
/**
* The shape from {@code corpus/rate-limiter/curveballs/02-global-backstop-cap}: a request
* needs its caller's own budget and the shared cap. Here {@code tryAcquire} was written to
* take own-then-cap, and a reporting method to take cap-then-own. A latch holds both threads
* until each has its first lock, so the interleaving that deadlocks is the only one possible.
*/
private static void pinnedDeadlock() throws Exception {
System.out.println("1. two locks, two orders, pinned: the deadlock every run");
ReentrantLock own = new ReentrantLock(); // budget "acme"
ReentrantLock cap = new ReentrantLock(); // the shared backstop cap
CountDownLatch bothHoldTheirFirst = new CountDownLatch(2);
Thread acquire = new Thread(
() -> grabInOrder(own, cap, bothHoldTheirFirst), "tryAcquire(acme)");
Thread report = new Thread(
() -> grabInOrder(cap, own, bothHoldTheirFirst), "remaining(acme)");
acquire.start();
report.start();
long[] deadlocked = awaitDeadlock(5_000);
if (deadlocked == null) {
System.out.println(" no deadlock within 5s -- report this run, it should be impossible");
} else {
for (ThreadInfo info : THREADS.getThreadInfo(deadlocked)) {
System.out.println(" \"" + info.getThreadName() + "\" waits for "
+ shortLockName(info.getLockName())
+ " held by \"" + info.getLockOwnerName() + "\"");
}
}
acquire.interrupt();
report.interrupt();
acquire.join(2_000);
report.join(2_000);
System.out.println(" dismantled by interrupt -- possible only because the demo used"
+ " lockInterruptibly()");
System.out.println();
}
/** First lock unconditionally, then wait for the other thread, then try the second. */
private static void grabInOrder(ReentrantLock first, ReentrantLock second,
CountDownLatch bothHoldTheirFirst) {
first.lock();
try {
bothHoldTheirFirst.countDown();
bothHoldTheirFirst.await();
second.lockInterruptibly();
second.unlock();
} catch (InterruptedException dismantled) {
Thread.currentThread().interrupt();
} finally {
first.unlock();
}
}
// --- block 2: the same shape, unpinned, raced --------------------------------------------
/**
* No latch this time: both threads loop lock-first, lock-second, unlock, as fast as they can,
* in opposite orders. The question each trial answers is not whether it stops but how many
* acquisitions it survives first.
*/
private static void racedDeadlocks() throws Exception {
System.out.println("2. the same two locks, unpinned: acquisitions survived before the hang");
for (int trial = 1; trial <= 5; trial++) {
ReentrantLock own = new ReentrantLock();
ReentrantLock cap = new ReentrantLock();
AtomicLong laps1 = new AtomicLong();
AtomicLong laps2 = new AtomicLong();
Thread t1 = new Thread(() -> race(own, cap, laps1), "own-then-cap");
Thread t2 = new Thread(() -> race(cap, own, laps2), "cap-then-own");
t1.start();
t2.start();
long[] deadlocked = awaitDeadlock(4_000);
String verdict = deadlocked == null
? "no hang in 2,000,000 laps"
: "hung; own-then-cap survived " + laps1.get()
+ " laps, cap-then-own " + laps2.get();
System.out.println(" trial " + trial + ": " + verdict);
t1.interrupt();
t2.interrupt();
t1.join(2_000);
t2.join(2_000);
}
System.out.println();
}
private static void race(ReentrantLock first, ReentrantLock second, AtomicLong laps) {
try {
for (int i = 0; i < 2_000_000 && !Thread.currentThread().isInterrupted(); i++) {
first.lockInterruptibly();
try {
second.lockInterruptibly();
second.unlock();
} finally {
first.unlock();
}
laps.incrementAndGet();
}
} catch (InterruptedException dismantled) {
Thread.currentThread().interrupt();
}
}
// --- block 3: one method, one order, 128 threads ------------------------------------------
/**
* The corrected design under the load that kills the broken one: 64 threads as "acme", 64 as
* "zeta", every request needing its own budget plus the shared cap. The cap is 16, so exactly
* 16 requests are allowed — not roughly 16 — and every thread returns.
*/
private static void orderedLimiterUnderLoad() throws Exception {
System.out.println("3. Limiter: one method takes the locks, in the order the keys give");
Limiter limiter = new Limiter("__cap__");
limiter.configure("__cap__", 16);
limiter.configure("acme", 1_000);
limiter.configure("zeta", 1_000);
System.out.println(" lockOrder(acme) = " + limiter.lockOrder("acme"));
System.out.println(" lockOrder(zeta) = " + limiter.lockOrder("zeta"));
int crowd = 128;
AtomicInteger allowed = new AtomicInteger();
CountDownLatch go = new CountDownLatch(1);
CountDownLatch done = new CountDownLatch(crowd);
ExecutorService pool = Executors.newFixedThreadPool(crowd);
try {
for (int i = 0; i < crowd; i++) {
String caller = i % 2 == 0 ? "acme" : "zeta";
pool.submit(() -> {
try {
go.await();
if (limiter.tryAcquire(caller)) {
allowed.incrementAndGet();
}
} catch (InterruptedException interrupted) {
Thread.currentThread().interrupt();
} finally {
done.countDown();
}
});
}
go.countDown();
boolean finished = done.await(20, TimeUnit.SECONDS);
System.out.println(" 128 threads, cap 16: allowed = " + allowed.get()
+ ", every thread returned = " + finished);
System.out.println(" remaining(acme) = " + limiter.remaining("acme")
+ ", remaining(zeta) = " + limiter.remaining("zeta"));
} finally {
pool.shutdownNow();
}
System.out.println();
}
// --- block 4: reentrancy, the one line -----------------------------------------------------
/**
* Both Java lock kinds count re-entries by the owning thread, so a method that takes a lock
* and calls another method that takes it again does not stop — J12 measured the hold count.
* Note what that does not buy: blocks 1 and 2 used {@link ReentrantLock} throughout, and
* deadlocked anyway. Reentrancy is about one thread and one lock; a cycle is two of each.
*/
private static void reentrancy() {
System.out.println("4. reentrancy is not deadlock immunity");
ReentrantLock lock = new ReentrantLock();
lock.lock();
lock.lock();
System.out.println(" same lock taken twice by one thread: holdCount = "
+ lock.getHoldCount() + ", no hang");
lock.unlock();
lock.unlock();
System.out.println(" blocks 1 and 2 deadlocked with ReentrantLocks -- the cycle is"
+ " between threads, not within one");
}
// --- shared plumbing ------------------------------------------------------------------------
/** Poll the JVM's own detector until it reports a cycle, or give up after {@code millis}. */
private static long[] awaitDeadlock(long millis) throws InterruptedException {
long deadline = System.nanoTime() + millis * 1_000_000L;
while (System.nanoTime() < deadline) {
long[] ids = THREADS.findDeadlockedThreads();
if (ids != null) {
return ids;
}
Thread.sleep(20);
}
return null;
}
/** {@code java.util.concurrent.locks.ReentrantLock$NonfairSync@1b6d} without the package. */
private static String shortLockName(String lockName) {
if (lockName == null) {
return "(unknown lock)";
}
int lastDot = lockName.lastIndexOf('.');
return lastDot < 0 ? lockName : lockName.substring(lastDot + 1);
}
}The faded stage is not here, on purpose
In the app, the third stage of a lesson hands you the worked design with a few lines
replaced by // GAP: markers, then compiles your completion and runs a JUnit suite
against it. That needs javac, and a static site has no compiler — so rather than show a
control that cannot work, this page stops at the worked source.
Run the app for the drill: it is the download in the header, and it works offline once unpacked.