JPH0241054B2 - - Google Patents

Description

【発明の詳細な説明】

本発明の背景 本発明はデータ処理装置に関し、更に具体的に
はホスト・プロセツサ及び記憶階層における複数
のアタツチメント装置を含むデータ処理装置に関
する。 データ処理システムにおいて、通常、情報の記
憶及び検索のため、１つ又はそれ以上のアタツチ
メント装置（例えば、記憶デイスク）が設けられ
る。例えば、Bouknechtその他の米国特許第
4038642号では、複数のＩ／Ｏ装置及び関連した
Ｉ／ＯコントローラがＩ／Ｏインターフエイス・
バスを介してホスト・プロセツサへ共通に接続さ
れている。Ｉ／Ｏアタツチメント装置の各々はマ
イクロプロセツサを含み、このマイクロプロセツ
サはホスト・プロセツサと協働してメイン・スト
レージとＩ／Ｏ装置との間でデータ転送を実行す
る。Bouknechtその他のシステムに対する改善
は、Brownその他の米国特許第4246637号に記載
されている。この特許によれば、マイクロプロセ
ツサを含む単一のＩ／Ｏコントローラがホスト・
プロセツサへ接続され、複数のデータ記憶アタツ
チメント装置がＩ／Ｏコントローラの出力へ接続
され、単一のマイクロプロセツサが、複数のアタ
ツチメント装置との間のデータ転送を調整するこ
とができるようになつている。 これらシステムの問題点は、ホスト・プロセツ
サがアタツチメント装置からデータを要求する度
に、アタツチメント装置へアクセスしなければな
らず、時間がかかることである。例えば、
Brownその他の特許によれば、データが直接プ
ログラム制御（DPC）の下でアタツチメント・
デイスクからホスト・プロセツサへ転送される時
に、指令及びデータ・ワードはホスト・プロセツ
サのメイン・ストレージからマイクロプロセツサ
へ転送され、そこから装置データ・レジスタへ転
送される。アタツチメント・デイスクからリクエ
ストされたデータを検索し、そのデータをホス
ト・プロセツサへ与えるため、適当な調整及び制
御論理が実行される。反対方向の動作の場合（即
ち、メイン・ストレージからデイスクへの書込み
の場合）、アタツチメント記憶装置へ書込まれる
データは、装置データ・レジスタへロードされ、
このデータを所望のアタツチメント・デイスクへ
転送するため、初期接続ルーチンが実行されねば
ならない。サイクル・スチール・モードの動作で
は、指令がマイクロプロセツサへ与えられ、この
指令はマイクロプロセツサを能動化して、ホス
ト・プロセツサのメイン・ストレージからデータ
を「盗ませ」、そのデータを装置データ・レジス
タへロードせしめる。次いで、データは、実質的
にDPCモードと同じようにして、適当なアタツ
チメント・デイスクへ転送される。 システムのスピードは改善されるけれども、ホ
スト・プロセツサのために必要な情報を得るた
め、アタツチメント・デイスクへアクセスするこ
とは依然として必要である。信号処理速度は早い
けれども、読出／書込ヘツド又は記憶媒体を物理
的に動かす必要があるため制限される。即ち、デ
イスク・サブシステム中の処理速度は、デイスク
が回転し、ヘツドが適当な位置をシークするのに
必要な時間によつて制約される。 動作速度を改善するため、中央処理ユニツトに
よつて使用される可能性の高いメイン・ストレー
ジのデータの一部を小容量高速メモリへ記憶し、
CPUのデータ・リクエストの多くを上記高速メ
モリによつて迅速に満足させるようにすることが
知られている。このような手法は、例えば
Ghanemによる米国特許第4035778号に開示され
ている。Ghanemの特許は、小容量高速作業メモ
リの使用を説明すると共に、近い将来に使用され
る可能性の最も高いデータを保存するため、メモ
リ内容を常に更新することによつて、メモリ効率
を最大にする必要性を述べている。メモリ内容の
更新は、使用時点の最も古いデータ（least
recently used data）が常に置換されるLRU法、
又は複数のユーザへメモリ容量を割当てるため、
複雑な統計的アルゴリズムを使用するGhanemの
方法によつてなされる。しかし、Ghanemの特許
は、競合するプログラム間で作業メモリ・スペー
スを割当てることを教えるが、複数のデイスク
Ｉ／Ｏコントローラへ同一の手法を適用する示唆
はなされていない。更に、リクエストされたデー
タが現在高速作業メモリ中に記憶されているかど
うかを決定するため、データ・リクエスト識別情
報と作業メモリの全体の内容を比較することが必
要である。これは時間のかかる仕事である。更
に、作業メモリへ転送されるデータは、CPUに
よつてリクエストされたデータであるが、未だリ
クエストされていないけれども近い将来リクエス
トされる可能性のある他のデータを転送すること
によつて効率が改善されよう。 本発明の要約 本発明の目的は、パフオーマンスが改善された
キヤツシユ・メモリを提供することである。 簡単に説明すれば、上記の目的は、ホスト・プ
ロセツサによつて既にリクエストされたデータと
は異つた或る追加のデータをキヤツシユ・メモリ
へ転送することによつて達成される。データは、
アタツチメント記憶装置からキヤツシユ・メモリ
へ、固定長データ・ブロツクの増分として転送さ
れる。各データ・ブロツクは一連のデータ・レコ
ードを含む。特定のデータ・レコードがホスト・
プロセツサによつてリクエストされた時、そのレ
コードを含むデータ・ブロツクがキヤツシユ・メ
モリへ転送される。リクエストされたデータ・レ
コードのブロツク内ポジシヨンが決定され、ブロ
ツクにおけるリクエストされたレコードの相対的
位置に従つて、１つ又は２つの追加のデータ・ブ
ロツクがキヤツシユ・メモリへ転送される。追加
のデータ・ブロツクが転送される論理限界
（threshold）は変更することができ、それによつ
て、各動作でキヤツシユ・メモリへ転送されるデ
ータの平均的実効ブロツク長を変更することがで
きる。平均的実効ブロツク長は、パフオーマンス
を最も改善できるように変更することができる。
本発明の実施例において、パフオーマンス改善の
基準は、読出ヒツト率である。 実施例の説明 第１図はホスト・プロセツサ１０、メイン・ス
トレージ１１、装置コントロール１４、鍵盤表示
端末１８、Ｉ／Ｏコントローラ２０を含む本発明
に従つたデータ処理システムを示す。装置コント
ローラ１４は、少なくとも１つのアタツチメント
装置（例えばデイスク１６）に接続されている。
コントローラ２０は、ホスト・プロセツサ１０と
デイスク１６との間で適当な装置コントロール１
４を介して実行されるデータ転送を制御する。 ホスト・プロセツサ１０はチヤネル・インター
フエイス・バス２１を介してコントローラ２０と
通信し、コントローラ２０は装置インターフエイ
ス・バス２２を介して装置コントロール１４と通
信する。 ホスト・プロセツサ１０はIBM社から市販さ
れているシリーズ／１、モデル５ミニコンピユー
タであると仮定する。このコンピユータについて
は、IBM社の出版物「シリーズ／１、モデル５、
4955プロセツサ及びプロセツサ機構の説明」
（Series／１、Model5、4955 Processor and
Processor Features Description、GA34―0021
―３）及び前記の米国特許第4038642号に説明さ
れている。更に、コントローラ２０はBrownそ
の他による米国特許第4246637号に開示されたコ
ントローラを改良したものであり、マイクロプロ
セツサは米国特許第4173782号に説明されている
ものであつてよい。 第１図に示されるように、コントローラ２０に
あるチヤネル・インターフエイス・バス２１はチ
ヤネル・データ・バス２３及びチヤネル制御バス
２４を含む。同様に、装置インターフエイス・バ
ス２２は装置データ・バス２５と装置制御バス２
６を含む。自動高速サイクル・スチール動作を実
行するため、データ・バス２３及び２５は、サイ
クル・スチール・データ・レジスタ３０、バイパ
ス・データ・バス３１、装置データ・レジスタ３
２によつて相互接続される。バス２３，２５，３
１の各々は、２つの方向へデータを転送する双方
向バス又は一対の単方向バスであつてよい。 非自動サイクル・スチール動作のためには、デ
ータ及びその他の情報は、チヤネル・データ・バ
ス２３、サイクル・スチール・データ・レジスタ
３０、マイクロプロセツサ・データ・バス（デー
タ・バス・イン・バス３４及びデータ・バス・ア
ウト・バス３５を含む）を介して、ホスト・プロ
セツサとマイクロプロセツサ３３との間で転送さ
れる。同様に、データ及びその他の情報は、装置
データ・バス２５、装置データ・レジスタ３２、
バス３４及び３５を介して、マイクロプロセツサ
３３と装置コントロール１４との間で、いずれの
方向へ対しても転送されることができる。 チヤネル制御バス２４及び装置制御バス２６の
各々は、高速コントロール３６の制御の下で、初
期接続（調整及び制御）論理３７及び３８を介し
て、マイクロプロセツサ３３と通信する。マイク
ロプロセツサ３３は、バス３４及び３５を介して
高速コントロール３６と通信する。ホスト・プロ
セツサ１０から与えられたサイクル・スチール開
始指令に応答して、マイクロプロセツサ３３は、
各種の初期パラメータ値を高速コントロール３６
へ与える。その後、高速コントロール３６は、マ
イクロプロセツサ３３から介入を受けることな
く、データ転送動作を自動的に制御することがで
きる。換言すれば、自動サイクル・スチール動作
の場合、マイクロプロセツサ３３は高速コントロ
ールの初期値を設定し、その後、高速コントロー
ルは、実際のデータ転送動作を引継いでそれを実
行する。この動作は、線３９及び４０を介して、
レジスタ・ロード・パルスをサイクル・スチー
ル・データ・レジスタ３０及び装置データ・レジ
スタ３２へ与えることを含む。線３９上のロー
ド・パルスは、データをレジスタ３２からレジス
タ３０へバイパス・データ・バス３１を介して転
送し、線４０上のロード・パルスはデータを反対
方向に転送する。高速コントロール３６によつて
与えられる自動的制御は、ホスト・プロセツサ１
０とレジスタ３０との間でデータを転送するた
め、初期接続論理３７を介してチヤネル制御バス
２４上で適当な初期接続シーケンスを実行するこ
とを含み、かつレジスタ３２と装置コントロール
１４との間でデータを転送するため、初期接続論
理３８を介して装置制御バス２６上で適当な初期
接続シーケンスを実行することを含む。 コントローラ２０はキヤツシユ・メモリ４２と
キヤツシユ・データ・レジスタ４４を含む。他の
データ・レジスタと同じように、レジスタ４４は
バス３４及び３５を介してマイクロプロセツサ３
３へ接続され、線４５を介して高速コントロール
３６からロード・パルスを受取る。更に、レジス
タ４４はバス３１を介してレジスタ３０及び３２
へ接続される。データがホスト・プロセツサ１０
によつてリクエストされた時、マイクロプロセツ
サ３３は、先ずリクエストされたデータが現在キ
ヤツシユ・メモリ４２に存在するかどうかを決定
する。もし存在すれば（即ち、読出ヒツトの場
合）、リクエストされたデータはバス４６、レジ
スタ４４、バス３１、レジスタ３０及びバス２３
を介してホスト・プロセツサ１０へ転送される。
もしリクエストされたデータの全て又は或るもの
がキヤツシユ・メモリ４２に含まれない場合（読
出ミスの場合）、データは、通常の態様でアタツ
チメント装置から得られ、かつバス３１、レジス
タ４４、バス４６を介してキヤツシユ・メモリ４
２へ転送される。後に詳細に説明するように、ホ
スト・プロセツサ１０によつてリクエストされた
データ以外の追加のデータをプリフエツチし、そ
れが間もなくホスト・プロセツサによつてリクエ
ストされるだろうという予想の下で、そのデータ
をキヤツシユ・メモリに記憶することが望まれ
る。リクエストされたデータは、バス４６、レジ
スタ４４、バス３１、レジスタ３０、バス２３を
介してキヤツシユ・メモリ４２からホスト・プロ
セツサ１０へ転送される。 ホスト・プロセツサ１０が特定のデータ・ブロ
ツクについて動作を終了した後、新しいデータを
元のアタツチメント装置の記憶ロケーシヨンへ書
込むことを望むかも知れない。その場合、マイク
ロプロセツサ３３は、アタツチメント装置のロケ
ーシヨンの内容が現在キヤツシユ・メモリ４２に
記憶されているかどうかを決定する。もし記憶さ
れていれば、書込ヒツトの状態が起る。その場
合、このデータはキヤツシユ・メモリ４２で更新
されねばならない。何故ならば、それは今や変更
されているからである。アドレスされたアタツチ
メント装置のロケーシヨンの内容が現在キヤツシ
ユ・メモリ４２の中にない場合、データ・ブロツ
クの全体が書込まれるのであれば、新しいデータ
がキヤツシユ中に書込まれ、続いてキヤツシユか
らデイスク１６へ書込まれ、そうでなければ、デ
ータは直接にデイスク１６へ書込まれる。 キヤツシユ・メモリ管理の望ましい手法をこれ
から説明する。デイスク、キヤツシユ、及びデイ
レクトリイのスペースを有効に使用する重要な要
件は、固定ブロツク動作を実行することである。
そのような設計思想において、全てのデイスク・
アドレスは、開始デイスク・アドレス及び終了デ
イスク・アドレスの固定境界内に入るものと考え
られる。デイスク上に記憶された各レコードは、
デイスク駆動装置番号、ヘツド番号、シリンダ番
号、及びレコード／セクタ位置によつて決定され
た独特の相対ブロツク・アドレス（RBA）を有
する。RBAは高レベル・ブロツキング構造内に
置かれている。かくて、本発明のシステムにおい
て、各レコードは次式によつて与えられる独特に
関連づけられたRBAを有する。 RBA＝k₁（シリンダ番号）＋k₂（ヘツド番号） ＋レコード番号＋k₃（駆動装置番号） ここでk₁、k₂、k₃はデイスク駆動装置の設計仕
様から決定される定数である。後に詳細に説明す
るキヤツシユ・メモリ管理のためには、ブロツキ
ング構造は、RBAをレコードで表わされた固定
ブロツク長で除算することによつて達成される。 ブロツク・ナンバー＝RBA／ブロツク長 ここでブロツク長はシステム設計のパラメータ
である。以下の説明で、データの１つのレコード
は256バイトを含み、１ブロツクは８レコードを
含み、１ページは１ブロツク（2.048バイト）を
含み、全体のキヤツシユ容量は192ページである
と仮定する。しかし、他のメモリ構成も可能であ
る。 ８のブロツク長を使用すれば、後に示すテーブ
ルは、最初の26個のRBAが最初の４個のブロツ
クに関してどのように位置しているかを示す。 この管理手法を用いれば、各情報レコードのア
ドレスは、指定されたブロツクに関してブロツ
ク・ナンバー及びレコード・アドレスによつて指
定されてよい。１つのブロツクには８個のレコー
ドが存在するので、レコードのブロツク・ナンバ
ーは、RBAを８で除算することによつて決定さ
れる。ハツシングは、基本番号であるハツシン
グ・フアクタによつてブロツク・ナンバーを除算
し、その剰余をデイレクトリイ・テーブルへのエ
ントリイ・ポイント（ハツシユ・エントリイ・ナ
ンバー）として使用することにより達成される。
実施例では、ハツシング・フアクタは311である。
所望ならば、他のハツシング・フアクタも使用で
きる。フアイル・サブシステム・ブロツク・アド
レスは、剰余がどのようなものであつても、ブロ
ツク・ナンバー及びハツシング・フアクタの商と
して定義される。 キヤツシユ・メモリ内容のデイレクトリイ・テ
ーブルは、第１図のランダム・アクセス・メモリ
（RAM）４７に維持される。デイレクトリイ・
テーブルのフオーマツトは、第２ａ図に示される
とおりである。 デイレクトリイ・テーブルの使用は、データ・
ブロツクをキヤツシユに配置するに当つて、オー
バヘツドを最少にするためのキー概念である。デ
イレクトリイ・テーブルはキヤツシユへの高レベ
ル・インデツクスを表わし、現在キヤツシユに何
があるか、及びそれがどこにあるかが上記インデ
ツクス中にリストされる。デイレクトリイ・テー
ブルは全時点でキヤツシユの内容を追跡し、キヤ
ツシユ内容をデイスク上のデータ・ブロツクと関
連づける。それは自由／使用インデイケータ（１
ビツト）、ホーム・インデイケータ（１ビツト）、
フアイル・サブシステム・ブロツク・アドレス
（11ビツト）、後方ポインタ（９ビツト）、前方ポ
インタ（９ビツト）、キヤツシユ・アドレス（８
ビツト）を含む。これらビツトの数は、特定のシ
ステム要件に従つて変更されてよい。 自由／使用インデイケータは、キヤツシユ中の
特定のデータ・ブロツクを指定するため、エント
リイが現在使用されているかどうかを示す。ホー
ム・インデイケータは、後に詳細に説明するよう
に、エントリイがホーム・エントリイであるかど
うかを示す。フアイル・サブシステム・ブロツ
ク・アドレス及びハツシユ・エントリイ・ナンバ
ーは、デイスク上のデータ・ブロツクを独特にア
ドレスする。キヤツシユ・アドレスは、フアイ
ル・サブシステム・ブロツク・アドレス及びハツ
シユ・エントリイ・ナンバーによつて指定された
データ・ブロツクがキヤツシユのどこに存在する
かを示す。前方がポインタ及び後方ポインタは、
エントリイを連鎖としてリンクするために使用さ
れる。 アドレスされてよいデータ・ブロツクは、単一
のハツシユ・エントリイ・ナンバーを発生する。
しかし、一般的には、複数のデータ・ブロツクが
同一のハツシユ・エントリイ・ナンバーを発生す
る。これら複数のデータ・ブロツクは、所謂「衝
突エントリイ」を発生する。衝突エントリイは、
所与のハツシユ・エントリイ・ナンバーを与える
オリジナルなデータ・ブロツクの「ホーム・エン
トリイ」に対応する。複数の衝突エントリイの間
で、特定のデータ・ブロツクを求める探索が実行
されねばならない。それは、そのデータ・ブロツ
クがキヤツシユ中にあるかどうかを決定するため
である。かくて、衝突リストの平均的長さを許容
できる範囲に維持するように、ハツシング・フア
クタを選択しなければならない。 ユーザがデイスク又はその他の記憶ユニツトか
ら読出されるデータ、又はそこへ書込まれるデー
タをリクエストしたものと仮定すると、マイクロ
プロセツサ３３はハツシユ・エントリイ・ナンバ
ーを計算し、リクエストされたデータがキヤツシ
ユ・メモリ４２にあるかどうかを調べるため、デ
イレクトリイ・テーブルを検査する。第３図を参
照すると、ハツシユ・エントリイ・ナンバーは探
索の開始点として使用されている。読出動作につ
いては、ハツシユ・エントリイ・ナンバーによつ
て指定されたデイレクトリイ位置において、自
由／使用インデイケータが検査され、エントリイ
が使用されたかどうかを最初に決定する。もし使
用されていなければ、リクエストされたデータは
キヤツシユに存在せず、「読出ミス」を示すため
ヒツト・フラグがリセツトされ、「自由ホーム」
が表示される。次に、リクエストされたデータは
適当なデイスクから検索され、キヤツシユ・メモ
リ中に記憶され、デイレクトリイ・テーブルのこ
のロケーシヨンでインデツクスされることができ
る。 もしエントリイが使用されていれば、ホーム・
インデイケータが検査され、エントリイ・ポイン
トがホーム・エントリイであるか衝突エントリイ
であるかが決定される。定義によれば、キヤツシ
ユ中の全てのブロツクは、衝突エントリイではな
くホーム・エントリイで、エントリイ・ポイント
を発生しなければならない。かくて、もしエント
リイ・ポイントが衝突エントリイであれば、リク
エストされたブロツクはキヤツシユにないことが
直ちに決定される。第４ａ図は、リクエストされ
たデータがキヤツシユにない場合を示す。もしリ
クエストされたブロツクがハツシユ・エントリ
イ・ポイント１（これは衝突エントリイＣであ
る）を発生すれば、リクエストされたブロツクが
キヤツシユ中に存在しないことが直ちに決定され
得る。かくて、第４ａ図のエントリイ・ポイント
１については、リクエストされたブロツクはキヤ
ツシユに存在せず、読出ミスを表示するためヒツ
ト・フラグがリセツトされ、第３図に示されるよ
うに「使用ホーム」が表示される。 しかし、キヤツシユにないデータ・ブロツク
が、第４ａ図のハツシユ・エントリイ・ポイント
２のようなホーム・エントリイＨでエントリイ・
ポイントを発生する可能性がある。この場合、ブ
ロツクがキヤツシユにあるかどうかを決定するた
め、エントリイのリンクされた連鎖を探索する必
要があある。 第３図に示されるように、先ずフアイル・サブ
システム・ブロツク・アドレス（商）がリクエス
トされたブロツクの相対的アドレスと比較され、
デイレクトリイ・テーブルのエントリイがリクエ
ストされたブロツクに対応するかどうかが決定さ
れる。それはリクエストされたブロツクではない
から、更に検査がなされ、現在のエントリイが連
鎖の終り（EOC）かどうかが決定される。連鎖
の終りではないから、ポイント２における前方ポ
インタが、エントリイの次のポイントとして使用
され、プロセスは、連鎖の終りが最後のエントリ
イの前方ポインタによつて表示されるまで繰返し
て実行される。その時点で、読出ミスを表示する
ためヒツト・フラグがリセツトされ、連鎖の終り
が表示され、ハツシユ・エントリイ・ナンバーが
連鎖の終りを示す。 もしこの反復的探索の間の任意の時点で、リク
エストされたデータ・ブロツクの位置が決定され
ると、ブロツクのキヤツシユ・アドレスが保存さ
れ、読出ヒツトを表示するため、ヒツト・フラグ
がセツトされる。第４ｂ図は、＊で示されたデイ
レクトリイ・テーブルのエントリイ地点で、リク
エストされたブロツクが存在する場合を示す。後
に第８図、第１１図、第１２図を参照して説明す
るように、リクエストされたブロツクがキヤツシ
ユに置かれている時、常にオリジナルのハツシ
ユ・エントリイ・ナンバーはホーム・エントリイ
Ｈを指定する。ハツシユ・エントリイ・ナンバー
はリクエストされたブロツクに対応するデイレク
トリイ・テーブル中のエントリイを直接に指定す
る必要はない。第４ｂ図に示されるように、リク
エストされたブロツクは、前方ポインタをたどる
ことによつて、第２の衝突エントリイＣで発見さ
れるかも知れない。 更に、RAM４７には、第２ｂ図に示されるフ
オーマツトを有するLRUテーブルが記憶されて
いる。LRUテーブルは、キヤツシユ・メモリ中
の各ページについて設けられる。LRUテーブル
にある前方ポインタは、より近時に使用されたペ
ージを指定し、最も近時に使用されたリストの前
方ポインタは最初の自由ページを指定する。同様
に、各LRUリストの後方ポインタは、使用時点
の古いページを指定する。従つて連鎖の最後のペ
ージは、最も近時性の少ない（最も使用時点が古
い）ページである。各LRUリストにあるデイレ
クトリイ・ポインタは、デイレクトリイ・テーブ
ルの311個のエントリイの特定の１個を指定する。
LRUテーブル中の最も使用時点の古い（LRU）
エントリイ、最も使用時点の新しい（MRU）エ
ントリイ、デイレクトリイ・テーブル中の最初の
自由ページを指定するため、ポインタ５０，５
１，５２を設けることが望ましい。更に、自由ペ
ージ・カウンタ５４を設けることが望ましい。本
発明に従う装置では、新しいページをキヤツシ
ユ・メモリに書込む必要がある際に利用可能なペ
ージがない時、後に詳細に説明するように、最も
使用時点の古いページがキヤツシユ・メモリから
削除される。新しく書かれたページは、LRUテ
ーブルで最も近時に使用されたリストとなり、そ
の後方ポインタは、以前の最も近時に使用された
リストを指定し、そのデイレクトリイ・ポインタ
はデイレクトリイ・テーブル中の対応するハツシ
ユ・エントリイ・ナンバーを指定する。書込動作
の場合、「通過書込（ライトスルー）」手法が実行
される。即ちデータがキヤツシユにない時、デー
タが完全なデータ・ブロツクであれば、それはキ
ヤツシユ・メモリへ書込まれ、次いでデイスクへ
書込まれる。データが既にキヤツシユにあれば、
それは単にキヤツシユ・メモリからデイスクへ転
送され、適当なページが最も近時に使用された状
態へ更新される。しかし、書込まれるデータ・レ
コードが所定の数を超過していれば、それは直接
システムからデイスクへ転送され、キヤツシユ・
メモリ中の対応するページが削除される。もしデ
ータ・レコードがキヤツシユに現存せず、完全な
データ・ブロツクよりも少なければ、データは直
接システムからデイスクへ転送される。 基本的なデイレクトリイ管理手法を説明したの
で、これから、実施例におけるＩ／Ｏコントロー
ラの動作を説明する。 第５図はＩ／Ｏコントローラの動作を示す簡単
な流れ図である。第５図に示されるように、マイ
クロプロセツサは指令を検査し、もしその指令が
デイスクとの間のデータ転送を必要としなけれ
ば、リクエストされた動作が実行され、割込リク
エストをセツトすることによつて動作が完了され
る。デイスクのデータ転送動作がリクエストされ
たものと仮定すれば、マイクロプロセツサは、キ
ヤツシユ・メモリがシステム中に設けられている
かどうかを決定する。もし設けられていなけれ
ば、システムは、前記の米国特許第4256637号及
び第4038642号に説明されている態様と実質的に
同じように動作する。 もしデイスクのデータ転送動作がリクエストさ
れており、かつキヤツシユ・メモリが設置されて
いれば、マイクロプロセツサは、キヤツシユ・メ
モリ動作がリクエストされたかどうかを決定す
る。もしリクエストされていれば、Ｉ／Ｏコント
ローラ２０は、後に詳細に説明するキヤツシユ・
アルゴリズムを実行する。キヤツシユ・アルゴリ
ズムは、キヤツシユ・メモリ内のデータ管理に関
連している。 キヤツシユ・アルゴリズムを実行した後で、も
し書込動作がリクエストされ、かつ「通過書込
み」が実行されるべきであれば、マイクロプロセ
ツサは、キヤツシユ・アルゴリズムの中で設定さ
れたデータ転送動作の全てを実行し、かつデイス
クへアクセスしてキヤツシユからデイスクへの転
送を実行するため、フアイル動作を発生させねば
ならない。もし「通過書込み」が実行されない
で、データが直接にデイスクへ書込まれるべきで
あれば、要求されたデータ転送動作はキヤツシ
ユ・アルゴリズムの中で設定されておらず、マイ
クロプロセツサは、ホスト・プロセツサから指定
されたデイスクへデータを書込むため、必要な動
作を設定すると共にそれを実行する。 もし書込動作ではなく、読出動作がリクエスト
されていれば、マイクロプロセツサは、バイパ
ス・フアクタを超過したかどうかを決定する。バ
イパス・フアクタの目的は、長いシーケンシヤル
参照パターンの発生を検出することである。長い
シーケンシヤル・ランは再使用性が少ないという
特性を有し、従つてこの種のデータをキヤツシ
ユ・メモリに記憶することは望ましくない。何故
ならば、それはヒツト率（即ち、キヤツシユ中で
次にリクエストされるデータを発見する確率）を
低くするからである。従つて、所定数（例えば
3072）のバイトが、単一のデータ転送リクエスト
でキヤツシユ・メモリへ入れられる最大数のデー
タ・バイトとして許される。それより多いデータ
が単一アクセスで要求されれば、シーケンシヤ
ル・ランの存在が決定され、ミスの場合でもデー
タはキヤツシユへ入ることを許されない。 もしバイパス・フアクタを超過しておらず全体
的ヒツトが生じたのであれば（即ち、リクエスト
されたデータの全てがキヤツシユ中に現存すれ
ば）、コントローラは、単にキヤツシユ・メモリ
からホスト・プロセツサへリクエストされたデー
タを転送するために必要な動作を実行する。もし
全体的ヒツトが生じていなければ、リクエストさ
れたデータはデイスクからキヤツシユ・メモリへ
転送され、キヤツシユからホスト・プロセツサへ
データを転送するため、適当な動作が実行され
る。読出動作が全体的ヒツトである場合、後に詳
細に説明するように、必要な動作はキヤツシユ・
アルゴリズム中で設定され、従つて、これら動作
を設定するステツプはバイパスすることができ
る。これに対し、キヤツシユに関連のない動作、
又は「通過書込み」でない書込動作、又はバイパ
ス・フアクタを超える読出動作のリクエストは、
マイクロプロセツサがデイスクとの間のデータ転
送に必要な動作を設定することを要する。 データ転送動作を実行した後に、後に詳細に説
明するように割込リクエストがセツトされ動作は
完了する。 ホスト・プロセツサから受取られた指令が現在
キヤツシユ・メモリに記憶されていないデータに
対するリクエストであり、従つて「読出ミス」を
生じるものと検定して、コントローラのキヤツシ
ユ・アルゴリズム動作を詳細に説明する。第５図
の流れ図に示されるように、もしキヤツシユが設
置されており、キヤツシユ動作がリクエストされ
たならば、キヤツシユ・アルゴリズムが実行され
る。キヤツシユ・アルゴリズムの流れ図が第６ａ
図乃至第６ｃ図に示される。図面に示されるよう
に、マイクロプロセツサは、書込動作がリクエス
トされたかどうかを決定する。もしリクエストさ
れていなければ、通過書込フラグ及び書込動作フ
ラグがリセツトされて、読出動作が表示される。
次にマイクロプロセツサは3072個のデータ・バイ
トを超えるデータ・バイトがリクエストされたか
どうかを決定する。もしリクエストされていれ
ば、バイパス・フアクタを超過したかどうかを決
定するため、キヤツシユ状況がセツトされる。こ
こで再び注意すべきは、バイパス・フアクタは
3072バイトである必要はなく、他の適当な数であ
つてよいことである。更に、キヤツシユ・メモリ
から長いシーケンシヤル・ランを除去することが
望まれなければ、バイパス・フアクタを使用しな
くてもよい。 バイパス・フアクタを超過していなければ、デ
イスク動作レコード・カウンタ及びヒツト／ミ
ス・ブロツク・フラグがクリアされる。次にブロ
ツク・カウンタが１へセツトされ、マイクロプロ
セツサは、そのデイスクに対する相対ブロツク・
アドレス（RBA）とハツシユ・ナンバー（即ち
311）を受取る。次に、キヤツシユ状況は全体的
ヒツトへ設定される。次に、ベース・レジスタ２
を初期設定する動作が実行され、ホスト・プロセ
ツサのメイン・ストレージと通信するためキヤツ
シユが能動化され、第３図を参照して説明したよ
うにして、デイレクトリイ・テーブルの探索が実
行される。 もしリクエストされたブロツクがデイレクトリ
イ・テーブル中に発見されなければ、第３図で示
されるようにシツト・フラグがリセツトされ、そ
れによつてミスが示される。ここで注意すべき
は、第３図の動作中にセツト又はリセツトされる
ヒツト・フラグは、第６ａ図のキヤツシユ・アル
ゴリズムの始めにリセツトされるヒツト・ブロツ
ク・フラグ又はミス・ブロツク・フラグと区別し
なければならないことである。ヒツト・フラグ
は、現在のデータ・ブロツクがキヤツシユ中にあ
るかどうかを示すために使用され、ヒツト・ブロ
ツク・フラグ及びミス・ブロツク・フラグは、後
の説明から更に明らかになるように、ヒツト又は
ミスが生じた最初のブロツクを示すために使用さ
れる。 第６ａ図へ戻つて、デイレクトリイ・テーブル
を探索した後に、マイクロプロセツサは、リクエ
ストされたデータ・ブロツクが発見されたかどう
かを決定するため、ヒツト・フラグを検査する。
読出動作でデータ・ブロツクが発見されず、ヒツ
ト・フラグがリセツトされたものと仮定すると、
マイクロプロセツサは、少なくとも８個のデー
タ・レコード（１ブロツク）がデイスクからキヤ
ツシユへ転送されることを示すため、レコード・
カウンタへ８を加える。この数は単なる一例であ
つて、特定のシステム要求に応じて変更されてよ
い。次に、ミス・ブロツク・カウンタが１へセツ
トされ、１ページがキヤツシユへ加えられる。次
に、マイクロプロセツサは、デイスクからキヤツ
シユへミスのブロツクを転送するのに必要な動作
を設定し、かつキヤツシユからホスト・プロセツ
サへデータを転送するために必要な動作を設定す
る。単一のデータ・ブロツクがリクエストされ、
そのデータ・ブロツクがミスであつたとすれば、
デイスクからリクエストされたデータを転送する
ため、RBAが適当な開始点へ調節され、キヤツ
シユ状況がミスへセツトされ、プリフエツチ計算
が実行される。次に、システムは第５図に示され
るように動作する。 複数のデータ・ブロツクがリクエストされた
時、３ブロツクの「ミス・ヒツト・ミス」の状態
が３ブロツクのミスとして処理されるように、キ
ヤツシユ・アルゴリズムが実行される。何故なら
ば、２つの小さなデータ・ブロツクを２つの動作
で転送するのではなく、３つのデータ・ブロツク
を１つの動作で転送することによつて、時間が全
体として節約されるからである。「ミス・ヒツ
ト・ミス」状態の検出は、次のとおりである。第
６ａ図及び次の表１を参照すると、デイレクトリ
イ・テーブルの最初の探索を開始する前に、デイ
スク動作レコード・カウンタ、ヒツト・ブロツ
ク・フラグ、及びミス・ブロツク・フラグが全て
クリアされ、ブロツク・カウンタが１へセツトさ
れることが分る。デイレクトリイ・テーブルの最
初の探索は、最初にリクエストされたブロツクの
ハツシユ・エントリイ・ナンバーを使用して実行
される。上記ナンバーはそのブロツクのRBAか
ら決定される。データ・ブロツクが発見されなけ
れば、第３図に示されるデイレクトリイ探索の間
に、ヒツト・フラグがリセツトされる。探索の終
りに（第６ａ図参照）、マイクロプロセツサはヒ
ツト・フラグを検査し、ミスが生じたかどうかを
決定する。ミスが生じた場合、デイスクからキヤ
ツシユへ８個のレコード（１ブロツク）が転送さ
れねばならないことを示すため、レコード・カウ
ンタが８だけ増加される。この時点における状態
は、表１のT₁に示されている。

