Aula 12 — Escalonamento de Processos

Objetivos

Ao final desta aula você deve ser capaz de:

• Descrever os três níveis de scheduling (longo, médio e curto prazo) e o papel do dispatcher.
• Calcular tempo de espera, turnaround e tempo de resposta para FIFO, SJF (preemptivo e não-preemptivo), Prioridades e Round-Robin a partir de um conjunto de processos.
• Construir gráficos de Gantt para cada algoritmo.
• Explicar convoy effect (FIFO), starvation (Prioridades) e como aging resolve o segundo.
• Descrever filas multiníveis com retroalimentação e identificar como o sistema classifica processos automaticamente.
• Explicar scheduling por loteria e por fração justa, e quando cada um é preferível.
• Descrever o Completely Fair Scheduler (CFS) do Linux com conceito de vruntime.

---

Conteúdo

Os três níveis de scheduling

Jobs no disco / lote
       │  ← Scheduler de LONGO PRAZO (admissão)
       ▼      Decide quais jobs entram na memória
  Memória principal
  (processos ativos)
       │  ← Scheduler de MÉDIO PRAZO (swapping)
       ▼      Move processos entre memória e disco (swapout/swapin)
  Fila de Prontos
       │  ← Scheduler de CURTO PRAZO (CPU scheduler + dispatcher)
       ▼      Escolhe qual processo recebe a CPU agora
     CPU

Nível	Frequência	Decisão
Longo prazo	Minutos	Qual job admitir no sistema (grau de multiprogramação)
Médio prazo	Segundos	Qual processo fazer swap para disco e trazer de volta
Curto prazo	Milissegundos	Qual processo pronto recebe a CPU agora

Dispatcher: o módulo do SO que efetivamente dá a CPU ao processo selecionado pelo scheduler de curto prazo. Executa a mudança de contexto, salva/restaura PCB, altera modo de execução (kernel→usuário). A latência de despacho é o overhead dessa operação — deve ser mínima.

---

Critérios de scheduling

Critério	Definição	Objetivo
Utilização da CPU	% do tempo com CPU ocupada	Maximizar (tipicamente 40–90%)
Throughput	Processos concluídos por unidade de tempo	Maximizar
Tempo de turnaround	Instante de conclusão − instante de submissão	Minimizar
Tempo de espera	Tempo total na fila de prontos	Minimizar
Tempo de resposta	Tempo entre submissão e primeira resposta	Minimizar (sistemas interativos)

Fórmulas:

Tempo de turnaround = instante de conclusão − instante de chegada
Tempo de espera     = turnaround − tempo de pico de CPU total
Tempo de resposta   = instante da primeira CPU − instante de chegada

---

Preempção: cooperativo vs. preemptivo

• Sem preempção (cooperativo): um processo ocupa a CPU até bloquear voluntariamente (I/O) ou terminar. Sem timer de interrupção. Simples mas injusto.
• Com preempção: o SO pode retirar a CPU do processo via timer (quantum expirado) ou quando um processo de prioridade maior chega. Necessita hardware de timer. Padrão em todos os SOs modernos.

---

Algoritmo 1: FIFO / FCFS — First Come, First Served

Regra: processa na ordem de chegada. Não-preemptivo.

Exemplo: P1(chegada=0, pico=24), P2(chegada=0, pico=3), P3(chegada=0, pico=3).

Gráfico de Gantt — FIFO:
│ P1 (24ms) │ P2 (3ms) │ P3 (3ms) │
0          24         27         30
 
Tempos de espera:
  P1: 0ms  |  P2: 24ms  |  P3: 27ms
  Média: (0 + 24 + 27) / 3 = 17ms

Convoy effect: se P2 e P3 chegassem primeiro (pico=3 cada):

│ P2 │ P3 │    P1 (24ms)      │
0    3    6                  30
 
Tempos de espera: P2=0, P3=3, P1=6 → média = 3ms

