(57)【要約】【課題】非常に大きな仮想アドレス空間を使用する場合でも、ある程度の平均性能を確保したまま処理時間の最悪値を制限でき、効率的なアドレス変換を実現可能とする。【解決手段】ＭＭＵ３の領域登録部３１は、登録すべき仮想アドレス領域に対応するページ検索ツリー２２１を生成する。領域登録部３１はまた、仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応するエントリであって、当該仮想アドレス領域に対応する検索ツリー２２１へのポインタが設定可能なエントリを含むハッシュテーブル２２２を生成する。テーブル検索部３２は、例えば任意の仮想アドレスの物理アドレスへの変換が必要な場合、当該仮想アドレスが属する仮想アドレス領域に対応するハッシュテーブル２２２のエントリを検索して目的の検索ツリー２２１を特定することで、該当する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索する。【選択図】      図１
2006178764.tif 000002
【特許請求の範囲】
【請求項１】
仮想記憶方式のコンピュータシステムに適用されて、仮想アドレスから物理アドレスへのアドレス変換のためのアドレス変換情報を含み、仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を用いたメモリ管理を行うメモリ管理装置において、
前記コンピュータシステムで実際に使用される可能性のある仮想アドレスが属する、仮想アドレス空間内の領域である仮想アドレス領域に対応付けられる木構造データであって、当該仮想アドレス領域に含まれる仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索するのに用いられる木構造データを前記物理メモリ上に生成する木構造データ生成手段と、
前記仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応付けられるエントリであって、当該仮想アドレス領域に対応付けられた前記木構造データを指すポインタが設定可能なエントリを含むハッシュ構造データを前記物理メモリ上に生成するハッシュ構造データ生成手段と、
任意の仮想アドレスから当該仮想アドレスが属する仮想アドレス領域に対応付けられた前記ハッシュ構造データのエントリを検索することにより、当該仮想アドレス領域に対応付けられた前記木構造データを特定して、当該木構造データから当該仮想アドレスが属する仮想ページに割り当てられる前記物理メモリ上の物理ページに関するページ情報を検索する検索手段と
を具備することを特徴とするメモリ管理装置。
【請求項２】
前記ハッシュ構造データは、当該ハッシュ構造データに対応する仮想アドレス空間に属する仮想アドレスのハッシュ値に応じて複数のグループに分けて管理され、当該グループ毎にそれぞれ異なる仮想アドレス領域に対応付けることが可能な複数のエントリを有することを特徴とする請求項１記載のメモリ管理装置。
【請求項３】
前記ハッシュ構造データの前記グループ毎の前記異なる仮想アドレス領域に対応付けられた各エントリには、当該仮想アドレス領域に対応付けられた前記木構造データを指すポインタに加えて、当該仮想アドレス領域を指す仮想アドレス情報が設定可能であることを特徴とする請求項２記載のメモリ管理装置。
【請求項４】
前記ハッシュ構造データ生成手段は、前記ハッシュ構造データを生成した際に、当該ハッシュ構造データの全てのエントリに、当該エントリが無効であることを示す特定データを書き込むことを特徴とする請求項３記載のメモリ管理装置。
【請求項５】
外部からの仮想アドレス領域登録要求を受け付ける要求受付手段を更に具備し、
前記木構造データ生成手段は、前記要求受付手段によって前記仮想アドレス領域登録要求が受け付けられた場合に、当該仮想アドレス領域登録要求によって要求された仮想アドレス領域に対応する前記木構造データを前記物理メモリ上に生成し、
前記ハッシュ構造データ生成手段は、前記木構造データ生成手段によって前記木構造データが生成された場合に、当該生成された木構造データに対応する前記仮想アドレス領域に属する仮想アドレスに共通のハッシュ値で特定される、前記ハッシュ構造データのグループ内の複数のエントリから、無効エントリを１つ検索して、当該検索された無効エントリを、前記生成された木構造データを指すポインタ及び前記生成された木構造データに対応する前記仮想アドレス領域を指す仮想アドレス情報に書き換える
ことを特徴とする請求項４記載のメモリ管理装置。
【請求項６】
前記仮想アドレス空間の大きさ、登録すべき前記仮想アドレス領域の大きさ、前記ハッシュ構造データのグループ数、前記ハッシュ構造データのグループ内のエントリ数、前記ハッシュ値の計算に用いられるハッシュ計算式、及び前記木構造データの示す木構造の深さのうちの少なくとも１つを外部からの指定に応じて設定するための設定手段を更に具備することを特徴とする請求項２記載のメモリ管理装置。
【請求項７】
前記物理メモリの大きさ、前記ページの大きさ、前記仮想アドレス空間の大きさ、登録すべき前記仮想アドレス領域の大きさ、及び仮想アドレス空間毎の前記仮想アドレス領域の個数の最大値のうちの少なくとも１つの値に基づき、登録すべき前記仮想アドレス領域の大きさ、前記ハッシュ構造データのグループ数、前記ハッシュ構造データのグループ内のエントリ数、前記ハッシュ計算式、及び前記木構造データの示す木構造の深さのうちの当該少なくとも１つとは異なる種類の少なくとも１つを決定する構造決定手段を更に具備することを特徴とする請求項２記載のメモリ管理装置。
【請求項８】
前記構造決定手段は、前記物理メモリの大きさに応じ、当該物理メモリの大きさが大きいほど、登録すべき前記仮想アドレス領域の大きさを大きく決定すること、前記ハッシュ構造データのグループ数を多く決定すること、前記ハッシュ構造データのグループ内のエントリ数を少なく決定すること、及び前記木構造データの示す木構造の深さを浅く決定することのうちの少なくとも１つを実行することを特徴とする請求項７記載のメモリ管理装置。
【請求項９】
前記構造決定手段は、前記ページの大きさに応じ、当該ページの大きさが大きいほど、登録すべき前記仮想アドレス領域の大きさを大きく決定すること、前記ハッシュ構造データのグループ数を少なく決定すること、前記ハッシュ構造データのグループ内のエントリ数を少なく決定すること、及び前記木構造データの示す木構造の深さを浅く決定することのうちの少なくとも１つを実行することを特徴とする請求項７記載のメモリ管理装置。
【請求項１０】
前記構造決定手段は、前記仮想アドレス空間の大きさに応じ、当該仮想アドレス空間の大きさが大きいほど、登録すべき仮想アドレス領域の大きさを大きく決定すること、前記ハッシュ構造データのグループ数を少なく決定すること、前記ハッシュ構造データのグループ内のエントリ数を少なく決定すること、及び前記木構造データの示す木構造の深さを深く決定することのうちの少なくとも１つを実行することを特徴とする請求項７記載のメモリ管理装置。
【請求項１１】
前記構造決定手段は、前記登録すべき仮想アドレス領域の大きさに応じ、当該仮想アドレス領域の大きさが大きいほど、前記ハッシュ構造データのグループ数を少なく決定すること、前記ハッシュ構造データのグループ内のエントリ数を少なく決定すること、及び前記木構造データの示す木構造の深さを深く決定することのうちの少なくとも１つを実行することを特徴とする請求項７記載のメモリ管理装置。
【請求項１２】
前記構造決定手段は、前記仮想空間毎の仮想アドレス領域の個数の最大値に応じ、当該最大値が大きいほど、前記ハッシュ構造データのグループ数を多く決定すること、前記ハッシュ構造データのグループ内のエントリ数を多く決定すること、及び前記木構造データの示す木構造の深さを浅く決定することのうちの少なくとも１つを実行することを特徴とする請求項７記載のメモリ管理装置。
【請求項１３】
仮想記憶方式のコンピュータシステムにおいて、
前記コンピュータシステムで実際に使用される可能性のある仮想アドレスが属する、仮想アドレス空間内の領域である仮想アドレス領域に対応付けられる木構造データであって、当該仮想アドレス領域内の仮想アドレスから物理アドレスへのアドレス変換のためのアドレス変換情報を含み、当該仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索するのに用いられる木構造データを保持する木構造データ保持手段と、
前記仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応付けられるエントリであって、当該仮想アドレス領域に対応付けられた前記木構造データを指すポインタが設定可能なエントリを含むハッシュ構造データを保持するハッシュ構造データ保持手段と、
任意の仮想アドレスから当該仮想アドレスが属する仮想アドレス領域に対応付けられた前記ハッシュ構造データのエントリを検索することにより、当該仮想アドレス領域に対応付けられた前記木構造データを特定して、当該木構造データから当該仮想アドレスが属する仮想ページに割り当てられる前記物理メモリ上の物理ページに関するページ情報を検索する検索手段と
を具備することを特徴とするコンピュータシステム。
【請求項１４】
仮想記憶方式のコンピュータシステムに適用され、仮想アドレスから物理アドレスへのアドレス変換のためのアドレス変換情報及び仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を用いたメモリ管理を行うメモリ管理方法において、
前記コンピュータシステムで実際に使用すべき仮想アドレスが属する仮想アドレス空間内の領域を仮想アドレス領域として登録することを要求するための仮想アドレス領域要求を受け付けるステップと、
前記仮想アドレス領域登録要求が受け付けられた場合に、当該仮想アドレス領域登録要求によって要求された仮想アドレス領域に対応付けられる木構造データであって、当該仮想アドレス領域に含まれる仮想ページに割り当てられる前記物理メモリ上の物理ページに関するページ情報を検索するのに用いられる木構造データを前記物理メモリ上に生成するステップと、
前記仮想アドレス空間に属する仮想アドレスのハッシュ値に応じて複数のグループに分けて管理され、当該グループ毎にそれぞれ異なる仮想アドレス領域に対応付けることが可能な複数のエントリであって、初期状態では無効であることを示す特定データが書き込まれる複数のエントリを有するハッシュ構造データを前記物理メモリ上に生成するステップと、
前記木構造データが生成された場合に、当該生成された木構造データに対応する前記仮想アドレス領域に属する仮想アドレスに共通のハッシュ値で特定される、前記ハッシュ構造データのグループ内の複数のエントリから、無効エントリを１つ検索して、当該検索された無効エントリを、前記生成された木構造データを指すポインタ及び前記生成された木構造データに対応する前記仮想アドレス領域を指す仮想アドレス情報に書き換えるステップと、
任意の仮想アドレスが属する仮想ページに対応するページ情報の検索要求を受けて、前記任意の仮想アドレスのハッシュ値を算出するステップと、
前記算出されたハッシュ値で特定される、前記ハッシュ構造データのグループ内の複数のエントリから、前記任意の仮想アドレスに対応する仮想アドレス情報が保持されているエントリを検索することにより、当該検索されたエントリから前記任意の仮想アドレスが属する仮想アドレス領域に対応付けられた前記木構造データを指し示すポインタを取得するステップと、
前記取得されたポインタによって指し示される木構造データから前記任意の仮想アドレスが属する仮想ページに割り当てられる前記物理メモリ上の物理ページに関するページ情報を検索するステップと
を具備することを特徴とするメモリ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想ページに割り当てられる物理メモリ上の物理ページを管理するのに好適なメモリ管理装置、コンピュータシステム及びメモリ管理方法に関する。
【背景技術】
【０００２】
仮想記憶方式のコンピュータシステムに適用されるメモリ管理ユニット（Memory Management Unit : ＭＭＵ）は、従来から、仮想アドレスと物理アドレスとの間のアドレス変換やメモリ保護等を目的とした、メモリ管理のための装置または機能単位として知られている。
【０００３】
一般的にＭＭＵは、物理メモリをページと呼ばれるブロックごとに分割して、仮想アドレス空間に割り当て（マッピングし）、またマッピングされた仮想アドレスから物理アドレスを検索する機能を有する。これによりＭＭＵは、ソフトウェアから認識される仮想アドレス空間を実際の物理アドレス空間より大きく見せたり、個々のソフトウェアに別々の仮想的なアドレス空間を用意し、お互いが物理メモリ上で干渉しないようにする保護機能が実現できるなど、ソフトウェアに対して非常に便利な機能を提供できる。
【０００４】
一方、今日のプロセッサの多くは、仮想ページ（アドレス）を物理ページ（アドレス）に変換するための変換情報（ページ変換エントリ情報）を格納するキャッシュ（ページ変換エントリキャッシュ）を有している。プロセッサは、ソフトウェアが命令やデータを仮想ページで指定したときに、上記キャッシュを参照することにより当該仮想ページを物理ページに変換して、メモリにアクセスするキャッシュ機能を有する。もし、キャッシュに該当する変換情報（キャッシュ情報）が存在しないキャッシュミスの場合、プロセッサは、ＭＭＵにキャッシュ情報の追加または入れ替え要求を通知する。ＭＭＵは、プロセッサからの要求に応じて、主メモリ等に用意されたアドレス変換情報（ページ変換テーブルのエントリ情報）を検索して、該当する変換情報を当該プロセッサのキャッシュにロードするキャッシュ入れ替え機能を有する。なお、製品によってはキャッシュ機能を有するだけでＭＭＵと称するものも知られている。ここでは、ＭＭＵがキャッシュ入れ替え機能を有するものとし、キャッシュ機能はプロセッサの一部の機能として扱う。
【０００５】
ページ変換テーブルを持たない実装や、ページ変換テーブルが必ずしも全ての仮想ページ分の変換エントリを持つわけではない実装では、最終的にアドレス変換できない場合、つまり該当ページが主メモリに存在しないページフォルトの場合、ＭＭＵはソフトウェアにその旨を通知することにより、当該ソフトウェアに該当エントリを追加してもらう処理（いわゆるページフォルト処理）を行わせるのが一般的である。
【０００６】
当然ながら、ソフトウェアにページフォルトの処理をさせる頻度が低いほど、当該ソフトウェアの全体の処理性能はよくなる。また、ハードウェアでアドレス変換する場合の処理時間もできるだけ短い方が望ましい。この点だけを考慮すると、ページ変換テーブルに全ての仮想ページ分の変換エントリを持たせることが好ましい。しかし、全ての仮想ページ分の変換エントリ（変換情報）を、配列形式またはリスト形式などでメモリ上に単純に配置すると、非現実的な量の管理メモリ（管理メモリ領域）が必要になるか、或いはハードウェアのＭＭＵにとっても無視できないほどの検索時間がかかってしまう。
【０００７】
例えば、全ての仮想ページ分の変換エントリを単純な配列形式で持つ場合を考える。この場合、エントリの検索は、インデックス計算１回であるので高速に行えるものの、仮想アドレス空間の大きさに比例した容量の管理メモリ領域が必要となる。例えば、仮想アドレス空間のページ数が２64ページ、１ページのサイズ（ページサイズ）が２12バイト（Ｂ）、１エントリ（変換エントリ）のサイズが１６Ｂであるとすると、必要な管理メモリ領域のサイズは
１６Ｂ＊（２64／２12）＝２56Ｂ
となる。この場合、管理メモリ領域は、物理メモリに入りきらないほどの大きさが必要となってしまう。
【０００８】
一方、仮想アドレス空間内で実際に物理ページを使用する部分のアドレスだけを、単純なリスト構造（エントリをポインタでつなぐ形式）で管理する場合には、必要な管理メモリ領域の大きさの最大値は、使用する物理メモリの容量に比例する。この物理メモリの容量を２30Ｂ（＝１ＧＢ）とすると、必要な管理メモリ領域の大きさの最大値は、
１６Ｂ＊（２30／２12）＝２22Ｂ（＝４ＭＢ）
と、現実的な大きさとなる。しかし、リスト構造の場合、前述の配列形式と異なり、インデックス計算でエントリの位置を算出することはできない。この場合、アドレス変換のたびに、４ＭＢ／１６Ｂで示される個数のエントリ、即ち２５６Ｋ個のエントリの中から該当エントリを順次検索しなければならず、管理メモリ領域のアクセスのために多大な時間がかかってしまう。
【０００９】
このような問題を解決するための一般的な方法、つまり、アドレス変換時のメモリアクセス回数を減らし、管理メモリ領域も現実的な大きさに抑えることが可能な一般的な方法として、以下に詳述する２つの方法、（１）ツリー構造を用いた方法、及び、（２）ハッシュテーブルを用いた方法が知られている。
【００１０】
（１）ツリー構造
仮想アドレス空間のサイズとページサイズの間に中間層を有するツリー構造が用意される。根及び中間層の管理データは直下の層のサブツリーへのポインタの配列を保持し、葉の管理データはアドレス変換情報を含むページ情報を保持する。この構造では、ツリーの根から葉を辿ることによりアドレス変換が実行される。
【００１１】
ここで、物理メモリと対応しない仮想アドレス（つまり、未使用または不正な仮想アドレス）については、適当な中間層に、使用していない旨のデータ（たとえばＮＵＬＬポインタ）を保持する。このようなツリー構造を用いることで、物理メモリと対応しない仮想アドレスについて、葉の管理情報を保持する必要がなく、管理メモリ領域を現実的な大きさに抑えることができる。また、ツリー構造を用いたアドレス変換では、必要なメモリアクセス回数はツリーの深さに比例する。このため、最悪となる場合の処理時間（処理時間の最悪値）を確定できるメリットがある。
【００１２】
（２）ハッシュテーブル
仮想アドレスの各々に対して、適当に選ばれたハッシュ関数を用いてハッシュ演算が施される（例えば、特許文献１参照）。このハッシュ演算の結果（ハッシュ値）の各々に配列またはリスト（グループ）が対応付けられる。この配列またはリストは、複数個のページ情報を保持する。
【００１３】
アドレス変換時には、対象となる仮想アドレスａｄｄｒに対してハッシュ関数を用いてハッシュ演算が施される。このハッシュ演算の結果に基づいて、該当するグループ（ハッシュグループ）の中から該当するページが検索される。ハッシュ関数の一例を次式に示す。
【００１４】
Group No. = ((addr & 0xFFFF000) >> 12) ^ ((addr & 0xFFFF0000000) >> 28)
（１）
ここで、「addr」は仮想アドレスを、「&」は論理積演算を、「^」は排他的論理和（ＥＸＯＲ）演算を、「A >> B」はＡをＢビットだけ右シフトする操作を示す。ここでは、仮想アドレスａｄｄｒがビット４３（ＭＳＢ）〜０（ＬＳＢ）の４４ビットで表されるものとする。
【００１５】
上記のハッシュ関数を用いたハッシュ演算により、仮想アドレスａｄｄｒのビット２７〜１２とビット４４〜２８とから１６ビットのハッシュ値が生成される。この１６ビットのハッシュ値が、グループ（配列またはリスト）に対応付けられる。ここで、各グループが８エントリのページ情報の配列で実装される場合を想定する。この場合、必要な管理メモリ領域の大きさは、１エントリのサイズが１６Ｂであるとすると、
１６Ｂ＊２16＊８＝２23Ｂ（＝８ＭＢ）
となる。
【００１６】
この例では、検索に必要なメモリロードの回数は、理論的には最大８回である。しかし、現実の実装の多くでは、配列データは物理アドレスが連続した領域に置かれることから、１回のメモリロードでは、（例えば１２８バイトなどの）ライン単位でページ情報がキャッシュに読み込まれる。このため、第２エントリ以降はデータキャッシュにヒットさせることができ、メモリロードは１回〜数回で済ませることができる。
【００１７】
このように、ハッシュテーブルを用いた方法では、グループ内を配列形式にすると非常に高速な処理が可能となる。しかし、全ての仮想ページに対して変換エントリを用意することはできず、また全ての物理ページを格納できるかどうかも不確定である（使用する仮想アドレスの配置とハッシュ関数による）。ところが、現実には上記のような簡単なハッシュ関数でも特定のグループにエントリが集中することは稀で、真に必要なエントリの多くはハッシュテーブル内に存在する可能性が高い。したがって、必要なエントリがないためにソフトウェアに当該エントリの追加（更新）を依頼する頻度は低く、平均としての性能は優れている。また、グループ内をリスト形式または配列のリスト形式にすることにより、使用する物理ページの全てを網羅することも、現実の範囲で可能である。但し、使用する仮想アドレスの配置によっては、最悪の場合、同一のグループに非常に多くのエントリが存在してしまうため、処理時間の最悪値は非常に大きくなる虞がある。
【特許文献１】特開平７−４９８１２号公報（段落００２３乃至００２６、図４）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
仮想記憶方式のコンピュータシステムにおいては、ソフトウェアの機能要件や構成によっては、例えばアプリケーションが自由に仮想アドレスを選びたいという場合がある。またその用途によっては、平均性能もある程度要求し且つ処理時間の最悪値を定数にバインドしたいという要求（リアルタイム性要求）がある。このような要求がある場合で、しかも６４ビットなどの非常に大きな仮想アドレス空間を使用する場合、前述した従来技術ではそれぞれ次のような問題がある。
【００１９】
（１）ツリー構造では、処理時間の最悪値はバインドできるが、仮想アドレス空間が非常に大きいと、中間層数を多くする必要が生じる（中間層数を減らすと管理メモリ領域が大きくなる）。また、たとえ実際に使用する物理領域が小さくても、必ずツリーの深さ分のメモリロードは必要であり、その数が多いと平均性能はあまり良くない。  
（２）ハッシュテーブルでは、平均の性能は優れている。しかし、処理時間の最悪値は非常に大きくなり、リアルタイム性は確保できない。
【００２０】
本発明は上記事情を考慮してなされたものでその目的は、非常に大きな仮想アドレス空間を使用する場合でも、ある程度の平均性能を確保したまま処理時間の最悪値を制限でき、効率的なアドレス変換を実現可能とする、メモリ管理装置、コンピュータシステム及びメモリ管理方法を提供することにある。
【課題を解決するための手段】
【００２１】
本発明の１つの観点によれば、仮想記憶方式のコンピュータシステムに適用されて、仮想アドレスから物理アドレスへのアドレス変換のためのアドレス変換情報を含み、仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を用いたメモリ管理を行うメモリ管理装置にが提供される。このメモリ管理装置は、上記コンピュータシステムで実際に使用される可能性のある仮想アドレスが属する、仮想アドレス空間内の領域である仮想アドレス領域に対応付けられる木構造データであって、当該仮想アドレス領域に含まれる仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索するのに用いられる木構造データを上記物理メモリ上に生成する木構造データ生成手段と、上記仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応付けられるエントリであって、当該仮想アドレス領域に対応付けられた上記木構造データを指すポインタが設定可能なエントリを含むハッシュ構造データを上記物理メモリ上に生成するハッシュ構造データ生成手段と、任意の仮想アドレスから当該仮想アドレスが属する仮想アドレス領域に対応付けられた上記ハッシュ構造データのエントリを検索することにより、当該仮想アドレス領域に対応付けられた上記木構造データを特定して、当該木構造データから当該仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索する検索手段とを備える。
【００２２】
このような構成において、木構造データ生成手段は、コンピュータシステムで実際に使用される可能性のある仮想アドレス領域（仮想アドレス空間内の仮想アドレス領域）に対応付けられる木（ツリー）構造データを生成する。この木構造データは、当該木構造データに対応する仮想アドレス領域に含まれる仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索するのに用いられる。一方、ハッシュ構造データ生成手段は、仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応付けられるエントリであって、当該仮想アドレス領域に対応付けられた木構造データを指すポインタが設定可能なエントリを含むハッシュ構造データ（例えば、ハッシュテーブル）を生成する。検索手段は、例えばソフトウェアから要求された任意の仮想アドレスを物理アドレスに変換するアドレス変換等が必要な場合（特にページ変換エントリキャッシュの入れ替えが必要な場合）、当該仮想アドレスに基づいて、当該仮想アドレスが属する仮想アドレス領域に対応付けられたハッシュ構造データのエントリを検索し、当該ハッシュ構造データのエントリから当該仮想アドレス領域に対応付けられた木構造データ（の所在）を特定することで、当該特定された木構造データから、当該仮想アドレスが属する仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報を検索する。
【００２３】
ここで、ハッシュ構造データ内のエントリの検索処理は、最悪でも当該ハッシュ構造データに対応するアドレス空間内のアドレス領域数分に限られる。特に、ハッシュ構造データが、当該ハッシュ構造データに対応する仮想アドレス空間に属する仮想アドレスのハッシュ値に応じて複数のグループに分けて管理され、当該グループ毎にそれぞれ異なる仮想アドレス領域に対応付けることが可能な複数のエントリを有する構成とするならば、ハッシュ構造データ内のエントリの検索処理は、最悪でも、ハッシュ値に対応するグループに属する無仮想アドレス領域数分に限られる。また、検索（特定）されたハッシュテーブル内のエントリに対応付けられた木構造データ内のページ情報の検索は、当該木構造の深さに制限される。このため上記の構成においては、ある程度の平均性能を確保したまま最悪処理時間も制限でき、且つソフトウェアは高い自由度で使用する仮想アドレスを選択できる。
【００２４】
ここで、上記メモリ管理装置に、仮想アドレス空間の大きさ、登録すべき仮想アドレス領域の大きさ、ハッシュ構造データのグループ数、ハッシュ構造データのグループ内のエントリ数、ハッシュ値の計算に用いられるハッシュ計算式、及び木構造データの示す木構造の深さ（等のパラメータ群）のうちの少なくとも１つ（のパラメータ）を外部からの指定に応じて設定するための設定手段を追加すると良い。このように、ハッシュ構造（ハッシュテーブル）や木構造（ツリー）の詳細構造はシステムの規模やソフトウェア等からの要求内容によって最適の形式が異なる可能性があることから、外部（例えばソフトウェア）からの指定によってハッシュ構造の大きさや木構造の深さなどが設定可能な構成とすることにより、システムの起動時や仮想アドレス空間の作成時などにそのシステムに適した具体的データ構造を用意することができる。
【００２５】
更に、ソフトウェアがシステムの規模などの情報の一部を関知しない場合を考慮して、上記メモリ管理装置に構造決定手段を追加し、当該構造決定手段が（つまりメモリ管理装置が自ら）それらの情報を取得して詳細なデータ構造を決定する構成とするならば、ソフトウェアでのシステム情報管理を軽減し、一層効果的なメモリ管理を実現することが可能となる。
【００２６】
ここで、上述のメモリ管理装置の機能が、コンピュータシステム（特に、コンピュータシステム内のプロセッサ装置）に組み込まれた構成とすることも可能である。
【発明の効果】
【００２７】
本発明によれば、仮想アドレス空間内の登録すべき仮想アドレス領域に対応する木構造データと、仮想アドレス空間に属する全ての仮想アドレス領域の各々に対応するエントリを含むハッシュ構造データとにより、仮想領域内の仮想ページに割り当てられる物理メモリ上の物理ページに関するページ情報が保持・管理される構成とすることにより、ある程度の平均性能を確保したまま最悪処理時間も制限でき、且つソフトウェアは高い自由度で使用する仮想アドレスを選択できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施形態につき図面を参照して説明する。
【００２９】
［第１の実施形態］
図１は本発明の第１の実施形態に係る仮想記憶方式のコンピュータシステムを示すブロック構成図である。このコンピュータシステムは、プロセッサ１と、主メモリ２と、ＭＭＵ（メモリ管理ユニット）３とを備えている。プロセッサ１、主メモリ２及びＭＭＵ３は、バス４によって相互接続されている。本実施形態では、プロセッサ１、主メモリ２及びＭＭＵ３は、中央処理装置（ＣＰＵ）の構成要素であるものとする。図１では、ＣＰＵ内の他の要素は本発明と直接関係しないため省略されている。同様に、図１では、ハードディスクドライブ（ＨＤＤ）等の入出力装置（Ｉ／Ｏ装置）も、本発明と直接関係しないため省略されている。
【００３０】
プロセッサ１は、演算ユニット１１とページ情報エントリキャッシュ１２とを含む。演算ユニット１１は、プログラム命令を実行しデータを処理する。ページ情報エントリキャッシュ１２の各エントリは、仮想アドレス空間内の一部のページについてのページ情報をキャッシュエントリ情報として保持するのに用いられる。このページ情報は、仮想アドレスと物理アドレスとの間のアドレス変換に用いられるアドレス変換情報を含む。このページ情報は更に、該当する物理ページを管理するためのページ管理情報を含む。このページ管理情報は、該当する物理ページの保護のための情報（保護情報、ページ属性情報）、例えば「読み出し許可／禁止」「書き込み許可／禁止」「キャッシュ許可／禁止」などを表す情報を含む。ここで、１ページの大きさ（ページサイズ）は４ＫＢであるものとする。
【００３１】
主メモリ２は、仮想アドレス空間内の一部のページ（仮想ページ）が割り当てられる物理ページを提供する物理メモリである。主メモリ２の記憶領域の一部はソフトウェア領域２１として用いられ、別の一部はメモリ管理領域２２として用いられる。ソフトウェア領域２１には、オペレーティングシステム（ＯＳ）及びアプリケーションプログラム等の各種ソフトウェア（を構成するプログラム命令）と、当該ソフトウェアが使用するデータとが格納される。メモリ管理領域２２には、ページ検索ツリー２２１と領域検索ハッシュテーブル２２２とが格納される。メモリ管理領域２２の大きさは固定ではなく、例えばページ検索ツリー２２１、或いは領域検索ハッシュテーブル２２２の数の増減等に応じて変化する。当然のことであるが、メモリ管理領域２２の大きさが大きくなれば、ソフトウェア領域２１の大きさは小さくなる。
【００３２】
第１の実施形態において、ページ検索ツリー２２１は、仮想アドレス空間における連続するＩＭページの領域（以下、仮想アドレス領域と称する）毎に用意される。ページ検索ツリー２２１は、当該ツリー２２１に対応する１Ｍページのページ情報を検索するための木構造データである。
【００３３】
領域検索ハッシュテーブル２２２は、ページ検索ツリー２２１を検索するのに用いられるハッシュ構造データである。領域検索ハッシュテーブル２２２は、システムがサポートする仮想アドレス空間毎に用意される。仮想アドレス空間内の各アドレスは、それぞれ、複数のグループ（ハッシュグループ）のいずれかに属する。領域検索ハッシュテーブル２２２は、このハッシュグループ毎にｍ個のエントリを有する。このｍ個のエントリは、共通のハッシュグループに属するｎ個（ｎ＞ｍ）の仮想アドレス領域から選択される、最大ｍ個の任意の仮想アドレス領域に割り当て可能である。領域検索ハッシュテーブル２２２の各エントリには、当該エントリに対応する仮想アドレス領域に属する仮想アドレスの共通部分（つまり、仮想アドレスの下位３２ビットを除く上位ビット）と、当該エントリに対応する仮想アドレス領域に固有のページ検索ツリー２２１を指すポインタ（ここでは、後述するようにページ検索ツリー２２１の２２ビット中間層２２１ｂを指すポインタ）とを含むエントリ情報が保持される。
【００３４】
図２は領域検索ハッシュテーブル２２２のデータ構造例を示す。第１の実施形態では、仮想アドレスは６４ビット、物理アドレスは３２ビットである。また、ページサイズ及び仮想ページ領域サイズは、それぞれ４ＫＢ及び４ＧＢである。したがって、仮想ページ領域のページ数は４ＧＢ／４ＫＢ＝１Ｍ（ページ）である。更に、仮想アドレス空間内の各アドレスは、それぞれ、２16個（つまり６４Ｋ個＝６５，５３６個）のハッシュグループＧｉ（ｉはグループ番号であり、ｉ＝０x００００，０x０００１，…０xＦＦＦＦである）のいずれかに属する。
【００３５】
図２の例では、領域検索ハッシュテーブル２２２は、６４Ｋ個のハッシュグループ毎に、当該グループのグループ番号に対応付けられたｍ＝８個のエントリを有する。ここでは、例えばグループ番号ｉが０（ｉ＝０x００００）のグループＧ０に対応する８つのエントリの１つ（先頭エントリ）には、仮想アドレスａｄｄｒが０x００００ ００００ ００００ ００００〜０x００００ ００００ ＦＦＦＦ ＦＦＦＦの範囲の仮想アドレス領域に属する１Ｍページのページ情報を検索するためのページ検索ツリー２２１へのポインタと、当該仮想アドレスａｄｄｒの共通部分（即ち、６４ビットの仮想アドレスａｄｄｒのうちの下位３２ビットを除く上位アドレス０x００００ ００００）とを含むエントリ情報が保持される。この８つのエントリの集合は、グループ番号から一意に特定できる。このグループ番号は、例えば次式に示すハッシュ関数
Group No.
= ((addr & 0x0000FFFF00000000) >> 32) ^ ((addr & 0xFFFF00000000000) >> 48)
（２）
を用いたハッシュ演算によって算出されるハッシュ値により示される。一方、算出されたグループ番号（ハッシュ値）で特定されるエントリ集合のうち、アドレスａｄｄｒが属する仮想アドレス領域に対応するページ検索ツリー２２１へのポインタが保持されているエントリは、当該アドレスａｄｄｒのうちの下位３２ビットを除く上位アドレスが保持されているエントリに一致する。
【００３６】
図２の例では、グループ番号ｉが０（ｉ＝０x００００）のグループＧ０に対応する８つのエントリのうちの先頭エントリを除く全てのエントリには、空きエントリを示すデータ、例えばＮＵＬＬデータが保持されている。
【００３７】
同様に、グループ番号ｉが２（ｉ＝０x０００２）のグループＧ２に対応する８つのエントリのうちの６番目のエントリには、仮想アドレスａｄｄｒが０x０００６ ０００４ ００００ ００００〜０x０００６ ０００４ ＦＦＦＦ ＦＦＦＦの範囲の仮想アドレス領域に属する１Ｍページのページ情報を検索するためのページ検索ツリー２２１へのポインタと、当該仮想アドレスａｄｄｒの下位３２ビットを除く上位アドレス０x０００６ ０００４とを含むエントリ情報が保持される。このように、図２の領域検索ハッシュテーブル２２２の例では、仮想アドレスａｄｄｒが０x００００ ００００ ００００ ００００〜０x００００ ００００ ＦＦＦＦ ＦＦＦＦの範囲の仮想アドレス領域と、仮想アドレスａｄｄｒが０x０００６ ０００４ ００００ ００００〜０x０００６ ０００４ ＦＦＦＦ ＦＦＦＦの範囲の仮想アドレス領域との、２つの仮想アドレス領域が登録された状態を示す。
【００３８】
図３は、仮想アドレスａｄｄｒが０x００００ ００００ ００００ ００００〜０x００００ ００００ ＦＦＦＦ ＦＦＦＦの範囲の仮想アドレス領域に属する１Ｍページのページ情報を検索するためのページ検索ツリー２２１の木構造の一例を示す。ここでは、ページ検索ツリー２２１は、根（ルート）２２１ａと、１段の中間層（２２ビット中間層）２２１ｂと、複数の葉の層（１２ビット葉の層）２２１ｃとから構成される。
【００３９】
根２２１ａは、図３に示すページ検索ツリー２２１に対応する領域検索ハッシュテーブル２２２内のエントリによって実現される。根２２１ａには、２２ビット中間層２２１ｂへのポインタが保持される。なお、図３に示すページ検索ツリー２２１の根２２１ａと、当該ページ検索ツリー２２１に対応する領域検索ハッシュテーブル２２２内のエントリとを切り離し、当該エントリにページ検索ツリー２２１の根２２１ａを指すポインタが保持され、当該ページ検索ツリー２２１の根２２１ａに当該ページ検索ツリー２２１の２２ビット中間層２２１ｂを指すポインタが保持される構成としても良い。
【００４０】
第１の実施形態では、１Ｍページ（４ＧＢ）の仮想アドレス領域は、１，０２４（＝１Ｋ）等分されて、連続する１Ｋページ（＝４ＭＢ＝２22Ｂ）単位で管理される。ページ検索ツリー２２１の２２ビット中間層２２１ｂは、この１Ｍページ（４ＧＢ）の仮想アドレス領域が１，０２４等分された１，０２４個の１Ｋページ（＝４ＭＢ＝２22Ｂ）に対応する１，０２４個のエントリを配列形式で有する。ここで１Ｋページに属する全ての６４ビットの仮想アドレスの上位４２ビットは共通である。また、この１Ｋページを含む上記１Ｍページ（４ＧＢ）の仮想アドレス領域に属する全ての仮想アドレスの上位３２ビットは、前記したように共通である。そこで、２２ビット中間層２２１ｂの各エントリＥｊの位置、更に詳細に述べるならば先頭位置を基準とする相対位置（つまりインデックス）は、仮想アドレスの上位３２ビットの下位側に続く１０ビット、即ちビット３１〜２２の値ｊに対応付けられる。この中間層２２１ｂの各エントリは、それぞれ下位の層（ここでは、葉の層２２１ｃ）へのポインタを保持することが可能である。
【００４１】
葉の層２２１ｃは、１Ｋページ、即ち１，０２４ページの各々に対応した１，０２４個のエントリを配列形式で有する。１ページの大きさ（ページサイズ）は４ＫＢ（＝２12Ｂ）である。そこで第１の実施形態では、葉の層２２１ｃの各エントリＥｊの位置、更に詳細に述べるならば先頭位置を基準とする相対位置（つまりインデックス）は、仮想アドレスの下位１２ビットの上位側に続く１０ビット、即ちビット２１〜１２に対応付けられる。葉の層２２１ｃの各エントリは、当該エントリに対応するページ（サイズが４ＫＢのページ）が割り当てられる物理ページの物理アドレス（つまりアドレス変換情報としての実アドレス）を含むページ情報を保持する。
【００４２】
再び図１を参照すると、ＭＭＵ３は、領域登録部３１と、テーブル検索部３２と、キャッシュ入れ替え部３３と、設定部３４とを含む。領域登録部３１は、ソフトウェア領域２１に格納されているソフトウェアから、例えば当該ソフトウェアで使用する仮想アドレス領域の登録が要求された場合に、その登録要求を受け付けて、要求された仮想アドレス領域をシステム内に登録する。この仮想アドレス領域の登録のために、領域登録部３１は、要求された仮想アドレス領域に固有のページ検索ツリー２２１を主メモリ２のメモリ管理領域２２に用意する。領域登録部３１はまた、要求された仮想アドレス領域に属する仮想アドレスに共通のハッシュグループ番号で特定される領域検索ハッシュテーブル２２２内のエントリ集合に含まれている空きエントリに、メモリ管理領域２２に用意されたページ検索ツリー２２１へのポインタを含むエントリ情報（ハッシュ構造データ）を設定する。
【００４３】
テーブル検索部３２は、仮想ページの仮想アドレスに基づき領域検索ハッシュテーブル２２２から当該仮想アドレスに対応するエントリ情報を検索し、当該エントリ情報に含まれているポインタにより指定されるページ検索ツリー２２１から当該仮想アドレスに対応するページ情報を検索する。キャッシュ入れ替え部３３は、演算ユニット１１がページ情報エントリキャッシュ１２から目的のページ情報を取得できなかったキャッシュミスの場合、当該演算ユニット１１からの要求に応じ、テーブル検索部３２を用いてページ情報エントリキャッシュ１２の入れ替えを行う。設定部３４は、仮想アドレス領域の大きさ、領域検索ハッシュテーブル２２２のグループ数（ハッシュグループ数）、グループ内のエントリ数、ページ検索ツリー２２１の深さ（中間層の数）及びハッシュ関数（ハッシュ計算式）等を設定する。
【００４４】
次に、図１のシステムにおける動作について、（１）領域登録処理、（２）ページ情報（物理メモリ）割り当て処理、及び（３）ページ情報取得処理を例に、順次説明する。
【００４５】
（１）領域登録処理
まず、ＭＭＵ３の領域登録部３１による領域登録処理について、図４のフローチャートを参照して説明する。今、主メモリ２のソフトウェア領域２１に格納されているソフトウェア（例えばＯＳ）が起動されたものとする。この場合、起動されたソフトウェアは、仮想アドレスの使用に先立って、当該ソフトウェアが使用する可能性のある仮想アドレスが属する仮想アドレス空間内の仮想アドレス領域の登録を、図１において矢印５１で示されるように、ＭＭＵ３に要求する。
【００４６】
ＭＭＵ３の領域登録部３１は、ソフトウェア（ＯＳ）から仮想アドレス領域の登録が要求されると要求受付手段として機能して、ソフトウェア（ＯＳ）からの仮想アドレス領域の登録要求を受け付ける。すると領域登録部３１はページ検索ツリー（木構造データ）生成手段として機能して、仮想アドレス領域登録のための以下に述べるページ検索ツリー（木構造データ）生成を行う。
【００４７】
まず領域登録部３１は、メモリ管理領域２２を拡張して、要求された仮想アドレス領域に対応するページ検索ツリー２２１の２２ビット中間層２２１ｂのデータ構造を格納するための領域（管理データ領域）を当該メモリ管理領域２２内に確保する（ステップＳ１）。２２ビット中間層２２１ｂは、１，０２４個のエントリの配列を有する。この時点において、要求された仮想アドレス領域の各ページには、物理メモリ（ここでは主メモリ２）の物理ページが未だ割り当てられていない。そこで領域登録部３１は、２２ビット中間層２２１ｂの１，０２４個のエントリを全て「無効（空き）」エントリに初期化する（ステップＳ２）。ここでは、２２ビット中間層２２１ｂの１，０２４個のエントリに、いずれもＮＵＬＬデータを設定することで、当該エントリが無効エントリに初期化される。
【００４８】
次に領域登録部３１は、要求された仮想アドレス領域に属する仮想アドレス、例えば当該仮想アドレス領域の先頭の仮想アドレスから、式（２）に示されるハッシュ関数を用いて、当該仮想アドレス領域が属するハッシュグループの番号（ハッシュグループ番号）Ｇｉ（を表すハッシュ値）を算出する（ステップＳ３）。そして領域登録部３１は、算出されたハッシュグループ番号Ｇｉで特定される、領域検索ハッシュテーブル２２２の８つのエントリ（つまりハッシュグループＧｉ内の８つのエントリ）から、ＮＵＬＬデータが設定されている「未使用（空き）」のエントリを１つ、登録すべき仮想アドレス領域に対応付けるエントリとして検索する（ステップＳ４）。
【００４９】
次に領域登録部３１はハッシュ構造データ（領域検索ハッシュテーブル）生成手段として機能して、検索されたハッシュグループＧｉ内のエントリの情報を、ＮＵＬＬデータから、登録すべき仮想アドレス領域を指す「仮想アドレス」と、先のステップＳ１で用意したページ検索ツリー２２１の２２ビット中間層２２１ｂへの「ポインタ」（２２ビット中間層２２１ｂの存在するアドレス）とを含む情報に書き換える（ステップＳ５）。ここで、登録すべき仮想アドレス領域を指す「仮想アドレス」には、当該仮想アドレス領域の先頭アドレスが用いられる。この仮想アドレス領域の先頭アドレスは４ＧＢの境界上にある。このため第１の実施形態では、ハッシュグループＧｉ内のエントリには、「仮想アドレス」の下位３２ビット（０x００００００００）を除く上位アドレスだけが保持される。この上位アドレス（つまり、「仮想アドレス」の上位３２ビット）の値は、登録すべき仮想アドレス領域に属する全ての仮想アドレスの下位３２ビットを除く上位アドレスに共通する。したがって、仮想アドレス領域の先頭アドレスの下位３２ビットを除く上位アドレス（仮想アドレスの上位３２ビット）がハッシュグループＧｉ内のエントリに保持されることは、当該仮想アドレス領域に属する全ての仮想アドレスに共通するアドレス部分（仮想アドレスの上位３２ビット）が、当該仮想アドレス領域を特定する情報として保持されることと等価である。
【００５０】
上述した領域登録部３１によるステップＳ１〜Ｓ５の処理によって、ソフトウェアから要求された仮想アドレス領域がシステムに登録されたことになる。つまりソフトウェアは、ＭＭＵ３の領域登録部３１を利用することで、使用する可能性のある仮想アドレス領域を任意のタイミングで登録できる。この仮想アドレス領域の登録後は、ソフトウェアは、ＭＭＵ３のテーブル検索部３２を用いて、登録された仮想アドレス領域内の仮想ページに対して物理メモリの割り当て（実際の使用）を行うことができる。ソフトウェアは、物理メモリが割り当てられたページに対しては、その仮想アドレスを用いてプログラム命令やデータを読み書きすることができる。
【００５１】
上記したように第１の実施形態では、ＭＭＵ３の領域登録部３１による領域登録処理が、ＯＳ等のソフトウェアからの仮想アドレス領域の登録要求に応じて実行される。しかし、以下に述べるアドレス変換情報を含むページ情報（で示される物理ページ）の割り当て時に領域登録部３１による領域登録処理が自動的に実行されるようにすることも可能である。
【００５２】
（２）ページ情報（物理ページ）割り当て処理
次に、ＭＭＵ３のテーブル検索部３２によるページ情報（物理ページ）割り当て処理について、図５のフローチャートを参照して説明する。今、主メモリ２のソフトウェア領域２１に格納されているソフトウェアからＭＭＵ３に対して、先に登録された仮想アドレス領域内の任意の仮想ページに対するページ情報の割り当てが要求されたものとする。
【００５３】
ＭＭＵ３のテーブル検索部３２は、ソフトウェアからの割り当て要求に応じて、要求された仮想ページの仮想アドレス（例えば仮想ページの先頭アドレス）から、式（２）に示されるハッシュ関数を用いて、当該仮想アドレスに対応する仮想アドレス領域が属するハッシュグループの番号（ハッシュグループ番号）Ｇｉを算出する（ステップＳ１１）。そしてテーブル検索部３２は、算出されたハッシュグループ番号Ｇｉで特定される、領域検索ハッシュテーブル２２２の８つのエントリ（ハッシュグループＧｉ内の８つのエントリ）の情報を主メモリ２のメモリ管理領域２２からロードして、当該８つのエントリの中から、要求された仮想ページが属する仮想アドレス領域に対応付けられたエントリを検索する（ステップＳ１２）。ここでは、ロードされたハッシュグループＧｉ内の８つのエントリにそれぞれ保持されている仮想アドレス（の上位３２ビット）と要求された仮想ページの先頭アドレス（の上位３２ビット）とを順に比較することで、一致するエントリが検索される。
【００５４】
テーブル検索部３２は、ステップＳ１２でのエントリ検索の結果、仮想アドレスが一致するエントリが検索できなかった場合には（ステップＳ１３）、その仮想アドレスは登録された仮想アドレス領域の範囲外であると判断する。この場合、テーブル検索部３２は、割り当てを要求したソフトウェアに対して、要求された仮想ページが属する仮想アドレス領域が未登録であることを示す領域未登録エラーを返す。これに対し、仮想アドレスが一致するエントリが検索できた場合には（ステップＳ１３）、テーブル検索部３２は検索されたエントリから、要求された仮想ページが属する仮想アドレス領域に対応付けられたページ検索ツリー２２１へのポインタ、更に詳細に述べるならばページ検索ツリー２２１の２２ビット中間層２２１ｂへのポインタを取得する（ステップＳ１４）。
【００５５】
次にテーブル検索部３２は、ステップＳ１４で取得されたポインタで指定されたページ検索ツリー２２１の２２ビット中間層２２１ｂ内の検索に移る。まずテーブル検索部３２は、取得されたポインタで指定された２２ビット中間層２２１ｂ内の１，０２４個のエントリ（図２参照）のうち、要求された仮想ページに対応するエントリＥｊのインデックスを、当該要求された仮想ページの仮想アドレス（先頭アドレス）から計算する（ステップＳ１５）。ここでは、要求された仮想ページの仮想アドレス（先頭アドレス）のビット３１〜２２の値ｊが、エントリＥｊのインデックスとして計算される。このステップＳ１５において、テーブル検索部３２は、取得されたポインタで指定された２２ビット中間層２２１ｂ内の１，０２４個のエントリのうち、計算されたインデックス値ｊで指定されるエントリＥｊから、当該中間層２２１ｂの下位層をなす１２ビット葉の層２２１ｃへのポインタを取得する。
【００５６】
次にテーブル検索部３２は、取得されたポインタが無効（ＮＵＬＬ）であるかを判別する（ステップＳ１６）。もし、取得されたポインタが無効であるならば、テーブル検索部３２はメモリ管理領域２２を拡張して、目的とする１２ビット葉の層２２１ｃの領域を当該メモリ管理領域２２内に確保する（ステップＳ１７）。そしてテーブル検索部３２は、確保された１２ビット葉の層２２１ｃの１，０２４個のエントリを全て「無効」エントリに初期化する（ステップＳ１８）。
【００５７】
続いてテーブル検索部３２は、ステップＳ１５で計算されたインデックス値ｊで指定される、２２ビット中間層２２１ｂ内のエントリＥｊを、無効エントリから、上記確保された１２ビット葉の層２２１ｃの先頭位置を指すポインタが設定された有効エントリに変更する（ステップＳ１９）。そしてテーブル検索部３２は、ステップＳ２０の処理に進む。これに対し、ステップＳ１５で取得されたポインタが無効でないならば（ステップＳ１６）、テーブル検索部３２はステップＳ１７〜Ｓ１９をスキップして、ステップＳ２０の処理に進む。
【００５８】
ステップＳ２０において、テーブル検索部３２は、１２ビット葉の層２２１ｃの１，０２４個のエントリのうち、要求された仮想ページに対応するエントリＥｋのインデックスを、当該要求された仮想ページの仮想アドレス（先頭アドレス）から計算する。ここでは、要求された仮想ページの仮想アドレス（先頭アドレス）のビット２１〜１２の値ｋが、エントリＥｋのインデックスとして計算される。
【００５９】
次にテーブル検索部３２は、１２ビット葉の層２２１ｃの１，０２４個のエントリのうち、ステップＳ２０で計算されたインデックス値ｋで指定されるエントリＥｋに、要求された仮想ページに新たに割り当てられる（または既に割り当てられている）物理ページのページ情報を書き込む（または更新する）（ステップＳ２１）。このページ情報は、要求された仮想ページに割り当てられる物理ページの物理アドレス（ｒｅａｌ  ａｄｄｒ）、つまりアドレス変換情報を含む。またページ情報は更に、要求された仮想ページに割り当てられる物理ページを管理する（例えば保護する）ためのページ管理情報を含むものとする。ページ情報の更新では、ページ管理情報のみが更新されることもある。
【００６０】
上述したテーブル検索部３２によるステップＳ１１〜Ｓ２１の処理によって、ソフトウェアから要求された仮想ページに対してページ情報（によって示される物理ページ）が割り当てられる。即ち、ソフトウェアから要求された仮想ページに割り当てられる物理ページの物理アドレス（アドレス変換情報）を含む新たな（または更新された）ページ情報が、当該仮想ページに対応付けられた、葉の層２２１ｃ内のエントリに保存される。この葉の層２２１ｃへのポインタは、ソフトウェアから要求された仮想ページが属する仮想アドレス領域に対応付けられたページ検索ツリー２２１の中間層２２１ｂ内の１つのエントリに保存される。この中間層２２１ｂ内の１つのエントリは、仮想アドレス領域が１，０２４（＝１Ｋ）等分された連続する１Ｋページ（＝４ＭＢ）の領域のうち、要求された仮想ページが属する１Ｋページ（＝４ＭＢ）の領域に対応付けられたエントリである。
【００６１】
第１の実施形態では、中間層２２１ｂ内のあるエントリに対応付けられた１Ｋページ（＝４ＭＢ）の領域に属する仮想ページに物理ページが全く割り当てられていない状態では、当該エントリに無効を示す値（ＮＵＬＬデータ）が保持されるだけで、当該１Ｋページ（＝４ＭＢ）の領域に対応付けられる葉の層２２１ｃは確保されない。これにより、主メモリ２内のメモリ管理領域２２が不要に拡張されるのを防止して、当該メモリ管理領域２２を節約することができる。
【００６２】
（３）ページ情報取得処理
次に、ＭＭＵ３のテーブル検索部３２によるテーブル検索を含むページ情報取得処理について、図６のフローチャートを参照して説明する。まず、プロセッサ１内の演算ユニット１１が、主メモリ２のソフトウェア領域２１からプログラム命令またはデータを取り出して、当該プログラム命令を実行または当該データを処理しようとするものとする。このプログラム命令またはデータが格納されている領域のアドレス（プログラム命令またはデータのアドレス）は仮想アドレスで表現される。このため演算ユニット１１が、プログラム命令またはデータを主メモリ２から実際に取り出すには、当該プログラム命令またはデータの仮想アドレスを物理アドレスに変換する必要がある。
【００６３】
そこで演算ユニット１１は、ソフトウェアからプログラム命令またはデータの仮想アドレスを受け取ると、当該仮想アドレスに対応するアドレス変換情報を含むページ情報を取得するために、ページ情報エントリキャッシュ１２を検索する。
【００６４】
もし、ページ情報エントリキャッシュ１２から目的のページ情報を取得できたならば、演算ユニット１１は当該ページ情報中のアドレス変換情報（物理アドレス）を用いて、ソフトウェアから受けとった仮想アドレスを物理アドレスに変換する。そして演算ユニット１１は、変換後の物理アドレスによって指定される主メモリ２の領域から、図１において矢印５２で示すようにプログラム命令またはデータを取り出して処理する。
【００６５】
これに対し、ページ情報エントリキャッシュ１２から目的のページ情報を取得できなかった場合、つまりページ情報エントリキャッシュ１２に目的のページ情報が保持されているエントリ（ページ情報エントリ）が存在しなかった場合、演算ユニット１１は図１において矢印５３で示すように、ＭＭＵ３にキャッシュミスを通知する。ＭＭＵ３のテーブル検索部３２は、演算ユニット１１からキャッシュミスが通知されると、図１において矢印５４で示すようにメモリ管理領域２２から該当するエントリを検索して、当該エントリの情報を取得するためのページ情報取得処理を次のように実行する。
【００６６】
まずテーブル検索部３２は、ミスヒットとなった仮想アドレスから、式（２）に示されるハッシュ関数を用いて、当該仮想アドレスに対応する仮想アドレス領域が属するハッシュグループの番号（ハッシュグループ番号）Ｇｉを算出する（ステップＳ３１）。そして領域登録部３１は、算出されたハッシュグループ番号Ｇｉで特定される、領域検索ハッシュテーブル２２２の８つのエントリ（ハッシュグループＧｉ内の８つのエントリ）の情報を主メモリ２のメモリ管理領域２２からロードして、当該８つのエントリの中から、ミスヒットとなった仮想ページが属する仮想アドレス領域に対応付けられたエントリを検索する（ステップＳ３２）。
【００６７】
テーブル検索部３２は、ステップＳ２２でのエントリ検索の結果、仮想アドレスが一致するエントリが検索できなかった場合には（ステップＳ３３）、その仮想アドレスは登録された仮想アドレス領域の範囲外であると判断する。この場合、テーブル検索部３２は、キャッシュミスを通知した演算ユニット１１に対して、ミスヒットとなった仮想アドレスが属する仮想ページが無効であることを示すページ無効エラーを返す。
【００６８】
これに対し、ステップＳ３２でのエントリ検索の結果、仮想アドレスが一致するエントリが検索できた場合には（ステップＳ３３）、テーブル検索部３２は検索されたエントリから、ミスヒットとなった仮想ページが属する仮想アドレス領域に対応付けられたページ検索ツリー２２１へのポインタ（ページ検索ツリー２２１の２２ビット中間層２２１ｂへのポインタ）を取得する（ステップＳ３４）。
【００６９】
次にテーブル検索部３２は、ステップＳ２４で取得されたポインタで指定された２２ビット中間層２２１ｂ内の１，０２４個のエントリ（図２参照）のうち、ミスヒットとなった仮想ページに対応するエントリＥｊのインデックスを、当該ミスヒットとなった仮想ページの仮想アドレス（先頭アドレス）から、上記ステップＳ１５の処理と同様にして計算する（ステップＳ３５）。このステップＳ３５において、テーブル検索部３２は、取得されたポインタで指定された２２ビット中間層２２１ｂ内の１，０２４個のエントリのうち、計算されたインデックス値ｊで指定されるエントリＥｊの情報をロードして、当該中間層２２１ｂの下位層をなす１２ビット葉の層２２１ｃへのポインタを取得する。
【００７０】
次にテーブル検索部３２は、取得されたポインタが無効（ＮＵＬＬ）であるかを判別する（ステップＳ３６）。もし、取得されたポインタが無効であるならば、テーブル検索部３２は演算ユニット１１に対してページ無効エラーを返す。
【００７１】
これに対して、取得されたポインタが無効でないならば、テーブル検索部３２は、当該ポインタで指定される葉の層２２１ｃの１，０２４個のエントリのうち、ミスヒットとなった仮想アドレスが属する仮想ページに対応するエントリＥｋのインデックスを、当該仮想アドレスから計算する（ステップＳ３７）。そしてテーブル検索部３２は、葉の層２２１ｃの１，０２４個のエントリのうち、ステップＳ３７で計算されたインデックス値ｋで指定されるエントリＥｋの情報を読み出す（ステップＳ３８）。
【００７２】
テーブル検索部３２は、読み出されたエントリＥｋの情報が無効であるかを判定する（ステップＳ３９）。もし、読み出されたエントリＥｋの情報が無効であるならば、テーブル検索部３２は演算ユニット１１に対してページ無効エラーを返す。これに対し、読み出されたエントリＥｋの情報が無効でないならば、テーブル検索部３２は当該情報から、ミスヒットとなった仮想アドレスが属する仮想ページに割り当てられた物理ページの物理アドレス（つまりアドレス変換情報）及び／またはページ管理情報を取得する（ステップＳ４０）。
【００７３】
領域登録部３１のキャッシュ入れ替え部３３は、メモリ管理領域２２に保存されているページ検索ツリー２２１からテーブル検索部３２によって取得された物理アドレス（つまりアドレス変換情報）及び／またはページ管理情報、つまりページ情報を、図１において矢印５５で示すように、ページ情報エントリキャッシュ１２の１つの空きエントリにロードする。もし、ページ情報エントリキャッシュ１２内に空きエントリがない場合には、キャッシュ入れ替え部３３は、例えばＬＲＵ（Least Recently Used）法に従って、当該キャッシュ１２から、その時点において最も優先度が低いエントリを選択して、その選択されたエントリに、テーブル検索部３２によって取得されたページ情報をキャッシュエントリ情報として書き込む。これにより演算ユニット１１は、ページ情報エントリキャッシュ１２から目的のページ情報を取得して、例えば当該当該ページ情報中のアドレス変換情報（物理アドレス）を用いて、ソフトウェアから受けとった仮想アドレスを改めて物理アドレスに変換することができる。
【００７４】
このように第１の実施形態においては、領域検索ハッシュテーブル２２２とページ検索ツリー２２１とを組み合わせたことで、ページ情報エントリキャッシュ１２に目的のページ情報が保持されているエントリ（ページ情報エントリ）が存在しなかったキャッシュミスヒットの場合、３回のメモリロード動作で、目的のページ情報を取得できる。これにより、ページ情報をツリー構造だけで管理する場合と比べて、ミスヒット時の仮想アドレスから物理アドレスへのアドレス変換を高速に行える。３回のメモリロード動作は、主メモリ２（のメモリ管理領域２２）からハッシュグループＧｉ内の８つのエントリをロードする動作と、ページ検索ツリー２２１の中間層２２１ｂからキャッシュミスヒットした仮想アドレスに対応するエントリをロードする動作と、ページ検索ツリー２２１の葉の層２２１ｃからキャッシュミスヒットした仮想アドレスに対応するエントリをロードする動作である。
【００７５】
また、領域検索ハッシュテーブル２２２とページ検索ツリー２２１とを組み合わせたことで、ページ情報を管理するのに必要なメモリ管理領域２２の大きさも、ページ情報をハッシュテーブルだけで管理する場合と比べて、物理メモリ全体の大きさに対して十分小さく抑えることができる。
【００７６】
さて、仮想アドレス領域の大きさ（実施形態では４ＧＢ）、領域検索ハッシュテーブル２２２（ハッシュ構造）のグループの数（実施形態では６４Ｋ個、つまり６５，５３６個）、グループ内のエントリの数（実施形態では８個）、ページ検索ツリー２２１（木構造）の深さ（中間層の数）などのパラメータ値の最適値は、ソフトウェアの仕様（例えば、ページの大きさ、仮想アドレス空間の大きさ、仮想アドレス領域の大きさ）やシステム全体の規模（例えば、物理メモリの大きさ）によって異なる。また、最適なハッシュ関数（ハッシュ計算式）も、ソフトウェアの仕様やシステム全体の規模によって異なる。
【００７７】
そこで、ソフトウェアは、自身の起動時などに、ＭＭＵ３が必要とするパラメータやハッシュ計算式を、当該ソフトウェアの仕様やシステム全体の規模に適したものに決定し、その決定されたパラメータやハッシュ計算式を設定部３４を用いて設定する。ここでは、ソフトウェアは、物理メモリの大きさに応じ、それが大きいほど、（１）登録する仮想アドレス領域の大きさを大きく決定する、（２）領域検索ハッシュテーブル２２２のグループ数を多く決定する、（３）グループ内のエントリ数を少なく決定する、（４）ページ検索ツリー２２１の深さを浅く決定する、のうちの少なくとも１つを実行する。
【００７８】
また、ソフトウェアが、ページの大きさに応じ、それが大きいほど、（１）登録する仮想アドレス領域の大きさを大きく決定する、（２）領域検索ハッシュテーブル２２２のグループ数を少なく決定する、（３）グループ内のエントリ数を少なく決定する、（４）ページ検索ツリー２２１の深さを浅く決定する、のうちの少なくとも１つを実行しても構わない。
【００７９】
また、ソフトウェアが、仮想アドレス空間の大きさに応じ、それが大きいほど、（１）登録すべき仮想アドレス領域の大きさを大きく決定する、（２）領域検索ハッシュテーブル２２２のグループ数を少なく決定する、（３）グループ内のエントリ数を少なく決定する、（４）ページ検索ツリー２２１の深さを深く決定する、のうちの少なくとも１つを実行しても構わない。
【００８０】
また、ソフトウェアが、登録すべき仮想アドレス領域の大きさに応じ、それが大きいほど、（１）領域検索ハッシュテーブル２２２のグループ数を少なく決定する、（２）グループ内のエントリ数を少なく決定する、（３）ページ検索ツリー２２１の深さを深く決定する、のうちの少なくとも１つを実行しても構わない。
【００８１】
また、ソフトウェアが、仮想アドレス空間毎の登録すべき仮想アドレス領域の個数の最大値に応じ、それが大きいほど、（１）領域検索ハッシュテーブル２２２のグループ数を多く決定する、（２）グループ内のエントリ数を多く決定する、（３）ページ検索ツリー２２１の深さを浅く決定する、のうちの少なくとも１つを実行しても構わない。
【００８２】
［第２の実施形態］
次に、本発明の第２の実施形態につき図面を参照して説明する。図７Ａ及び図７Ｂは本発明の第２の実施形態に係る仮想記憶方式のコンピュータシステムを示すブロック構成図である。図７Ａ及び図７Ｂにおいて、図１と等価な要素には同一符号を付してある。また図７Ａ及び図７Ｂでは、図１に示されているプロセッサ１及びバス４は省略されている。
【００８３】
第２の実施形態の特徴は、領域検索ハッシュテーブル２２２のグループの数、グループ内のエントリの数及びページ検索ツリー２２１の深さ、つまりハッシュ構造及び木構造を特定するパラメータを、ソフトウェアではなくてＭＭＵが決定する点にある。そのため、図７Ａ及び図７Ｂに示すシステムでは、図１中のＭＭＵ３に代えて、構造決定部３５が追加されたＭＭＵ３０が用いられる。この構造決定部３５は、ハードウェアのコンフィグレーション情報やソフトウェアによる設定情報など、システムの規模・要求（例えば、物理メモリの大きさ、ページの大きさ、仮想アドレス空間の大きさ、登録すべき仮想アドレス領域の大きさ、または仮想アドレス空間毎の登録すべき仮想アドレス領域の個数の最大値）に基づいて、ハッシュ構造及び木構造を特定するパラメータ値を決定する機能を有する。
【００８４】
図７Ａと図７Ｂとの違いは物理メモリの大きさであり、図７Ａでは物理メモリの大きさは２35Ｂであるのに対し、図７Ｂでは物理メモリの大きさは２25Ｂである。この物理メモリの違いに応じて、図７Ａと図７Ｂのシステムでは、ページ検索ツリー２２１及び領域検索ハッシュテーブル２２２の構造も異なる。
【００８５】
以下、図７Ａ及び図７Ｂの両システムにおけるＭＭＵ３０の構造決定部３５の動作について説明する。まず、ＭＭＵ３０の構造決定部３５は、システムの起動時に、例えば当該システムのコンフィグレーション情報から当該システムが有する物理メモリの大きさの情報を取得する。また構造決定部３５は、例えばＯＳ（ソフトウェア）から仮想アドレス空間の大きさの情報及びソフトウェアが使用する仮想空間毎の仮想アドレス領域の個数の最大値を取得する。ここでは説明を簡略化するために、仮想アドレス空間の大きさと、使用する仮想アドレス領域の数とは、図７Ａ及び図７Ｂの両システムにおいて、それぞれ同一であるものとする。
【００８６】
構造決定部３５は、図７Ａのシステムのように物理メモリの大きさが大きい場合、領域検索ハッシュテーブル２２２（ハッシュ構造）を大きし、ページ検索ツリー２２１（木構造）の深さを浅くするように決定する。領域検索ハッシュテーブル２２２を大きくするには、（１）領域検索ハッシュテーブル２２２のグループ数を多くする、（２）グループ内のエントリ数を少なく決定する、のうちの少なくとも１つを実行すれば良い。具体的には、物理メモリの大きさが２35Ｂである図７Ａのシステムでは、ページ検索ツリー２２１の深さを２層（つまり中間層２２１ｂの段数を２）にする。ページ検索ツリー２２１が浅いと領域検索ハッシュテーブル２２２を大きくする必要がある。例えばページ検索ツリー２２１の各層（中間層２２１ｂ）が１，０２４個のエントリの配列であったなら、ページ検索ツリー２２１が１層少なくなる毎に、領域検索ハッシュテーブル２２２を１，０２４倍の大きさにするべきである。しかし、物理メモリ全体の大きさが大きいため、メモリ管理領域２２自体が同程度の比率で大きくなっても全体のメモリ容量に与える影響は少ない。そしてページ検索ツリー２２１の深さが減った分だけ、検索時のメモリアクセス回数を減らすことができ、高速な処理が可能になる。
【００８７】
これに対し、図７Ｂのシステムのように物理メモリの大きさが図７Ａのシステムと比較して小さい場合、構造決定部３５は、ハッシュ構造を小さくし、木構造の深さを深くするように決定する。ハッシュ構造を小さくするには、（１）領域検索ハッシュテーブル２２２のグループ数を少なくする、（２）グループ内のエントリ数を多く決定する、のうちの少なくとも１つを実行すれば良い。具体的には、物理メモリの大きさが２25Ｂである図７Ｂのシステムでは、メモリ管理領域２２に使用できる大きさも小さくする必要があるため、ページ検索ツリー２２１の深さを、図７Ａのシステムより深い例えば３層（つまり中間層２２１ｂの段数を３）にする。これにより、検索時のメモリアクセス回数が、図７Ａのシステムより１回増加するものの、領域検索ハッシュテーブル２２２を小さくして、現実的な大きさに収めることができる。
【００８８】
このように、第２の実施形態においては、ＭＭＵ３０が自ら、ハッシュ構造及び木構造を特定するパラメータを物理メモリの大きさを考慮した適切な値に決定することにより、ソフトウェアに当該物理メモリの大きさを意識させることなく、ハッシュ構造及び木構造の現実的な使用状態を実現することができる。
【００８９】
なお、物理メモリの大きさ以外でも、ページの大きさ、仮想アドレス空間の大きさ、登録する仮想アドレス領域の大きさ、及び登録する仮想アドレス領域の個数の最大値などのうちの少なくとも１つの要素を考慮して、ＭＭＵ３０の構造決定部３５がハッシュ構造の大きさ、または木構造の深さを決定することも可能である。この場合にも、構造決定部３５はソフトウェアに当該要素を意識させることなく、適切なハッシュ構造及び木構造を設定して、より最適に近い使用状態を実現できる。
【００９０】
上記第１（または第２）の実施形態では、ＭＭＵ（メモリ管理装置）３（または３０）が独立して設けられている。しかし、ＭＭＵ３（または３０）の機能を、必ずしもＭＭＵによって実現する必要はなく、コンピュータシステムがＭＭＵ３（または３０）の機能を有していれば良い。例えば、ＭＭＵ３（または３０）の全てまたは一部を、プロセッサに組み込むことも可能である。また、ＭＭＵ３（または３０）の機能の全てまたは一部を、コンピュータ（プロセッサ）によって読み取り実行されるソフトウェアで実現することも可能である。
【００９１】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【図面の簡単な説明】
【００９２】
【図１】本発明の第１の実施形態に係る仮想記憶方式のコンピュータシステムを示すブロック構成図。
【図２】図１中の領域検索ハッシュテーブル２２２のデータ構造例を示す図。
【図３】図１中のページ検索ツリー２２１の木構造の一例を示す図。
【図４】同実施形態における領域登録処理の手順を示すフローチャート。
【図５】同実施形態におけるページ情報割り当て処理の手順を示すフローチャート。
【図６】同実施形態におけるページ情報取得処理の手順を示すフローチャート。
【図７Ａ】本発明の第２の実施形態に係る仮想記憶方式のコンピュータシステムの、物理メモリの大きさが２35Ｂの場合における概略構成を示すブロック図。
【図７Ｂ】本発明の第２の実施形態に係る仮想記憶方式のコンピュータシステムの、物理メモリの大きさが２25Ｂの場合における概略構成を示すブロック図。
【符号の説明】
【００９３】
１…プロセッサ、２…主メモリ（物理メモリ）、３，３０…ＭＭＵ（メモリ管理ユニット、メモリ管理装置）、４…バス、１１…演算ユニット、１２…ページ情報エントリキャッシュ、２１…ソフトウェア領域、２２…メモリ管理領域、３１…領域登録部、３２…テーブル検索部、３３…キャッシュ入れ替え部、３４…設定部、３５…構造決定部、２２１…ページ検索ツリー（木構造データ）、２２１ａ…根（ルート）、２２１ｂ…中間層（２２ビット中間層）、２２１ｃ…葉の層（１２ビット葉の層）、２２２…領域検索ハッシュテーブル（ハッシュ構造データ）。
【図１】
2006178764.tif 000003
【図２】
2006178764.tif 000004
【図３】
2006178764.tif 000005
【図４】
2006178764.tif 000006
【図５】
2006178764.tif 000007
【図６】
2006178764.tif 000008
【図７Ａ】
2006178764.tif 000009
【図７Ｂ】
2006178764.tif 000010