(57)【要約】本発明は、クライアントによって要求されるメモリの量によってメモリ空間におけるメモリを割り当てるメモリ管理システムに関し、このメモリ空間は、いくつかの等容量のコンテナを備え、そのコンテナの少なくとも一部は、いくつかの等容量のサブコンテナを備える。このシステムは、メモリ・ブロックを生成する手段を備え、そのメモリ・ブロックの容量はいくつかの所定の容量の中から選定され、その選定容量は、クライアントによって要求される上記メモリ量に少なくとも等しいものである。このシステムは更に、コンテナにおけるメモリ・ブロックに対してメモリを割り当てる手段を備え、このコンテナはメモリ・ブロックの少なくとも2倍の容量を有する最小コンテナである。
2005537557.tif 000002
【特許請求の範囲】
【請求項１】
クライアントによって要求されるメモリの量によってメモリ空間にメモリを割り当てるメモリ管理システムであって：
該メモリ空間はいくつかの等容量のコンテナを備え；
該コンテナの少なくとも一部はいくつかの等容量のサブコンテナを備え；
更に、メモリ・ブロックを生成する手段；
を備え；
該メモリ・ブロックの容量はいくつかの所定の容量のうちから選定され；
該選定容量は、該クライアントによって要求されるメモリの該量に少なくとも等しいものであり；
更に、コンテナにおいて該メモリ・ブロックに対してメモリを割り当てる手段；
を備え；
該コンテナは、該メモリ・ブロックの該容量の少なくとも2倍である容量を有するコンテナのうちの最小のものであることを特徴とするメモリ管理システム。
【請求項２】
請求項１記載のメモリ管理システムであって、コンテナに配置されている該サブコンテナが該コンテナの2分の１未満の容量を有することを特徴とするメモリ管理システム。
【請求項３】
請求項１記載のメモリ管理システムであって、コンテナが、等容量のメモリ・ブロック専用であることを特徴とするメモリ管理システム。
【請求項４】
請求項１記載のメモリ管理システムであって、該コンテナのうちの最大のものの容量が、該最大コンテナによって該メモリ空間を充填した場合、該最大コンテナよりも小さい残りの領域が、該最大コンテナよりもかなり小さい容量を有するように、選択されることを特徴とするメモリ管理システム。
【請求項５】
請求項１記載のメモリ管理システムであって、コンテナに配置されている該サブコンテナの該容量が、該サブコンテナによって該コンテナを充填した場合、該サブコンテナよりも小さい残りの領域が、該サブコンテナよりもかなり小さい容量を有するように、選択されることを特徴とするメモリ管理システム。
【請求項６】
クライアントによって要求されるメモリの量によってメモリ空間にメモリを割り当てる方法であって：
該メモリ空間はいくつかの等容量のコンテナを備え；
該コンテナの少なくとも一部はいくつかの等容量のサブコンテナを備え；
更に、メモリ・ブロックを生成する工程；
を備え；
該メモリ・ブロックの容量はいくつかの所定の容量のうちから選定され；
該選定容量は、該クライアントによって要求されるメモリの該量に少なくとも等しいものであり；
更に、コンテナにおいて該メモリ・ブロックに対してメモリを割り当てる工程；
を備え；
該コンテナは、該メモリ・ブロックの該容量の少なくとも2倍の容量を有するコンテナのうちの最小のものであることを特徴とする方法。
【請求項７】
請求項６記載の方法であって、コンテナに配置されている該サブコンテナが該コンテナの2分の１未満の容量を有することを特徴とする方法。
【請求項８】
請求項６記載の方法であって、コンテナが、等容量のメモリ・ブロック専用であることを特徴とする方法。
【請求項９】
請求項６記載の方法であって、該コンテナのうちの最大のものの容量が、該最大コンテナによって該メモリ空間を充填した場合、該最大コンテナよりも小さい残りの領域が、該最大コンテナよりもかなり小さい容量を有するように、選択されることを特徴とする方法。
【請求項１０】
請求項６記載の方法であって、コンテナに配置されている該サブコンテナの該容量が、該サブコンテナによって該コンテナを充填した場合、該サブコンテナよりも小さい残りの領域が、該サブコンテナよりもかなり小さい容量を有するように、選択されることを特徴とする方法。
【請求項１１】
コンピュータ判読可能媒体上に実施されるオペレーティング・システムであって：
請求項６乃至10記載のメモリを管理する方法；
を備えることを特徴とするオペレーティング・システム。
【請求項１２】
コンピュータ判読可能媒体であって：
請求項６乃至10記載のメモリを管理する方法を実行するアルゴリズム；
を備えることを特徴とするコンピュータ判読可能媒体。
【請求項１３】
組み込みリアル・タイム・ソフトウェア・システムであって：
請求項６乃至10記載のメモリを管理する方法；
を備えることを特徴とする組み込みリアル・タイム・ソフトウェア・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ空間におけるメモリを、クライアントによって要求されるメモリ量に応じて、割り当てるメモリ管理システムに関する。本発明は更に、メモリをメモリ空間において割り当てる方法に関する。更に、本発明はメモリを管理する方法を備えるコンピュータ判読可能媒体上で実施されるオペレーティング・システムに関する。本発明は更に、メモリを管理する方法を実行するアルゴリズムを備える、コンピュータ判読可能媒体に関し、メモリを管理する方法を備える組み込みリアル・タイム・ソフトウェア・システムに関する。最後に、本発明はメモリを管理する方法を備えるファイル・システムにも関する。
【背景技術】
【０００２】
コンピュータ・プログラムは通常、データを操作して結果を算出するアルゴリズムである。データを記憶するメモリのブロックはまず、そのデータが操作可能となる前に割り当てることを要する。データがもう要らなくなる場合、そのメモリのブロックは割り当て解除すなわち開放される。そのメモリのブロックの割り当てと割り当て解除とは通常、メモリ管理と呼ばれている。
【０００３】
メモリ管理は、メモリを、使用中か開放されているメモリ・ブロックを把握し、これをできるだけ速く行うことによって、管理するアロケータによって実行される。理想的なアロケータは空間も時間も浪費することなく、メモリのブロックの割り当てと開放とを行う。
【０００４】
従来のアロケータは、メモリを圧縮できず、どのメモリのブロックを割り当てるかを決定すると、その決定を変更できない。したがって、このメモリのブロックは、そのブロックを要求したプログラムがそのブロックを開放するようになるまで、不可侵のものとみなされることを要する。実際に、アロケータは開放されているメモリしか処理することができない。したがって、従来のアロケータは、直ちに要求に応答することを要する「オンラインの」アルゴリズムであり、その決定は変更できない。
【０００５】
従来のアロケータの場合、何れかの考えられるアロケーション・アルゴリズムに対して、何らかのアプリケーション・プログラムが、そのアロケータのストラテジを打破し、これに対して重大な断片化を行わせる方法によって、ブロックの割り当てと割り当て解除とを行う可能性が常に存在する。メモリのユーザの（メモリに関する）特性の一部が分かっている場合、メモリ・アロケータはこれらの特定の要求に「合わせる」ことができる。このように合わせることによって断片化の問題を軽減し得る。更に、動的割り当てと静的割り当てとを組み合わせ、特定のアルゴリズムを用いることによって、断片化を軽減し得るが、残念ながら、メモリ・オーバヘッドとCPU時間の消費とをもたらすこととなる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
動的メモリ管理によって、静的メモリ利用に加えて、４つの新たな課題をもたらすものである、すなわち：
-  外部断片化
-  内部断片化
-  メモリ・オーバヘッド(テーブル断片化)
-  リアル・タイムでの性能の課題
内部断片化は、外部断片化を妨げるストラテジの一部として受け入れ得る。例えば、組み込みソフトウェアでは、外部断片化は許されないが、それは、この外部断片化が経時的に悪化し、事実上、メモリの量を削減することがあるからである。
【０００７】
メモリ・オーバヘッドは多くの場合、ブックキーピングによってもたらされる。これに対してはテーブルが用いられることが多く、したがってこれはテーブル断片化と呼ばれている。これらのテーブルは例えば、未使用ブロックを有する、静的リストか、ルックアップ・テーブルであり得る。テーブルの形式でのメモリ・オーバヘッドは、静的なものであるので、容易に予測できる。
【０００８】
アロケータは、メモリのユーザの要求にできるだけ速く応答することを要する。例えば、C++の環境では、割り当てと削除の数は非常に大きなものになり得るものであり、したがって、利用するアルゴリズムは非常に高速なものであることが望ましい。通常、リアル・タイムでの割り当ての性能が劣悪であるのは特定のフリー・リストを検索して適切なメモリのブロックを見出すことによるものである。メモリのブロックを開放する場合、通常、所要時間はブロックを識別するもの（例えば、容量）を探索するのに用いられるが、それは、従来のアロケータの場合、消去するためには１つのポインタしか転送されないからである。
【０００９】
これらの４つの動的メモリ管理の課題の間でのトレードオフを検討することが必要である。例えば、低内部断片化と低外部断片化は、タイミング特性の悪化を犠牲にして実現し得るものであり、その逆も同様である。この例としては、（理論上は）断片化が何ら発生しないが、利用されるアルゴリズムは（時間）複雑度が高い、圧縮メモリ・アロケータがある。逆に、メモリ割り当てのストラテジが（ほとんど）ないことによって（すなわち、メモリにブロックを連続して配置することによって）リアル・タイムでの良好な性能をもたらす一方で、非常に劣悪な断片化数値をもたらす。
【００１０】
最も単純なストラテジはシーケンシャル・フィットである。このストラテジの実現形態にはいくつかのもの、すなわち第１のフィット、次のフィット、最良フィット及び最悪フィット、がある。ブロックは所定値へのラウンディングがされないので、「内部断片化」とも呼ばれている、ラウンディングによるメモリ・ロスは何らもたらされない。この方法の別の効果にはこの方法が単純であることがある。しかし、重大な断片化が発生し得るものであり、付随するフリー・リストを検索して適切なブロックを見出すことは極めて時間がかかる処理である。
【００１１】
別のストラテジとして「分離フリー・リスト」を用いることがある。２つの実現形態、すなわちクイック・フィット及びファスト・フィットがある。このストラテジも外部断片化を被り、全ての容量をサポートすることができないので、ラウンディングによるロスももたらされる。しかし、この方法は、フリー・リストを検索することを何ら要しないので、非常に高速である。
【００１２】
別の非常に頻繁に利用されるストラテジにはバディー・システムがある。このストラテジに関しても、いくつかの実現形態、すなわち2進バディー・システム、フィボナッチ・バディー・システム、重み付けバディー・システム、及びダブル・バディー・システムがある。2進バディー・システムの効果としては、（バディー）ブロックを高速に結合することと管理が単純であることがある。この方法の主な欠点としては、ラウンディングが非常に粗いので、メモリ利用率が悪く、多くの内部断片化をもたらすことがある。2進バディー・システムは外部断片化も被る。更に、管理の目的で、ブロック毎にヘッダを要する。フィボナッチ・バディー・システムは、程度の差はあれ、2進システムと同様な欠点を有する。しかし、内部断片化は、フィボナッチ級数の値が２のべき乗である値ほど速く上昇しないので、低減する。別の欠点には、バディーの計算はコスト高であることがある。フィボナッチ・バディーの別の考えられる欠点には、ブロックが特定の容量に対する要求を満たすよう分離される場合に、残りのブロックが、違った容量のものであり、プログラムが多くの同じ容量のオブジェクトを割り当てた場合に、そのブロックが有用となる可能性は低くなるものである。重み付けバディー・システムとダブル・バディー・システムは、2進バディー・システムと同様な欠点を有するが、小さいブロック内差異を有する効果も有する。
【００１３】
全く別の動的メモリ管理手法には、圧縮ハンドル・ベースのストラテジがある。ブロックのラウンディングは行われないので、内部断片化の問題がないことは明らかである。外部断片化が出現しつつあることは、実行時に圧縮によって解決される。しかし、この圧縮によって、リアル・タイムでの予測可能な性能は何ら保証できるものでない。更に、一間接レベルがもたらされる。この間接レベルによって、メモリ・オーバヘッドももたらされる。
【００１４】
メモリを管理する別の方法には、メモリ空間を、コンテナと呼ぶ、全て同じ容量の、小部分に分割することによるものがある。コンテナ内部には、クライアントによって要求されるメモリ・ブロックが割り当てられる。ここでは、各コンテナは、１つの特定の容量のブロックしか保持しない。この手法の効果は、第１に、割り当てと割り当て解除が高速で、内部断片化が非常に低いことであり、第２に、コンテナ容量が等しいために、外部断片化は何らもたらされないことである。その結果、組み込みリアル・タイム・システムに対する非常に信頼性の高い動的メモリ管理の方法が提供される。この方法は、しかし、大きな欠点を有する、すなわち、異なる容量のブロックを効率的に保持するのに最適なように選択すべきであるコンテナの容量は１つしかない（1つのコンテナ内部ではブロックは全て同じ容量を有する。）。ブロックの容量の範囲が広い場合には、最適化を行うことは不可能である。これらの欠点を回避するために、２つの異なるコンテナ容量を特定の製品の実現のために提案する、すなわち１つは小容量（＜1Ｋｂ）のブロックを保持するものであり、もう１つは大容量（＞１Kb、＜64Kb）のブロックを保持するものである。次に、ブロック容量がかなり変動する場合、２つのコンテナ容量では効率的なメモリ利用率を達成するのに十分でない。最後に、この解決策は、メモリ・アドレス空間全体を2つの部分、すなわち小容量コンテナを保持する1つの部分と大容量コンテナを保持するもう1つの部分、に分割することを要する、図１参照。その結果、この解決策は、要求されるブロック容量全て、予め分かっている場合にのみうまくいくものである。
【課題を解決するための手段】
【００１５】
本発明の目的としては、改良された方法で、メモリの割り当てを行うことがある。
【００１６】
このことは、クライアントによって要求されるメモリ量によってメモリ空間においてメモリを割り当てるメモリ管理システムによって得られるものである。メモリ空間は、いくつかの等容量のコンテナを備え、そのコンテナのうちの少なくとも一部はいくつかの等容量のサブコンテナを備える。このシステムはさらに、メモリ・ブロックを生成する手段を備え、該メモリ・ブロックの容量はいくつかの所定の容量のものから選定され、その選定容量は該クライアントによって要求される該メモリ量に少なくとも等しいものである。更に、このシステムは、コンテナにおける該メモリ・ブロックに対してメモリを割り当てる手段を備え、このコンテナは該メモリ・ブロックの容量の少なくとも2倍である容量を有する最小のコンテナである。
【００１７】
本発明によるメモリ管理システムによって提案される、メモリの割り当てはコンテナの容量と、コンテナ容量の数を合わせることによって最適化し得る。更に、本発明によって提案される複数レベルの、ネスト・コンテナの原理は、非常に広い範囲のブロック容量を可能とし、よって、ブロック容量を事前に知っていなくとも、事実上全ての場面において直接適用されることとなる。更に、起動時に、コンテナのレベルと容量との数を、最初に利用可能なメモリ空間を要求し、それを数回分割することによって、動的に設定し得る。最後に、非常に大きな、最上位のコンテナ容量を有することは小容量ブロックの割り当て特性に対する影響をほとんど有するものでないが、それは、その割り当て特性が最小規定コンテナ容量によって決定されるからである。何れかのコンテナ・ネスト・レベルでは、コンテナは等しい容量を有する。この効果としては、1つ又はいくつかのコンテナの割り当て解除を行うことによってもたらされるメモリ空間における何れかのホールが、コンテナ階層におけるこのレベルでの全く同数の何れかの新たに割り当てられるコンテナにちょうど合うほど十分大きく、メモリ空間のロスを伴わないので、何れかのコンテナ又はサブコンテナの割り当てと割り当て解除とを繰り返して行うことでメモリ空間の断片化がもたらされるものでない。コンテナとブロックとの容量は、メモリ利用率が最大になるように選択し得る。組み込みシステム用のメモリ割り当てプロフィールを作成することによって、コンテナとブロック容量との最適化を図ることが可能となる。
【００１８】
一実施例では、サブコンテナは、コンテナに配置され、該コンテナの2分の１未満の容量を有する。
【００１９】
サブコンテナを導入する目的は、メモリ利用効率を増大させることにある。すなわち、特定のブロック容量の（特定のブロック容量に丸められた）メモリ要求は、特定の容量の少なくとも１つのコンテナ全体を満たすものであり、コンテナにおけるブロックが占める空間と比較すると予備としてとっておく空間は非常に少ないものとなる。特定のブロック容量に対して、完全に満たされるコンテナが1つもない一方で、このコンテナ内部に割り当てられるこの特定の容量のブロックがかなりの数、存在する場合には、この選択されているコンテナ容量は明らかに大きすぎる。これは、コンテナにおける多くの空間が使用されていないので、望ましいものでない。この場合、小容量コンテナを導入することが有用である。しかし、この小容量コンテナは現行のコンテナ内部に一度だけしか合わない場合には役に立たないが、それは残りの空間が、何れかのネスト・レベルではコンテナは等しい容量を有するため、別のコンテナによってもう再利用できないからである。更に、各コンテナは通常、その内容に関する何らかの情報を保持するヘッダを有するため、コンテナ毎に3つ以上のサブコンテナを有することが効率的である。同じことが、コンテナにおけるブロックの数にもあてはまる。前述のように、効率性はコンテナが特定の容量のブロックによって充填されることによって大いに決定される。したがって、コンテナはあまり大きすぎるものであってもよくないものである。
【００２０】
特定の実施例では、コンテナは等容量のメモリ・ブロック専用のものである。それによって、コンテナ内部のメモリ・ブロックは全て、等しい容量を有し、コンテナ内部でブロックの割り当てと割り当て解除とを繰り返し行うことによってそのコンテナ内部での断片化をもたらすものでないようにしている。コンテナにおける何れかの開放された空間は新たな割り当て要求にちょうど合うほど十分大きなものとなることが保証される。次に、割り当て解除は高速で行われるが、それは、特定のメモリ・アドレスに対して、関連するコンテナだけを見出せばよいからであり、そのコンテナはその場合、そのヘッダ中にそのコンテナが有するブロックの容量に関する情報を有するものである。この検索の長さはコンテナのネスト・レベルによって判定され、このレベルは、非常に大きな範囲のブロック容量（例えば、32バイトから200Kバイトまでの範囲）に対しても、非常に限定的なものである（通常、4よりも小さいものである。）。
【００２１】
一実施例では、最大のコンテナの容量は、その最大のコンテナによってメモリ空間を充填する場合、その最大のコンテナよりも小さな、残りの領域がその最大のコンテナよりもかなり小さい容量を有するように選定される。メモリ空間をコンテナに分割することによって、この容量の別のコンテナに合うには小さすぎる、残りの空間ができるだけ小さくなるように、コンテナ容量を選択すべきである。この残りの空間がコンテナ全部とほぼ同じくらいの大きさである場合には、これは明らかにあまり効率的なものでない。なお、しかし、これは、最大のコンテナ容量がメモリ空間全体に比較すると非常に小さい場合、例えば、最大コンテナ容量が65306バイトであり、１６MBのメモリ空間に256回合い、58880バイトを未使用の状態にしておく（ロスは0.3%となる。）場合、常にあてはまるものでない。
【００２２】
別の実施例では、コンテナにおいて配置されるサブコンテナの容量は、そのサブコンテナによってコンテナを充填する場合、そのサブコンテナよりも小さい残りの領域は、そのサブコンテナよりもかなり小さな容量を有するように、選定される。ヘッダに対するある程度の予約部分を有する特定のコンテナ容量を選択する場合、その容量の倍数が高位コンテナ容量にちょうど合うようにサブコンテナの容量を選択することは常に可能なものではない。このことについては、何ら問題はない。しかし、高位コンテナにおける一部の空間が別のサブコンテナに合うには単に小さすぎるようにサブコンテナの容量が選定される場合、ほぼ１つのサブコンテナ全体の空間ロスが発生する。明らかに、わずかのサブコンテナしか大容量コンテナに合うことが可能でない場合にはあまり効率的でない。
【００２３】
本発明は更に、クライアントによって要求されるメモリの量に応じてメモリ空間におけるメモリを割り当てる方法に関し、そのメモリ空間はいくつかの等容量のコンテナを備え、そのコンテナの少なくとも一部はいくつかの等容量のサブコンテナを備え、その方法は：
メモリ・ブロックを生成する工程；
を備え、そのメモリ・ブロックの容量はいくつかの所定の容量の中から選定され、選定される容量はクライアントが要求するそのメモリ量に少なくとも等しいものであり；
更に、そのメモリ・ブロックに対するメモリをコンテナにおいて割り当てる工程；
を備え、そのコンテナはメモリ・ブロックの容量の少なくとも2倍である容量を有する最小のコンテナである。
【００２４】
本発明は更に、コンピュータ判読可能媒体上に実施されるオペレーティング・システムに関し、そのオペレーティング・システムは上記によってメモリを管理する方法を備える。
【００２５】
本発明は更に、上記によってメモリを管理する方法を備えるコンピュータ判読可能媒体に関する。
【００２６】
本発明は更に、上記によってメモリを管理する方法を備える組み込みリアル・タイム・ソフトウェア・システムに関する。このシステムはリアル・タイム環境に非常によく適したものであるが、それは高速での割り当てと割り当て解除のストラテジと性能の予測可能性とによるものである。
【００２７】
本発明は更に、上記によるメモリを管理する方法を備えるファイル・システムに関する。ファイル・システムは異なる容量の要求をディスク上の別々のパーティションにマッピングして読み取り/書き込みのアクセスの性能を最適化し得る。これは、ディスクとの間で記録と再生とを行うことを要するオーディオとビデオなどのストリーミング・データに有用である。
【発明を実施するための最良の形態】
【００２８】
本発明は、クライアントによる動的割り当て用に利用可能なメモリ空間をスタック・コンテナの階層として説明する。この手法では、利用可能なメモリ空間は全て、等容量のコンテナに分割される。各コンテナはその場合、クライアントによって要求される特定の容量のブロックと小容量のサブコンテナとの何れかを保持する。好適実施例において、メモリ空間を浪費することのないように、サブコンテナを備える大容量コンテナの容量は小容量のサブコンテナの倍数である容量を有するべきである。
【００２９】
割り当てられるブロックの容量は、クライアントによって決定され、したがって、特定の容量のコンテナに最適に複数回合うよう選択することは可能でない。しかし、高効率でメモリを割り当てることを、ブロックの容量が、ブロックが入っているコンテナと比較して小さい場合に、実現し得ることを表し得る。
【００３０】
本発明によるメモリ空間を説明する特定の方法は以下によるものである、すなわち、総割り当て可能メモリ空間をＭによって表すと、コンテナ群Ci  i=0,1,2,…,  は：
ni∈N,ni≧2,  i=0,1,2,3,…,
n0C0+Δ0=M,Δ0<<C0,
ni+1Ci+1+Δi+1=Ci,Δi+1<<Ci+1;
となるように選択される。
【００３１】
上記式は、コンテナ容量の範囲において、小容量サブコンテナは大容量コンテナに少なくとも2回は合うものであることを表している。更に、考えられる浪費空間Δiは、小容量サブコンテナの容量よりもかなり小さいものである。
【００３２】
メモリ空間において割り当てられているメモリ・ブロックは以下によってコンテナに配置されるものである、すなわち:
kの異なる容量Bk,ｋ=0,1,2,…,  は以下：
Ik∈N,Ik≧2,k=0,1,2,3,…,
Bk+1<Bk,
Ci+1<2Bk,
IkBk+δk=Ci,δk<<Bk;
の場合にコンテナCiに合わせられる。
【００３３】
コンテナに合うブロックは同様に表される。更に、ブロックは、小容量コンテナに少なくとも２回合うには大きすぎる場合及びコンテナにおける浪費空間δkがこのブロックの容量よりもかなり小さい場合にのみ、特定のコンテナに配置される。
【００３４】
クライアントがブロックBkの割り当てに相当するメモリの量が要求されると、どのコンテナにそれを配置すべきかが検査される。
【実施例】
【００３５】
図１には、本発明によるメモリ空間の例を示す。メモリ空間101は、メモリの連続した部分と、103と105とによって示すメモリの連続した領域を備えるものとの何れかであり得る。メモリ空間は更に、いくつかの等容量のコンテナ107に分割され、コンテナの容量Coは、浪費空間Δ0がコンテナ107の容量よりもかなり小さくなるように選択すべきである。コンテナの一部は更に、いくつかの等容量のサブコンテナ109に分割され、サブコンテナの容量Ciは、浪費空間Δ1がサブコンテナの容量よりもかなり小さくなるように選択すべきである。
【００３６】
図２では、容量Ｂ1、Ｂ2のメモリ・ブロックが図１によって示されるメモリ空間のコンテナに配置される、単純な例を示す。容量Ｂ2の最小ブロックは容量Ciのコンテナ109に配置される一方、大容量ブロックＢ1は容量C0のコンテナ107に配置されることになる。
【００３７】
図３は、小容量コンテナ301が大容量コンテナ303のサブコンテナである、２つのコンテナ容量を伴うアロケータの全体的な機能構造の例を表す。305でメモリの量が要求される場合、307でその量が検査され、特定のブロック容量に対する後続するラウンディングを高速で行い得るように事前にラウンディングを行い得る。割り当て処理における第１工程では、その容量にこの要求をラウンディングすることを要する、その適切なブロック容量を判定する。309では、適切なブロック容量の判定は、ルックアップ・テーブル、ハッシュ・テーブル又は特定の割り当て要求に対する特定のブロック容量の効率的な選定を実現する何れかの別の方法によって行われる。次に311では、適切なコンテナ容量が特定のブロック容量に対して判定される。更に、これはルック・アップ・テーブル、ハッシュ・テーブル、又は上記基準、すなわち、要求ブロック容量が特定のコンテナ容量の2分の１未満である場合、メモリのそのブロックがこの容量の利用可能なコンテナから取り出されることになり、さもなければ、そのブロックは大容量コンテナから得られるものを用いる単純なアルゴリズムを用いて行い得る。最大コンテナ容量を超える要求はサポートされず、例外となる。
【００３８】
第１要求が行われても、コンテナが未だ何ら割り当てられていない場合、最大容量の新たなコンテナが割り当てられ、この容量の「フリー」コンテナのリストに付加されることとなる。この動作は、以前に割り当てられたこの容量のコンテナ全てが充填されているか異なるブロック容量用に予約されている場合にも行われる。要求によって新たなコンテナを割り当てることは、メモリ空間の段階的なフォーマット化と考えることができる。
【００３９】
代替的には、最初に、メモリ空間全体を「最大」コンテナ空間C0に分割し、ポインタを容量C0の「フリー・コンテナ・リスト」におけるこれらの開始位置に配置することも考えられる。割り当て要求を扱うようコンテナが用いられると、これはそれに相当するフリー・リストから取り除かれる。異なる容量のコンテナを選択することを要する場合、その容量のコンテナのフリー・リストはフリー・コンテナを取り出すのに用いられる。このフリー・リストが空きである場合には、大容量のフリー・コンテナが選定され、そのフリー・リストから取り除かれ、次の小容量のフリー・コンテナに分割される。これらの小容量コンテナは、1つを除いて、全て、更にその特定のコンテナ容量のフリー・コンテナ・リストに配置される。なお、これは次の要求毎に、予測可能な性能を保証し得るように、段階的に行い得る。これらの小容量コンテナの１つは次に、ブロック要求を扱うよう用いられることになる。このコンテナは、なお大きすぎる場合、上記と同様に、何度も分割される。
【００４０】
最後に、適切な容量のコンテナが見出され、割り当てられる場合、これは（事実上）、個々のブロックを保持するのにちょうどよい程度に十分大きい部分に分割される。次に、フリー・リストがこのブロック容量について作成されることになる。フリー・リストはコンテナにおける全ての「フリー」ブロックの開始位置全てを有することを要しない。これらは更に、「フリー」コンテナ・リストについて行い得るように、割り当て/割り当て解除の手順の間に段階的に付加し得る。特定のブロック容量について何れかのフリー・リストが存在する場合、コンテナの割り当てもフォーマット化も要しない。
【００４１】
図３は、１つのコンテナ容量313のみがなお空きであり、したがってこのコンテナ容量についてのみ、１つのアイテムを保持しているフリー・コンテナ・リスト315がなお存在している状態を表す。別の容量のフリー・コンテナについての別のフリー・リストは全て、空きであり、それらはもう存在しない。しかし、異なる容量のブロックについていくつかのフリー・リスト311が存在する。一実施例では、図３に示すように、コンテナ、例えば、317の内部の空きブロックはリンクされている。このようにして、特定のコンテナは、別のコンテナが適用され、空きブロックを容易に識別し得る前に、完全に使い尽くされる。
【００４２】
図４は、上記によってメモリ空間においてメモリを割り当てるメモリ管理システム400の実施例を示す。このシステムは、メモリ空間を備えるメモリ・モジュール403に通信バス405を介して接続されるマイクロプロセッサ401を備える。マイクロプロセッサは更に、メモリ・モジュール403に記憶される割り当てアルゴリズムによってメモリ空間においてメモリの割り当てを行う。
【図面の簡単な説明】
【００４３】
【図１】本発明によるメモリ空間の例を示す図である。
【図２】2つの容量のメモリ・ブロック、Ｂ1、Ｂ2、が図１によって示されるメモリ空間のコンテナに配置される、単純な例を示す図である。
【図３】小容量コンテナが大容量コンテナのサブコンテナである、２つのコンテナ容量を伴うアロケータの全体的な機能構造の例を表す図である。
【図４】本発明によるメモリ管理システムの実施例を示す図である。
【図１】
2005537557.tif 000003
【図２】
2005537557.tif 000004
【図３】
2005537557.tif 000005
【図４】
2005537557.tif 000006
【国際調査報告】
2005537557.tif 000007
2005537557.tif 000008