ARA7132-UNIDADE-4

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
UNIDADE 4
Concorrência e Sincronização
Disciplina: Computação Distribuída (ARA7132)
Prof. Alexandre L. Gonçalves
E-mail: alexandre.goncalves@ararangua.ufsc.br
*
*
*
Sumário
Sincronização de Relógios
Deadlock Distribuído
Algoritmos de Eleição
*
*
*
Sincronização de Relógios
Definição
Processos em um sistema distribuído não compartilham memória e não compartilham relógio (clock).
As informações relevantes estão espalhadas entre diversas máquinas.
Os processos tomam decisões baseados exclusivamente nas informações disponíveis no local onde eles estão executando.
Deve ser evitada a qualquer custo a existência de um único ponto de falha.
Não existe nenhuma fonte precisa de tempo global (escorregamento de clock).
*
*
*
Sincronização de Relógios
Definição
Relação Acontecimento-Anterioridade (Happened Before)
Notação referente a ordenação parcial dos eventos em um sistema distribuído.
Se A e B são eventos do mesmo processo, e A foi executado antes de B, então:
A  B
Se A é um evento de envio de uma mensagem por um processo, e B é um evento de recepção da mensagem por outro processos, então:
A  B
Se A  B e B  C, então:
A  C
*
*
*
Sincronização de Relógios
Definição
Relação Acontecimento-Anterioridade (Happened Before)
Se dois eventos não estão relacionados com a notação , então esses dois eventos são executados concorrentemente.
*
*
*
Sincronização de Relógios
Definição
Relação Acontecimento-Anterioridade (Happened Before)
Exemplo:
p1  q2,
r0  q4,
q3  r4,
p1  q4, (p1  q2 e q2  q4)
Alguns eventos concorrentes:
q0 e p2,
r0 e q3,
r0 e p3,
q3 e p3,
p4
p3
p2
p1
p0
q4
q3
q2
q1
q0
r4
r3
r2
r1
r0
p
q
r
*
*
*
Sincronização de Relógios
Para determinar se um evento A acontece antes de um evento B, é necessário o uso de um tempo comum ou um conjunto de relógios perfeitamente sincronizados.
A cada evento do sistema é associado um timestamp.
Para cada par de eventos A  B, então o timestamp de A é menor que o timestamp de B.
*
*
*
Sincronização de Relógios
Relógios Lógicos
Algoritmo de Lamport (1978)
O importante é a ordem na qual os eventos venham a ocorrer.
Se dois processos não interagem, não é necessário que seus clocks estejam sincronizados.
Se A  B, então:
C(A) < C(B)
O tempo medido pelo clock C, deve ser sempre crescente, nunca decrescente.
Correções são feitas adicionando um valor positivo ao valor atual do clock.
Se o processo P recebeu uma mensagem (evento B), com timestamp t, e LC(B)  t, então P deve avançar seu clock, tal que LC(B) = t + 1.
*
*
*
Sincronização de Relógios
Relógios Lógicos
Algoritmo de Lamport (1978)
Exemplo 1 (sem sincronização de relógio):
0
6
12
18
24
30
36
42
48
54
60
0
8
16
24
32
40
48
56
64
72
80
0
10
20
30
40
50
60
70
80
90
100
P
Q
R
A
D
B
C
*
*
*
Sincronização de Relógios
Relógios Lógicos
Algoritmo de Lamport (1978)
Exemplo 2 (com sincronização de relógio):
0
6
12
18
24
30
36
42
48
70
76
0
8
16
24
32
40
48
61
69
77
85
0
10
20
30
40
50
60
70
80
90
100
P
Q
R
A
D
B
C
*
*
*
Sincronização de Relógios
Relógios Lógicos
Vetores de Relógio
Desenvolvido para contornar as dificuldades com os relógios lógicos de Lamport.
Se C(e) < C(e´) não implica que e  e´
Um vetor de relógio é um conjunto de valores de N inteiros.
N é o número de processos que fazem parte do sistema.
Vi[j], j = 1, 2, 3, ...N
Vi[i] = número de eventos que ocorreu em pi.
Vi[j] (j  i) = número de eventos produzidos em pj que tem potencialmente afetado pi.
*
*
*
Sincronização de Relógios
Relógios Lógicos
Vetores de Relógio
Regras para atualização dos vetores:
VC1: inicialmente Vi[j] = 0, para i, j = 1, 2, ..., N.
VC2: quando pi gera um evento, um timestamp é associado ao mesmo e o vetor é atualizado Vi[i] = Vi[i] + 1.
VC3: pi inclui o valor t = Vi, em cada mensagem ou evento interno que produz.
VC4: o vetor de pi é atualizado quando uma mensagem é recebida com timestamp t: Vi[j] = MAX(Vi[j] = t[j])
*
*
*
Sincronização de Relógios
Relógios Lógicos
Vetores de Relógio
Exemplo:
p1
p2
p3
(1,0,0)
a
b
(2,0,0)
(2,1,0)
(2,2,0)
c
d
Tempo Físico
e
f
(2,2,2)
(0,0,1)
m1
m2
*
*
*
Sincronização de Relógios
Relógios Lógicos
Vetores de Relógio
Exemplo:
A figura anterior demonstra que:
a  f, logo V(a) < V(f)
e e c são concorrentes (e  c)
*
*
*
Sincronização de Relógios
Relógios Físicos
Necessidade de marcar os eventos utilizando o tempo real (relógio físico).
Múltiplos relógios físicos diferem em relação ao tempo real.
Características diferentes dos cristais usados na implementação dos relógios físicos. (drift rate)
Tempo Universal Coordenado (UTC), baseado no TAI (Tempo Atômico Internacional) e sincronizado com o tempo astronômico.
O tempo UTC está disponível via rede de satélites GPS.
*
*
*
Sincronização de Relógios
Relógios Físicos
Algoritmo de Cristian
Sincronizar todas as máquina do sistema com um servidor de tempo.
Periodicamente, cada máquina envia uma mensagem para o servidor de tempo, solicitando o tempo corrente.
O servidor responde o mais rápido possível com uma mensagem contendo o tempo corrente Cutc.
O tempo de propagação da mensagem deve ser levado em consideração para o ajuste do relógio físico do cliente (t1 – t0)/2.
*
*
*
Sincronização de Relógios
Relógios Físicos
Algoritmo de Cristian
Exemplo:
Cliente
Servidor
t0
t1
Tempo de tratamento da interrupção
Cutc
Requisição
*
*
*
Sincronização de Relógios
Relógios Físicos
Algoritmo de Berkeley
O servidor de tempo é uma entidade ativa; consulta periodicamente as máquinas do sistema a fim de saber o tempo corrente em cada uma delas.
Baseado nas respostas dos clientes o servidor calcula o tempo médio, e informa a todas as outras máquinas para avançar ou atrasar seus clocks.
*
*
*
Sincronização de Relógios
Relógios Físicos
Algoritmo de Berkeley
Exemplo:
Servidor
de Tempo
3:00
Máquina A
3:25
Máquina B
2:50
3:00
3:00
Servidor
de Tempo
3:00
Máquina A
3:25
Máquina B
2:50
-10
+25
Servidor
de Tempo
3:05
Máquina A
3:05
Máquina B
3:05
+15
-20
*
*
*
Sincronização de Relógios
Relógios Físicos
Network Time Protocol (NTP)
Provê uma arquitetura para um serviço de tempo baseada na Internet.
Os clientes através da Internet se sincronizam o mais preciso possível ao UTC (Tempo Universal Coordenado).
NTP emprega técnicas estatísticas para análise da qualidade dos dados de tempo de diferentes servidores.
O NTP é fornecido por uma rede de servidores localizados na Internet;
Os servidores são conectados em uma hierarquia lógica chamada sub-rede de sincronização, em que os níveis são chamados de strata.
NTP.br: http://ntp.br/
*
*
*
Sincronização de Relógios
Relógios Físicos
Network Time Protocol (NTP)
Exemplo:
1
2
3
3
2
3
Obs: as setas indicam controle de sincronização, os números fornecem o stratum.
*
*
*
Deadlock Distribuído
Assim como ocorre em sistemas centralizados, deadlocks também podem ocorrer em sistema distribuídos.
Estratégias para tratar deadlocks:
Algoritmo do avestruz
Detecção
Prevenção
Evitar a ocorrência de deadlocks com uma política de alocação de recursos bastante cuidadosa.
*
*
*
Deadlock Distribuído
Algoritmo do Avestruz
Assume que deadlocks são raros e que uma estratégia de tratamento é mais onerosa do que a sua ocorrência:
ENFIA A CABEÇA NA AREIA E FINGE QUE NÃO EXISTE O DEADLOCK.
Utiliza uma premissa semelhante ao usada nos bloqueios por concorrência otimista.
*
*
*
Deadlock Distribuído
Detecção Centralizada do Deadlock
Utilização de um algoritmo centralizado para detecção de deadlocks em sistemas distribuídos.
Cada máquina possui um grafo de alocação de recursos para seus próprios processos.
Um coordenador central mantêm um grafo de alocação de recursos para todo o sistema.
Quando o coordenador detecta um ciclo, ele mata um dos processos para evitar o deadlock.
O coordenador deve ser informado sobre pedidos de alocação e liberação de recursos por parte dos processos.
Problemas com o falso deadlock.
*
*
*
Deadlock Distribuído
Detecção Centralizada do Deadlock
Exemplo:
Máquina A
S
P1
P2
R
Máquina B
S
P3
T
Coordenador
Coordenador
P1
P2
R
S
P3
T
P1
P2
R
S
P3
T
Situação de falso deadlock
*
*
*
Deadlock Distribuído
Detecção Distribuída do Deadlock (Chandy – Misra – Haas)
Todas as máquinas que compõem o sistema compartilham a tarefa de detectar deadlocks.
Nessa solução é permitido que os processos requisitem vários recursos.
O algoritmo de Chandy-Misra-Haas é executado quando um processo deve esperar por algum recurso.
Envio de uma mensagem especial de sondagem para processos detentores de recursos.
Este algoritmo vale tanto para recursos locais quanto para recursos remotos.
A mensagem de sondagem é composta de três parâmetros:
O processo que iniciou a sondagem,
O processo que enviou a mensagem, e
O processo para o qual ela está sendo enviada.
*
*
*
Deadlock Distribuído
Detecção Distribuída do Deadlock (Chandy – Misra – Haas)
O receptor da mensagem de sondagem, verifica se ele próprio está aguardando por recursos de algum processo, se estiver atualiza a mensagem, alterando o segundo e o terceiro campo e em seguida envia a mensagem para o processo responsável pelo seu bloqueio.
Se uma determinada mensagem, retornar ao processo que a transmitiu, fica clara a existência de um deadlock.
A situação de deadlock pode ser desfeita forçando o processo que iniciou a sondagem a cometer suicídio.
*
*
*
Deadlock Distribuído
Detecção Distribuída do Deadlock (Chandy – Misra – Haas)
Exemplo:
P1
P2
P3
P4
P6
P5
P7
P8
P9
Máquina A
Máquina B
Máquina C
(1,3,4)
(1,9,1)
(1,5,7)
(1,6,8)
*
*
*
Deadlock Distribuído
Prevenção de Deadlocks Distribuídos
Projetar o sistema de forma cuidadosa, de maneira que a ocorrência de deadlocks seja estruturalmente impossível.
Uso de técnicas de marcação de tempo global (timestamp).
Um processo que possui um timestamp menor, possui prioridade na alocação de recursos.
*
*
*
Deadlock Distribuído
Prevenção de Deadlocks Distribuídos
Exemplo 1: (Algoritmo espere-e-morra (wait-die))
Processo Velho
10
Processo Jovem
20
Precisa do Recurso
Detém o Recurso
Espera
*
*
*
Deadlock Distribuído
Prevenção de Deadlocks Distribuídos
Exemplo 2: (Algoritmo espere-e-morra (wait-die))
Processo Jovem
20
Processo Velho
10
Precisa do Recurso
Detém o Recurso
Morre
*
*
*
Deadlock Distribuído
Prevenção de Deadlocks Distribuídos
Exemplo 1: (Algoritmo fere e espera (wound-wait))
Processo Velho
10
Processo Jovem
20
Precisa do Recurso
Detém o Recurso
Retira o recurso (Preempção)
Ferido
*
*
*
Deadlock Distribuído
Prevenção de Deadlocks Distribuídos
Exemplo 2: (Algoritmo fere e espera (wound-wait))
Processo Jovem
20
Processo Velho
10
Precisa do Recurso
Detém o Recurso
Espera
*
*
*
Algoritmos de Eleição
Os algoritmos distribuídos, em grande parte, precisam de um processo para agir como coordenador, seqüenciador, inicializador e etc.
É necessário alguma forma de eleger um processo para atuar como coordenador.
Em geral algoritmos eletivos tendem a designar como coordenador o processo com o número de identificação mais alto.
O objetivo de um algoritmo eletivo é assegurar que, quando for iniciada uma eleição, ela termine com todos os processos do sistema sabendo quem é o novo coordenador.
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Quando um determinado processo nota que o coordenador não está respondendo as solicitações, ele inicia um eleição.
Um processo p, convoca uma eleição da seguinte forma:
P envia uma mensagem indicativa de eleição a todos os processos com números de identificação superiores ao seu.
Se nenhum processo responder, p ganha a eleição, tornando-se o coordenador.
Se algum dos processos consultados responder, ele passa a controlar a eleição.
O trabalho de p termina.
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
Atual coordenador
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
Atual coordenador
Processo P7 falha
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P4 inicia a eleição
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P5 e P6 confirmam a participação
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P5 e P6 iniciam uma nova eleição
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P6 confirma a participação para P5
*
*
*
Algoritmos de Eleição
Algoritmo do Ditador (bully algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P6 informa todos os outros processos que ele é o novo coordenador
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Os processos estão, física ou logicamente, ordenados, de forma que cada processo sabe quem é o seu sucessor.
Quando um processo p desconfiar que o coordenador está inativo, ele monta uma mensagem de convocação de eleição, contendo seu próprio número e a envia a seu sucessor.
Se o sucessor de p estiver inativo, p envia a mensagem para o próximo membro do anel, até localizar um processo ativo.
Eventualmente a mensagem retorna ao processo que a enviou pela primeira vez.
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Ao receber uma mensagem onde consta seu próprio número de identificação, o processo receptor envia uma mensagem a todos os outros processos informando quem é o novo coordenador.
O novo coordenador é o processo da lista de identificações, que tiver o maior número.
Quando a mensagem termina de circular pelo anel, ela é retirada da rede e todos os processos voltam ao trabalho.
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
Atual coordenador
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
Processo P8 falha
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
Processo P3 inicia a eleição
(3)
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
Processo P3 inicia a eleição
(3)
(3,4)
(3,4,5)
(3,4,5,6)
(3,4,5,6,7)
(3,4,5,6,7)
(3,4,5,6,7,1)
(3,4,5,6,7,1,2)
*
*
*
Algoritmos de Eleição
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
Processo P3 emite uma mensagem informando o novo coordenador
(3,4,5,6,7,1,2)
*
*
*
Algoritmo em Anel (ring algorithm)
Exemplo:
P1
P2
P3
P4
P5
P6
P7
P8
P7 é o novo coordenador
Algoritmos de Eleição