Pular para o conteúdo principal

Aula 09 — Exclusão Mútua: Abordagens e Algoritmos

Objetivos​

Ao final desta aula você deve ser capaz de:

  • Descrever e avaliar cada abordagem de exclusão mútua (desabilitar interrupções, variáveis lock simples, algoritmos de software, instruções atômicas, mutex).
  • Demonstrar por que uma variável lock simples sem atomicidade não resolve o problema da seção crítica.
  • Explicar a Solução de Peterson e verificar formalmente que ela satisfaz os três requisitos (exclusão mútua, progresso, espera limitada).
  • Definir atomicidade e descrever as instruções test_and_set e compare_and_swap.
  • Comparar busy waiting (spin) com bloqueio real, e indicar quando cada um é preferível.
  • Identificar o requisito que test_and_set simples viola e descrever a solução com array waiting[].

Conteúdo​

Panorama das abordagens​

O problema da seção crítica pode ser abordado em diferentes níveis:

AbordagemNívelExclusãoProgressoEspera Lim.Overhead
Desabilitar int.Hardware✓ (1 CPU)✓✓Paralisa sistema
Var. lock simplesSoftware✗✗✗Spin ineficaz
Solução PetersonSoftware✓✓✓Spin + restr. HW
TAS simplesHardware/HW✓✓✗Spin
TAS + waiting[]Hardware/HW✓✓✓Spin
CASHardware/HW✓✓✓*Spin/lock-free
Mutex (bloqueante)SO/lib✓✓✓Context switch

Abordagem 1: Desabilitar Interrupções​

Em um sistema monoprocessador, a preempção só ocorre via interrupção. Se as interrupções forem desabilitadas durante a seção crítica, nenhuma troca de contexto pode ocorrer — exclusão mútua garantida.

/* Somente leitura — pseudocódigo conceitual */
cli();              /* disable interrupts (instrução privilegiada x86) */
    /* seção crítica */
sti();              /* enable interrupts */

Análise dos três requisitos:

  • Exclusão mútua: ✓ (em sistemas monoprocessador)
  • Progresso: ✓
  • Espera limitada: ✓ (se a SC for finita)

Por que não é suficiente em geral:

  1. Instrução privilegiada: cli/sti são instruções de modo kernel — programas de usuário não podem executá-las. O SO não pode confiar que aplicações as usem corretamente.

  2. Ineficaz em multiprocessador: desabilitar interrupções em uma CPU não impede que outra CPU acesse dados compartilhados simultaneamente. Seria necessário desabilitar em todas as CPUs via IPI (Inter-Processor Interrupt) — latência enorme.

  3. Consequências de falha: se o processo travar dentro da SC com interrupções desabilitadas, o sistema congela completamente (sem timer, sem I/O, sem SO).

  4. Esconde bugs de temporização: programas que dependem de interrupções (timers, drivers) podem falhar silenciosamente.

Uso legítimo: o kernel usa cli/sti (ou equivalentes) em seções extremamente curtas para proteger estruturas internas em sistemas monoprocessador ou para desabilitar interrupções localmente (um núcleo) em SMP — nunca como mecanismo geral de aplicações.

Abordagem 2: Variável Lock Simples (sem atomicidade)​

A ideia intuitiva é usar uma variável compartilhada lock:

/* Somente leitura — tentativa ingênua INCORRETA */
int lock = 0;   /* 0 = livre, 1 = ocupado */

void entrar_sc() {
    while (lock == 1) ;   /* espera */
    lock = 1;             /* adquire */
}

void sair_sc() {
    lock = 0;
}

Por que não funciona:

Tempo  P0                          P1
T0     while(lock == 1): false     
T1     — preempção! —              while(lock == 1): false
T2                                 lock = 1  ← P1 adquire
T3     lock = 1  ← P0 também adquire!
T4     AMBOS NA SEÇÃO CRÍTICA  ← violação de exclusão mútua

A verificação (while) e a atribuição (lock = 1) não são uma operação única e indivisível — o preempção pode ocorrer entre elas.

