Quando começamos a lidar com múltiplos processos ou threads executando concorrentemente, uma série de problemas surge. A necessidade de sincronizar o acesso a recursos compartilhados se torna crucial para a integridade dos dados e o funcionamento correto do sistema. Nesta aula, exploramos os fundamentos da concorrência, os desafios que ela impõe e as principais soluções desenvolvidas para garantir a exclusão mútua e a sincronização entre processos.

1. O que é Concorrência e por que ela é necessária?

A concorrência é a base dos sistemas operacionais modernos. Sem ela, a CPU ficaria ociosa durante operações de E/S (I/O bound), desperdiçando recursos valiosos. A multiprogramação permite que vários processos residam na memória e alternem seu uso da CPU. Já o multiprocessamento oferece paralelismo real em sistemas com múltiplos núcleos.

O grande problema da concorrência é a condição de corrida (race condition). Ela ocorre quando o resultado de uma computação depende da ordem de execução das instruções de diferentes processos. Se dois processos tentam incrementar uma variável compartilhada ao mesmo tempo, a sequência de instruções (LOAD, INC, STORE) no nível de linguagem de máquina pode ser intercalada de forma imprevisível, levando a um resultado final incorreto. Por exemplo, se contador = 5, e dois processos executam contador++ concorrentemente, o resultado pode ser 6 ao invés de 7, pois ambos podem ler 5 antes de escrever.

2. Regiões Críticas e Exclusão Mútua

Para evitar condições de corrida, precisamos identificar as regiões críticas (critical sections) do código — os trechos que acessam recursos compartilhados. O princípio da exclusão mútua dita que apenas um processo pode executar sua região crítica por vez.

Uma boa solução para exclusão mútua deve satisfazer quatro condições:

  1. Exclusão Mútua: Apenas um processo na região crítica por vez.
  2. Progresso: Se nenhum processo está executando sua região crítica, a decisão sobre quem entra não pode ser adiada indefinidamente.
  3. Espera Limitada: Um processo não pode esperar para sempre para entrar em sua região crítica. Deve haver um limite no tempo de espera.
  4. Neutralidade: Nenhuma suposição deve ser feita sobre a velocidade relativa ou o número de CPUs/processos.

3. Soluções de Software: Algoritmo de Peterson

Uma das primeiras soluções puramente algorítmicas (sem suporte de hardware especial) foi proposta por Gary Peterson em 1981. Ela funciona para dois processos. O algoritmo utiliza duas variáveis: turn (indica de quem é a vez) e um array interested (indica se o processo deseja entrar na região crítica).

#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process) {
    int other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while (turn == process && interested[other] == TRUE);
}

void leave_region(int process) {
    interested[process] = FALSE;
}

A beleza do algoritmo está na variável turn: se ambos os processos desejam entrar, turn garante que apenas um prossiga. O busy waiting (loop while) é uma desvantagem, mas é uma solução elegante que prova que a exclusão mútua é possível sem suporte de hardware dedicado.

4. Soluções com Suporte de Hardware

Sistemas multiprocessadores exigem soluções mais robustas. Desabilitar interrupções (cli/sti no x86) funciona em monoprocessadores, mas é perigoso e ineficiente em sistemas multiprocessados (não afeta outras CPUs).

A abordagem moderna envolve instruções especiais de máquina atômicas, como TSL (Test and Set Lock) ou XCHG (Swap). A instrução TSL lê o valor de uma variável na memória, armazena o valor em um registrador e escreve um valor não-zero na memória, tudo em uma única operação indivisível (atômica).

// Pseudocódigo para TSL
enter_region:
    TSL REGISTER, LOCK        // copia LOCK para REGISTER e seta LOCK para 1
    CMP REGISTER, #0          // LOCK era 0?
    JNE enter_region          // se não, espera (busy waiting)
    RET                       // entrou na região crítica

leave_region:
    MOVE LOCK, #0             // libera o lock
    RET

Embora eficaz, essa abordagem ainda sofre de busy waiting (consumo de CPU) e pode levar a starvation ou deadlock em cenários de inversão de prioridade.

5. Semáforos

O conceito de semáforo foi introduzido por Edsger Dijkstra em 1965. Um semáforo é uma variável inteira que possui duas operações atômicas: down (também chamada de P ou wait) e up (também chamada de V ou signal).

  • Down (P): Se o valor do semáforo é maior que 0, decrementa e continua. Se for 0, o processo é bloqueado e colocado em uma fila de espera.
  • Up (V): Incrementa o valor do semáforo. Se houver processos na fila de espera, um deles é acordado (mudado para o estado de pronto).

A grande vantagem dos semáforos sobre as soluções com busy waiting é que eles não consomem CPU enquanto esperam, pois o processo é bloqueado.

Mutexes: Um semáforo binário (valor 0 ou 1) é frequentemente chamado de mutex (exclusão mútua). Antes de entrar na região crítica, um processo executa down(mutex). Após sair, executa up(mutex).

6. Problemas Clássicos de Concorrência

Diversos problemas clássicos são usados para ilustrar as técnicas de sincronização:

  • Produtor-Consumidor (Bounded Buffer): Um produtor insere itens em um buffer circular limitado, enquanto um consumidor os retira. A solução utiliza um mutex para proteger o buffer e dois semáforos (empty e full) para sincronizar o estado do buffer.
  • Leitores-Escritores (Readers-Writers): Leitores podem acessar um recurso simultaneamente (não o modificam), enquanto escritores precisam de acesso exclusivo. A solução priorizando leitores pode levar à starvation de escritores.
  • Jantar dos Filósofos (Dining Philosophers): Ilustra o problema de deadlock. Cinco filósofos sentam em uma mesa redonda com cinco garfos. Cada filósofo precisa de dois garfos para comer. Se todos pegarem o garfo da esquerda simultaneamente, ninguém conseguirá pegar o da direita, resultando em um deadlock. Soluções incluem usar um semáforo para limitar o número de filósofos na mesa, ou garantir que um filósofo pegue os dois garfos de uma vez só usando um mutex.

7. Monitores e Variáveis de Condição

Para tornar a programação concorrente mais segura e menos propensa a erros (como esquecer de chamar up em um semáforo), foram criadas abstrações de alto nível chamadas monitores. Um monitor é uma estrutura que agrupa dados compartilhados, procedimentos e variáveis de condição. O compilador garante que apenas um processo execute dentro do monitor por vez. wait() em uma variável de condição bloqueia o processo e libera o monitor temporariamente. signal() acorda um processo bloqueado naquela variável.

Conclusão

A concorrência é um tópico central e desafiador em sistemas operacionais modernos. Desde as condições de corrida mais simples até os deadlocks em sistemas complexos, o domínio das primitivas de sincronização (exclusão mútua com desabilitação de interrupções, instruções TSL, semáforos, mutexes e monitores) é fundamental para qualquer profissional da área de computação. O design correto de sistemas concorrentes é essencial para garantir desempenho, corretude e robustez.

FAQ

  • O que é exclusão mútua? É a técnica que garante que apenas um processo ou thread execute em uma região crítica por vez, prevenindo condições de corrida e garantindo a consistência dos dados.
  • O que é um semáforo? Um semáforo é uma variável inteira protegida por operações atômicas (down e up), usada para controlar o acesso a recursos compartilhados. Seu valor representa o número de recursos disponíveis.
  • Qual a diferença entre um semáforo binário e um mutex? Um semáforo binário pode ser "upado" por qualquer processo, enquanto um mutex tem o conceito de propriedade — geralmente o mesmo processo que o adquiriu deve liberá-lo. Mutexes modernos também incluem mecanismos como herança de prioridade para evitar ataques de inversão de prioridade.
  • O que é busy waiting? É uma técnica de espera ocupada onde o processo fica em um loop verificando repetidamente uma condição, consumindo ciclos de CPU. Embora simples, é ineficiente. Semáforos com filas de bloqueio eliminam o busy waiting.
  • O que é um deadlock? Deadlock é uma condição onde um conjunto de processos fica permanentemente bloqueado, cada um esperando por um recurso que está retido por outro processo no mesmo conjunto. É um dos problemas mais difíceis de depurar em sistemas concorrentes.