(57)【要約】【課題】サブセグメントのサイズを動的に変更することにより、より利用効率の高いメモリ管理が行えるようにする。【解決手段】メモリ領域３は複数のセグメント４に分割され、各セグメントは更に複数のサブセグメント５より構成される。領域取得処理部１１は、任意のメモリ要求プロセス９からのメモリ取得要求がある毎に、未使用のセグメント４に関しては、要求された領域サイズに基づいてサブセグメントのサイズを決定して、このサイズのサブセグメント５を生成して、１又は複数のサブセグメント５を割り当てると共に、このセグメント４を使用中とする。使用中のセグメント４に関しては、要求された領域サイズに基づいてサブセグメント５を再生成するか否かを判定し、再生成する場合には要求された領域サイズに基づいてサブセグメント５のサイズを決定して、空き領域についてサブセグメント５を再生成する。【選択図】図１
2009129187.tif 000002
【特許請求の範囲】
【請求項１】
メモリ領域を複数のセグメントに分割管理し、更に該各セグメントを複数のサブセグメントに分割管理するメモリ管理装置であって、
任意のメモリ要求プロセスによって任意の割り当て要求があると、任意の前記セグメントを対象として、
該セグメントが未使用である場合には、前記割り当て要求された領域サイズに基づいて該セグメントにおける前記サブセグメントのサイズを決定して複数のサブセグメントを生成し、１又は複数の該サブセグメントを前記要求に対して割り当てると共に該セグメントを使用中とする第１の領域取得手段と、
前記セグメントが前記使用中である場合には、前記割り当て要求された領域サイズと前記生成済みのサブセグメントのサイズとに基づいて再分割が必要か否かを判定し、再分割が必要と判定された場合には、該割り当て要求された領域サイズに基づいて該セグメントの空き領域における前記サブセグメントのサイズを再決定して、該空き領域において複数の新たなサブセグメントを生成し、１又は複数の該新たなサブセグメントを前記要求に対して割り当てる第２の領域取得手段と、
を有することを特徴とするメモリ管理装置。
【請求項２】
前記第１の領域取得手段又は前記第２の領域取得手段における前記サブセグメントサイズの決定処理は、予め登録されている複数のサブセグメントサイズのなかから前記割り当て要求された領域サイズとの差が最も小さい割り当て領域を生成できるサブセグメントサイズを選択するものであり、該領域サイズとの差が最も小さいサブセグメントサイズが複数ある場合には、そのなかで最もサイズが大きいものに決定することを特徴とする請求項１記載のメモリ管理装置。
【請求項３】
前記第２の領域取得手段は、前記割り当て要求された領域を前記１又は複数のサブセグメントに割り当てたときに余る領域のサイズが、予め設定される所定値以上である場合に、再分割が必要と判定することを特徴とする請求項１記載のメモリ管理装置。
【請求項４】
複数の前記セグメントが前記使用中の状態になったときに、該複数のセグメントの何れかを移動先または移動元として、該移動元のセグメントにおいて前記要求に対して割り当てられた領域のデータを、前記移動先のセグメントの空き領域に移動させる領域最適化手段を更に有することを特徴とする請求項１〜３の何れかに記載のメモリ管理装置。
【請求項５】
前記領域最適化手段は、前記移動先のセグメントの各空き領域のサイズを求め、前記移動元の領域のサイズに最も近いサイズの空き領域を移動先に決定して前記データの移動を行うと共に、該移動の際、前記移動先となる空き領域のサブセグメントのサイズが前記移動元の領域に係るサブセグメントのサイズと異なる場合には、該移動先の空き領域のサブセグメントのサイズを変更してから前記データの移動を行うことを特徴とする請求項３記載のメモリ管理装置。
【請求項６】
メモリ領域を複数のセグメントに分割管理し、更に該各セグメントを複数のサブセグメントに分割管理するメモリ管理装置におけるコンピュータを、
任意のメモリ要求プロセスによって任意の割り当て要求があると、任意の前記セグメントを対象として、
該セグメントが未使用である場合には、前記割り当て要求された領域サイズに基づいて該セグメントにおける前記サブセグメントのサイズを決定して複数のサブセグメントを生成し、１又は複数の該サブセグメントを前記要求に対して割り当てると共に該セグメントを使用中とする第１の領域取得手段と、
前記セグメントが前記使用中である場合には、前記割り当て要求された領域サイズと前
記生成済みのサブセグメントのサイズとに基づいて再分割が必要か否かを判定し、再分割が必要と判定された場合には、該割り当て要求された領域サイズに基づいて該セグメントの空き領域における前記サブセグメントのサイズを再決定して、該空き領域において複数の新たなサブセグメントを生成し、１又は複数の該新たなサブセグメントを前記要求に対して割り当てる第２の領域取得手段、
として機能させる為のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ領域をセグメント単位に分割して管理するメモリ管理方法に関する。
【背景技術】
【０００２】
従来の方法では、メモリ領域は予め指定された容量が静的に確保され、この領域内に点在する未使用領域をメモリ使用プロセスへ提供するのみであり、常時、システムの負荷の高い場合を想定して最大容量にて用意していなければならなかった。
【０００３】
その一つの解決方法として、セグメント割り当て方式がある。この方式は、メモリをセグメントと言う単位で分割管理しておき、メモリ使用プロセスが任意の容量のメモリ領域を要求した時に、管理下の空きセグメントから要求された容量に相当するセグメントを、要求元のメモリ使用プロセスに割り当てるというものである。
【０００４】
セグメント割り当て方式の一例として、特許文献１記載の「メモリバッファ制御方式」がある。図１０を参照してこの特許文献１の方式を簡単に説明する。
図１０に示すように、特許文献１記載の「メモリバッファ制御方式」では、個々のセグメントをさらに分割したバッファエレメントというサブセグメントを定義し、サブセグメント単位で、メモリ使用プロセスに対してメモリを割り当てている。
【０００５】
この方式によれば、まず必要最低限のセグメントを用意しておき、その中からサブセグメント単位で、メモリ使用プロセスに割り当てていく。そして、セグメント内の全てのサブセグメントを割り当て終えたら、新たにセグメントを生成し、その中のサブセグメントをメモリ使用プロセスに割り当てていく。すなわち、セグメントを動的に生成することにより、プロセス割り当て用のメモリ領域を常時確保しておく必要がなくなり、メモリの利用効率が上がる。また、セグメントをサブセグメントに分割して管理することにより、セグメントによるメモリ管理の容易さを維持している。
【特許文献１】特開平７−１３８５３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１の方式では、セグメント内のサブセグメントの領域サイズは固定であり、サブセグメントを割り当ててもらったメモリ使用プロセス（メモリ要求プロセス）が、サブセグメントの領域サイズよりも非常に小さいサイズのメモリ領域しか使用しない場合、割り当てられたサブセグメントの未使用メモリ領域は、他のプロセスからも使用不能であり、メモリの利用効率は低下する。
【０００７】
本発明の課題は、セグメントを更に分割したサブセグメント単位でメモリ使用プロセスに使用領域を割り当てていくメモリ管理方式において、メモリ要求プロセスにより割り当て要求されるメモリサイズに応じて、サブセグメントのサイズを動的に変更することにより、より利用効率の高いメモリ管理が行えるメモリ管理装置、そのプログラム等を提供することにある。
【課題を解決するための手段】
【０００８】
本発明のメモリ管理装置は、メモリ領域を複数のセグメントに分割管理し、更に該各セグメントを複数のサブセグメントに分割管理するメモリ管理装置であって、任意のメモリ要求プロセスによって任意の割り当て要求があると、任意の前記セグメントを対象として、該セグメントが未使用である場合には、前記割り当て要求された領域サイズに基づいて
該セグメントにおける前記サブセグメントのサイズを決定して複数のサブセグメントを生成し、１又は複数の該サブセグメントを前記要求に対して割り当てると共に該セグメントを使用中とする第１の領域取得手段と、前記セグメントが前記使用中である場合には、前記割り当て要求された領域サイズと前記生成済みのサブセグメントのサイズとに基づいて再分割が必要か否かを判定し、再分割が必要と判定された場合には、該割り当て要求された領域サイズに基づいて該セグメントの空き領域における前記サブセグメントのサイズを再決定して、該空き領域において複数の新たなサブセグメントを生成し、１又は複数の該新たなサブセグメントを前記要求に対して割り当てる第２の領域取得手段とを有する。
【０００９】
上記構成のメモリ管理装置では、各セグメント毎に最初は第１の領域取得手段によって、割り当て要求された領域サイズに応じてサブセグメントのサイズを動的に決定する。更に、その後、メモリ要求プロセスがある毎に、第２の領域取得手段が、必要に応じて、空き領域におけるサブセグメントのサイズを変更する。
【００１０】
また、例えば、前記第１の領域取得手段又は前記第２の領域取得手段における前記サブセグメントサイズの決定処理は、予め登録されている複数のサブセグメントサイズのなかから前記割り当て要求された領域サイズとの差が最も小さい割り当て領域を生成できるサブセグメントサイズを選択するものであり、該領域サイズとの差が最も小さいサブセグメントサイズが複数ある場合には、そのなかで最もサイズが大きいものに決定する。
【００１１】
出来るだけメモリ利用効率が高く且つ容易にメモリ管理が行えるようにサブセグメントサイズを決定する。
また、例えば、前記第２の領域取得手段は、前記割り当て要求された領域を前記１又は複数のサブセグメントに割り当てたときに余る領域のサイズが、予め設定される所定値以上である場合に、再分割が必要と判定する。
【００１２】
また、例えば、複数の前記セグメントが前記使用中の状態になったときに、該複数のセグメントの何れかを移動先または移動元として、該移動元のセグメントにおいて前記要求に対して割り当てられた領域のデータを、前記移動先のセグメントの空き領域に移動させる領域最適化手段を更に有する。
【発明の効果】
【００１３】
本発明のメモリ管理装置、そのプログラム等によれば、セグメントを更に分割したサブセグメント単位でメモリ使用プロセスに使用領域を割り当てていくメモリ管理方式において、メモリ要求プロセスにより割り当て要求されるメモリサイズに応じて、サブセグメントのサイズを動的に変更することにより、より利用効率の高いメモリ管理が行えるようになる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照して本発明の実施の形態について説明する。
図１に、本実施の形態に係わるメモリ管理方式が適用される構成（メモリ管理装置という）を示す。
【００１５】
図１に示す本例のメモリ管理装置１は、任意のコンピュータ（パソコン等の汎用コンピュータ、サーバ等）内における任意のメモリ２内の任意のメモリ領域３の管理処理の為の機能／データ構成を示すものである。すなわち、図示のメモリ領域操作処理部１０と、セグメント管理テーブル２０と、サブセグメント管理テーブル３０とで構成される。尚、図示のメモリ要求プロセス９は、何等かの処理実行に伴って生じる一般的なメモリアクセス要求を意味する。
【００１６】
メモリ領域３は、複数のセグメント４（図示の例では１〜ｎのｎ個のセグメント）で構成される。更に個々のセグメント４は、複数個のサブセグメント５で構成される。
メモリ領域操作処理部１０は、領域取得処理部１１と、領域返却処理部１２と、領域最適化処理部１３とで構成される。これら処理部の機能・処理（後述する）は、上記コンピュータの不図示のＣＰＵ／ＭＰＵ等の演算プロセッサが、不図示の記憶装置（ハードディスク等）に記憶されている所定のアプリケーション・プログラムを、読出し・実行することにより実現される。また、上記セグメント管理テーブル２０と、サブセグメント管理テーブル３０も、上記記憶装置等に記憶されている。
【００１７】
図２に、セグメント管理テーブル２０の一例を示す。
図示の例のセグメント管理テーブル２０は、各セグメントを識別するためのセグメントNo.２１と、各セグメントの使用状況を示す状態フラグ２２と、セグメント内に定義されているサブセグメントの個数を示す所有サブセグメント数２３と、このサブセグメントを管理するためのサブセグメント管理テーブル３０へのポインタ２４とで構成される。この他にも必要な要素があれば、セグメント管理テーブル２０に追加しても構わない。
【００１８】
図３に、サブセグメント管理テーブル３０の一例を示す。
図示の例のサブセグメント管理テーブル３０は、各サブセグメントを識別するためのサブセグメントNo.３１と、各サブセグメントの使用状況を示す状態フラグ３２と、各サブセグメントのメモリ領域上における位置を示す割り当てアドレス３３と、各サブセグメントの割り当て領域サイズ３４とで構成される。この他にも必要な要素があれば、サブセグメント管理テーブル３０に追加しても構わない。
【００１９】
図４は、領域取得処理部１１の処理フローチャート図である。
また、図５には、図４の処理によるサブセグメントの割当てとデータ格納の具体的な様子を示す図である。
【００２０】
図４に示す処理は、任意のメモリ要求プロセス９が発生する毎に実行する。対象のセグメントは、任意に（例えばランダムに）決定する。例えば後述する図９（ａ）に示す例においては、セグメント１〜４のなかからランダムに決定する。
【００２１】
まず、上記対象のセグメントの使用状況を状態フラグ２２を参照して確認する（ステップＳ１１）。もし、そのセグメントがまだ未使用の場合（ステップＳ１１，ＹＥＳ）、取得要求された領域サイズ（要求サイズ）からサブセグメントサイズを計算（決定）する（ステップＳ１２）。
【００２２】
サブセグメントサイズの計算（決定）にあたっては、上記メモリ要求プロセス９によって取得要求（割り当て要求）された領域サイズと、計算されたサブセグメントサイズ×ｎ（ｎ＝１〜サブセグメントの最大数）との差が最小となるようなサイズを得ることが望ましい。しかし、システム要件等の利用条件に応じて、サブセグメントの分割サイズを決定する方法を用いても良い。
【００２３】
本実施例では、２のｎ乗（ｎ＝０〜５）の範囲で領域サイズを分割し、その中で、最も取得要求された領域サイズとの差が最小となるようなサブセグメントのサイズを採用する方式として説明する。
【００２４】
すなわち、“分割しない”（２の０乗）、２分割（２の１乗）、２分割（２の２乗）、８分割（２の３乗）、１６分割（２の４乗）、３２分割（２の５乗）の６つのパターンそれぞれにおいて、サブセグメントサイズを求め（あるいは各セグメントサイズが一定であれば予め求めておける）、更に“求めたサブセグメントサイズ×ｎ（ｎ＝１〜サブセグメ
ントの最大数）”を算出して、各算出結果と上記要求サイズとの差を求める（算出結果−要求サイズ）。例えば、８分割（２の３乗）の場合のサブセグメントサイズは、セグメント全体のサイズの８分の１となり、当該求めたサブセグメントサイズに対して１〜８までをそれぞれ乗算して、８つの算出結果を得る。これを他の分割に関しても同様に行う。
【００２５】
そして、全ての計算結果（＝算出結果−要求サイズ）のなかで最も値が小さいもの（但し、正の値に限る。当然のことながら、負の値は対象外）を求め、この値を算出させたサブセグメントサイズが、上記ステップＳ１２で求められるサブセグメントサイズとなる。
【００２６】
もし、取得要求された領域サイズとの差が最小となるようなサブセグメントのサイズが複数ある場合には、最もサイズが大きなものを採用する。例えば、８分割（２の３乗）、１６分割（２の４乗）、３２分割（２の５乗）が上記最小となるものであったならば、８分割のサブセグメントのサイズを採用することになる。この例で、もし３２分割を採用すると、サブセグメントの数が多くなり、セグメントの管理が煩雑になるという弊害がでるからである。
【００２７】
上記セグメントサイズを計算（決定）後、このサイズにてセグメントの領域を分割して複数のサブセグメントを生成し、生成された各サブセグメントに関する情報をサブセグメント管理テーブル３０に登録する（ステップＳ１３）。更に、上記メモリ要求プロセス９により取得要求された領域サイズ分のサブセグメントを、当該メモリ要求処理に割り当てる（ステップＳ１４）。そして、サブセグメント管理テーブル３０及びセグメント管理テーブル２０を更新する（ステップＳ１５）。
【００２８】
すなわち、サブセグメント管理テーブル３０に関しては、上記ステップＳ１４で割り当てたサブセグメントに対応する状態フラグ３２を“使用中”にする。また、セグメント管理テーブル２０に関しては、当該セグメントに対応する状態フラグ２２を“使用中”にすると共に所有サブセグメント数２３に上記生成したサブセグメントの数を記憶する。最後に、割り当てたサブセグメントのアドレスをメモリ要求プロセス９に返し（ステップＳ２５）、当該領域取得処理を終了する。
【００２９】
尚、図示していないが、サブセグメント管理テーブル３０に、更に、各メモリ要求プロセス９にどのサブセグメント割り当てたか（当然、複数のサブセグメントを割り当てる場合もある）を示す情報を記憶してもよい。更に上記要求サイズを記憶してもよい。
【００３０】
上述した処理に関して、例えば、図５に示す任意のセグメントの一例では、まず、図５（ａ）に示す状態では、このセグメントは未使用の状態となっている。つまり、このセグメントの状態フラグ２２は“未使用”であり、当然、所有サブセグメント２３は‘０’の状態となっている。
【００３１】
尚、予め各セグメント毎にサブセグメント管理テーブル３０が作成されている場合には（但し、最初はテーブル３０の雛型の状態；例えば全レコードが図３に示すＮｏ．＝ｍのレコードの状態となっている）、ポインタ２４にはこのセグメントに対応する管理テーブル３０へのポインタ情報が格納されている。但し、この例に限らず、上記ステップＳ１３の処理の際に、このセグメントに対応するサブセグメント管理テーブル３０（その雛型）を作成して任意の記憶領域に格納して、その格納アドレスを上記ポインタ情報としてポインタ２４へ格納するようにしてもよい。
【００３２】
上記図５（ａ）に示す状態のセグメントに関しては、当然、ステップＳ１１の判定はＹＥＳとなり、上記ステップＳ１２〜Ｓ１５の処理が実行されることになる。
ここで、例えば、任意のメモリ要求処理がセグメント全体の大きさの４分の１の領域を
要求した場合（要求サイズ＝セグメントの１／４サイズ）、上記ステップＳ１２の処理により、サブセグメントのサイズをセグメントの４分の１の大きさとする。
【００３３】
これにより、上記ステップＳ１３の処理では、セグメントを４分割することで図５（ｂ）に示すように４つのサブセグメントを生成する。更に、上記の通り、生成された各サブセグメントに関する情報をサブセグメント管理テーブル３０に登録する。すなわち、サブセグメントＮｏ．３１＝‘１’〜‘４’までの４つのレコードについて、これら各レコードの割り当て領域サイズ３４に上記ステップＳ１２で求めたサブセグメントのサイズ（４つとも同じである）を格納すると共に、そのサブセグメントの領域の先頭アドレスを割り当てアドレス３３に格納する。また、ここでは状態フラグ３２は全て“未使用”としておく。
【００３４】
尚、図３に示す例のように割り当て領域サイズ３４が異なるのは（８ＫＢと４ＫＢ）、後述するステップＳ１７，Ｓ１８の処理により、空き領域に関してサブセグメントの再生成を行ったからであり、詳しくは後述する。
【００３５】
そして、ステップＳ１４の処理を行うが、本例では、生成した４つのサブセグメントのうちの１つを、図５（ｂ）に示すように、メモリ要求プロセス９に割り当てることになる。尚、図５（ｂ）〜（ｄ）において、任意のメモリ要求プロセス９により取得要求された領域サイズ（要求サイズ）を、図示の斜線で示すものとする。そしてステップＳ１５において、上記割り当てた１つのサブセグメントに対応する状態フラグ３２を“使用中”へと更新する。更に、テーブル２０において、上記対象のセグメントに対応する状態フラグ２２を“使用中”へと更新すると共に所有サブセグメント数２３に‘４’を格納する。
【００３６】
一方、セグメントが使用中の場合（ステップＳ１１，ＮＯ）（例えば上記図５（ｂ）や後述する図５（ｃ）、（ｄ）に示す状態になっている場合）、まず、今回のメモリ要求プロセス９によって取得要求された領域サイズ（要求サイズ）に対して、現在のサブセグメントのサイズでは半端か否かを判定する（ステップＳ１６）。
【００３７】
半端か否かの判定方法としては、この取得要求に対して上記ステップＳ１４と同様にして１以上の未使用のサブセグメントを割り当て、割り当てたサブセグメントの数をｎとし、上記未使用のサブセグメントのサイズをｐとし、取得要求された領域サイズ（要求サイズ）をｑとした場合に、
ｓ＝ｐ×ｎ−ｑ
を算出し、この算出結果ｓが予め設定される閾値Ｔよりも小さければ半端ではないと判定し（ステップＳ１６，ＮＯ）、ｓが閾値Ｔ以上であれば半端であると判定する（ステップＳ１６，ＹＥＳ）。つまり、割り当てられる領域の大きさ（ｐ×ｎ）と取得要求された領域サイズｑとの差、すなわち“余る領域”の大きさが、ある程度以上（閾値Ｔ以上）大きい場合には、サブセグメントサイズを計算し直す必要があると判定し、ステップＳ１７、Ｓ１８の処理を実行するようにする。
【００３８】
これより、もし、半端ではないと判定された場合には（ステップＳ１６，ＮＯ）、上記ステップＳ１４、Ｓ１５の処理と同様に、１又は複数の未使用サブセグメントを割り当てる処理（ステップＳ１９）、及びサブセグメント管理テーブル３０を更新する処理（割り当てたサブセグメントに対応する状態フラグ３２を“使用中”にする処理）（ステップＳ２１）を実行する。但し、空き領域が足りない場合、すなわちこのセグメントの空き領域が取得要求された領域サイズｑよりも小さい場合には（ステップＳ２０，ＹＥＳ）、新たなセグメントを生成し（ステップＳ２２）、当該新たなセグメントを対象として、ステップＳ１２に移り、ステップＳ１２〜Ｓ１５（及びＳ２５）の処理を実行することになる。
【００３９】
ステップＳ２１を実行後、割り当てたサブセグメントのアドレスをメモリ要求プロセス９に返し（ステップＳ２４）、本処理は終了する。
例えば図５に示す例では、図５（ｂ）に示す状態において、任意のメモリ要求プロセス９が、セグメント全体のサイズの４分の２よりもやや小さい領域を要求したことから、ステップＳ１６の判定はＮＯとなったものとし、サブセグメントのサイズを更新せず、図５（ｃ）に示すように、２つのサブセグメントを割り当てる。そして、これら２つのサブセグメントに対応する状態フラグ３２をそれぞれ“使用中”にする。
【００４０】
また、図５（ｂ）に示す状態において、もし、取得要求された領域サイズが、セグメント全体のサイズの４分の３よりも大きい場合には、ステップＳ２０の判定がＮＯとなり、新たなセグメントを生成することになる。
【００４１】
また、図５（ｂ）に示す状態において、例えば、任意のメモリ要求プロセス９が、サブセグメント２．５個分の領域を要求した場合、３つのサブセグメントが必要となるが、およそサブセグメント０．５個分の空き容量が生じてしまう。この空き容量分の領域は割り当てることはできないので、無駄が生じてしまう。上記ステップＳ１６の処理は、例えばこの様な状況においては“半端である”（ステップＳ１６，ＹＥＳ）と判定されるような処理とするものである。
【００４２】
これより、ステップＳ１７，Ｓ１８の処理を実行することで、例えば図５（ｄ）に示す例では、ステップＳ１７で求めた新たなサブセグメントサイズは、セグメント全体の８分の1の大きさになっており、このサブセグメントサイズによって空き領域を分割することで、図示の通り、空き領域は６分割されることになる。そして、当該再生成された６つの未使用のサブセグメントのうちの５つを、当該メモリ要求処理に割り当てる。これにより、残った１つのサブセグメント（セグメント全体のサイズの８分の１の大きさのサブセグメント）を、次回以降のメモリ要求処理に対して割り当てることが可能となり、使用されない無駄な領域とならずに済む。
【００４３】
尚、上記空き領域とは、セグメント全体の領域のうち、状態フラグ３２が“使用中”となっているサブセグメントが占める領域以外の領域全てを意味する。換言すれば、状態フラグ３２が“未使用”となっている全てのサブセグメントによって占められる領域を意味する。
【００４４】
以下、上記ステップＳ１７，Ｓ１８の処理について説明する。
すなわち、半端であると判定された場合（ステップＳ１６，ＹＥＳ）、まず、上記ステップＳ１２と同様に、取得要求された領域サイズに基づきサブセグメントサイズを計算（決定）する（ステップＳ１７）。そして、計算（決定）したセグメントサイズに基づき未使用のサブセグメント領域（上記空き領域）を分割することで、空き領域におけるサブセグメントの再生成が行われることになる。そして、再生成されたサブセグメントに関する情報をサブセグメント管理テーブル３０に登録する（ステップＳ１８）。
【００４５】
このサブセグメント管理テーブル３０の更新処理は、例えば、まず、既存のレコードのうち状態フラグ３２が“未使用”となっているレコードは全て削除したうえで、上記再生成したサブセグメントの数の分だけ新規レコードを追加して、各新規レコード毎にそのサブセグメントに関する情報を格納する処理である。すなわち、割り当てアドレス３３、割り当て領域サイズ３４を格納すると共に、状態フラグ３２は一律“未使用”とする処理である。
【００４６】
例えば上記図５（ｄ）の例では、まず、既存の４つのサブセグメントのレコードのうち未使用の３つを削除し、６つの新規レコードを追加して各レコードに上記再生成したサブ
セグメントに関する情報（サイズ、アドレス等）を格納する。よって、レコード数は‘７’となっている。
【００４７】
上述したように、本実施例では、セグメントから領域を取得する際に、その空き領域のサブセグメントのサイズを変更することにより、セグメントの空き領域を増やすことが可能となる。
【００４８】
次に、以下、図６、図７を参照して、領域返却処理について説明する。
図６は、領域返却処理の処理フローチャート図である。図６の処理は、領域返却処理部１２が実行する。
【００４９】
図７は、任意のメモリ要求プロセス９に対して割り当てられた領域を、図６の処理によって返却していく様子の一例を示す図である。
図６の処理は、上記図４の処理により割り当てられた領域のうちの任意の領域の返却要求がある毎に実行される。
【００５０】
図６に示すように、まず、返却要求された領域のサブセグメントが複数ある場合には、これら複数のサブセグメントを一つのサブセグメントにまとめ（ステップＳ３１）、サブセグメント管理テーブル３０を更新する（ステップＳ３２）。すなわち、サブセグメント管理テーブル３０において、返却要求された領域の複数のサブセグメントのレコードのうち最も先頭の（割り当てアドレスが若い）レコードの状態フラグ３２を“未使用”とすると共に、その割り当て領域サイズ３４を上記複数のサブセグメント全てを合計したサイズへと更新する。他のサブセグメントのレコードに関しては、例えば、雛型のときの状態、つまり図３に示すＮｏ．３１＝‘ｍ’のレコードと同じ状態にする。すなわち、その状態フラグ３２を“なし”にして、割り当てアドレス３３を“null”、割り当て領域サイズ３４を“０ＫＢ”にする。あるいは、他のサブセグメントのレコードは全て削除してもよい。
【００５１】
尚、上記ステップＳ３１、Ｓ３２の処理は必ずしも実行しなくてもよい（１つにまとめなくてもよい）。但し、１つにまとめることで、次に領域を割り当てる際の処理を簡単にすることができる。つまり、１つにまとめずにそのまま残しておくと、結局、次に領域を割り当てる際に、要求された領域サイズと空きサブセグメントサイズを比較することになる。このとき、空き領域が１つにまとまっていないと、１つのサブセグメントでは足りなければ次のサブセグメントと連結し、それでも足りなければまた次のサブセグメントと連結して・・・、というように、領域取得処理が煩雑になる。よって、上記の通り、領域返却時に、使用されていたサブセグメントを１つのサブセグメントにまとめる処理を行っておいたほうがよい。
【００５２】
ステップＳ３２の処理後のサブセグメント管理テーブル３０を参照して、このセグメント中に現在使用中のサブセグメントが存在しない場合には（ステップＳ３３，ＹＥＳ）、当該セグメントを解放し（ステップＳ３４）、セグメント管理テーブル２０を更新する（ステップＳ３５）（所有サブセグメント数２３を‘０’にすると共に、状態フラグ２２を“未使用”にする）。
【００５３】
このセグメント中に未だ使用中のサブセグメントが存在する場合には（ステップＳ３３，ＮＯ）、セグメントの解放は行わず、処理を終了する。
図７（ａ）には、図５（ｄ）と同じ状態を示してある。すなわち、セグメント中の２つの領域（図示の領域Ａ、領域Ｂ）が、各メモリ要求プロセス９に割り当てられているものとする。
【００５４】
この状態でまず割り当て領域Ｂの返却要求があったとすると、上記図６の領域返却処理により、領域Ｂが返却される。この際、割り当て領域Bに対応する複数の（ここでは５つの）サブセグメントは、図７（ｂ）に示すように、１つの空きサブセグメントとしてまとめられる。
【００５５】
続いて、割り当て領域Ａの返却要求があったとすると、上記図６の領域返却処理により、図７（ｃ）に示すように、領域Ａが返却される。図示の通り、このとき、セグメント内の全てのサブセグメントが空き状態（未使用）になる。
【００５６】
よって、ステップＳ３３の判定がＹＥＳとなり、ステップＳ３４、Ｓ３５の処理が実行されることになる。これにより、図７（ｄ）に示すように、セグメント内の全てのサブセグメントが削除され、サブセグメント管理テーブル３０を更新した後、セグメントそのものを解放することになる。
【００５７】
次に、以下、領域最適化処理部１３による領域最適化処理について説明する。
領域最適化処理は、例えば図９（ａ）に示すように複数のセグメントの個々の割り当て領域を、図９（ｂ）に示すように１つのセグメントにまとめる処理である。ここでは、特に、個々の割り当て領域のサブセグメントのサイズを変更せずに、セグメント間で領域を（そのデータを）移動させる例を説明する。
【００５８】
メモリ領域の最適化にあたって、セグメント間の領域移動の規則として、ここでは、セグメントの半分以上の領域を使用しているセグメントに関しては、その割り当て領域は、他のセグメントに移動しない事とする。従って、移動の対象となる領域は、セグメントの半分未満の領域を使用しているセグメントの領域である。なお、この領域移動に関する規則は、利用条件に応じて決定して良い（上記“半分以上”は、単なる一例に過ぎない）。
【００５９】
図８に、領域最適化処理のフローチャート図を示す。
以下、図８に示す処理について、図９に示す具体例も参照しながら説明する。
図８の処理は各セグメントをそれぞれ処理対象として処理実行し、全てのセグメントについて処理実行完了したら（ステップＳ４１，ＹＥＳ）終了する。
【００６０】
未だ全てのセグメントを処理対象としていない場合（ステップＳ４１，ＮＯ）、未処理の任意のセグメントについてステップＳ４２以降の処理を実行する。
まず、上述した一例の規則に従って、当該処理対象のセグメント中の全ての割り当て領域の合計サイズが、当該セグメント全体のサイズの半分以下か否かを判定し（ステップＳ４２）、半分以下ではない場合には（ステップＳ４２，ＮＯ）、当該セグメントを領域移動先セグメントの候補としてマークしておく（ステップＳ４３）。そして、ステップＳ４１に戻る。
【００６１】
一方、処理対象のセグメント中の全ての割り当て領域の合計サイズが、当該セグメント全体のサイズの半分以下である場合には（ステップＳ４２，ＹＥＳ）、ステップＳ４４以降の処理に進む。
【００６２】
尚、最初に全てのセグメントについてステップＳ４２，Ｓ４３の処理を実行して領域移動先セグメントの候補を求めておき、その後に、この候補以外のセグメントをステップＳ４４以降の処理の処理対象とするようにしてもよい。更に未使用のサブセグメントは最初から処理対象から除外するようにしてもよい。
【００６３】
例えば図９（ａ）に示す例では、まず、図示のセグメント１〜４の各々の状態フラグ２２を参照して、セグメント４のみは“未使用”であるので、処理対象から除外する。そし
て、処理対象のセグメント１〜３の各々について、そのサブセグメントのうち状態フラグ３２が“使用中”のものの割り当て領域サイズ３４の合計を算出し、この合計値がセグメント全体の領域サイズの半分未満か否かを判定する。
【００６４】
半分未満であるセグメントの割り当て領域が、領域移動の対象となる。移動先は、半分未満ではないセグメント（領域移動先セグメントという）となる。尚、上記候補が複数ある場合には、そのうちの１つを最初の領域移動先セグメントとし、全ての“領域移動の対象”をこの領域移動先セグメントに移せない場合には、他の候補を新たな領域移動先セグメントとして使用する。
【００６５】
図９（ａ）に示す例では、まず、セグメント１は、各サブセグメントサイズがセグメント全体の８分の１であり（８分割）、そのうちの５つのサブセグメントを使用している。よって、セグメント１では、半分以上のサブセグメントが使用されているので、領域移動先セグメントの候補となる。
【００６６】
尚、この例では、各セグメント内の全てのサブセグメントのサイズが同じであるので、上記の通り、全サブセグメント数と使用中のサブセグメント数とにより領域移動の対象となるか否かを判定できるが、この例に限るものではないので（例えば上記図５（ｄ）の状態）、上記の通り領域サイズ３４の合計を算出する方法が望ましいが、ここでは等分割された例であるので、上記のようにサブセグメントの数により判定を行うものとする。
【００６７】
これより、図９（ａ）に示す例では、セグメント２は、セグメント全体を８分割して８つのサブセグメントがあり、そのうちの１つのサブセグメントのみを使用している。よって、領域移動の対象となる。同様に、セグメント３は、セグメント全体を４分割して４つのサブセグメントがあり、そのうちの１つのサブセグメントのみを使用している。よって、領域移動の対象となる。
【００６８】
以上のことから、候補は１つであるのでセグメント１が領域移動先セグメントとなり、セグメント２，３の割り当て領域を、セグメント１へ移動させることになる。
よって、セグメント２，３のそれぞれを処理対象として、ステップＳ４４以降の処理が行われる。
【００６９】
ステップＳ４４以降の処理では、まず、上記領域移動先セグメントに関してその空き領域サイズを検索する（ステップＳ４４）。すなわち、領域移動先セグメントに係るサブセグメント管理テーブル３０を参照して、その状態フラグ３２が“未使用”となっているサブセグメントを全て求め、更にその中でレコードが連続しているサブセグメントはまとめて１つの空き領域と見做し、連続していないサブセグメントはこの１つのサブセグメントを１つの空き領域として、それぞれの空き領域のサイズを求める。
【００７０】
例えば、上記図９（ａ）の例ではセグメント１が領域移動先セグメントであるので、その先頭と２番目、及び最後の３つのサブセグメントが未使用であり、そのうち先頭と２番目のサブセグメントは連続しているのでまとめて１つの空き領域と見做すと、仮に図示の８分割のサブセグメントのサイズが４ＫＢであるとすると、この空き領域のサイズは８ＫＢ（４ＫＢ×２）となる。最後のサブセグメントは、これ１つで１つの空き領域となり、その空き領域サイズは当然４ＫＢとなる。
【００７１】
次に当該処理対象のセグメント（領域移動の対象となるセグメント）における移動元領域のサイズと、領域移動先セグメントにおける上記各空き領域サイズとの差を求め、この“差”が最も小さい空き領域を、移動先領域とする（ステップＳ４５）。
【００７２】
図９（ａ）に示す例においてセグメント２が処理対象である場合には、その移動元領域のサイズは図示の通り８分割のサブセグメントサイズ（４ＫＢ）であるので、上記セグメント１の最後のサブセグメントが、移動先領域となる。また、セグメント３が処理対象である場合には、その移動元領域のサイズは図示の通り４分割のサブセグメントサイズ（８ＫＢ）となるので、上記セグメント１の先頭と２番目のサブセグメントをまとめた空き領域が、移動先領域となる。
【００７３】
続いて、上記移動先領域のサブセグメントのサイズと上記移動元領域のサブセグメントのサイズとが同一であるか否かを判定し（ステップＳ４６）、同一である場合には（ステップＳ４６，ＮＯ）、そのまま、上記移動元領域のデータを上記移動先領域に移動させる（ステップＳ４８）。一方、同一ではない場合には（ステップＳ４６，ＹＥＳ）、上記移動元領域のサブセグメントサイズで上記移動先領域の再分割を行った後（ステップＳ４７）、上記移動元領域のデータを上記移動先領域に移動させる（ステップＳ４８）。
【００７４】
図９（ａ）に示す例では、セグメント１及びセグメント２のサブセグメントは、全て、８分割のサブセグメント（４ＫＢ）であり、セグメント３のサブセグメントは全て４分割のサブセグメント（８ＢＫ）であるので、セグメント２に関してはステップＳ４６はＮＯとなり、図９（ｂ）に示すように、セグメント１の移動先領域をそのままの状態で、セグメント２の移動元領域のデータを移動させる。
【００７５】
一方、セグメント３に関してはステップＳ４６はＹＥＳとなるので、ステップＳ４７の処理が行われる。尚、ステップＳ４７の処理は、上記ステップＳ１７，Ｓ１８等の処理と略同様であってよい。本例では、上記セグメント１の先頭と２番目のサブセグメントから成る移動先領域は、図９（ｂ）に示すように１つの（４分の１の）サブセグメントとなり、この移動先領域に図示の通りセグメント３の移動元領域のデータを移動させる。
【００７６】
尚、上記ステップＳ４６，Ｓ４７の処理は、必ずしも行わなくても良い。すなわち、上記セグメント３の例において、セグメント１の移動先領域のサブセグメントを８分の１のサイズのままでセグメント３の移動元領域のデータを移動させることもできる。
【００７７】
しかしながら、サブセグメントの管理上、サブセグメント管理テーブル３０の登録件数を減らすことで、処理の煩雑さを減らすことができるので、その意味では上記ステップＳ４６，Ｓ４７の処理を行うことが望ましい。
【００７８】
以上説明したように、本手法では、メモリ領域をセグメント単位に分割して管理するメモリ管理方法において、メモリ使用プロセスにより要求されたメモリサイズに応じてサブセグメントのサイズを動的に変更することが可能となり、メモリ利用効率が向上する。
【図面の簡単な説明】
【００７９】
【図１】本例のメモリ管理方式が適用される構成（メモリ管理装置）を示す図である。
【図２】セグメント管理テーブルの一例を示す図である。
【図３】サブセグメント管理テーブルの一例を示す図である。
【図４】領域取得処理部の処理フローチャート図である。
【図５】（ａ）〜（ｄ）は任意のセグメントに対する領域分割とメモリ割り当ての一例を示す図である。
【図６】領域返却処理の処理フローチャート図である。
【図７】メモリ要求処理が割り当てられた領域を返却していく様子の一例を示す図である。
【図８】領域最適化処理のフローチャート図である。
【図９】（ａ）、（ｂ）は図８の処理によるデータ移動の具体例を示す図である。
【図１０】従来のメモリバッファ制御方式を説明する為の図である。
【符号の説明】
【００８０】
１  メモリ管理装置
２  メモリ
３  メモリ領域
４  セグメント
５  サブセグメント
９  メモリ要求プロセス
１０  メモリ領域操作処理部
１１  領域取得処理部
１２  領域返却処理部
１３  領域最適化処理部
２０  セグメント管理テーブル
２１  セグメントNo.
２２  状態フラグ
２３  所有サブセグメント数
２４  サブセグメント管理テーブルへのポインタ
３０  サブセグメント管理テーブル
３１  サブセグメントNo.
３２  状態フラグ
３３  割り当てアドレス
３４  割り当て領域サイズ
【図１】
2009129187.tif 000003
【図２】
2009129187.tif 000004
【図３】
2009129187.tif 000005
【図４】
2009129187.tif 000006
【図５】
2009129187.tif 000007
【図６】
2009129187.tif 000008
【図７】
2009129187.tif 000009
【図８】
2009129187.tif 000010
【図９】
2009129187.tif 000011
【図１０】
2009129187.tif 000012