動的メモリ確保 (動的メモリアロケーション・動的メモリ割り当て・dynamic memory allocation) とは、メモリ管理のひとつである、プログラムを実行しながら、並行して必要なメモリ領域の確保と解放を行う仕組みである。メモリの利用状況は、自身の実行状況や他のプログラムの実行状況に応じて常に変動するため、そらら動作に支障を来さぬよう必要なメモリ領域を適切なアドレスに対して臨機応変に確保・解放を行う必要がある。現実のコンピュータでは、メモリに記憶できる情報の量は限られている。また、一つのプログラムやデータがメモリ全体を使いきってしまうことはできず、他のいろいろなプログラムやデータと分けあって使わなければならない。動的メモリアロケーションを使うことで、プログラムの実行時に必要な分だけ「メモリの分け前」 (記憶領域) を確保(allocate)し、また、記憶領域が不要になった時には、他のデータに再利用できるよう、解放 (release, free, deallocate) することができる。自動メモリアロケーション(スタック上に変数の記憶領域を確保する方式)や静的メモリアロケーションと異なり、確保すべき領域のサイズやメモリが確保・解放されるタイミング(生存期間)は、プログラム実行時に決定される。したがって、これらが外部からの入力や計算の進行状況によって決まる場合、動的メモリアロケーションが必要になる。確保するメモリ領域は連続している必要があるので、動的メモリアロケーションを実行するには、ヒープ領域（プログラムが自由に読み書きできる領域) から要求されたサイズの未使用領域のブロックを探す必要がある。メモリ確保は頻繁におこなわれる処理であり、扱うデータの量も大きいため、高速に行う必要があり難しい問題である。この問題には、様々なアルゴリズムが提案されてきた。メモリ確保アルゴリズムの主な課題は、確保と解放の速度、メモリの利用効率 (いかに空き領域を少なくするか)、メモリのフラグメンテーションを防いだデフラグすること、小さなサイズのメモリを大量に確保した場合に起こるオーバヘッド(無駄遣い)を削減することなどである。（最後の問題は、必要な記憶領域だけでなく管理用の付加的情報(メタデータ)を保存するための領域が必要になるために起こる。)ページング方式では、ページという単位に分割された空いているメモリを「論理アドレス空間」に配置し、それらのメモリだけが存在しているコンピュータであるかのようにプログラムに使わせることができる。物理アドレス（実際のメモリアドレス) では不連続な空き領域しかない場合でも、論理アドレスでは連続した領域であるようにマッピングすることができるため、未使用ページを単純に集め、空いているところから利用するだけで領域の割り当てを行うことができる。この領域確保は極めて効率がよいが、メモリの参照速度を保つためにはハードウェア(MMU)による対応が必須である。また、粒度の細かいページングは、ページングテーブル(物理アドレスと論理アドレスの対応表)が大きくなるため、4KB程度の大きなブロック単位でしか割り当てることができない。そこで、ページサイズ以上のメモリアロケーションはカーネルの仮想記憶機構に任せ、それより小さい領域の確保には動的メモリ確保のアルゴリズムを用いるのが一般的である。また、カーネルの内部では、デバイスドライバと機器の間でDirect Memory Accessによって通信するときのDMA領域の割り当てをおこなう場合など、物理アドレスが連続している領域が必要な場合があり、このような時はサイズの大小にかかわらず全て動的メモリ確保によってメモリを確保しなければならない。オブジェクト指向言語やLISPなどのプログラミング言語はオブジェクトが仮想空間上に散在（あるいは遍在）することになり、仮想記憶機構によるページアウトが大きな性能低下を招く。このためガベージコレクションでメモリ利用効率を上げる。ガベージコレクションによるメモリ解放は必ずしも物理ページの解放ではなく、解放したメモリ領域をそのプロセス内で再利用することが前提にある。実際に物理ページを解放するにはコンパクションによって解放すべき領域をまとめなければならない。もっとも単純なアルゴリズムは、未使用メモリ領域をサイズごとに分類し、これを線形リストに繋いでLIFO (スタック)として使用することである。要求されたサイズと同じか、ひとまわり大きいブロックをデータに割り当てることで使用する。この方法は単純な組み込みシステムなどで非常にうまく動作する。このリストを「フリーリスト」と呼ぶ。データ一つが必要とするメモリのサイズがあらかじめ分かっている場合は、そのサイズごとにフリーリストを準備し、そうでない場合は2のべき乗ごとに分類する。(2の累乗フリーリスト)2の累乗ごとのフリーリストでは、最大で50%の無駄が生じる。たとえば、65バイトのデータを格納するために、128バイトの領域を割り当てる必要があるためである。Two-Level Segregated Fit アロケータ (TLSFアロケータ、「2レベル分離適合割り当て器」)は、2のべき乗の分類の下に、さらに細かい分類を行うことでメモリ利用効率を改善する。空き領域を細かく分類して管理するので、要求されたサイズに最適なブロックがないこともあるが、細分類ごとの空き領域の有無をビットマップとして保持しているので、最適なサイズのブロックを即座に見つけだせるように工夫されている。速度については、平均的なケースではdmallocと比べて少し遅いが、固定サイズブロック割り当ての応用であるためどのような状況でも同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている。2003年に、リアルタイムオペレーティングシステムのアロケータとして発表された。TLSFアロケータを採用したシステムには、Morph OS などがある。未使用領域をサイズ順に並び替えておけば、要求されたサイズに最も近い未使用領域を比較的高速に(領域数に対し O(log n) の計算量で) 確保することができる。平衡2分木を用いれば、このような実装が可能である。ほかのアルゴリズムと比較すると遅いので、領域をできるだけ有効に使いたい場合にだけ使われることがある。Erlang 実行環境のアロケータ などで使用されている。別の解決策として「バディブロック・アロケータ」がある。このシステムでは、メモリは2の冪乗サイズの大きなブロックとして最初に確保される。要求されたサイズがブロックサイズの半分以下ならば、それを二つの同じサイズのブロックに分割する。これらを互いにバディブロック（Buddy Block; 相棒ブロック）と呼ぶ。その一方を選択して、要求されたサイズがブロックサイズの半分以上になるまで分割を続ける。残った各サイズのバディブロックはソートされた線形リストか木構造、あるいはサイズ毎の線形リストに保持される。ブロックが解放されると、対応するバディをチェックし、両方が解放された状態であればこれを結合して一段上のサイズのブロックとし、さらに結合できないかチェックしていく。ページングによる仮想記憶システムでバディブロックを使う場合、ページサイズ以上のメモリアロケーションは仮想記憶機構に任せるのが一般的である。そのため、ページサイズがバディブロック・アロケータの対象とするブロックサイズの上限となる。バディブロック・アロケータはリアルタイムオペレーティングシステムでよく使われるが、通常のオペレーティングシステムでも使われている（例えばLinuxカーネル）。SVR4やSolarisなどのカーネルでもこの機構をカーネル内の動的メモリアロケーションに使用している（Kernel Memory Allocatorと呼ばれている）。ユーザ空間プログラム(OS上で動くプログラム)は、動的に確保される記憶領域はヒープに配置される。ヒープとは、動的メモリ確保のための未使用メモリ領域の大きなプールのことである。(データ構造のヒープとは無関係。）ヒープからのメモリ割り当ては、言語の実行ランタイムや共有ライブラリ（多くはlibcなどの言語の基本ライブラリ）の関数(例えばmalloc)の中で行われる。静的メモリアロケーションとは、プログラムのコンパイル時にデータ領域の確保を決定すること。複数のサブルーチンや関数からアクセスされるグローバルなデータ領域、特にプログラム走行中常に使用されるものをこの方法で確保するのが一般的である。具体的な確保の方法はプログラミング言語に依存する。

出典:wikipedia