Escalonamento de CPU

Um escalonador de CPU escolhe o processo ou a thread no estado de pronto que executará em seguida em uma CPU. A regra que ele segue é sua política. O despachante realiza a escolha ao transferir a execução para a tarefa selecionada. Uma política diferente pode usar o mesmo mecanismo de troca.

Acompanhe as mudanças de estado

Uma tarefa em execução ocupa uma CPU. Uma tarefa pronta poderia executar, mas está esperando sua vez. Uma tarefa bloqueada espera por um evento, como a conclusão de uma leitura de disco. Apenas tarefas prontas são candidatas à seleção.

Suponha que um editor inicie uma leitura de disco enquanto um compilador está pronto. O editor passa de execução para bloqueado, então o compilador pode executar. Quando a leitura termina, uma interrupção deixa o editor pronto novamente. Ele não necessariamente executa imediatamente: a política precisa escolher entre ele e outras tarefas prontas.

Decisões de escalonamento ocorrem quando uma tarefa bloqueia, termina, fica pronta ou é interrompida e devolvida ao estado de pronto. Ceder a CPU voluntariamente também a libera. Preempção significa retirar a CPU de uma tarefa que poderia continuar executando; a tarefa mantém seu estado salvo e pode ser retomada depois.

Uma interrupção do temporizador permite que o núcleo imponha uma fatia de tempo, mesmo que um programa execute um laço sem ceder a CPU. Uma operação de entrada e saída concluída também pode provocar preempção ao deixar pronta uma tarefa mais favorecida. Linux, Windows e macOS usam escalonamento preemptivo.

O trabalho vem em rajadas

Os programas alternam entre rajadas de CPU, quando fazem cálculos, e períodos de espera por entrada e saída. Um programa limitado por processamento, como um codificador, tem longas rajadas de CPU. Um programa limitado por entrada e saída, como um editor, frequentemente processa por pouco tempo e depois espera. Atender rapidamente a um editor após o pressionamento de uma tecla pode melhorar a resposta sem dar a ele muito tempo total de CPU.

O despachante salva o estado da tarefa anterior, restaura os registradores da tarefa escolhida e retoma sua sequência de instruções em modo usuário. Latência de despacho é o tempo necessário para transferir a execução. A troca também afeta os caches e o buffer de tradução de endereços, ou TLB, que armazena traduções de endereços. A próxima tarefa pode precisar preenchê-los novamente, então o tempo para salvar registradores é apenas parte do custo.

Três escalas de tempo do escalonamento

O escalonador de longo prazo admite tarefas enviadas e controla quantas estão no sistema. O escalonador de médio prazo pode suspender processos inteiros, retirando-os da memória e restaurando-os depois. O escalonador de curto prazo seleciona a próxima tarefa pronta e atua frequentemente. Sistemas de uso geral dependem principalmente dessa última função; sistemas em lote e clusters também podem controlar a admissão explicitamente.

Comece uma comparação de políticas com tarefas simples que usam apenas a CPU e têm durações conhecidas. Depois varie uma característica: durações diferentes expõem os atrasos do FIFO, chegadas posteriores expõem os limites da ausência de preempção, operações de entrada e saída criam oportunidades para sobrepor trabalho e durações desconhecidas exigem previsão ou realimentação.

Um escalonamento mostra quando as tarefas executam. Uma métrica indica qual parte desse escalonamento é relevante. Registre a chegada, a primeira execução e a conclusão de cada tarefa antes de calcular qualquer média.

Separe os três tempos

O tempo de retorno mede todo o intervalo entre a chegada e a conclusão. O tempo de resposta mede a demora até a primeira execução. O tempo de espera soma todos os intervalos em que a tarefa está pronta, mas não executa.

Para uma tarefa que usa apenas a CPU, o tempo de retorno é igual à espera mais o tempo de execução na CPU. Com entrada e saída, o tempo bloqueado também faz parte do retorno, então subtrair apenas o tempo de CPU superestimaria a espera. Aqui, a resposta usa a definição baseada na primeira execução; um serviço voltado ao usuário pode medir separadamente o tempo até sua primeira saída.

Analise uma linha do tempo FIFO

A chega em 0 ms e precisa de 8 ms de tempo de CPU. B chega em 1 ms e precisa de 4 ms. C chega em 2 ms e precisa de 2 ms. Sem custo de troca, FIFO resulta em:

• A: 0–8 ms.
• B: 8–12 ms.
• C: 12–14 ms.

O tempo médio de retorno é $\frac{8+11+12}{3}=\frac{31}{3}\approx \mathrm{10,33}$ ms. Os tempos médios de resposta e de espera são ambos $\frac{0+7+10}{3}=\frac{17}{3}\approx \mathrm{5,67}$ ms. Eles coincidem porque cada tarefa executa uma vez sem interrupção. Com preempção, uma tarefa pode voltar a esperar após sua primeira vez, então a espera pode superar a resposta.

Avalie toda a carga de trabalho

A vazão conta as tarefas concluídas por unidade de tempo decorrido. O escalonamento conclui três tarefas em 14 ms, aproximadamente 214,29 tarefas/s. A utilização da CPU é o tempo em que a CPU está ocupada dividido pelo tempo decorrido; aqui é 100% porque a CPU nunca fica ociosa. Especifique o intervalo de medição: acrescentar um período ocioso após a conclusão alteraria ambos os valores.

Uma alta utilização ainda pode vir acompanhada de longas esperas. Ela também não significa necessariamente que todo o tempo ocupado seja trabalho útil das aplicações: medições reais podem contar trocas e outros trabalhos do núcleo como tempo ocupado. Indique se um cálculo de sobrecarga mede tempo ocupado ou trabalho útil.

Escolha o que otimizar

Trabalho em lote frequentemente valoriza o tempo médio de retorno. Trabalho interativo valoriza uma resposta rápida. Serviços compartilhados precisam de acesso justo e também de vazão. Inanição significa que uma tarefa elegível espera indefinidamente, então uma boa média, por si só, não demonstra tratamento justo.

Examine os atrasos individuais e a cauda da distribuição. Um tempo de resposta no percentil 99 descreve o atraso no qual ou abaixo do qual ficam aproximadamente 99% das observações; alguns atrasos graves podem desaparecer dentro de uma média baixa. Sempre subtraia o instante de chegada da própria tarefa e conte seus intervalos de execução como atendimento, nunca como espera.

