Atualizações perdidas no contador
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
O contador compartilhado não é o único estado. Cada thread também tem uma cópia privada que leu antes, e essa cópia pode ficar desatualizada.
Acompanhe, para cada thread, o registrador dela e qual dos três passos ela executa em seguida. O passo segue um ciclo: ler, somar, gravar, ler e assim por diante.
Percorra o escalonamento. Em uma leitura, copie o contador para o registrador da thread; em uma soma, some um ao registrador; em uma gravação, sobrescreva o contador com o registrador. Depois, avance essa thread para o próximo passo.
- Tempo-alvo
- O(s)
- Espaço-alvo
- O(t)
Restrições
- every thread finishes all of its steps
Solução
O bug de uma data race mora no intervalo entre uma leitura e a gravação correspondente, então a simulação guarda exatamente o estado de que esse intervalo precisa: um registrador por thread e qual passo cada thread executa em seguida. Uma leitura copia o valor compartilhado, uma soma altera só a cópia privada, e uma gravação armazena a cópia privada por cima do que o contador tiver agora, o que descarta em silêncio qualquer incremento que tenha caído no meio. Por isso, repetir o escalonamento passo a passo reproduz a atualização perdida exatamente como o hardware faria. O tempo é O(s) para um escalonamento de s passos, e o espaço é O(t) para t threads.
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])) # -> 2Travou na ideia, e não no código? Condições de corrida explica isso.