aula07 Escalonamento processos

Prévia do material em texto

Sistemas 
Operacionais
Aula 07
Escalonamento de processos
Prof. Alberlan Lopes
 
Conceito de Escalonamento
 Para cada estado, existe uma fila que contém os PCB's 
 nas transições entre estados, o PCB do processo é 
movido entre as filas apropriadas
executando
bloqueados
pcb3
prontos pcb1 pcb5 pcb2
pcb4 pcb6
pcb8 pcb7 pcb10
e/s disco
e/s terminal
e/s impressão
pcb9
 
Razões para Suspender Processos
 
 Do SO
 Swapping: para liberar espaço na memória principal 
para trazer outro processo da memória secundária
 SO pode suspender um processo
 em background
 utilitário
 suspeito de estar causando problemas
 Solicitação de usuário interativo 
 Temporização: determinados processos são executados 
periodicamente 
 Solicitação do processo pai
 
Conceito de Escalonamento
 Escalonamento consiste em determinar, dentre 
os processos prontos, qual o próximo processo a 
ser executado
 Realizado por um componente do sistema 
operacional denominado escalonador
 Dois tipos de escalonadores 
 longo prazo 
 curto prazo
 
Conceito de Escalonamento
 Escalonador longo prazo 
memória secundária  memória principal
 Escalonador curto prazo 
 memória principal  processador
 Principais objetivos
 maximizar a utilização do processador
 maximizar o número de processos completados 
por unidade de tempo
 garantir que todos os processos recebam o 
processador
 minimizar o tempo de resposta para o usuário
 
Conceito de Escalonamento
 Uma visão dos escalonadores do sistema operacional
Longo-Prazo
Fila de Prontos
Fila
EsperaI/O
CPU
Curto-Prazo
FIM
 
Conceito de Escalonamento
 Dispatcher: responsável por passar o controle da CPU 
para o processo selecionado pelo escalonador de curto 
prazo, envolve:
 mudança de contexto
 mudança para o modo usuário
 salto para a posição adequada dentro do processo 
selecionado para reiniciar sua execução
 Latência de despacho  Tempo gasto pelo
dispatcher para interromper um processo e começar a 
execução de um outro
 
Representação do Escalonamento
término de fatia
de tempo
término de fatia
de tempo
requisição de
I/O
requisição de
I/O
em espera por
uma interrupção
em espera por
uma interrupção
criação de um
processo filho
criação de um
processo filho
interrupção
ocorre
interrupção
ocorre
filho em
 execução
filho em
 execução
fila de dispositivoI/OI/O
fila de processos prontos CPUCPU
 
Adição de Escalonador Intermediário
fila de espera por
I/OI/O
fila de processos
 prontos CPU
terminar
processos em execução
parcialmente removidos
 da memória
carregar remover
 
Conceito de Escalonamento
 Mudança de contexto
 CPU é chaveada para outro processo  SO 
deve salvar o estado do processo antigo e 
carregar o estado do novo processo
 Implica overhead  SO não realiza nenhum 
trabalho útil durante os chaveamentos 
 Tempo consumido é dependente do suporte de 
hardware fornecido
 
Chaveamento da CPU
interrupção ou chamada ao sistema
Processo P
0
exec.
exec.
ocioso
Processo P
1
ocioso
executando
ocioso
recarregar estado no PCB0
armazenar estado no PCB1
armazenar estado no PCB0
recarregar estado no PCB1
.
.
.
.
.
.
interrupção ou chamada ao sistema
SO
 
Características dos Escalonadores
 Escalonador da CPU é invocado muito 
freqüentemente (milissegundos) 
  precisa ser rápido
 Escalonador de processos é invocado com muito 
pouca freqüência (segundos, minutos)
  pode ser lento
 O escalonador de processos controla o grau de 
multiprogramação do sistema
 
Conceito de Escalonamento
 Os escalonadores são implementados por 
algoritmos dentro do sistema operacional
 Critérios para comparar a eficiência dos algoritmos 
 utilização da CPU (1)
 taxa de saída (throughput) (2)
 turnaround time (3)
 tempo de espera (4)
 tempo de resposta (5)
 Objetivos maximizar (1) e (2)
 minimizar (3), (4) e (5) 
 
Conceito de Escalonamento
 Tipo de processamento
 batch
 interativo
 CPU bound
 I/O bound
 Tipo de sistema
 monoprogramado (?)
 multiprogramado
 time-sharing
 tempo-real
 multiprocessado
 Tipo de processamento
 batch
 interativo
 CPU bound
 I/O bound
 Tipo de sistema
 monoprogramado (?)
 multiprogramado
 time-sharing
 tempo-real
 multiprocessado
