Exclusão Mútua Distribuída
Principais Referências:
• Livro: Chow, Johnson, Cap. 10
• Livro: M.Raynal: Distributed Algorithms and Protocols, Cap. 2
• Livro Valmir Barbosa: An Introduction to Distr. Algorithms, Cap. 8
• Velazquez, M., A Survey of Distributed Mutual Exclusion Algorithms,
Technical Report CS-93-116, Colorado State University, 1993
© Markus Endler
1
Observações sobre Notação
A maioria dos Algoritmos serão descritos em pseudo-código, onde:
• a variável “me” (ou equivalente) contém o índice do processo corrente
e não pode ser alterada
• as demais variáveis são globais no processo
• não há compartilhamento de variáveis entre processos, mas estes
podem ter várias threads que compartilham as variáveis globais
• cada thread será composta de “clausulas reativas” da forma:
[when] Evento [&& Condição] => { Ações }
Onde:
Evento: pode ser de controle (START), chamada da aplicação,
chegada de mensagem (recvd), ou de temporização (timer T1);
Condição: sobre as variáveis que habilita/desabilita esta clausula;
Ações: sequência de instruções executadas atomicamente;
• assume-se que referências para os processos pares ja são conhecidos
(topologia de interconexão pré-estabelecida)
• assume-se a existência de procedimentos auxiliares (operações sobre
filas, pilhas, etc.)
© Markus Endler
2
Exclusão Mútua Distribuída
Usado para sincronizar/coordenar as ações de processos distribuídos
em um sistema de forma descentralizada.
Exemplos:
• garantir o acesso exclusivo a dados/arquivos compartilhados
• garantir a serialização de operações sobre o ambiente externo
(p.ex. Robôs cooperativos)
• garantir a consistência de páginas em uma Memória
compartilhada distribuída (DSM)
Exclusão Mútua Distribuída:
• consiste em garantir o acesso exclusivo de um processo (dentre
vários com requisições concorrentes) a uma seção crítica (recurso/
dado/serviço compartilhado).
 é caso específico de um Problema de Acordo (Agreement)
A principal diferença com relação à Sistemas centralizados (p.ex.:
sincronização em um Sist.Operacional)
 não há o compartilhamento de memória; toda sincronização precisa
ser feita através do envio de mensagens
© Markus Endler
3
Exclusão Mútua Distribuída: Definição do Problema
Sejam N processos Pi, i =1,..,N que interagem através de mensagens e
devem sincronizar os seus acessos a um recurso compartilhado (pode
ser trivialmente generalizado para >1 recurso):
No código de cada Pi:
enter();
// entrada na seção crítica
acesso exclusivo ao recurso compartilhado
exit();
// saida da seção crítica
Para este tipo de problema, é muito difícil lidar com falhas de nós!
 Todos processos precisam chegar a um acordo sobre a ordem de
acesso.
As Premissas mais comuns:
• processos não falham
• comunicação é confiável e
• mensagens não são duplicadas ou corrompidas
• Não há premissas sobre temporização ( sistemas assíncronos)
© Markus Endler
4
Requisitos Essenciais e Opcionais
Segurança (Safety)
<essencial>
• No máximo, um processo executa a cada momento na seção
crítica
Vivacidade (Liveness)
<essencial>
• Todo pedido de entrada e/ou saida da seção crítica é
eventualmente atendido
 com isto, evita-se deadlock e starvation
Atendimento em Ordem:
<opcional>
• Os pedidos para entrar na seção crítica são atendidos em
conformidade com a ordem causal.
 isto garante tratamento justo (Fairness)
© Markus Endler
5
Exclusão Mútua Distribuída
Existem três abordagens:
• Algoritmos baseados em token
• Algorítmos baseados em timestamps
• Algoritmos baseados em votação
© Markus Endler
6
Algoritmos baseados em um token
Ideia geral:
• uma mensagem especial (token) é passada entre os processos
• o processo que possuir o token é aquele com direito de executar na
seção crítica
• ao deixar a seção crítica, o processo detentor do token deve
repassa-lo a um outro processo que esteja esperando entrar na seção
“Tradução” dos principais requisitos essenciais:
• deve existir um único token (Segurança)
• o token precisa ser capaz de chegar a qualquer processo
participando da sincronização (Vivacidade)
Para isto, todos os algoritmos nesta abordagem definem uma
estrutura lógica de comunicação para passagem do token.
As estruturas mais comuns:
• anel
• arvore
© Markus Endler
7
Algoritmo de Token Circulante
Neste caso, a estrutura lógica é um anel conectando todos os
processos participantes da sincronização.
O Modelo de sistema (Premissas):
• topologia de interconexão é fixa (anel), mas # de processos arbitrário
• comunicação é confiável (token não é perdido)
• comunicação é segura (token não é duplicado nem modificado)
• processos não falham
Cada processo que deseja entrar na seção crítica:
• espera a chegada do token do antecessor (vizinho à esq/dir),
• durante a sessão crítica, mantém o token
• após sair da seção crítica passa o token para o próximo
processo (vizinho do qual não recebeu o token)
Processos que não precisam entrar na SC, passam o token adiante
imediatamente
Nota-se que satisfeitas as premissas, este algoritmo garante:
segurança, vivacidade, mas não garante atendimento em ordem
 Algoritmo tem simetria textual, mas o envio do token é um
overhead independente da freqüência de requisições para a SC
© Markus Endler
8
Algoritmo do Token Circulante
• O controle do repasse do token é feito por um processo, que
recebe requisições enter_region e exit_region da aplicação
(naquele nó), e tokens circulantes do processo predecessor
prev no anel.
Appl
Enter_region
prev
Exit_region
Proc i
Estados:
waiting e  waiting
next
Proc(i):
Bool waiting;
when recv(appl,enter_region) &  waiting => waiting:= true;
when recv(prev,token) => {
if (waiting) {
reply(appl,enter_region);
recv(appl,exit_region);
waiting:= false;
}
send(next,token);
© Markus Endler}
9
Algoritmo de Token Circulante
Mas se houver a possibilidade de perda do token, é necessário que os
processos possam detectar isto.
Idéia central do Algoritmo de [Misra83] :
• além do token principal t1 (usado para controlar o acesso à SC),
usar um token circulante complementar t2, de valor oposto a t1 (isto é,
t2 = - t1)
• o token t2 circula no mesmo sentido que token t1
• a cada vez que os tokens se encontram em um processo, seus
valores são atualizados (p.ex. t1++ e t2-- )
• se um processo P receber qualquer um dos tokens com o mesmo
valor mais de uma vez  isto significa que o outro token se perdeu
• o token perdido pode ser reconstruído a partir do token
complementar
• o 1º processo capaz de fazer esta detecção é o processo que
deveria ter recebido o token perdido (este será o responável por
recriar o token perdido)
[Misra83] Misra, J. Detecting Termination of Distributed Computations using Markers,
2nd ACM Conf. On Principles of Distributed Computing, August 83, pp.290-294.
© Markus Endler
10
Algoritmo de Token Circulante
Seja mi uma variável em Pi que guarda o último valor de um token
(t1 ou t2) visto. Atributo t.val armazena o contador associado ao token
when recv (i - 1, t1) {
if (mi == t1.val) {
// t2 foi perdido
mi = ++(t1.val);
new(t2);
// recriando t2
t2.val = - t1.val;
send(i+1, t2}
else mi = t1.val;
se não desejar entrar na seção critica send(i+1, t1);
}
when recv (i -1, t2) {
// análogo ao caso anterior, trocando t2 por t1 e vice-versa
}
when encontro (t1, t2) {
t1.val++;
t2.val--;
}
© Markus Endler
11
Premissas & Problemas
Modelo de sistema do algoritmo de [Misra83] :
• sistema assíncrono
• canais de comunicação são seguros
• processos não falham
• canal de comunicação tem falhas de omissão: perdas de mensagem
são esporádicas (não há partição) e
• não ocorrem falhas simultâneas em mais de um canal (ou seja, no
máximo um token é perdido)
Características:
• Simetria textual do algoritmo
Problemas:
• Overhead: além do token principal, t1, um segundo token sempre
circula
• Para evitar falsa detecção de perda de token, os valores absolutos
assumidos por t1 e t2 precisam ser diferentes de todos os valores mi,
 seus incrementos precisam ser no mínimo mod N+1 (pois tokens
podem se encontrar até N vezes)
© Markus Endler
12
Algoritmo de Token em Árvores
A fim de evitar que um token seja transferido independente de haver
uma requisição (ex.: topologia de anel), impõe-se uma estrutura de
árvore no conjunto de processos (raiz = o atual detentor do token).
Ideia básica do Algoritmo de [Raymond89]:
• o processo que está com o token é a raiz
• cada processo mantém uma referência (curr_dir) do seu vizinho mais
próximo da raiz.
• cada vez que o token é transferido, a árvore é atualizada
• processo que quer entrar na CS envia mensagem REQ para vizinho
indicado por curr_dir
• este vizinho gera outro REQ (em seu nome), que envia para o seu
curr_dir (somente 1ª vez)
• processos intermediários armazenam requisições pendentes em fila
(as cabeças das filas em cada processo intermediário indicam o
caminho do token até o requisitante)
[Raymond89] Raymond, K. A tree-based Algorithm for Distributed Mutual Exclusion,
ACM Transactions on Computer Systems, vol.7, no. 1, 1989.
© Markus Endler
15
Algoritmo de Raymond
Exemplo: ( indica curr_dir)
A
A
REQ B
B
D faz requisição
B
(D)
REQ D
C
D
(D)
C
A
D
C
© Markus Endler
(D)
A
A envia TOKEN
B
B repassa REQ
B
(D)
D
B consulta lista
e repassa TOKEN p/ D
(D)
C
D
16
O Algoritmo de Raymond
Variáveis em cada processo Pi:
bool token
// true, se Pi é detentor do token
bool InCS
// true, se Pi esta na seção crítica
Addr curr_dir
// referência para vizinho “na direção” do detentor do token
AddrQueue reqQ // fila que contém os endereços dos vizinhos com
// requisições pendentes
// obs: operação ‘rem‘ remove e retorna o 1o da fila)
when EnterCS {
if (token ==FALSE) {
if empty(reqQ) send(curr_dir, REQ me);
reqQ.add(me);
receive(any, TOKEN) //wait until token to enter CS
}
InCS = true;
}
when ExitCS {
InCS = false;
if (!empty(reqQ)) {
curr_dir = reqQ.rem();
send(curr_dir, TOKEN);
token = false;
if !empty(reqQ) send( curr_dir, REQ me)
}
}
© Markus Endler
17
Algoritmo de Raymond
MonitorCS {
loop
when recvd (sender, REQ) => {
Cada processo Pi
if (token == TRUE) {
if (InCS) reqQ.add(sender);
executa também uma
else {
thread, MonitorCS,
curr_dir = sender;
send(sender, TOKEN);
para repassar REQs e
token = FALSE;
}
TOKENs
}
else { // token == FALSE
if (empty(reqQ)) send (curr_dir, REQ me);
reqQ.add(sender);
}}
when recvd(sender, TOKEN) => {
curr_dir = reqQ.rem();
if (curr_dir == me) token = TRUE;
else { // repassa token na direção de requisitante
send(curr_dir, TOKEN);
if (!empty(reqQ)) send (curr_dir, REQ me); // se houver >1 na fila
}
}
endloop
}
© Markus Endler
18
Algoritmo de Raymond
Qual é o modelo de sistema?
• Sincronismo?
• Topologia de
interconexão?
• Canais de comunicação?
 Sist. assíncrono
 Grafo (não direcionado)
conexo qualquer
 Seguros e confiáveis
• Nós?
 Sem falha
© Markus Endler
19
Compressão de Caminhos (Path Compression)
O principal problema do algoritmo de Raymond é que o
token precisa ser passado por vários processos
intermediários até chegar ao requisitante (isto se deve à
estrutura logica fixa imposta aos processos por curr_dir)
em vez disto, pode-se fazer com que a árvore tenha
uma forma arbitrária e dinâmica, à medida que
requisições vão sendo repassadas pelos processos.
Isto é realizado no Algoritmo de Li e Hudak (1989), usado
para garantir a coerência de páginas em memória virtual
distribuída.
[Li&Hudak89] K.Li e P.Hudak. Memory Coherence in shared virtual memory systems
ACM Transactions on Computer Systems, 7(4), 1989.
© Markus Endler
20
Compressão de Caminhos (Path Compression)
A ideia basica do Algoritmo de [Li&Hudak89]:
• processo requisitante Pr manda msg (REQ Pr) para seu vizinho indicado
por curr_dir (= endereço do detentor do token ou do último a requisitar)
• quando processo Q recebe (REQ Pr):
• se Q estiver com o token (e não estiver na SC), então passa o token
diretamente para Pr,
• se não estiver com o token, faz um forward de (REQ Pr) para
Q.curr_dir (mas modifica o próprio Q.curr_dir para apontar diretamente
para o Pr)
 portanto, se uma requisição passar por vários intermediários, o novo
curr_dir destes todos irá apontar para o “próximo futuro detentor do token”.
• Enquanto o futuro detentor do token Pr não recebe o token, este pode
receber outras requisições, que serão tratadas quando este sair da SC.
• Obs: Junto com o token vai a lista de requisições pendentes
• Ao receber o token, um nó faz um merge de sua lista com a lista vinda
com o token.
© Markus Endler
21
Compressão de Caminhos (Path Compression)
Exemplo: A faz requisição, mas surgem outras requisições antes de A
receber token.
D
REQ E
D
(A,E)
D
(A,E)
()
REQ A
E
C
E
C
E
C
TOKEN, E
REQ A
B
REQ A
A
• A e E fazem requisição
© Markus Endler
B
B
REQ B
A
(B)
A
(B)  (E,B)
• B e C trocaram curr_dir=A D envia o token com lista de
• B envia REQ para A
pendentes, atualizadas em A
22
Compressão de Caminhos (Path Compression)
Problema: à medida que o número de processos requisitantes cresce, a
lista enviada com o token também aumenta
A complexidade de espaço (tamanho de mensagem) é O(N), e portanto o
algoritmo não é escalável.
Solução: manter uma lista encadeada entre os processos requisitantes
(usando um ponteiro adicional next)
Seja Pu o processo mais recente a ter requisitado o token:
• um novo requisitante Pn seta next=NIL e envia o seu pedido para
curr_dir
• pedido é repassado pelos processos intermediários ao longo do
caminho definido por curr_dir na direção de Pu
• em cada intermediário, curr_dir é atualizado para Pn
• ao chegar em Pu, este seta curr_dir = Pn e next = Pn
• quando Pu sair da CS, irá saber para onde mandar o token (next)
© Markus Endler
23
Exemplo Compressão de Caminhos
B
C

B
C
A
D

REQ D
A
REQ D
D

Seja C o último que requisitou token
D seta next= e envia REQ D
B
REQ D
A
C
D

A repassa REQ D e troca curr_dir
B
C
A
D


B repassa REQ D e troca curr_dir

C (ultimo requisitante) seta next e curr_dir
Legenda: processos amarelos estão requisitando SC
curr_dir
© Markus Endler
next
24
Compressão de Caminhos (Path Compression)
Variáveis em cada processo Pi:
bool token
// TRUE sse Pi é detentor do token
bool InCS
// TRUE sse Pi esta na seção crítica
IsRequesting
// TRUE sse Pi está requisitando a SC
curr_dir
// dica atual sobre o processo no final da fila de espera
next
// o próximo processo a receber o token, ou NIL, Pi é o último
when EnterCS {
IsRequesting = TRUE;
if (!token) {
// não possui o token
send(curr_dir, REQ me);
curr_dir = me; next = NIL;
wait until (token==TRUE) to enter CS
}
InCS = true;
}
when ExitCS {
InCS = FALSE; IsRequesting = FALSE;
if next != NIL {
send(next, TOKEN);
// envia o token para processo *next
token = false;
next = NIL;
}
}
© Markus Endler
25
Compressão de Caminhos (Path Compression)
MonitorCS {
loop
when recv (sender, REQ) => {
if (IsRequesting == TRUE )
// Pi requisitou o token
if (next ==NIL) next = sender
else send(curr_dir, REQ, sender);
elseif (token == TRUE) {
// Pi não requisitou o token
token = FALSE;
send(sender,TOKEN, sender)
}
else {
// Pi não está com token nem requisitou
send (curr_dir, REQ sender);
}
curr_dir = sender;
}
when receive(sender, TOKEN) => {
token = TRUE
}
endloop
}
© Markus Endler
26
Algoritmo de Li & Hudack
Qual é o modelo de sistema?
• Sincronismo?
• Topologia de
interconexão?
• Canais de comunicação?
• Nós?
 Sist. assíncrono
 Grafo (não direcionado)
completo
 Seguros e confiáveis, e
FIFO
 Sem falha, e
encaminhamento FIFO
das mensagens
Qual é o problema se encaminhamento não for FIFO?
Dica: considere que outro nó E (ligado a D) requisitou a seção crítica logo
depois que D enviou o seu req D, mas que req E “utrapassa” req D ao
longo do itinerário A-B-C. (alguns terão curr_dir para D, outros para E).
© Markus Endler
27
Algoritmos baseados em Tokens
Principais Diferenças das três categorias:
• Token Circulante:
 ordem de repasse previamente definida
 atendimento independente da ordem de requisição
 existe um overhead intrínseco independente do número de
requisições
 custo máximo: N-1 mensagens, custo médio N/2 mensagens
• Estrutura fixa de Árvore:
 caminho de repasse definido pela árvore e pela direção do detentor
do token
 atendimento na ordem de requisição (a menos de “atrasos” na
transmissão de req)
 custo: número de saltos por requisição: O(log N) mensagens
 e tamanho da mensagem O(N)
• Estrutura dinâmica de Árvore:
 caminho de repasse definido dinamicamente
 atendimento na ordem de requisição (definida pelo ponteiro next)
 custo: número de saltos por requisição: O(log N) mensagens e
 tamanho da mensagem O(1)
© Markus Endler
28
Algoritmos baseados em Timestamp
Sejam N processos em uma topologia de grafo completo:
Idéia Central:
• um processo só entra na sessão crítica se obtém o
consentimento de todos os demais processos (consenso)
• usa-se broadcast  todos os processos participantes têm
uma visão consistente das requisições
• usa-se o relógio lógico de Lamport para estabelecer uma
ordem total dos pedidos
• processo só envia resposta (OK) para uma requisição
recebida se esta é anterior a requisição de sua própria
aplicação (se houver)
• então, se dois (ou >2) solicitarem ao mesmo tempo, só
um deles receberá a OK de N-1 processos
© Markus Endler
29
Algoritmos baseados em Timestamp
Apresentaremos aqui o Algoritmo de [Ricart & Agrawala81], que usa o
conceito de Relógios Lógico de L. Lamport
Funcionamento básico do Algoritmo:
• processo requisitante Pr difunde um (REQ, ts) para todos os demais
processos Pi
• se o processo Pi tem um pedido pendente anterior ao ts recebido, (ou
está na SC) então adia a resposta, senão retorna um REPLY para Pr
• quando Pr recebeu REPLY de todos os Pi´s, sabe-se que não existem
outras requisições anteriores, e Pr pode entrar na SC
• ao sair da SC, Pr envia todos os REPLYs pendentes (e.g. de
requisições não respondidas)
Algoritmo garante:
• acesso exclusivo à Sessão Crítica
• acesso justo à SC (segundo a ordem total estabelecida)
© Markus Endler
30
Algoritmo de Ricart & Agrawala
Replies_pending=1
P1
Rep
Req, TS
Req, TS
P4
Req, TS
Rep
P2
Replydeferred[1]=T
P3
• se P4 está na sessão crítica (ou fez requisição anterior a P1), P4 deixa
de responder à requisição de P1
• P1 saberá que pode entrar na SC assim que tiver recebido os replies de
todos os demais processos
© Markus Endler
31
Algoritmo de Ricart & Agrawala
O Modelo de sistema:
• sincronismo
• conjunto/topologia de interconexão?
• canais de comunicação
• nós
• sistema assíncrono
• grupo fixo de processos, grafo completo
• comunicação é confiável e segura
• processos sem falha
Propriedades do Algoritmo:
• simplicidade e simetria textual
• para entrar na SC, precisa-se trocar 2*(N-1) mensagens
• como todas as requisições e liberações de SC são difundidas entre
todos os processos, estes compartilham a mesma visão da lista de
prioridades
• A confiabilidade da comunicação é essencial. Por que?
• O uso do relógico lógico é fundamental: Por que?
© Markus Endler
32
O Algoritmo de Ricart & Agrawala
Variáveis do processo Pi: (assumindo M processos)
TS
current_time
// current Lamport time
TS
my_timestamp
// timestamp do próprio pedido
int
replies_pending // contador dos replies que precisa receber
bool
is_requesting
// TRUE  Pi está requisitando entrada na SC
bool
reply_deferred[M] // para cada processo, indica se reply foi adiado
Enter_CS() {
my_timestamp = current_time
is_requesting = TRUE
replies_pending = N -1
send (all, REQ, my_timestamp)
wait until (reply_pending == 0)
}
// difusão da requisição
Exit_CS() {
is_requesting = FALSE
for (j=1; j <= N, j++)
if (reply_deferred[j] == TRUE) {
send(j,REPLY, current_time)
reply_deferred[j]=FALSE
}
}
© Markus Endler
33
O Algoritmo de Ricart & Agrawala
Precisa-se ter uma thread independente para tratar do recebimento de
mensagens dos demais processos (Monitor_CS), e que compartilha variáveis
com Enter_SC() e Exit_SC().
Monitor_CS() {
// thread executando em todo processo Pi
loop
when recv(j, REQ, req_TS) => {
current_time = max(current_time, req_TS) + 1
if (not_requesting || my_timestamp > req_TS)
send(j, REPLY, current_time)
else reply_deferred[j] = TRUE
}
when recv(j, REPLY, rep_TS) => {
replies_pending = replies_pending -1
current_time = max(current_time, rep_TS) +1
}
endloop
}
© Markus Endler
34
Trabalho Prático (até 4/05)
1.
Implementar em Neko:
a)
b)
Algoritmo de Tokens circulantes complementares
Algoritmo de Ricart and Agrawala com tolerância a mensagens
REQ
Simular os dois algoritmos para N = {5,10,15} processos e
dois diferentes padrões de solicitação de acesso na
Sessão Crítica (alta e baixa freqência).
Medir e comparar:
•
o tempo médio de resposta das solcitações
(temporização do Neko) e
•
o número médio de mensagens por solicitação.
Escrever um relatório mostrando e discutindo os dados
coletados.
© Markus Endler
35
Algoritmos baseados em Votação
Ideia Central:
• analogia a uma votação política, em que geralmente
um pequeno grupo de eleitores (“os indecisos”)
decide a eleição
• em vez de consultar todos os demais processos, o
requisitante da SC consulta apenas um sub-grupo de
processos, e
• caso obtenha todos as confirmações, pode entrar na
SC, senão espera
• principal vantagem: reduz o número de mensagens
Apresentaremos o algotitmo proposto por [Maekawa85]
[Maekawa85] A N Algorithm for Mutual Exclusion in Decentralized Systems, ACM
Transactions on Computer Systems, Vol 3, No. 2.
© Markus Endler
36
Algoritmos baseados em Votação
Seja {P1, P2, …, PM } o conjunto de processos
O conceito de distrito (coterie):
• A cada processo P está associado um distrito (=
subconjunto de processos) SP
• Tal que: Pi, Pj,  k,m, tal que Pi  Sk, Pj Sm e
Sk  Sm  
• O conjunto de distritos Si deve ser escolhido assim:
(sejam i,j = 1,..,M )
– Pi  Si
// o processo pertence ao seu distrito
– Si  Sj  
// há pelo menos 1 processo comum
em 2 distritos
E se possível respeitando:
– Si  = k
// distritos devem ter número igual de
elementos
– Cada Pj pertence a D distritos Si
© Markus Endler
37
Exemplo
P1
P3
• Cada Pi pertence a dois distritos
• Cada distrito tem três elementos
• Requisito essencial:
Para Si  Sj  
© Markus Endler
P2
P4
S1 = {p1,p2, p3}
S2 = {p1, p2, p4}
S3 = {p1, p3, p4}
S4 = {p2, p3, p4}
 D =2
