(57)【特許請求の範囲】
【請求項１】
ページテーブルの所定のページテーブルエントリ値を検索する検索処理を停止する必要なしに、前記ページテーブルの現在のページテーブルエントリ値を削除あるいは移動するページテーブルの更新方法であって、
（ａ）現在のページテーブルエントリ値が所定のページテーブルエントリ値であるか判定する工程と、
（ｂ）現在のページテーブルエントリの値が所定のページテーブルエントリ値でない場合、現在のページテーブルエントリ値を削除あるいは移動する工程と、
（ｃ）現在のページテーブルエントリ値が所定のページテーブルエントリ値である場合、現在のページテーブルエントリ値の削除あるいは移動以前に、前記検索処理が所定のページテーブルエントリ値の検索を完了するまで待機する工程とを備えることを特徴とするページテーブルの更新方法。
【請求項２】
前記ページテーブルは逆ページテーブルあるいはハッシュページテーブルであることを特徴とする請求項１に記載のページテーブルの更新方法。
【請求項３】
現在のページテーブルエントリ値を移動する工程は、更に、現在のページテーブルエントリ値を、現在のページテーブルの位置から宛て先ページテーブル位置へと複写する工程と、現在のページテーブルエントリ値を現在のページテーブル位置から削除する工程を含むことを特徴とする請求項１に記載のページテーブルの更新方法。
【請求項４】
前記ページテーブルはランダムアクセスメモリ（ＲＡＭ）に格納されることを特徴とする請求項１に記載のページテーブルの更新方法。
【請求項５】
前記ページテーブルは二次記憶に格納されることを特徴とする請求項１に記載のページテーブルの更新方法。
【請求項６】
ページテーブルの所定のページテーブルエントリ値を検索する検索処理を停止する必要なしに、前記ページテーブルの現在のページテーブルエントリ値を削除あるいは移動するページテーブルの更新装置であって、
（ａ）現在のページテーブルエントリ値が所定のページテーブルエントリ値であるか判定する手段と、
（ｂ）現在のページテーブルエントリの値が所定のページテーブルエントリ値でない場合、現在のページテーブルエントリ値を削除あるいは移動する手段と、
（ｃ）現在のページテーブルエントリ値が所定のページテーブルエントリ値である場合、現在のページテーブルエントリ値の削除あるいは移動以前に、前記検索処理が所定のページテーブルエントリ値の検索を完了するまで待機する手段とを備えることを特徴とするページテーブルの更新装置。
【請求項７】
前記ページテーブルは逆ページテーブルあるいはハッシュページテーブルであることを特徴とする請求項６に記載の装置。
【請求項８】
現在のページテーブルエントリ値を移動する手段は、更に、現在のページテーブルエントリ値を、現在のページテーブルの位置から宛て先ページテーブル位置へと複写する手段と、現在のページテーブルエントリ値を現在のページテーブル位置から削除する手段を含むことを特徴とする請求項６に記載の装置。
【請求項９】
前記ページテーブルはランダムアクセスメモリ（ＲＡＭ）に格納されることを特徴とする請求項６に記載の装置。
【請求項１０】
前記ページテーブルは二次記憶に格納されることを特徴とする請求項６に記載の装置。
【請求項１１】
コンピュータシステムに、ページテーブルの所定のページテーブルエントリ値を検索する検索処理を停止する必要なしに、前記ページテーブルの現在のページテーブルエントリ値を削除あるいは移動させるためのコンピュータプログラムが記録されたコンピュータ可読の記憶媒体であって、
前記コンピュータプログラムは、前記コンピュータシステムを、
現在のページテーブルエントリ値が所定のページテーブルエントリ値であるか判定する手段と、
現在のページテーブルエントリ値が所定のページテーブルエントリ値でない場合、現在のページテーブルエントリ値を削除あるいは移動する手段と、
現在のページテーブルエントリ値が所定のページテーブルエントリ値である場合、現在のページテーブルエントリ値の削除あるいは移動以前に、前記検索処理が所定のページテーブルエントリ値の検索を完了するまで待機する手段と
して機能させるためのものであることを特徴とする記憶媒体。
【請求項１２】
前記ページテーブルは逆ページテーブルあるいはハッシュページテーブルであることを特徴とする請求項１１に記載の記憶媒体。
【請求項１３】
現在のページテーブルエントリ値を移動する手段は、更に、現在のページテーブルエントリ値を、現在のページテーブルの位置から宛て先ページテーブル位置へと複写する手段と、現在のページテーブルエントリ値を現在のページテーブル位置から削除する手段を含むことを特徴とする請求項１１に記載の記憶媒体。
【請求項１４】
前記ページテーブルはランダムアクセスメモリ（ＲＡＭ）に格納されることを特徴とする請求項１１に記載の記憶媒体。
【請求項１５】
前記ページテーブルは二次記憶に格納されることを特徴とする請求項１１に記載の記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータを使用したシステムにおける仮想メモリ管理方法に関り、特にコンピュータ使用したシステムのためのメモリアクセスの仮想−物理マッピングに関する。
【０００２】
【従来の技術】
最近のプロセッサは、通常は、仮想アドレスから物理アドレスへのマッピングをハードウエアにより実行することで、仮想メモリシステムをハードウエアによりサポートしている。仮想メモリアドレス空間と物理メモリアドレス空間はともに、所定サイズ、しばしば４Ｋバイトのサイズの「ページ」の集積と考えることができる。現在の仮想アドレス空間で定義された仮想メモリページと物理メモリページとの間のマッピングの集合は、通常「ページテーブル」と呼ばれるデータ構造に格納される。通常、ページテーブルのエントリは、更に、アクセス保護情報と、ソフトウエアにより保持されるフラグや参照される計数などのその他の情報を含んでいる。そのページテーブル情報は各メモリの参照のほとんどに用いられるため、非常に頻繁にアクセスされる。あいにく、ページテーブルは、通常、中央処理装置（ＣＰＵ）内にオンチップで格納するには大きすぎる。そのかわりに、ＣＰＵが最近利用したページテーブルエントリが変換ルックアサイドバッファ（translation lookaside buffer:TLB)によってキャッシュされるのが常である。
【０００３】
仮想メモリアドレスで参照が行われた場合、ほとんどのマッピングはＴＬＢ検索により直ちに行われる。もし所望のエントリがＴＬＢに見いだせなかったなら（しばしばＴＬＢミスと呼ばれる）、要求された情報を取得するためにページテーブル検索が遂行される。さらに、もし所望のエントリが主記憶（例えば半導体ＲＡＭ）内のページテーブル内にも置かれていないならば、「ページフォルト」が発生し、適切な物理メモリページが、例えばハードディスクなどの二次記憶システム上に見つけだされ、その後のＣＰＵによる直接アクセスのために主記憶にロードされる。そして、物理メモリページのための適切なページテーブルエントリがページテーブルにロードされ、そこで所望のエントリが利用できる。複数のプロセッサがページテーブルにアクセスできるマルチプロセッサシステムでは、第２のプロセッサからのページテーブルの検索が進行している間に、第１のプロセッサはページテーブルを更新しようとすることができる。その結果、衝突の可能性がある。この衝突の可能性を解消するための機構が通常は要求され、あるいは適所に設置される。
【０００４】
仮想メモリアドレスの一部を用いてページテーブルを直接指し示めすには、ページテーブルが、仮想ページ番号から指し示めせるのと同じくらいの大きさであることが必要である。例えば、仮想メモリアドレスの上位２０ビットが仮想ページ番号として用いられているとすると、１メガページ（1,048,576ページ）まで指し示すことができる。１００万を越える仮想ページを収容するページテーブルは、メモリのかなりの部分を占有する。それぞれ関連づけられたページテーブルを有するいくつものアプリケーションが走るコンピュータシステムでは、ページテーブルの総数は、このように物理メモリのほとんどの部分を占有する。それゆえにページテーブルのサイズを縮小することが望まれる。
【０００５】
ページテーブルのサイズを縮小するために、幾つかの技術を利用できる。このような技術のひとつでは、ページテーブルのサイズを所定サイズに限定し、仮想ページ番号により指し示されるエントリの要求がページテーブルの範囲外であるなら、その要求のためにひとつのエントリがページテーブルに作成される。この方法により、ページテーブルは、仮想ページ番号によりアドレスできるのと同じサイズで生成されるのではなく、必要なサイズへと増大（あるいは成長）する。
【０００６】
ページテーブルのサイズを縮小するもう一つの技術は、主記憶の物理記憶ページをアドレスする、より小さなページテーブル構造を指し示すのに利用されている、より小さな、ハッシングされたインデックス値へと仮想ページ番号を縮小する方法で、仮想ページ番号に「ハッシング関数」を適用することである。
【０００７】
ハッシング関数を適用する技術によりもたらされるより小さなページテーブルは、「逆ページテーブル」あるいは「ハッシングされたページテーブル」として頻繁に参照される。ハッシング関数は、通常、仮想メモリシステム内のほとんど全ての仮想ページ番号を、ハッシングされたインデックス値とここでは呼ばれる、より小さな、値の部分集合へとマッピングする。
【０００８】
その結果、仮想ページ番号へのハッシング関数の適用により、ひとつのハッシングされたインデックス値に複数の仮想ページ番号が一致することが起こり得る。結果として、逆ページテーブルの検索において、現在の仮想アドレスがハッシングされて（すなわちハッシュ関数が適用されて）ある仮想アドレスを有する逆ページテーブルエントリを指し示すのに利用されているハッシングされたインデックス値が得られた場合に「ハッシュの衝突」が生じ、その仮想アドレスは現在の仮想アドレスに一致しない。
【０００９】
同様に、逆ページテーブルに新たなエントリを追加するとき、現在の仮想アドレスがハッシングされて、有効なエントリ（すなわち、後述する有効フラグがセットされたエントリ）により現在占有されている逆ページテーブルのエントリを指し示しているハッシングされたインデックス値が得られた場合、「ハッシュの衝突」が生じる。
【００１０】
【発明が解決しようとする課題】
システムのプロセッサ（あるいはコプロセッサ）が、ＴＬＢミスのためにページテーブルの検索をしようとするのと同時に、システムソフトウエアがページテーブルを更新しようとすると、衝突が生じる。この衝突の解決方法のひとつは、ページテーブルが更新されている間は、ページテーブルの検索を締め出すことによりページテーブルの検索を防止することである。けれども、この方法でページテーブルをロックすることは、性能面において不利である。
【００１１】
上述した衝突は、マルチプロセッサシステムにも（マルチプロセッサはいつでもページテーブルの検索を行えるので）、単一のプロセッサシステムにも（ページテーブル検索は基本的な操作なので、ページテーブル自身を更新する特権的なオペレーティングシステムコードを実行している間にさえも検索は行われ得るため）共通している。
【００１２】
例えば、グラフィックコプロセッサを用いたシステムは、本質的にマルチプロセッサシステムである。さらに、ページテーブルのアクセスに関してマルチプロセッサの同期が必要とされることは、同期処理中にグラフィックコプロセッサが停止される必要があるかもしれず、実際上画像処理が遅くなるため望ましくない。
【００１３】
本発明は上記従来例に鑑みてなされたもので、ページテーブルの検索を中止することなくページテーブルエントリの移動あるいは削除を行うことができ、処理を停滞させず、効率的に仮想メモリ管理にかかる処理を実行することができるページメモリ更新方法および装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記目的を達成するために、本発明の一態様によれば、ページテーブルの所定のページテーブルエントリ値を検索する検索処理を停止する必要なしに、前記ページテーブルの現在のページテーブルエントリ値を削除あるいは移動するページテーブルの更新方法であって、（ａ）現在のページテーブルエントリ値が所定のページテーブルエントリ値であるか判定する工程と、（ｂ）現在のページテーブルエントリ値が所定のページテーブルエントリ値でない場合、現在のページテーブルエントリ値を削除あるいは移動する工程と、（ｃ）現在のページテーブルエントリ値が所定のページテーブルエントリ値である場合、現在のページテーブルエントリ値の削除あるいは移動以前に、前記検索処理が所定のページテーブルエントリ値の検索を完了するまで待機する工程とを備える。
【００１７】
あるいは、他の実施態様によれば、コンピュータシステムに、ページテーブルの所定のページテーブルエントリ値を検索する検索処理を停止する必要なしに、前記ページテーブルの現在のページテーブルエントリ値を削除あるいは移動させるためのコンピュータプログラムが記録されたコンピュータ可読の記憶媒体であって、前記コンピュータプログラムは、前記コンピュータシステムを、現在のページテーブルエントリ値が所定のページテーブルエントリ値であるか判定する手段と、現在のページテーブルエントリ値が所定のページテーブルエントリ値でない場合、現在のページテーブルエントリ値を削除あるいは移動する手段と、現在のページテーブルエントリ値が所定のページテーブルエントリ値である場合、現在のページテーブルエントリ値の削除あるいは移動以前に、前記検索処理が所定のページテーブルエントリ値の検索を完了するまで待機する手段として機能させるためのものである。
【００２０】
【発明の実施の態様】
図１は、メモリ管理ユニット（ＭＭＵ）９０の主要構成要素を示している。メモリ管理ユニット（ＭＭＵ）９０は、仮想メモリアドレスを受け取る入力手段９１と、変換ルックアサイドバッファ９２（ＴＬＢ）と、物理メモリアドレスを出力する出力手段９３と、図３を参照して後述する通り、仮想−物理メモリマップの検索に適合したページテーブル検索手段９４とを含む。
【００２１】
ページテーブル検索手段９４は、ページテーブル（本明細書で説明する）へのインデックスを提供するために仮想メモリアドレスの少なくとも一部の操作に適合したハッシュ関数手段９５を含んでいる。ページテーブルは、コンピュータシステムのランダムアクセスメモリ（ＲＡＭ）９６に格納されるのが望ましい。あるいは、ページテーブルは、ハードディスクのような二次記憶装置に格納されてもよい。この場合、ページテーブルは、コンピュータシステムに要求されるとＲＡＭ９６にロードされる。
【００２２】
図２において、逆ページテーブル、あるいはハッシングされたページテーブル１００（ここではページテーブルと呼ぶ）は、２ワード（通常は１ワード３２ビット）を含む複数のページテーブルエントリ１０１とともに示されている。２つの３２ビットワードの一番目のワード１０２は物理メモリページ番号１０３を含んでおり、物理ページ番号１０３は、不図示のページオフセット番号とともにコンピュータシステムのメモリ（多くの場合ＲＡＭ）に格納された所望のデータ値への物理メモリアドレスを形成する。この例では、物理メモリページ番号１０３は、この実施形態の例である３２ビットワードよりも小さいため、残りのビットは予備ビット１０４としてたいてい空けておかれる。２つの３２ビットワードのうちの二番目のワード１０５は、仮想メモリページ番号１０６と、予備ビット部１０７と、読みだし専用フラグ１０８と、有効フラグ１０９とを含んでいる。例えば、読みだし専用フラグ１０８や有効フラグ１０９といったフラグは、値１（セット）あるいは０（アンセット）を取り得る単一のビットでよい。読みだし専用フラグ１０８（その一例としては、アドレスアクセス保護情報フラグ）は、それがセットされている場合に、ページテーブルエントリ１０１により指し示される物理メモリ内のデータを上書きしてはならないことを示している。有効フラグ１０９は、物理ページ番号と仮想ページ番号がページテーブル１００の有効なエントリであるかどうかを示している。有効フラグ１０９のセットおよびアンセットにより、ページテーブル検索には３つの出力がありえる。よって、有効フラグは、例示された方法によって最も適切に説明される。
【００２３】
図８を参照すると、ページテーブル検索処理７００が示されている。ページテーブル検索処理は、入口７０２の後に、ステップ７０４において与えられたアドレスからハッシュインデックス(i)を作成し、これによりページテーブルエントリ１０１を示している。ステップ７０６で判定されたときにページテーブルエントリ１０１の有効フラグ１０９がアンセットされており、ページテーブルエントリ１０１がページテーブルの検索結果としてアクセスされると、ステップ７０８に示すように、この後説明する「ページフォルト」が発生する。一方、有効フラグ１０９がセットされ、ページテーブルエントリ１０１がページテーブルの検索結果としてアクセスされると、ページテーブルエントリ１０１の仮想メモリページ番号１０６がページテーブルの検索に用いられた仮想メモリアドレスの仮想ページ番号とステップ７１０で比較される。その仮想メモリアドレスは、仮想メモリアドレスから物理メモリアドレスへのマッピングが求められたところの所望の仮想メモリアドレスである（仮想−物理マップは仮想ページ番号と物理ページ番号とを含む番号の対である）。比較の結果、もしページテーブルエントリ１０１の仮想ページ番号１０６が所望の仮想メモリアドレスの仮想ページ番号に一致していなければ、ページテーブルエントリ１０１へのインデックス(i)は(i+1)になるようステップ７１２で進められ、その後のエントリが系統立って検索され、ページテーブルエントリにそれぞれ対応する仮想ページ番号は、前記所望の仮想ページ番号と一致するまで、あるいはアンセットされた有効フラグを有するページテーブルエントリが見つかるまで比較される。所望の仮想ページ番号がページテーブルエントリ１０１に見いだせない場合には、物理メモリアドレスが戻される（７１４）。けれども、ページテーブルの検索時、もしアンセットされた有効フラグを有するページテーブルエントリ１０１が最初に見つかったなら、ページフォルトが発生する。
【００２４】
最近の最新のコンピュータシステムにおいては、メモリ管理ユニットは通常「変換ルックアサイドバッファ」（ＴＬＢ）を備えている。変換ルックアサイドテーブルは、仮想アドレスから物理アドレスへのマッピングのテーブルであり、たいてい、ページテーブルの最近使用されたエントリの、通常は小さなサイズのテーブルである。各ＴＬＢのエントリは、ページテーブルエントリとほとんど同じ情報を含んでおり、ＴＬＢは実質的に、最も最近使用されたページテーブルエントリの部分集合である。たいてい、ＴＬＢはページテーブルエントリに含まれているのとほとんど同じアドレス保護情報を含んでいる。ＴＬＢは、いずれかの仮想−物理アドレス変換に対するハードウエアシステム要求の必要に応じてしばしば更新される。ＴＬＢは通常、ハードウエアシステムが仮想−物理アドレス変換を要求したときに検索される最初のテーブルである。ＴＬＢはページテーブルに含まれる仮想−物理マップの全エントリの部分集合であるから、時には所望の仮想−物理メモリマップに対するハードウエアによる要求はＴＬＢ内には見いだせず、結果として、ページテーブル検索が開始される。ＴＬＢ内に所望の仮想−物理マップが見つけられない場合、すなわち、もし、有効フラグがセットされた、所望の仮想ページ番号と一致する仮想ページ番号を含むＴＬＢのエントリがなければ、「ＴＬＢミス」が発生し、ページテーブル検索が開始される。
【００２５】
ＴＬＢミスから生じるページテーブル検索を図３を参照して説明する。図８のフローチャートはまた、比較できる工程の要点を説明するものだが、後述する詳細全てを含むものではない。ページテーブル検索において、仮想−物理マッピングが検索された（すなわち仮想メモリアドレスに対応する物理メモリアドレスが検索された）ところの仮想メモリアドレスからの仮想ページ番号２００は、ＴＬＢ中では見つからず、仮想ページ番号２００は「ハッシュ」関数２０１の処理を施される。この、仮想ページ番号２００に適用されたハッシュ関数２０１の出力を、ページテーブルエントリの識別に用いられるハッシュインデックス値２０２と呼ぶ。この例では、一つのページテーブルエントリ（すなわちひとつのページテーブルアドレス）にアドレス２０５を提供するために、ページテーブルアドレス２０５は、ポインタベースアドレス値２０４を最上位のビット群とし、ハッシュインデックス値２０２を中間のビット群とし、３つのヌルビット２０８（すなわち０００）を最下位のビット群としてつなぎあわせることで構成される。最下位ビット群として連結される３つのヌルビット２０８により、ページテーブルアドレス２０５は、ページテーブルエントリのバイトアドレスとして利用できる。
【００２６】
ページテーブルエントリ１０１は、現在のページテーブルアドレス２０５により指し示されるアドレスから始めて、好ましくは一度に１ワードずつ読み出される。ページテーブルエントリ１０１の仮想メモリページ番号１０６は、ＴＬＢミスをもたらした仮想ページ番号２００と比較される（２０９）。もしページ番号（１０６，２００）が等しければ、すなわち、一致するページ番号（１０６，２００）が見つかったなら、ページテーブルエントリ１０１はＴＬＢに書き込まれる。その後の、仮想ページ番号２００についてのＴＬＢの検索はＴＬＢミスを引き起こさないであろう。ページ番号（１０６，２００）が等しくない（すなわち「ハッシュ衝突」が生じた）場合、現在のハッシュインデックス値２０５は、次のページテーブルエントリまでくり返しインクリメントされ（２０３）、次のページテーブルエントリの各々の仮想ページ番号は所望の仮想ページ番号２００と比較される（２０９）。ハッシュインデックス値２０５は、比較ステップ２０９が一致する仮想ページ番号１０６，２００を見いだすまで、あるいはアンセットされた有効フラグを有するページテーブルエントリ１０１にぶつかるまでインクリメント（２０３）できる。一致する仮想ページ番号が見つかった場合、一致する仮想ページ番号１０６を有するページテーブルエントリ１０１の対応する物理アドレス１０３はＴＬＢに送られる。対応する物理アドレス１０３はＴＬＢに書き込まれ、ＴＬＢ中の必要とされる仮想−物理変換に提供するため、所望の仮想ページ番号２００に関連づけられる。
【００２７】
必要なら、インクリメントにより、所望の一致が見いだされないままページテーブルの最後のエントリに達した場合、インクリメントしながらの所望の一致の検索は、ページテーブルの先頭から開始される。したがって、どこが始まりであっても、望んでいる一致を見つけるか、あるいはアンセットされたフラグを有するエントリにぶつかるまで「ひとまわり（wrapping-around）」される。ページテーブルエントリの有効フラグ１０９は比較２０９の前にチェックされ、もし有効フラグ１０９がアンセットされていればページフォルトが生じ、その結果ページテーブル検索が終了する。ページテーブルの検索はページテーブルの末尾からページテーブルの先頭へとひとまわりすることができるため、所望のページテーブルエントリが見つからなくとも検索が終了することを保証するために、少なくとも１つのページテーブルエントリが、アンセットされた有効フラグを通常は保持している。同様に、ページテーブルエントリが更新あるいは削除あるいは現在のページテーブル位置からそのページテーブルの他の位置に移動されるであろう場合、複数のページテーブルエントリ１０１のいずれを更新あるい削除あるいは移動するか決定するために、ほとんど図３を参照して説明したようにページテーブル検索が遂行される。
【００２８】
アンセットされた有効フラグ１０７が、現在、ページフォルトを示すものではなく、ページテーブルエントリが挿入（あるいは上書き）される可能性があることを示すものであっても、ページテーブルの挿入、すなわちページテーブルに挿入あるいは追加されたページテーブルエントリは、ページテーブル検索に関してほとんど上述した方法で遂行される。また、ページテーブルの挿入は必ずしもＴＬＢミスの結果ではなく、ページテーブルを挿入あるいは増やすというハードウエアあるいはソフトウエアによる特定の要求である。この説明は、入口８０２を有する処理８００として図９に示されている。ハッシュインデックス値(i)は、ＴＬＢ中の仮想ページ番号を供給するためにステップ８０４で生成される。ステップ８０６においては、そのインデックスは検討され、ＴＬＢミスが発生すると、ステップ８０８で、仮想アドレスを前記インデックスの仮想アドレスとしてセットし、そうして挿入が遂行される。ページテーブルエントリの最初のワード１０２（物理メモリアドレスを含む）は、システムソフトウエアあるいはハードウエアが完全に更新を完了する前にページテーブルエントリが使用されることを防止するために、第２のワード１０３（仮想メモリアドレスを含む）以前に更新あるいは挿入されることが望ましい。ステップ８０６で有効なインデックスであれば、ＴＬＢは「ヒット」し、ステップ８１０でその仮想アドレスを挿入のために与えられた仮想アドレスと比較する。等しければ、ステップ８０８が、挿入を遂行するために再び呼び出される。等しくなければ、ステップ８１２は、インデックスをインクリメントし、制御をステップ８０６に戻す。
【００２９】
図４乃至図６に関する説明は、ページテーブルエントリをページテーブルから取り除く、ページテーブルエントリの削除の一例である。ページテーブルエントリを除去あるいは削除するために、有効フラグを「アンセット」にすることのみが必要とされる。これは、現在の位置にあるページテーブルエントリが上書き可能であることを示している。
【００３０】
ページテーブル検索（上述）については、ハッシュの衝突が生じた場合、所望の仮想ページ番号と一致する仮想ページ番号を有する次のページテーブルエントリが検索されるか、あるいはページテーブルエントリの挿入においては（これも上述した）、ハッシュの衝突が生じると、アンセットされた有効フラグを有するページテーブルエントリが見つかるまでハッシュインデックス値２０２をインクリメントすることで、次の利用可能な位置が検索される。それゆえ、削除あるいは除去されるべきエントリは、ハッシングされたアドレス（すなわちハッシュ関数の適用により得られるページテーブルアドレス２０５）にはなく、ハッシングされたアドレスにより参照される位置以外のページテーブルエントリの位置にある可能性がある。
【００３１】
図４において、便宜的に「スロット」と呼ばれる、ページテーブルエントリ位置３０１を有するページテーブル３００は「０」から「ｎ」まで番号付けされており、ページテーブルアドレス値「０」から「ｎ」を有するページテーブル３００に対する「ｎ＋１」個の登録位置を示している。複数のスロット３０１には「フリー」と印されており、これは、これらスロットにおけるページテーブルエントリがアンセットされた有効フラグを有しており、そのページテーブルのスロットはページテーブルエントリを自由に挿入できることを示している。
【００３２】
この例では、ページテーブルアドレス値「０」は「スロット０」に対応しており、ページテーブルアドレス値「１」は「スロット１」に対応し、ページテーブルアドレス値「ｎ」は「スロットｎ」に対応している。それゆえ、例えばページテーブルの挿入時に、「スロット２」３０２に挿入できるのであれば（すなわち有効フラグがアンセットであれば）、ハッシュアドレス値「２」のページテーブルエントリは「スロット２」３０２に挿入されることが望ましい。しかしながら、「スロット２」でハッシュの衝突が生じたなら、すなわち有効フラグがセットされているなら、ページテーブルエントリは次の利用可能な「スロット」に挿入される。図４のページテーブルは、「スロット２」と「スロット３」とにおいて同一の２つのハッシュテーブルアドレス値を示している。これは、ページテーブルの挿入時にハッシュの衝突が生じたこと、および、第１のページテーブルエントリは、ハッシュ関数の実行後にハッシュアドレスが２（図中のハッシュ値＝２）となった仮想ページアドレスを有し、その結果第１のページテーブルエントリが「スロット２」に挿入されたことを示している。その後、それもハッシュアドレス２を有する第２のページテーブルエントリは、「スロット２」が第１のページテーブルエントリに使用されている（有効フラグがセットされている）ためにハッシュの衝突を引き起こした。そのため、第２のページテーブルエントリは、次の利用可能なスロットに挿入され、それがたまたま「スロット３」である。ハッシュアドレス値３に対応する第３のページテーブルエントリは次に利用可能なスロット（スロット４）に挿入され、このようにして続いていく。けれども、ハッシュアドレス値に対応するスロットが利用できれば、対応するスロットが望ましい（例えば、ハッシュアドレス９は、挿入要求されたときに利用可能であった「スロット９」に挿入される）。
【００３３】
次に図５において、図４のページテーブルから「スロット３」３０３のページテーブルエントリを削除あるいは除去したいものとする。このエントリを削除するために、「スロット３」３０３内のページテーブルエントリのための有効フラグが「セット」から「アンセット」に変更され、そのためにスロット３は自由に上書きできる（すなわちフリーとなる）。しかしながら、既に説明した通り、ページテーブルエントリのアンセットされた有効フラグは、ページテーブルの検索を終了させることができる。そのため、ハッシュ衝突によって高い「スロット番号」に挿入された「スロット３」より大きいスロット中のページテーブルエントリは、通常「フリー」３０５と印された最初のスロットまで、本例のページテーブル３００では移動される。ページテーブルエントリは、各ハッシュアドレス値が望ましいスロットに対応するような方法で移動されることが望ましい。例えば、図６は、図４の「スロット３」のページテーブルエントリの除去（削除）後の、図４のページテーブルエントリの望ましい配置を示している。すなわち、図４における、ハッシュアドレス値が３の「スロット４」３０６のページテーブルエントリは「スロット３」に移され、「スロット６」３０７のページテーブルエントリは「スロット４」に移されて、その結果図６の配置となる。
【００３４】
ページテーブルエントリは、通常、ページテーブルエントリ上の更新操作（例えば移動操作）のためにマルチプルアクセスの必要がある。そのため、ページテーブルは、ページテーブルの検索が進行中であり、まだページテーブルが自動的に（すなわち即座に）更新できない場合にも、ほとんどいつも首尾一貫していなければならない。その結果、更新操作がページテーブルエントリ上で行われている間に進行中のページテーブルの検索によって、ページテーブルエントリを見つけることができないかもしれない。また、システムソフトウエアあるいはハードウエアは、ページテーブルが更新されている間に、そのページテーブルにアクセスできることが望ましい。
【００３５】
その結果、図５に例示したように、ページテーブルエントリが第１のスロットから第２のスロット（宛て先スロット）に移されるであろう以前に、宛て先スロットに対応するハッシュ値を提供する仮想アドレスは、未使用のアドレス（すなわち、ページテーブルではほかに決して現れることのないであろう仮想アドレス）に変更される。それにより、宛て先スロット上のページテーブルの検索は、ページテーブルエントリが、殊にページテーブルエントリの物理アドレスが宛て先スロットに書き込まれている間には、試みられることはない。
【００３６】
ページテーブルエントリの移動が指示された宛て先スロットに存在しているページテーブルエントリを用いたページテーブル検索の防止のため、「未使用アドレス」を用いる代案は、ページテーブルの全ページテーブルエントリにアクセス保護フラグを追加して更に持たせることである。追加されたアクセス保護フラグにより、現在のページテーブルエントリについてセットされている場合には、ページテーブル検索処理は現在のページテーブルエントリを無視し、進行中のページテーブル検索を続行することができる。
【００３７】
現在のページテーブルエントリがくり上げられた場合、宛て先スロットの仮想アドレスが未使用に変更される（すなわち、ページテーブルエントリが移動されている間）か、あるいはページテーブルエントリの有効フラグがアンセットされるであろうときに、現在のページテーブルエントリ上のページテーブル検索が進行中でないことをＭＭＵ９０が知っていることが望ましい。一つの移動されているエントリ上でのページテーブル検索が同時に起こることはまれであるけれども、移動されている現在のページテーブルエントリに対してページテーブル検索が遂行されているならば、現在のエントリの検索は、現在のページテーブルエントリが移動される前に完了する。これは図７に示されている。図示のとおり、他のページテーブルエントリ位置（スロット）６０２に移動されるページテーブルエントリ６０１があり、ページテーブル検索６０３がページテーブルエントリ６０１に向かって進行してそれを検索する間に、そのページテーブルエントリの検索はページテーブルエントリ６０１が移動される前に完了させることができる。ページテーブルの検索が成功する（すなわち検索によってページフォルトが起こらない）と、その後ページテーブルエントリがＴＬＢ中で更新され、そのため、上述したように、ごく近い将来における同一のページテーブルエントリへのアクセスの必要性は相当小さくなる。ページテーブルエントリは、その上でのページテーブル検索が成功した後、移動される見込みが高い。その見込みは、ページテーブルエントリの移動が行われている間には、同一のエントリのページテーブル検索が当面行われないであろうという見込みである。
【００３８】
本発明のもう一つの実施例においては、ページテーブルエントリの削除はほとんど上述通りであるが、まさに第１のページテーブルエントリ位置（第１のスロット）から第２のページテーブルエントリ位置（第２のスロット）へ移動されようとしているひとつのページテーブルエントリ上のページテーブル検索が同時発生した場合には、そのページテーブルエントリの移動の完了は、ページテーブル検索の完了にかかる、所定の、考えられる最も長い時間遅延される。通常、ページテーブルエントリの移動操作は、第１のページテーブルエントリを第１のスロットから削除する工程と、第２のページテーブルエントリを第２のスロットから第１のスロットに複写する工程と、第２のページテーブルエントリを削除する工程とを含み、それによって第２のページテーブルエントリを第２のスロットから第１のスロットへ実際上移動する。
【００３９】
図４〜図７で説明した処理は、図１０に示された処理９００により要約される。除去あるいは削除は入口９０２から開始される。ステップ９０４で、ハッシュテーブルのインデックス値(i)に対するエントリの所在が突き止められる。これが終えると、ステップ９０６では、そのエントリの仮想アドレスを無効値にセットする。そしてステップ９０８では、エントリ(i)を使用するもう一つのエントリ(j)を求めてページテーブルを更に検索させる。そのようなエントリがないとステップ９１０で判断されたなら、インデックス(i)におけるそのエントリの有効フラグはクリアされ、削除が完了する。このようなエントリがあれば、インデックス(j)のエントリは、ステップ９１４でインデックス(i)に複写される。それから待機ステップ９１６に入り、ＭＭＵ９０は同時進行のページテーブル検索ができる。検索に必要な最大時間が満了したとき、ステップ９１８では、インデックス(i)を(ｊ)の現在値にセットし、ステップ９０６に制御を戻す。
【００４０】
上述した各実施例では、ページテーブルエントリが削除（あるいは除去）される場合、対応するＴＬＢのエントリは、ＭＭＵ９０がＴＬＢを介して削除されたページテーブルエントリにアクセスすることを防止するために無効化されねばなない。ＴＬＢのエントリを無効化するために、無効化されるＴＬＢの各エントリの有効フラグはアンセットされ、それゆえに無効化されたＴＬＢエントリのＴＬＢ位置は、その後に上書きされるようフリーとなっている。普通、すべてのページテーブルエントリが除去されるか、あるいはページテーブルが物理メモリに再配置される場合、すべてのＴＬＢエントリは、ＴＬＢのエントリ全ての有効フラグをアンセットする無効化サイクルによって無効化される。
【００４１】
好適な実施例（オプション１）およびその他の実施例（オプション２）のためのページテーブルエントリ削除の擬似コードを、付録として添付した。この付録は、ＩＢＭ ＰＣ／ＡＴデバイスといったコンピュータシステムやその互換機だけでなく、その他のコンピュータシステムで動作できる好適な実施例を示している。通常、本好適な実施例は、ディスク装置やテープあるいはインターネットのようなコンピュータネットワークから供給されるであろうソフトウエアによって実施される。
【００４２】
以上、本発明の好適な実施例を説明したが、当業者は本発明の範囲を逸脱することなく変形することは容易である。
＜付録＞
この付録は、本発明の好適な（オプション１）およびその他の（オプション２）実施例のためのページテーブル削除処理の擬似コードを提供する。
（擬似コード）
ハッシュ関数をページテーブルエントリに対応する仮想ページアドレスに適用し、ページテーブル中のエントリを検索する；
do
ページテーブルエントリ（第１のページテーブルエントリ）が削除されるスロットをハッシュする仮想アドレスを検索する
if      見つかった場合
削除されるページテーブルエントリの仮想アドレスを許容されていないアドレスにセットする。そうすればＭＭＵはこのエントリ（第１のページテーブルエントリ）をスキップする第２のページテーブルエントリの物理アドレスを第１のページテーブルエントリの対応する位置に複写する（すなわち上書きする）
第２のページテーブルエントリの仮想アドレスおよび有効フラグビットを、第１のページテーブルエントリの対応する位置に複写する（すなわち上書きする）
if      （オプション１）ＭＭＵが、第２のページテーブルエントリにおいて参照される仮想アドレス上で現在検索を行っている場合
then 待機する
（オプション１）until ＭＭＵが検索を完了する
fi
（オプション２）until 検索にかかると考えられる最も長い時間
次のくり返しループで第２のページテーブルエントリを削除する。
fi
while   削除すべきエントリがまだある
第２のページテーブルエントリの仮想アドレスをヌルにセットし、有効フラグをアンセットする。
第２のページテーブルエントリの物理アドレスをヌルにセットする。
＜擬似コード終了＞
【発明の効果】
以上説明したように、本発明によれば、ページテーブルの検索を中止することなくページテーブルエントリの移動あるいは削除を行うことができ、処理を停滞させず、効率的に仮想メモリ管理にかかる処理を実行することができる。
【００４３】
【図面の簡単な説明】
【図１】メモリ管理ユニットの概要ブロック図である。
【図２】実施の態様における主記憶中のページテーブルおよびページテーブルエントリを示す図である。
【図３】実施の態様におけるページテーブル検索を示す概要ブロック図である。
【図４】図２のページテーブルおよびページテーブルエントリを削除する方法を示す図である。
【図５】図２のページテーブルおよびページテーブルエントリを削除する方法を示す図である。
【図６】図２のページテーブルおよびページテーブルエントリを削除する方法を示す図である。
【図７】実施の態様におけるページテーブルおよびテーブルのエントリを移動する処理を示す図である。
【図８】図２及び図３のページテーブルの検索を表すフローチャートである。
【図９】図２及び図３の構成を用いたページテーブル挿入を表すフローチャートである。
【図１０】図２及び図３の構成を用いたページテーブル削除を表すフローチャートである。
【図１】
0003880146.tif 000002
【図２】
0003880146.tif 000003
【図３】
0003880146.tif 000004
【図４】
0003880146.tif 000005
【図５】
0003880146.tif 000006
【図６】
0003880146.tif 000007
【図７】
0003880146.tif 000008
【図８】
0003880146.tif 000009
【図９】
0003880146.tif 000010
【図１０】
0003880146.tif 000011