Publi

Deadlock, bloqueo mutuo, abrazo mortal o cómo colgar un proceso con esperas infinitas. ☠ ☠ ☠

5 agosto, 2014 Author: Gaspar Fernández
6 Comments


Es un ejercicio típico, pero que casi siempre se ve teóricamente, pero mira, vamos a traerlo a la práctica. Lo vamos a implementar con semáforos. Como vemos aquí y aquí, los semáforos, entre otras cosas nos servirán para bloquear un proceso o un thread que trata de acceder a un recurso crítico que está siendo usado por otro proceso, un ejemplo típico es un baño público, cuando la puerta no está bloqueada, pasas, la bloqueas, haces lo que tengas que hacer allí, y luego desbloqueas la puerta y te vas. Aquí todo funciona parecido, cuando tienes que acceder a un recurso, miras si el semáforo está abierto, y si es así, lo cierras, utilizas ese recurso y cuando terminas lo abres.
Pero claro, podemos crear todos los semáforos que queramos y tenemos total libertad para hacer que los procesos esperen que los semáforos estén abiertos o los abran, por lo que podemos crear multitud de situaciones.

Pero claro, ¿qué puede pasar si tenemos tres procesos (P1, P2 y P3) y se da el caso en el que P1 esté esperando a P2, P2 esté esperando a P3 y P3 esté esperando a P1? Pues nada, estaremos esperando indefinidamente.
El caso típico es el siguiente:

  • Tenemos dos procesos (P1 y P2)
  • Tenemos dos recursos (R1 y R2) de acceso exclusivo (sólo pueden ser accedidas por un proceso cada vez)
  • P1 quiere acceder a R1 por lo tanto cierra su semáforo
  • P2 quiere acceder a R2 por lo tanto cierra su semáforo
  • P1 quiere acceder también a R2 por lo que espera a que su semáforo esté abierto
  • P2 quiere acceder también a R1 por lo que espera a que su semáforo esté abierto

Como P1 está esperando a que P2 libere el semáforo de R2 y P2 está esperando a que P1 libere el semáforo de R1, los dos se van a quedar indefinidamente así.

Si queremos comprobarlo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/mman.h>
#include <semaphore.h>
#include <string.h>

int main()
{
  sem_t *sem1 = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE,
             MAP_SHARED | MAP_ANONYMOUS, -1, 0);
  sem_t *sem2 = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE,
             MAP_SHARED | MAP_ANONYMOUS, -1, 0);

  int child;

  sem_init (sem1, 1, 1);
  sem_init (sem2, 1, 1);

  child = fork();
  if (child==-1)
    exit(1);
  else if (child==0)
    {
      while(1)
    {
      printf ("[%d] Child waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Child passes sem1.\n", getpid());
      printf ("[%d] Child waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Child passes sem2.\n", getpid());
      usleep(100);
      printf ("[%d] Child posts sem2\n", getpid());
      sem_post(sem2);
      printf ("[%d] Child posts sem1\n", getpid());
      sem_post(sem1);
    }
      exit(2);
    }
  else
    {
      while(1)
    {
      printf ("[%d] Main waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Main passes sem2.\n", getpid());
      printf ("[%d] Main waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Main passes sem1.\n", getpid());
      usleep(100);
      printf ("[%d] Main posts sem1\n", getpid());
      sem_post(sem1);
      printf ("[%d] Main posts sem2\n", getpid());
      sem_post(sem2);
    }
    }
  while (wait(NULL)>=0);

  munmap(sem1, sizeof(sem_t));
  munmap(sem2, sizeof(sem_t));

  return 0;
}

Si compilamos (con pthread: gcc -o deadlock deadlock.c -lpthread) veremos algo como esto:

$ ./deadlock
[30643] Main waits for sem2…
[30643] Main passes sem2.
[30643] Main waits for sem1…
[30643] Main passes sem1.
[30644] Child waits for sem1…
[30643] Main posts sem1
[30643] Main posts sem2
[30643] Main waits for sem2…
[30643] Main passes sem2.
[30644] Child passes sem1.
[30643] Main waits for sem1…
[30644] Child waits for sem2…

También es verdad que no siempre es tan rápido, a veces pueden darse muchas iteraciones hasta que se produce el bloqueo, otras veces a la primera iteración se produce, depende de cómo de rápidos sean los procesos, pero tarde o temprano se va a dar. Para más información sobre esto, tenemos la página de Wikipedia.

Para dar algo de teoría, en este ejemplo se han cumplido las 4 condiciones necesarias (tienen que cumplirse todas ellas) de Coffman:

  • Exclusión mutua: Los recursos R1 y R2 son exclusivos, sólo pueden ser accedidos por un proceso cada vez
  • Retención y espera: P1 ha adquirido un recurso R1 y lo retiene mientras espera a que R2 (adquirido por P2) se libere
  • No expropiación: P1, por ejemplo, no puede quitarle R2 a P2 ni al revés.
  • Espera circular: P1 está esperando a P2 y P2 espera a P1.

¿Cómo lo arreglamos?
Aquí podemos buscar tantas soluciones como nos dé la imaginación, pero vamos a proponer algunas más típicas:

Guardar el orden de reserva de recursos