O processo longo (P1) "bloqueava o corredor" — por isso FIFO sofre com o convoy effect: processos curtos ficam presos atrás de um processo longo, degradando o tempo de resposta do sistema inteiro.

Resumo FIFO:

• ✓ Simples, sem starvation
• ✗ Convoy effect, alto tempo de espera médio para cargas mistas

---

Algoritmo 2: SJF — Shortest Job First

Regra: executa o processo com menor pico de CPU previsto. Ótimo para minimizar tempo de espera médio, mas requer conhecer o pico de antemão.

Previsão por média exponencial:

tau_(n+1) = alpha * t_n + (1 - alpha) * tau_n

Onde $t_n$ = pico atual medido, $\tau_n$ = previsão anterior, $\alpha \in [0,1]$ (tipicamente 0,5).

SJF Não-Preemptivo

Não interrompe o processo em execução mesmo se chegar um processo mais curto.

Exemplo: P1(cheg=0, pico=8), P2(cheg=1, pico=4), P3(cheg=2, pico=9), P4(cheg=3, pico=5).

Gráfico de Gantt — SJF não-preemptivo:
│  P1  (8)  │  P2 (4)  │  P4 (5)   │   P3 (9)    │
0           8         12          17             26
 
Esperas: P1=0, P2=7, P3=15, P4=9 → média = 7,75ms

SJF Preemptivo (SRTF — Shortest Remaining Time First)

Interrompe o processo atual se chegar um processo com pico restante menor.

