Sistemas Operacionais:
Escalonamento de
processos
Escalonamento
•
•
•
•
Critérios de escalonamento
Algoritmos de escalonamento
Escalonamento em multiprocessadores
Escalonamento tempo real
Características de processos
• Multiprogramação possibilita a máxima
utilização da CPU
• Processo:utilização da CPU e E/S
• Distribuição da utilização da CPU
Algoritmo de escalonamento
• Seleciona entre os processos prontos e na memória,
qual irá ganhar a CPU
• O escalonamento pode ocorrer:
1. Um processo passa do estado executando para o estado espera (p.
exemplo, o processo solicita uma operação de E/S)
2. Um processo passa do estado executando para o estado pronto
3. Um processo passo do estado espera para pronto
4. Um processo é finalizado
• Escalonamento nas alternativas 1 e 4 é denominado
não-preemptivo (nonpreemptive)
• As outras opções são denominadas preemptivo
(preemptive)
Critérios para o escalonamento
• Utilização da CPU – utilizar o máximo da CPU
• Throughput – número de processos finalizados em
um dado intervalo de tempo
• Tempo de execução – tempo para finalizar a
execução de um determinado processo no sistema
• Tempo de espera – quantidade de tempo que o
processo ficou na fila de prontos
• Tempo de resposta – tempo entre a requisição e a
saída do primeiro resultado (sistemas interativos)
Otimizações
•
•
•
•
•
Utilização máxima da CPU
Throughput máximo
Tempo de execução mínimo
Tempo de espera mínimo
Tempo de resposta mínimo
FCFS (First-come, first-served)
• Primeiro a chegar, primeiro a ser servido (sistemas
não preeemptivos)
Process
P1
P2
P3
Burst Time
24
3
3
• A ordem de chegada dos processos é P1, P2, P3. O gráfico de
Gantt para esse algoritmo é:
P1
0
P2
24
P3
27
• Tempo de espera P1 = 0; P2 = 24; P3 = 27
• Tempo médio de espera: (0 + 24 + 27)/3 = 17
30
FCFS(2)
• Considerando a ordem de chegada P2, P3, P1
• O gráfico de Gantt
P2
0
•
•
•
•
P3
3
P1
6
30
Tempo de espera P1 = 6; P2 = 0; P3 = 3
Tempo médio de espera: (6 + 0 + 3)/3 = 3
Melhor desempenho que o caso anterior
“Efeito comboio”: todos os processos menores ficam
esperando pelo processo maior utilizar a CPU
SJF (Shortest Job First)
• Menor tarefa primeiro
• Cada processo é associado com o tempo de utilização
da CPU (normalmente derivado das execuções
anteriores)
• Dois esquemas:
– Não preeemptivo– quando um processo ganha a CPU ele é
executado até o fim do período de utilização da CPU
– Preemptivo– se um processo chega com o tempo de
duração da CPU menor que o tempo restante que do
processo em execução, o escalomanento é realizado.
Shortest-Remaining-Time-First (SRTF)
• SJF– fornece o menor tempo médio de espera para
um dado conjunto de processos (solução ótima)
SJF não preemptivo
Process
P1
P2
P3
P4
Arrival Time
0.0
2.0
4.0
5.0
P1
0
3
Burst Time
7
4
1
4
P3
7
P2
8
P4
12
16
• Tempo médio de espera = (0 + 6 + 3 + 7)/4 = 4
SJF preemptivo
Process
P1
P2
P3
P4
P1
0
Arrival Time
0.0
2.0
4.0
5.0
P2
2
P3
4
P2
5
Burst Time
7
4
1
4
P4
7
P1
11
16
• Tempo médio de espera= (9 + 1 + 0 +2)/4 = 3
Determinando o tempo de uso da
CPU de um processo
• Estimativas
• Normalmente baseadas nos ciclos de execução
anteriores, utilizando a média exponencial
1. t n  actual length of n th CPU burst
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :
 n1   tn  1    n .
