JPS595483A

JPS595483A - 計算装置の動作方法

Info

Publication number: JPS595483A
Application number: JP58085180A
Authority: JP
Inventors: ロバ−ト・ア−サ−・ガマエア; ジヨン・アルバ−ト・モ−テンスン
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1982-06-24
Filing date: 1983-05-17
Publication date: 1984-01-12
Also published as: CA1189979A; US4509119A; JPS6150350B2

Abstract

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

Description

【発明の詳細な説明】〔発明の分野〕本発明はバッファ・プールを含む計算装置を動作させる
方法、特にバッチ・プロセス（順次プロセス）の両者に
よって参照されるバッファ・プールを管理するだめのデ
ータベース・システムに係る。

〔先行技術の説明〕

一般に、トランザクション処理用に設計されているデー
タベース・システムは、バッファをランダム・アクセス
するのに適したバッファ・マネージャを有する。普通、
バッファ・プールはＬＲＵ（Ｌｅａｓｔ　　ＲｅｃｅＴ
Ｌｔｌｙ　Ｕｓｅｄ）アルゴリズムに基づいて管理さね
、ているので、アプリケーションによる後続アクセスの
ために最後に使用されたバッファ内のデータ・ブロック
が使用可能の状態に維持さｔｌ、る。というのは、かか
るデータ・ブロックは最も長い間使用されなかったバッ
ファ内のデータ・ブロックよりも、次にアクセスされる
見込みが大きいとされ、でいるからである。

これは、順次式にデータをアクセスする多くのニーティ
、すケ・イ・およびいくつかのアプリケーションについ
て、性能上の問題を提起する。前記の使用例として、デ
ータベースのバックアップ・コピーをとるユーティリテ
ィがあり、このユーティリティでは大部分のブロックが
順次に検索される。

これらの１１］自次プロセスのためにバッファ・プール
を管理するときけ、新しいブロックの必要性を予測して
外部記憶装置からデータ・ブロックの事前取出しを行な
い、これらのデータ・ブロックを空いているバッファに
読込むことが望ましい。

このような動作は刊行物であるＩ　Ｂ　Ｍ　ＯＳ／ＶＳ
２ＳＡＭ　Ｌｏｇｉｃ，Ｒｅｌｅａｓｅ３．８、”Ｆｏ
ｒｍ　Ｎｏ　　ＳＶ４０−３８３２−１、２ｎｄ　Ｅｄ
ｉｔｉｏｎのＰＰ．１５−５６、１７８−１８１　　に
記述さ力ているＱＳＡＭ（待機順次アクセス方式）バッ
ファリング技法によって実行される。

しかしながら、ＬＲＵアルゴリズムに基づいて管理され
たバッファ・プールに割当てられたデータ・セットのペ
ージがランダム・アクセスおよび順次アクセス・パター
ンを同時に受ける場合には、前記事前取出しは重大な問
題を生じる。一般に、新しいページに対する順次アクセ
スの要求はランダム・アクセスの要求よりもずっと高い
レートで生じ、特に前者が事前取出しを伴なう場合には
そうである。

従って、ランダム・アクセスを遂行するトランザクショ
ンを支援することが不適当となる場合には、所尚のバッ
ファ内でランダム・ページを再アクセスすることができ
なくなり、かくてこのようなランダム・ページを外部記
憶装置から再び読増らねば々ら々いことがある。

これｕ、ＬＲＵバッファ・チェインを通してバッファを
移動するレートが、バッファ再割当要求レートの関数で
あることによって生じる。

要求レートが高ければ高いほど、ＬＲＵ侍行列の先頭へ
の移動が速くなり、従ってバッファの古い内容を再アク
セスしうる時間か短かく々る。

１１１次プロセスによるバッファの独占を阻止するため
に、ＩＢＭ　　ｒＭｓ／ＶＳ　　バーショア１．２　　
１ＳＡＭ１０ＳＡＭバッファ・ハンドラでは、所与のユ
ーザ（すなわち、ランダム・プロセス捷たは順次プロセ
スによって最後に使用されたバッファを該ユーザに割当
てるようにしている（ソース・コード・モジュールＤＦ
ＳＤＢＨ１０、ＤＦ’ＳＤＢＨ２０、ｒ）Ｆ’ＳＤＢＨ
３ＤおよびＤＦＳＤＢＨ４０、特にＤＦＳＤＢＨ２０に
おける特性テーブル内のＰＳＴＬＲ列参照）。しかしな
がら、ＩＳＡＭ１０ＳＡＭバッファ・ハンドラでは、順
次プロセスの性能を強化するために事前取出し能力は与
えら力ていない。

このように、先行技術では、バッファ・プールをＩｌｌ
Ｊ’１次プロセス捷たはランダム・プロセスのいずれか
に専用化することが普通に行われているが、もしバッフ
ァ・プールがこれらのプロセスによって共用されまたな
らば、バッチ・プロセスによってかかるバッファ・プー
ルが独占される傾向があり、かくて断力のランダム・プ
ロセスがデータ・セットのページを再アクセスするとき
不要々入出力動作を必要とする。

従って、バッファ・プールに割当てられたデータ・セッ
トのページに対するランダム・アクセスおよび順次アク
セスが同時に行なわれているようなデータベース・シス
テムでニ、バッファ・ハンドラに、（１）Ｊ＠次プロセ
ス及びランダム・プロセスの両方についてＬ　ＲＵバッ
ファ・プールを管理し、（２）シかも１齢次プロセスに
よるバッファ・プールの独占に起因するランダム・プロ
セスの不要な入出力動作が生じないようにし、（３）同
時にランダム・プロセスの性能ｒ（対する影響を最小限
にして順次プロセスに非同期式の事前取出し卵力を与え
る必要がある。

〔発明の概要〕

本発明にＪ：　Ｊ’ｌ、げ、メイン・プロセッサ、主記
憶装置に設けら力、だ複数のバッファおよび少々くとも
１つの外部ｍ４憶装置を有する計算装置を動作させる新
しい方法がりえられる。

メイン・プロセッサはデータベース・システムの制御下
で動作し、該データベース・システムは外部記憶装置か
らバッファへ読取られたデータ・セットのページを、順
次プロセスおよヒランタム・プロセスの両者による同時
的アクセスのために割当てるようなバッファ・マネージ
ャを含んでいる。

この新しい方法は次のステップによって特徴づけられる
。

（ａ）待行列の値を確立する。

（ｂ）通常のＬＲＵバッファ・チェイン上、前記チェイ
ン上にコピーさカ、たＳ　Ｌ　Ｒ，Ｕ　（順次ＬＲＵ）
バッファ・チェインとを維持する。

（ｃ）　　事前取出しプロセスではないｊ順次プロセス
から解放さ、ｆｌ、たバッファを両方のＬＲＵバッファ
・チェインに置き、そしてランダム・プロセスまたは順
次式の事前取出しプロセスから解放さカ涜バッファを通
常のＬＲＵバッファ・チェインのみに置く。

（ｄ）　５ＬＲＵバツフア壽チエイン中のバッファの数
が待行列の値を越えている場合には、Ｊ１泊次プロセス
のだめのバッファ要求に応答して、ＳＬ’ＲＵバッファ
・チェインカラ先頭ハッファヲスｆ　−／ｌ／し、そう
でない場合は通常のＬＲＵバッファ・チェインから先頭
バッファをスチールすることにより、ネストされた順次
プロセスで使用されるバッファの反復スチールを明止す
る。

この新しい方法は、次のステップによっても特徴づけら
ねる、。

（ｅ）　　データ・セット・ページの要求に応答して、
外部記憶装置からプロセスが定義した事前取出し一帛の
整数倍のデータ・セット・ページを条件付きで非同ｊυ
１式に巾前ＩＩＹ出しする。

更に、本発明によれば、メイン・プロセッサ、主記憶装
置に設けら力た複数のバッファおよび少なくとも１つの
外部記憶装置を有する計算装置が与えられる。メイン・
プロセッサはデータベース・システムの制御下で動作し
、該データベース・システムは外部記憶装置からバッフ
ァへ読取られたデータ・セットのページを１．順次プロ
セスおよびランダム・プロセスによる同時的アクセスの
ために割当てるようなバッファ・マネージャを含んでい
る。この針脚装置は、その特徴として、前記プロセッサ
が（ａ）　　待行列の値を確立し、（ｂ）　　通常のＬ　ＲＵバッファ・チェインと、前記
チェイン上にコピーされた５ＬＲＵバツフア・チェイン
とを維持し、（ｃ）事前取出しプロセスではない順次プロセスかう解
放されたバッファを両Ｌ　ＲＵバッフ７・ｆｘインに置
き、そしてランダム・プロセスまたは順次式の事前取出
しプロセスから解放されたバッファを通常のＬＲＵバッ
ファ・チェインのみに置き、（ｄｌｓＬＲＵバッファ・
チェイン中のバッファ数が待行列の値を越える場合には
、順次ブーｂセスのためバッファ要求に応答して、５Ｌ
ＲＵバツフア・チェインから先頭バッファをスチールし
、そうでない場合は通常のＬＲＵバッファ・チェインか
ら先頭バッファをスチールする手段をそれぞれ備−Ｃお
り、かくてイ・ストされた順次プロセスで使用されるバ
ッファの反復スチールを阻ＩＦする１ようにしている。

この新しい計や装置は更に次の手段によっても特徴づけ
られる。

（ｅ）データ・セット・ページの要求に応答して、外部
記憶装置からプロセスが定義した事前取出量の整数倍の
データ・セット・ページを条件付きで非同期式に事前取
出しする。

〔実施例の説明〕

