スケジューリング

この記事は英語の原文を日本語に翻訳したものです。原文: https://blog.stenmans.org/theBeamBook/#CH-Scheduling

翻訳元: happi/theBeamBook 7998e22e78417dbe20e5136b9aee862a1ecaa404（コミット 7998e22）

ERTSがどこで時間を使っているのかを正しく理解するには、どのErlangコードを、いつ実行するのかをシステムがどう決めているのかを理解する必要があります。この決定を行っているのがスケジューラです。

スケジューラは、システムのリアルタイム性を保証する役割を担っています。計算機科学における厳密な意味でのリアルタイムとは、指定された時間内に応答することを保証できるシステムを指します。つまり、実際の締め切りがあり、各タスクはその締め切りより前に完了しなければなりません。 Erlangにはそうした保証はなく、Erlangのタイムアウトが保証しているのは、指定した締め切りより前には発火しない、という点だけです。

Erlangのようにあらゆる種類のプログラムや負荷を扱いたい汎用システムでは、スケジューラも何らかの妥協をせざるを得ません。汎用的なスケジューラがうまく振る舞えないコーナーケースは常に存在します。本章を読み終えれば、Erlangのスケジューラがどのように動作するか、特にどんなときに最適に動作しないかを深く理解できるはずです。コーナーケースを避けるようにシステムを設計できるようになり、挙動のおかしいシステムを分析できるようにもなるでしょう。

並行性・並列性・プリエンプティブなマルチタスク

Erlangは並行言語です。プロセスが並行に動くというとき、外部から見ると2つのプロセスが同時に実行されているように見える、という意味で使っています。シングルコアのシステムでは、これはプリエンプティブなマルチタスクによって実現されます。つまり、あるプロセスがしばらく実行され、その後仮想マシンのスケジューラがそのプロセスを一時停止し、別のプロセスを実行させるということです。

マルチコアや分散システムでは、真の並列性、つまり2つ以上のプロセスがまったく同時に実行されることを実現できます。 SMP対応のエミュレータでは、スレッドごとに1つのスケジューラとエミュレータを走らせることで、複数のOSスレッドを使って間接的にErlangプロセスを実行します。 ERTSのデフォルト設定を使うシステムでは、有効なコア（物理コアまたはハイパースレッディングによる論理コア）1つにつき1スレッドが立ち上がります。

SMPサポートが有効かどうかを確認すれば、システムが並列実行に対応しているかどうかを確かめられます。

iex(1)> :erlang.system_info :smp_support
true

システム内で稼働しているスケジューラの数も確認できます。

iex(2)> :erlang.system_info :schedulers_online
4

この情報は、下図のようにObserverでも確認できます。

スケジューラの数より多くのプロセスをスポーンしてビジーな作業をさせると、並列に**実行中（running）**のプロセスがいくつかある一方で、**実行可能（runnable）**ではあってもまだ実行されていないプロセスもあることがわかります。これは erlang:process_info/2 関数でも確認できます。

1> Loop = fun (0, _) -> ok; (N, F) -> F(N-1, F) end,
   BusyFun = fun() -> spawn(fun () -> Loop(1000000, Loop) end) end,
   SpawnThem = fun(N) -> [ BusyFun() || _ <- lists:seq(1, N)] end,
   GetStatus = fun() -> lists:sort([{erlang:process_info(P, [status]), P}
                        || P <- erlang:processes()]) end,
   RunThem = fun (N) -> SpawnThem(N), GetStatus() end,
   RunThem(8).

