# Concurrency Basics

Course: [Low-Level Design](https://www.devtutorials.ai/learn/system-design/lld) · Section: LLD Foundations
Source: https://www.devtutorials.ai/learn/system-design/lld/foundations/concurrency-basics

> See race conditions happen, find them with a scheduler that tries every order, and fix them with locks, one-step updates and queues.

Picture the last plate of biryani at a busy counter. Two customers ask for it at the same time. Both cashiers look at the tray, see that one plate is available, and both say "yes". Then they walk to the tray. One customer ends up leaving disappointed because the plate was already taken.

This is called a **race condition**. It happens when multiple pieces of work share the same data and can pause before finishing their task.

**In simple words:** concurrency means multiple tasks can happen at the same time. Problems occur when something changes between checking a value and updating it.

## What You Will Learn

In this lesson, you will learn:

1. What a race condition is and why it can be difficult to reproduce.
2. How a scheduler that tries **every possible execution order** can reliably find race conditions.
3. Two common solutions: a **lock** and a **check-and-update operation performed as a single step**.
4. What a **deadlock** is and a simple rule to avoid it.
5. How using a **queue** can prevent race conditions by processing one task at a time.

In TypeScript, every `await` is a pause where other work can run. To make this easy to test, the examples use **generator functions**: each `yield` is a pause, like waiting for a database, and a small scheduler picks which task runs next.

## A Race, Step by Step

Each customer performs three steps: read the stock, wait for the database, and then check and update the stock. The `yield` represents the waiting period.

### The Bad Order

In this example, Asha reads the stock first, and Ravi reads it before either of them updates it. Step through the bad order:

Here is the same idea in code:

```ts runnable title="A race: both customers get the last biryani"
type Step = Generator<unknown, void, unknown>;

// Run tasks one step at a time, in the order given (0 = first task, 1 = second).
function runInOrder(tasks: Step[], order: number[]): void {
  for (const i of order) tasks[i].next();
  for (const t of tasks) while (!t.next().done) {} // finish anything left
}

let stock = 1;
const sold: string[] = [];

function* buy(name: string): Step {
  const count = stock; // 1. read
  yield;               // 2. wait for the database
  if (count > 0) {     // 3. check and write
    stock = count - 1;
    sold.push(name);
  }
}

// Asha reads, Ravi reads, Asha writes, Ravi writes:
runInOrder([buy("Asha"), buy("Ravi")], [0, 1, 0, 1]);
console.log("sold to:", sold.join(" and "));
console.log("stock:", stock);
```

Expected output:

```text
sold to: Asha and Ravi
stock: 0
```

```ts runnable title="The same code, a different order: no bug"
type Step = Generator<unknown, void, unknown>;

// Run tasks one step at a time, in the order given (0 = first task, 1 = second).
function runInOrder(tasks: Step[], order: number[]): void {
  for (const i of order) tasks[i].next();
  for (const t of tasks) while (!t.next().done) {} // finish anything left
}

let stock = 1;
const sold: string[] = [];

function* buy(name: string): Step {
  const count = stock;
  yield;
  if (count > 0) {
    stock = count - 1;
    sold.push(name);
  }
}

// Asha finishes completely before Ravi starts:
runInOrder([buy("Asha"), buy("Ravi")], [0, 0, 1, 1]);
console.log("sold to:", sold.join(" and "));
console.log("stock:", stock);
```

Expected output:

```text
sold to: Asha
stock: 0
```

Both customers read that there was "1 item left". Both then updated the stock to "0 left". The result is `sold to: Asha and Ravi` and `stock: 0`. Two biryanis were sold even though only one was available.

### The Same Code, Another Order

The last step of the animation shows the other order: Asha reads, waits and writes before Ravi starts. Ravi then reads 0 and buys nothing. The result is `sold to: Asha` and `stock: 0`. Because the steps did not overlap, the result was correct.

### Why Races Are Hard to Find

The code is exactly the same in both cases. The only difference is the **order of execution**. On your computer, the safe order may happen thousands of times without any issue. On a busy production system, the unsafe order may eventually occur.

## Try Every Order

Waiting for a race condition to appear by chance is not a reliable way to find bugs. Instead, a **scheduler** can test **every possible order** in which the steps can run. If even one of those orders breaks the expected rule, the race condition has been found.

### The Example

The scheduler runs Asha's and Ravi's steps in every possible order and checks, after each run, that the biryani was sold only once. Step through the six orders:

Here is the same idea in code:

```ts runnable title="Try every order to find the bad ones"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

// Try every possible order of steps. Calls check() after each run.
function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      if (ready.length === 0) throw new Error("stuck: deadlock in order " + order.join(","));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

let stock = 1;
let sold: string[] = [];

function* buy(name: string): Step {
  const count = stock;
  yield;
  if (count > 0) { stock = count - 1; sold.push(name); }
}

const result = everyOrder(
  () => { stock = 1; sold = []; return [buy("Asha"), buy("Ravi")]; },
  () => sold.length === 1,
);
console.log(`${result.bad} of ${result.runs} orders sold the biryani twice`);
```

Expected output:

```text
4 of 6 orders sold the biryani twice
```

The result: **4 of 6 orders sold the biryani twice**. Some execution orders worked correctly, while others did not. Just one bad execution order is enough to sell the same biryani twice.

**Easy way to remember:** a race condition happens in the gap between **checking** and **updating**. You can fix it by either removing the gap (performing both actions together) or by using a **lock** so that only one task can enter that section at a time.

## Fix 1: A Lock

A **lock** (also called a **mutex**) allows only one task to enter a critical section of code at a time. Any other task that reaches the same section must wait until the lock is released.

### The Example

Here, Asha, Ravi and Meena all try to buy the last biryani. Each one takes the lock before reading the stock and gives it back in a `finally` block. Step through it:

Here is the same idea in code:

```ts runnable title="Fix 1: a lock around read, check and write"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

// Try every possible order of steps. Calls check() after each run.
function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      if (ready.length === 0) throw new Error("stuck: deadlock in order " + order.join(","));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

let stock = 1;
let sold: string[] = [];
const lock = new Mutex();

function* buy(name: string): Step {
  yield* lock.acquire();      // wait here if someone else is inside
  try {
    const count = stock;
    yield;                    // still waiting for the database...
    if (count > 0) { stock = count - 1; sold.push(name); }
  } finally {
    lock.release();           // always give the lock back
  }
}

const result = everyOrder(
  () => { stock = 1; sold = []; lock.held = false; return [buy("Asha"), buy("Ravi"), buy("Meena")]; },
  () => sold.length === 1 && stock === 0,
);
console.log(`${result.bad} of ${result.runs} orders went wrong`);
```

Expected output:

```text
0 of 42 orders went wrong
```

The scheduler tested all possible orders: **0 of 42 orders went wrong**. The `finally` block ensures that the lock is always released, even if an error occurs inside the protected code.

## Fix 2: Check and Change in One Step

In some situations, you do not need a lock. If the check and the update happen together as a single operation, there is no opportunity for a race condition to occur.

Databases provide operations like this. For example, `UPDATE dishes SET stock = stock - 1 WHERE stock > 0` performs the check and the update in a single step. Step through two customers sending this command:

Here is the same idea in code:

```ts runnable title="Fix 2: check and change in one step"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

// Try every possible order of steps. Calls check() after each run.
function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      if (ready.length === 0) throw new Error("stuck: deadlock in order " + order.join(","));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

let stock = 1;
let sold: string[] = [];

// Like a database "UPDATE ... SET stock = stock - 1 WHERE stock > 0":
// the check and the change happen together, with no pause in between.
function* buy(name: string): Step {
  yield; // the trip to the database
  if (stock > 0) { stock -= 1; sold.push(name); }
}

const result = everyOrder(
  () => { stock = 1; sold = []; return [buy("Asha"), buy("Ravi"), buy("Meena")]; },
  () => sold.length === 1 && stock === 0,
);
console.log(`${result.bad} of ${result.runs} orders went wrong`);
```

Expected output:

```text
0 of 90 orders went wrong
```

The scheduler tried every order of three customers: **0 of 90 orders went wrong**. No lock is needed because nothing can run between `if (stock > 0)` and `stock -= 1`. The check and the update happen together as one operation.

## Deadlock: Waiting Forever

Locks can solve race conditions, but they can also introduce a new problem. Imagine transfer 1 locks wallet A and then tries to lock wallet B. At the same time, transfer 2 locks wallet B and then tries to lock wallet A. Each transfer is waiting for the other to release a lock, so neither can continue. This situation is called a **deadlock**.

Step through the two transfers. The scheduler stops with the message `stuck: deadlock in order 0,1,0,1`:

Here is the same idea in code:

```ts runnable title="A deadlock: two locks taken in opposite order"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

// Try every possible order of steps. Calls check() after each run.
function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      if (ready.length === 0) throw new Error("stuck: deadlock in order " + order.join(","));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

const walletA = new Mutex();
const walletB = new Mutex();

function* transfer(first: Mutex, second: Mutex): Step {
  yield* first.acquire();
  yield; // a pause between the two locks
  yield* second.acquire();
  second.release();
  first.release();
}

try {
  everyOrder(() => {
    walletA.held = false;
    walletB.held = false;
    return [transfer(walletA, walletB), transfer(walletB, walletA)];
  }, () => true);
  console.log("no deadlock");
} catch (e) {
  console.log((e as Error).message);
}
```

Expected output:

```text
stuck: deadlock in order 0,1,0,1
```

### The Rule That Prevents It

Always acquire locks in the **same order** throughout the application, such as by using an id. If every transfer locks the smaller id first, two transfers can never end up holding one lock each while waiting for the other.

Keep a lock for the shortest time possible. Also, avoid calling slow external services, such as payment gateways or SMS providers, while holding a lock. Other requests must wait until the lock is released.

## Queues: One at a Time

Another way to prevent race conditions is to avoid shared access altogether. Place tasks into a **queue** and let a single worker process them one at a time, in order. A restaurant kitchen's ticket rail works in the same way.

Watch three receipt jobs go through one worker:

Here is the same idea in code:

```ts runnable title="A queue: one worker handles jobs one at a time"
class JobQueue {
  private readonly jobs: string[] = [];
  private busy = false;
  readonly log: string[] = [];

  add(job: string): void {
    this.jobs.push(job);
    this.work();
  }

  private work(): void {
    if (this.busy) return; // someone is already working through the queue
    this.busy = true;
    while (this.jobs.length > 0) {
      const job = this.jobs.shift()!; // first in, first out
      this.log.push(`done: ${job}`);
    }
    this.busy = false;
  }
}

const q = new JobQueue();
q.add("send receipt 881");
q.add("send receipt 882");
q.add("send receipt 883");
for (const line of q.log) console.log(line);
```

Expected output:

```text
done: send receipt 881
done: send receipt 882
done: send receipt 883
```

The jobs finish in the order they were added: receipt 881, then 882, then 883. Because only one worker processes jobs from the queue, two receipts cannot be sent at the same time by mistake.

## Lab: The Last Biryani

QuickBite's `Kitchen.buy()` method contains the same race condition shown earlier. The hidden tests use a scheduler to try **every possible execution order** for two, three, and four customers.

Keep the `Kitchen` class, its constructor, the `left` getter, and the `*buy(name, sold)` method. Also keep the `yield`, which represents waiting for the database.

1. Add a `Mutex` to the kitchen.
2. Acquire the lock before reading the stock, and always release it inside a `finally` block.
3. Run the tests. If a test fails, the error message will show the exact execution order that caused the problem.

## Predict the Output

Here is a C# example about locks. Read the code and try to predict the output before running it.

<CsPredict id="lock-1" code={"int stock = 1;\nvar gate = new object();\nvar sold = new List<string>();\n\nvoid Buy(string name)\n{\n    lock (gate)\n    {\n        if (stock > 0) { stock--; sold.Add(name); }\n    }\n}\n\nBuy(\"Asha\");\nBuy(\"Ravi\");\nConsole.WriteLine(string.Join(\",\", sold));\nConsole.WriteLine(stock);"} expected={"Asha\n0"} why="Asha buys first and gets the only biryani, so the stock becomes 0. When Ravi tries to buy, the stock is already 0, so the condition is false. The lock keeps the check and the update together as one safe operation." />

## Common Mistakes

| Mistake | Wrong | Correct | Why it happens |
|---|---|---|---|
| Gap between checking and updating | `const n = stock; await db(); stock = n - 1;` | Perform the check and update together, or protect both with a lock. | The code looks simple and easy to read from top to bottom. |
| Acquiring the lock too late | Read the stock first, then acquire the lock. | Acquire the lock before reading the stock. | It may seem that only the update operation needs protection. |
| Not releasing a lock | An error prevents `release()` from running. | Always release the lock in a `finally` block. | The normal execution path always reaches the release statement. |
| Using different lock orders | Lock A then B in one place, but B then A somewhere else. | Always acquire locks in the same order, such as by id. | Different parts of the code were written independently. |
| Trusting a single test run | "It worked when I tested it." | Use a scheduler to test all possible execution orders. | Race conditions depend on timing and may appear random. |

## Practice

## What to Remember

- A **race condition** happens in the gap between reading a value and updating it.
- Race conditions depend on the **order of execution**, so test **all possible orders**, not just one run.
- Fix race conditions with a **lock** or by performing the **check and update as a single operation**.
- Acquire multiple locks in a **consistent order** to prevent **deadlocks**.
- A **queue** with a single worker avoids shared access and prevents many concurrency problems.

## Further Reading

These are the sources used to check this lesson:

- [MDN: Using promises and async functions](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Using_promises): where JavaScript code can pause.
- [MDN: Generator functions](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*): the `yield` used in the examples.
- [Microsoft Learn: The lock statement](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/lock): locks in C#.
- [PostgreSQL: Concurrency control](https://www.postgresql.org/docs/current/mvcc-intro.html): how databases keep updates safe.

This completes LLD Foundations. Next: **LLD Case Studies**, starting with a parking lot.