Threads

[rapso]

Algorithmiker schrieb:

rapso schrieb:

;fricky schrieb:

rapso schrieb:

das einfachste waere ein ringbuffer, das waere nicht nur lockfree, sondern auch waitfree.

aber nicht normalerweise, nur spezielle konstruktionen.

doch, normalerweise ist das der fall. man muss sich schon muehe geben sowas simples kaputt zu implementieren.

Das bezweifel ich, sonst hätte RedHat wohl kaum ein Patent auf einen der Algorithmen angemeldet welche in der von mir zitierten Ringbuffer Datenstruktur zur Anwendung kommt.

brauchst nicht zu bezweifeln, das ist schon seit jahrzehnten die realitaet.
RedHats patentierter ringbuffer ist fuer generische dinge, er ist abgesichert wenn mehrere feeder und consumer vorhanden sind. dabei musst du logischerweise synchronisieren.
das hat aber nichts mit diesem fall hier zu tun.

[rapso]

Algorithmiker schrieb:

Algorithmiker schrieb:

rapso schrieb:

;fricky schrieb:

rapso schrieb:

das einfachste waere ein ringbuffer, das waere nicht nur lockfree, sondern auch waitfree.

aber nicht normalerweise, nur spezielle konstruktionen.

doch, normalerweise ist das der fall. man muss sich schon muehe geben sowas simples kaputt zu implementieren.

Das bezweifel ich, sonst hätte RedHat wohl kaum ein Patent auf einen der Algorithmen angemeldet welche in der von mir zitierten Ringbuffer Datenstruktur zur Anwendung kommt.

P.S. Ich bezweifel das nicht nur deswegen, aber schaut euch einfach mal den von mir verlinkten Artikel an, dann wird die Problematik schon klar (der Artikel verweist übrigens auf ein Dokument des Autors, da findet ihr schöne Grafiken die die Problemsituationen illustrieren).

dein link? wo?

[hustbaer]

rapso schrieb:

hustbaer schrieb:

glaubt ihr dass der OP auch nur den funken einer chance hat, eure tollen lock-free ring-buffer hier zu verstehen, oder gar fehlerfrei zu implementieren?

ein ringbuffer der nur einen feeder und nur einen consumer hat ist in den allermeisten implementierungen lock-/waitfree. da muss man nichts an hyper funky dingen imlementieren.

ja wennst glaubst.
gibt ja auch keine CPUs die load-/store-reordering machen, oder wo man selbst für cache coherency sorgen muss. sowas wie memory-barriers ist eh überbewertet.

mal davon abgesehen dass es IMO total plem ist mit lock-free algorithmen auf was draufzuhauen was IO-limitiert ist.

er sagte der IO thread ist sehr viel schneller.

sorry, mein fehler.

allerdings... wenn der IO thread schon schneller ist als der "verarbeitung-thread", dann hat es erst recht keinen sinn, irgendwelche schwer zu implementierenden optimierungen einzubauen, da man sie nicht spüren wird.

weiter hat lockfree und IO limitierung nichts miteinander zu tun.

ansichtssache. ich denke mir halt: wenn ich IO limitiert bin, dann werde ich mir keinen haxen aussreissen, um den CPU intensiven teil noch weiter zu beschleunigen.

eine stinknormale queue, sowas in der art wie C0de4Fun gepostet hat, ist hier sicher das beste.

ja, wenn man spatzen mit raketenwerfen ausschalten will.

nein. es ist das beste, wenn man mit wenig aufwand ein korrektes programm schreiben will. das nicht anfängt mist zu bauen, wenn es mal auf nem MIPS/PPC/... läuft. oder eben unnötig kompliziert ist.

[;fricky]

rapso schrieb:

;fricky schrieb:

rapso schrieb:

das einfachste waere ein ringbuffer, das waere nicht nur lockfree, sondern auch waitfree.

aber nicht normalerweise, nur spezielle konstruktionen.

doch, normalerweise ist das der fall.

nee, weil die schreibfunktion mal kurz auf lesezeiger und die lesefunktion auf den schreibzeiger zugreifen muss.

rapso schrieb:

Jetzt ist der Thread 1 sehr viel schneller als der Thread 2.

in dem fall solltest du dir ueberlegen, ob du nicht lieber beide threads die dateien verarbeiten laesst, ansonsten ist das langsammer als es sein koennte.

oder nur einen thread nehmen, der suchen und verarbeiten nacheinander macht.

einen thread zu nutzen statt die arbeit auf zwei aufzuteilen soll welchen vorteil genau bringen?
[/quote]
z.b. hätte der OP dann diese frage garnicht stellen brauchen. möglicherweise bringt multithreading in seinem fall überhaupt nix, könnte sogar langsamer sein.

