Ir al contenido
wannacode

Bloqueo

En resumen: Un cerrojo (mutex) deja entrar a la sección crítica a un solo Worker cada vez; en JavaScript se construye con Atomics sobre un SharedArrayBuffer.

Problema

Cómo detener a la otra caja

En la lección «Condición de carrera» la venta perdía ventas: dos hilos hacían a la vez «leer, restar, escribir» y uno pisaba al otro. Los tres pasos tienen que ser un todo: mientras un hilo está dentro, el otro tiene que esperar fuera.

Eso es exactamente lo que hace un cerrojo.

La idea

El cerrojo

Un cerrojo (mutex, de «mutual exclusion») es un objeto con un dueño. Un hilo lo toma, hace su trabajo y lo suelta. Otro hilo que lo pida mientras tanto espera. El código entre tomarlo y soltarlo es la sección crítica: como máximo un hilo está dentro.

JavaScript no tiene un cerrojo ya hecho entre Workers, así que lo construyes con Atomics sobre un SharedArrayBuffer. shop[0] es el cerrojo: 0 es libre, 1 es tomado. Atomics.compareExchange hace «si es 0, pon 1» en un paso indivisible, así que solo un Worker lo toma. Los demás duermen en Atomics.wait hasta que unlock los despierta:
// state[0]: 0 es libre, 1 es ocupado.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // duerme mientras esté ocupado
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // despierta a uno de los que esperan
}


// shop[0] es el cerrojo, shop[1] son las existencias.
function sell(shop) {
  lock(shop);
  shop[1]--;
  unlock(shop);
}
Los dos Workers de la lección anterior, 100 000 ventas cada uno:
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(`Pedidos: ${2 * 100_000}`);
  console.log("Vendidos según el almacén:");
  console.log(200_000 - shop[1]);
} else {
  for (let i = 0; i < 100_000; i++) {
    sell(workerData);
  }
}
Salida
Pedidos: 200000
Vendidos según el almacén:
200000

Exacto, en cada ejecución. El cerrojo es un número en la memoria compartida: las dos cajas bloquean el mismo.

Míralo

El último artículo, arreglado

La comprobación «queda uno» y tomarlo están en la misma sección crítica. Si alguien está dentro comprobando, el otro no puede comprobar antes de que el primero haya tomado:

// state[0]: 0 es libre, 1 es ocupado.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // duerme mientras esté ocupado
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // despierta a uno de los que esperan
}


// shop[0] es el cerrojo, shop[1] son las existencias.
function reserve(shop) {
  lock(shop);
  try {
    if (shop[1] === 0) {
      return false;   // no queda ninguno: rechazar
    }
    shop[1]--;        // queda uno: tomarlo
    return true;
  } finally {
    unlock(shop);
  }
}
Paso a paso, en palabras
  1. Quedan 3 artículos, y 4 compradores llaman a reserve() en el mismo momento.
  2. Por lock(shop) pasa solo uno, los otros tres esperan delante. Entra el comprador 1, ve 3 y toma uno: quedan 2.
  3. El comprador 1 sale y suelta el cerrojo. Entra el comprador 2, ve 2 y toma uno: quedan 1.
  4. El comprador 2 sale y suelta el cerrojo. Entra el comprador 3, ve 1 y toma uno: quedan 0.
  5. El comprador 4 entra el último y ve 0: rechazado. Nadie vio un número que otro estaba cambiando justo en ese momento.
  6. 3 vendidos, 1 rechazado, 0 en existencias: correcto. El precio: los compradores se esperaron unos a otros en el torniquete.

Cuatro compradores, tres artículos, todos a la vez:

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(`Vendidos: ${results.filter((ok) => ok).length}`);
  console.log(`Rechazados: ${results.filter((ok) => !ok).length}`);
  console.log(`Existencias: ${shop[1]}`);
} else {
  parentPort.postMessage(reserve(workerData));
}
Salida
Vendidos: 3
Rechazados: 1
Existencias: 0

Y aquí están los dos compradores de la lección anterior que compraban el último artículo. El cobro de la tarjeta (~100 ms) va después del cerrojo: el artículo queda reservado, y la tarjeta se cobra sin que el otro espere:

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("Existencias antes: 1");
  console.log(`Vendidos: ${sold}`);
  console.log(`Rechazados: ${2 - sold}`);
  console.log(`Existencias: ${shop[1]}`);
} else {
  const ok = reserve(workerData);
  if (ok) {
    Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 100);   // se cobra la tarjeta, ~100 ms
  }
  parentPort.postMessage(ok);
}
Salida
Existencias antes: 1
Vendidos: 1
Rechazados: 1
Existencias: 0

Uno vendido, uno rechazado, 0 en existencias. En cada ejecución.

Pruébalo

No olvides soltarlo

Llamas tú mismo a lock y unlock, así que la liberación va en finally. Si no, una excepción en la sección crítica deja el cerrojo tomado para siempre:
// state[0]: 0 es libre, 1 es ocupado.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // duerme mientras esté ocupado
  }
}


function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // despierta a uno de los que esperan
}


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

¿Qué suelta el cerrojo?

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

Pruébalo

El cerrojo que no bloquea

Un compañero añadió un cerrojo, pero las cajas siguen perdiendo ventas. ¿Qué línea está mal?

Elige la línea con el error.

La idea

Lo que cuesta un cerrojo

