FACULDADE PITÁGORAS DE TECNOLOGIA
Gerência
do processador
(Escalonamento)
Faculdade PITÁGORAS – Outubro de 2012
Prof. Robert Gans
[email protected]
Prof. Robert Gans
1
FACULDADE PITÁGORAS DE TECNOLOGIA
Objetivos
 Este capítulo apresenta:
■
■
■
■
■
■
Prof. Robert Gans
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.
Os conceitos de escalonamento por prazo e de tempo real.
2
FACULDADE PITÁGORAS DE TECNOLOGIA
8.1 Introdução
 Política de escalonamento de processador
■
■
Determina que processo é executado em um determinado
momento.
Escalonadores diferentes terão metas distintas:
●
●
●
●
●
●
●
Maximizar o rendimento.
Minimizar a latência.
Evitar o adiamento indefinido.
Concluir o processo de acordo com o prazo estabelecido.
Maximizar a utilização do processador.
Privilegiar a execução de aplicações críticas
Balancear o uso da CPU entre processos
● Oferecer tempos de resposta razoáveis aos usuários interativos.
Prof. Robert Gans
3
FACULDADE PITÁGORAS DE TECNOLOGIA
8.1 Introdução
Conceitos Importantes:
Utilização do processador: corresponde a uma taxa de utilização, que na maioria dos sistemas
varia entre 30 e 90%. Uma utilização abaixo dos 30% indicaria um sistema ocioso, enquanto uma
taxa de utilização acima dos 90% pode indicar um sistema bastante carregado, próximo da sua
capacidade máxima (em alguns casos tal situação pode levar a um crash – travamento do sistema).
Throughput: é o 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. A maximização do
throughput é desejada na maioria dos sistemas.
Tempo de Processador: é o tempo que um processo leva no estado de execução, durante seu
processamento. As políticas de escalonamento não interferem neste parâmetro, sendo este tempo
função apenas do código executável e da entrada/saída de dados.
Prof. Robert Gans
4
FACULDADE PITÁGORAS DE TECNOLOGIA
8.1 Introdução
Conceitos Importantes:
Tempo de Espera (pela CPU): é todo o tempo que o processo permanece na fila de pronto,
aguardando a liberação da CPU para ser executado. A redução deste tempo de espera é desejada pela
maioria das políticas de escalonamento.
Tempo de Turnaround: é o tempo total que o processo permaneceu no sistema, desde sua criação
até o momento em que é encerrado. São contados os tempos de:
• alocação de memória.
• espera na fila de pronto.
• interrupção (E/S).
Tempo de Resposta: é o tempo decorrido entre uma requisição ao sistema e o instante em que a
resposta começa a ser exibida. Em sistemas interativos, como aplicações on-line ou acesso à Web, os
tempos de resposta devem ser da ordem de apenas poucos segundos.
Prof. Robert Gans
5
FACULDADE PITÁGORAS DE TECNOLOGIA
8.2 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
■
■
Prof. Robert Gans
Atribui prioridades.
Designa processadores a processos.
6
FACULDADE PITÁGORAS DE TECNOLOGIA
8.2 Níveis de escalonamento
Prof. Robert Gans
7
FACULDADE PITÁGORAS DE TECNOLOGIA
8.3 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
■
■
Prof. Robert Gans
São executados até o fim ou até que passem o controle a um
processador.
Processos insignificantes podem bloquear processos
importantes indefinidamente.
8
FACULDADE PITÁGORAS DE TECNOLOGIA
8.4 Prioridades
 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.
Prof. Robert Gans
9
FACULDADE PITÁGORAS DE TECNOLOGIA
8.5 Objetivos de escalonamento
 Objetivos diferentes, dependendo do sistema:
■
■
■
■
■
■
■
Prof. Robert Gans
Maximizar o rendimento.
Maximizar o número de processos interativos cujo tempo de
resposta seja aceitável.
Minimizar a utilização de recursos.
Evitar o adiamento indefinido.
Impor prioridades.
Minimizar a sobrecarga.
Garantir previsibilidade.
10
FACULDADE PITÁGORAS DE TECNOLOGIA
8.5 Objetivos de escalonamento
 Várias metas são comuns à maioria dos
