Revisión actual del 17:34 2 abr 2020

También conocido como bloqueo mutuo o deadlock.

Es una espera circular permanente de dos o más procesos. Existen una serie de condiciones para que se produzca y una serie de estrategias para resolverlos.

• Ejemplo simple:

Se aprecian dos procesos (P1 y P2), cada uno con un recurso diferente asociado (R1 y R2). Llega un punto en el que el proceso P1 ha adquirido el recurso R1 y el proceso P2 ha adquirido el recurso R2 y cada proceso necesita el otro recurso. Este es el punto de interbloqueo.

Según Dijkstra, una configuración de procesos y recursos es estado seguro si a partir de ella podemos seguir ejecutando código, es decir, no se producen interbloqueos.

Ejemplo

El siguiente ejemplo ilustra el problema con semáforos.

Dados dos procesos P1 y P2 con el siguiente código, con semáforos x e y con contadores a 1:

   P1                             P2
   --                             --

#1    while(1) {                   #1  while(1) { 
#2    down(x);                     #2  down(y);
#3    acceso recurso_x();          #3  acceso_recurso_y();
#4    down(y);                     #4   down(x);
#5    acceso_recurso_y();          #5   acceso_recurso_x();
#6    up(y);                       #6   up(x);
#7    up(x);                       #7   up(y);
 }                               }

El cronograma, suponiendo Round Robin con quantum de 3 unidades sería:

    X = El proceso pasa a estado bloqueado.
    / = El proceso pasa a estado preparado.
    > = Fin de su ejecución

    | #1| #2| #3|   |   |   | #4|   |     
  P1|---|---|---|   |   |   |---X   |    
    |   |   |   |   |   |   |   |   |     
    |   |   |   | #1| #2| #3|   | #4|  
  P2|   |   |   |---|---|---|   |---X   
    |   |   |   |   |   |   |   |   |   
    |___|___|___|___|___|___|___|___|  
    0   1   2   3   4   5   6   7   8  

En el que se puede ver la situación de interbloqueo.

Si repetimos con quantum 4:

    | #1| #2| #3| #4|   |   | #5| #6| #7| #1|   |   |   |   | #2| #3| #4|   /   |   |
  P1|---|---|---|---/   |   |---|---|---|---/   |   |   |   |---|---|---X   |   |   |
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    |   |   |   |   | #1| #2|   |   |   |   | #3| #4| #5| #6|   |   |   | #7| #1| #2|
  P2|   |   |   |   |---|---X   |   /   |   |---|---|---|---/   |   |   |---|---|---X
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
    0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20

La condición de carrera se produce igualmente, pero más tarde.

--Leoberbue (discusión) 16:50 25 nov 2014 (CET)

6.2 Condiciones para el interbloqueo y estrategias de resolución