• = controla o peso da última execução sobre as
execuções passadas
Predição do tempo de execução
Utilizando a média exponencial
•  =0
– n+1 = n
– A história recente não é considerada
•  =1
– n+1 =  tn
– Somente a última execução é considerada
• Expandindo a formula:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0
• Desde que  E (1 - ) são menores que 1, cada item
um peso menor que o seu predecessor
Escalonamento por prioridades
• Cada processo tem uma prioridade associada (valor inteiro)
• Ganha a CPU o processo com maior prioridade (normalmente,
menor valor = maior prioridade)
– Preemptivo
– Não preemptivo
• SJF é um algoritmo baseado em prioridades, onde a prioridade
do processo é a estimativa do tempo de uso da CPU
• Problema  Starvation (abandono de processos)–processos de
baixa prioridade podem não ganhar a CPU
• Solução Aging (envelhecimento)– durante a execução do
sistema, processos vão ganhando maior prioridade
Round Robin (RR)
• Alocação circular
• Cada processo ganha um pequeno tempo de
CPU (na ordem de milissegundos)
denominado quantum
• Cada processo ganha uma quantidade q de
utilização da CPU
– q grande: FCFS (todos os processos executam até
o FIM)
– q pequeno: haverá desperdício devido ao tempo
necessário para a troca de contexto
Simulação do escalonamento RR
Process
P1
P2
P3
P4
Burst Time
53
17
68
24
• Gráfico de Gantt:
P1
0
P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
• Normalmente, o throughput é menor, porém com um
melhor tempo de resposta
Exercício
• Calcular o tempo médio de processamento
para os seguintes processos utilizando a
política de alocação circular (RR), para q =1,
2, 3, 4, 5, 6
Processo
Tempo
P1
6
P2
3
P3
1
P4
7
Escalonamento com múltiplas filas
• A fila de prontos é separada em várias filas:
– fila para processos interativos
– fila para processos em lote
• Cada fila tem sua política de escalonamento
– RR para processos interativos
– FCFS para processos em lote
• Deve haver um escalonamento entre as filas
– Prioridade: primeiro a fila de processos interativos
(possibilidade de abandono de processos (starvation)
– Fatia de tempo para cada fila
Múltiplas filas e transferência entre
filas
• Processos podem ser transferidos de fila
• Envelhecimento (aging): processo vai ganhando
prioridade com o tempo
• Escalonador com múltiplas filas pode ser definido
através dos seguintes parâmetros:
–
–
–
–
–
Número de filas
Algoritmos de escalonamento para cada fila
Método utilizado para aumentar a prioridade do processo
Método utilizado para diminuir a prioridade do processo
Método utilizado para determinar qual fila o processo ficará
quanto o mesmo solicita um serviço
Escalonamento com múltiplas filas
Escalonamento em
multiprocesadores
• Escolher qual processo pronto vai executar em
qual CPU
• Simétrico
– Todas as estruturas de dados são acessadas por
todos os processadores
• Assimétrico
– Somente um processador tem acesso a estrutura de
dados do núcleo
Escalonamento no Linux (até 2.6)
• Dois algoritmos: tempo compartilhado e tempo real
• Tempo compartilhado
– Baseado em prioridades(“créditos”) – o processo com mais
crédito é escalonado
– O crédito é subtraído quando um interrupção ocorre
– Quando crédito= 0, outro processo é escolhido
– Quando todos os processos tem crédito= 0, um novo
cálculo dos créditos é realizado
• Baseado em fatores como prioridade e histórico
• Tempo real
– Soft real-time
– Duas classes de algoritmos
• FCFS e RR
• O processo de mais alta prioridade sempre executa
Escalonamento no Linux (a partir
2.6)
• CFS: Completely Fair Scheduler
– Modela uma CPU ideal (todos os processos
ganham a quantidade de tempo que precisam para
executar)
– Wait_runtime: tempo em que o processo esperou
para ganhar a CPU. Idealmente 0
– Os processos são organizados em uma árvore
rubro-negra
• Ordenados pela tempo que elas devem ganhar a CPU
• Resolução em nanosegundos