【表】 第６ａ図の５２に示される判定動作において、
マイクロプロセツサは、「ミス・ヒツト・ミス」
状態が生じたかどうかを決定するため、ヒツト・
ブロツク・フラグ及びミス・ブロツク・フラグを
検査する。そのような状態が生じていない場合、
マイクロプロセツサは、前にミスがあつたかどう
かを決定するため、ヒツト・ブロツク・フラグ及
びミス・ブロツク・フラグを検査する。データ・
ブロツクはリクエストされた最初のデータ・ブロ
ツクであるから、「答」はノーであり、ミス・ブ
ロツク・フラグは、ブロツク・カウンタの値に等
しくセツトされる。この状態は表１のT₂で示さ
れる。ここで注意すべきは、ミス・ブロツク・フ
ラグが最初のミスが生じたブロツク・ナンバーを
示すことである。第６ｂ図に示すように、マイク
ロプロセツサはページをキヤツシユへ付加し、ミ
スのデータ・ブロツクの転送に必要なデイスクか
らキヤツシユへ、及びキヤツシユからホスト・プ
ロセツサへの動作（第６ｃ図）を設定する。 全てのリクエストされたブロツクが検査された
わけではないから、ブロツク・カウンタが１だけ
増加され、第２のデータ・ブロツクが計算され
る。次に、マイクロプロセツサはデイレクトリイ
探索の直前のキヤツシユ・アルゴリズム地点へ戻
り、第３図のデイレクトリイ探索が第２のデー
タ・ブロツクについて繰返される。この時点のカ
ウンタ及びフラグの状態は表１のT₃に示される。 次にデイレクトリイ・テーブルが第２のデー
タ・ブロツクを求めて探索される。もしそれが発
見されると、ヒツト・フラグがセツトされ、第３
図に示されるように、この第２ブロツクのキヤツ
シユ・アドレスが保存される。ここで再び第６ａ
図を参照すると、マイクロプロセツサはヒツト・
フラグを検査し、第２のデータ・ブロツクが第２
の探索中に発見されたことを知る。次にマイクロ
プロセツサは、第６ｂ図に示されるアルゴリズム
の通路Ａへブランチする。この第２のデータ・ブ
ロツクが今や最も近時に使用されたブロツクであ
ることを示すため、LRUテーブルが更新される。
先行するヒツトはないから、ヒツト・ブロツク・
フラグはブロツク・カウンタの現在の値（カウン
ト２）へセツトされる。この時点における状態は
表１のT₄に示される。ミス・ブロツク・フラグ
及びヒツト・ブロツク・フラグは、それぞれ最初
のミス及び最初のヒツトのブロツク・ナンバーを
表示する。第６ｃ図に示されるように、次にマイ
クロプロセツサは、第２のデータ・ブロツクのた
めに、必要なキヤツシユからホスト・プロセツサ
への動作を設定する。 依然として、全てのリクエストされたデータ・
ブロツクが検査されたわけではないから、ブロツ
ク・カウンタが再び１だけ増加され、第３のデー
タ・ブロツクのブロツク・ナンバー及びハツシ
ユ・エントリイ・ナンバーが計算され、マイクロ
プロセツサは、デイレクトリイ探索の直前のアル
ゴリズム地点へ戻る。この時点における状態は、
表１のT₅で示される。次にデイレクトリイ・テ
ーブルが第３図に示された手順に従つて探索され
る。リクエストされた第３のデータ・ブロツクは
発見されないものと仮定すると、ヒツト・フラグ
がリセツトされ、読出ミスを表示する。デイレク
トリイ探索動作の終りに、マイクロプロセツサは
ヒツト・フラグを検査し、リクエストされた第３
のデータ・ブロツクが発見されたかどうかを決定
する。もしそれが発見されたのであれば、マイク
ロプロセツサは第６ｂ図に示される通路Ａをたど
り、リクエストされた第３のデータ・ブロツクを
LRUテーブル中で最も近時に使用されたブロツ
クとする。前にヒツトが生じたので、ブロツク・
ヒツト・フラグのセツトはスキツプされ、キヤツ
シユからホストへのプロセツサ動作が第３のデー
タ・ブロツクのために設定される。 第３のデータ・ブロツクがデイレクトリイ探索
で発見されないものと仮定すると、８の値が再び
レコード・カウンタへ加えられ、第６ａ図におけ
る判定動作５２の直前には、カウンタ及びフラグ
状態は、表１のT₆で示されるようになる。マイ
クロプロセツサはブロツク・ヒツト・フラグ及び
ブロツク・ミス・フラグを検査し、最初のブロツ
クがミスであり、第２のブロツクがヒツトである
ことが分るので、「ミス・ヒツト・ミス」の状態
となり、第６ｂ図の通路Ｃがとられる。デイスク
からキヤツシユへ第２ブロツクを転送するのに必
要な動作が設定され、レコード・カウンタへ８が
加えられて、このデータ転送を示す。ミスのデー
タ・ブロツクに対処するため、ページがキヤツシ
ユへ加えられ、キヤツシユ・アルゴリズムが前の
ように実行される。第２のデータ・ブロツクは単
に再び書かれるだけであるから、それについては
ページはキヤツシユへ加えられないことに注意さ
れたい。第６ｂ図の動作５３は、ミスのデータ・
ブロツクについてページがキヤツシユへ加えられ
るキヤツシユ・アルゴリズムの部分を示す。これ
について第７図を参照して詳細に説明する。先
ず、キヤツシユ・メモリ中に残つている自由ペー
ジの数が計数される。これは、例えば、第２Ａ図
の自由ページ・カウンタ５４をポーリングする
か、デイレクトリイ・ポインタ欄にエントリイを
有しないLRUテーブルのリストの数を計数する
ことによつてなされる。もし現在利用できる自由
ページが存在しなければ、LRUテーブルから決
定された最も使用時点の古いページがキヤツシユ
から削除される。次に、加えられようとしている
ブロツクに対応するハツシユ・エントリイ・ナン
バーが既に使用されたかどうかを決定するため、
デイレクトリイ・テーブルが検査される。これ
は、第２ａ図のデイレクトリイ・テーブルの最初
の欄にある自由／使用インデイケータを検査する
ことによつて、容易に決定される。もしそのエン
トリイが既に使用されているものでなければ、第
８図に示すようにして、現在のハツシユ・ナンバ
ーを使用して、ページがキヤツシユへ加えられ
る。自由ページ・カウンタが１だけ減少され、使
用時の最も新しいエントリイの前方がポインタ
（これは最初の自由ページを指定する）が検査さ
れて、新しいデータ・ブロツクがどこに記憶され
るかを決定する。次に、第2b図のMRUポインタ
５１が、この新しいページの値へセツトされ、新
しいページ・リストのデイレクトリイ・ポインタ
が現在のハツシユ・エントリイ・ナンバーの値へ
セツトされる。次にマイクロプロセツサは、現在
のハツシユ・エントリイ・ナンバーによつて指定
されるデイレクトリイ・エントリイへ行き、自
由／使用インデイケータを「使用」状態へセツト
し、ホーム・インデイケータを「ホーム」状態へ
セツトし、次いで新しいブロツクのサブシステ
ム・ブロツク・アドレスを入れる。次に、新しい
エントリイの前方ポインタが連鎖の終りを示すた
めにセツトされ、新しいデータ・ブロツクが記憶
されるキヤツシユ・アドレスを入れる。 第８図の動作５４及び５５は、適当な「自由連
鎖」（即ち、自由ページの連鎖）を維持するため
に必要である。デイレクトリイ・テーブル中の自
由エントリイ（即ち、使用されていないエントリ
イ）は、その前方及び後方ポインタによつて連鎖
として配列されている。そして、今やこの連鎖中
のエントリイの１つ（即ち、現在のハツシユ・エ
ントリイ・ナンバーに対応するエントリイを使用
することが望まれる。かくて、第９ａ図に示され
るように、いくつかのエントリイが相互に連鎖さ
れており、エントリイ５６を使用することが望ま
れるものとする。これは自由連鎖を破るので、新
しく使用されたエントリイ５６の周囲で連鎖を再
び経路づけることが必要である。エントリイ５６
を使用する前は、エントリイ５６の後方ポインタ
は前の自由エントリイ５７を指定し、エントリイ
５６の前方ポインタは次の自由エントリイ５８を
指定する。連鎖を再び経路づける場合、マイクロ
プロセツサはエントリイ５７を指定するエントリ
イ５６の後方ポインタをたどり、エントリイ５７
の前方ポインタをエントリイ５６の前方ポインタ
と置換する。それによつて、エントリイ５７の前
方ポインタは今やエントリイ５８を指定する。次
にプロセツサは、エントリイ５８を指定するエン
トリイ５６の前方ポインタをたどり、エントリイ
５８の後方ポインタをエントリイ５６の後方ポイ
ンタと置換する。従つて、エントリイ５８の後方
ポインタは、今やエントリイ５７を指定する。結
果として生じた新しい自由連鎖は第９ｂ図に示さ
れるが、そこではエントリイ５６が連鎖から除去
されている。 ステツプ54及び55で自由連鎖を再配列した後
に、マイクロプロセツサは、新しいエントリイが
最初の自由エントリイであつたかどうかを決定す
る。例えば、第９ａ図において、最初の自由エン
トリイはエントリイ５７である。この場合、マイ
クロプロセツサは第６ｂ図のキヤツシユ・アルゴ
リズムへ戻る。しかし、衝突リストを管理するた
め、第２ａ図の自由ポインタ５２が自由連鎖中の
最初の自由エントリイを正しく指定することが大
切である。もし新しく加えられたデータ・ブロツ
クが連鎖中の最初の自由エントリイ（即ち、エン
トリイ５７）を使用するならば、新しい最初の自
由エントリイはエントリイ５６である。エントリ
イ５６はエントリイ５７の前方ポインタによつて
指定された。従つて、自由ポインタ５２は、そこ
に含まれる値をエントリイ５７の前方ポインタへ
変更されることによつて更新される。ここで注意
すべきは、もし捕捉されたエントリイが最初の自
由エントリイであれば、このエントリイは自由連
鎖中の最初のものであり、後方ポインタを有しな
いことである。従つて、ステツプ54は必要でな
く、ステツプ55は単に自由連鎖中の次のエントリ
イの後方ポインタを消去するだけである。 第１０ａ乃至第１０ｄ図は、新しいデータ・ブ
ロツクをキヤツシユ・メモリへ加える場合に生じ
るいくつかの可能性を示す。これら図面の各々に
おいて、Ｈは「ホーム」エントリイによつて占拠
されている特定のデイレクトリイ・テーブル・エ
ントリイを示し、Ｃはデイレクトリイ・テーブ
ル・エントリイが「衝突」エントリイによつて占
拠されていることを示す。第１０ａ図は、現在の
ハツシユ・エントリイ・ナンバー（即ち、新しい
データ・ブロツクのハツシユ・エントリイ・ナン
バー）がデイレクトリイ・テーブル中で使用され
なかつたことを示す。その場合、必要な動作は、
新しいデータ・ブロツクのデイレクトリイ情報
を、このデイレクトリイ・テーブル・エントリイ
に挿入し、自由エントリイの連鎖を再配列するこ
とである。 ここで再び第７図へ戻つて、もし現在のハツシ
ユ・エントリイ・ナンバーのホーム・ポジシヨン
が既にデイレクトリイ・テーブル中で占拠されて
いることをマイクロプロセツサが識別すると、他
のデイレクトリイ・テーブル管理動作が必要とな
る。最初の可能性は、新しいデータ・ブロツクの
ホーム・ポジシヨンが、衝突リストの一部ではな
いホーム・エントリイによつて既に占拠されてお
り、従つてそれ自体連鎖の終りであるかも知れな
いことである。第３図のデイレクトリイ探索の間
に、マイクロプロセツサは連鎖終了（EOC）イ
ンデイケータをセツトし、第７図のプログラム通
路５９をたどる。現在のエントリイに対して余地
（空白）を作るため、キヤツシユ中のページを削
除することが必要であり、また削除されたLRU
エントリイがホーム・ポジシヨンを占拠していた
エントリイであつたならば、マイクロプロセツサ
は第７図のプログラム通路６０及び６１をたど
る。以前にホーム・ポジシヨンを占拠していたエ
ントリイが削除されると、そのポジシヨンは自由
になり、前に第８図と関連づけて説明したよう
に、現在のハツシユ・エントリイ・ナンバーを使
用して、新しいページを加えることができる。そ
の結果は、第１０ａ図に示される通りである。 もしホーム・ポジシヨンを占拠しているEOC
エントリイが、新しいページに対して余地を作る
ため、削除されていなければ、マイクロプロセツ
サは第７図のプログラム通路６２をとる。現在の
ハツシユ・エントリイ・ナンバーはデイレクトリ
イ・テーブルの最初の自由エントリイのハツシ
ユ・エントリイ・ナンバーによつて置換される。
前に第８図と関連して説明したように、この新し
い現在のハツシユ・エントリイ・ナンバーを使用
して、ページが加えられる。更に、このエントリ
イは、連鎖の終りにある衝突エントリイになる。
従つて、新しいエントリイ・ポジシヨンの「ホー
ム」インデイケータはオフにされ、元のEOCエ
ントリイを遡つて指定するため（即ち、ホーム・
ポジシヨンを占拠するエントリイを遡つて指定す
るため）後方ポインタがセツトされる。最後に、
ホーム・ポジシヨンを占拠しているエントリイ
（これは前にEOCインデイケータを含んでいた）
の前方ポインタは、今や新しく加えられたエント
リイを指定するように変更される。変更された結
果は第１０ｂ図に示される。第１０ｂ図におい
て、ホーム・ポジシヨンは既にホーム・エントリ
イ６３によつて占拠されており、新しいエントリ
イは、以前に最初の自由エントリイであつたポジ
シヨンへ動かされる。エントリイ６３の前方ポイ
ンタはエントリイ６４を指定するように変更さ
れ、エントリイ６４の後方ポインタはエントリイ
６３を指定するようにセツトされ、エントリイ６
４のホーム・インデイケータはオフにされる。エ
ントリイ６４の前方ポインタは、第８図に示され
るように、EOCエントリイを表示するようにセ
ツトされる。 第２の可能性として、複数エントリイ衝突リス
トの最初のエントリイであるホーム・エントリイ
によつて、ホーム・ポジシヨンが既に占拠されて
いる場合がある。この場合、第３図のデイレクト
リイ探索の間に、マイクロプロセツサは衝突リス
トの全体を走査しており、リクエストされたデー
タ・ブロツクを発見することなく、連鎖の終りに
到達する。EOCインデイケータはセツトされて
おり、現在のハツシユ・エントリイ・ナンバーも
また変更されて、デイレクトリイ探索の間に発見
された連鎖の終りを指定する。既に新しいデー
タ・ブロツクのホーム・エントリイ・ポジシヨン
で始まる衝突リストが存在するので、新しいデー
タ・ブロツクは次のようにして、この衝突リスト
の終りに加えられねばならない。先ず、EOCイ
ンデイケータはデイレクトリイ探索の間にセツト
されているから、マイクロプロセツサは第７図の
プログラム通路５９をたどる。もし衝突リスト中
のEOCエントリイが削除されて、新しいページ
のために余地を作つていなければ、プログラム通
路６２がとられ、第１０ｂ図と関連して説明した
ようにして、新しいエントリイが連鎖の終りへ加
えられる。 もしEOCエントリイが削除されていれば、そ
れは次のようにして新しいエントリイによつて置
換される。先ず、前のEOCエントリイは削除さ
れているから、それまで最後から２番目であつた
エントリイのナンバーが、第３図の動作６５でマ
イクロプロセツサによつて記憶される。マイクロ
プロセツサは、元のEOCエントリイのナンバー
を、この記憶されたナンバーと入替える。EOC
エントリイのナンバーが、このように変更された
後に、現在のハツシユ・ナンバーが最初の自由エ
ントリイのナンバーによつて置換され、新しいペ
ージが前と同じく、連鎖の終りへ加えられる。第
１０ｃ図は、エントリイ６３及び６４を含む衝突
リストの最初のエントリイであるホーム・エント
リイによつて、新しいデータ・ブロツクのホー
ム・ポジシヨンが既に占拠されている場合を示
す。ハツシユ・エントリイ・ナンバーは、第３図
のデイレクトリイ探索の終りで、既にEOCエン
トリイに等しくリセツトされており、従つて、第
７図のプログラムに従つた新しいデータ・ブロツ
クは、先ず衝突エントリイ６４の場所で入れられ
ようとする。もし衝突エントリイ６４が削除され
たばかりであれば、新しいデータ・ブロツクはそ
のポジシヨンに入れられる。そうでなければ、新
しいエントリイ６６が作られ、エントリイ６４及
び６６は、エントリイ６４の前方ポインタ及びエ
ントリイ６６の後方ポインタによつて相互に連結
される。 最後の最も単純な可能性は、新しいエントリイ
のホーム・ポジシヨンが衝突エントリイによつて
占拠されることである。この場合、第３図のプロ
グラム通路６７はデイレクトリイ探索の間に通過
されており、EOCインデイケータはセツトされ
ていない。従つて、マイクロプロセツサは第７図
の通路６８をたどり、衝突エントリイは最初の自
由なエントリイ位置へ動かされ、新しいエントリ
イがそのホーム・ポジシヨンに挿入される。この
状態は第１０ｄ図に示されている。第１０ｄ図に
おいて、エントリイ６３は、再び新しいエントリ
イのホーム・ポジシヨンを表示する。このエント
リイ６３のポジシヨンは既に衝突エントリイによ
つて占拠されている。この衝突エントリイは、エ
ントリイ６９，６３，７１を含む衝突リストの第
２のエントリイである。この状態において、エン
トリイ６３のポジシヨンに存在していた衝突エン
トリイは最初の自由エントリイ７２のポジシヨン
に動かされ、エントリイ６９の前方ポインタ、エ
ントリイ７１の後方ポインタ、エントリイ７２の
前方及び後方ポインタは衝突リストの連続性を維
持するために調整される。衝突エントリイが１度
エントリイ６３のポジシヨンから除かれると、そ
のホーム・ポジシヨンに新しいエントリイを作る
ことができる。 第１０ｄ図に示した方法に従つてデイレクトリ
イ・テーブルのエントリイを再配置する手法を、
第１１図の流れ図を参照して詳細に説明する。第
１１図は第７図の動作７３に対応する。先ず、衝
突するデイレクトリイ・テーブルのエントリイが
マイクロプロセツサによつて選択され、それが依
然として使用されているかどうかが検査される。
もし新しいデータ・ブロツクについて余地を作る
ため、このエントリイが削除されたのであれば、
もはや衝突は存在せず、第８図の方法に従い現在
のハツシユ・エントリイ・ナンバーを使用するこ
とにより、新しいページをキヤツシユへ加えるこ
とができる。エントリイが依然として使用されて
いれば、そのデータは、後に最初の自由エントリ
イのポジシヨンへ転送するため、マイクロプロセ
ツサによつて記憶される。かくて、第１０ｄ図の
場合、エントリイ６３のポジシヨンに存在してい
た衝突エントリイのデータは、後に最初の自由エ
ントリイ７２のポジシヨンへ転送するため、マイ
クロプロセツサによつて記憶される。 衝突エントリイ６３は、現在第２ｂ図のLRU
テーブル中の或るポジシヨンを占めている。この
ポジシヨンは、データが１つのデイレクトリイ・
テーブル・エントリイから他のエントリイへ動か
されているので、変更されてはならない。従つ
て、マイクロプロセツサは、デイレクトリイ・テ
ーブルのエントリイ６３に対応するLRUテーブ
ル・エントリイへ進み、最初の自由エントリイ７
２を指定するため、LRUリスト中のデイレクト
リイ・ポインタを変更する。かくて、エントリイ
７２は、以前にエントリイ６３によつて占められ
ていたLRUテーブル中の同じ優先ポジシヨンを
占拠する。 次にマイクロプロセツサはエントリイ６３の後
方ポインタによつて指定されたエントリイ６９へ
進み、最初の自由エントリイ７２を表示するた
め、エントリイ６９の前方ポインタを変更する。
次に、エントリイ６３に含まれていたデータ（自
由／使用インデイケータ、ホーム・インデイケー
タ、フアイル・サブシステム・ブロツク・アドレ
ス、後方ポインタ、前方ポインタ、及びキヤツシ
ユ・アドレス）が全て最初の自由エントリイ７２
のポジシヨンへ転送される。もし衝突エントリイ
がEOCエントリイであつたならば、変更されね
ばならない後続エントリイは存在しない。しか
し、衝突エントリイが第１０ｄ図の場合のように
EOCエントリイでなければ、マイクロプロセツ
サはエントリイ７２の前方ポインタによつて指定
されるエントリイ７１へ進み、エントリイ７２を
指定するようにエントリイ７１の後方ポインタを
変更する。 第１１図のプログラム地点７４では、衝突リス
トの同一順序が維持されかつエントリイ７２によ
つて指定されたキヤツシユ・メモリ・データが
LRUテーブル中で同一の優先ポジシヨンを維持
するという点で、デイレクトリイ・テーブルの構
成は変更されていない。第１１図の残りのステツ
プは、エントリイ６３を最初の自由エントリイに
することによつて、「自由連鎖」を実質的に元の
状態へ復元する。これは、第２ａ図の自由ポイン
タ５２を変更して衝突していたエントリイ６３を
指定するようにし、最初の自由エントリイからの
全てのデータをエントリイ６３のポジシヨンへ転
送し、最初の自由エントリイ７２を指定していた
最後の自由エントリイの前方ポインタを変更して
エントリイ６３を指定するようにし、最初の自由
エントリイ７２を指定していた第２の自由エント
リイの後方ポインタを変更してエントリイ６３を
指定するようにすることによつてなされる。今や
デイレクトリイ・テーブルは実質的に元の状態へ
設定される。新しいデータ・ブロツクのホーム・
エントリイ・ポジシヨンは自由になつているの
で、現ハツシユ・ナンバーを使用して新しいペー
ジをキヤツシユへ加えることができる。 ここで再び第６ａ図と第６ｂ図に戻ると、マイ
クロプロセツサが要求されたデータ・ブロツクの
全てについて動作を循環させた後、前述した「ミ
ス・ヒツト・ミス」の状態があるものと反応する
と、マイクロプロセツサは、ミスのデータ・ブロ
ツク１及び３を２つの新しいページとしてキヤツ
シユ・メモリへ加えており、リクエストされたデ
ータをデイスクからキヤツシユへ、かつキヤツシ
ユからホスト・プロセツサへ転送するのに必要な
全ての動作を設定している。読出動作がリクエス
トされ、リクエストされたデータ・ブロツクの少
なくとも１つがミスであつたから、第６ｂ図にお
いてプログラム通路７６及び７７がたどられる。
通路７７の目的は、追加のデータ・ブロツクが間
もなくリクエストされる可能性が存在する場合
に、リクエストされていないデータ・ブロツクを
キヤツシユ・メモリへ転送することによつて、キ
ヤツシユ・メモリの効率を最大にすることであ
る。 次のような典型的な動作シーケンスを考えてみ
る。 ケース：122、123、124、125、126 ケース：122、123、1594、720、124、14、
125、1595、126 ケース：127、128、129、130、131 各ケースで表示されたナンバーは、一連のデイ
スク・データ読出リクエストにおけるRBAロケ
ーシヨンを表わす。固定ブロツク長が８の場合、
ケースの項目は、RBA１２０〜１２７を含む
ブロツクと関連している。かくて、ケースにお
ける最初のRBAはブロツク中の項目３であり、
最後にリクエストされたRBAは、ブロツク中の
項目７である。 ケースにおいて、同じ５つのRBAがリクエ
ストされ、異つたブロツクから他のRBAロケー
シヨンが追加される。これらの例において、ホス
ト・プロセツサは、RBAロケーシヨンの短い上
昇シーケンスからデータをリクエストした。シー
ケンスを完了する時間は比較的短く、一般的に
200回以下のデイスク参照時間内にある。RBA１
２２―１２６の所与のシーケンスは、数百回のデ
イスク・リクエストの後に全面的又は部分的に反
復されてよい。動作の始めに、該当するブロツク
がキヤツシユ・メモリ中にないものと仮定すれ
ば、RBA１２２について読出ミスが生じ、該当
するブロツクの全てのレコードがキヤツシユ・メ
モリへ転送される。かくて、ブロツクがキヤツシ
ユ・メモリへ転送されている間、最初のリクエス
トは効率上不利点を有するが、RBA１２３―１
２６に対する次のリクエストは読出ヒツトを生
じ、かなりの効率改善となる。経験的には、近い
将来RBA１２０又は１２１に対するリクエスト
を受ける可能性は少なく、従つてこれらの項目を
キヤツシユ・メモリに保存すると若干の不利益を
生じる。RBA１２０及び１２１を記憶する場合
の不利益は、最初のリクエストされたレコードか
ら始まるデータ・ブロツクをキヤツシユ・メモリ
中に記憶することによつて避けることができる
が、これはシステムを複雑にする点で実際的とは
言えない。 第６ｂ図の通路７７によつて実行される「プリ
フエツチ」動作は、一般的にはケースで示され
る動作形式に関連している。ケースにおいて、
RBA１２７に対するリクエストは読出ミスを生
じ、該当するブロツクの全てがデイスクからキヤ
ツシユへ転送される結果となる。しかし、RBA
１２８に対する次のリクエストは、該当するブロ
ツクの一部分ではなく、このリクエストは読出ミ
スを生じ、従つて次のブロツク１６がキヤツシユ
へ記憶される。かくて、２つの独立したデイスク
読出動作がケースで必要となる。ケースにお
けるこの問題は、デイスク／キヤツシユ記憶のた
めに採用された固定ブロツクの境界と、ユーザに
よつて発生されたシーケンシヤルな参照パターン
の境界との間の不適当な整列状態から起る。 ケースで、２つの独立したデイスク読出動作
の必要性を除くため、最初のデイスク読出動作の
間に、追加のデータ・ブロツクをキヤツシユ・メ
モリへ転送することが、本発明の特徴である。 実施例において、統計上の確率は、ホスト・プ
ロセツサによつてリクエストされた現在の動作の
最後のレコードが特定ブロツクに含まれるポジシ
ヨンの関数であると考えられる。従つて、プリフ
エツチ動作は、固定したブロツク境界内のリクエ
ストされたレコード位置の論理限界比較に基づ
く。１つの例として、論理限界はブロツク内の5/
８ロケーシヨンにセツトされることができる。即
ち、或るブロツク１５の論理限界は、ブロツク中
の５番目のレコードであるRBA１２４におかれ
てよい。RBA１２０―１２３に対する読出ミス
のリクエストは論理限界を満足させず、ブロツク
１５のみがキヤツシユへ転送される。他方、
RBA１２４―１２７に対する読出ミスのリクエ
ストは論理限界を満足させる。次のブロツク１６
がキヤツシユ・メモリ中に記憶されていないと仮
定すれば、ブロツク１５及び直後に続くブロツク
１６からのデータはキヤツシユへ読出される。ブ
ロツク内のレコード・ポジシヨンの決定は簡単で
ある。即ちブロツク・ナンバーはRBAをブロツ
ク長で除算することによつて決定され、その剰余
がブロツク内の相対的レコード・ポジシヨンにな
る。 発明者の研究によれば、望ましいブロツク長の
値は、８個から24個までのレコードである。前の
シーケンスの一部のみを繰返す場合が多く、これ
は、比較的長いシーケンスの場合に度々起る。も
し前のシーケンスの一部のみが繰返されるのであ
れば、キヤツシユ・メモリ中に繰返された部分を
維持し、シーケンスの残りを削除することが望ま
しいかも知れない。しかし、これは固定ブロツク
長が非常に長い場合（例えば24レコード）には実
際的でない。従つて、長いシーケンスを複数かつ
固定長のデータ・ブロツクとして記憶することに
より、細分性を維持するのが望ましい。そうすれ
ば、個々のデータ・ブロツクは、それが将来のリ
クエストを待機してどれくらい長くキヤツシユ中
に保持されるかについて、個別的に管理されるこ
とができる。或るブロツクは、将来のリクエスト
が受取られなければ削除されてよく、キヤツシユ
へ同時に記憶された他のブロツクは、反復的リク
エストが近い将来になされれば、そのまま維持さ
れる。従つて、実施例では固定ブロツク長として
８個のレコードが選択される。実効ブロツク長
は、時に応じて複数の固定ブロツクを転送するこ
とによつて変更される。 前述したように、１つの追加的データ・ブロツ
クを転送できるかを決定するため、１つの論理限
界のみを使用することが可能であるが、実施例で
は、２論理限界法が使用される。２論理限界法で
は、各論理限界は前述した固定長ブロツク内の異
つたロケーシヨンで生じる。２つの論理限界は
T₁及びT₂で表わされる。T₂はT₁より大きいか又
はそれに等しい。論理限界T₁の比較で満足すべ
き結果が得られると、デイスク上順次に配置され
たデータ・ブロツクが読出されキヤツシユ・メモ
リへ記憶される。最初のデータ・ブロツクは読出
ミスを生じたリクエストに対する最後のレコード
を含み、第２のデータ・ブロツクは、リクエスト
されたレコードを含む最初のブロツクの直後に続
くブロツクである。論理限界T₂の比較が満足す
べきものであれば、デイスク上順次に配置された
３つのデータ・ブロツクを読出しそれらをキヤツ
シユ・メモリに記憶する決定がなされる。これら
ブロツクの最初のものはリクエストされたデー
タ・レコードを含み。 ここで注意すべきは、単一の読出リクエストで
複数レコードを読出す場合、最後のレコードが読
出ミスである時にのみ、プリフエツチ動作が実行
され、プリフエツチ動作のための論理限界比較
は、データ・ブロツクにおける最後のリクエスト
されたレコードのポジシヨンへ適用されることで
ある。これについては第１２ａ図乃至第１２ｃ図
を参照して具体的に説明する。各ブロツクには、
８個のレコードが含まれる。もしブロツクａのレ
コード０及び１が第１２ａ図に示されるようにホ
スト・プロセツサからリクエストされると、リク
エストされたレコードを含むブロツクの全体がキ
ヤツシユ・メモリへ転送される。もしブロツクａ
におけるレコード２―５の１つが第１２ｂ図に示
されるようにリクエストされると、ブロツクａの
みでなく次に続くブロツクｂがキヤツシユ・メモ
リへ転送される。ブロツクａにおけるレコード６
又は７のいずれかが第１２ｃ図に示されるように
リクエストされると、ブロツクａの外にブロツク
ｂ及びｃがキヤツシユ・メモリへ転送される。こ
の種の動作をここでは「プリフエツチ」と呼ぶこ
とにするが、これは、ブロツクａの最後の４分の
３がリクエストされた時、比較的高い確率とし
て、続くＩ／Ｏ動作で次のデータ・ブロツクｂか
らレコードがリクエストされ、ブロツクａの最後
の４分の１にあるレコードが現在のＩ／Ｏ動作で
リクエストされると、ブロツクｃからレコードが
リクエストされるであろうという予想に基く。 もしＲが固定ブロツク内の特定レコードの相対
的ロケーシヨンを示すものとすれば、ブロツク長
が８である時、Ｒの値は０から７までの範囲にあ
る。Ｒ＜T₁である時、リクエストされたデー
タ・ブロツクのみが転送され、T₁≦Ｒ＜T₂であ
る時、リクエストされたデータ・ブロツク及び次
のデータ・ブロツクが転送され、Ｒ≧T₂である
時、リクエストされたデータ・ブロツク及び次の
２つのデータ・ブロツクが転送される。平均の実
効ブロツク長は、T₁及びT₂のレベルによつて決
定される。例えばT₁＝T₂＝８の場合、それぞれ
の転送は８レコードを含む単一のブロツクについ
てなされ、T₁＝T₂＝０の場合、それぞれの転送
は、全部で24個のレコードを含む３つのデータ・
ブロツクについてなされる。T₁＝２及びT₂＝６
であれば、転送の４分の１は８個のレコードを含
み、転送の２分の１は16個のレコードを含み、転
送の４分の１は24個のレコードを含み、従つて平
均の実効ブロツク長は16レコードである。例とし
て掲げる次の表は、T₁及びT₂の代表的値を示し、
かつ結果として生じる平均の実効ブロツク長を示
す。

