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

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

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

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

その他の部品

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

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

計画: マルチレベルのフィードバック キュー

この講義では、最も有名なアプローチの XNUMX つを開発する際の問題について説明します。
いわゆるプランニング マルチレベルフィードバックキュー (MLFQ)。 MLFQ スケジューラは、1962 年にフェルナンド J. コルバトによって、と呼ばれるシステムで初めて記述されました。
互換性のあるタイムシェアリング システム (CTSS)。 これらの作品（以降の作品も含む）
Multics) はその後チューリング賞にノミネートされました。 スケジューラーは
その後改良され、すでに見られる外観が得られました。
いくつかの最新のシステム。

MLFQ アルゴリズムは、重複する 2 つの基本的な問題を解決しようとします。
まず第一に、ターンアラウンドタイムの​​最適化を試みます。前の講義で説明したように、キューの先頭から開始する方法によって最適化されます。
短いタスク。 ただし、OS は特定のプロセスがどれくらいの時間実行されるかを知りません。
SJF、STCFアルゴリズムの操作に必要な知識。 第二に、MLFQ が試みます
ユーザーに対してシステムの応答性を高めます (たとえば、座っている人や座っている人など)。
タスクが完了するのを待っている間画面を見つめる）ため、時間を最小限に抑えることができます。
応答。 残念ながら、RR のようなアルゴリズムは応答時間を短縮しますが、
所要時間の指標に悪影響を及ぼします。 したがって、私たちの問題は「どのように設計するか」です。
何も知らなくても要件を満たすスケジューラ
一般的なプロセスの性質は何ですか? スケジューラーはタスクの特性をどのようにして学習することができますか?
どちらを起動すれば、より良い計画決定ができ​​るでしょうか?

問題の本質: 完璧な知識がないのに、どうやってタスクの設定を計画するか?
同時に応答時間を最小限に抑えるスケジューラーを設計する方法
インタラクティブなタスクに使用できると同時に、知らず知らずのうちに所要時間を最小限に抑えます。
タスクの実行時間についての知識はありますか?

注: 過去の出来事から学ぶ

MLFQ キューは、トレーニングされたシステムの優れた例です。
未来を予測するために過去の出来事。 このようなアプローチは多くの場合、
OS (およびコンピューター サイエンスの他の多くの分野、
ハードウェア予測とキャッシュ アルゴリズム)。 同様のハイキング
タスクに行動フェーズがあり、予測可能な場合にトリガーされます。
ただし、予測は非常に簡単であるため、この手法には注意が必要です。
それが間違っていることが判明し、システムが以前よりも悪い決定を下すことになる可能性があります。
全く知識が無いでしょう。

MLFQ: 基本ルール

MLFQ アルゴリズムの基本ルールを見てみましょう。 そして、このアルゴリズムの実装は
いくつかありますが、基本的なアプローチは似ています。
私たちが検討する実装では、MLFQ にはいくつかの機能があります。
別々のキューであり、それぞれに異なる優先度が設定されます。 いつでも、
実行準備ができているタスクは同じキュー内にあります。 MLFQ は優先順位を使用します。
どのタスクを実行するかを決定します。つまり、 より高いタスク
優先度 (最も高い優先度を持つキューからのタスク) は最初に起動されます。
列。
もちろん、特定のキューに複数のタスクが存在する場合もありますので、
したがって、それらは同じ優先度を持つことになります。 この場合、このメカニズムが使用されます
これらのタスクのうち、打ち上げ計画のための RR。
したがって、MLFQ の XNUMX つの基本ルールに到達します。

• ルール 1: 優先度 (A) > 優先度 (B) の場合、タスク A が実行されます (B は実行されません)。
• ルール 2: 優先度(A) = 優先度(B) の場合、A&B は RR を使用して開始されます。

