作者：EDWIN RODRIGUEZ 5 年以前
447
SINCRONIZACION EN SISTEMAS DISTRIBUIDOS
作者：EDWIN RODRIGUEZ 5 年以前
447
更多类似内容
由karoll ibeth perez moreno
由Lina Isaza
由Tania Huerta
由Dublas Muñoz
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.
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.
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.
Evitar los bloqueos mediante la asignación cuidadosa de los recursos.
Hacer que los bloqueos sean imposibles desde el punto de vista estructural.
Permitir que ocurran los bloqueos, detectarlos e intentar recuperarse de ellos.
Ignorar el problema.
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.
Si esto no ocurre se realiza el compromiso.
Si esto ocurre la transacción aborta.
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.
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.
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.
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.
Pueden originar nuevas subtransacciones.
Se ejecuten en paralelo entre sí en procesadores distintos.
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:
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.
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.
La recuperación de fallas.
La prevención de bloqueos.
El manejo de las regiones críticas.
La exclusión mutua.
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.
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.
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.
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.
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
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.
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”.
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.
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.
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.).
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
