Memoria Compartida DistribuidaLos sistemas de memoria compartida distribuida (DSM) representan la creacin hibrida de dos tipos de computacin paralelos: la memoria distribuida en sistemas multiprocesador y los sistemas distribuidos. Ellos proveen la abstraccin de memoria compartida en sistemas con memorias distribuidas fsicamente y consecuentemente combinan las mejores caractersticas de ambos enfoques. Debido a esto, el concepto de memoria compartida distribuida es reconocido como uno de los enfoques mas atractivos para la creacin de sistemas escalables, de alto rendimiento de sistemas multiprocesador.La memoria compartida distribuida (DSM) es una abstraccin utilizada para compartir datos entre computadores que no comparten memoria fsica. Los procesos acceden a DSM para leer y actualizar, dentro de sus espacios de direcciones, sobre lo que aparenta ser la memoria interna normal asignada a un proceso. Sin embargo, existe un sistema subyacente en tiempo de ejecucin que asegura de forma transparente que procesos diferentes ejecutndose en computadores diferentes observen las actualizaciones realizadas entre ellas. Es como si 1os procesos accedieran a una nica memoria compartida, pero de hecho la memoria fsica est distribuidaLa principal caracterstica de DSM es que ahorra al programador todo lo concerniente al paso de mensajes al escribir sus aplicaciones, cuestin que en otro sistema debera tenerse muy presente. DSM es fundamentalmente una herramienta para aplicaciones paralelas o para aplicaciones o grupos de aplicaciones distribuidas en las que se puede acceder directamente a datos individuales que ellas comparten. En general, DSM es menos apropiado para sistemas cliente-servidor, ya que los clientes ven al servidor como un gestor de recursos en forma de datos abstractos que se acceden a travs de peticiones (por razones de modularidad y proteccin). Sin embargo, los servidores pueden proporcionar DSM compartido entre los clientes. Por ejemplo, los archivos plasmados en memoria (memory mapped) que son compartidos y sobre los que se gestiona un cierto grado de consistencia son una forma de DSM

Configuraciones Memoria Compartida Distribuida

Los sistemas de memoria compartida distribuida (DSM) representan la creacin hibrida de dos tipos de computacin paralelos: la memoria distribuida en sistemas multiprocesador y los sistemas distribuidos. Ellos proveen la abstraccin de memoria compartida en sistemas con memorias distribuidas fsicamente y consecuentemente combinan las mejores caractersticas de ambos enfoques. Debido a esto, el concepto de memoria compartida distribuida es reconocido como uno de los enfoques mas atractivos para la creacin de sistemas escalables, de alto rendimiento de sistemas multiprocesador

De Circuitos Basados en Bus, anillo o con conmutadorMultiprocesadores basados en un bus.

Para evitar que dos o ms CPUs intenten el acceso a la memoria al mismo tiempo, se necesita algn tipo de arbitraje del bus. El CPU debe pedir permiso para conseguir el bus. La concesin puede hacerse de forma centralizada, utilizando un dispositivo de arbitraje de bus, o de forma descentralizada, donde el primer CPU que realice una solicitud en el bus ganar cualquier conflicto.La desventaja es la sobrecarga del bus.Una solucin sera equipar a cada CPU con un cach husmeador.Un protocolo en particular comn es el de escritura a travs del cach. Cuando un CPU lee por primera vez una palabra de memoria, esa palabra es llevada por el bus y guardada en el cach del CPU solicitante.Puede suceder que una palabra en particular se oculte en dos o ms CPU al mismo tiempo.

Operacin de lectura. Si la palabra no esta en el cach, entonces buscarla en la memoria y copiarla a su cach. Si la palabra esta en el cach, tomar el dato de ah. Operacin de escritura Si ningn CPU tiene la palabra en su cach, entonces la palabra es actualizada en memoria, como si el ocultamiento no hubiera sido utilizado. Si el CPU (que realiza la escritura) tiene la nica copia de la palabra, se actualiza su cach y tambin la memoria mediante el bus. Si dos o ms CPU tienen la palabra, entonces se actualiza la palabra en el cach y en la memoria, y se invalidan las entradas de esa palabra en los cahs de los otros CPU. As la palabra slo la tendr la memoria y un colo cach.Una alternativa a invalidar otras entradas de cach es actualizarlas todas, pero esto puede resultar ms lento. Una ventaja de este protocolo es que es fcil de entender e implantar, la desventaja es que todas las escrituras utilizan el bus. Existe otro tipo de protocolos como el protocolo de membresa. Una versin de este protocolo plantea lo siguiente. Se manejan bloques de cach, cada uno de los cuales puede estar en uno de los siguientes estados:

1. INVALIDO: Este bloque de cach no contiene datos vlidos.2. LIMPIO: La memoria est actualizada, el bloque puede estar en otros cachs.3. SUCIO: La memoria es incorrecta; ningn otro cach puede contener al bloque.La palabra permanece el estado SUCIO hasta que se elimine del cach donde se encuentra en la actualidad por razones de espacio. En este momento, desaparece de todos los cachs y se escribe en la memoria. Este protocolo tiene tres propiedades importantes:

1. La consistencia se logra haciendo que todos los cachs husmeen el bus.2. El protocolo se integra dentro de la unidad de administracin de memoria.3. Todo el algoritmo se realiza en un ciclo de memoria.

La desventaja es que no funciona para multiprocesadores de mayor tamao y nada es vlido para la memoria compartida distribuida.

Multiprocesadores basados en un anillo

Ejemplo: MemnetEn Memnet, un espacio de direcciones se divide en una parte privada y una compartida. La parte compartida se divide en bloques de 32 bytes, unidad mediante la cual se realizan las transferencias entre las mquinas. Las mquinas Memnet estn conectadas mediante un anillo de fichas modificado. El anillo consta de 20 cables paralelos, que juntos permiten enviar 16 bits de datos y 4 bits de control cada 100 nanosegundos, para una velocidad de datos de 160 Mb/seg. Un bloque exclusivo de lectura puede estar presente en varias mquinas, uno de lectura-escritura debe estar presente en una sola mquina.Los bits en el dispositivo Memnet indican uno o ms de los siguientes estados:

1. VALIDO: El bloque esta presente en el cach y est actualizado.2. EXCLUSIVO: La copia local es la nica.3. ORIGEN: Se activa si sta es la mquina origen del bloque.4. INTERRUPCION: Se utiliza para forzar interrupciones.5. POSICION: Indica la localizacin del bloque en el cach si esta presente y es vlido.6. Protocolo Memnet.7. Lectura.

Cuando un CPU desea leer una palabra de la memoria compartida, la direccin de memoria por leer se transfiere al dispositivo Memnet, el cual verifica la tabla del bloque para ver si est presente. Si es as, la solicitud es satisfecha de inmediato. En caso contrario, el dispositivo Memnet espera hasta capturar la ficha que circula; despus, coloca un paquete de solicitud en el anillo y suspende el CPU. El paquete de solicitud contiene la direccin deseada y un campo vaco de 32 bytes.Cada dispositivo Memnet en el anillo verifica si tiene el bloque. De ser as, coloca el bloque en el campo vaco y modifica el encabezado del paquete para inhibir la accin de las mquinas posteriores.Si el bit exclusivo del bloque est activo, se limpia. Cuando el paquete regresa al emisor, se garantiza que contiene al bloque solicitado. El CPU que enva la solicitud guarda el bloque, satisface la solicitud y libera al CPU.Si la mquina solicitante no tiene espacio libre en su cach para contener el bloque recibido, entonces toma al azar un bloque oculto y lo enva a su origen, con lo que libera un espacio de cach. Los bloques cuyo bit origen estn activados nunca se eligen, pues se encuentran en su origen.

Escritura.

Tenemos tres casos:A. Si el bloque contiene la palabra por escribir est presente y es la nica copia en el sistema, (el bit exclusivo esta activado) la palabra solo se escribe de manera local.B. Si esta presente el bloque, pero no es la nica copia, se enva primero un paquete de invalidacin por el anillo para que las otras mquinas desechen sus copias del bloque por escribir. Cuando el paquete de invalidacin regresa al solicitante, el bit exclusivo se activa para ese bloque y se procede a la escritura local.C. Si el bloque no est presente, se enva un paquete que combina una solicitud de lectura y una de invalidacin. La primera mquina que tenga el bloque lo copia en el paquete y desecha su copia. Todas las mquinas posteriores solo desechan el bloque de sus cachs. Cuando el paquete regresa al emisor, ste lo guarda y escribe en l.

La ventaja de este protocolo es que se puede aplicar a multicomputadoras.Principales Aproximaciones a DSMExisten tres aproximaciones a la implementacin de memoria compartida distribuida, las cuales involucran el uso de hardware, memoria virtual o bibliotecas de soporte. Estos no son mutuamente exclusivas necesariamente.Basada en hardware. Por ejemplo Dash y PLUS. El conjunto de procesadores y los mdulos de memoria estn conectados va una red de alta velocidad. El problema es la escalabilidad.Basado en pginas. Por ejemplo Ivy, Munin, Mirage, Clouds, Choices, COOL y Mether, todas implanta DSM como una regin de memoria virtual que ocupa el mismo rango de direccin en el espacio de direcciones de cada proceso participante. En cada caso el kernel mantiene la consistencia de datos dentro de las regiones DSM como parte del manejo de fallo de pgina

