JP7754595B2 - ガベージ・コレクションのための３色ビットマップ・アレイ - Google Patents

Description

本開示は、コンピュータ・システムにおけるガベージ・コレクションに関し、より具体的には、ガベージ・コレクションついての到達不可能なリソースをマーク付けすることに関する。

幾つかのコンピュータ・システムは、プログラムが機能を完全なものにするためにそのリソースを必要とするときに、リソースをメモリにロードする。これらのリソースは、プログラム内の（例えば、そのプログラムによって使用される別のリソース内の）リソース及びそれらの位置を識別するポインタによって、識別することができる。

幾つかのコンピュータ・システムは時折、もはやコンピュータ・システムによって必要とされていないリソース（例えば、初めはそれらを必要としたプログラムによってもはや使用されていない、メモリにロードされているリソース）によって使用されているメモリを解放するために、ガベージ・コレクションを行う。この理由のために、ガベージ・コレクションは、それらの不要なリソースを識別する方法を含むことが多い。幾つかの方法は、メモリ内のいずれかのリソースが、現在使用されているプログラム又は他のリソースによってポイントされていないかどうかを判断するために、リソースの間のポインタを追跡することを含む。

本開示の幾つかの実施形態は、第１のメモリ・アドレスにおいて第１のオブジェクトを識別することを含む方法として例示することができる。この方法はさらに、ビットマップ内の第１のインデックス位置を計算することを含むことができる。第１のインデックス位置は、第１のメモリ・アドレスに対応することができる。本方法はさらに、第１のインデックス位置に第１のビットを設定することを含むことができる。本方法はさらに、第１のオブジェクト内で、チャイルド・オブジェクトへのポインタを検出することを含むことができる。本方法はさらに、ポインタを用いて、チャイルド・オブジェクトの第２のメモリ・アドレスを識別することを含むことができる。本方法はさらに、ビットマップ内の第２のインデックス位置を計算することを含むことができる。第２のインデックス位置は、第２のメモリ・アドレスに対応することができる。本方法はさらに、第２のインデックス位置に第２のビットを設定することを含むことができる。本方法はさらに、第３のインデックス位置に第３のビットを設定することを含むことができる。第３のインデックス位置は、第１のインデックス位置に隣接することができる。

本開示の幾つかの実施形態はさらに、プロセッサ及びメモリを備えるシステムとして例示することができる。メモリは、プロセッサと通信することができ、プロセッサによって実行されるときにプロセッサに上記の方法を行わせるように構成されたプログラム命令を含むことができる。

本開示の幾つかの実施形態はさらに、プログラム可読ストレージ媒体を含むコンピュータ・プログラム製品として例示することができる。プログラム可読ストレージ媒体は、そこに具体化されたコンピュータ命令を有することができる。プログラム命令は、コンピュータによって実行可能であり、上記の方法をコンピュータに行わせることができる。

上記の概要は、本開示の各々の例証的な実施形態又はあらゆる実施を説明することを意図したものではない。

本出願に含まれる図面は本明細書に組み込まれ、その部分を形成する。それらは、本開示の実施形態を例示し、その説明とともに本開示の原理を説明するために役立つ。図面は、ある特定の実施形態を例示するだけであり、本開示を限定するものではない。

本開示の実施形態による、ビットマップを用いて３色マーク付けを行う方法を示す。 本開示の実施形態にしたがって３色マーク付けを行うことができる、ビットマップによるメモリ・システムの初めの抽象化を示す。 本開示の実施形態にしたがって３色マーク付けを行うことができる、ビットマップによるメモリ・システムの第２の抽象化を示す。 本開示の実施形態にしたがって３色マーク付けを行うことができる、ビットマップによるメモリ・システムの第３の抽象化を示す。 本開示の実施形態による、到達可能なオブジェクトについてビットマップを走査する方法を示す。 実施形態によって使用することができるコンピュータ・システムの代表的な主要なコンポーネントを示す。

本発明は、さまざまな修正及び代替的形態の余地があるが、図面内にはそれらの特定のものが例として示されており、詳細に説明されることになる。しかし、その意図は、本発明を説明される特定の実施形態に限定することではない、ことを理解されたい。むしろ、本発明は、本発明の趣旨及び範囲に入る全ての修正形、等価形、及び代替形を包含するものである。

本開示の態様は、コンピュータ・システムにおけるガベージ・コレクションに関し、より具体的な態様は、ガベージ・コレクションについて到達不可能なリソースをマーク付けすることに関する。本開示は、必ずしもそのような応用に限定されないが、本開示の様々な態様は、この文脈を用いた様々な例の議論を通して認識することができる。

典型的なコンピュータ・システムは、リソース（本明細書では「オブジェクト」とも呼ばれる）が、それらのコンピュータ・システム上で開発中に又は実時間での使用中に実行されるプロセスによって必要とされるときに、それらのリソースをメモリに格納する。リソースを要求したプログラムが変化したり、プログラムの用途が変化したりすると、そのプログラムの動作に以前には必要であったリソースが不要となることがある。不必要にシステム・メモリを使用しているリソースの除去によって、システムをより速く且つより滑らかに動作させることができる。このために、多くのコンピュータ・システムは、コンピュータ・システムによってもはや必要とされないリソースをメモリから削除するように設計されたガベージ・コレクションの方式を組み入れている。しかし、ガベージ・コレクションの方法が、効果的にそれらリソースを削除するためには、もはや必要のないリソースを識別する必要がある。

幾つかのコンピュータ・システムにおいて、不要なリソースは、メモリ内のいずれかの他のリソースがそれらの不要なリソースを参照するかどうかに基づいて、識別することができる。例えば、多くのコンピュータ・システムは、「ポインタ」の使用によりリソースを追跡する。「ポインタ」は、本明細書で用いられる場合、別のリソースを識別してその位置を与える、リソースの参照を指す。ポインタは、コンピュータ・システムが第１のリソースの利用中に又は利用後に使用する必要があり得る１つ又は複数のリソースを識別するために、リソースによって使用される。メモリ内のリソースが、それ自体がルート・リソース（例えば、プログラム又はプロセスの実行時に初めにロードされるオブジェクト）にトレース・バックされ得るリソース内のポインタによって識別されるとき、そのオブジェクトは「到達可能」と言われる。このことが当てはまらないいずれのオブジェクトも「到達不可能」と言われる。

メモリ内の到達不可能なオブジェクトは、コンピュータ・システムに何の利益を与えることもなくメモリ空間を占有する。それらは到達不可能なために、どのプログラムもそのオブジェクトを使用することができない。従って、到達不可能なリソースを識別し、メモリから除去することが有益である。幾つかのコンピュータ・システムは、到達不可能なオブジェクトに割り当てられたメモリを解放するために、ガベージ・コレクションを使用する。ガベージ・コレクションは、典型的には、到達可能なオブジェクトのリストを決定し、次いでリストされないオブジェクトを削除するために、オグジェクトの間のポインタの分析を含む。

例えば、幾つかのガベージ・コレクションの方法は、システム又はプロセスのルート・オブジェクトとみなされるものを識別することによって開始する。ルート・オブジェクトは、本明細書で使用される場合、典型的には、特定のプロセス又はプログラム内の、システムによってロードされた第１のオブジェクトの形態をとる。ルート・オブジェクトは、典型的には、コンピュータ・システムによるルート・オブジェクトへの迅速且つ確実なアクセスをもたらす、メモリの構造化されたセクションに格納される。それらは、例えば、整理されたメモリのメモリ・スタック又は他のセクションに存在することがある。迅速且つ確実なアクセスと、ルート・オブジェクトがシステムによってプロセスのためにロードされたベース・オブジェクトであるということとから、定義上、ルート・オブジェクトは到達可能である。

ルート・オブジェクトは、多くの場合、ルート・オブジェクトがロードされた後でプロセスを行うために必要な他のオブジェクトへのポインタを含む。例えば、プロセスのためのリソース・オブジェクトは、そのプロセスを実行するために、順番に使用されることが必要なリンクされたリスト項目を含むことができる。リンクされたリストにおいて、各々のストレージ・オブジェクトは、リスト内の次のオブジェクトの位置へのポインタを含む。従って、リストのルートにおいて、ルート・オブジェクトは、リンクされたリスト内の次のオジェクトへのポインタを含むことになる。

本明細書で使用される場合、第２のオブジェクトへのポインタを含む第１のオブジェクト（例えば、ルート・オブジェクト）は、本明細書においては、その第２のオブジェクトに関する「ペアレント」又は「ペアレント・オブジェクト」と呼ばれる。一方、第２のオブジェクトは、そのペアレントの「チャイルド」又は「チャイルド・オブジェクト」と呼ばれる。第２のオブジェクトがさらに第３のオブジェクトへのポインタを含む場合、第２のオブジェクトはまた、第３のオブジェクトのペアレントと呼ばれ、第３のオブジェクトは、第２のオブジェクトのチャイルドと呼ばれる。さらに、第１のオブジェクトは、第３のオブジェクトの「グランドペアレント」又は「グランドペアレント・オブジェクト」と呼ばれ、一方、第３のオブジェクトは、第１のオブジェクトの「グランドチャイルド」又は「グランドチャイルド・オブジェクト」と呼ばれる。あるオブジェクトのチルドレン、グランドチルドレンなどを総称して、本明細書では、そのオブジェクトの「子孫」又は「子孫オブジェクト」と呼ぶことができる。

多くのメモリ・システムにおいて、ルート・オブジェクトは、メモリの極めて整理されたセクション（例えば、スタック・メモリ）に格納されるが、子孫オブジェクトは、多くの場合、メモリのあまり整理されていない、あまり管理されていない、自由な浮動セクション（例えば、ヒープ・メモリ）に格納される。整理されていないメモリは通常、メモリの整理されたセクションより大きく且つよりフレキシブルであるが、その中でオブジェクトの位置を特定することは、ディレクションなしにはより難しい。このため、オブジェクトへのポインタは、通常、メモリのこの未整理のセクション内のそのオブジェクトのアドレスを与えるか又は計算を可能にする情報を含む。換言すれば、ペアレント・オブジェクト内の、チャイルド・オブジェクトへのポインタを分析することによって、そのチャイルド・オブジェクトのメモリ位置を決定することができる。