escalonadores:
■
■
■
Prof. Robert Gans
Imparcialidade.
Previsibilidade.
Escalabilidade.
11
FACULDADE PITÁGORAS DE TECNOLOGIA
8.6 Critérios de escalonamento
 Processo orientado a processador
■
Usa todo o tempo disponível do processador.
 Processo orientado a E/S
■
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
■
Prof. Robert Gans
Exige continuamente informações do usuário.
12
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7 Algoritmos de escalonamento
 Algoritmos de escalonamento
■
■
Determinam quando e por quanto tempo cada processo é
executado.
Tomam decisões sobre:
●
●
●
●
●
Prof. Robert Gans
Preemptividade.
Prioridade.
Tempo de execução.
Tempo até a conclusão.
Imparcialidade.
13
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.1 Escalonamento
primeiro-a-entrar-primeiro-a-sair (FIFO)
 Escalonamento FIFO (First In First Out)
■
■
■
■
É o esquema mais simples.
Os processos são despachados de acordo com a hora de
chegada e permanece utilizando o processador até terminar sua
execução ou ser interrompido por E/S.
Não é preemptível.
Raramente é usado como algoritmo de escalonamento principal
devido às suas deficiências :
•
Dificuldade de se prever o início da execução de um
processo, já que a ordem de chegada à fila de pronto deve
ser observada à risca.
•
Outro problema é quanto aos tipos de processo, onde os
CPU-bound levam vantagem no uso do processador em
relação aos do tipo I/O-bound, pois o sistema não trata
este tipo de diferença.
O escalonamento FIFO foi inicialmente implementado em
sistemas monoprogramáveis, sendo ineficiente se aplicado em
sistemas interativos de tempo compartilhado.
Prof. Robert Gans
14
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.1 Escalonamento
primeiro-a-entrar-primeiro-a-sair (FIFO)
Figura 8.2 Escalonamento primeiro-a-entrar-primeiro-a-sair.
Abaixo, um exemplo de escalonamento utilizando o método FIFO: a ordem de chegada
dos processos (A, B, C) na fila de pronto foi obedecida, e, não tendo sido interrompidos
por E/S, os processos executaram inteiramente até terminar, de acordo com seus
tempos necessários para execução.
OBS: u.t. = Unidades de Tempo
Prof. Robert Gans
15
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.2 Escalonamento por
processo-mais-curto-primeiro (SPF ou SJF Shortest Job 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 velocidade do tempo de resposta diminui 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.
Como exemplo, vamos utilizar os mesmos processos executados no escalonamento
FIFO, com seus respectivos tempos de execução em u.t. (unidades de tempo):
processo A com 10 u.t., processo B com 8 u.t, e o processo C com 9 u.t. Como
neste escalonamento o que importa é o tempo de execução, a nova ordem de
escalonamento para utilização da CPU será B, C e A, como segue:
Prof. Robert Gans
16
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.3 Escalonamento por alternância circular (RR)
 Escalonamento por alternância circular
(Round-Robin — RR)
■
■
■
■
■
■
■
■
Prof. Robert Gans
Baseia-se no FIFO.
Projetado especialmente para sistemas de tempo
compartilhado.
Os processos são executados apenas durante um determinado
período denominado intervalo de tempo ou quantum.
É preemptível. (É conhecido como preempção por tempo)
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.
A principal vantagem deste escalonamento é não permitir que
um processo monopolize a CPU
uma desvantagem é que os processos CPU-bound são
beneficiados no uso do processador em relação aos processos
I/O-bound, pois tendem a utilizar totalmente a fatia de tempo
recebida.
17
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.3 Escalonamento por alternância circular (RR)
Figura 8.3 Escalonamento por alternância circular.
A figura a seguir mostra o escalonamento circular com 3 processos, onde a fatia de
tempo é igual a 2 u.t. No exemplo não estão sendo levados em consideração tempos
de troca de contexto entre os processos, nem o tempo perdido em operações de E/S.
Os processos A, B e C, gastam 10 u.t, 6 u.t e 3 u.t., respectivamente.
Prof. Robert Gans
18
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.3 Escalonamento por alternância circular (RR)
 Tamanho do quantum
■
■
Determina o tempo de resposta a solicitações interativas.
Quantum muito grande
● Os processos são executados durante longos períodos.
● Degenera o FIFO.
■
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
processado.
Prof. Robert Gans
19
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.4 Filas multiníveis de retorno
 Processos diferentes têm necessidades diferentes.
■
■
Os processos interativos curtos orientados a E/S geralmente
devem ser executados antes dos processos em lote orientados a
processador.
Os padrões de comportamento não são imediatamente
evidentes para o escalonador.
 Filas multiníveis de retorno
■
■
Os processos que chegam entram na fila de nível superior e sua
prioridade de execução é maior que a dos processos nas filas
inferiores.
Os processos longos são continuamente transferidos para os
níveis inferiores.
● Atribuem maior prioridade aos processos curtos e aos processos
orientados a E/S.
● Os processos longos serão executados quando da conclusão dos
processos curtos e orientados a E/S.
■
Os processos de cada fila são atendidos por meio do
escalonamento por alternância circular.
● Os processos que entram na fila de nível superior provocam
preempção nos processos em execução.
Prof. Robert Gans
20
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.4 Filas multiníveis de retorno
 O algoritmo precisa responder a mudanças no
ambiente.
■
Muda os processos para diferentes filas à medida que eles
alternam entre o procedimento interativo e em lote.
 Exemplo de mecanismo adaptativo:
■
Prof. Robert Gans
Os mecanismos adaptativos provocam uma sobrecarga em
geral compensada por uma percepção mais precisa do
comportamento do processo.
21
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.5 Escalonamento por fração justa
ou
Fair Share Scheduling (FSS)
 O FSS controla o acesso do usuário aos recursos do sistema.
■
■
■
■
•
•
•
Alguns grupos usuários são mais importantes que outros.
Garante que os grupos menos importantes não monopolizem os recursos.
Os recursos que não estão sendo usados são distribuídos de acordo com a
proporção de recursos que cada grupo alocou.
Atribui-se maior prioridade aos grupos que não atendem às metas de utilização
de recursos.
Considera não os processos em si, mas os usuários, para que a divisão de CPU seja
justa entre eles.
As frações de tempo de CPU são dadas aos usuários, independentemente do número
de processos cada um vai executar
Ex.
Usuário 1 roda processos A, B, C e D
Usuário 2 roda processo E
Se cada um tiver 50% da CPU, por round-robin
A E B E C E D E A E A E B E ...
Se Usuário 1 tiver 66% e Usuário 2 34%
A B E C D E A B E C D E A B ...
Prof. Robert Gans
22
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.5 Escalonamento por fração justa
Figura 8.5 Exempo de não FSS; Escalonador do processo-padrão do UNIX. O escalonador
concede o processador aos usuários, cada um deles pode ter muitos processos. (Propriedade
da AT&T Archives.
Reproduzido com a permissão da AT&T.)
Prof. Robert Gans
23
FACULDADE PITÁGORAS DE TECNOLOGIA
8.7.5 Escalonamento por fração justa
Figura 8.6 Escalonador por fração justa. O escalonador por fração justa divide a
capacidade de recursos dos sistema em porções, as quais são alocadas por escalonadores
de processo designados a vários grupos de fração justa. (Propriedade da AT&T Archives.
Reproduzido com a permissão da AT&T.)
Prof. Robert Gans
24
FACULDADE PITÁGORAS DE TECNOLOGIA
8.8 Escalonamento por prioridade
Funciona com base num valor associado a cada processo, denominado prioridade de
execução.
O processo com maior prioridade na fila de PRONTO é sempre o escolhido para
ocupar o processador, sendo os processos com prioridades iguais escalonados pelo
critério FIFO.
Neste escalonamento o conceito da fatia de tempo não existe. Como conseqüência
disto, um processo em execução não pode sofrer preempção por tempo.
Neste escalonamento a perda do uso do processador somente ocorrerá no caso de uma
mudança voluntária para o estado de espera (interrupção por E/S), ou quando um
outro processo de prioridade maior passa (ou chega) para o estado de pronto. Neste
caso o sistema operacional interrompe o processo em execução, salva seu contexto e
o coloca na fila de pronto, dando lugar na CPU ao processo prioritário.
Este mecanismo é chamado de preempção por prioridade.
Prof. Robert Gans
25
FACULDADE PITÁGORAS DE TECNOLOGIA
8.8 Escalonamento por prioridade
A figura a seguir mostra a execução dos processos A, B e C, com tempos de execução de 10, 4
e 3 u.t. respectivamente, e valores de prioridades de 2, 1 e 3, também respectivamente. Na
maioria dos sistemas, valores menores correspondem à MAIOR prioridade. Assim, a ordem de
execução será invertida para B, A e C.
Prof. Robert Gans
26
FACULDADE PITÁGORAS DE TECNOLOGIA
8.8 Escalonamento por prioridade
A prioridade de execução faz parte do contexto de software
do processo, e pode ser estática (quando não pode ser
alterada durante a existência do processo) ou dinâmica
(quando pode ser alterada durante a existência do processo).
Este escalonamento é muito usado em sistemas de tempo
real, com aplicações de controle de processos, controle de
tráfego (sinais de trânsito, de trens/metrô, aéreo), robótica,
entre outros.
Prof. Robert Gans
27
FACULDADE PITÁGORAS DE TECNOLOGIA
8.9 Escalonamento por prazo
 Escalonamento por prazo
■
■
■
O processo precisa ser concluído em um prazo específico.
É usado quando um processo precisa ser concluído a tempo,
pois do contrário seria inútil.
É difícil de implementar.
● Deve programar as solicitações de recursos com antecedência.
● Sua sobrecarga é significativa.
● O atendimento a outros processos pode degradar.
Prof. Robert Gans
28
FACULDADE PITÁGORAS DE TECNOLOGIA
8.10 Escalonamento de tempo real
 Escalonamento de tempo real
■
■
■
Está relacionado com o escalonamento por prazo.
Os processos têm restrição de tempo.
Engloba também tarefas que são executadas
periodicamente.
 Duas categorias: (Crítico e não crítico)
 A severidade da pena pelo não cumprimento das tarefas num determinado
intervalo de tempo é o fator que os distingüe.
■
Escalonamento de tempo real não crítico
● Não garante que as restrições de tempo serão cumpridas.
● Por exemplo, reprodução de multimídia.
■
Escalonamento de tempo real crítico
● As restrições de tempo sempre serão cumpridas.
● O não cumprimento do prazo pode ter resultados catastróficos.
● Por exemplo, controle de tráfego aéreo.
●
●
Prof. Robert Gans
Outra classificação: (Estático e Dinâmico)
29
FACULDADE PITÁGORAS DE TECNOLOGIA
8.10 Escalonamento de tempo real (Estático)
Antes de avançarmos veremos alguns conceitos importantes em
relação a estes escalonamentos:
Prof. Robert Gans
30
FACULDADE PITÁGORAS DE TECNOLOGIA
8.10 Escalonamento de tempo real (Estático)
■
Escalonamento de tempo real estático
■
■
■
Não ajusta as prioridades ao longo do tempo.
Sua sobrecarga é baixa.
É adequado para sistemas cujas condições mudam raramente.
■ Exemplos de Escalonadores de tempo real estático:
■
Escalonamento por taxa monotônica (rate monotonic scheduling – RMS)
● A prioridade do processo eleva-se monotonicamente (linearmente) de
acordo com a freqüência com que deve ser executado.
● (Quanto mais frequente, maior a prioridade)
■
Escalonamento por taxa monotônica com prazo
● Útil para um processo periódico cujo prazo não é o mesmo que o do seu
período.
Prof. Robert Gans
31
FACULDADE PITÁGORAS DE TECNOLOGIA
8.10 Escalonamento de tempo real (Dinâmico)
 Escalonamento de tempo real dinâmico
■
■
■
■
■
Ajusta as prioridades em resposta a situações variáveis.
Não atribuem prioridades fixas aos processos.
As decisões de escalonamento são tomadas em tempo de execução e as
prioridades dos processos podem mudar.
Sua sobrecarga pode ser significativa, mas deve garantir que
essa sobrecarga não interfira no cumprimento dos prazos.
As prioridades baseiam-se normalmente no prazo dos
processos.
● Prazo-mais-curto-primeiro (Earliest Deadline First - EDF)
→ Algoritmo preemptivo que sempre despacha primeiro o processo cujo
prazo é o mais curto.
● Folga-mínima-primeiro
→ Semelhante ao EDF, mas baseia sua prioridade na folga, que, por
sua vez, é baseada no prazo do processo e no tempo de execução
restante até sua conclusão.
Prof. Robert Gans
32