Diagnóstico: o problema é a ausência de atomicidade. Precisamos de uma operação que teste E modifique sem interrupção entre as duas etapas.

Abordagem 3: Solução de Peterson (revisão aprofundada)​

A Solução de Peterson resolve o problema algoritmicamente para dois processos, sem instrução especial de hardware.

/* Somente leitura — Solução de Peterson para Pi e Pj */
int turn;          /* de quem é a vez: i ou j                    */
bool flag[2];      /* flag[i] = Pi quer entrar na SC             */

/* Código de Pi (Pj é simétrico com i e j trocados) */
do {
    flag[i] = true;         /* "quero entrar"                     */
    turn   = j;             /* "cedo minha vez se houver conflito" */
    while (flag[j] && turn == j)
        ;                   /* spin enquanto Pj quer E é a vez de Pj */

    /* ─── SEÇÃO CRÍTICA ─── */

    flag[i] = false;        /* "terminei, pode entrar"            */

    /* ─── SEÇÃO REMANESCENTE ─── */
} while (true);

Prova formal dos três requisitos​

1. Exclusão mútua: Pi entra na SC somente se flag[j] == false OU turn == i. Como turn só pode ser i ou j (não ambos), se Pi e Pj tentam entrar simultaneamente, turn será o último valor escrito — digamos turn == j (Pj cedeu). Então Pi vê turn == j → loop, Pj vê flag[i] == true && turn == j (falso, pois turn==j, não i?)

Detalhando: se turn == j, Pj executa while(flag[i] && turn == i) — turn é j, não i → turn == i é false → Pj sai do while e entra. Pi executa while(flag[j] && turn == j) — turn é j → turn == j é true e flag[j] é true → Pi permanece no while. ✓

2. Progresso: se nenhum está na SC (flag[j] == false), Pi entra imediatamente (loop: flag[j] && turn == j → false && ... → false). Se Pj está tentando entrar, turn resolverá o empate em favor de um deles. ✓

3. Espera limitada: Pi espera no máximo uma entrada de Pj. Quando Pj sai da SC, ele seta flag[j] = false ou turn = i, liberando Pi. ✓

Limitação em hardware moderno​

Arquiteturas modernas (x86, ARM) reordenam instruções e usam
store buffers — uma escrita pode não ser imediatamente visível
por outro núcleo. A sequência:
    flag[i] = true;   ← pode ser atrasada no store buffer
    turn = j;         ← pode chegar ao outro núcleo antes
quebra a suposição de visibilidade imediata de Peterson.

Solução: adicionar barreiras de memória (memory fences):
    flag[i] = true;
    __sync_synchronize();  /* full memory barrier (GCC) */
    turn = j;

Abordagem 4: Hardware de Sincronização — Instruções Atômicas​

Processadores modernos fornecem instruções que realizam múltiplas operações em memória de forma indivisível — sem possibilidade de interrupção entre as etapas.

test_and_set (TAS)​

/* Somente leitura — semântica atômica de test_and_set */
bool test_and_set(bool *alvo) {
    bool rv = *alvo;   /* lê valor atual  */
    *alvo = true;      /* seta para true  */
    return rv;         /* retorna o antigo */
    /* TUDO ISSO É INDIVISÍVEL — hardware garante */
}

Implementação de EM com TAS (variável lock inicializada em false):

/* Somente leitura — exclusão mútua com TAS */
do {
    while (test_and_set(&lock))
        ;           /* spin: TAS retorna true enquanto lock=true */
    /* ─── SEÇÃO CRÍTICA ─── */
    lock = false;   /* libera — setter de volta para false       */
    /* ─── seção remanescente ─── */
} while (true);

Análise:

  • Exclusão mútua: ✓ — somente o processo que encontrou lock = false obtém o lock (TAS atômico garante que apenas um vê false).
  • Progresso: ✓
  • Espera limitada: ✗ — um processo pode ser "passado na frente" indefinidamente.

TAS com espera limitada — array waiting[]​

Para garantir espera limitada, usamos um array waiting[] para rastrear quem está esperando:

/* Somente leitura — TAS com espera limitada */
bool waiting[n];   /* waiting[i] = true: Pi quer entrar    */
bool lock;         /* inicializado em false                 */