次いで、ルート・オブジェクトのどの子孫オブジェクトもまた、ルート・オブジェクトをその子孫に結びつける一連のポインタを通して到達可能ということになる。同様に、ルート・オブジェクトの子孫ではないどのオブジェクトも到達可能ではない。従って、多くのガベージ・コレクション・システムは、ルート・オブジェクトの子孫オブジェクトを識別することによって、メモリから除去すべきオブジェクトを識別する。例えば、典型的なガベージ・コレクション・システムは、ルート・オブジェクトを識別し（例えば、メモリ・スタック内で）それを「到達可能」とマーク付けすることによって開始する。次いで、システムは、他のオブジェクト（例えば、ルート・オブジェクトのチルドレン）へのポインタについてルート・オブジェクトを分析する。チャイルド・オブジェクトへのポインタを発見すると、ガベージ・コレクションを行う典型的なシステムは、次に、そのチャイルド・オブジェクトのメモリ内での位置を識別することができ、そのメモリ位置にあるオブジェクトがシステムのメモリ管理システムにおいて「到達可能」であると記録する。ルート・オブジェクトのチルドレンのポインタを分析することにより、同様のプロセスを、ルート・オブジェクトのグランドチルドレンなどについても行うことができる。ルート・オブジェクトの子孫の全てのポインタが分析されると（従って、全ての到達可能オブジェクトが識別されると）、あらゆる残りの（即ち、マーク付けされない、子孫でない）オブジェクトは、到達不可能とみなされ、なぜなら、それらの到達不可能なオブジェクトにポイントする、ルート・オブジェクトに由来するポインタが存在しないからである。

多くの現代のシステムにおいて、複数のプロセッサ・スレッドが、メモリ管理システムにおいてオブジェクトを同時に「到達可能」としてマーク付けするように働くことができる。しかし、このことは、時々、幾つかのマーク付け技術を用いて他のスレッドによって行われた以前のマーク付け作業をスレッドが重複して行うことにつながる可能性がある。例えば、スレッドが、それ自体が到達可能とマーク付けされたペアレント・オブジェクトの位置を特定する場合、そのスレッドは、ペアレント・オブジェクトがポイントするチャイルド・オブジェクトが、それら自体の位置が特定されてマーク付けされているかどうか判断する方法を有しない可能性がある。このため、これらのマーク付け技術は、ナイーブと呼ばれることがある。ナイーブなマーク付け技術においては、スレッドは、ペアレント・オブジェクトの全てのポインタを分析して、それらのチルドレンが既にマーク付けされている場合でも、そのペアレントのチルドレンの位置を特定するために時間を費やす可能性がある。それは、これらのマーク付けシステムにおいては、ペアレントのチャイルドがマーク付けされているかどうかを判断する唯一の方法が、メモリ内でそのチャイルドの位置を特定することだからである。そのチャイルド・オブジェクトがマーク付けされていない場合には、そのペアレントのチルドレンをマーク付けするためにスレッドを効率的に使用することができるはずである。しかし、そのチャイルド・オブジェクトが別のスレッドによって既にマーク付けされている場合、それらが既にマーク付けされたことを見つけるためだけにそのチャイルド・オブジェクトの位置を特定する時間を費やすことは、相当な時間を浪費する可能性がある。特に、ペアレント・オブジェクトが多くのチルドレンを有する場合、このことは著しい非効率を招く可能性がある。

例えば、第１のスレッドがメモリを走査することができ、ペアレント・オブジェクトへの参照を見出し、そのペアレント・オブジェクトのメモリ・アドレスの位置を特定し、それを「到達可能」とマーク付けすることができる。第１のスレッドは次に、そのペアレント・オブジェクト内のポインタを走査し、そのチルドレンのメモリ・アドレスの位置を特定し、それらをまた「到達可能」とマーク付けすることを開始するができる。第１のスレッドが「到達可能」とマーク付けした後に、さらに第２のスレッドがメモリを走査し、ペアレント・オブジェクトへの参照を見つけた場合、ナイーブなマーク付け技術を使用する場合にはそのペアレントのチルドレンが既にマーク付けされているかどうか判断することができないことになる。このことは、第２のスレッドに選択をもたらし、即ち、ペアレントのチルドレンの位置を特定して、別のスレッドが既に行った作業を重複するリスクをもたらすか、チルドレンをスキップしてマーク付けされないままにしておくリスクをもたらす可能性がある。

ナイーブなマーク付け技術に伴う問題に対処するために、幾つかのシステムは、ガベージ・コレクションのために到達可能オブジェクトを識別するときに、３色マーク付け技術を使用する。３色マーク付けにおいて、オブジェクトは、３つの状態、（１）マーク付けされていない（業界ではしばしば「白」と呼ばれる）、（２）マーク付けされており、マーク付けされていないチルドレンを伴う（業界ではしばしば「グレイ」と呼ばれる）、及び（３）マーク付けされており、マーク付けされていないチルドレンを伴わない（業界ではしばしば「黒」と呼ばれる）に分類することができる。３色マーク付けにおいて、あるスレッドが「白」オブジェクト（即ち、マーク付けされていないオブジェクト）への参照の位置を特定したとき、そのスレッドは、オブジェクトを「グレイ」とマーク付けし、次いで、そのオブジェクトがマーク付けされていないチルドレンにポイントするかどうかを判断する。

グレイ・オブジェクトが、マーク付けされていないチルドレンにポイントしない場合、それは「黒」とマーク付けすることができる。グレイ・オブジェクトが、マーク付けされていないチルドレンにポイントする場合、スレッドは、メモリ内でそれらの位置を特定し、それらを同様にマーク付けする（典型的にはグレイとして）。幾つかの実施において、ペアレントは、全てのチルドレンがグレイとしてマーク付けされたときにのみ、黒に切り替えることができる。他の実装において、ペアレントは、プロセス中に早期に（例えば、スレッドがそのチルドレンをマーク付けし始めるとすぐに）黒に切り替えることができる。

３色マーク付け技術においては、スレッドが、黒とマーク付けされているオブジェクトへの参照を見つけたときに、そのオブジェクト及びそのオブジェクトのすべてのチルドレン（もしあれば）がいずれもマーク付けされていると結論づけることができ、したがって、スレッドは、他のオブジェクトへの参照のために、メモリの走査に移って継続することができる。一方、スレッドは、グレイ・オブジェクトを見つけたときに、そのグレイ・オブジェクトがマーク付けされていないチルドレンへのポインタを含むと結論づけることができ、それらのチルドレンの位置を特定してマーク付けすることを開始することができる。

例えば、第１のスレッドは、メモリを走査し、あるペアレント・オブジェクトへの参照をみつけ、そのペアレント・オブジェクトのメモリ・アドレスの位置を特定し、それを「グレイ」とマーク付けすることができる。次に、第１のスレッドは、そのペアレント・オブジェクト内のポインタを走査し、チルドレンのメモリ・アドレスの位置を特定し、チルドレンを同様にグレイとマーク付けすることを開始することができる。全てのチルドレンがマーク付けされると、第１のスレッドは、ペアレントを「黒」に変更することができることになる。

この例において、第２のスレッドが、第１のスレッドがペアレントを黒とマーク付けする前に、そのペアレントへの参照の位置を特定する場合、その第２のスレッドは、ペアレントが「グレイ」であるために、ペアレントがマーク付けされていないチルドレンへのポインタを有することを知ることになる。第２のスレッドは次に、第１のスレッドがそれらのチルドレンの位置を特定してマーク付けすることを助けることができる。一方、第１のスレッドがペアレントを黒とマーク付けした後に、第２のスレッドがペアレントへの参照の位置を特定した場合、第２のスレッドは、ペアレントがマーク付けされているばかりでなく、そのペアレントのチルドレンの位置も同様に特定されてマーク付けされていることを知ることになる。この状況で、第２のスレッドは、ペアレントをマーク付けしたり、ポインタについてペアレントを走査したり、ポイント先のアドレスにあるチャイルド・オブジェクトを探してそれらがマーク付けされていることを確認したりするために、時間を費やすべきではないと結論づけることになる。３色マーク付けがなければ、第２のスレッドは、確信を持ってこれらの判断を下すことができないであろう。

しかし、第１のスレッドがペアレントのチルドレンの１つを「グレイ」とマーク付けした後に、第２のスレッドが、メモリ走査中にそのチャイルドに遭遇した場合、第２のスレッドは、このチャイルドは別のスレッドによってマーク付けされているが、まだマーク付けされていない別のチルドレン（即ち、初めのペアレントのグランドチルドレン）へのポインタを有すると結論づける可能性がある。従って、第２のスレッドは次に、初めのチャイルド内のポインタを分析し、初めのペアレントのグランドチルドレンの位置を特定してマーク付けすることを開始することができることになる。重要なことに、このことは、第１のスレッドが、初めのペアレントの他のチルドレンの位置を特定して識別するためにまだ作業しているのと同時に起こる可能性がある。このように、３色マーク付けを使用することにより、第１及び第２のスレッドは、互いの努力が重複する危険性なく、同じファミリー・ツリーについて効率的に作業することができる。

残念なことに、３色マーク付け技術は、全てのメモリ・システムにおいて容易に実装できるものではない。例えば、幾つかのシステムは、ビットマップと呼ばれるメモリ構造を用いて、管理されていないメモリ・スペース（例えば、ヒープ・スペース）の占有を追跡する。ビットマップは典型的には、各々がメモリの対応する領域を表すインデックス位置の１次元アレイ（即ち、ヒープ・スペース内の連続的な一連のバイト）の形態をとる。これらのメモリの対応する領域は、メモリ内の特定の位置（場合により、「メモリ位置」又は「メモリ・アドレス」と呼ばれる）で開始し、インデックス位置に対応するこれらの特定の位置は、インデックス位置に基づいて決定することができる（例えば、「４」のインデックス位置に２００を掛けて、対応する「８００」のメモリ位置を計算し、２５のインデックス位置に２００を掛けて、対応する「５,０００」のメモリ位置を計算する）。ビットマップ内の各々のインデックス位置が対応する領域のサイズは、メモリ・システムの設定に基づいてカスタマイズすることができる。例えば、幾つかのシステムにおいては、各々のインデックス位置は、整理されていないメモリ空間内の２バイト領域を指すことができ、他のシステムにおいては、各々のインデックスは、メモリ内の２０バイト領域に対応することができる。

典型的なビットマップにおいて、各々のインデックス位置は単一ビットからなり、これは、オンにする（例えば、「１」に設定する）又はオフにする（例えば、「０」に設定する）ことができる。従って、ビットマップでは、単一ビットは、メモリ内の遥かに大きな領域に関する情報を伝えることができる。例えば、各々のインデックス位置が、メモリ内の８バイト領域に対応する場合、ビットマップの各々のビットは、実際には、メモリ内の約６４バイトの情報を伝える。これらのビットをオン及びオフにすることは、対応する領域に関する異なる情報（例えば、その領域が占有されているかどうか、その領域が分析されているかどうか、その領域が頻繁に使用されるデータを含むかどうか、又は、その領域が到達可能なオブジェクトを保持するかどうか）を追跡するために使用することができる。この情報は、メモリの相対的に大きな部分を単一ビットのサイズで表現することできるので、それらの小さいストレージ要件から、ビットマップが好まれることが多い。

ビットマップを使用する典型的なシステムが、ガベージ・コレクションを行うとき、あるメモリ位置で始まるオブジェクトは、そのメモリ位置に対応するビットマップ内のインデックス位置を見つけて、そのインデックス位置におけるビットを「０」から「１」へ切り替えることによって、マーク付けされる。しかし、各々のインデックス位置は、０又は１のいずれかにすることができるだけなので、対応するオブジェクトを、３つの状態（例えば、「白」、「グレイ」、又は「黒」）のうちの１つにマーク付けすることは困難である。従って、あるスレッドが、ビットマップ内の「１」とマーク付けされたメモリの領域への参照を調べるとき、そのスレッドは、メモリの対応する位置に、位置を特定された到達可能なオブジェクトが存在すると結論づけることはできるが、そのオブジェクトがマーク付けされていない何れかのチルドレンを含むかどうか結論づけることができない可能性がある。換言すれば、メモリ情報を追跡するためにビットマップを使用する幾つかのシステムにおいて、３色マーク付け技術は、ナイーブなマーク付け技術と同じ不利益を被る。

本開示の幾つかの実施形態は、ナイーブなマーク付けシステムの不利益を避ける方法で、ビットマップを使用するシステムにおける３色マーク付けを実施する。例えば、幾つかのシステムにおいては、整理されていないメモリは、ヒープ・メモリを形成する。前述のように、ビットマップ内の各々のビット（換言すれば、各々のインデックス位置）は、メモリの同じサイズの領域に対応する。各々のビットが対応するメモリの領域のサイズは、本明細書ではアライメント・サイズと呼ばれる。例えば、ビットマップ内の各々のビットが４バイトに対応する場合、ビットマップのアライメント・サイズは４バイトとなる。これらのシステムにおいて、アライメント・サイズ（例えば、４バイト）より大きいオブジェクトがメモリに加えられる場合、そのオブジェクトが格納される領域は、ビットマップ内の１ビットより多くを要することになる。換言すれば、８バイトのオブジェクトが、４バイトのアライメント・サイズを有するシステム内のヒープ・スペースの領域に加えられる場合、その領域は、そのビットマップの２ビットに対応することになる。

本開示の幾つかの実施形態は、ガベージ・コレクションのためにオブジェクトをマーク付けするときに、オブジェクトのサイズとアライメント・サイズとを比較することによって、３色マーク付けを実施する。例えば、幾つかの実施形態は、アライメント・サイズより大きいオブジェクトを識別することができる。これらのオブジェクトは、ビットマップ内の少なくとも２つのインデックス位置に対応するメモリ領域を占有するので、少なくとも２つのビットマップ・ビットを使用して、それらのオブジェクトが「白」とみなされるか、又は「ブラック」若しくは「グレイ」とマーク付けされているかを識別することができる。

例えば、幾つかの実施形態において、オブジェクトが、ビットマップの２つのインデックス位置に対応するヒープ・スペース内の領域を占有した場合、第１のインデックス位置を使用して、その領域内のオブジェクトがマーク付けされたかどうかを示すことができる。換言すれば、第１のビットは、オブジェクトが白であることを示すようにオフにする（即ち、「０」に設定する）ことができ、オブジェクトが黒又はグレイであることを示すようにオンにする（即ち、「１」に設定する）ことができる。この例において、第２のインデックス位置は、オブジェクトがグレイであることを示すためにオフにし、オブジェクトが黒であることを示すためにオンにすることができる。従って、これらの実施形態において、「００」と読まれるビットマップ内のビットのセットが白のオブジェクト（例えば、マーク付けされていないオブジェクト）を示し、「１０」と読まれるビットマップ内のビットのセットがグレイのオブジェクト（例えば、マーク付けされているが、マーク付けされていないチルドレンへのポインタを含むオブジェクト）を示し、「１１」と読まれるビットのセットが黒のオブジェクト（例えば、マーク付けされており、ポインタを含まないか又はマーク付けされたチルドレンへのポインタを含むオブジェクト）を示すことになる。従って、アライメント・サイズより大きいオブジェクトを識別することにより、本開示の実施形態は、ビットマップを使用するときでも、３色マーク付けが可能なヒープ・スペース内のオブジェクトを効率的に識別する。

アライメント・サイズより大きなオブジェクトを個々に識別することは、３色マーク付けが可能なオブジェクトを識別するための有用な方法であり得るが、本開示の実施形態を用いる３色マーク付けは、ヒープ・スペース内の全てのオブジェクトがアライメント・サイズより大きい場合には、特に有利である。これらの場合において、３色マーク付けは、ヒープ・スペースを通して用いることができ、ナイーブなマーク付け技術の非効率性を排除する。

従って、本開示の幾つかの実施形態は、ヒープ・スペースについての最小のオブジェクト・サイズがアライメント・サイズより大きいかどうか識別することを試みることができる。「最小のオブジェクト・サイズ」を有するヒープ・スペースにおいて、ヒープ・スペースは、メモリ内の連続するバイトの同じサイズのブロックに分割される。これらの同じサイズのブロックは、本明細書では、最小オブジェクト・サイズと呼ばれることがある。例えば、メモリ・システムは、１６バイトの最小オブジェクト・サイズを有することができる。この例において、メモリは、１６バイトの同じサイズの領域に分割されることになり、どの１６バイト領域も１つより多くのオブジェクトを含まないことになる。従って、実際にサイズが７バイトしかないオブジェクトがメモリ内に格納される場合、そのオブジェクトには、１つの１６バイト領域全体を割り当てることができる。一方、１７バイトのオブジェクトがメモリに加えられる場合、これは、２つの連続する１６バイト領域に割り当てることができる。このために、メモリ内の「オブジェクトのサイズ」は、メモリ内でそのオブジェクトに割り当てられる全体の領域のサイズを指す場合があると理解することができる。

メモリ・システムにおいて最小オブジェクト・サイズを使用すると、ビットマップ内でメモリ位置をインデックス位置へマッピングする効率を向上させることができる。しかし、アライメント・サイズより大きな最小オブジェクト・サイズを識別することにより、最小オブジェクト・サイズを使用することで、本開示の実施形態を通して、３色マーク付けの効率をさらに向上させることができる。例えば、ヒープ・スペースについての最小オブジェクト・サイズを、８バイトとすることができる。６バイトのオブジェクトがヒープ・スペースに加えられる場合、そのオブジェクトには、依然として最小オブジェクト・サイズ（８バイト）が割り当てられることになる。一方、１０バイトのオブジェクトがヒープ・スペースに加えられる場合、そのオブジェクトには、最小オブジェクト・サイズの２つの領域（１６バイト）が割り当てられることになる。

最小オブジェクト・サイズをアライメント・サイズと比較することにより、本開示の実施形態は、メモリ内の全てのオブジェクトに対して、少なくとも２ビットが使用可能かどうか判断することができる。例えば、最小オブジェクト・サイズが、アライメント・サイズの少なくとも２倍である場合、メモリ内の各々のオブジェクトは、ビットマップ内の少なくとも２ビットに対応することになる。これらの状況においては、２つのビットマップ・ビットを用いる３色マーク付けは、メモリ内のあらゆるオブジェクトについて行うことができる。

図１は、本開示の実施形態による、ビットマップを用いて３色マーク付けを行う方法１００を示す。方法１００は、例えば、コンピュータ・システム４０１などのより大きなコンピュータ・システムのストレージ・コントローラ又は中央処理ユニットの１つ又は複数のスレッドによって、実行することができる。方法１００は、整理されたメモリ・セクション（例えば、メモリ・スタック）、整理されていないメモリ・セクション（例えば、ヒープ・スペース）、及びビットマップを有するシステムで実行することができる。

図１は、スレッドがメモリ内のマーク付けされていないオブジェクトの位置を特定するブロック１０２において開始する。ブロック１０２は、マーク付けされていないオブジェクトのメモリ位置（「メモリ・アドレス」とも呼ばれる）を識別することを含む。幾つかの場合、ブロック１０２は、スレッドが、初めにスタック・スペースなどのメモリの整理されたセクションにおいてマーク付けされていないルート・オブジェクトの位置を特定することを含むことができる。例えば、スレッド実施の方法１００は、ガベージ・コレクションのまさに始めに、ルート・オブジェクトについてスタック・スペースを初めに走査するときに、ブロック１０２を実行することができる。一方、幾つかの場合において、ブロック１０２は、ヒープ・スペースなどのメモリの整理されていないセクションにおいて、マーク付けされていないオブジェクトの位置を特定することを含むことができる。例えば、スレッド実施の方法１００は、ペアレント・オブジェクト内のマーク付けされていないチャイルド・オブジェクトへのポインタをたどることによって、ブロック１０２を行うことができる。

ブロック１０４において、スレッドは、ビットマップとメモリとの間で、メモリ内のマーク付けされていないオブジェクトのサイズがアライメント・サイズより十分に大きいかどうかを判断する。前述のように、ビットマップ内の各々のインデックス位置（即ち、ビットマップ内の各々のビット）は、メモリの同じサイズの領域に対応する。ビットマップ内の各々のビットが対応するメモリのこのサイズは、アライメント・サイズと呼ばれる。従って、マーク付けされていないオブジェクトが、メモリ内でアライメント・サイズより小さくなる場合、マーク付けされていないオブジェクトは、ビットマップ内の１ビットのみによって参照することができる。例えば、ビットマップ内の各々のビットは、メモリの１６バイト領域に関する情報を提供することができる。この例において、アライメント・サイズは、１６バイトである。メモリ内のマーク付けされていないオブジェクトのサイズが、１０バイトのみである場合、ビットマップ内の１ビットのみによって参照することができる。マーク付けされていないオブジェクトがビットマップ内の１ビットのみで参照される場合、そのオブジェクトに関連するマーク付け情報を表すために複数のビットマップ・ビットを使用することは便利ではない。しかし、マーク付けされていないオブジェクトのサイズが２０バイトである場合、１６バイトのアライメント・サイズを有する前述の例において、そのオブジェクトによって消費されるメモリ内の全スペースを追跡するために、１つより多くのビットマップ・ビットを必要とすることになる。マーク付けされていないオブジェクトが、ビットマップ内の２ビットによって参照される場合、そのオブジェクトに関するマーク付け情報を表すために、複数のビットマップ・ビットを使用することが可能となる。

幾つかの実施形態において、ブロック１０４は、マーク付けされていないオブジェクトがアライメント・サイズより大きいかどうか判断することを含むだけでなく、マーク付けされていないオブジェクトがどれほど大きいかを判断することができる。例えば、マーク付けされていないオブジェクトがアライメント・サイズの少なくとも２倍大きいことは、有利な場合がある。この例において、オブジェクトのサイズがアライメント・サイズの２倍の大きさであれば、オブジェクトのサイズは、アライメント・サイズより単に「十分に大きい」とすることができる。このことは、例えば、メモリ内のオブジェクトの最小サイズがアライメント・サイズに比べて小さいメモリ・システムにおいて有利な場合がある。例えば、メモリ・システムが、最小オブジェクト・サイズは１バイトであるが、アライメントサイズは８バイトと指定することができる。この例においては、メモリ内の９バイトのオブジェクトは、追跡するために２ビットマップ・ビットを必要とする領域を占有する。しかし、そのオブジェクトは、第２のビットマップ・ビットによって追跡される８バイト領域のうちの１バイトしか消費しないので、その領域は、他の７つの１バイト・オブジェクトを含むこともできる。従って、そのような例では、９バイト・オブジェクトのマーク付けを追跡するために第２のビットマップ・ビットを使用すると、紛らわしい可能性がある。

しかし、ブロック１０４が、オブジェクト・サイズがアライメント・サイズの少なくとも２倍の大きさであるかどうかを判断する場合、ブロック１０４は、そのオブジェクトが格納されているメモリの領域を追跡するために２ビットマップ・ビットが割り当てられるであろうということを確認するために使用することができ、従って２ビットマップ・ビットがそのオブジェクトを白、グレイ、又は黒とマーク付けするために使用可能であろうと確認することができる。例えば、システム内のアライメント・サイズが４バイトであった場合、ブロック１０４は、マーク付けされていないオブジェクトのサイズが少なくとも８バイトであるかどうかを判断するために使用することができる。

幾つかの実施形態において、ブロック１０４は、オブジェクト自体がアライメント・サイズより十分に大きいかどうかを判断するために使用できるばかりでなく、オブジェクトに割り当てられた領域が十分に大きいかどうかを判断するために使用することができる。例えば、幾つかのメモリ・システムは、オブジェクトを説明するヘッダー又はプロセス中の次のオブジェクトに関する情報を与えるフッターを全てのオブジェクトに付加することを要求する場合がある。そのようなメモリ・システム上で方法１００を実施するとき、ブロック１０４は、オブジェクトのヘッダー及びフッターを考慮に入れることがある。例えば、アライメント・サイズが８バイトであり、オブジェクトのサイズは８バイトであるがさらに８バイトのヘッダーを有する場合、ブロック１０４は、そのオブジェクトは、ヘッダーを考慮に入れると、アライメント・サイズの２倍の大きさであると結論づけることができる。

幾つかの実施形態において、ブロック１０４の判断は、システム全体（又はメモリ・スペース全体）に基づいて行うことができる。換言すれば、ブロック１０４において、スレッドは、特定のオブジェクトがアライメント・サイズより十分に大きいかどうかではなく、メモリ・スペースについての最小オブジェクト・サイズがアライメント・サイズより十分に大きいかどうかを判断する場合がある。例えば、ヒープ・スペース内でオブジェクトの位置が特定されている場合、ブロック１０４を実行しているスレッドは、その最小オブジェクト・サイズがアライメント・サイズより十分に大きい（例えば、２倍大きい）かどうかを判断することができる。これらの実施形態においては、ブロック１０４は、ブロック１０２の前に、さらには、ガベージ・コレクション・プロセス又はガベージ・コレクション・プロセスのためのマーク付けが開始される前に、実行することができる。むしろ、ブロック１０４は、これらの実施形態においては、予備的な措置として行われ、システム構成として格納することができる。

スレッドが、ブロック１０４において、オブジェクト・サイズ（例えば、ヘッダー、フッターなどを含むオブジェクトに割り当てられるメモリ領域）がアライメント・サイズより十分に大きくないと判断する場合、スレッドは、オブジェクトの３色マーク付けを行うために複数のビットマップ・ビットを使用するべきではないと結論づけ、方法１００はブロック１０６において終了する。しかし、スレッドが、オブジェクト・サイズがアライメント・サイズより十分に大きいと判断する場合、スレッドはブロック１０８へ進み、そこでスレッドは、マーク付けされていないオブジェクトの対応するインデックス位置（又は、位置（複数））を識別する。

ブロック１０８において、スレッドは、マーク付けされていないオブジェクト（例えば、ブロック１０２において識別された可能性がある）のメモリ・アドレスをビットマップのインデックス位置に変換することができる計算を、行うことができる。例えば、スレッドは、メモリ・アドレスを所定の整数（例えば、１００）で割り、次いで、得られた商から別の所定の整数（例えば、２００）を差し引くことができる。この計算の結果、マーク付けされていないオブジェクトが格納されているメモリ領域のメモリ・アドレスに対応するインデックス位置を識別することができる。

幾つかの実施形態において、ブロック１０８は、複数のインデックス位置を識別することを含むことができる。計算されるインデックス位置の数は、アライメント・サイズに関するマーク付けされていないオブジェクトのサイズに依存し得る。例えば、マーク付けされていないオブジェクトのサイズがアライメント・サイズの４倍の大きさである場合、マーク付けされていないオブジェクトが格納される全領域は、ビットマップ内の４ビットに対応することになる。この例において、ブロック１０８を実行するスレッドは、複数のビットマップ・ビットがそのマーク付けされていないオブジェクトに対応することを検出することができ、それらのビットマップ・ビットすべてを識別することができる。幾つかの実施形態において、スレッドは、ビットマックのビットのうちの２つのみを、２つより多くのビットがマーク付けされていないオブジェクトに対応する場合でも識別することができる。例えば、マーク付けされていないオブジェクトによって占有される領域が、１０ビットマップ・ビットに対応する場合、スレッドは、初めの２つのインデックス位置（例えば、そのオブジェクトによって占有される最小のメモリ・アドレスに対応する２つのインデックス位置）、又は、最後の２つのインデックス位置（例えば、そのオブジェクトによって占有される最大のメモリ・アドレスに対応する２つのインデックス位置）のみを識別することができる。

スレッドが、マーク付けされていないオブジェクトのメモリ位置に対応するインデックス位置を識別すると、スレッドは、ブロック１１０に進み、それらのインデックス位置の「第１」にビットを設定する。換言すれば、スレッドは、第１のインデック位置におけるビットを「０」から「１」へ切り替える。第１のビットを１に設定することにより、スレッドは、ブロック１０２において位置を特定されたマーク付けされていないオブジェクトが、今やマーク付けされて「グレイ」又は「黒」とみなされるという事実を記録する。このマーク付けにより、その第１のインデックス位置に対応するメモリ・アドレスに到達可能なオブジェクトが存在し、従ってそのオブジェクトは削除されるべきではないことを、ガベージ・コレクティング・システムに通知する。

ブロック１１０において、「第１」のインデックス位置が何であるかを判断することは、システムの他の構成に依存し得る。例えば、幾つかの実施形態において、第１のインデックス位置は、マーク付けされていないオブジェクトについてのビットマップを走査するようにスレッドがプログラムされる方向に依存し得る。本質的ではないが、「第１」のインデックス位置は、スレッドがビットマップを走査しているときにブロック１０８で識別されたインデックス位置のうち、スレッドが初めに遭遇するインデックス位置であることが、有利な場合がある。スレッドが、ビットマップを上昇方向（即ち、小さいメモリ・アドレスに対応するインデックス位置で開始し、大きいメモリ・アドレスに対応するインデックス位置へ向かって進む）へ走査するようにプログラムされる場合、「第１の」インデックス位置は、マーク付けされていないオブジェクトによって占有される最小のメモリ・アドレスに対応するインデックス位置とすることができる。しかし、スレッドが、ビットマップを下降方向に走査するようにプログラムされる場合、「第１の」インデックス位置は、マーク付けされていないオブジェクトによって占有される最大のメモリ・アドレスに対応するインデックス位置とすることができる。幾つかの実施形態において、ブロック１０８において識別された２つより多くの対応するインデックス位置が存在する場合でも、「第１の」インデックス位置は、常に、マーク付けされていないオブジェクトによって占有される２つの最小の又は２つの最大のメモリ・アドレスに対応する２つのインデックス位置のうちの１つとすることができる。これらの実施形態において、これらの２つのインデックス位置の「第１の」インデックス位置は、依然として、スレッドの走査方向によって決定することができる。換言すれば、スレッドがビットマップを下降方向に走査するようにプログラムされ、ブロック１０８において４つのインデックス位置が識別される場合、ブロック１１０は、第１のビットとして、２番目に低いインデックス位置（即ち、マーク付けされていないオブジェクトによって占有される、２番目に小さいメモリ・アドレスに対応するインデックス位置）に設定することができる。これは、ビットマップを下降方向に走査するスレッドによって、２つの最低インデックス位置のうちの２番目に低いインデックス位置が初めに分析されることになるためである。