FIFO, também chamado de primeiro a chegar, primeiro a ser atendido ou FCFS, executa tarefas prontas em ordem de chegada. É não preemptivo: uma chegada posterior não pode interromper uma rajada de CPU em execução. Em exemplos que usam apenas a CPU, cada tarefa selecionada executa até a conclusão.

Observe o efeito comboio

A, B e C chegam juntas. A precisa de 60 ms; B e C precisam de 6 ms cada uma. Com A primeiro, FIFO executa A 0–60, B 60–66 e C 66–72. Os tempos de retorno são 60, 66 e 72 ms, com média de 66 ms. As tarefas pequenas passam a maior parte de seu tempo esperando atrás de A. Esse é o efeito comboio.

Tarefa mais curta primeiro (SJF) seleciona a próxima rajada de CPU mais curta entre as tarefas prontas e não a preempta. Com as mesmas chegadas, executa B 0–6, C 6–12 e depois A 12–72. O tempo médio de retorno passa a ser $\frac{6+12+72}{3}=30$ ms. O trabalho total de CPU continua sendo 72 ms; a melhora vem da conclusão mais cedo das tarefas curtas.

Por que isso ajuda? Se uma rajada longa executa imediatamente antes de uma curta, ambas as tarefas esperam por todo o trabalho anterior. Trocar apenas essas duas reduz o atraso da tarefa curta pela duração da rajada longa, enquanto aumenta o atraso da tarefa longa apenas pela duração da rajada curta. Repetir essas trocas coloca as rajadas em ordem crescente. Quando todas as tarefas chegam juntas e suas durações são conhecidas, SJF minimiza os tempos médios de retorno e de espera; a resposta até a primeira execução também é igual à espera nesse caso não preemptivo com tarefas que usam apenas a CPU.

Restrinja a escolha às tarefas prontas

Agora A chega em 0 ms, enquanto B e C chegam em 10 ms. Em 0 ms, A é a única opção. O SJF não preemptivo executa A 0–60, B 60–66, C 66–72. Os tempos de retorno são 60, 56 e 62 ms, com média de aproximadamente 59,33 ms. SJF não pode agir sobre uma tarefa futura nem interromper uma rajada que já iniciou.

FIFO evita a inanição quando as tarefas à frente acabam liberando a CPU. SJF pode causar inanição de uma tarefa longa em espera se tarefas curtas continuarem chegando.

Preveja uma rajada

A próxima rajada de CPU geralmente é desconhecida. Uma média exponencial combina a última rajada medida com a previsão anterior:

Aqui, $t_n$ é a rajada medida, ${\tau }_n$ a previsão anterior e $\alpha$ um peso entre 0 e 1. Começando com 10 ms e usando $\alpha =\mathrm{0,5}$, uma medição de 6 ms gera uma previsão de 8 ms. Uma medição seguinte de 4 ms gera 6 ms; outra de 6 ms mantém a previsão em 6 ms. Com peso zero, as medições não têm efeito; com peso um, apenas a medição mais recente importa. A grandeza prevista é a duração da rajada de CPU, não o tamanho do arquivo do programa ou o número de linhas.

Menor tempo restante primeiro (STCF, também SRTF) é o SJF preemptivo. Em uma chegada ou conclusão, compare o tempo de CPU de que cada tarefa pronta ainda precisa. Uma recém-chegada interrompe a tarefa atual quando precisa de menos tempo do que resta à atual.

Compare o tempo restante

A precisa de 60 ms e chega em 0 ms. B e C precisam de 6 ms cada uma e chegam em 10 ms. A executa por 10 ms, restando 50 ms. Em 10 ms, B vence porque 6 ms é menos que 50 ms; C tem a mesma duração, então a ordem de chegada e depois o nome resolvem o empate.

A linha do tempo é A 0–10, B 10–16, C 16–22, A 22–72. Os tempos de retorno são A 72 ms, B 6 ms e C 12 ms, com média de 30 ms. Os tempos de resposta são 0, 0 e 6 ms, com média de 2 ms. O SJF não preemptivo com essas chegadas tem médias de aproximadamente 59,33 ms de retorno e 35,33 ms de resposta.

Sempre subtraia o atendimento já recebido. Comparar uma nova rajada de 12 ms com os 60 ms originais de A estaria errado se restassem apenas 5 ms a A. STCF concluiria A primeiro. Com durações conhecidas de tarefas que usam apenas a CPU e custo de troca zero, STCF minimiza o tempo médio de retorno para chegadas arbitrárias. Tarefas longas ainda podem sofrer inanição sob um fluxo contínuo de trabalho mais curto.

Quando todas as tarefas que usam apenas a CPU chegam juntas, SJF e STCF produzem a mesma ordem. A tarefa mais curta em execução só fica mais curta, então nenhuma tarefa em espera se torna motivo para preemptá-la.

Use o tempo de bloqueio de outra tarefa

Uma tarefa bloqueada não pode usar a CPU. Sua espera por entrada e saída é uma oportunidade para executar outras tarefas prontas, mesmo com uma política não preemptiva. A preempção volta a ser relevante quando a conclusão de uma operação de entrada e saída deixa uma rajada curta pronta enquanto outra tarefa executa.

Considere A com cinco rajadas de CPU de 10 ms e uma leitura de disco de 10 ms após cada uma de suas quatro primeiras rajadas. B precisa de uma rajada de CPU de 50 ms. Ambas chegam em 0 ms. Se a CPU ficar ociosa durante as leituras de A e adiar B até A terminar, A conclui em 90 ms e B em 140 ms.

Trate cada rajada de A que retorna como uma tarefa curta pronta:

• A executa 0–10; sua leitura ocupa 10–20 enquanto B executa.
• A retorna para 20–30; restam 40 ms a B, então os 10 ms de A vencem.
• B executa 30–40 durante a próxima leitura. A alternância se repete.
• A última rajada de A executa 80–90; B conclui seus últimos 10 ms durante 90–100.

A ainda termina em 90 ms, mas B termina em 100 ms. A CPU realiza 100 ms de trabalho em 100 ms de tempo decorrido. A atividade de disco e a atividade de CPU se sobrepõem; a CPU não executa A enquanto A está bloqueada. Uma interrupção de dispositivo marca A como pronta quando cada leitura termina, após o que STCF compara sua nova rajada com o trabalho restante de B.

O escalonamento circular (RR) mantém uma fila FIFO de tarefas prontas e dá à tarefa da frente no máximo um quantum, ou fatia de tempo. Uma tarefa que termina ou bloqueia deixa a CPU antes. Uma tarefa que ainda está pronta quando sua fatia termina vai para o fim da fila.

