(57)【要約】      （修正有）【課題】より効率的なキャッシュ管理の廃棄ポリシーとディステージ・ポリシーのためのシステムを提供する。【解決手段】データ記憶において、データはキャッシュに一時的に記憶されるが、この際書込みデータは第１のキャッシュと第２のキャッシュに記憶され、読出データは第２のキャッシュに記憶される。前記第１のキャッシュに関するエントリを維持するリストが一杯である場合は、前記リストをスキャンして新しいデータ用の場所を設けるために、前記キャッシュから廃棄することができる未修正の（読出し）データを特定する。前記スキャン前又はスキャン中に、修正（書込み）データのエントリが前記リストの最短時間未使用（ＭＲＵ）の端部に移動し、それによって前記スキャンを効率的に進めて、前記スキャンが修正エントリをスキップしなければならない回数を減少させることができる。任意に、状態ビットを各修正データエントリと関連付けることもできる。【選択図】図９
2007141225.tif 000002
【特許請求の範囲】
【請求項１】
メモリ・スペースを、データ記憶コントローラ内の第１のキャッシュであって、最短時間未使用（ＭＲＵ）の端部と最長時間未使用（ＬＲＵ）の端部とを有する前記第１のキャッシュに、割り当てるステップと、
メモリ・スペースを、データ記憶コントローラ内の第２のキャッシュであって、前記第１のキャッシュよりもメモリ・スペースが少なく、最短時間未使用（ＭＲＵ）の端部と最長時間未使用（ＬＲＵ）の端部とを有する、前記第２のキャッシュに、割り当てるステップと、
読出データ・エントリを前記第１のキャッシュに一時的に記憶するステップと、
書込みデータ・エントリを前記第１及び第２のキャッシュに一時的に記憶するステップと、
前記第１及び第２のキャッシュ内のデータ・エントリへのアクセス要求を受信するステップと、
アクセスされ読出し中に前記第１のキャッシュ内で検出されたデータ・エントリを、前記第１のキャッシュ内の現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
アクセスされ書出し中に前記第２のキャッシュ内で検出されたデータ・エントリを、前記第２のキャッシュ内の現在位置から前記第２のキャッシュの前記ＭＲＵ端部に移動させるステップと、
第１の読出データ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュ内で使用可能である場合は、前記第１のキャッシュ内にその時点で存在する全てのデータ・エントリを、前記第１のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の読出データ・エントリを収容するステップと、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い前記書込みデータ・エントリの内の少なくとも１つを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる一方、読出データ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
前記第１のキャッシュの前記ＬＲＵ端部から読出データ・エントリを廃棄し、
前記第１の読出データ・エントリを前記第１のキャッシュの前記ＭＲＵ端部にステージするステップと、
第１の書込みデータ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュ内と前記第２のキャッシュ内のいずれでも使用可能である場合は、前記第１及び第２のキャッシュ内にその時点で存在する全てのデータ・エントリを各々、前記第１及び第２のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の書込みデータ・エントリを収容し、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い前記書込みデータ・エントリの内の少なくとも１つを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる一方、読出データ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
読出データ・エントリを前記第１のキャッシュの前記ＬＲＵ端部から廃棄し、
記第１の書込みデータ・エントリを前記第２のキャッシュの前記ＭＲＵ端部と前記第１のキャッシュの前記ＭＲＵ端部とにステージするステップと、
を有する、データ記憶コントローラ内のキャッシュ・データを管理する方法。
【請求項２】
状態ビットであって、各書込みデータの状態ビットが、各書込みデータ・エントリが前記第１のキャッシュにステージされる時に第１の段階に設定される状態ビットを、前記第１のキャッシュ内の各書込みデータ・エントリと関連付けるステップと、
少なくとも１つの書込みデータ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
前記少なくとも１つの書込みデータ・エントリの前記状態ビットを第２の段階に設定するステップと、
をさらに有する、請求項１に記載の方法。
【請求項３】
移動は全ての書込みデータ・エントリを前記第１のキャッシュ内のその時点での現在位置から、前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップを有する、請求項２に記載の方法。
【請求項４】
移動は少なくとも１つの書込みデータ・エントリを、読出データ・エントリが前記第１のキャッシュの前記ＬＲＵ端部に来るまで、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップを有する、請求項２に記載の方法。
【請求項５】
前記第１及び第２のキャッシュ内に位置する第２の書込みデータ・エントリの読出し要求を受信するステップと、
ヒットした前記第２の書込みデータ・エントリを前記第１のキャッシュ内の現在位置から再び前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
前記第１のキャッシュ内の前記第２の書込みデータ・エントリの前記状態ビットを前記第１の段階に設定するステップと、
第３の書込みデータ・エントリを前記第１及び第２のキャッシュに一時的に記憶させようとするステップと、
メモリ・スペースが前記第２のキャッシュ内で使用不可能な場合は、
既存の書込みデータ・エントリを、前記第２のキャッシュの前記ＬＲＵ端部からディステージし、
前記第３の書込みデータ・エントリを前記第１のキャッシュのＭＲＵ端部と前記第２のキャッシュのＭＲＵ端部とにステージし、
前記第２のキャッシュ内でディステージされた前記書込みエントリに対応する前記第１のキャッシュ内の前記書込みデータ・エントリを、前記ＬＲＵ端部の方向に降等させ、
前記降等された書込みデータ・エントリを、前記第１のキャッシュ内で読出データ・エントリに変換するステップと、
をさらに有する、請求項２に記載の方法。
【請求項６】
前記降等された書込みデータ・エントリを、前記第１のキャッシュから除去するステップをさらに有する、請求項５に記載の方法。
【請求項７】
データ・アクセス要求がホスト・デバイスから受信されるインターフェイスと、
データが少なくとも１つの付属記憶装置とのやりとりで送受信されるインターフェイスと、
読出し・書込みデータ・エントリを一時的に記憶する第１の複数のエントリ・スペースであって、最短時間未使用（ＭＲＵ）端部と最長時間未使用（ＬＲＵ）端部とを備える前記第１の複数のエントリ・スペースを有する、第１のキャッシュと、
書込みデータ・エントリを一時的に記憶する第２の複数のエントリ・スペースであって、前記第１の複数のエントリ・スペースよりも少なく、前記第２の複数のエントリ・スペースがＭＲＵ端部とＬＲＵ端部とを備える前記第２の複数のエントリ・スペースを有する、第２のキャッシュと、
前記第１及び第２のキャッシュ内の読出しデータ又は書込みデータ・エントリの要求を受信し、
アクセスされて読出し中に前記第１のキャッシュ内で検出されたデータ・エントリを、前記第１のキャッシュ内のその現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させ、
アクセスされて書出し中に前記第２のキャッシュ内で検出されたデータ・エントリを、前記第２のキャッシュ内の現在位置から前記第２のキャッシュの前記ＭＲＵ端部に移動させ、
第１の読出データ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュ内で使用可能である場合は、前記第１のキャッシュ内にその時点で存在する全てのデータ・エントリを、前記第１のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の読出データ・エントリを収容し、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い１つ以上の書込みデータ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるとともに、読出データ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
読出データ・エントリを、前記第１のキャッシュの前記ＬＲＵ端部から廃棄し、
前記第１の読出データ・エントリを前記第１のキャッシュの前記ＭＲＵ端部にステージする、とともに、
第１の書込みデータ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュと前記第２のキャッシュ内のいずれでも使用可能である場合は、前記第１及び第２のキャッシュ内にその時点で存在する全てのデータ・エントリをそれぞれ、前記第１及び第２のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の書込みデータ・エントリを収容し、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い１つ以上の書込みデータ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる一方、読出データ・エントリを、前記第１のキャッシュ内のその時点での前記現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
読出データ・エントリを前記第１のキャッシュの前記ＬＲＵ端部から廃棄して、
前記第１の書込みデータ・エントリを前記第２のキャッシュの前記ＭＲＵ端部と前記第１のキャッシュの前記ＭＲＵ端部とにステージする、
ようにプログラムされている、キャッシュ・マネージャと、
を有する、データ記憶コントローラ。
【請求項８】
前記第１のキャッシュは、揮発性メモリを有し、
前記第２のキャッシュは、不揮発性メモリを有する、
請求項７に記載のコントローラ。
【請求項９】
前記キャッシュ・マネージャはさらに、
状態ビットであって、各書込みデータ・エントリが前記第１のキャッシュにステージされる時に第１の段階に設定される各書込みデータ・エントリの前記状態ビットを、前記第１のキャッシュ内の各書込みデータ・エントリと関連付け、
少なくとも１つの書込みデータ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させ、
前記少なくとも１つの書込みデータ・エントリの前記状態ビットを第２の段階に設定する、
ようにプログラムされている、請求項７に記載のコントローラ。
【請求項１０】
前記キャッシュ・マネージャは、全ての書込みデータ・エントリを、前記第１のキャッシュ内のその時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させることによって、少なくとも１つの書込みデータ・エントリを移動させるようにプログラムされている、請求項９に記載のコントローラ。
【請求項１１】
前記キャッシュ・マネージャは、少なくとも１つの書込みデータ・エントリを、読出データ・エントリが前記第１のキャッシュの前記ＬＲＵ端部に来るまで、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップを有する移動によって移動させる、請求項９に記載のコントローラ。
【請求項１２】
前記キャッシュ・マネージャはさらに、
前記第１及び第２のキャッシュ内に位置する第２の書込みデータ・エントリの読出し要求を受信し、
ヒットした第２の書込みデータ・エントリを前記第１のキャッシュ内の現在位置から再び前記第１のキャッシュの前記ＭＲＵ端部に移動させ、
前記第１のキャッシュ内の前記第２の書込みデータ・エントリの前記状態ビットを前記第１の段階に設定し、
第３の書込みデータ・エントリを前記第１及び第２のキャッシュに一時的に記憶しようとし、
メモリ・スペースが前記第２のキャッシュ内で、使用不可能である場合は、
前記第２のキャッシュの前記ＬＲＵ端部から既存の書込みデータ・エントリをディステージし、
前記第３の書込みデータ・エントリを前記第１のキャッシュのＭＲＵ端部と前記第２のキャッシュのＭＲＵ端部とにステージし、
前記第２のキャッシュ内でディステージされた前記書込みエントリに対応する前記第１のキャッシュ内の前記書込みデータ・エントリを前記ＬＲＵ端部の方向に降等させ、
前記降等された書込みデータ・エントリを、前記第１のキャッシュ内の読出データ・エントリに変換する、
ようにプログラムされている、請求項９に記載のコントローラ。
【請求項１３】
前記キャッシュ・マネージャはさらに、前記降等された書込みデータ・エントリを、前記第１のキャッシュから除去するようにプログラムされている、請求項１２に記載のコントローラ。
【請求項１４】
コンピュータで使用可能なコンピュータ・プログラムであって、前記コンピュータ・プログラムはデータ記憶コントローラ内でキャッシュ・データを管理するためにコンピュータ読取り可能なコードを内蔵し、前記コンピュータ読取り可能なコードは、データ記憶コントローラ内でキャッシュ・データを管理する命令を有しており、
メモリ・スペースを、データ記憶コントローラ内の第１のキャッシュであって、最短時間未使用（ＭＲＵ）端部と最長時間未使用（ＬＲＵ）端部とを有する前記第１のキャッシュに、割り当てるステップと、
メモリ・スペースを、前記データ記憶コントローラ内の第２のキャッシュであって、前記第１のキャッシュよりもメモリ・スペースが少なく、最短時間未使用（ＭＲＵ）端部と最長時間未使用（ＬＲＵ）端部とを有する、前記第２のキャッシュに、割り当てるステップと、
読出データ・エントリを前記第１のキャッシュに一時的に記憶するステップと、
書込みデータ・エントリを前記第１及び第２のキャッシュに一時的に記憶するステップと、
前記第１及び第２のキャッシュ内のデータ・エントリへのアクセス要求を受信するステップと、
アクセスされて読出し中に前記第１のキャッシュ内で検出されたデータ・エントリを、前記第１のキャッシュ内のその現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
アクセスされて書出し中に前記第２のキャッシュ内で検出されたデータ・エントリを、前記第２のキャッシュ内のその現在位置から前記第２のキャッシュの前記ＭＲＵ端部に移動させるステップと、
第１の読出データ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュ内で使用可能である場合は、前記第１のキャッシュ内にその時点で所在する全てのデータ・エントリを、前記第１のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の読出データ・エントリを収容し、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い前記書込みデータ・エントリの内の少なくとも１つを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる一方、読出データ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
前記第１のキャッシュの前記ＬＲＵ端部から読出データ・エントリを廃棄し、
前記第１の読出データ・エントリを、前記第１のキャッシュの前記ＭＲＵ端部にステージする、ステップと、
１の書込みデータ・エントリを前記第１のキャッシュにステージする時に、
メモリ・スペースが前記第１のキャッシュ内及び前記第２のキャッシュ内のいずれでも使用可能である場合は、前記第１及び第２のキャッシュ内にその時点で存在する全てのデータ・エントリをそれぞれ、前記第１及び第２のキャッシュの前記ＬＲＵ端部の方向に移動させて前記第１の書込みデータ・エントリを収容し、
メモリ・スペースが前記第１のキャッシュ内で使用不可能である場合は、
前記第１のキャッシュの前記ＬＲＵ端部に最も近い前記書込みデータ・エントリの内の少なくとも１つを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる一方、読出データ・エントリを、前記第１のキャッシュ内の前記その時点の現在位置から前記第１のキャッシュの前記ＬＲＵ端部に移動させ、
前記第１のキャッシュの前記ＬＲＵ端部から読出データ・エントリを廃棄し、
前記第１の書込みデータ・エントリを前記第２のキャッシュの前記ＭＲＵ端部と前記第１のキャッシュの前記ＭＲＵ端部とにステージする、ステップと、
を有する、コンピュータ・プログラム。
【請求項１５】
前記命令がさらに、
状態ビットであって、各書込みデータが前記第１のキャッシュにステージされる時に第１の段階に設定される、各書込みデータ・エントリの前記状態ビットを、前記第１のキャッシュ内の各書込みデータ・エントリと関連付けるステップと、
少なくとも１つの書込みデータ・エントリを、前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
前記少なくとも１つの書込みデータ・エントリの前記状態ビットを第２の段階に設定するステップと、
を有する、請求項１４に記載のコンピュータ・プログラム。
【請求項１６】
前記移動させる命令が、全ての書込みデータ・エントリを前記第１のキャッシュ内のその時点での現在位置から、前記第１のキャッシュの前記ＭＲＵ端部に移動させる命令を有する、請求項１４に記載のコンピュータ・プログラム。
【請求項１７】
前記移動させる命令が、読出データ・エントリが前記第１のキャッシュの前記ＬＲＵ端部に来るまで、少なくとも１つの書込みデータ・エントリを前記第１のキャッシュ内の前記その時点での現在位置から前記第１のキャッシュの前記ＭＲＵ端部に移動させる命令を有する、請求項１４に記載のコンピュータ・プログラム。
【請求項１８】
前記命令はさらに、
前記第１及び第２のキャッシュ内に位置する第２の書込みデータ・エントリへアクセスする要求を受信するステップと、
ヒットした第２の書込みデータ・エントリを前記第１のキャッシュ内の現在位置から再び前記第１のキャッシュの前記ＭＲＵ端部に移動させるステップと、
前記第１のキャッシュ内の前記第２の書込みデータ・エントリの状態ビットを前記第１の段階に設定するステップと、
第３の書込みデータ・エントリを前記第１及び第２のキャッシュに一時的に記憶させようとするステップと、
メモリ・スペースが前記第２のキャッシュ内で使用不可能である場合は、
既存の書込みデータ・エントリを、前記第２のキャッシュの前記ＬＲＵ端部からディステージし、
前記第３の書込みデータ・エントリを、前記第１のキャッシュのＭＲＵ端部と前記第２のキャッシュのＭＲＵ端部とにステージし、
前記第２のキャッシュ内でディステージされた前記書込みエントリに対応する前記第１のキャッシュ内の前記書込みデータ・エントリを、前記ＬＲＵ端部の方向に降等させ、
前記降等された書込みデータ・エントリを、前記第１のキャッシュ内で読出データ・エントリに変換する、ステップと、
を有する、請求項１４に記載のコンピュータ・プログラム。
【請求項１９】
前記命令はさらに、前記降等された書込みデータ・エントリを前記第１のキャッシュから除去するステップを有する、請求項１８に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、データ記憶コントローラに関し、より詳細にはキャッシュ廃棄ポリシー及びディステージ・ポリシーを確立することに関する。
【背景技術】
【０００２】
ＩＢＭ  Ｅｎｔｅｒｐｒｉｓｅ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｅｒ（Ｒ）のようなデータ記憶コントローラは、付属記憶システムへ送付される入・出力（Ｉ／Ｏ）要求を受信する。前記付属記憶システムは、直接アクセス記憶装置（ＤＡＳＤ）、独立ディスク冗長配列（ＲＡＩＤ配列）、単純ディスク束（Ｊｕｓｔ  Ａ  Ｂｕｎｃｈ  ｏｆ  Ｄｉｓｋｓ：ＪＢＯＤ）等の多数の相互接続ディスク・ドライブを含む１つ以上の格納物  （ｅｎｃｌｏｓｕｒｅ）を有している。Ｉ／Ｏの読出し・書込み要求がそれらを処理できる速度よりも速い速度で受信される場合には、前記記憶コントローラは前記Ｉ／Ｏ要求を、ランダム・アクセス・メモリ（ＲＡＭ）やダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）等の１ギガバイト以上の揮発性記憶装置を備えることができる一次キャッシュの待ち行列に入れる。ある種の修正（書込み）データのコピーを、バッテリ・バックアップ型の揮発性メモリのような二次不揮発性記憶（ＮＶＳ）キャッシュ内に配置して、前記記憶コントローラに障害が発生した場合に書込みデータを付加的に保護することもできる。典型的には、前記二次キャッシュは、ＮＶＳメモリの費用のために前記一次キャッシュよりも小型である。
【０００３】
多くの現行システムでは、エントリは前記一次キャッシュに記憶されている各トラック毎の最長時間未使用（ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ：ＬＲＵ）リスト内に含まれている。「Method,  System,  and  Program  for  Destaging  Data  in  Cache」という表題で、本明細書に参照で援用されている、同一出願人による米国特許第６７８５７７１号には、１つのそのようなシステムが記載されている。トラックを前記記憶システムからキャッシュにステージして、読出し要求を戻すことができる。さらに、あるトラックに関する書込みデータを、前記付属記憶システムに転送する前に前記一次キャッシュに記憶して、転送できなかった場合に前記データを保存することができる。前記ＬＲＵリストの各エントリは、トラックの現行状態、キャッシュ内の前記トラックの位置、及び前記記憶システム内の前記トラックの配置を示す制御ブロックを備えている。別個のＮＶＳのＬＲＵリストは、前記二次ＮＶＳキャッシュ内のトラック毎に、同じ様に維持され管理される。要約すれば、前記一次キャッシュは読出しトラックと修正（書込み）トラックの両方を含んでいるが、前記二次キャッシュは修正（書込み）トラックのみしか含んでいない。それ故に、前記一次ＬＲＵリスト（「Ａ」リストとしても知られている）は、読出し・書込みトラックを表示するエントリを含んでいるが、前記二次ＬＲＵリスト（「Ｎ」リストとしても知られている）は、書込みトラックを表示するエントリのみしか含んでいない。前記一次及び二次ＬＲＵリストは各々、順次データ用リスト（「高速化（ａｃｃｅｌｅｒａｔｅｄ）」リスト）と、ランダム・データ用リスト（「アクティブ（ａｃｔｉｖｅ）」リスト）とに分けることもできるが、本開示ではそのような区別はしていない。
【０００４】
図１乃至図６並びに図７及び図８に示される従来技術のキャッシュ管理順序を参照すると、プライム記号「‘」で標示されるリスト・エントリは修正トラックのエントリを表し、一方前記プライム記号がないリスト・エントリは、未修正エントリ又は読出しエントリを表している。図１は既に部分的に読出し・書込みエントリが記入されているＡリスト及びＮリストの例を示している。新しいエントリは、前記一次キャッシュに追加された各トラックを表示する前記ＬＲＵリストの最短時間未使用（ｍｏｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ：ＭＲＵ）端部に追加される。図２では、新しい書込みエントリＥ'が、両方のリストの前記ＭＲＵ端部に追加されている。前記新しいエントリが前記ＭＲＵ端部に追加されていくにつれて、既存のエントリは前記両リストの前記ＬＲＵ端部の方向に「降等（ｄｅｍｏｔｅｄ）」される。トラックにアクセスする要求が受信された時は、前記一次キャッシュ内で検索が行われ、要求された前記トラックのエントリが検出された場合は（「ヒット」として知られている）、前記エントリが前記リストの前記ＭＲＵ端部に昇進（ｍｏｖｅｄ  ｕｐ）する（図３）。
【０００５】
追加要求のあった読出データと修正データをバッファするために前記一次キャッシュ内で追加スペースが必要になった時は、前記キャッシュから前記ＬＲＵリストの前記ＬＲＵ端部のエントリによって表示される１つ以上のトラックが廃棄され、それに対応するエントリが前記一次ＬＲＵリストから除去される（図６では、新しいエントリＨ'が追加された時に、エントリＡ'が、両方のキャッシュから廃棄されている）。前記一次キャッシュ内の読出データ・トラックは、前記データが既に前記記憶システム内のディスク上に記憶されていてディステージする必要がないため、前記キャッシュから迅速に廃棄することができる。ただし、前記一次及び二次キャッシュ内の修正（書込み）データ・トラックは、前記記憶システムに安全にディステージされた後だけ、前記キャッシュ及びリストから廃棄することができる。そのようなディステージ手順には、未修正の読出データを廃棄する時間の１００倍もの時間がかかることがある。
【０００６】
前記一次キャッシュと前記二次キャッシュのサイズの違いのために、書込みデータ・エントリが、前記関連トラックが前記二次キャッシュからディステージされた後に、前記二次（ＮＶＳ）リストから廃棄される場合には、前記エントリ及びトラックが、前記一次ＬＲＵリスト及びキャッシュ内に残る可能性がある（図７及び図８では、書込みエントリＤ'は、前記一次リスト内には残っているが、前記二次リストからは廃棄されている）。そのような場合には、前記エントリの状態は、「修正」から「未修正」に変更され、読出し要求に使用可能な状態のままとなる（図８ではエントリＤ'がＤに変更されている）。
【０００７】
上述のように、前記一次キャッシュが（図４乃至図５と同様に）追加のデータ・トラックを受け入れるのに十分な空きスペースを有していない場合には、既存のトラックが廃棄される。現在使用されている１つの処理では、前記一次ＬＲＵリストは、その対応するトラックを迅速に廃棄できる１つ以上の未修正（読出し）データ・エントリを、前記ＬＲＵ端部からスキャンされる。前記スキャン中は、修正（書込み）データ・エントリは、該トラックをディステージするのにより長い時間が必要となるためスキップされる（図５では、未修正エントリＣが廃棄されている）。前記修正データ・エントリをスキップせずにディステージした場合でも、それらの修正エントリが前記新しいエントリを受け入れるだけの十分なスペースを迅速に空けられない可能性がある。  それで、前記ディステージが進行している間は、それらの修正エントリをスキップしなければならなくなる。その結果、重い書込み負荷が生じている間は、いくつかの修正トラックが何度も修正され、比較的長時間前記二次キャッシュ内に残る可能性もある。そのようなトラックはディステージされる前に「修正」状態で、前記一次キャッシュ内にも残ることになる。さらに、そのようなトラックが最終的に前記二次キャッシュからディステージされた後でも、それらのトラックは「未修正」として前記一次キャッシュ内に残る可能性があり、前記一次リストの前記ＭＲＵ端部付近にある場合には、前記一次リスト内を移動する別の機会（又は「寿命」）を入手する可能性もある。前記一次キャッシュ内に多くの修正トラックが存在する場合、リスト・スキャンでは多くのエントリをスキップしなければならず、新しいトラック用の場所を設けるために廃棄する未修正トラックを十分に特定することができない可能性もある。上記から分かるように、これ程までに多くのキャッシュ・トラックをスキップすれば、かなり多くの時間を要し、プロセッサ・サイクルを浪費する。これらの要因のために、前記読出し置換ポリシーと書込み消却ポリシーは相互依存関係にあり、書込みキャッシュ管理は、読出しキャッシュ管理に連動している。
【特許文献１】米国特許第６７８５７７１号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
それ故に、キャッシュのディステージ処理を管理するＬＲＵリストを使用しているにも拘わらず、当業界では、キャッシュ内のデータを管理して前記ディステージ処理を実施する改良型技術の必要性が依然として残っている。
【課題を解決するための手段】
【０００９】
本発明は、より効率的なキャッシュ管理の廃棄ポリシーとディステージ・ポリシーのためのシステム、方法、及びプログラムを提供する。前記スキャン前又はスキャン中に、修正（書込み）データ・エントリが前記リストの最短時間未使用（ＭＲＵ）端部に移動し、それによって前記スキャンを効率的に進めて、修正データ・エントリをスキップしなくてもよくなる。任意に状態ビットを各修正データ・エントリと関連付けることもできる。前記エントリが前記Ａリストの前記ＭＲＵ端部に移動した時は、その状態ビットが初期状態（０などの）から、それが廃棄対象候補であることを示す第２の状態（１などの）に変更される。アクセスが要求されている書込みトラックが前記一次キャッシュ内で検出された場合は（「ヒット」）、対応するＡリスト・エントリの前記状態ビットが前記第１の状態に戻されて、その結果前記トラックが廃棄されることが防止される。かくして、書込みトラックは、必要な限り前記一次キャッシュ内に留まることが可能になる。
【発明を実施するための最良の形態】
【００１０】
図９は、本発明を実施することができるデータ処理環境３００のブロック図である。記憶コントローラ３１０は、ネットワーク３０４を介して前記記憶コントローラ３１０が取り付けられている１つ以上のホスト３０２Ａ、３０２Ｂ、３０２Ｃから入力／出力（Ｉ／Ｏ）要求を受信する。前記Ｉ／Ｏ要求は、直接アクセス記憶装置（ＤＡＳＤ）、独立ディスク冗長配列（ＲＡＩＤ配列）、単純ディスク束（ＪＢＯＤ）等のいくつかの構成のいずれかのディスク・ドライブを有する記憶システム３０６内のトラックへ送付される。前記記憶コントローラ３１０は、プロセッサ３１２と、キャッシュ・マネージャ３１４と、キャッシュ３２０とを有している。前記キャッシュ・マネージャ３１４は、前記キャッシュ３２０を管理するために前記プロセッサ３１２が実行するハードウェア構成要素あるいはソフトウェア／ファームウェア構成要素を備えている。前記キャッシュ３２０は、第１部分と第２部分とを備えている。一実施形態では、前記第１のキャッシュ部分は、揮発性キャッシュ部分３２２であり、前記第２のキャッシュ部分は、不揮発性キャッシュ部分３２４である。前記キャッシュ・マネージャ３１４は、読出し（未修正）データ・トラックと書込み（修正）データ・トラックとを前記揮発性キャッシュ部分３２２に一時的に記憶し、書込み（修正）データ・トラックだけを前記不揮発性キャッシュ部分３２４に一時的に記憶するように構成されている。
【００１１】
前記記載の実施形態では、前記データはキャッシュ内のトラックとして管理されているが、代替実施形態では、前記データはロジカル・ブロック・アドレス（ＬＢＡ）等のような他のデータ単位で管理することもできる。
【００１２】
前記キャッシュ・マネージャ３１４はさらに、前記揮発性キャッシュ部分３２２（前記「Ａ」リスト）に関する１組のデータ・トラック・リストと、前記不揮発性キャッシュ部分３２４（前記「Ｎリスト」）に関する１組のデータ・トラック・リストとを構築するように構成されている。図１０に示されるように、各組の一つのリストはランダム・アクセス・データのエントリを保持するために構築し（前記「アクティブ」リスト）、第二のリストは順次アクセス・データ用のエントリを保持するように構築してもよい（前記「アクセル」リスト）。図１０では、前記アクティブ・リストは前記アクセル・リストよりも大きいが、必ずしもそうする必要はない。さらに、本発明はアクティブ・リストとアクセル・リスト間のトラック・エントリ区分の存在に左右されず、これ以降のさらなる説明でもそのような区別はしていない。
【００１３】
図１１及び１２は、本発明の一態様に係るキャッシュ管理の順序を示している。図１１では、前記Ａリストは、前記ＭＲＵ端部から前記ＬＲＵ端部まで読出し・書込みエントリで一杯になっている。エントリは、前記ＮリストにもＭＲＵ端部から前記ＬＲＵ端部まで入力されているが、前記リストは未だ一杯にはなっていない。  新しい読出し又は書込みエントリの前記Ａリストへの追加前のある時点で、あるいは新しいエントリを追加する処理の一環として、前記Ａリストは、新しいエントリの追加準備の際に前記キャッシュ・マネージャ３１４によって再配置される。本明細書の前記背景技術で要約したように、従来技術の処理では、前記Ａリストを前記ＬＲＵ端部から前記ＭＲＵ端部の方へ上方にスキャンして、第一の未修正読出しエントリを位置決めする。当該エントリに関連する前記トラックが廃棄され、新しいエントリ用の場所が前記揮発性キャッシュ部分内に設けられる。しかしながら、これとは対照的に本発明の一変形形態では、前記キャッシュ・マネージャ３１４が、全て又は相当量の前記修正（書込み）データ・エントリを前記Ａリストの前記ＭＲＵ端部に移動させ、１つ以上の未修正データ・エントリを前記ＬＲＵ端部に残す（図１２）。そして、前記キャッシュ・マネージャ３１４が前記Ａリストのスキャンを開始する場合には、未修正データ・エントリを特定しようとして時間やプロセッサ・サイクルが浪費されることはない。なお、そのようなエントリは既に前記ＬＲＵ端部にあって直ちに廃棄できる。別の変形形態では、前記Ａリストのスキャンが開始され、修正データ・エントリは未修正データ・エントリが前記ＬＲＵ端部に来るまで、前記ＭＲＵ端部に移動する。なお、当該エントリによって表示される前記データ・トラックは廃棄される。
【００１４】
図１３乃至図１８は、図１１及び図１２に関して説明した前記実施形態への第１の選択的機能拡張を示している。各書込みデータ・エントリは、当初０に設定されている追加的な状態ビットを含んでいる（図１３）。本発明の実施を簡略化するため、エントリは全て当初０に設定された前記状態ビットを含んでいてもよい。ただし、未修正エントリに関連する状態ビットは０のままである。図１４では、修正データ・エントリ（Ａ'、Ｄ'、及びＥ'）は、前記Ａリストの前記ＭＲＵ端部に移動しており、それらの状態ビットは１に変更されていて、それらの修正データ・エントリが前記Ａリストを少なくとも部分的に一度は進んだことを示している。図１１及び図１２の順序のように、前記修正エントリの全部又はいくつかを移動させることができ、それらは十分な修正データのエントリを移動させて前記ＬＲＵ端部の未修正データのエントリを露わにする、スキャンの前またはスキャン中に移動させることができる。
【００１５】
その後、前記記憶コントローラ３１０は、トラックＥ'のような修正トラックにアクセスすることを求める要求をホスト３０２から受信する。前記トラックは前記キャッシュ３２０内にあるために、記憶装置３０６から検索する必要なしに、前記キャッシュから迅速に読み出すことができる。トラックＥ'に前記「ヒット」があると、前記キャッシュ・マネージャ３１４は前記対応するデータ・エントリを前記Ａリストの前記ＭＲＵ端部に移動させてその状態ビットを０に戻し（図１５）、それによって前記エントリが再び前記リストを移動することが可能になる。前記不揮発性キャッシュ部分３２４に追加される別の書込みトラックは、前記不揮発性キャッシュ部分３２４を満たし、そのエントリ（Ｇ'）が前記Ｎリストを満たす。前記Ａリストへの書込みトラックのエントリによって、前記Ａリストの前記ＬＲＵ端部の前記読出しエントリ（Ｃ）もまた強制廃棄される（図１６）。前記不揮発性キャッシュ部分３２４にさらに別の書込みトラックが追加された時は、前記関連するエントリ（Ｈ'）がＮリストに追加され、それによって前記Ｎリストの前記ＬＲＵ端部の前記書込みエントリ（Ａ'）が記憶装置３０６に強制的にディステージされる。前記Ａリスト内の前記対応するエントリは、修正状態から未修正状態に変更される（図１７）。前記エントリ（Ａ）は、その状態ビットが１であることから、直ちにあるいは後のスキャン中に前記Ａリストから廃棄される（図１８）。
【００１６】
図１９乃至図２３は、図１３乃至図１７に示される手順の一代替手順である。初期の順序（図１９乃至図２０）は前記先の手順（図１３及び図１４）の順序と同様である。次に、トラックＡ'に読出しヒットがあると、前記関連するＡリストのエントリが前記Ａリストの前記ＭＲＵ端部の最上部に残る（あるいは、当該エントリが以前に前記ＬＲＵ端部の方向に降等されている場合は、当該エントリを最上部に移動させる）。さらに、前記エントリの状態ビットは１から０に変更され、それによって前記エントリが再び前記リストを移動することが可能になる（図２１）。新しい書込みエントリ（Ｇ'）によって前記Ｎリストが一杯になり（図２２）、一方別の新しい書込みエントリ（Ｈ'）によって、Ａ'が前記Ｎリストから強制的にディステージされる。前記キャッシュ・マネージャ３１４は、その対応するＡリストのエントリの前記状態ビットが０であると判定する。したがって、前記キャッシュ・マネージャ３１４は、前記状態を修正（Ａ'）から未修正（Ａ）に変更し、前記エントリを前記Ａリストから直ちに廃棄することはしない。前記エントリ（Ａ）には前記Ａリストを移動する別の機会が与えられ、それが未修正であって状態ビットが１である場合にのみ廃棄されることになる。
【００１７】
本発明は十分に機能しているデータ処理システムのコンテキストで説明されているが、当業者ならば、本発明の前記処理を、各種命令のコンピュータ可読媒体の形や様々な形で分配させることができ、本発明が、実際に使用される特定のタイプの信号支持媒体に関わらず、前記分配を実行するために適用されることが理解されることに留意することが重要である。コンピュータ可読媒体の例には、フレキシブル・ディスク、ハード・ディスク・ドライブ、ＲＡＭ、ＣＤ−ＲＯＭ、並びにデジタル通信リンクやアナログ通信リンク等の伝送タイプの媒体等、記録可能な媒体が含まれる。
【００１８】
本発明の前記記載は、例示及び説明のために提示されているが、網羅的であることを意図したものではなく、又本発明を開示している前記形態に限定するものでもない。当業者には多くの修正形態及び変形形態が明らかであろう。例えば、上記は特定の順序で発生する具体的な動作を説明している。選択実施の際前記処理の中には、異なる順序で実施されたり、修正されたりあるいは除去されるものもある。さらに上述の前記処理にいくつものステップが追加され、それらがなお前記記載の実施形態に適合している場合もある。さらに本明細書に記載の処理は順番に行う場合もあれば、並行して処理される場合もある。前記記載の実施形態は、本発明の諸原理及び実際の適用形態を最良の形で説明するように、又意図された特定の使用に適するように、様々な修正を伴った様々な実施形態について、当業者の他の人々が本発明を理解することができるように選択され説明されてきた。さらに方法及びシステムに関して上述したが、当業界の必要性はデータ記憶コントローラ内のキャッシュ・データを管理する命令を含むコンピュータ・プログラムによって充足させることもできる。
【図面の簡単な説明】
【００１９】
【図１】キャッシュ管理の従来技術の順序を示す図である。
【図２】キャッシュ管理の従来技術の順序を示す図である。
【図３】キャッシュ管理の従来技術の順序を示す図である。
【図４】キャッシュ管理の従来技術の順序を示す図である。
【図５】キャッシュ管理の従来技術の順序を示す図である。
【図６】キャッシュ管理の従来技術の順序を示す図である。
【図７】キャッシュ管理の別の従来技術の順序を示す図である。
【図８】キャッシュ管理の別の従来技術の順序を示す図である。
【図９】本発明を実施することができるデータ処理環境のブロック図である。
【図１０】本発明で用いられるＬＲＵリストの例を示す図である。
【図１１】本発明の一態様に係るキャッシュ管理の順序を示す図である。
【図１２】本発明の一態様に係るキャッシュ管理の順序を示す図である。
【図１３】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１４】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１５】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１６】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１７】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１８】本発明の別の一態様に係るキャッシュ管理の順序を示す図である。
【図１９】本発明のさらに別の一態様に係るキャッシュ管理の順序を示す図である。
【図２０】本発明のさらに別の一態様に係るキャッシュ管理の順序を示す図である。
【図２１】本発明のさらに別の一態様に係るキャッシュ管理の順序を示す図である。
【図２２】本発明のさらに別の一態様に係るキャッシュ管理の順序を示す図である。
【図２３】本発明のさらに別の一態様に係るキャッシュ管理の順序を示す図である。
【符号の説明】
【００２０】
ＬＲＵ  最長時間未使用
ＭＲＵ  最短時間未使用
３００  データ処理環境
３０２Ａ  ホスト
３０２Ｂ  ホスト
３０２Ｃ  ホスト
３０４  ネットワーク
３０６  記憶装置
３１０  記憶コントローラ
３１２  プロセッサ
３１４  キャッシュ・マネージャ
３２０  キャッシュ
３２２  揮発性
３２４  不揮発性
【図１】
2007141225.tif 000003
【図２】
2007141225.tif 000004
【図３】
2007141225.tif 000005
【図４】
2007141225.tif 000006
【図５】
2007141225.tif 000007
【図６】
2007141225.tif 000008
【図７】
2007141225.tif 000009
【図８】
2007141225.tif 000010
【図９】
2007141225.tif 000011
【図１０】
2007141225.tif 000012
【図１１】
2007141225.tif 000013
【図１２】
2007141225.tif 000014
【図１３】
2007141225.tif 000015
【図１４】
2007141225.tif 000016
【図１５】
2007141225.tif 000017
【図１６】
2007141225.tif 000018
【図１７】
2007141225.tif 000019
【図１８】
2007141225.tif 000020
【図１９】
2007141225.tif 000021
【図２０】
2007141225.tif 000022
【図２１】
2007141225.tif 000023
【図２２】
2007141225.tif 000024
【図２３】
2007141225.tif 000025