JPH11338761A - 動的メモリ管理機構 - Google Patents

動的メモリ管理機構

Info

Publication number
JPH11338761A
JPH11338761A JP14471398A JP14471398A JPH11338761A JP H11338761 A JPH11338761 A JP H11338761A JP 14471398 A JP14471398 A JP 14471398A JP 14471398 A JP14471398 A JP 14471398A JP H11338761 A JPH11338761 A JP H11338761A
Authority
JP
Japan
Prior art keywords
area
garbage collection
object area
pointer
heap
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP14471398A
Other languages
English (en)
Inventor
Suketada Futamura
祐地 二村
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Priority to JP14471398A priority Critical patent/JPH11338761A/ja
Publication of JPH11338761A publication Critical patent/JPH11338761A/ja
Pending legal-status Critical Current

Links

Abstract

(57)【要約】 【解決手段】 メモリ獲得手段は残利用可能領域の一端
から順次オブジェクト領域を獲得し、ガベージコレクシ
ョン手段は、まず残利用可能領域をTO領域とし、TO
領域に隣接する同量の既獲得済み領域をFROM領域と
し、コピーにより個々のオブジェクト領域を移動させる
形で部分ガベージコレクション処理を行い、次に、TO
領域のうちオブジェクト領域が移動しておらず利用可能
として残った領域と、空になったFROM領域を合わせ
た新しい残利用可能領域を新たなTO領域とし、まだガ
ベージコレクション処理を行ってない既獲得済み領域の
うち新しい残利用可能領域と同量の領域を新たなFRO
M領域として再度部分ガベージコレクション処理を行
い、既獲得済み領域の全体にガベージコレクション処理
が及ぶまで、部分ガベージコレクション処理を繰り返
す。 【効果】 長期間の連続運転が可能で、処理が簡素でそ
の効率が良い。

Description

【発明の詳細な説明】
【0001】
【発明の属する技術分野】この発明は、計算機システム
におけるメモリ管理機構の改良に関し、さらに詳しく述
べればメモリ領域の自動ガベージコレクション手段を有
する動的メモリ管理機構の改良に関するものである。
【0002】
【従来の技術】例えば、特開昭63−253445号公
報に記載された「データ格納効率の改善方法とシステ
ム」における従来技術の記述に示されるように、動的メ
モリ管理機構におけるメモリの自動ガベージコレクショ
ン処理(以下、「ガベージコレクション処理」、または
「GC処理」と記す)は長年研究がなされてきた分野で
あり、多くの関連分岐を含む技術開発が行われている。
【0003】ガベージコレクション処理の目的は、計算
機システム内で動作するプログラムがその動作中に動的
メモリ管理機構から獲得し利用する記憶領域について、
プログラムが使わなくなった記憶領域を明示的に開放し
なくても、自動的に回収し再利用できるようにし、記憶
領域の有効活用を図れるようにすることである。
【0004】ガベージコレクション処理は、概念的には
2つの段階で構成される。最初の段階では、プログラム
が使用している記憶領域(「生きている」)と、プログ
ラムが使わなくなった記憶領域(「ごみ」)の区別を行
う。そして、次の段階で、「ごみ」を回収し再び利用で
きるようにする。ガベージコレクション処理において動
的メモリ管理機構内の記憶領域が「生きている」か「ご
み」であるかの区別は、記憶領域に対するプログラムか
らの到達可能性によって判断される。まず、動的メモリ
管理機構の外部にあるデータに基づきプログラムが参照
できる記憶領域は「生きている」記憶領域である。次
に、「生きている」記憶領域が保持するデータに基づき
プログラムが参照できる記憶領域も「生きている」記憶
領域と定める。これは再帰的に定義される。「ごみ」の
記憶領域は「生きていない」記憶領域であり、動的メモ
リ管理機構の外部にあるデータと「生きている」記憶領
域が保持するデータのどちらを用いてもプログラムが参
照できない記憶領域と定義される。
【0005】図35は、ガベージコレクション処理にお
ける「生きている」記憶領域と「ごみ」の区別を示す解
説図である。動的メモリ管理機構1は、計算機システム
のメモリ領域の一部であるヒープ領域2を含み、同ヒー
プ領域2内にはプログラムが使用する記憶領域であるオ
ブジェクト領域10が1ないし複数存在している。ポイ
ンタ12は、プログラムがオブジェクト領域10を参照
するために用いるデータで、図35ではオブジェクト領
域A、B、X、Yがそれぞれ1ないし2のポインタ12
を含むほか、動的メモリ管理機構1の外部にも2つのポ
インタRp1及びRp2が存在する。
【0006】図35において、オブジェクト領域A及び
オブジェクト領域Dは、それぞれ動的メモリ管理機構1
の外部にあるポインタRp1およびRp2を用いてプロ
グラムが参照可能であるため、共に「生きている」オブ
ジェクト領域10とみなされる。「生きている」オブジ
ェクト領域A内に含まれるポインタ12から参照可能な
オブジェクト領域B及びCもまた「生きている」オブジ
ェクト領域10である。一方、オブジェクト領域X、Y
並びにZは、動的メモリ管理機構1の外部のポインタR
p1あるいはRp2から、直接にも、他の「生きてい
る」オブジェクト領域10経由でもプログラムから参照
できないため、これらのオブジェクト領域は「ごみ」と
みなされる。
【0007】ガベージコレクション処理として提案され
ている各種の方式間の違いは、上記の概念的な2つの段
階を具体的にはどのように実行するかの違いである。ガ
ベージコレクション処理に関する主要な従来技術として
は、基本方式として、「参照カウンタ方式」、「マーク
−スイープ方式」、並びに「ストップ−コピー方式」の
3方式があり、またその重要な改良として「インクリメ
ンタル(歩進)方式」と「ジェネレーショナル(世代)
方式」の2つの方向が挙がる。以下、従来技術とその問
題点を示す。
【0008】図36は、第1の従来例である、単純な
「参照カウンタ方式」でガベージコレクション処理を行
う動的メモリ管理機構の構成図である。動的メモリ管理
機構1は、計算機システムのメモリ領域の一部であるヒ
ープ領域2と、同ヒープ領域2からその一部をオブジェ
クト領域10として獲得するメモリ獲得手段3と、獲得
した同オブジェクト領域10を同ヒープ領域2に戻し再
利用可能とするメモリ開放手段4と、同メモリ獲得手段
3により獲得されたがプログラムから利用されなくなっ
たオブジェクト領域10を探索し、同メモリ開放手段4
を用いて同ヒープ領域2に開放するガベージコレクショ
ン手段5から構成される。同ヒープ領域2は、そのアド
レスが連続する単一のメモリ領域であることが多いが、
計算機システムによっては複数のメモリ領域から構成さ
れている場合もある。
【0009】同ヒープ領域2には、1ないし複数のオブ
ジェクト領域10が存在し得る。個々のオブジェクト領
域は、メモリ獲得手段3によって生成され、メモリ開放
手段4によって消去される、ヒープ領域2内の小さなメ
モリ領域である。オブジェクト領域10の中にはプログ
ラムの動作に必要な各種の情報が適宜保持される。オブ
ジェクト領域10が保持する情報はプログラムの開発言
語やプログラム設計に大きく依存し、プログラムの動作
に必要なデータだけを含む場合もあれば、プログラムの
命令コードも含む場合もある。
【0010】各オブジェクト領域10は、それぞれ参照
カウンタ11を持つ。これは参照カウンタ方式のガベー
ジコレクション処理における特徴的な構造である。参照
カウンタ11は、整数値を保持する変数であり、その値
は、対応するオブジェクト領域10がいくつのポインタ
12から参照されているかを示す。
【0011】ポインタ12は、ガベージコレクション処
理を行うときに考慮が必要なプログラムのデータであ
る。ポインタ12は、プログラムがオブジェクト領域1
0を参照するため必要な情報を保持する記憶領域であ
り、計算機のCPUレジスタや、プログラムが静的に配
置したメモリ領域やスタック内の変数(小さなメモリ領
域)、オブジェクト領域10内の変数として存在する。
【0012】次に、本従来例の動作について説明する。
図37は、本従来例におけるオブジェクト領域獲得の動
作を示すフローチャートである。オブジェクト領域10
の獲得の動作では、まずヒープ領域2内の未使用部分か
らプログラムにより明示的あるいは暗示的に指定された
適切な大きさのメモリ領域を獲得し(P1101)、次
に獲得した領域をオブジェクト領域10とみなしてその
参照カウンタ11の値を0に設定し(P1102)、さ
らに必要に応じて獲得したオブジェクト領域内のその他
の場所(データ)の初期化を行い(P1103)、その
後オブジェクト領域10を参照するために必要なポイン
タの値を返す(P1104)。ここで、手順P1102
で参照カウンタ11の値を0とするのは、新たに生成し
たオブジェクト領域10が、まだどこのポインタ12か
らも参照されておらず、同オブジェクト領域を参照する
ポインタ12の数が0であることによる。
【0013】参照カウンタ11の値の更新は、ポインタ
12の値の変更と同期して行われる。図38は、本従来
例におけるポインタ12の値の変更の動作を示すフロー
チャートである。ポインタ12の値の変更の動作P12
0では、まずその値を変更するポインタ12が保持する
値の有効性を検査する(P1201)。もしポインタ1
2が値の変更に先立ちオブジェクト領域10を参照して
いれば(P1201のYes)、本変更により参照先の
オブジェクト領域10を参照するポインタの数が減るの
で、同オブジェクト領域10の参照カウンタ11の値を
1減算する(P1202)。その結果参照カウンタ11
の値が0であれば(P1203のYes)、対象とする
オブジェクト領域10はどこのポインタ12からも参照
されていないオブジェクト領域10、すなわち「ごみ」
となったので、そのオブジェクト領域10の開放を行
う。
【0014】オブジェクト領域10の開放では、対象オ
ブジェクト領域10が開放されることで他の1ないし複
数のオブジェクト領域10を参照するポインタも失わ
れ、その結果他のオブジェクト領域10の参照カウンタ
12の値についても調整を行わなければならない場合が
ある。このため、もし対象とするオブジェクト領域10
がその内部に1ないし複数のポインタ12を持っていれ
ば(P1204のYes)、オブジェクト領域10内に
存在するすべてのポインタ12についてそのそれぞれの
値を、ポインタ12の値の変更の動作P120を再帰的
に用いることで、無効な値(オブジェクト領域を参照し
ない値、通常0ないしNULL)に設定し(P120
6、P1207、P1208)、その後メモリ開放手段
4を用い同オブジェクト領域10を開放する(P120
9)。
【0015】その後は、まずポインタ12の値を新しい
値に設定し(P1210)、もしその値が有効でオブジ
ェクト領域を参照していれば(P1211のYes)、
参照先のオブジェクト領域を参照するポインタの数が増
えるので、同オブジェクト領域10の参照カウンタ11
の値を1加算し(P1212)、処理を終える。
【0016】なお、値を変更する前のポインタ12が参
照するオブジェクト領域10の参照カウンタ11を1減
算しても、参照カウンタ11の値は0にならなければ
(P1203のNo)、対象とするオブジェクト領域1
0は、まだ他のポインタ12から参照されており、使用
中のオブジェクト領域10であるので、オブジェクト領
域の開放処理は行わず、速やかにポインタ12に新しい
値を設定する(P1210)。これは、値を変更する前
のポインタ12の値が無効な値であった場合(P120
1のNo)も同様で、速やかにポインタ12に新しい値
を設定する(P1210)。また、ポインタに設定する
新しい値が無効な値であれば(P1211のNo)、更
新すべき参照カウンタ11が存在しないので手順P12
12は行わず、速やかに処理を終える。
【0017】本従来例の具体的な動作の様子を図39、
図40、図41、及び図42を用いて説明する。
【0018】図39は、本従来例の第1の動作の実施前
を示す解説図である。図39において、ポインタRpは
計算機のCPUレジスタ、プログラムが静的に配置した
メモリ領域、あるいはスタック内の変数として、ヒープ
領域2の外部に存在するポインタ12であり、第1のオ
ブジェクト領域Aを参照している。オブジェクト領域A
はその内部にポインタAp1およびポインタAp2を保
持し、ポインタAp1は第2のオブジェクト領域Bを、
またポインタAp2は第3のオブジェクト領域Cを参照
している。オブジェクト領域Bはその内部にポインタB
p1およびポインタBp2を保持し、ポインタBp1は
ポインタAp2同様オブジェクト領域Cを参照している
が、ポインタBp2はいずれのオブジェクト領域も参照
せず無効な値を保持している。オブジェクト領域Cはそ
の内部にポインタ12を保持しない。オブジェクト領域
AはポインタRpからのみ参照されているので、オブジ
ェクト領域Aの参照カウンタAc1の値は1である。同
様に、オブジェクト領域BはポインタAp1からのみ参
照されているので、その参照カウンタBc1の値は1で
あり、オブジェクト領域CはポインタAp2とポインタ
Bp1から参照されているので、その参照カウンタCc
1の値は2である。
【0019】図39に示される状況において、ポインタ
Rpを無効な値に変更する動作P120は次の通りとな
る。変更前のポインタRpの値はオブジェクト領域Aを
参照する有効な値なので、P1201、P1202と進
む。P1202の結果、参照カウンタAc1の値は0と
なるので、P1203のYesへ進み、さらにオブジェ
クト領域Aは内部にポインタAp1およびAp2を含む
ので、P1204のYesからP1205へと処理を進
め、まずポインタAp1についてP1206を実行す
る。P1206ではポインタAp1に対しP120を再
帰的に実行、これによりポインタAp1の参照するオブ
ジェクト領域Bの参照カウンタBc1の値が1から0に
減少し(ポインタAp1に対するP120内のP120
2)、オブジェクト領域Bの保持するポインタBp1の
参照先であるオブジェクト領域Cの参照カウンタCc1
の値も1減じられたのち(ポインタBp1に対するP1
20内のP1202)、オブジェクト領域Bは開放され
(ポインタAp1に対するP120内のP1209)、
ポインタAp1の値は無効な値に設定される(ポインタ
Ap1に対するP120内のP1210)。図40は、
本段階の状況を示す解説図であり、図39に対し、参照
カウンタAc1、参照カウンタBc1、参照カウンタC
c1がすべて1減じられ、オブジェクト領域Bが開放さ
れ(破線)、ポインタAp1およびポインタBp1に無
効な値に設定されている。
【0020】P1206でのポインタAp1に対するP
120の実行が終了すると、処理はP1207のNo、
P1208と進み、続くP1206では今度はポインタ
Ap2に対しP120を再帰的に実行する。これにより
ポインタAp2の参照するオブジェクト領域Cの参照カ
ウンタCc1の値が1から0に減少し(ポインタAp2
に対するP120内のP1202)、オブジェクト領域
Cもまた開放され(ポインタAp2に対するP120内
のP1209)、ポインタAp2の値は無効な値に設定
される(ポインタAp2に対するP120内のP121
0)。図41は、本段階の状況を示す解説図であり、図
40に対し、参照カウンタCc1が1減じられ、オブジ
ェクト領域Cが開放され(破線)、ポインタAp2が無
効な値に設定されている。
【0021】P1206でのポインタAp2に対するP
120の実行が終了し、オブジェクト領域A内のすべて
のポインタを無効に設定し終えると(P1207のYe
s)、オブジェクト領域Aを開放(P1209)したの
ちポインタRpの値を無効な値に設定し(P121
0)、その後P120を終える。図42は、本段階の状
況を示す解説図であり、図41に対しオブジェクト領域
Aが開放され(破線)、ポインタRpが無効な値に設定
され、結果としてオブジェクト領域A、オブジェクト領
域B、オブジェクト領域Cはすべて開放される。
【0022】本従来例に示した参照カウンタ方式のガベ
ージコレクション処理は上記のように動作することで、
「ごみ」の識別と回収、再利用を実現している。参照カ
ウンタ方式は、上記のようにガベージコレクション処理
が応用プログラムの動作の延長上で少しずつ行われると
いう特徴および長所がある。しかし一方で循環した参照
により「ごみ」を回収し損ねるという問題がある。本問
題の具体的な様子を図43、及び図44を用いて示す。
【0023】図43は、本従来例の第2の動作の実施前
を示す解説図である。図43において、ポインタRpは
図39同様、ヒープ領域2の外部に存在するポインタ1
2であり、本図では第1のオブジェクト領域Dを参照し
ている。オブジェクト領域Dはその内部にポインタDp
1およびポインタDp2を保持し、ポインタDp1は第
2のオブジェクト領域Eを、またポインタDp2は第3
のオブジェクト領域Fを参照している。オブジェクト領
域Eはその内部にポインタEp1およびポインタEp2
を保持し、ポインタEp1はポインタDp2同様オブジ
ェクト領域Fを参照しているが、ポインタEp2はいず
れのオブジェクト領域も参照せず無効な値を保持してい
る。オブジェクト領域Fはその内部にポインタFp1を
保持し、ポインタFp1はオブジェクト領域Eを参照し
ている。オブジェクト領域DはポインタRpからのみ参
照されているので、オブジェクト領域Dの参照カウンタ
Dc1の値は1である。同様に、オブジェクト領域Eは
ポインタDp1とポインタFp1から参照されているの
で、その参照カウンタEc1の値は2であり、オブジェ
クト領域FはポインタDp2とポインタEp1から参照
されているので、その参照カウンタFc1の値も2であ
る。
【0024】図43に示される状況においてポインタR
pを無効な値に変更する動作P120は次の通りとな
る。変更前のポインタRpの値はオブジェクト領域Dを
参照する有効な値なので、P1201、P1202と進
む。P1202の結果、参照カウンタDc1の値は0と
なるので、P1203のYesへ進み、さらにオブジェ
クト領域Dは内部にポインタDp1およびDp2を含む
ので、P1204のYesからP1205へと処理を進
め、まずポインタDp1についてP1206を実行す
る。P1206ではポインタDp1に対しP120を再
帰的に実行、これによりポインタDp1の参照するオブ
ジェクト領域Eの参照カウンタEc1の値が2から1に
減少する(ポインタDp1に対するP120内のP12
02)。しかし、ここでは前述の本従来例の第1の動作
と異なり、オブジェクト領域Eの参照カウンタEc1の
値は0にならないため、オブジェクト領域Eは開放され
ることなく(ポインタDp1に対するP120内のP1
203のNo)、ポインタDp1の値が無効な値に設定
される(ポインタDp1に対するP120内のP121
0)。
【0025】P1206でのポインタDp1に対するP
120の実行が終了すると、処理はP1207のNo、
P1208と進み、続くP1206では今度はポインタ
Dp2に対しP120を再帰的に実行する。これにより
ポインタDp2の参照するオブジェクト領域Fの参照カ
ウンタFc1の値が2から1に減少するが(ポインタD
p2に対するP120内のP1202)、やはり本従来
例の第1の動作と異なり、オブジェクト領域Fの参照カ
ウンタFc1の値は0にならないため、オブジェクト領
域Fも開放されることなく(ポインタDp2に対するP
120内のP1203のNo)、ポインタDp2の値は
無効な値に設定される(ポインタDp2に対するP12
0内のP1210)。
【0026】P1206でのポインタDp2に対するP
120の実行が終了し、オブジェクト領域D内のすべて
のポインタを無効に設定し終えると(P1207のYe
s)、オブジェクト領域Dを開放(P1209)したの
ち、ポインタRpの値を無効な値に設定し(P121
0)、その後P120を終える。図44は、本段階の状
況を示す、本従来例の第2の動作実施後を示す解説図で
あり、図43に対し参照カウンタEc1及び参照カウン
タFc1が減じられ、オブジェクト領域Dが開放され
(破線)、ポインタRpが無効な値に設定されている
が、結果として、オブジェクト領域Eおよびオブジェク
ト領域Fは、ヒープ領域外のポインタあるいは「生きて
いる」オブジェクト領域を経由してプログラムから参照
することができない「ごみ」となったオブジェクト領域
であるにも関わらず、その領域を開放できない。
【0027】上記の本従来例の第2の動作に示した、参
照カウンタ方式における「ごみ」回収漏れの問題は、動
的メモリ管理機構内で使用可能なヒープ領域2の見かけ
の大きさが次第に小さくなるという、メモリリーク現象
を引き起こす。本現象の発生は計算機システムが長期連
続運転できないことを意味し、長期間にわたる無停止運
転が前提の産業系計算機システムでは許容することがで
きない。よって参照カウンタ方式は「ごみ」の回収漏れ
をさけるため、他の方式との併用が必要であることが指
摘されている。
【0028】また、上記第1の従来例に示した単純な参
照カウンタ式のガベージコレクション処理では、開放す
るオブジェクト領域10が内部に有効なポインタ12を
持つ場合、そのポインタ12の指すオブジェクト領域1
0に対しても再帰的に参照カウンタの値の調整処理を行
うので(P1206)、1つのオブジェクト領域10の
開放が連鎖的に多数のオブジェクト領域10の開放につ
ながる場合があり、ポインタの値の変更の動作P120
に要する時間が不定で予測困難であるという問題があ
る。本問題に対する対策として第2の従来例を説明す
る。
【0029】第2の従来例は、上記の第1の従来例にお
けるポインタの値の変更の動作を改善したものであり、
その構成及びオブジェクト領域の獲得の動作は、それぞ
れ第1の従来例の構成(図36)及び第1の従来例にお
けるオブジェクト領域の獲得の動作(図37)と同一で
あるので、説明を省略する。第2の従来例におけるポイ
ンタの値の変更の動作およびガベージコレクション処理
(GC処理)の動作を図45を用いて説明する。
【0030】図45は、第2の従来例の動作を示すフロ
ーチャートである。第2の従来例におけるポインタ12
の値の変更の動作P130でも、まず第1の従来例の手
順P120と同じく、ポインタ12が保持する値を検査
し(P1201)、もしポインタ12が有効なオブジェ
クト領域10を参照していれば(P1201のYe
s)、参照するオブジェクト領域10の参照カウンタ1
1の値を1減算する(P1202)。しかし、その結果
参照カウンタ11の値が0であったときは(P1203
のYes)、即座にオブジェクト領域10開放の処理を
行うのではなく、一旦参照するオブジェクト領域10を
ごみリスト21に追加する(P1301)にとどめる。
この点が第1の従来例におけるポインタ12の値の変更
の動作P120と異なる特徴である。その後は、また第
1の従来例の手順P120と同じく、ポインタ12の値
を新しい値に設定し(P1210)、もしその値が有効
でオブジェクト領域を参照していれば(P1211のY
es)、同オブジェクト領域10の参照カウンタ11の
値を1加算し(P1212)、処理を終える。なお、値
を変更する前に参照しているオブジェクト領域10の参
照カウンタ11を1減算しても、参照カウンタ11の値
は0にならなければ(P1203のNo)、対象とする
オブジェクト領域10の開放のための処理は行わず速や
かにポインタ12に新しい値を設定する(P121
0)、値を変更する前のポインタ12の値が無効な値で
あった場合(P1201のNo)も速やかにポインタ1
2に新しい値を設定する(P1210)、ポインタに設
定する新しい値が無効な値あれば(P1211のN
o)、更新すべき参照カウンタ11が存在しないので手
順P212は行わず、速やかに処理を終える点も、第1
の従来例と同じである。
【0031】手順P1301で、ごみリスト21につな
がれたオブジェクト領域10は、別途応用プログラムの
動作とは平行して適宜動作するガベージコレクション処
理(GC処理)P131によって開放される。
【0032】手順P131では、まず、ごみリスト21
に含まれ開放の対象となっているオブジェクト領域10
の有無を調べ(P1311)、もしあれば(P1311
のYes)、ごみリストから開放すべき未処理のオブジ
ェクト領域10を1つ選択する(P1312)。なおこ
のとき、もしごみリスト21が空で開放すべきオブジェ
クト領域10は存在しなければ(P1311のNo)、
速やかに処理を終える。ついで手順P1312で選択し
たオブジェクト領域10について、そのオブジェクト領
域10が内部にポインタ12を保持していれば(P13
13のYes)、そのなかからまず1つの未処理のポイ
ンタ12を選択し(P1314)、その値が有効である
かを調べ(P1201)、有効であれば(P1201の
Yes)そのポインタ12が参照するオブジェクト領域
10の参照カウンタ11の値を1減算し(P120
2)、その結果参照カウンタの値が0になれば(P12
03のYes)、そのポインタ12が参照するオブジェ
クト領域10を開放すべく新たにごみリスト21に加え
る(P1301)。ついでさらに未処理のポインタ12
があれば(P1315のNo)、未処理のポインタ12
について手順P1201、P1202、P1203、P
1301を繰り返したうえで、ごみリストから獲得し開
放の対象となっているオブジェクト領域10自体をメモ
リ開放手段4を用いて開放する。その後は、まだごみリ
ストに開放すべき他のオブジェクト領域10が存在すれ
ば(P1316のNo)、未処理のオブジェクト領域1
0についてさらに手順P1312、P1313....
と上記の処理を繰り返す。
【0033】第2の従来例では上記のように動作するこ
とで、第1の従来例とは異なり、応用プログラムの処理
の一部として実行されるポインタの値の変更の動作P1
30に要する時間が予測可能となるという特徴および長
所がある。しかし、第1の従来例に比べ、応用プログラ
ムの処理とは独立してガベージコレクション処理P13
1を稼動させなければならず、その処理は複雑となる。
また、手順P131は、高い頻度で動作させればシステ
ムの負荷になり、低い頻度で動作させれば応用プログラ
ムの動作に「ごみ」オブジェクト領域の回収、再利用が
間に合わなくなるため、どのように動作させるか定める
ことが難しい。さらに、第1の従来例同様、循環した参
照により「ごみ」の回収漏れが発生する欠点は残ってお
り、やはり他の方式との併用が必要で、併用する他の方
式と手順P131の動作の相互干渉の回避も必要とな
り、これらを考慮すると処理はさらに複雑になるという
問題点がある。
【0034】次に、第3の従来例を用いて、マーク−ス
イープ方式と呼ばれるガベージコレクション処理につい
て説明する。マーク−スイープ方式は、第1および第2
の従来例で示した参照カウンタ方式における循環した参
照による「ごみ」の回収漏れ問題を改善している方式で
ある。
【0035】図46は、第3の従来例である、マーク−
スイープ方式でガベージコレクション処理を行う動的メ
モリ管理機構の構成図である。図46において、動的メ
モリ管理機構1、ヒープ領域2、ガベージコレクション
手段5、オブジェクト領域10、ポインタ12は、図3
6と同じであるので説明を省略する。ヒープ領域2は、
さらに、未だ利用されていないメモリ領域から構成され
る残利用可能領域13と、既にプログラムから利用され
ているメモリ領域から構成される既獲得済み領域14の
2つの領域から構成される。オブジェクト領域10は、
まずメモリ獲得手段3によりヒープ領域2の一部である
残利用可能領域13から獲得され、これにより獲得され
たオブジェクト領域10は既獲得済み領域14の一部を
構成するようになる。また、オブジェクト領域10はメ
モリ開放手段4によって開放されると、再び残利用可能
領域13の一部を構成するようになり、その領域は再利
用可能となる。残利用可能領域13内の利用可能なメモ
リ領域はフリーリスト18により管理され、オブジェク
ト領域10は、メモリ獲得手段3によりフリーリスト1
8内の適切な領域が割当てられることで獲得され、メモ
リ開放手段4によりフリーリスト18に戻されるよう動
作する。
【0036】既獲得済み領域14には、1ないし複数の
オブジェクト領域10が存在し得る。第1の従来例と異
なり、参照カウンタ11は持たないが、代わりにマーク
20の領域を持つ。これはマーク−スイープ方式または
その類型のガベージコレクション処理における特徴的な
構造である。このマークは、主に対応するオブジェクト
領域が使用中とみなせるか否かの状態を保持する変数で
あり、ガベージコレクション処理の中で操作される。
【0037】次に、本従来例の動作について説明する。
図47は、本従来例におけるガベージコレクション処理
(GC処理)の動作を示すフローチャートである。本従
来例におけるガベージコレクション処理は、大きく4つ
の段階を踏む。まず最初に、既獲得済み領域14内に存
在するすべてのオブジェクト領域10のマーク20を
「未使用」と印付ける(P1401)。次に計算機のC
PUレジスタ、プログラムが静的に配置したメモリ領
域、あるいはスタック内の変数としてヒープ領域2の外
部に存在するすべてのポインタ12について、それらの
ポインタ12から直接参照されるオブジェクト領域10
を探索し、そのマーク20を「使用中」と印付けする
(P141)。その後、既獲得済み領域14にあってマ
ーク20が「使用中」となっているオブジェクト領域1
0を探索し、該当するオブジェクト領域10から参照さ
れるオブジェクト領域10についてもマーク20を「使
用中」とする(P142)。手順P141、P142に
よりヒープ領域外のポインタ12から直接または間接に
参照できるすべてのオブジェクト領域10のマーク20
を「使用中」としたので、本段階でマークが「未使用」
となっている既獲得済み領域14内のオブジェクト領域
10は「ごみ」とみなすことができ、最後に既獲得済み
領域14内でマーク20が「未使用」のオブジェクト領
域10すべてをメモリ開放手段4を用いて開放する(P
143)。
【0038】次に、手順P141、P142、P143
の詳細を示す。手順P141では、まずヒープ領域2外
にある適切なポインタ12の1つを選択し(P141
1)、そのポインタ12が有効であれば(P1201の
Yes)、ポインタ12が参照するオブジェクト領域1
0のマーク20を「使用中」とし(P1412)、本手
順をヒープ領域2の外にあるすべてのポインタ12につ
いて繰り返す(P1413のYes、P1414)。
【0039】手順P142では、既獲得済み領域14内
にマーク20が「使用中」であるオブジェクト領域10
があれば(P1421のYes)、まず該当するオブジ
ェクト領域10を1つ選択し(P1422)、選択した
オブジェクト領域10が内部にポインタ12を含めば
(P1313のYes)、まず選択したオブジェクト領
域10に含まれるポインタ12の1つを選び(P131
4)、その値が有効で参照先オブジェクト領域10のマ
ーク20が「未使用」であれば(P1201のYe
s)、参照先のオブジェクト領域10のマーク20を
「使用中」に設定し探索対象に加え(P1424)、本
手順を選択したオブジェクト領域10の内部に含まれる
すべてのポインタ12に繰り返し行い(P1315のN
o)、さらに既獲得済み領域14内でマーク20が「使
用中」のオブジェクト領域10のすべてについて上記手
順を繰り返す(P1425)。
【0040】手順143では、既獲得済み領域14内に
あるマーク20が「未使用」のオブジェクト領域10を
選択し(P1431)、選択したオブジェクト領域10
をメモリ開放手段4を用いて開放、フリーリスト18に
つなげ(P1209)、本手順を既獲得済み領域14内
にあるマーク20が「未使用」のオブジェクト領域10
に対し繰り返す(P1432のNo)。
【0041】本従来例の具体的な動作の様子を図48を
用いて説明する。
【0042】図48は、本従来例の動作を示す解説図で
ある。図48に示される処理前の状況は、ヒープ領域2
内に6つのオブジェクト領域10があり、各オブジェク
ト領域10はその内部に存在するポインタ12により相
互に参照が行われており、さらに一部はヒープ領域2外
のポインタ12から参照されている。本状態に対し手順
P1401、P141、P142を行った段階が、図4
8に示される有効オブジェクト領域検索後の状況であ
り、ヒープ領域外のポインタ12からの到達可否状況に
応じて、各オブジェクト領域10のマーク20の値が
「使用中(1)」または「未使用(0)」に設定されて
いる。さらに、本状態に対し手順P143を行いガベー
ジコレクション処理が終了した段階が、図48に示され
る未使用オブジェクト領域解放後の状況であり、マーク
20が「未使用(0)」であった2つのオブジェクト領
域は、相互に循環した参照があるにも関わらず開放さ
れ、フリーリスト18の一部に組み込まれている。
【0043】本従来例に示したマーク−スイープ方式の
ガベージコレクション処理は上記のように動作するの
で、参照カウンタ方式では回収し損ねた循環した参照の
あるオブジェクト領域10も正しく回収できる。しか
し、マーク−スイープ方式には、まだいくつかの問題が
ある。その1つは、ガベージコレクション処理は一括し
て行わなければならないことであり、参照カウンタ方式
に比べ応用プログラムの中断時間がかなり長くなるとい
う欠点がある。もう1つは、フラグメンテーションと呼
ばれる現象が発生することである。これは参照カウンタ
方式でも同様であるが、マーク−スイープ方式ではオブ
ジェクト領域は一度獲得されると開放されるまでその位
置は不変であるため、応用プログラムの動作に伴い各種
の大きさのオブジェクト領域10の獲得および開放を繰
り返していくと、ヒープ領域2内の使用可能なメモリ領
域が細分化されていき、次第に大きなオブジェクト領域
が獲得できなくなる現象である。メモリリーク現象同
様、本現象の発生は計算機システムが長期連続運転でき
ないことを意味し、長期間にわたる無定試運転が前提の
産業系計算機システムでは許容することができない。本
問題に対する対策として第4の従来例を説明する。
【0044】第4の従来例は、マーク−コンパクト方式
と呼ばれるガベージコレクション処理であり、これは第
3の従来例で示したマーク−スイープ方式において、フ
ラグメンテーション現象の問題を改善した方式である。
【0045】図49は、第4の従来例である、マーク−
コンパクト方式でガベージコレクション処理を行う動的
メモリ管理機構の構成図である。図49において、動的
メモリ管理機構1、ヒープ領域2、ガベージコレクショ
ン手段5、オブジェクト領域10、ポインタ12、マー
ク20、残利用可能領域13、既獲得済み領域14は図
46と同じであるので説明を省略する。
【0046】図49に示す第4の従来例の構成と図46
に示す第3の従来例の構成との大きな違いは、第4の従
来例では残利用可能領域13内の利用可能なメモリ領域
がフリーリスト18を用いて管理されていないことであ
る。第4の実施例では、オブジェクト領域10は、メモ
リ獲得手段3によりヒープ領域の一部である残利用可能
領域13から獲得され、獲得されたオブジェクト領域1
0は既獲得済み領域14の一部を構成するようになる
が、メモリ開放手段4はガベージコレクション手段5に
組み込まれて動作し、オブジェクト領域10はメモリ開
放手段4によって個別に開放されることはなく、ガベー
ジコレクション処理の中で一括して開放される。
【0047】次に、本従来例の動作について説明する。
図50は、本従来例におけるガベージコレクション処理
(GC処理)の動作を示すフローチャートである。本従
来例におけるガベージコレクション処理は、第3の従来
例のガベージコレクション処理と同様、大きく4つの段
階を踏み、しかも最後の段階以外は同一の処理を行う。
すなわち、本従来例でも、まず最初に、既獲得済み領域
14内に存在するすべてのオブジェクト領域10のマー
ク20を「未使用」と印付け(P1401)、次にヒー
プ領域2の外部に存在するすべてのポインタ12につい
て、それらのポインタ12から直接参照されるオブジェ
クト領域10を探索し、そのマーク20を「使用中」と
印付けし(P141)、その後、既獲得済み領域14に
あってマーク20が「使用中」となっているオブジェク
ト領域10を探索し、該当するオブジェクト領域10か
ら参照されるオブジェクト領域10についてもマーク2
0を「使用中」とする(P142)。手順P141、P
142によりヒープ領域外のポインタ12から直接また
は間接に参照できるすべてのオブジェクト領域10のマ
ーク20を「使用中」としたので、本段階でマークが
「未使用」となっている既獲得済み領域14内のオブジ
ェクト領域10は「ごみ」とみなすことができる。
【0048】本従来例の最後の段階では、既獲得済み領
域14内でマーク20が「未使用」のオブジェクト領域
10の開放として、残利用可能領域13とマーク20が
「未使用」のオブジェクト領域10を1つにまとめ、新
たに残利用可能領域13と既獲得済み領域14を設定す
る(P151)。すなわち、まずヒープ領域2の一端を
探索開始端と定め、同探索開始端側から既獲得済み領域
14内に存在しマーク20が「使用中」のオブジェクト
領域を選択(P1511)、同オブジェクト領域10と
ヒープ領域2の探索開始端との間に空き領域があれば
(P1512のYes)、空きを無くすよう同オブジェ
クト領域10をコピーして移動し間を詰める(P151
3)。本手順を既獲得済み領域14内にあるマーク20
が「使用中」のオブジェクト領域10すべてに対して行
うことで(P1514のNo、P1515)、「使用
中」のオブジェクト領域10をヒープ領域の探索開始端
側にまとめ、ヒープ領域2のなかで、「使用中」オブジ
ェクト領域10が集まった部分を新しい既獲得済み領域
14、他の部分を残利用可能領域13とする(P151
6)。
【0049】本従来例の具体的な動作の様子を図51を
用いて説明する。
【0050】図51は、本従来例の動作を示す解説図で
ある。図51に示される処理前の状況は、既獲得済み領
域14内に6つのオブジェクト領域10があり、各オブ
ジェクト領域10はその内部に存在するポインタ12に
より相互に参照が行われており、さらに一部はヒープ領
域2外のポインタ12から参照されている。本状態に対
し手順P1401、P141、P142を行った段階
が、図51に示される有効オブジェクト領域検索後の状
況であり、ヒープ領域外のポインタ12からの到達可否
状況に応じて、各オブジェクト領域10のマーク20の
値が「使用中(1)」または「未使用(0)」に設定さ
れている。さらに、本状態に対し手順P151を行いガ
ベージコレクション処理が終了した段階が、図51に示
される未使用オブジェクト領域解放後の状況であり、マ
ーク20が「未使用(0)」であった2つのオブジェク
ト領域は、相互に循環した参照があるにも関わらず開放
され、さらにマークが「使用中(1)」のオブジェクト
領域はヒープ領域2の左端に集められ、その全体が新し
い既獲得済み領域14となり、ヒープ領域2の残りの部
分が新しい残利用可能領域13となっている。
【0051】本従来例に示したマーク−コンパクト方式
のガベージコレクション処理は上記のように動作するの
で、第3の従来例に示したマーク−スイープ方式と異な
りフラグメンテーション現象の問題が回避される。しか
し、マーク−コンパクト方式にも、まだいくつか問題が
ある。それらはフラグメンテーション現象の発生を避け
るため、ガベージコレクション処理の中でオブジェクト
領域の移動を行っていることにより発生する問題であ
り、その1つは、オブジェクト領域の移動のために行う
領域のコピー動作は重い処理であるため、マーク−スイ
ープ方式より、さらに応用プログラムの中断時間が長く
なるという欠点である。もう1つは、オブジェクト領域
の移動P1513に伴い、移動したオブジェクト領域を
参照しているポインタ12の参照先も移動先を示すよう
補正しなければならないが、その処理が複雑になるとい
う点である。
【0052】次に、第5の従来例を用いて、ストップ−
コピー方式と呼ばれるガベージコレクション処理につい
て説明する。ストップ−コピー方式は第3および第4の
従来例で示したマーク−スイープ方式およびマーク−コ
ンパクト方式を更に改良した方式と位置づけられる。
【0053】図52は、第5の従来例である、ストップ
−コピー方式と呼ばれるガベージコレクション処理を行
う動的メモリ管理機構の構成である。図52において、
動的メモリ管理機構1、ヒープ領域2、ガベージコレク
ション手段5、オブジェクト領域10、ポインタ12は
図49と同じであるので説明を省略する。
【0054】図52に示す第5の従来例の構成と図49
に示す第4の従来例の構成との違いは2つある。その1
つは、第5の従来例ではオブジェクト領域10内にマー
ク20が必要ないことである。もう1つは、第5の従来
例では残利用可能領域13および既獲得済み領域14に
代え、TO領域15およびFROM領域16がヒープ領
域2内に存在することである。TO領域15とFROM
領域16は同じ大きさの領域であり、多くの場合それぞ
れヒープ領域2の半分を占める領域として設定される。
本従来例では、メモリ獲得手段3は必ずFROM領域1
6内からオブジェクト領域10を獲得する。メモリ開放
手段4はガベージコレクション手段5に組み込まれて動
作し、オブジェクト領域10を個別に開放することはな
い。
【0055】次に、本従来例の動作について説明する。
図53は、本従来例におけるガベージコレクション処理
(GC処理)の動作を示すフローチャートである。本従
来例におけるガベージコレクション処理は大きく3つの
段階を踏む。まず最初に、第3の従来例における手順P
141と類似した手順で、ヒープ領域2の外部に存在す
るすべてのポインタ12について、それらのポインタ1
2から直接参照されるFROM領域16内のオブジェク
ト領域10を探索し、各オブジェクト領域10をコピー
によりTO領域15に移動する(P161)。次に、T
O領域15に移動したオブジェクト領域10を探索し、
該当するオブジェクト領域10から参照されるオブジェ
クト領域10についてもコピーによりFROM領域16
からTO領域15へ移動する(P162)。手順P16
1、P162によりヒープ領域外のポインタ12から直
接または間接に参照できるすべてのオブジェクト領域1
0はTO領域15に移動したので、本段階でFROM領
域16に残るオブジェクト領域10は「ごみ」とみなす
ことができる。最後に、FROM領域16とTO領域1
5を入れ替え、新しいFROM領域16とTO領域15
と定義し直す(P1631)。この結果、手順P16
1、P162によりTO領域15に集められたオブジェ
クト領域10は、新しいFROM領域16に存在するこ
ととなり、その後メモリ獲得手段3で獲得されたオブジ
ェクト領域10と共に新しいFROM領域16内に保持
されるようになる。
【0056】つぎに、手順P161、P162の詳細を
示す。手順P161では、まずヒープ領域2外にある適
切なポインタ12の1つを選択し(P1411)、その
ポインタ12が有効でFROM領域16内にあるオブジ
ェクト領域を参照していれば(P1611のYes)、
ポインタ12が参照するオブジェクト領域10をコピー
によりTO領域15へ移動し(P1612)、本手順を
ヒープ領域2の外にあるすべてのポインタ12について
繰り返す(P1413のYes、P1414)。
【0057】手順162では、TO領域15内に未処理
のオブジェクト領域10があれば(P1621のYe
s)、まず該当するオブジェクト領域10を1つ選択し
(P1622)、選択したオブジェクト領域10が内部
にポインタ12を含めば(P1313のYes)、まず
選択したオブジェクト領域10に含まれるポインタ12
の1つを選び(P1314)、その値が有効で参照先オ
ブジェクト領域10がFROM領域16内に存在してい
れば(P1611のYes)、参照先のオブジェクト領
域10をコピーによりTO領域15へ移動し処理対象へ
加え(P1612)、本手順を選択したオブジェクト領
域10の内部に含まれるすべてのポインタ12に繰り返
し行い(P1315のNo)、さらにTO領域15内の
オブジェクト領域10のすべてについて上記手順を繰り
返す(P1623のNo)。
【0058】本従来例の具体的な動作の様子を図54を
用いて説明する。
【0059】図54は、本従来例の動作を示す解説図で
ある。図54に示される処理前の状況は、ヒープ領域2
内のFROM領域16内に6つのオブジェクト領域10
があり、各オブジェクト領域10はその内部に存在する
ポインタ12により相互に参照が行われており、さらに
一部はヒープ領域2外のポインタ12から参照されてい
る。本状況に対し手順P161を行った段階が、図54
に示されるヒープ領域外から参照されるオブジェクト領
域を移動した状況であり、ヒープ領域外のポインタ12
が参照していた2つのオブジェクト領域10がFORM
領域16からTO領域15へコピーにより移動してい
る。さらに、本状態に対し手順P162を行った段階
が、図54に示されるTO領域から参照されるオブジェ
クト領域を移動した状況であり、前段階でTO領域に移
動した2つのオブジェクト領域10から参照されるオブ
ジェクト領域10が新たにTO領域へ移動している。さ
らに、本状態に対し手順P1631を行いガベージコレ
クション処理が終了した段階が、図54に示されるTO
領域とFROM領域の入れ替え後の状況であり、前段階
のFROM領域16が新たなTO領域15になることで
「ごみ」であったオブジェクト領域10の占めるメモリ
領域は回収、再利用可能となる。
【0060】本従来例に示したストップ−コピー方式の
ガベージコレクション処理は上記のように動作するの
で、第4の従来例に示したマーク−コンパクト方式に比
べると「生きている」オブジェクト領域と「ごみ」の区
別のために全オブジェクト領域を検索する必要がなく、
その処理時間が速いという利点がある。さらに、次の第
6の従来例を併用することで、オブジェクト領域の移動
に伴い移動したオブジェクト領域を参照するポインタ1
2の補正処理が、マーク−コンパクト方式より容易にで
きるという利点がある。ただし、最大でもヒープ領域2
の半分の大きさまでしか利用ができないため、メモリ利
用効率が低いという欠点がある。
【0061】図55は、第6の従来例を示す構成図であ
る。図55においてヒープ領域2、TO領域15、FR
OM領域16、ポインタ12は図52と同じであるので
説明を省略する。また、図55では第6の従来例の説明
に不要な動的メモリ管理機構1、メモリ獲得手段3、メ
モリ開放手段4、ガベージコレクション手段5は記述を
省略している。
【0062】図55に示される第6の従来例の構成と図
52に示される第5の従来例の構成の大きな違いは、第
6の従来例ではオブジェクト領域10の内部に新たに間
接ポインタ22が存在することである。第6の従来例で
は、プログラムは、ポインタ12が保持する情報と間接
ポインタ22が保持する情報の、両方を用いてオブジェ
クト領域10を参照する。具体的には、プログラムは、
まずポインタ12が保持する情報を元に仮のオブジェク
ト領域10を参照し、その後同オブジェクト領域10の
保持する間接ポインタ22の値を元に真のオブジェクト
領域10を参照する。
【0063】本従来例の具体的な動作の様子を図55を
用いて説明する。図55では、ヒープ領域外にポインタ
Rpが、またヒープ領域2内には3つのオブジェクト領
域A、B、Cが存在する。ヒープ領域外に存在するポイ
ンタRpは、オブジェクト領域Aを参照している。オブ
ジェクト領域Aは、その内部にポインタAp1及びポイ
ンタAp2を保持し、ポインタAp1はオブジェクト領
域Bを、またポインタAp2はオブジェクト領域Cを参
照している。オブジェクト領域Bは、その内部にポイン
タBp1およびポインタBp2を保持し、ポインタBp
1はオブジェクト領域Cを参照しているが、ポインタB
p2はいずれのオブジェクト領域も参照せず無効な値を
保持している。図55は、また、ストップ−コピー方式
のガベージコレクション処理の途中段階を示しており、
オブジェクト領域A及びオブジェクト領域CはFROM
領域16からTO領域15へコピーにより移動している
が、オブジェクト領域BはまだFROM領域16からT
O領域15へ移動していない。
【0064】オブジェクト領域10内の間接ポインタ2
2は、ガベージコレクション処理において、それぞれ真
のオブジェクト領域10を参照するように調整される。
ここで真のオブジェクト領域とは、まだFROM領域1
6内にありTO領域15へ移動していないオブジェクト
領域では、FROM領域にあるオブジェクト領域であ
り、FROM領域からTO領域に移動したオブジェクト
領域では、TO領域に存在する移動先のオブジェクト領
域である。図55では、FROM領域にあるオブジェク
ト領域Bと、TO領域にあるオブジェクト領域A(新)
及びオブジェクト領域C(新)が該当し、それらのオブ
ジェクト領域の内部の間接ポインタ22は、自身のオブ
ジェクト領域を参照するように設定される。一方、仮の
オブジェクト領域はFROM領域からTO領域にオブジ
ェクト領域が移動した場合の、元のオブジェクト領域で
あり、図55ではFROM領域に残されたオブジェクト
領域A(旧)及びオブジェクト領域C(旧)が該当し、
それらのオブジェクト領域の内部の間接ポインタ22
は、それぞれ対応するTO領域の移動先のオブジェクト
領域を参照するよう設定される。本設定はオブジェクト
領域をFROM領域からTO領域へ移動する手順P16
12において、移動前のオブジェクト領域の間接ポイン
タ22を移動先のオブジェクト領域を参照するよう変更
することで実現される。
【0065】本従来例は以上のように動作するので、比
較的単純なFROM領域からTO領域への移動時のオブ
ジェクトの参照関係の調整処理と、ポインタからオブジ
ェクトの参照処理で、TO領域へ移動したオブジェクト
からTO領域へ移動したオブジェクト領域の参照も、T
O領域へ移動したオブジェクトからFROM領域内のま
だ移動していないオブジェクト領域の参照も、FROM
領域のまだ移動してないオブジェクト領域からTO領域
の移動したオブジェクト領域への参照も、すべて等しく
同じ手順で扱えるという利点がある。すなわち、図55
において、オブジェクト領域A(新)のポインタAp2
からオブジェクト領域C(新)へは、まずポインタAp
2からオブジェクト領域C(新)を参照し、さらにオブ
ジェクト領域C(新)からその間接ポインタ22が指す
先であるオブジェクト領域C(新)を再度参照すること
で、正しくなされる。また、オブジェクト領域A(新)
のポインタAp1からオブジェクト領域Bへは、まずポ
インタAp1からオブジェクト領域Bを参照し、さらに
オブジェクト領域Bからその間接ポインタ22が指す先
であるオブジェクト領域Bを再度参照することで正しく
なされる。そして、オブジェクト領域BのポインタBp
1からオブジェクト領域C(新)へは、まずポインタB
p1からオブジェクト領域C(旧)を参照し、さらにオ
ブジェクト領域C(旧)からその間接ポインタ22が指
す先であるオブジェクト領域C(新)を参照することで
正しくなされる。
【0066】ただし、以上に示した本従来例は、オブジ
ェクト領域の移動に際し移動前の領域が破壊されないこ
とが必要である。このため第5の従来例により示したF
ROM領域からTO領域へ移動させるストップ−コピー
方式に組み合わせることはできるが、第4の従来例によ
り示したヒープ領域内で空きを埋めるように移動させる
マーク−コンパクト方式に組み合わせることは困難であ
り、本従来例はマーク−コンパクト方式におけるオブジ
ェクト領域の移動に伴う参照関係の保持の解決策とはな
らない。
【0067】次に、第7の従来例を用いて、インクリメ
ンタル(歩進)方式のガベージコレクション処理につい
て説明する。インクリメンタル方式は、ガベージコレク
ション処理を少しずつ進めることで応用プログラムの中
断時間を短くし、プログラムの応答性の向上を図る技術
であり、各種のガベージコレクション方式をベースとし
て多くの改良がなされているが、ここでは、第5の従来
例として示したストップ−コピー方式を元に改良した比
較的単純な方式について説明する。
【0068】第7の従来例の構成およびガベージコレク
ション処理の動作は、それぞれ第5の従来例の構成(図
52)及びガベージコレクション処理の動作(図53)
と同一であるので、説明を省略する。第7の従来例にお
けるポインタの値の読み出しの動作を図56を用いて説
明する。
【0069】図56は、第7の従来例の動作を示すフロ
ーチャートである。ポインタの値の読み出しの動作で
は、ポインタ12の値が有効であり(P1201のYe
s)、さらにポインタ12の参照するオブジェクト領域
10がFROM領域16にあれば(P1611のYe
s)、参照先のオブジェクト領域10をFROM領域1
6からTO領域15へ移動させ(P1612)、移動先
への参照をポインタ12の値に設定してから(P170
1)、その値をプログラムに渡し(P1702)、処理
を終える。なお、ポインタ12の参照先がTO領域のオ
ブジェクト領域であったり(P1611のNo)、ある
いは値が無効である場合は(P1201のNo)、速や
かに手順P1702に移りその値をそのままプログラム
に渡す。
【0070】本従来例に示したストップ−コピー方式を
元にしたインクリメンタル方式のガベージコレクション
は、上記のように動作することで、ガベージコレクショ
ン処理P160と応用プログラムの動作を平行して行う
ことが可能となり、これによりストップ−コピー方式の
長所を損ねることなく、第2の従来例として示した参照
カウンタ方式のガベージコレクション処理と同様に応用
プログラムの動作の中断を短くすることができる。ただ
し、オブジェクト領域のコピー処理が入るため、参照カ
ウンタ方式に比較すると応用プログラムの動作の中断時
間は長い。
【0071】次に、第8の従来例を用いて、ジェネレー
ショナル(世代)方式のガベージコレクション処理につ
いて説明する。ジェネレーショナル方式は、ガベージコ
レクション処理の対象とするオブジェクト領域に「世
代」の概念を導入し、世代の異なるオブジェクト領域を
分けて扱うことで、平均的なガベージコレクション処理
の効率を図る技術である。ジェネレーショナル方式のイ
ンクリメンタル方式同様、各種のガベージコレクション
方式をベースとして多くの改良がなされているが、ここ
では比較的単純だが第4の従来例として示したマーク−
コンパクト方式と第5の従来例として示したストップ−
コピー方式を併用する方式について説明する。
【0072】図57は、第8の従来例である、マーク−
コンパクト方式とストップ−コピー方式を併用したジェ
ネレーショナル方式のガベージコレクション処理を行う
動的メモリ管理機構の構成図である。図57において、
動的メモリ管理機構1、ヒープ領域2、メモリ獲得手段
3、メモリ開放手段4、ガベージコレクション5、ポイ
ンタ12、TO領域15、FROM領域16は図52と
同じであるので説明を省略する。また、オブジェクト領
域10、マーク20は図49と同じであるので説明を省
略する。図57ではヒープ領域2内には、TO領域1
5、FROM領域16のほかに、OLD領域23が存在
する。TO領域15、FROM領域16、OLD領域2
3は同じ大きさの領域であり、多くの場合それぞれヒー
プ領域2の3等分した領域として設定される。本従来例
では、第5の従来例同様、メモリ獲得手段3は必ずFR
OM領域16内からオブジェクト領域10を獲得し、メ
モリ開放手段4はガベージコレクション手段5に組み込
まれて動作し、オブジェクト領域10を個別に開放する
ことはない。
【0073】次に、本従来例の動作について説明する。
本従来例ではオブジェクト領域の世代を若い世代と古い
世代の2つに分ける。若い世代のオブジェクト領域はF
ROM領域に存在する。古い世代のオブジェクト領域は
OLD領域に存在する。まず最初に、若い世代に関する
ガベージコレクションについて説明する。
【0074】図58は、本従来例における第1の動作で
ある、若い世代に対するガベージコレクション処理(G
C処理)の動作を示すフローチャートである。本従来例
では、若い世代に対するガベージコレクション処理は第
5の従来例に示したストップ−コピー方式に準じて行わ
れ、まずOLD領域23にある古いオブジェクト領域に
含まれるポインタ12を、ヒープ領域外にあるように扱
うようにし(P1801)、ついでFROM領域16か
らTO領域15へストップ−コピー式の手順P161お
よびP162に準じた方法でガベージコレクション処理
を行う(P1802)。その後、FROM領域16とT
O領域15を入れ替え新しいFROM領域16とTO領
域15に定義し直す(P1631)。
【0075】本従来例の若い世代に対するガベージコレ
クション処理の具体的な動作の様子を図59を用いて説
明する。
【0076】図59は、本従来例の第1の動作である、
若い世代に対するガベージコレクション処理の動作を示
す解説図である。図59に示される処理前の状況は、ヒ
ープ領域2内のFROM領域16およびOLD領域23
内にのみオブジェクト領域10が存在し、その一部はヒ
ープ領域2外のポインタ12から参照されている。本状
態に対し、手順P1801、P1802を行った段階
が、図59に示される処理後の状況であり、OLD領域
23内に存在していたオブジェクト領域10は変化して
いないが、FROM領域16内に存在していたオブジェ
クト領域10はTO領域15に移され、ヒープ領域2外
のポインタ12の参照もTO領域内を指すよう変更され
ている。なお、図59に示される処理前の状況におい
て、FROM領域16内にあって、ヒープ領域2外のポ
インタ12からも、OLD領域23内のオブジェクト領
域23が保持するポインタ12からも、直接、ないし間
接的に参照することができなかったオブジェクト領域1
0は、図59に示される処理後の状況におけるTO領域
15へは移されず、「ごみ」として回収、再利用され
る。
【0077】次に、本従来例の第2の動作である、古い
世代のガベージコレクション処理について説明する。図
60は、本従来例の第2の動作である、古い世代に対す
るガベージコレクション処理の動作を示すフローチャー
トである。本従来例では、古い世代に対するガベージコ
レクション処理は第4の従来例に示したマーク−コンパ
クト方式に準じて行われ、まずTO領域15内にオブジ
ェクト領域10があれば、同オブジェクト領域10に含
まれるポインタ12を、ヒープ領域外にあるように扱う
ようにし(P1901)、ついでFROM領域16とO
LD領域23を合わせて1つの領域とみなしOLD領域
23から優先して詰めるようにマーク−コンパクト式の
手順P140に準じた方法でガベージコレクション処理
を行う(P1902)。
【0078】本従来例の古い世代に対するガベージコレ
クション処理の具体的な動作の様子を図61を用いて説
明する。
【0079】図61は、本従来例の第2の動作である、
古い世代に対するガベージコレクション処理の動作を示
す解説図である。図61に示される処理前の状況は、図
59に示される処理前の状況と同様に、ヒープ領域2内
のFROM領域16およびOLD領域23内にのみオブ
ジェクト領域10が存在し、その一部はヒープ領域2外
のポインタ12から参照されている。本状態に対し、手
順P1901、P1902を行った段階が、図61に示
される処理後の状況であり、OLD領域23内に存在し
ていたオブジェクト領域10とFROM領域に存在して
いたオブジェクト領域のうち、ヒープ領域2外のポイン
タ12から直接ないし間接的に参照することができなか
ったオブジェクト領域10は省かれ、残ったオブジェク
ト領域10はOLD領域23を先に詰めるようにまとめ
られ、これにより「ごみ」は回収、再利用される。なお
オブジェクト領域をまとめる際には、FROM領域16
とOLD領域23の境界をオブジェクト領域10がまた
ぐことはないようにする。なお、図61に示される処理
後の状況では、古いオブジェクト領域に対するガベージ
コレクション処理の結果、生き残ったオブジェクト領域
はOLD領域23に収まりきれず、一部FROM領域1
6にも存在している。このFROM領域16に存在する
オブジェクト領域は、新しい世代に対するガベージコレ
クション処理に加わることになる。一方、OLD領域2
3に収まったオブジェクト領域は、プログラムの動作に
よってどのポインタからも参照できない「ごみ」になっ
ても、図59に示したように、新しい世代に対するガベ
ージコレクション処理では、回収、再利用されることは
ない。
【0080】本従来例に示したジェネレーショナル方式
のガベージコレクション処理は、上記のように動作する
ので、新しい世代のガベージコレクション処理とも古い
世代のガベージコレクション処理ともヒープ領域2の全
体より小さな領域を対象に動作するため、その処理時間
を短くすることができる。また、過去に示されたガベー
ジコレクション処理に関する研究成果によれば、一般的
に多くのプログラムの動作では、新しく生成されたオブ
ジェクト領域10ほど早く「ごみ」になり易く、逆に一
定時間以上「生きている」オブジェクト領域10は「ご
み」になりにくいという傾向が観察されており、本傾向
が成立する状況では、OLD領域23に収まるオブジェ
クト領域は長生きである可能性が高いので、大抵の場
合、新しい世代のガベージコレクション処理のみであっ
ても全体に対したガベージコレクション処理に近い効果
を期待でき、処理の効率が向上する。さらに、本従来例
では、最大ヒープメモリ領域の2/3まで利用でき、第
5の従来例として示したストップ−コピー方式よりメモ
リの使用効率が向上する長所がある。しかし、本従来例
に限らず一般にジェネレーショナル方式のガベージコレ
クション処理では、若い世代に対するガベージコレクシ
ョン処理と古い世代に対するガベージコレクション処理
をどのような比率で、またどのようなタイミングで行う
かという問題点があり、またそもそもジェネレーショナ
ル方式は一般的なプログラムにおける平均的な効率の向
上を図るものであるため、プログラムの挙動の傾向が前
述とは異なりオブジェクト領域の生存期間に関する前提
が崩れる場合では、得られる効果は少ないか、逆に悪化
するという問題もある。
【0081】
【発明が解決しようとする課題】上述したような従来の
動的メモリ管理機構では、メモリリーク現象や、フラグ
メンテーション現象などを引き起こし、計算機システム
が長期連続運転できないことを意味し、長期間にわたる
無停止運転が前提の産業系計算機システムでは許容する
ことができない等の問題点があった。
【0082】この発明は、前述した問題点を解決するた
めになされたもので、主に産業分野で使われる計算機シ
ステムに向けた、長期間の連続運転が可能で、処理が簡
素でその効率が良く、また応用プログラムの動作の応答
性や計算機システムの応答性を高められ、さらにシステ
ム立ち上げに要する時間を短縮する効果のある、ガベー
ジコレクション手段を備えた動的メモリ管理機構を得る
ことを目的とする。
【0083】
【課題を解決するための手段】この発明に係る動的メモ
リ管理機構は、ヒープ領域と、前記ヒープ領域からその
一部をオブジェクト領域として獲得するメモリ獲得手段
と、前記獲得したオブジェクト領域を前記ヒープ領域に
戻し再利用可能とするメモリ開放手段と、前記メモリ獲
得手段により獲得されたがプログラムから利用されなく
なったオブジェクト領域を探索し、前記メモリ開放手段
を用いて前記ヒープ領域へ開放するガベージコレクショ
ン手段とを備え、前記各オブジェクト領域にはそれぞ
れ、その利用状況を示す参照カウンタが存在し、各参照
カウンタは対応するオブジェクト領域を参照するポイン
タの数を示すようその値が増減し、前記ガベージコレク
ション手段は、前記参照カウンタの値が0となったとき
対応するオブジェクト領域を開放する参照カウンタ方式
のガベージコレクション処理と、他の方式によるガベー
ジコレクション処理を併用して動作する場合に、前記参
照カウンタの値が0になり対応する第1のオブジェクト
領域が開放される際に、前記第1のオブジェクト領域の
み開放し、前記第1のオブジェクト領域内にある1ない
複数のポインタが参照している第2のオブジェクト領域
については、参照カウンタの値の更新処理および同処理
に付随して発生しうるオブジェクト領域の開放処理を行
わないものである。
【0084】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、前記参照カウン
タの値が0となって前記第1のオブジェクト領域を開放
するときに、前記第1のオブジェクトの領域内にある1
ないし複数のポインタの値を無効値に設定するものであ
る。
【0085】この発明に係る動的メモリ管理機構は、ヒ
ープ領域と、前記ヒープ領域からその一部をオブジェク
ト領域として獲得するメモリ獲得手段と、前記獲得した
オブジェクト領域を前記ヒープ領域に戻し再利用可能と
するメモリ開放手段と、前記メモリ獲得手段により獲得
されたがプログラムから利用されなくなったオブジェク
ト領域を探索し、前記メモリ開放手段を用いて前記ヒー
プ領域へ開放するガベージコレクション手段とを備え、
前記メモリ獲得手段は、前記ヒープ領域内の残利用可能
領域の一端から順次オブジェクト領域を獲得し、前記ガ
ベージコレクション手段は、まず前記残利用可能領域を
TO領域とし、前記TO領域に隣接する同量ないしそれ
以下の既獲得済み領域をFROM領域とし、コピーによ
り個々のオブジェクト領域を移動させる形で部分ガベー
ジコレクション処理を行い、次に、前記TO領域のうち
オブジェクト領域が移動しないで利用可能として残った
領域と、空になったFROM領域を合わせた新しい残利
用可能領域を新たなTO領域とし、まだガベージコレク
ション処理を行ってない既獲得済み領域のうち新しい残
利用可能領域と同量の領域を新たなFROM領域として
再度部分ガベージコレクション処理を行い、既獲得済み
領域の全体にガベージコレクション処理が及ぶまで、以
降も同様に部分ガベージコレクション処理を繰り返すも
のである。
【0086】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、部分ガベージコ
レクション処理を繰り返す際に、その途中で新しく生成
した残利用可能領域の大きさがある閾値を超えた場合
は、そこで繰り返しを止めるものである。
【0087】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、部分ガベージコ
レクション処理を繰り返す前に、まずヒープ領域外の存
在するポインタから参照されるオブジェクト領域のベー
スポインタリストを作成し、続いて繰り返される部分ガ
ベージコレクション処理では、ヒープ領域外に存在する
ポインタの代わりに前記ベースポインタリストが保持す
るポインタを用いて処理を行い、前記ポインタが参照す
るオブジェクト領域がTO領域へコピーされた場合は、
前記ポインタを前記ベースポインタリストから削除する
ものである。
【0088】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、ガベージコレク
ション処理の繰り返しに際し、TO領域となる残利用可
能領域がヒープ領域内を常に一方向へ移動するよう、残
利用可能領域からのオブジェクト領域獲得順序およびヒ
ープ領域内におけるFROM領域とTO領域の相対位置
を固定させているものである。
【0089】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、ガベージコレク
ション処理の繰り返しに際し、TO領域となる残利用可
能領域がヒープ領域内を往復するよう、残利用可能領域
からのオブジェクト領域獲得順序およびヒープ領域内に
おけるFROM領域とTO領域の相対位置を変化させる
ものである。
【0090】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、TO領域となる
残利用可能領域が小さい時は、既獲得済み領域からTO
領域に隣接して設定するFORM領域をTO領域の量よ
り大きく設定し、まずFROM領域内の有効なオブジェ
クト領域の探索をオブジェクト領域の移動を伴わずに行
い、ついでFORM領域内の有効なオブジェクト領域を
FROM領域とTO領域を合わせた領域の一端につめる
ことで、残利用可能領域を大きくしてから、前記部分ガ
ベージコレクション処理を実行するものである。
【0091】この発明に係る動的メモリ管理機構は、ヒ
ープ領域と、前記ヒープ領域からその一部をオブジェク
ト領域として獲得するメモリ獲得手段と、前記獲得した
オブジェクト領域を前記ヒープ領域に戻し再利用可能と
するメモリ開放手段と、前記メモリ獲得手段により獲得
されたがプログラムから利用されなくなったオブジェク
ト領域を探索し、前記メモリ開放手段を用いて前記ヒー
プ領域へ開放するガベージコレクション手段とを備え、
前記各オブジェクト領域を参照するポインタは、直接に
は参照テーブルのエントリを指し、前記ポインタによる
オブジェクト領域の参照は、必ず前記参照テーブルのエ
ントリを経由して行うものである。
【0092】この発明に係る動的メモリ管理機構は、ヒ
ープ領域と、前記ヒープ領域からその一部をオブジェク
ト領域として獲得するメモリ獲得手段と、前記獲得した
オブジェクト領域を前記ヒープ領域に戻し再利用可能と
するメモリ開放手段と、前記メモリ獲得手段により獲得
されたがプログラムから利用されなくなったオブジェク
ト領域を探索し、前記メモリ開放手段を用いて前記ヒー
プ領域へ開放するガベージコレクション手段とを備え、
前記ガベージコレクション手段は、周期的に一定時間以
下のみガベージコレクション処理を行うよう動作するも
のである。
【0093】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、周期的に一定の
比率で真/偽が変化するフラグを参照し、前記フラグが
真の間だけ、ガベージコレクション処理を行うよう動作
するものである。
【0094】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、ガベージコレク
ション処理の実施可否を示すカウンタと、周期的に前記
カウンタを適切な値で増加させるカウンタ増加手段とを
有し、ガベージコレクション処理の進行状況に応じて前
記カウンタの値を減算しながら、前記カウンタの値が正
の間だけガベージコレクション処理を行うよう動作する
ものである。
【0095】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、前記ヒープ領域
内の残利用可能領域の量がある閾値を超えるまでは、前
記カウンタの値が負にあってもガベージコレクション処
理を継続するものである。
【0096】この発明に係る動的メモリ管理機構は、ヒ
ープ領域と、前記ヒープ領域からその一部をオブジェク
ト領域として獲得するメモリ獲得手段と、前記獲得した
オブジェクト領域を前記ヒープ領域に戻し再利用可能と
するメモリ開放手段と、前記メモリ獲得手段により獲得
されたがプログラムから利用されなくなったオブジェク
ト領域を探索し、前記メモリ開放手段を用いて前記ヒー
プ領域へ開放するガベージコレクション手段とを備え、
前記ガベージコレクション手段は、ガベージコレクショ
ン処理を行う契機となった理由、プログラムの動作状
況、動的メモリ管理機構の内部状況、あるいはシステム
の稼動状況などのシステム状態に応じて、適宜異なるガ
ベージコレクション方式を使い分けるものである。
【0097】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、ヒープ領域内の
残利用可能領域の不足により応用プログラムの動作中に
前記メモリ獲得手段が応用プログラムから要求された量
のオブジェクト領域を獲得できないため臨時に行う場合
と、あらかじめ設定されていたタイミングにより行う場
合とで、異なるガベージコレクション方式を使い分ける
ものである。
【0098】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、最も最近に実施
したガベージコレクション処理の後に前記メモリ獲得手
段により獲得され、いまだガベージコレクションの処理
の対象となったことのないオブジェクト領域の数に応じ
て、異なるガベージコレクション方式を使い分けるもの
である。
【0099】また、この発明に係る動的メモリ管理機構
は、前記ガベージコレクション手段が、計算機システム
がシステム立ち上げ段階として動作している場合と、シ
ステムの定常段階として動作している場合とで、異なる
ガベージコレクション方式を使い分けるものである。
【0100】この発明に係る動的メモリ管理機構は、ヒ
ープ領域と、前記ヒープ領域からその一部をオブジェク
ト領域として獲得するメモリ獲得手段と、前記獲得した
オブジェクト領域を前記ヒープ領域に戻し再利用可能と
するメモリ開放手段と、前記メモリ獲得手段により獲得
されたがプログラムから利用されなくなったオブジェク
ト領域を探索し、前記メモリ開放手段を用いて前記ヒー
プ領域へ開放するガベージコレクション手段とを備え、
応用プログラムの動作によりガベージコレクション処理
が必要となると、即座にガベージコレクション処理を行
うのではなく、別途定められたタイミングで行われるガ
ベージコレクション処理が終了するまで、同応用プログ
ラムの動作を停止させるものである。
【0101】また、この発明に係る動的メモリ管理機構
は、応用プログラムからの明示的にガベージコレクショ
ン指示が行われた場合に、即座にガベージコレクション
処理を行うのではなく、別途定められたタイミングで行
われるガベージコレクション処理が終了するまで、同応
用プログラムの動作を停止させるものである。
【0102】また、この発明に係る動的メモリ管理機構
は、応用プログラムが前記メモリ獲得手段を用いてオブ
ジェクト領域を獲得しようとしたときに、ヒープ領域内
の残利用可能領域から応用プログラムが必要するオブジ
ェクト領域を得られないため、ガベージコレクション処
理が必要となった場合に、即座にガベージコレクション
処理を行うのではなく、別途定められたタイミングで行
われるガベージコレクション処理が終了するまで、同応
用プログラムの動作を停止させるものである。
【0103】また、この発明に係る動的メモリ管理機構
は、複数の応用プログラムがガベージコレクション処理
の終了を待っている場合に、ガベージコレクション処理
により増加するヒープ領域内の残利用可能領域が、各プ
ログラムのそれぞれの要求を満たすようになった場合、
各プログラムは処理の継続が可能となった時点で順次そ
の停止が解除されるものである。
【0104】そして、この発明に係る情報記録媒体は、
請求項1から請求項21までのいずれかに記載の動的メ
モリ管理機構を実現する計算機システムのプログラムを
記録したものである。
【0105】
【発明の実施の形態】実施の形態1.この発明の実施の
形態1に係る動的メモリ管理機構について図面を参照し
ながら説明する。図1は、この発明の実施の形態1に係
る動的メモリ管理機構の構成を示すブロック図である。
なお、各図中、同一符号は同一又は相当部分を示す。
【0106】本実施の形態1における構成は、図36に
示した第1の従来例の構成と同一であり、動的メモリ管
理機構1は、計算機システムのメモリ領域の一部である
ヒープ領域2と、同ヒープ領域2からその一部をオブジ
ェクト領域10として獲得するメモリ獲得手段3と、獲
得した同オブジェクト領域10を同ヒープ領域2に戻し
再利用可能とするメモリ開放手段4と、同メモリ獲得手
段3により獲得されたがプログラムから利用されなくな
ったオブジェクト領域10を探索し、同メモリ開放手段
4を用いて同ヒープ領域2に開放するガベージコレクシ
ョン手段5から構成される。同ヒープ領域2は、本実施
の形態1ではそのアドレスが連続する単一のメモリ領域
であるとするが、これは複数のメモリ領域から構成する
ことも容易に可能である。
【0107】同ヒープ領域2には、1ないし複数のオブ
ジェクト領域10が存在し得る。個々のオブジェクト領
域10は、メモリ獲得手段3によって生成され、メモリ
開放手段4によって消去される、ヒープ領域2内の小さ
なメモリ領域である。オブジェクト領域10の中にはプ
ログラムの動作に必要な各種の情報が適宜保持される。
オブジェクト領域10が保持する情報はプログラムの開
発言語やプログラム設計に大きく依存し、プログラムの
動作に必要なデータだけを含む場合もあれば、プログラ
ムの命令コードも含む場合もある。
【0108】各オブジェクト領域10は、それぞれ参照
カウンタ11を持つ。これは参照カウンタ方式のガベー
ジコレクション処理における特徴的な構造であり、参照
カウンタ11は整数値を保持する変数であり、その値
は、対応するオブジェクト領域10がいくつのポインタ
12から参照されているかを示す。
【0109】ポインタ12は、ガベージコレクション処
理を行うときに考慮が必要なプログラムのデータであ
る。ポインタ12は、プログラムがオブジェクト領域1
0を参照するため必要な情報を保持する記憶領域であ
り、計算機のCPUレジスタや、プログラムが静的に配
置したメモリ領域やスタック内の変数(小さなメモリ領
域)、オブジェクト領域10内の変数として存在する。
【0110】つぎに、前述した実施の形態1に係る動的
メモリ管理機構の動作について図面を参照しながら説明
する。本実施の形態1は、他の方式との併用を前提とし
た参照カウンタ方式のガベージコレクション処理に関す
る発明の実施例であり、ガベージコレクション手段5
は、本発明にかかる参照カウンタ方式と他の方式を併用
したガベージコレクション処理を行う。併用する他のガ
ベージコレクション処理の方式は、第1の従来例の第2
の動作(図43、図45)で示したオブジェクト領域の
循環する参照による回収漏れと、第3の従来例で示した
フラグメンテーション現象の、2つの問題を回避した方
式ならばいずれの方式でも良く、例えば第4の従来例と
して示したマーク−コンパクト方式や、第5の従来例と
して示したストップ−コピー方式、さらにそれらの改良
である他の従来方式、そして本発明の請求項3に示され
る方式などを採用することができ、そのいずれとの組み
合わせでも本発明の効果を奏する。
【0111】本実施の形態1におけるオブジェクト獲得
の動作は第1の従来例(図37)と同一であり、オブジ
ェクト領域10の獲得の動作では、まずヒープ領域2内
の未使用部分からプログラムにより明示的あるいは暗示
的に指定された適切な大きさのメモリ領域を獲得し(P
1101)、次に獲得した領域をオブジェクト領域10
とみなしてその参照カウンタ11の値を0に設定し(P
1102)、さらに必要に応じて獲得したオブジェクト
領域内のその他の場所(データ)の初期化を行い(P1
103)、その後オブジェクト領域10を参照するため
に必要なポインタ12の値を返す。ここで、手順P11
02で参照カウンタ11の値を0とするのは、新たに生
成したオブジェクト領域10が、まだどこのポインタ1
2からも参照されておらず、同オブジェクト領域を参照
するポインタ12の数が0であることによる。
【0112】図2は、本実施の形態1におけるポインタ
12の値の変更の動作を示すフローチャートである。ポ
インタ12の値の変更の動作S120では、まずその値
を変更するポインタ12が保持する値の有効性を検査す
る(P1201)。もしポインタ12が値の変更に先立
ちオブジェクト領域10を参照していれば(P1201
のYes)、本変更により参照先のオブジェクト領域1
0を参照するポインタ12の数が減るので、同オブジェ
クト領域10の参照カウンタ11の値を1減算し(P1
202)。その結果参照カウンタ11の値が0であれば
(P1203のYes)、対象とするオブジェクト領域
10はどこのポインタ12からも参照されていないオブ
ジェクト領域10、すなわち「ごみ」となったので、メ
モリ開放手段4を用いそのオブジェクト領域10の開放
を行う(P1209)。その後、ポインタ12の値を新
しい値に設定し(P1210)、もしその値が有効でオ
ブジェクト領域10を参照していれば(P1211のY
es)、参照先のオブジェクト領域10を参照するポイ
ンタ12の数が増えるので、同オブジェクト領域10の
参照カウンタ11の値を1加算し(P1212)、処理
を終える。
【0113】なお、値を変更する前のポインタ12が参
照するオブジェクト領域10の参照カウンタ11を1減
算しても、参照カウンタ11の値は0にならなければ
(P1203のNo)、対象とするオブジェクト領域1
0は、まだ他のポインタ12から参照されており、使用
中のオブジェクト領域10であるので、オブジェクト領
域10の開放処理は行わず、速やかにポインタ12に新
しい値を設定する(P1210)。これは値を変更する
前のポインタ12の値が無効な値であった場合(P12
01のNo)も同様で、速やかにポインタ12に新しい
値を設定する(P1210)。また、ポインタ12に設
定する新しい値が無効な値であれば(P1211のN
o)、更新すべき参照カウンタ11が存在しないので手
順P1212は行わず、速やかに処理を終える。
【0114】本実施の形態1の具体的な動作の様子を図
3、及び図4を用いて説明する。
【0115】図3は、本実施の形態1の動作の実施前を
示す解説図である。図3は、第1の従来例の第1の動作
の実施前を示す解説図(図39)と同一であり、図3に
おいて、ポインタRpは計算機のCPUレジスタ、プロ
グラムが静的に配置したメモリ領域、あるいはスタック
内の変数として、ヒープ領域2の外部に存在するポイン
タ12であり、第1のオブジェクト領域Aを参照してい
る。オブジェクト領域Aはその内部にポインタAp1お
よびポインタAp2を保持し、ポインタAp1は第2の
オブジェクト領域Bを、またポインタAp2は第3のオ
ブジェクト領域Cを参照している。オブジェクト領域B
はその内部にポインタBp1およびポインタBp2を保
持し、ポインタBp1はポインタAp2同様オブジェク
ト領域Cを参照しているが、ポインタBp2はいずれの
オブジェクト領域も参照せず無効な値を保持している。
オブジェクト領域Cはその内部にポインタ12は保持し
ない。オブジェクト領域AはポインタRpからのみ参照
されているので、オブジェクト領域Aの参照カウンタA
c1の値は1である。同様に、オブジェクト領域Bはポ
インタAp1からのみ参照されているので、その参照カ
ウンタBc1の値は1であり、オブジェクト領域Cはポ
インタAp2とポインタBp1から参照されているの
で、その参照カウンタCc1の値は2である。
【0116】図3に示される状況においてポインタRp
を無効な値に変更する動作S120は次の通りとなる。
変更前のポインタRpの値はオブジェクト領域Aを参照
する有効な値なので、P1201、P1202と進む。
P1202の結果、参照カウンタAc1の値は0となる
ので、P1203のYesへ進み、オブジェクト領域A
を開放(P1209)したのちポインタRpの値を無効
な値に設定し(P1210)、その後S120を終え
る。図4は、本段階の状況を示す解説図であり、図3に
対しオブジェクト領域Aが開放され(破線)、ポインタ
Rpが無効な値に設定される。なお、本手順S120で
は第1の従来例の手順P120と異なり、オブジェクト
領域B、オブジェクト領域Cは開放されないが、これら
は別途行われる他の方式のガベージコレクション処理に
より回収される。
【0117】第1の従来例の説明で述べたように、参照
カウンタ方式のガベージコレクション処理は、オブジェ
クト領域間の循環した参照により「ごみ」を回収し損ね
るという問題があり、本問題を避けるため他の方式との
併用が必要であることが指摘されている。本実施の形態
1では、循環した参照に対する問題を回避する他の方式
と併用されることを前提として、ポインタの値の変更の
動作を上記のように行うことで、第1の従来例と異なり
ポインタの値の変更の動作S120の要する時間が予測
可能であり、かつ同様の効果を奏する第2の従来例に対
しては、参照カウンタが0になったオブジェクト領域を
開放するための専用のガベージコレクション処理P13
1が不要で、ガベージコレクション手段5をより簡素に
することができる。
【0118】実施の形態2.この発明の実施の形態2
は、実施の形態1におけるポインタの値の変更の動作を
変更したものである。その基本構成およびオブジェクト
領域獲得の動作は実施の形態1と同一であるので、説明
を省略する。
【0119】図5は、実施の形態2におけるポインタ1
2の値の変更の動作を示すフローチャートである。実施
の形態2におけるポインタ12の値の変更の動作S13
0でも、まず実施の形態1の手順S120と同じく、ポ
インタ12が保持する値を検査し(P1201)、もし
ポインタ12が有効なオブジェクト領域10を参照して
いれば(P1201のYes)、参照するオブジェクト
領域10の参照カウンタ11の値を1減算する(P12
02)。しかし、その結果参照カウンタ11の値が0で
あったときは(P1203のYes)、即座にオブジェ
クト領域10の開放の処理を行うのではなく、対象とす
るオブジェクト領域10がその内部に1ないし複数のポ
インタ12を持っていれば(P1204のYes)、オ
ブジェクト領域10内に存在するすべてのポインタ12
についてそのそれぞれの値を無効な値に設定してから
(S1301、P1207、P1208)、メモリ開放
手段4を用い対象とするオブジェクト領域10を開放す
る(P1209)。その後は、また実施の形態1と同
様、ポインタ12の値を新しい値に設定し(P121
0)、もしその値が有効でオブジェクト領域10を参照
していれば(P1211のYes)、参照先のオブジェ
クト領域10を参照するポインタ12の数が増えるの
で、同オブジェクト領域10の参照カウンタ11の値を
1加算し(P1212)、処理を終える。なお、これは
値を変更する前のポインタ12の値が無効な値であった
場合(P1201のNo)や、値を変更する前のポイン
タ12が参照するオブジェクト領域10の参照カウンタ
11を1減算しても参照カウンタ11の値は0にならな
い場合(P1203のNo)、オブジェクト領域10の
開放処理は行わず、速やかにポインタ12に新しい値を
設定する(P1210)点、またポインタ12に設定す
る新しい値が無効な値であれば(P1211のNo)、
更新すべき参照カウンタ11が存在しないので手順P1
212は行わず、速やかに処理を終える点も実施の形態
1に同じである。
【0120】本実施の形態2の具体的な動作の様子を図
3、及び図5を用いて説明する。
【0121】本実施の形態2の動作の実施前を示す解説
図は、実施の形態1における動作の実施前を示す解説図
(図3)と同一であり説明を省略する。図3において、
ポインタRpを無効な値に変更する動作S130は次の
通りとなる。変更前のポインタRpの値はオブジェクト
領域Aを参照する有効な値なので、P1201、P12
02と進む。P1202の結果、参照カウンタAc1の
値は0となるので、P1203のYesへ進み、さらに
オブジェクト領域Aは内部にポインタAp1およびAp
2を含むので、P1204のYesからP1205へと
処理を進め、まずポインタAp1についてその値を無効
な値に設定する(S1301)。その後処理はP120
7のNo、P1208と進み、続くS1301では今度
はポインタAp2の値を無効な値に設定する。こうして
オブジェクト領域A内のすべてのポインタを無効に設定
し終えると(P1207のYes)、オブジェクト領域
Aを開放(P1209)したのちポインタRpの値を無
効な値に設定し(P1210)、その後P130を終え
る。図6は、本段階の状況を示す解説図であり、図3に
対しポインタAp1およびAp2が無効な値に設定さ
れ、オブジェクト領域Aが開放され(破線)、ポインタ
Rpが無効な値に設定される。本状況は、実施の形態1
の動作後の状況(図4)に対し、ポインタAp1および
Ap2の値が無効になっている点が異なる。
【0122】本実施の形態2は上記のように動作するこ
とで、実施の形態1に比較し、ポインタ12の値の変更
動作S130の要する時間は長くなるものの、実施の形
態1と比較してポインタ12の値の変更に要する時間を
短縮することができ、また実施の形態1同様、第2の従
来例に比べガベージコレクション手段5が簡素にでき、
さらに実施の形態1と異なり開放するオブジェクト領域
10内に含まれるポインタ12を無効な値に設定するこ
とで、併用する他の方式のガベージコレクション処理に
おけるごみ識別が行い易くなり、その処理の効率を高く
することができる。
【0123】なお、本実施の形態2では、開放するオブ
ジェクト領域10内のポインタ12すべてについて無効
な値としたが(手順P1205、S1301、P120
7のYes、P1208)、処理するポインタ12の数
に上限を設けることで、実施の形態1と同様、ポインタ
の値の変更の動作に要する時間を予測可能とすることが
できる。また、その上限の個数を、例えばシステムのC
PU負荷状況など、システムの動作の状況に応じて変化
させることで、ポインタ12の値の変更の動作に要する
処理の重さと、併用する他の方式のガベージコレクショ
ン処理の重さを、システムの動作の状況に応じて適切に
制御でき、システム全体の効率や応答性の向上を図るこ
とができる。
【0124】さらに、本実施の形態2の手法あるいは上
記本実施の形態2を発展させた手法を、第1の従来例に
示した参照カウンタ方式に適用し、第1の従来例のポイ
ンタ12の値の変更動作P120において、ポインタ1
2の値の変更に付随して再帰的に開放されるオブジェク
ト領域10の数や無効に設定するポインタ12の数につ
いて上限を設けることで、実施の形態1同様、ポインタ
12の値の変更の動作に要する時間を予測可能とするこ
とができ、またその上限を変化させることで、上記と同
様ポインタ12の値の変更動作に要する処理の重さと、
併用する他の方式のガベージコレクション処理の重さを
制御し、システム全体の効率や応答性向上を図ることが
できる。
【0125】実施の形態3.この発明の実施の形態3に
係る動的メモリ管理機構について図面を参照しながら説
明する。図7は、この発明の実施の形態3に係る動的メ
モリ管理機構の構成を示すブロック図である。図7にお
いて、動的メモリ管理機構1、ヒープ領域2、ガベージ
コレクション手段5、オブジェクト領域10、ポインタ
12は図1と同じであるの説明を省略する。ヒープ領域
2は、さらに、未だ利用されていないメモリ領域から構
成される残利用可能領域13と、既にプログラムから利
用されているメモリ領域から構成される既獲得済み領域
14の2つの領域から構成される。オブジェクト領域1
0は、まずメモリ獲得手段3によりヒープ領域2の一部
である残利用可能領域13から獲得され、これにより獲
得されたオブジェクト領域10は既獲得済み領域14の
一部を構成するようになる。また、オブジェクト領域1
0は、ガベージコレクション手段5に組み込まれて動作
するメモリ開放手段4によって開放されると、再び残利
用可能領域13の一部を構成するようになり、その領域
は再利用可能となる。
【0126】次に、本実施の形態3の動作について説明
する。図8は、本実施の形態3におけるガベージコレク
ション処理(GC処理)の動作を示すフローチャートで
ある。まず、処理開始時点の残利用可能領域13を最初
のTO領域15と定め(S1401)、既獲得済み領域
14のうち、まだガベージコレクション処理の対象とな
っておらず、かつTO領域15と隣接するTO領域15
と同じ量、またはそれより小さい領域をFROM領域1
6と定める(S1402)。なお、FROM領域16を
定める際には、FROM領域16に含まれるすべてのオ
ブジェクト領域10をTO領域15に移してもTO領域
15があふれることが無いよう、FROM領域16の境
界にまたがるオブジェクト領域10があれば、同オブジ
ェクト領域10はFROM領域16から除外する。次
に、大きく以下の3つの段階を踏み、部分ガベージコレ
クション処理(部分GC処理)を行う。まず最初に、計
算機のCPUレジスタ、プログラムが静的に配置したメ
モリ領域、あるいはスタック内の変数としてヒープ領域
2の外部に存在するすべてのポインタ12について、そ
れらのポインタ12から直接参照されるFROM領域1
6内のオブジェクト領域10を探索し、各オブジェクト
領域10をコピーによりTO領域15に移動する(P1
61)。次に、既獲得済み領域14のうちFROM領域
16以外にあるすべてのオブジェクト領域10を探索
し、それらのオブジェクト領域10から直接参照される
FROM領域16内のオブジェクト領域10についても
TO領域15に移動する(S141)。最後に、TO領
域15に移動したオブジェクト領域10を探索し、該当
するオブジェクト領域10から参照されるオブジェクト
領域10についてもコピーによりFROM領域16から
TO領域15へ移動する(P162)。手順P161、
S141、P162により、ヒープ領域2外のポインタ
12からと既獲得済み領域14のうちFROM領域16
以外に存在するオブジェクト領域10から直接または間
接に参照できるすべてのオブジェクト領域10はTO領
域15に移動したので、本段階でFROM領域16に残
るオブジェクト領域10は「ごみ」とみなすことができ
る。部分ガベージコレクション処理(P161、S14
1、P162)が終了すると、TO領域15のうちオブ
ジェクト領域10がコピーされず残った領域と空になっ
たFROM領域16を合わせ、新しい残利用可能領域1
3と定義し直し(S1403)、その後既獲得済み領域
14の中で、部分ガベージコレクション処理の未実施部
分が残っていれば(S1404のYes)、さらに部分
ガベージコレクション処理を繰り返し、既獲得済み領域
14の全体に対しガベージコレクション処理がなされる
ようにする。
【0127】つぎに、手順P161、S141、P16
2の詳細を示す。手順P161では、まずヒープ領域2
外にある適切なポインタ12の1つを選択し(P141
1)、そのポインタ12が有効でFROM領域16内に
あるオブジェクト領域10を参照していれば(P161
1のYes)、ポインタ12が参照するオブジェクト領
域10をコピーによりTO領域15へ移動し(P161
2)、本手順をヒープ領域2の外にあるすべてのポイン
タ12について繰り返す(P1413のYes、P14
14)。
【0128】手順S141では、既獲得済み領域14の
うちFROM領域16以外にオブジェクト領域10があ
れば(S1411のYes)、まず該当するオブジェク
ト領域10を1つ選択し(S1412)、選択したオブ
ジェクト領域10が内部にポインタ12を含めば(P1
313のYes)、まず選択したオブジェクト領域10
に含まれるポインタ12の1つを選び(P1314)、
その値が有効で参照先オブジェクト領域10がFROM
領域16内に存在していれば(P1611のYes)、
参照先のオブジェクト領域10をコピーによりTO領域
15へ移動し処理対象へ加え(P1612)、本手順を
選択したオブジェクト領域10の内部に含まれるすべて
のポインタ12に繰り返し行い(P1315のNo)、
さらに既獲得済み領域14のうちFROM領域16以外
にあるオブジェクト領域10のすべてについて上記手順
を繰り返す(S1413のNo)。
【0129】手順P162では、TO領域15内に未処
理のオブジェクト領域10があれば(P1621のYe
s)、まず該当するオブジェクト領域10を1つ選択し
(P1622)、選択したオブジェクト領域10が内部
にポインタ12を含めば(P1313のYes)、まず
選択したオブジェクト領域10に含まれるポインタ12
の1つを選び(P1314)、その値が有効で参照先オ
ブジェクト領域10がFROM領域16内に存在してい
れば(P1611のYes)、参照先のオブジェクト領
域10をコピーによりTO領域15へ移動し処理対象へ
加え(P1612)、本手順を選択したオブジェクト領
域10の内部に含まれるすべてのポインタ12に繰り返
し行い(P1315のNo)、さらにTO領域15内の
オブジェクト領域10のすべてについて上記手順を繰り
返す(P1623のNo)。
【0130】本実施の形態3の具体的な動作の様子を図
9を用いて説明する。
【0131】図9は、本実施の形態3の動作を示す解説
図である。図9に示される処理前の状況は、残利用可能
領域13を最初のTO領域15とし(S1401)、既
獲得済み領域14のうちTO領域15に隣接するTO領
域15と同じ量の領域を最初のFROM領域16と設定
した(S1402)段階を示している。本状況に対し1
回目の部分ガベージコレクション処理(P161、P1
41、P162)と手順S1403を行い、さらに手順
S1401、S1402を行い新しいTO領域15およ
びFROM領域16を設定した段階が、図9に示される
1回目部分GC処理後の状況である。本段階では、前段
階のFROM領域16に含まれていたオブジェクト領域
は、第5の従来例として示したストップ−コピー方式と
同様の処理によって、「ごみ」が取除かれ前段階のTO
領域15の図中右側の領域に集められ、前段階のTO領
域15で余った領域(図中左側の領域)と前段階のFR
OM領域16を合併し新たなTO領域15に設定され、
また未だガベージコレクション処理がなされていない既
獲得済み領域14のうち新たなTO領域15に隣接する
同量の領域が新たなFROM領域16に設定されてい
る。本状況に対し2回目の部分ガベージコレクション処
理(P161、P141、P162)と手順S140
3、さらに手順S1401、S1402を行い新しいT
O領域15およびFROM領域16を設定した段階が、
図9に示される2回目部分GC処理後の状況であり、さ
らに3回目の部分ガベージコレクション処理(P16
1、P141、P162)と手順S1403を行った段
階が、図9に示される3回目部分GC処理後の状況であ
る。図9の3回目部分GC処理後では、未だガベージコ
レクション処理がなされていない既獲得済み領域14が
なくなったので、部分ガベージコレクション処理を繰り
返す必要はなく、ガベージコレクション処理の全体が終
了する。
【0132】本実施の形態3は上記のように動作するこ
とで、第5の従来例に挙げたストップ−コピー方式と同
様に、循環する参照を持つオブジェクト領域でも正しく
回収できる、フラグメンテーション現象が発生しない、
「生きている」オブジェクト領域と「ごみ」の区別のた
めの処理が速いなどの利点を有し、かつストップ−コピ
ー方式とは異なり半分以上のヒープ領域2を利用するこ
とができ、メモリ利用効率を高めることができる。
【0133】なお、本実施の形態3では部分ガベージコ
レクション処理に第5の従来例に挙げたストップ−コピ
ー方式と同様の手順(手順P161、S141、P16
2)を用いているため、例えば第7の従来例として示し
たような、ストップ−コピー方式をインクリメンタル方
式化する既存の技術を適用することで、本実施の形態3
を容易にインクリメンタル方式に拡張することができ、
計算機システムの定応答性を向上させることができる。
【0134】また、本実施の形態3は部分ガベージコレ
クション処理を繰り返す際に、その繰り返し間で処理の
独立性が高いので、手順S1404から手順S1401
に戻る部分で一旦ガベージコレクション処理を休止し応
用プログラムの動作を行うようにし、ガベージコレクシ
ョン処理による応用プログラムの動作の中断時間を短く
することが容易に可能である。このような変形により、
インクリメンタル方式化の技術を適用せずとも、少ない
オーバヘッドで応用プログラムの動作の応答性を向上さ
せることができる。この際、部分ガベージコレクション
処理の繰り返しにおいて、用いるTO領域15の大きさ
に上限を課すようにすることで、各部分ガベージコレク
ション処理の処理時間を短くかつ予測可能とすることが
でき、応用プログラムの動作の応答性をより向上させる
ことができる。
【0135】また、本実施の形態3において、部分ガベ
ージコレクション処理を繰り返す際に、新しくできた残
利用可能領域13の大きさが、あらかじめ定められた閾
値を超えたところで処理を打ち切るようにすることで、
ガベージコレクション処理全体の処理時間の短縮を図る
ことができる。この場合もまた、部分ガベージコレクシ
ョン処理の繰り返しにおいてTO領域15の大きさに対
し、固定的あるいは適応的に上限を課すようにすること
で、不要に大きな残利用可能領域13を集めないように
することができ、処理時間の短縮を図ることができる。
なお、処理打ち切りの閾値は、例えばシステムのCPU
負荷状況など、システムの動作の状況に応じて変化する
値とすることもでき、これによりガベージコレクション
処理の重さや確保する残利用可能領域13を制御し、計
算機システム全体の効率向上を図ることができる。
【0136】実施の形態4.この発明の実施の形態4
は、実施の形態3におけるガベージコレクション処理の
動作を一部変更したものである。その基本構成は実施の
形態3と同一であるので説明を省略する。
【0137】図10は、実施の形態4におけるガベージ
コレクション処理の動作を示すフローチャートである。
本動作もまた、実施の形態3におけるガベージコレクシ
ョン処理S140と同様、部分ガベージコレクション処
理を繰り返すが、手順S140と異なり、部分ガベージ
コレクション処理に先立ち、ヒープ領域外にあるポイン
タ12の一覧であるベースポインタリストを作成する。
すなわち、まずヒープ領域2外にある適切なポインタ1
2の1つを選択し(P1411)、そのポインタ12が
オブジェクト領域10を参照する有効な値であれば(P
1201のYes)、そのポインタ12の値をベースポ
インタリストへ保存し(S1501)、本手順をヒープ
領域2の外にあるすべてのポインタ12について繰り返
す(P1413のYes、P1414)。
【0138】続いて、まず処理開始時点の残利用可能領
域13を最初のTO領域15と定め(S1401)、既
獲得済み領域14のうちまだガベージコレクション処理
の対象となっておらず、かつTO領域15と隣接するT
O領域15と同じ量、またはそれより小さい領域をFR
OM領域16と定める(S1402)。なお、FROM
領域16を定める際には、実施の形態3のガベージコレ
クション処理同様、FROM領域16に含まれるすべて
のオブジェクト領域10をTO領域15に移してもTO
領域15があふれることが無いよう、FROM領域16
の境界にまたがるオブジェクト領域10があれば、同オ
ブジェクト領域10はFROM領域16から除外する。
次に、大きく以下の3つの段階を踏み、部分ガベージコ
レクション処理(部分GC処理)を行う。まず最初に、
ベースポインタリストを元に、ヒープ領域2の外部に存
在するポインタ12から直接参照されるFROM領域1
6内のオブジェクト領域10を探索し、各オブジェクト
領域10をコピーによりTO領域15に移動する(S1
51)。次に、既獲得済み領域14のうちFROM領域
16以外にあるすべてのオブジェクト領域10を探索
し、それらのオブジェクト領域10から直接参照される
FROM領域内のオブジェクト領域10についてもTO
領域15に移動する(S141)。最後に、TO領域1
5に移動したオブジェクト領域10を探索し、該当する
オブジェクト領域10から参照されるオブジェクト領域
10についてもコピーによりFROM領域16からTO
領域15へ移動する(P162)。手順P161、S1
41、P162により、ヒープ領域外のポインタ12か
らと既獲得済み領域14のうちFROM領域16以外に
存在するオブジェクト領域10から直接または間接に参
照できるすべてのオブジェクト領域10はTO領域15
に移動したので、本段階でFROM領域16に残るオブ
ジェクト領域10は「ごみ」とみなすことができる。部
分ガベージコレクション処理(S151、S141、P
162)が終了すると、TO領域15のうちオブジェク
ト領域10がコピーされず残った領域と空になったFR
OM領域16を合わせ、新しい残利用可能領域13と定
義し直し(S1403)、その後既獲得済み領域14の
中で、部分ガベージコレクション処理の未実施部分が残
っていれば(S1404のYes)、手順S1401に
戻ってさらに部分ガベージコレクション処理を繰り返
し、既獲得済み領域14の全体に対しガベージコレクシ
ョン処理がなされるようにする。
【0139】次に、手順S151の詳細を示す。なお、
手順S141及び手順P162の詳細は、実施の形態3
(図8)における詳細と同一であるため説明を省略す
る。
【0140】手順S151では、まずベースポインタリ
ストにポインタが保存されていれば(S1511のYe
s)、保存されているポインタのうち最初の要素を選択
し(S1512)、そのポインタ12が有効でFROM
領域16内にあるオブジェクト領域を参照していれば
(S1513のYes)、ポインタ12が参照するオブ
ジェクト領域10をコピーによりTO領域15へ移動し
(P1612)、該当ポインタ12に対応する要素をベ
ースポインタリストから削除する(S1514)。本手
順をベースポインタリストに保持されるすべてのポイン
タ12について繰り返す(S1515のYes、S15
16)。
【0141】本実施の形態4は上記のように動作するこ
とで、実施の形態3と異なり、ヒープ領域2外にあるポ
インタ12の探索を部分ガベージコレクション処理毎に
行うのでなく、ガベージコレクション処理全体で1回の
み行い、かつポインタ12の参照先が一度ガベージコレ
クション処理の対象になればその後は検査対象になら
ず、ヒープ領域2外のポインタ12の探索処理が効率化
されており、ガベージコレクション処理全体の処理時間
を短縮できる。
【0142】なお、実施の形態3同様、本実施の形態4
もストップ−コピー方式をインクリメンタル方式化する
ための既存の技術を適用することで、容易にインクリメ
ンタル方式に拡張することができ、計算機システムの定
応答性を向上させることができる。また、部分ガベージ
コレクション処理を繰り返す際に新しくできた残利用可
能領域の大きさが、適切に定められた閾値を超えたとこ
ろで処理を打ち切るようにすることで、やはりガベージ
コレクション処理全体の短縮を図ることができる。
【0143】実施の形態5.この発明の実施の形態5
は、実施の形態3におけるガベージコレクション処理の
動作を詳細化したものである。その基本構成は実施の形
態3と同一であるので説明を省略する。また、ガベージ
コレクション処理の基本動作も実施の形態3と同一であ
るので説明を省略する。
【0144】本実施の形態5は、実施の形態3におい
て、メモリ獲得手段3が残利用可能領域13の常に同じ
一端から獲得するよう動作し、ガベージコレクション処
理内で繰り返す部分ガベージコレクション処理は、メモ
リ獲得手段3の上記動作に適合するよう、分割されたF
ROM領域16及びTO領域15を扱えるようにし、こ
れによりガベージコレクション処理の繰り返しにおい
て、残利用可能領域13がヒープ領域2内を常に一方向
へ移動するよう動作させたものである。
【0145】本実施の形態5の具体的な動作の様子を図
11を用いて説明する。図11は、本実施の形態5の動
作を示す解説図である。本実施の形態5では、メモリ獲
得手段3は常に残利用可能領域13の図中左側からオブ
ジェクト領域10を獲得する。図11に示される前回G
C処理前の状況は、メモリ獲得手段3は残利用可能領域
13に対し図中左側からにオブジェクト領域10を獲得
し、既獲得済み領域14が成長してきたことを示す。本
状況に対し本実施の形態5に示すガベージコレクション
処理を1回行った段階が図11に示される前回GC処理
後の状況である。図11に示される前回GC処理前の状
況は、実施の形態3の動作を示す図9に示される処理前
の状況に等しく、図11に示される前回GC処理後の状
況は、図9に示される第3回目部分GC処理後の状況に
等しい。本実施の形態5のガベージコレクション処理
は、図11に示される前回GC処理前の状況、すなわち
ヒープ領域2の図中右端に残利用可能領域13があると
きは、実施の形態3と同様に動作する。
【0146】図11に示す前回GC処理後の状況から、
応用プログラムの動作によりメモリ獲得手段3が呼び出
され、複数のオブジェクト領域が新たに獲得された段階
が、図11に示される今回GC処理前の状況である。図
11に示す前回GC後の状況では、残利用可能領域13
はヒープ領域2の図中左端にあったが、本実施の形態5
ではメモリ獲得手段3は常に残利用可能領域13の図中
左側からオブジェクト領域10を獲得するため、既獲得
済み領域14はヒープ領域2の図中左端にも成長し、図
11に示される今回GC処理前の状況では、残利用可能
領域13の図中左側および右側の両方に既獲得済み領域
14が存在するようになっている。
【0147】図11に示す今回GC処理前の状況から、
本実施の形態5におけるガベージコレクション処理での
部分ガベージコレクション処理の1回目が終わった段階
が、図11に示す1回目部分GC処理後の状況である。
本段階の部分ガベージコレクション処理に用いたFRO
M領域16は、TO領域15に対し図中左側の既獲得済
み領域14から、TO領域15に隣接するようにTO領
域15と同量を設定した。本段階では、領域の大きさの
関係からFROM領域16はヒープ領域2の図中左端に
達成していないため、図11に示す1回目部分GC処理
後の状況は、単にFROM領域16をTO領域15の図
中右端へ詰める形で動作した結果となっている。
【0148】図11に示す1回目部分GC処理後の状況
から、本実施の形態5におけるガベージコレクション処
理での部分ガベージコレクション処理の2回目が終わっ
た段階が、図11に示す2回目部分GC処理後の状況で
ある。2回目の部分ガベージコレクション処理に用いた
FROM領域16は、前回と異なり、TO領域15の図
中左側にある残利用可能領域14だけではTO領域15
と同量の領域を確保できないため、TO領域15に対し
図中右側にある既獲得済み領域14からも、同領域の右
端から不足分を補うFROM領域16を設定し、両者を
連続した1つのFROM領域16とみなして部分ガベー
ジコレクション処理を行う。この結果、図11に示す2
回目部分GC処理後の状況では、新たに設定される残利
用可能領域13、すなわち3回目の部分ガベージコレク
ション処理でのTO領域15が、ヒープ領域2の図中左
端と右端に分割される。
【0149】図11に示す2回目部分GC処理後の状況
から、本実施の形態5におけるガベージコレクション処
理での部分ガベージコレクション処理の3回目が終わっ
た段階が、図11に示す3回目部分GC処理後の状況で
ある。本段階の部分ガベージコレクション処理に用いた
TO領域15はヒープ領域2の図中右端と左端の2つに
分かれて存在するので、両者を連続した1つのTO領域
とみなして部分ガベージコレクション処理を行う。本段
階ではFROM領域16となるGC未実施の既獲得済み
領域14があまり残っていないため、図11の3回目部
分GC処理の状況では、図中左側のTO領域15の一部
にFROM領域16を詰める形で動作した結果となって
いるが、FROM領域16の内部に存在する「生きてい
る」オブジェクト領域の量によっては、図中左側のTO
領域15だけでは収まらず右側のTO領域15にも詰め
るよう動作する。
【0150】本実施の形態5は上記のように動作するこ
とで、常に既獲得済み領域14内に存在するオブジェク
ト領域10のうち、メモリ獲得手段3によって応用プロ
グラムが獲得してから時間の経過の少ない「若い」オブ
ジェクト領域10を優先してガベージコレクション処理
の対象とすることができ、ガベージコレクション処理の
効率が向上する。さらに、部分ガベージコレクション処
理を繰り返す際に、新しくできた残利用可能領域13の
大きさが適切に定められた閾値を超えたところで処理を
打ち切る動作と併用することで、その効果が向上する。
【0151】なお、本実施の形態5では「若い」オブジ
ェクト領域10を優先してガベージコレクション処理の
対象としたが、図11の今回GC処理前の状況におい
て、1回目部分GC処理におけるFROM領域16をT
O領域15に隣接する右側の既獲得済み領域14から設
定し、以降の部分ガベージコレクション処理でも同様に
設定することで、本実施の形態5とは逆に「古い」オブ
ジェクト領域10を優先してガベージコレクション処理
の対象とすることも容易に可能であり、これによりオブ
ジェクト領域10の寿命に関する挙動が一般的な応用プ
ログラムとは異なるプログラムに対するガベージコレク
ション処理の効率を向上させることができる。
【0152】実施の形態6.この発明の実施の形態6
は、実施の形態3におけるガベージコレクション処理の
動作を詳細化したものである。その基本構成は実施の形
態3と同一であるので説明を省略する。また、ガベージ
コレクション処理の基本的動作も実施の形態3と同一で
あるので説明を省略する。
【0153】本実施の形態6は、実施の形態3におい
て、ガベージコレクション処理により残利用可能領域1
3がヒープ領域2の端に達する度に、メモリ獲得手段3
が残利用可能領域13の異なる端から獲得するよう動作
し、ガベージコレクション処理内で繰り返す部分ガベー
ジコレクション処理は、メモリ獲得手段3の上記動作に
適合するよう、FROM領域16からオブジェクト領域
10を、TO領域15内でメモリ獲得手段13が獲得す
る端とは逆の端へ詰めるように移動させ、これによりガ
ベージコレクション処理の繰り返しにおいて、残利用可
能領域13がヒープ領域2内を往復するよう動作させた
ものである。
【0154】本実施の形態6の具体的な動作の様子を図
12を用いて説明する。図12は、本実施の形態6の動
作を示す解説図である。図12に示される前回GC処理
前の状況は、メモリ獲得手段3は残利用可能領域13に
対し図中左側からにオブジェクト領域10を獲得し、既
獲得済み領域14が成長してきたことを示す。本状況に
対し本実施の形態6に示すガベージコレクション処理を
1回行った段階が図12に示される前回GC処理後の状
況である。図12に示される前回GC処理前の状況は、
実施の形態3の動作を示す図9に示される処理前の状況
に等しく、図12に示される前回GC処理後の状況は、
図9に示される第3回目部分GC処理後の状況に等し
い。本実施の形態6のガベージコレクション処理は、図
12に示される前回GC処理前の状況、すなわちヒープ
領域2の図中右端に残利用可能領域13があるときは、
実施の形態3と同様に動作する。
【0155】図12に示す前回GC処理後の状況から、
応用プログラムの動作によりメモリ獲得手段3が呼び出
され、複数のオブジェクト領域10が新たに獲得された
段階が、図12に示される今回GC処理前の状況であ
る。本実施の形態6のメモリ獲得手段3は、残利用可能
領域13がヒープ領域2の図中右端にある時は残利用可
能領域13の図中左端からオブジェクト領域10を獲得
し、逆に残利用可能領域13がヒープ領域2の図中左端
にあるときは残利用可能領域13の図中右端からオブジ
ェクト領域10を獲得するよう動作するので、図11に
示される実施の形態5とは異なり、図12に示す前回G
C処理後の状況で、残利用可能領域13はヒープ領域2
の図中左端にあったのを保つよう、既獲得済み領域14
は残利用可能領域13の図中右端から成長し、図11に
示される今回GC処理前の状況では、残利用可能領域1
3はヒープ領域2の図中左端に接するよう存在し、既獲
得済み領域14はヒープ領域2の図中右端に接するよう
存在している。
【0156】図12に示す今回GC処理前の状況から、
本実施の形態6におけるガベージコレクション処理での
部分ガベージコレクション処理の1回目が終わった段階
が、図12に示す1回目部分GC処理後の状況である。
本段階の部分ガベージコレクション処理に用いたFRO
M領域16は、TO領域15に対し図中右側の既獲得済
み領域14から、TO領域15に隣接するようにTO領
域15と同量を設定、これにより図12に示す1回目部
分GC処理後の状況は、単にFROM領域16をTO領
域15の図中左端へ詰める形で動作した結果となってい
る。
【0157】図12に示す1回目部分GC処理後の状況
から、本実施の形態6におけるガベージコレクション処
理での部分ガベージコレクション処理の2回目が終わっ
た段階が、図12に示す2回目部分GC処理後の状況で
ある。2回目の部分ガベージコレクション処理に用いた
FROM領域16もまた、前回同様、TO領域15に対
し図中右側の既獲得済み領域14からTO領域15に隣
接するようにTO領域15と同量を設定、これにより図
12に示す2回目部分GC処理後の状況も、1回目部分
GC処理後の状況と同様、単にFROM領域16をTO
領域15の図中左端へ詰める形で動作した結果となって
いる。
【0158】図12に示す2回目部分GC処理後の状況
から、本実施の形態6におけるガベージコレクション処
理での部分ガベージコレクション処理の3回目が終わっ
た段階が、図12に示す3回目部分GC処理後の状況で
ある。本段階の部分ガベージコレクション処理でもま
た、前回同様、TO領域15に対し図中右側の既獲得済
み領域14からTO領域15に隣接するようにFROM
領域16を設定、これにより図12に示す2回目部分G
C処理後の状況も、1回目部分GC処理後の状況と同
様、単位FROM領域16をTO領域15の図中左端へ
詰める形で動作した結果となっている。
【0159】本実施の形態6は上記のように動作するこ
とで、少なくとも既獲得済み領域14内に存在するオブ
ジェクト領域10のうち、前回ガベージコレクション処
理が行われてからメモリ獲得手段3によって応用プログ
ラムが獲得した「若い」オブジェクト領域10を優先し
てガベージコレクション処理の対象とすることで、ガベ
ージコレクション処理の効率を保ちながら、実施の形態
5よりガベージコレクション処理の動作を簡素にするこ
とができる。
【0160】なお、本実施の形態6において、部分ガベ
ージコレクション処理を繰り返す際に、新しくできた残
利用可能領域13の大きさが適切に定められた閾値を超
えたところで処理を打ち切る場合や、部分ガベージコレ
クション処理の合間に応用プログラムを動作できるよう
にする場合では、残利用可能領域13がヒープ領域2の
右端から左端へ移動しているときはメモリ獲得手段3は
残利用可能領域13の左端からオブジェクト領域10を
獲得し、逆に残利用可能領域13がヒープ領域2の左端
から右端へ移動しているときはメモリ獲得手段3は残利
用可能領域13の右端からオブジェクト領域10を獲得
するようにすることで、本実施の形態6と同じ効果をえ
ることができる。
【0161】実施の形態7.この発明の実施の形態7
は、実施の形態3におけるガベージコレクション処理の
動作を一部変更したものである。その基本構成は実施の
形態3と同一であるので説明を省略する。
【0162】図13は、実施の形態7におけるガベージ
コレクション処理の動作を示す全体のフローチャートで
ある。本動作もまた、実施の形態3におけるガベージコ
レクション処理S140と同様、部分ガベージコレクシ
ョン処理を繰り返すが、手順S140と異なり、部分ガ
ベージコレクション処理に先立ち、まず現在の残利用可
能領域13の大きさが部分ガベージコレクション処理を
行うのに十分であるか調べ(S1601)、もし十分で
なければ(S1601のNo)マーク−コンパクト方式
に類似したコンパクト式の部分ガベージコレクション処
理(部分コンパクト処理)を行い残利用可能領域13の
大きさを拡充し(S161)、その後、部分ガベージコ
レクション処理を行うため、手順S140と同様に、ま
ず処理開始時点の残利用可能領域13を最初のTO領域
15と定め(S1401)、既獲得済み領域14のう
ち、まだガベージコレクション処理の対象となっておら
ず、かつTO領域15と隣接するTO領域15と同じ
量、またはそれより小さい領域をFROM領域16と定
める(S1402)。なお、FROM領域16を定める
際には、第3の従来例のガベージコレクション処理同
様、FROM領域16に含まれるすべてのオブジェクト
領域をTO領域15に移してもTO領域があふれること
が無いよう、FROM領域16の境界にまたがるオブジ
ェクト領域10があれば、同オブジェクト領域10はF
ROM領域16から除外する。次に、大きく以下の3つ
の段階を踏み、部分ガベージコレクション処理(部分G
C処理)を行う。まず最初に、計算機のCPUレジス
タ、プログラムが静的に配置したメモリ領域、あるいは
スタック内の変数としてヒープ領域2の外部に存在する
すべてのポインタ12について、それらのポインタ12
から直接参照されるFROM領域16内のオブジェクト
領域10を探索し、各オブジェクト領域10をコピーに
よりTO領域15に移動する(P161)。次に、既獲
得済み領域14のうちFROM領域16以外にあるすべ
てのオブジェクト領域10を探索し、それらのオブジェ
クト領域10から直接参照されるFROM領域16内の
オブジェクト領域10についてもTO領域15に移動す
る(S141)。最後に、TO領域15に移動したオブ
ジェクト領域10を探索し、該当するオブジェクト領域
10から参照されるオブジェクト領域10についてもコ
ピーによりFROM領域16からTO領域15へ移動す
る(P162)。手順P161、S141、P162に
より、ヒープ領域外のポインタ12からと既獲得済み領
域14のうちFROM領域16以外に存在するオブジェ
クト領域10から直接または間接に参照できるすべての
オブジェクト領域10はTO領域15に移動したので、
本段階でFROM領域16に残るオブジェクト領域10
は「ごみ」とみなすことができる。部分ガベージコレク
ション処理( P161、S141、P162)が終了
すると、TO領域15のうちオブジェクト領域10がコ
ピーされず残った領域と空になったFROM領域16を
合わせ、新しい残利用可能領域13と定義し直し(S1
403)、その後既獲得済み領域14の中で、部分ガベ
ージコレクション処理の未実施部分が残っていれば(S
1404のYes)、手順S1401に戻ってさらに部
分ガベージコレクション処理を繰り返し、既獲得済み領
域14の全体に対しガベージコレクション処理がなされ
るようにする。なお、ガベージコレクション処理の開始
時に十分な残利用可能領域13が存在する場合は、手順
S151は行わず、直接手順S1401に進む。
【0163】手順P161、手順S141、手順P16
2の詳細は、実施の形態3(図8)における詳細と同一
であるため説明を省略する。
【0164】次に、手順S161に示した、コンパクト
方式による部分ガベージコレクション処理(部分コンパ
クト処理)の詳細を示す。図14は、本実施の形態7お
けるガベージコレクション処理の動作を示す部分コンパ
クト処理のフローチャートである。本動作では、まず処
理開始時点の残利用可能領域13を最初のTO領域15
と定め(S1401)、既獲得済み領域14のうちTO
領域15と隣接する適切な大きさをFROM領域16と
定める(S1611)。なお、部分コンパクト処理S1
61実施後に得られる残利用可能済み領域13の大きさ
は、手順S1401で定めたTO領域15の大きさと手
順S1611で定めたFROM領域16の大きさの和か
ら、同FROM領域16に含まれる「生きている」オブ
ジェクト領域10の総量を減じたものとなる。このため
手順S1611で定めるFROM領域16の大きさは、
図13の手順S1601における現在の残利用可能領域
13の大きさが部分ガベージコレクション処理を行うの
に十分であるかの判断と関連付けて、部分コンパクト処
理S161終了後に、部分ガベージコレクション処理を
行うに適切な値が得られることが期待できる、適切な大
きさとする。
【0165】次に、大きく以下の3つの段階を踏み、F
ROM領域16内の「生きている」オブジェクト領域1
0を抽出する。まず最初に、計算機のCPUレジスタ、
プログラムが静的に配置したメモリ領域、あるいはスタ
ック内の変数としてヒープ領域2の外部に存在するすべ
てのポインタ12について、それらのポインタ12から
直接参照されるFROM領域16内のオブジェクト領域
10を探索し、未検出のオブジェクト領域10があれ
ば、同オブジェクト領域10を有効オブジェクト領域リ
ストへ追加する(S162)。次に、既獲得済み領域1
4のうちFROM領域16以外にあるすべてのオブジェ
クト領域10を探索し、それらのオブジェクト領域10
から直接参照されるFROM領域内のオブジェクト領域
10についても、未検出のオブジェクト領域10であれ
ば、同オブジェクト領域10を有効オブジェクト領域リ
ストへ追加する(S163)。最後に、有効オブジェク
ト領域リストを探索し、有効オブジェクト領域リストに
あるオブジェクト領域10から参照されるFROM領域
16内のオブジェクト領域10についても、未検出であ
れば有効オブジェクト領域リストへ追加する(S16
4)。手順S162、S163、S164により、ヒー
プ領域外のポインタ12からと既獲得済み領域14のう
ちFROM領域16以外に存在するオブジェクト領域1
0から直接または間接に参照できるすべてのオブジェク
ト領域10は有効オブジェクト領域リストに登録された
ので、本段階でFROM領域16に存在し、かつ有効オ
ブジェクト領域リストに登録されていないオブジェクト
領域10は「ごみ」とみなすことができる。FROM領
域16内の「生きている」オブジェクト領域10の抽出
(S162、S163、S164)が終了すると、有効
オブジェクト領域リストに登録されているすべてのオブ
ジェクト領域10を、TO領域15とFROM領域16
を合わせた領域へ、TO領域16側から先に詰めるよ
う、コピーにより移動し(S1612)、その後、移動
により空となった領域を新しい残利用可能領域13と定
義し直す(S1613)。
【0166】次に、手順S162、手順S163、手順
S164の詳細を示す。
【0167】手順S162では、まずヒープ領域2外に
ある適切なポインタ12の1つを選択し(P141
1)、そのポインタ12が有効でFROM領域16内に
ある未検出のオブジェクト領域10を参照していれば
(S1621のYes)、ポインタ12が参照するオブ
ジェクト領域10を有効オブジェクト領域リストに追加
登録し(S1622)、本手順をヒープ領域2の外にあ
るすべてのポインタ12について繰り返す(P1413
のYes、P1414)。
【0168】手順S163では、既獲得済み領域14の
うちFROM領域16以外にオブジェクト領域10があ
れば(S1411のYes)、まず該当するオブジェク
ト領域10を1つ選択し(S1412)、選択したオブ
ジェクト領域10が内部にポインタ12を含めば(P1
313のYes)、まず選択したオブジェクト領域10
に含まれるポインタ12の1つを選び(P1314)、
その値が有効でFROM領域16内にある未検出のオブ
ジェクト領域10を参照していれば(S1621のYe
s)、参照先のオブジェクト領域10を有効オブジェク
ト領域リストに追加登録し(S1622)、本手順を選
択したオブジェクト領域10の内部に含まれるすべての
ポインタ12に繰り返し行い(P1315のNo)、さ
らに既獲得済み領域14のうちFROM領域16以外に
あるオブジェクト領域10のすべてについて上記手順を
繰り返す(S1413のNo)。
【0169】手順S164では、有効オブジェクト領域
リストに未処理のオブジェクト領域10があれば(S1
641のYes)、有効オブジェクト領域リストからま
ず該当するオブジェクト領域10を1つ選択し(S16
42)、選択したオブジェクト領域10が内部にポイン
タ12を含めば(P1313のYes)、まず選択した
オブジェクト領域10に含まれるポインタ12の1つを
選び(P1314)、その値が有効でFROM領域16
内にある未検出のオブジェクト領域10を参照していれ
ば(S1621のYes)、参照先のオブジェクト領域
10を有効オブジェクト領域リストに追加登録し(S1
622)、本手順を選択したオブジェクト領域10の内
部に含まれるすべてのポインタ12に繰り返し行い(P
1315のNo)、さらに有効オブジェクト領域リスト
に登録されているオブジェクト領域10のすべてについ
て上記手順を繰り返す(S1643のNo)。
【0170】本実施の形態7の具体的な動作の様子を図
15を用いて説明する。
【0171】図15は、本実施の形態7の動作を示す解
説図である。図15に示される処理前の状態は、残利用
可能領域13を部分コンパクト処理S161におけるT
O領域15とし(S1401)、既獲得済み領域14の
うちTO領域15に隣接する適切な量の領域を部分コン
パクト処理S161におけるFROM領域16と設定し
た(S1611)段階を示している。本状況に対しFR
OM領域16内の「生きている」オブジェクト領域10
の抽出(S162、S163、S164)した段階が、
図15に示される有効オブジェクト探索後の状況であ
る。さらに本状況に対し、有効オブジェクト領域リスト
に登録されているすべてのオブジェクト領域10を、T
O領域15とFROM領域16を合わせた領域へ、TO
領域15側から先に詰めるよう、コピーにより移動(S
1612)した段階が、図15に示される部分コンパク
ト処理後の状況である。
【0172】本実施の形態7は上記のように、ガベージ
コレクション処理開始前の残利用可能領域13が小さい
場合に、部分コンパクト処理を行いあらかじめ残利用可
能領域13を大きくしてから実施の形態3として示した
ガベージコレクション処理を行うよう動作することで、
ガベージコレクション処理開始前の残利用可能領域13
の大きさが小さい場合に部分ガベージコレクション処理
の繰り返し回数が多くなってしまうという問題を回避す
ることができ、ガベージコレクション処理の効率を上げ
ることができる。
【0173】なお、本実施の形態7では部分コンパクト
処理S162において、FROM領域16内の「生きて
いる」オブジェクト領域10を抽出するために有効オブ
ジェクト領域リストを用い、その後「生きている」オブ
ジェクト領域を1つにまとめる方式を用いたが、手順S
162に示した方式に代え、例えば第4の従来例に示し
たマーク−コンパクト方式、さらにはその改良方式を用
いてもよく、同様の効果を得ることができる。
【0174】また、本実施の形態7では部分コンパクト
処理S162を1回のみ行うようにしたが、適切な残利
用可能領域13の大きさが得られるまで繰り返し行うよ
うにしても、同様の効果を得ることができ、更にはガベ
ージコレクション処理全体を部分コンパクト処理S16
2のみの繰り返しで行うようにしてもよい。
【0175】さらに、本実施の形態7は、実施の形態3
同様、既存のインクリメンタル方式化技術を適用するこ
とで、容易にインクリメンタル方式に拡張することがで
き、計算機システムの定応答性を向上させることができ
る。
【0176】またさらに、本実施の形態7は、やはり実
施の形態3同様、部分コンパクト処理S162や部分ガ
ベージコレクション処理(図13のS1401〜S14
04)の処理の移行及び処理の繰り返し間で、処理に独
立性が高いので、これらの部分で一旦ガベージコレクシ
ョン処理を休止し応用プログラムの動作を行うように
し、ガベージコレクション処理による応用プログラムの
動作の中断時間を短くすることが容易に可能である。
【0177】さらに、本実施の形態7は、やはり実施の
形態3同様、部分コンパクト処理S162や部分ガベー
ジコレクション処理(図13のS1401〜S140
4)の処理の移行および処理の繰り返し部分で、新しく
できた残利用可能領域13の大きさが適切な閾値を超え
たところで処理を打ち切るようにすることで、ガベージ
コレクション処理全体の短縮を図ることができる。
【0178】実施の形態8.図16は、この発明の実施
の形態8の基本構成を示す構成図である。図16におい
て、ヒープ領域2、オブジェクト領域10、ポインタ1
2は図7と同じであるので説明を省略する。また、動的
メモリ管理機構1、メモリ獲得手段3、メモリ開放手段
4、ガベージコレクション手段5は本実施の形態8の動
作の説明上重要でないためその記述を省略している。参
照テーブル17は、ヒープ領域2内の各オブジェクト領
域10への参照を保持するテーブルであり、ヒープ領域
2の外部に存在する。
【0179】次に、本実施の形態8の動作を説明する。
本実施の形態8(図16)は、実施の形態3(図7)と
異なり、ポインタ12は直接オブジェクト領域10を参
照せず、必ず参照テーブル17のエントリを経由してオ
ブジェクト領域10への参照を行う。参照テーブル17
のエントリとオブジェクト領域10の対応づけは、オブ
ジェクト領域10を生成するメモリ獲得手段3により成
され、オブジェクト領域10が存在している間は、オブ
ジェクト領域10が「生きている」場合でも「ごみ」の
場合でもその対応づけは不変であり、オブジェクト領域
10を開放するメモリ開放手段4によりその対応付けが
失われる。また、ガベージコレクション手段5が行うガ
ベージコレクション処理に付随してオブジェクト領域1
0の配置が移動する場合は、参照テーブル17のエント
リの内容は対応するオブジェクト領域10を正しく参照
できるよう、その内容が更新される。一方、ポインタ1
2は、オブジェクト領域10への参照に必要な情報を、
参照テーブル17のエントリを特定する情報として保持
する。ポインタ12からオブジェクト領域10を参照す
る場合は、常にまずポインタ12の保持する情報を元に
参照テーブル17のエントリを特定し、該当するエント
リの保持する情報を元に対応するオブジェクト領域10
にたどり着く形で行われる。
【0180】本実施の形態8では、参照テーブル17は
エントリの配列であり、ポインタ12は参照テーブル1
7でエントリを特定するための配列の添え字(整数値)
を保持し、参照テーブルのエントリは対応するオブジェ
クト領域10に関するメモリ領域上の先頭アドレスを保
持する。図16において、オブジェクト領域Aを参照す
るヒープ領域2外にあるポインタRp及びオブジェクト
領域B内のポインタBp1は、共に参照テーブル17内
でオブジェクト領域Aに対応づけられた同じエントリを
指すよう、同じ該当エントリの配列の添え字を保持す
る。同様に、オブジェクト領域Bを参照するオブジェク
ト領域A内のポインタAp2は、参照テーブル17内で
オブジェクト領域Bに対応づけられたエントリを指すよ
う、該当エントリの配列の添え字を保持する。無効な値
を保持しているオブジェクト領域B内のポインタBp2
は、参照テーブル17内で無効な値を示すための特別な
エントリを指すよう、該当エントリの配列の添え字を保
持する。ガベージコレクション処理によりメモリ領域上
でのオブジェクト領域10の配置位置が変化した場合
は、参照テーブル17の対応するエントリの保持するア
ドレス値のみが変更され、ポインタ12の値は変更され
ない。
【0181】本実施の形態8は上記のように動作するこ
とにより、第6の従来例と同様に、ガベージコレクショ
ン処理によってオブジェクト領域10が移動する際に、
同オブジェクト領域10を指すポインタ12の調整処理
を単純にすることができ、かつ第6の従来例とは異な
り、参照テーブル17がヒープ領域2から独立している
ので、第4の従来例に示したマーク−コンパクト方式
や、あるいは実施の形態7における部分コンパクト処理
(S161)のような、オブジェクト領域10の移動に
際し移動前の領域が破壊されるガベージコレクション方
式に組み合わせることが可能である。また、存在するオ
ブジェクト領域10はすべて参照テーブル17に登録さ
れているので、ガベージコレクション処理に際し参照テ
ーブル17を用いることでオブジェクト領域10の探索
が容易になり、さらにガベージコレクション処理時に比
較的大きさの小さい参照テーブル17を頻繁にアクセス
することで、計算機システム内の仮想アドレス変換キャ
ッシュやメモリキャッシュの動作効率が向上すること
で、ガベージコレクション処理の処理速度が高まるとい
う効果が得られる。
【0182】本実施の形態8における参照テーブル17
の大きさは、少なくともヒープ領域2内に同時に存在す
るすべてのオブジェクト領域10に対応したエントリを
保持できる大きさであればよく、ヒープ領域2内に同時
に存在できるオブジェクト領域10の最大数を考慮して
定めても、あるいはヒープ領域の大きさに合わせて定め
ても、さらにはヒープ領域2内に存在するオブジェクト
領域10の数に合わせて動的に変化させても良い。
【0183】また、本実施の形態8では、ポインタ12
は参照テーブル17のエントリを指すために、配列の添
え字(整数値)を保持するとしたが、これはエントリの
配置アドレスを保持するようにしても同様の効果が得ら
れる。さらに、本実施の形態8では、ポインタ12で無
効な値を示すために参照テーブル17に専用の特別なエ
ントリを持つようにしたが、これは参照テーブル17は
有効なオブジェクト領域10を参照するエントリしか保
持しないようにし、代わりにポインタ12が特別な値、
例えば配列の添え字であれば負値であったり、配置アド
レスであれば0ないしNULLといった参照テーブル1
7のエントリを指定するのには不適切な値を保持するよ
うにしても、同様の効果が得られる。
【0184】さらに、本実施の形態8では、参照テーブ
ル17はヒープ領域2の外部に存在するとしたが、参照
テーブル17はポインタ12の保持する値から一意にア
クセスできれば良いので、ヒープ領域2内にオブジェク
ト領域10とは別途確保したり、あるいは決して開放さ
れることのないオブジェクト領域10の1つとして確保
することでも、同様の効果を得ることができる。同じ理
由で、参照テーブル17を1つの連続した表として構成
する代わりに、複数の副表から構成してもよく、さらに
はポインタ12の保持する値からオブジェクト領域10
へ対応づける任意の構造、例えば木構造などを採用して
も、同様の効果を得られる。
【0185】実施の形態9.この発明の実施の形態9
は、応用プログラムとガベージコレクション処理の動作
タイミングに関するものである。その基本構成は実施の
形態3と同一であるので説明を省略する。
【0186】図17は、本実施の形態9の動作を示すフ
ローチャートである。本実施の形態9におけるガベージ
コレクション処理(GC処理)S200は、大きくは次
の3つの段階、事前処理S201、繰り返される単位処
理S202、事後処理S203から構成され、まずガベ
ージコレクション処理のうち繰り返し処理S202に入
る前の準備として事前処理S201を行った後、GC稼
動可否フラグを検査し(S2001)、その値が真すな
わちガベージコレクション処理を継続して良い状況であ
れば(S2001のYes)、ガベージコレクション処
理の繰り返し処理S202を1単位処理分だけ実行し、
その後さらに繰り返し処理を継続する必要があれば(S
2002のNo)、GC稼動可否フラグが真の間(S2
001のYes)繰り返し処理S202を繰り返し、繰
り返し処理S202を行う必要がなくなるか(S200
2のYes)、GC稼動可否フラグが偽となりガベージ
コレクション処理を継続できない状況であれば(S20
01のNo)、ガベージコレクション処理のうち繰り返
し処理S202の後始末として事後処理S203を行
い、処理を終了する。
【0187】次に、手順S201、S202、S203
の詳細を示す。手順S201、S202、S203の具
体的処理内容は、元とするガベージコレクション処理に
よって異なるが、まず実施の形態3に示すガベージコレ
クション処理を元にした場合では、手順S201及び手
順S203の詳細は空の処理となり、手順S202の詳
細は、図8のS1401、S1402、S161、S1
41、S162、S1403、S1404の手続きとな
る。また、実施の形態4に示すガベージコレクション処
理を元にした場合では、手順S201の詳細は、図10
のS105、P141、P1201、P1501、P1
413、P1414の手続きとなり、手順S203の詳
細は、図10のS1401、S1402、S151、S
141、S162、S1403、S1404の手続きと
なり、手順S203の詳細は空の処理となる。なお、手
順S202に示す処理は、0回から最大で繰り返す必要
がなくなるまでの、任意回数の繰り返しが可能な処理で
なければならず、繰り返しを途中で止めた場合にメモリ
獲得手段3、メモリ開放手段4、ないしガベージコレク
ション手段5のいずれか、あるいは複数の手段で内部的
な不整合が発生することは許容されない。
【0188】次に、本実施の形態9の動作について図1
8を用いて説明する。図18は、本実施の形態9の動作
を示す解説図であり、応用プログラムは適切な周期T1
で周期的に動作し、GC稼動可否フラグは応用プログラ
ム開始と同期して真となり、その後T1より短い一定時
間T2の経過後に偽となるよう、周期的に変化するよう
制御する。また、ガベージコレクション処理S200
は、応用プログラムと同時に動作契機が与えられるが、
両者が同時に動作可能な場合は、応用プログラムのほう
がガベージコレクション処理より優先して動作するよ
う、制御する。
【0189】本実施の形態9では上記のように、ガベー
ジコレクション処理S200は、応用プログラムの動作
契機から時間T2の間で、かつ応用プログラムの動作が
中断しているか、または応用プログラムの動作が終了し
ているときしか動作できないように制御されるので、最
大でもT2/T1(<1)(正確には(T2+手順S2
02の実行時間)/T1)の比率までしかその処理を行
わないように制限できるので計算機システムの動作が安
定し、さらに次の応用プログラムの動作契機では必ずガ
ベージコレクションの処理が終了しているようにするの
で、応用プログラムの周期的動作を阻害せず、計算機シ
ステムの定応答性を向上できる。
【0190】なお、本実施の形態9において、手順S2
01、S202、S202のそれぞれの処理を実行中に
は、途中で応用プログラムの処理を優先させて応用プロ
グラムの処理を行うことができない場合でも、例えば実
施の形態3の説明で言及したように、それらの処理の間
ではガベージコレクション処理を休止させ応用プログラ
ムの動作ができるようにすれば、応用プログラム実行中
に一旦ガベージコレクション処理が動作しても、その中
断時間を短く抑えることができ、計算機システムの定応
答性が向上できる。
【0191】また、本実施の形態9ではガベージコレク
ション処理S200の動作契機を応用プログラムの動作
契機と同時に与えられるとしたが、これは周期T1で動
作するすべての応用プログラムの動作が終了してからガ
ベージコレクション処理S200への動作契機が与えら
れるようにしてもよく、この場合は、応用プログラムの
処理をより優先して行うことができ、応用プログラムの
動作の応答性をより向上させることができる。
【0192】実施の形態10.この発明の実施の形態1
0は、応用プログラムとガベージコレクション処理の動
作タイミングに関するものである。その基本構成は実施
の形態3と同一であるので説明を省略する。
【0193】図19は、本実施の形態10の動作を示す
フローチャートである。本実施の形態10におけるガベ
ージコレクション処理(GC処理)S210は、実施の
形態9同様、大きくは次の3つの段階、事前処理S20
1、繰り返される単位処理S202、事後処理S203
から構成され、まずガベージコレクション処理のうち繰
り返し処理S202に入る前の準備として事前処理S2
01を行った後、GC稼動可否カウンタを検査し(S2
101)、その値が0より大きくガベージコレクション
処理を継続して良い状況であれば(S2101のYe
s)、ガベージコレクション処理の繰り返し処理S20
2を1単位処理分だけ実行し、その後GC稼動可否カウ
ンタの値を1減じ(S2102)、さらに繰り返し処理
を継続する必要があれば(S2002のNo)、GC稼
動可否カウンタの値が0より大きい間(S2001のY
es)繰り返し処理S202を繰り返し、繰り返し処理
S202を行う必要がなくなるか(S2002のYe
s)、GC稼動可否カウンタの値が0以下となりガベー
ジコレクション処理を継続できない状況であれば(S2
001のNo)、ガベージコレクション処理のうち繰り
返し処理S202の後始末として事後処理S203を行
い、処理を終了する。
【0194】手順S201、S202、S203の詳細
は、実施の形態9と同じであるので、説明を省略する。
【0195】次に、本実施の形態10の動作について図
20を用いて説明する。図20は、本実施の形態10の
動作を示す解説図であり、応用プログラムは適切な周期
T1で周期的に動作し、GC稼動可否カウンタは応用プ
ログラム開始と同期して適切な一定値が加算される。な
お、GC稼動可否カウンタに加算する値は、応用プログ
ラムの処理が長引いた後に、ガベージコレクション処理
S210が行われても、応用プログラムの次の動作契機
までにはガベージコレクション処理S210が終わるよ
うな値とする。また、ガベージコレクション処理S21
0が、GC稼動可否カウンタの値が0以下になった(S
2101のNo)ために終了したのではなく、繰り返し
処理S202の繰り返しが必要なくなった(S2002
のYes)ために終了した場合は、GC稼動可否カウン
タの値は0より大きい値となるが、これは0に戻される
ことなく、次の契機で一定値を加算する。ただし、加算
後のGC稼動可否カウンタの値が大きすぎる場合は適切
に調整する。なお、ガベージコレクション処理S210
は、応用プログラムと同時に動作契機が与えられるが、
両者が同時に動作可能な場合は、応用プログラムのほう
がガベージコレクション処理S210より優先して動作
するよう、制御する。
【0196】本実施の形態10では上記のように、ガベ
ージコレクション処理S210は、応用プログラムのG
C稼動可否カウンタが0より大きい間で、かつ応用プロ
グラムの動作が中断しているか、または応用プログラム
の動作が終了しているときしか動作できないように制御
されるので、毎回のGC稼動可否カウンタの増加値を適
切に選ぶことにより、次の応用プログラムの動作契機ま
でにガベージコレクション処理S210の処理を終えさ
せることができ、実施の形態9同様、応用プログラムの
周期的動作を阻害せず、計算機システムの定応答性を向
上でき、さらに本実施の形態10では、実施の形態9よ
り、より周期毎にガベージコレクション処理S210へ
割当てる処理時間を一定に保つことができるので、応用
プログラムの動作が長引いた場合には、実施の形態9よ
り、よりガベージコレクション処理S210を長く動作
させることができるため、より多くの「ごみ」の回収が
でき、メモリ利用効率が向上する。
【0197】なお、本実施の形態10においては、実施
の形態9同様、手順S201、S202、S202のそ
れぞれの処理を実行中には、途中で応用プログラムの処
理を優先させて応用プログラムの処理を行うことができ
ない場合でも、例えば実施の形態3の説明で言及したよ
うに、それらの処理の間ではガベージコレクション処理
を休止させ応用プログラムの動作ができるようにすれ
ば、応用プログラム実行中に一旦ガベージコレクション
処理が動作しても、その中断時間を短く抑えることがで
き、計算機システムの定応答性が向上できる。
【0198】また、本実施の形態10ではガベージコレ
クション処理S210の動作契機を応用プログラムの動
作契機と同時に与えられるとしたが、これも実施の形態
9同様、これは周期T1で動作するすべての応用プログ
ラムの動作が終了してからガベージコレクション処理S
210への動作契機が与えられるようにしてもよく、こ
の場合、応用プログラムの処理をより優先して行うこと
ができ、応用プログラムの動作の応答性をより向上させ
ることができる。
【0199】さらに、本実施の形態10では、GC稼動
可否カウンタに整数値を用いたが、これは時刻を表す値
を用いて、手順S2102ではGC稼動可否カウンタに
対しS202の実行時間を減算するようにしてもよく、
この場合、ガベージコレクション処理S210に割当て
る時間をより厳密に制御できる。
【0200】実施の形態11.この発明の実施の形態1
1は、応用プログラムとガベージコレクション処理の動
作タイミングに関するものであり、実施の形態10を改
善したものである。その基本構成は実施の形態3と同一
であるので説明を省略する。
【0201】図21は、本実施の形態11の動作を示す
フローチャートである。本実施の形態11におけるガベ
ージコレクション処理(GC処理)S220は、実施の
形態10同様、大きくは次の3つの段階、事前処理S2
01、繰り返される単位処理S202、事後処理S20
3から構成され、まずガベージコレクション処理のうち
繰り返し処理S202に入る前の準備として事前処理S
201を行った後、現状の残利用可能領域13が十分得
られているかを調べ(S2201)、もし十分であれば
(S2201のYes)、次にGC稼動可否カウンタを
検査し(S2101)、その値が0より大きくガベージ
コレクション処理を継続して良い状況であれば(S21
01のYes)、ガベージコレクション処理の繰り返し
処理S202を1単位処理分だけ実行する。なお、手順
S2201における残利用可能領域13の量の判断で
は、応用プログラムの動作挙動から、周期的に行うガベ
ージコレクション処理S220で少なくとも確保してお
く必要がある量に基づき判断することとし、もし手順S
2201で現状の残利用可能領域13が十分得られてい
なければ、手順S2101は割愛して速やかにガベージ
コレクション処理の繰り返し処理S202に移る。その
後は、まずGC稼動可否カウンタの値を1減じ(S21
02)、ついでさらに繰り返し処理を継続する必要があ
れば(S2002のNo)、残利用可能領域13が十分
回収できていないか(S2201のNo)、あるいはG
C稼動可否カウンタが0より大きい間(S2001のY
es)、繰り返し処理S202を繰り返し、繰り返し処
理S202を行う必要がなくなるか(S2002のYe
s)、残利用可能領域13が十分得られ(S2201の
Yes)、かつGC稼動可否カウンタの値が0以下とな
りガベージコレクション処理を継続できない状況であれ
ば(S2001のNo)、ガベージコレクション処理の
うち繰り返し処理S202の後始末として事後処理S2
03を行い、処理を終了する。
【0202】手順S201、S202、S203の詳細
は、実施の形態9及び実施の形態10と同じであるの
で、説明を省略する。
【0203】次に、本実施の形態11の動作について図
22を用いて説明する。図22は、本実施の形態11の
動作を示す解説図であり、応用プログラムは適切な周期
T1で周期的に動作し、GC稼動可否カウンタは応用プ
ログラム開始と同期して適切な一定値が加算される。な
お、GC稼動可否カウンタに加算する値は、応用プログ
ラムの処理が長引いた後に、ガベージコレクション処理
S220が行われても、応用プログラムの次の動作契機
までにはガベージコレクション処理S220が終わるよ
うな値とする。また、ガベージコレクションS210の
処理が、GC稼動可否カウンタの値が0以下になった
(S2101のNo)ために終了したのではなく、繰り
返し処理S202の繰り返しが必要なくなった(S20
02のYes)ために終了した場合は、GC稼動可否カ
ウンタの値は0より大きい値となるが、これは0に戻さ
れることなく、次の契機で一定値を加算する。ただし、
加算後のGC稼動可否カウンタの値が大きすぎる場合は
適切に調整する。同様に、ガベージコレクション処理S
220が、十分な残利用可能領域13をなかなか回収で
きずに終了した場合は、GC稼動可否カウンタの値が0
より小さい値となることがあるが、これも0に戻される
ことなく次の契機で一定値を加算する。ただし、この場
合も加算後のGC稼動可否カウンタの値が小さすぎる場
合は適切に調整する。なお、ガベージコレクション処理
S220は、応用プログラムと同時に動作契機が与えら
れるが、両者が同時に動作可能な場合は、応用プログラ
ムのほうがガベージコレクション処理S220より優先
して動作するよう、制御する。
【0204】本実施の形態11では上記のように、ガベ
ージコレクション処理S220は、応用プログラムの動
作が中断しているか、または応用プログラムの動作が終
了しているときで、かつ最低量の残利用可能領域13を
回収でき、さらに応用プログラムのGC稼動可否カウン
タが0より大きい間でしか動作できないように制御され
るので、毎回のGC稼動可否カウンタの増加値を適切に
選ぶことにより、次の応用プログラムの動作契機までに
ガベージコレクション処理S220の処理を終えさせる
ことができ、実施の形態9及び実施の形態10同様、応
用プログラムの周期的動作を阻害せず、計算機システム
の定応答性を向上できる。さらに、本実施の形態11で
は、実施の形態10同様、実施の形態9より、より周期
毎にガベージコレクション処理S220へ割当てる処理
時間を一定に保つことができるので、応用プログラムの
動作が長引いた場合には、実施の形態9より、よりガベ
ージコレクション処理S220を長く動作させることが
できるため、より多くの「ごみ」の回収ができ、メモリ
利用効率が向上する。加えて本実施の形態11では、実
施の形態10と比べ、毎回の周期で少なくとも一定量の
残利用可能領域13を確保するよう動作するので、応用
プログラム動作中での残利用可能領域13の不足による
メモリ獲得手段3のオブジェクト領域10の確保の失敗
が発生しにくくなり、応用プログラムの動作が安定し、
かつガベージコレクション処理S220の処理が長引い
た場合は次回の処理を短くするよう動作するので、計算
機システム全体の動作も安定する。
【0205】なお、本実施の形態11においては、実施
の形態9及び実施の形態10同様、手順S201、S2
02、S202のそれぞれの処理を実行中には、途中で
応用プログラムの処理を優先させて応用プログラムの処
理を行うことができない場合でも、例えば実施の形態3
の説明で言及したように、それらの処理の間ではガベー
ジコレクション処理を休止させ応用プログラムの動作が
できるようにすれば、応用プログラム実行中に一旦ガベ
ージコレクション処理が動作しても、その中断時間を短
く抑えることができ、計算機システムの定応答性が向上
できる。
【0206】また、本実施の形態11ではガベージコレ
クション処理S220の動作契機を応用プログラムの動
作契機と同時に与えられるとしたが、これも実施の形態
9及び実施の形態10同様、これは周期T1で動作する
すべての応用プログラムの動作が終了してからガベージ
コレクション処理S220への動作契機が与えられるよ
うにしてもよく、この場合、応用プログラムの処理をよ
り優先して行うことができ、応用プログラムの動作の応
答性をより向上させることができる。
【0207】さらに、本実施の形態11では、GC稼動
可否カウンタに整数値を用いたが、これは実施の形態1
0同様、時刻を表す値を用いて、手順S2102ではG
C稼動可否カウンタに対しS202の実行時間を減算す
るようにしてもよく、この場合、ガベージコレクション
処理S220に割当てる時間をより厳密に制御できる。
【0208】実施の形態12.この発明の実施の形態1
2に係る動的メモリ管理機構について図面を参照しなが
ら説明する。図23は、この発明の実施の形態12に係
る動的メモリ管理機構の構成を示すブロック図である。
図23において、動的メモリ管理機構1、ヒープ領域
2、ガベージコレクション手段5、オブジェクト領域1
0、ポインタ12、残利用可能領域13、既獲得済み領
域14は図7の実施の形態3と同じであるので説明を省
略する。残利用可能領域13内の利用可能なメモリ領域
はフリーリスト18により管理され、オブジェクト領域
10は、メモリ獲得手段3によりフリーリスト18内の
適切な領域が割当てられることで獲得され、獲得された
オブジェクト領域10は既獲得済み領域14の一部を構
成するようになる。また、オブジェクト領域10はメモ
リ開放手段4によりフリーリスト18に戻されることで
開放され、その領域は再利用可能となる。
【0209】次に、本実施の形態12の動作について説
明する。図24は、本実施の形態12におけるガベージ
コレクション処理(GC処理)の動作を示す全体のフロ
ーチャートである。本実施の形態12におけるガベージ
コレクション処理は、その起動契機により異なる動作を
し、起動契機が残利用可能領域13の不足により応用プ
ログラム稼働中にメモリ獲得手段3が応用プログラムか
ら要求された量のオブジェクト領域10を獲得できなか
ったことによる場合は(S2301の図中左分岐)、ま
ず既獲得済み領域14の一部に対し非コピー式の部分ガ
ベージコレクション処理を行い、残利用可能領域13内
のフリーリスト18の拡充を試み(S231)、必要な
オブジェクト領域10が確保できるようになれば(S2
302のYes)処理を終了し、手順S231だけでは
必要なオブジェクト領域10が確保できなければ(S2
302のNo)、実施の形態7(図14)における手順
1612と同様な方法で、必要なオブジェクト領域10
が確保できるように、コピーにより有効なオブジェクト
領域10の移動を行い、フリーリスト18にある複数の
利用可能なメモリ領域を単一のメモリ領域にまとめる
(S232)。一方、本ガベージコレクション処理S2
30の起動契機が、実施の形態9に示されるような定期
動作であった場合は(S2301の図中右分岐)、例え
ば第5の従来例に示したストップ−コピー方式のガベー
ジコレクション処理、あるいは実施の形態3ないし実施
の形態9に示したガベージコレクション処理などの、コ
ピー式のガベージコレクション処理を行い残利用可能領
域13を拡充する(S233)。
【0210】次に、手順S231に示した、既獲得済み
領域14の一部に対する非コピー式の部分ガベージコレ
クション処理(非コピー式部分GC処理)の詳細を示
す。図25は、本実施の形態9におけるガベージコレク
ション処理の動作を示す非コピー式の部分ガベージコレ
クション処理のフローチャートである。本動作では、ま
ず既獲得済み領域14のうち適切な大きさをFROM領
域16と定め(S2311)、FROM領域16内にあ
るすべてのオブジェクト領域を一旦フリーリスト18に
つなぐ(S2312)。次に、大きく以下の3つの段階
を踏み、FROM領域16内の「生きている」オブジェ
クト領域10を抽出し、フリーリスト18からはずす。
次に、計算機のCPUレジスタ、プログラムが静的に配
置したメモリ領域、あるいはスタック内の変数としてヒ
ープ領域2の外部に存在するすべてのポインタ12につ
いて、それらのポインタ12から直接参照されるFRO
M領域16内のオブジェクト領域10を探索し、未検出
のオブジェクト領域10があれば、同オブジェクト領域
10をフリーリスト18から抜き有効オブジェクト領域
リストへ追加する(S235)。次に、既獲得済み領域
14のうちFROM領域16以外にあるすべてのオブジ
ェクト領域10を探索し、それらのオブジェクト領域1
0から直接参照されるFROM領域16内のオブジェク
ト領域10についても、未検出のオブジェクト領域10
であれば、同オブジェクト領域10をフリーリスト18
から抜き有効オブジェクト領域リストへ追加する(S2
36)。最後に、有効オブジェクト領域リストを探索
し、有効オブジェクト領域リストにあるオブジェクト領
域10から参照されるFROM領域16内のオブジェク
ト領域10についても、未検出であればフリーリスト1
8から抜き有効オブジェクト領域リストへ追加し(S2
37)、処理を終了する。手順S235、S236、S
237により、ヒープ領域外のポインタ12からと既獲
得済み領域14のうちFROM領域16以外に存在する
オブジェクト領域10から直接または間接に参照できる
すべてのオブジェクト領域10はフリーリスト18から
抜かれ有効オブジェクト領域リストに登録されたので、
本段階でFROM領域16に存在し、かつ有効オブジェ
クト領域リストに登録されず、まだフリーリスト18に
つながっているオブジェクト領域10は「ごみ」とみな
すことができる。
【0211】次に、手順S235、手順S236、手順
S237の詳細を示す。
【0212】手順S235では、まずヒープ領域2外に
ある適切なポインタ12の1つを選択し(P141
1)、そのポインタ12が有効でFROM領域16内に
ある未検出のオブジェクト領域10を参照していれば
(S1621のYes)、ポインタ12が参照するオブ
ジェクト領域10をフリーリスト18から抜き有効オブ
ジェクト領域リストに追加登録し(S2351)、本手
順をヒープ領域2の外にあるすべてのポインタ12につ
いて繰り返す(P1413のYes、P1414)。
【0213】手順S236では、既獲得済み領域14の
うちFROM領域16以外にオブジェクト領域10があ
れば(S1411のYes)、まず該当するオブジェク
ト領域10を1つ選択し(S1412)、選択したオブ
ジェクト領域10が内部にポインタ12を含めば(P1
313のYes)、まず選択したオブジェクト領域10
に含まれるポインタ12の1つを選び(P1314)、
その値が有効でFROM領域16内にある未検出のオブ
ジェクト領域10を参照していれば(S1621のYe
s)、参照先のオブジェクト領域10をフリーリスト1
8から抜き有効オブジェクト領域リストに追加登録し
(S2351)、本手順を選択したオブジェクト領域1
0の内部に含まれるすべてのポインタ12に繰り返し行
い(P1315のNo)、さらに既獲得済み領域14の
うちFROM領域16以外にあるオブジェクト領域10
のすべてについて上記手順を繰り返す(S1413のN
o)。
【0214】手順S237では、有効オブジェクト領域
リストに未処理のオブジェクト領域10があれば(S1
641のYes)、有効オブジェクト領域リストからま
ず該当するオブジェクト領域10を1つ選択し(S16
42)、選択したオブジェクト領域10が内部にポイン
タ12を含めば(P1313のYes)、まず選択した
オブジェクト領域10に含まれるポインタ12の1つを
選び(P1314)、その値が有効でFROM領域16
内にある未検出のオブジェクト領域10を参照していれ
ば(S1621のYes)、参照先のオブジェクト領域
10をフリーリスト18から抜き有効オブジェクト領域
リストに追加登録し(S2351)、本手順を選択した
オブジェクト領域10の内部に含まれるすべてのポイン
タ12に繰り返し行い(P1315のNo)、さらに有
効オブジェクト領域リストに登録されているオブジェク
ト領域10のすべてについて上記手順を繰り返す(S1
643のNo)。
【0215】本実施の形態12は上記のように、ガベー
ジコレクション処理S230の起動契機に応じて、その
処理内容を変更するようにしたので、ガベージコレクシ
ョン処理S230の起動契機が、残利用可能領域13の
不足により応用プログラム稼働中にメモリ獲得手段3が
応用プログラムから要求された量のオブジェクト領域1
0を獲得できなかったことによる場合では、応用プログ
ラムの中断時間ができるだけ短くなるように動作し、一
方、その起動契機が周期的に予定されている定期動作で
は、残利用可能領域13内の利用可能なメモリ領域をで
きるだけ大きく連続した領域となるようにし、応用プロ
グラムの中断が起こりにくくなるように動作し、これに
より応用プログラムの動作の応答性を向上することがで
きる。
【0216】なお、本実施の形態12では、応用プログ
ラム稼働中の残利用可能領域13不足時は、まず、第3
の従来例に示したマーク−スイープ方式に準じた非コピ
ー式部分ガベージコレクション処理S231を行い、つ
いで手順S232でさらにフリーリスト18内の利用可
能なメモリ領域を単一の領域にまとめるようにしたが、
必要としているオブジェクト領域を獲得するに足る残利
用可能領域13を早く確保できる方式であれば、どのよ
うなガベージコレクション方式であっても代えることが
でき、例えば手順S231に代えマーク−スイープ方
式、あるいは類する他の方式を既獲得済み領域14に対
し部分的あるいは全体に利用することでも同じ効果を得
ることが出来、さらに手順S231と手順S232をま
とめ、例えば実施の形態7(図13、図14)における
部分コンパクト処理S161や、あるいは第4の従来例
に示したマーク−コンパクト方式のガベージコレクショ
ン処理に代えることでも、同じ効果を得ることができ
る。同様に、本実施の形態12の定期動作時の処理は、
できるだけ多くの残利用可能領域13を効率よく集めら
れる方式であれば、どのようなガベージコレクション方
式であっても代えることができる。さらに本実施の形態
12に対し、第1ないし第2の従来例、または実施の形
態1ないし実施の形態2に示したような、参照カウンタ
方式のガベージコレクション処理を併用することで、応
用プログラム稼働中の残利用可能領域13不足の発生
を、より抑制することができる。
【0217】実施の形態13.この発明の実施の形態1
3は、ガベージコレクション処理が、実施の形態12と
は別の条件によって、その起動契機の状況に応じて異な
る動作をするものである。その基本構成は実施の形態1
2の構成と同一であるので説明を省略する。
【0218】図26は、本実施の形態13の動作を示す
フローチャートである。本実施の形態13におけるガベ
ージコレクション処理(GC処理)S240は、その起
動契機の状態により異なる動作をし、前回ガベージコレ
クション処理が行われてから、今回の起動までにメモリ
獲得手段3によって獲得されたオブジェクト領域10の
数が少なかった場合は(S2401の図中左分岐)、第
5の従来例に示したストップ−コピー式のガベージコレ
クション処理を行い(S241)、一方、今回の起動ま
でにメモリ獲得手段3によって獲得されたオブジェクト
領域10の数が多かった場合は(S2402の図中右分
岐)、第3の従来例に示したマーク−スイープ方式のガ
ベージコレクション処理を行う(S242)。
【0219】第3および第5の従来例で示したように、
ストップ−コピー方式ではマーク−スイープ方式の問題
であるフラグメンテーション現象の発生を避けることが
できるが、その処理内にオブジェクト領域のコピー動作
が入るため、同じ数のオブジェクト領域を扱う場合マー
ク−スイープ方式より処理時間が長くなるという問題点
がある。しかし、本実施の形態13は上記のように、ガ
ベージコレクション処理S240の起動契機における状
態に応じて両者を使い分けるようにしたので、ガベージ
コレクション処理に要する処理時間を、前回ガベージコ
レクション処理後に新たに獲得されたオブジェクト領域
10の数に関わらず、できるだけ一定に保ちつつ、適宜
ストップ−コピー方式を行うことでフラグメンテーショ
ン現象発生を回避することができ、計算機システムの動
作を安定させることができる。
【0220】なお、本実施の形態13では、前回ガベー
ジコレクション処理後に新たに獲得されたオブジェクト
領域10の数によって、どちらのガベージコレクション
方式を用いるかの判断を行っているが、本判断は固定的
な閾値による判断ではなく、例えば過去の履歴を元に適
用的に閾値を定め判断するようにしても同様の効果を得
られる。また、前回ガベージコレクション処理後に新た
に獲得されたオブジェクト領域10に関して、そのの数
だけでなく、その総量も判断に用いても良く、あるいは
前回ガベージコレクション処理後に新たに獲得されたオ
ブジェクト領域10に関してではなく、ガベージコレク
ション処理起動契機時点で「生きてきる」とみなされる
オブジェクト領域10に関する指標、さらには他の指標
を用いても本実施の形態13と同様の効果を得ることが
できる。
【0221】また、本実施の形態13では、マーク−ス
イープ方式とストップ−コピー方式を併用するようにし
たが、これらの方式は両者をインクリメンタル化した方
式に代えてよく、さらには他の既存技術、ないしこの発
明にかかる他の実施の形態に挙げた他の方式で代えても
良く、さらに3種ないしそれ以上の方式を併用をしても
よい。
【0222】実施の形態14.この発明の実施の形態1
4は、ガベージコレクション処理が、実施の形態12及
び実施の形態13とは別の条件によって、その起動契機
の状況に応じて異なる動作をするものである。その基本
構成は実施の形態12の構成と同一であるので説明を省
略する。
【0223】図27は、本実施の形態14の動作を示す
フローチャートである。本実施の形態14におけるガベ
ージコレクション処理(GC処理)S250は、計算機
システムの立ち上げ段階であった場合は、残利用可能領
域13の不足により応用プログラム稼働中にメモリ獲得
手段3が応用プログラムから要求された量のオブジェク
ト領域10を獲得できなかったことによる場合のみ起動
され、計算機システムの定常段階では、実施の形態9に
示したように一定の周期で定期的に起動される。このた
め本実施の形態14のガベージコレクション処理S25
0は、その起動時が計算機システムの立ち上げ段階であ
った場合は(S2501の図中左分岐)、まず第3の従
来例として示したマーク−スイープ方式のガベージコレ
クション処理を行い(S251)、必要なオブジェクト
領域10が確保できるようになれば(S2302のYe
s)処理を終了し、手順S251だけでは必要なオブジ
ェクト領域10が確保できなければ(S2302のN
o)、実施の形態7(図14)における手順1612と
同様な方法で、必要なオブジェクト領域10が確保でき
るように、コピーにより有効なオブジェクト領域10の
移動を行い、フリーリスト18にある複数の利用可能な
メモリ領域を単一のメモリ領域にまとめる(S23
2)。一方、本ガベージコレクション処理S250の起
動時が計算機システムの定常状態であった場合は(S2
501の図中右分岐)、例えば実施の形態3ないし実施
の形態9に示した本発明にかかるガベージコレクション
処理などにより、既獲得済み領域14の一部に対しコピ
ー式のガベージコレクション処理を行い残利用可能領域
13を拡充する(S253)。
【0224】本実施の形態14は上記のように、ガベー
ジコレクション処理S230の起動契機における計算機
システムの稼動状況に応じて処理内容を変更するように
したので、計算機システムの立ち上げ段階では、立ち上
げに要する処理時間を短くするようガベージコレクショ
ン処理を行い、計算機システムの定常段階では、応用プ
ログラムの動作の応答性が良いようにガベージコレクシ
ョン処理を行うことができる。
【0225】なお、本実施の形態14では、計算機シス
テムの立ち上げ段階では、まず第3の従来例に示したマ
ーク−スイープ方式のガベージコレクション処理S25
1を行い、ついで手順S252でさらにフリーリスト1
8内の利用可能なメモリ領域を単一の領域にまとめるよ
うにしたが、本手順は、計算機システムの立ち上げ段階
の全体の処理時間を短くできるような方式であれば、ど
のような方式に代えても良く、同様に計算機システムの
定常段階では、応用プログラムの動作の応答性を向上で
きる方式であれば、どのような方式に代えても良い。
【0226】実施の形態15.この発明の実施の形態1
5は、実施の形態12と実施の形態14を合成し、改良
したものであり、ガベージコレクション処理が、より複
合した条件によって、その起動契機の状況に応じた異な
る動作をするものである。その基本構成は実施の形態1
2の構成と同一であるので説明を省略する。
【0227】図28は、本実施の形態15の動作を示す
フローチャートである。本実施の形態15におけるガベ
ージコレクション処理(GC処理)S260は、残利用
可能領域13の不足により応用プログラム稼働中にメモ
リ獲得手段3が応用プログラムから要求された量のオブ
ジェクト領域10を獲得できなかったことによる場合に
起動され、また計算機システムの定常段階においては、
実施の形態9に示したように一定の周期で定期的に起動
される。このため本実施の形態15のガベージコレクシ
ョン処理S250は、その起動時が計算機システムの立
ち上げ段階であった場合は(S2501の図中下分
岐)、既獲得済み領域14全体を処理対象として(S2
601)、まず対象領域に対し第3の従来例として示し
たマーク−スイープ式、あるいは実施の形態12(図2
5)の手順S231に準じた非コピー式のガベージコレ
クション処理を行い(S261)、必要なオブジェクト
領域10が確保できるようになれば(S2302のYe
s)処理を終了し、手順S261だけでは必要なオブジ
ェクト領域10が確保できなければ(S2302のN
o)、実施の形態7(図14)における手順1612と
同様な方法で、必要なオブジェクト領域10が確保でき
るように、コピーにより有効なオブジェクト領域10の
移動を行い、フリーリスト18にある複数の利用可能な
メモリ領域を単一のメモリ領域にまとめる(S23
2)。一方、本ガベージコレクション処理S260の起
動時が計算機システムの定常段階であった場合は(S2
501の図中右分岐)、次にガベージコレクション処理
の起動契機について判断を行い(S2301)、もし起
動契機が残利用可能領域13の不足により応用プログラ
ム稼働中にメモリ獲得手段3が応用プログラムから要求
された量のオブジェクト領域10を獲得できなかったこ
とによる場合は(S2301の図中下分岐)、既獲得済
み領域14の一部を処理対象として(S2602)、手
順261を行い、必要なオブジェクト領域10が確保で
きるようになれば処理を終えるが(S2302のYe
s)、手順S261だけでは必要なオブジェクト領域1
0が確保できなければ(S2302のNo)、さらに手
順S232を行う。また、ガベージコレクション処理S
260の起動時が計算機システムの定常段階であって
(S2501の図中右分岐)、ガベージコレクション処
理の起動契機が実施の形態9に示されるような定期動作
であった場合は(S2301の図中右分岐)、まず例え
ば実施の形態3ないし実施の形態9に示したガベージコ
レクション処理などにより、既獲得済み領域の一部に対
しコピー式のガベージコレクション処理を行い残利用可
能領域を拡充し(S253)、定期的な動作で確保すべ
き残利用可能領域13を得られれば(S2603のYe
s)処理を終了し、未だ残利用可能領域13が不足する
場合は(S2603のNo)、さらに対象領域を広げ既
獲得済み領域14全体に対し再びコピー式のガベージコ
レクション処理を行い残利用可能領域13を拡充する
(S264)。
【0228】本実施の形態15は上記のように、ガベー
ジコレクション処理S260の起動契機における計算機
システムの稼動状況と、ガベージコレクション処理S2
60の起動契機に応じて処理内容を変更するようにした
ので、実施の形態14同様、計算機システムの立ち上げ
段階では、立ち上げに要する処理時間を短くすることが
でき、一方、計算機システムの定常段階においては、実
施の形態12同様、その起動契機が残利用可能領域13
の不足により応用プログラム稼働中にメモリ獲得手段3
が応用プログラムから要求された量のオブジェクト領域
10を獲得できなかった場合では、応用プログラムの中
断時間ができるだけ短くなるように動作し、さらに起動
契機が定常段階において周期的に予定されている定期動
作では、処ガベージコレクション処理の負荷を抑えつ
つ、残利用可能領域13内の利用可能なメモリ領域をで
きるだけ大きく連続した領域となるようにし、応用プロ
グラムの中断が起こりにくくなるように動作し、これに
より応用プログラムの動作の応答性を向上することがで
きる。
【0229】なお、本実施の形態15では、計算機シス
テムの立ち上げ段階では、まず第3の従来例に示したマ
ーク−スイープ方式のガベージコレクション処理S25
1を行い、ついで手順S252でさらにフリーリスト1
8内の利用可能なメモリ領域を単一の領域にまとめるよ
うにしたが、本手順は、計算機システムの立ち上げ段階
の全体の処理時間を短くできるような方式であれば、ど
のような方式に代えても良く、同様に計算機システムの
定常段階では、応用プログラムの動作の応答性を向上で
きる方式であれば、どのような方式に代えても良い。ま
た本実施の形態15に対し、第1ないし第2の従来例、
または実施の形態1ないし実施の形態2に示したよう
な、参照カウンタ方式のガベージコレクション処理を併
用することで、応用プログラム稼働中の残利用可能領域
13不足の発生を、より抑制することができる。
【0230】さらに、実施の形態12〜実施の形態15
において、その判断条件を変更ないし追加し、また条件
に応じて実行するガベージコレクション方式も変更ない
し追加することで、ガベージコレクション処理の契機と
なった理由、プログラムの動作状況、動的メモリ管理機
構1の内部状態、システムの稼動状況、その他のシステ
ム状態に応じて、異なる動作特性のガベージコレクショ
ン方式を適宜使い分けるガベージコレクション処理へ容
易に展開でき、これにより計算機システムや応用プログ
ラムの動作の状況に応じてガベージコレクション処理に
要求される動作特性を適宜変化させ、最適な動作特性を
実現し、計算機システムの性能を向上させることができ
る。
【0231】実施の形態16.この発明の実施の形態1
6は、応用プログラムとガベージコレクション処理の動
作タイミングに関するものである。その基本構成は実施
の形態3の構成と同一であるので説明を省略する。
【0232】図29は、本実施の形態16の動作を示す
フローチャートである。本実施の形態16におけるガベ
ージコレクション処理(GC処理)S301は、実施の
形態9と同様に一定の周期で定期的に起動され動作する
ものである。本実施の形態16では、応用プログラムが
そのプログラム中で明示的にガベージコレクション処理
の実行を指示すると(S300)、応用プログラムの処
理の延長上でガベージコレクション処理を行わずに、単
に定期的に実行されるガベージコレクション処理S30
1の終了を待ち合わせ(S3001)、ガベージコレク
ション処理S301の処理が行われ待ち合わせが解除さ
れると、その処理を終了する。一方、ガベージコレクシ
ョン処理S301は、周期的に起動すると、まず「ご
み」の回収再利用のため処理S302として、例えば第
5の従来例に示したストップ−コピー方式のガベージコ
レクション処理であったり、あるいは実施の形態9に示
したようなより高度なガベージコレクション処理を実行
し、ついで処理S302の終了を待っている1ないし複
数の応用プログラムに対し、その待ち合わせを解除する
(S3011)。
【0233】次に、本実施の形態16の動作について図
30を用いて説明する。図30は、本実施の形態16の
動作を示す解説図であり、本実施の形態16では、実施
の形態9と同様に、一定の周期で応用プログラムおよび
ガベージコレクション処理(GC処理)S301が時間
間隔T1で定期的に動作している。また、本実施の形態
16では、応用プログラムはA、B、Cの3種類が存在
し、それらの処理優先度はA>B>Cの順であるため、
同じタイミングで起動されているが基本的にはA、B、
Cの順でその動作が始まり、またAが動作している間は
B及びCは動作できず、Bが動作している間はCが動作
できないよう制御される。ガベージコレクション処理S
301は、A、B、Cのいずれの応用プログラムよりも
処理優先度が低いため、原則としてA、B、Cのいずれ
かの応用プログラムが動作している間は動作できないよ
う制御される。
【0234】時刻t1は応用プログラムA、B、C及び
ガベージコレクション処理S301の起動契機であり、
処理優先度に従い、まず応用プログラムAが時刻t1〜
t2の間動作し、ついで応用プログラムAの動作終了
後、応用プログラムBが時刻t2から動作を開始する。
しかし、応用プログラムBは時刻t3の時点で、そのプ
ログラムの処理の一部として明示的にガベージコレクシ
ョン処理の実行を指示する(S300)と、ガベージコ
レクション処理S301の終了の待ち合わせに入り(S
3001)、応用プログラムCが実行可能となりその実
行が始まる。応用プログラムCは時刻t4の時点でその
処理を終了し、その後ガベージコレクション処理S30
1の処理に移り、時刻t5の時点でガベージコレクショ
ン処理S301が終了すると、手順S3011により停
止していた応用プログラムBの待ち合わせが解除され、
応用プログラムBはその処理を再開、時刻t6の時点で
その処理を終了する。
【0235】本実施の形態16は上記のように、周期的
にガベージコレクション処理が動作する計算機システム
において、処理優先度の高い応用プログラムが明示的に
ガベージコレクション処理の実行を指示した場合に、そ
の処理優先度の延長上でガベージコレクション処理を進
めること無く、他の応用プログラムの動作を優先して行
うよう動作するので、応用プログラムの動作の応答性が
向上する。
【0236】実施の形態17.この発明の実施の形態1
7は、応用プログラムとガベージコレクション処理の動
作タイミングに関するものである。その基本構成は実施
の形態3の構成と同一であるので説明を省略する。
【0237】図31は、本実施の形態17の動作を示す
フローチャートである。本実施の形態17におけるガベ
ージコレクション処理(GC処理)S301は、実施の
形態16のガベージコレクション処理と同一であり、実
施の形態9と同様に一定の周期で定期的に起動され動作
するものである。本実施の形態17では、応用プログラ
ムがそのプログラム中でオブジェクト領域10を獲得し
ようとすると(S310)、まず残利用可能領域13か
ら必要なオブジェクト領域10を確保できるか検査し
(S3101)、もし確保可能であれば(S3101の
Yes)、速やかにメモリ獲得手段3を用いてオブジェ
クト領域10を確保し(S3102)処理を終えるが、
一方もし確保できなければ(S3101のNo)、応用
プログラムの処理の延長上でガベージコレクション処理
を行わずに、定期的に実行されるガベージコレクション
処理S301の終了を待ち合わせ(S3001)、ガベ
ージコレクション処理S301の処理が行われ待ち合わ
せが解除されると、再度必要なオブジェクト領域10が
確保できるかの検査(S3101)に戻り、必要なオブ
ジェクト領域10が確保できるまで手順S3101、S
3001を繰り返す。一方、ガベージコレクション処理
S301は、実施の形態16における動作と同一であ
り、周期的に起動すると、まず「ごみ」の回収再利用の
ため処理S302として、例えば第5の従来例に示した
ストップ−コピー方式のガベージコレクション処理であ
ったり、あるいは実施の形態9に示したようなより高度
なガベージコレクション処理を実行し、ついで処理S3
02の終了を待っている1ないし複数の応用プログラム
に対し、その待ち合わせを解除する(S3011)。
【0238】次に、本実施の形態17の動作について図
32を用いて説明する。図32は、本実施の形態17の
動作を示す解説図であり、本実施の形態17では、実施
の形態16と同様、一定の周期で応用プログラムおよび
ガベージコレクション処理(GC処理)S301が時間
間隔T1で定期的に動作している。また、実施の形態1
6と同じく、応用プログラムはA、B、Cの3種類が存
在し、それらの処理優先度はA>B>Cの順であるた
め、同じタイミングで起動されているが基本的にはA、
B、Cの順でその動作が始まり、またAが動作している
間はB及びCは動作できず、Bが動作している間はCが
動作できないよう制御される。ガベージコレクション処
理S301は、A、B、Cのいずれの応用プログラムよ
りも処理優先度が低いため、原則としてA、B、Cのい
ずれかの応用プログラムが動作している間は動作できな
いよう制御される。
【0239】時刻t1は応用プログラムA、B、C及び
ガベージコレクション処理S301の起動契機であり、
処理優先度に従い、まず応用プログラムAが時刻t1〜
t2の間動作し、ついで応用プログラムAの動作終了
後、応用プログラムBが時刻t2から動作を開始する。
しかし、応用プログラムBは時刻t3の時点で、そのプ
ログラムの処理としてオブジェクト領域10の獲得S3
10を行おうと、残利用可能領域13の不足(S310
1のNo)からガベージコレクション処理S301の終
了の待ち合わせに入り(S3001)、応用プログラム
Cが実行可能となりその実行が始まる。さらに、応用プ
ログラムCも時刻t4の時点で、そのプログラムの処理
としてオブジェクト領域10の獲得S310を行おう
と、残利用可能領域13の不足(S3101のNo)か
らガベージコレクション処理S301の終了の待ち合わ
せに入る(S3001)ため、その後ガベージコレクシ
ョン処理S301の処理に移り、時刻t5の時点でガベ
ージコレクション処理S301の処理が終了すると、手
順S3011により停止していた応用プログラムB及び
応用プログラムCの待ち合わせが解除され、応用プログ
ラムB、Cは共にその処理を再開するが、応用プログラ
ムBのほうが処理優先度が高いため、まず応用プログラ
ムBが動作し時刻t6の時点でその処理を終了、続いて
応用プログラムCが動作し時刻t7の時点でその処理を
終了する。
【0240】本実施の形態17は上記のように、周期的
にガベージコレクション処理が動作する計算機システム
において、残利用可能領域13の不足から応用プログラ
ムの動作がガベージコレクション処理の実行を待つ必要
がある場合に、その処理優先度の延長上でガベージコレ
クション処理を進めること無く、他の応用プログラムの
動作を優先して行うよう動作するので、応用プログラム
の動作の応答性が向上し、またガベージコレクション処
理は一括して動作するのでその処理効率を高めることが
できる。
【0241】実施の形態18.この発明の実施の形態1
8は、応用プログラムとガベージコレクション処理の動
作タイミングに関するものである。その基本構成は実施
の形態3の構成と同一であるので説明を省略する。
【0242】図33は、本実施の形態18の動作を示す
フローチャートである。本実施の形態18におけるガベ
ージコレクション処理(GC処理)S321は、実施の
形態9と同様に一定の周期で定期的に起動され動作する
ものである。本実施の形態18では、応用プログラムが
そのプログラム中でオブジェクト領域10を獲得しよう
とした場合は(S320)、まず残利用可能領域13か
ら必要なオブジェクト領域10を確保できるか検査し
(S3101)、もし確保可能であれば(S3101の
Yes)、速やかにメモリ獲得手段3を用いてオブジェ
クト領域10を確保し(S3102)処理を終えるが、
一方もし確保できなければ(S3101のNo)、応用
プログラムの処理の延長上でガベージコレクション処理
を行わずに、GC処理待ちリスト19へ自プログラムが
必要とするオブジェクト領域10の要求量と、他プログ
ラムから自プログラムを区別するための、例えばプロセ
スIDなどの識別子を合わせ追加登録し(S320
1)、その後定期的に実行されるガベージコレクション
処理S301からの待ち合わせ解除を待ち(S320
2)、待ち合わせが解除されると、再度必要なオブジェ
クト領域10が確保できるかの検査(S3101)に戻
り、必要なオブジェクト領域10が確保できるまで手順
S3101、S3201、S3202を繰り返す。ま
た、応用プログラムがそのプログラム中で明示的にガベ
ージコレクション処理の実行を指示した場合は(S30
0)、実施の形態16と同じく、応用プログラムの処理
の延長上でガベージコレクション処理を行わずに、単に
定期的に実行されるガベージコレクション処理S301
の終了を待ち合わせ(S3001)、ガベージコレクシ
ョン処理S301の処理が行われ待ち合わせが解除され
ると、その処理を終了する。
【0243】一方、ガベージコレクション処理(GC処
理)S321は、実施の形態9に示しされるガベージコ
レクション処理S200と同様に、大きく次の3つの段
階、事前処理S201、繰り返される単位処理S20
2、事後処理S203から構成され、周期的な起動毎
に、まずガベージコレクション処理のうち繰り返し処理
S202に入る前の準備として事前処理S201を行
い、ついでガベージコレクション処理の繰り返し処理S
202を1単位処理分だけ実行する。その後は、GC処
理待ちリスト19の登録内容を検査し(S3211)
し、現在の残利用可能領域13の量で、必要とするオブ
ジェクト領域10が確保可能な応用プログラムがいるか
調べ(S3212のYes)、もし存在すれば(S23
12のYes)、GC処理待ちリスト17に登録されて
いるプログラムの識別子を元に該当する応用プログラム
の待ち合わせを解除し(S3213)、GC処理待ちリ
スト17から該当エントリを削除する(S3214)。
なお、現在の残利用可能領域13の量では必要とするオ
ブジェクト領域10が確保可能な応用プログラムがいな
ければ(S3213のNo)、手順S3213及び手順
S3214は行わない。ついで、さらに繰り返し処理S
202を継続する必要があれば(S2002のNo)、
上記手順S202〜S2002を繰り返し行い、繰り返
し処理S202を行う必要が無くなれば(S2002の
Yes)、ガベージコレクション処理の後始末として事
後処理S203を行い、その後ガベージコレクション処
理S321の終了を待っている1ないし複数の応用プロ
グラムに対し、その待ち合わせを解除し(S3011)
処理を終了する。
【0244】手順S201、S202、S203の詳細
は、実施の形態9に等しいので説明を省略する。ただ
し、本実施の形態18では、手順S202に示す処理
は、実施の形態9と異なり、常に必要な回数繰り返され
るため、繰り返しを途中で止めた場合に不整合が発生す
るような処理であってもかまわず、利用できるガベージ
コレクション方式の選択肢は、実施の形態9より広が
る。
【0245】次に、本実施の形態18の動作について図
34を用いて説明する。図34は、本実施の形態18の
動作を示す解説図であり、本実施の形態18では、実施
の形態16と同様、一定の周期で応用プログラムおよび
ガベージコレクション処理(GC処理)S321が時間
間隔T1で定期的に動作している。また、実施の形態1
6と同じく、応用プログラムはA、B、Cの3種類が存
在し、それらの処理優先度はA>B>Cの順であるた
め、同じタイミングで起動されているが基本的にはA、
B、Cの順でその動作が始まり、またAが動作している
間はB及びCは動作できず、Bが動作している間はCが
動作できないよう制御される。ガベージコレクション処
理S321は、A、B、Cのいずれの応用プログラムよ
りも処理優先度が低いため、原則としてA、B、Cのい
ずれかの応用プログラムが動作している間は動作できな
いよう制御される。
【0246】時刻t1は応用プログラムA、B、C及び
ガベージコレクション処理S321の起動契機であり、
処理優先度に従い、まず応用プログラムAが時刻t1〜
t2の間動作し、ついで応用プログラムAの動作終了
後、応用プログラムBが時刻t2から動作を開始する。
しかし、応用プログラムBは時刻t3の時点で、そのプ
ログラムの処理の一部として明示的にガベージコレクシ
ョン処理の実行を指示する(S300)と、ガベージコ
レクション処理S301の終了の待ち合わせに入り(S
3001)、その結果、応用プログラムCが実行可能と
なりその実行が始まる。応用プログラムCは時刻t4の
時点で、そのプログラムの処理としてオブジェクト領域
10の獲得S320を行おうとすると、残利用可能領域
13の不足(S3101のNo)から、GC処理待ちリ
スト19へ自プログラムの必要量と識別子を登録(S3
201)したのち、ガベージコレクション処理S301
から待ち合わせ解除の待ちに入り(S3202)、その
後ガベージコレクション処理S321の処理に移る。
【0247】ガベージコレクション処理S321では、
数回手順S202を繰り返すと、応用プログラムCが必
要とするオブジェクト領域10が獲得できるまで残利用
可能領域13が増えたので、GC処理待ちリスト19に
登録されている情報を元に、応用プログラムCの待ちを
時刻t5の時点で解除する(S3213)。その結果、
手順S3202により停止していた応用プログラムCの
待ち合わせが解除され、応用プログラムCはその処理を
再開、時刻t6の時点でその処理を終了する。その後は
再度ガベージコレクション処理がS321、応用プログ
ラムCの動作により時刻t5の時点で停止していた処理
を再開、時刻t7の時点でガベージコレクション処理S
321が終了すると、手順3011により停止していた
応用プログラムBの待ち合わせが解除され、応用プログ
ラムBはその処理を再開、時刻t8の時点でその処理を
終了する。
【0248】本実施の形態18は上記のように、周期的
にガベージコレクション処理が動作する計算機システム
において、応用プログラムの動作がガベージコレクショ
ン処理の実行を待つ必要がある場合に、その処理優先度
の延長上でガベージコレクション処理を進めること無
く、他の応用プログラムの動作を優先して行うよう動作
し、さらに残利用可能領域13の不足からガベージコレ
クション処理の実行を待つ必要のある応用プログラム
と、明示的にガベージコレクション処理の実行を指示し
た応用プログラムとでは前者の動作を優先するよう動作
すし、そのうえ、残利用可能領域13の不足からガベー
ジコレクション処理の実行を待つ必要のある複数の応用
プログラムの間では、必要量が少ない応用プログラムの
動作を優先するよう動作するので、応用プログラムの動
作の応答性が向上する。
【0249】なお、本実施の形態18では、手順S32
13、手順S3214にて、該当する応用プログラムの
1つについてのみ待ち合わせを解除するようにしたが、
これは該当する複数の応用プログラムに対して待ち合わ
せを解除するようにしてもよく、この場合待ち合わせを
解除された応用プログラムは、その処理優先度の高いも
のから順に可能な限りオブジェクト領域10を獲得する
ように動作するので、応用プログラムの動作の応答性は
さらに向上する。
【0250】また、本実施の形態18に示すガベージコ
レクション処理に対し、実施の形態9あるいは実施の形
態10を組み合わせ、その実行時間の制限を持たせた
り、また実施の形態3で述べたように、獲得した残利用
可能領域がある閾値を超えたところで処理を中断するよ
う変更してもよく、それぞれの実施の形態の効果を得る
ことができる。ただし、このような変更を行った場合
は、手順S202に示す処理は必要な回数に満たない回
数しか繰り返されない場合が有り得るようになるので、
手順S202の繰り返しを途中で止めた場合でも不整合
が発生しないよう、実施の形態3、実施の形態9あるい
は実施の形態10に示したようなガベージコレクション
方式を採用する必要がある。
【0251】
【発明の効果】以上のように、この発明の請求項1によ
れば、参照カウンタ方式と他の方式を併用したガベージ
コレクション手段を備えた動的メモリ管理機構におい
て、ポインタの値の変更の動作を予測可能とし、かつそ
の実装を簡素にできるという効果がある。
【0252】また、この発明の請求項2によれば、請求
項1の効果に加え、請求項1による動的メモリ管理機構
より、ガベージコレクション処理の効率を高められると
いう効果がある。
【0253】この発明の請求項3によれば、ガベージコ
レクション手段を備えた動的メモリ管理機構において、
メモリリーク現象やフラグメンテーション現象が発生せ
ず、かつメモリ利用効率を高められるという効果があ
る。
【0254】この発明の請求項4によれば、請求項3の
効果に加え、ガベージコレクション処理全体の処理時間
を短縮できるという効果がある。
【0255】この発明の請求項5によれば、請求項3の
効果に加え、ガベージコレクション処理全体の処理時間
を短縮できるという効果がある。
【0256】この発明の請求項6によれば、請求項3の
効果に加え、ガベージコレクション処理の効率を向上で
きるという効果がある。
【0257】この発明の請求項7によれば、請求項3の
効果に加え、ガベージコレクション処理の効率を向上で
き、さらにガベージコレクション処理の動作を簡素にで
きるというという効果がある。
【0258】この発明の請求項8によれば、請求項3の
効果に加え、ガベージコレクション処理の効率を向上で
きるという効果がある。
【0259】この発明の請求項9によれば、オブジェク
ト領域のコピーを伴う方式のガベージコレクション手段
を備えた動的メモリ管理機構において、その処理を簡素
にすることができ、さらにガベージコレクション処理の
速度が高まるという効果がある。
【0260】この発明の請求項10によれば、定期的に
動作するガベージコレクション手段を備えた動的メモリ
管理機構において、応用プログラムの周期的動作の阻害
せず、計算機システムの定応答性を向上できるという効
果がある。
【0261】この発明の請求項11によれば、請求項1
0の効果に加え、計算機システムの動作を安定にすると
いう効果がある。
【0262】この発明の請求項12によれば、請求項1
0の効果に加え、メモリ利用効率が向上するという効果
がある。
【0263】この発明の請求項13によれば、請求項1
2の効果に加え、より応用プログラムの動作および計算
機システム全体の動作が安定するという効果がある。
【0264】この発明の請求項14によれば、ガベージ
コレクション手段を備えた動的メモリ管理機構におい
て、計算機システムの性能が向上するという効果があ
る。
【0265】この発明の請求項15によれば、ガベージ
コレクション手段を備えた動的メモリ管理機構におい
て、応用プログラムの動作の応答性を向上させるという
効果がある。
【0266】この発明の請求項16によれば、ガベージ
コレクション手段を備えた動的メモリ管理機構におい
て、計算機システムの動作を安定させるという効果があ
る。
【0267】この発明の請求項17によれば、ガベージ
コレクション手段を備えた動的メモリ管理機構におい
て、計算機システムの立ち上げ段階では立ち上げ処理時
間が短くなり、計算機システムの定常段階では応用プロ
グラムの動作の応答性が向上するという効果がある。
【0268】この発明の請求項18によれば、定期的に
動作するガベージコレクション手段を備えた動的メモリ
管理機構において、応用プログラムの動作の応答性が向
上するという効果がある。
【0269】この発明の請求項19によれば、定期的に
動作するガベージコレクション手段を備えた動的メモリ
管理機構において、応用プログラムの動作の応答性が向
上するという効果がある。
【0270】この発明の請求項20によれば、請求項1
8の効果に加え、ガベージコレクション処理の効率を高
められるという効果がある。
【0271】この発明の請求項21によれば、定期的に
動作するガベージコレクション手段を備えた動的メモリ
管理機構において、応用プログラムの動作の応答性が向
上するという効果がある。
【図面の簡単な説明】
【図1】 この発明の実施の形態1に係る動的メモリ管
理機構の構成を示すブロック図である。
【図2】 この発明の実施の形態1に係る動的メモリ管
理機構の動作を示すフローチャートである。
【図3】 この発明の実施の形態1における動作実施前
を示す解説図である。
【図4】 この発明の実施の形態1における動作実施後
を示す解説図である。
【図5】 この発明の実施の形態2に係る動的メモリ管
理機構の動作を示すフローチャートである。
【図6】 この発明の実施の形態2における動作実施後
を示す解説図である。
【図7】 この発明の実施の形態3に係る動的メモリ管
理機構の構成を示すブロック図である。
【図8】 この発明の実施の形態3に係る動的メモリ管
理機構の動作を示すフローチャートである。
【図9】 この発明の実施の形態3における動作を示す
解説図である。
【図10】 この発明の実施の形態4の動作を示すフロ
ーチャートである。
【図11】 この発明の実施の形態5における動作を示
す解説図である。
【図12】 この発明の実施の形態6における動作を示
す解説図である。
【図13】 この発明の実施の形態7の動作を示す全体
のフローチャートである。
【図14】 この発明の実施の形態7における部分コン
パクト処理を示すフローチャートである。
【図15】 この発明の実施の形態7における動作を示
す解説図である。
【図16】 この発明の実施の形態8を示す構成図であ
る。
【図17】 この発明の実施の形態9の動作を示すフロ
ーチャートである。
【図18】 この発明の実施の形態9における動作を示
す解説図である。
【図19】 この発明の実施の形態10の動作を示すフ
ローチャートである。
【図20】 この発明の実施の形態10における動作を
示す解説図である。
【図21】 この発明の実施の形態11の動作を示すフ
ローチャートである。
【図22】 この発明の実施の形態11における動作を
示す解説図である。
【図23】 この発明の実施の形態12に係る動的メモ
リ管理機構の構成を示すブロック図である。
【図24】 この発明の実施例12の動作を示す全体の
フローチャートである。
【図25】 この発明の実施例12における非コピー式
のガベージコレクション処理を示すフローチャートであ
る。
【図26】 この発明の実施の形態13の動作を示すフ
ローチャートである。
【図27】 この発明の実施の形態14の動作を示すフ
ローチャートである。
【図28】 この発明の実施の形態15の動作を示すフ
ローチャートである。
【図29】 この発明の実施の形態16の動作を示すフ
ローチャートである。
【図30】 この発明の実施の形態16における動作を
示す解説図である。
【図31】 この発明の実施の形態17の動作を示すフ
ローチャートである。
【図32】 この発明の実施の形態17における動作を
示す解説図である。
【図33】 この発明の実施の形態18の動作を示すフ
ローチャートである。
【図34】 この発明の実施の形態18における動作を
示す解説図である。
【図35】 ガベージコレクション処理における「生き
ている」記憶領域と「ごみ」の区別を示す解説図であ
る。
【図36】 第1の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図37】 第1の従来例におけるオブジェクト領域獲
得の動作を示すフローチャートである。
【図38】 第1の従来例におけるポインタの値の変更
の動作を示すフローチャートである。
【図39】 第1の従来例における第1の動作実施前を
示す解説図である。
【図40】 第1の従来例における第1の動作実施の中
間段階1を示す解説図である。
【図41】 第1の従来例における第1の動作実施の中
間段階2を示す解説図である。
【図42】 第1の従来例における第1の動作実施後を
示す解説図である。
【図43】 第1の従来例における第2の動作実施前を
示す解説図である。
【図44】 第1の従来例における第2の動作実施後を
示す解説図である。
【図45】 第2の従来例の動作を示すフローチャート
である。
【図46】 第3の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図47】 第3の従来例の動作を示すフローチャート
である。
【図48】 第3の従来例における動作を示す解説図で
ある。
【図49】 第4の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図50】 第4の従来例の動作を示すフローチャート
である。
【図51】 第4の従来例における動作を示す解説図で
ある。
【図52】 第5の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図53】 第5の従来例の動作を示すフローチャート
である。
【図54】 第5の従来例における動作を示す解説図で
ある。
【図55】 第6の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図56】 第7の従来例の動作を示すフローチャート
である。
【図57】 第8の従来例の動的メモリ管理機構の構成
を示すブロック図である。
【図58】 第8の従来例における第1の動作を示すフ
ローチャートである。
【図59】 第8の従来例における第1の動作を示す解
説図である。
【図60】 第8の従来例における第2の動作を示すフ
ローチャートである。
【図61】 第8の従来例における第2の動作を示す解
説図である。
【符号の説明】
1 動的メモリ管理機構、2 ヒープ領域、3 メモリ
獲得手段、4 メモリ開放手段、5 ガベージコレクシ
ョン手段、10 オブジェクト領域、11 参照カウン
タ、12 ポインタ、13 残利用可能領域、14 既
獲得済み領域、15 TO領域、16 FROM領域、
17 参照テーブル、18 フリーリスト、19 ガベ
ージコレクション(GC)処理待ちリスト、20 マー
ク、21ごみリスト、22 間接ポインタ、23 OL
D領域。

Claims (22)

    【特許請求の範囲】
  1. 【請求項1】 ヒープ領域と、 前記ヒープ領域からその一部をオブジェクト領域として
    獲得するメモリ獲得手段と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 前記各オブジェクト領域にはそれぞれ、その利用状況を
    示す参照カウンタが存在し、各参照カウンタは対応する
    オブジェクト領域を参照するポインタの数を示すようそ
    の値が増減し、 前記ガベージコレクション手段は、前記参照カウンタの
    値が0となったとき対応するオブジェクト領域を開放す
    る参照カウンタ方式のガベージコレクション処理と、他
    の方式によるガベージコレクション処理を併用して動作
    する場合に、前記参照カウンタの値が0になり対応する
    第1のオブジェクト領域が開放される際に、前記第1の
    オブジェクト領域のみ開放し、前記第1のオブジェクト
    領域内にある1ない複数のポインタが参照している第2
    のオブジェクト領域については、参照カウンタの値の更
    新処理および同処理に付随して発生しうるオブジェクト
    領域の開放処理を行わないことを特徴とする動的メモリ
    管理機構。
  2. 【請求項2】 前記ガベージコレクション手段は、前記
    参照カウンタの値が0となって前記第1のオブジェクト
    領域を開放するときに、前記第1のオブジェクトの領域
    内にある1ないし複数のポインタの値を無効値に設定す
    ることを特徴とする請求項1記載の動的メモリ管理機
    構。
  3. 【請求項3】 ヒープ領域と、前記ヒープ領域からその
    一部をオブジェクト領域として獲得するメモリ獲得手段
    と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 前記メモリ獲得手段は、前記ヒープ領域内の残利用可能
    領域の一端から順次オブジェクト領域を獲得し、 前記ガベージコレクション手段は、まず前記残利用可能
    領域をTO領域とし、前記TO領域に隣接する同量ない
    しそれ以下の既獲得済み領域をFROM領域とし、コピ
    ーにより個々のオブジェクト領域を移動させる形で部分
    ガベージコレクション処理を行い、次に、前記TO領域
    のうちオブジェクト領域が移動しないで利用可能として
    残った領域と、空になったFROM領域を合わせた新し
    い残利用可能領域を新たなTO領域とし、まだガベージ
    コレクション処理を行ってない既獲得済み領域のうち新
    しい残利用可能領域と同量の領域を新たなFROM領域
    として再度部分ガベージコレクション処理を行い、既獲
    得済み領域の全体にガベージコレクション処理が及ぶま
    で、以降も同様に部分ガベージコレクション処理を繰り
    返すことを特徴とする動的メモリ管理機構。
  4. 【請求項4】 前記ガベージコレクション手段は、部分
    ガベージコレクション処理を繰り返す際に、その途中で
    新しく生成した残利用可能領域の大きさがある閾値を超
    えた場合は、そこで繰り返しを止めることを特徴とする
    請求項3記載の動的メモリ管理機構。
  5. 【請求項5】 前記ガベージコレクション手段は、部分
    ガベージコレクション処理を繰り返す前に、まずヒープ
    領域外の存在するポインタから参照されるオブジェクト
    領域のベースポインタリストを作成し、続いて繰り返さ
    れる部分ガベージコレクション処理では、ヒープ領域外
    に存在するポインタの代わりに前記ベースポインタリス
    トが保持するポインタを用いて処理を行い、前記ポイン
    タが参照するオブジェクト領域がTO領域へコピーされ
    た場合は、前記ポインタを前記ベースポインタリストか
    ら削除することを特徴とする請求項3記載の動的メモリ
    管理機構。
  6. 【請求項6】 前記ガベージコレクション手段は、ガベ
    ージコレクション処理の繰り返しに際し、TO領域とな
    る残利用可能領域がヒープ領域内を常に一方向へ移動す
    るよう、残利用可能領域からのオブジェクト領域獲得順
    序およびヒープ領域内におけるFROM領域とTO領域
    の相対位置を固定させていることを特徴とする請求項3
    記載の動的メモリ管理機構。
  7. 【請求項7】 前記ガベージコレクション手段は、ガベ
    ージコレクション処理の繰り返しに際し、TO領域とな
    る残利用可能領域がヒープ領域内を往復するよう、残利
    用可能領域からのオブジェクト領域獲得順序およびヒー
    プ領域内におけるFROM領域とTO領域の相対位置を
    変化させることを特徴と請求項3記載の動的メモリ管理
    機構。
  8. 【請求項8】 前記ガベージコレクション手段は、TO
    領域となる残利用可能領域が小さい時は、既獲得済み領
    域からTO領域に隣接して設定するFORM領域をTO
    領域の量より大きく設定し、まずFROM領域内の有効
    なオブジェクト領域の探索をオブジェクト領域の移動を
    伴わずに行い、ついでFORM領域内の有効なオブジェ
    クト領域をFROM領域とTO領域を合わせた領域の一
    端につめることで、残利用可能領域を大きくしてから、
    前記部分ガベージコレクション処理を実行することを特
    徴とする請求項3記載の動的メモリ管理機構。
  9. 【請求項9】 ヒープ領域と、 前記ヒープ領域からその一部をオブジェクト領域として
    獲得するメモリ獲得手段と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 前記各オブジェクト領域を参照するポインタは、直接に
    は参照テーブルのエントリを指し、前記ポインタによる
    オブジェクト領域の参照は、必ず前記参照テーブルのエ
    ントリを経由して行うことを特徴とする動的メモリ管理
    機構。
  10. 【請求項10】 ヒープ領域と、 前記ヒープ領域からその一部をオブジェクト領域として
    獲得するメモリ獲得手段と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 前記ガベージコレクション手段は、周期的に一定時間以
    下のみガベージコレクション処理を行うよう動作するこ
    とを特徴とする動的メモリ管理機構。
  11. 【請求項11】 前記ガベージコレクション手段は、周
    期的に一定の比率で真/偽が変化するフラグを参照し、
    前記フラグが真の間だけ、ガベージコレクション処理を
    行うよう動作することを特徴とする請求項10記載の動
    的メモリ管理機構。
  12. 【請求項12】 前記ガベージコレクション手段は、 ガベージコレクション処理の実施可否を示すカウンタ
    と、 周期的に前記カウンタを適切な値で増加させるカウンタ
    増加手段とを有し、 ガベージコレクション処理の進行状況に応じて前記カウ
    ンタの値を減算しながら、前記カウンタの値が正の間だ
    けガベージコレクション処理を行うよう動作することを
    特徴とする請求項10記載の動的メモリ管理機構。
  13. 【請求項13】 前記ガベージコレクション手段は、前
    記ヒープ領域内の残利用可能領域の量がある閾値を超え
    るまでは、前記カウンタの値が負にあってもガベージコ
    レクション処理を継続することを特徴とする請求項12
    記載の動的メモリ管理機構。
  14. 【請求項14】 ヒープ領域と、 前記ヒープ領域からその一部をオブジェクト領域として
    獲得するメモリ獲得手段と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 前記ガベージコレクション手段は、ガベージコレクショ
    ン処理を行う契機となった理由、プログラムの動作状
    況、動的メモリ管理機構の内部状況、あるいはシステム
    の稼動状況などのシステム状態に応じて、適宜異なるガ
    ベージコレクション方式を使い分けることを特徴とする
    動的メモリ管理機構。
  15. 【請求項15】 前記ガベージコレクション手段は、ヒ
    ープ領域内の残利用可能領域の不足により応用プログラ
    ムの動作中に前記メモリ獲得手段が応用プログラムから
    要求された量のオブジェクト領域を獲得できないため臨
    時に行う場合と、あらかじめ設定されていたタイミング
    により行う場合とで、異なるガベージコレクション方式
    を使い分けることを特徴とする請求項14の動的メモリ
    管理機構。
  16. 【請求項16】 前記ガベージコレクション手段は、最
    も最近に実施したガベージコレクション処理の後に前記
    メモリ獲得手段により獲得され、いまだガベージコレク
    ションの処理の対象となったことのないオブジェクト領
    域の数に応じて、異なるガベージコレクション方式を使
    い分けることを特徴とする請求項14記載の動的メモリ
    管理機構。
  17. 【請求項17】 前記ガベージコレクション手段は、計
    算機システムがシステム立ち上げ段階として動作してい
    る場合と、システムの定常段階として動作している場合
    とで、異なるガベージコレクション方式を使い分けるこ
    とを特徴とする請求項14記載の動的メモリ管理機構。
  18. 【請求項18】 ヒープ領域と、 前記ヒープ領域からその一部をオブジェクト領域として
    獲得するメモリ獲得手段と、 前記獲得したオブジェクト領域を前記ヒープ領域に戻し
    再利用可能とするメモリ開放手段と、 前記メモリ獲得手段により獲得されたがプログラムから
    利用されなくなったオブジェクト領域を探索し、前記メ
    モリ開放手段を用いて前記ヒープ領域へ開放するガベー
    ジコレクション手段とを備え、 応用プログラムの動作によりガベージコレクション処理
    が必要となると、即座にガベージコレクション処理を行
    うのではなく、別途定められたタイミングで行われるガ
    ベージコレクション処理が終了するまで、同応用プログ
    ラムの動作を停止させることを特徴とした動的メモリ管
    理機構。
  19. 【請求項19】 応用プログラムからの明示的にガベー
    ジコレクション指示が行われた場合に、即座にガベージ
    コレクション処理を行うのではなく、別途定められたタ
    イミングで行われるガベージコレクション処理が終了す
    るまで、同応用プログラムの動作を停止させることを特
    徴と請求項18記載の動的メモリ管理機構。
  20. 【請求項20】 応用プログラムが前記メモリ獲得手段
    を用いてオブジェクト領域を獲得しようとしたときに、
    ヒープ領域内の残利用可能領域から応用プログラムが必
    要するオブジェクト領域を得られないため、ガベージコ
    レクション処理が必要となった場合に、即座にガベージ
    コレクション処理を行うのではなく、別途定められたタ
    イミングで行われるガベージコレクション処理が終了す
    るまで、同応用プログラムの動作を停止させることを特
    徴とする請求項18記載の動的メモリ管理機構。
  21. 【請求項21】 複数の応用プログラムがガベージコレ
    クション処理の終了を待っている場合に、ガベージコレ
    クション処理により増加するヒープ領域内の残利用可能
    領域が、各プログラムのそれぞれの要求を満たすように
    なった場合、各プログラムは処理の継続が可能となった
    時点で順次その停止が解除されることを特徴とする請求
    項18記載の動的メモリ管理機構。
  22. 【請求項22】 請求項1から請求項21までのいずれ
    かに記載の動的メモリ管理機構を実現する計算機システ
    ムのプログラムを記録した情報記録媒体。
JP14471398A 1998-05-26 1998-05-26 動的メモリ管理機構 Pending JPH11338761A (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP14471398A JPH11338761A (ja) 1998-05-26 1998-05-26 動的メモリ管理機構

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP14471398A JPH11338761A (ja) 1998-05-26 1998-05-26 動的メモリ管理機構

Publications (1)

Publication Number Publication Date
JPH11338761A true JPH11338761A (ja) 1999-12-10

Family

ID=15368572

Family Applications (1)

Application Number Title Priority Date Filing Date
JP14471398A Pending JPH11338761A (ja) 1998-05-26 1998-05-26 動的メモリ管理機構

Country Status (1)

Country Link
JP (1) JPH11338761A (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2011505042A (ja) * 2007-11-29 2011-02-17 インターナショナル・ビジネス・マシーンズ・コーポレーション メモリ管理

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2011505042A (ja) * 2007-11-29 2011-02-17 インターナショナル・ビジネス・マシーンズ・コーポレーション メモリ管理
US8346822B2 (en) 2007-11-29 2013-01-01 International Business Machines Corporation Memory management

Similar Documents

Publication Publication Date Title
US11775429B2 (en) NUMA-aware garbage collection
US6865585B1 (en) Method and system for multiprocessor garbage collection
US8245239B2 (en) Deterministic runtime execution environment and method
KR100715638B1 (ko) 메모리 재사용 방법
US6862674B2 (en) Methods and apparatus for performing a memory management technique
US6314436B1 (en) Space-limited marking structure for tracing garbage collectors
US9037830B2 (en) Organization of a small object area and a large object area in a Java heap
JP2003507814A (ja) 固定サイズのリメンバードセットを使用する、トレインアルゴリズムに基づくガーベッジコレクター
JP4064404B2 (ja) 適応型ガーベージコレクション方法及び前記方法を行う装置
US20120254267A1 (en) Numa-aware garbage collection
JPH04195577A (ja) マルチプロセッサにおけるタスクスケジューリング方式
JP4756231B2 (ja) 掃除用のガーベッジコレクションの効果を高めるための方法、コンピュータ読み取り可能媒体、コンピュータシステム、及び、メモリ
US6427154B1 (en) Method of delaying space allocation for parallel copying garbage collection
CN112219196B (zh) 表示用于无暂停垃圾收集的激活帧的方法和装置
JPH11338761A (ja) 動的メモリ管理機構
Wei et al. Practically and theoretically efficient garbage collection for multiversioning
KR100846499B1 (ko) 메모리를 관리하는 방법 및 장치
JP2000099351A (ja) プログラム制御装置とメモリ割当装置および方法
KR100772872B1 (ko) 다중 자바 어플리케이션 환경에서 가상 아이디를 이용하여자원을 관리하는 장치 및 그 방법
US6842838B2 (en) Preemptive memory-block splitting
JP4050855B2 (ja) ガベージコレクション装置および方法
Lueh et al. Global register allocation based on graph fusion
US10936483B2 (en) Hybrid garbage collection
CN121560777B (zh) 面向编译型语言的内存回收方法、系统及计算机可读存储介质
JPH0566989A (ja) 情報処理システムにおける記憶管理装置