(57)【要約】【課題】メモリの管理を、ビットマップを使って行う処理において、メモリ不足、つまり、システムリソースの負荷の軽減を図る。【解決手段】最大連続空き領域長管理部１３は必要ビットマップ領域サイズをビットマップ領域１０１内の最大連続空き領域長と比べて、必要ビットマップ数分連続した空きの有無を調べる。ビットマップ内に必要な空きがある場合、空きビットマップ検索部１４は、ビット単位ビットマップ検索部１５を用いてビットマップ領域１０１の検索を行う。メモリ確保部１１は、必要な連続空きビットマップを見つけたら、確保候補場所領域管理部１６に連続空き領域長とその場所を通知し、メモリ確保に必要な連続空き領域が複数見つかった場合は、既に見つかっている場所の連続空き領域長と２個目以降で見つけた連続空き領域長を比べて、小さい方を確保場所領域管理部１６の内容と置き換える。【選択図】図１
2007264692.tif 000002
【特許請求の範囲】
【請求項１】
メモリ確保手段と、割り当てメモリアドレス算出手段と、必要ビットマップ領域数計算手段と、最大連続空き領域長管理手段と、空きビットマップ検索手段と、ビットマップ検索位置通知手段と、ビットマップ確保手段と、ビット単位ビットマップ検索手段と、確保候補場所領域管理手段とを有するメモリ管理装置を用いて、ビットマップ領域と割り当て領域を有するメモリを管理する方法であって、
前記メモリ確保手段が、メモリ確保要求を受けて要求メモリサイズを必要ビットマップ領域数計算手段に通知するステップと、
前記必要ビットマップ領域数計算手段が、前記要求メモリサイズを管理するために必要なビットマップ領域サイズを求め、その値を前記メモリ確保手段に返却するステップと、
前記最大連続空き領域長管理手段が、前記メモリ確保手段から通知された必要ビットマップ領域サイズを前記ビットマップ領域内の最大連続空き領域長と比べて、前記必要ビットマップ領域サイズ分連続した空きの有無を前記メモリ確保手段に通知するステップと、
前記必要ビットマップ領域サイズ分連続した空きがある場合、前記メモリ確保手段からの通知を受けて、前記空きビットマップ検索手段が、前記ビット単位ビットマップ検索手段を用いて前記ビットマップ検索位置通知手段から通知された検索位置から前記ビットマップ領域の検索を行い、必要な連続空きビットマップを見つけたら、前記メモリ確保手段に、その連続空き領域サイズと場所を通知するステップと
前記メモリ確保手段が、前記ビットマップ領域の検索が完了した地点で、確保に必要な連続空きビットマップが前記ビットマップ領域内で１つの場合、その連続空き領域サイズとその場所を、複数の場合、最小の連続空き領域長とその場所を前記確保候補場所領域管理手段に通知するステップと、
前記メモリ確保手段が、前記確保候補場所領域管理手段が記憶している場所を前記ビットマップ確保手段に通知するステップと、
前記ビットマップ確保手段が、前記ビットマップ領域の通知された場所の確保を行うと共に、前記割り当てメモリアドレス算出手段に対して新たに確保した前記ビットマップ領域の位置を通知するステップと、
前記割り当てメモリアドレス算出手段が、通知されたビットマップ領域の位置から割り当てメモリアドレスの算出を行い、メモリ要求者に対して割り当てアドレスを返却するステップと、
を有し、
前記必要ビットマップ領域サイズ分連続して空きがない場合、他のメモリを対象として前記最大連続空き領域長管理手段が行うステップから処理を繰り返す、
メモリ管理方法。
【請求項２】
前記空きビットマップ検索手段が前記ビットマップ領域の検索を行う際、前記必要なビットマップ領域サイズが１ワードを越える場合、ワード単位ビットマップ検索手段を用いて必要領域サイズのワード数分だけワード単位に空きを検索し、余った分、または１ワード以下の場合、バイト単位ビットマップ検索手段を用いてバイト単位に空きを検索し、最後に余った分について前記ビット単位ビットマップ検索手段を用いてビット単位に空きを検索する、請求項１に記載のメモリ管理方法。
【請求項３】
ビットマップ領域と割り当て領域を有するメモリを管理する装置であって、
要求メモリサイズを管理するために必要なビットマップ領域サイズを求める必要ビットマップ領域数計算手段と、
前記必要ビットマップ領域サイズをビットマップ領域内の最大連続空き領域長と比べて、前記必要ビットマップ領域サイズ分連続した空きの有無を通知する最大連続空き領域長管理手段と、
前記ビットマップ領域の検索位置を通知するビットマップ検索位置通知手段と、
前記必要ビットマップ領域サイズ分連続した空きがある場合、ビット単位ビットマップ検索手段を用いて前記ビットマップ検索位置通知手段から通知された検索位置から前記ビットマップ領域の検索を行い、必要な連続空きビットマップを見つけたら、その連続空き領域サイズと場所を通知する前記空きビットマップ検索手段と
確保候補場所領域管理手段と、
メモリ確保要求を受けて要求メモリサイズを前記必要ビットマップ領域数計算手段に通知し、前記必要ビットマップ領域サイズを前記最大連続空き領域長管理手段に通知し、前記空きビットマップ検索手段からの通知を受け、ビットマップ領域の検索が完了した地点で、確保に必要な連続空きビットマップが同じビットマップ領域内で１つの場合、その連続空き領域サイズとその場所を、複数の場合、最小の連続空き領域長とその場所を前記確保候補場所領域管理手段に通知するメモリ確保手段と、
前記メモリ確保手段からの通知された場所のビットマップの確保を行うと共に、新たに確保したビットマップ領域の位置を通知するビットマップ確保手段と、
前記ビットマップ確保手段から通知されたビットマップ領域の位置から割り当てメモリアドレスの算出を行い、メモリ要求者に対して割り当てアドレスを返却する割り当てメモリアドレス算出手段と、
を有するメモリ管理装置。
【請求項４】
ワード単位ビットマップ検索手段とバイト単位ビットマップ検索手段をさらに有し、前記空きビットマップ検索手段は、前記ビットマップ領域の検索を行う際、必要なビットマップ領域サイズが１ワードを越える場合、前記ワード単位ビットマップ検索手段を用いて必要領域サイズのワード数分だけワード単位に空きを検索し、余った分、または１ワード以下の場合、前記バイト単位ビットマップ検索手段を用いてバイト単位に空きを検索し、最後に余った分について前記ビット単位ビットマップ検索手段を用いてビット単位に空きを検索する、請求項３に記載のメモリ管理装置。
【請求項５】
コンピュータを、請求項３または４に記載のメモリ管理装置として実行させるためのメモリ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットマップを使用してメモリ管理を行う方法に関する。
【背景技術】
【０００２】
特許文献１は、空きメモリ確保時にメモリを管理するビットマップを検索する場合、必要なビットマップ領域数に応じてワード単位またはビット単位を切り替えることにより、１ワード以上のビットマップ領域を確保する場合の検索処理の高速化を実現している。
【特許文献１】特開２０００−３１１１１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上述した従来の方法は、最初に見つけた空き領域に無条件に確保してしまうため、不用意に大きな領域を細切れで使用してしまい、その結果、メモリの断片化が発生し、空き領域の合計は十分な量があるのに、メモリの確保ができない状態となり、メモリ不足が発生してしまう、という問題があった。
【０００４】
本発明の目的は、メモリの断片化を防ぐことにより、使用メモリの削減を実現するメモリ管理方法、装置、およびプログラムを提供することにある。
【課題を解決するための手段】
【０００５】
本発明のメモリ管理方法は、メモリ確保手段と、割り当てメモリアドレス算出手段と、必要ビットマップ領域数計算手段と、最大連続空き領域長管理手段と、空きビットマップ検索手段と、ビットマップ検索位置通知手段と、ビットマップ確保手段と、ビット単位ビットマップ検索手段と、確保候補場所領域管理手段とを有するメモリ管理装置を用いて、ビットマップ領域と割り当て領域を有するメモリを管理する方法であって、
メモリ確保手段が、メモリ確保要求を受けて要求メモリサイズを必要ビットマップ領域数計算手段に通知するステップと、
必要ビットマップ領域数計算手段が、要求メモリサイズを管理するために必要なビットマップ領域サイズを求め、その値をメモリ確保手段に返却するステップと、
最大連続空き領域長管理手段が、メモリ確保手段から通知された必要ビットマップ領域サイズを前記ビットマップ領域内の最大連続空き領域長と比べて、必要ビットマップ領域サイズ分連続した空きの有無をメモリ確保手段に通知するステップと、
必要ビットマップ領域サイズ分連続した空きがある場合、メモリ確保手段からの通知を受けて、空きビットマップ検索手段が、ビット単位ビットマップ検索手段を用いて前記ビットマップ検索位置通知手段から通知された検索位置からビットマップ領域の検索を行い、必要な連続空きビットマップを見つけたら、メモリ確保手段に、その連続空き領域サイズと場所を通知するステップと
メモリ確保手段が、ビットマップ領域の検索が完了した地点で、確保に必要な連続空きビットマップが前記ビットマップ領域内で１つの場合、その連続空き領域サイズとその場所を、複数の場合、最小の連続空き領域長とその場所を前記確保候補場所領域管理手段に通知するステップと、
メモリ確保手段が、確保候補場所領域管理手段が記憶している場所をビットマップ確保手段に通知するステップと、
ビットマップ確保手段が、ビットマップ領域の通知された場所の確保を行うと共に、割り当てメモリアドレス算出手段に対して新たに確保したビットマップ領域の位置を通知するステップと、
割り当てメモリアドレス算出手段が、通知されたビットマップ領域の位置から割り当てメモリアドレスの算出を行い、メモリ要求者に対して割り当てアドレスを返却するステップと、
を有し、
必要ビットマップ領域サイズ分連続して空きがない場合、他のメモリを対象として前記最大連続空き領域長管理手段が行うステップから処理を繰り返す。
【０００６】
本発明は、メモリの管理を、ビットマップを使って行う処理において、確保に必要な連続空き領域のうち一番小さい領域を確保し、大きいサイズの連続空き領域をなるべく残すことにより、メモリ不足、つまり、システムリソースの負荷軽減を図るものである。
【発明の効果】
【０００７】
本発明によれば、確保に必要な連続空き領域のうち一番小さい領域を使用し、大きいサイズの連続空き領域をなるべく残すことにより、メモリの断片化によるメモリ不足を解消し、システムリソースの負荷軽減を図ることができる。
【発明を実施するための最良の形態】
【０００８】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【０００９】
図１を参照すると、本発明のメモリ管理装置は、ビットマップ領域１０１と割り当て領域１０２を有するメモリ１００を管理するもので、メモリ管理部１１と必要ビットマップ領域数計算部１２と最大連続空き領域長管理部１３と空きビットマップ検索部１４とビット単位ビットマップ検索部１５と確保候補場所領域管理部１６とビットマップ確保部１７とビットマップ検索位置通知部１８と割り当てメモリアドレス算出部１９とを有している。
【００１０】
必要ビットマップ領域数計算部１２は要求メモリサイズを管理するために必要なビットマップ領域サイズを求める。最大連続空き領域長管理部１３は必要ビットマップ領域サイズをビットマップ領域１０１内の最大連続空き領域長と比べて、必要ビットマップ領域サイズ分連続した空きの有無をメモリ管理部１１に通知する。空きビットマップ検索部１４はメモリ確保部１１からの通知を受けて、必要ビットマップ領域サイズ分連続した空きがある場合、ビット単位ビットマップ検索部１５を用いて、ビットマップ検索位置通知部１８から通知されたビットマップ検索位置からビットマップ領域１０１の検索を行い、必要な連続空きビットマップを見つけたら、その連続空き領域サイズと場所をメモリ管理部１１に通知する。メモリ管理部１１は、メモリ確保要求を受けて要求メモリサイズを必要ビットマップ領域数計算部１２に通知し、必要ビットマップ領域数計算部１２で算出された必要ビットマップ領域サイズを最大連続空き領域長管理部１３に通知し、空きビットマップ検索部１４からの通知を受け、ビットマップ領域１０１の検索が完了した地点で、確保に必要な連続空きビットマップがビットマップ領域１０１内で１つの場合、その連続空き領域サイズとその場所を、複数の場合、最小の連続空き領域長とその場所を確保候補場所領域管理手段１６に通知する。ビットマップ確保部１７はビットマップ領域１０１の、メモリ確保部１１からの通知された場所の確保を行うと共に、新たに確保したビットマップの位置を割り当てメモリアドレス算出部１９に通知する。割り当てメモリアドレス算出部１９はビットマップ確保部１７から通知されたビットマップの位置から割り当てメモリアドレスの算出を行い、メモリ要求者に対して割り当てアドレスを返却する。
【００１１】
次に、本実施形態のメモリ管理装置の動作について図２を参照して説明する。
【００１２】
メモリ確保部１１は、メモリ確保要求を受けて要求メモリサイズを必要ビットマップ領域数計算部１２に通知する（ステップ２０１）。必要ビットマップ領域数計算部１２は、要求メモリサイズを管理するために必要なビットマップ領域サイズを、要求メモリサイズをビットマップ領域１０１の１ビット当たりのメモリサイズで割ることにより求め、その値をメモリ確保部１１に返却する（ステップ２０２）。最大連続空き領域長管理部１３はメモリ確保部１１から通知された必要ビットマップ領域サイズをビットマップ領域１０１内の最大連続空き領域長と比べて、必要ビットマップ数分連続した空きの有無をメモリ確保部１１に通知する（ステップ２０３）。メモリ確保部１１は、ビットマップ領域１０１内に必要な空きがなければ、他のメモリ領域を検索対象とし（ステップ２０４）、空きがある場合、空きビットマップ検索部１４は、メモリ確保部１１からの通知を受けて、ビット単位ビットマップ検索部１５を用いて、ビットマップ検索位置通知部１８から通知された検索位置からビットマップ領域１０１の検索を行う（ステップ２０５）。
【００１３】
メモリ確保部１１は、必要な連続空きビットマップを見つけたら、確保候補場所領域長管理部１６に連続空き領域長とその場所を通知し、他に候補がないかどうか空きビットマップ検索部１４によってビットマップ領域１０１内をさらに検索する（ステップ２０６〜２０９）。メモリ確保部１１はメモリ確保に必要な連続空き領域が複数見つかった場合は、既に見つかっている場所の連続空き領域長と２個目以降で見つけた連続空き領域長を比べて、小さい方を確保場所領域管理部１６の内容と置き換える（ステップ２１０、２１１）。
【００１４】
ビットマップ領域１０１内を全て検索した結果、メモリ確保部１１は、確保場所領域長管理部１６に記憶されているビットマップ領域１０１の位置をビットマップ確保部１７に通知し、ビットマップ確保部１７は通知された位置のビットマップを確保すると共に、割り当てメモリアドレス算出部１８に対して新たに確保したビットマップ領域１０１の位置を通知する（ステップ２１２、２１３）。割り当てメモリアドレス算出部１９は、通知されたビットマップ領域１０１の位置から割り当てメモリアドレスの算出を、該位置が示すビット数に１ビット当たりのビット数を乗算することで行い（ステップ２１４）、メモリ要求者に対して割り当てアドレスを返却する（ステップ２１５）。
【００１５】
次に、本実施形態の具体例について図３を参照して詳細に説明する。
【００１６】
図３に示すように、メモリ１００はビットマップ領域１０１と割り当て用領域１０２とから構成され、ビットマップ領域１０１の空き領域が、ビットマップＡ１、Ａ２、Ａ３、Ｂ、Ｃとなっている場合に、ビットマップが６バイト必要なメモリ要求がされたものとする。
【００１７】
メモリ確保部１１はメモリ確保の要求を受けると、要求されたサイズのメモリを管理するのに必要なビットマップの領域数を求めるため、必要ビットマップ領域数計算部１２を使用する。この場合は、必要なビットマップの領域数が６．５バイト（５２ビット）だったとする。メモリ確保部１１は、最大連続空き領域長と先に求めた６．５バイトを比較する。今回の場合は、最大連続空き領域長のほうが大きいためビットマップ領域１０１でメモリの確保が行えると判断し処理を続行する。ビットマップ１０１でメモリを確保できると判断したメモリ確保部１１は、空きビットマップ検索部１４を通じて空きビットマップ領域１０１の検索を行う。空きビットマップ検索部１４は、まず、必要ビットマップ領域数をビット単位ビットマップ検索部１５に通知する。ビット単位ビットマップ検索部１５は、Ａ１から始まる領域を見つけ、確保に必要な領域を見つけたと判断し、さらにその後ろの空き領域長をそのまま調査し、確保候補場所領域管理部１６にＡ１の場所および、Ａ１、Ａ２、Ａ３の連続空き領域長（１２バイト）を保存する。その後、さらに検索していない後ろのビットマップ領域１０１を検索し、領域Ｂを見つけ、上記と同様な処理を行い、確保可能と判断する。その際、先に見つけた候補場所の連続空き領域長と比べて、今回見つけた方が短い（８バイト）ため、確保候補場所領域管理部１６には、Ｂを記憶する。その結果、図に示す網掛けの部分が連続した６．５バイトの空きと判断され、ビットマップ確保部１７に通知される。ビットマップ確保部１７は、先に見つけた６．５バイトの空きを使用中に変更する（０００００００００００００→１１１１１１１１１１１１１）。ビットマップ確保部１７からビットマップの位置を受け取った割り当てメモリアドレス算出部１９は、割り当てる実メモリアドレスをビットマップの位置から算出し、メモリ確保要求者に求めたアドレスを返却する。
【００１８】
このように、不用意に大きいサイズの空き領域（Ａ１、Ａ２、Ａ３）を使用せず、小さい領域を使用することにより、メモリの断片化が原因のメモリ不足を防ぎ、システムリソースの負荷軽減を実現することが可能である。
【００１９】
図５を参照すると、本発明の他の実施形態によるメモリ管理装置は、図１のメモリ管理装置に、ワード単位にビットマップ領域を検索するワード単位ビットマップ検索部２０と、バイト単位にビットマップ領域を検索するバイト単位ビットマップ検索部２１を付加した構成となっている。
【００２０】
本実施形態では、ビットマップ領域１０１内に必要な空きがある場合、空きビットマップ検索部１４は、必要ビットマップ領域数に応じてワード単位ビットマップ検索部２０、バイト単位ビットマップ検索部２１、ビット単位ビットマップ検索手段１５を用いてビットマップ領域の検索を行う点が第１の実施形態と異なる。
【００２１】
ここで、必要に応じてというのは、必要なビットマップ領域サイズが１ワードを越える場合、必要領域サイズのワード数分だけワード単位に空きを検索し、余った分、または１ワード以下の場合、バイト単位に空きを検索し、最後に余った分（これは８ビット未満を意味する）についてビット単位に空きを検索することである。
【００２２】
なお、メモリ管理装置の機能は、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータ内の揮発性メモリのように、一定時間プログラムを保持しているものを含む。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態によるメモリ管理装置のブロック図である。
【図２】図１のメモリ管理装置の動作を示すフローチャートである。
【図３】図１のメモリ管理装置の動作を示すビットマップの例を示す図である。
【図４】本発明の他の実施形態によるメモリ管理装置のブロック図である。
【符号の説明】
【００２４】
１１    メモリ確保部
１２    必要ビットマップ領域数計算部
１３    最大連続空き領域長管理部
１４    空きビットマップ検索部
１５    ビット単位ビットマップ検索部
１６    確保候補場所領域管理部
１７    ビットマップ確保部
１８    ビットマップ検索位置通知部
１９    割り当てメモリアドレス算出部
２０    ワード単位ビットマップ検索部
２１    ビット単位ビットマップ検索部
１００、１００Ａ    メモリ
１０１    ビットマップ領域
１０２    割り当て領域
２０１-２０５  ステップ
【図１】
2007264692.tif 000003
【図２】
2007264692.tif 000004
【図３】
2007264692.tif 000005
【図４】
2007264692.tif 000006