Gómez,
Juan Francisco L.U:30.445MEMORIA COMPARTIDA DISTRIBUIDA
Tema
No. 31
Grupo
No. 13
Integrantes:
Gómez,
Juan Francisco L.U:30.445
González,
Francisco Javier L.U:30.465
Meaurio,
Martín Eduardo L.U:29.264
Méndez,
Víctor V
L.U:29.267
Meza,
Pedro Antonio
L.U:28.564
Moragues,
Claudio F
L.U:27.553
Parisi,
Bárbara Analía
L.U :29.363
Quintana,
Héctor Ariel
L.U:30.787
Roquel,
Cesar David
L.U:29.456
Sanchez,
Julian Oriel
L.U:22.658
Tedesco,
Anabella Elina
L.U :26.246
Vera,
Mayra E. A.
L.U:28.070
La
memoria compartida distribuida (DSM) es una abstracción utilizada para
compartir datos entre computadores que no comparten memoria física. 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 ejecución que
asegura de forma transparente que procesos diferentes ejecutándose 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 física está distribuida (véase la Figura
1).
La
principal característica de DSM es que ahorra al programador todo lo
concerniente al paso de mensajes al escribir sus aplicaciones, cuestión que en
otro sistema debería 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 través de peticiones
(por razones de modularidad y protección). 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. (Los archivos
reflejados en memoria se introdujeron en el sistema operativo MULTICS (Organick
1972).)
El
paso de mensajes no puede ser eliminado completamente en un sistema distribuido:
en ausencia de memoria compartida físicamente, el soporte en tiempo de ejecución
de DSM envía las actualizaciones mediante mensajes entre computadores. Los
sistemas DSM gestionan datos replicados: cada computador tiene una copia local
de aquellos datos almacenados en DSM que han sido usados recientemente, con el
fin de acelerar sus accesos.
Uno de los primeros y más notables ejemplos de una implementación DSM fue el sistema de archivos de Apollo Domain [Leach y otros 1983], en el que los procesos ejecutándose en las diferentes estaciones de trabajo comparten archivos mediante su correspondencia (mapping) simultánea sobre sus espacios de direcciones. Este ejemplo muestra que la memoria compartida distribuida puede ser persistente. Es decir, puede sobrepasar la ejecución de cualquier proceso o grupo de ellos que accede a ella y ser compartida por diferentes grupos de procesos a lo largo del tiempo.
Figura
1. La abstracción de la memoria compartida distribuida.
La
importancia de DSM ha crecido junto con el desarrollo de los multiprocesadores
de memoria compartida. Una gran parte de la investigación se ha orientado al
desarrollo de algoritmos para la computación paralela en ese tipo de
multiprocesadores. En el nivel de arquitectura del hardware, los desarrollos
incluyen estrategias de memoria caché e interconexiones rápidas procesador –
memoria con el objetivo de maximizar el número de procesadores que pueden ser
conectados manteniéndose la productividad y minimizando las latencias de acceso
a la memoria (Dubois y otros 1988). Si los procesadores se conectan a los módulos
de memoria mediante bus común, el límite práctico oscila entre diez y
veinte procesadores antes de que las prestaciones se degraden de forma drástica
debido a la contención en el bus. Los procesadores que comparten memoria se
agrupan normalmente de cuatro en cuatro, compartiendo cada grupo un módulo de
memoria sobre un bus en un único circuito impreso. Se construyen de esta forma
multiprocesadores con hasta 64 procesadores en arquitectura de memoria de
Acceso no Uniforme (Non-Uniform Memory Access, NUMA). Se trata de una
arquitectura jerárquica en la que las placas de cuatro procesadores se
conectan entre sí utilizando un switch de altas prestaciones o un bus de alto
nivel. En una arquitectura NUMA, los procesadores ven un único espacio de
direcciones que contiene toda la memoria de todos los circuitos. Sin embargo,
la latencia de acceso para la memoria dentro del mismo circuito es menor que la
de acceso a un módulo de memoria de una tarjeta diferente, de ahí el nombre
de la arquitectura.
En
los multiprocesadores de memoria distribuida los procesadores no comparten
memoria pero se conectan mediante una red de muy altas prestaciones. Estos
multiprocesadores, al igual que en los sistemas distribuidos de propósito
general, pueden escalar hasta un número mucho mayor de procesadores o
computadores que los 64 de los multiprocesadores de memoria compartida. Una
cuestión central perseguida por la comunidad investigadora de multiprocesadores
y DSM, es si la inversión en conocimiento sobre algoritmos de memoria
compartida y el software asociado puede ser directamente transferida a una
arquitectura de memoria distribuida más escalable.
Como
mecanismo de comunicación, DSM es comparable con los sistemas de paso de
mensajes en lugar de con la comunicación basada en peticiones y respuestas, ya
que su aplicación concreta al procesamiento paralelo impone el uso de
comunicación asíncrona. Los sistemas de programación DSM y de paso de
mensajes pueden compararse de la siguiente forma:
Modelo
de programación:
en el modelo de paso de mensajes, 1as variables deben empaquetarse desde un
cierto proceso, transmitirse y desempaquetarse sobre variables en el proceso
receptor. Por el contrario, con memoria compartida, los procesos involucrados
comparten directamente las variables, de forma que el empaquetamiento no es
necesario (incluso cuando se trata de punteros a variables compartidas) y por lo
tanto no son necesarias operaciones de comunicación separadas. La mayor parte
de las implementaciones permiten nombrar y acceder a las variables almacenadas
en DSM de forma similar a las variables no compartidas. Un aspecto favorable a
los sistemas de paso de mensajes es que permiten que los procesos se comuniquen
mientras se protegen entre ellos al disponer de espacios de direcciones
privados, mientras que los procesos compartiendo DSM pueden, por ejemplo,
provocar fallos entre ellos mediante la alteración errónea de los datos. Es más,
el empaquetamiento en los sistemas de paso de mensajes entre computadores
heterogéneos, resuelve las diferencias en la representación de los datos;
pero, ¿cómo puede compartirse memoria entre computadores que, por ejemplo,
representan los enteros de forma diferente?
La
sincronización entre procesos se consigue, en el modelo de mensajes, mediante
las propias primitivas de paso de mensajes, utilizando las técnicas como la
implementación del servidor de bloqueo. Para DSM, la sincronización se realiza
a través de construcciones normales de programación de memoria compartida,
como los bloqueos y los semáforos (a pesar de que su implementación es
diferente en un entorno de memoria distribuida).
Finalmente,
al ser DSM persistente, los procesos que se comunican mediante DSM pueden
ejecutarse en instantes temporales no solapados. Un proceso puede dejar datos en
una posición de memoria acordada para que otro proceso la examine cuando se
ejecute. Por el contrario, los procesos que se comunican mediante paso de
mensajes deben ejecutarse al mismo tiempo.
Eficiencia:
los experimentos muestran que ciertos programas paralelos desarrollados para DSM
pueden tener prestaciones similares a aquellos otros programas que se ejecutan
sobre la misma plataforma y son funcionalmente equivalentes pero que han sido
construidos usando un modelo de paso de mensajes [Carter y otros 1991] (por lo
menos cuando el número de computadores es relativamente bajo, alrededor de
diez). Sin embargo, este resultado no puede generalizarse. Las prestaciones de
un programa basado en DSM dependen de muchos factores; por ejemplo un factor
importante es el patrón de compartición de datos (como si un dato es
actualizado o no por varios procesos).
Hay
una diferencia en la visibilidad de los costes asociados con los dos tipos de
modelos de programación. En el paso de mensajes, todos los accesos remotos son
explícitos y por lo tanto el programador siempre sabe si una cierta operación
es local al proceso o bien supone un gasto en comunicación. Sin embargo, en DSM
cualquier lectura o actualización puede suponer o no comunicación sobre el
sistema de soporte en tiempo real. Si existe o no comunicación depende de
factores del tipo de si los datos han sido o no accedidos antes y del patrón de
compartición entre procesos en diferentes computadores.
La
memoria compartida distribuida se implementa utilizando uno de los siguientes métodos
o bien una combinación de ellos, hardware especializado, memoria virtual
paginada convencional o middleware:
Hardware:
las arquitecturas multiprocesador de memoria compartida basadas en una arquitectura
NUMA (por ejemplo, Dash [Lenoski y otros 1992] y PLUS [Bisiani y Ravishankar
1990] se basan en hardware especializado para proporcionar a los procesadores
una visión consistente de la memoria compartida. Gestionan las instrucciones de
acceso a memoria LOAD y STORE de forma que se comuniquen con la memoria remota y
los módulos de caché según sea necesario para almacenar y obtener datos.
Esta comunicación se realiza sobre sistemas de interconexión de alta
velocidad similares a una red. El prototipo del multiprocesador Dash tiene 64 nodos;
conectados mediante una arquitectura NUMA.
Memoria
virtual paginada:
muchos sistemas, incluyendo Ivy [Li y Hudak 1989], Munin [Carter y otros 1991],
Mirage [Fleisch y Popek 1989], Clouds [Dasgupta y otros 1991], Choices [Sane y
otros 1990], COOL (Lea y otros 1993] y Mether [Minnich y Farber 1989],
implementan DSM como una región de memoria virtual que ocupa el mismo rango de
direcciones en el espacio de direcciones de cada proceso participante. Este tipo
de implementación normalmente sólo es factible sobre una colección de
computadores homogéneos con formatos de datos y de paginación comunes.
Middleware:
algunos lenguajes del tipo de Orca [Bal y otros 1990] y middleware como Linda
[Carriero y Gelernter 1989] junto con sus derivados JavaSpaces y TSpaces
[Wyckoff y otros 1998] proporcionan DSM sin necesidad de soporte hardware o de
paginación, de una forma independiente de la plataforma. En este tipo de
implementación, la computación se implementa mediante la comunicación entre
instancias del nivel de soporte de usuario en los clientes y los servidores. Los
procesos realizan llamadas a este nivel cuando acceden a datos en DSM. Las
instancias de este nivel en los diferentes computadores acceden a los datos
locales y se intercambian información siempre que sea necesario para el
mantenimiento de la consistencia.
Con
soporte hardware, se pueden utilizar técnicas software de alto nivel para
minimizar la cantidad de comunicación entre componentes de una implementación
DSM.
La
aproximación basada en páginas tiene la ventaja de que no impone una
estructura particular en la DSM, que se muestra como una secuencia de bytes.
Inicialmente permite que los programas diseñados para multiprocesadores de
memoria compartida se ejecuten en computadores sin memoria compartida, con muy
poca o ninguna adaptación. Los micronúcleos como Mach y Chorus proporcionan
soporte nativo para DSM (y otras abstracciones de memoria). Actualmente, los
sistemas DSM basados en páginas son implementados en su mayor parte en el nivel
de usuario debido a su mayor flexibilidad. La implementación utiliza el
soporte del núcleo para los manejadores de fallos de las páginas de nivel de
usuario. UNIX y algunas variantes de Windows proporcionan esta posibilidad. Los
microprocesadores con espacios de direcciones de 64-bits amplían el ámbito
de los sistemas DSM basados en páginas mediante la relajación de las
restricciones en la gestión del espacio de direcciones [Bartoli y otros
1993].
En
el ejemplo de la Figura 2 aparecen dos programas en C, Lector y Escritor,
que se comunican a través de la DSM basada en páginas proporcionadas por el
sistema Mether (Minnich y Farber
1989]. Escritor actualiza dos campos de una estructura asociada al principio de
un segmento DSM en Mether (comenzando en la dirección METHERBASE) y Lector,
imprime periódicamente los valores que lee de esos dos campos.
No
existen operaciones especiales en los dos programas anteriores; se compilan para
generar instrucciones máquina que acceden al rango común de direcciones de
memoria virtual (comenzando a partir de METHERBASE). Mether se ejecutó en
estaciones de trabajo convencionales Sun interconectadas por una red.
La
aproximación del middleware es muy diferente a la utilización de hardware
especializado y paginación ya que no está pensado para utilizar código
existente de memoria compartida. Su importancia estriba en que nos permite el
desarrollo de abstracciones de mayor nivel sobre objetos compartidos, en lugar
de hacerlo sobre posiciones de memoria compartidas.
include
"world.h"
stru~t
compartida ( int a, b; j ; Programa Escritor.
main()
l
struct
compartida "p;
methersetup():
l* Inicialización del sistema Mether % p = (struct compartida )NlETHERBASE;
í"
estructura de overlay en el segm~nto METHER 7
p->
a= p-> b= 0; . l' inicialización a cero de los campos de la estructura %
while (TRUE)( l' actualización continua de
los campos de la estructura i p-> a=p-> a+ 1;
p->
b=p-> b- 1;
/
Programa Lector.
main()
struet compartida p; methersetup(); p=(struct compartida jivlETHERBASE;
while(TRUE)(
l" lectura de los campos una vez por segundo % printf("a=°id, b=~ódln",
p->a, p->b);
sleep(1);
Figura
2.
Programa en el sistema Mether.
En
esta sección se discuten las opciones de diseño e implementación relativas a
las principales características de un sistema DSM. Es decir, se discute la
estructura de los datos gestionados en DSM; el modelo de sincronización
utilizado para acceder a DSM de forma consistente desde el nivel de aplicación;
el modelo de consistencia de DSM, encargado de gobernar la consistencia de datos
accedidos desde diferentes computadores; las opciones de actualización para la
comunicación de valores escritos en diferentes computadores; la granularidad
de la compartición en una implementación DSM; y el problema del thrashing
(fustigamiento).
Los
sistemas que replican una colección de objetos como diarios y archivos son
sistemas que permiten a los programas cliente realizar operaciones sobre los
objetos como si existiera únicamente una copia de cada objeto, aunque en
realidad están accediendo a réplicas físicas diferentes. Estos sistemas
ofrecen garantías acerca de hasta qué punto se permite que se diferencien los
objetos.
Un
sistema DSM es equivalente a estos sistemas de replicación. Cada proceso de
aplicación dispone de una abstracción de una colección de objetos, pero en
este caso la colección tiene un aspecto muy parecido al que ofrece la memoria.
Es decir, los objetos pueden ser direccionados de una u otra forma. Las
diferentes aproximaciones de DSM difieren entre sí en qué es lo que consideran
un objeto y en cómo se direccionan los objetos. Consideramos tres
aproximaciones, que tienen una visión de DSM como formada por, respectivamente,
una secuencia contigua de bytes, objetos de nivel de lenguaje o datos
inmutables.
Este
tipo de DSM se utiliza como la memoria virtual ordinaria, es decir, como una
cadena de bytes contiguos. Es la visión del sistema Mether explicada
previamente. También es la imagen proporcionada por muchos otros sistemas
DSM, incluyendo Ivy. Permite que las aplicaciones (y las implementaciones de los
lenguajes) almacenen cualquier tipo de estructura de datos sobre la memoria
compartida. Los objetos compartidos son posiciones de memoria direccionables
directamente (en la práctica, las posiciones de memoria pueden ser palabras
multi-byte en lugar de bytes individuales). Las únicas operaciones permitidas
sobre esos objetos son lee (o LOAD) y escribe (o STORE). Si x e y son dos
posiciones de memoria, las dos operaciones tienen la siguiente notación:
L(x)a
- una operación de lectura del valor a desde la posición x.
E(x)b
- una operación de escritura que almacena el valor b en la posición x.
Un
ejemplo de ejecución es E(x)1, L(x)2. Este proceso escribe el valor 1 en la
posición x y lee el valor 2 desde la misma posición. Otro proceso debe haber
sido el encargado de escribir el valor 2 en la posición compartida.
La
memoria compartida se estructura como una colección de objetos de nivel de
lenguaje, como pilas o diccionarios, con una semántica de mayor nivel que la
simple de lectura/escritura de variables. Los contenidos de la memoria
compartida se modifican únicamente mediante invocaciones sobre dichos objetos y
nunca a través del acceso directo a sus variables miembro. Una ventaja de esta
visión de la memoria es que la semántica de objetos puede utilizarse para
forzar la consistencia. La visión de DSM proporcionada por Orca es la de una
colección de objetos compartidos en los que automáticamente se serializan las
operaciones simultáneas realizadas sobre cualquiera de ellos.
En
este caso DSM se muestra como una colección de datos inmutables que los
procesos pueden leer, sumar y eliminar. Algunos ejemplos son Agora (Bisiani y
Forin l988) y, más importante, Linda y sus derivados, TSpaces y JavaSpaces.
Los
sistemas de tipo Linda proporcionan al programador una colección de tuplas
llamado espacio de tuplas. Una
tupla está formada por una secuencia de uno o más campos de datos con tipo,
como < tino, 1958 >, < «teo», 1964 > y <4,9.8, «Sí» >. En
el mismo espacio de tuplas puede existir cualquier combinación de tipos de
tuplas. Los procesos comparten los datos mediante el acceso al mismo espacio de
tuplas: sitúan las tuplas en el espacio utilizando la operación escribe y 1as
leen o extraen utilizando las operaciones lee o toma. La operación escribe añade
una tupla sin afectar al resto de tuplas existentes en el espacio. La operación
lee devuelve el valor de una tupla sin afectar al contenido del espacio de
tuplas. La operación toma también devuelve una tupla, pero la elimina del
espacio.
Cuando
se lee o se toma una tupla desde su espacio, un proceso proporciona una
especificación de tuplas y el espacio devuelve cualquiera que cumpla dicha
especificación (se trata de una variante del direccionamiento asociativo).
Para permitir que los procesos sincronicen sus actividades, las operaciones lee
y toma se bloquean hasta que se encuentre la tupla dentro del espacio. Una
especificación de tupla está formada por el número de campos y los valores o
tipos de los campos solicitados. Por ejemplo, toma (<String, integer>)
podría extraer tanto <«tino», 1958> como < «teo», 1964 >; toma(
< String, 1958 > ) extraería únicamente < <tino>, 1958 >.
En
Linda no se permite el acceso directo a las tuplas en un espacio de tuplas y los
procesos las deben reemplazar en lugar de modificarlas. Sea, por ejemplo, un
conjunto de procesos que accede a un contador compartido en un espacio de
tuplas. El valor actual del contador (64) está en la tupla < «contador»,
64 >. Para incrementar el contador en un espacio de tuplas misTups se debe
ejecutar el siguiente fragmento de código:
<
s, contador > : = misTups.take( < «contador», integer > );
misTups
write( < «contador», contador+ 1 > );
El
lector deberá comprobar que las condiciones de carrera no pueden ocurrir, ya
que toma extrae la tupla contador del espacio de tuplas.
Muchas
aplicaciones aplican restricciones sobre los valores almacenados en la memoria
compartida. Esto ocurre tanto en aplicaciones basadas en DSM como en las
mismas aplicaciones escritas para multiprocesadores de memoria compartida (o
para cualquier programa concurrente que comparte datos, como los núcleos de
los sistemas operativos y los servidores multi-hilo). Por ejemplo, si a y b son
dos variables almacenadas en DSM, una restricción puede ser que siempre se
cumpla a = b. Si dos o más procesos ejecutan el siguiente fragmento de código:
a:=
a + 1;
b:=
b + 1;
entonces
se puede llegar a una situación inconsistente. Supóngase que a y b se han
inicializado a cero y que el proceso 1 incrementa a. Antes de que pueda
incrementar b, el proceso 2 pone un 2 en a y un 1 en b.
La
restricción ha dejado de cumplirse. La solución consiste en convertir este
fragmento de código en una sección crítica: sincronizar los procesos para
asegurar que sólo uno de ellos puede estar a la vez ejecutándola.
Para
poder utilizar DSM se debe construir un servicio de sincronización distribuida
que incluya construcciones familiares como bloqueos y semáforos. Incluso cuando
DSM se estructura como un conjunto de objetos, la implementación de estos
objetos depende de la sincronización. Las construcciones de sincronización
se implementan utilizando paso de mensajes. Las instrucciones máquina
especiales del tipo de testAndSet (comprueba y escribe), utilizadas para la
sincronización en multiprocesadores de memoria compartida, se pueden aplicar
a sistemas DSM basados en páginas, pero su operación en el caso distribuido
puede ser muy ineficiente. Las implementaciones de DSM utilizan la sincronización
a nivel de aplicación para reducir la cantidad de transmisión de actualización.
DSM incluye la sincronización como un componente integrado.
La
cuestión de la consistencia adquiere importancia en los sistemas DSM que
replican el contenido de la memoria compartida mediante su almacenamiento en
las cachés de computadores separados. Cada proceso tiene un gestor de réplicas
local, el cual está encargado de mantener copias en caché para los objetos. En
la mayor parte de las implementaciones, los datos se leen desde las réplicas
locales por cuestiones de eficiencia, pero las actualizaciones deben
propagarse al resto de gestores de réplica.
El
gestor de réplica local se implementa mediante una combinación del middleware
(el nivel DSM en tiempo de ejecución en cada proceso) y del núcleo. Es normal
que el middleware realice la mayor parte del procesamiento DSM. Incluso en las
implementaciones de DSM basadas en páginas, el núcleo normalmente
proporciona únicamente una correspondencia de páginas básica, el manejo de
fallos de página y los mecanismos de comunicación, mientras que el middleware
es responsable de implementar las políticas de compartición de páginas. Si
los segmentos DSM son persistentes, entonces uno o más servidores de
almacenamiento (por ejemplo, servidores de archivos) actuarán también como
gestores de réplicas.
Además
de la gestión de la caché, una implementación DSM puede almacenar las
actualizaciones y reducir los costes de comunicación mediante la propagación
de múltiples actualizaciones a la vez.
Un
modelo de consistencia de memoria (Mosberger 1993) especifica las garantías de
consistencia que un sistema DSM realiza sobre los valores que los procesos
leen desde los objetos, dado que en realidad acceden sobre una réplica de cada
objeto y que múltiples procesos pueden actualizar los objetos. Téngase en
cuenta que esto es diferente de la noción de consistencia de alto nivel y
dependiente de aplicación.
Cheriton
[1985], describe cómo diferentes formas de DSM pueden tener previsto que un
determinado nivel de inconsistencia pueda ser aceptable. Por ejemplo, DSM puede
utilizarse para almacenar la carga de diferentes computadores en una cierta
red para que los clientes puedan seleccionar, para ejecutar sus aplicaciones,
el computador más descargado. Puesto que esta información es, por su propia
naturaleza, muy inexacta en escalas de tiempo relativamente pequeñas, sería un
desperdicio gastar recursos en el mantenimiento continuo de la consistencia
para todos los computadores del sistema.
Sin
embargo, la mayor parte de las aplicaciones tienen requisitos de consistencia
muy estrictos. Es preciso proporcionar a los programadores un modelo que se
ajuste razonablemente al comportamiento que la memoria debería tener. Antes de
describir los requisitos de consistencia de memoria en mayor detalle será útil
estudiar un ejemplo.
Sea
una aplicación en la que dos procesos acceden a dos variables, a y b, cuyo
valor inicial es cero. El proceso 2 incrementa a y b, en ese orden. El proceso 1
lee los valores de b y a depositándolos sobre las variables locales br y ar, en
ese orden. Fíjese en que no existe sincronización a nivel de aplicación. De
forma intuitiva el proceso 1 espera encontrar una de las siguientes
combinaciones de valores, en función del momento en el que las operaciones de
lectura hayan sido aplicadas sobre a y b (implícito en las sentencias br:= b y
ar:= a) relativo a la ejecución del proceso 2: ar = 0, br = 0; ar = 1, br =
0; ar = 1, br = 1. En otras palabras, la condición ar >= br se debería
cumplir siempre y el proceso 1 debería imprimir OK. Sin embargo, una cierta
implementación DSM puede enviar las actualizaciones de a y b fuera de orden al
gestor de réplicas del proceso 1, en cuyo caso la combinación ar = 0, br = 1
podría ocurrir.
La
reacción inmediata del lector respecto a este ejemplo será, probablemente,
considerar que la implementación DSM, que cambia el orden de las dos
actualizaciones, es incorrecta. Si el proceso 1 y el proceso 2 se ejecutan
juntos en un computador con un único procesador, podríamos suponer que el
subsistema de memoria está averiado. Sin embargo, para el caso distribuido se
puede tratar de una implementación correcta de un modelo de consistencia más débil
del que muchos de nosotros suponemos de forma intuitiva, pero que en cualquier
caso puede ser útil y es relativamente eficiente.
Mosberger
(1993) realiza un bosquejo de un conjunto de modelos que han sido pensados para
multiprocesadores de memoria compartida y sistemas DSM software. Los principales
modelos de consistencia que se pueden implementar en la práctica en sistemas
DSM son la consistencia secuencial y los modelos basados en consistencia débil.
Figura
3.Dos procesos accediendo a variables compartidas
La
principal cuestión que se plantea al caracterizar un modelo particular de
consistencia de memoria es: cuando se realiza un acceso de lectura sobre una
posición de memoria, ¿qué accesos de escritura a esa posición son candidatos
para que sus valores sean proporcionados a la lectura? En el extremo más débil,
la respuesta es: cualquier escritura que haya sido iniciada antes que la
lectura. Este modelo se podría obtener si se permitiera a los gestores de réplica
retrasar la propagación de las actualizaciones a sus parejas de forma
indefinida. Es demasiado débil para ser útil.
En
el extremo más fuerte, todos los valores que se escriban aparecen disponibles
de forma instantánea a todos los procesos: una lectura devuelve el valor
escrito más reciente, respecto al instante en el que se realiza la lectura. Se
trata de una definición problemática en dos sentidos. En primer
lugar ni las escrituras ni las lecturas se realizan en un instante
temporal único, de forma que el significado de más reciente no siempre es
claro. Cada tipo de acceso tiene un punto de inicio bien definido, pero se
completa en un cierto instante posterior (por ejemplo, después de que se haya
enviado un mensaje). De forma que no es
siempre posible determinar de forma exacta si un evento ocurrió antes
que otro.
En
cualquier caso, este modelo ha sido especificado y estudiado. El lector puede
haberlo reconocido: es lo que llamamos secuenciación. La secuenciación es más
conocida como consistencia atómica en la literatura DSM.
Se
dice que un servicio de objetos compartidos replicados es secuenciable si para
cualquier ejecución existe un entrelazado de las series de operaciones
iniciadas por todos los clientes que satisfacen los dos criterios siguientes:
L1:
La secuencia de operaciones entrelazada cumple la especificación de una (única)
copia correcta de
los objetos.
L2:
El orden de las operaciones en el entrelazado es consistente con los instantes
reales en los que las operaciones
ocurrieron en la ejecución actual.
Se
trata de una definición genérica que se aplica a cualquier sistema que
contenga objetos replicados compartidos. Al estar tratando con memoria
compartida, podemos ahora ser más explícitos. Sea el caso más simple en el
que la memoria compartida se estructura como un conjunto de variables que pueden
ser leídas o escritas. Todas las operaciones son de lectura y de escritura: la
lectura del valor a desde la variable x se
indica como L(x)a; la escritura del valor b sobre la variable x se indica
como E(x)b. Podemos ahora expresar el primer criterio, L1, en términos de
variables (objetos compartidos):
L1':
La secuencia entrelazada de operaciones es tal que si L(x)a ocurre en la
secuencia, entonces o bien la última operación de escritura que ocurre antes
que ella en la secuencia entrelazada es E(x)a, o bien no ocurre ninguna operación
de escritura antes que ella y a es el valor inicial de x.
Este
criterio se ajusta a nuestra intuición de que una variable puede ser cambiada
únicamente por una operación de escritura. El segundo criterio de serialización,
L2, no cambia.
La
secuenciación es demasiado estricta en la mayor parte de las ocasiones. El
modelo de memoria más fuerte para DSM que se usa en la práctica es el de
consistencia secuencial (Lamport 1979).
Un
sistema DSM se dice que es secuencialmente consistente si para cualquier ejecución
existe algún entrelazado de las series de operaciones realizadas por todos los
procesos que satisface los dos siguientes criterios:
SCl:
La secuencia entrelazada de operaciones es tal que si L(x)a ocurre en la
secuencia, entonces o bien la última operación de escritura que ocurrió antes
en la secuencia entrelazada fue E(x)a, o bienno ha ocurrido ninguna operación
escritura antes que ella y a es el valor inicial de x.
SC2:
El orden de las operaciones en el entrelazado es consistente con el orden de
programa en el que dichas operaciones fueron ejecutadas por cada cliente
individual.
El
criterio SCl es el mismo que el Ll'. El criterio SC2 se refiere al orden de
programa en lugar de referirse al orden temporal, que es el que hace posible
implementar la consistencia secuencial.
La
condición puede ser retomada de la siguiente forma: existe un entrelazado
virtual para todas las operaciones de lectura y escritura de los procesos sobre
una única imagen virtual de la memoria; en este entrelazado se mantiene el
orden de programa de cada proceso individual y cada proceso siempre lee el último
valor escrito dentro del entrelazado.
En
una ejecución real, las operaciones de memoria pueden ser solapadas y algunas
actualizaciones pueden ser ordenadas de forma diferente en diferentes procesos,
siempre que las limitaciones de la definición no dejen de cumplirse. Fíjese
que, para satisfacer las condiciones de la consistencia secuencial, se deben
tener en cuenta las operaciones de memoria sobre el sistema DSM completo y no únicamente
las operaciones desde cada posición individual.
La
combinación ar = 0, br = 1 en el ejemplo anterior puede no ocurrir bajo la
consistencia secuencial, ya que el proceso 1 estaría leyendo valores que entrarían
en conflicto con el orden de programa del proceso 2. En la Figura
4 se muestra un ejemplo de entrelazado de los accesos a memoria de un
proceso en una ejecución con consistencia secuencial. Una vez más, mientras
que aquí se muestra un entrelazado real de las operaciones de lectura y
escritura, la definición únicamente estipula que la ejecución debe producirse
como si se realizara dicho entrelazado estricto.
Los
sistemas DSM con consistencia secuencial se pueden implementar utilizando un único
servidor para gestionar todos los datos compartidos y haciendo que todos los
procesos envíen las solicitudes de lectura y escritura al servidor, que las
ordena de forma global. Esta arquitectura es demasiado ineficiente para una
implementación DSM por lo que a continuación se describen algunos medios prácticos
para conseguir la consistencia secuencial. En cualquier caso, se trata de un
modelo cuya implementación es muy costosa.
Una
reacción al coste de la consistencia secuencial consiste en buscar un modelo más
débil pero con sus propiedades bien definidas. La coherencia es un ejemplo de
una forma más débil de consistencia. Bajo la coherencia, cada proceso llega a
acuerdos sobre el orden de las operaciones de escritura sobre la misma posición,
pero no acuerdan necesariamente el orden de las operaciones de escritura sobre
posiciones diferentes. Se puede pensar en la coherencia como una forma de
consistencia secuencial realizada posición a posición. Los sistemas DSM
coherentes pueden implementarse mediante un protocolo para implementar la
consistencia secuencial aplicada de forma separada a cada unidad de datos
replicados (por ejemplo, a cada página). El ahorro se produce del hecho de que
los accesos a dos páginas diferentes se hacen de forma independiente y no
existe retardo entre ellos al aplicarse el protocolo de forma separada a ambos.
Figura
4. Entrelazado bajo la consistencia secuencial.
Dubois
y otros (1988) desarrollaron un modelo de consistencia débil en un intento de
evitar los costes de la consistencia secuencial en los multiprocesadores, pero
conservando el efecto de esta consistencia secuencial. Este modelo aprovecha
el conocimiento de las operaciones de sincronización para relajar la
consistencia de memoria, mientras se muestra al programador para implementar
una consistencia secuencial. Por ejemplo, si el programador utiliza un bloqueo
para implementar una sección crítica entonces un sistema DSM puede asumir
que ningún otro proceso puede acceder a los datos accedidos bajo la exclusión
mutua. Será por lo tanto redundante que un sistema DSM propague las
actualizaciones de dichos datos antes que el proceso deje la sección crítica.
A pesar de que se mantienen valores inconsistentes durante algún tiempo para
los datos, durante ese tiempo dichos datos no son utilizados; la ejecución
aparenta ser secuencialmente consistente. Adve y Hill [1990] describen una
generalización de esta idea llamada ordenamiento débil:
« (Un sistema DSM) está ordenado débilmente respecto a un modelo de
sincronización si y sólo si aparenta ser secuencialmente consistente para el
software que aplica el modelo de sincronización.»
Para
la propagación de las actualizaciones realizadas desde un cierto proceso sobre
varios otros se han desarrollado dos posibles opciones: escritura actualizante y
escritura invalidante. Ambos se pueden aplicar a varios modelos de consistencia
DSM, incluyendo la consistencia secuencial. En detalle las opciones se describen
así:
Las
actualizaciones de un proceso se realizan de forma local y se envían por
multidifusión a todos los gestores de réplica que posean una copia del dato,
los cuales modifican inmediatamente el dato leído por los procesos locales (véase
la Figura 5). Los procesos leen las
copias locales de los datos, sin necesidad de comunicación. Además de permitir
múltiples lectores, varios procesos pueden escribir el mismo dato de forma
simultánea; esto se conoce como compartición
de múltiples lectores/múltiples escritores. El modelo de consistencia de
memoria implementado en la escritura actualizante depende de varios factores,
siendo el principal la propiedad de ordenamiento de la multidifusión. Se puede
conseguir la consistencia secuencial mediante la utilización de multidifusiones
totalmente ordenadas, que no terminan hasta que el mensaje de actualización
haya sido entregado localmente. Se consigue así que todos los procesos acuerden
el orden de las actualizaciones. El conjunto de lecturas que se realizan entre
dos actualizaciones consecutivas está bien definido y su ordenamiento es
independiente de la consistencia secuencial.
Las
lecturas son baratas en los sistemas de escritura actualizante. Sin embargo los
protocolos de multidifusión ordenada son relativamente caros de implementar
en software. Orca utiliza escritura actualizante a través del protocolo de
multidifusión de Amoeba (Kaashoek y Tanenbaum 1991] (véase www.cdk3.net/coordination),
que utiliza el soporte hardware para implementar la multidifusión. Munin
soporta la escritura actualizante como una opción. En la arquitectura
multiprocesador PLUS se utiliza un protocolo de escritura actualizante soportado
mediante hardware especializado.
Figura
5. DSM utilizando escritura actualizante
Está
implementada normalmente en la forma de compartición de múltiples lectores/un
único escritor. En cualquier instante, una cierta posición puede ser accedida
para lectura por uno o más procesos, o bien puede ser leída y escrita por un
único proceso. Una posición que está siendo utilizada en modo de sólo
lectura puede ser copiada a cualquier otro proceso. Cuando un proceso intenta
escribir sobre ella, en primer lugar se envía un mensaje multidifusión a todas
sus copias para invalidarlas y se espera el reconocimiento de esta operación
antes de que la escritura tenga lugar; el resto de los procesos están por lo
tanto prevenidos para no leer datos viejos (es decir, datos que no están
actualizados). Cualquier proceso que este intentando acceder al dato se bloquea
hasta que la escritura termine. Finalmente, el control se transfiere desde el
proceso escritor, y se puedan realizar otros accesos una vez que la actualización
haya sido enviada. El resultado es que se procesan todos los accesos al dato
mediante una política del tipo primero en llegar, primero en ser servido.
Lamport [1979] demostró que, con este esquema, se consigue consistencia
secuencial.
En
el esquema de invalidación, las actualizaciones únicamente se propagan cuando
los datos son leídos y además se pueden realizar varias actualizaciones
consecutivas sin necesidad de realizar ninguna comunicación. Como
contrapartida, se deben invalidar todas las copias de sólo lectura antes de que
se pueda realizar una escritura. Esto puede ser potencialmente caro en el
esquema de múltiples lectores/un único escritor. Sin embargo, si la relación
lectura/escritura es suficientemente alta, el paralelismo que se obtiene
permitiendo múltiples lectores simultáneos amortiza su coste. Cuando la relación
lecturas/escrituras es relativamente baja, un esquema de tipo único lector/único
escritor puede ser más apropiado: es decir, como máximo un proceso en cada
instante puede obtener acceso de sólo lectura.
Una
cuestión relacionada con la estructura de DSM es la granularidad de la
compartición. Teóricamente, todos los procesos comparten el contenido
completo del DSM. Sin embargo, según se van ejecutando los programas que
comparten DSM, únicamente ciertas partes de los datos son en realidad
compartidas y únicamente durante ciertos períodos de la ejecución. Para una
implementación DSM sería un derroche transmitir el contenido completo de DSM
cuando los procesos acceden y actualizan los datos compartidos. ¿Cuál debería
ser la unidad de compartición en una implementación DSM? Es decir, cuando un
proceso ha escrito sobre DSM, ¿qué datos debe enviar el sistema DSM para
conseguir que en todos los nodos los valores sean consistentes?
En
este punto nos centramos en las implementaciones basadas en páginas, a pesar de
que la cuestión de la granularidad aparece también en otro tipo de
implementaciones . En un sistema DSM basado en páginas, el hardware soporta de
forma eficiente las alteraciones sobre un espacio de direcciones siempre que la
unidad básica sea la página; esto se consigue mediante la inserción de un
nuevo puntero de marco de página en la tabla de páginas (véase, por ejemplo,
Bacon [1998] para una descripción de la paginación). Los tamaños de las páginas
pueden llegar a ser de 8 kilobytes, cantidad apreciable de datos que debe ser
transmitida sobre una red para mantener consistentes las copias remotas cuando
se genera una actualización. Por defecto; el precio de la transferencia
completa de la página debe ser pagado tanto si se ha modificado la página de
forma completa como si únicamente se ha variado un bit.
La
utilización de un tamaño de página menor (entre 512 bytes y 1 kilobyte) no
implica necesariamente una mejora global de las prestaciones. Primero, en
aquellos casos en los que los procesos actualizan grandes cantidades de datos
continuos, es mejor enviar una página grande que varias páginas pequeñas a
través de actualizaciones separadas, ya que las sobrecargas fijas debidos al
software se generan por paquete de red. Segundo, la utilización de una página
pequeña como unidad de distribución supone un mayor número de unidades que
deben ser administradas separadamente por la implementación DSM.
Para
complicar aún más el problema, los procesos tienden a competir más por las páginas
cuando el tamaño de éstas es mayor, debido a que la probabilidad de que los
datos utilizados estén en la misma página se incrementa con su tamaño.
Considere, por ejemplo, dos procesos, uno que accede únicamente a la posición
A mientras que el otro accede sólo a la posición B, asociada a la misma página
(véase la Figura 6). Supongamos,
para ser más concretos, que un proceso lee A y el otro actualiza B. A nivel de
aplicación no existe conflicto en el acceso u los datos. Sin embargo, la página
debe ser transmitida completamente entre los procesos, ya que el sistema DSM no
sabe por defecto, en tiempo de ejecución, qué posiciones han sido alteradas en
la página. A esta situación se la conoce como compartición
falsa: dos o más procesos comparten zonas de una página, pero de hecho sólo
uno de ellos accede a cada zona. En los protocolos de escritura invalidante, la
compartición falsa puede derivar en invalidaciones innecesarias. En los
protocolos de escritura actualizante, cuando varios escritores comparten datos
de forma falsa puede ocurrir que las páginas sean sobrescritas con versiones
antiguas.
En
la práctica, la elección de la unidad de compartición debe realizarse en
función de los tamaños de página física disponibles, a pesar de que, si el
tamaño de la página es pequeño, se pueda utilizar como unidad un cierto número
de páginas contiguas. La disposición de los datos respecto a las fronteras
entre páginas es un factor importante para determinar el número de
transferencias de páginas realizadas durante la ejecución de un cierto
programa.
Figura
6. Disposición de los datos sobre las páginas.
Un
problema potencial de los protocolos de escritura invalidante es el thrashing.
Se dice que un sistema DSM está en thrashing cuando realiza un gasto
desmesurado de tiempo en la invalidación y transferencia de datos compartidos
en comparación con el tiempo empleado por los procesos de aplicación en la
realización de trabajo útil. Ocurre cuando varios procesos compiten por el
mismo dato o bien por datos que están bajo compartición falsa. Si, por
ejemplo, un proceso lee de forma repetida el mismo dato que otro proceso está
actualizando regularmente, entonces el dato será continuamente transferido
desde el escritor e invalidado en el lector. Éste es un ejemplo de patrón de
compartición para el que la escritura invalidante es menos apropiada que la
escritura actualizante. En la siguiente sección se describe la aproximación
Mirage al thrashing, en la que los computadores poseen las páginas durante un
período de tiempo mínimo; en la Sección 4 se describe cómo Munin permite al
programador declarar patrones de acceso al sistema DSM de forma que se pueden
elegir opciones de actualización que se adapten al patrón de compartición de
cada dato y se evite así el thrashing.
En
esta sección se describen métodos para implementar sistemas DSM basados en páginas
con consistencia secuencial. La descripción se basa en Ivy [Li y Hudak 1959]
como caso de estudio.
El
modelo básico a considerar es aquel en el que una colección de procesos
comparten un segmento de DSM (véase la Figura
7). El segmento se hace corresponder sobre el mismo rango de direcciones en
cada proceso, de forma que sobre él se pueden almacenar valores de punteros
significativos. Los procesos se ejecutan en computadores equipados con
unidades de gestión de memoria paginada. Asumiremos que únicamente hay un
proceso que accede al segmento DSM en cada computador. En realidad puede haber
varios procesos de ese tipo en cada computador. Sin embargo, esos procesos
podrían entonces compartir las páginas directamente (el mismo marco de página
puede aparecer en las tablas de páginas de diferentes procesos). La única
complicación sería la de coordinar el envío y la propagación de
actualizaciones a una página cuando dos o más procesos locales acceden a ella.
En esta descripción se ignoran este tipo de detalles.
Figura
7. Modelo del sistema de un DSM basado en páginas.
La
paginación es transparente a los componentes de la aplicación dentro de los
procesos; ellos pueden leer y escribir de forma lógica cualquier posición
sobre DSM. Sin embargo, para mantener la consistencia secuencial, el soporte en
tiempo de ejecución de DSM restringe los permisos de acceso a páginas cuando
se procesan lecturas y escrituras. La unidad de gestión de memoria paginada
permite configurar los permisos de acceso a los datos de una página a ninguno,
sólo lectura o lectura escritura. Si un proceso trata de saltarse los permisos
de acceso actuales, se dispara un fallo de página en lectura o escritura, en
función del tipo de acceso. El núcleo redirige el fallo de página a un
manejador especificado por el nivel de soporte en tiempo de ejecución de DSM
para cada proceso. El manejador de fallos de página (que se ejecuta de forma
transparente a la aplicación) realiza un procesamiento especial del
mencionado fallo de página, según se describe a continuación, antes de
devolver el control a la aplicación. En sistemas DSM primitivos, como Ivy, el
propio núcleo realiza gran parte del procesamiento. Explicaremos cómo los
propios procesos realizan la gestión de los fallos de página y la comunicación
consiguiente. En la actualidad, estas funciones son realizadas por una
combinación del nivel en tiempo de ejecución de DSM en el proceso y del núcleo.
Normalmente, el módulo de DSM insertado en el proceso contiene la mayor parte
de la funcionalidad de forma que pueda ser modificada y ajustada sin tener que
afrontar los problemas asociados con la alteración del núcleo.
En
esta descripción no se tendrá en cuenta el procesamiento de fallo de página
que debe realizarse como parte de una implementación típica de memoria
virtual. Aparte del hecho de que los; segmentos DSM compiten con otros segmentos
por los marcos de páginas, las implementaciones son independientes.
En
la sección anterior se perfilaron las principales alternativas de
implementación de la escritura actualizante y de la escritura invalidante. En
la práctica, si el sistema DSM está basado en páginas, la escritura
actualizante sólo se usa si las escrituras pueden ser almacenadas en búferes.
Esto se debe a que la gestión estándar de fallos de página no se adapta bien
al procesamiento aislado de cada escritura a una página.
Para
entender esto, supongamos que cada actualización deba ser enviada vía
multidifusión a todas las copias y supongamos también que una página ha sido
protegida contra escritura. Cuando un proceso intenta escribir en la página, se
genera un fallo de página y se invoca a una rutina de gestión. Este gestor
debería, inicialmente, examinar la instrucción que provocó el fallo para
determinar el valor y la dirección que estaba siendo escrita y a continuación
realizar una multidifusión de la actualización antes de restablecer el acceso
de la escritura y devolver el control a la instrucción que generó el fallo.
Sin
embargo, ahora que el acceso de escritura ha sido restablecido, las siguientes
actualizaciones no generarán un fallo de página. Para provocar que cada
acceso de escritura genere un fallo de página, será necesario que el manejador
de fallos de página configure el proceso en modo TRAZA, de forma que en el
procesador se activará una excepción de éste tipo después de cada instrucción.
El manejador de la excepción TRAZA debería desactivar los permisos de
escritura de la página y desactivar el modo TRAZA. Todos los pasos anteriores
deberán repetirse cuando ocurra el siguiente fallo en escritura. Claramente
este método tiende a ser muy caro ya que podrían ocurrir muchas excepciones
durante la ejecución de un proceso.
En
la práctica, la escritura actualizante se utiliza en las implementaciones
basadas en página, pero sólo donde se deja a la página con permisos de
escritura después de un fallo de páginas inicial y se permite que se realicen
varias escrituras antes de que la página actualizada sea propagada. Munin
utiliza esta técnica de almacenamiento de escrituras. Para mejorar la
eficiencia, Munin intenta evitar la propagación de la página completa,
propagando únicamente la parte que haya sido modificada. Cuando un proceso
realiza un primer intento de escritura sobre una página. Munin gestiona el
fallo de páginas realizando una copia de la página y guardando la copia antes
de habilitar el acceso de escritura. Posteriormente, cuando Munin está
dispuesto para propagar la página, compara la página actualizada con la copia
original y codifica las actualizaciones en forma de conjunto de diferencias
entre las dos páginas. Estas diferencias a menudo ocupan mucho menos espacio
que la página completa. Los procesos receptores regeneran la página
actualizada partiendo de la copia antes de actualizar y del conjunto de
diferencias.
Los
algoritmos basados en invalidaciones utilizan la protección de páginas para
forzar la consistencia en la compartición de datos. Cuando un proceso está
actualizando una página, tiene localmente los permisos de lectura y escritura
sobre dicha página; el resto de procesos no tienen permisos de acceso sobre la
página. Cuando uno o más procesos están leyendo una página, sólo tienen
permiso de lectura; el resto de procesos no tienen permiso de acceso (a pesar de
que puedan adquirir los permisos de lectura). No son posibles otras
combinaciones. Un proceso con la versión actualizada de una página p es
marcado como su propietario y esto se indica mediante la notación propietario(p).
Se trata del único escritor o bien de uno de los lectores. A1 conjunto de
procesos que tienen una copia de una cierta página p se le denomina conjunto de
copia y se utiliza la notación conjuntocopia(p) para referirse a ellos.
Las
transiciones de estado posibles se muestran en la Figura
8. Cuando un proceso Pw intenta escribir sobre una página p
sobre la que o no tiene acceso o sólo tiene acceso de lectura, se genera un
fallo de página. El manejador de fallos de página realiza los siguientes
pasos:
v
Si el procesador Pw no tienen
una copia actualizada de la página, se le transfiere.
v
Se invalidan el resto de copias: los
permisos de acceso a las páginas se modifican para impedir el acceso de los
miembros de conjuntocopia(p).
v
conjuntocopia(p) : = { Pw }
v
propietario(p) : = Pw
v
El soporte en tiempo de ejecución de Pw
sitúa la página con permisos de lectura y escritura en la posición
correspondiente en su espacio de direcciones y reinicia la instrucción que generó
el fallo.
Nótese
que dos o más procesos con copias de sólo lectura pueden generar falsos de
escritura de forma más o menos simultánea. Una copia de sólo lectura de una página
puede quedar caducada cuando la propiedad sea finalmente cedida. Para detectar
si la copia actual de sólo lectura de una página está o no caducada, se
asocia un número de secuencia a cada página, el cual se incrementa cada vez
que la propiedad es transferida. Un proceso que solicita acceso de escritura
inserta en la solicitud el número de secuencia de su copia de sólo lectura, si
posee uno. El propietario actual utiliza este número para decidir si la página
ha sido modificada y por lo tanto es necesario enviarla. Este esquema es
descrito por Kessler y Livny [1989] bajo el nombre de algorítano
astuto.
Cuando
un proceso PR intenta leer una página p sobre la que no tiene
permisos de acceso, se genera un fallo de página en lectura. El manejador de
fallos realiza los siguientes pasos:
La página es copiada desde
propietario(p) hasta PR.
Si el propietario actual es un único
escritor, entonces éste mantiene la propiedad de p y se colocan sus permisos de
acceso en sólo lectura. La retención de los derechos de, acceso en lectura es
deseable en el caso que el proceso intente leer la página posteriormente, se
habrá retenido una versión actualizada de la página. Sin embargo, al ser el
propietario deberá gestionar las solicitudes que se reciban sobre la página,
incluso si no se vuelve a utilizar de nuevo. Por lo tanto se puede considerar
que en lugar de reducir los derechos de acceso sería más apropiado simplemente
prohibirlos y transferir la propiedad a PR.
conjuntocopia(p) : = conjuntocopia(p) U
{ PR }.
El nivel de soporte de sistema DSM en PR
sitúa la página con permisos de sólo lectura en la posición adecuada en su
espacio de direcciones y reinicia la instrucción que genero e1 fallo.
Es
posible que se genere un segundo fallo de página durante los algoritmos de
transición que se acaban de describir. Para que las transiciones se realicen de
forma consistente, cualquier nueva solicitud sobre la página no será procesada
hasta que la transición actual se haya completado.
La
descripción que se acaba de proporcionar se ha centrado en la explicación de
qué debe hacerse. A continuación se estudia el problema de cómo implementar
de forma eficiente el gestor de fallos de página
Figura
8. Transiciones de estado bajo invalidación de escritura.
Quedan
por resolver dos problemas importantes en un protocolo que implemente el esquema
de invalidación:
1.
Cómo localizar el propietario(p) para una cierta página p.
2.
Dónde almacenar conjuntocopia(p).
Li
y Hudak [1989] describen varías arquitecturas y protocolos para Ivy, que
realizan diferentes aproximaciones sobre los problemas mencionados. La más
simple que describiremos es el algoritmo mejorado de gestión centralizada. En
esta solución, se utiliza un único servidor, llamado gestor, para almacenar la
dirección (dirección de nivel de transporte) del propietario(p) para cada página
p. El gestor podría ser uno de los procesos que ejecutan la aplicación o bien
cualquier otro proceso. En este algoritmo el conjunto conjuntocopia(p) se
almacena en propietario(p). Es decir, se almacenan los identificadores y las
direcciones de transporte de los miembros de conjuntocopia(p).
Tal
y como se puede observar en la Figura 9,
cuando asume un fallo de página el proceso local (al que nos referiremos como cliente)
envía un mensaje al gestor conteniendo el número de página y el tipo de
acceso solicitado (lectura o lectura-escritura). El cliente espera una
respuesta. El gestor procesa la solicitud realizando una búsqueda de la dirección
de propietario(p) y reenviando la solicitud al propietario. Si se trata de un
fallo de escritura, el gestor configura al cliente como nuevo propietario. Las
siguientes solicitudes se insertan en una cola en el cliente a la espera de que
éste complete la transferencia de la propiedad sobre él mismo.
El
anterior propietario envía la página al cliente. En el caso de un fallo en
escritura, también envía el conjunto de copia de la página. El cliente
realiza la invalidación cuando recibe el conjunto de copia. Envía una
solicitud multidifusión a los miembros del conjunto de copia, y espera el reconocimiento
desde todos los procesos para considerar que la invalidación se ha completado.
La multidifusión no necesita ser ordenada. El anterior propietario no necesita
ser incluido en la lista de
destinatarios, al haberse invalidado a sí mismo. Los detalles de la gestión
del conjunto de copia se dejan al lector, que deberá consultar 1os algoritmos
de invalidación generales ya explicados.
El
gestor es un cuello de botella para las prestaciones y un punto de fallo crítico.
Li y Hudak sugirieron tres alternativas para que la carga de la gestión de páginas
fuera dividida entre computadores: gestiones de páginas distribuida fija,
gestión distribuida basada en multidifusión y gestión distribuida dinámica.
En la primera alternativa, se utilizan múltiples gestores, cada uno con
funcionalidad equivalente al gestor centralizado ya descrito, pero dividiendo de
forma estática las páginas entre ellos. Por ejemplo, cada gestor podría
manejar sólo aquellas páginas cuyos números de página estén dentro de un
cierto rango de valores. Los clientes calculan el número hash de la página que
se necesita y utilizan una tabla de configuración predeterminada para buscar 1a
dirección del gestor correspondiente.
Este
esquema debería mejorar en general el problema de la cara, pero tiene la
desventaja de que una correspondencia fija de las páginas sobre los gestores
puede no ser factible. Si los procesos no acceden a las páginas de forma
uniforme, algunos gestores estarán más cargados que otros. Describimos a
continuación la gestión basada en multidifusión y la gestión distribuida dinámica.
Figura
9. Gestor Central y mensajes asociados
La
multidifusión puede utilizarse para eliminar completamente al gestor. Cuando se
genera un fallo en un proceso, éste envía una multidifusión con su solicitud
de página al resto de los procesos. Sólo contesta el proceso que posea la página.
Se debe tener cuidado para garantizar el comportamiento correcto si los clientes
solicitan la misma página de forma simultánea: cada cliente debe terminar
obteniendo la página, incluso si su multidifusión se ha realizado durante la
transferencia de la propiedad.
Considérense
dos clientes C1 y C2 que utilizan multidifusión para
localizar una página cuyo propietario es O. Supongamos que O recibe la
solicitud de C1 en primer lugar y le transfiere la propiedad. Antes
de que la página llegue, la solicitud de C2 llega a O y a C1.
O descartará la solicitud de C2 ya que ha dejado de poseer la página.
Li y Hudak consideraron que C1, debería retrasar el procesamiento de
la solicitud de C2 hasta que haya obtenido la página ya que en otro
caso debería descartar dicha solicitud al no ser el propietario y la solicitud
de C2 se perdería. Sin embargo, queda todavía un problema sin
resolver. La solicitud de C1 ha sido almacenada mientras tanto en una
cola en C2. Después de que C1 haya finalmente
proporcionado a C2, la página, C2 recibirá y procesará
la solicitud de C1, ¡la cual ahora es obsoleta!
Una
solución consiste en utilizar multidifusión totalmente ordenada, de forma que
los clientes puedan descartar de forma segura aquellas solicitudes que llegan
antes que la suya (además de al resto de los procesos las solicitudes son
enviadas a ellos mismos). Otra solución, basada en una multidifusión sin orden
más barata, pero que utiliza mayor ancho de banda, consiste en asociar a cada página
un vector de marcas temporales, con una entrada por cada proceso. La marca de
tiempo se transfiere junto con la propiedad de una página. Cuando un proceso
obtiene la propiedad, incrementa su entrada en el vector de marcas temporales.
Cuando un proceso solicita la propiedad, inserta en la solicitud la última
marca temporal que mantiene para esa página. En nuestro ejemplo, C2
debería descartar la solicitud de C1 ya que la entrada de C1
en la marca temporal de la solicitud es menor que la marca que llegó con la página.
Independientemente
de que se utilice una multidifusión ordenada o desordenada, este esquema tiene
las desventajas típicas de los sistemas basados en multidifusión: los procesos
que no poseen una cierta página son interrumpidos con mensajes irrelevantes,
desperdiciando tiempo de procesamiento.
Li
y Hudak propusieron el algoritmo de gestión distribuida dinámico, que permite
que la propiedad de una página se transfiera entre procesos pero utiliza un método
alternativo a la multidifusión para localizar al propietario de una página. La
idea se basa en la división de las sobrecargas de localización de páginas
entre aquellos computadores que acceden a ellas. Para cada página p, cada
proceso mantiene una marca del propietario actual de la página, que en realidad
es el propietario probable de p o propietarioProbable(p). Inicialmente a cada
proceso se le proporcionan las localizaciones exactas para las páginas. Sin
embargo, estos valores son meros indicios, ya que las páginas se transfieren
entre los nodos en cualquier momento. Como ocurre en los algoritmos anteriores,
la propiedad se transfiere sólo cuando ocurre un fallo en escritura.
El
propietario de una página es localizado siguiendo una cadena de marcas que son
actualizadas al nuevo propietario cuando la página es transferida entre
computadores. La longitud de la cadena, es decir, el número de mensajes de
reenvío que son necesarios para localizar al propietario, amenaza con crecer de
forma indefinida. El algoritmo resuelve este problema mediante la actualización
inmediata de las marcas según vayan estando disponibles los valores más
actualizados. El procedimiento para actualizar las marcas y reenviar las
solicitudes es el siguiente:
Cuando un proceso transfiere la
propiedad de una página p a otro proceso, marca como nuevo
propietarioProbable(p) al receptor de la página.
Cuando un proceso gestiona una solicitud
de invalidación para una página p, marca como nuevo propietarioProbable(p) al
solicitante.
Cuando un proceso que ha solicitado
acceso de lectura a una página p la recibe, marca como nuevo
propietarioProbable(p) al nodo que se la proporcionó.
Cuando un proceso recibe una solicitud
para una página p de la que no es propietario. reenvía la solicitud al
propietarioProbable(p) y marca como nuevo propietarioProbable(p) al solicitante.
Las
primeras tres actualizaciones son una consecuencia del protocolo en lo que se
refiere a la transferencia de la propiedad de la página y la obtención de
copias de sólo lectura. La actualización cuando se reenvía una solicitud se
justifica en que, para las solicitudes de escritura, el solicitante será
pronto el propietario, incluso si no lo es actualmente. De hecho, en el
algoritmo de Li y Hudak, la actualización de propietarioProbable se realiza
tanto si la solicitud es para acceso de lectura como si lo es para escritura.
|
(a) Situación de los
punteros propietarioProbable justo antes de que en el proceso A se
produzca un fallo de página para una página propiedad de E |
(b) Fallo en escritura: situación
de los punteros propietariosProbable después de reenviar la solicitud de
escritura de A
c) Fallo en lectura: situación de los punteros propietariosProbable después de reenviar la solicitud de lectura de A
Figura
10. Actualizaciones de los punteros propietarioProbable.
En
la Figura 10 ((a) y (b)) se ilustran
los punteros de propietarioProbable antes y después de que en el proceso A se
produzca un fallo de página en escritura. El puntero propietarioProbable de A
para la página apunta inicialmente a B. Los procesos B, C y D reenvían la
solicitud a E siguiendo sus propios punteros propietarioProbable; después de
eso, todos los punteros apuntan a A como resultado de las reglas de actualización
descritas. El resultado una vez gestionado el fallo es claramente mejor que
antes de hacerlo: la cadena de punteros ha desaparecido.
Sin
embargo, si en A se produce un fallo de lectura, entonces el proceso B se
comporta mejor (dos pasos en lugar de tres para apuntar a E), la situación de C
no cambia (dos pasos) pero para D la situación empeora ya que necesita dos
pasos en lugar de uno (véase la Figura
10(c)). Para investigar el efecto en las prestaciones de esta táctica es
necesario realizar simulaciones.
El
tamaño medio de las cadenas de punteros puede ser controlado además
difundiendo periódicamente a todos los procesos la localización del
propietario actual. Esto provoca que todas las cadenas pasen a tener tamaño
1.
Li
y Hudak describen los resultados de las simulaciones que realizaron para
investigar la eficacia de sus actualizaciones de punteros. Eligieron de forma
aleatoria los procesos que generaban fallos de entre 1.024 procesadores y
encontraron que el número medio de mensajes necesarios para
conseguir el propietario de una página fue de 2,34 si las difusiones de
anuncio de la posición del propietario se realizaban cada 256 fallos y de 3,64
si las difusiones se realizaban cada 1.024 fallos. Estos valores se muestran aquí
únicamente a modo de ilustración: en Li y Hudak (1959) se muestra un conjunto
completo de resultados. Nótese que un sistema DSM que utiliza un gestor central
necesita dos mensajes para conseguir el propietario de una página.
Finalmente,
Li y Hudak describen una optimización que potencialmente consigue realizar la
invalidación de forma más eficiente y reduce el número de mensajes necesarios
para manejar un fallo de página en lectura. En lugar de tener que obtener una
copia de la página desde su nodo propietario, un cliente puede obtener una
copia de cualquier proceso con una copia válida. Existe la posibilidad de que
un cliente que está intentando localizar el propietario en la cadena de punteros
encuentre antes un nodo con una copia válida.
Esto
se realiza bajo la condición de que los procesas mantengan un registro de
clientes a los que han cedido una copia de una página de su propiedad. El
conjunto de procesos que poseen copias de sólo lectura de una página forma
un árbol cuya raíz es el propietario, con cada nodo apuntando a los nodos
hijo, los cuales obtuvieron copias de él. La invalidación de una página
comienza en el propietario y avanza hacia abajo a través del árbol. Cuando un
nodo recibe un mensaje de invalidación, lo reenvía a sus hijos además de
invalidar su propia copia. El efecto en su conjunto es el de que algunas
invalidaciones se realizan en paralelo. Esto puede reducir el tiempo global necesario
para invalidar una página, especialmente en un entorno sin soparte hardware
para la multidifusión.
Se
puede argumentar que es responsabilidad del programador evitar el thrashing. El
programador debería anotar las posiciones de sus datos para ayudar al soporte
DSM a minimizar tanto el número de veces que se copian las páginas como el número
de transferencias de propiedad. Esta última aproximación es discutida en la
siguiente sección en el contexto del sistema DSM Munin,
Mirage
[Fleisch y Popek 1989] adopta una aproximación al thrashing transparente a los
programadores. Mirage asocia cada página con un pequeño intervalo de tiempo.
Una vez que un proceso ha accedido a una página, se le permite retener el
acceso para e1 intervalo dado, que puede ser considerado como un intervalo de
tiempo. Cualquier otra solicitud realizada sobre la página durante dicho
intervalo de tiempo es rechazada. Una desventaja obvia de este esquema es que
resulta muy difícil elegir la longitud del intervalo de tiempo. Si el sistema
utiliza una longitud de tiempo elegida de forma estática, ese valor puede ser
inapropiado en muchos casos. Por ejemplo un proceso podría escribir una página
una única vez y no volver a acceder a ella; el resto de procesos tendrían
entre tanto el acceso prohibido a dicha página. Análogamente, el sistema podría
ceder a otro proceso el acceso a la página antes de acabar de usarla.
Un
sistema DSM podría elegir el tamaño del intervalo de tiempo de forma dinámica.
Un posible punto de partida para su elección podría ser la observación de
los accesos sobre la página (utilizando los bits de referencia de la unidad de
gestión de memoria). Otro factor que podría considerarse es el tamaño de la
cola de procesos que esperan por la página.
Los
algoritmos de la sección anterior fueron diseñados para conseguir la
consistencia secuencial en sistemas DSM. La ventaja de la consistencia
secuencial es que el sistema DSM se comporta de la forma que sus programadores
esperan que lo haga una memoria compartida. Su desventaja es el coste de
implementación. Los sistemas DSM a menudo necesitan utilizar multidifusión en
sus implementaciones, tanto si se basan en escritura actualizante como en
invalidación de escritura (aunque para la invalidación sea suficiente una
multidifusión desordenada). La búsqueda del propietario de una página
tiende a ser cara: un gestor central que conoce la ubicación del propietario de
cada página se convierte en un cuello de botella; las secuencias de punteros
implican, de media, la necesidad de más mensajes. Además, los algoritmos
basados en invalidaciones pueden sufrir de thrashing.
La
consistencia relajada fue utilizada por primera vez en el multiprocesador Dash,
el cual realiza una implementación hardware de DSM basada en un protocolo de
invalidación de escritura [Lenoski y otros 1992]. Munin y Treadmarks [Keleher y
otros 1992] utilizan una implementación software. La consistencia relajada es más
débil que la consistencia secuencial y más barata en su implementación, pero
conserva una semántica razonable que resulta tratable para los programadores.
La
consistencia relajada se basa en la reducción de las sobrecargas de DSM
explotando el hecho de que los programadores utilizan objetos de sincronización,
como semáforos, bloqueos y barreras. Una implementación DSM puede utilizar el
conocimiento del acceso a estos objetos para permitir que la memoria sea
inconsistente en determinados puntos, pero asegurando la consistencia a nivel de
aplicación mediante la utilización de estos objetos de sincronización.
Para
comprender la consistencia relajada (o cualquier otro modelo de memoria que
utilice la sincronización) comenzamos realizando una clasificación de los
accesos a memoria en función de su papel, si existe, en la sincronización.
Además estudiaremos cómo los accesos a memoria se pueden realizar de forma asíncrona
para mejorar las prestaciones y proporcionaremos un modelo operacional
sencillo de cómo se producen los accesos a memoria.
Tal
y como hemos mencionado previamente, las implementaciones DSM para sistemas
distribuidos de propósito general pueden utilizar, por razones de eficiencia,
paso de mensajes en lugar de variables compartidas para implementar la
sincronización. Sin embargo, resultará útil mantener en mente la sincronización
basada en variables compartidas para 1a siguiente discusión. El pseudocódigo
que aparece a continuación implementa bloqueos utilizando la operación
testAndSet sobre variables. La función testAndSet pone la variable lock a l y
devuelve 0 si valía previamente cero; en otro caso devuelve 1. Esto lo hace de
forma atómica.
adquiereBloqueo(var
int bloqueo): //
bloqueo se pasa por referencia
while
(testAndSet(bloqueo) = l )
skip;
liberaBloqueo(var
int bloqueo): //bloqueo
se pasa por referencia lock. : = 0;
La
principal distinción se realiza entre accesos
competitivos y accesos no
competitivos (ordinarios). Dos accesos son competitivos si:
Pueden ocurrir de forma concurrente (no
se fuerza el mantenimiento de un orden entre ellos).
Al menos uno de ellos es una escritura.
Por
lo tanto dos operaciones de lectura no pueden nunca ser competitivas; una
lectura y una escritura sobre la misma posición realizadas por dos procesos que
se sincronizan entre las operaciones (y por lo tanto las ordenan) no son
competitivas.
Además
dividimos los accesos competitivos entre accesos de sincronización
y de no sincronización:
Los accesos
de sincronización son operaciones de lectura o escritura que
contribuyen a la sincronización.
Los accesos
de no sincronización son operaciones de lectura o de escritura
concurrentes pero que no contribuyen a la sincronización.
La
operación de escritura implícita en bloqueo : = 0 dentro de liberaBloqueo
(arriba) es un acceso de sincronización. También lo es la operación de
lectura implícita en testAndSet.
Los
accesos de sincronización son competitivos, ya que los procesos que
potencialmente necesitan sincronizarse acceden a variables de sincronización de
forma concurrente y deben actualizarlas: las operaciones de lectura por sí
solas no permiten conseguir la sincronización. Pero no todos los accesos
competitivos son accesos de sincronización ya que existen algunos tipos de
algoritmos paralelos en los que los procesos realizan accesos competitivos a
variables compartidas simplemente para actualizar y leer resultados de otro y
no para sincronizar.
Los
accesos de sincronización también se dividen en accesos
de adquisición y accesos de liberación,
en función de su papel en el bloqueo potencial del proceso que realiza el
acceso o en el desbloqueo de otros procesos.
En
la descripción de la implementación DSM con consistencia secuencial, se explicó
que las operaciones de memoria pueden sufrir retardos significativos. Existen
varios tipos de operaciones asíncronas que permiten incrementar la velocidad a
la que se ejecutan los procesos, a pesar de los mencionados retardos. En primer
lugar, las operaciones de escritura pueden implementarse de forma asíncrona.
Un valor escrito es almacenado en un búfer antes de ser propagado y los efectos
de la escritura se observan con posterioridad desde otros procesos. En segundo
lugar, las implementaciones de DSM pueden realizar de forma anticipada la búsqueda
de valores con anticipación a su lectura, evitándose así la parada de un
proceso cuando necesita dichos valores. En tercer lugar, los procesadores pueden
ejecutar las instrucciones fuera de orden. Mientras se espera la finalización
del acceso a memoria actual, se puede iniciar la siguiente instrucción, siempre
que ésta no dependa de la actual.
A
la vista de las operaciones asíncronas que se acaban de presentar,
distinguiremos entre el punto en el que una operación de lectura o escritura es
iniciada (cuando el proceso comienza la ejecución de la operación) y el punto
en el que la instrucción es efectuada o completada.
Supondremos
que nuestro DSM es, al menos, coherente. Esto significa que cada proceso está
de acuerdo en el orden de las operaciones de escritura sobre una misma posición.
Dada esta suposición, podemos hablar de forma no ambigua del orden de las
operaciones de escritura sobre una cierta posición.
En
un sistema de memoria compartida distribuida, podemos dibujar un diagrama
temporal para cualquier operación de memoria o que ejecute el proceso P (véase
la Figura 11).
Decimos
que una operación de escritura E(x)v se ha realizado con respecto al proceso P
si desde ese punto las operaciones de lectura de P devuelven el valor v escrito
por la operación de escritura, o bien el valor escrito por alguna operación
posterior sobre x (nótese que otra operación puede escribir el mismo valor v).
De
forma similar, decimos que una operación de lectura L(x)v se ha realizado con
respecto al proceso P cuando ninguna escritura posterior iniciada sobre la misma
posición pueda proporcionar el valor v que P lee. Por ejemplo, P puede haber
obtenido mediante prebúsqueda el valor que necesita leer.
Finalmente,
se dice que la operación o se ha realizado si lo ha hecho respecto a todos los
procesos.
Figura
11. Diagrama temporal de una operación de lectura o escritura sobre DSM.
Los
requisitos que pretendemos cumplir son:
Preservar
la semántica de sincronización de objetos del tipo de bloqueos y barreras.
Mejorar
las prestaciones, para lo cual se permite un cierto grado de asincronía en las
operaciones de memoria.
Limitar
el solapamiento entre los accesos a memoria para garantizar ejecuciones cuyos
resultados sean equivalentes a los obtenidos con consistencia secuencial.
La
memoria con consistencia relajada se ha diseñado para satisfacer estos
requisitos. Gharachorloo y otros [1990] definen la consistencia relajada de la
siguiente forma:
CRl:
Antes de permitir que una operación ordinaria de lectura o escritura se realice
respecto a cualquier otro proceso, deben haberse realizado todos los accesos de
adquisición previos.
CR2:
Antes de permitir que una operación de liberación sea realizada con respecto a
cualquier otro proceso, deben haberse realizado todas las operaciones ordinarias
de lectura y escritura previas.
CR3:
Las operaciones de adquisición y liberación son secuencialmente consistentes
entre ellas.
CR1
y CR2 garantizan que, cuando se haya realizado una liberación, ningún otro
proceso que haya adquirido un bloqueo pueda leer versiones caducadas de los
datos modificados por el proceso que realiza la liberación. Esto coincide con
las expectativas de los programadores ya que cuando, por ejemplo, se libera un
bloqueo, eso implica que un proceso ha terminado de modificar los datos dentro
de la sección crítica.
El
soporte en tiempo de ejecución de DSM sólo podrá forzar la consistencia
relajada si es consciente de los accesos de sincronización. Por ejemplo, en
Munin, el programador se ve forzado a utilizar las primitivas propias de Munin
acquireLock (adquiere bloqueo), releaseLock (libera bloqueo) y waitAtBarrier
(espera en la barrera). (Una barrera es un objeto de sincronización que bloquea
cada uno de los procesos de un conjunto hasta que todos ellos hayan llegado a
ella; entonces todos los procesos continúan.) Un programa debe utilizar la
sincronización para asegurar que las actualizaciones se hacen visibles al resto
de procesos. Dos procesos que comparten DSM pero no utilizan nunca objetos de
sincronización pueden que nunca vean las actualizaciones que realizan entre
ellos si la implementación garantiza estrictamente las condiciones expuestas
previamente.
Nótese
que el modelo de consistencia relajada permite que una implementación realice
algunas operaciones asíncronas. Por ejemplo, un proceso necesita no ser
bloqueado cuando realiza actualizaciones dentro de una sección crítica. Sus
actualizaciones tampoco necesitan propagarse hasta que deja la sección crítica
mediante la liberación del bloqueo. Además las actualizaciones pueden recolectarse
y ser enviadas en un único mensaje. Únicamente la actualización final a cada
dato debe ser enviada.
Considérense
los procesos de la Figura 12, los cuales
adquieren y liberan un bloqueo para acceder a una pareja de variables a y b (a y
b son inicializadas a cero). El proceso 1 actualiza a y b bajo condiciones de
exclusión mutua, de forma que el proceso 2 no puede leer a y b al mismo tiempo
y por lo tanto para él se cumplirá que a = b = 0 o bien a = b = 1. Las
secciones críticas fuerzan la consistencia (igualdad de a y b) al nivel de
aplicación. Es redundante propagar las actualizaciones a las variables
afectadas durante la sección crítica. Si el proceso 2 hubiera, por ejemplo,
intentado acceder a la variable a fuera de la sección crítica, entonces
hubiera encontrado un valor caducado. Ese es un problema del programador de
aplicaciones.
Supongamos
que el proceso 1 adquiere primero el bloqueo. E1 proceso 2 se bloqueará y no
generará ninguna actividad sobre DSM hasta que haya adquirido e? bloqueo e
intente acceder a a y b. Si los dos procesos se ejecutaran en una memoria con
consistencia secuencial entonces el proceso 1 se hubiera bloqueado durante la
actualización de a y b. Bajo un protocolo de escritura actualizante, se
hubiera bloqueado durante la actualización de todas las versiones de los datos;
bajo un protocolo de invalidación de escritura, se hubiera bloqueado hasta que
se hubieran invalidado todas las copias.
Bajo
la consistencia relajada, el proceso 1 no se bloqueará cuando acceda a los
datos a y b. El soporte en tiempo de ejecución de DSM simplemente anota qué
datos han sido actualizados pero no realiza otras tareas en ese instante. Será
únicamente cuando el proceso 1 libere el bloqueo cuando se necesite la
comunicación. Bajo un protocolo de escritura actualizante, se propagarán las
actualizaciones sobre a y b; en un protocolo de invalidación de escritura, se
enviarán las invalidaciones.
El
programador (o un compilador) es el responsable de etiquetar las operaciones de
lectura y escritura como accesos de tipo liberación. Adquisición o
no-sincronización; el resto de instrucciones se considerarán ordinarias.
Etiquetar el programa supone la dirección del sistema DSM para forzar las
condiciones de la consistencia relajada.
Gharachorloo
y otros [1990] describen el concepto de programa etiquetado correctamente. Ellos
probaron que este tipo de programa no puede distinguir entre una ejecución DSM
con consistencia relajada y otra ejecución con consistencia secuencial.
Proceso 1:
adquiereBloqueo();
// entra a la sección crítica
a := a + 1;
b := b + 1;
liberaBloqueo()
// sale de la sección crítica Proceso 2:
adquiereBloqueo();
// entra a la sección crítica
print(“los
valores a y b son”, a,b);
liberaBloqueo()
// sale de la sección crítica
Figura
12. Procesos ejecutándose en un DSM con consistencia relajada.
El
diseño del sistema DSM Munin [Carter y otros 1991] intenta mejorar la
eficiencia de DSM mediante la implementación del modelo de consistencia
relajada. Además, Munin permite a los programadores anotar sus datos según
el tipo de compartición, de forma que se pueden realizar optimizaciones en
las opciones de actualización seleccionadas para la gestión de la
consistencia. Ha sido implementado sobre el núcleo V [Cheriton y Zwaenepoel
1985], que fue uno de los primeros núcleos que permitían a los hilos de nivel
de usuario manejar los fallos de página y manipular las tablas de páginas.
Los
siguientes puntos se refieren a la implementación de la consistencia relajada
en Munin:
* Munin envía la información de actualización o invalidación tan
pronto como se libere el bloqueo.
El
programador puede realizar anotaciones que asocien un bloqueo con ciertos
conjuntos de datos. En este caso, el soporte en tiempo de ejecución de DSM
puede propagar las actualizaciones relevantes en el mismo mensaje utilizado para
transferir el bloqueo al proceso en espera, asegurando que el receptor del
bloqueo tiene copias de los datos que necesita antes de utilizarlos.
Keleher
y otros [1992] describen una alternativa a la aproximación impaciente de Munin,
es decir, al envío de información de actualización o invalidación el mismo
instante de la liberación. En su lugar, esta implementación débil realiza
dicho envío únicamente cuando dicho bloqueo es adquirido a continuación.
Además, envía esta información sólo a los procesos que adquieran el bloqueo
y la inserta en el mensaje que sirve para conceder la adquisición de bloqueo.
Es innecesario hacer visible las actualizaciones a los otros procesos hasta que
ellos adquieran, por turno, el bloqueo.
Munin
implementa diferentes protocolos de consistencia aplicados con una granularidad
a nivel de datos individuales. Los protocolos están parametrizados según las
siguientes opciones:
Protocolo de escritura actualizante o de
invalidación de escritura.
Que puedan o no existir de forma simultánea
varias copias de un dato modificable.
Que se retarden o no las actualizaciones
o las invalidaciones (por ejemplo, bajo la consistencia relajada).
Que los datos tengan o no un propietario
fijo, al que se deben enviar todas las actualizaciones. .Que el mismo
dato pueda o no ser modificado concurrentemente por varios escritores.
Que los datos puedan o no ser
compartidos por un conjunto fijo de procesos;
Que los datos puedan o no ser
modificados.
Estas
opciones son elegidas en función de la naturaleza de los datos y de sus
patrones de compartición entre procesos. El programador puede elegir de forma
explícita qué opciones usar para cada dato. Sin embargo, Munin proporciona un
conjunto pequeño, estándar de anotaciones válidas para una gran variedad de
aplicaciones y datos para que el programador las aplique sobre los datos; cada
una de estas anotaciones supone una elección adecuada de los parámetros. Son
las siguientes:
Sólo
lectura: después de la inicialización
no se realizan actualizaciones y el dato puede ser copiado libremente.
Migratorio:
los procesos realizan por turno varios accesos al dato, siendo al menos uno de
ellos una actualización. Por ejemplo, el dato puede ser accedido dentro de una
sección crítica. Munin siempre proporciona los accesos de lectura y escritura
juntos en dicho objeto, incluso cuando un proceso genera un fallo de lectura.
Esto ahorra el procesamiento de los fallos de escritura posteriores.
Escritura
compartida: varios procesos actualizan
simultáneamente la misma variable (por ejemplo, un array) de forma que esta
anotación es una declaración por parte del programador de que los procesos no
actualizan las mismas partes de la variable. Esto significa que Munin puede
evitar la compartición falsa pero debe propagar sólo aquellas palabras del
dato que cada proceso está actualizando actualmente. Para conseguirlo, Munin
realiza una copia de la página (dentro de un gestor de fallos de escritura)
justo antes de que sea actualizada localmente. Sólo las diferencias entre las
dos versiones de la página son enviadas en una actualización.
Productor-consumidor:
el dato es compartido por un conjunto fijo de procesos, siendo actualizado sólo
por uno de ellos. Como ya se explicó anteriormente en la discusión del
thrashing, en este caso es más apropiado un protocolo de escritura
actualizante. Además, las actualizaciones pueden ser retrasadas utilizando el
modelo de consistencia relajada, suponiendo que el proceso utiliza bloqueos para
sincronizar su acceso.
Reducción:
el dato siempre es modificado siguiendo la secuencia de bloqueo, lectura,
actualización y desbloqueo. Por ejemplo, un mínimo global en una computación
paralela debe ser localizado y modificado atómicamente si es mayor que el mínimo
local. Estas variables son almacenadas en un propietario fijo. Las
actualizaciones son enviadas al propietario, que se encarga de su propagación.
Resultado:
varios procesos actualizan diferentes palabras dentro de elemento de datos
mientras que un único proceso lee el elemento completo. Por ejemplo diferentes
procesos trabajadores escriben en diferentes elementos de un array, que es
procesado posteriormente por un proceso maestro. La optimización consiste en
propagar las actualizaciones sólo al maestro y no a los trabajadores (como
ocurriría bajo la anotación de escritura compartida ya descrita).
Convencional:
los datos se manejan mediante un protocolo de invalidación similar al descrito
en la sección previa. Por lo tanto ningún proceso podrá leer versiones
caducadas de un dato. Carter y otros [1991] detallaron las opciones de parámetros
utilizadas en cada una de las anotaciones descritas. Este conjunto de
anotaciones no es fijo. Pueden crearse otras anotaciones de la misma forma que
pueden encontrarse otros patrones de compartición que necesiten diferentes
opciones de parámetros.
Los
modelos de consistencia de memoria se pueden dividir entre modelos uniformes,
caracterizados por no distinguir entre diferentes tipos de accesos a memoria y
modelos híbridos, los cuales distinguen entre accesos ordinarios y de
sincronización (al igual que otros tipos de accesos).
Existen
varios modelos uniformes más débiles que el modelo de consistencia secuencial.
En la Sección 2.3 se presentó la coherencia como la consistencia secuencial
sobre cada posición de memoria. Los procesos acuerdan el orden de todas las
escrituras sobre una cierta posición, pero el orden de las escrituras desde
diferentes procesadores sobre diferentes posiciones puede variar (Goodman 1989,
Gharachorloo y otros 1990).
Otros
modelos de consistencia uniforme son:
Consistencia
causal: las lecturas y escrituras se
asocian mediante la relación ocurrió-antes. Esta relación define el orden
entre dos operaciones de memoria cuando o bien (a) se han realizado desde el
mismo proceso: o bien (b) un proceso lee un valor escrito por otro proceso; o
bien (c) existe una secuencia de los dos tipos de operaciones anteriores que
enlazan las dos operaciones de memoria. El modelo fuerza a que el valor devuelto
por una lectura debe ser consistente con la relación ocurrió-antes. Esto es
descrito por Hutto y Ahamad [1990].
Consistencia
de procesador: la memoria cumple dos
condiciones, es coherente y cumple el modelo de RAM encauzada. La forma más
sencilla de pensar en la consistencia de procesador es que la memoria es
coherente y todos los procesos acuerdan el orden de dos accesos de escritura
cualquiera realizados por el mismo proceso, es decir, acuerdan el orden de
programa. Fue inicialmente descrito informalmente por Goodman [1989] y,
posteriormente definido formalmente por Gharachorloo y otros [1990] y Ahamad y
otros [1992].
RAM
encauzada: todos los procesadores
acuerdan el orden de las escrituras iniciadas por un cierto procesador [Lipton y
Sandberg 1988].
Además
de la consistencia relajada, otros modelos híbridos son los siguientes:
Consistencia
con admisión: la consistencia con
admisión (entry) fue propuesta inicialmente en el sistema DSM Midway [Bershad y
otros 1993]. En este modelo, cada variable compartida se
enlaza a un objeto de sincronización, como por ejemplo un bloqueo, que
gobierna el acceso a dicha variable. El primer proceso que adquiera el bloqueo
tiene garantizada la lectura del valor más reciente de la variable. Un proceso
que quiera escribir en la variable debe obtener primero el correspondiente
bloqueo en modo exclusivo, de forma que dicho proceso sea el único capaz de
acceder a la variable. Varios procesos podrán leer de forma concurrente la
variable manteniendo el bloqueo en modo no exclusivo. Midway evita la
tendencia a la compartición falsa de la consistencia relajada, pero a costa de
incrementar la complejidad de la programación.
Consistencia
de ámbito: este modelo de memoria
[Iftode y otros 1996] trata de simplificar el modelo de programación de la
consistencia entry. En la consistencia de ámbito, las variables se asocian con
objetos de sincronización de forma automática en su mayor parte, en lugar de
depender del programador para la asociación explícita de bloqueos a variables.
Por ejemplo, el sistema puede monitorizar qué variables son actualizadas en una
sección crítica.
Consistencia
débil: la consistencia débil [Dubois
y otros 1988] no distingue entre los accesos de sincronización adquiere y
libera. Asegura que todos los accesos ordinarios previos se completan antes
que lo haga cualquiera de los dos tipos de accesos de sincronización.
La
consistencia relajada y algunos de los modelos de consistencia más débiles que
la secuencial parecen ser los más prometedores para DSM. No parece muy
significativa la desventaja del modelo de consistencia relajada consistente en
que las operaciones de sincronización necesiten ser conocidas por el soporte en
tiempo de ejecución de DSM, siempre y, cuando las operaciones de sincronización
proporcionadas por el sistema sean suficientemente potentes para cubrir las
necesidades de los programadores.
Es
importante darse cuenta de que, bajo los modelos híbridos, la mayor parte de
los programadores no están forzados a tener en cuenta la semántica del modelo
de consistencia de memoria utilizado, siempre que sincronicen los accesos a sus
datos de forma adecuada. Pero existe el peligro general en los diseños DSM de
pedir al programador que realice múltiples anotaciones a su programa para
conseguir una ejecución eficiente. Esto incluye tanto anotaciones para asociar
datos con objetos de sincronización como las anotaciones de compartición
usadas en Munin. Se supone que una de las ventajas de la programación de
memoria compartida sobre el paso de mensajes debería ser su relativa
comodidad.
Se
ha descrito y justificado el concepto de memoria compartida distribuida como una
abstracción de la memoria compartida que sirve de alternativa a la comunicación
basada en mensajes en un sistema distribuido. El objetivo principal de DSM es el
procesamiento paralelo y la compartición de los datos. Se ha demostrado que sus
prestaciones son comparables a las del paso de mensajes para ciertas
aplicaciones paralelas, pero es difícil conseguir una implementación eficiente
y sus prestaciones dependen en gran medida de las aplicaciones.
Este
trabajo se ha centrado en las implementaciones software de DSM (en particular
aquellas basadas en el subsistema de memoria virtual) con un cierto soporte del
hardware.
Las
principales cuestiones de diseño e implementación son la estructura de DSM, la
forma de sincronizar las aplicaciones, el modelo de consistencia de memoria la
utilización de protocolos de escritura actualizante o de invalidación de
escritura, la granularidad de la compartición y el thrashing.
DSM
puede estructurarse como una serie de bytes, como una colección de objetos
compartidos o como una colección de datos inmutables como las tuplas.
Las
aplicaciones en DSM necesitan la sincronización para cumplir los requisitos de
consistencia específicos de la aplicación. Para este propósito utilizan
objetos como los bloqueos, implementados utilizando paso de mensajes por razones
de eficiencia.
El
modelo de consistencia más estricto implementado en los sistemas DSM es la
consistencia secuencial. Debido a su coste, se han desarrollado otros modelos de
consistencia más débiles, como la coherencia y la consistencia relajada. La
consistencia relajada permite a la implementación utilizar los objetos de
sincronización para conseguir mayor eficiencia sin romper las restricciones de
consistencia del nivel de aplicación. Se han mencionado brevemente otros
modelos de consistencia, incluyendo la consistencia de entrada, la de ámbito
y la débil, todas ellas basadas en la sincronización.
Los
protocolos de escritura actualizante son aquellos en los que las actualizaciones
de los datos son propagadas a todas sus copias. Normalmente son implementadas en
hardware, a pesar de que también existen implementaciones software que utilizan
multidifusiones totalmente ordenadas. Los protocolos de invalidación de
escritura evitan la lectura de datos no válidos mediante la invalidación de
todas las copias cuando los datos son actualizados. Estos protocolos se adaptan
mejor a los sistemas DSM basados en páginas, para los que la escritura
actualizante puede ser una opción costosa.
La
granularidad de DSM modifica la probabilidad de contención entre procesos con
compartición falsa de datos ya que dichos datos están contenidos en la misma
unidad de compartición (una página, por ejemplo). También afecta al coste por
byte de la transferencia de actualizaciones entre computadores.
El
thrashing puede ocurrir cuando se utiliza invalidación de escritura. Consiste
en la transferencia repetida de datos entre procesos competidores a costa del
progreso de la aplicación. Este efecto puede ser reducido mediante la
sincronización a nivel de aplicación, permitiendo a los computadores retener
una página durante una mínima cantidad de tiempo, o mediante el etiquetado de
los datos de forma que las lecturas y las escrituras sean concedidas
conjuntamente.
Se
han descrito los tres principales protocolos de invalidación de escritura de
Ivy para DSM basada en páginas, que tratan el problema de la gestión del
conjunto de copias de una página y de la localización de su propietario. Se
trata del protocolo de gestión central, en el que un único proceso almacena la
dirección del propietario actual de cada página; el protocolo basado en la
multidifusión para localizar el propietario actual de una página; y el
protocolo de gestión distribuida dinámica, que envía cadenas de punteros para
localizar al propietario actual de una página.
Munin
es un ejemplo de implementación de la consistencia relajada. Implementa una
consistencia relajada impaciente caracterizada porque la propagación de los
mensajes de actualización o invalidación se realiza tan pronto como el bloqueo
es liberado. Existen otras implementaciones más débiles que propagan sólo
aquellos mensajes que son solicitados. Munin permite a los programadores
anotar sus datos para seleccionar aquellas opciones de protocolo que mejor se
adapten, dada la forma en la que se comparten.
Número de visitantes actuales disponible desde el 14/07/2002:
Autor: lrmdavid@exa.unne.edu.ar
Ó FACENA - http://exa.unne.edu.ar
Servicios WEB: webmaster@exa.unne.edu.ar