第１図は本発明に従った計算装置を示す。プロセッサ１
０は、例えば１８Ｍシステム／３７０であり、そのアー
キテクチャ（刊行物である’ＩＢＭＳｙｓｔｅｍ／３７
０　　ｐｒｉｎｃｉｐｌｅｓ　　ｏｆ　　０ｐｅｒａｔ
ｉｏｎ“Ｆｏｒｍ　Ｎｏ、ＧＡ　２２−７０００−６に
説明されている）　ｉｄ　Ｉ　ＢＭ　Ｏ８／ＭＶＳ　　
オペレーティング・システムのようなＯ８の制御下で動
作する。前記Ｏ８の制御下で動作するの１は、バッファ
・マネージャ２０を含むデータベース制御システムであ
る。バッファ・ブール１４ｕグロセソサ１０の仮想記憶
装置内に設けられており、バッファ・マネージャ２０に
よって制御されるとともに、順次プロセス１６およびラ
ンダム・プロセス１８でアクセスされる。バッファ・マ
ネージャ２０の制御下で、プロセス１６および１８によ
って要求されたデータ・セット・ページは外記記憶装置
のデータベース・プール１４に読取られる。

本発明によって、バッファ・マネージャ２０はランダム
・プロセス１８の性能に対する影響を最小限にして順次
プロセス１６の性能を高める。かくて、バッファ・マネ
ージャ２０に含１れる制御ロジックは、バッファ・プー
ル１４に割当てられたデータ・セット・ページへのアク
セスが１順次プロセス１６およびランダム・プロセス１
８によって同時に行なわれる環境で、順次プロセス１６
によるバッファ・プール１４の独占を最小限にするとと
もに、非同期式の事前取出しを与えることにより、外部
記憶装置のデータベース６０に常駐するデータ・セット
・ページが、例えば順次プロセス１６によるそれらのア
クセスを予測してバッファ・プール１４に送り込まれる
ことを可能にする。

データ・セット・ページは、バッファ・プール１４およ
び／または外部データベース３０に存在することができ
る。バッファ・マネージャ２０の制御ロジックは、ラン
ダム・プロセス１８によってアクセスされるページの再
アクセスの確率が、順次アクセス１６によってアクセス
されるページの再アクセスの確率ｉ：りもずっと大きい
、という仮定に基づいている。

第２図において、バッファ・マネージャ２０はバッファ
・プール１４内に２つのＬＲＵバッファ・チェイン、す
なわち通常のＬＲＵバッファ・チェイン３４および順次
式の５ＬＲＵノ（ソファ・チェイン６６を維持する。バ
ッファ・プール１４におけるＬＲＵバッファ・チェイン
６４および５ＬＲＵバツフア・チェイン３６内のバッフ
ァの構成については以下で説明する。バッファ・マネー
ジャ２０によって初期設定された）（ソファ・プール１
４の各々ごとに生成されるバッファ制御ブロック・セッ
トは、１つのＷＰＨ（ウィンドウ・プール・ヘッダ）ブ
ロック４０および複数のＷ（ウィンドウ）ブロック５０
，６０．７０等（図面上は５０．６０および７０のみを
表示）を含み、・（ソファ・プール１４内の各バッファ
ごとに１つのＷブロックか対応する。

第２図のバッファ制御ブロックは、プロセッサ１Ｄの仮
想アドレス空間内に存在する。ＷＰＨブロック４０には
、ＥＱＢ（過剰ウィンドウ・ブロック待行列）ア／力・
フィールド４１（こり、はＥＱＢ４８内の最初のＷブロ
ックに対するポインタを含む）カウント・フィールド４
２（これ１ｓＬＲＵバツフア・チェイン３６上のバッフ
ァ数のカウントを記憶する）、５ＬＲＴＪ順方向アンカ
・フィールド４３（これは５ＬＲＵバツフア・チェイン
６６で先頭のＷブロック６０を指す）、Ｓ　ＬＲＵ逆方
向アンカ・フィールド４４（これはＳ　ＬＲＵバッファ
・チェイン３６で末尾のＷブロック７０を指す）、ＬＲ
Ｕ順方向アンカ・フィールド４５（これ［ＬＲＵバッフ
ソフチェイン６４での先頭のＷブロック５０を指す）、
およびＬＲＵ逆方向アンカ・フィールド４６（これはＬ
ＲＵ）くソファ・チェイン３４での末尾のＷブロック７
０を指す）が含捷れる。

Ｗブロック５０．６０および７０の各々は、それぞれが
６つのフラグ・ビットを含むＷＢ　（Ｗブロック）フラ
グ・フィールド５１．６１および７１を有する。これら
のフラグ・ビットは次の意味を有する（左から右へ）。

ビット１はＷＢがＬＲ・Ｕバッファ・チェイン６４上に
ある場合にオンにセントされ、ビット２け、ＷＢが５Ｌ
ＲＵバツフア・チェイン３６上にある場合にオンにナツ
トさね、ピッ）ｌｊ：Ｗｌｌが１順次プロセスで最後に
使用された場合にオンにセットされる。従って、値１０
０を有するＷＢフラグ・フィールドｓｉｕ、ｗブロック
５０がＬＲＵバッファ・チェイン３４上にアッテ、Ｓ　
Ｌ　ＲＵバッファ・チェイン３６上にすく、カつ順次プ
ロセスで（ランダム・プロセスとは反対に）−Ｃ後に使
用されなかったことを示す。

