Nesta aula mergulhamos no conceito de escalonamento de processos (process scheduling), um dos mecanismos centrais de qualquer sistema operacional moderno. O escalonador da CPU decide qual processo, dentre os que estão prontos para executar, deve receber o processador a seguir. Essa decisão influencia diretamente o desempenho, a responsividade e a justiça do sistema como um todo.

O que é escalonamento de processos?

Em ambientes com multiprogramação, vários processos competem pelo uso da CPU. Como o número de processos ativos geralmente excede o número de núcleos disponíveis, o SO precisa alternar a execução entre eles. O escalonador é o componente encarregado de selecionar o próximo processo a ser executado.

Quando um processo é selecionado, ocorre uma troca de contexto (context switch): o estado atual (registradores, contador de programa, etc.) é salvo e o estado do novo processo é carregado. Esse overhead é inevitável e precisa ser levado em conta no projeto dos algoritmos.

Objetivos do escalonamento

Um bom escalonador busca equilibrar vários objetivos, muitas vezes conflitantes:

  • Maximizar a utilização da CPU — manter o processador o mais ocupado possível.
  • Maximizar a vazão (throughput) — número de processos completados por unidade de tempo.
  • Minimizar o tempo de turnaround — tempo total desde a submissão até a conclusão do processo.
  • Minimizar o tempo de espera — tempo que o processo passa na fila de prontos.
  • Minimizar o tempo de resposta — tempo até a primeira resposta para o usuário (essencial para sistemas interativos).
  • Garantir justiça — evitar que um processo sofra starvation.

Métricas de desempenho

Para comparar algoritmos, utilizamos métricas como:

  • Tempo de turnaround: \( T_{\text{turnaround}} = T_{\text{conclusão}} - T_{\text{submissão}} \).
  • Tempo de espera: soma dos períodos que o processo aguarda na fila de prontos.
  • Tempo de resposta: tempo até o início da execução (primeira resposta).
  • Throughput: processos completados por segundo.

Nenhum algoritmo otimiza todas as métricas simultaneamente; a escolha depende do tipo de sistema (batch, interativo, tempo real).

Algoritmos clássicos de escalonamento

A seguir, revisamos os algoritmos tradicionais que formam a base dos escalonadores modernos.

FCFS (First-Come, First-Served)

O processo que chega primeiro é executado até o fim (não preemptivo). A implementação é feita com uma fila simples (FIFO).

  • Vantagem: Simplicidade e justiça na ordem de chegada.
  • Desvantagem: Tempo de espera médio alto, especialmente se um processo longo chegar antes de processos curtos (efeito comboio). Inadequado para sistemas interativos.

SJF (Shortest Job First) e SRTF (Shortest Remaining Time First)

Seleciona o processo com o menor próximo surto de CPU (CPU burst). A versão não preemptiva é o SJF; a preemptiva é o SRTF, que interrompe o processo atual se um novo processo chegar com surto menor.

  • Vantagem: Tempo de espera médio mínimo teoricamente.
  • Desvantagem: Dificuldade prática de prever a duração dos surtos futuros. Pode causar starvation de processos longos se houver uma chegada contínua de processos curtos.

Round Robin (RR)

Cada processo recebe um quantum (fatia de tempo) fixo, geralmente entre 10 ms e 100 ms. A fila é circular: após consumir o quantum, o processo é colocado no final da fila de prontos.

  • Vantagem: Tempo de resposta previsível e baixo; adequado para sistemas de tempo compartilhado. Nenhum processo sofre starvation.
  • Desvantagem: O desempenho depende criticamente do tamanho do quantum. Um quantum muito pequeno aumenta o overhead de trocas de contexto; muito grande torna o comportamento similar ao FCFS.

Escalonamento por prioridade

Cada processo recebe uma prioridade (estática ou dinâmica). O escalonador sempre escolhe o processo de maior prioridade. Pode ser preemptivo ou não.

  • Vantagem: Flexibilidade para atender tarefas críticas em tempo real ou processos do sistema.
  • Desvantagem: Risco de starvation de processos de baixa prioridade. Solução: envelhecimento (aging), que aumenta gradualmente a prioridade de processos que esperam muito.

Filas multinível (Multilevel Queue / Multilevel Feedback Queue)

Para combinar as vantagens de diferentes algoritmos, os sistemas modernos utilizam filas múltiplas. Cada fila pode ter sua própria política (RR, FCFS, prioridade) e os processos podem migrar entre filas com base em seu comportamento.

O Multilevel Feedback Queue é a base dos escalonadores de sistemas como Linux (CFS — Completely Fair Scheduler), Windows e macOS. Ele permite equilibrar interatividade e eficiência sem exigir conhecimento prévio dos surtos de CPU.

  • Vantagem: Adaptável; separa processos interativos (pouco uso de CPU) de processos batch (longos).
  • Desvantagem: Complexidade de implementação e ajuste de parâmetros.

Troca de contexto e overhead

Toda vez que o escalonador decide trocar o processo em execução, o sistema salva o estado do processo atual e carrega o estado do próximo. Esse custo (troca de contexto) é puramente overhead — não realiza trabalho útil. Por isso, algoritmos como Round Robin precisam de um quantum grande o bastante para que o tempo útil compense o custo da troca.

Em sistemas modernos, uma troca de contexto leva alguns microssegundos. Se o quantum for de 10 ms, a fração de overhead é pequena. Já com quantum de 1 ms, o overhead pode se tornar significativo.

Resumo de vantagens e desvantagens

  • FCFS: simples, mas sofre do efeito comboio; tempo de resposta alto.
  • SJF/SRTF: tempo médio ótimo, mas difícil de implementar e pode causar starvation.
  • Round Robin: excelente para interatividade, depende da escolha do quantum.
  • Prioridade: flexível, mas requer aging.
  • Multilevel Feedback Queue: combina o melhor de vários mundos, mas é complexo.

Perguntas Frequentes (FAQ)

O que é starving (fome) de processos?

Ocorre quando um processo nunca recebe a CPU porque outros processos com prioridade mais alta (ou surtos mais curtos) sempre são escolhidos primeiro. O aging é a técnica mais comum para evitar esse problema.

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

No escalonamento não preemptivo, um processo executa até terminar ou bloquear voluntariamente. No preemptivo, o SO pode interromper o processo a qualquer momento (geralmente por interrupção de timer) e escalonar outro. A maioria dos sistemas modernos usa escalonamento preemptivo para garantir responsividade.

Como escolher o quantum no Round Robin?

O quantum deve ser grande o suficiente para amortizar o custo da troca de contexto, mas pequeno o bastante para garantir baixo tempo de resposta. Valores típicos variam de 10 ms a 100 ms. A escolha depende também da velocidade da CPU e da natureza das cargas de trabalho.

O que diferencia a Multilevel Feedback Queue das filas simples?

Nas filas multinível com realimentação, um processo pode migrar entre filas de acordo com seu comportamento: se usa pouco a CPU (interativo), permanece em filas de alta prioridade; se usa muita CPU, é movido para filas de menor prioridade. Isso permite que o sistema se adapte automaticamente sem conhecimento prévio dos processos.

Próximos passos

Os conceitos vistos hoje são a base para entender como sistemas operacionais reais gerenciam a concorrência. Na próxima aula, vamos analisar a implementação do escalonador do Linux (CFS) e estudar exemplos práticos de cálculo de tempo médio de espera e turnaround. Para se aprofundar, explore os artigos na página de Posts ou filtre por Tags relacionadas a sistemas operacionais.