タスクスケジューラは、実行時にタスクをスケジュールし調整します。タスクとは、特定のジョブを実行する作業の単位です。タスクスケジューラは、複数の計算リソースを持つコンピュータ上でタスクを効率的にスケジュールするための詳細を処理します。
Windows OSは、プリエンプティブなカーネルモードスケジューラを提供しています。これは、ラウンドロビン方式の優先度ベースのメカニズムで、すべてのタスクに一定期間の計算リソースへの排他的アクセスを与え、その後別のタスクに切り替えます。このメカニズムは公平性を提供しますが（すべてのスレッドが前進する）、効率の面でコストがかかります。例えば、多くの計算集約型アルゴリズムは公平性を必要としません。代わりに、関連するタスクが可能な限り短い全体時間で完了することの方が重要です。協調スケジューリングにより、アプリケーションはより効率的に作業をスケジュールできます。
協調スケジューリングとは、タスクが完了するまで、またはタスクがリソースへのアクセスを明け渡すまで、すべてのタスクに計算リソースへの排他的アクセスを与えるメカニズムです。
ユーザーモード協調スケジューラにより、アプリケーションコードは独自のスケジューリング決定を行うことができます。協調スケジューリングにより、多くのスケジューリング決定をアプリケーションが行えるため、カーネルモード同期に伴うオーバーヘッドの多くが削減されます。
同時実行ランタイム（Concurrency Runtime）は、協調スケジューリングとオペレーティングシステムのプリエンプティブスケジューラを組み合わせて使用し、処理リソースの最大限の活用を実現します。
スケジューラの設計
同時実行ランタイムは、アプリケーションのニーズに適応した特定のスケジューラを実装するためのSchedulerインターフェースを提供します。
このインターフェースを実装しているクラスを見てみましょう。そのために、次のCQLクエリを実行できます。
同時実行ランタイムは、スケジューラの2つの実装を提供しています。ThreadSchedulerとUMSThreadSchedulerです。
次の依存関係グラフが示すように、スケジューラは目標を達成するために多くの抽象クラスを参照しています。
スケジューラが使用する各抽象クラスの役割を見てみましょう。そのために、その責務について説明します。
タスクスケジューラには3つの主要な責務が割り当てられています。
1. リソース（プロセッサ、コア、メモリ）の取得：
スケジューラが作成されると、ランタイムリソースマネージャーにリソースを要求します。詳しくはこの 記事をご覧ください。
スケジューラは、IResourceManager、ISchedulerProxy、ISchedulerインターフェースを使用してリソースマネージャーと通信します。スケジューラを作成するときに、そのポリシーを指定できます。
Concurrency::PolicyElementKey列挙型は、タスクスケジューラに関連付けられたポリシーキーを定義しています。
こちらに 記事 があります。各ポリシーキーの目的とそれぞれのデフォルト値を説明しています。
これは、スケジューラを作成するときに何が起こるかを示す依存関係グラフです。
同時実行ランタイムは、スケジューラが存在しない場合、GetDefaultSchedulerメソッドを呼び出してデフォルトスケジューラを作成し、デフォルトポリシーが使用されます。タスクスケジューラにより、アプリケーションは1つ以上のスケジューラインスタンスを使用して作業をスケジュールでき、アプリケーションはScheduler::Createを呼び出して、特定のポリシーを使用する別のスケジューラを追加できます。
スケジューラとリソースマネージャー間の次の相互作用は、リソース割り当てに関与する各インターフェースの役割を示しています。
- リソース割り当ての要求：
- リソースマネージャーからのリソースの取得：
2. タスクキューの管理：
スケジューラが作成されると、タスクを実行のために割り当てることができます。スケジューラはこれらのタスクをキューに格納します。クラスの凝集性を強制するために、キューはThreadSchedulerクラスではなくScheduleGroupBaseクラスによって直接管理されます。
スケジュールグループは、関連するタスクを関連付けたり、グループ化したりします。すべてのスケジューラには1つ以上のスケジュールグループがあります。例えば、関連するタスクのグループが同じプロセッサノードで実行することで利益を得る場合など、タスク間で高度な局所性が必要な場合にスケジュールグループを使用します。
次のグラフが示すように、ランタイムは2種類のScheduleGroupを提供しています。FairScheduleGroupとCacheLocalScheduleGroupです。後で説明するように、これら2つのグループの選択は、スケジューラが次に実行するタスクを選択するために使用するアルゴリズムに影響します。
すべての スケジューラ は、すべてのスケジューリングノードにデフォルトのスケジュールグループを持っています。ランタイムは、すべてのプロセッサパッケージまたはNUMA（Non-Uniform Memory Architecture）ノードに対して1つのスケジューリングノードを作成します。タスクをスケジュールグループに明示的に関連付けない場合、スケジューラがタスクを追加するグループを選択します。
次の依存関係グラフが示すように、SchedulingRingはスケジュールグループの管理を担当します。グループのリストを保持し、それらを作成します。
スケジュールグループには3種類のキューが含まれています。
1. FIFOキュー
このキューには軽量タスクが含まれています。軽量タスクは、Windows APIのCreateThread関数に提供する関数に似ています。したがって、軽量タスクは、既存のコードを同時実行ランタイムのスケジューリング機能を使用するように適応させる場合に便利です。
軽量タスクはRealizedChoreクラスで表され、スケジュールグループのFIFOキューはm_realizedChoresフィールドで表されます。
このキューを直接使用するメソッドを検索してみましょう。
つまり、ScheduleGroupBase::ScheduleTaskまたはScheduler::ScheduleTaskを呼び出すことで、グループに軽量タスクを追加できます。
軽量タスクに関する興味深い 記事 はこちらです。
2. ワークスティーリングキュー：
スケジュールグループに関連付けられたFIFOキューは1つだけですが、スケジュールグループはワークスティーリングキューのリストを参照しています。各ワーカースレッドには独自のローカルキューがあります。
スケジューラにアタッチされたスレッドは実行コンテキスト、または単にコンテキストと呼ばれるため、このローカルキューは実際にはContextクラスに関連付けられています。
Contextクラスは、実行コンテキストのプログラミング抽象化を提供し、現在のコンテキストを協調的にブロック、ブロック解除、イールドする機能を提供します。
Contextのみがこの種のキューを作成することを確認するために、m_workQueuesフィールドに直接アクセスするメソッドを検索してみましょう。
コンテキストがこのキューの作成を担当し、各コンテキストにはローカルのワークスティーリングキューが関連付けられています。
ワークスティーリングアルゴリズムの動作を説明するために、スケジューラに2つのワーカースレッドが割り当てられていると仮定しましょう。
上で説明したように、各ワーカースレッドには独自のローカルキューがあります。
ワーカースレッド1のキューには3つのタスクがあります。タスク3と4は実行待ちで、タスク5は実行中です。
Dispatchメソッドはキューが空であることを検出し、タスク3が元のキューから移動、つまり「盗まれ」、利用可能なワーカースレッドに割り当てられます。
ワークスティーリングキューで管理されるタスクはどのように作成できるでしょうか？それを調べるために、CreateWorkQueueメソッドを間接的に呼び出すメソッドを検索してみましょう。
この依存関係グラフが示すように、この種のタスクはtask_groupクラスを使用して作成できます。
ワークスティーリングアルゴリズムはスケジューラに割り当てられた仮想プロセッサをより有効に活用するため、新しいタスクを追加するには、Scheduler::ScheduleTaskを使用して軽量タスクを作成するよりもtask_groupを使用する方が望ましいです。
ただし、ScheduleTaskは、CreateThread APIを使用する既存のコードを簡単に移行する場合により適しています。
3. ブロック解除されたコンテキストのキュー
The Context クラスを使用すると、現在の実行コンテキストをブロックまたはイールドできます。リソースが利用できないために現在のコンテキストが続行できない場合、ブロックまたはイールドが役立ちます。Context::Blockメソッドは現在のコンテキストをブロックします。ブロックされたコンテキストは、ランタイムが他のタスクを実行できるように、その処理リソースを明け渡します。Context::Unblockメソッドは、ブロックされたコンテキストのブロックを解除します。
コンテキストのブロックが解除され、実行可能になると、実行可能なコンテキストのキューに追加されます。このキューはm_runnableContextsフィールドで表されます。
これは、コンテキストが実行可能キューに追加されるいくつかのケースを示す依存関係グラフです。
つまり、コンテキストは、ブロックが解除されたとき、または仮想プロセッサがスケジューラから退避したときにキューに追加されます。
3. タスクのディスパッチ：
スケジューラは実行する作業を探そうとします。作業は次のものが考えられます。
- ブロック解除されたコンテキスト。
- 軽量タスク。
- ワークスティーリングキュー内のタスク。
上で説明したように、これらすべての作業はスケジュールグループによって管理されるキューに格納され、各グループはスケジューリングリングによって管理されます。
仮想プロセッサがスケジューラに割り当てられると、ThreadProxyクラスが作成されてこのプロセッサに関連付けられ、作成後にThreadProxyのDispatchメソッドが呼び出されます。次の依存関係グラフが示し、前に説明したように、同時実行ランタイムは抽象クラスを使用して低結合を強制しており、実際に呼び出されるディスパッチはランタイムが選択した実装に依存します。この選択はスケジューラポリシーによって決まります。
Dispatchの具象実装は、実行コンテキストのDispatchメソッドを呼び出します。
これは、Context::Dispatchメソッドの具象実装によって呼び出されるメソッドを示す依存関係グラフです。
つまり、次に実行する作業を見つけるアルゴリズムは、WorkSearchContextクラスによって実装されています。
WorkSearchContextがその責務を果たすために直接使用するすべてのクラスを見てみましょう。
WorkSearchContextの責務は、実行するWorkItemを提供することです。これはInternalContextBase、RealizedChore、または_UnrealizedChoreになり得ます。
これらのクラス間のコラボレーションをよりよく理解するために、WorkSearchContextが直接使用するメソッドを検索してみましょう。
つまり、WorkSearchContextはSchedulerBaseメソッドを使用して、SchedulingRingクラスとScheduleGroupクラスを反復処理します。
各ScheduleBaseについて、RunnableContext、RealizedChore、またはUnrealizedChoreを検索します。
WorkSearchContextクラスはVirtualProcessorクラスによって作成され、次の依存関係グラフが示すように、使用されるアルゴリズムはVirtualProcessorの初期化時に指定されます。そのために、スケジューラが使用するスケジューリングアルゴリズムを記述するSchedulingProtocolをスケジューラに要求します。
WorkSearchContextは、Algorithm列挙型の値が渡されることで、使用するアルゴリズムを通知されます。
したがって、このクラスは作業を見つけるための2つのアルゴリズムを実装しています。
- キャッシュローカルアルゴリズム：
このアルゴリズムは、まず現在のスケジュールグループ内で実行可能なコンテキストを探し、次に実現されたチョア、次に未実現のチョアを探します。現在のスケジュールグループに作業がなくなった場合、同じスケジューリングリング内の次のグループを探します。現在のスケジューリングリングの作業を使い果たしたら、次のリングに移ります。
つまり、スケジューラは別のスケジュールグループに移る前に、現在のスケジュールグループ内のタスクの作業を続けることを優先します。
このアルゴリズムはWorkSearchContext::SearchCacheLocalメソッドによって実装されており、この依存関係グラフが示すように、このメソッドは実行可能なコンテキスト、RealizedChore、または_UnrealizedChoreを検索するために他のメソッドを呼び出します。
このアルゴリズムのもう一つの特徴は、ブロック解除されたコンテキストが仮想プロセッサごとにキャッシュされ、通常、それらのブロックを解除した仮想プロセッサによって後入れ先出し（LIFO）の順序でスケジュールされることです。
この動作を確認するために、実行可能なコンテキストを検索するときに呼び出されるメソッドの依存関係グラフを次に示します。
これは、何も指定されない場合にスケジューラが選択するデフォルトのアルゴリズムです。
- フェアアルゴリズム：
この場合、スケジューラは各タスクを実行した後、スケジュールグループをラウンドロビンで巡回することを優先します。ブロック解除されたコンテキストは通常、先入れ先出し（FIFO）方式でスケジュールされます。仮想プロセッサはブロック解除されたコンテキストをキャッシュしません。
このアルゴリズムはWorkSearchContext::SearchFairメソッドによって実装されており、この依存関係グラフが示すように、このメソッドは実行可能なコンテキスト、RealizedChore、または_UnrealizedChoreを検索するために他のメソッドを呼び出します。
