TOP > 国内特許検索 > メモリ管理方法、メモリ管理装置、及びメモリ管理プログラムが記録されている記録媒体 > 明細書

明細書 :メモリ管理方法、メモリ管理装置、及びメモリ管理プログラムが記録されている記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4769946号 (P4769946)
公開番号 特開2008-191952 (P2008-191952A)
登録日 平成23年7月1日(2011.7.1)
発行日 平成23年9月7日(2011.9.7)
公開日 平成20年8月21日(2008.8.21)
発明の名称または考案の名称 メモリ管理方法、メモリ管理装置、及びメモリ管理プログラムが記録されている記録媒体
国際特許分類 G06F  12/02        (2006.01)
G06F  12/00        (2006.01)
FI G06F 12/02 530C
G06F 12/00 591
請求項の数または発明の数 11
全頁数 31
出願番号 特願2007-026111 (P2007-026111)
出願日 平成19年2月5日(2007.2.5)
審査請求日 平成22年1月14日(2010.1.14)
特許権者または実用新案権者 【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
発明者または考案者 【氏名】鵜川 始陽
【氏名】湯淺 太一
早期審査対象出願または早期審理対象出願 早期審査対象出願
個別代理人の代理人 【識別番号】100084375、【弁理士】、【氏名又は名称】板谷 康夫
【識別番号】100121692、【弁理士】、【氏名又は名称】田口 勝美
【識別番号】100125221、【弁理士】、【氏名又は名称】水田 愼一
審査官 【審査官】多賀 実
参考文献・文献 特表2002-506550(JP,A)
米国特許第06249793(US,B1)
特許第3530887(JP,B2)
寺島 元章 外2名,圧縮型並列ガーベッジコレクション,情報処理学会研究報告,日本,社団法人情報処理学会,1997年 8月22日,第97巻 第78号(97-PRO-14),p.115-120
Ori Ben-Yitzhak 外4名,An algorithm for parallel incremental compaction,ISMM '02 Proceedings of the 3rd international symposium on Memory management ,米国,ACM,2002年,p.100-105
調査した分野 G06F12/00
G06F12/02
特許請求の範囲 【請求項1】
メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、
主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理方法において、
前記オブジェクトは、オブジェクトの複製先の位置又は複製元の位置を記録するための複製位置ポインタをさらに含み、
前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、
前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定ステップと、
前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、該複製元オブジェクト及び該複製先オブジェクトの複製位置ポインタの参照先を互いのオブジェクトの位置に設定するオブジェクト複製ステップと、
前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第1ポインタ更新ステップと、
前記限定範囲の領域を利用可能領域にする限定範囲利用可能化ステップと、
前記オブジェクト複製ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断ステップと、
前記複製判断ステップにより書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込みステップと、を含み、
前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、
前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第3ポインタ更新ステップと、
前記第3ポインタ更新ステップによるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新ステップによる処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定ステップと、をさらに備え、
前記第1ポインタ更新ステップは、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁が、関数の実行完了後、前記第3ポインタ更新ステップによる処理を再開させることを特徴とするメモリ管理方法。
【請求項2】
メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、
主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理方法において、
前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、
前記メモリ中に、オブジェクトの位置を記録するオブジェクト位置記録領域がさらに設けられ、
前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定ステップと、
前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、前記オブジェクト位置記録領域に、該複製元オブジェクトの位置及び該複製先オブジェクの位置を記録するオブジェクト複製ステップと、
前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第1ポインタ更新ステップと、
前記限定範囲の領域を利用可能領域にする限定範囲利用可能化ステップと、
前記オブジェクト複製ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断ステップと、
前記複製判断ステップにより書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込みステップと、を含み、
前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、
前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第3ポインタ更新ステップと、
前記第3ポインタ更新ステップによるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新ステップによる処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定ステップと、をさらに備え、
前記第1ポインタ更新ステップは、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁が、関数の実行完了後、前記第3ポインタ更新ステップによる処理を再開させることを特徴とするメモリ管理方法。
【請求項3】
前記オブジェクトは、前記データ要素として前記オブジェクト位置ポインタをさらに含み、
前記複製元オブジェクトの位置を参照する前記ヒープ領域内のオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第2ポインタ更新ステップと、
前記第2ポインタ更新ステップを実行中に、前記主プログラムが前記ヒープ領域に前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、該オブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に変更する参照先変更ステップと、
前記第2ポインタ更新ステップの実行中に、前記主プログラムが2つのオブジェクト位置ポインタの参照先が同じオブジェクトの位置であるかどうかの検査処理を行うとき、該2つのオブジェクト位置ポインタのうちの一方が前記複製元オブジェクトの位置を、他方が前記複製先オブジェクトの位置を参照している場合、同一のオブジェクトを参照していると判断する同一判断ステップと、をさらに備え、
前記複製判断ステップは、前記オブジェクト複製ステップ、又は前記第2ポインタ更新ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断することを特徴とする請求項1又は請求項2に記載のメモリ管理方法。
【請求項4】
前記ヒープ領域内に、前記スタック領域を除く前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とし、
前記範囲設定ステップは、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、
前記第1ポインタ更新ステップは、
前記限定範囲内の前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の前記データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、
前記限定範囲及び前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新することを特徴とする請求項1乃至請求項3のいずれかに記載のメモリ管理方法。
【請求項5】
前記ヒープ領域内に、前記スタック領域を含む前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とし、
前記範囲設定ステップは、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、
前記第1ポインタ更新ステップは、
前記限定範囲内の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内に割当てられた、前記スタック領域を除く該データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、
前記限定範囲外の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記第3ポインタ更新ステップは、
前記ヒープ領域内に割当てられた前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、前記限定範囲内の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の該関数フレームを、該ヒープ領域内の利用可能領域に移動させ、
前記限定範囲外の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁設定ステップは、前記第3ポインタ更新処理による処理を中断して、前記主プログラムを実行するときに、前記障壁を、該第3ポインタ更新処理による処理が最後に行われた前記関数フレームに設定することを特徴とする請求項1乃至請求項3のいずれかに記載のメモリ管理方法。
【請求項6】
メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、
主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理装置において、
前記オブジェクトは、オブジェクトの複製先の位置又は複製元の位置を記録するための複製位置ポインタをさらに含み、
前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、
前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定手段と、
前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、該複製元オブジェクト及び該複製先オブジェクトの複製位置ポインタの参照先を互いのオブジェクトの位置に設定するオブジェクト複製手段と、
前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第1ポインタ更新手段と、
前記限定範囲の領域を利用可能領域にする限定範囲利用可能化手段と、
前記オブジェクト複製手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断手段と、
前記複製判断手段により書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込み手段と、を備え
前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、
前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第3ポインタ更新手段と、
前記第3ポインタ更新手段によるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新手段による処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定手段と、をさらに備え、
前記第1ポインタ更新手段は、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁が、関数の実行完了後、前記第3ポインタ更新手段による処理を再開させることを特徴とするメモリ管理装置。
【請求項7】
メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、
主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理装置において、
前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、
前記メモリ中に、オブジェクトの位置を記録するオブジェクト位置記録領域がさらに設けられ、
前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定手段と、
前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、前記オブジェクト位置記録領域に、該複製元オブジェクトの位置及び該複製先オブジェクの位置を記録するオブジェクト複製手段と、
前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第1ポインタ更新手段と、
前記限定範囲の領域を利用可能領域にする限定範囲利用可能化手段と、
前記オブジェクト複製手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断手段と、
前記複製判断手段により書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込み手段と、を備え
前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、
前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第3ポインタ更新手段と、
前記第3ポインタ更新手段によるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新手段による処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定手段と、をさらに備え、
前記第1ポインタ更新手段は、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁が、関数の実行完了後、前記第3ポインタ更新手段による処理を再開させることを特徴とするメモリ管理装置。
【請求項8】
前記オブジェクトは、前記データ要素として前記オブジェクト位置ポインタをさらに含み、
前記複製元オブジェクトの位置を参照する前記ヒープ領域内のオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第2ポインタ更新手段と、
前記第2ポインタ更新手段を実行中に、前記主プログラムが前記ヒープ領域に前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、該オブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に変更する参照先変更手段と、
前記第2ポインタ更新手段の実行中に、前記主プログラムが2つのオブジェクト位置ポインタの参照先が同じオブジェクトの位置であるかどうかの検査処理を行うとき、該2つのオブジェクト位置ポインタのうちの一方が前記複製元オブジェクトの位置を、他方が前記複製先オブジェクトの位置を参照している場合、同一のオブジェクトを参照していると判断する同一判断手段と、をさらに備え、
前記複製判断手段は、前記オブジェクト複製手段、又は前記第2ポインタ更新手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断することを特徴とする請求項6又は請求項7に記載のメモリ管理装置。
【請求項9】
前記ヒープ領域内に、前記スタック領域を除く前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とし、
前記範囲設定手段は、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、
前記第1ポインタ更新手段は、
前記限定範囲内の前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の前記データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、
前記限定範囲及び前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新することを特徴とする請求項6乃至請求項8のいずれかに記載のメモリ管理装置。
【請求項10】
前記ヒープ領域内に、前記スタック領域を含む前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とし、
前記範囲設定手段は、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、
前記第1ポインタ更新手段は、
前記限定範囲内の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内に割当てられた、前記スタック領域を除く該データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、
前記限定範囲外の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記第3ポインタ更新手段は、
前記ヒープ領域内に割当てられた前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、前記限定範囲内の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の該関数フレームを、該ヒープ領域内の利用可能領域に移動させ、
前記限定範囲外の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、
前記障壁設定手段は、前記第3ポインタ更新処理による処理を中断して、前記主プログラムを実行するときに、前記障壁を、該第3ポインタ更新処理による処理が最後に行われた前記関数フレームに設定することを特徴とする請求項6乃至請求項8のいずれかに記載のメモリ管理装置。
【請求項11】
請求項1乃至請求項5のいずれか一項に記載のメモリ管理方法をコンピュータに実行させるためのメモリ管理プログラムが記録されているコンピュータ読取可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、メモリ管理方法、メモリ管理装置、及びメモリ管理プログラムが記録されている記録媒体に関する。
【背景技術】
【0002】
Java(登録商標)言語等の動的にデータを生成するプログラミング言語を用いて作成されたプログラム(以下、主プログラム)は、生成したデータを動的にメモリ領域に記録するので、主プログラムの実行が進むことにより不要となったメモリ領域のデータを消去しなければ主プログラムが利用可能な空き領域(以下、利用可能領域という)が不足してしまう。そのため、従来から、メモリ領域内の不要なデータを消去し、メモリ領域を再利用する方法が知られている。
【0003】
メモリ領域内の不要なデータを消去し、その領域を再利用できるようにする処理はガーベッジコレクション(以下、GC)と呼ばれる。GC処理によって再利用可能となった利用可能領域を一箇所に集めて連続した領域にする処理はコンパクションと呼ばれる。メモリ領域を再利用できるようにするこれら一連の処理は、主プログラムを実行する場合に不可欠な処理である。主プログラムが実時間性を必要とする処理を実行する場合、GC処理及びコンパクション処理は、主プログラムの処理と実質的に並行して実行される必要がある。
【0004】
コンパクション処理は、利用可能領域を一箇所に集めるために、メモリ領域内の必要なデータを移動させた後、移動元データの位置を参照するポインタの参照先を、移動先データの位置に更新する処理を行う。コンパクション処理がデータを移動した後、ポインタの参照先を更新する前に、主プログラムが移動元データを参照したとき、ここにデータが存在しないため、主プログラムが処理異常を発生する。そのため、移動元データの位置を参照する全てのポインタの参照先が、移動先データの位置に更新されるまで、コンパクション処理を中断させることができない。その結果、主プログラムの実時間性が損なわれる。
【0005】
GC処理は、本発明者の一人により特許第3530887号に提案された発明によって、主プログラムの実時間性を損なわずに行うことができる。しかし、この発明は、連続した利用可能領域を生成するコンパクション処理を中断することができず、コンパクション処理が終了するまで主プログラムが処理を行うことができない。
【0006】
ところで、従来から、小型機器である携帯電話等には、組込み用Java(登録商標)処理系としてKVM(K virtual machine)が多く使われている。KVMには、上述したGC処理及びコンパクション処理を行うプログラム(以下、メモリ管理プログラム)が採用されており、このプログラムは、通常、メモリ領域内の利用可能領域が不足してきたときに、自動的に実行される。その結果、メモリ管理プログラムの処理を中断させることができないので、主プログラムの実行が数ミリ秒~数秒の間中断させられることがある。
【0007】
これに対して、従来の携帯電話は、主プログラムが実時間性を必要とする処理、例えば、なめらかな動作が必要なアニメーションやゲームのキャラクタを画面上で動かす処理などを行う場合、主プログラムの実行中にメモリ管理プログラムが自動的に実行されないように、実時間性を必要とする処理を行う直前に、強制的にメモリ管理プログラムを実行させるものがある。これにより、利用可能領域のサイズが大きくなり、しばらくの間はメモリ管理プログラムを実行する必要がないので、主プログラムは、実時間性を損なわずに処理を行うことができる。
【0008】
しかし、実時間性を必要とする処理の内容の違いや、携帯電話の機種によるメモリ領域のサイズや主プログラムを処理する実行処理速度の違いにより、強制的にメモリ管理プログラムを実行させるタイミングが異なることがある。そのため、開発者は、これらの違いを考慮して、メモリ管理プログラムを強制的に実行させるタイミングを設定しなければならず、開発に手間がかかり、開発効率が低下するという問題がある。
【0009】
ところで、非特許文献1には、GC処理後のメモリ領域全体に対して、例えば16分割したメモリ領域のうちの1つの領域を限定領域とし、この限定領域内のデータを、限定領域外のメモリ領域に一括して移動させた後、限定領域内のデータを参照するポインタの参照先を一括して更新するコンパクション処理が開示されている。しかし、このコンパクション処理では、データを移動した後に移動元を参照する全てのポインタの参照先を更新するまでの処理を一括して実行する必要があるので、コンパクション処理を中断して主プログラムの処理を行うことができない。そのため、主プログラムの実時間性が損なわれてしまう。
【0010】
また、非特許文献2には、メモリ領域を任意の数に分割し、このうちの1つをデータ移動先領域として設定した後、主プログラムがデータ移動先領域を除くメモリ領域にデータを記録する。そして、データ移動先領域を除くメモリ領域のうちの1つをデータ移動元領域とし、このデータ移動元領域のデータをデータ移動先領域に移動させることにより連続した利用可能領域を生成する処理が開示されている。しかし、この処理も、非特許文献1と同様に、コンパクション処理を中断して主プログラムを実行することができないので、主プログラムの実時間性が損なわれてしまう。また、この処理では、主プログラムがメモリ領域にデータが記録する前に、データ移動先領域を設定しなければならないので、メモリ領域に記録されるデータの記録状態等を加味した後に、データ移動先領域を設定することができず、効率良く利用可能領域を生成することができない。
【0011】
ところで、一般的に、主プログラムがメモリ領域からデータを読出す回数は、主プログラムがメモリ領域にデータを書込む回数よりもはるかに多い。そのため、データの読出し処理に特別な処理を追加すると、データの読出し時にオーバヘッドが掛かり、主プログラムの処理の実行効率が悪くなることがある。上述した非特許文献2の処理において、各データの先頭に最新のデータの位置を指すフォワーディングポインタを付加し、主プログラムがデータ要素を読み出すとき、フォワーディングポインタを辿って最新のデータの位置からデータ要素を読み出す方法が知られている。しかし、この処理でも、データの読出し時にオーバヘッドが掛かり、主プログラムの処理の実行効率が悪くなることがある。

【非特許文献1】Parallel Incremental Compaction (US 2004/0128329 A1)
【非特許文献2】Incremental Incrementally Compacting Garbage Collection(SIGPLAN Notice 22(7) pp.253-263)
【発明の開示】
【発明が解決しようとする課題】
【0012】
本発明は、上述した問題点を解決するためになされたものであり、連続した利用可能領域を生成する処理を中断して、主プログラムが処理を行うことができるメモリ管理方法、メモリ管理装置、及びメモリ管理プログラムが記録されている記録媒体を提供することを目的とする。
【課題を解決するための手段】
【0013】
上記目的を達成するために請求項1の発明は、メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理方法において、前記オブジェクトは、オブジェクトの複製先の位置又は複製元の位置を記録するための複製位置ポインタをさらに含み、前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定ステップと、前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、該複製元オブジェクト及び該複製先オブジェクトの複製位置ポインタの参照先を互いのオブジェクトの位置に設定するオブジェクト複製ステップと、前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第1ポインタ更新ステップと、前記限定範囲の領域を利用可能領域にする限定範囲利用可能化ステップと、前記オブジェクト複製ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断ステップと、前記複製判断ステップにより書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込みステップと、を含み、前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第3ポインタ更新ステップと、前記第3ポインタ更新ステップによるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新ステップによる処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定ステップと、をさらに備え、前記第1ポインタ更新ステップは、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁が、関数の実行完了後、前記第3ポインタ更新ステップによる処理を再開させるものである。
【0014】
請求項2の発明は、メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理方法において、前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、前記メモリ中に、オブジェクトの位置を記録するオブジェクト位置記録領域がさらに設けられ、前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定ステップと、前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、前記オブジェクト位置記録領域に、該複製元オブジェクトの位置及び該複製先オブジェクの位置を記録するオブジェクト複製ステップと、前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第1ポインタ更新ステップと、前記限定範囲の領域を利用可能領域にする限定範囲利用可能化ステップと、前記オブジェクト複製ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断ステップと、前記複製判断ステップにより書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込みステップと、を含み、前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、
前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第3ポインタ更新ステップと、前記第3ポインタ更新ステップによるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新ステップによる処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定ステップと、をさらに備え、前記第1ポインタ更新ステップは、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁が、関数の実行完了後、前記第3ポインタ更新ステップによる処理を再開させるである。
【0015】
請求項3の発明は、請求項1又は請求項2に記載のメモリ管理方法において、前記オブジェクトは、前記データ要素として前記オブジェクト位置ポインタをさらに含み、前記複製元オブジェクトの位置を参照する前記ヒープ領域内のオブジェクト位置ポインタの参照先を、前記オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する第2ポインタ更新ステップと、前記第2ポインタ更新ステップを実行中に、前記主プログラムが前記ヒープ領域に前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、該オブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に変更する参照先変更ステップと、前記第2ポインタ更新ステップの実行中に、前記主プログラムが2つのオブジェクト位置ポインタの参照先が同じオブジェクトの位置であるかどうかの検査処理を行うとき、該2つのオブジェクト位置ポインタのうちの一方が前記複製元オブジェクトの位置を、他方が前記複製先オブジェクトの位置を参照している場合、同一のオブジェクトを参照していると判断する同一判断ステップと、をさらに備え、前記複製判断ステップは、前記オブジェクト複製ステップ、又は前記第2ポインタ更新ステップを実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断するものである。
【0016】
請求項4の発明は、請求項1乃至請求項3のいずれかに記載のメモリ管理方法において、前記ヒープ領域内に、前記スタック領域を除く前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とし、前記範囲設定ステップは、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、前記第1ポインタ更新ステップは、前記限定範囲内の前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の前記データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、前記限定範囲及び前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新するものである。
【0017】
請求項5の発明は、請求項1乃至請求項3のいずれかに記載のメモリ管理方法において、前記ヒープ領域内に、前記スタック領域を含む前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とし、前記範囲設定ステップは、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、前記第1ポインタ更新ステップは、前記限定範囲内の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内に割当てられた、前記スタック領域を除く該データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、前記限定範囲外の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記第3ポインタ更新ステップは、前記ヒープ領域内に割当てられた前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、前記限定範囲内の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の該関数フレームを、該ヒープ領域内の利用可能領域に移動させ、前記限定範囲外の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁設定ステップは、前記第3ポインタ更新処理による処理を中断して、前記主プログラムを実行するときに、前記障壁を、該第3ポインタ更新処理による処理が最後に行われた前記関数フレームに設定するものである。
【0018】
請求項6の発明は、メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理装置において、前記オブジェクトは、オブジェクトの複製先の位置又は複製元の位置を記録するための複製位置ポインタをさらに含み、前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定手段と、前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、該複製元オブジェクト及び該複製先オブジェクトの複製位置ポインタの参照先を互いのオブジェクトの位置に設定するオブジェクト複製手段と、前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第1ポインタ更新手段と、前記限定範囲の領域を利用可能領域にする限定範囲利用可能化手段と、前記オブジェクト複製手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断手段と、前記複製判断手段により書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込み手段と、を備え、前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第3ポインタ更新手段と、前記第3ポインタ更新手段によるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新手段による処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定手段と、をさらに備え、前記第1ポインタ更新手段は、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁が、関数の実行完了後、前記第3ポインタ更新手段による処理を再開させるものである。
【0019】
請求項7の発明は、メモリ中に、動的にデータを生成するプログラム(以下、主プログラム)の実行等に利用されるデータが記録されたデータ記録領域と、主プログラムが実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域とが設けられ、主プログラムの実行が進むことにより不要となった前記ヒープ領域のオブジェクトを消去し、該ヒープ領域に利用可能な空き領域(以下、利用可能領域)を生成すると共に、該ヒープ領域に連続した利用可能領域を生成するために、該ヒープ領域に記録されているオブジェクトを移動させるメモリ管理装置において、前記データ記録領域に、前記オブジェクトの位置を参照するオブジェクト位置ポインタが記録され、前記メモリ中に、オブジェクトの位置を記録するオブジェクト位置記録領域がさらに設けられ、前記ヒープ領域に連続した利用可能領域を生成する限定範囲を設定する範囲設定手段と、前記限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、前記オブジェクト位置記録領域に、該複製元オブジェクトの位置及び該複製先オブジェクの位置を記録するオブジェクト複製手段と、前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第1ポインタ更新手段と、前記限定範囲の領域を利用可能領域にする限定範囲利用可能化手段と、前記オブジェクト複製手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断する複製判断手段と、前記複製判断手段により書込み先が前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであると判断されたとき、前記主プログラムが書込み処理を行うデータを、前記複製元オブジェクトの記録領域及び前記複製先オブジェクトの記録領域の両方に書込みを行う複製書込み手段と、を備え、前記データ記録領域中に、前記主プログラムが実行する関数の実行結果等を一時的に記録する関数フレームが積み上げられて配置されるスタック領域が設けられ、前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、この順に該スタック領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第3ポインタ更新手段と、前記第3ポインタ更新手段によるオブジェクト位置ポインタの更新処理を中断するときに、該第3ポインタ更新手段による処理が最後に行われた前記関数フレームに、関数の実行を制御する障壁を設定する障壁設定手段と、をさらに備え、前記第1ポインタ更新手段は、前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁が、関数の実行完了後、前記第3ポインタ更新手段による処理を再開させるものである。
【0020】
請求項8の発明は、請求項6又は請求項7に記載のメモリ管理装置において、前記オブジェクトは、前記データ要素として前記オブジェクト位置ポインタをさらに含み、前記複製元オブジェクトの位置を参照する前記ヒープ領域内のオブジェクト位置ポインタの参照先を、前記オブジェクト複製手段により複製された複製先オブジェクトの位置に更新する第2ポインタ更新手段と、前記第2ポインタ更新手段を実行中に、前記主プログラムが前記ヒープ領域に前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、該オブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に変更する参照先変更手段と、前記第2ポインタ更新手段の実行中に、前記主プログラムが2つのオブジェクト位置ポインタの参照先が同じオブジェクトの位置であるかどうかの検査処理を行うとき、該2つのオブジェクト位置ポインタのうちの一方が前記複製元オブジェクトの位置を、他方が前記複製先オブジェクトの位置を参照している場合、同一のオブジェクトを参照していると判断する同一判断手段と、をさらに備え、前記複製判断手段は、前記オブジェクト複製手段、又は前記第2ポインタ更新手段を実行中に、前記主プログラムが前記ヒープ領域に記録されたオブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、前記複製元オブジェクトの記録領域又は前記複製先オブジェクトの記録領域のいずれかであるかを判断するものである。
【0021】
請求項9の発明は、請求項6乃至請求項8のいずれかに記載のメモリ管理装置において、前記ヒープ領域内に、前記スタック領域を除く前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とし、前記範囲設定手段は、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、前記第1ポインタ更新手段は、前記限定範囲内の前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の前記データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、前記限定範囲及び前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新するものである。
【0022】
請求項10の発明は、請求項6乃至請求項8のいずれかに記載のメモリ管理装置において、前記ヒープ領域内に、前記スタック領域を含む前記データ記録領域の一部又は全部を割当て、該ヒープ領域内の該データ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とし、前記範囲設定手段は、前記ヒープ領域内の前記データ記録領域が割当てられた領域に対して限定範囲を設定することができ、前記第1ポインタ更新手段は、前記限定範囲内の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内に割当てられた、前記スタック領域を除く該データ記録領域を、前記ヒープ領域内の利用可能領域に移動させ、前記限定範囲外の前記スタック領域を除く前記データ記録領域に記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記第3ポインタ更新手段は、前記ヒープ領域内に割当てられた前記スタック領域内の前記関数フレームを上位から下位に向かって走査し、前記限定範囲内の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新すると共に、該限定範囲内の該関数フレームを、該ヒープ領域内の利用可能領域に移動させ、前記限定範囲外の前記関数フレームに記録されている、前記複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、前記複製先オブジェクトの位置に更新し、前記障壁設定手段は、前記第3ポインタ更新処理による処理を中断して、前記主プログラムを実行するときに、前記障壁を、該第3ポインタ更新処理による処理が最後に行われた前記関数フレームに設定するものである。
【0023】
請求項11の発明は、請求項1乃至請求項5のいずれか一項に記載のメモリ管理方法をコンピュータに実行させるためのメモリ管理プログラムが記録されているコンピュータ読取可能な記録媒体である。
【発明の効果】
【0028】
請求項1の発明によれば、主プログラムが複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、書込み処理を行うデータを、複製元データの記録領域及び複製先データの記録領域の両方に書込むことができる。そのため、複製元データと複製先データとのデータの整合性を保つことができ、連続した利用可能領域を生成する処理を中断して、主プログラムが処理を行うことができる。従って、主プログラムの処理の実時間性を損なわずに、ヒープ領域に連続した利用可能領域を生成することができる。また、請求項1の発明によれば、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに障壁を設定し、関数の実行完了後、障壁により、オブジェクト位置ポインタの更新処理が再開される。そのため、スタック領域内のオブジェクト位置ポインタの更新処理を中断して、主プログラムが関数を実行することができ、主プログラムの処理の実時間性を損なわずに、スタック領域のオブジェクト位置ポインタを更新することができる。
【0029】
請求項2の発明によれば、主プログラムが複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、書込み処理を行うデータを、複製元データの記録領域及び複製先データの記録領域の両方に書込むことができるので、請求項1と同様の効果を得られる。また、オブジェクト位置記録領域を参照して、複製元オブジェクトの位置及び複製先オブジェクトの位置や、複製元オブジェクトの記録領域及び複製先オブジェクトの記録領域を取得することができるので、オブジェクトは複製位置ポインタを有する必要がない。そのため、ヒープ領域の使用効率が良くなる。また、請求項2の発明によれば、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに障壁を設定し、関数の実行完了後、障壁により、オブジェクト位置ポインタの更新処理が再開される。そのため、スタック領域内のオブジェクト位置ポインタの更新処理を中断して、主プログラムが関数を実行することができ、主プログラムの処理の実時間性を損なわずに、スタック領域のオブジェクト位置ポインタを更新することができる。
【0030】
請求項3の発明によれば、主プログラムがヒープ領域に複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、オブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に変更することができる。そのため、これらの処理(コンパクション処理)終了後にオブジェクト位置ポインタの参照先にデータが存在しなくなることを防ぐことができるので、主プログラムが処理異常を発生することを防ぐことができ、連続した利用可能領域を生成する処理を中断して、主プログラムが処理を行うことができる。従って、主プログラムの処理の実時間性を損なわずに、ヒープ領域に連続した利用可能領域を生成することができる。
【0031】
請求項4の発明によれば、ヒープ領域内に、スタック領域を除くデータ記録領域を割当て、ヒープ領域内のデータ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とするので、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに障壁を設定し、関数の実行完了後、障壁により、オブジェクト位置ポインタの更新処理が再開される。そのため、スタック領域内のオブジェクト位置ポインタの更新処理を中断して、主プログラムが関数を実行することができ、主プログラムの処理の実時間性を損なわずに、スタック領域のオブジェクト位置ポインタを更新することができる。
【0032】
請求項5の発明によれば、ヒープ領域内に、スタック領域を含むデータ記録領域を割当て、ヒープ領域内のデータ記録領域外の領域を、請求項1乃至請求項3のいずれかに記載のヒープ領域とするので、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに障壁を設定し、関数の実行完了後、障壁により、オブジェクト位置ポインタの更新処理が再開される。そのため、スタック領域内のオブジェクト位置ポインタの更新処理を中断して、主プログラムが関数を実行することができ、主プログラムの処理の実時間性を損なわずに、スタック領域のオブジェクト位置ポインタを更新することができる。また、限定範囲内のスタック領域をヒープ領域内の利用可能領域に移動させる処理を中断して、主プログラムが処理を行うことができる。そのため、主プログラムの処理の実時間性を損なわずに、限定範囲内のスタック領域をヒープ領域内の利用可能領域に移動させる処理を行うことができる。
【0033】
請求項6の発明によれば、請求項1の発明と同様の効果を得ることができる。
【0034】
請求項7の発明によれば、請求項2の発明と同様の効果を得ることができる。
【0035】
請求項8の発明によれば、請求項3の発明と同様の効果を得ることができる。
【0036】
請求項9の発明によれば、ヒープ領域内に、スタック領域を除くデータ記録領域を割当て、ヒープ領域内のデータ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とするので、請求項4の発明と同様の効果を得ることができる。
【0037】
請求項10の発明によれば、ヒープ領域内に、スタック領域を含むデータ記録領域を割当て、ヒープ領域内のデータ記録領域外の領域を、請求項6乃至請求項8のいずれかに記載のヒープ領域とするので、請求項5の発明と同様の効果を得ることができる。
【0038】
請求項11の発明によれば、コンピュータにメモリ管理プログラムを読み取らせて、コンピュータ上でこのプログラムを実行することにより、請求項1乃至請求項5のいずれか一項に記載の発明と同様の効果が得られる。
【発明を実施するための最良の形態】
【0043】
以下、本発明の第1実施形態に係る携帯電話(メモリ管理装置)について、図1乃至図3を参照して説明する。以下の実施形態では、本発明のメモリ管理装置を携帯電話に適用した場合について説明する。図1は、携帯電話1の構成を示し、図2はフラッシュメモリ(記録媒体)17の構成を示し、図3は、データ記録領域21の構成を示す。携帯電話1は、動的なデータを生成するJava(登録商標)言語を用いて作成されたプログラム(以下、主プログラム)91、及び本発明のメモリ管理プログラム93の実行が可能である。
【0044】
携帯電話1は、音声を入力するためのマイク等の入力部12と、音声を出力するためのスピーカ等の出力部13と、ユーザによって操作されるキーを有する操作部14と、音声データ等の送受信を行うための通信部15と、メニューや通信状態等を表示するための表示部16とを備える、また、携帯電話1は、プログラム及びデータの情報が記録されたフラッシュメモリ17と、各種情報を一時的に記録するメモリ部(メモリ)18と、装置各部の制御を行うためのCPU11と、を備える。
【0045】
フラッシュメモリ17には、図2に示すように、主プログラム91と、主プログラム91の実行に必要なJava(登録商標) VM(Java(登録商標) Virtual Machine)等の実行環境プログラム92と、実行環境プログラム92の一部であるメモリ管理プログラム93と、各種設定情報等のデータ94等と、が記録されている。携帯電話1は、メモリ管理プログラム93をメモリ部18に読み取らせて、CPU11で実行することにより、本発明のメモリ管理装置として動作する。なお、メモリ管理プログラム93は、フラッシュメモリ17中に、主プログラム91の一部として記録されていてもよいし、独立したプログラムとして記録されていてもよい。
【0046】
メモリ部18には、主プログラム91の実行等に利用されるデータを記録するためのデータ記録領域21と、主プログラム91が実行中に使用するデータ要素を含むデータ(以下、オブジェクト)を記録するためのヒープ領域22と、フリーリスト23と、が設けられている。データ記録領域21は、特別なオブジェクト等の位置を参照するオブジェクト位置ポインタや、スタック領域27の位置を示すポインタや、プログラムの実行位置を示すデータ等が記録されている固定データ記録領域(図示せず)や、一時的なデータを記録する一時データ記録領域(図示せず)などを記録している。
【0047】
ヒープ領域22は、主プログラム91の実行によりオブジェクトが記録され、主プログラム91の実行過程において利用可能な空き領域(以下、利用可能領域)が次第に不足する。そのため、ヒープ領域22は、メモリ管理プログラム93により、主プログラム91の実行が進むことにより不要になったオブジェクトを消去するガーベッジコレクション(以下、GC)処理と、GC処理の後に必要に応じて連続した利用可能領域を生成するためのコンパクション処理とを含むメモリ管理処理が行われる。フリーリスト23は、ヒープ領域22内の利用可能領域の位置が記録されている。
【0048】
次に、スタック領域27の構成について、図4を参照して説明する。図4は、スタック領域27に記録された関数フレームを概念的に示したものである。関数フレームは、主プログラム91の実行に必要な関数(Java(登録商標)言語ではメソッドと呼ばれる)を記録する領域である。スタック領域27は、主プログラム91が実行する関数の実行結果等を一時的に記録する関数フレーム60a~60cが積み上げられて配置されている。実行中の関数フレームはカレントフレームと呼ばれ、図4では、関数フレーム60aがカレントフレーム70となる。
【0049】
主プログラム91の関数は、実行中の関数が、実行すべき関数を呼び出して処理を行う。関数が関数を呼び出すとき、スタック領域27内に確保された実行中の関数の関数フレームに、呼び出し元の関数は、新たな関数フレームを積み上げる形で確保し、呼び出し先の関数を実行する。そして、呼び出し先の関数の実行完了後、呼び出し元の関数の関数フレームは不要であるため、積み上げられている不要な関数フレームを破棄する。なお、スタック領域27内に積み上げられる関数フレームは、それぞれの位置がデータ記録領域21内の記録領域において隣接している必要は無い。
【0050】
次に、ヒープ領域22に記録されるオブジェクトの構成について、図5を参照して説明する。図5は、ヒープ領域22に記録されるオブジェクト30の一例を概念的に示すものである。オブジェクト30は、複製位置ポインタ50の参照先アドレス111と、データ要素121~123と、データ要素131と、を含むものから構成される。データ要素121~123は、数値や文字などの値が記録されているものであり、データ要素131はオブジェクト位置ポインタ40の参照先アドレスが記録されているものである。
【0051】
オブジェクト位置ポインタ40は、データ要素として、他のオブジェクトを参照するものであり、データ要素121~123とオブジェクト位置ポインタ40とは、主プログラム91によって使用される。複製位置ポインタ50は、オブジェクト30の複製先の位置又は複製元の位置を記録するためのものである。複製位置ポインタ50の参照先アドレス111は、オブジェクト30の先頭に記録されており、主プログラム91によって使用されない。オブジェクトが複製されていない場合、複製位置ポインタ50の参照先アドレス111には、「オブジェクトが複製されていない」という旨を示す特別な値が記録される。
【0052】
次に、メモリ管理プログラム93によるメモリ管理処理について図6を参照して説明する。携帯電話1は、ヒープ領域22の利用可能領域が不足したときに、メモリ管理プログラム93を実行することによりメモリ管理処理を行う。携帯電話1は、ヒープ領域22の利用可能領域がある基準値以下になったとき、ヒープ領域22の利用可能領域が不足していると判断する。なお、ヒープ領域22の利用可能領域の不足を判断する基準値は、任意に設定可能である。
【0053】
まず、メモリ管理プログラム93は、ヒープ領域22内の不要なオブジェクトを消去し、利用可能領域を生成するGC処理を行った後(S1)、ヒープ領域22内の利用可能領域をフリーリスト23に登録する(S2)。なお、GC処理は、本発明者により特許第3530887号に提案された発明によって、主プログラムの実時間性を損なわずに行うことができるが、これに限られず、主プログラムの実時間性を損なわずにGC処理を行うことができる他の方法を用いてGC処理を行ってもよい。
【0054】
そして、上記S2処理の後、ヒープ領域22内に連続した利用可能領域を生成するためにコンパクション処理を行う(S3)。コンパクション処理の詳細については後述する。上記S3処理の後、メモリ管理プログラム92は、データ記録領域21内のオブジェクト位置ポインタ更新処理を行う(S4)。オブジェクト位置ポインタ更新処理の詳細については後述する。上記S4処理の後、ヒープ領域22内の限定範囲(図7参照)を連続した利用可能領域としてフリーリスト23に登録し(S5:限定範囲利用可能化ステップ)、メモリ管理処理を終了する。
【0055】
次に、上記S3のコンパクション処理について、図7を参照して説明する。まず、メモリ管理プログラム93は、ヒープ領域22中に連続した利用可能領域を生成する限定範囲を設定し(S11:範囲設定ステップ)、この限定範囲内に含まれるオブジェクト(以下、複製元オブジェクト)をこの限定範囲外の利用可能領域に複製先のオブジェクト(以下、複製先オブジェクト)として複製すると共に、複製元オブジェクト及び複製先オブジェクトの複製位置ポインタの参照先を、互いのオブジェクトの位置に設定する(S12:オブジェクト複製ステップ)。なお、複製元オブジェクト及び複製先オブジェクトは、オブジェクトの一種であり、便宜上、上記のように呼ぶ。
【0056】
そして、ヒープ領域22内の複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、上記S12により複製された複製先オブジェクトの位置に更新し(S13:第2ポインタ更新ステップ)、コンパクション処理を終了する。なお、本処理では、上記S11により限定範囲を設定した後に、上記S12の処理を実行しているが、これに限らず、上記S12の処理中に限定範囲を設定してもよい。また、上記S11による限定範囲設定処理は、メモリ管理プログラム93に含まれない独立したプログラムであってもよい。上記S11による限定範囲設定処理が独立したプログラムである場合、このプログラムは、メモリ管理プログラム93の実行前に実行される。
【0057】
次に、上記S4のオブジェクト位置ポインタ更新処理について、図8を参照して説明する。メモリ管理プログラム93は、データ記録領域21に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新し(S21:第1ポインタ更新ステップ)、処理を終了する。データ記録領域21内のスタック領域27のオブジェクト位置ポインタ更新処理については、メモリ管理プログラム93が、スタック領域27の関数フレームを上位から下位に向かって走査する。そして、この順にスタック領域27に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、オブジェクト複製ステップにより複製された複製先オブジェクトの位置に更新する(S21:第3ポインタ更新ステップ)。
【0058】
次に、メモリ管理処理中のヒープ領域22の状態について、図9を参照して説明する。図9(a)(b)(c)は、メモリ管理処理を行った際のヒープ領域22の状態を概念的に示したものであり、図9(a)は上記S11の処理を、図9(b)は上記S12の処理を、図9(c)は上記S13の処理を行った際の状態に相当する。
【0059】
図9において、31~37、34a、35aはオブジェクト、41~44はオブジェクト位置ポインタ、51~54は複製位置ポインタ、Rは限定範囲を示す。なお、34と35は複製元オブジェクトになっており、34aと35aは複製先オブジェクトになっている。
【0060】
図9(a)に示すように、限定範囲Rには、複製元オブジェクト34、35が含まれ、オブジェクト31のオブジェクト位置ポインタ41は複製元オブジェクト34の位置を参照し、オブジェクト37のオブジェクト位置ポインタ42は複製元オブジェクト35の位置を参照している。オブジェクト32~36は、オブジェクト位置ポインタを保持していない。また、オブジェクト31~37のオブジェクトは複製されておらず、オブジェクト31~37の複製位置ポインタは他のオブジェクトの位置を参照していない。
【0061】
複製元オブジェクト34、35を複製すると、図9(b)に示すように、ヒープ領域22内の利用可能領域に複製先オブジェクト34a、35aとして複製される。このとき、複製先オブジェクト34aの複製位置ポインタ51が複製元オブジェクト34の位置を参照し、複製元オブジェクト34の複製位置ポインタ53が複製先オブジェクト34aの位置を参照するように複製位置ポインタ51及び複製位置ポインタ53が設定される。また、複製先オブジェクト35aの複製位置ポインタ52が複製元オブジェクト35の位置を参照し、複製元オブジェクト35の複製位置ポインタ54が複製先オブジェクト35aの位置を参照するように複製位置ポインタ52及び複製位置ポインタ54が設定される。
【0062】
そして、ヒープ領域22を走査して、オブジェクト31~37のオブジェクト位置ポインタが、限定範囲R内の複製元オブジェクト34、35を参照している場合、このオブジェクト位置ポインタの参照先を複製先オブジェクト34a、35aの位置に更新する。ここでは、図9(c)に示すように、オブジェクト31のオブジェクト位置ポインタ43の参照先を複製先オブジェクト34aの位置に、オブジェクト37のオブジェクト位置ポインタ44の参照先を複製先オブジェクト35aの位置に更新している。
【0063】
次に、上述したコンパクション処理の上記S12及び上記S13の処理中に、主プログラム91がヒープ領域22にデータの書込みを行う際の処理について、図10を参照して説明する。まず、メモリ管理プログラム93は、主プログラム91がヒープ領域22にデータの書込み処理を行うとき、又は書込み処理を行った後、データの書込み先の記録領域が、複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域のいずれかであるかを判断する(S31:複製判断ステップ)。そして、データの書込み先が複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域のいずれかであると判断されたとき(S32でYES)、メモリ管理プログラム93は、主プログラム91が書込むデータを、複製元オブジェクトの記録領域及び複製先オブジェクトの記録領域の両方に書込む(S33:複製書込みステップ)。
【0064】
一方、上記S31により、データの書込み先が複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域のいずれかでもないと判断されたとき(S32でNO)、上記S33の処理を行わず、主プログラム91がデータを書込む(S34)。なお、上記S31乃至上記S33の処理は、主プログラム91が、ヒープ領域22に記録されたオブジェクトの記録領域にデータの書込み処理を行った後、メモリ管理プログラム93は、主プログラム91により複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域のいずれかにだけデータが書込まれたかどうかを判断し(上記S31に相当)、この判断の結果、データの書込みがあった場合(上記S32でYESに相当)、メモリ管理プログラム93は、データが書込まれていない複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域のいずれかに、主プログラム91により書込まれたデータを書込む(上記S33に相当)処理により実現されてもよい。
【0065】
次に、上述したコンパクション処理の上記S13の処理中に、主プログラム91がヒープ領域22に複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込みを行う際の処理について、図11を参照して説明する。まず、メモリ管理プログラム93は、主プログラム91が、ヒープ領域22にオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、このオブジェクト位置ポインタの参照先が、複製元オブジェクトの位置であるかどうかを判断する(S41)。そして、このオブジェクト位置ポインタの参照先が、ヒープ領域22の複製元オブジェクトの位置である場合(S42でYES)、このオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に変更し(S43)、参照先を変更したオブジェクト位置ポインタを上記図10の処理手順に従って書込む(S44)。このとき、参照先を変更したオブジェクト位置ポインタは、上述した図10の処理中のデータに相当する。
【0066】
一方、上記S41により、オブジェクト位置ポインタの参照先が複製元オブジェクトの位置でない場合(S42でNO)、上記S43の処理は行わず、主プログラム91がオブジェクト位置ポインタをヒープ領域22に、上記図10の処理手順に従って書込む(S44)。なお、図10及び図11の処理は、主プログラム91又は実行環境プログラム92が行ってもよい。
【0067】
上述したように携帯電話1は、主プログラム91が複製元オブジェクトの記録領域又は複製先オブジェクトの記録領域にデータの書込み処理を行うとき、又は書込み処理を行った後、書込み処理を行うデータを、複製元データの記録領域及び複製先データの記録領域の両方に書込むことができる。そのため、複製元オブジェクトと複製先オブジェクトとのデータの整合性を保つことができる。従って、オブジェクトの複製処理を中断して主プログラム91が処理を行うことができる。
【0068】
また、主プログラム91が、ヒープ領域22に複製元オブジェクトの位置を参照するオブジェクト位置ポインタの書込み処理を行うとき、又は書込み処理を行った後、オブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に変更することができる。そのため、オブジェクト位置ポインタの参照先にデータが存在しないことを防ぐことができるので、主プログラム91が処理異常を発生することを防ぐことができる。従って、携帯電話1は、コンパクション処理を中断して、主プログラム91の処理を行うことができ、主プログラム91の処理の実時間性を損なわずに、ヒープ領域22に連続した利用可能領域を生成することができる。
【0069】
次に、スタック領域27に対する上述したオブジェクト位置ポインタ更新処理の上記S21の処理中に、主プログラム91が関数を実行する際の処理について、図12を参照して説明する。まず、メモリ管理プログラム93がオブジェクト位置ポインタの更新処理を中断するときに、メモリ管理プログラム93は、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに、関数の実行を制御する障壁を設定する(S51:障壁設定ステップ)。そして、主プログラム91が関数を実行し、この関数の実行が完了して関数フレームを破棄するとき(S52)、主プログラム91が、この関数フレームに障壁が設定されているどうか判断する(S53)。
【0070】
上記S53の結果、障壁が設定されている場合(S54でYES)、障壁がメモリ管理プログラム93による、スタック領域27のオブジェクト位置ポインタの更新処理を再開させ、メモリ管理プログラム93は、この関数フレームの下位に位置する関数フレーム内の複製元オブジェクトを参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新する(S55)。そして、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに、関数の実行を制御する障壁を再設定し、カレントフレームを下位の関数フレームに移動し、カレントフレームが移動した関数フレームの関数を実行する(S56)。
【0071】
一方、上記S53により、関数フレームに障壁が設定されていない場合(S54でNO)、上記S55の処理は行わず、上記S56の処理を行う。なお、上述した障壁の設定処理、及び障壁が設定されているかどうかの判断処理は、実行環境プログラム92が行ってもよい。また、本処理によりスタック領域27のオブジェクト位置ポインタの更新が行われる場合、スタック領域27を除くデータ記録領域21に対して、上述した図8によるオブジェクト位置ポインタの更新処理が行われる。
【0072】
次に、上記図12に示したオブジェクト位置ポインタ処理中のスタック領域27の状態について、図13を参照して説明する。図13は、スタック領域27を概念的に示した図であり、(a)は、上記S52の処理に相当し、(b)は上記S56の処理に相当する。図13において、61~64は関数フレーム、70はカレントフレーム、80は障壁を示す。
【0073】
図13(a)に示すように、カレントフレーム70は関数フレーム61に位置し、このとき、関数フレーム61のオブジェクト位置ポインタは既に更新されている。この関数フレーム61の関数の実行が完了したとき、設定されている障壁80により、メモリ管理プログラム93が関数フレーム62のオブジェクト位置ポインタの更新処理を行う。そして、関数フレーム62のオブジェクト位置ポインタの更新後、図13(b)に示すように、メモリ管理プログラム93は、関数フレーム62に対して障壁80を設定し、カレントフレーム70を関数フレーム62に移動させ、主プログラム91が関数フレーム62の関数を実行する。なお、上記S55において、複数の関数フレームのオブジェクト位置ポインタを更新してもよい。
【0074】
上述したように、携帯電話1は、オブジェクト位置ポインタの更新処理が最後に行われた関数フレームに障壁を設定し、関数の実行完了後、障壁により、オブジェクト位置ポインタの更新処理を再開される。そのため、オブジェクト位置ポインタの更新処理を中断して、主プログラムが実行する関数を実行することができ、主プログラム91による関数の処理の実時間性を損なわずに、スタック領域のオブジェクト位置ポインタを更新することができる。また、スタック領域27内のオブジェクト位置ポインタの更新処理を分割して行うことができるので、主プログラム91の処理の実時間性を損なわない。
【0075】
次に、上述したコンパクション処理の上記S13の処理中における、2つのオブジェクト位置ポインタの比較処理について、図14を参照して説明する。ここでは、主プログラム91が、ヒープ領域22から読出し処理などを行うことにより、2つのオブジェクト位置ポインタを得ているものとする。まず、主プログラム91は、2つのオブジェクト位置ポインタを比較し(S61)、同一のオブジェクトを参照している場合(S62でYES)、同一のオブジェクトを参照しているものと判断し(S65)、同一判断処理を終了する。
【0076】
一方、同一のオブジェクトを参照していない場合(S62でNO)、一方のオブジェクト位置ポインタが参照するオブジェクトの複製位置ポインタと他方のオブジェクト位置ポインタを比較する(S63)。そして、これらのポインタが同一のオブジェクトを参照しているとき(S64でYES)、上記S65の判断を行い、同一判断処理を終了する。また、上記S63で、これらのポインタが同一のオブジェクトを参照していないとき(S64でNO)、異なるオブジェクトを参照しているものと判断し(S66)、同一判断処理は終了する。なお、上記図14の処理は実行環境プログラム92が行ってもよい。
【0077】
上記S61の結果、2つのオブジェクト位置ポインタのうちの一方が複製元オブジェクトの位置を、他方が複製先オブジェクトの位置を参照している場合(S62でYES)、メモリ管理プログラム93は、2つのオブジェクト位置ポインタが同一のオブジェクトを参照していると判断し(S63:同一判断ステップ)、処理を終了する。一方、上記S61の結果、2つのオブジェクト位置ポインタのうちの一方が複製元オブジェクトの位置を、他方が複製先オブジェクトの位置を参照していない場合(S62でNO)、上記S63の処理は行わないで処理を終了する。これにより、携帯電話1は、2つのオブジェクト位置ポインタが、同一のオブジェクトを参照しているかどうか判断することができる。
【0078】
上記のように、本実施形態に係る携帯電話1によれば、ヒープ領域22内に連続した利用可能領域を生成する処理を中断して、主プログラム91が処理を行うことができるので、主プログラム91の処理の実時間性を損なわない。そのため、開発者が、従来のように、携帯電話の機種毎によるメモリ部18のサイズの違い等により、メモリ管理プログラム93を強制的に実行させるタイミングを設定する必要がないので、開発効率が良くなり、開発期間が短縮する。
【0079】
また、主プログラム91がヒープ領域22にデータやオブジェクト位置ポインタの書込みを行うときに、書込み先の記録領域と書込むポインタの参照先を判断する処理を追加する。主プログラム91は、一般的に、ヒープ領域22への読出し処理よりも書込み処理を行う回数の方が少ないので、ヒープ領域22からオブジェクトを読出す際に処理を追加する場合よりも、主プログラム91の実行時にオーバヘッドが小さい。
【0080】
また、GC処理を行った後に、限定範囲の設定をすることができるので、利用可能領域や利用しているデータ量等のさまざまな要因を加味して限定範囲の設定をすることができるので、効率良く利用可能領域を生成することができる。
【0081】
次に、本発明の第2実施形態に係る携帯電話について、図15を参照して説明する。図15は、本実施形態の携帯電話1の構成を示す。携帯電話1は、メモリ部18が位置記録リスト(オブジェクト位置記録領域)24をさらに有していること、及びヒープ領域22に記録されるオブジェクトが複製位置ポインタを含んでいないこと以外は、第1実施形態に示した携帯電話1と同様の構成である。位置記録リスト24は、第1実施形態における複製位置ポインタに相当する、ヒープ領域22内のオブジェクトの位置を記録するためのリストである。ヒープ領域22内に記録されているオブジェクトは、データ要素と、オブジェクト位置ポインタと、を含むものから構成されている。
【0082】
次に、位置記録リスト24について、図16を参照して説明する。図16は、複製元オブジェクトの位置及び複製先オブジェクトの位置が記録されている位置記録リスト24の一例を示す。図16に示すように、位置記録リスト24は、隣接する複数の複製元オブジェクトを複製元オブジェクト群として、隣接する複数の複製先オブジェクトを複製先オブジェクト群としてまとめて記録し、複製元オブジェクト群の起点及び終点の位置と、この複製元オブジェクト群に対応する複製先オブジェクト群の起点及び終点の位置が、ヒープ領域22内のアドレスを示す数値で記録されている。そのため、複製元オブジェクトの位置、複製先オブジェクトの位置、複製元オブジェクトの記録領域、又は複製先オブジェクトの記録領域の取得を行うとき、メモリ管理プログラム93は、位置記録リスト24を参照する。
【0083】
次に、携帯電話1のコンパクション処理について、図17を参照して説明する。まず、メモリ管理プログラム93は、ヒープ領域22中に連続した利用可能領域を生成する限定範囲を設定し(S71)、この限定範囲内に含まれる複製元オブジェクトをこの限定範囲外の利用可能領域に複製先オブジェクトとして複製すると共に、位置記録リスト24に、複製元オブジェクトの位置及び複製先オブジェクの位置を記録する(S72)。
【0084】
そして、メモリ管理プログラム93は、位置記録リスト24を参照して、ヒープ領域22内の複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、上記S72により複製された複製先オブジェクトの位置に更新し(S73)、ヒープ領域22のコンパクション処理を終了する。
【0085】
上記のように、本実施形態に係る携帯電話1によれば、第1実施形態に係る携帯電話と同様の効果を得ることができる。また、位置記録リスト24を参照して、複製元オブジェクトの位置及び複製先オブジェクトの位置や、複製元オブジェクトの記録領域及び複製先オブジェクトの記録領域を取得することができるので、オブジェクトは複製位置ポインタを有する必要がない。そのため、ヒープ領域22の使用効率が良くなる。
【0086】
次に、本発明の第3実施形態に係る携帯電話について、図18及び図19を参照して説明する。図18は、本実施形態の携帯電話1の構成を示し、図19はヒープ領域25内のデータ記録領域26の割当て状態を示す。携帯電話1は、ヒープ領域25内にデータ記録領域26の一部が割り当てられていること以外は、第1実施形態に示した携帯電話1の構成と同様である。スタック領域27は、図19に示すように、ヒープ領域25内に割当てられていない。
【0087】
携帯電話1は、ヒープ領域25内のデータ記録領域26外の領域を、第1実施形態に係る携帯電話のヒープ領域とすることができる。メモリ管理プログラム93は、ヒープ領域25内の前記データ記録領域26が割当てられた領域に対しても限定範囲を設定することができる。
【0088】
次に、メモリ管理プログラム93による限定範囲内のデータ記録領域26のコンパクション処理について、図20を参照して説明する。まず、メモリ管理プログラム93は、限定範囲内のデータ記録領域26に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新すると共に、限定範囲内のデータ記録領域26を、ヒープ領域25内の利用可能領域に移動させる(S81)。
【0089】
そして、限定範囲及びスタック領域27を除くデータ記録領域26に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新し(S82)、処理を終了する。これにより、ヒープ領域25に割当てられているデータ記録領域26に対してもコンパクション処理を行うことができるので、ヒープ領域25内に連続した利用可能領域を効率良く生成することができる。
【0090】
上記のように、本実施形態に係る携帯電話1によれば、ヒープ領域25にデータ記録領域26の一部が割当てられている場合であっても、第1実施形態の携帯電話と同様の効果を得ることができる。なお、ここでは、ヒープ領域25にデータ記録領域26の一部が割当てられている場合を示したが、ヒープ領域25に、スタック領域27を除くデータ記録領域26の全部が割当てられてもよい。この場合であっても、携帯電話1は、第1実施形態の携帯電話と同様の効果を得ることができる。
【0091】
また、本実施形態に係る携帯電話1のメモリ部18が、オブジェクトの位置を記録するための位置記録リスト24をさらに有し、ヒープ領域25に記録されているオブジェクトが複製位置ポインタを有しない場合、本実施形態に係る携帯電話1は、第2実施形態に係る携帯電話と同様の効果を得ることができる。
【0092】
次に、本発明の第4実施形態に係る携帯電話について、図21を参照して説明する。図21は、ヒープ領域25内のデータ記録領域26の割当て状態を示す。携帯電話1は、ヒープ領域25内にデータ記録領域26の一部が割り当てられると共に、スタック領域27がヒープ領域25内に割当てられていること以外は、第3実施形態に示した携帯電話1の構成と同様である。
【0093】
次に、メモリ管理プログラム93による限定範囲内のデータ記録領域26のコンパクション処理について、図22を参照して説明する。まず、メモリ管理プログラム93は、限定範囲内のスタック領域27を除くデータ記録領域26に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新すると共に、限定範囲内に割当てられた、スタック領域27を除くデータ記録領域26を、ヒープ領域25内の利用可能領域に移動させる(S91)。
【0094】
そして、限定範囲外のスタック領域27を除くデータ記録領域26に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新し(S92)、処理を終了する。これにより、ヒープ領域25に割当てられている、スタック領域27を除くデータ記録領域26に対してもコンパクション処理を行うことができるので、ヒープ領域25内に連続した利用可能領域を効率良く生成することができる。
【0095】
次に、メモリ管理プログラム93による限定範囲内のスタック領域27のコンパクション処理について、図23を参照して説明する。まず、メモリ管理プログラム93は、限定範囲内の関数フレームの移動先を決定し(S101)、ヒープ領域25内に割当てられたスタック領域27内の関数フレームを上位から下位に向かって走査する(S102)。そして、限定範囲内の関数フレームに記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新すると共に、限定範囲内の関数フレームを、ヒープ領域25内の利用可能領域に移動させる(S103)。
【0096】
そして、限定範囲外の関数フレームに記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新し(S104)、処理を終了する。これにより、ヒープ領域25内のスタック領域27に対してもコンパクション処理を行うことができるので、ヒープ領域25内に連続した利用可能領域を効率良く生成することができる。
【0097】
上記のように、本実施形態に係る携帯電話1によれば、スタック領域27がヒープ領域25内に割当てられている場合であっても、第3実施形態の携帯電話と同様の効果を得ることができる。なお、ここでは、ヒープ領域26にデータ記録領域26の一部が割当てられている場合を示したが、ヒープ領域26に、データ記録領域26の全部が割当てられてもよい。この場合であっても、携帯電話1は、第3実施形態の携帯電話と同様の効果を得ることができる。また、スタック領域27の一部がヒープ領域25外に割当てられている場合でもよく、この場合であっても、携帯電話1は、第3実施形態の携帯電話と同様の効果を得ることができる。
【0098】
次に、メモリ管理プログラム93をコンピュータ上で実行した場合の主プログラムの最大停止時間の実験結果について説明する。本実験で使用したコンピュータの性能は、CPUが「Xeon 3.2GHz」、メモリが1GBである。実験方法は、このコンピュータに、ヒープ領域が5MBであるJava(登録商標)実行環境を実装し、JAKLD(Java(登録商標) Application Kumikomi Lisp Driver:LISP処理系:情報処理学会論文誌 プログラミング 44巻 p1~16参照)上でBoyerベンチマークを実行することにより、メモリ管理プログラム93による主プログラムの最大停止時間を測定した。なお、メモリ管理プログラム93のGC処理は、特許3530887号で本発明者が提案した処理を利用している。また、本実験では、データ記録領域及びスタック領域がヒープ領域内に割当てられている。
【0099】
まず、従来の一括してコンパクション処理を行う方法の場合、主プログラムの最大停止時間は9.5msであった。一方、本発明のメモリ管理プログラム93による主プログラムの最大停止時間は0.7msであった。
【0100】
なお、本発明は、上記各実施形態の構成に限られず、発明の趣旨を変更しない範囲で種々の変形が可能である。例えば、上記各実施形態では、本発明のメモリ管理装置を携帯電話に適用した例を示したが、これに限られず、例えば、コンピュータに適用したものであってもよい。また、上記各実施形態の携帯電話1では、フラッシュメモリ17にメモリ管理プログラム93が記録されている例を示したが、これに限らず、他の記憶媒体にメモリ管理プログラム93が記録されていてもよく、また、通信部15を用いて、インターネット上からメモリ管理プログラム93をダウンロードして、携帯電話に実行させるものであってもよい。また、CPU11内のレジスタをデータ領域とし、メモリ管理プログラム93が、レジスタに対して処理を行ってもよい。
【0101】
また、上記各実施形態のメモリ管理プログラム93は、データ記録領域に記録されている、複製元オブジェクトの位置を参照するオブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に更新する処理中に、主プログラム91がデータ記録領域に複製元オブジェクトの位置を参照するオブジェクト位置ポインタを書込む処理を行うとき、又は書込み処理を行った後、オブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に変更する処理と、主プログラム91がヒープ領域に、複製元オブジェクトの位置を参照するオブジェクト位置ポインタを書込む処理を行うとき、又は書込み処理を行った後、オブジェクト位置ポインタの参照先を、複製先オブジェクトの位置に変更する処理と、をさらに行うものであってもよい。
【図面の簡単な説明】
【0102】
【図1】本発明の第1実施形態に係る携帯電話の構成を示すブロック図。
【図2】上記携帯電話のフラッシュメモリの構成を示すブロック図。
【図3】上記携帯電話のデータ記録領域の構成を示すブロック図。
【図4】上記携帯電話のスタック領域の構成を説明する図。
【図5】上記携帯電話のヒープ領域に記録されるオブジェクトの構成を説明する図。
【図6】上記携帯電話におけるメモリ管理処理手順を示すフローチャート。
【図7】上記メモリ管理処理におけるコンパクション処理手順を示すフローチャート。
【図8】上記メモリ管理処理におけるオブジェクト位置ポインタ更新手順を示すフローチャート。
【図9】(a)(b)(c)は、上記携帯電話のヒープ領域におけるコンパクション処理を説明する図。
【図10】上記携帯電話のヒープ領域のコンパクション処理中にデータを書込む処理手順を示すフローチャート。
【図11】上記携帯電話のヒープ領域のコンパクション処理中にオブジェクト位置ポインタを書込む処理手順を示すフローチャート。
【図12】上記携帯電話のスタック領域におけるオブジェクト位置ポインタ更新処理手順を示すフローチャート。
【図13】(a)(b)は、上記携帯電話のスタック領域における障壁設定処理を説明する図。
【図14】上記携帯電話のオブジェクト位置ポインタの同一判断処理手順を示すフローチャート。
【図15】本発明の第2実施形態に係る携帯電話の構成を示すブロック図。
【図16】上記携帯電話の位置記録リストの一例を示す図。
【図17】上記携帯電話のヒープ領域のコンパクション処理手順を示すフローチャート。
【図18】本発明の第3の実施形態に係る携帯電話の構成を示すブロック図。
【図19】上記携帯電話のヒープ領域とデータ記録領域とスタック領域の状態を示す説明図。
【図20】上記携帯電話のデータ記録領域のコンパクション処理手順を示すフローチャート。
【図21】本発明の第3の実施形態に係る携帯電話のヒープ領域とデータ記録領域とスタック領域の状態を示す説明図。
【図22】上記携帯電話のデータ記録領域のコンパクション処理手順を示すフローチャート。
【図23】上記携帯電話のスタック領域のコンパクション処理手順を示すフローチャート。
【符号の説明】
【0103】
1 携帯電話(メモリ管理装置)
11 CPU
12 入力部
13 出力部
14 操作部
15 通信部
16 表示部
17 フラッシュメモリ(記録媒体)
18 メモリ部(メモリ)
21 データ記録領域
22 ヒープ領域
24 位置記録リスト(オブジェクト位置記録領域)
25 ヒープ領域
26 データ記録領域
27 スタック領域
30 オブジェクト
31~33 オブジェクト
36 オブジェクト
37 オブジェクト
34 複製元オブジェクト
35 複製元オブジェクト
34a 複製先オブジェクト
35a 複製先オブジェクト
40~44 オブジェクト位置ポインタ
50~54 複製位置ポインタ
60a~60c 関数フレーム
61~64 関数フレーム
70 カレントフレーム
80 障壁
91 主プログラム
93 メモリ管理プログラム
94 データ
121~123 データ要素
R 限定範囲
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22