JP2006515088A - 実時間アプリケーションのためのメモリ管理を改良する方法 - Google Patents

Abstract

【課題】
コンピュータ・システムにおけるメモリ管理を改善する。
【解決手段】
アドレス変換情報のサブセットが、ＣＰＵによる高速アクセスのためにそのようなアドレス変換情報を保存するために予約されたキャッシュ・メモリにおける他のタイプのアドレス変換情報によって置換されないようにする。このようにして、ＣＰＵは、キャッシュに保存されたアドレス変換情報のサブセットを識別することができる。

Description

本発明は、一般的に言えば、コンピュータ・システムにおけるメモリ管理に関し、更に詳しく言えば、コンピュータ・システムにおいて稼動する実時間アプリケーションのパフォーマンスを向上させるためのメモリ・アドレス変換機構の改良に関するものである。

最新のコンピュータ・システムでは、そのコンピュータ・システムの物理メモリ又は実メモリというリソースを管理するために、仮想メモリとして知られている技法が使用されている。この技法は、非常に大量のメモリの幻影をアプリケーションに与える。当初、仮想メモリ・システムは、物理的メモリ又は実メモリが小さ過ぎるという問題を解決するために開発された。これは、大量のメモリを有する最新のシステムでは最早１つの要因とはなり得ないが、仮想メモリ機構自体は、別の理由で価値あるものであることを証明した。これらの理由のうち、仮想メモリ機構は、メモリ・アプリケーション及び／又はメモリ保護、並びに、アプリケーション・プログラムの設計を簡素化する。

仮想メモリシステムでは、複数のページ・テーブル・エントリ（ＰＴＥ）を有するページ・テーブルによって、仮想アドレスが実アドレスに変換される。一般に、そのようなページ・テーブルは、ＤＲＡＭチップのようなコンピュータ・システムのメイン・メモリに保存される。しかし、ＣＰＵとメイン・メモリとの間を接続するメモリ・バスはＣＰＵの動作速度よりもずっと遅いので、ＣＰＵとメイン・メモリとの間にはボトルネックが存在する。実時間応答を必要としないアプリケーションに対しては、このボトルネックが不可避的な問題を生じることはないであろう。しかし、多くの実時間アプリケーションは、このボトルネックが、そのようなアプリケーションの操作において認識し得るような遅延を生じるものと理解する。

このボトルネックの問題を回避するための既知の技法は、中央処理装置（ＣＰＵ）に近接している変換索引緩衝機構（ＴＬＢ）と呼ばれる特殊なキャッシュにＰＴＥを保存することである。一般に、ＴＬＢはＣＰＵ内にオンチップで常駐し、ＣＰＵによりサーチされるＰＴＥの特定のセットがＴＬＢに保存されている限り、メイン・メモリにおけるページ・テーブルのルックアップと関連した如何なる遅延も排除されるか又はかなり減少する。ＰＴＥの特定のセットがＴＬＢにおいて見つからないとき、この事象は、一般には、ＴＬＢミスとして定義される。

一般的に、メモリ読取り要求、及び／又は、書込み要求が行われると、仮想メモリから実メモリへのマッピングがＴＬＢ内にキャッシュされる。ＴＬＢミスが存在するとき、専用のハードウェア又はソフトウェアが正しいＰＴＥをＴＬＢに再ロードしなければならない。ＴＬＢのソフトウェア再ロード又はハードウェア再ロードは、パフォーマンスを考慮するとかなり高価なものになることがある。それは、そのような再ロードが、メイン・メモリからＰＴＥを読み出すこと及び一致を見つけることを必要とするためである。一般に、それは、一致を見つけるために３つまでのキャッシュ・ライン・ミスを処理することが可能である。従って、実時間アプリケーションにおいては、ＴＬＢミスを生じることは望ましくない。

従って、本発明は、「請求の範囲」の請求項１に記載されたようなコンピュータ・システムにおけるメモリ管理を改良するための方法及び他の請求項に記載されたようなコンピュータ・プログラムを提供する。

本発明及びそれの利点をより完全に理解するためには、添付図面と関連して行われる以下の説明を参照すべきである。

本願において開示されるすべての機能は、別の方法を示されてない場合、ハードウェア又はソフトウェア、或いは、それの組み合わせでもって遂行することが可能である。しかし、好適な実施例では、それらの機能が、コンピュータ・プログラム・コードのようなコード、ソフトウェア、及び／又は、それ以外の方法を示されてない場合にはそのような機能を遂行するようにコード化された集積回路に従って、コンピュータのようなプロセッサ又は電子的データ・プロセッサによって遂行される。

添付図面の図１を参照すると、参照番号１００は、実時間アプリケーションのための改良されたメモリ管理機構を図解する高レベルのブロック図を全体的に指す。この場合、その高レベルのブロック図１００は、仮想メモリを使用したコンピュータ・システムにも適用することが可能である。最新のコンピュータ・システムはこのカテゴリに含まれる。ページ・テーブル１０６に保存されたページ・テーブル・エントリ（ＰＴＥ）（図示されていない）及び変換索引緩衝機構（ＴＬＢ）１０８を使用して、仮想アドレス１０２が実アドレス又は物理アドレス１０４に変換される。詳しく言えば、仮想アドレス１０２は、仮想ページ番号（ＶＰＮ）１０２Ａ及びページ・オフセット１０２Ｂを含む。同様に、実アドレス１０４は、ページ・フレーム番号（ＰＦＮ）１０４Ａ及びページ・オフセット１０４Ｂを含む。仮想アドレス１０２のＶＰＮ１０２Ａだけが実アドレスのＰＦＮ１０４Ａに変換されることが望ましい。ページ・オフセット１０２Ｂは、修正することなくページ・オフセット１０４Ｂにコピーされる。

ＴＬＢミスが存在するとき、又は、ＴＬＢにおけるＰＴＥがページ・テーブル１０６からの新しいＰＴＥ（ミスしたページを含む）でもって置換されなければならないとき、ＴＬＢを援助するためのハードウェア及び／又はソフトウェアのページ置換アルゴリズム（ＰＲＡ）１１０も使用される。実時間アプリケーションのためのメモリ管理機構１００を改良するために、テーブル・ロック機構１１２がＴＬＢ１０８及びＰＲＡ１１０と共に相互作用する。

少なくとも、中央処理装置（ＣＰＵ）（図示されていない）は、別の方法が示されない場合、この関連において必要なほとんどのオペレーション及び／又は計算を直接的に又は間接的に制御する。ＣＰＵに結合されたメモリ（図示されていない）もページ・テーブル１０６を保存している。ＰＲＡ１１０は、それがハードウェアとして実装される場合、ＴＬＢ１０８及びＴＬＢロック機構１１２に結合される。それがソフトウェアとして実装される場合、ＰＲＡ１１０は、メモリ（図示されていない）に保存され、ＴＬＢミスが生じた場合、ＣＰＵによって実行されるであろう。

一般に、ページ・テーブル１０６を保存するメモリに対してＣＰＵがアクセスを得ることは、（ＣＰＵの推測し得る短いクロック・サイクルに比べて）比較的長い期間を必要とする。ＴＬＢ１０８は、当初、ページ・テーブル１０６からの利用可能なＰＴＥの部分を動的に保存するために使用される特別のキャッシュである。特に、ＴＬＢ１０８は、高速アクセスのためにＰＴＥの比較的小さいセットを保存するための連想メモリである。或るフィールドの値が与えられると、連想メモリにおけるハードウェア機構がすべてのレコードをサーチし、その与えられた値を含むフィールドを持ったレコードを戻す。ＶＰＮ１０２Ａが与えられると、ＴＬＢ１０８におけるハードウェア機構は、ＴＬＢにおけるすべてのＰＴＥをサーチし、ＴＬＢミスが存在しない場合にＰＦＮ１０４Ａを戻す。本発明の真意から逸脱することなく、ＴＬＢ１０８の代わりに他のタイプの連想メモリを使用してもよいことに留意してほしい。

一般に、ＴＬＢ１０８は、ＣＰＵが近い将来に使用するかもしれない幾つかのＰＴＥを動的にキャッシュするために使用される。実際に、ＰＲＡ１１０は、ＣＰＵが、近い将来、どのページを使用するかもしれないかを予測し、それに従って、どのＰＴＥが所与の時点にＴＬＢ１０８に保存されるべきかを決定する。現在では、最低使用頻度（ＬＲＵ）アルゴリズム（図示されていない）を含むがそれに限定されない多くの種々のページ置換アルゴリズムがその分野では知られている。ＴＬＢミスが存在するとき、ＬＲＵアルゴリズムは、最も長い期間使用されてなかった（即ち、最近最も使用されていない）ＰＴＥを新しいＰＴＥ（例えば、ＴＬＢにおいてミスしたＰＴＥ）でもって置換する。