Acompanhe as vezes antes de calcular os tempos

A, B e C chegam em 0 ms e precisam de 9 ms cada uma. Com um quantum de 3 ms, RR executa:

• Primeira rodada: A 0–3, B 3–6, C 6–9.
• Segunda rodada: A 9–12, B 12–15, C 15–18.
• Última rodada: A 18–21, B 21–24, C 24–27.

As primeiras execuções ocorrem em 0, 3 e 6 ms, então o tempo médio de resposta é 3 ms. As conclusões ocorrem em 21, 24 e 27 ms, então o tempo médio de retorno é 24 ms. FIFO resulta em tempo médio de resposta de 9 ms e tempo médio de retorno de 18 ms. Aqui RR inicia todas rapidamente, mas adia a primeira conclusão até 21 ms.

RR divide o acesso à CPU enquanto as tarefas competem; ele não iguala os tempos de conclusão. Uma tarefa curta pode terminar em sua primeira vez. Com um conjunto fixo de $n$ tarefas prontas e quantum $q$, a espera entre as vezes é de no máximo $(n-1)q$ sem custos de troca. Chegadas contínuas, outras classes de prioridade e restrições às CPUs em que uma tarefa pode executar alteram as condições desse limite.

Trate chegadas no limite de uma fatia

Use a ordem de chegada e depois a ordem alfabética para desempates. Uma tarefa que chega exatamente quando uma fatia termina entra antes da tarefa preemptada. Com A chegando em 0 ms e precisando de 8 ms, B em 1 ms precisando de 4 ms e C em 2 ms precisando de 2 ms, um quantum de 2 ms resulta em A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

O intervalo final de A contém duas vezes consecutivas sem concorrente. Os tempos de resposta são 0, 1 e 2 ms; os tempos de retorno são 14, 9 e 4 ms. Suas médias são 1 ms e 9 ms. Quando uma tarefa bloqueada retorna no RR básico, ela entra para uma nova vez; não reserva tempo de CPU não usado enquanto está bloqueada.

Faça o quantum valer seu custo

Um quantum muito grande faz RR se comportar como FIFO para rajadas mais curtas que esse quantum. Um quantum minúsculo cria muitos despachos e perturbações repetidas nos caches. Em uma implementação simples baseada em temporizador, o quantum é um número inteiro de períodos do temporizador.

Para um custo de troca $s$ após cada fatia útil de duração $q$, a fração aproximada de sobrecarga é $\frac{s}{q+s}$. Uma troca de 0,1 ms custa cerca de 9,1% com uma fatia de 1 ms, mas cerca de 0,99% com uma fatia de 10 ms. Fatias mais longas amortizam o custo de troca ao distribuí-lo por mais trabalho útil.

Uma regra prática comum de dimensionamento é permitir que a maioria das rajadas, por exemplo, cerca de 80%, termine em uma fatia. A escolha adequada depende das durações medidas das rajadas e dos atrasos de resposta que a carga de trabalho tolera. Conte as trocas entre tarefas separadamente dos eventos do temporizador que apenas permitem que a mesma única tarefa pronta continue.

Um escalonador por prioridade executa a tarefa pronta de maior prioridade. Tarefas de mesma prioridade podem seguir FIFO ou escalonamento circular. Em uma versão preemptiva, uma tarefa recém-pronta de prioridade mais alta recebe a CPU imediatamente; em uma versão não preemptiva, ela espera até que a tarefa atual a libere.

Identifique a direção da escala

Os números de prioridade não seguem uma direção universal. Nos exemplos dos livros apresentados aqui, use números menores para prioridades mais altas. Os valores de nice do Linux seguem essa direção, mas os níveis de prioridade do Windows e as prioridades de tempo real do Linux usam números maiores para prioridades mais altas.

A, B e C chegam em 0 ms com rajadas de 4, 3 e 5 ms e prioridades 2, 1 e 3. O escalonamento não preemptivo por prioridade executa B 0–3, A 3–7 e C 7–12. Seus tempos de espera são 0, 3 e 7 ms, com média de aproximadamente 3,33 ms; os tempos de retorno são 3, 7 e 12 ms, com média de aproximadamente 7,33 ms.

Uma prioridade interna vem de comportamento medido, como uso da CPU ou esperas por entrada e saída. SJF determina a classificação a partir da duração prevista da rajada. Uma prioridade externa vem de uma pessoa, como um administrador que marca um backup como menos urgente. Nenhuma das escolhas garante que trabalho de baixa prioridade receba tempo de CPU quando há uma chegada contínua de trabalho de prioridade mais alta.

Aumente a prioridade com a espera

O envelhecimento aumenta gradualmente a prioridade de uma tarefa em espera. Se a classificação melhora uma posição a cada 100 ms, uma tarefa que começa na prioridade 20 chega à prioridade máxima 0 após 2 s de espera no estado de pronto. Uma classificação mais alta a coloca em competição com o trabalho favorecido; as regras de desempate determinam a vez de cada tarefa com a mesma classificação.

A inanição é a falta de progresso causada pela seleção repetida de outro trabalho. O envelhecimento a combate mudando a classificação ao longo do tempo. Ele tem uma finalidade diferente da previsão da duração de rajadas: uma tarefa longa que espera há muito tempo pode merecer uma vez, embora sua rajada continue longa.

Acompanhe a dependência na inversão de prioridade

Uma tarefa H de alta prioridade pode estar bloqueada por uma trava mantida pela tarefa L de baixa prioridade. Uma tarefa M de prioridade média pode preemptar L. Agora H não pode prosseguir, embora M tenha prioridade menor que H: L precisa executar primeiro para liberar a trava. Essa é a inversão de prioridade.

Com a herança de prioridade, L herda temporariamente a prioridade de H enquanto mantém a trava de que H precisa. M não consegue mais impedir que L use a CPU. L executa, libera a trava e perde a prioridade herdada; H fica pronta e pode executar.

Aumentar a própria prioridade de H não libera a trava: H continua bloqueada. O essencial é permitir que a thread capaz de satisfazer a dependência execute. Em 1997, a Mars Pathfinder enfrentou um problema de inversão de prioridade que foi resolvido com a ativação da herança de prioridade.

As filas multinível com realimentação (MLFQ) combinam prioridades com escalonamento circular. Seu objetivo é aproximar o atendimento de tarefas curtas e manter respostas rápidas para o trabalho interativo sem receber o tempo futuro de execução de cada tarefa. O uso recente da CPU fornece a realimentação.

Aplique as regras das filas

