JPH0337218B2 - - Google Patents

Description

【発明の詳細な説明】 Ａ 産業上の利用分野 本発明は、一般に計算機のメモリ組織に関する
ものである。具体的にいえば、誤り検出のための
カタログ式メモリ用の冗長ページ識別に関するも
のである。

Ｂ 開示の概要 本発明ではキヤツシユ・メモリ用の冗長な誤り
検出アドレツシング・コードが開示される。デイ
レクトリは、論理データ・アドレスをデータがブ
ロツクとして記憶されているキヤツシユ中の物理
アドレスに変換する。本発明のブロツクは、論理
データ・アドレスや物理キヤツシユ・アドレスな
どの冗長アドレツシング情報を含むように拡張さ
れる。キヤツシユからあるブロツクにアクセスす
ると、冗長アドレツシング情報をデイレクトリ・
アドレツシング情報と比較して、正しいデータに
アクセスしたことを確認する。

Ｃ 従来技術 計算機システムは、典型的な場合、メモリのア
ドレスによつてそのメモリにアクセスする。簡単
な計算機メモリでは、各記憶位置が一義的なアド
レスを持つており、読取りまたは書込みのために
そのメモリの内容にアクセスするとき、計算機は
所望の位置と一義的に関連するアドレスをもたら
す。しかし、さらに高度な計算機メモリ・システ
ムでは、カタログ式メモリを使用している。カタ
ログ式メモリとは、カタログ式メモリの物理記憶
位置が、その時々に異なるアドレスのデータに割
り振られるものである。その際、所望データの物
理記憶位置とアドレスの対応をつけるため、デイ
レクトリと呼ばれる追加メモリがメモリ・システ
ムに含められる。すなわち、処理装置がカタログ
式メモリにアクセスすることを希望する場合、ま
ずデイレクトリに照会して、アドレスされたデー
タが現在カタログ式メモリのどの物理位置に記憶
されているかを決定する。カタログ式メモリの最
も普通の例は、キヤツシユ・メモリである。キヤ
ツシユ・メモリは、典型的な場合、比較的高速の
メモリで、より大型であるがかなり低速の大容量
記憶装置に連結されている。しばしば、2048バイ
トが、１ページという形で表される大量のデータ
のブロツクが、大容量記憶装置からキヤツシユ・
メモリに転送される。デイレクトリは、大容量記
憶装置のアドレスされた位置がキヤツシユ・メモ
リのどこに記憶されるかについての情報を含んで
いる。その後、処理装置がメモリにアクセスを希
望するときは、低速の大容量記憶装置ではなく
て、高速のキヤツシユ・メモリにアクセスする。
ある時点でキヤツシユ・メモリの内容が大容量記
憶装置に転送され、デイレクトリが更新された
後、キヤツシユのその記憶域を大容量記憶装置の
別のページ用に使うことができる。

計算機アーキテクチヤにおける最近の発展は、
デイスク記憶装置にキヤツシユ・メモリを追加す
ることである。デイスク・キヤツシユは、二重の
目的に使われる。これは、低速のデイスクと高速
の計算機バスの間のバツフアとして働き、かつ処
理装置がずつと低速のデイスクに独立にアクセス
する必要なく、デイスク・キヤツシユにランダム
にアクセスすることができる。この種のデイス
ク・キヤツシユは、米国特許出願第270951号に開
示されている。

デイスク・キヤツシユを備えた計算機システム
を、第１図のブロツク・ダイアグラムに示す。処
理装置が、半導体メモリ・チツプの主記憶装置１
２と連結している。入出力チヤネル１４が処理装
置１０を複数のキーボード端末、表示端末１６お
よび入出力制御装置１８に接続している。この入
出力制御装置１８は、それぞれ容量200メガバイ
トの４個のデイスク装置２０をサポートする。デ
イスク２０と処理装置１０の間のデータ記憶およ
びデータ流れの管理は、マイクロプロセツサ２２
が、その読取り専用記憶装置２４中の制御プログ
ラムと、さらにランダム・アクセス記憶装置２６
を使つて行う。

ハンドシエーク論理２８がマイクロプロセツサ
２２と処理装置１０の間の相互作用を実現し、そ
れと同様のハンドシエーク論理３０がデイスク装
置２０との間で同様の相互作用を実現する。

ハンドシエーク論理は、単一のデータ転送経路
を使う複数のソースからの要求を解決するための
手段である。複数ソースのうちの一つまたはいく
つかが、同じ時点にその経路を使う許可を要求す
る。ハンドシエーク論理中の所与の中央制御装置
が、これらの衝突する要求を解決し、どの装置に
データ転送経路を使われるかについての許可を与
える。アクセスを許可する際に、どんな特定の優
先順位を使うかは本発明にとつて重要ではない。
特定の装置に許可が与えられると、その装置はデ
ータの転送を始める。すなわち、ある装置からの
データ転送には、かならずその装置からの要求と
それに続くその装置への許可が先行する。ハンド
シエーク２８および３０は、当業者には周知の
様々な方法で実現することができる。

マイクロプロセツサ２２は、高速制御ハードウ
エア３２によつて入出力制御装置１８の論理を制
御する。データ・レジスタ３４が入出力制御装置
１８と入出力チヤネル１４の間でデータを緩衝
し、もう一つのレジスタ３６がデイスク装置２０
に対する緩衝をもたらす。キヤツシングを望まな
い適用業務では、相互接続バス３８で相互接続さ
れたデータ・レジスタ３４と３６を介して、処理
装置１０とデイスク装置２０のうちの１個との間
で直接にデータを転送することができる。容量
384キロバイトの半導体キヤツシユ記憶装置４０
が、それ自体のデータ・レジスタ４２を経て、追
加相互接続バス４４と４６によつてデータ・レジ
スタ３４および３６に接続されている。ランダ
ム・アクセス記憶装置２６は、現在キヤツシユ４
０に記憶されているデイスク装置２０の記憶スペ
ース・ページ用のデイレクトリ専用である。もち
ろん、ポーター（porter）の米国特許第4225992
号に開示されているような、その他の型式のキヤ
ツシユ制御装置も可能である。

通常の一連の操作では、処理装置が１個のデイ
スク装置２０のページにアクセスする。そのペー
ジと普通はその前後の１ページないし数ページ
が、アドレスされたデイスク装置２０からキヤツ
シユ４０に転送される。次に要求された１ページ
が、さらにキヤツシユ４０から処理装置１０に転
送される。その後のアクセスの際には、ランダ
ム・アクセス記憶装置２６中のデイレクトリに照
会して、要求されたページが現在キヤツシユ４０
に入つているかどうかを確認する。入つている場
合は、デイスク装置２０に対する物理アクセスは
なく、アクセスはキヤツシユ４０に対して直接行
われる。

ある時点で、キヤツシユ４０は一杯になり、デ
イスク装置２０の新しいページにさらにアクセス
するには、キヤツシユ４０のページの一部を、キ
ヤツシユ４０から取り除いて固有デイスク装置２
０に移す必要がある。デイクソン（Dixon）等
は、キヤツシユされたページのうちのどれをキヤ
ツシユ４０から取り除くべきかを決定するための
効率的アルゴリズムを記載している。もちろん、
キヤツシユ４０からあるページを取り除いて別の
ページを入れる場合は、ランダム・アクセス記憶
装置２６中のデイレクトリを更新する必要があ
る。

