Sincronização

As próprias estruturas de dados de um kernel, filas de execução, alocadores de memória, estado de driver de dispositivo, são compartilhadas entre quantos contextos quer que as toquem ao mesmo tempo: um handler de interrupção rodando na mesma CPU que acabou de preemptar código de kernel comum, ou, em um sistema multiprocessador, CPUs inteiramente diferentes executando código de kernel simultaneamente. Sem algo impondo acesso exclusivo, dois desses contextos modificando a mesma estrutura em momentos sobrepostos a corrompem de formas difíceis de reproduzir e mais difíceis ainda de diagnosticar, já que a falha resultante frequentemente aparece longe, e muito depois, do acesso conflitante real.

Uma race condition concreta

Considere uma fila de execução implementada como uma lista ligada simples, com enqueue inserindo uma tarefa na cabeça:

void enqueue(struct task *t) {
    t->next = run_queue_head;
    run_queue_head = t;
}

Se uma interrupção dispara entre as duas linhas acima, e o próprio handler de interrupção chama enqueue em alguma outra tarefa, a chamada original resume depois e sobrescreve run_queue_head com um ponteiro construído a partir de um valor agora obsoleto, silenciosamente descartando o que quer que o handler de interrupção tenha acabado de inserir na lista por completo. Em uma única CPU, esse exemplo específico é evitável só desabilitando interrupções em torno das duas linhas; em um sistema multiprocessador, uma segunda CPU rodando enqueue concorrentemente em um fluxo de instruções genuinamente diferente produz a corrupção idêntica, e desabilitar interrupções na primeira CPU não faz nada para impedir a segunda CPU de rodar ao mesmo tempo.

Desabilitando interrupções

Desabilitar interrupções (a instrução cli no x86, combinada com sti para reabilitá-las) impede que um handler de interrupção na mesma CPU rode durante uma seção crítica, tornando-a suficiente por si só para proteger dados que só código de kernel comum e handlers de interrupção em uma única CPU jamais tocam. Não é de graça: enquanto interrupções estão desabilitadas, a CPU não consegue responder a eventos de hardware algum, incluindo a interrupção de timer que de outra forma dispararia uma decisão de escalonamento, então uma seção crítica protegida dessa forma precisa se manter curta ou atrasa mensuravelmente o tratamento de interrupção em outro lugar do sistema, ticks de timer incluídos. Também é inteiramente inútil sozinha contra uma segunda CPU rodando o mesmo caminho de código concorrentemente, já que desabilitar interrupções é uma operação por CPU sem efeito algum em qualquer outro núcleo.

Spinlocks

Um spinlock estende a desabilitação de interrupções para o caso multiprocessador com uma flag compartilhada que toda CPU checa antes de entrar em uma seção crítica, esperando ativamente (girando) em um loop apertado até a flag ficar limpa em vez de fazer qualquer outra coisa enquanto espera:

void spin_lock(volatile int *lock) {
    while (__sync_lock_test_and_set(lock, 1)) {
        while (*lock) { /* girando */ }
    }
}

void spin_unlock(volatile int *lock) {
    __sync_lock_release(lock);
}

O loop de espera interno, lendo o lock sem tentar adquiri-lo a cada iteração, existe especificamente para evitar martelar a própria instrução atômica de test-and-set enquanto espera, já que essa instrução tipicamente exige posse exclusiva da linha de cache relevante e pedi-la repetidamente a partir de toda CPU em espera gera tráfego de coerência de cache que mensuravelmente desacelera a CPU que de fato segura o lock e está tentando liberá-lo. Um spinlock destinado a também proteger contra um handler de interrupção na mesma CPU precisa desabilitar interrupções durante o tempo em que é segurado, não só executar a operação atômica, já que esperar com interrupções ainda habilitadas pode causar um deadlock de uma CPU contra si mesma se uma interrupção dispara naquele mesmo núcleo e seu handler então também tenta adquirir o mesmo lock já segurado.

Mutexes e semáforos

Esperar ativamente só faz sentido quando se espera que um lock seja segurado brevemente; uma seção protegida que possa bloquear em I/O de disco ou esperar uma quantidade não limitada de tempo é melhor servida por um mutex, que coloca uma tarefa em espera para dormir em vez de queimar tempo de CPU em um loop, acordando-a novamente uma vez que o lock fica disponível. Isso exige que o mutex interaja diretamente com o escalonador: adquirir um mutex já segurado remove a tarefa chamadora da fila de execução e a coloca em uma fila de espera associada àquele mutex, e liberar o mutex move uma tarefa em espera (ou, dependendo do design, todas elas, para disputá-lo novamente) de volta para a fila de execução. Um semáforo generaliza esse mesmo mecanismo de fila de espera para um contador em vez de um único estado binário segurado/livre, permitindo até algum número fixo de detentores de uma vez em vez de exatamente um, útil para proteger um pool de um número fixo de recursos intercambiáveis, como um conjunto fixo de buffers, em vez de uma única estrutura de dados de acesso exclusivo. Num sistema onde tarefas também carregam prioridade de escalonamento, a fila de espera de um mutex introduz um problema além da contenção comum: um detentor de baixa prioridade pode travar indiretamente um esperador de alta prioridade, o assunto de inversão de prioridade.

