我建議不要給每個線程一個塊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結構中,以便更快地進行主要檢測(如果某個數字可以被現有的素數均勻分配,則該數字不是素數)。
注:我沒有測試過這些例子,儘管它們應該足夠接近以給你一般的想法。
爲每個線程設置一個作業隊列會更有意義。殺死/終止短線程,特別是對於主要發現聽起來像是一個非常糟糕的主意。你是否僅僅將它作爲線程練習? – 2012-02-27 22:59:36
是的,我今天只是看着線程,這是一個練習 – 2012-02-27 23:06:50
運行一個多線程篩看起來似乎是一個更有趣的練習。 – 2012-02-27 23:39:21