6 Escalonamento

Prévia do material em texto

SISTEMAS OPERACIONAIS
Processos e Threads: Escalonamento
Ana Cristina A. Oliveira Dantas
ana.oliveira@ifpb.edu.br
IFPB – Instituto Federal da Paraíba
Campus Campina Grande
Eixo Temático
 Processos
 Threads
 Comunicação interprocessos
 Problemas clássicos de IPC
 Escalonamento
Processos e Threads: Escalonamento
2
•Os objetivos do escalonamento de processador
•Escalonamento preemptivo versus escalonamento não preemptivo
•O papel das prioridades no escalonamento
•Critérios de escalonamento
•Algoritmos de escalonamento comuns
Escalonamento de Processador3
Processos e Threads: Escalonamento
Introdução
 Política de escalonamento de processador:
 Determina que processo é executado em um determinado momento
 Escalonadores diferentes terão metas distintas!
 Escalonar = agendar
 Definir em que momento um evento deve ocorrer, gerenciar conflitos, 
maximizar o número de atividades em um período de tempo...
Processos e Threads: Escalonamento
4
Introdução ao Escalonamento
 Surtos de uso da CPU alternam-se com períodos de espera por E/S:
 (a) processo orientado à CPU (CPU-bound)
 (b) processo orientado à E/S (I/O-bound)
Processos e Threads: Escalonamento
5
Introdução ao Escalonamento
 Objetivos do algoritmo de escalonamento
Processos e Threads: Escalonamento
6
Níveis de escalonamento
 Escalonamento de alto nível
 Determina que serviços podem disputar os recursos
 Controla o número de processos admitidos por vez no sistema
 Escalonamento de nível intermediário
 Determina quais processos terão permissão de competir por processadores
 Responde a flutuações na carga do sistema
 Escalonamento de baixo nível
 Atribui prioridades
 Designa processadores a processos
Processos e Threads: Escalonamento
7
Níveis de escalonamento
8
Processos e Threads: Escalonamento
Escalonamento preemptivo versus 
escalonamento não preemptivo
 Processos preemptivos
 Podem ser removidos do processador em que estiverem sendo executados
 Podem melhorar o tempo de resposta
 São importantes para ambientes interativos
 Os processos que sofrem preempção permanecem na memória
 Processos não-preemptivos
 São executados até o fim ou até que passem o controle a um processador
 Problema: processos insignificantes podem vir a bloquear processos
importantes indefinidamente
Processos e Threads: Escalonamento
9
Prioridades dos Processos
 Prioridades estáticas
 Prioridades permanentes atribuídas a um processo
 São fáceis de implementar
 Sua sobrecarga é relativamente baixa
 Não respondem a mudanças no ambiente
 Prioridades dinâmicas
 Respondem a mudanças
 Promovem interatividade estável
 Sua sobrecarga é maior que a das prioridades estáticas
 Isso ocorre por causa de sua maior responsividade
Processos e Threads: Escalonamento
10
Objetivos de escalonamento
 Maximizar o rendimento
 Maximizar o número de processos interativos cujo tempo de resposta seja
aceitável
 Minimizar a utilização de recursos (minimizar a sobrecarga)
 Evitar o adiamento indefinido
 Impor prioridades
 Garantir previsibilidade (concluir o processo de acordo com o prazo 
estabelecido)
 Minimizar a latência
 Maximizar a utilização do processador
Processos e Threads: Escalonamento
11
Os objetivos dependem do tipo do sistema!
Objetivos de escalonamento
 Metas comuns à maioria dos escalonadores:
 Imparcialidade
 Previsibilidade
 Escalabilidade
Processos e Threads: Escalonamento
12
Critérios de escalonamento
 Processo orientado a processador (CPU-bound)
 Usa todo o tempo disponível do processador
 Processo orientado a E/S (I/O-bound)
 Gera uma solicitação de E/S rapidamente e devolve o processador
 Processo em lote
 Abrange trabalhos que o sistema executará sem interagir com o usuário
 Processos interativos
 Exige continuamente informações do usuário
Processos e Threads: Escalonamento
13
Algoritmos de escalonamento
 Determinam quando e por quanto tempo cada processo é executado
 Tomam decisões sobre:
 Preemptividade
 Prioridade
 Tempo de execução
 Tempo até a conclusão
 Imparcialidade
Processos e Threads: Escalonamento
14
Escalonamento primeiro-a-entrar-primeiro-a-sair 
(FIFO – First-In-First-Out)
 É o esquema mais simples
 Os processos são despachados de acordo com a hora de chegada
 Não é preemptível
 Raramente é usado como algoritmo de escalonamento principal
