Ein Detail über den Fork-Join-Framework

In Doug Lea Papier "Ein Java-Fork/Join Framework":Ein Detail über den Fork-Join-Framework

http://gee.cs.oswego.edu/dl/papers/fj.pdf

In 2.1 Arbeits-Diebstahl er sagt:

Wenn ein Arbeiter thread stößt auf eine Join-Operation, verarbeitet andere Tasks, falls verfügbar, bis die Zielaufgabe (via isDone) erreicht wurde. Ansonsten laufen alle Aufgaben ohne Blockierung ab.

so kann mir jemand sagen, wo diese speziell „anderen Aufgaben“ kommen aus? Sind sie von den Aufgabenwarteschlangen anderer Arbeitsthreads? Bedeutet das, dass, wenn ein Werksthread auf einen Join-Aufruf stößt, es mit "Stehlen von Aufgaben aus anderen Threads" fortfährt, anstatt "auf andere Aufgaben in seiner eigenen Warteschlange zu überspringen"?

Quelle

2012-04-11 njzhxf

Sie können die Cilk Papiere über Arbeit Diebstahl lesen, wenn Sie mehr Details darüber wollen. Die Java-Version ist nicht identisch mit Leisersons Arbeit, aber ziemlich ähnlich und leiserson beschreibt es genauer. – Voo

Die "anderen Aufgaben" können aus ihrer eigenen Deque kommen, wenn ausstehende Aufgaben, Deques aus anderen Threads oder aus der Übermittlungswarteschlange neuer Anforderungen vorhanden sind.

Die Join() ist eine ziemlich schwierige Prozedur. Es beinhaltet die Aufgabensteuerung, dh die Fähigkeit, Aufgaben zu steuern, wenn sie aktiv sind und auf etwas warten. Dies in einer Anwendung zu tun, funktioniert normalerweise nicht. (Die Betriebssysteme machen das gut und Cilk, JCilk macht es mit einem Compiler/Runtime.) Doug Lea verwendet "Fortsetzungs-Threads", wenn Joins die Worker-Threads zusammenfassen.

Quelle

2012-04-11 13:27:53 edharned

Soweit ich die Art und Weise Deques (Double-Ended-Warteschlangen) verstehen kann, werden nur drei Operationen von einem Deque unterstützt: "Pop", "Push" und "Steal" (oder gestohlen), und alle von ihnen funktionieren nur entweder die Hauptaufgabe oder die Endaufgabe der Warteschlange. Wie überspringt ein Worker-Thread in diesem Fall die Kopfaufgabe (wenn die Kopfaufgabe eine "Join" -Operation findet) und fährt mit "anderen ausstehenden Aufgaben in derselben Warteschlange" fort und kommt später wieder zu der übersprungenen Aufgabe? – njzhxf

Die Oberseite der Deque wird nur von anderen Threads verwendet, um Arbeit zu stehlen. Der untere Teil der Deque wird nur vom aktuellen Thread zum Hinzufügen/Abrufen von Aufgaben verwendet. Wenn der aktuelle Thread abfragt, wird eine Aufgabe entfernt. Wenn diese Task einen Join() ausgibt, sucht der aktuelle Thread oder ein "Fortsetzungsthread" nach Aufgaben am unteren Rand der Deque. Sieh dir den Code an. Es ist unglaublich komplex. Vor allem die vorgeschlagene Java8-Version. – edharned

Jeder Arbeiter-Thread im Fork/Join framework hat eine Arbeitsschlange, die einen Deque realisiert wird.

Jedes Mal, wenn eine neue Aufgabe (oder Teilaufgabe) erstellt wird, wird sie an den Kopf ihrer eigenen Warteschlange übergeben. Wenn eine Task eine Task ausführt und eine Verknüpfung mit einer anderen Aufgabe ausführt, die noch nicht abgeschlossen ist, funktioniert sie intelligent. Der Thread öffnet eine neue Task vom Kopf der Warteschlange und startet die Ausführung von anstatt zu schlafen (um auf die Beendigung einer anderen Aufgabe zu warten). In der Tat, wenn die Warteschlange eines Threads leer ist, dann erscheint der Thread eine Aufgabe aus dem Ende der Warteschlange eines anderen Threads. Dies ist nichts als ein Arbeits-Diebstahl-Algorithmus.

Quelle

2014-04-30 09:55:00 pardeep131085

Ein Detail über den Fork-Join-Framework

Antwort

Verwandte Themen