Baixe o app para aproveitar ainda mais
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
Compartilhar