[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