SO_07 - Escalonador de Processos.pdf

Prévia do material em texto

Sistemas Operacionais
Prof. Fernando Eryck
2012.2
Redes de Computadores
SUMÁRIO
� Gerenciador de Processos
Introdução
�Sistemas multiprogramáveis 
� Múltiplos processos compartilhamento a memória principal 
� Múltiplos processos fazendo a disputa pelo uso da CPU (fila)
�Sistema operacional 
�deve decidir qual dos processos será escolhido para fazer uso do 
processador
�Seleção baseada em critérios
�Política de escalonamento
Estado de
Espera
Estado de
Execução
Estado de
Pronto
Escalo
na
m
ento
Funções Básicas da Política de Escalonamento
�Manter a CPU ocupada a maior parte do tempo
�Balancear o uso da CPU entre os processos
�Privilegiar a execução de aplicações críticas
�Maximar o throughput 
�Oferecer tempos de respostas razoázeis para usuários interativos
�Implementar o scheduler e dispatcher
� Scheduler (Escalonador) – rotina do SO que tem como principal 
função implementar os critérios da política de escalonamento
�Dispatcher – rotina do SO responsável pela troca de contexto dos 
processos após o escalonamento
Funções Básicas da Política de Escalonamento
� Processos – unidades de alocação de recursos
�Threads - unidades de escalonamento
Critérios de Escalonamento
�Maximizar a utilização do processador
� É desejável que o processador permaneça a maior parte do seu 
tempo ocupado. 
�U/lização <= 30% → carga de processamento baixa�U/lização <= 30% → carga de processamento baixa
�Utilização até 90% → carga de processamento próximo a 
capacidade máxima
�Maximizar a produção do sistema (Throughput)
� Número de processos executados em um determinado intervalo de 
tempo
� Quanto maior o throughput, maior o número de tarefas executadas em 
função do tempo
Critérios de Escalonamento
� Tempo de processador / Tempo de CPU
� Tempo que um processo leva no estado de execução durante seu 
processamento
�Minimizar o tempo de espera�Minimizar o tempo de espera
� Tempo total de um processo na fila de pronto durante seu 
processamento, aguardando para ser executado.
�Minimizar o tempo de execução (Turnaround)
� tempo de criação de um processo até seu término
� tempo de espera alocação recursos + fila de pronto + tempo de 
processamento + tempo de espera (e/s)
Critérios de Escalonamento
�Minimizar o tempo de resposta
� Tempo decorrido entre uma requisição ao sistema e o instante em que a 
resposta é exibida
� Tempo de resposta, em geral, é limitado pela velocidade dos dispositivos 
de E/S, e não pela capacidade de processamento do sistema de E/S, e não pela capacidade de processamento do sistema 
computacional
Política de Escalonamento Visa:
- Otimizar a utilização do processador e o throughput
- Diminuir os tempos de turnaround, espera e resposta
Classificação das Políticas de Escalonamento -
Escalonadores Preemptivos e Não-Preemptivos
�Preemptivos 
� Possibilidade do SO interromper um processo em execução e substituí-
lo por outro
� Implementação mais complexa
� Possibilita políticas de escalonamento mais flexíveis
� É possível ao sistema priorizar a execução de processos� É possível ao sistema priorizar a execução de processos
� Possibilidade de implementar políticas de escalonamento que 
compartilhem a CPU de maneira uniforme.
�Não-preemptivos
� Quando um processo está em execução nenhum evento externo pode 
ocasionar a perda do uso do processador
� O processo sai do estado de execução quando terminar seu 
processamento, ou;
� Executar instruções do próprio código que o mude para o estado de 
espera
Escalonamento FIFO – (First In - First Out)
�O processo que chegar primeiro ao estado de pronto, é o 
primeiro a ser selecionado para execução
� Simples de ser implementado
� Necessário uma fila Necessário uma fila 
� Todos os processos quando saem do estado de espera entram no 
final da fila de pronto
� Tipo não-preemptivo
UCP
Estado de
Criação
Estado de
Espera
Fila dos processos no estado de Pronto
Estado de
Término
Problemas do escalonamento FIFO
� Problema
� Processos CPU-Bound levam 
vantagem no uso do processador 
em relação aos I/O-Bound
Processo A
Processo B
Processo C
10 14 17 u.t.
� Não se sabe quando um processo 
terá sua execução iniciada
�Não há uma preocupação em 
melhorar o tempo médio de espera.
�Problema nos tempos de 
turnaround para processos que 
demandam pouco tempo de CPU
10 14 17
Processo A
Processo B
Processo C
4 7 17 u.t.
u.t.
Processo
Tempo de
processador
(u.t.)
A
B
C
10
4
3
Implementações do escalonamento FIFO
� Implementado inicialmente em sistemas monoprogramáveis 
do tipo batch.
� Implementado atualmente em sistema de tempo 
compartilhado com algumas variações.compartilhado com algumas variações.
Escalonamento Shortest-Job-First (SJF)
�Algoritmo de escalonamento seleciona o processo que tiver o 
menor tempo de processador ainda por executar
� O processo na fila de pronto que necessita de menos tempo de CPU é 
selecionado 
�Realizado uma estimativa com base nas execuções passadas
� Para cada novo processo um tempo de CPU era associado ao 
seu contexto de software
Processo A
Processo B
Processo C
3 7 17 u.t.
Problema do Escalonamento SJF
� Impossibilidade de estimar tempo de processador para 
processos interativos
�Não é possível ao SO saber quanto tempo um processo irá 
permanecer utilizando a CPU na próxima vez que for escalonado, permanecer utilizando a CPU na próxima vez que for escalonado, 
mas é possível prever o tempo com base no comportamento 
passado
� É possível haver Starvation para processos com tempo de 
processador muito longo
� CPU-Bound
Starvation = Ocorre quando um processo fica indefinidamente esperando pela
utilização da CPU.
Escalonamento Shortest-Job-First (SJF)
�Tipo não-preemptivo (concepção inicial)
� Vantagem sobre o FIFO
� redução do tempo médio de turnaround dos processos
Implementações do Shortest-Job-First (SJF)
� Implementado nos primeiros SOs exclusivamente em batch
Escalonamento SJF preemptivo
�Escalonamento shortest remaining time (SRT Scheduling)
� Toda vez que um processo no estado de pronto tem um tempo de 
processador estimado menor do que o processo em execução o SO 
realiza a preempção
� O SO continua estimando o tempo de processador� O SO continua estimando o tempo de processador
�O risco de sofrer Stavartion continua
Escalonamento Cooperativo
�Um processo em execução libera voluntariamente o uso da CPU 
� Tarefa realizada exclusivamente pelo processo em execução
� Implementado em escalonadores que não executam a preempção, FIFO e SJF
�Processo verifica a fila de mensagens para determinar se existem outros �Processo verifica a fila de mensagens para determinar se existem outros 
processos na fila de pronto
�Melhor distribuição do processador
�Problema 
� Caso o processo não verifique a fila de mensagens os demais processos 
não terão chance de serem executadas até o término do uso da CPU
�EX. 
� Primeiros SOs Windows (Win 3.11)
Escalonamento Circular (Round Robin 
Scheduling))
�Escalonamento preemptivo
�Projetado para sistemas de tempo compartilhado
�Semelhante ao FIFO
� Quando um processo passa para o estado de execução é � Quando um processo passa para o estado de execução é 
alocado um tempo limite chamado fatia de tempo ou quantum.
� A fatia de tempo depende da arquitetura do SO e varia de 10 a 
100 ms
� Ao final da fatia de tempo o SO:
� interrompe o processo em execução
� Salva seu contexto
� Direciona para o final da fila de pronto
Escalonamento Circular (Round Robin 
Scheduling))
�O processo permanece em execução até que:
�Termine seu processamento 
�Voluntariamentepasse para o estado de espera
� Fatia de tempo expire� Fatia de tempo expire
� Vantagem
� Não permite que um processo monopolize a CPU
Escalonamento Circular (Round Robin 
Scheduling))
Preempção por tempo
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Estado de
Espera
Processo A
Processo B
Processo C
2 4 17 u.t.6 8 10 11
Escalonamento Circular (Round Robin 
Scheduling))
�Problema (Balanceamento desigual)
� CPU-Bound são beneficiados em relação ao I/O-Bound
� CPU-Bound tendem a utilizar por completo a fatia de tempo
� I/O-Bound passam mais tempo no estado de espera� I/O-Bound passam mais tempo no estado de espera
UCP
Estado de
Criação
Estado de
Espera
Fila dos processos no estado de Pronto
Estado de
Término
Escalonamento Circular (Round Robin 
Scheduling))
� Escalonamento Circular Virtual (Mecanismo adaptativo)
� Processos saem do estado de espera vão para uma fila de pronto auxiliar
� Os processos da fila auxiliar possuem preferência no escalonamento em 
relação à fila de pronto
� Fila de pronto é escalonada quando a fila auxiliar estiver vazia� Fila de pronto é escalonada quando a fila auxiliar estiver vazia
Preempção por tempo
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Estado de
Espera
Fila auxiliar
Processos na fila auxiliar
continuarão executando o 
tempo restante da fatia de
tempo.
Escalonamento por Prioridades
�Tipo preemptivo
� Realizado com base em um valor associado a cada processo 
denominado prioridade execução
� O processo com maior prioridade no estado de pronto e sempre � O processo com maior prioridade no estado de pronto e sempre 
o escolhido para execução
�Não existe o conceito de fatia de tempo
� Processos com prioridades iguais seguem o critério FIFO
� Perda do uso do processador
� Mudança voluntária para o estado de espera
� Um processo de prioridade maior passe para o estado de pronto
� termine seu processamento
Escalonamento por Prioridades
Estado de
Filas dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Estado de
UCP
Estado de
Término
Prioridade Pn
Estado de
Criação
Estado de
Espera
Preempção por prioridade
Escalonamento por Prioridades
Processo A
Processo B
Processo
Tempo de
processador
(u.t.)
Prioridade
Processo B
Processo C
3 13 17 u.t.
A
B
C
10
4
3
2
1
3
Escalonamento por Prioridades
�Tipo Não-preemptivo
� Processsos que passem para o estado de pronto com 
prioridade maior do que a do processo em execução não 
ocasionam preempção
� São colocados no ínicio da fila de pronto
� Prioridade estática 
� não tem seu valor alterado durante a existência do processo
�Prioridade dinâmica
� Pode alterar o valor de acordo com critérios definidos pelo SO
Escalonamento por Prioridades
� Principais problemas do Escalonamento de prioridades
� Processos de baixa prioridade podem sofrer starvation, permanecendo 
na fila de pronto indefinidamente
� Solução 
� Mecanismo de aging. � Mecanismo de aging. 
�Mecanismo que incrementa gradualmente a prioridade de 
processos que permanecem por muito tempo na fila de pronto
Escalonamento Circular com Prioridades
�a cada processo implementa o conceito de :
� fatia de tempo;
� Prioridade de execução
� O processo permanece no estado de execução até que:
� Termine seu processamento
� Voluntariamente passe para o estado de espera 
� Sofra uma preempção por tempo ou prioridade
� Permite um melhor balanceamento no uso do processador
� Processos I/O-Bound devem receber do adm. de sistemas prioridades 
maiores que os processos CPU-Bound.
� Usado em sistemas Windows e Unix
Escalonamento Circular com Prioridades
�Possui duas variações
� Prioridade estática
� Prioridade dinâmica
Escalonamento Circular com Prioridades
Estado de
Término
Fila dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Estado de
Criação UCP Término
Prioridade Pn
Criação
Estado de
Espera
Preempção por tempo ou prioridade
Escalonamento por Múltiplas Filas
� Diversas filas de processo no estado de pronto, cada qual com uma 
prioridade especifica
�Processos são associados às filas em função de características próprias 
� Importância para aplicação
� Tipo de processamento� Tipo de processamento
� Àrea de memória necessária
�Vantagem 
� Convivência de mecanismos de escalonamento distintos
� FIFO e CIRCULAR por exemplo
Escalonamento por Múltiplas Filas
� Preempção
� Ocorre com base nas filas (fila com maior prioridade)
� O SO só pode escalonar processos de uma fila caso a fila de prioridade 
maior estiver vazia
� Desvantagem
� Caso o processo altere seu comportamente no decorrer do tempo o 
processo não poderá ser redirecionado para uma fila mais adequada
Escalonamento por Múltiplas Filas
Fila de processos do sistema
Fila de processos interativos
Maior
prioridade
UCP
Fila de processos batch
Menor
prioridade
Escalonamento por Múltiplas Filas com 
realimentação
� semelhante ao de múltiplas filas, porém os processos podem trocar de filas 
durante seu processamento
Fila 1 (FIFO Adaptado)
Preempção por tempo
M
a
i
o
r
P
r
i
o
r
i
d
a
d
e
M
e
n
o
r
 
f
a
t
i
a
d
e
 
t
e
m
p
o
UCP
Fila 2 (FIFO Adaptado)
Preempção por tempo
Fila 3 (FIFO Adaptado)
Preempção por tempo
Fila n (Circular)
Preempção por tempo
M
e
n
o
r
P
r
i
o
r
i
d
a
d
e
M
a
i
o
r
 
f
a
t
i
a
d
e
 
t
e
m
p
o
Escalonamento por Múltiplas Filas com 
realimentação
�Vantagem
� SO pode identificar dinamicamente o comportamento de cada processo , 
direcionando-os para filas com prioridade de execução
�Escalonamento
� Ocorre apenas quando todas as outras filas de prioridade mais alta � Ocorre apenas quando todas as outras filas de prioridade mais alta 
estiverem vazias.
� A fatia de tempo em cada fila varia em função da prioridade
� quanto maior a prioridade da fila menor a sua fatia de tempo