Escalonamento de Processo Sistemas Operacionais - Prof. Dr. Márcio Andrey Teixeira

Prévia do material em texto

Escalonamento de Processo
Sistemas Operacionais
Prof. Dr. Márcio Andrey Teixeira
 
Quando um computador é multiprogramado, ele muitas vezes tem variados 
processos que competem pela CPU ao mesmo tempo;
Essa situação ocorre sempre que dois ou mais processos estão 
simultaneamente no estado de pronto; 
A parte do SO que faz a escolha de qual processo deve ser executado é 
chamado de escalonador, e o algoritmo que é usado é chamado de 
algoritmo de escalonamento;
Comportamento do processo
A figura abaixo mostra como os programas se comportam em relação a 
utilização da CPU
a)a)
b)
Espera pela E/S
 
Quando escalonar
Quando se deve escalonar ???
1 – Quando se cria um novo processo !!!
2 – No término de um processo !!!
3 – Quando um processo é bloqueado !!!!
4 – Quando um processo executa o evento de E/S !!!
O algoritmo de escalonamento pode ser:
Não preemptivo: O processo executa até o fim, sem ser interrompido;
Preemptivo: O processo executa em fatias de tempo (quantum) 
determinado pelo sistema operacional. 
 
Em sistemas multiprogramados, múltiplos processos são mantidos na memória 
principal, cada qual alternando o uso do processados. Como fator principal da 
multiprogramação, quatro tipo de escalonamento são possíveis:
Long−term Scheduling: Determina os processos que serão admitidos no sistema.
Medium−term Scheduling: Determina a adição de um número de processos que estão 
parcialmente ou completamente na memória
Short−term Scheduling: Determina quais processos serão executados pelo processador
Long−term Scheduling e Medium−term Scheduling estão diretamente relacionados 
com aspectos de performance, ou seja grau de multiprogramação. É utilizado quando o 
processo deverá ser admitido no sistema e quando tomar decisão de trocar parte do 
processo da memória primária para a memória secundária.
Short−term Scheduling aborda com alto grau de performance o escalonamento de 
processos que estão pronto para executar na memória principal.
 
A Figura abaixo mostra um exemplo da utilização dos tipos de algoritmos de 
escalonamento:
O objetivo do escalonador é atribuir processos para serem executados pelos 
processadores de modo a atingir parâmetros de performance, tais como tempo 
de resposta, vazão e eficiência do processados
 
Reorganização dos tipos de algoritmos de escalonamento existente:
 
O escalonamento afeta a performance do sistema, pois determina quais 
processos deverão esperar e quais deverão progredir. Isso envolve o 
gerenciamento de filas, exemplo:
 
Long−term Scheduling: Determina quais programas serão admitidos pelo sistema para o 
processamento, ou seja, controla o grau da multiprogramação. 
 - Em alguns sistemas, um processo que acabou de ser criado inicia-se na memória 
secundária e, neste caso, será adicionado a fila do escalonador intermediário.
 - Em sistemas operacionais de processamento em lote, processos recém criados são 
direcionados para o disco e mantidos numa fila de lote.
 - A decisão de quando criar um novo processo é geralmente tomada como resultado do 
grau de multiprogramação. Quanto mais processos existirem menor é o tempo da tomada 
para cada um ser executado, pois mais processos competem pelos recursos .
 - Em termos de frequência de execução, Long term Scheduler desempenha o 
gerenciamento grosseiro, e portanto, é executado com baixa frequência.
 
Medium-term Scheduling: Responsável pela troca (swapping) entre memória 
secundária e memória principal.
 - Executa com mais freqência que o anterior para o gerenciamento de swapping.
Short term Scheduling: Também conhecido como dispatcher, é executado muito 
frequêntemente sendo responsável pela tomada de descisão de qual processo a ser 
executado (próximo processo).
- Este escalonamento é executado quando da ocorrência de um evento que conduza o 
bloqueio do processo corrente, cria-se uma oportunidade de preenpção em favor de outro 
processo. Exemplos desses eventos são:
- Clock da CPU;
- Interrupções de I/O;
- Chamadas do sistema operacional;
- O Short term Scheduling procura alocar o tempo do processador de tal maneira a 
otmizar um ou mais aspectos do comportamento do sistema. 
 
