JPS633351A - バツフア検索制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 外部記憶装置からバッファに読み込んだデータを、その
後の処理でも利用するための、バッファの検索を効率化
する制御方式。

データの識別名のハツシュ関数で索引するテーブルに、
そのデータを保持するバッファへのポインタと、同じハ
ツシュ関数の別のデータが他に保持されているかの表示
とを記録し、あるデータがバッファにあるかを、このテ
ーブルを索引して検索する。

この方式により、バ・ノブァ数が多くなっても、検索を
高速に行うことができる。

〔産業上の利用分野〕

本発明は、計算機システムにおける、外部記憶装置から
バッファに読み込んだデータを、バッファ上で検索する
ための制御方式に関する。

計算機システムにおいて、磁気ディスク記憶装置等の大
容量の外部記憶装置に格納されているデータベース等の
データは、処理に際し所要のデータブロックが主記憶装
置等に読み込まれる。

その場合、外部記憶装置から読み込まれたデータブロッ
クは、主記憶装置の記憶領域に設けられるバッファに保
持されて、要求元のプログラムにアクセス可能にされる
。

〔従来の技術〕

第２図は計算機システムの一構成例を示すブロック図で
ある。

処理装置１は、主記憶装置２にロードされたプログラム
（図示せず）を実行することにより、例えば端末装置３
から入力される要求を受は取って、外部記憶装置４に格
納されているデータベース等にアクセスし、要求された
データの参照、更新等を処理する。

データベースへアクセスを要する場合に処理装置１は、
データベース内の所要のデータブロックを、外部記憶装
置４から主記憶装置２の記憶領域に設けるバッファプー
ル５の１つのバッファ６に読み込んで、処理プログラム
から直接アクセスできる状態にする。

各バッファ６はデータブロックの内容を保持するデータ
１聞７、データ欄７のデータブロックの３餞別名を保持
する識別老樹８、チエインポインタ９等からなる。

データブロックの識別名は、例えばデータセット名とブ
ロック番号からなり、アクセス要求時に要求元によって
指定され、この識別名をアドレスとして外部記憶装置４
へのアクセスを行う。

チエインポインタ９は、このバッファブール５の使用さ
れているバッファ６を例えば使用順に接続したチエイン
を構成するためのポインタで、チエインの先頭のバッフ
ァはレジスタ１０によってポイントされ、各バッファ６
のチエインポインタ９は次のバッファを指し、チエイン
の最後のバッファのチエインポインタ９は例えばＯにさ
れる。

又、このチエイン最後のバッファはレジスタ１１によっ
てポイントされている。

外部記憶装置４からデータブロックが読み込まれた場合
には、バッファプール５の各バッファ６のデータ欄７に
保持され、識別老樹８に識別名が記入され、そのバッフ
ァ６はレジスタ１１でポイントされるバッファ６の後に
つなげられる。

処理中に、あるデータブロックを指定するアクセス要求
が出ると、処理装置１で実行される管理プログラムは、
その処理に割り当てられているバッファプール５を走査
して、指定されたデータブロックが既に読み込まれてい
るか調べる。

コノ走査ハ、バッファの前記の、チエインを先頭からた
どって、各バッファ６の識別老樹８の内容を、要求のデ
ータブロックの識別名と比較して行われる。

識別名の一致する識別名Ｍ！Ｉ８を持つバッファ６がバ
ッファプール５にあれば、そのバッファ６に保持される
データを要求元に渡す。

バッファプール５に無い場合のみ外部記憶装置４へのア
クセスを実行する。その際に空きのバッファ６が無けれ
ば、使用中のバッファの１つを前記のチエインからはず
して使用する。

このようにして比較的長時間を要する外部記憶装置４と
の間のデータ入出力回数を減少することによってシステ
ムの処理効率を高めるようにしている。

〔発明が解決しようとする問題点〕

前記のように、バッファプール５に読み込まれたデータ
をできるだけ利用して、外部記憶装置へのアクセスを減
少する場合に、その効果を高めるには、適当にバッファ
数を多（して、前に読み込んだデータが他のデータで置
き換えられることな（残っている可能性を大きくする必
要がある。

