Aula 15 — Revisão Geral do Semestre

:::tip Para a prova Esta aula não introduz conteúdo novo — é uma revisão sistemática de todos os tópicos do semestre. Use os mapas conceituais e o quiz de revisão para identificar lacunas antes da prova. :::

Mapa do semestre

┌─────────────────────────────────────────────────────────────────────┐
│                    SISTEMAS OPERACIONAIS I                           │
│                                                                     │
│  BLOCO 1 — FUNDAMENTOS (Aulas 01–04)                               │
│  ┌────────────┐  ┌──────────────┐  ┌─────────────┐  ┌───────────┐ │
│  │ Intro SO   │  │  Processos   │  │ Notação     │  │ Syscalls  │ │
│  │ Serviços   │  │  PCB, Estados│  │ Fork/Join   │  │ open/read │ │
│  │ Estruturas │  │  fork/exec   │  │ Parbegin    │  │ stat/dir  │ │
│  └────────────┘  └──────────────┘  └─────────────┘  └───────────┘ │
│                                                                     │
│  BLOCO 2 — CONCORRÊNCIA (Aulas 05–09, 11–12)                      │
│  ┌────────────┐  ┌──────────────┐  ┌─────────────┐  ┌───────────┐ │
│  │ Problemas  │  │ Sincronização│  │  Problemas  │  │ IPC POSIX │ │
│  │ Race cond. │  │ Mutex, Sem.  │  │  Clássicos  │  │ shm+sem   │ │
│  │ Deadlock   │  │ Monitores    │  │  Prod/Cons  │  │ nomeados  │ │
│  └────────────┘  └──────────────┘  └─────────────┘  └───────────┘ │
│                                                                     │
│  BLOCO 3 — THREADS E PCB (Aulas 07–09)                            │
│  ┌────────────┐  ┌──────────────┐  ┌─────────────┐               │
│  │fork/exec   │  │  PCB/filas   │  │  Exclusão   │               │
│  │ prática    │  │  ctx switch  │  │  Mútua      │               │
│  │ pthreads   │  │  modelos 1:1 │  │  TAS/CAS    │               │
│  └────────────┘  └──────────────┘  └─────────────┘               │
│                                                                     │
│  BLOCO 4 — SCHEDULING (Aulas 13 e 16)                             │
│  ┌────────────────────────┐  ┌─────────────────────────────────┐  │
│  │ FIFO/SJF/RR/Prioridades│  │  Hard/Soft RT, RMS, EDF         │  │
│  │ MLFQ, CFS, Loteria     │  │  Latência, cotas proporcionais  │  │
│  └────────────────────────┘  └─────────────────────────────────┘  │
│                                                                     │
│  BLOCO 5 — VIRTUALIZAÇÃO (Aula 14)                                │
│  ┌─────────────────────────────────────────────────────────────┐  │
│  │ Tipos 0/1/2, VCPU, trap-and-emulate, NPT, containers        │  │
│  └─────────────────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────────────────┘

---

Bloco 1 — Fundamentos

Conceito de processo

• Processo = programa em execução. Inclui: código (text), dados (BSS/data), pilha (stack), heap + PCB.
• PCB contém: PID, estado, PC, registradores, prioridade, tabela de páginas, lista de fds.
• Estados: Novo → Pronto → Execução → Bloqueado → Concluído. Diagrama de 5 estados.
• Schedulers: longo prazo (admissão), médio prazo (swapping), curto prazo (dispatcher).

Fork / Exec / Wait

fork()   → duplica processo; retorna PID do filho ao pai, 0 ao filho
execvp() → substitui imagem do processo por novo programa (não retorna em sucesso)
waitpid(pid, &status, 0) → pai aguarda filho específico
WIFEXITED(s) / WEXITSTATUS(s) / WIFSIGNALED(s) / WTERMSIG(s)

Zumbi = filho terminou, pai não chamou wait(). Órfão = pai terminou antes do filho.

