MULTITAREFA, THREADS, SEMÁFOROS
Email: Walter Chagas
Atualização: 05/05/2003

1) Definiçáo de Processos

É o ambiente onde se executa um programa. O processo é quem define o ambiente, os recursos, e os Buffers disponíveis à este. Nenhum programa é executado diretamente na memoria e sim dentro de um processo. Se não fosse isto, o programa poderia fazer uso indiscriminado de qualquer área de memória inclusive areas protegidas ou então efetuando operações de I/O indiscriminadamente em qualquer área aleatória do disco, provocando o maior balaio de gato no computador e comprometendo a integridade e a consistência dos dados. Daí conclui-se que é através do processo que o sistema operacional controla a execução, as permissões e as restrições que o programa terá quando estiver sendo executado, bem como os recursos que estarão e quando estarão disponíveis à ele.

1.1) Estados de um processo

Execução (Running):
Quando um processo está sendo processado pela CPU. Tais processos se revezam na execução.

Pronto (Ready):
Quando um processo aguarda que o sistema operacional aloque a CPU para sua execução.

Espera (Wait):
Quando um processo está aguardando algum evento externo para prosseguir com o processamento.

Quando um processo passa a maior parte do temp no estado de execução, a este chamamos de CPU BOUND. Este tipo de processo é muito comum em aplicações matemáticas, científicas e gráficas por efetuarem muitos cálculos. Quando o processo passa a maior parte do tempo em estado de espera e realizando muitas operações de I/O, a este chamamos de I/O BOUND. É o processo mais comum em aplicações comerciais.

2) Conceitos Ligados a Processos

2.1) System Calls

É um mecanismo que protege o núcleo do sistema operacional intermediando as chamadas dos aplicativos ao nucleo processando as solicitações e as respostas à estas solicitações. Suas funções básicas são:

- Gerencia de processos.
- Gerência de memória.
- Gerência de Entrada e Saída..

2.2) Metodos de acesso

É um mecanismo que monitora as instruções executadas pelos programas de forma que estes não executem instruções que possam comprometer a integridade tanto do sistema como dos dados. As instruções que podem comprometer o sistema são autorizadas apenas ao Sistema operacional e este irá intermediar as chamadas à estas instruções pelos aplicativos.

3) Hierarquia entre Processos

Um processo pode criar outros processos e que podem, por sua vez, criarem tambem outros processos de maneira hierárquica. Quando um processo (Processo pai) cria um outro processo, a este chamamos de subprocesso ou processo filho, e este subprocesso poderá criar subprocessos que podem criar outros subprocessos etc... gerando uma arvore hierárquica de processos. Este tipo de recurso evita que o usuario tenha que esperar que um processo termine para que sua requisiçao seja processada melhorando o desempenho do sistema. Se a hierarquia de processos possúi este benefício, ela consome recursos deste pois para cada processo será necessário a alocação dos referidos recursos de memória, buffers, etc, principalmente nos SO's atuais que são multitarefa e muitas vezes são obrigados a rodarem em maquinas domésticas e de recursos de hardware limitados, de forma que depois de um certo numero de subprocessos a situação se torna crítica gerando erros no sistema como podemos ver abaixo:

Figura 1

Quando voce manda executar um programa dentro de outro, na verdade voce está criando um subprocesso que é subordinado ao processo principal e assim por diante. Imagine a situação em que o Command.com é executado dentro do processo principal e os programas, que serão executados no prompt do DOS, em subprocessos. Neste caso imagine um programa que é carregado e neste programa tem uma opção "Ir para o DOS". Quando voce executar esta opção, será criado mais um subprocesso dentro deste subprocesso que está sendo executado o referido programa. Se, dentro deste ambiente do DOS voce executar algum outro programa voce nada mais estará fazendo do que criando mais um subprocesso.

Não confunda hierarquia de processos com multiprocessamento. O ambiente de multiprocessamento é aquele ambiente onde vários processos podem ser executados ao mesmo tempo, o chamado "Multitarefa".

