JPH06505584A - キャッシュメモリ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 キャッシュメモリ １亙旦１ 本発明は、ソリッドステート記憶装置と回転磁気ディスク装置の組合わせを包含 する高性能コンピュータデータ記憶装置に関するものである。

支釆立亘１ 多数のコンピュータデータ記憶システムが存在しており、それらは回転磁気ディ スク装置に対するフロントエンドとしである程度ソリッドステートメモリ装置を 使用している。典型的なキャッシュシステムは、一連の磁気ディスク上に記憶さ れたデータに対する保持区域として単一のソリッドステートメモリユニットを使 用し、その際に高速キャッシュメモリ内にある情報を格納即ち記憶させることを 可能とし、その際に比較的低速のディスクメモリのみを使用する場合に比較して 速度性能を増加させており、即ち、所望のデータが高速キャッシュメモリ内に収 納される時間の割合を増加させ、その際にデータがディスクドライブのみに格納 即ち記憶される場合と比較してアクセスをより高速のものとすることを可能とし ている。このようなシステムのブロック図を図１に示しである。ホストコンピュ ータ１０１が、例えばＳＣ５Ｉ等のホストインターフェース１０４を介しキャッ シュユニット１０３を介してディスク１０２−１乃至１０２−Ｎの全ストリング と通信を行う。ディスク１０２へ送給され且つそこがら供給される全てのデータ は、ホストインターフェース１０４、とキャッシュユニット１０３と、ディスク インターフェース１０５とから構成されるキャッシュ−ディスクデータ経路を介 して通過する。キャッシュユニット１０３はデータのキャッシングを管理し且つ ポストコンピュータ１０１からの要求に応える。キャッシュユニット１０３の主 要な構成要素は、マイクロプロセサ１０３−１．キャッシュ管理ハードウェア１ ０３−２、キャッシュ管理ファームウェア１０３−３、アドレスルックアップテ ーブル１０３−４、ソリッドステートキャッシュメモリ１０３−５を包含してい る。

図１の従来のキャッシュシステムは、頻繁にアクセスされるデータをソリッドス テートメモリ区域内に保持し、同一のデータがディスク媒体上においてアクセス される場合に得られるものよりもそのデータに対してより迅速なアクセスを与え ることを意図したものである。通常、このようなキャッシュシステムは、あるホ ストコンピュータに取付けた場合及びある作業量のもとでは極めて効果的なもの である。

然しなから、幾つかの欠点も存在しており、且つある条件下においては。このよ うなキャッシュシステムは同様のキャッシュを行わない装置によって得られるも のよりも低い性能レベルを表わす。従来のキャッシュ付ディスク装置の所望の性 能より低い性能とさせる要因の幾つかについて検討する。

ディスクストリング１０２における全てのディスクと関連して単一のキャッシュ メモリ１０３−５が使用されている。いずれかのディスクからのデータは任意の 与えられた時間においてキャッシュメモリ１０３−５内に存在している場合があ る。ビジーデータ即ち頻繁にアクセスされるデータはそれが存在するディスクド ライブに拘らず、キャッシュ動作を行うことが望ましい。ホストのコマンド即ち 命令に応える場合、そのデータがキャッシュメモリ１０３−５内に存在するか否 か及びキャッシュメモリ１０３−５内におけるそのデータの位置の決定は、通常 、ハツシング手法及びテーブルサーチ操作によって行われる。ハツシング方法及 びテーブルサーチは、それら自身の時間遅延を導入する場合があり、そのことは キャッシュユニット自身の目的を阻害する場合がある。

性能はキャツシュヒツト率に非常に敏感である。

キャッシュ動作のためのオーバーヘッド及び待ち時間のために、典型的なストリ ング指向型キャッシュシステムにおける低いヒツト率は、キャッシュを行わない ディスクストリングの場合よりも全体的に低下した性能となる場合がある。

ディスク装置１０２の容量と相対的なキャッシュメモリ１０３−５の寸法は通常 小さなものである。

低いヒツト率を救済するための一見明白な技術は、キャッシュメモリ１０３−５ の寸法を増大させることである。然しなから、キャッシュメモリ１０３−５の寸 法には上限があり、それを超えてより大きな容量を加えてもそれから得られる利 点は限界的なものであることが判明している。キャッシュメモリ１０３−５の容 量が制限されている場合、多様なデータセグメントにわたっての多数の要求が、 キャッシュメモリ１０３−５内に所望のデータを維持するためにキャッシュシス テムの容量を使い果たす。しばしば、すぐ後で再使用するデータが、ホストコン ピュータ１０１からの新たな要求を取扱うためにキャッシュメモリ１０３−５内 に場所を確保するために、時期尚早にデキャッシュ動作、即ちキャッシュメモリ から取除かれる。その結果は、キャツシュヒツト率が低下する。キャツシュヒツ ト率が低下すると、ディスクアクセスの回数が増加し、ディスクアクセスの回数 が増加すると、データ経路上での競合が増加する。その結果、自己破壊的サイク ルが発生する。

「バックグラウンド」キャッシュアヘッド動作は制限されている。何故ならば、 このような動作によって転送されるデータは、ホストコンピュータ】０１からの 直接的な要求に応えるために転送されるデータと同一の経路を介して移動するも のであり、しばしばそのようなデータと競合を発生する。キャッシュユニット１ ０３とディスクストリング１０２との間のデータ経路は容易に過負荷状態となる 場合がある。ホストコンピュータ１０１からの要求に応えるためか又はキャッシ ュ管理の目的のために、ディスクストリング１０２内のいずれかのディスクへ又 はそのディスクからの全てのデータは、キャッシュ−ディスク経路を横断して移 動する。このことは、ディスクストリング１０２からキャッシュメモリ１０３− ５への大量なデータのプレフェッチ動作が発生する場合には、障害を発生する。

ディスクストリング１０２からキャッシュメモリ１０３−５内へデータをプレフ ェッチするための各試みは、潜在的に、ディスクストリング１０２のディスクド ライブのうちのいずれかとホストコンピュータ１０１との間で通信されているデ ータとその経路に関して競合を発生する。その結果、キャッシュメモリ１０３− ５内へのデータのプレフェッチ動作は妥当な程度に制限されねばならず、ある限 界を超えてキャッシュメモリ１０３−５の寸法を増加させることはキャッシュシ ステムの性能において対応する改善を発生するものではない。このことは一連の 関連した現象を発生する。キャッシュアヘッド管理は、しばしば、キャッシュ動 作されたデータから充足されなかった各ホスト読取りコマンドに関し先んじて読 取動作を行うことに制限されている。この技術は、キャッシュメモリ１０３−５ とディスクストリング１０２との間の経路に対して待機する要求の待ち状態を増 加させるキャッシュアヘッドの傾向を最小とさせることに貢献する。然しなから 、キャッシュ動作が基礎とする概念のうちの一つは、データアクセスが、妥当な 程度に短い時間フレーム内において与えられた局所性内に集中する傾向があると いうことである。例えば、データセグメントは、逐次的な態様でしばしばアクセ スされる。キャッシュアヘッド動作を読取ミスの関数に制限することは、キャツ シュヒツト率を低下させるネガティブな効果を有する場合がある。何故ならば、 このような制限は、データアクセスの局所性を利用するということを阻止するか 又は劣化させる場合があるからである。

ストリングキャッシュの性能を最適化させるために多種類のアルゴリズム及び形 態が考案されている。

はぼ普遍的に受入れられている概念は、最も最近でなく使用された即ち最も古い （ＬＲＵ）測定を基礎にしたキャッシュされたデータセグメントの保持及び置換 を包含している。新しいデータに対して場所を空けるためにデータをデキャッシ ュすること即ちキャッシュメモリから取除くことは、テーブルによって管理され 、該テーブルは、各キャッシュされたブロックのデータに対して、その相対的な 時間を与える。何故ならば、それが最後にアクセスされたものだからである。使 用されるアルゴリズムに依存して、このプロセスは、更に、潜在的な測定可能な 時間遅延を有するテーブルサーチの何らかの形態となることが可能である。

キャッシュメモリ１０３−５は、通常、揮発性であり、該ユニットに対するパワ ーが取除かれると、データは喪失する。この特性は、不意の停電の可能性と結合 されて、通常、ホストコンピュータ１０３からキャッシュストリングへ転送され るデータを取扱うためのライトスルー即ち全書き構成を課していた。このような 構成においては、ホストコンピュータ】０３からの全書きは直接ディスクに対し て書込まれ、ディスク速度において処理が行われ、これらの動作は通常ディスク 動作に関連する低い転送率、待ち時間、シークの全ての本来的な時間遅延に露呈 される。ギャッシュユニット１０３は、ディスクインターフェース１０５を介し てディスクドライブ１０２のストリングと通信を行う。

ｌ肚立１尤 コンピュタ動作及び処理能力は、しばしば、周辺のデータの読取りに必要とされ る時間によって制限を受ける。ソリッドステート記憶装置は高速の応答を有して いるが、それはメガバイトの記憶当たり比較的高いコストにおいてのものである 。回転磁気ディスク、光ディスク、又はその他の大量記憶媒体は、メガバイト当 たり比較的低いコストで高い記憶容量を与えるが、その応答速度は低いものであ る。本発明によれば、大量記憶装置のものに近付（メガバイトあたりのコストで もって、ソリッドステート記憶装置の速度に近い速度を与えるソリッドステート と大量記憶装置のハイブリッド装置が提供される。本発明をより良く説明するた めに、磁気ディスク媒体に関する実施例について説明を行う。然しなから、理解 すべきことであるが、本発明は、光デイスク装置等のその他のタイプの大量記憶 装置にも同様に適用可能なものである。

本発明は幾つかの特徴に基づいており、それらの特徴としては、回転磁気ディス ク媒体、充分なソリッドステート記憶容量、ディスク装置とソリッドステート記 憶装置との間のプライベートチャンネル、独特のデータ管理を実施するマイクロ プロセサ、独特のプレフェッチ手順、並列動作能力等である。本発明のハイブリ ッド記憶媒体は、いずれの作業量に対しても通常の磁気ディスク速度より低い速 度で実際的な動作を行うことなしに、多数のタイプのコンピュータ作業量に対し てほぼソリッドステート速度で動作を行う。

回転磁気ディスク媒体は、装置に大容量を与えるために使用されており、ソリッ ドステート記憶装置は、高速応答能力を本装置に与えるために使用されている。

ソリッドステート媒体を直接的に単一の磁気ディスク装置と関連させることによ って、プライベートなデータ通信線が確立され、該通信線はホストと本装置との 間の通常のデータ転送と、ソリッドステートメモリとディスクとの間の転送との 間の競合を回避する。このプライベートデータチャンネルは、事実上、二つの格 納媒体の間の無制限の対話を可能としている。充分なるソリッドステートメモリ を使用することにより、複数個の同時的にアクティブなデータストリームに対し てのデータの効率的なメンテナンスを可能としている。メモリ装置の管理は、− 個又はそれ以上のマイクロプロセサを介して行われ、該マイクロプロセサはデー タのインテリジェントな配置を行うために歴史的且つ予測的データアクセスを使 用する。時間臨界的経路においてはテーブルサーチを使用することはない。ソリ ッドステートメモリ内に格納されているデータへのホストのアクセスはソリッド ステート速度において行われ、磁気ディスク上に格納されているデータへのホス トのアクセスはディスク装置速度において行われる。殆どの条件下において、ホ ストから本装置へ送給される全てのデータはソリッドステート速度において取扱 われる。

作業量及び現在のＩｌｏの特性がそのようなモードが最適な動作モードであるこ とを表わす場合に、本装置が疑似的磁気ディスクモードに入るようにインテリジ ェンスが実現されている。このモードシフトは性能を高いレベルに維持すること を助ける。更に、歴史的情報に基づいて、実現したインテリジェンスは近い将来 のホスト−装置Ｉ１０１００取扱いを最適化させるために、本装置内における動 作上の優先度をシフトさせることが可能である。

゛　の　な９０ 図１は典型的な従来のキャッシュ型ディスクコンピュータデータ格納システムの ブロック図。

図２は本発明に基づいて構成したキャッシュ型ディスクコンピュータデータ記憶 装置の一実施例を示したブロック図。

図３は本発明を具体化するハードウェア形態の一実施例を示したブロック図。

図４は本発明の一実施例の動作を示したフローチャート図。

図５は図４のホストコマンドステップの動作をより詳細に説明したフローチャー ト図。

図６は図５の解析したホストＩ１０コマンド動作の一実施例の動作を示したフロ ーチャート図。

図７は図６のセットアツプトラックアドレスリスト動作をより詳細に示したフロ ーチャート図。

図８は図７のアドレス変換をより詳細に示したフローチャート図。

図９は図５に示したキャッシュ読取ヒツト動作を示したフローチャート図。

図１０は図５に示したキャッシュ読取ミス動作を　゛より詳細に示したフローチ ャート図。

図１１は図５のキャッシュ書込ヒツト動作を示したフローチャート図。

図１２は図５のキャッシュ書込ミス動作を示したフローチャート図。

図１３は図５のシークキャッシュミス動作を示したフローチャート図。

図１４は図６．１３．１５のデキャッシュＬＲＵ動作を示したフローチャート図 。

図１５は図４のキャッシュアヘッド動作を示したフローチャート図。

図１６は図１５のキャッシュアヘッド決定動作を示したフローチャート図。

図１７は図４のバックグラウンドスイープ動作開始の動作を示したフローチャー ト図。

図１８は図４に示したホストＩ１０完了におけるバックグラウンドスィーブ開始 のステップを示したフローチャート図。

図１９は図７．１８．２０に示したバックグラウンドイベント動作発生を示した フローチャート図。

図２０は図４のバックグラウンドスイープ継続ステップの動作を示したフローチ ャート図。

図２１はパワーダウン制御動作を示したフローチャート図。

図２２は図２１に示した最終的バックグラウンドスィーブ動作を示したフローチ ャート図。

Ｌ旦翌朋 表Ｆ−１乃至Ｆ−４は夫々表Ｔ−１乃至Ｔ−４の構成を示している。

表Ｔ−１はホストＣＰＵからの最初のＩ１０１００処理の前のアドレス変換（Ａ ＤＴ）テーブルにおける値の一例を示している。

表Ｔ−２はホストＣＰＵからの最初のＩ１０１００処理前の最も最近でなく使用 した即ち最も古い（ＬＲＵ）テーブルにおける値の一例を示している。

表Ｔ−３は最も最近でな（使用した即ち最も古い（ＬＲＵ）テーブルを示してい る。

表Ｔ−３ａ乃至Ｔ−３ｅは種々の数のＩ１０動作後のＡＤＴテーブルを示してい る。

表Ｔ−４は通常の利用期間中コンピュータシステム動作から抽出されるＩ１０コ マンドのサンプルを示している。これらのＩ１０コマンド、及び中間のコマンド は、表Ｔ−１乃至Ｔ−３に示した如く、サンプル予測ＬＲＵ及びＡＤＴテーブル 用の基礎である。

アドレス変換、 セクタアドレスのトラックアドレス及び該トラック内のセクタオフセットへの変 換。

キャッシュアヘッドファクタ、近接ファクタ、各トラックヒツト又は再ヒツトに おいて、多数のＩｌｏを満足させるのに充分なキャッシュされたデータは、現在 のＩｌｏに関与したデータの現在の位置の前及び／又は後に留まることが可能で ある。これら二つの残存するエリアのいずれかが設定した数のＩｌｏよりもより 少ない場合には、キャッシュアヘッドが活性化される。その最小数の潜在的なＩ ｌｏがキャッシュアヘッドファクタ即ち近接ファクタである。

