Sistemas Operacionais

Sistemas Operacionais
Capítulo 8
Gerência do Processador
(Escalonamento de Processos)

8.1 – 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.

8.2 – 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.

8.3 – 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

8.3.1 – 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.

8.3.2 – 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.

8.3.3 – 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.

8.4. 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.

8.4.1 – 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

8.4.2 – 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âmcia:

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 CPU-bounds esperam por algum evento.

O tempo de resposta compensa o maior overhead e complexidade algorítmica.

8.4.3 – 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.

8.4.4 – 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.

8.4.5 – 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.

8.5 – 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.

[voltar]