Processos e Soluções de Software

Os processos precisam freqüentemente se comunicar com outros processos. Por exemplo, num pipe do shell, a saída do primeiro processo precisa ser passada à entrada do segundo, e assim por diante, ao longo de todo o pipe. Existe, portanto, a necessidade de haver comunicação entre tais processos, preferencialmente de uma forma estruturada, que não seja baseada em interrupções. Nas seções seguintes, vamos examinar alguns aspectos relativos à comunicação entre processos, conhecida pela sigla IPC (InterProcess Communication).

Em alguns sistemas operacionais, processos que estão trabalhando em conjunto muitas vezes utilizam uma memória comum, onde cada processo pode ler ou escrever.

A memória compartilhada pode ser a principal ou pode ser um arquivo em disco, sendo que a natureza da memória compartilhada não influi de forma alguma na natureza da comunicação nem nos problemas que são criados. Para se ter idéia de como a comunicação entre processos funciona na prática, vamos considerar um exemplo bem simples e bastante comum, um spool de impressão.
Nos assuntos onde a Lei de Murphy pode ser aplicada, pode e deve ocorrer o seguinte: o processo A lê e armazena o valor lido 7, num variável local próxima_entrada_livre. Exatamente após esta operação ter sido concluída, ocorre uma interrupção de tempo, significando que o processo A já rodou o suficiente, devendo portanto ceder o processador para o processo B.

Este lê o valor de in, obtendo o valor 7, mesmo valor que A obteve quando realizou a leitura. Desta forma, B guarda o nome do seu arquivo de impressão na entrada 7 do diretório, e atualiza o valor de in 8. Após isto, ele continua seu processamento normalmente.
Já sabemos que em algum momento seguinte, o processo A vai reiniciar seu processamento no exato ponto onde houve a interrupção. Ao examinar o valor de sua variável local próxima_entrada_livre, encontra 7 armazenado nela, e escreve o nome de seu arquivo de impressão na entrada 7 do diretório, apagando o nome do arquivo escrito anteriormente por B, e ainda não impresso. Depois disso, o processo atualiza o valor de in para 8 e continua seu processamento. Observe que o diretório de spool está consistente, de forma que o processo impressor não vai notar nada de errado na estrutura do diretório.

Ocorre que o processo B nunca vai ter sua saída impressa. Situações como esta, onde dois ou mais processos estão acessando dados compartilhados, e o resultado final do processamento depende de quem roda quando, são chamadas de Condições de Corrida. A análise de programas em que ocorrem condições de corrida não é uma tarefa fácil. Os resultados da maioria dos testes são consistentes com a estrutura do programa, mas de vez em quando ocorre algo imprevisto e inexplicável, em função do não-determinismo potencial, causado pelas condições de corrida.
Como evitar a ocorrência de condições de corrida? A questão-chave para evitar problemas em casos envolvendo qualquer tipo de compartilhamento de recursos (memória, arquivo, e tudo o mais) é encontrar alguma forma de proibir que mais de um processo acesse o dado compartilhado ao mesmo tempo (pseudoparalelismo ou paralelismo real). Em outras palavras, precisamos encontrar um meio de implementar a exclusão mútua de execução – uma forma de se ter certeza de que se um processo estiver usando uma variável ou um arquivo compartilhados, os demais serão impedidos de fazer a mesma coisa.

A dificuldade identificada no exemplo acima vem do fato de o processo B ter começado a usar uma das variáveis compartilhadas antes que o processo A tenha terminado de usar esta mesma variável. A escolha das operações primitivas adequadas à implementação da exclusão mútua de execução é um dos grandes desafios no projeto de qualquer sistema operacional. O assunto será examinado em detalhes nas seções seguintes.
O problema de se evitarem as condições de corrida pode também ser formulado de modo abstrato. Parte do tempo, um processo está ocupado realizando um processamento que não resultará em condição de corrida, por não estar manipulando dados ou arquivos compartilhados. No entanto, em outros momentos, o processo pode estar acessando um parte da memória ou um arquivo compartilhado com outros processos ou realizando algum outro tipo de tarefa crítica que possa vir a levar a ocorrência de condições de corrida.

Esta parte do programa, cujo processamento pode levar à ocorrência de condições de corrida, é denominada região crítica ou seção crítica. Se pudermos arranjar as coisas de forma que não seja nunca permitido que dois ou mais processos estejam processando suas seções críticas correspondentes ao mesmo tempo, poderemos evitar a ocorrência das condições de corrida.
Apesar do esquema descrito acima evitar a ocorrência das condições de corrida, ele não é suficiente para permitir que processos paralelos cooperem correta e eficientemente no uso de recursos compartilhados. É necessário que quatro condições sejam atendidas para que tenhamos uma boa solução para o problema:

1.Dois ou mais processos não podem estar simultaneamente dentro de suas regiões críticas correspondentes.
2.Nenhuma consideração pode ser feita a respeito da velocidade relativa dos processos, ou a respeito do número de processadores disponíveis no sistema.
3.Nenhum processo que esteja rodando fora de sua região crítica pode bloquear a execução de outro processo.
4.Nenhum processo pode ser obrigado a esperar indefinidamente para entrar em sua região crítica.

A solução mais simples para tal problemas é obtida fazendo com que cada processo iniba as interrupções logo após seu ingresso em uma região crítica, habilitando-as outra vez imediatamente antes de deixá-la. Com as interrupções inibidas, o processo não poderá ser interrompido por exceder o tempo de processamento concedido a ele. Como o processador só pode ser chaveado entre processos através de interrupções de tempo, com as interrupções inibidas não haverá chaveamento. Então, uma vez inibidas as interrupções, o processo pode examinar e atualizar a memória compartilhada, sem se preocupar com a eventual intervenção de outro processo em seu processamento.

Inibir interrupção é uma função útil, se só puder ser realizada dentro do kernel, não sendo apropriada para servir como mecanismo para implementação de exclusão mútua de execução entre processos de usuários.
Como segunda tentativa de implementação de exclusão mútua de execução, vamos examinar uma solução implementada por software. Considere a existência de uma única variável compartilhada (variável de travamento), cujo valor seja inicialmente 0. Quando um processo desejar entrar em sua região crítica, ele deve primeiro testar a variável de travamento. Se ela for 0, o processo muda seu valor para 1 e entra na região crítica. Se o valor da variável já for 1, o processo deve esperar que ele volte a 0, antes de entrar na região crítica. Nesta solução, o valor da variável de travamento em 0 significa que não há nenhum processo executando a sua região crítica, e o valor em 1 significa que algum processo está executando sua região crítica.

Infelizmente esta idéia incorre na mesma falha. Suponha que um processo leia a variável de travamento e verifique que seu valor é 0. Antes que ele possa atualizá-lo para 1, ocorre uma interrupção, e outro processo é posto para rodar. Tal processo encontra a variável de travamento em 0, atualiza seu valor para 1 e entra na sua região crítica. Ocorre que o processo interrompido guardou em seu contexto o valor 0 para a variável de travamento, de modo que, quando ele for reativado, atualizará seu valor para 1 e executará sua região crítica. Observe então que dois processos poderão estar executando suas regiões críticas correspondentes ao mesmo tempo.
Uma terceira forma de abordar a questão da exclusão mútua é o trecho de um programa escrito em C:

A variável inteira turn, inicialmente em 0, estabelece de quem é a vez de entrar na região crítica. Primeiramente, o processo 0 inspeciona turn, encontra seu valor em 0 e entra em sua região crítica. O processo 1 também encontra turn em 0, entrando em um loop, que testa continuamente o valor de turn, aguardando que ele se torne igual a 1. O teste contínuo do valor de uma variável, aguardando que ela assuma determinado valor é denominado de espera ocupada. A espera ocupada deve ser evitada, em razão de consumir tempo de processador. Somente nos casos em que houver uma razão muito forte para supor que a espera será muito curta é que devemos usar a espera ocupada.

Quando o processo 0 deixar sua região crítica, ele faz com que turn assuma o valor 1, para permitir que o processo 1 entre em sua região crítica. Suponha que o processo 1 termine rapidamente a execução de sua região crítica, fazendo com que ambos os processos estejam fora de suas regiões críticas, com turn igual a 0. O processo 0 executa seu loop rapidamente, retornando à sua seção não-crítica fazendo turn igual a 1, e voltando para o início do loop. Infelizmente ele não pode executar sua região crítica, mesmo com o processo 1 em seu trecho não-crítico, pois turn vale 1. Podemos concluir que a estrita alternância de processos executando suas regiões críticas não é uma boa idéia quando um dos processos é muito mais lento que o outro.
Esta situação viola a condição 3 estabelecida acima, pois o processo 0 está sendo bloqueado por um processo que não está em sua região crítica. Tal solução não é viável na prática.
Combinando a idéia de estabelecer a vez dos processos entrarem em suas regiões críticas, com a da variável de travamento e com a de uma variável de tensão, um matemático holandês, T. Dekker, foi o primeiro a criar uma solução em software para o problema da exclusão mútua (1965). Em 1981, G. L. Petersen descobriu uma forma muito mais simples que a de Dekker de se obter exclusão mútua.

Antes de usar as variáveis compartilhadas (ou seja, antes de entrar na sua região crítica), cada processo deve chamar enter_region, com seu próprio número, 0 ou 1, como parâmetro. Esta chamada vai fazer com que o processo espere, se necessário, até que seja seguro entrar na região crítica. Quando ele terminar a execução da região crítica, deve chamar leave_region, permitindo a entrada do outro processo na região crítica, se for o caso.
Vamos ver como esta solução funciona. Inicialmente, nenhum processo está executando sua região crítica. Em seguida, o processo 0 chama enter_region. Ele indica seu interesse em executar a região crítica, setando seu elemento do vetor interested, e fazendo turn igual a 0. Uma vez que o processo 1 não está interessado na execução de sua região crítica, ele sai imediatamente do procedimento enter_region. Se o processo 1 chamar enter_region, ele vai ficar preso nesta rotina até que interested [0] seja FALSO, o que só ocorrerá quando o processo 0 chamar leave_region.

Agora considere o caso de ambos os processos chamarem enter_region quase simultaneamente. Ambos vão armazenar seus números em turn. O armazenamento que for feito por último será o que vai valer, sendo o primeiro perdido. Suponha que o processo 1 armazene por último, de maneira que turn será 1. Quando ambos os processos executarem o comando while, o processo 0 vai executá-lo zero vezes, e entrar em sua região crítica. O processo 1 fica em loop no while, não chegando a executar sua região crítica.
Vamos examinar uma proposta que precisa de uma pequena ajuda do hardware. Muitos computadores, especialmente aqueles projetados com o propósito de suportar múltiplos processadores, possuem uma instrução básica, denominada TEST AND SET LOCKED (TSL) que funciona como descrito a seguir.

Ela transfere o conteúdo de um endereço de memória para um registrador, e depois armazena um valor não nulo em tal endereço. As operações de transferência e de armazenamento são indivisíveis – nenhum outro processador ou processo pode acessar a palavra antes que a execução da instrução tenha chegado ao fim. O processador que estiver executando a instrução TSL, bloqueia o barramento de memória, de forma a não permitir que nenhum outro processador tenha acesso à memória até que termine a execução da instrução.
Para executar a instrução TSL, é necessário o uso de uma variável compartilhada, flag, para coordenar o acesso à memória compartilhada. Quando flag for igual a 0, qualquer processo pode fazê-la igual a 1, através da execução da instrução TSL, e então ler ou escrever na memória compartilhada. Ao terminar o acesso à memória, o próprio processo faz flag de volta a 0, usando uma instrução básica de MOVE.

Enfim, encontramos uma solução simples e correta para o problema do acesso a regiões críticas. Antes de entrar em sua região crítica, o processo chama enter_region, a qual coloca o processo em espera até que seu ingresso nela seja permitido. Quando isto ocorre, a sub-rotina termina sua execução, permitindo que o processo que a chamou entre em sua região crítica. Ao terminar a execução desta, o processo chama leave_region, que armazena o valor 0 em flag. A exemplo de todas as soluções para o problema da região crítica, os processos devem chamar enter_region e leave_region nos momentos apropriados. Se um dos processos trapacear nas chamadas, deixando, por exemplo, de executar leave_region, a exclusão mútua de execução das regiões estará comprometida.

Tanto a solução de Peterson quanto a baseada na instrução TSL são corretas, mas ambas têm o defeito de usar a espera ocupada em suas implementações. Em essência, o que estas soluções fazem é o seguinte: quando um processo deseja entrar em sua região crítica, ele verifica uma condição para saber se sua entrada é ou não possível. Se não houver possibilidade de executar um loop, até que lhe seja permitido entrar na região crítica.
Tal solução, além de gastar tempo de processamento, pode ter efeitos colaterais indesejáveis. Considere um computador que esteja executando dois processos, um H com alta prioridade, e outro L, com baixa prioridade. As regras de escalonamento são definidas de maneira que H rode sempre que estiver no estado de pronto. Em determinado instante, com L executando sua região crítica, vai para o estado de pronto quando, por exemplo, uma operação de entrada/saída solicitada por ele terminar. O processo H inicia então a execução de um loop de espera ocupado, mas uma vez que L nunca é escolhido para rodar enquanto H estiver rodando, ele nunca vai ter chance de sair de sua região crítica, de forma que H vai permanecer eternamente no loop de espera ocupada. Esta situação é conhecida na literatura como problema da prioridade invertida.

Um dos pares de primitivas mais simples para resolver este problema é o denominado SLEEP e WAKEUP. A primitiva SLEEP é uma chamada de sistema que bloqueia o processo que a chamou, isso é, suspende a execução de tal processo, até que outro processo o acorde. A primitiva WAKEUP tem um parâmetro, o processo a ser acordado. Alternativamente, tanto SLEEP quanto WAKEUP podem Ter um outro parâmetro, um endereço de memória usado para casar uma primitiva SLEEP com sua correspondente WAKEUP.
O chamado problema do produtor-consumidor, também conhecido como problema do buffer limitado (bounded buffer), é um bom exemplo do uso das primitivas acima descritas. Neste problema, dois processos compartilham um buffer de tamanho fixo. Um dos processos, o produtor, coloca informação no buffer, e o outro, o consumidor, retira informação do buffer.

Os problemas acontecem quando o produtor deseja colocar informação no buffer, mas este está cheio. A solução para isto é colocar o processo produtor para dormir, acordando-o quando o processo consumidor tiver retirado m ou mais itens do buffer. Da mesma forma, o processo consumidor pode desejar remover um item do buffer, encontrando-o vazio. Neste caso, o consumidor é posto para dormir, sendo acordado quando o produtor colocar algo no buffer.
Para controlar o número de itens no buffer, devemos usar uma variável, denominada count. Se o número máximo de itens que o buffer pode armazenar é N, o código do processo produtor ceve, em primeiro lugar, verificar se count é igual a N. Se for, o produtor deve ser posto para dormir, se não, ele deve depositar um item no buffer e incrementar count.

Semáforos

Esta era a situação em 1965, quando E. W. Dijkstra sugeriu o uso de uma variável inteira para contar o número de sinais armazenados para o uso futuro. De acordo com esta proposta, um novo tipo de variável foi criado, o tipo semáforo. Um semáforo pode ter valor o, indicando que não há nenhum sinal armazenado, ou pode ter um valor positivo, indicando, o número de sinais armazenados.
Dijkstra estruturou sua ferramenta com duas operações, DOWN e UP (generalizações de SLEEP e WAKEUP, respectivamente).

A operação DOWN executa sobre um semáforo verifica se o valor do semáforo é maior que 0. Se for, seu valor é decrementado (ou seja, um sinal armazenado é gasto) e o processo simplesmente continua sua progressão. Se o valor do semáforo for 0, o processo que executou a operação DOWN é posto para dormir, são ações únicas, indivisíveis, denominadas ações atômicas. A implementação da ferramenta deve garantir que, uma vez que um processo inicie uma operação sobre um semáforo, nenhum outro processo terá acesso ao semáforo até que a operação se conclua.

A atomicidade é absolutamente essencial para resolver os problemas de sincronização entre processos, evitando as condições de corrida.
A operação UP incrementa o valor do semáforo. Se um ou mais processos estiverem dormindo neste semáforo, impedidos de completar uma operação DOWN, um deles vai ser escolhido pelo sistema (randomicamente, por exemplo), sendo-lhe então permitido completar a operação DOWN. Então, após um UP sobre um semáforo (binário) com processos dormindo, o semáforo permanecerá em 0, porém haverá menos um processo dormindo associado a tal semáforo. A operação de incrementar o semáforo e acordar um processo é também indivisível. Nenhum processo pode ser bloqueado ao executar um UP, assim como nenhum processo era posto para dormir ao executar um WAKEUP definido anteriormente.

Clique aqui para ver a Figura!

Vale observar que Dijkstra usou em seu artigo que introduziu o conceito de semáforo os nomes P e V, termos estes introduzidos na linguagem Algol 68.

Contadores de Evento

Os semáforos baseiam-se na exclusão mútua para evitar a ocorrência de condições de corrida. Deve ser observado, porém, que é possível programar uma solução que não necessite da exclusão mútua. Nesta seção vamos descrever esta solução, que é baseada numa variável especial, denominada contadora de evento (Reed e Kanodia, 1979).
São possíveis somente três operações sobre um contador de evento:

1.Read (Ed): Retorna o valor corrente de E.
2.Advance (E): Incrementa E de 1 unidade atomicamente.
3.Await (E,v): Espera até que E tenha um valor maior ou igual a v.

Nesta solução, dois contadores de evento são usados. O primeiro deles, in, conta cumulativamente o número de itens que o produtor colocou no buffer desde que o programa iniciou sua execução. O outro, out, conta cumulativamente o número de itens que o consumidor removeu do buffer desde o início da execução. Fica claro que o valor de in deve ser maior ou no máximo igual ao de out, e nunca maior que o tamanho do buffer.
Quando o produtor computar um novo item, ele deve verificar para ver se há lugar no buffer, usando a chamada de sistema AWAIT. Inicialmente, o valor de out será 0, e o de sequence-N será negativo, de forma que o produtor não será bloqueado. Se o produtor gerar N+1 itens antes que o consumidor possa consumir alguma, a execução do AWAIT o fará esperar até que out seja igual a 1, condição esta que só se efetivará quando o consumidor remover um item do buffer.
A lógica do consumidor é ainda mais simples. Antes de tentar remover o K-ésimo item, ele simplesmente espera até que in seja igual a k, ou seja, que o produtor tenha posto k itens no buffer.

Monitores

Com o uso de semáforos e de contadores de evento, a comunicação entre processos parece extremamente simples. No entanto, vamos olhar mais de perto a ordem de execução das primitivas DOWN antes de se ter acesso ao buffer, e mostrar que a questão não é tão simples quanto parece. Suponha que os dois DOWNs no código do consumidor tenham tido sua ordem trocada, de forma que mutex foi decrementado antes de empty e não depois. Se o buffer estiver completo, o produtor será bloqueado com mutex igual a 0. Consequentemente, a próxima vez que o consumidor tentar acesso aos buffer, ele deverá executar um DOWN sobre mutex, cujo valor é 0, ficando, portanto, bloqueado. Então ambos os processos ficarão bloqueados indefinidamente. Tal situação é denominada deadlock.
O problema acima foi mostrado para explicar o cuidado que deve ser tomado quando estivermos com semáforos. Um pequeno erro e tudo pode vir abaixo de repente. É um pouquinho pior do que programar em linguagem de montagem, pois os erros levam a condições de corrida, a deadlocks, e a outras situações imprevisíveis e de reprodução virtualmente impossíveis.

Para facilitar a escrita de programas paralelos, Hoare (1974) e Brinch Hansen (1975) propuseram uma primitiva de alto nível para sincronização de processos, denominada monitor. As propostas de Hoare e de Brinch são muito semelhantes, diferindo apenas em pequenos detalhes, conforme descrito a seguir. Um monitor é um conjunto de procedimentos, variáveis e estruturas de dados, todas agrupadas juntas em um módulo especial. Um monitor é um conjunto de procedimentos do monitor sempre que desejarem, mas nunca poderão acessar diretamente as estruturas de dados e as variáveis internas do monitor a partir de procedimentos declarados fora do monitor.
O monitores têm uma propriedade muito importante que os torna úteis na implementação da exclusão mútua: somente um processo pode estar ativo dentro do monitor em um dados instante de tempo.

Os monitores são uma construção de linguagem de alto nível, portanto o compilador sabe de sua natureza especial, e manipula as chamadas aos procedimentos do monitor de forma diferente que as chamadas aos procedimentos comuns. Tipicamente, quando um processo chama um procedimento de um monitor, as primeiras instruções do procedimento verificam se algum outro processo está ativo dentro dele. Se isto for verdade, o processo que chamou o procedimento do monitor será suspenso até que o outro processo deixe o monitor. Se não houver nenhum processo ativo dentro do monitor, o processo que chamou o procedimento do monitor poderá entrar e executar o procedimento chamado.
É tarefa do compilador implementar a exclusão mútua de execução sobre o monitor, sendo o caminho mais usual utilizar os semáforos binários. Pelo fato de o compilador, e não do programador, estar envolvido com a exclusão mútua, é muito pouco provável que algo venha a dar errado. Desta forma, o programador do monitor não precisa preocupar-se com a forma do compilador implementar a exclusão mútua. Basta saber que, colocando todas as regiões críticas dentro do monitor, não haverá a possibilidade de mais de um processo executar sua região ao mesmo tempo.

Apesar de os monitores fornecerem uma forma muito simples de se obter a exclusão mútua, conforme vimos anteriormente, isto não é suficiente. Devemos procurar por formas de bloqueio de processos quando não houver condições lógicas para que eles continuem processando. No problema do produtor-consumidor, é muito fácil colocar todos os testes de buffer cheio e de buffer vazio no código dos procedimentos do monitor, mas como vamos fazer para bloquear o produtor quando o buffer estiver cheio?
A solução encontrada foi a introdução de variáveis de condição, com duas operações possíveis sobre elas, WAIT e SIGNAL. Quando um procedimento do monitor descobre que sua execução não pode prosseguir (o produtor encontra o buffer cheio), ele executa um WAIT em alguma variável de condição, por exemplo a variável full.

Esta ação faz com que o processo que executou WAIT seja bloqueado na fila associada à variável de condição, permitindo também que um outro processo que tenha sido anteriormente impedido de entrar no monitor o faça agora.
Este outro processo, por exemplo o consumidor, pode acordar um produtor que esteja dormindo, através da execução de um SIGNAL, sobre a variável de condição na qual o produtor está bloqueado. Para evitar que haja dois processos ativos no monitor ao mesmo tempo, há necessidade de se estabelecer uma regra que defina o que vai ocorrer após um SIGNAL. Hoare propôs que se deixasse que o processo acordado ganhasse o direito de executar, suspendendo o processo que o acordou.

Brinch propôs que o processo que executasse um SIGNAL fosse obrigado a deixar o monitor em seguida à execução da primitiva. Em outras palavras, a execução do SIGNAL só poderia aparecer como a última declaração do procedimento do monitor. Utilizaremos a proposta de Brinch, por ser conceitualmente mais simples e mais fácil de implementar. Se um SIGNAL for executado sobre uma variável de condição na qual vários processos estiverem esperando, somente um deles, determinado pelo escalonador do sistema, é reativado.
Conceitualmente, as variáveis de condição não se assemelham aos contadores de evento. Elas acumulam sinais para uso posterior, à imagem dos semáforos. Então, se um SIGNAL for executado sobre uma variável de condição sem nenhum processo bloqueado sobre ela, o SIGNAL, é perdido. O wait precisa vir antes do SIGNAL. Tal regra torna a implementação bastante simples. Na prática isto não chega a constituir um problema, uma vez que é fácil controlar o estado de cada processo, se for necessário. Um processo que precise emitir um SIGNAL pode verificar se isto é necessário, observando as variáveis de condição do sistema.

Você pode estar pensando que as operações de WAIT e SIGNAL são semelhantes às de SLEEP e WAKEUP, que vimos anteriormente serem sujeitas à ocorrência de condições de corrida. Na verdade, elas são semelhantes, porém com uma diferença fundamental: SLEEP e WAKEUP falham porque, enquanto um processo está tentando dormir, um outro pode estar tentando acordá-lo. Com o monitor, isto não pode ocorrer. A exclusão mútua automática dos procedimentos do monitor garante que se, digamos, o produtor executando um procedimento descobre que o buffer está cheio, ele poderá completar a execução do WAIT, sem correr o risco do escalonador comutar a execução para o consumidor antes que a execução do WAIT venha a completar-se. O consumidor jamais conseguirá entrar no monitor antes do término do WAIT e do bloqueio do produtor.
Fazendo com que a exclusão mútua sobre as suas regiões críticas seja automática, os monitores tornam a programação paralela muito menos suscetível a erros do que com o uso de semáforos.

O problema com monitores e com os semáforos é que ele foram projetados para prover exclusão mútua em um ou mais processadores que tenham acesso a uma memória comum. Colocando os semáforos ou os contadores de evento em uma memória comum, e protegendo-os com a instrução TSL, não haverá a ocorrência de condições de corrida. Quando passamos a tratar com sistemas distribuídos, compostos por diversos processadores, cada um acessando sua própria memória, e conectados através de uma rede de comunicação, tais primitivas tornam-se não-adequadas. A conclusão é que os semáforos são ferramentas de muito baixo nível e que os monitores precisam de uma linguagem específica para serem utilizados.

Troca de Mensagens

A Troca de Mensagens, é um método para comunicação entre processos que usa duas primitivas: SEND e RECEIVE, as quais, tal como os semáforos e diferente dos monitores, são chamadas de sistema, e não construção de linguagem. Como tal, podem ser facilmente acrescentadas à biblioteca de procedimentos.
A primeira primitiva envia uma mensagem para um dado destino e a outra recebe uma mensagem de determinada fonte (ou de qualquer fonte). Se não houver nenhuma mensagem a ser recebida, o receptor pode ser bloqueado até que uma mensagem chegue.
Os sistemas baseados em troca de mensagens têm muitos problemas que não ocorrem nos sistemas com semáforos ou com monitores, especialmente se os processos que se comunicam estiverem em máquinas diferentes, conectadas por uma rede.

Por exemplo, as mensagens podem perder-se na rede. Para prevenir a perda de mensagens, o transmissor e o receptor dever ser programados de forma que, tão logo tenha recebido uma mensagem, o receptor envie de volta ao transmissor uma mensagem especial de reconhecimento (acknowledgement). Se o transmissor não receber esta mensagem num certo intervalo de tempo, ele deve retransmitir a mensagem.
Consideremos agora o que ocorre se a mensagem for recebida corretamente, mas o reconhecimento for perdido. Neste caso, o transmissor transmite de novo a mensagem, e o receptor a recebe duas vezes. É fundamental que o receptor possa distinguir uma nova mensagem de uma velha que tenha sido transmitida novamente.

Normalmente este problema é resolvido pela colocação de números seqüenciais em cada mensagem original. Se o receptor receber uma mensagem com o mesmo número da anterior, ele sabe que tal mensagem é duplicada e que pode ser ignorada.
Outro problema dos sistemas com troca de mensagens é a questão envolvendo autenticação das mensagens: como um processo sabe que está se comunicando com um servidor de arquivos real e não com um impostor? Como um servidor de arquivos sabe qual o processo que requisitou acesso a um arquivo? A criptografia das mensagens, com uma chave conhecida somente por usuário autorizado, pode ser muito útil neste caso.
No outro extremo do espectro deve haver questões que são importantes quando o transmissor e o receptor estão rodando na mesma máquina. Uma de tais questões diz respeito à performance.

Copiar mensagens de um processo para outro demora muito mais do que fazer uma operação sobre um semáforo, ou uma chamada a um monitor. Muito trabalho de pesquisa te sido despendido para tornar eficiente o esquema de troca de mensagens. Cheriton (1984) sugeriu, por exemplo, limitar o tamanho das mensagens de forma que elas possam ser armazenadas nos registradores da máquina, realizando a troca de mensagens usando os registradores.
Vimos anteriormente quatro primitivas diferentes para comunicação entre processos. Ao longo dos anos, cada uma delas vem acumulando seguidores, que afirmam ser esta a melhor solução de todas para o problema. A verdade, porém, é que todos estes métodos são semanticamente equivalentes, pelo menos quando usamos um único processador. Com a utilização de qualquer um de tais métodos você pode construir todos os demais.