Concurrencia:
exclusión mutua y sincronización
INTRODUCCIÓN
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:
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.
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.
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
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 evitar 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:
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:
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:
booleano TS(int i)
{
if (I==0)
{
I=1;
return cierto;
}
else
{
return 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:
Algunas desventajas
importantes son las siguientes:
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:
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:
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:
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.
PASO DE MENSAJES
Son 2 los requisitos
básicos que deben satisfacerse cuando los procesos interactúan entre si.
Ellos son:
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:
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
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:
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:
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;
{
{
wait(x);
wait(esem);
signal(x);
LEER_UNIDAD();
wait(x);
If
(contlect==0)
signal(esem);
}
}
void escritor()
{
while (cierto)
{
signal(esem);
}
}
contlect = 0;
}
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);
}
Una solución al problema de los lectores/escritores
por medio de semáforos; los escritores tienen prioridad.
Número de visitantes actuales disponible desde el 14/07/2002:
Autor: lrmdavid@exa.unne.edu.ar
Ó FACENA - http://exa.unne.edu.ar
Servicios WEB: webmaster@exa.unne.edu.ar