k=3
38
Exemplo
• Considere N = 7 processos
• Como voce construiria os distritos?
P1
P2
P3
P4
P7
P6
P5
Mas será que essa é a melhor escolha
para os distritos? Que minimiza o K?
© Markus Endler
• K=3a5
• D=1a2
39
Algoritmos baseados em Votação
Maekawa mostrou que a solução ótima para N distritos
(que minimiza k e permite garantir a exclusão mútua) é
dada por k  M e D=k
Argumentação:
Cada distrito contém k processos que por sua vez podem
pertencer a D -1 outros distritos. Logo o número maximo N de
distritos que podem ser construídos é
N = (D-1) k + 1. Dados N, k e D, como cada processo pode estar
em D distritos e cada distrito tem k elementos, o número
máximo de distritos é DN/k. Se queremos ter exatamente N
distritos, então N = DN/k  D = k.
Ou seja N = (k - 1) k + 1, ou k  N
© Markus Endler
40
Algoritmos baseados em Votação
No caso geral (para qualquer N) não é trivial achar os distritos Si
ótimos. Uma aproximação é usar k = O(N): colocar os N processos
em uma matriz (N x N) e usar como Si = os processos da linha e
da coluna que contenham Pi . (Neste caso k  2 N)
1
2
3
4
5
6
7
8
9
S4
Note:
S4  = 5
P4 {S4,S1,S7,S5,S6}
D=5
O algoritmo naïve:
• para entrar na SC, um processo Pi envia REQ para todos em Si
• cada processo em Si responde com YES, caso já não tenha dado o
seu voto para outro pedido
• ao sair da SC, Pi envia RELEASE para todos em Si
Problema! Possibilidade de deadlock, pois não há garantia de que
todos elementos em Si irão receber todos os REQs na
mesma ordem
© Markus Endler
41
Situação de Deadlock
•
•
•
•
P2 recebe REQ1, seguida de REQ4 e dá voto a P1
P3 recebe REQ4, seguida de REQ1e dá voto a P4
P1 fica aquardando OK de P3
P4 fica aguardando OK de P2
P1
P2
REQ1
P3
P4
REQ4
• Precisa-se de:
– uma forma para decidir qual requisição é a anterior
– Permitir que processos re-atribuam os seus votos
© Markus Endler
42
Algoritmos baseados em Votação
Solução do problema [Sanders87+96] usando Relógios Lógicos:
• junto com cada REQ envia-se o timestamp de relógio lógico
(Lamport)
• se um P  Si  Sj ja deu o seu voto para REQi e depois recebe a
REQj com um timestamp menor, P vai enviar msg INQuire para Pi
para anular o seu voto
• Ao receber INQ* e se Pi ainda não tiver obtido todos os votos de
seu distrito Si, então Pi “devolve os votos”, adiando a sua entrada
na SC
Os relógios lógicos impõem uma ordem total aos pedidos, evitando
deadlock, pois
• ou a requisição com menor timestamp recebe todos os votos (talvez
depois de reclamar um voto),
• ou (se INQ chegar atrasado), o requisitante que já obteve todos os
votos entra na SC
(*) INQ vem com o timestamp da requisição cujo voto está sendo
reclamado
[Sanders87] The information structure of Distributed Mutual Exclusion Algorithms, ACM
Trans. On Computer Systems, 5(3), 1987.
[Sanders96] Data Refinement of mixed specification: A Generalization of UNITY, Dept. of
CISE,
University of Florida, Tech. Report 96-010
© Markus
Endler
43
Algoritmo de Sanders
Tipos de Mensagem:
• REQ + TS
// pedido de entrada na SC
• RELEASE
// notificação de saida da SC
• RELINQUISH // devolução dos votos
• YES
// voto para entrada na SC
• INQ + TS
// solicitação de devolução do voto
Variáveis em cada processo Pi:
Si
// o distrito associado a Pi
InCS
// TRUE se Pi está na sessão crítica
curr_TS
// o relógio lógico corrente
my_TS
// timestamp do próprio pedido de entrada na SC
yes_votes
// # de processos que responderam YES
has_voted
// TRUE se Pi ja deu seu voto para algum candidato
cand
// ID do candidato para o qual foi dado o voto
cand_TS
// timestamp do pedido do candidato cand
inquired
// TRUE se Pi tentou anular o seu voto
deferredQ
// fila de pedidos pendentes, com as seguintes operações
add({P, TS}),
// adiciona o par {processo, TS} da requisição
rem_min()
// remove o par {processo,TS} tq. TS é o menor valor
notempty()
// retorna TRUE se a fila não está vazia
© Markus Endler
44
Algoritmo de Sanders
Enter_CS {
my_TS = curr_TS
forall r in Si send(r, REQ, my_TS)
// multicast to coterie
while (yes_votes < Si ) {
when recvd(sender,YES) => yes_votes := yes_votes+1
when recvd(sender, INQ, inq_TS) =>
if (my_TS == inq_TS) {
send (sender, RELINQUISH);
yes_votes := yes_votes-1
}
}
InCS = TRUE
}
Exit_CS {
InCS = FALSE;
forall r in Si send(r,REL)
}
© Markus Endler
45
Algoritmo de Sanders
Monitor_CS {
loop
when recvd(sender, REQ, req_TS) => {
if (NOT has_voted) {
send(sender,YES)
cand = sender;
cand_TS = req_TS;
has_voted = TRUE }
else {
deferredQ.add({sender, req_TS})
if (req_TS < cand_TS) && (NOT inquired) {
send(cand, INQ, cand_TS); // pede anulação do voto
inquired = TRUE }
}
}
when recvd(sender,RELINQUISH) => {
deferredQ.add({cand, cand_TS})
{s,r_TS} = deferredQ.remove_min(); // resgata requisição anterior
send(s, YES);
cand = s;
cand_TS = r_TS;
inquired = FALSE;
}
when recvd(sender,RELEASE) => {
if (deferredQ.notempty()) {
{s, r_TS} = deferredQ.remove_min();
send(s, YES);
cand = s;
cand_TS = r_TS; }
else has_voted = FALSE;
inquired = FALSE
}
endloop
} Endler
© Markus
46
Exemplo: Algoritmo de Sanders
Sejam requisições REQA e REQB, com REQA_TS < REQB_TS
A
A
REQA, 4
a
b
c
d
REQB, 5
B
Deferred = (A,4)
a
Deferred = (A,4)
b
INQ
c
d
YES
INQ
B
Situação A: Apesar da requisição de A ser anterior a de B,
B entra na SC (e ignora todos os pedidos de INQ)
porque já tem os votos de {b,c, d}
© Markus Endler
47
Exemplo: Algoritmo de Sanders
Ainda REQA e REQB, com REQA_TS < REQB_TS
A
A
REQA, 4
a
b
c
d
YES
a
YES
b
c
d
Deferred = (B,5)
YES INQ
REQB, 5
B
RELINQUISH
B
SituaçãoB: Como B ainda não entrou na SC, o INQ de d é
tratado, B devolve o voto de d, que envia o seu voto para A,
e A entra na SC.
© Markus Endler
48
O Algoritmo de Sanders
A
B
Como nem A nem B já receberam todos os YES de
seus distritos, um dos processos na intersecção irá
pedir de volta os seu voto quando conhecer o pedido
do outro processo. Pois PIDA < PIDB
© Markus Endler
49
Algoritmo de Sanders
Premissas:
• sistema assíncrono
• comunicação é confiável e entrega é FIFO
• comunicação é segura
• requer uma associação prévia entre distritos e
processos (existem outros algoritmos que permitem
uma associação dinâmica)
• um processo pode falhar (temporariamente), contanto
que não esteja envolvido em um processo de votação
© Markus Endler
50
Corretude do Algoritmo
Argumentação informal de que o algoritmo garante a exclusão mútua
(safety):
1. Cada processo a cada momento dá o seu voto para no máximo um
processo requisitante: mesmo se P tiver mudado o seu voto, isto
só acontece após ter recebido RELEASE ou RELINQUISH, que
pressupõem que o processo que tinha o voto de P abriu mão do
voto.
2. Dado que:
•
Si  Sj para i,j;
• a entrada de um P na SC só ocorre após receber YES de todos
os processos em seu distrito;
• usando o fato no item 1, e que
• P só libera os votos obtidos ao sair da SC
tem-se que não é possível que dois ou mais processos entrem (e
permaneçam) simultaneamente na SC.
© Markus Endler
51
Corretude do Algoritmo
Argumentação informal sobre a garantia de vivacidade (liveness),
ausência de deadlocks
Suponha (por absurdo) que:
•
em algum momento exista um (ou mais) processo bloqueado por
ainda não ter obtido todos os votos de seu distrito e
•
que ao longo de qualquer possível execução a partir deste estado,
(um estado causalmente dependente) algum outro processo
também bloqueie tentando entrar na SC (ou seja, o sistema esteja
em deadlock).
Seja A processo bloqueado requisitando a SC com o menor timestamp. Este processo está esperando o voto de um processo P de
seu distrito, que deu o seu voto a um processo, p.ex. do qual
recebeu a mensagem REQ primeiro. Mas como o REQA.TS <
REQB.TS, P deve ter enviado um INQ para B. A única razão para B
não responder ao INQ é se B já obteve todos os votos e está na
SC.
 Mas isto contradiz a nossa hipótese de que nenhum está na
© Markus Endler
SC.
52