JPH071489B2 - コンピュータ装置およびコンピュータ装置においてキャッシュデータアレイ内のデータの不一致を検出して修正する方法 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、各ユーザーがマルチ稼動プロセスを持つこと
ができるようにするオペレーテイングシステムを含む、
書戻しキヤツシユを有するマルチユーザーオペレーテイ
ングシステムにおいて仮想アドレツシングを用いるワー
クステーシヨンにおけるハードウエアおよびソフトウエ
アのある改良に関するものである。これに関連して、説
明の便宜上、特定のマルチユーザー、マルチ稼動プロセ
スオペレーテイングシステム、すなわち、Unix（商標）
（ユニツクス）オペレーテイングシステムに関連して本
発明を説明することにする。しかし、本発明ユニツクス
オペレーテイングシステムに関連して使用することに限
定されるものではなく、特許請求の範囲を、ユニツクス
オペレーテイングシステムのみに使用できる本発明をカ
バーするものと解すべきではない。

〔従来の技術〕

ユニックスをベースとするワークステーションにおいて
は、構成要素の１つとして仮想アドレス書戻し（write
back）キャッシュを含むことによりシステムの性能を大
幅に向上できる。しかし、そのようなシステムにおいて
は、エイリアスアドレス（すなわち、実メモリ中の同じ
物理アドレスへマップする２以上の仮想アドレス）のサ
ポートが問題となる。

相互にはエイリアスである２つの仮想アドレス（２つの
エイリアスアドレス）の一方を介して行われる書戻しキ
ャッシュへの任意のデータ更新は、他方のエイリアスア
ドレスからは、（２つのエイリアスアドレス自体は一致
していないのであるから）見えないのである。

更に詳しく言えば、仮想アドレスの利用により、エイリ
アシング、すなわち、複数の仮想アドレスを同一の物理
アドレスへマップすることが可能となる。ページマッピ
ングの限定なしに直接マップされる仮想アドレス書戻し
キヤツシュが用いられると、任意の２つの仮想アドレス
は任意の２つのキヤツシュ場所を占ることができ、か
つ、同一の物理アドレスへマップされる。キヤツシュブ
ロックが修正されても、任意のキヤツシュ場所の相互間
では、データの一貫性を保つためにチェックをすること
が通常できない。一方のキヤツシュ場所での変化が、他
方のキヤツシュ場所から見えないとき、データの一貫性
は失われる結果とになる。最終的には、主メモリの物理
アドレスにおけるデータには、CPUやI/O装置によりキャ
ッシュメモリに対して行われた修正の一部のみが、含ま
れるだけとなるという不都合を生じる。

〔発明の概要〕

本発明においては、上記問題は、エイリアスを取扱うた
めに２種類の戦略を組合わせることにより解決される。

第１の戦略は、エイリアスアドレスの下位アドレスビッ
トが同一であつて、キヤツシユの寸法を（最小として）
モジユロするようにエイリアスアドレスを作成すること
である。この戦略は、核により、または全面的に核で発
生されたエイリアスアドレスを用いる全てのユーザープ
ログラムに適用できる。この戦略に対するそれらのエイ
リアスアドレスは、核に対する修正により発生され、ユ
ーザープログラムには見ることができない。そのように
して発生されたエイリアスアドレスは、直接マツプされ
た（一方向にセツトされた関連）キヤツシユ内、または
多方向にセツトされた関連キヤツシユ内の同じキヤツシ
ユセツト内、の同じキヤツシユブロツクへマツプする。
そうすると、このキヤツシユブロツク（またはキヤツシ
ユセツト）内でのデータの一貫性を保証するために、エ
イリアスハードウエア検出ロジツクが用いられる。

第２の戦略は、下位のアドレスビツト中で一致させるこ
とができない、ユーザープログラムではなく、オペレー
テイングシステム内のそれらのエイリアスアドレスをカ
バーする。それらは、仮想アドレツシングを用いるワー
クステーシヨンにより採用されるメモリ管理ユニツト
（MMU）内の「キヤツシユしない」ページとしてそれの
ページを割当てることにより取扱われる。

〔実施例〕

以下、図面を参照して本発明を詳しく説明する。

第１図は、本発明が実現される仮想アドレスを用いる典
型的なワークステーシヨンの機能的なブロツク図であ
る。

とくに、そのワークステーシヨンはマイクロプロセツサ
すなわち中央処理装置（CPU）11と、キヤツシユデータ
アレイ19と、キヤツシユタグアレイ23と、キヤツシユヒ
ツト比較器25と、メモリ管理ユニツト（MMU）27と、主
メモリ31と、書戻しバツフフア39と、ワークステーシヨ
ン制御ロジツク40とを含む。そのワークステーシヨン
は、希望によつては、コンテキストトIDレジスタ32と、
キヤツシユフラツシユロジツク33と、直接仮想メモリア
クセス（DVMA）ロジツク35とと、マルチプレクサ37とを
含むこともできる。

上記の素子に加えて、本発明を実現するために、マルチ
プレクサ45と、エイリアス検出ロジツク47と、エイリア
ス検出制御ロジツク49と、実アドレスレジスタ51とを更
に必要とする。上記素子は、仮想アドレス書戻しキヤツ
シユを利用する従来の技術に固有の諸問題なしにエイリ
アスアドレスをサポートする。

各前記素子について、オペレーテイングシステムの核に
ついて行わなければならない変更を含めて、かつ、本発
明に独特の部品にとくに重点をおいて、説明することに
する。

ワークステーシヨンの必要な素子についての説明 CPU11は、メモリおよびおそらくは他の装置内の命令と
データを（アドレスの翻訳に続いて）アドレスするため
にバスサイクルを生ずる。CPUアドレス自体は、仮想コ
ンテキスト内の命令またはデータのバイトを独特に識別
する、寸法が（Ａ）ビツトの仮想アドレスである。バス
サイクルは、バスサイクルを独特に識別する１つまたは
複数の制御フイールドにより特徴づけることができる。
とくに、「タイプ」フイールドはもちろん、読出し／書
込み指示子が求められる。そのフイールドは、バスサイ
クルのためのアクセス優先権（すなわち、「スーパーバ
イザ」または「ユーザー」のアクセス優先権）はもちろ
ん、メモリの命令とデータのアドレス空間を識別する。
仮想アドレツシングを有し、マルチユーザーオペレーテ
イングシステムをサポートできるワークステーシヨンに
おいて利用できるCPUはMC 68020である。

書戻しキヤツシユを有する第１図に示す仮想アドレスワ
ークステーシヨンにおける別の必要な素子は、仮想アド
レスキヤツシユデータアレイ19である。これは２^Ｎ個の
データブロツクのアレイとして構成される。各データブ
ロツクは２^Ｍ個のバイトを含む。各ブロツク内の２^Ｍバ
イトは下位のＭ個のアドレスビツトにより独特に識別さ
れる。２^Ｎ個の各ブロツクは、次の下位のＮ個のアドレ
スビツトによりアレイ素子として独特にアドレスされ
る。仮想アドレスキヤツシユとして、キヤツシユ内の
（Ｎ＋Ｍ）ビツトのアドレツシングバイトは（Ａ＋Ｃ）
ビツトの仮想アドレス空間からのものである。（下記の
ように、（Ｃ）ビツトは選択により用いられるコンテキ
ストIDレジスタ32からのコテキストビツトである。）
（Ｎ＋Ｍ）ビツトは、翻訳されない（Ｐ）個のページビ
ツトに、仮想ページアドレスを定める（Ａ＋Ｃ−Ｐ）ビ
ツトからの付加された仮想ビツトである。

ここで説明する仮想アドレスキヤツシユデータアレイ19
は「直接マツプされる」キヤツシユ、または「一方向セ
ツト連想」キヤツシユである。このキヤツシユ構成を本
発明の説明のために用いるが、それは発明の範囲を限定
することを意味するものではなく、多方向セツト連想キ
ヤツシユに関連して使用することもできる。

第１図に示されている別の要求される素子は、キヤツシ
ユデータアレイ19内の各データブロツクごとに１つのタ
グアレイ素子を有する仮想アドレスキヤツシユタグアレ
イ23である。したがつて、タグアレイは２^Ｎ個の素子を
含む。第３図に示すように、各素子は有効ビツト（Ｖ）
と、修正されるビツト（Ｍ）と、２つの保護ビツト
（Ｐ）と、仮想アドレスフイールド（VA、希望によりC
X）とを有する。保護ビツト（Ｐ）はスーパーバイザ保
護ビツト（Supvsr Prot）と書込み許可ビツトで構成さ
れる。仮想アドレスフイールドの内容は、キヤツシユタ
グとデータアレイをアドレスするために用いられる下位
アドレスビツトとともに、（Ａ＋Ｃ）ビツトの全仮想ア
ドレス空間を独特に識別する。すなわち、タグ仮想アド
レスフイールドは（Ａ＋Ｃ）−（Ｍ＋Ｎ）個の仮想アド
レスビツトを含まなければならない。

キヤツシユ「ヒツト」ロジツク25は、仮想アクセスアド
レスを仮想アドレスキヤツシユタグアドレスフイールド
の内容と比較する。アクセスアドレス内では、下位のＭ
ビツトがブロツク内のバイトをアドレスし、次の下位の
Ｎビツトがキヤツシユ内のブロツクをアドレスし、残り
の（（Ａ＋Ｃ）−（Ｍ＋Ｎ））ビツトが、キヤツシユ
「ヒツト」サイクルの一部として、タグ仮想アドレスフ
イールドと比較する。

キヤツシユ「ヒツト」ロジツクは、オペレーテイングシ
ステムを共用するシステムに対して、ユーザー命令とデ
ータおよびスーパーバイザ命令とデータに対するアクセ
スを識別せねばならない。それらの要求を満す「ヒッ
ト」の定義が第2a図に示されている。その図には比較器
20と、アンゲート22と、オアゲート24と、アンドゲート
26とが示れている。

仮想空間内のアドレスを物理アドレスへ翻訳するMMU27
は別の要求される素子である。MMU27は寸法が（２^Ｐ）
バイトのページを基にして構成される。それらのページ
は寸法が（２^Ｓ）バイトのセグメントとしてまとめられ
る。ページ内でのアドレツシングには（Ｐ）ビツトを必
要とする。それらの（Ｐ）ビツトは翻訳を要しない物理
アドレスビツトである。MMU27の役割は仮想ページアド
レスビツト（（Ａ＋Ｃ−Ｐ）または（Ａ−Ｐ））を（M
M）ビツトの物理ページアドレスへ翻訳することであ
る。そうすると、複合物理アドレスは（MM）ページアド
レスビツトである。この場合、ページ当りのビツト数は
（Ｐ）ビツトである。

MMU27は保護チエツクのため、すなわち、アクセスバス
サイクルの優先権をページに割当てられた保護と比較す
るための場所である。この点を示すために、ページへ割
当てることができる２種類の保護、すなわち、スーパー
バイザ／ユーザーアクセス識別子と書込み保護／書込み
許可識別子がある。本発明はそのような種類の保護に限
定されるものではないが、このページ保護が与えられる
と、「ユーザー」優先権バスサイクルが「スーパーバイ
ザ」保護を有するページをアクセスするか、「書込み」
バスサイクルが「書込み保護」指示を有するページをア
クセスするならば、「保護の侵害」が行われる結果とな
ることがある。

MMUを介するMMU保護チエツクの適用が第2c図に示されて
いる。この図にはインバータ28と、アンドゲート30a,30
bと、オアゲート34と、アンドゲート36とが示されてい
る。また、仮想アドレス書戻しキヤツシユで保護チエツ
クの概念を、MMUをアクセスしないキヤツシユのみCPUサ
イクルまで拡張できる。そのようなキヤツシユオンリー
保護ロジツクが第2b図に示されている。この図にはイン
バータ42と、アンドゲート44a,44bと、オアゲート46
と、アンドゲート48とが示されている。

また、第１図には、物理アドレス空間内でアドレスでき
る主メモリ31も示されている。主メモリアクセスの制御
はワークステーシヨン制御ロジツク40を介して行われ
る。

書戻しバツフア39は、キヤツシユデータアレイ19からロ
ードされたキヤツシユデータの１ブロツクを含むレジス
タである。既存のキヤツシユブロツクを移動させる時に
は書込みバツフア39へ常にロードされる。これはキヤツ
シユブロツクを新しい内容で更新する必要で行わせるこ
とができ、またはブロツクをフラツシユしなければなら
ないために行うことができる。いずれの場合にも、出戻
しキヤツシユにおいては、既存のキヤツシユブロツクに
対するキヤツシユタグの状態は、このブロツクをメモリ
へ書戻すべきかどうかを決定する。下記のように、ブロ
ツクが有効で、修正されれたことをタグが示したとする
と、キヤツシユブロツクが移動させられる時に、ブロツ
ク内容をメモリ31へ書戻さなければならない。そのデー
タがメモリへ書込まれる前に書戻しバツフア39がそのデ
ータを一時的に保持する。

ワークステーシヨン制御ロジツク40は、第１図に示され
ているワークステーシヨン素子の全体の動作を制御す
る。好適な実施例においては、制御ロジツク40はいくつ
かの状態マシンとして構成される。それらの状態マシン
は第４図および第６〜８図に示されている。それらの状
態マシンについては、エイリアス検出制御ロジツク49の
説明とともに以下に詳しく説明することにする。そのエ
イリアス検出制御ロジツク49も、好適な実施例において
は、ワークステーシヨン制御ロジツクに統合できる。

ワークステーシヨンの選択的な素子の説明 コンテキストIDレジスタ32は、仮想コンテキストまたは
仮想プロセスを識別する別の仮想アドレスビツトを含む
選択的な外部アドレスレジスタである。Ｃビツトと含む
そのレジスタは全部で（２＊＊Ｃ）アクテイブユーザー
プロセスを識別する。全部の仮想アドレス空間の寸法は
２＊＊（Ａ＋Ｃ）である。

２＊＊（Ａ＋Ｃ）のこの仮想アドレス空間における重要
な部品は、オペレーテイングシステムにより占められる
仮想アドレススペースである。オペレーテイングシステ
ムは全てのユーザープロセスに共通であるから、アクテ
イブな全てのユーザープロセススにわたつて共通のアド
レス空間に割当てられる。すなわち、（Ｃ）コンテキス
トビツトは、オペレーテイングシステム内のページのア
ドレスを修飾するのに何の意味も持たない。それより
も、アクテイブな各コンテキストに対して、オペレーテ
イングシステムは、仮想アドレス空間の（２＊＊Ａ）バ
イトのトツプにおける共通の排他的領域内にあると仮定
される。ユーザーページはこの領域内に含れないことが
ある。したがつて、２種類のユーザープロセスに対する
オペレーテイングシステムページアドレスは同一であ
り、２つのプロセスに対するプロセスは異なる。オペレ
ーテイングシステム内の全てのページは「スーパーバイ
ザ」保護を有するものとしてマークされる。

本発明を利用できる種類のワークステーシヨンは、仮想
アドレスを再び割当てる時に、選択されたブロツクを仮
想キヤツシユから除去するためにキヤツシユフラツシユ
ロジツク333を含むこともできる。

この明細書においては、キヤツシユフラツシユロジツク
33は、仮想アドレス、書戻しキヤツシユシステムにおけ
る部品としての役割を示すことだけを説明する。ある範
囲のアドレス（たとえば、仮想ページアドレス）を再び
割当てるものとすると、その範囲内からのアドレスの全
ての例を、新しいアドレス割当てを行うことができるよ
うになる前に、キヤツシユから除去、または「フラツシ
ユ」せねばならない。キヤツシユブロツクのタグ内の有
効ビツトを無効にし、ブロツクが修正されたとすれば、
そのブロツクをメモリへ書戻すことにによりキヤツシユ
ブロツクが「フラツシュれる」。

バスサイクルのソースとしてのCPU11に加えて、ワーク
ステーシヨンは、DVMAロジツク35のような、１つまたは
複数の外部入力／出力（I/O）装置を含むことができ
る。それらの外部I/O装置はバスサイクルを生ずること
ができる。それらのバスサイクルは、仮想アドレス空の
１つまたは複数の「種類」をアクセスするのにCPUと並
列に行う。CPU11またはDVMAロジツク35からの仮想アド
レスは、コンテキストIDレジスタ32内のアドレスととも
に、アクセスアドレスと呼ばれる。

別の選択的な素子はデータバスバツフア37である。好適
な実施例においては、そのデータバスバツフアは、32ビ
ツトバスと64ビツトバスの間のデータの流れを制御する
ために２つのバツフアとして実現される。それらのバツ
フアは、CPUデータバスが32ビツトで、キヤツシユデー
タアレイデータバスが64ビツトの時に必要とされる。

本発明のワークステーシヨンに独特の素子についての説
明 上記のように、本発明においては、エイリアスアドレス
から生ずるデータ一貫性の問題を解決するために、２種
類の戦略が利用される。両方の戦略は、データの一貫性
を確保するために、オペレーテイングシステムと特殊な
キヤツシユハードウエアと相互作用することを必要とす
る。

第１の戦略は、同じデータへマツプする全てのエイリア
スアドレスの下位アドレスビツトを一致させて、データ
をキヤツシユするものとすると、それらのアドレスが同
じキヤツシユ場所を用いるようにしなければならないこ
とを要する。本発明は、キヤツシユを「ミスする」メモ
リアクセスにおけるエイリアスアドレスを検出し、全て
のエイリアスアドレスが同じキヤツシユ場所内の一貫す
るデータを指すようにキヤツシユデータ更新を制御する
ために、実アドレス比較器であるエイリアス検出ロジツ
ク47を利用する。

