Gerência do Processador

Funções

Com o surgimento dos sistemas multiprogramáveis, onde múltiplos processos poderiam permanecer na memória e disputar o uso de um único processador, a gerência do processador tornou-se uma das atividades mais importantes em um sistema operacional.

A partir do momento em que vários processos podem estar no estado de pronto, devem ser estabelecidos critérios para definir qual processo será escolhido para fazer uso do processador. Tais critérios compõem a política de escalonamento, que é a base da gerência do processador e da multiprogramação em um sistema operacional.

Dentre as funções da gerência do processador, podemos citar: 

• Manter o processador ocupado a maior parte do tempo;
• Balancear o uso da CPU entre processos;
• Privilegiar a execução de aplicações críticas;
• Maximizar o throughput e;
• Oferecer tempos de resposta razoáveis aos usuários interativos.

Cada sistema operacional possui sua política de escalonamento adequada ao seu propósito e às suas características. Sistemas de tempo compartilhado, por exemplo, possuem requisitos de escalonamento distintos dos sistemas de tempo real.

Critérios de escalonamento

-          Utilização do processador: corresponde a uma taxa de utilização, que na maioria dos sistemas varia entre 30 e 90%. Uma utilização abaixo dos 30% indicaria um sistema ocioso, com carga de processamento baixa, enquanto uma taxa de utilização acima dos 90% pode indicar um sistema bastante carregado, próximo da sua capacidade máxima (em alguns casos tal situação pode levar a um crash – travamento do sistema).

-          Throughput: é o número de processos executados em um determinado intervalo de tempo. Quanto maior o throughput, maior o número de tarefas executadas em função do tempo. A maximização do throughput é desejada na maioria dos sistemas.

-      Tempo de Processador: é o tempo que um processo leva no estado de execução, durante seu processamento. As políticas de escalonamento não interferem neste parâmetro, sendo este tempo função apenas do código executável e da entrada/saída de dados.

-       Tempo de Espera (pela CPU): é todo o tempo que o processo permanece na fila de pronto, aguardando a liberação da CPU para ser executado. A redução deste tempo de espera é desejada pela maioria das políticas de escalonamento.

-          Tempo de Turnaround: é o tempo total que o processo permaneceu no sistema, desde sua criação até o momento em que é encerrado. São contados os tempos de alocação de memória, espera na fila de pronto e  interrupção (E/S).

-          Tempo de Resposta: é o tempo decorrido entre uma requisição ao sistema e o instante em que a resposta começa a ser exibida. Em sistemas interativos, como aplicações on-line ou acesso à Web, os tempos de resposta devem ser da ordem de apenas poucos segundos.

Escalonamentos Não-Preemptivos e Preemptivos

Escalonamentos do tipo não-preemptivos são aqueles onde o sistema operacional não pode interromper o processo em execução para retirá-lo da CPU. Assim sendo, se nenhum evento externo ocorresse durante a execução do processo, este permanecia na CPU até terminar ou então alguma instrução do próprio programa o desviasse para o estado de espera (operação de E/S).

Já os escalonamentos preemptivos são caracterizados pela possibilidade de o sistema operacional interromper o processo em execução para retirá-lo da CPU e dar lugar a outro. Neste caso o processo retirado da CPU volta ao estado de pronto, onde permanece aguardando nova oportunidade de ocupar a CPU. Com o uso da preempção, é possível ao sistema priorizar a execução de  processos, como no caso de aplicações em tempo real. Outro benefício é a possibilidade de implementar políticas de escalonamento que compartilhem o processador de uma maneira mais uniforme, balanceando o uso da CPU entre os processos.

São escalonamentos não-preemptivos:

