Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Sincronización entre procesos (página 3)



Partes: 1, 2, 3

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.

  1. 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

Partes: 1, 2, 3
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter