Javaスレッドとプロセスによって使用されるメモリ位置を追跡する C++ または C の場合のヒープ マネージャーまたは OS のデータ構造を理解したいと思いました。1 つの方法は、オブジェクトとメモリ アドレスのマップと、メモリ開始アドレスとメモリ内のオブジェクトのサイズの逆マップを使用することです。O(1)しかし、ここでは、新しいメモリ要求に間に合うように対応できません。これを行うためのより良いデータ構造はありますか?
1074 次
3 に答える
2
管理されていない言語は、システム コールを介してメモリの割り当て/解放を行うことに注意してください。通常、それ自体は管理しません。抽象化のレベル (OS から実行時間まで) に関係なく、これに対処する必要があります。
1 つの方法はバディ ブロック割り当てと呼ばれ、ウィキペディアの例で詳しく説明されています。基本的に、さまざまなサイズ (通常は 2 の倍数) のメモリ内のスペースの使用状況を追跡します。これは、巧妙なインデックス付けを使用して多数の配列を使用して行うことができます。または、より直感的にバイナリ ツリーを使用して行うことができます。各ノードは、特定のブロックが空いているかどうかを示し、レベル上のすべてのノードは同じサイズのブロックを表します。
これは、内部の断片化に悩まされます。物事が行き来するにつれて、データが効率的に統合されるのではなく散らばってしまい、大規模なデータに収まりにくくなる可能性があります. これは、より複雑で動的なシステムによって打ち消される可能性がありますが、バディ ブロックには単純さという利点があります。
于 2013-06-13T06:09:38.730 に答える
1
OS は、全体的なビューでプロセスのメモリ割り当てを追跡します。4KB ページまたはそれ以上の「塊」は、何らかの形式のリストに格納されます。
典型的な Windows 実装 (Microsoft の C ランタイム ライブラリ) では、少なくとも最近のバージョンでは、すべてのメモリ割り当ては HeapAlloc() システム コールによって行われます。そのため、すべてのヒープ割り当てが OS に渡されます。OSが実際にすべての割り当てを追跡するのか、それとも「何が無料で何が使用されているか」のマップを保持するだけなのかは別の問題です. ヒープ管理コードには「現在の割り当て」のリストがなく、解放されたメモリの塊のリストがあるだけだと私は理解しています
Linux/Unix では、C ライブラリは通常、小さな割り当てごとに OS を呼び出すことを避け、代わりに大量のメモリを使用し、割り当てごとにそれを小さな断片に分割します。繰り返しますが、ヒープ管理内で割り当てられたメモリは追跡されません。
これは、プロセス レベルで行われます。スレッドごとのレベルでメモリ割り当てを区別するオペレーティング システムを認識していません (TLS 以外 - スレッド ローカル ストレージですが、これは通常、典型的なヒープ コード管理の外にある非常に小さな領域です)。
つまり、要約すると、OS および/または C/C++ ランタイムは、使用されたすべての割り当てのリストを実際に保持するわけではなく、「解放された」メモリのリストを保持します [そして、別の塊が解放されると、通常は前のメモリに「結合」します断片化を減らすための次の連続した割り当て]。アロケーターが最初に開始されると、大きな塊が与えられ、それが単一の解放された割り当てとして割り当てられます。リクエストが行われると、塊がセクションに分割され、フリー リストが残りになります。その塊が十分でない場合、基盤となる OS 割り当てを使用して、別の大きな塊が分割されます。
割り当てごとに少量のメタデータが保存されます。これには、「割り当てられているメモリの量」などの情報が含まれており、このメタデータはメモリを解放するときに使用されます。通常、このデータは割り当てられたメモリの直前に格納されます。しかし、他の方法で割り当てを知らずに、割り当てメタデータを見つける方法はありません。
于 2013-06-13T07:34:19.937 に答える
0
C++ には自動ガベージ コレクションはありません。malloc/新しいヒープ メモリの割り当てには、free/delete を呼び出す必要があります。そこで、(メモリ リークをチェックする) valgrind などのツールが役に立ちます。参照できるヒープメモリを自動的に解放する auto_ptr のような他の概念があります。
于 2013-06-13T06:47:30.617 に答える