スケジューリング・とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 産業 > 農業 > スケジューリング > スケジューリング・の意味・解説 

scheduling

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

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

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

「scheduling」の発音・読み方

「scheduling」の発音は、IPA表記では /ˈskɛ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."(スケジューリングプロセスには慎重な考慮が必要である。)

スケジューリング

英語:scheduling

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

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

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

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

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

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

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

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

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

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

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

スケジューリング【scheduling】

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

予定日程を組むこと。


スケジューリング

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

計算機科学においてスケジューリング: 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時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。

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

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で削除された。[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 などの関数を使って明示的にプロセッサの制御を他のプロセスに譲る。各プロセスにはスレッドマネージャがあり、こちらもスレッド群を協調的にスケジュールする。スレッドは YieldToAnyThreadYieldToThread といった関数を使って他のスレッドにプロセッサの制御を譲る。

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スケジューラのスケジューリング複雑性は On(log N) で、この 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 9598Me 半分 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 あり 多段フィードバックキュー

脚注

  1. ^ Stallings 2004, p. 399
  2. ^ Stallings 2004, pp. 396, 370
  3. ^ Stallings 2004, p. 396
  4. ^ ジェンス・アクスボー (2018年10月12日). “block: remove legacy IO schedulers”. 2023年7月1日閲覧。
  5. ^ BFQ (Budget Fair Queueing)”. 2023年7月1日閲覧。
  6. ^ Deadline IO scheduler tunables”. 2023年7月1日閲覧。
  7. ^ Early Windows
  8. ^ Sriram Krishnan. “A Tale of Two Schedulers Windows NT and Windows CE”. 2012年7月22日時点のオリジナルよりアーカイブ。2012年7月19日閲覧。
  9. ^ Inside the Windows Vista Kernel: Part 1, Microsoft Technet
  10. ^ 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”. 2008年12月7日時点のオリジナルよりアーカイブ。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

関連項目

外部リンク


スケジューリング

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

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

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

※この「スケジューリング」の解説は、「リアルタイムオペレーティングシステム」の解説の一部です。
「スケジューリング」を含む「リアルタイムオペレーティングシステム」の記事については、「リアルタイムオペレーティングシステム」の概要を参照ください。

ウィキペディア小見出し辞書の「スケジューリング・」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ

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

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。



スケジューリング・と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「スケジューリング・」の関連用語

スケジューリング・のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



スケジューリング・のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
実用日本語表現辞典実用日本語表現辞典
Copyright © 2025実用日本語表現辞典 All Rights Reserved.
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのスケジューリング (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのリアルタイムオペレーティングシステム (改訂履歴)、プロジェクト管理ソフトウェア (改訂履歴)、Background Intelligent Transfer Service (改訂履歴)、グラフ彩色 (改訂履歴)、リソーススタベーション (改訂履歴)、リアルタイムシステム (改訂履歴)、ワールドニュース・ナウ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS