図解による古典的なプロセススケジューリングアルゴリズム

[[382804]]

この記事はWeChatの公開アカウント「Flying Veal」から転載したもので、著者はFeitian Vealです。記事を転載する場合は飛天牛肉公式アカウントまでご連絡ください。

記事の写真の多くは、私が大学院入試の準備をしていたときに受講したオンラインコースのものです。Bilibiliで今でも見つけることができるはずです。王道大学院入試が制作したオペレーティングシステムシリーズは、試験に適していますが、知識のポイントが詳細に説明されすぎていて、細部までカバーされているため、春と秋の採用には適していません。いくつかの章を選んで読むことができます。全文のマインドマップは以下のとおりです。

1. スケジュールの概念

CPU に実行すべきタスクが多数ある場合、リソースが限られているため、同時にすべてを実行することはできません。これには、これらのタスクが処理される順序を決定するためのいくつかのルールを確立する必要があり、これが「スケジューリング」によって研究される問題です。次に説明するプロセス スケジューリングの他に、ジョブ スケジューリング、メモリ スケジューリングなどがあります。

プロセスの 3 つの状態モデルを確認しましょう。

• 「実行中」状態: プロセスは CPU を占有し、実行中です。
• 「準備完了」: プロセスは実行準備が整っており、システムが実行のために CPU を割り当てるのを待機しています。
• 「ブロッキング状態」/ 待機状態 (wait): プロセスは実行条件を満たしておらず、特定のイベントの完了を待機しています。

いわゆるプロセススケジューリングとは、プロセスの同時実行を実現するために、「一定のアルゴリズムに従ってプロセスの準備完了キュー（ブロッキング）からプロセスを選択し、それに CPU を割り当てて実行させる」ことです。これはオペレーティング システムにおける最も基本的な (最下位レベルの) スケジューリング タイプであり、一般的なオペレーティング システムではプロセス スケジューリングを構成する必要があります。プロセスのスケジューリング頻度は非常に高く、通常は数十ミリ秒ごとに 1 回です。

2. 非プリエンプティブプロセススケジューリングアルゴリズム

いわゆる非プリエンプティブとは、プロセスの実行中は、プロセスが完了するかイベントによってブロックされるまで実行が継続され、その後 CPU が他のプロセスに渡されることを意味します。

同様に、プリエンプティブとは、プロセスの実行中にそのプロセスを中断して、CPU を他のプロセスに渡すことができることを意味します。

①先着順FCFS

先着順 (FCFS) スケジューリング アルゴリズム: プロセスが到着した順にスケジュールします。つまり、「最初に到着したプロセスが最初にスケジュールされます」。つまり、待機時間が長いほど、優先度が高くなります。

利点: 公平性、シンプルなアルゴリズムの実装

デメリット: 短いプロセスには適していません。長いプロセスの後ろにある短いプロセスは、長時間待機する必要があります。短いプロセスの応答時間が長すぎると、ユーザーのインタラクション エクスペリエンスが低下します。

②最短ジョブファーストSJF

最短ジョブ優先 (SJF) スケジューリング アルゴリズム: 「スケジューリングのたびに、到着したプロセスのうち実行時間が最も短いプロセスを選択します。」

最短ジョブ優先アルゴリズムは、先着順の正反対です。先着順は短いプロセスには不利ですが、最短ジョブ優先アルゴリズムは長いプロセスには不利です。なぜなら、短いプロセスが続くと、長いプロセスはスケジュールされず、長いプロセスは短いジョブが完了するのを待って飢え死にしてしまう可能性があるからです。

③高応答率優先HRRN

最高応答率次 (HRRN): スケジューリングは、現在実行中のプロセスが CPU を積極的に放棄する (正常/異常完了、またはアクティブ ブロッキング) 場合にのみ必要です。「スケジューリング中、準備完了したすべてのプロセスの応答率が計算され、応答率が最も高いプロセスに CPU が割り当てられます。」応答率 = (プロセス待機時間 + プロセス必要実行時間) / プロセス必要実行時間

3. プリエンプティブプロセススケジューリングアルゴリズム

プリエンプションとは、プロセスの実行中にそのプロセスを中断し、CPU を他のプロセスに渡すことができることを意味します。一般的に、優先原則には、タイムスライス原則、優先原則、およびショートジョブ優先原則の 3 つがあります。

①残り時間最短優先SRTN

Shortest Remaining Time Next (SRTN) アルゴリズムは、最短ジョブ優先アルゴリズムのプリエンプティブ バージョンです。

「新しいプロセスが到着したら、必要な合計実行時間と現在のプロセスの残りの実行時間を比較します。新しいプロセスに必要な時間が短い場合は、現在のプロセスを一時停止して新しいプロセスを実行します。そうでない場合は、新しいプロセスは待機します。」

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

ラウンド ロビン (RR) は、タイム スライス スケジューリング アルゴリズムとも呼ばれます。スケジューラは、通常 10 ミリ秒から 200 ミリ秒のタイム スライスと呼ばれる指定された時間間隔を使用して、毎回、準備完了キューの最初のプロセスに CPU を割り当てます。「準備完了キュー内の各プロセスは、順番にタイム スライスの間実行されます。タイム スライスが使い果たされると、現在実行中のプロセスは CPU リソースを放棄し、準備完了キューの最後に移動して、次のスケジュール ラウンドを待機する必要があります。」したがって、プロセスを完了するには通常、複数回の回転が必要です。

ラウンドロビン スケジューリング アルゴリズムは、各プロセスを平等に扱います。つまり、全員が 1 つずつ並んで、各人がしばらく実行してから、再びキューに入って実行を待機するのと同じです。

タイムスライスの長さは重要な要素であることに注意してください。

• タイムスライスが短すぎると、プロセスのコンテキスト切り替えが頻繁に発生し、CPU 効率が低下します。
• タイムスライスを長く設定しすぎると、準備キュー内のプロセス数が増えるにつれて、1 回転あたりに費やされる合計時間が増加し、つまり、各プロセスの対応する速度が低下します。タイム スライスがプロセスがすべてのタスクを完了するのに十分な大きさである場合でも、RR スケジューリング アルゴリズムは FCFS アルゴリズムに退化します。

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

RR スケジューリング アルゴリズムは、すべてのプロセスに対して同じ戦略を使用します。ユーザー プロセスが多すぎると、カーネルのサービス プロセスが応答に対応できなくなる可能性があります。オペレーティングシステムでは、カーネルプロセスはユーザープロセスよりもはるかに重要であり、システム全体の安定性に関係しています。

最高優先度のスケジューリング アルゴリズム (最高優先度優先、HPF) は、「実行準備完了キューから最高優先度のプロセスを選択する」というものです。プロセスの優先度はどのように決定されるのでしょうか? 静的優先度と動的優先度に分けられます。

• 「静的優先度」: プロセスが作成されるときに優先度が事前に決定され、プロセスの優先度は実行中のプロセス全体を通じて変更されません。一般的に、カーネル プロセスはユーザー プロセスよりも優先度が高くなります。
• 「動的優先度」：プロセスの動的な変化に応じて優先度を調整します。たとえば、プロセスの実行時間が長くなると、その優先度は適切に下げられ、準備完了キュー内のプロセスの待機時間が長くなると、その優先度は適切に上げられます。

さらに、最も優先度の高いアルゴリズムは、固定されたプリエンプティブ戦略または非プリエンプティブ戦略ではないことに注意することが重要です。「システムは、どの戦略を使用するかを事前に決定できます。」

• 非プリエンプティブ: 優先度の高いプロセスが準備キューに表示された場合は、現在のプロセスが完了した後に優先度の高いプロセスが選択されます。
• プリエンプティブ: 優先度の高いプロセスが準備キューに現れると、現在実行中のプロセスの CPU リソースが直ちに強制的に奪われ、優先度の高いプロセスに割り当てられます。