Introdução:

 

            Os sistemas de computadores atualmente permitem que vários programas sejam colocados na memória e executados simultaneamente. Com isso, a divisão de tarefas entre os diversos programas, tem que ser feita com um maior controle. Para atender as estas necessidades foi definido o conceito de processo que é a unidade de trabalho em um sistema moderno de tempo compartilhado. Informalmente, um processo é um programa, que contém várias instruções, em execução. Uma instrução é um comando em linguagem de máquina, gerado por um interpretador ou compilador, que é executado pela CPU. A execução das instruções do programa é feita de forma seqüencial, instrução após instrução e, em um dado tempo, somente uma instrução de um determinado processo pode ser executada.

 

Os processos são classificados pelo sistema operacional de acordo com o estado que está ativo. O diagrama, abaixo, mostra os estados possíveis de um processo no sistema.

 

           

Os sistemas operacionais multiprogramados, que procuram maximizar o uso da CPU executando processos até que eles tenham que esperar pelo término de alguma operação de E/S, utilizam o escalonador da CPU que é um programa que escolhe, por algum algoritmo, o processo que será executado no processador.

 

 

 

Os mecanismos de alocação para os processos são preemptivos e não-preemptivos.

 

            A alocação preemptiva desaloca a CPU de um processo para outro, na fila de processos prontos, quando um tempo (quantum) definido pelo sistema operacional termina (controle limitado da CPU). Já, para a alocação não-preemptiva um processo tem o controle da CPU até que este termine ou o seu estado mude para espera (bloqueado).

 

            Os processos podem ser divididos em classes ou grupos. Abaixo, seguem alguns exemplos:

 

-          Sistema que desempenham uma tarefa do sistema operacional como paginação ou segmentação, dependendo do sistema de gerenciamento de memória do sistema.

-          Interativos são processos criados pelos usuários e interagem diretamente com estes no sistema.

-          Convidados são processos de um tipo de usuário do sistema que não utilizam de maneira freqüente o sistema operacional.

 

            Os critérios que podem ser usados para a escolha do melhor algoritmo de alocação da CPU para as classes de processos são:

 

-          Utilização da CPU: A CPU deve ser ocupada a maior parte possível do tempo;

-          Produtividade: Se a CPU estiver sendo utilizada, este trabalho deve ser útil;

-          Tempo de processamento: Soma do tempo de espera para o processo ser alocado na memória, do tempo de espera na fila de processos prontos, tempo de execução pela CPU e tempo gasto com E/S;

-          Tempo de espera: Soma dos tempos do processo na fila de processos prontos.

-          Tempo de resposta: tempo para se produzir algum resultado e não o resultado inteiro (intervalo de tempo entre a requisição e a primeira resposta).

 

 

 

Os algoritmos de alocação da CPU para os processos na fila de processos prontos são:

 

-          FIFO: O primeiro processo a entrar na fila de processos prontos será o primeiro a ser escolhido para execução.  O tempo de espera deste algoritmo é longo e esse diminui o uso da CPU e dos dispositivos de E/S. É não-preemptivo.

-          SJF: Associa a cada processo a duração de sua próxima fase de uso da CPU. A CPU é alocada, quando disponível, ao processo com menor duração da próxima fase de uso. O tempo de espera do algoritmo é ótimo (melhor tempo de espera entre os algoritmos). É ideal para alocação de processos que demandam muito tempo de processamento. Pode ser preemptivo e não-preemptivo.

-          Prioridade: Atribui prioridades aos processos conforme limites de tempo, razão entre os números de fases de uso de E/S e uso da CPU, requisitos de memória dentre outras definições. A alocação na CPU se dá, geralmente, na ordem menor para maior prioridade. Favorece a alocação de alguns processos em detrimento de outros, com isso, pode ocorrer abandono de processos. Pode ser preemptivo e não-preemptivo.

-          Circular (Round-Robin): Determina um pequeno intervalo (quantum) de tempo de uso da CPU aos processos na fila circular de processos prontos. Este algoritmo é imparcial na distribuição de tempo de uso da CPU; mas possui um tempo de espera grande. É preemptivo.

-          Filas: Dividem os processos em classes que possuem uma hierarquia (a divisão pode ser feita por interação com o usuário, prioridade no sistema operacional e outras). Cada classe fica em uma fila. Beneficia os processos de classes superiores; mas pode haver uma variância deste algoritmo que permite que um processo seja transferido de uma fila para outra conforme este fique “velho” (muito tempo numa fila). É preemptivo.

 

Os algoritmos têm características diferentes e, por isto, podem favorecer um ou outro grupo de processos.

 

 

O escalonamento da CPU pelo sistema operacional LINUX:

 

            Este sistema operacional divide os processos em duas classes:

 

-          Processos de tempo real que precisam ser executados cumprindo requisitos temporais e lógicos com baixa prioridade (preferência para serem executados na CPU). Os processos do sistema operacional são exemplos destes processos.

-          Processos interativos e batch são tarefas criadas pelos usuários do sistema (processos interativos) ou programas executados em segundo plano no sistema operacional (batch). Estes processos são “inferiores” aos processos de tempo real, logo possuem prioridades mais altas. A execução de um editor de textos é um exemplo de processo interativo.

 

A prioridade do processo é classificada como estática e dinâmica.

 

A prioridade estática, somente para processos de tempo real, determina uma ordem de preferência de execução na CPU entre os processos desta classe.

 

A prioridade dinâmica, para processos interativos e batch, é relativa ao tempo de processamento dos processos na CPU. Os processos que demandam muito tempo de CPU têm a sua prioridade diminuída para execução quando colocados, novamente, na fila de processos prontos.

 

Observações:

- Um processo de prioridade estática tem sempre preferência para executar na CPU mesmo que haja processos de prioridade dinâmica na fila de processos prontos desta classe.

- A prioridade dos processos de tempo real pode ser modificada, somente, por usuários especiais como o administrador do sistema.

O Linux é time-sharing (divide o tempo de execução entre os processos) e usa os algoritmos FIFO e Round-Robin para escalonar os processos de tempo real com prioridade estática; e filas de vários níveis para os processos interativos e batch com prioridade dinâmica.

 

Os processo de tempo real não tem as suas prioridades modificadas pelo escalonador da CPU; mas, os processos interativos e batch têm suas prioridades “aumentadas” (menor prioridade para execução) se esses utilizam a CPU muitas vezes. Isto ocorre, à medida que são colocados várias vezes na fila de processos prontos.

 

O trabalho no kernel do Linux:

 

                        A nossa proposta de trabalho é implementar três algoritmos de alocação de CPU não existente na classe de processos interativos e batch no sistema operacional Linux. Temos por objetivo diminuir o tempo de espera e de processamento para todos os processos desta classe no sistema que demandam maior utilização da CPU, sem comprometer a execução dos processos de tempo real. Esperamos que processos de usuários como, por exemplo, consultas “pesadas” à banco de dados on-line (WEB) mostrem o resultado mais rápido mantendo o sistema estável e sem abandono de processos, ou seja, os processos de tempo real e processos interativos e batch não que demandam muito tempo de CPU continuem sendo executados.

 

                        Definimos que implementaremos o algoritmo SJF, que possui tempo de espera ótimo e é indicado para processos que demandam muito tempo de processamento, e os outros dois algoritmos ainda não foram definidos; mas, serão dentre os descritos acima ou variações destes buscando o mesmo objetivo que foi feito na escolha do algoritmo SJF.

 

                        Para avaliar os resultados vamos implementar um algoritmo de cada vez no kernel do Linux, executar aplicações de usuários que demandam muito e menos tempo de CPU, e depois, comparar estes resultados com o Linux original.

 

Referências:

 

·         Silberschatz, Abraham e Galvin, Peter – Sistemas Operacionais Conceitos.

·         Oliveira, Carissimi, Toscani – Instituto de Informática UFRGS.

 

 

 

Free Web Hosting