PDF de programación - Sincronización en sistemas distribuidos - Tema 4 - Sistemas distribuidos

Tema%4.(
Sistemas(distribuidos(
Sincronización(en(sistemas(distribuidos(

Marisol(García(Valls(

Departamento(de(Ingeniería(Telemá8ca(

Universidad(Carlos(III(de(Madrid(

[email protected]

(



Arquitectura(de(sistemas(II(

(

Grado(en(Ingeniería(Telemá8ca(
Curso:(3º,(cuatrimestre:(2º



Índice(

Introducción(a(la(sincronización(en(sistemas(distribuidos.(

• 
•  Sincronización(mediante(relojes.(

–  Relojes(lógicos(y(relojes(Qsicos.(
–  Algoritmos(de(sincronización(de(relojes(lógicos(
–  Algoritmos(de(sincronización(de(relojes(Qsicos.(
–  Aplicaciones(de(sincronización(de(relojes(

•  Exclusión(mutua(en(sistemas(distribuidos.(
–  Algoritmos(centralizados,(distribuidos(y(en(anillo.(

•  Algoritmos(de(elección.(
•  Transacciones(atómicas.(

(

©2017((Marisol(García(Valls((

(2(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

1

BibliograQa(

(((((((A.S.(Tanenbaum.(Distributed*Opera.ng*Systems.(Pearson.(2009((
(((((Capítulo%3.%
%

%%%%%%%%%%
%%%%%%%%A.%S.%Tanenbaum,%M.%Van%Steen.%Distributed%systems:%Principles%and%paradigms.%
%%%%%%%%(Anteriormente%editado%por%Pearson%EducaCon.)%
%%%%%%%%Publicado%pro%M.%Van%Steen.%2016.%
%
%%%%%%%Capítulo%6.%

©2017((Marisol(García(Valls((

(3(

Arquitectura(de(sistemas(II(T(GIT(

Comunicación(y(sincronización(distribuida(

La(comunicación(entre(procesos(puede(realizarse(mediante(protocolos(de(capas,(
paso(de(mensajes((con(protoc.(pe8ciónTrespuesta),(RPC(y(comunicación(de(grupos.(

Los(procesos(no(sólo(comunican(sino(que(deben(cooperar(y(sincronizarse.(

• 

• 

•  ¿Cómo(se(implementan(las(secciones%críCcas%en%un%sistema%distribuido?(¿Cómo(se(

asignan(los(recursos?(

•  En(sistemas(centralizados(los(problemas(de(sincronización(como(la(exclusión(mutua(

se(resuelven(con(métodos(como(semáforos,(monitores,(etc.,(que(no%sirven(en(
sistemas(distribuidos(porque(se(basan(en(el(uso(de((memoria%comparCda.(

•  Dos(procesos(que(usan(un(semáforo(deben(poder(acceder(a(él.(P.ej.(si(los(procesos(

están(en(dos(máquinas(dis8ntas(este(método(no(funciona.(

•  Determinar(si(un(evento(A(ocurre(antes(que(el(evento(B(no(es(trivial.(

©2017((Marisol(García(Valls((

(4(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

2

• 

• 

((Sincronización(mediante(relojes(

La(sincronización(en(sistemas(distribuidos(se(basa(en(algoritmos%distribuidos.(

Las(caracterís8cas(de(un(algoritmo(distribuido(son:(
–  Tienen(la(información%relevante%distribuida(entre(múl8ples(máquinas.(
–  Los(procesos(toman%decisiones(basándose(únicamente(en(información%local.(
–  Deben(evitarse(los(puntos%únicos%de%fallo(en(el(sistema.(
–  No%existe%un%reloj%común(o(ningún(8empo(global(de(precisión.(

•  En(un(sistema%centralizado(el(Cempo%es%no%ambiguo.(

•  En(un(sistema%distribuido(alcanzar(un(acuerdo%sobre(el(8empo(no%es%trivial.(

Máquina en la que
ejecuta el compilador

Máquina en la que
ejecuta el editor

2144

2145

2146

2147

a.out creado

a.c creado

2142

2143

2144

2145

Tiempo según el
reloj local

Tiempo según el
reloj local

©2017((Marisol(García(Valls((

(5(

Arquitectura(de(sistemas(II(T(GIT(

El(reloj(

• 

• 

• 

• 

• 

• 

• 

• 

• 

Los(computadores(8enen(un(circuito(que(permite(contabilizar%el%Cempo:(el%reloj(o(temporizador.(

Es(un(cristal(de(cuarzo(que(oscila(a(una(frecuencia(bien(definida(cuando(se(le(aplica(una(tensión.(

Cada(cristal(8ene(dos%registros(asociados:(un(contador((counter)(y(un(registro(mantenedor((holding*
register).(

Cada(oscilación(del(cristal(disminuye%el%contador%en(una(unidad.(

Cuando(el(contador(llega(a%0(se(genera(una(interrupción(y(el(contador(se(recarga%con(el(valor(del(
registro(mantenedor.(

Cada(interrupción(es(conocida(como(un(Cc%de%reloj((clock*.ck).(

Reg. mantenedor

En(un(sistema(con(una(sola(CPU(todos(los(procesos(comparten(el(mismo(reloj.(

Reg. Contador

Si == 0 ! Int

Si(hay(varias%CPUs,(los(relojes%soRware%no%estarán%sincronizados.(Sus(diferentes(valores(son(
conocidos(como(la(desviación%del%reloj((clock*skew).(

¿Es%posible(sincronizar%todos%los%relojes(para(obtener(un(único(y(no(ambiguo(estándar%de%Cempo?(

©2017((Marisol(García(Valls((

(6(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

3

Relojes(lógicos(y(relojes(Qsicos(

•  Acordar(el(8empo(exacto(no(es(lo(más(importante,(sino(acordar%el%orden%

en%que%suceden%los%eventos.((

•  En(ciertos(algoritmos(basta(con(que(las(máquinas(conozcan(el(mismo%

Cempo,(es(decir,(que(presenten(una(consistencia%interna%respecto(a(sus(
relojes.(

•  En(estos(8pos(de(algoritmos(se(suele(hablar(de(relojes%lógicos.(

•  Si(además(de(acordar(el(mismo(8empo,(los(relojes(no(pueden(desviarse(

del(8empo(real(más(de(una(cierta(can8dad(se(suele(hablar(de(relojes%
Vsicos.(

©2017((Marisol(García(Valls((

(7(

Arquitectura(de(sistemas(II(T(GIT(

Sincronización(de(relojes(lógicos.(Alg.%de%Lamport%%I%
Se(define(la(relación(sucede%antes%como(a%→%b%:(todos(los(procesos(acuerdan(que(el(
evento(a(sucede*antes(que(el(evento(b.(

a%→%b%%es(cierto(de(forma(directa(en(dos(situaciones:(
–  Si(a%y(b(son(eventos*en*el*mismo*proceso(y(a&ocurre*antes*que*b&
–  Si(a(es(el(evento(de(un(mensaje(que(es(enviado(por(un(proceso(y(b(es(el(evento(de(un(

mensaje(que(es(recibido(por(otro(proceso(

a%→%b%es(transi8va.(

Si(los(eventos*x*e*y&suceden*en*dis,ntos&procesos(que(no%intercambian%mensajes(entonces(
x%→%y(no(es(cierta(y(tampoco(lo(es(y%→%x%.(

Se(quiere(asignar(a(los(eventos(un(valor(de(8empo(C(sobre(el(que(todos(los(procesos(estén(
de(acuerdo.(

Los(valores(de(8empo(cumplirán(que(si(a%→%b%entonces(C(a)%<%C(b)%.(

• 

• 

• 

• 

• 

• 

•  Además,(se(cumple(que(el(8empo(de(reloj(C%siempre(se(incrementa.(Las(correcciones(se(

efectúan(sumando%valores%posiCvos.(

©2017((Marisol(García(Valls((

(8(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

4

Sincronización(de(relojes(lógicos.(Alg.%de%Lamport%%II%

0
0
6
12
18
24
30
36
42
48
54
60

1
0
8
16
24
32
40
48
56
64
72
80

A

D

B

C

2
0
10
20
30
40
50
60
70
80
90
100

0
0
6
12
18
24
30
36
42
48
70
76

1
0
8
16
24
32
40
48
61
69
77
85

A

D

B

C

2
0
10
20
30
40
50
60
70
80
90
100

©2017((Marisol(García(Valls((

(9(

Arquitectura(de(sistemas(II(T(GIT(

Relojes(Qsicos(

•  El(algoritmo(anterior(ordena(la(sucesión(de(eventos(pero(no(les(asigna(valores(de(

8empo(real.(

•  En(algunos(sistemas((por(ejemplo,(en(sistemas(de(8empo(real)(el%valor%real%del%

reloj%es%importante.(

•  Para(estos(sistemas(se(requieren(varios(relojes%Vsicos%exteriores.(

•  Esto(presenta(problemas(de(sincronización%de%unos%relojes%respecto%a%otros(y(

respecto%al%Cempo%del%mundo%real.(

•  El(8empo(del(mundo(real(se(mide(respecto(al(Tiempo%Universal%Coordinado((UTC).(

•  El(UTC(es(difundido(por(el(NIST((Ins8tuto(Nacional(de(Tiempo(Estándar)(que(opera(

una(estación(de(radio(de(onda(corta(WWV.(

•  WWV(envía(un(pulso(corto(al(comienzo(de(cada(segundo(UTC(con(una(precisión(de(

±1(ms((debido(a(las(condiciones(atmosféricas(±10(ms().(

©2017((Marisol(García(Valls((

(10(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

5

Sincronización(de(relojes(Qsicos(

•  Algoritmo(de(Berkeley(

•  Algoritmos(de(media(

•  Múl8ples(fuentes(externas(de(hora((

•  Aplicaciones(de(relojes(sincronizados(

©2017((Marisol(García(Valls((

(11(

Arquitectura(de(sistemas(II(T(GIT(

Sincronización(de(relojes(Qsicos.(Alg.%de%Berkeley%

•  El(servidor%de%Cempo(es(ac8vo;(es(un(daemon&de*.empo.(

•  Periódicamente(pregunta%a%cada%máquina(su(valor(de(8empo.(

•  Según(las(respuestas(obCene%la%media%del%valor%de%Cempo(e(informa(al(resto(de(

máquinas%que%deben%ajustar%sus%relojes.(

•  Este(sistema(es(adecuado(cuando(ninguna(máquina(8ene(un(receptor(WWV.(

3:00

3:00

+25

-10

-20

+15

©2017((Marisol(García(Valls((

(12(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

6

Sincronización(de(relojes(Qsicos.(Algoritmos%de%media%
•  Al(contrario(que(el(anterior,(éste(es(un(algoritmo(descentralizado.(

• 

• 

Se(divide(el(8empo(en(intervalos%de%resincronización(y(de(duración(fija.(

El(intervalo*i;ésimo(es([T0(+(iR,(T0(+((i+1)R](donde(T0(es(un(instante(pasado(y(R(es(un(
parámetro(de(sistema.(

•  Al(comienzo%de%cada%intervalo(cada(máquina(difunde%su%Cempo%actual.(

• 

Se(arranca(un(temporizador(para(recoger%todas%las%difusiones%de%otros.(

•  Cuando(llegan,(se(ejecuta(un(algoritmo%que%calcula%el%nuevo%Cempo.%

•  Variaciones(de(este(algoritmo(pueden(ser:(

–  Media(de(los(valores.(
–  Descartar%los%valores%más%alejados%(más(altos(y(más(bajos)(y(obtener(la(media(del(
–  Corrección%de(cada(mensaje(con(una(esCmación%del%Cempo%de%propagación(del(

resto((medida(contra(relojes(defectuosos).(

origen.(

©2017((Marisol(García(Valls((

(13(

Arquitectura(de(sistemas(II(T(GIT(

Sincronización(de(relojes(Qsicos.(MúlCples%fuentes%

externas%de%hora%

Sistemas%que%requieren%mucha%precisión(en(la(sincronización(con(el(UTC(pueden(tener(
varios(receptores(WWV.(

El(sistema(opera8vo(produce(un(rango(o(intervalo(de(8empo(en(el(que(está(el(UTC(que(
calcula.(

• 

• 

•  Dis8ntas(fuentes(de(UTC(producirán(dis8ntos(intervalos,(por(lo(que(deberán(alcanzar%un%

acuerdo.(

• 

La(base(de(este(acuerdo(está(en(que(cada(máquina(con(una(fuente(de(UTC(puede(difundir%
su%intervalo%periódicamente((p.ej.(al(inicio(de(cada(minuto(UTC).(

•  Cada(procesador(recogerá(los(paquetes(dentro(de(un(8empo(determinado,(según:(la(

distancia(entre(ellos,(el(número(de(pasarelas,(colisiones,(etc.(

•  Diferentes(sistemas(opera8vos(realizan(este(acuerdo(de(forma(diferente.(

©2017((Marisol(García(Valls((

(14(

Arquitectura(de(sistemas(II(T(GIT(

15/03/17

7

Aplicaciones(de(sincronización(de(relojes(

(

•  Entrega%única%de%mensajes%(At5Most5Once&Message&Delivery)(

(

•  Consistencia%de%caché%basada%en%el%reloj%

%

©2017((Marisol(García(Valls((

(15(

Arquitectura(de(sistemas(II(T(GIT(

Entrega%única%de%mensajes%

(At5Most5Once&Message&Delivery)(

(

Los(mensajes(llegan(a(través(de(una(cierta(conexión.(Cada(mensaje(lleva(un(idenCficador%de%conexión(y(
una(marca%de%Cempo((.mesta