4.2 Modelos de ConsistenciaUn modelo de consistencia es esencialmente un contrato entre procesos y el almacenamiento de datos. Es decir: si los procesos acuerdan obedecer ciertas reglas, el almacenamiento promete trabajar correctamente.Normalmente un proceso que realiza una operacin de lectura espera que esa operacin devuelva un valor que refleje el resultado de la ltima operacin de escritura sobre el dato.EnInformtica, en unsistema distribuido, tales como unamemoria compartida distribuidao almacenes de datos distribuido, tales como unabase de datos,sistema de archivos,cach webo sistemas de replicacin optimista, hay una serie de posibles modelos de consistencia de datos. Se dice que un sistema soporta un determinado modelo, si las operaciones en memoria siguen normas especficas. La consistencia de los datos es definida entre el programador y el sistema, que garantiza que si el programador sigue las reglas, la memoria ser consistente y el resultado de las operaciones de memoria ser predecible.

Los lenguajes de alto nivel, tales comoC,C++yJava, respetan parcialmente este modelo traduciendo operaciones de memoria en operaciones de bajo nivel para preservar la memoria semntica. Para mantener el modelo, los compiladores pueden reordenar algunas instrucciones de memoria, y las llamadas a las bibliotecas como pthread_mutex_lock(), encapsular la sincronizacin necesaria.

Los ejemplos incluyen:

Linealizable (tambin conocido como el estricta o consistencia atmica) Consistencia secuencial Consistencia de causalidad Consistencia liberada Consistencia eventual Consistencia delta Consistencia PRAM (tambin conocido como consistencia FIFO) Consistencia dbil Consistencia vector campo

La duplicidad de los bloques compartidos aumenta el rendimiento, pero produce un problema de consistencia entre las diferentes copias de la pgina en caso de una escritura.Si con cada escritura es necesario actualizar todas las copias, el envo de las pginas por la red provoca que el tiempo de espera aumente demasiado, convirtiendo este mtodo en impracticable

4.2.1 Estricta Causal Secuencial Debil, de liberacin y de entradaConsistencia CasualLa condicin a cumplir para que unos datos sean causalmente consistentes es: Escrituras que estn potencialmente relacionadas en forma causal deben ser vistas por todos los procesos en el mismo orden. Escrituras concurrentes pueden ser vistas en un orden diferente sobre diferentes mquinas.Es permitida con un almacenamiento causalmente consistente, pero no con un almacenamiento secuencialmente consistente o con un almacenamiento consistente en forma estricta.

Consistencia SecuencialLa consistencia secuencial es una forma ligeramente ms dbil de la consistencia estricta. Satisface la siguiente condicin:El resultado de una ejecucin es el mismo si las operaciones (lectura y escritura) de todos los procesos sobre el dato fueron ejecutadas en algn orden secuencial Un dato almacenado secuencialmente consistente. Un dato almacenado que no es secuencialmente consistente.

Consistencia DbilLos accesos a variables de sincronizacin asociadas con los datos almacenados son secuencialmente consistentes.

Propiedades No se permite operacin sobre una variable de sincronizacin hasta que todas las escrituras previas de hayan completado. No se permiten operaciones de escritura o lectura sobre datos hasta que no se hayan completado operaciones previas sobre variables de sincronizacin. Consistencia de LiberacinSe basa en el supuesto de que los accesos a variables compartidas se protegen en secciones crticas empleando primitivas de sincronizacin, como por ejemplo locks. En tal caso, todo acceso esta precedido por una operacin adquiere y seguido por una operacin release. Es responsabilidad del programador que esta propiedad se cumpla en todos los programas.

Consistencia EstrictaEst definido por la siguiente condicin: Cualquier lectura a una localidad de memoria x regresa el valor guardado por la operacin de escritura ms reciente en x Esta definicin supone la existencia de un tiempo global absoluto (como en la fsica de Newton), para que la determinacin del evento "ms reciente" no sea ambigua. Esta consistencia es tpica de sistemas uniprocesador, donde nunca se pueden presentar dos eventos simultneamente. Sin embargo es prcticamente imposible de lograr en sistemas multiprocesador (distribuidos o no), debido a que pueden existir escrituras y lecturas en memoria separadas por espacios mnimos de tiempo que no alcanzan a cumplir la condicin exigida