Trabalho de Sistemas Distribuídos

Autor:

• Eduardo H. Trevisan | GRR20171588

Tabela de Conteúdos

• Arquivos
• Tarefas
• Tarefa 0
• Tarefa 1
• Tarefa 2
• Tarefa 3
• Tarefa 4
• Implementação
• Testes

Introdução

Implementação do algoritmo distribuído VCube no ambiente de simulação SMPL.

Arquivos

• vcube.c
• cisj.c
• cisj.h
• makefile

Tarefas

O programa desenvolvido a partir destas tarefas serviu como base para a implementação final do algoritmo. Diversas decisões sobre como abordar o problema foram feitas nestes estágios.

Cada tarefa contém um link para o arquivo .c e um log de exemplo de execução. O log contém a execução do exemplo de sequência de eventos realizado na aula de laboratório. Ou seja, o nodo 1 falha no tempo 31.0 e recupera no tempo 61.0 e o intervalo de testes é de 30 unidades de tempo.

Tarefa 0:

Digitar, compilar e executar o programa exemplo, tempo.c

Após corrigir o nome do executável no makefile e alguns erros de digitação no tempo.c o programa foi compilado com sucesso.

O nodo 0 vai testar no tempo 30.0
O nodo 1 vai testar no tempo 30.0
O nodo 1 falhou no tempo 31.0
O nodo 0 vai testar no tempo 60.0
O nodo 1 recuperou no tempo 61.0
O nodo 0 vai testar no tempo 90.0
O nodo 1 vai testar no tempo 91.0
O nodo 0 vai testar no tempo 120.0
    

Tarefa 1:

Fazer cada um dos processos testar o seguinte no anel. Implemente o teste com a função status() do SMPL e imprimir (printf) o resultado de cada teste executado. Por exemplo: “O processo i testou o processo j correto no tempo tal.”

A expressão (token+1)%N sempre retorna o próximo membro do anel.

i = (token+1)%N; /* i recebe o próximo nodo do que está sendo executado */
if (status(nodo[i].id)!=0) { /* testando o próximo nodo */
    printf("O nodo %d testou o nodo %d falho no tempo %3.1f\n",token,i,time());
} else {
    printf("O nodo %d testou o nodo %d correto no tempo %3.1f\n",token,i,time());
}
    

O nodo 0 testou o nodo 1 correto no tempo 30.0
O nodo 1 testou o nodo 0 correto no tempo 30.0
O nodo 1 falhou no tempo 31.0
O nodo 0 testou o nodo 1 falho no tempo 60.0
O nodo 1 recuperou no tempo 61.0
O nodo 0 testou o nodo 1 correto no tempo 90.0
O nodo 1 testou o nodo 0 correto no tempo 91.0
O nodo 0 testou o nodo 1 correto no tempo 120.0
    

Tarefa 2:

Cada processo correto executa testes até achar outro processo correto. Lembre-se de tratar o caso em que todos os demais processos estão falhos. Imprimir os testes e resultados.

A condição é colocada dentro de um loop até achar um nodo correto.

i = (token+1)%N; /* i recebe o próximo nodo do que está sendo executado */
while (i != token) { 
    if (status(nodo[i].id)!=0) { /* testando o próximo nodo */
        printf("O nodo %d testou o nodo %d falho no tempo %3.1f\n",token,i,time());
        i = (i+1)%N; /* testou um nodo falho; i recebe próx nodo */
    } else {
        printf("O nodo %d testou o nodo %d correto no tempo %3.1f\n",token,i,time());
        i = token; /* testou um nodo correto; saindo do loop */
    }   
}
    

O nodo 0 testou o nodo 1 correto no tempo 30.0
O nodo 1 testou o nodo 2 correto no tempo 30.0
O nodo 2 testou o nodo 0 correto no tempo 30.0
O nodo 1 falhou no tempo 31.0
O nodo 0 testou o nodo 1 falho no tempo 60.0
O nodo 0 testou o nodo 2 correto no tempo 60.0
O nodo 2 testou o nodo 0 correto no tempo 60.0
O nodo 1 recuperou no tempo 61.0
O nodo 0 testou o nodo 1 correto no tempo 90.0
O nodo 2 testou o nodo 0 correto no tempo 90.0
O nodo 1 testou o nodo 2 correto no tempo 91.0
O nodo 0 testou o nodo 1 correto no tempo 120.0
    

