Is pthread_mutex_lock fair?

[Shachar Shemesh]

Hi all,

In principle, a mutex needs to satisfy two conditions:
1. It should never ever ever allow two threads/processes in
simultaneously (exclusion)
2. A blocked process/thread should know that, sooner or later, and
assuming that other threads are occasionally releasing the threads, it
will be allowed in (fairness).

If condition number 1 is not met, we will say that the mutex is
non-exclusive (read - horrendously broken).
If condition number 2 is not met, we will say that the mutex does not
prevent starvation.

I have circumstantial evidence that pthread_mutex_lock on 2.6.18, at
least on a single CPU machine, does not prevent starvation.

Attached is a program that tests this. It creates as many threads as are
specified in the command line. Each thread tries to write its unique
number into the array "results". The current position in the array is
controlled by a var called "position". Updating the variable requires
obtaining a mutex. Here's the thing: since the total amount of positions
in "results" is determined by "TEST_SIZE", and more to the point, is
predetermined, how dominant one thread over the others is solely
controlled by how fair pthread_mutex is with sharing the lock between
the threads.

The results, on my machine, are pretty bad.

I have actually had one run where the results looked like this:
> $ ./mutex_fair 6
> Thread b7d88bb0 started as thread #0
> Thread b7587bb0 started as thread #1
> Thread b6d86bb0 started as thread #2
> Thread b6585bb0 started as thread #3
> Thread b5d84bb0 started as thread #4
> Thread b5583bb0 started as thread #5
> Results: 4115693 1079530 0 5307675 1 120474
> Results: 11383803 1079530 0 14561398 1 120475
> Results: 24359183 1079530 0 18432014 1 373438
> Results: 35356101 1079530 0 23592369 1 1635686
> Results: 37747800 1079530 0 26963875 1 11958452
> Results: 52274254 1079530 0 26963875 1 19682340
> Joined thread #0
> Joined thread #1
> Joined thread #2
> Joined thread #3
> Joined thread #4
> Joined thread #5

That's right. Within 100 million mutex acquisitions, not once did thread
number 3 managed to get the mutex, and thread number 5 only got it once.
This was not the only run that was more or less that bad, but these are
not the typical numbers.

Most runs, while not THAT bad, are still far from good. The difference
between the most and the least dominant threads can easily reach a
factor of 40 on a typical run.

Any insight into this will be most welcome.

Thanks,
Shachar

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define TEST_SIZE 100000000

volatile int results[TEST_SIZE], position=0;

int worker( int threadnum )
{
   static pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;

   printf("Thread %lx started as thread #%d\n", pthread_self(), threadnum);

   pthread_mutex_lock(&mutex);
   while( position<TEST_SIZE ) {
      // printf("results[%d]=%d\n", position, threadnum);
      results[position++]=threadnum;
      pthread_mutex_unlock(&mutex);
      pthread_mutex_lock(&mutex);
   }
   pthread_mutex_unlock(&mutex);

   return 0;
}

int *histo;

void printres(int numthreads)
{
   int i;

   printf("Results: ");
   for( i=0; i<numthreads; ++i )
      printf("%d ", histo[i]);

   printf("\n");
}

int main(int argc, char * argv[] )
{
   int numthreads=atoi(argv[1]);

   if( argc<2 || numthreads==0 )
      exit(1);

   pthread_t *threads=calloc(sizeof(pthread_t), numthreads);
   histo=calloc(sizeof(int), numthreads);

   int i;

   int oldpos=position;

   for( i=0; i<numthreads; ++i ) {
      pthread_create(threads+i, NULL, (void *(*)(void *))worker, (void *)i);
   }

   /* Reap the results every second */
   while( oldpos<TEST_SIZE ) {
      sleep(1);

      for( ; oldpos<position; ++oldpos ) {
         histo[results[oldpos]]++;
      }

      printres(numthreads);
   }

   for( i=0; i<numthreads; ++i ) {
      pthread_join( threads[i], NULL );
      printf("Joined thread #%d\n", i);
   }

   return 0;
}