Actualizaciones perdidas en un contador
La misión
Problema
Varios hilos (threads) comparten un contador, y cada hilo ejecuta count += 1 unas cuantas veces. Cada incremento son en realidad tres pasos: leer el contador en el registro propio del hilo, sumarle uno al registro y escribir el registro de vuelta. Recibes el número de hilos y la planificación que eligió el sistema operativo, como una lista de números de hilo: cada entrada le permite a ese hilo dar su siguiente paso. Todos los hilos terminan todos sus pasos. Devuelve el valor final del contador, que empieza en 0.
Ejemplos
Input: threads = 2, schedule = [0, 0, 0, 1, 1, 1]
Output: 2
Por qué: el hilo 0 termina su incremento antes de que el hilo 1 lea, así que no se pierde nada
Input: threads = 2, schedule = [0, 1, 0, 1, 0, 1]
Output: 1
Por qué: ambos hilos leen 0, ambos escriben 1 y un incremento desaparece
Input: threads = 1, schedule = [0, 0, 0, 0, 0, 0]
Output: 2
Por qué: caso límite: un único hilo nunca puede entrar en carrera consigo mismo
Pistas
0 / 3
El contador compartido no es el único estado. Cada hilo también tiene una copia privada que leyó antes, y esa copia puede quedar desactualizada.
Lleva, para cada hilo, su registro y cuál de los tres pasos le toca después. El paso rota entre leer, sumar, escribir, leer, y así sucesivamente.
Recorre la planificación. En una lectura, copia el contador en el registro del hilo; en una suma, súmale uno al registro; en una escritura, sobrescribe el contador con el registro. Luego pasa ese hilo a su siguiente paso.
- Tiempo objetivo
- O(s)
- Espacio objetivo
- O(t)
Restricciones
- every thread finishes all of its steps
Solución
El bug de una carrera de datos vive en el hueco entre una lectura y su escritura correspondiente, así que la simulación guarda exactamente el estado que ese hueco necesita: un registro por hilo y qué paso le toca a cada hilo. Una lectura copia el valor compartido, una suma cambia solo la copia privada y una escritura guarda la copia privada encima de lo que tenga el contador en ese momento, lo que descarta en silencio cualquier incremento que haya caído en medio. Por eso, reproducir la planificación paso a paso recrea la actualización perdida tal como lo haría el hardware. El tiempo es O(s) para una planificación de s pasos y el espacio es O(t) para t hilos.
def final_count(threads, schedule):
count = 0 # the shared counter
reg = [0] * threads # each thread's private register
step = [0] * threads # 0 = read, 1 = add, 2 = write
for t in schedule:
if step[t] == 0:
reg[t] = count # read the shared value
elif step[t] == 1:
reg[t] += 1 # add one to the private copy
else:
count = reg[t] # write back, possibly over a newer value
step[t] = (step[t] + 1) % 3
return count
print(final_count(2, [0, 0, 0, 1, 1, 1])) # -> 2
print(final_count(2, [0, 1, 0, 1, 0, 1])) # -> 1
print(final_count(1, [0, 0, 0, 0, 0, 0])) # -> 2
print(final_count(2, [0, 1, 1, 1, 0, 0, 0, 0, 0])) # -> 2¿Lo que te frena es la idea y no el código? Condiciones de carrera lo explica.