(57)【要約】【課題】  組み込み機器の小さなメモリ領域においてもガベージコレクションの効果を高くし、処理の実時間性の保持を容易にする。【解決手段】  空き領域取得手段１ａは、メモリ２に散在している空き領域の大きさを取得する。使用領域移動手段１ｂは、メモリ２に散在している使用領域を所定のアドレスから詰めるように移動する。両領域移動手段１ｃは、使用領域が所定の大きさより小さい空き領域に隣接している場合、使用領域を空き領域とともに移動する。移動量格納手段１ｄは、使用領域移動手段１ｂより移動された使用領域の移動量および両領域移動手段１ｃより移動された空き領域と使用領域との全体の移動量をメモリ２に格納する。【選択図】  図１
2005242617.tif 000002
【特許請求の範囲】
【請求項１】
ガベージコレクションを行うメモリ管理プログラムにおいて、
コンピュータを、
メモリに散在している空き領域の大きさを取得する空き領域取得手段、
前記メモリに散在している使用領域を所定のアドレスから詰めるように移動する使用領域移動手段、
前記使用領域が所定の大きさより小さい前記空き領域に隣接している場合、前記使用領域を前記空き領域とともに移動する両領域移動手段、
前記使用領域移動手段より移動された前記使用領域の移動量および前記両領域移動手段より移動された前記空き領域と前記使用領域との全体の移動量を前記メモリに格納する移動量格納手段、
として機能させることを特徴とするメモリ管理プログラム。
【請求項２】
前記両領域移動手段は、
前記メモリに展開されるデータの領域が前記使用領域の移動によって前記メモリに確保できるように予め前記所定の大きさを算出する第１の算出手段と、
許容される時間内で前記使用領域の移動を終えることができるための前記所定の大きさを予め算出する第２の算出手段と、
前記第１の算出手段により算出された前記所定の大きさと前記第２の算出手段により算出された前記所定の大きさとを比較して一方を選択する選択手段と、
を有することを特徴とする請求項１記載のメモリ管理プログラム。
【請求項３】
前記移動量格納手段は、最大の大きさを有する前記空き領域に前記移動量を格納することを特徴とする請求項１記載のメモリ管理プログラム。
【請求項４】
前記移動量格納手段は、前記空き領域に前記移動量が格納できなくなった場合、新たに最大の大きさを有する前記空き領域を検索し、前記移動量を格納することを特徴とする請求項３記載のメモリ管理プログラム。
【請求項５】
ガベージコレクションが行われる組み込み機器において、
メモリに散在している空き領域の大きさを取得する空き領域取得手段と、
前記メモリに散在している使用領域を所定のアドレスから詰めるように移動する使用領域移動手段と、
前記使用領域が所定の大きさより小さい前記空き領域に隣接している場合、前記使用領域を前記空き領域とともに移動する両領域移動手段と、
前記使用領域移動手段より移動された前記使用領域の移動量および前記両領域移動手段より移動された前記空き領域と前記使用領域との全体の移動量を前記メモリに格納する移動量格納手段と、
を有することを特徴とする組み込み機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリ管理プログラムおよび組み込み機器に関し、特にガベージコレクションを行うメモリ管理プログラムおよび組み込み機器に関する。
【背景技術】
【０００２】
近年、多くのプログラミング言語処理系において、自動メモリ管理（ガベージコレクション）機能が備えられるようになってきている。この機能は、従来プログラマが明示的に行っていた割付済み記憶領域の開放作業を自動的に行うため、プログラムの不具合の数、メモリの無駄遣いを減らすことに大きく貢献している。
【０００３】
ガベージコレクションは、メモリに散在している空き領域をかき集め、連続性を必要とするデータをその領域に展開できるようにする。これによって、例えば、地図データやサウンドデータなど、連続したデータをメモリに展開でき、処理が途切れることなく画面に地図を表示し、また、サウンドを発生することができる。
【０００４】
携帯電話などの組み込み機器では、メモリ領域、処理能力に上限がある。組み込み機器は、このような条件下において実時間性が求められるため、できるだけ少ない作業領域、短い時間でメモリの空き領域の回収を行うことが求められる。しかし、ガベージコレクションは、システムに大きな負担をかける。
【０００５】
そこで、少ないメモリ領域でも動作するブレークテーブル式コンパクションガベージコレクションがある（例えば、非特許文献３参照）。この方式は、以下の１〜４の手順に従って処理が進められる。１．ガベージコレクション時に、１つの連続した使用されているデータの集まり（使用領域）をメモリの片側に移動する。２．移動した使用領域の移動量を、メモリの空き領域上のブレークテーブルに保存する。移動量は、例えば、メモリ上のＮ番地から始まる使用領域がＭワード移動されたという情報である。３．その他の使用領域も移動し、その移動量をメモリの空き領域上のブレークテーブルに保存する。４．メモリを走査し、他のアドレスのデータを参照する参照アドレスを見つけると、ブレークテーブルを参照して、適正な参照先アドレスに更新する。
【０００６】
図１５は、ブレークテーブル式コンパクションガベージコレクションを説明するための説明図である。
図の（ａ）〜（ｃ）は上記手順の１〜３までのメモリ内容を示している。図の塗り潰している部分は、使用されているデータの集まり（使用領域）を示す。空白部分は、メモリの空き領域を示す。ブレークテーブル１０２は、移動した使用領域の移動量が格納されるテーブルである。ブレークテーブル１０２は、メモリの先頭空き領域の最後尾に構成される。
【０００７】
図の（ａ）に示すように、使用領域の間に空き領域が存在している。図の（ａ），（ｂ）に示すように、使用領域１０１をメモリの片側に移動し、移動量をブレークテーブル１０２に保存する。そして、図の（ｃ）に示すように、その他の使用領域もメモリの片側に移動し、移動量をブレークテーブル１０２に保存する。このようにして、メモリの使用していない空き領域の回収を行う。
【０００８】
なお、空き領域が別のデータで上書きされたり，ブレークテーブルの大きさが空き領域サイズを上回ったりすると、ブレークテーブル１０２が移動させられる。従って、ブレークテーブル１０２の移動にも、処理負担が課せられる。また、ブレークテーブル１０２の大きさは、移動した使用領域の数に比例する。
【０００９】
一方、短い時間でメモリ領域の回収を行うインクリメンタルコンパクション型ガベージコレクションがある（例えば、非特許文献１，２参照）。この方式は、メモリ領域中の一部分だけに対してコンパクションを行う。
【００１０】
図１６は、インクリメンタルコンパクション型ガベージコレクションを説明するための説明図である。
図の（ａ）はコンパクション前、（ｂ）はコンパクション後のメモリ内容を示している。図の塗り潰している部分は、使用されているデータの集まり（使用領域）を示す。空白部分は、メモリの空き領域を示す。コンパクション対象領域１１２は、メモリのコンパクションが行われる領域の範囲を示している。
【００１１】
図の（ａ）に示すように、使用領域の間に空き領域が存在している。コンパクション型ガベージコレクションでは、図の（ａ），（ｂ）に示すように、コンパクション対象領域１１２内での使用領域１１１をメモリの片側に移動する。
【００１２】
なお、コンパクション以外によるガベージコレクションで、回収対象を高速に検索するガベージコレクション（例えば、特許文献１参照）、アドレス変換のコストを削減するガベージコレクションがある（例えば、特許文献２参照）。
【非特許文献１】Bernard Lang and Francis Dupont,"Incremental incrementally compacting garbage collection",ACM SIGPLAN Notices,Volume22 Issue7 p.253-263,U.S.,7.1987.
【非特許文献２】Ori Ben-Yitzhak et al.,"An algorithm for Parallel Incremental Compaction",ACM SIGPLAN Notices,Volume38 Issue2 p.100-105,U.S.,2.2003.
【非特許文献３】B. K. Haddon and W. M. Waite,"A compaction procedure for variable length storage elements",Computer Journal,Volume10 Issue2 p.162-165, U.K.,8.1967.
【特許文献１】特開２００１−３４５３２号公報（段落番号〔００３１〕〜〔００３３〕、図２，３）
【特許文献２】特開平４−４９４４０号公報（第３頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記のブレークテーブル式コンパクションガベージコレクションでは、ブレークテーブルが大きくなると処理負担が大きくなる。そのため、処理能力に上限がある組み込み機器では、実時間性の保持が困難であるという問題点がある。
【００１４】
また、インクリメンタルコンパクション型ガベージコレクションでは、大きなメモリ領域の一部に不要となったメモリ領域が集中している場合には、ガベージコレクションの効果は大きいが、組み込み機器の限られた小さなメモリに不要なメモリ領域が散在している場合には、効果が小さいという問題点がある。
【００１５】
本発明はこのような点に鑑みてなされたものであり、実時間性の保持が容易で、小さなメモリ領域においてもガベージコレクションの効果を高くすることができるメモリ管理プログラムおよび組み込み機器を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明では上記問題を解決するために、図１に示すようなガベージコレクションを行うメモリ管理プログラムにおいて、コンピュータ１を、メモリ２に散在している空き領域の大きさを取得する空き領域取得手段１ａ、メモリ２に散在している使用領域を所定のアドレスから詰めるように移動する使用領域移動手段１ｂ、使用領域が所定の大きさより小さい空き領域に隣接している場合、使用領域を空き領域とともに移動する両領域移動手段１ｃ、使用領域移動手段１ｂより移動された使用領域の移動量および両領域移動手段１ｃより移動された空き領域と使用領域との全体の移動量をメモリ２に格納する移動量格納手段１ｄ、として機能させることを特徴とするメモリ管理プログラムが提供される。
【００１７】
このようなメモリ管理プログラムによれば、所定の大きさより小さい空き領域に隣接している使用領域を、その空き領域とともに移動する。そして、移動された使用領域の移動量およびともに移動された使用領域と空き領域との全体の移動量をメモリ２に格納する。よって、移動する使用領域の移動回数、移動量のメモリ２への格納回数が低減され、また、小さなメモリにおいてもガベージコレクションの効果を高くできる。
【発明の効果】
【００１８】
本発明のメモリ管理プログラムによれば、所定の大きさより小さい空き領域に隣接している使用領域を、その空き領域とともに移動し、移動された使用領域の移動量およびともに移動された使用領域と空き領域との全体の移動量をメモリに格納する。これによって、移動する使用領域の移動回数、移動量のメモリへの格納回数が低減され、実時間性の保持が容易となり、また、小さなメモリにおいてもガベージコレクションの効果を高くすることができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の原理を図面を参照して詳細に説明する。
図１は、本発明の原理を説明する原理図である。
図に示すコンピュータ１は、ガベージコレクションを行うメモリ管理プログラムを実行することによって、空き領域取得手段１ａ、使用領域移動手段１ｂ、両領域移動手段１ｃ、移動量格納手段１ｄ、および参照更新手段１ｅを有している。コンピュータ１はメモリ２と接続されている。なお、図１には、メモリ２の５つの状態（ステップＳ１〜Ｓ５）が示してある。ステップＳ１〜Ｓ５に示しているメモリ２の塗り潰している部分は使用領域、空白部分は空き領域を示す。テーブル５ａは、移動された使用領域の移動量および移動された使用領域と空き領域との全体の移動量が格納されるテーブルである。
【００２０】
空き領域取得手段１ａは、メモリ２に散在している空き領域の大きさを取得する。空き領域とは、データの格納に使用されていない領域である。
使用領域移動手段１ｂは、メモリ２に散在している使用領域を所定のアドレスから詰めるように移動する。所定のアドレスは、例えば、メモリ２の先頭アドレスである。使用領域とは、データの格納に使用されている領域である。
【００２１】
両領域移動手段１ｃは、使用領域が所定の大きさより小さい空き領域に隣接している場合、使用領域をその空き領域とともに移動する。
移動量格納手段１ｄは、使用領域移動手段１ｂより移動された使用領域の移動量および両領域移動手段１ｃより移動された空き領域と使用領域との全体の移動量をメモリ２のテーブル５ａに格納する。
【００２２】
参照更新手段１ｅは、移動格納手段１ｄによって格納された移動量のテーブル５ａを参照し、メモリ２内の参照関係を更新する。そして、参照更新手段１ｅは、全ての参照関係を更新し終えたらテーブル５ａを破棄する。
【００２３】
以下、図１の動作について説明する。
空き領域取得手段１ａは、メモリ２に散在している空き領域の大きさを取得する。
使用領域移動手段１ｂは、図のステップＳ１に示すメモリ２に散在している使用領域３ａを、ステップＳ２に示すように先頭のアドレスから詰めるように移動する。移動量格納手段１ｄは、使用領域移動手段１ｂより移動された使用領域３ａの移動量をテーブル５ａに格納する。
【００２４】
ステップＳ２に示す空き領域４ａを所定の大きさより小さい空き領域とする。両領域移動手段１ｃは、所定の大きさより小さい空き領域４ａに隣接している使用領域３ｂ，３ｃを、ステップＳ３に示すように空き領域４ａとともに移動する。移動量格納手段１ｄは、使用領域移動手段１ｂより移動された使用領域３ｂ，３ｃと空き領域４ａとの全体の移動量をテーブル５ａに格納する。
【００２５】
使用領域移動手段１ｂは、図のステップＳ３に示すメモリ２に散在している使用領域３ｄを、ステップＳ４に示すように先頭のアドレスから詰めるように移動する。移動量格納手段１ｄは、使用領域移動手段１ｂより移動された使用領域３ｄの移動量をテーブル５ａに格納する。
【００２６】
参照更新手段１ｅは、移動格納手段１ｄによって格納された移動量のテーブル５ａを参照し、メモリ２内の参照関係を更新する。そして、参照更新手段１ｅは、ステップＳ５に示すように全ての参照関係を更新し終えたらテーブル５ａを破棄する。
【００２７】
このように、所定の大きさより小さい空き領域に隣接している使用領域を、その空き領域とともに移動し、移動された使用領域の移動量およびともに移動された使用領域と空き領域との全体の移動量をメモリに格納するようにした。これによって、移動する使用領域の移動回数、移動量のメモリへの格納回数が低減され、実時間性の保持が容易となる。また、組み込み機器の限られた小さなメモリに空き領域が散在していても、ガベージコレクションの効果を高くすることができる。
【００２８】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
図２は、本発明の実施の形態に係る携帯電話のハードウェア構成図である。
図に示す携帯電話１０は、ＣＰＵ（Central Processing Unit）１０ａによって装置全体が制御されている。ＣＰＵ１０ａには、バス１０ｋを介して、ＲＯＭ（Read Only Memory）１０ｂ、ＲＡＭ（Random Access Memory）１０ｃ、フラッシュＲＯＭ１０ｄ、無線通信装置１０ｅ、入力インターフェース１０ｇ、およびグラフィック処理装置１０ｉが接続されている。
【００２９】
ＲＯＭ１０ｂには、ＣＰＵ１０ａに実行させるＯＳ（Operating System）のプログラムおよび処理系プログラムが格納される。処理系プログラムは、例えば、ゲームなどのアプリケーションプログラムをＯＳ上で動作させるためのプログラムであり、アプリケーションプログラムをＯＳやプラットフォームに依存せずに動作できるようにしている。また、アプリケーションプログラムが使用するメモリの領域を確保するため、ガベージコレクションを行う。処理系プログラムは、ＯＳ上で動作する。
【００３０】
ＲＡＭ１０ｃには、ＣＰＵ１０ａのＯＳのプログラム、処理系プログラム、およびアプリケーションプログラムの処理に必要な各種データが保存される。データには、複数のオブジェクトも含まれる。
【００３１】
フラッシュＲＯＭ１０ｄには、例えば、ゲームのアプリケーションプログラムが格納される。フラッシュＲＯＭ１０ｄは書き換え可能な不揮発性メモリであり、アプリケーションプログラムは、ユーザの操作によって書き換えることができる。アプリケーションプログラムは、処理系プログラム上で動作し、処理系プログラムが処理できるプログラミング言語で記述されている必要がある。プログラミング言語には、例えば、Ｊａｖａ（登録商標）、Ｃ、Ｃ＋＋がある。なお、上述したように、アプリケーションプログラムは、処理系プログラムによって、ＯＳやプラットフォームに依存することなく動作することができる。
【００３２】
無線通信装置１０ｅは、ＣＰＵ１０ａからの命令に従って、他の携帯電話と無線通信する装置である。無線通信装置１０ｅには、アンテナ１０ｆが接続され、アンテナ１０ｆを介して他の携帯電話と無線通信を行う。
【００３３】
入力インターフェース１０ｇには、キーボタン１０ｈが接続されている。入力インターフェース１０ｇは、キーボタンから送られてくる信号を、バス１０ｋを介してＣＰＵ１０ａに送信する。
【００３４】
グラフィック処理装置１０ｉには、ＬＣＤ（Liquid Crystal Display）１０ｊが接続されている。グラフィック処理装置１０ｉは、ＣＰＵ１０ａからの命令に従って、画像をＬＣＤ１０ｊに表示させる。
【００３５】
以上のようなハードウェア構成によって、携帯電話１０は、例えば、ゲームのアプリケーションプログラムを実行し、他の携帯電話と無線通信をすることができる。
次に、プログラムの動作概念について説明する。
【００３６】
図３は、プログラムの動作概念を説明する図である。
図には、ＯＳ２１、処理系プログラム２２、アプリケーションプログラム２３、およびメモリ２４が示してある。メモリ２４は、例えば、図２のＲＡＭ１０ｃである。
【００３７】
処理系プログラム２２はＯＳ２１上で動作する。アプリケーションプログラム２３は処理系プログラム２２上で動作する。ＯＳ２１は、直接メモリ２４とデータのやり取りを行い、処理系プログラム２２は、ＯＳ２１を介してメモリ２４とデータのやり取りを行う。アプリケーションプログラム２３は、処理系プログラム２２を介してメモリ２４とデータのやり取りを行う。アプリケーションプログラム２３は、処理系プログラム２２を介することによって、ＯＳ２１やプラットフォームに依存することなく動作することができる。
【００３８】
処理系プログラム２２は図示するように、メモリ２４にアプリケーションプログラム２３が使用できる領域２５を割り当てる。処理系プログラム２２は、領域２５の範囲内で、アプリケーションプログラム２３からの要求によるデータの書き込みおよび読み出しを行う。
【００３９】
次に、メモリの使い方について説明する。
図４は、メモリの使い方について説明する図である。
図には、アプリケーションプログラムが使用できるメモリの領域３１が示してある。また、アプリケーションプログラムにより現在使用されている領域の使用領域３２、アプリケーションプログラムにより現在使用されない領域の空き領域３３が示してある。また、メモリの領域３１に、新たに展開されるデータ３４が示してある。
【００４０】
処理系プログラムは、アプリケーションプログラムからの要求によるデータを、メモリに割り当てた領域３１に展開していく。処理系プログラムは、図の（ａ）に示すように、メモリに割り当てた領域３１のアドレスの先頭からデータを詰めて展開していく。新たに展開するデータ３４は、図の（ｂ）に示すように、使用領域３２に続くアドレスから展開していく。
【００４１】
次に、ガベージコレクションの開始タイミングについて説明する。
図５は、ガベージコレクションの開始タイミングを説明する図である。
図５には、図４の領域３１、使用領域３２、空き領域３３が示してある。また、新たに領域３１に展開されるデータ３５が示してある。
【００４２】
アプリケーションプログラムの実行が進むと、領域３１の使用領域３２が大きくなり、空き領域３３が小さくなってくる。この場合に、アプリケーションプログラムから大きなデータの展開が要求されると、処理系プログラムは、要求のあったデータを空き領域３１に展開することができない場合が生じる。例えば、図に示すように、空き領域３３の容量を３５ＫＢ、データ３５の容量を４０ＫＢとすると、データ３５を空き領域３３に展開することができない。
【００４３】
一方、領域３１の使用領域３２内では、全く使用されないデータが存在しはじめ、空き領域が存在してくる。そこで、データ３５の３５ＫＢ分を空き領域３３に展開し、使用領域３２内にある空き領域に残りの５ＫＢのデータ３５を展開することが考えられる。しかし、この様なデータの分割管理は非常に複雑な処理を要するため、携帯電話などには適さない。
【００４４】
そこで、処理系プログラムは、ガベージコレクションを行い、使用領域３２のデータの中で現在使われなくなったデータの領域（空き領域）を探し出し、回収を行う。
次に、携帯電話１０の処理系プログラムにおける機能について説明する。
【００４５】
図６は、携帯電話の処理系プログラムにおける機能ブロック図である。
携帯電話１０は処理系プログラムの実行によって、図に示すようなマーク処理部１１、コンパクション処理部１２、閾値算出部１３、ブレークテーブル管理部１４、及び参照更新部１５を有している。
【００４６】
マーク処理部１１は、アプリケーションプログラムに割り当てられたメモリ領域のどの部分が現在使用されているかを調べ、メモリに割り当てられた領域のどの部分が使用領域であるか、空き領域であるかを取得する。マーク処理部１１は、アドレスによって、使用領域および空き領域を取得する。また、マーク処理部１１は、使用領域および空き領域の大きさを取得する。使用領域および空き領域の大きさは、例えば、アドレスを差分することにより算出することができる。また、各データの領域の先頭部分にデータの大きさが記述されており、それを手がかりに算出することもできる。
【００４７】
図７は、マーク処理を説明する図である。
図にはアプリケーションプログラムに割り当てられたメモリの領域４１が示してある。メモリは、例えば、図２のＲＡＭ１０ｃである。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。
【００４８】
図に示すようにアプリケーションプログラムの実行が進むと、使用領域と空き領域は散在して存在するようになる。マーク処理部１１は、領域４１のどの部分が使用されているかを調査し、アドレスによって、使用領域および空き領域を取得する。また、使用領域および空き領域の大きさを取得する。
【００４９】
図７の例では、マーク処理部１１は、メモリ番地０〜１０Ｋ，１５Ｋ〜４０Ｋ、６０Ｋ〜９０Ｋ，９５Ｋ〜１２０Ｋ，１５０Ｋ〜１８０Ｋを使用領域と取得する。また、メモリ番地１０Ｋ〜１５Ｋ，４０Ｋ〜６０Ｋ，９０Ｋ〜９５Ｋ，１２０Ｋ〜１５０Ｋ，１８０Ｋ〜２１５Ｋを空き領域と検出する。また、マーク処理部１１は、１０ＫＢ，２５ＫＢ，３０ＫＢ，２５ＫＢ，３０ＫＢの使用領域の大きさを取得し、５ＫＢ，２０ＫＢ，５ＫＢ，３０ＫＢ，３５ＫＢの空き領域の大きさを取得する。
【００５０】
図６の説明に戻る。コンパクション処理部１２は、使用領域をメモリの一箇所に移動して、必要な大きさの空き領域を生成するコンパクション処理を行う。コンパクション処理部１２は、使用領域が所定の閾値より小さい大きさの空き領域に隣接している場合、使用領域をその空き領域とともに移動する。すなわち、大きさが所定の閾値より小さい空き領域は、使用領域とともに、領域のアドレスの先頭から詰まるように移動される。このように、閾値より小さい大きさの空き領域を無視して（空き領域を使用領域とみなして）コンパクションを行うことにより、ガベージコレクションの負荷が軽くなる。また、容量の小さなメモリに空き領域が散在していても、ガベージコレクションの効果を高くすることができる。
【００５１】
ところで、閾値を大きな値にすると、コンパクションの回数が低減し、一回のガベージコレクションの負荷がより軽くなる。しかし、その閾値より小さい大きさの空き領域は、使用領域とともにコンパクションされるため、必要な空き領域を確保することができない場合が生じる。そこで、閾値は、少なくとも、必要な空き領域を確保することができる値まで下げる必要がある。
【００５２】
一方、閾値を小さな値にすると、１回のガベージコレクションでより大きな空き領域を確保でき、ガベージコレクションの頻度を減らすことが出来る。すなわち、全体でのガベージコレクションの負荷がより軽くなる。しかし、閾値を小さくすると、コンパクションの回数が多くなるため、１回のガベージコレクションにかかる時間が大きくなる。そこで、閾値は、少なくとも、許容される時間内（例えば、ゲーム動作が一時止まっても、ユーザに不快を与えない時間内）にガベージコレクションが終了する値まで上げる必要がある。
【００５３】
閾値算出部１３は、２種類の算出方法により２つの閾値を算出する。閾値算出部１３は、算出した２つの閾値を比較して、適当な方を正式な閾値として選択し、コンパクション処理部１２に出力する。第１の算出方法では、まず、マーク処理部１１より算出された最も大きさの大きい空き領域を閾値として採用する。この閾値では、必要な空き領域を確保できない場合、次に大きさの大きい空き領域を閾値として採用する。以下同様に、必要な空き領域を確保できるまで、閾値を下げていき、必要な空き領域を確保できた値を閾値とする。
【００５４】
第２の算出方法では、マーク処理部１１で算出されたそれぞれの空き領域の大きさでのガベージコレクションにかかる時間を算出する。そして、許容される時間内でガベージコレクションを終える最も小さな空き領域の大きさを閾値とする。
【００５５】
閾値算出部１３は、算出した２つの閾値を比較し、適当な方を閾値として選択し出力する。第１の算出方法によって算出した閾値が、第２の算出方法によって算出した閾値より小さい場合、第１の算出方法によって算出した閾値を選択する。第２の算出方法によって算出した閾値を選択すると、アプリケーションプログラムが要求する連続した空き領域を確保できず、アプリケーションプログラムが実行不能となる。つまり、この場合、アプリケーションプログラムが停止するよりは、時々止まりながらでも動作し続ける方が望ましいので、閾値算出部１３は、必要な空き領域が確保されるよう、第１の算出方法によって算出された閾値を選択し出力する。
【００５６】
第１の算出方法によって算出した閾値が、第２の算出方法によって算出した閾値以上の場合、第２の算出方法によって算出した閾値を選択する。第１の算出方法によって算出した閾値を選択すると、ガベージコレクションで許容されている時間内で必要な空き領域を確保することができる。しかし、必要な空き領域が確保できたからといって、ガベージコレクションで許容されている残りの時間を放棄することは無駄である。この場合、許容されている時間までなるべく多くの空き領域を生成してからアプリケーションプログラムの動作を再開することが望ましい。そこで、この場合、閾値算出部１３は、できるだけ多くの空き領域を生成できるよう、第２の算出方法によって算出した閾値を選択し出力する。
【００５７】
以下、第１の算出方法および第２の算出方法について具体的に説明する。
第１の算出方法を説明する。閾値算出部１３は、アプリケーションプログラムより展開要求されたデータを、展開することができる空き領域の大きさを求める。閾値算出部１３は、最も大きさの大きい空き領域の大きさが、展開要求されたデータの大きさを満たしているかを判断する。この条件を満たしていなければ、次に大きさの大きい空き領域の大きさを加算し、その加算した大きさが展開要求されたデータの大きさを満たしているかを判断する。以下、条件を満たしていない場合には同様にして、その次に大きさの大きい空き領域の大きさを加算し、その加算した大きさが展開要求されたデータの大きさを満たしているかを判断する。
【００５８】
条件を満たした場合には、条件を満たした空き領域で、展開要求されたデータの展開を確保することができる。従って、このときの空き領域の大きさが閾値となる。
図７の例で説明すると、閾値算出部１３は、空き領域の大きさを３５ＫＢ，３０ＫＢ，２０ＫＢ，５ＫＢ，５ＫＢと大きい順に並べ替える。展開要求されたデータの大きさを４０ＫＢとすると、最も大きさの大きい空き領域（３５ＫＢ）だけでは、データの展開を確保する大きさを有していない。そこで、最も大きさの大きい空き領域の大きさ（３５ＫＢ）に、次に大きさの大きい空き領域の大きさ（３０ＫＢ）を加算すると、６５ＫＢとなる。そうすると、最も大きさの大きい空き領域と、次に大きさの大きい空き領域とによって、展開要求されたデータを展開することができる。よって、閾値算出部１３は、閾値として３０ＫＢを算出する。
【００５９】
第２の方法を説明する。ガベージコレクションに要する時間には、変動費と固定費がある。固定費とは、ガベージコレクションを開始するために必要な一定の処理に要する時間である。一定の処理には、アプリケーションプログラムを一旦止めてガベージコレクションを開始する処理（例えば、マーク処理）と、ガベージコレクション後にアプリケーションプログラムの動作を再開するための処理（例えば、参照更新処理）がある。変動費は、メモリ領域を移動するのに要する時間である。
【００６０】
固定費の影響を少なくするためには、なるべく多くの空き領域を作成してからアプリケーションプログラムを再開した方がよい。例えば、１００ｍｓｅｃで６５ＫＢの空き領域を作成した場合、６５ＫＢの新たなデータの展開が行われると再びガベージコレクションが必要となる。一方、１５０ｍｓｅｃで１００ＫＢの空き領域を作成した場合、１００ＫＢの新たなデータの展開が行われるまで、ガベージコレクションを延期することができる。
【００６１】
ガベージコレクションの頻度が増えると、固定費における時間が多くなり、アプリケーションの実行速度が低下する。例えば、ゲームの場合、動きは滑らかであるが遅くなってしまう。ある程度滑らかな動きで、実行速度を上げるには、ユーザが耐えられるぎりぎりの時間までコンパクションを行うことが望ましい。
【００６２】
閾値算出部１３は、マーク処理部１１で算出された空き領域のそれぞれの大きさでのガベージコレクションにかかる時間を算出する。以下では、３０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間、２０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間、および空き領域を無視しない場合のガベージコレクションにかかる時間において説明する。
【００６３】
図８は、３０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間を説明する図である。
図にはアプリケーションプログラムに割り当てられた領域５１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。
【００６４】
図の（ａ）に示すように、使用領域と空き領域が散在しているとする。この場合、３０ＫＢより小さい空き領域を無視してガベージコレクションを行うとすると、使用領域５２が移動され、図の（ｂ）に示すようになる。まとまった空き領域は６５ＫＢ確保される。
【００６５】
固定費、１ＫＢあたりの使用領域を移動するのにかかる時間、およびブレークテーブルの管理にかかる時間を以下のようにする。
固定費＝５０ｍｓｅｃ
１ＫＢあたりの使用領域を移動するのにかかる時間＝１ｍｓｅｃ／ＫＢ
ブレークテーブルの管理時間＝エントリ数×エントリ数×５ｍｓｅｃ
エントリ数は移動した使用領域の数を示す。すると、図８の例では、移動する使用領域の大きさが３０ＫＢ、エントリ数が１より、
固定費＝５０ｍｓｅｃ
３０ＫＢの使用領域を移動するのにかかる時間＝３０ｍｓｅｃ
ブレークテーブルの管理時間＝５ｍｓｅｃ
となり、ガベージコレクションにかかる時間は合計８５ｍｓｅｃとなる。
【００６６】
図９は、２０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間を説明する図である。
図には図８と同じ領域５１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。
【００６７】
図の（ａ）に示すように、使用領域と空き領域が散在しているとする。この場合、２０ＫＢより小さい空き領域を無視してガベージコレクションを行うとすると、使用領域５２，５３が移動され、図の（ｂ）に示すようになる。まとまった空き領域は８５ＫＢ確保される。
【００６８】
固定費、１ＫＢあたりの使用領域を移動するのにかかる時間、およびブレークテーブルの管理にかかる時間を図８の条件と同じとする。すると、図９の例では、移動する使用領域の大きさが９０ＫＢ、エントリ数が２より、
固定費＝５０ｍｓｅｃ
９０ＫＢの使用領域を移動するのにかかる時間＝９０ｍｓｅｃ
ブレークテーブルの管理時間＝２０ｍｓｅｃ
となり、ガベージコレクションにかかる時間は合計１６０ｍｓｅｃとなる。
【００６９】
図１０は、空き領域を無視しない場合のガベージコレクションにかかる時間を説明する図である。
図には図８と同じ領域５１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。
【００７０】
図の（ａ）に示すように、使用領域と空き領域が散在しているとする。この場合、空き領域を無視しないでガベージコレクションを行うとすると、使用領域５２，５３ａ，５３ｂ，５４が移動され、図の（ｂ）に示すようになる。まとまった空き領域は９５ＫＢ確保される。
【００７１】
固定費、１ＫＢあたりの使用領域を移動するのにかかる時間、およびブレークテーブルの管理にかかる時間を図８の条件と同じとする。すると、図１０の例では、移動する使用領域の大きさが１１０ＫＢ、エントリ数が４より、
固定費＝５０ｍｓｅｃ
９０ＫＢの使用領域を移動するのにかかる時間＝１１０ｍｓｅｃ
ブレークテーブルの管理時間＝８０ｍｓｅｃ
となり、ガベージコレクションにかかる時間は合計２４０ｍｓｅｃとなる。
【００７２】
ガベージコレクションの制限時間は、予め処理系プログラムに与えられている。制限時間は、例えば、ゲームのアプリケーションプログラムである場合には、ゲームの動作が遅くなってもユーザに不快を与えない時間にする。
【００７３】
図８〜１０の例で、制限時間が１００ｍｓｅｃとすると、閾値算出部１３は、閾値として３０ＫＢを算出する。制限時間が２００ｍｓｅｃとすると、閾値算出部１３は、閾値として２０ＫＢを算出する。なお、閾値算出部１３は、制限時間以上の閾値が算出されたときに、第２の算出方法による処理を終了する。
【００７４】
図６の説明に戻る。ブレークテーブル管理部１４は、ひとかたまりの使用領域（無視された空き領域も含む）が初めて移動されたとき、ブレークテーブル１６を作成する。そして、使用領域が移動される度に、ブレークテーブル１６を更新する。ブレークテーブル１６には、移動された移動領域の移動量が格納される。具体的には、移動された使用領域の大きさと、移動前の使用領域の先頭メモリ番地と、移動後の使用領域の先頭メモリ番地が格納される。ブレークテーブル１６は、空き領域に格納される。
【００７５】
図１１は、ブレークテーブルを説明する図である。
図にはアプリケーションプログラムに割り当てられたメモリの領域６１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。また、図には、ブレークテーブル１６が示してある。
【００７６】
図の（ａ）に示すように使用領域と空き領域が散在しているとする。この状態から、５ＫＢより小さい空き領域を無視してコンパクションを開始するとする。メモリ番地０から領域６１を調べていくと、メモリ番地の４０Ｋから２０ＫＢの空き領域がある。そして、メモリ番地の６０Ｋから６０ＫＢの使用領域がある。よって、メモリ番地６０Ｋからの６０ＫＢの使用領域は、図の（ｂ）に示すようにメモリ番地４０Ｋへと移動される。
【００７７】
ブレークテーブル管理部１４は、初めて使用領域が移動されたので、図の（ｂ）に示すようにブレークテーブル１６を空き領域に作成する（ブレークテーブル１６を作成する位置については後述詳細）。そして、ブレークテーブル１６に移動量を書き込む。
【００７８】
図１１の例では、移動された使用領域の大きさは６０ＫＢで、移動前の使用領域の先頭メモリ番地は６０Ｋ、移動後の使用領域の先頭メモリ番地は４０Ｋである。よって、ブレークテーブル１６には、図１１の（ｂ）に示すように、左端の欄から、使用領域の移動前の先頭メモリ番地を示す６０Ｋ、使用領域の大きさを示す６０ＫＢ、使用領域の移動後の先頭メモリ番地を示す４０Ｋの情報が格納される。
【００７９】
さらに、図の（ａ）領域６１を調べていくと、メモリ番地１２０Ｋから３０ＫＢの空き領域がある。そして、メモリ番地１５０Ｋから３０ＫＢの使用領域がある。よって、メモリ番地１５０Ｋからの３０ＫＢの使用領域は、図の（ｃ）に示すようにメモリ番地１００Ｋへと移動される。
【００８０】
ブレークテーブル管理部１４は、使用領域が移動されたので、図の（ｃ）に示すようにブレークテーブル１６を更新する。
図１１の例では、移動された使用領域の大きさは３０ＫＢで、移動前の使用領域の先頭メモリ番地は１５０Ｋ、移動後の使用領域の先頭メモリ番地は１００Ｋである。よって、ブレークテーブル１６には、図１１の（ｃ）に示すように、左下端の欄から、使用領域の移動前の先頭メモリ番地を示す１５０Ｋ、使用領域の大きさを示す３０ＫＢ、使用領域の移動後の先頭メモリ番地を示す１００Ｋの情報が格納される。なお、ブレークテーブル１６の更新される情報は、メモリ上では、アドレスの先頭方向に向かって追加されていく。
【００８１】
使用領域の移動が繰り返されると、ブレークテーブル１６が大きくなり、１つの空き領域に格納できなくなる場合がある。この場合、ブレークテーブル１６を他の空き領域に移動する必要がある。そこで、ブレークテーブル管理部１４は、ブレークテーブル１６の移動回数をできるだけ抑えることのできる空き領域にブレークテーブル１６を配置する。
【００８２】
ブレークテーブル管理部１４は、最大の大きさを有する空き領域を検出し、ブレークテーブル１６を配置、更新する。ブレークテーブル１６が大きくなり、その空き領域にブレークテーブル１６を更新することができなくなると、新たに最大の大きさを有する空き領域を検出し、移動する。このとき、ブレークテーブル管理部１４は、空き領域の最後方のアドレスからブレークテーブルを詰めていく。
【００８３】
図１２は、ブレークテーブルの配置を説明する図である。
図にはアプリケーションプログラムに割り当てられた領域７１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。また、図には、ブレークテーブル１６が示してある。図の（ａ）に示すように、使用領域と空き領域とが散在しているとする。
【００８４】
図の（ａ）に示すように、領域７１の最後方にある空き領域が最大の大きさを有し、その空き領域にブレークテーブル１６が配置されているとする。
コンパクション処理部１２が図の（ａ），（ｂ）に示すように使用領域７２を移動したとする。ブレークテーブル管理部１４は、最後方の空き領域に配置されているブレークテーブル１６を更新する。
【００８５】
次に、コンパクション処理部１２が図の（ｂ），（ｃ）に示すように使用領域７３を移動したとする。ブレークテーブル１６が大きくなり、最後方の空き領域でブレークテーブル１６を更新することができなくなると、ブレークテーブル管理部１４は、最大の大きさを有する空き領域を検出し、図の（ｃ）に示すようにブレークテーブル１６を移動する。
【００８６】
次に、コンパクション処理部１２が、図の（ｃ），（ｄ）に示すように使用領域７４を移動したとする。ブレークテーブル管理部１４は、ブレークテーブル１６が配置されている空き領域で、ブレークテーブル１６を移動しなくても更新できる場合は、図の（ｄ）に示すようにその空き領域において、ブレークテーブル１６を更新する。
【００８７】
従来では、先頭空き領域の最後方のアドレスにブレークテーブルを配置していた。そのため、先頭空き領域が小さい場合にはブレークテーブルの移動回数が多くなり、処理系プログラムに大きな負担をかけていた。使用領域を移動する度に、その使用領域の後方に存在する空き領域の最後方のアドレスからブレークテーブルを配置していたブレークテーブルの移動回数が多く、さらに、その大きさが大きくなると本発明では、図１２で説明したように、最大の大きさを有する空き領域を検出し、その空き領域の、使用領域が移動される方向とは逆の最後方にブレークテーブルを格納する。そして、ブレークテーブルが空き領域に収まらなくなると、再び最大の大きさを有する空き領域を検出し、その空き領域にブレークテーブルを格納する。よって、移動回数が低減され、処理系プログラムの負担を低減することができる。
【００８８】
図６の説明に戻る。メモリの領域中には、必要なデータにアクセスするためのデータ（参照アドレス）が格納される。しかし、コンパクションによってデータを移動してしまうと、参照関係が破壊されてしまう。参照更新部１５は、コンパクションが終了するとブレークテーブル１６を参照して、破壊関係を修復し、正しくデータを参照できるようにする。
【００８９】
参照更新部１５は、メモリの領域中を参照して参照アドレスを検出し、その参照アドレスを、ブレークテーブル１６を参照して、正しい参照アドレスに変更する。
図１３は、参照アドレスの変更を説明する図である。
【００９０】
図にはアプリケーションプログラムに割り当てられたメモリの領域７１が示してある。図の塗り潰している部分は使用領域、空白部分は空き領域を示す。また、図には，ブレークテーブル１６が示してある。図の（ａ）に示すように、使用領域と空き領域とが散在しているとする。
【００９１】
図の（ａ）に示すようにメモリ番地１０Ｋには、メモリ番地１１０Ｋを参照する旨の参照アドレスが格納されているとする。従って、例えば、図２のＣＰＵ１０ａがメモリ番地１０Ｋをアクセスすると、ＣＰＵ１０ａは、メモリ番地１１０Ｋのデータを参照することになる。
【００９２】
図の（ａ）の状態から図の（ｂ）に示すように、メモリ番地６０Ｋから始まる大きさ６０ＫＢの使用領域７２がメモリ番地４０Ｋに移動され、メモリ番地１５０Ｋから始まる大きさ３０ＫＢの使用領域７３がメモリ番地１００Ｋに移動されたとする。このコンパクションによって、メモリ番地１１０Ｋのデータには、本来と異なるデータが格納されていることになる。なお、最後方の空き領域には、図の（ｂ）に示すようなブレークテーブル１６が作成される。
【００９３】
参照更新部１５は、領域７１を走査し、メモリ番地１０Ｋに参照アドレスが格納されていることを検出する。そして、参照更新部１５は、ブレークテーブル１６を参照して、参照アドレスの移動先を割り出し、メモリ番地１０Ｋの参照アドレスを適正な参照アドレスに変更する。
【００９４】
ブレークテーブル１６よりメモリ番地６０Ｋから６０ＫＢの大きさを有する使用領域７２は、メモリ番地４０Ｋに移動されたことがわかる。よって、参照更新部１５は、６０Ｋ−４０Ｋ＝２０Ｋより、使用領域７２が２０Ｋアドレス分、移動したことを算出する。そして、メモリ番地１１０Ｋのデータは、１１０Ｋ−２０Ｋ＝９０Ｋより、メモリ番地９０Ｋに移動したことを算出する。参照更新部１５は、メモリ番地１０Ｋの参照アドレスを、図の（ｃ）に示すように、メモリ番地１１０Ｋからメモリ番地９０Ｋに変更する。
【００９５】
これによって、図２のＣＰＵ１０ａがメモリ番地１０Ｋをアクセスすると、ＣＰＵ１０ａは、メモリ番地９０Ｋの適正なデータを参照することができる。
以下、図６の携帯電話１０のガベージコレクションにおける動作について、フローチャートを用いて説明する。
【００９６】
図１４は、携帯電話のガベージコレクションの処理の流れを示したフローチャートである。
携帯電話のガベージコレクションは、以下のステップに従って処理が進められる。
【００９７】
ステップＳ１１において、マーク処理部１１は、アプリケーションプログラムに割り当てられたメモリの領域のどの部分が現在使用されているかを調べ、メモリに割り当てられた領域のどの部分が使用領域であるか、空き領域であるかを取得する。
【００９８】
ステップＳ１２において、閾値算出部１３は、コンパクション処理部１２が無視してコンパクションを行う空き領域の閾値を算出する。閾値算出部１３は、２種類の算出方法により２つの閾値を算出する。そして、２つの閾値を比較し、適当な方を正式な閾値としてコンパクション処理部１２に出力する。
【００９９】
ステップＳ１３において、コンパクション処理部１２は、閾値算出部１３より算出された閾値より小さい大きさの空き領域を無視して、移動すべき領域（使用領域と、使用領域とともに移動する空き領域）を決定する。
【０１００】
ステップＳ１４において、ブレークテーブル管理部１４は、空き領域にブレークテーブル１６を更新できるか判断する。すなわち、ブレークテーブル管理部１４は、空き領域がブレークテーブル１６を更新できる大きさを有しているか判断する。更新できる場合は、ステップＳ１５へ進む。更新できない場合は、ステップＳ１６へ進む。なお、空き領域にまだブレークテーブル１６を作成していない場合、すなわち、コンパクションがこれから行われる場合は、ステップＳ１６へ進む。
【０１０１】
ステップＳ１５において、コンパクション処理部１２は、使用領域を領域の先頭アドレスから詰めるように移動する。また、コンパクション処理部１２は、閾値より小さい大きさの空き領域を使用領域とともに移動する。
【０１０２】
ステップＳ１６において、ブレークテーブル管理部１４は、最大の大きさを有する空き領域の最後方にブレークテーブル１６を移動する。なお、ブレークテーブル１６を初めて作成する場合は、最大の大きさを有する空き領域の最後方にブレークテーブル１６を作成する。
【０１０３】
ステップＳ１７において、ブレークテーブル管理部１４は、ブレークテーブル１６に使用領域、空き領域の移動量を格納する。
ステップＳ１８において、コンパクション処理部１２は、領域の全範囲において、無視すべき空き領域を含む使用領域を全て移動し終えたか判断する。全て移動し終えている場合は、ステップＳ１９へ進む。全て移動し終えていない場合は、ステップＳ１３へ進む。
【０１０４】
ステップＳ１９において、参照更新部１５は、メモリの領域中を参照して参照アドレスを検出し、検出した参照アドレスを、ブレークテーブル１６を参照して、正しい参照アドレスに変更する。
【０１０５】
このように、空き領域の大きさに応じて、その空き領域に隣接する使用領域を、その空き領域とともに移動し、移動された使用領域の移動量およびともに移動された使用領域と空き領域との全体の移動量をメモリに格納するようにした。これによって、移動する使用領域の移動回数、メモリへの移動量の格納回数が低減され、実時間性の保持が容易となる。
【０１０６】
また、携帯電話１０の限られた小さなメモリに空き領域が散在していても、ガベージコレクションの効果を高くすることができる。
また、上記では、携帯電話を例に説明したが、例えば、自動車に搭載されるカーナビゲーションなどの組み込み機器にも適用することができる。
【０１０７】
なお、コンピュータが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。
【０１０８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１０９】
（付記１）  ガベージコレクションを行うメモリ管理プログラムにおいて、
コンピュータを、
メモリに散在している空き領域の大きさを取得する空き領域取得手段、
前記メモリに散在している使用領域を所定のアドレスから詰めるように移動する使用領域移動手段、
前記使用領域が所定の大きさより小さい前記空き領域に隣接している場合、前記使用領域を前記空き領域とともに移動する両領域移動手段、
前記使用領域移動手段より移動された前記使用領域の移動量および前記両領域移動手段より移動された前記空き領域と前記使用領域との全体の移動量を前記メモリに格納する移動量格納手段、
として機能させることを特徴とするメモリ管理プログラム。
【０１１０】
（付記２）  前記両領域移動手段は、
前記メモリに展開されるデータの領域が前記使用領域の移動によって前記メモリに確保できるように予め前記所定の大きさを算出する第１の算出手段と、
許容される時間内で前記使用領域の移動を終えることができるための前記所定の大きさを予め算出する第２の算出手段と、
前記第１の算出手段により算出された前記所定の大きさと前記第２の算出手段により算出された前記所定の大きさとを比較して一方を選択する選択手段と、
を有することを特徴とする付記１記載のメモリ管理プログラム。
【０１１１】
（付記３）  前記移動量格納手段は、最大の大きさを有する前記空き領域に前記移動量を格納することを特徴とする付記１記載のメモリ管理プログラム。
（付記４）  前記移動量格納手段は、前記空き領域に前記移動量が格納できなくなった場合、新たに最大の大きさを有する前記空き領域を検索し、前記移動量を格納することを特徴とする付記３記載のメモリ管理プログラム。
【０１１２】
（付記５）  前記移動量格納手段は、前記空き領域の後方アドレスから前記移動量を格納することを特徴とする付記３記載のメモリ管理プログラム。
（付記６）  前記移動量を参照して、データの格納場所を示す参照アドレスを適正な値に変換する参照アドレス変換手段をさらに有することを特徴とする付記１記載のメモリ管理プログラム。
【０１１３】
（付記７）  前記所定のアドレスは、前記メモリにデータが展開される領域の先頭アドレスであることを特徴とする付記１記載のメモリ管理プログラム。
（付記８）  ガベージコレクションが行われる組み込み機器において、
メモリに散在している空き領域の大きさを取得する空き領域取得手段と、
前記メモリに散在している使用領域を所定のアドレスから詰めるように移動する使用領域移動手段と、
前記使用領域が所定の大きさより小さい前記空き領域に隣接している場合、前記使用領域を前記空き領域とともに移動する両領域移動手段と、
前記使用領域移動手段より移動された前記使用領域の移動量および前記両領域移動手段より移動された前記空き領域と前記使用領域との全体の移動量を前記メモリに格納する移動量格納手段と、
を有することを特徴とする組み込み機器。
【図面の簡単な説明】
【０１１４】
【図１】本発明の原理を説明する原理図である。
【図２】本発明の実施の形態に係る携帯電話のハードウェア構成図である。
【図３】プログラムの動作概念を説明する図である。
【図４】メモリの使い方について説明する図である。
【図５】ガベージコレクションの開始タイミングを説明する図である。
【図６】携帯電話の処理系プログラムにおける機能ブロック図である。
【図７】マーク処理を説明する図である。
【図８】３０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間を説明する図である。
【図９】２０ＫＢより小さい空き領域を無視した場合のガベージコレクションにかかる時間を説明する図である。
【図１０】空き領域を無視しない場合のガベージコレクションにかかる時間を説明する図である。
【図１１】ブレークテーブルを説明する図である。
【図１２】ブレークテーブルの配置を説明する図である。
【図１３】参照アドレスの変更を説明する図である。
【図１４】携帯電話のガベージコレクションの処理の流れを示したフローチャートである。
【図１５】ブレークテーブル式コンパクションガベージコレクションを説明するための説明図である。
【図１６】インクリメンタルコンパクション型ガベージコレクションを説明するための説明図である。
【符号の説明】
【０１１５】
１  コンピュータ
１ａ  空き領域取得手段
１ｂ  使用領域移動手段
１ｃ  両領域移動手段
１ｄ  移動量格納手段
１ｅ  参照更新手段
２  メモリ
１０  携帯電話
１１  マーク処理部
１２  コンパクション処理部
１３  閾値算出部
１４  ブレークテーブル管理部
１５  参照更新部
１６  ブレークテーブル
【図１】
2005242617.tif 000003
【図２】
2005242617.tif 000004
【図３】
2005242617.tif 000005
【図４】
2005242617.tif 000006
【図５】
2005242617.tif 000007
【図６】
2005242617.tif 000008
【図７】
2005242617.tif 000009
【図８】
2005242617.tif 000010
【図９】
2005242617.tif 000011
【図１０】
2005242617.tif 000012
【図１１】
2005242617.tif 000013
【図１２】
2005242617.tif 000014
【図１３】
2005242617.tif 000015
【図１４】
2005242617.tif 000016
【図１５】
2005242617.tif 000017
【図１６】
2005242617.tif 000018