Escalonamento de processos

Quando mais de um processo é executável, o sistema operacional deve decidir qual executar primeiro.

Um computador multiprogramado tem vários processos a serem executados simultaneamente, porém, para que todos os processos não tenham acesso à CPU de uma só vez e para que haja uma execução desses processos de forma justa, foi criada uma implementação para organizar tarefas. Esta implementação, ou seja, a parte do sistema operacional que cuida de qual processo será realizado antes ou depois, é chamado de escalonador ou agendador. O algoritmo que o escalonador usa é o algoritmo de escalonamento.

Nos sistemas antigos, que trabalhavam sequencialmente, praticamente estáticos, o algoritmo de escalonamento era bem simples. No caso dos sistemas em lote, era realizada apenas uma tarefa por vez. Com o avanço da informatização, e a necessidade de criação de sistemas mais interativos, foi necessário o desenvolvimento de outros algoritmos mais complexos, não visando somente à organização dos processos seletivamente, mas sim o melhor aproveitamento da CPU.

Tipos de escalonamento

     - Escalonamento preemptivo: tem como objetivo interromper o processo antes mesmo da finalização de sua execução, alternando entre níveis de prioridades. Sua implementação é mais complexa.

     - Escalonamento não-preemptivo: os algoritmos de escalonamento não-preemptivos são simples e mais fáceis de serem implementados, porém, não são adequados para sistemas de propósitos gerais com múltiplos usuários competindo.

Algoritmos de escalonamento

Assegurar que todos os processos recebam sua parte garantida na CPU, manter esta ocupada por 100% do tempo, minimizar o tempo de resposta e maximizar a vazão de serviços em menor intervalo de tempo, são critérios primordiais a serem seguidos para criar um bom algoritmo de escalonamento. Deve-se levar em consideração que o objetivo é de decisão sobre política, e não fornecer um mecanismo.

Escalonamento Round Robin

Também conhecido como escalonamento por alternância circular, o escalonamento Round Robin é um dos algoritmos mais antigos, simples e mais empregados. Os processos são organizados em uma fila e executados seguindo um intervalo de tempo (quantum), e não necessariamente a cada término de sua execução, ou seja, se um processo ainda estiver em execução ao final do quantum, outro processo entra e este vai para o final da fila aguardando a próxima rodada, como podemos ver na figura abaixo.

Agendamento Round Robin. (a) Lista de processos executáveis. (b) Lista de processos executáveis depois de B utilizar todo o seu quantum.

Para obter um melhor desempenho da CPU, a duração do quantum deve ser definida de forma que não seja muito curta nem seja longa demais. Esse cuidado deve-se ao fato de que ao alternar entre um processo e outro, a CPU requer uma quantidade de tempo para administrar: salvar e carregar registradores, etc. Em um intervalo de tempo muito curto ocorrem muitas comutações, ou seja, há muitas alternâncias de processos, o que reduz a eficiência da CPU. Um exemplo seria definir o quantum em 4ms e que o tempo gasto em administração da alternância dure 1ms. Nesse caso vinte por cento da CPU seria gasto em comutações de processos. Em outro caso, se fosse definido um intervalo de tempo de 100ms, mais longo, o tempo seria reduzido a um por cento, porém, significaria ter um tempo de resposta inadequado.

Escalonamento por prioridade

Priorizar os processos, atende justamente a necessidade de otimizar o trabalho da CPU, para tornar o sistema dinâmico, levando em consideração os dados recebidos pelos dispositivos de E/S.

A necessidade de levar em conta fatores externos, conduz ao agendamento de prioridade. A ideia básica é simples e direta: a cada processo é atribuído uma prioridade, e o processo executável com a maior prioridade recebe permissão para executar.

Os processos prontos com prioridades mais altas são escolhidos para utilizar a CPU, mas para evitar que esses processos monopolizem a CPU, são desenvolvidas alternativas que podem diminuir o nível de prioridade. Uma dessas alternativas seria configurar a prioridade como 1/f, onde f é a fração do último quantum que o processo utilizou. Por exemplo, se em um processo de quantum com 100ms levasse 5ms para processar, esse receberia prioridade 20 (vinte), enquanto um processo que executasse 20ms antes de bloquear, teria prioridade 5 (cinco), e um processo que ocupasse todo o quantum, receberia prioridade 1 (um). Outra alternativa seria agrupar classes de prioridades, com quantum definido para cada classe, e com o escalonamento Round Robin operando dentro delas. Um exemplo: em um sistema com quatro classes de prioridade, se existir processos com prioridade quatro, então são executados desconsiderando que haja outros processos de prioridade mais baixa. Se a classe quatro estiver vazia, então são executados os processos de classe três da mesma forma que a anterior e assim por diante.

