Archive

Posts Tagged ‘mutex’

Deadlock or how to hang a process waiting for a resource indefinitely ☠☠☠

April 4, 2014 No comments

It’s a typical exercise, but we always see it theoretically, let’s bring it to practice. We’re developing with semaphores. As we can see here and here, semaphores, among other things will be used to block a process or thread which is trying to access an exclusive resource which is already being used by other process. A typical example is when you go to a public toilet: when the door isn’t locked, you go in and lock the door, when you finish whatever you were doing there, you unlock the door and exit. The same way, when a process tries to use a resource, if the semaphore is open, closes it, use the resource and reopens the semaphore when finish.
But, here we can create as many semaphores as we want, and we are free to do whatever we want with them, so we can create tons of situations.

But, what if we have three processes (P1, P2 and P3), and P1 is waiting for P2, P2 is waiting for P3 and P3 is waiting for P1? We’ll be waiting forever.

What I’m about to code is:

  • We have two processes (P1 and P2)
  • We have two resources (R1 and R2) which are exclusive (only one process can access each moment)
  • P1 wants to access R1, so closes its semaphore
  • P2 wants to access R2, so closes its semaphore
  • P1 wants to access also R2, so waits for its semaphore to be open
  • P2 wants to access also R1, so waits for its semaphore to be open

As P1 is waiting P2 to open R2 semaphore and P2 is waiting P1 to open R1 semaphore, both processes will be waiting indefinitely.

Check this:

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;
}

Compile with pthread (gcc -o deadlock deadlock.c -lpthread) and see something like this:

$ ./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…

It isn’t always so fast, sometimes we can do lots of iterations before the deadlock, and some other times, it will block in the first iteration, let’s see Wikipedia for more information.

Some theory, in this example, the 4 necessary Coffman conditions have been met:

  • Mutual exclusion: R1 and R2 are exclusive, they only can be acceded by a process at a time.
  • Hold and Wait: P1 acquired R1 and hold it while waits for R2 (acquired by P2)
  • No preemption: P1, for example, can’t steal R2 to P2
  • Circular wait: P1 is waiting P2, P2 is waiting P1

How can we fix that?
We have as many solutions as our imagination can, but let’s see some common ones:

Wait for resources in order

If we are always requesting R1 and R2, let’s do in the same order:

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);
    }
    }
...

Don’t make a mess

Use the least amount of semaphores, if we can do the same using one semaphore, just use one. We can do it in some cases.

Use the resource if available, skip if not

We can use sem_trywait(), if the resource is busy, it’ll return an error without blocking the application. We only have to do it in one process, but this process will enter fewer times in the critic section:

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

As the last example, we can wait for a semaphore just a few nanoseconds, if the semaphore opens in this time interval, we will go in, but if not, it’ll return an error, so we can skip:

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);
    }
    }

We can set the timeout with a struct timespec where we can set the time in nanoseconds (variable tv_nsec).

Other algorithms

There are other algorithms which can help, I hope I can dedicate another post to them.
Foto: Moosealope (Flickr) CC-by

Creating a mutex with semaphores between child processes in C [fork()]

March 19, 2014 No comments

We’ve been practicing sharing variables between child processes, but when there are some processes trying to access a shared resource, we need a mutex to make it safer. This time to implement the mutex we’ll use semaphores. This semaphores must be also shared variables to work properly.

First, think about semaphores as variables which can be 0 or 1. So if the semaphore is 1, it’s open and we will close (0 value) it after we pass; if it is 0, we’ll wait until it goes 1 (it’s not like a while (semaphore==0); because the operating system will deactivate the process and reactivate it when the semaphore is open and we can use our system resources for anything else).
But, let’s go further, semaphore’s value can be whatever, not just 0 or 1, but if it’s positive, and we want to pass, we will decrement it and it won’t block our process, but if it’s zero or less, our process will block. So we can say a mutex is a semaphore with 1 and 0 values, used to protect a resource.

