JPH07500441A - バッファ・メモリ管理方法，及び該方法を実施するためのコンピュータシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 バッファ・メモリ管理方法、記録媒体、及びこれを組み込んだコンピュータ・シ ステム本発明は、バッファ・メモリを構成するバッファ・アセンブリを管理する 方法に関する。本発明はまた、この方法を実施するためのソフトウェアを組み込 んだ磁気ディスクや磁気テープなどの記録媒体、並びにこの方法を実施するため のコンピュータ・システム、また特に、一般に略号５ＧＢＤで表されるデータベ ース管理コンピュータ・システム（ｔＹｓ＋７ｓ＠１ｄｌｅｅｓｔ目ｑＩ＠ｄｅ 　ｌ５ｓｊｉｏｎ　ｄｓ　ｂ＊ｔｅ　ｄｅｄｏｎｎ’１ｅｔ）も、副次的対象と する。

バッファ・メモリは、プロセッサと大容量であるが通常遅いデータ・メモリとの 間の高速で小容量の一種のインターフェースを構成する。このバッファ・メモリ は、データ・メモリからのそれぞれのコピーを記憶することを目的とするバッフ ァのアセンブリから成る。これは、データ・メモリからデータｅブロックを受け 取るためのキャッシュ・メモリとなることもできる。

本発明をよく説明するために選ばれた例は５ＧＢＤのバッファ・メモリに関する ものである。５ＧＢＤは、コンピュータの中央メモリの全部または一部を構成し かつバッファ・メモリを表す仮想メモリを備えたプロセッサを用いて、コンピュ ータのオペレーティング・システムによって制御される。バッファ・メモリ内に 記憶されたデータのコピーは、データベースを構成する大容量メモリのページで あることが多い。従って、一般にバッファ・メモリはページ・キャッシュ・メモ リと呼ばれる。キャッシュ・メモリのバッファの管理は、プロセッサによって制 御されるバッファ管理プログラムによって行われる。

バッファ・メモリ、詳しくは例として考察するページ・キャッシュ・メモリを利 用するプロセスによって実行される処理は普通は２種類に区別される。キャッシ ュ・メモリの少量のページに頻繁にアクセスする処理はローカル処理と呼ばれ、 キャッシュ・メモリの大容量のページにまれにアクセスする処理は非ローカル処 理と呼ばれる。ローカル処理と非ローカル処理を同時に実行するために、キャッ シュ・メモリはバッファ管理プログラムの指示の下で分割される。この分割は、 キャッシュ・メモリの管理に関して大きな問題を提起する。

バッファ管理プログラムは、ローカル・アクセスを行う処理のために一般に論理 的に最適化される。通常、キャッシュ・メモリはＬ　ＲＩＪ　（Ｌｅ暑＋ｌ　Ｒ １ｃｅｎｌ１７　＋１ｔｅｄ）の名で知られるアルゴリズムによって管理される 。このアルゴリズムは、キャッシュ・メモリのバッファのリストをその最終使用 日付に従って作成する。原則として、バッファが参照される度ごとに、ＬＲＵで はそのバッファがリストの先頭に再連鎖される。その結果、リスト上でそれに先 行するバッファはリスト上の位置が１つずつ下がってゆく。これらのバッファは １位置だけ老化すると言われる。バッファ管理プログラムは、キャッシュ・メモ リの中でページを見つけないとき、データベースからページを抜き出してそれを キャッシュ・メモリにロードするよう要求し、一方ではＬＲＵは、新しいページ を記録するために最も直前に参照されたバッファを指定する。ローカル処理のた めのこの最適化は特に、非ローカル処理によるキャッシュ・メモリの同時利用に は適合しない。実際に、新しいページへのアクセスは、非ローカル処理では非常 に頻繁に行われる。その結果、ＬＲＵのリストの先頭が急速に変更され、従って 他のバッファの内容が早急に老化することになる。この早急な老化はローカル処 理の管理をひどく妨害し、その実行を大きく遅延させる。

