Can you spot the race condition?

Can you spot the race condition?

The example program below contains a common threading error. When I first started programming with threads, this was the first race condition to bite me. The program uses Pthreads because that's what I was using at the time.

The program creates four threads that each print a message with a unique id number. Like many threaded programs, it sometimes works correctly even though it contains an error. Can you spot the race condition?

#include 
#include 

#define N 4

void* hello (void* myID)
{
   printf ("Hello from thread %d
", *(int *)myID);
   return NULL;
}

int main ()
{
   int j;
   pthread_t tid[N];

   for (j = 0; j < N; j++)
      pthread_create (&tid[j], NULL, hello, (void *)&j);

   for (j = 0; j < N; j++)
      pthread_join (tid[j], NULL);
}

If you see the error, be the first to post the solution and win the forum's ovation and fame forever.

17 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

The program below contains the same error but uses the Win32 threading API:

#include 
#include 

#define N 4

DWORD WINAPI hello (LPVOID myID)
{
   printf ("Hello from thread %d
", *(int *)myID);
}

int main (int argc, char* argv[])
{
   int j;
   HANDLE h[N];
   DWORD rc;

   for (j = 0; j < N; j++)
   {
      h[j] = CreateThread (0, 0, hello, (LPVOID)&j, 0, NULL);
   }

   rc = WaitForMultipleObjects (N, h, TRUE, INFINITE);
}

Perhaps you should CRITICAL_SECTION j? Seems like it would produce unpredictable results due to the passing in of the address of j, rather than a non-referenced copy of the integer.

-Dale

Hi Dale,
Welcome to the forum! You're the first to join.

You're correct that variable j is incorrectly passed to the threaded function. It's the source of the race condition. You could fix the race condition using a critical section but that would serialize execution, which defeats the purpose of multithreading. There's a better solution that doesn't require synchronization.

Henry

robert-reed (Intel)'s picture

In the case of an int, j could be passed by value instead of by reference. Then each of the threads would have its own copy, uniquely and correctly set.

You're on the right track, but you can't pass by value with a thread's user data reference because, after all, it's a reference. Since these values aren't really being shared, you could create a separate storage location for each value and copy the value of j to each one before creating the thread. Each thread would therefore have its own separate "value."

I'm sure there are many ways to solve this problem of which my suggestion is only one.

There are many ways to solve this problem without synchronization but they all boil down to your solution - pass each thread a reference to a unique storage location, e.g.:

   int id[N];
   for (j = 0; j < N; j++)
   {
      id[j] = j;
      pthread_create (&tid[j], NULL, hello, (void *)&id[j]);
   }

Also you might want to initialize each of the variable on different cache lines (128 bytes in P4) to avoid false sharing. It would also be a good idea to check aliasing issues and if found then try allocation in different sets of cache.

An earlier post mentions that the corrected example code is prone to false sharing. False sharing can degrade the performance of multithreaded applications but it's easy to avoid once you understand its cause. The "Developing Multithreaded Applications: A Platform Consistent Approach" article on Intel Developer Services has a good description of false sharing and how to detect it with the VTune Performance Analyzer.

Message Edited by intel.software.network.support on 12-09-2005 01:30 PM

Interesting thread. That is a very common problem with threaded programming. I usually want to pass more than a single parameter to threads with multiple instances active so I usually have a structure passed in with multiple arguments contained within for the void * argument to pthread_create(). This allows you to have both the ID number along with any other unique parameters you might want to use during thread initializiation.

To do this safely without serializing thread startup, the simplest thing is to build an array of these structures (if you know the thread count will be constant) or to dynamically create them otherwise. Essentially, it's the same as you handle the array of thread id's in your example code, just extended to the parameter or parameter block passed during thread creation.

It is indeed a very common problem with MT code. Generally more than a single data member is needed and it makes sense to pack all data in a single structure.

"Command" is a useful design pattern here.

struct ICommand
{
virtual void execute () = 0;
};

it's easy to define a framework with something like

Thread *CreateThread (ICommand *cmd);

the command will be executed at thread launch and the instance deleted after execution

the client code will be typically like :

class HenryGCommand : public ICommand
{
const int id;
// typically way more data here
virtual void execute ()
{cout << "Hello from thread " << id << "
";}
public:
HenryGCommand (int vId) : id(vId) {}
};

void Test ()
{
Thread *t[N];
for (int j=0; j t[j] = CreateThread(new HenryGCommand(j));
WaitFor(t,N,INFINITE);
}

Or we could just change the LPVOID to int and take out the references altogether :)

-Dale

Ignore my ramblings, I'm high on Nyquil today.

-Dale

I agree. Casting the int to a void* for the sake of passing it around is really no more inherently unsafe than using a void* in the first place. I assume you meant something like:

#include
#include
#define N 4
void* hello (void* myID)
{
printf ("Hello from thread %d
", (int)myID);
return NULL;
}
int main ()
{
int j;
pthread_t tid[N];
for (j = 0; j < N; j++)
pthread_create (&tid[j], NULL, hello, (void *)j);
for (j = 0; j < N; j++)
pthread_join (tid[j], NULL);
}

Yea, in my confused state of mind I was thinking the same thing. I would probably prefer to do something like this for our situations, because it would be faster than creating an extra set of variables everytime we went through this sort of loop, but casting from int to void* is probably bad form for the more general use presented here.

-Dale

Holy smokes this is old.. but I didn't see a good answer.. but maybe I missed it..

The problem with the code is that we pass the variable J from the caller to the thread by reference. Thread starts require a variable amount of time.. sometimes its fast sometimes it takes awhile.. (this depends if there is pooling, etc.) Because we pass by ref it is possible that, by the time the thread starts, the variable J has been incremented. If this happens we may get four lines saying thread 4 has started or some other erroneous values. J needs to be copied to the thread by value. There are many ways of doing this. Simply passing J in the VOID* would work since they are both 4 bytes.You could also create a class or struct and pass the value inside the pointer to this. However we accomplish this, it must be a separate value from the J that is being incremented by the starting thread.

Chris

Hello Chris,
Welcome to the forum. Your solution is correct but I don't see how it differs from previous posts. Please post an example code if you think your solution is different.

Thanks for reviving this thread. It's an oldie-but-goodie.

Best regards,
Henry

Login to leave a comment.