Pular para o conteúdo

Atualizações perdidas no contador

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

A missão

Problema

Várias threads compartilham um contador, e cada thread executa count += 1 algumas vezes. Cada incremento são, na verdade, três passos: ler o contador para o registrador da própria thread, somar um ao registrador e gravar o registrador de volta. Você recebe o número de threads e o escalonamento escolhido pelo sistema operacional, como uma lista de números de thread: cada entrada deixa aquela thread executar o seu próximo passo. Toda thread conclui todos os seus passos. Retorne o valor final do contador, começando de 0.

Exemplos

Input:  threads = 2, schedule = [0, 0, 0, 1, 1, 1]
Output: 2
Por quê: a thread 0 termina o incremento antes de a thread 1 ler, então nada se perde
Input:  threads = 2, schedule = [0, 1, 0, 1, 0, 1]
Output: 1
Por quê: as duas threads leem 0, as duas gravam 1 de volta e um incremento desaparece
Input:  threads = 1, schedule = [0, 0, 0, 0, 0, 0]
Output: 2
Por quê: edge case: uma única thread nunca entra em corrida consigo mesma

Dicas

0 / 3

Tempo-alvo
O(s)
Espaço-alvo
O(t)

Restrições

  • every thread finishes all of its steps

Travou na ideia, e não no código? Condições de corrida explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado