[PLUG] Spot the race condition!

Jameson Williams jameson at jamesonwilliams.com
Tue Oct 6 03:53:49 UTC 2009


Hello all,

I've been trying to implement the parallel sort algorithm described at
http://www.cs.caltech.edu/~cs284/lectures/29oct97/sld001.htm. I'm currently
working on quicksorting some sublists. However, only sometimes does my
parallel quicksort routine produce sorted sublists, as expected. Sometimes
it fails to sort. I believe this is likely do to a race condition involving
my qs_arg object, but I'm not all together sure; my attempts to mutex it did
no further good. Can someone with a keen eye spot the race condition and
propose a solution?

Thank you!
Jameson Williams



#include <errno.h>
#include <error.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 This is a cpu bound activity. NUMBER_THREADS should probably be however
 many cores your machine has.
*/
#define NUMBER_THREADS 2

typedef struct {
    void   *base;
    size_t  nmemb;
    size_t  size;
    int(*compar)( const void *, const void * );
} quicksort_arg_t;

int intcmp( const void *a, const void *b ) {
    return *((int *)a) - *((int *)b);
}

void *quicksort_thread( void *arg ) {
    qsort( ((quicksort_arg_t *)arg)->base,
           ((quicksort_arg_t *)arg)->nmemb,
           ((quicksort_arg_t *)arg)->size,
           ((quicksort_arg_t *)arg)->compar );
    return ((quicksort_arg_t *)arg)->base;
}

void *quicksort( void *base, size_t nmemb, size_t size,
                 int(*compar)( const void *, const void * ) ) {
    pthread_t       *tids              = NULL;
    int              partition_index   = 0;
    int              number_partitions = NUMBER_THREADS;
    quicksort_arg_t  qs_arg;

    /*
      Set the initial arguments for the first sub list partition sort.
     */
    qs_arg.base   = base;
    qs_arg.nmemb  = nmemb / number_partitions;
    qs_arg.size   = size;
    qs_arg.compar = compar;

    if( (tids = malloc( sizeof( pthread_t ) * number_partitions )) ==
        NULL )
        error( EXIT_FAILURE, errno, "%s", strerror( errno ) );

    for( partition_index = 0;
         partition_index < number_partitions;
         partition_index++ ) {

        qs_arg.base = base + (qs_arg.nmemb * partition_index *
                              qs_arg.size);

        if( partition_index == (number_partitions - 1) )
            qs_arg.nmemb = nmemb - (partition_index * qs_arg.nmemb);

        if( pthread_create( &tids[partition_index], NULL,
                            quicksort_thread, &qs_arg ) != 0 ) {
            free( tids );
            error( EXIT_FAILURE, errno, "%s", strerror( errno ) );
        }
    }

    for( partition_index = 0;
         partition_index < number_partitions;
         partition_index++ ) {

        if( pthread_join( tids[partition_index], NULL ) != 0 ) {
            free( tids );
            error( EXIT_FAILURE, errno, "%s", strerror( errno ) );
        }
    }


    return NULL;
}

void test( void ) {
    int array[100];
    int i;

    for( i = 0; i < 100; i++ ) {
        array[i] = rand() % 10;
    }

    quicksort( array, 100, sizeof( int ), intcmp );

    for( i = 0; i < 100; i++ ) {
        if( i % 8 == 0 ) {
            printf( "\n" );
        }
        printf( "%2d", array[i] );
    }

}

int main( void ) {
    test();

    return 0;
}



More information about the PLUG mailing list