Na aula de hoje, mergulhamos no coração do gerenciamento de processos de um sistema operacional: o escalonador de CPU. Vimos que o objetivo principal do escalonamento é maximizar a utilização da CPU e o throughput — a quantidade de processos completados por unidade de tempo — enquanto minimiza o tempo de turnaround (tempo total de execução de um processo), o tempo de espera (tempo que o processo passa na fila de prontos) e o tempo de resposta (tempo até a primeira resposta do processo). A escolha do algoritmo certo depende do tipo de sistema: batch, interativo ou tempo real.

Métricas de Desempenho Essenciais

Antes de analisarmos os algoritmos em si, estabelecemos as quatro métricas fundamentais que guiam a avaliação do escalonador:

  • Utilização da CPU: manter a CPU ocupada o máximo possível. Em um sistema realista, a utilização deve ficar entre 40% (sistema ocioso) e 90%+ (sistema sobrecarregado).
  • Throughput: número de processos completados por unidade de tempo. Em sistemas de longa execução, medimos quantos jobs são finalizados por hora.
  • Tempo de Turnaround: intervalo entre a submissão do processo e sua finalização completa. Inclui todo o tempo de execução, espera na fila de prontos, operações de E/S, etc.
  • Tempo de Espera: soma do tempo que o processo passa na fila de prontos aguardando a CPU. Ignora o tempo efetivo de execução e E/S.
  • Tempo de Resposta: tempo desde a submissão até a primeira resposta visível do processo. Crítico para sistemas interativos.

Não existe um algoritmo que otimize todas essas métricas simultaneamente; o projetista do sistema precisa fazer trade-offs de acordo com o objetivo do ambiente.

FCFS — First-Come, First-Served

O algoritmo mais simples de todos. A fila de prontos é tratada como uma fila FIFO: o primeiro processo a chegar é o primeiro a ser executado, e a execução segue sem preempção até que o processo termine ou solicite uma operação de E/S. Quando um processo libera a CPU, o próximo da fila assume.

Vantagens: implementação trivial, ausência de starvation (todo mundo eventualmente executa) e baixo overhead de contexto. Desvantagens: o tempo médio de espera pode ser muito alto, especialmente se um processo longo chegar antes de vários processos curtos — o conhecido efeito comboio (convoy effect).

Exemplo clássico de cálculo:

Processos: P1 (24ms), P2 (3ms), P3 (3ms)
          Ordem de chegada: P1, P2, P3
          Tempo de espera: P1 = 0ms, P2 = 24ms, P3 = 27ms
          Tempo médio de espera: (0 + 24 + 27) / 3 = 17ms

Se a ordem fosse P2, P3, P1, o tempo médio de espera cairia drasticamente para (0 + 3 + 6) / 3 = 3ms. Isso mostra como o FCFS é sensível à ordem de chegada.

SJF — Shortest Job First

No SJF (não-preemptivo), quando a CPU fica livre, o processo com o menor próximo burst de CPU é selecionado na fila de prontos. Na versão preemptiva — chamada de SRTF (Shortest Remaining Time First) —, se um novo processo chegar com um burst menor do que o que resta do processo atual, a CPU é desalocada e o novo processo assume.

O SJF é teoricamente ótimo em termos de tempo médio de espera para um dado conjunto de processos, mas sofre de um problema grave: é impossível saber exatamente a duração do próximo burst na prática. Os sistemas operacionais utilizam previsões baseadas em médias exponenciais dos bursts anteriores. Além disso, processos longos podem sofrer starvation (inanição) se houver uma corrente contínua de processos curtos.

Exemplo SJF não-preemptivo:

Processos: P1 (8ms), P2 (4ms), P3 (9ms), P4 (5ms)
          Ordem SJF: P2, P4, P1, P3
          Tempo de espera: P2 = 0ms, P4 = 4ms, P1 = 9ms, P3 = 17ms
          Tempo médio: (0 + 4 + 9 + 17) / 4 = 7.5ms

No FCFS, considerando a ordem P1, P2, P3, P4, o tempo médio seria de (0 + 8 + 12 + 21) / 4 = 10.25ms. O ganho do SJF é evidente.

Round Robin (RR)

O Round Robin foi projetado especificamente para sistemas interativos e time-sharing. Cada processo recebe um pequeno intervalo de tempo de CPU chamado quantum (ou fatia de tempo), geralmente entre 10ms e 100ms. Ao final do quantum, se o processo ainda estiver em execução, a CPU é preemptada e o processo volta para o final da fila de prontos. Um novo processo é então selecionado do início da fila.

O desempenho do RR depende fortemente do tamanho do quantum:

  • Quantum muito grande: o algoritmo degenera em FCFS, prejudicando o tempo de resposta.
  • Quantum muito pequeno: o overhead de chaveamento de contexto (context switch) se torna significativo, reduzindo o throughput. Se o quantum for menor do que o tempo de chaveamento, a CPU passa mais tempo trocando de contexto do que executando.

