Qual algoritmo de agendamento é usado no Linux?

Recentemente, em uma entrevista, fui questionado sobre o algoritmo de agendamento usado pelo sistema operacional Linux. Qual é o algoritmo usado por quê?

Além disso, em que algoritmo é usado em sistemas operacionais em tempo real e por quê?

O atual agendador de tarefas do Linux é chamado Completely Fair Scheduler (CFS). Você deve dar uma olhada em http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt para obter mais detalhes. O design é bastante complexo e, a meu ver, não é adequado para RTOS.

Uma técnica comum em sistemas em tempo real é o agendamento de taxa monotônica, porque possui fortes garantias se certas premissas se mantiverem (por exemplo, prioridades estáticas de tarefas e tempo e taxa de execução fixos). Existem muitos outros algoritmos e muita pesquisa. Portanto, trata-se basicamente das propriedades necessárias e do que você sabe sobre sua tarefa e do que é corrigido.

Não tenho certeza se você está pensando sobre o agendamento de E / S do Kernel. Caso não esteja: Ignore esta resposta.

A Wikipedia afirma que o CFG (completamente Fair Queuing) é o padrão desde o Kernel 2.6.18.

No meu openSUSE (executando o Kernel 2.6.37), posso alternar entre CFG, NOOP e Deadline .

O algoritmo Round Robin é geralmente usado em ambientes de compartilhamento de tempo.

O algoritmo usado pelo planejador Linux é um esquema complexo com combinação de prioridade preventiva e divisão de tempo parcial. Atribui quantum de tempo mais longo a tarefas de prioridade mais alta e quantum de tempo mais curto a tarefas de prioridade mais baixa.

Ele identifica cada processo como um processo em tempo real ou um processo normal (outro). As tarefas em tempo real recebem prioridades estáticas atribuídas no intervalo [0,99], onde um número mais baixo indica uma prioridade mais alta.

Todas as outras tarefas têm prioridades dinâmicas no intervalo [100.139], com base na interatividade de uma tarefa que se baseia em seus valores agradáveis, mais ou menos o valor 5. As tarefas que são mais interativas geralmente têm períodos de sono mais longos e, portanto, são mais propensos a tenha ajustes mais próximos de -5, pois o planejador favorece tarefas interativas. (A interatividade de uma tarefa é determinada por quanto tempo ela está inativa enquanto aguarda a E / S.) A interatividade de uma tarefa determina se o valor 5 será adicionado ou subtraído do valor válido. O resultado de tais ajustes será uma prioridade mais alta para essas tarefas. Por outro lado, tarefas com tempos de suspensão mais curtos geralmente são mais vinculadas à CPU e, portanto, terão suas prioridades reduzidas.

O kernel mantém uma lista de todas as tarefas executáveis ​​em uma estrutura de dados da fila de execução. Uma fila de execução contém duas matrizes prioritárias: ativa e expirada. A matriz ativa contém todas as tarefas com tempo restante em suas faixas de tempo e a matriz expirada contém todas as tarefas expiradas. Cada uma dessas matrizes de prioridade contém uma lista de tarefas indexadas de acordo com a prioridade. O agendador escolhe a tarefa com a maior prioridade da matriz ativa para execução na CPU. Quando todas as tarefas esgotam seus intervalos de tempo (ou seja, a matriz ativa está vazia), as duas matrizes prioritárias são trocadas: a matriz expirada se torna a matriz ativa e vice-versa.

A prioridade dinâmica de uma tarefa é recalculada quando a tarefa esgotar seu quantum de tempo e deve ser movida para a matriz expirada. Assim, quando as duas matrizes são trocadas, todas as tarefas na nova matriz ativa recebem novas prioridades e intervalos de tempo correspondentes. (Nota: Este é um trecho do livro sobre conceitos de sistema operacional (9ª edição) de Abraham Silberschatz, et al. Para obter detalhes, consulte a seção 5.6.3 deste livro.

Esta é uma resposta para sua outra pergunta. Os sistemas de tempo real (RTS) são de dois tipos, rígido e flexível. O algoritmo de agendamento da CPU para o RTS rígido é um algoritmo preemptivo baseado em prioridade e o do RTS flexível é uma prioridade não preemptiva.