Escalonamento de Processos — Conceitos de SO

Escalonamento de processos é a decisão do sistema operacional sobre qual processo pronto receberá a CPU em seguida. Em linguagem simples, é a regra para escolher quem executa agora e quem espera. Essa regra altera o tempo de espera, o tempo de resposta, a justiça e a vazão geral.

O escalonamento de processos importa porque o mesmo conjunto de processos pode terminar em uma ordem muito diferente sob FCFS, SJF ou round robin. Se você entender essa ideia, a maioria dos exemplos de livro fica muito mais fácil de acompanhar.

O Que Significa Escalonamento de Processos em SO

No modelo usual de SO, os processos passam por estados como pronto, em execução e esperando. O escalonador escolhe entre os processos prontos.

É por isso que o escalonamento de processos muitas vezes também é chamado de escalonamento de CPU. Ele não cria trabalho novo. Ele decide a ordem em que o trabalho que está esperando recebe serviço da CPU.

Em sistemas modernos, o kernel muitas vezes escalona threads diretamente, mas o termo clássico "escalonamento de processos" ainda é o padrão no ensino.

O Que um Escalonador Tenta Otimizar

Um escalonador normalmente tenta equilibrar vários objetivos:

• baixo tempo de espera
• resposta rápida para tarefas interativas
• boa vazão
• justiça
• comportamento previsível

Esses objetivos podem entrar em conflito. Uma política que reduz o tempo médio de espera em um exemplo simplificado ainda pode parecer injusta na prática, e uma política justa de compartilhamento de tempo pode atrasar a conclusão de um trabalho curto.

Escalonamento Preemptivo vs Não Preemptivo

Um escalonador não preemptivo deixa um processo em execução manter a CPU até terminar seu burst de CPU ou bloquear. First-come, first-served é o exemplo padrão.

Um escalonador preemptivo pode interromper um processo em execução e entregar a CPU a outro. Round robin e muitos escalonadores por prioridade fazem isso.

Essa distinção importa porque o tempo de resposta muitas vezes melhora quando o sistema pode interromper trabalhos longos.

Algoritmos Comuns de Escalonamento de Processos

First-Come, First-Served

First-come, first-served, ou FCFS, executa os processos na ordem de chegada. É fácil de entender e simples de implementar, mas um trabalho longo no início pode fazer todos os trabalhos curtos atrás dele esperarem.

Shortest Job First

Shortest job first, ou SJF, dá preferência ao processo com o menor burst de CPU. Em um cenário simplificado em que os comprimentos dos bursts são conhecidos com precisão, ele pode reduzir o tempo médio de espera. Em sistemas reais, esse comprimento geralmente precisa ser estimado.

Round Robin

Round robin dá a cada processo pronto uma pequena fatia de tempo chamada quantum. Se o processo não terminar nessa fatia, ele volta para a fila de prontos. Isso normalmente melhora a justiça e a responsividade em cargas de trabalho interativas.

Escalonamento por Prioridade

O escalonamento por prioridade executa primeiro o processo pronto de maior prioridade. Ele pode ser útil quando algumas tarefas importam mais do que outras, mas, se tarefas de baixa prioridade esperarem demais, a inanição passa a ser um risco.

Um Exemplo Resolvido com Tempo de Espera

Suponha que três processos cheguem todos no tempo $0$ e que cada um precise apenas de tempo de CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Assuma:

• há uma CPU
• não há bloqueio por I/O
• o custo de troca de contexto é ignorado

Nessas condições, tempo de espera significa o tempo passado na fila de prontos antes de um processo executar. O turnaround é

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Se FCFS for usado, a ordem é $P_1 \rightarrow P_2 \rightarrow P_3$.

Linha do tempo:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Tempos de espera:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Tempo médio de espera:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Se SJF não preemptivo for usado, a ordem é $P_3 \rightarrow P_2 \rightarrow P_1$.

Linha do tempo:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Tempos de espera:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Tempo médio de espera:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Este exemplo mostra a intuição principal. A carga de trabalho não mudou, mas a regra mudou o resultado. Aqui, SJF produz um tempo médio de espera menor porque os trabalhos curtos não ficam presos atrás do longo.

Isso não significa que SJF seja sempre a melhor escolha no mundo real. Significa que, sob as hipóteses deste exemplo, a ordem de escalonamento importa muito.

A Intuição para Lembrar

Pense no escalonamento de processos como a disciplina da fila da CPU. A fila de prontos pode conter os mesmos trabalhos, mas a regra para atender essa fila muda o que os usuários percebem.

Se você se importa mais com respostas iniciais rápidas, pode preferir compartilhamento frequente. Se você se importa mais em terminar muitos trabalhos curtos rapidamente, pode preferir uma política que favoreça bursts curtos. Se você se importa com temporização rígida, talvez precise de outro escalonador.

Erros Comuns em Problemas de Escalonamento

Supor que uma política é universalmente melhor

Não existe um único vencedor para toda carga de trabalho. Uma política pode parecer excelente em tempo médio de espera e ainda assim ser ruim para justiça ou prazos.

Confundir tempo de espera, tempo de resposta e turnaround

Essas métricas estão relacionadas, mas não são idênticas. Em particular, tempo de resposta normalmente significa o tempo até o primeiro serviço de CPU ou a primeira resposta visível, enquanto turnaround mede o trabalho inteiro desde a chegada até a conclusão.

Ignorar a condição por trás da fórmula

As métricas só fazem sentido sob as hipóteses informadas. Se um problema inclui bloqueio por I/O, tempos de chegada diferentes ou sobrecarga de troca de contexto, a linha do tempo e os resultados mudam.

Esquecer se a política é preemptiva

SJF e shortest remaining time first não são a mesma regra. O escalonamento por prioridade também se comporta de forma diferente dependendo de um trabalho de maior prioridade poder ou não interromper o atual.

Onde o Escalonamento de Processos É Usado

O escalonamento de processos importa em qualquer lugar onde um sistema operacional precise compartilhar tempo de CPU:

• sistemas desktop e móveis que precisam de aplicativos responsivos
• servidores que lidam com muitas requisições
• sistemas em lote que se preocupam com vazão
• sistemas de tempo real que se preocupam com garantias temporais

Escalonadores reais costumam ser mais complexos do que as versões de livro, mas os mesmos trade-offs continuam aparecendo.

Tente Sua Própria Versão

Mude o exemplo para que $P_2$ chegue mais tarde, ou substitua FCFS por round robin usando um quantum de $2\ \mathrm{ms}$, e veja como o padrão de espera muda. Se quiser dar mais um passo depois de fazer à mão, experimente sua própria versão no GPAI Solver e compare sua linha do tempo prevista com a calculada.