Uma regra prática é que o quantum deve ser maior do que 80% dos bursts de CPU, mas ainda pequeno o suficiente para garantir boa responsividade. O RR oferece o melhor tempo de resposta médio entre os algoritmos clássicos, além de ser justo: todos os processos recebem uma fatia igual de CPU ao longo do tempo.

Escalonamento por Prioridades

Neste algoritmo, um número de prioridade é associado a cada processo. A CPU é alocada ao processo com a maior prioridade (menor número, no caso de prioridade numérica baixa indicar maior prioridade). O escalonamento por prioridades pode ser preemptivo ou não-preemptivo.

O problema principal é o starvation: processos de baixa prioridade podem nunca ser executados se houver um fluxo contínuo de processos de alta prioridade. A solução clássica é o aging (envelhecimento): aumentar gradualmente a prioridade dos processos que ficam muito tempo na fila de prontos, garantindo que eles eventualmente recebam a CPU. Prioridades podem ser estáticas (definidas pelo usuário) ou dinâmicas (ajustadas pelo sistema baseado em comportamento, como processos intensivos em E/S receberem prioridade maior).

Filas Multinível e Feedback

Na prática, sistemas operacionais modernos não usam um único algoritmo, mas uma combinação deles através de filas multinível. A fila de prontos é dividida em várias filas separadas, cada uma com seu próprio algoritmo de escalonamento:

  • Fila de tempo real: prioridade máxima, escalonamento FIFO ou RR com quantum pequeno.
  • Fila de processos interativos / de sistema: RR com quantum padrão.
  • Fila de processos batch / background: FCFS ou SJF, com prioridade mais baixa.

No Multilevel Feedback Queue, os processos podem migrar entre as filas. Se um processo da fila batch começa a se comportar de forma interativa, ele pode ser promovido para uma fila de maior prioridade. Se um processo interativo excede seu quantum repetidamente, ele pode ser rebaixado para uma fila batch. Essa adaptabilidade permite que o sistema responda bem a diferentes cargas de trabalho sem configuração manual.

O escalonador do Linux (CFS — Completely Fair Scheduler) moderno é baseado na ideia de árvores rubro-negras e tempo de execução virtual, garantindo que cada tarefa receba sua fatia justa de CPU de forma eficiente, mas os conceitos de prioridade dinâmica e envelhecimento continuam sendo a base teórica.

Conclusão da Aula

Hoje entendemos que não existe um algoritmo de escalonamento universal. A escolha depende do perfil da carga de trabalho e dos objetivos de desempenho. Sistemas batch priorizam throughput e turnaround (SJF/ FCFS), sistemas interativos priorizam tempo de resposta e justiça (RR), e sistemas de tempo real exigem previsibilidade e garantias de deadline. A combinação de múltiplos algoritmos em filas multinível é a abordagem que a maioria dos sistemas operacionais modernos adota para equilibrar todos esses fatores. Na próxima aula, veremos como esses conceitos se aplicam na prática ao escalonador do Linux e como monitorar o desempenho do sistema com ferramentas como top, htop e vmstat.

Perguntas Frequentes (FAQ)

Qual a principal diferença entre escalonamento preemptivo e não-preemptivo?

No escalonamento não-preemptivo, uma vez que um processo recebe a CPU, ele a mantém até terminar seu burst de CPU ou voluntariamente liberar o processador (ex: ao solicitar E/S). Já no preemptivo, o sistema operacional pode interromper o processo em execução a qualquer momento (tipicamente ao final de um quantum ou quando um processo de maior prioridade chega) e alocar a CPU para outro processo. A preempção permite melhor tempo de resposta, mas adiciona o overhead do chaveamento de contexto.

O que é o efeito comboio no escalonamento FCFS?

O efeito comboio ocorre quando um processo longo (com grande burst de CPU) é executado primeiro, enquanto vários processos curtos ficam esperando na fila de prontos. Visualmente, todos os processos curtos "seguem" o processo longo, como um comboio ou engarrafamento. Isso degrada drasticamente o tempo médio de espera e de turnaround, especialmente em sistemas interativos onde processos curtos são comuns.

Como o quantum influencia o desempenho do Round Robin?

O quantum (fatia de tempo) é o parâmetro mais crítico no RR. Um quantum muito grande torna o algoritmo equivalente ao FCFS, com tempo de resposta alto para processos interativos. Um quantum muito pequeno gera excesso de chaveamento de contexto (context switch), reduzindo a utilização da CPU e o throughput. O ideal é um quantum que seja grande o suficiente para cobrir a maioria dos bursts de CPU (reduzindo preempções desnecessárias), mas pequeno o bastante para manter o sistema responsivo (tipicamente entre 20ms e 100ms).

O que é starvation e como o envelhecimento (aging) resolve esse problema?

Starvation (inanição) é a situação em que um processo de baixa prioridade nunca é executado porque a CPU está continuamente ocupada com processos de maior prioridade. O aging (envelhecimento) é uma técnica que aumenta gradualmente a prioridade de um processo que está há muito tempo na fila de prontos. Com o tempo, a prioridade do processo aumenta até que ele se torne elegível para execução, garantindo que nenhum processo sofra starvation indefinidamente.