[23]. Relacione as propostas para alcançar exclusão mútua. Faça um breve comentário a respeito de cada proposta.

Passo 1

O enunciado pede que eu relacione propostas para alcançar exclusão mútua e faça um breve comentário sobre cada uma. Vou listar primeiro as propostas que vou relacionar (essas são as técnicas clássicas que aparecem em provas e em aulas de Sistemas Operacionais/Concorrência):
  • Desabilitar interrupções
  • Test-and-set / spinlocks
  • Compare-and-swap / outras instruções atômicas (fetch-and-add, swap)
  • Algoritmo de Dekker
  • Algoritmo de Peterson
  • Algoritmo bakery (de Lamport)
  • Semáforos (operações P e V)
  • Monitores (com variáveis de condição)
  • Passagem de mensagens (server / processo guardião)
  • Memória transacional (Transactional Memory)
No resto dos passos eu explico cada proposta, como funciona, vantagens e desvantagens e quando é adequada. Não vou resolver nada ainda — só listei o que o enunciado pede.

Passo 2

Conceitos-chave (o que se espera alcançar com qualquer proposta). Antes de ver propostas, é útil saber três requisitos que uma solução de exclusão mútua deve procurar satisfazer:
  • Mutual exclusion: garantir que, a qualquer tempo, no máximo um processo esteja na seção crítica (recurso compartilhado).
  • Progress (progresso): se nenhum processo está na seção crítica e há processos querendo entrar, algum processo deve conseguir entrar — sem bloqueio indefinido pelo sistema.
  • Bounded waiting (espera limitada): existe um limite (em número de entradas de outros processos) caso um processo esteja tentando entrar; evita fome (starvation).
Vou usar esses critérios para comentar cada proposta.

Passo 3

Desabilitar interrupções
  • Ideia: quando um processo quer entrar na seção crítica, desabilita as interrupções do processador; ao sair, reabilita-as.
  • Como funciona: em um uniprocessador, ao desabilitar interrupções nenhum contexto switch ocorre, então nenhum outro processo roda e a exclusão é garantida.
  • Vantagens: muito simples; fácil de implementar; garante exclusão em uniprocessadores.
  • Desvantagens: não escala para multiprocessadores (cada CPU tem suas interrupções); prejudica latência do sistema (interrupções essenciais ficam bloqueadas); só código no kernel pode fazer isso (usuário não); quebra progresso se o processo travar com interrupções desabilitadas.
  • Quando usar: técnicas de curto trecho em kernel de uniprocessador; não é solução geral para sistemas multiprocessador ou para código de usuário.

Passo 4

Test-and-set / spinlocks (espera ativa)
  • Ideia: usar uma operação atômica de hardware que testa um valor e o escreve simultaneamente; exemplo: \text{test\_and\_set}(lock) retorna o valor antigo e coloca lock := 1.
  • Como funciona (pseudoconceito): o processo faz while(test_and_set(lock)) { /* busy-wait */ } — entra na seção crítica quando a chamada retorna 0.
  • Vantagens: simples; funciona em multiprocessadores se a instrução for atômica; baixo overhead quando a seção crítica é curta.
  • Desvantagens: busy-wait (consume CPU enquanto espera); não é adequado quando espera pode ser longa; pode causar tráfego de cache e degradação em muitos processadores; possibilidade de inanição se scheduling for desfavorável.
  • Quando usar: locks de baixa latência (spinlocks) para seções críticas curtas, especialmente em kernels ou em SMP quando espera é muito curta.

Passo 5

Compare-and-swap / outras instruções atômicas (CAS, fetch-and-add, swap)
  • Ideia: instruções atômicas mais poderosas, por exemplo \text{CAS}(addr, expected, new) que troca addr por new somente se o valor atual for expected.
  • Como funciona: algoritmos lock-free e wait-free usam \text{CAS} para implementar estruturas seguras sem locks tradicionais.
  • Vantagens: permite construir soluções lock-free, que evitam deadlock e podem reduzir latência; útil em ambientes multi-core.
  • Desvantagens: lógica mais complexa; ainda pode haver contenda e retrys (retry loops); não resolve fairness por si só (pode causar starvation).
  • Quando usar: implementações de alto desempenho de estruturas concorrentes (filas, pilhas) e locks sem bloqueio.

