Reintentos en un bucle compare-and-swap
La misión
Problema
Varios hilos (threads) suman su propia cantidad a un único valor compartido sin un lock (bloqueo). Cada hilo repite dos pasos: leer el valor compartido en un snapshot privado y luego hacer un compare-and-swap (CAS). El CAS tiene éxito solo si el valor compartido sigue siendo igual al snapshot; en ese caso escribe snapshot + cantidad y el hilo termina. Si no, el CAS falla, no se escribe nada y el hilo vuelve a empezar con una lectura nueva. Recibes el valor inicial, la cantidad de cada hilo y la planificación como una lista de números de hilo, donde cada entrada le permite a ese hilo dar su siguiente paso. Las entradas de un hilo que ya terminó se ignoran. Devuelve el valor final y cuántos CAS perdió cada hilo.
Ejemplos
Input: start = 0, amounts = [5, 7], schedule = [0, 1, 0, 1, 1, 1]
Output: (12, [0, 1])
Por qué: el CAS del hilo 1 falla porque el hilo 0 cambió el valor después de que el hilo 1 lo leyera, así que vuelve a leer y lo intenta de nuevo
Input: start = 0, amounts = [1, 1, 1], schedule = [0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 2, 2]
Output: (3, [0, 1, 2])
Por qué: los tres leen 0, solo un CAS por ronda puede ganar y el hilo 2 pierde dos veces
Input: start = 10, amounts = [3], schedule = [0, 0]
Output: (13, [0])
Por qué: caso límite: sin otro escritor, el primer CAS siempre tiene éxito
Pistas
0 / 3
A diferencia de una lectura y una escritura simples, un CAS fallido no sobrescribe nada. El costo de la contención pasa de las actualizaciones perdidas a los reintentos.
Cada hilo necesita un snapshot, o una marca de que su siguiente paso es una lectura, y un indicador de si ya terminó.
Recorre la planificación. Salta los hilos terminados. En una lectura, guarda el valor compartido como snapshot. En un CAS, compara el valor compartido con el snapshot: si son iguales, escribe snapshot + cantidad y termina; si no, cuenta un fallo y borra el snapshot para que el siguiente paso sea una lectura.
- Tiempo objetivo
- O(s)
- Espacio objetivo
- O(t)
Solución
Un bucle de compare-and-swap reemplaza un lock por una verificación optimista: la escritura solo ocurre si nadie cambió el valor desde que este hilo lo leyó. La simulación guarda lo que esa verificación necesita, un snapshot (instantánea) por hilo y si ya terminó, y un snapshot None significa que el siguiente paso del hilo es una lectura. Un CAS fallido no escribe nada y manda al hilo a leer de nuevo, así que cada cantidad se suma exactamente una vez y el valor final siempre es el inicial más la suma; esa es la diferencia con la carrera de las actualizaciones perdidas. Lo que cuesta la contención, en cambio, son los reintentos, y el segundo ejemplo muestra cómo se acumulan en el hilo que sigue perdiendo. El tiempo es O(s) para una planificación de s pasos y el espacio es O(t) para t hilos.
def cas_add(start, amounts, schedule):
value = start # the shared value
snap = [None] * len(amounts) # None means the next step is a read
done = [False] * len(amounts)
failed = [0] * len(amounts)
for t in schedule:
if done[t]:
continue # finished threads take no more steps
if snap[t] is None:
snap[t] = value # read into a private snapshot
elif value == snap[t]:
value = snap[t] + amounts[t] # the swap wins: nobody wrote in between
done[t] = True
else:
failed[t] += 1 # someone got there first: retry from a read
snap[t] = None
return value, failed
print(cas_add(0, [5, 7], [0, 1, 0, 1, 1, 1])) # -> (12, [0, 1])
print(cas_add(0, [1, 1, 1], [0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 2, 2])) # -> (3, [0, 1, 2])
print(cas_add(10, [3], [0, 0])) # -> (13, [0])¿Lo que te frena es la idea y no el código? Compare-and-swap lo explica.