Algoritmos de Escalonamento

No código do linux (arquivos include/linux/sched.h e kernel/sched.c) é possível encontrar quatro classes de escalonamento disponíveis: SCHED NORMAL, SCHED FIFO, SCHED RR e SCHED BATCH, é a partir delas que o escalonador escolhe um processo para ser executado.

SCHED NORMAL

Podemos considerar este tipo de escalonamento como convencional já que a ênfase é no timesharing (compartilhamento do tempo).

A fatia de tempo (ou fatia quantum) é um valor numérico que indica quanto tempo uma

determinada tarefa pode ser executada antes de ser antecipada (antes de ceder o processador a outro processo). O escalonador do Linux calcula a fatia de tempo necessária a uma tarefa a partir do seu comportamento, por exemplo, processos de E/S necessitam de um tempo menor do que processos vinculados ao processador. Para resolver esse conflito, o Linux mantém valores de fatia de tempo e prioridade relativamente altas para os processos vinculados à E/S (100 ms), em contra-partida, os processos não precisam utilizar toda a sua fatia de tempo de uma só vez (podem utiliza-la em intervalos) quando ela acaba o processo é considerado expirado e para ser escalonado novamente esperar que todos os outros tenham também a sua fatia esgotada.

Quando um processo expira é necessário que ele tenha a sua fatia de tempo recalculada (já que agora ela corresponde a zero), para facilitar o cálculo (que até então era feito utilizando um complexo loop) as novas versões do Linux (a partir da série 2.5) se utilizam de dois arrays de prioridade (um para processos ativos e outro para processos expirados). Esse recurso é útil porque reduz a complexidade do cálculo e o tempo perdido com o mesmo.

O escalonador deve conhecer o comportamento de uma dada tarefa para determinar a sua prioridade e a sua fatia de tempo, ele obtém essa informação observando quanto tempo esse processo passa dormindo e quanto tempo fica em estado executável (esse valor é armazenado na variável sleep avg na task struct) e assim calcula a sua fatia de tempo concedendo bônus ou penalizando-o dependendo de como utilizou o seu tempo. O Linux trabalha também com uma regra para evitar que processos obtenham uma fatia de tempo ilimitada.

Cálculo da fatia de tempo do processo

SCHED FIFO

A estratégia FIFO (First In, First Out) implementada no kernel do Linux consiste no conceito: primeiro processo de tempo-real a entrar é o primeiro a sair. Os processos FIFO de tempo real não podem ser antecipados por outro processo que não seja FIFO de tempo real, esses processos também não trabalham com fatias de tempo, ou seja, eles podem dispor do processador praticamente o tempo que necessitarem.

SCHED RR

A política SCHED RR (Round Robin _ alternância circular) funciona do mesmo modo que a FIFO, entretanto com ela os processos de tempo real podem ser interrompidos pelo relógio, ou melhor, eles executam durante uma determinada fatia do tempo do processador, assim que o tempo acaba eles são postos no final da fila de execução. Esta estratégia garante uma atribuição justa do tempo de processador para todos os processos Round Robin.

SCHED BATCH

Esta política está presente no código-fonte do Linux apenas a partir do kernel 2.6.16, e é uma política similar a utilizada em SCHED NORMAL, com exceção de que ela sempre tende a fazer o escalonador supor que o processo é vinculado ao rocessador, por esse motivo ele sofrerá penalidades que o desfavorecem nas decisões de escalonamento. Esta é uma estratégia útil para tarefas que não são interativas mas não desejam reduzir o seu valor bom.