Escalonamento de processos

Escalonamento no Linux e no Windows NT/2000/XP

1

Escalonamento no Linux
Os requisitos do escalonador do Linux eram:
Apresentar boa performance em programas interativos, mesmo com carga elevada;
Distribuir de maneira justa o tempo da CPU;
Ser eficiente em máquinas SMP (Symmetric Multi
Processor);
Possuir suporte para tempo real.

2

Escalonamento no Linux
Cada processo possui uma prioridade, que é recalculada dinamicamente.
O escalonador entrega a CPU para o processo que possui a maior prioridade.
O escalonador é preemptivo.

3

Escalonamento no Linux
O Linux considera dois tipos de processos: processos interativos (time-sharing) processos tempo real

Para processos interativos (dentro da mesma prioridade) o algoritmo é Round Robin.
Para processos de tempo real (dentro da mesma prioridade) o algoritmo pode ser:
FCFS (o processo executa até terminar ou se bloquear) ou
Round Robin

Processos de tempo real possuem prioridade sobre os demais processos.

4

Escalonamento no Linux
Nas versões que antecederam a 2.6, o escalonador apresentava 2 problemas:
1) o tempo de execução do escalonador aumentava com o aumento do número de processos no sistema;
2) O escalonador usava uma ready list global em máquinas
SMP

5

Escalonamento no Linux
Primeiro problema (overhead):
Cada processo possui uma prioridade, baseada em uma prioridade básica
(Nice) e em seu comportamento em tempo de execução.
Uma vez selecionado, o processo ganha a CPU por uma fatia de tempo.
Quando o time-slice esgota, o processo é marcado como expirado.
O escalonador seleciona o processo não expirado com a maior prioridade.
Quando todos os processos estão expirados, o escalonador recalcula a prioridade de todos e então seleciona o próximo a rodar.
O problema era este recálculo de prioridades: aumentando o número de processos no sistema, aumenta o tempo necessário para o escalonador recalcular as prioridades. (Para aplicações com um número