オペレーティング システムのプロセス スケジューリング アルゴリズムとは何ですか?

スケジューラは、次に実行するプロセスを選択する役割を担うオペレーティング システム カーネルの一部です。したがって、スケジューリング戦略によって、オペレーティング システムが非リアルタイム オペレーティング システムかリアルタイム オペレーティング システムかが決まります。現在、オペレーティング システムには多くの種類がありますが、プロセス スケジューリング アルゴリズムは次の種類にまとめることができます。

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

先着順のスケジュール戦略は非常にシンプルです。レディキューを維持します。各スケジューリングは、レディキューから最初にキューに入るプロセスを選択し、それにプロセッサを割り当てて、動作させます。プロセスは完了するかイベントによってブロックされるまで実行され、その後プロセッサを放棄します。

ショートプロセスファースト（SPF）スケジューリングアルゴリズム

Short Process First (SPF) スケジューリング アルゴリズムは、実行時間の推定値が最も短いプロセスを準備キューから選択し、そのプロセスにプロセッサを割り当てて、そのプロセスが完了するまで直ちに実行するか、イベントが発生してプロセッサがブロックされて放棄されたときに再スケジュールします。

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

緊急のプロセスに対処し、優先的に実行できるようにするために、優先スケジューリング アルゴリズムが導入されています。このスケジューリング アルゴリズムは、リアルタイム オペレーティング システムで使用できます。プロセスのスケジューリングが発生すると、アルゴリズムは準備完了キュー内で優先度が最も高いプロセスにプロセッサを割り当てます。

アルゴリズムには 2 つの種類があります。

非プリエンプティブ優先度アルゴリズム: このモードでは、システムが準備キュー内の最も優先度の高いプロセスにプロセッサを割り当てると、プロセスは終了するまで実行を継続するか、プロセッサを積極的に放棄し、システムがプロセッサを最も優先度の高い別のプロセスに割り当てます。このアルゴリズムは、リアルタイム要件が高くない一部のオペレーティング システムで使用できます。

プリエンプティブ優先度スケジューリング アルゴリズム: このモードでは、システムはプロセッサを最も優先度の高いプロセスに割り当てて実行します。ただし、操作中に優先度の高いプロセスが準備キューに出現した場合、システムは現在実行中のプロセスを直ちに停止し、新しく追加された優先度の高いプロセスにプロセッサを再割り当てします。したがって、このモードではリアルタイム要件をより適切に満たすことができるため、リアルタイム要件が高いシステムでよく使用されます。

優先度の高いプロセスがリソース不足のためにブロックされ、優先度の低いプロセスがリソースを解放するまで待機していると想像してください。優先度の低いプロセスは、CPU 時間が少なくなります。優先度が 2 つのプロセスの間にあり、共有リソースを必要としないタスクがある場合、優先度が中程度のプロセスがこれら 2 つのプロセスよりも優先され、CPU 時間が割り当てられます。優先度の高いプロセスがリソースを待機している間にブロックせず、ビジー ループする場合、優先度の低いプロセスは CPU 時間に関して優先度の高いプロセスと競合できず、実行できず、リソースを解放できないため、リソースを取得できない可能性があります。その結果、優先度の高いプロセスはリソースを取得できず、前進し続けることになります。この現象を「優先順位の逆転」と呼びます。

上記の問題をどのように解決すればよいでしょうか?

方法は3つあります。

優先度の上限を設定し、クリティカル セクションに高い優先度を与えます。クリティカル セクションに入るすべてのプロセスは、この高い優先度を取得します。クリティカル セクションに入ろうとする他のプロセスの優先度がこの高い優先度よりも低い場合、優先度の逆転は発生しません。

優先度の継承: 優先度の高いプロセスが優先度の低いプロセスが保持しているリソースを待機している場合、優先度の低いプロセスは、優先度の高いプロセスの優先度レベルを一時的に取得します。共有リソースを解放した後、優先度の低いプロセスは元の優先度レベルに戻ります。組み込みシステム VxWorks はこの戦略を採用しています。

3 番目の方法は、クリティカル セクションを保護するために、クリティカル セクションの割り込みを無効にすることです。この戦略を使用するシステムには、プリエンプティブ優先度と割り込み無効優先度の 2 つの優先度しかありません。前者は実行中の一般的なプロセスの優先度であり、後者はクリティカル セクションで実行されているプロセスの優先度です。マーズ・パスファインダーの失敗は、クリティカル・セクションで実行されていた気象ミッションが、中断された通信ミッションによって優先されたために発生しました。クリティカル・セクションに割り込み禁止保護が設けられていれば、この問題は発生しなかったでしょう。

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

CPU を集中的に使用するシステムでは、短いプロセス優先度アルゴリズムの方が適しています。ただし、長いプロセスの実行時間は保証されません。この問題を解決するにはどうすればよいでしょうか? 動的な優先順位を導入することはできますか? 簡単に言えば、待機時間が長くなるほど、優先順位が高くなります。それで、しばらく待てば、必ず走る番が来るでしょう。ただし、優先度を動的に計算するアルゴリズムには CPU リソースが必要です。

タイムスライスの回転

早期タイムスライス ラウンドロビン方式では、システムはすべての準備完了プロセスを先着順にキューに配置します。スケジュールが行われるたびに、キューの最初のプロセスに CPU が割り当てられ、1 つのタイムスライスで実行するように命令されます。タイムスライスのサイズは、数ミリ秒から数百ミリ秒の範囲です。実行タイムスライスが使い果たされると、タイマーがクロック割り込み要求を送信し、スケジューラはこの信号を使用してプロセスの実行を停止し、それを準備キューの最後に送信します。その後、プロセッサは準備キューの新しい先頭プロセスに割り当てられ、タイムスライスを実行できるようになります。これにより、準備完了キュー内のすべてのプロセスが、指定された時間内にプロセッサ実行時間のタイムスライスを取得できるようになります。つまり、システムは指定された時間内にすべてのユーザー要求に応答できます。

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

これまで説明したスケジューリング アルゴリズムにはすべて一定の制限があります。たとえば、短いプロセス優先スケジューリング アルゴリズムは、短いプロセスのみを処理し、長いプロセスは無視します。マルチレベル フィードバック キュー スケジューリング アルゴリズムは、さまざまなプロセスのニーズを満たすことができるバランスの取れたアルゴリズムです。したがって、これは現時点ではより優れたプロセス スケジューリング アルゴリズムです。

複数の準備完了キューを設定し、各キューに異なる優先順位を設定します。最初のキューの優先度が最も高く、2 番目のキューの優先度が 2 番目に高くなります。キューの優先度が高いほど、タイムスライスは短くなります。

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

スケジューラは、最初のキューがアイドル状態の場合にのみ 2 番目のキューのプロセスが実行されるようにスケジュールします。また、スケジューラは、1 番目から (i-1) 番目のキューがすべて空の場合にのみ i 番目のキューのプロセスが実行されるようにスケジュールします。プロセッサが i 番目のキューのプロセスにサービスを提供しているときに、新しいプロセスがより高い優先度のキュー (1 から (i-1) までの任意のキュー) に入ると、新しいプロセスは実行中のプロセスのプロセッサをプリエンプトします。つまり、スケジューラは実行中のプロセスを i 番目のキューの最後に戻し、プロセッサを新しい高優先度プロセスに割り当てます。以下のように表示されます。

参照する

https://blog.csdn.net/qq_35642036/article/details/82809812、Yuan Lijun 氏はこの記事を参照しました。

要約する

この記事では、いくつかのプロセス スケジューリング アルゴリズムについて説明します。プロセス スケジューリング アルゴリズムに興味のある方の参考になれば幸いです。もちろん、この記事では説明されていない、抽選スケジューリング、単一比率スケジューリングなどのスケジューリング アルゴリズムもあります。