Escalonamento de processos

Métricas

Uma CPU, sem I/O nem custos. Com chegada $A$, rajada $B$, primeiro início $S$, fim $F$:

$$T=F-A,\qquad W=F-A-B,\qquad R=S-A.$$

Retorno, espera e primeira resposta. Com I/O, subtrai também o tempo bloqueado da espera.

Política	Regra	Risco
FCFS	ordem de chegada	efeito de comboio
SJF	menor rajada já pronta	não adivinha chegadas
SRTF	menor tempo restante	reavaliar em cada chegada; inanição sem aging
RR	quantum $q$, volta ao fim	espera inclui intervalos entre fatias
Prioridades	ordem definida	inanição; aging ou quotas

SJF minimiza a espera média só com todas disponíveis e durações conhecidas. Previsão exponencial, com medida $t_n$, previsão anterior $\tau_n$ e $0\leq\alpha\leq1$:

$$\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n.$$

Traços de referência

SRTF com A(0,5), B(1,3), C(2,1): A 0-1, B 1-2, C 2-3, B 3-5, A 5-9. Esperas 4, 1, 0; média $5/3$.

RR com $q=3$, rajadas 6, 3, 2, 4, todos em 0:

Fins 14, 6, 8, 15; esperas 8, 3, 6, 11; média 7. Quantum grande tende para FCFS; pequeno aumenta trocas sem garantir menor espera. Fração útil aproximada, com quantum $q$ e custo de troca $c$, supondo fatias cheias e fila sempre ocupada:

$$q/(q+c).$$

Justiça e tempo real

• MLFQ muda tarefas de fila pelo comportamento; exige regras explícitas de quotas e promoção.
• CFS escolhe menor vruntime; maior peso faz crescer mais devagar. nice menor é mais prioridade. EEVDF usa deadline virtual, não prazo físico.
• Modelo de tempo real: 1 CPU, tarefas independentes e preemptivas, deadline igual ao período. Para a tarefa $i$, $C_i$ é o custo máximo e $P_i$ o período; para $n$ tarefas, $U=\sum C_i/P_i$.
• RMS: prioridade ao menor período; $U\leq n(2^{1/n}-1)$ é suficiente, não necessária. Sem custos, este modelo não decide.
• EDF: menor deadline absoluta; $U\leq1$ decide. Hard deadline falhada é falha; soft admite atraso.

Exemplos completos.