JPH05197626A - 仮想記憶システムのための登録簿索引テーブル論理装置 - Google Patents

Abstract

(57)【要約】 【目的】 複数のデータ空間において、仮想ページアド
レスの周期性を効率的に処理するための登録簿索引テー
ブル（ＤＬＡＴ）論理装置の提供。 【構成】 改良されたＤＬＡＴ構造はアドレス空間とデ
ータ空間とを識別する。ＤＬＡＴ構造は、仮想ページ・
アドレスのＤＬＡＴ列への割当を制御する１以上の空間
ＩＤによって、データ空間を分類する。一実施例では、
異なるＤＬＡＴアドレス指定アルゴリズムを選択するの
に“私用空間ビット”が用いられる。他の実施例では、
空間ＩＤビットを用いてデータ空間がサブクラスに分け
られ、各サブクラスに対し、固有のアルゴリズムが、ペ
ージ・アドレスビットに基づいて選択される。排他的Ｏ
Ｒ関数が、ＤＬＡＴ選択ビットを生成するのに用いられ
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的に、データ処理
システムのための仮想記憶機構に関し、特に、複数のデ
ータ空間での処理に際し、周期的な仮想ページアドレス
の改良された処理を可能にする改良された登録簿索引テ
ーブル（ｄｉｒｅｃｔｒｏｒｙ ｌｏｏｋ−ａｓｉｄｅ
ｔａｂｌｅ：ＤＬＡＴ）構造に関する。本発明は、特
に、複数のデータ空間において並行して仮想アドレスを
実主記憶アドレスに変換できるＤＬＡＴエントリを有す
るシステムのための、ＤＬＡＴ内のシノニムエントリの
最小化を目指している。

【０００２】

【従来の技術】データ処理システムのための仮想記憶編
成およびその管理は、例えば、Ｈａｒｖｅｙ Ｍ． Ｄ
ｅｉｔｅｌ著“Ａｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ
Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ”，Ａｄｄｉｓ
ｏｎ−Ｗｅｓｌｅｙ（１９８４）や、Ｈａｒｏｌｄ Ｌ
ｏｒｉｎおよびＨａｒｖｅｙ Ｍ． Ｄｅｉｔｅｌ著
“Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ”，Ａｄｄｉｓ
ｏｎ−Ｗｅｓｌｅｙ（１９８１）や、Ｈａｒｏｌｄ
Ｓ． Ｓｔｏｎｅ著“Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃ
ｅ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ”，
Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ（１９８７）に説明され
ている。仮想記憶システムでは、ページングは再配置で
あり、アドレス対物理位置結合機構であり、システムの
ユーザに、実際に使用可能な空間よりも相当大きく見え
るメモリ空間を提供する。仮想記憶概念のキーとなる特
徴は、実行プロセスで参照されるアドレスと主記憶で使
用可能なアドレスとが互いに独立であることである。実
行プロセスによって参照されるアドレスを、仮想アドレ
スと呼び、主記憶で使用可能なアドレスを実アドレスと
呼ぶ。仮想アドレスは、プロセスが実行する実アドレス
に写像されねばならず、それは動的アドレス変換（ｄｙ
ｎａｍｉｃａｄｄｒｅｓｓ ｔｒａｎｓｌａｔｉｏｎ：
ＤＡＴ）機構によって実行される。そのような機構の１
つは、登録簿索引テーブル（ＤＬＡＴ）を採用してお
り、新しい仮想アドレス翻訳を格納する変換索引緩衝機
構（ｔｒａｎｓｌａｔｉｏｎｌｏｏｋ−ａｓｉｄｅ ｂ
ｕｆｆｅｒ：ＴＬＢ）と呼ばれるときもある。ＤＡＴプ
ロセスは、ＤＬＡＴに格納された仮想アドレスについて
は１〜２のマシンサイクルを要求する。しかし、ＤＬＡ
Ｔに格納されていないアドレスに対しては、ＤＡＴプロ
セスは１５〜６０マシンサイクルを要することがある。

【０００３】仮想アドレスから実アドレスへの変換は、
アドレス指定された命令またはデータが主記憶のどこに
存在するのかを見出すために行われる。これは典型的
に、ページを基にして行われる。実際、ＤＬＡＴに格納
されているのは、実際にはページのみである。アドレス
の後半ビット群はそのページにおける位置であるので、
ページアドレスのみの変換で十分なためである。

【０００４】従来の仮想記憶システムでは、過度のペー
ジングの結果、システムが有効作業を少ししか行えない
スラッシングと呼ばれる状態が発生する。この状態は、
例えば、ＡＦＩＰＳ Ｃｏｎｆ． Ｐｒｏｃ．， ｖｏ
ｌ．３３，１９６８ ＦＪＣＣ， ｐｐ．９１５−９２
２，“Ｔｈｒａｓｈｉｎｇ：ｉｔｓ Ｃａｕｓｅｓａｎ
ｄ Ｐｒｅｖｅｎｔｉｏｎ”，においてＰ． Ｊ． Ｄ
ｅｎｎｉｎｇにより認識され、説明されている。Ｄｅｎ
ｎｉｎｇの主張によれば、プログラムを効率的に実行す
るには、作業ページ・セットを１次記憶に保持しなけれ
ばならない。そうでなければ、プログラムが２次記憶か
らのページを繰り返し要求する毎に、スラッシングが発
生する。この状態は上記のＤｅｉｔｅｌによって、前記
文献のＶｅｒｔｕａｌ Ｓｔｏｒａｇｅ Ｍａｎａｇｅ
ｍｅｎｔの章・セクション９．５“Ｗｏｒｋｉｎｇ Ｓ
ｅｔｓ”で言及されている。

【０００５】米国特許第４，１３６，３８５号明細書
は、この問題を、多重仮想記憶システムに対するシノニ
ム制御として扱っている。この明細書ではＤＬＡＴシノ
ニム制御を、ＤＬＡＴエントリが全ユーザ・アドレス空
間によって共有されるのか、あるいはＤＬＡＴにおいて
識別される単一アドレス空間に制限されるのかを示すイ
ンディケータの、各ＤＬＡＴエントリへのセッティング
を制御する。これは、任意の私用アドレス空間におい
て、セグメントまたはページが、そのアドレス空間専用
のプログラムおよびデータを含むのか、あるいは全アド
レス空間によって共有されるプログラムおよびデータを
含むのかを示す、任意のセグメント・テーブル・エント
リ（ＳＴＥ）内の、あるいはまた、任意のページ・テー
ブル・エントリ（ＰＴＥ）内の共通空間ビットによって
達成される。このように、各ＤＬＡＴエントリは、共通
／私用記憶インディケータを含み、そのインディケータ
は、アドレス変換に使用されるＳＴＥまたはＰＴＥ内の
共通空間ビットの状態に対してセットされ、ＤＬＡＴエ
ントリ内にロードされる。エントリが読み出されると
き、共通／私用記憶インディケータは、ＤＬＡＴが単に
ＤＬＡＴにおいて識別されるアドレス空間によって使用
されるだけか、あるいは、全アドレス空間によって使用
されるかを区別する。

【０００６】従来の２ウェイＤＬＡＴ設計は、周期的な
仮想ページ・アドレスを、複数のデータ空間で処理する
とき、不十分な処理しかできなかった。典型的な２ウェ
イＤＬＡＴ設計は、全データ空間の同一の仮想アドレス
を、同一のＤＬＡＴ列に写像してしまう。例えば、次の
擬似コード ＤＯ ｉ＝１ ｔｏ １，０００ Ａ（ｉ）＋Ｂ（ｉ）＝Ｃ（ｉ） において、もしＡ，Ｂ，およびＣが同一の開始値（例え
ば０）を３つのデータ空間それぞれに有するならば、デ
ータ空間のシノニムによって発生したＤＬＡＴスラッシ
ングのために、このコードによるパフォーマンスは低下
する。米国特許第４，１３６，３８５号明細書のシノニ
ム制御は、共通空間ビットによってシノニムのクラス・
エントリを防止してはいるものの、同一のオリジンを有
する３つのデータ空間によって生成された、２ウェイＤ
ＬＡＴにおけるシノニムの問題を解決できない。

【０００７】

【発明が解決しようとする課題】本発明の一般的な目的
は、アドレス空間とデータ空間とを識別する、改良され
たＤＬＡＴ論理装置を提供することにあり、この論理装
置は、複数のデータ空間での処理のとき、仮想ページア
ドレスの周期性を効率的に処理する。

【０００８】本発明の他のより具体的な目的は、データ
空間を、ＤＬＡＴ列への仮想ページアドレスの割当を制
御する１以上の空間ＩＤによってクラス分けする、改良
されたＤＬＡＴ論理装置を提供することにある。

【０００９】

【課題を解決するための手段】本発明によると、米国特
許第４，１３６，３８５号明細書のシノニム制御の共通
空間ビットに対応する“私用空間ビット”を用いて、異
なるＤＬＡＴアドレス指定アルゴリズムを選択する、改
良されたＤＬＡＴ論理装置が提供される。空間ＩＤビッ
トを用いてさらに、データ空間をサブクラスに分け、各
サブクラスに対し、ページ・アドレスビットに基づい
て、固有のアルゴリズムを選択する。ＤＬＡＴ選択ビッ
トを生成するために、排他的ＯＲ関数を用いる。

