SO_5-escalonamento

Prévia do material em texto

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Capítulo 5: 
Escalonamento da CPU
4.2 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Sumário
 Conceitos básicos
 Critérios usados no escalonamento
 Algoritmos de escalonamento
 Escalonamento em multiprocessadores
 Escalonamento em tempo real
 Modelos de escalonamento
4.3 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Conceitos básicos
 Objetivo da multiprogramação: 
 Utilização máxima da CPU
 Processos normalmente alternam picos de processamento (uso da CPU) e 
E/S
 Quando um processo começa um pico de E/S outro deve assumir a CPU 
para evitar ociosidade
 Por outro lado, nenhum processo deve controlar a CPU indefinidamente! 
(melhorar a interação)
4.4 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Alternância de picos de CPU e E/S
4.5 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Distribuição de picos de CPU
4.6 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonador da CPU (scheduler)
 Controla a mudança de estado dos processos
 Escalonamento ocorre quando um processo:
 a) chaveia de “EM EXECUÇÃO” para “EM ESPERA”
 b) chaveia de “EM EXECUÇÃO” para “PRONTO”
 c) chaveia de “EM ESPERA” para “PRONTO”
 d) TERMINA
4.7 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Preempção ou não preempção
 Escalonamento não preemptivo
 Processo só deixa a CPU se tiver que esperar por E/S ou 
intencionalmente. Ex.: (a) em espera e (d) termina
 Implementação mais simples do escalonador
 Escalonamento preemptivo
 Periodicamente o escalonador interrompe o processo em execução e 
muda-o para “pronto”
 Escalonador mais complexo.
 Compartilhamento da CPU é garantido
4.8 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Dificuldades da Preempção
 Exige coordenação de acesso ao dado compartilhado
 produtor interrompido → dados inconsistentes
 Afeta o projeto do kernel
 troca de contexto durante chamada de sistema
 kernel atualizava tabelas de dispositivo
 não pode haver acesso simultâneo à ação de interrupção
 SO desabilita interrup. na entrada e reabilita na saída
4.9 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Dispatcher (despachante)
 Módulo responsável por dar o controle da CPU ao processo selecionado 
pelo escalonador
 Troca de contexto
 Mudança para modo usuário
 Desvio para o ponto apropriado do programa
 Latência de despacho: o mínimo possível
 Tempo gasto para o despachante interromper um processo e inciar a 
execução de outro
4.10 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Critérios de escalonamento
 Alguns critérios utilizados na comparação de algoritmos de escalonamento da CPU:
– Utilização de CPU – mantê-la tão ocupada quanto possível (ex.: 40-90%)
– Throughput – qtde. de processos concluídos numa unidade de tempo
– Tempo de turnaround – tempo para completar um processo (alocação + fila 
+ execução CPU + execução E/S), importante para sistemas não interativos
– Tempo de espera – soma dos períodos gastos em espera na fila “prontos”
– Tempo de resposta – tempo que vai do envio de uma solicitação até uma 
primeira resposta ser produzida, importante para sistemas interativos (de 
tempo compartilhado)
4.11 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Critérios de otimização
 Maximizar a utilização de CPU
 Maximizar o throughput
 Minimizar o tempo de turnaround
 Minimizar o tempo de espera
 Minimizar o tempo de resposta
– minimizar o tempo médio (ou o máximo)
– minimizar a variância no tempo de resposta (razoável mas 
previsível)
4.12 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
First-Come, First-Served (FCFS) 
 Gantt Chart do escalonamento:
 Tempo de espera: P1 = 6; P2 = 0; P3 = 3
 Tempo de espera médio: (6 + 0 + 3)/3 = 3
 Algoritmo simples
– implementação do FCFS gerenciada por uma FIFO
– sem preempção, ruim para tempo compartilhado
Ordem de chegada: P2, P3, P1
P1P3P2
63 300
4.13 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
First-Come, First-Served (FCFS) 
 Gráfico de Gantt do escalonamento:
 Tempo de espera: P1 = 0; P2 = 24; P3 = 27
 Tempo de espera médio: (0 + 24 + 27)/3 = 17
 “efeito comboio”: pequenos são atrasados pelo grande
 processos limitados por I/O esperaram pelo processo limitado pela CPU
