Canais Assíncronos I

Mestrado e Doutorado em Ciência da ComputaçãoMestrado e Doutorado em Ciência da ComputaçãoUniversidade Federal do CearáUniversidade Federal do Ceará

II. Memória DistibuídaII. Memória Distibuída

Passagem de Passagem de Mensagens AssíncronaMensagens Assíncrona

Fco. Heron de Carvalho Jr., Dr.Fco. Heron de Carvalho Jr., [email protected]

Prog. Concorrente – Prof. Dr. Francisco Heron de Carvalho JuniorProg. Concorrente – Prof. Dr. Francisco Heron de Carvalho JuniorDepartamento de Computação – UFC Departamento de Computação – UFC 22

IntroduçãoIntrodução

Os construtores de sincronização estudados até Os construtores de sincronização estudados até agora assumem a existência de uma agora assumem a existência de uma memória memória compartilhadacompartilhada;;• Variáveis Variáveis globaisglobais visíveis aos processos; visíveis aos processos;

Desde a última década, arquiteturas de memória Desde a última década, arquiteturas de memória distribuída tem se tornado comuns;distribuída tem se tornado comuns;• Memória local a cada processador;Memória local a cada processador;• Assume-se cada processo em num processador;Assume-se cada processo em num processador;

» Sistemas concorrentes distribuídos;Sistemas concorrentes distribuídos;

• Processos compartilham uma rede de comunicação;Processos compartilham uma rede de comunicação;



Tipos de processo em programas Tipos de processo em programas distribuídos:distribuídos:• FiltrosFiltros: transformadores de dados: transformadores de dados

• ClientesClientes: ativadores de requisições;: ativadores de requisições;• ServidoresServidores: reagem a estímulos (reativos);: reagem a estímulos (reativos);• PeerPeer: um dentre uma coleção de processos : um dentre uma coleção de processos

idênticos que interagem para solucionar um idênticos que interagem para solucionar um problema;problema;



Comunicação em sistemas distribuídosComunicação em sistemas distribuídos• Operações primitivas de rede;Operações primitivas de rede;

» Exigem sincronização por espera ocupada;Exigem sincronização por espera ocupada;

• Definição de operações especiais de rede que Definição de operações especiais de rede que incluem sincronização:incluem sincronização:» Semelhante a o que Semelhante a o que semáforossemáforos são para são para variáveis variáveis

compartilhadascompartilhadas;;» Primitivas de passagem de mensagensPrimitivas de passagem de mensagens;;



Passagem de MensagensPassagem de Mensagens• CanaisCanais

» Abstração de um meio físico de transmissão na rede;Abstração de um meio físico de transmissão na rede;» Caminho de comunicação entre dois processos;Caminho de comunicação entre dois processos;» Fila de mensagens;Fila de mensagens;» Únicos objetos compartilhados por processosÚnicos objetos compartilhados por processos

• Primitivas Primitivas sendsend and and receivereceive : :» Processo executa Processo executa send send para para enviarenviar um dado através de um um dado através de um

canal;canal;» Processo executa Processo executa receive receive em um canal para em um canal para receberreceber um um

dado que foi enviado por outro processo através deste canal;dado que foi enviado por outro processo através deste canal;» SincronizaçãoSincronização é realizada uma vez que uma mensagem não é realizada uma vez que uma mensagem não

pode ser recebida até depois de ser enviada;pode ser recebida até depois de ser enviada;


Passagem de Mensagens Passagem de Mensagens AssíncronaAssíncrona

Canais são Canais são filas de mensagensfilas de mensagens, de tamanho , de tamanho potencialmente potencialmente infinitoinfinito;;• sendsend acrescenta um dado na cauda da fila; acrescenta um dado na cauda da fila;• receivereceive retira um dado da frente da fila; retira um dado da frente da fila;

Analogia com semáforos;Analogia com semáforos;• sendsend e e receivereceive podem ser vistas como operações podem ser vistas como operações VV e e

PP, respectivamente, mas carregando dados;, respectivamente, mas carregando dados;• Número de elementos na fila de mensagens não Número de elementos na fila de mensagens não

recebidas no canal é o recebidas no canal é o contadorcontador do semáforo. do semáforo.



Notação:Notação:• chanchan chch(id(id11:type:type11,..., id,..., idnn:type:typenn))

• Exemplos:Exemplos:» chanchan inputinput((charchar))

» chanchan disk_accessdisk_access((cylindercylinder, , blockblock, , countcount::intint,, bufferbuffer::ptrptr [*] [*] charchar))

» chanchan resultresult[1:[1:nn](](intint))


Passagem de Mensagens Passagem de Mensagens Assíncrona (Assíncrona (NotaçãoNotação))

send send chch((exprexpr11,..., ,..., exprexprnn))

• Os tipos de Os tipos de exprexprii devem corresponder aos devem corresponder aos

tipos dos componentes do canal;tipos dos componentes do canal;• Exemplos:Exemplos:

» send send inputinput (2)(2)

» send send disk_accessdisk_access(454,23, 10, data)(454,23, 10, data)» send send resultresult[2] (4)[2] (4)

• Não-blocante;Não-blocante;» Dado é enfileirado no canal;Dado é enfileirado no canal;



receive receive chch((outout varvar11,..., ,..., outout varvarnn))

• Os tipos de Os tipos de varvarii devem corresponder aos tipos devem corresponder aos tipos

dos componentes do canal;dos componentes do canal;• Exemplos:Exemplos:

» receive receive inputinput (in)(in)

» receive receive disk_accessdisk_access(cyl, bl, c, data)(cyl, bl, c, data)» result result resultresult[2] (r)[2] (r)

• blocanteblocante» Processo é bloqueado quando a fila está vazia;Processo é bloqueado quando a fila está vazia;



Assume-se:Assume-se:• canais seguros;canais seguros;

» Sem corrupção de mensagens;Sem corrupção de mensagens;» Sem replicação de mensagens;Sem replicação de mensagens;» Sem perda de mensagens;Sem perda de mensagens;

• mensagens ordenadas;mensagens ordenadas;» Recebimento na ordem de envio;Recebimento na ordem de envio;



chan chan inputinput(char), (char), outputoutput([1:MAXLINE] char)([1:MAXLINE] char)Char_to_LineChar_to_Line:::: var var lineline[1:MAXLINE]: char, [1:MAXLINE]: char, ii:int := 1:int := 1 do true do true receive receive inputinput((lineline[i])[i]) do line[ do line[ii] ] CR and CR and ii < MAXLINE < MAXLINE {*} {*} ii := := ii + 1; receive + 1; receive inputinput((lineline[i])[i]) od od send send outputoutput((lineline); ); ii:=1:=1 od od

* = line[1:i] contains last * = line[1:i] contains last ii input characters input characters



empty empty chch• Verifica se o canal está vazioVerifica se o canal está vazio• Útil em diversas situações;Útil em diversas situações;• Não é um comando seguro;Não é um comando seguro;



Uso de canais:Uso de canais:• mailboxesmailboxes: qualquer processo pode enviar ou : qualquer processo pode enviar ou

receber de qualquer canal;receber de qualquer canal;

• input portinput port: : um canal possui exatamente um canal possui exatamente umum processo que envia, embora processo que envia, embora váriosvários possam possam receber;receber;

• linklink:: exatamente exatamente umum processo pode processo pode escreverescrever e e exatamente exatamente umum processo pode processo pode lerler no canal; no canal;

Mestrado e Doutorado em Ciência da ComputaçãoMestrado e Doutorado em Ciência da ComputaçãoUniversidade Federal do CearáUniversidade Federal do Ceará

II. Memória DistibuídaII. Memória Distibuída

Cap.Cap.77Passagem de Passagem de

Mensagens AssíncronaMensagens Assíncrona((AplicaAplicaçõesções))

Fco. Heron de Carvalho Jr., Dr.Fco. Heron de Carvalho Jr., [email protected]


Passagem de Mensagens Passagem de Mensagens Assíncrona (Aplicações)Assíncrona (Aplicações)

Redes de FiltrosRedes de Filtros

((ordenaçãoordenação))


Redes de Filtros OrdenaçãoRedes de Filtros Ordenação

Solução usando um processo Solução usando um processo SortSort• SORT: SORT: i: 1 i: 1 i i n: sent[i] n: sent[i] sent[i+1] sent[i+1]

valores enviados por valores enviados por output output são uma são uma permutação de valores recebidos de input;permutação de valores recebidos de input;

Esboço de solução:Esboço de solução:

recebareceba os números pelo canal os números pelo canal inputinputordene os númerosordene os númerosenvieenvie os números ordenados ao canal output os números ordenados ao canal output

Uso de valores Uso de valores sentinelassentinelas::• Detectando o final de uma lista;Detectando o final de uma lista;



Entretanto podemos utilizar uma rede de Entretanto podemos utilizar uma rede de processos para efetuar a ordenação;processos para efetuar a ordenação;

Processo MERGEProcesso MERGE• Recebe os valores ordenados de duas streams Recebe os valores ordenados de duas streams

ordenadas ordenadas in1in1 e e in2in2; ; • Produz uma nova Produz uma nova stream stream outout com os elementos com os elementos

recebidos ordenados;recebidos ordenados;

Na terminação do processoNa terminação do processo Merge Merge ... ...• MERGEMERGE: : in1in1 e e in2in2 são vazias são vazias sent[n+1] = EOS sent[n+1] = EOS ( (i: i:

1 1 i i n: sent[i] n: sent[i] sent[i+1]) sent[i+1]) valores enviados por valores enviados por outputoutput são uma permutação de valores recebidos de são uma permutação de valores recebidos de in1in1 e e in2in2;;




chan chan in1in1(int), (int), in2in2(int), (int), outout(int)(int)Merge :: var v1, v2: intMerge :: var v1, v2: int receivereceive in1in1(v1); (v1); receivereceive in2in2(v2);(v2); do do more input to process more input to process ->-> sendsend out(smaller from out(smaller from in1in1 or or in2in2)) receivereceive from from in1in1 or or in2in2 od od sendsend out(EOS) {MERGE} out(EOS) {MERGE}




chan chan in1in1(int), (int), in2in2(int), (int), outout(int);(int);Merge :: var v1, v2: intMerge :: var v1, v2: int receivereceive in1in1(v1); (v1); receivereceive in2in2(v2);(v2); do do v1 v1 EOS EOS v2 v2 EOSEOS ->-> if v1 if v1 v2 -> v2 -> sendsend out(v1); out(v1); receivereceive in1(v1); in1(v1); [] v2 [] v2 > > v1 -> v1 -> sendsend out(v2); out(v2); receivereceive in2(v2); in2(v2); fi fi [] [] v1 v1 EOS EOS v2 = v2 = EOS -> EOS -> sendsend out(v1); out(v1); receivereceive in1(v1); in1(v1); [] [] v1 v1 == EOS EOS v2 v2 EOS ->EOS -> sendsend out(v2); out(v2); receivereceive in2(v2); in2(v2); od od sendsend out(EOS) {MERGE} out(EOS) {MERGE}



Processos Merge podem ser organizados Processos Merge podem ser organizados em uma rede em árvore (ver em uma rede em árvore (ver quadroquadro););

Canais de Canais de entradaentrada e e saídasaída devem ser devem ser compartilhados;compartilhados;• Nomeação Nomeação estáticaestática;;• Nomeração Nomeração dinâmicadinâmica;;

FiltrosFiltros podem ser organizados de outras podem ser organizados de outras formas;formas;



Clientes e ServidoresClientes e Servidores



ServidorServidor é um processo que repetidamente é um processo que repetidamente atende requisições de processos atende requisições de processos clientesclientes;;

Como programar servidores com Como programar servidores com passagem de mensagens ?passagem de mensagens ?• Solução derivada de monitores;Solução derivada de monitores;• DualidadeDualidade entre entre monitoresmonitores e e passagem de passagem de

mensagemmensagem;;



