Gerência do Processador

Conteúdo integrante da disciplina de Sistemas Operacionais

Introdução

• Compartilhamento da CPU em sistemas multiprogramáveis.
• Critérios de escolha da ordem dos processo a entrar em execução.
• Scheduler (escalonador):
  • Uma das principais funções do Sistema Operacional
  • Parte do código do Sistema Operacional responsável pelo scheduling (escalonamento).
• Funções do escalonamento:
  • Manter a CPU ocupada a maior parte do tempo.
  • Balancear a utilização do processador entre diversos processos.
  • Maximizar o throughput do sistema
  • Oferecer tempos de respostas razoáveis para os usuários interativos.
  • Evitar starvation.

Critérios de Escalonamento

• Utilização da CPU
  • Em geral, é desejável que o processador permaneça a maior parte do tempo ocupado
• Throughput
  • Número de processos executados em um determinado intervalo de tempo.
  • Em geral, a maximização do throughput é desejada.
• Tempo de turnaroud
  • Tempo que um processo leva desde sua admissão no sistema até seu término.
  • Considera tempo de espera para alocação de memória, espera na fila de processos prontos, processamento e operações de entrada e saída.
  • Em geral, a minimização do tempo de turnaround é desejada.
• Tempo de resposta
  • Tempo decorrido do momento da submissão de um pedido ao sistema até a primeira resposta produzida.
  • Em geral, a minimização do tempo de resposta é desejada.

Escalonamento Não-preemptivo

• Existente nos primeiros sistemas multiprogramáveis, onde predominava o processamento batch.
• Quando um processo (JOB) ganha o direito de utilizar a CPU, nenhum outro processo pode lhe tirar esse recurso.

Escalonamento First-In-First-Out (FIFO)

• O processo que chegar primeiro, é o primeiro a ser selecionado para a execução.
• Necessário apenas uma fila de processos prontos, esperando pelo uso do processador.
• O processo utiliza a CPU sem ser interrompido.
• Problemas:
  • Impossibilidade de prever quando um processo entrará em execução.
  • Possibilidade de processos CPU-bound de menor importância prejudicarem processos de I/O-bound mais proprietários.

Escalonamento Shortest-Job-First (SJF)

• Associa cada processo (JOB) ao seu tempo de execução.
• Quando o processador está livre, o processamento que ocupar menos tempo da CPU para terminar seu processamento é selecionado.
• Favorece os programas menores.
• Reduz o tempomédio de espera em relação ao FIFO.
• Problemas:
  • Determinar, exatamente, quanto tempo de CPU o processo vai utilizar para terminar seu processamento.

Escalonamento Cooperativo

• O processo está em execução libera voluntariamente o processador, retornando para a fila de pronto, cooperando com os outros processos.
• Permite uma melhor distribuição do processador entre os processos.
• Não existe intervenção do Sistema Operacional na execução do processo.
• Exemplos: Microsoft Windows 3.1 e 3.11
• Problemas:
  • Um programa mal escrito pode entrar em looping, monopolizando a CPU.

Escalonamento Preemptivo

• O Sistema pode interromper um processo em execução para que outro processo utilize o processador.
• Permite que o sistema dê atenção imediata a processos mais prioritários, como no caso de sistemas em tempo real.
• Proporciona melhores tempos de resposta em sistemas de tempo compartilhado
• Compartilhamento do processador de uma maneira mais uniforme entre os processos.
• A troca de um processo pelo outro na CPU (mudança de contexto), causado pela preempção, gera um overhead no sistema.
• Critérios de preempção devem ser definidos para o overhead não se tornar crítico.

Escalonamento Circular (round robin) ou preempção por tempo

• Implementado por um algoritmo semelhante ao FIFO, porém, quando um processo passa para o estado de execução, existe um tempo-limite (quantum ou time-slice) para sua utilização de forma contínua. Se o processo não terminou a execução, volta ao estado de pronto.
• Em geral, o valor do quantum de tempo está entre 100 e 300 ms.
• Nenhum processo poderá monopolizar a CPU.
• Algoritmo bastante adequado para sistemas multiusuários de tempo compartilhado.
• No caso, o processo CPU-bound tem mais chances de ser executado do que o processo IO-bound

Escalonamento por Prioridades ou preempção por prioridade

• Processos possuem diferentes prioridades de execução.
• Processos de maior prioridade são escalonados preferencialmente.
• Algoritmo Implementado mediante um clock, que interrompe o processador em determinados intervalos de tempo, reavaliando prioridades e, possivelmente, escalonando outro processo.
• Todos os sistemas de tempo compartilhado implementam algum tipo de prioridade, sendo esta uma característica do contexto de software.

Prioridade estática

• Não é modificada durante a existência do processo.
• De simples de implementação.
• Pode ocasionar tempos de resposta elevados.

Prioridade dinâmica

• Pode ser modificada durante a execução do processo.
• O processo recebe um acréscimo à sua prioridade ao sair do estado de espera.
• Processos I/O-bounds terão mais chances de serem escalonados, compensando o tempo que passam no estado de espera.
• Os processos CPU-bounds podem ser executados enquanto os processos IO-bounds esperam por algum evento.
• O tempo de resposta compensa o maior overhead e complexidade algorítmica.

Escalonamento por Múltiplas filas

• Implementa diversas filas de processos no estado pronto, onde cada processo é associado exclusivamente a uma delas.
• Cada fila possui um mecanismo próprio de escalonamento, em função das características dos processos.
• Cada fila possui uma prioridade associada.
• O sistema só pode escalonar processos de uma fila, se todas as outras de prioridade maior estiverem vazias.

Escalonamento por Múltiplas Filas com Realimentação

• Também Implementa diversas filas onde cada uma tem uma prioridade de execução associada, porém, os processos não permanecem em uma mesma fila até o término do processamento.
• O sistema identifica dinamicamente o comportamento de cada processo, ajustando assim suas prioridades de execução e mecanismos de escalonamento.
• Os processos não são previamente associados às filas de pronto, e sim direcionados pelo sistema entre as diversas filas com base em seu comportamento.
• Execução:
  • Processo criado entra no final da fila de mais alta prioridade.
  • Cada fila implementa o mecanismo de FIFO para escalonamento.
  • Quando o processo em execução deixa a CPU por preempção por prioridade ou por solicitação a um ** recurso do sistema ele é reescalonado para dentro da mesma fila.
  • Caso o processo esgote seu quantum de tempo, ele é redirecionado para um a fila de menor prioridade (preempção por tempo), e assim por diante.
  • A fila de mais baixa prioridade implementa o mecanismo de escalonamento circular.
  • O quantum em cada fila varia em função da sua prioridade. Quanto maior a prioridade, menor seu quantum de tempo.
• Atende as necessidades dos diversos tipos de processos.
• Pode ser implementado em qualquer tipo de Sistema Operacional.
• Pode gerar um grande overhead no sistema, ainda assim, pode justificar sua implementação.

Escalonamento de Sistemas de Tempo Real

• Fator de tempo crítico, pequeno tempo de resposta obrigatório.
• Escalonamento feito unicamente com base no esquema de prioridades estáticas.
• Quanto maior a importância de uma tarefa, maior sua prioridade de execução em relação às demais.

Escalonamento com Múltiplos Processadores

• Escalonamento bem mais complexo do que com um único processador.
• Sistemas Fracamente Acoplados:
  • cada processador faz seu processamento local.
• Sistemas Fortemente Acoplados:
  • Possível implementar uma única fila de pronto para todos os processadores.
  • Importante a implementação da exclusão mútua.
  • Não pode haver a possibilidade de um mesmo processo ser escalonado por dois processadores diferentes.

Lista de Exercícios

Formulário

1. O que é Escalonamento de Processos e quais suas principais funções?
2. Cite e explique os critérios de escalonamento.
3. Quais as diferenças entre o escalonamento preemptivo e o escalonamento não-preemptivo? Explique de forma resumida cada um deles.
4. Descreva de forma resumida o escalonamento First-In-First-Out, o escalonamento Shortest-Job-First e o escalonamento cooperativo, explicando os problemas de cada um.
5. Descreva resumidamente o escalonamento circular, o escalonamento por prioridades, o escalonamento por múltiplas filas e o escalonamento por múltiplas filas com realimentação.
6. Como funciona o escalonamento de sistemas de tempo real?
7. Descreva o funcionamento do escalonamento com múltiplos processadores, e cite as diferenças do escalonamento em sistemas fracamente acoplados e fortemente acoplados