Escalonadores

Escalonador

Algoritmo mais simples

Round-robin

Refinamento comum

Baseado em prioridade / fila multinível

Troca principal

Throughput vs latência vs justiça

Um escalonador decide qual tarefa pronta para rodar recebe a CPU em seguida, e por quanto tempo, sempre que uma troca de contexto é disparada. A multitarefa fornece o mecanismo para trocar entre tarefas; o escalonador é a política que governa esse mecanismo, e políticas diferentes fazem trocas genuinamente diferentes, e frequentemente conflitantes, entre throughput, responsividade e justiça: não existe um único algoritmo de escalonamento que seja inequivocamente o melhor para toda carga de trabalho.

Round-robin

O escalonador mais simples e amplamente usado, round-robin, dá a toda tarefa pronta um time slice (ou quantum) fixo em uma rotação fixa, movendo para a próxima tarefa na lista quando o slice da atual expira ou ela bloqueia voluntariamente. Não exige noção alguma de prioridade de tarefa e trata toda tarefa pronta de forma idêntica, o que o torna simples de implementar corretamente e garante que nenhuma tarefa possa ser esfomeada indefinidamente (toda tarefa na lista de prontas eventualmente tem sua vez), mas também não faz distinção alguma entre uma tarefa que genuinamente precisa rodar com frequência e uma que não precisa, aplicando a mesma rotação fixa de qualquer forma.

struct task *round_robin_next(struct task *current) {
    struct task *next = current->next ? current->next : ready_list_head;
    while (next->state != READY) {
        next = next->next ? next->next : ready_list_head;
    }
    return next;
}

A escolha do comprimento do time slice em si é uma troca real: longo demais, e o sistema parece sem resposta, já que uma tarefa esperando sua vez pode esperar um slice inteiro de toda outra tarefa pronta antes de conseguir o dela; curto demais, e o overhead da troca de contexto, em si não gratuito, começa a consumir uma fração significativa do tempo total de CPU que, de outra forma, teria ido para trabalho útil.

Escalonamento baseado em prioridade

O escalonamento por prioridade atribui a cada tarefa um valor de prioridade e sempre roda a tarefa pronta de maior prioridade disponível, só considerando uma tarefa de prioridade mais baixa quando nada de prioridade mais alta está atualmente pronto. Isso permite que um escalonador favoreça trabalho sensível à latência (uma tarefa interativa esperando entrada do usuário) sobre trabalho em segundo plano (uma computação em lote sem urgência), mas introduz um risco real de starvation: uma tarefa de baixa prioridade pode, em princípio, nunca rodar se tarefas de prioridade mais alta permanecerem continuamente prontas. Escalonadores de prioridade práticos comumente mitigam isso através de envelhecimento de prioridade (elevando gradualmente a prioridade efetiva de uma tarefa quanto mais tempo ela passa sem rodar), garantindo que toda tarefa eventualmente cruze o limiar que a torna competitiva com tarefas que começaram com prioridade mais alta. Prioridade sozinha também cria uma falha mais sutil do que a starvation pura: um lock segurado por uma tarefa de baixa prioridade pode travar uma de alta prioridade indiretamente através de uma terceira tarefa, sem relação alguma, um cenário coberto por completo em inversão de prioridade.

Filas multinível com feedback

Uma fila multinível com feedback combina escalonamento round-robin e por prioridade: várias filas round-robin existem simultaneamente, cada uma associada a um nível de prioridade diferente e, tipicamente, um comprimento de time slice diferente (filas de prioridade mais alta recebem slices mais curtos, favorecendo responsividade; filas de prioridade mais baixa recebem slices mais longos, favorecendo throughput para trabalho limitado por CPU), e uma tarefa se move entre filas com base em seu comportamento observado, não em uma prioridade fixa atribuída externamente. Uma tarefa que repetidamente usa todo seu time slice sem bloquear (comportamento característico de trabalho limitado por CPU) é rebaixada ao longo do tempo para uma fila de prioridade mais baixa e slice mais longo; uma tarefa que frequentemente bloqueia antes que seu slice expire (característica de trabalho interativo ou limitado por I/O) é promovida ou mantida em uma fila de prioridade mais alta e slice mais curto, já que raramente consome muito tempo de CPU independentemente de sua prioridade nominal. Essa estrutura adaptativa, em vez de qualquer algoritmo único e fixo, é mais próxima do que kernels de propósito geral de produção de fato implementam, já que aproxima favorecer responsividade interativa sem exigir que nenhuma tarefa declare explicitamente seu próprio comportamento de antemão.

Considerações de tempo real

Cargas de trabalho com requisitos rígidos de tempo (uma tarefa que precisa rodar dentro de um tempo limitado e garantido a partir de quando fica pronta, não apenas “eventualmente”) precisam de garantias de escalonamento que nenhum dos algoritmos acima fornece por si só, já que os três são fundamentalmente de melhor esforço em relação a exatamente quando uma determinada tarefa de fato roda. Algoritmos de escalonamento de tempo real, como rate-monotonic ou earliest-deadline-first, existem especificamente para fornecer essas garantias para cargas de trabalho que precisam delas, ao custo de contabilidade adicional (o período ou prazo de cada tarefa precisa ser conhecido e respeitado) que um kernel hobby de propósito geral raramente precisa implementar, a menos que tenha como alvo especificamente casos de uso de tempo real.

Notas de implementação

A correção de um escalonador depende de a lista de prontas (ou listas, sob um esquema multinível) ser manipulada de forma consistente em relação a interrupções: uma interrupção de timer disparando no meio da própria contabilidade do escalonador, em uma implementação escrita ingenuamente, pode corromper a própria estrutura que o escalonador está tentando atualizar, razão pela qual a decisão de escalonamento em si, e qualquer manipulação de lista que ela realize, geralmente roda com interrupções desabilitadas durante sua duração. Também vale a pena distinguir, cedo em um design, entre a decisão de escalonamento (qual tarefa deveria rodar em seguida) e o mecanismo que a executa (a própria troca de contexto): confundir os dois em uma única rotina torna consideravelmente mais difícil depois trocar por uma política de escalonamento diferente sem também reescrever o código de troca com o qual ela acabou emaranhada.

Referências

1. ^ A. Silberschatz, P. Galvin, e G. Gagne, Operating System Concepts, Capítulo 5: o tratamento clássico de livro-texto dos algoritmos de escalonamento descritos acima.
2. ^ C. L. Liu e J. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, 1973: o artigo original de escalonamento rate-monotonic referenciado acima.

Ver também

• Multitasking: o mecanismo mais amplo através do qual as decisões de um escalonador são executadas.
• Context Switching: a mecânica de de fato executar a decisão de um escalonador.
• Inversão de Prioridade: o cenário em que escalonamento por prioridade e um lock compartilhado interagem para travar uma tarefa de alta prioridade.