Archive

Archive for the ‘C’ Category

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

Shared variables between child processes in C [fork()]

March 5, 2014 No comments

Another way of facing concurrency in the wonderful world of doing several task at the same time is using child processes with fork(). The main difference between fork and threads is that forked process are full process, they have their own memory for code, for data and stack, while threads share code and data, and have their own stack.

But, what about sharing variables in forked processes? If we try to make it as simpler as in thread examples, it’s not going to work, because as they are different processes, they are using different memory zones for their data. For example:

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
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main()
{
  int child;
  int *number = malloc(sizeof(int));
  int i;

  *number = 10;

  child = fork();

  if (child==-1)
    {
      exit(1);
    }
  else if (child==0)
    {
      for (i=0; i<10; ++i)
    {
      usleep(100);
      printf ("CHILD -- Number: %d\n", *number);
      *number=i;
    }
      exit(0);
    }
  else
    {
      for (i=20; i<30; ++i)
    {
      usleep(100);
      printf ("MAIN -- Number: %d\n", *number);
      *number=i;
    }
    }
  wait(NULL);
  free(number);
}

In our ideal world, the MAIN process can see the values written by CHILD and vice versa, but the value the MAIN process can access is completely different than the value the CHILD can access, even using malloc before calling fork(). fork() copies the values of all variables before fork(), but the physical memory address is different.

To do that we have to work with shared memory, have to use mmap instead of malloc:

1
2
  int *number = mmap(NULL, sizeof(int), PROT_READ | PROT_WRITE,
               MAP_SHARED | MAP_ANONYMOUS, -1, 0);

And, like malloc() uses free() to free memory, with mmap we will use:

1
mmunmap(number, sizeof(int));

And, of course, when using threads we can have a race condition, we must use mutex here too to solve the problem.
Photo: Rudolf Vicek (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

Concurrency, POSIX threads and shared variables in C

January 14, 2014 No comments

A few days ago, we talked about building our first multi-thread programs using POSIX threads. But soon a need arises: share data between the main thread and the recently launched thread, at least to indicate what we want it to do.
So we can use the last argument of pthread_create(), this is a void pointer we can use for whatever we want and pass the variable type we want. For example an integer:

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *newtask(void *_number)
{
  int number = *(int*)_number;
  printf("The number I was asked for: %d\n", number);
  pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;
   int i;
   int number = 99;

   printf ("Main process just started.\n");
   rc = pthread_create(&thread, NULL, newtask, &number);
   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);
}

Remember to compile using pthread:

$ gcc -o simplepass simplepass.c -lpthread