新たに参照されるバッファのＬＲＵリストの先頭への再連鎖に起因する他の問題 は、特にマルチプロセッサ環境において生じる。実際に、リストの先頭への再連 鎖はリスト連鎖の保全性を維持するために最小単位でなければならない。マルチ プロセッサ・システムでは、そのために、リスト中でバッファを移動するために 連鎖解除・再連鎖操作中に専用のラッチを採用せざるを得なくなる。専用ラッチ の採用は、いわゆるクリティカル・セクシヨンを構成する。クリティカル−セク ションは所定の瞬間に１つのプロセッサによってしか実行できず、マルチプロセ ッサ・システムの性能低下の原因となる。

本発明は、これらの２つの問題を、ローカルと非ローカルの同時処理によってバ ッファ・アセンブリの管理を最適化できるようにして解決する。

本発明の目的は、あるバッファが参照されるときに、そのバッファをその位置と リストの限界位置との関係に応じて分類することから成ることを特徴とする、Ｌ ＲＵ順にバッファを分類するリストによってバッファ・アセンブリを管理する方 法を提供することである。

これに付随して、本発明の目的はまた、ＬＲＵアルゴリズムに従って管理プログ ラムによって管理されるバッファ・アセンブリを介して、データ・メモリに接続 されたプロセッサを含む、コンピュータ・システムを提供することでもある。

本発明の副次的な目的は、この方法を実施するためのソフトウェアを組み込むこ とを特徴とする、記録媒体を提供することである。

本発明の特徴と利点は、例として示す添付の図面に図示した以下の説明から明ら かになろう。

−第１図は、データベース管理システムを構成し、本発明の方法に従って管理さ れるバッファ・アセンブリを組み込んだ、本発明によるコンピュータ・システム の概略図である。

−第２図は、第１図に示したデータベース管理方法のフローチャートである。

第１図に示す概略図では、コンピュータ・システム１０は、ここで考察する例で は、データベースを構成する大容量メモ・す１３に中央メモリ１２を介して接続 された中央プロセッサ１１を含む。したがって中央メモリ１２は、中央プロセッ サ１１とデータ・ベース１３の間のバッファ拳メモリとして働く。中央メモリ１ ２は、ｎ個のバッファ・メモリ１５のアセ、ンプリ１４と、ＬＲＵアルゴリズム に基づくアセンブリ１４の管理プログラム１６を含む。ｎ個のバッファ１５は各 々がデータベース１３のコピー、図の例では４キロバイトの１ページを記憶する ように適合されている。ｎ個のバッファ１５はＬＲＵによって決定された順序１ ．２、・・・、ｎで連鎖される。プロセッサ１１は、ローカル処理１７と非ロー カル処理１８を実行するためにアセンブリ１４にアクセスする。管理プログラム １６の制御下で、処理１７．１８によって要求されたページは、外部データベー ス１３からアセンブリ１４中に複写される。したがって、アセンブリ１４は並行 するローカル処理と非ローカル処理との間で分割される。

コンピュータ・システム１０はまた従来通り、図示するように管理プログラム１ ６中に、プロセッサが要求する全ページ数に対するアセンブリ１４中に存在する ページ数の現在比率を計算する装ｆｉ１９を含む。この比率は普通は一般にバッ ファ・アクセス成功率（ヒツト率）と呼ばれる。実際に、プロセッサ１１が要求 するページのアドレスがバッファ・アセンブリのディレクトリに含まれるアドレ スであるとき、成功と言われる。

成功率は定期的に、例えば参照１０００回毎に更新される。

本発明によれば、バッファが参照されるとき、このバッファは、その位置ｐのリ ストの限界位置ｔに対する関係に応じて、管理プログラム１６によってリスト中 で分類される。本発明による方法の一例を、第２図の機能フローチャートで示す 。

例えばアセンブリ１４は１０００個のバッファ１５（ｎ＝１０００）から構成さ れると考える。この例によれば、限界位置ｔは現バッファ・アクセス成功率に従 って定義される。この例で選択された関数は、アセンブリ１４のバッファ数に対 する成功率の簡単な対応関係である。すなわち、例えば成功率が８５％である場 合、１０００個のバッファ１５のアセンブリ１４における限界位置ｔは、位置ｔ ＝８５０に相当する。コンピュータ装置１０は図示するように、好ましくは管理 プログラム１６中に装置１９から供給された成功率を受け取る限界位置ｔの発生 機構２０と、発生機構２０から限界位［ｔを受け取り、ＬＲＵからリスト中て参 照されたバッファの位１ｐを受け取る位置比較袋［２１とを含む。

参照されたページがすでにアセンブリ１４中にある場合には、そのページを組み 込んだバッファの位置ｐが限界位ｊｉｌｔと比較される。第１図に示すように位 ｌｉｐが位ｌｉｔに先行する位置ｉである、すなわちｐａｔである場合には、管 理プログラム１６はバッファ１５の位ｌｉｔを変更しない。したがって、要求さ れるページはリストの安定ゾーンまたはフレッシュ・ゾーンにあると考えられる 。言い換えれば、限界位置ｔの前に位置するすべての安定ページ（作業セット・ ページ）は１つのページを読み取った後に老化しない。これに対して、位［ｐが 限界位置またはそれより後の位置に相当する位１１にである、すなわちｐ≧ｔで ある場合には、それはリストの先頭に置かれる。老化はこの場合にのみ起こる。

要求されたページがアセンブリ１４中にない場合には、このページを限界位置ｔ に置いて、このページの読取りが安定ゾーンの中に含まれ活動状態であるき考え られるページを老化させないようにする。したがって、ページが新たに参照され る場合にのみ、それが先の比較基準に従ってリストの先頭に連鎖される。

本発明による方法のこの例は多くの変形例を有することができる。この方法では 、限界位置ｔの決定は、その比率とＬＲＵリストの位置の集合との簡単な対応関 係である。しかし明らかに、限界位置の決定は、変化する限界位１ｔまたは複数 の限界位置をもたらすこともできる、成功率の値のより精巧な関数にすることも できる。例えば第１限界位置ｔｌを、新しいページの挿入と現ページ位置ｐの比 較のための事前に定義された位置にすることもでき、第２の位置ｔ２を、第１の 再連鎖に対応するようにより小さな値、例えばｔ　２＝　ｔ　１／２にすること もできる。したがって、すでに存在し限界位置ｔ１に続く位置を有するページは 、位置ｔ２に再連鎖することができる。他の例によれば、限界位置ｔを、現成功 率の値の範囲に関する予め決定された同じ固定値にすることができる。例えば、 限界位ａｔが、８０％〜１００％の間に含まれる率については９００．６０％〜 ８０％の間に含まれる率については７００になる。もちろん、この例を先の例と 組み合わせることができる。一方、この例で選んだ限界位置ｔはバッファ・アク セス成功率に応じて定義されるが、明らかに、限界位置ｔを全く単純に予め決定 された固定位置にすることもできる。したがってこの方法は、位置ｐを１つまた は複数の固定限界位置と比較することから成る。さらに一般的には、可変限界位 置を成功率以外の他のパラメータに応じて定義することができ、また可変位置を 固定位置に加えることができることも理解されたい。

したがって一般的に言えば、これまで述べてきたことから、本発明による方法は ＬＲＵ順によってバッファを分類するりストを用いたバッファ・アセンブリの管 理に関するもので、あるバッファが参照されるとき、リストの限界位置ｔに対す るその位置ｐに応じてそのバッファを分類することから成るものである。限界位 置は固定または可変にすることができる。限界位置が可変である場合には、バッ ファへのアクセスの現成功率に応じてそれを定義するのが有利である。情報、こ の例ではページが、すでに参照されたバッファ中に存在する場合には、本発明の 方法は、バッファの位置が限界位置に先行している場合はバッファの位置を維持 し、また先行していない場合はそれをリスト中に再連鎖することから成る。この 再連鎖はリストの先頭、またはこれに先行する他の限界位置ｔ２で行えることが わかった。参照されたバッファが新しい情報を受け取る場合には、本発明による 方法はこのバッファを限界位置に置くことから成る。

複数の限界位置がある場合には、バッファは最後の限界位置に置かれる。

なお、この例はデータ・メモリとしてのデータベースとバッファ・メモリの関係 に関するものであるが、本発明は、いずれかのプロセッサといずれかのメモリ、 混乱を避けるにはいわゆるデータ・メモリとの間のすべてのバッファ・メモリに 適用することができる。中央プロセッサの特定の場合には、データ・メモリはコ ンピュータ・システムの中央メモリとなる。したがって本発明は一般に、ＬＲＵ アルゴリズムに従った管理プログラムで管理されるバッファ・アセンブリを介し てデータ・メモリに接続されたプロセッサと、少なくとも１つの限界位置を発生 させる装置と、この発生装置及びＬＲＵに接続された比較装置とを含むコンピュ ータ・システムを提供することを他の目的とする。特に、コンピュータ・システ ムがバッファへのアクセスの現成功率を計算する装置を有する場合には、この装 置は、成功率に応じて少なくとも１つの限界位置を定義するために限界位置発生 手段に接続されることになる。

Claims (11)

【特許請求の範囲】
1. １．最長時間未使用（ＬＲＵ）順によってバッファ（１５）を分類するリストを 用いるバッファ・アセンブリ管理方法（１４）において、バッファ（１５）の１ つが参照されるとき、リストの限界位置（ｔ）に対するバッファの位置（ｐ）に 応じて分類することから成ることを特徴とする方法。
2. ２．情報が参照されたバッファ中にすでにあるとき、バッファの位置が限界位置 より前にある場合はバッファの位置を維持し、また前にない場合はそれをリスト 内に再連鎖することから成ることを特徴とする、請求の範囲第１項に記載の方法 。
3. ３．バッファの位置をリストの先頭、またはこれより前にある他の限界位置（ｔ ２）で再連鎖することから成ることを特徴とする、請求の範囲第２項に記載の方 法。
4. ４．参照されたバッファが新しい情報を受け取るとき、バッファの位置を限界位 置に置くことから成ることを特徴とする、請求の範囲第１項から第３項のいずれ か一項に記載の方法。
5. ５．複数の限界位置を使用し、バッファを最後にある限界位置に置くことから成 ることを特徴とする、前求の範囲第４項に記載の方法。
6. ６．バッファヘのアクセスの現成功率に応じて限界位置を定義することから成る ことを特徴とする、請求の範囲第１項から第５項のいずれか一項に記載の方法。
7. ７．限界位置が予め決定された固定値であることを特徴とする、請求の範囲第１ 項から第６項のいずれか一項に記載の方法。
8. ８．ＬＲＵアルゴリズムに従って管理プログラム（１６）によって管理されるバ ッファ（１５）のアセンブリ（１４）を介してデータ・メモリ（１２）に接続さ れたプロセッサ（１１）を含むコンピュータ・システム（１０）において、少な くとも１つの限界位置（ｔ）を発生させる装置（２０）と、この発生装置及びＬ ＲＵに接続された比較装置（２１）を含むことを特徴とするシステム（１０）。
9. ９．バッファヘのアクセスの現成功率を計算する装置（１９）を含む形式であっ て、計算する装置が発生装置（２０）に接続されていることを特徴とする、請求 の範囲第８項に記載のコンピュータ・システム。
10. １０．データ・メモリがデータベースであり、バッファ・アセンブリ（１４）が システムの中央プロセッサ（１１）と結合された中央メモリの全部または一部で あることを特徴とする、請求の範囲第８項または第９項に記載のシステム。
11. １１．請求の範囲第１項から第７項のいずれか一項によって定義された方法を実 施するためのソフトウェアを含むことを特徴とする記録媒体。