Passo 6

Algoritmos de software para dois processos: Dekker e Peterson
  • Dekker
    • Ideia: usar variáveis compartilhadas e turnos para coordenar dois processos sem instruções atômicas.
    • Como funciona (resumo): combina flags de interesse e uma variável indicando o turno; garante exclusão e evita fome se implementado corretamente.
    • Vantagens: puramente software (não precisa de instruções atômicas); histórico importante.
    • Desvantagens: complexo de entender; difícil de generalizar para n>2; sensível a reorderings de compilador/CPU (necessita garantir memória sequencial consistente).
  • Peterson
    • Ideia: solução elegante para dois processos com duas variáveis: interesse[i] e turn.
    • Vantagens: simples, provável de provar corretude para dois processos; satisfaz bounded waiting.
    • Desvantagens: como Dekker, não escala bem para muitos processos; também sensível a otimizações/reorderings sem barreiras de memória; depende de visibilidade imediata das escritas.
  • Quando usar: principalmente didático — raramente usados em sistemas reais devido a problemas com arquiteturas modernas e escalabilidade.

Passo 7

Algoritmo Bakery (Lamport) — solução para n processos
  • Ideia: cada processo pega um número (como em uma padaria: “take a number”); a ordem por número determina quem entra.
  • Como funciona (resumo): ao querer entrar, processo escolhe um número maior que todos; o menor número tem prioridade; empates quebrados por id do processo.
  • Vantagens: solução puramente de software para n processos; provê fairness (ordem FCFS) e bounded waiting.
  • Desvantagens: overhead (leitura/escrita de muitos valores), custo de múltiplas leituras para decidir o número; sensível a custos de memória em sistemas com muitos núcleos; também requer coerência de memória.
  • Quando usar: importante conceitualmente e em estudos teóricos; raramente usado em produções por custo/complexidade.

Passo 8

Semáforos (Dijkstra) — P (wait) e V (signal)
  • Ideia: abstração que mantém um contador; operações atômicas P decrementam e bloqueiam se zero; V incrementa e acorda espera.
  • Como funciona: semáforo binário (contador 0/1) implementa mutex bloqueante; semáforos contadores controlam acesso a múltiplas instâncias de recurso.
  • Vantagens: permite bloqueio (sleep) em vez de busy-wait, economizando CPU; general e amplamente usado; pode garantir ausência de busy-wait quando implementado com filas de espera.
  • Desvantagens: programação com semáforos pode ser sujeita a erros (deadlocks, ordem errada de sinais); não encapsula invariantes (difícil de modularizar).
  • Quando usar: em sistemas usuais para sincronização entre threads/processos; base para muitas primitivas de alto nível.

Passo 9

Monitores (primitiva de alto nível)
  • Ideia: encapsular estado compartilhado e operações protegidas; linguagem fornece mutex implícito e variáveis de condição.
  • Como funciona: só uma thread executa procedimentos do monitor por vez; variáveis de condição permitem esperar/sinalizar com filas de espera.
  • Vantagens: abstração segura e mais estruturada que semáforos; reduz riscos de uso incorreto; facilita modularidade e correção.
  • Desvantagens: requer suporte de linguagem ou runtime; sem cuidado, ainda pode haver deadlocks por ordem de chamadas.
  • Quando usar: preferível em projetos com suporte de linguagem (ex.: Java synchronized + wait/notify, ou monitores em linguagens concorrentes).

Passo 10

Passagem de mensagens / servidor guardião
  • Ideia: colocar o recurso dentro de um processo/servidor; outros processos pedem acesso via mensagens; servidor sequencia pedidos e concede acesso.
  • Como funciona: pedido → fila no servidor → servidor atende um por vez → responde; exclusão garantida porque único servidor manipula recurso.
  • Vantagens: boa para sistemas distribuídos; evita compartilhamento de memória; natural quando comunicação já existe.
  • Desvantagens: overhead de comunicação; latência maior; single point of failure no servidor (pode ser replicado com protocolos mais complexos).
  • Quando usar: sistemas distribuídos ou arquiteturas orientadas a mensagens (ex.: microserviços, actors).