This way, the thread can read the value we’ve passed him, as we can see if we run this little program. Just after starting newtask() we extract the number from the void pointer to an integer variable. But working a bit on this code we can realize this variable can be bi-directional, in other words, we can write a value from the secondary thread, and the main thread can read it. (Instead of doing this, we can use global variables, but I don’t like it much):

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *newtask(void *_number)
{
  int *number = _number;
  printf("The number I was asked for: %d\n", *number);
  *number = 10;
  pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;
   int i;
   int number = 99;

   printf ("Main process just started.\n");
   rc = pthread_create(&thread, NULL, newtask, &number);
   if (rc)
     {
       printf("ERROR in pthread_create(): %d\n", rc);
       exit(-1);
     }

   usleep(100000);

   printf (" Before exiting. Number = %d\n", number);

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

Now, if we want to pass multiple arguments to the secondary thread, we can create a struct which stores all variables we want to use there:

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

struct thread_vars_t
{
  int number;
  char string[50];
};

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

  printf("The number I was asked for: %d\n", vars->number);
  vars->number = 10;
  strcpy(vars->string, "Hello world from thread");
  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 = 99;

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

   usleep(100000);

   printf (" Before exiting. Number = %d\n", vars->number);
   printf (" Before exiting. String = %s\n", vars->string);

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

In older and slower computers, we may have to cary the value passed to usleep(), I’m just simulating a wait, it could be the time taken by additional computation. But using a sleep could be a problem, depending on the computer capabilities this value must change, or we could give a high value to make it compatible with more computers, but it could be a waste of time for modern computers. We can solve it many ways, but this first one will be a demo of what you shouldn’t do making an active wait:

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

struct thread_vars_t
{
  int ready;
  int number;
  char string[50];
};

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

  printf("The number I was asked for: %d\n", vars->number);
  vars->number = 10;
  strcpy(vars->string, "Hello world from thread");
  vars->ready = 1;
  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->ready = 0;
   vars->number = 99;

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

   //   usleep(100000);
   while (!vars->ready);
   printf (" Before exiting. Number = %d\n", vars->number);
   printf (" Before exiting. String = %s\n", vars->string);

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

In this case, we have a new variable (vars->ready), when it’s 1 it means the values are set by the secondary thread, so the main one can read them. The main thread, to wait for vars->ready is asking all the time for this value while it’s 0:

1
while (!vars->ready);

But it has a great disadvantage: the process is eating CPU while the condition is not met. We can see it clearer writing sleep(20) just before the secondary thread set ready to 1, and use a task manager to see how CPU use is going, our process will use a big percentage of CPU for nothing, just waiting. If we think about it and the secondary thread is doing any type of complex calculation, the main thread will be stealing CPU time obstructing the secondary one, making it slower, so we have to use another type of solution, like semaphores, signals, mutex, etc. But I’ll talk about them in another post.
Photo: OakleyOriginals (Flickr) CC-by

Dinamically allocate memory for a bi-dimensional array in C

January 7, 2014 No comments

One of the biggest faults of an array is that we have to define it’s size in coding time. Sometimes it’s the easiest thing to do and it’s ok, we may waste some bytes (As in a little string when we create a 100 bytes array); sometimes we choose the right size (for example when creating an array with the names of the months). But many times we have no idea what the size it must have, if it is very small we probably will fail short and if it is very large, we will wast a lot of memory.

But one of the tools C has is the dinamic memory allocation (malloc function and derivates), but it can allocate memory for an structure, or an unidimensional array, if we want to allocate memory for a two-dimensional, three-dimensional array or so, we must allocate memory for each of the arrays composing the multi-dimensional array,

To have a dynamic array, we must have a double pointer, so it can be declared as:

1
int **myArray;

To allocate memory for that variable, first we must allocate all rows, and then, inside each row, we must allocate the columns. For example for a 3×3 array, we must:

  • Allocate 3 rows
  • Allocate 3 columns for 1st row
  • Allocate 3 columns for 2nd row
  • Allocate 3 columns for 3rd row

The next example is using calloc() function to allocate memory (we can do it with malloc with no difficulties:

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
#include <stdlib.h>
#include <stdio.h>

void** calloc2d (int rows, int cols, int elemSize)
{
  void **variable;
  int i;

  variable=(void**)calloc(rows, sizeof(void*));
 
  for (i=0; i<rows; i++)
    {
      variable[i]=calloc(cols, elemSize);
    }
  return variable;
}

void free2d (void **var, int rows)
{
  int i;
  for (i=0; i<rows; i++)
    free(var[i]);

  free(var);
}

void randomValues(int **v, int rows, int cols)
{
  int i,j;
  for (i=0; i<rows; i++)
    for (j=0; j<cols; j++)
      v[i][j]=rand();
}

int main(int argc, char *argv[])
{
  int rows=10000;
  int cols=20000;
  getchar();
  int ** v=(int**)calloc2d(rows, cols, sizeof(int));

  randomValues(v, rows, cols);
  getchar();

  free2d((void**)v, rows);
  getchar();
  return EXIT_SUCCESS;
}

The first function (calloc2d()) will allocate dinamically bi-dimensional arrays indicating rows and columns, free2d() will free memory allocated only indicating rows.
The function randomValues() assign random integer values to the array, to use the allocated memory, so the memory will be really used.

The program does three pauses, one before anything (press enter, to continue), another one when the memory is allocated, and the other one when everything in freed. We can use a memory analysis program, or even top to see what’s going on.

Be careful if your system is low on memory, because 10000 rows * 20000 columns * 4 (sizeof(int)) = 800000000 = 8*10^8 or 800Mb

Photo cibomahto (Flickr) CC-by

Starting with concurrency and a “Hello world” using pthreads

December 31, 2013 No comments


Nowadays is very common to see dual-core or quad-core CPUs, but there are still systems with one single core.
In this post, I want to about the very basis of concurrency, a brief introduction to this world, so some descriptions will be so so simple, but real world is a little bit more complex.

In multi-core or multi-CPU systems, the operating system (OS) distributes tasks within our CPUs, and we can run several tasks at the same time, but we have been enjoying multitasking for decades, long before multi-core appeared, so, how is it possible? Let’s think about single-core systems, they can only perform one task, but the operating system distributes the CPU control along all tasks very fast so it makes us think all of them are running at the same time. So single-core CPUs usually have one execution thread, dual-core system, will have two execution threads, so they can perform two tasks at the same time. But don’t worry about how it is distributed, because the operating system does it for you.

We’ve seen the OS is smart enough to take advantage of our CPUs or CPU cores, so does it have any sense to make our application use several cores, or make our application run two things at the same time?
Of course it does, let’s see some examples:

  • Imagine a GUI program performing a heavy task. While this task is running, we may want to give the user some little control to cancel the process, for example, or to carry on using our software. We can run the heavy task in one thread and the GUI in another one.
  • A server which attends several clients simultaneously.
  • A program which does intense calculations, if we have dual-core, it can be twice faster

In the last case, we must think about something a little bit. Distributing tasks in time takes some time for the OS, so we must make sure the time we save (separating the process in several threads) is bigger than the time the OS wastes managing the new tasks and sometimes we must put all the results of all individual threads together (and it takes time too).
We may think it will be valid only for multi-core processors but the time taken by our tasks may vary depending on what we are doing, for example, calculations take all CPU Time, but if we access external devices (keyboard, screen, hard disk, USB, etc), even access a file, it makes our process wait for the data and while we are waiting, the CPU is wasting time, so we can take this time to perform calculations for some other process, and it is valid even on single-core CPUs. Sometimes running a tasks in two threads can squeeze our CPU better than one thread using CPU while the other thread is just waiting for data an vice-versa.

Ok, before playing a little bit with it we must know there are some ways to do that. We can create several processes, it’s like running some programs at the same time, and the other way is creating threads. The difference is that processes must store in RAM memory, data and stack among other things, and some threads can share code and data, so only stack and a little information about execution status belongs to each thread exclusively. We can say process initiates also a single execution thread.

Let’s code a bit, we will use pthreads (POSIX threads):

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *newtask(void *null)
{
   printf("Hello world! I'm a new thread\n");
   sleep(1);
   printf("Goodbye world! I'm a thread about to die\n");
   pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;

   printf ("Main process just started.\n");
   rc = pthread_create(&thread, NULL, newtask, NULL);
   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);
}

This example can be compiled including pthread library, this way:

$ gcc -o onethread onethread.c -lpthread

We are just executing a program that creates another thread that performs a task, this task is writing a couple of messages on screen and wait a bit between them. We can see a result like this:

Main process just started.
Main process about to finish.
Hello world! I’m a new thread
[ wait for a second ]
Goodbye world! I’m a thread about to die

The first two messages belongs to the main thread, one when it stats and the other one when it ends, but before ending we are invoking the other thread that writes the other two messages. As we can see, each thread is executed independently, but to see it a bit more clearer, let’s see the next code:

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
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *newtask(void *null)
{
   printf("Hello world! I'm a new thread\n");
   int i;

   for (i=0; i<10;++i)
     {
       printf (" THREAD: %d\n", i);
       usleep(60);
     }
   printf("Goodbye world! I'm a thread about to die\n");
   pthread_exit(NULL);
}

int main (int argc, char *argv[])
{
   pthread_t thread;
   int rc;
   int i;

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

   for (i=0; i<10;++i)
     {
       usleep(100);
       printf (" MAIN: %d\n", i);
     }
   printf ("Main process about to finish.\n");
   /* Last thing that main() should do */
   pthread_exit(NULL);
}

What we’ve done is that the main thread (MAIN) and secondary thread (THREAD) will write on screen several messages inside a for loop. They will be counting from 0 to 9, but waiting a little bit between each writing (instead of doing heavier time eater tasks we simulate them with sleeps).

We can see a execution result like this:

Main process just started.
Hello world! I’m a new thread
THREAD: 0
THREAD: 1
MAIN: 0
THREAD: 2
MAIN: 1
THREAD: 3
THREAD: 4
MAIN: 2
THREAD: 5
MAIN: 3
THREAD: 6
MAIN: 4
THREAD: 7
THREAD: 8
MAIN: 5
THREAD: 9
MAIN: 6
Goodbye world! I’m a thread about to die
MAIN: 7
MAIN: 8
MAIN: 9
Main process about to finish.

Messages are written alternatively both MAIN and THREAD, like interlaced, now we can see they are both running concurrently, at the same time. We can start making multi-thread software in C.

Photo: Toastyken (Flickr) CC-by

Get the HOME directory in C

October 23, 2013 No comments

In our programs, it’s usual to know where is the user home directory, to read/store configuration files, to search for something, or to know if the program is installed globally or locally.

There is a short function to get it:

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
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <pwd.h>

char *getHomeDir()
{
  static char *home = NULL;
 
  if (!home)
    {
      home = getenv("HOME") ;
    }
  if (!home)
    {
      struct passwd *pw = getpwuid(getuid());
      if (pw)
          home = pw->pw_dir ;
    }
  return home;
}

int main(int argc, char *argv[])
{
  printf ("HOME: %s\n", getHomeDir());

  return EXIT_SUCCESS;
}

If we look at getHomeDir() function, the directory we’re looking for is stored in a static variable, as we are not freeing this variable, we will get the value of this variable when we ask again (the user isn’t changing his home). We will ask the system just for the first time.

In the other hand, we have two ways of getting the PATH, the first is with the HOME environment variable, most of the times it will be defined and we can get it, but if it’s not there, we can get this information from /etc/passwd. There is much more information that what we want and we can have a look at the manual of getpwuid() to know what we can get (the user password is not included, muahaha, it isn’t stored there anymore, and if it is in an old or embedded system, you will probably see a hash).

Foto: Neetesh Gupta (Flickr) CC-by.

stermp.h, trying to port conio.h to Linux

October 22, 2013 No comments

This time I want to rescue an old project. I started it long ago. These days I’ve been reading some source codes in facebook using conio.h so I hope this could be interesting for anyone.

Of course there are some libraries that allow us to to write strings in colors and get/set position on screen and keys without echoing and pressing Enter, or we can do it without them, using ANSI codes directly but we would have to do a lot of changes in the source code.

I tried to keep the name of the functions the same, we use:

  • clrscr() : To clean screen
  • textbackground(color) : To change background color
  • textcolor(color) : To change text color
  • gotoxy(x,y) : Go to specific position
  • wherex() : To get X position
  • wherey() : To get Y position
  • getch() : To get a key press without ENTER
  • getche() : Like getch but echoing character on screen
  • kbhit() : To know if a key has been pressed without stopping execution. Returns true or false

We also have some additional stuff like:

  • wherexy() : Returns X,Y position in a struct
  • kbhit2() : Gets a key code if pressed without stopping execution
  • kbhit_pre() : Prepares to do lots of kbhits() to increase performance
  • restore_terminal_color() : Restores terminal color
  • screenheight() : Gets screen height.
  • screenwidth() : Gets screen width.

I tried also to keep color names the same. Let’s see an example:

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
#include <stdio.h>
#include <time.h>
#include "stermp.h"

void update_time()
{
  struct tm *tm;
  time_t _time;
  char text[50];
  textcolor(YELLOW);
  _time=time(NULL);
  tm = localtime(&_time);
  strftime(text,50,"%d/%m/%Y %H:%M:%S", tm);
  gotoxy(1,1);
  printf("%s    ", text);
}

int main()
{
  int x,y;
  int width, height;
  int key;
  term_init();

  width = screenwidth();
  height = screenheight();
  /* Rellenamos de verde la pantalla */
  textbackground(GREEN);
  clrscr();

  textbackground(BLUE);
  /* Rellenamos de azul la primera fila */
  for (x=0; x<width; x++)
    printf(" ");

  gotoxy(1,height);
  /* Rellenamos de azul la última fila */
  for (x=0; x<width; x++)
    printf(" ");

  gotoxy(2,2);
  while ((key=kbhit2())==0)
      update_time();

  printf("You have pressed: %d\n", key);

  term_defaults();
 
}

We can see I’m calling term_init() and term_defaults() but they are just to restore terminal after the execution ends.
You can download the source code on github. Just include stermp.h in your code and include stermp.h and stermp.c in your project.

stermp – conio.h compatible terminal features in Linux (for small projects)

October 15, 2013 No comments

When making CLI programs, sometimes we want to add some colors, or get the position of the cursor, terminal dimension or something like that. If you have been programming for years, you probably would remember conio.h, it was a C library used in the 80′s ? or 90′s to make user friendly terminal environments. And it is still being taught in some courses and even universities (omg). And I decided to create this some years ago, because conio.h was only compatible with MSDOS and Windows.

There are some Linux libraries to do so, or cross-platform, what is even better. But they are not as easy to use as conio.h was. And this was my intention, provide easy of use colors and position for terminal programs.

To use stermp, you just have to add stermp.h / stermp.c files to your project, and compile it, it will add a few (~10Kb) to your project. But it offers you these capabilities:

  • Terminal positioning (go to specific position, and get current terminal position.
  • Gets terminal dimensions (in MSDOS/Win) this is limited to some fixed resolutions, but in *nixes you can have lot of terminal sizes.
  • Text coloring
  • Background coloring
  • Text effects (underline, blink!! (ohh nooo), please don’t abuse)
  • Get keys without waiting for ENTER key
  • Detect whether if a key is pressed or not

To download it, just get stermp.tar (4.7Kb), or go to my github.

Categories: C, Linux Tags:
Top