Gráfico de Gantt — SRTF:
│P1│  P2(4)  │  P4(5)   │ P1 rest │    P3(9)     │
0  1        5          10        17             26
  P2 preempta P1 (4<7 restantes)
              P4 preempta (5 restantes < P1's 7)
 
Esperas: P1=(10-1)=9? … calculo correto:
  P1: termina em 17, chegou em 0, pico=8 → espera=17-0-8=9
  P2: termina em 5, chegou em 1, pico=4  → espera=0
  P3: termina em 26, chegou em 2, pico=9 → espera=26-2-9=15
  P4: termina em 10, chegou em 3, pico=5 → espera=10-3-5=2
  Média: (9+0+15+2)/4 = 6,5ms  (melhor que SJF não-preemptivo!)

Resumo SJF/SRTF:

• ✓ Ótimo para minimizar tempo médio de espera
• ✗ Requer previsão do pico (não sempre possível), starvation de processos longos

---

Algoritmo 3: Scheduling por Prioridades

Regra: cada processo tem uma prioridade; a CPU vai para o de maior prioridade. Pode ser preemptivo ou não.

Exemplo: todos chegam em t=0. P1(pico=10, pri=3), P2(pico=1, pri=1), P3(pico=2, pri=4), P4(pico=1, pri=5), P5(pico=5, pri=2). Convenção: menor número = maior prioridade.

Gráfico de Gantt — Prioridades:
│P2│  P5  │     P1      │ P3 │P4│
0  1      6            16  18  19
 
Tempo médio de espera = 8,2ms

Starvation: em sistemas carregados, processos de baixa prioridade podem esperar indefinidamente se processos de alta prioridade chegam continuamente.

Aging (envelhecimento): aumenta gradualmente a prioridade de processos que esperam há muito tempo. Garante que todo processo eventualmente execute. Ex.: incrementar prioridade em 1 a cada 15 minutos.

---

Algoritmo 4: Round-Robin (RR)

Regra: fila circular + quantum de tempo $q$. Cada processo recebe no máximo $q$ unidades de CPU antes de ser preemptado e colocado no fim da fila.

Exemplo: P1(pico=24), P2(pico=3), P3(pico=3), quantum=4.

Gráfico de Gantt — RR (q=4):
│P1(4)│P2(3)│P3(3)│P1(4)│P1(4)│P1(4)│P1(4)│P1(4)│
0     4     7    10    14    18    22    26    30
 
Esperas: P1=6, P2=4, P3=7 → média=5,66ms

Efeito do tamanho do quantum:

Quantum	Comportamento	Problema
Muito pequeno (→0)	Aparência de paralelismo perfeito	Overhead de context switch domina
Muito grande (→∞)	Degenera em FIFO	Resposta interativa piora
Ideal	80% dos picos termina em 1 quantum	Equilíbrio resposta/overhead

Regra prática: quantum deve ser maior que o tempo de mudança de contexto em pelo menos 10×. Sistemas modernos: 10–100ms.

Resumo RR:

• ✓ Justo (sem starvation), bom tempo de resposta interativo
• ✗ Tempo médio de espera maior que SJF, overhead de context switch

---

Algoritmo 5: Filas Multiníveis

Regra: múltiplas filas com prioridade fixa, cada uma com seu próprio algoritmo.

Fila 1 — Sistema         (prioridade máxima) → FCFS
Fila 2 — Interativos     (prioridade alta)   → RR q=8ms
Fila 3 — Edição interativa                  → RR q=16ms
Fila 4 — Batch           (prioridade baixa)  → FCFS
Fila 5 — Estudantes      (prioridade mínima) → FCFS

Processos são atribuídos permanentemente a uma fila. Fila de maior prioridade sempre esvazia antes da menor executar.

Alternativa com time slice entre filas: ex., fila 1 recebe 80% da CPU, fila 2 recebe 20% — mesmo se fila 1 não estiver vazia.

---

Algoritmo 6: Filas Multiníveis com Retroalimentação (MLFQ)

Regra: processos podem mover entre filas baseado no comportamento — a grande inovação em relação às filas estáticas. É o algoritmo mais próximo dos SOs reais.

Exemplo com 3 filas:

Fila 0: RR q=8ms   (maior prioridade)
Fila 1: RR q=16ms
Fila 2: FIFO       (menor prioridade)
 
Comportamento:
  Novo processo → entra na Fila 0
  Usa todo o quantum de 8ms → rebaixado para Fila 1
  Usa todo o quantum de 16ms → rebaixado para Fila 2
  Bloqueia por I/O antes do quantum → permanece na mesma fila (ou promovido)
 
  Espera muito na Fila 2 → envelhecimento promove para Fila 1 (aging)

Lógica: processos CPU-bound (longos picos) naturalmente descem para filas de menor prioridade. Processos I/O-bound (picos curtos, interativos) ficam nas filas altas com boa resposta.

Parâmetros configuráveis:

• Número de filas
• Algoritmo de scheduling de cada fila
• Critério de rebaixamento (quando vai para fila menor)
• Critério de promoção (aging — quando volta para fila maior)
• Fila de entrada para novos processos

Resumo MLFQ:

• ✓ Se adapta automaticamente ao comportamento do processo, sem informação prévia
• ✓ Aging evita starvation
• ✗ Mais complexo de configurar e implementar

---

Algoritmo 7: Scheduling por Loteria

Regra: cada processo recebe um número de "bilhetes de loteria". O scheduler sorteia um bilhete aleatoriamente — o processo dono do bilhete sorteado recebe a CPU.

Processo A: 30 bilhetes (30% do tempo de CPU esperado)
Processo B: 20 bilhetes (20%)
Processo C: 50 bilhetes (50%)
Total: 100 bilhetes
 
Sorteio: número aleatório 1-100 → se 1-30: A vence; 31-50: B; 51-100: C

Propriedades:

• Probabilístico: em média, cada processo recebe CPU proporcional aos seus bilhetes.
• Cooperação: um processo pode transferir bilhetes temporariamente para outro (ex.: cliente dá bilhetes ao servidor enquanto espera).
• Sem starvation: todo processo com ao menos 1 bilhete tem chance de ser sorteado.
• Simples de implementar (sem estruturas complexas de prioridade).

Uso: sistemas de pesquisa, VMs que precisam garantir cotas de CPU a grupos.

---

Algoritmo 8: Scheduling por Fração Justa (Fair Share)

Regra: garante que cada usuário (ou grupo) receba uma fração predefinida da CPU, independentemente de quantos processos cada um tem.

Usuário A tem 50% da CPU; Usuário B tem 50%.
A tem 1 processo; B tem 4 processos.
 
Sem fair share: cada processo recebe 20% → A=20%, B=80% (injusto para A).
Com fair share: A=50%, B=50%. Dentro de B, cada um de seus 4 processos recebe 12,5%.

Implementação: o scheduler rastreia o uso acumulado de CPU por usuário. Prioriza usuários que estão abaixo da sua fração garantida.

---

O CFS do Linux — Completely Fair Scheduler

O Linux usa o CFS desde a versão 2.6.23. Sua filosofia: garantir que cada processo execute por uma fração igual de tempo de CPU, independentemente do número de processos.

Conceito central: vruntime

vruntime = tempo de execução real × fator_de_decaimento(prioridade)

• Processo com prioridade alta (nice=-20): vruntime cresce mais devagar → recebe mais CPU.
• Processo com prioridade baixa (nice=+19): vruntime cresce mais rápido → recebe menos CPU.
• Processo que bloqueia (I/O-bound): vruntime para de crescer → acumula "crédito" → quando volta, tem o menor vruntime → alta prioridade para executar.

Seleção do próximo processo:

O CFS sempre executa o processo com menor vruntime.
Implementação: árvore rubro-negra (red-black tree) ordenada por vruntime.
  → inserção/remoção O(log N)
  → seleção do mínimo O(1) (rb_leftmost em cache)

latência-alvo: intervalo de tempo em que todos os processos executam pelo menos uma vez. Com N processos, cada um recebe latência-alvo / N.

Valores nice no Linux:

nice	Prioridade	Proporção de CPU
-20	Máxima	~10× mais que nice=0
0	Padrão	Normal
+19	Mínima	~10× menos que nice=0

# Atividade prática rápida: observar scheduling em ação
ps -eo pid,ni,stat,comm,pcpu --sort=-pcpu | head -20
# nice: valor de prioridade (-20 a +19)
# stat: R=running, S=sleeping, D=disk wait
 
# Mudar nice de um processo:
nice -n 10 ./meu_programa     # executa com nice=10
renice -n 5 -p 1234           # muda nice do PID 1234 para 5

---

Scheduling de Threads — PCS vs. SCS

Escopo	Nome	Competes	Algoritmo
PCS (Process Contention Scope)	Scheduling no nível do processo	Entre threads do mesmo processo	Biblioteca pthreads (espaço do usuário)
SCS (System Contention Scope)	Scheduling no nível do sistema	Todos os threads do sistema	Kernel do SO

No modelo 1:1 (Linux, Windows): todos os threads competem via SCS — são threads de kernel escalonados pelo kernel diretamente.

---

Tabela comparativa dos algoritmos

Algoritmo	Preemptivo	Starvation	Convoy Effect	Complexidade	Melhor para
FIFO/FCFS	Não	Não	Sim	O(1)	Batch simples
SJF	Não	Sim (longo)	Não	O(N)	Mínimo de espera médio
SRTF	Sim	Sim (longo)	Não	O(N)	Mínimo de espera médio com chegadas
Prioridades	Ambos	Sim	Não	O(N)	Sistemas com classes de processo
Round-Robin	Sim	Não	Não	O(1)	Sistemas interativos/time-sharing
Filas Multiníveis	Ambos	Possível	Não	O(N×k)	Cargas mistas (interativo + batch)
MLFQ	Sim	Com aging: não	Não	O(N×k)	SO de propósito geral
Loteria	Sim	Não	Não	O(1)	Cotas proporcionais
CFS (Linux)	Sim	Não	Não	O(log N)	Propósito geral, fairness

---

Exercícios

Questões dissertativas

Q1

Explique os três níveis de scheduling e o papel do dispatcher. Por que a latência de despacho deve ser minimizada?

Q2

Calcule o tempo médio de espera e turnaround para FIFO e SJF não-preemptivo com os processos: P1(chegada=0, pico=6), P2(chegada=2, pico=2), P3(chegada=4, pico=8), P4(chegada=5, pico=3). Construa os gráficos de Gantt.

Q3

O que é convoy effect no FIFO? Descreva um cenário concreto onde ele degrada severamente o desempenho do sistema.

Q4

Calcule o tempo médio de espera para Round-Robin com quantum=3 para: P1(chegada=0, pico=5), P2(chegada=1, pico=4), P3(chegada=2, pico=2), P4(chegada=4, pico=1).

Q5

Explique como o MLFQ classifica automaticamente processos CPU-bound e I/O-bound em filas diferentes. Por que isso é vantajoso?

Q6

Compare scheduling por loteria com scheduling por prioridade fixas. Quando a loteria é preferível? Qual desvantagem ela tem?

Q7

Explique o conceito de vruntime no CFS do Linux. Por que processos I/O-bound naturalmente ganham prioridade sem nenhuma configuração especial?

Q8

Por que o SJF é considerado 'ótimo' para minimizar o tempo médio de espera? Prove intuitivamente com um exemplo simples.

Q9Difícil

Dado que o Linux usa CFS com uma árvore rubro-negra para armazenar processos ordenados por vruntime, qual é a complexidade de: (a) selecionar o próximo processo, (b) inserir um novo processo, (c) remover um processo bloqueado?

Q10Difícil

Por que scheduling de threads de usuário (PCS) não é suficiente para aproveitar sistemas multicore? O que o SCS oferece que PCS não pode?

---

Quiz de múltipla escolha

Quiz10 questões

1. Três processos chegam ao mesmo tempo t=0: P1(pico=10), P2(pico=1), P3(pico=5). Com FIFO nessa ordem (P1, P2, P3), qual é o tempo médio de espera?

• a)3,67ms
• b)7,0ms
• c)5,0ms
• d)11,0ms
• e)4,0ms