Cada tarefa pronta pertence a uma fila de prioridade. A versão básica com contabilização segue quatro regras:

1. Escolha a fila de maior prioridade que contenha trabalho pronto.
2. Nessa fila, alterne as tarefas de mesma prioridade com escalonamento circular.
3. Coloque uma nova tarefa na fila mais alta.
4. Rebaixe uma tarefa quando ela consumir sua cota de tempo de CPU no nível atual, contando o uso ao longo de todas as vezes em que executou e das interrupções por entrada e saída.

Um quantum limita uma vez de execução. Uma cota limita o atendimento total em um nível de prioridade. Um nível pode permitir vários quanta antes do rebaixamento. No nível mais baixo, um rebaixamento mantém a tarefa na fila inferior.

Isso dá a uma nova tarefa a chance de terminar rapidamente. Uma tarefa que consome tempo de CPU repetidamente revela uma demanda maior e desce. Uma rajada curta que bloqueia consome pouca cota, então tarefas interativas tendem a permanecer nos níveis superiores por mais tempo.

Acompanhe uma tarefa longa e uma recém-chegada

Use as filas Q2, Q1 e Q0, com Q2 como a mais alta, quanta de 10 ms e cotas de 10 ms em cada nível, sem elevação de prioridade durante este acompanhamento. A precisa de 200 ms e chega em 0 ms. Ela executa em Q2 de 0–10, em Q1 de 10–20 e depois em Q0.

Em 100 ms, A recebeu 100 ms de tempo de CPU. B chega precisando de 20 ms. B entra em Q2 e preempta A, depois executa 100–110 em Q2. Ela consumiu a cota desse nível e desce para Q1. Q1 tem prioridade maior que Q0, onde está A, então B executa 110–120 e termina. A retoma em 120 e conclui seus 100 ms restantes em 220 ms. O tempo de retorno de B é 20 ms, apesar de chegar depois de uma tarefa muito mais longa.

Acompanhe o trabalho restante de A enquanto B executa: ele permanece em 100 ms. O tempo decorrido avança durante o atendimento de B, mas A não recebe atendimento da CPU nesse período.

Separe espera de consumo de CPU

Um editor que executa por 1 ms e espera por entrada usa uma cota de 10 ms ao longo de dez dessas rajadas. O tempo bloqueado não conta na cota de CPU. Com contabilização rigorosa, essas rajadas curtas ainda se somam, então o editor acaba descendo, a menos que uma elevação de prioridade o reinicie primeiro.

Uma regra inicial da MLFQ rebaixava apenas tarefas que usavam um quantum inteiro sem interrupção. Uma tarefa que cedia a CPU pouco antes do fim mantinha sua prioridade. Essa regra tornava o trabalho interativo responsivo, mas também permitia manipulação deliberada. Contar o uso cumulativo de CPU fecha essa brecha.

As filas inferiores executam sempre que nenhuma fila superior tem trabalho pronto. Uma tarefa de prioridade mais alta que está bloqueada não impede que tarefas de prioridade mais baixa usem a CPU. Sob demanda contínua de alta prioridade, o trabalho de prioridade mais baixa precisa de um mecanismo adicional contra a inanição, fornecido por elevações periódicas.

A realimentação cria uma separação útil, mas o comportamento passado de uma tarefa pode deixar de representar suas necessidades atuais. Um cálculo longo pode se tornar interativo mais tarde. Enquanto isso, uma tarefa na fila inferior pode esperar indefinidamente se as filas superiores permanecerem ocupadas.

Reavalie cada tarefa periodicamente

Uma elevação de prioridade move todas as tarefas de volta para a fila mais alta após um período $S$. Ela permite que tarefas em espera compartilhem a fila superior e que o escalonador aprenda novamente o comportamento alterado. Uma tarefa promovida e limitada por processamento depois consome sua cota e volta a descer.

Considere as primeiras regras da MLFQ: duas tarefas interativas sempre cedem a CPU antes de uma fatia completa de 10 ms e juntas mantêm Q2 ocupada. Uma tarefa limitada por processamento espera em Q0. Sem elevações, ela não recebe atendimento. Em um escalonamento repetitivo no qual uma elevação a cada 100 ms lhe dá uma vez de 10 ms no nível superior antes de ser rebaixada e o trabalho de maior prioridade ocupa o restante, ela recebe 10% da CPU. Essa porcentagem vem deste acompanhamento; uma elevação não atribui uma parcela fixa geral.

Um período de elevação longo deixa esperas longas entre oportunidades. Um período muito curto reinicia repetidamente o trabalho limitado por processamento e enfraquece a vantagem do trabalho interativo. Alguns projetos usaram períodos em torno de um segundo, mas o período é uma escolha de ajuste baseada no comportamento da carga de trabalho e nos objetivos de resposta.

Contabilize o uso entre cessões da CPU

Um problema separado é a manipulação do escalonador. Pela regra inicial da fatia completa, um programa pode executar por 9 ms, solicitar uma operação de entrada e saída de 1 ms e repetir. Ele nunca usa uma fatia inteira de 10 ms de uma vez, então mantém a prioridade máxima enquanto consome quase todo o tempo de CPU disponível.

Com uma cota cumulativa de 10 ms, a primeira rajada consome 9 ms e deixa 1 ms. Após a operação de entrada e saída, mais um milissegundo esgota a cota, e a tarefa é rebaixada durante sua segunda rajada. Uma requisição de entrada e saída muda o estado; ela não apaga o atendimento já recebido. A regra de contabilização impede essa tática mesmo sem uma elevação.

Ajuste os níveis

Escolha o número de filas, o quantum de cada fila, a cota de cada nível e o período de elevação. As filas superiores geralmente usam quanta curtos, por exemplo, 10 ms, para alternar rapidamente entre tarefas interativas. Filas inferiores podem usar quanta muito mais longos, às vezes centenas de milissegundos, para reduzir as trocas durante processamento contínuo.

A cota pode crescer independentemente do quantum. Um nível com quantum de 5 ms e cota de 15 ms pode permitir três vezes completas antes do rebaixamento. Aumentar a cota adia a classificação como tarefa de longa duração; aumentar o quantum prolonga uma vez individual.

O projeto de compartilhamento de tempo do Solaris ilustra a realimentação baseada em tabela: sua tabela clássica configurável tem 60 níveis de prioridade, com quanta que vão de aproximadamente 20 ms em alta prioridade até algumas centenas de milissegundos em baixa prioridade. Projetos clássicos do BSD, por sua vez, calculavam a prioridade a partir do uso recente da CPU, que decai ao longo do tempo. Ambos fazem o uso antigo da CPU perder influência, de modo que o histórico distante de uma thread não determina permanentemente seu tratamento.

