❧ Impasses (Deadlocks) ❧

Introdução7.1

Imagine uma ponte estreita de mão única. Um carro entra pela esquerda, outro pela direita, e os dois se encontram no meio. Cada motorista já ocupa um pedaço da ponte e precisa que o outro recue para terminar a travessia. Nenhum cede. O resultado não é lentidão: é paralisação estrutural.

Em Computação, esse tipo de bloqueio permanente recebe o nome de impasse ou deadlock. Ele ocorre quando um conjunto de processos ou threads fica preso porque cada membro do grupo espera por um evento que apenas outro membro do mesmo grupo pode produzir.

Nas aulas anteriores, estudamos como processos competem por CPU e como coordenam o acesso a recursos compartilhados usando mutexes e semáforos. Agora veremos o lado sombrio dessa sincronização: quando o controle de acesso está correto do ponto de vista da exclusão mútua, mas o sistema mesmo assim para de progredir.

Sistemas Operacionais Modernos, de Tanenbaum, nos fornece a formulação clássica:

Figura: A tem a impressora e quer o scanner; B tem o scanner e quer a impressora. Sem intervenção externa, ninguém termina.

Outra imagem que representa bem nosso problema é:

O que está em disputa: recursos7.2

Deadlocks existem porque processos disputam recursos. Um recurso pode ser físico, como impressora, disco ou GPU, ou lógico, como mutexes, semáforos, conexões, páginas, buffers ou linhas de uma tabela em um banco de dados.

Deadlocks aparecem quase sempre com recursos não preemptíveis, porque o sistema operacional não pode simplesmente arrancar o recurso do processo e seguir como se nada tivesse acontecido.

O uso de um recurso costuma seguir três passos:

1. O processo solicita o recurso.
2. O processo usa o recurso enquanto ele está alocado.
3. O processo libera o recurso para o restante do sistema.

O problema nasce quando diferentes processos fazem esse ciclo em ordens incompatíveis.

Deadlock vs. Starvation vs. Livelock7.2.1

Esses termos aparecem juntos, mas não significam a mesma coisa.

Seguro, inseguro e em deadlock7.2.2

Essa distinção é central para entender o Algoritmo do Banqueiro.

As Quatro Condições de Coffman7.3

Em 1971, Coffman mostrou que um impasse só pode existir se quatro condições forem verdadeiras ao mesmo tempo. Se quebrarmos qualquer uma delas, não há deadlock.

1. Exclusão Mútua: um recurso só pode ser usado por um processo por vez.
2. Posse e Espera: um processo retém recursos já obtidos enquanto espera por novos.
3. Não Preempção: o recurso não pode ser retirado à força.
4. Espera Circular: existe um ciclo de dependência entre processos e recursos.

graph TD
    A[Exclusao Mutua] --> D[Deadlock]
    B[Posse e Espera] --> D
    C[Nao Preempcao] --> D
    E[Espera Circular] --> D

graph TD
    A[Exclusao Mutua] --> D[Deadlock]
    B[Posse e Espera] --> D
    C[Nao Preempcao] --> D
    E[Espera Circular] --> D

Deadlock não é "qualquer espera longa". Ele exige a presença simultânea das quatro condições.

Exemplo prático: duas threads que travam para sempre7.4

O exemplo mais importante para os alunos é o erro clássico de adquirir locks em ordens opostas.

