Unidad 4 Memoria Compartida Distribuida

4.1 Configuraciones Memoria Compartida Distribuida

COMPUTACIÓN PARALELA
Un computador paralelo es un conjunto de procesadores capaces de cooperar en la solución de un problema.
El problema se divide en partes. Cada parte se compone de un conjunto de instrucciones. Las instrucciones de cada parte se ejecutan simultáneamente en diferentes CPUs.
Técnicas computacionales que descomponen un problema en sus tareas y pistas que pueden ser computadas en diferentes máquinas o elementos de proceso al mismo tiempo.
Por qué utilizar computación paralela?

1. Reducir el tiempo de procesamiento
2. Resolver problemas de gran embergadura.
3. Proveer concurrencia.
4. Utilizar recursos remotos de cómputo cuando los locales son escasos.
5. Reducción de costos usando múltiples recursos ”baratos” en lugar de costosas supercomputadoras.
6. Ampliar los límites de memoria para resolver problemas grandes.

El mayor problema de la computación paralela radica en la complejidad de sincronizar unas tareas con otras, ya sea mediante secciones críticas, semáforos o paso de mensajes, para garantizar la exclusión mutua en las zonas del código en las que sea necesario.
La computación paralela está penetrando en todos los niveles de la computación, desde computadoras masivamente paralelas usados en las ciencias de larga escala computacional, hasta servidores múltiples procesadores que soportan procesamiento de transacciones. Los principales problemas originados en cada uno de las áreas básicas de la informática (por ejemplo, algoritmos, sistemas, lenguajes, arquitecturas, etc.) se vuelven aún más complejos dentro del contexto de computación paralela.

4.1.1  De Circuito, basada en bus, anillo o con conmutador

• La principal  problemática que se presenta entre dos  o más procesos sean locales o distribuidos  al compartir recursos es que cada proceso  tiene su propio espacio de direcciones.

• Cuando  se trata de procesos locales al estar  físicamente en el mismo hardware el espacio  de direcciones se vuelve sencillo la compartición.  Esto no es sencillo en procesos distribuidos.

• En un  Sistema Operativo Distribuido, una computador  ejecuta los procesos en su memoria propia,  pero en caso de necesitar más memoria  utilizará los recursos disponibles de otra  computadora.

• La Memoria  compartida distribuida ayuda a que no  se formen los famosos cuellos de botella,  facilita el diseño y construcción de  sistemas distribuidos.

Visión general  de la MCD

• El esquema  más básico de compartición de datos  en Sistemas Distribuidos es el paso de  mensajes (e.g. sockets). La problemática es  la latencia y la garantía de acceso  (puede llegar o no el mensaje).

• Existen  tres formas básicas de lograr compartición  de memoria en ambientes distribuidos: por  hardware, por sistema operativo o a nivel  de usuario (software).  

• La compartición  de memoria se da por diversos esquemas,  siendo las más comunes: por paginación,  por variables compartidas y por objetos.

• El diseño  de la granularidad de compartición así  como la sincronización y manejo de consistencia  son elementos importantes en el diseño  de mecanismos de memoria compartida.

Replicación
(a)  páginas distribuidas en 4 máquinas 
(b)  CPU 0 lee página 10 
 
(c)  CPU 1 lee página 10 

• Pseudo-Compartición

Memoria  compartida en IPC 

• La forma  más rápida de comunicar dos procesos  es que compartan una zona de memoria  compartida. 

• Las primitivas  para manipular memoria compartida son: shmget  para crear una zona d ememoria compartida  o utilizar una ya creada, shmctl para  acceder y modificar la información administrativa  y de control, shmat para unir una  zona de memoria compartida a un proceso,  y shmdt para separa una zona previamente  unida.

#include  <sys/shm.h>
int  shmget(key, size, shmflg); 
int  shmid;
if((shmid  = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0600))  == -1)
/*Error  al crear memoria compartida*/

• int shmctl(shmid,  cmd, buf)

