CPU スケジューリング Algorithms in Operaティングシステムズ
ナサニエル・ブルックス
⚡ スマートサマリー
CPU スケジューリングは、オペレーティングシステムが次に実行する準備完了プロセスを決定します。ping プロセッサはビジー状態であり、先着順、最短ジョブ優先、優先度、ラウンドロビンなどのアルゴリズムによってパフォーマンスが向上します。
CPU スケジューリングとは何ですか?
CPU スケジューリング CPUスケジューリングとは、他のプロセスが保留状態にある間に、どのプロセスがCPUを使用して実行するかを決定するプロセスです。CPUスケジューリングの主な目的は、CPUがアイドル状態にあるときはいつでも、OSが実行準備完了キューにあるプロセスの中から少なくとも1つを選択して実行できるようにすることです。この選択プロセスはCPUスケジューラによって実行され、メモリ内で実行準備が整っているプロセスの中から1つが選択されます。
CPU スケジューリングの種類
スケジューリング方法には、以下の2種類があります。
プリエンプティブ スケジューリング
プリエンプティブスケジューリングでは、タスクは基本的に優先度に基づいて割り当てられます。場合によっては、優先度の低いタスクがまだ実行中であっても、優先度の高いタスクを優先度の低いタスクより先に実行することが重要な場合があります。優先度の低いタスクは一定時間待機し、優先度の高いタスクの実行が完了すると再開されます。
ノンプリエンプティブなスケジューリング
このスケジューリング方式では、CPUは特定のプロセスに割り当てられます。CPUを占有しているプロセスは、コンテキストを切り替えるか、終了することでCPUを解放します。プリエンプティブスケジューリングのように特別なハードウェア（例えばタイマー）を必要としないため、様々なハードウェアプラットフォームで使用できる唯一の方式です。
スケジューリングは、どのような場合にプリエンプティブになり、どのような場合に非プリエンプティブになるのか？
スケジューリングがプリエンプティブか非プリエンプティブかを判断するには、次の4つのパラメータを考慮してください。
- プロセスは実行状態から待機状態に切り替わります。
- 特定のプロセスが実行状態から準備完了状態に切り替わる。
- 特定のプロセスが待機状態から準備完了状態に切り替わる。
- プロセスは実行を完了し、終了します。
条件1と条件4のみが適用される場合、そのスケジューリングは非プリエンプティブと呼ばれます。その他のすべてのスケジューリング状況はプリエンプティブです。
重要なCPUスケジューリング用語
- バースト時間/実行時間: プロセスが実行を完了するのに要する時間。実行時間とも呼ばれる。
- 到着時刻： プロセスが準備完了状態に入る時刻。
- 終了時刻： プロセスが完了し、システムから終了する時刻。
- マルチプログラミング: メモリ上に同時に存在できるプログラムの数。
- 仕事： ユーザーとのやり取りが一切ないタイプのプログラム。
- ユーザー： ユーザーとの対話が可能なプログラムの一種。
- プロセス： ジョブとユーザーの両方に使用される参照情報。
- CPU/IOバーストサイクル: プロセス実行の特徴を表し、CPUとI/Oの処理が交互に行われます。通常、CPU処理時間はI/O処理時間よりも短くなります。
CPU スケジューリング基準
CPU スケジューリング アルゴリズムは、次のものを最大化および最小化しようとします。
最大化します
CPU使用率： CPU使用率は、オペレーティングシステムがCPUを常に最大限に活用し続けるようにするための主要なタスクです。その範囲は0%から100%までですが、RTOSの場合は、低レベルシステムで40%、高レベルシステムで90%程度になります。
スループット： 単位時間あたりに実行を完了するプロセスの数をスループットと呼びます。つまり、CPUがプロセスを実行している間は、何らかの処理が行われており、単位時間あたりに完了する処理量をスループットと呼びます。
最小限に抑える
待ち時間： 待ち時間とは、特定のプロセスが準備完了キューで待機しなければならない時間のことです。
反応時間： これは、リクエストが送信されてから最初のレスポンスが生成されるまでの時間です。
ターンアラウンドタイム： ターンアラウンドタイムとは、特定のプロセスを実行するのにかかる時間のことです。これは、メモリへのロード待ち、キューでの待機、CPU上での実行といった、合計時間を指します。プロセスの送信から完了までの期間がターンアラウンドタイムです。
インターバルタイマー
タイマー割り込みは、プリエンプションと密接に関係する方法です。 特定のプロセスが CPU 割り当てを取得すると、タイマーが指定された間隔に設定される場合があります。 タイマー割り込みとプリエンプションはどちらも、CPU バーストが完了する前にプロセスに CPU を強制的に返します。
ほとんどのマルチプログラム対応オペレーティングシステムは、プロセスがシステムを永久に占有してしまうのを防ぐために、何らかのタイマーを使用しています。
ディスパッチャーとは何ですか?
ディスパッチャは、プロセスにCPUの制御権限を与えるモジュールです。ディスパッチャは高速である必要があり、コンテキストスイッチのたびに実行されなければなりません。ディスパッチレイテンシとは、CPUスケジューラが1つのプロセスを停止し、別のプロセスを開始するために必要な時間のことです。
ディスパッチャーが実行する機能：
- コンテキストの切り替え。
- ユーザーモードに切り替えます。
- 新しくロードされたプログラム内の正しい場所に移動します。
CPU スケジューリングの種類 Algorithms
大きく分けてXNUMX種類あります プロセススケジューリングアルゴリズム:
- 先入れ先出し（FCFS）
- 最短ジョブ優先 (SJF) スケジューリング
- 最短残り時間
- 優先スケジューリング
- ラウンドロビンスケジューリング
- マルチレベルキューのスケジューリング
スケジュール管理 Algorithms
先着順
FCFSとは 先着順これは最も簡単でシンプルなCPUスケジューリングアルゴリズムです。このアルゴリズムでは、CPUを要求するプロセスが最初にCPU割り当てを受けます。このスケジューリング方法は、FIFOキューで管理できます。
プロセスが準備完了キューに入ると、そのプロセス制御ブロック（PCB）はキューの末尾にリンクされます。そのため、CPUが空いたときには、キューの先頭にあるプロセスに割り当てられるべきです。
FCFS方式の特徴
- これは非プリエンプティブなスケジューリングアルゴリズムです。
- ジョブは常に先着順で実行されます。
- 実装と使用は簡単です。
- ただし、この方法はパフォーマンスが低く、一般に待ち時間が非常に長くなります。
最短残り時間
SRTはShortest Remaining Time（最短残存時間）の略です。SJFプリエンプティブスケジューリングとも呼ばれます。この方式では、プロセスは完了に最も近いタスクに割り当てられます。この方式により、新しい準備完了状態のプロセスが古いプロセスの完了を遅らせることを防ぎます。
SRTスケジューリング方式の特徴
- この方法は主に、短時間で完了するジョブを優先する必要があるバッチ処理環境で用いられます。
- これは、必要なCPU時間が不明な共有システムで実装するには理想的な方法ではありません。
- 各プロセスには、次のCPUバーストの長さが関連付けられているため、オペレーティングシステムはこれらの長さを利用して、可能な限り短い時間でプロセスをスケジュールします。
優先順位に基づいたスケジューリング
優先スケジューリング これは、優先度に基づいてプロセスをスケジュールする方法です。この方法では、スケジューラは優先度に応じて処理するタスクを選択します。
優先度スケジューリングは、OSが優先度割り当てを行う際にも役立ちます。優先度の高いプロセスが優先的に実行され、優先度が同じジョブはラウンドロビン方式または先着順（FCFS）で実行されます。優先度は、メモリ要件、時間要件、その他の要因に基づいて決定されます。
ラウンドロビンスケジューリング
ラウンドロビン これは、最も古く、最もシンプルなスケジューリングアルゴリズムの1つです。このアルゴリズムの名前は、各人が順番に均等にタスクを受け取るというラウンドロビン方式に由来しています。主にマルチタスクシステムのスケジューリングに使用されます。この方法は、プロセスの飢餓状態のない実行を実現するのに役立ちます。
ラウンドロビンスケジューリングの特徴
- ラウンドロビン方式は、時間制御型のハイブリッドモデルです。
- 特定のタスクの処理に割り当てられる時間枠は最小限であるべきです。ただし、処理内容によって異なる場合があります。
- これは、各プロセスに特定の時間制限内で応答するタイムシェアリングシステムのように動作します。
最短のジョブが最初
SJF（最短ジョブ優先）は、実行時間が最も短いプロセスを優先的に実行するスケジューリングアルゴリズムです。このスケジューリング方式は、プリエンプティブ方式と非プリエンプティブ方式のどちらでも適用可能です。これにより、実行待ちの他のプロセスの平均待ち時間を大幅に短縮できます。
SJFスケジューリングの特徴
- 各作業には、完了に必要な時間単位が割り当てられています。
- この方式では、CPUが利用可能な場合、完了時間が最も短い次のプロセスまたはジョブが最初に実行されます。
- これは非先制的なポリシーで実装されています。
- このアルゴリズムは、ジョブの完了を待つことがそれほど重要ではないバッチ処理に適しています。
- これは、処理時間が短いジョブを優先的に実行することで、ジョブの生産性を向上させます。
複数レベルのキューのスケジューリング
このアルゴリズムでは、準備完了キューを複数の独立したキューに分割します。この方法では、プロセスの優先度、メモリサイズなど、プロセスの特定の特性に基づいて、プロセスがキューに割り当てられます。
しかし、これは独立したスケジューリングアルゴリズムではなく、ジョブをスケジュールするために他の種類のアルゴリズムを使用する必要がある。
多段階キューのスケジューリングの特性
- 共通の特性を持つプロセスについては、複数のキューを維持する必要があります。
- 各キューはそれぞれ独自のスケジューリングアルゴリズムを持つことができる。
- 各キューには優先順位が割り当てられます。
スケジューリングアルゴリズムの目的
スケジュール アルゴリズムを使用する理由は次のとおりです。
- CPU は効率を向上させるためにスケジューリングを使用します。
- これは、競合するプロセス間でリソースを割り当てるのに役立ちます。
- マルチプログラミングを用いることで、CPUの最大限の活用が可能となる。
- 実行予定のプロセスは、準備完了キューに格納されます。
