(57)【特許請求の範囲】
【請求項１】
物理メモリにマッピングされる仮想メモリを備えたコンピュータ・システムのアドレス変換を行う装置において、
基底物理アドレス、その基底物理アドレスから始まる物理アドレス範囲、及び変換エントリ・ポインタを備え、物理メモリの連続部分を記述する少なくとも１つのページ・フレーム記述子と、
基底仮想アドレス、基底仮想アドレスから始まる仮想アドレス範囲、変換ブロックの仮想アドレス範囲をマッピングするのに利用されるページ・サイズ、変換ブロック・ポインタを備えるヘッダ、及びそれぞれが逆方向ポインタを備える少なくとも１つの変換エントリを備える変換ブロックであって、変換ブロックの各変換エントリが仮想アドレス範囲における多様なサイズの変換範囲に対応し、ある変換エントリの変換範囲が対応する物理メモリ・ページ・フレームを有する場合、変換エントリの逆方向ポインタが対応するページ・フレームを記述したページ・フレーム記述子を指示し、このページ・フレーム記述子の変換エントリ・ポインタが変換エントリを指示するようになっている、仮想メモリの連続部分を記述するための少なくとも１つの変換ブロックと、
複数のハッシュ・エントリを備え、各ハッシュ・エントリには変換ヘッダ・ポインタ、及びハッシュ・エントリに固有の関連するハッシュ・インデックスが設けられており、少なくとも１つの変換ブロックの仮想アドレス変換連鎖が存在して、仮想アドレス変換連鎖の各変換ブロック毎に仮想アドレス範囲があり、仮想アドレス変換連鎖の変換ブロックにおける仮想アドレス範囲の各仮想アドレスにハッシングを施すことによって、同じハッシュ・エントリのハッシュ・インデックスを得ることが可能になる場合、ハッシュ・インデックスが得られたハッシュ・エントリの変換ヘッダ・ポインタは仮想アドレス変換連鎖における第１の変換ブロックを指示し、仮想アドレス変換連鎖の中に２つ以上の変換ブロックがある場合、第１の変換ブロックの変換ブロック・ポインタが仮想アドレス変換連鎖の第２の変換ブロックを指示し、第１の変換ブロックを除く仮想アドレス変換連鎖の全ての変換ブロックが、仮想アドレス変換連鎖における異なる変換ブロックの変換ブロック・ポインタによって指示されるハッシュ・リストから構成される、
アドレス変換装置。
【請求項２】
物理メモリにマッピングされる仮想メモリを備えたコンピュータ・システムでアドレス変換を行う方法において、
（ａ）基底物理アドレス、基底物理アドレスから始まる物理アドレス範囲、及び変換エントリ・ポインタを備え、物理メモリの連続部分を記述する少なくとも１つのページ・フレーム記述子を設けるステップと、
（ｂ）基底仮想アドレス、基底仮想アドレスから始まる仮想アドレス範囲、変換ブロックの仮想アドレス範囲をマッピングするのに利用されるページ・サイズ、変換ブロック・ポインタを備えるヘッダ、及びそれぞれが逆方向ポインタを備える少なくとも１つの変換エントリを備える変換ブロックであって、変換ブロックの各変換エントリイが仮想アドレス範囲における多様なサイズの変換範囲に対応し、ある変換エントリの変換範囲が対応する物理メモリ・ページ・フレームを有する場合、変換エントリの逆方向ポインタが対応するページ・フレームを記述したページ・フレーム記述子を指示し、このページ・フレーム記述子の変換エントリ・ポインタが変換エントリを指示するようになっている、仮想メモリの連続部分を記述するための少なくとも１つの変換ブロックを設けるステップと、
（ｃ）複数のハッシュ・エントリを備え、各ハッシュ・エントリには変換ヘッダ・ポインタ、及びハッシュ・エントリに固有の関連するハッシュ・インデックスが設けられており、少なくとも１つの変換ブロックの仮想アドレス変換連鎖が存在して、仮想アドレス変換連鎖の各変換ブロック毎に仮想アドレス範囲があり、仮想アドレス変換連鎖の変換ブロックにおける仮想アドレス範囲の各仮想アドレスにハッシングを施すことによって、同じハッシュ・エントリのハッシュ・インデックスを得ることが可能になる場合、ハッシュ・インデックスが得られたハッシュ・エントリの変換ヘッダ・ポインタは仮想アドレス変換連鎖における第１の変換ブロックを指示し、仮想アドレス変換連鎖の中に２つ以上の変換ブロックがある場合、第１の変換ブロックの変換ブロック・ポインタが仮想アドレス変換連鎖の第２の変換ブロックを指示し、第１の変換ブロックを除く仮想アドレス変換連鎖の全ての変換ブロックが、仮想アドレス変換連鎖における異なる変換ブロックの変換ブロック・ポインタによって指示されるハッシュ・リストを設けるステップと、
（ｄ）変換すべき仮想アドレスを受けるステップと、
（ｅ）変換すべき仮想アドレスから第１の変換ハッシュ・インデックスを抽出するステップと、
（ｆ）第１の変換ハッシュ・インデックスに対応するハッシュ・エントリが空でない場合、第１の変換ハッシュ・インデックスに対応するハッシュ・エントリの変換ヘッダ・ポインタによって指示される変換ブロックを検査を受ける変換ブロックとし、検査を受けた変換ブロックの仮想アドレス範囲を検査して、変換すべき仮想アドレスが、検査を受ける変換ブロックの仮想アドレス範囲内に含まれているか否かを判定するステップと、
（ｇ）変換すべき仮想アドレスが、検査を受ける変換ブロックの仮想アドレス範囲内に含まれている場合、変換すべき仮想アドレスを含む変換範囲を備えた、検査を受ける変換ブロックの変換エントリを検査して、変換エントリが有効か否かを判定し、その変換エントリが有効であれば、変換エントリの逆方向ポインタを利用して、変換エントリによって指示されるページ・フレームを記述するページ・フレーム記述子の位置指定を行うステップと、
（ｈ）変換すべき仮想アドレスが、検査を受ける変換ブロックの仮想アドレス範囲内に含まれていなければ、検査を受ける変換ブロックの変換ブロック・ポインタを検査して、その変換ブロック・ポインタが空でなければ、検査を受ける変換ブロックの変換ブロック・ポインタによって指示された変換ブロックを新たな検査を受ける変換ブロックとしてステップ（ｇ）及び（ｈ）を繰り返すステップから構成される、
アドレス変換方法。
【請求項３】
さらに、
（ｉ）変換すべき物理アドレスを受けるステップと
（ｊ）変換すべき物理アドレスを含む物理アドレス範囲を備えたページ・フレーム記述子が存在するか否かを判定するステップと、
（ｋ）変換すべき物理アドレスを含む物理アドレス範囲を備えたページ・フレーム記述子が存在する場合、そのページ・フレーム記述子の変換エントリ・ポインタを検査して、その変換エントリ・ポインタが変換エントリを指示しているか否かを確認するステップと、
（ｌ）変換エントリ・ポインタが変換エントリを指示している場合、変換エントリ・ポインタによって指示される変換エントリを検査を受ける変換エントリとするステップと、
（ｍ）検査を受ける変換エントリ、及び、検査を受ける変換エントリを含む変換ブロックのヘッダを利用して、変換される物理アドレスに対応する仮想アドレスを識別するステップが含まれていることを特徴とする、
請求項２に記載のアドレス変換方法。
【請求項４】
特定の物理ページが、２つ以上の仮想ページによってマッピング可能であり、変換ブロックの変換エントリには、さらに、正方向ポインタが備わっていて、物理ページが２つ以上の仮想ページによってマッピングされる場合、少なくとも２つの変換エントリを備えた物理アドレス変換連鎖が存在し、物理アドレス変換連鎖の各変換エントリ毎に、ページ・フレーム記述子によって記述される物理ページの物理アドレス範囲の少なくとも一部に対応する仮想アドレス範囲が設けられ、前記ページ・フレーム記述子の変換エントリ・ポインタが、物理アドレス変換連鎖の第１の変換エントリを指示し、第１の変換エントリの正方向ポインタが、物理アドレス変換連鎖における第２の変換エントリを指示し、第１の変換エントリを除く物理アドレス変換連鎖の全ての変換エントリが、物理アドレス変換連鎖における異なる変換エントリの変換エントリ・ポインタによって指示され、さらに、
（ｎ）ステップ（ｌ）で識別される変換エントリを含む物理アドレス変換連鎖における全ての変換エントリを、順次、検査を受ける変換エントリにして、ステップ（ｍ）を繰り返すステップが含まれることを特徴とする、
請求項３に記載のアドレス変換方法。
【請求項５】
物理メモリにマッピングされる仮想メモリを備えたコンピュータ・システムでアドレス変換を行う方法において、
（ａ）基底物理アドレス、基底物理アドレスから始まる物理アドレス範囲、及び変換エントリ・ポインタを備え、物理メモリの連続部分を記述する少なくとも１つのページ・フレーム記述子を設けるステップと、
（ｂ）基底仮想アドレス、基底仮想アドレスから始まる仮想アドレス範囲、変換ブロックの仮想アドレス範囲をマッピングするのに利用されるページ・サイズ、変換ブロック・ポインタを備えるヘッダ、及びそれぞれが逆方向ポインタを備える少なくとも１つの変換エントリを備える変換ブロックであって、変換ブロックの各変換エントリイが仮想アドレス範囲における多様なサイズの変換範囲に対応し、ある変換エントリの変換範囲が対応する物理メモリ・ページ・フレームを有する場合、変換エントリの逆方向ポインタが対応するページ・フレームを記述したページ・フレーム記述子を指示し、このページ・フレーム記述子の変換エントリ・ポインタが変換エントリを指示するようになっている、仮想メモリの連続部分を記述するための少なくとも１つの変換ブロックを設けるステップと、
（ｃ）複数のハッシュ・エントリを備え、各ハッシュ・エントリには変換ヘッダ・ポインタ、及びハッシュ・エントリに固有の関連するハッシュ・インデックスが設けられており、少なくとも１つの変換ブロックの仮想アドレス変換連鎖が存在して、仮想アドレス変換連鎖の各変換ブロック毎に仮想アドレス範囲があり、仮想アドレス変換連鎖の変換ブロックにおける仮想アドレス範囲の各仮想アドレスにハッシングを施すことによって、同じハッシュ・エントリのハッシュ・インデックスを得ることが可能になる場合、ハッシュ・インデックスが得られたハッシュ・エントリの変換ヘッダ・ポインタは仮想アドレス変換連鎖における第１の変換ブロックを指示し、仮想アドレス変換連鎖の中に２つ以上の変換ブロックがある場合、第１の変換ブロックの変換ブロック・ポインタが仮想アドレス変換連鎖の第２の変換ブロックを指示し、第１の変換ブロックを除く仮想アドレス変換連鎖の全ての変換ブロックが、仮想アドレス変換連鎖における異なる変換ブロックの変換ブロック・ポインタによって指示されるハッシュ・リストを設けるステップと、
（ｄ）変換すべき仮想アドレスを受けて、ステップ（ｅ）〜（ｈ）を実施するステップと、
（ｅ）変換すべき仮想アドレスから第１の変換ハッシュ・インデックスを抽出するステップと、
（ｆ）第１の変換ハッシュ・インデックスに対応するハッシュ・エントリが空でない場合、第１の変換ハッシュ・インデックスに対応するハッシュ・エントリの変換ヘッダ・ポインタによって指示される変換ブロックを検査を受ける変換ブロックとし、検査を受けた変換ブロックの仮想アドレス範囲を検査して、変換すべき仮想アドレスが検査を受ける変換ブロックの仮想アドレス範囲内に含まれているか否かを判定するステップと、
（ｇ）変換すべき仮想アドレスが、検査を受ける変換ブロックの仮想アドレス範囲内に含まれている場合、変換すべき仮想アドレスを含む変換範囲を備えた、検査を受ける変換ブロックの変換エントリを検査して、変換エントリが有効か否かを判定し、その変換エントリが有効であれば、変換エントリの逆方向ポインタを利用して、変換エントリによって指示されるページ・フレームを記述するページ・フレーム記述子の位置指定を行うステップと、
（ｈ）変換すべき仮想アドレスが、検査を受ける変換ブロックの仮想アドレス範囲内に含まれていなければ、検査を受ける変換ブロックの変換ブロック・ポインタを検査して、変換ブロック・ポインタが空でなければ、検査を受ける変換ブロックの変換ブロック・ポインタによって指示された変換ブロックを新たな検査を受ける変換ブロックとしてステップ（ｇ）及び（ｈ）を繰り返すステップと、
（ｉ）変換すべき物理アドレスを受けて、ステップ（ｊ）〜（ｍ）を実施するステップと
（ｊ）変換すべき物理アドレスを含む物理アドレス範囲を備えたページ・フレーム記述子が存在するか否かを判定するステップと、
（ｋ）変換すべき物理アドレスを含む物理アドレス範囲を備えたページ・フレーム記述子が存在する場合、そのページ・フレーム記述子の変換エントリ・ポインタを検査して、変換エントリ・ポインタが変換エントリを指示しているか否かを確認するステップと、
（ｌ）変換エントリ・ポインタが変換エントリを指示している場合、変換エントリ・ポインタによって指示される変換エントリを検査を受ける変換エントリとするステップと、
（ｍ）検査を受ける変換エントリ、及び、検査を受ける変換エントリを含む変換ブロックのヘッダを利用して、変換される物理アドレスに対応する仮想アドレスを識別するステップから構成される、
アドレス変換方法。
【請求項６】
特定の物理ページが、２つ以上の仮想ページによってマッピング可能であり、変換ブロックの変換エントリには、さらに、正方向ポインタが備わっていて、物理ページが２つ以上の仮想ページによってマッピングされる場合、少なくとも２つの変換エントリを備えた物理アドレス変換連鎖が存在し、物理アドレス変換連鎖の各変換エントリ毎に、ページ・フレーム記述子によって記述される物理ページの物理アドレス範囲に対応する仮想アドレス範囲が設けられ、前記ページ・フレーム記述子の変換エントリ・ポインタが物理アドレス変換連鎖の第１の変換エントリを指示し、第１の変換エントリの正方向ポインタが物理アドレス変換連鎖における第２の変換エントリを指示し、第１の変換エントリを除く物理アドレス変換連鎖の全ての変換エントリが、物理アドレス変換連鎖における異なる変換エントリの変換エントリ・ポインタによって指示され、さらに、
（ｎ）ステップ（ｌ）で識別される変換エントリを含む物理アドレス変換連鎖における全ての変換エントリを、順次、検査を受ける変換エントリにして、ステップ（ｍ）を繰り返すステップが含まれることを特徴とする、
請求項５に記載のアドレス変換方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、コンピュータ・システムに関するものである。とりわけ、本発明は、仮想メモリ・コンピュータ・システムにおける仮想アドレスと物理アドレスとの変換に関するものである。
【０００２】
【従来の技術】
仮想メモリは、アプリケーションに対して、該システムが、大形で、一様な一次メモリ（実際には、より小型で、断片化され、かつ、ハード・ディスクのような二次記憶装置によって部分的にシミュレートされるか、あるいは、そのいずれかである）を提供するものであるかのように思わせることが可能な技法である。アプリケーションは、特殊なハードウェアによって物理アドレスに変換（マッピング）される仮想アドレスを介してメモリにアクセスする。ページング及びセグメンテーションは、仮想メモリの一般的な２つの実施手段である。
【０００３】
ページング技法を利用して仮想メモリを実施する場合、仮想アドレス空間は、ページと呼ばれるいくつかの固定サイズのブロックに分割され、各ページは、該システムにおいて利用可能な、同様のサイズの物理ページのうち任意のページにマッピングすることが可能である。一般に、メモリ管理ユニット（ＭＭＵ）またはページ式メモリ管理ユニット（ＰＭＭＵ）のような特殊メモリ管理ハードウェアが、仮想アドレスから物理アドレスへのアドレス変換を実施する。このタイプのメモリ管理では、物理（システム）メモリに存在しないデータにアクセスを試みると、ＰＭＭＵが中央演算処理装置（ＣＰＵ）に対して割り込み信号を送り、オペレーティング・システムは、アプリケーションには、「分からない」ようにして、他の記憶装置（ハード・ディスクのような）からのデータを転送する。
【０００４】
仮想メモリ案の１つでは、仮想メモリ空間から物理メモリ空間へのマッピングは１回だけしか行われない。一方、他の実施例では、いくつかのアドレス空間が設けられ、それぞれ、物理アドレス空間に対してそれ自体のマッピングを行うことが可能である。従って、第１のプロセスでは、第１の仮想アドレスを利用して所定の物理アドレスを参照することが可能であり、マルチプロセッサ環境において、同じＣＰＵまたは異なるＣＰＵで実行される第２のプロセスでは、第２の仮想アドレスによって、前記所定の物理アドレスを参照することになる。こうした場合、同じ物理アドレスに対応する２つの仮想アドレスは、「エイリアス又は別名」と呼ばれる。
【０００５】
ＣＰＵには、２つ以上のサイズの仮想ページを利用して、操作可能なものもある。このため、マッピングされる仮想アドレス空間の要求に最も良く合致するように、マッピングに利用される仮想ページ・サイズを選択することが可能になる。大きいページを利用する場合、ＭＭＵにおける単一変換エントリを利用して、大量の仮想メモリを変換することが可能である。従って、ＭＭＵが必要とする資源が少なくなれば、結果として、性能が向上することになる。しかし、大きいページを利用すると、小さいページが用いられる場合には遭遇することのない、メモリの断片化問題が生じることになる。
【０００６】
【発明が解決しようとする課題】
本発明の目的は、物理メモリにマッピングされる仮想メモリを備えたコンピュータ・システムのためにアドレス変換を行うための新規な方法および装置を提供することにある。
【０００７】
【課題を解決するための手段】
その装置は、物理メモリの連続部分を記述するための少なくとも１つのページ・フレーム記述子と、仮想メモリの連続部分を記述するための少なくとも１つの変換ブロックと、ハッシュ・リストを備えている。
【０００８】
各ページ・フレーム記述子は、基底物理アドレス、基底物理アドレスから始まる物理アドレス範囲、及び、変換エントリ・ポインタを備えている。
【０００９】
各変換ブロックは、基底仮想アドレス、基底仮想アドレスから始まる仮想アドレス範囲、及び、変換ブロックの仮想アドレス範囲のマッピングに利用されるページ・サイズを備えている。各変換ブロックは、さらに、ヘッダ、及び、少なくとも１つの変換エントリも備えている。各ヘッダは変換ブロック・ポインタを備え、各変換エントリは逆方向ポインタを備えている。変換ブロックの各変換エントリは、変換ブロックの仮想アドレス範囲における多様なサイズの変換範囲に対応している。
【００１０】
ある変換エントリの変換範囲が物理メモリ・ページ・フレームによって指示される場合、変換エントリの逆方向ポインタが対応するページ・フレームを記述したページ・フレーム記述子を指示し、このページ・フレーム記述子の変換エントリ・ポインタが、変換エントリを指示する。
【００１１】
ハッシュ・リストは、複数のハッシュ・エントリを備えている。各ハッシュ・エントリには、変換ヘッダ・ポインタ、及び、ハッシュ・エントリに固有の関連するハッシュ・インデックスが設けられている。少なくとも１つの変換ブロックから成る仮想アドレス変換連鎖が存在している場合、仮想アドレス変換連鎖の各変換ブロック毎に仮想アドレス範囲があり、仮想アドレス変換連鎖の変換ブロックにおける仮想アドレス範囲の各仮想アドレスにハッシングを施すことによって、同じハッシュ・エントリのハッシュ・インデックスを得ることが可能になる。ハッシュ・インデックスが得られたハッシュ・エントリの変換ヘッダ・ポインタは、仮想アドレス変換連鎖における第１の変換ブロックを指示する。仮想アドレス変換連鎖の中に、２つ以上の変換ブロックがある場合、第１の変換ブロックの変換ブロック・ポインタが、仮想アドレス変換連鎖の第２の変換ブロックを指示し、第１の変換ブロックを除く仮想アドレス変換連鎖の全ての変換ブロックが、仮想アドレス変換連鎖における異なる変換ブロックの変換ブロック・ポインタによって指示される。
【００１２】
【実施例】
仮想アドレスと物理アドレスとの間における変換を行い、同時に複数ページ・サイズを支援する変換メカニズムを実現するための方法及び装置が開示される。例えば、仮想アドレスが与えられると、変換メカニズムは、対応する物理アドレス（存在すれば）を提供する。代わりに、物理アドレスが与えられると、変換メカニズムは、対応する仮想アドレス（存在すれば）を提供する。エイリアシングが可能な場合、変換メカニズムは、特定の物理アドレスに対する全ての仮想アドレスを提供する。変換メカニズムは、多様なサイズのページの１つによって、物理メモリの一部をマッピングできるようにすることによって、複数ページ・サイズを支援する。変換メカニズムは、また、さまざまなサイズのページによって、大きい物理ページの多重マッピングを行えるようにすることによって、複数ページ・サイズを支援する。
【００１３】
以下の解説では、説明のため、本発明の完全な理解が得られるように、特定の数、材料、及び、構成が示される。ただし、当該技術の熟練者には明らかなように、特定の細部にこだわらなくても、本発明の実施は可能である。他の例においては、本発明が不必要に曖昧にならないようにするため、周知のシステムは、略図またはブロック図の形で示される。
【００１４】
ここで、図１を参照すると、複数ページ・サイズを支援するアドレス変換メカニズムを利用した、仮想メモリ・コンピュータ・システムの実施例が示されている。アドレス変換メカニズムは、変換すべき仮想アドレス（ＶＡ）が与えられると、対応する物理アドレス（ＰＡ）が存在する場合には、仮想アドレスを対応する物理アドレスに変換する。アドレス変換メカニズムは、変換すべき物理アドレスが与えられると、対応する仮想アドレスが存在する場合には、物理アドレスを対応する仮想アドレスに変換する。エイリアシングが可能な場合、アドレス変換メカニズムは、与えられた物理アドレスに対応する全ての仮想アドレスを見つけることが可能である。
【００１５】
図１のコンピュータ・システム１００において、中央演算処理装置（ＣＰＵ）１１０は、メモリ・バス１２０のようなメモリ相互接続手段によって、一次メモリ１３０及び二次メモリ１４０に結合されている。コンピュータ・システム１００の実施例の場合、中央演算処理装置１１０は、二次メモリ１４０に対するアクセスよりも速く、一次メモリ１３０にアクセスすることが可能である。しかし、二次メモリ１４０は、一次メモリ１３０よりもはるかに大きい。従って、二次メモリ１４０は、一次メモリ１３０よりも多くのデータを保持することが可能である。この実施例の場合、二次メモリ１４０は、ページに分割され、ページは、中央演算処理装置１１０が必要とするところに応じて、一次メモリ１３０に対してスワップ・インまたはスワップ・アウトされる。こうして、中央演算処理装置１１０は、あたかも、一次メモリ１３０の速度で、二次メモリ１４０の全てのメモリにアクセスできるかのように、ほぼ同じ速度で、一次メモリ１３０において利用可能なメモリより多くのメモリにアクセスすることが可能になる。
【００１６】
従って、中央演算処理装置１１０が、データを必要とする場合、まず、一次メモリ１３０をチェックして、一次メモリ１３０に、必要なデータを納めたページが含まれているか否かを確認する。一次メモリ１３０が必要なデータを備えていない場合、必要なデータを納めたページは、二次メモリ１４０から一次メモリ１３０にコピーされるので、中央演算装置１１０によるアクセスが可能になる。
【００１７】
中央演算処理装置１１０内において実行されるプロセスがデータを必要とする場合、該プロセスは、仮想アドレスを利用して、必要なデータを指定することになる。アドレス変換バッファ（ＴＬＢ）１５０は、最近、または、頻繁に用いられる仮想アドレスの小集合に関する仮想アドレス・物理アドレス変換を納めたハードウェア装置である。ＴＬＢ１５０は、ハードウェアで実施されるので、要求された仮想アドレスの物理アドレス変換を中央演算処理装置１１０に対して迅速に供給することが可能である。ただし、ＴＬＢ１５０には、可能性のある仮想アドレスの小集合に関する変換だけしか含まれていない。ＴＬＢ１５０が、中央演算処理装置１１０の要求するアドレス変換を提供することができない場合、別の変換メカニズムを利用して、要求されたアドレス変換を行うことになる。
【００１８】
保守のため、物理アドレスから対応する全ての仮想アドレスに変換することも可能である。例えば、ページが物理メモリから消去された場合、消去されたページを指示している全ての仮想アドレスを見つけることができるので、対応する全ての変換テーブル・エントリを無効にすることが可能である。また、物理アドレスから仮想アドレスに変換する計算ステップが不要になる場合もあるが、やはり、特定の物理ページを指示する仮想ページの位置指定を行う必要はある。例えば、特定の物理アドレスを納めた特定の物理ページを指示する、１つ以上の仮想ページに関連した１つ以上の属性を検査し、あるいは、変更することが必要になる可能性がある。
【００１９】
簡略化のため、今後明らかになるように、物理アドレス・仮想アドレス変換を実施するための基準を作成する毎に、該基準には、特定の物理アドレスを含む特定の物理ページを指示する仮想ページの識別は行われるが、特定の物理アドレスに対応する仮想アドレスを実際に計算するステップは実施されない事例が含まれる。同様に、仮想アドレスから物理アドレスへの変換を計算するステップは、不要であるが、特定の仮想アドレスを指示する変換エントリまたはページ・フレーム記述子の位置を指定することは必要になる場合もある（例えば、１つ以上の属性を検査または変更するため）。やはり、簡略化のため、今後明らかになるように、仮想アドレス・物理アドレス変換を実施するための基準を作成する毎に、該基準には、特定の仮想アドレスに対応する物理アドレスを含む物理ページの識別は行われるが、特定の仮想アドレスに対応する物理アドレスを実際に計算するステップは実施されない事例が含まれる。
【００２０】
次に、図２を参照すると、本発明の実施例の１つに関する階層構造が示されている。図２には、３レベルの変換階層が示されている。ＣＰＵが、仮想アドレスから物理アドレスへの変換を要求する毎に、レベルＩによる変換が試みられる。図２において、レベルＩは、アドレス変換バッファ（ＴＬＢ）２２０のようなメモリ管理ユニット（ＭＭＵ）として示されている。上述のように、レベルＩは、一般に、ハードウェアで実施され、小数のアドレスについて高速変換を行うことを特徴とする。レベルＩにおいて変換可能なアドレス集合は、必要とされる可能性の最も高い変換が、レベルＩにおいて確実に利用できるようにするため、変換集合の構成要素が更新されるのに応じて、動的に変化する。
【００２１】
レベルＩＩの例としては、変換記憶バッファ（ＴＳＢ）がある。本発明の実施例の場合、ＴＳＢは、一次メモリによって実施される。従って、ＴＬＢ２２０ほど速くはないが、ＴＳＢは、ＴＬＢ２２０よりも大きい変換構成要素の集合を保持することが可能である。従って、ＴＬＢ２２０が、変換を提供できない（ＴＬＢ「ミス」）場合、ＴＳＢをテストして、必要な変換がＴＳＢに記憶されているか否かが確認される。その変換がＴＳＢによって提供し得る（ＴＳＢ「ヒット」）場合には、該変換は、ＣＰＵ及びアドレス変換バッファ２２０に提供される。一方、ＴＳＢが変換を提供できない（ＴＳＢ「ミス」）場合には、レベルＩＩＩの変換が実施される。
【００２２】
レベルＩＩＩの変換は、レベルＩＩの変換よりも遅く、総合的であることを特徴とする。一般に、仮想メモリ・オペレーティング・システムは、データ記憶装置に記憶された大形のソフトウェア変換テーブル（ＢＳＴ）２８０を提供する。例えば、データ記憶装置は、一次メモリ、二次メモリ、または、一次メモリと二次メモリの組み合わせとして設けることが可能である。ＢＳＴ２８０は、仮想アドレス空間から物理アドレス空間への全ての存在する変換を含んでいる。従って、レベルＩＩＩの変換は、比較的長時間を要するが、存在すれば、変換を見つけ出すことができる。レベルＩＩＩの変換を行うと、その結果は、ＣＰＵ、変換記憶バッファ、及び、アドレス変換バッファ２２０に提供される。
【００２３】
図２を要約すると、レベルＩの変換は、ＣＰＵがＴＬＢ２２０のようなレベルＩのトランスレータに対する仮想アドレス要求（２１０）を発生すると実施される。レベルＩの変換がうまくゆけば、レベルＩのトランスレータは、要求された仮想アドレス２１０に対応する要求された物理アドレス（２３０）を提供する。
【００２４】
レベルＩの変換が失敗すると、ＴＳＢのようなレベルＩＩのトランスレータに対して、仮想アドレス要求２４０が行われる。レベルＩＩの変換がうまくゆけば、仮想アドレス要求２４０に対応する物理アドレス２６０が、レベルＩのトランスレータに戻され、さらには、ＣＰＵに戻される（物理アドレス２３０）。
【００２５】
一方、レベルＩＩの変換が失敗すると、ＢＳＴ２８０のようなレベルＩＩＩのトランスレータに仮想アドレス要求２７０が送られる。ＢＳＴ２８０は、総合的であるため、物理アドレス変換が存在すれば、物理アドレス２９０としてレベルＩＩのトランスレータ（ＴＳＢ）に戻される。変換は、物理アドレス２６０としてレベルＩのトランスレータ（ＴＬＢ２２０）にも提供され、最終的には、物理アドレス２３０としてＣＰＵに供給される。
【００２６】
本発明の解説は、３レベルの変換を含む実施例によって行っているが、よりレベルの多い、または、少ない変換を含む代替実施例も存在する。さらに、本発明の解説は、ＢＳＴ２８０のようなレベルＩＩＩの大形ソフトウェア変換テーブルの実施例によって行っているが、本発明の代替実施例には、解説の変換メカニズムが、レベルＩのトランスレータとして、あるいは、より可能性が高いのは、レベルＩＩのトランスレータとして利用されるものもある。
【００２７】
次に、図３を参照すると、物理アドレスと仮想アドレスとの関係が示されている。図３には、さらに、仮想アドレス・物理アドレス変換を実施する際に用いられる、ハッシュ・インデックスの導出が示されている。図３において、物理アドレス３１０は、物理ページ・オフセット３２０と物理ページ数３３０から構成されるものとして示されている。物理ページは物理メモリの連続部分である。概念としては、物理ページは、「行」の集合に分割されるものとみなすことが可能であり、この場合、行は、個々にアドレス指定可能な最小のデータ集合を表している。物理ページ・オフセット３２０は、所定の物理ページ内においてアドレス指定されている行を指定する。物理ページ数３３０は、物理ページ集合のうちからどのページが選択されているかを指定する。
【００２８】
物理ページは、さまざまなサイズを有することが可能である。大きいページは、小さいページよりも多くの行を備えることになる。このため、所定の量の物理メモリは、小さいページに分割するよりも、大きいページに分割したほうがページ数を少なくすることができる。従って、小さいページの場合より、大きいページのほうが、物理ページ・オフセット３２０に充当される物理アドレス３１０のビット数が多くなる。相応じて、小さいページの場合より、大きいページのほうが、物理ページ数３３０に充当される物理アドレス３１０のビット数が少なくなる。
【００２９】
所定のページにおける行数が２の整数乗になるように制約が加えられており、所定のページ・サイズに関する物理ページの総数も、やはり、２の整数乗になるように制約が加えられている場合、物理アドレス３１０は、Ｋ＋Ｌビットの２進数として表すことができるが、ここで、物理アドレス３１０のＫビットは、物理ページ数３３０を指定するために利用され、物理アドレス３１０のＬビットは、物理ページ・オフセット３２０を指定するために利用される。
【００３０】
物理アドレス範囲は、１つの大きいページまたはいくつかの小さいページであるかのように取り扱うことが可能である。実施例の１つでは、４０ビットの物理アドレス空間が用いられる。この物理アドレス空間は、サイズが８ＫＢの小さいページと、サイズが６４ＫＢの大きいページを利用して、マッピングされる。この実施例の場合、物理アドレス３１０は４０ビットの２進数である。小さい（８ＫＢ）ページがアドレス指定されている場合、物理アドレス３１０の１３の最下位ビット（ＬＳｂ）（２１３＝８Ｋ）が、物理ページ・オフセット３２０を表すことになる。物理アドレス３１０の２７の上位ビット（ＭＳｂ）が、所定の小さいページに関する物理ページ数３３０を表すことになる。一方、大きい（６４ＫＢ）のページが利用されている場合、物理アドレス３１０の１６の下位ビット（ＬＳｂ）（２１６＝６４Ｋ）が、大きいページに関する物理ページ・オフセット３２０を提供するために利用されることになる。大きいページの場合、物理アドレス３１０の２４のＭＳｂを利用して、所定の物理ページに関する所定の物理ページ数が指定されることになる。
【００３１】
次に、仮想アドレス３４０に参照すると、仮想アドレス３４０は、物理アドレス３１０の分割と同様のやり方で、仮想ページ・オフセット３５０及び仮想ページ数３６０に分割されることが分かる。仮想アドレス３４０は、多くの異なるページ・サイズによってマッピングすることが可能であるが、所定の仮想アドレスに関するページ・サイズの選択が済むと、所定の仮想アドレスは、いつでも、１つのページ・サイズだけでマッピングすることが可能になる。所定のページ・サイズに関して、仮想ページ・オフセット３５０は、対応する物理ページ・オフセット３２０と等しくなる。仮想メモリ技法は、一般に、大きい仮想アドレス空間から小さい物理アドレス空間へのマッピングに利用されるので、所定のページ・サイズに関して、通常は、物理ページよりも仮想ページのほうが多くなる。
【００３２】
実施例では、仮想アドレス３４０は２６４のサイズの仮想アドレス・スペースを表す６４ビットの２進数である。サイズが８ＫＢの小ページが用いられる場合は、仮想ページ・オフセット３５０は仮想アドレス３４０の１３のＬＳｂとなり、仮想ページ数３６０は仮想アドレス３４０の５１のＭＳｂとなる。同様にして、サイズが６４ＫＢの大ページが用いられる場合は、仮想ページ・オフセット３５０は仮想アドレス３４０の１６のＬＳｂとなり、仮想ページ数３６０は、仮想アドレス３４０の４８のＭＳｂとなる。以後の詳細な説明では、別途の注記がなされていない限り、物理アドレス・スペースが４０ビットであり、仮想アドレス・スペースが６４ビットであり、大小のページ・サイズがそれぞれ６４ＫＢと８ＫＢである実施例を説明する。別の実施例では、仮想アドレスと物理アドレス、及び大小のページについて異なるサイズのものを用いることができる。更に、別の実施例では、２つ以上のサイズを用いることができる。その他に、更に別の実施例では、仮想アドレス・スペースよりも物理アドレスのスペースの方が大きい。
【００３３】
一実施例では、図５を参照して後述する方法で、仮想アドレス３４０のＭ＋Ｎの最下位ビットからＭの上位ビットを抜き出すことによってハッシュ・リスト・インデックスが作成される。その後、ハッシュ・リスト・インデックスは、仮想アドレス３４０を対応する物理アドレス３１０に変換する場合に、ハッシュ・テーブルにインデックス付けするために使用される。
【００３４】
ここで図４を参照すると、サイズが異なる３つのページの、メモリの一つの連続部分へのマッピングが示されている。図４では、大ページ４１２は物理メモリの連続部分をマッピングする。大ページ４１２は一連の行から成っているものとみなすことができ、ページの各行は大ページ４１２の“上部”からのオフセットによって特定することができる。このような場合、大ページ・オフセット４１０は、ページ内の個々の行を特定するために用いられるフィールドである。すなわち、例えば、大ページ４１２が１６Ｋの行から成っているものとすると、大ページ・オフセット４１０は１４ビットのフィールド（２１４＝１６Ｋ）となろう。
【００３５】
あるいは、大ページ４１２によってマッピングされたメモリの同一部分を、２つの中間サイズのページによってマッピングすることも可能であり、その場合、各々の中間サイズのページは大ページ４１２の半分のサイズである。これは中間ページ０  ４２２と、中間ページ１  ４２４によって示されている。そこで、大ページ・オフセット４１０の残りの下位ビットが、参照中の特定の中間サイズ・ページに中間ページ・オフセット４２０を付与する。このように、中間ページ・オフセット４２０が０の値を有し、中間ページ選択ビット４２６も０の値を有する場合は、中間ページ０  ４２２の最初の行がアドレス指定されることになる。これを大ページ４１２及び大ページ・オフセット４１０と比較すると、このような場合に大ページ４１２の最小の行も特定されることが理解されよう。
【００３６】
一方、中間ページ・オフセット・フィールドに１が記入され、中間ページ選択ビットフィールド４２６にも１が記入されている場合は、中間ページ１  ４２４の最後の行が、アドレス指定されているメモリの行となろう。ページ・オフセットが全ての１を含む大ページ・オフセット４１０であるとみなされる場合、これは大ページ４１２の最終行と対応する。
【００３７】
従って、大ページ４１２が１６Ｋ行のメモリをマッピングする実施例の場合、中間ページ０  ４２２は大ページ４１２のメモリの最初の８Ｋの行をマッピングし、中間ページ１  ４２４が大ページ４１２の最後の８Ｋの行をマッピングする。大ページ・オフセット４１０は依然として１４ビットのフィールドである。中間ページ・オフセット４２０、及び対応する中間ページ選択ビット４２６とみなした場合、大ページ・オフセット４１０の上位ビットは、中間ページ０  ４２２、又は中間ページ１  ４２４のいずれがアドレス指定されているかを特定する。そこで、大ページ・オフセット４１０の１３の下位ビット（２１３＝８Ｋ）は選択ビット４２６によって特定された中間ページの中間ページ・オフセット４２０を付与することになる。
【００３８】
同様にして、大ページ４１２は４つの小サイズのページに分割されるものとみることができる。このことは、小ページ０  ４３２、小ページ１  ４３４、小ページ２  ４３６及び小ページ３  ４３８によって示されている。このような場合、大ページ・オフセット４１０は小ページ選択ビット４４０と、小ページ・オフセット４３０に分割されるものとみなすことができる。大ページ・オフセット４１０が１６ＫＢのページを特定する１４ビットのフィールドである例を引き続き検討すると、大ページを４分割することによって、各々が４ＫＢのサイズの４つの小ページが作成される。この例では、大ページ・オフセット４１０の２つの上位ビット（２２  ＝４）によって小ページ選択ビット４４０が得られ、大ページ・オフセット４１０の１２の下位ビット（２１２＝４Ｋ）によって、小ページ選択ビット４４０により特定された小ページに小ページ・オフセット４３０が付与される。
【００３９】
図４には示していないが、メモリの特定の連続部分内で異なるサイズのページを組み合わせることも可能である。すなわち、上記とは異なり、大ページ４１２が一つの中間ページと、２つの小ページに分割されるものとみなすことができる。従って、例えば、大ページ４１２の最初の半分を、中間ページ０  ４２２によってマッピングし、大ページ４１２の後の半分を、小ページ２  ４３６と、小ページ３  ４３８によってマッピングすることができる。
【００４０】
図４の例はメモリの連続部分への、ページサイズ毎の３つのマッピングを示しているが、特定のメモリ部分にそれ以上、又はそれ以下のページ・サイズをマッピングすることが可能である。更に、各ページが２の整数乗である行数から成っている限り、より小さいページのマッピングはより大きいページのマッピングに常に適合する。例えば、別の実施例では、２つのページ・サイズだけがマッピングされる。この別の実施例では、小ページのサイズは８ＫＢであり、大ページのサイズは６４ＫＢである。
【００４１】
仮想メモリ・コンピュータ・システムは１つ以上のハードウェア・ページのサイズを有することができる。コンピュータ・システムが一つ、又は一つ以上のハードウェア・ページのサイズのいずれを有するにせよ、コンピュータ・システムは最小限のハードウェア・ページのサイズを有している。オペレーティング・システムは最小限のハードウェア・ページ・サイズと少なくとも同じサイズのページを用いる。オペレーティング・システムがハードウェア・ページ・サイズよりも大きいサイズの単数又は複数のページ・サイズを用いる場合、これらのページは充分な数の連続する同サイズのハードウェア・ページを互いに結合することによって構成され、必要なオペレーティング・システムのページ・サイズが作成される。オペレーティング・システムのページは代表的には、２の整数乗と、ハードウェア・ページ・サイズのサイズとの積である。このように、例えば、物理メモリは、コンピュータ・システムによって４ＫＢのサイズのハードウェア・ページへと分割されることができる。ハードウェア・ページ・サイズで全ての仮想メモリ動作を実行するのではなく、仮想メモリのオペレーティング・システムは、ページをメモリに転送する際に実際に使用されるより大きいページを有することができる。このように、実施例では、ハードウェア・ページのサイズが４ＫＢである場合でも、仮想メモリのオペレーティング・システムはサイズが８ＫＢと６４ＫＢのページでの動作を実行可能である。このような場合、各々の８ＫＢのオペレーティング・システムのページは、２つの連続するハードウェア・ページから成っており、各々の６４ＫＢのオペレーティング・システムのページは、１６の連続するハードウェア・ページから成っている。このような実施例では、ハードウェア・サイズが４ＫＢの１６の連続するページを、オペレーティング・システムの８ＫＢの８つの小ページ、又はオペレーティング・システムの６４ＫＢの一つの大ページであるとみなすことができる。
【００４２】
ここで図５を参照すると、仮想アドレスから物理アドレスへの変換を可能にする機構が図示されている。図５の同じ機構を、物理アドレスから仮想アドレスへの変換にも使用できる。一つ以上の仮想アドレスを所定の物理アドレスにマッピングできる場合は、図５の機構を、所定の物理アドレスの全ての別名の仮想アドレスを決定するために使用できる。更に、図５の機構によって、同時に一つ以上のページ・サイズについて、物理アドレスを仮想アドレス・マッピングへとマップすることができる。その上、図５の機構によって、一つ以上のページ・サイズを用いて物理メモリの特定の連続部分を同時にマッピングすることができる。
【００４３】
説明を容易にするため、別途指摘されない限り、図５の説明では一貫して主要な実施例を参照する。一実施例では、２つのハードウェア・ページ・サイズがあり、それは８ＫＢと６４ＫＢである。オペレーティング・システムのページ・サイズも２つあり、オペレーティング・システムの小さいページ・サイズは、小さいハードウェア・ページ・サイズ（すなわち８ＫＢ）と等しく、オペレーティング・システムの大きいページ・サイズは、大きいハードウェア・ページ・サイズ（すなわち６４ＫＢ）と等しい。
【００４４】
図５では、ＰＦＤ５１０、５１２及び５１４は、情報のオペレーティング・システム・ページ（ページ・フレーム）を記憶するために使用されている物理メモリ内の特定の連続領域を記述するために、仮想メモリのオペレーティング・システムによって作成される各々のページ・フレーム記述子である。ページ・フレーム記述子は、それが記述するページ・フレーム用の物理アドレス・ベースを特定するフィールドを有している。このフィールドは記述されるページ・フレームを記憶するために使用される物理メモリ内の連続領域の始点での物理アドレスを含んでいる。ページ・フレーム記述子は更に、ページ・フレームの物理アドレス範囲を特定するフィールドを有している。ページ・フレーム記述子内の変換ポインタ・フィールドは、少なくとも一つの仮想アドレス変換が存在する場合、所定のページフレームについて第１の仮想アドレス変換を指示する変換ポインタを含んでいる。特定のページ・フレーム記述子に対応する仮想アドレスが存在しない場合は、変換ポインタはその旨を指示する。このような事態は、例えば、ページ・フレーム記述子が、そこにロードされるべきデータを未だ有している空いたメモリを記述する場合、又は、ページ・フレーム記述子が、そこにロードされたデータを有するが、起動中のプロセスが目下のところデータを使用していないページ・フレームを記述する場合に生ずる。
【００４５】
ここでブロック５４０、５４２、５４４及び５４６を参照すると、各々のブロックは仮想メモリを物理スペースへマッピングするための変換ブロックである。従って、各ブロックは仮想アドレス・スペースの連続部分を表す。ブロック内で、仮想アドレス・スペースの連続部分は、一つの大ページ、又は幾つかのより小さいページとしてマッピングされる。各変換ブロックは関連するハッシュ・インデックスを有している。各変換ブロックはヘッダと、変換エントリの配列とに分割されている。主要な実施例では、大ページを表す変換ブロックは一つの変換エントリだけを有し、一方、小ページを表す変換ブロックは、複数の、例えば８つの変換エントリを有する。従って、主要な実施例では、小ページに対応する変換ブロックには、大ページに対応する変換ブロックよりも多くの記憶スペースが割当てられる。何故ならば、小ページの変換ブロックは大ページの変換ブロックよりも多くの変換エントリを有しているからである。
【００４６】
変換ブロックのヘッダは、変換ブロックによってマップされる仮想アドレス・スペースの連続部分全体に関する情報を含んでいる。これには、マップされるメモリ部分の基底仮想アドレスや、ブロック内の変換エントリの数や、有効な変換エントリの数や、ブロック内の全ての変換エントリのページ・サイズや、ブロック内の全ての変換エントリに共通のその他の属性等のような情報が含まれる。一つ以上の変換ブロックが同じハッシュ・インデックスと関連する場合は、ヘッダには特定のハッシュ・インデックスと関連する次の変換ブロックへのポインタが含まれる。
【００４７】
各々の変換エントリは有効ビット、変換エントリが利用するページのサイズを示すページ・サイズ・インジケータ、逆方向ポインタ及び変換エントリに対応するハードウェア・ページに特有の属性から成っている。逆方向ポインタはページ・フレーム記述子を示す。
【００４８】
同じ実施例で、各々の仮想アドレスは、仮想アドレスを使用している文脈を特定する関連する文脈数を有する。文脈数は変換ブロックによってマップされる仮想アドレスの全てに共通であるので、この文脈数は変換ブロックのヘッダに記憶されることができる。文脈数が用いられる場合は、仮想アドレス変換は、変換ブロックのヘッダに記憶された文脈数が、変換されるべき仮想アドレスに関連する文脈と一致した場合だけ有効である。この説明のため、文脈数は仮想アドレスの一部であるものと考えることができる。
【００４９】
従って、エイリアスが可能ではない場合、特定の物理アドレス用に仮想アドレスが存在するならば、特定の物理アドレスを含むページ・フレームを記述するページ・フレーム記述子は、変換ブロック内の変換エントリへのポインタを含む変換ポインタ・フィールドを有する。一方、変換ポインタによって指示される変換エントリ内の逆方向ポインタは、ページ・フレーム記述子を指示する。
【００５０】
この構造によって、変換が存在する場合、特定の物理アドレス用の所定の仮想アドレスが得られる。この変換は、変換される物理アドレスを含むページ・フレームを記述するページ・フレーム記述子が検知されるまで、ページ・フレーム記述子を検索することによって行われる。この動作が行われる理由は、全てのページ・フレーム記述子が物理アドレスの基底フィールドと範囲フィールドを有しているからである。フレーム記述子を有効に探索するには幾つかの公知の技術がある。これらの技術は公知であるので、ここでは詳細には説明しないが、代表的には、いくつかの種類のルックアップ・テーブル・データ構造を実施することが含まれる。
【００５１】
変換されるべき物理アドレスを含むページ・フレームに対応するページ・フレーム記述子が一旦識別されると、ページ・フレーム記述子の変換ポインタが点検される。変換ポインタが、変換されるべき物理アドレスに対応する仮想アドレスがないことを指示した場合は、変換プロセスは（変換されるべきアドレスがないので）変換を行わずに終了する。そうではない場合は、変換ブロック内の対応する変換エントリを検知するために、ページ・フレーム記述子の変換ポインタが用いられる。次に、変換されるべき物理アドレスに対応する仮想アドレスを計算するのに利用される情報を導出するため、ブロックのヘッダをアクセスするのにヘッダインジケータが利用される。例えば、主要な実施例では、ヘッダは、変換ブロックが一つの大ページを記述し、一つの変換エントリだけを有することを指示し、且つ、変換ブロック用の基底仮想アドレスを供給する。変換されるべき物理アドレス用のページ・オフセットは、変換されるべき物理アドレスの適宜のＬＳｂ数を抜き出すことによって検知することができる。抜き出されるビット数は変換エントリ用のページ・サイズによって左右される。ページ・オフセットを変換ブロックヘッダ内に記憶された仮想基底アドレスに付加すると、変換される物理アドレスに対応する仮想アドレスが得られる。
【００５２】
変換ブロックが一つ以上の変換エントリを有する場合は、変換の計算はやや複雑になる。変換ブロック内の変換エントリの位置を計算するために、変換のヘッダインジケータを利用することができる。例えば、ヘッダインジケータはブロックヘッダの始端へのポインタとして利用できる。変換エントリのメモリ・アドレスが判明しており、ヘッダと各変換エントリのサイズも判明しているので、変換ブロック内の変換エントリの位置を計算することができる。あるいは、ヘッダインジケータは、変換ブロック内の変換エントリの位置を指示する数であることができ、その場合は、ヘッダと各変換エントリのサイズが判明しているので、ヘッダの始端のメモリ・アドレスを計算することができる。変換されるべき物理アドレス用のページ・オフセットは上記のように計算することができる。しかし、この時点で、変換エントリ数から１が減算され、その差が、単一の変換エントリでマップされたメモリのサイズと乗算される。次に積がページ・オフセットに加算され、次に、その和が変換ブロックヘッダに記憶された仮想基底アドレスに加算されて、変換されるべき物理アドレスに対応する仮想アドレスが算出される。
【００５３】
更に、エイリアスが可能である場合は、変換エントリは別の変換ブロック（又は同じ変換ブロック）内の変換エントリに指示することができる順方向ポインタを有する。順方向ポインタによって指示された変換エントリは、記述される物理ページ用の別名に対応する。このように、特定のページ・フレームが変換エントリの連鎖を指示する。連鎖内の各変換エントリは、変換されるべき物理アドレス用の一つの別名を記述する。この連鎖構造によって、所定の物理アドレスに関して全ての仮想アドレスの検索が可能になる。
【００５４】
物理アドレスから仮想アドレスへの変換方式が図５に、ＰＦＤ５１０で開始される連鎖で示されている。このように、ページ・フレーム記述子５１０によって記述されるページ内に、変換されるべき物理アドレスがあるものと想定すると、ＰＦＤ５１０内のページ・フレーム・ポインタは、矢印５２０で示したように、ブロック５４０の変換エントリＴＮ１を指示していることが判る。変換エントリＴＮ１は、変換されるべき物理アドレス用の第１の仮想アドレス変換を行う。更に、矢印５３０によって示されるように、ブロック５４０の変換エントリＴＮ１は、ブロック５４２の変換エントリＴＮ３を指示するポインタを有している。矢印５３０をたどると、ページ・フレーム記述子５１０内の物理アドレスをマップする第２の仮想アドレスが、ブロック５４２の変換エントリＴＮ３内に見い出される。第３の変換がある場合は、変換エントリＴＮ３内のポインタは、その変換を含む別のブロックを指示するであろう。しかし、この場合は、変換エントリＴＮ３から出る矢印はない。従って、変換連鎖（ＴＮ３）の終了が明らかになり、変換されるべき物理アドレスに対応する全てのエイリアスが検索されたことになる。
【００５５】
同様にして、ブロック５４０の変換エントリＴＮ２へ向かう矢印５２２をたどることによって、次にＴＮ２から、ブロック５４６の変換エントリＴＮ５への矢印５３２を辿ることによって、ＰＦＤ５１２内に含まれる物理アドレスの変換が可能である。第３の例として、ページ・フレーム記述子５１４内に含まれる物理アドレスは、ブロック５４４の変換エントリＴＮ４へ向かう矢印５２４をたどることによって、次にブロック５４６の変換エントリＴＮ６への矢印５３４をたどることによって変換可能である。
【００５６】
大ページを表すページ・フレーム記述子はそのマッピング・リスト上の、より小さいサイズのページのマッピングを有することができることに留意されたい。一実施例では、ページ・フレーム記述子は、異なるページ・サイズの各々のページ・サイズがページ・フレーム記述子によって表されるサイズ未満であるか、等しい限り、異なるページ・サイズのマッピングを有することができる。このような場合、各々の対応する変換エントリは同じページ・フレーム記述子を再指示するが、異なる変換エントリはページ・フレーム記述子内の異なる領域を再指示することができる。
【００５７】
更に、別の実施例では、ページ・フレーム記述子のページ・サイズよりも大きいページ・サイズのマッピングが特定のページ・フレーム記述子のマッピング・リストに存在することができる。この場合は、マッピングはマッピング・リスト内のページ・サイズを上昇せしめることによって記憶される。大きいマッピングは第１のページ・フレーム記述子だけを再指示し、変換プロセスはこの場合を処理するように修正される。
【００５８】
前述したように、図５の変換機構は、仮想アドレスを物理アドレスに変換するためにも利用できる。これはハッシュ・リスト５６０によって行われる。ハッシュ・リスト５６０はハッシュエントリ（ＨＥ０−Ｆ  ）から成っている。各ハッシュエントリは空であるか、又は変換ブロックを指示するポインタを含んでいる。
【００５９】
ハッシュ・リストは、充分に大きい数の変換ブロックを指定するのに充分な大きさのものが選択される。図５の例では、ハッシュ・リスト５６０は１６のエントリを有しており、従って、ハッシュ・リストへのインデックスは４ビット（２４  ＝１６）によって指定されることになる。ほとんどの実施例で、より大きいハッシュ・リストが使用される。しかし、この例では、説明を簡単にするために１６のエントリを有するハッシュ・リストが使用される。主要な実施例では、変換ブロックは、一つのエントリを有する大ページ変換ブロックであれ、８つのエントリを有する小ページ変換ブロックであれ、６４ＫＢをマップする。６４ＫＢは１６ビットの２進数（２１６＝６４Ｋ）によって表すことができるので、ハッシュ・インデックスは、変換されるべき仮想アドレスの２０の（すなわち１６プラス４の）下位ビットから、４つの上位ビットを抜き出すことによって、変換されるべき仮想アドレスから作成されることになる。このように、図３を簡単に参照すると、一実施例では、Ｎは１６に等しく、Ｍは４に等しいことが理解されよう。
【００６０】
図５を再び参照すると、ハッシュ・インデックスは空である場合も、空でない場合もあるハッシュ・エントリを含むハッシュ・リスト内にインデックス付けする。ハッシュ・エントリのポインタが空である場合は、変換されるべき仮想アドレスに対応する物理アドレスはない。そこで第１の変換ブロックが点検され、変換されるべき仮想アドレスが第１の変換ブロック内に含まれているか否かが判定される。変換ブロックの範囲は、（ヘッダ内に記憶された）基底仮想アドレスで始まり、変換ブロックのエントリの最大数と、ブロック内の個々の変換エントリによって記述されるメモリのサイズとの乗算した値だけ継続する。変換されるべき仮想アドレスがこの範囲内にある場合は、変換されるべき仮想アドレスを含むとみられる第１の変換ブロックの変換エントリが点検されて、それが有効な変換エントリであるか否かが判定される。それが有効な変換エントリではない場合は、変換は存在しない。しかし、変換エントリが有効である場合は、変換されるべき仮想アドレス用の物理アドレスは、第１変換ブロックのヘッダ、変換エントリ及び変換エントリの逆方向ポインタによって指示されるページ・フレーム・エントリに含まれる情報から計算することができ、仮想アドレスから物理アドレスへの変換が達成されていることになる。
【００６１】
一方、第１変換ブロック（すなわちハッシュ・リスト・エントリによって指示された変換ブロック）が変換されるべき仮想アドレスに対応しない場合は、第１変換ブロックのヘッダが点検されて、ヘッダが空のポインタを含んでいるか、又は別の変換ブロックへのポインタを含んでいるかが判定される。他方、ヘッダが第２の変換ブロックへのポインタを含んでいる場合は、第２の変換ブロックが点検されて、それが変換されるべき仮想アドレスに対応するか否かが判定される。このプロセスは、変換が達成され、有効ではない変換エントリ内で変換されるべき仮想アドレスを含む変換ブロックが検知され、又は、変換連鎖を出るまで反復される。
【００６２】
仮想アドレスから物理アドレスへの変換プロセスは、物理アドレスから仮想アドレスへの変換プロセスと相反形である。仮想アドレスを物理アドレスに変換する場合、変換ブロックと、変換されるべき仮想アドレスを含む仮想アドレス範囲を記述するブロック内の変換エントリとを検知するために、変換ブロックのヘッダの情報が利用される。変換エントリに対応するページ・フレーム記述子を位置決めするために、変換エントリの逆方向ポインタが利用される。そこで、ページ・フレームの物理基底アドレスを物理ページ・オフセットに加算することによって、物理アドレスが作成される。
【００６３】
仮想アドレスから物理アドレスへの変換プロセスが２つの例について図５に示されている。第１の例では、変換されるべき仮想アドレスから抜き出されたハッシュ・インデックスは、ハッシュ・リスト５６０のハッシュ・エントリＨＥ４  である。ＨＥ４  を点検することによって、（矢印５７２で示すように）ブロック５４０のヘッダ５５０が検知される。次に、変換ブロック５４０のヘッダ５５０が点検されて、変換ブロック５４０が変換中の仮想アドレスを含むアドレス・スペースに対応するか否かが判定される。対応せず、適宜の変換エントリが有効である場合は、変換が検知され、適宜の変換エントリからの逆方向ポインタを、変換されるべき仮想アドレスの物理アドレスを含むＰＦＤへと逆に指示することができる。対応しており、適宜の変換エントリが有効ではない場合は、変換は存在しない。このように、変換されるべき仮想アドレスが変換エントリＴＮ１と関連するアドレス・スペース内に含まれている場合は、逆方向ポインタ５２１がＰＦＤ５１０へと逆に指示しよう。一方、変換されるべき仮想アドレスが、変換エントリＴＮ２と関連するアドレス・スペース内に含まれている場合は、逆方向ポインタ５２３がＰＦＤ５１２へと逆に指示しよう。変換ブロック５５０が、変換中の仮想アドレスを含むアドレス・スペースと対応しない場合は、ヘッダ５５０内のポインタは変換ブロック５４４へと指示する。変換ブロック５４４は同じハッシュ・インデックスを有する別の仮想アドレス・マッピングである。次に、この仮想アドレス・マッピングが点検されて、このマッピングが変換されるべき仮想アドレスを含むか否かが判定される。再度、含んでおり、適宜の変換エントリが有効である場合は、変換が検知されたことになる。含んでいるが、適宜の変換エントリが有効ではない場合は、変換は存在せず、逆方向ポインタ５２５はＴＮ４から逆にＰＦＤ５１４へと指示することができる。変換ブロック５４４が、変換される仮想アドレスを含むアドレス・スペースに対応しない場合は、ヘッダ５５４用のポインタが空であるので、検知されるべきその他の仮想アドレス・マッピングは存在せず、変換されるべき所定の仮想アドレスには変換は存在しない。
【００６４】
同様にして、変換されるべき第２の仮想アドレスから抜き出されたハッシュ・インデックスは、ハッシュ・リスト５６０のハッシュエントリＨＥｃ  である。ハッシュエントリＨＥｃ  は（矢印５７４に示すように）ヘッダ５５２を指示し、逆方向ポインタ５３１は変換エントリＴＮ３からＰＦＤ５１０を指示する。一方、ブロック５４２のヘッダ５５２は、（矢印５８４で示すように）ブロック５４６のヘッダ５５６へのポインタを含み、逆方向ポインタ５３３と５３５は、変換エントリＴＮ５及びＴＮ６から、ＰＦＤ５１２と５１４をそれぞれ指示する。図５では逆方向ポインタは常に変換エントリからＰＦＤへと指示するものの、別の実施例では、変換エントリＴＮ３のポインタ５３１のような逆方向ポインタは、ＴＮ１のような変換エントリを指示できることに留意されたい。このような場合、ＴＮ３からの逆方向ポインタはＴＮ１に指示し、次に、変換エントリＴＮ１の逆方向ポインタ５２１はＰＦＤ５１０を指示することになろう。
【００６５】
このように、図５に示した変換機構は２つの方法でアクセス可能なデータ構造を提示する。第１の方法では、ハッシュ・リストへのインデックスで開始することによって、データ構造をアクセスして、変換されるべき仮想アドレス用の物理アドレス変換を行うことができる。第２の方法では、ページ・フレーム記述子で開始することによって、データ構造をアクセスして、所定の物理アドレスに対応する全ての仮想アドレス変換を行うことができる。
【００６６】
一実施例では、変換ブロックは、仮想メモリのオペレーティング・システムによって用いられる全てのページ・サイズをマッピングするのに充分な大きさであるように選択された。このような場合、変換が存在する場合は、図５の変換機構は常に第１のハッシュで変換を行う。所定の変換ブロックによってマップされるメモリのサイズが、各変換ブロックが有効な変換エントリで密集するように選択され、又、最も普及したページ・サイズを変換ブロックでマッピングできる場合に、図５の変換機構は最も効率よく動作する。別の実施例では、多重のハッシュ機能が用いられる。このように、例えば、小ページ変換ブロックだけが、（８つではなく）４つの変換エントリを有するように一実施例を変更したものと想定してみる。この別の実施例では、小ページ変換ブロックは３２ＫＢの仮想アドレス・スペースをマップすることができ、大ページ・アドレス・ブロックは依然として６４ＫＢのアドレス・スペースをマップするであろう。このように、大ページ変換ブロックのアドレス・スペースは依然として１６ビット２進数で表現されるものの、小ページ変換ブロックのアドレス・スペースは１６ビット２進数で表現されよう。この別の実施例では、仮想アドレスから物理アドレスに変換する場合、２つのハッシュ・インデックスと変換連鎖が横移動されなければならないことがある。第１のハッシュ・インデックスは、仮想アドレスがより小さいページ・サイズに対応するものと想定することによって、変換されるべき仮想アドレスから抜き出される。従って、４ビットのハッシュ・インデックスがある図５の例では、第１のハッシュ・インデックスは、変換されるべき仮想アドレスの１９の下位ビットから、４つの上位ビットを抜き出すことによって作成されることになる。次に、第１ハッシュ・インデックスのハッシュエントリで開始される変換連鎖が点検される。アドレス・スペースの一部として、変換されるべき仮想アドレスを含む変換ブロックが連鎖内で検知されない場合は、変換されるべき仮想アドレスが大ページ・サイズに対応するものと想定することによって、変換されるべき仮想アドレスから第２のハッシュ・インデックスが抜き出される。このように、４ビットのハッシュ・インデックスがある図５の例を継続して参照すると、第２のハッシュ・インデックスは、変換されるべき仮想アドレスの２０の下位ビットから４つの上位ビットを抜き出すことによって作成されることになる。第２のハッシュ・インデックスは第２変換連鎖の基底で第２のハッシュエントリを提供する。このようにして、各ハッシュ・リストに対応する変換ブロックを密集状態に保つことができる。それによって、変換ブロック構造を保持するのに必要なメモリの容量は最小限にされる。
【００６７】
別の実施例では、ハードウェアのページ・サイズは一つしかない。（小ページ・サイズ）ハードウェアのページ・サイズが一つの実施例では、小ページ変換ブロックの個々の変換エントリを用いる場合、変換エントリは物理メモリのハードウェア・ページ・サイズ部分に対応する。大ページ変換ブロックの個々の変換エントリを用いる場合、変換エントリは物理メモリの８つの連続するページ・サイズ部分に対応する。（８つのハードウェア・サイズ・ページ×ハードウェア・サイズ・ページ当たりの８ＫＢは、６４ＫＢ、すなわち一つの大サイズのオペレーティング・システムのページに等しい。）次に、オペレーティング・システムは変換エントリを必要に応じて複数の変換エントリへと拡張することができる。
【００６８】
一実施例では、各ハードウェア・ページ・サイズは対応するオペレーティング・システムのページ・サイズと同サイズであるものの、この限定性は保持する必要がないことに留意されたい。従って、例えば、別の実施例では、最小限のハードウェア・ページ・サイズは４ＫＢであり、一方、オペレーティング・システムの小ページ・サイズは８ＫＢでもよいであろう。このような場合は、２つのアプローチが可能であろう。第１のアプローチでは、小ページ変換ブロック内の各変換エントリは最小限のサイズのハードウェア・ページに対応し、オペレーティング・システムの小ページを記述するために２つの変換エントリが利用されることになる。第２のアプローチでは、オペレーティング・システムの各々の小ページ用に、小ページ変換ブロック内には変換エントリは一つしかなく、その場合、仮想アドレスが物理アドレスに変換中に、オペレーティング・システムは小ページ変換ブロックエントリを必要に応じた適宜の数の変換エントリへと拡張することになる。
【００６９】
同様にして、ハードウェア・ページに複数のサイズがあり、オペレーティング・ページの大ページ・サイズがハードウェアの大ページ・サイズの倍数である場合同じ問題が生ずる。従って、例えば２つのハードウェア・ページ・サイズ（８ＫＢと３２ＫＢ）があるように、一実施例を変更することが可能である。子の場合は、オペレーティング・システムの大（６４ＫＢ）ページ・サイズが大きい変換ブロックによって表現された場合、第１のアプローチが採用されると、大ページ変換ブロックは２つの変換エントリを有することになる。（３２ＫＢのハードウェア・ページ毎に一つ）第２のアプローチが採用される場合は、大ページ変換ブロックは一つの変換エントリだけを有し、変換エントリは、仮想アドレスが物理アドレスに変換中に必要に応じて２つの変換エントリに拡張されよう。
【００７０】
一般に、変換ブロックが（変換エントリによってマップされたアドレス・スペースのサイズと、変換ブロック内の変換エントリの最大数との積に等しい）アドレス・スペースのＮビットのアドレス可能なセクションをマップし、更に、ハッシュ・リスト・インデックスがＭビット数によって特定される場合、変換されるべき仮想アドレス用のハッシュ・リストへのインデックスは、（図３に示すように）変換されるべき仮想アドレスのＮの下位ビットの上位に現れるＭの下位ビットを抜き出すことによって作成される。別の実施例ではハッシュ・インデックスの別の計算方法を利用できる。すなわち、別の実施例では例えば、ハッシュ・インデックス情報は仮想アドレスと、仮想アドレスを用いている文脈を識別する文脈数との関数である。
【００７１】
更に別の実施例では、大ページをマップする変換ブロックは一つ以上の有効な変換エントリを有することができる。このような場合、仮想アドレスを可能性として２つの位置で表現でき（ページ・サイズ毎に一箇所）、一つの一だけが変換を行う。常に最小のページに対応するインデックスで先ず開始することによって、各ページ・サイズ毎に異なるハッシュ・インデックスが計算される場合は常に、変換されるべき仮想アドレスを含む変換ブロックが最初に検知され、この変換ブロックが検知されると探索は終結する。一方、一つ以上のページ・サイズについて同一であるハッシュ・インデックスについて連鎖の横移動が行われ、ハッシュ・インデックスの最小サイズのページに対応しない有効ではない変換エントリを含む変換ブロックが検知された場合、探索が終了する前に、連鎖の残り部分を照合して、連鎖がより小さいページ・サイズの変換ブロックを含んでいるか否かを判定しなければならない。
【００７２】
ここで図６を参照すると、図５の機構を利用した仮想アドレスから物理アドレスへの変換を図示した流れ図が示されている。図６では、仮想アドレスから物理アドレスへの変換手順６００は開始バブル６１０から始まり、変換されるべき仮想アドレスからハッシュ・インデックスが計算される処理ブロック６２０へと進む。判断ブロック６３０で、ハッシュ・リストが点検され、変換されるべき仮想アドレスから計算されたハッシュ・インデックスに対応するハッシュエントリが第１変換ブロックを指示しているか、又は、それが空であるかの判定が行われる。ハッシュ・リストが空である場合は、判断経路６３２は手順ブロック６７０をたどり、そこでは手順が端末バブル６９０で終了する前に、変換が存在しない状態が宣言される。複数のハッシュ・インデックスがある場合には、次のハッシュ・インデックスが計算され、手順は終了するのではなく判断ブロック６３０へと続くことに留意されたい。
【００７３】
再度判断ブロック６３０を参照すると、ハッシュ・リストが空ではない場合、判断経路６３４は手順ブロック６４０へと進み、そこでハッシュエントリによって指示された変換ブロックが点検される。次に、判断ブロック６５０で、変換ブロックが変換されるべき仮想アドレスを含んでいるか否かが判定される。変換が有効ではない場合、判断経路６５６は手順ブロック６７０に進み、そこで変換が存在しない状態が宣言される。複数のハッシュ・インデックスがある場合、次のハッシュ・インデックスが計算され、手順は終了するのではなく、判断ブロック６３０に続くことに再度留意されたい。さらに、一つ以上のページ・サイズについて同一であるハッシュ・インデックスのために連鎖が横移動され、又、ハッシュ・インデックスの最小サイズのページに対応しない有効ではない変換エントリを含む変換ブロックが検知された場合、探索が終了する前に、連鎖の残り部分を照合して、連鎖がより小さいページ・サイズの変換ブロックを含んでいるか否かを判定しなければならないことに留意されたい。
【００７４】
一方、判断ブロック６５５で変換が有効であることが判明すると、判断経路６５８はブロック６８０に進み、そこで変換の検知状態が宣言される。次に、手順が端末バブル６９０で終了する前に、物理アドレス変換が計算される。
【００７５】
再度判断ブロック６５０を参照すると、点検される変換ブロックが、変換されるべき仮想アドレスを含んでいない場合、判断経路６５４は判断ブロック６６０に進み、そこで、点検される変換ブロックが変換ブロック・リストの最後のブロックであるか否かを判定する検査が行われる。点検される変換ブロックのヘッダ内のポインタが空である場合、同じハッシュ・インデックスを有する、点検されるべき他の変換ブロックは存在せず、判断経路６６４は手順ブロック６７０に進む。その場合は、端末バブル６９０で手順が終了する前に、変換が存在しない状態が宣言される。複数のハッシュ・インデックスがある場合、次のハッシュ・インデックスが計算され、手順は終了するのではなく、判断ブロック６３０に続くことに再度留意されたい。
【００７６】
一方、判断ブロック６６０で変換ブロック・リストが点検される際に、点検される変換ブロックのヘッダ内のポインタが、別の変換ブロックを指示していることが判明すると、判断経路６６２は手順ブロック６４０に進み、そこで、指示されている変換ブロックが点検される。このようにして、変換連鎖の点検は、変換されるべき仮想アドレスを含む変換ブロッンクが検知されるまで、又は、連鎖の最後のリンクの点検が終了するまで継続される。
【００７７】
ここで図７を参照すると、物理アドレスから仮想アドレスへの変換を示した流れ図が図示されている。図７では、物理アドレスから仮想アドレスへの変換手順７００は、開始バブル７１０で始まり、変換されるべき物理アドレスを含むページ・フレームを記述するページ・フレーム記述子が存在するか否かを判定する検査が行われる判断ブロック７１５に進む。判断ブロック７１５で、このようなページ・フレーム記述子が存在しないことが判定されると、判断経路７１６は端末バブル７６０に進み、そこで（変換が行われるべきアドレスが存在しないので）変換が行われずに終了する。
【００７８】
一方、判断ブロック７１５で、変換されるべき物理アドレスを含むページ・フレームを記述するページ・フレーム記述子が存在することが判定されると、判断経路７１８は手順ブロック７２０に進み、そこで、変換されるべき物理アドレスを含むページ・フレームを記述するページ・フレーム記述子が点検されて、それがマッピング・リスト内に第１変換ブロックへのポインタを含んでいるか否かが判定される。判断ブロック７３０で、変換されるべき物理アドレスを含むページ・フレーム記述子内のポインタが空であることが判定されると、変換は存在せず、判断経路７３２は端末バブル７６０に進み、そこで再び、手順は（変換が行われるべきアドレスが存在しないので）変換が行われずに終了する。
【００７９】
再度判断ブロック７３０を参照すると、ページ・フレーム記述子のマッピング・リストが空ではない場合には、第１変換ブロック内の変換エントリを判定するために、ページ・フレーム記述子内の変換ポインタが用いられる。このような場合は、判断経路７３４は処理ブロック７４０に進み、そこで、実際に仮想アドレスが必要ならば、変換エントリに対応する仮想アドレスが計算される。そうではない場合は、例えば、変換ブロック内の属性が点検、又は変更される。次に、判断ブロック７５０で、点検中の変換ブロックの変換エントリが点検されて、その順方向ポインタが空であるか否かが判定される。順方向ポインタが空である場合は、変換されるべき物理アドレスに対応する全ての仮想アドレスが識別されたことになり、判断経路７５４は端末バブル７６０に進み、そこで手順は終了する。
【００８０】
一方、判断ブロック７５０で、点検される変換ブロックの変換エントリの順方向ポインタが別の（又は同じ）変換ブロック内の別の変換エントリを指示しているものと判定された場合は、判断経路７５２は手順７４０に進む。手順ブロック７４０では、変換リスト内の次の変換エントリが点検され、物理アドレス用の仮想アドレスの別名が提供される。
【００８１】
変換プロセスは変換連鎖内の最後のリンクが検知され、変換手順が端末バブル７６０で終了するまで継続される。
【００８２】
これまで本発明の方法と装置を現段階で好適な実施例、及び別の実施例に関連して説明してきたが、本発明は添付の特許請求項の趣旨と範囲内で修正と変更が可能であることが、専門家には理解されよう。従って、本明細書と図面は、限定的なものではなく、説明目的であるとみなされるべきものである。
【図面の簡単な説明】
【図１】本発明の実施例を利用して、アドレス変換を実施するコンピュータ・システムを示す図である。
【図２】仮想アドレスを物理アドレスに変換するためのマルチ・レベル・アプローチを示す図である。
【図３】物理アドレスと仮想アドレスとの関係、及び、仮想アドレスからハッシュ・インデックスを導き出す方法を示す図である。
【図４】物理メモリの連続部分に対する複数ページ・サイズのマッピングを示す図である。
【図５】アドレス変換メカニズムの実施例を示す図である。
【図６】図５の変換メカニズムを利用した、仮想アドレスから物理アドレスへの変換を表したフロー・チャートである。
【図７】図５の変換メカニズムを利用した、物理アドレスから仮想アドレスへの変換を表したフロー・チャートである。
【符号の説明】
２２０…アドレス変換バッファ、２５０…二次変換機構、２８０…大型ソフトウエア変換テーブル、５６０…ハッシュ・リスト。
【図１】
0003577575.tif 000002
【図２】
0003577575.tif 000003
【図３】
0003577575.tif 000004
【図４】
0003577575.tif 000005
【図５】
0003577575.tif 000006
【図６】
0003577575.tif 000007
【図７】
0003577575.tif 000008