Operador de comparación
Para simplificar la escritura del algoritmo, se utiliza esta notación en las comparaciones entre las prioridades de los hilos:
(a, b) < (c, d)
que es equivalente a:
(a < c) o ((a == c) y (b < d))
Pseudocódigo
N es el número de hilos que hay en el sistema.
Para conocer los números de turno se utiliza un vector de enteros. número[i] es el turno correspondiente al hilo i. Si número[i] = 0 significa que el hilo i no está interesado en entrar en sección crítica.
/* Variables globales */
Número: vector [1..N] de enteros = {todos a 0};
Eligiendo: vector [1..N] de booleanos = {todos a falso};
/* Código del hilo i */
Hilo(i) {
loop {
/* Calcula el número de turno */
Eligiendo[i] = cierto;
Número[i] = 1 + max(Número[1], …, Número[N]);
Eligiendo[i] = falso;
/* Compara con todos los hilos */
for j in 1..N {
/* Si el hilo j está calculando su número, espera a que termine */
while ( Eligiendo[j] ) { /* nada */ }
/* Si el hilo j tiene más prioridad, espera a que ponga su número a cero */
/* j tiene más prioridad si su número de turno es más bajo que el de i, */
/* o bien si es el mismo número y además j es menor que i */
while ( (Número[j] != 0) && ((Número[j], j) < (Número[i], i)) ) { /* nada */ }
}
/* Sección crítica */
…
/* Fin de sección crítica */
Número[i] = 0;
/* Código restante */
}
}
Modelo de Sincronización por Semáforos
Dijkstra dio en 1968 una solución al problema de la exclusión mutua con la introducción del concepto de semáforo binario. Está técnica permite resolver la mayoría de los problemas de sincronización entre procesos y forma parte del diseño de muchos sistemas operativos y de lenguajes de programación concurrentes.
Un semáforo binario es un indicador (S) de condición que registra si un recurso está disponible o no. Un semáforo binario sólo puede tomar dos valores: 0 y 1. Si, para un semáforo binario, S = 1 entonces el recurso está disponible y la tarea lo puede utilizar; si S = 0 el recurso no está disponible y el proceso debe esperar.
Los semáforos se implementan con una cola de tareas o de condición a la cual se añaden los procesos que están en espera del recurso.
Sólo se permiten tres operaciones sobre un semáforo
– Inicializar
– Espera (wait)
– Señal (signal)
En algunos textos, se utilizan las notaciones P y V para las operaciones de espera y señal respectivamente, ya que ésta fue la notación empleada originalmente por Dijkstra para referirse a las operaciones.
Así pues, un semáforo binario se puede definir como un tipo de datos especial que sólo puede tomar los valores 0 y 1, con una cola de tareas asociada y con sólo tres operaciones para actuar sobre él.
Las operaciones pueden describirse como sigue:
• inicializa (S: SemaforoBinario; v: integer)
Poner el valor del semáforo S al valor de v (0 o 1)
• espera (S)
if S = 1 then S := 0
else suspender la tarea que hace la llamada y ponerla
en la cola de tareas
• señal (S)
if la cola de tareas está vacía then S := 1
else reanudar la primera tarea de la cola de tareas
Las operaciones son procedimientos que se implementan como acciones indivisibles y por ello la comprobación y cambio de valor del indicador se efectúa de manera real como una sola operación, lo cual hay que tener presente a la hora de diseñar el planificador de tareas. En sistemas con un único procesador bastará simplemente con inhibir las interrupciones durante la ejecución de las operaciones del semáforo. En los sistemas multiprocesador, sin embargo, este método no resulta ya que las instrucciones de los procesadores se pueden entrelazar de cualquier forma. La solución está en utilizar instrucciones hardware especiales, si se dispone de ellas, o en introducir soluciones software como las vistas anteriormente, que ya indicamos, que servían tanto para sistemas uniprocesador como para sistemas multiprocesador.
La operación inicializa se debe llevar a cabo antes de que comience la ejecución concurrente de los procesos ya que su función exclusiva es dar un valor inicial al semáforo.
Un proceso que corre la operación espera y encuentra el semáforo a 1, lo pone a 0 y prosigue su ejecución. Si el semáforo está a 0 el proceso queda en estado de espera hasta que el semáforo se libera. Dicho estado se debe considerar como uno más de los posibles de un proceso. Esto es así debido a que un proceso en espera de un semáforo no está en ejecución ni listo para pasar a dicho estado puesto que no tiene la CPU ni puede pasar a tenerla mientras que no se lo indique el semáforo. Tampoco es válido el estado suspendido, ya que este estado está pensado para que lo utilicen llamadas al sistema operativo para suspender o reactivar un proceso que no tiene por qué tener una conexión con los semáforos. El diagrama de transición de estados de la figura se puede ampliar con un nuevo estado que denominamos de espera, figura E.
Figura E Transiciones para el estado de espera
Cuando se ejecuta la operación señal puede haber varios procesos en la lista o cola, el proceso que la dejará para pasar al estado listo dependerá del esquema de gestión de la cola de tareas suspendidas que se haya implementado en el diseño del semáforo, por ejemplo: prioridades, FIFO, etc. Si no hay ningún proceso en espera del semáforo este se deja libre (S := 1) para el primero que lo requiera.
Modelo de Sincronización de Exclusión Mutua Con Semáforos
La exclusión mutua se realiza fácilmente utilizando semáforos. La operación de espera se usará como procedimiento de bloqueo antes de acceder a una sección crítica y la operación señal como procedimiento de desbloqueo. Se utilizarán tantos semáforos como clases de secciones críticas se establezcan.
El proceso P1 de la sección anterior ahora toma la forma:
process P1
begin
loop
espera (S) ;
Sección Crítica
señal (S) ;
Suspendido
Durmiente
Listo
Espera Ejecución
Espera
Señal
(* resto del proceso *)
end
end P1;
Modelo de Sincronización por Mensajes
Los mensajes proporcionan una solución al problema de la concurrencia de procesos que integra la sincronización y la comunicación entre ellos y resulta adecuado tanto para sistemas centralizados como distribuidos. Esto hace que se incluyan en prácticamente todos los sistemas operativos modernos y que en muchos de ellos se utilicen como base para todas las comunicaciones del sistema, tanto dentro del computador como en la comunicación entre computadores.
La comunicación mediante mensajes necesita siempre de un proceso emisor y de uno receptor así como de información que intercambiarse. Por ello, las operaciones básicas para comunicación mediante mensajes que proporciona todo sistema operativo son:
Enviar(mensaje) y recibir(mensaje). Las acciones de transmisión de información y de sincronización se ven como actividades inseparables.
La comunicación por mensajes requiere que se establezca un enlace entre el receptor y el emisor, la forma del cual puede variar grandemente de sistema a sistema. Aspectos importantes a tener en cuenta en los enlaces son: como y cuantos enlaces se pueden establecer entre los procesos, la capacidad de mensajes del enlace y tipo de los mensajes.
Su implementación varía dependiendo de tres aspectos:
1- El modo de nombrar los procesos.
2- El modelo de sincronización.
3- Almacenamiento y estructura del mensaje.
MODOS DE NOMBRAR LOS MENSAJES
El proceso de denominación de las tareas para la comunicación por mensajes se puede realizar de dos formas distintas: directa e indirectamente. En la comunicación directa ambos procesos, el que envía y el que recibe, nombran de forma explícita al proceso con el que se comunican.
Las operaciones de enviar y recibir toman la forma:
enviar(Q, mensaje): envía un mensaje al proceso Q
recibir(P, mensaje): recibe un mensaje del proceso P
Este método de comunicación establece un enlace entre dos procesos que desean comunicar, proporcionando seguridad en el intercambio de mensajes, ya que cada proceso debe conocer la identidad de su pareja en la comunicación, pero, por lo mismo, no resulta muy adecuado para implementar rutinas de servicio de un sistema operativo.
En la comunicación indirecta los mensajes se envían y reciben a través de una entidad intermedia que recibe el nombre de buzón o puerto. Como su nombre indica, un buzón es un objeto en el que los procesos dejan mensajes y del cual pueden ser tomados por otros procesos. Ofrecen una mayor versatilidad que en el caso de nombramiento directo, ya que permiten comunicación de uno a uno, de uno a muchos, de muchos a uno y de muchos a muchos.
Cada buzón tiene un identificador que lo distingue. En este caso las operaciones básicas de comunicación toman la forma:
enviar(buzónA, mensaje): envía un mensaje al buzón A
recibir(buzónA, mensaje): recibe un mensaje del buzón A.
El buzón establece un enlace que puede ser utilizado por más de dos procesos y permite que la comunicación de un proceso con otro se pueda realizar mediante distintos buzones.
En el caso de que haya varios procesos que recogen información del mismo buzón se plantea el problema de quien debe recoger un mensaje. Se pueden dar distintas soluciones: permitir que un buzón sólo pueda ser compartido por dos procesos, permitir que cada vez sólo un proceso pueda ejecutar una operación de recibir y, por último, que el sistema identifique al receptor del mensaje.
Además de las operaciones básica mencionadas, los sistemas operativos suelen proporcionar operaciones adicionales como las de crear y eliminar buzones.
MODELOS DE SINCRONIZACIÓN
Las diferencias en los modelos usados para la sincronización de los procesos se debe a las distintas formas que puede adoptar la operación de envío del mensaje.
a) Síncrona. El proceso que envía sólo prosigue su tarea cuando el mensaje ha sido recibido.
b) Asíncrona. El proceso que envía un mensaje sigue su ejecución sin preocuparse de si el mensaje se recibe o no.
- Invocación remota. El proceso que envía el mensaje sólo prosigue su ejecución cuando ha recibido una respuesta del receptor.
El método síncrono necesita de que ambos procesos, el emisor y el receptor, se "junten" para realizar una comunicación, por lo que se suele denominar encuentro( "rendezvous"). Si no se ha emitido una señal de recibir cuando se ejecuta la operación de enviar, el proceso emisor se suspende hasta que la ejecución de una operación de recibir le saca de ese estado. Cuando el proceso que envía el mensaje continúa sabe que su mensaje ha sido recibido. De este modo una pareja emisor-receptor no puede tener más de un mensaje pendiente en cada momento.
En el modelo asíncrono el sistema operativo se encarga de recoger el mensaje del emisor y almacenarlo en espera de que una operación de recibir lo recoja. Normalmente este tipo de comunicación tiene limitado la cantidad de memoria que puede utilizar una pareja en comunicación directa o un buzón en comunicación indirecta, para evitar así
que un uso descontrolado pudiera agotar la cantidad de almacenamiento temporal del sistema.
A la invocación remota también se le conoce como encuentro extendido, ya que el receptor puede realizar un número arbitrario de cómputos antes de enviar la respuesta. La operación de recibir, tanto en los métodos de nominación directa como indirecta, se suele implementar de modo que el proceso que ejecuta la operación toma un mensaje si este está presente y se suspende si no lo está. Sin embargo, este modo de funcionamiento plantea el problema de una espera indefinida en el caso de que un fallo impida que llegue un mensaje. Una solución consiste en proporcionar una operación de recibir sin bloqueo, que en algunos sistemas se denomina aceptar, de modo que si el mensaje está presente se devuelve, y si no lo está se devuelve un código de error. Otra solución más adecuada consiste en especificar en la sentencia de recibir un tiempo máximo de espera del mensaje. Si transcurre el tiempo especificado el sistema operativo desbloquea al proceso suspendido y le envía un mensaje o código de error indicando el agotamiento del tiempo de espera. Por ejemplo, en un sistema con nominación indirecta la operación de recibir puede tener la forma:
recibir(buzón, mensaje, tiempo_espera).
Aunque la especificación del tiempo de espera se podría realizar también en la operación de envío, resulta suficiente implementarla en la operación de recibir, por lo que es esto lo habitual en la mayoría de los sistemas operativos. Se pueden relacionar las distintas formas de enviar un mensaje. Dos operaciones asíncronas pueden constituir una relación síncrona si se envía una señal de reconocimiento. Así, si dos procesos, P y Q, se comunican de forma directa asíncrona se puede establecer la sincronización entre ellos mediante las operaciones:
P
enviar(Q, mensaje)
recibir(P, reconocimiento)
Q
recibir(P, mensaje)
enviar(P,reconocimiento)
El proceso P envía el mensaje a Q y después se suspende en espera de un mensaje de reconocimiento por parte de Q. Cuando el mensaje Q recibe el mensaje envía un mensaje de reconocimiento a P que hace que este pueda proseguir su ejecución.
La operación de envío con buzón también puede ser síncrona si se implementa de modo que el remitente se suspende hasta que el mensaje ha sido recibido.
La invocación remota se puede construir a partir de dos comunicaciones síncronas:
P
enviar(Q, mensaje)
recibir(P, respuesta)
Q
recibir(P, mensaje)
…….
construye respuesta
…….
enviar(P,respuesta)
Como una señal de envío asíncrona se puede utilizar para construir los otros dos modos se podría argumentar que este método es más flexible y es el que debería implementarse en todos los casos. Sin embargo adolece del inconveniente de que al no saberse cuando se recibe el mensaje la mayoría se programan para recibir un mensaje de reconocimiento, es decir, se hacen síncronas; también son más difíciles de depurar.
ALMACENAMIENTO Y ESTRUCTURA DEL MENSAJE
En la transferencia de información en un enlace se deben tener en cuenta la forma en la que esta se produce y la capacidad o número de mensajes que admite el enlace. A su vez, el intercambio de información se puede realizar de dos formas: por valor o por referencia.
En la transferencia por valor se realiza una copia del mensaje del espacio de direcciones del emisor al espacio de direcciones del receptor, mientras que en la transferencia por referencia se pasa un puntero al mensaje. La transferencia por valor tiene la ventaja de que mantiene el desacoplo en la información que maneja el emisor y el receptor, lo que proporciona mayor seguridad en la integridad de la información. Tiene el inconveniente del gasto de memoria y tiempo que implica la copia, que además se suelen ver incrementados por el uso de una memoria intermedia. Estos inconvenientes son justamente los convenientes de la transmisión por referencia que tiene como aspecto negativo el necesitar mecanismos adicionales de seguridad para compartir la información entre los procesos. El método de sincronización de la invocación remota utiliza necesariamente la transferencia por valor, mientras que los métodos síncrono y asíncrono pueden utilizar ambos modos.
Los sistemas operativos tienen asociado a cada enlace una cola en la cual mantienen los mensajes pendientes de ser recibidos. En la comunicación síncrona la cola se puede considerar que tiene una longitud nula ya que, como se ha indicado, los dos procesos deben encontrarse para proceder al intercambio del mensaje. En este caso se dice también que la transferencia se realiza sin utilización de una memoria intermedia. Sin embargo, en la comunicación asíncrona y en la invocación remota la implementación de la cola se realiza normalmente con una capacidad de mensajes finita mayor que cero, m.
Cuando el proceso emisor envía un mensaje, si la cola no está llena, se copia el mensaje y el proceso continúa su ejecución. Si la cola está llena el proceso se suspende hasta que queda espacio libre en la cola. Si el mensaje se pasa por referencia la cola guarda los punteros a los mensajes y los valores de esto si el paso es por valor. En algunos casos se considera que la capacidad de la cola es ilimitada, de manera que un proceso nunca se suspende cuando envía un mensaje.
Atendiendo a la estructura de los mensajes estos se pueden considerar divididos en tres tipos:
a) Longitud fija
b) Longitud variable
c) De tipo definido
El primer tipo resulta en una implementación física que permite una asignación sencilla y eficaz principalmente en las transferencias por valor. Por el contrario dificulta la tarea de la programación. Los mensajes de longitud variable son más adecuados en los sistemas donde la transferencia se realiza por punteros, ya que la longitud del mensaje puede formar parte de la propia información transmitida. La programación en este caso resulta más sencilla a expensas de una mayor dificultad en la implementación física.
Por último, los mensajes con definición del tipo son adecuados en la comunicación con buzones. A cada buzón que utilice un proceso se le puede asignar el tipo de dato adecuado para dicho mensaje y sólo mensajes con esa estructura pueden ser enviados por ese enlace.
Por ejemplo, en un lenguaje de programación con declaración explícita de buzones se podría tener la sentencia
buzónA: mailbox[p] of dato; para declarar un buzón con el identificador buzónA con una capacidad de p elementos del tipo dato.
Ejemplo
Este ejemplo muestra como se puede utilizar la comunicación por mensajes para implementar un semáforo binario. Se supone que se utiliza un buzón asíncrono con una cola ilimitada conocido tanto por el procedimiento de espera como por el de señal.
module semaforo;
type
mensaje = record …. ;
const
nulo = ….;
procedure espera(var S:integer);
var
temp: mensaje;
begin
recibir(Sbuzon,temp);
S := 0;
end espera;
procedure señal(var S: integer);
begin
enviar(Sbuzon,nulo);
end señal;
procedure inicializa(var S:integer; valor:boolean);
begin
if valor = 1 then
enviar(Sbuzon,nulo);
end;
S := valor;
end inicializa;
begin
crear_buzon(Sbuzon);
end {semaforo}
El buzón creado se identifica de forma exclusiva con el semáforo. El mensaje que se transmite es irrelevante ya que el paso de mensajes tiene la única misión de sincronizar tareas, por ello se utiliza un mensaje nulo. El semáforo está libre cuando hay un mensaje en la cola. En este caso, si un proceso ejecuta una señal de espera (lo que equivale a una operación de recibir) puede proseguir su ejecución. Cualquier otro proceso que ejecute una operación de espera no podrá leer ningún mensaje ya que la cola está vacía y, por lo tanto, se suspenderá hasta que es señalado (enviado un mensaje) por otro proceso. El comportamiento del primer proceso que emita la señal de espera dependerá de la inicialización que se haya hecho del semáforo.
Si se inicializa con un valor de 1 se envía un mensaje al buzón y el primer proceso en acceder al semáforo podrá leer el mensaje y pondrá, por lo tanto, al semáforo en ocupado. Si se inicializa a 0, el buzón esta inicialmente vacío y el semáforo aparece como ocupado, luego un proceso que ejecute la operación de espera se suspende hasta que se ejecute una operación de señal por otro proceso.
Para que el semáforo pueda funcionar es necesario suponer que sólo hay un mensaje circulando a la vez y que este sólo puede ser conseguido por uno de los procesos que están en la espera.
Problemas de Sincronización
En los sesentas Edsger Dijkstra y cinco de sus colegas desarrollaron uno de los primeros sistemas operativos que soportaban la multiprogramación. El sistema fue diseñado en la Universidad Tecnológica de Eindhoven en Holanda, y fue llamado sistema multiprogramación THE, (debido al nombre de la Universidad en alemán.). Una de las principales aportaciones de este sistema fue la incorporación del concepto de semáforos, como herramienta para implementación de la exclusión mutua.
Por ese mismo tiempo Dijkstra escribió un artículo sobre la cooperación de procesos. Este papel mostraba como utilizar los semáforos para resolver una variedad de problemas de sincronización, como el de los productores/consumidores, los
filósofos que cenan (sabios) y el del barbero dormilón.
En su papel sobre monitores Tony Hoare [Hoa74] introdujo el concepto de semáforos binarios separados y muestra cómo usarlos para implementar monitores. Sin embargo Dikstra, fue el que tiempo después le dio un nombre a la técnica e ilustro su uso general. Más concretamente Dijkstra, mostro como implementar semáforos generales usando solo semáforos binarios.
Es posible encontrar diferentes soluciones para el problema de los filósofos que cenan. Una de las soluciones utiliza asimetría para evitar el interbloqueo (i.e. que dos filósofos se bloqueen entre ellos).
Es decir un filósofo toma el tenedor en orden diferente que los otros. También se podría definir un orden en el que los filósofos de número impar tomen un tenedor en ese orden, y que los filósofos de número par lo toman en otro orden. Una segunda forma de evitar el interbloqueo es permitir que a lo mas cuatro filósofos puedan tomar tenedores, (i.e. permitir que a lo mas cuatro filósofos se sienten en la mesa.). Una tercera solución es tener a los filósofos tomando tenedores al mismo tiempo, dentro de una sección crítica, sin embargo esto puede llevar a un problema de inanición (i.e. algún filosofo podrá quedarse sin cenar). Mani Chandy y Jay Misra proponen una cuarta solución,
basada en el paso de fichas entre los filósofos, (esta solución es apropiada para sistemas distribuidos).
Las anteriores soluciones son determinísticas, (i.e. cada proceso ejecuta un conjunto predecible de acciones). Lehman y Rabin, presentan una interesante solución probabilística que es perfectamente simétrica. La idea base es que cada filosofo usa lanzamientos de monedas para determinar el orden en el cual trataran de tomar los tenedores, y si dos filósofos desean utilizar el mismo tenedor, el filosofo que más recientemente utilizo el tenedor le da preferencia al otro.
Courtois, Heymans y Parnas introdujeron el problema de los lectores escritores y presentaron dos soluciones usando semáforos. En una de ellas se le da preferencia a los lectores y en la otra a los escritores.
Los CLÁSICOS problemas de la SINCRONIZACIÓN de Procesos
El del fumador de cigarros, Considere un sistema con tres procesos fumadores y un proceso agente. Cada fumador está continuamente enrollando y fumando cigarrillos. Sin embargo, para enrollar y fumar un cigarrillo, el fumador necesita tres ingredientes: tabaco, papel, y fósforos. Uno de los procesos fumadores tiene papel, otro tiene el tabaco y el tercero los fósforos. El agente tiene una cantidad infinita de los tres materiales. El agente coloca dos de los ingredientes sobre la mesa. El fumador que tiene el ingrediente restante enrolla un cigarrillo y se lo fuma, avisando al agente cuando termina. Entonces, el agente coloca dos de los tres ingredientes y se repite el ciclo.
La panaderia de Lamport, en este problema una panadería tiene una variedad de panes y pasteles vendidos por n vendedores. Cada uno de los cuales toma un número al entrar. El cliente espera hasta oír su número. Cuando el vendedor se desocupa, llama al siguiente numero.
Los filósofos que cenan (sabios), Hay cinco filósofos chinos que se pasan sus vidas pensando y comiendo. Comparten una mesa circular, alrededor de la cual se sientan. En su centro se encuentra con una provisión infinita de arroz, y sobre ella hay cinco palitos, uno de cada lado de los filósofos. Cuando un filósofo piensa, no interactúa con sus colegas. De vez en cuando, un filósofo tiene hambre y trata de levantar los dos palitos más cercanos a él. Un filosofo puede levantar un palito a la vez, y no puede tomar un palito que ya está en la mano de un vecino. Cuando un filósofo tiene ambos palitos, puede comer. Cuando termino de hacerlo, deja sus dos palitos y comienza a pensar de nuevo.
El barbero dormilón, Una peluquería tiene un barbero, una silla de peluquero y n sillas para que se sienten los clientes en espera, si es que los hay. Si no hay clientes presentes, el barbero se sienta en su silla de peluquero y se duerme. Cuando llega un cliente, este debe despertar al barbero dormilón. Si llegan más clientes mientras el barbero corta el cabello de un cliente, estos deben esperar sentados (si hay sillas desocupadas) o salirse de la peluquería (si todas las sillas están ocupadas). El problema consiste en programar al barbero y los clientes sin entrar en condición de competencia.
Lectores y escritores, imaginemos una enorme base de datos, como por ejemplo un sistema de reservaciones de en una línea aérea, con muchos procesos en competencia, que intentan leer y escribir en ella. Se puede aceptar que varios procesos lean la base de datos al mismo tiempo, pero si uno de los procesos está escribiendo, (es decir modificando) la base de datos, ninguno de los demás procesos deberá tener acceso a esta, ni siquiera los lectores. El problema es como programar a los lectores y escritores.
Productor/Consumidor, También conocido como bounded buffer problem o problema del buffer limitado. Dos procesos comparten un almacén (buffer) de tamaño fijo. Uno de ellos, el productor, coloca información en el almacén (buffer) mientras que el otro, el consumidor, la obtiene de él. Si el productor desea colocar un nuevo elemento, y el almacén se encuentra lleno, este deberá irse a dormir". El consumidor despertara al productor cuando elimine un elemento del almacén. De forma análoga, si el almacén esta vacio y el consumidor desea eliminar un elemento del almacén, este debe dormirse" hasta que el productor coloque algo en el almacén.
Soluciones a algunos problemas
A continuación se presentan soluciones algunos de los problemas discutidos anteriormente. Como toda solución, no es la única, es posible que el lector encuentre otra.
Solución al problema productor consumidor con semáforos
La solución utiliza tres semáforos. La solución es presentada en un lenguaje cercano a C.
semaforo mutex = 1;
semaforo vacio = N;
semaforo lleno = 0;
productor()
{
while (TRUE) {
produce_item();
P(vacio);
P(mutex);
introducir_item();
V(mutex);
V(lleno);
}
consumidor()
{
while (TRUE) {
produce_item();
P(lleno);
P(mutex);
retirar_item();
V(mutex);
V(vacio);
consume_item();
}
Solución productor consumidor con monitores
Un ejercicio interesante para el lector es el de comparar esta solución con la presentada en la sección anterior. La solución es presentada en un lenguaje muy cercano a Pascal.
monitor ProductorConsumidor
condition vacio, lleno;
integer count;
procedure producir;
begin
if (count = N) then
wait(lleno);
introducir_item;
count=count+1;
if (count = 1) then
signal(vacio);
end
procedure consumir;
begin
if (count = 0) then
wait(vacio);
retirar_item;
count=count-1;
if (count = N-1) then
signal(lleno);
end;
count=0;
end monitor;
procedure productor
begin
while (true) do
begin
producir_item;
ProductorConsumidor.producir
end
end
procedure consumidor
begin
while (true) do
begin
ProductorConsumidor.consumir;
consumir_item;
end
end
Solución al problema de la cena de los filósofos
La solución utiliza un arreglo state para llevar un registro de la actividad de un filosofo: si está comiendo, pensando o hambriento. Un filósofo solo puede comer si los vecinos no están comiendo. Los vecinos del i-ésimo filósofo se definen en los macros LEFT y RIGHT. En otras palabras si i = 2 entonces LEFT = 1 y RIGHT = 3. Así mismo el programa utiliza un arreglo de semáforos, uno por cada filosofo, de manera que los filósofos hambrientos pueden bloquearse si los tenedores necesarios están ocupados.
#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
semaforo mutex = 1;
semaforo s[N];
filosofo()
{
while (TRUE) {
think();
toma_tenedor(i);
come();
libera_tenedor(i);
}
}
toma_tenedor(int i)
{
P(mutex);
state[i]=HUNGRY;
test(i);
V(mutex);
P(s[i]);
}
libera_tenedor(int i)
{
P(mutex);
state[i]=THINKING;
test(LEFT);
test(RIGHT);
V(mutex);
}
test(int i)
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
state[i] = EATING;
V(s[i]);
}
}
Solución problema lectores/escritores
semaforo mutex = 1;
semaforo db = 1;
int rc = 0;
lector()
{
while (TRUE) {
P(mutex);
rc = rc+1;
if (rc == 1)
P(db);
V(mutex)
leer_datos();
P(mutex);
rc = rc+1;
if (rc == 0)
V(db);
V(db);
procesamiento_datos();
}
escritor()
{
while (TRUE) {
analizando_dato();
P(db);
escribir_datos();
V(db);
}
Solución problema barbero dormilón
#define CHAIRS 5
semaforo clientes=0;
semaforo barberos=0;
semaforo mutex=1;
int waiting = 0;
barbero()
{
P(clientes);
P(mutex)
waiting = waiting – 1;
V(barberos)
V(mutex);
cortar_pelo();
}
cliente()
{
P(mutex);
if (waiting < CHAIRS) {
waiting = waiting + 1;
V(clientes);
V(mutex);
P(barberos);
tomar_barbero();
}
else
V(mutex);
}
Interbloqueo
Definición:
El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. Un proceso esta interbloqueado si está esperando por un evento determinado que nunca va a ocurrir. No existe una solución eficiente para el caso general. Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o más procesos.
El bloqueo es permanente hasta que el sistema realice una operación extraordinaria, como puede ser matar a uno o más procesos u obligar a uno o más procesos a retrazar su ejecución. El ínterbloqueo puede involucrar a recursos tanto consumibles como reutilizables. Un recursos consumible es aquel que se destruye al ser adquirido por un proceso; por ejemplo los mensajes, la información de los buffers de e/s. Un recurso reutilizable es aquel que no se destruyo o se desgasto con el uso como ser un canal de e/s o zona de memoria.
MÉTODOS PARA EL TRATAMIENTO DE INTERBLOQUEO
PRINCIPIOS DEL INTERBLOQUEO:
Un ejemplo clásico de ínter bloqueo es el ínter bloque de tráfico. La Figura siguiente la cual muestra una situación en la que cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro cuadrantes de la intersección son los recursos compartidos sobre los que se demanda control; si los cuatro coches desean atravesar el cruce, las necesidades de recursos son las siguientes.
• El coche que va hacia el norte necesita los cuadrantes 1 y 2
• El coche que va hacia el oeste necesita los cuadrantes 2 y 3
• El coche que va hacia el sur necesita los cuadrantes 3 y 4
• El coche que va hacia el este necesita los cuadrantes 4 y 1
Representación del ínter bloqueo
La forma más habitual en la carretera es que un coche en un cruce de cuatro caminos debe ceder el paso que está a su derecha. Esta norma funciona si solo hay dos o tres coches en el cruce.
Si los cuatro coches llegan al mismo tiempo, más o menos, cada un se abstendrá de entrar en el cruce, provocando ínter bloqueo. Si todos los coches ignoran las normas y entran (con cuidado) en el cruce, cada coche obtendrá un recurso (un cuadrante) pero no podrá continuar porque el segundo recurso que necesita ya ha sido invadido por otro coche. De nuevo, se tiene ínter bloqueo.
RECURSOS REUTILIZABLES:
Un recurso reutilizable es aquel que puede ser usado con seguridad por un proceso y no se agota con el uso.
Los procesos obtienen unidades de recursos que liberan posteriormente para que otros procesos las reutilicen. Ejemplo, los procesadores, canales E/S, memoria principal y secundaria, dispositivos y estructuras de datos tales como archivos, bases de datos y semáforos.
Como ejemplo de ínter bloqueo con recursos reutilizables, considérese dos procesos que compiten por el acceso exclusivo a un archivo D del disco y una unidad de cinta T. El ínter bloqueo se produce si cada proceso retiene un recurso y solicita el otro. Por ejemplo, se produce ínter bloqueo si el sistema multiprogramado itera la ejecución de los dos procesos de la siguiente forma:
p0p1q0q1p2q2
El diseño de un programa concurrente entraña gran dificultad. Se producen ínter bloqueos como este y la causa esta frecuentemente en la complejidad de la lógica del programa, haciendo más difícil su detección. Una posible estrategia para resolver estos ínter bloqueos es imponer restricciones en el diseño del sistema sobre el orden en el que se solicitan los recursos.
RECURSOS CONSUMIBLES:
Un recurso consumible es aquel que puede ser creado (producido) y destruido (consumido). Normalmente, no hay límite en el número de recursos consumibles de un tipo en particular. Un proceso productor que no está bloqueado puede liberar cualquier número de recursos consumibles. Como ejemplos de recursos consumibles están las interrupciones, señales, mensajes e información en buffers de E/S.
Como ejemplo de ínter bloqueo con recursos consumibles, considérese el siguiente par de procesos, en el que cada proceso intenta recibir un mensaje de otro y, después, enviar un mensaje a otro.
El ínter bloqueo se produce si el Recieve es bloqueante (por ejemplo, el proceso receptor está bloqueado hasta que recibe el mensaje). La causa del ínter bloqueo es un error de diseño. Estos errores pueden ser bastante sutiles y difíciles de detectar.
Un programa puede funcionar durante un periodo de tiempo considerable, incluso años, antes de que el problema se manifieste.
No hay ninguna estrategia sencilla y efectiva que pueda solucionar todas las clases de ínter bloqueo. Antes de examinar cada uno ellos, se explicaran las condiciones de ínter bloqueo.
Por ejemplo, supongamos que se tienen dos procesos P1 y P2 que desean acceder a dos Recurso (impresora y disco, por ejemplo) a los que sólo puede acceder un proceso cada Vez. Suponemos que los recursos están protegidos por los semáforos S1 y S2. Si los procesos acceden a los recursos en el mismo orden no hay ningún problema:
P1
……
espera(S1)
espera(S2)
..
..
señal(S2)
señal(S1)
end P1
P2
……
espera(S1)
espera(S2)
..
..
señal(S2)
señal(S1)
end P2
El primer proceso que toma S1 también toma S2 y posteriormente libera los recursos en el orden inverso a como se tomaron y permite al otro proceso acceder a ellos. Sin embargo, si uno de los procesos desea utilizar los recursos en orden inverso, por ejemplo:
P1
……
espera(S1)
espera(S2)
..
..
señal(S2)
señal(S1)
end P1
P2
……
espera(S2)
espera(S1)
..
..
señal(S1)
señal(S2)
end P2
Podría ocurrir que P1 tomara el primer recurso (semáforo S1) y P2 el segundo recurso (semáforo S2) y se quedarán ambos en espera de que el otro liberará el recurso que posee.
Este error no ocurre con demasiada frecuencia pero sus consecuencias suelen ser devastadoras. En algunas ocasiones puede resultar fácil darse cuenta de la posibilidad de que ocurra el interbloqueo, pero la mayoría de las veces resulta realmente complicado detectarlo.
CONDICIONES DE INTERBLOQUEO:
Deben darse tres condiciones para que pueda producirse un ínter bloqueo:
1. EXCLUSIÓN MUTUA: Solo un proceso puede usar un recurso cada vez.
2. RETENCIÓN Y ESPERAR: Un proceso puede retener unos recursos asignados mientras espera que se le asignen otros.
3. NO APROPIACIÓN: Ningún proceso puede ser forzado a abandonar un recurso que retenga.
En la mayoría de los casos, estas condiciones son bastantes necesarias. Por ejemplo, la exclusión mutua hace falta asegurar la consistencia de resultados y la integridad de la base de datos. La apropiación no se puede aplicar arbitrariamente, y cuando se encuentran involucrados recursos de datos debe estar acompañada de un mecanismo de recuperación y reanudación, que devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso pueda finalmente repetir sus acciones.
4. CÍRCULO VICIOSO DE ESPERA: existe una cadena cerrada de procesos, cada uno de los cuales retiene, al menos, un recurso que necesita el siguiente proceso de la cadena.
Las tres primeras condiciones son necesarias, pero no suficientes, para que exista ínter bloqueo.
La cuarta condición es, una consecuencia potencial de las tres primeras. Dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble. Un circulo de espera irresoluble es, la definición de ínter bloqueo.
En resumen, las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el ínter bloqueo.
EXCLUSIÓN MUTUA:
En general, la primera de las cuatro condiciones no puede anularse. Si el acceso a un recurso necesita exclusión mutua, el sistema operativo debe soportar la exclusión mutua. Algunos recursos, como los archivos, pueden permitir varios accesos para lectura, pero solo accesos exclusivos para escritura. Se puede produce ínter bloqueo si más de un proceso necesita permiso de escritura.
RETENCIÓN Y ESPERA:
La condición de retención y espera puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente. Esta solución resulta ineficiente. En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando que se concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con solo algunos de los recursos. En segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables, tiempo durante el cual se priva del acceso a otros procesos.
Esta también el problema práctico creado por el uso de programación modular o estructuras multihilo en una aplicación. Para poder hacer esta petición simultánea, una aplicación necesitaría conocer todos los recursos que va a necesitar en todos los niveles o en todos los módulos.
NO APROPIACIÓN:
La condición de no apropiación puede prevenirse de varias formas. Si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional. Si un proceso solicita un recurso que actualmente esta retenido por otro proceso, el sistema operativo puede expulsar al segundo proceso y exigirle que libere sus recursos. Este último esquema evitara el ínter bloqueo solo si no hay dos procesos que posean la misma prioridad.
Esta técnica es práctica solo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse mas tarde de una forma fácil, como es el caso de un procesador.
CIRCULO VICIOSO DE ESPERA:
La condición de círculo vicioso de espera puede prevenirse definiendo una ordenación lineal de los tipos de recursos. Si a un proceso se le han asignado recursos de tipo R, entonces solo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación.
Para comprobar el funcionamiento de esta estrategia, se asocia un índice a cada tipo de recurso. En tal caso, el recurso Ri antecede a Rj en la ordenación si i < j. Supóngase que dos procesos A y B, están ínter bloqueados, porque A ha adquirido Ri y solicitado Rj, mientras que B ha adquirido Rj y solicitado Ri. Esta condición es posible porque implica que i < j y j < i.
Como en la retención y espera, la prevención del círculo vicioso de espera puede ser ineficiente, retardando procesos y denegando accesos a recursos innecesariamente.
ALGORITMO DE DETECCIÓN DEL INTERBLOQUEO
El Control del Ínter bloqueo suele realizarse de forma frecuente tanto como las solicitudes de recurso o una frecuencia menos dependiendo esta de la ocurrencia del ínter bloqueo, por lo tanto la comprobación de cada una de las solicitudes de recurso posee ventajas como: la conducción a una pronta detección y el Algoritmo es relativamente simple, puesto que está basado en cambios de aumentos del estado del sistema. De otra forma, tal frecuencia de comprobaciones consume un tiempo de procesador considerable.
Un algoritmo de detección utilizado frecuentemente es uno donde utilizamos una matriz de asignaciones, un vector de recursos disponibles además de emplear otra matriz de solicitud (Q) definida tal que representa la cantidad de recursos del tipo J solicitados por el proceso i. Dicho algoritmo funciona marcando los procesos que no están ínter bloqueados. Al inicio de todos los procesos están sin marcar por lo tanto para su cancelación se debe llevar una serie de pasos:
1º Se marca cada proceso que tiene la columna asignación.
A cero.
2º Se inicia al vector temporal W con el vector disponible
3º Se busca un índice i tal que el proceso i no este marcado
y la columna i-csigma de Q sea menor o igual que W ósea
Qk < W para i< k < m. Si no se encuentra el algoritmo ha
Terminado.
4º Si se encuentra la columna. Se marca el proceso i y se
Sema la columna correspondiente de la matriz asignación
W osea Wk = Wk + Ak para i < K< M.Se vuelve al paso 3
RECUPERACIÓN
Una vez detectado el ínter bloqueo hace falta alguna estrategia de recuperación basándonos en la idea de que para romper el ínter bloqueo de un sistema hay que anular una amas de las condiciones necesarias (esperar por exclusión mutua no apropiatividad espera circular) que se dan para el ínter bloqueo, anticipando la perdida que sufrirán algunos procesos de todo lo realizado hasta el momento.
Las técnicas diferentes son diferentes puntos de enfoque según su orden decreciente de sostificación:
1º Abortar los procesos ínter bloqueados. Es la solución más común que adopta un S.O.
2º Retroceder cada proceso hasta algún punto de control definido, Previamente volver a ejecutar cada proceso. Es necesario que se tenga disponible mecanismo de retroceso y de reinicio de sistema.
El riesgo de tal solución se basa en que se podría repetir el ínter bloqueo principal. No obstante el no determinismo de procesamiento concurrente asegura la mayoría de los casos que esto no va a pasar.
3º Abortar sucesivamente los procesos ínter bloqueados hasta que deje de haber ínter bloquea; el orden en que se eligieran los procesos seguirá un criterio de mínimo coste. Luego de abortar cada proceso se debe ejecutar de nuevo el algoritmo de detección para ver si existe todavía ínter bloqueo.
4º Apropiación de recursos sucesivamente hasta que deje de haber ínter bloqueo de igual forma que el punto anterior la decisión se basa en el mínimo coste y luego se ejecutara el algoritmo de detección después de cada apropiación. Un proceso de apropiación debe retroceder hasta un momento anterior a la adquisición de tal recurso.
Para los dos puntos anteriores el criterio de selección podría basarse:
a-La menor cantidad de procesador consumido hasta ahora
b-El mayor número de líneas de salidas producidas hasta ahora.
c-El mayor tiempo restante estimado.
d-El menor número total de recursos asignados hasta ahora.
e-La prioridad más baja.
BIBLIOGRAFÍA
Referencias
Chandy K.M., and Misra J. The drinking philosphers problem ACM Trans. on Prog. Languages and Systems 6, 4(October), pp. 632-646.
Courtois P.J., Heymans F., y Parnas D.L. Concurrent Control with Readers and Writers, Comm. of the ACM, vol. 10, pp. 667-668, Oct. 1971
Dijkstra E.W. Hierarchical Ordering of Sequential Processes Acta Informatica, Volume 1, Number 2 (1971), pp. 115-138; reprinted in [Hoare and Perrot 1972], pp. 72-93.
Hoare C.A.R. Monitors: an operating system structuring concept Comm. of the ACM 17,10 (October), 549-557.
Lamport L., A New Solution to Dijkstra's Concurrent Programming Problem, Comm. of the ACM, vol 17, pp. 453-455, Ago. 1974
Lehmann D., y Rabin M.O., A symmetric and fully distributed solution to the dining philosophers problem. Prco. Eighth ACM Symp. on Princ. of Prog, Languages, January 1981, pp. 133-138
Tanenbaum A., Modern Operating Systems, 1992 Prentice Hall.
Miguel Pita
| Página siguiente |