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

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

[[318073]]

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

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

プロセスが 3 つあり、各プロセスの処理に 10 秒かかると仮定します。このとき、どのプロセスが先に実行されても、最後のプロセスの完了時間は 30 秒になります。つまり、この場合の最大完了時間は、すべてのプロセスに必要な時間の合計になります。ただし、プロセスが 3 つあり、そのうち 2 つに 10 秒かかり、もう 1 つに 100 秒かかる場合、最大完了時間は 120 秒になります。 3 つのプロセスの完了時間が異なるため、到着する順序によって最終的な影響は大きく異なります。 A(10s)、B(10s)、C(100s)の3つのプロセスがあるとします。 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 秒の場合、B は 10 秒間実行を開始したときに到着します。現時点では、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 つのアルゴリズムにはさらに多くのコンテンツがあるため、別々に取り出されます。

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