Certo cuidado deverá ser tomado quanto ao ajuste dos níveis de prioridades mais baixas, podendo estas sofrerem inanição (morrer de fome) por nunca terem a chance de ser executados.

Algoritmo de agendamento com quatro classes de prioridade.

Múltiplas filas

Como visto no item anterior, no escalonamento por prioridade são criadas classes de prioridades, e dentro dessas classes poderia ser implementado o escalonamento Round Robin, puramente. No caso das múltiplas filas, cada classe pode receber uma política de escalonamento diferente, sendo que cada processo não permanece em uma mesma classe de prioridade mesmo que ainda não tenha sido completamente finalizado.

Esse mecanismo otimiza os níveis de prioridades de forma que os processos passam por um tipo de filtragem. Exemplo: um processo que necessita de cem quanta, teria que sofrer cem comutações utilizando o algoritmo Round Robin. Utilizando o mecanismo de múltiplas filas, o processo inicial receberia um quantum, e em seguida, em um processo abaixo, este receberia dois quanta, no próximo receberia quatro quanta e assim sucessivamente.

Atribuindo mais quanta a cada vez que os processos afundam nas classes de prioridade, evita-se que sofram inanição (morram de fome), além de maximizar a realização de processos em menores intervalos de tempo.

Menor serviço primeiro

É um algoritmo em lote que conhece previamente o tempo de execução de cada processo e dá privilégio de execução aos processos de curta duração, melhorando o tempo médio de resposta. No exemplo a seguir, dado um processamento inicial (a) com o tempo de cada processo reconhecido, o mecanismo calcula uma melhor sequência de processamento e então é feita a realocação do menor para o maior tempo (b). Tomando o exemplo de (a) como referência, temos os processos representados pelas letras A, B, C e D e os seus respectivos valores de tempo 8, 4, 4 e 4. Para calcular o tempo médio de execução utiliza-se a seguinte regra: (4A+3B+2C+D) / 4. Substituindo os valores de A, B, C e D, a expressão fica assim: ((4x8) + (3x4) + (2x4) + 4) / 4 = 14. Ordenando do menor para o maior, como o exemplo de (b), a expressão fica da seguinte forma: ((4x4) + (3x4) + (2x4) + 8) / 4 = 11. Neste último cálculo vimos que o tempo médio foi menor, e que a função desse algoritmo é exatamente dar prioridade aos processos de curta duração.

Exemplo de agendamento de job mais curto primeiro.

Escalonamento dirigido à política

Esse tipo de escalonamento faz com que o sistema operacional saiba de quanto tempo é necessário para executar cada operação. Feito isso o sistema operacional pode garantir que n usuários tenham uma porcentagem e atribui o quanto da CPU para cada um em uma proporção 1/n dando a eles a mesma quantidade de tempo de execução.

Dessa forma, torna-se realista prometer ao usuário a ter sua parte da CPU garantida, balanceando todos os recursos.

Havendo processos que utilizem uma quantidade de tempo inferior do que lhe foi atribuído, é feito o aumento do nível de prioridade. O mesmo acontece com processos que tenham utilizado um tempo superior.

Escalonamento em dois níveis

Nem sempre a memória principal é suficiente para comportar todos os processos. Às vezes é preciso manter algumas tarefas no disco. Um processo que esteja parcialmente na memória principal e parcialmente em disco pode comprometer o tempo de resposta, já que o tempo de comutação de processos em disco é muito maior do que o tempo de comutação da memória principal. Para melhorar a comutação em disco, uma solução seria utilizar o escalonamento em dois níveis: nível alto e nível baixo.

Inicialmente, divide-se o processo em subconjuntos, em seguida é feita a escolha de qual desses subconjuntos serão carregados na memória principal temporariamente.

O papel do nível alto tem a função de esvaziar a memória principal quando os processos estiverem em tempo suficiente e carregar os processos que estiverem muito tempo em disco. Enquanto o nível baixo restringe-se aos processos que estão carregados na memória principal e dedica exclusivamente em escolher entre esses processos, o nível alto dedica a fazer o transporte de processos memória ↔ disco.