メモリー管理の内側

動的アロケーションの選択肢とトレードオフ、そして実装

この記事では、Linux™ プログラマーに使用可能なメモリー管理手法の概要を理解します。C言語に焦点を当てて説明しますが、他の言語にも応用することができます。まずメモリー管理がどのように動作するのかの詳細を説明し、次に手動でメモリーを管理する方法、また参照カウントやプールを使った半手動での管理方法、さらにガーベジ・コレクションを使った自動的なメモリー管理方法についても説明します。

Jonathan Bartlett, Director of Technology, New Medio

閉じる [x]

Jonathan Bartlett は Linux アセンブリ言語を使ったプログラミングの入門書 Programming from the Ground Up の著者です。New Media Worx での主席開発者であり、顧客向けに Web アプリケーションや、ビデオ、キヨスク、デスクトップなどのアプリケーションを開発しています。



2004年 11月 16日

なぜメモリーを管理する必要があるのか

メモリー管理は、コンピューター・プログラミングにおける最も基本的な領域の一つです。多くのスクリプト言語ではメモリーがどのように管理されているかを気にする必要はありませんが、だからといってメモリー管理が重要ではない、ということにはなりません。メモリー・マネージャーの能力と限界を知ることは、効果的なプログラミングにとって致命的な重要性を持っています。CやC++など、大部分のシステム言語では、メモリー管理を行う必要があります。この記事ではメモリーの管理に関して、手動による方法、半自動的な方法、また自動的な方法の基本について説明します。

かつてApple IIによるアセンブリー言語の時代には、メモリー管理は大した問題ではありませんでした。基本的にプログラマーが全システムを管理できたのです。システムのメモリーがどうであっても、プログラマーが自由に管理できました。また、メモリーがどのくらいあるのかを気にする必要もありませんでした。どのコンピューターでも同じ量のメモリーしか持っていなかったからです。ですからメモリーに対する要求が非常に静的なものである場合には、メモリーのどの範囲を使うかを選択し、そこを使えば良かったのです。

ところが、そうした単純なコンピューターであっても、やはり問題はありました。特にプログラムの各部分に必要となってくるメモリーの量がよく分からない場合には、問題がやっかいでした。メモリー空間が限られており、しかもメモリー要求が変動する時には、下記のような要求に対応するための何らかの手段が必要になります。

  • データを処理するのに充分なだけのメモリーがあるかどうかを確認する
  • 使用可能なメモリーから一部の領域を確保する
  • ある部分のメモリーを、使用可能メモリーのプールに戻し、プログラムの他の部分や他のプログラムがそのメモリー部分を使えるようにする

こうした要求を実装するライブラリーは、メモリーを割り当てたり（allocating）、割り当て解除したり（deallocating）する責任を持つため、アロケーターと呼ばれます。プログラムが動的であればあるほどメモリー管理は重要な問題となり、従ってメモリー・アロケーターの選択が重要になってきます。ではメモリーを管理する様々な方法を見ながら、それぞれの利点と欠点、またどういう状況で最も力を発揮するのかを調べて行くことにします。

上に戻る

Cスタイルのメモリー・アロケーター

Cプログラミング言語は上記3つの要求を満たすために、2つの機能を提供しています。

  • malloc: 指定されたバイト数を割り当て、そのバイトへのポインターを返します。充分なメモリーが無い場合には、ヌル・ポインターを返します。
  • free:mallocで割り当てられたメモリー・セグメントへのポインターを取り、後でプログラムまたはOS（operating system）が使えるように、そのポインターを返します（一部のmalloc実装では、実際にはメモリーをプログラムにのみ返し、OSには返しません）。

物理メモリーと仮想メモリー

プログラム中でメモリーがどのように割り当てられるかを理解するために、まずそのプログラムが、OSからどのようにメモリーの割り当てを受けるかを理解する必要があります。コンピューターの各プロセスは、物理メモリーの全てにアクセスできるものだと思っています。当然ですが、複数のプログラムが同時に実行しているので、各プロセスが全メモリーを所有することはできません。そこでプロセスは仮想メモリーを使うようになります。

一例として、プログラムがメモリー・アドレス629をアクセスしているとしましょう。ところが仮想メモリー・システムでは、そこがRAMの位置629である必要はないのです。実際、もし物理RAMが一杯であれば、その位置はRAMの中ではなくディスクに移動されてしまっているかも知れません。つまり、アドレスが必ずしもメモリーの存在する物理位置を反映しないので、仮想メモリーと呼ばれるのです。OSは仮想アドレスと物理アドレスの変換テーブルを保持しているので、コンピューターのハードウェアはアドレス要求に対して適切に対応できます。そして、もしそのアドレスがRAMではなくディスク上にある場合は、一時的にプロセスを停止して他のメモリーをディスクにアンロードし、要求されたメモリーをディスクからロードし、そしてプロセスを再開します。こうして各プロセスは自分が動作するためのアドレス空間を取得し、物理的にインストールされているメモリーよりも多くのメモリーにアクセスできることになります。

32ビットのx86システムでは、各プロセスは4 GBのメモリーにアクセスすることができます。ほとんどの人はシステムに4 GBのメモリーを持つことはないので、スワップを含めても、一つのプロセス当たり4 GB以下である必要があります。ですからプロセスがロードされると、システム・ブレークと呼ばれるアドレスまでの初期メモリー割り当てを受けます。それから先は、RAMにもディスク上にも何ら対応する物理位置がない、マップされていないメモリーです。ですからプロセスが初期割り当てを使い切ってしまう時には、そのプロセスはOSに対して「もっとメモリーをマップしてくれ」と要求する必要があります。（マッピングは一対一対応に対する数学的な用語です。メモリーは、そのメモリーを保存すべき仮想アドレスに対応して物理位置があるときに「マップ」されます。）

Unixベースのシステムでは、追加のメモリーをマップするための基本的なシステム・コールが2つあります。

  • brk:brk() は非常に単純なシステム・コールです。先ほどのシステム・ブレーク、つまりそのプロセスに対してマップされたメモリーの末端位置、を覚えていますか？brk() は、プロセスにメモリーを追加したり、プロセスからメモリーを削除したりするために、システム・ブレークの位置を単純に前や後に移動します。
  • mmap:mmap() または「メモリー・マップ」はbrk() と似ていますが、より柔軟です。まずmmap() は、メモリーを単にプロセスの最後だけではなく、どこにでもマップすることができます。次に、仮想アドレスを物理RAMにマップしたりスワップしたりできるだけではなく、仮想アドレスをファイルやファイル位置にマップすることができます。ですからメモリー・アドレスを読んだり書いたりすることで、ファイルとの間でデータを読んだり書いたりすることができるのです。ただしここでは、マップされたRAMをプロセスに追加できるというmmapの機能にのみ注目します。munmap() はmmap() の逆を行います。

これで分かる通り、brk() またはmmap() を使うと、プロセスに仮想メモリーを追加することができます。brk() の方がより単純で一般的なので、ここではbrk() を使います。

単純アロケーターを実装する

Cプログラミングの経験が豊富な人であれば、malloc() やfree() を大いに使ったことがあるでしょう。ただ、それらがOSの中でどのように実装されているかを考える時間はあまり無かったかも知れません。このセクションでは、どんなものがメモリー管理に関係するかを例示するために、mallocとfreeを単純に実装するコードを示します。

この例を試すには、このコード・リストをコピーし、malloc.cというファイルに貼り付けます。下記のリストの説明では、一度に一カ所ずつ説明することにします。

大部分のOSでは、メモリー割り当ては単純な2つの機能で処理されます。

  • void *malloc(long numbytes): これはnumbytesだけのバイト数のメモリーを割り当て、最初のバイトへのポインターを返します。
  • void free(void *firstbyte): その前のmallocが返したポインターを与えると、そのプロセスの「空き空間」となった空間を提供します。

malloc_init は、私達のメモリー・アロケーターを初期化するためのファンクションになるもので、次の3つのことをします。アロケーターが初期化中であることをマーク付けし、システム上での最後の有効メモリー・アドレスを見つけ、そして管理されるメモリーの最初の位置にポインターを設定します。この3つの変数はグローバル変数です。

リスト1. 単純アロケーターでのグローバル変数
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;

先に述べた通り、マップされたメモリーの端、つまり最後の有効アドレスは、システム・ブレークまたはカレント・ブレークとして知られています。多くのUNIX®システムでは、現在のシステム・ブレークを見つけるには、ファンクションsbrk(0) を使います。sbrkは現在のシステム・ブレークを、その引き数にあるバイト数だけ移動してから新しいシステム・ブレークを返します。引き数0でsbrkを呼ぶと、単純に現在のブレークを返します。下記はmalloc初期化コードで、現在のブレークを見つけ、私達の変数を初期化します。

リスト2. アロケーターの初期化ファンクション
/* Include the sbrk function */
#include <unistd.h>
void malloc_init()
{
	/* grab the last valid address from the OS */
	last_valid_address = sbrk(0);

	/* we don't have any memory to manage yet, so
	 *just set the beginning to be last_valid_address
	 */
	managed_memory_start = last_valid_address;
	/* Okay, we're initialized and ready to go */
 	has_initialized = 1;
}

さて、適切にメモリーを管理するには自分が何を割り当て、何を割り当て解除しているかを追跡できる必要があります。つまりブロックに対してfreeが呼ばれた後は未使用としてそのブロックをマーク付けしたり、mallocが呼ばれた時には未使用ブロックを見つけたりできる必要があります。ですから、mallocで返されるメモリー断片の開始部分はどれも、先頭に次のような構造を持つことになります。

リスト3. メモリー制御ブロックの構造の定義
struct mem_control_block {
	int is_available;
	int size;
};

これではmallocを呼ぶプログラムに問題を起こすだろう、と皆さんは考えるかも知れません。プログラムはどうやって、このstructについて知るのでしょう？ 実はプログラムはそれを知る必要がない、というのが答えなのです。つまりこのstructを返す前に、ポインターをこのstructの先にまで動かすことによってstructを隠すのです。こうすることによって、返されたポインターが、他のどの用途にも使われていないメモリーを指すことになります。ですから呼び出し側のプログラムから見ると、プログラムが手に入れるのは全て、誰にも使われていない空きのメモリーとなります。次にプログラムがポインターをfree() で戻すと、数メモリー・バイト戻り、再度この構造を見つけることになります。

メモリーの割り当てについて説明する前に、メモリーの解放の方が単純なので、解放についてまず説明することにしましょう。メモリーを解放するために必要なのは、与えられたポインターを取り、sizeof(struct mem_control_block) バイトだけバックアップし、使用可能であるとしてメモリーをマーク付けするだけです。そのためのコードを次に示します。

リスト4. 割り当て解除ファンクション
void free(void *firstbyte) {
	struct mem_control_block *mcb;
	/* Backup from the given pointer to find the
	 * mem_control_block
	 */
	mcb = firstbyte - sizeof(struct mem_control_block);
	/* Mark the block as being available */
	mcb->is_available = 1;
	/* That's It!  We're done. */
	return;
}

見てお分かりの通り、このアロケーターによるメモリーの解放は、非常に単純な機構を使って一定時間で行われます。メモリーの割り当ては、もう少し難しくなります。下記はそのアルゴリズムの概要です。

リスト5. メイン・アロケーター用の擬似コード
1. If our allocator has not been initialized, initialize it.
2. Add sizeof(struct mem_control_block) to the size requested.
3. Start at managed_memory_start.
4. Are we at last_valid address?
5. If we are:
   A. We didn't find any existing space that was large enough
      -- ask the operating system for more and return that.
6. Otherwise:
   A. Is the current space available (check is_available from
      the mem_control_block)?
   B. If it is:
      i)   Is it large enough (check "size" from the
           mem_control_block)?
      ii)  If so:
           a. Mark it as unavailable
           b. Move past mem_control_block and return the
              pointer
      iii) Otherwise:
           a. Move forward "size" bytes
           b. Go back go step 4
   C. Otherwise:
      i)   Move forward "size" bytes
      ii)  Go back to step 4

つまり基本的に、空いているメモリーの塊を探すために、リンク付きポインターを使ってメモリーをウォークスルーしているのです。下記がそのコードです。

リスト6. メイン・アロケーター
void *malloc(long numbytes) {
	/* Holds where we are looking in memory */
	void *current_location;
	/* This is the same as current_location, but cast to a
	 * memory_control_block
	 */
	struct mem_control_block *current_location_mcb;
	/* This is the memory location we will return.  It will
	 * be set to 0 until we find something suitable
	 */
	void *memory_location;
	/* Initialize if we haven't already done so */
	if(! has_initialized) 	{
		malloc_init();
	}
	/* The memory we search for has to include the memory
	 * control block, but the users of malloc don't need
	 * to know this, so we'll just add it in for them.
	 */
	numbytes = numbytes + sizeof(struct mem_control_block);
	/* Set memory_location to 0 until we find a suitable
	 * location
	 */
	memory_location = 0;
	/* Begin searching at the start of managed memory */
	current_location = managed_memory_start;
	/* Keep going until we have searched all allocated space */
	while(current_location != last_valid_address)
	{
		/* current_location and current_location_mcb point
		 * to the same address.  However, current_location_mcb
		 * is of the correct type, so we can use it as a struct.
		 * current_location is a void pointer so we can use it
		 * to calculate addresses.
		 */
		current_location_mcb =
			(struct mem_control_block *)current_location;
		if(current_location_mcb->is_available)
		{
			if(current_location_mcb->size >= numbytes)
			{
				/* Woohoo!  We've found an open,
				 * appropriately-size location.
				 */
				/* It is no longer available */
				current_location_mcb->is_available = 0;
				/* We own it */
				memory_location = current_location;
				/* Leave the loop */
				break;
			}
		}
		/* If we made it here, it's because the Current memory
		 * block not suitable; move to the next one
		 */
		current_location = current_location +
			current_location_mcb->size;
	}
	/* If we still don't have a valid location, we'll
	 * have to ask the operating system for more memory
	 */
	if(! memory_location)
	{
		/* Move the program break numbytes further */
		sbrk(numbytes);
		/* The new memory will be where the last valid
		 * address left off
		 */
		memory_location = last_valid_address;
		/* We'll move the last valid address forward
		 * numbytes
		 */
		last_valid_address = last_valid_address + numbytes;
		/* We need to initialize the mem_control_block */
		current_location_mcb = memory_location;
		current_location_mcb->is_available = 0;
		current_location_mcb->size = numbytes;
	}
	/* Now, no matter what (well, except for error conditions),
	 * memory_location has the address of the memory, including
	 * the mem_control_block
	 */
	/* Move the pointer past the mem_control_block */
	memory_location = memory_location + sizeof(struct mem_control_block);
	/* Return the pointer */
	return memory_location;
 }

そして、これが私達のメモリー・マネージャーです。今度はこれをビルドし、私達のプログラムで実行できるようにするだけです。

malloc準拠のアロケーター（実はrealloc() のようなファンクションが欠けているのですが、malloc() とfree() が主なファンクションです）をビルドするためには、次のコマンドを実行します。

リスト7. アロケーターをコンパイルする
gcc -shared -fpic malloc.c -o malloc.so

これでmalloc.soという名前のファイルが作られますが、これが私達のコードを含む共有ライブラリーです。

これによってUNIXシステムでは、下記のようにすることによって、システムのmalloc() の代わりに自分のアロケーターが使えるようになります。

リスト8. 標準のmallocを入れ換える
LD_PRELOAD=/path/to/malloc.so
export LD_PRELOAD

LD_PRELOAD環境変数はダイナミック・リンカーに対して、実行可能ファイルを何かロードする前に、与えられた共有ライブラリーのシンボルをロードするようにさせます。また指定されたライブラリーにおけるシンボルに優先権を与えます。ですからこの記事でこの先開始するアプリケーションはどれも、システムのmalloc() ではなく、私達が作るmalloc() を使います。malloc() を使わないアプリケーションも幾つかありますが、それは例外です。それ以外の、realloc() のようなメモリー管理ファンクションを使うアプリケーションや、malloc() の内部的な振る舞いに関して不的確な想定をしているアプリケーションは、恐らくクラッシュしてしまいます。ashシェルは、私達の新しいmalloc() を使っても問題なく動作するようです。

自分のmalloc() が確かに使われていることを確認したいのであれば、このファンクションのエントリー・ポイントにwrite() へのコールを追加することでテストを行います。

私達のメモリー・マネージャーには足りない部分が多々ありますが、メモリー・マネージャーが何をすべきかを示すためには充分です。欠点としては次のようなものです。

  • システム・ブレーク（グローバル変数）上で動作するので、他のアロケーターやmmapと共存することができません。
  • メモリーを割り当てる時の最悪シナリオでは、プロセスのメモリーのすべてに渡ってウォークする必要があります。これにはディスク上に置かれた、大量のメモリーも含みます。つまりOSはデータをディスクとの間でデータを移動するために、多くの時間を費やさざるを得ないことを意味します。
  • メモリー不足エラーをうまく処理する手段がありません（mallocは単純に成功すると想定してしまいます）。
  • realloc() など、他のメモリー・ファンクションの多くを実装していない。
  • sbrk() は要求よりも多くのメモリーを戻すかもしれないので、ヒープの最後で、一部のメモリーをリークすることになります。
  • is_availableフラグは、1ビットの情報しか含んでいないにもかかわらず、4バイトのワードをフルに使用してしまいます。
  • このアロケーターはスレッド・セーフではありません。
  • このアロケーターは、空き空間を大きなブロックにまとめることができません。
  • このアロケーターで使用しているアルゴリズム（fitting algorithm）は、潜在的に多くのメモリー・フラグメント化を引き起こす可能性があります。
  • 他にもまだまだ問題があると思います。ですから、あくまでも例としているのです！

他のmalloc実装

malloc() の実装には多くの種類があり、それぞれ強みと弱みがあります。アロケーターの設計にあたっては、幾つかのトレードオフを考慮する必要があります。

  • 割り当ての速さ
  • 割り当て解除の速さ
  • スレッド化環境での振る舞い
  • メモリーが一杯に近い時の振る舞い
  • キャッシュの局所性（cache locality）
  • メモリーの使用管理に費やされるオーバーヘッド
  • 仮想メモリー環境での振る舞い
  • 小さなオブジェクトが対象か、大きなオブジェクトが対象か
  • リアルタイム性の保証

それぞれの実装には特有の利点と欠点があります。私達の単純アロケーターでは、割り当ては非常に遅いのですが、割り当て解除は非常に高速でした。また仮想メモリーシステムに対する振る舞いが不備なため、最もうまく動作するのは大きなオブジェクトを扱う時です。

他にも数多くのアロケーターがあります。その幾つかは下記のようなものです。

  • Doug Lea Malloc: Doug Lea Mallocは実は、Doug Leaによる元々のアロケーターとGNU libcアロケーター、それにptmallocを含めた、アロケーター・ファミリーの全体を指します。Doug Leaのアロケーターは私達のアロケーターと基本的な構造はほとんど同じですが、検索を早めるためにインデックスを採り入れており、未使用の塊を幾つか組み合わせて一つの大きな塊にする機能を持っています。また最近解放されたメモリーの再利用を高速化するために、キャッシュを使用することができます。ptmallocはDoug Lea Mallocの一つのバージョンであり、複数スレッドをサポートするように拡張されています。Doug LeaによるMalloc実装を説明した論文は、この記事の最後の参考文献に挙げてあります。
  • BSD Malloc: BSD Mallocは4.2 BSDと共に配布された実装で、FreeBSDに含まれており、あらかじめ決められたサイズのオブジェクトを集めたプールにあるオブジェクトを割り当てるアロケーターです。これは2の累乗マイナス定数、であるオブジェクト・サイズに対するサイズ・クラスを持っています。ですから、ある指定サイズのオブジェクトを要求すると、そのオブジェクトに合うサイズ・クラスであればどんなものにでも単純に割り当てます。これによって高速実装が可能ですが、メモリーを浪費する可能性があります。この実装を説明した論文は、この記事の最後の参考文献に挙げてあります。
  • Hoard: Hoardは、マルチスレッド環境で非常に高速になることを目標に書かれました。ですから、メモリー割り当てのためにどれかのプロセスが待ったりする必要がないように、ロックを最大限利用するように構成されています。これを使うと、大量の割り当て、割り当て解除を行うマルチスレッド・プロセスが劇的に高速化されます。この実装を説明した論文は、この記事の最後の参考文献に挙げてあります。

これらは、数多くあるアロケーターのうち、最もよく知られたものです。もし皆さんのプログラムが割り当てに関して特別な要求をしている場合には、そのプログラムでのメモリー割り当て方法に適した、カスタムのアロケーターを書いた方が良いかも知れません。ただしアロケーターの設計に慣れていない場合には、カスタムのアロケーターは問題を解決するよりも、問題を作り出してしまいがちなものです。この件に関しての紹介記事としては、Donald KnuthによるThe Art of Computer Programming Volume 1: Fundamental Algorithmsのsection 2.5、「Dynamic Storage Allocation」（参考文献にリンクがあります）があります。この記事は仮想メモリー環境を考慮に入れていないので少し古いのですが、大部分のアルゴリズムは、そこに示されたものに基づいています。

C++では、operator new() をオーバーロードすることによって、自分独自のアロケーターをクラス単位、またはテンプレート単位ベースで実装することができます。Andrei AlexandrescuによるModern C++ DesignのChapter 4「Small Object Allocation」では、小さなオブジェクト・アロケーターを説明しています（参考文献にリンクがあります）。

malloc() ベースのメモリー管理の欠点

私達のメモリー・マネージャーに欠点があるだけではなく、malloc() ベースのメモリー管理には、どのようなアロケーターを使っても残ってしまう数多くの欠点があります。長期間実行するストレージを確保しておく必要のあるプログラムにとっては、malloc() でメモリーを管理するのは気の遠くなるような作業です。メモリーへの参照が数多く点在している場合には、いつメモリーを解放すべきかを知るのは困難なものです。生存時間が現在のファンクションに限られているメモリーの管理はごく簡単ですが、現在のファンクションを超えて生存するメモリーに対しては、管理がずっと困難になります。また多くのAPIでは、メモリー管理の責任が呼び出し側のプログラムにあるのか、呼ばれたファンクションの側にあるのかに関して、明確になっていません。

メモリー管理には多くの問題があるため、多くのプログラムでは、メモリー管理ルールを中心にしています。C++の例外処理は、このタスクをより問題の多いのものにしています。時には、メモリー割り当てやクリーン・アップを管理するためのコードの方が、実際の計算タスクを実現するためのコードよりも多いことすらあるのです！ そこでメモリー管理の手段として、他の方法を調べて見ることにします。

上に戻る

半自動のメモリー管理戦略

参照カウント

参照カウントは半自動のメモリー管理手法です。つまり一部でプログラマーによるサポートを必要としますが、オブジェクトがもはや使われていないのはいつなのか、プログラマーは確実に知らなくても良いのです。つまり参照カウントが、代わりにそれをしてくれるのです。

参照カウントでは、全ての共有データ構造は、その構造に対して現在アクティブな「参照」の数を保持するフィールドを持っています。データ構造へのポインターがプロシージャーに渡されると、そのプロシージャーは参照カウントに追加します。基本的にデータ構造に対して、そのデータ構造が保存されているのは何カ所かを伝えるのです。次にそのプロシージャーがデータ構造を使い終わると、参照カウントを減らします。この時には、カウントがゼロにまで落ちたかもチェックします。もしゼロになっていれば、メモリーを解放します。

この利点は、与えられたデータ構造がプログラムの中でたどる可能性のある全パスを追跡する必要はない、ということです。そのデータ構造に対するローカル参照はそれぞれ単純に、必要に応じてカウントを増加または減少させます。これによって、まだ使用している最中に解放されるのを防ぐことができます。だだし参照カウントされたデータ構造を使う場合には必ず、参照カウント・ファンクションを実行することを忘れるべきではありません。また、組み込みのファンクションやサード・パーティーのライブラリーは、あなたの参照カウント機構のことを知らず、また使うこともできません。参照カウントはまた、循環参照を持つ構造では困難です。

参照カウントを実装するには、単純に参照カウントを増加するファンクションと、参照カウントを減少するファンクション（カウントがゼロになったらメモリーを解放します）という、2つのファンクションが必要なだけです。

参照をカウントするファンクション・セットの一例は下記のようなものです。

リスト9. 基本的な参照カウント・ファンクション
/* Structure Definitions*/
/* Base structure that holds a refcount */
struct refcountedstruct
{
	int refcount;
}
/* All refcounted structures must mirror struct
 * refcountedstruct for their first variables
 */
/* Refcount maintenance functions */
/* Increase reference count */
void REF(void *data)
{
	struct refcountedstruct *rstruct;
	rstruct = (struct refcountedstruct *) data;
	rstruct->refcount++;
}
/* Decrease reference count */
void UNREF(void *data)
{
	struct refcountedstruct *rstruct;
	rstruct = (struct refcountedstruct *) data;
	rstruct->refcount--;
	/* Free the structure if there are no more users */
	if(rstruct->refcount == 0)
	{
		free(rstruct);
	}
}

REFとUNREFは、皆さんが何をしたいかによって、もう少し複雑になるかも知れません。例えば、マルチスレッド化したプログラムに対してロックを追加したり、またrefcountedstructを拡張して、メモリーを解放する前に呼ぶべきファンクションへのポインターを含むようにしたいかも知れません。（これはオブジェクト指向言語でのデストラクターに似ていますが、構造がポインターを含む場合には必要です）。

REFとUNREFを使う場合には、ポインター割り当てとして次のようなルールに従う必要があります。

  • 割り当て前に左側のポインターが指している値はUNREF（参照解除）する
  • 割り当て後には、左側のポインターが指している値はREF（参照）する

refcounted構造を渡されるファンクションでは、次のようなルールに従う必要があります。

  • ファンクションの最初で、すべてのポインターをREF（参照）する
  • ファンクションの最後で、全てのポインターをUNREF（参照解除）する

下記は、参照カウントを使う簡単なコード例です。

リスト10. 参照カウントを使う例
/* EXAMPLES OF USAGE */

/* Data type to be refcounted */
struct mydata
{
	int refcount; /* same as refcountedstruct */
	int datafield1; /* Fields specific to this struct */
	int datafield2;
	/* other declarations would go here as appropriate */
};

/* Use the functions in code */
void dosomething(struct mydata *data)
{
	REF(data);
	/* Process data */
	/* when we are through */
	UNREF(data);
}

struct mydata *globalvar1;
/* Note that in this one, we don't decrease the
 * refcount since we are maintaining the reference
 * past the end of the function call through the
 * global variable
 */
void storesomething(struct mydata *data)
{
	REF(data); /* passed as a parameter */
	globalvar1 = data;
	REF(data); /* ref because of Assignment */
	UNREF(data); /* Function finished */
}

参照カウントは非常に簡単なので、大部分のプログラマーはライブラリーを使わずに、自分で実装しています。ただしそうしたプログラマーも、実際にメモリーを割り当てたり解放したりするには、やはりmallocやfreeのような低レベルのアロケーターに依存しています。

参照カウントは、Perlのような高級言語ではメモリー管理を行うために頻繁に使われます。こうした言語では、言語が自動的に参照カウントを処理するので、拡張モジュールを書くこと以外、プログラマーは全く気にする必要はありません。この場合は全てを参照カウントする必要があるため、いくらかスピードが低下することになりますが、非常に安全性が高まり、またプログラミングが容易にもなります。利点としては次が挙げられます。

  • 実装が単純になる
  • 簡単に使用できる
  • 参照はデータ構造の一部なので、キャッシュの局所性が適切である

ただし、欠点もあります。

  • 参照カウント・ファンクションを必ず、忘れずに呼ぶ必要がある
  • 循環データ構造の一部である構造は解放しない
  • ほとんど全てのポインター割り当てで速度が低下する
  • 参照カウントされたオブジェクトを使用している時に例外処理（例えばtryまたはsetjmp()/longjmp()など）を行う際には、特に注意を払う必要がある
  • 参照を処理するために、追加のメモリーを必要とする
  • 参照カウンターは、大部分のマシンでは最初にアクセスされる、構造の最初の位置を占めてしまう
  • マルチスレッド環境では、より遅く、実行がより困難である

C++では、参照カウントなどのようなポインター処理の詳細を処理するスマート・ポインターを使うことで、プログラマーによる間違いをいくらか減らすことができます。ただし、（例えばCライブラリーへのリンクなど）スマート・ポインターを処理できないレガシー・コードを使わざるを得ない時には、参照カウントを使わない時よりもずっと複雑に絡まった、とんでもない混乱に陥ることが普通です。ですから普通は、C++のみのオブジェクトに対してのみ有効です。もし皆さんがスマート・ポインターを使いたいのであれば、Alexandrescu著によるModern C++ Designの「Smart Pointers」の章を絶対に読む必要があります。

メモリー・プール

メモリー・プールは、メモリー管理を半自動化するための、もう一つの方法です。メモリー・プールは、各ステージが特定な処理専用に割り当てられたメモリーを持つような、特定なステージを通るプログラムに対するメモリー管理を自動化するための助けになります。例えば、多くのネットワーク・サーバー・プロセスでは、コネクション毎に割り当てたメモリーを大量に持ちます。こうしたメモリーの最大生存時間は、現在のコネクションの生存時間です。Apacheではメモリー・プールを使いますが、コネクションをステージに分解し、それぞれが専用のメモリー・プールを持ちます。ステージの最後では、メモリー・プール全体が一度に解放されます。

メモリー・プールによる管理では、割り当てるべきメモリーのプールを、各割り当てが規定します。各プールはそれぞれ別々の生存時間を持っています。Apacheでは、サーバーの生存時間だけ持続するプールや、コネクションの生存時間だけ持続するプール、リクエストの生存時間だけ持続するプールなどもあります。ですからもし私が、コネクションよりも長く持続する、データを何も生成しない一連のファンクションを持っているとしたら、それらがコネクションの最後で自動的に解放されることを知っているので、それらをすべて単純にコネクション・プールから割り当てます。さらに一部の実装では、クリーンアップ・ファンクションを登録することを許しています。これはメモリー・プールがクリアーされる直前に呼ばれ、メモリーがクリアーされる前に実行すべき、あらゆる追加的なタスクを行います（オブジェクト指向の人達のために言うと、デストラクターに似たようなものです）。

プログラムの中でプールを使うには、GNUのlibcにあるobstack実装か、またはApacheのApache Portable Runtimeを使います。GNUのobstacksは、GNUベースのLinuxディストリビューションにデフォルトで含まれているので便利です。Apache Portable Runtimeは、マルチプラットフォームのサーバー・ソフトウェアを書く上で必要となる、あらゆる要素を処理するためのユーティリティーを数多く持っているので便利です。GNU obstacksとApacheのメモリー・プールの実装について詳しくは、それぞれのドキュメンテーションへのリンクが参考文献にありますので、それを見てください。

次のコードは実際のものではなく仮説的なものですが、obstacksをどのように使うかを示すものです。

リスト11. obstacksのコード例
#include <obstack.h>
#include <stdlib.h>
/* Example code listing for using obstacks */
/* Used for obstack macros (xmalloc is
   a malloc function that exits if memory
   is exhausted */
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
/* Pools */
/* Only permanent allocations should go in this pool */
struct obstack *global_pool;
/* This pool is for per-connection data */
struct obstack *connection_pool;
/* This pool is for per-request data */
struct obstack *request_pool;
void allocation_failed()
{
	exit(1);
}
int main()
{
	/* Initialize Pools */
	global_pool = (struct obstack *)
		xmalloc (sizeof (struct obstack));
	obstack_init(global_pool);
	connection_pool = (struct obstack *)
		xmalloc (sizeof (struct obstack));
	obstack_init(connection_pool);
	request_pool = (struct obstack *)
		xmalloc (sizeof (struct obstack));
	obstack_init(request_pool);
	/* Set the error handling function */
	obstack_alloc_failed_handler = &allocation_failed;
	/* Server main loop */
	while(1)
	{
		wait_for_connection();
		/* We are in a connection */
		while(more_requests_available())
		{
			/* Handle request */
			handle_request();
			/* Free all of the memory allocated
			 * in the request pool
			 */
			obstack_free(request_pool, NULL);
		}
		/* We're finished with the connection, time
		 * to free that pool
		 */
		obstack_free(connection_pool, NULL);
	}
}
int handle_request()
{
	/* Be sure that all object allocations are allocated
	 * from the request pool
	 */
	int bytes_i_need = 400;
	void *data1 = obstack_alloc(request_pool, bytes_i_need);
	/* Do stuff to process the request */
	/* return */
	return 0;
}

基本的に、主な操作ステージの後は、そのステージに対するobstacksは解放されます。ただし、もしあるプロシージャーが、現在のステージの持続時間よりも長い期間メモリーを割り当てる必要がある場合には、例えばコネクションobstacksやグローバルobstacksなど、より長期間のobstacksも使うこともできることに注意してください。obstack_free() にNULLを渡すと、obstackの内容全部を解放するように言っていることになります。他の値もあるのですが、普通はあまり便利なものではありません。

メモリー・プール割り付けを使う利点は次のようなものです。

  • アプリケーションにとってメモリー管理が簡単
  • 一度に一つのプールが処理されるので、メモリー割り当てと割り付け解除がずっと高速。割り当てはO(1) 回行われ、プール解放が閉じられます（実際にはO(n) 回ですが、巨大な因数で割り算されるので、大部分の場合はO(1) になります）。
  • 普通のメモリーを使い切ってしまってもプログラムが回復できるように、エラー処理プールを事前に割り当てることができる
  • 非常に使いやすい標準実装がある

