Fork/Join

概要

ForkJoinモデルは、並列プログラミングの手法の一つで、特に「分割統治 」アルゴリズムを効率的に実行するために設計されています

このモデルの基本的な考え方は、「大きな問題を、解決可能な小さな問題に分割（Fork）し、それらを並列で処理した後、結果を合流（Join）させて最終的な答えを導く」というもの

Fork/Joinモデルは、共有メモリベースの並列モデルの中で最もキャッシュ効率と動的負荷分散に優れた形態です。

一方、アクターモデルやCSPのようなメッセージ駆動型はスケールアウトに強く、Fork/Joinはスケールアップに強い構造

Work-Stealing

従来の並列処理では、1つのキューを全ての作業者（スレッド）が共有していましたが、それだとタスクの取り合い（競合）が発生して非効率でした。

ForkJoinモデルは、これを以下のように解決します。

各スレッドが専用のキューを持つ

自分のタスクは「上」から取る

スレッドは通常、自分のキューの先頭（Head）からタスクを取って実行します。

手が空いたら、他人の「下」から盗む

自分のキューが空になった（手が空いた）スレッドは、他のスレッドのタスクリストの末尾（Tail）からタスクを1つ盗んで（Steal）、それを実行します。

なぜこれが効率的なのか？

競合が減る

各スレッドは基本的に自分のリスト（先頭）しか触らないため、他のスレッドとの競合が最小限になります。

負荷が分散される

自分のキューの末尾（Tail）にあるタスクは、そのスレッドが一番最初に入れた大きなタスクであることが多いです。

それを手が空いたスレッドが盗んで実行することで、大きなタスクが自然に分割され、CPU全体の負荷が均等になります。

CPUを遊びなく使う

全てのスレッドが高い稼働率を維持しようとします。