Archive

Posts Tagged ‘section’

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