JPS6015760A - Ｄａｓｄキヤツシユの情報をステ−ジングするための方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、キャッシュの管理に係り、更に具体的に云え
ば、ＤＡＳＤキャッシュに於（づる固定ブロック・エク
ステン１〜を置換えるためのディレクトリによる管理方
法に係る。

［従来技術］ 従来、ページ（固定ブロック）の移動を制御し、記憶階
層の論理アドレス空間と物理アドレス空間との間を動的
に関連づけるために、機械により実行可能なページ又は
他の固定ブロックの置換え方法が用いられている。それ
に関連して、ＬＵＲ（ｌｅａｓｔ　ｒｅｃｅｎｔｌｙ　
ｕｓｅｄ）法又はＭ　ＲＵ　（ｍｏｓｔｒｅｃｅｎｔｌ
ｙ　ｕｓｅｄ）法によるページ置換え方法を用いている
階層記憶システムは、要求時ページングであれば、単一
レベルの記憶の場合よりも相当に少ない数のページ（固
定ブロック）しか必要としない。キャッシュ（ディレク
トリにより管理されるバッファ・ステージ）の性能は、
ヒツト／ミス率によって特性づけられる。“ヒツト″と
は、要求しているＣＰＵの実行可能なプロセスにより生
じたキャッシュへの読取の参照が、所望のデータ項目を
、低速度の補助記憶装置でなく、高速度のキャッシュに
見出すことを意見する。書込の参照に関しての“ヒツト
”は、上記ＣＰＵの実行可能なプロセスが、キャッシュ
管理機構により、重ね書きすべき対応する位置を、部分
的にしか充だされでいないバッファに見出したときに成
される。

これに関して、パミス″は、読取りの参照に於てデータ
がキャッシュに於て得られない場合、又は書込の参照に
於て空間を設けるために成るデータがキャッシュからデ
ステージングされねばならない場合に登録される。

小さい高速度のキャッシュと、より大きいがより低速度
の補助記憶装置との間において、データがデステージン
グ又はステージングされねばならない場合には、ステー
ジングのアルゴリズムが必要とさオシる。ＬＲＵ又はＭ
ＲＵの如き、一般に用いられているアルゴリズムは、成
るＣＰＵの実行可能なプロセスにより将来恐らく参照さ
れるであろう項目を、キャッシュ・インベン１−り中に
維持する。参照された項目を含んでいないキャッシュ及
び完全に充たされているキャッシュは、そのデータ要素
の１つが要求されている項目により置換えられるように
、上記データ要素の１つを移動させねばならない。従っ
て、システムは、長い間余照されなかった項目は将来も
参照されそうもないという仮定に基づいて、ＬＲＵ項目
を置換えようとする。

ディスク・キャッシュは、ディスク・アドレス空間内容
の一部を保持するために用いられるキャッシュ即ちバッ
ファである。それは、記憶サブシステム内に於けるその
物理的位置、及びチャネル・コマンド・ワードに応答す
ることにより、ＣＰＵキャッシュと異なっている。

動作に於て、成るＣＰＵの実行プロセスが、そのＣＰＵ
キャッシュ又は主記憶装置内に記憶されていない情報を
参照するとき、その参照はＣＰＵの外部の記憶サブシス
テムに対して行われる。例えば米国特許第３７２５８６
４号及び第４２０７６０９号の明細書の如き従来技術は
、ＣＰＵへの及びＣＰＵからのデータの転送並びに記憶
装置のアクセス位置について記載している。そのような
システムは、チャネルを含む物理的な径路接続を用いて
おり、制御装置が一方の側で上記チャネルと同期的に通
信し、他方の側で選択された装置と通信する。上記ＣＰ
Ｕのオペレーティング・システムは、入出力開始命令に
よって、転送を開始させる。これは、制御を、一連のチ
ャネル・コマンド・ワード（ＣＣＷ）に引渡すことにな
る。チャネル・コマンド・ワードのシーケンス即ちチェ
インは、記憶装置を選択及びアクセスし、インターフェ
ースを介してデータを移動させるために、ＣＰＵからチ
ャネルを経て制御装置へ送られる７４−記の両特許明細
吉：は又、ＣＰＵと装置どを関連づける径路を独立させ
る、適応性を有するチャネルの切断及び再接続について
も記載している。

連想アクセス・メモリ又はランダム・アクセス・メモリ
の形のキャッシュはナノ秒のアクセス時間を有するが、
ＤＡＳＤはミリ秒のアクセス時間を有する。ＬＲＵ／Ｍ
ＲＵ＠により管理されるキャッシュをＤＡＳＤ記憶制御
装置内に配置することにより、ＣＣＷの参照の高いヒラ
１へ串がスルーブツトを相当に増加させることが予測さ
れる。参照の多くがマイクロ秒で応答され、少数の参照
だけがＤＡＳＤからキャッシュへのステーシンクのため
にミリ秒を必要とする。