Monitores AtivosMonitores Ativos• Monitores são Monitores são gerenciadores de recursosgerenciadores de recursos;;• Simulando monitores com processos Simulando monitores com processos servidoresservidores e e

passagem de mensagenspassagem de mensagens;;• Inicialmente, assuminos uma única operação e o não Inicialmente, assuminos uma única operação e o não

emprego de variáveis condicionais;emprego de variáveis condicionais;

• monitormonitor MnameMname #Invariant MI #Invariant MI varvar permanent variables permanent variables initialization code initialization code procedureprocedure op( op(formalsformals) body of ) body of opop end endendend



chan chan requestrequest(int,(int,types of value formalstypes of value formals))chan chan replyreply[1:n]([1:n](types of result formalstypes of result formals))SnameSname:: var :: var permanent variablespermanent variables var var indexindex:int, :int, value formalsvalue formals, , result formalsresult formals initialization codeinitialization code do true do true {loop invariant MI}{loop invariant MI} receive receive requestrequest((indexindex, , value formalsvalue formals)) body of op body of op # return reply to process that sent request# return reply to process that sent request send send replyreply[[indexindex](](result formalsresult formals)) od odClientClient[[ii:1..n]:: :1..n]:: send send requestrequest((ii, , value argumentsvalue arguments) ) # “call” op# “call” op receive receive replyreply[[ii](](result argumentsresult arguments) ) # wait for reply# wait for reply … …



Cuidados especiais com clientesCuidados especiais com clientes• Uso dos canais Uso dos canais reply reply (canais de resposta);(canais de resposta);

Uso de nomeação dinâmica de canais;Uso de nomeação dinâmica de canais;• clientes não acessam clientes não acessam canal de respostacanal de resposta de outro cliente; de outro cliente;• Permite numero Permite numero variávelvariável de clientes; de clientes;

Monitores com múltiplos procedimentos:Monitores com múltiplos procedimentos:• Procedimento chamado como argumento de Procedimento chamado como argumento de requestrequest;;

• Argumentos e retorno de cada procedimento varia !!Argumentos e retorno de cada procedimento varia !!» Tipos variantes ou enumerações;Tipos variantes ou enumerações;» Empacotamento/Desempacotamento pelo cliente;Empacotamento/Desempacotamento pelo cliente;



type type op_kindop_kind = enum( = enum(opop11,…,,…,opopnn))type type arg_typearg_type = union( = union(argarg11::atypeatype11,…,…argargnn::atypeatypenn))type type result_typeresult_type = union( = union(resres11::rtypertype11,…,,…,resresnn::rtypertypenn))chan chan requestrequest(int,(int,op_kindop_kind, , arg_typearg_type))chan chan replyreply[1:[1:nn](](res_typeres_type)) … …



……

SnameSname::var permanent variables::var permanent variables var var indexindex:int, :int, kindkind::op_kindop_kind, , argsargs::arg_typearg_type, , resultsresults::res_typeres_type initialization code initialization code do true do true {loop invariant MI}{loop invariant MI} receive receive requestrequest((indexindex, , kindkind, , argsargs)) if if kindkind = = opop11 body of body of opop11

[] … [] … [] [] kindkind = = opopnn body of body of opopnn

fifi send send replyreply[[indexindex](result formals)](result formals) od od……



ClientClient[[ii:1..n]:: :1..n]::

var var myargsmyargs::arg_typearg_type, , myresultsmyresults: : result_typeresult_type place place value argumentsvalue arguments in in myargsmyargs send send requestrequest((ii, , opopii, , myargsmyargs) ) # “call” op# “call” op receive receive replyreply[[ii](](myresultsmyresults) ) # wait for reply# wait for reply … …



Até o momento não consideramos variáveis Até o momento não consideramos variáveis condicionais;condicionais;

Usaremos um exemplo para mostrar como Usaremos um exemplo para mostrar como contruir soluções cliente/servidor a partir de contruir soluções cliente/servidor a partir de monitores que empregam variáveis condicionais;monitores que empregam variáveis condicionais;

Resource_AllocatorResource_Allocator• acquireacquire(res id: int)(res id: int)• releaserelease(id: int)(id: int)• Clientes requisitam e liberam recursos um de cada vezClientes requisitam e liberam recursos um de cada vez



monitor monitor Resource_AllocatorResource_Allocatorvar var availavail:int := MAXUNITS, :int := MAXUNITS, unitsunits:set of int := initial values :set of int := initial values var var freefree:cond :cond procedure procedure acquireacquire(res id: int)(res id: int) if if availavail = 0 -> wait( = 0 -> wait(freefree)) [] [] availavail > 0 -> > 0 -> availavail := := availavail – 1 – 1 if if idid := remove( := remove(unitsunits))endendprocedure procedure releaserelease((idid:unit):unit) insertinsert((idid, , unitsunits)) if empty( if empty(freefree) -> ) -> availavail := := availavail + 1 + 1 [] not empty( [] not empty(freefree) -> signal() -> signal(freefree)) fi fiendend

endend



type op_kind = enum(ACQUIRE,RELEASE)type op_kind = enum(ACQUIRE,RELEASE)

chan request(index, op_kind, unitid:int)chan request(index, op_kind, unitid:int)

chan reply[1:n](int)chan reply[1:n](int)



Allocator::var Allocator::var availavail:int := MAXUNITS, units: set of int:int := MAXUNITS, units: set of int

var var pendingpending: queue of int: queue of int

var var indexindex:int, :int, kindkind:op_kind, :op_kind, unitidunitid:int:int

code to initialize units to appropriate valoescode to initialize units to appropriate valoes

do true ->do true ->

receive receive requestrequest((indexindex,,kindkind,,unitidunitid))

if if kindkind = ACQUIRE -> = ACQUIRE ->

código de acquirecódigo de acquire

[] [] kindkind = RELEASE = RELEASE

código de releasecódigo de release

fifi

odod



Código de Código de acquireacquire::

……

iif f availavail > 0 > 0 # honor request now# honor request now availavail := := availavail - 1; - 1; unitidunitid := remove( := remove(unitsunits)) send send replyreply[[indexindex](](unitidunitid))[] [] availavail = 0 = 0 # remenber request# remenber request insert( insert(pendingpending,,indexindex))fifi……



Código de Código de releaserelease::

……

if empty(pending) if empty(pending) # return unitid# return unitid avail := avail + 1; insert(units, unitid) avail := avail + 1; insert(units, unitid)[] not empty(pending) [] not empty(pending) # allocate unitid# allocate unitid index := remove(pending) index := remove(pending) send reply[index](unitid) send reply[index](unitid)fifi……



MonitoresMonitores• Variáveis permanentes;Variáveis permanentes;• Indentificadores de Indentificadores de

procedimento;procedimento;• Chamada de procedimento;Chamada de procedimento;

• Comando Comando waitwait;;

• Comandos Comandos signalsignal;;

• Corpos de procedimentos; Corpos de procedimentos;

Passagem de MensagemPassagem de Mensagem• Variáveis locais do servidor;Variáveis locais do servidor;• Canal resposta e tipos de Canal resposta e tipos de

operação;operação;• sendsend request; request;

receivereceive reply; reply;• Salvar requisições Salvar requisições

pendentes;pendentes;• Recuperar e processar Recuperar e processar

requisições pendentes;requisições pendentes;• Comandos Comandos casecase no tipo da no tipo da

operação;operação;



Em um Em um sistema hierárquicosistema hierárquico, servidores em , servidores em um nível são frequentemente clientes de um nível são frequentemente clientes de servidores em um nível mais baixo;servidores em um nível mais baixo;

Servidores possuem toda a informação Servidores possuem toda a informação necessária para processar as requisições necessária para processar as requisições do cliente;do cliente;



Veremos agora outro tipo de interação de Veremos agora outro tipo de interação de servidores;servidores;• Servidores em um mesmo nível são Servidores em um mesmo nível são parespares que que

cooperam para prover um serviço;cooperam para prover um serviço;• Computações distribuídasComputações distribuídas onde nenhum dos onde nenhum dos