• cmd indica  la operación la cual puede ser: IPC_STAT,  IPC_SET, IPC_RMID, SHM_LOCK, SHM_UNLOCK.

• struct  shmid_s *buf

• smctl(shmid,  IPC_RMID, 0);

char  *shmat(shmid, shmaddr, shmflg);
int  shmdt(shmaddr); 
float  *memoria;
shmid  = shmget(llave, MAX * sizeof(float), IPC_CREAT  | 0600);
memoria  = shmat(shmid, 0, 0);
/*Operar  memoria*/
shmdt(memoria);
shmctl(shmid,  IPC_RMID, 0);
Arquitecturas  de MCD 

• Existen  varías formas de implantar físicamente memoria  compartida distribuida, a continuación se  describen cada una de ellas.

• Memoria  basada en circuitos : existe una única  área de memoria y cada micro tiene  su propio bus de datos y direcciones  (en caso de no tenerlo se vuelve  un esquema centralizado)

Arquitecturas de MCD 

Existen varias formas de implantar físicamente memoria compartida distribuida, a continuación se describen cada una de ellas.

Memoria basada en circuitos: Existe una única área de memoria y cada micro tiene su propio bus de datos y direcciones (en caso de no tenerlo se vuelve un esquema centralizado).

MCD basada en bus: En este esquema los micros comparten un bus de datos y direcciones por lo que es más barato de implementar, se necesita tener una memoria caché grande y sumamente rápida. MCD basada en bus: En este esquema los micros comparten un bus de datos y direcciones por lo que es más barato de implementar, se necesita tener una memoria caché grande y sumamente rápida.

MCD basada en anillos: Es más tolerante a fallos, no hay coordinador central y se privilegia el uso de la memoria más cercana.

MCD basada en conmutador: Varios micros se conectan entre sí en forma de bus formando un grupo, los grupos están interconectados entre sí a través de un conmutador.

4.2 Modelos de consistencia.

• La principal  problemática de la compartición de memoria  en ambientes distribuidos consiste en el  manejo de la consistencia ya que varios  procesos distribuidos pueden estar escribiendo  en la zona de memoria compartida pudiendo  invalidar el contenido de las lecturas  que acaban de hacer algunos procesos.
• Para prevenir esta problemática se han planteado muchos mecanismos que permiten evitar la inconsistencia de los datos.

• Una forma  básica pero costosa es el manejo de  replicación sólo se debe considerar la  granularidad de la réplica así como  la reintegración de las modificaciones.

• Se deben  considerar el tipo de datos que se  están compartiendo: páginas, variables, objetos,  etc.

4.2.1  Estricta, causal, secuencial, débil, de liberación  y de entrada. 
Consistencia  Estricta 

• Este modelo  es el más robusto pero sumamente difícil  de implementar.

• Cualquier  lectura a la localidad de memoria x  retorna el valor almacenado por la última  operación de escritura (antes de la lectura).

• Supone  la existencia de un tiempo global. Determinar  cuál fue la escritura más reciente no  siempre es posible.

• En un  solo procesador la consistencia estricta es  lo esperado.

• P(X, t1):  A =1
• ….
• P(y, t2): A = 5
• …..
• P(z, t3): print(A) --> 5

• ¿Se puede implantar en SOD?

Consistencia  Causal 

• Como se  vio en la segunda unidad la sincronización  del tiempo es complicado en SOD, por  este motivo se sugiere que la consistencia  de los datos modificados sea de forma  causal.

• Si un  proceso desea leer (read) un dato en  memoria existirá siempre un proceso que  haya escrito (write) previamente en memoria.  De esta forma siempre se tiene el  último valor escrito.

Consistencia  Causal 

• Si dos  procesos escriben espontáneamente y simultáneamente  una variable, estos accesos no están  relacionados causalmente.

• La implementación  de este esquema se da a través de  grafos de dependencia para determinar cuáles  operaciones son dependientes de otras y  cuáles son concurrentes.

Consistencia  Secuencial 

