動的メモリ確保

動的メモリ確保は、メモリ管理手法のひとつであり、プログラムを実行しながら、随時必要なメモリ領域の確保と解放を行なう仕組みである。動的メモリアロケーション、動的メモリ割り当てとも。

メモリの利用状況は、自身の実行状況や他のプログラムの実行状況に応じて常に変動するため、それらの動作に支障をきたさないよう必要なメモリ領域を適切なアドレスに対して臨機応変に確保・解放を行なう必要がある。

1. 概要
-----

現実のコンピュータでは、メモリに記憶できる情報の量は限られている。理論的なメモリアドレス空間が必要十分に確保されていても、たいてい物理的に搭載されているメモリ量はその上限よりも小さく、さらに個々のコンピュータハードウェアによって異なることが多い。また、マルチタスクシステムでは一つのプログラムやデータがメモリ全体を使いきってしまうことはできず、他のいろいろなプログラムやデータと分けあって使わなければならない。動的メモリ確保を使うことで、プログラムの実行時に必要な分だけ記憶領域を確保  し、また、記憶領域が不要になったときには、他のデータに再利用できるよう、解放  することができる。物理メモリを仮想化し、個々のプログラムからの要求に応じて「メモリの分け前」を確保・調整するのは、オペレーティングシステムや標準ライブラリのような下位層の仕事である。

自動メモリ確保や静的メモリ確保では、メモリ領域のサイズおよびメモリが確保・解放されるタイミングはプログラムの記述時に静的に決まる。一方、動的メモリ確保では、メモリ領域のサイズおよびメモリが確保・解放されるタイミングはプログラムの実行時に動的に決まる。プログラムによっては、必要な領域のサイズが外部からの入力や計算の進行状況、あるいは実行環境によって決まることがあり、このような場合は一般的に動的メモリ確保が適している。

下位レベルのレイヤーでは、動的確保で作成できるデータ構造は原始的な配列のみである。配列では、確保するメモリ領域は連続している必要があるので、動的メモリ確保を実行する際、ヒープ領域から要求されたサイズの未使用領域のブロックを探す必要がある。ユーザーの要求に応じて処理対象や処理内容が変化する複雑なプログラムほど、動的メモリ確保は頻繁に行なわれる傾向があり、また扱うデータの量も大きくなる。そのため、動的メモリ確保を高速に行なうことが要求されるが、これは一般的に難しい問題である。この問題には、様々なアルゴリズムが提案されてきた。

メモリ確保アルゴリズムの主な課題は、確保と解放の速度、メモリの利用効率、メモリの断片化の防止と解消、小さなサイズのメモリを大量に確保した場合に起こる空間的オーバーヘッドを削減することなどである。

2. ページングと動的メモリ確保
----------------

ページング方式では、ページという単位に分割された空いているメモリを「論理アドレス空間」に配置し、それらのメモリだけが存在しているコンピュータであるかのようにプログラムに使わせることができる。物理アドレスでは不連続な空き領域しかない場合でも、論理アドレスでは連続した領域であるようにマッピングすることができるため、未使用ページを単純に集め、空いているところから利用するだけで領域の割り当てを行なうことができる。

この領域確保は極めて効率がよいが、メモリの参照速度を保つためにはハードウェアによる対応が必須である。また、粒度の細かいページングは、ページングテーブルが大きくなるため、4KB程度の大きなブロック単位でしか割り当てることができない。そこで、ページサイズ以上のメモリアロケーションはカーネルの仮想記憶機構に任せ、それより小さい領域の確保には動的メモリ確保のアルゴリズムを用いるのが一般的である。また、カーネルの内部では、デバイスドライバと機器の間でDirect Memory Accessによって通信するときのDMA領域の割り当てを行なう場合など、物理アドレスが連続している領域が必要な場合があり、このようなときは、サイズの大小にかかわらず、全て動的メモリ確保によってメモリを確保しなければならない。

オブジェクト指向言語やLISPなどのプログラミング言語はオブジェクトが仮想空間上に散在することになり、仮想記憶機構によるページアウトが大きな性能低下を招く。このためガベージコレクションでメモリ利用効率を上げる。ガベージコレクションによるメモリ解放は必ずしも物理ページの解放ではなく、解放したメモリ領域をそのプロセス内で再利用することが前提にある。実際に物理ページを解放するにはコンパクションによって解放すべき領域をまとめなければならない。

3. 固定サイズブロック・アロケーション
--------------------

もっとも単純なアルゴリズムは、未使用メモリ領域をサイズごとに分類し、これを線形リストに繋いでLIFOとして使用することである。要求されたサイズと同じか、ひとまわり大きいブロックをデータに割り当てることで使用する。この方法は単純な組み込みシステムなどで非常にうまく動作する。このリストを「フリーリスト」と呼ぶ。データ一つが必要とするメモリのサイズがあらかじめ分かっている場合は、そのサイズごとにフリーリストを準備し、そうでない場合は2のべき乗ごとに分類する。

4. TLSFアロケータ
------------

2の累乗ごとのフリーリストでは、最大で50%の無駄が生じる。たとえば、65バイトのデータを格納するために、128バイトの領域を割り当てる必要があるためである。Two-Level Segregated Fit アロケータ  は、2のべき乗の分類の下に、さらに細かい分類を行なうことでメモリ利用効率を改善する。空き領域を細かく分類して管理するので、要求されたサイズに最適なブロックがないこともあるが、細分類ごとの空き領域の有無をビットマップとして保持しているので、最適なサイズのブロックを即座に見つけだせるように工夫されている。

速度については、平均的なケースではdmallocと比べて少し遅いが、固定サイズブロック割り当ての応用であるためどのような状況でも同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている。

2003年に、リアルタイムオペレーティングシステムのアロケータとして発表された。

TLSFアロケータを採用したシステムには、Morph OS などがある。

5. 平衡2分木による方法
-------------

未使用領域をサイズ順に並べ替えておけば、要求されたサイズに最も近い未使用領域を比較的高速に確保することができる。平衡2分木を用いれば、このような実装が可能である。ほかのアルゴリズムと比較すると遅いので、領域をできるだけ有効に使いたい場合にだけ使われることがある。

Erlang 実行環境のアロケータ などで使用されている。

6. バディブロック
----------

別の解決策として「バディブロック・アロケータ」がある。このシステムでは、メモリは2の冪乗サイズの大きなブロックとして最初に確保される。要求されたサイズがブロックサイズの半分以下ならば、それを二つの同じサイズのブロックに分割する。これらを互いにバディブロックと呼ぶ。その一方を選択して、要求されたサイズがブロックサイズの半分以上になるまで分割を続ける。残った各サイズのバディブロックはソートされた線形リストか木構造、あるいはサイズ毎の線形リストに保持される。ブロックが解放されると、対応するバディをチェックし、両方が解放された状態であれば、これを結合して一段上のサイズのブロックとし、さらに結合できないかチェックしていく。

ページングによる仮想記憶システムでバディブロックを使う場合、ページサイズ以上のメモリアロケーションは仮想記憶機構に任せるのが一般的である。そのため、ページサイズがバディブロック・アロケータの対象とするブロックサイズの上限となる。

バディブロック・アロケータはリアルタイムオペレーティングシステムでよく使われるが、通常のオペレーティングシステムでも使われている。SVR4やSolarisなどのカーネルでもこの機構をカーネル内の動的メモリアロケーションに使用している。

7. メモリを確保する領域
-------------

ユーザー空間プログラムは、動的に確保される記憶領域はヒープに配置される。ヒープとは、動的メモリ確保のための未使用メモリ領域の大きなプールのことである。

ヒープからのメモリ割り当ては、プログラミング言語処理系の標準ランタイムライブラリに実装されたサブルーチンの中で行なわれる。

8. 静的メモリアロケーション
---------------

静的メモリアロケーションとは、プログラムのコンパイル時にデータ領域の確保を決定すること。複数のサブルーチンや関数からアクセスされるグローバルなデータ領域、特にプログラム走行中常に使用されるものをこの方法で確保するのが一般的である。具体的な確保の方法はプログラミング言語に依存する。

9. 脚注
-----

10. 関連項目
--------

仮想記憶
malloc
mmap

en:Memory management#Dynamic memory allocation