Wesloo
すべてのトピックトピック

オペレーティングシステム

cpu スケジューリング アルゴリズムの仕組み

要点

OSはCPUを1タスクずつしか実行できないため、ready queueにあるプロセスから次に実行するものを選ぶ。cpu スケジューリング アルゴリズムは、CPU利用率や待ち時間、応答時間などの指標をもとにこの選択を決める。プリエンプティブ方式とノンプリエンプティブ方式があり、FCFS、SJF、SRTF、Priority、Round Robinなどが用途に応じて使われる。

ポイント

  • 1つのCPUコアは同時に1つのタスクしか実行できない
  • スケジューラはready queueから次に実行するプロセスを選ぶ
  • プリエンプティブ方式は実行中タスクを中断できる
  • ノンプリエンプティブ方式はタスクがCPUを解放するまで待つ
  • 評価にはCPU利用率、スループット、ターンアラウンド時間、待ち時間、応答時間を使う

OSはcpu スケジューリング アルゴリズムで、次にCPUを使うプロセスを決めます。CPUコアは一度に1タスクしか実行できないので、待機中のプログラムがあるときはready queueから次を選びます。この選択を適切に行うことで、CPUを遊ばせず、待ち時間や応答時間を抑えられます。

cpu スケジューリング アルゴリズムの基本

CPUが空いたとき、ready queueのプロセスから少なくとも1つを実行するのがCPUスケジューリングです。CPUスケジューラが、実行準備のできたプロセスをメモリ上から選びます。狙いはCPU利用率を上げ、応答時間や待ち時間を短くすることです。

ノンプリエンプティブ方式では、プロセス終了時や実行状態から待機状態への切り替え時にCPUが解放されます。実行中のプロセスを途中で止めることはありません。

プリエンプティブ方式とノンプリエンプティブ方式

プリエンプティブ方式では、タスクに優先度が付くことが多く、高い優先度のタスクを先に実行するため、実行中の低い優先度のタスクを止められます。止められたタスクは、高い優先度のタスク完了後に再開します。この方式では、タイマーなどの特殊なハードウェアが必要になることがあります。

ノンプリエンプティブ方式では、CPUは特定プロセスに割り当てられ、そのプロセスがコンテキストスイッチや終了でCPUを解放するまで続きます。特殊なハードウェアが不要なので、さまざまなハードウェア環境で使えます。

代表的なアルゴリズム

OSでは、システムの目的に合わせて複数の方式が使われます。First Come First Serveは到着順に処理します。Shortest Job Firstは実行時間が短いジョブを優先します。Shortest Remaining Time Firstは、残り実行時間が一番短いプロセスを次に実行します。Priority Schedulingは、優先度に従ってタスクを選びます。Round Robinは各プロセスに順番にCPU時間を与え、飢餓状態を避けやすくします。

FCFSは実装が単純ですが、実行時間が長いプロセスが先に来ると後続プロセスの待ち時間が長くなることがあります。SJFは平均待ち時間を短くしやすい一方で、長いジョブが後回しになることがあります。SRTFは残り時間の短いプロセスを優先し、対話的な処理に向く場合があります。

Priority Schedulingでは、重要なタスクを先に実行できますが、優先度の低いタスクが長く待つ可能性があります。Round Robinは各プロセスに順番にCPU時間を配分するので、公平性を重視するシステムで使われます。Round Robinは単独では完結せず、他の方式と組み合わせて使われることがあります。

方式選択基準特徴
FCFS到着順単純で理解しやすい
SJF実行時間が短い順短いジョブを優先
SRTF残り時間が短い順残り時間が短いプロセスを優先
Priority優先度重要なタスクを先に実行
Round Robin順番にCPU時間を配分公平性を重視

マルチコアCPUでは複数プロセスを同時に実行できるため、スケジューリングには各コアへのタスク配分も含まれます。Windows、Linux、AndroidなどのOSは、性能目標や設計に合わせて異なるアルゴリズムを使います。時分割や優先度ベースの方式がその例です。

評価指標

