Aula 5 · Escalonamento de processos

Objetivos da aula

O que você vai aprender

Listar os critérios de avaliação de algoritmos de escalonamento.

Aplicar FCFS, SJF, Round-Robin e prioridades.

Entender filas multinível e o escalonamento preemptivo.

Calcular tempos de espera e de retorno e interpretar trade-offs.

1 · Motivação

Quem usa a CPU agora?

Há sempre mais processos prontos do que CPUs disponíveis. Alguém precisa decidir, a cada instante, quem roda. Essa decisão é do escalonador, e ela afeta diretamente o desempenho que você sente.

Um bom escalonamento mantém a CPU ocupada, dá respostas rápidas aos programas interativos e evita que processos esperem para sempre. Não existe algoritmo perfeito — há trade-offs, e hoje vamos compará-los, inclusive no simulador.

2 · Mapa

O que veremos nesta aula

Critérios→FCFS /
SJF→Prioridades→Round-
Robin→Multinível +
simulador

💡

Pergunta central: o algoritmo pode preemptar (interromper) um processo em execução, ou só troca quando ele libera a CPU?

3 · Conceito

Critérios de avaliação

Escalonador. Componente do SO que escolhe, entre os processos prontos, qual recebe a CPU.

Critério	Significado	Objetivo
Utilização da CPU	% de tempo ocupada	Maximizar
Vazão (throughput)	Processos concluídos por unidade de tempo	Maximizar
Tempo de retorno	Da chegada ao término	Minimizar
Tempo de espera	Tempo na fila de prontos	Minimizar
Tempo de resposta	Até a primeira resposta	Minimizar

4 · Conceito

Preemptivo × não preemptivo

Escalonamento preemptivo. Pode interromper um processo em execução e dar a CPU a outro (ex.: por fim de quantum).
Não preemptivo. Só troca quando o processo libera a CPU voluntariamente (termina ou bloqueia).

🔑

Preempção é o que viabiliza tempo compartilhado e boa resposta interativa, ao custo de mais trocas de contexto.

5 · Exemplo

FCFS e o efeito comboio

FCFS (First-Come, First-Served): atende por ordem de chegada. Considere P1=24, P2=3, P3=3 chegando juntos:

// ordem FCFS: P1, P2, P3 P1: 0..24 espera 0 P2: 24..27 espera 24 P3: 27..30 espera 27 // espera média = (0+24+27)/3 = 17

Os curtos esperam atrás do longo: é o efeito comboio.

6 · Interativo

Stepper: calculando o tempo de espera no SJF

Passo 1

SJF ordena pelo menor tempo: P2 (3), P3 (3), P1 (24).

Passo 2

Esperas: P2=0, P3=3, P1=6.

Passo 3

Espera média = (0+3+6)/3 = 3 — bem menor que os 17 do FCFS.

Passo 4

Conclusão: rodar os curtos primeiro reduz a espera média. Esse é o ganho do SJF.

7 · Conceito

SJF (Shortest Job First)

SJF. Executa primeiro o processo com menor tempo de CPU. É ótimo no tempo médio de espera.

Problemas: exige prever a duração de cada processo (impossível com exatidão) e pode causar inanição de processos longos se sempre chegarem curtos. A versão preemptiva é o SRTF (Shortest Remaining Time First).

8 · Conceito

Escalonamento por prioridades

Prioridades. Cada processo tem uma prioridade; executa o de maior prioridade entre os prontos.

SJF é um caso particular (prioridade = inverso do tempo). O risco é a inanição: processos de baixa prioridade podem nunca rodar. A solução é o envelhecimento (aging): a prioridade sobe com o tempo de espera.

⚠️

Inanição (starvation): um processo pode esperar indefinidamente se sempre houver outros com prioridade maior. O aging aumenta a prioridade conforme a espera cresce.

9 · Analogia

O pronto-socorro

🏥 Analogia

FCFS é a fila por ordem de chegada. SJF atende primeiro quem leva menos tempo (curativo rápido antes de uma cirurgia). Prioridades é a triagem: casos graves passam na frente — mas, sem envelhecimento, um caso leve pode esperar para sempre. O aging é dar prioridade a quem já espera há muito tempo.

10 · Comparação

Visão geral dos algoritmos

Algoritmo	Preemptivo?	Ponto forte	Ponto fraco
FCFS	Não	Simples e justo na ordem	Efeito comboio
SJF	Não (SRTF: sim)	Mínimo tempo médio de espera	Precisa prever; inanição
Prioridades	Pode ser	Atende o importante primeiro	Inanição (sem aging)
Round-Robin	Sim	Bom tempo de resposta	Overhead de troca de contexto

11 · Flow

Round-Robin em ação

O Round-Robin (RR) dá a cada processo um quantum e alterna circularmente — ideal para tempo compartilhado.

P1
quantum→P2
quantum→P3
quantum→P1
...

12 · Aprofundamento

O quantum e o multinível

💡

Quantum muito grande → RR vira FCFS; quantum muito pequeno → muita troca de contexto (overhead). O escalonamento multinível usa várias filas com prioridades e algoritmos diferentes; o multinível com realimentação move processos entre filas conforme o comportamento (quem usa muito a CPU desce; quem é interativo sobe).

13 · Interativo

Verifique: quantum grande

No Round-Robin, um quantum muito grande faz o algoritmo se comportar como:

Com quantum enorme, cada processo roda quase até o fim antes de trocar: vira FCFS.

14 · Caso prático

Round-Robin com quantum 3

Processos P1=8, P2=4, chegando juntos, quantum=3:

// linha do tempo (RR, q=3) 0-3 P1 3-6 P2 6-9 P1 9-10 P2(resta 1) 10-13 P1 13-15 P1(resta 2 -> termina em 15) // P2 termina em 10; P1 termina em 15

O RR intercala os processos, melhorando o tempo de resposta, mas com mais trocas.

15 · Erros comuns

Onde os cálculos erram

⚠️

Cuidado:
• Tempo de espera ≠ tempo de retorno: retorno = término − chegada; espera = retorno − tempo de CPU.
• SJF minimiza a espera média, não necessariamente a de cada processo individual.
• No RR, não esqueça de recolocar o processo no fim da fila ao esgotar o quantum.

16 · Dicas

Estratégia para resolver exercícios

✅

Dicas:
• Sempre desenhe a linha do tempo (diagrama de Gantt) antes de calcular.
• Anote término de cada processo; daí saem retorno e espera.
• Para RR, marque o quantum e a fila a cada troca.
• Confira tudo no simulador desta aula.

17 · Interativo

Revele: SJF e previsão

Se o SJF é ótimo, por que não é simplesmente usado em todo SO?

Porque o SJF exige saber de antemão quanto tempo de CPU cada processo vai usar — e isso é impossível de prever com exatidão. Na prática, estima-se a próxima rajada com base no histórico (médias exponenciais), o que é apenas aproximado. Além disso, o SJF puro pode causar inanição de processos longos. Por isso os SOs reais usam combinações, como filas multinível com realimentação.

18 · Flashcards

Revisão relâmpago

Efeito comboiovirar

No FCFS, processos curtos esperam atrás de um processo longo.

Quantumvirar

Fatia de tempo que o RR dá a cada processo antes de trocar.

Inaniçãovirar

Processo que espera indefinidamente; combatida com envelhecimento (aging).

Tempo de retornovirar

Término menos chegada do processo.

19 · Simulador

Mãos à obra no simulador

Hora de praticar: abra o simulador de escalonamento de CPU abaixo e compare FCFS, SJF e Round-Robin sobre o mesmo conjunto de processos.

Observe como o tempo médio de espera muda entre os algoritmos.
Force o efeito comboio colocando um processo bem longo primeiro no FCFS.
Varie o quantum no RR e veja o impacto nas trocas de contexto e na resposta.

20 · Conexões

Para onde isto leva

O timer que preempta usa interrupções → Aula 2.
Quem é escalonado são processos/threads → Aulas 3 e 4.
Trocas de contexto aparecem aqui como custo → Aula 3.
Prova 1 cobrará cálculos de espera/retorno → Aula 7.

21 · Síntese

Fechando a aula

🔑

Em uma frase: o escalonador escolhe o próximo processo segundo critérios como espera e retorno; FCFS é simples mas sofre comboio, SJF minimiza a espera média mas exige previsão, RR dá boa resposta via quantum, e filas multinível com aging combinam o melhor de cada um.

Mão na massa · colaborativo

Atividade em grupo · Torneio de escalonadores

Em grupos, calculem e comparem métricas de diferentes algoritmos.

⏱️ 30 min👥 grupos de 3–4🧩 laboratório

Roteiro

Recebam 4 processos com tempos de chegada e de CPU (ex.: P1=8, P2=4, P3=9, P4=5).
Calculem o tempo médio de espera para FCFS e para SJF.
Calculem para Round-Robin com quantum 3.
Confiram no simulador da aula e discutam qual venceu e por quê.

Calculista FCFS/SJFfaz as contas dos não preemptivos

Calculista RRmonta a linha do tempo do RR

Conferentevalida no simulador

📤 Entrega: Tabela comparando o tempo médio de espera dos três algoritmos.

Teste seu conhecimento

Mini-quiz · Aula 5

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova

O escalonador escolhe o próximo processo segundo critérios como espera, retorno, resposta e vazão.
FCFS é simples mas sofre efeito comboio; SJF minimiza a espera média mas exige previsão e pode causar inanição.
Round-Robin usa quantum e é ideal para tempo compartilhado; quantum grande vira FCFS, pequeno gera overhead.
Prioridades atendem o importante primeiro; aging evita inanição.
Filas multinível com realimentação combinam vários algoritmos adaptando-se ao comportamento.