スケジューリング･

実用日本語表現辞典

scheduling

別表記：スケジューリング

「scheduling」の意味・「scheduling」とは

「scheduling」は英語の単語で、日本語では「スケジューリング」と表現される。主に時間的な計画や調整、予定の立て方を指す。具体的には、会議の日程調整やプロジェクトの進行計画など、時間とタスクを効率的に組み合わせる行為を指す。

「scheduling」の発音・読み方

「scheduling」の発音は、IPA表記では /ˈskɛdʒuːlɪŋ/ となる。IPAのカタカナ読みでは「スケジューリング」となる。日本人が発音する際のカタカナ英語の読み方は「スケジューリング」である。

「scheduling」の定義を英語で解説

「Scheduling」 is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. In a literal sense, it is a timetable of events. It can also refer to the sequence of operations that are to be performed in a certain order.

「scheduling」の類語

「scheduling」の類語としては、「planning」「arranging」「organizing」などがある。これらの単語も同様に、時間やタスクの計画や調整を意味する。

「scheduling」に関連する用語・表現

「scheduling」に関連する用語としては、「timetable」「agenda」「itinerary」などがある。これらはすべて時間に関連した計画や予定を表す単語である。

「scheduling」の例文

1. "The scheduling of the project was done meticulously to ensure its success."（プロジェクトのスケジューリングは、その成功を確実にするために細心の注意を払って行われた。）
2. "Scheduling is crucial in time management."（時間管理においてスケジューリングは重要である。）
3. "The scheduling of the conference was changed due to unforeseen circumstances."（予期せぬ事情により、会議のスケジューリングが変更された。）
4. "The scheduling software helps to organize tasks efficiently."（スケジューリングソフトウェアはタスクを効率的に整理するのに役立つ。）
5. "The scheduling conflict led to the cancellation of the event."（スケジューリングの競合により、イベントがキャンセルされた。）
6. "Proper scheduling can prevent unnecessary stress."（適切なスケジューリングは不必要なストレスを防ぐことができる。）
7. "The scheduling of the tasks was done in order of priority."（タスクのスケジューリングは優先順位に従って行われた。）
8. "The scheduling of the flights was disrupted due to bad weather."（悪天候により、フライトのスケジューリングが乱れた。）
9. "The scheduling of the meeting was done well in advance."（会議のスケジューリングはかなり前に行われた。）
10. "The scheduling process requires careful consideration."（スケジューリングプロセスには慎重な考慮が必要である。）

（2023年9月15日更新）

スケジューリング

英語：scheduling

「スケジューリング」の意味・「スケジューリング」とは

「スケジューリング」とは、ある目的に沿って、タスクやイベントを計画・調整し、時間やリソースを効率的に配分するプロセスである。プロジェクト管理や個人のタイムマネジメントなど、様々な分野で用いられる。スケジューリングによって、期限や優先順位に基づいてタスクを整理し、効果的な実行が可能となる。

「スケジューリング」の語源

「スケジューリング」は英語の ""scheduling"" が語源であり、スケジュール（schedule）という言葉に ""ing"" を付け加えたものである。""schedule"" は、ラテン語の ""scheda""（紙片）が語源であり、紙片に書かれたリストや計画を意味していた。現代では、時間やタスクの管理に関連する言葉として広く使われている。

「スケジューリング」に関連する用語・知識

「スケジューリング」と「スケジュール」の違い

「スケジューリング」と「スケジュール」は似た言葉であるが、意味は異なる。「スケジュール」は、計画されたタスクやイベントのリストや時間表を指すのに対し、「スケジューリング」は、そのリストや時間表を作成・調整するプロセスを指す。

ビジネスにおける「スケジューリング」とは

ビジネスにおける「スケジューリング」は、プロジェクト管理やリソース配分、タイムマネジメントなどの分野で重要な役割を果たす。効率的なスケジューリングにより、プロジェクトの期限や目標を達成するために必要なタスクを適切に割り当て、リソースの最適化が可能となる。

「スケジューリング」を用いた例文

1. プロジェクトの成功のためには、効果的なスケジューリングが不可欠である。 2. 彼女は締め切りに間に合わせるため、スケジューリングを見直し、優先順位を再評価した。 3. 会議のスケジューリングを行う際には、参加者全員の都合を考慮する必要がある。

（2023年4月28日更新）

デジタル大辞泉

スケジューリング【scheduling】

読み方：すけじゅーりんぐ

予定や日程を組むこと。

ウィキペディア

スケジューリング

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/02 15:54 UTC 版)

計算機科学においてスケジューリング（英: scheduling）は、スレッドやプロセスやデータの流れについて、システム資源（例えば、プロセッサ時間、通信帯域など）へのアクセスを与える方法の一つ。スケジューラはスケジューリングを実行するソフトウェア。

概要

システムを効果的に負荷分散するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク（同時に複数のプロセスを実行）や多重化（複数のデータの流れを同時に転送）の発展とともに進化してきた。

スケジューラの主な関心事は以下の通りである。

• スループット - 単位時間ごとに実行完了するプロセスの総数
• レイテンシ
  • ターンアラウンド - プロセスの発行から完了までの総時間
  • 応答時間 - 要求を送ってから最初の応答が生成されるまでにかかる時間
• 公平さ/待ち時間 - 各プロセスに平等にCPU時間を割り当てること（またより一般的には、各プロセスの優先度に応じた適切な時間）

スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。

ファクトリーオートメーションのための組み込みシステム（例えば産業用ロボット）などのリアルタイム環境では、スケジューラがプロセスの時間制限（デッドライン）を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。

近年では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。

スケジューラの分類

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

長期スケジューラ

長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める（I/Oバウンドなプロセスとは記憶媒体すなわちディスクやメモリの入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する）。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる。

長期スケジューラはバッチ処理システム、コンピュータ・クラスター、スーパーコンピュータ、レンダーファームなどの大規模システムでも重要である。その場合、専用のジョブ管理システムが長期スケジューラの役目を果たす。

なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。

中期スケジューラ

中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶（ディスクなど）に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起動した場合などに、スワップアウトされていたプロセスをスワップインする。

多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。

短期スケジューラ

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

ディスパッチャ

CPUのスケジューリング機能に関わるもう1つのコンポーネントとしてディスパッチャがある。ディスパッチャは短期スケジューラが選択したプロセスにCPUの制御を与えるモジュールである。次のようなことを行う。

• コンテキストスイッチ
• ユーザーモードへの切り換え
• プログラムの実行再開のための正しい位置へCPUをジャンプさせる。

プロセスを切り換える際に必ず実行されるので、ディスパッチャは性能が重視される。ディスパッチャがあるプロセスを一時停止させ、別のプロセスを実行再開させるのにかかる時間を「ディスパッチ・レイテンシ」と呼ぶ。

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

スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。

スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。

FIFO

FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。

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

最小残余時間優先

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

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

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

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

• オーバーヘッドは最小でもないし、極端に大きくもない。
• スループットの面では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で削除された。
• Budget Fair Queueing (BFQ) - CFQをマルチキュー機構向けに改良したLinuxのI/Oスケジューラ。スループットよりもレイテンシーを少なくするように制御する。
• Deadline - 時間制限を設けリクエストの処理開始時間を保証する方式。

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ビットアプリケーションはプリエンプションなしで動作した。

Windows NT系のOSは多段フィードバックキューを使っている。優先度は32段階で0から31まであり、0から15がノーマル優先度、16から31がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。0はOSが予約している。ユーザーはタスクマネージャまたはスレッド管理APIから動作中アプリケーションの優先度を5段階に設定できる。カーネルはスレッドのI/OおよびCPU使用具合を見て優先度を更新しており、対話的（ユーザーとのやりとりを行っている）なI/O中心のプロセスの優先度は高くし、CPU中心のプロセスの優先度は低くする。それによってアプリケーションの応答性を向上させる。Windows Vistaではスケジューラが修正され、タイムスタンプカウンタを使って各スレッドが実際に動作したCPUサイクル数をカウントするようになった。また、I/Oキューも優先度付きとなり、ディスクのデフラグメンテーションなどのプログラムが通常の処理を邪魔しないようになった。

Mac OS

Mac OS 9はスレッドの協調的スケジューリングであり、1つのプロセスが複数の協調動作するスレッド群を制御する。また、MPタスクのプリエンプティブなスケジューリングも提供している。カーネルはプリエンプティブなスケジューリングアルゴリズムを使ってMPタスクをスケジュールする。プロセスマネージャの全プロセスは1つの特殊なMPタスク "blue task" 内で動作する。それらのプロセスはラウンドロビン・スケジューリングを使って協調的にスケジュールされ、WaitNextEvent などの関数を使って明示的にプロセッサの制御を他のプロセスに譲る。各プロセスにはスレッドマネージャがあり、こちらもスレッド群を協調的にスケジュールする。スレッドは YieldToAnyThread や YieldToThread といった関数を使って他のスレッドにプロセッサの制御を譲る。

macOSは多段フィードバックキューを使っており、スレッドにはノーマル/システム高優先度/カーネルモードオンリー/リアルタイムという4つの優先度バンドを提供する。プリエンプションを伴ってスケジュールを行う。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 と呼ばれる。

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 を開発した。Completely Fair Scheduler (CFS) はパケット通信用に発明された均等化キューイングという古典的なスケジューリングアルゴリズムをベースにしている。均等化キューイングはかつて stride scheduling の名でCPUスケジューリング方式として使われたことがある。

CFSスケジューラのスケジューリング複雑性は On(log N) で、この N はランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキューが赤黒木で実装されているためである。

汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である。

