Where to next?
Where to next?
Before finalizing your proposal, check through it again to ensure that all the information you are providing supports the objectives you originally set out and is relevant from the reader's point of view.
When you have gathered most of the material for your proposal, you can transfer it to a linear document for presentation. You can do this in Mindomo by converting topics into text in the topic notes for export to a linear document.
Good luck with your proposal!
Sincronización en Sistemas
Distribuidos
What is your business proposal about?
Give it a name. Type it in.
Algoritmos de Elección
Las técnicas de sincronización ya vistas son de bajo nivel
• El programador debe enfrentarse directamente con los detalles de:
— La exclusión mutua.
— El manejo de las regiones críticas.
— La prevención de bloqueos.
— La recuperación de fallas.
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:
• Construye un mensaje elección con su propio número de proceso.
• Envía el mensaje a su sucesor.
El Algoritmo del Grandulón o de García-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:
• Envía un mensaje elección a los demás procesos con un número mayor.
• Si nadie responde asume que gana la elección y se convierte en el nuevo coordinador.
• Si un proceso con un número mayor responde, toma el control y el trabajo de “P” termina. Envía de regreso un mensaje o.k. al emisor para indicar que está vivo y que tomará
el control.
• Realiza una elección salvo que ya esté haciendo alguna.
Son los algoritmos para la elección de un proceso coordinador, iniciador, secuenciador, etc.
Transacciones Atómicas
Las técnicas de sincronización ya vistas son de bajo nivel [25, Tanenbaum]:
• El programador debe enfrentarse directamente con los detalles de:
— La exclusión mutua.
— El manejo de las regiones críticas.
— La prevención de bloqueos.
— La recuperación de fallas. Se precisan técnicas de abstracción de mayor nivel que:
• Oculten estos aspectos técnicos.
• Permitan a los programadores concentrarse en los algoritmos y la forma en que los
procesos trabajan juntos en paralelo.
Tal abstracción la llamaremos transacción atómica, transacción o acción atómica.
La principal propiedad de la transacción atómica es el “todo o nada”:
El Modelo de Transacción
Describe the further actions for a commercial and a non-commercial proposal.
What are the next steps?
Transacciones Anidadas
Se presentan cuando las transacciones pueden contener subtransacciones (procesos hijos)
que:
• Se ejecuten en paralelo entre sí en procesadores distintos.
• Pueden originar nuevas subtransacciones.
Propiedades de las Transacciones
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:
— Para cada una de ellas y para los demás procesos.
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.
La permanencia se refiere a que una vez comprometida una transacción:
• Sigue adelante y los resultados son permanentes.
Primitivas de Transacción
Deben ser proporcionadas por el sistema operativo o por el sistema de tiempo de ejecución
del lenguaje.
Ejemplos:
• Begin_transaction: los comandos siguientes forman una transacción.
• End_transaction: termina la transacción y se intenta un compromiso.
• Abort_transaction: se elimina la transacción; se recuperan los valores anteriores.
• Read: se leen datos de un archivo (o algún otro objeto).
• Write: se escriben datos en un archivo (o algún otro objeto).
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.
Cuando se actualiza un bloque:
• Primero se actualiza y verifica el bloque de la unidad 1.
• Luego se actualiza y verifica el bloque de la unidad 2.
Supondremos que :
• El sistema consta de varios procesos independientes que pueden fallar aleatoriamente.
• El software subyacente maneja transparentemente los errores de comunicación.
Add delivery details for a commercial proposal.
Implantación del Modelo de Transacción
Do you need a glossary for any specific technical terms you are using?
Protocolo de Compromiso de Dos Fases (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 mensaje para que estén preparados para el compromiso.
Cuando un subordinado recibe el mensaje:
• Verifica si está listo para comprometerse.
• Escribe una entrada en la bitácora.
• Envía de regreso su decisión.
Bitácora de Escritura Anticipada
Este método también se denomina lista de intenciones.
Los archivos realmente se modifican pero antes de cambiar cualquier bloque:
• 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.
Espacio de Trabajo Particular
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).
Cuando se abre un archivo para escritura:
• Se lo localiza de manera similar que para lectura.
• Se copia en primer lugar al espacio de trabajo particular:
— Una optimización consiste en copiar solo el índice del archivo en el espacio de
trabajo particular:
∗ El índice es el bloque de datos asociado a cada archivo e indica la localización de sus bloques en el disco.
∗ Es el nodo-i correspondiente.
Existen varios métodos de implantación
Add a term.
Control de Concurrencia en el Modelo de Transacción
Include any detailed data in appendices rather than break up the flow of the proposal.
Identify the contents of an appendix for your proposal.
Resumen
Los diferentes esquemas ofrecen distintas ventajas pero el problema principal es la gran
complejidad de su implantación.
Marcas de Tiempo
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.
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:
• Una transacción iniciada posteriormente ha accedido al archivo y ha efectuado un
compromiso.
• La transacción activa se ha realizado tarde y se aborta.
Control Optimista de la Concurrencia
• Se sigue adelante y se hace todo lo que se deba hacer, sin prestar atención a lo que
hacen los demás.
• Se actúa a posteriori si se presenta algún problema.
Se mantiene un registro de los archivos leídos o grabados.
En el momento del compromiso
Los algoritmos de control de concurrencia son necesarios cuando se ejecutan varias tran-
sacciones de manera simultánea [25, Tanenbaum]:
• En distintos procesos.
• En distintos procesadores.
Los principales algoritmos son:
• El de la cerradura.
• El del control optimista de la concurrencia.
• El de las marcas de tiempo.
Add an appendix.
Bloqueos en Sistemas Distribuidos
Son especialmente críticos en sistemas de bases de datos distribuidos.
Las estrategias usuales para el manejo de los bloqueos son:
• Algoritmo del avestruz:
— Ignorar el problema.
• Detección:
— Permitir que ocurran los bloqueos, detectarlos e intentar recuperarse de ellos.
• Prevención:
— Hacer que los bloqueos sean imposibles desde el punto de vista estructural.
• Evitarlos:
— Evitar los bloqueos mediante la asignación cuidadosa de los recursos.
9.13 Detección Distribuida de Bloqueos
9.13.2 Detección 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:
• Un proceso puede esperar a uno o más recursos simultáneamente.
• Los recursos que espera un proceso pueden ser locales o remotos (de otra máquina).
Si el proceso “0” se bloquea debido al proceso “1”:
9.13.1 Detección Centralizada de Bloqueos
La información de control se debe transmitir explícitamente, existiendo las siguientes
variantes:
• Cada máquina informa cada actualización al coordinador.
• Cada máquina informa periódicamente las modificaciones desde la última actualización.
• El coordinador requiere la información cuando la necesita.
La información de control incompleta o retrasada puede llevar a falsos bloqueos:
• El coordinador interpreta erróneamente que existe un bloqueo y elimina un proceso.
• Una posible solución es utilizar el algoritmo de Lamport para disponer de un tiempo global.
Cuando se detecta un bloqueo en un S. O. convencional se resuelve eliminando uno o más
procesos [25, Tanenbaum].
Cuando se detecta un bloqueo en un sistema basado en transacciones atómicas se
resuelve abortando una o más transacciones:
• El sistema restaura el estado que tenía antes de iniciar la transacción.
• La transacción puede volver a comenzar.
Las consecuencias de la eliminación de un proceso son mucho menos severas si se
utilizan las transacciones que en caso de que no se utilicen.
9.14Prevención Distribuida de Bloqueos
La prevención consiste en el diseño cuidadoso del sistema para que los bloqueos sean imposibles estructuralmente.
Entre las distintas técnicas se incluye:
• Permitir a los procesos que solo conserven un recurso a la vez.
• Exigir a los procesos que soliciten todos sus recursos desde un principio.
• Hacer que todos los procesos liberen todos sus recursos cuando soliciten uno nuevo.
En un sistema distribuido con tiempo global y transacciones atómicas:
• Se puede asociar a cada transacción una marca de tiempo global al momento de su inicio.
• No pueden haber parejas de transacciones con igual marca de tiempo asociada.
Exclusión Mutua
Un Algoritmo de Anillo de Fichas (Token Ring)
Los procesos se organizan por software formando un anillo lógico asignándose a cada proceso una posición en el anillo.
En caso negativo: La cantidad de tiempo entre las apariciones sucesivas de la ficha en la red no está
acotada, por ello es difícil decidir si está perdida o demorada en algún proceso que
no la libera.
La falla de un proceso es detectada cuando su vecino intenta sin éxito pasarle la ficha:
• Se lo debe eliminar del grupo y pasar la ficha al siguiente proceso activo.
• Todos los procesos deben mantener la configuración actual del anillo.
En caso positivo:
— El proceso entra a la región crítica, hace el proceso necesario y sale de ella.
— Después de salir pasa la ficha a lo largo del anillo:
∗ No se puede entrar a una segunda región crítica con la misma ficha (token o permiso).
Un Algoritmo Distribuido
El objetivo es no tener un único punto de fallo (el coordinador central).
Un ej. es el algoritmo de Lamport mejorado por Ricart y Agrawala.
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:
• Construye un mensaje con el nombre de la región crítica, su número de proceso y la hora actual.
• Envía el mensaje a todos los demás procesos y de manera conceptual a él mismo.
• Se supone que cada mensaje tiene un reconocimiento.
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. 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.
Cuando un proceso debe leer o actualizar ciertas estructuras de datos.
• 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.
En sistemas monoprocesadores las regiones críticas se protegen con semáforos, monitores y similares.
En sistemas distribuidos la cuestión es más compleja.
Algoritmos Para la Sincronización de Relojes
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.
Algoritmos con Promedio
Los anteriores son algoritmos centralizados.
Una clase de algoritmos descentralizados divide el tiempo en intervalos de resincronización de longitud fija: Al inicio de cada intervalo cada máquina transmite el tiempo actual según su reloj.
Debido a la diferente velocidad de los relojes las transmisiones no serán simultáneas.
Luego de que una máquina transmite su hora, inicializa un cronómetro local para reunir las demás transmisiones que lleguen en cierto intervalo “S”.
Algoritmo de Berkeley
En el algoritmo de Cristian el servidor de tiempo es pasivo.
En el algoritmo de Berkeley el servidor de tiempo:
• Es activo.
• Realiza un muestreo periódico de todas las máquinas para preguntarles el tiempo.
• Con las respuestas:
— Calcula un tiempo promedio.
— Indica a las demás máquinas que avancen su reloj o disminuyan la velocidad del mismo hasta lograr la disminución requerida.
Algoritmo de Cristian
Una máquina tiene un receptor UTC, por lo que se la llama despachador del tiempo.
• El objetivo es sincronizar todas las máquinas con ella.
Si ninguna máquina tiene un receptor de UTC:
• Cada máquina lleva el registro de su propio tiempo.
• Se debe mantener el tiempo de todas las máquinas tan cercano como sea posible.
Relojes Físicos
• Se deben conocer con precisión la posición relativa del emisor y del receptor:
— Se debe compensar el retraso de propagación de la señal.
— Si la señal se recibe por módem también se debe compensar por la ruta de la
señal y la velocidad del módem.
— Se dificulta la obtención del tiempo con una precisión extremadamente alta.
El algoritmo de Lamport proporciona un orden de eventos sin ambigüedades, pero:
• Los valores de tiempo asignados a los eventos no tienen porqué ser cercanos a los tiempos reales en los que ocurren.
• En ciertos sistemas (ej.: sistemas de tiempo real), es importante la hora real del reloj: Se precisan relojes físicos externos (más de uno).
— Se deben sincronizar:
- Con los relojes del mundo real.
- Entre sí.
Relojes Lógicos
Describe the current position that your client is in.
This creates some common ground, which is a good platform for discussing your solution.
Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo
reloj
• Habrá una pérdida de sincronía en los relojes (de software), es decir que tendrán valores distintos al ser leidos.
• Generalmente lo importante no es que los procesos estén de acuerdo en la hora, pero sí importa que coincidan en el orden en que ocurren los eventos
• Si 2 procesos no interactúan no es necesario que sus relojes estén sincronizados.
Lamport señaló que la sincronización de relojes no tiene que ser absoluta:
• Es imposible garantizar que los cristales de computadoras distintas oscilen con la misma frecuencia.
Para varias computadoras con sus respectivos relojes:
— Importan los tiempos relativos.
— Todos los procesos de la máquina usan el mismo reloj y tendrán consistencia interna.
No interesan pequeños desfasajes del reloj porque:
Sincronización de Relojes
Summarize your proposal at the beginning of the document. Add a sum-up.
Generalmente los algoritmos distribuidos tienen las siguientes propiedades
• La información relevante se distribuye entre varias máquinas.
• Los procesos toman las decisiones solo con base en la información disponible en forma local.
• Debe evitarse un único punto de fallo en el sistema.
• No existe un reloj común o alguna otra fuente precisa del tiempo global.
relojes puede ser drástica en procesos dependientes del tiempo.
• Se requiere un acuerdo global en el tiempo, pues la falta de sincronización en los
hora.
• En un sistema distribuido no es trivial poner de acuerdo a todas las máquinas en la
En un sistema centralizado el tiempo no es ambiguo.
Introducción a la Sincronización en Sistemas Distribui-
dos
What do you know about the client's requirements?
Is your proposal in response to an inquiry?
Has there been provided a Request for Proposal (RFP) or other resources that you can work with?
If you have relevant materials in other files, you can attach them to this topic.
This section should not be included in the proposal.
Además de la comunicación, es fundamental la forma en que los procesos.
• Cooperan.
• Se sincronizan entre sí.
