JP5142995B2 - メモリページ管理 - Google Patents

Description

発明の詳細な説明

発明の背景
本発明はメモリページの管理に関する。

揮発性メモリ格納（例えば、ランダムアクセスメモリ（ＲＡＭ））を用いて、不揮発性メモリ格納（例えば、一つ以上のディスクドライブ）にも格納されているデータと連携をとることは有用である。例えば、揮発性メモリ格納は、普通は不揮発性メモリ格納よりアクセスおよび読み出し時間が高速である。揮発性メモリ格納および不揮発性メモリ格納のアドレス空間は、所定数の連続するアドレス配置にまたがるページに編成することができる。コンピュータシステムは、ページング技法を用いて、例えば、プログラミングまたはデータ構造が使用する揮発性メモリからメモリページを割り当てる。不揮発性メモリ格納は、普通は揮発性メモリ格納よりずっと規模が大きい。仮想メモリ方式を用いて、使用していない（例えば、現在、書き込みも読み出しもしていない）揮発性メモリ格納内のページを不揮発性メモリ格納へ書き込んでおいて、後で必要な時に、不揮発性メモリ格納から再度読み出すことができる。したがって、揮発性メモリ格納内のページは、各種のプログラミングおよび／またはデータ構造による使用のために「リサイクル（再使用）」される。ページを前後しての移動と関係付けられるオーバーヘッドを低減するために、技法によっては、最長時間未使用（ＬＲＵ）方式に基づいてページをリサイクルする。ＬＲＵ方式では、不揮発性メモリ格納へ書き込まれたページが揮発性メモリ格納への移動対象であるにもかかわらず、揮発性メモリ格納内に空きページがない場合、揮発性メモリ格納から不揮発性メモリ格納へリサイクル（つまり、スワッピングまたはページアウト）するように選択されるページは、未使用時間が最長の（例えば、最も長い時間、読み出しまたは書き込みがなされていない）ページである。

発明の概要
一般的な態様において、本発明は、シーケンシャルアクセスされる一つ以上のデータ構造のために用いられるメモリをページングするための方法、ならびにそれに対応するソフトウエアおよびシステムを特徴とする。本方法は、メモリページの再使用順序を表すデータ構造を提供するステップ、およびシーケンシャルアクセスされるデータ構造の一つと関係付けられた、メモリページへのアクセス履歴に基づいて、データ構造を維持するステップを含み、よって、その順序におけるメモリページの位置を、メモリページからのシーケンシャルアクセスの移行に依存させる。

この態様は、以下の特徴の一つ以上を含む：
メモリページからのシーケンシャルアクセスの移行は、メモリページからのポインタの移行に対応する。
その順序におけるメモリページの位置は、シーケンシャルアクセスの移行が、メモリページからの書き込みアクセスの移行に対応するかどうかに依存する。
シーケンシャルアクセスされるデータ構造の一つと関係付けられた、メモリページへのアクセス履歴に基づくデータ構造を維持するステップが、メモリページからの書き込みアクセスの移行に応じて、順序を表すデータ構造の第１エンドに、メモリページ用の識別子を配置するステップと、閉じられているメモリページと関係付けられる、シーケンシャルアクセスされるデータ構造に応じて、順序を表すデータ構造の第２エンドに、メモリページ用の識別子を配置するステップとを含む。

本方法は、順序を表すデータ構造の第１エンドからのメモリページを再使用するステップをさらに含む。

本方法は、空きメモリページリストが空であることを判定した後、データ構造の第１エンドからの前記メモリページを再使用するステップをさらに含む。

メモリページを再使用するステップは、メモリページの現在のコンテンツを不揮発性メモリ格納へ書き込むステップを含む。

メモリページを再使用するステップは、不揮発性メモリ格納からのメモリページをメモリページへ書き込むステップをさらに含む。

メモリページと関係付けられる、シーケンシャルアクセスされるデータ構造は、待ち行列を含む。

一般的な態様において、本発明は、シーケンシャルアクセスされる一つ以上のデータ構造のために用いられるメモリをページングするための方法、ならびにそれに対応するソフトウエアおよびシステムを特徴とし、第１のケースでは最長時間使用方式に基づき、第２のケースでは最長時間未使用方式に基づいて、シーケンシャルアクセスされるデータ構造に関係付けられるメモリページを再使用するステップを含む。

本態様は以下の特徴の一つ以上を含むことができる：
第１のケースは、メモリページからの書き込みポインタの移行を含む。
第２のケースは、シーケンシャルアクセスされるデータ構造を閉じるアクセスエンティティを含む。
第２のケースは、メモリページからの読み出しポインタの移行を含む。

本発明の態様は、以下の利点の一つ以上を含むことができる：
再使用のためのページを順序付けるステップは、待ち行列または他のシーケンシャルＩ／Ｏデータ構造を格納するメモリシステムに対して、どのページがすぐに再使用される可能性があるのか、より良好な予測を提供できる。書き込まれたばかりの（すなわち、書き込みポインタがページを去ったばかりの）ページは、読み出しポインタが書き込みポインタに「追いつかなければ」ならないので、すぐに再使用される可能性が少ない。したがって、これらのページは、最初にリサイクルされる。さらに、閉じたばかりの待ち行列に対するページは、すぐに再オープンされて、再使用されるかもしれないので、後までリサイクルされない。しばらく閉じたままのページはその間にどこかにリサイクルされる。

