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

こんにちは、Habr！私の考えでは、OSTEPという興味深い文献の一連の翻訳記事に注目したいと思います。この記事では、unixに似たオペレーティングシステムの動作、つまり、プロセス、さまざまなスケジューラ、メモリ、および現代のOSを構成する他の同様のコンポーネントの動作について詳しく説明します。ここで見ることができるすべての資料のオリジナル。翻訳は専門的ではない（非常に自由に）行われましたが、一般的な意味を保持したいと思います。

このテーマの実験室の仕事はここで見つけることができます：

その他の部品：

そして、あなたは電報で私のチャンネルを見ることができます=）

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

この講義では、最も有名なアプローチの1つを開発する問題について説明します。
マルチレベルフィードバックキュー （MLFQ）と呼ばれる計画。 MLFQスケジューラーは、1962年にFernando J.CorbatóによってCompatible Time-Sharing System（CTSS）と呼ばれるシステムで初めて説明されました。これらの作品（Multicsに関する後の作品を含む）は、その後チューリング賞に提出されました。スケジューラはその後改善され、一部の最新システムですでに見られる外観を獲得しました。

MLFQアルゴリズムは、2つの基本的な横断的な問題を解決しようとします。
最初に 、彼はターンアラウンド時間の最適化を試みます。これは、前の講義で検討したように、最短タスクのキューの先頭から開始することにより最適化されます。ただし、OSはこのプロセスまたはそのプロセスがどのくらいの期間機能するかを知りません。これは、SJF、STCFアルゴリズムの操作に必要な知識です。次に、MLFQはシステム（ユーザーがタスクの完了を待っている間に座って画面を見つめているユーザーなど）にシステムを応答させ、応答時間を最小化しようとしています。残念ながら、RRのようなアルゴリズムは応答時間を短縮しますが、ターンアラウンドタイムメトリックに非常に悪い影響を及ぼします。したがって、私たちの問題：要件を満たし、同時にプロセスの性質について何も知らないスケジューラを一般的にどのように設計するのでしょうか？スケジューラーは、起動するタスクの特性をどのようにして学習し、それにより、より良い計画決定を下すことができますか？

問題の本質：完全な知識なしにタスクの定式化を計画する方法は？対話型タスクの応答時間を最小化すると同時に、タスクを完了する時間を知らずに所要時間を最小化するスケジューラを開発する方法は？

注：以前のイベントから学ぶ

MLFQラインナップは、過去のイベントから学習して未来を予測するシステムの優れた例です。 OS（およびハードウェア予測ブランチやキャッシングアルゴリズムを含むコンピューターサイエンスの他の多くのブランチ）でも、同様のアプローチがよく見られます。タスクに行動段階があり、したがって予測可能な場合、同様の旅行が機能します。

ただし、そのような手法には注意が必要です。予測が非常に簡単に間違っていることが判明し、システムがまったく知識を持たない場合よりも悪い判断を下す可能性があるためです。

MLFQ：基本ルール

MLFQアルゴリズムの基本的なルールを考慮してください。このアルゴリズムにはいくつかの実装がありますが、基本的なアプローチは似ています。

検討する実装では、MLFQにいくつかの個別のキューがあり、それぞれが異なる優先度を持ちます。いつでも実行可能なタスクは1つのキューにあります。 MLFQは優先順位を使用して、実行するタスクを決定します。優先度の高いタスク（優先度の高いキューからのタスク）が最初に起動されます。

間違いなく、複数のタスクが特定のキューに存在する可能性があるため、それらのタスクの優先順位は同じです。この場合、RRエンジンを使用して、これらのタスク間の起動をスケジュールします。

したがって、MLFQの2つの基本的なルールになります。

ルール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：タスクがシステムに入ると、最高のキューに入れられます
優先順位。
Rule4a：タスクが割り当てられた時間枠全体を使用する場合、
優先度が下がります。
Rule4b：タイムウィンドウが切れる前にタスクがCPUを解放する場合、
同じ優先度のままです。

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

この例でわかるように、入場時のタスクは最高の優先度で提示されます。 10ミリ秒のタイムウィンドウの後、スケジューラによってプロセスの優先度が下げられます。次の時間枠の後、タスクは最終的にシステム内で最も低い優先度に落ち、そこで残ります。

例2：彼らは短いタスクを持ち出しました

次に、MLFQがSJFに近づこうとする方法の例を見てみましょう。この例には2つのタスクがあります。AはCPUを常に占有する長時間実行されるタスクであり、Bは短い対話型タスクです。タスクBが到着するまでに、Aがすでにしばらく働いていたとします。

スクリプトの結果は、このグラフに表示されます。タスクAは、CPUを使用する他のタスクと同様に、一番下にあります。タスクBはT = 100に到着し、優先度が最も高いキューに配置されます。彼女の作品の時間は短いため、最終段階に達する前に終了します。

この例から、アルゴリズムの主な目標を理解する必要があります。アルゴリズムは長いタスクや短いタスクを知らないため、まずタスクが短いと仮定し、最高の優先順位を与えます。これが本当に短いタスクである場合、それはすぐに完了します。そうでない場合、それが長いタスクである場合、優先度がゆっくり下に移動し、すぐに応答を必要としない本当に長いタスクであることを証明します。

例3：I / Oはどうですか？

次に、I / Oの例を見てみましょう。ルール4bで述べたように、プロセスがプロセッサ時間を完全に利用せずにプロセッサを解放した場合、プロセスは同じ優先度レベルのままです。このルールの意図は非常に単純です。たとえば、ユーザーがキーまたはマウスを押すのを待つなど、対話型タスクが多数のI / O操作を実行する場合、そのようなタスクは割り当てられたウィンドウの前にプロセッサを解放します。このようなタスクを優先して省略したくないため、同じレベルのままになります。

この例は、このようなプロセスでアルゴリズムがどのように機能するかを示しています。I/ Oプロセスを実行する前に1msだけCPUを必要とする対話型タスクBと、常にCPUを使用する長いタスクAです。

MLFQは常に継続するため、プロセスBを最高の優先度で保持します。
CPUを解放します。 Bが対話型タスクの場合、アルゴリズムは対話型タスクをすばやく起動するという目標を達成しました。

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

前の例では、MLFQの基本バージョンを構築しました。そして、長いタスク間でプロセッサ時間を誠実に分配し、短いタスクや集中的にI / Oにアクセスするタスクが迅速に動作できるように、うまく、正直に仕事をしているようです。残念ながら、このアプローチにはいくつかの重大な問題があります。

まず、空腹の問題：システムに多くの対話型タスクがある場合、それらはすべてのプロセッサー時間を消費するため、単一の長いタスクを実行できません（飢えています）。

第二に 、賢いユーザーは自分のプログラムを書いて、
プランナーをだます。トリックは何かをすることです
プロセスにより多くのプロセッサ時間を与えるスケジューラ。アルゴリズム
上記のような攻撃は、このような攻撃に対して非常に脆弱です：時間枠が実質的に切れる前
I / O操作を実行する必要がありました（どのファイルに関係なく、一部に対して）
したがって、CPUを解放します。この動作により、同じ状態を保つことができます
キュー自体もCPU時間の割合が大きくなります。完了したら
これは正しいです（たとえば、CPUを解放する前のウィンドウ時間の99％）
そのようなタスクは、プロセッサを単純に独占できます。

最後に、プログラムは時間とともにその動作を変更できます。それらのタスク
CPUを使用したユーザーはインタラクティブになります。この例では、同様の
他の人が受け取るように、タスクはスケジューラから適切な処理を受けません
（初期）対話型タスク。

聴衆への質問：現代世界では、プランナーに対するどんな攻撃が可能でしょうか？

試行2：優先度を上げる

ルールを変更して、問題を回避できるかどうかを確認しましょう
断食。その関連性を確保するために私たちにできること
CPUタスクは時間を取得します（長くない場合でも）。
問題の簡単な解決策として、定期的に提供することができます
システム内のそのようなすべてのタスクの優先度を上げます。多くの方法があります。
これを達成するために、例として簡単なものを翻訳してみましょう：翻訳
すべてのタスクを一度に最高の優先度で、したがって新しいルール：

ルール5 ：Sの一定期間後、システム内のすべてのタスクを最高の優先度に転送します。

新しいルールは、2つの問題を同時に解決します。まず、プロセス
飢えないことを保証：最も優先度の高いタスクが共有されます
RRアルゴリズムによるプロセッサ時間、したがってすべてのプロセスが受信します
プロセッサー時間。第二に、以前に使用したプロセスがある場合
プロセッサのみがインタラクティブになり、より高いプロセッサと一致したままになります
優先度が一度高くなると、優先度が最も高くなります。
例を考えてみましょう。このシナリオでは、1つのプロセスを使用して検討します

CPUと2つの対話型の短いプロセス。図の左側の図は、優先順位を上げない場合の動作を示しているため、2つの対話型タスクがシステムに到着した後、長いタスクは飢え始めます。右側の図では、50ミリ秒ごとに優先度が上がるため、すべてのプロセスがプロセッサ時間を受け取ることが保証され、定期的に開始されます。この場合の50ミリ秒が例として採用されていますが、実際にはこの数はいくぶん大きいです。
明らかに、Sの周期的な増加期間の追加は、
論理的な質問：どの値を設定する必要がありますか？名誉ある
システムエンジニアのJohn Ousterhoutは、voo-dooのようなシステムで同様の量を呼び出しました
彼らは何らかの方法で正しいために黒魔術を必要としたため、定数
出品中。残念ながら、Sにはそのような香りがあります。値も設定した場合
大きな-長いタスクは飢え始めます。設定した値が低すぎると、
インタラクティブなタスクは、適切なプロセッサ時間を受け取りません。

試行3：ベストアカウンティング

解決する必要があるもう1つの問題があります。
プランナーをcheしましょうか？この機会の有罪は
ルール4a、4b。タスクが優先度を維持し、プロセッサを解放できるようにします
割り当てられた時間の満了前。これに対処する方法は？
この場合のソリューションは、それぞれのCPU時間の最適なアカウンティングと見なすことができます
MLFQレベル。プログラムが使用した時間を忘れる代わりに
割り当てられた期間のプロセッサ、それを考慮し、保存する必要があります。後
プロセスに費やされた時間は次の時間に短縮されるべきです
優先レベル。プロセスがその時間をどのように使用するかに関係なく-どのように
絶えずプロセッサー上で計算するか、同じくらい多くの呼び出し。このように
ルール4は次のように書き換える必要があります。

ルール4 ：タスクが現在のキューで割り当てられた時間を使い果たした後（CPUを解放した回数に関係なく）、そのようなタスクの優先度は低下します（キューを下に移動します）。

例を見てみましょう：

」

この図は、スケジューラをだまそうとするとどうなるかを示しています。
前のルール4a、4bであった場合、左側に結果が表示されます。ハッピーニュー
ルールは右側の結果です。保護の前に、プロセスは完了までI / Oを呼び出し、
したがって、動作に関係なく、保護を有効にした後、CPUを支配します
I / O、それはまだラインをドロップダウンし、したがって不正ではありません
CPUリソースを占有します。

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

上記の改善により、新しい問題が発生します。
質問-そのようなスケジューラをパラメータ化する方法は？つまりいくらですか
バースト？キュー内のプログラムウィンドウのサイズはどれくらいですか？どうやって
飢starを避けるために、プログラムの優先度を上げる必要があります。
プログラムの動作の変化を考慮しますか？これらの質問には、簡単なことはありません
応答と、負荷およびその後の設定による実験のみ
計画者は、満足のいくバランスをとることができます。

たとえば、ほとんどのMLFQ実装では、異なる
異なるキューへの時間間隔。通常、高優先度キュー
短い間隔が割り当てられます。これらのキューはインタラクティブなタスクで構成され、
切り替えは非常に敏感であり、10以下を要する
ミリ秒対照的に、低優先度キューは、次を使用する長いタスクで構成されます
CPU この場合、長い時間間隔は非常にうまく適合します（100ミリ秒）。

この例では、高優先度キューで機能する2つのタスクがあります20
ミリ秒、10ミリ秒間Windowsで破損。中程度のキュー（20msのウィンドウ）および低優先度で40ms
キュー時間枠は40ミリ秒になり、タスクが作業を完了しました。

SolarisのMLFQ実装は、タイムシェアリングスケジューラのクラスです。
スケジューラーは、どのようにすべきかを正確に決定するテーブルのセットを提供します
プロセスの存続期間の優先度を変更します。サイズはどうあるべきですか
選択したウィンドウと、タスクの優先度を上げる必要がある頻度。管理者
システムはこのテーブルと対話して、スケジューラを動作させることができます
別の方法で。デフォルトでは、このテーブルには60個の増分キューがあります。
20ミリ秒（高優先度）から数百ミリ秒（最低優先度）のウィンドウサイズ
また、すべてのタスクが1秒に1回ブーストされます。

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

最後に、多くのプランナーには他の機能があります。たとえば、
スケジューラは、オペレーティングシステムの最高レベルを予約します。
そのため、どのユーザープロセスも最高の優先度を得ることができません
システム。一部のシステムでは、支援するためにアドバイスを提供できます。
スケジューラーが優先順位を正しく設定します。たとえば、 niceコマンドを使用する
タスクの優先度を上げたり下げたりすることができます
プロセッサ時間のプログラムの可能性を減らします。

MLFQ：概要

MLFQと呼ばれる計画アプローチについて説明しました。彼の名前
仕事の原則で結論-それはいくつかのキューを持ち、フィードバックを使用します
タスクの優先度を決定します。
ルールの最終形式は次のとおりです。

ルール1 ：優先度（A）>優先度（B）の場合、タスクAは開始します（Bは開始しません）
ルール2 ：優先度（A）=優先度（B）の場合、RRを使用してA＆Bが開始されます
ルール3 ：タスクがシステムに入ると、最も高い優先度でキューに入れられます。
ルール4 ：タスクが現在のキューで割り当てられた時間を使い果たした後（CPUを解放した回数に関係なく）、そのようなタスクの優先度は低下します（キューを下に移動します）。
ルール5 ：Sの一定期間後、システム内のすべてのタスクを最高の優先度に転送します。

MLFQは次の理由で興味深い-の知識を要求する代わりに
事前にタスクの性質、アルゴリズムはタスクの過去の動作を調査し、設定します
それに応じて優先順位。したがって、彼は一度に2つの椅子に座ろうとします-小さなタスク（SJF、STCF）のパフォーマンスを達成し、正直に長く実行するために、
CPU読み込みジョブ。したがって、BSDおよびその派生物を含む多くのシステムは、
Solaris、Windows、Macはスケジューラとして何らかの形式のアルゴリズムを使用します
ベースフレームワークとしてのMLFQ。

オペレーティングシステム：3つの簡単なピース。パート5：計画：マルチレベルフィードバックキュー（翻訳）

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

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

MLFQ：基本ルール

試行1：優先度を変更する方法

試行2：優先度を上げる

試行3：ベストアカウンティング

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

MLFQ：概要

追加資料：

More articles:

オペレーティングシステム：3つの簡単なピース。 パート5：計画：マルチレベルフィードバックキュー（翻訳）

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

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

MLFQ：基本ルール

試行1：優先度を変更する方法

試行2：優先度を上げる

試行3：ベストアカウンティング

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

MLFQ：概要

追加資料：

More articles:

オペレーティングシステム：3つの簡単なピース。パート5：計画：マルチレベルフィードバックキュー（翻訳）