(57)【要約】【課題】効率的な空き領域の探索を目的とする。【解決手段】複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップ３を用いて空きメモリの探索を行う空きメモリ探索方法であって、ＢＭ法を用いて、空きメモリの探索を行う探索段階を有することにより上記課題を解決する。【選択図】　　　　図３
2004110735.tif 000002
【特許請求の範囲】
【請求項１】
複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索方法であって、
ＢＭ法を用いて、空きメモリの探索を行う探索段階を有することを特徴とする空きメモリ探索方法。
【請求項２】
前記ＢＭ法は、前記メモリマップの連続するブロックのフラグの値と、値が１のｋ（ｋ＞＝１以上の自然数）ビット列とを、ｋビット列の後端から前端へ行って行く比較処理を、順次行うことを特徴とする請求項１記載の空きメモリ探索方法。
【請求項３】
前記探索段階は、前記メモリマップの連続するｎ（ｎ＞＝１の自然数）ブロックのフラグの値と、値が０のｎビット列との論理和演算を順次行って、探索の開始位置を決定することを特徴とする請求項１又は２記載の空きメモリ探索方法。
【請求項４】
複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索プログラムであって、
ＢＭ法を用いて、空きメモリの探索を行う探索手順をコンピュータに実行させることを特徴とする空きメモリ探索プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、空きメモリ探索方法及び空きメモリ探索プログラムに係り、特に複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索方法及び空きメモリ探索プログラムに関する。
【０００２】
【従来の技術】
近年、画像形成装置や、コンピュータなどの高速化、高機能化が進む中で、主記憶装置や外部記憶装置などのメモリ資源へのアクセス速度の高速化が望まれている。例えば、画像形成装置では、画像形成装置の制御プログラムと、画像形成装置のメモリ間で大量の画像データのやりとりが行われるため、要求された連続したメモリの空き領域を高速で探索して、要求された容量のメモリを確保することが必要とされている。また、メモリは頻繁に開放と確保とが繰り返されるため、その所々にメモリの空き領域が分断されて存在するようになる。限られたメモリ資源を活用するためには、このような分断された空きメモリも効率的に探索して、利用する必要がある。
【０００３】
したがって、従来は、空きメモリを検索する場合、単位ブロックに分割されたメモリを、メモリの先頭から順次、比較していた。このように、メモリの先頭から探索を開始するため、分断されている空き領域を確実に探索することができた（例えば特許文献１。）。
【０００４】
【特許文献】
特開平１０−８３３４０号公報。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来の方法では、空き領域を探索するために、メモリの先頭から探索を開始していたため、メモリの大部分が既に使用されている状態にあり、メモリ領域の後端付近にしか空き領域がないような場合、空き領域の探索に時間がかかっていた。
【０００６】
特に、主記憶装置やハードディスクといったメモリ容量の大きなメモリに対して空き領域を探索する場合には、探索に要する時間が、装置全体の処理に係る時間に大きく影響していた。
【０００７】
本発明は、上記の点に鑑みなされたもので、効率的な空き領域の探索を目的とする。
【０００８】
【課題を解決するための手段】
そこで、上記問題を解決するため、請求項１記載の発明は、複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索方法であって、ＢＭ法を用いて、空きメモリの探索を行う探索段階を有することを特徴とする。
【０００９】
また、請求項２記載の発明は、前記ＢＭ法は、前記メモリマップの連続するブロックのフラグの値と、値が１のｋ（ｋ＞＝１以上の自然数）ビット列とを、ｋビット列の後端から前端へ行って行く比較処理を、順次行うことを特徴とする。
【００１０】
また、請求項３記載の発明は、前記探索段階は、前記メモリマップの連続するｎ（ｎ＞＝１の自然数）ブロックのフラグの値と、値が０のｎビット列との論理和演算を順次行って、探索の開始位置を決定することを特徴とする。
【００１１】
また、請求項４記載の発明は、複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索プログラムであって、ＢＭ法を用いて、空きメモリの探索を行う探索手順をコンピュータに実行させることを特徴とする。
【００１２】
請求項１記載の発明によれば、複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索方法であって、ＢＭ法を用いて、空きメモリの探索を行う探索段階を有することによって、効率的な空き領域の探索をすることができる。
【００１３】
請求項２記載の発明によれば、前記ＢＭ法は、前記メモリマップの連続するブロックのフラグの値と、値が１のｋ（ｋ＞＝１以上の自然数）ビット列とを、ｋビット列の後端から前端へ行って行く比較処理を、順次行うことによって、無駄な比較を無くし、効率的な探索をすることができる。
【００１４】
請求項３記載の発明によれば、前記探索段階は、前記メモリマップの連続するｎ（ｎ＞＝１の自然数）ブロックのフラグの値と、値が０のｎビット列との論理和演算を順次行って、探索の開始位置を決定することによって、少ない演算処理で探索の開始位置を決定することができる。
【００１５】
請求項４記載の発明によれば、複数の単位ブロックに分割されたメモリについて、その各単位ブロックの使用状況を、０又は１のフラグによって表示するメモリマップを用いて空きメモリの探索を行う空きメモリ探索プログラムであって、ＢＭ法を用いて、空きメモリの探索を行う探索手順をコンピュータに実行させることによって、効率的な空き領域の探索を行うプログラムを提供することができる。
【００１６】
【発明の実施の形態】
以下、本発明の実施の形態について図面に基づいて説明する。図１は、メモリのブロックの読み出しの一例を説明するための図である。図１では、説明に必要な構成を表し、説明に必要の無い構成を省略してある。以下の図においても同様である。
【００１７】
情報の処理に必要なメモリの割り当て要求があると、後述するメモリ管理部１０は、メモリ１から、要求されたサイズの空き領域のメモリのブロック２を探索して、読み出す。読み出されたブロック２は、情報の処理が終了するとメモリ１に返却される。
【００１８】
図１に示されるが如く、メモリ１は、多数のブロックにより構成され、メモリ１からのブロックの読み出しと、返却との管理を行うため、以下で示すメモリマップが用いられる。
【００１９】
図２は、メモリマップによるメモリの管理の一例を説明するための図である。図２において、メモリマップ３は、メモリ１の各ブロックの使用状況を、１を空き領域、０を使用中領域とする１ビットのフラグを用いて管理している。
【００２０】
以下、メモリマップ３を用いてメモリを管理する一例を、図３を用いて説明する。図３は、メモリマップを用いて空き領域を探索する一例を説明するための図である。
【００２１】
メモリを管理するメモリ管理部１０は、探索開始位置決定部１１と、空きメモリ探索部１２とから構成されている。
【００２２】
探索開始位置決定部１１は、メモリの割り当て要求があると、後述する空きメモリ探索部１１が、探索を開始する探索開始位置を、メモリマップ３上から探索して決定する。
【００２３】
空きメモリ探索部１２は、探索開始位置決定部１１が決定した探索開始位置から、要求されたサイズの空きメモリを、メモリマップ３を用いて、探索する。
【００２４】
メモリ管理部１０に対してメモリ割り当て要求があると、探索開始位置決定部１１は、メモリマップ３における空きメモリの探索開始位置を決定し、空きメモリ探索部１２は、探索開始位置決定部１１が決定した探索開始位置から要求されたサイズの空き領域の探索を開始する。
【００２５】
以下、図３の探索開始位置決定部１１の探索開始位置を決定する方法の一例について説明する。図４は、メモリマップの一例を表す図である。
【００２６】
図４に示してあるが如く、メモリマップ３の先端部分から０が相当数続くような場合は、メモリ１の先端部分から相当数のブロック領域は、使用中であることを示している。
【００２７】
このような場合、空きメモリ探索部１２が、メモリマップ３の先頭から探索を開始するのは、効率が悪いため、探索開始位置決定部１１は、メモリマップ３上のメモリの使用状況を表すビットと、１６ビットの全ての値が０のパラメータとの論理和演算を行って、探索の開始位置を探す。
【００２８】
探索開始位置決定部１１は、論理和演算の結果、全てのビットの値が０ならば、演算を行った領域には空き領域が存在しないため、処理を１６ビット分シフトさせて進めて、同様の論理和演算を行う。
【００２９】
論理和演算の結果、いずれかのビットの値が１ならば、演算を行った領域内に空き領域が存在するため、演算を行った領域の先頭のビットから空き領域の探索を開始するよう、空きメモリ探索部１２に通知する。
【００３０】
なお、本発明の実施において、パラーメータのビット列は、１６ビットに限定されるものではない。
【００３１】
以下では、探索開始位置決定処理の一例を、フローチャートを用いて説明する。
【００３２】
図５は、図３の探索開始位置決定部１１による探索開始位置決定処理の一例のフローチャートである。以下、図５の説明においては、空きメモリ探索プログラムが、処理を行うものとして説明する。
【００３３】
ステップＳ１０では、空きメモリ探索プログラムが、メモリマップ３上のメモリの使用状況を表すビットと、値が全て０の固定長ビットのパラメータとの論理和演算を行う。
【００３４】
ステップＳ１０に続いてステップＳ１１に進み、空きメモリ探索プログラムは、論理和演算の結果、全てのビットの値が０であったかどうかを判定する。全てのビットの値が０だと判定すると（ステップＳ１１においてＹＥＳ）、ステップＳ１２に進み、全てのビットの値が０でないと判定すると（ステップＳ１１においてＮＯ）、ステップＳ１３に進む。
【００３５】
ここで、メモリマップ上の０は使用中の領域を表すため、全てのビットの値が０のパラメータと、論理和演算を行った結果、全ての値が０ならば、該論理和演算を行った範囲に空き領域が存在しないことがわかる。
【００３６】
ステップＳ１２では、空きメモリ探索プログラムが、パラメータを固定長分シフトさせて、ステップＳ１０からの処理を繰り返す。
【００３７】
図６に、パラメータをシフトさせていきながらメモリマップ３から探索開始位置を探索する概念図を示す。
【００３８】
図６では、探索開始位置決定部１１は、メモリマップ３の先頭からパラメータをシフトさせながら論理和演算を行い、メモリマップ３上のビットが１になっている箇所を探索している。
【００３９】
ステップＳ１３では、探索開始位置決定部１１が、ステップＳ１０において論理和演算を行った範囲に空き領域があるため、該範囲を空き領域の探索開始位置として決定して、処理を終了する。
【００４０】
以下、図３の空きメモリ探索部１２の空きメモリを探索する方法の一例について、説明する。
【００４１】
空きメモリ探索部１２は、文字列探索のための線形探索アルゴリズムであるＢＭ（Ｂｏｙｅｒ−Ｍｏｏｒｅ）法を、空きメモリの探索に適用して、空きメモリの探索を行う。
【００４２】
ＢＭ法の探索アルゴリズムは、ある任意の探索対象文字列と、探索パターンとの比較を、探索パターンの後端から前端へと比較していき、もし探索パターンの後端が、対応する探索対象文字列中の文字と比較して一致すれば、探索パターンの一つ前の文字（後端から前端へと一つ進んだ文字）と、対応する探索対象文字列中の文字とを比較する。
【００４３】
もし比較して一致しなければ、それより前の探索パターンの文字列と、対応する探索対象文字列とを比較しても、探索パターン全体と、対応する探索対象文字列とが一致することはないので、探索パターン長分シフトさせて、次の探索を行う。
【００４４】
探索対象文字列と、探索パターンとが途中まで一致していた場合は、次の探索開始位置を、探索パターン長分から一致していた文字数分を引いた長さだけ、シフトさせて、探索を行う。
【００４５】
上記探索を繰り返すことによって、ＢＭ法では、探索対象文字列から、探索パターンと一致する部分を探索する。
【００４６】
空きメモリ探索部１２は、上記ＢＭ法による線形探索アルゴリズムを、メモリマップ３から空きメモリを探索するために適用する。
【００４７】
図７は、探索パターンを用いてメモリマップ３から空き領域を探索する概念図である。図７で、探索対象は、メモリマップ３上のビット列を表し、探索パターンは４ブロック分の空き領域を表している。なお、これらは本発明の実施を限定するものではない。
【００４８】
空きメモリ探索部１２は、メモリマップ３の各ブロックのメモリの使用状況を表すフラグの値の列から、メモリの割り当て要求で求められる連続空きブロック数分の空きメモリを探索する。
【００４９】
図７の例において、空きメモリ探索部１２は、探索対象のメモリマップ３の先頭の４ブロック分のビット列と、探索パターンの１１１１とを、探索パターンの後端から比較する。
【００５０】
図７Ａで示されるように、探索パターンの後端と対応する探索対象とを比較して、一致しない場合は、空きメモリ探索部１２は、探索パターン長分、探索パターンをシフトさせる。
【００５１】
次に、図７Ｂで示されるように、空きメモリ探索部１２は、探索パターンの後端と、対応する探索対象とを比較する。比較して、一致しない場合は、同様に、探索パターン長分、探索パターンをシフトさせる。
【００５２】
続いて、図７Ｃで示されるように、空きメモリ探索部１２は、探索パターンの後端と、対応する探索対象を比較する。比較して一致すると、図７Ｄで示されるように、探索パターンの後端の一つ前と、対応する探索対象とを比較する。
【００５３】
同様に、図７Ｅ、Ｆで示されるように、比較を行い、図７Ｆに示されるが如く、探索パターンの前端の一つのみが一致しなかった場合は、空きメモリ探索部１２は、探索パターン長（図７の例においては４）から、一致したビット数（図７の例においては３）を引いた分だけ、探索パターンをシフトさせる。
【００５４】
図７Ｇで示されるように、空きメモリ探索部１２は、再び探索パターンの後端と、探索対象とを比較する。
【００５５】
上述した如く、探索パターンの後端から、探索対象と比較し、一致しなかった場合は、探索パターン長分、シフトして探索をすることによって、単純に探索パターンの先頭から探索対象と比較するよりも、少ない比較回数で、要求されたメモリの空き容量を探索することができる。
【００５６】
以下では、探索処理の一例を、フローチャートを用いて説明する。図８は、図３の空きメモリ探索部１２による探索処理の一例のフローチャートである。以下図８の説明においては、空きメモリ探索プログラムが、処理を行うものとして説明する。
【００５７】
ステップＳ２０では、空きメモリ探索プログラムが、変数ｉに０、変数ｊに０、変数ｐに探索パターン長を初期値として設定する。ここで、変数ｉは、探索パターンの後端からのビット数を表し、ｊは探索パターンと、探索対象との一致したビット数を表している。
【００５８】
ステップＳ２０に続いてステップＳ２１に進み、空きメモリ探索プログラムは、探索パターンの後端からｉ番目のビットと、探索対象との論理積をとって、比較を行う。
【００５９】
ステップＳ２１に続いてステップＳ２２に進み、空きメモリ探索プログラムは、ステップＳ２１において比較した結果の判定を行い、一致している判定すると（ステップＳ２２においてＹＥＳ）、ステップＳ２４に進み、一致していないと判定すると（ステップＳ２２においてＮＯ）、ステップＳ２３に進む。
【００６０】
ステップＳ２３では、空きメモリ探索プログラムは、（ｐ−ｊ）分探索パターンをシフトさせて、ステップＳ２０からの処理を繰り返す。
【００６１】
ステップＳ２４では、空きメモリ探索プログラムは、ｊの値をインクリメントする。
【００６２】
ステップＳ２４に続いてステップＳ２５に進み、ステップＳ２５では、空きメモリ探索プログラムは、ｉと（ｐ−１）との比較を行い、一致していると判定すると（ステップＳ２５においてＹＥＳ）、処理を終了し、一致していないと判定すると（ステップＳ２５においてＮＯ）、ステップＳ２６に進む。
【００６３】
ステップＳ２６では、空きメモリ探索プログラムは、ｉの値をインクリメントし、ステップＳ２１からの処理を繰り返す。
【００６４】
【発明の効果】
上述の如く、本発明によれば効率的な空き領域の探索を行うことができる。
【００６５】
【図面の簡単な説明】
【図１】メモリのブロックの読み出しの一例を説明するための図である。
【図２】メモリマップによるメモリの管理の一例を説明するための図である。
【図３】メモリマップを用いて空き領域を探索する一例を説明するための図である。
【図４】メモリマップの一例を表す図である。
【図５】探索開始位置決定部による探索開始位置決定処理の一例のフローチャートである。
【図６】パラメータをシフトさせていきながらメモリマップから探索開始位置を探索する概念図である。
【図７】探索パターンを用いてメモリマップから空き領域を探索する概念図である。
【図８】空きメモリ探索部による探索処理の一例のフローチャートである。
【符号の説明】
１　　メモリ
２　　ブロック
３　　メモリマップ
１０　　メモリ管理部
１１　　探索開始位置決定部
１２　　空きメモリ探索部
【図１】
2004110735.tif 000003
【図２】
2004110735.tif 000004
【図３】
2004110735.tif 000005
【図４】
2004110735.tif 000006
【図５】
2004110735.tif 000007
【図６】
2004110735.tif 000008
【図７】
2004110735.tif 000009
【図８】
2004110735.tif 000010