Ｄ、ＡＳＤキャッシュの今日の設泪に於ては、キャッシ
ュの“ミス”が生じたとき、その参照によつて必要とさ
れたＤＡＳＤのトラック上に記憶されたレコードと、同
一トランク上に於て上記レコードに続く全てのレコード
とが、上記キャッシュにステージングされる。これに関
して、キャッシュ内に於けるデータ管理の従来の単位は
、ＤＡＳＤのトランクである。これは、ＤＡＳＤの各ト
ラックが、異なる寸法のレコードを含む場合でも、同一
の寸法を有しているので、便利である。

当技術分野に関連する他の従来技術には米国特許第３９
３８０９７号及び第３５４４５２９号の明、？［１１書
、日本特願昭５８−３９３２１号明細書、並びに２８　
Ｉ　Ｅ　Ｅ　Ｅ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎＣｏ
ｍｐｕｔｅｒｓ、１９７９年２月、第１３３頁乃至第１
４１頁に於けるＥａｓｔｏｎ等によるυｓｅ　ＢｉｔＳ
ｃａｎｎｉｎｇ　ｉｎ　Ｒｅｐｌａｃｅｍｅｎｔ　Ｄｅ
ｃｉｓｉｏｎｓ”　と題する論文等がある。ＣＰＵキャ
ッシュについては、Ｃｏｍｐｕｔｉｎｇ　５ｕｒｖｅｙ
ｓ、第１４巻、第３号、１９８２年９月、第４７３頁乃
至第５３０頁を参照されたい。

［発明が解決しようとする問題点］ 本発明の目的は、記憶ザブシステムを参照するＣＰＵプ
ロセス（チャネル・プログラム）の実行速度を増し、階
層記憶システムのステージ間に於けるデータの転送を相
当に減少させることてあり、更に具体的に云えば、キャ
ッシュに於けるｎｆ変長レコードの管理の複雑さを除い
て、Ｄ　Ａ　ｌ）　ＳとＩ）ＡＳＤキャッシュとの間に
於けるデータの転送を減少させることである。

［問題点を解決するための手段］ 本発明は、各ブロックが少くとも１つの可変長レコード
に亘っているか又はそれ自体が、！ｌ、　−の＋＋Ｊ変
長レコードに亘る幾つかのブロックの１っである。ディ
レクトリにより管理されるＤΔＳ　Ｄキャッシュに於け
る情報の固定ブロック・エクステントを置換えるための
、ＣＰＵにより実行可能な方法を提供する。この方法は
、キャッシュにおいて得られないレコード（ミス・レコ
ード）を参照することにより呼出される。この方法のス
テップは、ＤＡＳＤの参照トラックに於て、ミス・レコ
ードから始まって、固定ブロックに亘るが、該トラック
の端部に達するか、又はキャッシュに既に存在するレコ
ードに遭遇するかする迄続くし、コードを上記キャッシ
ュにブロッキングしてステージングすることを含む。こ
れは、込の条件に従って行われる。即ち、（８）上記ミ
ス・レコードがブロック・エクステントと等しいか又は
それよりも小さい場合には、上記キャッシュに既にステ
ージングされているレコードが上記ブロックにあるか否
かを確認することが必要である。上記ブロックにおける
最初のすでにステージソゲされているレコード及び上記
ブロックにおいて上記ステージングされているレコード
に続く全てのレコードが、−１が生じた場合に、上記ブ
ロックから削除される６又、（ｂ）上記ミス・レコード
がブロック・エクステントよりも大きい場合には、上記
キャッシュ内の最近用いられていない最初のに個のブロ
ックが割振らねて、上記のに個のブロックのレコードが
ステージングされる。

前述の米国特許第３９３８０９７号明細書は、キャッシ
ュへの固定ブロックの転送のステージングについて記載
しているが、二重レコードの問題及び可変長のレコード
についても、又複数ブロック１こ亘るレコードのための
連続的空間の割振りについても、何ら言及していない。

前述の米国特許第３５４１５２９号明細書は、主記憶装
置に於て記憶のブロックを選択するだめの方法について
記載している。転送されているデータのブロックは、固
定の長さ及び範囲を有している。それらのブロックは、
重複していない記憶の区画を形成しているので、二重の
記憶は生しなし）６ 前述＋７）８本特願昭５８−３９３２１号明ｌｌｌ１ｌ
　ｆ！Ｆ’は。

線形的にアドレスされるバッファ記憶装釘の非連続的ブ
ロック中に可変長レコードを書込むことについて記載し
ている。本発明の方法に於るキャッシュの場合の如く、
ディレクトリにより管理されていないので、キャッシュ
における二重レコー１へを管理するための手段は何ら設
けられていない。

前述のＥａｓｔｏｎ等による論文は、本発明の方法にお
いて、キャッシュにに個の連続ブロックを確保するため
に、修正して用いられている、第２チヤンス・アルゴリ
ズムについて記載している。これは、レコードの長さが
ブロックの寸法を超えている場合に、バッファ空間にに
個の連続ブロックを見つけることを容易にする。このク
ロッキング・アルゴリズムにおいては、そのブロックに
おけるデータが参照されたとき、″使用”ビットがター
ン・オンされる。次に、位置表示機ｎ’ｊがブロックの
パ使用″ビットのセットをラウンド・ロビン式に循環し
、上記位置表示機栂が進むに従って、それらの″使用″
ビットをターン・″オフ″させる。

ｋ個の連続ブロックが必要とされる場合には、キャッシ
ュにおける最近用いられていないに個の連続ブロックが
選択される。

［実施例］ キャッシュ及びデータの単位 今日のキャッシュに於ては、キャッシュに於て管理され
るデータの単位は、二次記憶に於ける所定の位置でしか
始まらない。それらの位置又は境界は均一な空間を置い
て配置される。ＣＰＵキャッシュに於ては、２つの連続
する境界の間の全てのデータが１つの単位としてステー
ジングされる。これとは反対に、一般に入手される幾つ
かのディスク・キャッシュにおいては、ステージングは
、任意のレコードから始まって成る境界で終るが、又は
成る境界から始まって特定のレコードで終るかのいずれ
かである。しかしながら、割振られるデータの単位は律
゛に。

連続する境界の間の全体である。他のデーｒスク・キャ
ッシュに於ては、１つの単位全体が常にステージングさ
れる。

例えばＩＢＭ社のカラン１−・キー・データ（ＣＫ　Ｄ
）方式又は拡張カラン１−・キー・データ（ＣＫ　Ｉ）
　Ｅ　）方式の如き、ＩＤ　Ａ　Ｓ　Ｄ方式は、転送の
単位を１つ又はそれ以上のレコードに限定しており、そ
れらのレコードの長さは異なることがあるので、今日の
ディスク・キャッシュに於ける割振りの単位はディスク
のトラックであり、境界がトラックの開始点である。そ
れらのトラックは典型的には多数のレコードを含むので
、トラックのステージングに於ては、プログラムに必要
とされる個々のレコードよりも多くのデータが移動され
る。その結果、性能が低下し、ヒツト率が低下する。個
々のレコードをキャッシュにステージングすることは、
可変長レコードの管理が複雑であるために、従来広く用
いられていない。

第２図は、ＣＰＵＩがＣＰＵキャッシュ２を介して主記
憶装置４と通信する、従来の典型的な記憶階層を示して
いる。参照されたときにキャッシュ又は主記憶装置に含
ま九でいない情報について、外部記憶即ち二次記憶２７
が参照される。コンピュータにキャッシュ・メモリを付
加する、性能に関する要求は、ＣＰＵによる平均アクセ
ス時間をＣＰＵキャッシュの平均アクセス時間に出来る
限り近づけることである。これは又、ＤＡＳＤキャッシ
ュを用いる場合の目的でもある６”Ｃｏｍｐｕｔｅｒ　
Ａｒｃｈｉｉ；ｅｃｔｕｒｅ　ａｎｄＯｒｇａｎｉｚａ
ｔｉｏｎ”、　ＭｃＧｒａｗ　１ｌｉｌｌ　Ｃｏｍｐｕ
ｔｅｒＳｃｉｅｎｃｅ　５ｅｒｉｅｓ、１９７８年、第
３８５頁乃至第３８８頁に於て、１ｌａｙｅｓにより指
摘されている如く、キャッシュ及び主記憶の階層と主記
憶及び二次記憶の階層との間には幾つかの重要な相違が
存在する。それらの相違の１つは、ＣＰＵキャッシュに
必要な動作速度がソフト・ウェアのルーチンでなく、高
速度論理回「）ｉによって管理されることである。他方
、主記憶及び二次記憶のシステムは、ＣＰＵに於けるオ
ペレーティング・システム内のプログラムによって制御
される。従って、その記憶システムｌ’ｌ’Ｊ　ｍはｐ
ＨＩｉ”Ｊなる適用プロセスにも見えないが、システム
・プロセスにはみえる。これに列して、ＣＩ）　Ｕキャ
ッシュ及び主記憶は互いに見えない。

のＣＰＵがｔ用するＤ　Ａ　Ｓ　Ｄへのアクニζ内第３
図は、各々対応する制御装置２１及び２３へ、チャネル
５及びチャネル７（経路１１及び１３）並びにチャネル
７及びチャネル９（経路１５及び１７）を介して結合さ
れている、ＣＰＵＩ及びＣＰＵ３を示している。それら
の制御装置は、スイッチング手段２５を経て、ＤＡＳＤ
２７及び２９へのアクセスを共用している。

ＣＰＵとＤＡＳＤとの関係は、該ＣＰＵが入出力開始命
令を呼出したときに開始される。この命令は、ＣＰＵと
アドレスされた装置即ちＤＡＳＤとを接続させそして該
装置を用いてチャネル・プログラムを実行させるように
鋤く。入出力開始命令が呼出されると、制御が一連のチ
ャネル・コマンド・ワード（ＣＣＷ）に引渡される。こ
の一連のＣＣＷは、装置を選択及びアクセスしそしてイ
ンターフェースを介してデータを移動させるために、チ
ャネルを介して上記制御装置へ送られる。各チャネル・
プログラムは、ＣＰｔＪ又は主記憶装置に存在する一連
のオペレーションのリストより成る。ＣＣＷの制御装置
への転送及び該制御装置における実行は、ＣＰＵと該制
御装置との間に最初の接続が生じた後でなければ行われ
ない。チャネル・プロゲラ１１における各オペレーショ
ン（ＣＣＶ）について、１つ又はそれ以上の対応するオ
ペレーションが、制御装置のレベル又はＤＡＳＤのレベ
ルのいずれかにおいて、活動的な接続の間に必要とされ
る。もちろん、上記リスト即ちＣＣＷのシーケンスは、
不連続的に実行（セグメント化）可能である。

接続の最初の動作は、初期選択のシーケンスである。そ
のシーケンスは入出力開始動作で呼出され、該動作にお
いて初期の経路が装置のアドレス（仮想アドレス／実ア
ドレス）及び装置の状況（使用可能／使用中）により電
気的１１つ論理的にセラ１へ・アップさＡしる。次の活
動的な接続は、ＣａＷの転送及び実行に関するものであ
る。シークの如き制御ＣＣＷは、装置にＪ−タりる物理
的位置決め又は活動を必要とする。制御装置は、制御Ｃ
ＣＷの受信に応答して、該ＣＣＷを切断モードで実行す
ることができる。これは、制御装置が、指示されたオペ
レーションを実行する間、チャネルから切断されること
を意味する。制御装置は、チャネルに再接続される迄、
更にチャネルの活動を必要としない。例えば米国特許第
３７２５８６４号、第３３３６５８２号及び第３５６４
５０２号の明細書に記載されている如く、典型的なＩＢ
Ｍ３７０システムにおいては、制御装置は、シークＣＣ
Ｗ及びパラメータ（ターゲット・アドレス）を受信した
後、３０ミリ秒又はそれ以上の間切断される。

その３０ミリ秒は、ＤＡＳＤのアクセス・アームを所望
のシリンダのトラックに到達するようにディスパッチす
るために要する平均時間である。この″死んだ時間″′
の間、チャネル及び制御装置の両者は自由に他の接続を
設定することができる。切断モードと反対に、チャネル
と装置との間におけるデータの移動即ち転送を含む、読
取又はｉＬ）込ＣＣＷの如き、ＣＣＷは、データ”　の
転送を実行するために制御装置がチャネルに接続さ４ｔ
たままであることを必要とする。

各ＣＣＷは、主記憶装置におけるリストから得られて、
チャネルを介して制御装置に転送されねばならない、、
ＣＣＷは、制御装置において実行される。その実行の後
、終了シーケンスが生じる。ＣＣＷが装置の位置決めを
要する制御型のものであれば、制御装置はチャネルから
切断され、制御即ち装置の位置決めが完了したときに再
接続されねばならない。それから、終了シーケンスが生
じる。

共用アクセス・システムに、１１１忌１±犬士人邸」去
キャッシュ 第４図は、本発明による方法が用いられている、複数の
ＣＰＵ及び共用されているＬ’ｌ　Ａ　Ｓ　Ｉｆ）の構
成を示している。３つのＣＰＵＪ、３））、び６が、対
応するチャネルを介して、−刻の制御装置２１及び２３
に適当に交差接続されている。

ＣＰＵＩには、４つのチャネル５．７．１３及び１０が
取付けられている。ＣＰＵ３には、２つのチャネル９及
び１２が取付けられ、ＣＰＵ６には、２つのチャネル１
４及び１６が取付ｔＪられている。

チャネル５及び７は制御装置２１のポートａ及びｂにお
いて終端し、チャネル８及び１０は制御装置２３のポー
トｅ及びｆにおいて終端し、チャネル９は制御装置２１
のボー１〜Ｃにおいて終端し、チャネル１２は制御装置
２３のポートｇにおいて終端し、チャネル１４は制御装
置２１のポーｌ−ｄにおいて終端し、チャネル１６は制
御装置２３のポートｈにおいて終端して、それらを駆動
する。

制御装置２１及び２３には、タグ線及びデータ線を包含
する要求／応答型のインターフェースを介し、ＤＡＳＤ
制御装誼即ち接続機構２８及び３０を経て、１組のＤＡ
ＳＤ５３が取付けられている。制御装置２１とＤＡＳＤ
制御装置２８との間のインターフェースは、ダグ線６５
並びにデータ入力線５７及びデータ出力線５９を含む。

同様に、ダグ線６７並びにデータ入力線６１及びデータ
出力線６３は、制御装置２３をＤＡＳＤ制御装置３０に
結合させる。

要求／応答型のインターフェースにおいては、タグ出力
がデータ出力線上の情報を識別して有効化し、タグ入力
がデータ入力線上の情報を識別して有効化する。この点
に関して、名ＣＩ）　ｔＪ／制御装置／装置は相互に非
同期的に動作し、方向性制御がトップ・ダウンで行われ
る。制御装置２１と２３との間に於て、キャッシュ１０
１は、制御装［２１を経て経路１０３及びアクセス回路
１０５を介して、又は制御装置２３を経て経路１１１及
びアクセス回路］０９を一部１して、アクセスされる。