ブロック１１０において、第１の識別されたインデックス位置においてビットが設定されると、「マーク付けされていない」オブジェクトは「グレイ」とマーク付けされているとみなすことができる。このことは、そのオブジェクト自体は位置を特定されてマーク付けされているが、マーク付けされていないチルドレンを有する可能性があることを意味する。従って、ブロック１１０において、オブジェクトをグレイとマーク付けした後、スレッドは、ブロック１１２において、オブジェクトが少なくとも１つのマーク付けされていないチャイルドを有するかどうか判断することに進む。例えば、スレッドは、メモリ内のオブジェクトのコンテンツを分析し、オブジェクトが他のオブジェクト（即ち、チルドレン）へのいずれかのポインタを含むかどうか判断することができる。殆どの場合、直前にマーク付けされていないオブジェクトがチルドレンを有すると、それらのチルドレンは、マーク付けされていないことになる。従って、殆どの場合、スレッドは、ブロック１１２において、グレイ・オブジェクトがチルドレンへのポインタを有する場合、それらのチルドレンはマーク付けされていないと安全に推定することができる。

スレッドが、ブロック１１２において、グレイ・オブジェクトがマーク付けされていないチルドレンを何も有していないと判断する場合、スレッドは、ブロック１１４で、第２の識別されたインデックス位置においてビットを設定することができる。この第２のインデックス位置は、ブロック１０８においてオブジェクトが格納されているメモリ領域に対応すると識別されたインデックス位置の中にあるはずである。第２の位置にあるビットが設定されると、「グレイ」オブジェクトは、「黒」とみなすことができる。このことは、オジェクトの位置が特定されて「到達可能」とマーク付けされていることと、オブジェクトが、位置が特定されず「到達可能」とマーク付けされていないチルドレンを持たないこととを意味する。

ブロック１１４における「第２のインデックス位置」は、第１のインデックス位置に隣接するものとすることができる。これは、３色マーク付けに使用するためにビットマップ内の２つの隣接するビットしか必要としないので、有利な場合がある。例えば、スレッドがオブジェクトについてのビットマップを走査していた場合、スレッドは、第１のインデックス位置においてビットがセットされていることを発見することがある。スレッドは、到達可能オブジェクトが、その第１のインデックス位置に対応するメモリ・アドレスにおいてメモリに格納されていると結論づけることができる。次の隣接するビットを走査することにより、スレッドは、そのオブジェクトがいずれかのマーク付けされていないチルドレンを有するかどうかを結論づけることもできる。

選択された第２のインデックス位置がビットマップ内の上流（即ち、より大きいメモリ・アドレス）にあるか又はビットマップ内の下流にあるかは、ブロック１１０に関連して論じられたように、システムのスレッドの走査位置に基づいて決定することができる。例えば、スレッドが、ビットマップを上昇方向に（即ち、低メモリ・アドレスに対応するインデックス位置から、高メモリ・アドレスに対応するインデックス位置へ）走査するようにプログラムされる場合、より高いインデックス位置を選択することが有利な場合がある。

スレッドが、ブロック１１２において、オブジェクトが少なくとも１つのマーク付けされていないチャイルドを有すると判断する場合、スレッドは、ブロック１１６において、グレイ・オブジェクト内のチャイルドへのポインタをたどって進み、メモリ内でそのチャイルドの位置を特定する。メモリ内でチャイルドの位置を特定することは、システムの仕様及びポインタのコンテンツに基づいて変わる場合があるが、通常、チャイルドは、チャイルドのメモリ・アドレスを決定するためのポインタ内の情報を用いて位置が特定される。チャイルドのメモリ・アドレスの位置が特定されると、スレッドは、そのメモリ・アドレスのビットマップにおける対応するインデックス位置を識別することもできる。チャイルドのメモリ・アドレスについての対応するインデックス位置が識別されると、スレッドは、そのインデックス位置に、チャイルドの位置が特定されてマーク付けされていることを示すビットを設定することができる。このことは、そのインデックス位置に対応するメモリ位置に到達可能なオブジェクトが格納されていることを、他のスレッドに対して示すことになる。

ブロック１１６においてチャイルドの位置が特定されてマーク付けされた後、スレッドは、ブロック１１４に進み、ペアレント・オブジェクト（即ち、ブロック１０２において位置が特定されたオブジェクト）についての第２のインデックス位置においてビットを設定する。スレッドは、次に、ブロック１１８において、ペアレント・オブジェクトが、他のいずれかのチルドレンへのポインタを含むかどうか判断する。ペアレントがさらに別のチルドレンを有する場合、スレッドは、ブロック１２０において、次のチャイルドの位置を特定してマーク付けすることに進む。この位置の特定及びマーク付けは、ブロック１１６の位置の特定及びマーク付けに類似する場合がある。ブロック１２０において、次のチャイルドの位置が特定されてマーク付けされた後、スレッドは、ブロック１１８に戻り、さらにチルドレンが存在するかどうかを再び判断する。スレッドが、ブロック１１８において、ペアレント・オブジェクト（即ち、ブロック１０２において位置が特定されたオブジェクト）がチャイルド・オブジェクトへのさらなるポインタを有しないと判断する場合、スレッドは、ブロック１１６において方法１００を終了する。

図１は、方法１００に関する動作の１つの可能な順序を示すが、幾つかの他の実施形態においては、動作の正確なタイミング及び順序は、前述とは異なるものとすることができる。例えば、幾つかの実施形態においては、ブロック１１４における、ペアレントについて第２のビットを設定する正確なタイミングは、システム構成、ペアレントによってポイントされるチルドレンの数、並びに、チャイルド及びペアレントのオブジェクトの近接度に依存する可能性がある。

例えば、幾つかの実施形態において、第２のインデックス位置におけるビットは、ペアレント・オブジェクトのチルドレンの閾値パーセンテージが「グレイ」とマーク付けされるまで（例えば、ブロック１１６、１１８及び１２０を通して）、ブロック１１４において設定されない可能性がある。このことは、ブロック１１４において第２のビットを設定することによって、ビットマップを走査している他のスレッドに、ペアレントの全てのチルドレンがマーク付けされていることを知らせることができるので、ペアレントが多数のチルドレンを有する場合に有利な可能性がある。これは、努力の重複を避けるために有用であり得るが、ペアレントが非常に多くのチルドレンを有する場合に、他のスレッドがペアレントのチルドレンをマーク付けするのを支援することを妨げる可能性がある。このような場合には、努力のある程度の重複の可能性が、多数のチルドレンの位置を特定してマーク付けする複数のスレッド作業の性能上の利点を正当化する。従って、閾値（例えば、５０）を超える多数のチルドレンを伴うペアレント・オブジェクトについて、スレッドは、ペアレントのチルドレンの閾値数がマーク付けされるまで、ブロック１１４で第２のインデックス位置におけるビットを設定しなくて良い。例えば、ペアレント（例えば、ブロック１０２においてマーク付けされたオブジェクト）が、１００のチルドレンを有する場合、閾値は、５０％（即ち、ブロック１１８及び１２０の４９回の繰り返しと、ブロック１１６の１回の繰り返しの和）に設定することができる。

一方、幾つかの場合、スレッドは、チャイルドのマーク付けプロセスにおいてそうすることが好都合である限り、ブロック１１４において第２のビットを設定することを試みることができる。ブロック１１４において第２のビットをいつ設定するのが「好都合である」かは、ペアレント・オブジェクト（即ち、ブロック１０２において位置が特定されたオブジェクト）とチャイルド・オブジェクトの近接度に依存し得る。例えば、ブロック１１６において位置が特定されてマーク付けされたチャイルド・オブジェクトが、ビットマップ内でペアレント・オブジェクトに近い場合、ペアレントの第２のビットとチャイルドの第１のビットとを、同時に（例えば、同じ「コンペア・アンド・スワップ」命令内で）マーク付けすることができる。しかし、ブロック１１６において位置が特定されてマーク付けされたチャイルド・オブジェクトが、ペアレント・オブジェクトに近くない場合、スレッドは、ブロック１１８及びブロック１２０の繰り返し中に位置が特定されるペアレントにチャイルドが接近するまで、ブロック１１４において第２のビットを設定することを遅らせることができる。例えば、スレッドは、ブロック１１６から、ブロック１１８及びブロック１２０まで直接進むことができる。ブロック１１８及びブロック１２０の第１の繰り返し中に位置が特定されるチャイルドが、ペアレント・オブジェクトの近くで位置が特定される場合、スレッドは、ブロック１１４において、そのチャイルドをマーク付けすることができ、同時に第２のビットを設定することができる。そうでない場合には、スレッドは、再びブロック１１４を遅らせ、ブロック１１８及びブロック１２０のさらに別の繰り返しを行う。この実施は、ビットマップ内のビットを設定する余分な命令を防ぐことができるが、ブロック１１４における第２のインデックス位置のビットの設定を遅らせることは、別のスレッドが、ビットマップ走査でペアレント・オブジェクトを見つけ、それがグレイであると結論づけ、そのペアレントのチルドレンを走査することによって（例えば、ブロック１１６、１１８、及び１２０を実行することによって）努力を重複する機会を増やす可能性がある。従って、このようにブロック１１４を遅らせるようにプログラムされたスレッドは、ブロック１１８及び１２０の繰り返しの閾値数が行われた（例えば、２０の繰り返し）後にブロック１１４を行うようにプログラムすることもできる。

