(57)【要約】【課題】性能が向上した動的メモリ管理方法及びその装置を提供する。【解決手段】相対的に頻繁に生成され、サイズが小さくて寿命の短い客体が単位メモリブロックに順次に割り当てられ、また、これらが単位メモリブロックから放出されれば、客体のサイズ別に準備された再使用フリーリストに各々のサイズに応じて追加され、以後同一のサイズの客体に対する割り当て要求がある時に再使用される。このような順次割り当てと客体再使用とによりシステム性能を向上させることができる。【選択図】図８
2005108216.tif 000002
【特許請求の範囲】
【請求項１】
客体志向プログラムの動的メモリ管理方法において、
所定のサイズのメモリブロックを準備し、
前記メモリブロックに連続して客体を割り当てることを特徴とする動的メモリ管理方法。
【請求項２】
多数個の再使用フリーリストを準備することをさらに含み、
前記メモリブロックから放出された客体は、そのサイズに対応する再使用フリーリストに再使用可能客体で追加されることを特徴とする請求項１に記載の動的メモリ管理方法。
【請求項３】
新しい客体割り当て要求があれば、前記割り当て要求された客体のサイズに対応する再使用フリーリストに再使用可能客体があるか否かを確認し、
再使用可能客体が再使用フリーリストにあれば、前記再使用可能客体が示す前記メモリブロックの特定領域に新しい客体を再割り当て、前記再使用可能客体を前記再使用フリーリストから除去し、
再使用可能客体が再使用フリーリストになければ、前記メモリブロックで最後に位置する客体の次に、前記新しい客体割り当てがなされることを特徴とする請求項２に記載の動的メモリ管理方法。
【請求項４】
客体割り当てのためのフリーリンクリストを作ることをさらに含み、
あらかじめ決められた境界値と同一、または境界値より小さいサイズの客体に対する客体割り当て要求があれば、前記割り当て要求された客体が前記メモリブロックに割り当てられるように前記フリーリンクリストのノードから前記境界値のサイズより大きく前記所定のサイズのメモリブロックを準備し、
前記境界値より大きい客体に対する客体割り当て要求があれば、前記フリーリンクリストから要求された客体のサイズに対応するノードを生成して、ここに客体を割り当てることを特徴とする請求項１乃至請求項３項のうちのいずれか一項に記載の動的メモリ管理方法。
【請求項５】
客体志向プログラムの動的メモリ管理方法において、
（ａ）複数個の客体を割り当てるためのメモリブロックを準備し、
（ｂ）再使用フリーリストに割り当て要求された客体のサイズと同一な再使用可能客体が存在すれば、存在する再使用可能客体が示す前記メモリブロックの特定の場所に客体を再割り当て、存在する前記再使用可能客体を前記再使用フリーリストから除去し、
（ｃ）再使用フリーリストに割り当て要求された客体のサイズと同一な再使用可能客体が存在しなければ、前記メモリブロックで最後に位置する客体の次に前記新しい客体を割り当て、
（ｄ）前記メモリブロックから放出された客体をそのサイズに対応する再使用フリーリストに追加することを含むことを特徴とする動的メモリ管理方法。
【請求項６】
前記メモリブロックを準備する前に、割り当て要求された客体のサイズとあらかじめ決められた境界値のサイズとを判断することをさらに含み、
前記境界値と同一、または境界値より小さいサイズの客体に対するメモリ管理は前記段階 (ａ)〜(ｂ)を通じて行われ、
前記境界値より大きい客体に対するメモリ管理はメモリ管理ユニットによって行われることを特徴とする請求項５に記載の動的メモリ管理方法。
【請求項７】
前記メモリブロックに割り当てられる客体の抽象化されたデータ構造は割り当てられる客体のサイズに対する情報と、客体が割り当てられるメモリブロックのアドレスを示すアドレス指示ポインタと、前記メモリブロックから放出される客体を示す放出客体指示ポインタとを含み、
前記再使用フリーリストは前記境界値のサイズを配列のサイズとし、ＮＵＬＬポインタを元素とする配列を生成することによって作られ、
前記メモリブロックから客体が放出されれば、放出される客体のサイズに対応する再使用フリーリストのＮＵＬＬポイントが前記放出される客体を示すことを特徴とする請求項５または請求項６に記載の動的メモリ管理方法。
【請求項８】
前記メモリブロックから客体が放出されれば、現在放出される客体のサイズに対応する再使用フリーリストのＮＵＬＬポインタが現在放出される客体を示し、現在放出される客体の放出客体指示ポインタは以前に放出された客体を示すことを特徴とする請求項７に記載の動的メモリ管理方法。
【請求項９】
客体志向プログラムの動的メモリ管理方法において、
客体割り当てのためのフリーリンクリストを形成し、
あらかじめ決められた境界値より大きい客体は前記フリーリンクリストから同一のサイズのノードを合成して、その所に割り当てさせ、
前記境界値と同一、または境界値より小さい客体は前記フリーリンクリストから前記境界値より大きいサイズのメモリブロックを準備して、その所に連続して割り当てさせ、同一のサイズの再使用可能客体が再使用フリーリストにあれば、存在する再使用可能客体が示す所のメモリブロックに客体を割り当てることを特徴とする動的メモリ管理方法。
【請求項１０】
前記メモリブロックに割り当てられる客体の抽象化されたデータ構造は割り当てられる客体のサイズに対する情報と、客体が割り当てられるメモリブロックのアドレスを示すアドレス指示ポインタと、前記メモリブロックから放出される客体を示す放出客体指示ポインタとを含み、
前記再使用フリーリストは前記境界値のサイズを配列のサイズとし、ＮＵＬＬポインタを元素とする配列を生成することによって作られ、
前記メモリブロックから客体が放出されれば、それに対応する再使用フリーリストのＮＵＬＬポインタが前記放出される客体を示すことを特徴とする請求項９に記載の動的メモリ管理方法。
【請求項１１】
前記メモリブロックから客体が放出されれば、現在放出される客体のサイズに対応する再使用フリーリストのＮＵＬＬポインタが現在放出される客体を示し、現在放出される客体の放出客体指示ポインタは以前に放出された客体を示すことを特徴とする請求項１０に記載の動的メモリ管理方法。
【請求項１２】
実際の客体志向プログラムで頻繁に生成されて消滅する客体の分析を通じて前記境界値のサイズを決めることをさらに含むことを特徴とする請求項９に記載の動的メモリ管理方法。
【請求項１３】
客体志向プログラムを実行させるためデータ処理装置に、
客体割り当てのためのフリーリンクリストを形成する機能と、
あらかじめ決められた境界値より大きい客体は前記フリーリンクリストから同一のサイズのノードを合成して、その所に割り当てさせる機能と、
前記境界値と同一、または境界値より小さい客体は前記フリーリンクリストから前記境界値より大きいサイズのメモリブロックを準備し、その所に連続して割り当てさせ、同一のサイズの再使用可能客体が再使用フリーリストにあれば、存在する再使用可能客体が示す所のメモリブロックに客体を割り当てる機能を実現させるためのプログラムを記録することを特徴とするコンピュータで読み出すことができる記録媒体。
【請求項１４】
前記再使用フリーリストは前記境界値のサイズを配列のサイズとし、ＮＵＬＬポインタを元素とする配列を生成することによって作られ、
前記メモリブロックから客体が放出されれば、それに対応する再使用フリーリストのＮＵＬＬポイントが前記放出される客体を示すことを特徴とする請求項１３に記載のコンピュータで読み出すことができる記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は客体志向ソフトウエアシステムに係り、さらに詳細には、客体志向ソフトウエアシステムで客体割り当てのための動的メモリ管理に関する。
【背景技術】
【０００２】
客体志向プログラム(Ｏｂｊｅｃｔ  Ｏｒｉｅｎｔｅｄ  Ｐｒｏｇｒａｍ)は典型的な手続きのプログラム(ｐｒｏｃｅｄｕａｒｌ  ｐｒｏｇｒａｍ)に比べて様々な利点、例えば、相続を通じたコード再使用、カプセル化、データの抽象化、多形成、演算子オーバーローディングなど、がある。そこで、客体志向プログラムに対する持続的な開発が行なわれている。多くの研究結果によれば、動的メモリ管理がソフトウエアシステムで最も比重ある構成要素のうちの一つであり、プログラム実行時間の約３０％までが消耗される。したがって、動的メモリ管理(Ｄｙｎａｍｉｃ  Ｍｅｍｏｒｙ  Ｍａｎａｇｅｍｅｎｔ)に対する重要性は増加しており、プログラム動作速度を向上させるためには効率的な動的メモリ管理が必要となる。
【０００３】
従来の動的メモリ管理では、客体のサイズに関係なしに、同一の方法でメモリを割り当てる(ｍｅｍｏｒｙ  ａｌｌｏｃａｔｉｏｎ) 。従来の動的メモリ管理に対して図１及び図２を参照して説明する。図１は一般的なメモリ割り当てを説明するための図式化された流れ図であり、図２は図１のメモリ割り当てで実行される動作を説明するための模式図である。
【０００４】
まず、図１を参照して、段階Ｓ１０１でプログラムが開始される。段階Ｓ１０３で、運営体制Ｏ／Ｓにメモリを要求すれば、(例えば、ＵＮＩＸ（登録商標）上でメモリ管理ユニット ｍａｌｌｏｃ()による関数ｓｂｒｋ()呼び出し)、ヒップ(ｈｉｐ)上にメモリが割り当てられる。段階Ｓ１０５で割り当てられたメモリを適当なサイズで分けて客体を割り当てるためのフリーリンクリスト(ｆｒｅｅ ｌｉｎｋ−ｌｉｓｔ)がメモリ管理ユニットによって生成される(図２の(ａ) 参照)。
【０００５】
客体割り当て要求があれば、割り当て要求された客体のサイズと同一のノードを探すために段階Ｓ１０７でフリーリンクリストを探索する。段階Ｓ１０９で要求された客体と同一のサイズのノードがあるか否かを判断し、フリーリンクリストで同一のノードがあれば、それをフリーリンクリストから分離して段階Ｓ１１１で客体を割り当てる。一方、要求された客体と同一のサイズのノードがなければ、段階Ｓ１１３で、要求された客体のサイズがノードのサイズより大きいか否かを判断する。要求された客体がノードのサイズより大きければ、段階Ｓ１１５で、フリーリンクリストのノードを互いに結合して(ｃｏａｌｅｓｃｉｎｇ) 一つのノードを作り(図２の（ｂ）参照)、段階Ｓ１１７で結合されたノードをフリーリンクリストから分離して客体を割り当てる。一方、要求された客体のサイズがノードのサイズより小さければ、段階Ｓ１１９でノードを分割して(ｓｐｌｉｔｔｉｎｇ)、さらに小さなノードに分離し (図２の（ｃ）参照)、段階Ｓ１２１で、分割されたノードをフリーリンクリストから分離して客体を割り当てる。
【０００６】
一方、割り当てられた客体が消滅すれば、客体が割り当てられたノードは再びフリーリンクリストに挿入されて再使用される。この時、挿入されるノードが大きすぎれば、分割され、さらに小さなノードになって、フリーリンクリストに挿入することができる。
【０００７】
このような一般的な動的メモリ管理によれば、フリーリンクリストに対する探索、フリーリンクリストを構成するノードの結合、分割が行なわれ、これらは相当の時間を消費する。例えば、場合によっては、フリーリンクリストをはじめから最後まで探索しなければならない場合も発生する。
【０００８】
また、客体割り当て要求があるたびに、ｍａｌｌｏｃ（）関数を呼び出さなければならず、また、上述のフリーリンクリストの探索、ノードの分割、結合などの動作を毎度実行しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、性能が向上した動的メモリ管理方法及びその装置を提供することである。
【課題を解決するための手段】
【００１０】
上記の課題を達成するための本発明の一実施の形態による動的メモリ管理方法では、所定のサイズのメモリブロックを準備し、前記メモリブロックに連続して客体を割り当てることを特徴とする。
【００１１】
本発明による割り当て客体のデータ構造は客体のサイズと、アドレス指示ポインタと、放出客体指示ポインタとを具備する。客体のサイズは割り当てられる客体のサイズを示し、アドレス指示ポインタは客体が割り当てられるメモリブロックのアドレスを示し、放出客体指示ポインタはメモリブロックから放出される客体を示す。客体がメモリブロックに連続して割り当てられるので、客体をメモリブロックに割り当てる前に、返還アドレスが分かるようになる。データ構造のサイズ、割り当て要求された客体のサイズ、及び現在アドレスを知っているので、以前に割り当てられた客体の最後のアドレスは容易に計算される。割り当てられる客体の返還アドレスは、直前に割り当てられた客体の最後のアドレスに割り当てられる客体のサイズを合わせたアドレスになるであろう。客体がメモリブロックに順次に割り当てられる時に、放出客体指示ポインタはＮＵＬＬ値を有する。
【００１２】
望ましくは、所定のサイズのメモリブロックは、フリーリンクリスト（ｆｒｅｅ ｌｉｎｋ ｌｉｓｔ）から割り当てられる。例えば、メモリ管理ユニット ｍａｌｌｏｃ（）関数呼び出しによってフリーリンクリストを構成するノードを結合してメモリブロックを準備する。したがって、一回の ｍａｌｌｏｃ（）関数呼び出しによって多数の客体を割り当てることができる。客体割り当てによって準備された所定のサイズのメモリブロックのフリー空間(ｆｒｅｅ ｓｐａｃｅ)がなければ、再びｍａｌｌｏｃ（）関数呼び出しによって同一のサイズのメモリブロックがフリーリンクリストから準備される。
【００１３】
望ましくは、あらかじめ決められた境界値(ｔｈｒｅｓｈｏｌｄ)より小さいサイズの客体がメモリブロックに連続して割り当てられる。あらかじめ決められた境界値は実際の客体志向プログラムに示した客体割り当て類型分析を通じて得ることができる。本発明者が客体志向プログラムの一種であるＣ＋＋プログラムを分析した結果、約９０％以上の客体が再使用され、これらのサイズは非常に小さく、大部分が５１２バイトより大きくない。したがって、境界値は例えば、５１２バイトになりうる。
【００１４】
一方、客体がメモリブロックから放出(ｒｅｌｅａｓｅ)されれば、再使用フリーリスト(ｒｅｕｓｅ ｆｒｅｅ ｌｉｓｔ)に再使用可能客体(ｒｅｕｓａｂｌｅ ｏｂｊｅｃｔ)として追加され、以後、同一のサイズの客体割り当て要求がある時に再使用される。メモリブロックから放出される時、放出客体指示ポインタによって放出された客体が再使用フリーリストに追加される。
【００１５】
再使用フリーリストはポインタタイプの配列によって容易に形成しうる。例えば、境界値のサイズを配列のサイズとし、ポインタタイプの配列を生成すれば、再使用フリーリストが準備される。配列に貯蔵された各ポインタは、ＮＵＬＬに初期化された状態である。例えば、ｋバイトの客体がメモリブロックから放出されれば、配列のｋ番目の元素に貯蔵されたポインタ（＊ｐｋ）がｋバイトの放出された客体を示す。同様に、ｍバイトの客体Ｍがメモリブロックから放出されれば、ｍ番目の元素に貯蔵されたポインタ（＊ｍｐ）が放出されたｍバイトの客体Ｍを示す。また他のｍバイトの客体Ｍ'がメモリブロックから放出されれば、配列のｍ番目の元素に貯蔵されたポインタ＊ｍｐが放出された最近ｍバイト客体Ｍ'を示し、客体Ｍ'の放出客体指示ポインタは以前に放出された客体Ｍを示す。このような方法で、各サイズ別の再使用フリーリストにメモリブロックから放出された再使用客体が追加される。
【００１６】
再使用フリーリストに再使用可能客体が存在するか否かは再使用フリーリストの一番目のノード、すなわち、配列に貯蔵されたポインタがＮＵＬＬではないかを確認することによって決められる。
【００１７】
境界値より小さいサイズの客体に対する割り当て要求があれば、客体のサイズに対応する配列の元素に貯蔵されたポインタがＮＵＬＬであるかを確認する。すなわち、再使用フリーリストに再使用可能客体が連結されているか否かを確認する。もし再使用可能客体があれば(すなわち、配列に貯蔵されたポインタがＮＵＬＬでなければ)、再使用客体のアドレス指示ポインタが示すメモリブロックの所定の領域に客体を再割り当て、再使用可能客体は再使用フリーリストから削除される。一方、再使用フリーリストに再使用客体がなければ(すなわち、配列に貯蔵されたポインタがＮＵＬＬであれば)、メモリブロックで最後に位置する客体の次に(すなわち、最も最近になされた客体割り当て(再使用客体の再割り当て除外)の次に)新しい客体を割り当てる。
【００１８】
一方、境界値より大きいサイズの客体に対する割り当てはメモリ管理ユニットｍａｌｌｏｃ()によって客体割り当てがなされる。すなわち、フリーリンクリスト(ｆｒｅｅ ｌｉｎｋ ｌｉｓｔ)から適当なサイズのノードを探し、これをフリーリンクリストから分離してその所に客体を割り当てる。ここで、境界客体のサイズより大きいサイズの客体は生成が非常珍しく、またその寿命が非常に長いので、フリーリンクリストの探索、ノードの結合及び分割による時間消耗は無視しうる。
【００１９】
本発明によれば、頻繁に発生されて消滅する小さい客体(境界値より小さいサイズの客体)の割り当てに対しては、従来に行われたリンクリストの探索、ノードの結合及び分割プロセスは必要ではない。
【００２０】
本発明の再使用リンクリストの探索は、従来のリンクリストの探索に比べて、その時間が顕著に減少する。なぜなら、配列形成を通じて各サイズ別の再使用リンクリストのアドレスを知っており、また従来のフリーリンクリスト全体の探索と異なって、再使用フリーリストの一番目のノードのみを検査すれば良いためである。
【００２１】
本発明の一実施の形態の他の動的メモリ管理方法では、客体割り当てのためのフリーリンクリストを形成し、あらかじめ決められた境界値より大きい客体は前記フリーリンクリストから同一のサイズのノードを合成して、その所に割り当てさせ、前記境界値と同一、または境界値より小さい客体は前記フリーリンクリストから前記境界値より大きいサイズのメモリブロックを準備して、その所に連続して割り当てさせ、同一のサイズの再使用可能客体が再使用フリーリストにあれば、存在する再使用可能客体が示す所のメモリブロックに客体を割り当てることを含む。
【００２２】
本発明のさらに他の実施の形態によれば、客体志向プログラムを実行させるためにデータ処理装置に、客体割り当てのためのフリーリンクリストを形成する機能と、あらかじめ決められた境界値より大きい客体は前記フリーリンクリストから同一のサイズのノードを合成してその所に割り当てさせる機能と、前記境界値と同一、またはより小さい客体は前記フリーリンクリストから前記境界値より大きいサイズのメモリブロックを準備して、その所に連続して割り当てさせ、同一のサイズの再使用可能客体が再使用フリーリストにあれば、存在する再使用可能客体が示す所のメモリブロックに客体を割り当てる機能を実現させるためのプログラムを記録したコンピュータで読み出すことができる記録媒体を提供する。
【発明の効果】
【００２３】
本発明によれば、客体のサイズによって互いに異なるメモリ管理方法を使用することによって、システム性能を向上させることができる。
【００２４】
頻繁に生成及び消滅する小さい客体に対する割り当てをメモリブロックに連続して順次に行うことによって、従来と異なり、ｍａｌｌｏｃ（）呼び出し回数を減らして客体割り当て速度を向上させることができる。また索引化された再使用フリーリストを別において、メモリブロックから放出された客体を別に再使用フリーリストに追加させて再使用することにより、システムオーバーヘッドを減らし、メモリ管理速度を向上させることができる。
【発明を実施するための最良の形態】
【００２５】
以下、添付の図面を参照して本発明の実施の形態を詳細に説明する。本発明は客体志向プログラムの動的メモリ管理に関するものであって、所定のサイズのメモリブロックに客体が順次に割り当てられる。またメモリブロックで放出された客体は再使用されるために再使用リンクリストに追加されることを特徴とする。
【００２６】
(データ構造)
図３は本発明による客体割り当て及び再使用のためのデータ構造を概略的に示す。本発明による割り当て客体のデータ構造は客体のサイズ（ａｌｌｏｃ ｓｉｚｅ)と、アドレス指示ポインタ(＊ｒｅｔｕｒｎ_ｐｏｉｎｔｅｒ)と、放出客体指示ポインタ（＊ｎｅｘｔ_ｆ）とを具備する。客体のサイズは割り当てられる客体のサイズを示し、アドレス指示ポインタは客体が割り当てられるメモリブロックのアドレスを示し、放出客体指示ポインタはメモリブロックから放出される客体を示す。
【００２７】
(客体の割り当て)
図４は本発明の客体割り当て方法を説明するための模式的流れ図であり、図５は本発明による客体割り当てを説明するための模式図である。図４を参照して、段階Ｓ４０１で客体割り当て（ａｌｌｏｃａｔｉｏｎ）を要求する。段階 Ｓ４０３で割り当て要求された客体のサイズがあらかじめ設定された境界値（ｔｈｒｅｓｈｏｌｄ）と同一、または境界値より小さいかを判断する。境界値は実際の客体志向プログラムに示した客体割り当て類型分析を通じて得ることができる。本発明者が客体志向プログラムの一種であるＣ＋＋プログラムを分析した結果、約９０％以上の客体が再使用され、これらのサイズは非常に小さく、大部分が５１２バイトより大きくない。したがって、境界値は例えば、５１２Ｂｙｔｅ(バイト)になりうる。
【００２８】
割り当て要求された客体のサイズが境界値と同一、または境界値より小さければ、段階Ｓ４０５で客体割り当てのための所定のサイズのメモリブロックを準備する。メモリブロックは例えばメモリ管理ユニットｍａｌｌｏｃ（）によって形成されたフリーリンクリスト（ｆｒｅｅ ｌｉｎｋ ｌｉｓｔ）から確保されうる。メモリブロックのサイズは境界値より大きく、例えば、８ＫＢｙｔｅであってもよい。
【００２９】
段階Ｓ４０７で境界値以下のサイズを有する客体が図５に示したように、連続してメモリブロックに割り当てられる。すなわち、割り当てられた客体のサイズに応じて、メモリブロックを順次占める。すなわち、メモリブロックで以前に割り当てられた客体の次に新しい客体の割り当てが位置する。客体がメモリブロックに連続して割り当てられるので、客体をメモリブロックに割り当てる前に返還アドレスが分かるようになる。データ構造のサイズ、割り当て要求された客体のサイズ及び現在アドレスを知っているので、以前に割り当てられた客体の最後のアドレスは容易に計算される。割り当てられる客体の返還アドレスは直前に割り当てられた客体の最後のアドレスに割り当てられる客体のサイズを合わせたアドレスになるであろう。客体がメモリブロックに順次に割り当てられる時に、放出客体指示ポインタはＮＵＬＬ値を有する。
【００３０】
一つのメモリブロックに連続して客体が割り当てられるので、従来と異なり、ｍａｌｌｏｃ（）関数呼び出しの数を減らすことができる。すなわち本発明によれば、一つのメモリブロックが客体に全部割り当てられた後に、継続的な客体割り当てのためにｍａｌｌｏｃ（）関数によって新しいメモリブロックがフリーリンクリストから確保される。
【００３１】
段階 Ｓ４０３で割り当て要求された客体のサイズが境界値より大きければ、メモリ管理ユニットによって客体割り当てがなされる。すなわち、フリーリンクリストを探索して割り当て要求された客体と同一のサイズのノードを探して、フリーリンクリストから該当ノードを削除し、その所に客体を割り当てる。ここで、境界客体のサイズより大きいサイズの客体は生成されるのが非常に珍しく、またその寿命が非常に長く、フリーリンクリストの探索、ノードの結合及び分割による時間の消耗は無視しうる。
【００３２】
(客体の放出及び再使用フリーリスト)
図６は本発明による客体放出を説明するための模式的流れ図である。段階Ｓ５０１でメモリブロックに割り当てられた客体に対する割り当て解除(ｄｅａｌｌｏｃａｔｉｏｎ)を要求する。段階Ｓ６０３で割り当て解除要求された客体のサイズと境界値のサイズとを比べる。
【００３３】
割り当て解除要求された客体のサイズが境界値と同一、または境界値より小さければ、段階 Ｓ６０５でメモリブロックから客体が放出されて、以後再使用されるために再使用リンクリストに追加される。
【００３４】
再使用フリーリストはポインタタイプの配列によって容易に形成することができる。例えば、境界値のサイズを配列のサイズとし、ポインタタイプの配列を生成すれば、再使用フリーリストが準備される。配列に貯蔵された各ポインタはＮＵＬＬに初期化された状態である。メモリブロックから放出された客体は再使用フリーリストに追加される。すなわち、再使用フリーリストのポインタが放出された客体を示すようになる。ここで、すでに同一のサイズの放出客体が再使用フリーリストに連結されていれば、メモリブロックに割り当てられる時に、ＮＵＬＬに初期化された現在放出客体の放出客体指示ポインタ(＊ｎｅｘｔ_ｆ)は以前に放出された客体を示し、配列に貯蔵されたポインタは現在放出された客体を示すようになる。
【００３５】
他の方法で、現在放出された客体が再使用フリーリストに連結された以前に放出された客体に連結されることもできる。すなわち以前に放出された客体の放出客体指示ポインタ（＊ｎｅｘｔ_ｆ）が現在放出された客体を示すことができる。
【００３６】
(再使用フリーリスト生成)
図７を参照して再使用フリーリストの生成について説明する。図７は再使用リンクリスト生成を説明するための模式図である。
【００３７】
図７を参照して、メモリブロックから放出された客体は再使用フリーリストに追加される。配列を使用したので、再使用フリーリストは索引化されたリストである。メモリブロックから客体が放出されれば、放出される客体に対応する配列の元素に貯蔵されたポインタが放出された客体を示すようになる。すなわち、再使用フリーリストに放出される客体が連結される、配列の各元素に貯蔵されたポインタがＮＵＬＬであるか否かを確認すれば、再使用客体が存在するか否かが容易に分かる。
【００３８】
例えば、境界値が５１２バイトである場合、５１２個のＮＵＬＬポインタを元素とする配列(再使用フリーリスト)があらかじめ形成される。例えば、１バイトのサイズを有する客体がメモリブロックから放出されれば、配列の一番目の元素に貯蔵されたＮＵＬＬポインタ（＊ｐ１）が放出された１バイト客体を示すようになる。再び１バイトのサイズを有する客体がメモリから放出されれば、配列に貯蔵されたポインタ（＊ｐ１）は現在放出された客体を示すようになり、現在放出された客体の放出客体指示ポインタは以前に放出された客体を示すようになる。このような方法で、メモリブロックから放出された客体が再使用フリーリストに追加される。
【００３９】
本発明による再使用フリーリストは索引化されたリストであるので、放出客体の追加及び再使用客体の発見が非常に容易である。
【００４０】
(客体割り当て及び再使用)
図８は本発明による客体割り当て及び再使用を説明するための模式的流れ図である。
【００４１】
プログラムが開始されれば、ｍａｌｌｏｃ（）関数によってプログラムに必要なメモリが運営体制から割り当てられる。段階Ｓ８０１で客体割り当てが要求される。段階Ｓ８０３で割り当て要求された客体のサイズと境界値のサイズとを比べる。割り当て要求された客体のサイズが境界値より大きければ、段階Ｓ８０５でｍａｌｌｏｃ（）関数によって所定のサイズ(例えば、８ＫＢｙｔｅ)のメモリブロックを準備する。
【００４２】
次の段階Ｓ８０７で割り当て要求された客体が新しく割り当てられるか否かが判断される。すなわち、割り当て要求された客体のサイズに対応する配列の元素に貯蔵されたポインタがＮＵＬＬであるか否かを確認する。ＮＵＬＬではなければ(再使用客体が存在すれば)、段階Ｓ８０９で配列に貯蔵されたポインタが示す再使用客体のアドレス指示ポインタによって返されるメモリブロックのアドレスに客体を割り当てる。そして、再使用された客体は再使用リストから削除される。
【００４３】
段階Ｓ８０７で再使用客体が存在しないと判断されれば、段階Ｓ８１３で図４及び図５を参照して説明した客体割り当てがなされる。
【００４４】
一方、段階Ｓ８０３で割り当て要求された客体のサイズが境界値より大きければ、段階Ｓ８１１でｍａｌｌｏｃ（）によってフリーリンクリストを使用して客体割り当てがなされる。
【００４５】
これまで、本発明に対してその望ましい実施の形態を中心にして説明した。本発明が属する技術分野で通常の知識を持つ者は本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態で実現されることができることを理解することができるであろう。したがって、本開示の実施の形態は限定的な観点ではなく、説明的な観点で考慮されなければならない。本発明の範囲は上述の説明ではなく、特許請求の範囲に示されており、それと同等な範囲内にあるすべては本発明に含まれるように解釈されなければならない。
【図面の簡単な説明】
【００４６】
【図１】一般的な客体のためのメモリ割り当てを説明するための図式化された流れ図である。
【図２】図１のメモリ割り当てで実行される動作を説明するための模式図である。
【図３】本発明の客体割り当て方法を説明するための模式的流れ図である。
【図４】本発明による客体割り当てを説明するための模式図である。
【図５】本発明による客体放出を説明するための模式的流れ図である。
【図６】本発明による客体割り当て及び再使用のための抽象化されたデータ構造を概略的に図示する。
【図７】本発明による再使用フリーリスト生成を説明するための模式図である。
【図８】本発明による客体割り当て及び再使用を説明するための模式的流れ図である。
【図１】
2005108216.tif 000003
【図２】
2005108216.tif 000004
【図３】
2005108216.tif 000005
【図４】
2005108216.tif 000006
【図５】
2005108216.tif 000007
【図６】
2005108216.tif 000008
【図７】
2005108216.tif 000009
【図８】
2005108216.tif 000010