オペレーティング システムの概要

おい、ハブル！ 私の意見では、興味深い文献の XNUMX つである OSTEP の翻訳シリーズの記事を紹介したいと思います。 この資料では、UNIX に似たオペレーティング システムの動作、つまり、最新の OS を構成するプロセス、さまざまなスケジューラ、メモリ、およびその他の同様のコンポーネントの動作について非常に詳しく説明します。 すべての資料のオリジナルはこちらからご覧いただけます ここで。 翻訳は専門的ではなく（まったく自由に）行われたことに注意してください。しかし、一般的な意味を保持していれば幸いです。

このテーマに関するラボの作業は、次の場所にあります。

• 原作
• 原作
• 私の個人的な適応

その他の部品

• パート 1: イントロダクション
• パート 2: 抽象化: プロセス
• パート 3: プロセス API の概要
• パート 4: スケジューラの概要

私のチャンネルもチェックできます 電報 =)

スケジューラの概要

問題の本質: スケジューラ ポリシーを作成する方法
基礎となるスケジューラ ポリシー フレームワークはどのように設計されるべきですか? 重要な前提条件は何でしょうか? どのような指標が重要ですか? 初期のコンピューティング システムではどのような基本的な技術が使用されていましたか?

ワークロードの想定

考えられるポリシーについて議論する前に、まず、システム内で実行されているプロセス (総称して「プロセス」と呼ばれます) について簡単な余談をいくつかしておきます。 仕事量。 ワークロードの定義はポリシーを構築する上で重要な部分であり、ワークロードについての知識が増えるほど、より適切なポリシーを作成できるようになります。

システム内で実行されているプロセス (とも呼ばれることもあります) について次の仮定を立ててみましょう。 jobs (タスク)。 これらの仮定のほとんどすべては現実的ではありませんが、思考を発展させるためには必要です。

1. 各タスクは同じ時間実行されます。
2. すべてのタスクが同時に設定され、
3. 割り当てられたタスクは完了するまで機能し、
4. すべてのタスクは CPU のみを使用します。
5. 各タスクの実行時間はわかっています。

スケジューラのメトリクス

負荷に関するいくつかの仮定に加えて、さまざまなスケジューリング ポリシーを比較するための別のツール、スケジューラー メトリックが必要です。 メトリクスは、何かを測定するための単なる尺度です。 スケジューラーを比較するために使用できる指標が多数あります。

たとえば、というメトリクスを使用します。 ターンアラウンドタイム （ターンアラウンドタイム）。 タスクの所要時間は、システム内のタスクの完了時間とタスクの到着時間の差として定義されます。

Tturnaround=T完了−T到着

すべてのタスクが同時に到着すると仮定したため、Ta=0 となり、Tt=Tc となります。 上記の前提を変更すると、この値は当然変化します。

別の指標 - 公平 （公平性、誠実さ）。 生産性と公平性は、計画において相反する特性となることがよくあります。 たとえば、スケジューラはパフォーマンスを最適化できますが、他のタスクの実行を待つという犠牲が発生し、公平性が低下します。

先入れ先出し (FIFO)

実装できる最も基本的なアルゴリズムは FIFO または 先着順（入場）、先着順（出力順）。 このアルゴリズムにはいくつかの利点があります。実装が非常に簡単で、すべての仮定に適合し、非常にうまく機能します。

簡単な例を見てみましょう。 3 つのタスクが同時に設定されたとします。 ただし、タスク A が他のすべてのタスクより少し早く到着したと仮定します。そのため、タスク B が C に対して相対的に見えるように、他のタスクよりも早く実行リストに表示されます。それぞれのタスクが 10 秒間実行されると仮定しましょう。 この場合、これらのタスクを完了するのにかかる平均時間はどれくらいになりますか?

値 - 10+20+30 を数えて 3 で割ると、プログラムの平均実行時間は 20 秒になります。
さて、仮定を変えてみましょう。 特に、仮定 1 では、各タスクの実行に同じ時間がかかるとは仮定しません。 今回のFIFOはどうなるでしょうか？

結局のところ、タスクの実行時間が異なると、FIFO アルゴリズムの生産性に非常に悪影響を及ぼします。 タスク A が完了するまでに 100 秒かかる一方、タスク B と C はそれぞれ 10 秒かかると仮定します。

図からわかるように、システムの平均時間は (100+110+120)/3=110 になります。 この効果はと呼ばれます 護送船団効果、リソースの一部の短期間の消費者が大量の消費者の後にキューに入る場合。 それは、食料品店で、目の前にカートをいっぱいにした顧客がいるときの行列のようなものです。 この問題に対する最善の解決策は、レジを変えるか、リラックスして深呼吸してみることです。

最短のジョブが最初

重量のあるプロセスで同様の状況を何とか解決することは可能でしょうか? 確かに。 別のタイプの計画は次のように呼ばれます。最短のジョブが最初 (SJF)。 そのアルゴリズムも非常に原始的で、名前が示すように、最も短いタスクが最初に次々と起動されます。

この例では、同じプロセスを実行した結果、プログラムの平均所要時間が改善され、それは次のようになります。 50 ではなく 110、ほぼ2倍優れています。

したがって、すべてのタスクが同時に到着するという所定の仮定では、SJF アルゴリズムが最も最適なアルゴリズムであると思われます。 しかし、私たちの仮定はまだ現実的ではないようです。 今回は仮定 2 を変更し、タスクがいつでも存在する可能性があり、すべてが同時に存在するわけではないと想像します。 これはどのような問題を引き起こす可能性がありますか?

タスク A (100c) が最初に到着し、実行が開始されると想像してみましょう。 t=10 で、タスク B と C が到着します。それぞれに 10 秒かかります。 したがって、平均実行時間は (100+(110-10)+(120-10))3 = 103 となります。これを改善するためにスケジューラーは何をできるでしょうか?

完了までの最短時間優先 (STCF)

この状況を改善するために、プログラムが起動され、完了するまで実行されるという前提 3 を省略します。 さらに、ハードウェアのサポートが必要になるため、ご想像のとおり、次のものを使用します。 タイマー 実行中のタスクを中断し、 コンテキストスイッチング。 したがって、スケジューラは、タスク B、C が到着した瞬間に何かを行うことができます。タスク A の実行を停止し、タスク B と C を処理に移し、それらの完了後にプロセス A の実行を継続します。このようなスケジューラは、と呼ばれます。 STCFまたは 先制ジョブファースト.

このプランナーの結果は次の結果になります: ((120-0)+(20-10)+(30-10))/3=50。 したがって、このようなスケジューラはタスクにとってさらに最適になります。

メトリクスの応答時間

したがって、タスクの実行時間がわかっていて、これらのタスクが CPU のみを使用することがわかっている場合は、STCF が最適なソリューションになります。 そして、初期の頃、これらのアルゴリズムは非常にうまく機能していました。 しかし、ユーザーは現在、ほとんどの時間を端末で過ごしており、生産的なインタラクティブなエクスペリエンスを期待しています。 こうして、新しい指標が生まれました - 反応時間 （応答）。

応答時間は次のように計算されます。

応答=Tfirstrun−Tdelivery

したがって、前の例の場合、応答時間は A=0、B=0、C=10 (abg=3,33) となります。

そして、STCF アルゴリズムは、3 つのタスクが同時に到着する状況ではあまり優れていないことがわかりました。小さなタスクが完全に完了するまで待たなければなりません。 したがって、このアルゴリズムは所要時間の指標には適していますが、対話性の指標には不利です。 端末の前に座ってエディターに文字を入力しようとして、他のタスクが CPU を占有しているために 10 秒以上待たなければならなかった場合を想像してください。 あまり気持ちの良いものではありません。

そこで、別の問題に直面しています。応答時間に敏感なスケジューラをどのように構築すればよいでしょうか?

ラウンドロビン

この問題を解決するためにアルゴリズムが開発されました ラウンドロビン (RR)。 基本的な考え方は非常に単純です。完了するまでタスクを実行するのではなく、タスクを一定期間 (タイム スライスと呼ばれます) 実行してから、キュー内の別のタスクに切り替えます。 アルゴリズムは、すべてのタスクが完了するまで作業を繰り返します。 この場合、プログラムの実行時間は、タイマーがプロセスを中断するまでの時間の倍数である必要があります。 たとえば、タイマーが x=10 ミリ秒ごとにプロセスを中断する場合、プロセス実行ウィンドウのサイズは 10 の倍数、つまり 10,20、10、または x*XNUMX でなければなりません。

例を見てみましょう。ABC タスクがシステムに同時に到着し、それぞれのタスクを 5 秒間実行したいと考えています。 SJF アルゴリズムは、次のタスクを開始する前に各タスクを完了します。 対照的に、起動ウィンドウ = 1 秒の RR アルゴリズムは次のようなタスクを実行します (図 4.3)。

(SJF 再び (応答時間に悪い)

(ラウンドロビン (応答時間に優れる)

RR アルゴリズムの平均応答時間は (0+1+2)/3=1 ですが、SJF の場合は (0+5+10)/3=5 です。

時間ウィンドウが RR にとって非常に重要なパラメータであると仮定するのは論理的であり、それが小さいほど応答時間は長くなります。 ただし、コンテキストの切り替え時間も全体的なパフォーマンスに影響するため、この値を小さくしすぎないでください。 したがって、実行ウィンドウ時間の選択は OS アーキテクトによって設定され、その中で実行される予定のタスクによって決まります。 時間を無駄にするサービス操作はコンテキストの切り替えだけではありません。実行中のプログラムは、さまざまなキャッシュなど、他の多くのもので動作し、切り替えるたびにこの環境を保存および復元する必要があり、これにも多くの時間がかかる可能性があります。時間。

応答時間のメトリクスについてのみ話している場合、RR は優れたスケジューラです。 しかし、このアルゴリズムではタスク所要時間の指標はどのように動作するのでしょうか? 上の例で、A、B、C の動作時間 = 5 秒が同時に到着した場合を考えてみましょう。 タスク A は 13 秒、B は 14 秒、C は 15 秒に終了し、平均所要時間は 14 秒になります。 したがって、RR は売上高指標にとって最悪のアルゴリズムです。

より一般的に言えば、RR タイプのアルゴリズムはどれも公平であり、CPU 時間をすべてのプロセス間で均等に分割します。 したがって、これらの指標は常に互いに競合します。

したがって、いくつかの対照的なアルゴリズムがあり、同時に、タスク時間が既知であり、タスクが CPU のみを使用するといういくつかの仮定がまだ残っています。

I/Oとのミキシング

まず、プロセスが CPU のみを使用するという前提 4 を削除しましょう。当然のことですが、これは当てはまらず、プロセスは他の機器にアクセスできます。

いずれかのプロセスが I/O 操作を要求すると、プロセスはブロック状態に入り、I/O が完了するのを待ちます。 I/O がハード ドライブに送信される場合、そのような操作には数ミリ秒以上かかる可能性があり、この時点ではプロセッサはアイドル状態になります。 この間、スケジューラは他のプロセスでプロセッサを占有することができます。 スケジューラが次に決定しなければならないのは、プロセスがいつ I/O を完了するかということです。 これが発生すると、割り込みが発生し、OS は I/O を呼び出したプロセスを準備完了状態にします。

いくつかの問題の例を見てみましょう。 それぞれに 50 ミリ秒の CPU 時間が必要です。 ただし、最初のものは 10 ミリ秒ごとに I/O にアクセスします (これも 10 ミリ秒ごとに実行されます)。 また、プロセス B は、I/O なしで 50ms プロセッサを単純に使用します。

この例では、STCF スケジューラを使用します。 A のようなプロセスが起動された場合、スケジューラはどのように動作しますか? 彼は次のことを行います。最初にプロセス A を完全に実行し、次にプロセス B を実行します。

この問題を解決する従来のアプローチは、プロセス A の各 10 ミリ秒のサブタスクを別個のタスクとして扱うことです。 したがって、STJF アルゴリズムを開始する場合、50 ミリ秒のタスクと 10 ミリ秒のタスクのどちらを選択するかは明らかです。 次に、サブタスク A が完了すると、プロセス B と I/O が起動されます。 I/O が完了したら、プロセス B の代わりに 10 ミリ秒のプロセス A を再度開始するのが一般的です。このようにして、最初のプロセスが待機している間に CPU が別のプロセスによって使用されるオーバーラップを実装することができます。 I/O。 その結果、システムの利用効率が向上します。対話型プロセスが I/O を待機しているときに、他のプロセスをプロセッサ上で実行できます。

オラクルはもういない

ここで、タスクの実行時間がわかっているという前提を取り除いてみましょう。 これは一般に、リスト全体の中で最悪かつ最も非現実的な仮定です。 実際、平均的な通常の OS では、OS 自体は通常、タスクの実行時間についてほとんど知りません。では、タスクの実行にかかる時間がわからないのに、どうやってスケジューラーを構築できるのでしょうか? おそらく、この問題を解決するためにいくつかの RR 原則を使用できるでしょうか?

合計

私たちはタスク スケジューリングの基本的な考え方を検討し、スケジューラの 2 つのファミリーを検討しました。 XNUMX つ目のタスクは最も短いタスクを最初に開始するため、所要時間が増加します。一方、XNUMX つ目のタスクはすべてのタスク間で均等に分割されるため、応答時間が増加します。 他のファミリーのアルゴリズムが優れている場合、どちらのアルゴリズムも劣悪です。 また、CPU と I/O を並行して使用することでパフォーマンスがどのように向上するかについても検討しましたが、OS の千里眼の問題は解決できませんでした。 次のレッスンでは、直近の過去を調べて未来を予測しようとするプランナーについて見ていきます。 それはマルチレベルフィードバックキューと呼ばれます。

出所： habr.com