LFA – Escalonadores de Processos no Linux

No terceiro artigo da série, LFA ( Linux de uma Forma Acadêmica), vamos abordar, o que são escalonadores de processos, e de forma simples como funcionam os escalonadores no kernel Linux.

O escalonamento ocorre, segundo Tannebaum (2006, p 97) “[…] sempre que dois ou mais processos estão simultaneamente no estado de pronto. Se somente uma CPU se encontrar disponível, deverá ser feita uma escolha de qual o processo executará em seguida. A parte do sistema operacional que faz a escolha é chamada de escalonador […]”.

Os escalonadores de processos são funções executadas em conjunto pelo escalonador da CPU, com o algoritmo incluso no kernel do sistema, que determinam qual processo ou thread deve ter a atenção do processador naquele momento, porém essa não é uma tarefa fácil, pois nenhum algoritmo é a prova de falhas, podendo adequar-se a determinadas situações ou prejudicar em outras, para isso os escalonadores utilizam vários critérios para definir qual o melhor processo a ser trabalhado naquele exato momento como, a taxa de utilização de CPU, que é determinada pela fração de tempo que o processo irá utilizar (time slice) deixando assim a CPU ocupada, throughput que é a maximização do número de tarefas por unidade de tempo, turnaround que é o tempo transcorrido desde o momento em que o software entra e o instante em que termina sua execução, tempo de resposta que é o intervalo entre a chegada ao sistema e início de sua execução, tem-se também o tempo de espera que é a soma dos períodos em que o programa se encontra no seu estado pronto. Responsáveis por essa tarefa são algoritmos, que os sistemas operacionais utilizam e combinações deles para melhor escalonar os processos.

O sistema possui vários tipos de escalonadores, e esses são classificados em preemptivos e não-preemptivos, onde os primeiros são algoritmos que permitem que um processo seja interrompido durante sua execução, quer seja por força de uma interrupção de I/O, ou em decorrência da política de escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por força do término da execução do processo até mesmo a vontade do usuário. Após a interrupção deste processo, ocorre o que se chama de troca de contexto, que consiste em salvar o conteúdo dos registradores e a memória utilizada pelo processo e conceder à outro processo o privilégio de executar na CPU, restaurando assim o contexto deste último processo. cabe ressaltar que nos algoritmos não preemptivos, por serem utilizados exclusivamente em sistemas monoprocessados, isso não acontece, pois cada programa é executado até o fim, porém pode ser finalizado a qualquer momento pelo usuário.

Escalonando Processos no Linux

A responsabilidade do escalonador de processos do Linux é executar todas as tarefas em uma quantidade de tempo razoável, mantendo o uso correto dos recursos de hardware, ao mesmo tempo respeitando as políticas de prioridades, e execução.

O escalonador do kernel do Linux aborda uma variedade de sistemas pois o mesmo é utilizado nos mais diversos tipos de máquinas, provendo o escalonamento para arquiteturas SMP (multiprocessamento simétrico) quando é utilizado dois ou mais processadores para executar as tarefas simultaneamente.

Houve uma grande evolução da versão 2.4 para a versão 2.6 do kernel utilizada atualmente, uma das grandes evoluções foi a entrada da preempção. Outra mudança foi a correção de um bug do algoritmo de escalonamento onde quanto mais tarefas se tinha agendadas, mais difícil ficava para agendar outra tarefa e com isso o processador gastava muitos recursos com outras funções e pouco realmente processando o processo.

A cada interrupção do sistema, o kernel< atualiza várias estruturas de dados de contabilidade e realiza operações de escalonamento de acordo com o comportamento de um processo e ajusta dinamicamente sua prioridade, visando equalizar o uso do processador entre os processos. Processos que recentemente ocuparam o processador durante um período de tempo considerado longo, têm sua prioridade reduzida. O escalonador caracterizado como de tempo compartilhado, ou seja cada tarefa é executada até que a sua fatia de tempo, também chamada de quantum, expire, e um processo de prioridade mais alta torne-se executável ou o processo atual bloqueie.

O quantum de cada processo é medido em função da prioridade do mesmo, para evitar que haja intervalos de tempos muito pequenos, podendo assim atrapalhar o processamento desses, em contra partida também não pode ter intervalos de tempos muito grandes pois esses diminuiriam muito o tempo de resposta do sistema. Com isso o algoritmo de agendamento do escalonador de processos no do Linux trabalha com intervalos de tempo múltiplos de 10, entre 10 microssegundos e 100 microssegundos. Se uma tarefa sofrer preempção, seu processamento é parado, assim entra no estado onde espera algo ocorrer ou um processo de maior prioridade ser terminado para voltar o seu processamento normal.

Escalonamento por Prioridades

No Linux a prioridade de uma tarefa, afeta o tamanho da sua fatia de tempo ou quantum, se ela é de tempo real ou não, também afeta a ordem que o escalonador as executam no processador. Existem dois tipos de prioridades que o escalonador de processo do Linux trata, a estática e a dinâmica. A estática é usada exclusivamente pelos processos de tempo real e possuem o valor de 1 a 99, definido pelo o usuário. Assim que o processo é aberto, não pode ser modificada pelo o escalonador, lembrando sempre que apenas usuários com prioridades específicas podem criar e definir processos em tempo real.

As prioridades dinâmicas são processos interativos. Sua prioridade é calculada baseada na prioridade padrão do processo e na quantidade de tempo que ainda resta para ele ser processado. O escalonador só processa tarefas com a prioridade dinâmica, apenas quando não há tarefas em tempo real, com isso os processos com prioridade estática possuem maior prioridade que os dinâmicos.

Políticas de Escalonamento

O kernel utiliza três diferentes políticas de escalonamento, para selecionar um processo em questão.

A primeira é o escalonador FIFO (First In First Out), essa política é válida apenas para processos de tempo real e prevê, quando um processo é alocado ao processador, ele executa normalmente até que uma de quatro situações ocorra: um processo também de tempo real e de prioridade mais alta for apto a ser executado, assim o processo cede o processador para essa nova tarefa, ou o processo libera espontaneamente o processador para um processo de prioridade igual à sua, ou o processador é bloqueado em uma operação de entrada e saída e na última hipótese, o processo termina.

Segundo Deitel (2005, pag 205), “[…] O FIFO não é útil para escalonar processos interativos, pois não pode garantir tempo de respostas curtos . O FIFO raramente é utilizado como esquema mestre nos sistemas de hoje, mas é frequentemente encontrado dentro de outros esquemas[...]”.

Outra política existente é o escalonador RR (Round-Robin) comumente utilizado em sistemas de tempo compartilhado. O sistema operacional determina uma quantidade de tempo o quantum, que diz o tempo que o processador terá para trabalhar com o processo e é criada uma fila circular onde os processos serão incluídos. Com isso cada tarefa da fila é trabalhada até que o seu quantum expire e o sistema as pare, sofrendo assim a preempção, e logo em seguida a próxima toma o lugar, fazendo isso até que todas sejam finalizadas. Essa política também é usada apenas em processos de tempo real. Segundo Deitel (2006, p. 216).

“[…] A alternância circular é efetiva para ambientes interativos nos quais o sistema precisa garantir tempos de resposta razoáveis. O sistema pode minimizar a carga de preempção por meio de mecanismos eficientes de chaveamento de contexto e mantendo os processos à espera na memória principal […]”.

A última política trabalha com os processos estáticos é apenas uma fila com vários níveis de prioridades dinâmicas com tempo compartilhado para cada processo e é chamada de sched_orther.

Fica a dica.