384キヤバイトのキヤツシユ記憶装置４０は、
393、216バイトのデータ記憶容量をもち、第２図
の表に示されているように、２キロバイト（2048
バイト）のページに編成されている。すなわち
384キロバイトのキヤツシユ４０は192ページ分の
データを含むことができ、各ページは２進境界に
配列されている。データは、一度に１バイトずつ
データ・レジスタ３４，３６を経て転送されるの
で、キヤツシユ記憶装置４０にランダムにアクセ
スするのに必要なアドレツシング・ビツトは合計
19ビツトである。しかし、２進境界配列すなわち
2048＝2¹¹のため、アドレツシング・ビツトの高
位８ビツトがページを識別し、低位11ビツトがそ
のページ内のバイトを指す。この配列は、１度に
１ビツトずつページ全体にアクセスすることにつ
いて、自明の利点を持つている。

第２図に示したページ番号は、キヤツシユ・ペ
ージ番号であることを強調しておかねばならな
い。デイレクトリは、キヤツシユ・ページ番号を
デイスク・ページ番号、すなわちキヤツシユ中の
データの起点またはその宛先である、デイスク装
置２０中の位置と関係づける表を含んでいる。デ
イクソン等は、前掲の特許で、容易に更新できる
効率的なデイレクトリ組織を提供している。デイ
レクトリは、キヤツシユされたデータに正しくア
クセスするための唯一の手段なので、上記のキヤ
ツシユ・メモリ・システムにとつて非常に重要な
構成要素であることは自明のはずである。

第１図に示したデイスク・キヤツシユは、デイ
スク・フアイルと計算機システムの残りの部分と
の間のデータ流れを大いにスピードアツプするこ
とができる。しかし、キヤツシユされたデータを
使うと、新しい種類のシステム・エラーが入つて
くる。現代の計算機では、電子信号の誤差限界が
低すぎるため、フラグがつかず訂正されない偶然
の誤りが受諾できないと一般に考えられている。
記録されたデータは、データ回線上の雑音およ
び、書込み、記憶、読取り中の媒体に関係する欠
陥によつて損傷を受けることがある。データ・エ
ラーの問題は、従来パリテイー検査、CRC（巡回
冗長検査）、ECC（誤り訂正コード）を使つて対
処してきた。従来はデータ経路がかなり短かかつ
たため、この種の検査および誤り訂正法が効果的
に働いた。データ・バツフアは本来順次式で、デ
ータ順序が変わる機会はほとんどなかつた。しか
し、キヤツシユ・メモリの導入により、データ組
織がカタログまたはデイレクトリに依存するよう
になつた。キヤツシユ中のすべてのデータは、既
にパリテイー検査されており、CRCまたはECC
を使う場合は、誤りが訂正できる。しかし、キヤ
ツシユ中の間違つたページがアドレスされた場合
は、このようなデータ検出やデータ訂正は何の役
にも立たない。データ自体には誤りがなく、間違
つたデータだというだけである。

キヤツシユの操作しやすさの一般的テスト法
が、ジヨイス（Joyce）等の米国特許第4190885
号およびザルツ（Saltz）等の米国特許第4357656
号に記載されている。これらの方法は、通常のア
ドレツシングとは別のテスト・アルゴリズムを含
んでいる。

もちろん、デイレクトリを含むメモリに対して
誤り検出および誤り訂正を行うことは可能であ
る。シエルベルグ（Shelberg）等は、米国特許
第4084236号で、デイレクトリに含まれるアドレ
ス用の検査ビツトを使つて、無効アドレスを検出
できるようにすることを開示している。レデイ
（Ready）は、米国特許第3840862号で、デイレク
トリ中で追加タグを使用することを開示してい
る。このタグを使つて、無効キヤツシユ位置を検
出することができる。チヤン（Chang）等も、米
国特許第4197580号で、デイレクトリ中に妥当性
ビツトを使用することを開示している。ただし、
彼等の妥当性ビツトは、デイレクトリ内容が現在
有効であるかどうかを示すものである。フラナナ
シエク（Frananaszek）も、「IBM技術開示雑
誌」第25巻第５号、1982年10月刊、（IBM
Technical Disclosure Bulletin，Vol.25，No.５，
October，1092）の2621〜2622ページに所載の論
文「電子ドラムからの区分ページ転送」
（“Partitioned page Transfer from an
Electronic Drum”）で、デイレクトリ中の１種
の妥当性ビツトを開示している。デイレクトリ内
容に誤り検出コードまたは誤り訂正コードを付け
加えると、デイレクトリに入つた誤りを除去する
のに有用である。しかし、電気回線の雑音のため
に間違つたアドレスがデイレクトリ中で正しくコ
ード化されたり、正しいアドレスが雑音のある回
線上をキヤツシユ・メモリに転送されて正しいア
ドレスがキヤツシユ中で間違つたアドレスにアク
セスすることになつたりすることがある。上記の
どの特許も、この種の誤りを検出するのに有用な
方法を記載していない。最後に、デイクス・キヤ
ツシユに付随するキヤツシユ・アルゴリズムが非
常に複雑である。可能なコード経路が多すぎるた
め、コードの徹底的なテストが可能でない。その
結果、未知のコード・エラーが生じて、デイレク
トリとキヤツシユの間で不正確な通信が起こるこ
とがあり得る。