第２図の例でｄｌ、Ｗブロック５０．６０および７０か
Ｌ　ＲＵバッファ・チェイン３４上にあり、Ｗブロック
６０および７０が５ＬＲＵバツフア・チェイン３６Ｊ＝
にある。バッファ・プール１４でバッファの使用状態が
安定した後は、ＥＢＱ４８は通常は空である。

壕だ、Ｗブロック５０．６０および７０の各々は、４つ
のチェイン・ポインタ・フィールド（ＳＬＲＵ次ポイン
タ、５ＬＲＵ前ポインタ、ＬＲＵ次ポインクおよびＬＲ
Ｕ前ポインタ）を含み、そね、それのフィールドはバッ
ファ・チェーン３４およびＳ　Ｌ　ＲＵバッファ・チェ
イン６６内のＷＢを順方向および逆方向にチェインする
のに使用され、る。

第２図で、ポインタ・フィールド５２．５３．５５．６
３．７２および７４は空白（（セットされており、その
仙のポインタ・フィールドは第２図の矢印に対応する値
を有する。

次に第６図を参照して、Ｗブロック７０の追加フィール
ドおよびその用途について設明する。Ｗブロック７０に
対応するバッファ・ブロックを占有するページの相対ペ
ージ番号が、ＲＰＮ（相対ページ番号）フィールド８０
に含“まれる。

ラッチ・ポインタ・フィールド８１ば、次に説明するよ
うにハツシュ・チェイン探索（ルック・アサイド探索と
も呼ばれる）を直列化するのに用いられる。

ハツシュ・チェイン順方向／逆方向ポインタ・フィール
ド８２は、ＷＰＨブロック４０におけるフィールド（図
示せず）にアシ力さ′ｉ′１だ各々のノ・ソシュ・チェ
インと、同じ値にノｈツシュするＷブロック７０等とを
連結するのに使用される。占有者データ・セット・トー
クン・フィールド８３は、このＷブロック７０に関連す
るバッファを覗在占有しているページのデータ・セット
を、キー々どによって識別するフィールドである。スチ
ール・フラグ・フィールド８４は、複数のユーザが同じ
バッファをスチールするのを阻止するのに用いられ、Ｗ
（ウィンドウ）従属カウント・フィールド８４は、後に
詳Ａ…１に説明するように、ユーザが前記Ｗブロックに
関連したバッファ内のページをゲットおよび解放すると
きに増加され減少される。

ユーザ（プロセス）１６．１８がバッファ・マネージャ
２０からページを要求するとき、この要求されたページ
のデータ・セット・トークンおよびＲＰＮが含まれる。

この値はハツシュ値に・・ツシュされ、そして・・ラン
ス・チェイン順方向／逆方向ポインタ・フィールド８２
によって連結されたすべてのＷブロック７０等が同じ・
・ツシュ値を有するものとして探索される。この動作は
ルック・アサイド探索と呼ばれる。この探索は、当該要
求を一致する占有者データ・セット・トークン・フィー
ルド８６およびＲＰＮフィールド８０を有するＷブロッ
クが見つかる場合に成功する。

再び第２図を参照するに、順次プロセス１６かう解放さ
れたバッファはＳ　ＬＲＵバッファ・チェイン６６の末
尾およびＬＲＵバッファ・チェイ／６４の末尾に置かれ
、ランダム・プロセス１８から解放されたバッファは通
常のＬＲＵバッフソフチェイン３４の末尾にのみ置かれ
る。順次アクセス要求を満足するのに必要とされるバッ
ファは、バッファ・チェイン３６上に存在するバッファ
数が順次スチール限界値Ｑよりも大きい場合には、Ｓ　
ＬＲＵバッファ・チェイン６６の先頭から得られる。さ
もなければ、すなわちもしバッファ・チェイン３６上の
バッファ数がＱよりも大きくなく、また当該要求がラン
ダムプロセス１Ｂによるアクセスのためであれば、バッ
ファは通常のＬＲＵバッファ・チェイン６４の先頭から
得られる。

この論理によると、新しい順次式要求について、順次ア
クセスのために最近に使用されたバッファの力がランダ
ム・アクセスのために最後に使用さ力たバッファよりも
高いスチール優先順位が与えられることになり、しかも
その場合に新しいランダム要求に対するバッファ・スチ
ール優先順位が変更さね、ないので、これにより順次ア
クセス１６の独占作用を削土化することができる。

１１［１’１次スチール限界値Ｑは、順次プロセス１６
が時たまライン外のページ・シーケンスに対ｔ−るネス
トされた順次アクセスを実行しなければならない場合に
、再取出し動作を最小限にするのに使用される。この例
として、基本的には集合するのが時た擾ライン外の（集
合されない）挿入を有する論理的レコード・シーケンス
に続く再構成ニー・テイリテイ（順次プロセス１６）が
ある。

メイン・ライン・７−ケンスで最後に参照されたバッフ
ァはライン外のシーケンス要求を満たすのにスチールさ
れない順向がある。というの幻、ｓＬ　ＲＵバッファ・
チェイン３６が解放されたばかりのメイン・ラインＬＲ
Ｕシーケンス・バッファよりも最近に使用されなかった
十分なバッファを有しない限り、５ＬＲＵが使用されな
いからである。Ｑの合理的な値は、順次プロセスの時点
に最も頻繁に予測されたライン外のネスティングのレベ
ル数と、最も頻繁に予測された同時的な順次プロセスの
最大数との釉として確立されうる。Ｑの値が、例えば４
であれは、合理的な値といえる。

順次プロセス１６がデータベースのデータに対して遂行
されている場合、もＬ−このデータがその実際の使用前
にＤＡＳＤのような外部記憶装置であるデータベース３
０から仮想記憶装置内にあるバッファ・プール１４に、
非同期式に事前取出しされるならば、一定の性能上の利
点を実現回部である。これらの利点として、入出力バッ
チ処理による入出力経路長オーバヘッドの減少およびオ
ーバラップされた入出力による全経過時間の減少かある
。事前取出しは、バッファ・マネージャ２０のページ・
アクセス機能の副次機能として、非同期式に行わ力、る
。

この事前取出しを達成するため、バッファ・プール１４
から必ｊ汐なバッファを獲得し、それらに必要なデータ
ベースのページをロードし、そしてそれらをＬＲＵステ
ータスに解放する非同期式実行ユニットをスケジューリ
ングすることが行わねる。

必ｔなバッファけＳ　Ｌ　ＲＵバッファ・チェイン３６
からの事前取出しによってできるだけ多く取出されるが
、バッファが事前取出しによって解放され、る場合には
、こ力、らのバッファは、ＬＲＵバッファ・チェイン６
４上にのみ置かれ、５ＬＲＵバツフア・チェイン３６上
には置かれない。これは、ライン外のページ・／−ケン
スに対するネストされた１１１次アクセスが必要な場合
に、才だアクセスされていない生前ｉ１ｙ出しされたバ
ッファの再取出しを最小限にするために行なわハ、る。

しかしながら、事前取出しされたバッファは、たとえば
順次プロセス１６による個々のアクセス後の解放時に、
５ＬＲＵバツフア・チェイン３６上に置かれる。

事前取出しされたデータを含むバッファへのアクセスは
、通常のページ・アクセス手順によって行なわハる。本
実施例では、事前取出しされた連続ページ数Ｖゴロ４よ
りも少ない２の累乗である。この値は事前取出し動作を
要求するユーザ（プロセス１６．１８）によって力えら
れる。

事前取出しは、次に示す条件のすべてが満たされた場合
にのみ、バッファ・マネージャ２ｏのページ・アクセス
機能によってスケジュールされる。

（ａｌ　　ユーザは現在要求されているページの１１１
Ａ次プロセスを指示する。

（ｂ）　　事前取出しページ数の値が指定される。

（ｃ）現在要求されているページ数（データ・セットの
最初のページに対する）は事前取出しページ数の値によ
って平等に分割しうる。これは、同じ順次プロセスによ
って同じページに対する複数の事前取出しが初期設定さ
れるのを阻止するのに必要なトラッキングを避けるため
に行なわれる。

（ｄ）　　バッファ・プール１４は再割当可能な十分な
バッファを有しているので、いくつかのバッファを事前
取出しのために使用しても再割当可能なバッファの供給
が完全に枯渇することはない。

（ｅ）　　事前取出しが覗在のデータ・セットの物理的
な境界の外側で牛しることはない。

事前取出しハ親在のページ数＋１で開始する。

事前取出しされる最後のページは次の順次データ・セッ
ト・ページであり、そのページ数は事前取出しページ数
の個によって平等に公害１（回部である。

従ってく・、事前ｒ＋ｖ出しシーケンスが初期設定され
た後は、接続するすべてのページは、このシーケンスが
中断されない１丑でいる限り、アクセス前に事前取出し
される。

第４図を参照して、バッファ・ステータスおよびステー
タス変更について説、明する。ここでは、（ａ）ＯＮ　
　ＥＢＱ、（ｂ）ＡＣＴＩＶＥ、　（ｃ）　Ｉ　Ｎ　Ａ
　ＣＴ　Ｉ　Ｖ　Ｅおよび（ｄ）ＳＴＯＬＥＮの４つの
ステータスが示されている。ＯＮ　　ＥＢＱ　ステータ
スにあるバッファは過剰ウィン１つ・ブロック待行列上
のＥＢＱ４８によって表わされ、このバッファはり在ど
のデータ・ページにも割尚てられないので即時に使用す
ることができる。ＡＣＴＩＶＥステータスにあるバッフ
ァは、１つまたは２つ以上のデータベース・プロセッサ
（プロセス１６．１８）によって使用中であり、・・ツ
シュ・チェイン順方向／逆方向ポインタ・フィールド８
２およびそわらのＷＰＨブロック４０中のアンカによっ
て確立されたルック・アサイド待行列構造によって位置
指定可能でアル。ＩＮＡＣＴＩＶＥステータスにあるバ
ッフアバ、データベースプロセッサ（プロセス１６．１
８）によって使用中ではないが、ルック・アザイド・待
行列構造によって指定可能である。