Threads

• Thread compartilha: código, dados, heap, fds. Privado: pilha, PC, registradores.
• Modelos: N:1 (syscall bloqueia processo), 1:1 (Linux/Windows), M:N.
• Lei de Amdahl: speedup ≤ 1 / (S + (1−S)/N).

Syscalls (Aula 04)

Arquivo	Diretório	Processo
open, read, write, close, lseek	opendir, readdir, closedir	getpid, getppid, getuid, getcwd
stat/fstat (struct stat)	—	fork, exec, waitpid

---

Bloco 2 — Concorrência e Sincronização

O problema

counter++ em linguagem de máquina = 3 instruções
Preempção entre elas → race condition → resultado não-determinístico

Seção crítica — 3 requisitos

1. Exclusão mútua — apenas um processo na SC por vez
2. Progresso — se nenhum está na SC e alguém quer entrar, a decisão não é adiada indefinidamente
3. Espera limitada — limite finito de quantas vezes outros entram antes de um processo ser atendido

Soluções de exclusão mútua

Abordagem	EM	Prog.	Esp. Lim.	Obs.
Desabilitar interrupções	✓¹	✓	✓	¹só monoprocessador
Variável lock simples	✗	✗	✗	não atômica
Peterson	✓	✓	✓	requer memory fence em hw moderno
TAS simples	✓	✓	✗	sem espera limitada
TAS + waiting[]	✓	✓	✓	garante ordem cíclica
CAS	✓	✓	✓*	base para lock-free
Mutex bloqueante	✓	✓	✓	SO/biblioteca
Monitor	✓	✓	✓	automático pela linguagem

Semáforos

• wait(S): S--; se S < 0 → bloqueia. signal(S): S++; se S ≤ 0 → acorda.
• Binário (=1): mutex. Contador (=N): pool. Sincronização (=0): garantir ordem.
• Ordem correta no Produtor/Consumidor: wait(empty) ANTES de wait(mutex).

Deadlock — 4 condições de Coffman

1. Exclusão mútua | 2. Retenção e espera | 3. Sem preempção | 4. Espera circular

Starvation ≠ Deadlock: starvation = injustiça (outros progridem); deadlock = impasse total.

Problemas clássicos

Problema	Semáforos	Invariante
Buffer Limitado	mutex=1, empty=N, full=0	wait(condição) antes de wait(mutex)
Leitores-Gravadores	rw_mutex=1, mutex=1, read_count	1ª variante: starvation de gravadores
Filósofos	chopstick[5]={1} ou monitor	Deadlock se todos pegam esquerdo

---

Bloco 3 — PCB, Context Switch e Exclusão Mútua HW

Context switch

Salva PCB_A (PC, registradores, estado) → seleciona B → restaura PCB_B → TLB flush. Puro overhead.

TAS e CAS

• test_and_set(alvo): lê, seta true, retorna antigo — atômico.
• compare_and_swap(val, esperado, novo): substitui só se val==esperado — atômico.
• Peterson falha em hw moderno sem memory fence (store buffers reordenam writes).

---

Bloco 4 — Scheduling

Critérios

Utilização, throughput, turnaround = conclusão − chegada, espera = turnaround − pico, resposta = 1ª CPU − chegada.

Algoritmos — resumo rápido

Algoritmo	Preemptivo	Problema	Solução
FIFO	Não	Convoy effect	—
SJF	Não	Starvation (longos)	Ótimo para espera média
SRTF	Sim	Starvation (longos)	Ótimo com chegadas
Prioridades	Ambos	Starvation	Aging
Round-Robin	Sim	Alto tempo médio espera	Bom tempo resposta
MLFQ	Sim	Complexo	SOs reais (aprox. SJF)
CFS (Linux)	Sim	—	vruntime, árvore RV

Tempo real