2. No SJF não-preemptivo, qual propriedade ele garante que FIFO não garante?

• a)Ausência de starvation para todos os processos
• b)Tempo médio de espera mínimo entre algoritmos não-preemptivos
• c)Tempo de resposta mínimo para sistemas interativos
• d)Throughput máximo em qualquer carga
• e)Preempção automática de processos longos

3. Round-Robin com quantum muito pequeno (→ 0) aproxima-se de qual comportamento teórico?

• a)FIFO — processos executam na ordem de chegada
• b)SJF — processos curtos executam primeiro
• c)Processador compartilhado — todos os N processos executam a 1/N da velocidade do processador simultaneamente
• d)Prioridade — processos de maior prioridade dominam
• e)MLFQ — processos são promovidos automaticamente

4. Aging é uma solução para qual problema específico?

• a)Convoy effect no FIFO
• b)Alto overhead de context switch no RR
• c)Starvation de processos de baixa prioridade em scheduling por prioridades
• d)Dificuldade de prever picos de CPU no SJF
• e)Overhead de árvore no CFS

5. No MLFQ com 3 filas (q0=8, q1=16, q2=FIFO), um processo CPU-bound chega. Em qual fila ele estará após executar por 30ms total?

• a)Fila 0 — processos CPU-bound têm prioridade alta
• b)Fila 1 — usou mais que 8ms mas menos que 16ms
• c)Fila 2 — usou mais que 8+16=24ms total, foi rebaixado para FIFO
• d)Fila 0 novamente — aging promoveu de volta
• e)Removido do sistema — processos CPU-bound são eliminados

