スケジューリング

計算機科学においてスケジューリング︵英: scheduling︶は、スレッドやプロセスやデータの流れについて、システム資源︵例えば、プロセッサ時間、通信帯域など︶へのアクセスを与える方法である。システムを効果的に負荷分散するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク︵同時に複数のプロセスを実行︶や多重化︵複数のデータの流れを同時に転送︶の発展とともに進化してきた。スケジューラの主な関心事は以下の通りである。 ●スループット - 単位時間ごとに実行完了するプロセスの総数 ●レイテンシ ●ターンアラウンド - プロセスの発行から完了までの総時間 ●応答時間 - 要求を送ってから最初の応答が生成されるまでにかかる時間 ●公平さ/待ち時間 - 各プロセスに平等にCPU時間を割り当てること︵またより一般的には、各プロセスの優先度に応じた適切な時間︶スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。ファクトリーオートメーションのための組み込みシステム︵例えば産業用ロボット︶などのリアルタイム環境では、スケジューラがプロセスの時間制限︵デッドライン︶を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。近年^[いつ?]では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。

スケジューラの分類

スケジューラは3種類に分類される。﹁長期スケジューラ﹂、﹁中期スケジューラ﹂、﹁短期スケジューラ﹂である。名称が示唆するとおり、その機能が実行される頻度が異なる。スケジューラは、システムに次に入れるべきジョブを決定し、次の実行すべきプロセスを決定する。

長期スケジューラ

長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める︵I/Oバウンドなプロセスとは記憶媒体すなわちディスクやメモリの入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する︶。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる^[1]。長期スケジューラはバッチ処理システム、コンピュータ・クラスター、スーパーコンピュータ、レンダーファームなどの大規模システムでも重要である。その場合、専用のジョブ管理システムが長期スケジューラの役目を果たす。なお、﹁長期スケジューラ﹂という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。

中期スケジューラ

中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶︵ディスクなど︶に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を﹁スワップアウト﹂および﹁スワップイン﹂と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起動した場合などに、スワップアウトされていたプロセスをスワップインする^[2]。多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。

短期スケジューラ

短期スケジューラ︵またはCPUスケジューラ︶は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき︵CPUを割り当てるべき︶プロセスを決定する。そのタイミングとしては、クロック割り込み、I/O割り込み、システムコール、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブなスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う^[3]。

ディスパッチャ

CPUのスケジューリング機能に関わるもう1つのコンポーネントとしてディスパッチャがある。ディスパッチャは短期スケジューラが選択したプロセスにCPUの制御を与えるモジュールである。次のようなことを行う。 ●コンテキストスイッチ ●ユーザーモードへの切り換え ●プログラムの実行再開のための正しい位置へCPUをジャンプさせる。プロセスを切り換える際に必ず実行されるので、ディスパッチャは性能が重視される。ディスパッチャがあるプロセスを一時停止させ、別のプロセスを実行再開させるのにかかる時間を﹁ディスパッチ・レイテンシ﹂と呼ぶ。

スケジューリングアルゴリズム

スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。

FIFO

詳細は「FIFO」を参照

FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。 ●コンテキストスイッチはプロセス終了時にしか発生せず、キューの再編成も必要とされないので、スケジューリングのオーバーヘッドは最小である。 ●長くかかるプロセスがCPUを占有することがあるので、スループットは低くなりうる。 ●同じ理由で、ターンアラウンド時間、待ち時間、応答時間は長くなる可能性がある。 ●優先順位付けは行わないので、プロセスのデッドラインを満たすのは難しい。 ●優先順位付けを行わないということは、全てのプロセスが結局は完了するという意味で、スタベーションは発生しないと言える。一部プロセスが完了しない環境では、スタベーションがありうる。 ●キューイングをベースとしている。

最小残余時間優先

最小残余時間優先︵英語版︶ (SRT) 方式は、最短ジョブ優先︵英語版︶ (SJF) 方式とも似ている。この戦略では、キュー内で残り処理時間の推定値が最も短いプロセスをスケジューラが選択する。これはプロセスの完了までにかかる時間についての高度な知識または評価を必要とする。

●あるプロセスを実行中に別のもっと短いプロセスが到着すると、動作中のプロセスは中断され︵プリエンプション︶、そのプロセスを2つの別々の計算ブロックに分けることになる。これはコンテキストスイッチを追加することになり、オーバーヘッドが増えることを意味する。スケジューラはキュー上の適当な位置に新たなプロセスを置かなければならず、これもオーバヘッドを生じる。 ●多くの場合でスループットを最大化するよう設計されている。 ●プロセスが要求する計算資源が大きいほど、待ち時間と応答時間が増大する。ターンアラウンド時間は待ち時間と処理時間の総和なので、長くかかるプロセスは特に大きく影響を受ける。全体としての待ち時間の総和はFIFOと同程度だが、長くかかるプロセスの完了まで他のプロセスを待たせる必要はない。 ●デッドラインに対する配慮は全くない。プログラマはプロセスがなるべく短時間で終了するよう気をつけるぐらいしかできない。 ●スタベーションは発生しうる。特に小さなプロセスが多数動作するシステムで発生しやすい。

固定優先度プリエンプティブ・スケジューリング

固定優先度プリエンプティブ・スケジューリング︵英語版︶ (FCFS) は、全てのプロセスに固定の優先度を付与し、その優先度順にプロセスをキューイングする。新たに高優先度のプロセスが到着すると、現に実行中だった低優先度のプロセスは中断される。

●オーバーヘッドは最小でもないし、極端に大きくもない。 ●スループットの面ではFIFOスケジューリングと大差ない。 ●待ち時間と応答時間はプロセスの優先度に左右される。高優先度のプロセスほど待ち時間と応答時間が小さくなる。 ●デッドラインは優先度をうまく設定することで満たすことができる。 ●低優先度プロセスではスタベーションが発生しうる。

ラウンドロビン・スケジューリング

詳細は「ラウンドロビン・スケジューリング」を参照

スケジューラは各プロセスにある一定時間単位を割り当て、次々にその割り当てを実行させる。 ●オーバーヘッドは比較的大きく、特に割り当てる時間単位を短くするほど大きくなる。 ●スループットはFCFSとSJFの中間で、短いジョブはFCFSより早く完了し、長いプロセスはSJFより早く完了する。 ●平均応答時間はよくない。待ち時間はプロセス数に依存し、平均プロセス長︵時間︶には依存しない。 ●待ち時間は比較的長いので、純粋なラウンドロビンでデッドラインを守るのは難しい。 ●優先度を設定していないので、スタベーションは決して発生しない。時間単位を割り当てる順序は、FCFSと同様プロセスの到着順である。

多段キュースケジューリング

詳細は「多段フィードバックキュー」を参照

これは、プロセスを容易に複数のグループに分類できる場合に使われる、例えば典型的な分類はフォアグラウンド︵対話型︶プロセスとバックグラウンド︵バッチ︶プロセスである。このように分けると、それぞれ応答時間の要求がグループによって異なるので、スケジューリングに求められることがグループによって異なる。

まとめ

スケジューリングアルゴリズム	CPUオーバーヘッド	スループット	ターンアラウンド時間	応答時間
FIFO	低い	低い	高い	低い
最短ジョブ優先（英語版）	中程度	高い	中程度	中程度
優先度ベースのスケジューリング（英語版）	中程度	低い	高い	高い
ラウンドロビン・スケジューリング	高い	中程度	中程度	高い
多段キュー・スケジューリング	高い	高い	中程度	中程度

通信ネットワークのスケジューリングアルゴリズム

パケット交換コンピュータネットワークや他の統計多重化では、データパケットのFIFOキューがスケジューリングアルゴリズムとほぼ同義である。最も単純なベストエフォートなスケジューリングアルゴリズムとしてラウンドロビン・スケジューリング、均等化キューイング︵英語版︶︵最大最小公平︵英語版︶なスケジューリングアルゴリズム︶、比例公平︵英語版︶スケジューリング、最大スループットスケジューリング︵英語版︶などがある。ベストエフォートではなくQoSの保証を行う場合、重み付け均等化キューイング︵英語版︶などが使われる。 3.5G携帯システムの High-Speed Downlink Packet Access (HSDPA) などの無線パケットネットワークは、チャネル状態情報︵英語版︶を利用した channel-dependent scheduling を採用している。チャネル状態が良好なら、スループットとスペクトル効率も向上する。LTEなどのさらに進んだシステムでは、スケジューリングはパケット単位の動的チャネル割り当てと組み合わされたり、OFDMAマルチキャリアや周波数領域等化︵英語版︶コンポーネントを最も有効利用できるユーザーに割り当てることでなされる。

I/Oのスケジューリング方式

ディスクのアームやヘッダを移動させる時間を減少させるようにスケジュールすることで、高速化が期待できる。 ●FIFO (First In, First Out) - 単純にI/O要求を受け付けた順に処理する方式。 ●Shortest Seek First - シーク時間が最も短くなるようにスケジュールする方式。 ●Elevator Algorithm - ヘッドをシリンダ番号の昇順か降順に動作させるものとし、その順番にあうようにスケジュールする方式。Shortest Seek Firstと比べ、断続的にI/O要求を受け付けた場合でも待ち時間のばらつきが小さく収まる特徴がある。 ●Anticipatory Scheduling - 将来のI/O要求を予測してスケジュールする方式。 ●Completely Fair Queuing (CFQ) - プロセス毎のI/Oキューを持ち、できるだけ公平にスケジュールする方式。Linux 2.6.18以降のデフォルトのI/Oスケジューラとして採用されていたが、Linux5.0で削除された。^[4] ●Budget Fair Queueing (BFQ) - CFQをマルチキュー機構向けに改良したLinuxのI/Oスケジューラ。スループットよりもレイテンシーを少なくするように制御する。^[5] ●Deadline - 時間制限を設けリクエストの処理開始時間を保証する方式。^[6]

OSにおけるスケジューリングアルゴリズムの選択法

OS設計の際、そのシステムを使用するにあたって最善のスケジューリングアルゴリズムは何かを検討する必要がある。あらゆる用途に最善といえる単一のスケジューリングアルゴリズムは存在せず、上述の各種スケジューリングアルゴリズムを組み合わせたり拡張したりして使っているOSが多い。例えば、Windows NT/XP/Vista は固定優先度プリエンプティブ・スケジューリングとラウンドロビンとFIFOを組み合わせた多段フィードバックキューを採用している。このシステムでは、プロセスがそれまでに動作してきた状況や待ち続けた状況に従い、優先度を動的に調整する。優先度ごとにキューがあり、高優先度のキューではラウンドロビン・スケジューリング、低優先度のキューではFIFOを採用している。応答時間はほとんどのプロセスで短くなり、短いが重要なプロセスは特に素早く完了する。高優先度のキューはラウンドロビンなのでプロセスが一定時間単位しか動作しないため、スタベーションは起こりにくい。

リアルタイム性を保証するスケジューリング

スケジューリングにおいて、リアルタイム制約を満たすということは以下のどちらかを指す。 ●優先度逆転問題を防ぐ。 ●タスクのリアルタイム制約を守れることを保証する。後者についての研究はさかんに行われているが、スケジューリングが複雑になるために実際のシステムで利用されることは極めて少ない。

オペレーティングシステムのスケジューラ実装

