Condições de corrida e por que existem as travas

Duas threads somam 1 ao mesmo contador e o contador termina errado, sem erro nem falha. A linha x += 1 não é um passo, são três, e a ordem em que duas threads intercalam esses passos decide o resultado. Em 1085 dias de alta do SPY, 542 atualizações somem; uma trava traz todas de volta.

Um processador não consegue somar a um valor que mora na memória. Ele carrega o valor num registrador, soma ao registrador e guarda o registrador de volta. Então x += 1 é load x, add 1, store x. Uma thread sozinha faz os três em sequência e nada pode dar errado. Com duas threads, a máquina pode executar um passo de uma e depois um passo da outra, em qualquer ordem. Para ver isso escrevemos uma pequena máquina. Uma thread é uma lista de passos, cada uma com seu registrador; as threads compartilham um dicionário de valores nomeados. A função execute executa um passo de uma thread. A seguir jogamos à mão os seis passos de duas threads, um passo cada uma por vez.

def execute(op, shared, regs, locks, tid):    kind = op[0]    if kind == "load":        regs[tid] = shared.get(op[1], 0)    elif kind == "add":        regs[tid] += op[1]    elif kind == "store":        shared[op[1]] = regs[tid]    elif kind == "lock":        if op[1] in locks:            return False        locks[op[1]] = tid    elif kind == "unlock":        del locks[op[1]]    return Trueshared, regs, locks = {"x": 0}, {0: 0, 1: 0}, {}turns = [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)]1for tid, step in turns:    execute(INCREMENT[step], shared, regs, locks, tid)    print("thread", tid, INCREMENT[step], "->", shared, regs)

thread 0 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 1 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 0 ('add', 1) -> {'x': 0} {0: 1, 1: 0}
thread 1 ('add', 1) -> {'x': 0} {0: 1, 1: 1}
thread 0 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}
thread 1 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}

1. 1As duas threads carregam antes de qualquer uma guardar: cada registrador tem 0.

Leia a saída linha a linha. A thread 0 carrega 0, a thread 1 também carrega 0 (a thread 0 ainda não guardou), ambas somam 1 a um registrador que tem 0 e ambas guardam 1. Duas threads fizeram cada uma seu x += 1, mas x vale 1, não 2. Uma atualização se perdeu. Nada estava errado no código de nenhuma das threads; o bug existe só nessa ordem de passos.

No mundo real o escalonamento é escolhido pelo sistema operacional e muda de uma execução para outra, por isso uma corrida é tão difícil de reproduzir. Na nossa máquina nós o escolhemos. Um escalonamento é uma lista de números de threads, e run dá um turno à thread nomeada por cada entrada. Dois escalonamentos simples importam. No escalonamento serial a thread 0 executa todos os seus passos e depois a thread 1: é o que esperamos. No escalonamento round-robin as threads dão um passo cada uma por vez: é o pior caso para o nosso contador, porque os passos das duas threads se sobrepõem em todo lugar. A função lost_updates compara o que os incrementos deveriam ter somado com o que o contador mostra.

def run(programs, schedule, shared=None):    shared = dict(shared or {})    regs = {tid: 0 for tid in range(len(programs))}    pcs = [0] * len(programs)    locks = {}    for tid in schedule:        if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):            pcs[tid] += 1    while any(pcs[t] < len(programs[t]) for t in range(len(programs))):        progress = False        for tid in range(len(programs)):            if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):                pcs[tid] += 1                progress = True        if not progress:            raise RuntimeError("deadlock")    return shareddef serial_schedule(programs):    return [tid for tid, program in enumerate(programs) for _ in program]def round_robin_schedule(programs):    longest = max((len(program) for program in programs), default=0)    return [tid for step in range(longest) for tid, program in enumerate(programs) if step < len(program)]def lost_updates(programs, schedule, name="x"):    expected = sum(op[1] for program in programs for op in program if op[0] == "add")    return expected - run(programs, schedule).get(name, 0)two = [INCREMENT, INCREMENT]print(serial_schedule(two), run(two, serial_schedule(two)))print(round_robin_schedule(two), run(two, round_robin_schedule(two)))print("lost:", lost_updates(two, round_robin_schedule(two)))

[0, 0, 0, 1, 1, 1] {'x': 2}
[0, 1, 0, 1, 0, 1] {'x': 1}
lost: 1

O escalonamento serial [0, 0, 0, 1, 1, 1] dá 2; o escalonamento round-robin [0, 1, 0, 1, 0, 1] dá 1 e perde uma atualização. Observe o que run faz quando o escalonamento acaba cedo: as threads não terminadas continuam recebendo turnos, um passo cada uma na ordem das threads, então todo programa sempre termina. Observe também que uma thread terminada ignora seus turnos, então qualquer lista de números de threads é um escalonamento válido.

Uma trava corrige a corrida proibindo a sobreposição. Uma thread pega a trava antes de load e a solta depois de store. Uma segunda thread que pedir a trava nesse meio-tempo não a consegue: seu turno não faz nada e ela fica no mesmo passo até a trava ser liberada. Os passos entre lock e unlock executam assim como um único bloco e nenhuma outra thread consegue se meter no meio. A função counter_program constrói o programa de uma thread que incrementa um contador, com ou sem a trava. As travas trazem um novo perigo, mostrado no fim do código: duas threads que pegam duas travas em ordens opostas podem cada uma segurar a trava de que a outra precisa, e nenhuma consegue andar. Isso é um deadlock, e o nosso run o detecta quando uma passada completa não faz progresso.

def counter_program(increments, locked=False):    program = []    for _ in range(increments):        program += ([("lock", "m")] if locked else []) + INCREMENT + ([("unlock", "m")] if locked else [])    return programsafe = [counter_program(1, locked=True), counter_program(1, locked=True)]print(counter_program(1, locked=True))print(run(safe, round_robin_schedule(safe)))ab = [[("lock", "a"), ("lock", "b"), ("unlock", "b"), ("unlock", "a")],      [("lock", "b"), ("lock", "a"), ("unlock", "a"), ("unlock", "b")]]try:    run(ab, [0, 1])except RuntimeError as error:    print("error:", error)

[('lock', 'm'), ('load', 'x'), ('add', 1), ('store', 'x'), ('unlock', 'm')]
{'x': 2}
error: deadlock

def study(bars):    returns = [float(r) for r in bars["close"].pct_change().dropna()][:2000]    ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]    free = [counter_program(k) for k in ups]    locked = [counter_program(k, locked=True) for k in ups]    return {"up": sum(ups),            "serial": run(free, serial_schedule(free))["x"],            "racy": run(free, round_robin_schedule(free))["x"],            "locked": run(locked, round_robin_schedule(locked))["x"]}print(study(load_bars()))

{'up': 1085, 'serial': 1085, 'racy': 543, 'locked': 1085}

Sem trava, o escalonamento round-robin mantém as duas threads a um passo de distância, então elas sempre carregam o mesmo valor e cada par de incrementos conta uma vez só: cerca de metade dos 1085 dias de alta se perde. Uma trava restaura o total exato, ao preço de fazer uma thread esperar.

O laboratório segue a aula: um passo de uma thread, a máquina inteira sob um escalonamento, os dois escalonamentos simples, a contagem de atualizações perdidas, o programa de uma thread contadora com e sem trava e o estudo de duas threads contando os dias de alta do SPY.

• Função · perguntaBaseia-se em
• execute(op, shared, regs, locks, tid)O que faz um passo, e a thread precisa esperar?Aritmética simples
• run(programs, schedule, shared)O que as threads deixam sob este escalonamento?execute
• serial_schedule(programs)Uma thread depois da outra?Aritmética simples
• round_robin_schedule(programs)Um passo cada um por vez?Aritmética simples
• lost_updates(programs, schedule)Quantos incrementos somem?run
• counter_program(increments, locked)O que faz uma thread contadora?Aritmética simples
• study(bars)Quantas atualizações uma corrida custa no SPY?counter_programrunlost_updates

Próximo tópico: você achou a atualização perdida escolhendo um escalonamento à mão. Um programa real tem escalonamentos demais para tentar à mão. Em Um explorador de intercalações você enumera todos os escalonamentos de um programa pequeno, conta os que o quebram e mantém o explorador como ferramenta para o resto da habilidade.