Escalonamento de processos

Quatro compilações estão prontas e há uma só CPU. Dar primeiro serviço à mais curta reduz certas esperas; interromper uma compilação longa pode dar resposta mais cedo às restantes. O escalonador escolhe uma tarefa pronta. Para comparar políticas, fixamos chegadas, rajadas, desempates e custos.

Hipóteses e métricas

Nos exemplos, temos uma CPU, uma rajada de CPU por processo, sem I/O e custo de troca de contexto nulo. Uma política não preemptiva mantém a tarefa até terminar a rajada ou bloquear. Uma política preemptiva pode interrompê-la e devolvê-la à fila de prontos.

Sejam $A_i$ a chegada, $B_i$ a duração da rajada, $S_i$ o primeiro início e $F_i$ o fim. Definimos:

$$T_i = F_i-A_i,\qquad W_i=T_i-B_i,\qquad R_i=S_i-A_i.$$

$T_i$ é retorno (turnaround), $W_i$ espera na fila de prontos e $R_i$ resposta até ao primeiro serviço. Se houver I/O, subtrai também o tempo bloqueado para obter a espera. Em tempo real, alguns textos chamam resposta a $F_i-A_i$; verifica a definição do enunciado.

Utilização é a fração de tempo em que a CPU trabalha. Throughput conta tarefas concluídas por unidade de tempo. Melhorar uma média pode piorar a resposta de uma tarefa específica.

FCFS e SJF com a mesma entrada

Cada política é uma regra de escolha perante a fila de prontos. FCFS escolhe por ordem de chegada. SJF não preemptivo escolhe a menor rajada entre as tarefas já prontas, sem adivinhar chegadas futuras. Só depois de fixar a regra é que a tabela compara os resultados.

Todos chegam em 0, por ordem P1, P2, P3, P4, com durações 6, 3, 2 e 4.

Política	Intervalos	Esperas de P1, P2, P3, P4	Média
FCFS	P1: 0–6, P2: 6–9, P3: 9–11, P4: 11–15	0, 6, 9, 11	6,5
SJF	P3: 0–2, P2: 2–5, P4: 5–9, P1: 9–15	9, 2, 0, 5	4

Um processo longo à frente faz os curtos esperar, ou seja tens o efeito de comboio.

Com todas disponíveis e durações conhecidas, ordenar por duração minimiza a espera média, mas não resolve automaticamente todas as situações com chegadas futuras.

A duração pode ser estimada por média exponencial:

$$\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n,\quad 0\leq\alpha\leq1.$$

$t_n$ é a rajada medida e $\tau_n$ a previsão anterior. Para $\tau_n=8$, $t_n=4$ e $\alpha=0,5$, a próxima previsão é 6. Um $\alpha$ elevado dá mais peso à medição recente.

Chegadas diferentes e SRTF

A chega em 0 com duração 5, B em 1 com duração 3 e C em 2 com duração 1. Em SJF não preemptivo, A começa por ser o único disponível e corre até 5. Seguem-se C até 6 e B até 9. As esperas são A=0, B=5, C=3, média $8/3$.

SRTF escolhe o menor tempo restante. Usamos desempate pela chegada mais antiga:

Instante	Decisão
0	A começa
1	A tem 4 restantes; B tem 3, por isso B interrompe A
2	B tem 2 restantes; C tem 1, por isso C corre
3	C termina; B tem 2 e A tem 4, por isso B retoma
5	B termina e A retoma até 9

Fins A=9, B=5, C=3. Esperas $9-0-5=4$, $5-1-3=1$ e $3-2-1=0$, média $5/3$. Ao surgir uma tarefa curta, compara com o tempo restante da atual, não com a sua duração inicial.

Round Robin

Round Robin dá até um quantum $q$ a cada tarefa e coloca no fim da fila quem ainda não terminou. Com os quatro processos do primeiro exemplo e $q=3$:

Os fins são 14, 6, 8 e 15; as esperas são 8, 3, 6 e 11, média 7. Segue a fila depois de cada fatia: P1 corre 0-3 e vai para o fim; P2 corre 3-6 e termina; P3 corre 6-8 e termina; P4 corre 8-11 e volta ao fim; P1 corre 11-14 e termina; P4 corre 14-15 e termina. P1 não espera apenas até à primeira fatia: volta a esperar enquanto outros correm. Os tempos de primeira resposta são 0, 3, 6 e 8. FCFS tinha 0, 6, 9 e 11, por isso Round Robin melhora aqui a resposta dos últimos, embora a espera média aumente.

