O que é escalonamento?
O escalonador (scheduler) é o componente do sistema operacional responsável por selecionar, entre os processos no estado de pronto, qual será executado. A decisão pode ocorrer em momentos como: término de um processo, bloqueio por E/S, chegada de um novo processo ou interrupção de relógio (no caso de escalonamento preemptivo). O principal objetivo é maximizar a utilização da CPU e garantir uma experiência responsiva para o usuário.
Critérios de escalonamento
Para avaliar um algoritmo de escalonamento, utilizamos as seguintes métricas:
- Utilização da CPU: percentual de tempo em que a CPU está ocupada.
- Throughput: número de processos completados por unidade de tempo.
- Tempo de turnaround: intervalo entre a submissão e a finalização do processo.
- Tempo de espera: soma total do tempo que o processo passa na fila de prontos.
- Tempo de resposta: tempo decorrido desde a submissão até a primeira resposta (importante em sistemas interativos).
Algoritmos de escalonamento
First-Come, First-Served (FCFS)
O primeiro processo a chegar é o primeiro a ser executado. É um algoritmo não preemptivo. Sua implementação é simples, mas pode causar o efeito "convoy", onde processos curtos esperam por um processo longo, resultando em baixo throughput.
Exemplo: Três processos P1 (10 ms), P2 (5 ms) e P3 (8 ms) chegam na ordem P1, P2, P3. A execução seria:
| Processo | Início | Término |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 10 | 15 |
| P3 | 15 | 23 |
Tempo de espera médio: (0 + 10 + 15) / 3 ≈ 8,33 ms.
Shortest‑Job‑First (SJF)
Seleciona o processo com o menor tempo de CPU restante. Pode ser preemptivo (Shortest‑Remaining‑Time‑First) ou não preemptivo. O SJF otimiza o tempo de espera médio, mas sofre de starvation para processos longos se novos processos curtos chegarem continuamente.
Usando o mesmo exemplo na versão não preemptiva, a ordem seria P2 (5 ms), P3 (8 ms), P1 (10 ms). Tempo de espera médio: (0 + 5 + 13) / 3 ≈ 6 ms.
Round Robin (RR)
Cada processo recebe um quantum de tempo (fatia) e é executado por no máximo esse período. Se não terminar, volta ao final da fila. O RR é preemptivo e proporciona boa resposta para sistemas interativos. A escolha do quantum é crítica: muito pequeno → excesso de trocas de contexto; muito grande → degrada para FCFS.
Exemplo com quantum = 4 ms para P1 (10), P2 (5), P3 (8):
| Instante | Processo | CPU restante |
|---|---|---|
| 0‑4 | P1 | 6 |
| 4‑8 | P2 | 1 |
| 8‑12 | P3 | 4 |
| 12‑16 | P1 | 2 |
| 16‑17 | P2 | 0 |
| 17‑21 | P3 | 0 |
| 21‑23 | P1 | 0 |
Tempo de espera médio: (4 + 8 + 13) / 3 ≈ 8,33 ms (considerando o início real de cada processo).
Escalonamento por prioridade
Cada processo recebe uma prioridade (número menor = maior prioridade). O processo de maior prioridade é executado primeiro. Se for preemptivo, um processo de maior prioridade interrompe o atual. Prioridades podem ser estáticas ou dinâmicas. O problema principal é a starvation de processos de baixa prioridade, que pode ser resolvida com envelhecimento (aging).
Múltiplas filas
Em sistemas mais complexos, os processos são divididos em categorias (foreground, background, batch) e cada categoria tem sua própria fila com algoritmo específico. Por exemplo, a fila foreground usa RR com quantum pequeno, e a fila background usa FCFS. Pode haver também realimentação (feedback), onde processos migram entre filas baseando‑se em seu comportamento.
Preemptivo vs não preemptivo
No escalonamento não preemptivo (cooperativo), o processo em execução mantém a CPU até terminar ou entrar em estado de espera. Isso simplifica a implementação, mas pode levar a atrasos imprevisíveis. No escalonamento preemptivo, o SO pode interromper o processo a qualquer momento (tipicamente por interrupção de temporizador) e retomar outro processo. Sistemas modernos adotam escalonamento preemptivo para garantir responsividade e evitar que um processo monopolize a CPU.
Exemplo comparativo
A tabela abaixo resume o tempo de espera médio para os três processos com FCFS, SJF (não preemptivo) e RR (quantum 4):
| Algoritmo | Tempo de espera médio |
|---|---|
| FCFS | ≈ 8,33 ms |
| SJF (não preemptivo) | ≈ 6,00 ms |
| Round Robin (q = 4) | ≈ 8,33 ms |
Conclusão
O escalonamento de processos é uma área central dos sistemas operacionais. A escolha do algoritmo depende do ambiente de operação: sistemas batch podem utilizar FCFS ou SJF; sistemas de tempo compartilhado adotam Round Robin ou prioridades; sistemas de tempo real necessitam de escalonamento com garantias de prazo. Entender esses conceitos ajuda a projetar sistemas mais justos e eficientes.
Perguntas Frequentes
O que é starvation?
Starvation (ou fome) ocorre quando um processo nunca recebe tempo de CPU porque processos de prioridade mais alta sempre chegam. Técnicas como envelhecimento (aging) aumentam gradualmente a prioridade de processos que esperam há muito tempo, prevenindo starvation.
Qual a diferença entre turnaround e response time?
Turnaround é o tempo total desde a submissão até o fim do processo. Response time é o tempo até a primeira execução na CPU (primeira resposta), importante para medir a interatividade percebida pelo usuário.
Por que o Round Robin é considerado justo?
Porque todos os processos recebem a mesma quantidade de tempo (quantum) em rodadas sucessivas, garantindo que nenhum processo fique sem CPU por um período excessivo. O progresso é proporcional.
O que acontece se o quantum do Round Robin for muito pequeno?
Se o quantum for muito pequeno (ex: 1 ms), o sistema gastará mais tempo alternando entre processos (troca de contexto) do que executando trabalho útil, reduzindo drasticamente o throughput.