4. ESCALONAMENTO DE PROCESSOS
Escalonamento de processos é o ato de realizar o chaveamento dos processos ativos, de acordo com regras bem estabelecidas, de forma que todos os processos tenham chance de utilizar a UCP.
O escalonador é a parte do SO encarregada de decidir entre os processos prontos, qual será colocado em execução.
Diferente da idéia de execução de um processo até o término, vamos utilizar o escalonamento preemptivo, ou seja, o SO interrompe um processo em execução e roda o escalonador para decidir qual o próximo processo a ser executado.
Existem várias formas de implementar o escalonamento e estes devem seguir critérios como justiça (cada processo obter sua parte justa do tempo da UCP), eficiência (garantir ocupação de 100% do tempo da UCP), minimizar o tempo de resposta a comandos de usuários interativos, maximizar o número de serviços processados por hora etc.
Vejamos algumas forma de implementar:
1. Escalonamento “Round-Robin”: Cada processo recebe um intervalo de tempo (quantum) e se o processo ainda está rodando quando seu quantum terminar (ou se o processo bloqueie ou termine antes de acabar), a UCP é tomada deste processo e o escalonador seleciona um novo para rodar. O escalonador mantém uma lista de processos executáveis (que estão prontos) e quando o quantum termina sem o processo terminar, o mesmo é colocado no fim dessa lista. O escalonador sempre seleciona o primeiro processo dessa lista para execução. O valor do quantum deve ser escolhido cuidadosamente, se o valor do quantum for muito pequeno, teremos grande parte do tempo de execução da UCP gasta com o processo de chaveamento, e se o valor for muito grande, isto gera um tempo de resposta muito grande para usuários interativos. Processo com muita utilização da UCP devem ganhar maior quantum, para reduzir o número de chaveamento executado nesse processo. O grande problema aqui é o que o SO trata igualmente todos os processos, seja ele de pouca importância ou de grande importância.
2. Escalonamento com Prioridade: a prioridade serve para oferecer um tratamento distinto à processos diversos. No instante da criação de um processo ele recebe uma prioridade. E o quando o escalonador tiver que escolher qual processo será executado, escolherá o de mais alta prioridade. Cada vez que o processo é executado, o escalonador decrementa sua prioridade e quando sua prioridade fica abaixo de um outro processo pronto, ele é interrompido e o outro processo é executado. Temos duas maneiras de associar prioridades a processos:
a) de forma estática: quando a prioridade é associada no momento da criação do processo. Ex: quando se tem uma hierarquia.
b) de forma dinâmica: o escalonador decide o valor da prioridade de acordo com estatísticas sobre a execução deste processo em quanta anteriores. Ex: quando o sistema percebe que um processo efetua muita E/S, o escalonador aumenta sua prioridade (operações de E/S são realizadas independentemente da UCP, pois o processo faz uma chamada para o SO e fica bloqueado e enquanto isso a UCP pode estar alocada a outro processo que efetua cálculos).
Resumo: quanto maior E/S (menor uso do processador), maior prioridade (prioridade = 0).
3. Filas Múltiplas: devemos estabelecer classes de prioridades. Os processos de classes mais altas são escolhidos para execução mais freqüentemente que os de classe mais baixas (recebem um número maior de quanta para processamento). Os processos da classe mais alta existente recebem 1 quantum, a classe abaixo recebe 2, a outra 4 e assim sucessivamente na potência de 2. Quando o processo utiliza todos os quanta que recebeu, ele é abaixado de uma classe (fazendo com que seja escolhido menos freqüentemente, mas execute durante mais tempo). Ex: num processo que necessita de 100 quanta para executar, teremos execuções de 1, 2, 4, 8, 16, 32, 37 (totalizando 100), isto é, ele é selecionado para execução 7 vezes (7 chaveamentos para este processo). Se fosse no método Round-Robin ele seria selecionado 100 vezes até acabar. Surgiu um inconveniente: se um processo começa com grande quantidade de cálculos, mas depois se torna interativo (comunicação com o usuário), teríamos um tempo de resposta ruim. Para eliminar este problema, foi implementado mais um método que seria o seguinte: cada vez que um é teclado no terminal de um processo, este processo é transferido para a classe de prioridade mais alta (pois se tornou interativo). Mas depois um usuário descobriu que durante a execução de um processo grande, bastava teclar no terminal aleatoriamente para ter o tempo de execução melhorado.
OBS: As estratégias 1, 2 e 3 são úteis para sistemas de time-sharing.
4. Menor Serviço Primeiro: é útil para sistemas de lotes (batch), pois muitas vezes o usuário já sabe estimar o tempo de execução dos programas (pois os programas são rodados constantemente). O escalonador escolhe para execução entre todos os jobs disponíveis, aquele de menor tempo de execução. EX: Existem quatro jobs disponíveis (A, B, C, D). O A demora 8 minutos para executar e os demais, 4 minutos cada. Se o job de 8 minutos for escolhido antes, teríamos:
- Tempo de resposta de A: 8 minutos
- Tempo de resposta de B: 8 + 4 minutos = 12 minutos
- Tempo de resposta de C: 8 + 4 + 4 minutos = 16 minutos
- Tempo de resposta de D: 8 + 4 + 4 + 4 minutos = 20 minutos
- Tempo médio de resposta = 56/4 = 14 minutos
Utilizando o método Menor Serviço Primeiro vamos ter um tempo médio de reposta igual a 11 minutos! Mesmo que os serviços não são todos conhecidos o tempo de resposta pode não ser o mínimo mas é uma boa aproximação.
5. Escalonamento Dirigido a Política: Se existem n usuários ativos, então, cada um receberá aproximadamente 1/n do tempo de UCP. Para garantir isso devemos usar o seguinte método:
- manter para cada usuário o valor do tempo de UCP que ele já utilizou desde que entrou (tempo utilizado).
- contar quanto tempo já se passou desde que o usuário iniciou sua seção e dividir pelo número de usuários gerando o tempo destinado ao processo (tempo destinado)
- computar para cada usuário a razão entre o tempo utilizado e o tempo destinado (razão)
Então escolhemos para execução aquele usuário que apresenta a menor razão.
Ex:
 Ia = 4 / (10/2) = 0,8 = 80% Ib = 6 / (10/2) = 1,2 = 120 % Devemos escolher o processo de menor porcentagem para colocar em execução. (no caso, o A)
Ia = (( 4 / (10/2)) x 10 + Ic = (( 5/(15/3) x 15 ) / 15 = 1,0
Neste caso, o escolhido é o B |
6. Escalonamento em Dois Níveis: Até aqui consideramos que todos os processos executáveis estão na memória. Diferentemente, aqui precisamos manter parte dos processos em disco (pois a memória principal dificilmente comportará todos os dados necessários). O problema é que o tempo para ativar um processo que está em disco é muito maior que o para ativar um que está na memória. A melhor solução para isto é a utilização de um escalonador em dois níveis. Para isso um subconjunto dos processos executáveis é mantido na memória e um outro subconjunto é mantido no disco. Um escalonador (baixo nível) é utilizado para realizar o chaveamento (por qualquer método descrito anteriormente) apenas entre os processos que estão na memória e outro escalonador (alto nível) é utilizado para trocar periodicamente o conjunto de processos que estão na memória (por aqueles que estavam em disco). Para escolher qual conjunto de processos será colocado na memória, o escalonador de alto nível deve verificar: o tamanho do processo, a prioridade do processo, o tempo de UCP do processo, quando tempo se passou desde que o processo foi posto ou retirado
O material acima está dividido em oito partes, foi escrito por Alex De Francischi Coletta em 2003 e adaptado para a WEB.
Bibliografia: FREITAS, Ricador Luis de “Apostila de Sistemas Operacionais” utilizado no curso de graduação em Engenharia de Computação da Pontifícia Universidade Católica de Campinas na disciplina de Sistemas Operacionais I.