【００１０】この手法は私用空間のシノニムの発生を最
小にし、共通空間のシノニムの発生を最大にする。その
結果、前者がスラッシングを最小化し、後者がＤＬＡＴ
共通ビットの値を最大化するので、改良されたパフォー
マンスが得られる。

【００１１】

【実施例】以下の説明において、登録簿索引テーブルに
対し“ＤＬＡＴ”の用語を用いるが、この用語は変換索
引緩衝機構“ＴＬＢ”（ｔｒａｎｓｌａｔｉｏｎ ｌｏ
ｏｋ−ａｓｉｄｅ ｂｕｆｆｅｒ）と相互交換的に用い
ることができることを、当業者は理解するだろう。以下
の説明のために、ページングおよびセグメンテーション
仮想アドレス・システムを仮定する。このシステムにお
ける仮想アドレスのフォーマットを図１に示し、このフ
ォーマットは、セグメント・インデックス（ＳＸ）とし
てｓビット、ページ・インデックス（ＰＸ）としてｐビ
ット、変位インデックス（ｄｉｓｐｌａｃｅｍｅｎｔ
ｉｎｄｅｘ：ＤＸ）としてｄビットを含んでいる。仮想
アドレスは、例えば、３１ビットとし、そのうちの、ビ
ットＡ１〜Ａ１１はセグメントビットを含み、ビットＡ
１２〜Ａ１９はページビットを含み、ビットＡ２０〜Ａ
３１は変位ビットを含むことになる。

【００１２】図２に示すように、仮想アドレスはアドレ
ス・ジェネレータ２０によって生成される。アドレス・
ジェネレータ２０はＣＰＵ（ｃｅｎｔｒａｌ ｐｒｏｃ
ｅｓｓｉｎｇ ｕｎｉｔ：中央処理装置，図示せず）の
一部である。最も最近参照されたページは、ＤＬＡＴ２
１内にエントリを有する。２５６個の合同クラスを有す
るＤＬＡＴにおいては、仮想アドレスのビットＡ１２〜
Ａ１９が、ＤＬＡＴをアドレス指定するのに用いられ
る。ＤＬＡＴ２１から読み出されたアドレス・エントリ
からの仮想ページＩＤビットは、比較器２２において、
仮想アドレスのビットＡ１〜Ａ１１と比較される。一致
がない場合をＤＬＡＴ誤りという。ＤＬＡＴ誤りが発生
すると、例えば、セグメントまたはページ・テーブル・
サーチを通じてアドレス翻訳が得られ、ＤＬＡＴ内に置
かれる。このサーチを実施する構造は、バッファ制御機
構（ｂｕｆｆｅｒ ｃｏｎｔｒｏｌ ｅｌｅｍｅｎｔ：
ＢＣＥ）と呼ばれる。

【００１３】セグメントまたはページ・テーブル・サー
チは、セグメント・テーブル・オリジンレジスタ２３の
値と、仮想アドレスのビットＡ１〜Ａ１１を、加算器２
４において加算し、セグメント・マップ・テーブル２５
に対するインデックス値を得ることにより開始する。次
に、セグメント・マップ・テーブル２５からのエントリ
出力を、ページ・マップ・テーブル２６のエントリに対
するインデックスとして用いる。各セグメントには個別
のページ・マップ・テーブルが存在している。ページ・
マップ・テーブル２６からのエントリ出力は、実記憶内
で仮想ページが存在するページ・フレームを与え、ＯＲ
ゲート２７に引き渡され、仮想アドレス・ジェネレータ
２０の変位ビットＡ２０〜Ａ３１と連結されて、実アド
レスレジスタ２８に実アドレスを形成する。

【００１４】一方、ＤＬＡＴ２１に一致がある場合、比
較器２２はＡＮＤゲート２９をイネーブルし、ＡＮＤゲ
ート２９はエントリ出力をＤＬＡＴ２１からＯＲゲート
２７に引き渡す。この場合、ＤＬＡＴ２１からのエント
リ出力は、実アドレスのフィールドに対応付けられ、こ
のフィールドは変位ビットＡ２０〜Ａ３１に連結され
て、レジスタ２８に実記憶アドレスを形成する。明らか
に、このアドレス変換プロセスは、ＤＬＡＴ誤りで発生
したセグメントまたはページ・テーブル・サーチのプロ
セスよりも、相当速い。セグメントまたはページ・テー
ブル・サーチは、完了するのに１５〜８０マシンサイク
ルを要するのに対し、ＤＬＡＴアクセスは１マシンサイ
クルで完了する。

【００１５】通常、多くのアドレス変換要求はＤＬＡＴ
のサーチによって生成される。一方、セグメントまたは
ページ・テーブル・サーチは、ＤＬＡＴによって変換を
行うより多くの数のプロセッサ・サイクルを要するだけ
でなく、セグメントまたはページ・テーブル・サーチは
それ自身で、変換失敗の可能性がないわけではない。例
えば、セグメント・マップ・テーブル・サーチは、セグ
メントが１次記憶すなわち主記憶に存在しないことを示
す場合があり得る。そのときは、オペレーティングシス
テムに命じてセグメントを２次記憶、すなわち直接アク
セス記憶装置（ｄｉｒｅｃｔ ａｃｃｅｓｓ ｓｔｏｒ
ａｇｅ ｄｅｖｉｃｅ：ＤＡＳＤ）に配置させ、そのセ
グメントに対しページ・テーブルを生成させ、適切なペ
ージを１次記憶にロードするが、それによってプロセス
内の既存ページを排除することとなる。

【００１６】たとえセグメントが１次記憶に存在し、所
望のページが１次記憶に存在していない場合もある。そ
のときも、オペレーティングシステムに命じてページを
２次記憶に配置させ、ページを１次記憶にロードする
が、プロセス内の既存ページを排除することとなる。２
次記憶アクセスのプロセスは、数百プロセッサ・サイク
ルともなり得る。

【００１７】これまでの説明は従来のＤＬＡＴ構造に対
するものである。この従来のＤＬＡＴ構造に関する問題
は、複数のアドレス空間に対する仮想アドレスを同時
に、実主記憶アドレスに変換することのできるデータ処
理システムにおける、ＤＬＡＴシノニムエントリの問題
を解消しない。ここで、「シノニムエントリ」とは、異
なるアドレス空間が、共有されたプログラムおよびデー
タの同一セットにアクセスせねばならない場合をいう。
その問題は、上述のＧａｎｎｏｎ他によるの米国特許第
４，１３６，３８５号明細書において示され、Ｇａｎｎ
ｏｎ他は共通空間ビットを用いた特別の制御を与えてい
る。しかし、これは、複数のデータ空間での処理の際、
仮想ページアドレスの周期性によって引き起こされる問
題を示していない。すなわち、Ａ，Ｂ，およびＣが同一
の仮想ページアドレス（例えば０）および異なるデータ
空間を有し、従来の２ウェイ（ＸおよびＹサイド）ＤＬ
ＡＴ構造を有する周期的処理の例 Ａ（ｉ）＋Ｂ（ｉ）＝Ｃ（ｉ） では、Ａ（ｉ）およびＢ（ｉ）に対する関連実アドレス
は、アドレス変換が完了した後に、それぞれがＤＬＡＴ
のＸおよびＹサイドの０番地にロードされる。Ｃ（ｉ）
の関連実アドレスは、アドレス変換の後、ＤＬＡＴのＸ
サイドの同じアドレスにロードされ、Ａ（ｉ）のＤＬＡ
Ｔエントリを上書きする。次のループで、Ａ（ｉ）につ
いてはＤＬＡＴ誤りを発生するため、再変換に多くのマ
シンサイクルを要する。さらに、再変換されたＡ（ｉ）
の関連実アドレスはＤＬＡＴのＹサイドにロードされ、
Ｂ（ｉ）のＤＬＡＴエントリを上書きするので、同様の
問題を引き起こす。この種のＤＬＡＴスラッシングは著
しいシステム・パフォーマンスの劣化を招く。

【００１８】本発明はアドレス空間とデータ空間を識別
する。この種の識別機構は既知であり、上述のＧａｎｎ
ｏｎ他の米国特許第４，１３６，３８５号明細書が教示
している。セグメント・テーブル指定（ＳＴＤ）ビット
“２３”は私用空間（データ空間）ビットとして定義さ
れている。図３は、文字“ｐ”というラベルを付けたＳ
ＴＤビット“２３”を示す。このＳＴＤビットは、論理
値“１”であると、ＤＬＡＴ内でデータ空間を分離する
のに用いられる。ＳＴＤビット“２３”が論理値“０”
のときは、アドレス空間に対する、共通セグメントビッ
トのＤＬＡＴパフォーマンス値を保持するのに用いられ
る。

【００１９】本発明は、この機構の上に、１以上の空間
ＩＤ（ＳＰＡＣＥ−ＩＤ）でデータ空間をサブクラスに
分け、（例えばノンコスタント（ｎｏｎ−ｃｏｎｓｔａ
ｎｔ）またはランダムな）下位ビットを識別することに
よって、成り立っている。図４は、セグメント・テーブ
ル・オリジン（ＳＴＯ）ビット“１”〜“１９”をＳＰ
ＡＣＥ−ＩＤビットとして示している。ＩＢＭ社のＭＶ
Ｓシステムにおいては、これらのビットはＳＴＯレジス
タに格納され、アンハッシュト（ｕｎｈａｓｈｅｄ）ノ
ンコンスタント下位ビット、または多くのＳＴＯノンコ
ンスタントビットのハッシュの下位出力ビットとなるこ
とができる。データ空間の各サブクラスに対し、仮想ペ
ージ・アドレス（ＰＡＧＥ−ＡＤＤＲ）ビットを用い
て、固有のアルゴリズムを選択して、ＤＬＡＴ列に仮想
ページ・アドレスの割当を行う。これらのビットは、ア
ンハッシュトＰＡＧＥ−ＡＤＤＲビット、または多くの
ＰＡＧＥ−ＡＤＤＲビットのハッシュの出力ビットとな
ることができる。ＭＶＳ環境はＩＢＭ社の多重仮想記憶
（Ｍｕｌｔｉｐｌｅ Ｖｉｒｔｕａｌ Ｓｔｏｒａｇ
ｅ：ＭＶＳ）オペレーティングシステムを参照し、この
オペレーティングシステムは１９７４年中頃にメインフ
レーム・コンピュータの分野に導入された。このオペレ
ーティングシステムの一般的な説明については、例えば
上述のＤｅｉｔｅｌの著書の第２１章を参照されたい。

【００２０】一実施例では、２（偶数または奇数）デー
タ空間サブクラス設計が、ＭＶＳ環境におけるビット
“１７”のようなデータ空間アンハッシュトＳＴＯビッ
トと、仮想ページ・アンハッシュトＰＡＧＥ−ＡＤＤＲ
上位ビットとの排他的ＯＲによって実現される。この設
計の結果は、次の通りである。偶数サブクラス・データ
空間（ＳＴＯビット“１７”＝０）に対して、０値ＰＡ
ＧＥ−ＡＤＤＲ上位ビットを有するデータ空間ページア
ドレスを、ＤＬＡＴの偶数列に割当て、１値ＰＡＧＥ−
ＡＤＤＲ上位ビットを有するデータ空間ページアドレス
を、ＤＬＡＴの奇数列に割当てる。奇数サブクラス・デ
ータ空間（ＳＴＯビット“１７”＝１）に対して、０値
ＰＡＧＥ−ＡＤＤＲ上位ビットを有するデータ空間ペー
ジアドレスを、ＤＬＡＴの奇数列に割当て、１値ＰＡＧ
Ｅ−ＡＤＤＲ上位ビットを有するデータ空間ページアド
レスを、ＤＬＡＴの偶数列に割当てる。

【００２１】２５６×２個のＤＬＡＴがあるとする。も
し空間ＡおよびＣのサブクラスが０であり、空間Ｂのサ
ブクラスが１であるならば、Ａの各対応偶数ページをＤ
ＬＡＴ偶数列に割当て、Ｂの各対応偶数ページをＤＬＡ
Ｔ奇数列に割当て、Ｃの各対応偶数ページをＤＬＡＴ偶
数列に割当てる。同様にして、Ａの各対応奇数ページを
ＤＬＡＴ奇数列に割当て、Ｂの各対応奇数ページをＤＬ
ＡＴ偶数列に割当て、Ｃの各対応奇数ページをＤＬＡＴ
奇数列に割当てる。

【００２２】図５は排他的ＯＲ演算を表で表現したもの
で、前述の関係を示している。図５において注目すべき
は、０サブクラス・データ空間割当ルールが、アドレス
空間に対する割当ルールと同一であることである。周期
的プロセッシングの例、Ａ（ｉ）＋Ｂ（ｉ）＝Ｃ（ｉ）
に対し、もし３つのデータ空間の少なくとも１つが、Ｓ
ＴＯ下位ビットによって判別された他の２つのデータ空
間と異なるサブクラスであるならば、２ウェイＤＬＡＴ
のスラッシングはほとんどないか、または全くない。デ
ータ空間のこの分離は、データ空間に対するＳＴＯビッ
トのＭＶＳ割当が、通常はランダムであるという事実の
ためである。実際、参照された３つの空間すべてが同一
のサブクラスである確率は０．２５である。さらに、Ｓ
ＴＯビットがＭＶＳによって順番に割当てられるとき、
３つの連続的に生成されたデータ空間すべてが同一のサ
ブクラスである確率は０である。

【００２３】本発明の好適な実施例によるＤＬＡＴ処理
の論理装置を、図６に示し、参照する。この論理装置
は、入力として、仮想アドレス６０からのビットと、Ｓ
ＴＤビット“２３”（参照番号６１）と、セグメント・
テーブル・オリジン（ＳＴＯ）ビット６２からのＳＰＡ
ＣＥ−ＩＤビットとを受け取る。排他的ＯＲゲート６３
は、仮想アドレス６０のＰＡＧＥ−ＡＤＤＲのｎビット
と、ＳＰＡＣＥ−ＩＤ６２からのｎビットとを受け取
る。ＰＡＧＥ−ＡＤＤＲのｎビットは、セレクタ６４に
入力ａとして供給され、排他的ＯＲゲート６３の出力
は、セレクタ６４に入力ｂとして供給される。セレクタ
６４の動作は、“ｐ”ビット（ＳＴＤビット“２３”）
６１によって制御される。

【００２４】ｎデータ空間サブクラスの一般的なケース
は、ｎ個の識別用下位ＳＰＡＣＥ−ＩＤビットと、ｎ個
の上位仮想ページ・アドレス（ＰＡＧＥ−ＡＤＤＲ）ビ
ットとの各組合せに対する、ｎビットの固有セットを生
成することにより得られる。ＤＬＡＴ６５に対するｎ個
の上位有効列選択ビットの生成プロセスは、セレクタ６
４および排他的ＯＲゲート６３から得られる。ＤＬＡＴ
６５の構造は従来のものであり、好適な構造はＩＢＭ３
０９０−Ｓマシンに使用されている構造である。各ＤＬ
ＡＴエントリは、１９個のＳＴＯビットと、１個の共通
空間ビットと、１個の私用空間ビットと、１１個の上位
仮想アドレスビットと、１９個の上位実アドレスビット
とを含むフィールドを有している。

【００２５】“ｐ”ビット６１が０のとき、セレクタ６
４は、ａ入力のｎ個の上位ＰＡＧＥ−ＡＤＤＲビット６
０を選択する。“ｐ”ビット６１が１のとき、セレクタ
６４は、ｎ個の識別用下位ＳＰＡＣＥ−ＩＤ（ＳＴＯ）
ビット６２と、ｎ個の上位ＰＡＧＥ−ＡＤＤＲビット６
０との排他的ＯＲによって生成されたｂ入力のｎビット
を選択する。ＤＬＡＴ６５に対する８−ｎ個の下位有効
ＤＬＡＴ列選択ビットは、仮想アドレス６０のページ・
アドレスフィールドＰＸからの、８−ｎ個のアンハッシ
ュト下位ページ・アドレスビットである。留意すべき
は、もし排他的ＯＲ関数が実行されず、その代わりに下
位ＳＰＡＣＥ−ＩＤビット６２が無変更に置換されるな
らば、全ＤＬＡＴの再割振りではなく、ＤＬＡＴの分割
が生じる。

【００２６】ＤＬＡＴヒットは、比較器６６によって実
行される３ウェイ比較関数によって判別される。ＣＭＰ
Ｒ１関数は、ＳＰＡＣＥ−ＩＤビット６２と、ＤＬＡＴ
６５から読み出されたＳＴＯビットとが等しいとき、２
進数“１”を出力する。ＣＭＰＲ２関数は、“ｐ”ビッ
ト６１と、ＤＬＡＴ６５から読み出された対応“ｐ”ビ
ットとが等しいとき、２進数“１”を出力する。ＣＭＰ
Ｒ３関数は、仮想アドレス６０のセグメント・アドレス
ビットと、ＤＬＡＴ６５から読み出された仮想アドレス
（ＶＡ）とが等しいとき、２進数“１”を出力する。３
つの比較関数全てが２進数“１”出力を生成するとき、
ＤＬＡＴヒットが示される。ＤＬＡＴヒットは、選択さ
れたＤＬＡＴエントリの共通空間“ｃ”ビットが２進数
“１”であり、かつＣＭＰＲ３関数が２進数“１”のと
きにも、形成される。アーキテクチャは、“ｐ”ビット
と“ｃ”ビットの両方が、同一のアドレス変換で１にな
るケースを防止している。その結果、どんなＤＬＡＴエ
ントリも、“ｐ”および“ｃ”ビットの両方を“１”に
することはない。

【００２７】ｎ＝２の場合の実施に対し、２つのＳＰＡ
ＣＥ−ＩＤビットと２つの上位ＰＡＧＥ−ＡＤＤＲビッ
トとの組合せに対するこの排他的ＯＲ演算の結果値を、
図７の表に示す。留意すべきは、０サブクラス・データ
空間割当ルールは、アドレス空間に対する割当ルールと
同じであることである。

【００２８】ｎ＝２の実施に対し、ＤＬＡＴは仮想ペー
ジ・アドレス（ＰＡＧＥ−ＡＤＤＲ）に対して４つのサ
ブクラスに論理的に分割される。ｎ＝２に対し２５６×
２個のＤＬＡＴを与える。もし、空間Ａ，Ｂ，およびＣ
がそれぞれサブクラス“００”，“０１”，および“１
０”であるならば、周期的処理の例、Ａ（ｉ）＋Ｂ
（ｉ）＝Ｃ（ｉ）に対し、２ウェイＤＬＡＴのスラッシ
ングは発生しない。ＭＶＳは、データ空間に、ＳＴＤビ
ットをランダムに割当てるので、参照される３つのデー
タ空間全てが同じサブクラスになる確率は、小である
（すなわち０．０６２５）。ＭＶＳにおいて、ＳＴＤビ
ットが順番に割当てられるとき、３つの連続的に生成さ
れたデータ空間全てが同じサブクラスになる確率は０と
なることも考えられる。

【００２９】ｎ＝３の実施に対し、３つのＳＰＡＣＥ−
ＩＤビットと３つの上位ＰＡＧＥ−ＡＤＤＲビットとの
全ての組合せに対する排他的ＯＲ演算の結果値を、図８
の表に示す。留意すべきは、０サブクラス・データ空間
割当ルールは、アドレス空間に対する割当ルールと同じ
であることである。ｎ＝３の実施に対する実際の効果
は、ＤＬＡＴが、同じ仮想ページ・アドレス（ＰＡＧＥ
−ＡＤＤＲ）に対して、論理的に８個のサブクラスに分
割されることである。このため、周期的処理の例、Ａ
（ｉ）＋Ｂ（ｉ）＝Ｃ（ｉ）に対し、２ウェイＤＬＡＴ
のスラッシングはほとんどない。この最小スラッシング
は、データ空間へのＳＴＤビットのランダムなＭＶＳ割
当から生じる。参照される３つの空間すべてが同じサブ
クラスである確率は、非常に小さい（すなわち、０．０
１５６）。

【００３０】ｎ＝８の場合の実施に対し、データ空間の
同様のＰＡＧＥ−ＡＤＤＲに対するデータ空間ＤＬＡＴ
サブクラス全てに亘る割当の最大分散が存在する。この
分散は、データ空間シノニムによるＤＬＡＴスラッシン
グを最小化する。一方、アドレス空間の同様のＰＡＧＥ
−ＡＤＤＲに対し、０データ空間ＤＬＡＴサブクラスへ
の割当の最大集中が有効に存在する。この集中は、アド
レス空間に対する共通セグメントのパフォーマンス・ア
ドバーンテジを許可する。

【００３１】本発明は好適な実施例に関して説明した
が、当業者であれば、本発明の精神および範囲から逸脱
することなく、変形，変更が可能なことは明らかであ
る。

【図面の簡単な説明】

【図１】仮想アドレスのフォーマットを示すブロック図
である。

【図２】従来の動的アドレス変換機構のブロック図であ
る。

【図３】私用空間ビットを示すセグメント・テーブル指
定（ＳＴＤ）のフォーマットを示すブロック図である。

【図４】図３のＳＴＤの一部で、ＳＰＡＣＥ−ＩＤビッ
トとして用いられるセグメント・テーブル・オリジン
（ＳＴＯ）を示す部分図である。

【図５】ＳＴＤビットを用いた排他的ＯＲ演算を示す表
であり、２つのサブクラスが定義されている。

【図６】図５の排他的ＯＲ演算を実施するハードウェア
を示すブロック図である。

【図７】２つの空間ＩＤビットを用いた排他的ＯＲ演算
を示す表であり、４つのサブクラスが定義されている。

【図８】３つの空間ＩＤビットを用いた排他的ＯＲ演算
を示す表であり、８つのサブクラスが定義されている。

【符号の説明】

２０ アドレス・ジェネレータ ２２ 比較器 ２３ セグメント・テーブル・オリジンレジスタ ２４ 加算器 ２５ セグメント・マップ・テーブル ２６ ページ・マップ・テーブル ２７ ＯＲゲート ２８ 実アドレスレジスタ ６０ 仮想アドレス（ＰＡＧＥ−ＡＤＤＲ） ６１ ＳＴＤビット“２３”（“ｐ”） ６２ ＳＴＯビット（ＳＰＡＣＥ−ＩＤビット） ６３ 排他的ＯＲゲート ６４ セレクタ ６５ ＤＬＡＴ

───────────────────────────────────────────────────── フロントページの続き (72)発明者 リチャード・ジョン・シュマルツ アメリカ合衆国 ニューヨーク州 ワッピ ンガー フォールズ エッジ ヒル ドラ イブ ７ (72)発明者 セオドア・ジェローム・シュミット アメリカ合衆国 ニューヨーク州 キング ストン クリフトン アベニュー 98 (72)発明者 アーノルド・スチーブン・トラン アメリカ合衆国 ニューヨーク州 ショー カン メアリー ルー レーン ６ (72)発明者 シー−シュン・ステファン・タング アメリカ合衆国 ニューヨーク州 キング ストン レイニー レーン 18

Claims (9)

【特許請求の範囲】
1. 【請求項１】同じ仮想アドレスを有する異なるアドレス
   空間内にページを有することができ、前記アドレス空間
   は個々のセグメント・テーブルによって識別される仮想
   記憶システムのための、登録簿索引テーブル論理装置に
   おいて、 アドレス空間とデータ空間とを識別する第１の手段と、 １以上の空間ＩＤ識別用下位ビットによって、データ空
   間をサブクラスに分ける第２の手段と、 前記第１および第２の手段に応答し、仮想ページ・アド
   レスビットを用いて、登録簿索引テーブルの列に、仮想
   ページ・アドレスを割当てるために、データ空間の各サ
   ブクラスに固有のアルゴリズムを供給する第３の手段
   と、を備えることを特徴とする、登録簿索引テーブル論
   理装置。
2. 【請求項２】前記第１の手段は、セットされるとデータ
   空間を指定する私用空間ビットであることを特徴とす
   る、請求項１記載の登録簿索引テーブル論理装置。
3. 【請求項３】前記空間ＩＤ識別用下位ビットは、ｎ個の
   セグメント・テーブル・ビットであり、ｎは前記データ
   空間のサブクラスの数を示すことを特徴とする、請求項
   ２記載の登録簿索引テーブル論理装置。
4. 【請求項４】前記空間ＩＤ識別用下位ビットの数が２で
   あることを特徴とする、請求項３記載の登録簿索引テー
   ブル論理装置。
5. 【請求項５】前記空間ＩＤ識別用下位ビットの数が３で
   あることを特徴とする、請求項３記載の登録簿索引テー
   ブル論理装置。
6. 【請求項６】前記第３の手段が、 仮想アドレスのページ・アドレスのｎビットと、前記セ
   グメント・テーブル・オリジンビットのｎビットとを排
   他的ＯＲ論理によって結合して、第１の出力を形成する
   排他的ＯＲ手段と、 前記私用空間ビットがセットされたとき、登録簿索引テ
   ーブル列選択信号を発生させるために前記第１の出力を
   選択し、前記私用空間ビットがセットされないとき、前
   記ページ・アドレスの前記ｎビットを選択する前記登録
   簿索引テーブル列選択信号を発生させるための手段と、
   を有することを特徴とする、請求項３記載の登録簿索引
   テーブル論理装置。
7. 【請求項７】前記第１および第２の手段と、前記仮想ア
   ドレスのセグメント部と、前記登録簿索引テーブルから
   の出力とに応答し、前記登録簿索引テーブルから読み出
   された実アドレスに対するヒットを判別する３ウェイ比
   較手段をさらに備えることを特徴とする、請求項６記載
   の登録簿索引テーブル論理装置。
8. 【請求項８】前記３ウェイ比較手段が、 前記セグメント・テーブル・オリジンビットと、前記登
   録簿索引テーブルから読み出された対応セグメント・テ
   ーブル・オリジンビットとを比較する第１の比較手段
   と、 前記私用空間ビットと、前記登録簿索引テーブルから読
   み出された対応私用空間ビットとを比較する第２の比較
   手段と、 前記仮想アドレスの前記セグメント部と、前記登録簿索
   引テーブルから読み出された仮想アドレスの対応部とを
   比較する第３の比較手段とを有し、 前記第１，第２，および第３の比較手段全てによる比較
   がヒットを示すことを特徴とする、請求項７記載の登録
   簿索引テーブル論理装置。
9. 【請求項９】共通アドレス空間と私用アドレス空間との
   間の識別手段をさらに備え、共通空間ビットはセットさ
   れると共通アドレス空間を示し、前記共通空間ビットお
   よび前記私用空間ビットのセッティングは相互に排他的
   であり、ヒットもまた前記第３の比較手段と、セットさ
   れた前記共通空間ビットとの比較によって判別されるこ
   とを特徴とする、請求項８記載の登録簿索引テーブル論
   理装置。