Sobre escalonamento de processos
Em um computador com suporte à multiprogramação, frequentemente existem dois ou mais processos competindo pela CPU ao mesmo tempo. Quando mais de um processo está pronto para executar, o sistema operacional deve decidir qual deles vai ser executado primeiro e por quanto tempo.
A parte do sistema operacional que faz essa escolha é o escalonador, e o algoritmo que ele usa é chamado de algoritmo de escalonamento.
Introdução ao escalonamento
Na época dos sistemas de lote, o algoritmo do escalonador era simples: apenas executar o próximo job da fita. O tempo passou, a tecnologia cresceu exponencialmente em termos de hardware e software e hoje temos sistemas com multiprogramação.
Comportamento dos processos
Praticamente todos os processos alternam entre computação e requisições de E/S. Alguns usam mais a CPU, e outro mais o disco do computador.
Sabendo dessa informação, podemos notar que alguns processos passam a maior parte de seu tempo computando, e outros, esperando por E/S. Os primeiros são chamados de processos limitados por processamento (CPU-bound); os últimos são chamados de processos limitados por E/S (I/O-bound).
É interessante notar que, à medida que as CPUs se tornam muito rápidas, os processos tendem a ficar limitados por E/S — ou seja, de nada adianta ter uma CPU de última geração no computador, se o disco for lento — .
Quando escalonar?
Há uma variedade de situações onde o escalonamento pode ocorrer.
Nessas situações, o processo que estava em execução, não está apto a continuar, de modo que outro processo precisa ser escolhido para executar. Desta forma, o escalonamento deve acontecer:
- Quando um processo termina.
- Quando um processo é bloqueado em uma operação de E/S ou semáforo.
Nessas situações, o escalonamento é feito, mas não é absolutamente necessário nesses momentos:
- Quando um novo processo é criado.
- Quando ocorre uma interrupção de E/S.
- Quando ocorre uma interrupção de relógio.
No caso de um novo processo, é interessante reavaliar as prioridades nesse momento. Em alguns casos, um processo pai pode querer uma prioridade diferente para o processo filho.
No caso de uma interrupção de E/S, isso normalmente significa que um dispositivo de E/S acabou seu trabalho. Dessa forma, algum processo que estava bloqueado, aguardando pela E/S, poderá estar pronto para executar.
No caso de uma interrupção de relógio, essa é uma ótima oportunidade para decidir se o processo está atualmente executando, já está ali por tempo suficiente.
Categorias de algoritmos de escalonamento
Os algoritmos de escalonamento podem ser divididos em duas categorias, com relação ao modo que tratam as interrupções de relógio.
Não-preemptivo: Seleciona um processo para executar e, em seguida, permite que ele seja executado até ser bloqueado ou até que ele libere a CPU de forma voluntária.
Preemptivo: Seleciona um processo e o permite executa até um tempo limite. Se o processo estiver executando quando exceder o tempo limite, o escalonador suspenderá esse processo e liberará a CPU para outro processo (se houver).
Evidente que, em ambientes diferentes, são necessários diferentes tipos de algoritmos de escalonamento. É importante distinguir três ambientes:
- Lote;
- Interativo;
- Tempo real.
Em sistemas de lote, não há usuários esperando altas velocidades em seus terminais. Por isso, é aceitável o uso de algoritmos não-preemptivos ou algoritmos preemptivos com longos períodos de tempo para cada processo.
Em sistemas interativos (de propósitos gerais) e sistemas de tempo real (que executam somente os programas necessários) a preempção é fundamental.
Objetivos dos algoritmos de escalonamento
Para projetar um algoritmo de escalonamento decente, alguns objetivos devem ser alcançados. Alguns são específicos para os ambientes, outros são necessários em qualquer ambiente (como mostra a figura 1).
Sob qualquer circunstância, a imparcialidade é importante. Um processo A que seja semelhante a um processo B, deve receber o mesmo tempo de execução que o processo B receberá.
Outro objetivo geral é a aplicabilidade da política do sistema. Se o sistema disse que o processo A deve ser executado a qualquer momento, o escalonador deve ser capaz de executar essa política.
O último objetivo geral é manter a CPU ocupada o máximo de tempo possível, afinal, mantê-la ociosa significa desperdício de dinheiro.
Métricas
Gerentes dos centros de computação corporativos que executam muitas tarefas de lote, normalmente examinam 3 métricas para avaliarem o desempenho de seus sistemas:
- Taxa de saída (throughput): É a taxa da quantidade de jobs por segundo que o sistema conclui. Um algoritmo que maximiza a taxa de saída, não necessariamente é um bom algoritmo, levando em consideração que o escalonador pode escolher executar apenas jobs curtos e nunca os jobs longos. Isto é, embora tenha uma taxa altíssima de saída, alguns jobs poderiam nunca ser executados.
- Tempo de retorno (turnaround): Tempo médio desde o momento em que um job do lote é submetido até o momento em que ele é concluído. Quanto menor, melhor.
- Utilização da CPU: A utilização de CPU não é necessariamente a melhor métrica a ser analisada. Mas é importante para descobrir se a CPU está ociosa em algum momento.
Algoritmos de escalonamento
O primeiro a chegar é o primeiro a ser atendido
O mais simples de todos os algoritmos de escalonamento é, o não-preemptivo, primeiro a chegar é o primeiro a ser atendido (First Come, First Served — FCFS). Nesse algoritmo, os processos recebem tempo de CPU não ordem em que solicitam. É basicamente uma grande fila de jobs, cujo aquele em que estiver na frente executa usando o tempo que for necessário, ao terminar, volta pro final da fila.
É um algoritmo fácil de programar e de se entender. É imparcial e justo, afinal não faz distinção entre processos. Porém sua grande desvantagem é não saber gerenciar corretamente a ordem dos processos em relação ao uso de CPU e disco.
Por exemplo, imagine uma fila de processos. Nessa fila, existe um único processo (chamaremos de processo A) que execute 1s a cada vez e muitos processos limitados por E/S que utilizem pouco tempo na CPU. Agora o processo A é executado por 1 segundo e, em seguida, lê um bloco do disco. Nesse instante, todos os processos limitados por E/S começam a ser executados. Quando o processo A recebe novamente seu bloco de disco, executa mais 1s e esse processos circular se repete.
O resultado final é que cada processo limitado por E/S lê 1 bloco/s e demora 1000s para terminar. Se fosse usado um algoritmo de escalonamento que fizesse a preempção do processo A por processamento a cada 10ms, os processos limitados por E/S terminariam em 10s em vez de 1000s.
Tarefa mais curta primeiro
Esse algoritmo não preemptivo assume que os tempos de execução são conhecidos antecipadamente.
Quando várias tarefas igualmente importantes estão na fila esperando serem iniciadas, o escalonador escolhe a tarefa mais curta primeiro (Shortest Job First — SJF).
É interessante notar que esse algoritmo é ótimo apenas quando todos os jobs tem seus tempos conhecidos e estão disponíveis simultaneamente.
Menor tempo de execução restante
Uma versão preemptiva do algoritmo SJF é o menor tempo de execução restante (Shortest Remaining Time Next — SRT). Nesse algoritmo o escalonador sempre escolhe o processo (ou job) cujo tempo de execução restante é o mais curto. Toda vez que chega um novo processo uma comparação é realizada. Se o tempo de execução do novo processo for menor que a do processo corrente, este será suspenso e o novo processo será executado.
Escalonamento em três níveis
Os sistemas de lote permitem escalonar processos em três níveis diferentes, conforme a figura 4.
Quando os jobs chegam no sistema, são postos em uma fila de entrada armazenada em disco. O escalonador de admissão escolhe quem ingressará no sistema. Aqueles que não forem chamados, ficarão na fila aguardando.
Quando um job chega no sistema, um processo poderá ser criado para ele e poderá competir por CPU. Todavia, poderia ser que a quantidade de jobs fosse tão grande, que eles não seriam capazes de serem — simultaneamente — dispostos em memória. Nesse caso, alguns processos teriam de ser postos no disco.
O segundo nível de escalonamento é decidir quem fica na memória e quem fica no disco. Isso é chamado de escalonamento de memória.
Essa decisão precisa, frequentemente, ser revista para permitir que os processos que estão no disco recebam um tempo de memória. No entanto, essa tarefa é demorada, e por isso não deve ocorrer mais que uma vez por segundo. Se o swapping ocorre com muita frequência, implica em um consumo de uma grande quantidade de largura de banda de disco, diminuindo a velocidade de E/S dos discos.
Essa alternância entre estar em memória principal e estar armazenado no disco é denominado de swapping.
O terceiro nível de escalonamento é a seleção dos processos prontos, armazenados na memória RAM, para ser executada em seguida. Com certa frequência, ele é chamado de escalonador da CPU. Qualquer algoritmo pode ser usado aqui, seja preemptivo ou não preemptivo.
Round-Robin
Um dos algoritmos mais antigos, mais simples e mais amplamente utilizados. Nele, é feito um rodízio de processos (escalonamento round-robin RR). A cada processo é atribuído um intervalo de tempo chamado quantum, durante o qual ele pode ser executado. Se o processo estiver em execução durante o fim do quantum, é feita a preempção da CPU e nesta é alocada a outro processo.
O único problema desse algoritmo é a duração do quantum. A troca de um processo para o outro exige uma certa quantia de tempo para salvar o estado dos processos, os registradores, atualizar tabelas e afins.
Vamos imaginar que esse chaveamento de contexto dure 1ms, e o quantum tenha a duração de 4ms. Com esses parâmetros, a CPU depois de fazer 4ms de trabalho útil, ficará 20% do seu tempo ociosa, esperando o chaveamento do processo.
Novamente vamos exercitar a imaginação. Vamos supor que o chaveamento de contexto dure 1ms, e o quantum tenha a duração de 100ms. Agora o tempo desperdiçado é de 1%. Mas considere que dez usuários interativos apertem enter mais ou menos ao mesmo tempo. Se a CPU estiver ociosa, o primeiro processo começará automaticamente, o segundo depois do primeiro e por ai vai. O último, terá de esperar 1s antes de dar uma resposta para o usuário.
Com isso, podemos concluir que: se o quantum for curto demais, causa muita troca de processos e reduz a eficiência da CPU, se for muito rápido, causa um tempo de resposta alto para comandos curtos.
Um quantum de 20–50ms é, frequentemente, um compromisso razoável.
Escalonamento por prioridade
O escalonamento Round-Robin pressupõe que todos os processos tem o mesmo nível de prioridade. Em sistemas multiusuário, sabemos que essa não é a realidade. Como em uma escola, cuja prioridade máxima é a do diretor e a mínima, do aluno. A necessidade de levar em consideração esses fatores externos, conduz ao escalonamento por prioridade.
A ideia desse algoritmo é simples. Cada processo recebe uma prioridade, o processo pronto com maior prioridade é executado.
Para impedir que o processo de mais alta prioridade fique executando indefinidamente, o escalonador pode reduzir, a cada tique de relógio, a prioridade do processo. Se essa ação fizer com que a sua prioridade caia mais que a prioridade do processo que está aguardando, ocorrerá um chaveamento do processo.
Como alternativa, cada processo pode receber um quantum de tempo máximo em que ele pode ser executado. Quando esse quantum esgota, é dada a chance de executar ao próximo processo com maior prioridade.
Muitas vezes é conveniente agrupar processos em classes de prioridade e utilizar escalonamento por prioridade entre as classes. E dentro das classes, usar o escalonamento Round-Robin.
Conforme visto na figura 6, o algoritmo de escalonamento é o seguinte: enquanto houver processos executáveis na classe de prioridade 4, cada processo é executado por apenas um quantum. Se a classe 4 estiver vazia, quem será executada será a classe 3, e por ai vai. Se as prioridades não forem ajustadas ocasionalmente, as classes de prioridade inferior poderão nunca serem executadas.
Processo mais curto em seguida
Como o algoritmo da tarefa mais curta primeiro (SJF) sempre produz o menor tempo médio de resposta possível para sistemas de lote, seria interessante saber se ele pudesse ser usado para sistemas interativos.
Até certo ponto, sim, dá pra ser utilizado. Os processos interativos normalmente seguem o padrão de esperar um comando, executá-lo, esperar outro comando, executá-lo e por ai vai. Se considerássemos a execução de cada comando como um “processo” separado, poderíamos minimizar o tempo de resposta total, executando o processo mais curto primeiro (Shortest Process Next — SPN).
Escalonamento garantido
Uma outra estratégia completamente diferente de escalonamento é fazer promessas realistas aos usuário sobre o desempenho. Uma promessa simples de fazer e fácil de concretizar é prometer ao usuário cerca de 1/n do poder da CPU. De maneira similar, em sistemas monousuários com n processos em execução, todas as tarefas sendo iguais, cada um deve receber 1/n dos ciclos da CPU.
Para cumprir essa promessa, o sistema monitora o quanto da CPU cada processo recebeu desde sua criação. Em seguida, ele calcula quanto da CPU é atribuída a cada um, ou seja, o tempo desde a criação divida por n. Como a quantidade de tempo da CPU que cada processo realmente recebeu é conhecida, é simples calcular a proporção entre o tempo real da CPU consumido e o tempo atribuído. Ou seja, uma proporção de 0,5 significa que o processo só recebeu a metade daquilo que deveria receber, assim como a proporção de 2,0 significa que ele recebeu o dobro.
O algoritmo, então, é executar o processo com a proporção mais baixa até que sua proporção fique acima do seu concorrente mais próximo.
Escalonamento por sorteio
Fazer promessas aos usuários e cumpri-las na teoria é uma boa ideia, mas na prática é difícil de implementar. Entretanto, outro algoritmo pode ser utilizado para fornecer resultados previsíveis de maneira semelhante, e esse escalonamento é chamado de escalonamento por sorteio.
A ideia é dar aos processos tokens para vários recursos do sistema, como tempo de CPU. Quando uma decisão de escalonamento precisar ser tomada, um token é gerado aleatoriamente e o processo que possuir um token igual, recebe o recurso (igual bilhetes de loteria).
Conforme um processo tem mais prioridade que o outro, ele recebe mais tokens e assim, a probabilidade de ele ser o escolhido para ficar com o recurso aumenta.
Escalonamento com compartilhamento imparcial
Até aqui, supomos que cada processo é programado para executar por conta própria, sem levar em consideração quem é o dono do processo
Vamos imaginar uma situação. Se o usuário 1 inicia 9 processos, e o usuário 2 inicia 1 processo — com os algoritmos RR ou de prioridades iguais — o usuário 1 receberá 90% do tempo de CPU e o usuário 2, 10%.
Para evitar essas situações, o escalonador dividir uma fração da CPU para o dono dos processos, independente da quantidade de processos que eles tenham. Assim, se forem 50% da CPU para os dois usuários, o usuário 1 (com 9 processos) receberá 50%, e o usuário 2 (com 1 processo), 50%.
Referências
TANENBAUM, A. S. Sistemas Operacionais: Projeto e implementação. 3. ed. [S. l.: s. n.], 2008.
