Sistemas Operacionais
Escalonamento de Processo
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
simultaneamente no estado de pronto;
dois
ou
mais
processos
estão
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)
Espera pela E/S
b)
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érios que 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;
Sistemas interativos:
- Tempo de resposta: responder rapidamente às requisições;
- Proporcionalidade: Satisfazer as perspectivas dos usuários;
Sistemas de tempo real:
- Cumprimento dos prazos: evitar a perda de dados;
- Previsibilidade: evitar a degradação da qualidade em sistemas
multimídias
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
0
3
B
2
6
C
4
4
D
6
5
E
8
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 !
8
4
4
4
4
4
4
8
A
B
C
D
B
C
D
A
Tempo de retorno:
A = 8;
B = 12;
C = 16;
D = 20 ;
Tempo médio
(A + B + C + D) / 4
Exemplo. Considere a tabela abaixo.
Tempo de
chegada
Tempo de
serviço
P1
0
3
P2
2
6
P3
4
4
P4
6
5
P5
8
2
Processo
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:
- 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.
Tempo de
chegada
Tempo de
serviço
P1
0
3
P2
2
6
P3
4
4
P4
6
5
P5
8
2
Processo
Escalonamento por prioridades
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:
- A cada processo é atribuído uma prioridade, e o processo com maior
prioridade é executado primeiro;
Mesmo em um PC comum com um único proprietário, pode haver múltiplos
processos com prioridades diferentes.
- Exemplo, um processo como um deamon de correio eletrônico deve ter
menor prioridade que um processo que atualiza um vídeo na tela;
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;
Tt / Ts: Tempo de desempenho do processo;
Calcular o desempenho dos algoritmos de escalonamento utilizando a tabela
abaixo:
Tempo de
chegada
Tempo de
serviço
P1
0
3
P2
2
6
P3
4
4
P4
6
5
P5
8
2
Processo
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 sistema operacional 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 Roundrobin.
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 elevadas para 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.