このページ置換方式は、メモリ管理機構１００のパフォーマンス全体を徐々に最適化し得るが、その方式は、それが実時間アプリケーションにおいて持ち得る潜在的な悪影響を考慮していない。ＴＬＭロック機構１１２は、ＴＬＢ１０８及びＰＲＡ１１０と共に働くことによってこの問題を克服するために示される。一般に、ＴＬＢロック機構１１２は、実時間アプリケーションに対して割り振られたＰＴＥのセットが、ページ・テーブル１０６に属するＰＴＥの別のセットと置換されないようにする。換言すれば、ＴＬＢロック機構１１２は、ＰＲＡ１１０が何を決定するかに関係なく、実時間アプリケーションに対して割り振られたＰＴＥのセットをロックし、そのＰＴＥのセットがＴＬＢ１０８から排除されないようにする。

本発明が必ずしも実時間アプリケーションに限定されないが、そのようなアプリケーションが本発明から最も利益を受けそうであるということに留意することは重要である。一般に、本発明は、任意のタイプのアプリケーション及び／又は任意の特定のアプリケーションを、ＴＬＢミスの場合に置換されないようにするために適用可能であると考えるべきである。

次に、図２を参照すると、実時間アプリケーションのための改良されたメモリ管理機構の好適な実施例を図示するための低レベルのブロック図２００が示される。一般に、メモリ要求は、ＣＰＵ（図示されていない）から有効アドレス（ＥＡ）２０２の形式で行われる。ＥＡ２０２は仮想アドレス（ＶＡ）２０４に変換され、仮想アドレスは、順次、実アドレス（ＲＡ）２０６に変換される。有効アドレス（ＥＡ）２０２は、有効セグメントＩＤ（ＥＳＩＤ）２０２Ａ、ページ番号（ＰＮ）２０２Ｂ、及びオフセット２０２Ｃを含む。同様に、ＶＡ２０４は、仮想セグメントＩＤ（ＶＳＩＤ）２０４Ａ、ページ番号（ＰＮ）２０４Ｂ、及びオフセット２０４Ｃを有する。なお、ＶＳＩＤ２０４ＡをＰＮ２０４Ｂと連結することによって、仮想ページ番号（ＶＰＮ）２０４Ｄが作成されることが望ましい。

ＥＡ２０２は、セグメント索引バッファ（ＳＬＢ）２０８及び変換索引緩衝機構（ＴＬＢ）２１０に送られる。ＳＬＢ２０８は、ＥＡ２０２をＶＡ２０４に変換するように構成される。なお、ＳＬＢ２０８はＥＳＩＤ２０２ＡをＶＳＩＤ２０４Ａに変換し、一方、ＰＮ２０２Ｂ及びオフセット２０２Ｃは、それぞれ、ＰＮ２０４Ｂ及びオフセット２０４Ｃにコピーされることが望ましい。

ＶＰＮ２０４Ｄ及びＥＡ２０２が与えられると、ＣＰＵは、ＥＡ２０２によりインデックスされたすべてのＰＴＥをアクセスすること及びＶＰＮ２０４Ｄを比較することにより、ページ・テーブル・エントリ（ＰＴＥ）における一致（即ち、ＰＴＥヒット）を求めてＴＬＢ２１０をサーチする。ヒットが存在する場合、実ページ番号（ＲＰＮ）２１２が戻される。なお、そのような比較を行うために、ＴＡＧコンパレータ２１４が論理素子２１６と共に使用されることが望ましい。特に、ＴＡＧコンパレータ２１４は、ＶＰＮ２０４ＤがＴＬＢ２１０におけるＶＰＮ２１８と一致するとき、論理素子２１６がＲＰＮ２１２を通過することを可能にする。ＶＰＮ２０４ＤがＴＬＢ２１０におけるＶＰＮ２１８に一致しないとき、ＴＡＧコンパレータ２１４は、論理素子２１６がＲＰＮ２１２を通過させないようにする。

ＴＬＢミスが存在する場合、ＴＬＢ再ロード機構（図示されていない）がメモリ（図示されていない）におけるページ・テーブル（図示されていない）をサーチし、ＴＬＢ２１０を再ロードする。従来のＴＬＢ構造では、合同クラスにおけるＰＴＥのどのセットが置換されるべきかを表すために、最少使用頻度（ＬＲＵ）アルゴリズム２２０のようなページ置換アルゴリズム（ＰＲＡ）が使用される。

ＴＬＢの再ロードの場合、どのセットが置換されるべきかを選択するために、一組の範囲指定レジスタ２２２、クラスＩＤ、置換セット２２４、置換管理テーブル（ＲＭＴ）２２６、及び置換セット制御ブロック２３０が使用される。特に、範囲指定レジスタ２２２はＲＭＴ２２６に接続され、クラスＩＤをＲＭＴ２２６に送る。ＴＬＢの再ロードは、ＥＡ２０２を範囲指定レジスタ２２２に送ることによって達成される。範囲指定レジスタ２２２においてヒットが存在する場合、クラスＩＤが生成され、ＲＭＴ２２６に送られる。ＲＭＴはＲＭＴ置換制御ビットを生成し、そのＲＭＴ置換生成制御ビットがＲＭＴ置換制御バス２３２を介して置換セット制御ブロック２３０に送られる。置換セット制御ブロック２３０は、ＲＭＴ置換制御ビット及びＴＬＢ２１０からの置換セット２２４を使用して、どのセットを置換すべきかを決定する。

図３は、ＲＭＴ２２６の例を示す。この例では、ＲＭＴ２２６は、８個のＴＬＢセット（列）と交差した８個のクラスＩＤ（行）のマトリクスを含む。なお、ＲＭＴ２２６は、ＴＬＢ２１０内のセットが所与のクラスＩＤに相関するとき、そのセットの置換管理ステータスに関するオペレーティング・システム・ソフトウェアの判断を表すことが望ましい。

好適な実施例では、ＲＭＴ２２６はソフトウェア管理されたテーブルである。ソフトウェアはその構造を維持し、ＲＭＴエントリの意味を解釈する。一般に、ＲＴＭ２２６は、有効アドレスの範囲をＴＬＢの１つ又は複数のセットにマップする場合に使用される。また、クラスＩＤ（即ち、ＴＬＢ２２６の行）は、所与のアドレス範囲を表す。この例では、クラスＩＤ０は、他のクラスＩＤによって明確には提供されない任意のアドレス範囲に対応する。しかる後、その与えられたクラスＩＤが、ＲＭＴに送られ、ＲＭＴによりインデックスとして使用される。そのクラスＩＤをインデックスとして使ってＲＭＴ２２６がアクセスされ、情報がＲＭＴ置換制御バス２３２を介して送られる。

この例では、ＲＭＴ２２６は８ｘ８マトリクスである。換言すれば、ＴＬＢ２１０は８ウェイ・セット・アソシアティブである（即ち、それは８個のセットを有する）。従って、各ＲＭＴエントリは８ビットを有する。特に、ＲＭＴ２２６は、クラスＩＤの行０ではＴＬＢセット０−２から「１」を定義され、その行の残りでは「０」を定義される。従って、クラスＩＤ０に関しては、ＴＬＢに対してデータが置換されるべき場合、それは、最初の３セット、即ち、ＴＬＢのセット０−２において更新可能である。更に、クラスＩＤ０は、これらのセットの排他的使用を有する。従って、クラスＩＤ０に対しては、ＴＬＢのセット０−２は排他的である。クラスＩＤ０は、範囲指定レジスタにおいてヒットしないアドレスに対してデフォルト・クラスＩＤを提供する。

クラスＩＤ１に関しては、ＲＭＴは、セット０−２及びセット４−７において「０」を定義され、セット３に対して「１」を定義される。クラスＩＤ１に対応するいずれのデータもセット０−２又はセット４−７では置換されるべきではない。その代わり、データはセット３において置換されるべきである。クラスＩＤ２及びクラスＩＤ３は、共に、同じセット、即ち、セット７を置換する。従って、クラスＩＤ２及びクラスＩＤ３の両方ともセット７だけを置換すべきである。クラスＩＤ４は、置換に対する有効な候補である幾つかのセットを有する。これらは、セット４、５、及び６である。