Os critérios utilizados para isso são distinguidos em: critérios orientados ao sistema e 
critérios orientados aos usuários.
Critérios orientados aos usuários: Estão relacionados como os usuários ou os 
processos quantificam o comportamento do sistema:
- Response Time: Para um processo interativo, este é o tempo desde a submissão de 
uma requisição até a sua resposta. A disciplina de escalonamento deverá maximizar o 
número de usuários interativos em um tempo de resposta aceitável;
- Turnaround time: Este é o intervalo de tempo entre a submissão de um processo e o 
seu término de execução. Este tempo inclui o tempo atual de execução mais o tempo de 
espera pelo recurso, incluindo a CPU. Está é a média apropriada de um Job em Lote;
- Deadlines: Quando um deadline de um processo pode ser especificado, a disciplina do 
algoritmo de escalonamento deve maximizar a porcentagem da execução dos deadlines 
existentes;
 
Critérios orientados ao sistema: Estão relacionados o comportamento do sistema em si.
- Throughput: A politica de escalonamento deve tentar maximizar o número de processos 
 completados por unidade de tempo. Esta é a média de quanto trabalho iniciado é 
executado;
- Processor utilization: Porcentagem de tempo em que o processador está ocupado. Em 
um sistema compartilhado, este é um critério significante;
- Balanceamento de recursos: A politica de escalonamento deve manter os recursos do 
sistema ocupado;
- Priority: A política de escalonamento deve favorecer os processos com maiores 
prioridades;
 
Os critérios citados são independente, sendo complicado otimizá-los em conjunto e 
simultaneamente.
Ex:. Para prover um bom tempo de resposta, pode exigir do algoritmo de escalonamento 
que freqüentemente troque o contexto entre processos, o que aumenta o overhead do 
sistema, ou seja, contribui para reduzir a vazão dos processos.
Na maioria dos sistemas operacionais interativos, o tempo de resposta é o critério principal;
Em muitos sistemas, cada processo é atribuído uma prioridade e o escalonador irá sempre 
escolher com mais alta prioridade sobre o de menor prioridade;
A figura a seguir ilustra um exemplo de escalonamento com filas de prioridade
 
Um dos problemas deste algoritmo é que processos com baixa prioridade podem chegar a 
não serem executados;
Solução: alterar a prioridade do processo de acordo com seu histórico de execução e em 
função do tempo;
 
Exemplo de um Overhead do sistema
 
Categorias de escalonamento de processo 
Para ambientes diferentes de sistemas operacionais, são necessários tipos 
diferentes de algoritmos de escalonamento. Esses ambientes podem ser:
1. Lote;
2. Interativo (propósito geral);
3. Tempo real;
Em sistemas em Lote, não há terminal com usuários esperando impacientes 
por uma resposta rápida. Conseqüentemente, algoritmos com longo 
intervalo de tempo para cada processo em geral são aceitáveis.
Em sistemas com usuários interativos, a preempção é para evitar que um 
processo se aposse da CPU, e com isso negue serviço aos outros. 
Em sistemas com restrição de tempo real, a preempção é estranhamente, 
desnecessária algumas vezes, pois os processos sabem que não podem 
executar por longos períodos de tempo e em geral fazem seus trabalhos e 
bloqueiam rapidamente. 
 
Categorias de escalonamento de processo 
Um bom algoritmo de escalonamento é projetado de acordo com os critérios de 
utilização já mencionados, isso dependendo o ambiente do sistema operacional 
(em lote, interativo ou tempo real), mas existem alguns critériosque são 
desejáveis para todos os casos, exemplo:
Para todos os ambiente: 
- Justiça: Dar a cada processo uma porção justa da CPU;
- Aplicação da política: verificar se a política estabelecida é cumprida;
- Equilíbrio: manter ocupada todas as partes do sistema;
Sistemas em lote: 
- Vazão (Througput): Maximizar o número de jobs por hora;
- Tempo de retorno: Minimizar o tempo de entre a submissão e o término 
da execução;
- Utilização da CPU: manter a CPU ocupada todo o tempo;
 
