Find max in array using threads?

Question

How would you do this in c with a binary reduction and a barrier implemented using binary semaphores? This is the code I have so far. It doesnt have a barrier, and I'm confused on how to make one. Would I need mutex locks for this?

# include <stdio.h>
# include <pthread.h>
# define arrSize 10

struct StructMax
{
    int iMax;
};

int arr[arrSize];

void *thread_search_max(void *);

int main()
{
    pthread_t tid;
    struct StructMax *st_main,*st_th;
    int FinalMax;

    st_main=(struct StructMax*)malloc(sizeof(struct StructMax));

    int iCount;
    for(iCount=0;iCount<arrSize;iCount++)
    {
        printf("Enter Value of arr[%d] :",iCount);
        scanf("%d",&arr[iCount]);
    }        
    pthread_create(&tid,NULL,thread_search_max,NULL);

    st_main->iMax=arr[0];

    for(iCount=1;iCount<arrSize/2;iCount++)
    {
        if(arr[iCount] > st_main->iMax)
        {
            st_main->iMax=arr[iCount];
        }
    }    

    pthread_join(tid,(void**)&st_th);    

    if(st_main->iMax >= st_th->iMax)
    {
        FinalMax=st_main->iMax;
    }    
    else
    {
        FinalMax=st_th->iMax;
    }


    printf("Final Max : %d \n",FinalMax);
    return 0;
}


void *thread_search_max(void *para)
{
    struct StructMax *st;
    st=(struct StructMax*)malloc(sizeof(struct StructMax));

    int iCount;
    st->iMax=arr[arrSize/2];


    for(iCount=arrSize/2 + 1;iCount<arrSize;iCount++)
    {
        if(arr[iCount] > st->iMax)
        {
            st->iMax=arr[iCount];
        }
    }    

    pthread_exit((void*)st);        
}

[Don't cast the return value of `malloc()` in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). Write your allocations like: `st_main = malloc(sizeof *st_main);`. Much shorter, no pointless casts, and a bit safer too. — unwind, Feb 18 '15 at 14:30
As almost everyone else, you cast `malloc()`, [which is not needed](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) but ignore it's return value, which is bad practice. Also, use a mutex, and don't use a global variable, pass the array to the thread function via the last argument to `pthread_create`. And remember each `malloc()` should be matched by a `free()` somewhere. — Iharob Al Asimi, Feb 18 '15 at 14:30
Semaphore? Barriers? I'd avoid them searching for maximum in array, they'll hurt performance enough to push you back to a straight non parallel execution. If you're doing this for performance I'd consider to use _atomics_ (with a very careful implementation) or even (if your architecture allows you this _trick_) using _volatile_. — Adriano Repetti, Feb 18 '15 at 14:33

score 1 · Accepted Answer · answered Feb 18 '15 at 14:43

You didn't include stdlib.h: which is the main problem, but you should also consider some other minor fixes that would make your code robust.

The problem with not includeing stdlib.h is that the compiler assumes that malloc() returns an int, so you can see that this will cause problems.

If you enable compiler warnings, you can prevent this kind of things, I sometimes forget some headers, but I don't get too far because the compiler reminds me.

Assuming that you work with gcc then

gcc -Wall -Werror -o output $sourceFiles -pthread

will prevent compilation in this case.

This is an improved version of your program, with the stdlib.h header included

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

#define arrSize 10

struct StructMax
{
    int iMax;
};

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *thread_search_max(void *);

int main()
{
    pthread_t         tid;
    struct StructMax *st_main;
    struct StructMax *st_th;
    int               FinalMax;
    int               arr[arrSize];

    st_main = malloc(sizeof(struct StructMax));
    if (st_main == NULL)
        return -1;
    int iCount;
    for (iCount = 0 ; iCount < arrSize ; iCount++)
    {
        printf("Enter Value of arr[%d] :",iCount);
        scanf("%d",&arr[iCount]);
    }
    pthread_create(&tid, NULL, thread_search_max, arr);

    /* lock the mutex, in this secction we access 'arr' */
    pthread_mutex_lock(&mutex);
    st_main->iMax = arr[0];
    pthread_mutex_unlock(&mutex);

    for (iCount = 1 ; iCount < arrSize / 2 ; iCount++)
    {
        /* lock the mutex, in this secction we access 'arr' */
        pthread_mutex_lock(&mutex);
        if (arr[iCount] > st_main->iMax)
        {
            st_main->iMax = arr[iCount];
        }
        pthread_mutex_unlock(&mutex);
    }
    pthread_join(tid, (void **)&st_th);

    if (st_main->iMax >= st_th->iMax)
    {
        FinalMax = st_main->iMax;
    }
    else
    {
        FinalMax = st_th->iMax;
    }
    printf("Final Max : %d \n", FinalMax);
    free(st_th);
    free(st_main);
    return 0;
}

void *thread_search_max(void *para)
{
    struct StructMax *st;
    int               iCount;
    int              *arr;

    arr = para;
    if (arr == NULL)
        return NULL;
    st = malloc(sizeof(struct StructMax));
    if (st == NULL)
        return NULL;
    /* lock the mutex, in this secction we access 'arr' */
    pthread_mutex_lock(&mutex);
    st->iMax = arr[arrSize/2];
    pthread_mutex_unlock(&mutex);
    for (iCount = arrSize /  2 + 1 ; iCount < arrSize ; iCount++)
    {
        /* lock the mutex, in this secction we access 'arr' */
        pthread_mutex_lock(&mutex);
        if (arr[iCount] > st->iMax)
        {
            st->iMax = arr[iCount];
        }
        pthread_mutex_unlock(&mutex);
    }
    pthread_exit((void *)st);
}

see the usage of the mutex, it prevents the two threads from accessing the value simultaneously. And how global variables are not needed, besides they are a really bad idea when multithreading.

how would you do this if you had to start off with a bunch of threads containing two numbers each, and they had to build up the solution from there? Let's assume the array size is a power of 2, for the sake of my sanity, and yours. — Jf2k, Feb 19 '15 at 04:55

score 0 · Answer 2 · answered Feb 23 '17 at 15:07

Adding to the above optimization, the pthread should be created with attrributes specifying that is joinable (to guarantee that pthread_join() will block untill the thread specified is done). You can do this by declaring a 'attr' of type pthread_attr_t. The sample coded looks like below.

pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
pthread_t tid;

pthread_create(&tid, &attr, function, args);
//....
pthread_attr_destroy(&attr);

pthread_join(&tid, (void **)status);

The pthread_attr_destroy() is called before pthread_join(), because attr is no longer required once pthread_create() is invoked with appropriate arguments.

Find max in array using threads?

2 Answers2