Escalonamento de Processos - Slides

Prévia do material em texto

Tópicos
● Conceitos
● Níveis de escalonamento
● Tipos de sistemas
● Escalonamento em sistemas em lote
● Escalonamento em sistemas interativos
● Outros tópicos
● Escalonamento em sistemas de tempo real
● Escalonamento de threads
 
Conceitos
● O escalonador é a entidade do sistema operacional 
responsável por selecionar um processo apto/pronto
para executar no processador
● O objetivo é dividir o tempo do processador de forma 
“justa” entre os processos aptos a executar
● Além de escolher o processo “certo”, o escalonador deve se 
preocupar em fazer uso eficiente da CPU
– Lembrando, chaveamento de contexto (ou seja, escalonamento de 
processos) é uma tarefa administrativa “cara” e deve ser minimizada
● O escalonador é necessário em diferentes tipos de 
sistemas multiprogramados: em lote, tempo 
compartilhado e tempo real
● Requisitos e restrições diferentes em relação a utilização da 
CPU
 
Conceitos (cont.)
● Tipicamente, os processos alternam surtos de 
uso da CPU com períodos de espera por E/S
(a) um processo orientado à CPU
(b) um processo orientado à E/S
 
Conceitos (cont.)
● Situações típicas para execução do escalonador
● Sempre que a CPU estiver livre e houver processos aptos a 
executar
● Criação e término de processos
● Um processo de mais alta prioridade ficar apto a executar
● Interrupção de tempo
– Processo executou por um período de tempo máximo permitido
● Interrupção de dispositivos de entrada e saída
● Interrupção por falta de página (segmento) em memória
– Endereço acessado não está carregado na memória (memória 
virtual)
● Interrupção por erros
Fatores como o escalonador ser preemptivo ou não e considerar prioridades ou 
não vão definir quando o mesmo deve atuar
 
Conceitos (cont.)
● O escalonamento está divido em duas partes:
● Escalonador – define qual processo deve executar
● Expedidor (dispatcher) – efetua a troca de contexto
● Níveis de escalonamento:
● Longo prazo
● Médio prazo
● Curto prazo
 
Conceitos (cont.)
● Escalonamento de longo prazo:
● É executado quando um novo processo é criado
● Determina quando um processo novo passa a ser 
considerado no sistema, isto é, quando após sua 
criação ele passa a ser apto
– Controle de admissão
● Controla o grau de multiprogramação do sistema
– Quanto maior o número de processos ativos, menor a 
porcentagem de tempo de uso do processador por 
processo
 
Conceitos (cont.)
● Escalonamento de médio prazo:
● Associado a gerência de memória
– Participa do mecanismo de troca (swapping), escolhendo 
os processos que devem ir para o disco ou serem 
trazidos para a memória
● Suporte adicional a multiprogramação
– Grau de multiprogramação efetiva (diferencia aptos de 
aptos-suspensos e bloqueados de bloqueados-
suspensos)
 
Conceitos (cont.)
● Escalonamento de curto prazo:
● É o mais importante e, geralmente, o mais atuante
● Determina qual processo apto deverá utilizar o 
processador
● É executado quando ocorre eventos importantes:
– Interrupção de relógio
– Interrupção de entrada/saída
– Chamadas de sistemas
– Sinais (interrupção software)
 
Conceitos (cont.)
● Níveis de escalonamento
CPU
Escalonador de 
médio prazo
Processos
Escalonador
de longo prazo
Interrupção de tempo
Fila de aptos
Fila de suspensos (apto)
Filas de suspensos (bloqueado)
Fila de bloqueados
Evento Espera por evento
Término
Escalonador de
curto prazo
 
Conceitos (cont.)
● Um vez escalonado, o processo utiliza o 
processador até que:
● Não preemptivo:
– Término de execução do processo
– Execução de uma requisição de entrada/saída ou 
sincronização
– Liberação voluntária do processador a outro processo
● Preemptivo:
– Término de execução do processo
– Execução de uma requisição de entrada/saída ou 
sincronização
– Liberação voluntária do processador a outro processo
– Interrupção de relógio
– Processo de mais alta prioridade esteja pronto para executar
 
Conceitos (cont.)
● Ambientes diferentes, demandam diferentes 
algoritmos de escalonamento
● Diferentes áreas de aplicação e diferentes tipos de 
SOs têm objetivos diferentes
● Em termos de escalonamentos, três ambientes se 
destacam:
– Em lote
– Interativo
– Tempo real
 
