Exclusion mutua
Páginas: 43 (10610 palabras)
Publicado: 29 de junio de 2010
3 Sincronización distribuida
Contenido
3.1 3.2 Introducción Exclusión mutua distribuida Algoritmos centralizados Algoritmos distribuidos
3.2.1 3.2.2 3.3
Algoritmos de elección Algoritmo peleón (bully) Algoritmo del anillo
3.3.1 3.3.2 3.4
Comunicación a grupos Modelo de sistema Semánticas de difusión Gestión de la composición del grupo Ejemplos de sistemas para comunicación a grupos3.4.1 3.4.2 3.4.3 3.4.4 3.5
Replicación Modelo Criterios de consistencia Técnicas de replicación
3.5.1 3.5.2 3.5.3 3.6
Transacciones distribuidas Ejecución de transacciones distribuidas Acuerdo atómico Mecanismos de recuperación
3.6.1 3.6.2 3.6.3 3.7 3.8
El problema del consenso Ejercicios
Sistemas Distribuidos
Sincronización distribuida
3.2
3.1 Introducción
En elcapítulo precedente hemos tratado los problemas y los conceptos fundamentales relacionados con la gestión del estado global en un sistema distribuido. Comprobamos que las limitaciones prácticas en la sincronización de los relojes locales nos llevaba a considerar un modelo de tiempo lógico que permite expresar la causalidad entre eventos y a introducir una definición de estado global consistente apartir del concepto de corte. Sobre esta base vamos a describir aquí una serie de problemas de sincronización que plantean las aplicaciones distribuidas. • Exclusión mutua. El acceso exclusivo a recursos compartidos, un problema clásico de sincronización en sistemas centralizados, cuando se traslada a un sistema distribuido requiere un nuevo enfoque, que implica comunicar a los procesosinvolucrados para acordar el orden de acceso. Elección. La figura de un proceso coordinador o líder es frecuente en sistemas distribuidos. La posibilidad de fallo del coordinador hace necesarios mecanismos que permitan la promoción de un proceso como nuevo coordinador, lo que implica detectar el fallo del coordinador y la elección de uno nuevo. Comunicación a grupos. El multicast o difusión de mensajes a ungrupo de procesos requiere definir criterios de fiabilidad y orden en la entrega de mensajes e implementar algoritmos que los garanticen. Servicios replicados. Cuando un conjunto de servidores redundantes tratan de proporcionar tolerancia a fallos o alta disponibilidad, se requieren modelos que proporcionen la consistencia adecuada para la actualización de las réplicas y para la gestión de lasaltas y bajas. Transacciones distribuidas. En sistemas de reserva o bancarios, la actualización del estado distribuido mediante una operación que involucra a varios procesos (transacción) debe preservar invariantes que implican el acuerdo entre los procesos sobre el resultado de la operación.
•
•
•
•
Aunque las aplicaciones relacionadas aparentan ser de distinta naturaleza, coincidenen cuanto al contexto (procesos que actualizan el estado global distribuido y que están sujetos a fallo) y en cuanto al objetivo (la coordinación entre los procesos para una actualización consistente del estado global). [COU05] es la referencia más general para este tema.
Alberto Lafuente, Departamento de Arquitectura y Tecnología de Computadores, UPV/EHU
Sistemas DistribuidosSincronización distribuida
3.3
3.2 Exclusión mutua distribuida
De uso más limitado que en los sistemas operativos centralizados, la exclusión mutua es necesaria en sistemas distribuidos para resolver situaciones particulares en el acceso a recursos compartidos, como en sistemas de ficheros distribuidos (por ejemplo, en NFS1), memoria compartida distribuida, y entrada/salida (por ejemplo, sistemas deventanas). Los algoritmos de exclusión mutua distribuida pueden ser centralizados o distribuidos.
3.2.1
Algoritmos centralizados
Se basan en la existencia de un proceso coordinador de la sección crítica, que gestiona peticiones de entrar y dejar la sección crítica. • Petición de entrar a la sección crítica: − Si está libre, el coordinador responde con un mensaje de confirmación. − Si...
Contenido
3.1 3.2 Introducción Exclusión mutua distribuida Algoritmos centralizados Algoritmos distribuidos
3.2.1 3.2.2 3.3
Algoritmos de elección Algoritmo peleón (bully) Algoritmo del anillo
3.3.1 3.3.2 3.4
Comunicación a grupos Modelo de sistema Semánticas de difusión Gestión de la composición del grupo Ejemplos de sistemas para comunicación a grupos3.4.1 3.4.2 3.4.3 3.4.4 3.5
Replicación Modelo Criterios de consistencia Técnicas de replicación
3.5.1 3.5.2 3.5.3 3.6
Transacciones distribuidas Ejecución de transacciones distribuidas Acuerdo atómico Mecanismos de recuperación
3.6.1 3.6.2 3.6.3 3.7 3.8
El problema del consenso Ejercicios
Sistemas Distribuidos
Sincronización distribuida
3.2
3.1 Introducción
En elcapítulo precedente hemos tratado los problemas y los conceptos fundamentales relacionados con la gestión del estado global en un sistema distribuido. Comprobamos que las limitaciones prácticas en la sincronización de los relojes locales nos llevaba a considerar un modelo de tiempo lógico que permite expresar la causalidad entre eventos y a introducir una definición de estado global consistente apartir del concepto de corte. Sobre esta base vamos a describir aquí una serie de problemas de sincronización que plantean las aplicaciones distribuidas. • Exclusión mutua. El acceso exclusivo a recursos compartidos, un problema clásico de sincronización en sistemas centralizados, cuando se traslada a un sistema distribuido requiere un nuevo enfoque, que implica comunicar a los procesosinvolucrados para acordar el orden de acceso. Elección. La figura de un proceso coordinador o líder es frecuente en sistemas distribuidos. La posibilidad de fallo del coordinador hace necesarios mecanismos que permitan la promoción de un proceso como nuevo coordinador, lo que implica detectar el fallo del coordinador y la elección de uno nuevo. Comunicación a grupos. El multicast o difusión de mensajes a ungrupo de procesos requiere definir criterios de fiabilidad y orden en la entrega de mensajes e implementar algoritmos que los garanticen. Servicios replicados. Cuando un conjunto de servidores redundantes tratan de proporcionar tolerancia a fallos o alta disponibilidad, se requieren modelos que proporcionen la consistencia adecuada para la actualización de las réplicas y para la gestión de lasaltas y bajas. Transacciones distribuidas. En sistemas de reserva o bancarios, la actualización del estado distribuido mediante una operación que involucra a varios procesos (transacción) debe preservar invariantes que implican el acuerdo entre los procesos sobre el resultado de la operación.
•
•
•
•
Aunque las aplicaciones relacionadas aparentan ser de distinta naturaleza, coincidenen cuanto al contexto (procesos que actualizan el estado global distribuido y que están sujetos a fallo) y en cuanto al objetivo (la coordinación entre los procesos para una actualización consistente del estado global). [COU05] es la referencia más general para este tema.
Alberto Lafuente, Departamento de Arquitectura y Tecnología de Computadores, UPV/EHU
Sistemas DistribuidosSincronización distribuida
3.3
3.2 Exclusión mutua distribuida
De uso más limitado que en los sistemas operativos centralizados, la exclusión mutua es necesaria en sistemas distribuidos para resolver situaciones particulares en el acceso a recursos compartidos, como en sistemas de ficheros distribuidos (por ejemplo, en NFS1), memoria compartida distribuida, y entrada/salida (por ejemplo, sistemas deventanas). Los algoritmos de exclusión mutua distribuida pueden ser centralizados o distribuidos.
3.2.1
Algoritmos centralizados
Se basan en la existencia de un proceso coordinador de la sección crítica, que gestiona peticiones de entrar y dejar la sección crítica. • Petición de entrar a la sección crítica: − Si está libre, el coordinador responde con un mensaje de confirmación. − Si...
Leer documento completo
Regístrate para leer el documento completo.