Многопотоковый сортировщик методом Хаора (быстрая сортировка)

Guest · 13.02.2007

Уважаемые специалисты ;-)

Пишу многопоточный сортировщик методом Хаора.
Если не использовать многопоточность, то все работает нормально все сортируется.
Незнаю как конкретно прикрутить многопоточность сюда, вобщем это мое первое многопоточное приложение.
Еще количество потоков необходимо указывать в переменной, т.е. не возможно ручками создавать каждый поток отдельно.

Пишу вот такой код:
Создал сначала клас для потоков потом создаю экземляры класса
либо через массив SortThread *S1Thread[2];
либо через вектор vector <SortThread*> S1Thread(2);

Далее выделяю память
for (int num=0; num<=numThread-1; num++){
S1Thread[num] = new SortThread(false); //запускаем все потоки
S1Thread[num]->FreeOnTerminate = true;
}
Все компилируется нормально даже работает если указать кол-во дополнительных поток 1, т.е
vector <SortThread*> S1Thread(1);

Скажите правильно ли я это делаю?
И если можно подскажите какой нибудь отладчик для многопотокового приложения?
Или я не в курсе как это сделать в Билдере?

Просматриваю потоки через прогу Process Explore, она пишет что у моих дополнительных поток один и тот же адресс в памяти, неуверен может это и правильно, у каждого потока ID разные, но выполняется только один и главный.

Process Explorer пишет для процессов которые работаю Статус Ready, а для неработающих Статус Wait: UserRequest. И еще у этих процессов время которое они работаю меньше секунды, т.е. они просто создались и чего то ждут. А у работающий дополнительный процесс время идет.
Хочу заметить что в программе я нигде процессы не прерываю.

grigsoft · 13.02.2007

Скорее всего ты неправильно понимаешь задачу. Почему остальные висят - это надо смотреть твою функцию потоковую. Но твой код всего лишь выполняет одну и ту же сортировку несколько раз. А тебе надо распараллелить сортировку - чтобы разные части сортировались разными потоками. Не помню точно что такое Хаар, но например, вызывая разные потоки вместо рекурсии на частях массива. Это надо посидеть над алгоритмом, подумать где можно запускать отдельные потоки, и как ограничить число потоков указанным лимитом

Собственно, я туплю - стандартный пул потоков: переписываешь свой алгоритм без рекурсии, через стек подзадач, запускаешь N потоков, они будут висеть на стеке в ожидании задач, и обрабатывать их по очереди. Надо только подумать по алгоритму - не могут ли данные пересекаться, но с первого взгляда все красиво.

Вот только написать стек, поддерживающий многопоточный запрос - это будет посложнее сортировки

Guest · 13.02.2007

Для: grigsoft
Задачу я понимаю правильно.
И код у меня выполняет не одну и ту же функцию нескольео раз.
У меня есть стек в котором хранятся данные которые еще надо сортировать.
Каждый поток должен вытаскивать от туда данные.
Если данных нет то он просто, пока что, в холостую в бесконечном цикле вертится (наверно это не правильно, наверно надо приостанавливать выполнение потока) и все время смотрит не появилось что либо в стеке.
Алгоритм у меня без рекурсии.
Могу прислать сам код если скажешь куда слать.
Он не большой.

Код:

Главный модуль
//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

#include <conio.h>
#include <vector.h>
#include <algorithm.h>
#include <iostream.h>
#include <stack.h>
#include <stdio.h>
#include "unit2.h"


int NumElm=1700000;
vector <int> K(NumElm);
stack <int> stackL;
stack <int> stackR;
CRITICAL_SECTION CS;

int main(int argc, char* argv[])
{
int numThread = 3; //Кол-во дополнительных потоков  >= 1
SortThread *S1Thread[2]; //создаем массив указателей на SortThread
//		vector <SortThread*> S1Thread(3);
int l = 1;
int r = NumElm-1;

randomize();

for (int i=1; i<NumElm; i++)
K[i] = random(1000000);
K[0]=-10000;

TDateTime TBegin, TEnd;
TBegin = Time();
stackL.push(l);
stackR.push(r);

InitializeCriticalSection(&CS);


for (int num=0; num<=numThread-1; num++){
S1Thread[num] = new SortThread(false); //запускаем все потоки
S1Thread[num]->FreeOnTerminate = true;
}

do{
doo:
if (stackL.empty()){
for (int num=0; num<=numThread-1; num++){
if (!S1Thread[num]->term){
goto doo;
}

for (int num=0; num<=numThread-1; num++){
TerminateThread((void*)S1Thread[num]->Handle,0);
}
DeleteCriticalSection(&CS);
goto bla;
}
}
} while (true);
bla:

for (int i=1; i<50; i++){
cout << K[i]<< " ";
}
cout << endl;

TEnd = Time();
TEnd = TEnd - TBegin;
cout << endl << FormatDateTime("n:ss:zzz",TEnd);
cout << endl<< "Data sorted"<<endl;
getch();
return 0;
}
//---------------------------------------------------------------------------