O escalonamento por parcela proporcional busca dividir o atendimento da CPU de acordo com parcelas atribuídas. No escalonamento por loteria, cada tarefa apta a executar possui bilhetes. Um bilhete vencedor aleatório escolhe a tarefa para a próxima fatia de igual duração. A chance de uma tarefa vencer é seu número de bilhetes dividido pelo total de bilhetes das tarefas aptas a executar.

Localize um bilhete vencedor

A possui 100 bilhetes, B 50 e C 250. Numere os 400 bilhetes de 0 a 399. A possui 0–99, B possui 100–149 e C possui 150–399. Um sorteio de 300 seleciona C.

Uma implementação baseada em lista sorteia um número e acumula as quantidades de bilhetes. Os totais acumulados são 100 após A, 150 após B e 400 após C. Pare no primeiro total estritamente maior que o número sorteado. Usar “maior ou igual” atribuiria incorretamente os bilhetes nos limites: o número sorteado 100 pertence a B. Colocar primeiro quem possui mais bilhetes reduz o tamanho médio dessa busca na lista.

Diferencie expectativa de garantia

Com A possuindo 75 bilhetes e B 25, a parcela esperada de A é 75%. Em 100 sorteios independentes de fatias iguais com ambas aptas a executar, espera-se que A vença 75 vezes. O desvio padrão é:

$\sqrt{100\times \mathrm{0,75}\times \mathrm{0,25}}\approx \mathrm{4,33}$ fatias.

Um resultado de aproximadamente 71–79 vitórias está a cerca de um desvio padrão da média; não é um intervalo garantido. Execuções curtas podem se afastar bastante da proporção pretendida de 3:1. À medida que o intervalo de observação cresce, a variação aleatória relativa diminui. A loteria proporciona justiça probabilística, não uma divisão exata em um intervalo finito nem uma espera limitada até a próxima vez.

Para duas tarefas com quantidades iguais de bilhetes e demandas iguais de CPU, a métrica de injustiça U divide o instante de conclusão da primeira pelo da última. A razão chega a 1 quando terminam juntas e é menor quando uma termina muito antes. Essa razão entre conclusões é especialmente variável para tarefas curtas escalonadas por loteria.

Distribua bilhetes entre usuários e dependências

A moeda de bilhetes permite que um usuário divida localmente um direito global atribuído. O usuário X tem 200 bilhetes globais e atribui 300 bilhetes locais a X1 e 100 a X2. Dos 400 bilhetes locais, X1 tem três quartos, o que lhe dá 150 bilhetes globais; X2 recebe 50. O usuário Y tem 100 bilhetes globais para Y1. O total é 300, então X1 recebe uma parcela esperada de 50%, X2 cerca de 16,67% e Y1 cerca de 33,33% da CPU disputada.

A transferência de bilhetes empresta temporariamente os bilhetes de um cliente a um servidor que trabalha para ele e depois os devolve quando a requisição termina. Isso acompanha a dependência de trabalho. A inflação de bilhetes permite que tarefas cooperantes aumentem suas próprias quantidades de bilhetes para solicitar mais atendimento. Ela exige confiança ou limites: a inflação sem restrições permite que uma tarefa gananciosa reduza as parcelas de todas as outras.

A loteria precisa dos totais de bilhetes, mas não de um registro de quanto cada tarefa está adiantada em atendimento. Uma nova tarefa simplesmente acrescenta seus bilhetes ao conjunto das tarefas aptas a executar. A atribuição dos bilhetes continua sendo uma escolha de política; o sorteio aleatório implementa essa escolha em termos de expectativa. Os bilhetes de uma tarefa bloqueada não competem por uma fatia que ela não pode usar.

O escalonamento por passos transforma parcelas de bilhetes em uma sequência determinística. Cada tarefa apta a executar tem um passo, calculado como uma constante grande dividida por seus bilhetes, e um valor de passagem que registra seu progresso ponderado. Escolha o menor valor de passagem, execute essa tarefa por uma fatia de igual duração e depois some seu passo ao seu valor de passagem.

Calcule os passos

A tem 50 bilhetes, B 25 e C 100. Com a constante 1.000, seus passos são 20, 40 e 10. Mais bilhetes produzem um passo menor. O valor de passagem de uma tarefa favorecida cresce lentamente, então se torna o mínimo com mais frequência.

Comece todos os valores de passagem em zero e resolva empates alfabeticamente. Mantenha a tupla na ordem fixa A, B, C:

Somente o valor de passagem da tarefa selecionada muda. Em sete fatias, A recebe duas vezes, B uma e C quatro: a proporção exata de 50:25:100. No valor de passagem comum de 40, cada uma avançou pela mesma quantidade de atendimento ponderado. Entre esses alinhamentos, as parcelas em intervalos curtos não precisam ser exatas.

Separe atendimento real e progresso virtual

O valor de passagem é um valor de ordenação, não o tempo decorrido nem uma contagem de bilhetes. O passo grande de B faz com que ela espere enquanto A e C alcançam seu valor de passagem. Ela ainda recebe sua parcela pretendida de um sétimo nesse ciclo repetitivo. Somar a quantidade de bilhetes ao valor de passagem inverteria o projeto: a tarefa com mais bilhetes daria o maior salto e seria selecionada com menos frequência.

A constante controla a escala dos passos, não as proporções pretendidas dos bilhetes. Implementações com números inteiros precisam de precisão suficiente para evitar distorcer essas proporções pelo arredondamento. Comparações e atualizações precisam usar uma escala consistente.

Posicione uma recém-chegada de modo adequado

Suponha que tarefas já presentes tenham valores de passagem em torno de 4.000. Uma nova tarefa começando em zero venceria repetidamente enquanto alcançasse as demais, mesmo que tivesse poucos bilhetes. Inicialize seu valor de passagem em relação ao progresso atual do sistema, por exemplo, com o valor mínimo atual, para que ela não acumule atendimento referente ao tempo anterior à sua chegada.

O tempo de execução virtual do Linux usa a ideia relacionada de contabilizar progresso ponderado pelo atendimento real da CPU. Em ambos os projetos, um direito maior faz esse progresso crescer mais lentamente, mantendo a tarefa competitiva para atendimento posterior.