servidores possuem informações servidores possuem informações suficientessuficientes para atender um cliente;para atender um cliente;

Veremos a partir de agora diferentes tipos Veremos a partir de agora diferentes tipos de problemas derivados desta mesma de problemas derivados desta mesma idéia e suas soluções;idéia e suas soluções;



Algoritmos SistólicosAlgoritmos SistólicosComputação distribuída da topologia de uma rede de Computação distribuída da topologia de uma rede de

processosprocessos


Algoritmos Sistólicos Algoritmos Sistólicos ((HeartbeatHeartbeat))

Examinaremos agora um problema dentro da Examinaremos agora um problema dentro da classe de soluções através de algoritmos classe de soluções através de algoritmos sistólicos:sistólicos:• Computação distribuída da topologia Computação distribuída da topologia arbitráriaarbitrária de uma de uma

rede de processos;rede de processos;• Processos executam repetidamente as seguintes Processos executam repetidamente as seguintes

operações, até uma operações, até uma condição de terminaçãocondição de terminação::» Um processo informa as informações que contém sobre a Um processo informa as informações que contém sobre a

topologia para os vizinhos; topologia para os vizinhos; » Recebe as informações que os vizinhos tem sobre a topologiaRecebe as informações que os vizinhos tem sobre a topologia» Combina as informações;Combina as informações;

• Analogia com Analogia com batimentos cardíacos batimentos cardíacos ((sístolesístole e e diástolediástole))



Solução usando variáveis compartilhadas:Solução usando variáveis compartilhadas:

TOPOLOGY: (TOPOLOGY: (p,q: 1p,q: 1ppn, 1n, 1qqn:n: toptop[p,q][p,q]linkslinkspp[q]) [q])

var top[1:n,1:n]:bool := ([n+n] False);var top[1:n,1:n]:bool := ([n+n] False);

Node[p:1..n]:: var links[1:n]:boolNode[p:1..n]:: var links[1:n]:bool # inicialmente links[q] é verdade se# inicialmente links[q] é verdade se # q é vizinho de p # q é vizinho de p fa q:=1 to n st links[q] -> fa q:=1 to n st links[q] -> top[p,q] := True top[p,q] := True af af { top[p,1:n] = links[1:n] } { top[p,1:n] = links[1:n] }……



Solução distribuída óbvia:Solução distribuída óbvia:• Cada processo envia seu vetor Cada processo envia seu vetor links links para um processo para um processo

coordenador T;coordenador T;• Mas para isso T teria que estar conectado a cada um Mas para isso T teria que estar conectado a cada um

dos processos, o que não é uma suposição razoável;dos processos, o que não é uma suposição razoável;• SoluçãoSolução: processos vizinhos de T passariam adiante as : processos vizinhos de T passariam adiante as

mensagens dos demais processos;mensagens dos demais processos;» Solução Solução assimétricaassimétrica;;» Difícil de desenvolver, entender e sujeita a falhas, sendo mais Difícil de desenvolver, entender e sujeita a falhas, sendo mais

difícil a correção destas;difícil a correção destas;

• Devemos buscar uma solução Devemos buscar uma solução simétricasimétrica;;



Solução simétrica:Solução simétrica:• Cada processo computa a topologia dCada processo computa a topologia de toda ae toda a rede rede;;• Inicialmente cada processo sabe a informação de suas Inicialmente cada processo sabe a informação de suas

conexão com seus vizinhos;conexão com seus vizinhos;• Realiza repetidamente as seguintes operações:Realiza repetidamente as seguintes operações:

» Enviar aos vizinhos seu conhecimento local sobre a topologia;Enviar aos vizinhos seu conhecimento local sobre a topologia;» Perguntar o que cada vizinho sabe sobre a topologia;Perguntar o que cada vizinho sabe sobre a topologia;» Combinar com o que o processo sabe;Combinar com o que o processo sabe;

• A cada A cada rr passos, o processo conhece as informações passos, o processo conhece as informações sobre a sub-rede composta pelos processos que estão sobre a sub-rede composta pelos processos que estão a distância a distância rr dele: dele:

» ROUND: (ROUND: (q: 1q: 1qqn: (dist(p,q) n: (dist(p,q) r r top[p,*] filled in) top[p,*] filled in)



Solução simétrica (cont.):Solução simétrica (cont.):• Terminação:Terminação:

» Em D passos, onde D é o diâmetro da rede, Em D passos, onde D é o diâmetro da rede, assegura-se que cada processo sabe a topologia assegura-se que cada processo sabe a topologia total da rede;total da rede;

» É necessário portanto conhecer o diâmetro da rede;É necessário portanto conhecer o diâmetro da rede;

• Veja a solução a seguir:Veja a solução a seguir:



chan topology[1:n](1:n, 1:n) bool) chan topology[1:n](1:n, 1:n) bool) Node[p:1..n]: : var links[1:n]:boolNode[p:1..n]: : var links[1:n]:bool var top[1:n, 1:n]: bool := ([n*n] false) var top[1:n, 1:n]: bool := ([n*n] false) top[p,1..n] := linkstop[p,1..n] := links var r:int := 0 var r:int := 0 var newtop[1:n, 1:n]: bool var newtop[1:n, 1:n]: bool {top[p,1:n] = links[1:n] {top[p,1:n] = links[1:n] r = 0} {ROUND} r = 0} {ROUND} do r < D -> do r < D -> fa q:=1 to n st links[q] -> fa q:=1 to n st links[q] -> sendsend topology[q](top) af topology[q](top) af fa q:=1 tp n st links[q] -> fa q:=1 tp n st links[q] -> receivereceive topology[p](newtop) topology[p](newtop) top := top or newtop af top := top or newtop af r := r + 1 r := r + 1 od od {ROUND {ROUND r = D} {TOPOLOGY} r = D} {TOPOLOGY}



Neste algoritmo é necessário conhecer o Neste algoritmo é necessário conhecer o diâmetrodiâmetro da rede: da rede:• Suposição nem sempre realista;Suposição nem sempre realista;

Nova solução (D desconhecido):Nova solução (D desconhecido):• Processo satisfaz-se quando em cada linha de Processo satisfaz-se quando em cada linha de

top existe pelo menos uma entrada top existe pelo menos uma entrada TrueTrue;;» Supondo-se Supondo-se Rede conectadaRede conectada (existe um caminho (existe um caminho

entre cada par de processos);entre cada par de processos);

• Mensagem adicional para informar vizinhos Mensagem adicional para informar vizinhos sempre que detectar finalização;sempre que detectar finalização;



Seja D o diâmetro da rede e m o máximo Seja D o diâmetro da rede e m o máximo número de vizinhos de um processo:número de vizinhos de um processo:• Número de mensagens trocadas é limitada por Número de mensagens trocadas é limitada por

2 * 2 * nn * * mm * (D + 1); * (D + 1);

• Cada um dos Cada um dos n n processos executa no máximo processos executa no máximo D + 1 estágios, trocando 2 mensagens com D + 1 estágios, trocando 2 mensagens com cada um de seus possíveis (no máximo) cada um de seus possíveis (no máximo) mm vizinhos;vizinhos;



Qualquer algoritmos sistólico possui a Qualquer algoritmos sistólico possui a mesma estrutura do algoritmo discutido;mesma estrutura do algoritmo discutido;

O que varia é o O que varia é o conteúdo das mensagensconteúdo das mensagens e estas e estas como são processadascomo são processadas;;

Outra diferença importante é a Outra diferença importante é a condição de condição de terminaçãoterminação::• Nem sempre pode ser decidida localmente;Nem sempre pode ser decidida localmente;


Próxima AulaPróxima Aula

Algoritmos Algoritmos probe/echoprobe/echo;;• Sondagem e eco;Sondagem e eco;

Algoritmos Algoritmos broadcastbroadcast;;• Disseminação;Disseminação;

Algoritmos Algoritmos token-passingtoken-passing;;

Replicação de servidores;Replicação de servidores;

Documents

Canais Assíncronos I