(57)【特許請求の範囲】
【請求項１】
一つ以上の待ち行列のために用いられるメモリをページングするためのシステムであって、
前記待ち行列の少なくとも一部を格納するメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供する手段と、
第１のケースでは最新使用方式に基づいて、前記リサイクルリストデータ構造の第１エンドで識別されたメモリページを再使用する手段と、
を含むシステム。
【請求項２】
前記第１のケースは、前記メモリページからの書き込みポインタの移行を含む請求項１のシステム。
【請求項３】
アクセスエンティティが前記待ち行列を閉じるときに、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することをさらに含む請求項１のシステム。
【請求項４】
読み出しポインタが前記メモリページから移行するときに、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することをさらに含む請求項１のシステム。
【請求項５】
前記第１のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１のシステム。
【請求項６】
書き込みアクセスエンティティは、書き込みポインタで前記第２の部分を前記メモリページに書き込み、読み出しアクセスエンティティは、前記書き込みポインタから遅延する読み出しポインタで前記待ち行列からデータを読み出す請求項５のシステム。
【請求項７】
前記メモリページは、他のメモリページを使用する前に、一つ以上の最長時間未使用メモリページを前記読み出しアクセスエンティティのために利用可能としたまま、前記書き込みアクセスエンティティによって前記待ち行列に書き込むために繰り返し再使用される請求項６のシステム。
【請求項８】
前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することをさらに含み、前記メモリページは、第１の待ち行列の一部を格納し、第２の待ち行列の一部を格納するために再使用される請求項１のシステム。
【請求項９】
前記第２の待ち行列の前記一部は、アクセスエンティティによって前記第１の待ち行列が閉じられた後に、前記メモリページに格納される請求項８のシステム。
【請求項１０】
前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することをさらに含み、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項１のシステム。
【請求項１１】
書き込みアクセスエンティティは、前記第１の部分を読み出す読み出しアクセスエンティティの読み出しポインタが前記メモリページから移行した後に、前記第２の部分を前記メモリページに書き込む請求項１０のシステム。
【請求項１２】
一つ以上の待ち行列のために用いられるメモリをページングするためのシステムであって、
前記待ち行列の一部を格納する少なくとも幾つかのメモリページを含むメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造に基づいて、どのメモリページを再使用するかを判断するための手段と、
前記リサイクルリストデータ構造における前記メモリページの少なくとも幾つかの位置を、前記メモリページからのシーケンシャルアクセスの移行に依存する順序に編成する手段と、
を含むシステム。
【請求項１３】
前記メモリページからのシーケンシャルアクセスの前記移行は、前記メモリページからのポインタの移行に対応する請求項１２のシステム。
【請求項１４】
前記順序における前記メモリページの前記位置は、シーケンシャルアクセスの前記移行が、前記メモリページからの書き込みアクセスの移行に対応するかどうかに依存する請求項１２のシステム。
【請求項１５】
前記編成する手段は、
前記メモリページからの書き込みアクセスの移行に応じて、前記リサイクルリストデータ構造の第１エンドに、前記メモリページのための識別子を配置する手段と、
閉じている前記メモリページと関係付けられる前記待ち行列に応じて、前記リサイクルリストデータ構造の第２エンドに、前記メモリページのための識別子を配置する手段と、
を含む請求項１２のシステム。
【請求項１６】
前記リサイクルリストデータ構造の前記第１エンドからのメモリページを再使用する手段をさらに含む請求項１５のシステム。
【請求項１７】
空きメモリページリストが空であることを判定した後、前記リサイクルリストデータ構造の前記第１エンドから前記メモリページを再使用する手段をさらに含む請求項１６のシステム。
【請求項１８】
前記メモリページを再使用する手段は、前記メモリページの現在のコンテンツを不揮発性メモリ格納へ書き込む手段を含む請求項１６のシステム。
【請求項１９】
前記メモリページを再使用する手段は、前記不揮発性メモリ格納からのメモリページを前記メモリページへ書き込む手段をさらに含む請求項１８のシステム。
【請求項２０】
前記リサイクルリストデータ構造によって識別されたメモリページを再使用して、前記待ち行列の一つの一部を格納する手段をさらに含む請求項１２のシステム。
【請求項２１】
前記リサイクルリストデータ構造によって識別された前記再使用されるメモリページは、再使用される前に前記待ち行列の一つの別の一部を格納していた請求項２０のシステム。
【請求項２２】
前記再使用されるメモリページに格納されている、前記待ち行列の一つの前記一部は、待ち行列に書き込まれている待ち行列メッセージを含む請求項２０のシステム。
【請求項２３】
前記待ち行列を格納する前記メモリページは、待ち行列メッセージと、前記待ち行列メッセージの管理に関連する記録とを格納する請求項１２のシステム。
【請求項２４】
前記待ち行列に格納される論理的に順序付けられたエレメントは、複数のシーケンシャル待ち行列メッセージを含む請求項１２のシステム。
【請求項２５】
前記論理的に順序付けられたエレメントは、前記シーケンシャル待ち行列メッセージに関連する少なくとも１つの記録を含む請求項２４のシステム。
【請求項２６】
前記待ち行列に格納される論理的に順序付けられたエレメントは、書き込みアクセスエンティティによって書き込まれ、少なくとも一つの読み出しアクセスエンティティによって読み出される請求項１２のシステム。
【請求項２７】
前記書き込みアクセスエンティティと前記読み出しアクセスエンティティとは異なる請求項２６のシステム。
【請求項２８】
第１のメモリページのコンテンツを揮発性メモリ格納から不揮発性メモリ格納に書き込んだ後に第１の待ち行列の一部を前記第１のメモリページに格納することを含む、第１のアクセスエンティティからの要求に応じて前記第１の待ち行列を開く手段と、
前記第１の待ち行列のための書き込みポインタを前記第１のアクセスエンティティに提供する手段と、
をさらに含む請求項１２のシステム。
【請求項２９】
前記第１の待ち行列のための一つ以上の読み出しポインタを一つ以上の追加のアクセスエンティティに提供する手段をさらに含む請求項２８のシステム。
【請求項３０】
前記第１の待ち行列の一部を格納する第２のメモリページを、前記書き込みポインタまたは前記読み出しポインタの何れも前記第２のメモリページを指し示していないことを判定した後に、前記リサイクルリストデータ構造に移動させる手段をさらに含む請求項２９のシステム。
【請求項３１】
一つ以上の待ち行列のために用いられるメモリをページングするための、コンピュータ読取り可能な記録媒体上に格納されるソフトウェアであって、
前記待ち行列の一部を格納する少なくとも幾つかのメモリページを含むメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造に基づいて、どのメモリページを再使用するかを判断することと、
前記リサイクルリストデータ構造における前記メモリページの少なくとも幾つかの位置を、前記メモリページからのシーケンシャルアクセスの移行に依存する順序に編成することとをコンピュータシステムに実行させるための命令を含む、
ソフトウェア。
【請求項３２】
前記メモリページからのシーケンシャルアクセスの前記移行は、前記メモリページからのポインタの移行に対応する請求項３１のソフトウェア。
【請求項３３】
前記順序における前記メモリページの前記位置は、シーケンシャルアクセスの前記移行が、前記メモリページからの書き込みアクセスの移行に対応するかどうかに依存する請求項３１のソフトウェア。
【請求項３４】
前記リサイクルリストデータ構造における前記メモリページの少なくとも幾つかの位置を編成することは、
前記メモリページからの書き込みアクセスの移行に応じて、前記リサイクルリストデータ構造の第１エンドに、前記メモリページのための識別子を配置することと、
閉じている前記メモリページと関係付けられる前記待ち行列に応じて、前記リサイクルリストデータ構造の第２エンドに、前記メモリページのための識別子を配置することと、
を含む請求項３１のソフトウェア。
【請求項３５】
前記リサイクルリストデータ構造の前記第１エンドからのメモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含む請求項３４のソフトウェア。
【請求項３６】
空きメモリページリストが空であることを判定した後、前記リサイクルリストデータ構造の前記第１エンドから前記メモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含む請求項３５のソフトウェア。
【請求項３７】
前記メモリページを再使用することは、前記メモリページの現在のコンテンツを不揮発性メモリ格納へ書き込むことを含む請求項３５のソフトウェア。
【請求項３８】
前記メモリページを再使用することは、前記不揮発性メモリ格納からのメモリページを前記メモリページへ書き込むことをさらに含む請求項３７のソフトウェア。
【請求項３９】
前記リサイクルリストデータ構造によって識別されたメモリページを再使用して、前記待ち行列の一つの一部を格納することを前記コンピュータシステムに実行させるための命令をさらに含む請求項３１のソフトウェア。
【請求項４０】
前記リサイクルリストデータ構造によって識別された前記再使用されるメモリページは、再使用される前に前記待ち行列の一つの別の一部を格納していた請求項３９のソフトウェア。
【請求項４１】
前記再使用されるメモリページに格納されている、前記待ち行列の一つの前記一部は、待ち行列に書き込まれている待ち行列メッセージを含む請求項３９のソフトウェア。
【請求項４２】
前記待ち行列を格納する前記メモリページは、待ち行列メッセージと、前記待ち行列メッセージの管理に関連する記録とを格納する請求項３１のソフトウェア。
【請求項４３】
前記待ち行列に格納される論理的に順序付けられたエレメントは、複数のシーケンシャル待ち行列メッセージを含む請求項３１のソフトウェア。
【請求項４４】
前記論理的に順序付けられたエレメントは、前記シーケンシャル待ち行列メッセージに関連する少なくとも１つの記録を含む請求項４３のソフトウェア。
【請求項４５】
前記待ち行列に格納される論理的に順序付けられたエレメントは、書き込みアクセスエンティティによって書き込まれ、少なくとも一つの読み出しアクセスエンティティによって読み出される請求項３１のソフトウェア。
【請求項４６】
前記書き込みアクセスエンティティと前記読み出しアクセスエンティティとは異なる請求項４５のソフトウェア。
【請求項４７】
第１のメモリページのコンテンツを揮発性メモリ格納から不揮発性メモリ格納に書き込んだ後に第１の待ち行列の一部を前記第１のメモリページに格納することを含む、第１のアクセスエンティティからの要求に応じて前記第１の待ち行列を開くことと、
前記第１の待ち行列のための書き込みポインタを前記第１のアクセスエンティティに提供することと、
を前記コンピュータシステムに実行させるための命令をさらに含む請求項３１のソフトウェア。
【請求項４８】
前記第１の待ち行列のための一つ以上の読み出しポインタを一つ以上の追加のアクセスエンティティに提供することを前記コンピュータシステムに実行させるための命令をさらに含む請求項４７のソフトウェア。
【請求項４９】
前記第１の待ち行列の一部を格納する第２のメモリページを、前記書き込みポインタまたは前記読み出しポインタの何れも前記第２のメモリページを指し示していないことを判定した後に、前記リサイクルリストデータ構造に移動させることを前記コンピュータシステムに実行させるための命令をさらに含む請求項４８のソフトウェア。
【請求項５０】
一つ以上の待ち行列のために用いられるメモリをページングするための、コンピュータ読取り可能な記録媒体上に格納されるソフトウェアであって、
前記待ち行列の少なくとも一部を格納するメモリページを識別するとともに、前記識別されるメモリページが再使用される順序を表すリサイクルリストデータ構造を提供することと、
第１のケースでは最新使用方式に基づいて、前記リサイクルリストデータ構造の第１エンドで識別されたメモリページを再使用することと、
をコンピュータシステムに実行させるための命令を含むソフトウェア。
【請求項５１】
前記第１のケースは、書き込みポインタが前記メモリページから移行することを含む請求項５０のソフトウェア。
【請求項５２】
アクセスエンティティが前記待ち行列を閉じるときに、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含む請求項５０のソフトウェア。
【請求項５３】
読み出しポインタが前記メモリページから移行するときに、前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含む請求項５０のソフトウェア。
【請求項５４】
前記第１のケースでは、前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項５０のソフトウェア。
【請求項５５】
書き込みアクセスエンティティは、書き込みポインタで前記第２の部分を前記メモリページに書き込み、読み出しアクセスエンティティは、前記書き込みポインタから遅延する読み出しポインタで前記待ち行列からデータを読み出す請求項５４のソフトウェア。
【請求項５６】
前記メモリページは、他のメモリページを使用する前に、一つ以上の最長時間未使用メモリページを前記読み出しアクセスエンティティのために利用可能としたまま、前記書き込みアクセスエンティティによって前記待ち行列に書き込むために繰り返し再使用される請求項５５のソフトウェア。
【請求項５７】
前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含み、
前記メモリページは、第１の待ち行列の一部を格納し、第２の待ち行列の一部を格納するために再使用される請求項５０のソフトウェア。
【請求項５８】
前記第２の待ち行列の前記一部は、アクセスエンティティによって前記第１の待ち行列が閉じられた後に、前記メモリページに格納される請求項５７のソフトウェア。
【請求項５９】
前記リサイクルリストデータ構造の第２エンドで識別されたメモリページを再使用することを前記コンピュータシステムに実行させるための命令をさらに含み、
前記メモリページは、待ち行列の第１の部分を格納し、前記待ち行列の第２の部分を格納するために再使用される請求項５０のソフトウェア。
【請求項６０】
書き込みアクセスエンティティは、前記第１の部分を読み出す読み出しアクセスエンティティの読み出しポインタが前記メモリページから移行した後に、前記第２の部分を前記メモリページに書き込む請求項５９のソフトウェア。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリページの管理に関する。
【背景技術】
【０００２】
揮発性メモリ格納（例えば、ランダムアクセスメモリ（ＲＡＭ））を用いて、不揮発性メモリ格納（例えば、一つ以上のディスクドライブ）にも格納されているデータと連携をとることは有用である。例えば、揮発性メモリ格納は、普通は不揮発性メモリ格納よりアクセスおよび読み出し時間が高速である。揮発性メモリ格納および不揮発性メモリ格納のアドレス空間は、所定数の連続するアドレス配置にまたがるページに編成することができる。コンピュータシステムは、ページング技法を用いて、例えば、プログラミングまたはデータ構造が使用する揮発性メモリからメモリページを割り当てる。不揮発性メモリ格納は、普通は揮発性メモリ格納よりずっと規模が大きい。仮想メモリ方式を用いて、使用していない（例えば、現在、書き込みも読み出しもしていない）揮発性メモリ格納内のページを不揮発性メモリ格納へ書き込んでおいて、後で必要な時に、不揮発性メモリ格納から再度読み出すことができる。したがって、揮発性メモリ格納内のページは、各種のプログラミングおよび／またはデータ構造による使用のために「リサイクル（再使用）」される。ページを前後しての移動と関係付けられるオーバーヘッドを低減するために、技法によっては、最長時間未使用（ＬＲＵ）方式に基づいてページをリサイクルする。ＬＲＵ方式では、不揮発性メモリ格納へ書き込まれたページが揮発性メモリ格納への移動対象であるにもかかわらず、揮発性メモリ格納内に空きページがない場合、揮発性メモリ格納から不揮発性メモリ格納へリサイクル（つまり、スワッピングまたはページアウト）するように選択されるページは、未使用時間が最長の（例えば、最も長い時間、読み出しまたは書き込みがなされていない）ページである。
【発明の概要】
【０００３】
一般的な態様において、本発明は、シーケンシャルアクセスされる一つ以上のデータ構造のために用いられるメモリをページングするための方法、ならびにそれに対応するソフトウエアおよびシステムを特徴とする。本方法は、メモリページの再使用順序を表すデータ構造を提供するステップ、およびシーケンシャルアクセスされるデータ構造の一つと関係付けられた、メモリページへのアクセス履歴に基づいて、データ構造を維持するステップを含み、よって、その順序におけるメモリページの位置を、メモリページからのシーケンシャルアクセスの移行に依存させる。
【０００４】
この態様は、以下の特徴の一つ以上を含む：
メモリページからのシーケンシャルアクセスの移行は、メモリページからのポインタの移行に対応する。
その順序におけるメモリページの位置は、シーケンシャルアクセスの移行が、メモリページからの書き込みアクセスの移行に対応するかどうかに依存する。
シーケンシャルアクセスされるデータ構造の一つと関係付けられた、メモリページへのアクセス履歴に基づくデータ構造を維持するステップが、メモリページからの書き込みアクセスの移行に応じて、順序を表すデータ構造の第１エンドに、メモリページ用の識別子を配置するステップと、閉じられているメモリページと関係付けられる、シーケンシャルアクセスされるデータ構造に応じて、順序を表すデータ構造の第２エンドに、メモリページ用の識別子を配置するステップとを含む。
【０００５】
本方法は、順序を表すデータ構造の第１エンドからのメモリページを再使用するステップをさらに含む。
【０００６】
本方法は、空きメモリページリストが空であることを判定した後、データ構造の第１エンドからの前記メモリページを再使用するステップをさらに含む。
【０００７】
メモリページを再使用するステップは、メモリページの現在のコンテンツを不揮発性メモリ格納へ書き込むステップを含む。
【０００８】
メモリページを再使用するステップは、不揮発性メモリ格納からのメモリページをメモリページへ書き込むステップをさらに含む。
【０００９】
メモリページと関係付けられる、シーケンシャルアクセスされるデータ構造は、待ち行列を含む。
【００１０】
一般的な態様において、本発明は、シーケンシャルアクセスされる一つ以上のデータ構造のために用いられるメモリをページングするための方法、ならびにそれに対応するソフトウエアおよびシステムを特徴とし、第１のケースでは最長時間使用方式に基づき、第２のケースでは最長時間未使用方式に基づいて、シーケンシャルアクセスされるデータ構造に関係付けられるメモリページを再使用するステップを含む。
【００１１】
本態様は以下の特徴の一つ以上を含むことができる：
第１のケースは、メモリページからの書き込みポインタの移行を含む。
第２のケースは、シーケンシャルアクセスされるデータ構造を閉じるアクセスエンティティを含む。
第２のケースは、メモリページからの読み出しポインタの移行を含む。
【００１２】
本発明の態様は、以下の利点の一つ以上を含むことができる：
再使用のためのページを順序付けるステップは、待ち行列または他のシーケンシャルＩ／Ｏデータ構造を格納するメモリシステムに対して、どのページがすぐに再使用される可能性があるのか、より良好な予測を提供できる。書き込まれたばかりの（すなわち、書き込みポインタがページを去ったばかりの）ページは、読み出しポインタが書き込みポインタに「追いつかなければ」ならないので、すぐに再使用される可能性が少ない。したがって、これらのページは、最初にリサイクルされる。さらに、閉じたばかりの待ち行列に対するページは、すぐに再オープンされて、再使用されるかもしれないので、後までリサイクルされない。しばらく閉じたままのページはその間にどこかにリサイクルされる。
【００１３】
待ち行列特有のページングアルゴリズムの使用は、待ち行列構造またはアクセスパターンを利用しないページングアルゴリズムの使用を超える高い効率を提供できる。データ格納待ち行列のページングは、どのページが再使用されるかを決定する際に、待ち行列アクセス履歴を利用することにより改良できる。例えば、アクセス履歴に基づいて、幾つかのページは他のページより早く再アクセスされる、と予測することができる。この改良により、作業している記憶装置内に必要なページが存在する可能性がより高くなるので、作業中の記憶装置へデータを転送して戻すことに起因する遅延を低減できる。
【００１４】
本発明の他の特徴および利点は、以下の説明および特許請求の範囲から明らかになろう。
【図面の簡単な説明】
【００１５】
【図１】待ち行列システムの図である。
【図２Ａ】揮発性および不揮発性メモリ空間へリサイクルリストをリンクするページテーブルの図である。
【図２Ｂ】メモリページの図である。
【図３Ａ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図３Ｂ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図３Ｃ】図３Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。
【図３Ｄ】図３Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。
【図４Ａ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図４Ｂ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図４Ｃ】図４Ａの揮発性メモリ空間に対応するリサイクルリストの図である。
【図５Ａ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図５Ｂ】揮発性および不揮発性メモリ空間内のメモリページの図である。
【図５Ｃ】図５Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。
【図５Ｄ】図５Ａの揮発性メモリ空間に対応するリサイクルリストおよび空きリストの図である。
【発明を実施するための形態】
【００１６】
図１を参照すると、待ち行列システム１００により、アクセスエンティティ１０２Ａ〜１０２Ｐは、１セット以上の待ち行列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は、空きリスト２０４（図５Ｄ）上に配置される。
【００４４】
この実施例では、単一ライターおよび単一リーダーが所与の待ち行列にアクセスする。その他の実施例では、多数のアクセスエンティティ（例えば、加入者および／またはライター）が同一の待ち行列と相互作用できる（それぞれが自身の読み出しまたは書き込みポインタを有する）。多数のアクセスエンティティが一つの待ち行列と相互作用する場合、メモリページをリサイクルするために上記説明の同一ケースを用いることができる。
【００４５】
待ち行列システム１００は、本明細書で説明した技法と組み合わせた他の技法を用いてシステム性能を高めることができる。例えば、待ち行列マネージャ１０２は、ページが要求されようとしている時を予測でき、多数のページを同時にリサイクルできる。待ち行列マネージャ１０２は、例えば、リサイクルリスト内のページが追加された後にそれを並べ替えることによりリサイクルリストを修正することもできる。
【００４６】
上記のページ管理方式は、コンピュータ上で実行するためのソフトウエアを用いて実施できる。例えば、このソフトウエアは、プログラムされるか、またはプログラム可能な一台以上のコンピュータシステム（分散型、クライアント／サーバ型、またはグリッド型のような各種アーキテクチャで構成できる）上で実行される、一つ以上のコンピュータプログラム内の手順を形成し、上記コンピュータシステムはそれぞれ、少なくとも一つのプロセッサ、少なくとも一つのデータ記憶装置システム（揮発性および不揮発性メモリおよび／または記憶素子を含む）、少なくとも一つの入力装置または入力ポート、および少なくとも一つ出力装置または出力ポートを含む。このソフトウエアは、例えば、計算グラフの設計および構成に関連する他のサービスを提供する大規模なプログラムの一つ以上のモジュールを形成してもよい。グラフのノードおよび要素は、コンピュータ読取り可能な媒体内に格納されるデータ構造、またはデータ収納庫内に格納されるデータモデルに準拠した他の体系化されたデータとして実装できる。
【００４７】
このソフトウエアは、汎用または専用のプログラマブルコンピュータが読みとれるＣＤ−ＲＯＭのような、または実行している場所のコンピュータにネットワークを介して配信（伝送信号に符号化されて）可能な媒体上で提供できる。機能は全て、専用コンピュータ上で、またはコプロセッサのような専用ハードウエアを用いて実行できる。本ソフトウエアは、ソフトウエアが規定する、計算の異なる部分を異なるコンピュータで実行する分散方式で実施することができる。このようなコンピュータプログラムはそれぞれ、コンピュータシステムが記憶媒体または装置を読みとって本明細書に記載する手順を実行する場合、コンピュータを構成し、動作させるために、汎用または専用プログラマブルコンピュータが読みとれる記憶媒体または装置（例えば、固体のメモリもしくは媒体または磁気もしくは光の媒体）に格納するか、ダウンロードするのが好ましい。本発明のシステムは、コンピュータプログラムとともに構成されるコンピュータ読取り可能な記憶媒体として、実装されるべきであると考えることもでき、そのように構成された記憶媒体は、コンピュータシステムを特定のおよび所定の方法で動作させ、本明細書に記載の機能を実行させる。
【００４８】
言うまでもなく、上記記載は説明用であって、本発明の範囲を制限するものではなく、その範囲は、付帯する特許請求の範囲により定義される。例えば、上記の幾つかの機能ステップは、処理全体へ実質的に影響を及ぼさずに異なる順序で実行できる。他の実施の形態は、以下の特許請求の範囲内にある。
【図１】
0005647203.tif 000002
【図２Ａ】
0005647203.tif 000003
【図２Ｂ】
0005647203.tif 000004
【図３Ａ】
0005647203.tif 000005
【図３Ｂ】
0005647203.tif 000006
【図３Ｃ】
0005647203.tif 000007
【図３Ｄ】
0005647203.tif 000008
【図４Ａ】
0005647203.tif 000009
【図４Ｂ】
0005647203.tif 000010
【図４Ｃ】
0005647203.tif 000011
【図５Ａ】
0005647203.tif 000012
【図５Ｂ】
0005647203.tif 000013
【図５Ｃ】
0005647203.tif 000014
【図５Ｄ】
0005647203.tif 000015