Comunicación y sincronización

## Página 46

<!-- source-page: 46 -->

GNUFDL • PID_00214803                                                                                  46                                                                                         Comunicación y sincronización

4.Deadlocks (abrazos mortales o interbloqueos)







En los sistemas operativos actuales, que contienen un número de dispositivos
y un número de procesos considerablemente grande, la posibilidad de la eje-
cución concurrente/paralela de estos procesos y la posibilidad de acceder de
manera concurrente a los dispositivos aumenta el rendimiento del sistema de
manera significativa.


Todo este maremágnum de procesos y recursos a los que se accede a la vez
de manera compartida o exclusiva puede generar fácilmente situaciones de
interbloqueo (deadlock) que hacen que el sistema deje de hacer un trabajo útil.



    Un interbloqueo (deadlock) es una situación en la que un grupo de pro-
    cesos están indefinidamente bloqueados sin ninguna posibilidad de que
    continúe su ejecución. En términos generales, la causa de este bloqueo
    indefinido es que cada proceso del grupo ha adquirido un conjunto de
    recursos necesarios para operar y está esperando otros recursos que han
    sido asignados a otros procesos del grupo. Ello crea una situación en la
    que ningún proceso puede continuar su ejecución.



Los interbloqueos habitualmente aparecen en sistemas concurrentes como
consecuencia de la asignación de recursos del sistema de manera incontrola-
da, es decir, sin mirar o establecer ningún protocolo que intente evitar la si-
tuación. Muchas veces, es el mismo programador de los procesos el que crea
esta situación de manera involuntaria.

## Página 47

<!-- source-page: 47 -->

GNUFDL • PID_00214803                                                                                  47                                                                                         Comunicación y sincronización

    Supongamos que un sistema tiene un dispositivo impresora y un dispositivo disco a los
    que se debe acceder en exclusión mutua. Se crean dos semáforos binarios, disco e impre-
    sora, inicializados en 1 para indicar que los recursos están libres. En el sistema, creamos
    dos procesos que se ejecutan de manera concurrente: P0 (figura 42) y P1 (figura 43).

    ...
    sem_wait(disco)
    sem_wait(impresora)
    /*Utilizar el disco y la impresora*/
    ...
    sem_signal(impresora)
    sem_signal(disco)
    ...

    Figura 42. Código del proceso P0

    ...
    sem_wait(impresora)
    sem_wait(disco)
    /*Utilizar el disco y la impresora*/
    ...
    sem_signal(disco)
    sem_signal(impresora)
    ...

    Figura 43. Código del proceso P1

    Podemos observar que la ejecución secuencial de estos dos procesos es totalmente correc-
    ta y no supone ningún error. En cambio, a la hora de ejecutarse de manera concurrente,
    y según cómo se entrelacen las operaciones de los dos procesos, se puede generar una
    situación de interbloqueo. Por ejemplo, si se produce la secuencia siguiente:

    1) El proceso P0 pide el recurso disco y se le concede, sem_wait (disco).

    2) El proceso P1 pide el recurso impresora y se le concede, sem_wait (impresora).

    3) El proceso P1 pide el recurso disco y se queda bloqueado, sem_wait (disco), ya que
    el disco ha sido asignado.

    4) El proceso P0 pide el recurso impresora y se queda bloqueado, sem_wait (impresora),
    ya que este recurso ha sido asignado al proceso P1.

    A partir de este momento, el proceso P1 espera que se libere el recurso disco, pero éste
    está asignado al proceso P0, que no lo puede liberar porque está bloqueado esperando el
    recurso impresora. Éste tampoco será liberado, ya que el proceso que lo tiene asignado,
    el proceso P1, también está bloqueado. En definitiva, se ha creado un bucle de espera
    del que no hay salida.

Para que se produzca un interbloqueo, se deben dar las cuatro condiciones
siguientes simultáneamente:


•  Exclusión￿mutua: se debe acceder a los recursos en exclusión mutua.


•  Retención￿y￿espera: cada proceso tiene asignados ciertos recursos en ex-
     clusión mutua y espera que se liberen otros.


•  No￿expropiación: los recursos que un proceso tiene asignados tan sólo se
     liberan a petición explícita del propio proceso, el sistema operativo no los
     puede tomar.

## Página 48

<!-- source-page: 48 -->

GNUFDL • PID_00214803                                                                                  48                                                                                         Comunicación y sincronización

•  Espera￿circular: los procesos bloqueados forman una cadena circular en
     la que cada proceso está bloqueado esperando un recurso que ya ha sido
     asignado a otro proceso de la cadena.


Se han propuesto varios mecanismos para tratar de solucionar este problema.
Las diferentes propuestas se pueden clasificar en tres categorías según su ob-
jetivo:


1)￿Prevenir￿el￿interbloqueo: estas propuestas pretenden asegurar que una de
las cuatro condiciones necesarias para el interbloqueo no se producirá nunca.
Lo más sencillo es evitar la espera circular ordenando de manera lineal los re-
cursos del sistema, a fin de que los procesos estén obligados a pedir los recur-
sos que necesiten en un orden creciente dentro de la ordenación especificada.
En el ejemplo anterior, se podría haber prevenido el interbloqueo si todos los
procesos hubieran pedido los recursos en el mismo orden (por ejemplo, pri-
mero el disco y después la impresora).


2)￿Evitar￿el￿interbloqueo: estas propuestas se basan en el hecho de asignar
sólo los recursos disponibles que no puedan generar ningún tipo de interblo-
queo. Esta técnica necesita llevar un control detallado de qué recursos se han
asignado, a qué procesos se han asignado y si estos procesos están esperando
algún otro recurso.


3)￿Detectar￿y￿recuperar￿el￿interbloqueo: las propuestas que utilizan esta téc-
nica dejan que aparezcan interbloqueos, ya que asignan libremente los recur-
sos según los van pidiendo los procesos. De vez en cuando, se comprueba si
se ha producido un interbloqueo mirando si hay algún ciclo en el grafo de re-
cursos asignados. Así se determina qué procesos están bloqueados. Para rom-
per el interbloqueo, el sistema operativo reinicia algunos de los procesos que
estaban bloqueados.