(57)【特許請求の範囲】
【請求項１】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収するフル・ガーベジ・コレクション手段と、
前記ヒープ中のセルから、前記フル・ガーベジ・コレクション手段によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルを抽出し、その抽出されたセルについて該アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収するパーシャル・ガーベジ・コレクション手段と、
前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段によって過去に行なわれた不使用のセルの回収の状況に応じ、次に行なう不使用のセルの回収を、該フル・ガーベジ・コレクション手段と該パーシャル・ガーベジ・コレクション手段とのどちらかに行わせる制御を行なうフル・パーシャル制御手段と、
を有することを特徴とするメモリ管理装置。
【請求項２】
前記フル・パーシャル制御手段は、前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段のどちらかによって行なわれた前回の不使用のセルの回収における回収量に応じて前記制御を行なうことを特徴とする請求項１に記載のメモリ管理装置。
【請求項３】
前記フル・パーシャル制御手段は、前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段のどちらによって前々回に不使用のセルの判別若しくは回収がされている期間中に前記アプリケーションプログラムの実行によって使用が開始された前記ヒープ中のセルの使用開始量に対する、前記パーシャル・ガーベジ・コレクション手段によって行なわれた前回の不使用のセルの回収における回収量の比に応じて前記制御を行なうことを特徴とする請求項１に記載のメモリ管理装置。
【請求項４】
前記フル・パーシャル制御手段は、前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段のどちらかによる前回のセルの使用状況の判別若しくは回収がされている期間に、前記ヒープ中のセルであって、前記アプリケーションプログラムの実行によって該セルの有するデータの変更がされた該セルの個数に応じて前記制御を行なうことを特徴とする請求項１に記載のメモリ管理装置。
【請求項５】
前記フル・パーシャル制御手段は、前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段のどちらかによる前回のセルの使用状況の判別若しくは回収がされている期間に、前記ヒープ中のセルであって、前記アプリケーションプログラムの実行によって該セルの有するデータの変更がされた該セルの個数と、該フル・ガーベジ・コレクション手段によって最近に行なわれたセルの使用状況の判別以降の期間に、該フル・ガーベジ・コレクション手段若しくは該パーシャル・ガーベジ・コレクション手段のいずれかによって行なわれたセルの使用状況の判別においてそれらの判別時点で使用中であると判別された該ヒープ中のセルの個数と、の比に応じて、前記制御を行なうことを特徴とする請求項１に記載のメモリ管理装置。
【請求項６】
前記フル・パーシャル制御手段は、前記アプリケーションプログラムの実行の途中で前記ヒープの使用状況が変化することを示す通知に応じて前記制御を行なうことを特徴とする請求項１に記載のメモリ管理装置。
【請求項７】
アプリケーションプログラムの実行によって使用されるメモリ資源を管理し、パーシャル・マーキング・ガーベジ・コレクション方式により該メモリ資源から不使用の記憶領域を回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記パーシャル・マーキング・ガーベジ・コレクション方式におけるフル・サイクルのガーベジ・コレクション処理により前記メモリ資源から不使用の記憶領域を回収するフル・ガーベジ・コレクション手段と、
前記パーシャル・マーキング・ガーベジ・コレクション方式におけるパーシャル・サイクルのガーベジ・コレクション処理により前記メモリ資源から不使用の記憶領域を回収するパーシャル・ガーベジ・コレクション手段と、
前記フル・ガーベジ・コレクション手段もしくは前記パーシャル・ガーベジ・コレクション手段によって過去に行なわれた不使用の記憶領域の回収の状況に応じ、次に行なう不使用の記憶領域の回収を、該フル・ガーベジ・コレクション手段と該パーシャル・ガーベジ・コレクション手段とのどちらかに行わせる制御を行なうフル・パーシャル制御手段と、
を有することを特徴とするメモリ管理装置。
【請求項８】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別手段と、
前記フル判別手段による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収手段と、
前記ヒープ中のセルから、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出手段と、
前記パーシャル抽出手段により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別手段と、
前記パーシャル判別手段による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収手段と、
前記ヒープからの不使用のセルの回収を、前記フル回収手段と前記パーシャル回収手段とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御手段と、
を有し、
前記パーシャル回収手段は、前記パーシャル判別手段による判別の結果が不使用であるセルが、前記フル判別手段若しくは前記パーシャル判別手段による判別を初めて経験したものであるときには、該パーシャル判別手段による再度の該判別の結果に基づいて不使用のセルの該ヒープからの回収を行なう、
ことを特徴とするメモリ管理装置。
【請求項９】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別手段と、
前記フル判別手段による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収手段と、
前記ヒープ中のセルから、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出手段と、
前記パーシャル抽出手段により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別手段と、
前記パーシャル判別手段による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収手段と、
前記ヒープからの不使用のセルの回収を、前記フル回収手段と前記パーシャル回収手段とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御手段と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタを、前記パーシャル判別手段に通知する通知手段と、
を有し、
前記パーシャル判別手段は、前記通知手段により通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理装置。
【請求項１０】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別手段と、
前記フル判別手段による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収手段と、
前記ヒープ中のセルから、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出手段と、
前記パーシャル抽出手段により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別手段と、
前記パーシャル判別手段による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収手段と、
前記ヒープからの不使用のセルの回収を、前記フル回収手段と前記パーシャル回収手段とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御手段と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に、該フル判別手段及び前記パーシャル判別手段のいずれによる前記判別も未だ経験していない場合に限り、該第一のポインタを前記パーシャル判別手段に通知する通知手段と、
を有し、
前記パーシャル判別手段は、前記通知手段により通知された前記第一のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理装置。
【請求項１１】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理装置であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別手段と、
前記フル判別手段による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収手段と、
前記ヒープ中のセルから、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出手段と、
前記パーシャル抽出手段により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別手段と、
前記パーシャル判別手段による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収手段と、
前記ヒープからの不使用のセルの回収を、前記フル回収手段と前記パーシャル回収手段とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御手段と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別手段によって最近に行なわれたセルの使用状況の判別以後の期間に該フル判別手段又は前記パーシャル判別手段のいずれかによる前記判別を経験していた場合に限り、該第二のポインタを前記パーシャル判別手段に通知する通知手段と、
を有し、
前記パーシャル判別手段は、前記通知手段により通知された前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理装置。
【請求項１２】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理方法であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第一の工程と、
前記ヒープ中のセルから、前記第一の工程によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルを抽出し、その抽出されたセルについて該アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第二の工程と、
前記第一の工程もしくは前記第二の工程によって過去に行なわれた不使用のセルの回収の状況に応じ、次に行なう不使用のセルの回収を、該第一の工程と該第二の工程とのどちらかに行わせる制御を行なう第三の工程と、
を行なうことを特徴とするメモリ管理方法。
【請求項１３】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理方法であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別工程と、
前記フル判別工程による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収工程と、
前記ヒープ中のセルから、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出工程と、
前記パーシャル抽出工程により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別工程と、
前記パーシャル判別工程による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収工程と、
前記ヒープからの不使用のセルの回収を、前記フル回収工程と前記パーシャル回収工程とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御工程と、
を行ない、
前記パーシャル回収工程は、前記パーシャル判別工程による判別の結果が不使用であるセルが、前記フル判別工程若しくは前記パーシャル判別工程による判別を初めて経験したものであるときには、該パーシャル判別工程による再度の該判別の結果に基づいて不使用のセルの該ヒープからの回収を行なう、
ことを特徴とするメモリ管理方法。
【請求項１４】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理方法であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別工程と、
前記フル判別工程による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収工程と、
前記ヒープ中のセルから、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出工程と、
前記パーシャル抽出工程により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別工程と、
前記パーシャル判別工程による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収工程と、
前記ヒープからの不使用のセルの回収を、前記フル回収工程と前記パーシャル回収工程とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御工程と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタを、前記パーシャル判別工程に通知する通知工程と、
を行ない、
前記パーシャル判別工程は、前記通知工程により通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理方法。
【請求項１５】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理方法であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別工程と、
前記フル判別工程による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収工程と、
前記ヒープ中のセルから、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出工程と、
前記パーシャル抽出工程により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別工程と、
前記パーシャル判別工程による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収工程と、
前記ヒープからの不使用のセルの回収を、前記フル回収工程と前記パーシャル回収工程とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御工程と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に、該フル判別工程及び前記パーシャル判別工程のいずれによる前記判別も未だ経験していない場合に限り、該第一のポインタを前記パーシャル判別工程に通知する通知工程と、
を行ない、
前記パーシャル判別工程は、前記通知工程により通知された前記第一のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理方法。
【請求項１６】
データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なうメモリ管理方法であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別工程と、
前記フル判別工程による判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収工程と、
前記ヒープ中のセルから、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出工程と、
前記パーシャル抽出工程により抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別工程と、
前記パーシャル判別工程による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収工程と、
前記ヒープからの不使用のセルの回収を、前記フル回収工程と前記パーシャル回収工程とのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御工程と、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別工程によって最近に行なわれたセルの使用状況の判別以後の期間に該フル判別工程又は前記パーシャル判別工程のいずれかによる前記判別を経験していた場合に限り、該第二のポインタを前記パーシャル判別工程に通知する通知工程と、
を行ない、
前記パーシャル判別工程は、前記通知工程により通知された前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう、
ことを特徴とするメモリ管理方法。
【請求項１７】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムを記憶したコンピュータで読み取り可能な記憶媒体であって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第一のステップと、
前記ヒープ中のセルから、前記第一のステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルを抽出し、その抽出されたセルについて該アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第二のステップと、
前記第一のステップもしくは前記第二のステップによって過去に行なわれた不使用のセルの回収の状況に応じ、次に行なう不使用のセルの回収を、該第一のステップと該第二のステップとのどちらかに行わせる制御を行なう第三のステップと、
からなる処理を該コンピュータに行なわせるメモリ管理プログラムを記憶した記憶媒体。
【請求項１８】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムを記憶したコンピュータで読み取り可能な記憶媒体であって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル回収ステップは、前記パーシャル判別ステップによる判別の結果が不使用であるセルが、前記フル判別ステップ若しくは前記パーシャル判別ステップによる判別を初めて経験したものであるときには、該パーシャル判別ステップによる再度の該判別の結果に基づいて不使用のセルの該ヒープからの回収を行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラムを記憶した記憶媒体。
【請求項１９】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムを記憶したコンピュータで読み取り可能な記憶媒体であって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタを、前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラムを記憶した記憶媒体。
【請求項２０】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムを記憶したコンピュータで読み取り可能な記憶媒体であって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に、該フル判別ステップ及び前記パーシャル判別ステップのいずれによる前記判別も未だ経験していない場合に限り、該第一のポインタを前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知された前記第一のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラムを記憶した記憶媒体。
【請求項２１】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムを記憶したコンピュータで読み取り可能な記憶媒体であって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に該フル判別ステップ又は前記パーシャル判別ステップのいずれかによる前記判別を経験していた場合に限り、該第二のポインタを前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知された前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラムを記憶した記憶媒体。
【請求項２２】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムであって、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第一のステップと、
前記ヒープ中のセルから、前記第一のステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルを抽出し、その抽出されたセルについて該アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルを該ヒープから回収する第二のステップと、
前記第一のステップもしくは前記第二のステップによって過去に行なわれた不使用のセルの回収の状況に応じ、次に行なう不使用のセルの回収を、該第一のステップと該第二のステップとのどちらかに行わせる制御を行なう第三のステップと、
からなる処理を該コンピュータに行なわせるメモリ管理プログラム。
【請求項２３】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムであって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル回収ステップは、前記パーシャル判別ステップによる判別の結果が不使用であるセルが、前記フル判別ステップ若しくは前記パーシャル判別ステップによる判別を初めて経験したものであるときには、該パーシャル判別ステップによる再度の該判別の結果に基づいて不使用のセルの該ヒープからの回収を行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラム。
【請求項２４】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムであって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタを、前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラム。
【請求項２５】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムであって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に、該フル判別ステップ及び前記パーシャル判別ステップのいずれによる前記判別も未だ経験していない場合に限り、該第一のポインタを前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知された前記第一のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラム。
【請求項２６】
コンピュータに実行させることによって、データ列であるセルの単位で管理されるメモリ資源であって、アプリケーションプログラムの実行によってセル単位で使用される該メモリ資源であるヒープを管理し、不使用のセルを該ヒープから回収するガーベジ・コレクション処理を行なう制御を該コンピュータに行なわせるメモリ管理プログラムであって、
前記メモリ管理プログラムは、
前記ヒープ中の全てのセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうフル判別ステップと、
前記フル判別ステップによる判別の結果に基づいて不使用のセルを前記ヒープから回収するフル回収ステップと、
前記ヒープ中のセルから、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に前記アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なうパーシャル抽出ステップと、
前記パーシャル抽出ステップにより抽出されたセルについて前記アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なうパーシャル判別ステップと、
前記パーシャル判別ステップによる判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なうパーシャル回収ステップと、
前記ヒープからの不使用のセルの回収を、前記フル回収ステップと前記パーシャル回収ステップとのどちらかに行わせる制御を行なうパーシャル・マーキング・ガーベジ・コレクション制御ステップと、
前記アプリケーションプログラムの実行によって、前記ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルが、前記フル判別ステップによって最近に行なわれたセルの使用状況の判別以後の期間に該フル判別ステップ又は前記パーシャル判別ステップのいずれかによる前記判別を経験していた場合に限り、該第二のポインタを前記パーシャル判別ステップに通知する通知ステップと、
からなる処理を該コンピュータに行なわせ、
前記パーシャル判別ステップは、前記通知ステップにより通知された前記第二のポインタの指すセルについて、前記アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう処理を該コンピュータに行なわせる、
ことを特徴とするメモリ管理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メモリ資源を管理する技術に関し、特に、アプリケーションプログラムの実行によって使用されるメモリ資源を管理し、該メモリ資源から不使用の記憶領域を回収するガーベジ・コレクション処理を行なう技術に関する。
【０００２】
【従来の技術】
演算処理システムにおいて、有限であるメモリ資源をプログラマに負担をかけずに効率よく管理する手法として、ガーベジ・コレクション（garbage collection：以下、「ＧＣ」と略す）と呼ばれる手法がある。ＧＣ処理は、メモリ上で不要になったデータを特定し、そのデータのために使用されていたメモリ領域を他のデータが使用可能な領域として回収するというものである。
【０００３】
ＧＣの説明において、管理される対象となるメモリ資源はヒープ（heap）と呼ばれる。このヒープはセル（あるいはオブジェクト）と呼ばれるデータ列の単位から構成され、各セルは、他のセルへのポインタや、ポインタではない他のデータを含むことができる。
【０００４】
また、ヒープ外には、レジスタやスタックなどといった、演算処理システム上で実行されるアプリケーションプログラムが直接参照可能なポインタの集合が存在し、この集合はルート（root）と呼ばれる。ヒープには、このルートからのポインタ参照によって直接あるいは間接に到達可能なセルとそうでないセルとが存在する。前者のセルはアプリケーションプログラムの実行によってアクセスされる可能性があるセルであり、「生きているセル」、「生存セル」などと呼ばれる。これに対して後者のセルはアプリケーションプログラムの実行によってアクセスされることのないセルであり、「死んでいるセル」などと呼ばれる。
【０００５】
ＧＣは、ヒープにおける各セルの生死を区別して死んでいるセルを「ごみ」とみなし、その「ごみ」を他のデータが使用可能な領域として回収するという処理を行なうものである。
【０００６】
ＧＣは、採用されているアルゴリズムの原理によって幾つかの種類に分類することができる。ＧＣの各種手法については、特集  ごみ集めの基礎と最近の動向, 情報処理, Vol.35, No.11 (1994)、の記事全般に詳しく解説されているが、ここでは、そのひとつである、並列型のＧＣと呼ばれているものについて説明する。
【０００７】
ＧＣが行なわれる演算処理システムにおいて実行される処理は、アプリケーションプログラムの実行により行なわれる処理とＧＣの実行によって行なわれる処理とに大別される。この両処理のうち、前者の処理はミューテータ（mutator ）による処理と、また、後者の処理はコレクタ（collector ）による処理と、それぞれ呼ばれる。
【０００８】
ＧＣの基本的なアルゴリズムにおいては、コレクタによる処理を演算処理システムで実行する期間は、ミューテータによる処理によってセルの生死が変化してしまうことを防止するために、ミューテータの処理を一時停止させ、コレクタによる処理が一括して実行される。しかしながら、コレクタによる処理は、基本的にはルートから順にポインタを辿れば到達可能なセルを全て生存セルとして抽出する必要があり、使用されているセルの量によってはかなりの処理負担となるため、ミューテータ側の処理の中断時間も無視できなくなる。
【０００９】
ＧＣに起因するミューテータの実行中断時間をできるだけ短くするために、さまざまなＧＣのアルゴリズムが考案されている。
古典的なＧＣでは、ミューテータによる処理の実行を止め、コレクタが一気にメモリ回収を行なうという、一括型ＧＣと呼ばれる方式が行なわれていた。このＧＣは、ミューテータによる処理を長時間中断してしまうため、アプリケーションプログラムのレスポンスの悪化を招くという問題を抱えていた。
【００１０】
その後、ＧＣを一括して行なうのではなく、コレクタによる処理をミューテータによる処理の中に時間的に分散させ、両者を並列して少しずつ実行するようにしてミューテータによる処理の長時間の中断を防止したものが提案された。これらが並列型と呼ばれているＧＣである。
【００１１】
ここでは、並列型のＧＣのうち、Dijkstra他によって考案されたon-the-fly  ＧＣと、湯浅によって考案されたスナップショット（snapshot）ＧＣとについて、その概要を説明する。なお、これらのＧＣは、Dijkstra,E.W., Lamport, L., Martin, A.J., Scholten, C.S. and Steffens, E.F.M.:On-the-Fly Garbage Collection: An Exercise in Cooperation, Communications of the ACM, Vol.21, No.11, pp.966-975 (1978)、Yuasa, T: Real-Time Garbage Collection on General-Purpose Machines, Journal of Systems and Software,Vol.11, pp.181-198(1990) 、湯浅太一：特集  ごみ集めの基礎と最近の動向, ３．実時間ごみ集め,情報処理, Vol.35,No.11, pp.1006-1013 (1994)、に詳しく解説されている。
【００１２】
on-the-fly  ＧＣは、一括型ＧＣの基本的なアルゴリズムのひとつであるマーク・スイープ（mark and sweep）方式を改良したものである。マーク・スイープ方式では、１サイクルのＧＣがマークフェーズとスイープフェーズとの２種のフェーズに分けて行なわれる。
【００１３】
マークフェーズでは、まず、ルートの獲得が行なわれ（この処理を、特にルート挿入フェーズなどと称することもある）、次に、ルートからポインタを順に辿りながら、到達した全ての生存セルに印をつけてゆく処理が行なわれる。
【００１４】
その次に、スイープフェーズとして、ヒープ全体が走査され、印のついていない（死んでいる）セルが回収されると共に、印のつけられていたセルについては、次サイクルのＧＣに備えるために、その印が消される。以降、マークフェーズ（ルート挿入フェーズを含む）とスイープフェーズとが交互に繰り返される。これがマーク・スイープ方式によるＧＣである。
【００１５】
on-the-fly  ＧＣでは、コレクタが、ミューテータによる処理に並行して、マーク・スイープ方式によるＧＣを実行する。この場合、ミューテータによるポインタの付け替えがコレクタによるＧＣのマークフェーズの途中で発生することがある。このときにはポインタの付け替えによって生存セルとなったにもかかわらず、マークフェーズで印を付けることのできなかったセルが発生してしまうことがあり得る。そうすると、この生存セルが次のスイープフェーズで「ごみ」として回収されてしまう問題が生じる。そこで、on-the-fly  ＧＣでは、ヒープ中の各セルについて、黒（black）、暗黒色（dark）、白（white ）の３色のうちのいずれかの印をつける処理が行なわれる。on-the-fly  ＧＣによるセルへの印付けの手順を図３８に沿って説明する。
【００１６】
コレクタがon-the-fly  ＧＣを開始する前には、ヒープ中の全てのセルは白印が付されている。コレクタは、まず、ルートを参照し、このルートのポインタが直接に指しているセルの印を暗黒色にする。図３８の（Ａ）では、ルートのポインタが直接に指しているセルＡ及びセルＢの印が暗黒色にされたことを示している。なお、同図及び後に説明する図３９においては、セルに付した暗黒色の印を斜線で示している。
【００１７】
ここで、セルの印を暗黒色にすることは、このセルについて、後に黒への印付けの処理を行なうことが必要であることを示すものである。現実には、セルに暗黒色の印付けを行なうのではなく、その代わりの操作として、ＧＣ用に用意されているスタック（ＧＣスタック）にそのセルへのポインタをプッシュする処理（この処理を、「ルート挿入処理」などと呼ぶ）がコレクタによって行なわれる。
【００１８】
次に、コレクタは、暗黒色にしたセルの印を黒に変更する。すなわち、ＧＣ用のスタックからポインタをポップし、そのポインタの指すセルの印を黒に変更する。
【００１９】
更に、コレクタは、黒印に変更されたセルに他のセルを指すポインタが格納されていれば、そこに格納されている全てのポインタが指しているセルの印を暗黒色にする。この処理は、付されている印が黒にされているセルに格納されている他のセルへのポインタをＧＣ用スタックにプッシュする処理となる。同図（Ｂ）は、同図（Ａ）では暗黒色にされていたセルＡの印が黒に変更され、更にこのセルＡに格納されているポインタが指しているセルＣ及びセルＤの印が白から暗黒色にされたことを示している。
【００２０】
on-the-fly  ＧＣでは、コレクタによる処理によって上述したような印付けが行なわれることに加え、ミューテータによる処理によっても印付けが行なわれる。ミューテータは、ルート、またはヒープ上のいずれかのセル、のどちらかにポインタを格納するときに、その格納するポインタが指しているセルに付されている印が白ならば、そのポインタが指しているセルの印を白から暗黒色にする。同図（Ｃ）は、同図（Ａ）ではルートのポインタによってセルＢが指されており、且つ、セルＡに格納されているポインタによってセルＤが指されていたものが、ミューテータによる処理により、ルートのポインタがセルＤを指し、そしてセルＡに格納されているポインタがセルＢを指すように変更されたことを示している。そして、これらの変更によってルート及びセルＡに改めて格納されたポインタが指しているセルＢ及びセルＤのうち、付されている印が白であったセルＤについてその印が暗黒色にされたことを示している。
【００２１】
この後は、コレクタによる処理によって前述した印付けが行なわれる。同図（Ｄ）は、同図（Ａ）では暗黒色にされていたセルＡの印が黒に変更され、更にこのセルＡに格納されているポインタが指しているセルのうち、印が白であるセルＣについてその印が白から暗黒色に変更されたことを示している。このコレクタによる印付けが進んでいくと、印が暗黒色にされているセルはいつかはなくなり（ＧＣ用のスタックが空になり）、ヒープ上の各セルの印は白または黒のいずれかとなる。こうして、on-the-fly  ＧＣにおけるマークフェーズは終了する。
【００２２】
続いて行なわれるスイープフェーズでは、白印が付されているセルが「ごみ」とみなされて回収されると共に、黒印の付されているセルについては、次サイクルのＧＣに備えるために、その印が白に変更される。以降、マークフェーズとスイープフェーズとが交互に繰り返される。これがon-the-fly  ＧＣである。
【００２３】
このように、on-the-fly  ＧＣによれば、ミューテータによる処理によってポインタの付け替えが発生しても、付け替えられたポインタの指すセルの印を暗黒色にしておくことによって、いつかはそのセルについての印付けの処理がコレクタによって行なわれるので、生存セルの誤回収の問題が解消される。
【００２４】
次にスナップショットＧＣについて説明する。スナップショットＧＣも、on-the-fly  ＧＣと同様に、前述したマーク・スイープ方式を改良したものである。
スナップショットＧＣでは、あるＧＣの１サイクルの開始時に使用中であったセルは例えその後そのセルが「ごみ」となったとしてもそのサイクルのスイープフェーズでは回収しない。また、そのＧＣの１サイクル中でミューテータにより使用が開始されたセルも、例えその後そのセルが「ごみ」となったとしてもそのサイクルのスイープフェーズでは回収しない。つまり、スナップショットＧＣでは、ＧＣの１サイクルの開始時に既に「ごみ」であったセルのみを回収する。これは、あたかも、ＧＣの１サイクルの開始時にヒープの使用状況のスナップ写真（スナップショット）を撮影し、その写真に写っている「ごみ」のセルを回収しているかのような処理となる。なお、ＧＣの１サイクルの途中で「ごみ」となったセルは、その次のサイクルのスイープフェーズで回収される。
【００２５】
on-the-fly  ＧＣにおけるマークフェーズでは、ミューテータによる処理によって、ルート、またはヒープ上のいずれかのセル、のどちらかでポインタの付け替えが発生したときに、付け替えられたポインタの指すセルの印を白から暗黒色に変更する（すなわち、付け替えられたポインタをＧＣ用スタックにプッシュする）。これに対し、スナップショットＧＣにおけるマークフェーズでは、ミューテータによる処理によって、ヒープ上のいずれかのセルにポインタを格納するときに、そのポインタを格納するセルがそのポインタを格納する前に格納していたポインタの指しているセルの印が白であれば、その印を暗黒色にする（すなわち、ポインタを改めてセルに格納するときに、そのポインタを格納する前にそのセルに格納されていたポインタをＧＣ用スタックにプッシュする）。一方、スナップショットＧＣにおけるコレクタによる処理はon-the-fly  ＧＣにおけるコレクタによる処理と同様である。
【００２６】
スナップショットＧＣにおけるセルの印付けの手順を図３９に沿って説明する。
図３９の（Ａ）では、図３８の（Ａ）に示したon-the-fly  ＧＣにおけるコレクタによって行なわれる処理と同様に、ルートのポインタが直接に指しているセルＡ及びセルＢの印が暗黒色にされたことを示している。
【００２７】
ここで、ミューテータによる処理により、例えばルートのポインタがセルＤを指し、そしてセルＡに格納されているポインタがセルＢを指すように変更されると、これらの変更前にセルＡに格納されていたポインタが指していたセルＤに付されている印が白であるので、その印が暗黒色にされる。図３９の（Ｂ）がその様子を示している。
【００２８】
スナップショットＧＣにおいては、更に、ミューテータによる処理によって使用が開始されたセルは直ちにその印を白から黒に変更する。これらの印付けの操作により、ＧＣの１サイクルの開始時に生きていたセルの印、及びそのサイクルのマークフェーズの途中で新たに使用されたセルの印は、いつかは全て黒くなる。その後のスイープフェーズではセルの印が白であるセルを「ごみ」とみなして回収する。
【００２９】
on-the-fly  ＧＣと比較したときのスナップショットＧＣの利点は、ミューテータによる処理により行なわれる、セルを指すポインタのルートへの代入操作時には、ＧＣのための処理を不要としたことにある。通常のミューテータによる処理ではルートへのポインタの代入操作が頻繁に発生する。従って、ＧＣのための処理負担をこの代入操作からなくしたことによって、アプリケーションプログラムの実行パフォーマンスの向上が期待できるのである。
【００３０】
【発明が解決しようとする課題】
上述したように、スナップショットＧＣでは、ＧＣの１サイクルの途中で「ごみ」となったセルは、そのサイクルのスイープフェーズで回収されることはなく、次のサイクルのマークフェーズを経た後のスイープフェーズで回収される。しかしながら、スナップショットＧＣのスイープフェーズに要する時間は前述したマーク・スイープ方式でのスイープフェーズに要する時間と同じである。従って、スナップショットＧＣは、並列型ＧＣを実現してはいるものの、ＧＣの１サイクルの途中で「ごみ」となったセルがそのサイクルのスイープフェーズで回収されない分、マーク・スイープ方式でのＧＣよりも「ごみ」セルの回収効率が低下してしまっていると考えられる。このように、並列型ＧＣにおいては、「ごみ」セルの回収効率の向上が大きな課題である。
【００３１】
以上の問題を鑑み、並列型ＧＣの処理効率を向上させることが本発明が解決しようとする課題である。
【００３２】
【課題を解決するための手段】
図１は、本発明の第一の態様の原理構成を示すブロック図である。本発明の第一の態様は、フル・ガーベジ・コレクション手段１、パーシャル・ガーベジ・コレクション手段２、フル・パーシャル制御手段３を備えて構成される。
【００３３】
同図において、アプリケーションプログラム実行部１０は、アプリケーションプログラムを実行する。
ヒープ１１は、データ列であるセルの単位で管理されるメモリ資源である。ヒープ１１は、アプリケーションプログラム実行部１０においてアプリケーションプログラムが実行されることによってセル単位で使用される。
【００３４】
フル・ガーベジ・コレクション手段１は、ヒープ１１中の全てのセルについて、アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルをヒープ１１から回収する。つまり、フル・ガーベジ・コレクション手段１は、並列型ＧＣのひとつであるパーシャル・マーキング・ガーベジ・コレクション方式におけるフル・サイクルのガーベジ・コレクション処理により、不使用のセルをヒープ１１から回収する。
【００３５】
パーシャル・ガーベジ・コレクション手段２は、ヒープ１１中のセルから、フル・ガーベジ・コレクション手段１によって最近に行なわれたセルの使用状況の判別以後の期間に、アプリケーションプログラムの実行によって使用されたことのあるセルを抽出し、その抽出されたセルについて該アプリケーションプログラムの実行によるセルの使用状況の判別を行ない、該判別の結果に基づいて不使用のセルをヒープ１１から回収する。つまり、パーシャル・ガーベジ・コレクション手段２は、パーシャル・マーキング・ガーベジ・コレクション方式におけるパーシャル・サイクルのガーベジ・コレクション処理により、不使用のセルをヒープ１１から回収する。
【００３６】
フル・パーシャル制御手段３は、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２によって過去に行なわれた不使用のセルの回収の状況に応じ、次に行なう不使用のセルの回収を、フル・ガーベジ・コレクション手段１とパーシャル・ガーベジ・コレクション手段２とのどちらかに行わせる制御を行なう。
【００３７】
この図１に示す構成は、アプリケーションプログラムの実行と、セルの回収とを並行して行なうことができるので、並列型ＧＣといえる。
ここで、フル・パーシャル制御手段３は、例えば、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２のどちらかによって行なわれた前回の不使用のセルの回収における回収量に応じて前記制御を行なうようにしてもよい。
【００３８】
あるいは、フル・パーシャル制御手段３は、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２のどちらによって前々回に不使用のセルの判別若しくは回収がされている期間中に前記アプリケーションプログラムの実行によって使用が開始されたヒープ１１中のセルの使用開始量に対する、パーシャル・ガーベジ・コレクション手段２によって行なわれた前回の不使用のセルの回収における回収量の比に応じて前記制御を行なうようにしてもよい。
【００３９】
あるいは、フル・パーシャル制御手段３は、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２のどちらかによる前回のセルの使用状況の判別若しくは回収がされている期間に、ヒープ１１中のセルであって、アプリケーションプログラムの実行によって該セルの有するデータの変更がされた該セルの個数に応じて前記制御を行なうようにしてもよい。
【００４０】
あるいは、フル・パーシャル制御手段３は、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２のどちらかによる前回のセルの使用状況の判別若しくは回収がされている期間に、ヒープ１１中のセルであって、アプリケーションプログラムの実行によって該セルの有するデータの変更がされた該セルの個数と、フル・ガーベジ・コレクション手段１によって最近に行なわれたセルの使用状況の判別以降の期間に、フル・ガーベジ・コレクション手段１若しくはパーシャル・ガーベジ・コレクション手段２のいずれかによって行なわれたセルの使用状況の判別においてそれらの判別時点で使用中であると判別されたヒープ１１中のセルの個数と、の比に応じて、前記制御を行なうようにしてもよい。
【００４１】
あるいは、フル・パーシャル制御手段３は、アプリケーションプログラムの実行の途中でヒープ１１の使用状況が変化することを示す通知に応じて前記制御を行なうようにしてもよい。
【００４２】
この第一の態様の構成では、次に行なう不使用のセルの回収を、フル・ガーベジ・コレクション手段１とパーシャル・ガーベジ・コレクション手段２のうちどちらに行なわせればＧＣ全体の処理効率が良好になるかを、フル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２によって過去に行なわれた不使用のセルの回収の状況に基づいてフル・パーシャル制御手段３が判断する。そして、この判断結果に基づいて、フル・パーシャル制御手段３がフル・ガーベジ・コレクション手段１もしくはパーシャル・ガーベジ・コレクション手段２のどちらかに次回の不使用のセルの回収を行なわせる。従って、この構成により、並列型ＧＣの処理効率を向上させることが可能となる。
【００４３】
図２は、本発明の第二の態様の原理構成を示すブロック図である。本発明の第二の態様は、フル判別手段２１、フル回収手段２２、パーシャル抽出手段２３、パーシャル判別手段２４、パーシャル回収手段２５、パーシャル・マーキング・ガーベシ・コレクション制御手段２６を備えて構成される。
【００４４】
同図において、アプリケーションプログラム実行部１０及びヒープ１１は、図１に示したのと同様のものである。
フル判別手段２１は、ヒープ１１中の全てのセルについて、アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なう。
【００４５】
フル回収手段２２は、フル判別手段２１による判別の結果に基づいて不使用のセルを前記ヒープから回収する。
パーシャル抽出手段２３は、ヒープ１１中のセルから、フル判別手段２１によって最近に行なわれたセルの使用状況の判別以後の期間に、アプリケーションプログラムの実行によって使用されたことのあるセルの抽出を行なう。
【００４６】
パーシャル判別手段２４は、パーシャル抽出手段２３により抽出されたセルについて、アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なう。
【００４７】
パーシャル回収手段２５は、パーシャル判別手段２４による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なう。
パーシャル・マーキング・ガーベジ・コレクション制御手段２６は、ヒープ１１からの不使用のセルの回収を、フル回収手段２２とパーシャル回収手段２５とのどちらかに行わせる制御を行なう。
【００４８】
この図２に示す構成は、アプリケーションプログラムの実行と、セルの回収とを並行して行なうことができるので、並列型ＧＣといえる。
この第二の態様の原理構成においては、パーシャル判別手段２４による判別の結果が不使用であるセルが、フル判別手段２１若しくはパーシャル判別手段２４による判別を初めて経験したものであるときには、パーシャル回収手段２５が、パーシャル判別手段２４による再度の該判別の結果に基づいて不使用のセルのヒープ１１からの回収を行なうようにすることが、本発明に関する特徴である。
【００４９】
この特徴により、アプリケーションプログラムの実行により使用が開始され、その直後にその使用が終了してしまうような、使用期間の短いセルであっても、パーシャル回収手段２５で確実に回収することができるようになり、従って、この構成により、並列型ＧＣの処理効率を向上させることが可能となる。
【００５０】
図３は、本発明の第三、第四、第五の態様の原理構成を示すブロック図である。本発明のこれらの態様は、いずれも、フル判別手段２１、フル回収手段２２、パーシャル抽出手段２３、パーシャル判別手段３１、パーシャル回収手段３２、パーシャル・マーキング・ガーベシ・コレクション制御手段２６、通知手段３３を備えて構成される。
【００５１】
同図において、アプリケーションプログラム実行部１０、ヒープ１１は図１に示したのと同様のものであり、また、フル判別手段２１、フル回収手段２２、パーシャル抽出手段２３、パーシャル・マーキング・ガーベシ・コレクション制御手段２６は図２に示したのと同様のものである。また、この図３に示す構成も、アプリケーションプログラムの実行と、セルの回収とを並行して行なうことができるので、並列型ＧＣといえる。
【００５２】
パーシャル判別手段３１は、パーシャル抽出手段２３により抽出されたセルについて、アプリケーションプログラムの実行により該セルが使用中であるか不使用であるかの判別を行なう。
【００５３】
パーシャル回収手段３２は、パーシャル判別手段３１による判別の結果に基づいて不使用のセルの前記ヒープからの回収を行なう。
通知手段３３は、本発明の第三の態様においては、アプリケーションプログラムの実行によって、ヒープ１１中における使用中のセルに格納されていた第一のポインタであって、ヒープ１１中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタを、パーシャル判別手段３１に通知する。
【００５４】
ここで、パーシャル判別手段３１は、通知手段３３により通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なうことが、この第三の態様における本発明に関する特徴である。
【００５５】
この特徴により、アプリケーションプログラムの実行により使用が開始され、その直後にその使用が終了してしまうような、使用期間の短いセルであっても、パーシャル判別手段３１により該セルの判別が確実に行なわれるようになり、不使用と判断されれば該セルがパーシャル回収手段３２によって確実に回収できるようになる。従って、この構成により、並列型ＧＣの処理効率を向上させることが可能となる。
【００５６】
また、本発明の第四の態様においては、通知手段３３は、アプリケーションプログラムの実行によって、ヒープ１１中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタの指すセルが、フル判別手段２１によって最近に行なわれたセルの使用状況の判別以後の期間に、フル判別手段２１及びパーシャル判別手段３１のいずれによる前記判別も行なわれていない場合に限り、該第一のポインタをパーシャル判別手段３１に通知する。
【００５７】
ここで、パーシャル判別手段３１は、通知手段３３により通知されたポインタの指すセルに格納されている前記第一のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なうことが、この第四の態様における本発明に関する特徴である。
【００５８】
この特徴により、アプリケーションプログラム実行部１０からパーシャル判別手段３１へ通知する情報量を減らすことができ、通知手段３３の処理負担が軽減する。従って、この構成により、並列型ＧＣの処理効率を向上させることが可能となる。
【００５９】
また、本発明の第五の態様においては、通知手段３３は、アプリケーションプログラムの実行によって、ヒープ１１中における使用中のセルに格納されていた第一のポインタであって、ヒープ１１中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタの指すセルが、フル判別手段２１によって最近に行なわれたセルの使用状況の判別以後の期間にフル判別手段２１又はパーシャル判別手段３１のいずれかによる判別が行なわれている場合に限り、該第二のポインタをパーシャル判別手段３１に通知する。
【００６０】
ここで、パーシャル判別手段３１は、通知手段３３により通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なうことが、この第五の態様における本発明に関する特徴である。
【００６１】
この特徴によっても、アプリケーションプログラム実行部１０からパーシャル判別手段３１へ通知する情報量を減らすことができ、通知手段３３の処理負担が軽減する。従って、この構成により、並列型ＧＣの処理効率を向上させることが可能となる。
【００６２】
以上のように、本発明のいずれの態様によっても並列型ＧＣの処理効率を向上させることができる。
なお、上述した本発明の各態様の構成により行なわれる機能と同様の制御をコンピュータに行なわせるメモリ管理プログラムをコンピュータに実行させることによって、若しくはそのメモリ管理プログラムを記憶したコンピュータ読み取り可能な記憶媒体から、そのプログラムをコンピュータに読み出させて実行させることによっても、前述した課題を解決することができる。
【００６３】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて説明する。
図４は、本発明を実施する装置（以下、「本装置」という）の構成を示す図である。同図において、プログラム実行部１０１、メモリ管理部１０２、ＲＡＭ１０３は、バス１０４を介して相互に接続されている。
【００６４】
プログラム実行部１０１は、本装置外部から入力されるアプリケーションプログラムを実行するものであり、前述したＧＣの説明におけるミューテータに相当するものである。
【００６５】
メモリ管理部１０２は、ミューテータ１０１がアプリケーションプログラムを実行するために使用するＲＡＭ１０３の使用状況を管理し、ＧＣの処理を実行するものであり、前述したＧＣの説明におけるコレクタに相当するものである。
【００６６】
ＲＡＭ１０３は、プログラム実行部１０１がアプリケーションプログラムを実行するための作業用メモリとして使用されるランダム・アクセス・メモリであり、メモリ管理部１０２によって、管理され、そしてＧＣの処理が施される。
【００６７】
プログラム実行部１０１は、ＣＰＵ１１１、ＲＯＭ１１２、入力部１１３、出力部１１４を有しており、バス１１５によって相互に接続されている。
ＣＰＵ１１１は、プログラム実行部１０１を制御すると共に、入力部１１３に入力されたアプリケーションプログラムを、ＲＡＭ１０３をワークエリアとして使用しながら実行する中央演算処理装置である。
【００６８】
ＲＯＭ１１２は、ＣＰＵ１１１がプログラム実行部１０１を制御するための基本制御プログラムが格納されているリード・オンリ・メモリである。
入力部１１３は、キーボードやマウス、フロッピーディスクやＣＤ−ＲＯＭなどといった可搬型記憶媒体からデータを読み取る読み取り装置、他のコンピュータとの間でデータを授受するインタフェース装置、などで構成され、アプリケーションプログラムの入力のために用いられる。
【００６９】
出力部１１４は、表示装置やプリンタ装置、他のコンピュータとの間でデータを授受するインタフェース装置、などで構成され、アプリケーションプログラムの実行結果が出力される。
【００７０】
メモリ管理部１０２は、ＣＰＵ１２１、ＲＯＭ１２２、ＲＡＭ１２３を有しており、バス１２４によって相互に接続されている。
ＣＰＵ１２１は、プログラム実行部１０１に使用されるＲＡＭ１０３を管理し、ＲＯＭ１２２に格納されているＧＣプログラムを実行することによってＲＡＭ１０３の記憶領域に対してＧＣを行なう中央演算処理装置である。
【００７１】
ＲＯＭ１２２は、ＣＰＵ１２１がＲＡＭ１０３にＧＣを施すためのＧＣプログラムが格納されている。
ＲＡＭ１２３は、ＣＰＵ１２１によるＧＣプログラムの実行のために利用されるワークメモリである。
【００７２】
次に、図５に示すＲＡＭ１０３の記憶領域の構成について説明する。
レジスタファイル１３１は、プログラム実行部１０１のＣＰＵ１１１で使用されているレジスタに格納されているヒープ１３３へのポインタの値が格納されているファイルである。
【００７３】
実行スタック１３２は、プログラム実行部１０１のＣＰＵ１１１で使用されているスタックであって、ヒープ１３３へのポインタの値が格納されているものである。
【００７４】
本装置においては、レジスタファイル１３１及び実行スタック１３２に格納されるヒープ１３３へのポインタが、ＧＣにおけるルートとなる。
ヒープ１３３は、プログラム実行部１０１によって利用され、メモリ管理部１０２によってＧＣが施されるメモリ領域である。ヒープ１３３は複数のセルにより構成されている。
【００７５】
ここで、ヒープ１３３中のセルの構造について説明する。セルは、一般に１個以上のポインタフィールドを有する。なお、ここでは、セルは２つのフィールド（car, cdr）を有するものとしている。また、このセルは、カラーフィールドを有している。ポインタフィールドにはそのセルに繋がるセルを指すポインタが格納される。また、カラーフィールドにはそのセルに付される印の色が示される。詳細は後述するが、本実施の形態において、カラーフィールドに付される印の色には、白（white）、黒（black ）、白灰色（off-white ）の３色が原則として用いられる。
【００７６】
フリーリスト１３４は、ヒープ１３３中のセルのうち、使用されていないものを示すものである。
ＲＡＭ１０３において、セルのうちの使用されていないものは、ポインタフィールドcdr を利用して１本のリストを構成するようにしている。全ての不使用セルは、そのポインタフィールドcarにｆなる特殊な値が格納され、更にそのセルのカラーフィールドが白灰色（off-white ）に設定される。白灰色の印付けについては後に更に説明する。
【００７７】
フリーリスト１３４において、フィールドFREE.left には、不使用セルからなるリストの先頭のセルを指すポインタが、また、フィールドFREE.rightには不使用セルからなるリストの最後尾のセルを指すポインタが示されている。
【００７８】
ＧＣスタック１３５は、ＧＣの処理におけるマークフェーズの処理において、セルのうちの印付けを行なう必要のあるものを指すポインタが格納される。このＧＣスタック１３５に格納されたポインタが指しているセルは、その後確実に印付けのための判断が施される。なお、このようなセルは、前述したon-the-fly  ＧＣやスナップショットＧＣにおいては、暗黒色（dark）の印付けがなされたとみなされるセルである。
【００７９】
次に、図４に示す本装置で行なわれるＧＣについて説明する。
本実施の形態では、並列型ＧＣのひとつであるパーシャル・マーキングＧＣ（Partial Marking garbage collection：以下、「ＰＭＧＣ」と略す。）を採用している。そこで、まず、ＰＭＧＣの概要について説明する。なお、ＰＭＧＣについては、部分印付けを併用した並列ＧＣの提案および効率の解析,田中良夫, 松井祥悟, 前田敦司, 中西正和, 電子情報通信学会論文誌（Ｄ−Ｉ）, Vol.J78-D-I, No.12, pp.926-935, Dec.1995 、に詳細に説明されている。
【００８０】
ＧＣの研究において、セルがヒープ中で割り当てられてからの時間（この時間は、「セルの年齢」などと呼ばれている）を観察すると、その年齢の若いセルほど生存時間が短くて「ごみ」となりやすい傾向があり、また、それでも生き残ったセルは長期間に渡って生き残る傾向のあることが広く知られている。つまり、「ごみ」として回収できるセルは、ごく最近にヒープ中で割り当てられたものが多いのである。
【００８１】
このことを考えると、前述したスナップショットＧＣにおいてＧＣの１サイクルの途中で「ごみ」となった生存時間の短かったセルが直ちに回収されないことは、ＧＣの回収効率の低下を招いてしまっていることが考えられる。
【００８２】
ＰＭＧＣはこの点に注目したＧＣである。ＰＭＧＣは、ヒープ全体に対してセル回収の処理を行なうフルＧＣ（full  ＧＣ）のサイクルと、直前のＧＣサイクルの間にヒープ中に割り当てられたセルのみを対象としてセル回収の処理を行なうパーシャルＧＣ（partialＧＣ）のサイクルとを交互に行なうようにしたものである。パーシャルＧＣのサイクルにおいては、そのサイクルで行なわれる印付けの対象がヒープ中の一部のセルのみとなるので、スナップショットＧＣのマークフェーズに比べて処理量が少なくて済む。従って、ＰＭＧＣはスナップショットＧＣよりもＧＣの処理効率の向上が期待できる。
【００８３】
前述したように、ＰＭＧＣにおいては、セルに白（white ）、黒（black ）、白灰色（off-white）の３色の印付けが行なわれる（ここでは、セルを指すポインタのＧＣスタック１３５への代入を示す暗黒色の印付けは除外して説明する）。セルに対する白及び黒の印付けの意味は、前述したon-the-fly  ＧＣやスナップショットＧＣと同様に、白が「ごみ」とみなし得るセル、黒が「ごみ」とみなすことのできないセルであり、ＰＭＧＣのスイープフェーズにおいても白の印付けがなされているセルのみを回収する。また、白灰色の印付けがなされているセルは、前述したように、そのＧＣサイクルの開始時点においては使用されていなかったセルであり、このセルがプログラム実行部により使用された場合には、後述するような特別な処理を行なう必要がある。
【００８４】
図６は、ＲＯＭ１２２に格納されているＧＣプログラムをＣＰＵ１２１が実行することによって行なわれる、ＰＭＧＣの基本的な処理のアルゴリズムを示す図である。なお、図６以降の各図では、各アルゴリズムをフローチャートで示すと共にＣ言語風のプログラムで併記し、そのアルゴリズムの理解の助けとなるようにしている。
同図において、Ｓ１０１からＳ１０６にかけての処理がフルＧＣサイクルの処理であり、Ｓ１０６からＳ１１２にかけての処理がパーシャルＧＣのサイクルの処理である。
【００８５】
Ｓ１０１では、フラグＣＹＣＬＥに「ＦＵＬＬ」がセットされることによって、このステップ以降の処理がフルＧＣサイクルの処理であることが示される。更に、フラグＰＨＡＳＥに「ＲＯＯＴＩＮＳ」がセットされることによってこのステップ以降の処理がルート挿入フェーズであることが示される。
【００８６】
Ｓ１０２では、ルート挿入フェーズ処理が実行される。この処理の詳細は次に説明する。
Ｓ１０３では、フラグＰＨＡＳＥに「ＭＡＲＫＩＮＧ」がセットされることによって、このステップ以降の処理がマークフェーズであることが示され、続くＳ１０４ではマークフェーズ処理が実行される。マークフェーズ処理の詳細も後述する。
【００８７】
Ｓ１０５では、フラグＰＨＡＳＥに「ＳＷＥＥＰ」がセットされることによって、このステップ以降の処理がスイープフェーズであることが示され、続くＳ１０６ではスイープ・リーブマーク処理が実行される。スイープ・リーブマーク処理の詳細も後述する。
【００８８】
Ｓ１０７では、フラグＣＹＣＬＥに「ＰＡＲＴＩＡＬ」がセットされることによって、このステップ以降の処理がパーシャルＧＣサイクルの処理であることが示され、更に、フラグＰＨＡＳＥに「ＲＯＯＴＩＮＳ」がセットされることによって、このステップ以降の処理がルート挿入フェーズであることが示される。
【００８９】
Ｓ１０８では、ルート挿入フェーズ処理が実行される。
Ｓ１０９では、フラグＰＨＡＳＥに「ＭＡＲＫＩＮＧ」がセットされることによって、このステップ以降の処理がマークフェーズであることが示され、続くＳ１１０ではマークフェーズ処理が実行される。
【００９０】
Ｓ１１１では、フラグＰＨＡＳＥに「ＳＷＥＥＰ」がセットされることによって、このステップ以降の処理がスイープフェーズであることが示され、続くＳ１１２ではスイープ・クリアマーク処理が実行される。スイープ・クリアマーク処理の詳細も後述する。
【００９１】
Ｓ１１２の処理を終えた後にはＳ１０１へ戻り、上述した処理が繰り返される。
以上の処理をメモリ管理部１０２のＣＰＵ１２１が行なうことによって、ＲＡＭ１０３のヒープ１３３に対するＧＣが行なわれる。
【００９２】
次に、図６に示したアルゴリズム中の各処理ステップにおいて実行される処理の詳細について説明する。
図７は、図６のＳ１０２及びＳ１０８に示されているルート挿入フェーズ処理のアルゴリズムを示す図である。
【００９３】
図７のＳ１２１において、全てのルート中のデータ、すなわち、レジスタファイル１３１及び実行スタック１３２に格納されているセルへのポインタがＧＣスタック１３５に格納される。この処理の後にはルート挿入フェーズ処理を終了し、元の処理へ戻る。
【００９４】
次に、図６のＳ１０４及びＳ１１０に示されているマークフェーズ処理について、そのアルゴリズムを示す図８を参照しながら説明する。
まず、Ｓ１４１において、ＧＣスタック１３５が空であるか否かを判定し、この判定結果がＹｅｓならばマークフェーズ処理を終了する。一方、この判定結果がＮｏならばＳ１４２に進む。
【００９５】
Ｓ１４２では、ＧＣスタック１３５からその先頭に格納されているポインタをひとつ取り出して変数ｎに代入する。
Ｓ１４３では、変数ｎに代入されているポインタが指しているセルについて、（１）そのセルの内容がＮＩＬである（値が空である）か、（２）そのセルが使用されていないか、または、（３）そのセルのカラーフィールドに黒の印が付されているかどうかを判定する。この（１）から（３）までのうち、ひとつでもＹｅｓならばＳ１４１へ戻って上述した処理を繰り返す。
【００９６】
一方、Ｓ１４３の判定処理の結果がＮｏならば、Ｓ１４４において、変数ｎの指すセルのカラーフィールドを黒に変更し、このセルが使用されていることを示す。そして、このセルのポインタフィールドcdr に格納されているポインタをＧＣスタック１３５に格納してそのポインタが指すセルに対して印付け処理が後に行なわれるようにする。更に、変数ｎの指すセルのポインタフィールドcarに格納されているポインタを変数ｎに代入し、その後はＳ１４３へ戻って上述した処理を繰り返す。
【００９７】
以上までの処理がマークフェーズ処理である。
次に、図６のＳ１０６に示されているスイープ・リーブマーク処理について、そのアルゴリズムを示す図９を参照しながら説明する。この処理はＰＭＧＣがフルＧＣサイクルのときのスイープフェーズとして行なわれる処理である。
【００９８】
まず、Ｓ１６１において、セルのうち、ヒープ１３３中の先頭に位置しているものを指すポインタを変数ｉに設定する。
Ｓ１６２では、変数ｉの指すセルのカラーフィールドが白であるか否か、すなわち、そのセルが回収可能であるか否かを判定し、判定結果がＹｅｓならばＳ１６３に進み、ＮｏならばＳ１６４に進む。
【００９９】
Ｓ１６３では、フリーリスト追加処理が実行される。フリーリスト追加処理の詳細を図１０に示す。この処理は、Ｓ１７１において、変数ｉの指すセルを不使用セルとして管理するために、カラーフィールドを白灰色にすると共にポインタフィールドcar にポインタｆを格納する。更にフリーリスト１３４を更新してこのセルを不使用セルのリストに接続する処理である。
【０１００】
Ｓ１６３の処理を終えた後にはＳ１６６に進む。
Ｓ１６４では、変数ｉの指すセルが、フリーリスト１３４で示されている不使用セルに該当せず、且つ、そのセルのカラーフィールドが白灰色のものについてのみ、Ｓ１６５においてそのセルのカラーフィールドを白に変更する。このＳ１６４の判定処理と前述したＳ１６２の判定処理とを組み合わせて考えれば、ここでは、カラーフィールドが黒にされているセルについては、その黒印をそのまま維持する処理となる。黒印が維持されたセルは、図６のＳ１１０において図８に示したマークフェーズ処理が実行されるときに、セルの印付けの対象を減少させる効果をもたらすことになる。
【０１０１】
Ｓ１６６では、変数ｉの指すセルに続くセルがヒープ１３３に存在するか否かを判定し、判定結果がＹｅｓならばＳ１６７に進み、その続きのセルを指すポインタを変数ｉに代入した後にＳ１６２へ戻って上述した処理を繰り返す。一方、Ｓ１６６の判定結果がＮｏならば、スイープ・リーブマーク処理を終了する。
【０１０２】
次に、図６のＳ１１２に示されているスイープ・クリアマーク処理について、そのアルゴリズムを示す図１１を参照しながら説明する。この処理はＰＭＧＣがパーシャルＧＣサイクルのときのスイープフェーズとして行なわれる処理である。
【０１０３】
図１１に示すフローチャートと図９に示すフローチャートとを比較すると分かるように、スイープ・クリアマーク処理におけるＳ１８１からＳ１８７にかけての処理で、スイープ・リーブマーク処理におけるＳ１６１からＳ１６７にかけての処理と異なるのはＳ１８４の処理のみである。そこで、スイープ・クリアマーク処理についてはこのステップでの処理についてのみ説明する。
【０１０４】
Ｓ１８４では、変数ｉの指すセルがフリーリスト１３４で示されている不使用セルに該当しなければ、Ｓ１８５においてそのセルのカラーフィールドを白に変更する。このＳ１８４での処理を前述したスイープ・リーブマーク処理におけるＳ１６４（図９）の処理と比較すると分かるように、Ｓ１８４では、カラーフィールドが色灰色にされているセルと共に、そこが黒色にされているセルについても、その印が白色に変更される。従って、図６のＳ１０４において図８のマークフェーズ処理が次に実行されるときには、Ｓ１８５の処理の前には黒印が付されていたセルを含む全てのセルについて、セルの印付けの要否が判定されるようになる。
【０１０５】
ＰＭＧＣにおいては、メモリ管理部１０２のＣＰＵ１２１によって上述した処理が行なわれることに加え、プログラム実行部１０１のＣＰＵ１１１によって以下に説明するポインタ置き換え処理及びセル新規使用処理が行なわれる。
【０１０６】
図１２は、ポインタ置き換え処理のアルゴリズムを示す図である。ポインタ置き換え処理は、プログラム実行部１０１がアプリケーションプログラムを実行した際に、ポインタｍが指しているヒープ１３３中のポインタを、ポインタｎに変更するときに実行される処理である。
【０１０７】
まず、Ｓ２０１において、フラグＰＨＡＳＥが「ＭＡＲＫＩＮＧ」に設定されているか否か、すなわち、ＧＣの現在の処理フェーズがマークフェーズであるか否かを判定し、判定結果がＹｅｓの場合にのみ、Ｓ２０２においてポインタｍの指しているヒープ１３３中に現在格納されているポインタをＧＣスタック１３５に格納する。この処理は前述したスナップショットＧＣにおいても必要な処理である。
【０１０８】
Ｓ２０３では、フラグＰＨＡＳＥが「ＭＡＲＫＩＮＧ」に設定されているか否かを再度判定し、判定結果がＹｅｓならばＳ２０４に進み、ＮｏならばＳ２０６に進む。
【０１０９】
Ｓ２０４では、ポインタｎの指すセルのカラーフィールドが白灰色にされているか否か、すなわち、ポインタｎの指すセルが今まで不使用であったセルであるか否かを判定し、判定結果がＹｅｓならば、Ｓ２０５において、ポインタｎをＧＣスタック１３５に格納し、メモリ管理部１０２によってポインタｎの指すセルに対する印付けの処理がいつかは必ず行なわれるようにする。この処理の後にはＳ２０９に進む。一方、Ｓ２０４の判定処理の結果がＮｏならば、何もせずにそのままＳ２０９に進む。
【０１１０】
Ｓ２０６では、フラグＰＨＡＳＥが「ＳＷＥＥＰ」に設定されているか否か、すなわち、ＧＣの現在の処理フェーズがスイープフェーズであるか否かを判定し、判定結果がＹｅｓならばＳ２０７に進み、ＮｏならばＳ２０９に進む。
【０１１１】
Ｓ２０７では、ポインタｎの指すセルのカラーフィールドが黒色にされているか否か、すなわち、ポインタｎの指すセルが「ごみ」とみなすことはできないことが直前までのマークフェーズにおいて既に判定されているか否かを判定し、判定結果がＹｅｓならば何もせずにこのままＳ２０９に進む。一方、Ｓ２０７の判定処理の結果がＮｏならば、Ｓ２０８においてポインタｎをＧＣスタック１３５に格納し、ポインタｎの指すセルに対する印付けの処理がメモリ管理部１０２によっていつかは必ず行なわれるようにする。
【０１１２】
Ｓ２０９では、ポインタｍによって指されるヒープ１３３中のポインタをポインタｎに変更し、ポインタ置き換え処理を終了する。
図１３は、セル新規使用処理のアルゴリズムを示す図である。セル新規使用処理は、プログラム実行部１０１がアプリケーションプログラムを実行した際に、ヒープ１３３中のセルを指すポインタｍとポインタｎとを格納するセルを新たに使用開始するときに実行される処理である。
【０１１３】
まず、Ｓ２２１では、フリーリスト１３４を参照し、不使用セルが得られるまで待つ。
Ｓ２２２では、不使用セルのリストからセルをひとつ取り出してＮＥＷなる名称を付し、そのセルＮＥＷのポインタフィールドcar 及びcdr にそれぞれポインタｍ、ｎを代入し、セルＮＥＷへのポインタをアプリケーションプログラムへ返す。更に、フリーリスト１３４を更新し、セルＮＥＷを不使用セルのリストから除外する。それまでは不使用であったセルＮＥＷのカラーフィールドは白灰色なので、後のマークフェーズにおいて、このＮＥＷに対する印付けの処理がいつかは必ず行なわれる。
【０１１４】
以上までの図１２及び図１３に示した処理がプログラム実行部１０１のＣＰＵ１１１により実行されることによって、アプリケーションプログラムによるヒープ１３３の利用状況の変化がメモリ管理部１０２に伝えられる。こうして図４に示す構成の本装置において、使用中のセルを「ごみ」セルと誤判断することのない、正確なＰＭＧＣが行なわれる。
【０１１５】
以上までに説明したものが基本的なＰＭＧＣである。
以降の説明は、ＰＭＧＣの改良に関するものであり、本発明に関連するものである。
【０１１６】
前述した基本的なＰＭＧＣにおいては、図６を参照すれば分かるように、フルＧＣサイクルとパーシャルＧＣサイクルとが交互に１回ずつ実行される。また、前述した文献「部分印付けを併用した並列ＧＣの提案および効率の解析」にも、１つのフルＧＣサイクルと数回のパーシャルＧＣサイクルとで１つのシーケンスが構成され、このシーケンスが繰り返されてＧＣの処理が行なわれる旨が記載されているに過ぎず、１つのシーケンス当たりでの適切なパーシャルＧＣサイクルの繰り返し回数については言及されていない。
【０１１７】
これに対して、本実施の形態では、過去のＧＣによるセルの回収の状況に応じて、次に行なうＧＣサイクルを、フルＧＣサイクルにするか、あるいはパーシャルＧＣサイクルにするか、選択制御するようにした。この制御によって、現在のＧＣの状況に応じた適切なＧＣサイクルが選択されるのでＰＭＧＣ全体の処理効率を更に向上させることができる。本実施の形態では、この制御を「フル・パーシャル制御」と呼ぶこととする。
【０１１８】
ここでは、フル・パーシャル制御について、次に行なうＧＣサイクルを選択制御するために用いる情報の違いによる幾つかの実施例を示す。なお、これらの実施例はいずれも図４に示した本装置で動作させる。
【０１１９】
まず、処理効率を向上させたＰＭＧＣの第一の実施例について説明する。この第一の実施例では、前回のＧＣによってヒープ１３３から回収された不使用セルの回収量を求め、この回収量に応じて今回のＧＣサイクルを選択する。もしもその回収量が所定量に満たない場合には、例え今回のＧＣサイクルでパーシャルＧＣサイクルを実行しても不使用セルの回収量はわずかしか期待できず、すぐに次のＧＣサイクルを実行しなければならなくなるものと判断し、今回のＧＣサイクルとしてフルＧＣサイクルを実行する。一方、不使用セルの回収量が所定量以上である場合には、今回のＧＣサイクルでパーシャルＧＣサイクルを実行してもある程度の量の不使用セルの回収が期待できると判断し、今回のＧＣサイクルとしてパーシャルＧＣサイクルを実行する。
【０１２０】
この第一の実施例においては、後述するパーシャルＧＣサイクル処理及びフルＧＣサイクル処理をメモリ管理部１０２のＣＰＵ１２１が行なう際に、それらの処理内容に応じ、先に図７に示したルート挿入フェーズ処理、図８に示したマークフェーズ処理、図９に示したスイープ・リーブマーク処理の各アルゴリズムが実行される。但し、スイープ・リーブマーク処理が実行されるときには、図９に示したスイープ・リーブマーク処理ではＳ１６３において実行されるフリーリスト追加処理が図１０に示されていたアルゴリズムから変更されて実行される。変更されたフリーリスト追加処理のアルゴリズムを図１４に示す。
【０１２１】
図１４において、Ｓ３０１として示されている処理は図１０においてＳ１７１として示されている処理と同一である。
Ｓ３０１に続くＳ３０２において、変数ＮＯ＿ＦＲＥＥの値が１だけ増加させられる。変数ＮＯ＿ＦＲＥＥは、１回のＧＣサイクルで回収される不使用のセルのリストの個数を勘定するカウンタとして用いられている。つまり、このステップで行なわれる処理は、前ステップにおいて不使用のセルが不使用セルのリストにひとつ追加されたことに対応させるべく、変数ＮＯ＿ＦＲＥＥの値を１だけ増加させたものである。この処理の後、フリーリスト追加処理を終了する。
【０１２２】
次に図１５について説明する。同図は、この第一の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
まず、Ｓ３２１において、変数ＮＯ＿ＦＲＥＥの値が、定数ＴＨＲＥＳＨＯＬＤ＿ＦＲＥＥの値よりも小さいか否かが判定される。定数ＴＨＲＥＳＨＯＬＤ＿ＦＲＥＥの値は、ヒープ１３３の大きさやアプリケーションプログラムの消費するヒープ１３３の量、図４に示した本装置の処理速度などが勘案されて決定される。この判定結果がＹｅｓならばＳ３２２に進み、ＮｏならばＳ３２４に進む。
【０１２３】
Ｓ３２２では変数ＮＯ＿ＦＲＥＥに０が代入され、続くＳ３２３でパーシャルＧＣサイクル処理が実行される。この処理の後にはフル・パーシャル制御処理を終了する。
【０１２４】
パーシャルＧＣサイクル処理のアルゴリズムを図１６に示す。図１６のＳ３４１からＳ３４５にかけての処理は、図６のＳ１０７からＳ１１１にかけての処理と全く同様である。そして、図１６のＳ３４６では、図６のＳ１１２とは異なり、図９にアルゴリズムを示したスイープ・リーブマーク処理が実行され、その後パーシャルＧＣサイクル処理を終了して元の処理へ戻る。
【０１２５】
図１５の説明に戻る。Ｓ３２４では変数ＮＯ＿ＦＲＥＥに０が代入され、続くＳ３２５でフルＧＣサイクル処理が実行される。この処理の後にはフル・パーシャル制御処理を終了する。
【０１２６】
フルＧＣサイクル処理のアルゴリズムを図１７に示す。図１７のＳ３６１からＳ３６７にかけての処理は、クリアマーク処理を実行するステップがＳ３６１とＳ３６３との間にＳ３６２として挿入されていることを除けば、図６のＳ１０１からＳ１０６にかけての処理と同様である。
【０１２７】
クリアマーク処理のアルゴリズムを図１８に示す。クリアマーク処理は、ヒープ１３３中の全てのセルのカラーフィールドを白に戻す処理である。
まず、Ｓ３８１において、セルのうち、ヒープ１３３中の先頭に位置しているものを指すポインタを変数ｉに設定する。
【０１２８】
Ｓ３８２では、変数ｉの指すセルがフリーリストに入っているか否かを判定しし、判定結果がＹｅｓの場合にのみ、Ｓ３８３において、そのセルのカラーフィールドを白に変更する。
【０１２９】
Ｓ３８４では、変数ｉの指すセルに続くセルがヒープ１３３に存在するか否かを判定し、判定結果がＹｅｓならばＳ３８５に進み、その続きのセルを指すポインタを変数ｉに代入した後にＳ３８２へ戻って上述した処理を繰り返す。一方、Ｓ３８４の判定結果がＮｏならば、クリアマーク処理を終了して元の処理へ戻る。
【０１３０】
メモリ管理部１０２のＣＰＵ１１２が図１５に示した処理を実行することでフル・パーシャル制御処理の１シーケンスが終了する。この第一の実施例ではこのフル・パーシャル制御処理のシーケンスがＣＰＵ１１２により繰り返し実行され、各シーケンスごとに適切なＧＣサイクルが選択されて実行される。
【０１３１】
なお、この第一の実施例において、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１２に示したポインタ置き換え処理及び図１３に示したセル新規使用処理を実行する。
【０１３２】
次に、処理効率を向上させたＰＭＧＣの第二の実施例について説明する。
前述したように、パーシャルＧＣサイクルは、その直前のＧＣサイクルで使用が開始されたセルのみを対象としてセルの回収を行なうものである。そこで、この第二の実施例では、直前のＧＣサイクルで使用が開始されたセルの量と比べてパーシャルＧＣサイクルで回収されたセルの量が所定量以下の少なさならば、プログラム実行部１０１で実行されているアプリケーションプログラムのヒープ利用の性質が、パーシャルＧＣサイクルによるセルの回収には不向きである、セルを長い時間生存させる傾向を有していると判断し、次回のＧＣサイクルではフルＧＣサイクルを選択する。そして、その他のときにはパーシャルＧＣサイクルを選択する。
【０１３３】
この第二の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１２に示したポインタ置き換え処理を実行するが、セル新規使用処理は図１３に示したアルゴリズムの代わりに図１９に示したアルゴリズムに沿った処理を実行する。
【０１３４】
図１９において、Ｓ４０１及びＳ４０２として示されている処理は図１３においてＳ２２１及びＳ２２２として示されている処理と同一である。
Ｓ４０２に続くＳ４０３では、フラグＣＹＣＬＥに「ＰＡＲＴＩＡＬ」がセットされているか否か、すなわち、現在メモリ管理部１０２によって行なわれているＧＣのサイクルがパーシャルＧＣサイクルであるか否かが判定され、判定結果がＹｅｓのときにのみ、Ｓ４０４において、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥの値が１だけ増加させられる。変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥは、プログラム実行部１０１によって新規に使用が開始されたヒープ１３３中のセルの個数を勘定するカウンタとして用いられている。
【０１３５】
Ｓ４０４の処理を終えた後にはこのセル新規使用処理を終了する。また、Ｓ４０３の判定処理の結果がＮｏであるときもこのセル新規使用処理を終了する。
この第二の実施例においては、後述するこの第二の実施例におけるフル・パーシャル制御処理のアルゴリズムに沿った処理をメモリ管理部１０２のＣＰＵ１２１が行なう際に、そのアルゴリズムに応じ、図１６に示したパーシャルＧＣサイクル処理、及び図１７に示したフルＧＣサイクル処理の両アルゴリズムが実行される。但し、そのときには、図１６に示したパーシャルＧＣサイクル処理のＳ３４６、及び図１７に示したフルＧＣサイクル処理のＳ３６７において実行されるスイープ・リーブマーク処理が図９に示されていたものから変更されて実行される。変更されたスイープ・リーブマーク処理のアルゴリズムを図２０に示す。
【０１３６】
図２０のＳ４２１からＳ４２８にかけての処理は、Ｓ４２４として示されている処理ステップがＳ４２３とＳ４２７との間に挿入されていることを除けば、図９のＳ１６１からＳ１６７にかけての処理と同様である。
【０１３７】
図２０において、Ｓ４２３に続くＳ４２４では、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＲＥＣＬＡＩＭの値が１だけ増加させられ、その後はＳ４２７に進む。変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＲＥＣＬＡＩＭは、パーシャルＧＣサイクルの１サイクルによって回収されたヒープ１３３中の不使用セルの個数が設定されるものであるが、ここではこのスイープ・リーブマーク処理の今回の実行によって回収された不使用セルの個数を勘定するカウンタとして用いられている。
【０１３８】
次に、図２１について説明する。図２１は、この第二の実施例におけるフル・パーシャル制御処理のアルゴリズムを示している。
図２１において、Ｓ４４１では、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＲＥＣＬＡＩＭの値が、変数ＮＯ＿ＰＲＥＶＩＯＵＳ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥと定数Ａとの乗算結果よりも小さいか否かを判定し、判定結果がＹｅｓならばＳ４４２に、ＮｏならばＳ４４４に、それぞれ進む。ここで、変数ＮＯ＿ＰＲＥＶＩＯＵＳ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥは、後述するＳ４４４の処理によって、前回のＧＣサイクルがパーシャルＧＣサイクルである場合において、そのパーシャルＧＣサイクルの処理を実行している期間にプログラム実行部１０１によって新規に使用が開始されたヒープ１３３中のセルの個数が設定される。また、定数Ａは、ヒープ１３３中のセルの新規利用量とパーシャルＧＣサイクルによる不使用セルの回収量との比に応じて次に行なうＧＣサイクルを決定するための基準を定める定数であり、ヒープ１３３の大きさや図４に示した本装置の処理速度などが勘案されて決定される。
【０１３９】
Ｓ４４２では図１７に示したフルＧＣサイクル処理が実行される。
Ｓ４４３では、直前にフルＧＣサイクルが実行されたため、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＲＥＣＬＡＩＭ及び変数ＮＯ＿ＰＲＥＶＩＯＵＳ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥには共に０が代入され、その後はこのフル・パーシャル制御処理を終了する。
【０１４０】
Ｓ４４４では、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥの現在の値がＮＯ＿ＰＲＥＶＩＯＵＳ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥに代入される。そして、その後、変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＲＥＣＬＡＩＭ及び変数ＮＯ＿ＰＡＲＴＩＡＬ＿ＡＬＬＯＣＡＴＥに共に０が代入される。
【０１４１】
Ｓ４４５では、図１６に示したパーシャルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
メモリ管理部１０２のＣＰＵ１１２がこの図２１に示した処理を実行することでこのフル・パーシャル制御処理の１シーケンスが終了する。この第二実施例ではＣＰＵ１１２によりこのフル・パーシャル制御処理のシーケンスが繰り返し実行され、各シーケンスごとに適切なＧＣサイクルが選択されて実行される。
【０１４２】
次に、処理効率を向上させたＰＭＧＣの第三の実施例について説明する。
前述した基本的なＰＭＧＣにおいて、プログラム実行部１０１のＣＰＵ１１１によって行なわれる、図１２に示したポインタ置き換え処理について考える。
【０１４３】
図１２にＳ２０５及びＳ２０８として示されている処理ステップは、ＰＭＧＣにおいて、プログラム実行部１０１で実行されるアプリケーションプログラムの処理によってヒープ１３３のセルに含まれているポインタが置き換えられた場合に、置き換えられたポインタｎの指すセルについての印付けの処理が確実に行なわれるようにするために、ポインタｎをＧＣスタック１３５に格納する処理である。ところがアプリケーションプログラムによってはこのポインタの置き換えが大量に発生することがある。この場合にはＲＡＭ１０３の記憶領域が大量にＧＣスタック１３５として消費されてしまい、メモリ資源が圧迫を受ける。また、このような場合では例えパーシャルＧＣサイクルを実行したとしてもかなりの処理量となってしまう。そこで、このような場合には、パーシャルＧＣサイクルの実行による利点は少ないと判断し、次回のＧＣサイクルとしてフルＧＣサイクルを実行する。つまり、アプリケーションプログラムによるポインタの置き換えの量に応じて次回のＧＣサイクルを選択するものが、この第三の実施例におけるフル・パーシャル制御処理の意図する制御である。
【０１４４】
この第三の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１３に示したセル新規使用処理を実行するが、ポインタ置き換え処理は図１２に示したアルゴリズムの代わりに図２２に示したアルゴリズムに沿った処理を実行する。
【０１４５】
図２２において、Ｓ５０１では、フラグＰＨＡＳＥが「ＭＡＲＫＩＮＧ」に設定されているか否か、すなわち、ＧＣの現在の処理フェーズがマークフェーズであるか否かを判定し、判定結果がＹｅｓの場合にのみ、Ｓ５０２においてポインタｍの指しているヒープ１３３中に現在格納されているポインタをＧＣスタック１３５に格納する。
【０１４６】
Ｓ５０３では、フラグＰＨＡＳＥが「ＭＡＲＫＩＮＧ」に設定されているか否かを再度判定し、判定結果がＹｅｓならばＳ５０４に進み、ＮｏならばＳ５０６に進む。
【０１４７】
Ｓ５０４では、ポインタｎの指すセルのカラーフィールドが白灰色にされているか否か、すなわち、ポインタｎの指すセルが今まで不使用であったセルであるか否かを判定し、判定結果がＹｅｓならば、Ｓ５０５において、ポインタｎをＧＣスタック１３５に格納し、更に、変数ＮＯ＿ＲＥＭＥＭＢＥＲの値を１だけ増加させる。この処理の後にはＳ５０９に進む。一方、Ｓ５０４の判定処理の結果がＮｏならば、何もせずにそのままＳ５０９に進む。ここで、変数ＮＯ＿ＲＥＭＥＭＢＥＲは、プログラム実行部１０１で実行されるアプリケーションプログラムの処理によって置き換えられたポインタｎであって、ＧＣスタック１３５に格納されたものの個数を勘定するカウンタとして用いられている。
【０１４８】
Ｓ５０６では、フラグＰＨＡＳＥが「ＳＷＥＥＰ」に設定されているか否か、すなわち、ＧＣの現在の処理フェーズがスイープフェーズであるか否かを判定し、を判定し、判定結果がＹｅｓならばＳ５０７に進み、ＮｏならばＳ５０９に進む。
【０１４９】
Ｓ５０７では、変数ＮＯ＿ＲＥＭＥＭＢＥＲの値が定数ＴＨＲＥＳＨＯＬＤ＿ＲＥＭＥＭＢＥＲ以下であり、且つ、ポインタｎの指すセルのカラーフィールドが黒色にされているか否かを判定する。定数ＴＨＲＥＳＨＯＬＤ＿ＲＥＭＥＭＢＥＲは、ＧＣスタック１３５に格納するポインタｎの許容量を示す値であり、メモリ１０３の容量やＧＣスタック１３５の許容量などを勘案して設定される。なお、このステップの処理において変数ＮＯ＿ＲＥＭＥＭＢＥＲの値と定数ＴＨＲＥＳＨＯＬＤ＿ＲＥＭＥＭＢＥＲの値との大小判定を行ない、その判定結果に応じて、次のＳ５０７の処理の実行を制御している。これは、次回のＧＣサイクルにおいてフルＧＣサイクルが実行されることが確定しているのであれば、ポインタｎをＧＣスタック１３５に格納する処理を省くことができる（その後のフルＧＣサイクルでは、全てのセルに対して改めて印付けの処理が行なわれる）からであり、この制御により、メモリ資源が節約され、ＧＣのためのプログラム実行部１０１による処理量も削減することができる。
【０１５０】
Ｓ５０７の判定結果がＹｅｓならば何もせずにこのままＳ５０９に進み、その判定結果がＮｏならば、Ｓ５０８においてポインタｎをＧＣスタック１３５に格納し、更に、変数ＮＯ＿ＲＥＭＥＭＢＥＲの値を１だけ増加させる。
【０１５１】
Ｓ５０９では、ポインタｍによって指されるヒープ１３３中のポインタをポインタｎに変更し、ポインタ置き換え処理を終了する。
次に図２３について説明する。図２３は、この第三の実施例におけるフル・パーシャル制御処理のアルゴリズムを示している。
【０１５２】
図２３において、Ｓ５２１では、変数ＮＯ＿ＲＥＭＥＭＢＥＲの値が定数ＴＨＲＥＳＨＯＬＤ＿ＲＥＭＥＭＢＥＲの値よりも大きいか否かが判定され、判定結果がＹｅｓならばＳ５２２に、ＮｏならばＳ５２４に、それぞれ進む。
【０１５３】
Ｓ５２２では変数ＮＯ＿ＲＥＭＥＭＢＥＲに０が代入される。
Ｓ５２３では図１７に示したフルＧＣサイクル処理が実行される。
Ｓ５２４では変数ＮＯ＿ＲＥＭＥＭＢＥＲに０が代入される。
【０１５４】
Ｓ５２５では、図１６に示したパーシャルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
メモリ管理部１０２のＣＰＵ１１２がこの図２３に示した処理を実行することでこのフル・パーシャル制御処理の１シーケンスが終了する。この第三実施例では、ＣＰＵ１１２によりこのフル・パーシャル制御処理のシーケンスが繰り返し実行され、各シーケンスごとに適切なＧＣサイクルが選択されて実行される。
【０１５５】
次に、処理効率を向上させたＰＭＧＣの第四の実施例について説明する。この第四の実施例においては、前述した第三の実施例でも求めていた変数ＮＯ＿ＲＥＭＥＭＢＥＲの値、すなわちプログラム実行部１０１で実行されるアプリケーションプログラムの処理によって置き換えられたポインタｎであってＧＣスタック１３５に格納されたものの個数と共に、カラーフィールドが黒とされているヒープ１３３中のセルの個数を求める。パーシャルＧＣサイクルはカラーフィールドが黒でないセルを回収の対象とするのであるから、カラーフィールドが黒のセルの個数が少ないほどセル回収の処理量は多くなる。また、ＧＣスタック１３５に格納されたポインタｎの個数が多いほどパーシャルＧＣサイクルにおけるセル回収の処理量は多くなる。そこで、この両者の個数の比がある所定値から外れた場合には、パーシャルＧＣサイクルの処理量は特に多くなるためパーシャルＧＣサイクルの実行によるメリットは少ないと判断し、フルＧＣサイクルを行なうようにしたものがこの第四の実施例である。
【０１５６】
この第四の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、セル新規使用処理については図１３に示したアルゴリズムを実行し、ポインタ置き換え処理については図２２に示した第三の実施例のアルゴリズムに沿った処理を実行する。
【０１５７】
また、この第四の実施例においては、後述する第四の実施例におけるフル・パーシャル制御処理のアルゴリズムに沿った処理をメモリ管理部１０２のＣＰＵ１２１が行なう際に、そのアルゴリズムに応じ、図１６に示したパーシャルＧＣサイクル処理、及び図１７に示したフルＧＣサイクル処理の両アルゴリズムが実行される。但し、そのときには、図１６に示したパーシャルＧＣサイクル処理のＳ３４６、及び図１７に示したフルＧＣサイクル処理のＳ３６７において実行されるスイープ・リーブマーク処理が図９に示されていたものから変更されて実行される。変更されたスイープ・リーブマーク処理のアルゴリズムを図２４に示す。
【０１５８】
図２４のＳ６０１からＳ６０８にかけての処理は、Ｓ６０６として示されている処理ステップがＳ６０４とＳ６０６との間に挿入されていることを除けば、図９のＳ１６１からＳ１６７にかけての処理と同様である。
【０１５９】
図２４において、Ｓ６０２及びＳ６０４の判定処理の結果がいずれもＮｏの場合には、Ｓ６０６において、変数ＮＯ＿ＢＬＡＣＫの値を１だけ増加させる。この処理により、変数ＮＯ＿ＢＬＡＣＫは、ヒープ１３３中において、カラーフィールドが黒にされているセルの個数を勘定するカウンタとして機能する。
【０１６０】
Ｓ６０６の処理の後にＳ６０７に進む。
次に図２５について説明する。図２５はこの第四実施例におけるフル・パーシャル制御処理のアルゴリズムを示している。
【０１６１】
図２５において、Ｓ６２１では、変数ＮＯ＿ＲＥＭＥＭＢＥＲの値が変数ＮＯ＿ＢＬＡＣＫの値と定数Ｂとの乗算結果よりも大きいか否かが判定され、判定結果がＹｅｓならばＳ６２２に、ＮｏならばＳ６２４に、それぞれ進む。定数Ｂは、第四実施例におけるＧＣサイクル選択の判定条件の基準を決定するものであり、ヒープ１３３の大きさやＧＣ処理の速度などが勘案されて決定される。
【０１６２】
Ｓ６２２では変数ＮＯ＿ＲＥＭＥＭＢＥＲ及び変数ＮＯ＿ＢＬＡＣＫにそれぞれ０が代入される。
Ｓ６２３では図１７に示したフルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
【０１６３】
Ｓ６２４では変数ＮＯ＿ＲＥＭＥＭＢＥＲに０が代入される。
Ｓ６２５では、図１６に示したパーシャルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
【０１６４】
メモリ管理部１０２のＣＰＵ１１２がこの図２５に示した処理を実行することでこのフル・パーシャル制御処理の１シーケンスが終了する。この第四実施例ではＣＰＵ１１２によりこのフル・パーシャル制御処理のシーケンスが繰り返し実行され、各シーケンスごとに適切なＧＣサイクルが選択されて実行される。
【０１６５】
次に、処理効率を向上させたＰＭＧＣの第五の実施例について説明する。
プログラム実行部１０１で実行されるアプリケーションプログラムによっては、その処理の途中でヒープ１３３の利用状況が大きく変化する場合がある。例えば画像データの処理プログラムにおいて、処理対象である画像データが他のものに切り替わる場合などが、このようなアプリケーションプログラムの例として挙げることができる。ヒープ１３３の利用状況が変化したときには「ごみ」となるセルが大量に発生することが多くなり、セル回収の処理量が多くなるので、パーシャルＧＣサイクルを実行する利点は少ない。ところで、このようなヒープ１３３の利用状況の変化はプログラム実行部１０１で検出することができる。そこで、この検出結果に基づき、次回のＧＣサイクルにおいてフルＧＣサイクルの実行を選択するように制御を行なうものがこの第五実施例である。
【０１６６】
この第五の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、図１２に示したポインタ置き換え処理のアルゴリズム、及び図１３に示したセル新規使用処理のアルゴリズムに沿った処理を実行することに加え、図２６にアルゴリズムを示すフルＧＣサイクル実行要求処理を実行する。フルＧＣサイクル実行要求処理は、ＣＰＵ１１１がアプリケーションプログラムを実行中にヒープ１３３の利用状況を変化させるような処理を開始するとき、前述した画像処理プログラムの例で説明すれば、別の画像データの読み込み処理を実行するとき、に起動される。
【０１６７】
フルＧＣサイクル実行要求処理は、図２６に示すように、Ｓ７０１において、フラグＮＥＸＴ＿ＧＣに  「ＦＵＬＬ」をセットしてフルＧＣサイクルの実行を要求するのみである。
【０１６８】
次に、図２７に示す第五の実施例におけるフル・パーシャル制御処理のアルゴリズムについて説明する。
図２７において、Ｓ７２１では、フラグＮＥＸＴ＿ＧＣに「ＦＵＬＬ」がセットされているか否かが判定され、判定結果がＹｅｓならばＳ７２２に、ＮｏならばＳ７２４に、それぞれ進む。
【０１６９】
Ｓ７２２ではフラグＮＥＸＴ＿ＧＣにＮＩＬ（空値）が代入される。
Ｓ７２３では図１７に示したフルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
【０１７０】
Ｓ７２４では図１６に示したパーシャルＧＣサイクル処理が実行され、その後はこのフル・パーシャル制御処理を終了する。
メモリ管理部１０２のＣＰＵ１１２がこの図２７に示した処理を実行することでこのフル・パーシャル制御処理の１シーケンスが終了する。この第五実施例ではＣＰＵ１１２によりこのフル・パーシャル制御処理のシーケンスが繰り返し実行され、各シーケンスごとに適切なＧＣサイクルが選択されて実行される。
【０１７１】
次に、基本的なＰＭＧＣからの改良ついて、今までに説明したフル・パーシャル制御処理以外の他の例について説明する。
図８に示したマークフェーズ処理のＳ１４２からＳ１４４の処理に注目する。この部分の処理を考えると、ＧＣスタック１３５に格納されているポインタの指すセルであって、カラーフィールドが白灰色とされているものは、そのカラーフィールドが黒に変更される。ここで、カラーフィールドが白灰色とされているセルであってＧＣスタック１３５にそのセルを指すポインタが格納されているものとは、プログラム実行部１０１で実行されているアプリケーションプログラムにより新たに使用が開始されたセルであって、図１２に示すポインタ置き換え処理のＳ２０５若しくはＳ２０８によってそのセルを指すポインタがＧＣスタック１３５に格納されたものである。
【０１７２】
ここで、上述した新たに使用が開始されたセルのうち、マークフェーズ処理を一度も経験することなく、その使用を終えて「ごみ」となってしまったものについて考えてみる。このセルは未使用セルとして回収することが可能であることは明らかである。ところが、このセルを指すポインタがＧＣスタック１３５に既に格納されており、しかも、このセルのカラーフィールドが白灰色とされているため、このセルは、図１２のＳ１４２及びＳ１４３の処理ステップの作用によってＳ１４４の処理が施され、このセルのカラーフィールドが黒に変更されてしまう。黒の印付けがされたセルはスイープフェーズでは回収されることはなく、その回収のためにはフルＧＣサイクルの実行を待たなければならないことは今までに説明した通りである。また、生存時間の短いセルが直ちに回収されないことは、ＧＣの回収効率の低下を招く要因となることも既に説明している。
【０１７３】
以上の点を踏まえ、マークフェーズを一度も経験することのない、生存時間の短いセルを直後のスイープフェーズで回収できるようにする。ここでは、この実施例を処理効率を向上させたＰＭＧＣの第六実施例と呼ぶこととする。
【０１７４】
この第六実施例においては、今までの各実施例において用いられていた、セルのカラーフィールドに付される色のうち、白灰色を、マークフェーズ未経験のもの（ＯＦＦ＿ＷＨＩＴＥ＿ＵＶ）とマークフェーズ経験済みのもの（ＯＦＦ＿ＷＨＩＴＥ＿Ｖ）とに更に色分けする。このことにより、ヒープ１３３中のセルは計４色に色分けされることになる。
【０１７５】
なお、後述する処理においてセルに付されている色が判定される処理はどのようなものが多く発生するかを考えると、白か黒かの判定を行なう処理、及び白灰色におけるマークフェーズ経験の有無の判定を行なう処理の回数が多くなることは明らかである。そこで、セルのカラーフィールドについて、これらの判定処理の対象となる色の組に対応するフラグを図２８のようにビット毎に計２ビット割り当てるようにすると、処理回数の多い判定処理について、高速に処理することのできるビット単位の判断処理を用いて行なわせることができるので、ＧＣ全体の処理速度の点で有利である。
【０１７６】
この第六実施例において、メモリ管理部１０２のＣＰＵ１２１は、図６に示したＰＭＧＣの基本的な処理（以後、この処理を「ＰＭＧＣ制御処理」とも呼ぶ）のアルゴリズムに沿って各処理を実行する。但し、図６のＳ１０４及びＳ１１０に示されているマークフェーズ処理、及びＳ１０６に示されているスイープ・リーブマーク処理が、それぞれ図８、図９に示されていたものから図２９、図３０に示すものに変更されて実行される。
【０１７７】
まず、図２９に示す、この第六実施例におけるマークフェーズ処理のアルゴリズムについて説明する。
Ｓ１００１において、ＧＣスタック１３５が空であるか否かを判定し、この判定結果がＹｅｓならばマークフェーズ処理を終了する。一方、この判定結果がＮｏならばＳ１００２に進む。
【０１７８】
Ｓ１００２では、ＧＣスタック１３５からその先頭に格納されているポインタをひとつ取り出して変数ｎに代入する。
Ｓ１００３では、変数ｎに代入されているポインタが指しているセルについて、そのセルの内容がＮＩＬである（値が空である）か否か、及び、そのセルが不使用であるか否か、が判定され、このどちらか一方でもＹｅｓならばＳ１００１へ戻って上述した処理を繰り返す。一方、この両者の判定結果が共にＮｏならばＳ１００４に進む。
【０１７９】
Ｓ１００４では、変数ｎに代入されているポインタが指しているセルのカラーフィールドが白にされているか否かを判定し、判定結果がＹｅｓならば、Ｓ１００５において、変数ｎの指すセルのカラーフィールドを黒に変更し、このセルが使用されていることを示す。そして、このセルのポインタフィールドcdr に格納されているポインタをＧＣスタック１３５に格納してそのポインタが指すセルに対して印付け処理が後に行なわれるようにする。更に、変数ｎの指すセルのポインタフィールドcarに格納されているポインタを変数ｎに代入し、その後はＳ１００３へ戻って上述した処理を繰り返す。このＳ１００５の処理は、図８のＳ１４４の処理と同じである。
【０１８０】
Ｓ１００６では、変数ｎに代入されているポインタが指しているセルのカラーフィールドが白灰色であってマークフェーズ未経験のもの（ＯＦＦ＿ＷＨＩＴＥ＿ＵＶ）であるか否かを判定し、判定結果がＹｅｓならば、Ｓ１００７において、変数ｎの指すセルのカラーフィールドを白灰色であってマークフェーズ経験済みのもの（ＯＦＦ＿ＷＨＩＴＥ＿Ｖ）に変更する。そして、このセルのポインタフィールドcdr に格納されているポインタをＧＣスタック１３５に格納してそのポインタが指すセルに対しての印付けの判別処理が後に再度行なわれるようにする。更に、変数ｎの指すセルのポインタフィールドcarに格納されているポインタを変数ｎに代入し、その後はＳ１００３へ戻って上述した処理を繰り返す。このように、第六実施例は、セルが使用中であるか否かの判定を２度行なうようにしたのである。アプリケーションプログラムの実行により使用が開始され、その直後にその使用が終了してしまうような、使用期間の短いセルであっても、２度続けて使用中の判定が下されることはないので、こうすることにより、使用期間の短いセルでも確実に回収することができるようになる。
【０１８１】
以上までの処理が第六実施例におけるマークフェーズ処理である。
次に、図３０に示す、この第六実施例におけるスイープ・リーブマーク処理のアルゴリズムについて説明する。
【０１８２】
図３０に示すＳ１０２１からＳ１０２７にかけての処理を、図９に示すＳ１６１からＳ１６７にかけての処理と比較すると、両者の違いはＳ１０２４とＳ１６４との判断処理の処理ステップのみである。この違いはセルに付す白灰色についてマークフェーズ経験の有無に基づく印の色分けを導入したことに起因するものであり、本質的には両者の処理内容は同一である。但し、図３０のＳ１０２３において実行されるフリーリスト追加処理が、図１０に示されていたものから変更される。
【０１８３】
この第六実施例におけるフリーリスト追加処理のアルゴリズムを図３１に示す。この処理は、Ｓ１０４１において、変数ｉの指すセルを、カラーフィールドを白灰色であってマークフェーズ未経験のもの（ＯＦＦ＿ＷＨＩＴＥ＿ＵＶ）にすると共にポインタフィールドcar にポインタｆを格納し、更にフリーリスト１３４を更新してこのセルを不使用セルのリストに接続する処理である。
【０１８４】
また、この第六の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１３に示したセル新規使用処理を実行するが、ポインタ置き換え処理は図１２に示したアルゴリズムの代わりに図３２に示したアルゴリズムに沿った処理を実行する。
【０１８５】
図３２に示すＳ１０６１からＳ１０６９にかけての処理を、図１２に示すＳ２０１からＳ２０９にかけての処理と比較すると、両者の違いはＳ１０６４とＳ２０４との判断処理の処理ステップのみである。この違いも、前述した図３０と図９との違いと同様に、セルに付す白灰色についてマークフェーズ経験の有無に基づく印の色分けを導入したことに起因するものであり、本質的には両者の処理内容は同一である。
【０１８６】
次に、処理効率を向上させたＰＭＧＣの第七の実施例について説明する。この第七の実施例は、前述した第六の実施例と同様に、マークフェーズを一度も経験することのない、生存時間の短いセルを直後のスイープフェーズで回収できるようにするものである。
【０１８７】
前述した基本的なＰＭＧＣにおいて、プログラム実行部１０１がアプリケーションプログラムを実行した際に、ポインタｍが指すヒープ１３３中のポインタをポインタｎに変更するときに実行されるポインタ置き換え処理のアルゴリズムを示している図１２について考える。
【０１８８】
図１２においては、Ｓ２０５もしくはＳ２０８の処理の作用によって、カラーフィールドが白灰色にされているセルのポインタｎがＧＣスタック１３５に格納されてしまうために、図８に示したマークフェーズ処理のＳ１４２からＳ１４４の処理によってそのセルのカラーフィールドが黒に変更されてしまう。その結果、直後に実行されるスイープフェーズでは、例えそのセルがその使用を終えて「ごみ」となったものであったとしても、このセルが回収できなくなる。
【０１８９】
そこで、この第七実施例では、上述したポインタ置き換え処理のアルゴリズムを変更し、ポインタｎをＧＣスタック１３５に格納するのではなく、ポインタｍをＧＣスタック１３５に格納するようにし、更に、マークフェーズ処理を変更することによって、マークフェーズを一度も経験することのない、生存時間の短いセルを直後のスイープフェーズで回収できるようにする。
【０１９０】
この第七の実施例においては、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１３に示したセル新規使用処理を実行するが、ポインタ置き換え処理は図１２に示したアルゴリズムの代わりに図３３に示したアルゴリズムに沿った処理を実行する。
【０１９１】
図３３に示すＳ１１０１からＳ１１０９にかけての処理を、図１２に示すＳ２０１からＳ２０９にかけての処理と比較すると分かるように、図３３は、図１２のＳ２０５及びＳ２０８においてはポインタｎをＧＣスタック１３５に格納していたものを、Ｓ１１０５及びＳ１１０８において、前述したように、ポインタｍをＧＣスタック１３５に格納するように変更したものである。このように、変更前のポインタｍを格納するようにしたことにより、そのセルについての印付けの処理が後で必ず行なわれるようになるので、ポインタｎの指すセルの使用期間が短かったとしても、そのセルを回収できるようになる。
【０１９２】
更に、この第七実施例では、メモリ管理部１０２のＣＰＵ１２１は、図６に示したＰＭＧＣ制御処理のアルゴリズムに沿って各処理を実行する。但し、図６のＳ１０４及びＳ１１０に示されているマークフェーズ処理が、図８に示されていたものから図３４に示すものに変更されて実行される。
【０１９３】
図３４に示す、この第七実施例におけるマークフェーズ処理のアルゴリズムについて説明する。
まず、Ｓ１１２１において、ＧＣスタック１３５が空であるか否かを判定し、この判定結果がＹｅｓならばマークフェーズ処理を終了する。一方、この判定結果がＮｏならばＳ１１２２に進む。
【０１９４】
Ｓ１１２２では、ＧＣスタック１３５からその先頭に格納されているポインタをひとつ取り出して変数ｎに代入する。
以上のＳ１１２１及びＳ１１２２の処理は、図８のＳ１４１及びＳ１４２の処理と同じである。
【０１９５】
Ｓ１１２３からＳ１１２７にかけての処理について説明する。
図３３に示した、変更されたポインタ置き換え処理を実行すると、ＧＣスタック１３５に格納されるポインタｍが指すセルのうち、自分自身は既に印付けの処理が施されているが、自分自身のポインタフィールドに格納されているポインタが指すセルについての印付けの処理が未だ施されていないものが発生し得る。このＳ１１２３からＳ１１２７にかけての処理は、このような印付けの処理が施されていないセルを指すポインタをＧＣスタック１３５に格納するようにして、このセルについてもこのマークフェーズ処理中にいずれ必ず印付けの処理が行なわれるようにするものである。
【０１９６】
Ｓ１１２３では、変数ｎに代入されているポインタが指しているセルについて、そのセルの内容がＮＩＬではなく（値が空でない）、且つ、そのセルのカラーフィールドに黒の印が付されているかどうかを判定し、判定結果がＹｅｓならばＳ１１２４に、ＮｏならばＳ１１２８に、それぞれ進む。
【０１９７】
Ｓ１１２４では、変数ｎに代入されているポインタが指しているセルについて、そのセルのポインタフィールドcdrに格納されているポインタが指すセルの内容がＮＩＬではなく（値が空でない）、且つ、そのセルのカラーフィールドに黒の印が付されているかどうかを判定し、判定結果がＹｅｓのときにのみ、Ｓ１１２５において、変数ｎに代入されているポインタが指しているセルのポインタフィールドcdrに格納されているポインタをＧＣスタック１３５に格納する。
【０１９８】
Ｓ１１２６では、変数ｎに代入されているポインタが指しているセルについて、そのセルのポインタフィールドcarに格納されているポインタが指すセルの内容がＮＩＬではなく（値が空でない）、且つ、そのセルのカラーフィールドに黒の印が付されているかどうかを判定し、判定結果がＹｅｓのときにのみ、Ｓ１１２７において、変数ｎに代入されているポインタが指しているセルのポインタフィールドcarに格納されているポインタをＧＣスタック１３５に格納する。
【０１９９】
Ｓ１１２８では、変数ｎに代入されているポインタが指しているセルについて、（１）そのセルの内容がＮＩＬである（値が空である）か、（２）そのセルが使用されていないか、または、（３）そのセルのカラーフィールドに黒の印が付されているかどうかを判定する。この（１）から（３）までのうち、ひとつでもＹｅｓならばＳ１１２１へ戻って上述した処理を繰り返す。
【０２００】
一方、Ｓ１１２８の判定処理の結果がＮｏならば、Ｓ１１２９において、変数ｎの指すセルのカラーフィールドを黒に変更し、このセルが使用されていることを示す。そして、このセルのポインタフィールドcdr に格納されているポインタをＧＣスタック１３５に格納してそのポインタが指すセルに対して印付け処理が後に行なわれるようにする。更に、変数ｎの指すセルのポインタフィールドcarに格納されているポインタを変数ｎに代入し、その後はＳ１１２８へ戻って上述した処理を繰り返す。
【０２０１】
以上のＳ１１２８及びＳ１１２９の処理は、図８のＳ１４３及びＳ１４４の処理と同じである。
次に、処理効率を向上させたＰＭＧＣの第八の実施例について説明する。
【０２０２】
図１２に示したポインタ置き換え処理のＳ２０１及びＳ２０２の処理に注目する。この処理は、ＧＣの現在の処理フェーズがマークフェーズである場合に、プログラム実行部１０１でのアプリケーションプログラムの実行によってポインタｍが指すヒープ１３３中のポインタをポインタｎに変更する処理が発生したときに、その変更前のポインタをＧＣスタック１３５に格納して、その変更前のポインタの指していたセルに対して印付けの処理が施されるようにする処理である。
【０２０３】
ここで、この変更前のポインタを格納するセルのカラーフィールドについて考える。もしもこのセルのカラーフィールドが既に黒にされているのであれば、このセルに対して新たに印付けの処理を施す必要はない。また、もしもこのセルのカラーフィールドが白灰色なのであれば、その変更前に他のセルのポインタによってこのセルが指されていたことを考慮すれば、このセルを指すポインタが既にＧＣスタック１３５に格納されていることは明らかである。
【０２０４】
従って、ポインタ置き換え処理において、上述した変更前のポインタのうち、ＧＣスタック１３５に格納する必要のあるものは、そのポインタを格納しているセルのカラーフィールドが白にされているもののみで十分であることが分かる。
【０２０５】
この第八実施例は、上述した条件に従ったポインタ置き換え処理を実行して、ポインタのＧＣスタック１３５への不必要な格納を防止して印付け処理の最適化を図ると共に、プログラム実行部１０１によって行なわれるＧＣスタック１３５へのポインタの格納のための通知処理の負担を軽減するものである。
【０２０６】
この第八実施例では、メモリ管理部１０２のＣＰＵ１２１は、図６に示したＰＭＧＣ制御処理のアルゴリズムに沿って各処理を実行する。また、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１３に示したセル新規使用処理を実行するが、ポインタ置き換え処理は図１２に示したアルゴリズムの代わりに図３５に示したアルゴリズムに沿った処理を実行する。
【０２０７】
図３５に示すＳ１２０１からＳ１２１０にかけての処理を、図１２に示すＳ２０１からＳ２０９にかけての処理と比較すると分かるように、図３５は、図１２のＳ２０２の処理を、Ｓ１２０２及びＳ１２０３の処理に置き換える変更を行なったものである。
【０２０８】
図３５において、Ｓ１２０１の判定処理の結果がＹｅｓの場合に実行されるＳ１２０２では、ポインタｍの指しているヒープ１３３中に現在格納されているポインタを格納しているセルのカラーフィールドが白にされているか否かを判定し、判定結果がＹｅｓならば、Ｓ１２０３においてポインタｍの指しているヒープ１３３中に現在格納されているポインタをＧＣスタック１３５に格納し、その後はＳ１２０４に進む。一方、Ｓ１２０２の判定結果がＮｏならば何もせずにこのままＳ１２０４に進む。
【０２０９】
次に、処理効率を向上させたＰＭＧＣの第九の実施例について説明する。
まず、図１２に示したポインタ置き換え処理のＳ２０３からＳ２０５の処理に注目する。この処理は、ＧＣの現在の処理フェーズがマークフェーズである場合に、プログラム実行部１０１でのアプリケーションプログラムの実行によってポインタｍが指すヒープ１３３中のポインタをポインタｎに変更する処理が発生したときに、そのポインタｎをＧＣスタック１３５に格納して、カラーフィールドが白灰色にされているポインタｎの指すセルに対して印付けの処理が施されるようにする処理である。
【０２１０】
ここで、ポインタｍが指すポインタを格納するセルのカラーフィールドについて考える。もしも、このセルのカラーフィールドが黒ではない、白もしくは白灰色であるならば、ポインタｍが指すセルはこの変更前からその使用が継続していることを考慮すれば、ポインタｍが指すセルについては印付けの処理がそのマークフェーズにおいて未だ行なわれていないことが明らかである。そして、この場合には、その後ポインタｍが指すセルについて印付けの処理が施されるときに、そのセルに含まれるポインタｎが確実にＧＣスタック１３５に格納される。つまり、この場合には、Ｓ２０５の処理を実行しなくてもいずれはポインタｎがＧＣスタック１３５に格納されるのである。
【０２１１】
次に、図１２のＳ２０６からＳ２０８の処理に注目する。この処理は、ＧＣの現在の処理フェーズがスイープフェーズである場合に、プログラム実行部１０１でのアプリケーションプログラムの実行によってポインタｍが指すヒープ１３３中のポインタをポインタｎに変更する処理が発生したときに、そのポインタｎをＧＣスタック１３５に格納して、カラーフィールドが白もしくは白灰色であるポインタｎの指すセルに対して印付けの処理が施されるようにする処理である。
【０２１２】
この場合においても、前述した場合と同様であり、ポインタｍが指すポインタを格納するセルのカラーフィールドが黒ではない、白もしくは白灰色であるならば、その後ポインタｍが指すセルについて印付けの処理が施されるときに、そのセルに含まれるポインタｎが確実にＧＣスタック１３５に格納される。従って、この場合も、Ｓ２０８の処理を実行しなくてもいずれはポインタｎがＧＣスタック１３５に格納される。
【０２１３】
この第九実施例は、上述した２つの条件に従ったポインタ置き換え処理を実行することによって、ポインタのＧＣスタック１３５への不必要な格納を防止して印付け処理の最適化を図ると共に、プログラム実行部１０１によって行なわれるＧＣスタック１３５へのポインタの格納のための通知処理の負担を軽減するものである。
【０２１４】
この第九実施例では、メモリ管理部１０２のＣＰＵ１２１は、図６に示したＰＭＧＣ制御処理のアルゴリズムに沿って各処理を実行する。また、プログラム実行部１０１のＣＰＵ１１１は、前述した基本的なＰＭＧＣを実行する場合と同様に、図１３に示したセル新規使用処理を実行するが、ポインタ置き換え処理は図１２に示したアルゴリズムの代わりに図３６に示したアルゴリズムに沿った処理を実行する。
【０２１５】
図３６に示すＳ１３０１からＳ１３０９にかけての処理を、図１２に示すＳ２０１からＳ２０９にかけての処理と比較すると分かるように、図３６は、図１２のＳ２０４及びＳ２０７の判断処理を、Ｓ１３０４及びＳ１３０７の判断処理に変更したものである。
【０２１６】
図３６において、Ｓ１３０３の判定処理の結果がＹｅｓの場合に実行されるＳ１３０４では、ポインタｎの指すセルのカラーフィールドが白灰色にされており、且つ、ポインタｍの指すセルのカラーフィールドが黒にされているか否かを判定し、判定結果がＹｅｓならば、Ｓ１３０５において、ポインタｎをＧＣスタック１３５に格納し、その後はＳ１３０９に進む。一方、Ｓ１３０４の判定処理の結果がＮｏならば、何もせずにそのままＳ１３０９に進む。
【０２１７】
また、Ｓ１３０６の判定処理の結果がＹｅｓの場合に実行されるＳ１３０７では、ポインタｎの指すセルのカラーフィールドが黒ではない白または灰色にされており、且つ、ポインタｍの指すセルのカラーフィールドが黒にされているか否かを判定し、判定結果がＹｅｓならば、Ｓ１３０８において、ポインタｎをＧＣスタック１３５に格納し、その後はＳ１３０９に進む。一方、Ｓ１３０７の判定処理の結果がＮｏならば、何もせずにそのままＳ１３０９に進む。
【０２１８】
なお、上述した本発明の各実施形態において説明した各処理を汎用的なコンピュータで実施させることも可能である。そのためには、本発明の各実施形態において説明した、図６から図３６にかけて示した各アルゴリズムに沿った処理をコンピュータに行なわせるメモリ管理プログラムをそのコンピュータで読み取り可能な記録媒体（記憶媒体）に予め記憶させておき、その記録媒体から読み出したそのメモリ管理プログラムを読み出させてそのコンピュータのメインメモリに一旦格納させた後に、そのコンピュータの有する中央処理装置に格納されたこのプログラムを読み出させて実行させるように構成すればよい。
【０２１９】
上述したメモリ管理プログラムを格納し、且つそれをコンピュータで読み取ることの可能な記録媒体の例を図３７に示す。このような記録媒体としては、例えば、コンピュータ１４１の本体に内蔵若しくは外付けされる半導体メモリやハードディスク装置などのメモリ１４２、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＭＯ（光磁気ディスク）、フロッピーディスクなどといった可搬型記憶媒体１４３、あるいはコンピュータ１４１と回線１４４で接続されていてコンピュータ１４１がプログラムをダウンロードすることの可能なプログラムサーバ１４５の記憶装置１４６などがあるが、これらのいずれであってもよい。
【０２２０】
【発明の効果】
以上詳細に説明したように、本発明の第一の態様によれば、ＰＭＧＣにおける次に行なう不使用のセルの回収を、フルＧＣサイクルとパーシャルＧＣサイクルとのうちどちらに行なわせればＧＣ全体の処理効率が良好になるかを、フルＧＣサイクル若しくはパーシャルＧＣサイクルによって過去に行なわれた不使用のセルの回収の状況に基づいて判断し、この判断結果に基づいて次に実行させるＧＣサイクルを選択することができるようになる。
【０２２１】
また、本発明の第二の態様によれば、マークフェーズによって不使用であるとされたセルが、マークフェーズを初めて経験したものであるときには、その判断結果だけでそのセルを回収せずに、マークフェーズを再度経験させ、その結果に基づいて不使用のセルのヒープからの回収を行なうようにする。こうすることにより、アプリケーションプログラムの実行により使用が開始され、その直後にその使用が終了してしまうような、使用期間の短いセルであっても、確実に回収することができるようになる。
【０２２２】
また、本発明の第三の態様によれば、アプリケーションプログラムの実行によって、ヒープ中における使用中のセルに格納されていた第一のポインタであって、ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタが格納されていたセルを指すポインタが通知される。メモリ管理部は、その通知されたポインタの指すセルに格納されている該第二のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう。こうすることにより、アプリケーションプログラムの実行により使用が開始され、その直後にその使用が終了してしまうような、使用期間の短いセルであっても、該セルの判別が確実に行なわれるようになり、不使用と判断されれば該セルが確実に回収できるようになる。
【０２２３】
また、本発明の第四の態様によれば、アプリケーションプログラムの実行によって、ヒープ中における使用中のセルに格納されていた第一のポインタであって、該ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタの指すセルが、フルＧＣサイクルによって最近に行なわれたセルの使用状況の判別以後の期間に、マークフェーズを経験していない場合に限り、該第一のポインタが通知される。メモリ管理部では、通知されたポインタの指すセルに格納されている前記第一のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう。こうすることにより、メモリ管理部に通知されるポインタの量を減らすことができ、その分処理負担を軽減することができる。
【０２２４】
また、本発明の第五の態様においては、アプリケーションプログラムの実行によって、ヒープ中における使用中のセルに格納されていた第一のポインタであって、ヒープ中の他のセルを指す該第一のポインタが第二のポインタに変更されたときに、該第一のポインタの指すセルが、フルＧＣサイクルによって最近に行なわれたセルの使用状況の判別以後の期間にマークフェーズを経験していない場合に限り、該第二のポインタが通知される。メモリ管理部では、通知されたポインタの指すセルに格納されている前記第二のポインタの指すセルについて、アプリケーションプログラムの実行により該セルが使用中であるか否かの判別を新たに行なう。こうすることにより、メモリ管理部に通知されるポインタの量を減らすことができ、その分処理負担を軽減することができる。
【０２２５】
以上のように、本発明のいずれの態様によっても、並列型ＧＣの処理効率を向上させることが可能となる効果を奏する。
【図面の簡単な説明】
【図１】本発明の第一の態様の原理構成を示す図である。
【図２】本発明の第二の態様の原理構成を示す図である。
【図３】本発明の第三、第四、第五の態様の原理構成を示す図である。
【図４】本発明を実施する装置の構成を示す図である。
【図５】ＲＡＭ１０３の記憶領域の構成を示す図である。
【図６】ＰＭＧＣの基本的な処理のアルゴリズムを示す図である。
【図７】ルート挿入フェーズ処理のアルゴリズムを示す図である。
【図８】マークフェーズ処理のアルゴリズムを示す図である。
【図９】スイープ・リーブマーク処理のアルゴリズムを示す図である。
【図１０】フリーリスト追加処理のアルゴリズムを示す図である。
【図１１】スイープ・クリアマーク処理のアルゴリズムを示す図である。
【図１２】ポインタ置き換え処理のアルゴリズムを示す図である。
【図１３】セル新規使用処理のアルゴリズムを示す図である。
【図１４】処理効率を向上させたＰＭＧＣの第一の実施例におけるフリーリスト追加処理のアルゴリズムを示す図である。
【図１５】処理効率を向上させたＰＭＧＣの第一の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
【図１６】パーシャルＧＣサイクル処理のアルゴリズムを示す図である。
【図１７】フルＧＣサイクル処理のアルゴリズムを示す図である。
【図１８】クリアマーク処理のアルゴリズムを示す図である。
【図１９】処理効率を向上させたＰＭＧＣの第二の実施例におけるセル新規使用処理のアルゴリズムを示す図である。
【図２０】処理効率を向上させたＰＭＧＣの第二の実施例におけるスイープ・リーブマーク処理のアルゴリズムを示す図である。
【図２１】処理効率を向上させたＰＭＧＣの第二の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
【図２２】処理効率を向上させたＰＭＧＣの第三の実施例におけるポインタ置き換え処理のアルゴリズムを示す図である。
【図２３】処理効率を向上させたＰＭＧＣの第三の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
【図２４】処理効率を向上させたＰＭＧＣの第四の実施例におけるスイープ・リーブマーク処理のアルゴリズムを示す図である。
【図２５】処理効率を向上させたＰＭＧＣの第四の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
【図２６】フルＧＣサイクル実行要求処理のアルゴリズムを示す図である。
【図２７】処理効率を向上させたＰＭＧＣの第五の実施例におけるフル・パーシャル制御処理のアルゴリズムを示す図である。
【図２８】セルに付す色に対するビット割り当ての一例を示す図である。
【図２９】処理効率を向上させたＰＭＧＣの第六の実施例におけるマークフェーズ処理のアルゴリズムを示す図である。
【図３０】処理効率を向上させたＰＭＧＣの第六の実施例におけるスイープ・リーブマーク処理のアルゴリズムを示す図である。
【図３１】処理効率を向上させたＰＭＧＣの第六の実施例におけるフリーリスト追加処理のアルゴリズムを示す図である。
【図３２】処理効率を向上させたＰＭＧＣの第六の実施例におけるポインタ置き換え処理のアルゴリズムを示す図である。
【図３３】処理効率を向上させたＰＭＧＣの第七の実施例におけるポインタ置き換え処理のアルゴリズムを示す図である。
【図３４】処理効率を向上させたＰＭＧＣの第七の実施例におけるマークフェーズ処理のアルゴリズムを示す図である。
【図３５】処理効率を向上させたＰＭＧＣの第八の実施例におけるポインタ置き換え処理のアルゴリズムを示す図である。
【図３６】処理効率を向上させたＰＭＧＣの第九の実施例におけるポインタ置き換え処理のアルゴリズムを示す図である。
【図３７】記憶させたメモリ管理プログラムをコンピュータで読み取ることの可能な記憶媒体の例を示す図である。
【図３８】  on-the-fly  ＧＣにおける印付けの手順を説明する図である。
【図３９】スナップショットＧＣにおける印付けの手順を説明する図である。
【符号の説明】
１  フル・ガーベジ・コレクション手段
２  パーシャル・ガーベジ・コレクション手段
３  フル・パーシャル制御手段
１０  アプリケーションプログラム実行部
１１、１３３  ヒープ
２１  フル判別手段
２２  フル回収手段
２３  パーシャル抽出手段
２４、３１  パーシャル判別手段
２５、３２  パーシャル回収手段
２６  パーシャル・マーキング・ガーベジ・コレクション制御手段
３３  通知手段
１０１  プログラム実行部
１０２  メモリ管理部
１０３、１２３  ＲＡＭ
１０４、１１５、１２４  バス
１１１、１２１  ＣＰＵ
１１２、１２２  ＲＯＭ
１１３  入力部
１１４  出力部
１３１  レジスタファイル
１３２  実行スタック
１３４  フリーリスト
１３５  ＧＣスタック
１４１  コンピュータ
１４２  メモリ
１４３  可搬型記憶媒体
１４４  回線
１４５  プログラムサーバ
１４６  記憶装置
【図１】
0003934355.tif 000002
【図２】
0003934355.tif 000003
【図３】
0003934355.tif 000004
【図４】
0003934355.tif 000005
【図５】
0003934355.tif 000006
【図６】
0003934355.tif 000007
【図７】
0003934355.tif 000008
【図８】
0003934355.tif 000009
【図９】
0003934355.tif 000010
【図１０】
0003934355.tif 000011
【図１１】
0003934355.tif 000012
【図１２】
0003934355.tif 000013
【図１３】
0003934355.tif 000014
【図１４】
0003934355.tif 000015
【図１５】
0003934355.tif 000016
【図１６】
0003934355.tif 000017
【図１７】
0003934355.tif 000018
【図１８】
0003934355.tif 000019
【図１９】
0003934355.tif 000020
【図２０】
0003934355.tif 000021
【図２１】
0003934355.tif 000022
【図２２】
0003934355.tif 000023
【図２３】
0003934355.tif 000024
【図２４】
0003934355.tif 000025
【図２５】
0003934355.tif 000026
【図２６】
0003934355.tif 000027
【図２７】
0003934355.tif 000028
【図２８】
0003934355.tif 000029
【図２９】
0003934355.tif 000030
【図３０】
0003934355.tif 000031
【図３１】
0003934355.tif 000032
【図３２】
0003934355.tif 000033
【図３３】
0003934355.tif 000034
【図３４】
0003934355.tif 000035
【図３５】
0003934355.tif 000036
【図３６】
0003934355.tif 000037
【図３７】
0003934355.tif 000038
【図３８】
0003934355.tif 000039
【図３９】
0003934355.tif 000040