Conceitos (cont.)
● Sistemas em lote
● Ainda são amplamente usados em ambientes 
corporativos
– Exemplos: folhas de pagamento, estoque, contas a 
pagar, cálculo de juros (em bancos), processamento de 
pedidos indenização (em companhias de seguros), 
mineração de dados, etc.
● Não há demanda por interatividade
● Algoritmos não preemptivos ou preemptivo com 
longo intervalo de tempo para cada processo são 
aceitáveis
 
Conceitos (cont.)
● Sistemas interativos
● A preempção é essencial para evitar que um 
processo se aposse da CPU
– Minimiza os problemas causados por programas mal-
comportados ou defeituosos
● Além dos computadores pessoais, servidores que 
atendem a múltiplos usuários remotos também se 
enquadram nessa categoria
 
Conceitos (cont.)
● Sistemas de tempo real
● Em geral, são sistemas de propósito específico, 
permitindo assumir algumas premissas:
– Os processos sabem que não podem executar por 
longos períodos, portanto fazem seu trabalho e 
bloqueiam rapidamente
● Em determinados cenários, a preempção pode ser até
desnecessária
– Os processos visam o progresso da aplicação, ou seja, 
são cooperativos
 
Conceitos (cont.)
● Objetivos de um algoritmo de escalonamento
 
Escalonamento em sistemas em lote
● Algoritmos
● Primeiro a chegar, primeiro a ser servido (First-
Come, First-Served – FCFS ou First-In, First-Out – 
FIFO)
● Tarefa mais curta primeiro (Shortest Job First – SJF 
ou Shortest Process Next – SPN)
● Próximo de menor tempo restante (Shortest 
Remaining Time – SRT)
 
Escalonamento em sistemas em lote – 
FCFS
● Simples de implementar 
● É apenas uma fila
● Funcionamento:
● Processos que se tornam aptos são inseridos no 
final da fila
● Processo que está no início da fila é o próximo a
executar
● Processo executa até que:
– Libere explicitamente o processador
– Realize uma chamada de sistema (bloqueado)
– Termine sua execução
 
Escalonamento em sistemas em lote – 
FCFS (cont.)
● Desvantagem:
● Prejudica processos que fazem muitas operações 
de E/S
● Tempo médio de espera na fila do exemplo abaixo:
– Ordem A-B-C-D = (0 + 12 + 20 + 35 ) / 4 = 16.75 u.t.
A
0 12 20 35 40
B
C
D
Processo
A
B
C
D
Tempo
12
8
15
5
 
Escalonamento em sistemas em lote – 
SJF
● Motivado pelo fato que o menor tempo de 
médio é obtido quando se executa primeiro os 
processos de menor ciclo de processador (E/S 
intensiva)
● Tempo médio de espera na fila do exemplo abaixo:
– Ordem D-B-A-C = (0 + 5 + 13 + 25) / 4 = 10.75 u.t
A
0 40
B
C
D
5 13 25
Processo
A
B
C
D
Tempo
12
8
15
5
 
Escalonamento em sistemas em lote – 
SJF (cont.)
● Fornece o menor tempo médio de espera para 
um conjunto de processos
● Processos do tipo E/S intensiva são favorecidos
● Apresenta algumas dificuldades:
● É necessário que as tarefas estejam disponíveis
– Se os tempos de chegada são diferentes, o algoritmo 
não garante a melhor escolha
● Determinar o tempo do próximo ciclo de CPU de 
cada processo, ou seja, durante quanto tempo o 
processo vai utilizar a CPU
– Porém, é possível utilizar um preditor simples para 
estimar esse tempo
 
Escalonamento em sistemas em lote – 
SJF (cont.)
● Usando um preditor simples
● Média Móvel Exponencialmente Ponderada (EWMA 
– Exponentially Weighted Moving Average)
– Se baseia nos valores anteriores para estimaro próximo 
valor, da seguinte forma:
Tn+1 = a . tn + (1 – a) . Tn
Tn+1 = valor estimado para a próxima amostra
Tn = média exponencialmente ponderada das amostras 
anteriores
tn = amostra atual
a = parâmetro de ajuste do peso a ser dado a amostra atual e 
ao histórico das amostras, sendo que 0 ≤ a ≤ 1
 
Escalonamento em sistemas em lote – 
SJF (cont.)
● Ciclo de CPU (parâmetros: a = 0.5 e T0=10)
● Real: 6 4 6 4 13 13 13 13
● Previsto: 10 8 6 6 5 9 11 12
0
2
4
6
8
10
12
14
0 1 2 3 4 5 6 7
Real
Previsto
 
