PDF de programación - Sincronización en Sistemas Distribuidos - Sistemas de Operación II

Sistemas de Operación II

Sincronización en Sistemas Distribuidos

Prof. Carlos Figueira

Basado en material de
Yudith Cardinale (USB)

Andrew Tanembaum y Marteen van Steen

Contenido

● Introducción
● Relojes (temporizadores o timers)
● Sincronización de relojes lógicos
● Sincronización de relojes físicos
● Exclusión mutua distribuida
● Algoritmos de elección de coordinador

Carlos Figueira/USB

2

Algoritmos distribuidos:Propiedades

● La información relevante se distribuye entre

varias máquinas.

● Los procesos toman las decisiones sólo en

base a la información disponible en forma local.

● Debe evitarse un punto de fallo único en el

sistema.

● No existe un reloj común o alguna otra fuente

precisa del tiempo global.

Carlos Figueira/USB

3

Aspectos a considerar

● Tiempos y estados globales.
● Exclusión mutua.
● Algoritmos de elección. Problemas de

consenso

● Operaciones atómicas distribuidas:

Transacciones

Carlos Figueira/USB

4

Relojes y Sincronización

● Reloj: circuito con contador (C),

registro de valor inicial (HR) y
cristal cuarzo que cuenta
oscilaciones

● Cuando C llega a 0, genera una
interrupción (tick), manejada por
software y escalada a unidad de
tiempo conveniente

C

HR

Carlos Figueira/USB

5

Relojes

● ¿Pueden dos eventos tener el mismo registro
de reloj? Depende de resolución del reloj y la
frecuencia de ocurrencia de eventos

● La frecuencia de un cristal de cuarzo es muy
estable, pero puede variar por: temperatura,
tamaño, forma de corte. ¡Puede desfasarse!

● Desfase: diferencia entre reloj y una referencia

(reloj ideal) por unidad de tiempo medida

Carlos Figueira/USB

6

Sincronización de relojes físicos

● Los relojes (hardware) de cada máquina de un

sistema distribuido no están sincronizados
(frecuencia, fase)

● Sincronización es importante para:

● Aplicaciones en tiempo real
● Ordenación de eventos distribuidos

● Concepto de sincronización:

● Mantener relojes sincronizados entre sí
● Mantenerlos sincronizados con la realidad

Carlos Figueira/USB

7

Relojes lógicos

● En los sistemas/aplicaciones distribuidos

importa generalmente la secuencia de
ocurrencia de los eventos, no el tiempo exacto

● Reloj Lógico: contador de software que se

incrementa de manera monotónica, cuyo valor
no necesita estar relacionado con ningún reloj
físico.

● El reloj lógico nos permite ordenar eventos.
Generalmente se asocia a cada proceso un
reloj lógico

Carlos Figueira/USB

8

Sincronización de relojes lógicos:

Algoritmo de Lamport

● Principios:

● Si dos eventos ocurrieron en el mismo proceso,
entonces ocurrieron en el orden en que fueron
observados. Notación: x p y, donde x e y son
eventos que ocurren en el proceso P y “x ocurrió
antes que y”

● Siempre que un mensaje es enviado entre

procesos, el evento de enviar el mensaje ocurre
antes de recibirlo

Carlos Figueira/USB

9

Algoritmo de Lamport (cont.)

● Se generalizan estos ordenamientos con la
relación “pasó antes” (happened before), se
denota con → y se define como:
● PA1: si existe un proceso P, tal que

x

P

y

entonces x → y

● PA2: para cualquier mensaje m, send(m) →recv(m)

● PA3: (transitividad) si x,y,z son eventos tales que

x →y , y →z, entonces x →z


Carlos Figueira/USB

10

Algoritmo de Lamport (cont.)
c
f

b
d

b

c

d

a
c

b
d
a

e

a

P0

P1

P2

e

f

● Si cada proceso tiene un reloj lógico Cp se puede asignar

un valor de tiempo a cada evento : Cp(a)

● Propiedades:

● Si a → b, entonces Cp(a) < Cp(b)
● El valor de Cp siempre incrementa, nunca decrementa

Carlos Figueira/USB

11

Algoritmo de Lamport (cont.)

● Ordenamiento Causal

● LC1: Cp es incrementado antes que cada evento

sea ejecutado (Cp=Cp+1)

● LC2: cuando un proceso P envía un mensaje m,

coloca en el mensaje el valor t=Cp

● LC3: cuando un proceso Q recibe mensaje (m,t), Q

calcula Cq=max(Cq, t) y aplica LC1

● ¿Cp(a) < Cq(b) implica a →b ?

Carlos Figueira/USB

12

Algoritmo de Lamport: Ejemplo

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

a

A

b

g

D

h

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

c

B

C

f

d

e

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

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

a

A

b

g

D

h

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

c

B

C

f

d

e

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

Tres relojes no sincronizados

Sincronización de relojes

Carlos Figueira/USB

13

Sincronización de Relojes Físicos

● Sincronizar los relojes físicos con la hora real

(referencia única)

● Sincronizar los relojes físicos entre sí
● Se toma en cuenta el Tiempo Universal

Coordinado (UTC)

Carlos Figueira/USB

14

Sincronización de Relojes Físicos

● Tiempo Atómico Internacional (TAI) mantenido