幾つかの場合においては、スレッドが、ブロック１１４において第２のインデックス位置の第２のビットを可能な限り早く設定することが有利な場合がある。第２のインデックス位置においてビットを設定することにより、効果的にペアレント・オブジェクトを「黒」とマーク付けし、これによって、ペアレント・オブジェクトの全てのチルドレンがマーク付けされていることをスレッドに知らせる。これにより、次に、スレッドがポインタについてペアレントを分析することをスキップして、他のオブジェクトについてビットマップを走査することに移ることができることを意味する。このことは、別のスレッドがビットマップ走査でペアレント・オブジェクトの位置を特定し、別のスレッドによって既にマーク付けされ位置が特定されたチルドレンの位置を特定してマーク付けする試みを開始する危険性を最小にすることができる。

理解のために、図２Ａ～２Ｃは、本開示の実施形態による、３色マーク付けをビットマップで用いることができるメモリ・システム２００の抽象的な図を示す。図２Ａは、あらゆるオブジェクトが到達可能とマーク付けされる前のメモリ・システム２００の初めの図を示す。

メモリ・システム２００は、システムのコンピュータ処理ユニット（ＣＰＵ）によって重度に管理されるメモリの整理され秩序だった部分であるスタック・スペース２０２を含む。メモリ・システム２００はさらに、システムについての殆どのリソース・オブジェクトを格納することができる、より大きくあまり整理されていないセクション・メモリであるヒープ・スペース２０４を含む。ヒープ・スペース２０４のコンテンツは、各々が単一ビットを含むインデックス位置の１次元マトリックスであるビットマップ２０６によって、マッピングすることができる。インデックス位置２０８及び２１０は、それぞれヒープ・スペース２０４の最大及び最小のメモリ・アドレスに対応する、ビットマップ２０６のビットを表す。ビットマップ２０６は、理解し易くするために、１９のインデックス位置のみを含むように表されているが、実際には、ビットマップは、それらが追跡するヒープ・スペースのサイズに応じて、遥かに多数のインデックス位置を含むことができる。

スタック・スペース２０２は、ルート・オブジェクト２１２を含む。スレッドは、メモリ・システム２００において３色マーク付けを行うことを開始するときに、ルート・オブジェクト２１２を分析して、チャイルド・オブジェクト（オブジェクト２１４）へのポインタを発見することができる。そのポインタを分析することによって、スレッドに、ヒープ・スペース２０４におけるそのオブジェクトのメモリ内の位置（即ち、メモリ・アドレス）を与えることができる。この分析は、破線２１６によって表される。チャイルド２１４のメモリ・アドレスを用いて、スレッドは、オブジェクト２１４が格納されているヒープ・スペース２０４の領域のメモリ・アドレスに対応する、ビットマップ内のインデックス位置（インデックス位置２１６～２２２）を、識別することができる。この識別は、破線２２４によって表され、これらのインデックス位置を包含するビットマップの領域は、破線ボックス２２６によって示される。

図２Ｂは、メモリ・システム２００の次の図を示す。図２Ｂにおいて、スレッドは、インデックス位置２１６においてビットを設定し、インデックス位置２１６に対応するメモリ・アドレスに到達可能なオブジェクト（オブジェクト２１４）が存在することを示す。メモリ・システム２００のスレッドは、オブジェクトについてのビットマップを上昇方向に（即ち、インデックス位置２０８からインデックス位置２１０へ向かって）走査するようにプログラムすることができるため、スレッドは、ビットマップ領域２２６における他のいずれかのビットではなく、インデックス位置２１６を選択することができる。なぜなら、インデックス位置２１６は、ビットマップ２０６を走査するスレッドが遭遇することになる領域２２６内の初めのインデックス位置であるからである。従って、インデックス位置２１６において設定されたビットは、そのインデックス位置に対応するオブジェクト（オブジェクト２１４）が「グレイ」とマーク付けされていることをスレッドに示すことができるが、そのオブジェクトについての次のインデックス位置（例えば、インデックス位置２１８）に設定されたビットは、そのオブジェクトが「黒」とマーク付けされていることを示すことができる。

インデックス位置２１６においてビットを設定すると、スレッドは、オブジェクトを分析して、オブジェクトがチャイルド・オブジェクト２３４、２３６、及び２３８への３つのポインタ２２８、２３０、及び２３２を有することを発見することができる。それらのポインタの１つを分析することにより、スレッドは、メモリにおけるチャイルド・オブジェクトの１つの位置を決定することができる。例として、破線２４０は、スレッドがポインタ２３２を分析してチャイルド・オブジェクト２３８のメモリ・アドレスを決定する分析を示す。

チャイルド・オブジェクト２３８のメモリ・アドレスを決定することにより、スレッドは次に、チャイルド・オブジェクト２３８によって占有されるメモリの領域に対応する、ビットマップ２０６内の対応するインデックス位置を識別することができる。この識別は、破線２４２によって示され、チャイルド・オブジェクト２３８の位置が特定されたメモリ領域にインデックス位置が対応する、ビットマップ２０６の領域２４４を示す。インデックス位置２４６は、それらのインデックス位置の「最下位」であり、ビットマップを上昇方向に走査するスレッドによって走査されることになる。

図２Ｃは、メモリ・システム２００の次の図を示す。図２Ｃにおいて、チャイルド・オブジェクト２３８に対応するインデックス位置を識別したスレッドは、インデックス位置２４６でビットを設定している。このことは、実際に、チャイルド・オブジェクト２３８を「グレイ」とマーク付けし、ビットマップを走査している他のスレッドに対して、到達可能なオブジェクトがインデックス位置２４６に関連付けられるメモリ領域を占有していることを知らせる。図２Ｃに描かれているように、チャイルド・オブジェクト２３８に対応するインデックス位置を識別したスレッドは、インデックス位置２１８でもビットを設定している。

互いに隣接し、いずれも設定されている２１６及び２１８のビットは、到達可能なオブジェクトがインデックス位置２１６及び２１８に関連付けられるメモリ領域を占有していることと、さらに、その到達可能なオブジェクトのチルドレンは、位置を特定してマーク付けする必要がないこととを、ビットマップを走査している他のスレッドに知らせる。換言すれば、インデックス位置２１８にビットを設定することは、オブジェクト２１４のマーク付けを「グレイ」から「黒」へ効果的に変更する。幾つかの実施形態において、インデックス位置２１８のビットは、オブジェクト２１４の第１のチャイルドがマーク付けされたときに、設定されている可能性がある。このことは、他のいずれかのスレッドが、オブジェクト２１４の残りのチルドレン（例えば、チャイルド・オブジェクト２３４及び２３６）の位置を特定してマーク付けするのを助けることを妨げることになるが、重複努力（例えば、他のスレッドが、チャイルド・オブジェクト２３８の位置を、それが既にマーク付けされた後で決定してマーク付けするように試みること）を防ぐための助けにもなる。幾つかの実施形態において、インデックス位置２１８のビットは、オブジェクト２１４の最後のチャイルドがマーク付けされたときに設定することができる。このことは、別のスレッドが、オブジェクト２１４の残りのチルドレンの位置を特定してマーク付けすることを助ける機会を増やすことになるが、重複努力の機会を増やすことにもなる。幾つかの実施形態において、インデックス位置２１８のビットは、オブジェクト２１４の閾値数のチルドレンがマーク付けされた後で、又は、インデックス位置２１８と同じコンペア・アンド・スワップ命令でマーク付けすることができるチャイルド・オブジェクトと同時に、設定することができる。

スレッドは、オブジェクト２１４によってポイントされた全てのチャイルド・オブジェクトの位置を特定してマーク付けすると、グレイ・オブジェクトについてビットマップ２０６を走査し続けることができる。グレイ・オブジェクトの位置を特定すると、スレッドは、ヒープ・スペース内でそのオブジェクトの位置を特定することができ、そのポインタをたどって、そのチルドレンの位置を特定してマーク付けを開始することができる。

図２Ａに示されるように、ビットマップ２０６を上昇方向に走査する（例えば、インデックス位置２０８で開始し、２１０に向かって走査する）スレッドは、初めにインデックス位置２１６に設定されたビットを発見することができる。メモリ・システムにおけるスレッドは、オグジェクトをグレイとマーク付けするときに「最下位」のインデックス位置にビットを設定するようにプログラムされている場合、スレッドは、インデックス位置２１６に設定されたビットを検出することによって、到達可能なオブジェクト（即ち、オブジェクト２１４）がインデックス位置に対応するヒープ・スペース領域に位置すること、及び、その到達可能なオブジェクトが「グレイ」とマーク付けされていることを、仮定することができる。しかし、スレッドは、オブジェクト２１４のチルドレンが位置を特定されてマーク付けされているかどうかを直ちに知ることにはならない。スレッドは、次のインデックス位置であるインデックス２１８を走査することによって、しかし、そのオブジェクトが「黒」とマーク付けされたことを推論できることになる（特に、最小オブジェクト・サイズがアライメント・サイズより大きいシステムにおいて）。これは、オブジェクト２１４の全てのチルドレンがマーク付けされているか、又はマーク付けされている最中であることを意味する。従って、スレッドは、ヒープ・スペース内でオブジェクト２１４の位置を特定したり、オブジェクト２１４のポインタをたどってそのチルドレンの位置を特定してマーク付けしたりする必要がないと結論づけることができる。

オブジェクト２１４が「黒」とマーク付けされたことを理解すると、スレッドは、インデックス位置に設定されたビットを検出するまで、ビットマップ２０６を走査し続けることができる。これにより、インデックス位置２１６に設定されたビットと同様に、対応するヒープ・スペース位置にある到達可能なオブジェクト（即ち、チャイルド・オブジェクト２３８）が「グレイ」とマーク付けされたことを再びスレッドに知らせる。しかし、次のインデックス位置（インデックス位置２４８）を走査し、そこにビットが設定されたことを検出することによって、スレッドは、チャイルド・オブジェクト２３８がまだ「黒」とマーク付けされていなかったと結論づけることができる。これは、チャイルド・オブジェクト２３８が、位置を特定してマーク付けする必要がある幾つかの到達可能なチルドレンを有する可能性がまだあることを意味することになり、従ってスレッドは、ヒープ・スペース内でチャイルド・オブジェクト２３８の位置を特定し、ポインタについてそれを分析することを開始することができる。

前述のように、第１のスレッドは、オブジェクト２１４のチルドレンの位置を特定してマーク付けしながら、インデックス位置２１８におけるビットを設定した可能性がある。従って、第２のスレッドは、そのオブジェクト２１４が「黒」とマーク付けされたことを検出し、その検出に基づいて走査を続け、そのチャイルド・オブジェクト２３８が「グレイ」とマーク付けされたがまだ「黒」とマーク付けされていないことを検出することができる。従って第２のスレッドは、第１のスレッドが依然としてチャイル・オブジェクト２３４及び２３６の位置を特定してマーク付けしている一方で、チャイルド・オブジェクト２３８のチルドレンの位置を特定してマーク付けすることを開始することができる。このようにして、３色マーク付けを用いて、メモリ・システム２００内で、重複努力の可能性を減らしながら複数のスレッドの効率の利益を得ることができる。

図３は、到達可能なオブジェクトについてビットマップを走査する方法３００を示す。方法３００はさらに、ガベージ・コレクションのために到達可能なオブジェクトを識別中のスレッドが本開示の３色マーク付けシステムを使用することができる方法を示す。例えば、方法３００は、図２Ｃに関連して論じられた「第２のスレッド」によって実行することができる。

方法３００は、スレッドがインデックス位置を走査するブロック３０２で開始する。幾つかの場合において、そのインデックス位置は、ビットマップ内の第１のインデックス位置であるかもしれないし、次のインデックス位置であるかもしれない。幾つかの実施形態において、スレッドは、ビットマップを上昇方向に走査することができ、一方、他の実施形態においては、スレッドは、ビットマップを下降方向に走査することができる。ブロック３０４において、スレッドは、ブロック３０２において走査されたインデックス位置（本明細書では第１のインデックス位置と呼ばれる）においてビットが設定されている（即ち、「１」に設定されている）かどうか判断する。スレッドが、ビットが設定されていないと判断する場合、スレッドは、第１のインデックス位置に対応する位置におけるメモリには、「到達可能」とマーク付けされたオブジェクトが格納されていないと結論づけることができる。スレッドは次に、ブロック３０６において、ビットマップ内の次のインデックス位置（本明細書では「第２の」インデックス位置と呼ばれる）を走査することに進む。スレッドは次に、ブロック３０４に戻り、第２のインデックス位置においてビットが設定されているかどうか判断する。

ブロック３０４において、スレッドが、インデックス位置に（例えば、第２のインデックス位置に）ビットが設定されていると判断する場合、スレッドは、到達可能なオブジェクトがそのインデックス位置に対応するメモリ・アドレスに配置されていると結論づけることができる。このことは、オブジェクトが「グレイ」とマーク付けされたことをスレッドに知らせるが、スレッドは、そのインデックス位置（例えば、第２のインデックス位置）のみに基づいて、オブジェクトが「黒」とマーク付けされたかどうかを判断することができない。従って、スレッドは次に、ブロック３０８において、ビットマップ内の次のインデックス位置（本明細書では「第３の」インデックス位置と呼ばれる）を走査することに進む。

スレッドは次に、ブロック３１０において、次のインデックス位置（例えば、第３のインデックス位置）にビットが設定されているかどうか判断する。スレッドが、ビットが設定されていると判断する場合、スレッドは、２つの先行するインデックス位置（例えば、第２及び第３のインデックス位置）にビットが設定されたので、オブジェクトが「黒」とマーク付けされたと結論づけることができる。このことは、マーク付けされたオブジェクトのチルドレンが位置を特定されてマーク付けされていること、又は、十分な数のチルドレンがマーク付けされており、チルドレンに関して支援はもはや必要ないことを、スレッドに知らせることになる。従って、スレッドは、ブロック３１２において黒オブジェクトをスキップすることができ、ブロック３０６における次のインデックス位置を走査することに進むことができる。

一方、ブロック３１０において、スレッドが、ビットが設定されていないと判断する場合、２つの先行するインデックス位置（例えば、第２及び第３のインデックス位置）のうちの１つのみが設定されたビットを示したので、オブジェクトは「グレイ」とマーク付けされたと結論づけることができる。このことは、マーク付けされたオブジェクトのチルドレンがマーク付けされていなかったこと、又は、マーク付けされたチルドレンの数が十分に少ないので、残りのチルドレンの位置を特定してマーク付けするための支援が有益であることを、スレッドに知らせる。従って、スレッドは次に、ブロック３１４において「グレイ」オブジェクトをメモリからロードし、ブロック３１６においてオブジェクト内のポインタを分析し、そのチルドレンの位置を特定してマーク付けすることに進むことになる。このようにして、複数のスレッドを用いて、重複努力の望ましくないリスクを受けることなく、メモリ内の到達可能なオブジェクトの位置を特定してマーク付けすることができる。

図４は、本開示の実施形態に従って使用することができる例示的なコンピュータ・システム４０１の代表的な主要コンポーネントを示す。図示された個々のコンポーネントは、例のためだけに示されたものであり、必ずしもそれらの変化形だけではない。コンピュータ・システム４１０は、プロセッサ４１０、メモリ４２０、入力／出力インターフェース（本明細書ではＩ／Ｏ又はＩ／Ｏインターフェースとも呼ばれる）４３０、及びメイン・バス４４０を含むことができる。メイン・バス４４０は、コンピュータ・システム４０１の他のコンポーネントのための通信経路を提供することができる。幾つかの実施形態において、メイン・バス４４０は、特殊用途デジタル信号プロセッサ（図示されず）のような他のコンポーネントに接続することができる。

コンピュータ・システム４０１のプロセッサ４１０は、１つ又は複数のＣＰＵ４１２を含むことができる。プロセッサ４１０はさらに、ＣＰＵ４１２のための命令及びデータの一時的なストレージを提供する１つ若しくは複数のメモリ・バッファ又はキャッシュを含むことができる。ＣＰＵ４１２は、キャッシュ又はメモリ４２０から提供される入力に対して命令を実行することができ、その結果をキャッシュ又はメモリ４２０へ出力することができる。ＣＰＵ４１２は、本開示の実施形態と整合する１つ又は複数の方法を行うように構成された１つ又は複数の回路を含むことができる。幾つかの実施形態において、コンピュータ・システム４０１は、比較的大きいシステムに典型的な複数のプロセッサ４１０を含むことができる。しかし、他の実施形態においては、コンピュータ・システム４１０は、１つのＣＰＵ４１２のみを有する単一のプロセッサとすることができる。

コンピュータ・システム４０１のメモリ４２０は、メモリ・コントローラ４２２、及び、データを一時的に又は永続的に格納するための１つ又は複数のメモリ・モジュール（図示せず）を含むことができる。幾つかの実施形態において、メモリ４２０は、データ及びプログラムを格納するためのランダム・アクセス半導体メモリ、ストレージ・デバイス、又はストレージ媒体（揮発性又は不揮発性）を含むことができる。メモリ・コントローラ４２２は、プロセッサ４１０と通信し、メモリ・モジュールにおける情報のストレージ及び検索を容易にすることができる。メモリ・コントローラ４２２は、Ｉ／Ｏインタ－フェース４３０と通信し、メモリ・モジュールにおける入力及び出力のストレージ及び検索を容易にすることができる。いくつかの実施形態において、メモリ・モジュールは、デュアル・インライン・メモリ・モジュールとすることができる。

Ｉ／Ｏインターフェース４３０は、Ｉ／Ｏバス４５０、端末インターフェース４５２、ストレージ・インターフェース４５４、Ｉ／Ｏデバイス・インターフェース４５６、及びネットワーク・インターフェース４５８を含むことができる。Ｉ／Ｏインターフェース４３０は、メイン・バス４４０をＩ／Ｏバス４５０に接続することができる。Ｉ／Ｏインターフェース４３０は、プロセッサ４１０及びメモリ４２０からの命令及びデータを、Ｉ／Ｏバス４５０の種々のインターフェースへ向けることができる。Ｉ／Ｏインターフェース４３０はさらに、Ｉ／Ｏバス４５０の種々のインターフェースからの命令及びデータを、プロセッサ４１０及びメモリ４２０へ向けることができる。種々のインターフェースは、端末インターフェース４５２、ストレージ・インターフェース４５４、Ｉ／Ｏデバイス・インターフェース４５６、及びネットワーク・インターフェース４５８を含むことができる。幾つかの実施形態において、種々のインターフェースは、上記のインターフェースのサブセットを含むことができる（例えば、産業用途の埋め込み型コンピュータ・システムは、端末インターフェース４５２及びストレージ・インターフェース４５４を含まない場合がある）。

限定されるものではないが、メモリ４２０、プロセッサ４１０、及びＩ／Ｏインターフェース４３０を含むコンピュータ・システム４０１を通して、論理モジュールは、失敗及び１つ又は複数のコンポーネントに対する変更を、ハイパーバイザ又はオペレーティング・システム（図示せず）に伝えることができる。ハイパーバイザ又はオペレーティング・システムは、コンピュータ・システム４０１内の利用可能な種々のリソースを割り当てることができ、メモリ４２０内のデータの位置及び種々のＣＰＵ４１２に割り当てられたプロセスの位置を追跡することができる。要素を結びつけるか又は再編成する実施形態において、論理モジュールの能力の態様は、組み合わせるか又は再分散することができる。これらの変化形は、当業者には明白であろう。

本発明は、システム、方法若しくはコンピュータ・プログラム製品又はそれらの組み合わせを、いずれかの可能な技術的詳細レベルで統合したものとすることができる。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令を有するコンピュータ可読ストレージ媒体（単数又は複数）を含むことができる。

