AA CCT00341

Prévia do material em texto

1
SISTEMAS OPERACIONAIS
Escalonamento de CPU
Prof. Mateus Novaes
(Adaptação dos slides de Silberschatz)
SUMÁRIO
 Conceitos básicos
 Critérios de escalonamento
 Algoritmos de escalonamento
 FCFS
 SJF
 Prioridade
 Round-Robin ou Circular
 Múltiplas filas
 Múltiplas filas com retroalimentação
 Aleatório
2
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU
CONCEITOS BÁSICOS
 Máxima utilização de CPU obtida com 
multiprogramação.
 Processo é executado até ser colocado em espera
 Por causa de E/S ou ter excedido o tempo de execução
 Ciclos de surto de CPU e E/S
 A execução de um processo consiste de um surto de 
CPU e de um surto de E/S
 Um processo limitado pela E/S tem muitos surtos de 
CPU curtos
3
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
4
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
5
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
 O escalonador de processos
 Escolhe um processo para execução, dentre os 
processos na fila de prontos
 Processo de seleção executado pelo escalonador de 
curto prazo
 A fila de processo prontos nem sempre é FIFO
 Fila de prioridades, arvore
 Os elementos das filas são geralmente os PCBs dos 
processos
6
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
 Situações para a escolha de um processo
1. Processo passa de executando para em espera
2. Processo passa de executando para pronto
3. Processo passa de espera para pronto
4. Processo é terminado
 Escalonamento ocorrendo nos casos 1 e 4 é 
chamado não preemptivo
 Em qualquer outro caso é chamado preemptivo
7
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
 Escalonamento preemptivo tem mais custo
 Coordenar acesso aos dados compartilhados
 Preempção tem efeito no projeto do kernel
 Chamadas ao sistema podem deixar o kernel
inconsistente se interrompidas
 Alguns S.O.s resolvem este problema evitando 
interrupção de uma chamada ao sistema
8
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS
 Dispatcher (executor)
 Substitui o processo corrente na CPU pelo processo 
escolhido pelo escalonador de curto prazo
 Passos:
 Troca de contexto
 Passar a CPU para o modo de usuário
 Pular para a posição adequada no programa do usuário
 Latencia de dispatch: Tempo necessário para o dispatch
interromper um processo e colocar outro para execução
9
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CRITÉRIOS DE ESCALONAMENTO
 Critérios utilizados para comparar algoritmos:
 Tempo de processador – o tempo que o processo 
passa executando na CPU
 Vazão – número de processos que são completados 
por unidade de tempo 
 Tempo de retorno – o tempo necessário para executar 
um determinado processo.
 Este tempo deve incluir os tempos de espera, acesso à 
memória e dispositivos de I/O;
 Tempo de espera – tempo que um processo gasta 
esperando na fila de prontos
10
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
CRITÉRIOS DE ESCALONAMENTO
 Critérios utilizados para comparar algoritmos:
 Tempo de resposta – tempo percorrido desde que uma 
requisição é submetida até a primeira resposta 
produzida, não até a saída (para ambiente de tempo 
compartilhado)
 Critérios ótimos:
 Máxima utilização de CPU
 Máxima vazão
 Mínimo tempo de retorno
 Mínimo tempo de espera
 Mínimo tempo de resposta 11
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento first-come, first-served
 Escalonamento mais simples de implementar
 Utiliza fila FIFO
 Longo tempo de espera médio
Process Burst Time
P1 24
P2 3
P3 3
 Tempo de espera para o processo P1 é 0, P2 é 24 e P3
é 27
 Tempo médio de espera (0+24+27)/3 = 17 
milissegundos
12
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento first-come, first-served
 Se invertêssemos a ordem dos processos teríamos um 
tempo médio menor
Processo Surto de CPU
P1 24
P2 3
P3 3
 Se a ordem fosse: P2, P3 e P1
 Tempo médio de espera seria (0+3+6)/3 = 3 
milissegundos
 O algoritmo FCFS é não preemptivo
 Ruim em sistema de tempo compartilhado
13
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento job mais curto primeiro (SJF)
 Associa a cada processo o tempo do seu próximo surto 
de CPU
 O próximo processo a ser escolhido é o que possuir o 
menor tempo de surto de CPU
 Caso haja empate utiliza-se FCFS
 Algoritmo pode ser utilizado nos esquemas não-
preemptivo e preemptivo
 Preemptivo – Um novo processo com surto de CPU menor do 
que o tempo restante do processo atual, faz com que o 
processo atual seja retirado. 
 Esse esquema é conhecido como “Shortest Remaining
Time First” (SRTF)
14
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento job mais curto primeiro (SJF)
 Exemplo de um esquema não preemptivo:
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 Tempo de espera médio: (0 + 6 + 3+ 7)/4 = 4
15
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
P1 P3 P2
73 160
P4
8 12
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento job mais curto primeiro (SJF)
 Exemplo de um esquema preemptivo:
Processo Tempo de chegada Surto de CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 T. de esp. médio: (9 + 1 + 0 + 2)/4 = 3
16
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
P1 P3P2
42 110
P4
5 7
P2 P1
16
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Determinando o tempo do próximo surto de CPU
 n+1=  tn+ (1- ) n
n+1: Duração prevista para o próximo surto 
de CPU
tn: Duração real do último surto de CPU
n: Última previsão de duração de surto de 
CPU
: Varia de 0 a 1 e pode potencializar cada 
um dos termos da fórmula.
17
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Determinando o tempo do próximo surto de CPU
18
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento por prioridade
 Cada processo recebe do sistema operacional um 
número inteiro que representa sua prioridade
 A CPU é alocada ao processo com maior prioridade na 
fila de processos prontos
 O escalonamento SJF é um caso particular de 
escalonamento por prioridade
 A prioridade é o menor surto de CPU
19
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento por prioridade
 Um problema desta solução é o starvation
 Processos com baixa prioridade podem nunca chegar a 
executar
 IBM 7094 do MIT possuía um processo com 6 anos na fila 
de execução
 Uma solução para este problema de starvation seria aumentar 
a prioridade do processo a medida que o tempo passa
20
S
is
te
ma
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
Processo Prioridade Surto
P1 3 10
P2 1 1
P3 4 2
P4 5 1
P5 2 5
21
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
P2 P5
1 160
P4
6
P1 P3
1918
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento Round-Robin ou Circular
 Cada processo recebe uma fatia de tempo igual para 
executar
 Essa unidade de tempo pode variar e se chama quantum
 O quantum varia entre 10-100 milisegundos
 Implementado com uma fila FIFO
 O processo retirado da CPU vai para o final da fila
 Um quantum longo faz o algoritmo funcionar como o 
FCFS
 Um quantum pequeno gera muito overhead devido a 
troca de contexto
22
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
Processo Surto de CPU
P1 24
P2 3
P3 3
 Tempo de espera médio maior do que o SJF, mas o 
tempo de resposta é melhor
23
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
24
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
25
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento por múltiplas filas
 Fila de prontos é dividida em filas distintas:
 Primeiro plano (interativa)
 Segundo plano (batch)
 Outras...
 Cada fila possui seu próprio algoritmo de 
escalonamento
 Primeiro plano – RR
 Segundo plano – FCFS
26
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Deve haver um escalonamento entre as filas
 Prioridade fixa: As filas de maior prioridade devem 
esvaziar para serem escolhidos processos de outras 
filas
 Starvation
 Divisão de tempo: Cada fila tem uma porção de tempo 
da CPU 
 Primeiro plano – 80%
 Segundo plano – 20%
27
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
28
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento por múltiplas filas com 
retroalimentação
 Um processo pode se mover entre as filas de 
processos
 Normalmente implementado com 3 filas
 Q0 – Quantum de 8 millisegundos
 Q1 – Quantum de 16 millisegundos
 Q2 – FCFS
29
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
30
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Escalonamento por múltiplas filas com 
retroalimentação
 Escalonamento:
 Um processo novo entra na fila Q0 e recebe 8 milisegundos de 
tempo de CPU
 Se não terminar a execução passa para a fila Q1
 O processo na fila Q1 recebe 16 milisegundos
 Se não terminar a execução passa para a fila Q2
 Na fila Q2 os processos obedecem FCFS
 Os processos da fila Qn não são servidos enquanto a fila Qn-1 
não está vazia
31
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO
 Aleatório ou loteria
 Tokens numerados são distribuídos entre os processos 
e no escalonamento é sorteado um numero aleatório. O 
processo que tiver o número ganha a CPU.
 Escalonamento garantido
 Este algoritmo busca cumprir promessas de alocação 
de CPU o mais preciso possível.
32
S
is
te
m
a
s
 O
p
e
ra
c
io
n
a
is