Aula 06 — Sincronização: Mutex, Semáforos e Monitores

Objetivos

Ao final desta aula você deve ser capaz de:

Explicar o lock mutex como ferramenta de exclusão mútua e implementar exclusão mútua entre processos com semáforos POSIX.
Definir semáforo, distinguir semáforo binário de contador e implementar ambos os usos com wait() / signal().
Usar semáforos para sincronização de ordem (forçar S2 após S1) e para controle de pool de recursos.
Identificar erros clássicos de uso de semáforos (inversão de wait/signal, omissão) e seus efeitos.
Descrever o monitor como construtor de linguagem de alto nível e explicar o papel das variáveis de condição x.wait() / x.signal().
Comparar mutex, semáforo e monitor quanto a nível de abstração, expressividade e risco de erro.
Implementar o padrão fork-exec-wait com comunicação entre pai e filho usando variáveis de ambiente ou pipe.

Conteúdo

Visão geral das ferramentas de sincronização

A Aula 05 apresentou o problema da seção crítica e exigências de qualquer solução. Esta aula apresenta as ferramentas que os sistemas operacionais e linguagens fornecem para resolver esse problema na prática.

Lock Mutex

O mutex (mutual exclusion lock) é a ferramenta mais simples: uma trava binária que um processo deve adquirir antes de entrar na seção crítica e liberar ao sair.

Semântica:

acquire(): se o mutex está disponível, adquire-o (agora indisponível) e prossegue. Se está indisponível, bloqueia o processo até que seja liberado.
release(): torna o mutex disponível e acorda um processo bloqueado (se houver).

Mutex entre processos com semáforos POSIX

/* Executável — exclusão mútua entre processos com semáforo binário */
/* Compile: gcc -o contador contador.c -lpthread                    */
#include <sys/mman.h>   /* mmap, MAP_SHARED, MAP_ANONYMOUS */
#include <sys/wait.h>   /* wait */
#include <semaphore.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

#define N_PROC      4
#define INCREMENTOS 100000

int main(void)
{
    /* Variável compartilhada e semáforo na mesma região de memória */
    long  *contador = mmap(NULL, sizeof(long),
                           PROT_READ|PROT_WRITE,
                           MAP_SHARED|MAP_ANONYMOUS, -1, 0);
    sem_t *mtx      = mmap(NULL, sizeof(sem_t),
                           PROT_READ|PROT_WRITE,
                           MAP_SHARED|MAP_ANONYMOUS, -1, 0);
    *contador = 0;
    /* pshared=1: visível entre processos; valor=1: semáforo binário */
    sem_init(mtx, 1, 1);

    for (int i = 0; i < N_PROC; i++) {
        if (fork() == 0) {
            for (int j = 0; j < INCREMENTOS; j++) {
                sem_wait(mtx);   /* acquire — bloqueia se S = 0 */
                    (*contador)++;
                sem_post(mtx);   /* release                      */
            }
            exit(0);
        }
    }

    for (int i = 0; i < N_PROC; i++) wait(NULL);

    printf("Esperado: %ld\n", (long)N_PROC * INCREMENTOS);
    printf("Obtido:   %ld\n", *contador);
    /* Sem sem_wait/sem_post: valores incorretos. Com eles: sempre correto. */
    sem_destroy(mtx);
    return 0;
}

Atividade prática rápida: remova as chamadas de sem_wait/sem_post e execute várias vezes. Observe que o resultado varia entre execuções — a condição de corrida em ação. Reinsira as chamadas e confirme que o resultado é sempre determinístico.

Spinlock vs. mutex bloqueante:

Característica	Spinlock	Mutex bloqueante
Espera	Busy waiting (gira na CPU)	Bloqueia o processo (suspende)
Overhead de espera curta	Baixo (sem troca de contexto)	Alto (context switch)
Overhead de espera longa	Alto (CPU desperdiçada)	Baixo (não consome CPU)
Uso típico	Kernel, seções de microsegundos	Aplicações, seções longas

Semáforos

Um semáforo S é uma variável inteira acessada apenas por duas operações atômicas:

Notação histórica: wait() = P() = "proberen" (testar, em holandês). signal() = V() = "verhogen" (incrementar). Você verá as duas notações na literatura.

Quando S é negativo, |S| = número de processos bloqueados aguardando.

Semáforo Binário (mutex por semáforo)

Inicializado em 1. Funciona como um mutex — garante exclusão mútua:

Se Pi entra primeiro: mutex = 1 → 0. Pi executa a SC.
Pj chega: mutex = 0 → −1. Pj bloqueia (|−1| = 1 processo esperando).
Pi sai e faz signal: mutex = −1 → 0. Pj é acordado e entra na SC.

Semáforo Contador (pool de recursos)

Inicializado com o número de instâncias disponíveis do recurso. Controla acesso a pools:

Quando disponivel = 0: todos os recursos estão em uso. Novos processos bloqueiam até que um recurso seja devolvido.

Semáforo para sincronização de ordem

Semáforos inicializados em 0 forçam que uma operação ocorra antes de outra — mesmo que os processos sejam concorrentes:

Uso prático: garantir que a thread de inicialização conclua antes que as threads de trabalho comecem.

Implementação com bloqueio real (sem busy waiting)

A implementação do semáforo que bloqueia processos (em vez de spin) usa uma fila interna:

/* Somente leitura — estrutura interna do semáforo bloqueante */
typedef struct {
    int value;           /* valor do semáforo                  */
    struct process *list; /* fila de processos bloqueados       */
} semaphore;

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        /* insere este processo em S->list  */
        block();         /* suspende o processo atual          */
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        /* remove processo P de S->list     */
        wakeup(P);       /* acorda P (move para fila de prontos) */
    }
}

Observação importante: nessa implementação, o valor do semáforo pode ser negativo — o valor negativo indica quantos processos estão na fila de espera. Isso não ocorre na versão com busy waiting.

Erros clássicos com semáforos

Pequenos erros de programação quebram toda a garantia de sincronização:

Erro	Código errado	Consequência
Inversão de wait/signal	`signal(mutex); SC; wait(mutex)`	Múltiplos processos na SC simultaneamente — violação de exclusão mútua
Wait duplicado	`wait(mutex); SC; wait(mutex)`	Deadlock — o processo bloqueia a si mesmo
Omitir signal	`wait(mutex); SC;`	Deadlock — outros processos ficam bloqueados para sempre
Omitir wait	`SC; signal(mutex)`	Sem exclusão mútua — condição de corrida

Esses erros são difíceis de detectar porque só se manifestam em interleavings específicos — podem não aparecer em testes normais.

Semáforos POSIX em C

/* Executável — semáforo de ordenação entre processos (fork) */
/* Compile: gcc -o sem_ord sem_ord.c -lpthread               */
#include <sys/mman.h>
#include <sys/wait.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int   *recurso = mmap(NULL, sizeof(int),   PROT_READ|PROT_WRITE,
                          MAP_SHARED|MAP_ANONYMOUS, -1, 0);
    sem_t *pronto  = mmap(NULL, sizeof(sem_t), PROT_READ|PROT_WRITE,
                          MAP_SHARED|MAP_ANONYMOUS, -1, 0);
    *recurso = 0;
    sem_init(pronto, 1, 0);   /* pshared=1, valor=0 → consumidor bloqueará */

    if (fork() == 0) {
        /* filho = produtor */
        *recurso = 42;
        printf("Produtor: recurso = %d\n", *recurso);
        sem_post(pronto);     /* signal() — acorda o pai (consumidor) */
        exit(0);
    }

    /* pai = consumidor */
    sem_wait(pronto);         /* wait() — bloqueia até o filho sinalizar */
    printf("Consumidor: recurso = %d\n", *recurso);
    wait(NULL);
    sem_destroy(pronto);
    return 0;
}

API POSIX de semáforos:

Função	Equivalente	Descrição
`sem_init(&s, pshared, val)`	—	Inicializa semáforo sem nome; `pshared=0`: entre threads; `pshared=1`: entre processos (em `mmap` compartilhado)
`sem_wait(&s)`	`wait(S)` / `P(S)`	Decrementa; bloqueia se < 0
`sem_post(&s)`	`signal(S)` / `V(S)`	Incrementa; acorda processo se necessário
`sem_destroy(&s)`	—	Libera o semáforo
`sem_open(nome,...)`	—	Semáforo nomeado (entre processos distintos)

Monitores

Semáforos são poderosos mas propensos a erros de programação. O monitor é um construtor de linguagem de alto nível que encapsula dados compartilhados e garante exclusão mútua automaticamente.

Propriedade fundamental do monitor: somente um processo por vez pode estar ativo dentro do monitor — a exclusão mútua é garantida pela linguagem/runtime, não pelo programador.

