3 - Escalonamento de processos

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 
 Múltiplas filas 
 Múltiplas filas com retroalimentação 
 
2 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
c
io
n
a
is
 
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS 
4 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
ESCALONAMENTO DE CPU 
CONCEITOS BÁSICOS 
5 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
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
r
a
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
r
a
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
r
a
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 
 
 Tempo de espera – tempo que um processo gasta 
esperando na fila de prontos 
10 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
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
r
a
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
r
a
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
r
a
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
r
a
c
io
n
a
is
 
P1 P3 P2 
7 3 16 0 
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
r
a
c
io
n
a
is
 
P1 P3 P2 
4 2 11 0 
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
r
a
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
r
a
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
sO
p
e
r
a
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
m
a
s
 O
p
e
r
a
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
r
a
c
io
n
a
is
 
P2 P5 
1 16 0 
P4 
6 
P1 P3 
19 18 
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO 
 Escalonamento Round-Robin 
 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
r
a
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
r
a
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
r
a
c
io
n
a
is
 
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO 
25 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
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
r
a
c
io
n
a
is
 
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO 
28 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
c
io
n
a
is
 
ESCALONAMENTO DE CPU 
ALGORITMOS DE ESCALONAMENTO 
30 
S
is
te
m
a
s
 O
p
e
r
a
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
r
a
c
io
n
a
is