方式を選ぶときは、次の指標を比較します。

  • CPU利用率: CPUをできるだけビジー状態に保つ度合い。理論上は0から100%ですが、実システムでは負荷に応じて40から90%程度になることがあります。
  • スループット: 単位時間あたりに完了したプロセス数。
  • ターンアラウンド時間: プロセスが到着してから完了するまでの時間。メモリ待ち、ready queue待ち、CPU使用、I/O待ちを含みます。
  • 待ち時間: ready queueで待機した時間。スケジューリングは実行開始後の完了時間には影響しません。
  • 応答時間: 要求を出してから最初の応答が返るまでの時間。対話的なシステムで重要です。

公平性も重要な観点です。どのプロセスもCPU時間を得られるようにし、1つのタスクがCPUを独占しないようにします。複雑なアルゴリズムを単純なシステムに使う、またはリアルタイム環境に基本的な方式だけを使うと、性能が悪くなることがあります。

待ち時間とターンアラウンド時間の見方

Gantt chartを使うと、各プロセスの実行順序と時間幅を横軸に並べて、待ち時間やターンアラウンド時間を計算できます。スケジューリングは実行開始後の処理時間そのものは変えないため、改善できるのは主に待ち時間です。このため、方式の違いはready queueでの待機に強く現れます。

関連ページ

プロセス管理やメモリ管理と合わせて理解すると、仮想メモリ 仕組み:ページング方式の図解やモノリシックカーネル マイクロカーネル 違いと設計の要点も参考になります。OS全体の役割はOS とは 仕組み:役割と起動の流れで確認できます。

よくある質問

プリエンプティブ方式とノンプリエンプティブ方式の違いは何か

プリエンプティブ方式は実行中のタスクを一時停止して優先度の高いタスクを先に実行できます。ノンプリエンプティブ方式はプロセスが終了するか待機状態に切り替わるまでCPUを解放しません。

FCFSとは何か

First Come First Serveの略で、プロセスが到着した順にCPUを割り当てる方式です。実装は単純ですが、長いプロセスが先に来ると後続の待ち時間が長くなることがあります。

Round Robinが使われる理由は何か

各プロセスに順番にCPU時間を配分し、公平性を高めやすいためです。飢餓状態を避けやすく、マルチタスク環境でよく使われます。

CPUスケジューリングの評価指標には何があるか

CPU利用率、スループット、ターンアラウンド時間、待ち時間、応答時間があります。方式を選ぶときは、これらの指標とシステムの目的を比較します。

関連ページ

  • デバイスドライバ 仕組み:OSとハードウェアの橋渡し

    デバイスドライバは、OSとハードウェアの間で命令と結果をやり取りするソフトウェアです。OSは機器の詳細を知らなくても、ドライバが翻訳役となって印刷や音声出力などを実行します。

  • RTOS 汎用OS 違い:リアルタイム性と特徴の比較

    RTOSは期限内の決定論的応答を優先し、汎用OSは柔軟性とスループットを優先する。両者はOSの基本原則を共有するが、設計優先順位と能力が大きく異なる。選択は、アプリケーションが厳密なタイミング制約を必要とするか、一般的な計算能力を必要とするかに依存する。

  • OS デッドロック 原因 対策と回避策

    デッドロックは、複数のプロセスが互いに資源を待ち続ける状態である。発生には4つの必要条件が同時に成立する必要があり、対策は防止、回避、検出と回復、無視に分かれる。

  • OS 起動プロセス 仕組み:電源からOS起動まで

    電源投入後、OSがメモリに読み込まれて使える状態になるまでの連鎖的な処理がOSの起動プロセスです。冷起動と暖起動ではハードウェア初期化の範囲が異なり、BIOS/UEFI、ブートローダー、カーネル、initが順に動作します。

  • 32 ビットと 64 ビットの違い os:メモリと互換性

    32ビットOSと64ビットOSの違いは、扱えるメモリ量とデータ幅にあります。32ビットは最大4GB前後、64ビットはそれを大きく超えるメモリを扱えます。選択時はCPU、OS、ソフト、ドライバの互換性を確認します。

  • 仮想メモリ 仕組み:ページング方式の図解

    仮想メモリは、各プロセスに独立したアドレス空間を与え、物理メモリの容量を超える領域を安全に扱うためのOSの機能です。ページング方式では、アドレス空間を固定長のページに分け、必要なページだけを物理メモリへ載せます。

このページの作成方法

執筆の前に、下記の情報源でテーマを調査しました。その後、自動の品質チェックを通過しています。

このページの誤りを報告する