Interbloqueo en la comunicacion de mensajes

Interbloqueo en la Comunicación de Mensajes Espera Mutua Se produce interbloqueo en la comunicación de mensajes cuando cada uno de los procesos de un grupo de procesos está esperando un mensaje de otro miembro del grupo y no hay mensajesen camino. Para analizar esta situación con más detalle, se definirá el conjunto de dependencia
(DS) de un proceso. Para un proceso P, que está detenidoesperando un mensaje, DS(P) consta de todos los procesos de quienes Pi espera un mensaje. Normalmente, Pi puede continuar si llega cualquier mensaje de los esperados. Una formulación alternativa es que Pi puede continuar sólo después de que lleguen todos los mensajes esperados. La primera situación es más común y es la que aquí se considera. Con la definición anterior, un interbloqueo en un conjunto S deprocesos puede definirse como sigue: 1 . Todos los procesos de S están detenidos en espera de mensajes. 2. S contiene al conjunto de dependencia de todos los procesos de S. 3. Ningún mensaje está de camino entre los miembros de S. Cualquier proceso de S está interbloqueado porque no puede recibir nunca un mensaje que lo libere. En términos gráficos, hay una diferencia entre el interbloqueo demensajes y el interbloqueo de recursos. En el interbloqueo de recursos, se produce interbloqueo cuando hay un bucle cerrado o ciclo en el grafo que representa las dependencias de los procesos. En el caso de los recursos, un proceso depende de otro si el último emplea un recurso que el primero necesita. En el interbloqueo de mensajes, 1a condición de interbloqueo es que todos los sucesores decualquier miembro de S estén asimismo en S; es decir, el grafo de S es un nudo. La figura 13.16 ilustra este apartado. En la figura 31.16a, P1 está esperando un mensaje de P2 o de P5; P5 no está esperando ningún mensaje así que puede enviar un mensaje a P1 que, por tanto, es liberado. Como resultado, los enlaces (P1, P5) y (P1, P2) se eliminan. En la figura 13.16b se añade una dependencia: P5 estáesperando un mensaje de P . El grafo es ahora un nudo y existe interbloqueo.
Como con los recursos, el interbloqueo de mensajes puede atacarse mediante prevención o detección. [RAY88] ofrece varios ejemplos.
No Disponibilidad de Buffers de Mensajes Otra tornea en que puede producirse interbloqueo en un sistema de paso de mensajes es por la asignación de buffers para el almacenamiento de los mensajesen camino. Este tipo de interbloqueo es muy conocido en las redes de datos de conmutación de paquetes I [STAL94a]. Se examinará primero este problema en el contexto de las redes de datos, para posteriormente observarlo desde el punto de vista de un sistema operativo distribuido.
La forma más sencilla de interbloqueo en una red de datos es el interbloqueo directo por almacenamiento y reenvío(store-and-forward) y puede suceder si un nodo de conmutacion ele paquetes utiliza una reserva común de buffers de donde son asignados por solicitud a los paquetes. La figura 13.17a muestra una situación en que todo el espacio para bufferes del nodo A está ocupado por paquetes destinados a B. Lo contrario es cierto en B. Ningún nodo puede aceptar más paquetes porque sus buffers están llenos. Por tanto,ningún nodo puede transmitir ni recibir por ningún enlace. El interbloqueo directo por almacenamiento y reenvío puede impedirse si no se permite que todos los buffers acaben dedicados a un único enlace. Em leando buffers separados de tamaño fijo, uno por cada enlace, se logrará este impedimento. Incluso si se usa una reserva común de buffers se puede evitar el interbloqueo si no se permite queenlaces únicos consigan todo el espacio de buffers. Una forma más sutil de interbloqueo el interbloqueo indirecto por almacenamiento almacenamiento y reenvio,, se ilustra en la figura 13.17b. Para cada nodo, la cola dirigida al nodo adyacente en una dirección está llena de paquetes destinados al nodo más allá del siguiente. Una forma simple de impedir este tipo de interbloqueo es emplear una...