５ＴＯＬＥＮステータスにあるバッファは、到来する要
求を異なるデータベース・ページへ再割当する準備のた
めに、ルック・アサイド待行列構造から取除かれる。

ステータス変更Ａ１、Ａ２、Ｓ、Ａ３および■の５ステ
ータス変更が第４図に示されている。ステータス１ＮＡ
１は、バッファのステータスがＩＮＡＣＴＩＶＥからＡ
ＣＴＩＶＥに移ることを表わし、これは要求されたペー
ジを含むＩＮＡＣＴＩＶＥバッファがルック・アサイド
待行列構造を介して見つかったときに生じる。

ステータス変更Ａ２に、バッファのステしタスがＥＢＱ
４８からＡＣＴＩＶＥに移行することを表わし、これ附
ルック・アサイド待行列構造で見つからなかったページ
に対する到来する要求を満たすのにバッファが必要とさ
ね５、少なくとも１つのバッファかｌＴｈ　Ｉｓ　Ｑ　
４　Ｂに存在するときに生じる。

前記バッファに１、ルック・アサイド待行列構造に挿入
される。ステータス変更Ｓは、バッファＧ〉データスが
ＩＮＡＣＴＩＶＥから５ＴＯＬＥＮに移行することを表
わす。この状態では、ＩＮＡＣＴＩＶＥバッファはステ
ータス変更Ａ１が生シル前にＬ　ＲＵバッファ・チェイ
ン３４捷たは５ＬＲＵバツフア・チェイン３６の先頭に
移動し、ルック・アサイド待行列イク４造によって見つ
からなかったページに対する到来する要求を満たすため
にＬＲＵ／５ＬＲＵバッファ・チェインおよびルック・
アサイド待行列Ｊｆｌｆ造から現在取除かわ、つつある
。

また、到来するページ要求は、ＥＢＱ４８にバッファが
なかったので、ステータス変更Ａ２によって満足され１
）なかった。ステータス変更Ａ６はバッファのステータ
スが５ＴＯＬＥＮからＡＣＴＩＶＥに移行することを表
わす。スチールさ力たばかりのバッファ（ステータス変
更Ｓ）はアクティブ状態になり、ルック・アサイド待行
列構造に入れられる。ステータス変更■はバッファのス
テータスがＡＣＴ　Ｉ　ＶＥからＩＮＡＣＴＩＶＥに移
行することを表わす。バッファ・ユーザのカウントはＯ
に減少されたばかりで、従って、バッファ１ＬＲＵ／５
ＬＲＵバツフア・チェイン内で（もしあれば）覗１在の
位置から削除され、ＬＲＵバッファ・チェイン６４の末
尾に置かれ、そして恐らくは、５ＬＲＵバツフアΦチエ
イン３６の末尾に置かれる。

以下に示すいくつかの表に、本発明の方法を実行し本発
明の計算装置の特徴を表わす処理手順が擬似コードで表
わされている。当業者には明らかなように、これらの処
理手順を表わすコードは実行回部なコードに容易に変換
可能である。

＼’Ｊ　　　　　　　　　　　　　　　　　　　　　　
ρ壱　　　　　　　　　　　　　　　　　　ト（胃　　
　佃　　　　　　　　　　　　　さ謳　　　　劇　　　
　　　　　　　　　　　１−ヘト　　０　０　０　　　　０　０　０　　　　　　　　
　　　明　　０へＯ＋０＋　へ（イ）寸　　　寸岨へ　　０　　　、　　　、　　　　　　、−　　　Ｆ　
　−・　　　・　　　・　　ウ　　−・　　　。

ｌ（Ｏｏ　Ｏ００ｏ　　　　　　　　　　Ｏ。

