Si el receptor no está en la región crítica y no desea entrar a ella, envía de regreso un
mensaje o.k. al emisor.
Si el receptor ya está en la región crítica no responde y encola la solicitud.
Si el receptor desea entrar a la región crítica pero aún no lo logró, compara:
Si su propio mensaje tiene una marca menor el receptor no envía nada y encola el
pedido.
Si el mensaje recibido es menor el receptor envía un o.k.
La menor de las marcas gana.
La marca contenida en el mensaje que envió a cada uno.
La marca de tiempo del mensaje recibido con,
Los físicos definieron al segundo como el tiempo que tarda el átomo de cesio 133 para
hacer 9.192.631.770 transiciones:
Se tomó este número para que el segundo atómico coincida con el segundo solar
promedio de 1958.
El algoritmo de Lamport asigna tiempos a los eventos.
Consideramos tres procesos que se ejecutan en diferentes máquinas, cada una con su
propio reloj y velocidad:1
El proceso “0” envía el mensaje “a” al proceso “1” cuando el reloj de “0” marca
“6”.
El proceso “1” recibe el mensaje “a” cuando su reloj marca “16”.
Si el mensaje acarrea el tiempo de inicio “6”, el proceso “1” considerará que tardó
10 marcas de reloj en viajar.
El mensaje “b” de “1” a “2” tarda 16 marcas de reloj.
El mensaje “c” de “2” a “1” sale en “60” y llega en “56”, tardaría un tiempo
negativo, lo cual es imposible.
El mensaje “d” de “1” a “0” sale en “64” y llega en “54”.
Lamport utiliza la relación “ocurre antes de”
Los problemas relativos a las regiones críticas, exclusión mutua y la sincronización
Generalmente se resuelven en sistemas de una sola cpu con métodos como los se-
máforos y los monitores
No son aplicables a sistemas distribuidos.
Se basan en la memoria compartida.
Se sincronizan entre sí
Cooperan
SINCRONIZACION EN SISTEMAS DISTRIBUIDOS
Seek to understand how this civilization had evolved into becoming one of the most powerful in history.
Learn about Greek scientific breakthroughs, great battles, and mysterious stories with gods and goddesses.
9.14 PREVENCION DISTRIBUIDA DE BLOQUEOS
La prevención consiste en el diseño cuidadoso del sistema para que los bloqueos sean im-
posibles estructuralmente [25, Tanenbaum].
Entre las distintas técnicas se incluye:
Los ciclos son imposibles.
Las marcas aparecen en forma creciente.
Se puede permitir la espera solo si el proceso en estado de espera tiene una marca
inferior (más viejo) que el otro.
Se verifica cuál de ellos tiene la marca de tiempo mayor (es más joven).
No pueden haber parejas de transacciones con igual marca de tiempo asociada.
Se puede asociar a cada transacción una marca de tiempo global al momento de su
inicio.
Hacer que todos los procesos liberen todos sus recursos cuando soliciten uno nuevo.
Exigir a los procesos que soliciten todos sus recursos desde un principio.
Permitir a los procesos que solo conserven un recurso a la vez.
9.13 DETECCION DISTRIBUIDA DE BLOQUEOS
Cuando se detecta un bloqueo en un S. O. convencional se resuelve eliminando uno o más
procesos
Cuando se detecta un bloqueo en un sistema basado en transacciones atómicas se
resuelve abortando una o más transacciones:
La transacción puede volver a comenzar.
El sistema restaura el estado que tenía antes de iniciar la transacción.
9.13.2 DETECCION DISTRIBUIDA DE BLOQUEOS
Un algoritmo típico es el de Chandy-Misra-Haas.
Los procesos pueden solicitar varios recursos (por ejemplo cerraduras) al mismo tiempo,
en vez de uno cada vez.
Se permiten las solicitudes simultáneas de varios procesos:
Si un mensaje recorre todo el camino y regresa a su emisor original (el proceso
enlistado en el primer campo), entonces:
Existe un ciclo y el sistema está bloqueado.
Al llegar el mensaje el receptor verifica si él mismo espera a algunos procesos, en
cuyo caso:
El mensaje se envía al proceso debido al cual se bloquea
El mensaje se actualiza
El mensaje consta de tres números:
El proceso recién bloqueado, el proceso que envía el mensaje y el proceso al
cual se envía.
Se genera un mensaje de exploración que se envía al proceso (o procesos) que detienen
los recursos necesarios.
Los recursos que espera un proceso pueden ser locales o remotos (de otra máquina).
Un proceso puede esperar a uno o más recursos simultáneamente.
9.13.1 DETECCION CENTRALIZADA DE BLOQUEOS
Cada máquina mantiene la gráfica de recursos de sus propios procesos y recursos.
Un coordinador central mantiene la gráfica de recursos de todo el sistema, que es la
unión de todas las gráficas individuales.
Cuando el coordinador detecta un ciclo elimina uno de los procesos para romper el
bloqueo.
La información de control se debe transmitir explícitamente, existiendo las siguientes
variantes:
Una posible solución es utilizar el algoritmo de Lamport para disponer de un tiempo
global.
El coordinador interpreta erróneamente que existe un bloqueo y elimina un proceso.
El coordinador requiere la información cuando la necesita.
Cada máquina informa periódicamente las modificaciones desde la última actualiza-
ción.
Cada máquina informa cada actualización al coordinador.
9.12 BLOQUEOS EN SISTEMAS DISTRIBUIDOS
Son peores que los bloqueos en sistemas monoprocesador. Son especialmente críticos en sistemas de bases de datos distribuidos.
Las estrategias usuales para el manejo de los bloqueos son:
Evitarlos:
Evitar los bloqueos mediante la asignación cuidadosa de los recursos.
Prevención:
Hacer que los bloqueos sean imposibles desde el punto de vista estructural.
Detección:
Permitir que ocurran los bloqueos, detectarlos e intentar recuperarse de ellos.
Algoritmo del avestruz:
Ignorar el problema.
Toda la información relevante está dispersa en muchas máquinas.
Son más difíciles de evitar, prevenir, detectar y solucionar.
9.11 CONTROL DE CONCURRENCIA EN EL MODELO DE TRANSACCION
Los algoritmos de control de concurrencia son necesarios cuando se ejecutan varias tran-
sacciones de manera simultánea
El de las marcas de tiempo.
El del control optimista de la concurrencia.
El de la cerradura.
En distintos procesadores.
En distintos procesos.
9.11.4 RESUMEN
Los diferentes esquemas ofrecen distintas ventajas pero el problema principal es la gran
complejidad de su implantación.
9.11.3 MARCAS DE TIEMPO
Cuando un proceso intente acceder a un archivo, lo logrará si las marcas de tiempo de
lectura y escritura son menores (más antiguas) que la marca de la transacción activa.
Si la marca de tiempo de la transacción activa es menor que la del archivo que intenta
acceder:
En iguales circunstancias y en un esquema de cerraduras podría esperar o continuar
inmediatamente.
Una transacción aborta cuando encuentra una marca mayor (posterior).
La transacción activa se ha realizado tarde y se aborta.
Una transacción iniciada posteriormente ha accedido al archivo y ha efectuado un
compromiso.
Se asocia a cada transacción una marca de tiempo al iniciar (begin_transaction).
Se garantiza que las marcas son únicas mediante el algoritmo de Lamport.
Cada archivo del sistema tiene asociadas una marca de tiempo para la lectura y otra
para la escritura, que indican la última transacción comprometida que realizó la lectura o
escritura.
9.11.2 CONTROL OPTIMISTA DE LA CONCURRENCIA
La probabilidad de fallo puede crecer si la carga de trabajo es muy alta.
Re-ejecución de la transacción en caso de falla.
Paralelismo máximo ya que no se esperan cerraduras.
Ausencia de bloqueos.
Se verifican todas las demás transacciones para ver si alguno de los archivos ha sido
modificado desde el inicio de la transacción:
Si esto no ocurre se realiza el compromiso.
Si esto ocurre la transacción aborta.
Se actúa a posteriori si se presenta algún problema.
Se sigue adelante y se hace todo lo que se deba hacer, sin prestar atención a lo que
hacen los demás.
9.11.1 CERRADURA (LOCKING)
Cuando un proceso debe leer o escribir en un archivo (u otro objeto) como parte de una
transacción, primero cierra el archivo.
La cerradura se puede hacer mediante:
Las cerraduras para escritura no se comparten, es decir que deben ser exclusivas.
Las cerraduras para lectura se comparten.
Rechaza todos los intentos por cerrar archivos ya cerrados por otros procesos.
Mantiene una lista de los archivos cerrados.
Un manejador local de cerraduras en cada máquina.
Un único manejador centralizado de cerraduras.
9.10 IMPLANTACION DEL MODELO DE TRANSACCION
Cuando un proceso inicia una transacción, basta crear un espacio de trabajo particular
para él que sea vacío excepto por un apuntador de regreso al espacio de trabajo de su
proceso padre.
Para una transacción del nivel superior el espacio de trabajo del padre es el sistema
de archivos “real”.
Cuando el proceso abre un archivo para lectura, se siguen los apuntadores de regreso
hasta localizar el archivo en el espacio de trabajo del padre (o algún antecesor).
9.10.3 PROTOCOLO DE COMPROMISO DE DOS FRASES (TWO-PHASE COMMIT)
Uno de los procesos que intervienen funciona como el coordinador.
El coordinador escribe una entrada en la bitácora para indicar que inicia el protocolo.
El coordinador envía a cada uno de los procesos relacionados (subordinados) un men-
saje para que estén preparados para el compromiso.
Cuando un subordinado recibe el mensaje:
El coordinador:
Envía un mensaje a cada subordinado para informarle de la decisión.
Si alguno de los procesos no se compromete (o no responde) la transacción se aborta.
Si todos los procesos están listos para comprometerse cierra la transacción.
Envía de regreso su decisión.
Escribe una entrada en la bitácora.
Verifica si está listo para comprometerse.
9.10.2 BITACORA DE ESCRITURA ANTICIPADA
Este método también se denomina lista de intenciones.
Los archivos realmente se modifican pero antes de cambiar cualquier bloque:
Esta acción se denomina retroalimentación.
Se puede utilizar la bitácora para respaldo del estado original:
A partir del final y hacia atrás
Se deshace cada cambio descripto en él.
Se lee cada registro de la bitácora.
Las estructuras de datos no tienen que modificarse, puesto que ya han sido actuali-
zadas.
Se escribe un registro del compromiso en la bitácora.
Se graba un registro en la bitácora (“log”) de escritura anticipada en un espacio de
almacenamiento estable:
Se indica la transacción que produce el cambio, el archivo y bloque modificados
y los valores anterior y nuevo.
9.10.1 ESPACIO DE TRABAJO PARTICULAR
Consiste en que cuando un proceso inicia una transacción se le otorga un espacio de trabajo
particular:
Significa alto consumo de recursos por las copias de los objetos al espacio de trabajo
particular.
Las lecturas y escrituras irán a este espacio hasta que la transacción se complete o
aborte:
El “espacio real” es el sistema de archivos normal.
Contiene todos los archivos (y otros objetos) a los cuales tiene acceso.
Existen varios métodos de implantación
9.9 EL MODELO DE TRANSACCION
9.9.4 TRANSACCIONES ANIMADAS
Se presentan cuando las transacciones pueden contener subtransacciones (procesos hijos)
que:
Pueden originar nuevas subtransacciones.
Se ejecuten en paralelo entre sí en procesadores distintos.
9.9.3 PROPIEDADES DE LAS TRANSACCIONES
Las propiedades fundamentales son:
Permanencia:
La permanencia se refiere a que una vez comprometida una transacción:
Sigue adelante y los resultados son permanentes.
Atomicidad:
La atomicidad garantiza que cada transacción no ocurre o bien se realiza en su
totalidad:
Se presenta como una acción indivisible e instantánea.
Serialización:
La serialización garantiza que si dos o más transacciones se ejecutan al mismo tiempo:
El resultado final aparece como si todas las transacciones se ejecutasen de manera
secuencial en cierto orden:
9.9.2 PRIMITIVAS DE TRANSACCION
Deben ser proporcionadas por el sistema operativo o por el sistema de tiempo de ejecución
del lenguaje.
Write: se escriben datos en un archivo (o algún otro objeto).
Read: se leen datos de un archivo (o algún otro objeto).
Abort_transaction: se elimina la transacción; se recuperan los valores anteriores.
End_transaction: termina la transacción y se intenta un compromiso.
Begin_transaction: los comandos siguientes forman una transacción.
9.9.1 ALMACENAMIENTO ESTABLE
Se puede implantar con una pareja de discos comunes.
Cada bloque de la unidad 2 es una copia exacta (espejo) del bloque correspondiente
en la unidad 1.
Luego de la recuperación se pueden comparar ambos discos bloque por bloque:
Se puede actualizar la unidad 2 en función de la 1.
Luego se actualiza y verifica el bloque de la unidad 2.
Primero se actualiza y verifica el bloque de la unidad 1.
El software subyacente maneja transparentemente los errores de comunicación.
El sistema consta de varios procesos independientes que pueden fallar aleatoriamente.
9.8 TRANSACCIONES ATOMICAS
Las técnicas de sincronización ya vistas son de bajo nivel
O se hace todo lo que se tenía que hacer como una unidad o no se hace nada.
Permitan a los programadores concentrarse en los algoritmos y la forma en que los
procesos trabajan juntos en paralelo.
Oculten estos aspectos técnicos.
El programador debe enfrentarse directamente con los detalles de:
La recuperación de fallas.
La prevención de bloqueos.
El manejo de las regiones críticas.
La exclusión mutua.
9.7 ALGORITMOS DE ELECCION
Son los algoritmos para la elección de un proceso coordinador, iniciador, secuenciador,
etc. [25, Tanenbaum].
El objetivo de un algoritmo de elección es garantizar que iniciada una elección és-
ta concluya con el acuerdo de todos los procesos con respecto a la identidad del nuevo
coordinador.
9.7.2 UN ALGORITMO DE ANILLO
Se supone que los procesos tienen un orden físico o lógico, es decir que cada proceso conoce
a su sucesor.
Cuando algún proceso observa que el coordinador no funciona:
Concluida la ronda de información el mensaje coordinador se elimina y continúan
los procesos.
El mensaje de elección se transforma en mensaje coordinador y circula nuevamente:
Informa a los demás procesos:
Quiénes son los miembros del nuevo anillo.
Quién es el coordinador, es decir, el miembro de la lista con el número
mayor.
En cierto momento el mensaje regresa al proceso que lo inició:
El proceso lo reconoce al recibir un mensaje con su propio número de proceso.
Si el sucesor está inactivo:
En cada paso, al emisor añade su propio número de proceso a la lista en el
mensaje.
Continúa hasta localizar un proceso en ejecución.
El emisor va hacia el siguiente número del anillo o al siguiente de éste.
Envía el mensaje a su sucesor.
Construye un mensaje elección con su propio número de proceso.
9.7.1 EL ALGORITMO DEL GRANDULON DE GARCIA-MOLINA
Un proceso “P” inicia una elección cuando observa que el coordinador ya no responde a
las solicitudes.
“P” realiza una elección de la siguiente manera:
Realiza una elección salvo que ya esté haciendo alguna.
Envía de regreso un mensaje o.k. al emisor para indicar que está vivo y que tomará
el control.
Si un proceso con un número mayor responde, toma el control y el trabajo de “P”
termina.
Envía un mensaje elección a los demás procesos con un número mayor.
9.6 EXCLUSION MUTUA
Primero ingresa a una región crítica para lograr la exclusión mutua y garantizar que
ningún otro proceso utilizará las estructuras de datos al mismo tiempo.
Cuando un proceso debe leer o actualizar ciertas estructuras de datos compartidas
9.6.3 UN ALGORITMO DE ANILLO
Los procesos se organizan por software formando un anillo lógico asignándose a cada pro-
ceso una posición en el anillo.
Cada proceso sabe cuál es el siguiente luego de él.
Al inicializar el anillo se le da al proceso “0” una ficha (token) que circula en todo
el anillo, que se transfiere del proceso “k” al “k + 1” en mensajes puntuales.
Cuando un proceso obtiene la ficha de su vecino verifica si intenta entrar a una región
crítica:
En caso negativo:
La vuelve a pasar.
En caso positivo:
Después de salir pasa la ficha a lo largo del anillo
El proceso entra a la región crítica, hace el proceso necesario y sale de ella.
9.6.2 UN ALGORITMO DISTRIBUIDO
El objetivo es no tener un único punto de fallo (el coordinador central).
Se requiere un orden total de todos los eventos en el sistema para saber cuál ocurrióprimero.
Cuando un proceso desea entrar a una región crítica:
Se supone que cada mensaje tiene un reconocimiento.
Envía el mensaje a todos los demás procesos y de manera conceptual a él mismo.
Construye un mensaje con el nombre de la región crítica, su número de proceso y la
hora actual.
9.6.1 UN ALGORITMO CENTRALIZADO
La forma más directa de lograr la exclusión mutua en un sistema distribuido es simular a
la forma en que se lleva a cabo en un sistema monoprocesador.
Se elige un proceso coordinador.
Cuando un proceso desea ingresar a una región crítica
El coordinador extrae el primer elemento de la cola de solicitudes diferidas y envía a
ese proceso un mensaje otorgando el permiso, con lo cual el proceso queda habilitado
para acceder a la región crítica solicitada.
El coordinador no otorga el permiso y encola el pedido.
Cuando llega la respuesta el proceso solicitante entra a la región crítica.
Si ningún otro proceso está en ese momento en esa región crítica
Envía un mensaje de solicitud al coordinador
9.5 ALGORITMOS PARA LA SINCRONIZACION DE RELOJES
Se supone que cada máquina tiene un cronómetro que provoca una interrupción “h”
veces por segundo.
Cuando el cronómetro se detiene, el manejador de interrupciones añade “1” a un reloj
en software.
El reloj en software mantiene un registro del número de marcas (interrupciones) a
partir de cierta fecha acordada antes; al valor de este reloj se lo llama “C”.
Cuando el tiempo UTC es “t”, el valor del reloj en la máquina “p” es “Cp(t)”:
Si una máquina tiene un receptor de UTC, todas las máquinas deben sincronizarse con
ella
9.5.4 VARIAS FUENTES EXTERNAS DE TIEMPO
Los sistemas que requieren una sincronización muy precisa con UTC se pueden equipar
con varios receptores de UTC.
Las distintas fuentes de tiempo generaran distintos rangos (intervalos de tiempo) donde
“caerán” los respectivos UTC, por lo que es necesaria una sincronización.
Como la transmisión no es instantánea se genera una cierta incertidumbre en el tiempo.
Cuando un procesador obtiene todos los rangos de UTC:
La intersección determina un intervalo cuyo punto medio será el UTC y la hora del
reloj interno.
Verifica si alguno de ellos es ajeno a los demás y de serlo lo descarta por ser un valor
extremo.
9.5.3 ALGORITMOS CON PROMEDIO
Los anteriores son algoritmos centralizados.
Una clase de algoritmos descentralizados divide el tiempo en intervalos de resincroni-
zación de longitud fija
El i-ésimo intervalo:
“R” es un parámetro del sistema.
“T0” es un momento ya acordado en el pasado.
Inicia en “T0 + i R” y va hasta “T0 + (i + 1) R”.
9.5.2 ALGORITMOS DE BERKELEY
En el algoritmo de Cristian el servidor de tiempo es pasivo.
En el algoritmo de Berkeley el servidor de tiempo:
Con las respuestas
Realiza un muestreo periódico de todas las máquinas para preguntarles el tiempo.
Es activo.
9.5.1 ALGORITMOS DE CRISTIAN
Cada máquina envía un mensaje al servidor para solicitar el tiempo actual, periódica-
mente, en un tiempo no mayor que δ / 2 ρ segundos.
El despachador del tiempo responde prontamente con un mensaje que contiene el tiempo
actual “C UTC”.
Cuando el emisor obtiene la respuesta puede hacer que su tiempo sea “C UTC”.
Un gran problema es que el tiempo no puede correr hacia atrás:
También se debe considerar el tiempo de transmisión.
La atención del requerimiento en el servidor de tiempos requiere un tiempo del
manejador de interrupciones.
“C UTC” no puede ser menor que el tiempo actual “C” del emisor.
El objetivo es sincronizar todas las máquinas con ella.
Una máquina tiene un receptor UTC, por lo que se la llama despachador del tiempo.
Topic principal
9.4 RELOJES FISICOS
El algoritmo de Lamport proporciona un orden de eventos sin ambigüedades.
En ciertos sistemas (ej.: sistemas de tiempo real), es importante la hora real del reloj
Los valores de tiempo asignados a los eventos no tienen porqué ser cercanos a los
tiempos reales en los que ocurren.
9.3 RELOJES LOGICOS
Most important battles in Ancient Greece
Already internally warring, Ancient Greece has fought many battles with external enemies, but four of them were extremely significant: Battle of Marathon (490 B.C.), Battle of Salamis (480 B.C.), Battle of Thermopylae (480 B.C.), and Battle of Chaeronea (338 B.C.).
Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo
reloj
Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj
Cada interrupción se denomina marca de reloj.
Se puede programar un cronómetro para que genere una interrupción “x” veces por
segundo.
Cuando el contador llega a “0”
Cada oscilación del cristal decrementa en “1” al contador.
A cada cristal se le asocian dos registros
Oscila con una frecuencia bien definida que depende
9.2 SINCRONIZACION DE RELOJES
Los primeros tres puntos indican que es inaceptable reunir toda la información en un
solo lugar para su procesamiento, pero lograr la sincronización sin centralización requiere
hacer las cosas distintas al caso de los sistemas operativos tradicionales.
Se requiere un acuerdo global en el tiempo, pues la falta de sincronización en los
relojes puede ser drástica en procesos dependientes del tiempo.
En un sistema distribuido no es trivial poner de acuerdo a todas las máquinas en la
hora.
En un sistema centralizado el tiempo no es ambiguo.
propiedades
No existe un reloj común o alguna otra fuente precisa del tiempo global.
Debe evitarse un único punto de fallo en el sistema.
Los procesos toman las decisiones solo con base en la información disponible en forma local.
La información relevante se distribuye entre varias máquinas.
9.1 INTRODUCCION A LA SINCRONIZACION EN SISTEMAS DISTRIBUIDOS
Además de la comunicación, es fundamental la forma en que los procesos
