Concurrency · LLD

Race conditions in object design

A race condition happens when two threads read and write shared state, and the result depends on timing. Example: Gate A looks at the board — spot 101 is free. Gate B looks a moment later — spot 101 is still free. Both print a ticket. Two cars drive into one rectangle of concrete.

A is that story: two actors, one piece of , and a gap between “I looked” and “I wrote.” Name those two steps before you type a Java keyword.

The board after Saturday

Spot 101

Occupied. Last write won. Looks fine.

Ticket T-1

Gate A issued it. Driver A has a slip.

Ticket T-2

Gate B issued it. Driver B has a slip.

The damage

Two tickets. One spot. A lost update.

The real question

What is the shared state, and which two steps can both gates do at the same time?

If you answer “I need synchronized,” you skipped the question. The interviewer is grading whether you can point at occupancy, not whether you remember a monitor.

Walk the interleaving

One history, two tickets

Draw this on the whiteboard. is not a Java topic. It is the only way to prove the bug exists.

T0
Board
Spot 101 is FREE. No ticket yet.
T1
Gate A
isFree(101)? YES. Decision pending. Hand still empty.
T2
Gate B
isFree(101)? YES. Same snapshot. Same decision pending.
T3
Gate A
occupy(101). Issue T-1. Car A rolls in.
T4
Gate B
occupy(101). Issue T-2. Car B has nowhere to stand.

The last write left the board looking honest. The is the extra ticket, not a torn boolean.

Name the shared data before the tool

Spot occupancy is the fact. Not the ticket paper. Not the fee. Not the SMS. If you lock the printer, both gates still read FREE. The is “read free, then write occupied.” That pair is one decision. Split it, and Saturday evening invents a second car for 101.

This is . You will meet it again as “if the seat is open, hold it,” “if the key is missing, put it,” “if the ticket is ACTIVE, mark PAID.” The English is one sentence. The machine is two steps.

Name the fact

Spot 101’s occupancy. Say it out loud. If you cannot, you will protect the wrong object.

Name the two steps

Read free. Write occupied. Draw the gap. Invite the other gate into the gap.

Then pick a tool

CAS, a lock, or one thread that owns all spots. Story first. Java second.

The same race in other LLD problems

Once you can tell the two-gate story, you can smell it in a movie hall, a cache, and a cashier pair. The domain nouns change. The gap does not.

Movie ticket

Two counters both see seat H12 free. Both hold it. Both print. One seat. Two barcodes. Shared state is the seat, not the printer.

In-process cache

Two gets miss. Both load. Both insert. Recency list grows two nodes for one key. Shared state is the map plus the list, not the value bytes.

Ticket pay

Two cashiers read ACTIVE. Both mark PAID. Both open the till. The car left once. Shared state is the status arrow, not the cash drawer.

Inventory pick

Two orders read quantity 1. Both decrement to 0. Two shipments. Shared state is the count, not the packing slip.

The two-step bug, in Java

Reason first: the methods below are honest English. They are not one decision. After you can say that, the code is just the same story typed.

java

class ParkingSpot {
  private boolean occupied = false;

  boolean isFree() { return !occupied; }

  void occupy() { occupied = true; }   // too late — the check already raced
}

// Gate A and Gate B both do this:
if (spot.isFree()) {
  spot.occupy();
  return issueTicket(spot);            // two tickets for 101
}

isFree plus occupy is the diagnosis. A lock around issueTicket does not close the gap. Neither does making occupied volatile — that is a visibility story, not an atomic occupy. Those pages come next; this page stops at naming the race.

Diagnosis is not a keyword

How to explain this in an interview

“Two gates, one spot, check-then-act. I will make occupy one step, or give one thread the board.”

Avoid this

“I’ll put synchronized on ParkingLot.” That may be a later fix. It is not the bug. The bug is the gap.

Three honest fixes exist. An atomic transition on the spot. A lock around pick-and-occupy. Confinement: one allocator thread owns the whiteboard. Pick after you can tell the story. Do not start with ReentrantLock because it sounds grown-up.

Interview flow

Drive the round from the story

1Clarify: two gates may park at once, or is this a single-thread sketch first?
2Name occupancy as shared mutable state. Point at the field, not “the lot.”
3Walk T1–T4. Ask whether two tickets is unacceptable. It always is.
4Offer a mechanism only after the interviewer nods at the race.

Common mistakes

Calling it a missing synchronized

The bug is check-then-act on shared occupancy. A lock is one fix. It is not the diagnosis. Say the two steps first.

Protecting the wrong object

Synchronizing the receipt printer leaves the spot board open. Two gates can still both read FREE. Lock, or CAS, the occupancy decision.

Trusting a main-method demo

One thread never interleaves with itself. park() looking fine in a loop does not mean two gates cannot both take 101.

Where the design still breaks

Fixing occupy on one spot does not fix “pick a free compact among twenty.” Two gates can both choose 101 before either marks it, if pick and occupy are still split across the list. Either lock the pick, or make each tryOccupy fail cleanly so the loser walks to 102. That choice is the optimistic-versus-pessimistic page.

Exercises

Write the T0–T4 interleaving for two cashiers paying the same ACTIVE ticket. What is the lost update?
A HashMap of tickets: if (!map.containsKey(id)) map.put(id, ticket). Name the two steps. What collection operation closes the gap?
You locked issueTicket(). Two cars still share 101. Which object did you fail to name as shared state?