P1 P2 P3
24 27 300
Ordem de chegada: P1, P2, P3
4.14 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Shortest-Job-First (SJF) 
 Associa-se a cada processo o intervalo de seu próximo pico de CPU
 Próximo processo: o de menor pico de CPU
 SJF preemptivo:
 Um processo de pico menor que o restante do processo corrente, força 
a preempção do último
 Chamado Shortest Remaining Time First (SRTF)
 SJF não preemptivo:
 Processos que chegam são comparados apenas com aqueles à espera 
da CPU
 SJF é ótimo quanto ao tempo médio de espera
– Executar um processo curto antes de um longo reduz mais o tempo de 
espera do curto do que aumenta o do longo
4.15 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
SJF não preemptivo
P1 P3 P2
73 160
P4
8 12
Tempo de espera médio = (0 + 6 + 3 + 7)/4 = 4
4.16 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
SJF preemptivo
Tempo de espera médio = (9 + 1 + 0 + 2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
4.17 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Problema: qual a duração do próximo pico?
 Bom p/ escalonamento de longo prazo (tarefas), ruim p/ escalonamento de 
curto prazo (CPU)
– no curto prazo, não há como saber o valor do próximo pico de 
utilização de CPU, mas um valor aproximado pode ser previsto
 A duração do próximo pico de CPU pode ser prevista de várias maneiras
 ex.: média exponencial dos intervalos medidos anteriormente, sendo:
1. tn= tamanho observado do n
ésimo pico de CPU
2 . τn= armazena a média histórica de CPU
3 . α = peso relativo, com 0≤α≤1
4 . Define-se:
τ n+1=αtn+ (1−α ) τ n .
4.18 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Previsão da duração do próximo 
pico de utilização de CPU
4.19 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento por prioridades
 Um valor de prioridade (inteiro) p/ cada processo
 A CPU é alocada ao processo prioridade mais alta
– Usualmente, menor valor = maior prioridade (ex.: Linux -20 a 20)
– Pode ser preemptivo ou não preemptivo (compara ou não com o processo 
executando na CPU)
 As prioridades podem ser definidas interna ou externamente
– Internamente, ex.: limite de tempo, razão entre picos médios de I/O e de CPU
– Externamente, ex.: “importância” do processo, $ pago pelo uso da CPU 
 OBS.: SJF é um caso especial do escalonamento por prioridades, em que a 
prioridade é o inverso do próximo pico de CPU
– quanto maior o pico de CPU, menor a prioridade e vice-versa
4.20 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento por prioridades
 Problema: inanição (starvation) ou bloqueio indefinido
 Processos de baixa prioridade podem esperar indefinidamente
 Ex.: um fluxo constante de processos com prioridade mais alta pode 
impedir o uso da CPU pelos processos de prioridade mais baixa
 Solução: envelhecimento (aging)
 Técnica que aumenta gradualmentea prioridade dos processos que 
esperam no sistema por muito tempo
 Ex.: num sistema com prioridades de -20 (mais alta) a 20 (mais baixa), 
um processo em espera de prioridade 20 poderia ter sua prioridade 
aumentada gradualmente (20, 19, 18, …, 0, -1, 2, ...) a cada 15 minutos
• No máximo, não levaria mais que 10 horas para um 
processo envelhecer e se tornar um processo de 
prioridade -20 (mais alta)
4.21 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Round Robin (RR)
 Projetado especialmente para sistemas de tempo compartilhado
– Define uma pequena unidade de tempo como quantum de tempo
– Geralmente o quantum de tempo tem duração de 10 a 100 ms
 A fila de prontos é tratada como uma fila FIFO circular
– O escalonador seleciona o 1º processo da fila, define um timer para interromper 
após 1 quantum e despacha o processo
– Pico de CPU > 1 quantum: timer desliga e causa interrupção, troca de contexto 
executada
– Pico de CPU < 1 quantum: o próprio processo libera a CPU voluntariamente
– Ao sair, o processo vai para o fim da fila
4.22 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Quantum e trocas de contexto
 Preempção periódica é um overhead
– quantum muito grande: RR decai numa política FCFS
– quantum muito pequeno: overhead se torna proibitivo
– quantum deve ser longo em relação ao tempo de troca de contexto
4.23 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Round Robin (RR)
 Quantum também é conhecido como “fatia”
– OBS.: 1 quantum, 2 quanta
 Se há n processos na fila de prontos:
 cada processo recebe 1/n do tempo da CPU
 processo executa por no máximo 1 quantum de cada vez
 nenhum processo espera mais que (n-1) quanta na fila de prontos
4.24 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Round Robin (RR)
 Exemplo (quantum = 4 unidades de tempo)
 Gantt chart: 
 Usualmente, turnaround pior que a SJF, porém c/ melhor capacidade de 
resposta
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
Processo Duração
P1 24
P2 3
P3 3
4.26 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Turnaround varia com o quantum
 o tempo de turnaround depende do quantum
– Não fica necessariamente melhor quando o quantum aumenta! Pode ser 
melhorado qdo a maioria dos proc. termina seu pico num único quantum
4.27 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento de filas em vários níveis
 Algoritmo de escalonamento para situações em que os processos são 
facilmente classificados em diferentes grupos
 Fila de prontos é dividida em:
 processos interativos (foreground)
 processos em lote/batch (background)
 Grupos de processos
– Com requisitos de tempo de resposta diferentes, diferentes 
necessidades de escalonamento
• foreground: RR
• background: FCFS
– Processo de foreground podem ter prioridade sobre os de background
4.28 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento de filas em vários níveis
 Estratégias de escalonamento entre filas
 Prioridade fixa com preempção
 ex.: atender sempre os processos interativos primeiro
→ possibilidade de inanição
 Fatias de tempo
 cada fila é escalonada por uma fração do tempo total (ex.: FG 80%, BG 20%)
4.29 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Filas multinível com retroalimentação
 Um processo pode se mover entre filas
 isso é uma forma de implementar envelhecimento!
 deixa os processos interativos e limitados por I/O nas filas de alta prior.
 se apresentar longos picos de CPU → fila de baixa prioridade
 Este tipo de escalonamento pode ser definido por:
 número de filas
 algoritmo de escalonamento de cada fila
 método usado para promover um processo
 método usado para rebaixar um processo
 método usado para decidir em que fila cada processo entra no sistema
4.30 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento de multiprocessadores
 Escalonamento se complica com múltiplas CPUs
 Coisas acontecem realmente ao mesmo tempo
 Livro só aborda o caso de processadores homogêneos e com acesso 
uniforme à memória
 Podem fazer compartilhamento de carga
 CPUs acessam uma mesma fila
 Acesso à fila pode gerar contenção
4.31 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Escalonamento de multiprocessadores
Multiprocessamento Assimétrico (AMP): 
 só um processador (mestre) acessa as estruturas de dados do sistema
 reduz a complexidade do sistema
– ex.: primeiras versões do Linux multiprocessado
Multiprocessamento Simétrico (SMP): 
 todas as CPUs acessam dados e recursos de forma igual
– ex.: Windows XP (e posteriores), Solaris, Linux, Mac OS X
– opções: um só fila de prontos com todos os processos (contenção!) 
ou cada processador pode ter sua própria fila de prontos (é o 
mais usado)
4.32 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Multiprocessamento Simétrico (SMP)
Considerações sobre o Multiprocessamento Simétrico (SMP): 
 afinidade com o processador: se um processo migra de CPU, a cache do 
1º processador deve ser invalidada e a cache do 2º preenchida (alto 
custo)
 balanceamento de carga: quando cada processador tem sua fila, é 
importante que a carga de trabalho se mantenha balanceada entre os 
processadores
 processadores multicore: tendência atual no uso de múltiplos núcleos no 
mesmo chip físico (mais rápidos e consomem menos energia)
– cada núcleo tem seus registradores e aparenta ser um processador 
físico aos olhos do SO
– quando um processador acessa a memória (chace) ele gasta um 
tempo significativo esperando até os dados ficarem disponíveis
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Fim do Capítulo 5
	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 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 35