セット置換の最終的な選択は、ＬＲＵアルゴリズムのような任意のページ置換アルゴリズム（ＰＲＡ）によって行われる。換言すれば、ＲＭＴによる置換に対して適格なセットがマークされ、しかる後、図２の置換セット選択ブロック２３０に含まれたＬＲＵアルゴリズムの制御ロジック（図示されていない）が使用されて、置換されるべきセットの選択を完成させる。

実時間アプリケーションのための改良されたメモリ管理機構を示す高レベルのブロック図である。 実時間アプリケーションのための改良されたメモリ管理機構の好適な実施例を示す低レベルのブロック図である。 図２の改良されたメモリ管理機構と関連して使用されるべき置換管理テーブル（ＲＭＴ）の一例を示す図である。

Claims (8)

1. 処理ロジック並びに第１及び第２メモリを有するコンピュータ・システムにおいてメモリ管理を改良するための方法であって、
   前記第１メモリにおける仮想アドレス及び実アドレスの間のアドレス変換情報を保存するステップと、
   前記処理ロジックからのより高速のアクセスのために、アドレス変換情報のサブセットを含む前記アドレス変換情報の少なくとも一部分を前記第２メモリに保存するステップであって、前記第２メモリが前記第１メモリよりも前記処理ロジックに近接している、ステップと、
   アドレス変換情報の前記サブセットが、前記第１メモリに保存された他のアドレス変換情報でもって置換されないようにするステップと、
   を含む、方法。
2. 前記第１及び第２メモリが、それぞれ、メイン・メモリ及び前記コンピュータ・システムの変換索引緩衝機構（ＴＬＢ）である、請求項１に記載の方法。
3. 前記アドレス変換情報が、１つ又は複数のページ・テーブル・エントリ（ＰＴＥ）を有する１つ又は複数のページ・テーブルに保存される、請求項１に記載の方法。
4. アドレス変換情報の前記サブセットが実時間アプリケーションに対して割り振られる、請求項１に記載の方法。
5. アドレス変換情報の前記サブセットが、前記第１メモリに保存された他のアドレス変換情報でもって置換されないようにする前記ステップが、更に、
   各々が有効アドレスの所与のアドレス範囲を表す１つ又は複数のクラスＩＤを範囲指定レジスタに対して生成するステップと、
   前記１つ又は複数のクラスＩＤをインデックスとして使用して置換管理テーブル（ＲＭＴ）をアクセスするステップと、
   前記１つ又は複数のクラスＩＤを前記アドレス変換情報の前記少なくとも一部分の１つ又は複数のセットにマップするステップと、
   前記アドレス変換情報のどのセットが置換に対して適格であるかを前記ＲＭＴに基づいて決定するステップと、
   置換に対して適格であると決定された前記アドレス変換情報のセットのみに関して置換アルゴリズムを遂行するステップと、
   を含む、請求項１乃至４のいずれかに記載の方法。
6. 前記処理ロジックから有効アドレスの形でメモリ要求を行うステップと、
   前記有効アドレスに対応した仮想アドレスを生成するステップと、
   前記仮想アドレスを実アドレスに対応させるアドレス変換情報の第１セットを求めて前記第２メモリをサーチするステップと、
   前記第２メモリがアドレス変換情報の前記第１セットを保存していないということを決定するとき、アドレス変換情報の前記第１セットを求めて前記第１メモリをサーチするステップと、
   前記第１メモリがアドレス変換情報の前記第１セットを保存しているということを決定するとき、前記第１メモリにおけるアドレス変換情報の第２セットを置換するためにアドレス変換情報の前記第１セットを前記第２メモリ上にロードするステップであって、アドレス変換情報の前記第２セットが実時間アプリケーションに対して割り振られていない、ステップと、
   を更に含む、請求項１乃至５のいずれかに記載の方法。
7. 処理ロジック並びに第１及び第２メモリを有するコンピュータ・システムにおけるメモリ管理機構であって、請求項１乃至６のいずれかに記載の方法を実行する、メモリ管理機構。
8. 処理ロジック並びに第１及び第２メモリを有するコンピュータ・システムにおけるメモリ管理を改良するためのコンピュータ・プログラムであって、具体化されたコンピュータ・プログラムを持った媒体を有し、コンピュータ・システムにおいて稼動するとき請求項１乃至６のいずれかに記載の方法を実行する、コンピュータ・プログラム。

Images