当然のことながら、OSの数だけスケジューリング方式がある。ラウンドロビンのような単純なアルゴリズムを採用すると、各プロセスに同じ時間︵一般に1ミリ秒から100ミリ秒︶が割り当てられ、それが巡回するように実際に実行されていく。従って、プロセスとしてA、B、Cの3つがあるとき、Aを1ミリ秒実行し、次にB、次にCと実行していき、再びAを実行するというようになる。より進んだアルゴリズムではプロセスに優先度を設定したり、プロセスの重要度を判断したりする。それによって特定のプロセスが他のプロセスよりも優先してCPU時間を割り当てられることになる。カーネルはシステムを正しく機能させるのに必要な資源を必要なだけ使用するので、ある意味では無限の優先度があるとも言える。対称型マルチプロセッシング (SMP) システムでは、プロセッサ親和性を考慮することでシステム全体性能を向上させようとするが、個々のプロセスはそれによって動作がゆっくりになることもありうる。これは一般にキャッシュスラッシングを低減させることで性能を向上させる。マルチプロセッシングでは、各プロセッサをなるべく平等に使用するようスケジューリングするのが一般的である。スケジューリングをプロセッサ単位に行う方式とシステム全体で行う方式があり、前者ではプロセッサ毎の実行可能プロセスのキューが存在し、後者ではシステムに唯一の実行可能プロセスキューが存在する。システム全体の方が優先順位の逆転が発生しにくく、プロセッサ間の負荷バランスをとりやすいという利点がある。しかし、実行効率を考えた場合、各プロセッサのキャッシュメモリの内容などを生かすにはプロセスはなるべく同じプロセッサ上で実行された方がよい。この性質をアフィニティ (affinity) と呼ぶ。そのため、プロセッサ単位のスケジューラを使用し、負荷バランスが大きく崩れたときだけ調整を行う方式を採用するシステムもある。また、システム全体をひとつのスケジューラで制御しようとすると、実行可能プロセスキューへのアクセスで衝突が発生し性能が低下するという問題もある。 NUMAでは、SMPシステムが相互接続されている。このSMPシステム間でのプロセスの移動はSMP内よりもさらに性能に悪影響を与える。そのため各SMPシステムでスケジューラを動作させ、SMPシステム間の負荷バランスは別途調整するのが一般的である。Linuxではexec()によるオーバーレイの際にバランス調整を行う。exec()ではプロセスのアドレス空間の内容が置き換えられるので、ノード間の移動をさせるのにちょうどよいタイミングと言える。

Windows

初期のMS-DOSやWindowsシステムはマルチタスクではないので、スケジューラも存在しなかった。Windows 3.1系のOSは単純な非プリエンプティブ・スケジューラを使用しており、プログラマはプロセスが明示的にCPUを明け渡す (yield) ように設計してCPU時間を他のプロセスに使わせる必要があった。これにより協調的マルチタスクをサポートしていた。Windows 95 で初歩的なプリエンプティブ・スケジューラを導入したが、互換性を維持するため16ビットアプリケーションはプリエンプションなしで動作した^[^7]。 Windows NT系のOSは多段フィードバックキューを使っている。優先度は32段階で0から31まであり、0から15がノーマル優先度、16から31がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。0はOSが予約している。ユーザーはタスクマネージャまたはスレッド管理APIから動作中アプリケーションの優先度を5段階に設定できる。カーネルはスレッドのI/OおよびCPU使用具合を見て優先度を更新しており、対話的︵ユーザーとのやりとりを行っている︶なI/O中心のプロセスの優先度は高くし、CPU中心のプロセスの優先度は低くする。それによってアプリケーションの応答性を向上させる^[8]。Windows Vista ではスケジューラが修正され、タイムスタンプカウンタ︵英語版︶を使って各スレッドが実際に動作したCPUサイクル数をカウントするようになった^[9]。また、I/Oキューも優先度付きとなり、ディスクのデフラグメンテーションなどのプログラムが通常の処理を邪魔しないようになった。

Mac OS

Mac OS 9はスレッドの協調的スケジューリングであり、1つのプロセスが複数の協調動作するスレッド群を制御する。また、MPタスクのプリエンプティブなスケジューリングも提供している。カーネルはプリエンプティブなスケジューリングアルゴリズムを使ってMPタスクをスケジュールする。プロセスマネージャの全プロセスは1つの特殊なMPタスク "blue task" 内で動作する。それらのプロセスはラウンドロビン・スケジューリングを使って協調的にスケジュールされ、WaitNextEvent などの関数を使って明示的にプロセッサの制御を他のプロセスに譲る。各プロセスにはスレッドマネージャがあり、こちらもスレッド群を協調的にスケジュールする。スレッドは YieldToAnyThread や YieldToThread といった関数を使って他のスレッドにプロセッサの制御を譲る。 macOSは多段フィードバックキューを使っており、スレッドにはノーマル/システム高優先度/カーネルモードオンリー/リアルタイムという4つの優先度バンドを提供する^[10]。プリエンプションを伴ってスケジュールを行う。Carbon内では協調的スケジューラ︵英語版︶ (cooperative scheduler) も実装している。

AIX

AIX Version 4 には、スレッドスケジューリングポリシーとして以下の3種類の設定が可能である。 FIFO このポリシーでスケジュールされたスレッドは、ブロックされるまで、あるいはCPUの制御を明示的に明け渡すまで、あるいはより高優先度のスレッドが動作可能になるまで、動作し続ける。FIFOスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。 RR AIX Version 3 のスケジューラと同様のラウンドロビン方式で、タイムスライスは10ミリ秒である。RRスレッドがタイムスライスを使い切ると、その優先度の実行可能スレッドのキューの最後尾につなげられる。RRスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。 OTHER POSIX1003.4a で定義されたポリシーの実装。AIX Version 4 ではRRと等価だが、固定優先度でないスレッドにも適用される。クロック割り込みの際に動作中スレッドの優先度を再計算するので、他の動作可能なスレッドの方が優先度が高くなれば、そこでディスパッチが発生する。これは AIX Version 3 と同じである。 AIX 5 では、FIFO、ラウンドロビン、フェア・ラウンドロビンという3つのスケジューリングポリシーを実装している。FIFOポリシーには3つの実装︵FIFO、FIFO2、FIFO3︶がある。ラウンドロビンポリシーはAIXではSCHED_RRと呼ばれ、フェア・ラウンドロビンは SCHED_OTHER と呼ばれる^[11]。

Linux

Linux 2.4

Linux 2.4 では、多段フィードバックキュー方式のO(n)スケジューラ︵英語版︶を採用していた。優先度は0から140まであり、0から99まではリアルタイムタスク用、100から140まではniceタスク用のレベルとされていた。リアルタイムのタスクでは、プロセス切り替え間隔であるタイムクォンタムは約200ミリ秒、niceタスクでは約10ミリ秒となっていた^[要出典]。スケジューラは全実行可能プロセスが入っているactiveキューを調べ、最も優先度の高いプロセスを選択してディスパッチし、タイムクォンタムを使い切ったら、それをexpiredキューにつなぐ。activeキューが空になると、expiredキューがactiveキューとなり、activeキューだったものがexpiredキューとなる。一部の企業向けLinuxディストリビューション︵SUSE Linux Enterprise Server など︶は、O(1)スケジューラ︵英語版︶を2.4カーネルに先取りする形で移植したものを使っていた︵アラン・コックスが Linux 2.4-ac Kernel series として保守していた︶。

Linux 2.6.0 から Linux 2.6.22 まで

バージョン 2.6 から 2.6.22 までのカーネルは、Linux 2.5 の開発でインゴ・モルナー︵英語版︶らが開発したO(1)スケジューラ︵英語版︶を採用している。しかし、多くのディストリビューションはコン・コリバス︵英語版︶が開発した対話性を向上させるパッチを適用するか、あるいはコン・コリバスのスケジューラに完全に置き換えていた。

Linux 2.6.23 以降

コン・コリバス︵英語版︶が実装したフェア・シェア・スケジューリング︵英語版︶方式の "Rotating Staircase Deadline" に触発され、インゴ・モルナーがO(1)スケジューラ︵英語版︶の代替として Completely Fair Scheduler を開発した^[12]。Completely Fair Scheduler (CFS) はパケット通信用に発明された均等化キューイング︵英語版︶という古典的なスケジューリングアルゴリズムをベースにしている。均等化キューイングはかつて stride scheduling の名でCPUスケジューリング方式として使われたことがある。 CFSスケジューラのスケジューリング複雑性は O(logN) で、このNはランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキュー︵英語版︶が赤黒木で実装されているためである。汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である^[13]。

FreeBSD

FreeBSDは、優先度が0から255までの多段フィードバックキューを使用している。0から63までは割り込み用、64から127まではカーネル用、128から159まではリアルタイムのユーザースレッド用、160から223まではタイムシェアリングのユーザースレッド用、224から255まではアイドルスレッド用である。Linuxと同様、activeキューを使ってスケジューリングするが、FreeBSDにはidleキューもある^[14]。

NetBSD

NetBSDは、優先度が0から233までの多段フィードバックキューを使用している。0から63まではタイムシェアリング・スレッド用︵SCHED_OTHERポリシー︶、64から95まではカーネル空間に入った状態︵システムコール実行中など︶のユーザースレッド用、96から128まではカーネル・スレッド用、128から191まではユーザーのリアルタイム・スレッド用︵SCHED_FIFOまたはSCHED_RRポリシー︶、192から233まではソフトウェア割り込み用である。

Solaris

Solarisは、優先度が0から169までの多段フィードバックキューを使用している。0から59まではタイムシェアリング・スレッド用^[^15]、60から99まではシステムスレッド用、100から159はリアルタイム・スレッド用^[15]、160から169までは低優先度の割り込み用である。Linuxとは異なり、タイムクォンタムを使い切ったプロセスは新たな優先度を設定され、キューに戻される。

まとめ

OS	プリエンプション	アルゴリズム
Windows 3.1x	なし	協調的スケジューラ
Windows 95、98、Me	半分	32ビットプロセスはプリエンプティブ。16ビットプロセスは協調的スケジューラ
Windows NT系	あり	多段フィードバックキュー
Mac OS 8以前	なし	協調的スケジューラ
Mac OS 9	一部	MPタスクはプリエンプティブ。プロセスやスレッドは協調的スケジューラ
macOS	あり	多段フィードバックキュー
Linux 2.6 より以前	あり	多段フィードバックキュー
Linux 2.6-2.6.23	あり	O(1)スケジューラ（英語版）
Linux 2.6.23 以降	あり	Completely Fair Scheduler
Solaris	あり	多段フィードバックキュー
NetBSD	あり	多段フィードバックキュー
FreeBSD	あり	多段フィードバックキュー

脚注

(一)^ Stallings 2004, p. 399 (二)^ Stallings 2004, pp. 396, 370 (三)^ Stallings 2004, p. 396 (四)^ ジェンス・アクスボー (2018年10月12日). “block: remove legacy IO schedulers”. 2023年7月1日閲覧。 (五)^ “BFQ (Budget Fair Queueing)”. 2023年7月1日閲覧。 (六)^ “Deadline IO scheduler tunables”. 2023年7月1日閲覧。 (七)^ Early Windows (八)^ Sriram Krishnan. “A Tale of Two Schedulers Windows NT and Windows CE”. 2012年7月22日時点のオリジナルよりアーカイブ。2012年7月19日閲覧。 (九)^ Inside the Windows Vista Kernel: Part 1, Microsoft Technet (十)^ “Mach Scheduling and Thread Interfaces”. 2012年7月19日閲覧。 (11)^ CPU monitoring and tuning Archived 2011年8月11日, at the Wayback Machine. (12)^ Molnár, Ingo (13 April 2007). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list). (13)^ Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin (14)^ “Comparison of Solaris, Linux, and FreeBSD Kernels”. 2012年7月19日閲覧。 (15)^ ^a ^b“Real-Time Scheduler Scheduling Classes”. Oracle (2019年4月). 2020年11月7日閲覧。

参考文献

Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. (2001). Scheduling computer and manufacturing processes (2 ed.). Berlin [u.a.]: Springer. ISBN 3-540-41931-4
Stallings, William (2004). Operating Systems Internals and Design Principles (fifth international edition). Prentice Hall. ISBN 0-13-147954-7
Stallings, William (2004). Operating Systems Internals and Design Principles (fourth edition). Prentice Hall. ISBN 0-13-031999-6
Information on the Linux 2.6 O(1)-scheduler

外部リンク

Brief discussion of Job Scheduling algorithms
Understanding the Linux Kernel: Chapter 10 Process Scheduling
Kerneltrap: Linux kernel scheduler articles
AIX CPU monitoring and tuning
Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
Peter Brucker, Sigrid Knust. Complexity results for scheduling problems
TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.

[1]

[2]

[3]

[4]

[5]

[6]

[

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[