(57)【要約】【課題】実アドレス空間上において連続領域を確保し、かつ、メモリを有効利用できるようにする。【解決手段】仮想アドレス空間上で新規の領域が確保される前の状態（ａ）から、仮想アドレス空間上においてページＶ１，Ｖ２を跨ぐ領域が確保領域として確保されようとしている状態（ｂ）のとき、仮想アドレス空間上において、ページＶ１，Ｖ２を跨ぐ領域に仮領域を確保する（ｃ）。ただし、仮領域は、ページ境界を跨ぐ最小のサイズの領域とされる。その後、再確保が行われ、要求サイズの確保領域が再度取得される（ｄ）。このとき、仮領域として確保された領域は、要求サイズの領域確保の対象外とされる。このため、確保領域は、仮領域の上位側の次のアドレスから確保され、ページＶ２内に収まっている。確保領域が取得できた後、仮領域が解放される（ｅ）。【選択図】図４
2008181314.tif 000002
【特許請求の範囲】
【請求項１】
仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て方法であって、
前記仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索ステップと、
前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定ステップと、
前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保ステップと、
前記仮領域確保ステップにおいて確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保ステップと、
前記領域確保ステップにおいて確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定ステップと、
前記仮領域を開放する解放ステップと
を備えることを特徴とするメモリ割り当て方法。
【請求項２】
前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保される
ことを特徴とする請求項１に記載のメモリ割り当て方法。
【請求項３】
前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域である
ことを特徴とする請求項１に記載のメモリ割り当て方法。
【請求項４】
前記領域確保ステップにおいて連続領域が確保できなかった場合、確保失敗とされる
ことを特徴とする請求項１乃至３のいずれかに記載のメモリ割り当て方法。
【請求項５】
仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て装置であって、
前記仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索手段と、
前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定手段と、
前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保手段と、
前記仮領域確保手段によって確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保手段と、
前記領域確保手段によって確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定手段と、
前記仮領域を開放する解放手段と
を備えることを特徴とするメモリ割り当て装置。
【請求項６】
前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保される
ことを特徴とする請求項５に記載のメモリ割り当て装置。
【請求項７】
前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域である
ことを特徴とする請求項５に記載のメモリ割り当て装置。
【請求項８】
前記領域確保手段が連続領域を確保できなかった場合、確保失敗とされる
ことを特徴とする請求項５乃至７のいずれかに記載のメモリ割り当て装置。
【請求項９】
仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て装置におけるメモリ割り当てプログラムであって、
前記仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索ステップと、
前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定ステップと、
前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保ステップと、
前記仮領域確保ステップにおいて確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保ステップと、
前記領域確保ステップにおいて確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定ステップと、
前記仮領域を開放する解放ステップとを前記メモリ割り当て装置に実行させる
ことを特徴とするメモリ割り当てプログラム。
【請求項１０】
前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保される
ことを特徴とする請求項９に記載のメモリ割り当てプログラム。
【請求項１１】
前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域である
ことを特徴とする請求項９に記載のメモリ割り当てプログラム。
【請求項１２】
前記領域確保ステップにおいて連続領域が確保できなかった場合、確保失敗とされる
ことを特徴とする請求項９乃至１１のいずれかに記載のメモリ割り当てプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリ割り当て方法に関し、特に、実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て方法に関するものである。
【背景技術】
【０００２】
従来より、実メモリ空間の領域を確保する場合、連続する空き領域のサイズと要求サイズを比較し、空き領域のサイズが要求サイズ以上であればその空き領域を割り当て、空き領域のサイズが要求サイズ未満であれば上位アドレスにある空き領域に対して上記処理を繰り返し、最初に見つかった空き領域を割り当てるという処理が行われていた（例えば、特許文献１参照）。
プログラムによっては、仮想アドレス空間において動的に確保したメモリ領域を、実アドレス空間に変換して使用しなければならないケースが存在する。具体的にはＢＩＯＳコールするときのスタック領域／ワーク領域や周辺デバイスが使用する領域などがこれに該当する。ここで複数ページから構成される仮想アドレス空間から動的にメモリ確保する場合を考える。今、実メモリ上に使用不可領域があると仮定すると、単純に空き領域を使用した場合、分散してアドレス割り当てを行うことがあり、仮想アドレス空間上で連続して確保した領域が、実アドレス空間上では連続した領域にならない可能性がある。その場合、本領域を実アドレス空間として使用すると、割り当てられた実アドレス空間以外にアクセスすることになり、正しいメモリアクセスができない。
図８にこの例を示す。図８は、仮想アドレス空間３と実アドレス空間４との対応付けを示している。例えば、仮想アドレス空間３上の領域３１は、ページＶ０，Ｖ１，Ｖ２，Ｖ３から構成されている。同様に、実アドレス空間４上の領域４１は、ページＰ０，Ｐ１，Ｐ２、・・・、Ｐ１０から構成されている。今、仮に、実アドレス空間上のページＰ２とページＰ６が、使用不可領域であると仮定した場合、単純に空き領域を使用する方法のひとつとして、仮想アドレス空間３のページＶ０に実アドレス空間４のページＰ１を割り当て、以下同様に、ページＶ１にページＰ３を、ページＶ２にページＰ５を，ページＶ３にページＰ４をそれぞれ割り当てることがあげられる。このとき、仮想アドレス空間３から動的に確保した領域の先頭アドレスと最終アドレスの両方が、ページＶ２内に収まっていたと仮定すると、実アドレス空間上でもページＰ５内に収まっているので、この領域を実アドレス空間に変換し利用しても連続しているため問題はない。
しかし、動的に確保した領域の先頭アドレスがページＶ０内で、最終アドレスがページＶ１内であった場合、実アドレス空間４上では、それぞれ、Ｐ１とＰ３に該当し、実アドレス空間４上では連続にならないということになる。このとき、この領域を実アドレスに変換して利用した場合、正しいメモリアクセスができない問題が生じる。このことを回避するために、対応する実アドレス空間４上の領域もすべて連続であることを保障してアドレス割り当てを行うことが考えられる。
しかしながら、割り当て容量よりも小さい間隔で「使用不可領域」が存在した場合、「使用不可領域」を回避したアドレス空間を使用しなければならない。その結果、「使用不可領域」に挟まれた領域を有効に利用できない問題がある。この例を示したものが図９となる。ここで、仮に、実アドレス空間４上のページＰ２とページＰ６が、使用不可領域であると仮定した場合、前述のように対応する実アドレス空間４上の領域もすべて連続であることを保障しようとすると、ページＶ０，Ｖ１，Ｖ２，Ｖ３に対して、それぞれ実アドレス空間４上で連続したページＰ７，Ｐ８，Ｐ９，Ｐ１０を対応させなければならない。
これは、ページＰ０，Ｐ１，Ｐ３，Ｐ４，Ｐ５は領域として空いているが、連続して対応づけようとしても、ページＰ２、または、ページＰ６の使用不可領域と重複してしまうため、実アドレス空間４上で連続した領域への対応づけができないためである。
【特許文献１】特開２００１−２３６２４９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
このように、従来のメモリ割り当て方法では、実アドレス空間４上でのページＰ０，Ｐ１，Ｐ３，Ｐ４，Ｐ５は、未使用領域となり、メモリを有効活用できない状態にあるという問題があった。
本発明はこのような状況に鑑みてなされたものであり、連続した実アドレス空間を持てない計算機においても仮想アドレス空間から動的に確保した領域が実アドレス空間上においても連続した領域として確保されることを保障することができるようにするものである。
【課題を解決するための手段】
【０００４】
請求項１に記載のメモリ割り当て方法は、仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て方法であって、仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索ステップと、前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定ステップと、前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保ステップと、前記仮領域確保ステップにおいて確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保ステップと、前記領域確保ステップにおいて確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定ステップと、前記仮領域を開放する解放ステップとを備えることを特徴とする。
また、前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保されるようにすることができる。
また、前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域とすることができる。
また、前記領域確保ステップにおいて連続領域が確保できなかった場合、確保失敗とされるようにすることができる。
請求項５に記載のメモリ割り当て装置は、仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て装置であって、仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索手段と、前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定手段と、前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保手段と、前記仮領域確保手段によって確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保手段と、前記領域確保手段によって確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定手段と、前記仮領域を開放する解放手段とを備えることを特徴とする。
また、前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保されるようにすることができる。
また、前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域とすることができる。
また、前記領域確保手段が連続領域を確保できなかった場合、確保失敗とされるようにすることができる。
請求項９に記載のメモリ割り当てプログラムは、仮想アドレス空間上で確保された連続領域に対応して実アドレス空間上で連続領域が確保されることを保障するメモリ割り当て装置におけるメモリ割り当てプログラムであって、仮想アドレス空間上で要求サイズ以上の空き領域を検索する検索ステップと、前記空き領域から前記要求サイズの領域が確保されるとき、前記領域がページを跨ぐか否かを判定する判定ステップと、前記判定の結果、ページを跨ぐと判定された場合、前記領域のうち、ページ境界を跨ぐ最小のサイズの領域を仮領域として確保する仮領域確保ステップと、前記仮領域確保ステップにおいて確保された前記仮領域を除き、再度、前記仮想アドレス空間上において領域の確保が行われる領域確保ステップと、前記領域確保ステップにおいて確保された領域がページを跨がないとき、前記領域を確保領域として確定する領域確定ステップと、前記仮領域を開放する解放ステップとを前記メモリ割り当て装置に実行させることを特徴とする。
また、前記空き領域から前記要求サイズ分の前記領域を差し引いた残りの領域のサイズが、基準となる最低サイズ以上ない場合、前記空き領域全体が仮領域として確保されるようにすることができる。
また、前記仮領域は、前記領域の最上位アドレスを含む前記仮想アドレス空間上のページの最下位アドレスと、前記領域の最下位アドレスを挟む領域とすることができる。
また、前記領域確保ステップにおいて連続領域が確保できなかった場合、確保失敗とされるようにすることができる。
【発明の効果】
【０００５】
本発明のメモリ割り当て方法によれば、仮想アドレス空間から動的に確保した領域を実アドレス空間上でも連続したものとして扱うことが可能となる。即ち、仮想アドレス空間上で動的に確保した連続領域が実アドレス空間上でも連続していることを保障することができる。
【発明を実施するための最良の形態】
【０００６】
本発明は、仮想アドレス空間において動的に確保されるメモリ領域が、実アドレス空間においても連続領域であることを保障し、メモリ空間を効率的に利用できるようにするものである。なお、本発明は、アプリケーション毎のページ管理ができないソフトウェアや、連続した実メモリ空間が取れない計算機において有効である。
【０００７】
図１は、本発明が適用されるコンピュータの構成例を示している。図１において、記憶領域確保処理２は、仮想アドレス空間から動的にメモリを確保するものであり、オペレーティングシステム、もしくは、アプリケーション１から動的メモリ確保の要求を受けた際、実際にメモリを確保する処理を行い、その結果を要求元に返す機能を有している。
【０００８】
記憶領域確保処理２は、前処理２１と第一記憶領域確保手段２２と第二記憶領域確保手段２３を有している。前処理２１では、確保対象の領域中の空き領域を検索する機能をもっており、その結果から、第一記憶領域確保手段２２と第二記憶領域確保手段２３を選択する機能も有している。
【０００９】
第一記憶領域確保手段２２と第二記憶領域確保手段２３の違いは、検索された空き領域の容量と実際に確保する領域の容量の関係に起因して処理がわかれるものである。第一記憶領域確保手段２２が選択された場合、最初に、前処理２１で検出された空き領域から、要求容量を採取した場合のメモリ領域アドレスを計算する。この計算されたメモリ領域の先頭と最後のアドレスが仮想アドレス空間を管理するページ境界を跨いでいなければ、この動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できるため、第一通常確保手段２２１に進み、実際にメモリ確保を行う。
【００１０】
逆に、計算されたメモリ領域の先頭と最後のアドレスがページ境界を跨いでいた場合、動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できないため、第一回避確保手段２２２に進む。第一回避確保手段２２２では、このページ境界を跨ぐ領域に仮領域を配置し、再帰的に記憶領域確保処理２に進み、再確保を試みる。
【００１１】
再確保において、第一通常確保手段２２１、もしくは、第二通常確保手段２３２で実アドレス空間上も連続である領域を確保できた場合には、再帰的に記憶領域確保処理２をコールした第一回避確保手段２２２に確保できた先頭アドレスと共に確保成功として戻る。再帰的な実行から戻った回避確保手段２２２は、先に確保した仮領域を解放し、再確保において、確保できた領域のアドレス要求元に返却する。
【００１２】
なお、再確保処理は、２度目だけでなく確保できるまで試みるが、最大で（ページ数−１）回繰り返されることになる。また、ページ境界を跨ぐ領域に仮領域を配置しなければならないのは、再確保を試みた際、当該領域において再度確保しようとしてしまうのを回避するためである。
【００１３】
他方、第二記憶領域確保手段２３が選択された場合、最初に、前処理２１で検出された空き領域を使用する領域として確保する。この領域が仮想アドレス空間を管理するページ境界を跨いでいなければ、この動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できるため、第二通常確保手段２３１に進み、確保領域として確定させる。
【００１４】
逆に、このメモリ領域の先頭と最後のアドレスがページ境界を跨いでいた場合、動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できないため、第二回避確保手段２３２に進む。第二回避確保手段２３２では、このページ境界を跨ぐ領域を仮領域とし、再帰的に記憶領域確保処理２に進み、再確保を試みる。
【００１５】
第一回避確保手段２２２と同様に、再確保において、第一通常確保手段２２１、もしくは、第二通常確保手段２３２で実アドレス空間上も連続である領域を確保できた場合には、再帰的に記憶領域確保処理２をコールした第二回避確保手段２３２に確保できた先頭アドレスと共に確保成功として戻る。
【００１６】
再帰的な実行から戻った回避確保手段２３２は、先に確保した仮領域を解放し、再確保において、確保できた領域のアドレス要求元に返却する。
【００１７】
以上の動作により、ページ境界を跨ぐ動的メモリ確保を回避することができ、実アドレス空間における連続性も保障できるようになる。
【００１８】
図１を参照すると、本実施の形態は、オペレーティングシステム、もしくは、アプリケーション１と記憶領域確保処理２とを含む。オペレーティングシステム、もしくは、アプリケーション１のオペレーティングシステムの種別に制限はなく、オペレーティングシステムは、オペレーティングシステムの管理するワーク領域から、例えば、タスク領域、セマフォ領域、タイマ領域などの動的なメモリ確保要求や、ヒープ領域からの動的メモリ確保要求を実施する。同様にアプリケーションからもヒープ領域からの動的なメモリ確保要求、たとえば、Ｃ言語でのｍａｌｌｏｃ（）関数コールなどが実施される。
【００１９】
記憶領域確保処理２は、前処理２１と、第一記憶領域確保手段２２と、第二記憶領域確保手段２３とを含む。記憶領域確保処理２では、オペレーティングシステム、もしくは、アプリケーション１からの動的なメモリ確保要求を受け付け、指定された領域からの動的なメモリ確保を実行し、確保が成功した場合には、その確保された先頭アドレスをオペレーティングシステム、もしくは、アプリケーション１に返却する機能を有する。また、確保が失敗した場合には、確保失敗を通知する機能を有する。
【００２０】
前処理２１では、指定された領域の中から、要求容量を満たす空き領域を検索し、第一記憶領域確保手段２２か第二記憶領域確保手段２３のどちらを実行するか判断する機能を備えている。ここでは、第一記憶領域確保手段２２か第二記憶領域確保手段２３かの選択基準は、検索された空き領域から今回の要求容量を確保しても、残りの空き領域がさらなる確保要求に応えられる場合には、第一記憶領域確保手段２２を使用し、応えられない場合は、第二記憶領域確保手段２３を使用するものとする。第一記憶領域確保手段２２は、第一通常確保手段２２１と第一回避確保手段２２２を有し、確保を行う予定である領域のアドレス計算をする機能も保持する。
【００２１】
第一通常確保手段２２１は、今回、確保する領域が、ページ境界を跨がない領域であった場合に、実際に、検出された領域から要求容量の動的メモリ確保を実行する機能と、得られた動的メモリ領域のアドレスを第一記憶領域確保手段２２に通知する機能を有する。
【００２２】
第一回避確保手段２２２は、確保する領域が、ページ境界を跨ぐ領域であった場合、当該領域を跨ぐ最小容量の仮領域を配置する機能と再帰的に記憶領域確保処理２を呼び出す機能と、記憶領域確保処理２の処理が終ったときに仮領域を解放する機能と、再帰的に実行することによって得られた動的メモリ領域のアドレス、もしくは、確保失敗したことを第一記憶領域確保手段２２に通知する機能を有する。
【００２３】
第二記憶領域確保手段２３は、第一記憶領域確保手段２２に対し、検索された空き領域の容量が異なるため、機能も異なっている。第二記憶領域確保手段２３も、第二通常確保手段２３１と第二回避確保手段２３２を有する。
【００２４】
まず、第二記憶領域確保手段２３は、検索された空き領域全体を要求サイズの領域として確保する。その後、確保した領域が、ページ境界を跨がない領域であった場合には、第二通常確保手段２３１を選択し、跨ぐ領域であった場合には、第二回避確保手段２３２を選択する機能を備える。
【００２５】
第二通常確保手段２３１は、確保した領域が、ページ境界を跨がない領域であった場合に、その領域を要求容量の動的メモリ確保として確定する機能と、得られた動的メモリ領域のアドレスを第二記憶領域確保手段２３に通知する機能を有する。
【００２６】
第二回避確保手段２３２は、確保した領域が、ページ境界を跨ぐ領域であった場合、当該領域を仮領域とする機能と、再帰的に記憶領域確保処理２を呼び出す機能と、記憶領域確保処理２の処理が終ったときに仮領域を解放する機能と、再帰的に実行することによって得られた動的メモリ領域のアドレス、もしくは、確保失敗したことを第二記憶領域確保手段２３に通知する機能を有する。
【００２７】
次に、図１乃至図４、及び図５のフローチャートを参照して本発明の実施の形態の動作について詳細に説明する。図２は、仮想アドレス空間において確保された連続領域（ページＶ０，Ｖ１，Ｖ２，Ｖ３）に対応して、実アドレス空間上でも連続領域（ページＰ７、Ｐ８，Ｐ９，Ｐ１０）を確保することができるが、「使用不可領域（ページＰ２，Ｐ６）」で挟まれた領域（ページＰ３，Ｐ４，Ｐ５）が無駄になること、および、未使用な領域（ページＰ３，Ｐ４，Ｐ５）は存在するが、実アドレス空間上、仮想アドレス空間上で確保された連続領域（ページＶ０，Ｖ１，Ｖ２，Ｖ３）に対応する連続領域を確保することができない状態を示している。
【００２８】
図３は、本発明の解決すべき課題を模式的に示している。動的メモリ確保によって、仮想アドレス空間上で確保された領域のページＶ０が実アドレス空間上のページＰ１に対応し、ページＶ１がページＰ３に対応し、ページＶ２がページＰ５に対応し、ページＶ３がページＰ４に対応するとき、仮想アドレス空間上のページＶ３内の領域＃１は、実アドレス空間上では、ページＰ４内に割り当てられる。この場合、領域＃１は仮想アドレス空間上でページを跨いでいないので、実アドレス空間上でも連続領域であることが保障される。一方、仮想アドレス空間上で確保された領域＃２は、仮想アドレス空間上でページＶ０とＶ１を跨いでいるので、実アドレス空間上では、連続領域であることが保障されず、この例では、「使用不可領域（ページＰ２）」を挟んでページＰ１とＰ３に分割されて割り当てられる。即ち、実アドレス空間上において分割され、連続領域とはならない。
【００２９】
図４は、図３に示した課題を解決する方法を示す模式図である。図４（ａ）は、仮想アドレス空間上で新規の領域が確保される前の状態を示している。図４（ｂ）は、仮想アドレス空間上においてページＶ１，Ｖ２を跨ぐ領域が確保領域として確保されようとしている状態を示している。図４（ｃ）は、仮想アドレス空間上において、ページＶ１，Ｖ２を跨ぐ領域に仮領域を確保した状態を示している。ただし、仮領域は、ページ境界を跨ぐ最小のサイズの領域とされる。この例では、使用中の領域は、ページＶ０からＶ１の途中までを占め、仮領域は、使用中の領域の最上位アドレスの上位側の次のアドレスから、ページＶ２の最下位アドレスまでの領域となる。
【００３０】
図４（ｄ）は、要求サイズの確保領域を再度取得した状態を示している。仮領域として確保された領域は、要求サイズの領域確保の対象外とされる。このため、この例では、確保領域は、仮領域の上位側の次のアドレスから確保され、ページＶ２内に収まっている。図４（ｅ）は、確保領域が取得できた後、仮領域が解放された状態を示している。仮想アドレス空間上で連続領域として確保された確保領域は、ページを跨いでいないので、実アドレス空間上でも連続領域であることが保障される。
【００３１】
以下、図５のフローチャートを参照して本実施の形態の動作について説明する。まず、オペレーティングシステム、もしくは、アプリケーション１から動的メモリ確保要求が発行される（ステップＳ１）。記憶領域確保処理２は、オペレーティングシステム、もしくは、アプリケーション１からメモリ確保要求を受け取ると、前処理２１にて仮想アドレス空間上において確保対象領域中の空き領域を検索する（ステップＳ２、Ｓ３，Ｓ９）。一般に、空き領域の割り当て方法には、先頭一致（Ｆｉｒｓｔ−Ｆｉｔ）、最良一致（Ｂｅｓｔ−Ｆｉｔ）、最悪一致（Ｗｏｒｓｔ−Ｆｉｔ）があるが、ここでは、先頭一致を例に説明し、最良一致（Ｂｅｓｔ−Ｆｉｔ）、最悪一致（Ｗｏｒｓｔ−Ｆｉｔ）については後述する。
【００３２】
先頭一致で検索するため、検索した空き領域のうち、要求容量以上の領域が見つかった場合には、その容量が、要求容量と等しいか否かを確認する（ステップＳ４）。なお、最後の領域まで検索して、見つからなかったときは確保失敗となる（ステップＳ１０）。
【００３３】
ステップＳ４では、要求容量と等しいか否かを確認するが、厳密には、当該空き領域から今回の要求容量分を差し引いた残りの容量が、管理ブロックを含む最低容量以上か否かを確認している。すなわち、差し引いた残りの容量に、別の要求による領域確保が可能な最低限度の容量が残っているか否かを確認している。これは、最低限度の容量が残っていない領域を空き領域として残すことができないためである。
【００３４】
要求容量と等しくなかった場合、すなわち、検索された空き領域から今回の要求容量を差し引いても、最低限度の容量が残っている場合、前処理２１から、第一記憶領域確保手段２２に処理が進む。第一記憶領域確保手段２２では、検索された空き領域から、要求容量を採取した場合のメモリ領域アドレスを計算する。
【００３５】
この計算されたメモリ領域の先頭と最後のアドレスがページ境界を跨いでいるか否かを確認する（ステップＳ５１）。跨いでいなければ、この動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できるため、第一通常確保手段２２１に進み、実際にメモリ確保を行う（ステップＳ８２）。そして最後に、確保できた動的メモリ領域の先頭アドレスを、メモリの要求元に返す（ステップＳ１０２）。
【００３６】
ステップＳ５１で、ページ境界を跨ぐと判断された場合、この動的メモリ確保は、物理アドレス空間上、連続領域であることを保障できないため、第一回避確保手段２２２に進む。第一回避確保手段２２２では、まず、ページ境界を跨ぐサイズのうち、最小のサイズを計算する。即ち、ページ境界を跨ぐ最小の領域のサイズ（最小サイズ）を計算する。そして、その最小サイズで、一旦仮領域を確保する（ステップＳ６１）。これは、再度、確保を試みたときに、同じエリアの確保を試みることを避けるためである。
【００３７】
仮領域を確保した後、本アルゴリズムを同じ要求容量で再帰的に実行する（ステップＳ８１）。再帰的に実行するのはステップＳ２からとなる。これは、最初の確保を試みた領域に架空の領域を配置し、再度、同じ状態に陥るのを避けた状態において同一容量の確保要求をすることを意味する。再帰的な確保要求によって、前述のステップＳ８２、もしくは、後述のステップＳ８４でメモリ確保ができた場合には、２回目の再試行で要求容量の動的メモリ確保ができたことになる。
【００３８】
逆に２回目の再帰的な確保要求において、失敗した場合でも、再度、再帰的に本アルゴリズムを実行することで可能な限り再確保を試みる。再試行は、領域がページ境界を跨ぐごとに行われるので、最大で（ページ数−１）回の再試行が行われる可能性がある（最初の確保要求を数えるとページ数分が最大値）。
【００３９】
当然ながら、再試行中に他の確保できる可能性のある空き領域がなければ、確保失敗の通知を返却することになるが、いずれにしても最大再試行回数は（ページ数−１）回となる。再帰的な確保処理から返ってくると、第一回避確保手段２２２に戻り、先に確保した仮領域を解放する（ステップＳ９１）。そして、最後に再帰的な実行から得られた結果を返す（ステップＳ１０１）。
【００４０】
他方、ステップＳ４において、要求容量と等しいと判断された場合、すなわち、当該空き領域から今回の要求容量分（要求サイズ分）の領域を差し引いた残りの領域の容量（サイズ）が、管理ブロックを含む最低容量（基準となる最低サイズ）以上ない場合、前処理２１から、第二記憶領域確保手段２３に処理が進む。
【００４１】
第二記憶領域確保手段２３では、検索された空き領域を使用する領域として確保する（ステップＳ５３）。次に、この確保された領域の先頭と最後のアドレスがページ境界を跨いでいるか否かを確認する（ステップＳ６３）。
【００４２】
跨いでいなければ、この動的メモリ確保は、物理アドレス空間上も連続領域であることを保障できるため、第二通常確保手段２３１に進み、当該領域を要求容量を満たす領域として確定させる（ステップＳ８４）。そして、動的メモリ領域の先頭アドレスを、メモリの要求元に返す（ステップＳ１０４）。
【００４３】
ステップＳ６３で、ページ境界を跨ぐと判断された場合、この動的メモリ確保は、物理アドレス空間上、連続領域であることを保障できないため、第二回避確保手段２３２に進む。第二回避確保手段２３２では、当該領域を仮領域として確定させる（ステップＳ７３）。これも、ステップＳ６１と同様に、再度、確保を試みたときに、同じエリアの確保を実行することを避けるためである。
【００４４】
仮領域を確保した後、本アルゴリズムを同じ要求容量で再帰的に実行する（ステップＳ８３）。そして、再帰的な実行から返ったときに、仮領域を解放する（ステップＳ９３）。最後に、再帰的な実行の結果を要求元に返して終了する（ステップＳ１０３）。以上が、本実施の形態の動作である。
【００４５】
本実施の形態により、次のような効果が得られる。第１の効果は、メモリを有効活用できることにある。その理由は、アプリケーション毎のページ管理ができないソフトウェアや連続した実アドレス空間を持てない計算機においても、仮想アドレス空間から動的に確保した領域を実アドレス空間上も連続したものとして扱えるためである。
【００４６】
次に、本発明の他の実施の形態について説明する。空き領域の割り当て方法には、一般に次の３つがある。
（１）先頭一致（Ｆｉｒｓｔ−Ｆｉｔ）：空き領域中の最初の実行可能領域に割り当て
（２）最良一致（Ｂｅｓｔ−Ｆｉｔ）：空き領域中の実行可能領域のうち、もっとも小さな領域に割り当て
（３）最悪一致（Ｗｏｒｓｔ−Ｆｉｔ）：空き領域中の実行可能領域のうち、もっとも大きな領域に割り当て
【００４７】
前述の図５では、「先頭一致」による例を図示したが、本発明の考え方は、上記３つの割り当て方法によらず、すべてにおいて適用可能である。いずれも本発明の本質にかかわるところに差分はないが、図６に「最良一致」によるフローチャートを示す。図５に示した「先頭一致」の場合と同様に、オペレーティングシステム、もしくは、アプリケーション１から動的メモリ確保要求が発行される（ステップＳ１）。
【００４８】
記憶領域確保処理２は、オペレーティングシステム、もしくは、アプリケーション１からメモリ確保要求を受け取ると、前処理２１にて確保対象領域中の空き領域を検索する（ステップＡ２、Ａ９）。
【００４９】
「最良一致」で検索するため、すべての空き領域を検索し、その中で必要容量を満たし、かつ、最も小さな領域を検出する（ステップＡ３）。この条件に合う領域が見つかった場合には、その容量が、要求容量と等しいか否かを確認する（ステップＳ４）。以降の処理は、先の「先頭一致」の場合と同様であるのでその説明は省略する。なお、条件を満たす領域が見つからなかったときは確保失敗となる（ステップＳ１０）。
【００５０】
図７は、「最悪一致」によるフローチャートを示している。図５に示した「先頭一致」の場合と同様に、オペレーティングシステム、もしくは、アプリケーション１から動的メモリ確保要求が発行される（ステップＳ１）。
【００５１】
記憶領域確保処理２は、オペレーティングシステム、もしくは、アプリケーション１からメモリ確保要求を受け取ると、前処理２１にて確保対象領域中の空き領域を検索する（ステップＢ２、Ｂ９）。
【００５２】
「最良一致」で検索するため、すべての空き領域を検索し、その中で必要容量を満たし、かつ、最も大きな領域を検出する（ステップＢ３）。この条件に合う領域が見つかった場合には、その容量が、要求容量と等しいか否かを確認する（ステップＳ４）。以降の処理は、先の「先頭一致」の場合と同様であるのでその説明は省略する。なお、条件を満たす領域が見つからなかったときは確保失敗となる（ステップＳ１０）。
【００５３】
なお、上記実施の形態の構成及び動作は例であって、本発明の趣旨を逸脱しない範囲で適宜変更することができることは言うまでもない。
【産業上の利用可能性】
【００５４】
本発明は、小規模から大規模までのあらゆるコンピュータに適用可能であるが、特に、アプリケーション毎のページ管理ができないソフトウェアを実装した計算機や連続した実メモリ空間が取れない計算機において有効である。また、メモリを有効利用できるため、昨今、幅広い製品が出されている組み込みシステム分野においても効力を発揮するものである。
【図面の簡単な説明】
【００５５】
【図１】本発明が適用されるコンピュータの構成例を示すブロック図である。
【図２】仮想アドレス空間において確保された連続領域に対応して、実アドレス空間上で確保される領域を示す図である。
【図３】本発明の解決すべき課題を模式的に示す図である。
【図４】図３に示した課題を解決する方法を示す模式図である。
【図５】本実施の形態の動作を説明するためのフローチャートである。
【図６】「最良一致」による動作の例を示すフローチャートである。
【図７】「最悪一致」による動作の例を示すフローチャートである。
【図８】仮想アドレス空間と実アドレス空間との対応付けの例を示す図である
【図９】「使用不可領域」に挟まれた領域を有効に利用できない例を示す図である。
【符号の説明】
【００５６】
１  オペレーティングシステム、もしくは、アプリケーション
２  記憶領域確保処理
３  仮想アドレス空間
４  実アドレス空間
２１  前処理
２２  第一記憶領域確保手段
２３  第二記憶領域確保手段
３１  仮想アドレス空間上の領域
４１  実アドレス空間上の領域
２２１  第一通常確保手段
２２２  第一回避確保手段
２３１  第二通常確保手段
２３２  第二回避確保手段
【図１】
2008181314.tif 000003
【図２】
2008181314.tif 000004
【図３】
2008181314.tif 000005
【図４】
2008181314.tif 000006
【図５】
2008181314.tif 000007
【図６】
2008181314.tif 000008
【図７】
2008181314.tif 000009
【図８】
2008181314.tif 000010
【図９】
2008181314.tif 000011