(57)【要約】【課題】メモリへのアクセス回数及び書込み回数を、従来よりも低減した、動的な記憶方法を提供する。更に、従来よりも効率的であって、より高速なアクセスを行なう、メモリ割当て及び割当て解除方法を提供する。【解決手段】コンピュータ・メモリを管理する方法として、連続する永続的メモリのブロックを管理する方法であって、メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、主メモリ内の第１のポインタを更新することにより、第１のブロックから第２のブロックを割当てるステップとを含む。【選択図】        図２１
2004206733.tif 000002
【特許請求の範囲】
【請求項１】
連続する永続的メモリのブロックを管理する方法であって、
メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、
複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、
第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、前記主メモリ内の前記第１のポインタを更新することにより、前記第１のブロックから前記第２のブロックを割当てるステップと
を含む方法。
【請求項２】
ブロックｂを前記第１のブロックに追加するステップを含み、前記追加ステップが、
ｂに対応するコード・バイトを、ｂが前記第１のブロックの一部であることを示すように変更するステップと、
前記主メモリ内の前記第１のポインタを更新するステップと
を含む、請求項１記載の方法。
【請求項３】
前記少なくとも１コード・バイトが、前記第２のブロックがもはや前記第１のブロックの一部でないことを示す以外に、他の機能にも作用する、請求項１記載の方法。
【請求項４】
前記主メモリ内の前記第１のポインタの値にもとづき、前記永続的メモリ内の第２のポインタを周期的に更新するステップを含む、請求項１記載の方法。
【請求項５】
システム障害に応答して、前記少なくとも１コード・バイトを調査することにより、前記第１及び第２のポインタを更新するステップを含む、請求項４記載の方法。
【請求項６】
前記ヘッダが単一ブロック書込みを用いて初期化される、請求項１記載の方法。
【請求項７】
連続する永続的メモリのブロックを管理する方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置であって、前記方法が、
メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、
複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、
第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、前記主メモリ内の前記第１のポインタを更新することにより、前記第１のブロックから前記第２のブロックを割当てるステップと
を含むプログラム記憶装置
【請求項８】
ブロックｂを前記第１のブロックに追加するステップを含み、前記追加ステップが、
ｂに対応するコード・バイトを、ｂが前記第１のブロックの一部であることを示すように変更するステップと、
前記主メモリ内の前記第１のポインタを更新するステップと
を含む、請求項７記載のプログラム記憶装置。
【請求項９】
前記少なくとも１コード・バイトが、前記第２のブロックがもはや前記第１のブロックの一部でないことを示す以外に、他の機能にも作用する、請求項７記載のプログラム記憶装置。
【請求項１０】
前記主メモリ内の前記第１のポインタの値にもとづき、前記永続的メモリ内の第２のポインタを周期的に更新するステップを含む、請求項７記載のプログラム記憶装置。
【請求項１１】
システム障害に応答して、前記少なくとも１コード・バイトを調査することにより、前記第１及び第２のポインタを更新するステップを含む、請求項１０記載のプログラム記憶装置。
【請求項１２】
前記ヘッダが単一ブロック書込みを用いて初期化される、請求項７記載のプログラム記憶装置。
【請求項１３】
永久記憶域内の隣接するフリー・ブロックを合体するステップであって、
ブロックのサイズ及び割当て状況を示すヘッダを、各ブロックに対して保持するステップと、
ヘッダ情報を調査して、隣接フリー・ブロックを結合することにより、フリー・ブロックを合体するステップと、
達成される合体のレベルを示す情報を前記永久記憶域内に周期的に記憶するステップと
からなるフリー・ブロックを合体するステップを含む請求項１の方法。
【請求項１４】
請求項１３記載の方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置。
【請求項１５】
合体の間のシステム障害に応答して、前記永久記憶域内の情報を読出し、システム障害の前に達成された合体のレベルを決定するステップと、
前記永久記憶域内の情報にもとづき、ある時点で合体を再開するステップと
を前記フリー・ブロックを合体するステップに含む、請求項１３記載の方法。
【請求項１６】
請求項１５記載の方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ記憶方法及びシステムに関して、特に、ロバストな動的記憶域割当てのための方法及びシステムに関する。
【背景技術】
【０００２】
多くのコンピュータ・システムは記憶域を動的に割当てる必要がある。動的記憶割当ては、プログラムの実行のための記憶域を割当てるために、オペレーティング・システムにより使用される。動的記憶割当ての他の例には、Ｗｅｂデータを記憶するＷｅｂサーバが含まれる。多くの場合、要求されるメモリのサイズは、要求時まで計り知れない。動的に割当てられるブロックの寿命もまた不明である。
【０００３】
主メモリのための効率的な動的記憶域割当てを開発するために、これまでにかなりの研究が行われてきた。一方で、ディスクのための効率的な動的記憶域割当てアルゴリズムの開発は、余り研究されてこなかった。
【０００４】
ディスクにおける動的記憶域割当ては、様々な理由から重要である。多くの場合、システムがシャットダウンした後も、データが存続することが不可欠である。ディスク・メモリは永続的記憶域を提供する。ディスク・メモリはまた、故障許容記憶域を提供する。主メモリの内容が失われてしまう状況において、ディスク上に記憶される情報は、システム・クラッシュの後にしばしば保存される。ディスク・メモリの別の利点は、より多くのディスク・メモリが主メモリよりも手ごろな価格で入手可能なことである。従って、ディスク・メモリは、主メモリに適合（フィット）しない情報を記憶するために使用され得る。
【０００５】
図１を参照すると、第１のフィット・システムは、メモリ要求を満足する十分に大きい最初のメモリ・ブロック（の全てまたは一部）を割当てる。容量"７"のメモリ要求に対して、最初のフィットがＢ１を返却する。なぜなら、これは要求を満足するために遭遇する最初のブロックであるからである。最善のフィット・システムは、要求を満足する十分に大きい最小のブロック（の全てまたは一部）を割当てる。図１では、ブロックＢ３が返却されるべきである。なぜなら、容量"７"はＢ３（"８"の容量を有する）に最適に適合するからである。
【０００６】
図２を参照すると、バイナリ・バディ・システム（binary  buddy  system：相互協力方式）において、ブロック・サイズは２乗である（例えば４×４、８×８など）。多くの動的記憶域割当て（ＤＳＡ：dynamic  storage  allocation）は、フリー（すなわち未使用）・ブロックの１つ以上のリストを保持する。フリー・ブロックのリストなどのこうしたリストは、フリー・リストとして知られている。異なるサイズのブロックに対して、別々のフリー・リストが存在する。他のサイズのブロックを割当てるバディ・システムも存在する。動的記憶割当てにおける従来技術の概要が、非特許文献１及びこの論文における参考文献で述べられている。
【非特許文献１】Arun  Iyenga  著"Scalability  of  Dynamic  Storage  Allocation  Algorithms"（Proceedings  of  IEEE  Frontiers  '96、October  1996）
【０００７】
動的記憶域割当て（ＤＳＡ）は、隣接フリー・ブロックを合体するために、異なる方法を使用できる。１アプローチは、即時合体（immediate  coalescing）を使用するもので、この場合、図３に示されるように、ブロックが割当て解除されるとき、割当て解除されたブロックが隣のフリー・ブロックと結合される。図３において、ブロック・サイズが各ブロック内に示される。正のサイズはフリー・ブロックを示し、負のサイズは割当てられたブロックを示す。
【０００８】
図４を参照すると、別のアプローチが示され、これは遅延合体（deferred  coalescing）を含む。遅延合体が使用される場合、隣接フリー・ブロックは割当て解除後に自動的に結合されない。代わりに、ある時点で（要求を満足する十分に大きいブロックが突き止められない場合など）、ＤＳＡがメモリ内のブロックを走査し、図４に示されるように隣接ブロックを結合する。
【０００９】
断片化（fragmentation）はＤＳＡにより浪費されるメモリである。内部断片化は、要求サイズよりも大きいブロックにより要求を満足することにより、失われるメモリである（例えばブロック・サイズ２５に対する要求を、ブロック・サイズ３２により満足する場合など）。外部断片化は、フリー・ブロックに割当て済みブロックが点在する場合に発生する。これらの状況では、たとえｂバイトより多くがフリーであっても、ｂバイトの割当て要求が満足されない。なぜなら、フリー記憶域の最大の連続ブロックが、ｂバイトよりも小さいからである。
【００１０】
非特許文献１で述べられる多重フリー・リスト・フィットＩ（ＭＦＬＦ  Ｉ  multiple  free  list  fit）は、サイズにより編成される複数のフリー・リストを使用する。小ブロックのためのフリー・リストは、クイック・リストとして知られる。大ブロックのためのフリー・リストは、ｍｉｓｃリストとして知られる。１つのｍｉｓｃリストが保持される場合、ＭＦＬＦ  Ｉはクイック・フィットとして知られる記憶域割当てシステムに退化する。
【００１１】
図５を参照すると、クイック・フィット技法が示される。このシステムでは、サイズ１６までのブロックに対して、クイック・リストが存在する。クイック・リストの数は、異なる要求分配に対して、性能を最適化するように変更され得る。この例では、サイズｓ（２≦ｓ≦１６、２が最小ブロック・サイズ）のブロックに対する割当てが、サイズｓに対応するクイック・リストを調査することにより行われる。このリストが空でなければ、リスト上の最初のブロックが要求を満足するために使用される。ここでグレーン・サイズ（grain  size）の倍数に相当するブロック・サイズについても、クイック・リストを有することが可能である。例えば、図２では、グレーン・サイズは１である。グレーン・サイズが１０００の場合、サイズ１０００、２０００、３０００、...、１６０００のブロックのクイック・リスト（合計１６のクイック・リスト）が使用され得る。ＭＦＬＦ  Ｉは遅延合体を使用する。メモリは図５に示されるように、作業記憶域１２及びテール１４に分割される。作業記憶域１２は、割当てられたブロック、及びフリー・リスト上のブロックを含む。テール１４は、メモリの片端において未割当ての記憶域の連続ブロックを含む。何かを割当てる以前の初期には、テール１４は全ての割当て可能なメモリを含み、フリー・リストは空である。フリー・リストはクイック・リストとｍｉｓｃリストとを含み、ｍｉｓｃリストは大きなメモリ・ブロックに対して使用される。ブロック１３は、あるサイズ（ブロック１３内の数により示される）を含む。１つ以上のフリー・リストを調査しても、要求が満足されない場合、要求はテール１４から割当てることにより満足される。テール・ポインタは、テール１４が開始する位置を指し示す。割当てられたブロックが割当て解除されるとき、フリー・リストが占有される。
【００１２】
クイック・リストにとって大き過ぎるブロックに対する要求を満足するために、クイック・フィットはｍｉｓｃリストの第１のフィット探索を行う。大きなブロックの探索は、多くの命令を要求し得る。このオーバヘッドを低減するために、ＭＦＬＦ  Ｉは図６に示されるように、クイック・フィットの場合のような１つのリストの代わりに、複数のｍｉｓｃリストを使用する。図６では、１つのｍｉｓｃリストがサイズ１７乃至２５のブロック１３に対して存在し、別の１つはサイズ２６乃至４０のブロック１３に対して存在し、更に別の１つは、サイズ４１乃至６０のブロックに対して存在する。様々な方法が要求を満足するために使用可能であり、それらには図７及び図８に示されるように、ＭＦＬＦ  Ｉを用いて"８４"を割当てる方法が含まれる。図７は、８４を割当てる要求が満足される"前"の、メモリのスナップショットを示し、図８は要求が満足された"後"のスナップショットを示す。図７及び図８において、システムは、サイズ"９０"のブロックを分割し、過剰サイズ"６"をフリー・リストに返却することにより、リストＬ２上の最初のブロックを割当て、要求を満足する。システムはＬ１の代わりに、Ｌ２を調査する。なぜなら、Ｌ２上で許可される最小のブロックは、サイズ８９であるからである。従って、８９以下のサイズの要求を満足するために、Ｌ２内の最初のブロックを越えて探索する必要はない。
【００１３】
前述の技法は多くのアプリケーションにとって満足のいくものであるが、主メモリ動的記憶域割当てアルゴリズムをディスク・システムに直接的に適応化することは、しばしば性能の劣化をもたらす。なぜなら、ディスクをアクセスして書込むための待ち時間が、主メモリと比較して遙かに大きいからである。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従って、ディスクへのアクセス回数及び書込み回数を低減する、ディスク・メモリのための動的な記憶方法が待望される。更に、より効率的な記憶及びより高速なアクセス時間を提供する、メモリ割当て及び割当て解除方法が待望される。
【課題を解決するための手段】
【００１５】
本発明に従うコンピュータ・メモリを管理する方法は、連続する永続的メモリのブロックを管理する方法であって、メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、主メモリ内の第１のポインタを更新することにより、第１のブロックから第２のブロックを割当てるステップとを含む。
【００１６】
他の方法では、ブロックｂを第１のブロックに追加するステップを含み、追加ステップがｂに対応するコード・バイトを、ｂが第１のブロックの一部であることを示すように変更するステップと、主メモリ内の第１のポインタを更新するステップとを含む。少なくとも１コード・バイトは、第２のブロックがもはや第１のブロックの一部でないことを示す以外に、他の機能にも作用し得る。この方法は、主メモリ内の第１のポインタの値にもとづき、永続的メモリ内の第２のポインタを周期的に更新するステップを含む。方法は更に、システム障害に応答して、少なくとも１コード・バイトを調査することにより、第１及び第２のポインタを更新するステップを含む。ヘッダは単一ブロック書込みを用いて初期化される。
【００１７】
本発明の更に別の態様では、永久記憶域内の隣接するフリー・ブロックを合体する方法が、ブロックのサイズ及び割当て状況を示すヘッダを、各ブロックに対して保持するステップと、ヘッダ情報を調査して、隣接フリー・ブロックを結合することにより、フリー・ブロックを合体するステップと、達成される合体のレベルを示す情報を、永久記憶域内に周期的に記憶するステップとを含む。
【００１８】
この合体方法は、合体の間のシステム障害に応答して、永久記憶域内の情報を読出し、システム障害の前に達成された合体のレベルを決定するステップと、永久記憶域内の情報にもとづき、ある時点で合体を再開するステップとを含む。
【００１９】
これらの方法及び方法ステップは、方法ステップを実行するためのマシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置により実現され得る。
【００２０】
本発明のこれらの及び他の目的、特徴及び利点が、添付の図面に関連して後述する本発明の実施例の詳細な説明から明らかとなろう。
【発明の効果】
【００２１】
本発明により、メモリへのアクセス回数及び書込み回数を、従来よりも低減した、動的な記憶方法が提供される。更に、従来よりも効率的な記憶及びより高速なアクセス時間を提供する、メモリ割当て及び割当て解除方法が提供される。
【発明を実施するための最良の形態】
【００２２】
本発明は、メモリ管理及び割当てシステム及び方法に関する。ここで提供されるシステム及び方法は、従来システム及び方法に比べて、改善された性能を提供する。そして、本発明は特に、ディスク・メモリに有用である。ディスク上に情報を永続的に記憶する従来の技法は、ファイル・システム及びデータベースを使用する。
【００２３】
本発明により、従来技術を使用する場合に比べて、情報がディスク上に遙かに少ないオーバヘッドで記憶される。また、本発明を使用することにより、多数のオブジェクトが記憶され得る。多くのファイル・システムは、ディレクトリ内に記憶されるファイルの数により制限される。本発明は記憶されるオブジェクトの数に関して、これらの制限を有さない。
【００２４】
１実施例では、余計な記憶空間を著しく浪費することなく、ブロックの分割を最小化するように設計される方法が提供される。本発明の有用性は、ディスク割当て及び主メモリ割当ての両方に拡張する。
【００２５】
本発明は、ＭＦＬＦ  Ｉとの類似性を有するが、メモリ管理及びディスク性能の劇的な改善をもたらす変更を含む、新たな有用な動的記憶域割当て方法を提供する。１変更として、ブロック分割数の低減がある。ブロック分割数の低減は、例えばディスク・アロケーションなど、ブロックの分割が好ましくない場合に、重要である。
【００２６】
図９乃至図２１に示される要素は、様々な形態のハードウェア、ソフトウェアまたはそれらの組み合わせにより実現される。好適には、これらの要素は、プロセッサ、メモリ及び入出力インタフェースを有する、１つまたは複数の適切にプログラムされた汎用デジタル・コンピュータ上の記憶装置として実現される。
【００２７】
本発明の開示において、当業者であれば、後述のように、多数の一般に使用される記憶域割当てアルゴリズムを、本発明を用いるために適応化することができよう。従って、本発明は以下の実施例により述べられるが、これらは本発明を制限するものではない。本発明で使用されるメモリまたは主メモリは、ランダム・アクセス・メモリまたはキャッシュ・メモリなどの揮発性メモリを指し示すが、他のメモリ・タイプも使用可能である。ディスクまたはディスク・メモリは永続的メモリを指し、例えば、ハード・ディスク、フレキシブル・ディスク、コンパクト・ディスク、ＤＶＤ、ディスク・アレイまたは他の永続的記憶装置を含む。
【００２８】
ＭＦＬＦ  Ｉは前述のように、時に割当ての間にフリー・ブロックを分割し、ブロックの一部を割当て、他の部分をフリー記憶域に戻す。本発明はＭＦＬＦ  Ｉと比較して、分割されるブロックの数を有利に低減する。これはディスク記憶域を割当てるための重要なパラメータである。なぜなら、ブロックの分割は余計なディスク操作を生じるからである（ここで操作は読取りまたは書込みである）。従って、本発明はブロックを割当てる際に、ＭＦＬＦ  Ｉよりも少ない分割を行う。本発明はディスク・メモリ同様に、主メモリを割当てるためにも使用され得る。
【００２９】
添付の図面を参照すると、図面を通じて同一の参照番号は、同一のまたは類似の要素を表す。最初に図９及び図１０を参照すると、ディスクの割当て及び記憶管理のためのシステム／方法のブロック図が示される。リスト（例えばクイック・リスト、ｍｉｓｃリスト、またはフリー・リスト）は通常、リスト上に記憶される最小及び最大ブロックをそれぞれ表す、最小（min）または最大（max）サイズを有する（グレーン・サイズが１のクイック・リストでは、最小及び最大サイズは同一である）。最大ブロック・サイズを有するシステムでは、最近のｍｉｓｃリストの最大サイズが、最大ブロック・サイズである。最大ブロック・サイズを有さないシステムでは、最近のｍｉｓｃリストが最大サイズを有さないこともある。
【００３０】
ここでｓを要求サイズとする。ボックス８０７では、ｓが最大ブロックを記憶するリストの最小サイズよりも大きいか否かが判断される。大きい場合、処理は図１０のボックス９０５に続く。大きくない場合、処理はボックス８０５に続く。ボックス８０５では、システムは適切なリストを選択して調査する。ｌmin≧ｓなる最小サイズｌminを有するリストＬが選択される。他の基準もリスト選択のために使用可能である。処理はボックス８１０に続く。ボックス８１０では、リストＬが空か否かが判断される。空の場合、ボックス８１５でサイズｌminのブロックがテールから割当てられ、要求を満足するために使用される。Ｌが空でない場合、ボックス８２０で、メモリ・ブロックを分割することなく、リストＬからの最初のブロックが、要求を満足するために使用される。リストＬが異なるサイズのブロックを含む場合、当業者には明らかなように、直接的な拡張として、リストＬを探索することにより、より好適にフィットするブロックを獲得するか、割当てのために選択されたブロックを分割して、内部断片化を低減してもよい。
【００３１】
図１０を参照すると、本発明に従う大ブロックのための割当て方法が示される。ここでＬを最大ブロックを記憶するｍｉｓｃリストとする。ボックス９０５で、サイズがｓ以上且つｓ＋ａ以下（ここでａはしきい値で、例えば許容可能な浪費）の最初のブロックを突き止めるために、Ｌが調査される。ここで許容可能な浪費とは、時として割当ての間に、内部断片化を低減する目的で、ブロックを分割するために使用されるパラメータである。適切なブロックが見いだされる場合、ボックス９１０で、ブロックは分割無しに割当てられる。こうしたブロックが見いだされない場合、２つの可能性がある。リストＬ上のどのブロックも要求を満足するほど十分に大きくない場合、ボックス９３０で、サイズｓのブロックがテールから割当てられる。リストＬが十分に大きなブロックを含む場合、リストＬ上においてサイズがｓよりも大きい最小のブロックが、サイズｓ及びｒのそれぞれフラグメントｆ１及びｆ２に分割される（ボックス９３５）。
【００３２】
ｆ１は要求を満足するために使用される。ｆ２は、そのサイズに対応するフリー・リストの先頭に配置される。許容可能な浪費パラメータは動的に変化し得る。直接的な変形では、許容可能な浪費パラメータの代わりに、要求サイズなどの引数を取る関数を使用する。
【００３３】
本発明に従う割当て解除は直接的である。割当て解除されるブロックは、それらのサイズに対応するフリー・リストの先頭に配置される。１実施例では、遅延合体が使用される。本発明が主メモリ割当てに使用される場合、合体は直接的である。
【００３４】
本発明は、動的記憶域割当て機構（ＤＳＡ：dynamic  storage  allocator）管理型のディスク記憶域のために、遅延合体を実行する新たな方法を提供するものであり、これはファースト・フィット、ベスト・フィット、バディ・システム、ＭＦＬＦシステムなどの、様々な異なる方法と共に使用され得る。
【００３５】
記憶ブロックはヘッダを含む。ヘッダはブロックがフリー（未使用）か、割当て済みであるかを示すタグの他に、ブロック・サイズを含む。ヘッダ情報は、システムがクラッシュまたはオフされるときに保存されるように、ディスク上に含まれる。ヘッダ情報はまた、高速アクセスのために主メモリ内にもキャッシュされ得る。ヘッダ情報はディスク上に様々な方法で保持される。１方法は、ヘッダ情報として、指定バイト（例えば初期バイト数）のブロックを使用する。別の方法は、連続メモリの単一ブロック内に、複数ブロックに対するヘッダ情報を記憶する。
【００３６】
図１１を参照すると、隣接フリー・ブロックを合体する１つの好適な方法が示される。ボックス１００５で、合体のために必要なデータ構造が初期化される。例えば、多くのＤＳＡがフリー・リストを使用する。こうしたＤＳＡはボックス１００５において、フリー・リストを初期化する（例えば、１つ以上のフリー・リストを空にする）。ボックス１０１０、１０１２及び１０２５はループを形成し、そこでシステムがヘッダ・ブロックを走査して、隣接フリー・ブロックを結合する。システムはメモリの終わりのブロックから開始し、最初のブロックに対応するヘッダを読出す。システムは次にヘッダを順次走査し、隣接フリー・ブロックを結合する。フリー・リストを使用するメモリ・システムでは、フリー・ブロックが合体された後、それらが適切なフリー・リストに追加される。ボックス１０２５では、システムは、合体が進行したポイントを永続的記憶域に記録することにより、合体をチェックする。このチェックポイントの目的は、障害の際に必要とされる作業量を低減することである。チェックポイントは本発明により、陳腐化情報を更新するために使用される。
【００３７】
システム障害の場合、主メモリの内容は失われがちであるが、ディスク・メモリの内容は保持されがちである。システム障害の場合、チェックポイントは、既に実行された大半のまたは全ての合体作業を再実行する必要性を排除する。それに比較して、従来の方法は障害の後に、先頭からヘッダの再走査を要求する。有利な点として、ヘッダの順次走査を提供し、チェックポイントを設けることにより、よりロバストで永続的なメモリ・システムが提供される。更に、障害後の時間の浪費となる再合体が低減または排除され、例えば、合体時間の５０％以上が排除され、多くの場合、合体時間の１００％が排除される。チェックポイントが実行される頻度は適宜変更され、例えば、トランザクションの数に従い、または設定時間が経過した後に、変更される。頻繁なチェックポイントは、障害後に再実行される必要のある作業量を低減する。
【００３８】
ボックス１０１５では、最終クリーンアップ及び記帳操作が実行される。例えば、作業記憶域の終わりがフリー・ブロックを含む場合、そのブロックはこのステップにおいてテールに追加される。
【００３９】
本発明に従い永続的記憶域を効率的に割当て及び割当て解除する方法について、次に詳述することにする。本発明はＭＦＬＦシステム、ファースト・フィット、ベスト・フィットなどの、様々なＤＳＡと共に使用され得る。第１のメモリ管理方法（以下便宜上、メモリ管理方法１と呼ぶ）では、ディスクがヘッダを保持し、ヘッダはブロックがフリーか、割当て済みであるかを示すタグの他に、ブロック・サイズを含む。割当て及び割当て解除を処理するフリー・リスト・データ構造が、メモリ内に保持される。
【００４０】
図１２を参照すると、本発明のメモリ管理方法１に従う割当てが示される。図１２に示されるボックスは、任意の順序で実行され得る。ボックス１１０５では、内部メモリ・データ構造を用いて、適切なフリー・ブロックが突き止められる。一旦ブロックが突き止められると、ボックス１１１０で、そのブロックが割当てられる。これは適切な内部メモリ・データ構造を変更し、ディスク上のヘッダ・タグを"割当て済み"とマーク付けすることにより行われる。分割が実行されない場合、割当ては単に１ディスク操作を消費するだけである。
【００４１】
図１３を参照すると、本発明の方法１に従う割当て解除が示される。適切な内部メモリ・データ構造が変更されて、ブロックを割当て解除する。更にブロック１２０５で、ディスク上のヘッダ・タグが"割当て解除"とマーク付けされる。合体が実行されない場合、割当て解除は１ディスク操作を消費するだけである。障害または正常シャットダウンの後、システムが再始動されるとき、ＤＳＡにより使用される内部メモリ・データ構造（フリー・リストなど）が、ディスク上に記憶されるヘッダを走査することにより作成される。こうしたデータは必要に応じて増分的に読出され、１度に全部が読出される必要はない。但し、１度に全部が読出されても差し支えない。
【００４２】
１実施例では、１つ以上の連続ブロックのディスク記憶域内に、複数のヘッダ・ワードを保持することにより、ディスクから情報を読出す時間が低減される。連続ブロックｂ１がフルになると、新たなブロックｂ２がｂ１に連鎖されて、追加のヘッダを含むようになる。ディスク上の連続ブロックの記憶域は、極度に不連続の情報よりも迅速に読出される。例えば、読出される１つの（または少数の）ブロックが、幾つかの連続ヘッダを読出すために使用される。たとえ読出されるブロックが使用されなくても、お互いに接近するディスク位置からの複数の読出しは、ディスク・ヘッドの小さな移動を必要とするだけであり、時間を節約する。
【００４３】
正常シャットダウン後の始動時間を改善する別の実施例では、ＤＳＡがシャットダウン直前に、主メモリ・データ構造（フリー・リストなど）を、１つ以上の連続ブロックのディスク記憶域に出力する。再始動に際して、ＤＳＡはシャットダウン直前に書込まれた記憶ブロックから、データ構造を読込む。これはヘッダから情報を獲得するよりも、かなり高速である。前述のこれらの実施例は、メモリ管理方法１に加え、後述のメモリ管理方法のためにも使用され得る。
【００４４】
図１４を参照すると、本発明に従いディスク上の永続的記憶域を管理する別のメモリ管理方法が示される。この方法は便宜上、以下では方法２またはメモリ管理方法２と呼ばれる。図１４に示されるボックスは、任意の順序で実行され得る。システムは、ディスク上のブロックの少なくとも１つのリスト（フリー・ブロック及び割当て済みブロックのいずれかまたは両方を含む）を保持する（ボックス１３０５）。リストはヘッダ内にリスト・ポインタを保つことにより保持される。割当て（ボックス１３１０）が図１２に示されるように、また前述したように発生する。メモリ管理方法２により保持される内部メモリ・データ構造は、メモリ管理方法１により使用されたものとは異なる（例えば図１５参照）。割当て解除（ブロック１３２０）が、図１３で示されるように、また前述したように発生する。
【００４５】
新たな記憶ブロックを作成することが必要かもしれない（ボックス１３１５）。これはブロックがＭＦＬＦアルゴリズムにおいて、テールから割当てられるときに発生し得る。これはブロックが分割された後にも発生し得る。新たな記憶ブロックｂが作成されるとき、そのディスク・ヘッダがボックス１３１５で初期化される。ディスク・ヘッダは、ブロックの割当て状況、ブロック・サイズ、及びリスト上の次のブロックを指し示すポインタを含む。ディスク操作を最小化するために、これらのヘッダ・フィールドが連続バイトのディスク記憶域に保持される。このように、ヘッダは単一ブロック書込みにより、またはディスク・ヘッドの移動をほとんど伴わない多重書込みにより、効率的に更新される。新たな記憶ブロックｂが、フリー・リストの先頭に追加される。リストの先頭ポインタがまた、主メモリ内に保持され得る。その場合、ポインタがｂに更新される。ディスク操作を最小化するために、リストの先頭を指し示すディスク・ポインタは、ボックス１３１５で更新されなくてもよい。これはリストの先頭を指し示すディスク・ポインタが陳腐化し得ることを意味する。これらのディスク・ポインタを更新するために、システムは周期的にチェックポイントを設定する（ボックス１３２５）。例えば、システムはｎトランザクション毎に、チェックポイントを設定する。ここでｎはシステム・パラメータである。トランザクションは、割当て、割当て解除、または他の記憶操作を含み得る。
【００４６】
或いは、システムはｍ個の新たなブロックが作成される毎に、チェックポイントを設定する。ここでｍはシステム・パラメータである。チェックポイントは一般に、正常動作の間にシステムがオフされる前に実行される。
【００４７】
ボックス１３２５のステップの間、ディスク・リスト先頭ポインタが、主メモリ内に保持されるリスト先頭ポインタから更新される。複数ディスク・リストを有するシステムでは、ディスク・リスト先頭ポインタをディスク上の連続メモリ位置に保持することが好ましく、それによりリスト先頭ポインタが、単一ブロック書込みにより、またはディスク・ヘッドの移動をほとんど伴わない多重書込みにより、効率的に更新される。
【００４８】
図１５を参照すると、ランダム・アクセス・メモリ（ＲＡＭ）とディスクとの間で、メモリ管理方法２を使用するメモリ割当ての例が示される。メモリ管理方法２は、ＭＦＬＦアルゴリズムと共に使用され得る。その場合、内部メモリ・データ構造がクイック・リスト及びｍｉｓｃリストのために保持される。内部メモリ・リストとディスク・リストとの関係は、１対１の対応である必要はない。
【００４９】
障害または正常シャットダウンの後にシステムが再始動されるとき、ＤＳＡにより使用される内部メモリ・データ構造（フリー・リスト）が、ディスク上に記憶されるヘッダを走査することにより作成される。これはメモリ管理方法１の場合のように、ブロック・サイズ及び割当て状況を調査することによるか、或いはディスク上に記憶されるリストを調査することによる。こうしたデータは必要に応じて増分的に読出され、１度に全部が読出される必要はない。但し、１度に全部が読出されても差し支えない。
【００５０】
図１５は、本発明を使用する複数の異なる記憶操作のためのメモリ管理を示す。プロセスはランダム・アクセス・メモリ１４０４とディスク１４０６との間で分割される。メモリ・ブロック１４０８は、四角形により示される。メモリ・ブロック１４０８は、サイズを表す数をブロックの最初の位置１４１０に含む。この数はブロックがフリーであれば正であり、割当て済みであれば負である。主メモリ（ＲＡＭ１４０４）のメモリ・ブロック１４０９は、例えばａ１、ａ２、ａ３...ａ５などのアドレスと一緒にリストされており、対応するブロックがディスク１４０６上に配置される。リスト先頭は、ディスク１４０６上のリスト上の最初のメモリ・ブロックの位置を指し示す。ディスク１４０８上のブロック１４０８のアドレスは、ブロック１４０８の第２の位置１４１２のアドレス・ラベルにより示される。アドレス・ラベル１４１２は説明の都合上示されており、こうしたアドレス・ラベルは必ずしもディスク上に記憶される必要はない。ブロック１４０８の最後の位置１４１４は、リスト上のメモリの次のブロックを指し示すか、またはｎｉｌまたはリスト若しくはセットの終わりを意味する"＃"である。
【００５１】
図１５の例の記憶操作が、図１４に関連して述べられる。ＲＡＭ１４０４はフリーのブロックだけを含む。ディスク上のブロックのリストの保持（ボックス１３０５）が実行される。割当て２５がボックス１３１０に従い実行される。割当て解除ａ２が、ボックス１３２０に従い実行される。割当て９０がブロック１３１５に従い実行される。ここでリスト先頭ａ１はテールからの割当てにより陳腐化し、これがディスク上のリストの先頭に移動する。ボックス１３２５に従うチェックポイントは、図１５に示されるように、リスト先頭をａ５に更新する。
【００５２】
図１６を参照すると、ディスク上の永続的記憶域を管理するメモリ管理方法３が示される。図１６に示されるボックスは、任意の順序で実行され得る。システムはボックス１５０５で、ディスク上のフリー・ブロックの少なくとも１つのリストを保持する。リストはヘッダ内にリスト・ポインタを保つことにより保持される。このリストの先頭は陳腐化し得るが、ボックス１５２０で実行されるチェックポイントの間に更新される。このリストの最新バージョンが、主メモリ内に保持される。この方法は、割当てがリストの最初のメンバから発生するとき、特に有用である。ＭＦＬＦ方法では、全てのクイック・リストからの、及び最後のｍｉｓｃリストを除く全てからの割当てが、リストの最初のメンバから発生し得る。従って、これらのリストはメモリ管理方法３に役立つものである。
【００５３】
ボックス１５１５では、ブロックがリストの先頭から割当てられる。内部メモリ・フリー・リストが更新される。更に、ブロックがディスク上で割当て済みとマーク付けされる。しかしながら、ディスク操作を減らすために、ディスク上のリスト・ポインタは陳腐化することを許可される。ボックス１５１０では、ブロックを適切なフリー・リストの先頭に追加し、内部メモリ・データ構造を更新することにより、ブロックが割当て解除される。ブロックはディスク上で割当て解除済みとマーク付けされ、そのヘッダがフリー・リスト上の次のブロックを指し示すように更新される。このディスク更新のオーバヘッドを最小化するために、割当て状況タグ及び次のリスト要素を指し示すポインタが、ディスク上で互いに接近して記憶される。リストの先頭を指し示すディスク・ポインタは、ディスク操作を減らすために、陳腐化することを許可される。
【００５４】
ディスク上のリスト先頭ポインタを更新するために、システムは周期的にボックス１５２０で、チェックポイントを設定する。例えば、システムはｎトランザクション毎に、チェックポイントを設定する。ここでｎはシステム・パラメータである。更に、チェックポイントは一般に、システムがオフする前に実行される。ボックス１５２０のステップの間に、ディスク・フリー・リスト・ポインタが、メモリ内に保持されるリスト・ポインタの先頭から更新される。複数フリー・リストを有するシステムでは、ポインタが効率的に更新されるように、ディスク・フリー・リスト・ポインタをディスク上の連続メモリ位置に保持することが好ましい。それにより、ディスク・ヘッドの僅かな移動による単一ブロック書込みまたは多重書込みが可能になる。ディスク上の１つ以上のフリー・リストが正しくないときに、システムが故障すると、こうしたフリー・リストは割当て済みのブロックを含み得る。こうしたフリー・リストは、障害後に、ボックス１５２５で修正される。
【００５５】
システムは、メモリ管理方法３により管理されるディスク上の各フリー・リストを調査し、割当て済みのブロックを除去する。システムはフリー・リストを先頭から走査し、ヘッダを調査することにより、これを実行する。システムがフリー・リスト上のフリーのブロックに遭遇すると、システムは直ちにリストの調査を停止する。なぜなら、リスト上の残りのブロックもフリーのはずだからである。
【００５６】
図１７乃至図１９を参照すると、メモリ管理方法３の例が示される。図１７乃至図１９に示されるように、メモリ管理は、本発明を使用する複数の異なる記憶操作に対して示される。プロセスは、ランダム・アクセス・メモリ１６０４とディスク１６０６との間で分割される。メモリ・ブロック１６０８は、四角形により示される。メモリ・ブロック１６０８は、サイズを表す数をブロックの最初の位置１６１０に含み、この数はブロックがフリーであれば正であり、割当て済みであれば負である。主メモリ（ＲＡＭ１６０４）のメモリ・ブロック１６１１はフリー・リスト１６０７を含み、フリー・リストは例えばサイズ"３"を有するブロックを表す指標１６０９を含む。例えばａ１、ａ２、ａ３、ａ４などのアドレスがフリー・リスト１６０７内に含まれ、対応するブロックがディスク１６０６上に配置される。ディスク１６０６上のブロック１６０８のアドレスは、ブロック１６０８の位置１６１２内のアドレス・ラベルにより示される。アドレス・ラベル１６１２は説明の都合上示されており、こうしたアドレス・ラベルは必ずしもディスク上に記憶される必要はない。ブロック１６０８の位置１６１４は、メモリの次のブロックを指し示すか、またはｎｉｌまたはリストの終わりを意味する"＃"である。
【００５７】
図１７乃至図１９の例の記憶操作が、図１６に関連して述べられる。ディスク上のブロックのリストの保持（ボックス１５０５）が実行される。割当て３及びポインタのａ１への復帰が、ボックス１５１５に従い実行される。割当て３が再度、ボックス１５１５に従い同様に実行される。割当て解除または解放ａ４が、ボックス１５１０に従い実行される。ここでアドレスａ２及びａ４を有するブロック１６０８が、ブロック・アドレスａ３を指し示すことが注目される。これはチェックポイントにより修正される。ボックス１５２０によるチェックポイントは、アドレスａ４及びａ３を有するブロックがフリー・リスト上で保持されるように、フリー・リスト１６０７を更新する。
【００５８】
図２０を参照すると、メモリ管理方法の別の実施例が示され、これは便宜上、メモリ管理方法４と呼ばれる。図２０に示されるボックスは、任意の順序で実行され得る。システムは記憶域を管理するための内部メモリ・データ構造を保持する。こうした内部メモリ・データ構造はリストを含む。ボックス１７０５で、内部メモリ・データ構造を変更することにより、割当て及び割当て解除が実行される。通常、ディスク操作はボックス１７０５では発生しない。従って、割当て及び割当て解除は高速である。システムはボックス１７１０において、周期的に、メモリへの情報をチェックする。例えば、システムはｎトランザクション毎に、チェックポイントを設定する。ここでｎはシステム・パラメータである。更に、チェックポイントは一般に、システムがオフする前に実行される。正常シャットダウンの直前に、システムは追加の情報をディスク上に記憶でき（例えば、システムがフリー・リストを使用していると仮定した場合、メモリ内のフリー・リストの構造）、これが後に始動時間を低減するために読出される。
【００５９】
こうしたチェックポイントは、システムが正常シャットダウンまたは障害の後に、再始動する事を可能にする。正常シャットダウンの直前に、システムは自身が正規のチェックポイントの間に記憶しなかったかもしれない情報をディスク上に記憶する。こうした補助情報は、後に始動時間を低減するために読込まれる。
【００６０】
異なるメモリ管理方法のトレードオフが、システム設計者が性能要求に最も好適なメモリ管理方法を選択する際に考慮される。ここで述べるメモリ管理方法は、従来技術に勝る多くの利点を提供する。メモリ管理方法１は、メモリ管理方法２及び３よりも少ないヘッダ空間を必要とする。更に、メモリ管理方法１は割当て及び割当て解除のために、メモリ管理方法２及び３よりも少ないディスク書込みを実行する。メモリ管理方法１では、ディスク上の情報が常に最新であり、チェックポイントは必要とされない。
【００６１】
メモリ管理方法２は、ディスク上での複数リストの保持を可能にし、これらのリストは、始動の間に、メモリ管理方法１よりも少ないディスク読出しにより、特定サイズのブロックを突き止めるために使用される。チェックポイントがメモリ管理方法２では使用され、ディスク上のリスト先頭は常に最新とは限らない。
【００６２】
メモリ管理方法３はフリー・リストを使用し、最善の性能を獲得するために、全ての割当てがフリー・リストの先頭から行われる。メモリ管理方法３は、始動の間に特定サイズのフリー・ブロックを突き止めるために使用され、従って、メモリ管理方法１及び２よりも少ない読出しを使用する。なぜなら、メモリ管理方法３は複数リストを使用するからである。メモリ管理方法２と異なり、メモリ管理方法３のリストは、フリー・ブロックだけを含む（正常シャットダウンを仮定した場合）。チェックポイントが使用されて、ディスク上のリストが更新される必要があり、またディスク上のリストは障害の後に修正されなければならない。
【００６３】
メモリ管理方法４はディスク操作無しに、割当て及び割当て解除を実行する。しかしながら、メモリ管理方法４は他の方法（例えばメモリ管理方法１乃至３）よりも多くのチェックポイント・プロシージャを含み得る。更に、メモリ管理方法４を使用すると、障害の際に、他の方法を使用する場合よりも、ディスク・メモリがより陳腐化し得る。
【００６４】
次に、本発明に従い記憶域を割当てる別の方法（メモリ管理方法５）について述べることにする。この方法は特に、システムが最初のフリー・バイトを指し示すポインタ（例えばテール・ポインタ）を保持及び更新することにより、記憶域をディスク・メモリの大きなブロック（例えば図５のテール）から割当てているときに有用である。
【００６５】
図２１を参照すると、システムはブロックに対するディスク上のヘッダを保持する（ボックス１８０５）。ヘッダはコード・バイトとして知られる少なくとも１バイトを含む。ここで図２１で示されるボックスは、任意の順序で実行され得る。システムはまた、現テール・ポインタ及びディスク上のテール・ポインタを示す変数を、メモリ内に保持する。ディスク上のテール・ポインタは陳腐化し得る。ボックス１８１０では、システムはテールからブロックｂ１を割当てる。このステップによりヘッダに記憶される情報には、割当てられたタグ、ブロック・サイズ、及び１つ以上のコード・バイトが含まれる。ディスク上のテール・ポインタは通常、このステップでは更新されない。その理由は、テール・ポインタはディスク上でｂ１のヘッダから離れているからである。ディスク上のテール・ポインタの更新は、余計なディスク操作を伴う必要があり得る。対照的に、ｂ１のヘッダ・バイトはディスク上で接近して維持され、従って、ヘッダの全ての更新は、一般にほとんどディスク操作を使用せずに行われる（多くの場合、１ディスク書込みで十分）。ブロックがもはやテールの一部でないことを示す特殊な情報が、コード・バイトに記憶される。他の目的で使用されるヘッダ・バイトがコード・バイトとして機能することも可能であり、これによりコード・バイトによりもたらされるオーバヘッドを低減または排除することができる。例えば、メモリ管理方法２及び３は、ブロック・サイズ及びリスト・ポインタを記憶するためにヘッダ・バイトを使用する。これらのバイトはコード・バイトとしても機能し得る。
【００６６】
（ディスク上ではなく、）メモリ内のテール・ポインタが、ボックス１８１０で更新される。ボックス１８２５では、ブロックｂ１がテールに割当て解除される。コード・バイトは、ｂ１が現在テールの一部であることを示すように変更される。ディスク上のテール・ポインタがメモリ内にキャッシュされ、従って、ディスクをアクセスすることなく調査可能である。ディスク上のテール・ポインタが最新の場合、テール・ポインタは更新され、ｂ１がテールに割当て解除された後も最新に維持される。そうでない場合、ディスク上のテール・ポインタは陳腐化を容認される。
【００６７】
更新されたテール・ポインタは、周期的にチェックポイントでチェックされる（ボックス１８２０）。例えば、システムはｎトランザクション毎に、チェックポイントを設定する。ここでｎはシステム・パラメータである。或いは、システムは、最後にディスク上のテール・ポインタが更新されてから、ｐ回目のテールの更新の後にチェックポイントを設ける。ここでｐはシステム・パラメータである。チェックポイントは一般に、システムが正常動作の間にオフされる前に実行される。
【００６８】
ディスク上のテール・ポインタを更新する犠牲は、何度かの割当て及び割当て解除に渡って償却される。本発明は、図９及び図１０に関連して述べた方法、或いはメモリ管理方法１乃至３などと共に使用され得る。メモリ管理方法２及び３と共に使用される場合、テールのチェックポイントはフリー・リストのチェックポイントと組み合わされる。例えば、ＭＦＬＦシステムが、テール・ポインタ及びフリー・リスト・ポインタのチェックポイントを必要とすると仮定する。ディスク上のテール・ポインタは、フリー・リスト・ポインタに隣接して記憶され得る。こうして、テール・ポインタとフリー・リストとが、単一ブロック書込みまたはディスク・ヘッド移動をほとんど伴わない少数の書込みを用いて、チェックポイントに掛けられる。
【００６９】
システム障害が発生する場合、ディスク上に書込まれたテール・ポインタは最新でない可能性がある。ボックス１８１５は障害後に、テール・ポインタを修正しようとする。ここでｔをテール・ポインタの記憶値とする。システムは、ｔで始まるブロックに対応するヘッダ内のコード・バイトを調査する。これらのコード・バイトがｔがブロックに対応することを示す場合、ブロック・サイズｓがヘッダから決定される。テール・ポインタがｔ＋ｓに増分され、記憶域がブロックに対応しないことが示されるまで、コード・バイトの調査プロセスが継続する。
【００７０】
ここで１例において、メモリ管理方法２が使用されていると仮定する。サイズ及びポインタ・ヘッダの両方が、コード・バイトとして使用され得る。ボックス１８１５で、有効コード・バイトのテストにより、サイズ・バイトが正当なサイズを記憶し、ポインタが適切なサイズ・クラスに属するブロックを指し示すことが確認される。図２１は、確率的リカバリ・アルゴリズムを実行する。ボックス１８１５で、テール・ポインタが不必要に進められる可能性がある。コード・バイトの適切な使用により、この可能性が任意に低く抑えられる。最悪の場合、あるテール記憶域が失われるかもしれないが、割当てられた記憶域が誤って割当て解除されることはない。
【００７１】
ＭＦＬＦアルゴリズムなどの、テール式データ構造を使用する幾つかの異なるＤＳＡと共に、図２１の方法を使用することが可能である。常にボックス１８２５を用いて、ブロックをテールに割当て解除する必要はない。例えば、ＭＦＬＦアルゴリズムは通常、最近解放されたブロックをテールに追加しない。代わりに、ＭＦＬＦアルゴリズムは、解放されたブロックをフリー・リストに追加する。記憶域は合体の間にテールに追加される。
【００７２】
図２２を参照すると、本発明者が行った、メモリ管理方法１を使用するＭＦＬＦ  ＩＩＩと、ＩＢＭから販売されるＤＢ２（商標）との性能特性のテスト結果が示される。読出し及び書込み操作は、各々が１００バイト未満のサイズの５３００項目に対して行われた。報告される時間は、初期化時間を含む。テストランは、次のものを含む。  Ａ：単純機能テストを含む全てのテストを、１実行により実行する。  Ｒ：各項目をデータベースから１度読出す（キード（keyed）・ルックアップ）。  Ｗｐ：各項目を空データベースに１度書込む（データベースを準備）。  Ｗｎ：各項目をフルのデータベースに１度書込む（準備されたデータベース内の各項目を置換する）。  Ｉ：データベース内の各項目に渡り反復を実行する（非キード・ルックアップ）。
【００７３】
初期化時間とテストＡの余分な機能テストのために、（Ｒ＋Ｗｐ＋Ｗｎ＋Ｉ）の合計は、Ａにはならない。データベースは、指標付き基本キー（ストリング）及びデータ・オブジェクト（ＬＯＢ）を有する、１つのテーブルを含む。基本テストは、全ての更新が完了した後にだけ、更新をコミットした。図２３に示されるように、補助更新が毎回の更新後に、または５回目の更新の度にコミットされた。ＤＢ２へのテストの実際の適用は、５回の更新毎にコミットされる必要があり、ＤＢ２がテストを完了するために、幾つかの調整パラメータが必要とされた。基本テスト結果が図２２に示される。テスト時間（秒）は、ＤＢ２（１９０２）に比較して、本発明の驚くべき改善（１９００）を示している。ほとんどの場合、１桁の改善が達成された。
【００７４】
図２３を参照すると、ＤＢ２は幾つかのモードで実行された。例えば、ＤＢ２へのテストの適用は、図２３に示されるように、手動コミット、自動コミット、及び５回の更新毎に行われた。Ｗｐ及びＷｎテストにおける本発明の動作時間（秒）は、１桁以上も大きく、時には２桁以上も大きかった。
【００７５】
本発明には当業者により達成されるであろう多くの変形が存在する。例えば、ＤＳＡは複数のトランザクションを同時に処理するように並列化され得る。これはディスク・アレイと併用するのに適している。並列化を達成する技術については、次の参考文献で述べられている。  １）"Dynamic  Storage  Allocation  on  a  Multiprocessor"、Arun  Iyengar、Massachusetts  Institute  of  Technology  Laboratory  for  Computer  Science  TR-560  (PhD  Thesis)、December。  ２）"Scalability  of  Dynamic  Storage  Allocation  Algorithm"、Arun  Iyengar、in  Proceedings  of  IEEE  Frontiers  '96、October  1996。
【００７６】
以上、永続的且つロバストな記憶割当てのためのシステム及び方法の実施例について述べてきたが、当業者であれば前記の教示を鑑み、本発明の趣旨及び範囲内において、多くの変更及び変形が実施できよう。本発明はこれらの変更及び変形も網羅するものである。
【００７７】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００７８】
（１）  連続する永続的メモリのブロックを管理する方法であって、メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、前記主メモリ内の前記第１のポインタを更新することにより、前記第１のブロックから前記第２のブロックを割当てるステップとを含む方法。
【００７９】
（２）  ブロックｂを前記第１のブロックに追加するステップを含み、前記追加ステップが、ｂに対応するコード・バイトを、ｂが前記第１のブロックの一部であることを示すように変更するステップと、前記主メモリ内の前記第１のポインタを更新するステップとを含む、（１）記載の方法。
【００８０】
（３）  前記少なくとも１コード・バイトが、前記第２のブロックがもはや前記第１のブロックの一部でないことを示す以外に、他の機能にも作用する、（１）記載の方法。
【００８１】
（４）  前記主メモリ内の前記第１のポインタの値にもとづき、前記永続的メモリ内の第２のポインタを周期的に更新するステップを含む、（１）記載の方法。
【００８２】
（５）  システム障害に応答して、前記少なくとも１コード・バイトを調査することにより、前記第１及び第２のポインタを更新するステップを含む、（４）記載の方法。
【００８３】
（６）  前記ヘッダが単一ブロック書込みを用いて初期化される、（１）記載の方法。
【００８４】
（７）  連続する永続的メモリのブロックを管理する方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置であって、前記方法が、メモリの第１のブロック内の最初のフリー・バイトを決定する第１のポインタを主メモリ内に保持するステップと、複数のブロックに対する、少なくとも１コード・バイトを含むヘッダを永続的記憶域内に保持するステップと、第２のブロックに対して、第２のブロックがもはや第１のブロックの一部でないことを示す少なくとも１コード・バイトをセットし、前記主メモリ内の前記第１のポインタを更新することにより、前記第１のブロックから前記第２のブロックを割当てるステップとを含むプログラム記憶装置。
【００８５】
（８）  ブロックｂを前記第１のブロックに追加するステップを含み、前記追加ステップが、ｂに対応するコード・バイトを、ｂが前記第１のブロックの一部であることを示すように変更するステップと、前記主メモリ内の前記第１のポインタを更新するステップとを含む、（７）記載のプログラム記憶装置。
【００８６】
（９）  前記少なくとも１コード・バイトが、前記第２のブロックがもはや前記第１のブロックの一部でないことを示す以外に、他の機能にも作用する、（７）記載のプログラム記憶装置。
【００８７】
（１０）  前記主メモリ内の前記第１のポインタの値にもとづき、前記永続的メモリ内の第２のポインタを周期的に更新するステップを含む、（７）記載のプログラム記憶装置。
【００８８】
（１１）  システム障害に応答して、前記少なくとも１コード・バイトを調査することにより、前記第１及び第２のポインタを更新するステップを含む、（１０）記載のプログラム記憶装置。
【００８９】
（１２）  前記ヘッダが単一ブロック書込みを用いて初期化される、（７）記載のプログラム記憶装置。
【００９０】
（１３）  永久記憶域内の隣接するフリー・ブロックを合体するステップであって、ブロックのサイズ及び割当て状況を示すヘッダを、各ブロックに対して保持するステップと、ヘッダ情報を調査して、隣接フリー・ブロックを結合することにより、フリー・ブロックを合体するステップと、達成される合体のレベルを示す情報を前記永久記憶域内に周期的に記憶するステップとからなるフリー・ブロックを合体するステップを含む（１）の方法。
【００９１】
（１４）  （１３）記載の方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置。
【００９２】
（１５）  合体の間のシステム障害に応答して、前記永久記憶域内の情報を読出し、システム障害の前に達成された合体のレベルを決定するステップと、前記永久記憶域内の情報にもとづき、ある時点で合体を再開するステップとを前記フリー・ブロックを合体するステップに含む、（１３）記載の方法。
【００９３】
（１６）  （１５）記載の方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置。
【００９４】
また、本発明は以下の方法、及びプログラム記憶装置を併せて使用することが可能である。
【００９５】
（１）  コンピュータ・メモリを管理する方法であって、メモリのフリー・ブロックの複数のセットを保持し、前記フリー・ブロックが該フリー・ブロックのサイズにもとづき、前記セットに追加されるステップと、第１のしきい値を越える要求サイズのフリー・ブロックに対する要求に応じて、少なくとも前記要求サイズと同じ大きさの、但し前記要求サイズに第２のしきい値を加えたよりも小さいフリー・ブロックのセットを探索するステップと、フリー・ブロックが見いだされると、該フリー・ブロック全体を割当てるステップとを含む、方法。
【００９６】
（２）  前記フリー・ブロックの複数セットを保持するステップが、前記フリー・ブロックの複数セットをディスク上に保持するステップを含む、（１）記載の方法。
【００９７】
（３）  前記フリー・ブロックの複数セットを保持するステップが、前記フリー・ブロックの複数セットを主メモリ内に保持するステップを含む、（１）記載の方法。
【００９８】
（４）  フリー・ブロックが見いだされないが、前記要求サイズと少なくとも同じ大きさの少なくとも１つのブロックが見いだされる場合、当該少なくとも１つのブロックを分割するステップと、分割ステップから生じる第２のブロックにより前記要求を満足するステップとを含む、（１）記載の方法。
【００９９】
（５）  分割される少なくとも１つのブロックが、前記要求サイズよりも大きい、見いだされる最小のブロックである、（４）記載の方法。
【０１００】
（６）  前記複数セットが最大ブロックのセットを含み、前記第１のしきい値が、前記最大ブロックのセットに対して許可される最小ブロック・サイズよりも大きいか等しく、前記要求を満足する最大ブロックのセットを探索するステップを含む、（１）記載の方法。
【０１０１】
（７）  前記探索ステップが、リストを含むセットを探索するステップを含み、前記リストが前記セットのメモリ・ブロック割当て情報を含む、（１）記載の方法。
【０１０２】
（８）  前記第１及び第２のしきい値の少なくとも１つを動的に調整して、性能を動的に調整するステップを含む、（１）記載の方法。
【０１０３】
（９）  メモリの連続ブロックを維持するステップと、前記要求サイズにもとづき、フリー・ブロックのセットを選択するステップと、前記フリー・ブロックのセットが空でないことに応じて、前記セット内で突き止められる最初のブロックの少なくとも一部を割当てるステップと、前記セットが空であることに応じて、前記要求をメモリの前記連続ブロックから満足するステップとを含む、（１）記載の方法。
【０１０４】
（１０）  第１のポインタ位置として、ポインタを前記連続ブロックを指し示すように維持するステップと、所与のサイズの記憶域に対する要求に応じて、前記ポインタを所与のサイズ増分して、第２のポインタ位置を指し示すステップと、前記第１のポインタ位置から始まる前記連続ブロックの一部を用いて、前記要求を満足するステップとを含む、（９）記載の方法。
【０１０５】
（１１）  割当てられたブロックを、当該ブロックのサイズにもとづき、フリー・ブロックの新たなセットに割当て解除するステップを含む、（１）記載の方法。
【０１０６】
（１２）  コンピュータ・メモリを管理する方法を実行する、マシンにより実行可能な命令のプログラムを有する、マシンにより読取り可能なプログラム記憶装置であって、前記方法が、メモリのフリー・ブロックの複数のセットを保持するステップであって、前記フリー・ブロックがサイズにもとづき、前記セットに追加され、第１のしきい値を越える要求サイズのフリー・ブロックに対する要求に応じて、少なくとも前記要求サイズと同じ大きさの、但し前記要求サイズに第２のしきい値を加えたよりも小さいフリー・ブロックのセットを探索するステップと、フリー・ブロックが見いだされると、該フリー・ブロック全体を割当てるステップとを含む、プログラム記憶装置。
【０１０７】
（１３）  前記フリー・ブロックの複数セットを保持するステップが、前記フリー・ブロックの複数セットをディスク上に保持するステップを含む、（１２）記載のプログラム記憶装置。
【０１０８】
（１４）  前記フリー・ブロックの複数セットを保持するステップが、前記フリー・ブロックの複数セットを主メモリ内に保持するステップを含む、（１２）記載のプログラム記憶装置。
【０１０９】
（１５）  フリー・ブロックが見いだされないが、前記要求サイズと少なくとも同じ大きさの少なくとも１つのブロックが見いだされる場合、当該少なくとも１つのブロックを分割するステップと、分割ステップから生じる第２のブロックにより前記要求を満足するステップとを含む、（１２）記載のプログラム記憶装置。
【０１１０】
（１６）  分割される少なくとも１つのブロックが、前記要求サイズよりも大きい、見いだされる最小のブロックである、（１５）記載のプログラム記憶装置。
【０１１１】
（１７）  前記複数セットが最大ブロックのセットを含み、前記第１のしきい値が、前記最大ブロックのセットに対して許可される最小ブロック・サイズよりも大きいか等しく、前記要求を満足する最大ブロックのセットを探索するステップを含む、（１２）記載のプログラム記憶装置。
【０１１２】
（１８）  前記探索ステップが、リストを含むセットを探索するステップを含み、前記リストが前記セットのメモリ・ブロック割当て情報を含む、（１２）記載のプログラム記憶装置。
【０１１３】
（１９）  前記第１及び第２のしきい値の少なくとも１つを動的に調整して、性能を動的に調整するステップを含む、（１２）記載のプログラム記憶装置。
【０１１４】
（２０）  メモリの連続ブロックを維持するステップと、前記要求サイズにもとづき、フリー・ブロックのセットを選択するステップと、前記フリー・ブロックのセットが空でないことに応じて、前記セット内で突き止められる最初のブロックの少なくとも一部を割当てるステップと、前記セットが空であることに応じて、前記要求をメモリの前記連続ブロックから満足するステップとを含む、（１２）記載のプログラム記憶装置。
【０１１５】
（２１）  第１のポインタ位置として、ポインタを前記連続ブロックを指し示すように維持するステップと、所与のサイズの記憶域に対する要求に応じて、前記ポインタを所与のサイズ増分して、第２のポインタ位置を指し示すステップと、前記第１のポインタ位置から始まる前記連続ブロックの一部を用いて、前記要求を満足するステップとを含む、（２０）記載のプログラム記憶装置。
【０１１６】
（２２）  割当てられたブロックを、当該ブロックのサイズにもとづき、フリー・ブロックの新たなセットに割当て解除するステップを含む、（１２）記載のプログラム記憶装置。
【図面の簡単な説明】
【０１１７】
【図１】最初のフィット割当て及び最善のフィット割当てを示す図である。
【図２】従来技術に従うバイナリ・バディ・システムを示す図である。
【図３】メモリ・ブロックの即時合体を示す図である。
【図４】メモリ・ブロックの遅延合体を示す図である。
【図５】従来技術に従う多重フリー・リスト・フィッティングの特殊なケースとしての、クイック・フィットの例を示す図である。
【図６】従来技術に従う多重フリー・リスト・フィッティング（ＭＦＬＦ  Ｉ）の例を示す図である。
【図７】従来技術に従うＭＦＬＦ  Ｉを用いて、大ブロックの割当てを行う前のスナップショットを示す図である。
【図８】従来技術に従うＭＦＬＦ  Ｉを用いて、大ブロックの割当てを行った後のスナップショットを示す図である。
【図９】本発明に従う多重フリー・リスト・フィット割当て（ＭＦＬＦ  ＩＩＩ）を示すブロック／フロー図である。
【図１０】本発明に従う大ブロックに対する多重フリー・リスト・フィット（ＭＦＬＦ  ＩＩＩ）割当てを示すブロック／フロー図である。
【図１１】本発明に従う隣接フリー・ブロックの合体を示すブロック／フロー図である。
【図１２】本発明に従うメモリ管理方法１を用いる割当てを示すブロック／フロー図である。
【図１３】本発明に従うメモリ管理方法１を用いる割当て解除を示すブロック／フロー図である。
【図１４】本発明に従うメモリ管理方法２を示すブロック／フロー図である。
【図１５】本発明に従うメモリ管理方法２の実施例である。
【図１６】本発明に従うメモリ管理方法３を示すブロック／フロー図である。
【図１７】本発明に従うメモリ管理方法３の実施例である。
【図１８】本発明に従うメモリ管理方法３の実施例である。
【図１９】本発明に従うメモリ管理方法３の実施例である。
【図２０】本発明に従うメモリ管理方法４を示すブロック／フロー図である。
【図２１】本発明に従うテール割当て及び割当て解除の管理のブロック／フロー図である。
【図２２】従来技術に対する本発明の１実施例のテスト結果のプロット図である。
【図２３】従来技術に対する本発明の１実施例のテスト結果の別のプロット図である。
【符号の説明】
【０１１８】
１３、１４０８、１４０９、１６０８、１６１１  メモリ・ブロック
１６０７  フリー・リスト
１６０９  指標
１６１２  アドレス・ラベル
【図１】
2004206733.tif 000003
【図２】
2004206733.tif 000004
【図３】
2004206733.tif 000005
【図４】
2004206733.tif 000006
【図５】
2004206733.tif 000007
【図６】
2004206733.tif 000008
【図７】
2004206733.tif 000009
【図８】
2004206733.tif 000010
【図９】
2004206733.tif 000011
【図１０】
2004206733.tif 000012
【図１１】
2004206733.tif 000013
【図１２】
2004206733.tif 000014
【図１３】
2004206733.tif 000015
【図１４】
2004206733.tif 000016
【図１５】
2004206733.tif 000017
【図１６】
2004206733.tif 000018
【図１７】
2004206733.tif 000019
【図１８】
2004206733.tif 000020
【図１９】
2004206733.tif 000021
【図２０】
2004206733.tif 000022
【図２１】
2004206733.tif 000023
【図２２】
2004206733.tif 000024
【図２３】
2004206733.tif 000025