• Fue propuesta  por Lamport en 1977 y basa su funcionamiento  en que la consistencia estricta es prácticamente  imposible de implementar en un sistema  distribuido y que la experiencia demuestra  que a un programador le bastan modelos  más débiles.

• Este modelo  basa su funcionamiento en ordenar (“seriabilizar”)  los accesos de memoria, de esta forma  se evitan inconsistencias.

Consistencia  Secuencial 

• Se necesita  de un coordinador central que maneje la  secuencialidad de las operaciones.

• La principal  problemática es que el orden impuesto  puede ser diferente al orden real o  deseado.

• En muchos  casos el problema de la seriabilización  es no determinista.

Consistencia  Secuencial 

• Dos ejecuciones del mismo programa podrían no arrojar el mismo resultado a menos que se utilicen operaciones explicitas de sincronización

Consistencia  PRAM 

• El modelo  Pipelined RAM basa su funcionamiento en  que las escrituras realizadas por un proceso, son recibidas por el resto en el orden en el cual éstas fueron ejecutadas, no obstante, las escrituras realizadas por diferentes procesos pueden ser vistas en órdenes diferentes por todos ellos.

Consistencia  PRAM 

• Tanto  P1 como P2 escriben datos, al mismo  tiempo P3 y P4 leen los valores,  como P3 depende de P2 el primer valor  es el último escrito aunque puede visualizar  después el otro valor de P1. P4  depende de P1 por eso tiene el primer  valor, pero puede acceder al del otro  proceso.

P1:  W(x)1                            
P3:                                          R(x)2   R(x)1 
P2:               R(x)1  W(x)2  
P4:                                         R(x)1   R(x)2 
Una sucesión  correcta de 
eventos 
con Consistencia  PRAM
Consistencia  Débil 

• Fue propuesta  por Dubois en 1986 y basa su funcionamiento  en que los modelos anteriores de consistencia  se consideran aún restrictivos porque requieren  que las escrituras de un proceso se  vean en orden.  

• Esto no  siempre es necesario. Por ejemplo, cuando  se está en una región crítica no  es necesario propagar valores intermedios sino  los valores finales.

• Para poder  implantar este modelo se necesita de una  variable de sincronización.

• Los accesos  a las variables de sincronización son  secuencialmente consistentes:  todos los procesos  ven todos los accesos a las variables  de sincronización en el mismo orden. 

• No se  permite el acceso a ninguna variable de  sincronización hasta que todas las escrituras  previas se hayan completado: Hacer una  sincronizacion después de operaciones de escritura  obliga a que los nuevos valores se  propaguen a todas las memorias.

• El hacer  una operación de sincronización antes de  leer los datos,  le garantiza  a  un proceso que leerá los últimos valores. 

• Además,  la operación de sincronización garantiza  que las escrituras locales sean propagadas  a todas las otras máquinas y se  actualiza la memoria actual con escrituras  hechas remotamente.

• Existen  variantes a este modelo como los modelos  de consistencia relajada, de liberación y  de entrada por mencionar algunos. 

4.3  MCD en base a páginas. 

• En este  esquema se tiene un único espacio de  direcciones virtuales para todo el sistema.

• Cuando  ocurre un fallo de página implica acceder  a memoria disponible en otra computadora.  La idea es que los programas no deban  de ser modificados.

• Un ejemplo  de este esquema es el sistema Igvy.

Esquema general de MCD  basada en páginas

• Se recomienda  tener múltiples copias de páginas para mejorar rendimiento*

• Cada página  tiene asociado:
• Un estado: R (sólo lectura) o W (lectura/escritura)
• Un propietario: el último proceso que la modificó

• Página  W sólo 1 copia en máquina propietaria

• Página  R copia en varias máquinas (1 propietaria)

• Lectura:
• Si tiene copia local: lee de la misma
• Si no: la solicita a propietario y la marca R
• Si el propietario la tenía W, la pasa a R (degradación)

• Otros  factores a considerar son:

• Replicación
• Estructura
• Localización de los datos
• Políticas de escritura
• Política de reemplazo de páginas
• Modelos de consistencia

• Se recomienda  replicar sólo las páginas R o bien,  todas las páginas con la problemática  de la reintegración.

• En cuestión  de localización de los datos se debe  tomar en cuenta si se va a hacer  local, esquema centralizado o distribuido.

• En cuanto  a políticas de reemplazo se utiliza ampliamente  LRU.

4.4  MCD en base a variables. 

• En este  esquema la granularidad es más fina ya  que sólo se comparten variables que han  sido marcados previamente en el código  del programa.

• Tanto  el compilador como el entorno de ejecución  se encargan del acceso y compartición  de las variables compartidas.

• Ejemplos:  Munin y Midway 

• Se recomienda  la duplicación. Ésta puede ser parcial  o total.

• El Algoritmo  de actualización es sumamente importante.

• No hay  compartición falsa dado que todos los procesos acceden a datos protegidos y consistentes dado que la variable compartida monitoriza los accesos de escritura.

Munin 

• Se basa  en objetos del software (usa MMU).

• Declaraciones  con “shared”.

• Una variable compartida por página (por defecto).
• Instrucciones normales de lectura y escritura.
• No hay métodos de protección especiales.

Munin 

• Se manejan  regiones críticas.

• Clases  de variables:
• Variables ordinarias.
• Variables de datos compartidos.
• Variables de sincronización.

Munin 

• Categorías  de variables:
• Exclusiva para lectura.
• Migratoria.
• De escritura compartida.
• Convencional.

Midway 

• Compartir  estructuras de datos individuales.

• C, C++  o ML convencional con información adicional.

• Mantiene  consistentes las variables compartidas de manera  eficiente.

4.5  MCD en base a objetos. 

• Nace como  respuesta a la creciente popularización de  los lenguajes orientados por objetos.

• Los datos  se organizan y son transportados en unidades  de objetos, no unidades de páginas.

• Ejemplos:  Linda y Orca

¿Qué son los objetos? 

• Estructura  de datos encapsulada definida por el programador.

• Se componen  de datos internos (estado) y operaciones  o métodos.

• Cumplen  con la propiedad de ocultamiento de la información, por lo que contribuyen con la modularidad.

• No existe una memoria lineal en bruto.

• La localización y administración de los objetos es controlada por el sistema de tiempo de ejecución.

• Los objetos  se pueden duplicar o no.  En caso  de duplicarse, hay que decidir cómo    se harán las actualizaciones.

• Evitan  el compartimiento falso.

• Sus principales  desventajas son que no soportan programas  multiprocesadores antiguos y el costo adicional  que genera el acceso indirecto a los  datos.

El  Sistema Linda 

• El acceso  a memoria se hace mediante un pequeño  conjunto de primitivas que se agregan  a los lenguajes existentes.

• Las ventajas  son que no hay que aprender un nuevo  lenguaje, es sencillo de implantar y es  portable.

• Se basa  en un espacio de n-adas global a  todo el sistema.

Las  n-adas de Linda 

• Son análogas  a las estructuras de C.

• Las operaciones  sobre ellas son restringidas;     sólo se soportan cuatro operaciones:

          out(“matrix-I”, i, j, 3.14)
          in(“abc”, 2, ?i)
          read(“abc”, 2, ?i)
          eval(X,Y,Z), con X,Y,Z expresiones.
El  Sistema Orca 

• El acceso  a memoria se basa en un esquema de  objetos protegidos.

• Consta  del lenguaje, el compilador y el sistema  de tiempo de ejecución.

• Se basa  en Módula 2.

• Los objetos son pasivos y no se soporta la herencia.

El  Sistema Orca 

• Cada operación  consta de una lista (protección, bloque  de enunciados).

• Cuenta  con una operación fork, en la que se basa la distribución de objetos.

• Las operaciones son atómicas y secuencialmente consistentes.

• Usa sincronización de la exclusión mutua y sincronización de condiciones.