- Tempo de resposta: responder rapidamente às requisições;
- Proporcionalidade: Satisfazer as perspectivas dos usuários;
Sistemas interativos: 
- Cumprimento dos prazos: evitar a perda de dados;
- Previsibilidade: evitar a degradação da qualidade em sistemas 
multimídias
Sistemas de tempo real: 
 
Algoritmos de escalonamento (Lote)
Primeiro a chegar, primeiro a ser servido
O algoritmo (first come, first served – FCFS) possui as seguintes 
características:
 - Com esse algoritmo, a CPU é atribuída aos processos na ordem em que 
eles a requisitam. Basicamente há uma fila única de processos prontos;
 - Quando o processo requisita a CPU ele é executado. Quando chega mais 
processos, estes são inseridos em uma fila.
 
Considere a seguinte tabela 
Processo Tempo de 
chegada
Tempo de 
serviço
A
B
C
D
E
0
2
4
6
8
3
6
4
5
2
 
Primeiro a chegar, primeiro a ser servido
Grande vantagem desse algoritmo é que: é de fácil entendimento e de fácil 
implementação.
Maior desvantagem desse algoritmo: quando tem-se programas orientados a 
CPU e programas orientados a E/S. Por exemplo, um programa orientado a 
CPU executa 1 segundo, e um programa orientado a E/S que executa pouco 
tempo de CPU, mas necessita de executar mil leituras no disco antes de 
terminar;
Em um algoritmo com preempção a cada 10 milessegundos (em vez de cada 
um segundo), o processo terminaria em 10 segundos;
Job mais curto primeiro
Vejamos um outro algoritmo em lote não preemptivo que supõe como 
previamente conhecido todos os tempos de execução.
 
Job mais curto primeiro
Considere a seguinte seqüência de execução !
A B C D
8 4 4 4
B C D A
4 4 4 8
Tempo de retorno: 
A = 8;
B = 12;
C = 16;
D = 20 ;
Tempo médio 
(A + B + C + D) / 4
 
Processo Tempo de 
chegada
Tempo de 
serviço
P1
P2
P3
P4
P5
0
2
4
6
8
3
6
4
5
2
Exemplo. Considere a tabela abaixo.
Job mais curto primeiro
 
Próximo de menor tempo restante
Uma versão preemptiva do FCFS é o próximo menor tempo restante. Com 
este algoritmo, o escalonador sempre escolhe o processo cujo o tempo de 
execução restante seja o menor.
Novamente, o tempo de execução deverá ser previamente conhecido. 
Quando chega um novo job, seu tempo total é comparado ao tempo restante 
do processo em curso. Se para terminar, o novo job precisar de menos tempo 
que o processo atual, então esse será suspenso e o novo job será iniciado. 
 
Algoritmos de escalonamento interativo
Escalonamento por alternância circular (Round Robin)
 - Um dos algoritmos mais antigos
 - A cada processo é atribuído um intervalo de tempo, o quantum, no qual 
ele é permitido executar;
 - Se no final do quantum o processo não terminou, a CPU sofre uma 
preempção e outro processo entra para executar;
 - Quando um processo termina o seu quantum, ele é colocado no final da 
fila. Exemplo:
Escalonamento por alternância circular (Round Robin)
 
 - O que interessa em um escalonador circular é o tamanho do quantum.
 A alternância de um processo para outro requer uma certa quantidade de 
tempo (Troca de contexto).
 Vamos supor que para cada processo, a troca de contexto dure 1ms. 
Suponha também que o quantum é de 4 ms. Com este exemplo, após 4 ms 
de trabalho, a CPU gastará 1 ms para alternar o processo;
Nesse exemplo, 20% da CPU será gasta com a troca de contexto dos 
processos gerando um overhead muito alto.
Para melhorar a eficiência, vamos supor um quantum de 100 ms, agora o 
tempo gasto com o overhead é de 1% do tempo da CPU;
Considere o que pode acontecer quando 10 usuários de um sistema interativo 
apertem a tecla <ENTER> quase ao mesmo tempo. Dez processos serão 
alocados na lista de pronto para executar.
O que acontecerá ?????????
Um quantum entre 25 a 50 ms é bastante razoável
 
 A Figura a seguir ilustra um a execução do escalonamento RR com quantum 
de 1 e 4 ms.
Processo Tempo de 
chegada
Tempo de 
serviço
P1
P2
P3
P4
P5
0
2
4
6
8
3
6
4
5
2
 
Escalonamento por prioridades
 - A cada processo é atribuído uma prioridade, e o processo com maior 
prioridade é executado primeiro;
 - Exemplo, um processo como um deamon de correio eletrônico deve ter 
menor prioridade que um processo que atualiza um vídeo na tela;
 O escalonamento circular pressupõe que todos os processos são igualmente 
importantes. Para que haja diferenças externas de execução, foi criado o 
escalonamento por prioridade. A idéia básica é simples:
 Mesmo em um PC comum com um único proprietário, pode haver múltiplos 
processos com prioridades diferentes.
 Para evitar que processos de alta prioridade executem infinitamente, o 
escalonador pode reduzir a prioridade do processo a cada execução do 
mesmo.
As prioridades são atribuídas pelo S.O. No Linux, o comando nice altera a 
prioridade de um processo de acordo com que o usuário desejar. 
 
Muitas vezes é conveniente agrupar processos em classes de prioridade e 
usar o escalonamento de prioridade entre as classes, contudo em cada classe 
usar o escalonamento circular.
A figura a seguir mostra um exemplo com quatro classes de prioridades:
 
Outro exemplo de escalonamento com classes de prioridades.
 
Medidas de Desempenho dos algoritmos de escalonamento
Considere as seguintes itens:
Tempo de chegada: Tempo em que o processo entra no sistema;
Tempo de serviço: Tempo total de processamento;
Turneraund Time: Intervalo entre a entrada do processo no sistema e o seu 
término;
T
t
 / T
s
: Tempo de desempenho do processo;
Calcular o desempenho dos algoritmos de escalonamento utilizando a tabela
 abaixo:
Processo Tempo de 
chegada
Tempo de 
serviço
P1
P2
P3
P4
P5
0
2
4
6
8
3
6
4
5
2
 
Medidas de Desempenho dos algoritmos de escalonamento
 
Determine as medidas de tempo para os algoritmos abaixo:
Job mais curto primeiro
 
Determine as medidas de tempo para os algoritmos abaixo:
Round Roubin: Q=1; Q=4
 
Escalonamento utilizado pelo sistema 
operacional Linux 
O problema básico de escalonamento em sistemas operacionais é como satisfazer 
simultaneamente objetivos conflitantes: tempo de resposta rápido, bom throughput para 
processos background, evitar postergação indefinida, conciliar processos de alta 
prioridade com de baixa prioridade, etc. (Determinar a política de escalonamento)
Os sistemas operacionais Linux implementam o escalonamento da seguinte forma:
Os processos são divididos em três grandes classes: processos interativos, 
processos batch e processos tempo real.
Em cada classe, os processos podem ser ainda subdivididos em I/O bound ou CPU 
bound de acordo com a proporção de tempo que ficam esperando por operações de 
entrada e saída ou utilizando o processador.
O escalonador do Linux não distingue processos interativos de processos batch, 
diferenciando-os apenas dos processos tempo real. Como todos os outros 
escalonadores UNIX, o escalonador Linux privilegia os processos I/O bound em relação 
aos CPU bound de forma a oferecer um melhor tempo de resposta às aplicações 
interativas.
 
