(57)【特許請求の範囲】
【請求項１】
ｎ個に分割した領域からなり、ｎ分割した各領域が必要に応じて再帰的ｍ個の領域に分割されてなる記憶領域と、
１又は複数の連続する領域をセルとして管理するため、該セル毎に設けられ、該セルのサイズ情報及び記憶領域の先頭からの相対アドレスからなるセル情報を記憶したセル領域と、
１の管理項目制御テーブルと１以上の階層テーブルとから構成され、
該管理項目制御テーブルは、記憶領域が分割された各領域に対応するｎ個のポインタを有し、各ポインタは、対応する領域が分割されていない場合は、当該領域が含まれるセルを管理するセル領域にリンクし、ｍ個に分割されている場合は、分割されたｍ個の領域に対応するｍ個のポインタを有する第１段目の階層テーブルにリンクし、各段の階層テーブルの各ポインタは、対応する領域が分割されていない場合は、当該領域を含むセルを管理するセル領域にリンクし、さらにｍ個に分割されている場合は、分割されたｍ個の領域に対応するｍ個のポインタを有する次段の階層テーブルにリンクするように再帰的に接続されており、
前記セルを検索する時に、当該セルのアドレスおよびサイズ情報をもとに、上記管理項目制御テーブル中の該当するポインタによって、あるいは更に当該ポインタによってリンクされた上記階層テーブル中の該当するポインタによって、目的とするセルを検索する手段と
を備えたことを特徴とする記憶領域管理装置。
【請求項２】
ｎ個に分割した領域からなり、ｎ分割した各領域が必要に応じて再帰的ｍ個の領域に、記憶領域を分割する手段と、
１又は複数の連続する領域をセルとして管理するため、該セル毎に設けられ、該セルのサイズ情報及び記憶領域の先頭からの相対アドレスからなるセル情報を、セル領域に記憶する手段と、
１の管理項目制御テーブルと１以上の階層テーブルとから構成され、
該管理項目制御テーブルは、記憶領域が分割された各領域に対応するｎ個のポインタを有し、各ポインタは、対応する領域が分割されていない場合は、当該領域が含まれるセルを管理するセル領域にリンクし、ｍ個に分割されている場合は、分割されたｍ個の領域に対応するｍ個のポインタを有する第１段目の階層テーブルにリンクし、各段の階層テーブルの各ポインタは、対応する領域が分割されていない場合は、当該領域を含むセルを管理するセル領域にリンクし、さらにｍ個に分割されている場合は、分割されたｍ個の領域に対応するｍ個のポインタを有する次段の階層テーブルにリンクするように再帰的に接続されており、
前記セルを検索する時に、当該セルのアドレスおよびサイズ情報をもとに、上記管理項目制御テーブル中の該当するポインタによって、あるいは更に当該ポインタによってリンクされた上記階層テーブル中の該当するポインタによって、目的とするセルを検索する手段と
して機能させるプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、記憶領域を管理する記憶領域管理装置および記録媒体に関するものである。
【０００２】
【従来の技術】
従来、領域管理プログラムは、フラグメンテーション抑止のために、２のべき乗単位のサイズのセルで領域管理している。セルに対応する管理情報は、制御テーブルに登録して管理している。この際、同じサイズのセルを管理する管理情報（ＣＥ（セル情報））は相互に連鎖（リンク）しているため、セルの探索時には、同じサイズのセルのセル情報のリンクを辿って目的とするセルのセル情報がみつかるまで追跡するようにしていた。
【０００３】
【発明が解決しようとする課題】
このため、記憶領域中に存在するセルのアドレスが分かっているセルであっても、制御テーブル中の同じサイズのセルのリンクを順に辿って目的とするセルを見つける必要があり、探索時間が長く必要になってしまうなどの問題があった。
【０００４】
本発明は、これらの問題を解決するため、記憶領域中のセルのアドレスに対応づけて管理項目制御テーブル中からポインタで、分割した１階層あるいは複数階層の該当サイズ位置に当該セルをリンクすることで、検索対象のセルのアドレスおよびサイズをもとに簡易かつ迅速に目的とするセルを見つけると共に、使用セルあるいは未使用セルのセル情報をテーブルから合わせてリンクし簡易かつ迅速に未使用セルあるいは使用セルを見つけることを目的としている。
【０００５】
【課題を解決するための手段】
図１および図３を参照して課題を解決するための手段を説明する。
図１および図３において、記憶領域１は、所定サイズの領域からなるセル１１を設けるものである。
【０００６】
管理項目制御テーブル２は、記憶領域１を所定サイズでｎ分割した当該分割した各領域に対応するポインタ１ないしポインタｎ（ｎは整数）を登録したりなどするものである。
【０００７】
階層テーブル３は、ポインタ１ないしポインタｎで必要に応じてそれぞれリンクされ、当該ｎ分割した各記憶領域のサイズを更にｍ分割した各領域に対応するポインタ１ないしポインタｍ（ｍは整数）を登録したりなどするものである。
【０００８】
セル１１は、記憶領域１中の所定サイズの領域である。
制御テーブル１２は、使用セルおよび未使用セルのセル情報４へのポインタを登録するものである。
【０００９】
次に、動作を説明する。
記憶領域１を所定サイズでｎ分割した当該分割した各領域に対応するポインタ１ないしポインタｎ（ｎは整数）を登録する管理項目制御テーブル２、およびポインタ１ないしポインタｎで必要に応じてそれぞれリンクされ、当該ｎ分割した各記憶領域１のサイズを更にｍ分割した各領域に対応するポインタ１ないしポインタｍ（ｍは整数）を登録する階層テーブル３を設け、記憶領域１中のセルのアドレスとサイズをもとに管理項目制御テーブル２からセル１１のセル情報４をリンク、あるいは更にリンクされた階層テーブル３中からセル１１のセル情報４をリンクし、セルを管理するようにしている。
【００１０】
この際、セル１１の探索依頼があった時に、当該セル１１のアドレスおよびサイズをもとに、管理項目制御テーブル２中の該当するポインタから目的とするセル１１のセル情報４を見つけたり、あるいは更に当該ポインタでリンクされた階層テーブル３中の該当するポインタから目的とするセル１１のセル情報４を見つけたりするようにしている。
【００１１】
また、管理項目制御テーブル２あるいは階層テーブル３の２つ以上のポインタからセル１１のセル情報４をリンクし、管理項目制御テーブル２あるいは階層テーブル３の２つ以上のサイズのセル１１のセル情報４をリンクするようにしている。
【００１２】
また、階層テーブル３を必要に応じて更に１つあるいは複数リンクし、更に分割した小さなサイズでセルを管理するようにしている。
また、使用セルおよび未使用セルのセル情報４へのポインタを登録する制御テーブル１２を設け、セル１１のセル情報４に対して制御テーブル１２の使用セルあるいは未使用セルからポインタを合わせて登録するようにしている。
【００１３】
また、管理項目制御テーブル２および階層テーブル３に２のべき乗の数のポインタを登録するようにしている。
従って、記憶領域１中のセル１１のアドレスおよびサイズに対応づけて管理項目制御テーブル２中からポインタで、分割した１階層あるいは複数階層の該当サイズ位置に（階層テーブル３を介して）当該セル１１のセル情報４をリンクすることにより、検索対象のセル１１のアドレスおよびサイズをもとに簡易かつ迅速に目的とするセル１１のセル情報４を見つけると共に、使用セルあるいは未使用セルのセル情報４を制御テーブル１２から合わせてリンクすることにより、簡易かつ迅速に未使用セルあるいは使用セルを見つけることが可能となる。
【００１４】
【実施例】
次に、図１から図５を用いて本発明の実施の形態および動作を順次詳細に説明する。
【００１５】
図１は、本発明の説明図（その１）を示す。
図１において、記憶領域１は、所定サイズの領域からなるセルを設けるものであって、例えばサイズ８×ｔ（８ＫＢがｔ個からなるサイズを表す）、サイズ２×ｔ（２ＫＢがｔ個からなるサイズを表す）などからなるセル（セル領域）を設けるものである。
【００１６】
セル１１は、所定サイズの整数倍からなる領域であって、先頭アドレス（例えば記憶領域の先頭からの相対アドレス）とサイズで表現されるものである。
管理項目制御テーブル２は、記憶領域１を所定サイズでｎ分割した当該分割した各領域に対応するポインタ１ないしポインタｎ（ｎは整数）を登録したりなどするものであって、例えば３２ＫＢで記憶領域１をｎ分割して各分割した領域に対応づけてポインタ１からポインタｎを登録するものである。これら登録した各ポインタ１からポインタｎは、セルが当該分割した領域と等しいときは当該セルを直接にポイントし、一方、小さいときは当該分割した領域内のセルを管理するために１階層の階層テーブル３をポイントする。更に、当該１階層の階層テーブル３より小さいサイズのセルを管理するときは２階層の階層テーブル３をポイントすることを繰り返し、任意の小さいサイズのセルをアドレスで直接に管理（ポイント）するようにしている。
【００１７】
階層テーブル３は、管理項目制御テーブル２の最小管理サイズを、分割した小さなサイズ（１倍、２倍などの整数倍のサイズ）でセルを管理するものである。１階層の階層テーブル３の最小サイズよりも、セルのサイズが小さいときは、更に当該１階層の階層テーブル３から２階層の階層テーブル３をポイントとし当該サイズを分割した小さなサイズにセルをリンクして管理する。更に、３階層の階層テーブル３で管理するサイズよりも、セルのサイズが小さいときは更に４階層の階層テーブル３をポイントして管理するようにする。以下同様に階層テーブル３が管理するサイズを小さくして管理できるまで、階層を深くする。
【００１８】
セル情報４は、管理項目制御テーブル２あるいは任意階層の階層テーブル３からポイントされたものであって、セルのサイズ情報および記憶領域１中のアドレス（例えば記憶領域１の先頭からの相対アドレス）などを管理するものである。
【００１９】
次に、図１の構成の動作を説明する。
図１において、▲１▼は、検索対象のセルのアドレスを含む管理項目制御テーブル２中のエントリを見つけた状態を示す。この図示の場合には、検索対象のセルのアドレス（例えば記憶領域１の先頭からの相対アドレス）を、当該管理項目制御テーブル２で用いている記憶領域１の分割サイズ（ここでは、３２ＫＢ）で割り算して何番目のエントリかを求め、この求めた何番目のエントリが▲１▼のエントリである。これにより、検索対象のセルのアドレスをもとに、当該アドレスを含むここでは、３２ＫＢ内に含まれるセル（領域）を管理する管理項目制御テーブル２中のエントリが一意に見つかったこととなる。
【００２０】
▲２▼は、▲１▼で見つけた管理項目制御テーブル２中のエントリからポイントされる１階層ノードの階層テーブル３を見つけた状態を示す。尚、検索対象のセルのサイズが３２ＫＢの場合には、例えば▲１▼’で見つけた管理項目制御テーブル２中のエントリから直接に▲２▼’のセル情報４をポイントする（１階層ノードの階層テーブル３をポイントして更に当該３２ＫＢを８ＫＢの４個のエントリに分割する必要がないので、当該１階層ノードの階層テーブル３を設けることなく、直接に▲２▼’のセル情報４を管理項目制御テーブル２▲１▼’のエントリからポイントする）。
【００２１】
▲３▼は、１階層ノードの階層テーブル３の２つ目のエントリ（８ＫＢの２つ目のエントリ）から更に２階層ノードの階層テーブル３をポイントする。尚、１階層ノードの階層テーブル３から８ＫＢのサイズのセルのセル情報は、▲３▼’に示すように直接にポイントする。また、１階層ノードの階層テーブル３から８ＫＢ×２（＝１６ＫＢ）のサイズのセルのセル情報４は、例えば▲３▼’’に示すように該当する２つのエントリから直接にそれぞれポイントする。
【００２２】
▲４▼は、２階層ノードの階層テーブル３のエントリから、２ＫＢのセルのセル情報４をポイントする。尚、２階層ノードの階層テーブル３から２ＫＢ×２（＝４ＫＢ）のサイズのセルのセル情報４は、例えば▲４▼’に示すように該当する２つのエントリから直接にそれぞれポイントする。
【００２３】
以上によって、記憶領域１中のセル（サイズおよびアドレスの情報を持つセル）について、当該セルのアドレスをもとに管理項目制御テーブル２中のエントリを見つけ、更にセルのサイズをもとに当該管理項目制御テーブル２から直接にセル情報４を見つけ、あるいはサイズが小さいときは更に１階層ノードの階層テーブル３などを順次辿って直接に該当セルのセル情報４を見つけることが可能となる。これにより、セルのアドレスとサイズをもとに管理項目制御テーブル２、更に必要に応じて階層テーブル３を辿って直接に検索対象のセルのセル情報４を簡易かつ迅速に見つけることが可能となる。以下順次詳細に説明する。
【００２４】
図２は、本発明の動作説明フローチャートを示す。
図２において、Ｓ１は、領域アドレスから管理項目制御テーブル２のポインタを求める。これは、既述したように、検索対象のセルのアドレスを、管理項目制御テーブルのエントリに対応づけた記憶領域１の分割サイズ、例えば３２ＫＢで当該検索対象のセルのアドレスを除算して何番目のエントリに該当するかを求め、当該求めたエントリのポインタを取り出す。
【００２５】
Ｓ２は、ノードポインタか判別する。これは、Ｓ１で取り出したポインタがノードポインタ（１階層ノードの階層テーブル３へのポインタ）か判別する。ＹＥＳの場合には、Ｓ３に進む。ＮＯの場合には、ノードポインタではなく、ＣＥ（セル情報、以下同じ）へのポインタ、即ちセルのセル情報４へのポインタと判明したので、Ｓ８で３２×ｔサイズのセル情報４（３２ＫＢ×ｔ（整数）のサイズ）、例えば図１の▲１▼’の管理項目制御テーブル２中のＣＥへのポインタによって▲２▼’のセル情報４を見つけ、目的とするセルのセル情報４が見つかったので検索終了する。
【００２６】
Ｓ３は、領域アドレスのあるビットより１階層ノードのポインタを求める。これは、Ｓ２のＹＥＳで図１の管理項目制御テーブル２中の例えば▲１▼’のエントリにノードへのポインタが設定されていると判明したので、このポインタでポイントされる▲２▼の１階層ノードの階層テーブル３中から、検索対象のセルのアドレスが含まれる階層テーブル３中のエントリを求め、この求めたエントリのポインタ（ＣＥへのポインタ、あるいはノードへのポインタ）を取り出す。
【００２７】
Ｓ４は、Ｓ３で取り出したポインタがノードポインタか判別する。ＹＥＳの場合には、Ｓ５に進み、Ｓ３と同様に、領域アドレスのあるビットより２階層ノードのポインタ（ＣＥへのポインタ、あるいはノードへのポインタ）を求める。一方、Ｓ４のＮＯの場合には、ノードポインタではなく、ＣＥへのポインタと判明、即ちセルのセル情報４へのポインタと判明したので、Ｓ９に進む。
【００２８】
Ｓ９は、１６ＫＢ×ｔサイズＣＥか判別する。これは、Ｓ４のＮＯで、セルのセル情報４へのポインタと判明したので、更に、１６ＫＢの整数倍（ここでは、２倍）のセルのセル情報４へのポインタか判別する。ＹＥＳの場合には、Ｓ１０で１６ＫＢ×ｔ（ｔは整数）のＣＥ、例えば８ＫＢの２倍の１６ＫＢのセルのセル情報４が見つかったので検索終了する。一方、Ｓ９のＮＯの場合には、Ｓ１１で８ＫＢ×ｔ（整数）のＣＥ、例えば８ＫＢのセルのセル情報４が見つかったので検索終了する。
【００２９】
Ｓ５は、Ｓ３と同様に、領域アドレスのあるビットより１階層ノードのポインタを求める。これは、Ｓ４のＹＥＳで図１の１階層ノードの階層テーブル３中の例えば▲２▼’’のエントリにノードへのポインタが設定されていると判明したので、このポインタでポイントされる▲３▼の２階層ノードの階層テーブル３中から、検索対象のセルのアドレスが含まれる２階層ノードの階層テーブル３中のエントリを求め、この求めたエントリのポインタ（ＣＥへのポインタ、あるいはノードへのポインタ）を取り出す。
【００３０】
Ｓ６は、４×ｔサイズＣＥか判別する。これは、Ｓ５で取り出したエントリの内容が、４×ｔサイズＣＥ、即ち４ＫＢのｔ倍（整数倍）のセルのセル情報４へのポインタか判別する。ＹＥＳの場合には、Ｓ７で４ＫＢ×ｔのＣＥ、即ち４ＫＢ×ｔ倍のセルのセル情報４が見つかったので、検索終了する。一方、ＮＯの場合には、Ｓ１２で２ＫＢ×ｔのＣＥ、即ち２ＫＢ×ｔ倍のセルのセル情報４が見つかったので、検索終了する。
【００３１】
以上によって、検索対象のセルのアドレスとサイズをもとに、既述した図１の項目管理制御テーブル３および階層テーブル３を辿って検索対象のセルのセル情報４を簡単かつ迅速に見つけることが可能となる。
【００３２】
図３は、本発明の説明図（その２）を示す。これは、制御テーブル（未使用／使用）を設けて未使用のセルのセル情報４あるいは使用中のセルのセル情報４をポイントし、セル１１の領域を開放、あるいはセル１１の領域の獲得を迅速に行えるようにしたものである。ここで、記憶領域１、セル１１、管理項目制御テーブル３、および階層テーブル４は、既述した図１の同一番号のものと同一であるので、説明を省略する。
【００３３】
図３において、制御テーブル（未使用／使用中）１２は、未使用のセルのセル情報４へのポインタ、あるいは使用中のセルのセル情報４へのポインタを登録して管理するものである（図中では一部のセルのセル情報４にのみポイントしているが、実際は全てのセルのセル情報４についてポイントする）。この制御テーブル（未使用／使用中）１２を設けたことで、既述した図１のセルのセル情報４について、未使用のセルのセル情報４あるいは未使用のセルのセル情報４を区別して簡易かつ迅速に検索することが可能となる。この際、制御テーブル１２のエントリには、未使用のセルと、使用中のセルについて、当該セルのアドレスとサイズに対応するエントリの位置に、該当セルのセル情報４へのポインタと使用中あるいは未使用である旨のフラグを設定したり、あるいは未使用と使用中の制御テーブル１２を内部的に分けて、セルのアドレスとサイズに対応するエントリの位置に、当該セルのセル情報４へのポインタを設定したりするようにする。
【００３４】
以上のように、未使用のセルのセル情報４および使用中のセルのセル情報４へのポインタを制御テーブル１２に登録することにより、使用中のセルを開放する場合や、未使用のセルの領域を獲得したりする場合に迅速かつ簡易に未使用セルや使用中セルを見つけることが可能となる。
【００３５】
図４は、本発明の説明図（その３）を示す。これは、階層テーブル３を１階層ノード、２階層ノード、・・・ｍ階層ノードを設け、深い階層ノードになるに従い、小さいサイズのセルのセル情報４を登録して管理するものである。ここでは、
・管理項目制御テーブル２：
・１階層ノードの階層テーブル３：
・２階層ノードの階層テーブル３：
・・・
・ｍ階層ノードの階層テーブル３：
という階層構造で、
第１に、記憶領域１の全体のサイズを、複数に分割した各サイズに対応づけたエントリ（ポインタ）を管理項目制御テーブル２に登録して管理し、
第２に、管理項目制御テーブル２で管理する最小サイズを、複数に分割した各サイズに対応づけたエントリ（ポインタ）を１階層ノードの階層テーブル３に登録して管理し、
第３に、１階層ノードの階層テーブル３で管理する最小サイズを、複数に分割した各サイズに対応づけたエントリ（ポインタ）を２階層ノードの階層テーブル３に登録して管理し、
第４に、同様にして繰り返し、（ｍ−１）階層ノードの階層テーブル３で管理する最小サイズを、複数に分割した各サイズに対応づけたエントリ（ポインタ）をｍ階層ノードの階層テーブル３に登録して管理する。
【００３６】
以上のように、階層化してセルのセル情報４を登録して管理することにより、大きなサイズのセルから小さなセルまで効率的に登録して管理し、簡単かつ迅速に目的とするセル（アドレスとサイズを持つセル）を検索することが可能となる。
【００３７】
図５は、本発明の説明図（その４）を示す。これは、１階層ノードの階層テーブル３、２階層ノードの階層テーブル３、３階層ノードの階層テーブル３、４階層ノードの階層テーブル３について、それぞれ８エントリ（２の３乗＝８エントリ）でそれぞれ階層化（８×８×８×８＝４０９６）した例である。例えば管理項目制御テーブル２の１エントリに対応する記憶領域１上のサイズを３２ＫＢ（正確には２の１５乗＝３２．７６８ＫＢ）とすると、図５の４階層化すると、４階層ノードの階層テーブル３の最小サイズは３２７６８／４０９６＝８Ｂとなり、最小サイズ８Ｂの整数倍のセルのセル情報４を１階層ノードから４階層ノードの階層テーブル３、あるいは３２ＫＢのセルのときは管理項目制御テーブル２からポイントし登録して管理することが可能となる。
【００３８】
以上のように、階層テーブル３を複数に階層化することで、非常に小さいサイズ単位にセルのセル情報４をポイントして管理し、簡単かつ迅速に検索することが可能となる。
【００３９】
【発明の効果】
以上説明したように、本発明によれば、記憶領域１中のセル１１のアドレスに対応づけて管理項目制御テーブル２中からポインタで、分割した１階層あるいは複数階層の該当サイズ位置に（階層テーブル３を介して）当該セル１１のセル情報４をリンクする構成を採用しているため、検索対象のセル１１のアドレスおよびサイズをもとに簡易かつ迅速に目的とするセルを検索することができると共に、使用セルあるいは未使用セルのセル情報４を制御テーブル１２から合わせてリンクする構成を採用することで、簡易かつ迅速に未使用セルあるいは使用セルを検索して領域を獲得したり、開放したりできる。
【図面の簡単な説明】
【図１】本発明の説明図（その１）である。
【図２】本発明の動作説明フローチャートである。
【図３】本発明の説明図（その２）である。
【図４】本発明の説明図（その３）である。
【図５】本発明の説明図（その４）である。
【符号の説明】
１：記憶領域
２：管理項目制御テーブル
３：階層テーブル
４：セル情報
１１：セル
１２：制御テーブル
【図１】
0003846614.tif 000002
【図２】
0003846614.tif 000003
【図３】
0003846614.tif 000004
【図４】
0003846614.tif 000005
【図５】
0003846614.tif 000006