Aula 6 - Sistemas Operacionais

Prévia do material em texto

SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Sumário
6.1 Introdução
6.2 Níveis de escalonamento
6.3 Escalonamento Preemptivo vs. Não-preemptivo
6.4 Prioridades
6.5 Objetivos de escalonamento
6.6 Critérios de escalonamento
6.7 Algorítmos de escalonamento
6.7.1 Escalonamento First-In-First-Out (FIFO)
6.7.2 Escalonamento Round-Robin (RR)
6.7.3 Escalonamento Shortest-Process-First (SPF)
6.7.4 Escalonamento Highest-Response-Ratio-Next (HRRN)
6.7.5 Escalonamento Shortest-Remaining-Time (SRT)
6.7.6 Filas Multinível com Retroalimentação
6.7.7 Escalonamento Fair Share
6.8 Escalonamento Deadline
6.9 Escalonamento Real-Time
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Objetivos
• Após ler este capítulo, você deve compreender:
– Os objetivos do escalonamento do processador.
– Escalonamento preemptive vs. nonpreemptive.
– O papel das prioridades no escalonamento.
– Critérios de escalonamento.
– Algorítmos comuns de escalonamento.
– Noções de escalonamento de deadline e escalonamento real-time.
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.1 Introdução
• Política de escalonamento de processador
– Decide qual processo roda em um determinado tempo
– Escalonadores diferentes terão diferentes objetivos
• Maximizar throughput
• Minimizar latência
• Prevenir postergações indefinidas
• Completar um processo em um determinado limite
• Maximizar a utilização do processador
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.2 Níveis de Escalonamento
• Escalonamento Alto-Nível
– Determina que tarefas podem competir por recursos
– Controla o número de processos no sistema em um dado tempo
• Escalonamento Nível-Intermediário
– Determina que processos podem competir por processadores
– Responde por flutuações na carga do sistema
• Escalonamento Baixo-Nível
– Atribui prioridades
– Atribui processadores a processos
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.1 Níveis de escalonamento
6.2 Níveis de Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.3 Escalonamento Preemptivo vs. Não-preemptivo 
• Processos Preemptivos
– Podem ser removidos de seus processadores atuais
– Podem levar a tempo tempo de respostas melhores
– Importante para ambientes interativos
– Processos Preemptivos permanecem em memória
• Processos Não-preemptivos
– Rodam até finalizarem ou até que eles liberem o controle do 
processador
– Processos não importantes podem bloquear processos 
importantes indefinidamente
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.4 Prioridades
• Prioridades estáticas
– Prioridade designada a um processo não muda
– Fácil de implementar
– Baixo overhead
– Não responsivo a mudanças no ambiente
• Prioridades dinâmicas
– Responsiva a mudanças
– Promove interatividade suave
– Encorre em mais overhead que prioridades estáticas
• Justificada por respostas melhoradas
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.5 Objetivos de Escalonamento
• Diferentes objetivos dependem do sistema
– Maximizar throughput
– Maximizar o número de processos interativos recebendo tempos 
de resposta aceitáveis
– Minimizar a utilização de recursos
– Evitar postergações indefinidas
– Garantir prioridades
– Minimizar overhead
– Garantir predibilidade
– Minimizar o turnaround time
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.5 Objetivos dos Escalonadores
• Vários objetivos comuns aos escalonadores
– Justiça
– Previsibilidade
– Escalabilidade
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Histogram of CPU-burst Times
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.6 Critérios de Escalonamento
• Processos CPU-bound
– Usam todo o tempo disponível do processador
• Processos I/O-bound
– Gera uma requisição de I/O rapidamente e libera o processador
• Processos Batch
– Contém trabalho a ser realizado sem interação com o usuário
• Processos Interativos
– Requirem entrada do usuário frequente
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7 Algorítmos de Escalonamento
• Algorítmos de escalonamento
– Decidem quando e por quanto tempo um processo roda
– Fazem escolhas sobre 
• Preemptibilidade
• Prioridade
• Tempo de execução
• Tempo de execução para completament
• Justiça
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.1 Escalonamento First-In-First-Out (FIFO) 
• Escalonamento FIFO
– Esquema simples
– Processos despachados de acordo com o tempo de chegada
– Não-preemptível
– Raremente usado como algorítmo de escalonamento primário
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.2 Escalonamento First-in-first-out
6.7.1 Escalonamento First-In-First-Out (FIFO)
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
 Suppose that the processes arrive in the order: P1 , P2 , P3 
