How to check if thread is done

[aymank1985]

Hi,
I am doing a quicksort where the function call two threads , passing left array to the pivot , and right array to the pivot .
i am trying to check if the threads are finished , which means the array is sorted , then return from my quicksoft function to main
My issue is trying to identify a value i in my for(int i = 0; i < 1; i++) to check all threads created , unless theres a better way to do that.

        _beginthreadex(NULL, 0,  QuickSort,  arrLeft, 0, 0);
	_beginthreadex(NULL, 0,  QuickSort,  arrRight, 0, 0);
	bool rightFlag = true;
	bool leftFlag = true;
	while(rightFlag && leftFlag)
	{
		rightFlag = false;
		leftFlag=false;
		for(int i = 0; i < 1; i++)
		{
			rightFlag =rightFlag || arrRight[i].run;
		}
		for(int i = 0; i < 1; i++)
		{
			leftFlag = leftFlag || arrLeft[i].run;
		}
	}
	info->run = false;

main has while(info.run){}

[Computergeek01]

The return value from _beginthreadex() is a handle to that thread that can be used with the "WaitForMultipleObjects()" function. This way you're not spiking your CPU with that "while()" loop.

WaitForMultipleObjects(): http://msdn.microsoft.com/en-us/library/windows/desktop/ms687025(v=vs.85).aspx

If you would like to verify my claim:
_beginthreadex(): http://msdn.microsoft.com/en-us/library/kdzttdcb(v=VS.80).aspx

[aymank1985]

Hi,

Thank you for your reply, sorry i am new to threading , we have not covered such function , but i dont thing its a problem to use it for sure .

I did the following but not doing it :

        HANDLE t1=(HANDLE) _beginthreadex(NULL, 0,  QuickSort,  arrLeft, 0, 0);
	HANDLE t2=(HANDLE)_beginthreadex(NULL, 0,  QuickSort,  arrRight, 0, 0);
	 WaitForMultipleObjects(1, &t1, 0, 0);
	 WaitForMultipleObjects(1, &t2, 0, 0);

main got

   HANDLE main=(HANDLE) _beginthreadex(NULL, 0,  QuickSort, &info, 0, 0);
   WaitForMultipleObjects(1, &main, 0, 0);

[Computergeek01]

The second argument to "WaitForMultipleObjects()" needs to be an array of HANDLE objects. I'm a little confused about what you posted can I see all of your code? Or at least Main and QuickSort?

[aymank1985]

Hi,
Thanks for quick reply , this is the code after doing the above , the old method i was trying to achieve is commented :

#include <iostream>
#include <fstream>
#include <windows.h>
#include <process.h>
#include <time.h>
#include <string>
#include <sstream>
#include <string>
#include <array>
using namespace std;
int globalArraySize=0;
struct ThreadInfo
{
	int *list;
	int size;
	bool run;
	int *pLeft;
	int *pRight;
};

int * readFile(){
	int* array1 ;
	int arraysize;
	int i=0;
	ifstream myfile ("input.txt");
    if (myfile.is_open())
  {
	myfile >> arraysize;
	array1= new int[arraysize];
		while ( myfile.good() )
		{
			myfile >> array1[i++];
		}
		myfile.close();
  }
  else cout << "Unable to open file"; 
  globalArraySize=arraysize;
  return array1;
}
unsigned __stdcall QuickSort(void* a) {

	ThreadInfo *info = (ThreadInfo*)a;
	//int arraysize=_msize(array) / sizeof(int);
	int *array=info->list;
	if (info->size<=1){
		info->run = false;
		return 0;
	}
	cout << " First element is   " <<  array[0] <<endl;//<<"  last element is " << array[info->size-1]<< endl;
	srand(time(NULL));
	int pivotIndex=(rand())%info->size;
	cout << "Pivot Index is " << pivotIndex << endl;
	int pivot =array[pivotIndex];
	int *pPivot=&array[pivotIndex];
	cout << " Pivot is   " <<  pivot<< endl;
	int leftSize=pivotIndex;
	int rightSize=info->size-(pivotIndex)-1;
	//cout << "Full Size is  " <<  info->size << endl;
	//cout << "Right size is : " << rightSize << endl;
	
	while (info->pLeft < info->pRight){
		while ( *info->pLeft < pivot){
			++info->pLeft;
		}
		while ( *info->pRight  > pivot){
			--info->pRight;
		}
			int temp=*info->pLeft;
			*info->pLeft=*info->pRight;
			*info->pRight=temp;
	}
	//cout << " First element in the array after loop is : " << info->list[0] << endl;
	ThreadInfo *arrLeft =new ThreadInfo;
	arrLeft->list=info->list;
	arrLeft->pLeft=info->list;
	//cout << "First element is the left array is : " <<arraarrLeft->pLeft << endl;
	arrLeft->pRight=pPivot-1;
	arrLeft->size=leftSize;
	arrLeft->run=true;
	ThreadInfo *arrRight=new ThreadInfo;
	arrRight->list=pPivot+1;
	arrRight->pLeft=pPivot+1;
	arrRight->pRight=&info->list[info->size-1];
	arrRight->size=rightSize;
	arrRight->run=true;
        HANDLE t1=(HANDLE) _beginthreadex(NULL, 0,  QuickSort,  arrLeft, 0, 0);
	HANDLE t2=(HANDLE)_beginthreadex(NULL, 0,  QuickSort,  arrRight, 0, 0);
	/*
	bool rightFlag = true;
	bool leftFlag = true;
	while(rightFlag && leftFlag)
	{
		rightFlag = false;
		leftFlag=false;
		for(int i = 0; i < 2; i++)
		{
			rightFlag =rightFlag || arrRight[i].run;
		}
		for(int i = 0; i < 2; i++)
		{
			leftFlag = leftFlag || arrLeft[i].run;
		}
	}
	info->run = false;*/
	return 0;
}

int main () {
    //int* list;
    ThreadInfo info;
    //Read the input.text file , and pass an array , that contain the values in that text file .
	info.list =readFile() ;
	info.run = true;
	info.pLeft=&info.list[0];
	info.pRight=&info.list[globalArraySize-1];
	info.size=globalArraySize;
  //Start my thread , passing the array passed from readFile function.
    HANDLE main=(HANDLE) _beginthreadex(NULL, 0,  QuickSort, &info, 0, 0);
    WaitForMultipleObjects(1, &main, 0, 0);
 // while(info.run){}
    cout << "array elements are " ;
    for ( int i=0;i<=7;i++){
	  cout <<" , " <<info.list[i];
    }
    cout << endl;
    system ("pause");
    return 0;
}

[Computergeek01]

QuickSort doesn't return a handle so the call to WaitForMultipleObjects On Line 119 doesn't do anything. Also QuickSort needs to be broken up into two maybe three functions. I don't know how you expect to call that recursivley.

To use "WaitForMultipleObjects()" You need an array, so after you've figured out your program flow issue, Starting at Line 86:

HANDLE hArray[2];
hArray[0] =  =(HANDLE) _beginthreadex(NULL, 0,  QuickSort,  arrLeft, 0, 0);
hArray[1] =  =(HANDLE) _beginthreadex(NULL, 0,  QuickSort,  arrRight, 0, 0);
WaitForMultipleObjects(2, hArray, TRUE, INFINITE);

This will cause the program to wait until it recieves status changes from both threads.


EDIT: The idea of sorting a set of data from both ends at once is flawed from the start. You won't be able to get this to work right even if you figured out the threads. Threads are useful because they allow INDEPENDENT tasks to be processed alongside eachother instead of having one function have to pause it's execution until the function of another is completed.

[aymank1985]

Hi,
Thank you for your reply .
So should i still have to figure out how to know if all threads are done before calling cout in my main .
As i mentioned , using the WaitforMultipleObjects whats covered . I guess this is why we were asked to sort the array in a such manner .

Thanks

[Computergeek01]

You were told to sort a single array using multiple threads? This is not something I know how to do. Can you confirm that this was the assignment?

[aymank1985]

Hi,
Yes exactly , this is what was required in the assignment regarding that part :
" The main requirement of this assignment is that the implementation should enable leftArr and rightArr be sorted concurrently in two different threads. "

[Computergeek01]

The problem is that threads work independantly of eachother, so if they are both writing to the same address then you're going to have a collision and possible data loss. If you have the algorythm then it really doesn't matter. Everything I've posted so far is still relavent unless the threads need to talk to eachother, in which case you could just use a global variable.

[aymank1985]

ooh i see what you mean , so basically if both are writing at the same memory location , i cant create two threads to write in two different memory locations .
Can you please advice which area in my code i need to reconsider maybe alternative way to implement ?

Thanks aloooot

[Computergeek01]

No creating two threads to write to two memory locations is just fine, in fact that's exactly what you want. You cannot, or rather should not, have two threads writting to the SAME memory location.