Estrutura de um monitor

monitor NomeDoMonitor {
    /* variáveis de estado compartilhadas */
    int saldo;
    condition pode_sacar;

    /* operações — apenas uma executa por vez */
    void depositar(int valor) {
        saldo += valor;
        pode_sacar.signal();   /* notifica quem está esperando */
    }

    void sacar(int valor) {
        while (saldo < valor)
            pode_sacar.wait(); /* bloqueia e LIBERA o monitor  */
        saldo -= valor;
    }

    /* código de inicialização */
    NomeDoMonitor() { saldo = 0; }
}

Variáveis de condição

Dentro do monitor, o programador pode declarar variáveis de condição para sincronização condicional:

condition x;

x.wait()    — o processo bloqueia e LIBERA o monitor (outro pode entrar)
x.signal()  — acorda UM processo bloqueado em x.wait() (se nenhum, não faz nada)

Diferença crítica entre x.signal() e signal(S) do semáforo:

signal(S) do semáforo sempre afeta o estado — incrementa S mesmo sem ninguém esperando.
x.signal() do monitor só tem efeito se há processo em x.wait() — caso contrário, é uma operação nula.

Monitores vs. Semáforos

Aspecto	Semáforo	Monitor
Exclusão mútua	Manual (wait/signal)	Automática (garantida pela linguagem)
Risco de erro	Alto (inversões, omissões)	Baixo (estrutura força o padrão correto)
Expressividade	Alta (mais flexível)	Alta (com variáveis de condição)
Suporte em linguagens	C (POSIX), Assembly	Java (`synchronized`), C# (`lock`)
Nível	SO/biblioteca	Linguagem de programação

Java — synchronized como monitor:

/* Somente leitura — monitor em Java com synchronized */
public class ContaBancaria {
    private int saldo;

    /* synchronized garante exclusão mútua automaticamente */
    public synchronized void depositar(int valor) {
        saldo += valor;
        notifyAll();         /* equivalente a x.signal() */
    }

    public synchronized void sacar(int valor)
                              throws InterruptedException {
        while (saldo < valor)
            wait();          /* equivalente a x.wait() — libera o lock */
        saldo -= valor;
    }
}

Revisão: padrão Fork-Exec-Wait

A ementa da Aula 06 inclui revisão de fork e fork-exec. O padrão completo é fundamental para criar processos que executam programas distintos:

/* Executável — padrão fork-exec-wait completo */
/* Compile: gcc -o forkexec forkexec.c         */
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    pid_t pid;
    int status;

    pid = fork();

    if (pid < 0) {
        perror("fork");
        exit(1);
    }

    if (pid == 0) {
        /* ─── FILHO ─────────────────────────────────── */
        /* execve substitui a imagem do filho por /bin/ls */
        char *args[] = {"ls", "-la", "/tmp", NULL};
        execvp("ls", args);
        /* se chegou aqui, execvp falhou               */
        perror("execvp");
        exit(1);
    }

    /* ─── PAI ──────────────────────────────────────── */
    pid = waitpid(pid, &status, 0);   /* aguarda o filho específico */

    if (WIFEXITED(status))
        printf("Filho terminou com código %d\n", WEXITSTATUS(status));
    else if (WIFSIGNALED(status))
        printf("Filho morto por sinal %d\n", WTERMSIG(status));

    return 0;
}

Macros de waitpid:

Macro	Significado
`WIFEXITED(status)`	Filho terminou normalmente com `exit()`
`WEXITSTATUS(status)`	Código de saída (0–255)
`WIFSIGNALED(status)`	Filho morto por sinal
`WTERMSIG(status)`	Número do sinal que matou o filho

Atividade prática rápida: compile e execute o programa acima. Em seguida, modifique args para executar "grep" com algum padrão em /var/log. Observe que o processo pai recebe o código de saída do filho via waitpid.

Exercícios

Questões dissertativas

Explique a diferença entre um lock mutex e um semáforo binário. Eles são intercambiáveis? Em que situação um semáforo binário não deve ser usado no lugar de um mutex?

Dado um semáforo S inicializado em 3, descreva o valor de S e o estado de cada processo após a seguinte sequência: P1 faz wait(S); P2 faz wait(S); P3 faz wait(S); P4 faz wait(S); P5 faz signal(S).

Mostre como usar um semáforo para garantir que a operação B() só execute após A() ter sido concluída, mesmo que os processos PA e PB sejam iniciados em qualquer ordem.

Identifique o erro no código abaixo e explique a consequência. Como corrigi-lo? wait(mutex); seção crítica wait(mutex); /* deveria ser signal */

Explique o papel das variáveis de condição em um monitor. Qual a diferença semântica entre x.signal() de um monitor e signal(S) de um semáforo quando não há processos aguardando?

Explique como Java implementa o conceito de monitor através da palavra-chave synchronized. Qual é o papel de wait() e notifyAll() em um método synchronized?

Descreva o padrão fork-exec-wait. Por que o padrão correto separa fork() do exec() em vez de criar o processo diretamente com o novo programa?

Q8Difícil

Dois semáforos S e Q são inicializados em 1. O processo P0 executa wait(S); wait(Q); signal(S); signal(Q). O processo P1 executa wait(Q); wait(S); signal(Q); signal(S). Há risco de deadlock? Justifique e proponha correção.

Qual a vantagem do monitor sobre o semáforo do ponto de vista de segurança de programação? Dê um exemplo de erro com semáforos que o monitor previne estruturalmente.

Q10Difícil

Compare as três ferramentas de sincronização desta aula (mutex, semáforo, monitor) em uma tabela com os critérios: nível de abstração, quem garante exclusão mútua, uso de variáveis de condição, linguagens/APIs e principal risco.

Quiz de múltipla escolha

Quiz10 questões

1. Um semáforo S é inicializado em 1. Após as operações wait(S); wait(S); signal(S), qual é o valor de S e quantos processos estão bloqueados?

a)S = 1, nenhum bloqueado
b)S = 0, nenhum bloqueado
c)S = -1, 1 processo bloqueado
d)S = 0, 1 processo bloqueado
e)S = -1, 0 processos bloqueados

2. Qual é a diferença semântica entre x.signal() de um monitor e signal(S) de um semáforo quando NENHUM processo está aguardando?

a)Nenhuma — ambos incrementam o contador interno
b)x.signal() acorda todos os processos; signal(S) acorda apenas um
c)x.signal() não tem efeito algum; signal(S) incrementa S e guarda o sinal para uso futuro
d)x.signal() bloqueia o processo; signal(S) o libera imediatamente
e)Ambos têm o mesmo efeito — são idênticos

3. Um programador usa 'signal(mutex)' antes da seção crítica (invertendo com wait). Qual a consequência?

a)Deadlock — o processo bloqueia a si mesmo
b)Starvation — o processo nunca entra na seção crítica
c)Múltiplos processos podem entrar na seção crítica simultaneamente, violando exclusão mútua
d)O semáforo fica em estado inválido e lança exceção
e)Nenhuma — signal antes de wait é permitido em semáforos

4. Para implementar um semáforo que controla acesso a um pool de 5 impressoras, qual deve ser o valor inicial do semáforo?

a)0 — para forçar todos a esperar inicialmente
b)1 — valor padrão de semáforos binários
c)5 — número de recursos disponíveis
d)-5 — para contagem negativa de espera
e)∞ — para permitir acesso ilimitado

5. Qual das afirmações sobre pthread_mutex_t em C está CORRETA?

a)Um thread pode fazer unlock em um mutex que outro thread travou
b)Um mutex pode ser travado múltiplas vezes pelo mesmo thread sem bloquear
c)O mesmo thread que fez lock deve fazer unlock — violação disso é comportamento indefinido
d)pthread_mutex_lock nunca bloqueia — é sempre não-bloqueante
e)Mutexes POSIX são automaticamente destruídos quando o processo termina

6. Em qual situação usar sem_post() (signal de semáforo POSIX) em vez de pthread_mutex_unlock() é a escolha CORRETA?

a)Quando o recurso protegido é um arquivo em disco
b)Quando um processo produtor quer sinalizar ao consumidor que um item foi produzido, sem que ambos compartilhem posse do mesmo lock
c)Quando apenas um thread precisa acessar o recurso por vez
d)Quando a seção crítica é muito longa (> 1 segundo)
e)Semáforos nunca devem ser usados no lugar de mutexes

7. No padrão fork-exec-wait, qual é o propósito de usar waitpid() em vez de wait() simples?

a)waitpid() é mais rápido que wait()
b)waitpid() permite especificar qual filho aguardar pelo PID, além de opções como WNOHANG para não bloquear
c)waitpid() funciona com exec(); wait() não funciona após exec()
d)waitpid() coleta o status de todos os filhos; wait() apenas do primeiro
e)waitpid() é necessário quando o filho usa semáforos

8. Qual a vantagem do monitor sobre o semáforo do ponto de vista de segurança de programação?

a)Monitores são mais rápidos que semáforos em todos os casos
b)Monitores permitem mais de um processo na seção crítica simultaneamente
c)A exclusão mútua é garantida estruturalmente pelo compilador/runtime — o programador não pode esquecer de liberar o lock
d)Monitores eliminam completamente a necessidade de variáveis de condição
e)Monitores são os únicos que funcionam em sistemas multiprocessador

9. Por que o padrão correto com variáveis de condição em monitores usa while() e não if() para verificar a condição antes de chamar x.wait()?

a)while() é mais eficiente que if() na JVM
b)if() causaria starvation enquanto while() evita
c)Após ser acordado por x.signal(), o thread deve reavaliar a condição pois outro thread pode ter mudado o estado antes de reacquirir o lock do monitor
d)x.wait() dentro de if() bloqueia o monitor permanentemente
e)Não há diferença — while() e if() são equivalentes nesse contexto

10. Um semáforo contador 'vagas' controla um estacionamento com 3 vagas. Qual é o valor de 'vagas' depois que: 2 carros entram, 1 sai, 3 entram, 1 sai?

a)vagas = 0, 0 carros esperando
b)vagas = -1, 1 carro esperando
c)vagas = 1, 0 carros esperando
d)vagas = -2, 2 carros esperando
e)vagas = 2, 0 carros esperando

Referências

Principais (essenciais)

SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
- §5.5 — Locks Mutex
- §5.6 — Semáforos (uso, implementação, deadlock com semáforos)
- §5.8 — Monitores (uso, variáveis de condição, implementação com semáforos)
- §3.3 — Operações sobre Processos (fork-exec-wait)

Aprofundamento (opcionais)

TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016. §2.3.4–2.3.7 — Semáforos, Mutexes, Monitores.
KERRISK, M. The Linux Programming Interface. No Starch Press, 2010. Cap. 30–31 (pthreads mutex e semáforos POSIX).
man 3 pthread_mutex_lock, man 3 sem_init, man 3 sem_wait — páginas de manual POSIX.

Recursos Complementares

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

Formas para obtenção de exclusão mútua

ENOpcional

Solve Critical Section Problem with Busy Waiting

Parul's E-Diary

Comunicação entre processos

ENOpcional

Inter Process Communication — Part 1/2

Education 4u

ENOpcional

Interprocess Communication

Neso Academy

Semáforos

ENOpcional

19.2.2 Semaphores

MIT OpenCourseWare

ENOpcional

Semaphores

Neso Academy

Monitores

ENOpcional

Monitors

Neso Academy

Objetivos​

Conteúdo​

Visão geral das ferramentas de sincronização​

Lock Mutex​

Mutex entre processos com semáforos POSIX​

Semáforos​

Semáforo Binário (mutex por semáforo)​

Semáforo Contador (pool de recursos)​

Semáforo para sincronização de ordem​

Implementação com bloqueio real (sem busy waiting)​

Erros clássicos com semáforos​

Semáforos POSIX em C​

Monitores​

Estrutura de um monitor​

Variáveis de condição​

Monitores vs. Semáforos​

Revisão: padrão Fork-Exec-Wait​

Exercícios​

Questões dissertativas​

Quiz de múltipla escolha​

Referências​

Principais (essenciais)​

Aprofundamento (opcionais)​

Recursos Complementares​

Formas para obtenção de exclusão mútua​

Comunicação entre processos​

Semáforos​

Monitores​

Objetivos

Conteúdo

Visão geral das ferramentas de sincronização

Lock Mutex

Mutex entre processos com semáforos POSIX

Semáforos

Semáforo Binário (mutex por semáforo)

Semáforo Contador (pool de recursos)

Semáforo para sincronização de ordem

Implementação com bloqueio real (sem busy waiting)

Erros clássicos com semáforos

Semáforos POSIX em C

Monitores

Estrutura de um monitor

Variáveis de condição

Monitores vs. Semáforos

Revisão: padrão Fork-Exec-Wait

Exercícios

Questões dissertativas

Quiz de múltipla escolha

Referências

Principais (essenciais)

Aprofundamento (opcionais)

Recursos Complementares

Formas para obtenção de exclusão mútua

Comunicação entre processos

Semáforos

Monitores