上記に基づいて、MLFQ を計画するための重要な要素は次のとおりです。
が優先事項です。 それぞれに固定の優先順位を与えるのではなく、
タスクに応じて、MLFQ は観察された動作に応じて優先順位を変更します。
たとえば、キーボード入力を待機している間にタスクが常に CPU 上で終了する場合、
MLFQ はプロセスの優先度を高く保ちます。
インタラクティブなプロセスが機能するはずです。 逆に、タスクが継続的に行われ、
長期間にわたって CPU に負荷がかかるため、MLFQ によってダウングレードされます
優先事項。 したがって、MLFQ はプロセスの実行中の動作を研究します。
そして行動を利用します。
ある時点でキューがどのように見えるかの例を描いてみましょう
すると、次のような結果が得られます。


このスキームでは、2 つのプロセス A と B が最高の優先順位でキューに入れられます。 プロセス
C は中間のどこかにあり、プロセス D はキューの最後尾にあります。 上記によると
MLFQ アルゴリズムの説明に従うと、スケジューラは最高のタスクのみを実行します。
RR に従って優先順位が変更され、タスク C、D は作業外になります。
当然のことながら、静的なスナップショットでは、MLFQ がどのように機能するかを完全に把握することはできません。
時間の経過とともに画像がどのように変化するかを正確に理解することが重要です。

試み 1: 優先度を変更する方法

この時点で、MLFQ が優先レベルをどのように変更するかを決定する必要があります。
ライフサイクル中のタスク (したがってキュー内のタスクの位置)。 のために
これはワークフローを念頭に置くために必要です: 一定量
実行時間が短い対話型タスク (したがって頻繁にリリースされる)
CPU) と、作業時間全体にわたって CPU を使用するいくつかの長時間実行タスク、
このようなタスクでは、応答時間は重要ではありません。 このようにして、最初の試みを行うことができます
次のルールで MLFQ アルゴリズムを実装します。

• ルール 3: タスクがシステムに入ると、タスクは最も高いキューに配置されます。
• 優先順位。
• ルール 4a: タスクが、割り当てられた時間枠全体を使用する場合、
• 優先順位が下がります。
• ルール 4b: タスクがタイム ウィンドウが期限切れになる前に CPU を解放した場合、
• 同じ優先度のままです。

例 1: 単一の長時間実行タスク

この例からわかるように、入院時のタスクは最も高い値で設定されています。
優先度。 10 ミリ秒の時間枠が経過すると、プロセスの優先順位がダウングレードされます。
スケジューラー。 次の時間枠が経過すると、タスクは最終的に次のようにダウングレードされます。
システム内で最も優先度が低く、そのまま残ります。


例 2: 短いタスクを選択した

次に、MLFQ が SJF にどのようにアプローチしようとするかの一例を見てみましょう。 その中で
たとえば、XNUMX つのタスク: A、これは常に長時間実行されるタスクです。
CPU と B を占有します。これは短い対話型タスクです。 仮定する
タスク B が到着するまでに、A はすでにしばらく働いていたと考えられます。


このグラフはシナリオの結果を示しています。 タスク A は、他のタスクと同様に、
CPUの使用は最下位でした。 タスク B は時刻 T=100 に到着し、
最も優先度の高いキューに入れられます。 上映時間が短いので、
最後のキューに到達する前に完了します。

この例から、アルゴリズムの主な目的を理解する必要があります。
長いタスクか短いタスクかを知っている場合、まず第一に、そのタスクは次のことであると想定します。
短く、最も高い優先度を与えます。 本当に短時間のタスクであれば、
すぐに実行されますが、長いタスクの場合はゆっくりと実行されます。
優先順位は下がっており、彼女が本当に長い仕事であることがすぐに証明されるでしょう
応答が必要です。

例 3: I/O はどうなるでしょうか?