Un cerrojo funciona haciendo que los hilos se esperen unos a otros. Cuanto más tiempo se queda un hilo dentro, más esperan los demás. Eso es la contención por el cerrojo.

Una tienda con 10 artículos y cuatro pedidos a la vez. Cada pedido toma un artículo y envía un correo (~200 ms), y Network de la lección «Por qué hilos» cuenta las rondas de espera:

// Consulta un servicio por la red: la respuesta llega después de ~200 ms.
function call(net, service, answer) {
  if (Atomics.add(net, 0, 1) === 0) Atomics.add(net, 1, 1);   // nadie espera: una ronda nueva
  Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 200);
  Atomics.sub(net, 0, 1);
  return `${service}: ${answer}`;
}
// shop[0] es el cerrojo, shop[1] son las existencias.


// Mal: el correo sale mientras el cerrojo está tomado.
function orderSlow(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
    call(net, "correo", customer);
  } finally {
    unlock(shop);
  }
}


// Bien: bajo el cerrojo solo están las existencias.
function order(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
  call(net, "correo", customer);
}
Con orderSlow el correo está bajo el cerrojo:
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: `cliente ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Pedidos: 4, existencias: ${shop[1]}`);
  console.log(`Rondas de espera: ${net[1]}`);
} else {
  orderSlow(workerData.shop, workerData.net, workerData.customer);
}
Salida
Pedidos: 4, existencias: 6
Rondas de espera: 4

Cuatro rondas: los correos salen uno a uno, y el último cliente espera unos 800 ms. Con order solo las existencias están bajo el cerrojo:

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: `cliente ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Pedidos: 4, existencias: ${shop[1]}`);
  console.log(`Rondas de espera: ${net[1]}`);
} else {
  order(workerData.shop, workerData.net, workerData.customer);
}
Salida
Pedidos: 4, existencias: 6
Rondas de espera: 1

Las mismas existencias, una ronda. Las reglas:

  • Solo los datos compartidos bajo el cerrojo. Calcula, da formato y espera fuera. Dentro, solo leer y escribir.
  • Nunca esperes bajo un cerrojo: red, disco, base de datos, sleep. Toma lo que necesitas, suelta el cerrojo y luego espera.
  • Un cerrojo por cada dato. Las existencias y los ingresos son cosas separadas: cada uno con su cerrojo, para que las cajas que tocan solo uno de ellos no se esperen entre sí.
Más precisamente, para curiosos
  • Este cerrojo es el más sencillo: no es justo (un Worker despertado puede perder su turno) ni reentrante. En código real se usa una biblioteca ya hecha.
  • Atomics.wait no se puede llamar en el hilo principal del navegador: no debe dormir. En Node sí.
  • Con un solo hilo y async, solo necesitas un cerrojo alrededor de un await. Esa es la lección «async no es un hilo».

Un cerrojo no es el único camino. Para un contador hay operaciones atómicas, que no hacen esperar a los hilos, y los datos que nadie cambia no necesitan cerrojo: la lección «Operaciones atómicas y objetos inmutables». Y dos cerrojos que dos hilos toman en distinto orden pueden detener el programa para siempre: la lección «Deadlock».

Ejercicio

Los ingresos y un pedido de varios artículos

Resuelve las tareas en tu editor.

Los ingresos. Arregla la tarea de la lección anterior: dos cajas con 500 000 ventas cada una a 3 €, y revenue[1] += 3 está entre lock(revenue) y unlock(revenue), y el cerrojo es revenue[0]. Ejecuta el programa varias veces: los ingresos tienen que ser los mismos cada vez.

Se espera
Caja 1: 50000 ventas
Caja 2: 50000 ventas
Ingresos (€):
300000

Un pedido de varios artículos. Hay 5 artículos en existencias. Escribe reserve(shop, count): si quedan al menos count, los toma y devuelve true; si no, no toma nada y devuelve false. Tres clientes quieren 2 artículos cada uno a la vez, cada uno en su propio Worker.

Se espera
Pedidos: 3
Aceptados: 2
Rechazados: 1
Existencias: 1

Más tareas

  • El precio de un cerrojo. Ejecuta las dos cajas con 1 000 000 de ventas cada una, con y sin cerrojo, y mide el tiempo. ¿Cuánto más lento es con el cerrojo? ¿Y con 8 cajas?
  • Dos cerrojos. Añade a las existencias unos ingresos con su propio cerrojo. Una venta resta de las existencias y suma a los ingresos. ¿Siguen juntos los dos si alguien lee las existencias y los ingresos entre los dos cerrojos? - tryLock. Escribe tryLock(state), que toma el cerrojo con un compareExchange si está libre y devuelve false sin dormir si está tomado.

Test

Ponte a prueba

1. Dos Workers llaman a sell(shop), que hace shop[1]-- entre lock(shop) y unlock(shop). ¿Qué hace el segundo cuando el cerrojo está tomado?
2. La comprobación «hay artículos» está bajo el cerrojo, y la resta está en un bloque aparte bajo el mismo cerrojo. Dos personas compran el último artículo. ¿Qué pasa?
3. Bajo el cerrojo están la resta de las existencias y el envío de un correo (~200 ms). Llegan cuatro pedidos a la vez. ¿Cuánto espera el último?
4. ¿Qué pasa si shop[1]-- lanza una excepción entre lock(shop) y unlock(shop) sin try/finally?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·