Os escalonadores justos do Linux acompanham o atendimento ponderado de CPU. O escalonador completamente justo (CFS), introduzido no Linux 2.6.23 em 2007, escolhia a tarefa apta a executar com o menor tempo de execução virtual. O Linux começou a substituir essa regra de seleção pelo EEVDF na versão 6.6 em 2023.

Divida o atendimento por peso

Um valor de nice vai de −20, o mais favorecido, a +19, o menos favorecido. Nice 0 tem peso 1024. Cada passo em direção a um valor de nice maior reduz o peso por um fator de aproximadamente 1,25. Exemplos de pesos são 3121 para nice −5, 820 para nice 1, 335 para nice 5, 110 para nice 10 e 15 para nice 19.

Nice 0 contra nice 1 resulta em $\frac{1024}{1024+820}\approx \mathrm{0,555}$, aproximadamente 55,5% contra 44,5%. As parcelas dependem aproximadamente da diferença entre os valores de nice: $3121\mathrm{/}1024$ e $335\mathrm{/}110$ são ambos aproximadamente 3,05. Nice +19 competindo com nice 0 ainda recebe cerca de 1,4% nesse modelo simples de duas tarefas.

O CFS clássico distribui uma latência de escalonamento alvo por peso:

Para pesos 1024, 1024 e 335, o total é 2383. Um período alvo de 48 ms dá aproximadamente 20,63 ms a cada tarefa de peso maior e 6,75 ms à de peso menor. Esses parâmetros são ilustrativos, não padrões universais do núcleo. Com quatro tarefas iguais, 48 ms dão 12 ms a cada uma. Com dez, 4,8 ms para cada uma ficaria abaixo de uma granularidade mínima ilustrativa de 6 ms, então o período precisa crescer.

Contabilize o progresso virtual

O CFS aumenta o tempo de execução virtual de uma tarefa em execução em:

Uma tarefa de peso 1024 ganha um milissegundo virtual por milissegundo real. Uma tarefa de peso 335 ganha aproximadamente 3,06. Contabilizar mais rapidamente as tarefas de menor peso faz com que esperem mais cedo, enquanto tarefas de maior peso recebem mais atendimento real.

O CFS clássico ordena as tarefas aptas a executar que estão na fila em uma árvore rubro-negra pelo tempo de execução virtual. Inserção e remoção têm custo de tempo logarítmico; um ponteiro armazenado para o nó mais à esquerda permite encontrar o mínimo em tempo constante. Tarefas bloqueadas saem dessa árvore de tarefas aptas a executar. O posicionamento ao despertar impede que uma longa suspensão anterior se transforme em uma reivindicação ilimitada de atendimento para recuperar o tempo.

Escolha entre tarefas elegíveis com EEVDF

O primeiro prazo virtual elegível mantém pesos e a contabilização do atendimento virtual. Uma tarefa tem defasagem de serviço positiva quando ainda lhe é devido atendimento e negativa quando recebeu mais que seu direito. Tarefas com defasagem não negativa são elegíveis. O EEVDF seleciona a tarefa elegível com o prazo virtual mais próximo.

O prazo combina o início virtual de uma requisição com sua duração de atendimento solicitada, ajustada ao tempo virtual. É um valor de ordenação do atendimento, não uma promessa de horário real de conclusão. Uma fatia solicitada mais curta pode dar a uma tarefa elegível um prazo mais próximo e melhorar a latência sem aumentar sua parcela de longo prazo determinada pelo peso. O Linux atual oferece suporte a solicitações de fatia por meio de sched_setattr().

Várias CPUs só ajudam quando há trabalho paralelo. Uma única thread executa em uma CPU lógica por vez; várias threads ou programas independentes podem usar várias CPUs juntos. Um escalonador precisa escolher tanto qual tarefa executa quanto onde ela executa.

Compartilhe a responsabilidade pelo escalonamento

No multiprocessamento simétrico (SMP), as CPUs executam código do núcleo e tomam suas próprias decisões de escalonamento. No multiprocessamento assimétrico, um processador principal coordena o escalonamento enquanto os demais executam o trabalho atribuído. O controle central é mais simples, mas o processador principal pode se tornar um gargalo. Sistemas de uso geral usam SMP.

Decisões simultâneas exigem coordenação. Se duas CPUs removem tarefas de uma fila compartilhada de prontos, suas atualizações precisam ser sincronizadas para que nenhuma entrada seja perdida nem a mesma tarefa da fila seja selecionada duas vezes. Mais CPUs podem aumentar a contenção por essa estrutura compartilhada.

Preserve o conteúdo útil dos caches

Os núcleos têm caches pequenos e rápidos, normalmente caches L1 e L2 privados e um L3 maior compartilhado por vários núcleos. Localidade temporal significa reutilizar dados acessados recentemente. Localidade espacial significa acessar dados próximos, como elementos consecutivos de um vetor.

Uma thread de ordenação no núcleo 0 preenche seus caches e sua TLB. Se ela retomar nesse núcleo após uma breve preempção, muitas entradas necessárias ainda podem estar presentes. No núcleo 3, ela pode precisar buscar os mesmos dados novamente em um cache compartilhado ou na memória. Afinidade de cache é a tendência do escalonador de manter uma thread próxima da CPU que ela usou recentemente. O benefício exato depende do que permanece em cache e da topologia de compartilhamento dos caches.

Separe coerência de sincronização

A coerência de cache impede que núcleos usem indefinidamente cópias conflitantes armazenadas em cache de uma única posição de memória. O monitoramento do barramento é uma ideia de implementação: caches observam o tráfego e invalidam ou atualizam cópias quando outro núcleo escreve. Sistemas maiores podem usar outros mecanismos de coerência.

A coerência não transforma várias instruções em uma operação atômica. Se duas CPUs leem o tamanho de uma fila, alteram entradas e escrevem o tamanho de volta, leituras e escritas individuais coerentes ainda permitem intercalações prejudiciais. O escalonador precisa de travas ou outro método de sincronização para toda a atualização. A própria linha de cache compartilhada de uma trava pode se mover entre núcleos à medida que competem por ela.

Interprete a organização do hardware

A Intel chama sua implementação de SMT de Hyper-Threading. Duas threads ocupadas em CPUs lógicas do mesmo núcleo competem pelos recursos desse núcleo; duas CPUs lógicas não equivalem a dois núcleos físicos independentes. Uma migração em NUMA também pode afastar o processamento da memória que ele usa, mesmo quando o preenchimento do cache é rápido.

