Skip to content
wannacode

Locking

In short: A lock (mutex) lets only one Worker at a time into the critical section; in JavaScript it is built with Atomics on a SharedArrayBuffer.

Problem

How to stop the other till

In the lesson "Race condition" the sale lost sales: two threads did "read, subtract, write" at once and one overwrote the other. The three steps have to be one whole: while one thread is inside, the other has to wait outside.

That is exactly what a lock does.

The idea

The lock

A lock (mutex, from "mutual exclusion") is an object with one owner. A thread takes it, does its work and releases it. Another thread that asks for it in the meantime waits. The code between taking and releasing is the critical section: at most one thread is in it.

JavaScript has no ready-made lock between Workers, so you build one from Atomics on a SharedArrayBuffer. shop[0] is the lock: 0 is free, 1 is taken. Atomics.compareExchange does "if it is 0, set 1" as one indivisible step, so only one Worker takes it. The others sleep in Atomics.wait until unlock wakes them:
// state[0]: 0 is free, 1 is taken.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // sleep while it is taken
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // wake one of the waiting
}


// shop[0] is the lock, shop[1] is the stock.
function sell(shop) {
  lock(shop);
  shop[1]--;
  unlock(shop);
}
The two Workers from the last lesson, 100,000 sales each:
if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 200_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: shop }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Orders: ${2 * 100_000}`);
  console.log("Sold according to the stock:");
  console.log(200_000 - shop[1]);
} else {
  for (let i = 0; i < 100_000; i++) {
    sell(workerData);
  }
}
Output
Orders: 200000
Sold according to the stock:
200000

Exact, on every run. The lock is one number in the shared memory: both tills lock the same one.

See it

The last item, fixed

The check "is there one" and taking it are in one and the same critical section. If someone is inside checking, the other cannot check before the first has taken:

// state[0]: 0 is free, 1 is taken.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // sleep while it is taken
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // wake one of the waiting
}


// shop[0] is the lock, shop[1] is the stock.
function reserve(shop) {
  lock(shop);
  try {
    if (shop[1] === 0) {
      return false;   // none left: refuse
    }
    shop[1]--;        // there is one: take it
    return true;
  } finally {
    unlock(shop);
  }
}
Step by step, in words
  1. 3 items are left, and 4 buyers call reserve() at the same moment.
  2. Only one gets through lock(shop); the other three wait in front of it. Buyer 1 goes in, sees 3 and takes one: 2 left.
  3. Buyer 1 leaves and releases the lock. Buyer 2 goes in, sees 2 and takes one: 1 left.
  4. Buyer 2 leaves and releases the lock. Buyer 3 goes in, sees 1 and takes one: 0 left.
  5. Buyer 4 goes in last and sees 0: refused. No one saw a number that someone else was in the middle of changing.
  6. 3 sold, 1 refused, 0 in stock: correct. The price: the buyers waited for each other at the turnstile.

Four buyers, three items, all at once:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 3;
  const buyers = Array.from({ length: 4 }, () =>
    new Worker(new URL(import.meta.url), { workerData: shop }));
  const results = await Promise.all(
    buyers.map(async (buyer) => (await once(buyer, "message"))[0]),
  );
  console.log(`Sold: ${results.filter((ok) => ok).length}`);
  console.log(`Refused: ${results.filter((ok) => !ok).length}`);
  console.log(`In stock: ${shop[1]}`);
} else {
  parentPort.postMessage(reserve(workerData));
}
Output
Sold: 3
Refused: 1
In stock: 0

And here are the two buyers from the last lesson who were buying the last item. Charging the card (~100 ms) is after the lock: the item is reserved, and the card is charged without the other one waiting:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 1;
  const buyers = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: shop }),
  );
  const bought = await Promise.all(
    buyers.map(async (buyer) => (await once(buyer, "message"))[0]),
  );
  const sold = bought.filter((ok) => ok).length;
  console.log("In stock before: 1");
  console.log(`Sold: ${sold}`);
  console.log(`Refused: ${2 - sold}`);
  console.log(`In stock: ${shop[1]}`);
} else {
  const ok = reserve(workerData);
  if (ok) {
    Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 100);   // charging the card, ~100 ms
  }
  parentPort.postMessage(ok);
}
Output
In stock before: 1
Sold: 1
Refused: 1
In stock: 0

One sold, one refused, 0 in stock. On every run.

Try it

Don't forget to release

You call lock and unlock yourself, so the release is in finally. Otherwise an exception in the critical section leaves the lock taken forever:
// state[0]: 0 is free, 1 is taken.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // sleep while it is taken
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // wake one of the waiting
}


function sell(shop) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
}

What releases the lock?

function sell(shop) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    
  }
}

Try it

The lock that does not lock

A colleague added a lock, but the tills still lose sales. Which line is wrong?

Pick the line with the bug.

The idea

What a lock costs

A lock works by making threads wait for each other. The longer one thread stays inside, the longer the others wait. That is contention for the lock.

A shop with 10 items and four orders at once. Each order takes an item and sends an e-mail (~200 ms), and Network from the lesson "Why threads" counts the rounds of waiting:

// Asks a service over the network: the answer comes after ~200 ms.
function call(net, service, answer) {
  if (Atomics.add(net, 0, 1) === 0) Atomics.add(net, 1, 1);   // nobody is waiting: a new round
  Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 200);
  Atomics.sub(net, 0, 1);
  return `${service}: ${answer}`;
}
// shop[0] is the lock, shop[1] is the stock.


// Bad: the e-mail goes out while the lock is held.
function orderSlow(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
    call(net, "e-mail", customer);
  } finally {
    unlock(shop);
  }
}


// Good: only the stock is under the lock.
function order(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
  call(net, "e-mail", customer);
}
With orderSlow the e-mail is under the lock:
if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  const net = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 10;
  const orders = [1, 2, 3, 4].map((c) => new Worker(new URL(import.meta.url), {
    workerData: { shop, net, customer: `customer ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Orders: 4, in stock: ${shop[1]}`);
  console.log(`Rounds of waiting: ${net[1]}`);
} else {
  orderSlow(workerData.shop, workerData.net, workerData.customer);
}
Output
Orders: 4, in stock: 6
Rounds of waiting: 4

Four rounds: the e-mails go out one by one, and the last customer waits about 800 ms. With order only the stock is under the lock:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  const net = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 10;
  const orders = [1, 2, 3, 4].map((c) => new Worker(new URL(import.meta.url), {
    workerData: { shop, net, customer: `customer ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Orders: 4, in stock: ${shop[1]}`);
  console.log(`Rounds of waiting: ${net[1]}`);
} else {
  order(workerData.shop, workerData.net, workerData.customer);
}
Output
Orders: 4, in stock: 6
Rounds of waiting: 1

The same stock, one round. The rules:

  • Only the shared data under the lock. Compute, format and wait outside. Inside, only read and write.
  • Never wait under a lock: network, disk, database, sleep. Take what you need, release the lock and then wait.
  • One lock for one piece of data. The stock and the revenue are separate: each with its own lock, so that tills touching only one of them do not wait for each other.
More precisely, if you are curious
  • This lock is the simplest one: it is not fair (a Worker that was woken can miss its turn) and not reentrant. In real code you use a ready-made library.
  • Atomics.wait cannot be called on the browser's main thread: it must not sleep. In Node it can.
  • On one thread with async, you need a lock only around await. That is the lesson "async is not a thread".

A lock is not the only way. For one counter there are atomic operations, which do not make threads wait at all, and data that nobody changes needs no lock: the lesson "Atomic operations and immutable objects". And two locks that two threads take in a different order can stop the program forever: the lesson "Deadlock".

Exercise

The revenue and an order of several items

Solve the tasks in your editor.

The revenue. Fix the task from the last lesson: two tills with 500,000 sales each at €3, and revenue[1] += 3 is between lock(revenue) and unlock(revenue), and the lock is revenue[0]. Run the program several times: the revenue has to be the same every time.

Expect
Till 1: 50000 sales
Till 2: 50000 sales
Revenue (€):
300000

An order of several items. There are 5 items in stock. Write reserve(shop, count): if there are at least count, it takes them and returns true, otherwise it takes nothing and returns false. Three customers want 2 items each at once, each in their own Worker.

Expect
Ordered: 3
Accepted: 2
Refused: 1
In stock: 1

More tasks

  • The price of a lock. Run the two tills with 1,000,000 sales each, with and without the lock, and time them. How much slower is it with the lock? And with 8 tills?
  • Two locks. Add revenue to the stock, with its own lock. A sale subtracts from the stock and adds to the revenue. Do the two stay together if someone reads the stock and the revenue between the two locks? - tryLock. Write tryLock(state) that takes the lock with one compareExchange if it is free, and returns false without sleeping if it is taken.

Test

Test yourself

1. Two Workers call sell(shop), which does shop[1]-- between lock(shop) and unlock(shop). What does the second do when the lock is taken?
2. The check "are there items" is under the lock, and the subtraction is in a separate block under the same lock. Two people buy the last item. What happens?
3. Under the lock are the stock subtraction and sending an e-mail (~200 ms). Four orders come at once. How long does the last one wait?
4. What happens if shop[1]-- throws an exception between lock(shop) and unlock(shop) without try/finally?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·