Retries em um loop de compare-and-swap
A missão
Problema
Várias threads somam a própria quantia a um único valor compartilhado, sem lock. Cada thread repete dois passos: ler o valor compartilhado para um snapshot privado e, depois, fazer o compare-and-swap. O swap só tem sucesso se o valor compartilhado ainda for igual ao snapshot; nesse caso, ele grava snapshot + amount e a thread termina. Caso contrário, o swap falha, nada é gravado e a thread recomeça com uma nova leitura. Você recebe o valor inicial, a quantia de cada thread e o escalonamento como uma lista de números de thread, em que cada entrada deixa aquela thread executar o seu próximo passo. Entradas de uma thread que já terminou são ignoradas. Retorne o valor final e quantos swaps cada thread perdeu.
Exemplos
Input: start = 0, amounts = [5, 7], schedule = [0, 1, 0, 1, 1, 1]
Output: (12, [0, 1])
Por quê: o swap da thread 1 falha porque a thread 0 mudou o valor depois que a thread 1 o leu, então ela lê de novo e tenta outra vez
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ê: as três leem 0, só um swap por rodada pode vencer, e a thread 2 perde duas vezes
Input: start = 10, amounts = [3], schedule = [0, 0]
Output: (13, [0])
Por quê: edge case: sem nenhum outro escritor, o primeiro swap sempre tem sucesso
Dicas
0 / 3
Diferente de uma leitura e uma gravação simples, um swap que falha não sobrescreve nada. O custo da contenção passa de atualizações perdidas para retries.
Cada thread precisa de um snapshot, ou de um marcador de que o próximo passo é uma leitura, e de uma flag indicando se ela já terminou.
Percorra o escalonamento. Pule as threads que terminaram. Em uma leitura, guarde o valor compartilhado como snapshot. Em um swap, compare o valor compartilhado com o snapshot: se forem iguais, grave snapshot + amount e termine; se não, conte uma falha e limpe o snapshot para que o próximo passo seja uma leitura.
- Tempo-alvo
- O(s)
- Espaço-alvo
- O(t)
Solução
Um loop de compare-and-swap troca o lock por uma verificação otimista: a gravação só acontece se ninguém mudou o valor desde que esta thread o leu. A simulação guarda o que essa verificação precisa, um snapshot por thread e se ela já terminou, e um snapshot None significa que o próximo passo da thread é uma leitura. Um swap que falha não grava nada e manda a thread reler, então cada quantia entra exatamente uma vez e o valor final é sempre o inicial mais a soma, e essa é a diferença em relação à corrida da atualização perdida. O que a contenção custa, em vez disso, são retries, e o segundo exemplo mostra como eles se acumulam na thread que continua perdendo. O tempo é O(s) para um escalonamento de s passos, e o espaço é O(t) para t threads.
def cas_add(start, amounts, schedule):
value = start # the shared value
snap = [None] * len(amounts) # None means the next step is a read
done = [False] * len(amounts)
failed = [0] * len(amounts)
for t in schedule:
if done[t]:
continue # finished threads take no more steps
if snap[t] is None:
snap[t] = value # read into a private snapshot
elif value == snap[t]:
value = snap[t] + amounts[t] # the swap wins: nobody wrote in between
done[t] = True
else:
failed[t] += 1 # someone got there first: retry from a read
snap[t] = None
return value, failed
print(cas_add(0, [5, 7], [0, 1, 0, 1, 1, 1])) # -> (12, [0, 1])
print(cas_add(0, [1, 1, 1], [0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 2, 2])) # -> (3, [0, 1, 2])
print(cas_add(10, [3], [0, 0])) # -> (13, [0])Travou na ideia, e não no código? Compare-and-swap explica isso.