Einfache Multi-Threading-Hilfe? C++, WaitForSingleObject und Synchronisation

Question

Also versuche ich ein einfaches Multithreading-Programm, das die Collatz-Vermutung für eine große Anzahl von Zahlen validiert und die Gesamtzahl der validierten Zahlen zurückgibt. Jeder Thread (insgesamt 4) macht ein Intervall von Zahlen und aktualisiert die "validierte" Variable, wenn eine Zahl 1 erreicht. Ich bin auch Timing der gesamte Prozess (zum Vergleich vs eine Einzel-Thread-Berechnung)

Das Problem, das ich bin Das heißt, dass es nie eine Konsistenz gibt, wenn ich das "validierte" int am Ende des Programms ausdrucke, so denke ich, dass entweder die Threads übereinander geschrieben werden, oder der Hauptthread vor den anderen endet und somit gedruckt wird eine unvollständige Nummer. Ich gehe auch davon aus, dass die Uhr() Berechnungen auch aus sind, wenn der Hauptthread vor den anderen fertig ist. Also, wie STOPP ich den Haupt-Thread fortfahren, bis die anderen Threads abgeschlossen sind (so dass es auf eine aktualisierte validierte Anzahl warten und eine genaue Zeitmessung durchführen)? Dies ist, was ich dachte, dass WaitForSingleObject das getan hat, aber ich schätze, es stoppt nur den Haupt-Thread von EXITING und erlaubt ihm immer noch, seine anderen Funktionen zu berechnen.

Dies ist mein erster Schritt bei jedem Multithreading, und ich glaube nicht, dass ich die Funktionsweise der Synchronisation und des WaitForSingleObject-Befehls verstehe. Hier ist, was ich bisher in meiner Hauptfunktion habe:

EDIT: Hier ist meine aktualisierte Hauptfunktion und Collatz Funktion. Ich änderte es so, dass jeder Thread auf eine separate Variable zugreift, um das Synchronisationsproblem zu vermeiden, aber das Problem besteht immer noch. Es gibt keine konsistenten Wert, wenn ich drucken „validiert“ *

Erneut bearbeiten: Okay, so dass ich entfernt den „Faden“ int pro Mladen Jankovic, und verwendet nur einen einfachen Zähler, um die unterschiedlichen Intervallen zu verteilen die erstellten Threads. Es gibt jetzt einen konsistenten, korrekten Wert für "validiert". JEDOCH kann ich das Programm noch nicht fertigstellen, wenn es 1.000.000 Nummern gibt. Testen Sie es für 100.000 oder sogar 10.000 funktioniert einwandfrei, aber wenn ich es auf 1.000.000 Zahlen aufstocken, läuft das Programm unbegrenzt (Stunden), ohne tatsächlich eine Werte zurückgeben. Ich vermute, dass es bei einem bestimmten Wert hängen bleibt (zB 750831, wie Martin James darauf hingewiesen hat). Ich habe versucht, Int für Long Int zu ersetzen, aber es scheint, dass es immer noch unter Überlauf leidet. Irgendwelche Vorschläge? Und danke für die immense Hilfe.

LAST EDIT: Okay, so dass ich nur lange lange statt int und jetzt das Programm funktioniert einwandfrei verwendet. Danke für die Hilfe alle!

void main() 
{ 
    clock_t start; 
    clock_t finish; 
    unsigned int thread = 0; 

    start = clock(); 

    HANDLE h1 = (HANDLE)_beginthreadex(NULL, 0, collatz_thread, NULL, 0, NULL); 

    HANDLE h2 = (HANDLE)_beginthreadex(NULL, 0, collatz_thread, NULL, 0, NULL); 

    HANDLE h3 = (HANDLE)_beginthreadex(NULL, 0, collatz_thread, NULL, 0, NULL); 

    for (int i = 750001 ; i <= 1000000 ; i++) { collatz(i, 4); } 

    WaitForSingleObject(h1, INFINITE); 
    WaitForSingleObject(h2, INFINITE); 
    WaitForSingleObject(h3, INFINITE); 

    finish = clock() - start; 
    double time = finish/(double) CLOCKS_PER_SEC; 

    validated = v1 + v2 + v3 + v4; 
    cout << validated << " numbers validated." << endl; 
    cout << endl << time << " seconds." << endl; 
} 

