Garantias de progresso: de obstruction-free a wait-free

Três contadores dão a resposta certa sob todos os escalonamentos e, mesmo assim, não são iguais. Pause uma thread no pior momento: a trava giratória para todo mundo, o contador com compara-e-troca deixa alguém passar e o contador fetch-and-add deixa cada thread terminar em 1 turno. São os três degraus da escada das garantias de progresso.

Um sistema operacional real pode tirar uma thread do seu núcleo a qualquer momento: sua fatia de tempo acaba, uma falha de página a manda ao disco, chega uma interrupção. Uma boa estrutura concorrente deve sobreviver a isso. Precisamos a pergunta com um adversário. Ele executa um prefix de turnos à sua escolha, depois pausa uma thread para sempre e damos um budget de rodadas a todas as outras. Se alguma thread não pausada ainda não terminou, a estrutura pode ser parada. Uma trava giratória falha nesse teste do jeito mais simples: se o adversário pausa a thread que segura a trava, as outras giram até o orçamento acabar.

def locked_increments(k):    def thread(shared):        for _ in range(k):            while True:                yield                if not shared.get("lock", 0):                    shared["lock"] = 1                    break            yield            value = shared.get("x", 0)            yield            shared["x"] = value + 1            yield            shared["lock"] = 0    return threaddef progress_without(make_threads, prefix, paused, budget=50):    n = len(make_threads({}))    allowed = [tid for tid in range(n) if tid not in paused]    _, alive = run_prefix(make_threads, list(prefix) + allowed * budget)    return [tid for tid in allowed if tid not in alive]lk = lambda shared: [locked_increments(1)(shared), locked_increments(1)(shared)]print(run_prefix(lk, [0]))print("thread 0 paused holding the lock:", progress_without(lk, [0], [0]))print("thread 0 finished first:         ", progress_without(lk, [0, 0, 0, 0], [0]))

({'lock': 1}, [0, 1])
thread 0 paused holding the lock: []
thread 0 finished first:          [1]

Depois de um turno a thread 0 segura a trava ('lock': 1). Pausada ali, a thread 1 não termina nada em cinquenta rodadas: []. Deixe a thread 0 fazer antes seus quatro turnos e a trava volta a ficar livre, então a thread 1 termina: [1]. A diferença é só onde o adversário ataca. Uma trava transforma qualquer pausa dentro da seção crítica numa pausa do programa inteiro.

is_blocking automatiza o adversário. Tenta todos os prefixos de alguns turnos, pausa cada thread viva por vez e pergunta a progress_without se as outras ainda terminam. Para a trava giratória a resposta é sim depois de um único turno. Para o contador com compara-e-troca nunca: uma thread pausada entre a leitura e a troca simplesmente deixa o valor inalterado, então a troca da outra thread tem sucesso. Esta é a definição de sem travas: o sistema como um todo sempre avança, mesmo se uma thread estiver parada para sempre.

def is_blocking(make_threads, depth=3, budget=50):    def visit(prefix):        _, alive = run_prefix(make_threads, prefix)        for paused in alive:            finished = progress_without(make_threads, prefix, [paused], budget)            if len(finished) < len([tid for tid in range(len(make_threads({}))) if tid != paused]):                return True        if len(prefix) < depth:            return any(visit(prefix + [tid]) for tid in alive)        return False    return visit([])cs = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]at = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]print("spin lock:", is_blocking(lk))print("compare-and-swap:", is_blocking(cs))print("fetch-and-add:", is_blocking(at))

spin lock: True
compare-and-swap: False
fetch-and-add: False

Tanto o contador com compara-e-troca quanto o contador fetch-and-add são não bloqueantes. A escada tem um terceiro degrau porque «sem travas» ainda permite um dia ruim para uma thread: ela pode perder todas as corridas.

Uma operação wait-free tem um limite para seus próprios turnos que nenhum vizinho pode quebrar. worst_own_turns o mede: o maior número de turnos que uma thread toma em todos os escalonamentos completos. classify faz então a pergunta decisiva. O pior caso da thread 0 continua o mesmo quando o vizinho tem 1 incremento e quando tem 3? Se sim, a thread 0 é wait-free. Se cresce, o vizinho pode fazer a thread 0 tentar mais vezes, então a estrutura é apenas lock-free.

def worst_own_turns(make_threads, tid):    worst = 0    def visit(prefix):        nonlocal worst        _, alive = run_prefix(make_threads, prefix)        if not alive:            worst = max(worst, prefix.count(tid))            return        for other in alive:            visit(prefix + [other])    visit([])    return worstdef classify(factory, others=(1, 3)):    def program(m):        return lambda shared: [factory(1)(shared), factory(m)(shared)]    if is_blocking(program(others[0])):        return "blocking"    light, busy = worst_own_turns(program(others[0]), 0), worst_own_turns(program(others[1]), 0)    return "wait-free" if light == busy else "lock-free"for neighbour in (1, 2, 3):    cas = lambda shared: [cas_increments(1)(shared), cas_increments(neighbour)(shared)]    atomic = lambda shared: [atomic_increments(1)(shared), atomic_increments(neighbour)(shared)]    print(neighbour, "increments next door: CAS", worst_own_turns(cas, 0), "turns, fetch-and-add", worst_own_turns(atomic, 0))print([classify(f) for f in (locked_increments, cas_increments, atomic_increments)])

1 increments next door: CAS 4 turns, fetch-and-add 1
2 increments next door: CAS 6 turns, fetch-and-add 1
3 increments next door: CAS 8 turns, fetch-and-add 1
['blocking', 'lock-free', 'wait-free']

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:6]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]for name, factory in (("locked", locked_increments), ("cas", cas_increments), ("atomic", atomic_increments)):    program = lambda shared, f=factory: [f(k)(shared) for k in ups]    blocking = is_blocking(program)    print(name, classify(factory), blocking, None if blocking else worst_own_turns(program, 0))

locked blocking True None
cas lock-free False 8
atomic wait-free False 1

Leia as barras: a thread fetch-and-add precisa de 1 turno por mais ocupado que esteja o vizinho, enquanto a thread com compara-e-troca precisa de 4, 6 e depois 8 turnos conforme o vizinho faz mais incrementos. Cada incremento extra ao lado pode fazer a thread 0 perder mais uma corrida e repetir a leitura e a troca. Esse crescimento é exatamente o que separa lock-free de wait-free.

O laboratório segue a aula: o contador com trava giratória, a execução com algumas threads pausadas, o teste que diz se pausar uma thread pode parar as outras, o pior caso dos turnos próprios de uma thread, a classificação de um contador e o estudo dos três contadores nos dias de alta do SPY.

• Função · perguntaBaseia-se em
• locked_increments(k)Um contador que espera uma trava?Aritmética simples
• progress_without(make_threads, prefix, paused, budget)Quem termina se algumas threads estão pausadas?run_prefix
• is_blocking(make_threads, depth, budget)Uma thread pausada pode parar todo mundo?progress_without
• worst_own_turns(make_threads, tid)De quantos turnos uma thread pode precisar?run_prefix
• classify(factory, others)Bloqueante, lock-free ou wait-free?is_blockingworst_own_turns
• study(bars)Onde ficam os três contadores no SPY?classifyis_blockingworst_own_turns

Próximo tópico: agora você sabe o que uma fila poderia prometer. Um buffer circular de um produtor e um consumidor constrói a fila sem travas útil mais simples, com um escritor e um leitor, memória fixa e nenhuma leitura-modificação-escrita atômica, e o explorador verifica que ela nunca perde nem reordena um tick.