• RMS: prioridade estática pelo período. Limite: N * (2^(1/N) - 1) ≈ 69% para N→∞.
• EDF: prioridade dinâmica pelo deadline mais próximo. Ótimo teórico (100% utilização).
• Indústria prefere RMS pela previsibilidade sob sobrecarga.

---

Bloco 5 — Virtualização

Hierarquia de conceitos

Hardware → Hipervisor (VMM) → SO convidado → Aplicação
 
Tipo 0: firmware | Tipo 1: bare metal | Tipo 2: sobre SO hospedeiro
Popek-Goldberg: fidelidade + desempenho + controle
VCPU ↔ PCB :: VMM ↔ SO
Trap-and-emulate: instruções privilegiadas → VM exit → VMM emula → VM entry

Containers: compartilham kernel (namespaces + cgroups). Mais leves, menor isolamento.

---

Quiz de revisão geral

Quiz10 questões

1. fork() é chamado em um processo multithreaded com 3 threads. Quantos threads o processo filho terá?

• a)3 — herda todos os threads do pai
• b)1 — apenas o thread que chamou fork()
• c)0 — fork() não funciona em processos multithreaded
• d)Depende do sistema operacional
• e)2 — todos exceto o thread principal

2. Três requisitos da seção crítica: exclusão mútua, progresso e espera limitada. Uma solução de turno rígido (turn=0→P0, turn=1→P1, alternando) viola qual requisito?

• a)Exclusão mútua — dois processos podem entrar simultaneamente
• b)Progresso — se P1 está na seção remanescente e turn=1, P0 não pode entrar mesmo sem conflito
• c)Espera limitada — P0 pode esperar indefinidamente
• d)Não viola nenhum requisito
• e)Viola os três requisitos

3. Um semáforo S=2 e 5 processos chegam simultaneamente fazendo wait(S). Quantos processos ficam bloqueados?

• a)0 — todos passam
• b)2 — os primeiros dois bloqueiam
• c)3 — os três últimos bloqueiam
• d)5 — todos bloqueiam
• e)Depende do escalonador

4. Qual propriedade o CAS (compare_and_swap) tem que o TAS simples não tem, permitindo implementar estruturas lock-free?

• a)CAS é mais rápido que TAS em qualquer arquitetura
• b)CAS só modifica o valor SE ele ainda for o esperado — permite detectar se outro thread interferiu entre a leitura e a escrita
• c)CAS não gera busy waiting; TAS sempre gera
• d)CAS funciona em multiprocessador; TAS não
• e)CAS pode ser usado sem suporte de hardware

5. No Buffer Limitado com semáforos, o produtor DEVE fazer wait(empty) ANTES de wait(mutex). O que acontece se a ordem for invertida quando o buffer está cheio?

• a)Starvation — o produtor espera indefinidamente mas sem deadlock
• b)Condição de corrida — dois produtores inserem no mesmo slot
• c)Deadlock — produtor bloqueia em wait(empty) com mutex em posse; consumidor não consegue wait(mutex) para liberar espaço
• d)O buffer transborda
• e)Nada — a ordem não importa para a corretude

6. Lei de Amdahl: uma aplicação tem 10% de código serial. Com 8 núcleos, qual o speedup aproximado?

• a)8× — todos os núcleos trabalham
• b)4,7×
• c)7,1×
• d)5,5×
• e)3,2×

7. No RMS, P1(p=30, t=10) e P2(p=70, t=20). Qual processo tem maior prioridade e o sistema é escalonável pelo RMS?

• a)P2 prioridade maior; sim, escalonável
• b)P1 prioridade maior; sim, escalonável (U≈61,4% < 82,8%)
• c)P1 prioridade maior; não escalonável (U>82,8%)
• d)P2 prioridade maior; não escalonável
• e)Iguais; depende do deadline

8. Qual a diferença entre um Hipervisor Tipo 1 e um Hipervisor Tipo 2?