Escalonamento utilizado pelo sistemaoperacional Linux 
O escalonador do Linux é baseado em time-sharing, ou seja, o tempo do processador é 
dividido em fatias de tempo (quantum) as quais são alocadas aos processos. Se, 
durante a execução de um processo, o quantum é esgotado, um novo processo é 
selecionado para execução, provocando então uma troca de contexto
Esse procedimento é completamente transparente ao processo e baseia-se em 
interrupções de tempo. Esse comportamento confere ao Linux um escalonamento do 
tipo preemptivo.
Outra característica do escalonador Linux é a existência de prioridades dinâmicas. O 
escalonador do Linux monitora o comportamento de um processo e ajusta 
dinamicamente sua prioridade, visando a equalizar o uso do processador entre os 
processos.
Processos que recentemente ocuparam o processador durante um período de tempo 
considerado “longo” têm sua prioridade reduzida. De forma análoga, aqueles que estão 
há muito tempo sem executar recebem um aumento na sua prioridade, sendo então 
beneficiados em novas operações de escalonamento.
As prioridades dos processos podem ser modificadas pelo usuário, utilizando o comando 
nice. As prioridades dos processos variam entre 20 e -19, sendo esta a prioridade mais 
alta.
 
Escalonamento utilizado pelo sistema operacional Linux 
Na realidade, o sistema Linux trabalha com dois tipos de prioridades: estática e 
dinâmica. As prioridades estáticas são utilizadas exclusivamente por processos de 
tempo real e, neste caso, a prioridade do processo tempo real é definida pelo usuário e 
não é modificada pelo escalonador.
O esquema de prioridades dinâmicas é aplicado aos processos interativos e batch. Aqui, 
a prioridade é calculada, considerando-se a prioridade base do processo e a quantidade 
de tempo restante em seu quantum.
O escalonador do Linux executa os processos de prioridade dinâmica apenas quando 
não há processos de tempo real. Em outros termos, os processos de prioridade estática 
recebem uma prioridade maior que os processos de prioridade dinâmica. Para 
selecionar um processo para execução, o escalonador do Linux prevê três políticas 
diferentes :
 
Escalonamento utilizado pelo sistema operacional Linux 
SCHED_FIFO: Essa política é valida apenas para os processos de tempo real. Na 
criação, o descritor do processo é inserido no final da fila correspondente à sua 
prioridade. Nessa política, quando um processo é alocado ao processador, ele executa
até que uma de três situações ocorra: (i) um processo de tempo real de prioridade 
superior torna-se apto a executar; (ii) o processo libera espontaneamente o processador
para processos de prioridade igual à sua; (iii) o processo termina, ou bloqueia-se, em 
uma operação de entrada e saída ou de sincronização.
SCHED_RR: Na criação, o descritor do processo é inserido no final da fila 
correspondente à sua prioridade. Quando um processo é alocado ao processador, ele 
executa até que uma de quatro situações ocorra: (i) seu período de execução (quantum) 
tenha se esgotado nesse caso o processo é inserido no final de sua fila de prioridade; 
(ii) um processo de prioridade superior torna-se apto a executar; (iii) o processo libera 
espontaneamente o processador para processos de prioridade igual a sua; (iv) o 
processo termina, ou bloqueia-se, em uma operação de entrada e saída ou de 
sincronização. Essa política também só é válida para processos de tempo real.
 
Escalonamento utilizado pelo sistema operacional Linux 
Se o processo a ser desbloqueado possuir uma prioridade mais alta, o escalonador 
é acionado, e ocorre uma troca de processo.
- A terceira, e última forma de execução lazy, é quando um processo explicitamente 
invoca o escalonador através de uma chamada de sistema do tipo yield. Essa 
chamada de sistema permite a um processo “passar sua vez de execução” a outro 
processo, e, para isso, parece claro, é necessário executar o escalonador.
 
