Aula 05 — Execução Concorrente: Problemas e Propriedades

Objetivos

Ao final desta aula você deve ser capaz de:

Explicar como o interleaving de instruções causa comportamento não determinístico em programas concorrentes.
Identificar condições de corrida em trechos de código e indicar a variável e o ponto exatos do conflito.
Definir seção crítica e os três requisitos que toda solução válida deve satisfazer: exclusão mútua, progresso e espera limitada.
Analisar a Solução de Peterson e verificar que ela satisfaz os três requisitos.
Descrever as abordagens de hardware — desabilitar interrupções, test_and_set e compare_and_swap — e suas limitações.
Enumerar as quatro condições necessárias para deadlock e identificá-las em cenários concretos.
Distinguir deadlock de starvation, identificando a causa raiz de cada um.

Conteúdo

O problema central da concorrência

Na Aula 03 vimos como expressar paralelismo. Mas executar tarefas concorrentemente sobre dados compartilhados introduz um problema sutil e perigoso: o resultado pode depender da ordem exata em que as instruções são intercaladas pelo escalonador — o interleaving.

Analogia: dois caixas de banco consultam simultaneamente o saldo de uma conta para processar saques. Ambos leem R $1.000,00, ambos subtraem R$ 700,00 e ambos escrevem R $300,00. O saldo final é R$ 300,00 — mas dois saques de R $700,00 deveriam ter deixado R$ −400,00. A conta foi a descoberto sem que nenhum sistema de validação detectasse. Esse é exatamente o problema da condição de corrida.

Interleaving e a condição de corrida

Considere dois processos (Produtor e Consumidor) compartilhando uma variável counter. O Produtor executa counter++ e o Consumidor executa counter--.

Embora pareçam operações atômicas em C, não são — cada uma se expande em três instruções de máquina:

/* counter++ (Produtor) em linguagem de máquina */
R1 = counter         /* lê o valor atual */
R1 = R1 + 1          /* incrementa no registrador */
counter = R1         /* escreve de volta */

/* counter-- (Consumidor) em linguagem de máquina */
R2 = counter
R2 = R2 - 1
counter = R2

Suponha counter = 5. Vejamos um interleaving problemático:

O resultado correto seria counter = 5 (um incremento e um decremento). Mas obtivemos counter = 4 porque o Consumidor leu o valor antes da escrita do Produtor ser concluída.

Definição formal: uma condição de corrida (race condition) ocorre quando múltiplos processos acessam e manipulam dados compartilhados concorrentemente, e o resultado final depende da ordem específica de execução das instruções.

O Problema da Seção Crítica

Para eliminar condições de corrida, é necessário identificar e proteger os trechos de código que acessam dados compartilhados.

Seção Crítica é o segmento de código em que um processo acessa/modifica recursos compartilhados (variáveis, arquivos, tabelas). Dois processos não podem estar em suas seções críticas simultaneamente.

A estrutura geral de um processo com seção crítica:

do {
    [seção de entrada]      /* solicita permissão para entrar */
        seção crítica       /* acessa dados compartilhados    */
    [seção de saída]        /* libera o acesso                */
        seção remanescente  /* resto do processamento         */
} while (verdadeiro);

Os três requisitos de uma solução válida

Toda solução ao problema da seção crítica deve satisfazer simultaneamente:

Requisito	Definição	O que viola?
1. Exclusão mútua	Se Pi está na SC, nenhum outro Pj pode estar na SC	Permite corrida de dados
2. Progresso	Se nenhum processo está na SC e há processos querendo entrar, a decisão de quem entra não pode ser adiada indefinidamente	Bloqueia progresso sem necessidade
3. Espera limitada	Existe um limite no número de vezes que outros processos entram na SC após um processo fazer sua solicitação	Permite starvation

Abordagem ingênua: desabilitar interrupções

A forma mais direta de garantir exclusão mútua em um único processador é desabilitar interrupções enquanto a seção crítica é executada — sem interrupção, não há preempção, não há interleaving.

/* Somente leitura — pseudocódigo conceitual */
desabilitar_interrupcoes();
    /* seção crítica */
habilitar_interrupcoes();

Problemas:

