Como funciona o escalonamento de CPU (CPU scheduling), e quais são os algoritmos comuns?

Question

IT Interview Practice · Accepted Answer

O **CPU scheduling** é a decisão do kernel sobre *qual* thread pronta recebe a CPU *em seguida*, e por *quanto tempo*. Como normalmente há mais threads executáveis do que cores, o **scheduler** as multiplexa, buscando equilibrar objetivos concorrentes — **throughput**, **baixa latência / tempo de resposta**, e **justiça (fairness)** — evitando ao mesmo tempo a **starvation**.

## Algoritmos comuns

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

O **round-robin** ilustra o botão de ajuste central — o **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Schedulers reais

O padrão de longa data do Linux foi o **CFS (Completely Fair Scheduler)**: em vez de fatias fixas, ele rastreia o **virtual runtime (vruntime)** de cada task e sempre executa a thread que recebeu menos CPU até então, ponderado pelo seu valor **nice** — aproximando "todo mundo recebe uma parcela justa". Ele indexa uma red-black tree por vruntime, então escolher a próxima task é O(log n). (Kernels mais novos usam o EEVDF, um refinamento com o mesmo objetivo de fairness mais limites de latência mais rígidos.)

**Preemptive vs cooperative:** os OSes modernos são **preemptive** — uma timer interrupt permite que o scheduler retome a CPU à força, então uma thread não pode monopolizar um core.

## Por que isso importa

O scheduling molda diretamente a latência e o throughput que os usuários sentem. Os entrevistadores sondam isso para ver se você entende os trade-offs — por que um workload interativo quer quanta curtos ou um boost de prioridade, por que o priority scheduling precisa de **aging** para evitar starvation, e como o MLFQ/CFS obtêm bom comportamento interativo sem conhecer de antemão a duração dos jobs. É também o modelo mental por trás de ajustar o `nice`, prioridades real-time, e diagnosticar um serviço em starvation ou com lag.

Algoritmos comuns

Schedulers reais

Por que isso importa

Perguntas relacionadas