Asincronas y sincronas
Éste es un tema muy relevante (sobre todo si uno quiere diseñar programas que sean realmente atractivos y que se usen de verdad), porque hay notables diferencias. En este artículo vamos a exponer, muy brevemente, la “popularidad” actual de las herramientas más conocidas:
Síncronas (sesiones presenciales, chats y videoconferencias, etc.).
-Asíncronas (foros, eMail y listas de distribución, aportaciones asíncronas a debates virtuales, etc.).
Dentro de los principales colectivos relacionados con el método:
- Responsables de organizaciones que implantaron eLearning y Blended Learning
- Tutores virtuales
- Alumnos
Asíncronas: Tipo de comunicación donde cada byte se transmite del emisor al receptor de modo independiente. Es la que utilizan los módems.
Asíncronas:
Por exclusión, lo contrario.- Es evidente que permiten mayor flexibilidad aunque exijan más trabajo por parte del tutor, coordinador o alguna figura similar.
Síncronas:
Herramientas para desarrollar una actividad en la que emisor(es) y receptor(es) necesariamente han de coincidir en el tiempo en cuanto a su conexión a la red.
Concurrencia Exclusion Mutua Y Sincronizacion
Los temas fundamentales del diseño de sistemas operativos están relacionados con la gestión de procesos e hilos:
• Multiprogramación: consiste en la gestión de varios procesos dentro de un sistema mono-procesador.
• Multiprocesamiento: consiste en la gestión de varios procesos, dentro de un sistema multiprocesador.
• Procesamiento distribuido: consiste en la gestión de varios procesos, ejecutándose en sistemas de computadores múltiples y distribuidos. La reciente proliferación de las agrupaciones es el principal ejemplo de este tipo de sistemas.
La concurrencia es fundamental en todas estas áreas y para el diseño sistemas operativos. La concurrencia comprende un gran número de cuestiones de diseño, incluida la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos. Se verá que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso distribuido, sino incluso en sistemas multiprogramados con un solo procesador.
La concurrencia puede presentarse en tres contextos diferentes:
• Múltiples aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.
• Aplicaciones estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.
• Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.
PRINCIPIOS GENERALES DE LA CONCURRENCIA
En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo aparentando una ejecución simultánea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecución intercalada produce beneficios en la eficiencia del procesamiento y en la estructuración de los programas.
La intercalación y la superposición pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecución de los procesos que no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema operativo trata las interrupciones surgen las siguientes dificultades:
Compartir recursos globales es riesgoso Para el sistema operativo es difícil gestionar la asignación óptima de recursos. Las dificultades anteriores también se presentan en los sistemas multiprocesador.
El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.
Los problemas de concurrencia se producen incluso cuando hay un único procesado
LABORES DEL SISTEMA OPERATIVO
Elementos de gestión y diseño que surgen por causa de la concurrencia:
1) El sistema operativo debe seguir a los distintos procesos activos
2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se incluyen:
_Tiempo de procesador
_Memoria
_Archivos
_Dispositivos de E/S
3) El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.
4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecución de otros procesos concurrentes.
Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactúan.
INTERACCIÓN ENTRE PROCESOS
Se puede clasificar los en que interactúan los procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimiento:
1) Los procesos no tienen conocimiento de los demás: son procesos independientes que no operan juntos. Ej: la multiprogramación de procesos independientes. Aunque los procesos no trabajen juntos, el sistema operativo se encarga de la “competencia” por los recursos.
2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus identificadores de proceso, pero muestran cooperación el objeto común.
3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de proceso y pueden trabajar conjuntamente.
Competencia entre procesos por los recursos
Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o más procesos necesitan acceder a un recurso durante su ejecución .Cada proceso debe dejar tal y como esté el estado del recurso que utilice.
La ejecución de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dos procesos desean acceder a un recurso, el sistema operativo le asignará el recurso a uno y el otro tendrá que esperar.
Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de exclusión mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos recursos se les llama “recursos críticos” y la parte del programa que los utiliza es la “sección crítica” del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado.
Hacer que se cumpla la exclusión mutua provoca un interbloqueo.
Otro problema es la inanición si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo concede el acceso a P1 YP2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.
El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.
Cooperación entre procesos por compartimiento Comprende los procesos que interactúan con otros sin tener conocimiento explícito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.
Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Los mecanismos de control deben garantizar la integridad de los datos compartidos.
Cooperación entre procesos por comunicación Los distintos procesos participan en una labor común que une a todos los procesos.
La comunicación sincroniza o coordina las distintas actividades, está formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programación o por el núcleo del sistema operativo
REQUISITOS PARA LA EXCLUSIÓN MUTUA
Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición. Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora. No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores. Un proceso permanece en su sección crítica por un tiempo finito. Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.
EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE
Pueden implementarse soluciones de software para los procesos concurrentes que se ejecuten en máquinas monoprocesador o multiprocesador con memoria principal compartida.
ALGORITMO DE DEKKER
La solución se desarrolla por etapas. Este método ilustra la mayoría de los errores habituales que se producen en la construcción de programas concurrentes.
Primer intento
Cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es que sólo se puede acceder a una posición de memoria en cada instante, teniendo en cuenta esto se reserva una posición de memoria global llamada turno. Un proceso que desea ejecutar su sección crítica primero evalúa el contenido de turno. Si el valor de turno es igual al número del proceso, el proceso puede continuar con su sección crítica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su sección crítica. Este procedimiento se llama espera activa.
Después de que un proceso accede a su sección crítica y termina con ella, debe actualizar el valor de turno para el otro proceso.
Segundo intento:
Cada proceso debe tener su propia llave de la sección crítica para que, si uno de ellos falla, pueda seguir accediendo a su sección crítica; para esto se define un vector booleano señal. Cada proceso puede evaluar el valor de señal del otro, pero no modificarlo. Cuando un proceso desea entrar en su sección crítica, comprueba la variable señal del otro hasta que tiene el valor falso (indica que el otro proceso no está en su sección crítica). Asigna a su propia señal el valor cierto y entra en su sección crítica. Cuando deja su sección crítica asigna falso a su señal.
Si uno de los procesos falla fuera de la sección crítica, incluso el código para dar valor a las variables señal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la variable señal del otro proceso está siempre en falso. Pero si un proceso falla en su sección crítica o después de haber asignado cierto a su señal, el otro proceso estará bloqueado permanentemente.
Tercer intento
El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica.
Si un proceso falla dentro de su sección crítica, incluso el código que da valor a la variable señal que controla el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.
Si ambos procesos ponen sus variables señal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensará que el otro ha entrado en su sección crítica, generando así un interbloqueo.
Cuarto intento
En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su señal para indicar que desean entrar en la sección crítica pero deben estar listos para desactivar la variable señal y ceder la preferencia al otro proceso.
Existe una situación llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones críticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecución con éxito.
Una solución correcta
Hay que observar el estado de ambos procesos, que está dado por la variable señal, pero es necesario imponer orden en la actividad de los procesos para eitar el problema de “cortesía mutua”. La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su sección crítica.
ALGORITMO DE PETERSON
El algoritmo de Deker resuelve el problema de la exclusión mutua pero mediante un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad.
Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 esta aun en su sección crítica, entonces señal[1] = cierto y P0 está bloqueado en su bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[1] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:
P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso. P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podría entrar en su sección crítica. P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su sección crítica. Así pues, se tiene una solución posible al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos.
Disciplina de cola
La disciplina de cola mas simple es la de primero en llegar/ primero en salir, pero ésta puede no ser suficiente si algunos mensajes son mas urgentes que otros. Una alternativa es permitir la especificación de prioridades de los mensajes, en función del tipo de mensaje o por designación del emisor. Otra alternativa es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.
Exclusión mutua
Supóngase que se usan primitivas receive bloqueantes y send no bloqueantes. Un conjunto de procesos concurrentes comparten un buzón, exmut, que puede ser usado por todos los procesos para enviar y recibir. El buzón contiene inicialmente un único mensaje, de contenido nulo. Un proceso que desea entrar en su sección crítica intenta primero recibir el mensaje. Si el buzón está vacío, el proceso se bloquea. Una vez que un proceso ha conseguido el mensaje, ejecuta su sección crítica y, después, devuelve el mensaje al buzón. De este modo, el mensaje funciona como testigo que se pasa de un proceso a otro.
Esta técnica supone que si hay más de un proceso ejecutando la acción receive concurrentemente, entonces:
Si hay un mensaje, se entrega sólo a uno de los procesos y los otros se bloquean. Si el buzón está vacío, todos los procesos se bloquean; cuando haya un mensaje disponible, sólo se activará y tomará el mensaje uno de los procesos bloqueados.
EXCLUSIÓN MUTUA: SOLUCIONES POR HARDWARE
INHABILITACIÓN DE INTERRUPCIONES
En una máquina monoprocesador, la ejecución de procesos concurrentes no puede superponerse; los procesos solo pueden intercalarse. Es más, un proceso continuará ejecutándose hasta que solicite un servicio el sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusión mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el núcleo del sistema para habilitar o inhabilitar las interrupciones. Un proceso puede hacer cumplir la exclusión mutua del siguiente modo:
While (cierto)
{
/*inhabilitar interrupciones */;
/* sección critica */;
/* habilitar interrupciones */;
/* resto */;
}
Puesto que la sección crítica no puede ser interrumpida, la exclusión mutua está garantizada. Sin embargo, el precio de esta solución es alto. La eficiencia de la ejecución puede verse notablemente degradada debido a que se limita la capacidad del procesador para intercalar programas. Un segundo problema es que está técnica no funciona en arquitecturas de multiprocesador. Cuando el sistema tenga más de un procesador, es posible (y habitual) que haya más de un proceso ejecutándose al mismo tiempo. En este caso, inhabilitar las interrupciones no garantiza la exclusión mutua.
INSTRUCCIONES ESPECIALES DE MAQUINA
En configuraciones multiprocesador, varios procesadores comparten el acceso a una memoria principal común. En este caso, no hay relación maestro/esclavo, sino que los procesadores funcionan independientemente en una relación de igualdad. No hay un mecanismo de interrupciones entre los procesadores en el que se pueda basar la exclusión mutua.
A nivel de hardware, como se ha mencionado, los accesos a posiciones de memoria excluyen cualquier otro acceso a la misma posición. Con esta base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atómicamente, tales cono leer y escribir o leer y examinar, sobre una misma posición de memoria en un único ciclo de lectura de instrucción.
Puesto que estas acciones se realizan en un único ciclo de instrucción, no están sujetas a injerencias por parte de otras instrucciones.
-La instrucción COMPARAR Y FIJAR (TS, Test and Set)puede definirse de la siguiente forma:
boolean TS(int i)
{
if (I=0)
{
I=1;
return cierto;
}
else
{
retur falso;
}
}
La instrucción examina el valor de su argumento i. Si el valor es 0 , lo cambia por 1 y devuelve cierto. En otro caso, el valor no se modifica y se devuelve falso. La función Comparar y Fijar se ejecuta atómicamente en su totalidad, es decir, no esta sujeta a interrupciones.
La instrucción INTERCAMBIAR se puede definir como sigue:
void intercambiar (int registro, int memoria)
{
int temp;
temp = memoria;
memoria = registro;
registro = temp;
}
Esta instrucción intercambia el contenido de un registro con el de una posición de memoria. Durante la ejecución de la instrucción, se bloquea el acceso a la posición de memoria de cualquier otra instrucción que haga referencia a la misma posición.
Propiedades de las soluciones con instrucciones de maquina
El uso de instrucciones especiales de la maquina para hacer cumplir la exclusión mutua tiene varias ventajas:
Es aplicable a cualquier número de procesos en sistemas con memoria compartida, tanto de monoprocesador como de multiprocesador. Es simple y fácil de verificar. Puede usarse para disponer de varias secciones críticas; cada sección crítica puede definirse con su propia variable. Algunas desventajas importantes son las siguientes:
SE EMPLEA ESPERA ACTIVA. Así pues, mientras un proceso está esperando para acceder a la sección crítica, continúa consumiendo tiempo del procesador. PUEDE PRODUCIRSE INANICIÓN. Cuando un proceso abandona la sección crítica y hay más de un proceso esperando, la selección es arbitraria. Así pues se podría denegar el acceso a algún proceso indefinidamente. PUEDE PRODUCIRSE INTERBLOQUEO. Supóngase la siguiente escena en un sistema monoprocesador. El proceso “P1″ ejecuta una instrucción especial (sea TS o Intercambiar) y entra su sección crítica. Se interrumpe a “P1″ para dar el procesador a “P2″, que tiene mayor prioridad. Si “P2″ intenta ahora usar el mismo recurso que “P1″, se le negará el acceso por el mecanismo de exclusión mutua. De este modo, “P2″ entrará en un bucle de espera activa. Sin embargo, “P1″ nunca será expedido porque su prioridad es menor que la del proceso listo “p2″.
SEMÁFOROS
Para solucionar problemas de procesos concurentes, se diseño un S.O. como un conjunto de procesos secuenciales, eficiente y fiables para dar soporte a la cooperación. Los procesos de usuario podrían utilizar estos mecanismos si el procesador y el S.O. los hacían disponible.
El principio fundamental es el siguiente, 20+ procesos pueden cooperar por medio de simples señales, de manera que se pueda obligar a un proceso a detener en una posición determinada hasta que reciba una señal específica. Para la señalización se usan variables especiales llamadas semáforos “S”, los procesos ejecutan las primitivas wait(s) si la señal aun no se transmitió, el proceso se suspende hasta que tiene lugar la transmisión.
A los semáforos se los contemplan como variables que tienen un N° entero sobre el que se definen las siguientes operaciones:
un semáforo puede iniciarse con un valor negativo la operación wait disminuye el valor del semáforo. Si el valor no es positivo el proceso que ejecuta wait se bloquea. las operaciones signal incrementa el N° del semáforo. Si el valor es positivo se desbloquea el proceso bloqueado por una operación wait. No hay forma de examinar o manipular los semáforos aparte de estas tres operaciones.
Las primitivas wait y signal se suponen atómicas, es decir no pueden ser interrumpidas y cada rutina puede considerarse como un peso indivisible.
Un semáforo solo puede tomar los valores 0 y 1. Son más sencillos de implantar y pueden demostrarse que tienen la misma potencia de expresión que los semáforos generales.
En ambos semáforos se emplean una cola para mantener los procesos en espera, la cuestión reside en el orden en que se retiran los procesos de la cola. La política utilizada el la de FIFO; el proceso que estuvo bloqueado durante mas tiempo se libera de la cola, se denomina semáforo robusto (incluye esta estrategia). Un semáforo débil no especifica el orden en que se retiran los procesos de la cola.
Los semáforos robustos garantizan la inexistencia de inanición en el algoritmo de exclusión mutua, pero no así en los semáforos débiles, se supone que los semáforos son siempre robustos ya que son los más adecuados y porque son los tipos de semáforos que más incluyen los S.O.
Implementación de los semáforos. Como se menciono anteriormente es impredecible que las operaciones wait y signal sean implementadas como primitivas atómicas.
La esencia del problema del productor/consumidor, es la exclusion mutua: solo 1 proceso puede manipular un semáforo a la vez, en una operación wait o signal. Se pueden utilizar cualquier esquema de software con los algoritmos de Dekker o Peterson los que suponen una sobrecarga de procesos sustancial. Otra alternativa es usar uno de los esquemas de soporte del hardware p/la exclusion mutua..
En sistemas monoprocesador procesador, se pueden inhibir las interrupciones durante una operación wait o signal.
MONITORES
Los monitores son estructuras de un lenguaje de programación que ofrecen una funcionalidad equivalente a las de los semáforos pero son más fáciles de controlar. El concepto de monitor fue definido por primera vez en [HOAR 74] . La estructura de monitor se ha implementado en varios lenguajes de programación como: Pascal concurrente, Modulo-2, Java, etc.
En concreto, para una lista enlazada se puede necesitar un cierre que bloquee todas las listas enlazadas o bien un cierre por cada elemento de una lista.
Monitores con Señales: ( definición de Hoare )
Un monitor es un modulo de software que consta de uno o más procedimientos, una secuencia de inicio y uno datos locales. Sus características son las siguientes:
Solo los procedimientos del monitor acceden a variables de datos locales. Un proceso entra en el monitor invocando a uno de sus procedimientos. En el monitor solo un proceso puede ser ejecutado en un momento dado; cualquier otro proceso quedara suspendido esperando la disponibilidad del monitor. Al ser un proceso por vez, el monitor puede ofrecer un servicio de exclusión mutua fácilmente. Así una estructura de datos puede protegerse situándola dentro de un monitor.
Los monitores deben ofrecer herramientas de sincronización. Por ejemplo: si un proceso llama a un monitor y una vez dentro de él el proceso queda suspendido esperando alguna condición, hará falta un servicio que libere al monitor y lo deje disponible para el siguiente proceso. Mas tarde cuando la condición se cumpla el proceso suspendido podrá regresar al monitor y ejecutarse desde el momento de la suspensión.
El monitor proporciona variables de condición que son accesibles solo desde dentro del monitor.
Hay dos funciones para operar variables de condición:
cwait ©: suspende la ejecución del proceso que llama bajo la condición “c”. El monitor está ahora disponible para otro proceso. csignal ©: retorna la ejecución de un proceso suspendido después de un cwait, bajo la misma condición. Si hay varios procesos elige uno de ellos. Si un proceso de monitor ejecuta un csignal y no hay tareas esperando entonces el csignal de pierde.
Aunque un proceso puede entrar al monitor llamando a cualquiera de sus procedimientos, se puede decir que el monitor tiene un solo punto de acceso, custodiado para que solo un proceso este en el monitor en un instante dado. Si existen otros procesos tratando de entrar al monitor, estos se colocan en una cola de procesos suspendidos esperando la disponibilidad del monitor.
Un proceso dentro de un monitor puede suspenderse a sí mismo, temporalmente, bajo la condición X ejecutando cwait(x), entonces se coloca en una cola de procesos que esperan que cambie la condición X entonces ejecuta un csignal(x) que avisa a la cola de condición correspondiente de que la condición a cambiado.
En el código se puede apreciar la solución al problema de productor / consumidor usando monitores:
El modulo monitor, buffers_acotado, controla el buffer para almacenar y retirar caracteres. El monitor incluye dos variables de condición:
No-lleno es verdadero su hay lugar para agregar al menos un carácter.
No-vació es verdadero si hay al menos un carácter en el buffer.
Un productor solo puede agregar caracteres al buffer mediante el procedimiento añadir del monitor; el productor no tiene acceso directo al buffer. El procedimiento comprueba si hay espacio en el buffer, mediante la condición no-lleno, si no lo hay el proceso queda suspendido y cualquier otro proceso (consumidor o productor) puede entrar al monitor. Luego, cuando el buffer ya no esta lleno, el proceso se retira de la cola y es reactivado. Luego de añadir un carácter el proceso activa la condición no-vació.
La estructura misma del monitor garantiza la exclusión mutua (solo un proceso por vez puede acceder al buffer). Sin embargo, el programador debe situar correctamente las primitivas cwait( ) y csignal( ) en el monitor para evitar que los procesos depositen elementos en un buffer lleno o los extraigan de uno vació.
Un proceso sale del monitor inmediatamente después de ejecutar csignal( ).
Si csignal( ) se ejecuta antes del final entonces ese proceso libera el monitor y esta colocado en una lista de procesos suspendidos. Un nuevo proceso puede entrar el monitor.
Si no hay procesos esperando en la condición X, la ejecución de csignal (x) no tiene efecto.
Es posible cometer errores en la sincronización de los monitores, por ejemplo, si se omite cualquiera de las funciones csignal() en el monitor buffer _ acotado los procesos que entran en la cola de condición permanecen colgados permanentemente. Sin embargo la ventaja de los monitores es que todas las funciones de sincronización están incluidas dentro del monitor, lo que permite una fácil detección y corrección de fallas de sincronización.
Monitores con Notificación y Difusión (definición de Lampson y Redell)
Son varios los inconvenientes que presenta la solución de Hoare:
-Si el proceso que ejecuta el csignal( ) no ha terminado en el monitor, se necesitaran dos cambios de procesos adicionales: uno para suspender el proceso y otro para reanudarlo.
-La planificación de procesos asociados con las señales debe ser muy fiable. Si un proceso ejecuta un csignal ( ), el proceso de la cola de condición correspondiente debe activarse de inmediato, antes de que ingrese otro proceso del exterior o cambie la condición bajo la que se activó el proceso. Otro caso seria que un proceso productor escribe un carácter en el buffer y falla antes de dar la señal, entonces la cola de condición no-vacía se colgaría para siempre.
Lampson y Redell desarrollaron una definición de monitores para el lenguaje MESA [Lamp 80]. La estructura de mesa reemplaza la primitiva csignal( ) por cnotify( ). Cuando un proceso ejecuta cnotify(x) envía una notificación a la cola de condición X, lo cual no significa que el proceso que esta ocupando el monitor vaya a detenerse, simplemente el cnotify(x) avisa al proceso de la cola de condición correspondiente de que será reanudado en un futuro cercano. Puesto que esta no garantiza que un proceso exterior entre al monitor, el proceso debe comprobar la condición nuevamente.
En el código, la sentencia IF se reemplaza por un bucle While, lo cual genera una evaluación extra de la variable, pero sin embargo no hay cambios de procesos extra.
Una modificación útil seria asociar un temporizador de guardia a cnotify( ) que permitiría que un proceso que ha esperado durante el intervalo máximo sea situado en estado de listo, independientemente de sí se ha notificado la condición.
Con la norma de notificar a los procesos en lugar de reactivarlos, es posible añadir una primitiva de difusión cbroadcast. La difusión provoca que todos los procesos que están esperando por una condición se coloquen en el estado de listo. Esto es útil cuando un proceso no sabe cuantos procesos deben reactivarse.
El método Lampson/Redell es menos propenso a errores debido a que cada procedimiento comprueba la condición luego de ser despertado, por medio de la instrucción while, un proceso puede realizar una señal o una difusión incorrectamente sin provocar un error en el programa que la recibe.
Además este modelo presta un método mas modular de construcción de programas.
Hay dos niveles de condición que deben satisfacerse para los procesos secuenciales cooperantes.
Estructura de datos consistentes: significa que el monitor hace cumplir la exclusión mutua y concluye la operación de entrada o salida antes de permitir cualquier otra operación sobre el buffer. La misma condición del nivel 1 y, además disponer de suficiente memoria para que este proceso pueda completar su solicitud de asignación. PASO DE MENSAJES
Son 2 los requisitos básicos que deben satisfacerse cuando los procesos interactúan entre si.
Ellos son:
La sincronización La comunicación Los procesos tienen que sincronizarse para cumplir la exclusión mutua, los procesos cooperantes pueden necesitar intercambiar información.
El paso de mensajes es un método que permite que se realice ambas funciones. Este método tiene la ventaja de que es de fácil implementación en sistemas distribuidos y también es sistemas de multiprocesador y monoprocesador de memoria compartida.
La funcionalidad real del paso de mensajes, generalmente, se da por medio de un par de primitivas:
send(destino, mensaje)
receive(origen, mensaje)
Este es el conjunto mínimo de operaciones necesarias para que los procesos puedan dedicarse al paso de mensajes.
SINCRONIZACION
La comunicación de un mensaje entre 2 procesos implica cierto nivel de sincronización entre ambos. El receptor no puede recibir un mensaje hasta que sea enviado por otro proceso. Además hace falta especificar que le sucede a un proceso después de ejecutar una primitiva SEND o RECEIVE.
Considérese en primer lugar la primitiva send. Cuando se ejecuta una primitiva send en un proceso, hay 2 posibilidades: o bien el proceso emisor se bloquea hasta que recibe el mensaje o no se bloquea. Igualmente cuando un proceso ejecuta una primitiva RECEIVE, existen 2 opciones:
1) Si previamente se ha enviado algún mensaje, este es recibido y continua la ejecución.
2) Si no hay ningún mensaje esperando entonces:
a) el proceso se bloquea hasta que llega un mensaje o,
b) el proceso continúa ejecutando, abandonando el intento de recepción.
El emisor y el receptor pueden ser bloqueantes o no bloqueantes.
Existen 3 tipos de combinaciones pero un sistema solo implementa uno o dos.
I) Envío bloqueante, recepción bloqueante: tanto el emisor como el receptor se bloquean hasta que llega el mensaje; esta técnica se conoce como rendezvous.
II) Envío no bloqueante, recepción bloqueante: aunque el emisor puede continuar, el receptor se bloquea hasta que llega el mensaje solicitado. Es la combinación más útil.
III) Envío no bloqueante, recepción no bloqueante: nadie debe esperar.
El send no bloqueante es la forma más natural para muchas tareas de programación concurrente. Un posible riesgo del send no bloquente es que por error puede llevar a una situación en la que el proceso genere mensajes repetidamente.
Para el receive, la versión bloqueante es la mas natural para muchas tareas de programación concurrente. En general, un proceso que solicita un mensaje necesitara la información esperada antes de continuar.
DIRECCIONAMIENTO
Es necesario disponer de alguna forma de especificar en la primitiva send que proceso va a recibir el mensaje. La mayoría de las implementaciones permiten a los procesos receptores indicar el origen del mensaje que se va a recibir.
Los distintos esquemas para hacer referencia a los procesos en las primitivas send y receive se encuadran dentro de 2 categorías:
1) Direccionamiento directo: la primitiva send incluye una identificación específica del proceso de destino.
La primitiva receive se puede gestionar de 2 formas:
Una posibilidad requiere que el proceso designe explícitamente un proceso emisor. El proceso debe conocer de antemano de que proceso espera un mensaje. En otros casos es imposible especificar el proceso de origen por anticipado. 2) Direccionamiento indirecto: los mensajes no se envían directamente del emisor al receptor, sino a una estructura de datos compartidos formada por colas, que pueden guardar los mensajes temporalmente, que se denominan BUZONES (mailboxes). Para que 2 procesos se comuniquen, uno envía mensajes al buzón apropiado y el otro los retira. Una ventaja de este tipo de direccionamiento es que se desacopla a emisor y receptor, asegurando mayor flexibilidad en el uso de mensajes.
Relación entre emisores y receptores
UNO A UNO: permite que se establezca un enlace privado entre 2 procesos. Aísla su interacción de injerencias erróneas de otros procesos. MUCHOS A UNO: resulta útil para interacciones cliente-servidor. En este caso el buzón se llama puerto. UNO A MUCHOS: permite un emisor y varios receptores. La asociación de procesos a buzones puede ser ESTATICA o DINAMICA. Los puertos suelen estar asociados estáticamente con algún proceso en particular. El puerto se crea y se asigna al proceso permanentemente. Una relación de UNO A UNO se define de forma estática y permanentemente. Cuando hay varios emisores, la asociación a un BUZON puede realizarse dinámicamente. Se pueden utilizar primitivas como CONECTAR o DESCONECTAR.
Propiedad del buzón. en el caso de 1 puerto, normalmente pertenece y se crea por el RECPTOR. Entonces cuando se destruye el proceso, también se destruye el puerto.
Para los buzones en general el S.O. ofrece un servicio de creación de buzones. Son considerados como propiedad del proceso creador en cuyo caso se destruyen junto con el proceso, o como propiedad del S.O., en este caso se necesita una orden explicita para destruir el buzón.
FORMATO DE MENSAJES
Para algunos S.O. los diseñadores han elegido mensajes cortos y tamaños fijos para minimizar procesamiento y coste de almacenamiento. Si se van a pasar una gran cantidad de datos, estos pueden ponerse en un archivo y el mensaje simplemente hará referencia a este archivo. Una solución más flexible es utilizar mensajes de longitud variable.
DISCIPLINA DE COLA
La disciplina de cola más simple es FIFO, pero esta puede no ser suficiente para mensajes más urgentes que otros. Una opción es habilitar la especificación de prioridades de los mensajes, en función del tipo de mensajes o por designación del emisor. Otra es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.
EXCLUSION MUTUA
Con el siguiente algoritmo de muestra una forma de usar el PASO DE MENSAJES para cumplir la exclusión mutua.
Se usan RECEIVE bloqueantes y SEND no bloqueantes. Unos procesos concurrentes comparte un BUZON, EXMUT, que puede ser usado por todos los procesos. EXMUT (buzón) tiene inicialmente un único mensaje nulo. Un proceso que requiere entrar en su sección crítica intenta:
1) recibir el mensaje. Si el EXMUT(buzón) esta vacío, se bloquea el proceso.
2) Una vez que consiguió el mensaje, ejecuta su sección crítica y devuelve el mensaje al buzón.
El mensaje funciona como un testigo(TOKEN) que se pasa de proceso a otro.
Esta técnica supone que si hay más de un proceso ejecutando la acción RECEIVE concurrentemente, entonces:
Si hay un mensaje, se entrega solo a uno de los procesos y los demás se bloquean. Si el buzón esta vacío, todos se bloquean cuando hay un mensaje, solo se activara y tomara el mensaje uno de los procesos bloqueados. PROBLEMA DE LOS LECTORES/ESCRITORES
Descripción del problema:
Existe un área de datos compartida entre una serie de procesos, algunos sólo leen los datos (lectores) y otros sólo escriben datos (escritores). El problema es satisfacer las siguientes condiciones:
1. Cualquier número de lectores puede leer el archivo simultáneamente.
2. En el archivo sólo puede escribir un escritor en cada instante.
3. Si un escritor está accediendo al archivo, ningún lector puede leerlo.
El problema general de exclusión mutua, consiste en permitir a cualquiera de los procesos (lectores o escritores) leer o escribir en el área de datos. Esto hace necesario declarar cualquier acceso como una sección crítica donde los procesos tendrían que acceder uno a uno produciéndose intolerables retrasos, además se debe impedir que los escritores interfieran unos con otros y también que se realicen consultas mientras se llevan a cabo modificaciones
Aplicar la solución general al problema de los lectores/escritores sería inaceptablemente lenta. En este caso más restrictivo es posible crear soluciones más eficientes.
A continuación se examinan dos soluciones al problema:
PRIORIDAD A LOS LECTORES Es una solución que utiliza semáforos para respetar la exclusión mutua. Se permite el acceso a varios lectores, pero mientras que un escritor está accediendo a los datos compartidos, no se permite acceder a ningún escritor o lector.
El primer lector que intenta acceder debe esperar en el semáforo, Cuando haya al menos un lector, los lectores siguientes no necesitan esperar para entrar, se les da prioridad. El problema es que un escritor estará esperando mientras que haya al menos un lector leyendo, que luego podría dar paso a otro lector, en este caso el lector estará sujeto a inanición.
Se utiliza una variable global contlect para mantener el número de lectores y el semáforo x para que la actualización de contlect sea consistente. El semáforo esem controla el acceso al recurso compartido.
/* program lectores_escntores*/
int contlect;
semáforo x = 1, esem=1;
void lector()
{
while (cierto)
{
wait(x);
contlect++;
If (contlect==1)
wait(esem);
signal(x);
LEER_UNIDAD();
wait(x);
contlect—;
If (contlect==0)
signal(esem);
signal(x);
}
}
void escritor()
{
while (cierto)
{
wait(esem);
ESCRIBIR_UNIDAD();
signal(esem);
}
}
vold main() {
contlect = 0;
parbegln(tector, escritor);
}
Una solución al problema de los lectores/escritores por medio de semáforos; los lectores tienen prioridad.
2. PRIORIDAD A LOS ESCRITORES
Esta solución garantiza que no se permitirá acceder a los datos a ningún nuevo lector una vez que, al menos, un escritor haya declarado su deseo de escribir. Se utilizan los mismos semáforos que en la solución anterior y se añaden otros más:
• Un semáforo Isem que inhibe todas las lecturas cuando al menos un escritor desea acceder
• Una variable contesc que controla la activación de Isem
• Un semáforo y que controla la actualización de contesc
• Un semáforo y que controla la actualización de contesc
• Un semáforo z donde se encolan los lectores cuando ya hay uno en lsem
/* program lectores_escritores */
Int contlec, contesc;
semáforo x=1, y =1, z=1, esem=1, lsem=1;
void lector()
{
while (cierto)
{
wait(z);
wait(lsem);
wait(x);
contlect++;
if (contlect = = 1)
{
wait(esem);
}
signal(x);
signal(lsem);
signal(z);
LEER_UNIDAD();
wait(x);
contlect—;
if (contlect == 0)
signal(esem);
signal(x);
}
}
void escritor()
{
while (cierto)
{
wait(y);
contesc++;
if (contesc = = 1)
wait(lsem) ;
signal(y);
wait(esem);
ESCRIBIR_UNIDAD();
signal(esem);
wait(y);
contesc—;
If (contesc== 0)
signal(lsem);
signal(y);
}
}
void mailn()
{
contlect = contesc = 0;
parbegin (lector, escritor);
}
