Durante nossas aulas de sistemas operacionais, exploramos um dos componentes mais importantes do gerenciamento de processos: o escalonamento da CPU. Nesta nota, vamos revisar os principais conceitos, critérios e algoritmos utilizados pelo escalonador para decidir qual processo será executado a seguir.
O que é escalonamento de processos?
O escalonamento de processos é a atividade do sistema operacional que decide qual processo, dentre os que estão prontos na fila de prontos, receberá o uso da CPU. O módulo responsável por essa decisão é chamado de escalonador (scheduler). A troca de um processo por outro envolve uma mudança de contexto (context switch), que possui custo computacional — principalmente o salvamento e restauração de registradores e o gerenciamento de cache.
O escalonador é ativado sempre que um processo:
- passa do estado de execução para o estado de espera (ex.: aguardando I/O);
- passa do estado de execução para o estado de pronto (ex.: interrupção de timer);
- passa do estado de espera para o estado de pronto (ex.: I/O concluído);
- finaliza sua execução.
Critérios de escalonamento
Para avaliar a qualidade de um escalonador, utilizamos métricas bem estabelecidas. As principais são:
- Utilização da CPU — percentual do tempo em que o processador está ocupado. Em sistemas ideais, esse valor deve ser o mais alto possível, mas na prática fica entre 40% e 90% dependendo da carga.
- Throughput — número de processos completados por unidade de tempo. Mede a produtividade do sistema.
- Tempo de turnaround — intervalo entre a submissão do processo e sua conclusão completa. É a soma do tempo de execução com o tempo de espera na fila.
- Tempo de espera — tempo total que o processo permanece na fila de prontos, aguardando a CPU. Não inclui o tempo de I/O ou de execução.
- Tempo de resposta — tempo decorrido desde a submissão até a primeira resposta (primeira execução) do processo. Importante para sistemas interativos.
Cada algoritmo busca otimizar uma ou mais dessas métricas, e frequentemente há um compromisso (trade-off) entre elas, especialmente entre throughput e tempo de resposta.
Algoritmos de escalonamento
FCFS (First‑Come, First‑Served)
O processo que chega primeiro é executado por completo, sem preempção. É simples de implementar (fila FIFO), mas pode causar o efeito conhecido como convoy effect, onde processos curtos esperam por um processo longo.
Exemplo: Considere três processos com burst time (tempo de CPU) de 10, 5 e 2 unidades, chegando nessa ordem (P1, P2, P3). Os tempos de turnaround são: P1 = 10, P2 = 15, P3 = 17. O tempo de espera médio é (0 + 10 + 12) / 3 ≈ 7,33. Se a ordem fosse P3, P2, P1, o espera média cairia para 2,67.
SJF (Shortest Job First) — não preemptivo
Seleciona o processo com menor tempo de execução estimado. É ótimo em termos de tempo de turnaround médio, mas sofre de starvation: processos longos podem nunca ser executados se processos curtos chegarem continuamente.
Exemplo: Com os mesmos processos, se a ordem de chegada for P1 (10), P2 (5), P3 (2), o SJF seleciona P3 primeiro, depois P2, depois P1. Turnaround: P3 = 2, P2 = 7, P1 = 17. Espera média = (0 + 2 + 7) / 3 = 3 — bem menor que o FCFS.
STCF (Shortest Time to Completion First) — preemptivo
Variante preemptiva do SJF: quando um novo processo chega com burst menor que o restante do processo em execução, a CPU é trocada. Também conhecido como SRTF (Shortest Remaining Time First).
Round Robin (RR)
Cada processo recebe um pequeno quantum de tempo (time slice, geralmente entre 10 e 100 ms) e a CPU alterna circularmente entre todos os processos prontos. Excelente para tempo de resposta e interatividade, mas o throughput pode ser reduzido se o quantum for muito pequeno (devido ao excesso de context switches).
Exemplo: Com quantum = 4 e os processos P1 (10), P2 (5), P3 (2), a execução seria: P1 executa 4, P2 executa 4, P3 executa 2 (termina), P1 executa 4, P2 executa 1 (termina), P1 executa 2 (termina). O tempo de turnaround médio é maior que SJF, mas o tempo de resposta é muito baixo — todos começam a executar em até 8 unidades de tempo.
Escalonamento por prioridade
Cada processo recebe uma prioridade (geralmente um número, sendo que valores menores indicam maior prioridade). O processo de maior prioridade executa primeiro. Pode causar starvation se processos de baixa prioridade nunca executarem. Uma solução comum é o envelhecimento (aging): aumentar gradualmente a prioridade dos processos que esperam muito tempo.
O escalonamento por prioridade pode ser preemptivo ou não preemptivo. No Linux, por exemplo, a prioridade dinâmica é ajustada conforme o comportamento do processo (I/O‑bound vs CPU‑bound).
Preemptivo vs Não Preemptivo
Em escalonamento não preemptivo (cooperativo), um processo mantém a CPU até terminar ou bloquear voluntariamente. Em preemptivo, o escalonador pode interromper um processo em execução (normalmente via timer) e alocar a CPU a outro processo. Sistemas modernos de tempo compartilhado usam preempção para garantir interatividade e evitar que um processo monopolize o processador.
A preempção traz o custo adicional do context switch, mas permite um tempo de resposta muito mais previsível. O Windows, macOS e Linux adotam variantes preemptivas (com prioridade dinâmica e múltiplas filas).
Escalonamento em sistemas multiprocessadores
Em sistemas com múltiplas CPUs (ou núcleos), o escalonador deve considerar:
- Afinidade de cache — é vantajoso manter um processo no mesmo processador para reutilizar o cache quente.
- Balanceamento de carga — distribuir processos entre os processadores para evitar que uns fiquem ociosos enquanto outros sobrecarregados.
- Concorrência — acesso a estruturas de dados compartilhadas deve ser sincronizado.
Abordagens comuns incluem escalonamento simétrico (SMP) — onde cada processador executa seu próprio escalonador e compartilham a fila de prontos — e assimétrico, onde um processador mestre gerencia a distribuição.
Comparativo resumido
- FCFS: simples, sem starvation, mas com alto tempo de espera médio para processos curtos.
- SJF/STCF: ótimo para turnaround, mas pode causar starvation de processos longos; difícil de implementar na prática (requer estimativa de burst).
- Round Robin: excelente para tempo de resposta, adequado para sistemas interativos; throughput depende do quantum.
- Prioridade: flexível, mas requer mecanismos para evitar starvation (aging).
Perguntas frequentes (FAQ)
1. Qual a diferença entre escalonamento preemptivo e não preemptivo?
No modo não preemptivo, o processo mantém a CPU até se bloquear ou terminar; no modo preemptivo, o sistema pode interrompê‑lo após um quantum ou quando um processo de maior prioridade se torna pronto.
2. Por que o Round Robin é considerado justo?
Porque todos os processos recebem uma fatia igual de tempo da CPU de forma cíclica, garantindo que nenhum processo fique esperando por muito tempo para obter uma fatia. É particularmente justo para processos de curta duração.
3. O que é starvation e como evitá‑la?
Starvation (inanição) ocorre quando um processo nunca recebe a CPU porque processos de maior prioridade ou mais curtos sempre são escolhidos. A técnica mais comum de prevenção é o aging: aumentar gradualmente a prioridade de processos que esperam muito tempo, forçando sua eventual execução.
Para se aprofundar no assunto, veja a aula sobre OS — Memória e também o artigo sobre gerenciamento de memória. Consulte também a página de tags para mais notas sobre sistemas operacionais.