キャッシュ本体は、にへ４ｏＳの如き適当な高速度の主
記憶装置の技術におけるＲＡＭより成ることができる。

本発明の方法を実施するために適しているＤＡＳＤキャ
ッシュの構成は、ＩＢＭ社刊行物Ｇ　Ａ、　３２−００
６２−０に記載されているＩ　Ｂ　Ｍ　３８８０記憶制
御装置のモデル１３に見ることができる。

このモデルは、ＩＢＭシステム３７０、特にＭＶＳ／Ｓ
Ｐリリース３のオペレーティング・システムとともに用
いられる、高性能キャッシュＤＡＳＤサブシステムとし
て設計されている。

上記モデル１３は、第４図に示されている如き２つの制
御装置、及びキャッシュ１０１を形成している４乃至８
メガバイトの容量のキャッシュを有している。

１組のＤＡＳＤ５３は、各々接続機構２８又は３０を経
て、別個の経路を介してアクセス可能な装置即ちＤＡＳ
ＤＯｌｌ、２及び３を含む。

接続機構２８は、制御装置２１を経て線５５を介して任
意の装置への経路を与える。線５５は、装置毎に読取／
書込ヘッドを含むディスパッチ可能なアームに於て電気
的に終端している。同様に、接続機構３０は、制御装置
２３を経て線５１を介してもう１つのディスパッチ可能
なアームへの独立したアクセス経路を与える。各接続機
構は、各々接続機構論理（３９，４７）及びシーケンス
制御装置（４１，４９）を含む。

ＤＡＳＤキャッシュ及びデータの移動 オペレーションを実行するための素子間の活動的な接続
は、データの移動に関してのみ、成る期間に亘って必要
とされる。いずれかの制御装置２１又は２３が、読取Ｃ
ＣＷに応答して、データが存在するか否かを確認するた
めにキャッシュのブイレフ１〜りにアクセスする。″ヒ
ツト″が生じた場合には、該制御装置を経てＲＡＭチャ
ネルとの間で移動が行われる。νＦ込ＣＣＷの場合には
、チャネルから制御装置を経てキャッシュへ移動が行わ
れる。該キャッシュか゛ライ１−・イン”型であって゛
′ヒツｈ”（利用可能な空間又は更新さ４するべきレコ
ード）が生じた場合には、データがキャッシュに書込ま
れた後に、ＤＡＳＤにコピーされる。」二記キャッシュ
が１′ライト・スルー型である場合には、データが独立
にキャッシュ及びＤ　Ａ　Ｓ　Ｔ３中にｆＩ込まれる。

キャッシュのディレクトリ キャッシュは、ディスクのレコードの一部のコピーを保
持する、大容量のＲＡＭを与える。

キャッシュ１０１が″ライ１−・イン”型で動作される
場合には、ＲＡＭ１０７は、接続されたプロセッサから
ディスクに送られたが、未だ書込まれていないレコード
を含むことができる。

ディレクトリは、ブロックの割振りを用いてディスク・
キャッシュのための内容を記述している。又、ディレク
トリは、ＲＡＭ１’０７に記憶されており、次に示す如
く、トラック及びブロック記述子の表より成る。キャッ
シュの空間は、固定寸法のブロックに分割されている。

１つのブロックは、ディスク・トラックからの１つ又は
それ以上の隣接するレコードをレコード識別（ｉＤ）フ
ィールドとともに含んでいる。更に、レコードを修正す
るためのフラグ情報を含むこともできる。トラックに於
ける、レコードのカウント、キー及びデータのフィール
ド間のギャップは記憶されていない。

ディレクトリ・フ本＝マツ）Σ トラック記述子の内容 ビット　項目 ５　装置番号 １０　シリンダ番号 ４　ヘッド番号 １２　ハツシュ・チェイン」二の次の１へラック記述子
の指標 １４　１−ラックの第１データ・ブロックの４旨１票フ
ラ殆 １９　予備 ６４　合計（８バイ１へ） ブロック記述子の内容 ビット　項目 １４　ブロック記述子の循環チェイン上のトラックの次
のブロックの指標 フラグ： １　予備１５ １　最後のレコードは次のブロックに続く１　ブロック
は参照されている １　ブロックは修正されたレコードを含む１４　予備 ６４　ブロックの第ルコードのＩＤ（カウント）フィー
ルド ６４　ブロックに続く第ルコードのＩＤ（カラン１−）
フィールド １６０　合計（２０バイト） トラックのためのブロック記述子は循ぶリスｉ−におい
て相互に連鎖しているべきである。そのチェインは、ト
ラックの第１ブロツクにおいて、トラック記述子のエン
トリにおけるポインタから入るべきである。ブロック記
述子は、それらのレコードがトラックにおいて生じる順
に連鎖している。ディレクトリの索引は、１−ラック記
述子を見出すために、ハツシュ・コーチ−ｒングを用い
ている。その索引は、要求されたレコードを確認するた
めに、ブロック・チェインに従う。