Processos e Threads: Escalonamento
15
Escalonamento primeiro-a-entrar-primeiro-a-sair
(FIFO)
Processos e Threads: Escalonamento
16
Escalonamento por alternância circular (RR)
 Escalonamento por alternância circular ou Round-Robin (RR)
 Baseia-se no FIFO
 Os processos são durante o quantum
 É preemptível
 Exige que o sistema mantenha vários processos na memória para
diminuir a sobrecarga
 É usado com freqüência como parte de algoritmos mais complexos
Processos e Threads: Escalonamento
17
Escalonamento por alternância circular (RR)
Processos e Threads: Escalonamento
18
Escalonamento por alternância circular (RR)
 Alterância circular egoísta
 Eleva a prioridade à medida que o processo envelhece
 Duas filas
 Ativa
 De retenção
 Favorece processos mais velhos para evitar atrasos exagerados
Processos e Threads: Escalonamento
19
Escalonamento por alternância circular: Como definir
o tamanho do quantum?
 Tamanho do quantum
 Determina o tempo de resposta a solicitações interativas
 Quantum muito grande
 Os processos são executados durante longos períodos
 Ruim para o FIFO, porque os processos são executados sem preempção
 Quantum muito pequeno
 O sistema despende mais tempo chaveando o contexto do que executando os processos
 Tamanho médio
 Longo o suficiente para que os processos interativos lancem solicitações de E/S
 Processos em lote continuam consumindo maior parte do tempo do processador
Processos e Threads: Escalonamento
20
Escalonamento por processo-mais-curto-primeiro (SPF –
Shortest-Process-First)
 O escalonador seleciona o processo cujo tempo de finalização é o menor
 Tempo de espera médio menor que no FIFO
 Reduz o número de processos em espera
 Variação possivelmente grande dos tempos de espera
 Não é preemptivo
 A capacidade de resposta pode diminuir para as solicitações interativas que
estão chegando
 Baseia-se na estimativa do tempo de execução até a conclusão
 Pode ser impreciso ou inválido
 Não é adequado para os modernos sistemas interativos
Processos e Threads: Escalonamento
21
Escalonamento em Sistemas em Lote
Um exemplo de escalonamento job mais curto primeiro
Processos e Threads: Escalonamento
22
Escalonamento em Sistemas em Lote
Escalonamento em três níveis
Processos e Threads: Escalonamento
23
Escalonamento em Sistemas Interativos
 Escalonamento por alternância circular (round-robin)
a) lista de processos executáveis
b) lista de processos executáveis depois que B usou todo o seu quantum
Processos e Threads: Escalonamento
24
Escalonamento em Sistemas Interativos
Um algoritmo de escalonamento com quatro classes de prioridade
Processos e Threads: Escalonamento
25
Escalonamento em Sistemas de Tempo-Real
Sistema de tempo-real escalonável
 Dados
 m eventos periódicos
 evento i ocorre dentro do período Pi e requer Ci segundos
 Então a carga poderá ser tratada somente se
Processos e Threads: Escalonamento
26
1
1
m
i
i i
C
P

Política versus Mecanismo
 Separa o que é permitido ser feitodo como é feito
 Um processo sabe quais de seus threads filhos são importantes e 
precisam de prioridade
 Algoritmo de escalonamento parametrizado
 Mecanismo no núcleo
 Parâmetros preenchidos pelos processos do usuário
 Política estabelecida pelo processo do usuário
Processos e Threads: Escalonamento
27
Escalonamento de Threads
Possível escalonamento de threads de usuário
 processo com quantum de 50-mseg
 threads executam 5 mseg por surto de CPU
Processos e Threads: Escalonamento
28
Escalonamento de Threads
Possível escalonamento de threads de núcleo
 Processo com quantum de 50-mseg
 Threads executam 5 mseg por surto de CPU
Processos e Threads: Escalonamento
29
Bibliografia
 ANDREW S. TANENBAUM. Sistemas Operacionais Modernos. Editora 
Prentice-Hall, 2ª Edição, 2003. ISBN: 8587918575
 Capítulo 2: Processos e Threads
 DEITEL & CHOFFNES. Sistemas Operacionais. Editora Prentice-Hall, 3ª 
Edição, 2005. ISBN: 8576050110.
 Capítulo 8: Escalonamento de Processador
Processos e Threads: Escalonamento
30