Aulas UNIESSA

Gerência do Processador

 O escalonador é a entidade do SO responsável por selecionar um processo apto para executar no processador

 O objetivo é dividir o tempo do processador de forma justa

 Típicos de sistemas multiprogramados

 Duas partes:

     Escalonador: política de seleção

     Dispatcher: efetua a troca de contexto

Objetivos do Escalonamento

Maximizar a utilização do processador Maximizar a produção do sistema

 N° de processos executados por unidade de tempo

Minimizar o tempo de execução

 Tempo total para executar um processo

Minimizar o tempo de espera

 Tempo em que o processo permanece na fila de aptos

Minimizar o tempo de resposta

 Tempo decorrido entre a requisição e sua realização

Quando Escalonar

 Quando se cria um novo processo, é necessário tomar uma decisão entre executar o processo pai ou o processo filho

 Quando se termina um processo, algum outro processo deve ser escolhido entre processos prontos

 Quando um processo bloqueia para E\S

 Quando ocorre uma interrupção de E\S

Algoritmos de Escalonamento

– Existem duas categorias de algoritmos de escalonamento:

Não preemptivos – escolhe um processo para executar e então o deixa executar até que seja bloqueado ou até que ele voluntariamente libere a CPU

Preemptivos – escolhe um processo e o deixa em execução por um tempo máximo fixado

Ambientes de escalonamento

 Lote (Batch)

Algoritmos não preemptivos ou preemptivos com longo intervalo de tempo

 Interativo

Preempção é essencial!

 Tempo real

Algumas vezes a preempção é desnecessária

Objetivos do algoritmo de escalonamento

Todos os Sistemas:

Justiça – dar a cada processo um porção justa da CPU

Aplicação da política – verificar se a política estabelecida é cumprida

Equilíbrio – manter ocupadas todas as partes do sistema

Sistemas em Lote:

Vazão (throughput) – maximizar o n° de processos por hora

Tempo de retorno – minimizar o tempo entre a submissão e o término

Utilização de CPU – manter a CPU ocupada o tempo todo

Sistemas Interativos

Tempo de resposta – responder rapidamente às requisições

Proporcionalidade – satisfazer às expectativas 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ídia

Considerações

 Vazão – é o número de processos por hora que o sistema termina

 Tempo de resposta – indica quanto tempo, em média, o usuário tem de esperar pelo fim de um trabalho

Despacho (Dispatch) ou Troca/Chaveamento de contexto

• Mudança do processo em execução
• O S.O. deve salvar o estado do processo atual e carregar o estado do novo processo
  • Pergunta: Onde salvar e de onde recuperar?
• Troca de contexto é overhead
• Tempo gasto depende do hardware e da estrutura do processo no S.O.

 

Escalonamento em Sistemas em Lote (Batch)

Escalonamento em Sistemas Interativos

Níveis de Escalonamento

 Longo Prazo

• Executado quando um novo processo é criado;

• Determina quando um processo novo passa a ser considerado no sistema;

• Controla o grau de multiprogramação do sistema

  • Quanto maior o n° de processos ativos, menor a porcentagem de tempo de uso do processador por processo

 Médio Prazo

• Associado a gerência de memória

  • Participa do mecanismo de swapping

• Suporte adicional a multiprogramação

  • Grau de multiprogramação efetiva (diferencia aptos dos aptos suspensos)

 Curto Prazo

• Mais importante;

• Determina qual processo apto deverá utilizar o processador;

• Executado sempre que eventos importantes ocorrem

  • Interrupção de relógio

  • Interrupção de E\S

  • Chamadas de sistemas

  • Sinais (interrupção de software)

 

Diagrama de Escalonamento

 

 

Algoritmos de escalonamento

 FIFO

     Simples de Implementar (Fila)

     Funcionamento:

             Processos aptos são inseridos no fim da fila

             Processo no início da fila é o próximo a executar

             Processo executa até que:

                         Libere o processador

                         Realize uma chamada de sistema (bloqueado)

                         Termine sua execução

 Round Robin

      Similar ao algoritmo FIFO, só que:

               Cada processo recebe um tempo limite máximo para executar um ciclo do processador

      Fila de processos aptos é uma fila circular

      Necessidade de um relógio para delimitar as fatias de tempo

Shortest Job First (SJF)

• Associa-se a cada processo seu próximo pulso
  • Próximo processo será o de menor pulso
• SJF Preemptivo:
  • Um processo que possui um pulso menor que o restante de pulsos do correntemente em execução força a preempção
  • Chamado de Shortest Remaining Time First (SRTF)
• SJF não preemptivo
  • Processos que chegam são comparados apenas com aqueles à espera da CPU
• SJF é ótimo quanto ao tempo médio de espera

 

Problema: Duração do próximo pulso

Como resolver?

 

Escalonamento com prioridades

• um valor inteiro de prioridade para cada processo
• A CPU é alocada para o processo de maior prioridade
  • Usualmente quanto menor o valor, maior a prioridade
  • Preemptivo ou não preemptivo
• SJF é um escalonamento com prioridade, onde a prioridade é o tamanho previsto do pulso de CPU
• Problema: Inanição (Starvation)
  • Processos de baixa prioridade podem nunca ser executados
• Solução: Envelhecimento (aging)
  • Prioridade de cada processo que fica na fila aumenta à medida que o tempo passa

 

Escalonamento por Filas Multi-Nível

• Fila de processos prontos é dividida:
  • Processos interativos (Foreground) – RR
  • Processos em lote;batch(background) – FIFO
• Escalonamento entre filas
  • Prioridade fixa
    • P. Ex: Atender sempre processos interativos primeiro
    • Possibilidade de inanição
  • Fatias de Tempo
    • Cada fila é escalonada por uma fração do tempo total

 

Filas Multinível com realimentação

• Um processo pode se mover entre filas
  • Forma de interpretar o envelhecimento
• Escalonamento pode ser definido por:
  • No de filas
  • algoritmo de escalonamento de cada fila
  • método usado para promover um processo
  • método usado para rebaixar um processo
  • método usado para decidir em que fila cada processo entra no sistema

Escalonamento de multi-processadores

Multiprocessamento Simétrico (SMP)

• Todas as CPUs acessam dados e recursos de forma igual

Multiprocessamento assimétrico (AMP):

• Só um processador acessa as estruturas de dados do sistema, reduzindo a complexidade do sistema

 

Escalonamento de tempo real

• Processos podem estabelecer demandas em termos de tempo de ativação de tarefas
• Essencial para sistemas de controle de processos de precisão e multimídia
• Hard real-time (tempo rígido) – Devem completar tarefas em um tempo garantido
• Soft real-time (tempo maleável) – requerem que processos críticos recebam prioridade superior aos demais

 

Latência de despacho

• Tempo gasto até que um processo de tempo real que solicita a CPU realmente a receba
• Técnicas podem reduzir essa latência
  • Pontos de interceptação: Pontos onde operações potencialmente longas podem ser interrompidas
  • Kernel interceptável (interrompível)
  • Liberação forçada de recursos de processos de baixa prioridade (resolução de conflitos)