(57)【特許請求の範囲】
【請求項１】
シーケンシャル・アクセス記憶媒体に格納されているトラックに関連してシステムから読み出し要求および書き込み要求を受け取るシーケンシャル・アクセス・ストレージ・デバイスにおいてデータを管理するためのプログラムであって、
受け取られた改変済みトラックを、前記改変済みトラックをキャッシュすると決定したことに応答して、前記シーケンシャル・アクセス・ストレージ・デバイスと統合されている不揮発性ストレージ・デバイスにキャッシュすることと、
改変済みトラックを有する書き込み要求を受け取ることと、
前記受け取られた書き込み要求の属性が条件を満たすか否か判定することであって、前記条件は前記属性がシーケンシャル書き込み要求であることを含み、前記判定される属性は、もし前記書き込み要求がノンシーケンシャル書き込み要求を含むならば、前記条件を満たさないと、判定することと、
前記判定される属性が前記条件を満たさないと判定したことに応答して、前記書き込み要求のための前記受け取られた改変済みトラックを前記不揮発性ストレージ・デバイスにキャッシュすることと、
前記条件を満たさない前記判定される属性を有する前記受け取られた書き込み要求のためにデステージング要求を要求キューに加えることと、
前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックを、前記条件を満たさない前記属性を有する書き込み要求のための改変済みトラックより高い優先順位で書き込むことと、
をコンピュータに実行させるプログラム。
【請求項２】
前記不揮発性ストレージ・デバイスは前記シーケンシャル・アクセス記憶媒体より高速のアクセスのデバイスである、請求項１に記載のプログラム。
【請求項３】
前記シーケンシャル・アクセス・ストレージ・デバイスはバッファを含むハード・ディスク・ドライブを含み、前記不揮発性ストレージ・デバイスは前記バッファを含むデバイスとは別のフラッシュ・デバイスを含み、前記シーケンシャル・アクセス記憶媒体は少なくとも１つの磁気ディスクを含み、前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックは、前記不揮発性ストレージ・デバイスに格納されることなく、前記シーケンシャル・アクセス記憶媒体に書き込まれるまで前記バッファに格納される、請求項１に記載のプログラム。
【請求項４】
前記コンピュータに、
前記不揮発性ストレージ・デバイス内の前記改変済みトラックを、前記シーケンシャル・アクセス記憶媒体におけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することと、
前記要求キュー内のデステージング要求を処理することに応答して、前記不揮発性ストレージ・デバイスから前記シーケンシャル・アクセス記憶媒体へデステージングされるべき改変済みトラックとして、書き込みヘッドの現在の位置と前記空間的インデックスにおいて示されている前記シーケンシャル・アクセス記憶媒体上の前記改変済みトラックの物理的位置の比較に基づいて、前記書き込みヘッドの現在の位置から最小の時間で書き込まれ得る改変済みトラックを選択することとをさらに実行させ、前記条件を満たす前記判定される属性を有する書き込み要求では、選択された前記改変済みトラックが前記シーケンシャル・アクセス記憶媒体に書き込まれる、
請求項１に記載のプログラム。
【請求項５】
前記判定される属性は前記受け取られた書き込み要求の一部としての書き込まれるべきブロックの数を含み、前記判定される属性は、もし書き込まれるべきブロックの前記判定された数がブロックのスレショルド数より大きければ前記条件を満たし、もしブロックの前記判定された数がブロックの前記スレショルド数より小さければ前記条件は満たされない、請求項１に記載のプログラム。
【請求項６】
前記判定される属性は第１属性を含み、前記判定される条件は第１条件を含み、
前記コンピュータに、
前記第１属性が前記第１条件を満たすと判定したことに応答して前記書き込み要求の第２属性を判定することと、
前記第２属性が第２条件を満たすか否か判定することと、
前記判定される第２属性が前記第２条件を満たすと判定したことに応答して、前記書き込み要求をバイパス・キューに加えるとともに、前記受け取られた改変済みトラックをバッファにキャッシュすることと、
前記第１条件を満たさない前記判定される第１属性を有する前記書き込み要求ならびに前記第１条件を満たす前記第１属性を有するけれども前記第２条件を満たさない前記第２属性を有する書き込み要求のためにデステージング要求を前記要求キューに加えることとをさらに実行させ、前記第１条件を満たす前記判定される第１属性と前記第２条件を満たす前記判定される第２属性とを有する前記書き込み要求のための前記受け取られた改変済みトラックは、前記第１条件を満たさない前記第１属性を有する書き込み要求のための改変済みトラックならびに前記第１条件を満たす前記第１属性を有するけれども前記第２条件を満たさない前記第２属性を有する書き込み要求のための改変済みトラックよりも高い優先順位で書き込まれる、
請求項１に記載のプログラム。
【請求項７】
前記判定される第１属性は前記書き込み要求がシーケンシャル書き込みであるのかノンシーケンシャル書き込みであるのかを示し、前記判定される第１属性は、もし前記第１属性がシーケンシャル書き込み要求であるならば前記第１条件を満たし、もし前記第１属性がノンシーケンシャル書き込み要求であるならば前記第１条件は満たされず、前記第２属性は前記受け取られた書き込み要求の一部としての書き込まれるべきブロックの数を含み、前記判定される第２属性は、もし書き込まれるべきブロックの前記判定された数がブロックのスレショルド数より大きければ前記第２条件を満たし、もしブロックの前記判定された数がブロックの前記スレショルド数より小さければ前記第２条件は満たされない、請求項６に記載のプログラム。
【請求項８】
前記コンピュータに、
前記要求キュー内の１つの書き込み要求の処理を完了したことに応答して、バイパス・キューが空であるか否かを判定し、前記バイパス・キューが少なくとも１つの書き込み要求を有することに応答して前記バイパス・キュー内の１つの書き込み要求を処理すること、
をさらに実行させる、請求項１に記載のプログラム。
【請求項９】
前記コンピュータに、
前記バイパス・キュー内の第１所定数の書き込み要求が処理されると、前記要求キュー内の第２所定数の要求を処理することを実行させる、
請求項８に記載のプログラム。
【請求項１０】
シーケンシャル・アクセス記憶媒体に格納されているトラックに関連してシステムから読み出し要求および書き込み要求を受け取るシーケンシャル・アクセス・ストレージ・デバイスにおいてデータを管理する方法であって、
受け取られた改変済みトラックを、前記改変済みトラックをキャッシュすると決定したことに応答して、前記シーケンシャル・アクセス・ストレージ・デバイスと統合されている不揮発性ストレージ・デバイスにキャッシュすることと、
改変済みトラックを有する書き込み要求を受け取ることと、
前記受け取られた書き込み要求の属性が条件を満たすか否か判定することであって、前記条件は前記属性がシーケンシャル書き込み要求であることを含み、前記判定される属性は、もし前記書き込み要求がノンシーケンシャル書き込み要求を含むならば、前記条件を満たさないと、判定することと、
前記判定される属性が前記条件を満たさないと判定したことに応答して、前記書き込み要求のための前記受け取られた改変済みトラックを前記不揮発性ストレージ・デバイスにキャッシュすることと、
前記条件を満たさない前記判定される属性を有する前記受け取られた書き込み要求のためにデステージング要求を要求キューに加えることと、
前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックを、前記条件を満たさない前記属性を有する書き込み要求のための改変済みトラックより高い優先順位で書き込むことと、
を含む、方法。
【請求項１１】
前記シーケンシャル・アクセス・ストレージ・デバイスはバッファを含むハード・ディスク・ドライブを含み、前記不揮発性ストレージ・デバイスは前記バッファを含むデバイスとは別のフラッシュ・デバイスを含み、前記シーケンシャル・アクセス記憶媒体は少なくとも１つの磁気ディスクを含み、前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックは、前記不揮発性ストレージ・デバイスに格納されることなく、前記シーケンシャル・アクセス記憶媒体に書き込まれるまで前記バッファに格納される、請求項１０に記載の方法。
【請求項１２】
前記不揮発性ストレージ・デバイス内の前記改変済みトラックを、前記シーケンシャル・アクセス記憶媒体におけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することと、
前記要求キュー内のデステージング要求を処理することに応答して、前記不揮発性ストレージ・デバイスから前記シーケンシャル・アクセス記憶媒体へデステージングされるべき改変済みトラックとして、書き込みヘッドの現在の位置と前記空間的インデックスにおいて示されている前記シーケンシャル・アクセス記憶媒体上の前記改変済みトラックの物理的位置の比較に基づいて、前記書き込みヘッドの現在の位置から最小の時間で書き込まれ得る改変済みトラックを選択することとをさらに含み、前記条件を満たす前記判定される属性を有する書き込み要求では、選択された前記改変済みトラックが前記シーケンシャル・アクセス記憶媒体に書き込まれる、
請求項１０に記載の方法。
【請求項１３】
前記判定される属性は前記受け取られた書き込み要求の一部としての書き込まれるべきブロックの数を含み、前記判定される属性は、もし書き込まれるべきブロックの前記判定された数がブロックのスレショルド数より大きければ前記条件を満たし、もしブロックの前記判定された数がブロックの前記スレショルド数より小さければ前記条件は満たされない、請求項１０に記載の方法。
【請求項１４】
前記判定される属性は第１属性を含み、前記判定される条件は第１条件を含み、
前記第１属性が前記第１条件を満たすと判定したことに応答して前記書き込み要求の第２属性を判定することと、
前記第２属性が第２条件を満たすか否か判定することと、
前記判定される第２属性が前記第２条件を満たすと判定したことに応答して、前記書き込み要求をバイパス・キューに加えるとともに、前記受け取られた改変済みトラックをバッファにキャッシュすることと、前記第１条件を満たさない前記判定される第１属性を有する前記書き込み要求ならびに前記第１条件を満たす前記第１属性を有するけれども前記第２条件を満たさない前記第２属性を有する書き込み要求のためにデステージング要求を前記要求キューに加えることとをさらに含み、前記第１条件を満たす前記判定される第１属性と前記第２条件を満たす前記判定される第２属性とを有する前記書き込み要求のための前記受け取られた改変済みトラックは、前記第１条件を満たさない前記第１属性を有する書き込み要求のための改変済みトラックならびに前記第１条件を満たす前記第１属性を有するけれども前記第２条件を満たさない前記第２属性を有する書き込み要求のための改変済みトラックよりも高い優先順位で書き込まれる、
請求項１０に記載の方法。
【請求項１５】
前記判定される第１属性は前記書き込み要求がシーケンシャル書き込みであるのかノンシーケンシャル書き込みであるのかを示し、前記判定される第１属性は、もし前記第１属性がシーケンシャル書き込み要求であるならば前記第１条件を満たし、もし前記第１属性がノンシーケンシャル書き込み要求であるならば前記第１条件は満たされず、前記第２属性は前記受け取られた書き込み要求の一部としての書き込まれるべきブロックの数を含み、前記判定される第２属性は、もし書き込まれるべきブロックの前記判定された数がブロックのスレショルド数より大きければ前記第２条件を満たし、もしブロックの前記判定された数がブロックの前記スレショルド数より小さければ前記第２条件は満たされない、請求項１４に記載の方法。
【請求項１６】
システムからトラックのための読み出し要求および書き込み要求を受け取るストレージ・デバイスであって、
トラックを記憶するシーケンシャル・アクセス記憶媒体と、
不揮発性ストレージ・デバイスと、
操作を行うべく実行するコンピュータ可読プログラム・コードがその中に具体化されているコンピュータ可読記憶媒体とを含み、前記操作は、
受け取られた改変済みトラックを、前記改変済みトラックをキャッシュすると決定したことに応答して、前記不揮発性ストレージ・デバイスにキャッシュすることと、
改変済みトラックを有する書き込み要求を受け取ることと、
前記受け取られた書き込み要求の属性が条件を満たすか否か判定することであって、前記条件は前記属性がシーケンシャル書き込み要求であることを含み、前記判定される属性は、もし前記書き込み要求がノンシーケンシャル書き込み要求を含むならば、前記条件を満たさないと、判定することと、
前記判定される属性が前記条件を満たさないと判定したことに応答して、前記書き込み要求のための前記受け取られた改変済みトラックを前記不揮発性ストレージ・デバイスにキャッシュすることと、
前記条件を満たさない前記判定される属性を有する前記受け取られた書き込み要求のためにデステージング要求を要求キューに加えることと、
前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックを、前記条件を満たさない前記属性を有する書き込み要求のための改変済みトラックより高い優先順位で書き込むことと、
を含む、ストレージ・デバイス。
【請求項１７】
前記ストレージ・デバイスはバッファを含むハード・ディスク・ドライブを含み、前記不揮発性ストレージ・デバイスは前記バッファを含むデバイスとは別のフラッシュ・デバイスを含み、前記シーケンシャル・アクセス記憶媒体は少なくとも１つの磁気ディスクを含み、前記条件を満たす前記判定される属性を有する前記書き込み要求のための前記受け取られた改変済みトラックは、前記不揮発性ストレージ・デバイスに格納されることなく、前記シーケンシャル・アクセス記憶媒体に書き込まれるまで前記バッファに格納される、請求項１６に記載のストレージ・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シーケンシャル・アクセス・ストレージ・デバイス内の不揮発性ストレージ・キャッシュを含む複数のキャッシュを有するストレージ・システムにおいてデータをどこにキャッシュするかを決定するために書き込み要求の属性を使用するためのコンピュータ・プログラム製品（プログラム）、システム、および方法に関する。
【背景技術】
【０００２】
キャッシュ管理システムは、読み出し操作および書き込み操作の結果として最近アクセスされたストレージ・デバイス内のトラックを、その要求されたトラックを記憶しているストレージ・デバイスよりも高速なアクセスの、メモリ等のストレージ・デバイスにバッファリングする。より高速なアクセスのキャッシュ・メモリ内のトラックに対する爾後の読み出し要求は、要求されたトラックをより低速のアクセスのストレージから返すよりも速い速度で返され、従って読み出し待ち時間を短縮する。キャッシュ管理システムは、ストレージ・デバイスに向けられた改変済みトラックがキャッシュ・メモリに書き込まれたとき、改変済みトラックがハード・ディスク・ドライブ等のストレージ・デバイスへ完全に書き込まれる前に、書き込み要求に対するコンプリートを返すこともできる。ストレージ・デバイスへの書き込み待ち時間は、通例、キャッシュ・メモリへの書き込みのための待ち時間より著しく長い。従って、キャッシュを使用すれば書き込み待ち時間も短縮される。
【０００３】
キャッシュ管理システムは、キャッシュに格納されている各トラックのために１つのエントリを有するリンク・リストを維持することができ、それは、ストレージ・デバイスへ書き込む前にキャッシュにバッファリングされた書き込みデータまたは読み出しデータを含むことができる。一般的に使用される最長時間未使用（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ（ＬＲＵ））キャッシュ手法では、キャッシュ内のトラックがアクセスされると、すなわちキャッシュ“ヒット”ならば、アクセスされるトラックのためのＬＲＵリスト内のエントリは該リストの最短時間未使用（Ｍｏｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ（ＭＲＵ））エンドへ移される。要求されたトラックがキャッシュ内に存在しなければ、すなわちキャッシュ・ミスならば、そのエントリが該リストのＬＲＵエンドに存在するキャッシュ内のトラックが除去（あるいはストレージにデステージング）されることができ、ストレージからキャッシュへステージングされるトラック・データのためのエントリがＬＲＵリストのＭＲＵエンドに加えられる。このＬＲＵキャッシュ手法では、より頻繁にアクセスされるトラックはキャッシュに残留しやすく、あまり頻繁にはアクセスされないデータは、新たにアクセスされるトラックのためにキャッシュ内に空間を作るために該リストのＬＲＵエンドからより除去されやすいであろう。
【０００４】
ＬＲＵキャッシュ手法は、デステージング操作の数を最小にするためにすぐに再書き込みされる可能性の最も小さいトラックをデステージングするように時間的ローカリティを最適化しようとする、すなわち、デステージングされない書き込みがオーバーライトされるならば、そのオーバーライトされる書き込みのデステージングが回避され、それによりデータをキャッシュからディスクへ書き込む時間および労力を節約する。一方、空間的ローカリティを利用する仕方でデステージングを行いたいという希望もあり、そのことは、書き込まれるべき次の記憶場所に到達するためにストレージ・デバイス書き込みメカニズムおよび記憶媒体が動かされなければならない距離を最小にするために互いに最も近い記憶場所にデータが書き込まれるということを意味する。
【０００５】
時間的ローカリティおよび空間的ローカリティの両方を利用するための１つの手法はワイズ・オーダリング・フォー・ライツ（Ｗｉｓｅ  Ｏｒｄｅｒｉｎｇ  ｆｏｒ  Ｗｒｉｔｅｓ（ＷＯＷ））アルゴリズムである。ＷＯＷアルゴリズムは円形リンク・リストまたはクロックを使用し、該円形リンク・リストはキャッシュにバッファリングされている各書き込み要求について１つのエントリを有する。エントリは、該リンク・リストにおいて、空間的ローカリティの利益を利用するために関連する書き込み要求が向けられる記憶場所に応じて配列される。さらに、各エントリは、キャッシュ内の該記憶場所のための書き込みデータが最近更新されたか否かを示すビットを含む。エントリのための該ビットは、そのエントリのための書き込みデータが更新されるとセットされる。ポインタが、該円形リンク・リスト内の現在のエントリを指す。ＷＯＷアルゴリズムを使用するタスクは、ポインタによりアドレス指定されたエントリにアクセスする。キャッシュ内の該エントリのためのデータが最近更新されたことを該エントリのためのビットが示すならば、該ビットは、該書き込みデータが最近更新されていないことを示すようにセットされ、ポインタは、前に書き込まれた記憶場所の空間的近傍において次に最も近い記憶場所への書き込みデータを有するエントリが考慮されるように次のエントリを指すようにインクリメントされる。最後に書き込まれた記憶場所の空間的近傍において最も近くて、該エントリのための書き込みデータが最近更新されていないことをそのビットが示しているエントリが書き込みのために選択される。
【０００６】
このように、ＷＯＷアルゴリズムでは、最後にデステージングされた書き込み要求に空間的近傍において最も近い書き込まれるべき次のエントリが考慮されるべく選択されるので、空間的ローカリティが利用される。さらに、最近書き込まれたエントリは、ポインタがそのスキップされたエントリを考慮するべく回り戻ってくるまではスキップされるので、時間的ローカリティが利用される。
【０００７】
ディスク・ドライブは、書き込みトラックの線形位置および角度位置の両方を考慮するとともに、最小総サービス時間を決定するために現在の書き込みヘッド位置に関して両方を最適化するＷＯＷアルゴリズムおよび他のアルゴリズムを実行することができる。このプロセスは“シークおよび回転最適化に基づくコマンド再配列（ｃｏｍｍａｎｄ  ｒｅ−ｏｒｄｅｒｉｎｇ  ｂａｓｅｄ  ｏｎ  ｓｅｅｋ  ａｎｄ  ｒｏｔａｔｉｏｎａｌ  ｏｐｔｉｍｉｚａｔｉｏｎ）”と称される。ディスク・ドライブのロジック・ボードは、複数の書き込み要求を分析して、書き込まれるべきトラックの種々のシリンダおよび角度位置へシークするためにどれだけの時間がかかるか、およびヘッドの下で該データが回転するのを待つ間にどれだけの時間が経過するかの両方に基づいて、先にどれを行うかを決定する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
当該技術において、ストレージ・システムでキャッシュを使用する改善された手法に対するニーズが存在する。
【課題を解決するための手段】
【０００９】
シーケンシャル・アクセス・ストレージ・デバイス内の不揮発性ストレージ・キャッシュを含む複数のキャッシュを有するストレージ・システムにおいてデータをどこにキャッシュするかを決定するために書き込み要求の属性を使用するためのコンピュータ・プログラム製品、システム、および方法が提供される。受け取られた改変済みトラックは、その改変済みトラックをキャッシュするという決定に応答して該シーケンシャル・アクセス・ストレージ・デバイスと統合されている該不揮発性ストレージ・デバイスにキャッシュされる。改変済みトラックを有する書き込み要求が受け取られる。その受け取られた書き込み要求の属性が条件を満たすか否かが判定される。その書き込み要求のための受け取られた改変済みトラックは、該判定される属性が該条件を満たさないと判定したことに応答して該不揮発性ストレージ・デバイスにキャッシュされる。該条件を満たさない該判定される属性を有する該受け取られた書き込み要求のためにデステージング要求が要求キューに加えられる。該条件を満たす該判定された属性を有する書き込み要求のための受け取られた改変済みトラックは、該条件を満たさない該属性を有する書き込み要求のための改変済みトラックより高い優先順位で書き込まれる。
【図面の簡単な説明】
【００１０】
【図１】コンピューティング環境の実施態様を示す。
【図２】第１キャッシュ管理情報の実施態様を示す。
【図３】第２キャッシュ管理情報の実施態様を示す。
【図４】シーケンシャル・アクセス・ストレージ・デバイスの実施態様を示す。
【図５】第１キャッシュ制御ブロックの実施態様を示す。
【図６】第２キャッシュ制御ブロックの実施態様を示す。
【図７】不揮発性ストレージ・キャッシュ制御ブロックの実施態様を示す。
【図８】空間的インデックス・エントリの実施態様を示す。
【図９】トラックを第１キャッシュに加えるためのスペースを解放するために第１キャッシュ内のトラックを除去するか否か判定する操作の実施態様を示す。
【図１０】第１キャッシュ内のスペースを解放する操作の実施態様を示す。
【図１１】第１キャッシュにトラックを加える操作の実施態様を示す。
【図１２】第２キャッシュへトラックをプロモートする操作の実施態様を示す。
【図１３】第２キャッシュ内のスペースを解放する操作の実施態様を示す。
【図１４】要求されたトラックのための読み出し要求を処理する操作の実施態様を示す。
【図１５】書き込み要求を処理するためのシーケンシャル・アクセス・ストレージ・デバイスにおける操作の実施態様を示す。
【図１６】書き込み要求のための改変済みトラックを不揮発性ストレージ・デバイスにキャッシュするか否か判定するためのシーケンシャル・アクセス・ストレージ・デバイスにおける操作の実施態様を示す。
【図１７】要求キューを処理するためのシーケンシャル・アクセス・ストレージ・デバイスにおける操作の実施態様を示す。
【図１８】要求キュー内のデステージング要求を処理するためのシーケンシャル・アクセス・ストレージ・デバイスにおける操作の実施態様を示す。
【図１９】要求キューおよび書き込みバイパス・キュー内の書き込み要求を処理するためのシーケンシャル・アクセス・ストレージ・デバイスにおける操作の実施態様を示す。
【発明を実施するための形態】
【００１１】
図１は、コンピューティング環境の実施態様を示す。複数のホスト２ａ、２ｂ・・・２ｎは、ストレージ１０内のボリューム８（例えば、ロジカル・ユニット・ナンバ、ロジカル・デバイス、ロジカル・サブシステムなど）に存するデータにアクセスするためにネットワーク６を介してストレージ・コントローラ４に入力／出力（Ｉ／Ｏ）要求を提出することができる。ストレージ・コントローラ４は、単一のもしくは複数のコアを有する１つ以上のプロセッサを含むプロセッサ・コンプレックス１２と、第１キャッシュ１４と、キャッシュ１４内のトラックをバックアップする第１キャッシュ・バックアップ・デバイス１６と、第２キャッシュ１８とを含む。第１キャッシュ１４および第２キャッシュ１８は、ホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるキャッシュ・データをキャッシュする。第１キャッシュ・バックアップ・デバイス１６は、第１キャッシュ１４内のトラックの不揮発性記憶を提供することができる。さらなる実施態様では、第１キャッシュ・バックアップ・デバイス１６は、第１キャッシュ１４のそれとは異なる電力境界上のクラスタまたはハードウェア内に置かれ得る。
【００１２】
ストレージ・コントローラ４は、ホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるトラックの転送を管理するためのストレージ・マネージャ２２と、第１キャッシュ１４、第１キャッシュ・バックアップ・デバイス１６および第２キャッシュ１８内のホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるデータを管理するキャッシュ・マネージャ２４とを含むメモリ２０を有する。トラックは、ボリューム、ロジカル・デバイスなどのような複数のトラックのより大きなグルーピングの一部であるトラック、ロジカル・ブロック・アドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ（ＬＢＡ））などのような、ストレージ１０において構成されているデータの任意の単位を含み得る。キャッシュ・マネージャ２４は、第１キャッシュ１４および第２キャッシュ１８内の読み出し（未改変）トラックおよび書き込み（改変済み）トラックを管理するために第１キャッシュ管理情報２６および第２キャッシュ管理情報２８を維持する。第１キャッシュ・バックアップ・デバイス・インデックス３０は、第１キャッシュ・バックアップ・デバイス１６内の位置に対するトラック識別子のインデックスを提供する。
【００１３】
ストレージ・マネージャ２２およびキャッシュ・マネージャ２４は、メモリ２０にロードされてプロセッサ・コンプレックス１２により実行されるプログラム・コードとして図１に示されている。代わりに、該機能の幾つかまたは全部は、特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ（ＡＳＩＣ））などの、ストレージ・コントローラ４内のハードウェア・デバイスで実行され得る。
【００１４】
第２キャッシュ１８は、トラックを、トラックが受け取られた順に書き込まれるログ・ストラクチャード・アレイ（ｌｏｇ  ｓｔｒｕｃｔｕｒｅｄ  ａｒｒａｙ（ＬＳＡ））３２に格納することができ、従って第２キャッシュ１８に書き込まれたトラックの時間的配列を提供する。ＬＳＡでは、該ＬＳＡ内に既に存在するトラックの遅いほうのバージョンはＬＳＡ３２の末尾に書き込まれる。代わりの実施態様では、第２キャッシュ１８は、ＬＳＡ以外のフォーマットでデータを記憶することができる。
【００１５】
一実施態様では、第１キャッシュ１４はダイナミック・ランダム・アクセス・メモリ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＤＲＡＭ））などのランダム・アクセス・メモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ））を含むことができ、第２キャッシュ１８はソリッド・ステート・デバイスなどのフラッシュ・メモリを含むことができ、ストレージ１０はハード・ディスク・ドライブおよび磁気テープなどの１つ以上のシーケンシャル・アクセス・ストレージ・デバイスから構成される。ストレージ１０は、単一のシーケンシャル・アクセス・ストレージ・デバイスを含むことができ、あるいは、ジャスト・ア・バンチ・オブ・ディスクス（Ｊｕｓｔ  ａ  Ｂｕｎｃｈ  ｏｆ  Ｄｉｓｋｓ（ＪＢＯＤ））、ダイレクト・アクセス・ストレージ・デバイス（Ｄｉｒｅｃｔ  Ａｃｃｅｓｓ  Ｓｔｏｒａｇｅ  Ｄｅｖｉｃｅ（ＤＡＳＤ））、リダンダント・アレイ・オブ・インディペンデント・ディスクス（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ（ＲＡＩＤ））アレイ、仮想化デバイスなどの複数のストレージ・デバイスのアレイを含むことができる。一実施態様では、第１キャッシュ１４は第２キャッシュ１８より高速のアクセスのデバイスであり、第２キャッシュ１８はストレージ１０より高速のアクセスのデバイスである。さらに、第１キャッシュ１４は第２キャッシュ１８より大きな単位記憶当たりコスト（ｃｏｓｔ  ｐｅｒ  ｕｎｉｔ  ｏｆ  ｓｔｏｒａｇｅ）を有することができ、第２キャッシュ１８はストレージ１０内のストレージ・デバイスより大きな単位記憶当たりコストを有することができる。
【００１６】
第１キャッシュ１４は、メモリ２０の一部であることができ、あるいはＤＲＡＭなどの別のメモリ・デバイスに実装されることができる。一実施態様では、第１キャッシュ・バックアップ・デバイス１６は、例えばバッテリー・バックアップされるランダム・アクセス・メモリ（ＲＡＭ）、スタティックＲＡＭ（ｓｔａｔｉｃ  ＲＡＭ（ＳＲＡＭ））などの、不揮発性メモリのような不揮発性バックアップ・ストレージ（ｎｏｎ−ｖｏｌａｔｉｌｅ  ｂａｃｋｕｐ  ｓｔｏｒａｇｅ（ＮＶＳ））を含むことができる。
【００１７】
ネットワーク６は、ストレージ・エリア・ネットワーク（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＳＡＮ））、ローカル・エリア・ネットワーク（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ））、ワイド・エリア・ネットワーク（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＡＮ））、インターネット、およびイントラネットなどを含むことができる。
【００１８】
図２は、制御ブロック・ディレクトリ５２内のブロックを制御するための第１キャッシュ１４内のトラックのインデックスを提供するトラック・インデックス５０と；第１キャッシュ１４内の未改変シーケンシャル・トラックの時間的配列を提供する未改変シーケンシャルＬＲＵリスト５４と；第１キャッシュ１４内の改変済みシーケンシャル・トラックおよび改変済みノンシーケンシャル・トラックの時間的配列を提供する改変済みＬＲＵリスト５６と；第１キャッシュ１４内の未改変ノンシーケンシャル・トラックの時間的配列を提供する未改変ノンシーケンシャルＬＲＵリスト５８とを含む第１キャッシュ管理情報２６の実施態様を示す。
【００１９】
或る実施態様では、第１キャッシュ・バックアップ・デバイス１６が満杯であると判定すると、新たな改変済みトラックのために第１キャッシュ・バックアップ・デバイス１６内に空間を作るために第１キャッシュ・バックアップ・デバイス１６内の改変済みトラックのコピーが廃棄され得るように第１キャッシュ１４から改変済みトラックをデステージングするために改変済みＬＲＵリスト５６が使用される。
【００２０】
図３は、制御ブロック・ディレクトリ７２内のブロックを制御するための第２キャッシュ１８内のトラックのインデックスを提供するトラック・インデックス７０と；第２キャッシュ１８内の未改変トラックの時間的配列を提供する未改変リスト７４と；改変済みトラックが格納されているストレージ１０内の物理的位置に基づいて第２キャッシュ１８内の改変済みトラックの空間的配列を提供する空間的インデックス７６とを含む第２キャッシュ管理情報２８の実施態様を示す。
【００２１】
すべてのＬＲＵリスト５４、５６、５８、および７４は、識別されたトラックが最後にアクセスされた時に応じて配列された第１キャッシュ１４および第２キャッシュ１８内のトラックのトラックＩＤを含むことができる。ＬＲＵリスト５４、５６、５８、および７４は、最も最近にアクセスされたトラックを示す最短時間未使用（ｍｏｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ（ＭＲＵ））エンドと、最も古くに使用またはアクセスされたトラックを示すＬＲＵエンドとを有する。キャッシュ１４および１８に加えられるトラックのトラックＩＤはＬＲＵリストのＭＲＵエンドに加えられ、キャッシュ１４および１８からデモートされるトラックはＬＲＵエンドからアクセスされる。トラック・インデックス５０および７０および空間的インデックス７６は、スキャッター・インデックス・テーブル（ｓｃａｔｔｅｒ  ｉｎｄｅｘ  ｔａｂｌｅ（ＳＩＴ））を含むことができる。キャッシュ１４および１８内のトラックの時間的配列および第２キャッシュ１８内のトラックの空間的配列を提供するために代わりのタイプのデータ構造が使用され得る。
【００２２】
ノンシーケンシャル・トラックはオンライン・ライン・トランザクション・プロセッシング（Ｏｎｌｉｎｅ  Ｌｉｎｅ  Ｔｒａｎｓａｃｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ（ＯＬＴＰ））トラックを含むことができ、該トラックは、しばしば、完全にはランダムでなくて参照の或る程度のローカリティを有する、すなわち繰り返しアクセスされる確率を有する、小ブロック・ライトを含む。
【００２３】
図４は、シーケンシャル・アクセス・ストレージ・デバイス１００の実施態様を示し、ここでストレージ１０は１つまたは複数のシーケンシャル・アクセス・ストレージ・デバイス１００で実装され得る。シーケンシャル・アクセス・ストレージ・デバイス１００は、Ｉ／Ｏマネージャ１０２として示されている制御ロジックと、改変済みデータをバッファリングするための不揮発性ストレージ・デバイス１０４と、メモリ１０６とを含み、該メモリ１０６は、制御ブロック・ディレクトリ１１０内のブロックを制御するために不揮発性ストレージ・デバイス１０４内のトラックのインデックスを提供するトラック・インデックス１０８と；改変済みトラックが格納されているシーケンシャル・アクセス記憶媒体１１４内の物理的位置にある不揮発性ストレージ１０４内の改変済みトラックの空間的配列を提供する空間的インデックス１１２と；読み出し要求および書き込み要求が待機させられる要求キュー１１６とを含む。Ｉ／Ｏマネージャ１０２は、読み出し要求および書き込み要求を要求キュー１１６に加えるとともに、シーケンシャル・アクセス媒体１１４に対して実行するために要求キュー１１６からの読み出し要求および書き込み要求にアクセスする。Ｉ／Ｏマネージャ１０２は、読み出し／書き込みヘッド１２０を有する１つ以上のアクチュエータを、データが読み出されまたは書き込まれ得るシーケンシャル・アクセス記憶媒体１１４上の位置へ移動させるための制御信号を発生させる読み出し／書き込み制御ユニット１１８へコマンドを送ることができる。
【００２４】
メモリ１０６は、不揮発性ストレージ・デバイス１０４にキャッシュされなくてシーケンシャル・アクセス記憶媒体１１４に直接書き込まれるシーケンシャル書き込み要求およびそれらの改変済みトラックをバッファ１２４にバッファリングするための書き込みバイパス・キュー１２２をさらに含む。バッファ１２４は、読み出し入力要求および書き込み入力要求ならびに読み出し要求に対して返されるデータを一時的にバッファリングすることができる。バッファ１２４は、不揮発性ストレージ・デバイス１０４以外の別のデバイス内に存在することができるとともに、不揮発性ストレージ・デバイス１０４において利用可能であるよりも小さな記憶空間を含むことができる。
【００２５】
デバイス１００内のバッファ１２４は、読み出し入力要求および書き込み入力要求ならびに読み出し要求に対して返されるデータを一時的にバッファリングすることができる。バッファ１２４は、シーケンシャル書き込み要求およびそれらの改変済みデータのためのものなど、不揮発性ストレージ・デバイスにおいて維持されない書き込み要求のための改変済みトラックを一時的にバッファリングするためにも使用され得る。バッファ１２４は、不揮発性ストレージ・デバイス１０４以外の別のデバイス内に存在することができるとともに、不揮発性ストレージ・デバイス１０４において利用可能であるよりも小さな記憶空間を含むことができる。あるいは、バッファ１２４の一部または全体は不揮発性ストレージ・デバイス内に実装されることができる。
【００２６】
シーケンシャル・アクセス記憶媒体１１４は、ハード・ディスク駆動装置のための１つ以上のハード・ディスク・ドライブ・プラッタまたは磁気テープを含むことができる。或る実施態様では、不揮発性ストレージ・デバイス１０４は、ソリッド・ステート・ストレージから構成されるフラッシュ・メモリ・デバイスを含むことができる。或る実施態様では、不揮発性ストレージ・デバイス１０４、例えばフラッシュ・メモリは、シーケンシャル・アクセス・ストレージ・デバイス１００のコンポーネントを含むエンクロージャの中のシーケンシャル・アクセス・ストレージ・デバイス１００回路基板上に実装される。例えば、８ＧＢフラッシュ・メモリ・デバイスを含むことができる。
【００２７】
Ｉ／Ｏマネージャ１０２の機能の一部または全部は、シーケンシャル・アクセス・ストレージ・デバイス１００内のプロセッサによって実行されるコードとして実装されることができる。あるいは、Ｉ／Ｏマネージャ１０２の機能の一部または全部は、シーケンシャル・アクセス・ストレージ・デバイス１００上のＡＳＩＣに実装されることができる。
【００２８】
図５は、制御ブロック識別子（ＩＤ）１５２と、第１キャッシュ１４内のトラックの物理的位置の第１キャッシュ位置１５４と、該トラックが改変済みであるか未改変であるかを示す情報１５６と、該トラックがシーケンシャル・アクセスであるかノンシーケンシャル・アクセスであるかを示す情報１５８とを含む、制御ブロック・ディレクトリ５２内の第１キャッシュ制御ブロック１５０の実施態様を示す。
【００２９】
図６は、制御ブロック識別子（ＩＤ）１６２と、ＬＳＡ３２において該トラックが位置するＬＳＡ位置１６４とを含む、第２キャッシュ制御ブロック・ディレクトリ７２内の第２キャッシュ制御ブロック１６０の実施態様を示す。
【００３０】
図７は、制御ブロック識別子（ＩＤ）１７２と、例えば該トラックが不揮発性ストレージ・デバイス上のＬＳＡに格納されている場合のＬＳＡ位置などの、該トラックが位置する物理的位置１７４とを含む、不揮発性ストレージ１０４制御ブロック・ディレクトリ１１０内の不揮発性ストレージ制御ブロック１７０エントリの実施態様を示す。
【００３１】
図８は、不揮発性ストレージ・デバイス１０４内のトラックのトラック識別子１８２と、例えばシリンダ、プラッタ番号、シリンダ上の角度位置など、シーケンシャル・アクセス記憶媒体１１４において該トラックが格納されている物理的位置１８４とを含む空間的インデックス・エントリ１８０を示す。
【００３２】
図９は、未改変トラックを第１キャッシュ１４からデモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。デモート操作は、第１キャッシュ１４内のスペースを解放すると決定したときに開始され得る。第１キャッシュ１４に加えられるトラックを収容するために第１キャッシュ１４からトラックを除去するか否か判定する操作を（ブロック２００で）開始すると、キャッシュ・マネージャ２４は種々のタイプの未改変トラックへの予想されるヒットに基づいてノンシーケンシャル未改変トラックをデモートするかあるいはシーケンシャル未改変トラックをデモートするかを（ブロック２０２で）決定する。（ブロック２０４で）該決定が未改変シーケンシャル・トラックをデモートする決定であるならば、キャッシュ・マネージャ２４は、デモートされるべき未改変シーケンシャル・トラックを未改変シーケンシャルＬＲＵリストのＬＲＵエンドから決定するために（ブロック２０６で）未改変シーケンシャルＬＲＵリスト５４を使用し、該トラックは第２キャッシュ１８へプロモートされない。（ブロック２０４で）該決定が未改変ノンシーケンシャル・トラックをデモートする決定であるならば、キャッシュ・マネージャ２４は、デモートされるべき未改変ノンシーケンシャル・トラックを（ブロック２０８で）決定するために未改変ノンシーケンシャルＬＲＵリスト５８を使用する。該未改変ノンシーケンシャル・トラックは（ブロック２１０で）第２キャッシュ１８へプロモートされる。
【００３３】
図１０は、改変済みトラックを第１キャッシュ１４からデステージングするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。キャッシュ・マネージャ２４は、スケジュールされた操作の一部として定期的にトラックをデステージングすることができるとともに第１キャッシュ・バックアップ・デバイス１６においてスペースが必要ならばデステージングの速度を高めることができる。改変済みトラックをデステージングする操作を（ブロック２５０で）開始するとき、キャッシュ・マネージャ２４は、ＬＲＵリスト５６のＬＲＵエンドから、デステージングされるべき改変済みトラックを決定するために改変済みＬＲＵリスト５６を（ブロック２５２で）処理する。キャッシュ・マネージャ２４は、決定された改変済みトラック（シーケンシャルまたはノンシーケンシャル）を、第２キャッシュ１８をバイパスしてストレージ１０に（ブロック２５４で）書き込む。キャッシュ・マネージャ２４は、デステージングされた改変済みトラックのコピーを第１キャッシュ・バックアップ・デバイス１６から（ブロック２６０で）廃棄する。
【００３４】
図９および１０の操作では、ノンシーケンシャル・トラックはデモートされるけれども第２キャッシュ１８へプロモートされない。改変済みトラック（書き込み）は、第２キャッシュをバイパスして、ストレージ１０に直接書き込まれる。シーケンシャルな未改変トラック（読み出し）は廃棄されてどこへもコピーされず、第１キャッシュ１４からデモートされる未改変ノンシーケンシャル・トラックは第２キャッシュ１８へプロモートされる。
【００３５】
図１１はトラックを第１キャッシュ１４に加える、すなわちプロモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示し、そのトラックは、ホスト２ａ、２ｂ・・・２ｎからの書き込みあるいは改変済みトラック、読み出し要求に従い、結果として第１キャッシュ１４へ移動させられる第２キャッシュ１８内のノンシーケンシャル・トラック、または、キャッシュ１４内にも１８内にも見出されなくてストレージ１０から取り出される読み出し要求されたデータであり得る。第１キャッシュ１４に加えられるべきトラックを（ブロック３００で）受け取ると、キャッシュ・マネージャ２４は、第１キャッシュ１４内の１５４位置と、該トラックが改変済み／未改変１５６であるかおよびシーケンシャル／ノンシーケンシャル１５８であるかとを示す、該加えられるべきトラックのための制御ブロック１５０（図５）を（ブロック３０１で）作成する。この制御ブロック１５０は、第１キャッシュ１４の制御ブロック・ディレクトリ５２に加えられる。キャッシュ・マネージャ２４は、加えられるべきトラックのトラックＩＤと、制御ブロック・ディレクトリ５２内の作成されたキャッシュ制御ブロック１５０へのインデックスとを有するエントリを第１キャッシュ・トラック・インデックス５０に（ブロック３０２で）加える。加えられるべきトラックのトラック・タイプについてのエントリがＬＲＵリスト５４、５６または５８のＭＲＵエンドに（ブロック３０４で）加えられる。（ブロック３０６で）加えられるべきトラックが改変済みノンシーケンシャル・トラックであれば、該加えられるべきトラックは第１キャッシュ・バックアップ・デバイス１６に（ブロック３０８で）コピーもされ、その加えられるトラックのためのエントリが第１キャッシュ・バックアップ・デバイス・インデックス３０に加えられ、（ブロック３０６で）加えられるべきトラックが未改変シーケンシャルであるならば、制御は終了する。
【００３６】
図１２は、第１キャッシュ１４からデモートされる未改変ノンシーケンシャル・トラックを第２キャッシュ１８へプロモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。トラックを第２キャッシュ１８へプロモートする操作を（ブロック３５０で）開始すると、キャッシュ・マネージャ２４は、プロモートされるトラックを第２キャッシュ１８内のＬＳＡ３２に（ブロック３５２で）加えるとともに、該加えられるべきトラックのためのＬＳＡ３２内のトラック位置１６４を示す制御ブロック１６０（図６）を（ブロック３５４で）作成する。プロモートされるトラックのトラックＩＤと、第２キャッシュ１８のための制御ブロック・ディレクトリ７２内の作成されたキャッシュ制御ブロック１６０へのインデックスとを有するエントリが第２キャッシュ・トラック・インデックス７０に（ブロック３５６で）加えられる。キャッシュ・マネージャ２４は、該トラックＩＤをＭＲＵエンドに加えることなどにより、プロモートされるトラックを未改変ＬＲＵリスト７４のＭＲＵエンドに（ブロック３６０で）示す。
【００３７】
キャッシュ・マネージャ１２は、第２キャッシュ１８を未改変シーケンシャル・トラックだけのための読み出し専用キャッシュとして使用することができる。改変済みシーケンシャル・トラックおよび改変済みノンシーケンシャル・トラックはシーケンシャル・アクセス・ストレージ・デバイス１００に直接書き込まれ、シーケンシャル・アクセス・ストレージ・デバイス１００内の不揮発性ストレージ・デバイス１０４は改変済みノンシーケンシャル・トラックのための書き込みキャッシュを提供する。
【００３８】
図１３は、第２キャッシュ１８に加えられるべき新しいトラック、すなわち第１キャッシュ１４からデモートされるトラックのために第２キャッシュ１８内のスペースを解放するためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。この操作を（ブロック４００で）開始すると、キャッシュ・マネージャ２４は、第２キャッシュ１８内の未改変トラックを未改変ＬＲＵリスト７４のＬＲＵエンドから（ブロック４０２で）決定し、その決定された未改変トラックを（ブロック４０４で）無効にし、その無効にされた未改変トラックをストレージ１０にデステージングしない。
【００３９】
図１４は、読み出し要求のために要求されているトラックをキャッシュ１４および１８およびストレージ１０から取り出すためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。読み出し要求を処理するストレージ・マネージャ２２は、要求されたトラックのための要求をキャッシュ・マネージャ２４に提示することができる。該トラックのための要求を（ブロック４５０で）受け取ると、キャッシュ・マネージャ２４は、要求されたトラックのすべてが第１キャッシュ１４内にあるか否か判定するために第１キャッシュ・トラック・インデックス５０を（ブロック４５４で）使用する。（ブロック４５４で）すべての要求されたトラックが第１キャッシュ１４内にあるわけでは無ければ、キャッシュ・マネージャ２４は、要求されたトラックのうちの第１キャッシュ１４内にはなくて第２キャッシュ１８内にあるものを判定するために第２キャッシュ・トラック・インデックス７０を（ブロック４５６で）使用する。（ブロック４５８で）第１キャッシュ１４および第２キャッシュ１８内にない要求されたトラックがあるならば、キャッシュ・マネージャ２４は、要求されたトラックのうちの、第１キャッシュ１４および第２キャッシュ１８内になくてストレージ１０内にあるものを第２キャッシュ・トラック・インデックス７０から（ブロック４６０で）判定する。キャッシュ・マネージャ２４は、その後、判定されたトラックのうちの第２キャッシュ１８およびストレージ１０内のものを第１キャッシュ１４へ（ブロック４６２で）プロモートする。キャッシュ・マネージャ２４は、読み出し要求に返すために、要求されたトラックを第１キャッシュ１４から取り出すために第１キャッシュ・トラック・インデックス５０を（ブロック４６４で）使用する。取り出されたトラックのためのエントリは、取り出されたトラックのためのエントリを含むＬＲＵリスト５４、５６、５８のＭＲＵエンドに（ブロック４６６で）移動させられる。図１３の操作では、キャッシュ１４および１８は要求されたトラックの最も最近の改変済みバージョンを有するので、キャッシュ・マネージャ２４は要求されたトラックを最高レベルのキャッシュ１４から取り出し、その後に、ストレージ１０へ移行する前に先ず第２キャッシュ１８から取り出す。その最も最近のバージョンは、先ず第１キャッシュ１４内に見出され、もし第１キャッシュ１４内に見出されなければ第２キャッシュ１８内に見出され、その後、もしどちらのキャッシュ１４、１８にも見出されなければストレージ１０内に見出される。
【００４０】
図１４の操作では、キャッシュ１４および１８は要求されたトラックへの最高速のアクセスを提供し、第１キャッシュ１４は要求されたトラックの最も最近の改変済みバージョンを提供するので、キャッシュ・マネージャ２４は、要求されたトラックを最高レベルのキャッシュ１４から集め、次に、ストレージ１０へ移行する前に先ず第２キャッシュ１８から集める。
【００４１】
図１５は、シーケンシャル・アクセス記憶媒体１１４のための改変済みトラックを伴う書き込み要求を処理するためにシーケンシャル・アクセス・ストレージ・デバイス１００においてＩ／Ｏマネージャ１０２により実行される操作の実施態様を示す。書き込み要求を（ブロック５００で）受け取ると、Ｉ／Ｏマネージャ１０２は該書き込み要求の属性が条件を満たすか否か（ブロック５０２で）判定する。該書き込み要求がシーケンシャル書き込み要求であるか、あるいは該書き込み要求のブロック・サイズが所定スレショルドを上回るなど、（ブロック５０２で）該条件が満たされれば、該書き込み要求は書き込みバイパス・キュー１２２に（ブロック５０４で）加えられる。該条件を満たす該書き込み要求の改変済みトラックはバッファ１２４に（ブロック５０６で）バッファリングされる。書き込みバイパス・キュー１２２内の書き込み要求は、不揮発性ストレージ・デバイス１０４にキャッシュされることなくバッファ１２４からシーケンシャル・アクセス記憶媒体１１４に直接書き込まれる。
【００４２】
一実施態様では、書き込み要求が不揮発性ストレージ・デバイス１０４にキャッシュされないでシーケンシャル・アクセス記憶媒体１１４に直接書き込まれるか否かを決定する条件は、書き込み要求がシーケンシャル書き込み要求を含むことであり得る。代わりの実施態様では、書き込み要求のブロック・サイズがスレショルド未満ならば改変済みトラックは不揮発性ストレージ・デバイスにキャッシュされ得るので、該スレショルド未満の数のブロックを有するシーケンシャル書き込み要求およびノンシーケンシャル書き込み要求は不揮発性ストレージ・デバイス１０４にキャッシュされる。
【００４３】
（ブロック５０２で）書き込み要求の属性が条件を満たさなければ、例えばノンシーケンシャル書き込み要求であるならば、Ｉ／Ｏマネージャ１０２は、受け取られた改変済みトラックを不揮発性ストレージ・デバイス１０４に（ブロック５０８で）加える。一実施態様では、該トラックは、不揮発性ストレージ・デバイス１０４内のＬＳＡに加えられるか、あるいは他のフォーマットでデバイス１０４に格納され得る。Ｉ／Ｏマネージャ１０２は、各々の受け取られた改変済みトラックのために該改変済みトラックの不揮発性ストレージ・デバイス１０４内での位置（例えば、ＬＳＡ位置）を示すキャッシュ制御ブロック１７０（図７）を（ブロック５１０で）作成する。不揮発性ストレージ・デバイス１０４内の改変済みトラックのトラックＩＤと、作成された制御ブロック１７０へのインデックスとを有するエントリがトラック・インデックス１０８に（ブロック５１２で）加えられる。
【００４４】
Ｉ／Ｏマネージャ１０２は、シーケンシャル・アクセス記憶媒体１１４において改変済みトラックが格納される物理的位置、例えば該媒体上のシリンダなど、を（ブロック５１４で）決定する。さらに、１つのさらなる実施態様では、空間的インデックス１１２に含まれる決定された物理的位置は改変済みトラックのシリンダ上での角度位置（セクタとも称される）をも含むことができる。Ｉ／Ｏマネージャ１０２は、改変済みトラックのトラックＩＤ１８２と、シーケンシャル・アクセス記憶媒体１１４上での該改変済みの決定された物理的位置１８４とを示すエントリを空間的インデックス１１２に（ブロック５１６で）加える。Ｉ／Ｏマネージャ１０２は、書き込まれるべき各トラックのためにデステージング要求を要求キュー１１６に（ブロック５１８で）さらに加える。このデステージング要求はデモートされるべき特定の改変済みトラックを特定しないかもしれなくて、それは、後に、書き込みを実行するための総アクセス時間を短縮するためのアルゴリズムを用いて決定される。
【００４５】
図１６は、書き込み要求を要求キュー１１６に入れるかそれとも書き込みバイパス・キュー１２２に入れるかを決定するために書き込み要求の複数の属性をチェックするためにＩ／Ｏマネージャ１０２により実行される操作の実施態様を示す。書き込み要求が該条件を満たすか否か判定する操作を（ブロック５３０で）開始すると、Ｉ／Ｏマネージャ１０２は、受け取られた書き込み要求がシーケンシャル書き込み要求であるか否かを（ブロック５３２で）判定する。（ブロック５３２の「いいえ」ブランチから）該書き込み要求がノンシーケンシャルであるならば、Ｉ／Ｏマネージャ１０２は、該書き込み要求のための改変済みトラックを不揮発性ストレージ・デバイス１０４に（ブロック５３４で）格納するとともにデステージング要求を要求キュー１１６のＭＲＵエンドに加える。（ブロック５３２で）書き込み要求がシーケンシャル書き込み要求であって（ブロック５３６で）該書き込みのサイズ、例えばブロックの数、がスレショルドを上回るならば、すなわち大きな書き込み要求であるならば、Ｉ／Ｏマネージャは（ブロック５３８で）該書き込み要求を書き込みバイパス・キュー１２２に加えるとともに該改変済みトラックをバッファ１２４に格納する。（ブロック５３６で）シーケンシャル書き込み要求のサイズが該スレショルドを上回らなければ、すなわち割合に小さいシーケンシャル書き込みであるならば、コントロールはブロック５３４へ進み、ここでその小さなサイズのシーケンシャル書き込みは不揮発性ストレージ・デバイス１０４にキャッシュされる。
【００４６】
図１７は、要求キュー１１６で要求が待機させられている間継続的に反復され得る、要求キュー１１６を処理するためにＩ／Ｏマネージャ１０２により実行される操作の実施態様を示す。要求キュー１１６を処理する操作を（ブロック５５０で）開始すると、（ブロック５５２で）該要求が読み出し要求であるならば、Ｉ／Ｏマネージャ１０２は、該読み出し要求に返すために要求されたトラックのうちの不揮発性ストレージ・デバイス１０４内にあるものを（ブロック５５４で）集める。（ブロック５５６で）不揮発性ストレージ・デバイス１０４内にない要求されたトラックがあれば、Ｉ／Ｏマネージャ１０２は、要求されたトラックのうちの不揮発性ストレージ・デバイス１０４内に見出されないものを（ブロック５５８で）シーケンシャル・アクセス記憶媒体１１４から集める。すべての要求されたトラックを集めた後（ブロック５５８からまたはブロック５５６の「いいえ」ブランチから）、Ｉ／Ｏマネージャ１０２は、集められた読み出し要求されたトラックをストレージ・コントローラ４（図１）に（ブロック５６０で）返し、該読み出し要求されたトラックは不揮発性ストレージ・デバイス１０４にキャッシュすることはない。
【００４７】
（ブロック５６２で）要求がデステージング／書き込み要求ならば、コントロールは、そのデステージング／書き込み要求を処理するために（ブロック５６２で）図１８のブロック６００に進む。該デステージング要求を（ブロック６００で）実行するために、Ｉ／Ｏマネージャ１０２は、（ブロック６０２で）シーケンシャル・アクセス記憶媒体１１４に関しての書き込みヘッド１２０の現在の位置を、空間的インデックス１１２において示されているおよび別様に決定される該シーケンシャル・アクセス記憶媒体上での改変済みトラックの物理的位置（例えば、シリンダおよび角度位置）と比較する。空間的インデックス１１２は、書き込みヘッドに時間的に最も近いトラックを判定するための所要の情報のすべて、例えば書き込まれるべきトラックのシリンダおよび角度位置など、を含むことができ、あるいは該情報の一部だけ、例えばシリンダ、を含むことができて、所要の物理的位置情報の残りは読み出し／書き込み制御ユニット１１８から判定されることができる。Ｉ／Ｏマネージャ１０２は、その比較に基づいて、書き込みヘッド１２０の現在の位置から最小の時間で書き込まれ得る改変済みトラックを（ブロック６０６で）選択し、その選択された改変済みトラックをシーケンシャル・アクセス記憶媒体１１４に（ブロック６０６で）書き込む。デステージングされた改変済みトラックは（ブロック６０８で）無効にされる。
【００４８】
シーケンシャル・アクセスストレージ・デバイスがハード・ディスク・ドライブを含み、シーケンシャル・アクセス記憶媒体１１４が磁気ディスクを含む１つの実施態様では、空間的インデックスは磁気ディスク上のトラックのシリンダを示す。書き込みヘッドの現在の位置から最小の時間でアクセスされ得る改変済みトラックを決定するために、Ｉ／Ｏマネージャ１０２は、書き込みヘッド１２０が改変済みトラックのシリンダへシークするとともに書き込みヘッド１２０の下のディスクを該改変済みトラックの角度位置へ到達するように回転させるために要する時間を推定するために空間的インデックス１１２内の改変済みトラックのシリンダおよび角度位置を解析することができる。Ｉ／Ｏマネージャは、その後、最小の推定アクセス時間を有する改変トラックを選択することができる。
【００４９】
さらなる実施態様では、シーケンシャル・アクセス・ストレージ・デバイス１１４は、複数のディスク・プラッタと各プラッタへの書き込みのための複数の書き込みヘッドとを有するハード・ディスク・ドライブを含み得る。Ｉ／Ｏマネージャ１０２は、該ディスク・プラッタにおいてアクセスするための最小推定時間を有する改変済みトラックを選択するために書き込みヘッドの現在の位置から各ディスク・プラッタ上の各改変済みトラックへシークし回転するための推定時間を決定することができる。
【００５０】
図１９は、書き込みバイパス・キュー１２２内の書き込み要求を処理するとともに要求キュー１１６内の書き込み要求および読み出し要求を処理するためにＩ／Ｏマネージャ１０２によって実行される操作の実施態様を示す。要求キュー１１６内の読み出し要求または書き込み要求の処理を（ブロック６５０で）完了すると、Ｉ／Ｏマネージャ１０２は、書き込みバイパス要求キューが空であるか否か（ブロック６５２で）判定する。もしそうならば、Ｉ／Ｏマネージャ１０２は（ブロック６５４で）図１７のブロック５５０に進んで要求キュー１１６内の要求を処理する。（ブロック６５２で）書き込みバイパス要求キュー１２２が空でなければ、Ｉ／Ｏマネージャ１０２は、処理される書き込み要求のためのバッファリングされている改変済みトラックを、不揮発性ストレージ・デバイス１０４をバイパスしてシーケンシャル・アクセス記憶媒体１１４に書き込むことによって、書き込みバイパス・キュー１２２内の書き込み要求を（ブロック６５６で）処理する。このようにして、要求キュー１１６より高い優先順位が書き込みバイパス・キュー１２２内の書き込み要求に提供される。書き込みバイパス・キュー１２２からの書き込み要求を処理した後、（ブロック６５８で）書き込みバイパス・キュー１２２内の連続的な第１所定数の書き込み要求が処理されると、要求キュー１１６内の要求の飢餓を避けるべくコントロールは要求キュー１１６内の第２所定数の要求を処理するために図１７のブロック５５０に進む。そうではなくて、（ブロック６５８で）書き込みバイパス・キュー１２２からの該連続的第１所定数の書き込み要求が処理されていなければ、すなわち、該飢餓状態が発生していなければ、コントロールは書き込みバイパス・キュー１２２内のさらなる書き込み要求を処理するべくブロック６５６へ進み戻る。
【００５１】
さらに、不揮発性記憶媒体１０４内のスペースを解放するべく不揮発性ストレージ・デバイス１０４内の改変済みトラックをシーケンシャル・アクセス記憶媒体１１４へデステージングするためにデステージング操作が実行されなければならないとＩ／Ｏマネージャ１０２が判定すると、該デステージング操作は、該デステージング操作が完了するまで書き込みバイパス・キュー１２２内の書き込み要求の処理を中断させることができる。
【００５２】
記載された実施態様は、最高速アクセスの第１キャッシュ１４が最も高価なスペース、バイトあたりコスト、を有し、第１キャッシュよりは安価であるがストレージよりは高速である第２キャッシュがシステム内でキャッシュされるデータの量を増やすために使用され得るときにキャッシュ・スペースを増やすために主要なあるいは第１レベルのキャッシュとストレージとの間の第２レベルのキャッシュの使用を可能にするための技術を提供する。より高速なアクセスのキャッシュ記憶スペースを増やせば、要求されたデータがキャッシュ内にあって、より低速のアクセスのより安価なストレージから取り出さなければならない代わりにキャッシュから返され得るときに、キャッシュされたデータへのアクセスが改善される。さらに、記載された実施態様では、ストレージへのトラックの書き込みを最適化するためにデステージングされるトラックがストレージ内の近接するあるいは連続する物理的位置にトラックのグループをなして書き込まれるように、未改変ノンシーケンシャル・トラックは、第１キャッシュにおける時間的配列に基づいて第２キャッシュに加えられ、その後に、シーケンシャル・アクセス・ストレージにおける空間的物理的位置に基づいて第２キャッシュにおいてソートされる。
【００５３】
記載された実施態様は、改変済みトラックのキャッシングを可能にするためにフラッシュ・メモリなどの不揮発性ストレージ・デバイス１０４をシーケンシャル・アクセス・ストレージ・デバイス１００内にさらに設け、この場合、読み出し性能を向上させるために、トラックに対する読み出し要求は、それらがシーケンシャル・アクセス媒体１１４へデステージングされる前に不揮発性ストレージ・デバイス１０４から返されることができる。さらに、書き込みがシーケンシャル・アクセス記憶媒体１１４へデステージングされる前に不揮発性ストレージ・デバイス１０４に格納されたことに応答して書き込みへのコンプリートを返すことによって書き込み性能が改善され得る。
【００５４】
一定のタイプの書き込み要求、代表的にはあまり頻繁にはアクセスされないデータ、例えばシーケンシャル書き込みデータ、のための書き込み要求、をシーケンシャル・アクセス記憶媒体１１４に直接書き込み、ノンシーケンシャル書き込みトラックなどの、より頻繁にアクセスされそうな書き込みデータのために不揮発性ストレージ・デバイス１０４キャッシュ内により多くのスペースを提供するために不揮発性ストレージ・デバイス１０４キャッシュをバイパスすることによって、さらなる利益が実現される。これにより、要求されたより頻繁にアクセスされるデータにより低速のディスク・ドライブなどのシーケンシャル・アクセス記憶媒体１１４からアクセスしなければならない場合と比べて、より頻繁にアクセスされるデータがフラッシュ・メモリなどのより高速のアクセスの不揮発性ストレージ・デバイス１０４から読み出し要求に対して返されることが可能になる。
【００５５】
記載された操作は、ソフトウェア、ファームウェア、ハードウェア、あるいはそれらの任意の組み合わせを作るための標準的なプログラミングもしくはエンジニアリング技術またはその両方を用いて方法、装置またはコンピュータ・プログラム製品として実装され得る。従って、該実施態様の側面は、完全にハードウェアの実施態様、完全にソフトウェアの実施態様（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）あるいは本明細書において全く一般的に“回路”、“モジュール”もしくは“システム”と称され得るソフトウェア側面およびハードウェア側面を組み合わせた実施態様の形をとることができる。さらに、該実施態様の側面は、コンピュータ可読プログラム・コードがその上に具体化されている１つ以上のコンピュータ可読媒体において具体化されるコンピュータ・プログラム製品の形をとることができる。
【００５６】
１つ以上のコンピュータ可読媒体の任意の組み合わせが利用され得る。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であり得る。コンピュータ可読記憶媒体は、例えば、それに限定はされないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、もしくはデバイス、または前記のものの任意の適切な組み合わせであり得る。コンピュータ可読記憶媒体のより具体的な例（非網羅的なリスト）は、次のもの：１つ以上のワイヤを有する電気的接続、ポータブルなコンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能でプログラマブルな読み出し専用メモリ（ＥＰＲＯＭ（ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）またはフラッシュ・メモリ）、光ファイバ、ポータブルなコンパクト・ディスク読み出し専用メモリ（ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ（ＣＤ−ＲＯＭ））、光記憶装置、磁気記憶装置、あるいは前記のものの任意の適切な組み合わせ、を含む。この文書の文脈においては、コンピュータ可読記憶媒体は、命令実行システム、装置、またはデバイスによりまたはこれらと関連して使用されるプログラムを包含または記憶できる任意の有形媒体であり得る。
【００５７】
コンピュータ可読信号媒体は、コンピュータ可読プログラム・コードが例えばベースバンドにあるいは搬送波の一部としてその中に具体化されている伝播されるデータ信号を含み得る。そのような伝播される信号は、電磁、光、あるいはそれらの任意の適切な組み合わせを含むがこれらに限定はされない種々の形のうちのいずれをもとることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなくて、命令実行システム、装置、またはデバイスによりまたはこれらと関連して用いられるプログラムを伝達、伝播、またはトランスポートすることのできる任意のコンピュータ可読媒体であり得る。コンピュータ可読媒体上に具体化されたプログラム・コードは、無線、ワイヤライン、光ファイバ・ケーブル、ＲＦなど、あるいは前記のものの任意の適切な組み合わせを含むがこれらに限定はされない任意の適切な媒体を用いて送信され得る。
【００５８】
本発明の側面のための操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのようなオブジェクト指向プログラミング言語ならびに“Ｃ”プログラミング言語もしくは類似のプログラミング言語のような在来の手続き型プログラミング言語を含む１つ以上のプログラミング言語の任意の組み合わせで書かれ得る。該プログラム・コードは、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上でスタンドアロン・ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でかつ部分的にリモート・コンピュータ上で、あるいは完全にリモート・コンピュータまたはサーバ上で、実行することができる。後者のシナリオにおいては、リモート・コンピュータはローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通してユーザのコンピュータに接続されることができ、あるいは接続は（例えば、インターネット・サービス・プロバイダを用いてインターネットを通して）外部コンピュータに対してなされることができる。
【００５９】
本発明の側面は、本発明の実施態様に従う方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方と関連して上で記述されている。該フローチャート図もしくはブロック図またはその両方の各ブロック、ならびに該フローチャート図もしくはブロック図またはその両方のブロックの組み合わせがコンピュータ・プログラム命令によって実現され得るということが理解されるであろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊目的コンピュータ、またはマシンを作るための他のプログラマブルなデータ処理装置のプロセッサに、該コンピュータもしくは他のプログラマブルなデータ処理装置の該プロセッサを介して実行する該命令が該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行するための手段を生すように、提供されることができる。
【００６０】
これらのコンピュータ・プログラム命令は、コンピュータ可読媒体に格納された命令が該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行する命令を含む製造物品を作るように特定の仕方で機能するようにコンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスに命令することのできるコンピュータ可読媒体に格納されることもできる。
【００６１】
該コンピュータ・プログラム命令は、コンピュータまたは他のプログラマブルな装置上で実行する命令がフローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行するためのプロセスを提供するようにコンピュータ実行されるプロセスを作るために一連の操作ステップを該コンピュータ、他のプログラマブルな装置または他のデバイス上で実行させるためにコンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスにロードされることもできる。
【００６２】
“ａｎ  ｅｍｂｏｄｉｍｅｎｔ”、“ｅｍｂｏｄｉｍｅｎｔ”、“ｅｍｂｏｄｉｍｅｎｔｓ”、“ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔ”、“ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、“ｏｎｅ  ｏｒ  ｍｏｒｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、“ｓｏｍｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、および“ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ”という用語は、明示的に別様に特定されていなければ、“ｏｎｅ  ｏｒ  ｍｏｒｅ  （ｂｕｔ  ｎｏｔ  ａｌｌ）  ｅｍｂｏｄｉｍｅｎｔｓ  ｏｆ  ｔｈｅ  ｐｒｅｓｅｎｔ  ｉｎｖｅｎｔｉｏｎ（ｓ）（１つまたは複数の本発明の１つ以上の（けれども全部ではない）実施態様）”を意味する。
【００６３】
“ｉｎｃｌｕｄｉｎｇ”、“ｃｏｍｐｒｉｓｉｎｇ”、“ｈａｖｉｎｇ”およびこれらのバリエーションは、明示的に別様に特定されていなければ、“ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ（含むけれども限定はされない）”を意味する。
【００６４】
列挙されたアイテムのリスティングは、明示的に別様に特定されていなければ、該アイテムのうちのいずれかまたは全部が相互に排他的であることを意味しない。
【００６５】
“ａ”、“ａｎ”および“ｔｈｅ”は、明示的に別様に特定されていなければ、“ｏｎｅ  ｏｒ  ｍｏｒｅ（１つ以上）”を意味する。
【００６６】
互いに通信するデバイス同士は、明示的に別様に特定されていなければ、互いに連続的に通信していなくてもよい。さらに、互いに通信するデバイス同士は直接にあるいは１つ以上の媒介を通して間接的に通信することができる。
【００６７】
互いに通信する数個のコンポーネントを有する実施態様についての記述は、そのようなコンポーネントがすべて必要であることを意味しない。反対に、本発明の広範な可能な実施態様を示すために多様な任意選択のコンポーネントが記載されている。
【００６８】
さらに、プロセス・ステップ、方法ステップ、アルゴリズムなどが順次に記載されているかも知れないけれども、そのようなプロセス、方法およびアルゴリズムは代わりの順序で働くように構成されることができる。換言すれば、記載され得るステップのシーケンスまたは順序は、該ステップがその順序で実行されなければならないことを必ずしも示さない。本明細書に記載されているプロセスのステップは任意の実際的な順序で実行されることができる。さらに、幾つかのステップは同時に実行され得る。
【００６９】
本明細書において単一のデバイスまたは物品が記載されるとき、単一のデバイス／物品の代わりに２つ以上のデバイス／物品（それらが協働してもしなくても）が使用され得ることは明白であろう。同様に、本明細書において２つ以上のデバイスまたは物品が記載される場合（それらが協働してもしなくても）、その２つ以上のデバイスまたは物品の代わりに単一のデバイス／物品が使用され得ることあるいはその示された数のデバイスまたはプログラムの代わりに異なる数のデバイス／物品が使用され得ることは明白であろう。デバイスの機能もしくはフィーチャまたはその両方は、そのような機能／フィーチャを持っていると明示的に記載されてはいない１つ以上の他のデバイスによって代わりに具体化されることができる。従って、本発明の他の実施態様は、そのデバイス自体を含んでいなくてもよい。
【００７０】
図７〜図１９に示されている操作は、一定の順序で起こる一定のイベントを示す。代わりの実施態様では一定の操作は異なる順序で実行され、改変されあるいは除去されることができる。さらに、ステップが上記のロジックに加えられ、なお記載された実施態様に従うことができる。さらに、本明細書に記載された操作は順次に起こることができ、あるいは一定の操作は並行して処理されることができる。さらに、操作は単一の処理装置によってまたは分散された処理装置によって行われることができる。
【図１】
0005943363.tif 000002
【図２】
0005943363.tif 000003
【図３】
0005943363.tif 000004
【図４】
0005943363.tif 000005
【図５】
0005943363.tif 000006
【図６】
0005943363.tif 000007
【図７】
0005943363.tif 000008
【図８】
0005943363.tif 000009
【図９】
0005943363.tif 000010
【図１０】
0005943363.tif 000011
【図１１】
0005943363.tif 000012
【図１２】
0005943363.tif 000013
【図１３】
0005943363.tif 000014
【図１４】
0005943363.tif 000015
【図１５】
0005943363.tif 000016
【図１６】
0005943363.tif 000017
【図１７】
0005943363.tif 000018
【図１８】
0005943363.tif 000019
【図１９】
0005943363.tif 000020