Antes de apresentar os detalhes sobre Escalonador de Processos, gostaria de mostrar a definição de alguns termos e especificar alguns cenários que determinam qual o tipo de algoritmo de escalonamento de processos apresentará melhor desempenho.

Definição de Processo em Sistemas Operacionais

Processo é uma abstração do programa em execução. Mantêm a capacidade de operações pseudoconcorrentes, mesmo quando há apenas uma CPU disponível. Então quando me referir a um programa, em um sistema operacional, estamos falando do processo referente a esse programa. A CPU chavearia de programa para programa, executando cada um deles por dezenas ou centenas de milissegundos. A cada instante a CPU executa somente um programa, no decorrer de um segundo ela pode trabalhar sobre vários programas, dando aos usuários a ilusão de paralelismo.

Definição de Multiprogramação

Conceitualmente, cada processo tem sua própria CPU virtual. Na prática, a CPU troca, a todo momento, de um processo para outro. Portanto, um conjunto de processos executando paralelamente é conceitual quando há uma CPU apenas. O mecanismo de trocas rápidas, onde a CPU faz esses chaveamentos é a Multiprogramação.

Pronto, já sabemos o que é um processo. E como a CPU trata vários processos, através da multiprogramação,  quando diversos processos competem pela CPU e cabe ao Sistema Operacional decidir o momento em que cada processo obterá a CPU. Agora focaremos nos métodos de Escalonamento de Processos, mas cabe mais uma definição:

O que é Escalonador de Processos

Um Escalonador de Processos é um subsistema do Sistema Operacional responsável por decidir o momento em que cada processo obterá a CPU. É utilizado algoritmos de escalonamento que estabelecem a lógica de tal decisão. Nesse momento de decidir qual escalonador será utilizado no sistema operacional, cabe avaliar o cenário que o sistema será utilizado.

Deve-se ter cuidado com algumas variáveis como em casos que necessitam de mais processamento, ou seja, ação da CPU. Como com processos que necessitam de processamento, ocuparão a CPU por um tempo maior e não precisarão, ou de pouca, intervenção do usuário. Por exemplo, programas de cálculo científico, que o usuário insere parâmetros e executa o programa que demorará um determinado tempo para mostrar os resultados, isso exige processamento da CPU, com entrada e saída de dados apenas no momento inicial. Já processos que necessitam de mais entrada e saída de dados, ou seja, o processo necessita de intervenção do usuário. Por exemplo, ao digitar um texto, há entrada e saída de dados, logo, a resposta do ato de teclar e a resposta de aparecer isso na tela exige que esse processo "entra e sai" da CPU inúmeras vezes e em um pequeno espaço de tempo.

Acabamos de ver os dois diferentes comportamentos de processos. Aqueles orientados a Entrada e Saída (IN/OUT bound) e aqueles orientados a orientados a CPU (CPU bound).


Comportamento de Processos

Quando escalonar? 

Quando se faz necessário a escolha do próximo processo obter a CPU?

Agora sim, estamos no momento em que o sistema operacional toma a decisão de intervir ou não sobre qual processo ganhará a CPU. Apresentarei dois cenários de escalonamento:

O Escalonamento Não Preemptivo que ocorre apenas em situações que praticamente obrigam que uma decisão seja tomada. Esse cenário tem as seguintes condições: Criação de um novo processo; Término de um processo; Processo ser bloqueado; Após alguma interrupção.

E o Escalonamento Preemptivo que escolhe um processo e lhe concede a CPU durante certo tempo. Findado esse tempo, a CPU é de outro processo. Esse cenário tem as seguintes condições: Criação de um novo processo; Término de um processo; Processo ser bloqueado; Após alguma interrupção; Periodicamente, a cada k intervalos de relógio.

Categoria de Algoritmos de Escalonamento de Processos

O Escalonamento de Processos pode envolver diferentes tipos de requisitos, seguindo assim diferentes parâmetros e diferentes lógicas. É sugerida uma classificação segundo o tipo de sistema, o tipo de aplicação onde o algoritmo estará atuando. Segue os sistemas e seus objetivos:

Todos os sistemas possuem o objetivo geral de justiça, dar a cada processo uma porção justa da CPU; aplicação da política do algoritmo, verificar se a política estabelecida está sendo cumprida; equilíbrio, manter ocupada todas as partes do sistema.

Sistemas em Lote possuem o objeto de vazão (throughput), maximizar o número de Jobs por hora; tempo de retorno, minimizar o tempo entre a submissão e o término; utilização de CPU, manter a CPU ocupada por todo tempo.

Sistemas Interativos possuem o objetivo de tempo de resposta, responder rapidamente às requisições; proporcionalidade, satisfazer as expectativas dos usuários.

Sistemas de Tempo Real possuem o objetivo de cumprimento dos prazos, evitar a perda de dados; previsibilidade, evitar a degradação da qualidade em sistemas multimídia.

Entendimento do Algoritmo de Escalonamento de Processo de Sistema Interativo:

Escalonamento por Prioridades com Escalonamento Round Robin

Esse método é um misto entre o Algoritmo Prioridade e o Algoritmo Round Robin.

Falando sobre o Algoritmo Escalonamento Round Robin: Trata-se de um algoritmo para um escalonamento por alternância circular onde cada processo ganha um intervalo de tempo para uso contínuo da CPU (quantum), se ao final do quantum o processo ainda está processando, há preempção e outro processo será escolhido. Mas se houver bloqueio ou o processo terminou antes do fim do quantum, outro processo será escolhido. O dimensionamento do quantum é um detalhe sensível e merece observações futuras.

E falando sobre o Algoritmo por Prioridades: Cada processo possui uma prioridade. O processo pronto com maior prioridade ganha a CPU. Processo de mais alta prioridade deixaria a CPU somente quando quisesse. Pode-se baixar a prioridade do processo executando, a cada tick do relógio. Ou estabelecer um quantum máximo. A atribuição das prioridades dos processos pode ser estática ou dinâmica.

Então, falando sobre o Algoritmo de escalonamento por Prioridade + Round Robin: Define-se as classes de prioridade. Normalmente promove justiça apenas intra-classe.

A figura a seguir mostra a organização dos processos numa fila ordenada de tal forma que os processos com maior prioridade estão em cima, e conforme for diminuindo a posição na fila, diminui a prioridade dos processos. O funcionamento conforme o Algoritmo Roud Robin organiza os processos de uma mesma posição na fila de prioridades onde ao sair da CPU vai para o final da fila dentro desse grupo de prioridades.


Roud Robin com Prioridades

É isso. Nesse artigo, apresentei alguns conceitos importantes de Sistemas Operacionais e mostrei como o Sistema Operacional Moderno consegue executar vários programas e facilitar a usabilidade. Lembrando que estou me referindo ao cenário onde temos apenas uma CPU. Vale o comentário de que os computadores atuais trabalham com vários núcleos, o que seria trabalhar com várias CPUs. Mas isso, é uma deixa para as próximas pautas. Espero que tenha gostado. Até o próximo artigo.

Fonte: Modern Operating Systems - Andrew Stuart "Andy" Tanenbaum - third Edition