Em sistemas multiprocessador: desabilitar interrupções em uma CPU não impede que outra CPU acesse os dados simultaneamente. Seria necessário desabilitar em todas — operação custosa e que paralisa o sistema.
Dá ao processo de usuário controle sobre o hardware — é uma instrução privilegiada reservada ao kernel.
Se o processo travar dentro da SC, as interrupções nunca são reabilitadas — o sistema congela.

Uso legítimo: o próprio kernel usa essa técnica em seções curtíssimas para proteger estruturas internas em sistemas monoprocessador.

Solução de Peterson (software, 2 processos)

A Solução de Peterson resolve o problema da seção crítica para dois processos usando apenas duas variáveis compartilhadas — sem suporte de hardware especial.

/* Somente leitura — variáveis compartilhadas */
int turn;         /* de quem é a vez: 0 ou 1              */
bool flag[2];     /* flag[i]=true: Pi quer entrar na SC   */

Estrutura para o processo Pi (o outro é Pj, j = 1 − i):

/* Somente leitura — estrutura do processo Pi */
do {
    flag[i] = true;          /* "eu quero entrar"                */
    turn   = j;              /* "mas deixo o outro ir primeiro"  */
    while (flag[j] && turn == j)
        ;                    /* espera enquanto Pj quer e é a vez de Pj */

    /* ──── seção crítica ──── */

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

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

Verificando os três requisitos:

Exclusão mútua: Pi entra na SC somente se flag[j] == false OU turn == i. Como turn tem valor único (i ou j), apenas um processo passa pelo while ao mesmo tempo. ✓
Progresso: se nenhum está na SC (flag[j] == false), Pi entra imediatamente. Se Pj está tentando entrar, turn determina quem passa primeiro. ✓
Espera limitada: Pi espera no máximo uma entrada de Pj. Depois que Pj sai da SC, ele seta flag[j] = false ou turn = i, liberando Pi. ✓

Limitação moderna: arquiteturas com reordenação de instruções (out-of-order execution) e caches com coerência relaxada podem quebrar a suposição de que escritas são visíveis imediatamente por outros processadores. A solução de Peterson funciona teoricamente, mas pode falhar em hardware moderno sem barreiras de memória (memory fences).

Hardware de sincronização: instruções atômicas

O hardware moderno fornece instruções que executam atomicamente — sem possibilidade de interrupção a meio caminho.

test_and_set

/* Somente leitura — semântica de test_and_set */
boolean test_and_set(boolean *alvo) {
    boolean rv = *alvo;   /* lê o valor atual        */
    *alvo = true;         /* seta para true           */
    return rv;            /* retorna o valor antigo   */
}
/* Toda essa operação é atômica — indivisível */

Uso para exclusão mútua (variável lock inicializada com false):

/* Somente leitura — exclusão mútua com test_and_set */
do {
    while (test_and_set(&lock))
        ;              /* spin: aguarda lock ficar false   */
    /* ── seção crítica ── */
    lock = false;      /* libera o lock                    */
    /* ── seção remanescente ── */
} while (true);

Problema: não garante espera limitada — um processo pode ficar em spin indefinidamente se outros processos sempre conseguem o lock antes.

compare_and_swap (CAS)

/* Somente leitura — semântica de compare_and_swap */
int compare_and_swap(int *valor, int esperado, int novo_valor) {
    int temp = *valor;
    if (*valor == esperado)
        *valor = novo_valor;
    return temp;
}
/* Atômica: lê, compara e escreve como unidade indivisível */

CAS é a instrução base de muitas estruturas lock-free modernas (filas, pilhas, contadores atômicos). Na arquitetura x86-64 é implementada como CMPXCHG.

Resumo das abordagens:

Abordagem	Exclusão mútua	Progresso	Espera limitada	Overhead
Desabilitar interrupções	✓ (monoproc.)	✓	✓	Bloqueia sistema
Solução de Peterson	✓	✓	✓	Spin + restrição hardware moderno
test_and_set simples	✓	✓	✗	Spin (busy waiting)
test_and_set + waiting[]	✓	✓	✓	Spin
compare_and_swap	✓	✓	✓*	Spin / base para lock-free

Deadlock

Quando múltiplos processos competem por recursos e cada um retém recursos que o outro precisa, o sistema pode entrar em impasse total.

Definição: um conjunto de processos está em deadlock quando cada processo do conjunto aguarda por um evento que somente outro processo do mesmo conjunto pode causar — tipicamente a liberação de um recurso.

Analogia: dois trens em uma linha de mão única se encontram cara a cara. Nenhum pode recuar porque o outro está bloqueando o desvio. Ambos esperam indefinidamente.

As quatro condições necessárias (Coffman, 1971)

Para que ocorra deadlock, todas as quatro condições devem estar presentes simultaneamente:

Condição	Descrição	Como quebrar
1. Exclusão mútua	Pelo menos um recurso é não-compartilhável	Tornar recurso compartilhável (nem sempre possível)
2. Retenção e espera	Processo retém ≥ 1 recurso e aguarda outros	Solicitar todos os recursos de uma vez (ou liberar antes de pedir novos)
3. Inexistência de preempção	Recurso só é liberado voluntariamente pelo processo que o retém	Preemptar recursos forçadamente
4. Espera circular	Há uma cadeia circular P0→P1→…→Pn→P0 de espera por recursos	Impor ordem total na solicitação de recursos

Exemplo clássico com mutexes

/* Somente leitura — cenário de deadlock com pthreads */
/* Thread 1                      Thread 2             */
pthread_mutex_lock(&mutex_A);    pthread_mutex_lock(&mutex_B);
pthread_mutex_lock(&mutex_B);    pthread_mutex_lock(&mutex_A);
/* trabalho */                   /* trabalho */
pthread_mutex_unlock(&mutex_B);  pthread_mutex_unlock(&mutex_A);
pthread_mutex_unlock(&mutex_A);  pthread_mutex_unlock(&mutex_B);

Se Thread 1 adquire mutex_A e Thread 2 adquire mutex_B antes que qualquer uma tente o segundo lock, temos deadlock:

As quatro condições estão presentes: exclusão mútua (mutexes), retenção e espera, sem preempção, espera circular.

Solução simples: impor ordem global — sempre adquirir locks na mesma sequência (ex.: sempre A antes de B):

/* Somente leitura — solução: ordenação global de locks */
/* Thread 1                      Thread 2 (corrigida)   */
pthread_mutex_lock(&mutex_A);    pthread_mutex_lock(&mutex_A);
pthread_mutex_lock(&mutex_B);    pthread_mutex_lock(&mutex_B);

Com a mesma ordem, não há espera circular — logo, deadlock impossível.

Starvation

Starvation (inanição) ocorre quando um processo nunca consegue os recursos de que precisa, mesmo sem deadlock — porque outros processos continuamente têm prioridade sobre ele.

Diferença fundamental:

Característica	Deadlock	Starvation
Causa	Espera circular entre processos	Política injusta de escalonamento/sincronização
O processo está bloqueado?	Sim — todos do ciclo	Sim — mas por falta de acesso, não por ciclo
Outros progridem?	Não — todos do conjunto travam	Sim — outros continuam normalmente
O sistema para?	Parcialmente (processos afetados)	Não — apenas o processo faminto para
Solução típica	Quebrar uma das 4 condições	Aging (envelhecimento de prioridade)

Analogia de starvation: numa fila de banco com prioridade VIP, um cliente comum que chega e sempre encontra clientes VIP na frente nunca é atendido — mesmo que o banco esteja funcionando normalmente.

Aging é a técnica clássica de prevenção: aumentar progressivamente a prioridade de processos que esperam há muito tempo, garantindo que eventualmente sejam atendidos.

Visão geral dos problemas da concorrência

Exercícios

Questões dissertativas

Explique com um exemplo concreto por que counter++ não é uma operação atômica em linguagem de máquina. Mostre o interleaving que resulta em um valor incorreto de counter quando dois processos executam counter++ concorrentemente com counter = 10.

Enuncie os três requisitos de uma solução válida ao problema da seção crítica. Para cada requisito, dê um exemplo de situação que violaria somente aquele requisito.

Na Solução de Peterson, explique o papel de cada variável (turn e flag[]). O que acontece se apenas uma delas for usada — apenas turn ou apenas flag[]?

Explique a semântica de test_and_set. Por que ela deve ser atômica? Mostre como usá-la para implementar exclusão mútua simples.

Enuncie as quatro condições necessárias para deadlock. Para o exemplo abaixo com dois threads e dois mutexes, identifique qual condição cada elemento do cenário representa: Thread A: lock(M1) → lock(M2) Thread B: lock(M2) → lock(M1)

Qual a diferença entre deadlock e starvation? Um processo em starvation está em deadlock? Dê um exemplo de starvation que não envolve deadlock.

Por que desabilitar interrupções não é uma solução adequada para exclusão mútua em sistemas multiprocessador? Em que contexto essa abordagem ainda é usada legitimamente?

Analise o seguinte trecho e diga se há condição de corrida. Se sim, identifique o recurso compartilhado, o ponto exato do conflito e proponha uma correção conceitual. int saldo = 1000; void saque(int valor) { if (saldo >= valor) saldo -= valor; }

O que é busy waiting (espera ocupada)? Qual a principal vantagem e a principal desvantagem em relação a uma solução que bloqueia o processo?

Q10Difícil

Suponha três processos P1, P2, P3 e três recursos R1, R2, R3 (um de cada). P1 tem R1 e pede R2; P2 tem R2 e pede R3; P3 tem R3 e pede R1. Há deadlock? Justifique identificando as quatro condições de Coffman.

Quiz de múltipla escolha

Quiz10 questões

1. Dois processos executam concorrentemente 'x++' sobre uma variável compartilhada x=5. Qual é o conjunto de todos os resultados POSSÍVEIS de x após ambos terminarem?

a)Apenas 7 — a soma de dois incrementos
b)Apenas 6 — cada incremento adiciona 1
c)5 ou 6 — dependendo do interleaving
d)6 ou 7 — dependendo do interleaving
e)5, 6 ou 7 — dependendo do interleaving