Mover uma thread para uma CPU ociosa pode eliminar um longo atraso na fila. Mantê-la no lugar pode preservar a localidade. Compare esses custos usando a carga de trabalho real: afinidade é uma preferência de desempenho, enquanto uma máscara de afinidade explícita restringe quais CPUs são permitidas.

Um escalonador multiprocessador precisa de um lugar para manter o trabalho pronto. Uma fila compartilhada facilita encontrar trabalho. Filas separadas por CPU reduzem a contenção compartilhada e preservam a distribuição, mas podem deixar uma CPU sobrecarregada enquanto outra está ociosa.

Compare projetos de filas

No escalonamento multiprocessador com fila única, todas as CPUs retiram trabalho de uma fila compartilhada. Se as tarefas podem executar em todas as CPUs, o trabalho em espera naturalmente ocupa uma CPU ociosa. Uma trava compartilhada protege a fila, então aumentar o número de CPUs pode transformar essa trava em um gargalo.

Com cinco tarefas A–E em escalonamento circular em quatro CPUs, uma sequência atribui A, B, C, D na primeira rodada; E, A, B, C na segunda; e D, E, A, B na terceira. A executa na CPU 0, depois na 1 e depois na 2. A máquina permanece ocupada, mas A troca repetidamente de caches privados. Regras de afinidade podem manter a maior parte da distribuição enquanto movem tarefas selecionadas para equilibrar o trabalho.

Observe parcelas desiguais

No escalonamento multiprocessador com múltiplas filas, cada CPU escalona sua própria fila. Suponha que a CPU 0 tenha A e C e a CPU 1 tenha B e D, todas limitadas por processamento e compartilhando localmente em escalonamento circular. Inicialmente cada tarefa recebe metade de uma CPU. Quando C termina, A recebe toda a CPU 0 enquanto B e D ainda recebem metade da CPU 1 cada uma.

A máquina continua plenamente utilizada, mas as tarefas deixam de receber parcelas iguais. Se A também terminar, a CPU 0 fica ociosa embora B e D estejam prontas. Mover uma delas para a CPU 0 dá uma CPU inteira a ambas e usa capacidade antes ociosa.

Com três tarefas iguais limitadas por processamento e duas CPUs, o atendimento igual no longo prazo é de dois terços de uma CPU por tarefa. Uma distribuição fixa deixa uma tarefa sozinha e duas compartilhando. Alternar periodicamente qual tarefa fica sozinha pode aproximar a divisão igual. Nenhuma thread executa nas duas CPUs ao mesmo tempo.

Decida quando migrar

A migração move uma tarefa para a fila de outra CPU. O roubo de trabalho é uma estratégia de busca: uma CPU com pouco trabalho examina a fila de uma CPU mais ocupada e retira trabalho dela. Verificações frequentes criam tráfego de sincronização; verificações raras deixam o desequilíbrio sem solução. O roubo também precisa respeitar a elegibilidade das CPUs e a localidade da memória.

Compare o tempo de espera que se espera economizar com o custo da migração. Uma fila longa em uma CPU e uma CPU compatível ociosa criam um forte motivo para mover uma tarefa. Uma pequena diferença temporária entre filas pode desaparecer antes que os custos de preencher os caches sejam recuperados.

Os projetos O(1) e CFS do Linux usavam filas de tarefas prontas por CPU; o Linux equilibra a carga entre domínios de escalonamento do hardware, considerando núcleos compartilhados e soquetes. O BF Scheduler, uma alternativa, usava uma fila única. Usuários podem restringir a distribuição com taskset ou sched_setaffinity() no Linux e SetThreadAffinityMask() no Windows. Uma máscara de afinidade restrita pode explicar por que uma tarefa pronta não usa uma CPU que parece ociosa.

O Linux escalona threads, chamadas de tarefas no núcleo. A política de escalonamento, o valor de nice, os controles de grupo e a afinidade de CPU de uma tarefa respondem a perguntas diferentes sobre quando e onde ela executa.

Examine primeiro a política

As políticas normais têm prioridade estática 0. FIFO e RR de tempo real usam 1–99, em que 99 é a mais alta. Uma tarefa FIFO continua até bloquear, ceder a CPU ou ser preemptada por trabalho de prioridade mais alta. RR acrescenta alternância entre tarefas de mesma prioridade; sched_rr_get_interval() informa seu quantum. Esses nomes descrevem políticas do Linux: o escalonamento justo normal não é o algoritmo RR de fatias iguais dos livros.

Altere parcelas e distribuição

Nice vai de −20 a +19, com padrão 0. Valores maiores reduzem o peso na classe justa, por um fator de aproximadamente 1,25 por passo. Em uma inicialização típica com nice 0, nice -n 10 make inicia uma compilação com nice 10; -n é um ajuste ao valor de nice herdado. renice -n 5 -p 4321 define o processo indicado com nice 5. Um usuário pode tornar seu próprio trabalho menos favorecido; aumentar a prioridade exige privilégio adequado ou um limite de recursos que o permita.

taskset -c 0,1 ./app permite que um programa execute nas CPUs 0 e 1. Ele não cria uma segunda thread nem promete qualquer uma das CPUs exclusivamente. ps -o pid,cls,ni,rtprio,comm mostra campos relacionados à política, enquanto top ajuda a observar prioridade, nice e consumo de CPU.

chrt -f 50 ./app seleciona a prioridade de tempo real FIFO 50. Use configurações de tempo real apenas em um ambiente controlado: uma thread ocupada de alta prioridade pode atrasar o interpretador de comandos e o trabalho essencial do sistema. Os limites padrão de tempo de CPU para tarefas de tempo real reservam algum tempo para trabalho normal, mas não garantem que toda carga desse tipo responda rapidamente. A precedência altera o acesso ao atendimento da CPU, não a velocidade de uma instrução.

Diferencie peso de grupo de cota

No cgroup v2, cpu.weight vai de 1 a 10000, com padrão 100, e divide a capacidade disputada da CPU na classe justa entre grupos ativos do mesmo nível. Pesos 200 e 100 dão aproximadamente dois terços e um terço de uma CPU quando ambos os grupos estão ocupados. Se o segundo ficar ocioso, o primeiro poderá usar toda a capacidade disponível.

cpu.max define um limite de tempo de CPU. O valor “50000 100000” permite 50 ms de tempo agregado de CPU por período de 100 ms, equivalente a metade de uma CPU em média. Várias threads podem consumir esse orçamento em paralelo e esgotá-lo mais cedo no tempo decorrido. Um grupo sujeito a limite pode ter seu uso restringido mesmo quando há capacidade de CPU disponível.