【表】 キヤツシユ・メモリの容量が無限であると仮定
すれば、平均実効ブロツク長が長くなれば、効率
が改善され利点が生じることが分る。ブロツク長
が長くなれば、キヤツシユ・メモリへ多くのデー
タを転送することができ、その結果、将来の読出
ヒツトの確率は高くなる。しかし、実際的な見地
からは、平均実効ブロツク長が長くなれば、或る
限度までキヤツシユ・メモリの効率は改善される
が、その限度を超えると、ブロツク長の増加が効
率を低下させる。これは読出確率がそれ程高くな
い情報が過度に記憶され、メモリ容量を占拠する
ためである。メモリ容量は、より高い確率を有す
る情報のためにより良好に使用されることができ
る。一般的には、論理限界T₁及びT₂を適当にセ
ツトすることによつて、或る最適の平均実効ブロ
ツク長を決定することができる。適当な論理限界
レベルの組を前に説明したが、その場合、デー
タ・ブロツクの最後の４分の１（コータ）にある
リクエストされたレコードのポジシヨンは、全部
で３個のブロツクを転送する結果となり、デー
タ・ブロツクの第２及び第３コータにあるリクエ
ストされたレコードのポジシヨンは、全部で２つ
のブロツクを転送する結果となる。しかし、平均
実効長の大きいものが良いかどうかは、ホスト・
プロセツサによつてリクエストされた一連のレコ
ードの平均の長さに依存する。もし平均シーケン
ス長が非常に長ければ、平均実効ブロツク長の大
きい方が効率を改善して利点を与える。 不幸にして、所与の顧客に対してどのような平
均実効ブロツク長が最適であるかを前もつて知る
方法はなく、更に、最適ブロツク長の値は、所与
に顧客についてタスクごとに変化する。従つて、
効率を最適化するため、論理限界レベルをダイナ
ミツクに制御することが望ましい。これは、シス
テム効率の種々の局面を連続的に評価し、それに
従つて論理限界を変化させることによつて達成さ
れる。しかし実施例ではもつと簡単な方法が選択
される。この方法によれば、論理限界レベルは読
出ヒツト率に従つて連続的に変化させられる。読
出ヒツト率は、システム効率の最重要な尺度の１
つである。読出ヒツト率は、読出ヒツトを生じる
読出リクエストの百分率である。 論理限界T₁及びT₂をダイナミツクに調整する
方法をこれから説明する。比較的直截な方法とし
て、マイクロプロセツサはデイスク・アクセスの
数を計数する第１のカウンタ、デイスク読出アク
セスの数を計数する第２のカウンタ、読出ヒツト
の数を計数する第３のカウンタを含んでよい。マ
イクロプロセツサは、読出ヒツトの数をデイスク
読出アクセスの数で除算することによつて読出ヒ
ツト率を計算する。読出ヒツト率が計算されるの
は、少なくとも1000回のデイスク・アクセス、少
なくとも250回のデイスク読出アクセス、少なく
とも50回の読出ヒツトが生じた時である。これら
最少値の全てが満足させられると、読出ヒツト率
が計算され、３つのカウンタの全てがゼロへリセ
ツトされる。サイクルは、３つの最少値の全てが
再び満足させられるまで継続し、新しい読出ヒツ
ト率が計算される。 平均実効ブロツク長は、T₁及びT₂を変化させ
ることによつて、計算された読出ヒツト率に従つ
て変更される。かくて、T₁及びT₂は、予め選択
された初期値にセツトされることができ、読出ヒ
ツト率は、前記の最少値が生じた後に計算され
る。注意すべきは、読出ヒツトの数がT₁及びT₂
の選択によつて影響を受ける唯一の数値であるこ
とである。 最初の読出ヒツト率が計算された後、実効長の
平均値を単一ステツプだけ増加させるように、
T₁及びT₂の新しい組が選択される。新しい読出
ヒツト率が計算され、前に計算された値と比較さ
れる。もし新しい読出ヒツト率が大きければ、再
びT₁及びT₂が変更され、平均実効ブロツク長が、
単一ステツプだけ増加するようにされる。 T₁及びT₂の変更は、新しく計算された読出ヒ
ツト率が、前に計算された値より小さくなるまで
継続する。前の値より小さくなると、論理限界は
最適の読出ヒツト率が生じた前のレベルへ戻され
る。もし所望ならば、論理限界を前の値へ戻した
後に、確認サイクルが実行されてよい。確認サイ
クルは、通常の評価時間の２倍だけ続き、最新の
論理限界が依然として最良の読出ヒツト率を生じ
ることを確認するサイクルである。 最終的に選択された論理限界は、20又はそれ以
上の標準評価時間の間維持されてよい。その時間
の終りに、新しい評価サイクルが再び取られて、
最大読出ヒツト率に対応する最適論理限界を決定
する。後続する評価において、論理限界レベルが
変更されて、読出ヒツト率が減少するまで、平均
実効ブロツク長が増加又は減少される。次に、最
適論理限界が発見されたことを確かめるため、読
出ヒツト率が減少するまで、平均実効ブロツク長
が反対方向へ変化させられ、次いで、確認サイク
ルが最良の論理限界レベルで実行される。それ
は、論理限界レベルが望ましいものであることを
確かめるためである。 ここで第６ｂ図へ戻つて、もしブロツクのいず
れもミスでなければ、デイスクからキヤツシユへ
の動作は必要でなく、マイクロプロセツサは第６
ｂ図の下部からキヤツシユ・アルゴリズムを出
る。しかし、ミスが生じると、マイクロプロセツ
サは、スタートのRBAをセツトしかつキヤツシ
ユ状況を「ミス」へセツトすることによつてデイ
スクからキヤツシユへの転送動作を準備する。デ
イスクからキヤツシユへの転送を開始する前に、
マイクロプロセツサは「プリフエツチ」の計算を
実行する。それは、後に第１２ａ図乃至第１２ｃ
図及び第１３図を参照して詳細に説明するよう
に、追加のデータ・ブロツクを転送すべきかどう
かを決定するためである。 第１３図はプリフエツチ計算のフローチヤート
である。プリフエツチ動作が実行されるのは、リ
クエストされた一連のブロツク中の最後のブロツ
クがキヤツシユ・メモリ中に発見されない時であ
る。もし最後のブロツクがヒツトであれば、キヤ
ツシユ・アルゴリズムは終り、コントローラ動作
は第５図に示されるように進行し、ミスのデー
タ・ブロツクのみが転送される。最後にリクエス
トされたブロツクがミスであつたと仮定すると、
マイクロプロセツサは、ミスになつたブロツクの
最後の４分の１（レコード６及び７）がリクエス
トされたのかどうかを決定する。もしそうであれ
ば、２のプリフエツチ・ブロツク・カウントがセ
ツトされる。もしそうでなければ、マイクロプロ
セツサは、最後のブロツクの第２又は第３のコー
タ（４分の１）部分がリクエストされたのかどう
かを決定する。もしそうでなければ、プリフエツ
チの必要はなく、キヤツシユ・アルゴリズムは終
る。もし最後のブロツクの第２又は第３コータ部
分がリクエストされたのであれば、１のプリフエ
ツチ・ブロツク・カウントがセツトされる。次に
マイクロプロセツサは、現在のブロツク及びハツ
シユ・エントリイ・ナンバーを増加させ、かつ第
３図に示されるようにして、ブロツクｂのために
デイレクトリイ・テーブルの探索を実行する。も
しブロツクｂが既にキヤツシユにあることが分る
と、キヤツシユ・アルゴリズムは終り、コントロ
ーラ動作は第５図に示されるように進行する。ブ
ロツクａの最後の４分の１がリクエストされた場
合でも、ブロツクｂが既にキヤツシユに存在する
ならば、ブロツクｃをキヤツシユへ転送する利点
はない。 もしブロツクｂがキヤツシユに発見されなけれ
ば、第７図のプロセスを介して新しいページが加
えられ、レコード・カウントが８だけ増加され
て、追加ブロツクの転送を示す。次にプリフエツ
チ・ブロツク・カウントが１だけ減少される。も
し１つのブロツクのみがリクエストされたなら
ば、キヤツシユ・アルゴリズムは終り、リクエス
トされたブロツクは、追加のブロツクｂと共にキ
ヤツシユへ転送される。もし２ブロツクのプリフ
エツチが表示されていれば、現在のブロツク及び
ハツシユ・ナンバーが再び増加され、ブロツクｃ
に対する探索が実行される。もしブロツクｃがキ
ヤツシユ中に発見されなければ、第７図のプロセ
スに従い他のページがキヤツシユへ加えられ、レ
コード・カウントが再び８だけ増加される。 ここで再び第５図へ戻つて、読出動作について
キヤツシユ・アルゴリズムが完了した後、マイク
ロプロセツサは、バイパス・フアクタが超過され
たかどうかを決定する。もしバイパス・フアクタ
が超過されていれば、マイクロプロセツサは第６
ａ図の動作７８でキヤツシユ状況をセツトてして
おり、キヤツシユ・アルゴリズムはその地点で終
つている。続いて、第５図において、マイクロプ
ロセツサはこのキヤツシユ状況を検査するだけで
よい。もしバイパス・フアクタが超過されていれ
ば、デイスクからホスト・プロセツサへデータを
直接に転送するのに必要な動作が通常の態様で設
定される。第５図のフアイル動作７９は、データ
がフアイル（デイスク）へ転送されるか、又はそ
こからデータが転送される時にのみ必要である。
これは、全体的ヒツトの場合には不必要である。
次に、全てのデータ転送動作が実行され、割込リ
クエストをセツトすることによつて、コントロー
ラの動作は終了する。 もしバイパス・フアクタが超過されていなけれ
ば、マイクロプロセツサは第５図のプログラム通
路８１をたどり、もし全体的ヒツトが生じていれ
ば（即ち、リクエストされたデータ・ブロツクの
全てがキヤツシユ中で発見されていれば）、キヤ
ツシユ・アルゴリズム中で設定されたキヤツシユ
からホスト・プロセツサへの転送動作が実行さ
れ、コントローラ動作が終了する。新しくリクエ
ストされたデータ・ブロツクをMRU状態へ変更
することは、第６ｂ図のキヤツシユ・アルゴリズ
ムにおけるプログラム通路Ａで既に達成されてい
る。 もしバイパス・フアクタが超過されておらず、
ミスが生じていれば、フアイル動作が発生され、
データ転送動作が実行され、コントローラ動作が
終了する。 これまでの説明は、主として「読出ミス」の場
合に関する。その場合、少なくとも１つのデー
タ・ブロツクがキヤツシユ・メモリ中で発見され
なかつた。読出ミスの動作は、キヤツシユ内容が
更新される必要がないため複雑ではない。第６ａ
図及び第６ｂ図のキヤツシユ・アルゴリズムにお
いて、通路Ａがとられており、メモリ管理動作
（即ち、リクエストされたデータ・ブロツクを
MRU状態へ更新すること）は、第６ｂ図の動作
８２で実行される。バイパス・フアクタが超過さ
れておらず、全体的ヒツトが生じているものと仮
定すると、マイクロプロセツサは第５図のプログ
ラム通路８３をたどり、リクエストされたデータ
をキヤツシユからホスト・プロセツサへ転送する
動作が実行される。 或る時点で、ホスト・プロセツサはデイスク・
メモリ・ロケーシヨンへ新しいデータを書込むこ
とによつて古いデータと入替えたいと望むかも知
れない。そのような場合、キヤツシユが設けられ
ており、かつ第５図に示されるようにキヤツシユ
動作がリクエストされるものと仮定すれば、第６
ａ図及び第６ｂ図のキヤツシユ・アルゴリズムが
実行される。通過書込動作を表示するため、通過
書込及び書込動作フラグがセツトされ、バイパ
ス・フアクタが超過されたかどうかを決定するた
め、リクエストが検査される。もし超過されてい
れば、データがキヤツシユ・メモリを通らないで
直接にシステムからデイスク・フアイルへ転送さ
れるべきことを示すため、通過書込フラグがリセ
ツトされる。次に、読出動作と関連して説明した
のと同じようにして、デイレクトリイ探索が実行
される。第６ａ図に示されるフローチヤートにお
いて、動作８４は通過書込でない書込動作につい
てスキツプされる。何故ならば、ホスト・プロセ
ツサはキヤツシユへ書込まないからである。キヤ
ツシユ・メモリへ書込む必要がある通過書込動作
については、キヤツシユはホスト・プロセツサの
メイン・ストレージとインターフエイスしなけれ
ばならず、動作８４はスキツプされてはならな
い。 ホスト・プロセツサが書込みたいデータをキヤ
ツシユが含んでいないものと仮定し、バイパス・
フアクタが超過され、かつ通過書込フラグがリセ
ツトされているものと仮定すると、プログラム通
路８５，７５，８６が第６ｂ図のキヤツシユ・ア
ルゴリズムの終りに至るまでとられる。ここで再
び第５図を参照すると、通過書込みでない書込動
作については、マイクロプロセツサはホスト・プ
ロセツサからデイスクへデータを直接に転送する
のに必要な動作を設定し、データ転送動作が実行
され、割込リクエストによつてコントローラ動作
が終了する。 書込ミスが生じ、バイパス・フアクタが超過さ
れていなければ、通過書込動作が実行されるべき
であり、第６ｂ図の通路Ｄがとられる。もし書込
まれるべきデータが完全なブロツクより小さけれ
ば、ホスト・プロセツサからデイスクへデータを
直接に転送する動作が設定される。もし書込まれ
るべきデータが完全なブロツクであれば、動作５
３でページがキヤツシユへ加えられ、システムか
らキヤツシユへの転送動作が設定され、第６ｃ図
の通路Ｆに沿つてキヤツシユからデイスクへの動
作が実行される。 もし書込ヒツトが生じており（即ち、書込まれ
るべきデイスク・メモリ・ロケーシヨンの少なく
とも１つのロケーシヨンからのデータが、キヤツ
シユ・メモリ中に現在記憶されており）、かつバ
イパス・フアクタが超過されていれば、第６ｂ図
でプログラム通路８７がとられ、書込まれつつあ
るデイスク・メモリ・ロケーシヨンに対応するデ
イレクトリイ及びLRUテーブルのページが削除
される。 バイパス・フアクタが超過されておらず、従つ
て通過書込動作が依然として有効であれば、
LRUテーブルが第６ｂ図の動作８２で更新され、
第６ｃ図の通路Ｆでキヤツシユからデイスクへの
転送動作が設定される。 もし数ブロツクのデータが書込まれ、バイパ
ス・フアクタが超過されていなければ、ブロツク
全体のミスに関するシステムからキヤツシユへの
動作が第６ｂ図で設定される。ヒツト・ブロツク
に対しては、キヤツシユへ書込むことによつて、
既にキヤツシユへ記憶されたデータを更新するこ
とが必要である。これは、最後のブロツクを除く
全てのブロツクに関して、第６ｃ図の通路Ｈで達
成される。もし書込まれるべき最後のデータ・ブ
ロツクがヒツトであれば、システムからキヤツシ
ユへの動作は第６ｃ図の通路５′で設定される。 書込動作のためにキヤツシユ・アルゴリズムを
終了した後、マイクロプロセツサは第５図のチヤ
ートに従つて動作を継続する。もしバイパス・フ
アクタが超過されていなければ、全ての必要なデ
ータ転送動作がキヤツシユ・アルゴリズムの中で
設定されており、単にそれを実行するだけでよ
い。しかし、キヤツシユ内容が更新されてしまう
まで、データはキヤツシユからデイスクへ転送さ
れることができない。従つて、システムからキヤ
ツシユへの動作が先ず実行され、次にデイスク・
フアイルを準備してデータを受取らせるためフア
イル動作が発生され、最後にキヤツシユからデイ
スクへの動作及びシステムからデイスクへの動作
が実行される。 もしバイパス・フアクタが超過されており、通
過書込フラグがリセツトされていれば、システム
からデイスクへの動作は設定されない。この動作
は第５図の動作８８でなされなければならない。
その次に、フアイル動作の発生及び転送動作の実
行が続く。 第１４ａ図乃至第１４ｅ図は第１図に示される
コントローラ２０の詳細なブロツク図である。コ
ントローラの動作はサイクル・スチール読出動作
に関して説明される。ホスト・プロセツサによる
データのリクエストは、コントローラ２０によつ
て自動的に処理される。 このコントローラの動作の大部分は、前記米国
特許第4038642号及び第4246637号に説明されるコ
ントローラの動作と同じであり、従つて詳細に説
明しない。簡単に説明すれば、ホスト・プロセツ
サはコントローラ２０へメイン・ストレージ１１
からの即値装置制御ブロツク（IDCB）を送る。
IDCBは、アドレス・バス１００（第１４ｃ図）
を介して送られるＩ／Ｏ指令コード及びＩ／Ｏ装
置アドレスを含む（第１のワード）。検索される
べきデータを指定する第２のワードが、チヤネ
ル・データ・バス２３（第１４ｃ図）を介して同
時に送出される。装置アドレス比較器１０２はバ
ス１００上のアドレスを検査し、もしそれがＩ／
Ｏコントローラ２０によつてサービスを受ける装
置に対応したアドレス・ジヤンパ１０４の１つに
一致すると、ロード・パルスが指令レジスタ１０
６へ送られ、受取られたアドレスを該レジスタへ
記憶させる。更に、この出力信号はロード・パル
スとして装置制御ブロツク（DCB）レジスタ１
０８（第１４ｃ図）へ与えられる。それは、該レ
ジスタへバス２３からのデータ・ワードを記憶せ
るためである。更に、他の出力がANDゲート１
１２（第１４ａ図）の１つの入力へ行く線１１０
へ与えられる。指令及び装置アドレスがバス１０
０へ置かれてから暫くして、ホスト・プロセツサ
はアドレス・ゲート線１１４を能動化する。比較
器１０２から出力が線１１０へ与えられた時、ア
ドレス・ゲート・リターン線１１６が能動化され
て、アドレス一致が生じたことをホスト・プロセ
ツサへ伝える。それに応答して、ホスト・プロセ
ツサは線１１８（第１４ａ図）へデータ・ストロ
ーブ・パルスを送出する。 この最初の選択シーケンス中、ホスト・プロセ
ツサは、条件コード・イン・バス１２０（第１４
ａ図）上に存在する条件コードを検査することに
よつて、コントローラ２０の状況を検査する。上
記条件コードはレジスタ１２２から与えられる。
レジスタ１２２の内容は、コントローラ２０の現
在の状況を反映するように、マイクロプロセツサ
によつて制御される。 前記のステツプが終つた後に、ホスト・プロセ
ツサはアドレス・ゲート線１１４を非能動化す
る。アドレス・ゲート線１１４は、AND回路１
１２を介してアドレス・ゲート・リターン線１１
６を非能動化する。これによつて、初期選択シー
ケンスは完了する。その後暫くして、指令レジス
タ１０６（第１４ｃ図）にある指令、及びレジス
タ１０８にあるデータ・ワードが、データ・バ
ス・イン・バスを介してマイクロプロセツサへ転
送される。マイクロプロセツサは指令を検査し、
コントローラ２０の現在の状況に従つて、次に何
をなすべきかを決定する。 先ず第１に、コントローラは、ホスト・プロセ
ツサから一時に１つのDCBワードをサイクル・
スチールすることによつて、ホスト・プロセツサ
からDCBワードをフエツチする。これを達成す
るために、マイクロプロセツサはレジスタ１０８
からアドレス・カウンタ１５０（第１４ｃ図）へ
DCBアドレスをロードする。DCBアドレスは、
アドレス・カウンタ１５０からサイクル・スチー
ル・アドレス・レジスタ１５２へ転送される。
DCBは典型的には８個のワード（16バイト）を
含むので、マイクロプロセツサは16のカウントを
バイト・カウンタ１５３へセツトする。 ANDゲート１５７，１５８，１５９（第１４
ｄ図）へ与えられた入力信号に応答して、ラツチ
１５５の出力にサイクル・スチール・リクエスト
信号が発生される。次に、このサイクル・スチー
ル・リクエスト信号はANDゲート１６０（第１
４ａ図）へ与えられる。ラツチ１６２（第１４ａ
図）からのサイクル・スチール・ポール捕捉信号
又は極性保持回路１６３からの出力が不在の時、
ANDゲート１６０はサイクル・スチール・リク
エスト・イン信号をホスト・プロセツサへ与え
る。 サイクル・スチール・リクエスト・イン信号に
応答して、ホスト・プロセツサはバス１６４（第
１４ａ図）上にポール識別信号を送出する。ポー
ル識別信号はANDゲート１６６をセツトする。
サイクル・スチール・リクエスト信号が存在する
ものと仮定すると、極性保持回路１６８（第１４
ａ図）は、ORゲート１７０及び極性保持回路１
７２を介してANDゲート１７４の入力へ出力を
与える。ANDゲート１７４はポール・リターン
信号をホスト・プロセツサへ送る。ポール・リタ
ーン信号に応答して、ホスト・プロセツサは線１
７５（第１４ａ図）上にサービス・ゲート信号を
送出する。サービス・ゲート信号は、極性保持回
路１６３（第１４ｂ図）の出力にサイクル・スチ
ール・サービス・ゲート捕捉信号を発生する。こ
の信号は極性保持回路１７６（第１４ｂ図）の
CD端子へ与えられる。従つて、サービス・ゲー
ト・リターン信号がORゲート１７８によつて線
１７９へ与えられる。 線１７９上のサービス・ゲート・リターン信号
を受取つた後、ホスト・プロセツサはアドレス・
バス１００を介してサイクル・スチール・アドレ
ス・レジスタ１５２からアドレスを受取る。この
アドレスは、最初の装置制御ブロツク（DCB）
ワードのアドレスである。次に、ホスト・プロセ
ツサはこのワードをフエツチし、それをチヤネ
ル・データ・バス２３上に置く。このワードはサ
イクル・スチール・データ・レジスタ３０へロー
ドされる。この時点で、マイクロプロセツサは２
のカウントだけアドレス・カウンタ１５０を増加
させ、２のカウントだけバイト・カウンタ１５３
を減少させる。カウンタ１５０にある新しいアド
レスは、次のサイクル・スチール・リクエスト・
イン信号をコントローラに準備させるため、レジ
スタ１５２へ転送される。次に、サイクル・スチ
ール・データ・レジスタ３０にあるDCBワード
がマイクロプロセツサへ転送され、そこに記憶さ
れる。そして次のDCBワードを獲得するシーケ
ンスを開始するため、新しいサイクル・スチー
ル・リクエスト・イン信号がANDゲート１６０
（第１４ａ図）によつて送出される。この手順は、
全てのDCBワードがマイクロプロセツサに記憶
されるまで継続する。全てのDCBワードが記憶
されると、バイト・カウンタ１５３の内容は０と
なり、線１８０が能動化される。 DCBワードの全てを得た後に、マイクロプロ
セツサは自動転送動作を実行するようにコントロ
ーラを設定する。最初、自動ラツチ１８２（第１
４ｂ図）が自動転送モードを表示するためセツト
され、サイクル・スチール入力モード・ラツチ１
８４（第１４ｄ図）が入力（即ち、装置読出し）
動作を表示するためセツトされる。これらラツチ
の各々からの出力は、コントローラ内の各種の制
御論理動作で使用され、サイクル・スチール入力
モード・ラツチ１８４からの出力は、サイクル・
スチール・サービス・ゲート捕捉信号の存在の下
で、ANDゲート１８６を介して線１８７上のサ
イクル入力インデイケータとしてホスト・プロセ
ツサへ与えられる。更に、マイクロプロセツサは
バイト・カウンタ１５３へ転送されるデータ・バ
イトの数を入れ、アドレス・カウンタ１５０へホ
スト・プロセツサのメイン・ストレージへ転送さ
れるデータの開始アドレスを入れる。アタツチメ
ント装置との通信は、リクエスト・アウト・シー
ケンスによつて設定される。マイクロプロセツサ
はタグ・レジスタ１９０（第１４ｂ図）へ適当な
制御情報をロードし、アタツチメント・データ・
レジスタ３２（第１４ｅ図）へ必要なデータ又は
他の情報をロードする。更に、マイクロプロセツ
サは、線１９３へアタツチメント・データ・レジ
スタ満杯信号を与えるため、ラツチ１９２（第１
４ｄ図）をセツトし、ラツチ１８４（第１４ｄ
図）を「出力モード」状態へリセツトし、リクエ
スト・アウト信号を与えるため、リクエスト・ア
ウト・フリツプ・フロツプ１９５（第１４ｂ図）
がセツトされる。 リクエスト・アウト信号に応答して、装置コン
トロール１４（第１図）は承認リクエスト・アウ
ト線１９６を能動化する。線１９６上の信号は
ORゲート１９７を介してANDゲート１９８へ与
えられる。ゲート１９８に対する他の入力はオン
であるから、ストローブ・アウト・フリツプ・フ
ロツプ２００がセツトされ、ストローブ・アウト
信号が装置コントロール１４へ送られる。このス
トローブ・アウト・パルスに応答して、装置コン
トロール１４は、それぞれタグ・バス２０２及び
アタツチメント・データ・バス２５を介して、タ
グ・レジスタ１９０及びアタツチメント・デー
タ・レジスタ３２から情報を受取る。更に、スト
ロープ・アウト信号はリクエスト・アウト・フリ
ツプ・フロツプ１９５をリセツトする。 装置コントロール１４へ与えられた情報は、そ
れを能動化して、デイスク１６の１つとの間で、
必要なデータ転送動作を実行せしめる。装置コン
トロール１４がデータ転送の準備を完了する度
に、それはリクエスト・イン線２０４（第１４ｄ
図）を能動化する。ANDゲート２０６は、線２
０４上の信号に応答して、ANDゲート２０７又
は２０８のいずれかが出力を与える時、承認リク
エスト・イン信号を発生する。出力転送について
は、ANDゲート２０７（第１４ｂ図）は、アタ
ツチメント・データ・レジスタ３２（第１４ｅ
図）が満杯でありかつ適当な制御信号が線２０９
上で受取られる時、出力を与える。デイスクから
データが読取られる入力転送については、AND
ゲート２０８は、アタツチメント・データ・レジ
スタが満杯であつてデータ転送の準備が完了して
おり、かつ適当な制御信号が線２１０上で受取ら
れる時、出力を与える。 線２０９及び２１０へ印加される制御信号、及
びコントローラの他の個所で使用される同様の制
御信号は、第１５ａ図及び第１５ｂ図を参照して
更に明確に理解することができる。第１５ａ図に
示されるように、コントローラは３個のデータ・
レジスタ３０，３２，４４を含み、これら３つの
レジスタの中の任意の２つの間でデータを転送す
る手段が設けられている。かくて、これらレジス
タの間で、実質的に６つのデータ通路が存在す
る。コントローラは第１５ｂ図に示される回路を
含む。この回路は、マイクロプロセツサの制御の
下で、実行されている転送の種類に従つて、制御
信号を与える。例えば、通路レジスタ２１２は通
路デコーダ２１４へ３ビツト出力を与える。通路
デコーダ２１４は、Ｉ／Ｏコントローラ回路の残
りの部分へ適当な制御信号を与える。「通路４又
は６」の如く代替的な通路制御信号を表示する論
理入力（例えば、ANDゲート２０７及び２０８
（第１４ｂ図）への入力）は、ORゲートを介し
て適当な通路デコーダ出力信号へカツプルされる
ことができる。 ここで再び第１４ａ図乃至第１４ｅ図を参照す
ると、入力モード転送の場合に、装置コントロー
ルは、線２２０へストローブ・イン信号を与える
ことによつて、承認リクエスト・イン信号に応答
する。それによつて、アタツチメント・データ・
レジスタ３２は、アタツチメント・データ・バス
２５に現われるデータ・ワードをロードされる。
更に、このストローブ・イン信号は、ANDゲー
ト２２２及び２２４へ与えられる。それによつ
て、ラツチ１９２は、アタツチメント・データ・
レジスタが満杯であることを表示するためにセツ
トされる。 もしアタツチメント・データ・レジスタ中のワ
ードがキヤツシユに置かれるべきでなければ、コ
ントローラは米国特許第4246637号に説明されて
いるように動作する。簡単に説明すれば、AND
ゲート２２６（第１４ｅ図）へ与えられた「通路
１」信号は、サイクル・スチール・データ・レジ
スタ３０（第１４ｃ図）へ至る線２２７上にロー
ド・パルスを発生する。それによつて、レジスタ
３０は、アタツチメント・データ・レジスタによ
つてサイクル・スチール・データ・バス３１上に
置かれたデータを記憶する。更に、このロード・
パルスは、ANDゲート１５９へ１つの入力とし
て与えられる。ANDゲート１５９の出力は、サ
イクル・スチール・データ・レジスタ３０が満杯
であることを示すため、フリツプ・フロツプ２２
９をセツトする。更に、ANDゲート１５９の出
力はラツチ１５５をセツトする。それによつて、
サイクル・スチール・リクエスト・イン信号が、
再びANDゲート１６０からホスト・プロセツサ
へ与えられる。このサイクル・スチール・リクエ
スト・イン信号は信号シーケンスを開始する。そ
れによつて、ホスト・プロセツサはサイクル・ス
チール・データ・レジスタ３０からデータ・ワー
ドを受取る。次にサイクル・スチール・リクエス
ト・イン信号がオフにされ、サイクル・スチー
ル・データ・レジスタ３０が今や空であることを
表示するため、フリツプ・フロツプ２２９がリセ
ツトされる。前記のステツプは、装置コントロー
ル１４からホスト・プロセツサへ転送される各デ
ータ・ワードについて繰返される。バイト・カウ
ンタ１５３は、転送される各ワードについて２の
カウントだけ減少され、アドレス・カウンタ１５
０は、２だけ増加される。装置読出動作について
は、カウンタ１５３中の値が０に達した時、マイ
クロプロセツサは適当な割込シーケンスを開始す
る。 装置書込動作において、デイスクは典型的には
レコードの増分を書込むように設計される。ホス
ト・プロセツサから書込まれるべきバイトの数
は、レコードのバイト数より少なくてよい。この
場合、バイト・カウンタ１５３はゼロへ減少され
るが、装置コントロール１４は依然として書込動
作を完了するため多くのデータを必要とする。も
しカウンタ１５３中の値がゼロで、レジスタ３０
及びレジスタ３２が共に空であつて、書込まれる
べきデータが存在せず、他のリクエスト・イン信
号が装置コントロール１４から受取られると、
「ゼロ充填」信号がANDゲート１５２′（第１４
ｄ図）を能動化するように与えられる。それによ
つて、ラツチ２３６（第１４ｄ図）がセツトさ
れ、プロセスの継続が許される。更に、ゼロ充填
信号がレジスタ３２へ与えられ、それをゼロで充
填する。これらのゼロは、レコードの終りに達し
て追加データに対するリクエストが受取られなく
なるまで、デイスクへ書込まれる。 もし装置コントロール１４からアタツチメン
ト・データ・レジスタ３２へ受取られたデータが
先ずキヤツシユ・メモリへ転送されるべきであれ
ば、動作は前述したところと同じであるが、デー
タは異つたレジスタ（即ち、キヤツシユ・デー
タ・レジスタ４４）へ転送される。この点に関し
て、「通路２」信号が第１５ｂ図の通路デコーダ
によつて与えられる。かくて、能動信号をAND
ゲート２２６（第１４ｅ図）へ与えてサイクル・
スチール・データ・レジスタ３０へロード信号を
与える代りに、デコーーダは能動信号をANDゲ
ート２３０へ与える。それによつて、キヤツシ
ユ・データ・レジスタ４４は、アタツチメント・
データ・レジスタ３２からバス３１へ送出された
データをロードされる。デイスクからキヤツシユ
への転送を実行する場合、マイクロプロセツサは
キヤツシユ・アクチブ・ラツチ２３２（第１４ｅ
図）をセツトする。アタツチメント・データ・レ
ジスタ３２は現在満杯であり、キヤツシユ・デー
タ・レジスタ４４は空であるから、「通路２」信
号によりロード信号がキヤツシユ・データ・レジ
スタ４４へ与えられ、同時にANDゲート２３４
を介して、ロード・レジスタ・ラツチ２３６がセ
ツトされる。それによつて、ラツチ１９２は
ANDゲート２３８を介してリセツトされ、キヤ
ツシユ・メモリ・レジスタ満杯ラツチ２４０が
ANDゲート２４２を介してセツトされる。ラツ
チ１９２のリセツトはANDゲート２０８（第１
４ｂ図）を介してフリツプ・フロツプ２０６をリ
セツトする。それによつて、承認リクエスト・イ
ン信号が終了し、コントローラはレジスタ３２が
今や次のワードを受取る準備を完了していること
を知らされる。 第１６図は、後述するリクエスト論理２５６
（第１４ｅ図）及びANDゲート２９０（第１４ｅ
図）のための結合論理回路のブロツク図である。
論理回路は反転ANDゲート２５１ａ―２５１ｃ
と、２５３，２５３ａ及び２５３ｂのような
NOTゲートと、否定ORゲート２５５とを含む。
反転ANDゲート２５１ａ―２５１ｃの各々は、
全ての入力が高である時低レベル出力を与え、他
の場合には高出力を与える。NOTゲート２５３
ａ及び２５３ｂはその入力を反転し、否定ORゲ
ート２５５は、その入力のいずれかが低の時高レ
ベル出力を与える。最初のデータ・ワードがキヤ
ツシユ・データ・レジスタ４４（第１４ｅ図）に
記憶され、線２５０，２５２，２５４の全てがア
クチプになると、リクエスト論理２５６はゲート
２５５から出力信号を与え、書込サイクル・ラツ
チ２５７をセツトする。それによつてリング・カ
ウンタ２５８が能動化される。リング・カウンタ
２５８は、通常の３ステージ６状態、又は６ステ
ージ12状態の歩行カウンタであつてよい。 マイクロプロセツサは、転送されつつあるデー
タのために、キヤツシユ・メモリ中の開始アドレ
スを、アドレス・カウンタ２６０（第１４ｅ図）
へロードしており、転送されつつあるバイトの数
を、特殊バイト・カウンタ２６２へロードしてい
る。キヤツシユ中で利用可能なページは、必ずし
も連続しているとは限らないので、いくつかの動
作が必要となるかも知れない。例えば、もし10個
のレコードが転送される必要があり、キヤツシユ
中８レコードを含むページの８番目のレコードか
ら記憶されている時、転送は３つの別々の動作で
実行される。最初の転送はレコード１を転送し、
第２の転送はレコード２―９を完全なキヤツシ
ユ・ページへ転送し、第３の転送はレコード１０
を第３のキヤツシユ・ページへ転送する。かく
て、第１及び第３の動作では、特殊バイト・カウ
ンタ２６２は２５６バイトでセツトされ、第２動
作では、２０４８バイトへセツトされる。 デコーダ２６４（第１４ｅ図）は、リング・カ
ウンタ２５８からの出力と、サイクルの種類を示
す線２５９上の信号とを受取り、図示されるよう
な制御信号を与える。これらの制御信号として
は、行／列デコーダ２６６の出力を能動化するた
めの行時間能動信号、バス２６８上のデータをバ
ス２６９及び２７０によつて指定されたキヤツシ
ユ・メモリ２８２へロードするためのストローブ
信号、アドレス・カウンタ２６０を増加させる信
号、特殊バイト・カウンタ２６２を減少させる信
号がある。デコーダ２６４は、書込ラツチ２５７
をリセツトするため、そのラツチへサイクル終了
信号を送る。 アタツチメント・データ・レジスタ３２中のワ
ードがキヤツシユ・データ・レジスタ４４へ転送
されると、そのワードは前述したようにしてキヤ
ツシユ・メモリへ転送されるので、新しいワード
が装置コントロール１４からアタツチメント・デ
ータ・レジスタ３２へ入れられる。アタツチメン
ト・データ・レジスタ満杯ラツチ１９２が再びセ
ツトされ、「通路２」信号が与えられ、キヤツシ
ユ書込サイクルの終りにラツチ２４０がリセツト
されると、ANDゲート２３４が能動化され、ラ
ツチ２３６がセツトされる。かくて、再びキヤツ
シユ・データ・レジスタ４４やロードされると共
に、ラツチ２４０がセツトされる。これは、線２
５４上のリクエスト論理信号を高にし、他の書込
サイクルを開始する。このプロセスは、リクエス
トされたデータの全てが転送されるまで継続す
る。 データ処理システムでキヤツシユ・メモリを使
用する場合、キヤツシユ・メモリ動作は「透明」
であることが望ましい。即ち、データがキヤツシ
ユ・メモリからホスト・プロセツサへ転送される
時、その転送は、デイスクから転送と全く同じも
のであることが望ましい。また、デイスクへの書
込みと同じようにキヤツシユ・メモリへ書込むこ
とが望ましく、デイスク・フアイルへ直接書込む
場合と同じようなゼロ充填モードの動作が実行さ
れねばならない。第１４ｅ図及び第１６図に示さ
れるように、特殊バイト・カウンタ２６２がゼロ
値へ達していても２５６バイト・レコードの終り
に達していない場合、線４００及び４０２上の信
号レベルは共に高になる。このような状態の下で
は、反転ANDゲート２５１ａ及び２５１ｂから
の出力は高となるが、反転ANDゲート２５１ｃ
への全ての入力は高となるのでその出力は低とな
る。かくて、否定ORゲート２５５の出力に、書
込サイクル・リクエスト信号が生じ、ゼロ充填動
作を実行するため、低レベルのゼロ充填モード信
号がキヤツシユ・データ・レジスタ４４へ与えら
れる。かくて、書込サイクルは、レコードの終り
である２５６バイト境界に達するまで、ゼロをキ
ヤツシユ・メモリへ書き続ける。レコードの終り
に達すると、線４０２上の信号は低レベルとな
り、読出サイクル・リクエスト及び書込サイク
ル・リクエストのいずれもリクエスト論理から与
えられない。 リクエストされたデータを、キヤツシユ・メモ
リからサイクル・スチール・データ・レジスタ３
０へ転送するため（データは、レジスタ３０から
ホスト・プロセツサへ通常の態様で転送されるこ
とができる）、特殊バイト・カウンタ２６２及び
アドレス・カウンタ２６０が、再び転送されるべ
きバイトの数及びキヤツシユの開始アドレスへセ
ツトされ、通路３のみが使用されているから、低
論理信号が線２５２へ与えられる。リング・カウ
ンタが走る時、デコーダ２６４は前に与えられた
出力を同じ順序で与える。例外として、ストロー
プ書込パルスは与えられないので、キヤツシユ・
メモリ２８２は、バス２６８を介してアドレスさ
れた内容をキヤツシユ・データ・レジスタ４４へ
与える。最後の信号であつて、これはANDゲー
ト２８４及び２８８へ与えられて、レジスタ４４
へキヤツシユ・メモリ２８２からデータを受取ら
せ、かつラツチ２４０をセツトする。それは、レ
ジスタ４４が今や満杯であり、レジスタ３０が空
であることを表示するためである。ラツチ２４０
の出力はANDゲート２８９（第１４ｄ図）を介
してレジスタ２３６をセツトし、かくてANDゲ
ート２２６（第１４ｅ図）を能動化する。AND
ゲート２２６はロード・パルスをレジスタ３０へ
与える。それは、レジスタ４４からレジスタ３０
へデータをロードするためである。次にホスト・
プロセツサは、通常の態様で、サイクル・スチー
ル・データ・レジスタ３０の内容を受取る。 上記の手順は、全てのデータが転送されるまで
繰返される。全てのデータが転送された時点で、
割込シーケンスが開始される。 具体的に説明すると、動作が完了した時、マイ
クロプロセツサは割込識別ワードを識別レジスタ
３００へロードし、適当な条件コード（例えば、
「装置終了」コード）を条件コード・レジスタ１
２２へロードする。ホスト・プロセツサから準備
指令が発生される間、割込優先レベル信号がコン
トローラ２０へ割当てられ、かつレベル準備レジ
スタ３０６へ記憶される。線３０８上に信号が発
生した時、デコーダ３１０はリクエスト・イン・
バス３１２にある複数の線の１本を付勢する。 ホスト・プロセツサは、バス１６４へポール識
別信号を送出することによつて、リクエスト・イ
ン・バス３１２上の信号に応答する。ポール識別
信号は、比較器３１６の中で、レベル準備レジス
タ３０６に記憶されたＩ／Ｏコントローラ優先順
位レベルと比較される。一致が検出されると、双
安定極性保持回路３１８のCD端子へ出力が印加
される。回路３１８は、ORゲート１７０を介し
て他の極性保持回路１７２へ出力を与える。極性
保持回路１７２の出力は、ANDゲート１７４の
１つの入力へ与えられる。ANDゲート１７４は
ポール・リターン信号をホスト・プロセツサへ送
り、ホスト・プロセツサは、線１７５へサービ
ス・ゲート信号を送出することによつて応答す
る。サービス・ゲート信号は極性保持回路３２８
へ与られる。極性保持回路３２８の出力は、ホス
ト・プロセツサへ線１７９を介してサービス・ゲ
ート・リターン信号を戻すため、ORゲート１７
８を能動化する。同時に、割込識別レジスタ３０
０（第１４ｃ図）の内容がデータ・バス２３上に
置かれる。サービス・ゲート・リターン信号は、
ホスト・プロセツサへ、情報がバス２３及びバス
１２０上に存在することを知らせる。ホスト・プ
ロセツサは、この情報を受取つて記憶すると共
に、初期接続手順を終了させるため、線１７５
（第１４ａ図）を非能動化する。この割込処理の
詳細な説明は、前記米国特許第4246637号及び第
4038642号でなされている。 これまで説明しなかつたが、第１４ａ図乃至第
１４ｅ図に示される各種の論理コンポーネント
（例えばANDゲート２２２（第１４ｄ図））は、
パリテイ（Ｐ）検査入力を有するものとして示さ
れている。当技術分野で周知の如く、各種のバス
上のデータは、一般的にパリテイ・ビツトを設け
られている。各種のデータ転送の間にパリテイ検
査（例えば第１４ｅ図の４０３）が実行される。
パリテイ検査でエラーが生じると、リトライが実
行される。 これまで説明したようにキヤツシユ・メモリを
使用するＩ／Ｏコントローラは、ホスト・プロセ
ツサ及び１つ又はそれ以上のアタツチメント装置
（例えばデイスク）を有するデータ処理システム
の動作時間を顕著に改善する。何故ならば、それ
は、ホスト・プロセツサがアタツチメント装置に
アクセスする回数を減少させるからである。更
に、デイレクトリイ・テーブルの使用により、全
てのデータ・ブロツクがホーム・ポジシヨンにリ
ストされるか、又はホーム・ポジシヨンから始ま
る衝突リスト中に含ませられるので、リクエスト
されたデータ・ブロツクが現在キヤツシユ・メモ
リに記憶されているかどうかの決定が非常に容易
になる。従つて効率が改善される。リクエストさ
れたレコードがデータ・ブロツクの後方部分で生
じた時、後続するデータ・ブロツクをキヤツシユ
へ予め転送する「プレステージング」動作によつ
て、キヤツシユ・メモリの効率が更に改善され
る。 １つの変更例として、キヤツシユ・メモリそれ
自体は、Ｉ／Ｏコントローラの中へ物理的に設け
られる必要はなく、第１図の装置コントロール１
４の中に設けられてもよい。