To use semaphores we must have in mind three basic functions (there are some more):

  • sem_init(semaphore, pshared, value): Initialize the semaphore with a known value, pshared can be 0 if we want it to be shared between threads of the process, or another value if we want it to be shared between processes. In this case we will put a 1 here.
  • sem_post(semaphore): Increment the semaphore, it’s what we do to free the resource
  • sem_wait(semaphore): Decrement the semaphore, if its value is less than zero, blocks the process until we have a value greater or equal than zero. We’ll use this to check if the resource is locked.

In the next example, we’ll increment a number, but to make it a bit more difficult, it will be stored in a string, each increment must be done by a different child process. The final value of x must be 20. On the other hand, I’ve inserted some random waits to simulate a heavy process and provoke a race condition.

We can change SEMAPHORES constant value from 1 to 0 to see how this program behaves in each case:

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
66
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/mman.h>
#include <semaphore.h>
#include <string.h>

#define SEMAPHORES 1

int main()
{
  char *x = mmap(NULL, sizeof(char)*10, PROT_READ | PROT_WRITE,
               MAP_SHARED | MAP_ANONYMOUS, -1, 0);
  strcpy(x, "0");

  int i;
  int child;
  sem_t *semaphore = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE,
             MAP_SHARED | MAP_ANONYMOUS, -1, 0);
  int temp;
  sem_init (semaphore, 1, 1);
  for (i=0; i<10; ++i)
    {
      child = fork();
      if (child==0)
    {
      usleep(rand()%20000);

      if (SEMAPHORES)
        sem_wait(semaphore);
      printf("[%d] Trying to access the resource\n", getpid());
      temp=atoi(x);
      printf("[%d] Using the resource\n", getpid());
      temp++;
      sprintf(x, "%d", temp);

      if (SEMAPHORES)
        sem_post(semaphore);
      printf("[%d] Just used the resource\n", getpid());
      usleep(rand()%20000);

      if (SEMAPHORES)
        sem_wait(semaphore);
      printf("[%d] Trying to access the resource\n", getpid());
      temp=atoi(x);
      printf("[%d] Using the resource\n", getpid());
      temp++;
      sprintf(x, "%d", temp);

      if (SEMAPHORES)
        sem_post(semaphore);
      printf("[%d] Just used the resource\n", getpid());
      printf("[%d] EXITING\n", getpid());
      exit(1);
    }
    }

   while (wait(NULL)>=0);

  printf("x is: %s\n", x);
  munmap(x, sizeof(int));
  munmap(semaphore, sizeof(sem_t));

  return 0;
}

Each time a process wants to enter our critic section, it will be written on screen by its process Id, so we can see when a process is accessing the resource, and we can detect if two or more processes are accessing simultaneously (and we don’t want it). Remember, then final x value must be 20 and without semaphores we may or may have not this value, it isn’t under our control.

Note: To compile the example, include pthread:

$ gcc -o example example.c -lpthread

Photo: Paul Albertella (Flickr) CC-by

Concurrency, when several threads fight for the access to a resource [ example in C ]

January 30, 2014 No comments

If we’re creating a multi-thread application and we’re also sharing information between the main thread and the secondary thread, or between threads, you must have in mind the type of access to that information.
For example, if we will only allow one thread to write on a variable and the other will just read we won’t have any problem in most cases, but if any thread can write a value at any time, we must be careful. If some threads are willing to write a variable at almost the same time, only the last value written will remain.

Another example, we have a film collection software, and at the moment we have 50 films stored. Another thread is going to synchronize an Internet server, but while the synchronization is running, we add 3 films more. The thread synchronizing may see 50 films, but the films sent can be a mix of the old and new films, so the server will think we’ve removed some films and we will have a problem.
In this case, we must protect the access to the critic section (our film list), so when we are adding data, the other thread can’t sync, and when the other thread is syncing, we must wait before adding anything. We will use for that mutual exclusion or mutex.

To try to make a visible example, we’re incrementing numbers, but we will insert a CPU eater task between the read of the value and the writing of the new value. The CPU-eater task can finish in a variable time interval, so one threads will finish this task before others. The desired result is the number incrementing to 10, but the real one differs a bit:

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
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

struct thread_vars_t
{
  int number;
};

int numberExists(int arr[], int current)
{
  int i;

  for (i=0; i<current; ++i)
    {
      if (arr[current]==arr[i])
    return 1;
    }

  return 0;
}

void numberSearch()
{
  /* A time taking task */
  int numbers[100];
  int i;

  for (i=0; i<100; ++i)
    {
      numbers[i] = rand()%101;
      while (numberExists(numbers, i))
    numbers[i] = rand()%101;
    }
}


void *newtask(void *_number)
{
  struct thread_vars_t *vars = _number;

  int number = vars->number;
  numberSearch();
  vars->number = number+1;

  printf ("THREAD: number = %d\n", vars->number);

  pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;
   int i;
   struct thread_vars_t *vars = malloc (sizeof(struct thread_vars_t));

   vars->number = 0;

   printf ("Main process just started.\n");
   for (i=0; i<10; ++i)
     {
       rc = pthread_create(&thread, NULL, newtask, vars);
       if (rc)
     {
       printf("ERROR in pthread_create(): %d\n", rc);
       exit(-1);
     }
     }

   printf ("Main process about to finish.\n");
   /* Last thing that main() should do */
   pthread_exit(NULL);
}

Your result can be more or less like that:

$ ./sharedvar
Main process just started.
THREAD : number = 1
THREAD : number = 1
THREAD : number = 2
THREAD : number = 2
THREAD : number = 3
Main process about to finish.
THREAD : number = 4
THREAD : number = 4
THREAD : number = 3
THREAD : number = 4
THREAD : number = 4

What has happened? Some threads read the variable when it was 0 (two occasions), so they both incremented to 1, others read the value when it was 1 (another two ones), and incremented to 2, in other cases, the variable was 2 and was incremented to 3…
So, several threads read the same value and when writing the new value, we didn’t have in mind the value could have changed by another thread while we were working. That is the race condition.

How can we fix that? The solution is coding structures that block access to the resource when it’s being used. For example, it some other thread has read the value of the variable, no other can, until a new value is written.
Do we lose performance? Yes, a bit, because we are waiting for other tasks instead of working together. But we avoid undesirable situations like the example before. But the threads may do also some other things outside the critical section, and this work can be done simultaneously. We will only block the critical section (when working on a number), when we will block other threads with a mutex.

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

struct thread_vars_t
{
  int number;
  pthread_mutex_t mutex;
};

int numberExists(int arr[], int current)
{
  int i;

  for (i=0; i<current; ++i)
    {
      if (arr[current]==arr[i])
    return 1;
    }

  return 0;
}

void numberSearch()
{
  /* A time taking task */
  int numbers[100];
  int i;

  for (i=0; i<100; ++i)
    {
      numbers[i] = rand()%101;
      while (numberExists(numbers, i))
    numbers[i] = rand()%101;
    }
}


void *newtask(void *_number)
{
  struct thread_vars_t *vars = _number;

  /* BLOCK */
  pthread_mutex_lock(&vars->mutex);
  /* BLOCK */

  int number = vars->number;
  numberSearch();
  vars->number = number+1;

  /* UNBLOCK */
  pthread_mutex_unlock(&vars->mutex);
  /* UNBLOCK */

  printf ("THREAD: number = %d\n", vars->number);

  pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;
   int i;
   struct thread_vars_t *vars = malloc (sizeof(struct thread_vars_t));

   pthread_mutex_init(&vars->mutex, NULL);
   vars->number = 0;

   printf ("Main process just started.\n");
   for (i=0; i<10; ++i)
     {
       rc = pthread_create(&thread, NULL, newtask, vars);
       if (rc)
     {
       printf("ERROR in pthread_create(): %d\n", rc);
       exit(-1);
     }
     }

   printf ("Main process about to finish.\n");
   /* Last thing that main() should do */
   pthread_exit(NULL);
}

And the result will be like this:

$ ./simplemutex
Main process just started.
THREAD: number = 1
Main process about to finish.
THREAD: number = 2
THREAD: number = 3
THREAD: number = 4
THREAD: number = 5
THREAD: number = 6
THREAD: number = 7
THREAD: number = 8
THREAD: number = 9
THREAD: number = 10

Photo: Daryl L. Hunter (Flickr) CC-by

Top