• a)Tipo 1 usa paravirtualização; Tipo 2 usa virtualização completa
• b)Tipo 1 executa diretamente no hardware (bare metal); Tipo 2 executa como aplicação sobre um SO hospedeiro
• c)Tipo 1 é implementado em firmware; Tipo 2 é implementado em software de kernel
• d)Tipo 1 suporta apenas Linux como convidado; Tipo 2 suporta qualquer SO
• e)Tipo 1 usa trap-and-emulate; Tipo 2 usa tradução binária

9. O que distingue EDF de RMS quanto ao comportamento sob sobrecarga (utilização > 100%)?

• a)RMS distribui a perda de deadline uniformemente; EDF protege as tarefas de maior prioridade
• b)RMS tem comportamento previsível (tarefas de menor prioridade falham primeiro); EDF tem comportamento imprevisível (qualquer tarefa pode falhar)
• c)EDF nunca perde deadlines; RMS perde deadlines frequentemente
• d)São equivalentes sob sobrecarga
• e)EDF para o sistema; RMS continua com degradação gradual

10. Um container Docker e uma VM rodando Ubuntu diferem em qual aspecto fundamental relacionado ao kernel do SO?

• a)A VM tem kernel mais rápido que o container
• b)O container usa o kernel do sistema hospedeiro; a VM tem seu próprio kernel isolado
• c)Ambos têm kernels idênticos — a diferença é apenas na interface gráfica
• d)O container não pode executar aplicações de rede; a VM pode
• e)A VM usa namespaces; o container usa tabelas de páginas aninhadas

---

Checklist de revisão por bloco

Antes da prova, verifique se você consegue responder cada item sem consultar o material:

Bloco 1 — Processos e Threads

• Desenhar o diagrama de estados de um processo (5 estados com transições)
• Explicar o que o PCB contém e qual campo é essencial no context switch
• Escrever um programa fork/exec/wait em C com tratamento correto de erros
• Calcular quantos processos são criados por fork(); fork(); fork()
• Explicar a diferença entre processo zumbi e processo órfão
• Comparar modelos N:1, 1:1 e M:N de threads

Bloco 2 — Sincronização

• Demonstrar race condition com trace de counter++ em nível de máquina
• Enunciar os 3 requisitos da seção crítica com exemplo de violação de cada
• Explicar a Solução de Peterson e provar que satisfaz os 3 requisitos
• Traçar a execução de wait(S) e signal(S) com valor de S e processos bloqueados
• Identificar o erro de inversão de wait/mutex no Produtor/Consumidor
• Desenhar o deadlock no Jantar dos Filósofos e identificar as 4 condições de Coffman
• Escrever o pseudocódigo da solução com monitor para o Jantar

Bloco 3 — Exclusão Mútua HW

• Explicar por que variável lock simples não funciona
• Descrever o mecanismo de TAS e por que deve ser atômico
• Diferenciar TAS (sem espera limitada) de TAS+waiting[] (com espera limitada)
• Explicar a diferença semântica entre TAS e CAS

Bloco 4 — Scheduling

• Calcular tempo de espera e turnaround para FIFO, SJF e RR dado um conjunto de processos
• Construir gráfico de Gantt para cada algoritmo
• Explicar convoy effect (FIFO), starvation (Prioridades) e como aging resolve
• Descrever MLFQ e como ele classifica automaticamente CPU-bound vs. I/O-bound
• Explicar vruntime no CFS e por que processos I/O-bound têm prioridade natural
• Calcular utilização RMS e aplicar o limite N * (2^(1/N) - 1)
• Construir Gantt para RMS e EDF, identificando onde RMS falha e EDF resolve
• Explicar por que RMS é preferido na indústria

Bloco 5 — Virtualização

• Explicar os 3 requisitos de Popek-Goldberg
• Descrever o mecanismo trap-and-emulate passo a passo
• Comparar Tipo 0, 1 e 2 com exemplos
• Explicar VCPU por analogia com PCB
• Diferenciar VMs de containers em termos de kernel e overhead