Exemplo 1: Deadlock em C com pthread_mutex_t7.4.0.1

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void* threadA(void* arg) {
    pthread_mutex_lock(&lock1);
    printf("A: pegou lock1\n");
    sleep(1); // aumenta a chance de interleaving ruim

    printf("A: tentando pegar lock2\n");
    pthread_mutex_lock(&lock2);

    printf("A: pegou lock2\n");
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

void* threadB(void* arg) {
    pthread_mutex_lock(&lock2);
    printf("B: pegou lock2\n");
    sleep(1);

    printf("B: tentando pegar lock1\n");
    pthread_mutex_lock(&lock1);

    printf("B: pegou lock1\n");
    pthread_mutex_unlock(&lock1);
    pthread_mutex_unlock(&lock2);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, threadA, NULL);
    pthread_create(&t2, NULL, threadB, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    return 0;
}

sequenceDiagram
    participant A as Thread A
    participant L1 as lock1
    participant B as Thread B
    participant L2 as lock2
    A->>L1: lock(lock1)
    B->>L2: lock(lock2)
    A->>L2: espera por lock2
    B->>L1: espera por lock1
    Note over A,L2: Espera circular permanente

sequenceDiagram
    participant A as Thread A
    participant L1 as lock1
    participant B as Thread B
    participant L2 as lock2
    A->>L1: lock(lock1)
    B->>L2: lock(lock2)
    A->>L2: espera por lock2
    B->>L1: espera por lock1
    Note over A,L2: Espera circular permanente

As quatro condições de Coffman aparecem nitidamente:

1. lock1 e lock2 são exclusivos.
2. A segura lock1 e espera lock2; B faz o inverso.
3. O sistema não rouba o mutex à força.
4. A espera B, e B espera A.

Modelagem com grafos7.5

Grafos ajudam a enxergar dependências que, no código, ficam espalhadas por várias funções.

No Resource Allocation Graph:

• processos são círculos,
• recursos são quadrados,

Se cada recurso tiver uma única instância, um ciclo no grafo é prova de deadlock.

Quando queremos focar apenas em processos, convertemos o grafo para um wait-for graph: removemos os nós de recurso e ligamos diretamente um processo ao outro.

Esse formato aparece muito em bancos de dados e ferramentas de diagnóstico.

Note que, um ciclo nem sempre significa deadlock. Com múltiplas instâncias de um recurso, ciclo deixa de ser prova suficiente.

Se P3 terminar e liberar sua instância, P1 prossegue. Portanto, há espera, mas não necessariamente impasse.

Estratégias para lidar com deadlocks7.6

Quatro famílias de abordagem aparecem na literatura e na prática.

Algoritmo do Avestruz7.6.1

Em muitos sistemas gerais, o kernel não tenta resolver genericamente todo deadlock possível. Em vez disso, trata deadlocks como bugs de implementação de locks internos ou como falhas raras demais para justificar o custo de uma política universal de prevenção.

flowchart LR
    A[Requisicao de recurso] --> B{Vale monitorar formalmente?}
    B -- Nao --> C[Concede e segue]
    C --> D{Travou?}
    D -- Nao --> E[Execucao normal]
    D -- Sim --> F[Bug, reinicio, rollback ou correcao de codigo]

flowchart LR
    A[Requisicao de recurso] --> B{Vale monitorar formalmente?}
    B -- Nao --> C[Concede e segue]
    C --> D{Travou?}
    D -- Nao --> E[Execucao normal]
    D -- Sim --> F[Bug, reinicio, rollback ou correcao de codigo]

Essa estratégia parece irresponsável, mas faz sentido quando:

1. deadlocks são muito raros,
2. o custo de evitar todos eles é alto,
3. a política universal prejudicaria o desempenho de todo o sistema.

Detecção e recuperação7.6.2

Aqui o sistema permite a alocação normal, mas periodicamente verifica se surgiu um ciclo.

Detecção matricial para múltiplos recursos7.6.2.1

Usamos quatro estruturas:

• $E$: vetor de recursos existentes.
• $A$: vetor de recursos disponíveis.
• $C$: matriz de alocação atual.
• $R$: matriz de requisição pendente.

A lógica é procurar um processo cuja requisição seja compatível com os recursos disponíveis. Se ele puder terminar, devolvemos o que ele segura e repetimos. Se sobrar alguém que nunca consegue terminar, esse conjunto está em deadlock.

#include <stdio.h>
#include <stdbool.h>

#define N 3  // quantidade de processos
#define M 4  // quantidade de tipos de recurso

void detectar_deadlock(int available[M], int current[N][M], int request[N][M]) {
    int work[M];
    bool finish[N] = {false};

    for (int j = 0; j < M; j++) {
        work[j] = available[j];
    }

    bool mudou = true;
    while (mudou) {
        mudou = false;

        for (int i = 0; i < N; i++) {
            if (finish[i]) {
                continue;
            }

            bool pode_terminar = true;
            for (int j = 0; j < M; j++) {
                if (request[i][j] > work[j]) {
                    pode_terminar = false;
                    break;
                }
            }

            if (pode_terminar) {
                for (int j = 0; j < M; j++) {
                    work[j] += current[i][j];
                }
                finish[i] = true;
                mudou = true;
            }
        }
    }

    printf("Processos em deadlock: ");
    for (int i = 0; i < N; i++) {
        if (!finish[i]) {
            printf("P%d ", i + 1);
        }
    }
    printf("\n");
}

int main(void) {
    int available[M] = {2, 1, 0, 0};
    int current[N][M] = {
        {0, 0, 1, 0},
        {2, 0, 0, 1},
        {0, 1, 2, 0}
    };
    int request[N][M] = {
        {2, 0, 0, 1},
        {1, 0, 1, 0},
        {2, 1, 0, 0}
    };

    detectar_deadlock(available, current, request);
    return 0;
}

Exemplo passo a passo7.6.2.2

Considere:

$$ A = (2, 1, 0, 0) $$

1. Com $A=(2,1,0,0)$, quem pode terminar primeiro é $P_3$, pois sua requisição é $(2,1,0,0)$, exatamente compatível com os recursos disponíveis.
2. Ao terminar, $P_3$ devolve $(0,1,2,0)$.
3. Agora $A=(2,2,2,0)$ e $P_2$ pode terminar, pois pede apenas $(1,0,1,0)$.
4. $P_2$ devolve $(2,0,0,1)$.
5. Agora $A=(4,2,2,1)$ e $P_1$ também consegue terminar.
6. Por fim, $P_1$ devolve $(0,0,1,0)$, ficando $A=(4,2,3,1)$.

Como todos conseguem terminar, não há deadlock.

Recuperação7.6.2.3

Depois de detectar, o sistema precisa decidir como sair do ciclo. As opções clássicas são:

1. Preempção de algum recurso, quando isso for tecnicamente possível.
2. Rollback de um processo para um ponto seguro anterior.
3. Abortar uma ou mais vítimas.

Como escolher a vítima?7.6.2.4

Na prática, não se mata um processo aleatoriamente. Alguns critérios comuns são:

1. menor custo de rollback,
2. menor prioridade,
3. menor tempo de execução já investido,
4. menor quantidade de recursos segurados,
5. menor impacto para o usuário.

Evitação: o Algoritmo do Banqueiro7.6.3

Dijkstra propôs um método mais rigoroso: um recurso só é concedido se, depois da concessão, o sistema continuar em estado seguro.

A ideia é a de um gerente de banco conservador. O banco pode até ter dinheiro em caixa agora, mas isso não basta. Antes de emprestar, ele se pergunta:

Se eu entregar este recurso agora, ainda existirá alguma ordem possível em que todos os processos possam terminar e, ao terminar, devolver os recursos que já possuem?

Se a resposta for sim, a concessão é feita. Se a resposta for não, o pedido é adiado, mesmo que o recurso esteja livre naquele instante.

O modelo usa:

• Max: demanda máxima declarada de cada processo,
• Allocation: o que cada processo já recebeu,
• Need = Max - Allocation,
• Available: o que ainda está livre.

Como pensar no algoritmo7.6.4

Sempre que um processo faz uma nova requisição, o sistema executa mentalmente três passos:

1. Simula a concessão do recurso.
2. Recalcula Available, Allocation e Need.
3. Testa se, nesse novo estado, ainda existe uma sequência de processos que pode terminar até esvaziar o sistema.

Se existir essa sequência, o estado é seguro. Se não existir, o estado é inseguro e o pedido deve esperar.

Receita operacional7.6.4.1

1. Veja quanto está livre em Available.
2. Procure algum processo cujo Need caiba inteiro dentro de Available.
3. Se encontrar, imagine que ele termina e devolve tudo o que está em Allocation.
4. Atualize Available com essa devolução.
5. Repita.
6. Se todos conseguem terminar, o estado é seguro.
7. Se em algum momento ninguém mais consegue terminar, o estado é inseguro.

Exemplo intuitivo do banqueiro7.6.4.2

Se o caixa tem 5, o estado é seguro porque o banco consegue atender C, que precisa de 2. Quando C termina, devolve tudo e o caixa sobe, permitindo uma sequência segura para os demais.

Questões7.7

1. O que define um estado como inseguro no Algoritmo do Banqueiro?

• A) O sistema já está em deadlock.
• B) Um processo solicitou mais recursos do que o total existente.
• C) Não existe garantia de uma sequência segura para todos, embora o deadlock ainda possa não ter ocorrido.
• D) Todos os recursos foram alocados e o vetor Available está zerado.