１−ラックはキャッシュ中に部分的にしか存在しない場
合がある。レコードは、ブロック間においてのみ、存在
しないことがある。所−ダのトラックのためのキャッシ
ュのブロック間の間係は、ブロックの第ルコーｌく及び
該ブロックに続く第ルコードの両方のＩ　Ｉ）フィール
ドを記憶することによって記録される。

ブロック記述子は、番号１乃至１１のデータ領域に記憶
される。キャッシュのデータ・プロツりも、番号１乃至
ｎのデータ領域に記憶される。

位置ｉに記憶されたブロック記述子は、常にデータ・ブ
ロックｉを参照する。データ（又はキー）・フィールド
及びレコードより（カラン１〜）フィールドを交互に含
むブロックは、第ルコードのデータ（キー）から始まっ
て、最後のレコードのデータ（キー）・フィールドで終
る。

ブロックにおける第ルコード以外のレコードのＩＤは、
データ・ブロックに記憶されている。

４０９６バイトのブロック寸法においては、キャッシュ
・ブロックにおけるレコードよりフィールドとブロック
記述子とに利用可能な空間は、８つの５１２バイトのレ
コード及びそれらのＩＤを収容するために、更に５４バ
イ１−又はそれ以上である。キャッシュが不揮発生キャ
ッシュ（″ライト・イン”キＡ７ツシユ）として取扱わ
れる場合には、ＩＤフィールドの１ビツトが、レコード
が修正されたことを示す標識として働く。又、ディレク
トリの大きさは、ブロック記述子によって支配される。

４０９６バイトの各ブロックのための２０バイトの記述
子は、１％よりも小さいディレクトリのオーバヘッドを
示す。

ブロック・ステージングの手順 本発明の方法を呼出して実行するために必要な手順を以
下に記述する。それらの手順は、制御装置２１及び／若
しくは２３に存在するキャッシュ管理機溝部分によって
実行される。

１、ブロックの割振り ２、レコードの読取又は書込 ３、フォーマットの書込 ４、二重のレコード又はキーのチェック５、次のレコー
ドの取得 ブロックの割振り ブロックの割撮りは、新しいブロックのデータがキャッ
シュ１０１中にステージングされる前に呼出されるプロ
トコルである。最初に、位置表示機構が値１に初期設定
される。該位ｎｓｔ＜示機構は値１だけ増分される。そ
の値がｎ＋１に達した場合には、循環されて、１にセッ
トされる。

単一ブロックのデータの割振りに於ては、そのブロック
は、指標が位置表示機溝の値であるブロック記述子にお
いて調べられた参照ピッ１へを有している必要がある。

そのビットが１１オフ″である場合には、同一の指標の
値のデータ・ブロックが割振りのために選択される。次
に、上記位置表示機構が増分されて、オペレーションが
終了される。しかしながら、使用ビットが“オン″であ
る場合には、そのビットはターン・オフされて、上記位
置表示機溝が増分される。

オペレーションが、ブロック記述子の検査に戻る。

ｋ個の隣接するデータ・ブロックの割振りは、次のプロ
トコル・ステップを必要とする。

１、可変の呼出されたカウンタを零に初期設定する。

２、番号が位置表示機構の値であるブロック記述子に於
けるブロック使用ビットを調べる。

その使用ビットが″オフ”であれば、カウンタ値が増分
される。そのビットが″オン″であれば、又は位置表示
機構の値が１にセットされていれば、そのビットはター
ン・“オフ”されて、カウンタ値が零にセラ１へされる
。

３、位置表示機構を＋１だけ増分し、カウンタ値がｋよ
りも小さい場合には、ステップ２に戻る。

４、番号が位置表示機構の最後のｋの値に相当するブロ
ックを割振りのために選択する。

キャッシュが“ライト・イン”型で動作される場合には
、′ブロックは修正されたレコードを含む″のビットが
、割振りのために選択された各ブロックについてチェッ
クされる。修正されたブロックに於けるレコードがＤ　
Ａ　Ｓ　Ｉ）に書込まれる。

レコードの　／書込 レコードの読取り又は書込において、有利な手順は、任
意にＴＥＭＰＣとして表わされる６４ビツトのフィール
ドを用いる。そのフィールドは、二重チェック手順によ
っても用、いられる。

レコードの読取又は書込は次のステップを用いる。

１、キャッシュ・ディレクトリにおける１〜ラツク記述
子のエントリを見出すためにハツシュ・テーブルを索引
することによりその装置番号、シリンダ番号及びヘッド
番号を連結することによって形成された、要求している
トラックのＩＤを用いる。

２、ハツシュ・テーブルに衝突が生じた場合には、必要
なエントリを見出すために、トラック記述子のエントリ
に於ける″ハツシュチェモノ上の次のトラック記述子の
指標”を用いることができる。トラックＩＤが見出され
ない場合には、レコードがキャッシュに存在していない
ことに留意されたい。

この場合、トラック記述子のエントリは、そのトラック
のためにつくられる。しかしながら、トラックＩＤが見
出さばした場合には、その記述子のエントリからパＩ・
ラックの第１データ・ブロックの指標″が得られる。そ
れから、各エン１〜りに存在する″１−ラック・フィー
ルドの次のブロックの指標″を用いてブロック記述子の
チェインが探索される。