この第１の戦略を実現する核アドレスオペレーシヨンモ
ジユールは、エイリアスアドレスの下位アドレスビツト
を一致させるから、同じキヤツシユ場所を使用すること
をエイリアスアドレスは保証される。キヤツシユの寸法
が２^Ｍのデータブロツクであるとすると（各データブロ
ツクは２^Ｎバイト）、エイリアスアドレスの少くとも下
位（Ｎ＋Ｍ）ビツトを一致させねばならない。これは同
じプロセス内のエイリアスアドレスと、プロセス間のエ
イリアスアドレスにも適用される。この要求を満す限り
は、直接マツプされるキヤツシユにおいては、エイリア
スアドレスは同じキヤツシユブロツクへマツプし、多方
向セツト連想キヤツシユにおいてはエイリアスアドレス
は同じキヤツシユセツトへマツプする。第２の戦略は、
MMU27中の各ページについて定められる「キヤツシユし
ない」ビツトを使用することにより、データがキヤツシ
ユされることを阻止する。いいかえると、MMU27中の各
ページ記述子は「キヤツシユしない」ビツトを有する。
そのビツトは、そのページからの命令とデータをキヤツ
シユに書込むことができるかどうかを制御する。この制
御ビツトがあるページについてセツトされるものとする
と、このページに対する全てのデータアクセスがメモリ
に対しては、またはメモリから、直接に行われ、キヤツ
シユをバイパスする。キヤツシユのバイパスにおいて
は、仮想キヤツシユデータの一貫性の問題が避けられ
る。

エイリアスドレツシングが可能であるから、１つのMMU
ページエントリイにおいてあるページが「キヤツシユし
ない」とマークされるものとすると、全てのエイリアス
ページエントリイにおいて「キヤツシユしない」とマー
クせねばならない。さもないとデータの一貫性は保証さ
れない。

ユーザープロセスのためのエイリアスアドレス発生は核
を介して制御されるから、エイリアスアドレスの間でデ
ータの一貫性を確保するために、全てのユーザープロセ
スは第１の戦略を利用する。しかし、オペレーテイング
システムに対するあるアドレスは、第１の戦略のアドレ
ツシング要求を満たすために変更することはできない。
その代りに、それらのシステムエイリアスアドレスは、
第２の戦略、すなわち、「キヤツシユしない」ページへ
の割当てにより取扱われる。

以下に、２つの戦略の組合わせを用いて、直接マツプさ
れる仮想アドレス書戻しキヤツシユにおけるデータの一
貫性を生ずるために必要とされるものについて機能的に
説明する。

CPU11またはDVMA35のメモリアクセスサイクルがキヤツ
シユを「ミスした」とすると、アクセス仮想アドレスが
MMUにより翻訳される。MMUの翻訳は、アクセスされるペ
ージが「キヤツシユしない」ページかどうか、アクセス
が保護の侵害を有するかどうかを決定する。アクセスが
有効で、キヤツシユできるページに対するものであると
すると、アクセスアドレスに対応するキヤツシユブロツ
クでキヤツシユが更新される。

アクセスアドレスに対応する場所におけるキヤツシユの
現在の内容を調べて可能なエイリアスアドレスを検出す
る。現在のキヤツシユブロツクが有効で、修正されたと
すると、キヤツシユブロツクの翻訳されるアドレスを翻
訳されるアクセスアドレスと比較して有効なデータのソ
ースを判定してキヤツシユを更新する。

エイリアス検出ロジツク47により行われる実アドレス比
較は、翻訳されたバスサイクルアクセスを実アドレスレ
ジスタ51から、および翻訳されるキヤツシユアドレスを
MMU27から、入力としてとる。

現在のキヤツシユブロツクが有効であり、翻訳されたア
ドレス相互が等しいとすると、アクセスアドレスとキヤ
ツシユブロツクアドレスはエイリアスである。キヤツシ
ユブロツクが修正されたとすると、現在のキヤツシユデ
ータは最も現在のデータであり、このアドレスにおける
主メモリデータは古い。

翻訳されたアドレス相互は等しいが、キヤツシユブロツ
クが修正されないとすると、古いキヤツシユデータとメ
モリデータは同一であり、いずれもキヤツシユ更新のた
めのソースとして使用できる。

有効なブロツクデータのソースがひとたび決定される
と、アクセスサイイクルを終らることができる。読出し
サイクルにおいては、キヤツシユ更新に続いて、バスサ
イクルはデータを、実現に応じてソースまたはキヤツシ
ユから直接戻す。書込みサイクルにおいては、アクセス
データをキヤツシユへ書込むことができる。キヤツシユ
寸法の更とキヤツシユデータの整列は実現に依存する。

データの一貫性を保証するために、ページへのどのよう
な書込みも、そのページへの全ての関係（読出しまたは
書込み）はこの制約を固守する。

エイリアス検出ロジツク47を含むアドレス路の好適な実
施例を第３図に示す。第３図に示すように、アドレス路
は、仮想アドレス書戻しキヤツシユにおけるアドレス制
御をサポートする基本素子を含む。エイリアスアドレス
サポートのために、仮想アドレス（CXおよびVA）とキヤ
ツシユブロツク有効ビツト（Ｖ）のための仮想アドレス
レジスタ52（VAR）と、仮想アドレスと仮想アドレスレ
ジスタを多重化するマルチプレクサ45と、実アドレスレ
ジスタ51と、エイリアス検出ロジツク47と、アンドゲー
ト53（VARからの有効ビツトとエイリアス検出ロジツク
出力を入力として有する）と、実アドレス一致が検出さ
れた時にセツトされるアドレス一致フリツプフロツプ55
も必要とされる。

キヤツシユ19から主メモリ31へのデータ路は２つの64ビ
ツトバス56,58を介する。CPUデータ路60は32ビツトであ
つて、Ｄ（31:0）として示される。読出しバスサイクル
では、２つの３ビツトバツフア37のうちいずれが64ビツ
トキヤツシユデータバス56からのデータを32ビツトCPU
データバス60へ置くことを可能にするかをキヤツシユア
ドレスビツトＡ（２）が選択する。エイリアス検出ロジ
ツク49は読出しサイクルキヤツシユミス（キヤツシユま
たはメモリ）におけるデータのソースを制御し、書込み
サイクルキヤツシユミスでキヤツシユがメモリデータで
更新されるかどうかを制御する（第６図，第７図のデー
タ状態マシン）。

第３図と第５図においては、図の不必要な混乱を避ける
ために、全ての制御線を示しているわけではない。しか
し、本発明を適切に動作させるために必要な制御線は、
第４図および第６図乃第８図に示す状態マシンの流れ図
から確かめることができる。

流れ図においては下記の省略を用いている。

MUX−マルチプレクサ45 Sel−選択 VA−仮想アドレス RA−実アドレス OE−出力イネイブル Ack−確認応答 Cache Hit?−キヤツシユ「ヒツト」ロジツク25がキヤツ
シユヒツトを検出したか（第2a図） Cache Protect Violation?−制御ロジツク40がキヤツシ
ユ保護侵害を検出したか（第2b図） Memory Busy?−メモリビジーがアサートされたか MMU Protect Viol?−制御ロジツク40がMMU保護侵害を検
出するか（第2c図） RAR−実アドレスレジスタ51 CLK−クロツク Adr−アドレス Mem Adr Strobe−メモリ31アドレスストローブ VAR−仮想アドレスレジスタ Mem Adr Ack?−メモリアドレス確認応答がメモリ31によ
りアサートされたか Mem Data Strobe 0?−メモリデータストロープ０がアサ
ートれたか Mem Date Ack 0?−メモリデータ確認応答０がアサート
されたか Mem Date Strobe 1?−メモリデータストローブ１がアサ
ートされたか Mem Data Ack 1?−メモリデータ確認応答１がアサート
されたか Clk Write Back Buffer−クロツク書戻しバツフア39 Real Adr Match?−実アドレス一致が検出れたか（フリ
ツプフロツプ55） Don′t Catch Page?−制御ロジツク40がMMU27からキヤ
ツシユしないページを検出したか CPU Read Cycle?−CPU11が読出しサイクルにあるか Clk Date Reg−クロツクデータレジスタ61 Valid and Modified Write Back Data?−制御ロジツク4
0が有効ビツト（Ｖ）と修正されたビツト（Ｍ）を検出
したか Write to Don′t Cache Page−制御ロジツク40がキヤツ
シユしないページへのCPU書込みを検出したか Start No Cache Write?−制御ロジツク40がキヤツシユ
書込み無しスタートをアサートしたか Start Write Back Cycle?−制御ロジツク40が書戻しサ
イイクルスタートをアサートしたか 第９図乃至第11図に示すタイミング図においても類似の
省略が用いられる。

第4a図と第4b図に示すアドレス状態マシンは、キヤツシ
ユのアドレス取扱い部に関連する制御のあるものを定め
る。実アドレス一致フリツプフロツプ55のクロツキング
により本発明は統合される（状態（ｏ））。状態（ｗ）
中に、メモリ31からの全てのブロツクデータの成功した
転送に続いて、状態（ｗ）の間にキヤツシユタグ23が有
効なものとして書込まれる。

第6a図と第6b図および第7a図乃至第7d図に示すデータ状
態マシンは、キヤツシユのデータ転送部分に関連するあ
る制御を定める。図示のように、状態（ｇ）の後で、キ
ヤツシユしないページへの書込みについてのテストが行
われる。メモリへのこの書込みの取扱いが、データ状態
マシンにおける次の状態（i,dw）の経路に示されてい
る。状態（ｏ）に続いて、キヤツシユしないページアク
セス（この時には読出しデータに対して）についてテス
トが行われる。キヤツシユしない読出しの制御は、状態
（q.nr）および（u.nr）まで、非実アドレス一致路をと
る。ここで、キヤツシユしないページについてのテスト
が状態（s.nr）と（w.nr）におけるキヤツシユ更新を禁
示する。

第８図に示す書戻し状態マシンはメモリへの書戻しサイ
クルの制御を定める。書戻し制御とデータ路はキヤツシ
ユアクセス制御およびデータ路とは独立しているから、
そのサイクルはCPUキヤツシユアクセスと並列に実行で
きる。下記のように、「Memory Busy」信号は、前の書
戻しサイクルが終るまでアドレスおよびデータ状態マシ
ンを待機させる。

第9a図に示す書込みキヤツシユミスタイミング図は、キ
ヤツシユをミスするメモリ内のキヤツシユできるページ
へのCPU書込みバスサイクルの全体のタイミングを定め
る。キヤツシユヒツトと保護チエツクがこの図のサイク
ル（ｃ）で起る。

ミス取扱いシーケンスの部分が、サイクル（ｉ）と
（ｍ）における、書戻しバツフア39へ置きかえられる現
在のキヤツシユブロツクのローデイングを含む。現在の
キヤツシユブロツクのための翻訳されたアドレスもサイ
クル（ｏ）において実アドレスレジスタ51へロードされ
る。サイクル（ｏ）においては実アドレス一致ラツチ
（フリツプフロツプ55）もクロツクされる。現在のキヤ
ツシユブロツクが有効で、前のCPU（またはDVMA）書込
みサイクルから修正されたとすると、第11b図のメモリ
データバスタイミング図と第８図の書戻し状態マシンに
示されるように、そのキヤツシユブロツクは書戻しバス
サイクルにおいてメモリ31へ書込まれる。

アクテイブ実アドレス一致ラツチ（フリツプフロツプ5
5）はエイリアスアドレス一致を意味する。エイリアス
一致がなければ、CPU書込みデータが、ブロツク読出し
メモリバスサイクルの第１のデータ転送においてメモリ
から戻されたブロツクデータと一緒にされる。サイクル
（ｑ）〜（ｕ）の間は、CPU書込み出力イネイブル制御
バツフア37は、CPUにより書込むべきバイトのみに対し
てアクテイブであり、データレジスタ出力イネイブル制
御データレジスタ61は他の全てのバイトに対してアアク
テイブである。第２のデータ転送中、サイクル（ｗ）は
全てのバイトに対するデータレジスタ出力イネイブルが
アクテイブである。

エイリアス一致が存在するものとすると、CPUデータは
状態（ｓ）においてデータキヤツシユへ書込まれ、メモ
リ31からのデータは無視される。

第9b図に示されているキヤツシユしないページへの書込
みは、キヤツシユしないページへのアクセスに対するメ
モリへのCPU書込みバスサイクルの全体のタイミングを
定める。サイクル（ｃ）で起るキヤツシユヒツトはミス
（ヒツトなし）を常に指示する。

キヤツシユしないページへの書込みのケースは、キヤツ
シユがCPUまたはメモリデータにより更新されない点
が、キヤツシユできるページについてのキヤツシユミス
のケースとは異なる。メモリを直接更新するために、実
現は特殊なメモリバスサイクルを用いる。そのメモリバ
スサイクルはキヤツシユしないページへの書込みサイク
ル（第11c図）と呼ばれる。この場合には実アドレス一
致ラツチは意味を持たないことに注目されたい。

第10a図に示されている読出しキヤツシユミスタイミン
グ図は、キヤツシユをミスするメモリ内のキヤツシユ可
能なページへのCPU読出しバスサイクルの全体のタイミ
ングを定める。キヤツシユヒツトおよび保護チエツク
は、この図ではサイクル（ｃ）で起る。

ミス取扱いシーケンスの一部が、サイクル（ｉ）と
（ｍ）において、書戻しバツフア39へ置きかえられる現
在のキヤツシユブロツクのローデイングを含む。現在の
キヤツシユブロツクに対する翻訳されたアドレスも実ア
ドレスレジスタ51へロードされる（サイクル（ｏ））。
サイクル（ｏ）においては実アドレス一致ラツチ（フリ
ツプフロツプ55）もクロツクされる。現在のキヤツシユ
ブロツクが有効で、前のCPU（またはDVMA）書込みサイ
クルから修正されたとすると、第11b図のメモリデータ
バスタイミングと第８図の書戻し状態マシンに示されて
いるように、そのキヤツシユブロツクは書戻しサイクル
でメモリ31へ書戻される。

アクテイブ実アドレス一致ラツチ（フリツプフロツプ5
5）はエイリアスアドレス一致を意味する。エイリアス
アドレス一致がないとすると、状態（ｑ）〜（ｕ）にお
いてアクテイブである制御信号「CPU読出し出力イネイ
ブル」によりイネイブルされるバツフア37を介してデー
タをCPUへバイパスすることと、状態（ｅ）においてキ
ヤツシユを更新することを同時に行うことにより、デー
タはCPUへ読込まれる。メモリは、ブロツク読出しメモ
リバスサイクルの初めの64ビツト転送と、次の64ビツト
転送において「ミスしたデータ」を常に戻すように構成
される。CPU読出しバスサイクルデータが戻された後
で、メモリからの第２のデータ転送でキヤツシユが更新
されている間にCPUは内部サイクルを実行できる。

エリリアスアドレス一致が存在したとすると、データは
キヤツシユ19からCPU11へ直接読出され、メモリ31から
のデータは無視される。

第10b図に示すキヤツシユしないページタイミングから
の読出しは、キヤツシユしないページへのアクセスのた
めのメモリに対するCPU読出しバスサイクルの全体のタ
イミングを定める。状態（ｃ）で起るキヤツシユヒツト
はミス（ヒツトなし）を常に指示する。

キヤツシユしないページからの読出しのケースは、キヤ
ツシユがメモリデータで更新されない点が、キヤツシユ
できるページからの読出しに対するキヤツシユミスのケ
ースとは異なる。実現は、キヤツシユミスのケースと同
じブロツク読出しメモリバスサイクルを用いる（下のメ
モリデータバスタイミング参照）。実アドレス一致ラツ
チ（フリツプフロツプ55）はこのケースに対しては何の
意味も持たない。

第11a図乃至第11c図に示すメモリデータバスタイミング
はブロツク読出しサイクルと、書戻しサイクルと、キヤ
ツシユしないページへの書込みバスサイクルとの各タイ
ミングをそれぞれ示すものである。キヤツシユブロツク
の寸法は128ビツトであるから、各キヤツシユブロツク
更新は２回のデータ転送を要する。前記のように、CPU1
1によりアドレスされるデータを含む64ビツトは、ブロ
ツク読出しバスサイクルの初めの転送で常に戻される。
「Memory Busy」制御信号は、前の書戻しサイクルを終
ることができるまで次のキヤツシユミスサイクルのスタ
ートを禁止するために用いられている間アクテイブであ
る。

キヤツシユしないページバスサイクルへの書込みにおい
ては、サイクルのアドレス転送段階中に送られた８ビツ
トバイトマークフイールドが、データの８バイトのう
ち、データ段階中に、どれがメモリ31において更新され
るかを定める。

以上説明したハードウエアに加えて、エイリアスドレツ
シングをサポートするために、下記の２つの基本的なや
り方でオペレーテイングシステムの核を修正せねばなら
ない。

１）ユーザーエイリアスアドレスを発生するオペレーテ
イングシステムユーテイリテイは、エイリアスアドレス
の下位（Ｎ＋Ｍ）アドレスビツトが、最少限、一致せね
ばならないことを求める規則に合致することを保護する
ために修正せねばならない。

２）下位（Ｎ＋Ｍ）ビツトの一致を求める規則に合致さ
せることができないオペレーテイングシステム内のエイ
リアスアドレスの例を、「キヤツシユしない」ページへ
割当てねばならない。

【図面の簡単な説明】

第１図は書戻しキヤツシユを有する仮想アドレスを利用
するワークステーシヨンの主な部品を示すブロツク図、
第2a図はキヤツシユ「ヒツト」ロジツクの略図、第2b図
はキヤツシユ保護の侵害を検出する回路の概略ブロツク
図、第2c図はMMU保護の侵害を検出する回路の概略ブロ
ツク図、第３図は本発明のエイリアス検出ロジツクによ
り利用されるアドレス路を示す詳細なブロツク図、第4a
図および第4b図は仮想アドレス書戻しキヤツシユのアド
レツシングに関連するある制御の状態マシン実現の流れ
図、第５図は本発明のエイリアス検出ロジツクにより利
用されるデータ路を示す詳細なブロツク図、第6a図と6b
図は仮想アドレス書戻しキヤツシユとの間のデータ転送
に関連するある制御の状態マシン実現の流れ図（状態
（ａ）〜（ｏ））、第7a図は実アドレス一致が存在する
時のデータ路を実現するための状態マシンの流れ図（状
態（ｑ）〜（ｕ））、第7b図はCPU書込みバスサイクル
中に実アドレス一致が存在しない時のデータ路を実現す
るための状態マシンの流れ図（状態（ｑ）（ｙ））、第
7c図はCPU読出しバスサイクル中に実アドレス一致が存
在しない時のデータ路を実現するための状態マシンの流
れ図（状態（ｑ）〜（ｙ））、第7d図はMMUがキヤツシ
ユページをしない時にCPU書込みバスサイクル中のデー
タ路を実現するための状態マシンの流れ図、第８図はメ
モリへの書戻しバスサイクルを制御する状態マシン実現
の流れ図、第9a図はMMUがキヤツシユできるページを示
す時にCPU書込みバスサイクルのための最良のケースに
対するタイミング図、第9b図はMMUがキヤツシユしない
ページを示す時にCPU書込みバスサイクルの最良のケー
スに対するタイミング図、第10a図はMMUがキヤツシユで
きるページを示す時にCPU書込みバスサイクルのための
最良のケースに対するタイミング図、第10b図はMMUがキ
ヤツシユしないページを示す時にCPU書込みバスサイク
ルの最良のケースに対するタイミング図、第11a図はブ
ロツク読出しサイクルを実現するメモリバスサイクルの
タイミング図、第11b図は書戻しサイクルを実現するメ
モリバスサイクルのタイミング図、第11c図はキヤツシ
ユしないページへの書込みを実行するメモリバスサイク
ルのタイミング図である。 11……中央処理装置、19……キヤツシユデータアレイ、
23……キヤツシユタグアレイ、25……キヤツシユヒツト
比較器、27……メモリ管理ユニツト（MMU）、31……主
メモリ、32……コンテキスト識別レジスタ、33……キヤ
ツシユフラツシユロジツク、35……直接仮想メモリアク
セス（DVMA）ロジツク、37,45……マルチプレクサ、39
……書戻しバツフア、40……ワークステーシヨン制御ロ
ジツク、47,49……エイリアス検出制御ロジツク、51…
…実アドレスレジスタ、52,54……仮想アドレスレジス
タ、60……比較器、61……クロツクデータレジスタ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジヨセフ・モラン アメリカ合衆国95054カリフオルニア州・ サンタ クララ・ワイルドウツド ウエ イ・544 (72)発明者 ウイリアム・シヤノン アメリカ合衆国94022カリフオルニア州・ ロス アルトス・トリアノン ウエイ・ 261 (72)発明者 レイ・チエン アメリカ合衆国95014カリフオルニア州・ クーパーチノ・サマーセツト コート・ 10402 (56)参考文献 特開 昭63−53889（ＪＰ，Ａ) 特開 昭54−148329（ＪＰ，Ａ)

Claims (4)

【特許請求の範囲】
1. 【請求項１】オペレーティングシステムが、実行中の少
   なくとも１つのプロセスのために資源を割当て且つエイ
   リアスアドレスを使用しており、 前記プロセスおよび前記オペレーティングシステムを実
   行する中央処理装置（CPU）と、 この中央処理装置（CPU）に結合されていて、キャッシ
   ュされている仮想メモリブロックを特定する、仮想アド
   レス・キャッシュタグアレイ（CTA）と、 前記中央処理装置（CPU）に結合されていて、前記の特
   定された仮想メモリブロックをキャッシュする、仮想ア
   ドレス・書戻しキャッシュデータアレイ（CDA）と、 前記中央処理装置（CPU）に結合されていて、仮想アド
   レスを物理アドレスに翻訳するメモリ管理ユニット（MM
   U）と、 前記中央処理装置（CPU）に結合されていて、現在常駐
   状態の仮想メモリページを格納する主メモリ（MM）と、 前記中央処理装置（CPU）および前記キャッシュタグア
   レイ（CTA）に結合されていて、キャッシュヒットを検
   出する、キャッシュヒット検出器（CHD）と、 前記中央処理装置（CPU），前記キャッシュタグアレイ
   （CTA），前記キャッシュデータアレイ（CDA），前記メ
   モリ管理ユニット（MMU），前記主メモリ（MM），前記
   キャッシュヒット検出器（CHD）に結合されてそれらの
   動作を制御する、処理器制御ロジックと を備えるコンピュータ装置において、 ａ） 第１の仮想アドレスと第２の仮想アドレスとが、
   相互にエイリアスであるが、下記する所定の仮想アドレ
   ス・セットには属していない場合には、前記オペレーテ
   ィングシステムは、前記第１の仮想アドレスと第２の仮
   想アドレスを、それらの下位のｎ＋ｍビット部分につい
   て等しくさせ、これにより、第１の仮想メモリ位置と第
   ２の仮想メモリ位置のキャッシュ動作に、１つのキャッ
   シュ位置が使用され、 前記第１の仮想アドレスと第２の仮想アドレスとは、第
   １の仮想メモリページとそのメモリページ内の第１の仮
   想メモリ位置との特定、および、第２の仮想メモリペー
   ジとそのメモリページ内の第２の仮想メモリ位置との特
   定をそれぞれ行う、第１および第２の複数の仮想アドレ
   スビットから成り、 前記第１の仮想アドレスと第２の仮想アドレスとは、前
   記主メモリ（MM）のメモリページとそのメモリページ内
   のメモリ位置とを特定する複数の物理アドレスビットで
   構成される同一の物理アドレスに、翻訳されるものであ
   り、 前記所定の仮想アドレス・セットは、前記オペレーティ
   ングシステムのアドレス空間の仮想アドレスの所定のサ
   ブセットを含み、その所定のサブセットに含まれる各仮
   想アドレスは、その所定のサブセット中の他の何れかの
   仮想アドレスとエイリアスであり、 前記キャッシュタグアレイ（CTA）は、キャッシュされ
   ているｎ個の仮想メモリブロックを特定するｎ個のキャ
   ッシュ タグ エントリイを有し、前記キャッシュデー
   タアレイ（CDA）は、ｍ個のキャッシュ位置がそれぞれ
   あるｎ個のキャッシュブロックを有して前記ｎ個の仮想
   メモリブロックを有しており、 ｂ） 仮想メモリページが、前記所定の仮想アドレス・
   セットの１つの仮想アドレスにより特定される少なくと
   も１つの仮想アドレス位置を、含んでいる場合には、前
   記メモリ管理ユニット（MMU）は、上記の仮想メモリペ
   ージを、キャッシュしないページとしてマークを付し、
   もって、マークされた仮想メモリページの仮想メモリブ
   ロックのキャッシュ動作を禁止し、そのマークされた仮
   想メモリページの全てのデータアクセスが、前記キャッ
   シュデータアレイ（CDA）をバイパスさせて前記主メモ
   リ（MM）との間で直接に行われる ことを特徴とするコンピュータ装置。
2. 【請求項２】特許請求の範囲第１項記載のコンピュータ
   装置において、前記メモリ管理ユニット（MMU）は、前
   記所定の仮想アドレス・セットの１つの仮想アドレスに
   より特定される少なくとも１つの仮想アドレス位置を含
   む前記仮想メモリページに、その仮想メモリページ用の
   ページ記述子内にビットをセットすることによってマー
   クを付し、対応の仮想メモリページを記述する仮想メモ
   リ用ページ記述子は前記メモリ管理ユニット（MMU）に
   複数含まれている、ことを特徴とするコンピュータ装
   置。
3. 【請求項３】オペレーティングシステムが、実行中の少
   なくとも１つのプロセスのために資源を割当て且つエイ
   リアスアドレスを使用しており、 前記プロセスおよび前記オペレーティングシステムを実
   行する中央処理装置（CPU）と、 この中央処理装置（CPU）に結合されていて、キャッシ
   ュされている仮想メモリブロックを特定する、仮想アド
   レス・キャッシュタグアレイ（CTA）と、 前記中央処理装置（CPU）に結合されていて、前記の特
   定された仮想メモリブロックをキャッシュする、仮想ア
   ドレス・書戻しキャッシュデータアレイ（CDA）と、 前記中央処理装置（CPU）に結合されていて、仮想アド
   レスを物理アドレスに翻訳するメモリ管理ユット（MM
   U）と、 前記中央処理装置（CPU）に結合されていて、現在常駐
   状態の仮想メモリページを格納する主メモリ（MM）と、 前記中央処理装置（CPU）および前記キャッシュタグア
   レイ（CTA）に結合されていて、キャッシュヒットを検
   出する、キャッシュヒット検出器（CHD）と、 前記中央処理装置（CPU），前記キャッシュタグアレイ
   （CTA），前記キャッシュデータアレイ（CDA），前記メ
   モリ管理ユニット（MMU），前記主メモリ（MM），前記
   キャッシュヒット検出器（CHD）に結合されてそれらの
   動作を制御する、処理器制御ロジックと を備えるコンピュータ装置において、前記キャッシュデ
   ータアレイ（CDA）のデータの不一致を検出して修正す
   る方法であって、 ａ） 第１の仮想アドレスと第２の仮想アドレスとが、
   相互にエイリアスであるが、下記する所定の仮想アドレ
   ス・セットには属していない場合には、前記第１の仮想
   アドレスと第２の仮想アドレスを、それらの下位のｎ＋
   ｍビット部分が等しくなるよう変更するステップを備
   え、これにより、第１の仮想メモリ位置と第２の仮想メ
   モリ位置のキャッシュ動作に、１つのキャッシュ位置が
   使用され、 前記第１の仮想アドレスと第２の仮想アドレスとは、第
   １の仮想メモリページとそのメモリページ内の第１の仮
   想メモリ位置との特定、および、第２の仮想メモリペー
   ジとそのメモリページ内の第２の仮想メモリ位置との特
   定をそれぞれ行う、第１および第２の複数の仮想アドレ
   スビットから成り、 前記第１の仮想アドレスと第２の仮想アドレスとは、前
   記主メモリ（MM）のメモリページとそのメモリページ内
   のメモリ位置とを特定する複数の物理アドレスビットで
   構成される同一の物理アドレスに、翻訳されるものであ
   り、 前記所定の仮想アドレス・セットは、前記オペレーティ
   ングシステムのアドレス空間の仮想アドレスの所定のサ
   ブセットを含み、その所定のサブセットに含まれる各仮
   想アドレスは、その所定のサブセット中の他の何れかの
   仮想アドレスとエイリアスであり、 前記キャッシュグクアレイ（CTA）は、キャッシュされ
   ているｎ個の仮想メモリブロックを特定するｎ個のキャ
   ッシュ タグ エントリイを有し、前記キャッシュデー
   タアレイ（CDA）は、ｍ個のキャッシュ位置がそれぞれ
   あるｎ個のキャッシュブロックを有して前記ｎ個の仮想
   メモリブロックを有しており、 ｂ） 仮想メモリページが、前記所定の仮想アドレス・
   セットの１つの仮想アドレスにより特定される少なくと
   も１つの仮想アドレス位置を、含んでいる場合には、上
   記の仮想メモリページを、キャッシュしないページとし
   てマークを付すマキーング・ステップを備え、もって、
   マークされた仮想メモリページの仮想メモリブロックの
   キャッシュ動作を禁止し、そのマークされた仮想メモリ
   ページの全てのデータアクセスが、前記キャッシュデー
   タアレイ（CDA）をバイパスさせて前記主メモリ（MM）
   との間で直接に行われる ことを特徴とする、コンピュータ装置においてキャッシ
   ュデータアレイ内のデータの不一致を検出して修正する
   方法。
4. 【請求項４】特許請求の範囲第３項記載の方法におい
   て、前記マーキング・ステップは、前記メモリ管理ユニ
   ット（MMU）内の前記仮想メモリページ用のページ記述
   子内にビットをセットすることを含み、対応の仮想メモ
   リページを記述する仮想メモリ用ページ記述子は前記メ
   モリ管理ユニット（MMU）に複数含まれていることをこ
   とを特徴とする、コンピュータ装置においてキャッシュ
   データアレイ内のデータの不一致を検出して修正する方
   法。