política de escalonamento
(scheduling policies)
política de escalonamento
(scheduling policies)
 Considerações
 
Critérios de Escalonamento
Orientados ao Usuário e Desempenho
Uso do processador  mede a porcentagem de 
tempo em que a CPU está ocupada
 importante em tempo compartilhado
 não muito importante em sistemas monousuário e 
tempo-real
Tempo de resposta
processos interativos
tempo entre uma requisição e o início da resposta 
do ponto de vista do usuário
qual seria o tempo de resposta ideal ?
 
Critérios de Escalonamento
Orientados ao Usuário e Desempenho
Deadlines (prazos)  quando o prazo de término 
pode ser especificado
 o sistema deveria fazer o melhor esforço para 
atender todos os prazos
Previsibilidade  um dado processo deveria 
executar sempre em um tempo médio previsível
 a carga do sistema não deveria impor 
variações
 
Critérios de Escalonamento
Orientados ao Sistema e Desempenho 
Throughput (vazão)  número de processos 
completados por unidade de tempo, depende:
 do tamanho dos processos
 das políticas de escalonamento
Turnaround  intervalo de tempo entre a submissão 
de um processo e o seu término
 inclui o tempo de execução, espera por recursos
 medida para sistemas batch
Waiting time  quantidade total de tempo que um 
processo esteve esperando na fila de prontos
 
Critérios de Escalonamento
 Orientados ao Sistema
 Justiça  processos devem ser tratados igualmente, 
a menos que especificado o contrário
processos não deveriam sofrer starvation
 Prioridades  processos mais prioritários devem 
efetivamente ser favorecidos
problema da inversão de prioridade
 Balanceamento de recursos  recursos devem ficar 
ocupados o máximo possível
processos que não vão utilizar recursos 
sobrecarregados devem ser favorecidos
 
Escalonamento de Processos
 Longa duração  decisão de se adicionar um 
processo ao pool de processos para serem 
executados
admissão ao sistema
 Duração média  decisão de se adicionar ao 
número de processos que está completamente ou 
parcialmente na memória
swapping, memória virtual
 
Escalonamento de Processos
 Curta duração  decisão de qual processo 
disponível será executado
interrupção de clock e I/O, chamadas ao 
sistema, signals
 I/O  decisão de qual processo que está na fila 
de espera por uma requisição de I/O será 
tratado
 
Escalonamento de Processos
 Tipos
 não-preemptivo: processo executando não pode 
ser interrompido
 preemptivo: processo pode ser retirado do 
processador
 Políticas mais comuns:
 First-Come-First-Served (FCFS)
 Shortest Job First (SJF)
 Prioridade
 Múltiplas Filas
 Round-Robin
 
First-Come-First-Served (FIFO)
 Não preemptivo por definição
 Primeiro processo da fila é o primeiro a ser 
executado
 Processos usam a CPU até terminar todo 
 processamento
 Mesmo com alguma intercalação, processos 
com menor prioridade podem prejudicar 
processos com maior prioridade
 inversão de prioridade
 starvation
 
First-Come-First-Served
p1 p2 p3 p4
t = 6 t = 8 t = 7 t = 3
p1 p2 p3 p4
0 6 14 2421 t
 
First-Come-First-Served
Exemplo: ProcessoTempo de execução
P1 24
 P2 3
 P3 3 
Suponha que os processos chegaram na seguinte 
ordem: P1 , P2 , P3 
1. Qual seria o diagrama de Gannt, o waiting time para cada um 
dos processos e o waiting time médio?
 
First-Come-First-Served
Diagrama de Gantt para o escalonamento:
Waiting time para P1 = 0; P2 = 24; P3 = 27
Waiting time médio: (0 + 24 + 27)/3 = 17
P1
24 27 300
P2 P3
 
Shortest-Job-First
 Pode ser preemptiva ou não-preemptiva
 Cada processo é associado ao seu tempo de uso do 
processador
 Escalonado o processo com o menor tempo de CPU
 privilegiam processos menores
 reduzem o tempo médio de espera na fila de 
prontos
 Problema: 
 Como determinar quanto tempo de CPU será 
necessário?
 
Shortest-Job-First
 Tanto o escalonamento FIFO quanto o SJF não são 
utilizados em sistemas de time-sharing (por quê ?)
p1 p2 p3 p4
t = 6 t = 8 t = 7 t = 3
p4 p1 p3 p2
3 9 16 240 t
 
Shortest-Job-First
A política SJF é ótima, minimizando o tempo 
médio de espera de um conjunto de processos
 Dificuldade: determinar antecipadamente o 
