動的メモリ確保
動的メモリ確保（どうてきメモリかくほ、英: dynamic memory allocation）は、メモリ管理手法のひとつであり、プログラムを実行しながら、随時必要なメモリ領域の確保と解放を行なう仕組みである。動的メモリアロケーション、動的メモリ割り当てとも。
メモリの利用状況は、自身の実行状況や他のプログラムの実行状況に応じて常に変動するため、それらの動作に支障をきたさないよう必要なメモリ領域を適切なアドレスに対して臨機応変に確保・解放を行なう必要がある。
概要
[編集]現実のコンピュータでは、メモリに記憶できる情報の量は限られている。理論的なメモリアドレス空間（仮想アドレス）が必要十分に（例えば48ビットなど）確保されていても、たいてい物理的に搭載されているメモリ量はその上限よりも小さく、さらに個々のコンピュータハードウェアによって異なることが多い。また、マルチタスクシステムでは一つのプログラムやデータがメモリ全体を使いきってしまうことはできず、他のいろいろなプログラムやデータと分けあって使わなければならない。動的メモリ確保を使うことで、プログラムの実行時に必要な分だけ記憶領域を確保 (allocate) し、また、記憶領域が不要になったときには、他のデータに再利用できるよう、解放 (release, free, deallocate) することができる。物理メモリを仮想化し、個々のプログラムからの要求に応じて「メモリの分け前」を確保・調整するのは、オペレーティングシステムや標準ライブラリのような下位層の仕事である。
自動メモリ確保（スタック上に変数の記憶領域を確保する方式）や静的メモリ確保では、メモリ領域のサイズおよびメモリが確保・解放されるタイミング（生存期間）はプログラムの記述時に静的に決まる[1]。一方、動的メモリ確保では、メモリ領域のサイズおよびメモリが確保・解放されるタイミング（生存期間）はプログラムの実行時に動的に決まる。プログラムによっては、必要な領域のサイズが外部からの入力や計算の進行状況、あるいは実行環境（ハードウェア仕様）によって決まることがあり、このような場合は一般的に動的メモリ確保が適している。
下位レベルのレイヤーでは、動的確保で作成できるデータ構造は原始的な配列のみである。配列では、確保するメモリ領域は連続している必要があるので、動的メモリ確保を実行する際、ヒープ領域（プログラムが生存期間を制御でき、自由に読み書きできる領域）から要求されたサイズの未使用領域のブロックを探す必要がある。ユーザーの要求に応じて処理対象や処理内容が変化する複雑なプログラムほど、動的メモリ確保は頻繁に行なわれる傾向があり、また扱うデータの量も大きくなる。そのため、動的メモリ確保を高速に行なうことが要求されるが、これは一般的に難しい問題である。この問題には、様々なアルゴリズムが提案されてきた。
メモリ確保アルゴリズムの主な課題は、確保と解放の速度、メモリの利用効率（いかに空き領域を少なくするか）、メモリの断片化（フラグメンテーション）の防止と解消（デフラグ、コンパクション）、小さなサイズのメモリを大量に確保した場合に起こる空間的オーバーヘッド[2]を削減することなどである。
ページングと動的メモリ確保
[編集]ページング方式では、ページという単位に分割された空いているメモリを「論理アドレス空間」に配置し、それらのメモリだけが存在しているコンピュータであるかのようにプログラムに使わせることができる。物理アドレス（実際のメモリアドレス）では不連続な空き領域しかない場合でも、論理アドレスでは連続した領域であるようにマッピングすることができるため、未使用ページを単純に集め、空いているところから利用するだけで領域の割り当てを行なうことができる。
この領域確保は極めて効率がよいが、メモリの参照速度を保つためにはハードウェア（メモリ管理ユニット、MMU）による対応が必須である。また、粒度の細かいページングは、ページングテーブル（物理アドレスと論理アドレスの対応表）が大きくなるため、4KB程度の大きなブロック単位でしか割り当てることができない。そこで、ページサイズ以上のメモリアロケーションはカーネルの仮想記憶機構に任せ、それより小さい領域の確保には動的メモリ確保のアルゴリズムを用いるのが一般的である。また、カーネルの内部では、デバイスドライバと機器の間でDirect Memory Accessによって通信するときのDMA領域の割り当てを行なう場合など、物理アドレスが連続している領域が必要な場合があり[3]、このようなときは、サイズの大小にかかわらず、全て動的メモリ確保によってメモリを確保しなければならない。
オブジェクト指向言語やLISPなどのプログラミング言語はオブジェクトが仮想空間上に散在（あるいは遍在）することになり、仮想記憶機構によるページアウトが大きな性能低下を招く。このためガベージコレクションでメモリ利用効率を上げる。ガベージコレクションによるメモリ解放は必ずしも物理ページの解放ではなく、解放したメモリ領域をそのプロセス内で再利用することが前提にある。実際に物理ページを解放するにはコンパクションによって解放すべき領域をまとめなければならない。
固定サイズブロック・アロケーション
[編集]もっとも単純なアルゴリズムは、未使用メモリ領域をサイズごとに分類し、これを線形リストに繋いでLIFO（スタック）として使用することである。要求されたサイズと同じか、ひとまわり大きいブロックをデータに割り当てることで使用する。この方法は単純な組み込みシステムなどで非常にうまく動作する。このリストを「フリーリスト」と呼ぶ。データ一つが必要とするメモリのサイズがあらかじめ分かっている場合は、そのサイズごとにフリーリストを準備し、そうでない場合は2のべき乗ごとに分類する。(2の累乗フリーリスト)
TLSFアロケータ
[編集]2の累乗ごとのフリーリストでは、最大で50%の無駄が生じる。たとえば、65バイトのデータを格納するために、128バイトの領域を割り当てる必要があるためである。Two-Level Segregated Fit アロケータ (TLSFアロケータ、「2レベル分離適合割り当て器」) は、2のべき乗の分類の下に、さらに細かい分類を行なうことでメモリ利用効率を改善する。空き領域を細かく分類して管理するので、要求されたサイズに最適なブロックがないこともあるが、細分類ごとの空き領域の有無をビットマップとして保持しているので、最適なサイズのブロックを即座に見つけだせるように工夫されている[4][5]。
速度については、平均的なケースではdmallocと比べて少し遅いが、固定サイズブロック割り当ての応用であるためどのような状況でも同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている[4][6]。
2003年に、リアルタイムオペレーティングシステムのアロケータとして発表された[4]。
TLSFアロケータを採用したシステムには、Morph OS[7] などがある。
平衡2分木による方法
[編集]未使用領域をサイズ順に並べ替えておけば、要求されたサイズに最も近い未使用領域を比較的高速に（領域数に対し O(log n) の計算量で）確保することができる。平衡2分木を用いれば、このような実装が可能である。ほかのアルゴリズムと比較すると遅いので、領域をできるだけ有効に使いたい場合にだけ使われることがある。
Erlang 実行環境のアロケータ[8] などで使用されている。
バディブロック
[編集]別の解決策として「バディブロック・アロケータ」がある。このシステムでは、メモリは2の冪乗サイズの大きなブロックとして最初に確保される。要求されたサイズがブロックサイズの半分以下ならば、それを二つの同じサイズのブロックに分割する。これらを互いにバディブロック（Buddy Block; 相棒ブロック）と呼ぶ。その一方を選択して、要求されたサイズがブロックサイズの半分以上になるまで分割を続ける。残った各サイズのバディブロックはソートされた線形リストか木構造、あるいはサイズ毎の線形リストに保持される。ブロックが解放されると、対応するバディをチェックし、両方が解放された状態であれば、これを結合して一段上のサイズのブロックとし、さらに結合できないかチェックしていく。
ページングによる仮想記憶システムでバディブロックを使う場合、ページサイズ以上のメモリアロケーションは仮想記憶機構に任せるのが一般的である。そのため、ページサイズがバディブロック・アロケータの対象とするブロックサイズの上限となる。
バディブロック・アロケータはリアルタイムオペレーティングシステムでよく使われるが、通常のオペレーティングシステムでも使われている（例えばLinuxカーネル）。SVR4やSolarisなどのカーネルでもこの機構をカーネル内の動的メモリアロケーションに使用している（Kernel Memory Allocatorと呼ばれている）。
メモリを確保する領域
[編集]ユーザー空間プログラム（OS上で動くプログラム）は、動的に確保される記憶領域はヒープに配置される。ヒープとは、動的メモリ確保のための未使用メモリ領域の大きなプールのことである[9]。
ヒープからのメモリ割り当ては、プログラミング言語処理系の標準ランタイムライブラリ（C言語の場合はlibcやMSVC CRTなど）に実装されたサブルーチン（例えばC言語のmalloc関数など）の中で行なわれる。
静的メモリアロケーション
[編集]静的メモリアロケーションとは、プログラムのコンパイル時にデータ領域の確保を決定すること。複数のサブルーチンや関数からアクセスされるグローバルなデータ領域、特にプログラム走行中常に使用されるものをこの方法で確保するのが一般的である。具体的な確保の方法はプログラミング言語に依存する。
脚注
[編集]- ^ 一部の言語では、スタック上に可変長の領域（可変長配列）を確保することができるものもあるが、これは動的メモリ確保とは異なる仕組みに基づいており、スタック上限を超えて書き込もうとするとスタックオーバーフローする危険性がある。
- ^ データ本体の格納に必要な記憶領域だけでなく、領域サイズなど管理用の付加的情報（メタデータ）を保存するための領域が必要になるため、細切れに確保すると無駄が発生する。
- ^ “Dynamic DMA mapping using the generic device”. 2011年1月27日閲覧。 "Part Id - Streaming DMA mappings" 参照
- ^ a b c M. Masmano, I. Ripoll, A. Crespo (2003). Dynamic storage allocan for real-time embedded systems.
- ^ @Marupeke_IKD. “TLSFアロケータ”. 2012年2月12日閲覧。
- ^ Matthew Conte. “tlsf memory allocator implementation (TLSFの実装の公開ページ)”. 2012年2月18日閲覧。
- ^ “Morph OS Development”. 2012年1月27日閲覧。
- ^ “Erlang リファレンスマニュアル - erts_alloc (英語)”. 2012年1月26日閲覧。
- ^ データ構造のヒープとは無関係。