(57)【要約】【課題】コンパクションを不要とし、且つメモリの使用効率を向上させることにある。【解決手段】メモリのヒープ領域内に生成されたオブジェクトの特性を検知する特性検知手段と、前記特性検知手段が検知した特性に応じて、前記ヒープ領域に対する当該オブジェクトの割り当てを決定する割当決定手段と、を設けている。これにより、オブジェクトのサイズや、オブジェクトの寿命等に応じてヒープ領域に対する当該オブジェクトの割り当てを決定することができ、メモリの使用効率の向上が図れる。【選択図】図３０
2006185456.tif 000002
【特許請求の範囲】
【請求項１】
メモリのヒープ領域内に生成されたオブジェクトの特性を検知する特性検知手段と、
前記特性検知手段が検知した特性に応じて、前記ヒープ領域に対する当該オブジェクトの割り当てを決定する割当決定手段と、を設けたことを特徴とするメモリ割当装置。
【請求項２】
前記特性検知手段は、前記ヒープ領域内に割り当てられるオブジェクトのサイズの分布を検知する手段であり、
前記割当決定手段は、前記分布の中心より大きな固定サイズの整数倍を前記ヒープ領域に対する新たなオブジェクトの割り当てサイズに決定する割当サイズ決定手段を含む請求項１に記載のメモリ割当装置。
【請求項３】
前記特性検知手段は、システムの使用開始時にシステムに組み込まれ、前記オブジェクトのサイズの分布を検知した後にシステムから切り離されるプログラムモジュールによるものである請求項２に記載のメモリ割当装置。
【請求項４】
前記割当サイズ決定手段は、システムの使用開始時にシステムに組み込まれ、前記固定サイズが決定された後にシステムから切り離されるプログラムモジュールによるものである請求項２に記載のメモリ割当装置。
【請求項５】
前記ヒープ領域内を予め複数のサイズに分割するヒープ領域分割手段と、
オブジェクト生成時に当該オブジェクトのサイズより大きく且つ最も小さなサイズの領域を割り当てる手段を設けたことを特徴とする請求項２に記載のメモリ割当装置。
【請求項６】
前記ヒープ領域分割手段は、前記複数のサイズの分割数と各サイズを引数とするアプリケーションプログラムインタフェースの呼び出しによって、前記ヒープ領域を分割する手段である請求項５に記載のメモリ割当装置。
【請求項７】
アプリケーションプログラムインタフェースの呼び出しによって前記固定サイズを設定する手段を設けたことを特徴とする請求項２に記載のメモリ割当装置。
【請求項８】
クラスからオブジェクトが生成された時刻に相当するデータを記憶し、前記オブジェクトを削除する際に、当該オブジェクトの寿命を検出し、該寿命のデータをクラスに設ける手段を備え、
前記特性検知手段は、クラスから生成されたオブジェクトの寿命を検知する手段であり、
前記割当決定手段は、前記特性検知手段により検知されたオブジェクトの寿命に基づいて、このオブジェクトに割り当てる、前記ヒープ領域に対するオブジェクトの生成領域を決定する手段である請求項１に記載のメモリ割当装置。
【請求項９】
メモリのヒープ領域内に生成されたオブジェクトの特性を検知する第１のステップと、
前記第１のステップが検知した特性に応じて、前記ヒープ領域に対する当該オブジェクトの割り当てを決定する第２のステップと、をコンピュータに実行させるメモリ割当方法。
【請求項１０】
メモリのヒープ領域内に生成されたオブジェクトの特性を検知する第１のステップと、
前記第１のステップが検知した特性に応じて、前記ヒープ領域に対する当該オブジェクトの割り当てを決定する第２のステップと、をコンピュータに実行させる処理プログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータのメモリ割当装置、メモリ割当方法、およびプログラム記録媒体に関する。
【背景技術】
【０００２】
先ず、本願発明の明細書において用いる各種用語の定義を以下に示す。尚、出典記号は次のとおりである。
【０００３】
ＪＩＳ：ＪＩＳ工業用語大辞典第４版（日本規格協会刊）
参１：情報技術用語事典（オーム社刊）
参２：情報処理用語大事典（オーム社刊）
参３：先端ソフトウエア用語事典（オーム社刊）
参Ａ：SUPER ASCII Glossary Help on Internet 
【０００４】
(1) プロセス(process) ：
処理や過程を意味する一般用語（参２）
(2) スレッド(thread)：
プロセスまたはタスクと呼ばれる１つの実行環境の中で並列実行可能な処理を複数に分割した場合に、プロセッサのスケジュール対象となる実行単位または制御フローのこと。（参３）
(3) コンテキスト(context) ：
（オブジェクト指向システムに関連して）メソッドを実行するために必要な情報を蓄えるオブジェクトをいう。コンテキストは、呼び出し先のコンテキスト、プログラムの入ったメソッドオブジェクト、プログラムカウンタ、スタックポインタという情報、引数や一時変数を取るところ、および評価スタックから成立する。このような実行環境をオブジェクトとしてとるが、プロセスなどをサポートする高級言語の特徴でヒープ言語と呼ばれる。他方ＰＡＳＣＡＬやＡＬＧＯＬ６０では実行環境はスタックにとられＦＯＲＴＲＡＮでは固定領域にとられる。（参１）
(4) タスク(task)：
多重プログラミング又は多重プロセッシングの環境において、計算機によって実行されるべき仕事の要素として制御プログラムによって取り扱われる命令の１つ以上の列（ＪＩＳ）
(5) ガベージ(garbage) ：
どこからも参照されていないが、生成されてしまったオブジェクト。ガベージはガベージコレクタで回収する。（参１）
(6) ガベージコレクション(Garbage Collection)：
（オブジェクト指向システムに関連して）メモリ管理の中心となるプログラムを言う。主記憶を使いきるとメインの計算を止め、ガベージコレクタを動かして、もはや使われていないオブジェクトを全部集める方法である。この方法でガベージコレクタが働くと、計算が止まってしまうため入出力が全く反応しなくなり、実時間の応答が必要な用途には使えない。（参１）
(7) インタプリタ(interpreter) ：
解釈実行を行う翻訳プログラム（ＪＩＳ）
(8) リアルタイム(real time) ：
計算機外部の他の処理との関係をもちながら、かつ外部の処理によって定められる時間要件に従って、計算機の行うデータの処理に関する用語。実時間。（ＪＩＳ）
(9) オブジェクト(object)：
プロシジュア（定義した手続き）とデータの特性を結合させるエンティティ（実体）であり、これにより計算が行われ、局部的状態が蓄えられる。（参１）
(10) クラス(class) ：
同一の手続き群とデータ構造を持つオブジェクトの集合。（参３）
(11) ヒープ領域(heap area) ：
プログラム実行時に必要に応じて使用されるような作業領域。（参２）
(12) スケジュールする(scheduling)：
ディスパッチされるべきジョブ又はタスクを選択すること。（ＪＩＳ）
(13) イベント(event) ：
ハードウエア／ソフトウエアが、自分自身の状態の変化を他のハードウエア／ソフトウエアに通知すること。一般にこの際の通知では、イベントの種類やハードウエア／ソフトウエアの状態を表す各種パラメータをメッセージとしてまとめ、相手に送信する。そしてイベントの通知を受けた側では、メッセージのパラメータなどから適切な処理を行う。（参Ａ）
(14) イベントフラグ(event flag)：
タスクが１つまたは複数の事象の発生を待ち合わせるための機能とその事象を通知する機能とからなるタスク間同期通信機構。（参３）
(15) セマフォ(semaphore) ：
複数のプロセスやタスクを並列に処理するシステムで、各プロセス間，タスク間の同期やメッセージ制御、割込処理を行うための仕組み。（参３）
(16) 仮想マシーン（仮想機械）(virtual mathine) ：
複数の特定のプラットホーム（ＯＳやハードウエア）に組み込まれた、特定のプラットホームに依存しないアプリケーションプログラムを実行する環境。同じ仮想マシンさえ提供されていれば、プラットホームが変わっても同じアプリケーションプログラムが実行できる。
【０００５】
(17) Java VM(Java Virtual Machine) （ＪａｖａはSun Microsystems社の商標）：
オペレーティングシステムに組み込まれた、Ｊａｖａアプリケーションプログラム（ＪａｖａはSun Microsystems社の商標）を実行するための環境。一般的なプログラムは、ソースコードをコンパイルして、それぞれのオペレーティングシステムに最適化した実行コードを生成する、というスタイルを採る。Ｊａｖａ（ＪａｖａはSun Microsystems社の商標）で書かれたプログラムも同様の手順で作成するが、コンパイル後のコードは、特定のオペレーティングシステムに依存しない中間コードの形をとる。これをロードし、各オペレーティングシステムに合わせたコードに変換しながら実行するのがＪａｖａ仮想マシン（ＪａｖａはSun Microsystems社の商標）の役目であり、同じ仮想マシンさえ提供されていれば、プラットホームが変わっても同じコードが実行できるようになっている。
【０００６】
(18) フリー領域(free area) ：
ヒープ領域上の使用可能な領域、未使用領域。
【０００７】
(19) ノーマルスレッド(normal thread) ：
リアルタイム性が要求されない処理を行うスレッド。
【０００８】
(20) マークテーブル(mark table)：
オブジェクトがどこからも参照されないか否かを調べるために存在するオブジェクトに１対１に対応する表。或るオブジェクトに参照があることが確かめられた場合、そのオブジェクトに対応する表の欄にマークを付ける。全ての参照関係を調べたときマークの無いオブジェクトは不要であるので取り除くことができる。
【０００９】
(21) オブジェクトの寿命(life time of the object) ：
オブジェクトが生成され、消去されるまでの時間。
【００１０】
(22) ライトバリア(write barrier) ：
オブジェクトへの参照関係の変更をチェックし、書き替えが起こった場合に何らかの処理をすること。本件の場合は、書き替えが起きたとき、書き替える参照が指しているオブジェクトに対応するマークテーブルの欄にマークを付ける。
【００１１】
(23) スイープ(sweeping)：
ヒープ領域上の不要なオブジェクトを取り除く処理。
【００１２】
(24) オブジェクト生成(create the object) ：
新しいオブジェクトを生成すること。具体的には、ヒープ領域の一部をオブジェクトに割り当て、内容を初期化すること。
【００１３】
(25) オブジェクト消去(delete the object) ：
不要なオブジェクトを取り除くこと。具体的には、ヒープ領域に確保してある領域を解放すること。
【００１４】
(26) 参照(reference) ：
或るオブジェクトＡが別の特定のオブジェクトＢにアクセスするためにオブジェクトＢを特定する情報。具体的には、オブジェクトＢを指すポインタまたはインデックス。
【００１５】
(27) 参照変更(chenge the reference  / reconnect the reference) ：
参照を現在のオブジェクトＢから別のオブジェクトＣに変更すること。
【００１６】
さて、従来のシングルプロセッサのコンピュータシステムにおいて、オペレーティングシステム上で複数のスレッドを並行処理する場合、共有メモリを用いて排他制御するために、また複数のタスク間で同期をとるために、従来よりセマフォやイベントフラグなどを用いて排他制御が行われている。
【００１７】
また、例えばプログラムを少量のメモリ環境下で動作させることなどを目的として、仮想記憶を行わないで単一のアドレス空間のメモリをプログラムの実行時に動的に割り当てる、いわゆる動的記憶管理が従来より行われている。このような動的記憶管理によれば、プログラムにより明示的にメモリ領域の解放を行わなければ、プログラムの実行過程において使用されなくなったメモリ領域が発生する。その結果、プログラムが使用できるフリー領域が次第に不足する。こうした問題を回避するために、使用されなくなったメモリ領域（ガベージ）を抽出し、これらを集めて（コレクトして）再び使用可能なフリー領域とする、ガベージコレクションと呼ばれる処理を自動的に行うようにしている。
【００１８】
ここで従来のガベージコレクションの処理手順をフローチャートとして図５４に示す。ガベージコレクションのアルゴリズムにはマーク＆スイープ法、複写法、参照カウント法などの各種方法が考えられているが、ここではマーク＆スイープ法について例示する。図５４に示すように、まずガベージコレクションの途中でガベージコレクションスレッド以外の他のスレッドが実行されないように割り込みを禁止し、シングルスレッドモードにする(s201)。続いてメモリ上のガベージコレクションの対象となる領域（以下「ヒープ領域」という。）に割り当てられているオブジェクトにそれぞれ対応するマークの記憶領域（以下「マークテーブル」という。）をクリアする(s202)。続いてヒープ領域内に割り当てられているオブジェクトの参照関係を示す情報を基に何れかのオブジェクから参照されているオブジェクトを検出し、それらに対応するマークテーブル上の位置にマークを付ける処理を行う(s203)。この処理により、何れのオブジェクトからも参照されていないオブジェクトはもはや使われなくなったオブジェクトであり、それに相当するマークテーブルにはマークが付けられないことになる。従ってそのマークしていないオブジェクトを新たなオブジェクトの割当可能な領域、すなわちフリー領域として抽出する(s204)。例えばこのフリー領域をリスト構造のデータとして生成する。その後、割り込み禁止を解除し、マルチスレッドのモードに戻す(s205)。
【００１９】
従来はこのようなガベージコレクションが、メモリのフリー領域が所定量まで減少した時点で自動的に起動されるようにしていた。
【００２０】
また、ガベージコレクションを行ったとき、任意の大きさ（メモリサイズ）のオブジェクトが任意に解放されるのでフラグメントが発生する。そこで、連続したサイズの大きな領域がとれるように、オブジェクトの割当領域を例えば先頭から順次詰めるメモリコンパクション（以下単に「コンパクション」という。）を実行していた。
【００２１】
ここで、先行技術調査を行った際に発見した文献について示しておく。
【００２２】
(1) Incremental Garbage Collection of Concurrent Objects for Real-Time Application
この論文はBaker が書いたという1978年のリアルタイムＧＣに対して、全体の処理時間から必要なＧＣの処理時間の割合を求めるものである。
【００２３】
(2) Distributed Garbage Collection for the Parallel Inference Machine:PIE64 
ＧＣを行う領域を細かく分けることにより、個々の処理時間を短くしてリアルタイム性を向上する方法であり、全ての領域を対象にするものではない。また、スケジューリングについては述べられていない。
【００２４】
(3) Garbage Collection in Distributed Enviroment
Baker の考えを発展させ、ネットワークの分散環境に適応したもの。ネットワーク固有の問題を解決しようとするものである。
【００２５】
(4) 特開平１−２２００３９号
システムコール発行時に、そのシステムコールにより起動されるタスクの優先度を制御するものである。
【００２６】
(5) 特開平３−２３１３３３号
オブジェクトのサイズを検出し、そのサイズに応じてワークエリアをメモリに確保することが一応示されている。
【００２７】
(6) 電子情報通信学会誌Vol.80 No.6 pp586-592 
マルチメディアオペレーティングシステムのコンセプトが示されている。
【００２８】
(7) 日本ソフトウェア科学会第１２回Ｄ７−４
スタック上のオブジェクトの一番上にオブジェクトの大きさを書いておくことが示されている。
【００２９】
(8) 11TH Real-Time System Symposium "Incremental Garbage Collection of Concurrent Object for Real-Time Applications"
オブジェクト間の参照ツリーの考え方が示されている。
【００３０】
(9) 情報処理学会第３８回全国大会5U-7
オブジェクトの寿命に関連してメモリ割当を行うことが示されている。
【００３１】
(10)Lecture Notes in Computer Science 259 "Garbage Collection in a Distributed Environment" 
アプリケーションプログラムインタフェースの呼出に応じてＧＣを制御することと、オブジェクト参照に関する技術思想が示されている。
【発明の開示】
【発明が解決しようとする課題】
【００３２】
上述した排他制御の機能をセマフォやイベントフラグなどのコンピュータ資源を用いることで実現している従来のシステムにおいては、その資源が他のスレッドなどで使用されている場合には、他のスレッドはその資源が解放されるのを待たなければならない。このような資源待ちの時間が生じると、リアルタイム性の要求されるシステムにおいては大きな障害となる。すなわち、資源待ち状態にあるスレッドは、その資源が解放されるまで、処理できずリアルタイムな応答が不可能となる。
【００３３】
例えば上記従来のガベージコレクション（以下「ＧＣ」という。）の方法によれば、メモリ空間が広いほど、ガベージとしてコレクトしてもよい領域を見つけ出すのに時間がかかり、例えば６４〜１２８ＭＢのヒープ領域で数秒間を要し、且つＧＣはフリー領域がある程度減少した時点で不定期に行われるので、リアルタイム性の要求されるシステムには用いることができなかった。
【００３４】
リアルタイム性の要求されるシステムでは、あるタスクを実行中に何らかのイベント（割り込み）が発生すれば、そのイベントに応じた他のスレッドを処理することになるが、そのスレッドの切替に要する時間は、最悪値として例えば数十μｓｅｃ以下であることが要求される。ところが、上述したようにＧＣが何時起動されるか予測できず、一旦起動されれば、ＣＰＵは数秒間ＧＣに専念することになるため、その間リアルタイム処理は不可能となる。
【００３５】
上述の問題はＧＣの場合に限らず、長時間の資源待ち状態が生じるシステムに共通の問題である。
【００３６】
ＧＣの他の方法として、従来の複写法をインクリメンタルに行うようにして、リアルタイム性を確保する方法が情報処理Vol.35 No.11 pp1008 〜pp1010に示されている。この方法によれば、ＧＣの途中で中断を許すことができるので、時分割的に他のスレッドと並行処理することが一応はできる。しかし、この複写法をインクリメンタルに行うようにする方法では、複写中に他のスレッドがメモリを使用する訳にはいかないので、メモリを使用しない極一部のスレッドしか並行処理できない。また、複写法では、複写元と複写先のメモリ領域を確保しておかなければならないので、メモリの使用効率が低く、少量のメモリ環境下で動作させるシステムには向かない。
【００３７】
また、マーク＆スイープ法でマルチスレッドに対応するために参照関係が変更される度にマークを付与する方法は、「On-the-fly GC 」という名前で、ＧＣ専用のＣＰＵに処理を割り当てるマルチＣＰＵ化のための方法が情報処理Vol.35 No.11 pp1006 〜pp1008に示されている。しかし、この方法では、オブジェクトが常に作成されて、且つ参照関係が変更されている場合に、既にマークしているツリーを何回も辿り直して新しいノードを見つけてマークしなければならず、マーク作業がいつまでも終わらない場合が生じたり、非常に長い時間がかかる。また、この方法ではスイープ中にシステムをロックする必要があった。
【００３８】
そして、従来のマーク＆スイープ法等のＧＣによるフラグメントを解消するためにコンパクションを行う際、多大なＣＰＵパワーを必要としていた。また、このコンパクションを行わなければメモリの使用効率が低下するという問題があった。
【００３９】
この発明の目的は、コンパクションを不要とし、且つメモリの使用効率を向上させることにある。
【００４０】
さらに、従来のオブジェクト指向システムにおいては、永続的に存在する寿命の長いオブジェクトと短時間で消滅する寿命の短いオブジェクトがヒープ領域内に混在していたため、ＧＣを行うと、短寿命のオブジェクトから消去されて確実にフラグメントが生じてメモリ使用効率が急に低下する。また、ＧＣを行う場合に、永続的に存在するオブジェクトに対してもガベージであるか否かの判定を毎回行わなければならないので、このことがＣＰＵパワーの無駄となっていた。これに対して、一定期間存在していたオブジェクトを永久に存在するものと見なして、そのオブジェクトを存在調査から外す、いわゆる世代別ガベージコレクションという方法も従来から考えられているが、このような方法でも不要なオブジェクトが存続したり、それぞれのオブジェクトについて一定期間の存続調査をしなければならないという欠点があった。
【００４１】
この発明の他の目的はオブジェクトごとの寿命を考慮してフラグメントを低減し、メモリの使用効率を向上させ、ＣＰＵパワーの無駄を削減することにある。
【課題を解決するための手段】
【００４２】
この発明は、上記課題を解決するために以下の構成を備えている。
【００４３】
（１）メモリのヒープ領域内に生成されたオブジェクトの特性を検知する特性検知手段と、
前記特性検知手段が検知した特性に応じて、前記ヒープ領域に対する当該オブジェクトの割り当てを決定する割当決定手段と、を設けている。
【００４４】
この構成では、特性検知手段が、メモリのヒープ領域内に生成されたオブジェクトの特性、例えばオブジェクトのサイズや、オブジェクトの寿命、を検知し、割当決定手段が検知された特性に応じてヒープ領域に対する当該オブジェクトの割り当てを決定する。したがって、オブジェクトの特性に応じて、ヒープ領域に対する当該オブジェクトの割り当てを決定することができるので、メモリの使用効率の向上が図れる。
【００４５】
（２）前記特性検知手段は、前記ヒープ領域内に割り当てられるオブジェクトのサイズの分布を検知する手段であり、
前記割当決定手段は、前記分布の中心より大きな固定サイズの整数倍を前記ヒープ領域に対する新たなオブジェクトの割り当てサイズに決定する割当サイズ決定手段を含む。
【００４６】
この構成では、オブジェクトの特性としてオブジェクトのサイズの分布を検知する。一般に、オブジェクト指向のシステムにおいては、プログラムの実行時に生成されるオブジェクトの大きさ（メモリ上のサイズ）の発生頻度分布は正規分布を示す。一方、新たなオブジェクトを生成する際、メモリ上のフリー領域から割り当て可能な領域を抽出するが、上述のようにオブジェクトのサイズの分布中心より、大きなサイズを新たなオブジェクトの割り当てサイズとしておくことによって、その割り当てられたオブジェクトが消去された後、新たなオブジェクトが割り当てられるとき、上記割り当てサイズより小さなオブジェクトであれば再利用できる。上記割り当てサイズは正規分布の分布中心より大きなサイズであるため、多くのオブジェクトが先に使用されていたメモリ領域を再利用できることになる。また、このことにより、コンパクションを行わなくてもメモリの使用効率が向上することになる。また、コンパクションのためのＣＰＵパワーが不要となり、小規模のＣＰＵで応答性の高いシステムを構成することができる。
【００４７】
（３）前記特性検知手段は、システムの使用開始時にシステムに組み込まれ、前記オブジェクトのサイズの分布を検知した後にシステムから切り離されるプログラムモジュールによるものである。
【００４８】
この構成では、一度オブジェクトのサイズの分布が検知された後は、また、オブジェクトの割り当てサイズが決定された後は、メモリ領域とＣＰＵパワーの無駄がなくなる。
【００４９】
（４）前記割当サイズ決定手段は、システムの使用開始時にシステムに組み込まれ、前記固定サイズが決定された後にシステムから切り離されるプログラムモジュールによるものである。
【００５０】
この構成では、一度オブジェクトのサイズの分布が検知された後は、また、オブジェクトの割り当てサイズが決定された後は、メモリ領域とＣＰＵパワーの無駄がなくなる。
【００５１】
（５）前記ヒープ領域内を予め複数のサイズに分割するヒープ領域分割手段と、
オブジェクト生成時に当該オブジェクトのサイズより大きく且つ最も小さなサイズの領域を割り当てる手段を設けたことを特徴とする。
【００５２】
この構成では、多くのオブジェクトがメモリのヒープ領域を無駄なく再利用できることになり、コンパクションを行わなくてもメモリの使用効率が向上する。また、コンパクションのためのＣＰＵパワーが不要となり、小規模のＣＰＵで応答性の高いシステムを構成することができる。
【００５３】
（６）前記ヒープ領域分割手段は、前記複数のサイズの分割数と各サイズを引数とするアプリケーションプログラムインタフェースの呼び出しによって、前記ヒープ領域を分割する手段である。
【００５４】
この構成では、多くのオブジェクトがメモリのヒープ領域を無駄なく再利用できることになり、コンパクションを行わなくてもメモリの使用効率が向上する。また、コンパクションのためのＣＰＵパワーが不要となり、小規模のＣＰＵで応答性の高いシステムを構成することができる。
【００５５】
（７）アプリケーションプログラムインタフェースの呼び出しによって前記固定サイズを設定する手段を設けたことを特徴とする。
【００５６】
この構成では、別の装置、システム、およびアルゴリズムで、メモリのヒープ領域内に割り当てられるオブジェクトのサイズの分布を測定して、決定したオブジェクトの割り当てサイズの基になる固定サイズを登録することができ、ＣＰＵパワーとメモリの使用効率を向上させることができる。
【００５７】
（８）クラスからオブジェクトが生成された時刻に相当するデータを記憶し、前記オブジェクトを削除する際に、当該オブジェクトの寿命を検出し、該寿命のデータをクラスに設ける手段を備え、
前記特性検知手段は、クラスから生成されたオブジェクトの寿命を検知する手段であり、
前記割当決定手段は、前記特性検知手段により検知されたオブジェクトの寿命に基づいて、このオブジェクトに割り当てる、前記ヒープ領域に対するオブジェクトの生成領域を決定する手段である。
【００５８】
一般にオブジェクト指向のシステムにおいては、クラスをテンプレートとしてオブジェクトが生成されるため、同一のクラスから生成されたオブジェクトは略同一の寿命を持つ。そこで、或るクラスからオブジェクトが生成された時刻に相当するデータを記憶し、そのオブジェクトが削除された際に、当該オブジェクトの寿命を検出して、これをそのオブジェクトを生成したクラスの寿命データとして記憶し、そのクラスからオブジェクトを生成する際に、寿命データに基づいて、異なったヒープ領域にオブジェクトを生成することによって、長寿命のオブジェクトと短寿命のオブジェクトが異なった領域に生成される。これにより、長寿命領域でのフラグメントが大幅に低下し、メモリの使用効率が向上する。また、ＧＣを行う場合に、短寿命のオブジェクトが生成される領域を重点的に処理することによって、ＧＣに消費されるＣＰＵパワーを低減することができるようになる。
【発明の効果】
【００５９】
この発明によれば、多くのオブジェクトが先に使用されていたメモリ領域を再利用できることになり、このことにより、コンパクションを行わなくてもメモリの使用効率が向上することになる。また、コンパクションのためのＣＰＵパワーが不要となり、小規模のＣＰＵで応答性の高いシステムを構成することができる。
【００６０】
また、寿命データに基づいて、異なったヒープ領域にオブジェクトを生成することによって、長寿命のオブジェクトと短寿命のオブジェクトが異なった領域に生成されるため、長寿命領域でのフラグメントが大幅に低下し、メモリの使用効率が向上する。また、ＧＣを行う場合に、短寿命のオブジェクトが生成される領域を重点的に処理することによって、ＧＣに消費されるＣＰＵパワーを低減することができるようになる。
【発明を実施するための最良の形態】
【００６１】
以下、この発明の実施形態であるプログラム制御装置について、図１〜図５３を参照して順次説明する。
【００６２】
図１は装置のハードウエアの構成を示すブロック図である。装置は基本的にＣＰＵ１とオブジェクト群を生成するヒープ領域およびマークテーブル等を記憶するメモリ２、および外部との入出力を行うＩ／Ｏ３とから構成する。また、外部から必要なプログラムをメモリにロードする場合は、ＣＤ−ＲＯＭ読取インタフェース４を用い、プログラムが予め書き込まれたＣＤ−ＲＯＭ５を読み取るようにする。このＣＤ−ＲＯＭが本願発明に係るプログラム記録媒体に相当する。
【００６３】
図２はソフトウエアの構成を示すブロック図である。同図において、カーネル部分はＣＰＵやメモリを資源として管理し、時分割によるマルチスレッドの機能を実現する。ＶＭ（仮想マシーン）部分はプログラムとカーネルとのインタフェースを行うソフトウエアであり、ここではアプリケーションプログラムから見てＶＭ以下の階層全体が例えばＪａｖａ仮想マシン（ＪａｖａはSun Microsystems社の商標）として作用させる。この場合、カーネルとＶＭ部分がＪａｖａＯＳ（ＪａｖａはSun Microsystems社の商標）を構成する。このＶＭにはプログラムがバイトコード等の中間コードで与えられるとき、これを解釈するインタプリタとその解釈に応じて呼び出されるプログラムモジュール等を含む。同図におけるプログラムは中間コードによる各種スレッドであり、上記インタプリタを介して、内部のプログラムモジュールを実行する。
【００６４】
図３はメモリのヒープ領域に生成されるオブジェクトの参照関係およびスタックとの関係を示す図である。ヒープ領域に対してオブジェクトを生成した際、或るオブジェクトから他のオブジェクトへの参照関係は同図に示すようにルートノードから延びるツリー構造を成す。例えばグローバル変数を宣言すれば、その変数に対応するオブジェクトが生成される。またスレッド毎に引き数領域、戻り番地、ローカル変数、作業領域等の情報を記憶するスタックが生成され、例えば図中矢印で示すようなスタック上のローカル変数からツリー上のグローバル変数への参照関係なども記憶される。これらのスタックはヒープ領域外の所定領域に格納される。
【００６５】
図４は図２に示したソフトウエアの構成をブロック図として詳細に示したものである。同図において、ＧＣモジュール１０はＧＣを行うための各種処理のプログラムモジュールであり、ＧＣスレッド１１はこれらのモジュールを呼び出すことによって、ＧＣを実行させる。また、インタプリタ１２は、この例で、「スレッド４」からオブジェクト生成依頼があったとき、ＧＣモジュール１０の「オブジェクト生成」を呼び出し、またオブジェクト間の参照関係の変更依頼があったとき、ＧＣモジュール１０の「マーク付与」を呼び出す。
【００６６】
なお、図４に示した例では、各スレッドが中間コード（例えばＪａｖａアプレット（ＪａｖａはSun Microsystems社の商標）の場合バイトコード）で表されているが、中間コードをＶＭに対するネイティブコードに変換するコンパイラを設けてもよい。（例えばＪａｖａ（ＪａｖａはSun Microsystems社の商標）の場合、ＪＩＴ(Just-In-Time コンパイラ）等を設ける。）この場合、ネイティブコードで記述したスレッドであるので、図４に示したインタプリタ１２を介さずにＧＣモジュール１０を直接アクセスすることになる。
【００６７】
図５はＧＣを行うことによって、ヒープ領域内に生じるフラグメントを解消するためのコンパクションを行った例を示す図である。図中ハッチング部分がオブジェクトであり、これをコンパクションすることによって、（Ｂ）に示すようにフラグメントが解消されて、連続したメモリ空間が広がることになる。
【００６８】
上記コンパクションは図４に示したＧＣモジュールの「コンパクション」のプログラムにより行う。
【００６９】
図６はコンテキストスイッチ発生有無を検出するためのＡＰＩの使用例を示す図である。同図の（Ａ）に示すように、処理１を実行する前にコンテキストスイッチ発生有無の検出開始を依頼するＡＰＩ＃Ａを発行してから処理１を実行する。処理１の終了後、コンテキストスイッチ発生有無検出の終了を依頼するＡＰＩ＃Ｂを発行する。（Ａ）に示す例ではこの間にコンテキストスイッチが発生していないので、そのまま次の処理２を行う。もし、（Ｂ）に示すように、処理１の途中でスレッド＃２の処理が行われれば、すなわちコンテキストスイッチが発生していれば、ＡＰＩ＃Ｂの発行後、処理１を破棄する。たとえばメモリの領域Ａの内容を領域Ｂにコピーするような処理で、コピー処理中にコンテキストスイッチが発生した場合、領域Ａの内容が変わって領域ＡとＢの内容が不一致となる場合がある。不一致ではコピーしたことにならないので、領域Ｂを無効にする。このことは、最初から処理が行われなかったのと同じであり、処理自体を破棄したことに他ならない。
【００７０】
図７は上記の処理をフローチャートとして示したものである。まず、ＡＰＩ＃Ａを発行してから処理１を実行する（ｓ１→ｓ２）。この処理１が終了した後、ＡＰＩ＃Ｂを発行して、その戻り値を取得する（ｓ３）。戻り値がコンテキストスイッチの発生を表す場合、処理１を破棄して、再び処理１を実行する（ｓ４→ｓ５→ｓ１→ｓ２）。戻り値がコンテキストスイッチの非発生を表す場合、処理を終了する。このように所定の期間内でのコンテキストスイッチの発生有無が分かるので、コンテキストスイッチが発生すれば、その間の処理を破棄し無効とすることによって、システムを現実にはロックしていないにも拘らず排他的制御を行うことが可能となる。
【００７１】
図８は上記ＡＰＩ＃ＡおよびＡＰＩ＃Ｂのカーネルにおける処理手順を示すフローチャートである。ＡＰＩ＃Ａの発行（システムコール）があれば、コンテキストスイッチの発生有無を示すフラグをクリアする。また、ＡＰＩ＃Ｂが発行されると、上記フラグの状態を戻り値としてスレッドに返す。
【００７２】
図９はコンテキストスイッチの処理手順を示すフローチャートである。コンテキストスイッチがスケジューラによって行われると、上記フラグをセットしてからコンテキストスイッチを実行する。すなわちスイッチ前のスレッドの実行状態をコンテキストとして格納するとともに、スイッチ後のスレッドのコンテキストを読み出してＣＰＵのレジスタ等に設定する。
【００７３】
図１０は上記コンパクションの処理手順を示すフローチャートである。先ず、ヒープ領域内の先頭のオブジェクトを指定し（ｓ１１）、そのオブジェクトをヒープ領域の先頭にコピーするための領域を確保し（ｓ１２）、コピー中に他のスレッドによってその領域に何らかのデータが書き込まれないようにしてから上記ＡＰＩ＃Ａを発行する（ｓ１３）。そして、図５に示したように、ヒープ領域内のオブジェクトを先頭から順次空き領域へコピーすることによって詰めていく（ｓ１４）。１つのオブジェクトについてのコピーが終われば、上記ＡＰＩ＃Ｂを発行する（ｓ１５）。このことにより、ＡＰＩ＃Ａを発行してから、ＡＰＩ＃Ｂを発行するまでの期間にコンテキストスイッチが発生したか否かがＡＰＩ＃Ｂの戻り値として得られる。もしコンテキストスイッチが発生していれば、今回コピーを行ったオブジェクトを既に確保している領域に再びコピーする（ｓ１６→ｓ１３→・・・）。もしコンテキストスイッチが発生していなければ、次のオブジェクトについて同様に処理を行う（ｓ１６→ｓ１７→ｓ１８→・・・）。このようにシステムをロックすることなく、しかも他のスレッドとともに、コンパクションを同時に行うことが可能となる。
【００７４】
上述の例ではマーク＆スイープ法によるＧＣにおけるコンパクションに適用したが、複写法によるＧＣに適用する場合、図１１および図１２に示す処理を行う。
【００７５】
図１１は上記複写法によるＧＣのフローチャートである。先ず、オブジェクトの参照関係を表すツリー構造のデータのルートノードへポインタを移動し（ｓ２１）、そのルートノードに相当する、Ｆｒｏｍ領域にあるオブジェクトをＴｏ領域に複写する（ｓ２２）。（ヒープ領域はＦｒｏｍ領域とＴｏ領域に分けられ、Ｆｒｏｍ領域内の残すべきオブジェクトのみをＴｏ領域に複写することによってＴｏ領域にガベージのないオブジェクトだけを再構成する。次回は現在のＦｒｏｍ領域をＴｏ領域とし、Ｔｏ領域をＦｒｏｍ領域として、その操作を交互に繰り返すのが、複写法によるガベージコレクションである。）その後、ツリーを辿って、参照関係にある次のオブジェクトへポインタを移動させ（ｓ２３）、そのオブジェクトをＴｏ領域に複写する（ｓ２４）。この処理をツリーで辿れるすべてのオブジェクトについて行う。
【００７６】
図１２は図１１における複写処理の内容を示すフローチャートである。先ず、複写すべきオブジェクトをＴｏ領域内の所定位置にコピーするための領域を確保し、コピー中に他のスレッドによってその領域に何らかのデータが書き込まれないようにし、上記ＡＰＩ＃Ａを発行してから（ｓ３１）、オブジェクトをＦｒｏｍ領域からＴｏ領域に複写する（ｓ３２）。その後、上記ＡＰＩ＃Ｂを発行する（ｓ３３）。このことにより、ＡＰＩ＃Ａを発行してから、ＡＰＩ＃Ｂを発行するまでの期間にコンテキストスイッチが発生したか否かがＡＰＩ＃Ｂの戻り値として得られる。もしコンテキストスイッチが発生していれば、今回複写を行ったオブジェクトを既に確保している領域に再び複写する（ｓ３４→ｓ３１→・・・）。
【００７７】
図１３および図１４はコンテキストスイッチの発生有無を検出して排他性を確保するのではなく、複写しようとするオブジェクトが複写前に書き替えられたか否かを検出して排他性を確保する場合の処理手順を示すフローチャートである。
【００７８】
複写を行う場合、先ず複写すべきオブジェクトをＴｏ領域内の所定位置にコピーするための領域を確保し、コピー中に他のスレッドによってその領域に何らかのデータが書き込まれないようにしてから、図１３に示すようにＡＰＩ＃Ｃを発行する（ｓ４１）。このＡＰＩは指定したメモリ領域に対する書き込みが発生したか否かの検出を依頼するアプリケーションプログラムインタフェースである。続いてオブジェクトをＦｒｏｍ領域からＴｏ領域に複写する（ｓ４２）。その後、ＡＰＩ＃Ｄを発行する（ｓ４３）。このＡＰＩは上記ＡＰＩ＃Ｃが呼び出されてから、このＡＰＩ＃Ｄが呼び出されるまでの間に指定メモリ領域に何らかのデータの書き込みが発生したか否かが戻り値として返されるアプリケーションプログラムインタフェースである。したがって、複写しようとするオブジェクトのメモリ領域を指定してＡＰＩ＃Ｃを発行し、ＡＰＩ＃Ｄの戻り値を見れば、そのオブジェクトが参照されたか否かが判る。オブジェクトが参照されていれば、内容が書き変わっている可能性があるので、そのオブジェクトの複写をやり直す（ｓ４４→ｓ４１→・・・）。
【００７９】
図１４は上記ＡＰＩ＃ＣおよびＡＰＩ＃Ｄのカーネルにおける処理手順を示すフローチャートである。ＡＰＩ＃Ｃの発行（システムコール）があれば、所定のワークエリアをクリアし、ＡＰＩ＃Ｃのパラメータで指定された領域がライトされたときに例外が発生するようにＭＭＵ（Memory Management Unit) を設定する。また、ＡＰＩ＃Ｄが発行されると、上記パラメータで指定された領域がライトされたときに例外が発生しないように、ＭＭＵに対する上記設定を解除する。そして上記ワーク領域にセットされるフラグの状態を戻り値としてスレッドに返す。
【００８０】
図１５は上記例外発生時のＭＭＵの処理内容を示すフローチャートである。例外が発生すると、上記ワーク領域内の参照フラグをセットする。
【００８１】
なお、上述の例では複写法によるＧＣの場合について示したが、マーク＆スイープ法におけるコンパクションの場合にも同様に適用できる。
【００８２】
次に、インクリメンタルにガベージコレクションできるＧＣスレッドの優先度を自動的に切り替えるようにした場合について説明する。図１６および図１７はインクリメンタルにガベージコレクションできるＧＣスレッドの優先度を自動的に切り替えるようにした場合の例を示す図である。
【００８３】
図１６の（Ａ）に示すように、ＧＣスレッドの優先度を、高優先度時間は高め（例えば最高優先度にし）、低優先度時間は低く（例えば最低優先度）する動作を交互に行う。
【００８４】
同図の（Ｂ）はＧＣスレッド以外の中程度の優先度のスレッドを同時に行った場合の例について示している。すなわちＧＣスレッドの優先度が低いとき、それより優先度の高いスレッドがＲｅａｄｙ状態となれば、コンテキストがスイッチされ、そのスレッドの実行中にＧＣスレッドの優先度が高くなれば、そのＧＣスレッドにコンテキストがスイッチされ、そのＧＣスレッドの処理が中断すると、上記のＧＣスレッド以外のスレッドの処理を行うことになる。このようにすれば、一定周期で必ずＧＣスレッドが実行されるため、フリー領域が慢性的に不足状態となることが防止され、常に高いパフォーマンスを維持することができる。
【００８５】
図１７はスレッドの優先度の切替に関するカーネルの行う処理手順を示すフローチャートである。優先度の値は複数段階あり、その値の設定は対応するＡＰＩの発行により行えるようにしている。ここでは、ＧＣスレッドの２つの優先度を設定する際、高優先度の値を設定するＡＰＩが発行されると、図１７の（Ａ）に示すように、その値をＧＣスレッドの高優先度の値として設定する。同様に、低優先度の値を設定するＡＰＩが発行されると、（Ｂ）に示すように、その値をＧＣスレッドの低優先度の値として設定する。また、ＧＣスレッドの高優先度の時間を設定するＡＰＩが発行されると、同図の（Ｃ）に示すように、その値を設定し、同様に低優先度の時間を設定するＡＰＩが発行されると、同図の（Ｄ）に示すように、その値を設定する。
【００８６】
図１７の（Ｅ）は、カーネルのスケジューラに対する処理手順を示すフローチャートである。ここでは、初期状態で、高優先度のキューにＧＣスレッドが資源の割当を受けようとする待ち行列に入っているものとし、先ず、そのデータ（ＧＣスレッドを識別するデータ）を高優先度のキューから取り出して低優先度のキューに挿入する（ｓ５１）。そしてスケジューラは、既に設定されている低優先度時間だけ時間待ちを行い（ｓ５２）、続いて低優先度のキューからＧＣスレッドを識別するデータを取り出して高優先度のキューに挿入する（ｓ５３）。そしてスケジューラは、既に設定されている高優先度時間だけ時間待ちを行う（ｓ５４）。以上の処理を繰り返すことによって、スケジューラの動作により図１６（Ａ）に示したようにＧＣスレッドの優先度が交互に切り替わる。ＧＣスレッド以外のスレッドについては、そのスレッドの優先度に対応するキューの待ち行列に応じて従来と同様のスケジューリングが行われ、図１６の（Ｂ）に示したように、コンテキストスイッチがなされる。
【００８７】
図１８は上記のＧＣスレッドの高優先度時間をＡＰＩによって設定可能とした場合について示している。また、図１９はそのＡＰＩの呼び出しに応じたカーネルにおける処理手順を示すフローチャートである。このＡＰＩの発行（システムコール）があれば、上記の高優先度時間をそのＡＰＩのパラメータによって設定（登録）する。
【００８８】
図２０は上記のＧＣスレッドの高優先度時間を設定可能とするＡＰＩを使うプログラムの例を示すフローチャートである。先ず、ループの１回目の示すフラグの状態を見る（ｓ６１）。最初はＯＦＦ状態であるので、このフラグをＯＮし（ｓ６２）、現在のフリー領域を調べ、それを記録する（ｓ６３）。初めはＧＣの高優先度時間と低優先度時間は予め定められたデフォルト値である。スケジューラにより、一定時間停止した後（ｓ６４）、今度は、前回に調べたフリー領域の容量と現在のフリー領域の容量との大小比較を行い（ｓ６５）、フリー領域の容量が増加していれば、ＧＣスレッドの高優先度時間を短くし（ｓ６６→ｓ６７）、フリー領域の容量が減少していれば、ＧＣスレッドの高優先度時間を長くする（ｓ６８）。以上の処理を繰り返す。
このことによって、ＧＣの優先度が動的に自動調整される。
【００８９】
図２１はＧＣスレッドの高優先度時間と低優先度時間とによる周期を設定可能とした場合について示している。（Ａ）は周期が長い場合、（Ｂ）は短い場合である。
【００９０】
図２２は上記周期を設定可能とする周期設定ＡＰＩの呼び出しに応じたカーネルにおける処理手順を示すフローチャートである。この周期設定ＡＰＩの発行があれば、現在設定されている高優先度時間および低優先度時間の値を読み取り、その割合（比率）を計算する（ｓ７１→ｓ７２→ｓ７３）。その後、この周期設定ＡＰＩのパラメータで指定された周期の値に応じて高・低優先度時間を再計算する（ｓ７４）。そして、その高優先度時間および低優先度時間を設定更新する（ｓ７５→ｓ７６）。
【００９１】
たとえば連続的なパルスを処理するような、連続してＣＰＵ資源が必要なアプリケーションプログラムの場合には、ＧＣスレッドの周期が短くなるように周期設定ＡＰＩを発行し、通常のアプリケーションプログラムのように断続的にＣＰＵ資源を利用するアプリケーションプログラムでは周期が長くなるように周期設定ＡＰＩを発行する。
【００９２】
次に、必要な時点でＧＣスレッドを実行し、且つリアルタイム性を確保するようにした場合について説明する。
【００９３】
図２３および図２４は必要な時点でＧＣスレッドを実行し、且つリアルタイム性を確保するようにした例であり、図２３に示す例では、スレッド１とスレッド３がリアルタイム性の要求されるスレッド、スレッド２がリアルタイム性の要求されないスレッド（ノーマルスレッド）である。また、スレッド３がＧＣスレッドである。メモリのフリー領域が多い通常状態で、スレッド２が実行されているときにイベント１が発生すれば処理がスレッド１に移され、イベント１の処理に起因するスレッド１の処理が終了すればスレッド２へ戻る。同様に、イベント２が発生すればスレッド３に処理が移る。もしスレッド２の処理によってフリー領域が予め定めた警告レベルまで低下したとき、スレッド２の処理を中断して、スレッド３のＧＣスレッドを実行する。この処理によってフリー領域が確保されるとスレッド２の処理へ戻る。もしＧＣスレッドの処理途中でイベント１が発生すれば、ＧＣの途中であってもスレッド１へ処理が移る。このようにリアルタイム性の要求されるスレッドでは、一般に生成されるオブジェクトの量が少なく、大体の予測が可能であるので、それに応じて上記警告レベルを設定しておけば、スレッド２に処理によって、フリー領域が大幅に減少してスレッド１やスレッド３のリアルタイム性の要求される処理が実行できなくなるといった、不都合が回避できる。
【００９４】
図２４は上記コンテキストスイッチの処理を行うスケジューラの処理手順を示すフローチャートである。先ずイベントの発生有無を検知し（ｓ８１）、イベントが発生していれば、対応するリアルタイムスレッドにコンテキストをスイッチする（ｓ８２）。イベントが発生していなくて、フリー領域が警告レベルより多ければ、ノーマルスレッドのうち優先度の最も高いもの（図２３に示した例ではスレッド２）にコンテキストをスイッチする（ｓ８３→ｓ８４）。もしフリー領域が警告レベルより少なくなれば、ＧＣスレッドにコンテキストをスイッチする（ｓ８５）。
【００９５】
次に、コンテキストスイッチの検出を依頼するＡＰＩにおける強制コンテキストスイッチの例について説明する。図２５はコンテキストスイッチの検出を依頼するＡＰＩにおける強制コンテキストスイッチの例を示している。先に示した例では、ＡＰＩ＃Ａを発行してから、ＡＰＩ＃Ｂを発行するまでの間にコンテキストスイッチが発生したか否かが判るようにしたものであったが、この図２５に示す例は、ＧＣの優先度を高・低交互に切り替える場合に、上記の排他制御のためのＡＰＩを発行している間にコンテキストスイッチが発生することを予測して、無駄な処理を行わないようにしたものである。すなわち、高優先度ＧＣスレッドを実行中にＡＰＩ＃Ａ′を発行した際、ＡＰＩ＃Ａ′は高優先度時間が終了するまでに、必要な処理が完了するか否かを判定して、もし完了しなければ、その時点でＧＣスレッドの優先度を低くする。図２５に示した例では、ＧＣスレッドの優先度が低くなったことにより、ＧＣスレッド以外の中優先度のスレッドにコンテキストスイッチされることになる。このことにより無駄な処理が避けられる。
【００９６】
図２６は上記ＡＰＩ＃Ａ′の呼び出しに応じたカーネルにおける処理手順を示すフローチャートである。このＡＰＩの呼び出しがあれば、コンテキストスイッチフラグをクリアし（ｓ９１）、ＧＣスレッドの高優先度時間の残時間を取得する（ｓ９２）。そして、このＡＰＩ＃Ａ′のパラメータである排他時間（ＡＰＩ＃Ａ′を発行してから、ＡＰＩ＃Ｂを発行するまでの時間）と上記残時間との大小比較を行う（ｓ９３）。もし、残時間が排他時間より短ければＧＣスレッドの優先度を強制的に低くする（ｓ９４）。なお、ＡＰＩ＃Ｂ呼び出しによる処理内容とコンテキストスイッチの処理内容は図８および図９に示したものと同様である。
【００９７】
次に、メモリ（ヒープ領域）使用量に応じてＧＣのアルゴリズムを切り替える例について説明する。図２７はメモリ（ヒープ領域）使用量に応じてＧＣのアルゴリズムを切り替えるための処理手順を示すフローチャートである。先ず、メモリ使用量の値とそれに応じてどのアルゴリズムでＧＣを行うかを示すしきい値を設定し（ｓ１０１）、メモリ使用量を取得する（ｓ１０２）。これはヒープ領域内に生成されたオブジェクトのメモリサイズの合計値である。メモリ使用量がしきい値ｔｈ１を超えた場合、ＧＣアルゴリズム（１）の手順でＧＣを行う（ｓ１０３→ｓ１０４）。メモリ使用量がしきい値ｔｈ２を超えたなら、ＧＣアルゴリズム（２）の手順でＧＣを行う（ｓ１０５→ｓ１０６）。以下同様である。ここで、しきい値ｔｈ１はしきい値ｔｈ２より小さく、ＧＣアルゴリズム（１）としては図１６に示した、ＧＣスレッドの優先度の高低を交互に繰り返す処理を行う。しきい値の高いときに行うＧＣアルゴリズムとしては、図２３に示した不定期のＧＣを実行する。ここでＧＣ自体は例えばマーク＆スイープ法により行う。通常、前者の場合にはＣＰＵ負荷が軽く、専らこの方法によりＧＣが行われるが、ノーマルスレッドによって短時間に大量のメモリが使用された場合には、図２３に示した方法によりＧＣを重点的に行う。このことによって常に広いフリー領域を確保し、且つリアルタイム性を維持する。
【００９８】
次に、オブジェクト生成時のヒープ領域に対する新たなオブジェクトの割り当てサイズを定める例について説明する。図２８〜図３０はオブジェクト生成時のヒープ領域に対する新たなオブジェクトの割り当てサイズを定めるための処理に関する図である。一般にプログラムの実行により生成されるオブジェクトのサイズの分布は図２８に示すように略正規分布を示す。その中心値は３２と６４バイトの間に納まる程度である。そこで、図２９の（Ａ）に示すように、この中心値より大きなサイズで、且つ２の巾乗バイトの整数倍のサイズをオブジェクトの割り当てサイズとする。従来は同図の（Ｂ）に示すように、生成すべきオブジェクトのサイズの量だけ任意に割り当てられていたため、そのオブジェクトの消去の際、不揃いのサイズのフラグメントが生じる。本願発明によれば、新たに生成されるオブジェクトのサイズが上記固定値の整数倍であるため、メモリ領域の再利用性が高まり、メモリ使用効率が全体に高まる。しかも場合によってはコンパクションが不要となる。
【００９９】
図３０はそのオブジェクト生成時の処理手順を示すフローチャートである。先ず、これまでに生成したオブジェクトのサイズの発生頻度の分布データを求める（ｓ１１１）。既に前回までに分布データを求めている場合には、それを更新する。続いて、今回割り当てるべきメモリの空いている領域で、且つ生成しようとするオブジェクトのサイズより大きな領域を探し、上記の固定サイズの整数倍のメモリ領域にオブジェクトを割り当てる（ｓ１１２→ｓ１１３→ｓ１１４→ｓ１１５）。上記２の巾乗バイトはシステム定数であるが、必ずしもこの値を固定サイズとする必要はなく、任意である。固定サイズをもし大き過ぎる値に採れば、サイズの大きな領域に小さなオブジェクトが割り当てられる場合が増えることになり、逆に、固定サイズを小さ過ぎる値に採れば、オブジェクトの生成に再利用できない領域が増えることになる。分布データを基に上記固定サイズを決定する場合には、メモリの使用効率が最適となるように決定すればよい。また、最適値でなくても、例えば２の巾乗の値を採れば、アドレス決定がやり易くなるという効果を奏する。
【０１００】
図３１は上記オブジェクトのサイズの発生頻度分布データを求めるプログラムモジュール、およびオブジェクトの割り当てサイズを決定するプログラムモジュールの処理内容を示すフローチャートである。先ず、オブジェクトのサイズの発生頻度分布データを求めるプログラムモジュールをロードし（ｓ１２１）、そのプログラムモジュールを起動する。すなわち一定時間が経過するまで（たとえばアプリケーションプログラムの起動・終了が１０回行われるまで、またたとえば２４時間経過するまで）、生成された各オブジェクトのサイズをサイズ毎に計数し、その分布データを求める（ｓ１２２→ｓ１２３）。その後、その分布データをシステムに登録し（ｓ１２４）、オブジェクトのサイズの発生頻度分布データを求めるプログラムモジュールをアンロードする（ｓ１２５）。続いて固定サイズを決定するプログラムモジュールをロードし（ｓ１２６）、そのプログラムモジュールを実行する。すなわちシステムの登録された分布データを取得し、その分布中心値より大きなサイズで、且つたとえば２の巾乗バイトを固定サイズとして決定し、その値をシステムに登録する（ｓ１２７→ｓ１２８）。その後、固定サイズを決定するプログラムモジュールをアンロードする（ｓ１２９）。
【０１０１】
このように、一度オブジェクトのサイズの分布が検知された後、および固定サイズが決定された後は、それらのためのプログラムモジュールをアンロードすることによって、メモリ領域とＣＰＵパワーの無駄を無くす。
【０１０２】
次に、固定サイズをＡＰＩによって設定する例について説明する。図４９は上記固定サイズをＡＰＩによって設定する例を示している。図に示すように、固定サイズ設定処理では、固定サイズを引数として固定サイズ設定ＡＰＩを呼び出す。呼び出されたＡＰＩでは、引数を固定サイズとしてシステムに登録する。オブジェクト生成時にはオブジェクトのサイズと固定サイズを比較し（ｓ２１１）、固定サイズ以下であれば、ヒープ上の固定サイズの空き領域を探し、見つかった領域をオブジェクトに割り当てる（ｓ２１２→ｓ２１３）。固定サイズを超える場合は、ヒープ上のオブジェクトサイズより大きな空き領域を探し、見つかった領域をオブジェクトに割り当てる（ｓ２１４→ｓ２１５）。
【０１０３】
次に、固定サイズをＡＰＩによって設定する他の例について説明する。図５０は上記固定サイズをＡＰＩによって設定する他の例を示している。図５０に示すように、この例では、まずオブジェクトサイズの分布データをオブジェクトサイズ分布設定ＡＰＩを呼び出して設定する。この分布データは予め所定時間所定のアプリケーションを実行して測定したものである。オブジェクトサイズ分布設定ＡＰＩは呼び出しに応答して、引数をオブジェクトサイズ配列変数にセットする。続いて、その中心値より大きなサイズで、且つ２の巾乗バイトを固定サイズとして決定し、これを固定サイズ変数にセットする。
【０１０４】
次に、オブジェクトの割り当てサイズを予めいくつかのサイズに定めておく例について説明する。図５１〜図５３はオブジェクトの割り当てサイズを予めいくつかのサイズに定めておく例を示す図である。図５１は事前に所定のアプリケーションを所定時間実行して測定したオブジェクトサイズの分布および分割領域の集合を表している。予めヒープ領域を分割する場合、実際のオブジェクトサイズの分布を測定し、その分布に近くなるように、分割サイズと数を定める。たとえば、ヒープ領域が２ＭＢの場合、分割サイズ指定変数を
集合No.n    バイトk   個数m 
1           64       5000 
2          256      10000 
3           1k      10000 
4           4k       5000 
5          32k        500 
とする。
【０１０５】
上記分割サイズを設定する場合、図５２に示すように、分割サイズ設定ＡＰＩを呼び出して行う。呼び出された分割サイズ設定ＡＰＩは図５３に示すように、引数を分割サイズ指定変数にセットし、それに応じてヒープ領域を分割する。すなわち、まずループカウンタｎを０とし（ｓ２２１）、ｎ番目の分割サイズ指定変数からサイズｋと個数ｍを取得する（ｓ２２２）。続いてヒープ領域からサイズｋの領域をｍ個に分割し（ｍ個分確保し）、リストに登録する（ｓ２２３）。この処理をループカウンタｎを１インクリメントしながら繰り返し、全てのサイズの分割を行う（ｓ２２５→ｓ２２２→・・・）。なお、上記の例で、サイズが３２ｋバイトを超えるオブジェクトを生成する場合は、ヒープ領域内の上記分割された領域以外の領域に割り当てる。
【０１０６】
次に、オブジェクトの寿命を考慮してＧＣの効率を高める例について説明する。図３２〜図３４はオブジェクトの寿命を考慮してＧＣの効率を高めるための処理を行う例を示す図である。図３２の（Ａ）に示す例では、ヒープ領域として、短寿命のオブジェクトを生成する領域と長寿命のオブジェクトを生成する領域とに分け、クラスは長寿命領域に確保する。尚、クラスはその他の固定領域に確保してもよい。そして、クラスにはオブジェクトを生成するためのテンプレートとしての定義情報以外に、生成するオブジェクトの寿命を示す寿命フラグを持たせる。この寿命フラグはクラスの生成時に自動的に生成する。同図の（Ｂ）は従来のヒープ領域に対するオブジェクトの割り当て例を示す図である。
【０１０７】
図３３はオブジェクトの消去の手順を示すフローチャートである。同図に示すようにオブジェクトを消去した際に、そのオブジェクトの寿命が長いか短いかを判定し、寿命が短ければ、そのオブジェクトのクラスの寿命フラグを短寿命にセットする。例えばオブジェクトの領域内にそのオブジェクトが生成された時刻を格納しておき、そのオブジェクトを消去する時刻との差によって、そのオブジェクトの寿命を求める。上記時刻は例えばＧＣの回数を単位としてもよい。
【０１０８】
図３４はオブジェクトの生成の処理手順を示すフローチャートである。クラスの寿命フラグが短寿命を示していれば、短寿命領域にオブジェクトを生成し、そうでなけば、長寿命領域にオブジェクトを生成する。
【０１０９】
このようにオブジェクトの寿命に応じてメモリの割り当て領域を区分することによって、長寿命領域ではフラグメントを大幅に低下でき、メモリの使用効率が向上する。また、例えば寿命領域についてＧＣを重点的に行うことにより、ＧＣに消費されるＣＰＵパワーを小さくすることができる。
【０１１０】
次に、マーク＆スイープ法によるインクリメンタルＧＣについて図３５〜４８を参照して説明する。
【０１１１】
図３５はマーク＆スイープ法によるＧＣの全体の処理手順を示すフローチャートである。このＧＣはマークテーブルのクリア、上記ツリー探索によるマーク付与およびオブジェクトの消去（スイープ）を繰り返し行う。
【０１１２】
図３６は図３５における「マーククリア」の処理内容を示すフローチャートである。この処理はマークテーブルの内容を一旦クリアするものであり、まずマークテーブルの先頭にポインタを移動し（ｓ１３１）、その位置のマークをクリアし（ｓ１３２）、次のマークの位置までポインタを移動させる（ｓ１３３）。この処理を全てのマークについて繰り返す（ｓ１３４→ｓ１３２→・・・）。
【０１１３】
図３７は図３５における「オブジェクトの消去」の処理内容を示すフローチャートである。先ず、マークテーブルの先頭にポインタを移動させ（ｓ１４１）、マークの有無を検出し、マークされていなければ、そのマークテーブル上の位置に相当するオブジェクトのヒープ領域内の位置を計算し、該当のオブジェクトを消去する（ｓ１４２→ｓ１４３→ｓ１４４）。続いて、マークテーブルのポインタを次に移動して、同様の処理を繰り返す（ｓ１４５→ｓ１４６→ｓ１４２→・・・）。これによりマークテーブルにマークされているオブジェクトを残し、その他のオブジェクトをヒープ領域から消去する。
【０１１４】
説明を容易にするために、先ず前提となるマーク＆スイープ法におけるマーク付与について説明する。
【０１１５】
図３８はツリー探索によるマーク付与の手順を示す図である。（Ａ）に示すように、ルートノード１０から各ノードへ、ツリー構造で表される参照関係を辿って、参照関係にあるノード（オブジェクト）にマークを付与する。具体的にはマークテーブル上の該当位置のビットをセットする。このツリー構造は、たとえば或るオブジェクトが他のどのオブジェクトを参照しているかを示す、オブジェクト内に設けられる変数の内容によって構成され、このオブジェクトの参照関係を辿ることが、すなわちツリーを辿ることである。
【０１１６】
（Ａ）のように、ノード番号３までマーク付与を行った時点で割込が発生し、その割込処理によって、（Ｂ）のように、ルートノードからノード番号７で表されるオブジェクトへの参照関係が絶たれて、ノード番号２で表されるオブジェクトからノード番号７で表されるオブジェクトが参照される関係となれば、割込処理が終了してＧＣスレッドに戻って、マーク付与を再開したとき、ルートノードからノード番号７で表されるオブジェクトへの参照関係が絶たれているので、（Ｃ）に示すようにポインタをルートノードに戻して次の参照関係にあるノード番号８に進むことになる。この時点ではノード番号５，６に対してはマーク付与されない。そこで、参照関係の変更のあったオブジェクトについては、そのオブジェクトからツリーを辿ってそのオブジェクトから参照されているオブジェクトについてマークを付与する必要がある。
【０１１７】
図３９は「オブジェクトの生成」の処理内容を示すフローチャートである。まずカーネルに対してシステムのロックを起動し（ｓ１５１）、ヒープ領域内の空いている領域を探し（ｓ１５２）、生成しようとするオブジェクトのサイズより大きな領域に対して必要なサイズを割り当て（ｓ１５３→ｓ１５４）、参照変更のマーク付与（ライトバリア）を行い（ｓ１５５）、システムをアンロックする（ｓ１５６）。
【０１１８】
図４０は上記「参照変更のマーク付与」の処理手順を示すフローチャートである。先ず、参照変更されたオブジェクトからマークテーブル上の位置を計算し、該当のマークがWhite であるか否かを判定する。このWhite マークはたとえば00の２ビットで表され、未だマークされていない状態を意味する。もし、White マークでなければ、すでにマークされているので、そのまま処理を終了する。White マークであれば、それをGrayにマークする。このGrayマークはたとえば01の２ビットで表され、参照変更のあったオブジェクトであることを意味する。なお、オブジェクトからマークの位置を計算する際、たとえばオブジェクトのアドレスを１／８してオフセットを加えることによって行うか、オブジェクトの通し番号により計算する。
【０１１９】
図４１は「ツリー探索によるマーク付与」の処理手順を示すフローチャートである。まず、ツリーを辿るためのポインタをツリーのルートノードに移動させ（ｓ１６１）、新たに生成するオブジェクトに対応するマークを付与する（ｓ１６２）。続いてツリーを辿って、ポインタを次のオブジェクトへ移動させ（ｓ１６３）、この処理をツリーの最後まで繰り返す（ｓ１６４→ｓ１６２→・・・）。その後、各スレッドスタックの先頭へポインタを移動させ（ｓ１６５）、スタックにあるオブジェクトに対応するマークを付与する（ｓ１６６）。その後、ポインタをスタックの次に移動させて（ｓ１６７）、この処理をツリーの最後まで繰り返す（ｓ１６８→ｓ１６６→・・・）。その後、スレッドスタックの次に移り（ｓ１６９）、同様の処理をスレッドスタックの最後まで繰り返す（ｓ１７０→ｓ１６６→・・・）。さらにこのスレッドスタックについての処理をすべてのスレッドスタックについて行う（ｓ１７１→ｓ１７２→ｓ１６５→・・・）。この一連のツリー探索において、Grayマークが途中で１度でも検出された場合、もう一度ルートノードから探索およびマーク付与を行う（ｓ１７３→ｓ１６１→・・・）。
【０１２０】
図４２は図４１における「オブジェクトに対応するマーク付与」の処理手順を示すフローチャートである。この処理は、生成されているオブジェクトからマークテーブル上の位置を計算し、Black マークを付与する。このBlack マークはたとえば1xの２ビットで表され、マークされている状態を意味する。
【０１２１】
上述したようなマーク付与の方法では、その途中で割込がかかってオブジェクトの参照関係が変化すると、Grayマークが付与されるので、ツリー探索を繰り返さなければならない。場合によってはいつまでたってもマーク付与が完了せずに、ＧＣがいつまでも行われないといった事態に陥る。
【０１２２】
図４３は上記の問題を解消するための「ツリー探索によるマーク付与」の手順を示す図である。（Ａ）は図３８に示した（Ａ）の状態で割込がかかって参照関係が変化したときの状態を示す。このように、ノード番号３までマーク付与を行った時点で割込が発生し、その割込処理によって、ルートノードからノード番号７で表されるオブジェクトへの参照関係が絶たれて、ノード番号２で表されるオブジェクトからノード番号７で表されるオブジェクトが参照される関係となれば、参照先のノード番号７表すデータをマークスタックに積む。その後、割込処理が終了してＧＣスレッドに戻って、マーク付与を再開したとき、ルートノードからノード番号７で表されるオブジェクトへの参照関係が絶たれているので、（Ｂ）に示すようにポインタをルートノードに戻して次の参照関係にあるノード番号８をマークする。この時点で一通りのツリー探索を終了し、その後は、（Ｃ）に示すようにマークスタックの内容によって示されるノードからツリーを辿って参照関係にあるオブジェクトについてマークを付与する。これにより（Ｄ）に示すように、参照関係にある全てのオブジェクトについてのマーク付与が完了する。
【０１２３】
図４４は「参照変更のマーク付与」の処理手順を示すフローチャートである。このように、参照変更されたオブジェクトを示すデータを上記マークスタックに積む。なお、オブジェクトの生成の処理は図３９に示したもの変わらない。
【０１２４】
図４５は、「ツリー探索によるマーク付与」の処理手順を示すフローチャートである。ステップｓ１６１〜ｓ１７２の部分は図４１に示したフローチャートのステップｓ１６１〜ｓ１７２と同じである。この図４５に示す例では、全スレッドスタックについてのツリー探索を完了した後、マークスタックからデータを取り出し（ｓ１８１→ｓ１８２）、そのデータで示されるオブジェクトに対応するマーク付与を行い（ｓ１８３）、そのオブジェクトからツリーを辿ってツリーの最後まで、参照関係にあるオブジェクトのマーク付与を行う（ｓ１８４→ｓ１８５→ｓ１８３→・・・）。この処理をマークスタックが空になるまでマークスタックのポインタを更新しながら繰り返す（ｓ１８１→ｓ１８２→・・・）。
【０１２５】
図４６は図４５における「オブジェクトに対応するマーク付与」の処理手順を示すフローチャートである。この処理は、生成されているオブジェクトからマークテーブル上の位置を計算し、マークを付与する。
【０１２６】
このようにマークスタックを用いることによって、ツリー探索をルートノードから再開する必要がなくなり、マーク付与に要する全体の処理時間を大幅に短縮化できる。
【０１２７】
図４７および図４８は上記マークスタックを用いてマーク付与を行う場合に、更に無駄な処理時間を無くすようするフローチャートである。
図４７は上記「参照変更のマーク付与」の処理手順を示すフローチャートである。先ず、参照変更されたオブジェクトからマークテーブル上の位置を計算し、該当のマークがWhite であるか否かを判定する（ｓ１９１→ｓ１９２）。このWhite マークは上述したように未だマークされていない状態を意味する。もし、White マークでなければ、すでにマークされているので、そのまま処理を終了する。White マークであれば、それをGrayにマークする（ｓ１９３）。上述したようにこのGrayマークは参照変更のあったオブジェクトであることを意味する。続いてマークスタックに参照先のオブジェクトを示すデータを積む（ｓ１９４）。
【０１２８】
図４８は上記「オブジェクトに対応するマーク付与」の処理手順を示すフローチャートである。この処理は、生成されているオブジェクトからマークテーブル上の位置を計算し、Black マークを付与する。このBlack マークは上述したように、マークされている状態を意味する。なお、「オブジェクトの生成」の処理は図３９に示したものと同様である。
【０１２９】
このように、参照変更のあったオブジェクトについてマークを付与する場合、そのオブジェクトが初めて検出されたオブジェクトである場合にのみマークを付与するようにしたため、マークスタックの内容によるツリー探索に要する時間およびマークスタックの読み出しに要する時間を短縮化できる。
【０１３０】
なお、参照変更のあったオブジェクトについてのマークを記憶するのはスタックでなくてもよく、ＦＩＦＯのバッファを用いてもよい。
【０１３１】
また、実施形態ではマークテーブルにマークを付与するようにしたが、オブジェクトの内部にマーク用の情報を設けて、オブジェクトに直接マークを付与するようにしてもよい。
【図面の簡単な説明】
【０１３２】
【図１】実施形態に係る装置のハードウエアの構成を示すブロック図
【図２】同装置のソフトウエアの構成を示すブロック図
【図３】オブジェクト間の参照関係を示すツリーおよび各スレッドのスタックとの関係を示す図
【図４】ソフトウエアの機能ブロック図
【図５】コンパクションの作用を説明するための図
【図６】コンテキストスイッチの有無によるスレッドの処理内容の変化の例を示す図
【図７】排他制御の処理手順を示すフローチャート
【図８】コンテキストスイッチ発生有無検出のＡＰＩに関する処理手順を示すフローチャート
【図９】コンテキストスイッチの処理手順を示すフローチャート
【図１０】コンパクションの処理手順を示すフローチャート
【図１１】複写法によるＧＣの処理手順を示すフローチャート
【図１２】複写法ＧＣにおける排他制御の処理手順を示すフローチャート
【図１３】複写法ＧＣにおける他の排他制御の処理手順を示すフローチャート
【図１４】図１３における排他制御用ＡＰＩに関する処理手順を示すフローチャート
【図１５】図１３における排他制御用ＡＰＩに関する処理手順を示すフローチャート
【図１６】ＧＣスレッドの優先度の自動切替の例を示す図
【図１７】スレッドの優先度値および優先度時間の切替に関するフローチャート
【図１８】ＧＣスレッドの高優先度時間を変更した例を示す図
【図１９】ＧＣスレッドの高優先度時間を変更可能とするためのフローチャート
【図２０】ＧＣスレッドの高優先度時間を自動変更する例を示すフローチャート
【図２１】ＧＣスレッドの高・低優先度時間の切り替え周期を変更した例を示す図
【図２２】ＧＣスレッドの高・低優先度時間の切り替え周期を変更するためのフローチャート
【図２３】不定期なＧＣ処理の例を示す図
【図２４】図２１に対応するフローチャート
【図２５】排他制御ＡＰＩによるＧＣスレッドの優先度の強制変更の例を示す図
【図２６】排他制御ＡＰＩによるＧＣスレッドの優先度を強制変更するためのフローチャート
【図２７】ＧＣのアルゴリズムを切り替える処理手順を示すフローチャート
【図２８】生成されるオブジェクトのサイズの分布の例を示す図
【図２９】オブジェクトのメモリの割り当てサイズの例を示す図
【図３０】オブジェクト生成の処理手順を示すフローチャート
【図３１】オブジェクトサイズの分布検知および固定サイズの決定処理に関するフローチャート
【図３２】ヒープ領域の構成を示す図
【図３３】オブジェクト消去の手順を示すフローチャート
【図３４】オブジェクト生成の手順を示すフローチャート
【図３５】マーク＆スイープ法によるＧＣの手順を示すフローチャート
【図３６】マーククリアの処理手順を示すフローチャート
【図３７】オブジェクト消去の処理手順を示すフローチャート
【図３８】ツリー探索によるマーク付与の例を示す図
【図３９】図３８に対応するフローチャート
【図４０】図３８に対応するフローチャート
【図４１】図３８に対応するフローチャート
【図４２】図３８に対応するフローチャート
【図４３】ツリー探索によるマーク付与の例を示す図
【図４４】図４３に対応するフローチャート
【図４５】図４３に対応するフローチャート
【図４６】図４３に対応するフローチャート
【図４７】参照変更のマーク付与の他の処理手順を示すフローチャート
【図４８】オブジェクトに対応するマーク付与の他の処理手順を示すフローチャート
【図４９】固定サイズの設定とオブジェクト生成に関する処理手順を示すフローチャート
【図５０】オブジェクトサイズ分布設定に関する処理手順を示すフローチャート
【図５１】オブジェクトサイズの分布と分割サイズの例を示す図
【図５２】ヒープ領域を所定サイズで分割する処理とオブジェクト生成に関する処理手順を示すフローチャート
【図５３】ヒープ領域を所定サイズで分割する処理に関する処理手順を示すフローチャート
【図５４】従来のマーク＆スイープ法によるＧＣの手順を示すフローチャート
【図１】
2006185456.tif 000003
【図２】
2006185456.tif 000004
【図３】
2006185456.tif 000005
【図４】
2006185456.tif 000006
【図５】
2006185456.tif 000007
【図６】
2006185456.tif 000008
【図７】
2006185456.tif 000009
【図８】
2006185456.tif 000010
【図９】
2006185456.tif 000011
【図１０】
2006185456.tif 000012
【図１１】
2006185456.tif 000013
【図１２】
2006185456.tif 000014
【図１３】
2006185456.tif 000015
【図１４】
2006185456.tif 000016
【図１５】
2006185456.tif 000017
【図１６】
2006185456.tif 000018
【図１７】
2006185456.tif 000019
【図１８】
2006185456.tif 000020
【図１９】
2006185456.tif 000021
【図２０】
2006185456.tif 000022
【図２１】
2006185456.tif 000023
【図２２】
2006185456.tif 000024
【図２３】
2006185456.tif 000025
【図２４】
2006185456.tif 000026
【図２５】
2006185456.tif 000027
【図２６】
2006185456.tif 000028
【図２７】
2006185456.tif 000029
【図２８】
2006185456.tif 000030
【図２９】
2006185456.tif 000031
【図３０】
2006185456.tif 000032
【図３１】
2006185456.tif 000033
【図３２】
2006185456.tif 000034
【図３３】
2006185456.tif 000035
【図３４】
2006185456.tif 000036
【図３５】
2006185456.tif 000037
【図３６】
2006185456.tif 000038
【図３７】
2006185456.tif 000039
【図３８】
2006185456.tif 000040
【図３９】
2006185456.tif 000041
【図４０】
2006185456.tif 000042
【図４１】
2006185456.tif 000043
【図４２】
2006185456.tif 000044
【図４３】
2006185456.tif 000045
【図４４】
2006185456.tif 000046
【図４５】
2006185456.tif 000047
【図４６】
2006185456.tif 000048
【図４７】
2006185456.tif 000049
【図４８】
2006185456.tif 000050
【図４９】
2006185456.tif 000051
【図５０】
2006185456.tif 000052
【図５１】
2006185456.tif 000053
【図５２】
2006185456.tif 000054
【図５３】
2006185456.tif 000055
【図５４】
2006185456.tif 000056