オペレーティングシステムに関して、一般的に使用されているスケジューリングアルゴリズムをいくつ知っていますか?

オペレーティングシステムには多くのスケジューリングアルゴリズムがあり、ジョブスケジューリングに適したもの、プロセススケジューリングに適したもの、両方に適したものがあります。以下に、一般的に使用されるいくつかのスケジューリングアルゴリズムを紹介します。

[[258769]]

先着順 (FCFS) スケジューリングアルゴリズム

FCFS スケジューリングアルゴリズムは、ジョブスケジューリングとプロセススケジューリングの両方に使用できる最も単純なスケジューリングアルゴリズムです。ジョブスケジューリングでは、アルゴリズムは毎回、バックアップジョブキューから最初にキューに入る 1 つまたは複数のジョブを選択し、それらをメモリにロードし、必要なリソースを割り当て、プロセスを作成して、それらを準備完了キューに入れます。

プロセススケジューリングでは、FCFS スケジューリングアルゴリズムは、毎回、準備完了キューからキューに入る最初のプロセスを選択し、それにプロセッサを割り当て、完了するか何らかの理由でブロックされるまで、それを動作させます。

次の例は、FCFS スケジューリングアルゴリズムのパフォーマンスを示しています。システム内に 4 つのジョブがあり、それぞれの送信時間が 8、8.4、8.8、9、実行時間がそれぞれ 2、1、0.5、0.2 であるとします。システムは FCFS スケジューリングアルゴリズムを使用します。このジョブグループの平均待機時間、平均ターンアラウンド時間、平均加重ターンアラウンド時間を表 2-3 に示します。

平均待ち時間 t = (0+1.6+2.2+2.5)/4=1.575

平均所要時間 T = (2+2.6+2.7+2.7)/4=2.5

平均加重回転時間 W = (1+2.6+5.13.5)/4=5.625

FCFS スケジューリングアルゴリズムは非プリエンプティブアルゴリズムです。表面的には、すべてのジョブに対して公平ですが、長いジョブが最初にシステムに到着すると、後続の多くの短いジョブが長時間待機することになります。したがって、タイムシェアリングシステムやリアルタイムシステムの主なスケジューリング戦略として使用することはできません。しかし、他のスケジュール戦略と組み合わせて使用されることもよくあります。たとえば、優先度をスケジューリング戦略として使用するシステムでは、同じ優先度を持つ複数のプロセスが FCFS 原則に従って処理されることがよくあります。

FCFS スケジューリングアルゴリズムの特徴は、アルゴリズムは単純だが効率が低いこと、長いジョブには適しているが短いジョブには適していないこと (SJF および高応答率と比較して)、CPU がビジーなジョブには適しているが I/O がビジーなジョブには適していないことです。

最短ジョブ優先 (SJF) スケジューリングアルゴリズム

短いジョブ（プロセス）優先スケジューリングアルゴリズムとは、短いジョブ（プロセス）のスケジューリングを優先するアルゴリズムを指します。 Short Job First (SJF) スケジューリングアルゴリズムは、バックアップキューから推定実行時間が最も短い 1 つ以上のジョブを選択し、実行のためにメモリにロードします。 Short Process First (SPF) スケジューリングアルゴリズムは、実行時間が最短と推定されるプロセスを準備キューから選択し、そのプロセスにプロセッサを割り当てて即時実行します。プロセッサは、完了するかイベントによってブロックされるまで解放されません。

たとえば、表 2-3 に示すジョブセットを考えます。システムがショートジョブ優先スケジューリングアルゴリズムを採用した場合、平均待機時間、平均ターンアラウンド時間、平均加重ターンアラウンド時間は表 2-4 に示されます。

平均待ち時間 t = (0+2.3+1.4+1)/4=1.175

平均回転時間 T = (2+3.3+1.9+1.2)/4=2.1

平均加重回転時間 W = (1+3.3+3.8+6)/4=3.525

SJF スケジューリングアルゴリズムには無視できない欠点もあります。

このアルゴリズムは長時間ジョブには適していません。表 2-3 および表 2-4 からわかるように、SJF スケジューリングアルゴリズムでは長時間ジョブのターンアラウンド時間が長くなります。さらに深刻なのは、長いジョブがシステムのバックアップキューに入ると、スケジューラは常に短いジョブ (後から入ってくるジョブも含む) を優先するため、長いジョブは長時間スケジュールされないことです (「飢餓」現象。これを「デッドロック」と区別するように注意してください。後者はシステムの循環待機であり、前者はスケジューリング戦略の問題です)。
このアルゴリズムはジョブの緊急性をまったく考慮しないため、緊急ジョブがタイムリーに処理されることを保証できません。
ジョブの長さはユーザーが提供する推定実行時間によってのみ決定され、ユーザーは意図的または無意識のうちにジョブの推定実行時間を短縮する可能性があるため、アルゴリズムは短いジョブを真に優先できない可能性があります。

SJF スケジューリングアルゴリズムでは、平均待機時間と平均ターンアラウンド時間が最も短くなることに注意してください。

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

優先度スケジューリングアルゴリズムは、優先度スケジューリングアルゴリズムとも呼ばれます。このアルゴリズムは、ジョブスケジューリングとプロセススケジューリングの両方に使用できます。このアルゴリズムの優先度は、ジョブ実行の緊急性を表すために使用されます。

ジョブスケジューリングでは、優先度スケジューリングアルゴリズムによって、バックアップジョブキューから優先度が最も高い 1 つまたは複数のジョブが毎回選択され、メモリにロードされ、必要なリソースが割り当てられ、プロセスが作成されて準備完了キューに配置されます。プロセススケジューリングでは、優先度スケジューリングアルゴリズムによって、毎回、準備完了キューから優先度が最も高いプロセスが選択され、プロセッサが割り当てられ、処理が開始されます。

新しい高優先度プロセスが実行中のプロセスをプリエンプトできるかどうかに応じて、スケジューリングアルゴリズムは次のように分けられます。

非プリエンプティブな優先スケジューリングアルゴリズム。プロセスがプロセッサ上で実行されているときに、より重要または緊急のプロセスが準備キューに入っても、実行中のプロセスは、自身の理由 (タスクの完了またはイベントの待機) により自発的にプロセッサを放棄するまで実行を継続し、その後、プロセッサはより重要または緊急のプロセスに割り当てられます。
プリエンプティブ優先スケジューリングアルゴリズム。プロセスがプロセッサ上で実行されているときに、より重要または緊急のプロセスが準備キューに入ると、実行中のプロセスは直ちに一時停止され、プロセッサはより重要または緊急のプロセスに割り当てられます。

プロセスの作成後にプロセスの優先度を変更できるかどうかによって、プロセスの優先度は次の 2 種類に分けられます。

静的優先度。優先度はプロセスの作成時に決定され、プロセスの実行時間中は変更されません。静的優先度を決定する主な基準は、プロセスの種類、リソースに対するプロセス要件、およびユーザー要件です。
動的優先度。プロセス実行中は、プロセス状況の変化に応じて優先度が動的に調整されます。優先度を動的に調整する主な基準は、プロセスが CPU を占有する時間の長さと、準備完了プロセスが CPU を待機する時間の長さです。

高応答率優先スケジューリングアルゴリズム

高応答率優先スケジューリングアルゴリズムは、主にジョブスケジューリングに使用されます。このアルゴリズムは、各ジョブの待機時間と推定実行時間を考慮しながら、FCFS スケジューリングアルゴリズムと SJF スケジューリングアルゴリズムを総合的にバランスさせたものです。ジョブがスケジュールされるたびに、まずバックアップジョブキュー内の各ジョブの応答率が計算され、応答率が最も高いジョブが選択されて実行されます。

応答比率の変化法則は次のように記述できます。

式によれば：

ジョブの待機時間が同じ場合、必要なサービス時間が短いほど応答率が高くなり、短いジョブに有利になります。
必要なサービス時間が同じ場合、ジョブの応答率は待機時間によって決まります。待機時間が長いほど応答率が高くなるため、先着順で実行されます。
長いジョブの場合、待機時間が長くなるにつれてジョブの応答率が向上します。待機時間が十分に長い場合、応答率を非常に高いレベルまで高めることができるため、プロセッサも取得できます。空腹状態を乗り越えて長い宿題をやり遂げました。

タイムスライスラウンドロビンスケジューリングアルゴリズム

タイムスライスラウンドロビンスケジューリングアルゴリズムは、主にタイムシェアリングシステムに適用されます。このアルゴリズムでは、システムはすべての準備完了プロセスを到着時間順にキューに配置します。プロセススケジューラは常に準備完了キューの最初のプロセスを選択して実行します。つまり、先着順の原則ですが、実行できるのは 100 ミリ秒などのタイムスライスのみです。タイムスライスを使用した後、プロセスが操作を完了していなくても、(奪われた) プロセッサを次の準備完了プロセスに解放する必要があり、奪われたプロセスは準備完了キューの最後尾に戻り、再度キューイングされて、再度実行を待機します。

タイムスライスラウンドロビンスケジューリングアルゴリズムでは、タイムスライスのサイズがシステムパフォーマンスに大きな影響を与えます。タイムスライスが十分に大きく、すべてのプロセスを 1 つのタイムスライス内で実行できる場合、タイムスライスラウンドロビンスケジューリングアルゴリズムは先着順スケジューリングアルゴリズムに退化します。タイムスライスが小さすぎると、プロセッサはプロセス間を頻繁に切り替えるため、プロセッサのオーバーヘッドが増加し、ユーザープロセスの実行に実際に使用される時間が短縮されます。したがって、タイムスライスのサイズは適切に選択する必要があります。

タイムスライスの長さは通常、システムの応答時間、準備完了キュー内のプロセス数、システムの処理能力などの要因によって決まります。

マルチレベルフィードバックキュースケジューリングアルゴリズム（以前のアルゴリズムの利点を組み合わせたもの）

マルチレベルフィードバックキュースケジューリングアルゴリズムは、図 2-5 に示すように、タイムスライスラウンドロビンスケジューリングアルゴリズムと優先度スケジューリングアルゴリズムを組み合わせて開発したものです。プロセスの優先度とタイムスライスのサイズを動的に調整することにより、マルチレベルフィードバックキュースケジューリングアルゴリズムは複数のシステム目標を考慮できます。たとえば、短いプロセスはシステムのスループットを向上させ、平均ターンアラウンド時間を短縮するために処理されます。また、I/O タイプのプロセスは、I/O デバイスの使用率を向上させ、応答時間を短縮するために処理されます。同時に、プロセスの実行時間を事前に見積もる必要はありません。

図2-5 マルチレベルフィードバックキュースケジューリングアルゴリズム

マルチレベルフィードバックキュースケジューリングアルゴリズムの実装の考え方は次のとおりです。

1. 複数の準備完了キューを設定し、各キューに異なる優先順位を割り当てる必要があります。第 1 レベルのキューの優先順位が最も高く、次に第 2 レベルのキューの優先順位が続き、残りのキューの優先順位は順に低くなります。

2. 各キュー内のプロセスに割り当てられる実行タイムスライスのサイズも異なります。キューの優先度が高いほど、各プロセスの実行タイムスライスは小さくなります。たとえば、第 2 レベルのキューのタイムスライスは、第 1 レベルのキューのタイムスライスの 2 倍の長さです。...i+1 レベルのキューのタイムスライスは、i レベルのキューのタイムスライスの 2 倍の長さです。

3. 新しいプロセスがメモリに入ると、まず第 1 レベルのキューの最後尾に配置され、FCFS 原則に従ってスケジュールのためにキューに入れられます。プロセスの実行順番が来たら、タイムスライス内に完了できればシステムからの退避準備ができます。タイムスライスの終了時に完了していない場合、スケジューラはプロセスを第 2 レベルキューの最後に転送し、FCFS 原則に従ってスケジューリング実行を待ちます。第 2 レベルキューでタイムスライスの実行後に完了していない場合、同様に第 3 レベルキューに配置されます...など。長いプロセスが第 1 レベルキューから第 n レベルキューに順番に落とされると、タイムスライスローテーション方式で第 n レベルキューで実行されます。

4. スケジューラは、第 1 レベルのキューが空の場合にのみ、第 2 レベルのキューのプロセスが実行されるようにスケジュールします。また、スケジューラは、第 1 レベルから (i-1) レベルのキューがすべて空の場合にのみ、i 番目のレベルのキューのプロセスが実行されるようにスケジュールします。プロセッサが i 番目のレベルのキューでプロセスを実行しており、新しいプロセスがより高い優先度のキュー (1 から (i-1) までの任意のキュー) に入ると、新しいプロセスは実行中のプロセスのプロセッサをプリエンプトします。つまり、スケジューラは実行中のプロセスを i 番目のレベルのキューの最後に戻し、新しく到着したより高い優先度のプロセスにプロセッサを割り当てます。

マルチレベルフィードバックキューの利点は次のとおりです。