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 anterior | Volver al principio del trabajo | Página siguiente  |