「断片化」は、実際にはあまり正確な用語ではありません。しかし、実行中のアプリケーションがバイトのブロックを必要とし、未使用のバイトnが1 つ以上あるにもかかわらず、必要なブロックを取得できない場合は、「メモリが断片化しすぎている」と断言できます。n
しかし、[ページング] は外部割り当て [断片化のことだと思います] にどのように役立ちますか?
複雑なことは何もありません。外部断片化は、アプリケーションの要件を満たすには「小さすぎる」割り当てられたブロック間の空きメモリです。これは一般的な概念です。「小さすぎる」の定義はアプリケーションに依存します。それにもかかわらず、割り当てられたブロックが任意の境界に落ちる可能性がある場合、多くの割り当てと割り当て解除の後、そのようなフラグメントが大量に発生するのは簡単です。ページングは、2 つの方法で外部断片化に役立ちます。
まず、メモリを固定サイズの隣接するチャンク (ページ) に分割します。これらのチャンクは「十分な大きさ」であるため、無駄になることはありません。ここでも、「十分な大きさ」の定義は正確ではありません。しかし、ほとんどのアプリケーションには、単一の 4k ページで満たすことができる多くの要件があります。ページ以下の割り当てでは外部フラグメンテーションの問題は発生しないため、問題は軽減されています。
第 2 に、ページング ハードウェアは、アプリケーション ページと物理メモリ ページとの間に一定レベルの間接性を提供します。したがって、どのような空き物理メモリ ページでも、アプリケーションの要求を満たすために使用できます。たとえば、物理ページが 100 ページあり、物理ページが 1 ページおきに (そのうち 50 ページが) 割り当てられているとします。ページ マッピング ハードウェアがなければ、満たすことができる連続メモリの最大要求は 1 ページです。マッピングありで50ページです。(物理ページがマップされていない状態で最初に割り当てられた仮想ページは無視しています。それは別の議論です。)
しかし、より小さな割り当ての場合はどうなるでしょうか?
繰り返しますが、それは非常に簡単です。割り当ての単位がページの場合、ページより小さい割り当ては未使用の部分を生成します。これは内部フラグメンテーションです: 割り当てられたブロック内の使用できないメモリ。アロケーション ユニットを大きくすればするほど (1 ページである必要はありません)、内部の断片化のために使用できなくなるメモリが増えます。平均すると、これはアロケーション ユニットの半分に近づく傾向があります。したがって、OS はページ単位で割り当てる傾向がありますが、ほとんどのアプリケーション側のメモリ アロケータは、OS から非常に少数 (多くの場合 1 つ) の大きなブロック (ページ) を要求します。それらは内部的にはるかに小さい割り当て単位を使用します。4 ～ 16 バイトはかなり一般的です。
問題は、外部割り当てをどのように処理するかです [フラグメンテーションを意味すると思います] ? それで、（最悪の場合を想定して）遅かれ早かれ、ページングの有無にかかわらず、ヒープメモリ（異なるサイズ）を割り当てて解放する長時間動作するアプリケーションは、外部の断片化のためにメモリ不足の状態に陥りますか？
私の理解が正しければ、断片化が避けられないかどうかを尋ねています。非常に特殊な状況 (アプリケーションが 1 つのサイズのブロックしか必要としないなど) を除いて、答えはイエスです。しかし、それが必ずしも問題であるというわけではありません。
メモリ アロケーターは、断片化を非常に効果的に制限するスマート アルゴリズムを使用します。たとえば、特定のリクエストに最も近いブロック サイズのプールを使用して、異なるブロック サイズの「プール」を維持する場合があります。これにより、内部および外部の断片化が制限される傾向があります。非常によく文書化されている実際の例はdlmallocです。ソースコードも非常に明確です。
もちろん、汎用アロケーターは特定の条件下で失敗する可能性があります。このため、最新の言語 (C++ と Ada は私が知っている 2 つです) では、特定の型のオブジェクトに専用のアロケーターを提供できます。通常、固定サイズのオブジェクトの場合、これらは事前に割り当てられた空きリストを維持するだけなので、その特定のケースの断片化はゼロであり、割り当て/割り当て解除は非常に高速です。
もう 1 つ注意:ガベージ コレクションをコピー/圧縮することで、断片化を完全になくすことができます。もちろん、これには基礎となる言語のサポートが必要であり、支払うべきパフォーマンスの請求書があります。コピー ガベージ コレクターは、ストレージを再利用するために実行されるたびに、オブジェクトを移動してヒープを圧縮し、未使用の領域を完全に排除します。これを行うには、実行中のプログラム内のすべてのポインターを、対応するオブジェクトの新しい場所に更新する必要があります。これは複雑に聞こえるかもしれませんが、コピー ガベージ コレクターを実装しましたが、それほど悪くはありません。アルゴリズムは非常にクールです。残念ながら、多くの言語 (C や C++ など) のセマンティクスでは、実行中のプログラムで必要なすべてのポインターを見つけることができません。
最も根本的な解決策は、ヒープの使用を禁止することですが、ページング、仮想アドレス空間、仮想メモリなどを備えたプラットフォームにヒープが本当に必要でしょうか...そして唯一の問題は、アプリケーションを何年も止められずに実行する必要があることですか?
汎用アロケータは優れていますが、保証されていません。セーフティ クリティカルなシステムやハード リアルタイム制約のあるシステムでは、ヒープの使用を完全に回避することは珍しくありません。一方、絶対的な保証が不要な場合は、汎用アロケーターで十分です。汎用アロケータを使用して長期間にわたって厳しい負荷をかけて完全に動作するシステムが多数あります。断片化は許容可能な安定状態に達し、問題は発生しません。
もう1つの問題..内部フラグメンテーションはあいまいな用語ですか?
この用語はあいまいではありませんが、さまざまなコンテキストで使用されます。不変なのは、割り当てられたブロック内の未使用のメモリを参照していることです。
OS の資料では、割り当て単位がページであると想定する傾向があります。たとえば、Linux sbrkでは、データ セグメントの末尾を任意の場所に設定するように要求できますが、Linux はバイトではなくページを割り当てるため、最後のページの未使用部分は、OS の観点から見ると内部断片化です。
アプリケーション指向の議論は、割り当てが任意のサイズの「ブロック」または「チャンク」にあると想定する傾向があります。dlmalloc は約 128 の個別のチャンク サイズを使用し、それぞれが独自の空きリストに保持されます。さらに、OS メモリ マッピング システム コールを使用して非常に大きなブロックをカスタムで割り当てるため、リクエストと実際の割り当ての間の不一致はせいぜいページ サイズ (マイナス 1 バイト) です。明らかにそれは多くのことを行っています内部の断片化を最小限に抑えます。特定の割り当てによって引き起こされた断片化は、リクエストと実際に割り当てられたチャンクとの差です。非常に多くのチャンク サイズがあるため、その差は厳密に制限されています。一方、チャンク サイズが多いと、外部の断片化の問題が発生する可能性が高くなります。空きメモリは、dlmalloc によって適切に管理されていても、アプリケーションの要件を満たすには小さすぎるチャンクで完全に構成されている場合があります。