windows - Afslutning af en tråd i C ++ fra en anden tråd

Indlæg af Hanne Mølgaard Plasc

Problem



Dybest set finder jeg primer med to tråde. Jeg splitter rækkevidden af ​​mulige primer i halv for hver tråd eller på anden måde statisk fordeler afstanden mellem trådene. Men tråden, der skal håndtere de mindre tal, vil uundgåeligt afslutte før den, der beregner de større. Hvad jeg vil gøre er, så snart en tråd går igennem dennes rækkevidde, afslut begge tråde og derefter give halvdelen af ​​resten af ​​tråden, der ikke var færdig med den, der gjorde det at de ville rekursivt udjævne og altid løbe parallelt.
Eks: A (1-100) og B (100-200), A slutter først, mens B stadig er på 150. Begge stop, A starter som A (150-175) og B ligesom B (175-200).


Her er min kode hidtil:


#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;
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; i++)
    {
        if(e\_prosto(i)){
            EnterCriticalSection(&critical);
            primes.push(i);
            LeaveCriticalSection(&critical);
        }
    }
    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;

    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 	", primes.top());
        primes.pop();
    }
    printf("
Gotov za \%d milisec", abs(now.wMilliseconds - then.wMilliseconds));
    system("pause>nul");
    return 0;
}

Bedste reference


Jeg foreslår snarere at give hver tråd en blok A (1-100) og B (101-200), at hver tråd bliver tildelt en modulo. For eksempel vil A tage alle ulige indekser, B ville tage alle lige indekser, der resulterer i A {1,3,5,7,9, ..., 191,193,195,197,199} og B {2,4,6,8, ..., 190.192.194.196.198.200}. Dette ville sandsynligvis være den hurtigste og nemmeste måde at indlæse balance på trådene, da kompleksiteten af ​​beregningerne ville blive jævnt fordelt.


Det næste forslag ville være at tilføje en bool, der angiver, om det er ok at fortsætte behandlingen. Derefter kontrollerer du før starten af ​​hver beregning, om det er ok at fortsætte. På denne måde kan du stoppe beregningen uden at afslutte tråden på bekostning af en ekstra sammenligning af hver løkke.


#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 	", primes.top());
        primes.pop();
    }
    printf("
Gotov za \%d milisec", abs(now.wMilliseconds - then.wMilliseconds));
    system("pause>nul");
    return 0;
}


Den anden måde ville være at opdele dit interval i mange blokke, så når en tråd fuldender giver den en ny blok til at behandle. Dette har den fordel, at du ikke tilføjer yderligere overhead til beregningen, men kræver lidt mere kode (så du genbruger trådene og lytter efter en hvilken som helst tråd, der skal udfyldes, ikke kun en). For at være af nogen værdi, vil du sandsynligvis have brug for et større udvalg, og du skal muligvis variere blokstørrelse efter kompleksitet (blokstørrelser {1-100}, {101-150}, {151-175}, {176-183}, {184-187}, ...). Et hurtigt eksempel ved hjælp af din kode (med symmetriske blokstørrelser):


#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 	", primes.top());
        primes.pop();
    }
    printf("
Gotov za \%d milisec", abs(now.wMilliseconds - then.wMilliseconds));
    system("pause>nul");
    return 0;
}


Der er en afvejning mellem at øge antallet af blokke versus blokstørrelse. Ved stigning af antallet af blokke betyder det, at der vil være mindre tid brugt med kun en blok, der kan behandles (tråd

Andre referencer 1

fuldender og der er ikke noget tilbage at behandle, mens tråd
#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;
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; i++)
    {
        if(e\_prosto(i)){
            EnterCriticalSection(&critical);
            primes.push(i);
            LeaveCriticalSection(&critical);
        }
    }
    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;

    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 	", primes.top());
        primes.pop();
    }
    printf("
Gotov za \%d milisec", abs(now.wMilliseconds - then.wMilliseconds));
    system("pause>nul");
    return 0;
}
er færdig), men betyder også at der vil Jeg har mere tid til at vente på forsendelsessløjfen for at tildele en ny blok til at behandle. Med din problemstilling fortæller jeg, at det tager så lang tid at finde de højere primere, som det ikke betyder noget.


Som det fremgår af de andre svar, må du ikke bruge den samme stak til opbevaring af de primærværdier, der findes af hver tråd (mængden af ​​tid, der kræves for at arbejde med låsen, vil være for stor). Hvis du vil have primerne returneret i en numerisk rækkefølge, foreslår jeg enten at omskrive sløjfen, der udskriver primene, så den går gennem begge stakke på samme tid, udskrivning af den næste værdi (efter ordre). Noget som:


    while(!primes1.empty() && !primes2.empty())
    {
        if(primes1.top() > primes2.top())
        {
            printf("\%d 	", primes1.top());
            primes1.pop();
        }
        else
        {
            printf("\%d 	", primes2.top());
            primes2.pop();
        }
    }


Du ville skulle håndtere værdierne tilbage i en stak, når den anden er tom (eller måske placere -1 på bunden af ​​hver stak, så hvis du enten stak er tom, vil alle værdier større end -1 allerede blive udskrevet) .


Den anden løsning ville være at opretholde en sorteret liste over primer, som opdateres hver gang en tråd vender tilbage. Dette kunne derefter kopieres til par strukturen for hurtigere primær detektion (hvis et tal er deleligt jævnt med en eksisterende prime så er nummeret ikke prime).


Bemærk: Jeg har ikke testet disse eksempler, selv om de skal være tæt nok til at give dig den generelle ide.

Andre referencer 2


At afslutte en tråd voldsomt er en dårlig idé, da du kan forlade din proces i en dårlig tilstand. Hvis din tråd løber i en loop, kan du indstille et flag eksternt, at tråden kan teste og bestemme, om du vil afslutte sig selv (dette kan gøres ved blot at afslutte thead-funktionen). Husk bare at beskytte dit flag med en mutex.


Der er nogle andre mønstre, som du måske vil se på. Du ønsker måske at sætte dit primække i en kø. Hver arbejdstråd kan derefter trække værdier ud af køen og udføre søgningen. På denne måde kan du jævnt opdele lasten uden at dræbe og genstarte tråde.

Andre referencer 3


Din førende algoritme er forfærdelig ineffektiv, men jeg vil gerne tale om det nu ..


threading:


Opsæt en jobkø for hver tråd. Dræbende/afsluttende korte levende tråde, især til førsteklasses find, lyder som en rigtig dårlig ide.


Undgå anfægtelse. Brug ikke låsning til primes.push(i);. Indstil en separat kø for hver tråd, tryk resultaterne der. Når tråden er færdig med området, skal du derefter indtaste criticalsection og fusionere resultaterne. måde du næsten ikke låser.