他方、前記の制御から明らかなように、バッファ数の増
加は、所要データの有無を検査するためのバッファ検索
時間の増加に直接つながり、そのためにバッファ数を十
分設けることができないという問題があった。

〔問題点を解決するための手段〕

第１図は、本発明の構成を示すブロック図である。

図において、５はバッファプール、２０はハ。

シュテーブルであり、ハツシュテーブルの２１はポイン
タ欄、２２はタグ欄を示す。

〔作　用〕

前記のように、外部記憶装置４からデータブロックが読
み込まれて、バッファ６に保持され、そのバッファ６が
チエインにつながれるとき、同時にハツシュテーブル２
０が更新される。

ハツシュテーブル２０は、データブロックの識別名から
求める所定のハツシュ関数値をテーブル内相対アドレス
として索引され、各項はポインタ欄２１とタグ欄２２か
らなる。

データブロックの読み込みにおいて、その識別名からハ
・ノシュ関数値を求めて、ハツシュテーブル２０を索引
する。

索引した項のポインタ欄２１がバッファをポイントして
いない状Ｂ（例えばＯ）であれば、使用したバッファ６
のアドレスをポインタ欄に設定し、ポインタ欄２１がバ
ッファをポイントしていれば、タグ欄を例えば１に設定
して、この項に対応する識別名のデータブロックが、バ
ッファプール５に２以上保持されていることを表示する
。

バッファプール５を使用する処理で、あるデータブロッ
クへのアクセス要求が発生されると、指定の識別名から
所定のハツシュ関数値を求めて、ハツシュテーブル２０
を索引する。

索引したポインタ欄２１がＯでなければ、その内容をポ
インタとしてバッファ６にアクセスし、その識別老樹８
を指定の識別名と比較し、−敗すればそのバッファ６を
使用する。

一致しないときは、索引したタグ欄２２を調べ、１なら
バッファのチエインを従来のように走査して、８亥当の
データブロックがあるか８周べる。

以上の何れかにより、バッファプール５で所要データブ
ロックを発見できなかった場合に、外部記憶装置４への
アクセスを実行する。

以上の方式により、ハ・ンシュテーブル２０からバッフ
ァが直接ポイントされる場合には、バッファ数に関わら
ず高速の検索ができるので、バッファ検索時間が平均的
に短縮される。

〔実施例〕

ハツシュテーブル２０は、データブロックの識別名から
求める所定のハフシュ関数値をテーブル内相対アドレス
として索引され、各項はポインタ欄２１とタグ憫２２か
らなる。

ポインタ欄２０はバッファ６をポイントしているとき、
該バッファのアドレスが設定され、例えば０によって、
何れのバッファもポイントしていない状態を示すものと
する。

フグ欄は例えば１ビツトで、１′　によりその項に対応
するハツシュ関数値を生成する識別名を持つデータブロ
ックが、ポインタ欄のポインタで指すバッファ６以外の
バッファ６にも保持されていることを示し、０゛　はそ
れ以外の状態とする。

データブロックの読み込みにおいて、その識別名からハ
フシュ関数値を求めて、ハツシュテーブル２０を索引す
る。

例えば、識別名が４バイト（３２ピント）のデータセッ
ト名と４バイトのデータブロック番号からなる場合に、
データセット名とデータブロック番号の排他的論理和を
、例えば適当な素数Ｎで除した剰余をハフシュ関数とし
、これによりＮ項からなるハツシュテーブル２０にアク
セスするための相対アドレスを得る。

このようにして、比較的長い識別名から、バッファ６を
直接ポイントするポインタを得る手段が、比較的小さな
ハフシュテーブルを使用することによって構成できる。

その結果、テーブルの１項に複数のデータブロックが対
応し得、後に説明するように、同一の項に対応するデー
タブロックが同期間に２以上読み込まれた場合には、第
２以後のデータブロックのバッファは、従来と同様にチ
エインをたどって検索しなければならない。

しかし、適当なテーブル項数（例えばバッファの個数の
２倍程度）を設けることにより、実際に同じ期間に同じ
項に対応する複数のデータブロックが使用される確率を
十分小さくすることができる。

前記により索引した項の、ポインタ欄２１が０（バッフ
ァをポイントしていない状態）であれば、データブロッ
クを読み込んだバッファ６のアドレスをポインタ欄に設
定する。

ポインタ欄２１がＯでない場合には、タグ欄を例えば１
に設定して、この項に対応する識別名のデータブロック
が、バッファプール５に２以上保持されていることを表
示する。

バッファプール５を使用する処理で、あるデータブロッ
クへのアクセス要求が発生されると、指定の識別名から
前記のハツシュ関数値を求めて、ハツシュテーブル２０
を索引する。

索引したポインタ欄２１がＯであれば、該当のデータブ
ロックはバッファに無いので、直ちに適当なバッファ６
を選択して、外部記憶装置４からデータブロックを読み
込む処理を開始する。

即ちこの場合には、チエインを走査する必要無（、利用
できるデータブロックが無いことが識別でき、必要な処
理を開始することができる。

ポインタ欄２１が０でなければ、その内容をポインタと
してバッファ６にアクセスし、その識別老樹８を指定の
識別名と比較し、−致すればそのバッファ６を使用する
。

一致しないときは、索引したタグ欄２２を調べ、Ｏなら
この項に対応するデータブロックが他に読み込まれてい
ない表示なので、外部記憶装置４から読み込む必要があ
る。即ちこの場合にも、チエインを走査する必要無しに
、利用できるデータブ、ロックの無いことを識別ができ
る。

タグ（聞が１なら、イ也のバッファに言亥当のデータブ
ロックがある可能性があるので、バッファのチエインを
従来のように走査し、その結果該当のデータブロックが
あれば使用し、無ければ外部記憶装置４にアクセスする
。

外部記４ｇ装置４にアクセスする場合には、適当なバッ
ファ６を選択して使用する。その際には、そのバッファ
６の識別老樹８の以前の内容により、ハフシュテーブル
２０の該当項を索引して、要すれば更新し、以前の識別
名をハツシュテーブル２０上で無効化し、且つそれに伴
う所要の項のポインタの張り換え等を行う。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、計算
機システムの外部記憶装置から読み込んだデータを保持
するバッファのデータを再利用するためのバッファ検索
において、バッファ数による形容を少なくして、高速の
検索が可能になるので、処理効率改善が増進されるとい
う著しい工業的効果がある。

【図面の簡単な説明】

第１図は本発明の構成を示すブロック図、第２図は従来
の一構成例ブロック図である。 図において、 １は処理装置、　　　　　２は主記憶装置、３は端末装
置、　　　　　４は外部記憶装置、５はバッファプール
、　　６はバッファ、７はデータ欄、　　　　　８は識
別老樹、９はチエインポインタ、１０．１１はレジスタ
、２０はハツシュテーブル、２１はポインタ憫、本発明
の構成を示すブロック図 従来の一構成例ブロック図 第２図

Claims (1)

1. 【特許請求の範囲】 外部記憶装置から読み込んだデータを保持するバッファ
   を有する計算機システムにおいて、該データの識別名の
   所定のハッシュ関数値をアドレスとして索引され、 該データを保持するバッファへのポインタ（２１）と、
   該ハッシュ関数値を生成する識別名を有する２以上の異
   なるデータがバッファに保持されているか否かの表示（
   ２２）とを保持する手段（２０）を設け、前記外部記憶
   装置に保持するデータにアクセスを要する場合に、該デ
   ータの識別名に基づき前記手段（２０）を索引し、 前記ポインタの指すバッファに該データがあるか検査し
   、及び、 該バッファに該データが無く前記異なるデータが保持さ
   れている表示がある場合には、他のバッファを走査して
   該データが保持されているか検査するように構成されて
   いることを特徴とするバッファ検索制御方式。