【図面の簡単な説明】

第１図はキヤツシユ・メモリを含むデータ処理
システムのブロツク図、第２ａ図及び第２ｂ図は
第１図のRAMに含まれるデイレクトリイ・テー
ブルとLRUテーブルの説明図、第３図はリクエ
ストされたデータ・ブロツクのためにデイレクト
リイ・テーブルを探索する動作シーケンスの流れ
図、第４ａ図はリクエストされたデータ・ブロツ
クがキヤツシユ・メモリ中にない場合のデイレク
トリイ・テーブルの探索を示す説明図、第４ｂ図
はリクエストされたデータ・ブロツクがキヤツシ
ユ・メモリ中にある場合のデイレクトリイ・テー
ブルの探索を示す説明図、第５図はマイクロプロ
セツサによつてＩ／Ｏコントローラの中でとられ
る全体的動作シーケンスを示す流れ図、第６ａ
図、第６ｂ図、第６ｃ図は第５図に示されたキヤ
ツシユ・アルゴリズムを詳細に示す流れ図、第７
図はブロツクをキヤツシユへ加えるステツプを詳
細に示す流れ図、第８図は現ハツシユ・ナンバー
を使用してブロツクをキヤツシユへ加えるステツ
プを詳細に示す流れ図、第９ａ図及び第９ｂ図は
デイレクトリイ・テーブルに維持された「自由連
鎖」の管理を説明する図、第１０ａ図、第１０ｂ
図、第１０ｃ図、第１０ｄ図は第７図の流れ図で
実行される各種のキヤツシユ・メモリ動作を示す
図、第１１図はデイレクトリイ・テーブルで衝突
する最初の自由エントリイを交換するステツプを
詳細に示す流れ図、第１２ａ図、第１２ｂ図、第
１２ｃ図は本発明のシステムで実行されるプレス
テージング（プリフエツチ）動作の説明図、第１
３図はプリフエツチ計算を実行するステツプを詳
細に説明する流れ図、第１４図は第１４ａ図乃至
第１４ｅ図の配置を示す図、第１４ａ図、第１４
ｂ図、第１４ｃ図、第１４ｄ図、第１４ｅ図はキ
ヤツシユ・メモリを利用するＩ／Ｏコントローラ
のブロツク図、第１５ａ図はＩ／Ｏコントローラ
の中の各種のデータ転送通路を示すブロツク図、
第１５ｂ図はＩ／Ｏコントローラに含まれる各種
の論理エレメントへ制御信号を与える通路制御回
路を示す図、第１６図は第１４ｅ図に示されるリ
クエスト論理２５６及びANDゲート２９０の結
合回路の詳細を示す図である。 １０……ホスト・プロセツサ、１１……メイ
ン・ストレージ、１４……装置コントロール、１
６……デイスク、１８……鍵盤表示端末、３０…
…サイクル・スチール・データ・レジスタ、３２
……装置データ・レジスタ、３３……マイクロプ
ロセツサ、３６……高速コントロール、３７，３
８……初期接続論理、４２……キヤツシユ・メモ
リ、４４……キヤツシユ・データ・レジスタ、４
７……ランダム・アクセス・メモリ。