アドレス変換テーブル、ＡＤＴテーブルディスクトラック識別子とソリッドステ ートメモリアドレスとの間の関係を維持するテーブルであり、それは、必要に応 じて、その他の情報も保持する。

キャッシュ 全体としてユニット内のユーザデータを保持するソリッドステートメモリエリア 。

ＣＰＵセクタ 論理セクタの用語の説明を参照。

ディスク、磁気ディスク、回転磁気ディスク回転磁気媒体ディスクドライブのこ とである。

ディスクセクタアドレス 磁気ディスクユニット上の物理的セクタのアドレス。

ディスクサーバ、 回転磁気ディスクへの書込み及びそれからの読取りを取扱うユニットの論理的セ クション。

ディスクトラックアドレス、トラックアドレスディスク上の与えられたトラック における第一セクタのデータのアドレス。これらのアドレスは回転磁気ディスク 上の物理的位置に対応している。工１０動作において特定された各セクタアドレ スは、トラックアドレス及びそのトラック内のセクタオフセットへ変換すること が可能である。

ＤＭＡ、ダイレクトメモリアクセス プロセサを関与させることなしにメモリからメモリへのデータの転送。

ＤＲＡＭ、ダイナミックランダムアクセスメモリソリッドステートメモリ装置と して使用される一個又はそれ以上のチップ。

ＥＤＡＣ。

エラー検知及び補正 ＥＥＰＲＯＭ。

電気的消去可能プログラム可能リードオンリメモリＥＰＲＯＭ、消去可能書込可 能リードオンリメモリ。

ホスト、 本ユニットが取付けられているコンピュータ。

ホストサーバ、 ホストコンピュータとインターフェースする本ユニットの部分。

Ｉｌｏ、 セクタ数としてのホストＩ１０要求の寸法。

ＬＲＵ　（Ｌｅａｓｔ−Ｒｅｃｅｎｔ　１ｙ−Ｕｓｅｄ）、データ格納トラック に関して、最も長い時間にわたりアクセスされなかったもの。

ＬＲＵテーブル、 キャッシュ効率に与える影響が最も少ない状態でどのソリッドステートメモリデ ータエリアを再使用することが可能であるかをユニットのコントローラが決定す ることを可能とする情報に関するテーブル。

ＭＲＵ　（Ｍｏｓｔ−Ｒｅｃｅｎｔｌｙ−Ｕｓｅｄ）データ格納トラックに関し て、最も最近にアクセスされたもの。

ノーマルモード、 最適な性能レベルに発達するためにその通常の優先変を使用することの可能な装 置の状態。

ナル、ナル値、 フィールドが空であると考えられる状態を表わすテーブルフィールドにおける値 であって、使用状態に依存して、それは、０であるか、又はフィールドのビット 構成が受付けることの可能な最高の値である。

物理的トラック、ディスクトラック、 ディスク上の完全なデータトラックで、ディスクユニットの一つのブラタ上の一 つの完全な磁気バンド。

近接ファクタ 各トラックヒツト又は再ヒツトにおいて、多数のＩｌｏを満足するのに充分なデ ータは、現在のＩｌｏに関与するデータの現在の位置の前及び／又は後に留まる ことが可能である。これら二つの残存するエリアのうちのいずれかが設定した数 のＩｌｏよりも少ない場合には、キャッシュアヘッドが活性化される。その最小 数の潜在的なＩｌｏがキャッシュアヘッドファクタ即ち近接ファクタ。

読取ミス最大寸法、 セクタ数としてのホスト読取トランズアクションの寸法であり、それは、その寸 法を超えた場合には、該トランズアクションを疑似的ディスクモードで処理させ る。

リサイクル、 ＬＲＵ位置への到着を超えてのキャッシュ内のトラックの保持を記述するために 使用される用語であり、このような保持は、キャッシュアヘッド動作の結果とし てキャッシュを行なうようになったか又はそれがリサイクル作用の恩恵を被るも のの最後のものであったためにある時間においてそのトラックが再使用されたと いう事実に基づくものである。

ＳＣ５Ｉ（Ｓｍａｌｌ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍ　Ｉｎｔｅｒｆｅｃｅ ）、 例えばホストコンピュータに対するディスク装置などの装置をインターフェース するためのプロトコルに適用される名称である。

ＳＣ５Ｉ制御チャンネル、 ＳＣ３Ｉプロトコルを使用する装置間の物理的接続であって、ケーブルによって 接続された論理的制御器から構成されている。

セクタ、 ディスクトラックの論理的サブユニットであって、ディスク上のデータの最も小 さなアドレス可能な単位。

ソリッドステートメモリ、ソリッドステート装置、ＳＳＤ。

例えばＤＲＡＭ等のソリッドステート装置から構成されたメモリ媒体。

ＳＳＤトラックアドレス、 与えられたディスクトラックの最初のセクタの最初のバイトが存在するソリッド ステートメモリ内のアドレス。

トラック、論理的トラック、論理的ブロック、ディスク上の論理的データトラッ ク又はＳＳＤにおけるその等偽物は、ディスク上の物理的トラックと同一である 場合もない場合もある（ディスクユニットの一つのブラタ上の一つの完全なる磁 気バンド）。

注意すべきことであるが、Ｉ１０動作は一つを超えた論理的ブロックを関与させ る場合がある。

トラック寸法、 ディスクトラック内にあると考えられるセクタ数であって、これは、ディスクト ラック内の実際のセクタ数と等しい場合も等しくない場合もある。

ユニット（単位）、 ユニットの指定は以下に説明する。

緊急モード、 少な（とも磁気ディスクレベル性能を維持するために優先度をシフトせねばなら ない装置の状態。

書込ミス最大寸法、 それを超えた場合に、トランズアクションを疑似的ディスクモードで処理させる セクタ数としてのホスト書込トランズアクションの寸法。

本発明によれば、コンピュータ周辺データ格納（記憶）装置が提供され、それは 、ソリッドステートメモリと回転ディスクメモリとの組合わせを有しており、こ の装置は、磁気ディスク媒体の速度に近付いたメガバイトあたりのコストでのソ リッドステート速度に近い速度を有する大容量の磁気ディスクを有している。説 明の便宜上、ディスク媒体に関して実施例の説明を行なう。然しなから、理解す べきことであるが、本発明は、光デイスク装置等のその他のタイプの大量記憶装 置に同様に適用可能である。

本発明のこの装置は、回転磁気ディスク媒体からその大記憶容量が得られている 。その高速性能は、二つの記憶媒体の間のプライベートチャンネル、−組の独特 のデータ管理アルゴリズムを使用した複数個のマイクロプロセサ、独特のプレフ ェッチ手順、並列動作能力、充分なソリッドステートメモリの組合わせから得ら れている。このハイブリッド記憶媒体は、いずれの作業量に対しても通常の磁気 ディスク速度以下で決して実際的な動作を行うことなしに、殆どのタイプのコン ピュータ作業量に対してソリッドステートメモリの速度に近い速度で全体的な性 能を与える。

ホストコンピュータに対して、本発明装置は単一の直接的にアドレス可能な実体 であるように見える。

本装置内においての、ソリッドステートメモリと一つ又はそれ以上の磁気ディス ク装置との組合わせによって、本装置内にプライベートなデータ通信線が確立さ れ、それはホストと本装置との間の通常のデータ転送とソリッドステートメモリ とディスク媒体との間の転送との間の競合を回避している。このプライベートな データチャンネルは、ホストコンピュータと上述した本装置との間の通信と実際 上競合なしで、二つの記憶媒体の間の制限のないデータ転送を行うことを可能と している。充分なるソリッドステートメモリを使用することにより、複数個の同 時的に活性なデータストリームに対してデータの効率的な保持を行うことを可能 とする。メモリ管理は、歴史的活動に基づいたデータアクセスを予測するマイク ロプロセサを介して行われる。データは管理アルゴリズムに基づいてディスク媒 体からソリッドステートメモリ内へ移動され、そのことは、時間臨界的経路にお いてテーブルサーチを使用することを必要とすることはない。ソリッドステート メモリ内に格納されているデータへのホストコンピュータのアクセスはソリッド ステート速度に近いものであり、磁気ディスク上に格納されているデータへのア クセスは磁気ディスク速度に近いものである。ホストから本装置へ送給される全 てのデータは、チャンネル能力によってのみ制限されるソリッドステート速度に おいて転送される。

バー゛ウェアの手口 本発明に基づいて構成した装置を図２に示しである。メモリ装置２００は、独立 的なモジュールであり、それは外界との三つの接触点を有している。その主要な コンタクトは、ホストインターフェース２０４を介してのホストコンピュータ２ ０１との接触である。ホストインターフェース２０４は、例えば、専用ＳＣ５Ｉ 制御プロセサを有しており、それはホストコンピュータ２０１とメモリマネジャ ２０５との間の通信を取扱う。オペレータインターフェースがコンソール２０７ を介して設けられており、それはユーザがメモリ装置２００の全体的な制御を行 うことを可能とする。別のコンタクト即ち接触点はデュアルインライン即ちＰＣ コンピュータ接続であって、それはメモリ装置２００の動作状態又はユニットの ステータスを調べるためのものである。

メモリマネジャ２０５はディスクドライブ２１０（又は高容量メモリ装置）及び ソリッドステートメモリ２０８の二つの格納媒体内へのデータの格納及びそれら からのデータの検索を管理するのに必要な全ての機能を取扱う。メモリマネジャ ２０５は、一つ又はそれ以上のマイクロプロセサ２０５−１等と、関連するファ ームウェア２０５−２と、例えばアドレス変換（Ａ　Ｄ　Ｔ）テーブル２０５− ３及び最も最近でなく使用した（ＬＲＵ）テーブル２０５−４等の管理テーブル から構成されている。

ソリッドステートメモリ２０８は、その経験に基づいて、メモリマネジャ２０５ がホストコンピュータ２０１に対して最も有用であるか又は近い将来において有 用なものとなる蓋然性が最も高いと思われるデータに対して使用される。

磁気ディスク２０１は全てのデータに対しての究極的な格納装置即ち記憶装置で あり、必要とされる大きな記憶容量を与える。ディスクインターフェース２０９ は、メモリマネジャ２０５とディスクドライブ２１０との間の通信を取扱うため の別の専用の制御プロセサ（例えば、ＳＣ５Ｉプロセサ）として作用する。

機能的エラー及び動作上の統計に関する情報は、診断モジュール−エラーロガー ２０６によって維持される。モジュール２０６へのアクセスは、デュアルインラ イン２０２又はコンソール２０７のいずれかによって行われる。コンソール２０ ７は、本ユニットの電源を入れたり外したりすること、エラーロガーの読取又は リセット動作、又は本ユニットの統計の調査等の動作に対しメモリ装置２００へ のオペレータのアクセスとして作用する。

メモリ装置２００は、パワーバックアップシステム２０３を有しており、それは 再充電可能なバッテリを具備している。バックアップシステム２０３は、通常の パワーが中断された場合に、メモリ装置２００へのパワーの供給を維持するため のものである。

このようなパワーの中断が発生すると、メモリマネシャ２０５は必要な動作を行 って、ソリッドステートメモリ２０８内に格納されている全てのアップデートさ れたデータを、メモリ装置２００をシャットダウンする前に、磁気ディスク２１ ０上へ供給する。

図３は本発明の一実施例のハードウェア制御器ブロックを示している。図３に示 した如く、ハードウェア制御器３００は三つのＩ１０ポート３０１，３０２゜３ ０３を与えている。Ｉ１０ポート３０１及び３０２は、ハードウェア制御器３０ ０を一つ又はそれ以上のホストコンピュータ２０１　（図２）へ接続するために 使用される差動的ＳＣ５Ｉポートである。Ｉ１０ポート３０３はシングルエンド ＳＣ５Ｉポートであり、制御器３００をディスクドライブ２１０　（本実施例に おいては、５．２５インチの磁気ハードディスクドライブ）へ接続するために使 用されている。

ディスクドライブ２１０はホストコンピュータ２０１から制御器３００内へ流れ るデータに対しての長期的な非揮発性の記憶装置を与えている。「差動的」及び 「シングルエンド」という用語は、ＳＣ５Ｉポートの特定の電気的特性に関する ものであって、これら二つの間の最も顕著な差異は、許容可能なＩ１０ケーブル 長の分野に存在している。Ｉ１０ポート３０１．３０２，３０３のＳＣ５Ｉに関 する側面については、それら以外のものにおいては、同一である。

キャッシュメモリ３０８　（メモリ２０８に対応）は大型の高速メモリであって 、ダイナミックな態様で、現在アクティブ即ち活性なデータ及び潜在的にアクテ ィブなデータを格納するために使用される。

キャッシュメモリ３０８の格納容量は、任意の寸法に選択することが可能であり 、図３に図示した実施例においては、６４メガバイトの格納容量を有している。

キャッシュメモリ３０８は１６メガワードとして構成されており、各ワードは四 個のデータバイト（３２ビツト）及び７ビツトのエラー補正コードから構成され ている。典型的には、キャッシュメモリ３０８の格納容量は、それと共に動作す る一つ又はそれ以上の磁気ディスク２１０（図２）の格納容量の１００％に対し 約０．５％の範囲内に選択される。キャッシュメモリ３０８の小さな部分が、キ ャッシュ動作を管理するために必要とされるテーブルを格納するために使用され るか、又は、この目的のために異なったメモリ（図示していないがマイクロコン トローラ３０５によりアクセス可能なもの）が使用される。

ＥＤＡＣ回路３０６が、キャッシュメモリ３０８に対してエラー検知及び補正機 能を行う。この実施例においては、ＥＤＡＣ回路３０６はキャッシュメモリ３０ ８に書込まれた各３２ビツトデータワードに対し７ビツトのエラー補正コードを 発生し、この情報は、それが発生されたデータワードと共に、キャッシュメモリ ３０８へ書込まれる。このエラー補正コードは、キャッシュメモリ３０８へ最後 に書込まれてからそのデータが崩壊していないことを検証するために、キャッシ ュメモリ３０８からデータが検索される場合に、ＥＤＡＣ回路３０６により検査 される。この実施例に対して選択された修正ハミングコードは、ＥＤＡＣ回路３ ０６が、発生する全ての単一ビットエラーを補正し且つ発生する全ての２０ビツ ト及び多くのマルチビットエラーを検知することを可能としている。

エラーロガー３０７は、ＥＤＡＣ回路３０６によって検知されたエラーの記録を 与えるために使用されている。エラーロガー３０７によって記録された情報は、 解析及び／又は表示を行うためにマイクロコントローラ３０５によつて検索され る。この情報は、マイクロコントローラ３０５によって特定のビットエラー（単 一ビットエラーの場合）又は特定のワードエラー（２０ビツトエラーの場合）を 識別することを可能とするのに充分に詳細なものである。

ＥＤＡＣ回路３０６が単一ビットエラーを検知する場合には、そのデータがその データにより要求されたインターフェース（プロセサ／キャッシュインターフェ ース論理３１１．ホスト／キャッシュインターフェース論理３１１及び３１２、 及びディスク／キャッシュインターフェース論理３１３）へ転送される場合に補 正される。又、このエラー条件を処理することを可能とするための信号がマイク ロコントローラ３０５へ送給される（それは、エラーロガー３０７の内容に基づ いてのエラーの解析、そのエラーを揉消すことを試み、且つそのエラーがソフト であるか又はハードであるかを決定するためにその揉消しの結果の解析が関与す る）。