３、その探索において、要求されたＩＤフィールドが見
出された場合には、読取に於てはキャッシュから制御装
置へ、膚込においては制御装置からキャッシュへ、レコ
ードが転送される。

４、その探索において、要求されたＩＤフィールドが見
出されない場合には、チＡ７ネルから受信されたレコー
ドの寸法が制マコ１装置から得られる。これは、必要な
ブロックの数を含み、ブロックの寸法による分割された
レコードの寸法を越えない最小の整数であると考えられ
る。レコードの寸法の表示がない場合には、１つのブロ
ックが割振られる。それが不充分であれば、オペレーシ
ョンが再試行される。

１一つのブロックが割振られた場合には、レコードが、
そのトラックからそのブロックに入ることができる数の
後続レコードとともに、キャッシュにステージングさ肛
る。書込に於ては、上記レコードがＤＡＳＤに書込まれ
、上記後続レコードがＤＡＳＤからキャッシュヘステー
ジングされる。上記ブロックに入ること力１できない第
ルコードのＩＤフィールドは、ＴＥＭＰＣフィールド中
に読込まれる。後述される二重チェック手順が、二重レ
コードのステージングを防ぐために用いられる。新しい
ブロックのためのブロック記述子のエントりが書込まれ
、その指標が該トラックのためのブロック記述子のチェ
インに挿入される。″ブロックに続く第ルコードのＩＤ
フィールド″がＴＥＭＰＣフィールドから得られる。

１つ以上のブロックが割振られた場合には、要求された
レコードだけがそれらのブロック中にステージングされ
、そのトラックの次のレコードのレコードＩＤが続く。

書込に於ては、そのトラックの次のレコードのレコード
ＩＤだ【ノがＤＡＳＤから読取られる。新しいブロック
のためのブロック記述子のエントリが書込まれ、指標が
該トラックのためのブロック記述子のチェインに挿入さ
れる。最後のブロック記述子を除くそのような各ブロッ
ク記述子において、“最後のレコードは次のブロックに
続＜１′のピッ１−が″オン″にセットされる。現デー
タ・レコードとともに読込まわる、上記レコードの次の
レコードのＩＤフィールドが、最後のブロック記述子の
″ブロックに続く第ルコードのＩＤフィールド”のフィ
ールドに記憶される。

キャッシュが１′ライト・イン型であり、チャネルが書
込の参照を行った場合には、″ブロックは修正されたレ
コードを含む″のピッ１へがブロック記述子に於て″オ
ン″にセットされ、レコードＩＤに於ける″レコード修
正″のビットが“オン”にセットされる。キャッシュが
“ライト・イン型でない場合には、レコードがディスク
に書込まれる。

フォーマットの書込 フォーマットの書込は、ディスクからのステージング及
びその後に於ける二重処理のチェックが除かれること以
外は、″レコードの書込″と同一である。又、書込まれ
るべきレコードが、キャッシュの単一のブロックに既に
含まれているレコードＲの″次″のレコードであり、そ
の新しいレコードがレコードＲに続くそのブロックに入
ることができる場合には、レコードを読取る又は書込む
ステップ４が除かれる。その代りに、上記の新しいレコ
ードが、レコードＲに続く位置に於て、キャッシュに書
込まれる。更に、書込まれたレコードに続く特定のトラ
ックから、キャッシュにおける任意のブロックが削除さ
れる。書込まれたレコードを含むブロックが既にキャッ
シュに存在している場合には、そのブロック内でそのレ
コードに続く全てのレコードが削除される。

二重レコードのチェック この手順は、ブロックがディスクからステージングされ
た後、新しいブロック記述子のエンドりが書込まれる前
に適用される。その手順は次に示すステップを含む。

１、ブロックのための１へラック記述子及び“１ヘラツ
クの第１データ・ブロックの指標″を確認する。

２、新しいブロックに於て連続する各レコードＩＤフィ
ールドについて、第１フイールドから始めて、各エント
リに存在する″）・ラックの新しいブロックの指標″を
用いて、そのトラックのブロック記述子のチェインを探
索する。レコードＩＤが既にキャッシュに存在すること
が見出された叫合には、その値がＴＥＭＰＣフィール１
−に記憶され、そのレコードが新しいブロックの残りの
部分全体とともに削除される。そのとき、」二記手順が
終了する。新しいブロックからの突合せＩＤがキャッシ
ュに既に存在しＣいない場合には、上記手順は終了する
。

７のレコードの数件 ＣＣＷのシーケンスは、しばしば１．トラック上の″次
″のレコードを暗黙に参照する。フォーマットの書込の
場合には、次のレコードのよりが、到来するＣＣＷシー
ケンスにより供給される。現ＣＣＷシーケンスによるア
クセスされた前のレコードがキャッシュに存在している
が。

そのブロックの最後に存在していないときに、１１次の
レコード″への参照が生じた場合には、次のエントリは
、単にデータ・ブロックに於ける次のエントリである。

又、キャッシュのブロックに於ける最後のレコードがア
クセスされた直後で、その１−ラック上の後続レコード
が必要とされる場合には、次のレコードのＩＤが、ブロ
ック記述子に於ける“ブロックに続く第ルコードのＩＤ
フィールド″から得られる。

その他 第５図において、固定長ブロックにおける従来のステー
ジングの単位が示されており、本発明の方法によるトラ
ック」二のミス・レコードから始まる固定エクステン１
〜に於ける可変長ブロックのバッキング及びステージン
グと対比されている。第１図は、本発明の方法に於ける
ステップを示す高レベルの流れ図を示している。ミス・
レコードがブロック・エクステントを越えるか否かの関
数として、別個の処理が開始される。

もう一つの点は、キーが別個にステーシンクされること
である。その実施においては、″ミス″であるキーの探
索は、新しいブロック中に、必要なキーを、そのトラッ
クがら該プロッタに入ることができる数の後続キーとと
もに、ステージングさせる。二重のキーを除くためのル
ールはレコードに関して示したものと同様である。

その選択の利点は、キャッシュに存在していないレコー
ドのキーがそのキャッシュに存在しているかもしれない
ことである。これは、探索時間を短縮する。

以上においては１本発明の方法を読取及び碧込の両方に
おけるキャッシュの参照に関して説明したが、著しい量
のデータを用いた書込の参照について言及しておく。デ
ータ・エクステントを知るための機能が設けられている
ならば、本発明の方法を用いることができる。こ、ｌｂ
は、例えば、最大容量迄充たすことができるバッファ又
はＣＣＷにより制御装置に供給されるパラメータを有す
ること等の種々の方法によって行われる。

［発明の効果］ 本発明の方法によれば、記憶サブシステムを参照するＣ
ＰＵプロセス（チャネル・プログラム）の実行速度が増
し、Ｗｉ層記憶システムのステージ間に於けるデータの
転送が相当に減少し、更に具体的に云えば、キャッシュ
に於ける可変長レコードの管理の複雑さが除かれて、Ｄ
ＡＳＤとＤＡＳＤキャッシュとの間におけるデータの転
送が減少する。

【図面の簡単な説明】

第１図は本発明の方法におけるステップを示す層を示す
図、第３図は複数のＣＰＵが複数のＩ）ＡＳＤへのアク
セスを共用している従来技術によるシステム構成を示す
図、第４図は記憶制御装置のレベルにおいて管理される
本発明の方法におけるキャッシュを有する種々のアクセ
ス経路を有している１組のＤＡＳＤを示す図、第５図は
ステージングのための固定エクステン１へに於ける可変
長レコードのブロッキングと比較されている従来のステ
ージング及び固定ブロックを示ず図である。 １．３．６・・・・ＣＰＵ、２・・・・ＣＰＵキャッシ
ュ、４・・・・主記憶装置、５．７．８．９、］０．１
２．１４．１６・・・・チャネル、１１．１３．１５．
１７．３１．３３．３５．３７．１０３、Ｌｌｌ・・・
・経路、２１．２３・・・・制御装置、２５・・・・ス
イッチング手段、２７．２９・・・・１〕ΔＳ１つ、２
８．３０・・・・ＤＡＳＤ制御装置（接続機構）３９．
４７・・・・接続機構論理、４１．４９・・・・シーケ
ンス制御装置、５１．５５・・・・線、５３・・・・１
組のＤＡＳＤ、５７．６１・・・・データ入力線５９．
６３・・・・データ出力線、６５．６７・・・・タグ線
、１０１・・・・キャッシュ、１０５．１０９・・・・
アクセス回路、１０７・・・・キャッシュＲＡＭ、。 出願人　インターナショナル・ビジネス・マシーンズ・
コーポレーション 代理人　弁理士　岡　１）　次　生 （外１名）

Claims (1)

1. 【特許請求の範囲】 ＤＡＳＤキャッシュに存在しない長さの異なるミス・レ
   コードを、ＤＡＳＤのトラックから固定のブロック・エ
   クステントに分割された上記ＤＡＳＤキャッシュ内ヘス
   テージングするための方法であって、 （ａ）上記ミス・レコードがブロック・エクステントと
   等しいか又はそれよりも小さい場合には、上記ミス・レ
   コードから始まるブロック・エクステント内に上記キャ
   ッシュに既にステージングさｈているレコードがあるか
   否かを確認し、既にステージングされているレコード及
   びその後続の全てのレコードを上記ブロックから削除す
   るように、又は （ｂ）上記ミス・レコードがブロック・エクステントよ
   りも大きい場合には、上記キャッシュ内の最近用いられ
   ていない最初のに個のブロック裂開振り、上記に個のブ
   ロックのレコードをステージングするように、 Ｄ　Ａ　Ｓ　Ｉ）の参照トラックに於て、」二記ミス・
   レコードから始まって、固定ブロックに亘るか、」二記
   トラックの端部に達するか、又はキャッシュに既に存在
   するレコードに遭遇するかする迄続くレコードを上記キ
   ャッシュにブロッキングしてステージングするステップ
   を含む。 ＤＡＳＤキャッシュに於ける情報の固定ブロック・エク
   ステントをステージングするための方法。