The Gantt Chart for the schedule is:
 Waiting time for P1 = 0; P2 = 24; P3 = 27
 Average waiting time: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order
P2 , P3 , P1
 The Gantt chart for the schedule is:
 Waiting time for P1 = 6; P2 = 0; P3 = 3
 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case
 Convoy effect short process behind long process
P1P3P2
63 300
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.2 Escalonamento Round-Robin (RR)
• Escalonamento Round-robin
– Baseado em FIFO
– Processos rodam somente por um período de tempo limitado 
chamado de fração de tempo ou quantum
– Preemptível
– Requer que o sistema mantenha vários processos em memória para 
minimizar o overhead
– Frequentemente usado como parte de algorítmos mais complexos
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.3 Escalonamento Round-robin
6.7.2 Escalonamento Round-Robin (RR)
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Example of RR with Time Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
 The Gantt chart is: 
 Typically, higher average turnaround than SJF, but better response
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Time Quantum and Context Switch Time
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAISAula 6: Escalonamento
Turnaround Time Varies With The Time Quantum
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.2 Escalonamento Round-Robin (RR)
• Escalonamento round-robin egoísta
– Incrementa a prioridade com o envelhecimento do processo
– Duas filas
• Ativo
• Em espera
– Favorece processos mais velhos e evita demoras não razoáveis
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.2 Escalonamento Round-Robin (RR)
• Tamanho do Quantum
– Determina o tempo de resposta de requisições interativas
– Tamanho de quantum muito grande
• Processos rodam por longos períodos
• Degenera em FIFO
– Tamnho de quantum muito pequeno
• Sistema gasta muito tempo trocando contexto do que rodando processos
– Meio de campo
• Longo o suficiente para processos interativos emitir requisição de I/O
• Processos Batch ainda obterão a maior parte do tempo do processador
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.3 Escalonamento Shortest-Process-First (SPF)
• Escalonadores selecionam o processo com menor 
tempo para terminar
– Tempo de espera médio menor que na FIFO
• Reduz o número de processos em espera
– Potencialmente grandes variâncias nos tempos de espera
– Não-preemptivo
• Resulta em pequenos tempos de espera para requisições interativas 
entrantes
– Basea-se em estimativas do tempo para completamento
• Pode ser inacurado ou falsificado
– Não apropriado para uso em modernos sistemas interativos
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 SJF (non-preemptive)
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Example of Non-Preemptive SPF
P1 P3 P2
73 160
P4
8 12
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Exemplo de SPF Preempitivo
Processo Chegada Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 SJF (preemptive)
 Average waiting time = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.4 Escalonamento Highest-Response-Ratio-Next (HRRN)