2. Qual dos três requisitos da seção crítica é violado quando um processo de baixa prioridade nunca consegue entrar na seção crítica porque processos de alta prioridade sempre são favorecidos?

a)Exclusão mútua — dois processos entram simultaneamente
b)Progresso — nenhum processo consegue entrar
c)Espera limitada — não há limite para quantas vezes outros entram antes do processo faminto
d)Atomicidade — as operações não são indivisíveis
e)Consistência — os dados ficam corrompidos

3. Na Solução de Peterson, para o processo Pi, qual é o propósito da atribuição 'turn = j' (e não 'turn = i') antes do loop de espera?

a)Indica que é a vez de Pi entrar na seção crítica
b)Sinaliza que Pi já terminou sua seção crítica
c)Cede educadamente a vez para Pj, garantindo que Pj possa entrar se quiser
d)Bloqueia Pj de entrar enquanto Pi está esperando
e)Inicializa o estado compartilhado para zero

4. Por que test_and_set deve ser implementada como instrução atômica de hardware e não em software?

a)Porque software não pode executar operações booleanas
b)Porque qualquer implementação em software seria muito lenta
c)Porque a implementação em software sofre a mesma condição de corrida que se tenta resolver — dois processos poderiam ambos ler false antes de qualquer um setar true
d)Porque o sistema operacional não permite acesso a variáveis booleanas em modo usuário
e)Porque a operação requer acesso direto ao barramento de memória

5. Qual das quatro condições de Coffman é a mais fácil de quebrar na prática para prevenir deadlocks em sistemas de banco de dados?

a)Exclusão mútua — usar recursos compartilhados sempre que possível
b)Retenção e espera — exigir que processos solicitem todos os recursos de uma vez antes de iniciar
c)Inexistência de preempção — o sistema operacional nunca pode interromper processos
d)Espera circular — só é possível quebrar em sistemas distribuídos
e)Nenhuma condição pode ser quebrada na prática

6. Um processo P está em busy waiting num spinlock há 10 segundos. O processo Q, que detém o lock, está bloqueado aguardando uma operação de E/S. O que está ocorrendo?

a)Deadlock — P e Q se bloqueiam mutuamente
b)Starvation — P nunca conseguirá o lock
c)Livelock — ambos mudam de estado continuamente sem progredir
d)Uma situação normal de espera — P receberá o lock quando Q terminar a E/S
e)Condição de corrida — P e Q acessam o lock simultaneamente

7. Compare_and_swap(val, esperado, novo) é usada numa instrução: CAS(&x, 5, 10). Se x=5, qual o resultado? Se x=3, qual o resultado?

a)x=5: x vira 10, retorna 5. x=3: x permanece 3, retorna 3
b)x=5: x vira 10, retorna 10. x=3: x vira 10, retorna 3
c)x=5: x permanece 5, retorna 10. x=3: x vira 10, retorna 3
d)x=5: x vira 5, retorna 10. x=3: x permanece 3, retorna 10
e)Ambos os casos: x vira 10, retorna o valor antigo

8. Qual afirmação sobre a diferença entre deadlock e starvation está CORRETA?

a)No deadlock, todos os processos progridem lentamente; na starvation, nenhum progride
b)No deadlock, um conjunto de processos fica bloqueado em espera circular; na starvation, um processo específico nunca recebe o recurso por política injusta
c)Starvation é uma forma mais grave de deadlock, onde o processo é eliminado
d)Deadlock ocorre apenas com recursos físicos; starvation ocorre apenas com recursos lógicos
e)Ambos podem ser resolvidos somente desabilitando interrupções

9. Qual é a principal limitação da Solução de Peterson em hardware moderno?

a)Funciona apenas para mais de dois processos
b)Requer suporte de hardware especial como test_and_set
c)Arquiteturas modernas podem reordenar instruções ou usar caches inconsistentes, quebrando as suposições sobre visibilidade imediata de escritas
d)Viola o requisito de exclusão mútua em qualquer cenário
e)Não pode ser implementada em linguagem C — requer Assembly

10. Uma solução para exclusão mútua usa busy waiting. Num sistema com apenas 1 núcleo de CPU, que problema específico pode ocorrer?

a)Nenhum — busy waiting é sempre eficiente em sistemas monoprocessador
b)O processo em spin pode monopolizar a CPU e impedir que o processo que detém o lock receba tempo de CPU para liberá-lo
c)O processo em spin libera o lock automaticamente após um timeout
d)O sistema operacional detecta o spin e força a liberação do lock
e)O processo em spin é automaticamente migrado para um segundo núcleo

Referências

Principais (essenciais)

SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
- Cap. 5 — Sincronização de Processos: §5.1 (antecedentes), §5.2 (seção crítica), §5.3 (Peterson), §5.4 (hardware)
- Cap. 7 — Deadlocks: §7.1 (modelo), §7.2 (caracterização e 4 condições)

Aprofundamento (opcionais)

TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016. Cap. 2.3 — Comunicação entre processos.
STALLINGS, W. Operating Systems. 9. ed. Pearson, 2018. Cap. 5 — Concorrência: Exclusão mútua e sincronização.
COFFMAN Jr., E. G. et al. "System Deadlocks." ACM Computing Surveys, v. 3, n. 2, 1971. (artigo original das 4 condições)

Recursos Complementares

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

Thumbnail do vídeo: Process Synchronization — Critical Section Problem

21:00

ENOpcional

Process Synchronization — Critical Section Problem

Neso Academy

Condição de corrida com o exemplo do contador produtor-consumidor, estrutura da seção crítica e os três requisitos. Alinhado ao §5.1–5.2 do Silberschatz.

Thumbnail do vídeo: Operating Systems: Crash Course Computer Science #18

11:43

ENOpcional

Operating Systems: Crash Course Computer Science #18

CrashCourse

Revisão compacta das responsabilidades do SO e de conceitos que levam à necessidade de sincronização e controle de concorrência.

Thumbnail do vídeo: Introduction to Operating System | Full Course for Beginners

2:11:13

ENAprofundamento

Introduction to Operating System | Full Course for Beginners

Mike Murphy Co

Curso completo para consolidar sincronização, seção crítica, deadlock e escalonamento em um único material.

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 de Process Synchronization e Critical Section Problem dentro do curso completo.

Objetivos​

Conteúdo​

O problema central da concorrência​

Interleaving e a condição de corrida​

O Problema da Seção Crítica​

Os três requisitos de uma solução válida​

Abordagem ingênua: desabilitar interrupções​

Solução de Peterson (software, 2 processos)​

Hardware de sincronização: instruções atômicas​

test_and_set​

compare_and_swap (CAS)​

Deadlock​

As quatro condições necessárias (Coffman, 1971)​

Exemplo clássico com mutexes​

Starvation​

Visão geral dos problemas da concorrência​

Exercícios​

Questões dissertativas​

Quiz de múltipla escolha​

Referências​

Principais (essenciais)​

Aprofundamento (opcionais)​

Recursos Complementares​