ρ ρ　　　　　　　　　　　＋　　　　　　　　　　　ρ
ｌ−１ｔｅ　　　　　　　　　　　１．ｐｒｔ　　　に
）　　　　　　　　　ｒｔ　　に）　　　　　　　　　
ｉ　　国−匡　　　　　　　　　　　　−〇　　　　　
　　　　　　　−匡０　　０　　　　　　　　　　　　
　　　　Ｃ１０００＋Ｏｒ−＋　　　のＯ＋〇− ｅ　　　口　　　「　　　・　　　・　　　＠　　　−
セ　　　・　　　・　　　　・　　　ヘヘ　　　　・０
　　０　　　　　　　　　　　　　　　０　　０　　　
　　　　　　　　　　　　０　　０トく山０　０　　　　　　　　　　（）　　０　　　　　　　
　　　　　　　　　Ｃ１００ｏｏ　　　　　　　　　　
　　１ｊ　　Ｃ１００ｍ＋　　０　　０　　０　　０　
　Ｃ）　　０　　　ＣＩ　　　Ｃ１０Ｃ）　　　０　　
０へ（イ）マ旧Ｃｎωさ。６〜　（イ）寸ｎ（イ）　　
（イ）　　（イ）　　（イ）　　嬶　　哨　　嬶　　（
イ）　　寸　　寸　　マ　　　　　マ　　マ寸０　０　
　０　　Ｃ１００ＣＩ　　０　０　０　　　Ｃ）　　０
　　　　　０　　０　　　。

０　　　　し　　　　　　・＼４蛸ノＯＯ００００００００００００ ω　　ｏ−０−へ　　（イ）　　寸　　叩　　℃　　Ｎ
　　ω　　　　　α　　　　　Ｏ（イ）寸　　寸　　　
　　い　　旧　　い　　の　　叩　　い　い　　旧　　
の　　　　　困　　　　　っ　　で０Ｃ１００００００
Ｃ１）Ｑ００００観　　　　　　　　トへ１へ小　　　　　　　　　　　　　　　　　　　　　　　ｐ
菌　　　　　　　（イ）　　　　　　　　・・　　匡′
＠　　　　　　　０　　　　　　　　　　　　　　　匡
　−與　　　　　　＜　　　　　　　　　　　　　　１
．ｌＱψ　六　　　　Ｅ　　　　　　　　　　　　　　
　　ｐ　°へ’Ｔ’ｆＪ　　　コ　　・−国　　　　　
　　　　　　　　　　　　　国　　。

トＯ匡　ト率　　　　−四゛（ｅ０　　　Ｃ１００＜　　　０　　０寸叩つＮ　　　　に）〇− Ｎ’Ｏ℃　　′Ｏ１＋ト　　　＼０　　０　　０　　０　　　　　　　　　　　　　　　
　　　（θ　　０　０ハ　　　　　　　　　　　　　　
　マＨへ　　　　　　　　る　　ト　　　　　　　　　　　
如　　　　　　　　塑）も　　　　　　　　　　　　′
　　　　　　　八　　ヘ　　　　　　　　　　ム　　　
　　　　へ０　　　Ｃ１０００００００００ＣＩ　　　
０　　０　　０　　０１／ｌ　　　寸　　　　　の　　
”Ｏｒ％　　　の　　　　　（ト）　　０　−　　へ　
　（イ）　　寸　　旧　　’ＯＮ　　ω盆　ヘ　　　　
ハ藝　マ　　　　ト揶ト　藝　観ρ ヤ　　　　　　φ　　　　　　　　　　　　　　で　へ
ギＪ　　　　　　　　　　　　　　　　　　　　肩　　
１トｈ−ｂ　　区率　藝　顯　ＦＬイｊ　　ワト率０　　　０　　　　　　　０　　０　　　０　　　Ｃ）
　　　　０　　　０　　　０　　　０Ｃ’０　−へ（イ
）寸岨℃Ｎの゛（コ　　捲　　　　　　　　　　　　　　　　　　　
ロ　　卯に）　　２く ■ ０　　（）　　０　　　　　　　　　　　　　１−（０
（：ｌ　　０　０　０　　ｏ　ＯＯω　Ｃ１＝　　　　
　　　　　　　　　　Ｑ　　０　−　へ　（イ）　寸　
い　℃　へω　　Ｃ１’　　ＣＩ　　　　　　　　　　
　　　　　Ｚ　　　−？−−一？−’　　”−−「０　
２　−　　　　　　　　　　　　　−　−　−　　豐　
　？−−６「　　−国０　０　０　　Ｃ）　　０　　Ｃ１ｌ、、　　０　０　
　Ｑω　　Ｏ＋Ｃ１亡　　へ　　噂　　　　　　　　　
　　　　　凶　　〇　　−へ、−へへヘヘ　　　　ｌ：
ｌ１８１／１哨のＦ　　！−口　　Ｆ　　−−山　　。

　　７　　ウド　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　ぜヨ　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　（国　　　　　　　　　　　　　　　　
　　　　　　　　　　　　ヰ　　　　′０　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
養　　　　舅　国　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　、°（研　・−ＣＩ
Ｌ、、Ｊ　　絽　４１′−に）率　　　　　　　　　　　印　匡く０　　０　　０　　　　　　　　　　　　　　　　　　
Ａ　　　０　　０　　ＣＩ　　　０　　０　　　ＣＩ　
　　０　　０寸　　的　　ＣＩＪｃ＋　　　−へ　　（
イ）　　寸　　の　　く　　べ（イ）Ｉ／）ｌ／ｌ　　
　　　に）寸寸寸寸寸マ寸寸豐　　口　　「　　　　　
　　　　　　　　　氏　　豐　　セ　　で　　−−口　
　「　　１酬率０　　０　　０　　０　　　Ｃ１０００００００ＣＩ　
　　ＣＩのＯ＋ＯＦへ（イ）寸（ト）−ｏ、■さＯ「へ
寸寸のＬｆ’）叩０唖０００（ト）Ｃ’ＯＣ１６３０　
　　　さもなげれば；１６４０　　終了；

