PDF de programación - 5-Sincronizacion - Sistemas Operativos Distribuidos

Sistemas Operativos Distribuidos

Sistemas Operativos Distribuidos

Sincronización en Sistemas Distribuidos

Más compleja que en los centralizados

Sincronización,
Sincronización,
Concurrencia y
Concurrencia y
Transacciones
Transacciones

Sistemas Operativos Distribuidos

Tiempo y Estados
Tiempo y Estados

•Relojes Distribuidos
Relojes Distribuidos
•Relojes Lógicos

i d d d l

it

di t ib id

• Propiedades de algoritmos distribuidos:

P
– La información relevante se distribuye entre varias máquinas.
– Se toman decisiones sólo en base a la información local.
– Debe evitarse un punto único de fallo.
– No existe un reloj común.
• Problemas a considerar:

– Tiempo y estados globales.
– Exclusión mutua.
– Algoritmos de elección.
– Operaciones atómicas distribuidas: Transacciones

Sistemas Operativos Distribuidos
2

María S. Pérez

Fernando Pérez
José María Peña

Sincronización de Relojes Físicos

Relojes hardware de un sistema distribuido no están
sincronizados.
Necesidad de una sincronización para:
Necesidad de una sincronización para:

– En aplicaciones de tiempo real.
– Ordenación natural de eventos distribuidos (fechas de ficheros).

Concepto de sincronización:

– Mantener relojes sincronizados entre sí.
– Mantener relojes sincronizados con la realidad.

UTC: Universal Coordinated Time

– Transmisión de señal desde centros terrestres o satélites.
– Una o más máquinas del sistema distribuido son receptoras de señal

UTC.

5-Sincronización

1

Sistemas Operativos Distribuidos
4

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos

Algoritmo de Cristian

Cliente
T0

petición

Servidor
de tiempos

o
o
p
m
e
i
t

I

Tiempo del manejador

de interrupciones

T1

i e m p o

t

• Adecuado para sincronización con UTC.
• Tiempo de transmisión del mensaje: (T1-T0)/2
• Tiempo en propagar el mensaje: (T1-T0-I)/2
(T1 T0 I)/2
• Valor que devuelve el servidor se incrementa en (T1-T0-I)/2
• Para mejorar la precisión se pueden hacer varias mediciones y

Ti

l



j

descartar cualquiera en la que T1-T0 exceda de un límite

Sistemas Operativos Distribuidos
5

María S. Pérez

Fernando Pérez
José María Peña

Algoritmo de Berkeley

• El servidor de tiempo realiza un muestreo periódico de todas

las máquinas para pedirles el tiempo.

• Calcula el tiempo promedio e indica a todas las máquinas que
• Calcula el tiempo promedio e indica a todas las máquinas que

avancen su reloj a la nueva hora o que disminuyan la
velocidad.

• Si cae servidor: selección de uno nuevo (alg. de elección)

3:00

3:00

3:00

0

3:00

+5

3:00

+25

-20

3:00

-10

+15

3:25
Sistemas Operativos Distribuidos
6

2:50

3:25

2:50

3:25

2:50

María S. Pérez

Fernando Pérez
José María Peña

Protocolo de Tiempo de Red

Protocolo de Tiempo de Red

NTP (Network Time Protocol).

– Aplicable a redes amplias (Internet).
– La latencia/retardo de los mensajes es significativa y variable.

g

y

j

Objetivos:

– Permitir sincronizar clientes con UTC sobre Internet.
– Proporcionar un servicio fiable ante fallos de conexión.
– Permitir resincronizaciones frecuentes.
– Permitir protección ante interferencias del servicio de tiempo.

Organización:

– Jerarquía de servidores en diferentes estratos.
– Los fallos se solventan por medio de ajustes en la jerarquía.

La sincronización entre cada par de elementos de la jerarquía:

– Modo multicast: Para redes LAN. Se transmite por la red a todos los

elementos de forma periódica. Baja precisión.

j p

p

– Modo de llamada a procedimiento: Similar al algoritmo de Cristian.

Se promedia el retardo de transmisión. Mejor precisión.

– Modo simétrico: Los dos elementos intercambian mensajes de

sincronización que ajustan los relojes. Mayor precisión.

Los mensajes intercambiados entre dos servidores son
Los mensajes intercambiados entre dos servidores son
datagramas UDP.

Sistemas Operativos Distribuidos
7

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
8

María S. Pérez

Fernando Pérez
José María Peña

5-Sincronización

2

Sistemas Operativos Distribuidos

Causalidad Potencial

Relojes Lógicos (Algoritmo de Lamport)

En ausencia de un reloj global la relación causa-efecto (tal como
precede a) es una posibilidad de ordenar eventos.

Relación de causalidad potencial (Lamport)

– eij = evento j en el proceso i
– Si j < k entonces eij → eik
– Si ei=send(m) y ej=receive(m), entonces ei → ej
– La relación es transitiva.

Dos eventos son concurrentes (a || b) si no se puede deducir
entre ellos una relación de causalidad potencial.

• Útiles para ordenar eventos en ausencia de un reloj común.
– Cada proceso P mantiene una variable entera LCP (reloj lógico)
– Cuando un proceso P genera un evento, LCP=LCP+1
– Cuando un proceso envía un mensaje incluye el valor de su reloj
– Cuando un proceso Q recibe un mensaje m con un valor t:

g

p

P

P

,

• LCQ=max(LCQ,t)+1
• El algoritmo asegura:

– Que si a → b entonces LCa < LCb
– Pero LCa < LCb no implica a → b (pueden ser concurrentes)
(p
)

p

b

a

• Relojes lógicos sólo representan una relación de orden parcial.
• Orden total entre eventos si se añade el número del

procesador.

Sistemas Operativos Distribuidos
9

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
10

María S. Pérez

Fernando Pérez
José María Peña

Algoritmo de Lamport

No sincronizado

Sincronizado

+1

+1

Relojes de Vectores (Mattern y Fidge)

Para evitar los casos en los que LCa < LCb no implica a → b.
Cada reloj es un array V de N elementos siendo N el número de
procesadores (nodos) del sistema
procesadores (nodos) del sistema.
– Inicialmente Vi[j]=0 para todo i,j
– Cuando el proceso i genera un evento Vi[i]=Vi[i]+1
– Cuando en el nodo i se recibe un mensaje del nodo j con un vector

de tiempo t entonces:
• para todo k: Vi[k]=max(Vi[k],t[k]) (operación de mezcla) y
• Vi[i]=Vi[i] + 1
Vi[i] Vi[i] + 1

Por medio de este mecanismo siempre es posible evaluar si dos
marcas de tiempo tienen o no relación de precedencia.

Sistemas Operativos Distribuidos
11

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
12

María S. Pérez

Fernando Pérez
José María Peña

5-Sincronización

3

Sistemas Operativos Distribuidos

Algoritmo de Mattern y Fidge

Uso de los Relojes Lógicos

A

(100)

(200)

B

(300)

C

(400)

(562)

D

(662)

E

(010)

(020)

(230)

(242)

F

(252)

(262)

(276)

G

(286)

H

(001)

(002)

I

(003)

(024)

(025)
J

(026)

K

(027)

(000)

A→F ⇔ (100)<(252)
B||J ⇔ (300)<(025) AND (300)>(025)

La utilización de relojes lógicos (Lamport, Vectoriales o
Matriciales) se aplica a:

– Mensajes periódicos de sincronización
Mensajes periódicos de sincronización.
– Campo adicional en los mensajes intercambiados (piggybacked).

Por medio de relojes lógicos se pueden resolver:

– Ordenación de eventos (factores de prioridad o equitatividad).
– Detección de violaciones de causalidad.
– Multicast causal (ordenación de mensajes)
– Multicast causal (ordenación de mensajes).

Sistemas Operativos Distribuidos
13

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
14

María S. Pérez

Fernando Pérez
José María Peña

Estados Globales

Snapshots

• En un sistema distribuido existen ciertas situaciones que no es

posible determinar de forma exacta por falta de un estado
global:
global:
– Recolección de basura: Cuando un objeto deja de ser referenciado

por ningún elemento del sistema.

– Detección de interbloqueos: Condiciones de espera cíclica en grafos

de espera (wait-for graphs).

– Detección de estados de terminación: El estado de actividad o

espera no es suficiente para determinar la finalización de un proceso.

El análisis de los estados globales de un sistema se realiza por
medio de snapshots: Agregación del estado local de cada
componente así como de los mensajes actualmente en
componente así como de los mensajes actualmente en
transmisión.

Debido a la imposibilidad de determinar el estado global de todo
el sistema en un mismo instante se define una propiedad de
consistencia en la evaluación de dicho estado
consistencia en la evaluación de dicho estado.

Sistemas Operativos Distribuidos
15

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
16

María S. Pérez

Fernando Pérez
José María Peña

5-Sincronización

4

Sistemas Operativos Distribuidos

Cortes Consistentes

Corte no consistente
p1
p3

p2

Corte consistente
p3

p2

p1

m1

m4 no se
ha enviado

m4
4

m4 ya ha
ll
d
llegado

m2

m3

m5

m1

m4
4

m2

m3

m5

Sistemas Operativos Distribuidos
17

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos

Exclusión Mutua
Exclusión Mutua

•Algoritmos de
Algoritmos de
Exclusión Mutua

Exclusión Mutua

Exclusión Mutua

Mecanismo de coordinación entre varios procesos concurrentes
a la hora de acceder a recursos/secciones compartidas.

Las soluciones definidas para estos problemas son:

– Algoritmos centralizados.
– Algoritmos distribuidos.
– Algoritmos basados en marcas de tiempo.

Problemática:

– No existen variables compartidas
– Riesgo de interbloqueos
– Riesgo de inanición

Funciones básicas de exclusión mutua:

– enter(): Acceso a la región critica (bloqueo).
– operations(): Manipulación de los recursos compartidos.
– exit(): Liberación del recurso (despierta a procesos en espera).

()

p

p

p

Propiedades:

– Seguridad: Como máximo un proceso puede estar ejecutado en la

sección crítica a la vez.
Vivacidad: Eventualmente se producen entradas y salidas en la
– Vivacidad: Eventualmente se producen entradas y salidas en la
sección crítica.

– Ordenación: Los procesadores acceden a la región crítica en base a

unos criterios de ordenación (causalidad temporal/Lamport).

Sistemas Operativos Distribuidos
19

María S. Pérez

Fernando Pérez
José María Peña

Sistemas Operativos Distribuidos
20

María S. Pérez

Fernando Pérez
José María Peña

5-Sincronización

5

Sistemas Op