Gerência do Processador
De Aulas
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
- O que é Escalonamento de Processos e quais suas principais funções?
- Cite e explique os critérios de escalonamento.
- Quais as diferenças entre o escalonamento preemptivo e o escalonamento não-preemptivo? Explique de forma resumida cada um deles.
- 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.
- 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.
- Como funciona o escalonamento de sistemas de tempo real?
- Descreva o funcionamento do escalonamento com múltiplos processadores, e cite as diferenças do escalonamento em sistemas fracamente acoplados e fortemente acoplados
