O Problema da Seção Crítica e a Exclusão Mútua

• Definir uma seção crítica como qualquer código que acessa estado compartilhado de um jeito que não pode ser intercalado com o acesso de outra thread a esse mesmo estado.
• Enunciar as três propriedades que toda solução correta para o problema da seção crítica precisa garantir: exclusão mútua, progresso e espera limitada.
• Acompanhar, em nível de instrução, como um incremento não sincronizado de uma variável compartilhada pode produzir um resultado final errado.
• Explicar por que "simplesmente não trocar de contexto durante uma seção crítica" não é, por si só, uma solução completa nem suficiente.

O conceito anterior estabeleceu que as threads compartilham memória de verdade, e que esse compartilhamento é exatamente o que torna as condições de corrida fisicamente possíveis, e não hipotéticas. Este conceito dá a esse perigo seu nome formal: o problema da seção crítica: identificar com precisão qual código é perigoso (qualquer código que toca estado compartilhado cuja intercalação com o acesso de outra thread poderia produzir um resultado errado) e com precisão o que uma correção certa precisa garantir. Toda ferramenta de sincronização vista mais adiante neste bloco (locks, variáveis de condição, semáforos) existe para resolver este único problema enunciado formalmente; nomeá-lo com precisão aqui é o que permite avaliar os conceitos posteriores contra um padrão claro, e não contra uma intuição vaga.

O que é uma seção crítica

Uma seção crítica é um trecho de código que acessa um ou mais pedaços de estado compartilhado (uma variável compartilhada, uma estrutura de dados compartilhada, um arquivo compartilhado) de um jeito em que duas threads executando-o em tempos sobrepostos poderiam interferir nos resultados uma da outra. A linha counter++ do exemplo resolvido do conceito anterior é uma seção crítica de livro: ela lê uma variável compartilhada, calcula um valor novo e o escreve de volta; três passos separados em nível de máquina, qualquer um dos quais poderia ser interrompido por outra thread fazendo os mesmos três passos na mesma variável.

As três propriedades exigidas

Uma solução correta para o problema da seção crítica (seja qual for o mecanismo específico usado para construí-la) precisa garantir as três propriedades a seguir ao mesmo tempo:

1. Exclusão mútua. No máximo uma thread pode estar executando dentro da seção crítica num dado momento. Essa é a propriedade central de segurança: ela impede diretamente a intercalação que causa as condições de corrida.
2. Progresso. Se nenhuma thread está na seção crítica no momento, e uma ou mais threads querem entrar, a decisão de quem entra em seguida não pode ser adiada indefinidamente por threads que não estão tentando entrar; em outras palavras, o sistema como um todo precisa continuar progredindo, e não entrar em deadlock ou livelock na questão de quem vai em seguida.
3. Espera limitada. Precisa haver um limite de quantas vezes outras threads podem entrar na seção crítica depois que uma dada thread pediu para entrar e antes que esse pedido seja atendido; nenhuma thread pode ser forçada a esperar para sempre enquanto outras threads furam a fila na frente dela repetidamente. É exatamente a preocupação com a inanição já vista no bloco de escalonamento, agora enunciada como requisito formal de correção da sincronização, e não como um detalhe agradável de escalonamento.

Um mecanismo de sincronização que oferece exclusão mútua, mas permite a inanição indefinida de alguma thread, resolveu só parte do problema; as três propriedades juntas definem a correção completa aqui.

Por que "simplesmente impedir trocas de contexto" não é a resposta inteira

Um instinto é eliminar o perigo desabilitando as interrupções (ou impedindo de outra forma uma troca de contexto) durante uma seção crítica: se a thread em execução não pode ser pausada no meio do counter++, nenhuma outra thread consegue se intercalar com ela. Isso de fato funciona numa máquina de uma única CPU para seções críticas muito curtas, e kernels reais usam exatamente esse truque internamente, em circunstâncias estreitas e controladas. Ele falha como solução de propósito geral por dois motivos reais: não faz nada em hardware de vários núcleos, em que uma thread diferente pode estar genuinamente executando em outro núcleo no mesmo instante físico, sem nenhuma troca de contexto envolvida (como o Exemplo 3 do conceito anterior mostrou); e deixar código arbitrário em nível de usuário desabilitar interrupções é um sério risco de segurança: um programa com bug ou malicioso poderia desabilitar as interrupções e nunca reabilitá-las, congelando a máquina inteira. É exatamente por isso que o próximo conceito se volta para as instruções atômicas fornecidas pelo hardware: mecanismos que funcionam corretamente em vários núcleos ao mesmo tempo, sem dar a uma única thread o poder de parar o sistema inteiro.

Exemplo 1: counter++ acompanhado em nível de instrução

A única linha counter++ normalmente é compilada em três passos de máquina separados:

text
LOAD  R1, counter     ; lê a variável compartilhada para um registrador
ADD   R1, R1, 1       ; incrementa o valor do registrador
STORE counter, R1     ; escreve o novo valor de volta na memória

Se a thread A executa LOAD e ADD (agora guardando counter + 1 no seu próprio registrador) e é interrompida antes do seu STORE, e a thread B roda a sequência inteira até o fim nesse meio-tempo, então A retoma e executa seu próprio STORE: o STORE de A sobrescreve a atualização de B usando um valor velho que A calculou antes de B sequer rodar, perdendo silenciosamente o incremento de B.

Exemplo 2: uma intercalação concreta que perde uma atualização

Começando com counter = 0, as duas threads pretendem incrementá-lo uma vez:

text
Tempo  Thread A                    Thread B                    counter
t0     LOAD R1, counter (R1=0)                                 0
t1                                 LOAD R1, counter (R1=0)     0
t2     ADD  R1, R1, 1  (R1=1)                                  0
t3                                 ADD  R1, R1, 1  (R1=1)      0
t4     STORE counter, R1 (=1)                                  1
t5                                 STORE counter, R1 (=1)      1

As duas threads pretendiam incrementar counter, então o resultado final correto é 2; mas o resultado real é 1, porque as duas threads leram o mesmo valor velho (0) antes de qualquer uma escrever de volta, e o STORE de B simplesmente sobrescreve o resultado idêntico de A, em vez de construir sobre ele. Nenhuma das threads fez algo errado isoladamente; o resultado errado é puramente consequência da intercalação.

Exemplo 3: conferindo uma "correção" proposta contra as três propriedades

Suponha que uma correção ingênua use uma única flag compartilhada: uma thread coloca flag = 1 antes de entrar na seção crítica e a volta para 0 na saída, com toda thread girando em while (flag == 1) { } antes de tentar marcá-la.

text
Exclusão mútua?  Quebrada: a verificação (while flag==1) e a marcação
                 (flag = 1) são elas mesmas dois passos separados e não
                 atômicos, então duas threads podem ambas ver flag==0 e
                 ambas seguirem para marcá-la e entrar, ao mesmo tempo.

Essa única falha basta para desqualificar o esquema inteiro, seja qual for seu desempenho em progresso ou espera limitada: uma solução correta precisa satisfazer a exclusão mútua incondicionalmente, e é exatamente por isso que o próximo conceito se volta para instruções atômicas fornecidas pelo hardware (test-and-set, compare-and-swap), em vez de pares comuns de load/store, que este exemplo mostra não serem suficientes sozinhos.

• "Uma seção crítica é qualquer código que use uma variável compartilhada." Uma seção crítica significa especificamente código cuja intercalação com outra thread acessando o mesmo estado compartilhado poderia produzir um resultado incorreto; código que só lê um valor que nunca muda, por exemplo, não precisa dessa proteção, mesmo tocando estado compartilhado.
• "A exclusão mútua sozinha é uma solução completa para o problema da seção crítica." A exclusão mútua é necessária, mas não suficiente: uma solução que concede acesso exclusivo, mas deixa uma thread esperando para sempre (violando a espera limitada) ou que pode entrar em deadlock por completo (violando o progresso) não resolveu o problema completo como definido formalmente aqui.
• "Desabilitar interrupções é uma solução geral e suficiente para o problema da seção crítica." Isso não impede a interferência de uma thread genuinamente rodando em outro núcleo físico no mesmo instante, e dar a programas comuns a capacidade de desabilitar interrupções é ele mesmo um risco sério; é um truque estreito, interno ao kernel, e não a resposta geral.
• "Se uma condição de corrida só aparece raramente nos testes, o código provavelmente está bem." Uma seção crítica sem proteção correta é insegura, não importa quão raramente a intercalação perigosa de fato se manifeste; a atualização perdida do Exemplo 2 pode acontecer em algumas execuções e não em outras, dependendo puramente de uma temporização de escalonamento imprevisível, e é exatamente isso que torna os bugs de concorrência notoriamente difíceis de pegar só com testes.

Uma seção crítica é qualquer código que acessa estado compartilhado de um jeito em que a execução sobreposta de duas threads poderia interferir nos resultados uma da outra, e uma solução correta para esse problema da seção crítica precisa garantir três propriedades juntas: exclusão mútua (no máximo uma thread dentro por vez), progresso (a escolha de quem entra em seguida não pode ser adiada indefinidamente por threads desinteressadas) e espera limitada (nenhuma thread pode ficar em inanição porque outras furam a fila repetidamente). Acompanhar o counter++ em nível de instrução mostra exatamente como um incremento de aparência comum é, na verdade, três passos separados e interrompíveis, e uma intercalação concreta pode perder silenciosamente uma atualização sem que nenhuma thread faça algo errado isoladamente. Correções simples construídas com operações comuns de load/store (como uma flag compartilhada) não conseguem garantir a exclusão mútua, porque a sequência de conferir e depois marcar não é ela mesma atômica, motivando a virada do próximo conceito para as instruções atômicas fornecidas pelo hardware como a base real sobre a qual os locks são construídos.