Ｄ 発明が解決しようとする問題点 したがつて、カタログ式メモリに加えられた誤
まつたアドレスの検出を実現することが、本発明
の一目的である。

可能な最大数の誤り発生源をカバーする、誤ま
つたアドレスの検出を実現することが、本発明の
第２の目的である。

Ｅ 問題点を解決するための手段 本発明は、カタログ式メモリ用の冗長アドレツ
シング・コードを提供する。デイレクトリ内には
カタログ式メモリの内容が完全に目録化されてい
る。さらに、カタログ式メモリの各ブロツクは、
デイレクトリに含まれる情報に対して部分的にま
たは完全に冗長なアドレツシング情報を含む、追
加アドレス・コーデイング・セクシヨンを含んで
いる。カタログ式メモリにアクセスする場合、デ
イレクトリに照会することによつて、カタログ式
メモリ中の正しいブロツクが得られる。次に冗長
アドレツシング・コードをデイレクトリ・メモリ
の内容と比較して、カタログ式メモリ中の正しい
ブロツクにアクセスしたことが確認される。

Ｆ 実施例 本発明によれば、キヤツシユ・メモリに記憶さ
れているデータの各ページには、ページ識別子が
ついているが、これはキヤツシユにアドレスする
ためデイレクトリに記憶されているものと同じ情
報の大部分を含んでいる。キヤツシユ・メモリは
第３図に示した表にもとづいて編成されている。
各ページは、２キロバイト（2048バイト）のデー
タを含んでいる。このデータはそれ自体エラー・
コーデイングを含むことができる。しかし、キヤ
ツシユ内のブロツクは、さらにアドレス・コーデ
イング・サブブロツク中に、データ・ページのア
ドレスを識別するためのページIDを含むように
拡張されている。その結果、各ブロツクは2048バ
イトから2052バイトに拡大される。上記で考察し
た同じ384KBのキヤツシユ４０の場合、本発明
では使用できるページ数は192から191に1/2％減
少する。本発明の難点は、ページ境界がもはや２
進境界でないことである。そのため、キヤツシ
ユ・メモリの高位８アドレス行の特定アドレス
が、必ずしもキヤツシユされた１つのページを指
さない。したがつて、キヤツシユされたデータの
指標付けがより難しくなるが、マイクロプロセツ
サ２２の追加指標付け作業は比較的僅かであり、
キヤツシユ・アルゴリズム時間はほとんど増加し
ない。

表１に、ページIDの書式を示す、最低位バイ
トであるバイト０は物理キヤツシユ・ページを識
別するもので、ここで説明する実施例では、０〜
190の範囲となる。もちろん、アドレスが正しい
場合は、バイト０の内容とアドレスは冗長である
ことを識別すべきである。その場合のページ識別
子の内容は、そのアドレス掛ける2052である。し
かし、データ・ページとそれに関連するページ識
別が、キヤツシユ中の間違つたブロツクに記憶さ
れている場合は、この対応が成り立たない。