[rapso]

hustbaer schrieb:

rapso schrieb:

hustbaer schrieb:

glaubt ihr dass der OP auch nur den funken einer chance hat, eure tollen lock-free ring-buffer hier zu verstehen, oder gar fehlerfrei zu implementieren?

ein ringbuffer der nur einen feeder und nur einen consumer hat ist in den allermeisten implementierungen lock-/waitfree. da muss man nichts an hyper funky dingen imlementieren.

ja wennst glaubst.
gibt ja auch keine CPUs die load-/store-reordering machen, oder wo man selbst für cache coherency sorgen muss. sowas wie memory-barriers ist eh überbewertet.

ja, das ist komplett irrelevant bei nem simplen ringbuffer. entweder es steht 0 drinnen, und dann kann der feeder was einfuegen, oder es steht ein ptr drinnen, dann kann der consumer 0 einfuegen. das ist dermassen primitiv. eine memory barrier brauchst du nur wenn du zwei writes hast die zueinander eine abhaengige reihenfolge haben, das gibt es hier nicht, weder im fall vom feeder, noch writer.

mal davon abgesehen dass es IMO total plem ist mit lock-free algorithmen auf was draufzuhauen was IO-limitiert ist.

er sagte der IO thread ist sehr viel schneller.

sorry, mein fehler.

allerdings... wenn der IO thread schon schneller ist als der "verarbeitung-thread", dann hat es erst recht keinen sinn, irgendwelche schwer zu implementierenden optimierungen einzubauen, da man sie nicht spüren wird.

deswegen schlug ich ja diese simple vor. etwas als zwischenbuffer damit beide asynchron laufen braucht man, denn es wuerde ja keinen sinn machen zwei threads zu haben wenn der eine darauf warten wuerde dem anderen einen wert zu uebergeben.

weiter hat lockfree und IO limitierung nichts miteinander zu tun.

ansichtssache. ich denke mir halt: wenn ich IO limitiert bin, dann werde ich mir keinen haxen aussreissen, um den CPU intensiven teil noch weiter zu beschleunigen.

das ist nicht wirklich IO relevant, denn wann auch immer das verhaeltniss von "arbeit" zu "sync" sich in richtung "arbeit" shiften, macht es weniger sinn den sync zu optimieren. da wuerde ich mir als auch keine arbeit machen.
jedoch, wenn man kommunizieren will, muss man sich schon gedanken machen wie es sicher ist.
von daher wuerde ich etwas waehlen was so trivial ist, dass man keine arbeit in sync investieren muss, weil es per definition sicher ist.
mein tipp mit ringbuffer war also nicht als optimierung gedacht fuer die laufzeit, sondern implementierungszeit.

eine stinknormale queue, sowas in der art wie C0de4Fun gepostet hat, ist hier sicher das beste.

ja, wenn man spatzen mit raketenwerfen ausschalten will.

nein. es ist das beste, wenn man mit wenig aufwand ein korrektes programm schreiben will.

das ist deine meinung. ich hab meine 2cent dazu gegeben.
steht dem threadstarter frei selbst zu entscheiden was er machen moechte.

[rapso]

;fricky schrieb:

rapso schrieb:

;fricky schrieb:

rapso schrieb:

das einfachste waere ein ringbuffer, das waere nicht nur lockfree, sondern auch waitfree.

aber nicht normalerweise, nur spezielle konstruktionen.

doch, normalerweise ist das der fall.

nee, weil die schreibfunktion mal kurz auf lesezeiger und die lesefunktion auf den schreibzeiger zugreifen muss.

wozu?

rapso schrieb:

Jetzt ist der Thread 1 sehr viel schneller als der Thread 2.

in dem fall solltest du dir ueberlegen, ob du nicht lieber beide threads die dateien verarbeiten laesst, ansonsten ist das langsammer als es sein koennte.

oder nur einen thread nehmen, der suchen und verarbeiten nacheinander macht.

einen thread zu nutzen statt die arbeit auf zwei aufzuteilen soll welchen vorteil genau bringen?

z.b. hätte der OP dann diese frage garnicht stellen brauchen. möglicherweise bringt multithreading in seinem fall überhaupt nix, könnte sogar langsamer sein.
:)[/quote]es koennte auch sein dass er im debug baut
ja, wenn ich sowas annehmen wuerde, wuerde ich den thread meiden

[;fricky]

rapso schrieb:

;fricky schrieb:

rapso schrieb:

;fricky schrieb:

rapso schrieb:

das einfachste waere ein ringbuffer, das waere nicht nur lockfree, sondern auch waitfree.

aber nicht normalerweise, nur spezielle konstruktionen.

doch, normalerweise ist das der fall.

nee, weil die schreibfunktion mal kurz auf lesezeiger und die lesefunktion auf den schreibzeiger zugreifen muss.

wozu?

die schreibfunktion muss wissen, ob im buffer platz ist und die lesefunktion muss wissen, ob im buffer daten sind.

rapso schrieb:

ja, das ist komplett irrelevant bei nem simplen ringbuffer. entweder es steht 0 drinnen, und dann kann der feeder was einfuegen, oder es steht ein ptr drinnen, dann kann der consumer 0 einfuegen. das ist dermassen primitiv.

darf man fragen, was du unter einem 'simplen ringbuffer' verstehst?

[hustbaer]

rapso schrieb:

hustbaer schrieb:

rapso schrieb:

hustbaer schrieb:

glaubt ihr dass der OP auch nur den funken einer chance hat, eure tollen lock-free ring-buffer hier zu verstehen, oder gar fehlerfrei zu implementieren?

ein ringbuffer der nur einen feeder und nur einen consumer hat ist in den allermeisten implementierungen lock-/waitfree. da muss man nichts an hyper funky dingen imlementieren.

ja wennst glaubst.
gibt ja auch keine CPUs die load-/store-reordering machen, oder wo man selbst für cache coherency sorgen muss. sowas wie memory-barriers ist eh überbewertet.

ja, das ist komplett irrelevant bei nem simplen ringbuffer. entweder es steht 0 drinnen, und dann kann der feeder was einfuegen, oder es steht ein ptr drinnen, dann kann der consumer 0 einfuegen. das ist dermassen primitiv. eine memory barrier brauchst du nur wenn du zwei writes hast die zueinander eine abhaengige reihenfolge haben, das gibt es hier nicht, weder im fall vom feeder, noch writer.

es ist eben nicht irrelevant, da es immer abhängigkeiten gibt.
der "producer" muss sicherstellen, dass das, was er produziert hat, für den "consumer" auch sichtbar ist, bevor er anfängt es zu konsumieren.

beispiel:

int* buffer_ptr = 0; // der auf einen zeiger reduzierte ring-buffer

void produce()
{
    int* value_ptr = get_value_buffer();
    *value_ptr = 123; // (1) wert schreiben

    // HIER fehlt eine barrier

    // warten bis platz im buffer ist
    while (buffer_ptr != 0)
        wait();

    buffer_ptr = value_ptr; // (2) zeiger schreiben
}

void consume()
{
   // warten bis es was zu konsumieren gibt
   while (buffer_ptr == 0) // (3.1)
        wait();

   int* value_ptr = buffer_ptr; // (3.2) zeiger lesen
   buffer_ptr = 0; // platz im buffer machen

   // HIER fehlt auch eine barrier

   int value = *value_ptr; // (4) wert lesen
   release_value_buffer(value_ptr);

   // irgendwas mit "value" machen
}

hier haben wir 2 interessante stores und 2 (bzw. 3) interessante loads.

angenommen (2) wird für den "consumer" vor (1) sichtbar, dann wird der "consumer" bei (3) den neuen zeiger lesen, aber bei (4) einen alten wert lesen.

-> fehler

mal davon abgesehen dass es IMO total plem ist mit lock-free algorithmen auf was draufzuhauen was IO-limitiert ist.

er sagte der IO thread ist sehr viel schneller.

sorry, mein fehler.

allerdings... wenn der IO thread schon schneller ist als der "verarbeitung-thread", dann hat es erst recht keinen sinn, irgendwelche schwer zu implementierenden optimierungen einzubauen, da man sie nicht spüren wird.

deswegen schlug ich ja diese simple vor. etwas als zwischenbuffer damit beide asynchron laufen braucht man, denn es wuerde ja keinen sinn machen zwei threads zu haben wenn der eine darauf warten wuerde dem anderen einen wert zu uebergeben.

ja, richtig. eine "stinknormale" über mutexen und condition-variablen implementierte producer-consumer queue würde genau das bewerkstelligen. ohne die diversen fehler, die man so schnell einbaut, wenn man versucht, etwas "einfaches" ohne explizite synchronisierung zu basteln.

weiter hat lockfree und IO limitierung nichts miteinander zu tun.

ansichtssache. ich denke mir halt: wenn ich IO limitiert bin, dann werde ich mir keinen haxen aussreissen, um den CPU intensiven teil noch weiter zu beschleunigen.

das ist nicht wirklich IO relevant, denn wann auch immer das verhaeltniss von "arbeit" zu "sync" sich in richtung "arbeit" shiften, macht es weniger sinn den sync zu optimieren. da wuerde ich mir als auch keine arbeit machen.
jedoch, wenn man kommunizieren will, muss man sich schon gedanken machen wie es sicher ist.

genau. was du vorschlägst ist aber nicht sicher. genau darum geht's mir ja.

von daher wuerde ich etwas waehlen was so trivial ist, dass man keine arbeit in sync investieren muss, weil es per definition sicher ist.

mir wäre nichts bekannt, was gleichzeitig trivial, sync-frei und sicher ist. mal abgesehen von einfachen "kill-flags".

mein tipp mit ringbuffer war also nicht als optimierung gedacht fuer die laufzeit, sondern implementierungszeit.

mein tip war genauso gedacht.

eine stinknormale queue, sowas in der art wie C0de4Fun gepostet hat, ist hier sicher das beste.

ja, wenn man spatzen mit raketenwerfen ausschalten will.

nein. es ist das beste, wenn man mit wenig aufwand ein korrektes programm schreiben will.

das ist deine meinung. ich hab meine 2cent dazu gegeben.
steht dem threadstarter frei selbst zu entscheiden was er machen moechte.

jopp, das ist meine meinung

[hustbaer]

@C0de4Fun:

Deine "RemoveFromQueue" Funktion ist nicht wirklich korrekt.
Du solltest die Queue nicht angreifen, bevor du die CRITICAL_SECTION gelockt hast.
Nichtmal den pQueueFirst Zeiger.

Und was dein Kommentar in GetItemCount angeht: ja, auch hier ist es nötig die CRITICAL_SECTION zu locken.

[hustbaer]

@rapso:
p.S.:
es gibt auch architekturen, auf denen ein zeiger nicht "atomar" geschrieben oder gelesen werden kann.
wenn man kein alignment erzwingt, gehört auch x86 zu diesen architekturen.

und sobald man davon ausgeht dass das lesen/schreiben eines zeigers nicht atomar sein könnte, muss man sowieso synchronisieren.

[Kenner des Problems]

Ohne einem atomaren Zeigerswap geht es nicht.
Wenn man solch einen hat, ich nenne diesen Befehl einfach mal pswap(a,b) dann kann man das so machen (in allen Threads):

void *globaler_buffer;

// Für lesende Threads
void thread_func()
{
   void *p = NULL;
   // Für Lesethreads
   do {
       pswap(p, globaler_buffer);
   } while(NULL == p);

   // Jetzt haben wir exklusiven Zugriff auf die Daten und verarbeiten sie
}
   // Für schreibende threads
void thread_writeer()
{
   void *p = malloc(sizeof(daten_struct));
   // erstelle Daten

   do {
     pswap(p, globaler_buffer);
   } while(NULL != p);

   // jetzt sind alte Daten verarbeitet und die neuen in globaler_puffer
}

[;fricky]

Kenner des Problems schrieb:

Ohne einem atomaren Zeigerswap geht es nicht.

doch, z.b. sowas geht noch: http://en.wikipedia.org/wiki/Peterson's_algorithm

Kenner des Problems schrieb:

void *globaler_buffer;

// Für lesende Threads
void thread_func()
{
   void *p = NULL;
   // Für Lesethreads
   do {
       pswap(p, globaler_buffer);
   } while(NULL == p);

   // Jetzt haben wir exklusiven Zugriff auf die Daten und verarbeiten sie
}
   // Für schreibende threads
void thread_writeer()
{
   void *p = malloc(sizeof(daten_struct));
   // erstelle Daten

   do {
     pswap(p, globaler_buffer);
   } while(NULL != p);

   // jetzt sind alte Daten verarbeitet und die neuen in globaler_puffer
}

aber 'spinlocks' sind auch nicht so toll, ausser du kannst garantieren, dass die sehr schnell verlassen werden (und das kannste bei dem code nicht. wenn der buffer leer ist, idled sich der lesethread 'nen wolf und die CPU läuft heiss).

[Kenner des Problems]

;fricky schrieb:

Kenner des Problems schrieb:

Ohne einem atomaren Zeigerswap geht es nicht.

doch, z.b. sowas geht noch: http://en.wikipedia.org/wiki/Peterson's_algorithm

Kenner des Problems schrieb:

void *globaler_buffer;

// Für lesende Threads
void thread_func()
{
   void *p = NULL;
   // Für Lesethreads
   do {
       pswap(p, globaler_buffer);
   } while(NULL == p);

   // Jetzt haben wir exklusiven Zugriff auf die Daten und verarbeiten sie
}
   // Für schreibende threads
void thread_writeer()
{
   void *p = malloc(sizeof(daten_struct));
   // erstelle Daten

   do {
     pswap(p, globaler_buffer);
   } while(NULL != p);

   // jetzt sind alte Daten verarbeitet und die neuen in globaler_puffer
}

aber 'spinlocks' sind auch nicht so toll, ausser du kannst garantieren, dass die sehr schnell verlassen werden (und das kannste bei dem code nicht. wenn der buffer leer ist, idled sich der lesethread 'nen wolf und die CPU läuft heiss).

Der Einwand ist doch sinnlos, wenn man mit Wartezeiten rechnet, dann benutzt man doch ganz andere Synchronisationsmechanismen. Alternativ kann man das auch so modifizieren, dass der Thread nach einer gewissen Wartezeit schlafen geht.

[;fricky]

Kenner des Problems schrieb:

Der Einwand ist doch sinnlos...

wir sind sowieso längst vom thema abgekommen.

[harumaro]

secondsun schrieb:

ich habe ein kleines Problem.Ich habe 2 Threads mit CreateThread instanziert.
Thread 1: Sucht bestimmte Dateien auf einem Medium
Thread 2: Verarbeitet die bestimmten Dateien

Jetzt ist der Thread 1 sehr viel schneller als der Thread 2. Wie erreiche ich es, dass eine Art "Leitung" gelegt wird? Also Thread 1 schreibt durchgehend alles in einen Queue und Thread 2 holt sich die Daten aus dem Queue heraus und verarbeitet sie.

Die Aufteilung der Threads ist dann aber nicht sehr sinnvoll. Thread 1 ist dann z.B. nach 1 Minute mit suchen fertig und Thread 2 muss noch 10 Minuten verarbeiten.

Wenn die Threads hauptsächlich auf die Platte zugreifen machst du es wahrscheinlich nur langsamer als schneller, wenn immer wieder von anderen Stellen gelesen wird.

[hustbaer]

Kenner des Problems schrieb:

Ohne einem atomaren Zeigerswap geht es nicht.
Wenn man solch einen hat, ich nenne diesen Befehl einfach mal pswap(a,b) dann kann man das so machen (in allen Threads):

wenn man nur einen producer und nur einen consumer hat, dann reichen atomare lese- und schreiboperationen + barriers.

wenn man mehrere producer und/oder consumer hat, dann braucht man einen atomaren swap (mehrere consumer), oder sogar einen atomaren compare-and-swap. und barriers. ohne barriers geht schonmal nix. (ein atomarer swap/compare-and-swap ist meist auch eine full-barrier, aber nicht unbedingt auf jedem system.)

[C0de4Fun]

Hi,

hustbaer schrieb:

@C0de4Fun:

Deine "RemoveFromQueue" Funktion ist nicht wirklich korrekt.
Du solltest die Queue nicht angreifen, bevor du die CRITICAL_SECTION gelockt hast.
Nichtmal den pQueueFirst Zeiger.

also dann quasi so:

...
void* RemoveFromQueue(PQUEUE pQueue)
{
    PQUEUE_ITEM pTmp;
    void* pTmpContent = NULL;

    EnterCriticalSection(&pQueue->CritSection);

    pTmp = pQueue->pQueueFirst;

    if(pTmp)
    {

        if(pQueue->pQueueFirst == pQueue->pQueueLast)
        {
            pQueue->pQueueFirst = NULL;
            pQueue->pQueueLast = NULL;
        }
        else
            pQueue->pQueueFirst = pQueue->pQueueFirst->pNext;

        pQueue->uiItems--;

        pTmpContent = pTmp->pContent;
        free(pTmp);

    }

    LeaveCriticalSection(&pQueue->CritSection);

    return pTmpContent;
}
....

Danke war mir nicht bewusst, ist aber eig klar weil ja die Add Func pQueue->pQueueFirst veraendern koennte.

hustbaer schrieb:

Und was dein Kommentar in GetItemCount angeht: ja, auch hier ist es nötig die CRITICAL_SECTION zu locken.

Danke auch fuer diese Antwort ;).

Peace C0de4Fun

[hustbaer]

Das sieht schon besser aus, ja

[Blue-Tiger]

Zwar ein bisschen Offtopic, aber: habt ihr irgendwelche Literaturempfehlungen fuer Lockfree-Datenstrukturen?

[;fricky]

Blue-Tiger schrieb:

Zwar ein bisschen Offtopic, aber: habt ihr irgendwelche Literaturempfehlungen fuer Lockfree-Datenstrukturen?

internet: http://www.pdf-search-engine.com/lock-free-pdf.html