A Simulação de Ordenamento de Mensagens

Ferramenta para simulação de ordenamento de mensagens

Resumo. O presente artigo apresenta a descrição de uma ferramenta para a simulação da entrega de mensagens. Sendo que a ordenação pode ser sem ordem, ordenação FIFO, Causal e Total.

1. Introdução

Provavelmente você já recebeu um e-mail em resposta a um e-mail anterior sendo que você ainda não recebeu o e-mail com a pergunta. Isto acontece pois o tempo de entrega de mensagens é diferente de uma rede para outra. Quando estamos falando em sistemas distribuídos este problema é comum, uma vez que os processos conversam entre eles, e a velocidade da comunicação entre eles pode variar.

Existe porém uma diferença, quando você recebe uma resposta antes da pergunta o único inconveniente é que você pode não saber qual a pergunta, já em sistemas distribuídos este é um problema crítico pois estas mensagens podem determinar a ordem de execução de um processo e a quebra da ordem acarreta numa execução incorreta.

Para resolver o problema da ordenação da entrega das mensagens de um sistema distribuído são sugeridos três tipos de ordenação: FIFO (First In, First Out), Causal e Total (TANENBAUM, STEEN, 2002, p. 300-308).

O presente artigo tem por objetivo apresentar os tipos de ordenação e demonstrar a implementação da ferramenta que faz a simulação do envio e entrega das mensagens, ordenadas de acordo com a seleção do usuário. O artigo está organizado da seguinte forma a segunda seção apresenta a troca de mensagens entre os processos e os tipos de ordenação de mensagens. A seção seguinte apresenta a ferramenta que foi desenvolvida. Para finalizar, na última seção são apresentadas as conclusões do trabalho.

1. Troca de Mensagens

Em sistemas distribuídos é fundamental a comunicação entre os diversos computadores que compõem este ambiente de sistemas distribuídos. Dentro desta comunicação existem propriedades essenciais para o bom funcionamento da comunicação, entre eles podem ser destacados: a atomicidade, que trata da garantia de que uma mensagem será entregue para todos ou para ninguém; e o ordenamento das mensagens, que é a garantia de que a ordem de envio será a mesma da entrega.

Neste conceito de comunicação não basta garantir que a mensagem será entregue, deve-se preocupar também com o processo de entrega da mensagem. “Assim uma mensagem recebida para um destino final passa por um processo de entrega que eventualmente precisa ser controlado para que a seqüência de entrega seja a mesma seqüência de envio.” (GOULART, 2002, p.62).

Este processo de entrega é tratado por algoritmos de ordenação, que serão apresentados na seção seguinte. Os tipos de ordenações apresentados, são os que foram implementados na ferramenta.

1. Tipos de Ordenação

A ferramenta implementa quatro tipos de ordenações, que são os mais comuns. São eles:

 ·  Sem Ordem: As mensagens são enviadas sem qualquer ordem. É o mais fácil e não possui overhead, porém deve ser utilizada com cuidado, não é indicada para alguns casos;

·  Ordenamento FIFO: Garante que todas as mensagens de um membro sejam entregues aos demais membros do grupo na ordem em que elas foram enviadas. Funciona como uma pilha, o primeiro que chega é o primeiro que sai. Isto é, se um processo envia a M2 antes de M1 todos os processos devem receber M1 antes de M2;

·  Ordenamento CAUSAL: No ordenamento causal introduz-se o conceito de mensagem dependente de outra. No ordenamento causal as mensagens estão em ordenamento FIFO e se um membro após receber a mensagem A envia uma mensagem B, é garantido a todos os membros do grupo que vão receber A antes de B;

·  Ordenamento Total: No ordenamento total cada membro do grupo recebe todas as mensagens na mesma ordem. Este é o melhor ordenamento porém sua implementação é difícil.

1. Ferramenta

A ferramenta foi desenvolvida na linguagem Java, utilizando a biblioteca swing para a interface. Foi escolhida a linguagem Java devido a sua independência de sistema operacional.

A figura 1 apresentada à tela da ferramenta.

[pic 1]

Figura 1: Tela Principal

Está tela apresenta dois painéis, no primeiro denominado “Gerar Clientes”, o usuário irá definir quantos clientes serão criados, com um mínimo de 2 e máximo de 7. No segundo painel, denominado “Simulação”, o usuário tem a opção de selecionar o método de ordenação e de reiniciar a ordenação. Cada uma destas funções será explica a seguir.

1. Clientes

De acordo com o número de clientes, é criado um frame para cada um. Cada frame de cliente possui a área de mensagens locais e mensagens recebidas. Na área de mensagens locais, o usuário pode escrever as mensagens que deseja enviar, no máximo cinco. Quando é iniciado o cliente, já existem 5 mensagens, caso deseje enviar menos, basta limpar o campo da mensagem que automaticamente ela não é enviada.

Na área de mensagens recebidas serão apresentadas as mensagens que ele recebeu. A mensagem é composta pela origem, a mensagem e o tempo dela em que ela saiu do servidor.

A figura 2 apresenta a tela com quatro clientes criados.

[pic 2]

Figura 2: Clientes criados

1. Coleta de Mensagens

Após a criação dos clientes e a edição das mensagens, o usuário pode solicitar o envio das mensagens. Para isto basta selecionar qual o tipo de ordenação que será aplicada na entrega das mensagens e apertar o botão Início. Existe ainda a opção de Reset, caso ela esteja seleciona, quando foi feita a ordenação as mensagens serão embaralhadas novamente antes de serem ordenadas.

O envio das mensagens foi implementado da seguinte forma:

1. O servidor verifica quantos clientes são;
2. Em seguida faz um random para verificar de qual cliente irá pegar uma mensagem, e pega uma mensagem do cliente sorteado. Depois de pegar a mensagem ele faz um random para ver de qual cliente vai pegar a próxima mensagem e pega uma mensagem do cliente sorteado, isto é feito até que o servidor receba todas as mensagens de todos os clientes. Com isso, as mensagens estão embaralhadas. Quando chega no servidor cada mensagem recebe o seu tempo, que é a ordem de chega delas;
3. Em seguida ele faz uma cópia das mensagens, para que caso o usuário deseje ordenar as mensagens por mais de uma ordenação e queira comparar o resultado, exista uma cópia da ordem original;
4. Agora as mensagens são novamente embaralhadas através de um random. Em seguida ele faz a ordenação de acordo com o tipo escolhido e entrega para cada cliente as mensagens.

1. Sem Ordem

O servidor entrega as mensagens sem qualquer ordem. A figura 3 apresenta a entrega das mensagens sem ordem.

[pic 3]

Figura 3: Mensagens sem ordem

1. FIFO

No quadro 1 encontra-se o código fonte da implementação da ordenação FIFO na ferramenta.

public ArrayList ordenaArrayFifo(ArrayList msgs){

        ArrayList aux = new ArrayList(msgs);

        ArrayList ordenado = new ArrayList();

        ArrayList buffer = new ArrayList();

        int t[] = {0,0,0,0,0,0,0};