Sistemas Operacionais

Aula 3: Escalonamento

Porque ?
Quando ?
Como ?
Critérios ?
Políticas de escalonamento.
Como avaliar ?

Referências

Capítulo 5: 5.1 a 5.3, 5.6

Porque Escalonar ?

Escalonamento controla o compartilhamento de recursos.
Multiprogramação: permite a utilização simultânea de vários usuários.
Maximizar utilização da CPU: Processos bloqueados não param a CPU.

Quando Escalonar ?

Escalonamento ocorre quando existem:

Interrupções:
- Temporização
- Erros (e.g. divisão por zero)
Eventos:
- E/S
- Comunicação e sincronização

Ou seja, quando muda o processo que está
executando.

Troca de contexto

Importante porque:

Necessário para proteção
Caro porque troca-se todo o modo de endereçamento

Critérios de Otimização

Políticas de escalonamento devem:

Maximizar a utilização da CPU: mantê-la ocupada por mais tempo.
Maximizar ``throughput'': número de jobs por seg.
Minimizar ``turnaround'': tempo entre submissão e conclusão
Minimizar tempo de resposta: tempo entre submissão e início da execução,
Ser ``justos'': o que significa ?
Ser eficientes: minimizar overhead tal como como troca de contexto.

Muitas políticas de escalonamento existem! Cada uma atende um objetivo.

Preempção X Não Preempção

Políticas não preemptivas:

Processo nunca é interrompido: execução só para quando processo termina ou é bloqueado.
Mais simples.

Políticas preemptivas:

Processo pode ser interrompido antes de terminar ou sem ser bloqueado.
Cada processo tem um quantum de execução. Após este tempo ele é interrompido.
Melhor tempo de resposta.

A partir de agora processos e threads serão equivalentes a não ser quando citado.

Política de Escalonamento -- FIFO

FIFO: First In First Out
FCFS: First Come First Served
Não preemptivo: processo executa até o fim.

Ou até bloquear por E/S ou sincronização.

Justo: quem pede primeiro leva vantagem.

Vantagem: simples
Desvantagem: Tempo de resposta alto. Alguém já ficou atrás de uma pessoa com ``pastinha preta'' na fila do banco ?

Shortest Job First -- SJF

Solução: Rodar os processos menores primeiro.

Algoritmo com menor tempo de espera: ótimo!
Contudo é difícil calcular-se o tamanho do processo:
principalmente o tamanho do próximo burst.
Pode-se estimar o tamanho do burst usando-se o tamanho do anterior: nem sempre preciso.

Round-Robin

Outra solução: Adotar um quantum de tempo. Quando o processo esgota seu quantum, é interrompido e colocado no fim da fila de ready.

Justo: todos tem um pedaço igual.
Virtualmente todos SOs usam round-robin.
Tamanho do quantum:
- muito pequeno: troca de contexto cara.
- muito grande: tempo de resposta alto.
Desvantagem: nenhum processo termina antes de todo mundo rodar um pouco.

Prioridades

Cada processo tem uma prioridade:

Processos com prioridade maior rodam primeiro
Alocação de prioridades:
- Estática: e.g. processos que monitoram a temperatura do urânio rodam primeiro.
- Dinâmica: e.g. processos que estão mais perto do seu prazo rodam primeiro.

Vantagem: O urânio não derrete!
Desvantagem: Quem não cuida do urânio pode não rodar nunca.

Usado em sistemas de tempo real.

Filas Múltiplas

São usadas várias filas de processos prontos para executar. Cada processo é colocado em uma fila.
Cada fila tem uma política de escalonamento.
Existe uma política de escalonamento entre filas.

Vantagem:
- Pode-se implementar políticas sofisticadas.
Desvantagem:
- Complicado de prever o comportamento
- Processos nunca mudam de fila.

Filas Múltiplas com Realimentação

Processos podem mudar de filas.

Desvantagem: Mais complicado ainda! Agora tem que ter política de promoção e de rebaixamento.

Vantagem: flexibilidade.

Exemplo: 4.3 BSD Unix

Filas múltiplas com realimentação:

Entre filas: prioridades fixas
Dentro de cada fila: round-robin

Prioridades (i.e. a qual fila o processo pertence) mudam baseado em:

Processo usou todo quantum? PRI--
Usou a CPU por muito tempo? PRI--
Está esperando por muito tempo? PRI++ aging!
...

Efeito: Processos interativos rodam mais rápidos. Processos com muita CPU rodam depois. Mas as prioridades mudam dinamicamente.

Avaliação Analítica

Dada uma certa política de escalonamento, como ela se comporta na prática ?

Assume um conjunto fixo de processos;
Calcula-se como cada política escalona este conjunto;
Determina-se tempo de resposta, etc.

Vantagem: Fácil de calcular.
Desvantagem: conjunto fixo de processos.

Teoria de Filas

Assume-se que processos vão chegar segundo certa distribuição;
Métodos estatísticos (teoria de filas) permite concluir que se a chegada de processos obedece à distribuição podemos calcular:
Vantagem: Produz muita informação útil
Desvantagem: Nem todos os processos podem ser modelados de acordo com distribuições estatísticas; resultados são ``médios''

Simulação

Implementa-se um modelo e roda-se-o para um número grande de processos;
Calcula-se tempo de resposta, etc, a partir dos resultados desta execução;

Vantagem: Qualquer política pode ser modelada; eficiente.
Desvantagem: Resultados não são garantidos.

Verificação Automática

Modela-se o sistema como um grafo;
Usa-se ferramentas que visitam o grafo e calculam propriedades do mesmo, incluindo tempo de resposta, etc...

Vantagem: Resultados garantidos; Qualquer política pode ser modelada.
Desvantagem: Busca em grafos é cara.

Escalonamento: Resumo

Controla o compartilhamento de recursos.
Ocorre quando o processo executando muda.
Critérios de otimização de políticas: tempo de resposta, throughput, utilização, etc.
Políticas:
Métodos de Avaliação: