JPS5831460A - アドレシング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明の分野 本発明は階層記憶システ＾に関し、更に具体的にはこの
ようなシステムで使用されるアドレシング装置に関する
。

先行技術の説明 大容量メモリのアドレシングには、長年の間ハツシング
手法が用いられてきた０特にメイン・メモリの領域でそ
うであった。一般的には、ハツシング動作はハツシュ・
クラスのためにインデックス・インディケータを発生す
る０インデツクス・インディケータはアドレシング機構
をスキャタ・インデックスーテ〜プル（ＢＩＴ）へ導く
。ＢＩＴはアクセスされるメモリ領域に関連していると
考えられるメモリーアドレス・ディレクトリイ・エント
リイのアドレス、を含む。ディレクトリイ・エントリイ
は、単一的にリンクされたリストによって、同一ハツシ
ュ・クラスの他のディレクトリイーエントリイへリンク
されている。従って”、メモリ内の所与の項目へアクセ
スするためには、インデックス・インディケータが発生
され、ディレクトリイ・エントリイにアクセスするため
、ディレクトリイ会エントリイへのアドレスが使用され
る０もし所望のメモリ・アドレスとディレクトリイ・エ
ントリイ中に記憶されたメモリ・アドレスの間ｋＴ−Ｒ
が発見されると、八ツシュ・クラス内の一連のディレク
トリイーエントリイが検査さが調べられる。アドレスを
有すれば、それはメモリがデニタな含むか、データを受
取るように割当てられたスペースを有することを意味す
る・そのような領域がディレクトリイ中で決定されると
、「ヒツト」が生じたのであり、メモリへのアクセそ、
が進行する。そのような領域がハツシングｉ法によって
決定されないと、「ミス」が生じたので、　　ある・階
層システムのミスに続いて、’７＝−夕はバッキング・
ストアからメモリへ転送門れるか、記録用データを受取
るためのスペースがメモリ内で割当てられる。

そのようなハツシング手法では、ノ・ツシュ時間を最小
にする（メモリへのアクセス時間を小さく　。

する）ことが望まれる・ ハツシュ中クラスのサイズが大きい時、多くの項目がそ
のクラスの中ヘマツブされる０この複数のマツピングは
コリジヨン（ｃｏｌｌｉｓｔｏｎ）と呼ばれるが、それ
は複数のデー′夕項目が同一のハツシュＱり２スへ衝突
するからである。多数のコリジヨンが存在する時のハツ
シュ拳り２スの探索は・メモリへのアクセス時間を非常
に重大させる。０それは特にデレイクトリイが内容によ
ってアドレス可能でない時にそうである・従って、多く
のメモリ・アプリケーションにおいて、ディレクトリイ
の探索時間を小さくするため、ハツシュ・クラスのサイ
ズを最小に維持することが望まれる。これに対し、ディ
レクトリイのために内容アドレス可能メモリが使用され
る時、全ての探索は１サイクル内で実行される。残念な
がら、内容アドレス可能メモリは高価であり、従って多
くのアプリケーションにおいて、内容アドレス可能メモ
リは利用できない。

このような問題は、比較的大型のメモリが使用される場
合に大きくなる。例えば、直接アクセス記憶装−（ＤＡ
ＳＤ）のバッファとして１妾型キヤツシュカ使用され、
このキャッシュが８メガバイト以上の容量を有する場合
、コリジヨンの数を減少させることと、記憶システムの
コストを抑えることとの間に矛盾が起る。更に、ＤＡＳ
Ｄはいくつかの遅延アクセス境界を示すので、問題を生
じる。待ち時間（Ｌａｔｅｎ、ｃｙ）と呼ばれる第１の
遅延境界は、ＤＡＳＤの回転特性に基く。１つ又は２つ
の変換器が回転するディスク表面に関して位置づけられ
、ディスク表面上の所与の地点に対するアクセスは、回
転待ち時間に依存するようになっている。更に大部分の
ＤＡＳＤでは、１つのディスク表面に対して１つの変換
器が設けられている０これは、変換器がトラックからト
ラックへと半径方向に移動することを意味する。多重表
面ディスク記憶装置では、移動はシリンダからシリンダ
と実行され、シリンダ・シークを実行する。

シリンダは何−半径上の全てのトラックから形成される
０アドレシング及びアクセス時間におけるこれら２つの
遅延は、ディスク記憶装置の機械的特性に基く。従って
、そのような機械的遅延に適応しないキャッシュ中のミ
スの数は、データ領域へのアクセス時間を非常に増大さ
せる可能性があるｏ全体的なシステム動作において、バ
ッキング・ストアの機械的遅延の効果を最小にするよう
に、キャッシュへアクセスすることが望まれる。

多くの先行技術によるハツシング手法は、コリジヨンの
数が少なくなるように、アドレスのランダム分布を使用
する。その結果、アドレスは、アクセスされるメモリの
アドレス・スペース上、均一に分布されていなければな
らない。このような原理は１８Ｍテクニカル・ディスク
ロージャ・プレチン（ＴＤＢ）のいくつかの記事で説明
されている０例えば、１９７７年５月のＴＤＢの４８２
２−４８２３頁には、Ｊ、Ｌ、Ｃａｒｔｅｒ　　その他
による’Ｃ１ａｓｓ　　ｏｆ　　Ｆａｓｔ　　Ｈａｓｈ
　　ＦｕｎｃｔｉｏｎｓＵｓｉｎｇ　　Ｅｘｃｌｕｓｉ
ｖｅ　　ＯＲ’と題する記事があり、４８２６頁には−
Ｍｅｔｈｏｄ　　ｏｆ　　ＥｘｔｅｎｄｉｎｇＨａｓｈ
　　Ｆｕｎｃｔｉｏｎｓ　　ｆｏｒ　　Ｌｏｎｇ　　Ｋ
ｅｙｓ’と題する記事がある。これらは、１対になった
ランダム・ハツシング機能が、トランザクションの数に
対して線形の平均走行時間を発生することを教えている
０これは、メイン・メモリのようなランダム・アクセス
・メモリにはあてはまるが、アクセス遅延境界が存在す
る場合には、必ずしもあてはまらない◎従って、これら
の記事で論議されている「比例定数」は、全ての場合に
適用され得ない０％に、アクセス遅延境界が存在する場
合にそうである。

更に１ハツシング手法では、プライム・ナンバーが使用
されてきた。例えば、１９７２年４月の１８Ｍテクニカ
ル・デスクロージャ・プレチンの３４８９頁にあるＲ、
Ｐ、Ｂｒｅｎｔによる’ＭｏｄｉｆｉｅｄＬｉｎｅａｒ
　　５ｃａｔｔｅｒ　　Ｓｔｏｒａｇｅ　　Ｔｅｃｈｎ
ｉｑｕｅという事を参照されたい。この記事は、顕著な
アクセス遅延境界を有しないランダム・アクセス・メモ
リに運上だハツシング手法を取扱っている。

ハツシングの他の局面は、ノ・ツシュ時間を少なくする
こと（アドレス発生に必要な時間を少なくすること）で
ある。このような時間の減少は、アドレスへ変換可能な
データ名称を選択することＫよって達成されてきた。例
えば、１９７５年６月の１８Ｍテクニカル・ディスクロ
ージャ・ブレチンに％　Ｌ、Ｊ、Ｗａｇｕｅｓｐａｃｋ
　　によって発表された％Ｐｒｅｄｉｓｔｒｊｂｕｔｅ
ｄ　　Ｌｏｇｉｃａｌ　　ＮａｍｅＧｅｍｅｒａｔｉｏ
ｎ　’　　という記事は１８−３９頁λランダム・アク
セス・メモリにアクセスするため、単一レベル排他的Ｏ
Ｒのハツシュ機能が、予め配分された論理名称によって
駆動されるハツシング手法を示している。１９７５年８
月に発行された１８Ｍテクニカル・ディスクロージャ・
ブレチンの８８０−８８１頁には、Ｄ、　Ｃ，Ｂｏｓｓ
ｅｎ　　その他による″Ｇｅｎｅｒａｔｉｎｇ　Ｕｎｉ
ｑｕｅ　　Ｎａｍｅｓｆｏｒ　　Ｖｉｒｔｕａｌ　　Ｓ
ｅｇｍｅｎｔｓ　’という記事に一同様の手法が紹介さ
れている。この記事は、アドレスの先行配分及び排他的
ＯＲ機能が、ハツシュ・テーブルのアドレシングを生じ
るという点で、Ｗａｇｕｅｓｐａｃｋ　　の記事と同じ
である。

据付は後のデータ処理システムにおいて、メモリはサイ
ズを変えることができる。従って、ハツシング手法は容
易に変更されねばならない０この事態は、これまで列挙
して来た記事の１つで取扱われているが、更に米国特許
４２１５４０２で取扱われている。この特許では、ＳＩ
Ｔ及びハツシュ−サイズはメイン・メモリのサイズにマ
ツチしたものとなっている。しかし、ハツシングは、顕
著なアクセス遅延境界を示さない純粋のランダム−アク
セス−メモリのためＫなされている０１８Ｍテクニカル
・ディスクローシャープレチンの１９７３年１２月号の
２２１４−２２１６頁には、望ましいハツシング手法の
要約が、Ｒ，Ｆ。

Ａｒｎｏｌｄ　その他による’Ｕｎｉｆｏｒｍ　Ｈ’ａ
ｓｈｉｎｇＡ１ｇｏｒｉｔｈｍ’　という記事によって
紹介されている。この記事は、仮想アドレス中スペース
をリアル・アドレス・スペースヘマツプスルこトラ説明
している。アドレス・スペースをマツプするために使用
されるハツシング・アルゴリズムの望ましい特性は、分
布の均一性、シーケンシャルな仮想アドレスのランダム
分布であり、／′／％ツシングの細分化よりも更に細か
く、リアル・アドレスヘマツプされるシーケンシャルな
仮想アドレスを与える０全てのアドレスは、仮想アドレ
スからリアル・アドレスへ１対１で対応ずけられねばな
らず、メモリ変更の場合には、ハラシネに最小のりマツ
ピングが要求され、計算は迅速（短い遅延）かつ反復可
能でなければならない。本明細書で説明されるハツシン
グ・アルゴリズムは、ヒツトが即時に生じない場合、反
復的プロセスを必要とするＯそれは、モジｘ　ｐ　；２
Ｂ加算（排他的ＯＲ機能の如く）を使用するのではなく
、桁上り及び借りを含む演算手法を使用する。この記事
は顕著なアクセス遅延境界を有しないランダム・アクセ
ス・メモリに望ましいハツシング手順を教えているが、
それがどのようにしてアクセス遅延境界を示すノ（ツ±
ング・ストアへ適用できるかは明らかではない・更に階
層記憶システムは複数のディスク記憶装置を含むことが
できる。単一のキャッシュであっても、全てのディスク
記憶装置のためにキャッジ・二接能を果さなければなら
ない。従って、）１ツシングは、そのようなディスク記
憶装置の内部アクセス遅延境界に対してのみならず、デ
ィスク記憶装置の独特の特性に対しても適応しなければ
ならない。例えば、各ディスク記憶装置のシリンダ「０
」は、通常、ディスク記憶装置に記憶されたデータ内容
に対するインデックスとして使用されるシリンダ「０」
は、通常、半径方向で最も外側のトラックより成るシリ
ンダである。シリンダ「０」は他のシリンダよりも頻繁
にアクセスされることが予想されるので、１つのディス
ク記憶装置のシリンダ「０」と、他のディスク記憶装置
のシリンダ「０」との間に、コリジヨンがあってはなら
ない◎ランダム分布は、たとえそれが均一であっても、
成る相対アドレスが他の相対アドレスとコリジヨンを生
じる可能性があることを意味する。従って、通常の設計
仕様を有するディスク記憶装置が使用される時、ハツシ
ングのランダム分布を避けるようにしなければならない
・ 本発明の要約 本発明の目的は、アドレス・スペース及びバッキング・
ストアのサイズの多様性に容易に適応するハツシング拳
システムを提供することである・本発明の他の目的は、
高い頻度で使用されるアドレスに対して最小のハツシン
グ・コリジヨンを保証するハツシュ型アクセス・システ
ムを提供することである。

本発明の他の目的は、サイズにおいて拡張伸縮自在のハ
ツシング手法実行システムを提供することである。

本発明の他の目的は、ハツシュ・アクセスがバッキング
・ストアに関連したキャッシュ又はバッファに対してな
される時、バッキング・ストアの遅延境界へ容易に適応
するアクセス頻度・システムを提供することである・ 本発明の第１の局面に従うハツシング・システムは、バ
ッキング・ストアのアクセス遅延境界及びバッキング・
ストアのアドレスに対して予想されるアクセス頻度に従
って順序ずけられたアドレス信号を処理する。

本発明ｙ従うハツシング・アクセス・システムは、ＢＩ
Ｔアドレス・スペースにおいて所定の順序及び等間隔の
分布状態で遅延ユニットの数（例えば、ディスク記憶装
置の数）をマツプされたＳＩＴアドレス・スペースを有
し、最低順序のアドレスから始まる全てのハツシング・
スペーネが１ＳＩＴアドレス・スペース内の独特のアド
レスで始まるようになっている。汗の構成によって、ア
クセス遅延境界を形成するユニットの各々において１全
てのハツシングの順序ずけられたオフセットが共通の相
対アドレスのために設定される。