tempo de processador de cada processo
 Na prática, o tempo é estimado, é utilizada 
uma aproximação
 
Shortest-Job-First: não preemptivo
Processo Tempo de chegada Duração da rajada
 P1 0.0 7
 P2 2.0 1
 P3 4.0 4
 P4 5.0 4
 SJF (não preemptivo)
waiting time médio = (0 + 5 + 4 + 7)/4 = 4
73 160 8 12
P1 P2 P3 P4
 
Shortest-Job-First: preemptivo
 Processo Tempo de chegada Duração da rajada
 P1 0.0 7
 SJF (preemptivo)
 waiting time médio = (9 + 1 + 0 +2)/4 = 3
P2 2.0 4
P3 4.0 1 terminado
P4 5.0 4
terminado
0
P1
2
P2
5
P3
4 7
P2
11
P4
terminado
16
P1
terminado
 
Shortest-Job-First: preemptivo
?
 Processo Tempo de chegada Duração da 
rajada
 P1 0.0 7
0
P1
 SJF (preemptivo)
 waiting time médio = (9 + 1 + 0 +2)/4 = 3
2
P2
P2 2.0 4
tempo restante: 5
? 5
P3 4.0 1
P3
4
tempo restante: 2
terminado
P4 5.0 4
7
P2
terminado
11
P4
terminado
16
P1
terminado
 
Shortest-Job-First
Determinação do tempo de CPU, pode:
somente estimar a próxima duração 
ser feita usando a duração de tempo de CPU 
anteriores, usando-se média exponencial 
 
Shortest-Job-First
  =0
n+1 = n  História recente não conta
  =1
n+1 = tn  Somente o último tempo de CPU (rajada) é 
condiserado
 Se expandirmos a fórmula teremos
 n+1 =  tn+(1 - )  tn-1 + …
 +(1 -  ) j  tn-1 + …
 +(1 -  )n+1 tn 0
 Uma vez que tanto  como (1 - ) são menores ou iguais a 1, 
cada termo tem peso menor do que o seu predecessor
 
Shortest-Job-First Preemptivo
 Permite que se dê atenção mais rapidamente a processos 
mais prioritários
 Melhores respostas em sistemas time-sharing
 Compartilhamento do processador tende a ser mais 
uniforme
 Troca de processos na CPU gera overhead 
 Estabelecer de forma otimizada os critérios para a 
preempção
 Procurar utilizar processos leves quando possível
 
Prioridade
 A cada processo é atribuída uma prioridade
 O processo com maior prioridade é atribuído ao 
processador
 Pode ser não-preemptiva ou preemptiva
 não-preemptiva: o processo libera 
espontaneamente o processador
 preemptiva : o processo executando é 
interrompido caso chegue à fila de prontos um 
processo com maior prioridade 
 
Prioridade
 Atribuição de prioridades 
 estática: o processo tem uma prioridade 
fixa durante o seu tempo de vida
 dinâmica: prioridade muda ao longo do 
tempo de vida do processo, de acordo com 
o seu comportamento 
 
Prioridade
 Atribuição de prioridades
 normalmente é feita pelo SO
 pode ser configurada pelo superusuário
 processos de usuário recebem uma prioridade 
máxima de usuário
 usuário pode diminuir a prioridade de seus 
processos
 ex.: comando renice do Unix
 Dinâmica
 pode ser ajustada de acordo com
 tipo de processamento realizado
 a carga do SO
 quando o processo passa do estado de 
espera para o estado executando ele é 
penalizado e sua prioridade é reduzida, 
processos
  CPU bound terão suas prioridades 
reduzidas a cada passagem para o estado 
executando
  I/O bound ficam em estado de espera 
com freqüência, processos CPU bound não 
serão prejudicados
 Dinâmica
 pode ser ajustada de acordo com
 tipo de processamento realizado
 a carga do SO
 quando o processo passa do estado de 
espera para o estado executando ele é 
penalizado e sua prioridade é reduzida, 
processos
  CPU bound terão suas prioridades 
reduzidas a cada passagem para o estado 
executando
  I/O bound ficam em estado de espera 
com freqüência, processos CPU bound não 
serão prejudicados
 Estática
 é atribuída quando o processo é 
iniciado
 não é alterada durante a existência do 
processo
 pode oferecer tempos de resposta 
aceitáveis
 Estática
 é atribuída quando o processo é 
iniciado
 não é alterada durante a existência do 
processo
 pode oferecer tempos de resposta 
aceitáveis
 Observação
 SO pode associar à alta prioridade um 
número escalar pequeno 
  0 significa a maior prioridade
 Observação
 SO pode associar à alta prioridade um 
