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