メモリー・プールの欠点は下記のようなものです。

  • メモリー・プールはステージで動作するプログラムでないと有効ではない。
  • メモリー・プールはサード・パーティーのライブラリーではうまく動作しない場合が多い。
  • プログラム構造が変更されるとメモリー・プールの変更が必要になる可能性があり、その結果、メモリー管理システムの再設計が必要になってしまう可能性がある。
  • どのプールから割り当てるべきかを覚えておく必要がある。しかもこれを誤ると、捉えるのが非常に困難になる。

上に戻る

ガーベジ・コレクション

ガーベジ・コレクションは完全自動で、もはや使われていないデータ・オブジェクトを検出し、削除します。ガーベジ・コレクションは通常、使用可能なメモリーが、規定したしきい値以下に下がった場合に実行します。一般的に、スタック・データやグローバル変数、レジスターなど、プログラムに使用可能であると分かっている「ベース」となるデータ・セットから始めます。次に、こうしたデータ・セットにリンクされた、あらゆるデータ片を追跡します。ガーベジ・コレクターが見つけるデータは全て「良い」データです。逆に見つけられないデータはガーベジであり、廃棄され、再利用されます。メモリーを効果的に管理するために各種のガーベジ・コレクターでは、データ構造内でのポインターのレイアウトについての情報を必要とします。ですから、適切に機能するためには言語自体の一部となっている必要があります。

ガーベジ・コレクターのタイプ

  • 複写: このタイプでは、メモリー・ストレージを2つの部分に分け、データはその一方でのみ生存することを許します。ガーベジ・コレクターは周期的に、「ベース」要素から始まるデータを、一方からもう一方の側にコピーし始めます。新たに占有されたメモリー部分が今度はアクティブになり、もう一方の側にあるものはすべてガーベジと見なされます。また、このコピーが行われる時には全てのポインターを更新して、各メモリー・アイテムの新しい位置を指すようにする必要があります。従って、この方式のガーベジ・コレクションを使うには、プログラミング言語の中にガーベジ・コレクターが統合されている必要があります。
  • マーク・アンド・スイープ: 各データ片はタグでマーク付けされます。時々、全てのタグが0にセットされ、ガーベジ・コレクターが「ベース」要素で始まるデータをウォークスルーします。メモリーに突き当たると、タグを1にします。最後になって、1のタグが付いていないものはすべてガーベジと見なされ、後の割り当てで再利用されるようになります。
  • インクリメンタル: インクリメンタル・ガーベジ・コレクターは、全てのデータ・オブジェクトを対象に実行することを要求しません。メモリー全部に対して実行しようとすると、全てが同時に行われることによる待ちが生じたり、現在の全データにアクセスすることによるキャッシュが問題になったり（全てをページングして読み込む必要がある）という問題が起きてきます。インクリメンタル・ガーベジ・コレクターでは、こうした問題を回避しています。
  • 保守的: 保守的ガーベジ・コレクターは、メモリー管理にあたってデータ構造について何も知る必要がありません。単純に全データ・バイトを見て、全てがポインターであり得ると想定するのです。ですから、あるバイト・シーケンスが、割り当てられたメモリー断片を指すポインターであり得る場合には、参照されているとしてマーク付けするのです。ところが、割り当てられたメモリーのアドレスであった値を整数フィールドが含んでいる場合には、参照されていないメモリーが収集されてしまうという問題を起こします。ただしそれが起きることは稀であり、起きたとしても浪費されるメモリーはわずかです。保守的ガーベジ・コレクターは、どんなプログラミング言語にも統合できるという利点があります。

Hans Boehmによる保守的ガーベジ・コレクターは無料な上、保守的かつインクリメンタルなので、ガーベジ・コレクターとして入手できるものの中では最も人気のあるものです。これを--enable-redirect-mallocでビルドすることによって、（システム自体のAPIの代わりにmalloc/freeを使うことで）システム・アロケーターの代わりとして手軽に使うこともできます。実際こうすることによって、先ほどガーベジ・コレクションを使用可能にするために単純アロケーターに対して使ったのと同じLD_PRELOADという細工を、システム上のどんなプログラムでも使えるようになります。もしプログラムがメモリー・リークを起こしている疑いがある時には、このガーベジ・コレクターを使って、プロセスのサイズを低下させることができます。Mozillaの初期には非常にメモリー・リークが激しかったので、多くの人はこの手法を使ったのです。このガーベジ・コレクターは、Windows® でもUNIXでも動作します。

ガーベジ・コレクションの利点をいくつか挙げると下記の通りです。

  • メモリーを二重に解放したり、オブジェクトの生存時間を気にしたりする必要がない
  • 一部のガーベジ・コレクターでは、通常の割り当てに使用したものと同じAPIが使える

欠点としては次のようなものです。

  • 大部分のコレクターでは、いつメモリーが解放されるのかに関して、何も言うことができない
  • 多くの場合、ガーベジ・コレクションは他のメモリー管理方式よりも遅い
  • ガーベジ・コレクションが引き起こすバグは、デバッグが難しい
  • 使われていないポインターをヌルに設定し忘れると、やはりメモリー・リークが起きる

上に戻る

まとめ

これはトレードオフの世界です。ちょっと数え上げるだけでも、パフォーマンスや使い易さ、実装のし易さ、そしてスレッド機能などのバランスを取りながら考慮する必要があります。皆さんのプロジェクトでの要求に合致するメモリー管理のパターンには、実に様々なものがあります。しかもそれぞれのパターンでも、実装の幅は広く、その実装にもまたそれぞれ利点と欠点があります。自分のプログラミング環境用のデフォルト手法を使っても多くの場合は問題がありませんが、他のオプションを知っておくと、プロジェクトに特別な要求がある場合に役に立つものです。下記の表は、この記事で取り上げたメモリー管理の戦略を比較したものです。

表1. メモリー割り当て戦略の比較
戦略割り付け速度割り付け解除速度キャッシュの局所性使い易さ一般性リアルタイムでの使用可能性SMPとスレッド親和性
カスタム・アロケーター実装による実装による実装による非常に困難無し実装による実装による
単純アロケーターメモリー使用が少なければ高速非常に高速劣る容易高い無し無し
GNUmalloc普通高速普通容易高い無し普通
Hoard普通普通普通容易高い無しあり
参照カウントN/AN/A優れている普通普通あり（malloc実装による）実装による
メモリー・プール普通非常に高速優れている普通普通あり（malloc実装による）実装による
ガーベジ・コレクション普通（コレクションが起きると遅い）普通劣る普通普通無しほとんど無い
インクリメンタル・ガーベジ・コレクション普通普通普通普通普通無しほとんど無い
インクリメンタル保守的ガーベジ・コレクション普通普通普通容易高い無しほとんど無い

参考文献

Web上の資料基本的なアロケーターメモリー・プールによるアロケーター
  • GNU Obstacks（GNU Libcの一部）はglibcベースのシステムには必ずあるので、最も広くインストールされているメモリー・プールによるアロケーターです。
  • Apacheでのメモリー・プールによるアロケーター（Apache Portable Runtimeにあります）は、メモリー・プールによるアロケーターとしては最も広く使われているものです。
  • Squidには独自のメモリー・プールによるアロケーターがあります。
  • NetBSDにも独自のメモリー・プールによるアロケーターがあります。
  • tallocはSambaの一部であるメモリー・プールによるアロケーターです。
スマート・ポインターとカスタム・アロケーター
  • The Loki C++ Libraryには、スマート・ポインターやカスタムの小型オブジェクト・アロケーターを含めて幾つか、C++用に実装された汎用のパターンがあります。
ガーベジ・コレクター最近のOSでの仮想メモリーに関する論文mallocに関する論文カスタム・アロケーターに関する論文ガーベジ・コレクションに関する論文Web上にある一般的な資料本
  • Michael DacontaによるC++ Pointers and Dynamic Memory Managementは、メモリー管理に関する様々な手法を網羅しています。
  • Frantisek FranekによるMemory as a Programming Concept in C and C++はメモリーの効果的な使い方を開発するための手法とツールを論じ、またコンピューター・プログラミングにおいて重要な役割を果たすメモリー関連のエラーに光を当てています。
  • Richard JonesとRafael LinsによるGarbage Collection: Algorithms for Automatic Dynamic Memory Managementは、最も一般的に使われているガーベジ・コレクションのアルゴリズムを説明しています。
  • Donald KnuthによるThe Art of Computer Programmingの第1巻、Fundamental AlgorithmsのSection 2.5「Dynamic Storage Allocation」では、基本的なアロケーターを実装する上での手法を幾つか説明しています。
  • Donald KnuthによるThe Art of Computer Programmingの第1巻、Fundamental AlgorithmsのSection 2.3.5「Lists and Garbage Collection」では、ガーベジ・コレクションのアルゴリズムを幾つかのリストに渡って説明しています。
  • Andrei AlexandrescuによるModern C++ DesignのChapter 4「Small Object Allocation」では、C++標準のアロケーターよりもずっと効率的な、高速、小型オブジェクトのアロケーターを説明しています。
  • Andrei AlexandrescuによるModern C++ DesignのChapter 7「Smart Pointers」では、C++でのスマート・ポインターの実装に関して説明しています。
  • JonathanによるProgramming from the Ground UpのChapter 8「Intermediate Memory Topics」には、この記事で使用した単純アロケーターのアセンブリー言語版があります。
developerWorksの記事
  • Self-manage data buffer memory（developerWorks, 2004年1月）は、自己管理で理論的なメモリー管理用データ・バッファーを疑似的にC実装する概要を説明しています。
  • A framework for the user defined malloc replacement feature（developerWorks, 2002年2月）は、メモリー・サブシステムを自分で設計したものと入れ換える方法として、AIXに備わっている機能を利用する方法を説明しています。
  • Linuxのデバッグ手法をマスターする（developerWorks, 2002年8月）は、セグメント化失敗、メモリー・オーバーラン、メモリー・リーク、ハングアップ、という4つのシナリオにおけるデバッグ方法を説明しています。
  • Javaプログラムでのメモリー・リークの処理（developerWorks, 2001年2月）では、何がJavaのメモリー・リークを引き起こすのか、それが問題になるのはどういう場合かについて学びます。
  • developerWorksのLinuxゾーンには、Linux開発者用の資料が他にも豊富に用意されています。
  • Linux上で実行する、IBMミドルウェア製品の無料試用版をダウンロードしてください。developerWorksのSpeed-start your Linux appセクションからWebSphere® Studio Application DeveloperやWebSphere Application Server、DB2® Universal Database、Tivoli® Access ManagerそしてTivoli Directory Serverが入手できます。また、ハウ・ツー記事や技術サポートもご覧ください。
  • developerWorks blogsに参加して、developerWorksコミュニティーに加わってください。
  • Developer BookstoreのLinuxセクションではLinux関係の技術書が値引きして購入できますので、ご利用下さい。

コメント

閉じる [x]

developerWorks: サイン･イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか？


パスワードをお忘れですか？
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む。

 

お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報（名前、国/地域や会社名）は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

閉じる [x]

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む。

 

送信されたすべての情報は安全です。

上に戻る

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=226859
ArticleTitle=メモリー管理の内側
publish-date=11162004