-          FIFO: o processo que chegar primeiro à fila de pronto é selecionado para execução, e permanece utilizando o processador até terminar sua execução ou ser interrompido por E/S. Neste caso, o próximo processo da fila de pronto é selecionado para execução. Todo processo que chega à fila de pronto entra no final desta fila, conservando a ordem de chegada na fila, até ser escalonado novamente. Apesar de simples, este escalonamento apresenta algumas deficiências, principalmente no que diz respeito à dificuldade de se prever o início da execução de um processo, já que a ordem de chegada á fila de pronto deve ser observada à risca. Outro problema é quanto aos tipos de processo, onde os CPU-bound levam vantagem no uso do processador em relação aos do tipo I/O-bound, pois o sistema não trata este tipo de diferença. O escalonamento FIFO foi inicialmente implementado em sistemas monoprogramáveis, sendo ineficiente se aplicado em sistemas interativos de tempo compartilhado.

-          SJF (Shortest Job First): este  escalonamento seleciona o processo que tiver o menor tempo de processador ainda por executar. Desta forma, o processo que estiver na fila de pronto com menor necessidade de tempo de CPU para terminar o seu processamento será o escolhido para ocupar a CPU. Funciona com um parâmetro passado ao sistema via contexto de software, onde o tempo estimado para o processo é informado baseando-se em estatísticas de execuções anteriores.

Como exemplo, vamos utilizar os mesmos processos executados no escalonamento FIFO acima, com seus respectivos tempos de execução em u.t. (unidades de tempo): processo A com 10 u.t., processo B com 8 u.t, e o processo C com 9 u.t. Como neste escalonamento o que importa é o tempo de execução,  a nova ordem de escalonamento para utilização da CPU será B, C e A.

-          Cooperativo: este escalonamento busca aumentar o grau de concorrência no processador. Neste caso, um processo em execução pode voluntariamente liberar o processador retornando à fila de pronto, possibilitando que um novo processo seja escalonado, permitindo melhor  distribuição do tempo do processador. A liberação da CPU é uma tarefa exclusiva do programa em execução, que de maneira cooperativa libera o processador para um outro processo. Neste mecanismo, o processo em execução verifica periodicamente uma fila de mensagens para saber se existem outros processos na fila de pronto. Porém, como a interrupção do processo não depende do sistema operacional, situações indesejáveis podem ocorrer, como por exemplo, se um programa em execução não verificar a fila de mensagens, os demais programas não terão chance de executar enquanto a CPU não for liberada. As primeiras versões do Windows chegaram a utilizar este tipo de escalonamento.

-          Circular: é um tipo de escalonamento projetado especialmente para sistemas em tempo compartilhado. É muito semelhante ao FIFO (obedece a ordem de chegada á fila de PRONTO), mas quando um processo passa para o estado de execução há um limite de tempo para o uso contínuo do processador, chamado fatia de tempo (time-slice) ou quantum. Assim, toda vez que um processo é selecionado para execução uma nova fatia de tempo lhe é concedida. Caso esta fatia de tempo expire, o sistema operacional interrompe o processo, salva seu contexto e o direciona para a fila de PRONTO. Este mecanismo é conhecido como preempção por tempo. A principal vantagem deste escalonamento é não permitir que um processo monopolize a CPU. Outrossim, uma desvantagem é que os processos CPU-bound são beneficiados no uso do processador em relação aos processos I/O-bound, pois tendem a utilizar totalmente a fatia de tempo recebida. A figura a seguir mostra o escalonamento circular com 3 processos, onde a fatia de tempo é igual a 2 u.t. No exemplo não estão sendo levados em consideração tempos de troca de contexto entre os processos, nem o tempo perdido em operações de E/S. Os processos A, B e C, gastam 10 u.t, 6 u.t e 3 u.t., respectivamente.

 

São escalonamentos preemptivos:

-          Circular: é um tipo de escalonamento projetado especialmente para sistemas em tempo compartilhado. É muito semelhante ao FIFO (obedece a ordem de chegada á fila de PRONTO), mas quando um processo passa para o estado de execução há um limite de tempo para o uso contínuo do processador, chamado fatia de tempo (time-slice) ou quantum. Assim, toda vez que um processo é selecionado para execução uma nova fatia de tempo lhe é concedida. Caso esta fatia de tempo expire, o sistema operacional interrompe o processo, salva seu contexto e o direciona para a fila de PRONTO. Este mecanismo é conhecido como preempção por tempo. A principal vantagem deste escalonamento é não permitir que um processo monopolize a CPU. Outrossim, uma desvantagem é que os processos CPU-bound são beneficiados no uso do processador em relação aos processos I/O-bound, pois tendem a utilizar totalmente a fatia de tempo recebida. A figura a seguir mostra o escalonamento circular com 3 processos, onde a fatia de tempo é igual a 2 u.t. No exemplo não estão sendo levados em consideração tempos de troca de contexto entre os processos, nem o tempo perdido em operações de E/S. Os processos A, B e C, gastam 10 u.t, 6 u.t e 3 u.t., respectivamente.

-          Por Prioridades: funciona com base num valor associado a cada processo, denominado prioridade de execução. O processo com maior prioridade na fila de PRONTO é sempre o escolhido para ocupar o processador, sendo os processos com prioridades iguais escalonados pelo critério FIFO. Neste escalonamento o conceito da fatia de tempo não existe. Como conseqüência disto, um processo em execução não pode sofrer preempção por tempo. Neste escalonamento a perda do uso do processador somente ocorrerá no caso de uma mudança voluntária para o estado de espera (interrupção por E/S), ou quando um outro processo de prioridade maior passa (ou chega) para o estado de pronto. Neste caso o sistema operacional interrompe o processo em execução, salva seu contexto e o coloca na fila de pronto, dando lugar na CPU ao processo prioritário. Este mecanismo é chamado de preempção por prioridade. A figura a seguir mostra a execução dos processos A, B e C, com tempos de execução de 10, 4 e 3 u.t. respectivamente, e valores de prioridades de 2, 1 e 3, também respectivamente. Na maioria dos sistemas, valores menores correspondem à MAIOR prioridade. Assim, a ordem de execução será invertida para B, A e C.

          A prioridade de execução faz parte do contexto de software do processo, e pode ser estática (quando não pode ser alterada durante a existência do processo) ou dinâmica (quando pode ser alterada durante a existência do processo). Este escalonamento é muito usado em sistemas de tempo real, com aplicações de controle de processos, controle de tráfego (sinais de trânsito, de trens/metrô, aéreo), robótica, entre outros.

-          Escalonamento Circular com Prioridades: implementa o conceito de fatia de tempo e de prioridade de execução  associada a cada processo. Neste escalonamento, um processo permanece no estado de execução até que termine seu processamento, ou voluntariamente passe para o estado de espera (interrupção por E/S), ou sofra uma preempção por tempo ou prioridade. A principal vantagem deste escalonamento é permitir um melhor balanceamento no uso do processador, com a possibilidade de diferenciar o grau de importância dos processos através da prioridade (o Windows utiliza este escalonamento).

-          Por Múltiplas Filas: Este escalonamento implementa várias filas de pronto, cada uma com prioridade específica. Os processos são associados às filas de acordo com características próprias, como importância da aplicação, tipo de processamento ou área de memória necessária. Assim, não é o processo que detém a prioridade, mas sim a fila. O processo em execução sofre preempção caso um outro processo entre em uma fila de maior prioridade. O sistema operacional só pode escalonar processos de uma fila quando todas as outras filas de maior prioridade estejam vazias. Os processos sempre voltam para a mesma fila de onde saíram.

-          Por Múltiplas Filas com Realimentação: semelhante ao anterior, porém permitindo ao processo voltar para uma outra fila de maior ou menor prioridade, de acordo com seu comportamento durante o processamento. O sistema operacional identifica dinamicamente o comportamento de cada processo e o redireciona para a fila mais conveniente ao longo de seu processamento. É um algoritmo generalista, podendo ser implementado na maioria dos sistemas operacionais.