/* Código de Pi */
do {
    waiting[i] = true;
    bool key   = true;
    while (waiting[i] && key)
        key = test_and_set(&lock);   /* tenta adquirir     */
    waiting[i] = false;

    /* ─── SEÇÃO CRÍTICA ─── */

    /* ao sair: procura quem está esperando (ordem cíclica) */
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;

    if (j == i)        /* ninguém esperando — libera lock  */
        lock = false;
    else               /* acorda o próximo na fila cíclica */
        waiting[j] = false;

    /* ─── seção remanescente ─── */
} while (true);

Por que garante espera limitada: ao sair da SC, Pi percorre o array waiting ciclicamente e acorda o primeiro processo esperando. Qualquer processo esperará no máximo n-1 entradas antes de ser atendido.

compare_and_swap (CAS)​

/* Somente leitura — semântica atômica de compare_and_swap */
int compare_and_swap(int *val, int esperado, int novo) {
    int temp = *val;
    if (*val == esperado)
        *val = novo;
    return temp;    /* retorna o valor ANTERIOR */
    /* TUDO ATÔMICO */
}

Uso para EM (lock inicializado em 0):

/* Somente leitura */
do {
    while (compare_and_swap(&lock, 0, 1) != 0)
        ;           /* spin enquanto lock != 0 */
    /* ─── SEÇÃO CRÍTICA ─── */
    lock = 0;
    /* ─── seção remanescente ─── */
} while (true);

CAS é mais poderoso que TAS: permite implementar estruturas lock-free (sem locks) — filas, pilhas, contadores — que não bloqueiam nenhum thread. Na x86-64, CAS é implementado como CMPXCHG (atomicamente com prefixo LOCK).

Atomicidade em C moderno — <stdatomic.h>​

/* Executável — contador atômico sem mutex (C11) */
/* Compile: gcc -o atomic_demo atomic_demo.c -lpthread */
#include <stdatomic.h>
#include <pthread.h>
#include <stdio.h>

#define N_THREADS  8
#define ITER       100000

atomic_long contador = 0;   /* atomic_long: operações são atômicas */

void *incrementa(void *arg) {
    for (int i = 0; i < ITER; i++)
        atomic_fetch_add(&contador, 1);   /* equivale a CAS internamente */
    return NULL;
}

int main(void) {
    pthread_t tids[N_THREADS];
    for (int i = 0; i < N_THREADS; i++)
        pthread_create(&tids[i], NULL, incrementa, NULL);
    for (int i = 0; i < N_THREADS; i++)
        pthread_join(tids[i], NULL);
    printf("Esperado: %ld | Obtido: %ld\n",
           (long)N_THREADS * ITER, (long)contador);
    /* Sempre correto, sem mutex, com menor overhead */
    return 0;
}

Abordagem 5: Lock Mutex (revisão com foco em comparação)​

O mutex combina a atomicidade do TAS/CAS com bloqueio real — em vez de spin, o processo é suspenso e acordado quando o lock fica disponível.

TAS spinlock:                 Mutex bloqueante:
  while(TAS(&lock)) ;           acquire():
  // CPU 100% girando             if (!available) → bloqueia (sleep)
  // Útil se espera < 1µs         available = false
                                release():
                                  available = true
                                  wakeup(próximo na fila)

Quando usar cada um:

SituaçãoRecomendaçãoRazão
Seção crítica < 1µs, multicoreSpinlockEvita overhead de context switch
Seção crítica > 1µsMutex bloqueanteEvita desperdício de CPU
Sistema monoprocessadorMutex bloqueanteSpin nunca libera CPU para quem tem o lock
Kernel Linux (regiões curtíssimas)Spinlock (spin_lock)Não pode dormir em contexto de interrupção
Aplicações de usuárioMutex (pthread_mutex_t)Correto e eficiente para seções variáveis

Visão integrada: cronologia das soluções​

Problema:
  Variável compartilhada → race condition → seção crítica

Solução simplista (errada):
  Variável lock sem atomicidade → não funciona