Escalonamento em sistemas em lote – 
SRT
● Versão preemptiva do SJF
● O escalonador escolhe o processo cujo tempo de 
execução restante seja o menor
– Novamente, o tempo de execução deve ser previamente 
conhecido (ou estimado)
● Quando chega um novo processo, seu tempo total 
é comparado ao tempo restante do processo em 
curso
– Se o novo processo precisar de menos tempo que o 
processo corrente, então esse será suspenso e o novo 
processo começa a ser executado
● Não é afetado por tempos de chegada diferentes 
entre os processos
 
Escalonamento em sistemas interativos
● Algoritmos
● Chaveamento circular (Round-Robin)
● Por prioridades
● Há vários outros na literatura: próximo processo 
mais curto, escalonamento garantido,
escalonamento por loteria, escalonamento por 
fração justa, etc.
 
Escalonamento em sistemas interativos 
– Round-Robin
● Similar ao FCFS, porém cada processo recebe um 
tempo limite máximo (fatia de tempo, quantum) para 
executar um ciclo de processador
● Fila de processos aptos/prontos é uma fila circular
● Necessidade de um relógio para delimitar as fatias de 
tempo
● Interrupção de tempo fornecido pelo hardware
A
0 40
B
C
D
3 6 9 12 15 18 2823 34
Processo
A
B
C
D
Tempo
12
8
15
5
Quantum = 3 u.t.
 
● Problemas:
● Dimensionamento do quantum
– Compromisso entre sobrecarga (devido ao chaveamento 
de contexto) e tempo de resposta em função do número 
de usuários (1/n na presença de n usuários)
● Quantum muito curto causa muitos chaveamentos de contexto e
reduz eficiência da CPU e quantum muito longo pode gerar 
tempo resposta muito alto para requisições interativas curtas
● Processos que fazem muito E/S são prejudicados
– Esperam da mesma forma que processos que utilizam 
muito a CPU, porém (provavelmente) não utilizam todo o 
seu quantum
– Solução:
● Prioridades: associar prioridades mais altas aos processos do 
tipo E/S intensiva para compensar o tempo de espera 
Escalonamento em sistemas interativos 
– Round-Robin (cont.)
 
Escalonamento em sistemas interativos 
– Por prioridades
● Consiste em atribuir tratamento diferenciado 
aos processos no escalonamento
● Prioridades podem ser:
● Estáticas – associadas com alguma característica 
do processo: função desempenhada, usuário, etc.
● Dinâmicas – alteradas de acordo com o 
comportamento do processo: quanto menos usa a 
CPU, maior a prioridade
– Exemplo de algoritmo simples: prioridade = 1 / f, onde f é 
a fração efetivamente usada do quantum
● “Mistas” – combina prioridades estáticas e 
dinâmicas
 
Escalonamento em sistemas interativos – Por 
prioridades (cont.)
● Exemplo: algoritmo de escalonamento com 4 classes 
de prioridade
● Abordagens comuns:
– Escalonar todos os processos de uma prioridade antes de começar 
a escalonar de outra
● Se não houver ajuste das prioridades, pode levar a inanição (starvation)
– Associar a frequência de escalonamento à prioridade
– Atribuir quantum de tempo diferente para cada prioridade
 
Escalonamento em sistemas de tempo real
● Principal objetivo é escalonar os processos de 
maneira que os prazos sejam cumpridos
● Tipicamente, os processos de um sistema de 
tempo real precisam tratar 2 tipos de eventos
● Periódicos – ocorrem em intervalos regulares de 
tempo (exemplo: captura de vídeo)
– É necessário dimensionar se o sistema de tempo real é 
escalonável
● Aperiódicos – acontecem de modo imprevisível 
(exemplo: falha de uma turbina de avião)
 
● Dimensionamento de um sistema de tempo 
real escalonável
● Dados:
– m eventos periódicos
– evento i ocorre dentro do período Pi e requer Ci 
segundos
● A carga poderá ser tratada somente se
1
1
m
i
i i
C
P
=
≤
∑
Escalonamento em sistemas de tempo real 
(cont.)
 
Escalonamento de threads
● Threads modo usuário
● Núcleo escalona o processo e biblioteca de threads é 
responsável pelo escalonamento das mesmas
– Depende da cooperação das threads, pois não há interrupção de 
relógio
– Pode ser usado qualquer algoritmo de escalonamento
– É flexível, podendo ser customizado para dar tratamento 
diferenciado as threads através de conhecimento da aplicação
 
Escalonamento de threads (cont.)
● Threads modo núcleo
● Não precisa levar em consideração a qual processo 
pertence uma thread, embora possa fazê-lo
● Impede que o bloqueio de uma thread leve necessariamente 
ao bloqueio de um processo
● Suporta diferenciação das threads por prioridade, mas não 
sabe nada sobre a aplicação