Algoritmo para eleição em anel usado em Sistemas Distribuídos.

Bem, para falar sobre esse assunto eu deveria criar uma nova categoria e chama-la de sistemas distribuídos, mas como o assunto é um algoritmo em C achei melhor coloca-lo aqui e então fazer uma breve explicação do que é esse algoritmo para eleição em anel.

Essa é uma das soluções para eleição de líder em sistemas distribuídos e exige que os processos estejam organizados em um anel lógico, onde cada processo sabe quem é seu sucessor. As mensagens são enviadas no sentido horário através de um canal de comunicação que liga cada processo ao seu vizinho. O algoritmo parte do princípio que os processos não estão sujeitos a falhas durante a execução do algoritmo de eleição. Mas as falhas podem ocorrer e devem ser tratadas.

Quando um processo identificar a ausência de um líder (falha), ele inicia o processo de eleição primeiramente marcando-se como participante e em seguida enviando uma mensagem de eleição contendo seu identificador para seu vizinho no anel.

Ao receber uma mensagem de eleição, um processo deve comparar o identificador contido na mensagem com o seu próprio. Se o identificador recebido for maior, o processo deve passar adiante a mensagem para seu vizinho. Se por outro lado, o identificador contido na mensagem for menor que o identificador do processo em questão e o mesmo ainda não for um participante, então este deverá substituir o conteúdo da mensagem pelo seu próprio identificador antes de enviá-la para seu
vizinho.

Imagem simulando como funciona a eleição em anel.

Esse algoritmo foi escrito e testado usando Linux(Ubuntu), ele faz uso de algumas referencias de cores que poderão não funcionar em ambientes Windows, portanto se caso utiliza-lo, você deverá modificar conforme as suas necessidades.

/*********************************
Autor: Fernando Krein Pinheiro
Data: 06/04/2011
Linguagem: C
========= IMPORTANTE ===========
O código esta livre para usar,
citar e compartilhar desde que
mantida sua fonte e seu autor.
Obrigado.
*********************************
 Esse algoritmo é apenas uma
 simulação do que um algoritmo
 de eleição em anel faz nos
 sistemas distribuidos.
********************************/
#include <stdlib.h>
#include <stdio.h>
#define TAM 5 /*aqui pode-se definir o numero de processos que se quer, precisa ser (>=2) */

struct Processos{
    int pid;
};
typedef struct Processos Processos;

int falha()
{
      int falha;
      srand(time(NULL));
      falha = rand() % TAM;
  return falha;
}

int promove_eleicao()
{
      int eleicao;
      eleicao = rand() % TAM;
 return eleicao;
}

int main()
{
    Processos proc[TAM];
    int proc_falha = 0;

    int proc_eleicao = 0;
    int proc_lider = 0;
    int vet_proc[TAM],i,cont;

 if(TAM<2)
 {
      system("clear");
      printf("\033[31mERRO 666 :\033[37mVoce precisa ter pelo menos 2 processos.\n");
      sleep(3);
      exit(0);
 }
 system("clear");

      for(; cont<TAM+TAM; cont++)
      {
            //inicializa os processo preenchendo a struct com numero do processo (PID)
             for(i=0; i<TAM; i++)
             {
                  vet_proc[i] = proc[TAM].pid = i;
             }
             do
             {
                   proc_falha = falha();
                   proc_eleicao = promove_eleicao();
             }while(proc_eleicao == proc_falha);

             //inicializa o processo com falha colocando -1
             for(i=0; i<TAM; i++)
             {
                 if(vet_proc[i] == proc_falha)
                 vet_proc[i] = -1;
             }

 proc_lider = vet_proc[0];
 for(i=0; i<TAM; i++)//faz a escolha do novo lider
 {
           if(vet_proc[i] > proc_lider)
           proc_lider = vet_proc[i];
 }
 printf("|\033[32m PROC PID\033[37m |\n");//faz a impressão na tela
 for(i=0; i<TAM; i++)
 {
         printf("| [%d] [%d] |\n",vet_proc[i],proc[TAM].pid=i);
 }
 sleep(1);
 printf("\n\nProcesso de PID\033[31m [%d]\033[37m falhou.\n",proc_falha);
 sleep(2);
 printf("Processo de PID\033[33m [%d]\033[37m iniciou eleicao.\n",proc_eleicao);
 sleep(2);
 printf("\033[36mEscolhendo novo lider...\033[37m \n");
 sleep(3);
 printf("Processo de PID\033[33m [%d]\033[37m e o novo lider.\n",proc_lider);
 sleep(3);
 system("clear");
}
return 0;
}

Lembro novamente que esse algoritmo apenas simula uma eleição em anel, e pode ser incrementado utilizando algumas funcionalidades a mais que não foram implementadas nessa versão.

Anúncios
por ferpinheiro Postado em C/C++

12 comentários em “Algoritmo para eleição em anel usado em Sistemas Distribuídos.

  1. Boa noite.
    Não sei se é porque estou usando Windos, mas peguei o exemplo e compilei no DevC++ e deu erro na linha 028 [srand(time(NULL))]. E também deu erro em um dos sleep.

    • Sim, é devido ao fato de voce usar Windows!

      No linux quando voce quer uma pause de um segundo voce diz: sleep(1) “Um segundo”.
      Já no Windows voce precisa dizer: sleep(1000) “Que equivale a um segundo”.

      Já na questão do srand não estou bem lembrado, pois faz tempo que nao faço nada com windows, mas procure sobre estrutura de um srand() ou rand() no windows…

      Verifique a questão dos print(). estou usando uma constante para modificar a cor de saida no terminal que funciona somento no Linux tambem!

      • Já coloquei o time.h.
        A saída:
        ‘sleep’ undeclared (firsr use this function)
        (Each undeclared identifier is reported only once for each function it appears in.)

      • Bem isso realmente está estranho…. Mas o mais estranho é que eu tentei rodar esse mesmo código em uma maquina que tem windows e funcionou perfeitamente!
        Então em uma rápida pesquisa no Google encontrei pessoas que falavam sobre a extensão do arquivo fonte que deveria ser arquivo.c e não arquivo.cpp

        Ja em outros casos vi pessoas usando a biblioteca windows.h e usando o comando sleep assim: Sleep(1000); —> Com o S maiusculo. Não tentei essa soluação, mas verifique ai e me informe caso tenha conseguindo resolver o problema!

  2. Sou eu de novo!
    Será que é possível postar algum exemplo da topologia Token Ring? Tenho que implementá-la até quinta-feira!

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s