オペレーティング システムのプロセス スケジューリング アルゴリズム (CPU 仮想化)

前回の記事では、オペレーティング システムが CPU を仮想化する方法についてすでに説明しました。今日は、さらに深く掘り下げて、プロセス スケジューリングについて説明します。

[[318073]]

CPU 仮想化の目的は、複数のプロセスを同時に実行できるようにすることです (これが唯一の目的ではありません)。本質はプロセスを切り替えること、つまり複数のプロセスをすばやく切り替えて実行することで、ユーザーにとってはすべてのプロセスが同時に実行されることですが、複数のプロセスを公平に、合理的に、安全かつ効率的に実行するにはどうすればよいでしょうか。そのため、多くのプロセス スケジューリング アルゴリズムがあります。ここでは、基礎から始めて、より広く使用されているアルゴリズムについて詳しく説明します。

1 つ目は最も単純な先入先出法 (FIFO) で、先着順とも呼ばれます。このアルゴリズムの最大の利点はそのシンプルさです。そうです、私たちが理解している限りでは、CPU は最初に来たプロセスを処理し、現在のプロセスが終了するまで待ってから次のプロセスを処理します。

プロセスが 3 つあり、各プロセスの処理に 10 秒かかると仮定します。このとき、どのプロセスが先に実行されても、最後のプロセスの完了時間は 30 秒であるため、この場合の最大完了時間はすべてのプロセスに必要な時間の合計になります。ただし、プロセスが 3 つあり、そのうち 2 つが 10 秒、もう 1 つが 100 秒かかる場合、最大完了時間は 120 秒になります。3 つのプロセスの完了時間が異なるため、到着順序によって最終的な影響は大きく異なります。 3 つのプロセス A(10 秒)、B(10 秒)、C(100 秒) があるとします。これらのプロセスが A、B、C の順に到着した場合、実行プロセスは予想どおりになります。開始から 10 秒後に A の実行が終了し、実行から 20 秒後に C の実行が終了します。しかし、逆の順序で到着した場合はどうなるでしょうか? C、B、A。このようにすると、開始から 100 秒後に C の実行が終了し、110 秒後に B の実行が終了し、120 秒後に A の実行が終了します。明らかに、この場合、B と A は両方とも、実行する前に最も時間のかかる C が完了するのを待つ必要があるため、このアルゴリズムの効率は到着順序と密接に関係しています。明らかに、これは私たちが望んでいることではありません。ここでは、3 つのプロセスすべてが 10 秒かかる場合のプロセスの平均ターンアラウンド時間を計算します。

(10+20+30)/3=20、Aは10秒目に完了し、Bは20秒目に完了し、Cは30秒目に完了するためです。考えてみてください。プロセス A、B、C の時間がそれぞれ 10 秒、10 秒、100 秒の場合はどうなるでしょうか。このとき、プロセスの順序は C、B、A なので、平均ターンアラウンド時間は (100+110+120)/3=110 となります。これは私たちにとって受け入れられないことです。この問題はしばしば護送船団効果と呼ばれます。このような状況は私たちの生活でも非常によく見られます。たとえば、何かをするためにどこかに行くとき、ほとんどの人はそれを終えるのに 1 分しかかかりませんが、前にいる人はそれを終えるのに 30 分かかるので、後ろの人たちは一緒に 30 分間待たなければなりません。

上記の問題に対処するために、Shortest Job First (SJF) と Shortest Completion Time First (STCF) という新しいソリューションがあります。

名前が示すように、最短タスク優先とは、CPU 時間をより少なく消費するプロセスが最初に実行されることを意味します。つまり、上記の例 (A は 10 秒、B は 20 秒、C は 100 秒かかります) では、A と B が最初に到着し、それらの実行が完了した後に C を実行します。ただし、このアルゴリズムでは、C が最後に到着することを保証することはできません。C が最初に到着した場合、状況は依然として悪いです。次の図は状況を示しています。

SJF

この問題を解決するために、すべてのプロセスが一度に実行されることを保証する必要がないという条件を設定します。ここで、最悪のシナリオを想定して、C が最初に到着し、その後に A と B が到着します。 C の合計実行時間が 100 秒の場合、10 秒実行を開始したときに B が到着します。この時点で、C が完全に実行されることを確認する必要はありません。B が完了するには 10 秒しかかからないことがわかります。この時点で、C を一時停止し、B の実行を開始します。B が終了したら、A が再び到着します。この時点で、C は実行されず、A が実行されます。A が終了したら、C に戻ります。このようにして、パフォーマンスがより高いレベルに向上します。以下のように表示されます。

ストフ

上記のアルゴリズムは主に平均ターンアラウンドタイムを考慮していますが、実際には、このようなアルゴリズムはまだ信頼できません。ソフトウェアを開いたときに、特定の機能が応答するまでに 100 秒待つ必要があると想像してください。気が狂いそうになりませんか? このとき、新しいメトリックが登場します。応答時間 (応答時間 = 初回実行時間 - 到着時間) です。

ここで、新しいアルゴリズムであるラウンドロビン (RR) を紹介します。名前の通り、ローテーション実行処理です。ジョブを一定時間実行し、実行キュー内の次のタスクに切り替えます。すべてが完了するまで繰り返します。ここで注意すべき点は、タイム スライスはクロック割り込み周期の倍数である必要があるということです。クロック割り込み部分については、前回の記事で既に説明しているので、ここでは詳しく説明しません。クロック割り込み周期が 10 ミリ秒の場合、タイム スライスは 10 ミリ秒、20 ミリ秒、30 ミリ秒、または 10 ミリ秒の任意の倍数になります。 3 つのプロセス A、B、C に必要な時間は 5 です。RR アルゴリズムを使用する場合、実行プロセスは次のようになります。

RR

ただし、このアルゴリズムにはコンテキスト切り替えのコストという別のコストがあります。したがって、妥当なタイムスライスを見つける必要があります。しかし、主な問題は、このアルゴリズムが、これまでの最短タスク優先度や最短完了時間優先度とは多少逆であり、つまり、このアルゴリズムによってターンアラウンド時間が長くなることです。例に示すように、プログラム A は 13 時に完了し、プログラム B は 14 時に完了し、プログラム C は 15 時に完了します。これは非常に恐ろしいことです。

これで、それぞれ異なるメトリックを持つ 2 つのアルゴリズムができました。1 つはターンアラウンド タイム、もう 1 つは応答時間です。しかし、両方を同時に実現することはできないことは誰もが知っています。では、具体的には何をすればよいのでしょうか。次の記事では、さらに完全な 2 つのアルゴリズム、マルチレベル フィードバック キューと比例配分について引き続き説明します。これら 2 つのアルゴリズムにはさらに多くのコンテンツがあるため、別々に取り出されます。

今日お話しするのは、プロセス スケジューリングの考え方の出発点とも言える、比較的基本的な内容です。この基礎があれば、その後のマルチレベル フィードバック キュー アルゴリズムと比例配分についてより深く理解することができます。もう少しお話ししましょう。なぜ最近、オペレーティング システムについて書きたいのか。それは、特に実稼働環境での問題の発見やパフォーマンスの向上など、実稼働に非常に役立つと思うので、誰もが学ぶことをお勧めするからです。これは私が常に主張していることです。言語は単なるツールであり、フレームワークもツールですが、どのように変化しても、すべてに本質があります。最もコアで基本的なものを習得することによってのみ、無敵になれます。