# Escalonamento de processos

Critérios de escalonamento e contas de espera e retorno em FCFS e Round Robin.

Página: https://resumos.rgo.pt/cadeiras/so/escalonamento/

Há quase sempre mais processos prontos do que processadores. O **escalonador** é a parte do núcleo que escolhe, de cada vez, qual corre a seguir e por quanto tempo. As políticas diferem no compromisso entre simplicidade, justiça e tempo de resposta, e os testes pedem-te contas concretas sobre elas.

## O que se mede

Para cada processo, com instante de chegada $C$ e duração $D$, medem-se dois tempos a partir do instante em que termina, $F$:

*   **retorno** (_turnaround_): $F - C$, quanto tempo o processo demorou desde que chegou até estar feito.
*   **espera**: retorno menos duração, $(F - C) - D$, quanto desse tempo foi passado à espera em vez de a correr.

As médias destes dois valores sobre todos os processos comparam políticas. Uma boa política mantém os dois baixos, mas nenhuma vence em tudo: favorecer processos curtos prejudica os longos, e responder depressa custa trocas de contexto frequentes.

## FCFS: por ordem de chegada

O **FCFS** (_first come, first served_) corre cada processo até ao fim por ordem de chegada, sem interrupções. É simples e justo no sentido da fila do supermercado, mas sofre do **efeito de comboio**: um processo longo à frente prende todos os curtos atrás dele.

Toma quatro processos que chegam no instante 0 com durações P1 = 6, P2 = 3, P3 = 2, P4 = 4. Em FCFS correm P1, P2, P3, P4:

