document4
DESCRIPTION
.TRANSCRIPT
INSTITUTO TECNOLÓGICO SUPERIOR DE CINTALAPA “Ciencia y tecnología al servicio de la comunidad”
Integrantes:
• CARRASCO TOLEDO MAYRA
• DIAZ ESPINOSA EDUARDO
• DOMINGUEZ RAMIREZ JESUS IVAN
• HERNANDEZ LOPEZ NOEMI
• POZO PEREZ DANIELA GUADALUPE
Catedrático: ING. ROQUEZ FARRERA
Asignatura: SIETAMAS OPERATIVO II
Área: INGENIERÍA INFORMÁTICA
Semestre: QUINTO Grupo: “E”
Actividad: INVESTIGACIÓN
Periodo: AGOSTÓ –DICIEMBRE 2015
4.1 Configuraciones de memoria compartida distribuida: de
circuitos, basada en bus, anillo o con conmutador.
Los sistemas de memoria compartida distribuida (DSM) representan la creación
hibrida de dos tipos de computación paralelos: la memoria distribuida en sistemas
multiprocesador y los sistemas distribuidos. Ellos proveen la abstracción de
memoria compartida en sistemas con memorias distribuidas físicamente y
consecuentemente combinan las mejores características de ambos enfoques.
Debido a esto, el concepto de memoria compartida distribuida es reconocido como
uno de los enfoques más atractivos para la creación de sistemas escalables, de alto
rendimiento de sistemas multiprocesador.
Multiprocesadores basados en un bus.
Para evitar que dos o más CPU’s intenten el acceso a la memoria al mismo tiempo,
se necesita algún tipo de arbitraje del bus. El CPU debe pedir permiso para
conseguir el bus. La concesión puede hacerse de forma centralizada, utilizando un
dispositivo de arbitraje de bus, o de forma descentralizada, donde el primer CPU
que realice una solicitud en el bus ganará cualquier conflicto.
La desventaja es la sobrecarga del bus.
Una solución sería equipar a cada CPU con un caché husmeador.
Un protocolo en particular común es el de escritura a través del caché. Cuando un
CPU lee por primera vez una palabra de memoria, esa palabra es llevada por el bus
y guardada en el caché del CPU solicitante.
Puede suceder que una palabra en particular se oculte en dos o más CPU al mismo
tiempo.
Operación de lectura.
Si la palabra no está en el caché, entonces buscarla en la memoria y copiarla a su
caché.
Si la palabra está en el caché, tomar el dato de ahí.
Operación de escritura
Si ningún CPU tiene la palabra en su caché, entonces la palabra es actualizada en
memoria, como si el ocultamiento no hubiera sido utilizado.
Si el CPU (que realiza la escritura) tiene la única copia de la palabra, se actualiza
su caché y también la memoria mediante el bus.
Si dos o más CPU tienen la palabra, entonces se actualiza la palabra en el caché y
en la memoria, y se invalidan las entradas de esa palabra en los cachés de los otros
CPU. Así la palabra sólo la tendrá la memoria y un solo caché. Una alternativa a
invalidar otras entradas de caché es actualizarlas todas, pero esto puede resultar
más lento.
Una ventaja de este protocolo es que es fácil de entender e implantar, la desventaja
es que todas las escrituras utilizan el bus.
Existe otro tipo de protocolos como el protocolo de membresía. Una versión de este
protocolo plantea lo siguiente. Se manejan bloques de caché, cada uno de los
cuales puede estar en uno de los siguientes estados:
1. INVALIDO: Este bloque de caché no contiene datos válidos.
2. LIMPIO: La memoria está actualizada, el bloque puede estar en otros cachés.
3. SUCIO: La memoria es incorrecta; ningún otro caché puede contener al bloque.
La palabra permanece el estado SUCIO hasta que se elimine del caché donde se
encuentra en la actualidad por razones de espacio. En este momento, desaparece
de todos los cachés y se escribe en la memoria. Este protocolo tiene tres
propiedades importantes:
1. La consistencia se logra haciendo que todos los cachés husmeen el bus.
2. El protocolo se integra dentro de la unidad de administración de memoria.
3. Todo el algoritmo se realiza en un ciclo de memoria.
La desventaja es que no funciona para multiprocesadores de mayor tamaño y nada
es válido para la memoria compartida distribuida.
Multiprocesadores basados en un anillo
Ejemplo: Memnet
En Memnet, un espacio de direcciones se divide en una parte privada y una
compartida. La parte compartida se divide en bloques de 32 bytes, unidad mediante
la cual se realizan las transferencias entre las máquinas. Las máquinas Memnet
están conectadas mediante un anillo de fichas modificado. El anillo consta de 20
cables paralelos, que juntos permiten enviar 16 bits de datos y 4 bits de control cada
100 nanosegundos, para una velocidad de datos de 160 Mb/seg. Un bloque
exclusivo de lectura puede estar presente en varias máquinas, uno de lectura-
escritura debe estar presente en una sola máquina.Los bits en el dispositivo Memnet
indican uno o más de los siguientes estados:
1. VALIDO: El bloque está presente en el caché y está actualizado.
2. EXCLUSIVO: La copia local es la única.
3. ORIGEN: Se activa si ésta es la máquina origen del bloque.
4. INTERRUPCION: Se utiliza para forzar interrupciones.
5. POSICION: Indica la localización del bloque en el caché si está presente y es
válido.
6. Protocolo Memnet.
7. Lectura.
Cuando un CPU desea leer una palabra de la memoria compartida, la dirección de
memoria por leer se transfiere al dispositivo Memnet, el cual verifica la tabla del
bloque para ver si está presente. Si es así, la solicitud es satisfecha de inmediato.
En caso contrario, el dispositivo Memnet espera hasta capturar la ficha que circula;
después, coloca un paquete de solicitud en el anillo y suspende el CPU. El paquete
de solicitud contiene la dirección deseada y un campo vacío de 32 bytes.
Cada dispositivo Memnet en el anillo verifica si tiene el bloque. De ser así, coloca el
bloque en el campo vacío y modifica el encabezado del paquete para inhibir la
acción de las máquinas posteriores.
Si el bit exclusivo del bloque está activo, se limpia. Cuando el paquete regresa al
emisor, se garantiza que contiene al bloque solicitado. El CPU que envía la solicitud
guarda el bloque, satisface la solicitud y libera al CPU.
Si la máquina solicitante no tiene espacio libre en su caché para contener el bloque
recibido, entonces toma al azar un bloque oculto y lo envía a su origen, con lo que
libera un espacio de caché. Los bloques cuyo bit origen están activados nunca se
eligen, pues se encuentran en su origen.
Escritura.
Tenemos tres casos:
A. Si el bloque contiene la palabra por escribir está presente y es la única copia en
el sistema, (el bit exclusivo está activado) la palabra solo se escribe de manera local.
B. Si está presente el bloque, pero no es la única copia, se envía primero un paquete
de invalidación por el anillo para que las otras máquinas desechen sus copias del
bloque por escribir. Cuando el paquete de invalidación regresa al solicitante, el bit
exclusivo se activa para ese bloque y se procede a la escritura local.
C. Si el bloque no está presente, se envía un paquete que combina una solicitud de
lectura y una de invalidación. La primera máquina que tenga el bloque lo copia en
el paquete y desecha su copia. Todas las máquinas posteriores solo desechan el
bloque de sus cachés. Cuando el paquete regresa al emisor, éste lo guarda y
escribe en él.
La ventaja de este protocolo es que se puede aplicar a multicomputadoras.
Principales Aproximaciones a DSM
Existen tres aproximaciones a la implementación de memoria compartida
distribuida, las cuales involucran el uso de hardware, memoria virtual o bibliotecas
de soporte. Estos no son mutuamente exclusivas necesariamente.
Basada en hardware. Por ejemplo Dash y PLUS. El conjunto de procesadores y los
módulos de memoria están conectados vía una red de alta velocidad. El problema
es la escalabilidad.
Basado en páginas. Por ejemplo Ivy, Munin, Mirage, Clouds, Choices, COOL y
Mether, todas implanta DSM como una región de memoria virtual que ocupa el
mismo rango de dirección en el espacio de direcciones de cada proceso
participante. En cada caso el kernel mantiene la consistencia de datos dentro de las
regiones DSM como parte del manejo de fallo de página.
4.2 Modelos de consistencia: Estricta, causal, secuencial, débil, de
liberación, y de entrada.
Un modelo de consistencia es esencialmente un contrato entre procesos y el
almacenamiento de datos. Es decir: si los procesos acuerdan obedecer ciertas
reglas, el almacenamiento promete trabajar correctamente.
Normalmente un proceso que realiza una operación de lectura espera que esa
operación devuelva un valor que refleje el resultado de la última operación de
escritura sobre el dato.
En Informática, en un sistema distribuido, tales como una memoria compartida
distribuida o almacenes de datos distribuido, tales como una base de datos, sistema
de archivos, caché web o sistemas de replicación optimista, hay una serie de
posibles modelos de consistencia de datos. Se dice que un sistema soporta un
determinado modelo, si las operaciones en memoria siguen normas específicas. La
consistencia de los datos es definida entre el programador y el sistema, que
garantiza que si el programador sigue las reglas, la memoria será consistente y el
resultado de las operaciones de memoria será predecible.
Los lenguajes de alto nivel, tales como C, C++ y Java, respetan parcialmente este
modelo traduciendo operaciones de memoria en operaciones de bajo nivel para
preservar la memoria semántica. Para mantener el modelo, los compiladores
pueden reordenar algunas instrucciones de memoria, y las llamadas a las
bibliotecas como pthread_mutex_lock(), encapsular la sincronización necesaria.
Los ejemplos incluyen:
Linealizable (también conocido como el estricta o consistencia
atómica)
Consistencia secuencial
Consistencia de causalidad
Consistencia liberada
Consistencia eventual
Consistencia delta
Consistencia PRAM (también conocido como consistencia FIFO)
Consistencia débil
Consistencia vector campo
La duplicidad de los bloques compartidos aumenta el rendimiento, pero produce un
problema de consistencia entre las diferentes copias de la página en caso de una
escritura.
Si con cada escritura es necesario actualizar todas las copias, el envío de las
páginas por la red provoca que el tiempo de espera aumente demasiado,
convirtiendo este método en impracticable
Consistencia Casual
La condición a cumplir para que unos datos sean causalmente consistentes es:
Escrituras que están potencialmente relacionadas en forma causal deben ser vistas
por todos los procesos en el mismo orden.
Escrituras concurrentes pueden ser vistas en un orden diferente sobre diferentes
máquinas.
Es permitida con un almacenamiento causalmente consistente, pero no con un
almacenamiento secuencialmente consistente o con un almacenamiento
consistente en forma estricta.
Consistencia Secuencial
La consistencia secuencial es una forma ligeramente más débil de la consistencia
estricta. Satisface la siguiente condición:
El resultado de una ejecución es el mismo si las operaciones (lectura y escritura) de
todos los procesos sobre el dato fueron ejecutadas en algún orden secuencial
Un dato almacenado secuencialmente consistente.
Un dato almacenado que no es secuencialmente consistente.
Consistencia Débil
Los accesos a variables de sincronización asociadas con los datos almacenados
son secuencialmente consistentes.
Propiedades
No se permite operación sobre una variable de sincronización hasta que todas las
escrituras previas de hayan completado.
No se permiten operaciones de escritura o lectura sobre datos hasta que no se
hayan completado operaciones previas sobre variables de sincronización.
Consistencia de Liberación
Se basa en el supuesto de que los accesos a variables compartidas se protegen en
secciones críticas empleando primitivas de sincronización, como por ejemplo locks.
En tal caso, todo acceso esta precedido por una operación adquiere y seguido por
una operación release. Es responsabilidad del programador que esta propiedad se
cumpla en todos los programas.
Consistencia Estricta
Está definido por la siguiente condición: Cualquier lectura a una localidad de
memoria x regresa el valor guardado por la operación de escritura más reciente en
x Esta definición supone la existencia de un tiempo global absoluto (como en la
física de Newton), para que la determinación del evento "más reciente" no sea
ambigua. Esta consistencia es típica de sistemas uniprocesador, donde nunca se
pueden presentar dos eventos simultáneamente. Sin embargo es prácticamente
imposible de lograr en sistemas multiprocesador (distribuidos o no), debido a que
pueden existir escrituras y lecturas en memoria separadas por espacios mínimos de
tiempo que no alcanzan a cumplir la condición exigida.
4.3 Memoria compartida distribuida en base a páginas: Diseño,
replica, granulada, consistencia, propietario, y copias.
El esquema de DSM propone un espacio de direcciones de memoria virtual que
integra la memoria de todas las computadoras del sistema, y su uso se realiza
mediante paginación. Las páginas quedan restringidas a estar necesariamente en
un único nodo. Cuando un programa intenta acceder a una posición virtual de
memoria, se comprueba si esa página se encuentra de forma local. Si no se
encuentra, se provoca un fallo de página, y el sistema operativo solicita la página al
resto de nodos. El sistema funciona de forma análoga al sistema de memoria virtual
tradicional, pero en este caso los fallos de página se propagan al resto de
ordenadores, hasta que la petición llega al nodo que tiene la página virtual solicitada
en su memoria local. A primera vista este sistema parece más eficiente que el
acceso a la memoria virtual en disco, pero en la realidad ha mostrado ser un sistema
demasiado lento en ciertas aplicaciones, ya que provoca un tráfico de páginas
excesivo.
Una mejora dirigida a mejorar el rendimiento sugiere dividir el espacio de
direcciones en una zona local y privada y una zona de memoria compartida, que se
usará únicamente por procesos que necesiten compartir datos. Esta abstracción se
acerca a la idea de programación mediante la declaración explícita de datos
públicos y privados, y minimiza el envío de información, ya que sólo se enviarán los
datos que realmente vayan a compartirse.
El sistema operativo, y en el caso del protocolo de consistencia de entrada, por
acciones de sincronización explícitas dentro del código del usuario. El hecho que la
especificación se encuentre dispersa dificulta tanto la incorporación de nuevos
protocolos de consistencia como la modificación de los ya existentes, debido a que
los componentes tienen además de su funcionalidad básica responsabilidades que
no les corresponden.
Hay dos razones principales para la replicación de datos:
Confiabilidad
Continuidad de trabajo ante caída de la réplica, mayor cantidad de copias mejor
protección contra la corrupción de datos.
Rendimiento
El SD escala en número
Escala en área geográfica (disminuye el tiempo de acceso al dato) Consulta
simultánea de los mismos datos.
Granularidad
Se refiere a la especificidad a la que se define un nivel de detalle en una tabla, es
decir, si hablamos de una jerarquía la granularidad empieza por la parte más alta
de la jerarquía, siendo la granularidad mínima, el nivel más bajo.
4.4 Memoria compartida distribuida en base a variables
En los MCD basados en variables busca evitar la compartición falsa ejecutando un
programa en cada CPU que se comunica con una central, la que le provee de
variables compartidas, administrando este cualquier tipo de variable, poniendo
variables grandes en varias páginas o en la misma página muchas variables del
mismo tipo, en este protocolo es muy importante declarar las variables compartidas.
La compartición falsa se produce cuando dos procesos se pelean el acceso a la
misma página de memoria, ya que contiene variables que requieren los dos, pero
estas no son las mismas. Esto pasa por un mal diseño del tamaño de las páginas y
por la poca relación existente entre variables de la misma página.
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.
Se manejan regiones críticas.
Clases de variables:
Variables ordinarias.
Variables de datos compartidos.
Variables de sincronización.
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 Memoria compartida distribuida en base a objetos
En los MCD basados en objetos se busca el acceso a datos por medio de la
encapsulación de la información y repartida a través de la red, estos objetos serán
definidos por el Programador y las CPU´s cambiaran los estados según procedan
con los accesos. 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
Una alternativa al uso de páginas es tomar el objeto como base de la transferencia
de memoria. Aunque el control de la memoria resulta más complejo, el resultado es
al mismo tiempo modular y flexible, y la sincronización y el acceso se pueden
integrar limpiamente. Otra de las restricciones de este modelo es que todos los
accesos a los objetos compartidos han de realizarse mediante llamadas a los
métodos de los objetos, con lo que no se admiten programas no modulares y se
consideran incompatibles.
Ventajas:
Es más modular que otras técnicas.
La implementación es más flexible por que los accesos son controlados.
Sincronización y accesos se pueden integrar juntos, más fácilmente
Desventajas:
No corre en viejos programas para multiprocesadores.
Los accesos se deben hacer invocando a los accesos, lo que significa más trabajo
que los métodos de páginas compartidas.
Ejemplos: Linda y Orca
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.
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 nada global a todo el sistema.
Las nada 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.
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.
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.
¿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 dela 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.
Una alternativa al uso de páginas es tomar el objeto como base de la transferencia
de memoria. Aunque el control de la memoria resulta más complejo, el resultado es
al mismo tiempo modular y flexible, y la sincronización y el acceso se pueden
integrar limpiamente. Otra de las restricciones de este modelo es que todos los
accesos a los objetos compartidos han de realizarse mediante llamadas a los
métodos de los objetos, con lo que no se admiten programas no modulares y se
consideran incompatibles.