Algoritmo de Bully
Em sistemas distribuídos, diversos algoritmos necessitam que um processo funcione como coordenador, inicializador, sequenciador, enfirm, ter um papel especial. No caso de falha deste processo coordenador, pode acontecer o comprometimento das tarefas sendo realizadas, então um novo coordenador deve assumir. Para a escolha do novo coordenador existem alguns algoritmos especiais, chamados algoritmos de eleição. Um destes algoritmos é o Algoritmo de Bully. O algoritmo de Bully, desenvolvido por Garcia-Mollina em 1982, assume que um processo sabe a prioridade de todos os outros processos no sistema. Quando um processo Pi detecta que o coordenador não está mais respondendo a um pedido de serviço, ele inicia uma eleição da seguinte forma:
- Pi envia uma mensagem de Eleição para todos os processos com prioridade maior do que a sua.
- Se nenhum processo responde, Pi vence a eleição e torna-se o coordenador, avisando a todos os outros processos com menor prioridade que ele é o novo coordenador.
A implementação
Este código foi desenvolvido para uma disciplina de Sistemas Distribuídos de uma Pós-Graduação que cursei. Foi desenvolvido usando-se sockets Unix, assim o PID é o valor da prioridade, quanto maior o PID maior a prioridade. Para testar é só executar o script várias vezes e depois matar um deles. Os outros processos iniciarão a eleição na procura pelo processo com maior prioridade (PID maior do que o seu). O processo com PID maior assumirá como coordenador e avisará aos outros que a eleição acabou e que ele é o novo coordenador. O curioso foi que o professor não queria aceitar o programa porque não era desenvolvido em C, a linguagem que ele solicitou. Depois de mostrar o código e o programa em execução ele mudou de idéia e aceitou o programa. E eu tirei A. Interessante exemplo de programação científica usando python.
O código
1 #!/usr/bin/python
2 import socket
3 import os
4 import string
5 import exceptions
6 import sys
7
8 ## Variaveis globais
9 mySock = 0
10 ## Path onde estao os sockets
11 SPATH='/tmp/bully'
12
13 ## Funcao q manda mensagem
14 def sendMsg(dest,msg):
15 global mySock
16 try:
17 ns = socket.socket(socket.AF_UNIX,socket.SOCK_STREAM)
18 ns.connect((dest))
19 ns.send(msg+';'+mySock)
20 ns.close()
21 return 1
22 except:
23 return 0
24 ## Funcao q fica se comunicando com o coordenador para ver se esta ativo
25 def verificaCoord(coord):
26 global SPATH
27 global mySock
28
29 while 1:
30 ## Verifica se o coordenador esta ativo
31 status = sendMsg(coord,'1')
32 if status == 0:
33 print 'Coodenador parado '+str(coord)+'. Iniciando Eleicao'
34 list = os.listdir(SPATH)
35 for i in list:
36 if string.atoi(i) > string.atoi(mySock):
37 status = sendMsg(i,'E')
38 if status == 0:
39 print 'Erro enviando E ao processo '+i
40 break
41 else:
42 print 'Conectou no coordenador '+coord
43 return 0
44
45 def main():
46 ## Variaveis
47 fCord = 1
48 BUF=1024
49
50 global mySock
51 global SPATH
52 try:
53 ## Se recebeu um argumento he um processo recussitado
54 mySock = sys.argv[1]
55 ## Testa se existem processos com prioridade maior
56 list = os.listdir(SPATH)
57 for i in list:
58 if string.atoi(i) > string.atoi(mySock):
59 status = sendMsg(i,'1')
60 if status == 1:
61 fCord = 0 ## Se houver processos maiores, nao he coordenador
62 continue
63 ## Se for o maior anuncia a todos
64 if fCord == 1:
65 for i in list:
66 if string.atoi(i) < string.atoi(mySock):
67 status = sendMsg(i,'C')
68 except:
69 ## Nome do socket = pid do processo
70 mySock=str(os.getpid())
71 fCord = 0
72 print 'Iniciando. PID='+str(mySock)
73 ## Verifica se existe o diretorio para os sockets
74 try:
75 os.chdir(SPATH)
76 except:
77 ## Se nao existe cria o diretorio
78 os.mkdir(SPATH)
79 try:
80 ## Cria o socket
81 s = socket.socket(socket.AF_UNIX,socket.SOCK_STREAM)
82 s.bind((mySock)) ## Atribui um nome ao socket
83 s.listen(1) ## Estabelece fila para conexoes
84 ## Inicialmente o menor PID he o coordenador
85 list = os.listdir(SPATH)
86 ## Ordena os pids e pega o primeiro
87 list.sort(cmp)
88 if list:
89 COORD=list[0]
90 else:
91 COORD=mySock
92 ## Nao he o coordenador
93 if COORD != mySock and fCord == 0:
94 ## Divide o processo
95 childPID = os.fork()
96 if childPID == 0:
97 ## O filho permanece testando o coordenador
98 verificaCoord(COORD)
99 #sys.exit(1)
100 else:
101 COORD = mySock
102 print 'Eu sou o coordenador '+str(mySock)
103 ## Todos os processos pais permanecem em wait, aguardando conexao
104 conn, addr = s.accept()
105 data = conn.recv(BUF)
106 while 1:
107 if data:
108 msg = string.split(data,';')
109 ## Se a mensagem recebida for de eleicao
110 if msg[0] == 'E':
111 print 'Recebido mensagem '+msg[0]+' de PID='+str(msg[1])
112 ## Enviar msg para pid menor parar eleicao
113 sendMsg(msg[1],'PE')
114 #procura se tem alguem maior q ele
115 list = os.listdir(SPATH)
116 maior = 1
117 for i in list:
118 if string.atoi(i) > string.atoi(mySock):
119 #print 'Enviar para PID '+i
120 status = sendMsg(i,'E')
121 if status == 1:
122 maior = 0
123 #se for o maior envia msg para todos como novo coord.
124 if maior == 1:
125 print 'Eu sou o novo Coordenador '+str(mySock)
126 os.kill(childPID,9)
127 for i in list:
128 if string.atoi(i) < string.atoi(mySock):
129 print 'enviando C para '+str(i)
130 send = sendMsg(i,'C')
131
132 ## Recebeu msg para parar eleicao
133 if msg[0] == 'PE':
134 print 'Recebida mensagem '+msg[0]+' de PID='+str(msg[1])
135 ## Recebeu msg de verificacao de conexao
136 #if msg[0] == '1':
137 # print 'Recebida mensagem '+msg[0]+' de PID='+str(msg[1])
138 ## Recebeu msg de coordenador
139 if msg[0] == 'C':
140 print 'Novo coordenador '+msg[1]
141 os.kill(childPID,9)
142 childPID = os.fork()
143 if childPID == 0:
144 ## Novo filho gerado monitora o novo coordenador
145 verificaCoord(msg[1])
146 #sys.exit(1)
147 data = conn.recv(BUF)
148 else:
149 conn, addr = s.accept()
150 data = conn.recv(BUF)
151 except:
152 print "Unexpected error:", sys.exc_info()[0]
153 s.close()
154 os.remove(SPATH+'/'+str(mySock))
155 print 'Processo '+str(mySock)+' parando'
156
157
158 ## Invoca a funcao main na inicializacao do programa
159 if __name__ == '__main__':
160 main()
Links
