Make your own free website on Tripod.com

Jorge Amo, Daniel Capuzzi, Gustavo Cardenas, Jose Leitao, Andres Vasquez

 

Memoria compartida distribuida

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 mas atractivos para la creación de sistemas escalables, de alto rendimiento de sistemas multiprocesador.

Memoria compartida basada en páginas

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.

Memoria compartida basada en objetos

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 / DESVENTAJAS DE LA MEMORIA DISTRIBUIDA

Ventajas:

Desventajas:

 

IMPLEMENTACION DE UNA MEMORIA DISTRIBUIDA

Acceso compartido a la memoria à comunicación Inter-procesos.

Ningún procesador puede acceder directamente a la memoria de otro procesador à NORMA (NO Remote Memory Access) Systems.

Los procesadores hacen referencia a su propia memoria local. Hay que aumentar software para que, cuando un procesador haga referencia a una página remota, esta página sea recuperada.

El espacio de direccionamiento común es particionado en pedazos.

Cada pedazo es situado en una estación.

Cuando un procesador hace referencia a una pagina no local à "trap" (page fault).

 

Figura 1. Ejemplo de implementación de memoria distribuida.

 

Procesos y Procesadores en un sistema distribuido:

 Un proceso es un programa en ejecución, es una actividad de cierto tipo, que contiene un programa, entradas salidas y estados.

(Entrada --àProceso--àSalida)

Los procesos pueden ser cooperantes o independientes:

Un proceso puede estar en cualquiera de los siguientes tres estados:

Los procesos que se encuentran en estado listo son los que pueden pasar a ejecución. Los que se encuentran en estado de ejecución solo los que se estan ejecutando en el procesador en un determinado momento y los procesos que se encuentran en estado de bloqueado son los que están esperando respuesta de algún otro proceso, o le hace falta algún recurso para poder ser ejecutados.

Características de los procesos:

-         Cantidad de Entrada/Salida: Existen procesos que realizan una gran cantidad de operaciones de entrada y salida (aplicaciones de bases de datos, por ejemplo).

-         Cantidad de Uso de CPU: Existen procesos que no realizan muchas operaciones de entrada y salida, sino que usan intensivamente la unidad central de procesamiento. Por ejemplo, operaciones con matrices.

-         Procesos de Lote o Interactivos: Un proceso de lote es más eficiente en cuanto a la lectura de datos, ya que generalmente lo hace de archivos, mientras que un programa interactivo espera mucho tiempo (no es lo mismo el tiempo de lectura de un archivo que la velocidad en que una persona teclea datos) por las respuestas de los usuarios.

-         Procesos en Tiempo Real: Si los procesos deben dar respuesta en tiempo real se requiere que tengan prioridad para los turnos de ejecución.

-         Largo de los Procesos: Existen procesos que típicamente requerirán varias horas para finalizar su labor, mientras que existen otros que solo necesitan algunos segundos.

 

 Planificación del procesador:

La planificación del procesador se refiere a la manera o técnicas que se usan para decidir cuánto tiempo de ejecución y cuando se le asignan a cada proceso del sistema. Obviamente, si el sistema es monousuario y monotarea no hay mucho que decidir, pero en el resto de los sistemas esto es crucial para el buen funcionamiento del sistema.

Existen varios niveles de planificación como son los siguientes:

En los sistemas de planificación generalmente se identifican tres niveles:

 

·        El alto

·        El medio

·        El bajo

El nivel alto decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los recursos del sistema; el nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas metas de rendimiento mientras que el planificador de bajo nivel es el que decide que proceso, de los que ya están listos (y que en algún momento paso por los otros dos planificadores) es al que le toca ahora estar ejecutándose en la unidad central de procesamiento. En este trabajo se revisaran principalmente los planificadores de bajo nivel porque son los que finalmente eligen al proceso en ejecución.

El objetivo de la planificación es buscar que los procesos obtengan sus turnos de ejecución apropiadamente al mismo tiempo que un buen rendimiento y minimización de la sobrecarga del planificador mismo. En general, se buscan cinco objetivos principales:

·       Justicia o Imparcialidad: Todos los procesos son tratados de la misma forma, y en algún momento obtienen su turno de ejecución o intervalos de tiempo de ejecución hasta su terminación exitosa.

·       Maximizar la Producción: El sistema debe de finalizar el mayor numero de procesos en por unidad de tiempo.

·       Maximizar el Tiempo de Respuesta: Cada usuario o proceso debe observar que el sistema les responde consistentemente a sus requerimientos.

·       Evitar el aplazamiento indefinido: Los procesos deben terminar en un plazo finito de tiempo.

·       El sistema debe ser predecible: Ante cargas de trabajo ligeras el sistema debe responder rápido y con cargas pesadas debe ir degradándose paulatinamente. Otro punto de vista de esto es que si se ejecuta el mismo proceso en cargas similares de todo el sistema, la respuesta en todos los casos debe ser similar.

Planificación apropiativa o no apropiativa:

La planificación apropiativa es aquella en la cual, una vez que a un proceso le toca su turno de ejecución ya no puede ser suspendido, ya no se le puede quitar la unidad central de procesamiento. Este esquema puede ser peligroso, ya que si el proceso contiene accidental o deliberadamente ciclos infinitos, el resto de los procesos pueden quedar aplazados indefinidamente. Una planificación no apropiativa es aquella en que existe un reloj que lanza interrupciones periódicas en las cuales el planificador toma el control y se decide si el mismo proceso seguirá ejecutándose o se le da su turno a otro proceso. Este mismo reloj puede servir para lanzar procesos manejados por el reloj del sistema. Por ejemplo en los sistemas UNIX existen los 'cronjobs' y 'atjobs', los cuales se programan en base a la hora, minuto, día del mes, día de la semana y día del año.

En una planificación no apropiativa, un trabajo muy grande aplaza mucho a uno pequeño, y si entra un proceso de alta prioridad esté también debe esperar a que termine el proceso actual en ejecución.

A cada proceso se le asigna un turno de ejecución por medio de algoritmos los cuales son los siguientes:

- Por prioridad: Los procesos de mayor prioridad se ejecutan primero. Si existen varios procesos de mayor prioridad que otros, pero entre ellos con la misma prioridad, pueden ejecutarse estos de acuerdo a su orden de llegada o por 'round robin'. La ventaja de este algoritmo es que es flexible en cuanto a permitir que ciertos procesos se ejecuten primero e, incluso, por más tiempo. Su desventaja es que puede provocar aplazamiento indefinido en los procesos de baja prioridad. Por ejemplo, suponga que existen procesos de prioridad 20 y procesos de prioridad 10. Si durante todo el día terminan procesos de prioridad 20 al mismo ritmo que entran otros con esa prioridad, el efecto es que los de prioridad 10 estarán esperando por siempre. También provoca que el sistema sea impredecible para los procesos de baja prioridad.

- El trabajo más corto primero: Es difícil de llevar a cabo porque se requiere saber o tener una estimación de cuánto tiempo necesita el proceso para terminar. Pero si se sabe, se ejecutan primero aquellos trabajos que necesitan menos tiempo y de esta manera se obtiene el mejor tiempo de respuesta promedio para todos los procesos. Por ejemplo, si llegan 5 procesos A,B,C,D y E cuyos tiempos de CPU son 26, 18, 24, 12 y 4 unidades de tiempo, se observa que el orden de ejecución será E, D, B, C y A (4, 12, 18,  24 y 26 unidades de tiempo respectivamente). En la tabla siguiente se muestra en que unidad de tiempo comienza a ejecutarse cada proceso y como todos comenzaron a esperar desde la unidad cero, se obtiene el tiempo promedio de espera.

- El primero en llegar, primero en ejecutarse: Es muy simple, los procesos reciben su turno conforme llegan. La ventaja de este algoritmo es que es justo y no provoca aplazamiento indefinido. La desventaja es que no aprovecha ninguna característica de los procesos y puede no servir para un proceso de tiempo real.

- Round Robin: También llamada por turno, consiste en darle a cada proceso un intervalo de tiempo de ejecución (llamado time slice), y cada vez que se vence ese intervalo se copia el contexto del proceso a un lugar seguro y se le da su turno a otro proceso. Los procesos están ordenados en una cola circular. Por ejemplo, si existen tres procesos, el A, B y C, dos repasadas del planificador darían sus turnos a los procesos en el orden A, B, C, A, B, C.  La ventaja de este algoritmo es su simplicidad, es justo y no provoca aplazamiento indefinido.

- El tiempo restante más corto: Es parecido al del trabajo más corto primero, pero aquí se está calculando en todo momento cuánto tiempo le resta para terminar a todos los procesos, incluyendo los nuevos, y aquel que le quede menos tiempo para finalizar es escogido para ejecutarse. La ventaja es que es muy útil para sistemas de tiempo compartido porque se acerca mucho al mejor tiempo de respuesta, además de responder dinámicamente a la longevidad de los procesos; su desventaja es que provoca más sobrecarga porque el algoritmo es más complejo.

- La tasa de respuesta más alta: Este algoritmo concede el truno de ejecución al proceso que produzca el valor mayor de la siguiente formula:

Tiempo que ha esperado + tiempo total para terminar

Valor = ___________________________________________

tiempo total para terminar.

Es decir, que dinámicamente el valor se va modificando y mejora un poco las deficiencias del algoritmo del trabajo más corto primero.

- Por politica: Una forma de asignar el turno de ejecución es por politica, en la cual se establece algún reglamento específico que el planificador debe obedecer. Por ejemplo, una política podría ser que todos los procesos reciban el mismo tiempo de uso de CPU en cualquier momento. Esto sig- nifica, por ejemplo, que si existen 2 procesos y han recibido 20 unidades de tiempo cada uno (tiempo acumulado en time slices de 5 unidades) y en este momento entra un tercer proceso, el planificador le dara inmediatamente el turno de ejecución por 20 unidades de tiempo. Una vez que todos los procesos están 'parejos' en uso de CPU, se les aplica 'round robin'.

 

Problemas de Concurrencia:

En los sistemas de tiempo compartido se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema. Imagine que un proceso está escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta, existen una multitud de recursos cuyo acceso debe ser controlado para evitar los problemas de la concurrencia.

El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos: semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de recursos. Para entender este y otros mecanismos es importante entender los problemas generales de concurrencia, los cuales se describen enseguida.

·        Condiciones de Carrera o Competencia: La condición de carrera ocurre cuando dos o más procesos accesan un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada.

·        Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado anterior y consiste en el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su tarea.

·       Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una cadena de espera que los involucra a todos.

·       Condición de No Apropiación: Esta condición no resulta precisamente de la concurrencia, pero juega un papel importante en este ambiente. Esta condición especifica que si un proceso tiene asignado un recurso, dicho recurso no puede arrebatársele por ningún motivo, y estará disponible hasta que el proceso lo 'suelte' por su voluntad.

·       Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un recurso que ya está asignado a otro proceso y la condición de no apropiación se debe cumplir. Entonces el proceso estará gastando el resto de su tiempo revisando si el recurso fue liberado. Es decir, desperdicia su tiempo de ejecución en esperar. La solución más común a este problema consiste en que el sistema operativo se dé cuenta de esta situación y mande a una cola de espera al proceso, otorgándole inmediatamente el turno de ejecución a otro proceso.

·        Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema realiza una serie de operaciones sobre el recurso y después lo deja de usar. A la sección de código que usa ese recurso se le llama 'región crítica'. La condición de exclusión mutua establece que solamente se permite a un proceso estar dentro de la misma región crítica. Esto es, que en cualquier momento solamente un proceso puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el concepto de 'región crítica'. Para logar la exclusión mutua generalmente se usan algunas técnicas para lograr entrar a la región crítica: semáforos, monitores, el algoritmo de Dekker y Peterson, los 'candados'.

Condición de Ocupar y Esperar un Recurso:

Consiste en que un proceso pide un recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene asignado.

Los problemas mencionados anteriormente son todos importantes para el sistema operativo, ya que debe ser capaz de prevenir o corregirlos. Tal vez el problema más serio que se puede presentar en un ambiente de concurrencia es el abrazo mortal. El abrazo mortal es una condición que ningún sistema o conjunto de procesos quisiera exhibir, ya que consiste en que se presentan al mismo tiempo cuatro condiciones necesarias: La condición de no apropiación, la condición de espera circular, la condición de exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el abrazo mortal involucra a todos los procesos del sistema, el sistema ya no podrá hacer algo productivo y si  involucra algunos procesos, éstos quedarán congelados para siempre.

 

Implantación de los procesos

La implementación del modelo de procesos se logra debido a que el sistema operativo almacena en una tabla denominada tabla de control de procesos información relativa a cada proceso que se esta ejecutando en el procesador. Cada línea de esta tabla representa a un proceso. En la tabla se almacena la identificación del proceso hijo y padre, información sobre el usuario y grupo, el estado del procesador, información del control de proceso, la información del planificador, segmentos de memoria asignados y los recursos asignados.

Condiciones de competencia

Las condiciones de competencia se dan cuando dos o más procesos intentan acceder a un mismo recurso. Para solucionar las condiciones de competencia se implementó un modelo para prohibir que dos procesos accedan al mismo recurso. El modelo en cuestión se denomina exclusión mutua. Las soluciones con espera ocupada funcionan de la siguiente manera, cuando un proceso intenta ingresar a su región crítica, verifica si esta permitida la entrada. Si no, el proceso se queda esperando hasta obtener el permiso.

 

Desactivación de interrupciones

El método más simple para evitar las condiciones de competencia es hacer que cada proceso desactive todas sus interrupciones antes de entrar a su sección crítica y las active una vez que salio de la misma. Este modelo como se puede observar, éste modelo tiene una gran problema y es que si se produce una falla mientras que el proceso esta en la región crítica no se puede salir de la misma y el sistema operativo no recuperaría el control.

 

Variables cerradura

En éste caso se genera una variable la cual puede tener dos valores o bien 0 (no hay ningún proceso en su sección crítica) o bien 1 (indicando que la sección crítica está ocupada) entonces cada proceso antes de ingresar a la sección crítica verifica el estado de la variable de cerradura y en caso de que la misma este en 0, le cambia el valor e ingresa a la misma y en caso de que la misma sea 1 el proceso se queda verificando el estado de la misma hasta que el mismo sea 0.

El problema aquí se presenta si dos procesos verifican al mismo tiempo que la variable cerradura esta en 0 e ingresan a la región crítica.

 

Alternancia estricta

El algoritmo de alternancia estricta no bloquea el ingreso a la región crítica cuando otro proceso se esta ejecutando. El problema de ésta solución es que cuando un proceso no esta en la sección crítica igualmente tiene bloqueado el acceso a la misma y por lo tanto no permite que otro proceso que requiera ingresar a la misma logre hacerlo.

 

Instrucción TSL

Esta solución requiere ayuda del hardware y es debido a que en general las computadoras diseñadas para tener más de un procesador tienen una instrucción TEST AND SET LOCK

 

Dormir y despertar

El modelo de espera acotada tienen el inconveniente que se desperdicia tiempo de procesador.

 

El problema del productor y el consumidor

El problema del productor y el consumidor describe el echo de que cuando hay dos o más procesos interactuando a través de un buffer común habiendo procesos que ponen información o datos y otros que los sacan se pueden llegar a dar condiciones en las cuales los procesos que ingresan los datos no puedan hacerlo debido a que el buffer ya se encuentra lleno y para el caso de los que sacan los datos del buffer intenten sacar datos cuando ya no hay nada que sacar. Para evitar estas condiciones se desarrollaron métodos de comunicación/sincronización entre procesos en los cuales se impide que esto suceda haciendo que el proceso productor "duerma" si el buffer está lleno y una vez que exista espacio el proceso "consumidor" despierte al productor para que siga generando o viceversa.