Upload
voduong
View
215
Download
0
Embed Size (px)
Citation preview
Gerência de Recursos
Gerência do Processador
Escalonamento Não-Preemptivos e Preemptivos
• Preempção - possibilidade de o SO interromper um processo em execução e substituí-lo por um outro.
• O Escalonamento não-preemptivo foi o primeiro tipo de escalonamento implementado nos sistemas multiprogramáveis, onde predominava tipicamente o processamento batch.
Escalonamento Não-Preemptivos e Preemptivos
• Nesse tipo de escalonamento, quando um processo está em execução nenhum evento externo pode ocasionar a perda do uso do processador.
• Só muda de estado quando terminar ou execute instruções que ocasionem uma mudança para o estado de espera
• Exemplos: Windows 3.1 e IBM OS/2.
Escalonamento Não-Preemptivos e Preemptivos
• O escalonamento preemptivo écaracterizado pela possibilidade do SO interromper um processo em execução e passá-lo para o estado de pronto, com o objetivo de alocar outro processo na CPU.
• Com o uso da preempção, é possível ao sistema priorizar a execução de processos, como no caso de aplicações de tempo real onde o fator tempo é crítico.
Escalonamento Não-Preemptivos e Preemptivos
• Outro benefício é a possibilidade de implementar políticas de escalonamento que compartilhem o processador de uma maneira mais uniforme, distribuindo de forma balanceada o uso da CPU.
• Exemplos: Windows 95/98..., Linux, QNX.
EscalonamentoFirst-In-First-Out(FIFO)
• O processo que chegar primeiro ao estado de pronto é o selecionado para execução.
• Algoritmo bastante simples, sendo necessária apenas uma fila, onde os processos que passam para o estado de pronto entram no seu final e são escalonados quando chegam ao seu início.
EscalonamentoFirst-In-First-Out(FIFO)
UCP
Estado deCriação
Estado deEspera
Fila dos processos no estado de Pronto
Estado deTérmino
EscalonamentoFirst-In-First-Out(FIFO)
• A seguir é possível comparar o uso do escalonamento FIFO em duas situações distintas, onde os processos A, B e C são criados no instante de tempo 0, com os tempos de processador 10, 4 e 3.
• A diferença entre os exemplos é o posicionamento dos processos na fila de pronto.
EscalonamentoFirst-In-First-Out(FIFO)
Tempo médio de espera dos processos = (7 + 0 + 4) / 3 = 3,7 u.t.
Tempo médio de espera dos processos = (0 + 10 + 14) / 3 = 8 u.t.
EscalonamentoFirst-In-First-Out(FIFO)
• Apesar de simples possui deficiências.– Impossibilidade de se prever quando um
processo terá sua execução iniciada, já que isso varia em função do tempo de execução dos demais processos e posicionados a sua frente.
– Processos ligados as CPU levam vantagens sobre processos E/S.
• É do tipo não-preemptivo.
EscalonamentoShortest-Job-First(SJF)
• Seleciona o processo que tiver o menor tempo de processador ainda por executar.
• Desta forma, o processo em estado de pronto que necessitar de menos tempo de CPU para terminar seu processamento éselecionado para execução.
EscalonamentoShortest-Job-First(SJF)
Processo A
Processo B
Processo C
3 7 17 u.t.
Tempo médio de espera dos processos = (7 + 3 + 0) / 3 = 3,3 u.t.
EscalonamentoShortest-Job-First(SJF)
• Para cada novo processo admitido no sistema, um tempo de processador era associado ao seu contexto de software.
• Como não é possível precisar previamente o tempo de processador para cada processo, uma estimativa era realizada com base em análises estatísticas de execuções passadas dos programas.
• Caso seja inferior o SO pode interromper a execução.
EscalonamentoShortest-Job-First(SJF)
• É do tipo não-preemptivo.• Vantagem sobre o FIFO, tempo médio,
porém pode ocorrer espera indefinida para processo com tempo de processador muito longo.
Escalonamento Cooperativo
• É uma implementação que busca aumentar o grau de multiprogramação em políticas de escalonamentos que não possuam mecanismos de preempção (FIFO - SJF).
• Neste caso, um processo em execução pode voluntariamente liberar o processador retornando à fila de pronto, possibilitando que um novo processo seja escalonado.
Escalonamento Cooperativo
• A principal característica está no fato de a liberação do processador ser uma tarefa realizada exclusivamente pelo processo em execução.
• Verifica periodicamente uma fila de mensagens para determinar se existem outros processos na fila de pronto.
• No caso de um processo não verificar a fila de mensagens, os demais não terão chance de ser executados.
• Exemplo: primeiros SO Windows.
Escalonamento Circular
• Round Robin Scheduling• Do tipo preemptivo, projetado
especialmente para sistemas de tempo compartilhado.
• Bastante semelhante ao FIFO; porém, quando um processo passa para o estado de execução, existe um tempo limite para o uso contínuo do processador denominado fatia de tempo (time-slice).
Escalonamento Circular
• Toda vez que um processo é escalonado para execução, uma nova fatia de tempo e concedida.
• Caso a fatia de tempo expire, o SO interrompe o processo em execução, salva seu contexto e direciona-o para o final da fila de pronto. (Preempção por tempo).
Escalonamento Circular
Preempção por tempo
UCP
Estado deCriação
Estado deEspera
Fila dos processos no estado de Pronto
Estado deTérmino
Escalonamento Circular
• O processo permanecerá no estado de execução até que termine seu processamento, voluntariamente passe para o estado de espera, ou que sua fatia de tempo expire, sofrendo, neste caso a preempção por tempo.
• O valor da fatia de tempo depende de cada SO e, em geral, varia entre 10 e 100 milissegundos.
Escalonamento Circular
• A principal vantagem e que um processo não monopoliza a CPU.
• Um problema presente nesta política e que processos ligados ao Processador são beneficiados no uso em relação aos ligados a E/S.
• Um refinamento deste e conhecido como escalonamento circular virtual.
Escalonamento Circular
Preempção por tempo
UCP
Estado deCriação
Fila dos processos no estado de Pronto
Estado deTérmino
Estado deEspera
Fila auxiliar
Escalonamento Circular
• Neste esquema, processos que saem do estado de espera vão para uma fila de pronto auxiliar.
• Processos da fila auxiliar possuem preferência no escalonamento em relação à fila de pronto, e o escalonador sóseleciona processos na fila de pronto quando a fila auxiliar estiver vazia.
Escalonamento por prioridades
• É do tipo preemptivo realizado com base em um valor associado a cada processo denominado prioridade de execução.
• Processos com maior prioridade no estado de pronto é sempre o escolhido para execução, e processos com valores iguais são escalonados seguindo o critério de FIFO.
• Não existe a idéia de fatia de tempo.
Escalonamento por prioridades
• A perda do uso do processador só ocorreráno caso de uma mudança voluntária para o estado de espera ou quando um processo de prioridade maior passa para o estado de pronto.
• Conhecido como preempção por prioridade.
Escalonamento por prioridades
UCP
Estado deTérmino
Filas dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Prioridade Pn
Estado deCriação
Estado deEspera
Preempção por prioridade
Escalonamento por prioridades
• Cada SO implementa sua faixa de valores para as prioridades de execução.
• Alguns SO associam as maiores prioridades a valores altos, enquanto outros utilizam valores baixos.
• OpenVMS - 0 a 31, onde 31 é a maior.• IBM-AIX - 0 a 127, onde 0 é a maior.
Escalonamento por prioridades
Processo A
Processo B
Processo C
3 13 17 u.t.
ProcessoTempo de
processador(u.t.)
A
B
C
10
4
3
Prioridade
2
1
3
Escalonamento por prioridades
• A prioridade de execução é uma característica do contexto de software de um processo e pode ser classificada como estática ou dinâmica.– A prioridade estática não tem o seu valor
alterado durante a existência do processo– A prioridade dinâmica pode ser ajustada de
acordo com critérios definidos pelo SO.
Escalonamento por prioridades
• Um dos principais problemas no escalonamento por prioridades é a espera indefinida.– Processo de baixa prioridade podem não ser
escalonados, permanecendo indefinidamente na fila de pronto.
– Possível solução em sistemas de prioridade dinâmica, é a técnica de aging, que incrementa gradualmente a prioridade de processos que permanecem por muito tempo na fila de pronto.
EscalonamentoCircular por prioridades
• Implementa o conceito de fatia de tempo e de prioridade de execução associada a cada processo.
• Um processo permanece no estado de execução até que termine seu processamento, voluntariamente passe para o estado de espera ou sofra uma preempção por tempo ou prioridade.
EscalonamentoCircular por prioridades
• Principal vantagem desse escalonamento é permitir o melhor balanceamento no uso da CPU, com a possibilidade de diferenciar o grau de importância dos processos.
• Este tipo de escalonamento é amplamente utilizado em sistemas de tempo compartilhado.
Escalonamentopor Múltiplas Filas
• Existem diversas filas de processos no estado de pronto, cada qual com uma prioridade específica.
• Os processos são associados às filas em função de características próprias, como importância para a aplicação, tipo de processamento ou área de memória necessária.
Escalonamentopor Múltiplas Filas
• A principal vantagem de múltiplas filas é a possibilidade da convivência de mecanismos de escalonamento distintos.
• Cada fila possui um mecanismo próprio, permitindo que alguns processos sejam escalonados pelo mecanismo FIFO, enquanto outros pelo circular.
• Neste mecanismo, o processo não possui prioridade, ficando esta característica associada a fila.
Escalonamentopor Múltiplas Filas
UCP
Fila de processos do sistema
Fila de processos interativos
Fila de processos batch
Maiorprioridade
Menorprioridade
Uma desvantagem deste escalonamento é que, no caso de um processo alterar seu comportamento no decorrer do tempo, o processo não poderá ser redirecionado para uma outra fila mais adequada.
Escalonamento por MúltiplasFilas com Realimentação
• É semelhante ao escalonamento por múltiplas filas, porém os processos porém trocar de fila durante seu processamento.
• Sua grande vantagem é permitir ao SO identificar dinamicamente o comportamento de cada processo, direcionando-o para fila com prioridade de execução e mecanismo de escalonamento mais adequados ao longo de seu processamento.
Escalonamento por MúltiplasFilas com Realimentação
• Esse esquema permite que os processos sejam redirecionados entre as diversas filas, fazendo com que o SO implemente um mecanismo de ajuste dinâmico denominado mecanismo adaptativo.
• Os processos não são previamente associados às filas de pronto, e, sim, direcionados pelo sistema para as filas existentes com base no seu comportamento.
Escalonamento por MúltiplasFilas com Realimentação
UCP
Fila 1 (FIFO Adaptado)
Preempção por tempo
Fila 2 (FIFO Adaptado)
Preempção por tempo
Fila 3 (FIFO Adaptado)
Preempção por tempo
Fila n (Circular)
Preempção por tempo
Men
orPr
iori
dade
Mai
orPr
iori
dade
Mai
or fa
tiade
tem
poM
enor
fatia
de te
mpo