Thread: Linux Mulithreaded Program - Help please!

Hello all,

I am new to multithreaded programming (in the Linux Debian environment) and so I thought I would work on a project to help me learn it. Here are the details of the project:

Write a multithreaded sorting program that works as follows: A list of integers is divided into two smaller lists of equal size. Two separate threads (which we will term sorting threads) sort each sublist using a sorting algorithm of your choice. The two sublists are then merged by a third thread - a merging thread - which merges the two sublists into a single sorted list.

I understand the general outline of what I'm supposed to do. Here's my code of what I've done so far (For the sorting algorithm I thought it might be best to implement a bubble sort):

Code:

#include <pthread.h>
#include <stdio.h>
#include  <stdlib.h>
#include <sys/types.h>

#define SIZE 10

//three threads
void *sorter(void *params);
void *merger(void *params);

int list[SIZE] = {7,12, 19, 3, 18, 4, 2,6, 15, 8};

int result[SIZE];

typedef struct
{
    int from_index;
    int to_index;
} parameters;

int main(int argc, char *argv[]){

    pthread_t pid1, pid2, pid3;
    
    //establish the first sorting thread
    parameters *data = (parameters *) malloc(sizeof(parameters));
    
    data->from_index = 0;
    data->to_index = (SIZE/2)-1;
    pthread_create(&pid1, 0, sorter, data);
    
    //establish second sorting thread
    data->from_index = (SIZE/2);
    data->to_index = SIZE-1;
    pthread_create(&pid2,0, sorter, data);
    
    pthread_join(pid1,NULL);
    pthread_join(pid2,NULL);
    
    //create merge thread
    data = (parameters *) malloc(sizeof(parameters));
    data->from_index = 0;
    data->to_index = (SIZE/2);
    pthread_create(&pid3, 0, merger, data);
    
    pthread_join(pid3,NULL);
    
    //print the result array
    
    return 0;
    
}

void *sorter(void *params){

parameters* p = (parameters*) params;

int begin = p->from_index;
int end = p->to_index;

//sort
int i,j,t;

for(i=begin; i< end; i++)
{
    for(j=begin; j< end-i; j++)
    {

        if(list[j] > list[j+1])
        {
            t = list[j];
            list[j] = list[j+1];
            list[j+1] = t;
            list[j] = result[j];
        }
    }
}


printf("Sorted array is: ");
int k;
for(k = begin; k< end+1; k++)
{
    printf(result[k]);
}

}

void *merger(void *params){

parameters* p = (parameters*) params;

int begin = p->from_index;
int end = p->to_index;

//sort
int i,j,t;

for(i=begin; i< end; i++)
{
    for(j=begin; j< end-i; j++)
    {

        if(list[j] > list[j+1])
        {
            t = list[j];
            list[j] = list[j+1];
            list[j+1] = t;
            list[j] = result[j];
        }
    }
}



int k;
for(k = begin; k< end+1; k++)
{
    printf("The result is: ", result[k]);

}
}

This is as far as I've gotten. I'm kinda stuck on what to do. I know I don't have it quite right. Would anyone be able to help me fix this? Thanks in advance for all your help! I really appreciate it!!!

Is my sorting and merging algorithm correct at all?
I thought the sorting algorithm was correct. If it was, how do I use what I have to do the merger?

Okay, I've been working on it some more and I've got it down to this

Code:

//Sort a list of numbers using two separate threads
//by sorting half of each list separately then
//recombining the lists

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

#define SIZE 10
#define NUMBER_OF_THREADS 3

void *sorter(void *params);    /* thread that performs basic sorting algorithm */
void *merger(void *params);    /* thread that performs merging of results */

int list[SIZE] = {7,12,19,3,18,4,2,6,15,8};

int result[SIZE];

typedef struct
{
    int from_index;
    int to_index;
} parameters;

int main (int argc, const char * argv[]) 
{
    int i;
    
    pthread_t workers[NUMBER_OF_THREADS];
    
    /* establish the first sorting thread */
    parameters *data = (parameters *) malloc (sizeof(parameters));
    data->from_index = 0;
    data->to_index = (SIZE/2) - 1;
    pthread_create(&workers[0], 0, sorter, data);
    
    /* establish the second sorting thread */
    data = (parameters *) malloc (sizeof(parameters));
    data->from_index = (SIZE/2);
    data->to_index = SIZE - 1;
    pthread_create(&workers[1], 0, sorter, data);
    
    /* now wait for the 2 sorting threads to finish */
    for (i = 0; i < NUMBER_OF_THREADS - 1; i++)
        pthread_join(workers[i], NULL);
    
    /* establish the merge thread */
    data = (parameters *) malloc(sizeof(parameters));
    data->from_index = 0;
    data->to_index = (SIZE/2);
    pthread_create(&workers[2], 0, merger, data);
    
    /* wait for the merge thread to finish */
    pthread_join(workers[2], NULL);
    

    /* output the sorted array */
    
    return 0;
}

