(57)【要約】【課題】複数のデータ構造を使用してキャッシュ内のデータを管理する方法、システム、およびプログラムを提供すること。【解決手段】複数のデータ構造が、第２コンピュータ可読媒体に追加された第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する。第１コンピュータ可読媒体内のデータを求める要求が受信される。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在するかどうかに関して判定が行われる。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在しないと判定したことに応答して、要求されたデータが第１コンピュータ可読媒体から取り出され、第２コンピュータ可読媒体に格納される。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在しないと判定したことに応答して、データ構造のうちの１つが選択され、前記取り出されたデータに関するエントリが、選択されたデータ構造に追加される。【選択図】図２
2008027444.tif 000002
【特許請求の範囲】
【請求項１】
第２コンピュータ可読媒体に追加された第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造を提供するステップと、
前記第１コンピュータ可読媒体内のデータを求める要求を受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記第１コンピュータ可読媒体から前記要求されたデータを取り出し、前記第２コンピュータ可読媒体に格納するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記取り出したデータに関するエントリを前記選択したデータ構造に追加するステップと
を含む方法。
【請求項２】
前記データ構造のうちの１つが、前記データ構造のうちの１つをランダムに選択するステップを含む請求項１に記載の方法。
【請求項３】
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記取り出した要求されたデータを格納するために利用可能なスペースを前記第２コンピュータ可読媒体が有するかどうかを判定するステップと、
前記第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、前記データ構造のうちの１つから１つのエントリを選択するステップと、
前記第２コンピュータ可読媒体から前記選択したエントリに関するデータをデステージするステップと
をさらに含む請求項１に記載の方法。
【請求項４】
前記第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、前記データ構造のうちの１つから１つのエントリを選択するステップが、
最も古いエントリを有する前記データ構造のうちの１つを求めるステップであって、前記選択したエントリが、前記求めたデータ構造内の前記最も古いエントリを含むステップ
を含む請求項３に記載の方法。
【請求項５】
前記第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、前記データ構造のうちの１つから１つのエントリを選択するステップが、
前記データ構造のランダムなサブセットを選択するステップと、
前記選択したランダムなサブセットから、その最も古いエントリが前記選択したサブセット内の任意の他のデータ構造内の最も古いエントリよりも新しくない１つのデータ構造を選択するステップと
を含む請求項３に記載の方法。
【請求項６】
前記データ構造が最長時間未使用（ＬＲＵ）リストを含み、前記取り出したデータに関する前記エントリを追加するステップが、選択したＬＲＵリストの最短時間未使用（ＭＲＵ）端に前記エントリを追加するステップを含む請求項１に記載の方法。
【請求項７】
前記データ構造がクロックを含み、各クロックが、リスト内で互いに隣接するヘッド・エントリおよびテール・エントリを有し、前記取り出したデータに関する前記エントリを追加するステップが、前記選択したクロックの前記ヘッド・エントリに前記エントリを追加するステップを含む請求項１に記載の方法。
【請求項８】
前記クロック内の前記エントリが、前記エントリにアクセスされたかどうかを示し、
前記要求されたデータに関するエントリが前記クロックのうちの１つの中に存在しないと判定したことに応答して、前記取り出した要求されたデータを格納するために利用可能なスペースを前記第２コンピュータ可読媒体が有するかどうかを判定するステップと、
前記クロックのうちの１つを選択するステップと、
アクセスされていないと示される前記クロック内の１つのエントリを求めるステップと、
前記求めたエントリに関するデータを前記第２コンピュータ可読媒体からデステージするステップと
をさらに含む請求項７に記載の方法。
【請求項９】
第２コンピュータ可読媒体に追加された第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造を提供するステップと、
前記第１コンピュータ可読媒体内のデータを求める要求を受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ要求に関して、第２コンピュータ可読媒体から前記要求されたデータにアクセスするステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記要求されたデータに関する１つのエントリが存在すると判定したことに応答して、前記要求されたデータに関する求めたエントリを選択された前記データ構造に移動するステップと
を含む方法。
【請求項１０】
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ構造がランダムに選択される請求項９に記載の方法。
【請求項１１】
各データ構造が、最長時間未使用（ＬＲＵ）リストおよびクロック・データ構造のうちの１つを含む１組のデータ構造のメンバである請求項９に記載の方法。
【請求項１２】
第１コンピュータ可読媒体と通信するシステムであって、
少なくとも１つのプロセッサと、
第２コンピュータ可読媒体と、
前記第２コンピュータ可読媒体に追加された前記第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造と、
オペレーションを実行するようにされた前記第２コンピュータ可読媒体に対するアクセスを管理するキャッシュ・マネージャであって、前記オペレーションが、
前記第２コンピュータ可読媒体に追加された前記第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造を提供するステップと、
前記第１コンピュータ可読媒体内のデータを求める要求を１つのプロセッサから受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記第１コンピュータ可読媒体から前記要求されたデータを取り出し、前記第２コンピュータ可読媒体に格納するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記取り出したデータに関するエントリを前記選択したデータ構造に追加するステップと
を含むキャッシュ・マネージャと
を備えるシステム。
【請求項１３】
前記キャッシュ・マネージャによって実行される前記オペレーションが、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記取り出した要求されたデータを格納するために利用可能なスペースを前記第２コンピュータ可読媒体が有するかどうかを判定するステップと、
前記第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、前記データ構造のうちの１つから１つのエントリを選択するステップと、
前記第２コンピュータ可読媒体から前記選択したエントリに関するデータをデステージするステップと
をさらに含む請求項１２に記載のシステム。
【請求項１４】
前記第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、前記データ構造のうちの１つから１つのエントリを選択するステップが、
前記データ構造のランダムなサブセットを選択するステップと、
前記選択したランダムなサブセットから、その最も古いエントリが前記選択したサブセット内の任意の他のデータ構造内の最も古いエントリよりも新しくない１つのデータ構造を選択するステップと
を含む請求項１３に記載のシステム。
【請求項１５】
前記データ構造が最長時間未使用（ＬＲＵ）リストを含み、前記取り出したデータに関する前記エントリを追加するステップが、選択したＬＲＵリストの最短時間未使用（ＭＲＵ）端に前記エントリを追加するステップを含む請求項１２に記載のシステム。
【請求項１６】
前記データ構造がクロックを含み、各クロックが、リスト内で互いに隣接するヘッド・エントリおよびテール・エントリを有し、前記取り出したデータに関する前記エントリを追加するステップが、前記選択したクロックの前記ヘッド・エントリに前記エントリを追加するステップを含む請求項１２に記載のシステム。
【請求項１７】
前記クロック内の前記エントリは、前記エントリにアクセスされたかどうかを示し、前記キャッシュ・マネージャによって実行される前記オペレーションが、
前記要求されたデータに関するエントリが前記クロックのうちの１つの中に存在しないと判定したことに応答して、前記取り出した要求されたデータを格納するために利用可能なスペースを前記第２コンピュータ可読媒体が有するかどうかを判定するステップと、
前記クロックのうちの１つを選択するステップと、
アクセスされていないと示される前記クロック内の１つのエントリを求めるステップと、
前記求めたエントリに関するデータを前記第２コンピュータ可読媒体からデステージするステップと
をさらに含む請求項１６に記載のシステム。
【請求項１８】
第１コンピュータ可読媒体と通信するシステムであって、
プロセッサと、
第２コンピュータ可読媒体と、
前記第２コンピュータ可読媒体に追加された前記第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造と、
オペレーションを実行するように動作可能にされた前記第２コンピュータ可読媒体に対するアクセスを管理するキャッシュ・マネージャであって、前記オペレーションが、
前記第１コンピュータ可読媒体内のデータを求める要求を前記プロセッサから受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ要求に関して、前記第２コンピュータ可読媒体から前記要求されたデータにアクセスするステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記要求されたデータに関する１つのエントリが存在すると判定したことに応答して、前記要求されたデータに関する求めたエントリを選択された前記データ構造に移動するステップと
を含むキャッシュ・マネージャと
を備えるシステム。
【請求項１９】
コードを実装するプログラムであって、前記コードが、第１コンピュータ可読媒体および第２コンピュータ可読媒体にアクセスするようにオペレーションを実行させ、前記オペレーションが、
前記第２コンピュータ可読媒体に追加された前記第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造を提供するステップと、
前記第１コンピュータ可読媒体内のデータを求める要求を受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記第１コンピュータ可読媒体から前記要求されたデータを取り出し、前記第２コンピュータ可読媒体に格納するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在しないと判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記取り出したデータに関するエントリを前記選択したデータ構造に追加するステップと
を含むプログラム。
【請求項２０】
コードを実装するプログラムであって、前記コードが、第１コンピュータ可読媒体および第２コンピュータ可読媒体にアクセスするようにオペレーションを実行させ、前記オペレーションが、
前記第２コンピュータ可読媒体に追加された前記第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する複数のデータ構造を提供するステップと、
前記第１コンピュータ可読媒体内のデータを求める要求を受信するステップと、
前記要求されたデータに関するエントリが前記データ構造のうちの１つの中に存在するかどうかを判定するステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ要求に関して、前記第２コンピュータ可読媒体から前記要求されたデータにアクセスするステップと、
前記要求されたデータに関する１つのエントリが前記データ構造のうちの１つの中に存在すると判定したことに応答して、前記データ構造のうちの１つを選択するステップと、
前記要求されたデータに関する１つのエントリが存在すると判定したことに応答して、前記要求されたデータに関する求めたエントリを選択された前記データ構造に移動するステップと
を含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータ構造を使用してキャッシュ内のデータを管理する方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
キャッシュ管理システムは、記憶装置内に維持されるデータを、メモリ装置などのより高速なアクセス媒体に格納し、その結果、ストレージからのデータを求める要求に、より高速アクセスのキャッシュ・メモリから、より高速にサービスすることができる。キャッシュ管理システムは、ストレージからキャッシュにステージされたデータ単位ごとに１エントリを有するリンク・リストを維持することができる。一般的に使用される最長時間未使用（ＬＲＵ）キャッシュ技法では、キャッシュ内のデータにアクセスされた場合、すなわちキャッシュ「ヒット」の場合、アクセスされたデータに関するＬＲＵリスト内のエントリが、リストの最短時間未使用（ＭＲＵ）端に移動される。要求されたデータがキャッシュ内にない場合、すなわちキャッシュ・ミスである場合、そのエントリがリストのＬＲＵ端にあるキャッシュ内のデータを削除する（すなわちストレージにデステージする）ことができ、キャッシュにステージされた新しいデータに関するエントリがＬＲＵリストのＭＲＵ端に追加される。このＬＲＵキャッシュ技法では、より頻繁にアクセスされるデータがキャッシュにとどまる可能性が高く、一方あまり頻繁にアクセスされないデータがリストのＬＲＵ端から削除されて、新たにアクセスされるデータのためにキャッシュ内に空間が作成される可能性が高くなる。
【０００３】
複数のスレッド、またはマルチプロセッサ環境内の異なるプロセッサが同一のキャッシュからのデータにアクセスしている非同期コンピューティング環境では、ＭＲＵエントリがロックによって保護され、ＭＲＵエントリへのアクセスが直列化される。このことは、１つまたは複数のスレッドが、そのキャッシュ・ヒット・オペレーションまたはキャッシュ・ミス・オペレーションを完了するために、ＭＲＵエントリに対するロックを保持するスレッドを待機しなければならないことを意味する。マルチスレッド化環境では、すべてのキャッシュ・ヒットおよびキャッシュ・ミスはこのロックに対するアクセスを必要とするので、このロックに対する著しい量の競合が存在する。そのような競合は、仮想メモリ、データベース、ファイル・システム、およびストレージ・コントローラなどの高性能環境および高スループット環境にとって望ましくないと考えられる。
【０００４】
図１に、記憶装置からキャッシュされたデータを管理するために従来技術で周知のクロック・データ構造（または「クロック」）２を示す。クロック２は循環バッファを備える。クロックは、クロック２のヘッド・エントリ６とテール・エントリ８との間を指し示すクロック・ハンド４を含む。ストレージからのデータがヘッド・エントリ６に追加される。クロック・アルゴリズムは、クロック２のエントリすなわちページごとに「ページ参照ビット」を維持する。データが最初にストレージからキャッシュに運ばれたとき、キャッシュされたデータに関するエントリに対するページ参照ビットが０にセットされる。キャッシュ内のデータにアクセスされたとき、アクセスされたデータに関するページ参照ビットが１にセットされる。
【０００５】
キャッシュ内のデータをストレージから新たにアクセスされたデータと置き換えるために、クロック・ハンド４の所のヘッド・エントリ８がページ参照ビット０を有する場合、ヘッド・エントリ８に対応するデータがキャッシュからデステージされ、新しいページに関する情報がヘッド・エントリ６に追加される。現ヘッド・エントリ８に関するページ参照ビットが１である場合、ページ参照ビットが０にリセットされ、置き換えるためのページ参照ビット０を有するヘッド・エントリ８を見つけるまで、クロック・ハンド４がクロック２内を前方に移動する。仮想メモリ応用例では、ページ参照ビットをハードウェアで変更することができる。
【０００６】
クロック・キャッシュ技法の１つの利点は、ＬＲＵキャッシュ技法の場合のようにキャッシュ・ヒットに関するＭＲＵ位置にページを移動する必要がないことである。ＬＲＵキャッシュ技法は、アクセスされたデータに関するＬＲＵリスト内のエントリをＭＲＵ位置に移動するのにロックおよび直列化を必要とする。さらに、クロック・キャッシュ技法のヒット率は通常、ＬＲＵキャッシュ方法のヒット率に匹敵する。このため、クロック・キャッシュ技法の変形例が多くのオペレーティング・システムおよびアプリケーション・プログラムで使用されている。しかし、ページをクロック構造のヘッド・エントリ８に追加するとき、キャッシュ・ミスに関してロックが依然として必要である。したがって、ＬＲＵ技法とクロック・キャッシュ技法は共に、キャッシュ内のデータを置き換えるときにロック競合を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
こうした理由で、キャッシュ内のデータを管理する技法を提供することが当技術分野で求められている。
【課題を解決するための手段】
【０００８】
複数のデータ構造を使用してキャッシュ内のデータを管理する方法、システム、およびプログラムが提供される。複数のデータ構造がそれぞれ、第２コンピュータ可読媒体に追加された第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する。第１コンピュータ可読媒体内のデータを求める要求が受信される。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在するかどうかに関して判定が行われる。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在しないと判定したことに応答して、要求されたデータが第１コンピュータ可読媒体から取り出され、第２コンピュータ可読媒体に格納される。要求されたデータに関するエントリがデータ構造のうちの１つの中に存在しないと判定したことに応答して、データ構造のうちの１つが選択され、取り出されたデータに関するエントリが、選択されたデータ構造に追加される。
【０００９】
別の実施形態では、データ構造のうちの１つを選択することは、データ構造のうちの１つをランダムに選択することを含む。
【００１０】
別の実施形態では、要求されたデータに関するエントリがデータ構造のうちの１つの中に存在しないと判定したことに応答して、取り出された要求されたデータを格納するために利用可能なスペースを第２コンピュータ可読媒体が有するかどうかに関して判定が行われる。第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、データ構造のうちの１つから１つのエントリが選択される。選択されたエントリに関するデータが第２コンピュータ可読媒体からデステージされる。
【００１１】
別の実施形態では、第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、データ構造のうちの１つから１つのエントリを選択することは、最も古いエントリを有するデータ構造のうちの１つを求めることを含み、選択したエントリが、求めたデータ構造内の最も古いエントリを含む。
【００１２】
別の実施形態では、第２コンピュータ可読媒体が利用可能なスペースを有さないと判定したことに応答して、データ構造のうちの１つから１つのエントリを選択することは、データ構造のランダムなサブセットを選択すること、および選択したランダムなサブセットから、その最も古いエントリが選択したサブセット内の任意の他のデータ構造内の最も古いエントリよりも新しくない１つのデータ構造を選択することを含む。
【００１３】
別の実施形態では、データ構造は最長時間未使用（ＬＲＵ）リストを含み、取り出されたデータに関するエントリを追加することは、選択されたＬＲＵリストの最短時間未使用（ＭＲＵ）端にエントリを追加することを含む。
【００１４】
別の実施形態では、データ構造はクロックを含み、各クロックは、リスト内で互いに隣接するヘッド・エントリおよびテール・エントリを有し、取り出されたデータに関するエントリを追加することは、選択されたクロックのヘッド・エントリにエントリを追加することを含む。
【００１５】
別の実施形態では、クロック内のエントリは、エントリがアクセスされたかどうかを示す。要求されたデータに関するエントリがクロックのうちの１つの中に存在しないと判定したことに応答して、取り出された要求されたデータを格納するために利用可能なスペースを第２コンピュータ可読媒体が有するかどうかに関して判定が行われる。クロックのうちの１つが選択され、アクセスされていないと示されるクロック内の１つのエントリが求められる。求められたエントリに関するデータが、第２コンピュータ可読媒体からデステージされる。
【００１６】
別の実施形態では、複数のデータ構造がそれぞれ、第２コンピュータ可読媒体に追加された第１コンピュータ可読媒体からのデータを識別するエントリをそれぞれ有する。第１コンピュータ可読媒体内のデータを求める要求が受信され、要求されたデータに関するエントリがデータ構造のうちの１つの中に存在するかどうかに関して判定が行われる。要求されたデータに関する１つのエントリがデータ構造のうちの１つの中に存在すると判定したことに応答して、データ要求に関して、要求されたデータが第２コンピュータ可読媒体からアクセスされる。要求されたデータに関する１つのエントリがデータ構造のうちの１つの中に存在すると判定したことに応答して、データ構造のうちの１つが選択され、要求されたデータに関する１つのエントリが存在すると判定したことに応答して、要求されたデータに関する求められたエントリが、選択されたデータ構造に移動される。
【００１７】
別の実施形態では、要求されたデータに関する１つのエントリがデータ構造のうちの１つの中に存在すると判定したことに応答して、データ構造がランダムに選択される。
【００１８】
別の実施形態では、各データ構造が最長時間未使用（ＬＲＵ）リストおよびクロック・データ構造のうちの１つを含む１組のデータ構造のメンバである。
【発明を実施するための最良の形態】
【００１９】
図２にコンピューティング環境の一実施形態を示す。システム１２は１つまたは複数のプロセッサ１４ａ、１４ｂ．．．１４ｎを含み、各プロセッサ１４ａ、１４ｂ．．．１４ｎは、ストレージ１６内の記憶位置を対象とする入出力（Ｉ／Ｏ）要求をサブミットする。キャッシュ・マネージャ１８はＩ／Ｏ要求を処理し、プロセッサ１４ａ、１４ｂ．．．１４ｎによって要求されるデータを、メモリ２２に格納された複数の最長時間未使用（ＬＲＵ）リスト２０ａ、２０ｂ．．．２０ｎのうちの１つにキャッシュする。キャッシュ・マネージャ１８は、ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎを使用して、メモリ２２にキャッシュされたストレージ１６からのデータを管理し、ストレージ１６からデータをいつステージおよびデステージするかを判定し、キャッシュ・ヒットを最適化し、キャッシュ・ミスを最小限に抑える。各ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎは、最短時間未使用（ＭＲＵ）端２４ａ、２４ｂ．．．２４ｎおよびＬＲＵ端２６ａ、２６ｂ．．．２６ｎを含む。ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎで識別されるストレージ１６からアクセスされるデータが、メモリ２２にキャッシュされる。
【００２０】
キャッシュ・マネージャ１８はさらに、メモリ２２のキャッシュ内に維持されるストレージ６からのデータに関する情報を有するキャッシュ・インデックス２８を維持する。キャッシュ・インデックス２８は、ストレージ１６内の特定のアドレスまたは位置からのデータがＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのうちの１つの中のエントリで識別されるかどうかを示す。記憶アドレスまたは位置は、トラック、ブロック、ページ、またはストレージ１６内のデータの任意のその他のセグメントを含むことができる。
【００２１】
ストレージ１６は、１つまたは複数のディスク・ドライブなどの１つまたは複数の記憶装置、Justa Bunch of Disks (JBOD)、直接アクセス記憶装置（ＤＡＳＤ）、Redundant Array of Independent Disks(RAID)アレイ、仮想化装置、テープ・ストレージ、フラッシュ・メモリなどの記憶装置のアレイを含むことができる。メモリ２２は、ストレージ１６よりもスループットが高く、アクセスが高速である１つまたは複数のメモリ装置を含むことができる。代替実施形態では、メモリ２２およびストレージ１６は、当技術分野で周知の任意の適切なコンピュータ可読媒体を含むことができ、それによって、あるコンピュータ可読媒体が、Ｉ／Ｏ要求が対象とする別のコンピュータ可読媒体に対する高速アクセス・キャッシュとして機能する。プロセッサ１４ａ、１４ｂ．．．１４ｎは、別々のマイクロプロセッサ装置、あるいは１つまたは複数のマルチコア・マイクロプロセッサ装置上に実装された別々の処理コアを含むことができる。キャッシュ・マネージャ１８は、プロセッサ１４ａ、１４ｂ．．．１４ｎのうちの１つまたは複数によって実行されるコンピュータ・プログラムとして実装することができ、またはメモリ２２ハードウェア内に実装することができる。
【００２２】
一実施形態では、システム１２は、接続された複数のホストからストレージ１６に対する読取り要求および書込み要求を受信するストレージ・コントローラを備えることができる。
【００２３】
図３に、キャッシュ・インデックス２８内のキャッシュ・インデックス・エントリ３０の一実施形態を示し、キャッシュ・インデックス・エントリ３０は、記憶アドレスなどの記憶位置３２、キャッシュされた記憶位置３２に関するエントリを有するＬＲＵリスト１０ａ、１０ｂ．．．１０ｎを識別するＬＲＵリスト３４、およびキャッシュされた記憶位置３２に関して示されるＬＲＵリスト３４内のエントリ３６位置を示す。
【００２４】
キャッシュ・インデックス２８は、記憶位置３２のハッシュに基づいてそのエントリが索引付けされるハッシュ・テーブルを含むことができる。あるいは、キャッシュ・インデックス２８は、ハッシュ・テーブル以外の当技術分野で周知の適切なインデックス型データ構造として実装することもできる。
【００２５】
図４は、ストレージ１６からメモリ２２へのデータのキャッシングを管理するためにキャッシュ・マネージャ１８によって実行されるオペレーションの一実施形態を示す。（ブロック１００で）ストレージ１６内のデータにアクセスする要求、例えば読取り要求または書込み要求を受信した時、キャッシュ・マネージャ１８は、（ブロック１０２で）キャッシュ・インデックス２８を処理し、要求された記憶アドレスがＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのうちの１つの中にあるかどうかを判定する。キャッシュされるデータの記憶位置は、ブロック、トラック、ページ、またはストレージのセグメントのその他の単位を含むことができる。（ブロック１０４で）要求された記憶アドレスに関するキャッシュ・インデックス・エントリ３０（図３）が存在する場合、要求されたデータがキャッシュ内にあり、すなわち「キャッシュ・ヒット」となる。そのような場合、キャッシュ・マネージャ１８は、（ブロック１０６で）キャッシュ・インデックス２８から、フィールド３４からのＬＲＵリスト２０ａ、２０ｂ．．．２０ｎと、要求されたデータに関するリスト内のエントリ３６とを求める。一実施形態では、キャッシュ・マネージャ１８は、アクセスされたデータに関するエントリを、エントリが含まれる現ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのＭＲＵ端２４ａ、２４ｂ．．．２４ｎに移動することができる。代替実施形態では、キャッシュ・マネージャ１８は、（ブロック１０８で）ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎ（求めたエントリを既に含むＬＲＵリストを含むことがあり、または含まないことがある）のうちの１つを選択することができ、例えばランダムに選択することができ、（ブロック１１０で）要求されたデータに関する求めたエントリを、選択したＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのＭＲＵ端２４ａ、２４ｂ．．．２４ｎに移動することができる。
【００２６】
（ブロック１０４で）要求された記憶アドレスに関するキャッシュ・インデックス２８内のエントリが存在しない場合、要求されたデータはキャッシュ内に存在せず、すなわち「キャッシュ・ミス」となる。そのような場合、（ブロック１１２で）キャッシュ・メモリ２２が満杯でない場合、すなわち要求されたデータに関して利用可能なスペースを有する場合、キャッシュ・マネージャ１８は、（ブロック１１４で）要求されたデータをキャッシュ・メモリ２２内にステージする。キャッシュ・メモリ２２内にステージされたデータに関するＬＲＵリスト・エントリを作成するために、キャッシュ・マネージャ１８は、（ブロック１１６で）ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのうちの１つを例えばランダムに選択し、（ブロック１１８で）ステージされたデータに関するエントリを、選択したＬＲＵリスト２０ａ、２０ｂ．．．２０ｎのＭＲＵ端２４ａ、２４ｂ．．．２４ｎに追加する。エントリ３０（図３）も（ブロック１２０で）要求されたデータの記憶アドレスを含むキャッシュ・インデックス２８と、エントリ３０が追加される選択したＬＲＵリスト２０ａ、２０ｂ．．．２０ｎとに追加される。（ブロック１１２で）キャッシュが満杯である場合、すなわち要求されたデータに関して利用可能なスペースを有さない場合、データをデステージする必要がある。データをデステージするために、キャッシュ・マネージャ１８は、（ブロック１２４で）ランダムに選択したリストのサブセットを処理して、最も古いＬＲＵ２６ａ、２６ｂ．．．２６ｎエントリを有するランダムに選択したサブセットのリストを求めることにより、リストのうちの１つを選択する。各キャッシュ・エントリと共に、そのエントリに対する最後のアクセスの時刻を格納するタイムスタンプを維持することによって最も古いエントリを求めることができる。例えば、ｎ個のＬＲＵリストが存在する場合、ランダムに選択したリストのサブセットはｍ個のリストを含むことができる。一実施形態では、リストのサブセットすなわちｍは２でよい。次いで、キャッシュ・マネージャ１８は、（ブロック１２６で）ＬＲＵエントリ２６ａ．．．２６ｎに関するデータを選択したＬＲＵリスト２０ａ、２０ｂ．．．２０ｎからデステージする。データのデステージは、メモリ２２からデータを削除し、データに対する何らかの更新をストレージ１６に適用する。データをデステージした後、制御はブロック１１４に進み、要求されたデータをステージインする。ブロック１１０または１２０より、制御はブロック１２８に進み、要求されたデータを要求側プロセッサ１４ａ、１４ｂ．．．１４ｎに返す。
【００２７】
各ＬＲＵリストの間でエントリをランダムに分散させることにより、記載の実施形態は、同時にアクセスされる記憶位置が異なるＬＲＵリスト内のエントリを有する可能性を増加させて、データを要求するプロセッサ１４ａ、１４ｂ．．．１４ｎによるロック競合を回避しようとする。例えば、そのＬＲＵエントリが異なるＬＲＵリスト上にある記憶位置に対する２つの同時要求が存在する場合、２つの要求が同一のＬＲＵリスト内のＭＲＵエントリに対するアクセスを要求するときに生じるロック競合および直列化による遅延はない。しかし、２つの同時要求が、そのエントリが同一リスト上にあるデータに対するものである場合、ロック競合は依然として生じる可能性がある。それでも、記載の実施形態は、最後にアクセスしたエントリをＭＲＵ端ＬＲＵ端に対する別々のロックを有する複数のＬＲＵリストにわたってランダムに分散させることにより、ロック競合の可能性を大幅に低減する。
【００２８】
図５は、ＬＲＵリスト２０ａ、２０ｂ．．．２０ｎ（図２）を使用する代わりに、キャッシュ・マネージャ１８がクロック・データ構造（または「クロック」）１５０ａ、１５０ｂ．．．１５０ｎをメモリ１５２内に維持して、ストレージ１６からのデータをキャッシュ・メモリ１５２内で管理する代替実施形態である。各クロック１５０ａ、１５０ｂ．．．１５０ｎは、クロック１５０ａ、１５０ｂ．．．１５０ｎ内のクロック１５０ａ、１５０ｂ．．．１５０ｎのテール・エントリ１５６ａ、１５６ｂ．．．１５６ｎとヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎとの間の位置に対するポインタを与えるクロック・ハンド１５４ａ、１５４ｂ．．．１５４ｎを含む。キャッシュ・インデックス１６０は、クロックのうちの１つの中のエントリに対する記憶アドレスのインデックスを提供する。キャッシュ・インデックス１６０は、ハッシュ・テーブルまたはその他の適切なインデックス・データ構造を含むことができる。
【００２９】
図６は、キャッシュ・インデックス１６０内のエントリ１７０の一実施形態であり、エントリ１７０は、記憶アドレスなどの記憶位置１７２、記憶位置１７２に関するエントリを有するクロック１５０ａ、１５０ｂ．．．１５０ｎを識別するクロック１７４、および記憶位置１７２に関して示されるクロック１７４内のエントリ１７６を示す。
【００３０】
図７に、キャッシュ・メモリ１５２を管理するためにクロック１５０ａ、１５０ｂ．．．１５０ｎを使用してキャッシュ・マネージャ１８によって実行されるオペレーションの一実施形態を示す。（ブロック２００で）記憶アドレスを求める要求を受信した時、キャッシュ・マネージャ１８は、（ブロック２０２で）キャッシュ・インデックス１６０を処理し、要求されたデータがクロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つの中にあるかどうかを判定する。（ブロック２０４で）要求された記憶アドレスに関するキャッシュ・インデックス・エントリ１６０が存在する場合、すなわち「キャッシュ・ヒット」である場合、キャッシュ・マネージャ１８は、（ブロック２０６で）キャッシュ・インデックス１６０から、クロック１５０ａ、１５０ｂ．．．１５０ｎと、要求されたデータに関するクロック１５０ａ、１５０ｂ．．．１５０ｎ内のエントリ１７６（図６）とを求める。次いで、キャッシュ・マネージャ１８は、（ブロック２０８で）求めたエントリに関するエントリ・ビットをセットして、エントリがアクセスされたことを示し（例えば、ページ参照ビットを「１」にセットする）、（ブロック２１０で）要求されたデータを返す。（ブロック２０４で）キャッシュ・インデックス１６０が要求された記憶アドレスに関するエントリを含まない場合、すなわち「キャッシュ・ミス」である場合、かつ（ブロック２１２で）キャッシュ・メモリ１５２が満杯でない場合、すなわち要求されたデータに関して利用可能なスペースを有する場合、キャッシュ・マネージャ１８は、（ブロック２１４で）要求されたデータをキャッシュ・メモリ１５２にステージし、（ブロック２１６で）クロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つを選択する。クロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つはランダムに選択することができる。（ブロック２１８で）ステージしたデータに関するエントリ１７０（図６）が選択したクロック１５０ａ、１５０ｂ．．．１５０ｎのヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎに追加され、（ブロック２２０で）エントリがキャッシュ・インデックス１７０に追加される。このキャッシュ・インデックス・エントリ１７０は、要求されたデータの記憶アドレス１７２、選択したクロック１７４、およびメモリ１５２にステージされたデータに関する選択したクロック内のエントリを含む。ブロック２２０から、制御はブロック２１０に進み、データを返す。
【００３１】
（ブロック２１２で）メモリ・キャッシュ１５２が満杯である場合、すなわち要求されたデータに関して利用可能なスペースを有さない場合、キャッシュ・マネージャ１８は、（ブロック２２２で）クロック１５０ａ、１５０ｂ．．．１５０ｎのサブセットをランダムに選択して、ランダムに選択したサブセットの最大のクロック、すなわち最も多くのエントリ１７０を有するクロックを求め、最も多くのエントリを有するクロックであるそのクロックからエントリを削除することにより、クロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つを選択することができる。各クロックについて、クロック内のエントリの数を示すカウンタが維持される。カウンタを使用して、１組のクロックの中から、最大のクロック、すなわち最も多くのエントリを含むクロックを求めることができる。あるいは、キャッシュ・マネージャ１８は、キャッシュ・ミスのためにメモリ１５２にステージされるデータに関するエントリで更新すべきクロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つをランダムに選択することもできる。
【００３２】
（ブロック２２４で）選択したクロック・セット１５０ａ、１５０ｂ．．．１５０ｎのクロック・ハンド１５４ａ、１５４ｂ．．．１５４ｎの所のヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎがアクセスされたと示される場合、すなわちそのエントリに関するページ参照ビットが「１」にセットされる場合、キャッシュ・マネージャ１８は、（ブロック２２６で）記憶アドレスがアクセスされていないことを示すようにエントリ１７０に関するビットを例えば「０」にセットして、クロック・ハンド１５４ａ、１５４ｂ．．．１５４ｎを１エントリ前方に移動し、その結果、以前のヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎが今度は新しいクロック・ハンド位置のテール・エントリ１５６ａ、１５６ｂ．．．１５６ｎとなる。「未アクセス」、例えば「０」を示すようにエントリに関するビットをリセットした後、（ブロック２２６で）制御はブロック２２４に戻り、その結果、エントリが最近アクセスされていないこと、例えばページ参照ビットが０であることをそのアクセス・ビットが示すヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎに達するまで、クロック・ハンド１５４ａ、５４ｂ．．．１５４ｎは前方に移動し続ける。
【００３３】
（ブロック２２４で）キャッシュ内の記憶アドレスがアクセスされていないこと、例えばページ参照ビットが０であることをクロック・ハンド１５４ａ、１５４ｂ．．．１５４ｎの所のヘッド・エントリ１５８ａ、１５８ｂ．．．１５８ｎが示す場合、キャッシュ・マネージャ１８は、（ブロック２２８で）ヘッド・エントリ１５６ａ、１５６ｂ．．．１５６ｎに関するデータが修正された場合、そのデータをキャッシュ・メモリ１５２からストレージ１６にデステージする。データが修正されていない場合、データを廃棄することができる。次いで、制御はブロック２１４に進み、要求されたデータをステージインし、要求されたデータに関するエントリをクロック１５０ａ、１５０ｂ．．．１５０ｎのうちの１つに追加し、要求されたデータを返す。
【００３４】
各クロック・データ構造の間でエントリをランダムに分散させることにより、記載の実施形態は、同時にアクセスされる記憶位置が異なるクロック内のエントリを有する可能性を増加させて、キャッシュ・ミスがあるときにプロセッサ１４ａ、１４ｂ．．．１４ｎによるロック競合を回避しようとする。例えば、そのクロック・エントリが異なるクロック上にある記憶位置に対する２つの同時要求が存在する場合、キャッシュ・ミスが存在する場合にロック競合および直列化による遅延はない。キャッシュ・ミスに対して、キャッシュにステージされるデータに関して異なるクロックを別々に更新することができるからである。記載の実施形態は、最後にアクセスしたエントリを別々のロックを有する複数のクロックにわたってランダムに分散させることにより、ロック競合の可能性を大幅に低減する。さらに、複数のリストの使用は、ロッキング遅延を回避することによってシステム転送スループットを改善する。
【００３５】
追加の実施形態の詳細
ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組合せを生成するための標準プログラミング技法または標準エンジニアリング技法あるいはその両方を使用する方法、装置、または製品(article of manufacture)、さらにはプログラムとして記載のオペレーションを実装することができる。「コンピュータ可読媒体」内に維持されるコードとして記載のオペレーションを実装することができる。プロセッサは、コンピュータ可読媒体からコードを読み取り、実行することができる。コンピュータ可読媒体は、磁気記憶媒体（例えばハード・ディスク・ドライブ、フロッピィ・ディスク、テープなど）、光学式ストレージ（ＣＤ−ＲＯＭ、ＤＶＤ、光ディスクなど）、揮発性および不揮発性メモリ装置（例えばＥＥＰＲＯＭ、ＲＯＭ、ＰＲＯＭ、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭ、フラッシュ・メモリ、ファームウェア、プログラマブル論理など）の媒体を含むことができる。さらに、記載のオペレーションを実装するコードを、ハードウェア論理（例えば集積回路チップ、プログラマブル・ゲート・アレイ（ＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）など）として実装することができる。さらに、記載のオペレーションを実装するコードを「伝送信号」として実装することができる。伝送信号は、空間を介して、または光ファイバ、銅線などの伝送媒体を介して伝播することができる。コードまたは論理がその中に符号化される伝送信号は、ワイヤレス信号、衛星伝送、電波、赤外線信号、Bluetoothなどをさらに含むことができる。コードまたは論理がその中に符号化される伝送信号は、送信局で送信することができ、受信局で受信することができ、伝送信号内に符号化されるコードまたは論理は、受信側および送信側の局または装置で復号化し、ハードウェアまたはコンピュータ可読媒体内に格納することができる。「製品」は、コードをその中に実装することのできるコンピュータ可読媒体、ハードウェア論理、または伝送信号、あるいはそれらの組合せを含む。記載のオペレーションの実施形態を実装するコードがその中に符号化される装置は、コンピュータ可読媒体またはハードウェア論理を含むことができる。もちろん、本発明の範囲から逸脱することなくこの構成に対して多くの修正を行えること、および製品が当技術分野で周知の適切な情報運搬媒体を含むことができることを当業者は理解されよう。
【００３６】
記載の実施形態では、キャッシュ内のデータに関するエントリを格納するのに使用されるデータ構造は、ＬＲＵリストまたはクロックを含んだ。代替実施形態では、追加の適切なデータ構造を使用して情報のエントリを格納し、キャッシュ内のデータを管理することができる。さらに、記載の実施形態では、エントリを格納するのに使用されるデータ構造が、同じタイプの例えばＬＲＵリスト、クロックであった。代替実施形態では、キャッシュ・エントリを格納するのに使用される複数のデータ構造は混合タイプでよい。
【００３７】
「一実施形態」、「実施形態」、「１つまたは複数の実施形態」、および「一部の実施形態」という用語は、明白に指定されるのでない限り「本発明の１つまたは複数の（しかしすべてではない）実施形態」を意味する。
【００３８】
「含む」、「備える」、「有する」という用語、およびそれらの変形は、明白に指定されるのでない限り「含むが、それに限定されない(including but not limited to)」を意味する。
【００３９】
列挙した項目の一覧表は、明白に指定されるのでない限り、項目のいずれかまたはすべてが相互排他的であることを示唆しない。
【００４０】
「a」、「an」、および「the」は、明白に指定されるのでない限り、「１つまたは複数」を意味する。
【００４１】
変数「ｎ」および「ｍ」は、要素の可変数を表すのに使用されるときに、要素の任意の数の例を示すことがあり、異なる要素と共に使用されるときに、異なる整数を表すことがある。
【００４２】
互いに通信する装置は、明白に指定されるのでない限り、互いに連続的に通信する必要はない。さらに、互いに通信する装置は、１つまたは複数の媒介を介して直接的または間接的に通信することができる。
【００４３】
互いに通信するいくつかの構成要素を有する一実施形態の記述は、すべてのそのような構成要素が必要であることを示唆しない。逆に、本発明の可能な多種多様な実施形態を示すのに様々な任意選択の構成要素が記述される。
【００４４】
さらに、プロセス・ステップ、方法ステップ、アルゴリズムなどが順番に記述されることがあるが、そのようなプロセス、方法、およびアルゴリズムを代替の順序で機能するように構成することができる。言い換えれば、記述される何らかのシーケンスまたは順序のステップは、必ずしも、ステップがその順序で実施されるという要件を示すわけではない。本明細書に記載のプロセスのステップは、実用的な任意の順序で実施することができる。さらに、一部のステップを同時に実施することができる。
【００４５】
単一の装置または物品が本明細書で説明されるとき、複数の装置／物品（それらが協働するか否かに関わらず）を単一の装置／物品の代わりに使用できることを容易に理解されよう。同様に、複数の装置または物品が本明細書で説明される場合に（それらが協働するか否かに関わらず）、その複数の装置または物品の代わりに単一の装置／物品を使用することができ、あるいは図示される数の装置またはプログラムの代わりに異なる数の装置／物品を使用できることを容易に理解されよう。装置の機能または特徴あるいはその両方を、そのような機能／特徴を有するものとして明示的には説明されていない１つまたは複数の他の装置で代替的に実施することができる。したがって、本発明の他の実施形態は、装置自体を含む必要がない。
【００４６】
図示される図４および７のオペレーションは、一定のイベントが一定の順序で生じることを示す。代替実施形態では、一定のオペレーションを異なる順序で実行することができ、修正または除去することができる。さらに、上述の論理にステップを追加することができ、ステップは、依然として記載の実施形態に準拠することができる。さらに、本明細書に記載のオペレーションを順次行うことができ、または一定のオペレーションを並列に処理することができる。さらに、オペレーションを単一の処理装置または分散処理装置で実行することができる。
【００４７】
上記の本発明の様々な実施形態の説明を例示および説明のために提示した。これは網羅的なものではなく、本発明を開示の厳密な形態に限定するものでもない。上記の教示に照らして多数の修正形態および変形形態が可能である。本発明の範囲はこの詳細な説明によって限定されるのではなく、本明細書に添付の特許請求の範囲によって限定されるものとする。上記の仕様、例、およびデータは、本発明の構成の製造および使用の完全な説明を与える。本発明の精神および範囲から逸脱することなく本発明の多数の実施形態を作成することができるので、本発明は本明細書に添付の特許請求の範囲に属する。
【図面の簡単な説明】
【００４８】
【図１】キャッシュ管理のために使用される従来技術のクロック・データ構造を示す図である。
【図２】コンピューティング環境の一実施形態を示す図である。
【図３】図２のコンピューティング環境内でキャッシュを管理するのに使用されるインデックス・エントリの一実施形態を示す図である。
【図４】図２および３のデータ構造を使用してキャッシュを管理するためのオペレーションの一実施形態を示す図である。
【図５】キャッシュを管理するのに使用されるメモリ内の構成要素の一実施形態を示す図である。
【図６】図５のメモリと共にキャッシュを管理するのに使用されるインデックス・エントリの一実施形態を示す図である。
【図７】図５および６のデータ構造を使用してキャッシュを管理するためのオペレーションの一実施形態を示す図である。
【符号の説明】
【００４９】
２  クロック・データ構造
４  クロック・ハンド
６  ヘッド・エントリ
８  テール・エントリ
１２  システム
１４ａ、１４ｂ．．．１４ｎ  プロセッサ
１６  ストレージ
１８  キャッシュ・マネージャ
２０ａ、２０ｂ．．．２０ｎ  最長時間未使用（ＬＲＵ）リスト
２２  メモリ
２４ａ、２４ｂ．．．２４ｎ  最短時間未使用（ＭＲＵ）端
２６ａ、２６ｂ．．．２６ｎ  ＬＲＵ端
２８  キャッシュ・インデックス
３０  キャッシュ・インデックス・エントリ
３２  記憶位置
３４  ＬＲＵリスト
３６  エントリ
１５０ａ、１５０ｂ．．．１５０ｎ  クロック・データ構造
１５２  キャッシュ・メモリ
１５４ａ、１５４ｂ．．．１５４ｎ  クロック・ハンド
１５６ａ、１５６ｂ．．．１５６ｎ  テール・エントリ
１５８ａ、１５８ｂ．．．１５８ｎ  ヘッド・エントリ
１６０  キャッシュ・インデックス
１７０  エントリ
１７２  記憶位置
１７４  クロック
１７６  エントリ
【図１】
2008027444.tif 000003
【図２】
2008027444.tif 000004
【図３】
2008027444.tif 000005
【図４】
2008027444.tif 000006
【図５】
2008027444.tif 000007
【図６】
2008027444.tif 000008
【図７】
2008027444.tif 000009