Hoje demos continuidade ao estudo de sistemas operacionais com um mergulho profundo no escalonamento de processos. O objetivo principal do escalonador de curto prazo (CPU scheduler) é decidir qual dos processos na fila de pronto (ready queue) irá executar na CPU a seguir. Um bom escalonador pode maximizar o throughput do sistema, minimizar o tempo de resposta para usuários interativos e garantir justiça na distribuição do tempo de processador.

O Ciclo CPU-I/O

Antes de analisar os algoritmos, é fundamental entender o comportamento dos processos. Durante sua execução, um processo alterna entre dois estados:

  • Burst de CPU: período em que o processo está executando instruções na CPU (cálculos, processamento).
  • Burst de I/O: período em que o processo espera por uma operação de entrada/saída (ler disco, rede, teclado).

Processos podem ser classificados como CPU-bound (longos bursts de CPU, poucas operações de I/O) ou I/O-bound (bursts de CPU muito curtos, muitas operações de I/O). A distribuição dos bursts de CPU segue tipicamente uma distribuição exponencial, com muitos bursts curtos e poucos muito longos.

Critérios de Avaliação do Escalonamento

Para comparar algoritmos de escalonamento, utilizamos as seguintes métricas:

  • Utilização da CPU: percentual de tempo em que a CPU está ocupada. Idealmente queremos o máximo possível (40%–90% em sistemas reais).
  • Throughput: número de processos completados por unidade de tempo.
  • Tempo de Turnaround (TTR): intervalo entre a submissão do processo e sua conclusão total. TTR = Término - Submissão.
  • Tempo de Espera (Waiting Time): soma total dos períodos que o processo passou na fila de pronto, aguardando a CPU. Não inclui tempo de I/O ou execução.
  • Tempo de Resposta: tempo desde a submissão até a primeira resposta (primeiro burst de CPU). Crítico para sistemas interativos.
Em sistemas interativos, minimizar o tempo de resposta é geralmente mais importante que maximizar o throughput.

Algoritmos Clássicos de Escalonamento

1. FCFS — First-Come, First-Served (FIFO)

O processo que chega primeiro na fila de pronto é o primeiro a ser executado. É implementado com uma fila FIFO simples.

  • Vantagem: Simples e fácil de implementar.
  • Desvantagem: Pode causar o efeito comboio (convoy effect). Um processo CPU-bound com burst longo monopoliza a CPU, enquanto vários processos I/O-bound completam seus bursts de I/O rapidamente e ficam esperando na fila de pronto. A utilização da CPU e de I/O fica baixa.
  • Tipo: Não preemptivo.

2. SJF — Shortest-Job-First (Menor Burst Primeiro)

Associa a cada processo o comprimento do seu próximo burst de CPU. A CPU é alocada ao processo com o menor burst.

  • Vantagem: Comprovadamente ótimo em relação ao tempo de turnaround médio.
  • Desvantagem: Difícil de implementar na prática, pois não sabemos o comprimento do próximo burst. Sistemas utilizam médias exponenciais ponderadas para estimar (τₙ₊₁ = α · tₙ + (1-α) · τₙ).
  • Preemptivo (SRTF — Shortest-Remaining-Time-First): Quando um novo processo chega com um burst menor que o tempo restante do processo atual, ocorre uma preempção. O SRTF é ainda mais ótimo que o SJF não preemptivo.
  • Risco: Pode causar starvation (fome) de processos com bursts muito longos.

3. Round Robin (RR)

Cada processo na fila de pronto recebe um pequeno quantum de tempo de CPU (geralmente entre 10 ms e 100 ms). 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 pronto.

  • Vantagem: Excelente tempo de resposta para todos os processos. É justo (todos recebem a mesma fatia de tempo).
  • Impacto do quantum: Muito pequeno → grande overhead de troca de contexto. Muito grande → degenera para FCFS.
  • Regra prática: O quantum deve ser maior que 80% dos bursts de CPU para manter o overhead baixo, garantindo boa experiência interativa.

Escalonamento por Prioridade

Cada processo possui uma prioridade (número inteiro, geralmente quanto menor o número, maior a prioridade). A CPU é alocada ao processo de maior prioridade.

  • Problema principal: Starvation — processos de baixa prioridade podem nunca executar se houver processos de alta prioridade constantemente.
  • Solução clássica: Envelhecimento (Aging). A prioridade de um processo é aumentada gradualmente com o tempo que ele passa esperando na fila de pronto. Em algum momento, ele se tornará a maior prioridade e executará.

A combinação de Prioridade + Round Robin é comum: processos na mesma prioridade executam em Round Robin.

Filas Multinível (Multilevel Queue)

Particiona a fila de processos em múltiplas filas separadas, cada uma com seu próprio algoritmo de escalonamento. Exemplo clássico:

  • Fila de foreground (interativos): Round Robin (quantum pequeno).
  • Fila de background (batch): FCFS.

Entre as filas, é necessário um escalonamento global (prioridade fixa ou fatia de tempo entre filas).

Multilevel Feedback Queue (MLFQ)

Evolução do modelo multinível. Os processos podem mover-se entre filas baseado em seu comportamento.

  • Um processo que consome muito tempo de CPU (CPU-bound) é movido para filas de prioridade mais baixa.
  • Um processo que se comporta como interativo (bursts curtos) permanece ou é movido para filas de prioridade mais alta.
  • Muito flexível e usado em sistemas operacionais modernos (ex: variantes do Linux CFS, Windows, BSD 4.4).
O MLFQ consegue equilibrar perfeitamente a necessidade de baixo tempo de resposta para processos interativos e alta eficiência para processos batch.