Linux は仮想メモリを実装するために何を使用しますか?

#LRU はパフォーマンスが優れていますが、レジスタとスタックのハードウェア サポートが必要であり、高価です。 #LRU は

のアルゴリズムです。理論的には、スタック アルゴリズムでは Belady 例外が発生することは不可能であることが証明できます。 FIFO アルゴリズムは、スタック アルゴリズムではなくキューに基づいて実装されます。

3.4 クロック (CLOCK) 置換アルゴリズムLRU アルゴリズムのパフォーマンスは OPT に近いですが、実装が難しく、高価です; FIFO アルゴリズムは実装が簡単ですが、パフォーマンスは劣ります。したがって、オペレーティング システムの設計者は、比較的少ないオーバーヘッドで LRU のパフォーマンスに近づけようと、多くのアルゴリズムを試してきましたが、これらのアルゴリズムはすべて CLOCK アルゴリズムの変形です。

単純な CLOCK アルゴリズムは、使用ビットと呼ばれる追加ビットを各フレームに関連付けます。ページが最初にメイン メモリにロードされ、その後アクセスされると、使用ビットは 1 に設定されます。

ページ置換アルゴリズムの場合、置換に使用される

のセットは 循環バッファ として扱われ、それに関連付けられたポインタを持ちます。ページが置き換えられると、ポインタはバッファ内の次のフレームを指すように設定されます。 ページを置換する時期が来ると、オペレーティング システムはバッファをスキャンして、使用ビットが 0 の最初のフレームを見つけます。使用ビット 1 を持つフレームに遭遇すると、オペレーティング システムはそのビットを 0 にリセットします。すべてのフレームの使用ビットが 1 の場合、ポインタはバッファ内で 1 サイクルを完了し、すべての使用ビットをクリアします。0 に設定してそのままになります。元の位置で、フレーム内のページを置き換えます。このアルゴリズムは各ページのステータスを周期的にチェックするため、CLOCK アルゴリズムと呼ばれ、

アルゴリズムとも呼ばれます。 CLOCK アルゴリズムのパフォーマンスは LRU に比較的近く、使用するビット数を増やすことで CLOCK アルゴリズムをより効率的にすることができます。

を 使用ビット used に追加すると、CLOCK 置換アルゴリズムが改善されます。 各フレームは、次の 4 つの状況のいずれかになります。

は最近アクセスされておらず、変更されていません (u=0、m=0)。
は最近アクセスされましたが、変更されていません (u=1、m=0)。
は最近アクセスされていませんが、変更されています (u=0、m=1)。
は最近アクセスされ、変更されました (u=1、m=1)。
アルゴリズムは次の手順を実行します。

ポインタの現在位置から開始して、フレーム バッファをスキャンします。このスキャン中、使用ビットは変更されません。最初に遭遇したフレーム (u=0、m=0) が置換対象として選択されます。
ステップ 1 が失敗した場合は、再スキャンして (u=0, m=1) のフレームを探します。最初に遭遇したそのようなフレームが置換対象として選択されます。このスキャン中に、スキップされたフレームごとに、その使用ビットが 0 に設定されます。
ステップ 2 が失敗した場合、ポインタは元の位置に戻り、セット内のすべてのフレームの使用ビットは 0 になります。ステップ 1 を繰り返し、必要に応じてステップ 2 を繰り返します。これにより、交換用のフレームが見つかります。
改良された CLOCK アルゴリズムは、

変更されていないページを優先するという点で、単純な CLOCK アルゴリズムよりも優れています。 変更されたページは置換される前に に書き戻す必要があるため、これにより時間が節約されます。

4.1 常駐セットのサイズページング仮想メモリの場合、実行の準備をするときに、プロセスのすべてのページをメイン メモリに読み込む必要はなく、また読み込むこともできないため、オペレーティング システムが読み込むページ数を決定する必要があります。言い換えると、

、これには次の点を考慮する必要があります。

割り当てられるストレージの量が少ないほど、メインメモリに一度に常駐できるプロセスが多いほど、プロセッサ時間をより効率的に使用できます。
プロセスのメイン メモリ内の
• pages

  が少なすぎる場合、局所性の原則にもかかわらず、ページ フォールト率 は依然として比較的高くなります。 。

• ページが多すぎる場合は、局所性の原則により、特定のプロセスにより多くのメイン メモリ領域を割り当てても、エラーに重大な影響はありません。プロセスの速度。
  これらの要因に基づいて、最新のオペレーティング システムでは通常、次の 3 つの戦略が採用されています。

固定割り当てのローカル置換
• : It Eachプロセスには、実行中に

  変更されない特定の数の物理ブロックが割り当てられます。プロセスの実行中にページ フォールトが発生した場合、プロセスのメモリ内にある ページから 1 ページだけを選択して交換し、必要なページを読み込むことができます。この戦略を実装する場合、各プロセスに割り当てる必要がある物理ブロックの数を決定するのは困難です。少なすぎるとページ フォールトが頻繁に発生し、多すぎると CPU やその他のリソースの使用率が低下します。 変数割り当てグローバル置換

  : これは、システム内の各プロセスに特定の数の物理ブロックを割り当てる、最も簡単に実装できる物理ブロックの割り当てと置換戦略です。オペレーティング システム自体も、空き物理ブロックのキューを維持します。プロセスでページフォルトが発生した場合、システムは
空き物理ブロックキューから物理ブロックを取り出してプロセス
• に割り当て、そこにロード対象のページをロードします。

• 可変割り当てローカル置換: 各プロセスに一定数の物理ブロックを割り当て、プロセス内でページフォルトが発生した場合、プロセスのメモリ上のページのみを割り当てます。他のプロセスの動作に影響を与えないように、ページを選択して入れ替えてください。プロセスの実行中にプロセス がページ ミスを頻繁に発生する場合、システム は、プロセスのページ ミス率が適切なレベルに達するまで、プロセスに物理ブロック を割り当てます。 、プロセス が実行中の場合 ページ フォールト率が特に低い場合は、 プロセスに割り当てられる物理ブロックの数 を適切に減らすことができます。

4.2 ページの読み込みのタイミング

• Pre-pagingStrategy: によると、局所性の原則、1 ページング戦略 複数の隣接するページは、一度に 1 ページをロードするよりも効率的である可能性があります。ただし、読み込まれたページのほとんどがアクセスされていない場合は、非効率的です。したがって、近い将来にアクセスされると予想されるページをメモリに事前にロードするには、予測ベースの事前ページング戦略を採用する必要があります。ただし、事前調整されたページの現在の成功率は約 50% にすぎません。したがって、この戦略は主にプロセスが初めてロードされるときに使用され、プログラマはどのページを最初にロードする必要があるかを指示します。

• リクエスト ページング

  戦略 : プロセスが操作中にアクセスする必要がある ページがメモリ内にないため、リクエストが行われます。 , by システムは必要なページをメモリにロードします。この戦略で転送されたページには確実にアクセスがあり、実装も比較的容易なため、現在の仮想メモリでは主にこの戦略が使用されています。欠点は、 は一度に 1 ページしかロードしないことです。多くのページが読み込まれたり読み出されたりすると、I/O オーバーヘッドが過剰に消費されることになります。

ページング システムの 外部ストレージをリクエストします。

ファイル領域 と、スワップ ページの保存に使用される スワップ領域 の 2 つの部分に分かれています。 スワップ領域は通常連続割り当て方式を使用しますが、ファイル領域は離散割り当て方式を使用するため、スワップ領域のディスクI/O速度はそれよりも高速です。ファイル領域の。quick。ページを転送できる状況は 3 つあります。

システムに十分なスワップ領域スペースがある
• :

  スワップ領域からすべて転送できるページング速度を向上させるには必須のページです。このため、プロセスを実行する前に、プロセスに関連するファイルをファイル領域 からスワップ領域 にコピーする必要があります。

システムには十分なスワップ領域スペースがありません
• : 変更されないすべての

  ファイルは、 ファイル領域#から直接コピーされます。 # #転送します (スワップアウト時に書き戻す必要はありません)。ただし、変更される可能性のあるパーツについては、スワップアウト時にスワップ領域に転送し、後で必要になったときにスワップ領域から元に戻す必要があります。

  UNIX の方法
: プロセスに関連するファイルはファイル領域に配置されるため、実行されていない
• ページはファイル領域から転送する必要があります。 ＃＃＃。以前に実行されたがスワップアウトされたページはスワップ領域に配置されるため、次回ロードされるときに

  がスワップ領域から転送される必要があります 。プロセスが要求した共有ページが他のプロセスによってメモリ上に転送された場合、スワップ領域から転送する必要はありません。 5. ページ ジッター (乱流) とワーキング セット (常駐セット)

5.1 ページ ジッター (乱流) )

ページ置換プロセス中の最悪の状況の 1 つは、スワップアウトされたばかりのページがすぐにスワップアウトされ、スワップインされたばかりのページもすぐにスワップアウトされることです。 、この 頻繁なページング動作はスラッシング、またはスラッシング と呼ばれます。プロセスが実行時間 よりも

頻繁なページ フォールト割り込み (ジッター) は、主に プロセスによって頻繁にアクセスされるページの数が、利用可能な物理ページ フレームの数よりも多いために発生します。仮想メモリ テクノロジにより、より多くのプロセスをメモリ内に保持して、システム効率を向上させることができます。定常状態では、メイン メモリのほぼすべてがプロセス ブロックによって占有されており、プロセッサとオペレーティング システムはできるだけ多くのプロセスに直接アクセスできます。しかし、適切に管理されていない場合、プロセッサの時間のほとんどは、プロセスの命令を実行するのではなく、ブロックのスワップ、つまりページのロード操作の要求に費やされることになり、システム効率が大幅に低下します。

5.2 ワーキング セット (常駐セット)

ワーキング セット (または常駐セット) は、プロセスが 特定の間隔内でアクセスするページのセット を指します。頻繁に使用されるページはワーキング セットに含める必要がありますが、長期間使用されなかったページはワーキング セットから破棄されます。システムのスラッシングを防ぐには、適切なワーキング セット サイズを選択する必要があります。

ワーキング セット モデルの原理は、オペレーティング システムが各プロセスのワーキング セットを追跡し、そのワーキング セットより大きい物理ブロックをプロセスに割り当てることです。空き物理ブロックがある場合は、別のプロセスをメモリに転送して、マルチプログラムの数を増やすことができます。すべてのワーキング セットの合計が増加して利用可能な物理ブロックの総数を超えると、オペレーティング システムはプロセスを一時停止し、ページアウトし、その物理ブロックを他のプロセスに割り当ててスラッシングを防ぎます。

ワーキング セットのサイズを正しく選択すると、 メモリ使用率とシステム スループットの向上 に重要な影響を与えます。

6. 概要

ページング管理メソッドと セグメンテーション管理メソッドは、メモリ内など多くの場所で類似しています。これらは不連続であり、アドレス マッピングなどを実行するためのアドレス変換メカニズムを備えています。表 3-20 は、ページング管理方式とセグメンテーション管理方式をさまざまな観点から比較したものです。