Diferencia entre revisiones de «Definición de interbloqueo»

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
Línea 20: Línea 20:
 
--                              --
 
--                              --
  
#1  while(1) {                      #1while(1) {  
+
#1  while(1) {                      #1  while(1) {  
#2    down(x);                      #2down(y);
+
#2    down(x);                      #2  down(y);
#3    acceso recurso_x();      #3     acceso_recurso_y();
+
#3    acceso recurso_x();      #3 acceso_recurso_y();
 
#4    down(y);                      #4  down(x);
 
#4    down(y);                      #4  down(x);
#5    acceso_recurso_y();      #5     acceso_recurso_x();
+
#5    acceso_recurso_y();      #5   acceso_recurso_x();
#6    up(y);                          #6   up(x);
+
#6    up(y);                          #6   up(x);
 
#7    up(x);                          #7  up(y);
 
#7    up(x);                          #7  up(y);
 
  }                              }
 
  }                              }

Revisión del 09:56 28 nov 2014

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:

Ssoo wiki.png

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)