ＥＤＡＣ回路３０６が２０ビツトエラーを検知する場合には、信号がマイクロコ ントローラ３０５へ送給される。マイクロコントローラ３０５は何等かのデータ が崩壊したことを認識する。その崩壊がＡＤＴ又はＬＲＵテーブル内において発 生した場合には、現在欠陥性のテーブルを他のものから再構築し、次いで両方の テーブルをキャッシュメモリ３０８の異なった部分へ再配置させる試みが行われ る。

ユーザデータを保持するキャッシュメモリ３０８のエリアにおいて崩壊が発生し た場合には、マイクロコントローラ３０５は新たなデータ転送コマンドを受付け ることを拒否する前に、可及的に多くのデータを救済する試みを行う（例えば、 キャッシュメモリ３０８の適宜の部分をディスクドライブ２１０へ転送する）。

ホストコンピュータ２０１からのステータス要求に対する任意の応答は、メモリ 装置２００がもはや適切に動作をしていないことを認識するためにホストコンピ ュータ２０１を使用することが可能である情報を有している。

マイクロコントローラ３０５は、プログラム可能（書込可能）コントロールプロ セサ３１４（例えば、インテルコーポレーションから入手可能な８０Ｃ１９６マ イクロコントローラ）、６４キロバイトのＥＰＲＯＭメモリ３１５、Ｉ１０ポー ト３０１，３０２，３０３と、キャッシュメモリ３０８と、ＥＤＡＣ３０６と、 エラーロガー３０７と、ホスト／キャッシュインターフェース論理３１１及び３ １２と、ディスク／キャッシュインターフェース論理３１３と、プロセサ／キャ ッシュインターフェース論理３１６と、直列ポート３０９とをプログラム可能コ ントロールプロセサ３１４が制御することを可能とするためのハードウェアを有 している。

プログラム可能コントロールプロセサ３１４は、直接的に実行することが可能で ある形態に変換されているソフトウェアプログラムによって支配される機能を実 行する。これらのソフトウェアプログラムはＥＰＲＯＭメモリ３１５内に格納さ れている。

一実施例においては、ホスト／キャッシュインターフェース論理セクション３１ １及び３１２は基本的に同一なものである。各ホスト／キャッシュインターフェ ース論理セクションはＤＭＡ、バイト／ワード、ワード／バイト、キャッシュメ モリ３０８へのアクセスを得るために対応するＩ１０ボート（３１１の場合は３ ０１，３１２の場合は３０２）に対して必要とされるアドレスレジスタハードウ ェアを有している。各ホスト／キャッシュインターフェース論理セクションは、 更に、マイクロコントローラ３０５を介して制御を行うことを可能とするハード ウェアを有している。この実施例においては、Ｉ１０ポート３０１及び３０２は ８ビツト（バイト）のデータ経路幅を有している。キャッシュメモリ３０８は３ ２ビツト（ワード）のデータ経路幅を有している。

ディスク／キャッシュインターフェース論理３１３はホスト／キャッシュインタ ーフェース論理セクション３１１及び３１２に類似している。それは、ディスク Ｉ１０ポート３０３がキャッシュメモリ３０８へのアクセスを獲得するのに必要 なりＭＡ、パイ゛ト／ワード、ワード／バイト、アドレスレジスタハードウェア を有している。ディスク／キャッシュインターフェース論理３１３は、更に、マ イクロコントローラ３０５を介しての制御を可能とするハードウェアを有してい る。この実施例においては、Ｉ１０ボート３０３は８ビツト（バイト）のデータ 経路幅を有している。

プロセサ／キャッシュインターフェース論理３１６は、ホスト／キャッシュイン ターフェース論理セクション３１１及び３１２及びディスク／キャッシュインタ ーフェース論理３１３に類似している。それは、プログラム可能コントロールプ ロセサ３１４がキャッシュメモリ３０８へのアクセスを獲得するために必要とさ れるＤＭＡ、半ワード／ワード、ワード／半ワード、アドレスレジスタハードウ ニアラ有している。プロセサ／キャッシュインターフェース論理３１６は、更に 、マイクロコントローラ３０５を介しての制御を可能とするためのハードウェア を有している。この実施例においては、プログラム可能コントロールプロセサ３ １４は１６ビツト（半ワード）のデータ経路幅を有している。

直列ポート３０９は、システム２００に対して人のインターフェースを与えるた めに外部装置（例えば、小型コンピュータ）の接続を可能としている。

直列ポート３０９は、診断の開始、診断結果の報告、システム２００の動作パラ メータのセットアツプ、システム２００の性能のモニタ、システム２００内部に 記録されたエラーの検討を行うことを可能とする。他の実施例においては、直列 ポート３０９は、外部装置から制御プログラム格納部（例えば、メモリ３１５が ＥＰＲＯＭではなくＥＥＰＲＯＭで実現されている場合）へ異なる及び／又は改 良されたソフトウェアプログラムを転送することを可能としている。

′テーブルのフ　−マ・・ アドレス変換（ＡＤＴ）テーブルのフォーマットＬＲＵテーブルと共に、アドレ ス変換テーブルは、キャッシュ動作を管理するために必要な情報を維持している 。ＡＤＴテーブル内には二つのセクションが存在しており、即ちインデックスさ れた即ち表の形式の部分と、−組のインデックスされていない即ち単一値項目で ある。

ＡＤＴテーブルのインデックスされていない部分は、二つのタイプのデータフィ ールドを有しており、即ち第一のデータフィールドはキャッシュ管理に基本的な 項目であり、第二のデータフィールドは本ユニットの性能の記録を維持するデー タ項目に関するものである。

インデックスされていない項目の第一グループ、即ちキャッシュ管理に必要なも のに対するグループは、以下の単一値項目を有している。

（１）ＡＤＴ−ＣＮＬ キャッシュされるディスクスピンドル上のトラック数であり、それはＡＤＴテー ブル内のライン数に等しい。これはレディキャッシュユニットが構成される時に セットされ、本ユニットが動作中は変化されることはない。

（２）ＡＤＴ−ＨＥＡＤ−ＰＯＳ キャッシュディスクの読取／書込ヘッドの現在位置。これはヘッドが位置決めさ れる毎にアップデートされる。

（３）ＡＤＴ−ＳＷＥＥＰ−ＤＩＲ バックグラウンド書込みの現在のスィーブが進行している方向。これは、スイー プがディスクを横断してその方向を逆転することにアップデートされる。

（４）ＡＤＴ−ＭＯＤ−ＣＯＵＮＴ ホストからの書込みによって修正されており且つディスクサーバーによりディス クへの書込みを現在待機しているキャッシュ内のトラックの総数。これは、ホス トによって修正されていないキャッシュトラックがアップデートされる場合に１ だけ増加され、且つそれは修正されるキャッシュトラックがキャッシュディスク ヘコビーされる毎に１だけ減少される。

第ニゲループのインデックスされていない項目は、ユニットの性能を記録する項 目であって、且つ本ユニットの現在の動作特性を計算するためにそれらの全てが 使用される。それらは、以下の単一値項目を包含している。

（１）ＡＤＴ−ＲＥＡＤ−ＨＩＴＳ 最後のリセットから発生したキャッシュ読取ヒツトの数。この値は、ＰＣ／コン ソールからリセット動作によりゼロヘセットされる。それは、キャッシュメモリ 内に存在するデータが完全に満足する各読取Ｉ１０に対しｌだけインクリメント される。

（２）ＡＤＴ−ＲＥＡＤ−ＭＩ　５ＳＥＳ最後のリセット以来遭遇したキャッシ ュ読取ミスの回数。この値は、ＰＣ／コンソールからのリセット動作によりゼロ ヘセットされる。キャッシュメモリ内に存在するデータから完全に満足されるこ との出来ない各読取Ｉ１０に対しｌだけインクリメントされる。

（３）ＡＤＴ−ＷＲＩ　ＴＥ−ＨＩ　ＴＳ最後のリセット以来遭遇したキャッシ ュ書込ヒツトの回数。この値は、ＰＣ／コンソールからのリセット動作によって ゼロヘセットされる。対応する−つ又はそれ以上のトラックがキャッシュメモリ 内に見つかった場合に各書込Ｉ１０に対して１だけインクリメントされる。

（４）ＡＤＴ−ＷＲＩ　ＴＥ−ＭＩ　Ｓ　Ｓ　ＥＳ最後のリセット以来遭遇した 書込ミスの回数。この値はＰＣ／コンソールからのリセット動作によりゼロヘセ ットされる。一つ又はそれ以上の対応するトラックがキャッシュメモリ内に見つ からない場合に各書込Ｉ１０に対してｌだけインクリメントされる。

スピンドル上の各データトラックに対し表部骨内に１本のラインが存在している 。１本のラインはそのライン番号即ちインデックスによって参照される。

そのライン番号はディスク上のトラック番号に直接的に対応している。ホストが ディスク上のデータへアクセスするか又は修正することを所望する場合、開始セ クタアドレスを参照し且つアクセス又は修正されるべきセクタ数を表示すること により行われる。

キャッノユを行うためには、開始セクタアドレスがトラック識別子へ変換され且 つそのトラック内においてオフセットされる。

ディスクセクタアドレスはそれをトラック当たりのセクタ数によって割算するこ とにより、トラック番号及びセクタオフセットへ変換される。その残り（余り） は該トラック内へのオフセットである。その商はトラック識別子であり且つＡＤ Ｔテーブル内へのインデックスである。このインデックスを使用して、特定した ディスクトラックの条件をＡＤＴテーブル内のデータから直接的に決定すること が可能であり、キャツシュヒツト又はミスを決定するためにサーチが必要とされ ることはない。

各ＡＤＴラインは以下の項目を有している。

（１）ＡＤＴ−５ＬＯＴ このＡＤＴテーブルラインのインデックスと同一の数のディスクトラック内に保 持されるデータを有するキャッシュスロット数。構成上、ＡＤＴ−５ＬＯＴ内の 値は、キャッシュしたディスクトラックに関連したＬＲＵテーブル内のラインを 指し示している。ディスクトラックがキャッシュ内にない場合には、このフィー ルド内の値は無意味であり且つそのナル値ヘセットされる。何等テーブル装置な しでキャツシュヒツトを完全にサービスすることが可能であるのはこのフィール ドによるものである。このフィールド内のナル値は、対応するディスクトラック 　゛がキャッシュ内に格納されていないことを示している。このフィールドは、 トラックがＳＳＤエリア内へエンターされるか又はそこから取除かれる度にアッ プデートされる。

（２）　ＡＤＴ−ＭＯＤ　Ｉ　Ｆ　Ｉ　ＥＤ対応するキャッシュされたトラック がホストからの書込動作によって修正されているか否か従うてキャッシュからデ ィスクヘコピーする必要があるか否かを表わすフラッグ。

′に　されていない　ＬＲＵ　テーブルのム１ニヱユ止 ＬＲＵテーブルはキャッシュされたデータのトラックが最初にアクセスされた時 間に関する情報を維持している。この情報はキャッシュされていないデータトラ ックをキャッシュ内に配置されねばならない場合にどのキャッシュスロットが上 書きのために使用可能であるかを本ユニットが常に注意するために必要である。

その内容は、又、ＡＤＴテーブル内に保持されているデータに対する冗長性を与 え、従ってシステムの信頼性に貢献する。

ＬＲＵテーブル内には二つのセクションが存在しており、即ちインデックス付即 ち表部分と、−組のインデックスされていない即ち単一値項目である。

ＬＲＵテーブルのインデックスされていない部分は、キャッシュプロセスを管理 するのに必要なデータを有している。表部分はＬＲＵチェーン動作目的のための ポインタ、ＡＤＴテーブル内へのポインタ、及びリサイクルコントロールマーカ ーから構成されている。

キャッシュされていないディスクトラックに対してキャッシュエリアが必要な場 合にどのキャッシュしたトラックを上書きするかをシステムが決定するのはこの ＬＲＵ情報及びＡＤＴテーブル情報によるものである。インデックスされていな い項目は、キャッシュ管理のために必要であり、且つ以下の単一値項目を有して いる。

（１）ＬＲＵ−ＣＮＬ キャッシュエリア内のトラック等価スロット数であり、これはＬＲＵテーブル内 のライン数と等しい。

（２）ＬＲＵ−ＬＲＵ ＬＲＵ−ＬＲＵテーブル要素は、最も長い時間にわたり不変のままとされたキャ ッシュされたデータを有するキャッシュエリアトラックスロットを指し示す。そ れは、参照されたスロットに対する新たな活動がそれを最も最近に使用されたも のではないものとする場合にアップデートされる。参照されたスロットは、新た なデータをキャッシュ内に書込まねばならない場合の上書きをするための第一候 補者である。

（３）ＬＲＵ−ＭＲＵ ＬＲＵ−ＭＲＵテーブル要素は、ホストによって最も最近に参照されたキャッシ ュされたデータを有するキャッシュエリアトラックスロットを指し示す。

ＬＲＵ−ＭＲＵは、ホストからの読取又は書込のいずれかによってトラックが影 響を受ける度にアップデートされる。その時に、アクセスされるトラックのアド レスはＬＲＵ−ＭＲＵ内に配置され、且つＬＲＵチェーンがＬＲＵテーブルのイ ンデックスされた部分においてアップデートされる。

キャッシュデータエリア内の各データトラックスロットに対し表部針内に一本の ラインが存在している。一本のラインはそのライン番号即ちインデックスによっ て参照される。そのライン番号は、キャッシュデータエリア内の一つのスロット に直接対応している。

各ＬＲＵテーブルラインはポインタフィールドとその他のコントロールフィール ドとを有している。

（１）ＬＲＵ−ＴＲＡＣＫ 対応するキャッシュスロット内に現在存在しているディスクトラックを参照する ＡＤＴラインへのポインタ。構成上、この値は、又、存在する場合にそのデータ が現在対応するキャッシュスロット内に存在するディスクトラックの識別子であ る。

（２）ＬＲＵ−ＬＡＳＴ これはキャッシュデータスロットの双方向チェーンの一部である。ＬＲＵ−ＬＡ ＳＴは次に古い（使用上）キャッシュスロットへのポインタである。このスロッ トが最も古い場合には、ＬＲＵ−ＬＡＳＴはゼロを有している。

（３）ＬＲＵ−ＮＥＸＴ これは、キャッシュデータスロットの双方向チェーンの他の半分である。ＬＲＵ −ＮＥＸＴは次に新しい（使用上）キャッシュスロットへのポインタである。こ のスロットが最も新しいものである場合には、ＬＲＵ−ＮＥＸＴはゼロを有して いる。

（４）ＬＲＵ−ＣＡＣＨＥＤ−ＬＯＷ 有効なキャッシュされたデータを有するこのキャッシュされたトラックの最も低 いセクタのトラック関連番号を有するフィールド。

（５）ＬＲ（Ｊ−ＣＡＣＨＥＤ−ＨＩＧＨ有効なキャッシュされたデータを有す るこのキャッシュされたトラックの最も高いセクタのトラック関連番号を有する フィールド。

（６）ＬＲＵ−ＭＯＤ−ＬＯＷ 修正されたキャッシュされたデータを有するこのキャッシュされたトラックの最 も低いセクタのトラック関連番号を有するフィールド。

（７）ＬＲＵ−ＭＯＤ−ＨＩ　ＧＨ 修正されたキャッシュされたデータを有するこのキャッシュされたトラックの最 も高いセクタのトラック関連番号を有するフィールド。

（８）ＬＲＵ−ＬＯＣＫＥＤ 対応するキャッシュされたトラックが、現在、例えばディスクから獲得されたか 、ホストによづて修正されたか、又はキャッシュコントローラによってディスク へ書込まれたか等の何等か動作のターゲットであるか否かを表わすフラッグであ り、このような活動はその他のある動作に対してはトラックを使用不能なものと させる。

（９）ＬＲＵ−ＲＥＣＹＣＬＥ 対応するトラックがリサイクル用の候補者であるか否かを表わす単一ビットマー カー。それは、トラックが再使用される場合にはｌ　（オン）ヘセットされ、そ のトラックがリサイクルされる場合（ＭＲＵ位置へ移動される場合）は、０（オ フ）ヘセットされる。キャッシュアヘッド決定の結果としてトラックがキャッシ ュ内へ持込まれる場合には、それは初期的にＯヘセソトされる。キャッシュミス を満足させるために持込まれるトラックの場合、それは１ヘセツトされる。

１二１互辺１ 初期的ＡＤＴテーブル ユニットが最初にパワーオンされると、ＡＤＴテーブルは不定状態となる。動作 可能状態となるためには、それらの適宜のテーブル要素内へ初期値をエンターせ ねばならない。ＡＤＴテーブルのインデックスしていないフィールドに対する初 期値は以下の如くである。

ＡＤＴ−ＣＮＬフィールドは、トラック数としてキャッシュディスクの寸法ヘセ ットされねばならない。

ＡＤＴ−ＨＥＡＤ−ＰＯＳフィールドは、ヘッドが現在ディスクの端部にあるこ とを表わすためにゼロヘセットされる。このことは真実である場合もない場合も あるが、そのことは重要ではない。それは、ディスクへの最初のアクセスで正し くされる。

ＡＤＴ−５ＷＥＥＰ−Ｄ　Ｉ　Ｒフィールドは、ヘッドが上方向（トラックアド レスに基づいて）に移動することを表わすために１へ任意的にセットされる。

このことは、最初のバックグラウンドスィーブの開始で補正される。

ＡＤＴ−ＭＯＤ−ＣＯＵＮＴフィールドは、ディスクヘコビーされるべ（修正さ れたトラックがキャッシュ内に待機していない事実を反映するために０ヘセツト される。

ＡＤＴ−ＲＥＡＤ−ＨＩ　ＴＳフィールドは、読取動作期間中にキャツシュヒツ トが発生しなかった事実を反映するために０ヘセツトされる。

ＡＤＴ−ＲＥＡＤ−ＭＩ　５ＳＥＳフイールドは、読取動作期間中にキャッシュ ミスが発生しなかった事実を反映するために０ヘセツトされる。

ＡＤＴ−ＷＲＩＴＥ−ＨＩＴＳフィールドは、書込動作期間中にキャツシュヒツ トが発生しなかった事実を反映するために０ヘセツトされる。

ＡＤＴ−ＷＲＩＴＥ−ＭＩ　５ＳＥＳフイールドは、書込動作期間中にキャッシ ュミスが発生しなかった事実を反映するために０ヘセツトされる。

ＡＤＴテーブルの全てのラインの全てのインデックスされたフィールドは、初期 的に０ヘセツトされ、トラックがキャッシュ内に存在しないことを表わす。

ｒＬＲＵテーブル ユニットが最初にターンオンされると、ＬＲＵテーブルは不定状態にある。動作 可能状態となるためには、それらの適宜のテーブル要素内に初期値がエンターさ れねばならない。チェーンフィールドを初期化させるために多数の許容可能な方 法が存在しているが、簡単な方法が選択され且つそれについて以下に説明する。

ＬＲＵテーブルのインデックスされていないフィールドに対する初期値は以下の 如くである。

ＬＲＵ−ＣＮＬフィールドは、トラック等価スロットの数としてキャッシュの寸 法ヘセットされねばならない。

ＬＲＵ−ＬＲＵフィールドは、最も古いものとして最も低い番号の付いたキャッ シュスロットを表わすために１ヘセツトされる。これは、選択されたチェーン値 についてい（場合の任意的な選択である。

ＬＲＵ−ＭＲＵフィールドは、最も最近に使用されたものとして最も高いキャッ シュスロット表わすためにＬＲＵ−ＣＮＬと等しくセットされる。これは、選択 された初期的チェーン値についていく場合の任意的な選択である。

ＬＲＵテーブルのインデックスされたフィールドに対する初期値は以下の如くで ある。

ＬＲＵテーブルの全てのラインのＬＲＵ−ＴＲＡＣＫフィールドは、ディスクデ ータトラックが現在キャッシュ内に保持されていないことを表わすために０ヘセ ツトされる。

ＬＲＵテーブルの全てのラインのＬＲＵ−ＬＡＳＴ　’フィールドは、そのライ ンのインデックス−１ヘセツトされる。この作用は、ＬＲＵ−ＮＥＸＴ値に対す る設定と共に、キャッシュ始動動作に適したチェーン化リストを発生する。

ＬＲＵテーブルの最も高いものを除いた全てのラインのＬＲＵ−ＮＥＸＴフィー ルドは、そのラインのインブックスミ＋１ヘセツトされる。最も高いラインのＬ ＲＵ−ＮＥＸＴ値はＯヘセットされる。これらの設定は、ＬＲＵ−ＬＡＳＴ値に 対する設定と共に、キャッシュ始動動作に適したチェーン化リストを発生する。

全てのラインのＬＲＵ−ＣＡＣＨＥＤ−ＬＯＷフィールドは、ディスクトラック のどの部分も現在キャッシュ内に保持されていないことを表わすためにそのナル 値ヘセットされる。

全てのラインのＬＲＵ−ＣＡＣＨＥＤ−ＨＩ　ＧＨフィールドは、ディスクトラ ックのどの部分も現在キャッシュ内に保持されていないことを表わすためにその ナル値ヘセットされる。

全てのラインのＬＲＵ−ＭＯＤ−ＬＯＷフィールドは、現在キャッシュ内に保持 されているディスクトラックのどの部分も修正された条件にないことを表わすた めにそのナル値ヘセットされる。

全てのラインのＬＲＵ−ＭＯＤ−ＨＩ　ＧＨフィールドは、現在キャッシュ内に 保持されているディスクトラックのどの部分も修正条件にないことを表わすため にそのナル値ヘセットされる。

ＬＲＵテーブルの全てのラインのＬＲＵ−ＬＯＣＫＥＤフィールドは、どのキャ ッシュスロットも現在ロックされていないことを表わすために０ヘセツトされる 。

ＬＲＵテーブルの全てのラインのＬＲＵ−ＲＥＣＹＣＬＥフィールドは、どのス ロットも現在リサイクル用の候補者ではないことを表わすためにＯヘセットされ る。

、ＡＤＴ−−プル 動作状態ＡＤＴテーブル例は、最初の（サンプル）Ｉｌｏが発生した後及びシス テムが完全な活性条件に到達した後の条件を示している。これらの完全な活性例 は、ＡＤＴテーブル内容の状態に関しいくつかのＩｌｏの影響を示している。こ れらの例の中には、更に、キャッシュからディスクへ修正したトラックを書込ん だバックグラウンドスイープの効果も設けられている。これらの特定のサンプル 動作の詳細な説明はＬＲＵテーブルの説明において後に説明する。

ｊＬＲＵテーブル 動作状態ＬＲＵテーブル例は、最初のＩｌｏが発生した後及びシステムが完全な 活性条件に到達した後の条件を示している。これらの完全な活性例は、ＬＲＵテ ーブル内容の状態に関しいくつかのＩｌｏの効果を示している。

サンプル■　０の　日 説明の便宜上、Ｉｌｏの一つのサンプルを詳細に説明すべ（選択した。説明のた めに選択したものは動作箇所において作用のトレースからとられたＩ１０番号１ ，１０００，１００１．１００２であり、それらは説明したシステム内に投影さ れたものとして表４に詳細に示しである。サンプルＩ１０の以下の説明はＡＤＴ テーブルとＬＲＵテーブルの両方に関する効果を包含している。

Ｉ１０動作番号ｌに関連した作用： （１）このＩｌｏはディスクトラック番号４６及び４７が関与する読取であり、 何もキャッシュ内に存在しないので、それはキャッシュミスである。トラック４ ６の一部とトラック４７の全てがキャッシュ内へ持込まれる。ＡＤＴテーブルは 修正されてキャッシュ内のこれらのトラックの位置を示し、今キャッシュされた 各トラックの量が記録され、チェーンが再連結されてＭＲＵとなるべきトラック 及びＭＲＵの次のトラックを示し、且つそれらは両方ともリサイクル用にマーク が付けられる。それらは、チェーン内のＬＲＵ位置に到達するまでに少なくとも 一度使用されているので、それらはリサイクル用のマークが付けられる。

（２）トラック４７におけるＩｌｏの端部からの距離及び１１０寸法に基づいて 、トラック４８のプレフェッチが開始される。この活動は、ＡＤＴテーブル及び ＬＲＵテーブル内に反映されることはない。

何故ならば、それは現在のＩｌｏの完了後にバックグラウンド動作として開始さ れるからである。

９９９Ｉ１０が発生した後に、ＡＤＴテーブル及びＬＲＵテーブルはあるステー タスに到達している。

Ｉ１０番号１０００はセクタアドレス１４，１９０において開始する６８個のセ クタの読取である。これはディスクトラック５６のセクタ１１乃至７８を占有す る。これらの条件に基づいて、以下の作用はＩ１０動作番号１０００に関連して いる。

（１）このＩｌｏはキャッシュ内に存在しないトラック５６が関与する読取であ り、その所要の部分はキャッシュ内に持込まれねばならない。この必要とされる データをフェッチする間に、要求されたデータの端部からそのトラックの端部ま でのトラック５６の部分もフェッチされる。ここでこのことが行われるのは、そ れを行うのに最も便利な時間だからであり、且つプレフェッチ規則を満足させる 。ＬＲＵテーブルは、トラック５６のキャッシュ動作を反映すべくアップデート され、且つこのデータがフェッチされるスロットがＬＲＵチェーン内のＭＲＵ位 置に配置される。

（２）トラック５６をキャッシュするための場所を確保するために、古いＬＲＵ トラックはデキャッシュ即ちキャッシュメモリから取除かれる。

（３）読取Ｉ１０動作はバックグラウンドスィーブに対する必要性に影響を与え るものではない。ディスクヘコピーする必要があるトラックはキャッシュ内に三 つあり、この条件は現在のＩｌｏによって不変のまま留まる。

（４）いくつかのキャッシュスロットがリサイクル用にマークが付けられており 、該チェーンのＬＲＵ端部におけるスロット及びそれを指し示すスロットを包含 している。プレフェッチが開始される前に、これらはＭＲＵ位置及びＭＲＵの次 の位置へ移動され、且つそれらのリサイクルマーカーは取除かれる。

（５）トラック５７は既にキャッシュ内に存在しているので、そのためのプレフ ェッチは必要ではない。

（６）Ｉｌｏ　（６８個のセクタ）の寸法及びトラック５６内の最初のセクタへ の現在のＩｌｏの近接度は、トラック５５がキャッシュアヘッド作用によってプ レフェッチされるべきであることを表わす。そのプレフェッチはバックグラウン ド動作として開始される。ＬＲＵチェーン及びリサイクル状態に基づいて、トラ ック５５はスロット３内ヘキヤツシユされる。しばらくの間、それはチェーン内 のＭＲＵ位置を占有する。

Ｉ１０動作番号１００１に関連した作用：（１）Ｉｌｏｌｏｏｏによって開始さ れたトラック５５のプレフェッチは現在完了している。

（２）Ｉ１０番号１００１はトラック６１のセクタ１９１−２５６及びトラック ６２のセクタｌ−２が関与する書込である。それらを参照するＬＲＵテーブル及 びＡＤＴテーブルはアップデートされる。

（３）このＩ１０作用は二つのキャッシュしたトラックを修正しており、ディス クへ書込まれることが必要なトラックの総数をバックグラウンドスイープ用のト リガ点とさせる。

（４）バックグラウンドスイープが開始され、且つキャッシュからディスクへ修 正したトラックの書込を開始する。

（５）バックグラウンドスイープはディスクスピンドルを使用するので、本ユニ ットがキャッシュ内へのトラック６０のプレフェッチを検討する場合であっても 、キャッシュアヘッドが開始されることはない。

Ｉ１０動作番号１００２に関連した作用：（１）バックグラウンドスイープがキ ャッシュからディスクへの全ての修正したトラックの書込を完了しており、従っ て、それは次いで休眠状態となっている。

（２）ｌ１０１００２は、既にキャッシュ内に存在するトラック２０４が関与す る書込であった。そのトラックは、修正されたものとしてＡＤＴテーブル内にマ ークが付けられている。ＬＲＵテーブルにおいて、スロット番号１３内のトラッ ク２１４はＭＲＵ−ＬＲＵチェーンから取除かれており、且つ修正された量がＬ ＲＵ−ＭＯＤ−ＬＯＷフィールド及びＬＲＵ−ＭＯＤ−ＨＩ　ＧＨフィールド内 に記録される。

（３）トラック２１４内の現在のＩｌｏの位置がキャッシュアヘッド動作の充分 な根拠を与えるためにトラックの端部に充分近いものであるので、トラック２１ ５のプレフェッチが開始される。この作用は、ｌ１０１００２に対するＡＤＴテ ーブル及びＬＲＵテーブル内には表われない。何故ならば、それは、現在のＩｌ ｏの完了後にバックグラウンドにおいて発生するからである。

（４）トラック２１５のプレフェッチが開始されているので、トラック２１３は プレフェッチのために考慮されることはない。

ｌ」ユニ１辷立」二二 フ　−ムラエア 本発明のメモリコントローラは、それが取扱うことを必要とする作用が存在しな い場合には準体眠状態となる。図４のフローチャートに示した如（、コントロー ラを活性状態とさせる三つのタイプの発生原因がある。

（１）ホストコンピュータがコマンドを送給する場合 （２）バックグラウンドスイープがイベントを完了する場合 （３）バックグラウンドスイープがタイムアウトする場合 可能である限り、ホストコンピュータのコマンドは他のメモリ装置の活動に対し て優先度が与えられている。従って、ホストからのコマンドが受取られると、そ れはすぐにホストコマンドハンドラへ渡される。そのコマンドによって要求され る活動乃至は作用が完了すると、メモリコントローラはバックグラウンドスイー プが活性状態であるか否かを決定す　゛る。活性状態にない場合には、バックグ ラウンドステータスを検査し、且つ、後にバックグラウンドチェックに関して説 明する如（、適宜の作用が行なわれる。バックグラウンドステータスチェックに 続いて、キャッシュアヘッドステータスがチェックされ、そのことについては後 にキャッシュアヘッドステータスに関して説明する。次いで、該コントローラは 次のホストからのコマンドを待つ。該コントローラはその時には完全に非活性状 態にない場合があり、バックグラウンドスィーブ又はキャッシュアヘッドのいず れかが何等かのディスク活動を開始させたが又は継続して行っている場合がある からである。バックグラウンドが活性状態にあることが判明すると、その活動は 、後にバックグラウンド継続に関して説明する如（、もはややるべき直接的な仕 事が存在しなくなる時まで継続して行われる。

バックグラウンドスィーブがコマンドを完了すると、該コントローラはスイープ がその注意を必要とすることを表わす信号によってインタラブド（中断）が与え られる。その時には、該コントローラは、待機しているものがある場合には、次 のスィーブイベントを開始し、且つバックグラウンド継続に関して後に説明する 如く、必要性に基づいて次のスィーブイベントをセットアツプする。各スイープ イベントの完了時に、該コントローラは、そのスイープを継続する必要性がある か否かを決定する。そのような必要性が存在しない場合には、バックグラウンド スイープは休眠状態とされる。いずれの場合においても、該コントローラがその ハウスキーピングを完了すると、それは非活性状態となりその次のタスクを待機 する。

バックグラウンドスィーブは二つの方法のうちのいずれかによって活性化させる ことが可能である。

即ち、設定した数のキャッシュされたトラックが修正された場合及びキャッシュ からディスクへ書込を行う必要性がある場合に活性化される。このスイープは、 又、タイムアウトによって活性化される場合がある。スィーブが非活性状態にあ り、且つ予め設定した量の時間を超えて待機しているキャッシュからディスクへ 書込まれることを待機している修正されたトラックが存在する場合にタイムアウ トが発生する。タイムアウトが発生すると、該コントローラはスイープがその注 意を必要とする信号を受取る。

該コントローラはバックグラウンドスイープを開始しくバックグラウンド開始の 説明を参照）、且つ適宜のハウスキーピングを完了した後に、その注意を必要と する次のコマンド又はイベントを待つ。バックグラウンドスイープ自身は、それ をサービスするための直接的な必要性が存在しなくなるまで動作を継続して行う 。その時に、それも休眠状態とされる。

ホス　コマン゛　理 ホストコンピュータからコマンドが受取られると、それには最も高い可能な優先 度が与えられ且つ図５に示した如くに取扱われる。どのような活動乃至は作用が 必要とされているかを決定するために、このコマンドは解析されねばならない。

ファームウェアの一部は、その目的のために専用とされている（ホストコマンド 解析の説明を参照）。コマンドの解析は、コマンドのタイプ（読取、書込、シー ク又はその他）を決定し、且つ意味がある場合には、キャツシュヒツト／ミスの 決定を行う。この解析は、更に、後にそのコマンドのサービスを行う場合に使用 する一つ又はそれ以上のラインからなるテーブルをセットアツプする。

そのコマンドが読取であり且つそれがキャッシュから完全にサービスすることが 可能である場合（即ち、キャツシュヒツト）、そのコマンドはコントローラの読 取ヒツト部分によりサービスされる（読取ヒツト処理の説明参照）。

読取のいずれかの部分がキャッシュされたトラックからサービスすることができ ない場合（即ち、キャッシュミス）、そのコマンドはコントローラの読取ミス部 分へ渡される（読取ミス処理の説明参照）。

そのコマンドが書込であり且つその動作に関与する全てのトラックが既にキャッ シュ内に存在する場合には、そのコマンドはコントローラの書込ヒツト部分によ りサービスされる（書込ヒツト処理の説明参照）。

その書込のいずれかの部分がキャッシュされていない一つ又はそれ以上のトラッ クを関与させる場合には、そのコマンドはコントローラの書込ミス部分へ渡され る（書込ミス処理の説明参照）。

そのコマンドがシークであり且つターゲットトラックが既にキャッシュされてい る場合には、何等の作用が必要とされることはない。そのターゲットトラックが キャッシュされていない場合には、そのコマンドはコントローラのシークミス部 分へ渡される（シークミス処理の説明参照）。

ホス　Ｉ　Ｏコマン゛ 図６に示した如（、ホストコマンドの解析は、その動作に関与する各トラックの 位置を有するトラックアドレスリストを形成することを包含している（トラック アドレスリストセットアツプの説明参照）。

各このようなトラックに対して、そのリストは、それが既にキャッシュ内に存在 する場合には、キャッシュ内のトラックの現在の位置を有しており、又は、この コマンド及び関連したキャッシュ用活動が完了した後にキャッシュ内に存在する 。トラックが既にキャッシュされていない場合には、それをキャッシュ内に配置 させる空間が探し出され、且つその空間内に存在する現在のトラックはデキャッ シュされる、即ちキャッシュから取除かれる。この解析は、コントローラ論理を 促進させることが可能であるようにキャツシュヒツト／ミスフラッグをセットす ることを包含している。

う・・　アドレス変換　のセ・・　ア・・ブ図７に示した如く、トラックアドレ スリストをセットアツプするコントローラセグメントは、Ｉ１０ディスクトラッ クを決定するためにＩ１０セクタアドレス及び寸法を使用する（アドレス変換の 説明参照）。関与するトラック数も決定され、且つその各々に対して、その動作 に関与するトラックの部分が計算される。

７１４旦ス亙遣 図８はこの変換動作を示している。セクタアドレスをトラック寸法で割算するこ とによってトラックアドレスへ変換することが可能である。その場合の商はトラ ック番号であり、且つその残りはセクタが存在するトラック内へのオフセットで ある。

胱」Ｌ旦！Ｌ上」Ｌ作 図９を参照して説明する。読取ヒツトはキャッシュされたデータから完全に充足 される。コントローラのこのモジュールに到達するために、コマンドの解析が行 われ且つトラックアドレステーブルがセットアツプされる。この予備的な作業が 完了すると、ホスト読取コマンドがサブコマンドコントロールとしてトラックア ドレステーブルの各ラインを使用することによって満足させることが可能である 。全ての影響を受けるトラックの全ての必要とされる部分は既にキャッシュ内に あるので、全ての必要とされるデータはキャッシュからホストへ直接送給するこ とが可能である。ホストへデータを転送することに加えて、このモジュールは影 響を受けたトラックを再度チェーン化させてＬＲＵテーブル内において最も最近 に使用されたトラックとなる。

Ｌ１土ス１１ 読取ミス（図１０）はディスクから部分的に又は完全に満足される。コントロー ラのこのモジュールに到達するために、コマンドが解析され且つトラックアドレ ステーブルがセットアツプされる。この予備的作業が完了すると、ホスト読取コ マンドはサブコマンドコントロールとしてトラックアドレステーブルの各ライン を使用することにより満足させることが可能である。寸法がＲＥＡＤ−ＭＩ　Ｓ Ｓ−ＭＡＸＳＩＺＥ（読取−ミス−最大寸法）を超えるＩｌｏの場合には、キャ ッシュに何等影響を与えることなしにディスクからホストへ直接的にキャッシュ されていない部分が送られる。寸法がＲＥＡＤ−ＭＩＳＳ−ＭＡＸＳ　Ｉ　ＺＥ を超えないＩｌｏの場合には、動作はユニットの現在のモードに基づいて取扱わ れる。

本ユニットが緊急モードにない場合には、既にキャッシュ内にあるトラックセグ メントに対しては、データはキャシュからホストへ直接的に送給することが可能 である。キャッシュ内に存在しないトラックセグメントの場合には、データはデ ィスクからホストへ送給され、且つ同時的に、要求されたデータの第一セクタか らそのトラックの終端へのトラック部分がキャッシュへ送られる。対応するＬＲ ＵテーブルラインのＬＲＵ−ＣＡＣＨＥＤ−ＬＯＷ及びＬＲＵ−ＣＡＣＨＥＤ− ＨＩ　ＧＨフィールドがキャッシュへ持込まれたトラックの部分を反映すべ（セ ットされる。

本ユニットが緊急モードにある場合には、キャッシュ内に存在しないトラックに 対しては、データは、キャッシュ内へエンターされることなしに、ディスクから ホストへ直接的に送給される。

いずれのモードにおいても、データをホストへ送給することに加えて、このモジ ュールは影響されキャッシュされたトラックを再度チェーン化してＬＲＵテーブ ル内において最も最近に使用されたスロットとなる。

１立旦ユ上１１ 書込ヒツト（図１１）は完全にキャッシュ内において取扱われる。コントローラ のこのモジュールに到達するために、コマンドが解析され且つトラックアドレス テーブルがセットアツプされる。この予備的作業が完了すると、ホスト書込コマ ンドは、サブコマンドコントロールとしてトラックアドレステーブルの各ライン を使用することによって満足させることが可能である。全ての影響されたトラッ クは既にキャッシュ内に表わされているので、全てのデータは部分的トラックの 転送後のステージングに対する懸念なしに、ホストからキャッシュへ直接的に送 給することが可能である。キャッシュへデータを転送することに加えて、このモ ジュールは、そのスロットがＬＲＵチェーンにリンクされた場合には、ＬＲＵチ ェーンから影響を受けたキャッシュスロットを取除く。全ての場合において、対 応するＬＲＵ−ＭＯＤ−ＬＯＷ、ＬＲＵ−ＭＯＤ−ＨＩ　ＧＨｌＬＲＵ−ＣＡＣ ＨＥＤ−ＬＯＷ、ＬＲＵ−ＣＡＣＨＥＤ−ＨＩＧＨフィールドは、この新たなデ ータが存在することを反映するためにアップデートされる。

１点上ス１准 １１０寸法がＷＲＩＴＥ−ＭＩ　ＳＳ−ＭＡＸＳ　ＩＺＥ（書込−ミス−最大寸 法）を超える場合には、キャシュされていないトラック又はトラックセグメント とがキャッシュに何等影響を与えることなしに直接的にディスクへ書込まれる。

寸法がＷＲＩＴＥ−ＭＩ　ＳＳ−ＭＡＸＳ　Ｉ　ＺＥを超えルコとのなイＩ１０ の場合にはその動作はユニットの現在のモードに基づいて取扱われる。本ユニッ トが通常モードで動作している場合には、書込ミスはキャッシュ内において完全 に取扱われるが、データのディスクへの書込を可能とし且つ図１２に示した如く 関与した部分的トラックのキャッシュ内へディスクからのデータの転送後のステ ージングを制御するために、ＬＲＵ−ＣＡＣＨＥＤ−ＬＯＷ、ＬＲＵ−ＣＡＣ） ＩＥＤ−ＨＩＧＨ，ＬＲＵ−ＭＯＤ−ＬＯＷ、ＬＲＵ−ＭＯＤ−ＨＩ　Ｇ　Ｈフ ィールド内への情報を配置させることを必要とする。コントローラのこのモジュ ールに到達するためには、コマンドを解析し、且つトラックアドレステーブルを セットアツプする。この予備的作業が完了すると、ホスト書込コマンドは、サブ コマンドコントロールとしてトラックアドレステーブルの各ラインを使用するこ とによって満足させることが可能である。これはキャッシュミスであるので、影 響を受けるトラックの幾つか又は全てはキャッシュ内に存在することはなく、然 しなから、全てのデータはホストからキャッシュへ直接的に送給することが可能 である。

キャッシュコントローラはトラック又はいずれかの部分的トラックにおけるギャ ップを充填するためにデータの転送後のステージングのための責任を有している 。実際には、転送に関与した最初のトラック及び／又は最後のトラックのみが部 分的トラックとなることが可能であり、全ての内部のトラックは充填トラックで なければならず、従って、いずれの場合においても転送後のステージングを必要 とするものでない。転送後のステージングを必要とするトラックの場合には、コ ントローラはキャッシュイベントのリストをセットアツプし、全ての必要とされ るトラックセグメントをキャッシュ内へ持込み、キャッシュされたトラックの一 体性を維持する。キャッシュへデータを転送することに加えて、このモジュール はＬＲＵチェーンから影響されたトラックを除去する。本ユニットが緊急モード で動作している場合には、書込ミスの取扱いが、現在キャッシュされていないト ラックに対するキャッシュをバイパスし、そのデータをホストからディスクへ直 接的に送給する。ＬＲＵテーブル及びＡＤＴテーブルは影響されている場合のあ るキャッシュされたトラックに対してアップデートされる。

シー　キ　・・シ　ミス 図１３に示した如く、コントローラはシークコマンドを無視するオプションを有 している。何故ならば、コントローラは、究極的には、爾後の関連したＩ１０コ マンドを充足する責任があるからである。

ターゲットトラックが既にキャッシュ内に存在しているシークコマンドの場合に は、何等コントローラの作用は必要ではなく又適切なものでもない。ターゲット トラックがキャッシュ内に存在していないシークコマンドの場合には、コントロ ーラは、そのシークが指向されているディスクがビジーでない場合には、そのタ ーゲットトラックをキャッシュする。この作用は、読取又は書込コマンドによっ て追従されない限り、ホストはシークコマンドを送給することがないという仮定 に基づいている。シークが指向されているディスクが、シークコマンドがホスト から受取られた場合にビジーである場合には、そのシークコマンドは無視される 。

う・・　のデキ　・・シュ 発生する全てのキャッシュミスＩ１０に対し、且つ全てのキャッシュアヘッド動 作に対して、データの何等力）の前にキャッシュした一つ又はそれ以上のトラッ クはデキャッシュ即ちキャッシュから取り除かれねばならない。Ｌ　ＲＵテーブ ルの主要な機能は、データのどのキャッシュしたトラックがデキャッシュ即ちキ ャッシュから取除くための最良の候補者であるかをコントローラが迅速に決定す ることを可能とすることである。図１４に図示したデキヤツシユ用モジュールは 、デキャッシュされるべきトラックを選択する。通常、その最後の利用から最も 長い経過時間を有するトラックがデキャッシュされべきトラックである。これは ＬＲＵテーブルのＬＲＵ−ＬＲＵ要素によって指し示されるトラックである。Ｌ ＲＵ−ＬＲＵポインタは、最も最近でな（使用された即ち最も古いトラックへ常 にポイント即ち指し示すような態様で維持される。

第一条件は、トラックが非活性状態でなければならないことであり、即ち、この 時刻において何等かの活動の主題でないことである。殆どの活動がＬＲＵ−ＬＲ Ｕスポットからそれを再配置させるので、ＬＲＵ−ＬＲＵトラックが何等かの活 動を有することは極めて蓋然性が低い。然しなから、その蓋然性はデキヤツシユ 用アルゴリズムによってカバーされる。

トラックをデキャッシュすることが可能である前に充足されねばならない第二条 件は、デキャッシュされるべきトラックはリサイクル用の候補者であってはなら ないということである。それが最初にキャッシュされてから再使用されているか 又はそれが最後にリサイクルされてから再使用されているトラックはデキャッシ ュされない。その代わりに、このようにキャッシュされたトラックはＭＲＵ位置 ヘリサイクルされ、且つそのリサイクルマーカーが取除かれる。このように、こ のようなトラックは、それが最後にリサイクルされてから、又は、キャッシュア ヘッドトラックの場合には、それが最初にキャッシュされた時から再使用されて いないトラックよりもより長い時間の間キャッシュに留まることが許容される。

この手順の効果は、使用されたものよりもより速いレートでＬＲＵリストを介し て使用されていないキャッシュアヘッドトラックが下方向へ移動することを可能 とし、且つより有用なトラックがより長い時間の間キャッシュ内に留まることを 可能とする。

上述した理由のいずれかに対して、ＬＲＵ−ＬＲＵトラックがデキャッシュする ことが不可能な場合には、ＬＲＵチェーンは次のＬＲＵ候補者へポイント即ち指 し示す。ＬＲＵトラックがリサイクルされることは異常なことではないが、デキ ヤツシユ用モジュールが、デキャッシュされるべきスロットを捜し出すために一 つを超えたリサイクルされていないＬＲＵスロットを検査することが必要となる ことは極めて異常な条件である。

デキャッシュ用の実際の候補者が識別された場合には、ＬＲＵテーブルとＡＤＴ テーブルの両方がアップデートされて、選択された候補者がもはやキャッシュさ れていないことを反映する。これは、マイナーな量の作業であり、何等ディスク の活動が関与することはない。

キ　・・シュアへ・・　゛ キャツシュヒツト及び管理動作は図１５に示しである。コントローラが、そのＩ ｌｏがキャツシュヒツトであったか又はキャシュミスであったかに否かに拘らず 、読取動作である全てのホストＩ１０の後にキャッシュアヘッドを試みる。ホス トから本装置へデータを書込む動作は、何等キャッシュアヘッド動作を必要とす るものではない。何故ならば、デー夕は、常にホストからキャッシュのＳＳＤ内 へ受付けることが可能だからである。然しなから、読取キャッシュアヘッド作用 はバックグラウンド型の活動であり、ディスクとキャッシュとの間のプライベー トチャンネルを使用するのみであり、それは、ホストＩ１０活動に対しユニット の応答時間に関して非常に小さなネガティブの影響を有している。その影響を更 に制限するために、キャッシュアヘッドには、入力するホストＩ１０要求よりも 低い優先度が与えられる。

キャッシュアヘッド活動を制限する主要な要因は、殆どのホス１−Ｉｌｏに続く その動作の必要性が欠乏することである。図１６のフローチャートに示した如（ 、Ｉ１０局所性の特徴はキャッシュアヘッド活動を現在のＩｌｏを満足したトラ ックを超えて近い将来のホストＩ１０がデータをアクセスする蓋然性のある条件 へ制限する。Ｉ１０局所性アルゴリズムは現在のＩ１０ブロック寸法を使用し且 つ影響されるトラック内の位置を使用して現在のＩｌｏが位置されていた現在の トラックの「端部」がどれほど近いかを決定する。隣接するトラックに対する必 要性なしにこの同一のトラックから充分な数の同一の寸法のＩｌｏを満足させる ことが可能であることが決定される場合には、キャッシュアヘッドが実施される ことはない。

キャッシュアヘッドに対しては二つの候補者が存在する・に過ぎない。即ち、そ れらは、ホストＩ１０に関与するものの直後の単一のトラック及びホストＩ１０ のものの直前のトラックである。これらのトラックは、しばしば、前のキャッシ ュアヘッド活動によって既にキャッシュされているので、キャッシュアヘッド活 動は大概自己制限的プロセスである。

任意の与えられたホストＩ１０に対して−っのトラックのみがキャシュアヘッド 処理され、ホストＩ１０に続くトラックは主要な候補者である。それが既にキャ ッシュされていない場合であって、且つ近接ファクタがキャッシュアヘッドが発 生すべきであることを表わす場合には、順方向トラックがこの時にキャッシュさ れる。それに続くトラックが既にキャッシュされている場合には、ホストＩ１０ に先行するトラックが考慮され、それが既にキャッシュされていない場合であっ て、且つ近接ファクタがキャシュすることを所望する場合には、この先行するト ラックはこの時にキャッシュされる。勿論、これらの候補者トラックの両方が前 にキャッシュされている場合には、キャッシュアヘッドモジュールは何等キャッ シュ動作をする必要性がない。

このキャッシュアヘッドキャッシュバック特徴から非常に重要な利点が発生する 。関連するトラックがシーケンシャルモードでホストによってアクセスされる場 合には、そのシーケンスは与えられたディスクエリアにおいて最初にアクセスさ れたものから順方向または逆方向のいずれかである。キャッシュアヘッドアルゴ リズムの特性によって、非生産的なキャッシュアヘッドは、任意の与えられたト ラッククラスタにおける初期的トラックから誤った方向に存在する一つのトラッ クを関与するに過ぎない。このことは、近接アルゴリズムと結合されて、キャッ シュアヘッド動作を、アクセスの方向に対して自己適合性のものとさせる。

バ・・　゛ラウン゛スイープ ホストからの書込Ｉ１０がコントローラによってサービスされる場合には、ホス トからのデータはキャッシュ内に配置される。それは、バックグラウンドにおい てキャッシュからディスクへ書込まれ、■１０をサービスするのに必要とされる 時間に関してディスク動作の影響を最小とさせる。このビくツクグラウンド活動 を取扱うモジュールはバックグラウンドスイープモジュールである。スィーブ活 動を制限するため、且つスピンドルに対する競合を制限するために修正されたト ラックの部分のみがスィーブ期間中にＳＳＤからディスクへ書込まれる。更なる 効率を達成するためにバックグラウンドスィーブモジュールは、それが使用可能 状態となるやいなやキャッシュからディスクへ常にデータをコピーするものでは ない。そうではなく、ある最小数の修正したトラックが動作状態となる前にコピ ーされるべき待機するまでそれが休眠状態に留まる。キャッシュからディスクヘ コピーされる前に単一の修正されたトラックが非常に長い時間待機することを回 避するために、バックグラウンドスイープは、タイムアウトによっても活性化さ れる。従って、いずれかの修正されたトラックがある最小時間待機しており、か つそのスィーブが非活性状態でない場合にはそのスイープは活性化される。その スイープがキャッシュからディスクへトラックの全ての修正した部分をコピーし た後に、それは休眠状態へ復帰する。

スィーブタイムアラ 何らかのキャッシュされたデータトラックが修正され且つディスク上の対応する トラックがある最小時間が経過した後にアップデートされていない場合にタイム アウトが発生する。タイムアウトが発生すると、定義上、ディスクヘコピーされ ることを必要とする少なくとも一個のキャッシュされたトラックが存在する。こ の時に、バックグラウンドは活性状態へ変化される。タイムアウトモジュール（ 図１７）は、更に、最初のバックグラウンドイベントをセットアツプさせ（バッ クグラウンドイベント発生の説明参照）、且つディスクをアクセスするためにホ ストとの競合が存在しない場合には、そのイベントの実行が開始される。このイ ベントが開始された後に、一つが必要であると知られている場合には次のイベン トもセットアツプされ且つ後の実行のために保持される。これらの事柄が行われ ると、バックグラウンドスィーブはその動作を継続するか又は休眠状態へ復帰す るかの条件を待機する。

左乙二１■上 各ホストＩ１０動作の完了時にスィーブ開始モジュール（図１８）にエンターす る。三つのケースのうちの一つが存在する場合がある。第一のケースはスイープ が休眠状態であり、且つこの時にスイープをイネーブルさせるためにディスクヘ コピーされることを待機する充分な数の修正されたトラックが存在しない場合で ある。この場合には、最も一般的なものであり、この時に取られるべき作用は存 在しない。

第二のケースにおいては、スイープが活性状態であり、且つバックグラウンドイ ベントが動作状態である。この状態においては、この時に新たな作用が必要とさ れることはない。

最後のケースにおいては、スィーブが活性状態であるが、どのバックグラウンド イベントも現在動作状態にはない。これらの条件下において、バックグラウンド 、イベントが発生され（スイープイベント発生の説明を参照）且つ、適切である 場合には、この実行が開始される。

スイープイペン　の バックグラウンドスイープイベントの発生の必要性は、ディスクが関与するその 他の進行中の活動が存在しないということに基づいている。何らかのこのような 活動が進行中である場合に図１９のイベント発生モジュールにエンターすると、 同等イベントが発生されることはない。

時折、イベント発生モジュールは、ディスクヘコピーされるべく待機している修 正したトラックがもはや存在していないことを見出す。この場合には、バックグ ラウンドスイープは休眠状態へ復帰される。

その他の時間においては、バックグラウンドスイープは活性モードにあるが、一 時的に中断されてホストＩ１０をサービスするより高い優先度の活動を取扱う。

このような中断はバックグラウンドスィーブが再開始されることを必要とする。

それは、直接的にディスクヘッドにおいてではないがそれに最も近い修正された トラックを見出すことによって行い、そのトラックへのシークを開始し、次いで そのトラックに対する書込イベントをセットアツプする。この書込イベントは後 になるまで回避されることがないが、それが存在することは、可能である場合に はこの書込が次ぎに行うべきことであることをスイープ継続モジュール（継続モ ジュールの説明）へ知らせる。

このバックグラウンド書込を取扱う方法の効果は、ホスト動作に関しての影響を 最小とすることである。

コントローラは、バックグラウンドシークと対応する書込動作との間でのＩ１０ ミスをサービスする機会を有している。このいずれもがホストＩ１０キャツシュ ヒツトをサービスすることに何等顕著な影響を有するものではない。何故ならば 、ヒツトは常にすぐに処理されるからである。ディスクはヒツトに関与すること はない。

スイープは、トラック内の全てのセクタが修正されているか、又はそれらのセク タの幾つかのみが発生されているかに依存して、修正されたトラックの書込を異 なった態様で取扱う。更に、完全に修正されたトラックの数及び部分的に修正さ れたトラックの数は、両方とも、個々のトラックをディスクに書込むための優先 度の設定において考慮される。部分的に修正されたものの数と比較してより大き な数の完全に修正されたトラックが存在する場合には、完全に修正されたトラッ クにはスィーブ動作によって優先性が与えられる。

キャッシュからディスクへの修正したトラックの書込は、対応するＬＲＵ−ＭＯ Ｄ−ＬＯＷ及びＬＲＵ−ＭＯＤ−ＨＩ　ＧＨ値によって定義される如（、トラッ クの修正された部分のみを取扱うことに制限される。修正されたトラック又はト ラックセグメントがディスクへ書込まれると、チェーン化されていないステータ ス内に存在していたトラックのキ↑ツシュスロットが、そのトラックが部分的に 修正されたものであるに過ぎない場合には、ＭＲＵ位置においてＬＲＵチェーン 内に配置され、且つそのトラックが完全に修正されたものである場合にはＬＲＵ 位置に配置される。同時に、対応するＬＲＵ−ＭＯＤ−ＬＯＷ及びＬＲＵ−ＭＯ Ｄ−ＨＩ　ＧＨフィールドは、それらのナル値ヘセットされて、キャッシュされ たデータのどの部分も対応するディスクトラック内のものと異なるものではない ことを表わす。

各〕ニニノ」Ｅ總 図２０のフローチャートに図示した如く、各バックグラウンドスィーブイベント は、シークであるが又は書込であるかに拘らず、スィーブの爾後の作用に対して 待機するイベントを準備する。従って、シークの開始は常に爾後の関連した書込 イベントを準備し、書込の開始は、別のトラックがディスクへ書き込まれること を待機している場合には、爾後の無関係のシークイベントを準備する。

継続モジュールは、各スイープイベントを完了すると、エンターされる。ホスト がディスクを必要とするＩ１０コマンドを発生すると（換言すると、キャッシュ ミス）、バックグラウンドスィーブシーケンスが中断され且つ待機用イベントが 消去される。

この動作はホストのコマンドのサービスを迅速化させるために取られ、且つ待機 状態にあるスィーブイベントのタイプに拘らずに取られる。それはバックグラウ ンドシーク作用を浪費する結果となる場合がある。このことは許容可能なもので ある。中止された書込は時間が許す場合に後に取扱われる。勿論、シークである か書込であるかに拘らずスィーブコマンドが実際に開始されると、それはアボー ト即ち中断される場合がある。スイープ動作が中断された後にスイープ継続モジ ュールにエンターすると、それはイベント発生モジュール（イベント発生説明を 参照）を使用してスイープシーケンスを再開始させる。

最後に、継続モジュールが、今完了したスィーブ動作が書込であったことを判別 し、且つディスクヘコピーされるためにもはや修正されたトラックが待機状態に ない場合には、スィーブは休眠状態とされる。

パワー　ラン　′ 図２１のフローチャートに図示した如（、ファームウェア部分は、本ユニットが それへのラインパワー即ち商用電源が降下したこを検知する場合に喚起される。

本ユニット内のデータの幾つかは修正された状態でキャッシュ部分に存在し且つ ディスクへの転送を待機している場合があるので、修正された部分がディスクへ 書込まれるまではキャッシュメモリ上にはパワー即ち電力が維持されねばならな い。従って、ラインパワー即ち商用電源がなくなると、本ユニットをバッテリバ ックアップユニットヘスイッチさせる。バッテリバックアップユニットは、メモ リ装置がインテリジェントシャットダウンプロセスを介して動作する間パワーを 供給する。

パワーが降下する場合にホストがメモリ装置とのデータ転送のプロセス中である 場合には、シャットダウンコントローラは進行中の転送を完了することを可能と させる。次いで、それはホストとの更なるトランズアクションを開始することを 阻止する。

従って、シャットダウンコントローラはソリッドステートメモリからディスクへ データトラックの任意の修正した部分をコピーするためのバックグラウンドスィ ーブを開始せねばならず、従ってコントローラ及びメモリ回路へのパワーが完全 にシャットオフされた場合にそれが喪失されることはない。スィーブが完了した 後に（それは２．３秒かかるに過ぎない）、ソリッドステートメモリ内の全ての データはディスク上にも存在する。この点において、ディスクスピンドルはパワ ーダウンさせることが可能であり、バッテリ上の負荷を減少させる。殆どの停電 は短い期間のものである。従って、コントローラは継続しである時間の量制御回 路及びソリッドステートメモリヘバッテリパワーを供給する。この期間中に外部 パワーが回復されると、コントローラはスピンドルにパワーを与え且つ外部パワ ーへスイッチハックする。この場合には、ソリッドステートメモリ内に歴史的デ ータを再度確立させる必要性なしに動作を進行させることが可能である。いずれ の場合にも、最終的なシャットダウンの前に回転磁気ディスク上に全てが格納さ れているのでデータが危険な状態となることはない。

、・バ・・り　ラウン゛スイープ 最終的バックグラウンドスィーブ（図１２）は、ソリッドステートメモリがら磁 気ディスクへトラックの修正した部分をコピーする。通常このようなトラック又 はトラックの部分は数個に過ぎないものである。何故ならば、この状態に到達す ることの可能な数はシステムの動作によって意図的に制限されているからである 。最終的スイープはバックグラウンドスイープの通常動作のために開発された論 理を利用する。

スイープは、通常動作期間中のタイムアウトに対してのものとほぼ同一の態様で 開始される。トラックをコピーする必要がない場合には、スイープは休眠状態の ままとされ、且つ更なるスィーブ動作が必要とされることはない。いずれかのト ラックをコピーすることが必要である場合には、スィーブ開始体が最初のバック グラウンドシークをセットアツプすると共に開始し、更に関連した書込イベント をセットアツプする。この第一シークの完了値に、制御はバックグラウンド継続 モジュールへ移行し、該モジュールは交互に前に発生した待機用イベントを実行 し且つ次のイベントを発生し且つそれを待機ステータスとさせる。コピーすべき 修正したトラックが残存していない場合には、スィーブは完了される。

パラメータ　び日 本明細書は特定の量又は識別が与えられていない項目を参照している。これらは 同等絶対的な限界又は制限を課することがないように意図的に量を特定しないま まとしである。説明の便宜上且つ公知の実施可能な寸法及び識別を与えるために 、サンプル形態に対して満足のいくセットと共に、以下の範囲の値及び識別子を 提供する。