2. Relacione as condições de Coffman com suas descrições:

3. No código com threadA e threadB, qual linha de raciocínio mostra formalmente a presença das quatro condições de Coffman?

4. Analise o grafo abaixo. Se cada recurso tiver apenas uma instância, existe impasse?

5. Um sistema possui três instâncias do recurso R:

• P1 possui 1 e pede mais 1.
• P2 possui 1 e pede mais 1.
• P3 possui 1 e não pede nada.

Há deadlock? O que acontece quando P3 termina?

6. Explique por que a técnica de ordem global de aquisição de locks quebra a condição de espera circular.

7. Diferencie deadlock, starvation e livelock em um parágrafo curto para cada um.

8. No contexto de banco de dados, por que duas transferências simultâneas entre contas podem gerar deadlock? Dê uma solução baseada em prevenção.

9. Por que memória RAM é tipicamente tratada como recurso preemptível, enquanto uma impressora não é? O que daria errado se o sistema interrompesse uma impressão na metade?

10. Em um sistema que detecta deadlocks, como você escolheria a vítima de rollback? Cite pelo menos três critérios plausíveis.

11. Analise o código abaixo e explique por que ele pode entrar em livelock em vez de deadlock:

while (1) {
    pthread_mutex_lock(&lock1);
    if (pthread_mutex_trylock(&lock2) == 0) {
        break;
    }
    pthread_mutex_unlock(&lock1);
}

12. Um sistema está em estado seguro. Isso significa que toda requisição futura deve ser aceita imediatamente? Justifique com base no Algoritmo do Banqueiro.

Próximos passos7.8

Agora que sabemos como processos podem travar uns aos outros ao disputar recursos, o próximo passo é estudar o espaço onde esses processos vivem: a memória. Na próxima aula, exploraremos a 8 - memory management, saindo da concorrência para a organização do espaço de endereçamento.