Mantenimiento de los relojes lógicos
Relojes lógicos totalmente ordenados Los relojes lógicos de Lamport imponen sólo una relación de orden parcial: Eventos de distintos procesos pueden tener asociado una misma marca de tiempo. Se puede extender la relación de orden para conseguir una relación de orden total añadiendo el nº de proceso (Ta, Pa): marca de tiempo del evento a del proceso P (Ta, Pa) < (Tb, Pb) sí y solo si Ta < Tb o Ta=Tb y Pa< Pb
Problemas de los relojes lógicos No bastan para caracterizar la causalidad Dados RL(a) y RL(b) no podemos saber: si a precede a b si b precede a a si a y b son concurrentes Se necesita una relación (F(e), < ) tal que: a Y b si y sólo si F(a) < F(b) Los relojes vectoriales permiten representar de forma precisa la relación de causalidad potencial
Relojes vectoriales Desarrollado independientemente por Fidge, Mattern y Schmuck Todo proceso lleva asociado un vector de enteros RV RVi[a] es el valor del reloj vectorial del proceso i cuando ejecuta el evento a. Mantenimiento de los relojes vectoriales Inicialmente RVi= 0 Cuando un proceso i genera un evento RVi[i ] = RVi[i ] +1 Todos los mensajes llevan el RV del envío Cuando un proceso j recibe un mensaje con RV RVj = max(RVj , RV ) (componente a componente) RVj[j ] = RVj[j ] +1 (evento de recepción)
Relojes vectoriales
Propiedades de los relojes vectoriales RV < RV´ si y solo si RV RV´ y RV[i ] ? RV´[i ], ? i Dados dos eventos a y b a precede a b si y solo si RV(a) < RV(b) Si a es un evento del proceso i y b es un evento del proceso j (con i ? j) a precede a b si y solo si RV(a)[i ] ? RV(b)[i ] RV(a)[i ] = RV(b)[i ] cuando a es el evento de envío a j y b es el evento de recepción. a y b son concurrentes si y solo si RV(a)[i ] > RV(b)[i ] y RV(b )[j ] > RV(b)[j ]
Exclusión mutua distribuida Los procesos ejecutan el siguiente fragmento de código entrada() SECCIÓN CRÍTICA salida() Requisitos para resolver el problema de la sección crítica Exclusión mutua Progreso Espera acotada Algoritmos Algoritmo centralizado Algoritmo distribuido Anillo con testigo
Algoritmo centralizado Existe un proceso coordinador
Anillo con testigo Los procesos se ordenan conceptualmente como un anillo. Por el anillo circula un testigo. Cuando un proceso quiere entrar en la SC debe esperar a recoger el testigo Cuando sale de la SC envía el testigo al nuevo proceso del anillo
Algoritmo distribuido Algoritmo de Ricart y Agrawala requiere la existencia un orden total de todos los mensajes en el sistema Un proceso que quiere entrar en una sección crítica (SC) envía un mensaje a todos los procesos (y a él mismo) Cuando un proceso recibe un mensaje Si el receptor no está en la SC ni quiere entrar envía OK al emisor Si el receptor ya está en la SC no responde Si el receptor desea entrar, compara la marca de tiempo del mensaje. Si el mensaje tiene una marca menor envía OK. En caso contrario entra y no envía nada. Cuando un proceso recibe todos los mensajes puede entrar
Contenido Sistemas distribuidos Sistemas operativos distribuidos Comunicación de procesos Sincronización de procesos Gestión de procesos Sistemas de archivos Gestión de memoria
Modelos de sistema Conjunto de estaciones de trabajo El sistema consta de estaciones de trabajo a las que tienen acceso los usuarios. Pool de procesadores Los usuarios con terminales. Los procesos se envían a procesadores de un pool. Modelo híbridos Trabajos interactivos en las estaciones de trabajo. Trabajos no interactivos en en el pool de procesadores.
Asignación de procesadores Objetivo: decidir en qué procesador se debería ejecutar un proceso para equilibrar la carga y optimizar el rendimiento. Evitar que un nodo esté inactivo mientras hay procesos esperando a ejecutar. Suposiciones: Todos los procesadores son compatible en el código. La velocidad de los procesadores puede ser distinta. Conectividad total: cualquier procesador puede comunicarse con cualquier otro.
Estaciones de trabajo inactivas En entornos típicos con estaciones de trabajo se desperdicia cerca del 80% de ciclos totales de CPU. Uso de estaciones de trabajo inactivas: Ejecutar procesos de forma totalmente transparente en máquinas remotas que se encuentran inactivas . Los usuarios de las estaciones de trabajo inactivas no deberían observar una degradación del rendimiento como consecuencia de la ejecución de procesos remotos.
Empleo de estaciones de trabajo inactivas ¿Qué es una estación de trabajo inactiva? Una que lleva varios minutos sin recibir entrada del teclado o ratón y que no está ejecutando procesos interactivos. ¿Cómo localizar estaciones inactivas? Dirigidas por el servidor: la estación inactiva anuncia su disponibilidad. Dirigida por el cliente: un cliente envía un mensaje al resto para localizar una estación inactiva.
Estrategias para localizar una estación inactiva
Algoritmos de distribución de la carga Política de transferencia: determina cuando transferir. Política de selección: selecciona el proceso a transferir. Política de ubicación: selecciona el nodo al que transferir. Política de información: decide cuándo, desde dónde y qué información sobre otros nodos recoger.
Planificación de procesos en sistemas distribuidos Definición del problema: Dado un conjunto de tareas con ciertas restricciones de precedencia y requisitos de cálculo y comunicación, Dado un conjunto de procesadores conectados por una red de interconexión, Encontrar la asignación de tareas a procesadores y el orden de ejecución con el objetivo de minimizar el tiempo de ejecución total.
Planificación de procesos
Complejidad del problema El problema en su forma general es NP-completo Algoritmos con complejidad polinomial: Cuando sólo hay dos procesadores. En el caso general se utilizan heurísticas. Los planificadores se eligen por 2 métricas: El rendimiento del plan generado. La eficacia del planificador: tiempo tomado por el planificador para generar un plan.
Contenido Sistemas distribuidos Sistemas operativos distribuidos Comunicación de procesos Sincronización de procesos Gestión de procesos Sistemas de archivos Gestión de memoria
Sistema de archivos distribuido Objetivo principal: compartir datos entre usuarios ofreciendo transparencia Objetivos secundarios: rendimiento (debería ser comparable al de un sistema tradicional) tolerancia a fallos disponibilidad
Componentes Servicio de directorio: Gestión de los nombres de los archivos Objetivo: ofrecer un espacio de nombres único Servicio de archivos: Proporciona acceso a los datos de los archivos
Métodos de accesos remotos Modelo carga/descarga Transferencias completas del fichero Localmente se almacenan en memoria o discos locales Normalmente utilizan semántica de sesión Eficiencia en las transferencias Llamada open con mucha latencia Múltiples copias de un fichero Modelo de servicios remotos El servidor debe proporcionar todas las operaciones sobre el fichero. Acceso por bloques Modelo cliente/servidor Empleo de cache en el cliente Combina los dos modelos anteriores.
Tipos de servidores Servidores con estado Cuando se abre un fichero, el servidor almacena información y da al cliente un identificador único a utilizar en las posteriores llamadas Cuando se cierra un fichero se libera la información Servidores sin estado Cada petición es autocontenida (fichero y posición)
Tipos de servidores II Ventajas de los servidores con estado Mensajes de petición más cortos Mejor rendimiento (se mantiene información en memoria) Facilita la lectura adelantada. El servidor puede analizar el patrón de accesos que realiza cada cliente Es necesario en invalidaciones iniciadas por el servidor Ventajas de los servidores sin estado Más tolerante a fallos No son necesarios open y close. Se reduce el nº de mensajes No se gasta memoria en el servidor para almacenar el estado
Cache de bloques El empleo de cache de bloques permite mejorar el rendimiento Explota el principio de proximidad de referencias Proximidad temporal Proximidad espacial Lecturas adelantadas Mejora el rendimiento de las operaciones de lectura, sobre todo si son secuenciales Escrituras diferidas Mejora el rendimiento de las escrituras Otros tipos de cache Cache de nombres Cache de metadatos del sistema de ficheros
Localización de las cache en un SFD Cache en los servidores Reducen los accesos a disco Cache en los clientes Reducen el tráfico por la red Reducen la carga en los servidores Mejora la capacidad de crecimiento Dos posibles localizaciones En discos locales Más capacidad, Más lento No volátil, facilita la recuperación En memoria principal Menor capacidad Más rápido Memoria volátil
Tamaño de la unidad de cache Mayor tamaño puede incrementar la tasa de aciertos y mejorar la utilización de la red pero Aumentan los problemas de coherencia Depende de las características de las aplicaciones En memoria cache grandes Es beneficioso emplear bloques grandes (8 KB y más) En memorias pequeñas El uso de bloques grandes es menos adecuado
Políticas de actualización Escritura inmediata (write-through) Buena fiabilidad En escrituras se obtiene el mismo rendimiento que en el modelo de accesos remotos Las escrituras son más lentas Escritura diferida (write-back) Escrituras más rápidas. Se reduce el tráfico en la red Los datos pueden borrarse antes de ser enviados al servidor Alternativas Volcado (flush) periódico (Sprite) Write-on-close
Problema de la coherencia de cache El uso de cache en los clientes de un sistema de ficheros introduce el problema de la coherencia de cache: Múltiples copias. El problema surge cuando se coutiliza un fichero en escritura: Coutilización en escritura secuencial Típico en entornos y aplicaciones distribuidas. Coutilización en escritura concurrente Típico en aplicaciones paralelas.
Soluciones al problema de la coherencia No emplear cache en los clientes. Solución trivial que no permite explotar las ventajas del uso de cache en los clientes (reutilización, lectura adelantada y escritura diferida) No utilizar cache en los clientes para datos compartidos en escritura (Sprite). Accesos remotos sobre una única copia asegura semántica UNIX Mecanismos de cache sin replicación de datos Basado en esquemas cooperativos que definen un único espacio global formado por la unión de todas las cache del sistema. Los datos fluyen a través de las caches sin replicación Empleo de protocolos de coherencia de cache
Contenido Sistemas distribuidos Sistemas operativos distribuidos Comunicación de procesos Sincronización de procesos Gestión de procesos Sistemas de archivos Gestión de memoria
Uso de paginadores externos
Memoria compartida distribuida
Características Se construye utilizando paso de mensajes. Modelo de programación más sencillo, no es necesario el paso de mensajes. Sincronización utilizando construcciones tradicionales (semáforos, mutex, …). ¿Rendimiento? Los accesos a memoria no son siempre locales Modelos: Basado en hardware (arquitectura NUMA). Basado en páginas. Basado en objetos
Implementación Replicación y caching (igual que los sistemas de ficheros) Las escrituras se realizan localmente Aparece un problema en el acceso a variables compartidas (en escritura). Problema idéntico a la coherencia de cache
| Página siguiente |