[{[{status,garbage_collecting}],<0.62.0>},
 {[{status,garbage_collecting}],<0.66.0>},
 {[{status,runnable}],<0.60.0>},
 {[{status,runnable}],<0.61.0>},
 {[{status,runnable}],<0.63.0>},
 {[{status,runnable}],<0.65.0>},
 {[{status,runnable}],<0.67.0>},
 {[{status,running}],<0.58.0>},
 {[{status,running}],<0.64.0>},
 {[{status,waiting}],<0.0.0>},
 {[{status,waiting}],<0.1.0>},

...

プロセスが取りうる各状態については本章の後半で詳しく見ていきますが、いまのところは、runningまたはgarbage_collectingという状態のプロセスは実際にスケジューラ上で実行されている、ということだけ押さえておけば十分です。この例のマシンは4コア4スケジューラなので、4つのプロセス（シェルプロセスと3つのビジープロセス）が並列に実行されています。さらに5つのビジープロセスがrunnable状態で実行の順番を待っています。

ObserverのLoad Chartsタブを見ると、ビジープロセスが実行されている間、4つのスケジューラすべてがフルロードになっていることがわかります。

2> observer:start().
ok
3> RunThem(8).

Erlang Observerの負荷チャートタブ。4つのスケジューラすべてが100%近くまで埋まっている様子が描かれている。 図: ビジープロセス実行中のObserverの負荷チャート

ERTSにおけるプリエンプティブなマルチタスクとC言語レベルでの協調

Erlangレベルでのプリエンプティブなマルチタスクは、C言語レベルでの協調的マルチタスクによって実現されています。 Erlang言語とコンパイラ、仮想マシンが協力し合うことで、Erlangプロセスの実行が限られた時間内にyieldして次のプロセスに実行を譲ることを保証しています。この実行時間を計測・制限するために使われる技法がリダクションカウントであり、その詳細はこの後すぐに見ていきます。

リダクション

BEAMにおけるスケジューリングは、協調的スケジューリングの上に組み立てられたプリエンプティブなスケジューリングだと説明できます。プロセスが一時停止できるのは実行中の特定のポイント、たとえばreceiveや関数呼び出しの箇所に限られます。その意味でこのスケジューリングは協調的です。プロセスは一時停止を許すコードを実行しなければなりません。 Erlangコードの性質上、関数呼び出しを行わずに長時間動き続けることはほぼ不可能です。ただし、いくつかの組み込み関数（BIF）は、yieldせずに長くかかりすぎることがあります。また、実装の悪いネイティブ実装関数（NIF）でC言語のコードを呼び出すと、1つのスケジューラを長時間ブロックしてしまうことがあります。行儀のよいNIFの書き方はCの章で見ていきます。

再帰とリスト内包表記以外にループの構文が無いため、関数呼び出しをせずに無限ループすることはできません。各関数呼び出しはリダクションとして数えられ、プロセスのリダクション上限に達すると一時停止させられます。

OTP-20.0より前のバージョンでは、CONTEXT_REDSの値は2000でした。

リダクションという用語は、ErlangがProlog系統から受け継いだものです。 Prologでは、各実行ステップがゴール簡約（goal-reduction）であり、論理的な問題をその構成要素へと簡約し、それぞれの部分を解こうとします。

何リダクション分もらえるのか

プロセスがスケジュールされると、erl_vm.h（erl_vm.hで定義。現在の値は4000）で定義されるCONTEXT_REDSの数だけリダクションが与えられます。割り当てられたリダクションを使い切るか、受信箱にマッチするメッセージが無い状態でreceiveを行うと、プロセスは一時停止され、新しいプロセスがスケジュールされます。

VMがINPUT_REDUCTIONS（現在はerl_vm.hで定義されている2*CONTEXT_REDS）で定義された数のリダクションを実行したとき、あるいは実行できるプロセスが無いときは、スケジューラはシステムレベルの作業を行います。これは基本的にはIOのチェックであり、詳細はこの後すぐに扱います。

リダクションとは実際には何か

リダクションが正確に何を指すのかは完全には定義されていませんが、少なくとも各関数呼び出しは1リダクションとして数えられるべきものです。 BIFやNIFの話になると、事情は少し複雑になります。プロセスがリダクションを消費してyieldすることなく「長時間」動き続けるべきではありません。 Cで書かれた関数は途中でyieldできないので、きれいな状態であることを確認してからreturnしなければなりません。再入可能であるためには、returnする前に内部状態を何らかの形で保存し、再度呼ばれたときにその状態を復元する必要があります。これは非常にコストがかかることがあり、特に、あるときはわずかな作業しかせず、あるときは大量の作業を行うような関数では顕著です。 Cで関数を書く理由は、通常は性能を上げることと、不要な記帳作業を省くことにあります。 Erlangレベルでの関数呼び出し以外にリダクションが何であるかの明確な定義が無いため、Cで実装された関数がErlangの通常の関数よりも1リダクションあたり多くのクロック数を消費してしまうリスクがあります。これはスケジューラの不均衡、さらには枯渇（starvation）にまでつながることがあります。

たとえば、R16より前のErlangのバージョンでは、BIFのbinary_to_term/1とterm_to_binary/1はyieldせず、1リダクションとしてしか数えられませんでした。つまり、これらの関数を大きな項に対して呼び出すプロセスが、他のプロセスを枯渇させてしまう可能性があったということです。これはSMPシステムでも起こりえます。プロセスがスケジューラ間でどのように振り分けられるかという理由によるものであり、その仕組みはこの後すぐに扱います。

プロセスが実行されている間、エミュレータは（レジスタにマップされた）変数FCALLS（beam_emu.cを参照）に、あと何リダクション実行できるかを保持しています。

redsフィールドは、そのプロセスが直前に一時停止するまでに行った総リダクション数を記録します。この数値を監視することで、どのプロセスが最も多くの作業をしているかがわかります。

プロセスの総リダクション数（redsフィールド）は、erlang:process_info/2の第2引数にアトムreductionsを渡すことで確認できます。 Observerのプロセスタブや、Erlangシェルのi/0コマンドでもこの数値を確認できます。

先ほど述べたように、プロセスが開始するたびにfcallsフィールドはCONTEXT_REDSの値に設定され、プロセスが関数呼び出しを実行するたびにfcallsは1ずつ減らされます。プロセスが一時停止すると、redsフィールドは実行済みのリダクション数だけ増やされます。おおよそC言語風に書くと p->reds += (CONTEXT_REDS - p->fcalls) のようになります。

通常、プロセスは割り当てられたリダクションをすべて使い切り、この時点でfcallsは0になりますが、メッセージを待つreceiveで一時停止した場合は、リダクションがいくらか残った状態になります。

プロセスがリダクションを使い切ると、別のプロセスを実行させるためにyieldし、プロセス状態は**実行中（running）から実行可能（runnable）**へ遷移します。 receiveの中でyieldした場合は、代わりに（メッセージを待つ）**待機中（waiting）**状態へ遷移します。次の節では、プロセスが取りうるすべての状態を見ていきます。

プロセスの状態（status）

PCB内のstatusフィールドには、プロセスの状態が格納されています。これはfree、runnable、waiting、running、exiting、garbing、suspendedのいずれかです。プロセスが終了すると、freeとしてマークされます。この状態のプロセスを目にすることはまず無いはずです。プロセスがシステムの他の部分からはもはや存在しないものとして扱われつつも、まだ後始末（メモリなどのリソースの解放）が残っている、短命な状態だからです。

各プロセス状態は、プロセス状態機械における1つの状態を表しています。タイムアウトやメッセージの配送などのイベントが、状態機械の辺に沿った遷移を引き起こします。 プロセス状態機械は次のようになっています。

プロセスの状態機械。実行可能・実行中・待機中を中心とした通常の状態遷移に加えて、GCによる実行中とGC中の往復、exitによる終了処理中への遷移、suspend/resumeによる一時停止中との往復を示す。 図: プロセス状態機械

プロセスの通常の状態はrunnable、waiting、runningです。実行中（running）のプロセスは、いずれかのスケジューラでコードを実行している最中のプロセスです。プロセスがreceiveに入り、メッセージキューにマッチするメッセージが無い場合、そのプロセスはメッセージが届くかタイムアウトが発生するまで待機中（waiting）になります。プロセスがリダクションを使い切ると、実行可能（runnable）になり、スケジューラに再び選ばれるのを待ちます。待機中のプロセスは、メッセージを受け取るかタイムアウトが発生すると実行可能になります。

プロセスがガベージコレクションを行う必要があるときは、GCが終わるまでGC中（garbing）状態になります。 GCを行っている間、直前の状態はgcstatusフィールドに保存され、GCが終わるとこのgcstatusを使って元の状態に戻されます。

一時停止（suspended）状態は、デバッグ目的でのみ使われることを想定しています。別のプロセスに対してerlang:suspend_process/2を呼ぶと、そのプロセスを強制的に一時停止状態にできます。あるプロセスが別のプロセスに対してsuspend_processを呼ぶたびに、サスペンドカウントが増加します。これはrcountフィールドに記録されます。一時停止させた側のプロセスがerlang:resume_process/1を呼ぶと、サスペンドカウントは減少します。一時停止状態のプロセスは、サスペンドカウントが0になるまでその状態から抜けません。

rstatus（resume status）フィールドは、一時停止前にそのプロセスがどの状態だったかを記録するために使われます。一時停止前の状態がrunningまたはrunnableであればrunnableとして再開し、waitingであれば待機キューへ戻ります。一時停止中の待機プロセスがタイムアウトを受け取ると、rstatusはrunnableに設定され、runnableとして再開されます。

次にどのプロセスを実行するかを把握するために、スケジューラはプロセスをキューで管理しています。

プロセスキュー

スケジューラの主な仕事は、作業キュー、つまりプロセスとポートのキューを管理することです。

スケジューラが扱わなければならないプロセス状態はrunnableとwaitingの2つです。メッセージの受信を待っているプロセスはwaiting状態にあります。 waiting状態のプロセスがメッセージを受け取ると、送信操作によってそのプロセスはrunnable状態へ移されます。 receive文にタイムアウトが指定されている場合は、タイムアウトが発火したときにスケジューラがrunnableへの状態遷移を引き起こす必要があります。この仕組みは本章の後半で扱います。

実行可能キュー（Ready Queue）

runnable状態のプロセスは、スケジューラが管理するFIFO（先入れ先出し）キュー、実行可能キュー（ready queue）に置かれます。このキューは、先頭・末尾それぞれへのポインタと、参加している各プロセスのPCB内にあるnextポインタによって実装されています。新しいプロセスがキューに追加されるときはlastポインタがたどられ、O(1)の操作でキューの末尾にプロセスが追加されます。新しいプロセスがスケジュールされるときは、キューの先頭（firstポインタ）から単純にポップされます。

 The Ready Queue

 First: -->  P5       +---> P3       +-+-> P17
             next: ---+     next: ---+ |  next: NULL
                                       |
 Last: --------------------------------+

複数のスケジューラスレッドを持つSMPシステムでは、スケジューラごとに1つのキューがあります。

 Scheduler 1       Scheduler 2      Scheduler 3      Scheduler 4

 Ready: P5         Ready: P1        Ready: P7        Ready: P9
        P3                P4               P12
        P17                                P10

実際にはErlangプロセスには優先度があるため、もう少し複雑です。各スケジューラは実際には3つのキューを持ちます。 max priorityタスク用のキューが1つ、high priorityタスク用のキューが1つ、そしてnormalとlow priorityの両方のタスクを収めるキューが1つです。

 Scheduler 1       Scheduler 2      Scheduler 3      Scheduler 4

 Max:    P5        Max:             Max:             Max:
 High:             High:  P1        High:            High:
 Normal: P3        Ready: P4        Ready: P7        Ready: P9
         P17                              P12
                                          P10

maxキューにプロセスが1つでもあれば、スケジューラはこれらのプロセスを実行対象として選びます。 maxキューにプロセスが無く、high priorityキューにプロセスがあれば、スケジューラはそちらを選びます。 maxキューとhigh priorityキューの両方が空の場合に限り、スケジューラはnormalとlowキューから先頭のプロセスを選びます。

normalプロセスがキューに挿入されるときはスケジュールカウント1が、lowプロセスにはスケジュールカウント8が与えられます。プロセスがキューの先頭から取り出されるとき、そのスケジュールカウントが1減らされ、カウントが0に達すればそのプロセスがスケジュールされ、そうでなければキューの末尾に再度挿入されます。つまり、low priorityのプロセスは、スケジュールされるまでにキューを7回通過することになります。

待機・タイムアウト・タイミングホイール

空のメールボックス、あるいはマッチするメッセージの無いメールボックスに対してreceiveを行おうとしたプロセスはyieldし、待機（waiting）状態に入ります。

メッセージが受信箱に配送されると、送信側のプロセスは受信側が待機状態でスリープしていないかを確認し、スリープしていれば受信側プロセスを起こし、その状態をrunnableに変え、対応する実行可能キューの末尾に置きます。

receive文にtimeout節がある場合、指定したタイムアウト時間が経過すると発火するタイマーがそのプロセスのために作成されます。ランタイムシステムがタイムアウトについて保証しているのは、設定した時刻より前には発火しない、という点だけです。プロセスが実際にスケジュールされて実行されるまでには、意図した時刻より多少後になることがあります。

VM内のタイマーはタイミングホイールによって扱われます。タイミングホイールとは、循環する時間スロットの配列のことです。 Erlang 18より前では、タイミングホイールはグローバルな資源であり、多くのプロセスが同時にタイマーをホイールに挿入すると、書き込みロックを巡る競合が発生することがありました。多くのタイマーを使うのであれば、必ず新しめのバージョンのErlangを使うようにしてください。

タイミングホイールのデフォルトサイズ（TIW_SIZE）は65536スロットです（メモリ使用量を切り詰めた構成でビルドした場合は8192スロット）。現在時刻は配列へのインデックス（tiw_pos）で示されます。タイムアウトTを指定してタイマーがホイールに挿入されるとき、そのタイマーは(tiw_pos+T)%TIW_SIZEのスロットに挿入されます。

   0 1                                      65535
  +-+-+- ... +-+-+-+-+-+-+-+-+-+-+-+ ... +-+-----+
  | | |      | | | | | | |t| | | | |     | |     |
  +-+-+- ... +-+-+-+-+-+-+-+-+-+-+-+ ... +-+-----+
              ^           ^                       ^
              |           |                       |
           tiw_pos     tiw_pos+T               TIW_SIZE

タイミングホイールに格納されるタイマーは、ErlTimer構造体へのポインタです（erl_time.hを参照）。複数のタイマーが同じスロットに挿入された場合、prevフィールドとnextフィールドによって連結リストとしてつながれます。 countフィールドにはT/TIW_SIZEが設定されます。

/*
** タイマーエントリ:
*/
typedef struct erl_timer {
    struct erl_timer* next; /* tiwスロットまたはチェーン中の次のエントリ */
    struct erl_timer* prev; /* tiwスロットまたはチェーン中の前のエントリ */
    Uint slot;          /* タイマーホイール中のスロット */
    Uint count;         /* 残りループ回数 */
    int    active;      /* 1=有効化済み、0=無効化済み */
    /* タイムアウト時に呼ばれる */
    void (*timeout)(void*);
    /* キャンセル時に呼ばれる（NULLでもよい） */
    void (*cancel)(void*);
    void* arg;        /* timeout/cancelプロシージャへの引数 */
} ErlTimer;

ポート

ポートは、Erlang VMの外の世界との通信点を表すErlangの抽象化です。ソケットやパイプ、ファイルIOとの通信は、Erlang側からはすべてポートを通じて行われます。

ポートも、プロセスと同じように、生成元のプロセスと同じスケジューラ上に作られます。プロセスと同じくポートもリダクションを使っていつyieldするかを決めており、ポートにも4000リダクション分の実行時間が与えられます。ただしポートはErlangコードを実行しないので、リダクションとして数えるべきErlangの関数呼び出しがありません。その代わりに、ポートタスクごとに一定数のリダクションが数えられます。現在、1タスクあたり200リダクションあまりに加えて、送受信したデータサイズの1000分の1に相当するリダクション数が消費されます。

ポートタスクとは、ポートに対する1回の操作、たとえばオープンやクローズ、バイト列の送信やデータの受信のことです。ポートタスクを実行するために、実行スレッドはそのポートのロックを取得します。

ポートタスクは、新しいプロセスが実行対象として選ばれる前に、スケジューラループの各イテレーションでスケジュールされ実行されます（詳細は次節）。

スケジューラループ

概念的には、スケジューラをErlang VMにおけるプログラム実行のドライバとみなすことができます。実際には、つまりC言語コードの構造としては、実行を駆動しているのはエミュレータ（beam_emu.c中のprocess_main）であり、次に実行するプロセスを見つけるためにサブルーチンとしてスケジューラを呼び出しています。

とはいえ、スケジューラループの概念モデルとしてはこちらのほうがわかりやすいので、ここでは逆の見方をすることにします。つまり、スケジューラが実行するプロセスを選び、その実行をエミュレータに引き渡す、という見方です。

この見方に立つと、スケジューラループは次のようになります。

リダクションカウンタを更新する。
各プロセスには一定数のリダクション（小さな実行単位）が割り当てられています。リダクションカウントを使い切ると、そのプロセスはプリエンプトされ、別のプロセスがスケジュールされます。
タイマーを確認する。
タイマー（たとえばreceive ... after）はタイミングホイールを通じて確認されます。タイムアウトが発生していれば、対応するプロセスは実行可能キューへ移されます。
必要であればバランスを確認する。
システムは、いずれかのスケジューラスレッドに負荷が偏っていないかを随時確認します。偏りがあれば、負荷分散の判断が行われます。
必要であればプロセスとポートを移動する。
マルチコア環境でCPU負荷を再分散するために、プロセスとポートはスケジューラスレッド間で移動されることがあります。
スケジューラの補助的な作業を行う。
dirty NIFの処理、プロセスの終了処理、トレースフック、その他の後回しにされたランタイムの保守作業などが含まれます。
必要であればIOを確認し時刻を更新する。
ファイルディスクリプタやポートのI/O可否をポーリングし、システム時刻や時計を更新することがあります。
必要な限りポートタスクを選んで実行する。
TCPの読み書きやドライバコールバックの呼び出しといったタスクが、プロセスをスケジュールする前にここで実行されます。
実行するプロセスを選ぶ。
優先度と公平性を考慮して実行可能キューからrunnableなプロセスが選ばれ、実行のためにエミュレータへ引き渡されます。

負荷分散

現在の負荷分散戦略は、どのCPUも過負荷にしない範囲でできるだけ少ないスケジューラを使う、というものです。これは、複数のプロセスが同じCPUを共有することで、メモリ局所性が高まり性能が上がるという考えに基づいています。

ただし、スケジューラが行う負荷分散は、あくまでスケジューラスレッド間のものであり、必ずしもCPUやコア間のものではない点に注意してください。ランタイムシステムを起動するときには、スケジューラをコアへどう割り当てるかを指定できます。デフォルトの挙動では、スケジューラスレッドをコアへ割り当てるのはOS任せになっていますが、スケジューラをコアに固定することも選べます。

負荷分散器は、各コア上で1つのスケジューラが動いていることを前提としています。そのため、過負荷のスケジューラから利用率の低いスケジューラへプロセスを移動させれば、より多くの並列処理能力が得られるということになります。スケジューラのコアへの割り当てを変更していたり、OSがスレッドのコアへの割り当てが苦手だったり過負荷だったりする場合は、負荷分散がかえって裏目に出ることがあります。

負荷分散器は、負荷を均すためにタスクスティーリングとマイグレーションという2つの技法を使います。タスクスティーリングは、スケジューラが作業を使い果たすたびに使われます。この技法によって、作業はスケジューラ間でより広く分散されるようになります。マイグレーションはより複雑で、適切な数のスケジューラへ負荷を圧縮しようとします。

タスクスティーリング

スケジューラが新しいプロセスを選ぼうとしたときに実行可能キューが空であれば、そのスケジューラは別のスケジューラから作業を奪おうとします。

まずスケジューラは、他のスケジューラから自分の作業を奪われないよう自分自身にロックを取得します。続いて、作業を奪える非アクティブなスケジューラが無いかを確認します。奪える作業を持つ非アクティブなスケジューラが無ければ、自分より大きいIDを持つスケジューラから順にアクティブなスケジューラを見ていき、奪える作業を探します。

タスクスティーリングは一度に1つのスケジューラだけを見て、そのスケジューラの中で最も優先度の高いタスクを奪おうとします。これはスケジューラごとに行われるため、実際には別のスケジューラに奪えるより優先度の高いタスクがあっても、それが奪われないことがあります。

タスクスティーリングは番号の大きいスケジューラから奪おうとすることで、番号の小さいスケジューラへタスクを移そうとします。ただしスティーリングは番号の小さいスケジューラからも（一周して）行われるため、結果的にプロセスはアクティブな全スケジューラに分散することになります。

タスクスティーリングはかなり高速であり、スケジューラが作業切れになったスケジューラループの各イテレーションで行うことができます。

マイグレーション

スケジューラを本当に最適に活用するために、より作り込まれたマイグレーション戦略が使われています。現在の戦略は、いずれのスケジューラも過負荷にならないように負荷を分散させつつ、できるだけ少ない数のスケジューラへ負荷を圧縮する、というものです。

これはerl_process.c内のcheck_balance関数によって行われます。

マイグレーションは、まずマイグレーション計画を立て、新しい計画が立てられるまでスケジューラがその計画に従って動作する、という形で行われます。 2000*CONTEXT_REDSリダクションが経過するたびに、あるスケジューラは全スケジューラの作業負荷を見て、スケジューラごと・優先度ごとのマイグレーションパスを計算します。マイグレーションパスが取りうる値は3種類あります。1) クリア済み、2) あるスケジューラへマイグレーションする、3) あるスケジューラからイミグレーションする、です。

プロセスがreadyになったとき（たとえばメッセージを受け取ったとき、あるいはタイムアウトが発火したとき）は、通常、そのプロセスは直前に実行されていたスケジューラ（S1）上に再びスケジュールされます。これは、そのスケジューラ（S1）のその優先度でのマイグレーションパスがクリア済みである場合の話です。そのスケジューラのマイグレーションパスがエミグレーション（S2へ）に設定されている場合、S1とS2の両方の実行可能キューに不均衡があれば、プロセスはS2へ引き渡されます。この「不均衡」が何を意味するかは後で扱います。

スケジューラ（S1）が新しく実行するプロセスを選ぶとき、S1は自分に（S2からの）イミグレーションパスが設定されているかどうかを確認します。関係する2つのスケジューラの実行可能キューが不均衡であれば、S1はS2からプロセスを奪います。

マイグレーションパスは、ある優先度について各スケジューラの最大実行可能キュー長を比較することで計算されます。各スケジューラは、自身のスケジューラループの各イテレーションで最大キュー長を追跡するカウンタを更新します。この情報は、平均（最大）キュー長（AMQL）を計算するために使われます。

 Max
 Run Q
 Length
    5         o
              o
           o  o
Avg: 2.5 --------------
           o  o     o
    1      o  o     o

scheduler S1 S2 S3 S4

続いて、各スケジューラは最大キュー長でソートされます。

 Max
 Run Q
 Length
    5               o
                    o
                 o  o
Avg: 2.5 --------------
              o  o  o
    1         o  o  o

scheduler S3 S4 S1 S2

           ^        ^
           |        |
          tix      fix

平均より実行可能キューが長いスケジューラ（S1、S2）はエミグレーション対象としてマークされ、平均より最大実行可能キューが短いスケジューラ（S3、S4）はイミグレーション対象としてマークされます。

これは、ソート済みのスケジューラ集合に対して、イミグレーション元を指す添字（fix）とエミグレーション先を指す添字（tix）という2つの添字でループを回すことで行われます。ループの各イテレーションで、S[tix]のイミグレーションパスがS[fix]に設定され、S[fix]のエミグレーションパスがS[tix]に設定されます。続いてtixが増やされfixが減らされ、両方がバランス点を通過するまでこれを繰り返します。どちらか一方の添字が先にバランス点に達した場合は、そこで一周します。

先ほどの例では次のようになります。

イテレーション1：S2のエミグレーション先=S3、S3のイミグレーション元=S2
イテレーション2：S1のエミグレーション先=S4、S4のイミグレーション元=S1

これで完了です。

実際にはスケジューラをオフラインにできる分、もう少し複雑になります。マイグレーション計画はオンラインのスケジューラについてのみ立てられます。また、先に述べたとおり、この計算は優先度ごとに行われます。

プロセスを実行可能キューへ挿入しようとするとき、S1からS2へのマイグレーションパスが設定されていれば、スケジューラはまずS1の実行可能キューがAMQLより長いこと、S2の実行可能キューが平均より短いことを確認します。これにより、両方のキューがいまだに不均衡である場合に限ってマイグレーションが許可されます。

ただし、キューが均衡している場合、あるいはキューが逆方向に不均衡になっている場合でさえ、マイグレーションが強制される例外が2つあります。どちらの場合も、バランステストを上書きする特別な退避フラグが設定されます。

退避フラグは、スケジューラがオフラインにされるときに設定され、オフラインのスケジューラに新しいプロセスがスケジュールされないようにします。また、あるスケジューラで特定の優先度の処理が進んでいないことを検知したときにもこのフラグは設定されます。たとえば、常に実行可能なmax priorityのプロセスが存在するために、normal priorityのプロセスがまったくスケジュールされない、といった場合です。このとき、そのスケジューラのnormal priorityキューに対して退避フラグが設定されます。