ページ識別子の高位３バイトは、デイスク・ペ
ージに対応する。バイト１−３のビツト０−４は
０にセツトされている。これらのビツトはデイス
ク・ページを表すのには不必要で、最小量の誤り
検出しか行わない。ビツト５−６は４つのデイス
ク装置２０のデイスク・ドライブ番号を識別す
る。ビツト７−２３の17ビツトは、ページまたは
ブロツクの相対ブロツク・アドレス（RBA）を
識別する。

RBAの17ビツトは、４個のうち何れかの
200MBデイスク装置２０の各ブロツクを一義的
に識別する。この用途に使うRBAは、前記に引
用したデイクソン等の特許のRBAとは少し異な
ることに注意しなければならない。デイクソン等
のRBAは、デイスク装置２０の名称とさらにブ
ロツク内の８つのレコードのうちの一つの名称を
含んでいた。とはいえ、どちらのRBAもデイス
ク装置２０の物理記憶位置を指定する働きをす
る。

デイクソン等が記載したデイレクトリは、キヤ
ツシユ・ページとデイスク・ページの両方を指す
項目を含んでいる。デイクソン等のデイレクトリ
中のデイスク・ページ・ポインタは、指標付き追
加アドレス・ブロツクの使用を判つている。本発
明の場合は、デイレクトリを使つてデイスク・ペ
ージ・ポインタおよびキヤツシユ・ページ・ポイ
ンタを記憶し検索し、この２種のポインタを対応
づけることができると言うだけで充分である。こ
の項目は、さらに妥当性ビツトおよびデイレクト
リの効率的な更新を行うための他のデイレクトリ
項目に対するポインタを含んでいる。ページID
中のすべての有意な情報がこのデイレクトリにも
含まれており、このページIDがデイレクトリに
含まれるアドレツシング情報に対して完全に冗長
であることが重要である。

本発明のコンセプトにとつて、ページIDがそ
のページに対するデイレクトリ情報に対して完全
に冗長であることは不可欠ではない。例えば、ペ
ージIDがデイスク番号とそのページのRBAを含
んでいる場合でも、ページIDはキヤツシユに含
まれるメモリのページのアドレスを一義的に識別
することになる。その上、ページIDのエクステ
ントをさらに減らすして、少くともページ・アド
レスに対する若干の誤り検出を実現することが、
可能である。しかしながら、ページIDをそのよ
うに短縮してしまうと、ページ・アドレスが一義
的に識別されなくなり、その結果若干の誤りが検
出不可能になる。ページIDにキヤツシユ・ペー
ジを含めると、デイレクトリに含まれるキヤツシ
ユ・ページ・アドレス生成の際に起こる誤りを検
出することが可能になる。

本発明を用いて、キヤツシユ・メモリのアクセ
ス毎に、ページIDを、そのキヤツシユ・アクセ
スで使われるキヤツシユ・ページおよびデイス
ク・ページと対比して検査し、正しくキヤツシユ
されたデータがアクセスされていることを決定す
る。ページIDの使用例を、第４図の流れ図に示
す。説明を簡単にするため、処理装置からデイス
クへの直接アクセスは行われず、すべてのアクセ
スがキヤツシユ・メモリを介して行われるものと
仮定する。処理装置は、アクセスを行う際に、ア
クセスすべきデイスク・セクターを指定する。次
に入出力制御装置１８中のマイクロプロセツサ
が、このセクターの常駐するデイスク・ページを
決定し、その後マイクロプロセツサ２２がデイレ
クトリに照会して、そのデイスク・ページが現在
キヤツシユに常駐しているかどうかを決定する。
そのデイスク・ページがキヤツシユに入つていな
い場合、マイクロプロセツサは、キヤツシユ中の
使用可能ページのアドレスを生成し、デイレクト
リを再配列してその１つの項目中にそのキヤツシ
ユ・ページに対するポインタとデイクス・ページ
に対するポインタが含まれるようにする。キヤツ
シユ・ページを使用できるようにするには、通常
は既存のデータ・ページをキヤツシユから取り除
いてデイスクに移すことが必要である。次にマイ
クロプロセツサ２２がページIDを、デイレクト
リ中で指定されたキヤツシユ・ブロツクの始めに
記憶する。このページIDは、デイレクトリ中で
新しい項目を作成するのに使つたものと同じ情報
から生成される。

デイスク・ページが既にキヤツシユに入つてい
る場合は、マイクロプロセツサ２２はそのキヤツ
シユ・ページにどのキヤツシユ・ページが対応す
るのかをデイレクトリから決定する。上記のデイ
レクトリの決定と再配列は、前掲のデイクソン等
の特許に記載されている。

キヤツシユ・ページが決定されると、そのキヤ
ツシユ・ページがアドレスしたキヤツシユの位置
からページIDを読み取る。次にページIDをキヤ
ツシユ・ページおよびデイスク・ページと比較す
る。すべてのアドレツシング項目とデイレクトリ
項目が正しく作られていれば、ページIDはキヤ
ツシユ・ページおよびデイスク・ページと対応す
る。一致していることが決定されると、アクセス
は完了し、正しいデータがキヤツシユ中でアクセ
スされたことが信じられる。しかし、ページID
がキヤツシユ・ページまたはデイスク・ページの
どちらかと一致しない場合、何らかの種類の誤り
が起こつている。誤りがあれば、問題を解決する
ため適用業務プログラムにフラグされる。異なる
ページIDを使つてデイレクトリを再構成するこ
とも可能であるが、不一致があることは、基礎的
な問題があり、それが反復するかもしれないとい
うことなので、適用業務プログラムが、その後の
アクシヨンについて判断すべきであると思われ
る。

Ｇ 発明の効果 何れにせよ、アドレツシング情報をキヤツシ
ユ・メモリのアドレス位置に記憶されている冗長
コードと比較することによつて、アドレツシン
グ・デイレクトリまたはマイクロコードの問題点
が検出でき、キヤツシユ・メモリ中の間違つたデ
ータをアクセスすることが防止できる。最大数の
誤りを検出するには、ページIDを早期にマイク
ロコード・プロセス中で書き込み、次に処理の際
にできるだけ後に検査して、その間に起こるマイ
クロコードまたはハードウエアの誤りが検出でき
るようにすることを推奨する。

表 ページID（４バイト） バイト０−物理 キヤツシユ・ページ （０−190） バイト１−３− ビツト０−４＝０ ビツト５−６＝デイスク・ドライブ番号 ビツト７−23＝相対ブロツクアドレス （RBA）

【図面の簡単な説明】

第１図は、デイスク・キヤツシユを含む計算機
システムの構成図である。第２図は、通常のキヤ
ツシユ・メモリの組織を示す図である。第３図
は、本発明の冗長アドレス・コードを使つたキヤ
ツシユ・メモリの組織を示す図である。第４図
は、本発明の冗長アドレス・コードの使い方を示
す流れ図である。

Claims (1)

1. 【特許請求の範囲】 １ データ情報を記憶するためにメモリが複数の
   ブロツクに分割されていて、該データ情報が第１
   のアドレスによつてアドレスされ、該ブロツクが
   第２のアドレスによつてアドレスされ、デイレク
   トリが該第１アドレスと該第２アドレスを対応づ
   けるカタログ式メモリにおいて、 前記ブロツク中に、前記データ情報と共に、前
   記第１アドレスおよび前記第２アドレスから導か
   れた冗長アドレツシング情報を記憶しておき、 前記ブロツクへのアクセス操作が正しく行なわ
   れたかどうかを前記冗長アドレツシング情報を用
   いて確認するようにしたことを特徴とするアクセ
   ス操作のエラーを検出するための冗長アドレツシ
   ング情報を有するカタログ式メモリ。