Saltar al contenido

Actualizaciones perdidas en un contador

Fácil#race-condition#step-simulation~15 min

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

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

Restricciones

  • every thread finishes all of its steps

¿Lo que te frena es la idea y no el código? Condiciones de carrera lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio