[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
e ) - 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:
retorna o valor antigo e coloca . - 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
que troca por somente se o valor atual for . - Como funciona: algoritmos lock-free e wait-free usam
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
; 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]eturn. - 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.
- Ideia: solução elegante para dois processos com duas variáveis:
- 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
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
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) —
(wait) e
(signal)
- Ideia: abstração que mantém um contador; operações atômicas
decrementam e bloqueiam se zero; 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 (
, ) 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
, 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
; 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
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
e
) — 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.