número escalar pequeno 
  0 significa a maior prioridade
 
Prioridade
Processo A
Processo B
tempo4 8 10 13 16 18 23 26 27
 1u.t.
4 u.t.
B solicita 
I/O preempçãopor B
4 u.t.
B solicita 
I/O
2 u.t.
A solicita 
I/O
3 u.t.
2 u.t.
B solicita 
I/O
5 u.t.
preempção
por B
3 u.t.
B solicita 
I/O
 Tempo de CPU (u.t.) Característica do Processo Prioridade
Processo A 13 CPU bound 1 
menor
Processo B 11 I/O bound 0 
maior 
 
Prioridade
 Vantagens
 é possível fazer diferenciação entre processos
 adaptabilidade (prioridades dinâmicas)
 Desvantagem
 starvation: um processo com baixa prioridade 
pode nunca ser atribuído ao processador
 solução: aumentando, em intervalos regulares, a 
prioridade dos processos que estão há muito tempo 
esperando 
 
Round-Robin
 Escalonamento do tipo preemptivo
 Cada processo executa durante uma fatia de 
tempo (time-slice ou quantum)
 Ao final da fatia de tempo, o processo 
executando é inserido no final da fila de 
prontos
 Processo na frente da fila de prontos recebe o 
processador
 
Round-Robin
bcp1 bcp2 bcp3 bcp4
processo 1 executando
fatia de tempo
esgotada
bcp2 bcp3 bcp4 bcp1
processo 2 executando
 
Round-Robin
 Bom para tempo compartilhado
 Similar a FIFO + tempo limite para 
execução (time-slice ou quantum)
 terminado o quantum, o processo é 
devolvido(preempção) para o final da 
fila de prontos
 processos não monopolizam a CPU
 quantum entre 100 a 300 ms
 Bom para tempo compartilhado
 Similar a FIFO + tempo limite para 
execução (time-slice ou quantum)
 terminado o quantum, o processo é 
devolvido (preempção) para o final da 
fila de prontos
 processos não monopolizam a CPU
 quantum entre 100 a 300 ms
 
Round-Robin
Processo A
Processo B
tempo5 9 11 13 16 21 23 26 27
 Tempo de CPU (u.t.) Característica do 
Processo
Processo A 15 CPU bound
Processo B 8 I/O bound 
5 u.t.
termina
quantum 
de A 
4 u.t.
B solicita 
I/O
A solicita 
I/O
2 u.t.
B solicita 
I/O
2 u.t.
5 u.t.
termina
quantum 
de A 
2 u.t.
B solicita 
I/O
3 u.t.
A solicita 
I/O
 
Round-Robin
 Vantagem do escalonamento Robin Round 
  simplicidade
 Tamanho da fatia de tempo é crucial no 
escalonamento circular
 pequena: tempo de troca de contexto 
torna-se significativo
 grande: aumenta o tempo de resposta 
dos processos no final da fila de prontos
 Vantagem do escalonamento Robin Round 
  simplicidade
 Tamanho da fatia de tempo é crucial no 
escalonamento circular
 pequena: tempo de troca de contexto 
torna-se significativo
 grande: aumenta o tempo de resposta 
dos processos no final da fila de prontos
 
Round-Robin
 Se existem n processos na fila de prontos
 Se quantum = q 
  cada processo tem 1/n do tempo de 
CPU em fatias de no máximo q unidades 
de tempo cada
 Nenhum processo espera por mais de 
(n-1) q unidades de tempo para ser 
atendido
 Se existem n processos na fila de prontos
 Se quantum = q 
  cada processo tem 1/n do tempo de 
CPU em fatias de no máximo q unidades 
de tempo cada
 Nenhum processo espera por mais de 
(n-1) q unidades de tempo para ser 
atendido
 
Round-Robin
 Desempenho
quantum = muito grande 
  FIFO
quantum = muito pequeno 
  q deve ser grande comparado a 
mudança de contexto, caso contrário, o 
overhead é muito elevado
 Desempenho
quantum = muito grande 
  FIFO
quantum = muito pequeno 
  q deve ser grande comparado a 
mudança de contexto, caso contrário, o 
overhead é muito elevado
 
Round-Robin
 Processo Tempo de execução
P1 53
P2 17
P3 68
P4 24
Diagrama de Gantt (quantum = 20 u.t.)
Tipicamente, temos turnaround time médio maior que 
na SJF, mais em compensação melhor resposta
0 20 37 57 77 97 117 121 134 154 162
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
 
Como um pequeno quantum de tempo aumenta as mudanças de 
contexto
tamanho do processo: 10 u.t. quantum mudançasde contexto
0 10
12 0
0 6 10
6 1
0 1 2 3 4 5 6 107 8 9
1 9
 
