(57)【要約】【課題】処理の応答性を確保するためにスレッド固有領域ごとにガーベージコレクションすると、領域の断片化や、プログラムの実行の進行に伴い、回収可能な領域が減少するという問題が生じる。【解決手段】スレッド固有のデータを配置する領域と、他のスレッドから参照される可能性のあるデータを配置する領域とを分けて管理することにより課題を解決できる。具体的には、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置する。【選択図】図１
2009037546.tif 000002
【特許請求の範囲】
【請求項１】
プログラムに対応して生成され、平行動作する一つ以上のスレッドの各々に対応するスレッド固有領域と前記スレッドが共有する大域領域とをメモリに設け、
前記スレッドの各々が固有に参照するデータを前記対応するスレッド固有領域に配置し、
前記スレッドの各々以外から参照されるデータを前記大域領域に配置するメモリ管理方法。
【請求項２】
前記スレッド固有領域に配置したデータが、前記スレッドの各々以外から参照される場合、前記参照に先立って、前記スレッド固有領域に配置したデータを前記大域領域に移動する請求項1記載のメモリ管理方法。
【請求項３】
前記スレッドの各々以外のスレッドの実行状態を維持したままで、前記スレッドの各々に対応するスレッド固有領域のガーベージコレクションを実行する請求項1記載のメモリ管理方法。
【請求項４】
データを前記スレッド固有領域および前記大域領域のいずれに配置するかを前記プログラムによって決定する請求項1記載のメモリ管理方法。
【請求項５】
プログラムに対応して生成された一つ以上のスレッドの各々に対応するスレッド固有領域と前記スレッドが共有する大域領域とを設けたメモリ、および
前記スレッドの各々を平行動作させ、前記動作に伴って、前記スレッドの各々が固有に参照するデータを前記対応するスレッド固有領域に配置し、前記スレッドの各々以外から参照されるデータを前記大域領域に配置するプロセッサを有するコンピュータ。
【請求項６】
前記プロセッサは、前記スレッド固有領域に配置したデータが、前記スレッドの各々以外から参照される場合、前記参照に先立って、前記スレッド固有領域に配置したデータを前記大域領域に移動する請求項５記載のコンピュータ。
【請求項７】
前記プロセッサは、前記スレッドの各々以外のスレッドの実行状態を維持したままで、前記スレッドの各々に対応するスレッド固有領域のガーベージコレクションを実行する請求項５記載のコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムを並行動作させる機能を備えたコンピュータにおけるメモリ管理方法およびそのコンピュータに関する。
【背景技術】
【０００２】
サーバにより実行されるアプリケーションプログラム（業務プログラム）などのように、外部からのリクエストの受け付けに応じて処理するシステムでは、受付に対応した処理は、スレッドと呼ばれる単位に分けられ、複数のスレッドが並行に実行される。スレッドとは逐次的な実行単位であり、プログラムを構成するスレッドは記憶領域を共有するという特徴を持つ。
【０００３】
このようなアプリケーションプログラムの作成にはJava（Javaは、米国  Sun Microsystems，Inc．の商標である。）などのオブジェクト指向プログラミング言語が用いられる。このような最近のプログラミング言語では、動的に割り当てたメモリ領域のうち、以降のプログラム実行に不要であるようなものをシステム（Javaの場合、ランタイムシステム、Java仮想マシン、実行環境などと呼ばれる。）が判断して、自動的に回収（collection）するガーベージコレクション(GCと略す。)するメモリ管理が採用されている。
【０００４】
一般に利用されているGCでは、実行中のスレッドを全て停止させて、メモリ領域を回収することが多い。これは、GCによる回収作業中に実行中のスレッドが存在すると、回収対象領域が実行中のスレッドによって使用中か否かを判定する必要があるが、その判定が困難であることによる。
【０００５】
GCの際に実行中のスレッドを停止させることは、処理の応答性の低下を意味する。したがって、オンライン・トレーディング・システムのような応答性が重要となるアプリケーションでは、このようなスレッドの停止時間の発生が重要な問題となる。
【０００６】
GCによるプログラムの停止を回避するための技術として、スレッド毎にデータを格納する固有領域(thread-local heap)をランタイムシステムが用意し、あるスレッドの固有領域をGCする際に、他のスレッドを停止しない方法が提案されている(非特許文献1)。この方法では、固有領域内の個々のデータに他のスレッド（のデータ、オブジェクト）からの参照が可能である場合にフラグを設定することで、フラグが設定されていないデータを対象にスレッド個別のGC処理を実行する。あるデータを他のスレッドから参照可能な状態になる前に、そのデータを生成したスレッドがフラグを設定する。他のスレッドから参照される可能性のあるデータはフラグ付けにより識別されるので、固有領域に対応するスレッドのみから参照されるデータを識別でき、そのようなデータのうち以降のプログラム実行に不要なデータに関しては他のスレッドの動作を考慮することなく回収することができる。
【０００７】
【非特許文献１】T. Domani他, Thread-Local Heaps for Java, In Proceedings of the International Symposium on Memory Management, 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
各スレッド対応の固有領域を対象にした既存のGCでは、あるスレッド対応の固有領域に存在するデータで、他のスレッド（のデータ、オブジェクト）から参照可能なデータにフラグを設定し、印（フラグ）付けされていないデータのうち、以降のプログラム実行に不要なデータを回収する。この時、印付けされたデータは回収できないだけでなく、固有領域内の他の領域へ移動することもできない。これは、固有領域の回収処理の実施中（GC中）に当該固有領域にある印付けされたデータを他のスレッドが参照する可能性があるためである。データを固有領域内で移動できないという制約により、回収されたメモリ領域の断片化が生じる。回収されたメモリ領域、すなわち空き領域が細切れになる。また、印付けされたデータは増加するため、プログラムの実行が進むにつれてスレッド固有領域中の回収可能な領域は減少することとなり、後々は、スレッド対応の固有領域のGCを実施できなくなる。このような場合には、関連するスレッドをすべて停止させて、これらのスレッドに対応する固有領域をGCすることになる。
【０００９】
以上のように、処理の応答性を確保するために、他のスレッドが参照する可能性があるデータを除いてスレッド固有領域ごとにGCすると、領域の断片化が生じるという問題と、プログラムの実行が進行することにより回収可能な領域が減少するという他の問題が生じる。
【課題を解決するための手段】
【００１０】
本発明は、スレッド固有のデータ（オブジェクト）を配置する領域と、他のスレッドから参照される可能性のあるデータを配置する領域とを分けて管理するところに特徴がある。
【００１１】
本発明の一つの態様は、プログラムに対応して生成され、平行動作する一つ以上のスレッドの各々に対応するスレッド固有領域とスレッドが共有する大域領域とをメモリに設け、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置するメモリ管理方法である。
【００１２】
本発明の他の態様は、スレッド固有領域に配置したデータが、スレッドの各々以外から参照される場合、その参照に先立って、参照される可能性のあるデータを大域領域に移動するメモリ管理方法である。
【００１３】
本発明のさらに他の態様は、プログラムに対応して生成された一つ以上のスレッドの各々に対応するスレッド固有領域とスレッドが共有する大域領域とを設けたメモリ、およびスレッドの各々を平行動作させ、この動作に伴って、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置するプロセッサを有するコンピュータである。
【発明の効果】
【００１４】
スレッド固有のデータを配置する領域（スレッド固有領域）と、他のスレッドから参照される可能性のあるデータを配置する領域（大域領域）とを分けて設けたことにより、スレッド固有領域対応にガーベージコレクションを実行することができ、領域の断片化を回避できる。さらに本発明のある態様によれば、大域領域に他のスレッドから参照される可能性のあるデータを配置することにより、プログラムの実行が進行することにより回収可能な領域が減少するという問題を解決できる。さらに本発明の他の態様によれば、スレッド固有領域対応のガーベージコレクションの実行時に、他のスレッドの実行状態を維持するので、処理の応答性を確保できる。
【発明を実施するための最良の形態】
【００１５】
本発明を実施するための最良の形態は、スレッド固有のデータ（オブジェクト）を配置する領域と、他のスレッドから参照される可能性のあるデータを配置する領域とを分けるところにある。
【００１６】
本発明を実施するための具体的な形態は、プログラムに対応して生成され、平行動作する一つ以上のスレッドの各々に対応するスレッド固有領域とスレッドが共有する大域領域とをメモリに設け、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置するメモリ管理方法である。
【００１７】
さらに、スレッド固有領域に配置したデータが、スレッドの各々以外から参照される場合、その参照に先立って、参照される可能性のあるデータを大域領域に移動するところにある。
【００１８】
本発明を実施するための他の具体的な形態は、プログラムに対応して生成された一つ以上のスレッドの各々に対応するスレッド固有領域とスレッドが共有する大域領域とを設けたメモリ、およびスレッドの各々を平行動作させ、この動作に伴って、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置するプロセッサを有するコンピュータである。
【実施例１】
【００１９】
以下、本発明の一実施例について図面を参照して説明する。
【００２０】
図1は、コンピュータ上に実現される、一般に言語処理系105と呼ばれる構成図である。たとえばJavaのようなオブジェクト指向プログラミング言語で記述されたソースプログラム104はコンパイラ106によって中間コード（Javaの場合はバイトコードと呼ばれる。）107に変換される。中間コード107はランタイムシステム108（Javaの場合はJava仮想マシン（JavaVM）、Java実行環境などと呼ばれる。）にあるインタプリタ111によって解釈され、実行される。インタプリタ111により、その都度、中間コードを解釈、実行する場合だけでなく、JITコンパイラ（Just-In-Time Compiler）により機械語プログラム109への変換が用いられる場合もある。ランタイムシステム108は、機械語への変換および実行を仮想化しているのであって、ユーザにとってはランタイムシステム108上でプログラムが実行されているように見える。
【００２１】
ランタイムシステム108は、一つのプログラムについて1つ以上のスレッド（実行単位）101を生成する。またスレッド101を生成に対応して各スレッド101に対応したスレッド固有領域102を生成する。スレッド固有領域102は、スレッドの実行に伴って生成されるデータ（オブジェクト）を格納する領域である（領域にオブジェクトを生成するという表現もある。）。本実施例では、各スレッド101が共有してデータを格納、参照する大域領域103も生成する。協調して動作すべきプログラムは一つのランタイムシステム108の上で実行される。したがって大域領域103はランタイムシステム108に対応して設けられる。各スレッド固有領域102および大域領域103は、ランタイムシステム108のガーベージコレクタ110によるガーベージコレクションの対象になる。ガーベージコレクションとは、プログラム（スレッド）が使用しなくなったメモリ領域を新たに利用可能にすることや、データ（プログラムも含む）間の隙間のメモリ領域（断片化したメモリ領域）を集めて、連続して利用可能なメモリ領域を増やすことである。
【００２２】
なお、各スレッド固有領域102および大域領域103を対象にガーベージコレクションするガーベージコレクタ110は、ランタイムシステム108に組み込まれている（ランタイムシステム108によって実行される。）ので、ガーベージコレクションを実行するタイミングをプログラムから制御できない。
【００２３】
図2に言語処理系105およびその動作に必要な記憶領域等のコンピュータ200上の構成を示す。図2は本実施例を説明するために必要な構成を示すものであり、パーソナルコンピュータや携帯機器のようなプラットホームであっても良いことは当業者にとっては自明であろう。
【００２４】
図2に示すコンピュータ200は、CPU（プロセッサ）201、メモリ202およびディスク装置などの外部記憶装置204がバス203などで接続されている。メモリ202には、ソースプログラム104および中間コード107が格納され、スレッド固有領域102および大域領域103が確保される。ソースプログラム104および中間コード107はコンピュータ200の構成、メモリ202の容量、実行環境（ランタイムシステム108）の仕様などに応じて、外部記憶装置204に格納される場合もある。
【００２５】
CPU201では、OS205上でランタイムシステム108およびコンパイラ106が動作する。OS205、ランタイムシステム108およびコンパイラ106は、メモリ202または外部記憶装置204に格納されており（図示略）、CPU201によって実行される。図2のCPU201部分は、実行されるプログラム構成を示している。ランタイムシステム108の機能であるインタプリタ111およびガーベージコレクタ110を含めたコンピュータ200の動作説明は、図1で説明した内容に重複するので省略する。
【００２６】
図3および図4を用いて、大域領域103の有用性を明らかにするために、大域領域103を設けない場合について説明する。ここでは説明を単純にするために、スレッド（＃1）301に対応するスレッド固有領域（＃1）303、およびスレッド（＃2）302に対応するスレッド固有領域（＃2）304について説明する。
【００２７】
スレッド固有領域303にはデータ（オブジェクト）307〜310が存在し、スレッド固有領域304にはデータ305, 306が存在する。図中ではデータを丸で示す。データ間の実線矢印はデータ間の参照関係を表わし、破線矢印は実行中の命令により作成されようとしている参照関係を表わす。矢印の元が参照元、矢印の先が参照先を表す。網掛け（ハーフトーン）の丸は、他のスレッド固有領域に存在するデータから参照されているデータを表す。これを大域データと呼ぶことにする。図3では、スレッド固有領域303中のデータ310から、スレッド固有領域304中のデータ306への参照311が存在するため、参照先のデータ306は大域データである。
【００２８】
図3では、スレッド固有領域304のデータ305からスレッド固有領域303のデータ307への参照312を作成しようとしている。図4は参照312を作成した後の状態を表す。参照312の作成に応じて、参照先データ307とそこから到達可能なデータ308が大域データとして印付けされる。到達可能とは参照関係のチェーンがあることを意味する。印付けされた大域データは、他のスレッド固有領域にあるデータから参照される可能性があることから、ガーベージコレクタ110によるガーベージコレクションの対象外としなければならない。すなわち、スレッド固有領域303のデータ307, 308およびスレッド固有領域304のデータ306は、回収（データを削除し、そのデータ格納領域を新たに利用可能にすること）および移動の対象外である。印付けされた大域データは、実行中の他のスレッド固有領域にあるデータから参照される可能性があるので、スレッド固有領域内であっても、移動することはできない。
【００２９】
図5はスレッド固有領域に新たに利用可能な領域、すなわち空き領域の断片化の発生を示す図である。図5ではスレッド501に対応したスレッド固有領域502を示し、この固有領域502中に大域データ503と空き領域（未使用の領域またはデータ回収した領域）504が存在していることを示している。ここでは、スレッド固有領域502中に空き領域504が、データ回収（ガーベージコレクション）の結果、非連続的に存在しているが、前述したように大域データ503を移動できないために、断片化した空き領域を結合して大きなデータ格納領域に纏めることができない。一般にコンパクションやデフラグと呼ばれる処理を実行できない。
【００３０】
図6は、スレッド601に対応したスレッド固有領域602が大域データ603によって一杯になった状態を示している。スレッド固有領域602中の大域データは局所的な回収対象とならないため（スレッド固有領域のデータ回収の対象から大域データは除外されるため）、全てのスレッドを停止した状態で回収処理を行う必要がある。
【００３１】
図3〜図6を用いて説明した、スレッド固有領域に空き領域（利用可能な領域）の断片化が生じるという問題、および回収可能な領域が減少するという問題を解決するための処理について、図10〜図12を用いて説明する。
【００３２】
図10は、インタプリタ111の処理における1つの命令の解釈実行部分を示す。命令セットや命令の形式については、言語の種別や実行環境に応じて変更する必要があるが、ここでは関知しない。
レジスタPCが指示する命令は「obj1.f=obj2」というポインタストア命令であるか否かをチェックする（ステップ1000）。レジスタPCには、次に実行すべき命令（中間コード）の格納アドレスが格納されている。「obj1.f=obj2」は、ポインタobj1が示すデータが、ポインタobj2が示すデータを参照していることを意味している。ここで言うポインタはメモリ202のアドレスや予め定めた基点からの相対アドレスであっても良い。チェックの結果、命令がポインタストア命令でない場合はステップ1040に分岐し、既存の命令解釈実行処理を実行して終了する。
【００３３】
チェックの結果、命令がポインタストア命令である場合、ポインタobj1が示すデータが大域領域103に配置され、ポインタobj2が示すデータがスレッド固有領域102に配置されているか否かをチェックする。すなわち、obj1が大域領域103中を示すポインタであり、obj2がスレッド固有領域102中を示すポインタであるか否かをチェックする（ステップ1005）。否の場合、ステップ1040に分岐し、既存の命令解釈実行処理を実行して終了する。ここで「isGlobal(obj)」はポインタobjが示すデータが大域領域103に配置されていることを確認するための関数、「isLocal(obj)」はポインタobjが示すデータがスレッド固有領域102に配置されていることを確認するための関数であるものとする。
【００３４】
チェックの結果、判定が成立する場合、大域領域103に配置されたポインタobj1が示すデータが、スレッド固有領域102に配置されたポインタobj2が示すデータを参照していることを示す。したがって、ポインタobj2が示すデータは、スレッド間で共有される可能性があるために、大域領域103に移動する必要がある。
【００３５】
そこで、移動対象のポインタobj2が示すデータから到達可能なデータの集合Sを求める（ステップ1010）。到達可能とは、前述したように、参照関係のチェーンがあることを意味する。所属するスレッドグループ中のスレッドの実行を停止する（ステップ1015）。スレッドグループとは、ここではスレッド固有領域102を共有するスレッド群、すなわち一つのランタイムシステム108上で動作する複数のスレッドである。
【００３６】
スレッドグループはアプリケーションの性格により、次のような場合もあることは当業者であれば容易に推測できるであろう。ランタイムシステム108上で動作するスレッドに対応するプログラムがいくつかのグループを構成し、このプログラムグループ対応のスレッド群に固有領域が設けられ、それらのスレッド群が共有する大域領域が設けられる場合がある。また、ランタイムシステム108上で動作するスレッドに対応するプログラムがいくつかのグループを構成し、各スレッド対応に固有領域が設けられ、プログラムグループに対応して大域領域が設けられ、さらに各大域領域のデータ間で参照関係がある場合に階層的に上位階層の大域領域を設ける場合もある。さらに、複数のランタイムシステムに跨って、大域領域を設ける場合があっても良い。これらは、アプリケーションの性格により、適宜選択されるものであり、技術思想は共通していることは容易に推測されるものである。
【００３７】
次に、集合Sに含まれるデータを大域領域103に移動し、ポインタobj2が示すデータの移動先のポインタをobj2'とする（ステップ1020）。停止したスレッドの実行を再開し（ステップ1025）、ポインタobj1が示すデータが参照しているデータのポインタとして、obj2の代わりにobj2'を代入する（ステップ1030）。
【００３８】
スレッド固有領域102中のデータは対応するスレッドグループ内のスレッドのデータのみから参照可能である。一つのスレッド対応にスレッド固有領域102を設けた場合は、そのスレッドのデータのみから参照可能である。一方、大域領域103中のデータは、大域領域103を共有する他のスレッドのデータから参照可能である。したがって、ポインタobj1が示すデータからポインタobj2が示すデータを参照する場合、ポインタobj1が示すデータから直接的または参照関係のチェーンにより間接的に参照されたデータが他のスレッドのデータから参照可能となる。よって、他のスレッドのデータから参照される可能性のあるデータを、他のスレッドのデータから参照される前に、スレッド固有領域102から大域領域103へ移動することにより、スレッド固有領域102中のデータが対応スレッド以外のスレッドから参照されないことを保証できる。
PCを次に実行すべき命令のアドレスに更新し（ステップ1035）、1つの命令の解釈実行処理を終了する。
図10のステップ1040がランタイムシステム108に含まれる既存のインタプリタ処理であるので、図10の他のステップはステップ1040の前段で実行できるように構成することができる。以上の処理により、他のスレッドまたは他のスレッドグループに属するスレッドのデータから参照される可能性のあるデータを大域領域103に移動するので、スレッド固有領域102に対するガーベージコレクションの機能（データの回収および利用可能な領域の断片化の解消）を十分に発揮させるようにできる。
【００３９】
図11を参照して、図10のステップ1020、集合Sに含まれるデータの大域領域103に移動について説明する。大域領域103に移動するデータの集合Sが空集合（φ）か否かをチェックする（ステップ1100）。空集合ならば、移動すべきデータが存在しないため、処理を終了する。集合Sが空集合でない場合、集合Sからデータを1つ選択し、そのデータのサイズに相当する領域を大域領域103に確保し、確保した領域を示すポインタをnとする（ステップ1105）。ポインタnが示す領域に、移動すべきデータの集合Sから選択したデータを移動する（ステップ1110）。
次に、ステップ1110で移動したデータを参照している参照の集合Pを求める（ステップ1115）。参照の集合Pが空集合（φ）か否かをチェックし（ステップ1120）、参照の集合Pが空集合ならば、移動すべきデータとして選択したデータの移動に伴って変更すべき参照が存在しない（移動したデータへの参照のチェーンが存在しない。）ので、ステップl100へ分岐し、移動すべき次のデータを処理する。参照の集合Pが空集合でないならば、参照の集合Pから参照を1つ選択して、選択した参照をpとする（ステップ1125）。参照pが示すデータの参照先をnに変更し（ステップ1130）、ステップ1120へ分岐する。
【００４０】
図12にランタイムシステム108における、スレッド固有領域102および大域領域103へのメモリ割り当て処理を示す。説明中の対象領域は個々のスレッド固有領域102または大域領域103である。
【００４１】
対象領域の空き領域のサイズが予め定めた閾値以下であるか否かをチェックする（ステップ1200）。閾値は対象領域によって異なっても良い。特に、大域領域103の閾値は、スレッド固有領域102の閾値と異なることがある。否の場合、ステップ1230へ分岐する。
【００４２】
閾値以下である場合、対象領域に対応したスレッドグループの各スレッドを停止する（ステップ1205）。スレッドグループを構成する各スレッドから到達可能なデータに印を付ける（ステップ1210）。なお、ここでの印は、データが複数のスレッドから参照可能であることを表すフラグとは異なることに注意されたい。次に、印付けされていないデータを以降のプログラム実行に不要なデータ領域として回収する（ステップ1215）。これは、各スレッドから到達できないデータは以降のプログラム実行に際して参照できない、すなわち、未使用領域であることによる。回収した領域を含めた未使用領域をまとめる（ステップ1220）。言い換えると、対象領域に残っているデータを対象領域内で移動し、空き領域をまとめる。スレッドグループ内のスレッドの実行を再開する（ステップ1225）。
【００４３】
対象領域への領域追加の要否をチェックし（ステップ1230）、必要であれば、領域を追加割り当てする（ステップ1235）。なお、対象領域への領域追加を前提に図12の処理が実行される場合は、ステップ1230のチェックは不要である。
【００４４】
図7および図8を用いて、図10および図11の処理の具体例を説明する。図7および図8は、スレッド（＃1）701およびスレッド（＃2）702に対応するスレッド固有領域703および 704と大域領域705へのデータの配置を表わしている。複数のスレッド701、702で共有されるデータ707は大域領域705へ配置されている。図中ではデータを丸で示す。データ間の実線矢印はデータ間の参照関係を表わし、破線矢印は実行中の命令により作成されようとしている参照関係を表わす。矢印の元が参照元、矢印の先が参照先を表す。網掛け（ハーフトーン）の丸は、他のスレッド固有領域に存在するデータまたは大域領域に存在するデータから参照されている大域データを表す。
【００４５】
図7の大域領域705に配置されたデータ706から、スレッド701に対応したスレッド固有領域703中のデータ708への参照711を作成する場合を例に説明する。図10のステップ1000におけるPCが指示する命令が、「obj1.f=obj2」であるとし、obj1がデータ706を示すポインタ、obj2がデータ708を示すポインタであるとする。このとき、ステップ1000の判定は成立する。ポインタobj1の示すデータ706が大域領域705、ポインタobj2の示すデータ708がスレッド固有領域703に配置されていることから、ステップ1005の判定も成立する。ステップ1010で、ポインタobj2が示すデータ708から到達可能なデータ集合（データ708自身を含む。）を求めると、S={708,709}が得られる。ステップ1015で、大域領域705を共有するスレッド701およびスレッド702を停止する。ステップ1020で、集合Sに含まれるデータ708およびデータ709を大域領域705へ移動する。
【００４６】
図11のステップ1100で、移動対象のデータ集合S={708,709}は空集合でないため、移動すべきデータとして、データ708を選択し、データ708と同サイズのデータ領域を大域領域705に確保し、そのポインタをnとする。データ708をポインタnが示す領域に移動し、移動したデータを813とする。すなわち、ポインタnが示すデータがデータ813になる。
【００４７】
ステップ1115で、移動したデータ708を参照している参照の集合Pを求めると、図7および図8では参照の集合P={711、713}である。ステップ1120で、参照の集合Pは空集合ではないので、ステップ1125で参照の集合Pから1つの参照pを選択する。ここでは選択したポインタをｐ＝711とする。データ706からデータ708への参照711をデータ813への参照に変更する。ステップ1120へ戻り、選択した参照をp=713とする。参照713が示すデータは移動したデータ708であるので、ステップ1130で参照713をデータ708の移動後のデータ813を示すポインタｎに対応する参照へ変更する。すなわち参照713を、データ813を示す参照815へ変更する。ステップ１１２０に戻ると、参照の集合Pは空集合であるので、次の移動すべきデータ709について、ステップ1100から処理を繰り返す。
【００４８】
図9は、空き領域の断片化への対応を示す。図9ではスレッド901に対応したスレッド固有領域902が存在し、このスレッド固有領域中にデータ903〜904と空き領域905が存在する。図９(a)は、図12のステップ1215によりデータの領域が回収され、空き領域が断片化している状態を示す。ステップ1220の実行により、空き領域がまとめられた、言い換えると、対象領域に残っているデータを対象領域内で移動した状態を図9(b)に示す。
【００４９】
本実施例によれば、スレッド固有のデータを配置する領域（スレッド固有領域）と、他のスレッドから参照される可能性のあるデータを配置する領域（大域領域）とを分けて設けたことにより、スレッド固有領域対応にガーベージコレクションを実行することができ、領域の断片化を回避できる。
【００５０】
さらに本実施例によれば、大域領域に他のスレッドから参照される可能性のあるデータを配置することにより、プログラムの実行が進行することにより回収可能な領域が減少するという問題を解決できる。
【００５１】
さらにスレッド固有領域対応のガーベージコレクションの実行時に、他のスレッドの実行状態を維持することにより、処理の応答性を確保できる。
【実施例２】
【００５２】
図10に示す命令実行処理では、大域領域103中のデータから固有領域102中のデータへの参照を作成する場合に、ステップ1020で参照されるデータの移動が発生する。このデータの移動が頻繁に発生する場合は、予め大域領域103に参照されるデータを配置しておくと、データ移動のオーバーヘッドが削減できる。
【００５３】
図13に大域領域103へのデータの配置とスレッド固有領域へのデータの配置とを切り替える処理を示す。配置対象データの型は大域領域103へ配置の型か否かをチェックする（ステップ1300）。大域領域103へ配置の型であれば、大域領域103へ配置し（ステップ1305）、否であれば、スレッド固有領域102へ配置する（ステップ1310）。
【００５４】
ステップ1300において、対象データの型が大域領域配置か否かは、オプションやプログラム上でのユーザ指示、プログラム解析によって大域データへの参照が生じるか否か、実行時プロフィールの解析結果などによって実現することができる。プログラム上でのユーザ指示の例を図14に示す。この例では、クラスCへの属性指定1400によりクラスCが大域領域配置であることを指示している。
【００５５】
本実施例によれば、スレッドの実行に伴うデータの配置領域を、プログラムからの指示などのように外的に決定できるので、データ移動のオーバーヘッドを削減しようとする、プログラム設計者、プログラム作成者の意図に応じたデータ配置が可能になる。
【図面の簡単な説明】
【００５６】
【図１】コンピュータ上に実現される言語処理系の構成図である。
【図２】言語処理系のコンピュータ上の構成図である。
【図３】スレッド固有領域へのデータ配置の例である。
【図４】スレッド固有領域へのデータ配置の例である。
【図５】スレッド固有領域の空き領域の断片化の例である。
【図６】回収可能領域がないスレッド固有領域の例である。
【図７】大域領域を設けた場合のデータ配置の例である。
【図８】大域領域を設けた場合のデータ移動の例である。
【図９】スレッド固有領域の空き領域の断片化を回避する例である。
【図１０】命令の解釈実行処理を示す図である。
【図１１】データの大域領域への移動処理を示す図である。
【図１２】スレッド固有領域および大域領域への領域割当て処理を示す図である。
【図１３】データ配置領域の切り替え処理を示す図である。
【図１４】大域領域配置を指定するプログラム例である。
【符号の説明】
【００５７】
101…スレッド、102…スレッド固有領域、103…大域領域、104…プログラム、105…言語処理系、106…コンパイラ、107…中間コード、108…ランタイムシステム、109…機械語プログラム、110…ガーベージコレクタ、111…インタプリタ、200…コンピュータ、201…CPU、202…メモリ。
【図１】
2009037546.tif 000003
【図２】
2009037546.tif 000004
【図３】
2009037546.tif 000005
【図４】
2009037546.tif 000006
【図５】
2009037546.tif 000007
【図６】
2009037546.tif 000008
【図７】
2009037546.tif 000009
【図８】
2009037546.tif 000010
【図９】
2009037546.tif 000011
【図１０】
2009037546.tif 000012
【図１１】
2009037546.tif 000013
【図１２】
2009037546.tif 000014
【図１３】
2009037546.tif 000015
【図１４】
2009037546.tif 000016