Arquitectura de la Máquina Dash: Directorios, Estados y Protocolos de Consistencia

Arquitectura de la Máquina Dash

Introducción a Dash

En esta sección, nos centraremos en la máquina Dash. Un diagrama simplificado del prototipo de Dash, que consta de 16 unidades, donde cada una contiene:

• Un bus
• Cuatro CPU
• 16M de memoria global
• Equipo de E/S

Directorios

Cada unidad tiene un directorio con un registro de las unidades que tienen copias de sus bloques.

Cada unidad tiene 1M de bloques de memoria y una entrada por bloque en su directorio. Cada entrada contiene un mapa de bits, con un bit por unidad, que indica si esa unidad tiene el bloque oculto. La entrada también tiene un campo de 2 bits que indica el estado de ese bloque (NO OCULTO, SUCIO, LIMPIO).

Otra forma de organizar una entrada de directorio, en lugar de con un mapa de bits, sería con una lista encadenada que indique las unidades que contienen el bloque en su caché.

Estados de los Bloques de Caché

Cada bloque de caché puede estar en alguno de los siguientes estados:

• NO OCULTO: La única copia del bloque está en memoria.
• LIMPIO: La memoria está actualizada. El bloque puede encontrarse en varias cachés.
• SUCIO: La memoria es incorrecta. Solo una caché contiene el bloque.

Protocolos

El protocolo Dash se basa en la membresía y la invalidación.

En cada momento, cada bloque de la caché tiene un propietario.

• Bloque NO OCULTO o LIMPIO: La unidad de origen del bloque es el propietario.
• Bloque SUCIO: La unidad que contiene la única copia válida es el propietario.

Para escribir en un bloque LIMPIO hay que invalidar todas las copias existentes.

Modelos de Consistencia en Sistemas DSM

Los sistemas DSM (Distributed Shared Memory) tienen una o más copias de cada una de las páginas de memoria. Cuando una computadora remota llama una página, ésta se señala y es ocupada. Si alguna página está muy compartida, y solo se tiene una copia, se puede presentar un cuello de botella. Si, por el contrario, se tienen muchas copias, se evita el embotellamiento, pero surge un nuevo problema: la consistencia de todas las copias, sobre todo si las copias están en diferentes páginas que se comunican a través de una red lenta (en comparación con la velocidad de la memoria).

Modelo de Consistencia

Un modelo de consistencia es un contrato entre el software y la memoria: si el software acata las reglas, la memoria trabaja correctamente; si el software no cumple, la memoria tampoco.

Hay varios contratos, desde los débiles y fáciles de implementar hasta los estrictos e imposibles.

Consistencia Secuencial

El resultado de cualquier ejecución es el mismo que si las operaciones de todos los procesos fueran ejecutadas en algún orden secuencial, y las operaciones de cada proceso individual aparecen en esta secuencia en el orden especificado por su programa.

Cuando los procesos corren en paralelo en diferentes máquinas, cualquier intercalado válido es aceptable, pero todos los procesos deben ver la misma serie de llamadas a memoria.

El tiempo no importa, no se hace referencia al “más reciente”. Un proceso “ve” las escrituras de todos los procesos, pero solo sus propias lecturas.

Consistencia Causal

Es un debilitamiento de la consistencia secuencial que distingue entre los eventos relacionados por la causalidad y los que no.

Consistencia de Liberación

La consistencia débil tiene el problema de que, cuando se accede a una variable de sincronización, la memoria no sabe si entra o sale de una Región Crítica (RC) y debe realizar las acciones necesarias en ambos casos. Si la memoria diferencia entre entrar o salir de una RC, es posible ser más eficiente. Se necesitan dos variables de sincronización.

Los accesos de adquisición indican a la memoria que se va a entrar a una RC. Los accesos de liberación indican que acaba de salir.

Consistencia de Liberación con Base en Páginas (MCD)

En esta sección, estudiaremos la DSM “clásica”, que se construyó en multicomputadoras (procesadores conectados en red con transferencia de mensajes). En este caso, ningún CPU tiene acceso directo a la memoria de otro CPU (NORMA), en contraste con los sistemas NUMA (Non-Uniform Memory Access).

La diferencia entre NUMA y NORMA es que, en el primero, cada CPU hace referencia de forma directa a cada palabra en el espacio global de direcciones, solo leyendo o escribiendo.

Diseño básico: La idea es sencilla: emular el caché de un multiprocesador mediante MMU y el SO. El espacio de direcciones se separa en pedazos dispersos en todos los procesadores. Cuando un CPU referencia a una dirección remota, ocurre un señalamiento y el software DSM trae el pedazo que contiene la dirección y reinicia la instrucción suspendida, que puede concluir con éxito.