151 votes

En quoi le cadre fourche/join mieux qu’un pool de threads ?

Quels sont les avantages de l'utilisation de la nouvelle fork/join cadre plus simplement, le fractionnement de la tâche, en N sous-tâches dans le début, de les envoyer à une mise en cache du pool de threads (à partir de Exécuteurs) et d'attente pour chaque tâche à accomplir? Je ne vois pas comment à l'aide de la fork/join abstraction simplifie le problème ou rend la solution plus efficace à partir de ce que nous avons eu depuis des années maintenant.

Par exemple, le parallélisée flou de l'algorithme dans le tutoriel exemple pourrait être mis en œuvre comme ceci:

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

Split, dans le début et d'envoyer des tâches à un pool de threads:

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

Les tâches aller pour le pool de threads de la file d'attente, à partir de laquelle ils sont exécutés comme des threads de travail deviennent disponibles. Tant que le fractionnement est granulaire assez (pour éviter d'avoir à en particulier d'attendre la dernière tâche) et le pool de threads a suffisamment (au moins N de processeurs) threads, tous les processeurs sont à fonctionner à pleine vitesse jusqu'à ce que le calcul est fait.

Ai-je raté quelque chose? Quelle est la valeur ajoutée de l'utilisation de la fork/join?

148voto

A.H. Points 23369

Je pense que la base de l'incompréhension, c'est que le Fork/Join exemples ne PAS montrer le travail de voler , mais seulement une sorte de standard de diviser pour régner.

Le travail de voler serait comme ceci: Travailleur B a terminé son travail. Il est un genre, c'est pourquoi il regarde autour de lui et voit Un Travailleur travaille toujours très dur. Il promenades et demande: "Hé les gars, je pourrais vous donner un coup de main." Une des réponses. "Cool, j'ai cette tâche de 1000 unités. Jusqu'à présent j'ai fini 345 laissant 655. Pourriez-vous s'il vous plaît sur le nombre de 673 à 1000, je vais faire de la 346 à 672." B dit "OK, nous allons commencer afin que nous puissions aller au pub plus tôt."

Vous voyez - les travailleurs doivent communiquer entre eux, même quand ils ont commencé le travail réel. C'est la partie manquante dans les exemples.

Les exemples de l'autre montrent seulement quelque chose comme "utiliser des sous-traitants":

Travailleur: "Dang, j'ai 1000 unités de travail. Trop pour moi. Je vais faire 500 moi-même et de sous-traitance de 500 à quelqu'un d'autre." Cela va jusqu'à la grande tâche est décomposée en petits paquets de 10 unités chacun. Elles seront exécutées par les travailleurs disponibles. Mais si un paquet est une sorte de poison et prend beaucoup plus de temps que d'autres paquets -- la malchance, la fracture de la phase est terminée.

La seule différence entre Fork/Join et le fractionnement de la tâche d'avance est ce: Quand la division dès le début, vous avez la file d'attente de travail de plein droit depuis le début. Exemple: 1000 unités, le seuil est de 10, de sorte que la file d'attente a 100 entrées. Ces paquets sont distribués à le pool de threads membres.

Fork/Join est plus complexe et essaie de garder le nombre de paquets dans la file d'attente de plus petits:

  • Étape 1: Mettre un sachet contenant (1...1000) dans la file d'attente
  • Étape 2: Un travailleur pop le paquet(1...1000) et la remplace par deux paquets: (1...500) et (501 et 1000).
  • Étape 3: Un ouvrier pop paquet (500...1000) et pousse (500...750) et (751...1000).
  • Étape n: La pile contient ces paquets: (1..500), (500...750), (750...875)... (991..1000)
  • Étape n+1: Paquet (991..1000) est sauté et exécuté
  • Étape n+2: Paquet (981..990) est sauté et exécuté
  • Étape n+3: Paquet (961..980) est sauté et divisé en (961...970) et (971..980). ....

Vous voyez: la Fourche/Rejoignez la file d'attente est plus petit (6 dans l'exemple) et le "split" et "travail" phases sont entrelacées.

Lorsque plusieurs travailleurs sont popping et poussant simultanément les interactions ne sont pas si claires, bien sûr.

28voto

Si vous n ont occupé tous les threads de travail de suite à 100%, indépendamment, ça va être mieux que les n threads dans un Fork-Join (FJ) de la piscine. Mais ça ne fonctionne jamais de cette façon.

Il pourrait ne pas être capable de diviser le problème en n parties égales. Même si vous le faites, la planification de thread est assez loin d'être juste. Vous obtiendrez d'attente pour le plus lent fil. Si vous avez plusieurs tâches, puis ils peuvent chaque course avec moins de n-way parallélisme (généralement plus efficace), mais aller jusqu'à n-autres tâches ont fini.

Alors, pourquoi ne pas simplement couper le problème en FJ-morceaux de la taille et de disposer d'un pool de threads de travail. Typique FJ utilisation coupes le problème en petits morceaux. Faire ces dans un ordre aléatoire nécessite beaucoup de coordination au niveau matériel. Les frais généraux serait un tueur. Dans FJ, les tâches sont mises sur une liste d'attente qui le thread lit en Last In First Out commande (LIFO/pile), et le travail de voler (dans les travaux de base, en général) est de faire en Premier entré Premier Sorti (FIFO/"file d'attente"). Le résultat est que le tableau de traitement peut être fait en grande partie de manière séquentielle, même si il est cassé en petits morceaux. (C'est aussi le cas, il pourrait ne pas être facile à diviser le problème en petits morceaux de taille égale dans un big bang. Dire de traiter avec une certaine forme de hiérarchie sans équilibrage.)

Conclusion: FJ permet une utilisation plus efficace du matériel de threads dans une inégale des situations, qui sera toujours, si vous avez plus d'un thread.

21voto

Matthew Farwell Points 31257

Fork/join est différente à partir d'un pool de threads parce qu'il met en œuvre les travaux de voler. De Fork/Join

Comme avec n'importe quel ExecutorService, le fork/join cadre distribue les tâches pour les threads de travail dans un pool de threads. Le fork/join cadre est distinctes, car il utilise un vol de travail de l'algorithme. Les threads de travail qui court de choses à faire peuvent voler des tâches à partir d'autres threads sont encore occupés.

Disons que vous avez deux fils et 4 tâches a, b, c, d qui prennent 1, 1, 5 et 6 secondes. D'abord, a et b sont affectés à fil 1 et c et d pour le thread 2. Dans un pool de threads, ce serait prendre 11 secondes. Avec fork/join, le thread 1 finitions et peut voler de travail à partir du fil 2, de sorte que la tâche d finirait par être exécuté par le thread 1. 1 Thread exécute a, b et d, le thread 2 c seulement. Temps total: 8 secondes, pas 11.

EDIT: Comme Joonas points, les tâches ne sont pas nécessairement pré-affectés à un fil. L'idée de fork/join est qu'un thread peut choisir de diviser une tâche en plusieurs sous-pièces. Donc pour redire la-dessus:

Nous avons deux tâches (ab) et (cd) qui prennent 2 et 11 secondes, respectivement. 1 Thread commence à s'exécuter ab et de le diviser en deux sous-tâches a et b. De la même façon avec filetage 2, il se divise en deux sous-tâches c et d. Lorsque le thread 1 a fini de a et de b, il peut voler de d à partir de fil 2.

14voto

iain Points 4876

Tout le monde ci-dessus est correcte, les avantages sont obtenus par le travail de voler, mais à l'étendre sur les raisons de cette.

L'avantage principal est la coordination efficace entre les threads. Le travail doit être fractionnée et remonté, ce qui nécessite une coordination. Comme vous pouvez le voir dans A. H de la réponse ci-dessus, chaque thread possède sa propre liste de travail. Une propriété importante de cette liste est qu'elle est triée (les grandes tâches en haut et les petites tâches au bas de la page). Chaque thread exécute les tâches en bas de sa liste, et vole des tâches à partir du dessus des autres threads listes.

Le résultat de ceci est:

  • La tête et la queue de la liste des tâches peut le synchronisée de manière indépendante, la réduction de la contention sur la liste.
  • D'importants sous-arbres du travail sont séparés et remonté par le même thread, donc pas de inter fil de coordination est nécessaire pour ces sous-arbres.
  • Lorsqu'un thread vole le travail qu'il faut un gros morceau qu'il subdivise sur sa propre liste
  • Le travail de l'affûter signifie que les fils sont presque entièrement utilisée jusqu'à la fin du processus.

La plupart des autres diviser et conquérir systèmes utilisant des pools de threads nécessitent plus de communication inter-thread et de la coordination.

14voto

volley Points 3229

Dans cet exemple Fork/Join n'ajoute pas de valeur parce que la fourche n'est pas nécessaire et la charge de travail est réparti également entre les threads de travail. Fork/Join seulement ajoute de la surcharge.

Voici un bel article sur le sujet. Citation:

Dans l'ensemble, on peut dire que le ThreadPoolExecutor est à privilégier où la charge de travail est réparti également entre les threads de travail. Pour être en mesure afin de garantir cela, vous avez besoin de savoir précisément ce que les données d'entrée ressemble. En revanche, la ForkJoinPool fournit de bonnes performances indépendamment de l'entrée de données et est donc beaucoup plus robuste solution.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X