Claims (1)

【特許請求の範囲】
1. １ それぞれがｎ個（ｎは正の整数）のデータ・
   レコードを含む複数のデータ・ブロツクを記憶す
   るメモリ・ユニツトと、該メモリ・ユニツトに記
   憶されたデータの一部を記憶するキヤツシユ・メ
   モリと、上記メモリ・ユニツトに記憶されたデー
   タをリクエストするホスト・プロセツサと、リク
   エストされたデータが上記キヤツシユ・メモリに
   記憶されているとき該データを上記キヤツシユ・
   メモリから上記ホスト・プロセツサへ転送しリク
   エストされたデータが上記キヤツシユ・メモリに
   記憶されていないとき該データを上記メモリ・ユ
   ニツトから上記ホスト・プロセツサへ転送する制
   御装置とを具備し、該制御装置は上記ホスト・プ
   ロセツサによつてリクエストされたデータ・レコ
   ードを含むデータ・ブロツクが上記キヤツシユ・
   メモリになく且つ該リクエストされたデータ・レ
   コードが該データ・ブロツクにおいて所定の位置
   よりも後にあつた時に該データ・ブロツクの他に
   後続の１つ又は２つのデータ・ブロツクを上記メ
   モリ・ユニツトから上記キヤツシユ・メモリへ転
   送することを特徴とするデータ処理システム。