Passo 11

Memória Transacional (Transactional Memory)
  • Ideia: tratar uma sequência de operações como uma transação; executar otimista em paralelo e validar no commit; em caso de conflito, aborta e refaz.
  • Como funciona: hardware ou software detecta conflitos nas leituras/escritas; commits são atômicos; evita locks explícitos.
  • Vantagens: programação mais simples para certas cargas; evita deadlocks; bom para seções críticas complexas.
  • Desvantagens: overhead de rollback, não ideal para seções com E/S; ainda imaturo em alguns contextos; conflitos frequentes causam degradação.
  • Quando usar: pesquisa e algumas implementações práticas em linguagens/runtimes com suporte a TM; promissor para paralelismo de memória compartilhada.

Passo 12

Resumo comparativo rápido (para você ter claro na prova)
  • Hardware vs Software: instruções atômicas ( \text{test\_and\_set}, \text{CAS}) dependem de suporte HW; algoritmos puros (Peterson, bakery) são só software.
  • Busy-wait vs Blocking: spinlocks e algoritmos de espera ativa gastam CPU; semáforos/monitores/passing-messages bloqueiam (sleeps) e liberam CPU.
  • Uniprocessador vs Multiprocessador: desabilitar interrupções funciona em uniprocessador; spinlocks/atomic ops/monitores funcionam em multiprocessador (se bem implementados).
  • Escalabilidade e fairness: bakery oferece fairness para n, Peterson funciona bem só para dois; CAS permite lock-free mas fairness não é garantida automaticamente.
  • Facilidade de uso: monitores > semáforos > locks atômicos > algoritmos puros (Dekker/Peterson são didáticos).

Resposta

Desabilitar interrupções — Solução simples para uniprocessadores: garante exclusão ao impedir trocas de contexto, mas bloqueia interrupções (não escala para SMP) e não é adequada para código de usuário nem para espera longa.
Test-and-set / spinlocks — Usa instrução atômica de hardware com espera ativa (busy-wait); simples e rápido para seções críticas muito curtas em SMP, mas consome CPU e causa contenda de cache quando a espera é longa.
Compare-and-swap (CAS) / fetch-and-add — Instruções atômicas mais poderosas que permitem construir algoritmos lock-free; oferecem alta concorrência e baixa latência quando bem usadas, porém são mais complexas e podem levar a retries e starvation.
Dekker — Algoritmo puramente em software para dois processos usando flags e turno; histórico e provável de provar corretude, mas complexo e não facilmente generalizável para n>2; sensível a reordenações de memória.
Peterson — Solução simples e elegante para dois processos usando variáveis de interesse e turno; satisfaz exclusão e bounded waiting em teoria, mas não é prática em arquiteturas modernas sem barreiras de memória e não escala para muitos processos.
Bakery (Lamport) — Solução puramente em software para n processos que usa numeração estilo “pegar senha”; provê fairness (FCFS) e bounded waiting, mas tem overhead de leituras/escritas e custo em sistemas com muitos núcleos.
Semáforos (operações P e V) — Abstração clássica que permite bloqueio em vez de busy-wait; versátil (binário para mutex, contador para múltiplas instâncias), evite erros de uso (deadlocks) mas é eficiente e muito usado em SOs.
Monitores — Abstração de alto nível que encapsula estado e sincronização (mutex implícito + variáveis de condição); mais seguro e modular que semáforos, requer suporte de linguagem/runtime.
Passagem de mensagens (servidor guardião) — Colocar recurso em um servidor e acessar por mensagens garante exclusão sequencial; ótimo para sistemas distribuídos e modelos sem memória compartilhada, mas tem overhead de comunicação e latência.
Memória transacional — Abordagem otimista que executa transações concorrentes e valida no commit, evitando locks explícitos; simplifica programação em alguns casos, mas tem overhead de rollback e não é adequada para todas as cargas.

Exercícios relacionados