unsigned _stdcall collatz_thread (void* n) 
{ 
    selection++; // selects a different interval each time collatz_thread is called 

    switch (selection) { 
    case 1: 
     for (int i = 1 ; i <= 250000; i++)  { collatz(i, 1); } 
     break; 
    case 2: 
     for (int i = 250001 ; i <= 500000; i++) { collatz(i, 2); } 
     break; 
    case 3: 
     for (int i = 500001 ; i <= 750000; i++) { collatz(i, 3); } 
     break; 
    } 
    return 0; 
} 

int collatz (int n, int thread) 
{ 
    int original = n; 

    while (n != 1) { 
    if (n%2 == 0) 
     n = (n/2); 
    else 
     n = (3*n + 1); 
    } 

    if (n == 1) { 
    switch (thread) { 
     case 1: 
      v1++; 
      break; 
     case 2: 
      v2++; 
      break; 
     case 3: 
      v3++; 
      break; 
     case 4: 
      v4++; 
      break; 
    } 
    return n; 
} 

}

Answer 1

Sie benötigen Zugriff auf validated zu synchronisieren, wenn sie variabel geteilt wird. Der einfachste Weg ist es, InterlockedIncrement Funktion anstelle von Standard-++-Operator zu verwenden, wenn Sie es erhöhen möchten. Ein anderer Ansatz besteht darin, beim Zugriff auf die gemeinsam genutzte Variable eine Art von Synchronisationsobjekt wie Spinlock oder Mutex zu verwenden, aber das ist zuviel, wenn Sie nur den Inkrementierungsvorgang synchronisieren müssen.

Wenn Sie weitere Informationen wünschen, geben Sie bitte Code von collatz Funktion.

Als 'usr' vorgeschlagen, für die bessere Leistung können Sie separate Variable für jeden Thread verwenden und sie dann im Hauptthread summieren. In diesem Szenario sollten Sie diese Variablen so auffüllen, dass sie nicht dieselbe Cache-Line teilen, um false sharing zu vermeiden.

Sie haben keine collatz_thread Funktion zur Verfügung gestellt, die eine weitere Ursache für inkonsistente Ergebnisse sein könnte. Der Grund dafür ist Zeiger auf Variable (&thread), die Thread # speichert, die zwischen den Aufrufen ändert, die neue Threads erstellen, so dass die neuen Threads je nach Status des OS-Scheduler möglicherweise nicht starten können, während Variable ist bereits geändert, um einen anderen Wert zu haben, also haben Sie mehr als einen Thread, der den gleichen Satz von Daten macht, während andere Sätze möglicherweise übersprungen werden. Da das Verhalten vom aktuellen Status des Thread-Schedulers abhängt, ist es ziemlich unberechenbar.

Die Lösung thread Variable void* gegossen wird, statt deren Adresse vorbei und dann in collatz_thread Funktion warf es zurück zu int:

HANDLE h1 = (HANDLE)_beginthreadex(NULL, 0, collatz_thread, (void*)thread, 0, NULL);

Und wie Martin vorgeschlagen, Sie möglicherweise Integer-Überlauf, aber es sollte keine inkonsistenten Ergebnisse, nur falsche Ergebnisse, aber dennoch konsistent.

Answer 2

Versuchen Sie einen Blick auf diese zu nehmen:

Semaphore and threads explenation from MSDN

Es ist wahrscheinlich die beste Dokumentation Sie online finden.

nun in Bezug auf Sie Code, gehe ich davon aus es nicht ganz gut funktioniert und das ist der Grund, warum: WaitForSingleObject - Basicly bedeutet, dass Sie versuchen, eine zu tun -1 auf dem h1 Semaphore (oder h2 oder h3) und Wenn Sie das nicht tun -1 (dh der Semaphor ist auf 0), dann warten Sie auf eine unendliche Zeit. WaitForSimgleObject sollte tatsächlich in Ihrer Thread-Routine und nicht in Ihrer Haupt-Routine aufgerufen werden.

Auch in Ihrem Thread-Objekt müssen Sie, sobald Sie mit der gemeinsamen Variablen fertig sind, den Semaphor freigeben, damit ein anderer Thread die Sperre für diesen bestimmten Semaphor erhalten kann.

Versuchen Sie, das Beispiel auf dem Link zu betrachten, den ich Ihnen gab, und ich bin sicher, dass Sie es schnell arbeiten lassen werden.

Answer 3

Ich habe versucht, einige gute, zu gute Ergebnisse zu erzielen: ((Irgendwas stimmt nicht, aber ich sehe es nicht. Ich bekomme keine Laufzeiten in der Größenordnung von Stunden, auch nicht für n von 1 bis 10.000.000 (zehn Millionen).

8 tests, 
8 tasks, 
counting to 1000000, 
using 14 threads: 
Validated: 1000000 in 670ms 
Validated: 1000000 in 671ms 
Validated: 1000000 in 624ms 
Validated: 1000000 in 656ms 
Validated: 1000000 in 655ms 
Validated: 1000000 in 655ms 
Validated: 1000000 in 640ms 
Validated: 1000000 in 686ms 
Average time: 657ms 
Total validated: 8000000 

8 tests, 
8 tasks, 
counting to 10000000, 
using 14 threads: 
Validated: 10000000 in 8081ms 
Validated: 10000000 in 7441ms 
Validated: 10000000 in 7784ms 
Validated: 10000000 in 7598ms 
Validated: 10000000 in 7956ms 
Validated: 10000000 in 7534ms 
Validated: 10000000 in 7816ms 
Validated: 10000000 in 7769ms 
Average time: 7747ms 
Total validated: 80000000 

Beachten sie, dass, obwohl es 14 Fäden sagt, dass für den gesamten Pool ist ein Thread immer wartet, verbraucht für andere Aufgaben zu erledigen, so dass nur 13 Threads waren tatsächlich verfügbar, um die Validierung auszuführen. Aus irgendeinem Grund war das optimal.

OK, mein i7 ist auf allen 4/8 Kernen flat-out, aber ich kann nicht sehen, Laufzeiten von shr Sekundengenaue Einfärbung, nur weil ich mehr Kerne habe und die Arbeit an alle verteilt habe :(

Das habe ich benutzt. Es ist ein bisschen anders als du es gemacht hast, weil ich die meisten Tools/Code herumliegen hatte. Es ist Visual C++, um damit anzufangen. Es gibt zwei Klassen. Jeder Lauf wird von einer 'PoolTest'-Klasse verwaltet, die mehrere' TestTask'-Instanzen an einen Threadpool abgibt, einen für jedes Segment des gesamten Bereichs von zu validierenden Ganzzahlen. Sie werden feststellen, dass Ihr Code in die TestTask-Klasse kopiert/eingefügt wurde. Ich habe hervorgehoben, wo die TestTask im PoolTest-Code zusammengestellt ist.Die 'PoolTest'-Klasse wartet dann auf ein Ereignis, damit alle' TestTask'-Instanzen abgeschlossen werden können - dies kann geschehen, weil die TestTask nach Abschluss auf eine 'taskComplete'-Methode von PoolTest zurückruft. Diese Methode greift auf einen thread-sicheren Zähler zu, der gezählt wird, wenn TestTasks von der Methode 'taskComplete' übergeben und heruntergezählt werden.

Dieser Code, den ich wiederverwendet habe, verkompliziert die Dinge ein wenig, weil es den Lauf mehrere Male wiederholen kann, um eine durchschnittliche Zeit zu erhalten, so dass das komplette Set von TestTasks mehrere Male ausgegeben werden kann.

Wenn die letzte TestTask auf Null herunter zählt, signalisiert sie das Event und der PoolTest wird dann erneut ausgeführt, um die Beendigung des gesamten Testlaufs an die GUI zu signalisieren (die GUI-Inhalte nicht zu belasten, ist nicht relevant).

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading; 


namespace WindowsFormsApplication1 
{ 

public class TestTask: Task{ 
public int validated; 
public int fromVal, toVal; 
public int ticks; 

    long collatz(long n) 
    { 
     while (n != 1) 
     { 
      if (n % 2 == 0) 
       n = (n/2); 
      else 
       n = (3 * n + 1); 
     } 
     return (n); 
    } 

    public override void run(){ 
     int index; 
     int localTo = toVal; 
     int localFrom = fromVal; 
     int localVal = 0; 
     for (index = localFrom; index < localTo; index++) 
     { // if not disproved, inc the stack 'validated' 
      if (1 == collatz(index + 1)) localVal++; 
     } 
     validated = localVal; // put stack result into instance field, 
    } 
    public TestTask(int paramx, EventHandler OnDone) 
     : base(paramx, OnDone){} 
}; 


/* a task that submits testTask instances. 
*/ 
public class PoolTest:Task{ 
    int FnumTasks; 
    int FnumTests; 
    int Fcount; 
    int FtestCount; 
    int taskCount; 
    int startTicks; 
    int endTicks; 
    int totalTicks; 
    EventHandler FonTaskComplete; 
    AutoResetEvent testCompleteEvent; 
    public int average; 
    public int testTicks; 
    public int Vone; 
    public int Vtot; 
    public TestTask thisTestTask; 

    public PoolTest(int testsNum, int tasks, int count, EventHandler taskDone, 
     EventHandler testDone) 
     : base(0, testDone) 
    { 
     FnumTests=testsNum; 
     FtestCount=testsNum; 
     FnumTasks=tasks; 
     Fcount=count; 
     Vtot = 0; 
     Vone = 0; 
     totalTicks = 0; 
     FonTaskComplete=taskDone; // call after each test to report ticks 
     testCompleteEvent= new AutoResetEvent(false); 
    } 
    void submitAtest(){ // queue up numTasks testTask instances 
     taskCount=FnumTasks; 
     startTicks = System.Environment.TickCount; 

//*********************THIS IS WHERE THE RANGES AND TASKS ARE ASSEMBLED 

     int startNum = 0; // here, start at 0 and build up the ranges 
     int countIncrement=Fcount/FnumTasks; // calc. range size 
     int endNum=startNum+countIncrement; // and so init. start/end 
     TestTask newTask; 
     for (int i = 1; i < FnumTasks; i++) // one less than requested 
     { 
      newTask=new TestTask(0, taskComplete); 
      newTask.fromVal=startNum; // load in the start/end for the loop 
      newTask.toVal = endNum; 
      myPool.submit(newTask);  // off it goes, see you later 
      startNum = endNum;   // now move range up for 
      endNum += countIncrement;  // next TestTask 
     } 
     // treat last range separately to cover div rounding when 
     // calculating 'countIncrement' 
     newTask = new TestTask(0, taskComplete); // do last one 
     newTask.fromVal = startNum; 
     newTask.toVal = Fcount; 
     myPool.submit(newTask); // send off the last one 
    } 

//***************************************************************** 

    public override void run(){ 
     submitAtest(); //start off the first run of testTasks 
     testCompleteEvent.WaitOne(); 
    } 
    void taskComplete(object sender, EventArgs e){ // called when a testTask 
     bool finishedTasks;       // instance is complete 
     lock (this) 
     { 
      thisTestTask = (TestTask)sender; 
      taskCount--;       // another one down 
      Vone += thisTestTask.validated;   // Vone - total for one run 
      Vtot += thisTestTask.validated;   // total for all runs 
      finishedTasks = (taskCount == 0);  // this run all done yet? 
      if (finishedTasks) 
      { 
       endTicks = System.Environment.TickCount; // yes, so calc. elapsed time 
       testTicks=endTicks-startTicks; 
       thisTestTask.ticks = testTicks; 
       totalTicks=totalTicks+testTicks; 
       if (0!=--FtestCount) {     // done all the test runs? 
        thisTestTask.validated = Vone;  // use this field to return run total 
        FonTaskComplete(thisTestTask, null); // and signal result of test 
        Vone = 0; 
        submitAtest();      // no, so send off another load 
       } 
       else{ 
         average=totalTicks/FnumTests;  // done all test runs! 
         testCompleteEvent.Set();   // signal all runs completed 
        }; 
      } 
     } 
    } 
}; 
}