Pular para o conteúdo

Retries em um loop de compare-and-swap

Fácil#compare-and-swap#step-simulation~15 min

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

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

Travou na ideia, e não no código? Compare-and-swap explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado