O que você vai aprender
Comparar FCFS, SJF, Round-Robin e prioridades.
Calcular métricas como tempo de espera e de retorno.
Aplicar Rate Monotonic e EDF a tarefas periódicas de tempo real.
Interpretar testes de escalonabilidade (utilização).
Quem roda agora?
Há dez processos prontos e um core livre. Qual deles recebe a CPU? Essa decisão, tomada milhares de vezes por segundo, define se o sistema parece ágil, se jobs longos terminam e se um airbag dispara a tempo.
O escalonador é o árbitro. Esta aula compara estratégias clássicas e, crucialmente para a Engenharia de Computação, as de tempo real, onde perder um prazo pode ser catastrófico.
Roteiro da aula
FCFS/SJF/RR→Métricas→Tempo real
RM/EDF→Simuladores
Veremos os algoritmos de propósito geral, como medi-los, e depois o escalonamento de tarefas periódicas com prazos rígidos.
Preemptivo vs. não preemptivo
Não preemptivo. O processo só larga a CPU ao terminar ou bloquear (FCFS, SJF clássico).
A preempção, viabilizada pela interrupção do timer (Aula 2), é o que permite respostas rápidas e o cumprimento de prazos — mas custa trocas de contexto (Aula 3).
Os algoritmos clássicos
| Algoritmo | Ideia | Característica |
|---|---|---|
| FCFS | Ordem de chegada | Simples; sofre efeito comboio |
| SJF | Menor tarefa primeiro | Ótimo para espera média; pode causar inanição |
| Round-Robin | Quantum fixo, circular | Justo para interativos |
| Prioridades | Maior prioridade primeiro | Flexível; risco de inanição |
FCFS e o efeito comboio
O processo longo P1, à frente no FCFS, "engarrafa" os curtos — o efeito comboio. O SJF, colocando os curtos primeiro, despenca a espera média de 17 para 3.
Passo a passo: Round-Robin com quantum 2
Métricas de escalonamento
Tempo de espera. Tempo na fila de prontos (retorno − tempo de surto).
Vazão. Processos concluídos por unidade de tempo.
Tempo de resposta. Da chegada até começar a rodar pela primeira vez.
Não existe escalonador perfeito
Cada métrica puxa para um lado. Minimizar o tempo de espera médio favorece o SJF, mas ele pode causar inanição (um job longo nunca roda se chegam curtos sem parar). Maximizar a justiça favorece o RR, mas quantum pequeno gera muita troca de contexto.
O caixa do supermercado
Rate Monotonic vs. EDF
| Aspecto | Rate Monotonic (RM) | EDF |
|---|---|---|
| Prioridade | Estática (por período) | Dinâmica (por prazo) |
| Regra | Menor período → maior prioridade | Prazo mais próximo → executa |
| Limite de utilização | ≈ 69% (n→∞) | 100% |
| Implementação | Simples, previsível | Mais complexa (recalcula prazos) |
EDF (Earliest Deadline First). Prioridade dinâmica: executa a tarefa cujo prazo está mais próximo.
Teste de escalonabilidade
Σ Cᵢ/Tᵢ→RM: U ≤
n(2^(1/n)−1)?→EDF:
U ≤ 1?→Escalonável?
Por que RM se limita a 69%
O limite de Liu & Layland para RM é U ≤ n(2^(1/n) − 1), que decresce de 100% (1 tarefa) até ln 2 ≈ 69,3% quando n → ∞. É uma condição suficiente, não necessária: conjuntos acima de 69% podem ainda ser escalonáveis (verifica-se pela análise de tempo de resposta).
EDF, por usar prioridade dinâmica, aproveita 100% da CPU em uniprocessador. A contrapartida: sob sobrecarga (U > 1), o EDF degrada de forma imprevisível (efeito dominó de perdas de prazo), enquanto o RM perde primeiro as tarefas de menor prioridade — mais controlável.
Verifique seu entendimento
Duas tarefas periódicas: A (período 4) e B (período 6). No Rate Monotonic, quem tem maior prioridade?
RTOS controlando um drone
Num drone, o laço de estabilização precisa rodar a, digamos, 500 Hz (período 2 ms), enquanto a telemetria roda a 10 Hz (100 ms). Sob Rate Monotonic, a estabilização — período menor — recebe prioridade maior automaticamente, garantindo que nunca seja preterida pela telemetria.
Antes do voo, calcula-se a utilização total. Se U exceder o limite de RM, ou se reduz a carga, ou se migra para EDF, ou se adiciona um core. Errar isso significa o drone perder o prazo de controle e cair — tempo real no sentido literal.
Onde os alunos erram
• Inverter a regra do RM — é menor período que ganha maior prioridade, não o contrário.
• Tratar o limite de 69% do RM como "necessário" — é apenas suficiente.
• Esquecer o custo da troca de contexto ao calcular a utilização real (o C de cada tarefa deve incluí-lo).
Calculando à mão sem erro
Revele o cálculo
Tarefas (C,T): A(1,4), B(2,6). A utilização permite RM? E EDF?
Revisão relâmpago
Como isto se encaixa
O escalonamento conecta:
- A preempção com o timer e as interrupções (Aula 2).
- O custo do quantum com a troca de contexto (Aula 3).
- O tempo real com a inversão de prioridade (Aula 6), que pode arruinar as garantias de RM/EDF.
Resumo da aula
Simulador: escalonamento clássico
O simulador de escalonamento permite inserir processos com tempos de chegada e de surto e comparar FCFS, SJF e Round-Robin lado a lado.
Simulador: tempo real (RM e EDF)
O simulador de tempo real mostra tarefas periódicas sendo escalonadas por Rate Monotonic e EDF, evidenciando se cada prazo é cumprido ou perdido.
Atividade em grupo · Torneio de escalonadores
Em grupos, escalonem o mesmo conjunto de processos por vários algoritmos e comparem.
Roteiro
- Recebam 4 processos com tempos de chegada e de surto definidos.
- Calculem o diagrama de Gantt e o tempo médio de espera para FCFS, SJF e RR (quantum 2).
- Confiram os resultados no simulador de escalonamento.
- Para um conjunto periódico, testem RM e EDF no simulador de tempo real e vejam se há perda de prazo.
Mini-quiz · Aula 5
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- FCFS é simples mas sofre efeito comboio; SJF minimiza a espera média.
- Round-Robin equilibra resposta e overhead via quantum.
- Rate Monotonic usa prioridade estática por período; EDF, dinâmica por prazo.
- EDF é ótimo em uniprocessador (até 100%); RM é mais simples e previsível.
- O teste de utilização decide a escalonabilidade; o limite do RM (~69%) é suficiente.