6. No CFS do Linux, por que um processo interativo (I/O-bound) responde tão rapidamente quando acorda?

• a)O CFS usa prioridade estática alta para processos interativos
• b)Enquanto bloqueado em I/O, o vruntime do processo para de crescer — quando acorda, tem o menor vruntime do sistema e é imediatamente selecionado
• c)O kernel reserva 10% da CPU exclusivamente para processos interativos
• d)Processos interativos têm quantum maior no CFS
• e)O CFS usa uma fila separada de alta prioridade para processos de I/O

7. Qual a principal vantagem do scheduling por loteria sobre scheduling por prioridade fixa para um hypervisor que gerencia VMs de múltiplos clientes?

• a)Loteria é mais determinístico — as VMs sabem exatamente quando terão CPU
• b)Loteria garante cotas proporcionais: uma VM com 2× mais bilhetes recebe 2× mais CPU em média, sem starvation para nenhuma VM
• c)Loteria é mais simples de implementar que prioridade no hypervisor
• d)Loteria elimina overhead de context switch entre VMs
• e)Loteria permite que VMs se comuniquem mais rapidamente

8. SJF não-preemptivo vs. SRTF (SJF preemptivo): qual garante menor tempo médio de espera quando há processos chegando em momentos diferentes?

• a)SJF não-preemptivo — evita overhead de preempção
• b)São equivalentes — a preempção não afeta o tempo médio
• c)SRTF — pode explorar processos curtos que chegam depois, reduzindo o tempo médio
• d)Depende do quantum escolhido
• e)FIFO é melhor quando há chegadas em momentos diferentes

9. Qual algoritmo é mais adequado para um sistema de tempo compartilhado (time-sharing) como um servidor SSH com múltiplos usuários interativos?

• a)FIFO — simples e previsível
• b)SJF — processa as requisições mais rápidas primeiro
• c)Round-Robin — divide o tempo igualmente entre todos os usuários, sem starvation
• d)Prioridades sem aging — usuários VIP têm sempre prioridade
• e)MLFQ com apenas 1 fila — equivale a FIFO com preempção

10. Um processo P usa renice para mudar seu nice de 0 para +15 no Linux. Qual o efeito no scheduling CFS?

• a)P é imediatamente removido do sistema pelo kernel
• b)O vruntime de P passa a crescer mais rápido que o normal → P recebe proporcionalmente menos CPU que processos com nice=0
• c)P passa para uma fila de menor prioridade permanentemente, sem poder voltar
• d)O quantum de P é aumentado para compensar a menor prioridade
• e)Nenhum efeito — nice só afeta prioridade em sistemas SJF

---

Referências

Principais (essenciais)

• SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
  • §3.2 — Scheduling de Processos (filas, scheduler de curto prazo, dispatcher)
  • §6.1 — Conceitos Básicos (ciclo CPU-I/O, preempção)
  • §6.2 — Critérios de Scheduling
  • §6.3 — Algoritmos (FIFO, SJF, Prioridades, RR, Filas Multiníveis, MLFQ)
  • §6.4 — Scheduling de Threads (PCS, SCS)
  • §6.7 — Exemplos de SOs (CFS Linux, Windows)

Aprofundamento (opcionais)

• TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016. §2.4 — Scheduling.
• WALDSPURGER, C.; WEIHL, W. Lottery Scheduling: Flexible Proportional-Share Resource Management. USENIX OSDI, 1994.
• man 1 nice, man 2 sched_setscheduler — referência Linux para CFS e classes de scheduling.

---

Recursos Complementares

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

▶18:10

ENOpcional

CPU Scheduling — FCFS Algorithm

Neso Academy

FIFO/FCFS com exemplos resolvidos. Cobre §6.3.1 do Silberschatz.

▶15:05

ENOpcional

Round Robin Scheduling

Neso Academy

Round-Robin com exemplos e análise do tamanho do quantum. Cobre §6.3.4.