Si siempre vamos a utilizar R1 y R2, los pedimos siempre en el mismo orden:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
...
  child = fork();
  if (child==-1)
    exit(1);
  else if (child==0)
    {
      while(1)
    {
      printf ("[%d] Child waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Child passes sem1.\n", getpid());
      printf ("[%d] Child waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Child passes sem2.\n", getpid());
      usleep(100);
      printf ("[%d] Child posts sem2\n", getpid());
      sem_post(sem2);
      printf ("[%d] Child posts sem1\n", getpid());
      sem_post(sem1);
    }
      exit(2);
    }
  else
    {
      while(1)
    {
      printf ("[%d] Main waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Main passes sem1.\n", getpid());
      printf ("[%d] Main waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Main passes sem2.\n", getpid());
      usleep(100);
      printf ("[%d] Main posts sem2\n", getpid());
      sem_post(sem2);
      printf ("[%d] Main posts sem1\n", getpid());
      sem_post(sem1);
    }
    }
...

No liarla demasiado

Utilizar la mínima cantidad de semáforos posible, si vemos que con sólo uno basta, pues ponemos uno. En este caso sí bastaría con uno, pero habrá casos en los que no se pueda y tendremos que hacer otras cosas…

Si se puede se puede, si no, no

Consiste en utilizar sem_trywait(), si el recurso está ocupado devolverá error, pero no bloqueará. Sólo haciéndolo en uno de los procesos vale, pero claro este proceso entrará menos veces en la sección crítica:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
...
  child = fork();
  if (child==-1)
    exit(1);
  else if (child==0)
    {
      while(1)
    {
      printf ("[%d] Child waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Child passes sem1.\n", getpid());
      printf ("[%d] Child waits for sem2...\n", getpid());
      try = sem_trywait(sem2);
      if (try==0)
        {
          printf ("[%d] Child passes sem2.\n", getpid());
          usleep(100);
          printf ("[%d] Child posts sem2\n", getpid());
          sem_post(sem2);
        }
      else
        printf ("[%d] sem2 busy\n", getpid());
      printf ("[%d] Child posts sem1\n", getpid());
      sem_post(sem1);
    }
      exit(2);
    }
  else
    {
      while(1)
    {
      printf ("[%d] Main waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Main passes sem2.\n", getpid());
      printf ("[%d] Main waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Main passes sem1.\n", getpid());
      usleep(100);
      printf ("[%d] Main posts sem1\n", getpid());
      sem_post(sem1);
      printf ("[%d] Main posts sem2\n", getpid());
      sem_post(sem2);
    }
    }
...

Timeouts

De la misma forma que probamos si estaba disponible el recurso o no, ahora probamos con un timeout, hacemos que el proceso sea capaz de esperar un tiempo a ver si el recurso se libera, aunque pasado ese tiempo dejará de esperar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
  child = fork();
  if (child==-1)
    exit(1);
  else if (child==0)
    {
      while(1)
    {
      printf ("[%d] Child waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Child passes sem1.\n", getpid());
      printf ("[%d] Child waits for sem2...\n", getpid());
      timeout.tv_sec=0;
      timeout.tv_nsec=100000;
      try = sem_timedwait(sem2, &timeout);
      if (try==0)
        {
          printf ("[%d] Child passes sem2.\n", getpid());
          usleep(100);
          printf ("[%d] Child posts sem2\n", getpid());
          sem_post(sem2);
        }
      else
        printf ("[%d] sem2 busy\n", getpid());
      printf ("[%d] Child posts sem1\n", getpid());
      sem_post(sem1);
    }
      exit(2);
    }
  else
    {
      while(1)
    {
      printf ("[%d] Main waits for sem2...\n", getpid());
      sem_wait(sem2);
      printf ("[%d] Main passes sem2.\n", getpid());
      printf ("[%d] Main waits for sem1...\n", getpid());
      sem_wait(sem1);
      printf ("[%d] Main passes sem1.\n", getpid());
      usleep(100);
      printf ("[%d] Main posts sem1\n", getpid());
      sem_post(sem1);
      printf ("[%d] Main posts sem2\n", getpid());
      sem_post(sem2);
    }
    }

Aquí con un struct timespect timeout donde ponemos el tiempo en nanosegundos (variable tv_nsec) creamos una espera de un tiempo máximo para el recurso reservado.

Otros algoritmos

Para solucionar esto, dependiendo de los casos tenemos otros algoritmos, que espero dedicar posts próximamente.
Foto: Moosealope (Flickr) CC-by

También podría interesarte....

Posted in :  C/C++ , Concurrencia
Tags :  , , , , ,

URL for this post : https://poesiabinaria.net/2014/08/deadlock-bloqueo-mutuo-abrazo-mortal-o-como-colgar-un-proceso-con-esperas-infinitas-%e2%98%a0-%e2%98%a0-%e2%98%a0/

There are 6 comments left Ir a comentario

  1. Gustavo /
    Usando Google Chrome Google Chrome 36.0.1985.125 en Windows Windows 7

    Excelente post… muy practico 😀 salu2

    Reply
    1. Gaspar Fernández / Post Author
      Usando Mozilla Firefox Mozilla Firefox 30.0 en Linux Linux

      Gracias Gustavo !

      Reply

  2. Pingback: BlogESfera.com /

  3. CiVault /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    More traffic lights are appearing at road intersections and crossings. The various hues of lights indicate what drivers should do. Every time I ride my bike, I notice it.
    Local SEO Citations

    Reply
  4. Fool Me Once Maya Stern Grey Trench Coat /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post.

    Reply
  5. Joshua Jasmine /
    Usando Google Chrome Google Chrome 122.0.0.0 en Windows Windows NT

    Superb post. I am very much excited to read this kind escort girls Brisbane of content. Thanks.

    Reply

Leave a Reply