JPH05314010A - 置換対象データの選択方式 - Google Patents
置換対象データの選択方式Info
- Publication number
- JPH05314010A JPH05314010A JP4113585A JP11358592A JPH05314010A JP H05314010 A JPH05314010 A JP H05314010A JP 4113585 A JP4113585 A JP 4113585A JP 11358592 A JP11358592 A JP 11358592A JP H05314010 A JPH05314010 A JP H05314010A
- Authority
- JP
- Japan
- Prior art keywords
- data
- lru
- storage device
- speed storage
- accessed
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【目的】 ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕ
ｓｅｄ）管理テーブルを複数段に階層化することで、高
速にＬＲＵ近似方式を実現し、各ＬＲＵテーブル毎に占
有権管理を行なうことで、複数のデータ・アクセス要求
に対する処理を同時行なう。 【構成】 ＬＲＵテーブルを複数段に階層化し、各階層
においてＬＲＵ近似方式を実行することで、低速記憶装
置との置換処理を行なうデータを決定する手段と、各Ｌ
ＲＵテーブル毎に施錠フラグを設け、各ＬＲＵテーブル
へのアクセスが終了した時点でそのＬＲＵテーブルの占
有権を放棄する（即ち、ＬＲＵテーブルの施錠を解除す
る）手段とを備える。
ｓｅｄ）管理テーブルを複数段に階層化することで、高
速にＬＲＵ近似方式を実現し、各ＬＲＵテーブル毎に占
有権管理を行なうことで、複数のデータ・アクセス要求
に対する処理を同時行なう。 【構成】 ＬＲＵテーブルを複数段に階層化し、各階層
においてＬＲＵ近似方式を実行することで、低速記憶装
置との置換処理を行なうデータを決定する手段と、各Ｌ
ＲＵテーブル毎に施錠フラグを設け、各ＬＲＵテーブル
へのアクセスが終了した時点でそのＬＲＵテーブルの占
有権を放棄する（即ち、ＬＲＵテーブルの施錠を解除す
る）手段とを備える。
Description
【０００１】
【産業上の利用分野】本発明は、並列計算機システムに
おいて、高速記憶装置と低速記憶装置間のデータの置換
方式に関するものである。
おいて、高速記憶装置と低速記憶装置間のデータの置換
方式に関するものである。
【０００２】
【従来の技術】計算機システムなどの情報処理装置で
は、低速記憶装置上のデータの一部を高速記憶装置にコ
ピーして、データの参照をその高速記憶装置に対して行
なうようにして、処理の高速化をはかる方式がある。高
速記憶装置と低速記憶装置には、二次記憶と主記憶、主
記憶とキャッシュ装置などがある。
は、低速記憶装置上のデータの一部を高速記憶装置にコ
ピーして、データの参照をその高速記憶装置に対して行
なうようにして、処理の高速化をはかる方式がある。高
速記憶装置と低速記憶装置には、二次記憶と主記憶、主
記憶とキャッシュ装置などがある。
【０００３】この高速記憶装置に対するアクセスは、あ
るデータのアクセス要求に対して高速記憶装置内を検索
し、存在すればそのデータにアクセスが行なわれ、存在
しなければ高速記憶装置内のあるデータを低速記憶装置
に書き込み、その位置に低速記憶装置からアクセス要求
のあったデータを高速記憶装置に読み出す。この高速記
憶装置と低速記憶装置間の置換において、高速記憶装置
内のどのデータを低速記憶装置に書き出すかという方式
に、従来から、最も以前に参照されたデータを置換する
ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）方
式がある。
るデータのアクセス要求に対して高速記憶装置内を検索
し、存在すればそのデータにアクセスが行なわれ、存在
しなければ高速記憶装置内のあるデータを低速記憶装置
に書き込み、その位置に低速記憶装置からアクセス要求
のあったデータを高速記憶装置に読み出す。この高速記
憶装置と低速記憶装置間の置換において、高速記憶装置
内のどのデータを低速記憶装置に書き出すかという方式
に、従来から、最も以前に参照されたデータを置換する
ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）方
式がある。
【０００４】ＬＲＵ方式は正確に実現するのは難しく、
近似方式により代用することが多い。従来、この近似方
式として例えば、前川 守著、岩波講座 ソフトウェア
科学６オペレーティングシステム、岩波書店発行の２６
１ページから２６４ページに示されたものがあった。
近似方式により代用することが多い。従来、この近似方
式として例えば、前川 守著、岩波講座 ソフトウェア
科学６オペレーティングシステム、岩波書店発行の２６
１ページから２６４ページに示されたものがあった。
【０００５】図８は、従来のＬＲＵ近似方式を示す構成
図であり、１はデータを読み込む要求元プログラム、４
は高速記憶装置、５は低速記憶装置、１３はＬＲＵテー
ブルである。なお、ＬＲＵテーブル１３は、ＬＲＵ近似
方式を実現するために、データを検索する際に用いるデ
ータ識別子を格納するデータ識別子部２２、データが前
回の置換処理から参照されたかを示す１ビットの情報を
格納する参照ビット部１９、置換処理時に参照ビット部
１９が０であった回数を格納するカウンタ部２０から構
成される。また、参照ビット部１９及びカウンタ部２０
の初期状態は、全て０である。
図であり、１はデータを読み込む要求元プログラム、４
は高速記憶装置、５は低速記憶装置、１３はＬＲＵテー
ブルである。なお、ＬＲＵテーブル１３は、ＬＲＵ近似
方式を実現するために、データを検索する際に用いるデ
ータ識別子を格納するデータ識別子部２２、データが前
回の置換処理から参照されたかを示す１ビットの情報を
格納する参照ビット部１９、置換処理時に参照ビット部
１９が０であった回数を格納するカウンタ部２０から構
成される。また、参照ビット部１９及びカウンタ部２０
の初期状態は、全て０である。
【０００６】このような構成のシステムにおいては、図
９に示すフローチャートに基づいて、ＬＲＵ近似方式が
行なわれる。まず、要求元プログラム１に必要なデータ
の読み込み要求が発生すると、ステップ１で読み込みた
いデータを特定するためのデータ識別子（以下参照識別
子という）を基に高速記憶装置４を検索し、該当データ
が高速記憶装置４内に存在すれば当該データを取り出す
と共にステップ２へ進みＬＲＵテーブル１３の参照デー
タに対応する参照ビット部をセットし、存在しなければ
ステップ３へ進み置換処理を行なう。ステップ２では、
参照識別子をキーとしてＬＲＵテーブル１３を検索し、
該当するエントリの参照ビット部１９を１にする。これ
により、検索データに対応する参照ビットのセットが終
了する。ステップ３では、ＬＲＵテーブル１３の全ての
エントリに対して、参照ビット部１９が０ならばカウン
タ部２０を１増化し、参照ビット部１９が１ならば参照
ビット部１９を０にすると共にカウンタ部２０を０にす
る。次に、ＬＲＵテーブル１３内でカウンタ部２０の値
が最大のエントリを検索し、検索されたエントリのデー
タ識別子部２２の値を取り出し、それを置換対象のデー
タ識別子とし、このエントリを削除し、ステップ４へ進
む。ステップ４では、ステップ３により求められた置換
対象のデータ識別子を基に置換データを高速記憶装置４
から取り出し低速記憶装置５へ書き戻す。次に、参照識
別子を基に低速記憶装置５から検索データを読み出すと
共に、高速記憶装置４へそのデータを書き込み、ステッ
プ５に進み参照データの登録を行なう。ステップ５で
は、データ識別子部２２の値を検索識別子、参照ビット
部１９の値を０、カウンタ部２０の値を０とした新たな
エントリをＬＲＵテーブル１３に登録する。
９に示すフローチャートに基づいて、ＬＲＵ近似方式が
行なわれる。まず、要求元プログラム１に必要なデータ
の読み込み要求が発生すると、ステップ１で読み込みた
いデータを特定するためのデータ識別子（以下参照識別
子という）を基に高速記憶装置４を検索し、該当データ
が高速記憶装置４内に存在すれば当該データを取り出す
と共にステップ２へ進みＬＲＵテーブル１３の参照デー
タに対応する参照ビット部をセットし、存在しなければ
ステップ３へ進み置換処理を行なう。ステップ２では、
参照識別子をキーとしてＬＲＵテーブル１３を検索し、
該当するエントリの参照ビット部１９を１にする。これ
により、検索データに対応する参照ビットのセットが終
了する。ステップ３では、ＬＲＵテーブル１３の全ての
エントリに対して、参照ビット部１９が０ならばカウン
タ部２０を１増化し、参照ビット部１９が１ならば参照
ビット部１９を０にすると共にカウンタ部２０を０にす
る。次に、ＬＲＵテーブル１３内でカウンタ部２０の値
が最大のエントリを検索し、検索されたエントリのデー
タ識別子部２２の値を取り出し、それを置換対象のデー
タ識別子とし、このエントリを削除し、ステップ４へ進
む。ステップ４では、ステップ３により求められた置換
対象のデータ識別子を基に置換データを高速記憶装置４
から取り出し低速記憶装置５へ書き戻す。次に、参照識
別子を基に低速記憶装置５から検索データを読み出すと
共に、高速記憶装置４へそのデータを書き込み、ステッ
プ５に進み参照データの登録を行なう。ステップ５で
は、データ識別子部２２の値を検索識別子、参照ビット
部１９の値を０、カウンタ部２０の値を０とした新たな
エントリをＬＲＵテーブル１３に登録する。
【０００７】このように従来の方式では、参照ビット部
１９により前回置換が行なわれた時からそのデータが参
照されたかを示し、カウンタ部２０により置換が起きる
ごとに参照されなかった数をカウントすることで、カウ
ンタ部２０の値が最も大きいデータを最も長い間参照さ
れなかったと判断することで、ＬＲＵ方式を近似してい
る。
１９により前回置換が行なわれた時からそのデータが参
照されたかを示し、カウンタ部２０により置換が起きる
ごとに参照されなかった数をカウントすることで、カウ
ンタ部２０の値が最も大きいデータを最も長い間参照さ
れなかったと判断することで、ＬＲＵ方式を近似してい
る。
【０００８】
【発明が解決しようとする課題】以上のような従来のＬ
ＲＵ近似方式においては、置換時にＬＲＵテーブル内の
全エントリについて参照ビット部を操作し、更にカウン
タ部の最大のエントリを検索しているが、高速記憶装置
のサイズが大きくなるにつれＬＲＵテーブルのサイズも
大きくなり、ＬＲＵテーブルの全エントリに対する操作
に非常に時間がかかるため、置換処理が高速に行なえな
いという課題があった。また、並列計算機においては、
要求元プログラムが複数存在し、複数のデータ・アクセ
ス要求が同時に発行される場合があり、従来方式では、
１つの要求のために長時間ＬＲＵテーブルを占有するこ
とになり、並列度を減少されるという課題もある。
ＲＵ近似方式においては、置換時にＬＲＵテーブル内の
全エントリについて参照ビット部を操作し、更にカウン
タ部の最大のエントリを検索しているが、高速記憶装置
のサイズが大きくなるにつれＬＲＵテーブルのサイズも
大きくなり、ＬＲＵテーブルの全エントリに対する操作
に非常に時間がかかるため、置換処理が高速に行なえな
いという課題があった。また、並列計算機においては、
要求元プログラムが複数存在し、複数のデータ・アクセ
ス要求が同時に発行される場合があり、従来方式では、
１つの要求のために長時間ＬＲＵテーブルを占有するこ
とになり、並列度を減少されるという課題もある。
【０００９】特開昭６１−１５６４４６号の発明におい
ては、置換処理の管理テーブルを複数に分割すること
で、この課題を解決しようとしているが、この方式で
は、最大でも記憶装置のサイズの平方根倍程度の高速化
しか行なえない。
ては、置換処理の管理テーブルを複数に分割すること
で、この課題を解決しようとしているが、この方式で
は、最大でも記憶装置のサイズの平方根倍程度の高速化
しか行なえない。
【００１０】
【課題を解決するための手段】本発明に係る並列計算機
に適した置換対象データの選択方式においては、ＬＲＵ
テーブルを複数段に階層化し、各階層においてＬＲＵ近
似方式を実行することで、低速記憶装置との置換処理を
行なうデータを決定する手段と、各ＬＲＵテーブル毎に
施錠フラグを設け、各ＬＲＵテーブルへのアクセスが終
了した時点でそのＬＲＵテーブルの占有権を放棄する
（即ち、ＬＲＵテーブルの施錠を解除する）手段からな
るものである。
に適した置換対象データの選択方式においては、ＬＲＵ
テーブルを複数段に階層化し、各階層においてＬＲＵ近
似方式を実行することで、低速記憶装置との置換処理を
行なうデータを決定する手段と、各ＬＲＵテーブル毎に
施錠フラグを設け、各ＬＲＵテーブルへのアクセスが終
了した時点でそのＬＲＵテーブルの占有権を放棄する
（即ち、ＬＲＵテーブルの施錠を解除する）手段からな
るものである。
【００１１】
【作用】本発明においては、ＬＲＵテーブルを複数段に
階層化することで、各ＬＲＵテーブルのサイズが階層数
根分の１と非常に小さくなり、高速にＬＲＵ近似方式を
実現でき、各ＬＲＵテーブル毎に施錠フラグを設け、各
ＬＲＵテーブルへのアクセスが終了した時点でそのＬＲ
Ｕテーブルの施錠を解除することで、他の要求元プログ
ラムがそのＬＲＵテーブルに対してアクセス可能とな
り、複数の要求元プログラムの置換処理を並列に実行す
ることを可能としている。
階層化することで、各ＬＲＵテーブルのサイズが階層数
根分の１と非常に小さくなり、高速にＬＲＵ近似方式を
実現でき、各ＬＲＵテーブル毎に施錠フラグを設け、各
ＬＲＵテーブルへのアクセスが終了した時点でそのＬＲ
Ｕテーブルの施錠を解除することで、他の要求元プログ
ラムがそのＬＲＵテーブルに対してアクセス可能とな
り、複数の要求元プログラムの置換処理を並列に実行す
ることを可能としている。
【００１２】
【実施例】図１はこの発明の一実施例を示す構成図であ
り、１〜３は並列に動作するデータを読み込む要求元プ
ログラム、４は高速記憶装置、５は低速記憶装置、６〜
１２はＬＲＵセット・テーブル、１３〜１６はＬＲＵテ
ーブルである。ＬＲＵセット・テーブルは、ＬＲＵ近似
方式を実現するための情報及び下位のＬＲＵセット・テ
ーブルまたはＬＲＵテーブルが格納されている。また、
ＬＲＵテーブルは、ＬＲＵ近似方式を実現するための情
報及びデータ識別子が格納されている。
り、１〜３は並列に動作するデータを読み込む要求元プ
ログラム、４は高速記憶装置、５は低速記憶装置、６〜
１２はＬＲＵセット・テーブル、１３〜１６はＬＲＵテ
ーブルである。ＬＲＵセット・テーブルは、ＬＲＵ近似
方式を実現するための情報及び下位のＬＲＵセット・テ
ーブルまたはＬＲＵテーブルが格納されている。また、
ＬＲＵテーブルは、ＬＲＵ近似方式を実現するための情
報及びデータ識別子が格納されている。
【００１３】なお、本実施例では、高速記憶装置４及び
低速記憶装置５は、データをそのデータと一対一で対応
して付されたデータ識別子と共に記憶しており、３２ビ
ットのデータ識別子を基に、記憶装置のサイズに依存し
ない時間でデータを取り出すことが可能である。高速記
憶装置４のサイズは１メガワード（即ち、２の２０乗ワ
ード）で、ＬＲＵテーブルの階層段数が４段としてあ
る。従って、ＬＲＵセット・テーブルは、３２エントリ
から構成される。
低速記憶装置５は、データをそのデータと一対一で対応
して付されたデータ識別子と共に記憶しており、３２ビ
ットのデータ識別子を基に、記憶装置のサイズに依存し
ない時間でデータを取り出すことが可能である。高速記
憶装置４のサイズは１メガワード（即ち、２の２０乗ワ
ード）で、ＬＲＵテーブルの階層段数が４段としてあ
る。従って、ＬＲＵセット・テーブルは、３２エントリ
から構成される。
【００１４】図２は、１つのＬＲＵセット・テーブルを
示す構成図であり、１７は施錠フラグ、１８はキー部、
１９は参照ビット部、２０はカウンタ部、２１は下位テ
ーブル部であり、１７はＬＲＵセット・テーブルに１
つ、１８〜２１はエントリ毎に（即ち、３２個）存在す
る。なお、施錠フラグ１７は、あるプログラムによりＬ
ＲＵセット・テーブルが使用されているかどうかを示す
１ビットの情報を格納するもので、その値が０であれば
未使用状態（即ち、解錠状態）、１であれば使用状態
（即ち、施錠状態）を表す。キー部１８は、０から３１
までの数値が格納されており、参照ビット部１９は、前
回の置換処理からそのエントリが参照されたかを示す１
ビットの情報を格納するもので、その値が０であれば未
参照、１であれば参照されたことを表す。また、カウン
タ部２０は置換処理に参照ビット部１９が０であった回
数を格納するものであり、下位テーブル部は１階層下の
ＬＲＵセット・テーブルまたはＬＲＵテーブルを格納す
るものである。なお、キー部１８の値を基にしたＬＲＵ
セット・テーブルの検索は、固定時間で行なえるものと
する。また、施錠フラグ１７、参照ビット部１９、カウ
ンタ部２０は、全て値０で初期化されているものとす
る。
示す構成図であり、１７は施錠フラグ、１８はキー部、
１９は参照ビット部、２０はカウンタ部、２１は下位テ
ーブル部であり、１７はＬＲＵセット・テーブルに１
つ、１８〜２１はエントリ毎に（即ち、３２個）存在す
る。なお、施錠フラグ１７は、あるプログラムによりＬ
ＲＵセット・テーブルが使用されているかどうかを示す
１ビットの情報を格納するもので、その値が０であれば
未使用状態（即ち、解錠状態）、１であれば使用状態
（即ち、施錠状態）を表す。キー部１８は、０から３１
までの数値が格納されており、参照ビット部１９は、前
回の置換処理からそのエントリが参照されたかを示す１
ビットの情報を格納するもので、その値が０であれば未
参照、１であれば参照されたことを表す。また、カウン
タ部２０は置換処理に参照ビット部１９が０であった回
数を格納するものであり、下位テーブル部は１階層下の
ＬＲＵセット・テーブルまたはＬＲＵテーブルを格納す
るものである。なお、キー部１８の値を基にしたＬＲＵ
セット・テーブルの検索は、固定時間で行なえるものと
する。また、施錠フラグ１７、参照ビット部１９、カウ
ンタ部２０は、全て値０で初期化されているものとす
る。
【００１５】図３は、１つのＬＲＵテーブルを示す構成
図であり、１７，１９，２０は、図２におけるＬＲＵセ
ット・テーブルと同様のものであり、２２はデータ識別
子部であり、データの識別子を格納するものである。
図であり、１７，１９，２０は、図２におけるＬＲＵセ
ット・テーブルと同様のものであり、２２はデータ識別
子部であり、データの識別子を格納するものである。
【００１６】このような構成のシステムにおいては、図
４〜図７に示すフローチャートに基づいてＬＲＵ近似方
式が行なわれる。まず、要求元プログラム１に必要なデ
ータの読み込み要求が発生すると、ステップ１で読み込
みたいデータを特定するためのデータ識別子（即ち、参
照識別子）を基に高速記憶装置４を検索し、該当データ
が高速記憶装置４内に存在すれば当該データを取り出す
と共に第１層のＬＲＵセット・テーブル６を対象として
ステップ２へ進み、参照ビット部をセットし、存在しな
ければ第１層のＬＲＵセット・テーブル６を対象として
ステップ３へ進み置換処理を行なう。
４〜図７に示すフローチャートに基づいてＬＲＵ近似方
式が行なわれる。まず、要求元プログラム１に必要なデ
ータの読み込み要求が発生すると、ステップ１で読み込
みたいデータを特定するためのデータ識別子（即ち、参
照識別子）を基に高速記憶装置４を検索し、該当データ
が高速記憶装置４内に存在すれば当該データを取り出す
と共に第１層のＬＲＵセット・テーブル６を対象として
ステップ２へ進み、参照ビット部をセットし、存在しな
ければ第１層のＬＲＵセット・テーブル６を対象として
ステップ３へ進み置換処理を行なう。
【００１７】ステップ２では、対象とするテーブルの施
錠フラグ１７が０ならば（即ち、施錠されていなけれ
ば）ステップ２ａへ進み、施錠フラグ１７が１ならば
（即ち、施錠されていれば）施錠フラグ１７が０になる
まで待ち、ステップ２ａへ進む。ステップ２ａでは、施
錠フラグ１７を１にし、参照識別子の第１ビットから第
５ビットまでの５ビットの情報をキーとして対象テーブ
ル（即ち、ＬＲＵセット・テーブルまたはＬＲＵテーブ
ル）を検索し、該当するエントリの参照ビット部１９を
１にすると共に、対象テーブルがＬＲＵセット・テーブ
ルであればステップ２ｂへ進み、対象テーブルがＬＲＵ
テーブルであれば、ステップ２ｃへ進む。ステップ２ｂ
では、上記該当するエントリの下位テーブル部２１から
下位のテーブルを取り出し施錠フラグ１７を０にし、そ
の下位のテーブルを対象としてステップ２へ進むが、キ
ーを基にエントリを検索する際のキー値が階層のレベル
により異なり、その対象テーブルが第２層であれば参照
識別子の第６ビットから第１０ビットまでの５ビットの
情報をキーにし、第３層であれば、参照識別子の第１１
ビットから第１５ビットまでの５ビットの情報をキーに
し、第４層であれば（即ち、次回の対象テーブルがＬＲ
Ｕテーブルの場合）参照識別子をキーとする。ステップ
２ｃでは、施錠フラグを０にする。これにより、検索デ
ータに対応する参照ビットのセットが終了する。
錠フラグ１７が０ならば（即ち、施錠されていなけれ
ば）ステップ２ａへ進み、施錠フラグ１７が１ならば
（即ち、施錠されていれば）施錠フラグ１７が０になる
まで待ち、ステップ２ａへ進む。ステップ２ａでは、施
錠フラグ１７を１にし、参照識別子の第１ビットから第
５ビットまでの５ビットの情報をキーとして対象テーブ
ル（即ち、ＬＲＵセット・テーブルまたはＬＲＵテーブ
ル）を検索し、該当するエントリの参照ビット部１９を
１にすると共に、対象テーブルがＬＲＵセット・テーブ
ルであればステップ２ｂへ進み、対象テーブルがＬＲＵ
テーブルであれば、ステップ２ｃへ進む。ステップ２ｂ
では、上記該当するエントリの下位テーブル部２１から
下位のテーブルを取り出し施錠フラグ１７を０にし、そ
の下位のテーブルを対象としてステップ２へ進むが、キ
ーを基にエントリを検索する際のキー値が階層のレベル
により異なり、その対象テーブルが第２層であれば参照
識別子の第６ビットから第１０ビットまでの５ビットの
情報をキーにし、第３層であれば、参照識別子の第１１
ビットから第１５ビットまでの５ビットの情報をキーに
し、第４層であれば（即ち、次回の対象テーブルがＬＲ
Ｕテーブルの場合）参照識別子をキーとする。ステップ
２ｃでは、施錠フラグを０にする。これにより、検索デ
ータに対応する参照ビットのセットが終了する。
【００１８】ステップ３では、対象とするテーブルの施
錠フラグ１７が０ならばステップ３ａへ進み、施錠フラ
グ１７が１ならば施錠フラグ１７が０になるまで待ち、
ステップ３ａへ進む。ステップ３ａでは、施錠フラグ１
７を１にし、対象テーブルの全てのエントリに対して、
参照ビット部１９が０ならばカウンタ部２０を１増加
し、参照ビット部１９が１ならば参照ビット部１９を０
にすると共にカウンタ部２０を０にする。次に、対象テ
ーブル内でカウンタ部２０の値が最大のエントリを検索
し、対象テーブルがＬＲＵセット・テーブルであればス
テップ３ｂへ進み、ＬＲＵテーブルであればステップ３
ｃへ進む。ステップ３ｂでは、上記で検索されたエント
リの下位テーブル部２１から下位のテーブルを取り出し
施錠フラグ１７を０にし、その下位のテーブルを対象と
してステップ３へ進む。ステップ３ｃでは、上記で検索
されたエントリのデータ識別子部２２の値を取り出し、
それを置換対象のデータ識別子とし、そのエントリを削
除すると共に施錠フラグ１７を０にし、ステップ４へ進
む。
錠フラグ１７が０ならばステップ３ａへ進み、施錠フラ
グ１７が１ならば施錠フラグ１７が０になるまで待ち、
ステップ３ａへ進む。ステップ３ａでは、施錠フラグ１
７を１にし、対象テーブルの全てのエントリに対して、
参照ビット部１９が０ならばカウンタ部２０を１増加
し、参照ビット部１９が１ならば参照ビット部１９を０
にすると共にカウンタ部２０を０にする。次に、対象テ
ーブル内でカウンタ部２０の値が最大のエントリを検索
し、対象テーブルがＬＲＵセット・テーブルであればス
テップ３ｂへ進み、ＬＲＵテーブルであればステップ３
ｃへ進む。ステップ３ｂでは、上記で検索されたエント
リの下位テーブル部２１から下位のテーブルを取り出し
施錠フラグ１７を０にし、その下位のテーブルを対象と
してステップ３へ進む。ステップ３ｃでは、上記で検索
されたエントリのデータ識別子部２２の値を取り出し、
それを置換対象のデータ識別子とし、そのエントリを削
除すると共に施錠フラグ１７を０にし、ステップ４へ進
む。
【００１９】ステップ４では、ステップ３により求めら
れた置換対象のデータ識別子を基に置換データを高速記
憶装置４から取り出し低速記憶装置５へ書き戻す。次
に、参照識別子を基に低速記憶装置５から参照データを
読み出すと共に、高速記憶装置４へそのデータを書き込
み、第１層ＬＲＵテーブル６を対象としてステップ５に
進み参照データの登録を行なう。
れた置換対象のデータ識別子を基に置換データを高速記
憶装置４から取り出し低速記憶装置５へ書き戻す。次
に、参照識別子を基に低速記憶装置５から参照データを
読み出すと共に、高速記憶装置４へそのデータを書き込
み、第１層ＬＲＵテーブル６を対象としてステップ５に
進み参照データの登録を行なう。
【００２０】ステップ５では、対象とするテーブルがＬ
ＲＵセット・テーブルであればステップ５ａへ進み、Ｌ
ＲＵテーブルであればステップ５ｂへ進む。ステップ５
ａでは、参照識別子の第１ビットから第５ビットまでの
５ビットの情報をキーとして対象テーブルを検索し、該
当するエントリの下位テーブル部２１から下位のテーブ
ルを検索し、該当するエントリの下位テーブル部２１か
ら下位のテーブルを取り出し、その下位のテーブルを対
象としてステップ５へ進むが、キーを基にエントリを検
索する際のキー値が階層のレベルにより異なり、その対
象テーブルが第２層であれば参照識別子の第６ビットか
ら第１０ビットまでの５ビットの情報をキーにし、第３
層であれば、参照識別子の第１１ビットから第１５ビッ
トまでの５ビットの情報をキーにする。ステップ５ｂで
は、対象テーブルの施錠フラグ１７が０ならばステップ
５ｃへ進み、施錠フラグ１７が１ならば施錠フラグ１７
が０になるまで待ち、ステップ５ｃへ進む。ステップ５
ｃでは施錠フラグ１７を１にし、識別子部２２の値を参
照識別子、参照ビット部１９の値を０、カウンタ部２０
の値を０とした新たなエントリを対象テーブルに登録
し、施錠フラグ１７を０にする。これにより、参照デー
タのＬＲＵテーブルへの登録が終了する。
ＲＵセット・テーブルであればステップ５ａへ進み、Ｌ
ＲＵテーブルであればステップ５ｂへ進む。ステップ５
ａでは、参照識別子の第１ビットから第５ビットまでの
５ビットの情報をキーとして対象テーブルを検索し、該
当するエントリの下位テーブル部２１から下位のテーブ
ルを検索し、該当するエントリの下位テーブル部２１か
ら下位のテーブルを取り出し、その下位のテーブルを対
象としてステップ５へ進むが、キーを基にエントリを検
索する際のキー値が階層のレベルにより異なり、その対
象テーブルが第２層であれば参照識別子の第６ビットか
ら第１０ビットまでの５ビットの情報をキーにし、第３
層であれば、参照識別子の第１１ビットから第１５ビッ
トまでの５ビットの情報をキーにする。ステップ５ｂで
は、対象テーブルの施錠フラグ１７が０ならばステップ
５ｃへ進み、施錠フラグ１７が１ならば施錠フラグ１７
が０になるまで待ち、ステップ５ｃへ進む。ステップ５
ｃでは施錠フラグ１７を１にし、識別子部２２の値を参
照識別子、参照ビット部１９の値を０、カウンタ部２０
の値を０とした新たなエントリを対象テーブルに登録
し、施錠フラグ１７を０にする。これにより、参照デー
タのＬＲＵテーブルへの登録が終了する。
【００２１】このように、ＬＲＵテーブルを４階層に階
層化することで、１つのテーブルのサイズを３２エント
リという小さなサイズにしているために、ＬＲＵ近似方
式を高速に行なうことができる。更に、並列計算機にお
いて、要求元プログラム１に対する処理を行なっている
途中で他の要求元プログラムも読み込みを行なおうとし
た場合、各テーブル毎に施錠フラグ１７により占有権管
理を行なっているので、要求元プログラム１のあるテー
ブル（即ち、ＬＲＵセット・テーブルまたはＬＲＵテー
ブル）へのアクセスが終了した時点で、他の要求元プロ
グラム２，３がそのテーブルにアクセスすることがで
き、複数の並列に実行されるプログラムで低速記憶装置
と高速記憶装置間のデータ置換処理を同時に実行でき
る。
層化することで、１つのテーブルのサイズを３２エント
リという小さなサイズにしているために、ＬＲＵ近似方
式を高速に行なうことができる。更に、並列計算機にお
いて、要求元プログラム１に対する処理を行なっている
途中で他の要求元プログラムも読み込みを行なおうとし
た場合、各テーブル毎に施錠フラグ１７により占有権管
理を行なっているので、要求元プログラム１のあるテー
ブル（即ち、ＬＲＵセット・テーブルまたはＬＲＵテー
ブル）へのアクセスが終了した時点で、他の要求元プロ
グラム２，３がそのテーブルにアクセスすることがで
き、複数の並列に実行されるプログラムで低速記憶装置
と高速記憶装置間のデータ置換処理を同時に実行でき
る。
【００２２】なお、本実施例では、ＬＲＵテーブルの階
層化の段数を４段、高速記憶装置のサイズを１メガ・ワ
ードにした例を用いて説明を行なっているが、階層化の
段数及び高速記憶装置のサイズはどんな値であっても良
い。
層化の段数を４段、高速記憶装置のサイズを１メガ・ワ
ードにした例を用いて説明を行なっているが、階層化の
段数及び高速記憶装置のサイズはどんな値であっても良
い。
【００２３】
【発明の効果】以上のようにこの発明によれば、ＬＲＵ
テーブルを複数段に階層化し１つのＬＲＵテーブルのサ
イズを小さくすることで、高速にＬＲＵ近似方式を実行
でき、各ＬＲＵテーブル毎に施錠フラグを設け占有権管
理を行なうことで、複数の要求元プログラムの置換処理
を並列に実行することを可能としている。
テーブルを複数段に階層化し１つのＬＲＵテーブルのサ
イズを小さくすることで、高速にＬＲＵ近似方式を実行
でき、各ＬＲＵテーブル毎に施錠フラグを設け占有権管
理を行なうことで、複数の要求元プログラムの置換処理
を並列に実行することを可能としている。
【図１】この発明の一実施例を示す全体構成図である。
【図２】ＬＲＵセット・テーブルを示す構成図である。
【図３】ＬＲＵテーブルを示す構成図である。
【図４】この実施例の動作を示すフローチャートであ
る。
る。
【図５】この実施例の動作を示すフローチャートであ
る。
る。
【図６】この実施例の動作を示すフローチャートであ
る。
る。
【図７】この実施例の動作を示すフローチャートであ
る。
る。
【図８】従来のＬＲＵ近似方式を示す構成図である。
【図９】その動作を示すフローチャートである。
１〜３ 要求元プログラム ４ 高速記憶装置 ５ 低速記憶装置 ６〜１２ ＬＲＵセット・テーブル １３〜１６ ＬＲＵテーブル １７ 施錠フラグ １８ キー部 １９ 参照ビット部 ２０ カウンタ部 ２１ 下位テーブル ２２ データ識別部
Claims (2)
- 【請求項１】 複数のエントリから構成される高速記憶
装置及び低速記憶装置を具備し、アクセスするデータが
高速記憶装置内に存在する場合はそのデータをアクセス
し、上記データが存在しない場合は高速記憶装置内の適
当なデータを低速記憶装置内のアクセスすべきデータと
置換する記憶管理システムにおいて、高速記憶装置内の
各データのアクセス順序を管理するテーブルを複数段に
階層化し、高速記憶装置内にアクセスすべきデータが存
在した場合には上記階層化された管理テーブル及び参照
データの参照順序情報を更新する第１の手段と、高速記
憶装置内にアクセスすべきデータが存在しない場合には
上記階層化された管理テーブル及びデータの内最も過去
にアクセスされたと判断されるものを低速記憶装置と置
換を行なう第２の手段を備えたことを特徴とする置換対
象データの選択方式。 - 【請求項２】 上記記憶管理方式において、階層化され
た各管理テーブル毎に施錠フラグを設け、管理テーブル
にアクセスする場合、上記施錠フラグが解錠状態であれ
ば施錠状態にしアクセスを行ないアクセスが終了した時
点で解錠状態にする第１の手段と、施錠フラグが施錠状
態であれば解錠状態になるまで待ってからアクセスを行
なう第２の手段を備えたことを特徴とする置換対象デー
タの選択方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4113585A JPH05314010A (ja) | 1992-05-06 | 1992-05-06 | 置換対象データの選択方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4113585A JPH05314010A (ja) | 1992-05-06 | 1992-05-06 | 置換対象データの選択方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05314010A true JPH05314010A (ja) | 1993-11-26 |
Family
ID=14615953
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4113585A Pending JPH05314010A (ja) | 1992-05-06 | 1992-05-06 | 置換対象データの選択方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH05314010A (ja) |
-
1992
- 1992-05-06 JP JP4113585A patent/JPH05314010A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0303231B1 (en) | Method and device for enabling concurrent access of indexed sequential data files | |
| EP1540533B1 (en) | Controlling visibility in multi-version database systems | |
| US4864497A (en) | Method of integrating software application programs using an attributive data model database | |
| JP3674117B2 (ja) | 排他制御方法およびそれを利用したデータ管理システム並びに記録媒体 | |
| US7613683B2 (en) | System and method for retrieving information from a database | |
| US6631366B1 (en) | Database system providing methodology for optimizing latching/copying costs in index scans on data-only locked tables | |
| US5430869A (en) | System and method for restructuring a B-Tree | |
| US4914569A (en) | Method for concurrent record access, insertion, deletion and alteration using an index tree | |
| JPH05210637A (ja) | 同時アクセス管理方法 | |
| JPH04337850A (ja) | データベース・トランザクション及び照会処理システム | |
| CA2302303A1 (en) | System for accessing database tables mapped into memory for high performance | |
| JPH05128072A (ja) | システム間排他制御方式 | |
| CN114328500B (zh) | 一种数据访问方法、装置、设备及计算机可读存储介质 | |
| CN108694230B (zh) | 数据库中的唯一标识符的管理 | |
| CN111581123B (zh) | 基于分类的存储器分配的锁定 | |
| JP3621433B2 (ja) | データベース排他制御方法 | |
| US20040243624A1 (en) | Undrop objects and dependent objects in a database system | |
| CN118051502B (zh) | 数据库的索引处理方法、装置、设备及可读存储介质 | |
| JP2009265840A (ja) | データベースのキャッシュシステム | |
| US6327597B1 (en) | Method, memory system, and computer program product for implementing lock based delayed space recycle control | |
| JPH05314010A (ja) | 置換対象データの選択方式 | |
| US7107404B2 (en) | Method and system for data processing for controlling a cache memory | |
| JPH02212949A (ja) | オンライン中データベース再編成処理方式 | |
| CN114791913B (zh) | 数据库的共享内存缓冲池处理方法、存储介质与设备 | |
| US8510269B2 (en) | Uninterrupted database index reorganization/movement |