バックグラウンドスイープトリガ、修正トラック数範囲：ｌ乃至選択したディス ク上のトラック数サンプル形態−５ バックグラウンドスイープトリガ、時間範囲１１３９秒乃至無限 サンプル形態：５秒 マイクロプロセサ用のＥＰＲＯＭメモリ寸法範囲：非特定 サンプル形態：６４キロバイト ハードウェアマイクロプロセサコントローラ候補者：任意の適宜の使用可能なプ ロセササンプル形態：８０Ｃ１９６，２４Ｍ　Ｈｚパワーダウン、キャッシュホ ールド時間範囲二〇秒乃至バッテリバックアップユニットにより課される制限 サンプル形態：５分 回転磁気ディスク容量 寸法範囲：任意の使用可能なディスク容量サンプル形態：６７５メガバイトフオ ーマツト済ｓｃｓ　４コントローラ 候補者；任意の適宜の使用可能なコントローラ装置サンプル形態：ＮＣＲ５３Ｃ ９０Ａ セクタ寸法 寸法範囲：ホストシステム及び選択したディスクドライブに対して任意の適宜の もの サンプル形態：１８０バイト トラック当たりのセクタ数 範囲：選択したディスク及びホストシステムにとって適宜のもの サンプル形態＝２５６ ソリッドステートメモリ寸法 寸法範囲：ｌメガバイト乃至取付けたりディスク容量の１００％の容量 サンプル形態：３２メガバイト トラック寸法 寸法範囲：ｌセクタ乃至選択したディスクドライブにとって適切な任意の寸法 サンプル形態：２５６セクタ デイスク当たりのトラック数 範囲：選択したディスク上で使用可能な任意のものサンプル形態＝１４６５０ テープルフ　−マ・・ 表Ｆ−１ アドレス変換（ＡＤＴ）テーブルフォーマット−非インデツクス要素 ユニ二Ｌｋ」［旦　盈−一一皿 ＡＤＴ−ＣＮＬ　キャッシュしたディスクスピンドル上のトラック数、 ＡＤＴテーブル内のライン 数と等しい。

ＡＤＴ−ＨＥＡＤ−ＰＯＳキャッシュディスクの読取／書込ヘッドの位置 ＡＤＴ−５ＷＥＥＰ−現在のＤＩＳＫ　５ＥＲＶＥＲＤＩＲ（ディスクサーノ＜ −）スイー プの方向、 ｌ＝スィーブは低から高へ 進行 ０＝スイープは高から低へ 進行 ＡＤＴ−ＭＯＤ−ＣＯＵＮＴホストからの書込によって修正されており且つ現在 デ イスフサ−バーによるディ スフへの書込を待機してい るキャッシュ内のトラック の総数。

ＡＤＴ　−ＭＯＤ　−ＵＲＧＥＮＴ修正された条件にある場合には最適性能を維 持するた めに本装置をして優先度を シフトさせるキャラシュス ロットの数 ＡＤＴ　−ＲＥＡＤ　−ＨＩＴＳ最後のリセット以来遭遇したキャッシュ読取ヒ ツトの 数 ＡＤＴ　−ＲＥＡＤ　−ＭＩＳＳＥＳ最後のリセット以来遭遇した読取ミスの数 ＡＤＴ−ＷＲＩ　ＴＥ最後のリセット以来遭遇し−ＨＩ　Ｔ　Ｓ　た書込ヒツト の数 ＡＤＴ−ＷＲＩ　ＴＥ最後のリセット以来遭遇し−ＭＩＳＳＥＳ　た書込ミスの 数 表Ｆ−２ アドレス変換テーブルフォーマット−インデックス要素 立：Ｊ５Ｌ１月１太１　１上目１所 （ＩＮＤＥＸ）　（ＡＤＴ−ＣＮＬ）ＡＤＴテーブルインデックス、対応す るディスクトラツ ク数と等価。各デ ィスクトラック対 し−個のＡＤＴテー プルラインが存在 する。

ＡＤＴ−５ＬＯＴ　（ＬＲＵ−ＣＮＬ）：のＡＤＴインデックスに対応するデー タのディスクトラ ツクを有するキャ ッシュスロットの 数、又ディスクト ラックに関連した ＬＲＵテーブル内 のラインを指し示 ッンユ内にない場 合には、このフィー ルドはその事実を 表わすためにその ナル値ヘセットさ れる。

ＡＤＴ　−ＭＯＤＩＦＩＥＤ　１　この（キャッシュされた）トラック がホストからの書 込動作により修正 されているか否か、 込まれる必要があ るか否かを表わす フラッグ。

０＝このトラック（キ ャッシュされてい る場合）は修正さ れておらず且つデ ィスクへ書込まれ る必要はｉヱい。

ｌ＝このトラックは ディスクへ書込ま れる必要がある。

表Ｆ−３ 最も最近でなく使用された（ＬＲＵ）テーブルフ１−マット−非インデツクス要 素 １二１基皿上　１−訓 ＬＲＵ−ＣＮＬ　ＬＲＵテーブル内のライン数、キャッシュエリア内の スロット数と等しい。

ＬＲＵ−ＬＲＵ　ＬＲＵチェーンの最も最近でなく使用された即ち最も 古い端部へのポインタ。

ＬＲＵ−ＭＲＵ　ＬＲＵチェーンの最も最近でな（使用された即ち最も 古い端部へのポインタ 表Ｆ−４ 最も最近でなく使用したテーブルフォーマット−インデックス要素 Ｌニエ互Ｕｔ太１　１且且ｊ ＬＲＵ　−ＴＲＡＣＫ　（ＡＤＴ　−ＣＮＬ）このキャッシュスロット内に格納 さ れたデータに対す るディスクトラッ ク番号、又そのデ ィスクトラックに 関連したＡＤＴテー プル内のラインを １旨し示す。

ＬＲＵ−ＮＥＸＴ　（ＬＲＵ−ＣＮＬ）ＬＲＵチェーン内の次のリンクへのポ インタ ０＝これはチェーン 内の最後の（ＭＲＵ） リンクである。

ＬＲＵ　−ＴＲＡＣＫ　（ＡＤＴ　−ＣＮＬ）このキャッシュスロット内に格納 さ れたデータに対す るディスクトラッ ク番号、又、その ディスクトラック に関連したＡＤＴテー プル内のラインを 指し示す。

ＬＲＵ−ＣＡＣＨＥＤ　（ＴＲＡＣＫ　５ＩＺＥ）有効なデータを有−ＬＯＷ　 するキャッシュし たトラック内の最 も低いトラック関 連セクタ番号 ＬＲＵ−ＣＡＣＨＥＤ　（ＴＲＡＣＫ　５ＩＺＥ）有効なデータを有−ＨＩＧＨ するキャッシュし たトラック内の最 も高いトラック関 連セクタ番号 Ｌ　ＲＵ−Ｍ　ＯＤ　（ＴＲＡＣＫ　５ＩＺＥ）修正したデータを−ＬＯＷ　有 するキャッシュ したトラック内の 最も低いトラック 関連セクタ番号 Ｌ　ＲＵ　−Ｍ　ＯＤ　（ＴＲＡＣＫ　５ＩＺＥ）修正したデータを−ＨＩＧＨ 有するキャッシュ したトラック内の 最も高いトラック 関連セクタ番号 ＬＲＵ　−ＬＯＣＫＥＤ　１　例えばディスクから獲得したか、キャラ シュコントローラに よってディスクへ書 込まれる等のこの（キ ャッシュした）トラ ツクが現在何等かの 動作のターゲットで あるか否かを表わす ユした）はロックさ れておらず、それは 何等かの動作のため に使用可能である。

１＝この（キャッジ ュした）トラックは ロックされており、 それは、この時は、 別の対立する動作の ターゲットとなるこ とは不可能である。

ＬＲＵ−ＲＥＣＹＣＬＥ　１　リサイクルマーカー、０＝これはリサイク ル用の候補者では ない。

表Ｔ−１ ・ＡＤＴテーブル ＡＤＴテーブルはいずれのディスクトラックもキャッシュされていないことを表 わすために初期条件に設定される。尚、「＊」はナル値を表わしている。

ＡＤＴ　−ＣＮＬ　＝　１４６２８ ＡＤＴ　−ＨＥＡＤ　−ＰＯ５＝　０ ＡＤＴ　−５ＷＥＥＰ　−ＤＩＲ＝　ＩＡＤＴ−ＭＯＤ−ＣＯＵＮＴ　＝　Ｏ ＡＤＴ−ＭＯＤ−ＵＲＧＥＮＴ＝　１６ＡＤＴ−ＲＥＡＤ−ＨＩＴＳ　＝　０ ＡＤＴ　−ＲＥＡＤ　−ＭＩＳＳＥＳ　＝　０ＡＤＴ　−ＷＲＩＴＥ−ＨＩＴＳ 　＝　０ＡＤＴ　−ＷＲＩＴＥ　−ＭＩＳＳＥＳ＝　０ＤＩＳＫ　５ＳＤ ＴＲＡＣＫ　５ＬＯＴ　ＭＯＤＩＦＩＥＤ（ＡＤＴ　−ＣＮＬ） 表Ｔ−２ ・ＬＲＵテーブル ＬＲＵテーブルは、キャッシュ動作の開始期間中に最小の特別の処理でもって初 期的動作が進行することを可能とすべ（任意的にチェーン化される。

表はＭＲＵからＬＲＵの順番でリセットされている。

尚、「＊」はナル値を表わしている。

（スロット１は任意的にＬＲＵと指定）去」ユニ」Ｌ立 一つのＩ１０１００後のＡＤＴテーブル（トラック１６及び４７が関与する読取 ）注：「＊」はナル値を表わしている。

ＡＤＴ　−ＣＮＬ　＝　１４６２８ ＡＤＴ　−ＨＥＡＤ　−１）Ｏ５＝　４７ＡＤＴ　−５ＷＥＥＰ　−ＤＩＲ＝　 ＩＡＤＴ−ＭＯＤ−ＣＯＵＮＴ　＝　Ｏ ＡＤＴ−ＭＯＤ−ＵＲＧＥＮＴ＝　１６ＡＤＴ　−ＲＥＡＤ　−ＨＩＴＳ　＝　 ０ＡＤＴ　−ＲＥＡＤ　−ＭＩＳＳＥＳ　＝　ＩＡＤＴ　−ＷＲＩＴＥ　−ＨＩ ＴＳ　＝　０ＡＤＴ　−ＷＲＩＴＥ　−ＭＩＳＳＥＳ＝　０ＤＩＳＫ　５ＳＤ ＴＲＡＣＫ　５ＬＯＴ　口ＩＦＩＥＤ　ＣＯＭＭＥＮＴＳ４６　１　０　読取ミ スから゛（２トラツク）４７　２　０　読取ミスから（２トラ・ツク）４８　＊ 　０ （ＡＤＴ−ＣＮＬ）　” 表］ユニ二よ 一つのＩ１０１００後のＬＲＵテーブル（トラック４６が関与する読取） 表」ユニ」Ｌ且 １０００回のＩ１０１００後のＬＲＵテーブルｌ１０１０００はトラック５６が 関与する読取である。テーブルはＭＲＵからＬＲＵの順番にリストされている。

注＝「＊」はナル値を表わしている。

１６　２　２０　５７　１２７　２５６　＊　＊　ＯＯ２１２１６４６１５３２ ５６＊　＊　ＯＯ１２２２２５２１８＋　２５６　＊　＊　ＯＯ２２４１２６７ １２５６＊　＊　ＯＯ ４１５２２４１１２５６＊　＊　ＯＯ １５１０４４２２１２５６＊　＊　ＯＯｌｏ　６　１５　４３　１　２５６　＊ 　＊　ＯＯ８３１０’５８　１　２５６　＊　＊　ＯＯ３０６２１５１２５６＊ 　＊　ＯＯ （スロット３は現在ＬＲＵスロット） 以下のスロットは修正されているが、修正した部分をディスクへ書込むことによ って未だにクリーニングしておらず、従って、それらはチェーン化されていない 。

７＊＊４５１２ＪＥ追　ｌ　２　０　０ＩＩ　＊　＊　４４　１９１　２５６　 １９１　２５６　０　０１３　＊　＊　２１４　５５　２５６　５５　１２２　 ０　０表ユユニ３ｄ １０００回Ｉ１０動作の後のＬＲＵテーブルｌ１０１０００はトラック５６が関 与する読取であだ。

表はＭＲＵからＬＲＵの順番にリストしである。

注＝「＊」はナル値を表わしている。

（スロット３は未だにＬＲＵスロットである。）以下のスロットは修正されてい るが、修正した部分をディスクへ書込むことによって未だにクリーニングしてお らず、従って、それらはチェーン化されていない。５個のトラックを修正してい るので、バックグランドスイープはターンオンされる。

表」ユニ」Ｌ且 １００２番目のＩ１０１００後のＬＲＵテーブル（トラック２１４が関与する書 込） テーブルはＭＲＵからＬＲＵの順番にリストされである。

注：「＊」はナル値を表わしている。

（ス艷ソト３は未だにＬＲＵスロットである。）以下のスロットは修正されてい るが、修正部分をディスクへ書込むことにより未だにクリーニングしておらず、 従って、それらはチェーン化されていない。１個のトラックが修正されているに 過ぎないので、バックグランドスイープは不活性状態のままである。

１３　＊　＊　２１４　５５　２５６　５５　１２２　０　０表−一土 ｆＦｉ　のサンプルＴ。

ＬＲＵ及びＡＤＴテーブル例は、実際の動作するコンピュータシステムから取ら れたＩ１０サンプルに基づくものであり且つシステムの環境に投影されている。

各Ｉ１０に対して、以下の情報が使用可能である。

１　１１．７４２　６８　４６．４７　読取４６で開始し４７で終る１０００　 １４．１９０　６８　５６　読取は完全に５６中１００１　１５．５５０　６８ 　６１．６２　書込６１テ開始し６２で終了１００２　５４．５８２　６８　２ １４　書込は完全に２１４中以上、本発明の具体的実施の態様について詳細に説 明したが、本発明は、これら具体例にのみ限定されるべきものではな（、本発明 の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。

ＦＩＣ，ＵＲＥ　１ Ｆ工ＧＵＲＥ　２ Ｆ工ＧＵＲＥ　３ ＦＩＧＵＲＥ　１６ ＦＩＧＵＲＥ　１９ ｒ工ＧＵＲＥ　２０ Ｆ工ＧＵＲＥ　２２ フロントページの続き （８１）指定国　ＥＰ（ＡＴ、ＢＥ、ＣＨ，ＤＥ。

ＤＫ、ＥＳ、ＦＲ，ＧＢ、ＧＲ，ＩＴ、ＬＵ、ＭＣ，ＮＬ、ＳＥ）、ＡＵ、ＣＡ 、ＪＰ、ＫＲ

Claims (34)

【特許請求の範囲】
1. １．キャッシュメモリシステムにおいて、大量記憶装置、 キャッシュメモリ、 前記大量記憶装置及び前記キャッシュメモリヘパワーを供給するパワーサブシス テム、前記パワーサブシステムは通常の電源及び補助電源からパワーを受取るも のであり、 前記パワーサブシステムヘの前記通常の電源が中断されたことを検知する手段、 前記通常の電源が中断された場合に前記キャッシュメモリの通常の動作を終了さ せる手段、前記中断が検知された場合に前記キャッシュメモリから前記大量記憶 装置へのデータの書込手段、前記中断の後に前記キャッシュメモリから大量記憶 装置へ前記データを書込んだ後に前記パワーサブシステムから前記大量記憶装置 及び前記キャッシュメモリヘのパワーをシャットダウンする手段、を有すること を特徴とするキャッシュメモリシステム。
2. ２．大量記憶装置とキャッシュメモリとを具備するキャッシュメモリシステムの 動作方法において、前記大量記憶装置から選択したデータを前記キャッシュメモ リ内に格納し、 前記キャッシュメモリ内に格納される各データの使用の相対的最近性を表わす最 も最近でなく使用された（ＬＲＵ）テーブルを維持し、 前記キャッシュメモリ内に格納される各新たなデータに対し前記ＬＲＵテーブル の上部へエントリを付加し、 前記ＬＲＵエントリと関連した前記キャッシュメモリ内に格納されているデータ が使用された場合に前記ＬＲＵテーブル内の各エントリに対しフラッグをセット し、 前記ＬＲＵテーブルの底部に到達する各ＬＲＵテーブルエントリに対して、前記 フラッグがセットされているか否かを決定し、前記フラッグがセットされている 場合には、前記フラッグのセットを解除し且つ前記エントリを前記ＬＲＵテーブ ルの上部へ配置させ、且つ前記フラッグがセットされていない場合には、前記Ｌ ＲＵテーブルから前記エントリを除去し且つ前記ＬＲＵテーブルエントリと関連 する前記キャッシュメモリ内の前記データをデキャッシュする、 上記各ステップを有することを特徴とする方法。
3. ３．請求項２において、更に、前記ＬＲＵテーブルエントリが前記ＬＲＵテーブ ルへ付加される場合に選択したＬＲＵテーブルエントリに対し前記フラッグをセ ットするステップを有することを特徴とする方法。
4. ４．大量記憶装置とキャッシュメモリとを具備するキャッシュメモリシステムの 動作方法において、前記大量記憶装置内に格納されているデータヘのアクセスを シークし、 アクセスが要求されたデータを有する前記大量記憶装置の第一選択サブセクショ ンの第二側部とアクセスが要求されたデータの第一側部との間の第一距離を決定 し、 前記第一距離及び単一のＩ／Ｏ動作で転送することが予定されたデータ量に基づ いて使用可能なＩ／Ｏ動作の回数を決定し、 前記使用可能なＩ／Ｏ動作の回数が予め選択した臨界的回数未満であるか否かを 決定し、前記使用可能なＩ／Ｏ動作回数が前記予め選択した臨界的な回数未満で ある場合には、前記第一選択サブセクションの前記第一側部に隣接して位置した 前記大量記憶装置の第二選択サブセクション内のデータを前記キャッシュメモリ 内へコピーする、上記各ステップを有することを特徴とする方法。
5. ５．請求項４において、前記第一距離が、アクセスが要求されるデータの端部か ら前記大量記憶装置の隣接したサブセクションの開始部へ測定した順方向距離で あることを特徴とする方法。
6. ６．請求項４において、前記第一距離が、アクセスが要求されたデータの開始部 から前記大量記憶装置の隣接するサブセクションの端部へ測定した逆方向距離で あることを特徴とする方法。
7. ７．請求項４において、前記大量記憶装置の前記選択したサブセクションが論理 ブロックであることを特徴とする方法。
8. ８．請求項４において、更に、 前記使用可能なＩ／Ｏ動作の回数が前記予め選択した臨界的な回数を超えている 場合に、アクセスが要求されたデータを有する前記大量記憶装置の前記第一選択 サブセクションの第二側部とアクセスが要求されたデータの第一側部との間の第 二距離を決定し、前記第二距離と単一のＩ／Ｏ動作で転送することが予測される データ量とに基づいて使用可能なＩ／Ｏ動作の回数を決定し、前記使用可能なＩ ／Ｏの動作回数が予め選択した臨界的な回数未満であるか否かを決定し、且つ、 前記使用可能なＩ／Ｏ動作の回数が前記予め選択した臨界的な回数未満である場 合には、前記第一選択サブセクションの前記第二側部に隣接して位置した前記大 量記憶装置の第三選択サブセクション内の前記データを前記キャッシュメモリ内 へコピーする、 ことを特徴とする方法。
9. ９．キャッシュメモリシステムにおいて、各論理ブロックが複数個のセクタを有 している複数個の論理ブロックによって組織された大量記憶装置、 前記大量記憶装置と関連した選択したデータを一時的に格納するキャッシュメモ リ、 前記大量記憶装置のどの論理ブロック情報が前記キャッシュメモリ内に現在格納 されているデータに対応しているかを表わす情報を格納するための論理ブロック アドレスルックアップテーブル、前記論理ブロックアドレスルックアップテーブ ルは、前記大量記憶装置の各論理ブロックに対し一個のフラッグを有しており、 前記フラッグは前記論理ブロックに関連するデータが現在前記キャッシュメモリ 内に格納されているか否かを表わす、 ことを特徴とするキャッシュメモリシステム。
10. １０．請求項９において、前記論理ブロックアドレスルックアップテーブルは、 前記大量記憶装置の各論理ブロックと関連した独特のシーケンシャルな論理ブロ ック番号によってインデックスされていることを特徴とするキャッシュメモリシ ステム。
11. １１．請求項１０において、更に、前記大量記憶装置の論理ブロック番号を前記 論理ブロックアドレスルックアップテーブルの前記シーケンシャルな論理ブロッ ク番号へ変換するアドレス変換手段が設けられていることを特徴とするキャッシ ュメモリシステム。
12. １２．請求項１１において、前記アドレス変換手段が、論理ブロック番号に等し い商と前記シーケンシャルなセクタ番号に対応する前記大量記憶装置の前記論理 ブロック内のセクタ番号に等しい残りとを与えるために、シーケンシャルなセク タ番号を前記大量記憶装置の論理ブロック当たりのセクタ数で割算する手段を有 することを特徴とするキャッシュメモリシステム。
13. １３．大量記憶装置とメモリとを具備するキャッシュメモリシステムの動作方法 において、各論理ブロックが複数個のセクタを有する複数個の論理ブロックへ前 記大量記憶装置を組織化し、前記大量記憶装置の各論理ブロックと関連した一個 のエントリを有する論理ブロックアドレスルックアップテーブルを維持し、前記 各エントリは関連したシーケンシャルな論理ブロック番号を有すると共に、前記 大量記憶装置の関連した論理ブロックに対応するデータが現在前記キャッシュメ モリ内に格納されているか否かを表わすフラッグを有している、上記各ステップ を有することを特徴とする方法。
14. １４．請求項１３において、更に、 前記大量記憶装置の開始から選択した論理ブロック内の選択したセクタヘのセク タ数を計算することによって前記大量記憶装置内の前記選択した論理ブロック内 の前記選択したセクタの関数として前記論理ブロックアドレスルックアップテー ブル内の所望のシーケンシャルなセクタアドレスをアクセスし、前記計算を使用 して前記大量記憶装置の前記選択した論理ブロック内の前記選択したセクタと関 連する前記キャッシュメモリの前記シーケンシャルなセクタアドレスを派生させ る、 上記各ステップを有することを特徴とする方法。
15. １５．請求項１３において、更に、 商と残りとを派生させるために前記大量記憶装置内の論理ブロック当たりのセク タ数によって前記選択したシーケンシャルなセクタアドレスを割算することによ って前記論理ブロックアドレスルックアップテーブル内の選択したシーケンシャ ルセクタアドレスの関数として前記大量記憶装置内の選択した論理ブロック内の 所望のセクタヘアクセスし、前記商を使用して前記大量記憶装置の前記選択した 論理ブロックを派生し、 前記残りを使用して前記大量記憶装置の前記選択した論理ブロックの前記選択し たセクタを派生する、上記各ステップを有することを特徴とする方法。
16. １６．大量記憶装置とキャッシュメモリとを具備するキャッシュシステムの動作 方法において、前記大量記憶装置内の選択した位置に対応する位置において前記 キャッシュヘデータを書込み、前記大量記憶装置へ書込む前に前記キャッシュメ モリヘのデータの書込みの間の経過時間を決定し、前記経過時間が所定の時間を 超える場合には、前記キャッシュメモリから前記大量記憶装置ヘデータを書込む 、 上記各ステップを有することを特徴とする方法。
17. １７．大量記憶装置とキャッシュメモリとを具備するキャッシュシステムの動作 方法において、前記大量記憶装置内の選択した位置に対応する位置において前記 キャッシュメモリへデータを書込み、前記大量記憶装置へ書込む前に前記キャッ シュメモリへ書込んだデータの量を決定し、 前記データの量が所定の量を超える場合には、前記キャッシュメモリから前記大 量記憶装置ヘデータを書込む、 上記各ステップを有することを特徴とする方法。
18. １８．請求項１６において、前記大量記憶装置が複数個のトラックを有しており 、且つ前記キャッシュメモリから前記大量記憶装置ヘデータを書込むステップが 、前記大量記憶装置へ未だに書込まれていない前記キャッシュメモリからのデー タを書込むステップを有しており、前記データは前記大量記憶装置の現在選択し たトラックと相対的なその位置によって選択されることを特徴とする方法。
19. １９．請求項１８において、前記データは前記現在選択したトラックに関し前記 大量記憶装置の最も近いトラックに対応するデータとして選択されることを特徴 とする方法。
20. ２０．請求項１７において、前記大量記憶装置が複数個のトラックを有しており 、且つ前記キャッシュメモリから前記大量記憶装置ヘデータを書込むステップが 、前記大量記憶装置へい未だに書込まれていない前記キャッシュメモリからのデ ータを書込むステップを有しており、前記データは前記大量記憶装置の現在選択 されたトラックと相対的なその位置によって選択されることを特徴とする方法。
21. ２１．請求項２０において、前記データは前記現在選択されたトラックに関し前 記大量記憶装置の最も近いトラックに対応するデータとして選択されることを特 徴とする方法。
22. ２２．各々が複数個のブロックとして組織されており且つ各ブロックが複数個の セクタを有するキャッシュメモリと大量記憶装置とを具備するキャッシュメモリ の動作方法において、 前記大量記憶装置からの選択したデータを前記キャッシュメモリ内に格納し、 前記キャッシュメモリ内に格納されている各ブロックのデータを使用の相対的最 先性及び現在のデータを有する前記ブロック内のセクタを表わす最も最近でなく 使用した（ＬＲＵ）テーブルを維持し、前記キャッシュメモリ内に格納されたデ ータの各新たなブロックに対し前記ＬＲＵテーブルの上部にエントリを付加し、 前記ＬＲＵエントリに関連した前記キャッシュメモリ内に格納されたデータが使 用された場合に前記ＬＲＵテーブル内の各ブロックエントリに対しフラッグをセ ットし、 前記ＬＲＵテーブルの底部に到達する各ＬＲＵブロックエントリに対して、前記 フラッグがセットされているか否かを決定し、前記フラッグがセットされている 場合には、前記フラッグのセットを解除し且つ前記ＬＲＵテーブルの上部へ前記 エントリを配置させ、且つ前記フラッグがセットされていない場合には、前記Ｌ ＲＵテーブルから前記エントリを削除し、且つ前記ＬＲＵテーブルエントリと関 連する前記キャッシュメモリ内の前記ブロックのデータをデキャッシュする、 上記各ステップを有することを特徴とする方法。
23. ２３．請求項２２において、更に、前記キャッシュメモリ内に格納された各ブロ ックのデータのどのセクタが修正されたかを表わすデータを前記ＬＲＵテーブル 内に維持するステップを有することを特徴とする方法。
24. ２４．請求項２２において、前記キャッシュメモリ内に格納された各ブロックに 対して、与えられたブロックの全てのセクタがキャッシュされることは必要では ないが、キャッシュされたデータの間にセクタギャップを存在させることなしに キャッシュされたデータのセクタを隣接した状態に維持することを特徴とする方 法。
25. ２５．キャッシュメモリシステムにおいて、各論理ブロックが複数個のセクタを 有する複数個の論理ブロックによって組織された大量記憶装置、前記大量記憶装 置と関連する隣接した組の有効セクタの選択したデータを一時的に格納するキャ ッシュメモリ、前記隣接した組の有効セクタは隣接した組の修正したセクタを包 含する可能性があり、前記大量記憶装置での論理ブロックは前記キャッシュメモ リ内に現在格納されているデータに対応するかを表わす情報を格納する論理ブロ ックアドレスルックアップテーブル、 前記論理ブロックアドレスルックアップテーブルは、前記大量記憶装置の各論理 ブロックに対し一つのフラッグを有しており、前記フラッグは、前記論理ブロッ クに関連するデータが現在前記キャッシュメモリ内の格納されているか否かを表 わし、前記論理ブロックルックアップテーブルは、更に、前記論理ブロック内に どのセクタが有効セクタ及び修正されたセクタを有しているかを表わす各論理ブ ロックに関連したデータを格納している、 ことを特徴とするキャッシュメモリシステム。
26. ２６．請求項２５において、前記論理ブロックアドレスルックアップテーブルが 、前記大量記憶装置の各論理ブロックと関連した独特のシーケンシャルな論理ブ ロック番号によってインデックスされていることを特徴とするキャッシュメモリ システム。
27. ２７．請求項２６において、前記大量記憶装置の論理ブロック番号を前記論理ブ ロックアドレスルックアップテーブルの前記シーケンシャルな論理ブロック番号 へ変換するアドレス変換手段が設けられていることを特徴とするキャッシュメモ リシステム。
28. ２８．請求項２７において、前記アドレス変換手段が、前記論理ブロック番号に 等しい商と、前記シーケンシャルなセクタ番号に対応する前記大量記憶装置の前 記論理ブロック内のセクタ番号と等しい残りとを与えるために、前記アドレス変 換手段が、シーケンシャルなセクタ番号を前記大量記憶装置の論理ブロック当た りのセクタ数によって割算する手段を有していることを特徴とするキャッシュメ モリシステム。
29. ２９．請求項２２において、そのトラックが修正したデータを有している場合に は、前記ＬＲＵテーブルの脱チェーン化メンバーとしてＬＲＵトラックエントリ に対してフラッグが立てられることを特徴とするキャッシュメモリシステム。
30. ３０．請求項２９において、その修正したデータが前記大量記憶装置へ書込まれ た後にトラックエントリを前記ＬＲＵテーブルのチェーン化したメンバーとさせ ることを特徴とするキャッシュメモリシステム。
31. ３１．請求項３０において、前記トラックエントリが、前記大量記憶装置へ書込 む前に前記トラックの全てのセクタが修正された場合には、前記ＬＲＵテーブル の底部においてチェーン化したメンバーとされることを特徴とするキャッシュメ モリシステム。
32. ３２．請求項３０において、前記トラックエントリが、前記大量記憶装置へ書込 む前に前記トラックの全てより少ないセクタが修正された場合には、前記ＬＲＵ テーブルの上部においてチェーン化したメンバとされることを特徴とするキャッ シュメモリシステム。
33. ３３．大量記憶装置とキャッシュメモリとを具備するキャッシュメモリシステム の動作方法において、 前記大量記憶装置から選択したデータを前記キャッシュメモリ内に格納し、 前記キャッシュメモリから所望のデータを得ることが可能である場合には前記キ ャッシュメモリからデータを読取り、 アクセスされるべき所望のデータに基づいて前記キャッシュメモリ内に格納され ているデータを周期的にアップデートし、 選択した寸法のデータがアクセスされることを所望する場合には前記大量記憶装 置を直接的にアクセスする、 上記各ステップを有することを特徴とする方法。
34. ３４．請求項３３において、前記選択した寸法が、前記キャッシュメモリ内に格 納されている修正されていないデータの量の関数であることを特徴とする方法。