Operações atômicas e o prefixo LOCK

Tanto spinlocks quanto as operações de compare-and-swap das quais mutexes comumente dependem, no fim, precisam que a CPU forneça uma operação que seja indivisível mesmo sob execução concorrente de outro núcleo, já que uma sequência comum de leitura-modificação-escrita construída a partir de instruções separadas tem exatamente o mesmo problema de race condition do exemplo enqueue acima, só em escala menor. No x86, o prefixo LOCK aplicado a certas instruções (CMPXCHG, XADD, XCHG entre elas) impõe posse exclusiva da linha de cache da localização de memória relevante durante aquela única instrução, garantindo que acesso algum de outra CPU à mesma localização consiga se intercalar com ela. O CMPXCHG em particular, compare-and-swap, é o bloco de construção do qual a maioria dos algoritmos lock-free de nível mais alto são construídos: ele compara uma localização de memória contra um valor esperado e só escreve um novo valor se a comparação tiver sucesso, permitindo que o software detecte e tente de novo quando outra CPU modificou a localização primeiro, em vez de sobrescrever cegamente o que quer que esteja lá.

Ordenação de memória

Uma CPU e um compilador são ambos livres para reordenar acessos de memória que não tenham dependência de dados observável entre si, uma otimização invisível para código de thread única mas que pode quebrar um algoritmo que dependa de as escritas de uma CPU se tornarem visíveis a outra CPU em uma ordem específica. Uma barreira de memória (mfence no x86, ou variantes mais estreitas lfence/sfence para ordenação só de leitura ou só de escrita) força todo acesso de memória antes dela na ordem do programa a se completar, e se tornar visível a outras CPUs, antes de qualquer acesso depois dela prosseguir. A maioria das implementações de lock e operação atômica já inclui as barreiras necessárias como parte da própria operação, o que é a razão pela qual código construído inteiramente a partir de locks e atômicos raramente precisa de barreiras explícitas próprias; código lock-free escrito à mão que lê e escreve estado compartilhado sem passar por nenhum dos dois é onde barreiras ausentes mais frequentemente produzem bugs que dependem de timing e são quase impossíveis de reproduzir de forma confiável.

Notas de implementação

Um spinlock segurado através de uma chamada que ela mesma bloqueia, ou através de uma falha de página tratada por código que espera dormir, pode causar deadlock no sistema inteiro em vez de só nas duas CPUs disputando, já que toda outra CPU girando naquele lock não tem como saber que o detentor não está meramente lento mas está esperando por algo que nunca vai se resolver enquanto o lock é segurado; é por isso que código de kernel segurando um spinlock é convencionalmente exigido a evitar qualquer coisa que possa dormir durante toda a seção. Adquirir múltiplos locks em ordem inconsistente entre caminhos de código diferentes é a causa clássica de deadlock mesmo sem lock algum sendo segurado por tempo demais: se um caminho adquire o lock A depois o lock B enquanto outro adquire B depois A, os dois podem acabar cada um segurando um lock enquanto espera pelo outro, indefinidamente, e a disciplina usual para evitar isso é uma única ordem global fixa que todo caminho de código adquirindo mais de um lock precisa seguir.

Referências

^ Intel, Intel 64 and IA-32 Architectures Software Developer’s Manual, volume 3, seção sobre operações atômicas com lock (define o prefixo LOCK e quais instruções o aceitam)
^ Documentação do kernel Linux, “Linux Kernel Memory Barriers” (um tratamento detalhado de ordenação de memória a partir da perspectiva de um kernel real)

Ver também

Schedulers: a fila de execução de onde vem o exemplo de race condition deste artigo, e onde tarefas bloqueadas na fila de espera de um mutex de fato vivem.
Context Switching: o que de fato acontece quando um mutex tira uma tarefa da CPU.
Inversão de Prioridade: o que pode dar errado quando a fila de espera de um mutex interage com escalonamento por prioridade.
IPC: as mesmas condições de corrida cobertas aqui, reintroduzidas entre processos separados compartilhando memória.
Bring-Up de Multiprocessador: como um segundo núcleo de fato começa a rodar, o pré-requisito para qualquer coisa deste artigo importar.