【図面の簡単な説明】

第１図は本発明の環境を表わす計算装置を示す図、第２図は本発明の通常のＬＲＵチェインおよび５ＬＲＵ
チエインを示す図、第６図はＷ（ウィンドウ）ブロックを示す図、第４図は
第１図のバッファ・プールを特徴づけるバッファ状態お
よび状態変化を示す状態図である。１０・・・・ブロセツザ、１４・・・・バッファ・プー
ル、１６・・・・順次フロセス、１８・・・・ランダム
・プロセス、２０・・・・バッファ・マネージャ、６０
・・・・データベース、３４・・・・ＬＲＵバッファ・
チェイン、３６・・・・５ＬＲＵバツフア・チェイン、
４０・・・・ＷＰＨブロック、４１・・・・ＥＱＢアン
カ・フィールド、４２・・・・カウント・フィールド、
４３・・・・Ｓ’　Ｌ　ＲＵ順方向アンカ・フィールド
、４４・・・・Ｓ　ＬＲＵ逆方向アンカ・フィールド、
４５・・・・ＬＲＵ順方向アンカ・フィールド、４６・
・・・ＬＲＵ逆方向アンカ・フィールド、４８・・・・
ＥＢＱｌ　５０・・・・Ｗブロック、５１・・・・ＷＢ
フラグ−フィールド、５２・・・・５ＬＲＵ次ポインタ
・フィールド、５３・・・・Ｓ　ＬＲＵ前ポインタ・フ
ィールド、５４・・・・Ｌ　Ｒ０次ポインタ・フィール
ド、５５・・・・Ｌ　ＲＵ前ポインタ・フィールド、６
０・・・・Ｗブロック、６１・・・・ＷＢフラグ・フィ
ールド、６２・・・・Ｓ　Ｌ　Ｒ０次ポインタ・フィー
ルド、６６゛　・・・・Ｓ　、Ｌ　ＲＵ前ポインタ・フ
ィールド、６４・・・・ＬＲＵ次ポインタ・フィールド
、６５・・・・ＬＲＵ前ポインタ・フィールド、７０・
・・・Ｗブロック、７１・・・・ＷＢフラグ・フィール
ド、７２・・・・５ＬＲＵ次ボイ／り・フィールド、７
６・・・・５ＬＲＵ前ポインタ・フィールド、７４・・
・・ＬＲＵ次ポインタφフィールド、７５・・・・ＬＲ
Ｕ前ポインタ・フィールド、８０・・・・ＲＰＮフィー
ルド、８１・・・・ラッチ・ポインタ・フィールド、８
２・・・・ノ・ツシュ・チェイン順方向／逆方向ポイン
タ・フィールド、８３・・・・占有者データ・セット・
トークン・フィールド、８４・・・・スチール・フラグ
・フィールド、８５・・・・Ｗ従属カウント・フィール
ド。

Claims

【特許請求の範囲】メイン・プロセッサ、主記憶装置に設けられた複数のバ
ッファおよび少なくとも１つの外部記憶装置を含み、前
記メイン・プロセッサはデータベース・システムの制御
下で動作し、該データベース・システムは前記外部記憶
装置から前記バッファに読込まれたデータ・セット・ペ
ージを順次プロセス及びランダム・プロセスの両者によ
る同時アクセスのために割当てるバッファ・マネージャ
を含んでいる計算装置の動作方法であって、（ａｌ　　待行列の値を確立し　　　　　　　　　　　
　　６（ｂ＋　　通常のＬＲＵバッファ・チェインおよ
びそれに複写された順次式Ｌ　ＲＵバッファ・チェイン
を維持し、ｔｅｌ　　事前取出しプロセスではない順次プロセスが
　　　′ア・チェイン及び前記順次式ＬＲＵバッファ・
チェインの両方に置き、且つランダムプロセスまたは事
前取出しプロセスから解放されたバッファを前記通常の
ＬＲＵバッファ・チェインのみに置き、（ｄｌ　　前記
順次式ＬＲＵバッファ・チェイン中のバッファ数が前記
待行列の値を越える場合には、順次プロセスからのバッ
ファ要求に応答して該バッファ・チェイン中の先頭バッ
ファをスチールし、そうでない場合には前記通常のＬＲ
Ｕバッファ・チェインから先頭バッファをスチールし、
それによってネストされた順次プロセスで利用されるバ
ッファの反復スチールを明止するようにしたことを特徴とする計算装置の動作方法。