//**********************************************************************
//Дополнительные потоки

//---------------------------------------------------------------------------

#include <vcl.h>
#include <stack.h>
#include <vector.h>
#include <iostream.h>
#pragma hdrstop

#include "Unit2.h"

#pragma package(smart_init)

extern CRITICAL_SECTION CS;
extern stack <int> stackL;
extern stack <int> stackR;
extern vector <int> K;

__fastcall SortThread::SortThread(bool CreateSuspended)
: TThread(CreateSuspended)
{
term = false;
}
//---------------------------------------------------------------------------
void __fastcall SortThread::Execute()
{

do{
EnterCriticalSection(&CS);
if (stackL.empty()){
term = true;
}else{
term = false;
l = stackL.top();
stackL.pop();
r = stackR.top();
stackR.pop();
LeaveCriticalSection(&CS);
quicksort(l,r);
}
}while (true);
}

void __fastcall SortThread::quicksort(int l, int r)
{
//Начальная установка
int i;
int j;
int ikey;
int M = 1;	 //размер подмассива минимальный
Q2:
//Начать новую итерацию Q2
i = l;
j = r + 1;
ikey = K[l];

Q3:
//Сравнить K[i]:ikey Q3
do{
i++;
}while (ikey>K[i]);

//Сравнить ikey:K[j] Q4
do{
j--;
}while (K[j]>ikey);

//Проверить i:j Q5
if (j<=i){
swap (K[l],K[j]);

//Q7 Помещаем в стек
if ((r - j >= j - l) && (j - l > M)){
EnterCriticalSection(&CS);
stackL.push(j+1);
stackR.push(r);
LeaveCriticalSection(&CS);
r=j-1;

goto Q2;
}

if ((j - l > r - j) && (r - j >M)){
EnterCriticalSection(&CS);
stackL.push(l);
stackR.push(j-1);
LeaveCriticalSection(&CS);
l=j+1;

goto Q2;
}

if ((r - j > M)&& (M >= j - l)){
l=j+1;
goto Q2;
}

if ((j - l > M) && ( M >= r - j)){
r=j-1;
goto Q2;
}

} else {
//Взаимный обмен Q6
swap (K[i],K[j]);
//и возвращаемся на шаг Q3
goto Q3;
}
}
//---------------------------------------------------------------------------

grigsoft · 13.02.2007

А, ну это я не так понял из вопроса. Надо твой код поизучать - отлаживаться лениво

Скорее всего проблема в реализации стека. А что, continue и break вызывают у тебя отвращение?

grigsoft · 13.02.2007

Ну навскидку я бы все-таки освобождал критическую секцию если стек пустой. Так вроде ничего в глаза не бросается с синхронизацией. Я бы убрал goto и переписал стек на ожидание (WaitForSingle\MultipleObject).
А вот красивое условие окончания работы - это любопытный вопрос. Что-то сходу ничего не приходит в голову, надо подумать.

grigsoft · 13.02.2007

А, для окончания надо или N+1 событий ожидать, или ставить счетчик синхронизированный и событие по нему.

Что то меня твоя функция сортировки смущает с постоянными goto, но раз работает - ладно.

Guest · 13.02.2007

Насчет постоянных goto, в самой процедуре quicksort они необходимы чтоб не было рекурсии.
Насчет continue и break кажись они не так работаю как надо мне ведь надо просто прервать цикл, в VB например есть функции типа exit for, exit do. А вот если использовать здесь Break или continue то они просто прерывают текущую итерацию (покрайней мере в справке если я правильно понял именно так и написано). Кстати я пробовал и то и другое помоему не работает. Если знаешь как правльно скажи. Сам с неохотой использую goto.

О а насчет критических секций ты прав че то я упустил это. Они кстати накапливаются? Сколько раз зашел столько и выходить надо?
Сто пудова осовбодил критическую секцию и все запахало вроде )

А что это за WaitForSingle\MultipleObject. Это типа состояние когда вызываешь Suspend(); ???
Кстати правильно приостанавливать процесс или пофиг пусть в цикле бесконечном крутится?

Guest · 13.02.2007

Вроде работает но почему то через раз иногда он почему то досрочно выходит не отсортировав все данные (((

А, для окончания надо или N+1 событий ожидать, или ставить счетчик синхронизированный и событие по нему

N+1 событие это куда вобще я ж откуда знаю сколько будет проходов ???
Что это за счетчик синхронизированный чего считать?

grigsoft · 14.02.2007

Не, го-ту никак не может помочь от рекурсии избавиться - от рекурсии помогает стек. Разбираться мне в твоей реализации лень, но если это оно:http://algolist.manual.ru/sort/quick_sort.php, то думаю что ты неправильно сделал: после того как положил фрагменты в стек, твоя процедура должна завершаться, больше ей лопатить нечего.
Твой goto bla - это break; goto doo - это установка флажка + break + по флажку continue для внешнего цикла.
А не работает стабильно потому что с потоками так обращаться нельзя как ты - очень слабенькая у тебя процедура проверки окончания. Условие окончание - стек пустой, все потоки стоят. Ты что делаешь - если стек пустой, то проверяешь состояние потоков - а если пока ты это делал в стек уже что-то положили? А если первый поток уже запустился пока ты состояние второго проверяешь? Тебе надо проверить что все это произошло одновременно - вот для этого как раз и нужнa функция WaitForMultipleObjects.
А здесь мы как раз приходим к твоему постоянному опросу - так делать нельзя, хотя для твоей учебной задачи может и пройти, если учитель на код не смотрит или ему *цензура* Но я сомневаюсь что ты сможешь заставить это все стабильно работать.
Навскидку, чтобы нормально сделать надо: в каждом потоке иметь Event, который будет ставиться когда поток стоит. + Semaphor указывающий на состояние стека, + Event что стек пустой. Хотя может без семафора можно и обойтись. Потоки должны ждать семафор (WaitforsingleObject)- как сигнал что задача есть в стеке, а программа должна ждать все ивенты (WaitForMultipleObjects).
Вообщем почитай про multithreading, thread synchronization и прочее. Настоятельно рекомендую Рихтера (http://anatolix.naumen.ru/Books/Richter)

Кстати, в качестве дешевого решения можешь попробовать обернуть в CS проверку на окончание - stackL.empty() все равно надо оборачивать.

Guest · 14.02.2007

Не, го-ту никак не может помочь от рекурсии избавиться - от рекурсии помогает стек. Разбираться мне в твоей реализации лень, но если это оно:http://algolist.manual.ru/sort/quick_sort.php, то думаю что ты неправильно сделал: после того как положил фрагменты в стек, твоя процедура должна завершаться, больше ей лопатить нечего.

Да именно этот алгоритм. Только я писал по Искусству Программирования Кнута. Там блок-схемка я по простому так и написал ибо ставил цель не написать самый быстрый сортировщик с правильным кодом а именно прикрутить многопоточность. Ладно goto я уберу в quicksort прочел статью что ты дал ))) Отличная статья кстати все подробно написано.

Какая процедура? Если quicksort, то она и так завершается как только оработала подмассив и положила данные в стек. А вот поток в котором эта процедура была вызвана работает пока его не прервет главный поток. Он проверяет а вдруг что то в стеке появится. Тогда он вызовет процедуру quicksort.

Твой goto bla - это break; goto doo - это установка флажка + break + по флажку continue для внешнего цикла.

О первый break сработал ))) там я просто со скобками нахимичил поэтому и не срабатывало, как оно вобще выходило.
А насчет флажка break это ты имеешь ввиду сделать

Код:

bool brk=false;
do{
doo:
if (stackL.empty()){
for (int num=0; num<=numThread-1; num++)
if (!S1Thread[num]->term){
brk=true;
break;
//goto doo;
}
if (brk) {break}; // так что ли??? Дальше идет код который не должен выполняться если term какого-либо потока = false (т.е. если он работает еще)
for (int num=0; num<=numThread-1; num++){
TerminateThread((void*)S1Thread[num]->Handle,0);
}
DeleteCriticalSection(&CS);
break;
}
} while (true);

Или можно еще вот так написать

Код:

bool brk=false;
do{
doo:
if (stackL.empty()){
for (int num=0; num<=numThread-1; num++)
if (!S1Thread[num]->term){
brk=true;
//break;
//goto doo;
}
continue; //Или так??? Дальше идет код который не должен выполняться если term какого-либо потока = false (т.е. если он работает еще)
for (int num=0; num<=numThread-1; num++){
TerminateThread((void*)S1Thread[num]->Handle,0);
}
DeleteCriticalSection(&CS);
break;
}
} while (!brk);

А не проще ли тогда написать goto и операций помоему меньше. Что будет быстрее выполняться? Так каой вариант использовать ты считаешь лучше?

Guest · 14.02.2007

Блин опят я напутал. Не тот не другой вариант не работает. По разным причинам.
Че то я не соображу как отсюда убрать goto (
Сейчас этот код выглядит вот так:

Код:

do{
doo:
if (stackL.empty()){
for (int num=0; num<=numThread-1; num++)
if (!S1Thread[num]->term){
goto doo;
}

for (int num=0; num<=numThread-1; num++){
TerminateThread((void*)S1Thread[num]->Handle,0);
}
DeleteCriticalSection(&CS);
break;
}
} while (true);

Guest · 14.02.2007

хотя для твоей учебной задачи может и пройти, если учитель на код не смотрит или ему *цензура*

Это я для себя пишу. Для обучения. А не для учителя. Вот ка мне надоест так сразу и брошу. Только вот не хочется бросать не сделав по уму.
Наши учителя. Не знают что такое многопоточность и C++. Они вобще не чего не знают что не спроси.

А если первый поток уже запустился пока ты состояние второго проверяешь? Тебе надо проверить что все это произошло одновременно - вот для этого как раз и нужнa функция WaitForMultipleObjects.

А разве не достаточно тех двух проверок что я делаю???
Одна это вот этот злополучный код

Код:

do{
doo:
[b]if (stackL.empty()){[/b]
for (int num=0; num<=numThread-1; num++)
if (!S1Thread[num]->term){
goto doo;
}

for (int num=0; num<=numThread-1; num++){
TerminateThread((void*)S1Thread[num]->Handle,0);
}
DeleteCriticalSection(&CS);
break;
}
} while (true);

term показывает что поток простаивает.

И вторая проверка в Execute

Код:

do{
EnterCriticalSection(&CS); //т.е. стек другой процесс не заполнит
if (stackL.empty()){		 //если стэк пустой тогда меняем указатель что поток простаивает
term = true;
LeaveCriticalSection(&CS);
}else{
term = false;		 //если стэк не пустой тогда указатель показывает что поток работает и извлекаем из стэка данные 
l = stackL.top();
stackL.pop();
r = stackR.top();
stackR.pop();
LeaveCriticalSection(&CS);
quicksort(l,r);
}
}while (true);

Надо попробовать переписать код чтоб останавливать потоки если ему делать нечего через suspend(), и запускать через resume() если стэк наполнился.
А если все потоки стоят тогда удалять потоки.

[/quote]Вообщем почитай про multithreading, thread synchronization и прочее. Настоятельно рекомендую Рихтера (http://anatolix.naumen.ru/Books/Richter)

Рихтера я уже немного посмотрел там же все через WIN API описано, мне бы где нибудь описание с уклоном на Билдер. Архангельский че то совсем почти нечего не написал по этому вопросу в своей книжке. Даже про секции. Может посоветуешь книгу по Билдеру чтоб там все было подробненько?

grigsoft · 14.02.2007

не надо тебе с уклоном на билдер ничего читать - ты главное вникни в суть многопоточности и синхронизации. Я билдера не знаю вообще, так что книжек не посоветую.
Про break:

Код:

bool brk=false;
do{
doo:
if (stackL.empty()){
for (int num=0; num<=numThread-1; num++)
if (!S1Thread[num]->term){
brk=true;
break;
//goto doo;
}
if (brk) continue;

Машинный код с го-ту будет на пару байтов короче и на пару тактов быстрее. НО: каждый раз, когда ты или кто-то другой захочет внести исправление возле метки, ему придеться анализировать весь твой код, искать все переходы на метку что бы решить - код надо ставить до метки или после. А continue\break дают стандартный эффект в пределах цикла, читая код и видя break ты знаешь о результате, без необходимости искать метку и думать о смысле. Потому го-ту и считается плохим тоном - сопровождать такой код через год значительно сложнее.

Ну если для себя - то тем более надо по уму делать. Ты пойми главную идею - потоки работают независимо от тебя, основной поток может быть прерван в любой момент для выполнения остальных потоков. Ты проверил что стек пустой - отлично. Но после твоей проверки, и до того как ты проверишь состояние даже первого потока, что мешает третьему потоку опять положить элемент в стек? Потому и говорю - оберни всю проверку критической секцией, может это и поможет - для гарантии надо плотно изучать что и когда блокируется в потоках.

Но все равно опрос переменной в цикле - это принципиально неверный подход при работе с потоками. Ты можешь поиграться, но переделать на события и ожидание надо все равно, если хочешь действительно вникнуть в происходящее. И Suspend\Resume тоже неправильно.

Guest · 14.02.2007

Вот все заработало вроде.
Обернул проверку в CS и нашел одну ошибочку в исходных данных.
Когда писал без потоков все правльно написал.
А когда переделывал для многопоточности подумал что это не нужно.
В результате иногда выходило за границы массива.

Спасибо за помощь.

Все сервисы Codeby

Поиск

Поиск

Многопотоковый сортировщик методом Хаора (быстрая сортировка)

Guest

grigsoft

Guest

grigsoft

grigsoft

grigsoft

Guest

Guest

grigsoft

Guest

Guest

Guest

grigsoft

Guest