Realidade e Ilusão

Conceitos em Linux (III)

3 - Multiprogramação:
O Linux é um sistema inerentemente multiusuário e multiprogramado. Isso significa que ele deve ser capaz de gerenciar vários usuários que concorrem pelo uso do sistema e vários programas (processos) que competem por recursos ou os compartilham. Por multiprogramação, entenderemos aqui a disputa de vários processos pelo uso do sistema, ou seja, há vários processos compartilhando uma ou mais CPUs e demais recursos de hardware. Quero aqui tratar do compartilhamento do tempo de CPU. Portanto vamos admitir que há apenas uma CPU disponível, o que não trará perda de generalidade, uma vez que este mecanismo é implementado no núcleo com uma interface por CPU (e respectivos bloqueios, que não tratarei agora).
O responsável pelo gerenciamento do compartilhamento de tempo entre os processos é o escalonador do núcleo. É o escalonador que determina que processo será executado e por quanto tempo. É importante que seja o núcleo a decidir isso e não os processos, ou algum processo poderia se apoderar indefinidamente do sistema. Sistemas que permitem que os processos executem até ceder deliberadamente a CPU são ditos de multitarefa cooperativa. É fácil notar que se algum processo do usuário estiver com problemas, o sistema inteiro está comprometido. Infelizmente, sistemas operacionais assim foram muito populares por um tempo. O Linux não sofre deste problema. Quem decide a execução é o núcleo e se o processo do usuário estiver com problemas, o núcleo pode deixar de agendar sua execução se assim o administrador o desejar. Sistemas que funcionam desta forma são ditos de multitarefa preemptiva (ou multitarefa real). No núcleo 2.6 até mesmo partes do núcleo podem ser escalonadas, melhorando muito a performance e o controle sobre o sistema.
Para um escalonamento adequado, o escalonador deve estimar de forma adequada de que maneira o processo utiliza o sistema para poder lhe dar um agendamento que satisfaça os usuários. Assim, podemos classificar os processos em duas categorias, processos orientados à entrada e saída (que doravante indicarei apenas por E/S) e orientados à CPU.
Processos orientados à E/S são processos que utilizam muitos procedimentos e recursos de E/S e por isso passsam muito tempo esperando os dados serem escritos ou ficarem disponíveis. Quando o processo fica ocioso nesta espera, é melhor que seja bloqueado, ou seja, que aguarde que os recursos fiquem disponíveis enquanto outro processo é executado. Afinal, você deve ter pago uma fortuna no seu processador e não quer que ele fique parado a maior parte do tempo só porque um processo resolveu esperar por dados de seu HD.
Processos orientados à CPU são processos que utilizam a CPU de modo pesado, realizando muita computação, ou seja, bloqueando-se pouco. O escalonador do Linux não “gosta” de processos usurpadores de CPU.
Obviamente, esta classificação é bastante subjetiva, pois todos os processos fazem uso de CPU e de E/S, não existe processo puramente orientados à CPU ou à E/S, mas podemos classificá-los assim se mantivermos nossas categorias como conceitos difusos.
Como exemplo de processo orientado à E/S posso citar este editor de textos no qual escrevo estas notas. Por mais rápido que eu digite, a CPU do meu laptop é rápida o suficiente para esperar durante uma eternidade pela próxima tecla a ser digitada. Ele pode muito bem bloquear enquanto outro processo executa, por exemplo o decodificador de mp3 que está neste momento transformando um arquivo em mp3 num fluxo de áudio. Se eu perceber interrupção no fluxo de áudio, vou ficar irritado. Seria capaz de eu fechar o editor e escrever à mão (para mim, sem música, sem trabalho).
Um exemplo de processo orientado à CPU é justamente o decodificador de mp3 que comentei. É claro que ele executa muita E/S (lê arquivo, manda arquivo decodificado para a placa de som, etc.) mas passa a maior parte do tempo decodificando mp3, o que utiliza muito a CPU.
Mas como o escalonador pode me manter feliz? Se eu perceber interrupção no áudio com certeza vou me irritar, mas se os caracteres que eu digitar começarem a demorar muito a aparecer na tela, ficarei igualmente contrariado. Resolver este impasse é justamente o objetivo do escalonador.
Para tanto, cada processo recebe uma prioridade de execução e uma fatia de tempo de CPU. Em princípio, o processo recebe uma prioridade inicial, atribuída pelo sistema ou pelo usuário. Após isso, o escalonador recalcula sua prioridade e respectiva fatia de tempo de acordo com sua orientação.
A prioridade de um processo é um valor que varia de 0 a 139. Os valores de 0 a 99 são reservados a processos que devem responder o mais imediatamente possível, por isso chamados de processos de “tempo real”. Aplicativos onde a resposta deve ocorrer em tempo crítico são classificados como de tempo real. Um exemplo é o processo responsável pela queima de uma mídia de DVD. Se ele demorar muito a ser executado, o buffer do dispositivo irá se esvaziar, haverá interrupção no laser que queima a mídia, a mídia será perdida e o usuário ficará nervoso com o escalonador.
Há dois tipos de filas de execução de tarefas de tempo real, as filas FIFO (primeiro a entrar, primeiro a sair) onde o processo de mais alta prioridade (valor mais próximo de 0) é executado até bloquear e ceder sua vez ao próximo da fila. Se não houver mais ninguém na fila correspondente a este valor de prioridade, um valor de prioridade mais alto é testado até todas as tarefas bloquearem. O outro tipo é a RR (Round Robin – se me permitem, seria algo como “escravos de Jó”?). Neste tipo, cada tarefa recebe uma fatia de tempo e as tarefas da fila de mais alta prioridade (valor mais próximo de 0) são executadas uma por vez, numa fila circular, cada uma durante uma fatia de tempo até que todas bloqueiem e uma nova fila seja pesquisada.
Desta maneira, o Linux não garante a entrega do serviço no tempo exigido, mas faz de tudo para cumprir a agenda.
As tarefas que não são de tempo real, classificadas como “outras”, tem valores associados de 100 a 139. Para o usuário, elas têm seu valor inicial (ou valor “bom” - nice) mapeadas de -20 a 19. -20 corresponde ao valor de mais alta prioridade e 19 ao de mais baixa. Por isso mesmo é que a tarefa ociosa é marcada com prioridade 19. O valor padrão é 0 e usuários não privilegiados só têm autorização para aumentar este valor, nunca diminuir. É por isso que tarefas marcadas com valores negativos são associadas com o superusuário.
Dentro de cada prioridade, forma-se uma fila onde cada processo recebe uma fatia de tempo. As filas são executadas na ordem de prioridade. Dentro de cada valor de prioridade, os processos correspondentes são executados até que todos eles sejam marcadas como expirados. Um processo é marcado como expirado quando esgota sua fatia de tempo. Esgotada sua fatia de tempo, o escalonador recalcula sua prioridade com base no seu uso de CPU. Se o processo bloqueou pouco (orientado à CPU), recebe uma penalidade e tem sua prioridade reduzida. Se o processo bloqueou muito (orientado à E/S), recebe um “bônus” e tem sua prioridade aumentada.
Uma vez que não há mais tarefas ativas, ou seja, todas foram marcadas como expiradas, troca-se a lista de expiradas pela de ativas (trocam-se seus ponteiros) e o sistema varre as listas de prioridade em busca do valor mais baixo (mais alta prioridade) para agendar sua execução.
É interessante notar que meu editor de texto tem uma alta prioridade e uma vez que se desbloqueie, tem prioridade sobre meu decodificador de mp3. Assim, eu digito a tecla, ela é processada quase imediatamente, meu editor bloqueia e meu decodificador pode voltar ao trabalho. Quando num futuro remoto (minha CPU trabalha a 1800 Mhz) eu digitar outra tecla, o decodificador terá me satisfeito disponibilizando fluxo de áudio por aquele período (e, espero eu, enchendo alguns buffers), terá sua execução interrompida, pois um processo de mais alta prioridade foi marcado como ativo (meu editor), este processa minha tecla, bloqueia (é marcada como TASK_INTERRUPTIBLE e chama o escalonador, para ser mais exato) e eu posso voltar a ouvir música.
Até este ponto do texto o escalonador foi capaz de me deixar feliz.
Assim funciona o escalonador do kernel 2.6. Ele é implementado como possuindo um mapa de bits de prioridades (140 bits), cada bit correspondendo a uma lista de tarefas. O funcionamento exato não importa aqui, apenas o fato de que a pesquisa pela próxima tarefa não depende do número de tarefas agendadas pelo escalonador. Ele executa seu código com tempo independente do número de tarefas no sistema. Isto foi um grande avanço com relação ao kernel 2.4, no qual esta pesquisa (todos os procedimentos envolvidos) dependia linearmente do número de processos.
As fatias de tempo destinadas às tarefas dependem de sua prioridade correspondente. As tarefas de mais baixa prioridade recebem fatias de tempo menores até um mínimo de 10 ms. As tarefas de prioridade mais alta recebem uma fatia que pode chegar a 200 ms, e um valor padrão de fatia é 100 ms. Todos estes parâmetros são configuráveis, de acordo com a necessidade do administrador do sistema. O que se deve ter em mente entretanto, é que uma fatia de tempo muito grande pode tornar o sistema perceptivelmente lento ao responder, ou seja, pouco interativo. Os processos de maior prioridade podem deter o uso da CPU tempo demais e o usuário pode vir a perceber que seu processo de baixa prioridade está demorando a responder (no meu caso, poderia fazer com que uma tarefa administrativa qualquer interrompa meu fluxo de áudio). Porém, uma fatia de tempo muito pequena faria com que o sistema perdesse muito tempo em trocas de contexto, ou seja, descarregando um processo com sua memória cache associada, descritores de arquivos, recursos adquiridos, etc. e carregando outro. O sistema passaria mais tempo efetuando trocas de processos na CPU do que efetivamente os executando.
Ao se criar um novo processo, o filho recebe metade da fatia de tempo do pai, que perde o valor de tempo correspondente. Assim evita-se que processos monopolizem o processador simplesmente criando filhos.
Quando vários processadores estão presentes (em processamento simétrico) há ainda uma função que verifica periodicamente o tamanho das listas de execução de cada processador, fazendo um “balanço” (retirando processos de um e inserindo para o outro), caso um deles esteja sobrecarregado com relação aos outros.
Vimos como o núcleo gerencia o compartilhamento de um dos recursos mais importantes de um sistema, o tempo. A análise do compartilhamento de outros recursos de hardware será postergada até que tenhamos visto como funciona um sistema mínimo, capaz de inicializar e administrar tarefas básicas. Penso que assim poderemos parar de perder tanto tempo com “tecnicalismos” e colocar a “mão na massa” mais cedo.

Para mais informações sobre o funcionamento e implementação do escalonador de processos no Linux, leia “Desenvolvimento do Kernel do Linux”, escrito por Robert Love (editora Ciência Moderna).
Para mais informações sobre implementação de escalonadores e gerenciamento de tarefas em sistemas operacionais de forma geral, leia “Sistemas Operacionais Modernos” (2ª ed.), por Andrew Tanenbaum (editora Prentice Hall).
Para informações gerais sobre hardware, software e configurações relacionadas ao Linux continuo recomendando:
www.guiadohardware.net
www.vivaolinux.com.br
Para um excelente guia de comandos e configurações recomendo:
www.guiafoca.org

Próximo tópico: muitos usuários.

Marcadores: escalonador, kernel, Linux, processo

posted by Luiz Henrique @ 23:10