void *sorter(void *params)
{
    parameters* p = (parameters *)params;

    //SORT

    int begin = p->from_index;
    int end = p->to_index+1;

    int z;
    for(z = begin; z < end; z++){
    printf("The array recieved is: %d\n", list[z]);
    }
    
    printf("\n");

    int i,j,t,k;

for(i=begin; i< end; i++)
{
    for(j=begin; j< end-i-1; j++)
    {

        if(list[j] > list[j+1])
        {
            t = list[j];
            list[j] = list[j+1];
            list[j+1] = t;
            
        }
    }
}

for(k = begin; k< end; k++){
    printf("The sorted array: %d\n", list[k]);
}

int x;
for(x=begin; x<end; x++)
{
list[x] = result[x];
}

printf("\n");

    pthread_exit(0);
}

void *merger(void *params)
{
    parameters* p = (parameters *)params;
    
    //MERGE
    int begin = p->from_index;
    int end = p->to_index+1;

int i,j,t;

printf("list[1]: %d",list[1]);
printf("result[1]: %d",result[1]);

for(i=begin; i< end; i++)
{
    for(j=begin; j< end-i; j++)
    {

        if(result[j] > result[j+1])
        {
            t = result[j];
            result[j] = result[j+1];
            result[j+1] = t;
            
        }
    }
}

int d;
for(d=0; d<SIZE; d++)
{
    printf("The final resulting array is: %d\n", result[d]);
}
        
    pthread_exit(0);
}

I'm still not sure what I'm doing wrong in my algorithms that its not working. It doesn't seem to catch the new sorted array. Any help on this problem would be appreciated VERY much! Thanks again in advance for all your help!

I know the sorting method works. I've tested it and it runs like its supposed to. What I'm trying to do in the program is take the elements of list, sort them and return them to their respective spots. That will be done for both arrays. After each sort, the elements will be copied over into the same respective positions of the result array in which will be passed to the merge method where I sort the result. Maybe this is not the correct way of doing it or performing such a merger? Any help would be greatly appreciated!

Thank you anduril462 - I appreciate your help. However, I did try and take the advice of you and Salem when I wrote the program. I'll admit, initially I started out by writing a bunch of code and hoping for the best, but when it failed and asked for help from the users here, I broke it down. In a threadless environment, my methods work fine. However, I think I'm doing something wrong with the threads that its not working properly. The other thing is your code suggests that I make two separate arrays from the first. However, I don't see how I can do that. The program starts off with one array. So when I get to the sort method, how do I know that I can put my values in a particular array. What I mean (hopefully more clearly) is that how do I tell the values (whether it be the first pass or second pass into the thread) to go into a particular array? My merge method would be much better if I have multiple arrays to work with, however, It seems feasible to only have two - an initial array (list) and the final, sorted array (result).

Thanks again for your help!

Originally Posted by billyjthorton

In a threadless environment, my methods work fine.

Sorry, but they don't. In post #5, sorter() and merger() as whole functions are both broken. You do correctly sort, but then you ruin your sorted list. merger() doesn't actually merge the two halves, it attempts to sort (incorrectly) the array you give it

Originally Posted by billyjthorton

However, I think I'm doing something wrong with the threads that its not working properly.

Yes, you have a few things wrong with your threaded code. But that will be dealt with later.

Originally Posted by billyjthorton

The other thing is your code suggests that I make two separate arrays from the first. However, I don't see how I can do that. The program starts off with one array. So when I get to the sort method, how do I know that I can put my values in a particular array. What I mean (hopefully more clearly) is that how do I tell the values (whether it be the first pass or second pass into the thread) to go into a particular array? My merge method would be much better if I have multiple arrays to work with, however, It seems feasible to only have two - an initial array (list) and the final, sorted array (result).

My functions will work with partial arrays. You see, for all intents and purposes, there is no difference between two halves of one array, and two separate arrays that are adjacent in memory. That is part of the reason I use length parameters everywhere. So, you can call my sort_array function on two halves, like so:

Code:

int list[SIZE] = {7, 12, 19, 3, 18, 4, 2, 6, 15, 8};
int results[SIZE];

int first_size = SIZE / 2;
int second_size = SIZE - first_size;
sort_array(list, first_size);  // sort the first half of the array
sort_array(list + first_size + 1, second_size);  // sort the second half of the array
merge_arrays(results, list, first_size, list + first_size + 1, second_size);

Note, you could write the merge_arrays function to merge in place, but that is a bit tougher. Merging into a separate array is pretty easy.

Okay. Its making more sense now...

anduril462, you say

You do correctly sort, but then you ruin your sorted list

Do you think you could point out to me where after the sort I ruin it so I can fix that problem?

Originally Posted by billyjthorton

Okay. Its making more sense now...

anduril462, you say
Do you think you could point out to me where after the sort I ruin it so I can fix that problem?

You probably think you're moving entries into your result list, but.....

That's one problem I couldn't figure out...why won't the entries go into the global variables?

Originally Posted by billyjthorton

That's one problem I couldn't figure out...why won't the entries go into the global variables?

Well, what's the difference between

Code:

a = b;

and

Code:

b = a;

?