+ Sistemas Distribuidos Coordinación y acuerdo Rodrigo Santamaría +Coordinación y acuerdo • Introducción • Exclusión mutua distribuida • Elección distribuida • Multidifusión • Consenso distribuido 2 + 3 Introducción  Hasta ahora hemos visto cómo  Comunicar procesos en distintos nodos: middleware  Sincronizar procesos en distintos nodos: tiempos lógicos  Con estas herramientas podemos plantearnos cómo  Coordinar procesos en distintos nodos ??? + 4 Introducción Asunciones  Sincronismo: asincronía  Fallos de proceso: los procesos no fallan  Fallos de comunicación: canales fiables  Los mensajes se terminan recibiendo  El fallo de un proceso no evita que el resto puedan comunicarse  En un sistema síncrono, además con un límite de tiempo Se harán siempre estas asunciones para cada solución discutida salvo que se indique lo contrario + 5 Introducción Objetivos  Dado un conjunto de procesos en un SD, vamos a necesitar  Coordinar sus acciones  Llegar a un acuerdo en uno o más valores  Formas de coordinación y acuerdo:  Acceso a recursos: exclusión mutua distribuida  Selección de valores: algoritmos de elección  Comunicación distribuida: algoritmos de multidifusión  Toma de decisiones: algoritmos de consenso +Coordinación y acuerdo • Introducción • Exclusión mutua distribuida • Elección distribuida • Multidifusión • Consenso distribuido 6 + 7 Exclusión mutua distribuida  Sección crítica (SC): porción de código que permite el acceso a un recurso compartido por varios procesos  Exclusión mutua: el acceso a la sección crítica se regula por medio de variables compartidas, por ejemplo semáforos  Exclusión mutua distribuida: el acceso a la sección crítica se basa en paso de mensajes + 8 Exclusión mutua distribuida Algoritmo básico entrarSC() // bloqueo del proceso si SC ocupada 1. accesoRecursos()// uso de recursos compartidos 2. salirSC() // liberación de procesos bloqueados 3. + 9 Exclusión mutua distribuida Requisitos  Seguridad  A lo sumo un proceso puede estar ejecutándose a la vez en la SC  Pervivencia  Las peticiones de entrada/salida de la SC al final son concedidas  Sin interbloqueos ni inanición  Ordenación  Si una petición para entrar en la SC ocurrió “antes que” otra, entonces la entrada en la SC se garantiza en ese orden RECUERDA: un evento sucede “antes que” otro si 1) ocurren en ese orden en el mismo proceso, o 2) es el envío correspondiente a una recepción Tema 5 (diap 28 y sigs.) + 10 Exclusión mutua distribuida Criterios de evaluación  Retraso de entrada  Cuánto tarda un proceso en entrar en la SC desde que lo solicita  Retraso en el “relevo”  Tiempo que pasa entre que un proceso sale de la SC y el siguiente que esté esperando entra  Ancho de banda consumido  Proporcional al número de mensajes enviados en cada operación de entrada y salida de la SC  En sistemas asíncronos, va a ser la medida del retraso