4) THREAD's

Para resolver o problema da hierarquia de processos, foi criado o conceito de "Thread" onde um processo pode efetuar varias operações concorrentemente ou simultaneamente através das chamadas "Linhas de execução". Neste caso, o processo é dividido no numero de Threads sem que haja necessidade de ser criado um outro.

Desde que a IBM começou a promover o seu sistema operacional OS2 2.0 em 1991, ouvimos falar de "threads" e software "Multi-thread". Mas o que é este recurso?

Threads compartilham o processador da mesma maneira que um processo. Por exemplo, enquanto uma Thread espera por uma operação de I/O, outra Thread pode ser executada. Cada Thread tem seu proprio conjunto de registradores mas todas elas compartilham o mesmo espaço de endereçamento pois lembre-se que o processo é um só. As Threads passam pelos mesmos estados de espera que o processo, ou seja, Running, ready, wait.

Um programa "Multi-thread" pode estar sendo executado em vários locais ao mesmo tempo. E qual a vantagem disso? Vamos supor que um programa deseje imprimir um relatório. Enquanto o programa estiver enviando os dados para a impressora, a execução dele estará bloqueada. O usuário não poderá emitir novos comandos, inserir um novo registro por exemplo, enquanto a impressão não terminar. Um programa "Multi-thread" pode iniciar uma "Thread" para imprimir enquanto os resto do programa continua funcionando.

Mas qual a diferença de "Multi-thread" para Multi Tarefa? A diferença é que o Multi Tarefa requer que seja iniciado um outro processo caso se deseje a execução simultânea. Isto aumenta bastante a complexidade dos aplicativos e traz uma grande perda de performance.

Para efetuar troca de informações entre duas Threads de um mesmo programa, basta utilizar uma variável comum. Entre programas devem ser utilizados recursos mais sofisticados como arquivos comuns, filas, etc. As várias threadas podem ser codificadas em um mesmo fonte. Multiplos processos exigem a quebra do projeto em vários executáveis.

Iniciar uma Thread é uma tarefa barata para o sistema operacional, bem mais simples do que carregar um outro processo. Além disto, a troca de execução entre threads de um mesmo programa é feita com um mínimo de desperdício.

Figura 2

Figura 2 - Exemplo de uma thread, duas seções de copia de arquivos no Explorer são iniciadas simultaneamente. Isto somente é possível porque cadas seção corresponde a uma thread.

Uma interessante exemplo de como usar threads são as Dll's, procedimento este conhecido como API. Diversos fornecedores oferecem API's proprietárias que permitem que outros aplicativos sejam ampliados de uma maneira mais eficiente. Utilizando este método, a lógica é implementada por meio de um conjunto de funções de aplicativos que são empacotadas como bibliotecas compartilhadas na forma de DLL (Dynamic Linked Library) no ambiente Windows ou um SO (Shared Object) no ambiente UNIX/LINUX e que permitem, às funções do aplicativo, o acesso direto às estruturas de dados do sistema Operacional.

Por exemplo, no ambiente Windows, um aplicativo qualquer chama uma DLL através de um pedido de um recurso para o qual foi definida uma associação DLL/função. O sistema operacional aloca este pedido recebido em uma thread, que ficará em uma fila de espera. Quando chegar sua vez, será criada para ela, uma estrutura de dados sobre o pedido e este então começará a ser executado. Quando estiver completo, a thread será retornada ao pool de threads gerenciadas, até que sejam necessárias novamente.

Normalmente esta técnica tem um desempenho de até 5 vezes superior ao de um processo comum. A razão disto é muito simples. A chamada a um programa é substituída pelo carregamento de um objeto compartilhado (DLL) que normalmente é feito somente uma vez. Depois disto, este objeto permanece dentro do espaço de endereço do sistema operacional, e as sobrecargas se restringem às chamadas de função.

À estrutura de dados sobre o pedido, fornecida pelo sistema operacional para se comunicar com o objeto compartilhado, recebe o nome de ECB (EXTENSION CONTROL BLOCK) e consiste em um conjunto de variáveis, tanto de ambiente como oriundas do pedido e funções de chamada para suporte à geração da resposta. Cada pedido tem seu próprio ECB alocado e estes não se comunicam entre si em hipótese alguma. Em outras palavras, um ECB é a forma que o sistema operacional tem de compartilhar entre as threads, o conjunto de variáveis ambientes e também de disponibilizar dados que somente interessarão ao pedido sem que outro pedido tenha acesso à estes.

Outra grande diferença entre as threads e os processos é que cada processo tem seu proprio espaço de endereçamento enquando N threads compartilham um espaço de endereçamento de um único processo, otimizando o sistema e consumindo menos recursos dele, mas ai aparece também a grande desvantagem deste recurso pois, por causa desta característica (serem executadas no mesmo espaço de endereçamento), elas compartilham este espaço sem nenhuma proteção ou restrição o que permite que uma Thread possa alterar dados de uma outra ou vice versa. Com base nesta informação, voce pode concluir que para que uma aplicação possa funcionar eficientemente com threads, é preciso que haja mecanismos de sincronização robustos e consistentes e que possam ter controle total sobre a fila de threads que acessarão as funções e os recursos globais do servidor pois, um bug ou um erro lógico de programacão, pode criar um conflito entre duas ou mais Threads que acabaria detonando todas as outras e consequentemente derrubar o processo.

Figura 3

Figura 3 - 3 instâncias do Internet Explorer abertos simultâneamente. Isto somente é possível porque cada IE está sendo executada em uma thread separada.

5) Comunicação entre Processos

É comum processos trabalharem concorrendo e compartilhando recursos do sistema, como arquivos, registros, dispositivos e áreas de memória. Na verdade o importante é como estes processos irão usar e o que irão fazer com estes recursos. Um recurso mal usado ou usado indevidamente pode comprometer o sistema ou o próprio processo gerando falhas como podemos ver abaixo:

Figura 4

Um dos exemplos é de dois processos concorrentes que trocam informações através de operação de gravação e leitura em um Buffer. Um processo só poderá gravar dados no Buffer caso ele não esteja cheio, da mesma forma, um processo só poderá ler dados armazenados no Buffer se existir algum dado a ser lido.

Para gerenciar este compartilhamento de forma que dois ou mais processos tenham acesso a um mesmo recurso compartilhado, existe um mecanismo que controla este acesso, chamado de MECANISMO DE SINCRONIZAÇÃO. Este mecanismo tem o propósito de garantir a confiabilidade e a integridade da gravação dos dados, evitando que os dados armazenados fiquem sem consistência. Como exemplo dois processos efetuando operações de gravação, de dados diferentes, em disco exatamente no mesmo setor ou no mesmo arquivo. Esta situação se torna mais crítica ainda em sistemas operacionais MULTIPROGRAMÁVEIS.

Este conceito se aplica também aos subprocessos e as threads.

Na abordagem dos problemas de comunicação entre processos, são usados algoritmos nos programas que incorporam o mecanismo de sincronização e gerenciam este acesso. Um bom exemplo disto é quando desenvolvemos programas para trabalharem em rede onde você precisará fazer o bloqueio de um arquivo para usa-lo impedindo assim que outra estação de trabalho manipule aquele mesmo arquivo no momento em que você estiver usando-o.

Para que sejam evitados problemas desta natureza, onde dois processos manipulem o mesmo arquivo ou a mesma variável de memória simultaneamente, enquanto um processo estiver acessando determinado recurso, todos os outros que queiram acessar esse mesmo recurso deverão esperar. Isso se chama EXCLUSÃO MUTUA.

A exclusão mútua deverá agir apenas sobre os processos que estão concorrendo em um determinado recurso. Quando desenvolvemos um programa, que faça tratamento de exclusão mutua, este deverá terá uma seção chamada REGIÃO CRÍTICA. Nesta região existe uma serie de procedimentos e protocolos que o programa deverá fazer para que o sistema operacional libere o recurso para o mesmo. A região critica deve ser sempre usada quando seu programa for fazer uso de recursos que são passiveis de compartilhamento com algum outro suposto programa na memória. É nela também que os processos encontram-se em um momento mais critico, pois qualquer erro ocorrido ali dentro pode fazer com que dois ou mais processos colidam gerando falhas e derrubando o sistema . figura abaixo mostra uma falha ocasionada quando um processo apresentou problemas e acabou interferindo no funcionamento de outro:

Figura 5

6) Problemas de Sincronização

A tentativa de implementar a exclusão mútua nos programas traz alguns problemas com sincronização. As mais freqüentes são:

6.1) Velocidade de Execução dos Processos

Um dos problemas causados pela exclusão mutua é quando um processo mais rápido é obrigado à esperar que um lento use o recurso e o libere. Um gargalo gerado pela consistência dos processos onde o mais rápido ficará limitado à velocidade do mais lento. Conseqüência disto, o sistema todo fica lento comprometendo o seu desempenho.

6.2) Starvation

Quem determina as prioridades dos processos é o sistema operacional. Neste caso existem duas formas do sistema operacional determinar qual será a vez de quem. Ou por escolha aleatória ou por prioridades. Quando a escolha é aleatória, existirá a probabilidade de um processo nunca ser escolhido, quando for uma escolha por prioridades, um processo de menor prioridade nunca receberá o acesso ao recurso, e ai este processo nunca executará sua rotina.

6.3) Sincronização condicional

Quando um recurso não está pronto para ser utilizado, o processo que vai acessar o recurso ficará em estado de espera até que o mesmo esteja pronto. Existe o risco deste recurso nunca ficar pronto por já estar com problemas. Ai todo o sistema fica esperando o Recurso resolver sua vida. Um exemplo disto é o caso do uso de Buffers para leitura e gravação de dados feita pelos processos. Uma possível falha na memória que impeça o acesso aos buffers e todo o sistema está parado...

7) Soluções de Hardware

Também o hardware traz algumas soluções que ajudam a diminuir o problema da exclusão mútua dos processos:

7.1) Desabilitação de interrupções

Faz com que o processo, antes de entrar em sua região crítica desabilite todas as interrupções externas e a reabilite após deixar a região critica. Este mecanismo também traz seus inconvenientes. Se um processo entrou na região crítica e desabilitou todas as interrupções ao sair dela ele deverá HABILITÁ-LAS novamente sob risco de todo o sistema estar comprometido.

7.2) Instrução Test-And-Set

Instrução especial onde um processo apenas lê o conteúdo de uma variável, e armazena seu valor em outra área podendo neste caso fazer todas as manipulações necessárias e devidas sem precisar de prioridades ou esperar que a variável original seja liberada.

8) Soluções de Software

Além da exclusão mútua, que soluciona os problemas de compartilhamento de recursos, existem outros fatores fundamentais para a solução de problemas de sincronização:

- O número de processadores e o tempo de exxecução dos processos.

- Um processo fora de sua regiião crítica nnão pode impedir que outros processos entrem em suas próprias regiões críticas.

- Um processo não pode permaneecer indefiniidamente esperando para entrar em sua região crítica.

Todas as soluções que foram apresentadas para contornar estes inconvenientes apresentavam problemas da ESPERA OCUPADA, Na espera ocupada, todas vezes que um processo tenta entrar em sua região crítica ele são impedidas por já existir um outro processo usando o recurso, fazendo o sistema ficar parado esperando que o mesmo tenha acesso a este respectivo recurso.

8.1) Semáforos

O semáforo é uma variável que fica associada a um recurso compartilhado, indicando quando este está sendo acessado por um outro processo. Ela terá seu valor alterado quando o processo entra e quando sai da região crítica de forma que se um outro processo entrar em sua região critica ele possa checar antes este valor para saber se o recurso esta ou não disponível. Quando o processo tiver seu acesso impedido, ele será colocado em uma fila de espera associada ao semáforo aguardando sua vez de utilizar o recurso. Todos os processos da fila terão acesso ao recurso na ordem de chegada. O semáforo pode ser usado também para implementar sincronizações condicionais. Isto consiste em um processo que necessita ser notificado sobre a ocorrência de um evento. Pode-se usar o semáforo para notificar este processo sobre a ocorrência deste evento.

Outro tipo de semáforo usado é SEMÁFORO CONSUMIDOR onde ele pode informar ao processo se o buffer está cheio ou está vazio.

SEMÁFORO CONTADOR é aquele que notifica os processos sobre o uso dos recursos. Sempre que um processo usa um recurso qualquer, este semáforo é incrementado sempre que um processo liberar um recurso ele será decrementado. Este semáforo é útil para evitar que um processo na região crítica sem que hajam recursos disponíveis no sistema.

O uso de semáforos exige do programador muito cuidado, pois qualquer engano pode gerar bugs em seu programa que o levem a falhas de sincronização ocasionando quedas e travamento geral do sistema.

8.2) Monitores

São mecanismos de sincronização compostos de um conjunto de procedimentos, variáveis e estrutura de dados definidos dentro de um módulo cuja finalidade é a implementação automática da exclusão mútua entre seus procedimentos. Somente um processo pode estar executando um dos procedimentos do monitor em um determinado instante. Toda vez que um processo chamar um destes procedimentos, o monitor verifica se já existe outro processo executando algum procedimento do monitor. Caso exista, o processo fica aguardando a sua vez ate que tenha permissão para executa-lo.

A implementação da exclusão mútua nos monitores é realizada pelo compilador do programa e não mais pelo programador. Para isto ele irá colocar todas as regiões críticas do programa em forma de procedimentos no monitor e o compilador se encarregará de garantir a exclusão mútua destes procedimentos. A comunicação do processo com o monitor passa a ser feita através de chamadas a seus procedimentos e dos parâmetros passados para eles.

Outra característica do monitor é que os processos, quando não puderem acessar estes procedimentos, ficarão aguardando em uma fila de espera e enquanto isto, eles poderão executar outros procedimentos.

Como ele é escrito em uma linguagem de programação, o compilador das outras demais linguagens deverão ser capazes de reconhecê-la e implementa-la. São raras as linguagens que permitem tal implementação criando uma limitação para o uso deste recurso.

8.3) Troca de Mensagens

A troca de mensagens é um mecanismo de comunicação e sincronização entre os processos, implementado pelo sistema operacional através de duas rotinas do sistema SEND e RECEIVE. A rotina SEND é a responsável pelo envio de uma mensagem para o processo receptor enquanto a rotina RECEIVE por receber a mensagem do processo transmissor. Tais procedimentos mesmo não sendo mutuamente exclusivos permitem a comunicação entre os processos e a sincronização entre eles, pois uma mensagem somente poderá ser lida depois de ter sido enviada e ela somente será envidada após a ocorrência de um evento.

No sistema de troca de mensagens, existe a possibilidade da mensagem se perder. Para isto foi implementado o recurso de que o processo receptor ao recebe-la deverá enviar ao processo transmissor uma mensagem de recebimento. Caso o transmissor não receber esta mensagem em um certo espaço de tempo ele irá retransmitir esta mensagem.

A comunicação entre processos pode ser feita diretamente. Bastando que o processo que deseja enviar uma mensagem enderece explicitamente o nome do receptor. Esta característica chama-se ENDEREÇAMENTO DIRETO e só é permitida à comunicação entre dois processos.

Existe também o ENDEREÇAMENTO INDIRETO que é um mecanismo que consiste no uso de uma área compartilhada, onde as mensagens podem ser colocadas pelo processo transmissor e retiradas por qualquer processo.

Existem duas formas de comunicação entre os processos: COMUNICAÇÃO SINCRONA e COMUNICAÇÃO ASSINCRONA. Uma comunicação é dita Síncrona, quando um processo envia uma mensagem e fica esperando até que o processo receptor leia a mensagem e mande a notificação de recebimento. Uma comunicação assíncrona é aquela em que o processo que envia a mensagem não espera notificação de recebimento.

9) Deadlock

O Deadlock existe em qualquer sistema multiprogramável. Dizemos que um processo está em Deadlock quando este para de responder porque está esperando por um evento que nunca ocorrerá. Esta situação é conseqüência do problema da exclusão mútua. Existem as condições onde o Deadlock irá ocorrer:

- Cada recurso só pode estar aalocado a um único processo em um determinado instante. (Exclusão mútua)

- Um processo além dos recursoos já alocadoos, pode estar esperando por outros recursos.

- Um recurso não pode ser libeerado de um pprocesso porque outros processos desejam o mesmo recurso (Não-preempção)

- Um processo pode ter de espeerar por um rrecurso alocado a outro processo e vice-versa (Espera circular).

9.1) Prevenção de Deadlock

Para prevenir o Deadlock é preciso garantir que uma das quatro condições acima citada nunca ocorra, dentre as diversas situações já citadas pode ser feito um minucioso trabalho de determinar muito bem que recursos, quais recursos e quando estes recursos deverão ser disponibilizados aos processos.

9.2) Detecção de Deadlock

Em sistemas que não possuam mecanismos que previnam a ocorrência de deadlocks, é necessário um esquema de detecção e correção do problema. A Detecção do Deadlock é um mecanismo que determina a existência deste e identifica os recursos envolvidos no problema. Um Exemplo deste tipo de detector é o próprio Gerenciador de tarefas do Windows que detecta o aplicativo que parou de responder ao sistema causado, possivelmente, por um deadlock, como podemos ver logo abaixo:

Figura 6

9.3) Correção do Deadlock

Geralmente o problema é resolvido eliminando os processos envolvidos e desalojando os recursos para ele já garantidos. É aquele processo em que você dá um Alt+Cr+Del no Windows e aparece uma janela informando o aplicativo que não responde. Este aplicativo pode estar em um processo de Deadlock, neste caso você manda finalizar o aplicativo e tudo voltará ao normal. Muitas vezes este mecanismo não resolve e pelo contrário gera novos problemas. Se você finalizar um processo que esteja intimamente envolvido com o sistema operacional ou que esteja usando recursos de baixo nível do mesmo, você poderá vir a deixa-lo instável ou travado.

Abaixo vemos a caixa de dialogo do Windows que tentará fechar o processo que pode estar parado por falta de comunicação com o sistema.

Figura 7

O problema do Deadlock é um problema que tende a tornar-se mais critico à medida que os sistemas operacionais evoluem no sentido de implementar o paralelismo e permitir a alocação dinâmica de um numero maior de recursos e a execução de um numero maior de processos simultaneamente. Os usuários sentem muita saudade dos computadores que rodavam o DOS nos bons tempos quando quase não davam problemas. Mas é bom lembrar que o DOS era um sistema operacional monotarefa e monousuário onde praticamente tínhamos apenas um único processo rodando de cada vez. Neste caso não existiam os problemas que um ambiente multitarefa e multiusuário tem hoje. Todos os recursos do sistema estavam exclusivamente disponíveis para aquele processo e, portanto ele tinha total e plena liberdade de fazer com estes o que bem entendia. Hoje os sistemas operacionais são mais complexos rodando em maquinas mais críticas devido à velocidade de processamento tendo um maior numero de aplicações que rodam simultaneamente e demandando praticamente todos os recursos do sistema ao mesmo tempo. Muitos destes programas trabalham não só com um, mas com vários processos simultaneamente o que aumentam as chances de colisões entre eles ou com os recursos do sistema.