Download Sistemas Operativos II

Memoria Compartida
Distribuida
M.C. Juan Carlos Olivares Rojas
[email protected]
http://antares.itmorelia.edu.mx/~jcolivar
Julio, 2009
Agenda
• 4.1 Configuraciones de MCD.
•
•
•
•
4.2 Modelos de consistencia.
4.3 MCD en base a páginas.
4.4 MCD en base a variables.
4.5 MCD en base a objetos.
Memoria
• Una de las principales características de una
computadora es la capacidad que tienen para
almacenar datos e información.
• El primero en tener la idea de almacenar un
programa en una computadora fue Jonh Von
Neumman (participante en la ENIAC).
• Él utilizó la memoria para almacenar datos y
programas.
Memoria
• El
otro
modelo
de
arquitectura
de
computadoras conocida como Arquitectura
Harvard, existe una memoria especial para
datos y otra memoria para programas. Esto
hace que los circuitos sean más eficientes pero
más costosos a la vez.
• La gran mayoría de la computadoras
(incluyendo las PC) utilizan la arquitectura Von
Neumman.
Concepto de memoria
• La memoria principal puede ser considerada
como un arreglo lineal de localidades de
almacenamiento de un byte de tamaño. Cada
localidad de almacenamiento tiene asignada
una dirección que la identifica.
• La memoria principal es el lugar donde el CPU
lee las instrucciones a ejecutar, así como
algunos datos a emplear.
Memoria
Memoria
• ¿Por qué es importante la memoria?
• Programas = Algoritmos + Estructuras de Datos
• Estructuras de Datos (pilas, listas, colas, etc.)
son memoria.
Memoria
Memoria
• La memoria se puede ver como un casillero en
el cual se almacena información.
• La memoria puede ser estática o dinámica
dependiendo de cómo se gestione.
• La memoria está divida en secciones de
código, datos estáticos, Pila y el Heap
(monton).
Memoria
Conceptos de memoria
• Todo sistema operativo tiene un mapa de
memoria que indica como están administrada la
memoria y que partes se pueden ocupar.
• La filosofía del administrador de memoria
consiste en optimizar el uso de este recurso, ya
que la memoria es uno de los componentes
críticos de todo sistema de cómputo.
Mapa de Memoria
Memoria
• La principal problemática de la memoria
principal es que no es persistente. Por este
motivo se tienen que implementar estrategias
de almacenamiento y recuperación de
información.
• Las operaciones básicas que se realizan sobre
una memoria son dos: lectura (r) y escritura
(w).
Memoria
• Las operaciones anteriores son a nivel usuario.
A nivel sistema se tienen llamadas al sistema
como malloc, free, allocate, etc. También debe
proporcionar
opciones
de
bloqueo
y
desbloqueo (protección).
• La ley de Parkinson dice: “los programas se
expanden hasta llenar la memoria disponible
para contenerlos”.
Memoria
• No por tener el doble de memoria instalada en
un sistema legado, este será el doble de
rápido.
• La memoria física es utilizado por muchos
procesos en lugar de la memoria virtual.
• Todo proceso necesita memoria física para
poderse ejecutar.
Administrador de memoria
• Sirve para tener un control sobre los lugares
donde están almacenados los procesos y datos
que actualmente se están utilizando.
• Las políticas de administración de memoria
generalmente son duras, es decir no
modificables, pero se pueden configurar
algunos parámetros para su mejor uso.
Administrador de Disponibilidad
Ejemplos de memoria
• Las tendencias actuales sobre el manejo de
memoria indican el uso en diversas
aplicaciones:
• Portapapeles: permite guardar
transferirlo a otros programas.
datos
y
• Uso de base de datos en memoria. Algunas
versiones de MySQL Lite permiten hacerlo.
Ejemplos de memoria
• Las computadoras actuales permiten guardar
los datos al apagar una computadora, para
tener un mejor desempeño (hibernación,
suspensión).
• Los punteros permiten desplazarnos por las
localidades de memoria. Una variable es una
localidad de memoria.
Mecanismos de Asignación
• Un mecanismo de asignación determina la
cantidad de bloques (particiones) que serán
administrados en la memoria.
• El esquema básico de asignación consiste en
particionar (dividir) la memoria en diferentes
partes.
• Existen 3 mecanismos de Asignación:
Asignación de una partición
Asignación de dos particiones
Asignación de Múltiples Particiones
Estrategias de asignación de memoria
• Una estrategia de asignación de memoria determina
el lugar donde será cargado un nuevo proceso en
base a un criterio. Las estrategias de asignación son:
•
•
•
•
Primer ajuste.
Siguiente ajuste
Mejor ajuste
Peor ajuste
Complejidad de los mecanismos y
estrategias de asignación
• Cualquier método para manejar la disponibilidad de la
memoria presenta inconvenientes como:
•
•
•
•
Fragmentación
Overhead
Relocalización de programas
Trashing (sacar un programa inmediatamente
después de haber sido asignado memoria)
Segmentación
Paginación
Paginación
Concepto de Memoria virtual
• Es un método mediante el cual, un sistema operativo
simula tener mas memoria principal que la que existe
físicamente. Para implementar la memoria virtual se
utiliza un medio de almacenamiento secundario de
alta velocidad de acceso, generalmente en disco duro
de la maquina.
• Se utiliza la paginación como método de
administración de memoria básica y algún mecanismo
de intercambio.
Espacio de Direcciones en
Windows
• Espacio de Direcciones de
32-bit (4 GB)
– 2 GB espacio de usuarios
– 2 GB sistema operativo
• Espacio de Direcciones de
64-bit
– 7192 GB espacio de usuario
(Itanium)
– 8192 GB espacione de
usuario (x64)
– ~6000 GB sistema operativo
Espacio de Direcciones
De 32-bit
Único por proceso
2 GB
Espacio de
Procesos
de Usuario
Systemwide
2 GB Sistema
Kernel/HAL
drivers
Sistema
de cache
Mecanismos de Memoria Virtual
• Existen 2 métodos para cargar programas en
memoria:
• Demanda de página: consiste en iniciar la
ejecución de los procesos sin páginas
cargadas, estas se irán cargando conforme el
proceso las demande.
• Prepaginación: consiste en que el sistema
operativo predice cuales páginas se ocuparán
durante la ejecución de un proceso.
Algoritmos de descarga (Reemplazo)
• Se utiliza para determinar cuales páginas serán
descargadas hacia el disco duro cuando se
quiera cargar nuevas paginas y no haya
memoria libre. Existen 3 algoritmos básicos:
• MIN
• FIFO
• LRU
Swap
• El swap es la forma en como se intercambia
una partición de memoria por otra.
Generalmente se utiliza en técnicas basadas
en paginación.
• Se ocupa de una administración adecuada del
sistema de archivos para permitir paginación.
Swap
• Un ejemplo claro de intercambio es la famosa
función de intercambio
int swap(int a, int b) {
int aux = a;
a = b;
b = aux;
}
Agenda
• 4.1.1 De circuitos, basados en bus, anillo o con
conmutador.
Memoria Compartida Distribuida
• 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.
Memoria Compartida Distribuida
• 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.
Memoria Compartida Distribuida
Distributed shared memory
DSM appears as
memory in address
space of proces s
Process
accessing DSM
Phy sical
memory
Phy sical
memory
Phy sical
memory
Visión general de la MCD
Memoria Compartida Distribuida
• 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).
Memoria Compartida Distribuida
Memoria Compartida Distribuida
• 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.
Memoria Compartida Distribuida
Replicación
(a)
páginas
distribuidas en 4
máquinas
(b) CPU 0 lee página
10
(c) CPU 1 lee página
10
Memoria Compartida Distribuida
• 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.
Memoria compartida
#include <sys/shm.h>
int shmget(key, size, shmflg);
int shmid;
if((shmid
=
shmget(IPC_PRIVATE,
IPC_CREAT | 0600)) == -1)
/*Error al crear memoria compartida*/
4096,
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);
Memoria compartida
char *shmat(shmid, shmaddr, shmflg);
int shmdt(shmaddr);
float *memoria;
shmid = shmget(llave, MAX
IPC_CREAT | 0600);
memoria = shmat(shmid, 0, 0);
/*Operar memoria*/
shmdt(memoria);
shmctl(shmid, IPC_RMID, 0);
*
sizeof(float),
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)
MCD basa en circuitos
Arquitecturas de MCD
• ¿Diferencias entre UMA y NUMA?
• 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 bus
MCD basada en anillo
Arquitecturas de MCD
• 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. Cuando se
realiza una operación de memoria se intenta
realizar dentro del grupo, de lo contrario pasa al
conmutador para que lo redireccione a otro
grupo.
• No existe un arquitectura de MCD óptima.
MCD basada en conmutador
Agenda
• 4.1 Configuraciones de MCD.
• 4.2 Modelos de consistencia.
• 4.3 MCD en base a páginas.
• 4.4 MCD en base a variables.
• 4.5 MCD en base a objetos.
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.
Modelos de Consistencia
• 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.
Agenda
• 4.2.1 Estricta, causal, secuencial, débil, de
liberación y de entrada.
Consistencia Estricta
• Este modelo es el más robusto
sumamente difícil de implementar.
pero
• 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.
Consistencia Estricta
• 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
sincronización del tiempo es complicado
SOD, por este motivo se sugiere que
consistencia de los datos modificados sea
forma causal.
la
en
la
de
• 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
través de grafos de dependencia
determinar
cuáles
operaciones
dependientes de otras y cuáles
concurrentes.
da a
para
son
son
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
seriabilización es no determinista.
de
la
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
P2:
P3:
P4:
R(x)1 W(x)2
R(x)2 R(x)1
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.
Consistencia Débil
• 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.
Consistencia Débil
• 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.
Consistencia Débil
• 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.
Agenda
• 4.1 Configuraciones de MCD.
• 4.2 Modelos de consistencia.
• 4.3 MCD en base a páginas.
• 4.4 MCD en base a variables.
• 4.5 MCD en base a objetos.
Agenda
• 4.3.1
Diseño,
replica,
granularidad,
consistencia, propietario y copias.
MCD basada en 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.
MCD basada en páginas
Process access ing
paged DSM s egment
Kernel redirec ts
page faults to
us er-lev el
handler
Kernel
Pages transferred over network
Esquema general de MCD basada en páginas
Diseño 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
Diseño de MCD basada en Páginas
• 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)
Diseño de MCD basada en páginas
• 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
Diseño de MCD basada en páginas
• 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.
Agenda
• 4.1 Configuraciones de MCD.
• 4.2 Modelos de consistencia.
• 4.3 MCD en base a páginas.
• 4.4 MCD en base a variables.
• 4.5 MCD en base a objetos.
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
MCD en base a variables
• 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
compartidas de manera eficiente.
variables
Agenda
•
•
•
•
4.1 Configuraciones de MCD.
4.2 Modelos de consistencia.
4.3 MCD en base a páginas.
4.4 MCD en base a variables.
• 4.5 MCD en base a objetos.
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.
MCD basados en objetos
• 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.
MCD basado en Objetos
• 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
basa la distribución de objetos.
• Las
operaciones
son
secuencialmente consistentes.
atómicas
se
y
• Usa sincronización de la exclusión mutua y
sincronización de condiciones.
Referencias
• Márquez,
Francisco
Programación Avanzada.
México, Alfaomega Ra-Ma.
(2004).
Tercera
UNIX
edición,
• Colouris, George, Dollimore, Jean, Kindberg,
Tim (2001). Sistemas Distribuidos Conceptos y
Diseño. 3a. Edición. España, Pearson AddisonWesley.
Referencias
• Deitel, Harvey, Deitel, Paul (2004). Java Como
Programar. Quinta Edición. México, Pearson
Prentice Hall.
• Tanenbaum,
Andrew
(1996).
Sistemas
Operativos Distribuidos. México, Prentice Hall.
• Tanenbaum, Andrew, Van Steen, Maarten
(2006). Distributed Systems Principles and
Paradigms. Estados Unidos, Pearson Prentice
Hall.
Referencias
• Solomo, D. y Polze, A. (2009), Windows
Operating System Internals.
• Tutorial de Sistemas Operativos 2. (2009)
Instituto
Tecnológico
de
la
Paz.
http://sistemas.itlp.edu.mx/tutoriales/sistemasop
erativos2/
• Cardinale, Y. (2009) Memoria Compartida
Distribuidad, Universidad Simón Bolívar.