(57)【要約】      （修正有）【課題】参照カウント型のガベージ・コレクションでは検出できないオブジェクトの循環参照を、マーク・アンド・スイープ型のガベージ・コレクションを併用して検出する言語処理系において、この循環参照を発見するために他のプログラムを停止させる時間を短縮し、リアルタイム性に優れたガベージ・コレクションを実現する。【解決手段】各オブジェクトについてオブジェクトの順序関係に基づいた２つの参照カウント１１０を備えることで循環参照を検出するための起点となるオブジェクトの候補を絞り込み、これらの候補から参照リンクを辿って孤立した循環参照を検出する部分的なマーク・アンド・スイープ型のガベージ・コレクションを実行することで個別に循環参照をなすガベージ群を解放し、プログラムの停止時間を短縮する。【選択図】図２
2011257900.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、プログラムの実行時に個々のオブジェクトに割り当てたメモリ領域のうち、不要となったオブジェクトに割り当てたメモリ領域を解放するガベージ・コレクション方法であって、
前記コンピュータが、前記プログラムの実行に伴って増減する各オブジェクトの他オブジェクトからの被参照回数を、所定の基準によって順序付けられたオブジェクトの順序を用いて、自身よりも順序が前のオブジェクトからの被参照回数と、自身よりも順序が後のオブジェクトからの被参照回数との２つの参照カウントに分けて記憶部に保持して前記被参照回数の更新を行うステップと、
前記コンピュータが、前記２つの参照カウントの値がともに０となったときに、当該オブジェクトに割り当てたメモリ領域を解放するステップと、
前記コンピュータが、他オブジェクトを参照しているオブジェクトの前記２つの参照カウントの値の一方が０となったときに、当該オブジェクトを循環参照の検出の起点として循環参照の候補リストに登録するステップと、
前記コンピュータが、前記循環参照の候補リストに登録されているオブジェクトを１つずつ取得して、当該オブジェクトを起点として孤立した循環参照が形成されているか否かを探索し、孤立した循環参照が形成されていた場合は当該循環参照を形成している各オブジェクトに割り当てたメモリ領域を解放するステップと
を含むことを特徴とするガベージ・コレクション方法。
【請求項２】
請求項１に記載のガベージ・コレクション方法において、
各オブジェクトは、その識別子の値によって順序付けられており、
前記２つの参照カウントは、その一方が自身よりも識別子の値が小さいオブジェクトからの参照回数を保持し、他方が自身よりも識別子の値が大きいオブジェクトからの参照回数を保持する
ことを特徴とするガベージ・コレクション方法。
【請求項３】
請求項１または請求項２に記載のガベージ・コレクション方法において、
前記孤立した循環参照が形成されているか否かの探索では、起点となる当該オブジェクトから参照先のオブジェクトを順に辿って、各オブジェクトが削除されたものと仮定して、当該オブジェクトが参照していた参照先オブジェクトの前記参照カウントの値を減じる処理を繰り返し、最終的に辿ったすべてのオブジェクトの前記参照カウントの値が０となったときに、孤立した循環参照が形成されていると判定される
ことを特徴とするガベージ・コレクション方法。
【請求項４】
プログラムの実行時に個々のオブジェクトに割り当てたメモリ領域のうち、不要となったオブジェクトに割り当てたメモリ領域を解放するガベージ・コレクション処理をコンピュータに実行させるためのガベージ・コレクションプログラムであって、
前記プログラムの実行に伴って増減する各オブジェクトの他オブジェクトからの被参照回数を、所定の基準によって順序付けられたオブジェクトの順序を用いて、自身よりも順序が前のオブジェクトからの被参照回数と、自身よりも順序が後のオブジェクトからの被参照回数との２つの参照カウントに分けて記憶部に保持させて前記被参照回数の更新を行わせる処理と、
前記２つの参照カウントの値がともに０となったときに、当該オブジェクトに割り当てたメモリ領域を解放させる処理と、
他オブジェクトを参照しているオブジェクトの前記２つの参照カウントの値の一方が０となったときに、当該オブジェクトを循環参照の検出の起点として循環参照の候補リストに登録させる処理と、
前記循環参照の候補リストに登録されているオブジェクトを１つずつ取得させて、当該オブジェクトを起点として孤立した循環参照が形成されているか否かを探索させ、循環参照が形成されていた場合は当該循環参照を形成している各オブジェクトに割り当てたメモリ領域を解放させる処理と
を前記コンピュータに実行させるためのガベージ・コレクションプログラム。
【請求項５】
請求項４に記載のガベージ・コレクションプログラムにおいて、
各オブジェクトは、その識別子の値によって順序付けられており、
前記２つの参照カウントは、その一方が自身よりも識別子の値が小さいオブジェクトからの参照回数を保持し、他方が自身よりも識別子の値が大きいオブジェクトからの参照回数を保持する
ことを特徴とするガベージ・コレクションプログラム。
【請求項６】
請求項４または請求項５に記載のガベージ・コレクションプログラムにおいて、
前記孤立した循環参照が形成されているか否かの探索では、起点となる当該オブジェクトから参照先のオブジェクトを順に辿って、各オブジェクトが削除されたものと仮定して、当該オブジェクトが参照していた参照先オブジェクトの前記参照カウントの値を減じる処理を繰り返し、最終的に辿ったすべてのオブジェクトの前記参照カウントの値が０となったときに、孤立した循環参照が形成されていると前記コンピュータに判定させる
ことを特徴とするガベージ・コレクションプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機科学の分野において一般に言語処理系と総称されるソフトウェアに係り、特に、プログラムを実行することによって生じるメモリ内の断片化された未参照領域を再利用するために行われる、ガベージ・コレクションの技術に関する。
【背景技術】
【０００２】
一般に、言語処理系と呼ばれるソフトウェアは、何らかのプログラミング言語で書かれたソースコードを入力として処理を行う。これには、ソースコードの内容を逐次的に解釈して実行するインタプリタや、あるプログラミング言語で書かれたソースコードを計算機が直接的に実行可能なネイティブコードへと変換するコンパイラが含まれる。
【０００３】
一方で、Ｊａｖａ（登録商標）言語のような幾つかの言語においては、コンパイラによって、ソースコードをネイティブコードよりは抽象度が高く、元のソースコードよりは抽象度の低い中間的なコード（バイトコード）へと変換することが行われる。プログラム実行時には、このバイトコードを仮想マシンと呼ばれる機能に入力することで、仮想マシンがインタプリタと同様にバイトコードを逐次解釈して実行するか、あるいはバイトコードをネイティブコードへと変換（再コンパイル）してから実行する。このように中間的なコードであるバイトコードを利用するプログラミング言語においては、仮想マシンもまた言語処理系の一つとして扱われることがある。
【０００４】
以下、言語処理プログラムまたは言語処理系には、前記のインタプリタとコンパイラに加えて、前記の仮想マシンの機能を実行するソフトウエアも含むものとする。また、特に断らない限り、「言語」なる記述は前記のプログラミング言語を指すものとする。
【０００５】
従来の言語処理系の多くが、限られたメモリ資源を有効に利用する目的で、プログラムの実行時に動的に割り当てられ、その後未使用の状態になり不要となっても解放されない断片化されたメモリ領域を集めて再利用可能とする、ガベージ・コレクション（ごみ集め）と呼ばれる処理を自動的に実行するようにしている。
【０００６】
このようなガベージ・コレクションにおいて、不要となったメモリ領域（ガベージ）を解放するための様々なアルゴリズムが知られているが、処理が比較的単純でリアルタイム性に優れていることから、参照カウント型と呼ばれるアルゴリズムが多くのシステムで採用されている。
【０００７】
参照カウント型のガベージ・コレクションでは、メモリ領域を割り当てられている各オブジェクトに、参照カウントと呼ばれるカウンタを１つずつ持たせ、そのオブジェクトが他のオブジェクトから参照される回数（被参照回数）を記憶させる。そして、オブジェクトのコピーや参照先の変更など、プログラムの実行にともなって発生する被参照回数の増減をこの参照カウントによって動的に管理し、参照カウントが０になって他のどのオブジェクトからも利用されなくなった時点で、不要となったそのオブジェクトのメモリ領域（ガベージ）を解放する。
【０００８】
しかし、この参照カウント型のガベージ・コレクションには、他のオブジェクトから参照されることがなく孤立して不要となっていても、オブジェクトの参照先を順に辿っていくと再び同じオブジェクトに戻ってくるような場合には、それらループ状に接続されたオブジェクトに割り当てられたメモリ領域（ガベージ群）を解放することができない、という循環参照と呼ばれる欠陥が存在する。これは、実際には不要となっていても、ループ状に繋がった他の不要なオブジェクトからの参照が残っているために、オブジェクトの参照カウントが０にならないためである。
【０００９】
なお、広義の循環参照は、まだ利用されているオブジェクトをも含んで構成される場合と、他のオブジェクトから参照されることがない孤立したオブジェクトだけから構成される場合とがあるが、以後、特に断らない限り循環参照とは後者を指すものとし、それらのオブジェクトに割り当てられていて本来解放すべきメモリ領域のことを、循環参照をなすガベージ群と呼ぶこととする。
【００１０】
従来、この参照カウント型のガベージ・コレクションにおける循環参照の問題に対しては、参照カウント型とは異なるアプローチを取るマーク・アンド・スイープ型のガベージ・コレクションを併用する手法が用いられてきた（非特許文献１参照）。マーク・アンド・スイープ型のガベージ・コレクションは循環参照となっているオブジェクトをも検出可能であるので、参照カウント型のガベージ・コレクションを行いつつ、マーク・アンド・スイープ型のガベージ・コレクションを定期的に実行することで、参照カウント型では検出できずに残っていた循環参照をなすガベージ群をも解放することができる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Richard Jones and Rafael Lins, "Garbage Collection: Algorithms for Dynamic Memory Management", John Wiley & Sons Ltd., pp.19-25, 1996.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
前記のように、参照カウント型とマーク・アンド・スイープ型のガベージ・コレクションを併用することにより、参照カウント型のガベージ・コレクションでは検出できずに残っていた循環参照をなすガベージ群をも解放することができる。その一方で、マーク・アンド・スイープ型のガベージ・コレクションでは、そのガベージ・コレクション処理の実行中に他のプログラムの処理が実行されずに停止してしまう停止時間が発生する。しかも、マーク・アンド・スイープ型のガベージ・コレクションは、全てのオブジェクトを対象として連続して実行する必要があり、このことが停止時間増大の原因となって、参照カウント型の長所であるリアルタイム性を損ねるという問題があった。
【００１３】
本発明は、前記の問題を解決するためになされたものであり、循環参照をなすガベージ群を検出するときの他のプログラムの停止時間を短縮することにより、リアルタイム性に優れたガベージ・コレクションを実現することを目的とする。
【課題を解決するための手段】
【００１４】
そこで本発明は、コンピュータが、プログラムの実行時に個々のオブジェクトに割り当てたメモリ領域のうち、不要となったオブジェクトに割り当てたメモリ領域を解放するガベージ・コレクション方法であって、前記コンピュータが、前記プログラムの実行に伴って増減する各オブジェクトの他オブジェクトからの被参照回数を、所定の基準によって順序付けられたオブジェクトの順序を用いて、自身よりも順序が前のオブジェクトからの被参照回数と、自身よりも順序が後のオブジェクトからの被参照回数との２つの参照カウントに分けて記憶部に保持して前記被参照回数の更新を行うステップと、前記コンピュータが、前記２つの参照カウントの値がともに０となったときに、当該オブジェクトに割り当てたメモリ領域を解放するステップと、前記コンピュータが、他オブジェクトを参照しているオブジェクトの前記２つの参照カウントの値の一方が０となったときに、当該オブジェクトを循環参照の検出の起点として循環参照の候補リストに登録するステップと、前記コンピュータが、前記循環参照の候補リストに登録されているオブジェクトを１つずつ取得して、当該オブジェクトを起点として孤立した循環参照が形成されているか否かを探索し、孤立した循環参照が形成されていた場合は当該循環参照を形成している各オブジェクトに割り当てたメモリ領域を解放するステップとを含むことを特徴とする。
【００１５】
これにより、従来の参照カウント型のガーベジ・コレクションを行いつつ、循環参照が疑われるオブジェクトの候補を絞り込み、これらの候補を起点として参照先を順に辿って孤立したループを検出する部分的なマーク・アンド・スイープ型のガベージ・コレクションを実行することによって、個別に循環参照を検出して当該循環参照をなすガベージ群を解放する。その結果、従来のマーク・アンド・スイープ型のガベージ・コレクションを併用する方式よりも、他のプログラムの停止時間を短縮することができる。
【００１６】
また本発明は、前記のガベージ・コレクション方法において、各オブジェクトは、その識別子の値によって順序付けられており、前記２つの参照カウントは、その一方が自身よりも識別子の値が小さいオブジェクトからの参照回数を保持し、他方が自身よりも識別子の値が大きいオブジェクトからの参照回数を保持することを特徴とする。
【００１７】
これにより、オブジェクトの識別子の値を比較するという簡単な処理によって、前記２つの参照カウントのどちらを更新すればよいかがわかる。
【００１８】
また本発明は、前記のガベージ・コレクション方法において、前記孤立した循環参照が形成されているか否かの探索では、起点となる当該オブジェクトから参照先のオブジェクトを順に辿って、各オブジェクトが削除されたものと仮定して、当該オブジェクトが参照していた参照先オブジェクトの前記参照カウントの値を減じる処理を繰り返し、最終的に辿ったすべてのオブジェクトの前記参照カウントの値が０となったときに、孤立した循環参照が形成されていると判定されることを特徴とする。
【００１９】
これにより、前記起点となるオブジェクトに連結されたオブジェクト群が孤立した循環参照をなすか否かを正確に判定することができる。なお、以下、本明細書においては、循環参照を検出するための起点の候補となるオブジェクトのことを循環参照の候補と呼ぶ。
【発明の効果】
【００２０】
本発明によれば、循環参照をなすオブジェクトの検出とガベージ群の解放とを、それぞれの循環参照の候補について個別に行うので、他のプログラムの停止時間を短縮することができる。そのため、リアルタイム性が必要とされるプログラムへの適用性に優れたガベージ・コレクションを実現することができる。
【図面の簡単な説明】
【００２１】
【図１】循環参照をなすガベージ群とその参照カウントの説明図である。
【図２】言語処理プログラムと記憶部との構成例を示す機能ブロック図である。
【図３】検出すべき循環参照の例の初期状態を示す有向グラフである。
【図４】図３に示した循環参照の例を検出する手順の説明図である。
【図５】複数の循環参照が重なっている場合の例を示す有向グラフである。
【図６】全ての参照カウントが０となり循環参照が検出される例である。
【図７】０でない参照カウントが残り循環参照ではないと判定される例である。
【発明を実施するための形態】
【００２２】
以下、本発明を実施するための形態を、適宜図面を参照しながら詳しく説明する。
一般に、ガベージ・コレクションは、インタプリタや仮想マシンを用いるプログラミング言語において利用されることが多いため、本明細書においては、言語処理プログラム（インタプリタや仮想マシン）によるソースコードやバイトコードの実行に伴ってガベージ・コレクションが実行される例につき説明する。
【００２３】
一方、ソースコードをネイティブコードへとコンパイルするコンパイラ型の言語処理系を用いる（つまり、インタプリタや仮想マシンを用いない）プログラミング言語においても、プログラム中に独自にガベージ・コレクションの機能を実装することが可能であるため、本発明に係るガベージ・コレクション方法およびプログラムを利用することができる。したがって、本発明に係るガベージ・コレクション方法およびプログラムは、インタプリタや仮想マシン上での利用に限定されるものではなく、Ｃ言語のようなコンパイラ型のプログラミング言語の言語処理系においても利用可能である。
【００２４】
まず始めに、本発明との比較のために、従来のガベージ・コレクションの技術とその課題について説明しておく。従来のガベージ・コレクションには、大別して参照カウント型とマーク・アンド・スイープ型との２種類が存在する。参照カウント型のガベージ・コレクションは、数あるガベージ・コレクションのアルゴリズムの中でも最も古くから存在する手法の１つである。
【００２５】
参照カウント型のガベージ・コレクションにおいては、各オブジェクトに参照カウントと呼ばれるカウンタを１つずつ持たせる。参照カウントの値は、そのオブジェクトを参照している他のオブジェクトの数、つまりオブジェクトの被参照回数を表し、オブジェクトのコピーや計算式での利用などによって新たに他のオブジェクトからの参照が追加される毎に値が１増え、オブジェクトの削除や参照先の変更などによって他のオブジェクトからの参照が削除される毎に値が１減る。
【００２６】
オブジェクトが生成された時点での参照カウントの初期値は１であり、その後、プログラムの実行に伴うに他のオブジェクトからの参照の追加と削除とに応じて参照カウントの値を増減させる。参照カウントの値が０になることは、全ての参照がなくなったこと、すなわち他のいずれのオブジェクトからも利用されなくなったことを表す。
【００２７】
参照カウントが０になったオブジェクトは、不要なオブジェクトであるので、言語処理系によってそのオブジェクトが利用していたメモリ記憶（ガベージ）が解放される。解放されたメモリ領域は、再び別のオブジェクトを割り当てることが可能な領域となる。
【００２８】
この参照カウント型のガベージ・コレクションには、実際にはプログラム上で二度と利用されないオブジェクト群が存在していても、それらのオブジェクト群が循環参照をなしているとガベージとして検出できない、という欠陥が存在する。
【００２９】
循環参照とは、参照関係によって連結された一連のオブジェクトの最後のオブジェクトが、先頭のオブジェクトを参照することで参照がループしている状態を指す。最も小さな循環参照は、２つのオブジェクトによって構成され、あるオブジェクトＡからはもう一方のオブジェクトＢを参照し、このオブジェクトＢからもオブジェクトＡを参照するという形となる。
【００３０】
図１には、循環参照をなすガベージ群が発生する場合の一例と、そのときの参照カウントの値を示している。図１の有向グラフにおいて、丸（ノード）はオブジェクトを、矢印（エッジ）はオブジェクト間の参照関係を、丸の中の数字はオブジェクトが他のオブジェクトから参照される回数（被参照回数）である参照カウントの値を表している。ここで、図１の左側の有向グラフの状態にて、オブジェクト１０１からオブジェクト１０２への参照が終了したためこの両者を連結するエッジが削除されたものとすると、図１の右側のグラフに示した状態となる。このグラフの破線枠１０３で囲まれた４つのオブジェクトは、元のオブジェクト群から孤立して不要になっているのにも関わらず、循環参照による参照カウントが１ずつ残るためにガベージ群として検出することができない。
【００３１】
この例のように、循環参照をなす一連のオブジェクト以外の他のオブジェクトからの参照が全くなく孤立している状態は、プログラムからそれらのオブジェクトを二度と利用することがなく、不要になったガベージ群を表している。
【００３２】
不要になったガベージ群だけから構成される循環参照は、本来であればガベージ・コレクションの対象として適切に検出され、該当するすべてのメモリ領域が解放されるべきである。しかし、参照カウント型のガベージ・コレクションでは、循環参照をなすオブジェクト群の各々が、同じ循環中にある他の少なくとも１つのオブジェクトから参照されているため、参照カウントが０になることがない。参照カウントが０にならないので、ガベージとして検出されずに、いつまでも解放されないで残り続けてしまう。
【００３３】
次に、この循環参照の問題を解決するために、参照カウント型のガベージ・コレクションに併用されることが多い従来のマーク・アンド・スイープ型のガベージ・コレクションについて説明する。
【００３４】
言語処理系によって実行される全てのユーザプログラムには、オブジェクトを参照する大もととなるルートと呼ばれるオブジェクトが存在する。マーク・アンド・スイープ型のガベージ・コレクションでは、このルートから参照先を順に辿って到達できるすべてのオブジェクトに印（マーク）をつけ、最後まで辿れなかった（印がつけられなかった）オブジェクトのメモリ領域を一掃（スイープ）して解放する。
【００３５】
このマーク・アンド・スイープ型のガベージ・コレクションでは、参照カウント型では検出できない循環参照をなすガベージ群をも検出して解放することができる。また、参照カウント型のように参照の回数を逐一数えることはしないので、処理量が少なくスループット（単位時間あたりの総仕事量）が高い。
【００３６】
通常、マーク・アンド・スイープ型のガベージ・コレクションでは、マークとスイープを行う間は他のプログラムを停止させるため、本来のプログラムの処理を行うことができない。このプログラムの処理ができない時間を停止時間と呼ぶ。オブジェクトの数が多い場合などには、この停止時間は数秒にも及ぶことがあり、リアルタイム性が要求されるシステムなどでは問題となる場合がある。
【００３７】
従来より、一般にはスループットが重視され、ガベージ・コレクションのアルゴリズムとしてマーク・アンド・スイープ型を基にしたアルゴリズムが広く利用されてきた。一方で、近年になり、リアルタイム性が重視される分野においてもガベージ・コレクションを利用するプログラミング言語が広く利用されるようになるにつれ、この停止時間が問題視されてきている。
【００３８】
リアルタイム性が重視される分野の例として、医療、軍事、電気通信等が挙げられる。例えば医療における手術の補助や、軍事における戦闘行為の補助をプログラムによって行う場合、わずかな停止時間でさえ致命的なミスに繋がる可能性がある。また、電気通信の分野においても、例えば電話の接続までの時間が数秒単位で延びてしまうようなことは、サービスの品質面で問題がある。
【００３９】
このようなリアルタイム性の問題を受けて、近年ではマーク・アンド・スイープ型をベースとするアルゴリズムにおいても、マークとスイープを細分化し、所定の周期で部分的に実行する等の手法により停止時間を減らす工夫がなされている。一方で、もともとリアルタイム性が高い参照カウント型のアルゴリズムの循環参照の課題を解決することで、リアルタイム性の問題を解決しようとするアプローチも存在する。
【００４０】
前記のように、参照カウント型とマーク・アンド・スイープ型のガベージ・コレクションを併用することで循環参照をも検出して全てのガベージ群を解放することができるが、到達可能な全てのオブジェクトにマークを付すために長い停止時間が生じる可能性がある。
【００４１】
これに対し、本発明は、循環参照の検出の起点となるオブジェクトの候補を絞り込み、それらの候補と参照関係によって連結されるオブジェクト群が循環参照となっているか否かを判定することにより、個別に循環参照を検出する。これにより、循環参照をなすガベージ群の検出とその解放のために必要となるプログラムの停止時間を短縮することができる。
【００４２】
図２は、本発明の実施形態に係る言語処理プログラムと記憶部との構成例を示す機能ブロック図である。図２に示すように、言語処理プログラム１０を実行する不図示のコンピュータの記憶部１００は、ユーザプログラム６０の実行に伴って生成される複数のオブジェクト１１０〜１３０のそれぞれについて参照カウントＡ（符号１１１，１２１，１３１）と参照カウントＢ（符号１１２，１２２，１３２）との２つの参照カウントを保持する領域と、オブジェクト間の参照関係の一覧からなるオブジェクトの参照リスト１４０を保持する領域と、循環参照を検出する起点となるオブジェクトの一覧からなる循環参照の候補リスト１５０を保持する領域とを備える。また、不図示のコンピュータにユーザプログラム６０を実行させるインタプリタなどの言語処理プログラム１０は、プログラム実行制御部２０、参照カウント更新部３０、循環参照検出部４０およびメモリ領域解放部５０を備えて構成される。
【００４３】
参照カウントＡ（符号１１１，１２１，１３１）と参照カウントＢ（符号１１２，１２２，１３２）とは、所定の基準によって順序付けられたオブジェクトの順序を用いて、自身よりも順序が前のオブジェクトからの被参照回数と、自身よりも順序が後のオブジェクトからの被参照回数とをそれぞれ保持するものである。例えば、オブジェクトの識別子の値によってオブジェクトが順序付けられるのであれば、参照カウントＡを自身よりも識別子の値が小さいオブジェクトからの被参照回数、参照カウントＢを自身よりも識別子の値が大きいオブジェクトからの被参照回数とする。これは、図３の有向グラフのように、識別子の値が小さいオブジェクトが左側に来るようにノードを配置した場合、参照カウントＡ（ノード内の左側の数値）は自身よりも左側のオブジェクトからのエッジ数に、参照カウントＢ（ノード内の右側の数値）は自身よりも右側のオブジェクトからのエッジ数にそれぞれ対応付けられる。なお、図３における双方向の矢印は、オブジェクトが互いに参照し合う２つのエッジを表している。
【００４４】
プログラム実行制御部２０は、ハードディスク装置などからユーザプログラム６０を読み出して、その実行を制御する。その過程で、記憶部１００に保持されるオブジェクトの生成および削除や、オブジェクトの参照リスト１４０の登録、更新を行う。
【００４５】
参照カウント更新部３０は、ユーザプログラム６０の実行に伴って生成されるオブジェクトの被参照回数を更新する機能を有し、オブジェクトが生成されたときに参照元のオブジェクトとの順序の前後関係に応じて参照カウントＡと参照カウントＢとのいずれか一方の値を１に初期設定し、当該オブジェクトへの参照が追加あるいは削除される都度、該当するいずれかの参照カウントの値を増減させる。その結果、参照カウントＡと参照カウントＢとのいずれか一方が０となった時点で、そのオブジェクトが他のオブジェクトを参照していれば、そのオブジェクトを循環参照の候補リスト１５０に追加登録する。また、参照カウントＡと参照カウントＢとの双方が０となったオブジェクトを、不要なオブジェクトとして検出し、そのオブジェクトの参照先のオブジェクトの参照カウントを１ずつ減じるとともに、メモリ領域解放部５０にそのオブジェクトのメモリ領域の解放を依頼する処理を、再帰的に実行する。
【００４６】
循環参照検出部４０は、循環参照の候補リスト１５０に登録されたオブジェクトを１つずつ取り出し、そのオブジェクトを起点として循環参照が形成されているか否かを探索する部分的なマーク・アンド・スイープ型のガベージ・コレクションを実行する。前記した従来のマーク・アンド・スイープ型のガベージ・コレクションは、ルートから辿れる全てのオブジェクトにマークを付し、最後までマークが付されなかったオブジェクトを削除するものであった。これに対して、部分的なマーク・アンド・スイープ型のガベージ・コレクションは、起点から辿れるオブジェクトだけにマークを付し、マークが付されたオブジェクト間の参照が無くなった場合に、それらのオブジェクトの両方の参照カウントが全て０になるようであれば、マークされたオブジェクト群は循環参照となっているため、これらを削除するというものである。これは、循環参照においてはもし循環参照となっているオブジェクト群の中から１つでもオブジェクトが削除されれば、それが波及して循環全体の参照カウントが０になることを利用している。
【００４７】
部分的なマーク・アンド・スイープの具体的な手順としては、まず起点となる循環参照の候補に印を付け、あたかもこの循環参照の候補が消えたかのように、その参照先のオブジェクトＸの参照カウントを１減らす。これを参照先のオブジェクトＸでも同様に、まずＸに印をつけ、更にＸの参照先のオブジェクトの参照カウントを１減らす。これを参照先のオブジェクトがなくなるか、既に印のつけられたオブジェクトに戻ってくるまで繰り返す。
【００４８】
なお、この循環参照検出部４０が行う循環参照の探索処理は、所定の周期で定期的に実行するものであっても、候補の数が所定の数に達した場合に実行するものであっても良く、本発明ではこれを特に限定しない。
【００４９】
循環参照を検出した場合、循環参照検出部４０は、当該循環参照となっているオブジェクト群のメモリ領域を全て解放するようメモリ領域解放部５０に依頼する。
【００５０】
メモリ領域解放部５０は、参照カウント更新部３０または循環参照検出部４０からオブジェクトのメモリ領域の解放の依頼を受けて、当該オブジェクトに割り当てられているメモリ領域（ガベージ）を解放する。このとき、連続するメモリ領域については、それらをまとめて１つの大きなメモリ領域に変換する処理を行うものとしてもよい。
【００５１】
ここで、参照カウントＡとＢとの一方が０であり、かつそのオブジェクトが他のオブジェクトを参照しているという条件だけで、循環参照を検出できることを説明する。
【００５２】
図３は、循環参照の候補の数が２つしかない場合の循環参照の例を示す有向グラフである。以後、このような有向グラフにおいては、図の左から右に行くにつれて各オブジェクトを一意に識別するための識別子の値（図示は省略）が大きくなっているものとし、ノード内の数字は、左側が自身よりも識別子の値が小さいオブジェクトからの参照に対応する参照カウントＡ、右側が自身よりも識別子値がの大きいオブジェクトからの参照に対応する参照カウントＢの値を表すものとする。図３の例では、左端と右端の２つのオブジェクト２００，２０５のみ一方の参照カウントが０となっているため、この２つが循環参照の候補として循環参照の候補リスト１５０に登録されることになる。
【００５３】
次に、図３に示した初期状態から、循環参照の候補の１つである左端のオブジェクト２００を起点として部分的なマーク・アンド・スイープを行う場合の処理手順を、図４を用いて説明する。
【００５４】
図３の初期状態のグラフにおいて、左端のオブジェクト２００を仮に解放できたとすると、その両隣のオブジェクト２０１，２０２の参照カウントＡがそれぞれ１減少し、図４のステップ１のグラフのようになる。続いて、オブジェクト２００の参照先である両隣のオブジェクト２０１，２０２を解放できたとすると、図４のステップ２のグラフのようになる。オブジェクト２０１，２０２の両方から参照されていたオブジェクト２００の参照カウントＢが１ずつ（合計で２）減少し、オブジェクト２０１，２０２の右隣のオブジェクトであるオブジェクト２０３，２０４の参照カウントＡが１ずつ減少する。
【００５５】
この手順を同様に図４のステップ３、ステップ４と繰り返して行くと、最終的にオブジェクト２０５が解放できたとした場合に、全てのオブジェクトの参照カウントが０になる。連結されたオブジェクト群が循環参照となっていない場合と、循環参照以外のオブジェクトから参照されるオブジェクトを含んでいる場合は、到達可能な全てのオブジェクトについて同様な手順を繰り返しても、最後に参照カウントが０とはならないオブジェクトが残ることになる。そのため、全ての参照カウントが０になったとき、これらのオブジェクト群が循環参照をなすガベージ群であることがわかる。
【００５６】
この手順を、左端のオブジェクト２００と同様に、循環参照の候補である右端のオブジェクト２０５を起点として行った場合も、前記と同じく全てのオブジェクトの参照カウントが０になるので、循環参照をなすガベージ群として解放することが可能である。
【００５７】
図５は、３つの循環参照が重なっている場合の例を示す有向グラフである。図５のグラフの中央部に存在する循環参照のように、別の循環参照と重なっている場合は、参照カウントＡおよびＢの一方が０であるオブジェクトを含まない循環参照が存在しうる。ただし、この場合も、重なり合った複数の循環参照を１つの複合的な循環参照と捉えた場合、その左端と右端とには、必ず参照カウントＡとＢとの一方が０になっているオブジェクト３００，３０１が存在しており、これらのオブジェクトを循環参照を探索するための起点として前記と同様に部分的マーク・アンド・スイープを実行することで、複合的な循環参照の全てを検出してガベージ群を解放することができる。
【００５８】
図６は、やや複雑に循環参照が重なっている場合における循環参照の探索手順の例を示した説明図である。ここでは、図６の初期状態のグラフの中で循環参照の候補となる３つのオブジェクト４００，４０３，４０４のうち、オブジェクト４００を起点として循環参照を探索する例を示している。
【００５９】
まず始めに、初期状態のグラフからオブジェクト４００が解放できたと仮定して、その参照先であるオブジェクト４０１，４０２の参照カウントＡを１ずつ減らすと、ステップ１のグラフのようになる。次に、ステップ１のグラフのオブジェクト４０１，４０２の共通の参照先であるオブジェクト４０３の参照カウントＡを２だけ減らし、オブジェクト４０２の参照先であるオブジェクト４０４の参照カウントＡを１だけ減らすと、ステップ２のグラフのようになる。次に、ステップ２のグラフのオブジェクト４０３の３つの参照先であるオブジェクト４００，４０１，４０４の参照カウントＡまたはＢを１ずつ減らし、オブジェクト４０４の参照先であるオブジェクト４０２の参照カウントＢを１だけ減らすと、ステップ３のグラフのようになる。
【００６０】
その結果、ステップ３のグラフにおいて、最終的に全てのオブジェクトの参照カウントが０となり、これら循環参照をなすガベージ群を解放することができる。
【００６１】
これに対して、図７は、連結されたオブジェクト群が循環参照となっていない場合の処理の例を示した説明図である。図７の初期状態のグラフは、図６の初期状態に他のオブジェクトからの参照を表すエッジ４０５が追加され、オブジェクト４０１の参照カウントＢが２となっている。このような外部から参照されるオブジェクトを含む場合は、循環参照が孤立しておらずガベージではないので解放してはならない。
【００６２】
図７の初期状態のグラフについて、図６の場合と同様に、オブジェクト４００を起点として循環参照の探索を行うと、エッジ４０５で示される外部参照が存在するため、最終的にステップ３のグラフにおいてオブジェクト４０１の参照カウントＢが１となる。このように、参照関係を辿って到達可能な全てのオブジェクトの中に、参照カウントが０にならなかったオブジェクトが存在していた場合は、それらのオブジェクト群はガベージではないことがわかるので、オブジェクトの解放を行わずに減少させた参照カウントを図７の初期状態の値に復元する。
【００６３】
このように、いかなる循環参照の形においても、参照カウントＡとＢとの一方が０であり、かつ他のオブジェクトを参照しているオブジェクトを、循環参照の候補とすれば良いことが言える。また、従来のように全オブジェクトに対するマーク・アンド・スイープを一括して実行する必要がない、部分的なマーク・アンド・スイープによって個別に循環参照を探索してガベージ群を解放できるので、ガベージ・コレクションに伴う他のプログラムの停止時間を短縮することができる。
【００６４】
以上にて本発明を実施するための形態の説明を終えるが、本発明の実施の態様はこれに限られるものではなく、本発明の趣旨を逸脱しない範囲内で各種の変更が可能である。例えば、オブジェクト順序付けには識別子の値を用いたが、オブジェクトの生成時刻や割り当てられたメモリ領域のアドレスなど、一意に順序付けを行うことができる他の任意の属性値を用いることができる。また、２つの参照カウントのどちらかが０であるオブジェクトを循環参照の候補としたが、選択したいずれか一方の参照カウントが０であるオブジェクトだけを候補とするようにしてもよい。
【符号の説明】
【００６５】
１０  言語処理プログラム
２０  プログラム実行制御部
３０  参照カウント更新部
４０  循環参照検出部
５０  メモリ領域解放部
６０  ユーザプログラム
１００  記憶部（メモリ領域）
１１０，１２０，１３０  オブジェクト
１１１，１２１，１３１  参照カウントＡ（２つの参照カウント）
１１２，１２２，１３２  参照カウントＢ（２つの参照カウント）
１４０  オブジェクトの参照リスト
１５０  循環参照の候補リスト
【図１】
2011257900.tif 000003
【図２】
2011257900.tif 000004
【図３】
2011257900.tif 000005
【図４】
2011257900.tif 000006
【図５】
2011257900.tif 000007
【図６】
2011257900.tif 000008
【図７】
2011257900.tif 000009