[PLUG] Spot the race condition!

[Heath Morrison]

It appears that you are using a single qs_arg variable and passing a
pointer to it into each thread that you create. The next cycle of the
loop then clobbers everything in this variable's contents, even if the
thread you spawned is still working on it. Don't share your qs_arg
memory between threads. Make sure you don't make this a variable
scoped locally to your partition_index loop though, either. I'd
suggest pre-allocating an array of number_partitions variables for
your qs_args, or something similarly transparent.

-Heath


On Mon, Oct 5, 2009 at 8:53 PM, Jameson Williams
<jameson at jamesonwilliams.com> wrote:
> 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;
> }
> _______________________________________________
> PLUG mailing list
> PLUG at lists.pdxlinux.org
> http://lists.pdxlinux.org/mailman/listinfo/plug
>