Solução algorítmica (correta, limitada):
  Peterson → funciona em teoria, pode falhar em hardware moderno

Solução de hardware (correta, com spin):
  TAS/CAS → correto, mas busy waiting (CPU desperdiçada)
  TAS + waiting[] → correto e com espera limitada

Solução de SO (correta, eficiente para longas esperas):
  Mutex bloqueante → correto, sem spin, com context switch

Operações atômicas modernas:
  atomic_t, CAS → lock-free, para contadores e estruturas simples

Exercícios​

Questões dissertativas​

Q1

Por que desabilitar interrupções não é uma solução viável para exclusão mútua em sistemas multiprocessador? Explique em termos de hardware o que precisaria ser feito e por que isso é impraticável.

Q2

Demonstre com um trace de execução específico por que a variável lock simples (sem atomicidade) não garante exclusão mútua.

Q3

Explique a intuição por trás de cada uma das duas variáveis na Solução de Peterson (turn e flag[]). Por que usar apenas uma delas não resolve o problema?

Q4

Defina atomicidade no contexto de operações de memória. Por que test_and_set deve ser implementada em hardware como instrução atômica?

Q5

Por que a implementação simples de TAS não garante espera limitada? Descreva o cenário em que um processo pode esperar indefinidamente.

Q6

Explique a diferença semântica entre test_and_set e compare_and_swap. Em que situação CAS é mais poderoso que TAS?

Q7

Quando é mais eficiente usar um spinlock do que um mutex bloqueante? Justifique em termos de overhead de cada abordagem.

Q8Difícil

Considere a versão de TAS com o array waiting[]. Prove informalmente que ela satisfaz espera limitada.

Q9

Explique o conceito de memory fence (barreira de memória). Por que ela é necessária para que a Solução de Peterson funcione em hardware moderno?

Q10Difícil

Compare as cinco abordagens de exclusão mútua desta aula numa tabela, avaliando: corretude (3 requisitos), tipo de espera, dependência de hardware, e aplicabilidade prática.

Quiz de múltipla escolha​

Quiz10 questões

1. Por que a variável lock simples (while(lock==1); lock=1;) não resolve o problema da seção crítica?

  • a)Porque o compilador pode otimizar o loop e removê-lo
  • b)Porque a verificação e a atribuição são operações separadas — o processo pode ser preemptado entre elas, permitindo que dois processos entrem na SC
  • c)Porque variáveis booleanas não podem ser compartilhadas entre processos
  • d)Porque o sistema operacional não permite acesso direto a variáveis globais
  • e)Porque a instrução while não é suportada em modo kernel

2. Na Solução de Peterson, Pi seta turn=j (e não turn=i) antes de esperar. Qual o propósito dessa atribuição?

  • a)Indica que Pi está executando sua seção crítica
  • b)Sinaliza que Pi terminou e liberou a seção crítica
  • c)Cede a vez para Pj em caso de conflito simultâneo — quem seta turn por último 'perdeu' o empate
  • d)Inicializa a variável turn para um valor neutro
  • e)Incrementa um contador de quantas vezes Pi tentou entrar

3. test_and_set(&lock) é chamado por dois processos simultaneamente em CPUs diferentes. O que a atomicidade do hardware garante?

  • a)Ambos retornam false e ambos obtêm o lock
  • b)Exatamente um vê false (obtém o lock); o outro vê true (não obtém)
  • c)O resultado depende qual CPU é mais rápida
  • d)Ambos bloqueiam até que um deles libere o lock manualmente
  • e)Um deles recebe uma exceção de violação de acesso

4. compare_and_swap(val, 5, 10) é chamado. *val = 7 no momento da chamada. O que retorna e *val é alterado?

  • a)Retorna 5, *val = 10
  • b)Retorna 7, *val = 10
  • c)Retorna 7, *val permanece 7
  • d)Retorna 10, *val = 5
  • e)Retorna 0 (falha)

5. Por que TAS simples viola o requisito de espera limitada?

  • a)Porque TAS pode retornar valores incorretos sob alta carga
  • b)Porque ao liberar o lock (lock=false), qualquer processo em spin pode obtê-lo — sem garantia de ordem, um processo pode ser 'pulado' indefinidamente
  • c)Porque TAS não funciona em sistemas com mais de 2 processos
  • d)Porque TAS não garante exclusão mútua — dois processos podem entrar simultaneamente
  • e)Porque o processo que detém o lock nunca libera voluntariamente

6. Em que situação o spinlock é MAIS eficiente que o mutex bloqueante?

  • a)Quando a seção crítica é longa (> 100ms)
  • b)Em sistemas monoprocessador com apenas 1 núcleo
  • c)Quando a espera esperada é muito curta (< tempo de 2 context switches, ~1-2µs em hardware moderno)
  • d)Quando há muitos processos competindo pelo mesmo lock
  • e)Nunca — o mutex bloqueante é sempre mais eficiente

7. A Solução de Peterson pode falhar em hardware moderno sem barreiras de memória. Qual mecanismo de hardware causa esse problema?

  • a)Cache L1 — pode armazenar valores incorretos
  • b)Store buffer — escritas podem ser adiadas e vistas em ordem diferente por outros núcleos
  • c)Branch predictor — pode executar o código errado
  • d)Out-of-order execution — pode reordenar leituras de memória
  • e)Pipeline stall — impede que escritas sejam completadas a tempo

8. atomic_fetch_add(&x, 1) em C11 é equivalente a qual operação?

  • a)x++ sem garantias de atomicidade
  • b)Uma implementação de x++ usando CAS ou instrução atômica de hardware, garantindo que o incremento é indivisível
  • c)Um mutex que protege x++
  • d)Uma operação que incrementa x apenas se x == 0
  • e)Uma macro que desabilita interrupções antes do incremento

9. Qual dos três requisitos da seção crítica é MAIS difícil de satisfazer com variáveis de turno simples (onde turn alterna P0/P1/P0/P1)?

  • a)Exclusão mútua — dois processos podem entrar ao mesmo tempo
  • b)Progresso — P0 pode estar impedido de entrar mesmo que P1 não queira a SC
  • c)Espera limitada — P0 pode esperar indefinidamente
  • d)Atomicidade — a variável turn não pode ser lida atomicamente
  • e)Corretude — o resultado depende da velocidade dos processos

10. Desabilitar interrupções é uma solução viável para seções críticas dentro do KERNEL Linux. Por quê?

  • a)Porque o kernel nunca usa multiprocessador
  • b)Porque o kernel usa apenas um thread e não precisa de exclusão mútua
  • c)Porque seções curtíssimas de kernel podem desabilitar interrupções localmente em um núcleo para proteger estruturas de dados acessadas apenas por aquele núcleo
  • d)Porque o kernel tem permissão para monopolizar a CPU indefinidamente
  • e)Porque o kernel usa memória ROM que não pode ser modificada por outros processos

Referências​

Principais (essenciais)​

  • SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
    • §5.1 — Antecedentes (race condition, counter++)
    • §5.2 — O Problema da Seção Crítica (3 requisitos)
    • §5.3 — Solução de Peterson
    • §5.4 — Hardware de Sincronização (TAS, CAS, waiting[])
    • §5.5 — Locks Mutex

Aprofundamento (opcionais)​

  • TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016. §2.3.3–2.3.5.
  • HERLIHY, M.; SHAVIT, N. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012. Cap. 2.
  • Linux kernel source — arch/x86/include/asm/atomic.h (implementação de operações atômicas x86).

Recursos Complementares​

Opcional — Vídeos para reforçar os conceitos desta aula.

Thumbnail do vídeo: Critical Section Problem — Process Synchronization21:00
ENOpcional

Critical Section Problem — Process Synchronization

Neso Academy

Condição de corrida, seção crítica e os três requisitos. Cobre §5.1 e §5.2 do Silberschatz.
Thumbnail do vídeo: Operating Systems — Full Course (25h)25:00:00
ENAprofundamento

Operating Systems — Full Course (25h)

freeCodeCamp.org

Para esta aula, foque nos módulos Critical Section Problem, Peterson's Solution e Hardware Synchronization.