次に、I/O の例を見てみましょう。 ルール 4b に記載されているように、
プロセスがプロセッサ時間を完全に使用せずにプロセッサを解放した場合、
その後、同じ優先レベルのままになります。 このルールの目的は非常に単純です。
- 対話型ジョブが大量の I/O を実行する場合 (たとえば、待機中)
ユーザーのキーストロークまたはマウスからのタスクを実行すると、プロセッサが解放されます。
割り当てられた窓口の前で。 このような優先課題を手抜きしたくないのですが、
したがって、同じレベルに留まります。


この例では、このようなプロセス (実行前に CPU を 1 ミリ秒だけ必要とする対話型タスク B) でアルゴリズムがどのように機能するかを示します。
I/O プロセスと長時間実行されるジョブ A。CPU の使用にすべての時間を費やします。
MLFQ はプロセス B を継続するため、最高の優先度を維持します。
CPUを解放します。 B が対話型タスクの場合、アルゴリズムは次のことを達成します。
その目的は、対話型タスクを迅速に起動することです。

現在の MLFQ アルゴリズムの問​​題点

前の例では、MLFQ の基本バージョンを構築しました。 そして彼はどうやら
その仕事は適切かつ公平に実行され、CPU 時間を公平に分配します。
長時間のタスクと、短時間または大量のタスクの実行が可能
高速に処理するために I/O に転送します。 残念ながら、このアプローチにはいくつかの要素が含まれています。
深刻な問題。
まず第一に、飢餓の問題: システムに多くのインタラクティブ機能がある場合
タスクを実行すると、すべての CPU 時間を消費するため、単一の長い時間はかかりません。
タスクは実行される機会がありません (タスクは飢えています)。

第二に、賢いユーザーは次のようにプログラムを書くことができます。
スケジューラをバカにする。 欺瞞とは、何かを強制することにある
スケジューラを使用してプロセスにさらに多くの CPU 時間を与えます。 そのアルゴリズムは、
上で説明したものは、そのような攻撃に対して非常に脆弱です。つまり、時間枠が実質的に満たされる前に、
以上、(どのファイルであっても) I/O 操作を実行する必要があります。
したがって、CPU が解放されます。 そのような行動により、同じ状態に留まることができます
キュー自体を処理し、再び CPU 時間のより大きな割合を取得します。 完了したら
これは正しいです (たとえば、CPU を解放する前にウィンドウ時間の 99% を実行します)。
このようなタスクは単にプロセッサを独占する可能性があります。

最後に、プログラムは時間の経過とともに動作を変えることができます。 それらのタスク
CPU を使用したものはインタラクティブになる可能性があります。 この例では、同様の
タスクは、他のタスクとは異なり、スケジューラから適切な処理を受けません。
(オリジナルの) インタラクティブなタスク。

聴衆への質問: 現代世界ではスケジューラに対してどのような攻撃が行われる可能性がありますか?

試み 2: 優先度を上げる

ルールを変更して、問題を回避できるかどうか試してみましょう。
飢餓。 関連性を確保するために何ができるか
CPU タスクには (長くない場合でも) 時間がかかります。
問題の簡単な解決策として、定期的に提案することができます。
システム内のそのようなすべてのタスクの優先順位を上げます。 たくさんの方法があります
これを実現するために、例として簡単なものを実装してみましょう。
すべてのタスクには直ちに最高の優先順位が与えられるため、新しいルールは次のようになります。

• Rule5: 一定期間 S の後、システム内のすべてのタスクを最上位のキューに転送します。

私たちの新しいルールは XNUMX つの問題を一度に解決します。 まず、プロセス
飢えないことが保証されています: 最も高いキューにあるタスクは共有されます
RR アルゴリズムに従ってプロセッサー時間を設定するため、すべてのプロセスは
プロセッサー時間。 次に、以前に使用していたプロセスがある場合、
プロセッサのみが対話型になり、最も高いプロセッサのキューに残ります。
一度最高優先度へのブーストを受けた後の優先度。
例を考えてみましょう。 このシナリオでは、次を使用する単一プロセスを検討します。


CPU と 50 つの対話型の短いプロセス。 図の左側は、優先順位をブーストしない場合の動作を示しているため、50 つの対話型タスクがシステムに到着した後、長時間実行されているタスクが停止し始めます。 右の図では、XNUMX ミリ秒ごとに優先度の増加が実行されるため、すべてのプロセスがプロセッサー時間を受け取ることが保証され、定期的に開始されます。 この場合の XNUMXms は例として挙げていますが、実際にはこの数値はもう少し大きくなります。
周期的な立ち上がり時間 S を追加すると、次の結果が得られることは明らかです。
論理的な質問: どのような値を設定する必要がありますか? 当然のことの XNUMX つ
システムエンジニアのジョン・オースターハウトは、システム内の同様の量をブードゥーと呼んでいました。
正しいものを得るには何らかの形で黒魔術が必要だったため、一定です。
暴露。 そして、残念なことに、Sにはそのような味があります。 値も設定した場合
大きい - 長いタスクは枯渇します。 また、設定を低くしすぎると、
対話型タスクは適切な CPU 時間を受け取りません。

試み 3: 会計の改善

さて、解決すべき問題がもう XNUMX つあります。
私たちのスケジューラーがだまされるのを許してください? この可能性について責任を負うのは次の人々です
プロセッサを解放することでジョブの優先順位を維持できるようにするルール 4a、4b
割り当てられた時間が経過する前に。 どうやって対処すればいいのでしょうか？
この場合の解決策は、それぞれの CPU 時間をより適切に計算することであると考えることができます。
MLFQレベル。 プログラムが使用した時間を忘れる代わりに
プロセッサに割り当てられた間隔を使用する必要がある場合は、それを考慮して保存する必要があります。 後
プロセスは割り当てられた時間を使い果たしたので、次のプロセスに降格する必要があります
優先レベル。 今では、プロセスがどのように時間を使うかは問題ではありません。
プロセッサ上で、または一連の呼び出しとして常に計算されます。 したがって、
ルール 4 は次のように書き換える必要があります。

• Rule4: タスクが現在のキューに割り当てられた時間を使い果たすと (何度 CPU を解放したかに関係なく)、そのタスクの優先度は下がります (キューの下に移動します)。

例を見てみましょう:
»

この図は、次のようにスケジューラを騙そうとした場合に何が起こるかを示しています。
以前のルール 4a、4b を使用した場合は、左の結果が得られます。 おめでとうございます
ルールは結果が右側にあるということです。 保護される前は、どのプロセスも完了前に I/O を呼び出すことができ、
したがって、保護を有効にした後は、動作に関係なく CPU を支配します。
I/O、彼はまだキューに残っているため、不正にアクセスすることはできません。
CPUリソースを引き継ぎます。

MLFQ およびその他の問題の改善

上記の改善により、新たな問題が発生します。
質問 - このようなスケジューラをパラメータ化するにはどうすればよいですか? それらの。 いくらあるべきか
行列？ キュー内のプログラム ウィンドウのサイズはどれくらいにすべきでしょうか? どうやって
多くの場合、飢餓を避けるためにプログラムを優先する必要があります。
プログラムの動作の変化を考慮するには? これらの質問に対して、単純な答えはありません
応答と、負荷とその後の構成の実験のみ
スケジューラを使用すると、ある程度満足のいくバランスが得られます。

たとえば、ほとんどの MLFQ 実装では、異なる値を割り当てることができます。
さまざまなキューの時間間隔。 通常、優先度の高いキュー
短い間隔。 これらのキューは対話型タスクで構成されます。
どちらの切り替えは非常に繊細であり、10 以下の時間がかかるはずです
MS。 対照的に、優先度の低いキューは、次のような長時間実行タスクで構成されます。
CPU。 この場合、長い時間間隔 (100 ミリ秒) が非常によく適合します。


この例では、高優先度キュー 2 で動作しているタスクが 20 つあります。
ms を 10ms ウィンドウに分割します。 中間キュー (40 ミリ秒ウィンドウ) および低優先度キューで 20 ミリ秒
タスクが作業を完了するキュー タイム ウィンドウが 40 ミリ秒になりました。

Solaris OS での MLFQ の実装は、タイムシェアリング スケジューラのクラスです。
プランナーは、必要なとおりに正確に定義する一連のテーブルを提供します。
プロセスの存続期間全体にわたってプロセスの優先順位を変更します。サイズはどのくらいにすべきですか
割り当てられたウィンドウと、タスクの優先順位を上げる必要がある頻度。 管理者
システムはこのテーブルと対話し、スケジューラを動作させることができます
違う。 デフォルトでは、このテーブルには 60 個のキューがあり、徐々に増加します。
ウィンドウ サイズは 20 ミリ秒 (優先度が高い) から数百ミリ秒 (優先度が最も低い)、
また、すべてのタスクを XNUMX 秒に XNUMX 回ブーストします。

他の MLFQ スケジューラは、テーブルや特定のテーブルを使用しません。
この講義で説明するルールは、逆に、以下を使用して優先度を計算します。
数式。 たとえば、FreeBSD のスケジューラは次の式を使用します。
プロセスにかかる時間に基づいてタスクの現在の優先度を計算する
使用したCPU。 さらに、CPU 使用率は時間の経過とともに低下するため、
したがって、優先度の増加は上記とは多少異なります。 これは本当です
減衰アルゴリズムと呼ばれます。 バージョン 7.1 以降、FreeBSD は ULE スケジューラを使用します。

最後に、多くのスケジューラには他の機能もあります。 たとえば、いくつかの
スケジューラはオペレーティング システムの動作のために最高レベルを予約するため、
したがって、どのユーザープロセスも最高の優先順位を取得できません。
システム。 一部のシステムでは、役立つアドバイスを提供できます
スケジューラが正しく優先順位を付けます。 たとえば、次のコマンドを使用すると、 nice
タスクの優先度を増減できるため、増減することができます。
プログラムが CPU 時間を費やす可能性を減らします。

MLFQ: 概要

MLFQ と呼ばれる計画アプローチについて説明しました。 彼の名前
動作原理で結論付けられています - いくつかのキューがあり、フィードバックを使用します
タスクに優先順位を付けるため。
ルールの最終的な形式は次のようになります。

• Rule1: 優先度(A) > 優先度(B) の場合、タスク A が実行されます (B は実行されません)。
• Rule2: 優先度(A) = 優先度(B)の場合、RRを使用してA&Bが開始されます。
• Rule3: タスクがシステムに入力されると、そのタスクは最も優先度の高いキューに配置されます。
• Rule4: タスクが現在のキューに割り当てられた時間を使い果たすと (何度 CPU を解放したかに関係なく)、そのタスクの優先度は下がります (キューの下に移動します)。
• Rule5: 一定期間 S の後、システム内のすべてのタスクを最上位のキューに転送します。

MLFQ が興味深いのは、次の理由からです。
タスクの性質を事前に学習し、アルゴリズムがタスクの過去の動作を学習し、
それに応じて優先順位が付けられます。 したがって、彼は一度に XNUMX つの椅子に座ろうとします - 小さなタスク (SJF、STCF) の生産性を達成し、正直に長く走るために、
CPU 負荷の高いジョブ。 したがって、BSD とその派生システムを含む多くのシステムは、
Solaris、Windows、Mac はスケジューラとして何らかのアルゴリズムを使用します
ベースラインとしての MLFQ。

追加の資料

1. manpages.debian.org/stretch/manpages/sched.7.en.html
2. en.wikipedia.org/wiki/Scheduling_（コンピューティング）
3. Pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
5. chebykin.org/freebsd-process-scheduling

出所： habr.com