プロセススケジューリング
1. 概要
このチュートリアルでは、CPUスケジューリングがどのように機能するかを説明し、スケジューリングの基準とアルゴリズムを明確にします。
2. 定義と基本概念
プロセスの定義は非常に明白です。それはプログラムの実行であるか、単に実行中のプログラムです。ただし、プロセスがどのように機能するかを理解するには、オペレーティングシステムの詳細を調べる必要があります。 オペレーティングシステムがプロセスを稼働させ、動作させるためです。 それ以外は、プログラムはディスク上にあります。
ラップトップまたはデスクトップで同時に音楽を聴きながら、プロセスのスケジューリングに関する記事を書いていると想像してみてください。 また、他にも何百ものブラウザタブが開いています。 システムはこれらすべてのプログラムを許可し、同時に実行する必要があります。 それ以外の場合は、コンピューターで複数のプログラムを実行できませんでした。 OSはこの状況を処理しますが、プロセスがCPUが使用可能であることを検出できるようにする必要があります。
この時点で、CPUが1つだけで、プロセスが数百を超える場合はどうなるかを考えることができます。 OSは、CPUを仮想化することでこのような問題を処理します。 1つのプロセスを実行し、一時停止して別のプロセスを開始するなど、複数のCPUの錯覚を作り出すことができます。 CPUタイムシェアリングと呼ばれるこの基本的な概念により、ユーザーは必要な数のプロセスを実行できます。
最近のほとんどすべてのOSは、このタイムシェアリングメカニズムを採用しています。実際、特定のCPUで1つのプログラムを停止し、別のプログラムを開始する機能は、コンテキストスイッチと呼ばれます。タイムシェアリングとプロセスにおいて重要な役割を果たします。スケジューリング。
2.1. プロセス状態
プロセスの定義と、複数のプロセスを同時に実行するためにOSがCPUを仮想化する方法について簡単に紹介しました。 これで、プロセスの状態を確認できます。 プロセスが次のようになる可能性があるのは、単純に3つの状態です。
- 実行中：この状態では、プロセスはプロセッサ上で実行されており、その命令を実行しています。
- 準備完了：準備完了状態では、プロセスを実行する準備ができていますが、オペレーティングシステムは、何らかの理由でこの時点でプロセスを起動しないことを決定しました。
- ブロック：ブロック状態で、プロセスは、別のイベントが発生するまで実行できないようにする何らかのアクションを完了しました。 たとえば、プロセスにディスクへのI / O要求があると、プロセスはブロックされます。 これにより、別のプロセスがCPUにアクセスできるようになります。
次の図は、プロセス状態間の遷移を示しています。
3. スケジューリング基準とアルゴリズム
最近、人々はOSのスケジューラーのように時間を管理することが奨励されています。 ただし、スケジューリングはコンピュータシステムよりも前のものです。 初期の技術は、運用管理の分野から採用され、コンピュータシステムに適用されました。 これは、生産ラインと非常に多くの人間の努力がスケジューリングを伴うことは驚くべきことではありません。 また、同じ問題の多くはそれらすべてに当てはまります。
CPUスケジューリングに関しては、スループット、CPU使用率、ターンアラウンドタイム、待機時間、応答時間などの重要なメトリックがいくつかあります。 このチュートリアルの範囲では、ターンアラウンドタイムと応答時間の観点からいくつかのスケジューリングアルゴリズムを検討します。
これらの重要な指標に関する簡単な情報を提供しましょう。
- 所要時間：特定のプロセスを実行する時間です。 これは、実際には、プロセスが完了する時間からプロセスがCPUに到着する時間を引いた時間に等しくなります。
- 応答時間：プロセスのターンアラウンドタイムが長いため、ターンアラウンドタイムだけでは不十分な場合があるため、これはもう1つの重要なメトリックです。 応答時間は、プロセスがCPUに到着してから最初にスケジュールされるまでの時間を表します。
3.1. 先入れ先出し（FIFO）
先入れ先出しは、実装できる最も基本的なアルゴリズムの1つです。 FIFOには、明確でシンプルで実装が簡単であるなどのいくつかの利点がありますが、そのような場合にはいくつかの欠点があります。 先入れ先出し（FCFS）とも呼ばれます。
X、Y、およびZの3つのプロセスがシステムに到着すると仮定します。 プロセスがX、Y、Zの順序で到着し、各プロセスが20秒間実行されると仮定します。 3つのプロセスの平均所要時間は、秒に等しくなります。
このシナリオでは、すべてのプロセスの実行時間が同じです。 実行時間が異なる場合はどうなりますか。 たとえば、Xが80秒間実行され、YとZが10秒間実行される必要がある場合はどうなりますか。 その場合、所要時間は秒に等しくなります。
3.2. 最短ジョブ優先（SJF）
このスケジューリングポリシーの名前は、それ自体を完全に表しています。 最初に最短のプロセスを選択し、次に最短のプロセスを選択すると、次のようになります。
上の図からわかるように、YとZはXを待つ必要はありません。 SJFは、前にYとZを実行することにより、平均ターンアラウンドタイムを短縮します。 平均所要時間は秒に相当します。
SJFはスムーズに機能しているように見えますが、実際には、YとZはそれぞれ時間0と時間20に来る必要はありません。 Xが時間0に到着し、80秒間実行する必要があり、その後、次の図に示すように、YとZが時間20に到着した場合はどうなりますか。
YとZがXの実行を待たなければならない同じ問題に戻ります。 この状況は再びコンボイの問題につながります。平均ターンアラウンドタイムは秒に等しいです。
また、応答時間を考慮すると、SJFも応答時間に適していないことがわかります。 この時点で、ラウンドロビンがステージに入ります。次のセクションで、ラウンドロビンがどのように機能するかを見ていきます。
3.3. ラウンドロビン（RR）
プロセスの実行全体を待つのではなく、時間を分割してみませんか。 スライスに分割し、完了していない限り、タイムサイクルごとに実行するプロセスを変更できます。これはRRポリシーの機能であり、これにより、平均所要時間と応答時間の両方が短縮されます。 。 RRの平均応答時間は秒に等しくなります。
4. 結論
この記事では、プロセスとそれらがCPUでどのようにスケジュールされるかについて簡単に説明しました。 また、スケジューリングの基準とアルゴリズムについても直感的に説明しました。
