Um explorador de intercalações: achar bugs enumerando escalonamentos

Tentar escalonamentos à mão só acha um bug se você adivinhar o certo. Um explorador executa o programa sob todos os escalonamentos, lista todos os resultados e entrega o escalonamento que o quebrou. Para duas threads que contam os dias de alta de dez retornos do SPY há 210 escalonamentos, e só 10 dão a contagem certa.

Um escalonamento é uma ordem de turnos, e a thread t toma exatamente lengths[t] deles. Para contar as ordens, colocamos todos os turnos em fila (a soma dos comprimentos), que podem ser arrumados em tantas maneiras quanto o fatorial desse número; depois dividimos pelo fatorial dos turnos de cada thread, porque trocar dois turnos da mesma thread não dá um escalonamento novo. É o coeficiente multinomial. Cresce rápido: duas threads de 2 turnos têm só 6 escalonamentos, três threads de 3 turnos têm 1680 e duas threads de 10 turnos têm 184 756. Por isso ninguém consegue checar um programa concorrente tentando escalonamentos ao acaso e esperando.

def count_schedules(lengths):    total = factorial(sum(lengths))    for n in lengths:        total //= factorial(n)    return totalprint(count_schedules([2, 2]))print(count_schedules([3, 3, 3]))print(count_schedules([10, 10]))

6
1680
184756

No laboratório anterior uma thread era uma lista de passos. O código real se escreve melhor em Python comum, então daqui em diante uma thread é um gerador que recebe o dicionário compartilhado e executa yield antes de cada acesso a dados compartilhados. Uma chamada de next() avança a thread até o próximo acesso e não mais, de modo que um turno é exatamente um passo com o qual outra thread pode se intercalar. run_threads prepara cada gerador (executa até o primeiro yield), dá um turno à thread nomeada por cada entrada do escalonamento e, quando o escalonamento acaba, deixa as threads não terminadas terminarem na ordem das threads. all_schedules lista todas as ordens de turnos escolhendo qual thread vai primeiro e recursando no que sobra. A seguir, os seis escalonamentos de duas threads que incrementam uma vez cada.

def all_schedules(lengths):    if sum(lengths) == 0:        return [[]]    out = []    for tid, n in enumerate(lengths):        if n:            rest = list(lengths)            rest[tid] -= 1            out += [[tid] + tail for tail in all_schedules(rest)]    return outdef run_threads(make_threads, schedule, shared=None):    shared = dict(shared or {})    threads = make_threads(shared)    alive = [True] * len(threads)    def turn(tid):        try:            next(threads[tid])        except StopIteration:            alive[tid] = False    for tid in range(len(threads)):        turn(tid)    for tid in schedule:        if alive[tid]:            turn(tid)    while any(alive):        for tid in range(len(threads)):            if alive[tid]:                turn(tid)    return sharedtwo = lambda shared: [increments(1)(shared), increments(1)(shared)]for schedule in all_schedules([2, 2]):    print(schedule, run_threads(two, schedule))

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

Dois dos seis escalonamentos terminam em 2, os outros quatro em 1. Os dois bons são aqueles em que uma thread faz seus dois passos antes de a outra começar. Nos outros quatro as duas threads leem antes de qualquer uma escrever, que é exatamente a atualização perdida do laboratório anterior, agora achada sem adivinhar.

explore executa o programa sob todos os escalonamentos e conta quantos dão cada estado final. A chave é uma tupla ordenada de pares (nome, valor) para que estados iguais sejam a mesma chave. find_schedule faz a pergunta de um relatório de bug: qual escalonamento quebra o meu invariante? Devolve o primeiro e, como run_threads é determinístico, dá para reproduzi-lo, imprimi-lo ou colá-lo num teste. Se devolve None, o invariante vale sob todos os escalonamentos, o que é uma prova para este programa pequeno, não uma esperança.

def explore(make_threads, lengths, shared=None):    outcomes = {}    for schedule in all_schedules(lengths):        key = tuple(sorted(run_threads(make_threads, schedule, shared).items()))        outcomes[key] = outcomes.get(key, 0) + 1    return outcomesdef find_schedule(make_threads, lengths, check, shared=None):    for schedule in all_schedules(lengths):        if not check(run_threads(make_threads, schedule, shared)):            return schedule    return Noneprint(explore(two, [2, 2]))print(find_schedule(two, [2, 2], lambda shared: shared["x"] == 2))

{(('x', 2),): 2, (('x', 1),): 4}
[0, 1, 0, 1]

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:10]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]lengths = [2 * k for k in ups]many = lambda shared: [increments(k)(shared) for k in ups]print(ups, count_schedules(lengths))print({dict(key)["x"]: n for key, n in explore(many, lengths).items()})

[2, 3] 210
{5: 10, 4: 70, 3: 104, 2: 26}

A resposta certa, x = 5, aparece em só 10 dos 210 escalonamentos, cerca de 5%. Um teste que executa o programa uma vez, ou cem vezes numa máquina real onde as threads raramente se sobrepõem exatamente assim, passaria quase sempre e ainda assim entregaria um bug. O explorador não pode perdê-lo, e find_schedule entrega o primeiro culpado: [0, 0, 0, 1, 0, 1, 1, 1, 1, 1].

O laboratório segue a aula: o número de escalonamentos, a lista de todos, a máquina que executa threads geradoras sob um escalonamento, o explorador que conta resultados, a busca do primeiro escalonamento que quebra um invariante e o estudo de duas threads contando dias de alta do SPY.

• Função · perguntaBaseia-se em
• count_schedules(lengths)Quantos escalonamentos o programa tem?Aritmética simples
• all_schedules(lengths)Quais são, em ordem?Aritmética simples
• run_threads(make_threads, schedule, shared)O que um escalonamento deixa?Aritmética simples
• explore(make_threads, lengths, shared)Quais resultados existem e quantas vezes?all_schedulesrun_threads
• find_schedule(make_threads, lengths, check)Qual escalonamento quebra o invariante primeiro?all_schedulesrun_threads
• study(bars)Quantos escalonamentos da contagem do SPY dão errado?count_schedulesexplorefind_schedule

Próximo tópico: o explorador mostra que o bug é real; agora o consertamos. Atômicas e leitura-modificação-escrita acrescenta as operações que um processador faz num passo indivisível, como fetch-and-add e compare-and-swap, e você confere com o explorador que o contador está certo sob todos os escalonamentos.