Escalonamento de CPU

O problema do caixa único

Imagine uma fila de banco com 5 clientes, cada um com tempo de atendimento diferente, e apenas um caixa. Em que ordem atender? FCFS (ordem de chegada) é justo mas pode ser lento. SJF (mais rápido primeiro) minimiza a espera média mas pode ser injusto. Round Robin dá vez a todos em turnos — ninguém espera muito.

CPUs modernas têm múltiplos núcleos, mas há sempre mais processos prontos que núcleos disponíveis. O escalonador decide quem usa a CPU e por quanto tempo (quantum), com preempção — pode interromper um processo para dar CPU a outro.

Simulador de escalonamento

Ajuste os burst times dos processos, selecione o algoritmo e veja o diagrama de Gantt e as métricas de espera e turnaround. Para Round Robin, defina o quantum.

Linux CFS — Completely Fair Scheduler

// Linux CFS — Completely Fair Scheduler (simplificado)
// Mantém uma red-black tree de processos prontos, ordenada por vruntime.

struct sched_entity {
  u64 vruntime;   // tempo virtual de execução (ponderado por prioridade)
  int nice;       // -20 (maior prioridade) a +19 (menor)
};

// O CFS sempre escala o processo com menor vruntime
// (o que recebeu menos CPU proporcionalmente)

// nice -20: processo recebe 10× mais CPU que nice +19
// peso = prio_to_weight[nice + 20]  (tabela no kernel)

// Quanto o processo executa por vez? O "target latency"
const TARGET_LATENCY = 6ms;  // todos os procs rodam em 6ms
const MIN_GRANULARITY = 0.75ms; // mínimo para evitar thrashing

// quantum_i = TARGET_LATENCY × (peso_i / Σpesos)
// Processo de alta prioridade ganha fatia maior do latency target

// Quando um novo processo fica pronto:
if (novo.vruntime < atual.vruntime - TARGET_LATENCY) {
  preempt();  // preempção: novo processo merece CPU agora
}

Métricas de avaliação

// Métricas de escalonamento

// Para um processo P com:
//   arrival_time = 2  (chegou no instante 2)
//   burst_time   = 5  (precisa de 5 unidades de CPU)
//   finish_time  = 10 (terminou no instante 10)

const turnaround = finish_time - arrival_time;  // 10 - 2 = 8
// turnaround = tempo total desde chegada até conclusão

const waiting = turnaround - burst_time;        // 8 - 5 = 3
// waiting = tempo que o processo ficou esperando (sem usar CPU)

const response = first_cpu_time - arrival_time; // tempo até primeira execução
// response time é crítico para sistemas interativos

// Convoy effect (FCFS): processo longo atrasa todos os curtos
// P1(burst=20), P2(burst=1), P3(burst=1), todos chegam t=0
// FCFS: P2 e P3 esperam 20 unidades → waiting médio = (0+20+21)/3 = ~14
// SJF:  P2, P3, P1 → waiting médio = (0+1+2)/3 = 1

Implementando um escalonador

Mini projeto: implemente FCFS e Round Robin (quantum=2) em Python. Receba uma lista de processos [(id, arrival, burst)] e retorne o Gantt chart como lista de (pid, start, end), mais as métricas de waiting time e turnaround médios. Valide com o simulador acima.

Projeto principal: implemente o algoritmo do Banqueiro (Banker's Algorithm) em Python: dado um estado de alocação de recursos (allocated, max, available), implemente is_safe_state() que retorna se o estado atual é seguro (existe sequência de execução que permite todos os processos terminarem). Teste com os cenários do simulador de deadlock.

Desafio extra: use chrt (Linux) para rodar um programa com política de escalonamento de tempo real: chrt -f 50 ./meu_prog (SCHED_FIFO, prioridade 50). Compare a jitter de timing (variação no tempo de execução de um loop de 1ms) entre SCHED_FIFO e o CFS padrão com clock_gettime(CLOCK_MONOTONIC).

Teste sua intuição

Onde você encontra isso