コンピュータ可読ストレージ媒体は、命令実行デバイスにより使用される命令を保持及び格納できる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、これらに限定されるものではないが、電子ストレージ・デバイス、磁気ストレージ・デバイス、光ストレージ・デバイス、電磁気ストレージ・デバイス、半導体ストレージ・デバイス、又は上記のいずれかの適切な組み合わせとすることができる。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストとして、以下のもの、すなわち、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ－ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー・ディスク、パンチカード若しくは命令がそこに記録された溝内の隆起構造のような機械的にエンコードされたデバイス、及び上記のいずれかの適切な組み合わせが挙げられる。本明細書で使用される場合、コンピュータ可読ストレージ媒体は、電波、又は他の自由に伝搬する電磁波、導波管若しくは他の伝送媒体を通じて伝搬する電磁波（例えば、光ファイバ・ケーブルを通る光パルス）、又はワイヤを通って送られる電気信号などの、一時的信号自体として解釈されない。

本明細書で説明されるコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスに、又は、例えばインターネット、ローカル・エリア・ネットワーク、広域ネットワーク若しくは無線ネットワーク、又はそれらの組み合わせなどのネットワークを介して外部コンピュータ又は外部ストレージ・デバイスにダウンロードすることができる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ若しくはエッジ・サーバ、又はそれらの組み合わせを含むことができる。各コンピューティング／処理デバイスにおけるネットワーク・アダプタ・カード又はネットワーク・インターフェースは、ネットワークからコンピュータ可読プログラム命令を受け取り、コンピュータ可読プログラム命令を転送して、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体内に格納する。

本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セットアーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ、集積回路のための構成データ、又は、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、及び、「Ｃ」プログラミング言語若しくは類似のプログラミング言語などの従来の手続き型プログラミング言語を含む１つ又は複数のプログラミング言語の任意の組み合わせで記述されるソース・コード又はオブジェクト・コードとすることができる。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で、独立型ソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は完全に遠隔コンピュータ若しくはサーバ上で実行される場合もある。最後のシナリオにおいて、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は外部コンピュータへの接続がなされる場合もある（例えば、インターネットサービスプロバイダを用いたインターネットを通じて）。幾つかの実施形態において、例えば、プログラム可能論理回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、又はプログラム可能論理アレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用することによってコンピュータ可読プログラム命令を実行して、電子回路を個別化することができる。

本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図若しくはブロック図又はその両方を参照して説明される。フローチャート図若しくはブロック図又はその両方の各ブロック、並びにフローチャート図若しくはブロック図又はその両方におけるブロックの組み合わせは、コンピュータ可読プログラム命令によって実装できることが理解されるであろう。

これらのコンピュータ可読プログラム命令を、コンピュータ又は他のプログラム可能データ処理装置のプロセッサに与えて機械を製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート若しくはブロック図又は両方の１つ又は複数のブロック内で指定された機能／動作を実施するための手段を作り出すようにすることができる。コンピュータ、プログラム可能データ処理装置若しくは他のデバイス又はそれらの組み合わせを特定の方式で機能させるように指示することができるこれらのコンピュータ・プログラム命令を、コンピュータ可読媒体内に格納することもでき、それにより、そのコンピュータ可読媒体内に格納された命令が、フローチャート若しくはブロック図又はその両方の１つ又は複数のブロックにおいて指定された機能／動作の態様を実施する命令を含む製品を含むようにすることもできる。

コンピュータ可読プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上にロードして、一連の動作ステップをコンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で行わせてコンピュータ実施のプロセスを生産し、それにより、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート若しくはブロック図又は両方の１つ又は複数のブロックにおいて指定された機能／動作を実行するためのプロセスを提供するようにすることもできる。

図面内のフローチャート及びブロック図は、本発明の様々な実施形態による、システム、方法、及びコンピュータ・プログラム製品の可能な実装の、アーキテクチャ、機能及び動作を示す。この点に関して、フローチャート内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能命令を含む、モジュール、セグメント、又はコードの一部を表すことができる。幾つかの代替的な実装において、ブロック内に示される機能は、図に示される順序とは異なる順序で生じることがある。例えば、連続して示される２つのブロックは、関与する機能に応じて、実際には実質的に同時に実行されることもあり、又はこれらのブロックはときとして逆順で実行されることもある。ブロック図若しくはフローチャート図又は両方の各ブロック、及びブロック図若しくはフローチャート図又はその両方におけるブロックの組み合わせは、指定された機能又は動作を実行する、又は専用のハードウェアとコンピュータ命令との組み合わせを実行する、専用ハードウェア・ベースのシステムによって実装できることにも留意されたい。

本開示の種々の実施形態の説明は、例証の目的のために提示されたが、これらは、網羅的であること、又は開示した実施形態に限定することを意図するものではない。当業者には、説明される実施形態の範囲から逸脱することなく、多くの修正及び変形が明らかであろう。本明細書で用いられる用語は、実施形態の原理、実際の適用、又は市場に見られる技術に優る技術的改善を最もよく説明するため、又は、当業者が、本明細書に開示される実施形態を理解するのを可能にするために選択された。

Claims (13)

1. コンピュータ・システムの情報処理により、前記コンピュータ・システムにおけるガベージ・コレクションのためにオブジェクトをマーク付けする方法であって、
   第１のメモリ・アドレスにおいて第１のオブジェクトを識別することと、
   前記第１のオブジェクトのオブジェクト・サイズが、ビットマップについてのアライメント・サイズより大きいかどうかを判断することと、
   前記第１のオブジェクトのオブジェクト・サイズが、前記ビットマップについてのアライメント・サイズより大きいと判断された場合に、
   前記第１のメモリ・アドレスに対応する、前記ビットマップ内の第１のインデックス位置を計算することと、
   前記第１のインデックス位置に第１のビットを設定することと、
   前記第１のオブジェクト内で、チャイルド・オブジェクトへのポインタを検出することと、
   前記ポインタを用いて、前記チャイルド・オブジェクトの第２のメモリ・アドレスを識別することと、
   前記第２のメモリ・アドレスに対応する、前記ビットマップ内の第２のインデックス位置を計算することと、
   前記第２のインデックス位置に第２のビットを設定することと、
   前記第１のインデックス位置に隣接する第３のインデックス位置に第３のビットを設定することと
   を含む方法。
2. 前記第１のビットを設定することは、前記第１のオブジェクトが「グレイ」とマーク付けされていることを意味し、前記第３のビットを設定することは、前記第１のオブジェクトが「黒」とマーク付けされていることを意味する、請求項１に記載の方法。
3. 前記第２のビットを設定したときに前記第３のビットを設定することをさらに決定する、請求項１に記載の方法。
4. 前記第３のビットは、前記第２のビットが設定されたのと同じコンペア・アンド・スワップ命令によって設定される、請求項３に記載の方法。
5. 前記第２のビットを設定したときに前記第３のビットを設定することを決定することは、前記第１のオブジェクトによってポイントされるチルドレンの数が閾値より少ないことを検出することに基づく、請求項３に記載の方法。
6. 前記第３のビットは、前記第１のオブジェクトの全てのチルドレンの位置が特定されて「グレイ」とマーク付けされていることを検出したときに、設定される、請求項１に記載の方法。
7. 前記第１のインデックス位置を走査することと、
   前記第１のビットが設定されていることを検出することと、
   前記第１のビットが設定されていることを検出することに基づいて、前記第１のメモリ・アドレスにおける第１の到達可能なオブジェクトが「グレイ」とマーク付けされていると結論づけることと、
   前記第３のインデックス位置を走査することと、
   前記第３のビットが設定されていることを検出することと、
   前記第３のビットが設定されていることを検出することに基づいて、前記第１のメモリ・アドレスにおける前記第１の到達可能なオブジェクトが「黒」とマーク付けされていると結論づけることと
   をさらに含む、請求項１に記載の方法。
8. プロセッサと、
   前記プロセッサによって実行されるときに前記プロセッサに方法を行わせるように構成されたプログラム命令を含む、前記プロセッサと通信するメモリと
   を含み、
   前記方法は、
   第１のメモリ・アドレスにおいて第１のオブジェクトを識別することと、
   前記第１のオブジェクトのオブジェクト・サイズが、ビットマップについてのアライメント・サイズより大きいかどうかを判断することと、
   前記第１のオブジェクトのオブジェクト・サイズが、前記ビットマップについてのアライメント・サイズより大きいと判断された場合に、
   前記第１のメモリ・アドレスに対応する、前記ビットマップ内の第１のインデックス位置を計算することと、
   前記第１のインデックス位置に第１のビットを設定することと、
   前記第１のオブジェクト内で、チャイルド・オブジェクトへのポインタを検出することと、
   前記ポインタを用いて、前記チャイルド・オブジェクトの第２のメモリ・アドレスを識別することと、
   前記第２のメモリ・アドレスに対応する、前記ビットマップ内の第２のインデックス位置を計算することと、
   前記第２のインデックス位置に第２のビットを設定することと、
   前記第１のインデックス位置に隣接する第３のインデックス位置において第３のビットを設定することと
   を含む、
   システム。
9. 前記方法は、前記第２のビットを設定したときに前記第３のビットを設定することを決定することをさらに含む、請求項８に記載のシステム。
10. 前記第２のビットを設定したときに前記第３のビットを設定することを決定することは、前記第１のオブジェクトによってポイントされるチルドレンの数が閾値より少ないことを検出することに基づく、請求項９に記載のシステム。
11. 前記方法は、
    前記第１のインデックス位置を走査することと、
    前記第１のビットが設定されていることを検出することと、
    前記第１のビットが設定されていることを検出することに基づいて、前記第１のメモリ・アドレスにおける第１の到達可能なオブジェクトが「グレイ」とマーク付けされていると結論づけることと、
    前記第３のインデックス位置を走査することと、
    前記第３のビットが設定されていることを検出することと、
    前記第３のビットが設定されていることを検出することに基づいて、前記第１のメモリ・アドレスにおける前記第１の到達可能なオブジェクトが「黒」とマーク付けされていると結論づけることと
    をさらに含む、請求項８に記載のシステム。
12. 請求項１から請求項７までのいずれか１項に記載の方法をコンピュータに実行させるコンピュータ可読プログラム命令を含むコンピュータ・プログラム。
13. 請求項１２に記載のコンピュータ・プログラムを格納したコンピュータ可読ストレージ媒体。