Saltar al contenido

Reintentos en un bucle compare-and-swap

Fácil#compare-and-swap#step-simulation~15 min

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

Tiempo objetivo
O(s)
Espacio objetivo
O(t)

¿Lo que te frena es la idea y no el código? Compare-and-swap lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio