2006年02月05日

参照カウント

参照カウント(さんしょうカウント)は、ガベージコレクタの動作方法の一つ。

* すべてのオブジェクト(メモリ上におかれているデータの単位)に対して、参照カウントと呼ばれる整数値を付加しておく。これは、このオブジェクトへのポインタがシステム全体にいくつ存在しているかを数えるものである

* オブジェクトへの参照が変化するたびにこの値は随時書き換わる。
* 参照カウントが0になったものについては破棄が許される。

この方法は処理が高速であり、オブジェクトを多数生成し、すぐに参照を切るような処理においても迅速に破棄が起きる。ただ、不要になったオブジェクト同士が循環参照してる場合、参照カウントが0にならないために破棄がおきないという問題がある。

また、参照カウントが頻繁に書き変わる場合には書き換え負荷そのものが問題になる場合もある。さらに、単純な実装の場合、大量のオブジェクトが一斉に解放になる場合があり、 CPUの空き時間を利用してガベージコレクションを行う方法と比べると、メモリの解放で処理が遅くなってしまう場合もある。

class A {
public B b;
}
class B {
public A a;
}
public class Test{
public static void main(String[]arg) {
A a=new A(); // *1*
a.b=new B();
b.a=a;
a=null;
// *1*で作成したAのオブジェクト は到達不可能にもかかわらず、参照カウントは1
}
}

例2

ウィキペディアの「孤立した記事」は、参照カウントが0のものを表示しているだけなので、孤立した記事だけから参照されている記事は孤立した記事と見なされていない。

上で述べた問題を回避する方法としてマーク・アンド・スイープがある。
[編集]

実用例

* マイクロソフトのComponent Object ModelにおけるCOMオブジェクトは参照カウント方式で管理される。
* プログラミング言語Pythonのガベージコレクタは主に参照カウント方式を用いている。
* Boost C++ Library の smart_ptr
posted by シンビアン at 08:42| Comment(0) | TrackBack(0) | Symbian OS C++ 実践開発技法 | このブログの読者になる | 更新情報をチェックする

参照カウンタ

概要

アクセス不可能オブジェクトを決定する方法の1つに、参照カウンタ (reference counting) を使う方法があります。これは非常にシンプルな GC で、実装が容易であるが、後で述べるように致命的な欠点があるため、通常は他の GC 手法と併用する必要がある。

【注意】参照カウント法を GC 手法と見なさない人々もいる。

実装

1. GC 管理されるすべてのオブジェクトに、参照カウンタを付随させます。
2. オブジェクトへの参照が作成されると、参照カウンタを 1 つ増やします。
3. オブジェクトへの参照が削除されると、参照カウンタを 1 つ減らします。
4. 参照カウンタを減らしたときに参照カウンタが 0 になれば、 オブジェクトを回収する。

サンプル

次のような擬似 Java コードを考えてみよう。

SomeObject obj1, obj2, obj3;

// ここで作成されるオブジェクトは、作成と同時に変数にバインドされるので、
// 参照カウントが 1 になる。
obj1 = new SomeObject("A"); // オブジェクト A を作成
obj2 = new SomeObject("B"); // オブジェクト B を作成

// オブジェクト A は obj3 変数により参照されるので、参照カウントが増えて 2 になる。
obj3 = obj1;

// オブジェクト A は obj2 により参照されるので、参照カウントが 3 になる。
// それと同時にオブジェクト B の参照は減らされて 0 になり、
// オブジェクト B は回収されることになる。
obj2 = obj3;

利点
GC 実行時間が極めて短い

オブジェクトの回収はオブジェクト毎に行われるため、GC の実行時間はきわめて短い。

そのため、リアルタイム用途に適しています。
欠点
参照カウンタの増減によるオーバーヘッド

オブジェクトの大半は寿命が非常に短いという一般法則があります。参照カウント法では、すぐに不要になるオブジェクトに対しても参照カウントを増減させるというオーバーヘッドが伴います。

このようなオーバーヘッドはコンパイラによる最適化によって大きく軽減できる可能性があります。

[執筆注: もう少し精密な議論ができるはず。]
オブジェクト毎に参照カウンタ用のストレージが必要

十分な大きさの参照カウントを保持しようとすると、そのためのストレージのオーバーヘッドが大きくなる (通常の 32 bit システムでは、参照カウントを 32 bit にとることが多いであろう。) また、参照カウンタようのストレージを小さく取ると、次に述べるオーバーフローの問題が出てくる。
参照カウンタのオーバーフローの問題

たとえば、参照カウント用に 8 bit のストレージを使うとすると、参照カウントは 255 までしか使えない。参照カウントのオーバーフローを許すと、実際には 256 の参照があるにも関わらずオブジェクトが回収されてしまうことが起こりかねない。

このような問題を避けるため、参照カウントの最大値に達したオブジェクトに対しては、もはやカウントの増加も減少も行わないように、参照カウントのロックが行われる。これにより、参照されているオブジェクトが回収されてしまうという問題を回避することはできるが、ロックされたオブジェクトは永遠に回収されないという問題が起きる。

ロックされたオブジェクトを回収するためには、参照カウント法を別の GC 手法と組み合わせることが多い。
循環参照を行うオブジェクトを回収できない

2 つのオブジェクトが互いに相互参照を行う場合、両オブジェクトが不要になっても参照カウントが 0 にならないため、決して回収されない。

注意すべきは、相互参照をしている当該のオブジェクトだけでなく、そのオブジェクトから直接・間接に参照されているオブジェクトも、決して回収されないことである。

この問題は参照カウント GC だけでは解決することは不可能であり、別の GC 手法を併用することで回収を行う。
サンプル

次の Java コードでは、Mike と Cathy は相互参照をしており、両オブジェクトが不要になった後でも参照カウントは 0 にならない。

obj1 = new Person( "Mike" );
obj2 = new Person( "Cathy" );
obj1.wife = obj1;
obj2.husband = obj2;
obj1 = null;
obj2 = null;
posted by シンビアン at 08:40| Comment(0) | TrackBack(0) | Symbian OS C++ 実践開発技法 | このブログの読者になる | 更新情報をチェックする

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。