por el BIH (Bureau International de l'Heure),
París

● Laboratorios mantienen tiempo contando
transiciones del átomo de cesio-133. Un
segundo atómico es 9.192.631.770
transiciones del cesio-133

● Cada lab. envía al BIH el número de ticks de su
reloj (se empezó en 1958). El BIH calcula el TAI
promediando las lecturas de los lab.

Carlos Figueira/USB

15

Sincronización de Relojes Físicos

● Segundo solar: 1/86.400 veces el día solar
● UTC es un estándar basado en TAI, usa unos
“segundos de salto” para sincronizar TAI con
segundos solares

● En EEUU, el Instituto Nacional de Estándares y
Tecnología (NIST) difunde señal por onda corta

● Otras posibilidades: NTP (Internet), Satélite

(GEPS. GPS)

Carlos Figueira/USB

16

TAI vs segundos solares

Carlos Figueira/USB

17

Sincronización relojes físicos: Alg.

de Cristian

● Servidor de reloj en red
● El tiempo nunca retrocede: ajustar gradualmente
● ¿Tiempo de tránsito? Estimarlo Tprop=((T2-T1)+(T4-T3))/2 =>

TA'=TB + Tprop, Θ = TA-TA'

Carlos Figueira/USB

18

Sincronización de Relojes Físicos

● ¿Cada cuánto se debe sincronizar?
● Cada máquina tiene reloj que causa H

interrupciones por segundo. En la práctica, se
obtiene un error e

● En cada interrupción se suma 1 al reloj del sistema
(C) que mantiene número de ticks desde una fecha
de referencia pasada

● IDEAL: Si UTC=t, en máquina M se debe cumplir
que CM(t)=t para todo M,t. Así, se cumple dC/dt=1

Carlos Figueira/USB

19

Relación entre tiempo local y UTC

Carlos Figueira/USB

20

Sincronización de relojes físicos

● Se cumple que: 1-e <= dC/dt <= 1+e
● e es provisto por el fabricante
● La idea es sincronizar el reloj con UTC y que entre

ellos no haya una diferencia mayor de δ.

● En el peor caso, en un tiempo T un reloj se atrasa
eT y el otro se adelanta eT, siendo la diferencia en
tiempo entre ambos de 2eT.

● Para que esta diferencia sea menor que δ (i.e.
2eT<δ), los relojes deben ser re-sincronizados
cada δ/2e segundos

Carlos Figueira/USB

21

Sincronización relojes físicos:

Algoritmo de Berkeley

● Se basa en servidor de
tiempo activo (demonio
del tiempo), que
consulta el tiempo
periódicamente a cada
máquina (en Intranets)

● Tiempo colocado
manualmente por
operador

Carlos Figueira/USB

22

Algoritmo de Berkeley

Carlos Figueira/USB

23

Sincronización relojes físicos:

Algoritmo de Berkeley

● ¿Qué ventaja tiene transmitir el ajuste y no la

hora?

● ¿Qué pasa si hay relojes con desfases muy

grandes?

● El demonio toma promedio tolerante a fallas:
subconjunto de relojes seleccionados para
promediar son aquellos que no difieran entre sí
más allá de una cantidad especificada.

Carlos Figueira/USB

24

Exclusión Mutua Distribuida

¿Ideas?

Carlos Figueira/USB

25

Requerimientos

1. EM1 (seguridad). A lo sumo un proceso a la

vez puede ejecutar su sección crítica (SC)

2. EM2 (vitalidad).

1. (Sin bloqueo) Un proceso que requiere entrada a

su SC, en algún momento se le concederá

2. (Sin inanición) Cualquier proceso que ejecute su

SC, en algún momento saldrá de ella

3. EM3 (ordenamiento). La entrada a la SC debe

ser otorgada en el orden “pasó antes”

Carlos Figueira/USB

26

Algoritmo Centralizado

● Si un proceso quiere entrar en su SC, envía un
mensaje de solicitud al coordinador, indicando
cuál SC requiere

● Si ningún proceso está en esa SC, coordinador

envía mensaje de otorgamiento

● Si hay otro proceso en la SC, encola su petición
● Envía mensaje de negación, y solicitante intentará

de nuevo más tarde (espera activa) o

● No envía nada, el solicitante se bloquea

Carlos Figueira/USB

27

Algoritmo Centralizado (cont.)

● Si un proceso sale de la SC, envía un mensaje

notificando al coordinador

● Coordinador busca siguiente petición encolada

y envía mensaje de otorgamiento

Coordinador

1. solicita

3. otorga

2. libera

P1

P2

P3

P4

P2

P4
P1

sc1

sc2

Carlos Figueira/USB

28

Algoritmo Centralizado (cont.)

● Ventajas

● Se puede generalizar para asignación de recursos
● Es justo: peticiones atendidas en orden de solicitud
● Requiere sólo 3 tipos de mensaje

● Desventajas

● Centralizado (punto único de falla, cuello de botella)
● Si coordinador no envía respuesta ante negación, el

solicitante no sabe si respuesta no llega por negación
o por falla

● ¿Qué pasa si cliente falla dentro de una SC?

Carlos Figueira/USB

29

Algoritmo Distribuido: Ricart y

Agrawala

● Cada proceso que requiere entrar a SC envía

mensaje a todos los procesos; entra sólo
cuando recibe confirmación de todos

● Construye mensaje con id de SC, id. de

proceso y hora actual

● Envía mensaje a todos, incluyendo a sí mismo

Carlos Figueira/USB

30

Algoritmo Ricart y Agrawala (cont.)

● Cuando un proceso recibe mensaje de solicitud

de otro proceso:
1. Si receptor no está en esa SC y no desea entrar,

envía OK

2. Si receptor está en SC, no responde sino que

incluye solicitud en una lista

3. Si el receptor desea entrar en SC pero no lo ha

logrado, compara fecha del mensaje recibido con la
fecha del que él envió: si la suya es menor, encola
la petición; sino, envía OK

Carlos Figueira/USB

31

Algoritmo Ricart y Agrawala (cont.)

● Dos procesos (0 y 2)
quieren acceder a un
recurso compartido al
mismo tiempo