Para comparar, mantém as mesmas rajadas e muda só o quantum para 2. O traço fica:

Intervalo	Processo	Efeito no fim da fatia
0–2	P1	Restam 4; volta ao fim
2–4	P2	Resta 1; volta ao fim
4–6	P3	Termina
6–8	P4	Restam 2; volta ao fim
8–10	P1	Restam 2; volta ao fim
10–11	P2	Termina
11–13	P4	Termina
13–15	P1	Termina

P1, P2, P3 e P4 terminam em 15, 11, 6 e 13. As esperas são 15-6=9, 11-3=8, 6-2=4 e 13-4=9, média 7,5. Diminuir o quantum não garante reduzir a espera média: o objetivo de resposta pode exigir outro compromisso.

Um quantum muito grande aproxima o modelo de FCFS. Um quantum muito pequeno aumenta a frequência de trocas. Se cada fatia útil tiver duração $q$ e cada troca custo $c$, uma aproximação à fração útil é $q/(q+c)$, desde que existam tarefas para alternar e fatias completas.

Quando a aproximação falha

A fração $q/(q+c)$ supõe fatias cheias e fila sempre ocupada. Com rajadas mais curtas que o quantum ou CPU por vezes sem trabalho, mede antes os intervalos reais de execução e troca.

Prioridades e filas

Uma prioridade fixa pode deixar uma tarefa esperar indefinidamente se chegam sempre tarefas de prioridade superior. Isto é inanição. Aging aumenta a prioridade de quem espera para combater esse problema.

Em filas multinível, tarefas de classes diferentes ficam em filas fixas, que podem ter políticas próprias. É preciso definir como a CPU é repartida entre filas. Prioridade estrita entre elas pode causar inanição; quotas de tempo dão outro compromisso.

Em filas multinível com realimentação, ou MLFQ, as tarefas podem mudar de fila segundo o comportamento observado. Um modelo comum começa com prioridade alta, reduz a prioridade de quem consome a sua quota e periodicamente promove tarefas para evitar inanição. Especifica os quantums e as regras de promoção: MLFQ não designa um único algoritmo com resultados universais.

Para tarefas periódicas, como ler um sensor de 4 em 4 ms, usa o modelo de custo e período da secção de tempo real, não uma fila multinível genérica. O CFS histórico e o EEVDF atual do Linux inspiram-se em justiça proporcional, mas os seus detalhes e parâmetros não são o modelo de resposta dos exercícios.

Justiça proporcional e Linux

O modelo CFS organiza tarefas por vruntime, tempo executado ponderado pelo peso. Escolher quem tem menor vruntime tenta compensar quem recebeu menos CPU. Maior peso faz o vruntime crescer mais devagar para a mesma duração física, dando uma maior quota de CPU. Em nice, valores menores correspondem a maior prioridade e peso; não invertas esta relação.

Por exemplo, se os pesos de A e B são 2 e 1, a divisão ideal com ambos sempre prontos é $2/3$ para A e $1/3$ para B. Uma árvore ordenada permite encontrar o menor vruntime. Este é um modelo estudado; Linux moderno está a transitar para EEVDF, que escolhe entre tarefas elegíveis pela deadline virtual. Não confundir a deadline virtual com o prazo físico de uma tarefa de tempo real.

Tempo real: RMS e EDF

Uma tarefa periódica tem custo máximo $C_i$, período $P_i$ e deadline. Uma hard deadline é um requisito cujo incumprimento é falha; uma soft deadline admite atraso com perda de qualidade.

No modelo com uma CPU, tarefas independentes, preempção, custo desprezável e deadlines iguais aos períodos, RMS dá prioridade fixa ao menor período. Para $n$ tarefas, a condição suficiente

$$U=\sum_i C_i/P_i\leq n(2^{1/n}-1)$$

prova escalonabilidade. Exceder o limite não prova impossibilidade: podes precisar de analisar a linha do tempo ou os tempos de resposta. EDF escolhe a job pronta com deadline absoluta mais próxima. Nas mesmas hipóteses, $U\leq1$ é o critério de escalonabilidade de EDF.

Para A com $C=1,P=4$ e B com $C=2,P=5$, $U=0,25+0,4=0,65$. O limite de RMS para duas tarefas é cerca de 0,828, por isso ambos os critérios aceitam o conjunto. Para A com $C=2,P=4$ e B com $C=3,P=6$, $U=1$ passa em EDF, mas não no limite suficiente de RMS. Neste caso RMS falha: A corre 0–2, B 2–4, A 4–6, e a primeira job de B ainda precisa de uma unidade na sua deadline 6.