Reentrant and thread safe functions

December 31st, 2009 by Kevin | 1 Comment | Filed in programming

Threads

Process with two concurrent threads

©en:User:Cburnett

A thread is a sequence of execution in a process. Multiple threads can run concurrently in a process as shown in the figure above. The feature of concurrently executing threads of a process is that they share resources such as memory.

An example of a project using threads that I have worked on is playing an MPEG4 stream. The stream contains both audio and video tracks. We should be able to play them concurrently with the timing information provided inside the tracks. So we create a thread to play the audio, another thread to play the video and a third thread to maintain synchronization between the two.

Since the threads share the same address space, we can share the synchronization information between them. The only issue is when the address space is accessed concurrently and the threads are writing on it at the same time or with one read and the other write. To solve this problem we have to make the functions thread safe.

The way to make functions thread safe is to use one of the following mechanisms:

1) Using local variables: By ensuring that we just use local variables we can make the function thread safe. This is because even though the global address space is shared between the threads, each thread is assigned it’s own stack with separate memory for it’s local variables.

2) Using mutual exclusion: Mutex as they are popularly know are another way of making a function thread safe. This is done by ensuring that the shared resources of the function are accessed by only one thread at a time i.e the access to these critical shared resources are mutually exclusive among the threads.

pthread_mutex_t VideoStatusMutex = PTHREAD_MUTEX_INITIALIZER;

static int GetVideoStatus()
{
  int tmp = 0;
  pthread_mutex_lock(&VideoStatusMutex);
  tmp = g_VideoStatus;
  pthread_mutex_unlock(&VideoStatusMutex);
  return tmp;
}

static int SetVideoStatus(int VideoStatus)
{
  pthread_mutex_lock(&VideoStatusMutex);
  g_VideoStatus = VideoStatus;
  pthread_mutex_unlock(&VideoStatusMutex);
  return 0;
}

Whenever we need to use a share resource like g_VideoStatus, we use the mutex functions SetVideoStatus() and GetVideoStatus() instead.

3) Reentrant functions: To make a function a list of requirements is below (from Wikipedia):

  • Must hold no static (or global) non-constant data.
  • Must not return the address to static (or global) non-constant data.
  • Must work only on the data provided to it by the caller.
  • Must not rely on locks to singleton resources.
  • Must not modify its own code. (unless executing in its own unique thread storage)
  • Must not call non-reentrant computer programs or routines.

All reentrant functions are thread safe but not all thread safe functions are reentrant. An example of a reentrant function is our recursive factorial example which satisfies all the above conditions.

int fact(int n)
{
   if(n == 0 || n == 1)
   {
      return 1;
   }else{
      return n * fact(n-1);
   }
}
 

Related Posts:

Tags: ,

Recursion

December 22nd, 2009 by Kevin | 2 Comments | Filed in C Programming, programming

Recursion is a technique in computer programming which allows us to compute the solution of a problem by defining the problem into smaller and smaller instances of itself. The concept of recursion is quite confusing to the new programmer. Let us try to understand this by the typical example of finding the factorial of a number.

A factorial of a number can be found by applying the following equation:

n! = n(n-1)(n-2)...1
eg: 4! = 4 x 3 x 2 x 1 = 24

A recursive C program to calculate the factorial of a number is shown below:

int fact(int n)
{
   if(n < 0)
   {
      return 0;
   }
   else if(n == 0 || n == 1)
   {
      return 1;
   }
   else
   {
      return n * fact(n - 1);    /* recursively calling fact() with a smaller instance */
   }
}

This program works as following:

fact(4) = 4 * fact(3)                                             /* winding phase */
                  fact(3) = 3 * fact(2)
                                fact(2) = 2 * fact(1)
                                              fact(1) = 1         /* terminating condition */
                                fact(2) = (2)*(1)                 /* unwinding phase */
                  fact(3) = (3)*(2)
fact(4) = (4)*(6)
24                                                                /* recursion complete */

As can be seen, during the winding phase, the function fact() is called recursively and each functions gets a stack frame on the stack. Every recursive function should have a terminating condition else it will continue recursively till the stack runs out of space and we get a stack overflow. After the terminating condition is the unwinding phase where the results of each recursive call are computed by the results from the previous recursive call and finally we get the solution.

It should be noted that a problem can be solved without using recursion as well but applying recursion makes the solution more simple and elegant in most cases. However, the disadvantage of recursion is the increased cost of maintaining the stack frame for each recursive function call. In the above example, we can see that for each recursive call during the winding phase, the function frame has to be maintained in the stack so that during the unwinding phase, we can use the values to compute the solution for that instance and pass it on further down.

A solution to this problem is to reduced the number of stack frames used by using tail recursion. A tail recursive function is one which is the last executable statement of a recursive function and whose return value will not be used in an expression. This is better explained by writing the above program to calculate a factorial using a tail recursive function.

int facttail(int n, int a)
{
   if(n < 0)
   {
      return 0;
   }
   else if(n == 0)
   {
      return 1;
   }
   else if(n == 1)
   {
      return a;
   }
   else
   {
      facttail(n - 1, n * a);
   }
}

The program works as following:

facttail(4, 1) = facttail(3, 4)                                               /* winding phase */
                     facttail(3, 4) = facttail(2, 12)
                                      facttail(2, 12) = facttail(1, 24)
                                                        facttail(1, 24) = 24  /* terminating condition */

Observe that there is no unwinding phase necessary if we use a tail recursive function. How this helps is that many compilers can optimize tail recursion. When the compiler notices tail recursion, it will overwrite the function frame rather than maintain a frame for each recursive function. This is because there is no need to maintain a frame for each function call as there is no unwinding phase and the return of the function does not matter because it is not included in an expression and it is also the last executable statement of the function.

 

Related Posts:

Tags: , ,

Pointer to a function

December 20th, 2009 by Kevin | 1 Comment | Filed in C Programming

In a C program, we can have a pointer to a function which gives us a pointer to a specific block of executable code. The code to be executed is determined at the run time depending on the address assigned to the function pointer. This helps us create programs which can emulate the polymorphic capabilities of any object oriented programming language.

A function pointer is declared as

return-type (* function-pointer-name)(type arg1, type arg2. ...);

Following code excerpt shows an example how a function pointer can be used to design polymorphism in C.

struct MediaObject_
{
   ...........
   void (*play)(int ); /* declaration of a function pointer */
}MediaObject;

playAudio(int sound)
{
   ............
}

playVideo(int sound)
{
   ............
}

void main()
{
   MediaObject mediaObj;
   MediaType mediaType = getMediaType();

   if(mediaType == AUDIO)
   {
       mediaObj.play = playAudio; /* function pointer assignment */
   }
   else if(mediaType == VIDEO)
   {
      mediaObj.play = playVideo; /* function pointer assignment */
   }

   /* play function pointer can be used for audio or video*/
   mediaObj.play(100);
}

Care should be taken to provide some value to your function pointer before it is actually used. Since a function pointer is a variable, you will not get any compilation errors if you do not initialize it but your program will give an ugly crash at runtime.

 

Related Posts:

Tags: , ,

« Older Entries