待ち行列特有のページングアルゴリズムの使用は、待ち行列構造またはアクセスパターンを利用しないページングアルゴリズムの使用を超える高い効率を提供できる。データ格納待ち行列のページングは、どのページが再使用されるかを決定する際に、待ち行列アクセス履歴を利用することにより改良できる。例えば、アクセス履歴に基づいて、幾つかのページは他のページより早く再アクセスされる、と予測することができる。この改良により、作業している記憶装置内に必要なページが存在する可能性がより高くなるので、作業中の記憶装置へデータを転送して戻すことに起因する遅延を低減できる。

本発明の他の特徴および利点は、以下の説明および特許請求の範囲から明らかになろう。

詳細な説明
図１を参照すると、待ち行列システム１００により、アクセスエンティティ１０２Ａ〜１０２Ｐは、１セット以上の待ち行列QUEUE_1〜QUEUE_Nへメッセージを追加し、待ち行列からメッセージを読み出すことができる。アクセスエンティティは待ち行列マネージャ１０２を介してシステム１００と相互作用する。待ち行列マネージャ１０２はメモリ管理モジュール（ＭＭＭ）１０６を用いて、データ読み書きのアクセスが相対的に高速な一時的作業記憶装置である揮発性メモリ格納１０８と、データの永続性が相対的に高い恒久的記憶装置であって揮発性格納より読み書きのアクセスが相対的に低速な不揮発性メモリ１１０との間で、ページのスワッピングを支援する。ＭＭＭ１０６は、ソフトウエアまたはハードウエアまたはその両方で実装できる。ＭＭＭは、揮発性メモリアドレス空間と不揮発性メモリアドレス空間との間のページアドレスを翻訳する。ＭＭＭは揮発性メモリへのページ参照の監視も行い、利用不可のページ（例えば、揮発性メモリページが不揮発性メモリへ書き込まれた後、新規使用のためにリサイクルされたページ）への参照を検出できる。ＭＭＭは、この「ページフォールト」について、待ち行列マネージャ１０２に警告することにより応答する。次いで、待ち行列マネージャ１０２は、参照されたページを不揮発性メモリから読み出し、揮発性メモリの空きページ内へそのページをコピーする。揮発性メモリに空きページがない場合、待ち行列マネージャ１０２は、後で詳細に説明するように、「リサイクルリスト」に基づいてページをリサイクルする。待ち行列マネージャ１０２およびＭＭＭ１０６は、任意の種類のオペレーティングシステムおよびコンピュータ環境で実装できる。待ち行列マネージャおよび／またはＭＭＭ１０６は、オペレーティングシステム内へ統合できる。代替として、オペレーティングシステムは、待ち行列マネージャ１０２へ割り当てられないページを管理するための、別の仮想メモリシステムを有してもよい。

所与の待ち行列（例えばQUEUE_2）は一連の記録を格納でき、一セットの「待ち行列ページ」内に、シーケンシャル待ち行列メッセージおよびこれらのメッセージの管理に関連する記録を含む。メッセージおよび待ち行列ページの相対的なサイズに応じて、待ち行列ページは一つ以上のメッセージ、または一つのメッセージの一部を保持できる。待ち行列マネージャ１０２は、一セットの待ち行列ページに待ち行列を割り当て、待ち行列が成長すると、そのセットへページを追加できる。図示の実施の形態では、セット内の待ち行列ページは全て不揮発性メモリ格納１１０内に格納され、アクティブな待ち行列ページのサブセットは揮発性メモリ格納１０８内に格納される。

待ち行列（または他のシーケンシャルアクセスされるデータ構造）の「シーケンシャル」状況は、メッセージ（またはデータ構造の他の要素）の論理的順序を参照する。メッセージの格納配置は、必ずしも、システム１００の物理的または仮想的なアドレス空間内のシーケンシャルアドレスにある必要はない。

揮発性メモリ格納１０８内の待ち行列ページのコンテンツが変更された場合、その待ち行列ページは「ダーティ」とマーキングされる。ダーティ待ち行列ページが揮発性メモリ格納１０８から削除された場合、不揮発性メモリ格納１１０内の待ち行列ページの古いコピーは、その変更により更新される（すなわち、待ち行列ページは、不揮発性メモリ格納１１０へ「同期」される）。ダーティ待ち行列ページは、待ち行列ページが揮発性メモリ格納１０８から削除される前に、不揮発性メモリ格納１１０に同期させることもできる。待ち行列マネージャは、待ち行列が待ち行列ページをもはや必要としなくなった後（例えば、待ち行列が削除された後）、待ち行列に対する幾つかのまたは全ての待ち行列ページを回収する。

図２Ａを参照すると、リサイクルリスト２００は、リサイクルされる可能性がある揮発性メモリ内のページを識別する。リサイクルリスト２００は、第１の「ヘッド」エンド２０２および第２の「テール」エンド２０４を有する。ページは、後述するように、テールまたはヘッドエンドのどちらかに追加することができ、ヘッドエンド２０２から削除される。リサイクルリストは、例えば、二重リンクされたリストとして実装できる。

一実施の形態では、リサイクルリスト２００は、ページテーブル２０６内の待ち行列ページを識別する「仮想アドレス」を格納する（例えば、QUEUE_1へ割り当てられた待ち行列ページ「５」を識別する「Q1/P5」）。ページテーブル２０６は、待ち行列システム１００内の待ち行列へ割り当てられる待ち行列ページそれぞれに対するエントリを含む。図では、ページテーブル２０６は、それぞれのエントリに対して、不揮発性メモリ空間２０８内に不揮発性メモリページアドレス「N-PAGE」を含み、揮発性メモリ空間２１０内に揮発性メモリページアドレス「V-PAGE」を含む。揮発性メモリページアドレスは、揮発性メモリ格納１０８内に格納されない待ち行列ページに対しては空（例えば、未使用アドレス値と一致）であってもよい。ページテーブル２０６は、待ち行列ページがリサイクルリスト２００内にあるかどうかを指示する「リサイクルビット」を含む。ページテーブルは、幾つのアクセスエンティティが待ち行列ページにアクセスしているかを示す「参照カウント」を含む。

各待ち行列は、不揮発性メモリ格納１１０内に格納される割り当て待ち行列ページセットを有する（例えば、図３Ｂで、QUEUE_2は、アドレスN-PAGE_10〜N-PAGE_16に格納されるページQ2/P1〜Q2/P7を有する）。待ち行列ページによっては、揮発性および不揮発性メモリの両方にコピーを持つことができる（例えば、図３Ａおよび３ＢのページQ2/P3〜Q2/P7）。揮発性メモリ格納１０８内に格納される待ち行列ページに対しては、ページテーブル２０６は、「ダーティビット」を用いて、まだ不揮発性メモリ格納１１０へ戻して同期していない、待ち行列ページのコンテンツへ変更があるかどうかを示す。

例えば、待ち行列へ新規に追加されたメッセージは、単に揮発性メモリ内に格納されているだけとしてもよい。関係する待ち行列メッセージを格納する待ち行列ページは、待ち行列ページが揮発性メモリから不揮発性メモリへコミット操作で同期されるので、揮発性および不揮発性メモリの両方に格納されていてもよい。（幾つかの方式の何れかを用いて、関係するメッセージを同期させることでメッセージが失われないようにすることができる。メッセージを確実にする一手法は、引用して本明細書に組み込まれる同時係属／同時出願の「メッセージ待ち行列管理」に記載されている）。待ち行列ページを格納する揮発性メモリのページは、不揮発性メモリ内のコピーだけを残して、リサイクルしてしまってもよい（例えば、別の待ち行列が使用するために）。

一つ以上のアクセスエンティティは、読み出しおよび／または書き込みのために待ち行列を開くことができる。アクセスエンティティは、待ち行列を開いて、待ち行列の最後に一つ以上のメッセージを追加することができる。アクセスエンティティは、待ち行列を開いて、待ち行列の前から、または待ち行列内の特定の場所（例えば、以前に待ち行列から読み出した時に到達した場所）から、関係するメッセージを読み出すことができる。アクセスエンティティによるアクセスに対して待ち行列が開かれると、待ち行列システム１００は、アクセスエンティティに対して読み出しおよび／または書き込みポインタを設定する等の、開くための作業を実行する。アクセスエンティティが待ち行列へのアクセス終了後、アクセスエンティティは待ち行列を閉じ、待ち行列システム１００は、閉じるための適切な作業を実行する。多数のアクセスエンティティが、同一待ち行列へ同時にアクセスできる。したがって、待ち行列は、幾つかのアクセスエンティティのアクセスに対して開くことができ、他のアクセスエンティティに対して閉じることができる。

アクセスエンティティが待ち行列を開くと、アクセスエンティティは、アクセスされている待ち行列ページに対する参照カウントをインクリメントする。アクセス対象である待ち行列ページが既に揮発性メモリ格納１０８内にない場合、その待ち行列ページは、不揮発性メモリ格納１１０から、揮発性メモリ格納１０８へコピーされる。アクセスエンティティが待ち行列ページへのアクセスを終了した後（例えば、待ち行列を閉じた後または待ち行列ページの最後を越えて書き込んだ後）、アクセスエンティティは、その待ち行列ページに対する参照カウントをデクリメントする。

待ち行列システム１００は、アクセスエンティティが読み出しポインタでデータを読み出している場所、およびアクセスエンティティが書き込みポインタでデータを追加（すなわち書き込み）している場所のトラックを保持する。アクセスエンティティが待ち行列から読み出し、またはそれへ書き込んでいる間、アクセスされている待ち行列ページは、揮発性メモリ格納１０８内にある。待ち行列システム１００は、空きリスト２１２により利用可能な揮発性メモリページのトラックを保持する。新規待ち行列ページが不揮発性メモリ格納１１０から揮発性メモリ格納１０８へコピーされる対象であるのに、空きページがない場合（すなわち、空きリストが空の場合）、待ち行列システム１００は、リサイクルリスト２００に基づいて揮発性メモリページをリサイクルする。

揮発性メモリページをリサイクルするには、待ち行列システム１００が、リサイクルリスト２００のヘッド２０２で識別されるページをチェックすることにより、リサイクルするページを探す。識別されたページが、所定の基準によりリサイクル可能なページとして適格である場合（例えば、読み出しまたは書き込みポインタが現在参照していないことを示す参照カウントゼロをそのページが有する）、そのページの現在のコンテンツは、（必要なら）不揮発性メモリ格納１１０へ書き込まれ、そのページは割り当てが自由になる（次いで、リサイクルリスト２００から削除される）。そのページの現在のコンテンツが、既に不揮発性メモリに同期している場合、待ち行列システム１００は、不揮発性メモリへの書き込みをせずにページを開放する。識別されたページが、リサイクル可能なページとして不適格である場合、そのページはリサイクルリストから削除され、リサイクルリストの新規ヘッド２０２が、リサイクル可能ページに対するチェックを受ける。

一実施では、待ち行列システム１００が、リサイクルリスト２００へ揮発性メモリページを追加する（すなわち、そのページは、開放される可能性のある候補となる）のには、２つのケースがある。
ケース１：書き込みポインタがページから移動し、他の読み出しまたは書き込みポインタがどれもそのページを指し示さず、そのページは既にリサイクルリスト２００上にない。
ケース２：ページを使用している待ち行列が閉じられ、他の読み出しまたは書き込みポインタがどれもそのページを指し示さず、そのページは既にリサイクルリスト２００上にない。

ケース１は、例えば、待ち行列に一連のメッセージを追加しているアクセスエンティティが、メッセージで待ち行列ページを埋める場合に生じる可能性がある。ケース１では、待ち行列システム１００は、リサイクルリスト２００のヘッド２０２へそのページを追加する。このケースは、より新しく書き込まれたページが、それより前に書き込まれたページの前にリサイクルされるので、最長時間使用（ＭＲＵ）方式に対応する。

ケース２では、待ち行列システム１００は、リサイクルリスト２００のテール２０４へそのページを追加する。このケースは、ページがリサイクルリストの先頭から用いられ、それにより、古い閉じられたページが、より新しい閉じられたページの前にリサイクルされるので、最長時間未使用（ＬＲＵ）方式に対応する。

他の実施では、ページをリサイクルリスト２００へ追加するために他のケースを含めることができる。例えば、ページをリサイクルリスト２００のテール２０４へ追加することができる別のケースは：
ケース３：読み出しポインタがページから移動し、他の読み出しまたは書き込みポインタがどれもそのページを指し示さず、そのページは既にリサイクルリスト２００上にない。

他の実施は、各ページへのアクセス履歴に基づいて、リサイクルリスト内でページ順序を維持するための多様な規則のどれかを含むことができる。メモリページからのシーケンシャルアクセスの移行（例えば、ページから移動する書き込みポインタ）に依存するよう、メモリページの少なくとも幾つかの位置を順序よく編成することにより、本システムは、シーケンシャルアクセスされるデータ構造の統計的特性を利用して、ページングの効率を高めることができる。

空きリスト２１２内のページは、もはや必要ではない、したがって、待ち行列ページと関係付けられないページに対応する。待ち行列システム１００がページを空きリスト２１２へ追加するケースは様々である。あるケースでは、システム１００は、リーダー（読み出し者）として待ち行列へ申し込んでいる、全てのアクセスエンティティにより読み出された（すなわち、全ての申し込み者の読み出しポインタが、ページ上の各メッセージを処理してしまい、そのページから去ってしまった）待ち行列メッセージを保持するページを開放する。待ち行列システム１００は、何らかの様々な他の理由でページを開放できる。例えば、ページ上のメッセージ全てが、削除されるかまたは「片づけられた」場合、ページが開放される。

実施によっては、ページは時間制限に基づいて開放される。例えば、ページは、ページと関係付けられる待ち行列が、所定時間（例えば２分間）を越えて閉じていた後に、開放される。別のケースでは、ページは、関係する待ち行列が開いていても、所定時間（例えば１０分間）を越えてアクセスされなかった後は開放される。

さらに、待ち行列マネージャ１０２は、他のプログラムまたはデータ構造が使用する揮発性メモリページを開放して、待ち行列システム１００が待ち行列ページを割り当てるために使用できる。待ち行列システム１００は、全ての揮発性メモリページを開放するために用いることもできるグローバルフリーリスト２１２を用いることができ、さもなければ代替として、待ち行列ページに用いる揮発性メモリページに対してセパレートフリーリスト２１２を用いることができる。

図２Ｂに示すのは、仮想アドレスに基づいてシーケンシャルに並べたQUEUE_1に対するページQ1/P1〜Q1/P8のセットの実施例である。本実施例では、一つの書き込みアクセスエンティティが、一連のメッセージを待ち行列に書き込んでいて、二つの読み出しアクセスエンティティが、利用可能になった時にメッセージを読み出している。書き込みアクセスエンティティは、シーケンシャルに増加する仮想アドレスで、ページ上にメッセージを書き込む書き込みポインタWRITER_1を有する。書き込みポインタWRITER_1がページQ1/P7からページQ1/P8へ移動した後、ページQ1/P7は、ケース１のもとでリサイクルリスト２００のヘッド２０２上に配置可能となる。読み出しポインタREADER_2がページQ1/P2からページQ1/P3へ移動した後、ページQ1/P2は、ケース３のもとでリサイクルリスト２００のテール２０４上に配置可能となる。

第１の読み出しアクセスエンティティは読み出しポインタREADER_1を有し、このポインタが、書き込みポインタWRITER_1を何ページかの待ち行列ページ分だけ遅延させる。この遅延は、そのアクセスエンティティが待ち行列システム１００と相互作用する時に短くなったり長くなったりする。第２の読み出しアクセスエンティティは、同様に、書き込みポインタWRITER_1を遅延させる読み出しポインタREADER_2を有する。空きページがライターにとって利用可能なままである場合、リーダーは、揮発性メモリ格納１０８から、書き込まれたページにアクセスできる。空きページを利用できない場合（例えば、揮発性メモリ空間が、リーダーによる大きな遅延が原因で一杯になっている場合）、書き込まれたページの幾つかをリサイクルできるかもしれない。例えば、このページ管理方式のもとでは、最新使用ページが繰り返しリサイクルされることになり、揮発性メモリ内には、遅れているリーダーが利用可能な最長時間未使用ページのシーケンスが残される。

QUEUE_1を閉じた後、リサイクルリスト２００上に既にない待ち行列ページはどれも、リサイクルリスト２００のテール２０４上に配置可能となる。テール２０４上に配置される最新の閉じた待ち行列に対するこのような待ち行列ページはどれも、テール２０４からヘッド２０２まで、そのページがリサイクルリスト２００を上方「スクロール」するまで、別のアクセスエンティティによるアクセスに対して揮発性メモリ格納１０８内に利用可能なまま残る。

図３Ａは、揮発性メモリ格納１０８に対するメモリアドレス空間２１０内の待ち行列ページの実施例を示す。ページアドレスV-PAGE_1〜V-PAGE_2は空なので、図３Ｄに示す空きリスト２１２内に含まれる。アドレスV-PAGE_3〜V-PAGE_7を用いて、QUEUE_2の待ち行列ページを格納する。読み出しアクセスエンティティは、待ち行列ページQ2/P3内のメッセージを読み出すための、V-PAGE_2内に配置された読み出しポインタREADER_1を有する（本実施例では待ち行列ページは複数のメッセージを格納する）。書き込みアクセスエンティティは、待ち行列ページQ2/P7内にメッセージを書き込むための、V-PAGE_7内に配置された書き込みポインタWRITER_1を有する。アドレスV-PAGE_8〜V-PAGE_10を用いて、閉じられるQUEUE_1の待ち行列ページを格納する。アドレスV-PAGE_11〜V-PAGE_12を用いて他のデータを格納する。

図３Ｂに示すのは、不揮発性メモリ格納１１０のメモリアドレス空間２０８の実施例である。不揮発性メモリ格納１１０は、同期されている（例えばコミット操作による同期）QUEUE_1およびQUEUE_2の待ち行列ページを格納し、その内の幾つかは揮発性メモリ格納１０８にも新しくロードされている。本実施例では、揮発性メモリ内の待ち行列ページQ2/P7は、不揮発性メモリとまだ同期していない新規メッセージで書き込まれている。

図３Ｃは、揮発性メモリ格納１０８内の活動履歴に対応するリサイクルリスト２００を示す。例えば、QUEUE_1は閉じたばかりなので、待ち行列システム１００は、ＬＲＵ方式に基づいてリサイクルするために、リサイクルリスト２００のテールエンド２０４上にこれらの仮想アドレスを配置することにより、待ち行列ページQ1/P3〜Q1/P5を記録したところである。書き込みポインタWRITER_1は、待ち行列ページQ2/P4、Q2/P5、およびQ2/P6（この順序で）から移動したばかりである。したがって、待ち行列システム１００は、これらの仮想アドレスを、リサイクルリスト２００の、テールエンド２０４ではなくヘッドエンド２０２上に配置したところである。

図４Ａ〜４Ｃは、続いて起こる活動の後の、揮発性アドレス空間２１０、不揮発性アドレス空間２０８、およびリサイクルリスト２００の状態をそれぞれ示す。書き込みポインタWRITER_1は、空きリスト２１２から割り当てられるアドレスV-PAGE_2で新規待ち行列ページQ2/P8上に移動したところである。第２の読み出しアクセスエンティティは、V-PAGE_1内に配置された読み出しポインタREADER_2を有し、空きリスト２１２から割り当てられた待ち行列ページQ1/P1内のメッセージを読み出す。これらのページ割り当て後、空きリスト２１２は空になる。

図５Ａ〜５Ｃは、リサイクルリスト２００からのページ割り当て後の、揮発性アドレス空間２１０、不揮発性アドレス空間２０８、およびリサイクルリスト２００の状態をそれぞれ示す。書き込みポインタWRITER_1は、待ち行列ページQ2/P8上に残る。読み出しポインタREADER_1は、V-PAGE_4で待ち行列ページQ2/P4上に移動したところである。読み出しポインタREADER_2は、リサイクルリスト２００（図４Ｃ）のヘッド２０２から割り当てられた待ち行列ページQ1/P2上に移動したところである。このページ割り当て後、リサイクルリスト２００の新規ヘッド２０２は、Q2/P6となる（図５Ｃ）。待ち行列ページQUEUE_1AおよびQUEUE_1Cはもはや必要でなくなるので、アドレスV-PAGE_1およびV-PAGE_3は、空きリスト２０４（図５Ｄ）上に配置される。

この実施例では、単一ライターおよび単一リーダーが所与の待ち行列にアクセスする。その他の実施例では、多数のアクセスエンティティ（例えば、加入者および／またはライター）が同一の待ち行列と相互作用できる（それぞれが自身の読み出しまたは書き込みポインタを有する）。多数のアクセスエンティティが一つの待ち行列と相互作用する場合、メモリページをリサイクルするために上記説明の同一ケースを用いることができる。

待ち行列システム１００は、本明細書で説明した技法と組み合わせた他の技法を用いてシステム性能を高めることができる。例えば、待ち行列マネージャ１０２は、ページが要求されようとしている時を予測でき、多数のページを同時にリサイクルできる。待ち行列マネージャ１０２は、例えば、リサイクルリスト内のページが追加された後にそれを並べ替えることによりリサイクルリストを修正することもできる。

上記のページ管理方式は、コンピュータ上で実行するためのソフトウエアを用いて実施できる。例えば、このソフトウエアは、プログラムされるか、またはプログラム可能な一台以上のコンピュータシステム（分散型、クライアント／サーバ型、またはグリッド型のような各種アーキテクチャで構成できる）上で実行される、一つ以上のコンピュータプログラム内の手順を形成し、上記コンピュータシステムはそれぞれ、少なくとも一つのプロセッサ、少なくとも一つのデータ記憶装置システム（揮発性および不揮発性メモリおよび／または記憶素子を含む）、少なくとも一つの入力装置または入力ポート、および少なくとも一つ出力装置または出力ポートを含む。このソフトウエアは、例えば、計算グラフの設計および構成に関連する他のサービスを提供する大規模なプログラムの一つ以上のモジュールを形成してもよい。グラフのノードおよび要素は、コンピュータ読取り可能な媒体内に格納されるデータ構造、またはデータ収納庫内に格納されるデータモデルに準拠した他の体系化されたデータとして実装できる。

このソフトウエアは、汎用または専用のプログラマブルコンピュータが読みとれるＣＤ−ＲＯＭのような、または実行している場所のコンピュータにネットワークを介して配信（伝送信号に符号化されて）可能な媒体上で提供できる。機能は全て、専用コンピュータ上で、またはコプロセッサのような専用ハードウエアを用いて実行できる。本ソフトウエアは、ソフトウエアが規定する、計算の異なる部分を異なるコンピュータで実行する分散方式で実施することができる。このようなコンピュータプログラムはそれぞれ、コンピュータシステムが記憶媒体または装置を読みとって本明細書に記載する手順を実行する場合、コンピュータを構成し、動作させるために、汎用または専用プログラマブルコンピュータが読みとれる記憶媒体または装置（例えば、固体のメモリもしくは媒体または磁気もしくは光の媒体）に格納するか、ダウンロードするのが好ましい。本発明のシステムは、コンピュータプログラムとともに構成されるコンピュータ読取り可能な記憶媒体として、実装されるべきであると考えることもでき、そのように構成された記憶媒体は、コンピュータシステムを特定のおよび所定の方法で動作させ、本明細書に記載の機能を実行させる。

言うまでもなく、上記記載は説明用であって、本発明の範囲を制限するものではなく、その範囲は、付帯する特許請求の範囲により定義される。例えば、上記の幾つかの機能ステップは、処理全体へ実質的に影響を及ぼさずに異なる順序で実行できる。他の実施の形態は、以下の特許請求の範囲内にある。

図１は、待ち行列システムの図である。 図２Ａは、揮発性および不揮発性メモリ空間へリサイクルリストをリンクするページテーブルの図である。 図２Ｂは、メモリページの図である。 図３Ａは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図３Ｂは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図３Ｃは、図３Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。 図３Ｄは、図３Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。 図４Ａは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図４Ｂは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図４Ｃは、図４Ａの揮発性メモリ空間に対応するリサイクルリストの図である。 図５Ａは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図５Ｂは、揮発性および不揮発性メモリ空間内のメモリページの図である。 図５Ｄは、図５Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。 図５Ｄは、図５Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。

Claims (47)

1. 一つ以上の待ち行列のために用いられるメモリをページングするための方法であって、
   前記待ち行列の少なくとも一部を格納する少なくとも幾つかのメモリページを含むメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供するステップと、
   前記待ち行列の少なくとも一つの一部を格納するメモリページへのアクセス履歴に基づいて、前記リサイクルリストデータ構造を維持して、前記順序における前記メモリページの位置を、前記メモリページからのシーケンシャルアクセスの移行に依存させるステップ
   とを含む方法。
2. 前記メモリページからのシーケンシャルアクセスの前記移行は、前記メモリページからのポインタの移行に対応する請求項１の方法。
3. 前記順序における前記メモリページの前記位置は、シーケンシャルアクセスの前記移行が、前記メモリページからの書き込みアクセスの移行に対応するかどうかに依存する請求項１の方法。
4. 前記待ち行列の一つと関係付けられた、メモリページへのアクセス履歴に基づいて、前記順序を表す前記リサイクルリストデータ構造を維持するステップは、
   前記メモリページからの書き込みアクセスの移行に応じて、前記リサイクルリストデータ構造の第１エンドに、前記メモリページのための識別子を配置するステップと、
   閉じている前記メモリページと関係付けられる前記待ち行列に応じて、前記リサイクルリストデータ構造の第２エンドに、前記メモリページのための識別子を配置するステップ
   とを含む請求項１の方法。
5. 前記リサイクルリストデータ構造の前記第１エンドからのメモリページを再使用するステップをさらに含む請求項４の方法。
6. 空きメモリページリストが空であることを判定した後、前記リサイクルリストデータ構造の前記第１エンドから前記メモリページを再使用するステップをさらに含む請求項５の方法。
7. 前記メモリページを再使用するステップは、前記メモリページの現在のコンテンツを不揮発性メモリ格納へ書き込むステップを含む請求項５の方法。
8. 前記メモリページを再使用するステップは、前記不揮発性メモリ格納からのメモリページを前記メモリページへ書き込むステップをさらに含む請求項７の方法。
9. 一つ以上の待ち行列のために用いられるメモリをページングするための、コンピュータ読取り可能な記録媒体上に格納されるソフトウエアであって、
   前記待ち行列の一部を格納する少なくとも幾つかのメモリページを含むメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供する命令と、
   前記待ち行列の少なくとも一つの一部を格納するメモリページへのアクセス履歴に基づいて、前記リサイクルリストデータ構造を維持して、前記順序における前記メモリページの位置を、前記メモリページからのシーケンシャルアクセスの移行に依存させる命令とをコンピュータシステムに実行させるソフトウエア。
10. 一つ以上の待ち行列のために用いられるメモリをページングするためのシステムであって、
    前記待ち行列の一部を格納する少なくとも幾つかのメモリページを含むメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供するための手段と、
    前記待ち行列の少なくとも一つの一部を格納するメモリページへのアクセス履歴に基づいて、前記リサイクルリストデータ構造を維持して、前記順序における前記メモリページの位置を、前記メモリページからのシーケンシャルアクセスの移行に依存させる手段とを備えたシステム。
11. 一つ以上の待ち行列のために用いられるメモリをページングするための方法であって、
    前記待ち行列の少なくとも一部を格納するメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供するステップと、
    第１のケースでは最新使用方式に基づいて、前記リサイクルリストデータ構造の第１エンドで識別されたメモリページを再使用し、第２のケースでは最長時間未使用方式に基づいて、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用するステップを含む方法。
12. 前記第１のケースは、前記メモリページからの書き込みポインタの移行に応じて発生する請求項１１の方法。
13. 前記第２のケースは、アクセスエンティティが前記待ち行列を閉じることに応じて発生する請求項１１の方法。
14. 前記第２のケースは、前記メモリページからの読み出しポインタの移行に応じて発生する請求項１１の方法。
15. 一つ以上の待ち行列のために用いられるメモリをページングするための、コンピュータ読取り可能な記録媒体上に格納されるソフトウエアであって、
    前記待ち行列の少なくとも一部を格納するメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供する命令と、
    第１のケースでは最新使用方式に基づいて、前記リサイクルリストデータ構造の第１エンドで識別されたメモリページを再使用し、第２のケースでは最長時間未使用方式に基づいて、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用させるための命令を、コンピュータシステムに実行させるソフトウエア。
16. 前記リサイクルリストデータ構造によって識別されたメモリページを再使用して、前記待ち行列の一つの一部を格納するステップをさらに含む請求項１の方法。
17. 前記リサイクルリストデータ構造によって識別された前記再使用されるメモリページは、再使用される前に前記待ち行列の一つの別の一部を格納していた請求項１６の方法。
18. 前記再使用されるメモリページに格納されている、前記待ち行列の一つの前記一部は、待ち行列に書き込まれている待ち行列メッセージを含む請求項１６の方法。
19. 前記待ち行列を格納する前記メモリページは、待ち行列メッセージと、前記待ち行列メッセージの管理に関連する記録とを格納する請求項１の方法。
20. 前記第１のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１１の方法。
21. 書き込みアクセスエンティティは、書き込みポインタで前記第２の部分を前記メモリページに書き込み、読み出しアクセスエンティティは、前記書き込みポインタから遅延する読み出しポインタで前記待ち行列からデータを読み出す請求項２０の方法。
22. 前記メモリページは、他のメモリページを使用する前に、一つ以上の最長時間未使用メモリページを前記読み出しアクセスエンティティのために利用可能としたまま、前記書き込みアクセスエンティティによって前記待ち行列に書き込むために繰り返し再使用される請求項２１の方法。
23. 前記第２のケースでは、前記メモリページは、第１の待ち行列の一部を格納し、第２の待ち行列の一部を格納するために再使用される請求項１１の方法。
24. 前記第２の待ち行列の前記一部は、アクセスエンティティによって前記第１の待ち行列が閉じられた後に、前記メモリページに格納される請求項２３の方法。
25. 前記第２のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１１の方法。
26. 書き込みアクセスエンティティは、前記第１の部分を読み出す読み出しアクセスエンティティの読み出しポインタが前記メモリページから移行した後に、前記第２の部分を前記メモリページに書き込む請求項２５の方法。
27. 前記待ち行列に格納される論理的に順序付けられたエレメントは、複数のシーケンシャル待ち行列メッセージを含む請求項１の方法。
28. 前記論理的に順序付けられたエレメントは、前記シーケンシャル待ち行列メッセージに関連する少なくとも１つの記録を含む請求項２７の方法。
29. 前記待ち行列に格納される論理的に順序付けられたエレメントは、書き込みアクセスエンティティによって書き込まれ、少なくとも一つの読み出しアクセスエンティティによって読み出される請求項１の方法。
30. 前記書き込みアクセスエンティティと前記読み出しアクセスエンティティとは異なる請求項２９の方法。
31. 第１のメモリページのコンテンツを揮発性メモリ格納から不揮発性メモリ格納に書き込んだ後に第１の待ち行列の一部を前記第１のメモリページに格納するステップを含む、第１のアクセスエンティティからの要求に応じて前記第１の待ち行列を開くステップと、
    前記第１のキューのための書き込みポインタを前記第１のアクセスエンティティに提供するステップとをさらに含む請求項１の方法。
32. 前記第１の待ち行列のための一つ以上の読み出しポインタを一つ以上の追加のアクセスエンティティに提供するステップをさらに含む請求項３１の方法。
33. 前記第１の待ち行列の一部を格納する第２のメモリページを、前記書き込みポインタまたは前記読み出しポインタの何れも前記第２のメモリページを指し示していないことを判定した後に、前記リサイクルリストデータ構造に移動させるステップをさらに含む請求項３２の方法。
34. 前記第１のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１５のソフトウェア。
35. 書き込みアクセスエンティティは、書き込みポインタで前記第２の部分を前記メモリページに書き込み、読み出しアクセスエンティティは、前記書き込みポインタから遅延する読み出しポインタで前記待ち行列からデータを読み出す請求項３４のソフトウェア。
36. 前記メモリページは、他のメモリページを使用する前に、一つ以上の最長時間未使用メモリページを前記読み出しアクセスエンティティのために利用可能としたまま、前記書き込みアクセスエンティティによって前記待ち行列に書き込むために繰り返し再使用される請求項３５のソフトウェア。
37. 前記第２のケースでは、前記メモリページは、第１の待ち行列の一部を格納し、第２の待ち行列の一部を格納するために再使用される請求項１５のソフトウェア。
38. 前記第２の待ち行列の前記一部は、アクセスエンティティによって前記第１の待ち行列が閉じられた後に、前記メモリページに格納される請求項３７のソフトウェア。
39. 前記第２のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１５のソフトウェア。
40. 書き込みアクセスエンティティは、前記第１の部分を読み出す読み出しアクセスエンティティの読み出しポインタが前記メモリページから移行した後に、前記第２の部分を前記メモリページに書き込む請求項３９のソフトウェア。
41. 前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１０のシステム。
42. 書き込みアクセスエンティティは、書き込みポインタで前記第２の部分を前記メモリページに書き込み、読み出しアクセスエンティティは、前記書き込みポインタから遅延する読み出しポインタで前記待ち行列からデータを読み出す請求項４１のシステム。
43. 前記メモリページは、他のメモリページを使用する前に、一つ以上の最長時間未使用メモリページを前記読み出しアクセスエンティティのために利用可能としたまま、前記書き込みアクセスエンティティによって前記待ち行列に書き込むために繰り返し再使用される請求項４２のシステム。
44. 前記メモリページは、第１の待ち行列の一部を格納し、第２の待ち行列の一部を格納するために再使用される請求項１０のシステム。
45. 前記第２の待ち行列の前記一部は、アクセスエンティティによって前記第１の待ち行列が閉じられた後に、前記メモリページに格納される請求項４４のシステム。
46. 前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１０のシステム。
47. 書き込みアクセスエンティティは、前記第１の部分を読み出す読み出しアクセスエンティティの読み出しポインタが前記メモリページから移行した後に、前記第２の部分を前記メモリページに書き込む請求項４６のシステム。

Images