Situe os nomes na história

O escalonador O(1) do Linux 2.6.0 usava vetores de prioridade e realimentação de interatividade. O CFS chegou na versão 2.6.23 em 2007. O Linux 6.6 em 2023 começou a transição para a seleção EEVDF na classe justa. Desde o Linux 6.12 em 2024, sched_ext oferece suporte a políticas de escalonamento BPF carregadas dinamicamente em núcleos configurados para isso. Se esse escalonador falhar ou impedir o progresso de tarefas aptas a executar, o núcleo restaura o escalonamento interno.

O Windows escalona threads prontas por prioridade de 0 a 31, com números maiores indicando prioridades mais altas. Threads prontas de mesma prioridade se alternam em escalonamento circular. Uma thread recém-pronta de prioridade mais alta preempta uma de prioridade mais baixa sem esperar o fim de seu quantum. A prioridade 0 pertence à thread de zeragem de páginas, que preenche com zeros as páginas livres.

Encontre a prioridade base a partir de duas configurações

A prioridade base de uma thread depende da classe de prioridade de seu processo e de seu próprio nível relativo de thread. As classes de processo são Idle, Below normal, Normal, Above normal, High e Realtime. Os níveis de thread incluem Idle, Lowest, Below normal, Normal, Above normal, Highest e Time critical.

Time critical resulta em 15 fora da classe Realtime e em 31 dentro dela. O nível de thread Idle resulta em 1 fora de Realtime e em 16 dentro dela. Esses níveis extremos são entradas especiais da tabela, então somar um deslocamento fixo a cada classe produziria resultados errados.

Acompanhe uma elevação temporária

As prioridades 1–15 são a faixa variável; 16–31 são a faixa de tempo real. Uma thread começa com prioridade dinâmica igual à prioridade base. Para threads na faixa variável, eventos como entrada ou conclusão de uma espera podem elevar temporariamente a prioridade dinâmica. Threads com prioridades base de tempo real não recebem essas elevações.

Suponha que uma thread com prioridade base 8 seja elevada a 14. Se ela continuar processando, sua prioridade dinâmica cai um nível após cada quantum completo: 13 após o primeiro, 12 após o segundo e 8 após o sexto. A elevação não muda permanentemente a prioridade base e não decai abaixo dela.

Isso é realimentação: trabalho recém-desbloqueado recebe atendimento rápido, enquanto o uso contínuo de CPU perde a vantagem temporária. O Windows também usa elevações temporárias para threads prontas que esperam há muito tempo, a fim de combater a inanição. Essa elevação pode ajudar quem mantém uma trava e tem classificação baixa a progredir, mas é um mecanismo diferente da herança de prioridade específica de uma trava.

Reconheça projetos relacionados

A classe de compartilhamento de tempo do Solaris é um projeto de MLFQ orientado por tabela. O ULE do FreeBSD usa filas de tarefas prontas por CPU e compara o comportamento de suspensão com o de execução para identificar threads interativas. Esses sistemas compartilham a ideia de adaptar o atendimento ao comportamento observado sem usar regras de filas idênticas.

O macOS oferece classes de qualidade de serviço (QoS), incluindo interativa para o usuário, iniciada pelo usuário, padrão, utilitária e em segundo plano. Elas descrevem a urgência do trabalho. Em Apple silicon, a QoS ajuda o sistema a distribuir o trabalho entre núcleos de desempenho e de eficiência. Os programas comunicam a importância do trabalho; o sistema operacional escolhe a distribuição de acordo com a política e o hardware disponível.

Escalonadores reais combinam realimentação, prioridades, justiça e afinidade. Uma classe Realtime do Windows tem precedência maior, mas não garante cálculos mais rápidos nem correção completa de tempo real.

Escolha o objetivo da carga de trabalho antes de escolher um escalonador. Uma fila de tarefas em lote pode valorizar a conclusão rápida de muitas tarefas pequenas. Um editor precisa de atendimento rápido após uma entrada. Um servidor compartilhado precisa de uma distribuição justificável entre usuários ou grupos.

Associe o mecanismo ao objetivo

Compare políticas com entradas idênticas

A chega em 0 ms precisando de 8 ms, B em 1 ms precisando de 4 ms e C em 2 ms precisando de 2 ms. Ignore o custo de troca. FIFO executa A, B, C. SJF também começa por A, mas depois executa C antes de B. STCF executa A 0–1, B 1–2, C 2–4, B 4–7, A 7–14. RR usa um quantum de 2 ms, com chegadas no limite da fatia entrando na fila antes da tarefa cuja fatia terminou.

STCF vence nas duas métricas nessa carga porque cada tarefa mais curta recém-chegada executa imediatamente. RR proporciona um início rápido sem conhecer as durações das rajadas. Com tarefas de mesma duração que chegam simultaneamente, FIFO pode ter menor tempo médio de retorno que RR. Uma classificação em uma carga de trabalho é uma evidência sobre essa carga.

Escolha um método de avaliação

A modelagem determinística calcula manualmente uma sequência fixa. Ela fornece resultados exatos para suas entradas e facilita a análise das decisões, mas frequentemente deixa de fora os custos de despacho e de cache. Modelos de filas descrevem padrões de chegada e atendimento usando distribuições e preveem o comportamento médio.

Para um sistema estável em regime permanente, a lei de Little relaciona a população média $n$, a taxa de chegada $\lambda$ e o tempo médio de permanência $W$:

Com 14 tarefas/s e tempo médio de 0,5 s no sistema, a população média é de 7 tarefas. Mantenha o limite de observação consistente: a população da fila de prontos exige o tempo de espera nessa fila, enquanto a população de todo o sistema exige o tempo em todo o sistema. Converta as unidades antes de multiplicar.

A simulação executa um modelo de escalonador, frequentemente com um registro de carga de trabalho. Ela pode testar padrões complexos de chegada e bloqueio, mas suas conclusões dependem do modelo e dos registros escolhidos. A implementação avalia o escalonador em um sistema operacional real e inclui a sobrecarga efetiva; exige mais esforço e ainda precisa de cargas representativas e medições reproduzíveis.

Examine vazão, utilização, atrasos individuais e na cauda, justiça e consumo de energia junto com as médias. Em um multiprocessador, uma máquina ocupada ainda pode dividir o atendimento de forma desigual ou desperdiçar tempo preenchendo caches novamente. Compare políticas usando o mesmo intervalo de observação e a mesma carga de trabalho e depois varie as características da carga que importam para os usuários pretendidos.