FreeBSD

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

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まではタイムシェアリング・スレッド用、60から99まではシステムスレッド用、100から159はリアルタイム・スレッド用、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	あり	多段フィードバックキュー

参考文献

• 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

関連項目

• プロセス管理
• 自動計画
• Brain Fuck Scheduler
• マルチタスク
• Earliest Deadline First
• Least Slack Time
• 多段フィードバックキュー
• 優先順位の逆転
• プロセス
• レートモノトニックスケジューリング
• ラウンドロビン・スケジューリング

外部リンク

• Brief discussion of Job Scheduling algorithms
• Understanding the Linux Kernel: Chapter 10 Process Scheduling - ウェイバックマシン（2006年6月13日アーカイブ分）
• Kerneltrap: Linux kernel scheduler articles - archive.today（2013年4月15日アーカイブ分）
• CPU monitoring and tuning - ウェイバックマシン（2011年8月11日アーカイブ分）
• Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation - ウェイバックマシン（2015年1月29日アーカイブ分）
• Complexity results for scheduling problems Peter Brucker, Sigrid Knust.
• TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.

ウィキペディア小見出し辞書

スケジューリング

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/09 15:59 UTC 版)

「リアルタイムオペレーティングシステム」の記事における「スケジューリング」の解説

RTOSは通常マルチタスクOSで、スケジューリングはタスクの優先度に基づいて行われる。タスクの実行中（割り込みハンドラやOS自身などの実行中でないということ）は、常に、実行可能状態にあるタスクのうち最高優先度のものを実行しなければならない。実行中のタスクよりも優先度が高いタスクが実行可能状態になった場合は、即座にタスク切り替えを行う。すなわち、RTOSはいわゆる「プリエンプティブ・マルチタスク」（プリエンプションを参照）でなければならない。さらにRTOSの場合は、カーネルが優先度の低いタスクによるシステムコールを実行中の場合でクリティカルセクションでなければ、優先度の高いタスクを実行する「プリエンプティブ・カーネル」でなければならない。 汎用OSのように、タスクの消費時間により優先度を変化させることは通常おこなわない。ただし、時間制約のない低優先度のタスクを複数同居させる場合など、それらのタスクでは優先度を共通とし、自発的にCPUを手放す協調的マルチタスクや、タイマ割込みにより順番に切り替えるタイムシェアリング的なスケジューリングを同居させることもある。 典型的な設計では、タスクには「実行中」「実行可能」「ブロック」の3状態がある。ほとんどのタスクはブロック状態でいることが多い。CPUは1度に1つのタスクを実行できる（実行中状態となるタスクはCPU毎に最大1つ）。単純なシステムでは実行可能なタスクのリストも短く、せいぜい2個から3個のタスクが載っていることが多い。 スケジューラの設計は重要である。実行可能タスクのリストはスケジューラのクリティカルセクション（プリエンプションが禁止され、場合によっては全割り込みも不可となる）で消費する時間を最小にするよう設計される。ただし、データ構造の選択は実行可能リスト上の最大タスク数にも依存する。 実行可能リスト上のタスク数が少ないなら、単純な双方向線形リストが最適である。状況によって実行可能タスク数が増えるなら、優先度に従ってソートされたリストを使用し、最高優先度のタスクを探すためにリスト全体を検索する必要がないようにすべきである。そうすると、あるタスクを実行可能タスクのリストに追加する際にリスト全体を探索して、そのタスクより低い優先度のタスクを見つけ、その前の位置にタスクを追加（挿入）する必要が生じる。この探索期間中ずっとプリエンプションを禁止してはいけない。探索中の真にクリティカルな期間だけプリエンプションを禁止することで、例えば探索中に割り込みが発生してより高優先度のタスクが実行可能となったら、現に実行可能リストに挿入しようとしている低優先度タスクよりも先に実行可能リストに挿入して実行するようにしなければならない。 新たな実行可能タスクをキューに登録し、最高優先度タスクの状態をリストアするのにかかる時間が非常に重要な応答時間である（フライバック時間とも呼ばれる）。よく設計されたRTOSでは、新たなタスクの実行可能キューへの挿入には（キュー上のエントリ毎に）3-20命令かかり、最高優先度タスクのリストアには5-30命令かかる。20MHzのMC68000プロセッサでは、2個のタスクが実行可能な状態でのタスク切り替え時間は20マイクロ秒である。100MHzのARMプロセッサでは数マイクロ秒となる。 高度なリアルタイムシステムでは、リアルタイムのタスク以外に非リアルタイムタスクも共存するため、実行可能リストは非常に長くなる可能性がある。そのようなシステムでは、スケジューラの実行可能リストを単純な線形リストで実装するのでは不十分である。このため、優先度毎に実行可能リストを分割することで探索処理を不要にすることもある。

Weblio日本語例文用例辞書

「スケジューリング」の例文・使い方・用例・文例

• 調整のついてないスケジューリングは、しばしば矛盾するゲームをもたらす