(57)【要約】【課題】ガベージコレクションを必要としない階層的ヒープ管理方法及び装置を提供する。【解決手段】処理１０１，１０２において、生成したオブジェクトを特定する変数を要素とする集合を作成する。処理１０３において、第１のヒープを確保する。処理１０４，１０５において、第２のヒープを確保し、第２のヒープを第１のヒープの下位層として記憶する。処理１０６において、第２のヒープ内にオブジェクトを生成し、オブジェクトを特定する変数を集合に追加する。処理１１０において、第１のヒープをクリアする際に、下位層である第２のヒープをクリアし、第２のヒープをクリアする際に、集合から第２のヒープ内のオブジェクトを特定する変数を除去する。【選択図】  図１
2007179154.tif 000002
【特許請求の範囲】
【請求項１】
階層的に管理された複数のヒープをプログラムの実行時に確保し、ヒープ内にメモリを確保して使用し、ヒープをクリアするヒープ管理方法であって、
生成したオブジェクトを特定する変数を要素とする集合を作成する処理と、
第１のヒープを確保する処理と、
第２のヒープを確保し、該第２のヒープを前記第１のヒープの下位層として記憶する処理と、
前記第２のヒープ内にオブジェクトを生成し、該オブジェクトを特定する前記変数を前記集合に追加する処理と、
前記第１のヒープをクリアする際に、下位層である前記第２のヒープをクリアする処理と、
前記第２のヒープをクリアする際に、前記集合から前記第２のヒープ内のオブジェクトを特定する前記変数を除去する処理とを具えることを特徴とする階層的ヒープ管理方法。
【請求項２】
前記第２のヒープにおいてメモリ不足が生じた際に、上位層である前記第１のヒープにおいて拡張用メモリを確保して第２のヒープを拡張する処理と、
前記第２のヒープをクリアする際に、前記集合から前記拡張用メモリ内のオブジェクトを特定する前記変数を除去した後、前記第１のヒープにおいて前記メモリを解放する処理とを更に具えることを特徴とする請求項１記載の階層的ヒープ管理方法。
【請求項３】
前記集合をツリーで表現し、
前記第１のヒープ内にオブジェクトを特定する変数を要素とする第２の集合を作成する処理と、
前記第２のヒープ内にオブジェクトを特定する変数を要素とする第３の集合を作成する処理と、
前記第３の集合を前記第２の集合の下位層として記憶する前記ツリーを作成する処理とを更に具え、前記第２のヒープをクリアする際に、前記ツリーから前記第３の集合を除去することを特徴とする請求項１記載の階層的ヒープ管理方法。
【請求項４】
メモリ及び制御部を具え、階層的に管理された複数のヒープをプログラムの実行時に確保し、ヒープ内にメモリを確保して使用し、ヒープをクリアするヒープ管理装置であって、前記制御部が前記メモリに対して、
生成したオブジェクトを特定する変数を要素とする集合を作成する処理と、
第１のヒープを確保する処理と、
第２のヒープを確保し、該第２のヒープを前記第１のヒープの下位層として記憶する処理と、
前記第２のヒープ内にオブジェクトを生成し、該オブジェクトを特定する前記変数を前記集合に追加する処理と、
前記第１のヒープをクリアする際に、下位層である前記第２のヒープをクリアする処理と、
前記第２のヒープをクリアする際に、前記集合から前記第２のヒープ内のオブジェクトを特定する前記変数を除去する処理とを行うことを特徴とする階層的ヒープ管理装置。
【請求項５】
前記制御部が前記メモリに対して、
前記第２のヒープにおいてメモリ不足が生じた際に、上位層である前記第１のヒープにおいて拡張用メモリを確保して第２のヒープを拡張する処理と、
前記第２のヒープをクリアする際に、前記集合から前記拡張用メモリ内のオブジェクトを特定する前記変数を除去した後、前記第１のヒープにおいて前記メモリを解放する処理とを更に行うことを特徴とする請求項４記載の階層的ヒープ管理装置。
【請求項６】
前記集合をツリーで表現し、前記制御部が前記メモリに対して、
前記第１のヒープ内にオブジェクトを特定する変数を要素とする第２の集合を作成する処理と、
前記第２のヒープ内にオブジェクトを特定する変数を要素とする第３の集合を作成する処理と、
前記第３の集合を前記第２の集合の下位層として記憶する前記ツリーを作成する処理とを更に行い、前記第２のヒープをクリアする際に、前記ツリーから前記第３の集合を除去することを特徴とする請求項４記載の階層的ヒープ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層的に管理された複数のヒープをプログラムの実行時に確保し、ヒープ内にメモリを確保して使用し、ヒープをクリアする階層的ヒープ管理方法及び装置に関する。
【背景技術】
【０００２】
現在、衛星デジタル放送や地上デジタル放送のデータ放送において、ＸＨＴＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｈｙｐｅｒ  Ｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）を拡張したＢＭＬ（Ｂｒｏａｄｃａｓｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）というマークアップ言語で記述した文書が送信され、受信機はこれを受信し、表示し、イベント処理を行っている。ＢＭＬ文書には、表示するテキストやスタイルの他に、イベントとスクリプトを定義し、イベント発生時に実行すべき関数をスクリプトで記述できるようになっている。スクリプトは、ＥＣＭＡＳｃｒｉｐｔと呼ばれる言語が採用されている。ＥＣＭＡＳｃｒｉｐｔはＥＣＭＡ（Ｅｕｒｏｐｅａｎ  Ｃｏｍｐｕｔｅｒ  Ｍａｎｕｆａｃｔｕｒｅｒｓ’  Ａｓｓｏｃｉａｔｉｏｎ）がＥＣＭＡ−２６２として定めたスクリプト言語で、ＩＳＯ／ＩＥＣ  １６２６２として承認されたものが、ＥＣＭＡ−２６２  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎとして発行されている。さらにＥＣＭＡ−２６２はｔｈｉｒｄ  ｅｄｉｔｉｏｎが発行されている。ＥＣＭＡＳｃｒｉｐｔは、プロトタイプベースの継承を行うオブジェクト指向言語であり、オブジェクトの新規生成は行うが、オブジェクトの廃棄については特に配慮されておらず、使われていないオブジェクトがガベージコレクションによって自動的に回収されることを前提としている。
【０００３】
また、地上デジタル放送を携帯機器で受信するための規格が従来定められている。携帯機器では、重量やサイズの観点からバッテリーの容量に制限があり、搭載するメモリやシステムクロックもできるだけ低く抑える必要がある。しかしながら、地上デジタル放送を受信する携帯機器では、ＢＭＬで記述された文書を表示し、含まれているＥＣＭＡＳｃｒｉｐｔを実行することが求められている。ＥＣＭＡＳｃｒｉｐｔを実行するためには、ガベージコレクションの搭載が必要となっている。
【０００４】
ガベージコレクションは、本来の実行処理を停止した上で、メモリ上の変数領域とスタックとＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）のレジスタの中でヒープ内のオブジェクトのアドレスとして解釈可能かどうかを判定し、解釈可能な場合はそのオブジェクトを残し、解釈できるものがなかったオブジェクトは解放する、という処理である。ネットワークを利用するアプリケーションを記述する際には、多くの例外処理や異常処理を記述しなければならず、メモリの解放処理の記述を忘れてメモリーリークが多発するため、ガベージコレクションを搭載することが安全とされている。
【０００５】
従来、フラグメンテーションの発生を少なくし、ガベージコレクション（メモリコンパクション）の発生を少なくするメモリ管理方法およびデータ処理装置が提案されている（例えば、特許文献１）。メモリコンパクションとは、断片化して虫食い状態になったメモリにおいて、使用されている領域と使用されていない領域とを分離して再配置することにより、より大きな連続した未使用領域を作ることである。ガベージコレクションの様々な方式の中でも、コピーアルゴリズム方式のガベージコレクションではメモリコンパクションが達成される。
【特許文献１】特開２００２−３５１７３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ガベージコレクションは、本来の処理を停止する必要があるため、一時的なパフォーマンスの低下が問題となる。また、メモリ上の変数領域とスタックとＣＰＵのレジスタを調査する特殊なプログラムであり、開発や移植が難しい。携帯機器のような小規模なコンピュータシステムにおいては、ガベージコレクションを搭載しないで済むならばその方が好ましいが、その場合、不要なメモリが解放されずにメモリ不足が起きたり、メモリのフラグメンテーション（断片化）によってメモリの総量は足りているにもかかわらずサイズの大きなメモリが確保できなくなる、といった問題が生じる。
【０００７】
本発明の目的は、ガベージコレクションを搭載する必要がない階層的ヒープ管理方法及び装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明による階層的ヒープ管理方法は、
階層的に管理された複数のヒープをプログラムの実行時に確保し、ヒープ内にメモリを確保して使用し、ヒープをクリアするヒープ管理方法であって、
生成したオブジェクトを特定する変数を要素とする集合を作成する処理と、
第１のヒープを確保する処理と、
第２のヒープを確保し、該第２のヒープを前記第１のヒープの下位層として記憶する処理と、
前記第２のヒープ内にオブジェクトを生成し、該オブジェクトを特定する前記変数を前記集合に追加する処理と、
前記第１のヒープをクリアする際に、下位層である前記第２のヒープをクリアする処理と、
前記第２のヒープをクリアする際に、前記集合から前記第２のヒープ内のオブジェクトを特定する前記変数を除去する処理とを具えることを特徴とする。
【０００９】
本発明による階層的ヒープ管理装置は、
メモリ及び制御部を具え、階層的に管理された複数のヒープをプログラムの実行時に確保し、ヒープ内にメモリを確保して使用し、ヒープをクリアするヒープ管理装置であって、前記制御部が前記メモリに対して、
生成したオブジェクトを特定する変数を要素とする集合を作成する処理と、
第１のヒープを確保する処理と、
第２のヒープを確保し、該第２のヒープを前記第１のヒープの下位層として記憶する処理と、
前記第２のヒープ内にオブジェクトを生成し、該オブジェクトを特定する前記変数を前記集合に追加する処理と、
前記第１のヒープをクリアする際に、下位層である前記第２のヒープをクリアする処理と、
前記第２のヒープをクリアする際に、前記集合から前記第２のヒープ内のオブジェクトを特定する前記変数を除去する処理とを行うことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、第１のヒープをクリアする際に、下位層である第２のヒープをクリアし、第２のヒープをクリアする際に、集合から第２のヒープ内のオブジェクトを特定する変数を除去し、ヒープ内に動的に確保したメモリを個別に解放しなくてもヒープを一括してクリアするので、メモリーリークが生じなくなり、その結果、ガベージコレクションを不要とすることができる。
【発明を実施するための最良の形態】
【００１１】
本発明の実施の形態を、図面を参照して詳細に説明する。
図１は、本発明によるヒープメモリ管理方法の第１の実施の形態を示すフローチャートであり、図２は、図１の処理１１０の詳細を示すフローチャートである。本実施の形態は、後に説明するＥＣＭＡＳｃｒｉｐｔインタープリタによって実行される。
【００１２】
図１において処理を開始すると、処理１０１において文字列リストを作成する。文字列リストは、インタープリタが使用した文字列の一覧を保持している線形リストであり、これはＥＣＭＡＳｃｒｉｐｔのランタイム（実行環境）の一部である。文字列リストは、本発明におけるオブジェクトを特定する変数を要素とする集合の例である。本発明のオブジェクトを特定する変数としては、ポインタやハンドルがあり、さらにインデクスでもよい。本発明のオブジェクトを特定する変数を要素とする集合としては、線形リストの他、ツリーや配列でもよい。
【００１３】
線形リストとは、セルと呼ばれる自己参照ポインタを持つ構造体が１次元的に連なってできるリストである。セルには、次のセルを指すポインタと、データを指すポインタとを持ち、このデータポインタが文字列を指しておけば、文字列リストが構成できる。文字列リストによって、インタープリタが認識している変数名などが唯一であることを保証し、同じ文字列を重複して持つことを避けることができる。すなわち、ＥＣＭＡＳｃｒｉｐｔは、文字列を受け取ると、文字列リストの中に存在するかどうかを探索し、既に存在すればリスト中の文字列を替わりに使用し、辞書中に存在しなければ、この文字列の複製を作成してリストに格納する。ランタイムが作成される際には、システムが定義する名前が文字列リストに予め登録され、その後ユーザー定義のスクリプトが実行されると、ユーザーが使用した名前も文字列リストに追加登録される。文字列リストは、ＬＩＳＰ言語におけるＡｔｏｍ  ＬｉｓｔやＯｂｌｉｓｔと似たものである。文字列リストは、一つの線形リストとは限らず、ハッシュによって検索を高速に行えるようにし、文字列から計算されるハッシュ値によって、例えば５１２個のスロットに分割し、各スロットに線形リストを備えてもよい。次に、処理１０２へ進む。
【００１４】
処理１０２は、Ｇｌｏｂａｌオブジェクトを作成する処理である。Ｇｌｏｂａｌオブジェクトは、グローバル変数の受け皿であり、特定のオブジェクトのメンバーではないグローバル変数が、Ｇｌｏｂａｌオブジェクトのメンバーとして登録される。登録は、プロパティとして行われ、変数名とその中味であるオブジェクトの対が、Ｇｌｏｂａｌオブジェクトのプロパティリストに追加される。Ｇｌｏｂａｌオブジェクトもランタイムの一部であり、ランタイムが作成される際には、システムが定義するグローバル変数が予め登録され、その後ユーザー定義のスクリプトが実行されると、ユーザーが使用したグローバル変数が登録される。Ｇｌｏｂａｌオブジェクトのプロパティも線形リストであり、これも、本発明におけるオブジェクトを特定する変数を要素とする集合の例である。次に、処理１０３へ進む。
【００１５】
処理１０３は、第１のヒープを確保する処理である。アプリケーションが実行される際には、１個のプロセスヒープを割当てられており、このヒープ上にメモリを確保するには標準関数のmalloc()を用いるが、処理１０３の第１のヒープは、プロセスヒープとは別のヒープであって、アプリケーションの実行中に動的に確保され、動的に解放される。ＥＣＭＡＳｃｒｉｐｔインタープリタにおいては、ある一連の事前に定義されたスクリプトを実行する。このスクリプトは、ＢＭＬ文書に記述されており、イベント処理の開始前に実行されるものである。このために、あるＢＭＬ文書を受信し、その表示を開始する際に第１のヒープを確保し、そのＢＭＬ文書が廃棄されると、第１のヒープをクリアする。ＢＭＬ文書ごとに使用したヒープをクリアすることによって、不要なメモリの回収すなわちガベージコレクションを行う必要がなくなる。ＢＭＬ文書間で共有するオブジェクトやデータは限定されており、ＧｒｅｇとＵｒｅｇと呼ばれる配列に格納されることになっているため、これらは、第１のヒープとは別の持続性のあるメモリに格納している。また、ＢＭＬブラウザが利用するＤＯＭ（Ｄｏｃｕｍｅｎｔ  Ｏｂｊｅｃｔ  Ｍｏｄｅｌ） ＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍ Ｉｎｔｅｒｆａｃｅ）などのホストオブジェクトでは、プロパティの追加が禁止されているため、第１のヒープが解放されても問題は生じない。また、Ｇｌｏｂａｌオブジェクトに追加されたグローバル変数は、第１のヒープの解放時に無効になったものを除去する必要があるが、これは後に説明する。次に、処理１０４へ進む。
【００１６】
処理１０４は、第２のヒープを確保する処理である。第２のヒープも動的に確保される。ＥＣＭＡＳｃｒｉｐｔインタープリタにおいては、ある実行単位に対して第２のヒープを確保する。すなわち、ＢＭＬの表示中に何らかのイベントが発生し、そのイベントに対応した予め定義され、既に解釈されてあるスクリプトが実行される場合である。また、あるオブジェクトに対して第２のヒープを確保してもよい。例えば、あるオブジェクトに関する処理を実行する際には、そのオブジェクトに付属しているヒープを用いるといった使い方をすることもできる。次に、処理１０５へ進む。
【００１７】
処理１０５は、第１のヒープの下位層を格納する線形リストに第２のヒープを追加し、第２のヒープの上位層を第１のヒープに設定する処理である。第１のヒープは、第２のヒープ以外にも下位層のヒープを持つことができる。イベントによって起動されるスクリプトは、正常に終了することもあり、何らかの障害によって例外が発生し、実行を途中で放棄することもある。例外が発生した場合、第２のヒープを解放すればメモリーリークを抑止することができる。実行が正常に終了した場合、演算結果のうち、第２のヒープ以外の変数に格納する演算結果を、第２のヒープの上位層である第１のヒープ内に複製し、保存すれば、第２のヒープをクリアすることができる。これによって、フラグメンテーションを局所的に閉じ込め、ガベージコレクションがなくても問題を回避することができる。次に、処理１０６へ進む。
【００１８】
処理１０６は、第２のヒープにオブジェクトＯを生成する処理である。これは、あるスクリプトの実行結果がオブジェクトＯになったという場合である。スクリプトの実行には、この他に多くのオブジェクトを第２のヒープに生成する必要がある。次に、処理１０７へ進む。
【００１９】
処理１０７は、第２のヒープに名前Ｎを作成する処理である。これは、あるスクリプトがあるグローバル変数に演算結果を代入する場合に、そのグローバル変数の名前を名前Ｎとして作成することである。次に、処理１０８へ進む。
【００２０】
処理１０８は、文字列リストに名前Ｎを追加する処理である。この際、線形リストを構成するセルを第２のヒープに確保し、その値として名前Ｎを参照し、このセルを文字列リストに挿入する。次に、処理１０９へ進む。
【００２１】
処理１０９は、Ｇｌｏｂａｌオブジェクトのプロパティに名前Ｎという名前でオブジェクトＯを追加する処理である。これによって、グローバル変数として名前Ｎが記憶され、その値がオブジェクトＯと記憶される。次に、処理１１０へ進む。
【００２２】
処理１１０は、第１のヒープをクリアする処理である。「ヒープをクリアする」とは、単純に言えば、ヒープ内に確保されているメモリを全て解放した状態にすることである。ただし、本発明ではヒープは階層的に管理されているので、下位層のヒープを先にクリアする必要があり、また、解放されるメモリを指しているセルをリストから除去する処理を行い、その詳細は図２に示してある。
【００２３】
動的に確保されるヒープがプロセスヒープとは別の独自の管理方法を実装しているので、一気に全てのメモリを解放することが可能であるが、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）が動的に確保されるヒープをサポートし、これを利用するときには、ヒープをクリアするＡＰＩが存在しない場合、ヒープ自体を解放することによってヒープのクリアを実現してもよい。独自の管理方法を実装する場合、簡単な方法としては、ヒープを、メモリブロックの線形リストとして扱うことができる。各メモリブロックの先頭には、そのメモリブロックが使用中であるか使用可能であるかを示すフラグと、次のメモリブロックへのポインタを含んだヘッダとを設置する。最初にメモリを確保した際には線形リストは空なので、未使用領域に新しくメモリブロックを設置し、線形リストに追加する。次々にメモリを確保する度にこれを繰り返してゆくが、線形リストを順次検索し、フラグが使用可能に設定されているメモリブロックを発見でき、かつ、そのサイズが要求に応えられる場合には、そのメモリブロックのフラグを使用中に設定してこれを確保する。あるメモリを解放する際には、そのメモリブロックのフラグを使用可能に変更し、メモリブロック自体を消去して未使用領域に統合し、又は、隣接する利用可能なメモリブロックと統合する。処理１１０が終了すると、図１のフローが終了する。
【００２４】
次に、図２を用いてヒープをクリアする処理１１０を説明する。処理１１０は、第１のヒープをクリアする処理であるが、本発明において階層的に管理されているヒープ一般をクリアする処理でもある。すなわち、第１のヒープ以外のヒープを対象にした場合でも、それをクリアする際には処理１１０を適用する。先ず、処理１２１へ進む。
【００２５】
処理１２１は、クリアしようとする対象ヒープが下位層として記憶している下位層ヒープを一つ取得する処理である。下位層のヒープは線形リストとして記憶されているので、その線形リストの先頭位置のヒープを取り出す。次に、判定処理１２２へ進む。
【００２６】
判定処理１２２は、取り出した下位層ヒープが存在しているか否かを判定する処理である。すなわち、取り出した下位層ヒープを指すポインタがＮＵＬＬであるかどうかを判定する。ＮＵＬＬである場合、下位層を記憶している線形リストが終端したことを意味するので、下位層ヒープはもはや存在せず、処理１２５へ進む。ＮＵＬＬ以外である場合、下位層ヒープは存在しているので、処理１２３へ進む。ここでは、ヒープを指すためにポインタを使った例を述べたが、これがハンドルであってもよい。ハンドルとは、リソースやオブジェクトを指すための変数である。その実装はＯＳに依存しているが、ある例において簡単に説明すると、ハンドルとは、ヒープなどのオブジェクトを指すポインタ変数を指すポインタ変数である。このようにハンドルを定義すると、アプリケーションにはオブジェクトのアドレスが通知されないので、ＯＳがオブジェクトの位置を勝手に変更でき、アプリケーションの関知しない間にメモリコンパクションをＯＳが実行できるというメリットがある。
【００２７】
処理１２３は、下位層ヒープをクリアする処理である。これは、処理１１０を再帰的に下位層ヒープを対象にして適用する処理である。次に、処理１２４へ進む。
【００２８】
処理１２４は、第１のヒープが記憶している下位層ヒープの線形リストにおいて次の下位層ヒープを取得する処理である。これは、線形リストのセルにある次の下位層ヒープを参照すればよい。次に、判定処理１２２へ戻る。図２では端子Ａを通じて判定処理１２２へ戻るように描かれている。
【００２９】
処理１２５は、文字列リストを探索し、対象ヒープ内にあるセルを除去する処理である。文字列リストは、セルの１次元的なつらなりであるが、対象ヒープ内に文字列を確保した際にセルも対象ヒープ内に確保されているため、文字列リストから対象ヒープ内にあるセルを除去する必要がる。セルを除去する処理とは、具体的には、除去するセルの前のセルのポインタを、除去するセルのポインタの値に変更する処理であって、メモリは解放しない。その理由は、メモリの解放が幾分複雑な処理であるためにパフォーマンス低下の原因となるからである。除去するセルのポインタがＮＵＬＬであれば、そこが終端であることを表しているので、そのまま代入してよい。処理１２５は、文字列リストを順に探索してそのセルのアドレスが対象ヒープに含まれているか否かを判定し、含まれていれば除去する。また、あるセルが対象ヒープ内に含まれているか否かを判定するために、セルの中にヒープを識別する変数、例えば、ヒープへのポインタやハンドルを持っておき、対象ヒープのそれと比較しても好適である。次に、処理１２６へ進む。
【００３０】
処理１２６は、Ｇｌｏｂａｌオブジェクトのプロパティの線形リストを探索し、対象ヒープ内にあるセルを除去する処理である。この場合も、セルやオブジェクトの使用しているメモリの解放は行わない。次に、処理１２７へ進む。
【００３１】
処理１２７は、対象ヒープのメモリブロックをクリアする処理である。ヒープをクリアする処理は既に説明したが、ここでは、ヒープにおいてメモリブロックを管理している線形リストの先頭にＮＵＬＬを格納して、線形リストに何もない状態にする。これによって、ヒープをクリアする処理１１０は終了する。既に説明したように、図２のフローは、下位層ヒープをクリアする処理１２３にも適用される。
【００３２】
図３は、本発明によるヒープメモリ管理方法の第２の実施の形態を示すフローチャートであり、図４は、図３の処理１３２の詳細を示すフローチャートである。図３と図４において、図１と図２と同じ処理には同一の符号を付してあり、ここでの説明は省略する。
【００３３】
処理１０５の後の処理１３１は、第１のヒープにメモリを確保して、第２のヒープを拡張する処理である。これは、第２のヒープにおいて要求されたメモリが確保できない場合に発生する処理である。メモリ不足を検出した第２のヒープは、上位層ヒープに対して拡張を依頼する。第２のヒープは、上位層が第１のヒープであると記憶しているので、第１のヒープがメモリを確保して提供する。第２のヒープは、当初のメモリブロックの他に拡張用メモリも管理してメモリを確保し、アプリケーションへ提供する。このため、ヒープは、複数の線形リストを管理する。このようにあるヒープにおいてメモリが不足した際に、上位層ヒープが支援することによって、各下位層ヒープに確保するメモリ量を少なく抑えつつ、メモリ不足の発生も抑制することができる。これは、複数のヒープが同時にメモリ不足になる確率が小さいという性質による。下位層ヒープは、拡張用メモリの解放が可能になった時点で、それを上位層ヒープに返し、上位層ヒープは、これを他の下位層ヒープの拡張のために再利用する。これによって、個々の下位層ヒープがメモリ不足に直面したとしても、それらが同時に発生しにくいため、上位層ヒープを含めた全体としては無駄を省くことができる。次に、処理１０６へ進む。
【００３４】
処理１０９の後の処理１３２は、第１のヒープをクリアする処理である。処理１３２が終了すると、図３のフローは終了である。
【００３５】
次に、図４を用いてヒープをクリアする処理１３２を説明する。本例では、図２に比べて拡張用メモリを解放する処理が追加されている。
【００３６】
判定処理１２２で下位層ヒープが存在すると判定された場合に進む処理１４１は、下位層ヒープをクリアする処理である。これは、処理１３２を再帰的に下位層ヒープを対象にして適用する処理である。次に、処理１２４へ進む。
【００３７】
処理１２６の後の処理１４２は、対象ヒープの拡張用メモリとして記憶している拡張用メモリを一つ取得する処理である。上位層ヒープに依頼して得た拡張用メモリは、線形リストとして記憶されているので、その線形リストの先頭位置の拡張メモリを取り出す。次に、判定処理１４３へ進む。
【００３８】
判定処理１４３は、取り出した拡張用メモリが存在しているか否かを判定する処理である。すなわち、取り出した拡張用メモリを指すポインタがＮＵＬＬであるか否かを判定する。ＮＵＬＬである場合、拡張用メモリを記憶している線形リストが終端したことを意味するので、拡張用メモリはもはや存在せず、処理１２７へ進む。ＮＵＬＬ以外である場合、拡張用メモリは存在しているので、処理１４４へ進む。
【００３９】
処理１４４は、拡張用メモリを上位層ヒープにおいて解放する処理である。第１のヒープは上位層ヒープを持っていないので、処理１３２においては処理１４４を実行しないが、処理１４１において第２のヒープがクリアされる際には、第２のヒープは上位層ヒープとして第１のヒープを記憶しているので、第１のヒープにおいて拡張用ヒープが解放される。次に、処理１４５へ進む。
【００４０】
処理１４５は、対象ヒープが記憶している拡張用メモリの線形リストにおいて次の拡張用メモリを取得する処理である。第１のヒープは処理１４５を実行しないが、処理１４１において第２のヒープがクリアされる際には、処理１４５を実行する。次に、判定処理１４３へ戻る。図４では、端子Ｂを通じて判定処理１４３へ戻るように描かれている。
【００４１】
処理１２７は、対象ヒープのメモリブロックをクリアする処理である。これによって、ヒープをクリアする処理１３２は終了する。既に説明したように、図４のフローは、下位層ヒープをクリアする処理１４１にも適用される。
【００４２】
図５は、本発明によるヒープメモリ管理方法の第３の実施の形態を示すフローチャートであり、図６は、図５の処理１５９の詳細を示すフローチャートである。図５と図６において、図１と図２と同じ処理には同一の符号を付してあり、ここでの説明は省略する。
【００４３】
図５において手順を開始すると、処理１５１へ進む。
処理１５１は、図７に示す文字列ツリー７４を作成する処理である。文字列ツリー７４は、文字列リストをツリーによって管理するように拡張したものであり、本発明における生成したオブジェクトを特定する変数を要素とする集合の例である。文字列ツリー７４は、ヒープの階層構造に対応して各ヒープに確保された文字列を、ツリーによって階層的に管理する。ツリーの左の枝に各ヒープの線形リストを持ち、ツリーによって階層構造を表す。図７によってこのツリーを説明する。ツリーは２分木であり、図７の上段に示すようなセル７１を複数個生成してリンクすることによって、ツリーを表す。セル７１の左の枝は、そのヒープにおける文字列のリストを参照し、右の枝には、下位層ヒープたちを格納した下位層のツリーのリストを参照する。ツリーのリストとなっているのは、上位層ヒープは複数の下位層ヒープを持つことを許しているため、複数のツリーがリストとして格納されるからである。
【００４４】
本実施の形態では、リストとは線形リストであるが、そのセルは、セル７１のように２分木によって表されている。したがって、線形リストは、ツリーの特殊な形態と見なすことができる。２分木によるリスト処理は、ＬＩＳＰ言語の知識を持つ技術者には容易に理解されるものである。なお、ツリーにおいては、セルのことをノード（節）と呼ぶことがあるが、セルは、プログラム言語上の構造体に注目した用語であり、ノードは、グラフ構造に注目した用語であり、両者は同じものを意味していると考えても問題はない。
【００４５】
図７の下段がそのツリーの例である。ツリー７４は、ルートから始まり、ツリー７４の左の枝は、本発明による階層的ヒープ管理方法によらないプロセスヒープを利用して生成された文字列を格納したルートの文字列リスト７５を参照する。ツリー７４の右の枝は、本発明による階層的ヒープ管理方法によるツリーのリストを参照する。図７では、このツリーのリストにはただ一つツリー７６が存在している。ツリー７６は、第１のヒープを表しており、その左の枝には、第１のヒープで生成した文字列のリスト７７を参照している。左の枝は、第１のヒープの下位層のヒープに関するツリーのリストを参照している。図７では、下位層のツリーは、ツリー７８とツリー８０の二つが存在している。ツリー７８は、第２のヒープに関するツリーであり、ツリー８０は、第３のヒープに関するツリーである。それぞれの左の枝は、そのヒープで生成した文字列のリスト７９や８１を参照している。それぞれの右の枝はＮＵＬＬになっており、リストが存在しないことを表している。これは、第２、第３のヒープが下位層のヒープを持っていないことに対応している。なお、図７において、第２の集合とは、ツリー７６である第１のヒープのツリーであり、これは、文字列用とＧｌｏｂａｌのプロパティ用の二つがある。また、第３の集合とは、ツリー７８である第２のヒープのツリーであり、これも、文字列用とＧｌｏｂａｌのプロパティ用の二つがある。次に、処理１５２へ進む。
【００４６】
処理１５２は、Ｇｌｏｂａｌオブジェクトを作成する処理である。Ｇｌｏｂａｌオブジェクトのプロパティは、本発明ではツリーによって表現する。すなわち、各ヒープで生成したプロパティを、ヒープの階層構造に対応したツリーで管理する。この様子は図７と相似である。ツリーで表現したＧｌｏｂａｌオブジェクトのプロパティも、本発明における生成したオブジェクトを特定する変数を要素とする集合の例である。次に、処理１０３へ進む。
【００４７】
処理１０３の後の処理１５３は、第１のヒープのツリー７６を文字列ツリー７４に追加する処理である。最初にツリー７４の右の枝にはヌルリストを作成しておくので、新しいセル７１を第１のヒープ上に作成してツリー７６とし、ヌルリストの中に入れて、要素として参照する。第１ヒープのツリー７６の左の枝には、文字列リスト７７が参照され、右の枝には，ヌルリストを作成しておく。ヌルリストとは、セルの左の枝がＮＵＬＬで右の枝もＮＵＬＬであるセルである。次に，処理１５４へ進む。
【００４８】
処理１５４は，第１ヒープのツリーをＧｌｏｂａｌのプロパティツリーに追加する処理である。このツリー構造は，処理１５３とほぼ同じであるが、文字列リストの代わりに、ヒープ上で作成したＧｌｏｂａｌのプロパティすなわちグローバル変数のリストを参照することが違う。これらの処理１５３，１５４によって、第１のヒープ内のオブジェクトを特定する変数を要素とする第２の集合が作成される。次に、処理１０４へ進む。
【００４９】
処理１０４の後の処理１５５は、第２のヒープのツリー７８を文字列ツリー７４の第１のヒープのツリー７６の下位層のリストの中に追加する処理である。この場合も、新しいセル７１を第２のヒープ上に作成してツリー７８とし、第１ヒープのツリー７６の右の枝にあるヌルリストの左の枝に追加する。次に、処理１５６へ進む。
【００５０】
処理１５６は、第２のヒープのツリーをＧｌｏｂａｌのプロパティツリーの第１のヒープのツリーの下位層のリストの中に追加する処理である。この処理も、処理１５５とほぼ同じであり、文字列リストがＧｌｏｂａｌのプロパティのリストに代わるだけである。これらの処理１５５，１５６によって、第２のヒープ内にオブジェクトを特定する変数を要素とする第３の集合を作成するとともに、第３の集合を第３の集合の下位層として記憶するツリーを作成する。したがって、処理１５５と処理１５６とでは、第３の集合の作成とツリーの作成が一つの処理となっている。次に、処理１０５へ進む。
【００５１】
処理１０７の後の処理１５７は、文字列ツリー７４の中の第２ヒープのツリー７８下の文字列リストに名前Ｎを追加する処理である。第２ヒープのツリー７８の左の枝にはヌルリストが作成されているので、ヌルリストの左の枝が名前Ｎを参照するように設定する。次に、処理１５８へ進む。
【００５２】
処理１５８は、Ｇｌｏｂａｌのプロパティツリーの第２のヒープのツリー下のプロパティのリストに、名前Ｎという名前でオブジェクトＯを追加する処理である。これは、第２ヒープ上に新しいセル７１を作成し、その左の枝が名前Ｎを参照し、右の枝がオブジェクトＯを参照しておき、この新しいセルを第２ヒープのプロパティリストに追加する。左の枝と右の枝の両方に参照があるようなセルは、ドット対あるいはドットリストと呼ばれている。次に、処理１５９へ進む。
【００５３】
処理１５９は、第１のヒープをクリアする処理である。処理１５９の詳細は図６に示してある。処理１５９が終ると図５のフローは終了である。次に、図６を用いてヒープをクリアする処理１５９を説明するが、図２と同一処理については、説明を省略する。
【００５４】
判定処理１２２で下位層ヒープが存在すると判定された場合に進む処理１６１は、下位層ヒープをクリアする処理である。これは、処理１５９を再帰的に下位層ヒープを対象にして適用する処理である。次に、処理１２４へ進む。
【００５５】
判定処理１２２で下位層ヒープが存在しないと判定された場合に進む処理１６２は、対象としている第１のヒープのツリー７６を文字列ツリー７４から除去する処理である。文字列ツリー７４の右の枝には、下位層ヒープのツリーのリストがあり、現在は第１のヒープのみが存在するので、第１ヒープのツリーを除去するには、リストの右の枝にＮＵＬＬを代入する。このときのリストはヌルリストになる。なお、ここではメモリの解放は行わない。次に、処理１６３へ進む。
【００５６】
処理１６３は、対象としている第１のヒープのツリーをＧｌｏｂａｌのプロパティツリーから除去する処理である。この処理１６３は、処理１６２とほぼ同じであってツリーが違うだけである。次に、処理１２７へ進む。
【００５７】
本実施の形態では、文字列とグローバル変数がツリーによって管理されているため、線形リストを順次探索してそれが対象ヒープに含まれているかどうかを判定する必要がなくなっており、効率よくヒープをクリアすることができる。
【００５８】
図８は、本発明による階層的ヒープ管理方法を実施するＥＣＭＡＳｃｒｉｐｔランタイムソフトウエアのブロック図である。
スクリプト１は、ＵＴＦ−１６でエンコーディングされたテキストであり、図示していないＤＯＭツリーに格納されていたものが入力される。パーサ２は、スクリプト１を解釈するブロックであり、スクリプト１に含まれている文字列が文字列リスト３に含まれているか否かを検査し、含まれていなければ新しく登録する。パーサ２は、スクリプト１の式の形を解釈してツリー表現４を作成して出力する。ツリー表現４は、例えば第２のヒープメモリ上に動的に作成される。
【００５９】
次に、ツリー表現４がＥｖａｌｕａｔｅｒ５に入力され、評価される。すなわち、文字列が表しているオブジェクトを参照して、文字列が表しているメソッドを適用して結果を得、それを文字列が表している変数に代入する。オブジェクトは、オブジェクトメモリ６に作成されている。オブジェクトメモリ６は、本発明によって階層的に管理された複数のヒープを含んでおり、プロセスヒープを含んでもよい。各オブジェクトは、既に作成してあるプロトタイプに関連付けて動的に作成されており、各オブジェクトのプロパティには、メンバー変数とメンバーメソッドが関連付けられている。このメンバーメソッドが呼び出されると、ＥＣＭＡＳｃｒｉｐｔランタイムを実装しているネィティブ言語であるＣ言語の関数が呼び出される。
【００６０】
オブジェクトメモリ６には、ＥＣＭＡＳｃｒｉｐｔのＮａｔｉｖｅ  Ｏｂｊｅｃｔ７が存在し、その中には、ＥＣＭＡ−２６２で規定されるオブジェクトが作成されてある。そのようなオブジェクトとして、Ｇｌｏｂａｌオブジェクト８及びＮｕｍｂｅｒオブジェクト９のみを図８に示すが、それ以外にもＥＣＭＡ−２６２が規定した図示しないオブジェクトは多数ある。
【００６１】
オブジェクトメモリ６には、Ｈｏｓｔ  Ｏｂｊｅｃｔ１０も存在し、地上デジタル放送で規定されるオブジェクトが作成されている。これらオブジェクトは、Ｕｒｅｇ１１、Ｇｒｅｇ１２、ＤＯＭ  ＡＰＩ１３、擬似オブジェクト１４である。Ｕｒｅｇ１１とＧｒｅｇ１２は、文字列を要素とする配列であり、ＢＭＬドキュメント間での情報の受け渡しに利用される。ＤＯＭ  ＡＰＩ１３は、ＥＣＭＡＳｃｒｉｐｔからＤＯＭで規定される関数を呼び出すために、ＥＣＭＡＳｃｒｉｐｔ上に設けられたインターフェースである。擬似オブジェクト１４は、オブジェクトの実体を持たないサービス関数群をｂｒｏｗｓｅｒやｎａｖｉｇａｔｏｒといった予約されたオブジェクトのメソッドとして格納しているものである。Ｕｒｅｇ１１、Ｇｒｅｇ１２は、ｂｒｏｗｓｅｒ擬似オブジェクトの一種であるが、ドキュメント間でのメモリの受け渡しのために特別に管理されたメモリ上に作成してある。Ｈｏｓｔ  Ｏｂｊｅｃｔ１０は、ＥＣＭＡ−２６２以外で定義されたオブジェクトであって、スクリプトからプロパティを追加することは禁止されている。
【００６２】
オブジェクトメモリ６には、放送用拡張オブジェクト１５も存在し、地上デジタル放送で規定されるオブジェクトが作成されている。これらオブジェクトは、Ｂｉｎａｒｙ  Ｔａｂｌｅ１６とＸＭＬ  Ｄｏｃ１７である。これらは、スクリプトが必要に応じて作成するオブジェクトであり、Ｈｏｓｔ  Ｏｂｊｅｃｔ１０のような制限がない。Ｂｉｎａｒｙ  Ｔａｂｌｅ１６は、バイナリーデータで伝送される表にアクセスするためのオブジェクトであり、ＸＭＬ  Ｄｏｃ１７は、外部のＸＭＬ文書にアクセスするためのオブジェクトである。
【００６３】
Ｅｖａｌｕａｔｅｒ５は、ツリー表現４を評価する際にスコープオブジェクトを必要とする。スコープオブジェクトは、変数や関数を表す文字列が格納されているオブジェクトであり、Ｇｌｏｂａｌオブジェクト８がその役を担っている。このために、グローバル変数はＧｌｏｂａｌオブジェクト８のプロパティとして記憶される。
【００６４】
Ｅｖａｌｕａｔｅｒ５は、代入文を評価するとある変数に値を関連付け、該当するオブジェクトのプロパティとして格納する。Ｅｖａｌｕａｔｅｒ５の各動作に必要なメモリもヒープ上に確保されるが、例えば第２のヒープが用いられる。Ｅｖａｌｕａｔｅｒ５による評価が終わると、ツリー表現４の多くのメモリは不要となる。但し、関数を定義するスクリプトの場合は、ツリー表現４がその関数を表しているので、引き続き利用される。
【００６５】
図９は、本発明による階層的ヒープ管理方法を実施する本発明による階層的ヒープ管理装置の実施の形態を示す図である。この階層的ヒープ管理装置は、制御部２１と、バス２２と、ＲＡＭ２３と、ＲＯＭ２４と、ＦｌａｓｈＲＯＭ２５と、表示部２６と、キー２７と、無線部２８と、オーディオ部２９と、マイクロホン３０と、スピーカ３１と、デジタル放送受信部３２とを具え、図８に示すようなＥＣＭＡＳｃｒｉｐｔランタイムソフトウエアが、制御部２１、ＲＡＭ２３、ＲＯＭ２４及びＦｌａｓｈＲＯＭ２５によって実現される。
【００６６】
上記実施の形態によれば、第１のヒープをクリアする際に、下位層である第２のヒープをクリアし、第２のヒープをクリアする際に、集合から第２のヒープ内のオブジェクトを特定する変数を除去し、ヒープ内に動的に確保したメモリを個別に解放しなくてもヒープを一括してクリアするので、メモリーリークが生じなくなり、その結果、ガベージコレクションを不要とすることができる。その結果、ガベージコレクションによるパフォーマンスの一時的な低下が避けられ、また、ガベージコレクションを開発するコストも不要となる。
【００６７】
また、ヒープごとに確保とクリアを行うため、ヒープをアロケートする上位層ヒープではフラグメンテーションが生じなくなり、下位層ヒープの中では、フラグメンテーションが問題となる前にヒープ自体が不要になりクリアするような用途で使用すればよい。ＢＭＬブラウザに本発明を適用すれば、ガベージコレクション（のメモリコンパクション機能）を不要とすることができる。
【００６８】
また、ガベージコレクション以外にも、ヒープにメモリを確保し、後にこれを解放するという処理自体も、小さなメモリを大量に操作する場合には、メモリ管理のための処理が増大しパフォーマンスの低下が問題となっているが、上記実施の形態によれば、唯一のプロセスヒープを用いるのではなく、用途ごとに複数のヒープを用いることにより、メモリ管理の処理が軽減され、パフォーマンスの低下を避けることができる。
【００６９】
本発明は上記実施の形態に限定されるものではなく、当業者であれば本開示に基づき種々の変形や修正を行うことが容易であることに注意されたい。したがって、これらの変形や修正は本発明の範囲に含まれることに留意されたい。
【図面の簡単な説明】
【００７０】
【図１】本発明によるヒープメモリ管理方法の第１の実施の形態を示すフローチャートである。
【図２】図１の処理１１０の詳細を示すフローチャートである。
【図３】本発明によるヒープメモリ管理方法の第２の実施の形態を示すフローチャートである。
【図４】図３の処理１３２の詳細を示すフローチャートである。
【図５】本発明によるヒープメモリ管理方法の第３の実施の形態を示すフローチャートである。
【図６】図５の処理１５９の詳細を示すフローチャートである。
【図７】文字ツリーの作成を説明するための図である。
【図８】本発明による階層的ヒープ管理方法を実施するＥＣＭＡＳｃｒｉｐｔランタイムソフトウエアのブロック図である。
【図９】本発明による階層的ヒープ管理方法を実施する本発明による階層的ヒープ管理装置の実施の形態を示す図である。
【符号の説明】
【００７１】
１  スクリプト
２  パーサ
３，７２  文字列リスト
４  ツリー表現
５  Ｅｖａｌｕａｔｅｒ
６  オブジェクトメモリ
７  Ｎａｔｉｖｅ  Ｏｂｊｅｃｔ
８  Ｇｌｏｖａｌオブジェクト
９  Ｎｕｍｂｅｒオブジェクト
１０  Ｈｏｓｔ  Ｏｂｊｅｃｔ
１１  Ｕｒｅｇ
１２  Ｇｒｅｇ
１３  ＤＯＭ  ＡＰＩ
１４  擬似オブジェクト
１５  放送用拡張オブジェクト
１６  Ｂｉｎａｒｙ  Ｔａｂｌｅ
１７  ＸＭＬ  Ｄｏｃ
２１  制御部
２２  バス
２３  ＲＡＭ
２４  ＲＯＭ
２５  ＦｌａｓｈＲＯＭ
２６  表示部
２７  キー
２８  無線部
２９  オーディオ部
３０  マイクロホン
３１  スピーカ
３２  デジタル放送受信部
７１  セル
７３  下位層のリスト
７４，７６，７８，８０  文字列ツリー
７５  ルートリスト
７７  第１リスト
７９  第２リスト
８１  第３リスト
【図１】
2007179154.tif 000003
【図２】
2007179154.tif 000004
【図３】
2007179154.tif 000005
【図４】
2007179154.tif 000006
【図５】
2007179154.tif 000007
【図６】
2007179154.tif 000008
【図７】
2007179154.tif 000009
【図８】
2007179154.tif 000010
【図９】
2007179154.tif 000011