![Linha do tempo do FCFS: P1 de 0 a 6, P2 de 6 a 9, P3 de 9 a 11 e P4 de 11 a 15.](https://resumos.rgo.pt/cadeiras/so/escalonamento/figura-1.svg)

Os instantes de fim são 6, 9, 11 e 15. Os retornos são 6, 9, 11 e 15 (chegaram todos em 0), e as esperas são $6 - 6 = 0$, $9 - 3 = 6$, $11 - 2 = 9$ e $15 - 4 = 11$. Espera média: $(0 + 6 + 9 + 11) / 4 = 6{,}5$. Repara como o P1, que não esperou nada, fez os outros três esperar no total 26 unidades.

## Round Robin: fatias para todos

O **Round Robin** dá a cada processo uma **fatia** (_quantum_) de cada vez, pela ordem, e quem não acabar volta ao fim da fila. Com quantum 3 nos mesmos quatro processos:

*   P1 corre 0 a 3 (faltam 3), P2 corre 3 a 6 (termina), P3 corre 6 a 8 (termina), P4 corre 8 a 11 (falta 1), P1 corre 11 a 14 (termina), P4 corre 14 a 15 (termina).

Os fins são P1 = 14, P2 = 6, P3 = 8, P4 = 15. As esperas: P1 $14 - 6 = 8$, P2 $6 - 3 = 3$, P3 $8 - 2 = 6$, P4 $15 - 4 = 11$. Espera média: $(8 + 3 + 6 + 11) / 4 = 7$. Aqui o Round Robin até perde para o FCFS na média, porque o quantum divide o trabalho sem encurtar a fila. A vantagem dele está noutro lado: o P2, o P3 e o P4 começam todos a correr cedo, por isso o **tempo de resposta** (até à primeira fatia) é muito melhor, o que interessa quando há um utilizador à espera do terminal.

Confirma as contas a correr: este programa simula o Round Robin nos mesmos dados e lê o quantum da entrada. Experimenta `2` e `3` e compara com as linhas do tempo feitas à mão.

```c
#include <stdio.h>

int main(void) {
    int dur[4] = {6, 3, 2, 4};
    int falta[4] = {6, 3, 2, 4};
    int fim[4] = {0, 0, 0, 0};
    int quantum, t = 0, feitos = 0;
    if (scanf("%d", &quantum) != 1 || quantum <= 0) return 1;
    while (feitos < 4) {
        for (int i = 0; i < 4; i++) {
            if (falta[i] == 0) continue;
            int fatia = falta[i] < quantum ? falta[i] : quantum;
            t += fatia;
            falta[i] -= fatia;
            if (falta[i] == 0) { fim[i] = t; feitos++; }
        }
    }
    double soma = 0;
    for (int i = 0; i < 4; i++) {
        int espera = fim[i] - dur[i];
        printf("P%d termina em %d, espera %d\n", i + 1, fim[i], espera);
        soma += espera;
    }
    printf("Espera media: %.2f\n", soma / 4);
    return 0;
}
```

Com quantum 2 a saída é fins 15, 11, 6 e 13, com espera média 7,50. Refaz à mão: P1 0 a 2, P2 2 a 4, P3 4 a 6, P4 6 a 8, P1 8 a 10, P2 10 a 11, P4 11 a 13, P1 13 a 15. Se a tua linha do tempo der outros fins, o erro está na ordem da fila, não na fórmula.

Como resolver estes exercícios

Desenha a linha do tempo com os intervalos de cada processo antes de calcular o que quer que seja. Marca chegadas, fins e, no Round Robin, o que falta a cada um depois de cada fatia. Só depois aplica $F - C$ e subtrai $D$. A maioria dos erros nasce de calcular esperas de cabeça sem a linha do tempo.

## SJF e o dilema

O **SJF** (_shortest job first_) corre primeiro o processo pronto mais curto. Nos mesmos dados (todos chegam em 0), a ordem é P3, P2, P4, P1, com fins 2, 5, 9, 15 e esperas 0, 2, 5, 9. Média: 4, a melhor das três. O problema é duplo: o núcleo não sabe a duração antes de correr, e um fluxo contínuo de processos curtos deixa os longos à espera para sempre (**inanição**). É por isso que os sistemas reais usam prioridades com envelhecimento e fatias, misturando as três ideias em vez de escolher uma. O Linux usa o **CFS** (_Completely Fair Scheduler_), que trata cada processo com justiça proporcional em vez de adivinhar durações; o desenho oficial está na [documentação do escalonador](https://kernel.org/doc/html/v5.19/scheduler/sched-design-CFS.html).[1](https://resumos.rgo.pt/cadeiras/so/escalonamento/#user-content-fn-cfs)

Quando as chegadas diferem, a ordem deixa de ser óbvia. Resolve este segundo jogo, com A a chegar em 0 com duração 5, B em 1 com duração 3 e C em 2 com duração 1:

Em FCFS manda a chegada: A corre 0 a 5, B 5 a 8, C 8 a 9. Fins 5, 8 e 9. Retornos: A $5 - 0 = 5$, B $8 - 1 = 7$, C $9 - 2 = 7$. Esperas: A $5 - 5 = 0$, B $7 - 3 = 4$, C $7 - 1 = 6$. Espera média: $(0 + 4 + 6) / 3 = 3{,}33$.

Em SJF não preemptivo, no instante 0 só A está pronto, por isso A corre 0 a 5 apesar de ser o mais longo. Em 5 estão B e C: o mais curto é C, que corre 5 a 6 (fim 6, retorno $6 - 2 = 4$, espera $4 - 1 = 3$). Depois B corre 6 a 9 (fim 9, retorno $9 - 1 = 8$, espera $8 - 3 = 5$). A não esperou. Espera média: $(0 + 5 + 3) / 3 = 2{,}67$.

A lição: o SJF só escolhe entre os que já chegaram. Um processo curto que ainda não chegou não conta.

[Vídeo: Scheduling Algorithms - Round Robin Scheduling](https://www.youtube.com/watch?v=YzBBJYfwdi8)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=YzBBJYfwdi8)

## Para saber mais

*   O índice da [documentação oficial do escalonador do Linux](https://www.kernel.org/doc/html/v6.4/scheduler/index.html) mostra as peças reais por trás destas políticas simplificadas.

## Para levar para a próxima página

O escalonador decide quem corre, mas os processos também precisam de falar uns com os outros sem partilhar memória. Isso resolve-se com a [comunicação entre processos](https://resumos.rgo.pt/cadeiras/so/escalonamento/comunicacao-processos/).

## Notas de rodapé

1.  A descrição oficial do CFS explica a justiça proporcional sem fatias fixas: [desenho do CFS](https://kernel.org/doc/html/v5.19/scheduler/sched-design-CFS.html). [Voltar](https://resumos.rgo.pt/cadeiras/so/escalonamento/#user-content-fnref-cfs)