Múltiplas Filas
 Política do tipo preemptiva
 Prioridades são atribuídas às classes de processos
 Processos das classes de maior prioridade recebem o 
processador
 Processos podem migrar entre classes de acordo com 
seu comportamento
 Vantagem: adaptabilidade de acordo com o 
comportamento do processo
 
Múltiplas Filas
 Processos são classificados em função do 
tipo de processamento
 Cada grupo formado  fila associada 
 Fila de prontos associada a cada grupo 
permite
aplicação de tipos de escalonamento 
diferentes
 Processos são classificados em função do 
tipo de processamento
 Cada grupo formado  fila associada 
 Fila de prontos associada a cada grupo 
permite
aplicação de tipos de escalonamento 
diferentes
 
Múltiplas Filas
 Cada fila possui uma prioridade 
 SO só vai escalonar processos em uma fila 
se todos os processos das filas de maior 
prioridade estiverem vazias
 Cada fila possui uma prioridade 
 SO só vai escalonar processos em uma fila 
se todos os processos das filas de maior 
prioridade estiverem vazias
 
Múltiplas Filas
p = 3
p = 2
p = 0
p = 1
processos interativos
processos em batch
 
Fila de Processos do SistemaFila de Processos do Sistema
Fila de Processos BatchFila de Processos Batch
Fila de Processos InterativosFila de Processos Interativos
Maior PrioridadeMaior Prioridade
Menor PrioridadeMenor Prioridade
 sistema
mais prioritário
algoritmo de escalonamento por prioridades
 interativo
prioridade intermediária
escalonamento Round-Robin
 batch
menor prioridade
usa Round-Robin ou FCFS
 sistema
mais prioritário
algoritmo de escalonamento por prioridades
 interativo
prioridade intermediária
escalonamento Round-Robin
 batch
menor prioridade
usa Round-Robin ou FCFS
Exemplo
 
Múltiplas Filas com Realimentação
 Escalonamento anterior a classificação dos processos 
era estática
 Se processo alterar seu comportamento, o esquema 
pode falhar (não existe reclassificação)
 Seria interessante que o SO
 reconhecesse a alteração de comportamento de um 
processo
ajustasse dinamicamente o seu tipo de 
escalonamento
 
Múltiplas Filas com Realimentação
 No escalonamento por múltiplas filas com 
realimentação (multi-level feed-bak queues)
 é permitido que os processos sejam movimentados 
entre as filas
 ajuste dinâmico (mecanismo adaptativo)
 processo é direcionado para uma das filas em 
função de seu comportamento
 
Múltiplas Filas com Realimentação: 
Funcionamento
 Criação do processo
  prioridade mais alta e quantum mais baixo
 Cada fila pode implementar uma política de 
escalonamento diferente para chegar a CPU: 
 FIFO com quantum
 SJF
 RR 
 
Múltiplas Filas com Realimentação: 
Funcionamento
 Processo é reescalonado dentro da mesma fila 
quando
 processo volta ao estado de pronto
sofre preempção por outro processo de uma fila 
mais prioritária
 Processo é direcionado para fila de menor 
prioridade e maior quantum quando
 processo esgota o seu quantum (sofrendo 
preempção)
 
Múltiplas Filas com Realimentação: 
Funcionamento
 Quanto maior a prioridade menor o quantum
 Escalonamento de uma fila só acontece depois 
que todas as outras filas de prioridade mais alta 
estão vazias
 Fila de menor prioridade  Round-Robin
 
Múltiplas Filas com Realimentação: 
Características
Atende as necessidades de escalonamento de 
diversos tipos de processos
Processos I/O bound
 bom tempo de resposta: maior prioridade
 permanecem a maior parte do tempo nas 
filas de alta prioridade
 usa pouco a CPU
 
Múltiplas Filas com Realimentação: 
Características
Processos CPU bound
com o transcorrer do processamento sua 
prioridade vai sendo reduzida
É um mecanismo complexo e gera 
overhead, mas os resultados são 
satisfatórios
 
Múltiplas Filas com Realimentação: 
Exemplo 1
Fila 1 (escalonamento FIFO)
Fila 2 (escalonamento FIFO)
Fila m (Round-Robin)
Maior Prioridade
Menor Prioridade Maior quantum
Menor quantum
Fila 3 (escalonamento FIFO)
preempção por término de quantum
preempção por término de quantum
...
preempção por término de quantum
 
Múltiplas Filas com Realimentação: 
Exemplo 2
quantum = 8
quantum = 16
FCFS
 

	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63