Tarefa 3:

Cada processo mantém localmente o vetor State[N]. Inicializa o State[N] com -1 (indicando estado “unknown”) para todos os demais processos e 0 para o próprio processo. Nesta tarefa ao executar um teste, o processo atualiza a entrada correspondente no vetor State[N]. Em cada intervalo de testes, mostre o vetor State[N].

O valor -2 foi utilizado para representar o estado falho porque foi encontrado a necessidade de diferenciar os estados unknown e falho.

/* iterando sobre os nodos até achar um nodo correto */
for (i = (token+1)%N; i != token; i = (i+1)%N)
{
  if (status(nodo[i].id)!=0) /* nodo testado é falho */
  {
    printf("  nodo %d falho\n",i,time());
    nodo[token].state[i] = -2; /* atualizando nodo i no vetor de estados para falho */
  }
  else /* nodo testado não é falho */
  {
    printf("  nodo %d correto\n",i,time());
    nodo[token].state[i] = 1; /* atualizando nodo i no vetor de estados para correto */
    break;
  }
}
    

nodo 0 testando no tempo 30.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: unknown | 
nodo 1 testando no tempo 30.0:
  nodo 2 correto
  State[1]: | 0: unknown | 2: correto | 
nodo 2 testando no tempo 30.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: unknown | 
nodo 1 falhou no tempo 31.0
nodo 0 testando no tempo 60.0:
  nodo 1 falho
  nodo 2 correto
  State[0]: | 1: falho   | 2: correto | 
nodo 2 testando no tempo 60.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: unknown | 
nodo 1 recuperou no tempo 61.0
nodo 0 testando no tempo 90.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: correto | 
nodo 2 testando no tempo 90.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: unknown | 
nodo 1 testando no tempo 91.0:
  nodo 2 correto
  State[1]: | 0: unknown | 2: correto | 
nodo 0 testando no tempo 120.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: correto |
    

Tarefa 4:

Quando um processo correto testa outro processo correto obtém as informações de diagnóstico do processo testado sobre todos os processos do sistema exceto aqueles que testou nesta rodada, além do próprio testador.

Iniciamos resetando o vetor de estados do nodo pois são informações antigas.

Quando o nodo é correto atualizamos o vetor de estado do testador e do nodo sendo testado também.

/* reset vetor de status */
for (i=0;i<N;i++)
  nodo[token].state[i] = -1;
nodo[token].state[token] = 0;

printf("nodo %d testando no tempo %3.1f:\n", token, time());
/* iterando sobre os nodos até achar um nodo correto */
for (i = (token+1)%N; i != token; i = (i+1)%N)
{
  if (status(nodo[i].id)!=0) /* nodo testado é falho */
  {
    printf("  nodo %d falho\n",i,time());
    nodo[token].state[i] = -2; /* atualizando nodo i no vetor de estados para falho */
  }
  else /* nodo testado é correto */
  {
    printf("  nodo %d correto\n",i,time());
    nodo[token].state[i] = 1; /* atualizando nodo i no vetor de estados para correto */
    nodo[i].state[token] = 1;

    /* atualizando vetor de estados com informações do nodo i */
    for (j=0;j<N;j++)
      if (nodo[token].state[j] == -1)
        nodo[token].state[j] = nodo[i].state[j];
    /* atualizando nodo i com info do nodo token */
    for (j=0;j<N;j++)
      if (nodo[i].state[j] == -1)
        nodo[i].state[j] = nodo[token].state[j];

    break;
  }
}
    

nodo 0 testando no tempo 30.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: unknown | 
nodo 1 testando no tempo 30.0:
  nodo 2 correto
  State[1]: | 0: unknown | 2: correto | 
nodo 2 testando no tempo 30.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: correto | 
nodo 1 falhou no tempo 31.0
nodo 0 testando no tempo 60.0:
  nodo 1 falho
  nodo 2 correto
  State[0]: | 1: falho   | 2: correto | 
nodo 2 testando no tempo 60.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: falho   | 
nodo 1 recuperou no tempo 61.0
nodo 0 testando no tempo 90.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: unknown | 
nodo 2 testando no tempo 90.0:
  nodo 0 correto
  State[2]: | 0: correto | 1: correto | 
nodo 1 testando no tempo 91.0:
  nodo 2 correto
  State[1]: | 0: correto | 2: correto | 
nodo 0 testando no tempo 120.0:
  nodo 1 correto
  State[0]: | 1: correto | 2: correto |
    

Implementação

Estrutura de dados

Dentro da estrutura de um nodo, além do vetor de estados também há uma variável s para guardar o atual cluster de testes, e um vetor failState.

O vetor failState guarda a informação se um nodo está correto(1), incorreto(0) ou desconhecido(-1).

/*----Descritor do nodo SMPL----*/
 typedef struct {
     int id; /* identificador da facility SMPL */
     int *state; /* vetor de estados dos nodos; conta numero de eventos */
     int *failState; /* vetor que guarda estados falhos */
     int s; /* indice do cluster sendo testado atualmente */
 } tnodo;
    

Função c(i,s)

Para implementar a função c(i,s) apenas transformei o arquivo base cisj.c em uma biblioteca. O resultado dessa função é utilizado para iterar entre os nodos ao fazer os testes:

node_set* testList = cis(token, nodo[token].s);
/* iterando sobre os nodos ate achar um nodo correto */
for (int it = 0; it < testList->size; it++)
{
  i= testList->nodes[it];
  if (i>=N) break; /* se nodo não existe */
    

Temos uma condição para tratar o caso em que N não é potencia de 2, fazendo com que alguns clusters que c(i,s) retorna tenham elementos a mais.

Atualizando o estado

Só podemos incrementar o contador de eventos de um nodo se detectamos uma mudança de estado no failState:

if (status(nodo[i].id)!=0) /* nodo testado eh falho */
{
  printf("  nodo %d falho\n",i,time());
  if (nodo[token].failState[i] != 1) { /* esta falha eh um evento novo? */
    if (nodo[token].state[i] == -1) nodo[token].state[i] = 0;
    nodo[token].state[i] += 1;    /* atualizando contador de eventos para i */
    nodo[token].failState[i] = 1; /* atualizando nodo i para falho */
  }
}
    

Trocando informações de estado com um nodo

Se um nodo é testado correto trocamos informações de estado entre os nodos, sempre pegando a informação mais recente com base nos contadores de eventos.

/* trocando info entre nodos token e i */
for (j=0;j<N;j++)
{
  if (nodo[token].state[j] >= nodo[i].state[j])
  {
    nodo[i].state[j] = nodo[token].state[j];
    nodo[i].failState[j] = nodo[token].failState[j];
    

Testes

Informações para interpretar os logs:

• Informações com identação pertencem ao teste sendo realizado pelo nodo.
• Os números após : nas linhas indicando testes são o resultado da função c(i,s)
• State[i] é o vetor de estados do nodo i
• O número [n] dentro do vetor state indica o valor do contador de eventos
• s representa o índice do cluster sendo testado atualmente

Número ímpar de nodos, sem eventos:

nodo 0 testando no tempo 30.0 [s=1]:  1 
  nodo 1 correto
  State[0]: | 0: correto [0]| 1: correto [1]| 2: unknown [-1]| 

nodo 1 testando no tempo 30.0 [s=1]:  0 
  nodo 0 correto
  State[1]: | 0: correto [0]| 1: correto [0]| 2: unknown [-1]| 

nodo 2 testando no tempo 30.0 [s=1]:  3 
  State[2]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 

nodo 0 testando no tempo 60.0 [s=2]:  2 3 
  nodo 2 correto
  State[0]: | 0: correto [0]| 1: correto [1]| 2: correto [1]| 

nodo 1 testando no tempo 60.0 [s=2]:  3 2 
  State[1]: | 0: correto [0]| 1: correto [0]| 2: unknown [-1]| 

nodo 2 testando no tempo 60.0 [s=2]:  0 1 
  nodo 0 correto
  State[2]: | 0: correto [0]| 1: correto [1]| 2: correto [0]| 

nodo 0 testando no tempo 90.0 [s=1]:  1 
  nodo 1 correto
  State[0]: | 0: correto [0]| 1: correto [1]| 2: correto [1]| 

nodo 1 testando no tempo 90.0 [s=1]:  0 
  nodo 0 correto
  State[1]: | 0: correto [0]| 1: correto [0]| 2: correto [1]| 

nodo 2 testando no tempo 90.0 [s=1]:  3 
  State[2]: | 0: correto [0]| 1: correto [1]| 2: correto [0]| 

nodo 0 testando no tempo 120.0 [s=2]:  2 3 
  nodo 2 correto
  State[0]: | 0: correto [0]| 1: correto [1]| 2: correto [1]|
    

Um nodo falho no início N=4:

nodo 0 testando no tempo 30.0 [s=1]:  1 
  nodo 1 falho
  State[0]: | 0: correto [0]| 1: falho   [1]| 2: unknown [-1]| 3: unknown [-1]| 

nodo 2 testando no tempo 30.0 [s=1]:  3 
  nodo 3 correto
  State[2]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [1]| 

nodo 3 testando no tempo 30.0 [s=1]:  2 
  nodo 2 correto
  State[3]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [0]| 

nodo 0 testando no tempo 60.0 [s=2]:  2 3 
  nodo 2 correto
  State[0]: | 0: correto [0]| 1: falho   [1]| 2: correto [1]| 3: correto [1]| 

nodo 2 testando no tempo 60.0 [s=2]:  0 1 
  nodo 0 correto
  State[2]: | 0: correto [0]| 1: falho   [1]| 2: correto [0]| 3: correto [1]| 

nodo 3 testando no tempo 60.0 [s=2]:  1 0 
  nodo 1 falho
  nodo 0 correto
  State[3]: | 0: correto [1]| 1: falho   [1]| 2: correto [1]| 3: correto [0]| 

    

Subgrupo inteiro falho no início. (nodos 0 e 1) N=4:

nodo 1 falhou no tempo 1.0

nodo 0 falhou no tempo 1.0

nodo 2 testando no tempo 30.0 [s=1]:  3 
  nodo 3 correto
  State[2]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [1]| 

nodo 3 testando no tempo 30.0 [s=1]:  2 
  nodo 2 correto
  State[3]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [0]| 

nodo 2 testando no tempo 60.0 [s=2]:  0 1 
  nodo 0 falho
  nodo 1 falho
  State[2]: | 0: falho   [1]| 1: falho   [1]| 2: correto [0]| 3: correto [1]| 

nodo 3 testando no tempo 60.0 [s=2]:  1 0 
  nodo 1 falho
  nodo 0 falho
  State[3]: | 0: falho   [1]| 1: falho   [1]| 2: correto [0]| 3: correto [0]|
    

Nodo se recuperando de uma falha. N=4

nodo 3 testando no tempo 120.0 [s=2]:  1 0 
  nodo 1 falho
  nodo 0 correto
  State[3]: | 0: correto [0]| 1: falho   [2]| 2: correto [1]| 3: correto [0]| 

nodo 1 recuperou no tempo 121.0

nodo 0 testando no tempo 150.0 [s=1]:  1 
  nodo 1 correto
  State[0]: | 0: correto [0]| 1: correto [3]| 2: correto [1]| 3: correto [1]| 

nodo 2 testando no tempo 150.0 [s=1]:  3 
  nodo 3 correto
  State[2]: | 0: correto [0]| 1: falho   [2]| 2: correto [0]| 3: correto [1]| 

nodo 3 testando no tempo 150.0 [s=1]:  2 
  nodo 2 correto
  State[3]: | 0: correto [0]| 1: falho   [2]| 2: correto [1]| 3: correto [0]| 

nodo 1 testando no tempo 151.0 [s=1]:  0 
  nodo 0 correto
  State[1]: | 0: correto [0]| 1: correto [0]| 2: correto [1]| 3: correto [1]| 

nodo 0 testando no tempo 180.0 [s=2]:  2 3 
  nodo 2 correto
  State[0]: | 0: correto [0]| 1: correto [3]| 2: correto [1]| 3: correto [1]|
    

Dois nodos falham simultaneamente (1 e 5), nodo 1 se recupera. N=6

odo 0 testando no tempo 30.0 [s=1]:  1                                                                                                                              [65/1933]
  nodo 1 correto                                                                                                                                                              
  State[0]: | 0: correto [0]| 1: correto [1]| 2: unknown [-1]| 3: unknown [-1]| 4: unknown [-1]| 5: unknown [-1]|                                                             
                                                                                                                                                                              
nodo 1 testando no tempo 30.0 [s=1]:  0                                                                                                                                       
  nodo 0 correto                                                                                                                                                              
  State[1]: | 0: correto [0]| 1: correto [0]| 2: unknown [-1]| 3: unknown [-1]| 4: unknown [-1]| 5: unknown [-1]|                                                             
                                                                                                                                                                              
nodo 2 testando no tempo 30.0 [s=1]:  3                                                                                                                                       
  nodo 3 correto                                                                                                                                                              
  State[2]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [1]| 4: unknown [-1]| 5: unknown [-1]|                                                             
                                                                                                                                                                              
nodo 3 testando no tempo 30.0 [s=1]:  2                                                                                                                                       
  nodo 2 correto                                                                                                                                                              
  State[3]: | 0: unknown [-1]| 1: unknown [-1]| 2: correto [0]| 3: correto [0]| 4: unknown [-1]| 5: unknown [-1]|                                                             
                                                                                                                                                                              
nodo 4 testando no tempo 30.0 [s=1]:  5                                                                                                                                       
  nodo 5 correto                                                                                                                                                              
  State[4]: | 0: unknown [-1]| 1: unknown [-1]| 2: unknown [-1]| 3: unknown [-1]| 4: correto [0]| 5: correto [1]|                                                             
                                                                                                                                                                              
nodo 5 testando no tempo 30.0 [s=1]:  4                                                                                                                                       
  nodo 4 correto                                                                                                                                                              
  State[5]: | 0: unknown [-1]| 1: unknown [-1]| 2: unknown [-1]| 3: unknown [-1]| 4: correto [0]| 5: correto [0]|                                                             
                                                                                                                                                                              
nodo 1 falhou no tempo 31.0                                                                                                                                                   
                                                                                                                                                                              
nodo 5 falhou no tempo 31.0                                                                                                                                                   
                                                                                                                                                                              
nodo 0 testando no tempo 60.0 [s=2]:  2 3                                                                                                                                     
  nodo 2 correto                                                                                                                                                              
  State[0]: | 0: correto [0]| 1: correto [1]| 2: correto [1]| 3: correto [1]| 4: unknown [-1]| 5: unknown [-1]| 

nodo 2 testando no tempo 60.0 [s=2]:  0 1 
  nodo 0 correto
  State[2]: | 0: correto [0]| 1: correto [1]| 2: correto [0]| 3: correto [1]| 4: unknown [-1]| 5: unknown [-1]| 

nodo 3 testando no tempo 60.0 [s=2]:  1 0 
  nodo 1 falho
  nodo 0 correto
  State[3]: | 0: correto [1]| 1: falho   [1]| 2: correto [1]| 3: correto [0]| 4: unknown [-1]| 5: unknown [-1]|
                                                                                                                                                                     [25/1933]
nodo 4 testando no tempo 60.0 [s=2]:  6 7                                                                                                                                     
  State[4]: | 0: unknown [-1]| 1: unknown [-1]| 2: unknown [-1]| 3: unknown [-1]| 4: correto [0]| 5: correto [1]|                                                             
                                                                                                                                                                              
nodo 0 testando no tempo 90.0 [s=3]:  4 5 6 7                                                                                                                                 
  nodo 4 correto                                                                                                                                                              
  State[0]: | 0: correto [0]| 1: falho   [1]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: correto [1]|                                                                 
                                                                                                                                                                              
nodo 2 testando no tempo 90.0 [s=3]:  6 7 4 5                                                                                                                                 
  State[2]: | 0: correto [0]| 1: correto [1]| 2: correto [0]| 3: correto [1]| 4: unknown [-1]| 5: unknown [-1]|                                                               

nodo 3 testando no tempo 90.0 [s=3]:  7 6 5 4 
  State[3]: | 0: correto [1]| 1: falho   [1]| 2: correto [1]| 3: correto [0]| 4: unknown [-1]| 5: unknown [-1]| 

nodo 4 testando no tempo 90.0 [s=3]:  0 1 2 3 
  nodo 0 correto
  State[4]: | 0: correto [0]| 1: falho   [1]| 2: correto [1]| 3: correto [1]| 4: correto [0]| 5: correto [1]| 

nodo 1 recuperou no tempo 91.0

nodo 0 testando no tempo 120.0 [s=1]:  1 
  nodo 1 correto
  State[0]: | 0: correto [0]| 1: correto [2]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: correto [1]| 

nodo 2 testando no tempo 120.0 [s=1]:  3 
  nodo 3 correto
  State[2]: | 0: correto [1]| 1: correto [1]| 2: correto [0]| 3: correto [1]| 4: unknown [-1]| 5: unknown [-1]| 

nodo 3 testando no tempo 120.0 [s=1]:  2 
  nodo 2 correto
  State[3]: | 0: correto [1]| 1: correto [1]| 2: correto [1]| 3: correto [0]| 4: unknown [-1]| 5: unknown [-1]| 

nodo 4 testando no tempo 120.0 [s=1]:  5 
  nodo 5 falho
  State[4]: | 0: correto [0]| 1: falho   [1]| 2: correto [1]| 3: correto [1]| 4: correto [0]| 5: falho   [2]| 

nodo 1 testando no tempo 121.0 [s=2]:  3 2  
  nodo 3 correto
  State[1]: | 0: correto [1]| 1: correto [0]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: correto [1]|

nodo 0 testando no tempo 150.0 [s=2]:  2 3 
  nodo 2 correto
  State[0]: | 0: correto [0]| 1: correto [2]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: correto [1]| 

nodo 2 testando no tempo 150.0 [s=2]:  0 1 
  nodo 0 correto
  State[2]: | 0: correto [1]| 1: correto [2]| 2: correto [0]| 3: correto [1]| 4: correto [1]| 5: correto [1]| 

nodo 3 testando no tempo 150.0 [s=2]:  1 0 
  nodo 1 correto
  State[3]: | 0: correto [1]| 1: correto [1]| 2: correto [1]| 3: correto [0]| 4: correto [1]| 5: correto [1]| 

nodo 4 testando no tempo 150.0 [s=2]:  6 7 
  State[4]: | 0: correto [0]| 1: falho   [1]| 2: correto [1]| 3: correto [1]| 4: correto [0]| 5: falho   [2]| 

nodo 1 testando no tempo 151.0 [s=3]:  5 4 7 6 
  nodo 5 falho
  nodo 4 correto
  State[1]: | 0: correto [1]| 1: correto [0]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: falho   [2]| 

nodo 0 testando no tempo 180.0 [s=3]:  4 5 6 7 
  nodo 4 correto
  State[0]: | 0: correto [0]| 1: correto [2]| 2: correto [1]| 3: correto [1]| 4: correto [1]| 5: falho   [2]