• Escalonamento HRRN
– Melhora sobre o escalonamentoImproves upon SPF scheduling
– Still nonpreemptive
– Considers how long process has been waiting
– Prevents indefinite postponement
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.5 Escalonamento Shortest-Remaining-Time (SRT)
• Escalonamento SRT
– Versão Preemptiva do SPF
– Processos pequenos entrantes preemptam um processo executando
– Variâncias muito grandes do tempo de resposta: processos longos 
esperam esperam ainda mais que sob SPF
– Nem sempre ótimo
• Processos pequenos entrantes podem preemptar um processo 
executando próximo ao seu término
• Overhead de troca de contexto pode tornar-se significativo
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.6 Filas Multinível com Retroalimentação
• Processos diferente têm diferentes necessidades
– Pequenos processos I/O-bound interativos devem rodar geralmente antes 
que um processo batch CPU-bound
– Padrões de comportamento nem sempre óbvio para o escalonador
• Filas multinível com retroalimentação
– Processos entrantes entram na fila de mais alta prioridade e executam 
com mais alta prioridade que processos em filas mais baixas
– Processos longos repedidamente descem para filas mais baixas
• Dá a processos pequenos e a processos I/O-bound maior prioridade 
• Processos longos rodarão quando processos pequenos e I/O-bound 
terminarem
– Processos em cada fila serão servidos usando round-robin
• Processo entrante em uma fila mais alta preempt processos executando
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.6 Filas Multinível com Retroalimentação
• Algorítmos devem reposder a mudanças no ambiente
– Mova processos para filas diferentes enquanto eles alternam entre 
comportamentos interativos e batch
• Exemplo de um mecanismo adaptivo
– Mecanismos adaptivo encorrem em overhead que frequentemente é 
deslocado por sensibilidade incrementada para o comportamento do 
processo
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Multilevel Queue Scheduling
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.4 Filas multinível com 
retroalimentação.
6.7.6 Filas Multinível com Retroalimentação
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.7.7 Escalonamento Fair Share
• FSS controla acesso de usuários aos recursos do sistema 
– Alguns grupos de usuários são mais importantes que outros
– Assegura que grupos menos importantes não podem monopolizar os 
recursos
– Recursos não usados distribuídos de acordo com a proporcionalidade dos 
recursos cada grupo tem alocado
– Grupos que não encontram os objetivos de recursos-utilização ganham 
maior prioridade
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.5 Escalonador padrão UNIX. O escalonador entregam o processador a 
usuários, cada um pode ter diversos processos. (Propriedade do AT&T Archives.
Reimpresso com permissão da AT&T.)
6.7.7 Esclonamento Fair Share
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
Figura 6.6 Escalonador fair share. O escalonador fair share divide a capacidade de 
recursos do sistema em porções, as quais são alocadas por escalonadores atribuídas 
a vários grupos fair share. (Propriedade da AT&T Archives. Reimpresso com a 
permissão da AT&T.)
6.7.7 Escalonamento Fair Share
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.8 Escalonamento de Deadline
• Escalonamento de Deadline
– Processo deve completar em um tempo específico
– Usado quando resultados serão sem sentido se não entregues a tempo
– Difícil de implementar
• Deve planejar requerimento de recursos antecipadamente
• Encorre em overhead significativo
• Serviço provido a outros processos pode degradar
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.9 Escalonamento Real-Time
• Escalonamento Real-time
– Relacionado ao escalonamento de deadline
– Processos têm restrições de tempo
– Também abrange tarefas que executam periodicamente
• Duas categorias
– Escalonamento soft real-time
• Não garante que restrições de tempo serão obedecidas
• Por exemplo, multimedia playback
– Escalonamento hard real-time
• Restrições de temposerão sempre obedecidas
• Falha em obedecer o deadline pode ter resultados catastróficos
• Por exemplo, controle de tráfego aéreo
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.9 Escalonamento Real-Time
• Escalonamento real-time estático
– Não ajusta prioridades ao longo do tempo
– Baixo overhead
– Aplicável para sistemas onde as condições raramente mudam
• Escalonadores Hard real-time
– Escalonamento Rate-monotonic (RM)
• Prioridade de processos aumentam monotonicamente com a 
frequência que ele deve executar
– Escalonamento Deadline RM
• Útil para um processo que tem um deadline que não é igual ao seu 
período
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
SISTEMAS OPERACIONAIS
Aula 6: Escalonamento
6.9 Escalonamento Real-Time
• Escalonamento real-time dinâmico
– Ajusta prioridades em resposta a mudanças nas condições
– Pode encorrer em overhead significativo, mas deve assegurar que o 
overhead não resultte no aumento dos deadlines perdidos
– Prioridades são usualmente baseadas nos deadlines dos processos
• Earliest-deadline-first (EDF)
– Preemptivo, sempre despacha o processo com o deadline mais cedo
• Minimum-laxity-first
– Similar ao EDF, mas baseia a prioridade em laxity, a qual é baseada 
no deadline do processo e seu tempo que falta para completamento