Archive

Posts Tagged ‘memory’

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

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

Top