本発明の他の局面に従うハツシング・システムは、装置
の構造上の特徴に関連した順序で歩容量のキャッシュ・
メモリをアドレーするため、装置アドレスのサイズ定数
によってハツシングされているアドレスを変更する。例
えば、パツキングーストア内の装置の数は、順序ずけら
れた態様でアドレスを分配する第１のハツシング・７ア
クタを構成し、遅延境界（即ち、ディスク記憶装置中の
シリンダ）の数は、順序ずけられたシリンダのノ１ツシ
ュ・アドレシングのハツシング−ファクタである◎ 実施例の説明 本発明は、第１図に示されるような階層周辺記憶システ
ム１０で実施されるのが望ましい。複数のディスク記憶
装置（ＤＡＳＤ）ＩｆはＤＯｌＤｌ、Ｄ２で示され、中
央処理ユニット又は他の計算機構のようなホスト（図示
せず）との間で、入出力接続線１３を介してデータを転
送するため、共用キャッシュ１２へ接続される。キャッ
シュ１２又はＤＡＳＤ１１におけるデータ又はデータ領
域へのアクセスは、アドレシングぐス１４を介して行わ
れる＠ＤＡ８Ｄアドレスの１部は、バス１５を介して１
対の電子スイツ゛チ１６及び１８を付勢するために与え
られる。これらのスイッチは１それぞれシステム１０の
異った通路を介して、アドレス信号及びデータ信号を導
く。バス１５は、スイッチ１６及び１８を付勢する周辺
指令を送ることもできる０例えば、指令はキャッシュ１
２を通して全てのデータ参照をなすべきことを指示する
かも知れない。その場合、スイッチ１６は図示された位
置ヘセットされる。他方、全てのデータ参照がＤＡＳＤ
１．１に対してなされるべきことを命する指令が受取ら
れるかも知れない。その場合、スイッチ１６はもう１つ
の位置へ切換えられ、ＤＡＳＤｌｌがバス１４へ接続さ
れる。スイッチ１６を制御する他の手段も使用されてよ
い０ パス１５はスイッチ１８へも延長されるＯスイッチ１８
は、データ信号をホストへ転送するため、ＤＡＳＤ１１
をバス２１へ接続する。バス２１は゛Ｉ１０接続１１１
１３へも接続されることができるＯこの接続は示されて
いない。バス２２はスイッチ１Ｂからキャッシュ１２へ
延長され、データはＤＡＳＤ１１とキャッシュ１２との
間を転送されることができる。システム１０はコントロ
ール２０ヲｔｔｒｏコント、ロール２０はスイッチ１８
を付勢し、ＤＡＳＤ、１１とキャッシュ１２との間のデ
ータ信号の転送が８、ホストの動作と独立してかつ非同
期的に行われるようにすることができる。即ち、スイッ
チ１８はホストによって制御されると共！ＩＣ′局部的
にも制御される。

スイッチ１６が図示された位置にあるものと仮定する。

バス１４上のＤＡＳＩ）アドレス信号は゛旧ハツシュ回
路２３へ導かれ、キャッシュ１２の前の参照によって、
バス１４上で受取られたアドレスをハツシングする必要
なしに、キャッシュ１２へのアクセスが可能であるかど
うかが決定される。

ＤＡＳＤ、１１はデータを記憶するための大容量を有し
、キャッシュ１２はそれよシも小さい容量を有するので
、スペースがデータ・アクセスのためにキャッシュ１２
の中で割当てられたかどうか、又ハ所与のデータがキャ
ッシュ１２の中で実際ニ記憶されているかどうかを決定
するため、ＤＡＳＤｌｌのアドレスを使用するハツシン
グ・アドレス手法が使用される。いずれにせよ、旧ハツ
シュ回路２３が前のアドレスと密接に関連したアドレ、
　スを検出すると、後述するようにスキャタ・インデッ
クス・テーブル（ＳＩＴ）２７へ直接にアドレスする。

５ＩＴ２７は、キャッシュ１２ヘアクセスするため、デ
ィレクトリイ３０へのハツシュ信号をインデックスする
。論理装置制御プロシフ・レジスタ２５は、バス２４を
介してアクセスされるが、ＤＡＳＤアドレス及び対応す
る５ＩＴ２７アドレスを含む・ ディレクトリイ３０は、キャッジ１２の各アドレス可能
セグメン）Ｋついて１つのエントリイを含む。各エント
リイはＤＡＳＤｌｌのためにアドレス表示を含む・それ
は、どのデータがキャッシュ１２の中に記憶されている
か、又はキャッシュ・スペースがデータのために決定さ
れたかを表示するためである。ハツシュ・クラスはディ
レクトリイ３０のエントリイの複数個を含んでよいから
リンキング機構３１は、単一的にリンクされたリストを
用いて、同一ハツシュ・クラスにある全てのエントリイ
を相互にリンクする。１度ＤＡＳＤ１１のアドレスに対
応するディレクトリイ・エントリイが発見されると、キ
ャッシュ１２は、通路３２を介して、ディレクトリイ３
０によって指示されたアドレスをアクセスされる。次い
で、データは、ホスト（図示せず）とキャッシュ１２と
の間で、Ｉｌｏ　接続線１３を介して転送されることが
できる０勿論、ディレクトリイ３０はミス（即ち、デー
タ・スペースはキャッシュ１２の中で割当てられなかっ
たこと）を表示してよいＯこの場合、他の動作が必要と
なる・ 旧ハツシュ回路２３が、キャッシュ１１２への前の参照
が現在受取られたＤＡＳＤアドレスに対してなされたも
のでなく、それから離れたものであることを示す場合、
現在受取られたアドレスは、アドレス・ノ・ツシング動
作のために、ノ・ツシュ回路３４へ与えられる。ハツシ
ング動作の結果として、バス３５へ与えられたアドレス
信号は、５ＩＴ２７における所与のレジスタを指定する
。そのレジスタの内容は、ハツシュ−クラスに対応する
ディレクトリイ３０のエントリイを指定するＯ次いで１
後述するように１デイレクトリイ３０のノ・ツシューク
ラスが走査される。

要スるＫ、キャッシュ１２へのアクセスは、ＤＡＳＤｌ
ｌのアドレス信号がバス１４上で受取られ、それが旧ノ
・ツシュ回路２３へ送られ、次いで新しいハツシング動
作を実行するため／％　ｙ　シュ回路６４を通るか、直
接に８１Ｔ２７へ与えられて、ディレクトリイ３０に対
するインデックス又はアドレス信号を発生することによ
って行われる０次に、ディレクトリイ３０はハツシュ・
クラス内のエントリイを走査するためにアクセスされる
が、それは受取られたＤＡＳＤアドレスに対応するＤＡ
ＳＤｌｌのアドレスを探すためである０ヒツトの場合、
キャッシュ１２がアクセスされ、そうでなければ、ミス
が表示される。

ＤＡＳＤｌｌは直接にアクセスすることができる０この
場合、スイッチ１６は他の位置ヘセットされ、スイッチ
１８も他の位置へ動かされるＯそして、データへのアク
セス及びＤＡＳＤｌｌへ記録するためのデータ記憶領域
へのアクセスは、通常のディスク記憶装置の場合と同じ
ようにして実行される。

ディレクトリイ３０によってミスが表示されると、バス
３３を介してコントロール２０へ与えられる制御信号は
、スイッチ１８を図示された位置へ付勢する。それは、
ＤＡ８Ｄからバス２２を介してキャッシュ１２へ、デー
タ信号を転送するためである０勿論、そのような転送が
生じる前に、ＤＡＳＤｌｌは利用可能となっていなけれ
ばならず（ビジィでない）、ディレクトリイ３０及び−
・ツシング拳アドレスがセットアツプされて、キャッシ
ュ１２へのアクセスが能動化されねばならな℃翫。

第２図はＤＡＳＤｌｌの概略的構成を示す◎一般的に、
それぞれのＤＡＳＤＩＩ（例えばＤｏ）は同時に回転す
る複数のディスク４０．４１を含み、各ディスクはデー
タ信号を記録するための１対の表面を有する。ＤＯにあ
る表面の１つは、位置すけ情報又はサーボ情報を記憶す
るために確保されている。トラックの全ては、他のトラ
ックの全てと同心円関係を有し、かつ他の表面上の他の
トラックと半径方向的に揃えられている０例えば、２つ
のディスク４０及び４１の各々は、それぞれ半径方向で
一番外にあるトラック４５，４２を有する・半径方向的
に一番外の位置にあるトラックはシリンダ０（ＣＯ’）
と呼１ばれるＯ缶表面に対して１つのヘッドが設けられ
るから、サーボ・機構（図示せず）がヘッド（図示せず
）をＣＯ）ラックへ整列させると、任意の表面が電子ス
イッチングの働きによりアクセスされ、ＣＯ中の任意の
トラックがアク声スできるようになる０他のシリンダに
アクセスするためＫは、ヘッドの全てが、アドレスされ
たトラック（例えば、シリンダＣ１のトラック）へ向っ
て、半径方向へ動かされなければならない。この機械的
な移動はデータ領域へアクセスする場合にかなりの遅延
を生じ１、従って、顕著な遅延アクセス境界となる。他
のシリンダは（１つのディスク装置には、５００以上の
シリンダがあるかも知れない）、それぞれディスク４１
及び４０の上に存在するトラック４４及び４５を有する
シリンダＸを含む。同様に、シリンダＹはディスク４１
上にトラック４６を有し、ディスク４０も同様のトラッ
クを有する。同じように、ＤＡ８Ｄ１１の選択はかなり
のプロトコルを必要とし、□ハツシュ・クラスを限定す
る主たるファクタは各記憶装置にあるシリンダの数であ
るから、前述した特性の全ては本発明のハツシング・シ
ステムへ融合されている。これはノーツシュ・アドレシ
ングにおいてシリンダ・オフセットを生じるＯ装置アド
レスによって指定さ些た全での装置は、５ＩＴ２７のア
ドレス・スペース内でノ（ランスされたスペースを割当
てられる。各ハツシュ・クラスは装置の各々からのア金
レスを含むＯ小さな５ＩＴ２７では、所与の装置から得
られたいくつかのシリンダ・アドレス・スペースは、後
にもつと明らかｋなるようＫ、同一の）・ツシュ・クラ
ス内にあるかも知れない。ノーツシングの順序ずけられ
た対称性を与えるため、装置は８ＩＴ２７のアドレス・
サイズ（即ち、そこに含まれるレジスタの数）の関数と
してオフセットされる。従って、装置の総数はオフ↓ッ
トであり、全てのＣＯに対する全てのアドレスは、決し
て同じノ〜ツシ二〇クラスの中にはない。ＣＯは、典型
的に、ディスク記憶装置に記憶されたデータに対するイ
ンデックスを含むので、それは最も普通にアドレスされ
るシリンダである。もつとも普通にアドレスされるシリ
ンダを異ったハツシュ・クレスに保つことＫよって、ハ
ツシング動作におけるノ＼ツシエ・コリジヨンの確率が
少なくなる。８１Ｔ２７ではトラックが隣接しているの
で、トラフ−りのアドレスを９ＩＴ２７の隣接したレジ
スタへ関連ずけることによって、トラック間の電子的切
換えが有利となる。シリンダ及び装置のオフセットは、
キャッシュ１２のサイズが変化した時にも、５ＩＴ２７
のサイズが変化上た時にも、ハツシング・アルゴリズム
を容易に調整可能にする。ここで注意すべき、は１．−
キャッシュ１２又は５ＩＴ２７示変化した時、キャッシ
ュ１２にあるデータの播ては、データの統一性を維持す
るため無効にされねばならないことである。

第２１１において、ノ１ツシ五・クラスは次のようｋな
っている。　　　　　　　　　□ シリンダー〇−オフセジト トラック−Ｈ−隣接 装置−バランスされたスペース 装置−ｐ−オフセット 第３図及び第４図は、０個のレジスタからＮ個のレジス
タまで延長されている５ＩＴ２７のアドレス・スペース
ヲ示ス。ノ＼ツシング・アルゴリズムは、装置アドレス
の全てを、５ＩＴ２７のベースφア本°レスｒ　ＯＪ、
から等しい大きさだけオフセットする。例えば、第３図
のアドレス・スペース５０の場合、１４個の装置（ＤＡ
ＳＤ１１’）は）１４個の等しいスペースのオフ るように示□される。装置ＤＯは、ゼロのところＫ。

そのシリンダ「０」アドレスを有する。装置ＤＩはその
シリンダ「０」アドレスをＮ／１４のところに有し、装
置Ｄ２はそのシリンダ「０」アドレスを２Ｎ／１４のと
ころに有するＯこれは、各装置ＤＸのシリンダ「０」が
、装置の数によって除算された５Ｎ１２７のアドレスＮ
Ｘのところでインデックスされることを意味する。従っ
て、２２個の装置がシステム１０の中にある時、小さい
オフセット５２が生じる。第３図は、全てのＤＡ８Ｄ１
１が同じ数のトラックを有する場合を示すＯしかし、こ
の制限＆！、本発明の実施型態を簡単・Ｋするが、必要
条件となるものではない。第４図において、５ＩＴ２７
は、各種の記憶装置のトラック数で表わしたサイズ又は
容量に従って、異ったオフセットへ分割されている。大
きな装置に対するオフセット５６は、オフセット５５よ
り大きい。

同様に１オフセツト５７は更に大きい装置に対するもの
である。

第５図は、ディレクトリイ３ｏにアクセスするため、装
置アドレスがどのようＫＳＩＴレジスタ・アドレスに現
われるかのマツプを示す。装置ＤＯ−Ｄ３のための欄６
ｏ、６１．６２．６３には）それぞれ別個の装置アドレ
スが掲げられている。

シリンダ番号Ｃは欄の左゛方に示され、シリンダ内のト
ラックの番号は欄の右方に示される０第５図に示される
ように各シリンダは１０本のトラックを有する０１０の
値は任意に選択されたものであって、例を簡単にするた
めの値である０第５図の例示された々ツピングのハツシ
ュ・クラスは、シリンダ及びトラック表示の行に対応す
る０例えば、１つのハツシュ・クラスは装置り、Ｏのア
ドレス６６０、装置Ｄ１のアドレス３３０、装置Ｄ２の
アドレス０００より構成され、装置Ｄ３については、；
−ントリイは存在しない。小さな５ＩＴ２７では、ハツ
シュ・クラスは装置の各々から取られた１つ又はそれ以
上のトラックを含むことができる。装置ＤＯのシリンダ
ＣＯは、トラックＤＯ−０９を有する６５０部分如上っ
て示される０装置ＤＯのシリンダＣ１もトラック０−９
を有するが、これらのトラックは１０−１’９によって
示される。同様に、装置ＤＯ内の全てのトラックは、そ
れぞれのシリンダによって表示される。５ＩＴ２７は比
較的に大きく、１つのノ＼ツシュ・クラスは所与の装置
から取られた１つだけのトラックを含む０実施例の場合
、装置オフセットは６６で示されるように３シリンダで
ある。重複はない０即ち、５ＩＴ２７のサイズに関して
は、比較的小さな装置が存在する０装置Ｄ１のシリンダ
ＣＯは６７のところに現われ、装置Ｄ２のシリンダＣＤ
は６８のところに現われる。この編成は第３図及び第４
図の装置配分に従ったものであって、如何なる装置の。

シリンダＣＯも他の装置のシリンダｃｔ２とハツシュ・
クラスを共用しない。装置Ｄ２において、数字７０は５
つのシリンダ装置オフセットを指定するが、数学７１は
空のスペースを示す＠即ち、５ＩＴ２７のこのスペース
は、装置Ｄ２のためにトラック・アドレスを含まない。

他方、ＤＡ８Ｄ１１のサイズに関して小さな５ＩＴ２７
の場合、各ハツシュ・クラスは、各装置から取られた２
つのトラック、各装置から取られた３つのトラックなど
を含むことができる。前と同じように、如何なる装置の
シリンダＣＯも、他の装置のシリンダＣＯから得られた
ハツシュ・クラスを共用しない０この原理を拡張すれば
、同じようにアドレスされるシリンダは、同じノ１ツシ
ュ・クラスの中にはないと言える０即ち、成る装置のシ
リンダＸは、常に他の装置のシリンダＸとは異ったノ１
ツシュ・クラスの中にある。ここで、Ｘはシリンダ・ア
ドレスを示す整数もある・ 第６図はハツシュ回路６４を示す論理図である０ハツシ
ュ回路３４は、８４に８ＩＴ２７のレジスタ・アドレス
を出力する演算回路であるＯこのレジスタ・アドレスは
、５ＩＴ２７にあるレジスタの数を法とする数値を有す
るノ・ツシュ・クラスを指定する。計算は、７５でシリ
ンダ・アドレスＣを２進乗算器７６へ与えることによっ
て開始される・乗算器７６は７７で受取られたシリンダ
ーウェイトＣＷとＣとを乗算するＱシリンダ・ウェイト
は、装置中のシリンダの数であ今。結果の積＆ム加算器
７８において、線７９を介して与えられたトラック・ア
ドレスＨへ加えられるＯこの積の和はモジュｐＮ加算器
８０へ与えられるＯ加算器８０でをキ・上記の積の和が
装置オフセット積へ加えられる０装置オフセツト積は、
それぞれ８２及び８３で受取られた装置番号り及び装置
ウェイ）ＤＷから構成される装置ウェイトはＤＡＳＤｌ
ｌの数である。８４で得られる１９ＩＴ２７のアドレス
信号は、ハツシュ・クラスに対するディレクトリイ３０
のインデックスをフェッチするため）ＳＩＴ２７ヘアク
セスする〇 第７図は第１図に示され−るシステム１００ノ）ツシン
グ動作を詳細に示す。装置アドレスＣＨＤ　（Ｃ・・・
・シリンダ、Ｈｌｌ・・Ｏヘッド、Ｄ・・・・装置）は
スイッチ１６を介して旧ハツシュ回路２５へ送られる。

更にレコードＲＱアドレスが与えられる。

これはハツシング・プロセスの１部ではない◎何故なら
ば、ＤＡＳＤｌｌのトラックの全ての内容がキャッシュ
１２へ転送されることができるからである・レコードが
ＤＡＳＤｌｌの中で別個にアドレス可能である場合、レ
コード番号Ｒはハツシング・アルゴリズムの中へ導入さ
れることができる０アドレスＣＨＤは比較回路９０へ与
えられる。

比較回路９０は、ＣＨ値の比較を行う◎即ち、バス８９
を介してレジスタ９１へ与えられたＤアドレス信号によ
って選択されたレジスタ９１の内容の１部であるＣＨ値
と比較する。Ｃが等しい場合（トラックが同一シリンダ
にある場合、比較回路９０は差異信号を加算器９２へ与
える。差異信号は、スイッチ１６から受取られたＨ値と
、レジスタ９１に記憶されたＨ値との差を示す。この差
は、レピスタ９１に記憶されたＳＩＴアドレスへ加えら
れる。それは、第６図に関して説明したようにハツシン
グすることな（ＣＨＤのためにＳＩＴア。

ドレスを発生す谷ためづあも。上記の差の値に前のＳＩ
Ｔアドレスを加えたものは、シリンダ内のトラックに関
してディレクトリイ３０へのインデックスを含む５ＩＴ
２７のレジスタを指定する０従って、シリンダ内の全て
のトラックについて、１度シリンダがアクセスされると
、〕蔦ツシュ結果が一時的に保存される場合、それ以上
のノ・ツシングは′必要でない。旧ＳＩＴアドレスに差
異を加えた合計は、ＯＲ回路９３を介して５ＩＴ２７を
アドレスするためそこへ与えられる。アドレスされた５
ＩＴ２７のレジスタの内容は、バス９５を介してディレ
クトリイ３０をアドレスするためそこへ与えられる。Ｓ
　ＴＴ２７のレジスタ内容が全てゼロである場合、キャ
ッシュ・ミスが表示されるＯＪ％−ｖ　タｙ、ｘ）ンダ
がアクセスされていることを比較回路９０が表示すると
、新しいノ・ツシュが起る０アドレスＣＨＤはバス９６
を介してハツシュ回路３４へ寿えられる。バス９６は第
６図の線７５へ接続される◎ハツシュ回路３４は、ＯＲ
回路９３を介してＳ　ＩＴ２７をアドレスするため、バ
ス５５へ５ＩＴ２７のアドレスを出力する０新しくノー
ツシングされたＳＩＴ値はレジスタ９１に入れられる。

このレジスタは、バス８９を介して送られたＤ値によっ
て指定される。

゛バス９５にあるディレクトリイ３０のアドレス信号は
、エントリイ・レジスタ１００の１つを為ディレクトリ
イ３０におけるノ蔦ツシュ・クラスの゛　　　最初のエ
ントリイとして選択する。アクセスされたレジスタは、
バス１０１を介して比較回路１０２へＤＣＨ値を与える
。比較のためレコード値Ｒが与えられる場合、レジスタ
１００のフィールド１１１にあるレコード値も比較回路
１０２へ与えられる。比較回路１０２は、レジスタ１０
０に記憶されたＤＡＳＤアドレスとパス１０３上で受取
られた゛ナトレスとを比較する０比較が不等価であれば
、比較回路１０２は、ＨＬフィールド１０７にアクセス
量るため、バス１０６を介してアクセス信号を送る。Ｈ
Ｌフィールド１０７は、単−的にリンクされたリストの
１部分である。この部分は、同一ハツシュ・クラスのエ
ントリイを含む次のレジスタ１００のアドレスを指示す
る。次のレジスタ１００は、線３１によって示されるよ
うにアクセスされるｏ　ＨＬフィールド１０７がＥＯＣ
（連鎖の終り）を示す時、線１０８上にミスが表示され
る。

線１０８は第１図の線３６に対応する〇比較回路１０２
が等価を示す時、キャッシュ１２のヒツトが起って〜・
る。比較回路１０２によって線１０４へ与えられた信号
は、アドレス発生器１０５を能動化する。アドレス発生
器１０５はバス１０６１からディレクトリイ６０のアド
レスを取り（バス９５又はｌ（Ｌフィールド１０７を介
するアクセス）、このアドレスに基いてキャッシュ１２
のアドレスを発生する。キャッシュ・アドレスは、キャ
ッシュ１２にアクセスするため、バス３２へ与えられる
。アドレス発生器１０５は、キャッシュ１２のオフセッ
トΦアドレスを計算するため、レジスタ１００のオフセ
ット・アドレスに成る定数をかけあわせる。この定数は
、エン）　ＩＪイ・レジスタ（八ツシュ０レジスタ）１
００にオケルバイト数に対するキャッシュ１２中のアド
レス可能セグメントのバイト数の率を示す値である０次
に１キヤツシユ１２のオフセットがキャッシュ１”） ２のアドレスが得られる０計算する代りに、各ディレク
トリイに対する計算結果を、各ディレクトリイ・エント
リイと共に１物理的又は論理的に記憶することもできる
◎ デイレク゛トリイ３０はフィールド１１１，１０７の外
にインデックス・フィールド１１０を含む〇フィールド
１（０はディレクトリイ・エントリイを指定するのに有
用である◎フィールドー１１２はレコードＲのセクタ値
を含み、フィールド１１３は論理シリンダ数を含み（例
えばリアル・ディスク上の仮想ディスク属対して与えら
れる）、フィールド１１４は本発明の理解に無関係の種
々の制御フラグを含む＠フィールド１１５及び１１６は
、それぞれＬＲＵ（ｌｅａｓｔ　　ｒｅｅ、ｅ、ｎｏｔ
ｊｌｙ　　ｕｓｅｄ）リストにおける後方ポインタ及′
び前方ポインタ及び後方ポインタを示す・このリストは
、バッファ管理技術において周知の如く、キャッシュ１
２のスペース管理に関連して使用される◇ 第８図は本発明の実施例を示す。ＤＡＳＤｌ　１の２つ
のストリングは、キャッシュ１２と通信すると共に入出
力接続線１３を介してホス゛ト（図示せず）と通信する
。入出方接−線はチャネル−アダプタ１２０　（ＣＡＡ
、ＣＡＢ、ＣＡＣ，ＣＡＤを含む）によって制御される
◎これらのチャネル・アダプタはＩＢＭ３７０シリーズ
・コンピュータで使用される入出力接続論理設計を採用
しているふプロセッサ１２１は、バス１２２及びチャネ
ル・アダプタ１２０を介してホストと通信する。

例えば、ホス）Ｋよって与えられた周辺指令は、バス１
２２を介してプロセッサ１２１へ転送される・プロセッ
サ１２１は、バス１２３を介してシステム・ストレージ
１２４とも通信するＯシステム・ストレージ１２４Ｉｉ
７′キヤツシユ１２１デイレクトリイ３０．５ＩＴ２７
を含む０システム・ストレージ１２４は、半導体で構成
された高速ランダム・アクセス・メモリであることが望
ましい◎キャッシュ１２．５ＩＴ２７％及びディレクト
リイ３（ｌ対する全てのアドレシングは、ベースΦアド
レスにオフセットを加えることにより行われるＯ プロセッサ１２１はバス１３０を介してＤＡＳＤｌｌと
通信する・バス１３０はデータ・フニー回路１３１及び
装置アダプタ１３２，１３２’へ延長される。装置アダ
プタ１３２，１３２’　　の各々はＤＡＳＤｌ１の１つ
のストリングを制御すると共にそれにアクセスし、既知
の技術を使用して構成されている・データ・フロー回路
１３１は直列化器、その他ディスク配憶装置で通常使用
される回路を含むことができる。ＤＡＳＤｌｌへ直接に
アクセスするため、データ・フロー回路１６１とチャネ
ル・アダプタ１２０との間に）くス１３３が設けられる
。バス１３４は、データ・フロー回路１３１をシステム
・ストレージ１２ｊｌ（従ってキャッシュ１２）へ接続
する。バス１３５はシステム・ストレージ１２４をチャ
ネル・アダプタ１２０へ接続する・第１図のスイッチ１
．！ｓの機能は１既知の電子技術を用いてチャネル・ア
ダプタ１２０の中で実行され、スイッチ１８の機能は１
データ・フロー回路１３１の中で実行される０プロセツ
サ１２１は制御ストレージ１４０を有する◎制御ストレ
ージ１４０は高速ランダム・アクセス・メそりであり、
ハツシュ回路３４０機能ケ実行するマイクロコード形コ
ンピュータ・プログニアＡ３４Ｐを含む。制御ストレー
ジには、ＬＤＣＢレジスタ２５Ｐも含まれる。更に、記
憶システム１０′を通常の態様で制御するため、他のプ
ログラム１４１が含まれている。他方、プロセッサ１２
１は、マイクロコードの実行速度を早めるため、複数の
高速レジスタ１４２を含む０レジスタ１４２は、プロセ
レサのために１スクラツチ・パッド又は作業スペースを
形成する◎ＳＩＴレジスタ１４３は５ＩＴ２７の１ペー
ジを含み、この１ページはプロセッサ１２１によって処
理される。

即ち、１度プログラム３４Ｐがプｐ、セッサ１２１によ
って実行されると、ハツシュの１つ又は２つのシリンダ
に対応する５ＩＴ２７の１ページがレジスタ１４３へ転
送さｔ１旧ハツシュ回路２６の手法が実行さｎる。更に
、ディレクトリイ６０の探索は、ディレクトリイ・レジ
スタ１４４に対するディレクトリイ・エントリイの１ペ
ージの転送を生じる。それは迅速処理を達成するためで
ある。このようにして、制御目的のためのシステム・ス
トレージ１２４のアクセスは最少にされるので、データ
処理信号の転送と、プロセッサ１２１による制御処理が
重複して実行される。４つのチャネル・アダプタが設け
られるので、４つの異った動作が同時に実行されてよい
。更に、独立した動作がＤＡＳＤｌｌによって実行され
ることができるので、プロセッサ１２１は、できるだけ
システム・ストレージ１２４から独立して処理を実行す
ることができなければならない。第８図に示される装置
の動作は第９図乃至第１１図を参照して、より良（理解
することができる。注意すべきは、プログラム１４１が
、プログラミング及びデータ処理技術において周知の遊
び走査又はディスパッチング機能を含むことである。

第９図に示されるＬＤＣＢレジスタ２５Ｐは、キャッシ
ュ１２の特定のアクセスに関連したＤＡＳＤｌｌのアド
レスを含む。例えば、フィールド１５０に含まれるシー
ク・アドレスはシリンダを限定し、フィールド１５１及
び１５２にあるＳＩＤアドレス及びセクタは、ＤＡＳＤ
ｌｌでどのトラック又はトラック部分がアクセスされる
べきであるかを指定する０フイールド１５３のインデッ
クスは第７図のフィールド１１０にあるインデックスに
対応する。フィールド１５４のキャッシュ・アドレスは
、アドレス発生器１０５及びプログラム１４１によって
発生されたキャッシュ・アドレスである。フィールド１
５５にあるシーケンス・ビットは、連続的にアドレスさ
れる一連のブロックがシーケンシャル・モードで転送さ
れることを示す。シーケンス−ビットは、ホストから受
取られたモード設定指令によってセットされるＯモード
設定指令は、システム１０によって実行されるべき動作
の種類を示す。省略符号１５６はレジスタ２５Ｐが本発
明の理解には関連のない他のエン）　＋１イを含んでよ
いことを示す０次に第１０図を参照すると、そこにはプ
ログラム２５Ｐによって実行される旧ノヘツシュ機能が
詳細なマシン動作のフローとして示される。マシン動作
の開始は１６０で始まるＯこれはプログラム２５Ｐの能
動化に対応する。最初のステップはレジスタ２５Ｐへア
クセスすることである。それＬフィールド１５５のシー
ケンス・ビットがセットされていてシーケンシャル・モ
ードを示すかどうかを決定するためである。成るブロッ
クがアクセスされる時、同一のシリンダ又は隣接したト
ラックにある次のデータ・ブロックがアクセスされる高
い確率が存在する。本実施例において、シーケンシャル
・モードで使用されるアドレスのみが、旧ハツシュ原理
を使用する。非シーケンシャル・モードの場合、プログ
ラム３４Ｐによって実行されるハツシュ動作が論理通路
２００を介して能動化される。ステップ１６１がシーケ
ンシャル・モードを示す時、プロセッサ１２１はレコー
ドＲに対する受信アドレスＲＤＣＨな内部レジスタＩＲ
（図示せず）へ転送する。１６３で、プロセッサ１２１
は、チャネル・アダプタ１２０を介して、受取られたア
ドレスＲＤＣＨと、そのアドレスに対して許さｎたアド
レス範囲とを比較する。即ち、ホストはｒｔ？！、囲限
定」指令を送り、この指令は、所与のチャネル・アダプ
タ１２０を含む所与のチャネル通路のためにアクセス限
界を設定する。もしアドレスＲＤＣＨが限定さｔたアド
レス範囲の外にあれば、プロセッサ１２１は論理通路１
６４をたどり、ホストへエラー状態を知らせる。

そうでなけｎば、１６６で、プロセッサ１２１は、受取
らｔたＲＤＣＨと、レジスタ９１の最後のアドレスとを
比較する。レジスタ９１は、第８図においてはレジスタ
１４２に含まｎろ。もし受取らｎたアドレスＲＤＣＨと
１／ジスタ９１にある最後のアドレスとの差が１まり大
きけｎば、論理通路２００を介してハツシュ動作が能動
化される。トランク・アドレスＨが１だけ異なる時、シ
リンダ境界と無関係にレジイタ９１の内容へ１が加えら
れる０それは５ＩＴ２７のアドレスを１だけ増加させた
り減少させたりするためである。隣接した５ＩＴ２７の
レジスタが、ハツシングなしにディレクトグイ３０ヘア
クセスできるように読出される。シーケンシャル・モー
ドでは、キャッシュ１２の複数のデータ・ブロックにア
クセスするため、１つのハツシュ動作のみが必要となる
〇 代替的方法として、比較ステップ１６６は、受取られた
アドレスＲＤＣＨがレジスタ９１に記憶されたアドレス
と同じシリンダにあるかどうかを決定するため、比較動
作を実行する◇その場合、受取られたアドレスと記憶さ
れたアドレスとの差異値は、５ＩＴ２７のレジスタのオ
フセット・アドレスを指示スる。これのレジスタは、受
取られたＲＤＣＨ及びレジスタ９１に記憶されたアドレ
スに対応するポインタを含む。次に、この差異値ハレシ
スタ９１へ加算されるか又はそこから減算され、ディレ
クトリイ３０をインデックスする５ＩＴ２７のレジスタ
が得られる。

本実施例において、データが必要とされる前に、そのデ
ータをキャッシュへ転送することは、所与のシリンダ（
即ち、遅延境界の所与の組）の中に存在するデータに限
ることとした。しかし、本発明の他の実施にあたっては
、このような制限は存在しない。１７０では、受取られ
たアドレスＲＤＣＨがレジスタ９１にある最後のアドレ
スと同じシリンダにあるかどうかを決定するため、シリ
ンダ境界が検査される。もしＲＤＣＨがシリンダの外に
あれば、プロセッサ１２１は１７１から論理通路１７２
をたどってミスを知らせる。即ち、プロセッサ１２１は
、データがキャッシュ１２へ転送されなかったことを知
る。他方、ＲＤＣＨがレジスタ９１に記憶されたアドレ
スと同じシリンダにあれば、１７３でディレクトリイ３
０のアドレスが５ＩＴ２７からフェッチされ、前述した
ハツシュ・クラスの探索が実行される。探索が終ると、
プロセッサ１２１は、１７４で、データがキャッシュ５
０にあるかどうかを決定する。例えば、５ＩＴ２７のエ
ントリイがオール−・ゼロであれば〜即時にミスが表示
される。そうでなければミデイレクトリイ５０のハツシ
ュ・クラスが順次に探索される。

ミスの場合、通常の割当て及びデータ転送の手順がとら
れる。ヒツトの場合、プロセッサ１２１は、１７５で、
データが固定（ピン）されるか、又はキャッシュ５０へ
送られ得るかを決定する０固定化（ｐ、ｊｎｎｉｎｇ又
はｂｉｎｄｉｎｇ）は、データが解放されるまで、キャ
ッシュ３０にとどまっていなければならないことを意味
し、従ってそのようなデータは置換アルゴリズムの対象
とならない０固定されたデータについては、論理通路１
８０がとられ、キャッシュ１２のデータに一アクセスし
又はキャッシュ１２にデータを記憶する準備を実行する
。データが固定されていなければ、１７６で、レコード
Ｒは置換アルゴリズムの中で最も近時に使用された（Ｍ
ＲＵ）データであるとされる０次に、論理通路１８０が
とられる・ 第１１図はプログラム５４Ｐの動作を示す０旧ハツシュ
動作を実行す′るプログラム２３Ｐ力ψなるシリンダの
アクセスを表示すると、プロセッサ１２１はステップ２
０１への論理通路２００をたどる０それは、レジスタ２
５ＰからアドレスＤＣＨをとり、それをレジスタ１４２
に置くためである０ステツプ２０２及び２０３は、第１
図のハツシュ回路′５４に対応する機能を実行する。ス
テップ２０２は、ステップ２０２に表示された等式に従
って５ＩＴ２７のアドレスを発生し、そのアドレスをレ
ジスタ１４２へ記憶する＠ここで注意すべきは５ＩＴ２
７の法の２倍の値が使用されていることである。即ち、
Ｎではなく２Ｎが使用されている＠２０３でハツシュ書
オフセット（ＨＯ）がレジスタ１４２の内容に等しくさ
れ、ハツシュ・シリンダ（ＨＣ）がレジスタ１４２の内
容を２で除算した値にされる。２０４で、システム・ス
トレージ１２４の中に含まれＨＯ及びＨＣＫよって指定
された５ＩＴ２７のレジスタ内容が、レジスタ１４５へ
転送される。２０５で、ＨＣに対応するレジスタ１４３
が、ディレクトリイ３０中のエントリイに対するポイン
タを得るため読出される。このエントリイはハツシュ値
に対応する。次にディレクトリイ３０は、ステップ２１
７から始まる探索ループ２１０の中で探索される。連鎖
の終り（ＩＯＣ，ハツシュ・クラスの終り）は常に２１
７で検出される。もし５ＩＴ２７がゼロのエントリイを
有すれば、連鎖の終りは２１７で表示される。

所与のハツシュ・クラス内でディレクトリイ３０を探索
するためには、ディレクトリイ３０の１部をレジスタ１
４４へ転送しなければならない。

この転送はディレクトリイ３０の探索ループ２１０内で
暗黙的に示される。ループ２１０は、比較回路１０２を
含む第７図に対応する。２１１ではディレクト・リイ６
０のエントリイが読出され、レジスタ１４４へ転送され
る。２１２で、ディレクトリイのエントリイに含まれる
ＤＡＳＤアドレスの値ＤＣＨが、ホストから受取られか
つステップ２０１でレジスタ１４艮に記憶されたＤＣＨ
値と比較される。

比較が一致しない時、走査は継続しなければならない。

従ってプロセッサ１２１は、検査されるべき次のデイレ
クトリイ５０のエントリイを指定するため、論理通路２
１５を通ってリンク・ポインタを読出す。

２１７では、リンク・ポイ、ンタの内容が検査され１そ
れが連鎖の終り（ＥＯＣ）であるかどうか決定される・
もし連鎖の終りであれば、キャッシュ・ミスが起ってお
り、２１８でレジスタ１４２のミス・フラグがセットさ
れる。このフラグは後にプロセッサ１２１によって使用
される０次にプログラムは通路２１４から出て、データ
処理技術で知られるように、指令の実行を続ける。ハツ
シュ・クラスが２１７で終らない場合、ステップ２１１
及び２１２が反復される０ループは・２１２でヒツトが
表示されるまで継続する。

キャッシュ・ヒツトが生じると、プロセッサ１２１は、
キャッシュ・アドレスを発生するため、論理通路１０４
を通ってステラｙ２１３へ進む＠ステップ２１５は第７
図のアドレス発生器１０５に対応する０キヤツシユ・ア
ドレスはレジスタ１４４にあるディレクトリイ５０のエ
ントリイのアドレスに基いて発生される。上記エントリ
イは、キャッシュ・アドレスを発生するため、所定の態
様で変更されている。即ち、キャッシュ１２のそれぞれ
のアドレス可能手グメントについてディレクトリイ３０
の１つのエントリイが存在、する０門って、空間的関係
を設定することができる０次Ｋ、エントリイ・レジスタ
１００におけるフィールド１１０のインデックスがレジ
スタ２５Ｐのフィールド１５５ヘセツトされる。またレ
ジスタ１４２にあるヒツト・フラグ（図示せず）がセッ
トさ執キャッシュ−１２の指定されたセグメントを最も
近時に使用されたセグメントとするため、エントリイ・
レジスタ１００におけるフィニルド１１５及び１１６の
後方ポインタ及び前方、ポインタを調整することＫよっ
てＬＲＵリストが更新される。ＬＲＵＩＪストの更新は
周知であり、従って説明を省略する◎受取られたアドレ
スＲＤＣＨ及び５ＩＴ２７のアドレスはレジスタ９１に
記憶される◎

【図面の簡単な説明】

第１図は本発明の装置を使用する階層記憶シス　□テム
のブロック図、第２８Ｊは本発明の装置で実行さレルハ
ツレユ・アドレシングに対するディスク記憶装置の構造
的関係を示す図、第３図及び第４図は第１図の階層記憶
システムで使用さ、れるスキャタ・インデックス・テー
ブルのアドレス・スペース内に配分されたディスク装置
のアドレスを示す図、第５図は第１図の階層記憶システ
ムが複数の装置を含む場合のハツシュ・・アドレス配分
を示すマツプ、第一回は第１図に示されたシステムの中
でハツシュ方法を実行する゛回路の論理図、第７図は本
発明の装置で使用されるディレクトリイの構成及び関連
した制御回路を示′す図、第８図は本発明の代替的実施
例を示す図、第９図は第８図のシステムと結合して使用
される１理装置制御ブロツク（ＬＤＣＢ）のデ、−タ輌
成を示す図、第１０図は第８図に示されるシステムにお
いて遅延アクセス境界内のシーケンシャル・トラックの
ハツシングを避けるマシン動作を示す論理フロー図、第
１１図は第８図に示されるシステムにおいてハツシング
実行方法を示す論理フロー図である０１０・・・・・・
階層周辺記憶システム、１１・・・・直。 接アクセス記憶装置、１２・・・・キャッシュＳ２０会
・・Ｏコントロール、２５・０・旧ハツシュ回路、２５
・・・・論理装置制御ブロック（ＬＤＣＢ）レジスタ１
２７・・・・スキャタ・インデックス・テープ−（ＢＩ
Ｔ）、５０−・・拳ディレクトリイ、３４・・・・ハツ
シュ回路。

Claims (1)

1. 【特許請求の範囲】 それぞｎが複数のアドレス可能メモリ・セグメントを有
   する複数のアドレス可能ユニットを有するバッキング・
   ストアと、該バッキング・ストアのためのバッファとし
   て使用されるアドレス可能バッファ・セグメントを有す
   るバッファ・メモリとを具備する記憶システムにおいて
   、与えらｎたバッキング・ストアのアドレスに応答して
   上記バッファ・セグメントをアドレスするだめの、下記
   構成要件（イ）−（ホ）を有するアドレシング装置。 （イ）上記メモリ・セグメントに関連した記号及び上記
   アドレス可能ユニットのアドレス及び上記メモリ・セグ
   メントのアドレスを記憶した上記バッファ・セグメント
   のアドレスを含むディレクトリイ・ユニット。このディ
   レクトリイ・ユニットは複数のアドレス可能エントリイ
   を有し、該エントリイの各々は上記メモリ・セグメント
   の成る所定の数のアドレス・クラスを表示するため上記
   所定の数に等しいリンク手段を含む０（ロ）上記リンク
   手段のそれぞれのアドレスを記憶するため、上記所定の
   数に等しいアドレス可能レジスタを含むインデックス・
   テーブルＯこのインデックス・テーブルを介して、上記
   エントリイの各々が、ベース・アドレスから成る限界ア
   ドレスまでの一連のアドレスを含むアドレス・スペース
   内でアドレスされる。 ｒｌ　　上記アドレス可能ユニットのアドレス及び上記
   メモリ・セグメントのアドレスを含む上記バッキング・
   ストアのアドレスを受取って、上記インデックス・テー
   ブルに含まれるアドレス可能レジスタの１つのアドレス
   を発生する手段０この発生されたアドレスは、上記所定
   の数を法とするアドレス値を有するとともに、上記ベー
   ス・アドレスからのアドレス・オフセット値と、該アド
   レス・オフセット値からのアドレス変位値とを有し、上
   記アドレス・オフセット値は、上記所定の数と上記アド
   レス可能ユニットの数との組、合せに基き上記アドレス
   可能ユニットのアドレスを変更することによって決定さ
   れ、上記アドレス変位値は、上記メモリ・セグメントの
   アドレスと等しい。 に）上記発生されたアドレスに応ｓして、上記インデッ
   クス・テーブルの１つのアドレス可能レジスタ誉アドレ
   スし、このアドレスされたレジスタの内容に基いて上記
   ディレクトリイ・ユニットの゛アドレス可能エントリイ
   の１つをアドレスする手段。 傍　上記バッキング・ストアのアドレス及び上記゛　ア
   ドレスされたエントリイに記憶され′た信号を受取って
   、アドレスされたメモリ・セグメントに関連するバ、ツ
   ファ１セグメントのアドレスを決定する手段。