Escalonamento utilizado pelo sistema operacional Linux 
SCHED_OTHER: Corresponde a um esquema de filas multinível de prioridades
dinâmicas com timesharing. Os processo interativos e batch recaem nessa categoria.
O escalonador do Linux é executado a partir de duas formas diferentes:
- A primeira é a forma direta através de uma chamada explícita à rotina que implementa 
o escalonador. Essa é a maneira utilizada pelo núcleo do Linux quando, por exemplo, 
detecta que um processo deverá ser bloqueado em decorrência de uma operação de 
entrada e saída ou de sincronização.
- A segunda forma, denominada de lazy, também é conseqüência do procedimento de 
escalonamento, ocorrendo tipicamente em uma das duas situações:
- A primeira dessas situações é a rotina de tratamento de interrupção de tempo que 
atualiza os temporizadores e realiza a contabilização de tempo por processo. Essa 
rotina, ao detectar que um processo esgotou seu quantum de execução aciona o 
escalonador para que seja efetuada uma troca de processo.
- A segunda situação ocorre quando um processo de mais alta prioridade é 
desbloqueado pela ocorrência do evento que esperava. A parte do código que efetua 
o desbloqueio, isto é, trata os eventos de sincronização e de entrada e saída, 
consulta a prioridade do processo atualmente em execução e compara-a com a do 
processo que será desbloqueado.
 
Escalonamento utilizado pelo sistema operacional 
Windows 2000
O escalonador do Windows 2000 é preemptivo com prioridades. As prioridades são 
organizadas em duas classes: tempo real e variável.
Cada classe possui 16 níveis de prioridades, sendo que as threads da classe tempo real 
têm precedência sobre as threads da classe variável, isto é, sempre que não houver 
processador disponível, uma thread de classe variável é preemptada em favor de uma 
thread da classe tempo real.
Todas as threads prontas para executar são mantidas em estruturas de filas associadas 
a prioridades em cada uma das classes. Cada fila é atendida por uma política Round-
robin.
A atribuição de prioridades a threads é diferente para cada uma das classes. Enquanto 
na classe de tempo real, as threads possuem prioridade fixa, determinada no momento 
de sua criação, as threads da classe variável têm suas prioridades atribuídas de forma 
dinâmica (por isso o nome de “variável” para essa classe).
 
Escalonamento utilizado pelo sistema operacional Windows 
2000
Dessa forma, uma thread de tempo real, quando criada, recebe uma prioridade e será 
sempre inserida na fila dessa prioridade, ao passo que uma thread da classe variável 
poderá migrar entre as diferentes filas de prioridades.
Em outros termos, o Windows 2000 implementa um esquema de múltiplas filas para as 
threads da classe real e múltiplas filas com realimentação para as threads da classe 
variável. A figura a seguir ilustra o sistema de prioridades de Wndows 2000.
 
Escalonamento utilizado pelo sistema operacional Windows 
2000
Na classe variável, a prioridade de uma thread é estabelecida a partir de dois 
parâmetros, um vínculado à própria thread e outro, ao processo a que pertence.
Um objeto processo, durante sua criação, recebe um valor, entre zero e 15 inclusive, 
para sua prioridade de base. Cada thread recebe uma prioridade inicial, variando 2 
unidades acima ou abaixo da prioridade de base do processo, que indica sua prioridade 
relativa dentro desse processo.
A prioridade de uma thread varia durante a sua vida, mas nunca assumirá valores 
inferiores a sua prioridade base nem superiores a 15. O critério empregado para variar a 
prioridade de uma thread é o tempo de utilização do processador.
Se a thread for preemptada por ter executado durante todo o quantum de tempo que lhe 
foi atribuído, o escalonador do Windows 2000 diminui sua prioridade; caso contrário, sua 
prioridade é aumentada. Em outros termos, o escalonador do Windows 2000 tende a 
atribuir prioridades mais elevadaspara threads do tipo I/O bound.
 
Escalonamento utilizado pelo sistema operacional Windows 
2000
Em máquinas monoprocessadoras, a thread de mais alta prioridade está sempre ativa a 
menos que esteja bloqueada esperando por um evento (E/S ou sincronização). Caso 
exista mais de uma thread com um mesmo nível de prioridade o processador é 
compartilhado de forma round-robin entre essas threads.
Em um sistema multiprocessador com n processadores, as threads de mais alta 
prioridade executam nos n-1 processadores extras. As threads de mais baixa prioridade 
disputam o processador restante.
	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 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43