Я предлагаю вместо того, чтобы дать каждому потоку один блок A (1-100) и B (101-200), чтобы каждый поток был назначен по модулю.Например, A будет принимать все нечетные индексы, B будет принимать все четные индексы, в результате чего получаются A {1,3,5,7,9, ..., 191,193,195,197,199} и B {2,4,6,8, ...,190.192.194.196.198.200}.Вероятно, это был бы самый быстрый и простой способ балансировки нагрузки потоков, поскольку сложность вычислений была бы равномерно распределена.
Следующим предложением было бы добавить bool, который указывает, можно ли продолжать обработку,Затем перед началом каждого расчета вы проверяете, можно ли продолжить.Таким образом, вы можете остановить вычисление, не прерывая поток, за счет одного дополнительного сравнения в каждом цикле.
#include <windows.h>
#include <stdio.h>
#include <process.h>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
bool run;
priority_queue<int> primes;
CRITICAL_SECTION critical;
struct args
{
int begin;
int end;
}par1, par2;
int e_prosto(int n)
{
for(int i = 2; i*i<(n + 1) ; i++)
if (n & 1 == 0 || n % i == 0) return 0;
return 1;
}
unsigned int __stdcall rabotnik(void* n)
{
struct args *lPar = (args*) n;
for(int i = lPar->begin; i < lPar->end && run; i++)
{
if(e_prosto(i)){
EnterCriticalSection(&critical);
primes.push(i);
LeaveCriticalSection(&critical);
}
}
run = false;
return 0;
}
int main()
{
int foo;
printf(" Tarsene na prosti do: ");
scanf("%d", &foo);
par1.begin=1;
par1.end=foo/2+1;
par2.begin=foo/2+1;
par2.end=foo;
run = true;
HANDLE hvadkaA, hvadkaB;
InitializeCriticalSection(&critical);
SYSTEMTIME st, now, then;
hvadkaA = (HANDLE)_beginthreadex(0, 0, &rabotnik, (void*)&par1, 0, 0);
hvadkaB = (HANDLE)_beginthreadex(0, 0, &rabotnik, (void*)&par2, 0, 0);
::GetSystemTime(&then);
WaitForSingleObject(hvadkaA, INFINITE);
WaitForSingleObject(hvadkaB, INFINITE);
CloseHandle(hvadkaA);
CloseHandle(hvadkaB);
::GetSystemTime(&now);
while(!primes.empty())
{
printf("%d \t", primes.top());
primes.pop();
}
printf("\nGotov za %d milisec", abs(now.wMilliseconds - then.wMilliseconds));
system("pause>nul");
return 0;
}
Другой способ состоит в том, чтобы разделить ваш диапазон на множество блоков, а затем, когда поток завершает, даютэто новый блок для обработки.Это дает преимущество, заключающееся в том, что в вычисления не добавляются дополнительные издержки, но требуется немного больше кода (поэтому вы повторно используете потоки и прослушиваете любой поток, а не только один).Чтобы иметь какое-либо значение, вам, вероятно, понадобится больший диапазон, и вам может потребоваться изменить размер блока по сложности (размеры блоков {1-100}, {101-150}, {151-175}, {176-183},{184-187}, ...).Краткий пример использования вашего кода (с симметричными размерами блоков):
#include <windows.h>
#include <stdio.h>
#include <process.h>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
priority_queue<int> primes;
CRITICAL_SECTION critical;
typedef struct args
{
int begin;
int end;
//Helper method for initalizing struct
void setAll(int inBegin, bool inEnd)
{
}
} *PArgs;
int e_prosto(int n)
{
for(int i = 2; i*i<(n + 1) ; i++)
if (n & 1 == 0 || n % i == 0) return 0;
return 1;
}
static DWORD WINAPI rabotnik(LPVOID lpParam)
{
struct args *lPar = (args*) lpParam;
for(int i = lPar->begin; i < lPar->end; i++)
{
if(e_prosto(i)){
EnterCriticalSection(&critical);
primes.push(i);
LeaveCriticalSection(&critical);
}
}
return 0;
}
int main()
{
const int NUM_THREAD = 2; //Use named constant incase you want to change later.
DWORD returnedThreadID;
DWORD threadID[NUM_THREAD];
HANDLE threadHandle[NUM_THREAD]; //Holds the handels for the threads.
int foo, //Range size.
fooBlockSize, //Number of elements in a block.
nextBlock;
PArgs par[NUM_THREAD];
printf(" Tarsene na prosti do: ");
scanf("%d", &foo); //Get range size from user.
fooBlockSize = foo / (NUM_THREAD * 10); //Set number of elements in a block.
InitializeCriticalSection(&critical);
SYSTEMTIME st, now, then;
for (int i = 0; i < NUM_THREAD; i++)
{
par[i] = (PArgs) HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(PArgs));
// If the allocation fails, the system is out of memory so terminate execution.
if( par[i] == NULL ){ cout<<"par HeapAlloc failed with error# "<<GetLastError()<<endl<<"Will now quit."<<endl; ExitProcess(2);}
}
for(int i = 0; i < NUM_THREAD; i++)
{
par[i]->begin = (fooBlockSize * i) + 1;
par[i]->end = par[i]->begin + fooBlockSize;
threadHandle[i] = CreateThread(NULL, 0, rabotnik, par[i], CREATE_SUSPENDED, &threadID[i]);
}
nextBlock = NUM_THREAD;
::GetSystemTime(&then);
for (int i = 0; i < NUM_THREAD; i++)
{
ResumeThread(threadHandle[i]); //Start threads
}
while( ((fooBlockSize * nextBlock) + 1) < foo)
{
returnedThreadID = WaitForMultipleObjects(NUM_THREAD, threadHandle, false, INFINITE); //Wait for a thread to complete.
for(int i = 0; i<NUM_THREAD;i++)
{
if(returnedThreadID = threadID[i])
{
//Update the thread's arguments with the new block.
par[i]->begin = (fooBlockSize * nextBlock) + 1;
par[i]->end = par[i]->begin + fooBlockSize;
//Restart the thread.
ResumeThread(threadHandle[i]);
nextBlock++;
}
}
}
for (int i = 0; i < NUM_THREAD; i++)
{
//Return heap memorry (good practice, though Windows should return it all when the process terminates).
if (HeapFree(GetProcessHeap(), 0, par[i]) == 0)
{
cout<<"HeapFree failed for par["<<i<<"]"<<endl;
}
//Not sure we need to close the threads, but it was in original version.
CloseHandle(threadHandle[i]);
}
::GetSystemTime(&now);
while(!primes.empty())
{
printf("%d \t", primes.top());
primes.pop();
}
printf("\nGotov za %d milisec", abs(now.wMilliseconds - then.wMilliseconds));
system("pause>nul");
return 0;
}
Существует компромисс между увеличением количества блоков по сравнению с размером блока.Увеличение количества блоков означает, что будет меньше времени, затрачиваемого только на один блок, способный обрабатывать (поток [0] завершается, и ничего не осталось обработать, пока поток [1] завершает работу), но также означает, чтоЯ потратил больше времени на ожидание цикла диспетчера, чтобы назначить новый блок для обработки.С вашей формулировкой проблемы я ожидаю, что для поиска простых чисел более высокого уровня потребуется столько времени, что это не имеет значения.
Как отмечено в других ответах, не используйте один и тот же стек для хранения простых значений, найденных каждымпоток (количество времени, необходимое для работы блокировки будет чрезмерным).Если вы хотите, чтобы простые числа возвращались в числовом порядке, я предлагаю либо переписать цикл, который печатает простые числа, чтобы он проходил через оба стека одновременно, печатая следующее значение (по порядку).Что-то вроде:
while(!primes1.empty() && !primes2.empty())
{
if(primes1.top() > primes2.top())
{
printf("%d \t", primes1.top());
primes1.pop();
}
else
{
printf("%d \t", primes2.top());
primes2.pop();
}
}
Вам придется иметь дело со значениями, оставшимися в одном стеке, когда другой станет пустым (или, возможно, поместите -1 внизу каждого стека, так что если вы либопусто, тогда все значения больше -1 будут уже напечатаны).
Другим решением будет сохранение отсортированного списка простых чисел, который обновляется каждый раз, когда возвращается поток.Затем это можно было бы скопировать в структуру par для более быстрого обнаружения простого числа (если число делится равномерно на существующее простое число, то число не простое).
Примечание: я не проверял эти примеры, хотя они должныбыть достаточно близко, чтобы дать вам общее представление.