JPH02294835A - 使用中テーブルの管理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は、コンピューターシステムにおけるデータベー
ス・オブジェクトの回復に関し、具体的には、異常シス
テム終了の後にオブジェクトの迅速な回復を保証するた
めにデータベース・オブジェクトの使用を追跡する使用
中マネージャに関する。

Ｂ．従来の技術 データベース・システムでは、通常は、データベース内
のデータの保全性が維持されることを保証するため、異
常システム終了の後に回復処理が必要である。通常、終
了時に「使用中」であったデータベース・オブジェクト
は選択的回復動作の実行を必要とする。オブジェクトは
、記憶された情報のファイルであり、通常は記憶された
情報を記述するヘッダ・データを含む。ヘッダはまた安
全保護情報も含む。

システムが異常終了した場合にすべてのオブジェクトが
適切に回復されることを保証するため、どのオブジェク
トが使用中であるかに関する情報が中央リポジトリに維
持されることがある。中央リボジトリは通常、使用中テ
ーブルと呼ばれる。そのテーブルは、使用中であったオ
ブジェクトを識別し、回復活動をこうしたオブジェクト
だけに制限するために使用される。そのテーブルが余り
大きくなく、クラッシュの後も信頼でき、かつ重要な競
合源とならないことが望ましい。

どのオブジェクトが使用中であるかに関する情報は、各
オブジェクト自体の内部に維持することが可能であるが
、これは、システム再開時に、各オブジェクトをすべて
２次記憶装置から主記憶装置にベージングし、検査する
必要があるので望ましくない。これは時間がかかり過ぎ
る。もう一つの方法は、オブジェクト・ディレクトリに
使用中状況を記録するものである。これも、探索するデ
ィレクトリがシステム内に多数あることがあり、またす
べてのオブジェクトをディレクトリに入れる必要がある
わけではない（ＩＢＭアプリケーション・システム４０
０／　（ＴＭ）ではそうである。

回復を必要とするオブジェクトのうちにはディレクトリ
に記憶されてないものがある）ので非実用的である。さ
らに、多くのコンピュータ・システムは、滅多に使用さ
れない眠っているオブジェクトを大量に格納している。

オブジェクトが回復処理を必要とするかどうかを決定す
るために、クラッシュに直面してこうしたすべてのオブ
ジェクトを徹底的に検査するのは非効率的である。その
代わりに、潜在的な回復処理のために探索しなければな
らないオブジェクトの数を最小に抑える機構を提供する
ことが望ましい。

ＩＢＭシステム／３８では、使用中テーブルは多くの項
目から構成され、各項目が１つのオブジェクトに対応し
ていた。そのテーブル自体が１つのオブジェクトであり
、単一プロセスでロックすることができた。このため、
テーブルに対して実行される動作が直列化され、システ
ムの大きなネックになる。オブジェクトが高速で繰返し
使用され、また使用から外されるときは特にそうであっ
た。

またこのテーブルは線形方式で探索されていた。

大きなテーブルでは、線形探索は非効率的であった。テ
ーブルが修正される度にテーブルがディスクに書き込ま
れていた。この結果、入出力線上のトラフィックが高率
になった。こうした同期書込み動作は、入出力トラフィ
ックの高い時間には大きなシステムのネックとなってい
た。このテーブルのもう１つの限界は、あるオブジェク
トが使用中であるかどうかしか指示しないことであった
。

単に読取り中のオブジェクトは、変更が行なわれないの
で回復する必要はない。

ｃ、発明が解決しようとする課題 本発明の一目的は、異なるいくつかのプロセッサで走行
する多くの異なるプロセスによるテーブルに対する並行
動作を可能にする、使用中テーブル・マネージャを提供
することである。

本発明の一目的は、どの項目が所与のオブジェクトに関
連するかを迅速に見つける、使用中テーブル・マネージ
ャを提供することである。

本発明の他の目的は、項目が並行して指定されないとき
に利用可能なフリー・テーブル項目を効率的に見つける
ことである。

本発明の他の目的は、テーブルに対する入出力活動を最
小にすることである。

本発明の他の目的は、使用中のオブジェクトに対する不
必要な回復動作を回避することである。

Ｄ．課題を解決するための手段 単一のシステム規模のテーブルはスロットを存し、各ス
ロットは、マシンが突然に終了した場合に各オブジェク
トがどの潜在的な回復動作を受けなければならないかを
示すのに十分な情報とともに、使用中のオブジェクトの
アドレスを含んでいる。各スロットは、データベース・
オブジェクトやファイルなど１つのオブジェクトに対応
する。

データベース・オブジェクトが少なくとも１回使用され
ると、それは好ましい同期点としてテーブル中のスロッ
トに割り当てられる。同期点とは、そのオブジェクトに
関する動作が記憶されるスロットである。そのオブジェ
クトが使用されなくなった期間でも、そのスロットはそ
の好ましい同期点のままである。使用中テーブルに戻る
直接のリンクをもたらすため、スロット・アドレスがオ
ブジェクトのヘッダ中に含まれている。

使用中マネージャは、個々のスロットをロックするのに
使用される。個別ロック動作により、１つのオブジェク
ト用のテーブルの使用を試みる任意の１つの処理が、他
の処理からテーブル全体をロックすることが防止される
。使用中テーブル・マネージャはまた効率的なスロット
割振り機構を利用する。以前に使用されなかった新しく
作成されたオブジェクトは、ゼロの使用スロット・アド
レスを有する。こうしたオブジェクトを使用しようとす
る最初の試みの際、アドレスがゼロであるため、使用中
テーブル・マネージャが好ましいスロットをこのオブジ
ェクトに割り当てる。スロット選択処理は、オブジェク
トの仮想アドレスをスロット・アドレスにマップするこ
とにより実施される。オブジェクトの識別子であるセグ
メント■Ｄは、仔効な使用中テーブル項目のアドレスを
作成するハッシュ機能によってマップされる。これは、
オブジェクトのヘッダに記憶される。いくつかのオブジ
ェクトが同じ位置にハッシュするので、さらにスロット
を割り振る方法は、２次記憶装置から主記憶装置へとテ
ーブルのページをさらに検索するのを回避するために、
データの同じページにスロットを割り振ろうとする試み
を含んでいる。

テーブル・マネージャはまた、使用中テーブルのサイズ
を変更する方法ももたらす。コンピュータ・システムの
寿命を通じて、同時に使用中のデータベース・オブジェ
クトの数は大きく変動する。

テーブル・マネージャは、記憶資源を効率的に割り振り
、システムの性能を改良するために、テーブルを縮小及
び拡大することができる。テーブルが小さくなりすぎな
いようにするために、テーブル・サイズの活動記録が保
持される。オブジェクトのヘッダ中でテーブルの現在の
サイズより大きなスロット・アドレスに遭遇した場合、
そのアドレスは、それがゼロである場合と同様に処理さ
れて、新しいアドレスが生成される。

２次記憶装置（ディスク・ドライブなどの直接アクセス
記憶装置ＤＡＳＤ）の動作の合計数を最小にするために
、無関係のスロット修正が単一の入出力要求として束ね
られる。マネージャはまた、本当に修正されているオブ
ジェクトと単に読み取られているだけのオブジェクトを
区別する。オブジェクトの実際の修正の前に、必要なら
、使用中テーブルの適切な部分が２次記憶装置に吉き込
まれる。

使用中マネージャは、多くの処理が多くのオブジェクト
で並行して動作できるようにする機能をもたらす。スロ
ット中のカウンタは、現在あるオブジェクトにアクセス
している処理の数を示すために使用される。それらの処
理は、複数のプロセッサ上に存在することができる。す
なわち、使用中マネージャは、並列処理環境によく適し
ている。

Ｅ．実施例 Ｅ−１　　概要 本発明の論理形式の構成図を第１図に１０で一般的に示
す。データベース・ファイル１２、１４など複数のオブ
ジェクトが、データベース情報を含んでいる。オブジェ
クト１２、１４は、カプセル化されたデータであること
が好ましい。このカプセルは、データを記述する情報を
含むヘッダ１６、１８を含む。ヘッダ１６、１８は、そ
のオブジェクトがデータまたはプログラミングまたは様
々な形式の情報を含むことを示すことができる。

ＩＢＭシステム／３８及びアプリケーション・システム
／４００は、それらが処理する情報の大半をオブジェク
トの形にカプセル化する。オブジェクトは、１つまたは
複数の５１２バイト・ページに記憶される。そのページ
は通常２次記憶装置１７上に存在しており、記憶装置管
理ブロック２０により周知の方式でメモリ及びプロセッ
サ１９との間でページングされる。アドレス方式は、単
一の仮想アドレス範囲が２次記憶装置１７のすべてに使
用されるという、単一レベル記憶形式のものであること
が好ましい。メモリ・ブロック１９は、プロセッサ及び
メモリ１９のラベルがつけてある。

これは、プロセッサの記憶装置に存在しそのプロセッサ
中で実行されるプログラムとデータの論理表示として使
用される。

複数のプロセス２１、２２、２４が、データベース・フ
ァイルの探索やそこでのデータの更新などの作業を実行
するため、オブジェクトにアクセスする。プロセスは、
プロセッサ及びメモリ１９、並びに２次記憶装置１７に
接続されたプロセッサ２６、２７、２８にも存在する。

オブジェクトにアクセスするため、任意のプロセッサに
存在するプロセスは、使用中マネージャ３０を呼び出し
、オブジェクトの仮想アドレスと実行すべき動作のタイ
プを供給する。使用中マネージャ３０は、オブジェクト
が１つまたは複数のプロセッサによって使用されている
かどうかに関する情報を含む複数のスロット３４を含む
使用中テーブル３２を生成して維持する。プロセスから
呼出しを受け取ると、使用中マネージャ３０は、仮想ア
ドレスを用いてオブジェクト１４のヘッダにアクセスし
、スロット・アドレス１８を含むフィールドを見る。

スロット・アドレスがゼロの場合、使用中マネージャは
、使用中テーブルのスロット・アドレスに到達するため
、オブジェクトの仮想アドレスのハッシュを実行する。

そのアドレスがオブジェクト・ヘッダに挿入されて、使
用中テーブルの好ましいスロットまたは項目を識別する
。このスロットは、好ましい同期点として動作する。使
用中状況の変更に関する次の活動は、そのオブジェクト
上で使用中動作を実行する前に、このスロットをロック
する。

他の普通のハソシュの場合と同じく、複数の仮想アドレ
スが単一のスロット・アドレスにマップされる。次いで
使用中マネージャは、オブジェクトの仮想アドレスをス
ロット項目に挿入し、そのオブジェクトが使用中である
ことを示すフラグをセットする。そのオブジェクトがプ
ロセスによって修正される可能性がある場合、スロット
項目の更新フラグがそう指示するようにセットされる。

異常システム終了の場合、このフラグは、オブジェクト
が正確であることを保証するため、回復中に使用されて
、どのオブジェクトが回復動作を必要とするのかを示す
。

スロットが使用中マネージャによってアクセスされる間
、そのスロットは、他の処理による使用からロックされ
る。使用中テーブルの各ページに３２バイト（１バイト
当り８ビット）のスロ，ントが１６個ある。ページ上の
どのスロットがすでに占有されているかを示す、使用中
マネージャによってセットされるビット・マップも各ペ
ージにある。

２つのオブジェクトが同じスロットにハッシュする場合
、可能ならそのオブジェクトの１つが同じページ上の新
しいスロットに割り当てられる。ビット・マップは、ど
のスロットが利用可能かを検査するために使用される。

同じページに利用可能なスロットがない場合、使用中テ
ーブルの上端のヘッダ４０は、利用可能なスロットを有
するページの別のマップを含む。使用中マネージャ３０
はまた使用中テーブル３２のサイズも制御する。使用中
マネージャ３０は、テーブルの使用量に基づいてスロッ
トを追加するが、空間を節約するため、使用中テーブル
の使用が減少するにつれてスロットの数を減らすことが
できる。その結果、使用される資源割振りの柔軟性が増
大して、システムの性能が向上する。

好ましい実施例では、テーブルは、オブジェクトが現に
使用されていない間、ＩＰＬ（初期プログラム・ロード
）中にのみ縮小できる。縮小を最小にするために、過去
３回のＩＰＬ中のテーブルの最高サイズの十分な活動記
録が維持される。平均サイズは、次のＩＰＬでテーブル
をどれくらいの大きさにすべきかを決定するために使用
される。

けれども、時々、テーブルの縮小を行なうことができる
。

テーブルがその現サイズより大きかったときに、好まし
い同期スロットが、既に割り当てられていた可能性があ
る。したがってテーブルを縮小すると、その好ましい同
期スロット・アドレスがもはやテーブルの境界内にはな
いようなオブジェクトが、生じることもある。これは、
それがゼロである場合と同様に、無効な使用中アドレス
として処理される。そのオブジェクトＩＤが新たにテー
ブル項目にハッシュされ、その項目がロックされる。

テーブルを拡大する場合、そのテーブルに対するすべて
のアクセスがロックされる。次に、使用中マネージャは
、まだ割り当てられていないスロットがもはや見つから
ないとき、さらに３２Ｋの記憶域を求める要求を記憶管
理ブロック２０に出す。

要求された記憶域を受け取ると、ヘッダ中のテーブルの
サイズが更新されて、テーブル全体に及ぶロックが解除
される。

ハッシュ関数は、レコード１ないしＭのテーブル項目ア
ドレスを生成する。ただしＭは使用中テーブルの最小サ
イズ（後で行なわれる拡大の前にＩＰＬ中にそのテーブ
ルに割り当てられたサイズ）の最後の項目である。すな
わち、使用中テーブルがその後に拡大した場合でさえ、
ハッシュ関数は、好ましい同期点を第１の割振りの内部
に完全に存在するスロットにマップする。この実施によ
り、すべてのユーザが、基本となる使用中テーブルの現
サイズに関わらず、この同期スロットの好ましい位置に
同意することが保証される。

ハッシュ関数の望ましい特性は、オブジェクトＩＤを最
初に割り振られた使用中テーブル項目にほぼ均一にマッ
プすることである。これは、下記の単純な乗法的合同ハ
ッシュ関数を用いて実現できる。オブジェクトＩＤに大
きな素数をかける。

次に、この積を使用中テーブルの初期割振りのサイズで
割る。

ＨＡＳＨ（オブジェクトＩＤ）＝（オブジェク｝ＩＤ＊
素数）ｍｏｄｕｌｏ初期割振り複数のデータベース・オ
ブジェクトが同し同期スロットにハッンユできるので、
初期テーブル・サイズが、使用中になっているオブジェ
クトの間でどのぐらい競合が見られるかについての決定
的な要因となる。この実施態様では、１００８項目とい
う初期テーブル・サイズを使用した。この場合、使用中
テーブル上で最高１００８の並行動作が可能である。テ
ーブルの初期サイズは、３２Ｋバイトに選択する。これ
は、単一の入出力動作で２次記憶装置に古き込める最高
量とも対応する。

３２Ｋバイト記憶域をもう１つテーブルに追加すると、
実際には１０２４個の新しいスロットが追加される。と
いうのは、追加の３２Ｋバイト記憶域には新しいテーブ
ル・ヘッダは不必要であるからである。コンピュータ・
システムの性能特性に応じて、他のテーブル・サイズも
本発明の籟囲内に含まれることは明らかである。

ヘッダ４０はまた、オブジェクトに対する実際の変更の
前に２次記憶装置に古き込むべきスロットの範囲を示す
下限ポインタ４２と上限ポインタ４４も含む。これらの
ポインタは実際にはヘッダ４０に存在するが、図では、
スロットの範囲を示すため実際のスロットを指すように
なっている。

言い換えれば、この範囲外のスロット中のデータは、そ
のテーブルが最後に２次記憶装置に書き込まれて以降に
変更されなかった（更新フラグがＯないし１に変更され
ていない）。この機構により、使用中テーブルに対する
各修正ごとに入出力動作を必要とするのではなく、単一
の入出力動作で使用中テーブルの最近修正されたすべて
のスロットを単一バンドルとして書き込むことが可能と
なる。

ヘッダはまた、実行が計画されているディスク書込みを
識別する入出力開始番号も含む。これらの計画された開
始は、個々のスロット中の項目内に存在する対応する入
出力開始番号と調整される。

使用中マネージャによる入出力開始番号と項目の比較に
よって、とのスロットがすでに２次記憶装置に書き込ま
れたかが明らかになる。

使用中テーブル・マネージャにより、多くの動作が並行
して動作可能となる。使用中動作がオブジェクトの代わ
りになるので、同期の目的で、使用中テーブルの特定の
項目（項目とスロー／　｝はこの説明では同じ意味で使
用する）にそのオブジェクトをマップすることが可能で
ある。次に、この対応するテーブル項目を排他的にロッ
クすると、他のプロセスがこの同期点を同時に使用でき
なくなる。

使用中マネージャの高レベル流れ図が第２図に示されて
いる。要求された機能に応じて、情報を使用中テーブル
から検索し、あるいはそこに記憶する。たとえば、Ｉ？
’ＩＮＤ動作はテーブルから情報を検索するだけであり
、ＩＮＣＲ（増分）動作は追加情報を使用中テーブルに
入れさせる。使用中動作の結果を記述する戻りコードが
、その動作を要求するプロセスに戻される。ＦＩＮＤ動
作は、オブジェクトの使用中状況に関する情報を問い合
わせるために使用される。ＩＮＣＲは、オブジェクトを
使用中にするために使用される。そのオブジェクトがす
でに使用中である場合、テーブル項目またはスロットの
使用カウントが、１だけ増分される。ＤＥＣＲ　（減分
）機能はＩＮＣＲ機能の逆である。これは、使用中テー
ブル・スロットによって参照されたオブジェクトの現ユ
ーザの削減を記録するのに使用される。

使用中テーブル・マネージャの主な任務は、テーブルの
揮発性の主記憶装置コピーに追加されたすべてのオブジ
ェクトが、システムのクラッシュ後にテーブルのＤＡＳ
Ｄコピーに現れるようにすることである。テーブルは主
記憶装置で修正されるので、新しく割り振られた使用中
の項目を非揮発性記憶装ほに書き込まなければならない
（強制するとも言う）。この動作を、項目の保証と言う
。

使用中マネージャは、最小の入出力動作及びテーブル上
の資源競合でこれらの機能を実行する。本明細書では、
揮発性記憶装置とは、内容を失うことがあり得る記憶装
置を言う。重要なことは、２次記憶装置が使用中テーブ
ルのバックアップ・コピーとして使用できることである
。

Ｅ−２　　ロック方法 使用中テーブル・マネージャは、テーブルの各項目内に
存在するロック・フィールドを使用して、スロットが一
時に１つの処理によってしかアクセスされないようにす
る。項目の四式は第３図に示されており、後で説明する
。これを項目のロックと言う。そのフィールドは次の２
つの値を持つ。

ロック（Ｌｏｃｋｅｄ）　　一　ある処理が同期のため
にこの項目を使用している。非ロック（　Ｏｎ　ｌｏｃ
ｋｅｄ　）項目がどの処理によってもロックされていな
い。僅かなオーバーヘッドのみで高レベルの並行性を実
現するため、データに対して原子的動作（複数ＣＰＵ環
境で、あるＣＰＵによるこうしたロック・フィールドの
修正が、部分的に完了した状態では隣接するＣＰＵから
決して見えないような、分割不能に見える動作）を実行
するハードゥエア命令を利用する。項目のロック・フィ
ールドを検査して変更する好ましい方法は、こうした命
令（アプリケーション・システム／４００プロセッサで
は半ワード比較後交換（Ｃｏｍｐａｒｅ　ａｎｄ　Ｓｗ
ａｐ１１ａ　Ｉｆ　ｗｏｒｄ）命令と呼ばれている）を
使用して、ロック・フィールドを修正する。同じく良好
な別法は、一部のハードウェア・プラットフォームで利
用できるテスト後セット（Ｔｅｓｔ　ａｎｃｌ　Ｓｅｔ
）命令を使用するものである。複数処理環境において記
憶装置オペランドの分割不能な検査及び設定を実行する
、同様の命令が、大半の現代のコンピュータ・システム
及びマイクロ・プロセノサに存在する。

比較後交換命令は、項目のロック・フィールドの値を検
査するために使用される。下記の表１には、擬似コード
を使って、比較後交換ハードウェア命令がどのように動
作するかを示す。ハードウェアは、変数”ａ“゜に対し
て同時に実行される比較後交換命令の数を１つに制限す
る。すなわち、変数へのアクセスは、破壊的な干渉が許
されないようにすべてのＣＰＵにわたって直列化される
。この命令は原子的であり、割込み可能でない。

表１ ｐｒｏｃｅｄｕｒｅ Ｃｏｍｐａｒｅ　　ａｎｄ　　ｓｗａｐ　　（ａ．　　
ｗｅｔｈｉｎｋ，　　ｖｅｖａｎｔ，　　ｒｃ）｛ａは
原子的に動作されている記憶装置の位置である｝（ｗｅ
ｔｈ　ｉｎｋは、変数ａが含むと想定される値である）
｛ｗｅｗａｎｔは、下記の場合に変数ａをそれに設定し
たい新しい値である｝ ｛ａがｖｃｔｈｉｎｋに等しい｝ ｉｆ　ａ　＝　ｗｅｔｈｉｎｋ ｔｈｅｎ ｂｅＦＳｉｎ ａ　　：＝　　ｗｅｗａｎｔｉ ｒｅ　：＝　ｃｏｍｐａｒｅ　ａｎｄ　ｓｗａｐ　ｓｕ
ｃｃｅｓｓｆｕｌ；（ｒｅは戻りコードである｝ ｅｎｄ ｅｌｓｅ ｂｅｇｉｎ ｖｅｔｈｉｎｋ　　：＝　　ａ； ｒｅ　：＝　ｃｏｍｐａｒｅ　ａｎｄ　ｓｗａｐ　ｆａ
ｉｌｅｄ；ｅｎｄ ｅｎｄ　Ｃｏｎ＋ｐａｒｅ　ａｎｄ　ｓｗａｐｉ　　：
下記の表２に示す擬似コードは、テーブル項目のリト他
的制御を獲得する論理を記載したものである。排他的制
御が達成されると、その項目はロックされたと言われる
。ｅｎｔｒｙ　　ａｄｄｒｅｓＳ→ロソクという表記は
、ポインタ値（ｅｎｔｒＹ　　ａｄｄｒｅｓｓ）の参照
解除を意味し、ｅｎｔｒｙ　　ａｄｄｒｅｓｓと呼ばれ
る変数によってアドレスされる使用中テーブル項目の好
ましい同期スロット内に存在するロック・フィールドに
対するアドレス可能性を与える。以下のコードでは、リ
テラル“Ｌｏｏｋｅｄ″はスロットの１つの状態を表し
、リテラル″Ｕｎｌｏｃｋｅｄ″ハ他方の状態を表す。

表２の論理は、（あるオブジェクトに対する好ましい同
期スロットなどの）使用中テーブル項目の排他的制御を
獲得する方法を示している。

表２ ａｃｑｕｉｒｅ　ｅｎｔｒｙ　：　ｐｒｏｃｅｄｕｒｅ
　（ｅｎｔｒｙ　ａｄｄｒｅｓｓ）ｃｏＬＩｌｐａｒｅ
　ａｎｄ　ｓｗａｐ　（ｅｎｔｒｙ　ａｄｄｒｅｓｓ　
＝　ｌｏｃｋ，　ｕｎｌｏｃｋｅｄ，ｌｏｃｋｅｄ，　
ｒｅ） ｗｈｉｌｅ　（ｒｅ　＝　ｃｏｍｐａｒｅ　ａｎｄ　ｓ
ｗａｐ　ｆａｉｌｅｄ）ｂｅｇ　ｉ　ｎ ｄｅｌａｙ　ｔａｓｋ　ｂｒｉｅｆｌｙ；ｃｏｍｐａｒ
ｅ　ａｎｄ　ｓｗａｐ　（ｅｎｔｒｙ　ａｄｄｒｅｓｓ
→ｌｏｃｋ，ｕｎｌｏｃｋｅｄ，　ｌｏｃｋｅｄ，　ｒ
ｅ）ｉｅｎｄ ｅｎｄ　ａｃｑｕｉｒｅ　ｅｒ＋ｔｒｙ次の表３の論理
は、使用中テーブル項目のリ１：他的制御を放棄する方
法を示したものである。このルーチンは、処理を呼び出
すことにより項目がすでに排他的に保持されており、し
たがって比較後交換の成否の検査が不要な場合にのみ使
用される。

表３ ｒｅｌｅａｓｅ　ｅｎｔｒｙ　：　ｐｒｏｃｅｄｕｒｅ
　（ｅｎｔｒｙ　ａｄｄｒｅｓｓ）ｃｏｍｐａｒｅ　ａ
ｎｄ　ｓｗａｐ　（ｅｎｔｒｙ　ａｄｄｒｅｓｓ　＋ｌ
ｏｃｋ，　ｌｏｃｋｅｄ，ｕｎｌｏｃｋｅｄ，　ｒｃ） あるオブジェクトに対する「適切な」項目の制御を得る
ための手順を表４に示す。それが「適切な」スロットと
呼ばれるのは、データベース・オブジェクトに関する回
復情報を収容するスロットの位置に関する第１印象を改
訂する必要があるかもしれないためである。たとえば、
これまで一度も使用中になっていない２つのオブジェク
トが両方とも同じスロットにハッシュしたときに何が起
こるか考えてみる。第１の要求側にスロットを許可し、
第２の要求側にこのオブジェクトに対する好ましい同期
スロットになると考えられる位置をその後に改訂するよ
うに伝えることにより、この衝突が処理される。スロッ
ト・マネージャが実行する改訂は、オブジェクト・ヘッ
ダ内に存在するゼロ・スロット・アドレスを改訂済みス
ロットノアドレスで置き換えることから成る。元のゼロ
・スロット・アドレスをサンプリングしたどの並行実行
ジョブも、最初オブジェクト・アドレスをハツシュする
ことによって元のスロットをロックしようと試みるが、
その間に好ましいスロット位置が改訂されたことを発見
するだけである。その結果、高並行性環境では、「適切
な」スロットであると想定したスロットをロックしても
、ロックを獲得した後に「好ましい」スロットが今は他
の場所に存在することを発見するだけになることが時々
起こる。下記の擬似コードは、この状態を処理するため
に設けられている。この機構を使用することにより、高
度の並行性が支援され、データベース・オブジェクト・
レベルでのアクセスの直列化は不要となる。好ましいス
ロットが他の場所に存在することを発見する状況を処理
するため、そのオブジェクトが繰り返しある項目にマッ
プされることに留意されたい。使用中マネージャは、テ
ーブル項目のアドレスが、好ましいスロットを識別する
ためにハッシュされたオブジェクト・アドレスと一致し
ないことを発見する。この機構は、一定の性能上の利益
をもたらす。

表４ ａｄｄｒｅｓｓ） ｓｙｎｃｈ　ｅｎｔｒｙ　ａｄｄｒｅｓｓ　：＝　Ｎｉ
ｌｉＭａｐ　ｏｂｊｅｃｔ　ｔｏ　ｅｎｔｒｙ　（ｏｂ
ｊｅｃｔ　ｉｄ，　ｏｒｉｇｉｎａｌ　ｅｎｔｒｙａｄ
ｄｒｅｓｓ） 〔「好ましい」スロットの位置に関する初期印象をもた
らす｝ Ｃｏｎｃｕｒｒｅｎｔ　ｓｕｃｃｅｓｓ　：＝　ｆａｌ
ｓｅ；Ｒｅｐｅａｔ ａｄｄｒｅｓｓ）　； ｛これは上記の繰返しマソピングであり、オブジェクト
が依然として同じスロットを指しているかどうかを明ら
かにする｝ ｉｆ　｛オブジェクトがもはや上記でロックされた項目
にマップしない｝ ｓｙｎｃｈ　ｅｎｔｒｙ　ａｄｄｒｅｓｓ　Ｏ　ｏｒｉ
ｇｉｎａｌ　ｅｎｔｒｙ　ａｄｄｒｅｓｓｔｈｅｎ Ｒｅｌｅａｓｅ　ｅｎｔｒｙ　（ｏｒｉｇｉｎａｌ　ｅ
ｎｔｒｙ　ａｄｄｒｅｓｓ）ｉｏｒｉｇｉｎａｌ　ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ　：＝　ｓｙｎｃｈ　ｅｎｔｒ
ｙ　ａｄｄｒｅｓｓ；Ｅｌｓｅ　｛同期項目は移動しな
かった｝Ｃｏｎｃｕｒｒｅｎｔ　ｓｕｃｃｅｓｓ　：＝
　ｔｒｕｅ；Ｕｎｔｉｌ　ｃｏｎｃｕｒｒｅｎｔ　ｓｕ
ｃｃｅｓｓ　＝　ｔｒｕｅ　ｉＥ−３　　使用中テーブ
ルの動作 本年では、並行環境で使用中テーブルに対して動作を実
行する方法について説明する。

ＦＩＮＤ動作は、使用中マネージャが特定のオブジェク
トに対する情報をテーブルから検索するために使用する
。重要なことは、この動作が、使用中テーブルを求めて
競合している他のジョブまたは処理に対する衝撃を全体
として最小限に抑え、その状況を求めている特定のデー
タベース・オブジェクトの使用中状況を変更することを
求めている他のジョブまたは処理に対する衝撃を低く抑
えて、実行されることである。下記の表５の擬似コード
はＦ　Ｉ　ＮＤの方法を示したものである。オブジェク
ト・ヘッダのスロット・アドレスを使用するか、または
ゼロの場合、好ましいスロット・アドレスにハッシュす
ることにより、まずスロットを見つける。そのスロット
は、ＦＩＮＤ動作の実行中口・ソクされる。

表５ Ｐｒｏｃｅｄｕｒｅ　Ｉｎ　Ｕｓｅ　Ｆｉｎｄ　（ｏｂ
ｊｅｃｔ　ｉｄ，　Ｖａｒ　Ｅｎｔｒｙ　ｉｎｆｏ，Ｆ
ｉｎｄ　ｒｅｔｕｒｎ　ｃｏｄｅ） Ｃｏｎｃｕｒｒｅｎｔ　ｌｏｃｋ　（ｏｂｊｅｃｔ　ｉ
ｄ，　ｅｎｔｒｙ　ａｄｄｒｅｓｓ）ｉｉｆ　ｅｎｔｒ
ｙ　ａｄｄｒｅｓｓ　＋　Ｅｎｔｒｙ．ｏｂｊｃｃｔ　
ｉｄ　＝　ｏｂｊｅｃｔ　ｉｄ〔使用中テーブルで参照
されたスロットが、データベース・オブジェクトについ
て何か知っている｝ｔｈｅｎ ｂｅｇｉｎ ｛この項目に対して使用中テーブルで見つかった情報を
ユーザに戻す｝ Ｒｅｔｕｒｎ　ｅｎｔｒｙ　ｉｎｆｏ　（ｅｎｃｔｙ　
ａｄｄｒｅｓｓ，　ｅｎｔｒｙ　ｉｎｆｏ）Ｆｉｎｄ　
Ｒｅｔｕｒｎ　ｃｏｄｅ　：＝　Ｆｉｎｄ　ｓｕｃｃｅ
ｓｓｆｕｌ；ｅｎｄ ｅｌｓｅ Ｆｉｎｄ　Ｒｅｔｕｒｎ　ｃｏｄｅ　：＝　Ｎｏｔ　ｉ
ｎ　ｔａｂｌｅ；Ｒｅｌｅａｓｅ　ｅｎｔｒｙ　（ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ）処理が、オブジェクトの使用
を始めるときに、使用中マネージャが呼び出されてＩＮ
ＣＲ（使用カウント増分）動作を実行する。そのオブジ
ェクトがすでに使用中ではなくなっていた場合、第３図
に５０で示す新しいテーブル項目がそのオブジェクトに
割り振られて、１の使用カウント５８で初期設定される
。一方、オブジェクトが他の処理によってすでに使用中
である場合は、ＩＮＣＲ動作は、ただスロット・アドレ
スを用いて、事前に存在する好ましいスロットにマップ
して、そこに記憶されたカウント５８を増分するだけで
ある。使用カウントに関する０から１及び１からＯへの
遷移だけが、オブジェクトの回復状態の真の変化を意味
する。クラッシュに直面して十分な回復情報を提供する
ために、このＯから１への遷移が、非揮発性２次記憶装
置に効率的に到達しなければならない。０から１への遷
移が行なわれるときは、更新フラグ６４もスロット項目
中でセットされる。

実際の回復処理は本発明の一部ではないことに注意され
たい。使用中テーブルは、回復が必要なオブジェクトを
識別するために使用される。このテーブルは、異常シス
テム終了の後のＩＰＬ中に使用される。すなわち、重要
なのは、スロット項目がオブジェクトの実際の変更より
前にＤＡＳＤに書き込まれることである。

単一レベル記憶マシンの好ましい実施態様では、オブジ
ェクト識別子（ＩＤ）６０は、単なるオブジェクトのア
ドレスである。多レベル記憶マシンでは、これは単にフ
ァイル名などの識別子でもよい。更新フラグ６４は回復
中に、オブジェクトが特殊な回復活動を実行する必要が
あるかどうかを決定するために使用される。更新フラグ
がオンである場合、オブジェクトの回復が実行される。

ロック・フラグ６６は、その項目がどの時点でも複数の
処理によって変更されないようにするために使用される
。これは、表２と表３に記載した項目獲得機能及び項目
解放機能によって使用される。

入出力カウント６８は、項目の変更の後に、その項目が
２次記憶装置に書き込まれたかどうかを決定するために
使用される。これらのフィールドについては、後節でよ
り詳しく説明する。

下記の表６の擬似コードは、オブジェクトの使用カウン
トを増分するために使用される方法を示したものである
。実際のＩＮＣＲ機能で遭遇するケースは３つあり、そ
れらを、表７、表８及び表９に示す。下記の各表では、
同期項目という短縮句を用いて、ほかの所では好ましい
同期スロットと呼ぶ項目を指す。

表６ Ｐｒｏｃｅｄｕｒｅ　ＩＮＣＲ　（ｏｂｊｅｃｔ　ｉｄ
，　ｅｎｔｒｙ　ｉｎｆｏ）Ｒｅｐｅａｔ　｛ｌｏｏｐ
　ｕｎｔｉｌ　ａｎ　ｅｎｔｒｙ　ｉｓ　ａｌｌｏｃａ
ｔｅｄ｝ｃｏｎｃｕｒｒｅｎｔ　ｌｏｃｋ　（ｏｂｊｅ
ｃｔ　ｉｄ，　ｅｎｔｒｙ　ａｄｄｒｅｓｓ）；ｉｆ　
（ｓｙｎｃｈ　ａｎｔｒｙが割り振られていない｝ｅｒ
＋ｔｒｙ　ａｄｄｒｅｓｓ　＋ｕｓｅ　ｃｏｕｎｔ　二
Ｏｔｈｅｎ　（このスロットに新しいオブジェクト情報
を記憶する｝ ＩＮＣＲ　ｃａｓｅ　１　（ｅｎｔｒｙ　ａｄｄｒｅｓ
ｓ）；　（Ｓｅｅ　Ｔａｂｌｅ　７）ｅｌｓｅ　ｉ「（
ロックされた項目がすてに、その使用カウントが増分す
べきデータベース・オブジェクトを表している｝ ｅｎｔｒｙ　ａｄｄｒｅｓｓ→ｏｂｊｅｃｔ　ａｄｄｒ
ｅｓｓ　＝　ｏｂｊｅｃｔ　ｉｄｔｈｅｎ ＩＮＣＲ　ｃａｓｅ　２；　｛Ｓｅｅ　Ｔａｂｌｅ　８
｝ｅｌｓｅ　（ロックされた項目が他のオブジェクトに
割り振られており、したがって新しいテーブル項目を割
り振る必要がある｝ ＩＮＣＲ　ｃａｓｅ　３；　｛Ｓｅｅ　Ｔａｂｌｅ　’
）｝ＵＮＴＴＬ　Ｉｎｃｒ　ｐｒｏｃｅｓｓｉｎｇ　＝
ｃｏｍｐｌｅｔｅ　ｉｉｆ　｛周囲のデータベース・マ
ネージャは、このスロットに記憶されている回復情報に
依存し、したがって回復状態をＤΔＳＤに書き込む必要
がある｝ｅｎｓｕｒｅ　ｌｅｖｅｌ　＝　ｅｎｓｕｒｅ
　ａｌｌ　ＯＲ　ｅｎｓｕｒｅ　ｌｅｖｅｌ　＝ｅｎｓ
ｕｒｅ　ｓｐｅｃｉｆｉｃ ｔｈｅｎ Ｉ１ａｎｄｌｅ　ｉｎ　ｕｓｅ　Ｅｎｓｕｒａｎｃｅ；
　（主記憶装置からＤＡＳＤへの書込みがスケジュール
され効率的に実行されることを保証するための支援をも
たらす｝ｅｎｄ　Ｉｎｃｒ　Ｐｒｏｃｅｄｕｒｅｉ２つ
の主要ソースから、こうしたテーブルに対して競合が発
生する可能性が大きい。すなわち同時に同じスロットを
ロックしようとする試み、及び他のジョブがこのページ
を２次記憶装置に書き出そうと試みているのと同時にテ
ーブルのページを修正しようとする試みである。低オー
バヘッドの比較後交換機構を上記の並列ロック手順と併
用して、第１の問題に対処する。後でより詳しく説明す
るように、バンドル書込み動作と併用して自由スロット
配置を慎重に選択すると、第２の問題が軽減される。さ
らに別の方法は、新しいスロットを割り当てる必要があ
るときに、テーブルの以前に修正されたどのページが依
然として入出力の最中であるかに関する知識によって、
自由スロソト配置が影響を受けるという機構を設けるも
のである。

下記の表７は、使用中テーブルを調べて空のテーブル項
目が見つかったときに使用される論理を記述したもので
ある。これは表６のコードから呼び出される。その項目
はオブジェクト情報に対して使用される。

表７ Ｐｒｏｃｅｄｕｒｅ　ＩＮＣＲ　ｃａｓｅ　１　（ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ）；ｂｅｇｉｎ Ｓｅｔ　　Ｏｂｊｅｃｔ　　ｉｎ−ｕｓｅ　　ｐｏｉｎ
ｔｅｒ　　（ｅｎｔｒｙ　　ａｄｄｒｅｓｓ）ｉＩｎｉ
ｔｉａｌｉｚａ　ｅｎｔｒｙ　（ｅｎｔｒｙ　ａｄｄｒ
ｅｓｓ）；ロｐｄａｔｅ　　ＩＯ　　ｒａｎｇｅｓ　　
（ｅｎｔｒｙ　　ａｄｄｒｅｓｓ）；｛入出力範囲は、
使用中テーブルのどの部分が、最近修正されたがまだ、
ＤＡＳＤに書き込まれていないかを識別するために維持
される｝ Ｕｐｄａｔｅ　　ｏｎ　　ｐａｇｅ　　ａｌｌｏｃａｔ
ｉｏｎ　　ｂｉｔｅ　　（ｅｎｔｒｙ　　ａｄｄｒｅｓ
ｓ）；（ベージ上の他のスロットが消費されたことを明
らかにする｝ ｅｎｄ ｅｎｄ　ＩＮＣＲ　ｃａｓｅ　１； 下記の表８の擬似コードは、表６から呼び出され、使用
中テーブルを調べて使用中のオブジェクトを指す項目が
見つかったケースを記述したものである。すなわち、使
用中の項目に記憶されたオブジェクト識別子が、使用中
のオブジェクトのオブジェクト　ＩＤと同じである。

表８ ＩＮＣＲ　Ｃａｓｅ　２　（ｅｎｔｒｙ　ａｄｄｒｅｓ
ｓ）；Ｐｒｏｃｅｄｕｒｅ ｂｅｇｉｎ ｌＪｐｄａｔｅ　ｅｎｔｒｙ　（ｅｎｔｒｙ　ａｄｄｒ
ｅｓｓ）：Ｕｐａｄｔｅ　ＩＯ　ｒａｎ８ｅｓ　（ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ）；ＩＮＣＲ　Ｐｒｏｃｅｓｓ
ｉｎｇ　　：＝ｃｏｍｐｌｅｔｅｅｎｄ ｅｎｄ． 新しいスロットが選択されると、増分処理が終了したと
いうステートメントの後で、表９の一部に示すようにそ
れが初期設定できる。表９に示した最後のケースは、使
用中テーブルを調べて、他のオブジェクトに対して割り
振られたテーブル項目が見つかったときである。この結
果、自由項目が割り振られるが、ｓｙｎｃｈ　　ｅｎｔ
ｒｙは１このオブジェクトに対するテーブル・アクセス
を同期させるために保持される。新しい項目が割り振ら
れて初期設定され、そのオブジェクトがｎｅｗｉｎ−ｕ
ｓｅテーブル項目を指すようになると、最初に獲得され
たロック（ｓａｎｅ−ｅｎｔｒｙ）が解除される。

表９ Ｐｒｏｃｅｄｕｒｅ　ＩＮＣＲ　ｃａｓｅ　３　（ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ）；ｂｅｇｉｎ Δｌｌｏｃａｔｅ　ｎｅｗ　ｅｎｔｒｙ　（ｅｎｔｒｙ
　ａｄｄｒｅｓｓ．　Ｎｅｗ−ｅｎｔｒｙ＠）　；ｉｆ
　ａｌｌｏｃａｔｉｏｎ　ｒｃ　＝　ｓｕｃｃｅｓｓｔ
ｈｅｎ ｉｎｃｒ　ｐｒｏｃｅｓｓｉｎｇ　：＝　ｃｏｍｐｌｅ
ｔｅ；Ｓｅｔ　　Ｏｂｊｅｃｔ　　ｉｎ−ｕｓｅ　　ｐ
ｏｉｎｔｅｒ　　（Ｏｂｊｅｃｔ　　ｉｄ，　　Ｎｅｗ
ｅｎｔｒｙ＠）　； Ｒｅｌｅａｓｅ　ｌｏｃｋ　（Ｅｎｔｒｙ　ａｄｄｒｅ
ｓｓ）ｉＩｎｉｔｉａｌｉｚｅ　ｅｎｔｒｙ　（ｎｅｗ
　ｅｎｔｒｙｏ）　ｉＵｐｄａｔｅ　ＩＯ　ｒａｎｇｅ
ｓ　（ｎｅｗ　ｅｎｔｒｙ＠）　；ロｐｄａｔｅ　　ｏ
ｎ　　ｐａｇｅ　　ａｌｌｏｃａｔｉｏｎ　　ｂｉｔｍ
ａｐ　　（ｎｅｗ　　ｅｎｔｒｙ＠）；Ｒｅｌｅａｓｅ
　ｌｏｃｋ　　（Ｎｅｗ　ｅｎｔｒｙ＠）；ｅｌｓｅ ｐｒｏｃｅｓｓｉｎｇ　ｃｏｍｐｌｅｔｅ　：＝　ＮＯ
Ｔ　ＣＯＭＰＬＥＴＥ；Ｒｅｌｅａｓｅ　ｌｏｃｋ　（
Ｅｎｔｒｙ　ａｄｄｒｅｓｓ）；Ｅｎｌａｒｇｅ　ｉｎ
　ｕｓｅ　ｔａｂｌｅｉ使用中マネージャの減分機能を
用いると、もはやオブジェクトにアクセスする必要がな
いとき、処理はオブジェクトの活動ユーザのカウントを
威少させる。この機能は、（データベース・ファイルが
クローズされるときに発生することがあるように）ユー
ザがもはやオブジェクトを使用していないことを記録す
るためのものである。オブジェクトを共用するユーザが
１人減ったことを示すために使用カウン１・が減分され
る。そのオブジェクトに関連する使用カウントがゼロに
なるき、その項目は、オン・ページ・スロット割振りビ
ット・マップの適切なビットをオフにすることによって
割振りが解除される。表１０に、減分機能（ＤＥＣＲ）
の擬似コードを示す。

表１０ Ｐｒｏｃｅｄｕｒｅ　ＤＥＣＲ　　（ｏｂｊｅｃｔ　ｉ
ｄ，　Ｖａｒ　Ｏｂｊｅｃｔ　ｉｎｆｏ，　Ｒｅｔｕｒ
ｎｃｏｄｅ）　； ｃｏｎｃｕｒｒｅｎｔ　ｌｏｃｋ　（ｏｂｊｅｃｔ　ｉ
ｄ，　ｅｎｔｒｙ　ａｄｄｒｅｓｓ）；ｉｆ　　ｅｎｔ
ｒｙ　　ａｄｄｒｅｓｓ　　＝　　ｅｎｔ．ｒｙ．ｏｂ
ｊｅｃｔ　　ａｄｄｒｅｓｓ＝ｏｂｊｅｃｔ　　ＩＤ｛
項目はＤＥＣＲがどれに対して実行中かを表す｝ｔｈｅ
ｎ ｂｅｇｉｎ Ｃこの項目に対する使用中テーブルで見つかった情報を
ユーザに戻す｝ Ｒｅｔｕｒｎ　ｅｎｔｒｙ　ｉｎｆｏ　（ｅｎｔｒｙ　
ａｄｄｒｅｓｓ，　ｅｎｔｒｙ　ｉｎｆｏｌＤｅｃｒｅ
ｍｅｎｔ　　ｔｈｅ　　Ｕｓｅ　　ＣｏｕｎｔｉＲｅｔ
ｕｒｎ　ｃｏｄｅ　：＝　Ｏｂｊｅｃｔ　ｒｏｕｎｄｉ
ｉｆ　（使用カウントが現在ゼロである｝ｔｈｅｎ ｂｅｇｉｎ （このスロットに関連するオン・ページ・ビットマップ
をオンにする。これは、このスロットが割り振られてい
ないことを示す｝ ｉｆ　（このページに対するオン・ページ・ビットマッ
プのすべてのビットが１の値をもつ｝ ｔｈｅｎ ｛０に減分されたばかりのスロットを含むページに対応
するページ割振りビッマップ中のビットをトグルする。

｝ ｅｎｄ ｅｌｓｅ　（オブジェクトは使用中でない｝ｂｅｇｉｎ ｒｅｔｕｒｎ　ｃｏｄｅ　：＝　Ｏｂｊｅｃｔ　ｎｏｔ
　ｉｎ　ｕｓｅ；ｅｎｄ Ｒｅｌｅａｓｅ　ｌｏｃｋ　（Ｅｎｔｒｙ　ａｄｄｒｅ
ｓｓ）；ｅｎｄ　ＤＥＣＲ　Ｐｒｏｃｃｄｕｒｅｉ使用
中マネージャは、使用中テーブルの項目を見つけて割り
振る。その割振りが必要になるのは、ＩＮＣＲ機能が使
用中のオブジェクト以外のオブジェクトにすでに割り振
られたｓＹｎｃｈ項目を選択するときである。使用中テ
ーブルの構造は第４図に示してある。使用中テーブル構
造には異なる３つの部分がある。使用中テーブル制御情
報ヘッダ８０は、最初及び最後の項目アドレスを含む。

そのアドレスは％　ｅｎｓｕｒｅ　ｒｅｑｕｉｒｅｄ範
囲１テーブル指示サイズ及びテーブル中の項目数の値を
指定する。さらにテーブル全体について発行された入出
力書込み動作のカウントが含まれている。そのテーブル
は、スロット、使用中項目のセクションまたはオブジェ
クトについての使用情報を含む項目を含む。項目セクシ
ョンは、５１２バイトの論理ページ８２、８４、８６か
ら構成され、各ページは好ましい実施例では１６個の項
目を含む。各ページは別々にＤＡＳＤに書き込める。各
ページは、内蔵の項目割振りビット・マップ８８、９０
、９２の形の項目割振り情報を有する。項目ビット・マ
ップはページの各項目の状況を示す１６ビットを含む。

テーブルのヘッダ８０中のページ割振りビット・マップ
は、そのテーブルのどのページが利用可能な項目をもつ
かを示す。ページ割振りビット・マップのｊ番目のビッ
トは、テーブルの項目セクシ日ンのｊ番目の論理ページ
を表す。各ビットは、使用中項目セクションのページの
割振り状態を表す。

そのビットは、それが表すページが満杯である場合、１
の値を持つ。０の値は、論理ページ上に利用可能な空間
がまだあることを意味する。

上記のように、使用中テーブルは論理ページに分割され
、各ページは１６個の項目を含む。第３図に示したオブ
ジェクトに関連する使用中状況情報に加えて、各論理ペ
ージの第１項目は、オン・ページ項目割振りビット・マ
ップと呼ばれる、１６ピットのフィールドをも含む。一
番左側のビットは、ビット・マップを含む周囲の論理ペ
ージ上の第１項目の割振り状況を表す。たとえば、左か
ら２番目のビットは、論理ページの第２項目の割り振り
状況を表し、以下同様にして、オン・ぺ−ジ項目ビット
・マップの一番右側のビットは、論理ページの１６番目
の項目の割振り状況を表す。

オン・ページ項目ビット・マップのｉ番目のビットが変
更できるのは、そのページ上の対応する項目が前記の項
目獲得手順を用いてロソクされてぃるときである。オン
・ページ項目ビット・マップへのすべてのアクセスは、
望ましいビットだけが変更されることを保証するため、
比較後交換などの原子的命令を用いて実行することが好
ましい。

Ｅ−４　　項目の割振り ＩＮＣＲ機能から理解できるように、項目を割り振ろう
と試みる際の最初のステップは、オブジェクトを同期項
目にマップし、同期項目が使用できるかどうか検査する
ことである。考慮すべき最初のケースは、異なるオブジ
ェクトにまだ割り振られていない項目に関するものであ
る。その後、それが割り振られ、オン・ページ項目割振
りビット・マップが更新される。この割振りの結果、論
理ページが満杯になると、そのページが満杯でない状態
から満杯な状態になったので、ページ割振りビット・マ
ップ８０の対応するビットがトグルされる。

ビットのトグルは、すべてのプロセッサが次にそのピッ
トにアクセスするときに正確なデータを受け取るように
、原子的に行なわれる。あるページが、ある処理の活動
のために満杯にされつつあり、同時に他の処理が同じペ
ージ上の項目を解放することがあり得る。このビットの
トグルにより、２つの動作が完了したとき正確な状況が
存在することが保証される。

第２のケースは、好ましい同期項目が他のオブジェクト
にすでに割り振られているときに発生する。この例では
、オン・ページ項目割振りビット・マップ８８が、同じ
ページの利用可能な項目を見つけるために検査される。

これが重要なのは、プロセッサが、すでに１つのページ
・フォールトを起こして、２次記憶装置から同期点を含
むページを主記憶に持ってきていることがあるからであ
る。

主記憶装置にすでに入れられた同じ論理ページがら代替
スロットを選択することを試みることにより、追加のペ
ージ・フォールトを回避することが望ましい。同期項目
と同じペーノ上の項目が利用可能な場合、その項目がロ
ックされ、上記のケース１の場合と同様に割り振られる
。したがって、ヘーシ・フォールトは容易に回避される
。

考慮すべき第３のケースは、同期点が異なるオブジェク
トに割り振られ、オン・ページ項目ビ，ソト・マソプの
検査で、ページのすべての項目が割り振られたこともわ
かったときに発生する。これには、異なるページを選択
する必要がある。満杯のページは１のビット設定で表さ
れるので、新しいページを見つけるには、ゼロ・ビット
を求めてページ割振りビｙト・マップ８０を探索する必
要がある。単に第１ビットから順にページ割振りビット
・マップ８０の探索を始めることもできるが、そうする
場合は、最初の自由ページ８２に対して大きな競合が起
こる。好ましい方法は、ページ割振りビット・マップの
開始点を選択する別のハッンユ関数への入力として、テ
ーブルの同期項目のオフセットを使用するものである。

好ましい実施例では、ページ発見ハッシュは、スロソト
がより均一に割り振られるように実行される。オフセソ
トが２分されて、半分になったオフセットを含むページ
番号に変換される。探索は、ページ割振りビット・マッ
プの、ｎ番目のビットを含むバイトから始まる。ただし
、ｎはすぐ前に述べた変換によって見つかったページ番
号である。

好ましい実施技術のもう１つの特徴は、共通の変換後検
査命令を使って最初のゼロを探索し、かつページ割振り
ビット・マップのビット・パターンを第１のゼロ・ビッ
トのビット番号に変換スルことである。変換テーブル中
のビット番号のコード化により、バイトを走査する労力
が省ける。

項目の一般的割振りの高レベル擬似コードを、表１１に
示す。上記のケースエはすでに提示したＩＮＣＲ機能の
最初のケースに当たるので、ここには示していない。

表１１ ＰｒｏｃｅｄｕｒｅΔＩｌｏｃａｔｅ　Ｎｅｗ　ｅｎｔ
ｒｙ　（ｅｎｔ．ｒｙ　ａｄｄｒｅｓｓ，　ｗａｒ　ｎ
（：．ｒｅｎｔｒｙ＠）　； Ｍａｐ　　ｅｎｔｒｙ　　ｔｏ　　ｐａｇｅ　　ａｄｄ
ｒｅｓｓ　　（ｅｎｔｒｙ　　ａｄｔ　　九一ＳＳ，　
　ｐａｇｅａｄｄｒｅｓｓ）　ｉ Ｔｒｙ　ｔｏ　ａｌｌｏｃａｔｅ　ｅｎｔｒｙ　ｏｎ　
ｐａｇｅ　（ｐａｎ　　ｊｄｄｒｅｓｓ＋　ｎｅＷｅｎ
ｔｒｙ＠，　Ｔｒｙ　ｐａｇｅ　Ｒｅ）Ｗｈｉｌｅ　ｔ
ｒｙ　ｐａｇｅ　ｒｅ　Ｏ　Ｓｕｃｃｅｓｓ　ｄｏＢｅ
ｇｉｎ 〔利用可能な空間をもつと思われるページを探す｝Ｆｉ
ｎｄ　Ｕｎａｌｌｏｃａｔｅｄ　ｐａｇｅ　（ｅｎｔｒ
ｙ　ａｄｄｒｅｓｓ，　ｎｅｗ　ｐａｇｅａｄｄｒｅｓ
ｓ）　； 〔選択されたページ上の未割振り項目を探すことを試み
る｝ Ｔｒｙ　ｔｏ　ａｌｌｏｃａｔｅ　ｅｎｔｒｙ　ｏｎ　
ｐａｇｅ　（ｐａｇｅ　ａｄｄｒｅｓｓ，Ｎｅｗ　ｅｎ
ｔｒｙ（！，　Ｔｒｙ　ｐａｇｅ　Ｒｅ）ｅｎｄ ページが選択された後に項目を割り振ろうと試みること
は、かなり容易であり、表１２に示されている。しかし
テーブル・マネージャは並行動作するので、１つの興味
深いアイデアがある。オン・ページ項目ビット・マップ
８８を検査して候補項目を決定する。この検査を行なう
には、比較後交換命令を用いてビット・マップの最も最
近のスナップシＥｌットを得る。そのスナップショット
を検査して、このページの最初の未割振り項目を見つけ
る。ページ上の未割振り項目は、オン・ページ項目ビッ
ト・マップ中で１のイ直で示される。ハードウェア命令
を使って、ビット・マップの最初の１ビットを見つける
。最初の１ビットを見つけるための他の多くの代替手段
は当業者には明らかである。次のステップは、ビット・
マップのスナップシ日ットから示された項目の排他的制
御を得ることである。この時点で、並行して実行中の処
理が、自由であると考えられていた項目の排他的制御を
脊する場合、遅延に遭遇することがあり得る。したがっ
て、この項目に対するロックが最終的に許可されたとき
、ビット・マップの新しい原子的スナップショットを獲
得しなければならない。この新しいスナップショットを
検査して、ロックされた項目に対応するビットが、依然
として項目が１で、未割振りであることを意味するある
ことを確認する。そうである場合、そのビットがオフに
なり、ｎｅｗ　　ｅｎｔｒＹ＠がこの新しい項目に設定
される。

項目の排他的制御を獲得するとき、オン・ぺ一ジ割振り
ビットマップの再検査でその項目がすでに割り振られて
いることが明らかになった場合、この手順ではビット・
マップの残りのビットを検査し、他の候補項目について
上記の処理を繰り返す。１つの項目が首尾よく割り振ら
れるか、または未割振り項目がページ上に存在しなくな
るまで、このページでこの処理が継続する。

表１２ Ｐｒｏｃｅｄｕｒｅ Ｔｒｙ　　ｔｏ　　ａｌｌｏｃａｔｅ　　ｅｎｔｒｙ　
　ｏｎ　　ｐａｇｅ　　（ｐａｇｅ　　ａｄｄｒｅｓｓ
，　　ｎｅｗｅｎｔｒｙ＠，　Ｔｒｙ　ｐａｇｅ　ｒｃ
）ｇｅｔ　ｓｎａｐｓｈｏｔ　ｏｆ　ｂｉｔｍａｐ　（
ｐａｇｅ　ａｄｄｒｅｓｓ，　Ｖａｒ　ｂｉｔｍａｐ）
Ｆｉｎｄ　ｆｉｒｓｔ　１　ｂｉｔ　（ｂｉｔｍａｐ，
　Ｖａｒ　ｂｉｔ　ｎｕａ＋ｂｅｒ，　Ｅｎｔｒｙｎｕ
ｍｂｅｒ）　； Ａｃｑｕｉｒｅ　ｌｏｃｋ　（Ｅｎｔｒｙ　ｎｕｍｂｅ
ｒ）；ｔｒｙｐａｇｅ　ｒｅ　＝　Ｄｏ　ｎｏｔ　ｋｎ
ｏｗ　ｙｅｔｉＲｅｐｅａｔ　｛項目が割り振られるま
で、またはページ上にもう自由な項目がなくなるまで｝ ｇｅｔ　ｓｎａｐｓｈｏｔ　ｏｆ　ｂｉｔｍａｐ　（ｐ
ａｇｅ　ａｄｄｒｅｓｓ，　Ｖａｒ　ｂｉｔｍａｐ）汀
（そのビットが依然として１にセットされている｝Ｂｉ
ｔ　ｔｅｓｔ　（ｂｉｔ−ｍａｐ＋　ｂｉｔ　ｎｕｍｂ
ｅｒ）　＝１ｔｈｅｎ　（項目を割り振ることができる
｝ｂｅｇｉｎ ［割り振られた項目を示すためにビットをオフにする｝ Ｒｅｓｅｔ　Ｂｉｔ　（Ｖａｒ　ｂｉｔｍａｐ，　ｂｉ
ｔ　ｎｕｍｂｅｒ）Ｔｒｙｐａｇｅ　ｒｅ　：＝　Ｓｕ
ｃｃｅｓｓｉｅｎｄ Ｅｌｓｅ　ｉｆ　｛この論理ページ上のすべてのスロッ
トが現在割り振られている｝ ｂｉｔｍａｐ　＝　Ｏ ｔｈｅｎ　Ｔｒｙｐａｇｅ　ｒｅ　：＝　Ｆａｉｌｕｒ
ｅ；下記の表１３の擬似コードは、ページ割振りビット
・マップ８０を使って、候補ページがどのようにして選
択されるかを記述したものである。

表１３ ？ｒ■（Ｈｅｄｕｒｅ Ｆｉｎｄ　Ｕｎａｌｌｏｃａｔｅｄ　ｐａｇｅ　（ｅｎ
ｔｒｙ　ａｄｄｒｅｓｓ，　ｎｅｗ　ｐａｇｅａｄｄｒ
ｅｓｓ）　； Ｃピット・マップ中の探索が始まる点を選択する｝ｓｔ
ａｒｔｉｎｇ　ｂｉｔ　：＝　（ｅｎｔｒｙ　ａｄｄｒ
ｅｓｓ　−　ｆｉｒｓｔ　ｅｎｔｒｙａｄｄｒｅｓｓ）
／ｐａｇｅｓｆｚｅ／２ｓｔａｒｔｉｎｇ　ｂｙｔｅ　
：＝　ｓｔａｒｔｉｎｇ　ｂｉｔ／８　＋　１ｓｃａｎ
　ｂｉｔ＊ａｐ　（ｓｔａｒｔｉｎｇ　ｂｙｔｅ，　ｗ
ａｒ　ｓｔｏｐ　ｂｙｔｅ，　ｂｉｔｎｕ＋＊ｂｅｒ，
　　ｒｅ） Ｃビット・マップから適切なρａｇｅ　ｎｕｍｂｅｒを
計算する｝Ｐａｇｅ　ｎｕｍｂｅｒ　：＝　ｓｔｏｐ　
ｂｙｔｅ　”８　＋ｂｉｔ　ｎｕｍｂｅｒ　−１；（候
補ページの実際のページ・アドレスを決定する｝ｐａｇ
ｅ　ａｄｄｒｅｓｓ　：＝　ｆｉｒｓｔ　ｅｎｔｒｙ−
ａｄｄｒｅｓｓ　＋Ｅ−５　　人出力の最小化 使用中マネージャは、絶対的に必要なときにだけ項目を
非揮発性記憶装置にセーブするために入出力を実行する
ことによって、入出力を最小にする。これを達成するた
めに、いくつかのフィールドがテーブル・ヘッダに追加
される。まず、強制を必要とするテーブル項目の範囲を
示す「上限」ポインタと「下限」ポインタがある。強制
は、その節囲のテーブル項目が、強制される、すなわち
揮発性の主記憶装置から非揮発性２次記憶装置に書き込
まれるという意味で使用する。これは、ページング環境
で実行される共通動作である。ポインタは、強制を必要
とする項目がないことを示すように初期設定される。テ
ーブル・ヘッダ中にはまた、各入出力が開始される直前
及びそれが完了した直後に増分されるカウント・フィー
ルドがある。

このカウント・フィールドはゼロに初期設定される。こ
れは、そのフィールドが偶数であるときは入出力は進行
中ではなく、奇数であるときは入出力が進行中であるこ
とを意味する。このことは後で利用する。各テーブル項
目はまた入出力カウント・フィールド６８をも含む。入
出力カウントをヘッダ・カウントと比較することにより
、特定のスロットの内容が補助記憶装置に書き込まれた
かどうかが容易にかつ効率的に決定できる。

対話型コンピュータ処理環境では、データベース・オブ
ノエクトは一般に、対応するデータベース・ファイルが
オーブンしたときに使用されるが、後でアブリケーシａ
ン・プログラムが基本的データベースの修正を開始する
ときまで実際の修正を受けないことがあるので、あるオ
ブジェクトを使用中にする（ＩＮＣＲ）動作を、回復の
リスクがあり得る、そのオブジェクトをフラグ付けする
という後続動作（数分後）から分離することを選択した
。この第２ステップは、使用中テーブル・マネージャが
補助記憶装置に対応するスロットを古き込むことを要求
することで表される（これは、ＥＮＳＵＲＥ動作と呼ば
れている）。したがって、１つのオブジェクトが使用さ
れるとき、それを収容するテーブル項目をディスクに直
接書き込む必要はない。そうではなく、システムが回復
を必要とするオブジェクトに対して最初の変更を行なお
うとするときに、対応テーブル項目がディスクにもたら
されることを保証するために、使用中テーブル・マネー
ジャが呼び出される。このため、複数のオブジェクトの
項目が一度に２次記憶装置に書き込めるようになり、テ
ーブル全体に対して実行される入出力動作の合計数が最
小になる。人出力のオーバヘッドとしては、バス割振り
処理などがある。本発明を使用しない場合、単純な方法
は、まだ書き込まれていないテーブル内のどこかに何ら
かの変更が行なわれた場合に、繰り返してテーブルに新
たに吉き込むことになる。すなわち、対応する項目が複
数の入出力動作で以前に書き込まれていて、さらに書き
込まれるということになる。

下記の偶数／奇数カウント方法を用いると、オブジェク
トが使用されるとき、テーブル項目中の入出力カウント
・フィールド６８が、次の完全な入出力動作が行なわれ
たときにヘッダ・カウントが設定される値に設定される
・入出力動作が現在進行中（ヘッダ・フィールドが奇数
）の場合、項目フィールドは、ヘッダ・フィールド＋３
に設定される。ヘッダ・フィールドが偶数の場合は、項
目フィールドはヘッド・フィールド＋２に設定される。

入出力カウント・フィールドは、この時点以降、オブジ
ェクトがもはや使用されなくなるまで決して変更されな
い。ヘッダ・フィールドと項目フィールドの単純な比較
を用いて、回復を必要とする修正が関連するオブジェク
トに加えられる前に、その項目が２次記憶装置上にある
ことを保証するために、入出力動作が必要かどうかを決
定する。

第５図は、使用中テーブル・ヘッダ１０３ａ，１０３ｂ
，１０３ｃ，１０３ｄ，１０３ｅに記憶された入出力カ
ウントを時間順に配列したものを、それらの入出力カウ
ントを示す４つのテーブル・スｏ−，トの集合１０４ａ
，１０４ｂ１　１０４ｃ１１０４ｄ，１０４ｅと共に示
す。時間ｔ１では、活動が発生していす、すべての値が
ゼロから始まる。さらに、上下限インジケータ１０５ａ
と１０６ａが、どのスロットも入出力を必要としないこ
とを示すように初期設定されている。

時間ｔ　２では、２つのスロットが割り振られて、次の
完全な入出力動作が発生したときにヘッダ１０３ｂ中に
設定される入出力カウントに対応する入出力カウントで
マークされる。次の入出力でヘッダ入出力カウントが０
から２に増分されるので、集合１０４ｂの第１及び第３
スロットに２が入れられる。また、上下限インジケータ
１０５ｂと１０６ｂは、次の入出力でどのスロットが書
き込まれる必要があるかを示すように調節される。

時間ｔ３で、入出力が開始されて、集合１０４Ｃのスロ
ット１と３を非揮発性記憶装置に書き込む。上下限イン
ジケータ１０５ｃと１０Ｅｉｃは、スロットが入出力を
必要としないことを示すように調節されている。しかし
、スロット１と３は、それらの入出力カウントがヘッダ
入出力カウントより大きいので、依然としてそれらが非
揮発性記憶装置に書き込まれていないことを示している
。

そうなるのは、ヘッダ入出力カウントの１によって示さ
れるように、その入出力が開始されただけでまだ完了し
ていないからである。

時間ｔ４では、さらに２つのオブジェクトが使用中にな
り、テーブル集合１０４ｄのスロット２と４を占めてい
る。それに応じて、上下限インジケータ１０５ｄと１０
８ｄが調節されている。スロット２と４に対する変更が
以前に要求された入出力（スロット２は以前の上下限イ
ンジケータ内にあったが４はなかったので、恐らくスロ
ット２）によって書き込まれるかどうかが決定できない
ので、ヘッダ入出力カウントが４に達するまでそうした
変更は書き込まれることが保証できない。

スロット１と３に対して入出力が進行中の場合でさえ、
揮発性記憶装置内でスロット１及び３と同じページに存
在するスロット２及び４に対して変更を行なうことがで
きる。これは、後でそれに対するアクセスが行なわれた
ときに書き込まれるページの別のコピー（クローン）を
作ることによって実現される。このため、ページが書き
込まれているときに、それを修正することが可能になる
。

時間ｔ５で、最初の入出力動作が完了して、ヘッダ１０
３ｅの入出力カウントが２に更新される。

これは、集合１０４ｅのスロット１と３が非揮発性記憶
装置に首尾よく書き込まれたことを他の処理に伝える曇
きをする。これにより、そのスロット２または４が書き
込まれることが必要となるまで、他の入出力は発行され
ない。

入出力縮小論理の実施には、最良の性能を得るために２
つのロックが必要である。最初のロックは、入出力ウィ
ンドウ（ポインタ間のテーブル項目）の上限及び下限へ
のアクセスを制限するために獲得される。このロックは
、最短の時間保持され、保持タスクに対する入出力動作
が進行中は保持されない。そのため、このロックは性能
を損なわない。単純な手順が使用され、制限ロックを獲
得し解除する擬似コードで示される。

第２のロックである入出力ロックは、使用中テーブルに
対する同時入出力動作の数を１つに制限するのに使用さ
れる。これは、きわめて短い時間内に開始される後続要
求が１つの入出力動作に縮小できるようにするためのも
のである。そのシナリオは次の通りである。タスク１が
いくつかの変更を保証するために入出力要求を発行する
（時間ｔｏ）。タスク２が、時間ｔ１でいくつかの変更
を行ない、入出力のウィンドウを更新する。タスク１は
、このとき時間ｔ２で入出力ロック及び制限ロックを獲
得する。タスク１に対して入出力動作が実行され、その
後タスク２のデータが書き込まれる。タスク２は最後に
入出力の制御を獲得し、入出力動作がすでに完了したこ
とを発見する。タスク２は、不必要なのでその入出力を
実行しない。

細分性をさらに向上させるため、この方法を、入出力動
作を使用中テーブルの複数のゾーンに同期させる場合に
も適用できる。各ゾーンは、別々のＤＡＳＤ装置上に割
り振られる。次に各ゾーンご七に１つの入出力動作が実
行される。これを達成するため、上下限並びに入出力カ
ウントが、テーブルの各ゾーン（エクステント）ごとに
複製される。また、制限ロック及び入出力ロックも各ゾ
ーンごとに必要である。この拡張態様は、複数の記憶エ
クステントにわたる大きなテーブルの性能の向上をもた
らす。

この方法の実施は、論理的に２つの機能部分に分けられ
る。最初の部分は、テーブル項目が増分動作を通じて作
用を受けるときに呼び出される。

保証情報取扱い更新ルーチンが、前述の増分手段から呼
び出される。擬似コードは表１４の通りである。

表１４ Ｐｒｏｃｅｄｕｒｅ　ｌｌａｎｄｌｅ　ｉｎ−ｕｓｅ　
ｅｎｓｕｒａｎｃｅ；Ｉｆ　｛この項目が、読取り専用
状態から読書き状態になり、それにより、オブジェクト
が変更されようとしており、潜在的な回復処理の候補と
して分類される必要があることを示す｝ ｔｈｅｎ Ｂｅｇｉｎ Ｏｂｔａｉｎ　ｉｎ−ｕｓｅ　ｌｉｍｉｔ　ｌｏｃｋ；
ＩＦ　（下限＝０１またはテーブル項目のアドレスが下
限より小さい｝ ＴＩＩＥＮ　｛下限をテーブル項目のアドレスに設定す
る｝ＩＦ　（テーブル項目のアドレスがウィンドゥの上
限より大きい｝ ＴＩＩＥＮ　（上限をテーブル項目のアドレスに設定す
る｝（このテーブル項目が書き出されることが保証され
ているとき、その項目のＩ／ＯＩ＋を入出力番号の将来
の値に設定する｝ ＤＳＩロＩＯＩ１　　：＝　　（ＤＳＩＵＦＲＣＩ１　
　＋　３）　　＆　　（−２）：ＩＦ　｛ｈｅａｄｅｒ
　ＩＯ　ｃｏｕｎｔが奇数｝Ｔｌｌ聞 ｅｎｔｒｙ　ＩＯ　ｃｏｕｎｔ　＝　ｈｅａｄｃｒ　Ｉ
Ｏ　ｃｏｕｎｔ　＋　３ＥＬＳＥ ｅｎｔｒｙ　ＩＯ　ｃｏｕｎｔ　＝　ｈｅａｄｅｒ　Ｉ
Ｑ　ｃｏｕｎｔ　＋　２）Ｒｅｌｅａｓｅ　ｉｎ−ｕｓ
ｅ　ｌｉｍｉｔ　ｌｏｃｋ；Ｉｆ　［特定のスロットが
ＤＡＳＤに書き込まれ、使用中テーブル・ヘッダの入出
力カウントがこの項目の入出力カウントより小さく、ｅ
ｎｓｕｒｅ　ｓｐｅｃｉｆｉｃ＝Ｔｒｕｅかつ１ｌｅａ
ｄｅｒ　ＩＯ　ｃｏｕｎｔ＜Ｅｎｔｒｙ　ＩＯ　ｃｏｕ
ｎｔ　となることを確認するように呼出しプログラムが
求めた｝Ｔｈｅｎ　（特定の確認なので強制が必要であ
ると強制ルーチンに告げる｝ ＦＯＲＣＥＳＰＣ　：＝　ＳＥＴ； ｌＥｎｄ 使用中の強制ルーチンは、表１５に示すように、適切な
ときに、テーブル項目を補助記憶装置に書込むことを扱
う。

表１５ Ｐｒｏｃｅｄｕｒｅ　Ｉｎ−Ｕｓｅ　ＩＯ；Ｖａｒ　Ｃ
ＵＲＩＯ　ＩＮＴＥＧＥＲ．　（現入出力カウンタのス
ナップシ１１　−／ト｝ ＦＯＲＣＬＯ＠ＰＴＲ，　（強制範囲の下限の局所コピ
ー｝ＦＯＲＣＩＩＩ＠　　ＰＴＲ；　（強制箱囲の上限
の局所コピー｝Ｂｅｇｉｎ Ｆｅｘｍｐ．　　：ｘｍｐ． Ｉｆ　｛ｈａｎｄｌｅ　ｅｎｓｕｒｅ手１順が、入出力
が必要であることを示し、または大城保証が要求された
｝ Ｔｈｅｎ Ｂｅｇｉｎ （ＣＲロ■０を入出力カウントの現在値に設定する｝Ｏ
ｂｔａｉｎ　ｉｎ−ｕｓｅ　ｒＯ　ｌｏｃｋ；　｛他の
処理により入出力中にここで遅延することがある｝ Ｏｂｔａｉｎ　ｉｎ−ｕｓｅ　Ｌｉｍｉｔ　ｌｏｃｋ；
Ｉｆ　｛ロックを得ようと試みて以降、入出力が行なわ
れなかったが、実行すべき入出力がある｝Ｔｈｅｎ Ｂｅｇｉｎ Ｅｎｄ ｛ＦＯＲＣＬＯ＠を入出力範囲の［３０ＴＴＯ｝４の現
在値に設定する｝ ［ＦＯＲＣＩＩＩＯを入出力範囲のＴＯＰの現在値に設
定する｝ （入出力範囲の上限及び下限をクリアする｝｛入出力が
実行される前に一度入出力カウントを増分する｝ Ｒｅｌｅａｓｅ　ｉｎ−ｕｓｅ　ＬＩＭＩＴ　ｌｏｃｋ
；　Ｃ他の割振りを実行させる｝ Ｗｒｉｔｅ　ｓｔｏｒａｇｅ　（ｆｏｒｃｌｏ＠，　ｆ
ｏｒｃｈｉ＠）；（入出力が実行された後に一度入出力
カウントを増分する｝ Ｒｅｌｅａｓｅ　ＩＮ−ＬＩＳＥ　ＩＯ　ｌｏｃｋ；Ｅ
ｎｄ Ｅｌｓｅ Ｂｅｇｉｎ Ｒｅｌｅａｓｅ　ｉｎ−ｕｓｅ　ｌｉｍｉｔ　ｌｏｃｋ
；Ｒｅｌｅａｓｅ　ｉｎ−ｕｓｅ　ｒ０　ｌｏｃｋ；Ｅ
ｎｄ Ｅｎｄ． オブジェクトがそれにアクセスするいずれかの処理によ
って変更されなかった場合は、異常システム終了の後に
その回復が不必要なことがある。

オブジェクトは、読取り専用機能及び読書き機能の両方
のために、使用中にされる。本発明以前には、オブジェ
クトが読取り／魯込みの目的のために使用中にされず、
読取り専用動作のためだけに使用されていて、システム
が故障したとき、再開処理は読取り専用状況と読取り／
古込み使用中状・況とを区別できず、したがって読取り
専用オブジェクトが不必要な回復処理を受けていた。使
用中マネージャは、オブジェクトが読み書き目的のため
に使用されたかどうかを示す、テーブル項目中の別のビ
ット（更新フラグ６８）を記録することにより、この不
効率を回避する。このと゛ットは、システムが故障した
場合にそのオブジェクトを回復すべきかどうかを示す。

個々の項目を保証するとき、それらの項目を含む周囲の
ページが補助記憶装置に書き込まれる。

未処理の入出力動作によって生じる競合を軽減するため
、いくつかの方法が使用される。１つの方法は、主記憶
装置の実記憶フレームの内容をクローン・フレームにコ
ピーするものである。その後、自由にクローン・フレー
ムに直接アクセスできるが、元の記憶フレームは、２次
記憶装置に書き出せる。入出力の競合を最小にするため
のもう１つの技術は、記憶装置に現在どのページが書き
込まれているかを記録するために、ページ割振りビット
・マップに入出力保留ビットを入れるものである。前記
のＦＩＮＤ　　Ｕｎａｌｌｏｃａｔｅｄｐａｇｅ手順を
使って、満杯ではなく、かつ現在補助記憶装置に書き込
まれていないページを探索すると、上記のようにページ
・フレームのクローンを作る必要がなくなる。変換後検
査命令で、２つの隣接するビットが各ページの入出力保
留状況及び割振り杖況を表すというビット列を効率的に
探索できるようにするコーディングが開発された。

ビット・マップの１走査で、適切な自由で利用可能なペ
ージが選択される。

もう１つの好ましい実施例では、１ページ毎に多くの項
目があるため、すべての隣接項目が特定の項目向けのペ
ージ・アウト動作によって補助記憶装置に書き込まれた
ことを反映させることが望ましい。そのアイデアは、あ
る項目が最初に割り振られたとき、その項目の１ビット
をオンにすることである。１の値は、その項目が補助記
憶装置に書き込まれていないことを示す。ページ・アウ
ト動作が実行されるとき、書き込まれているぺ一ジ上の
各項目に対するこのビットをオフにするため記憶装置管
理出口が呼び出される。これにより、記憶装置管理の外
部でそのビットをオフにする必要がなくなる。というの
は、そうすると、そのページが変更済みとマークされて
、他のページ入出力がトリガされるからである。記憶装
置管理出口は、そのページ・アウトが使用中テーブルの
テーブル項目に対するものであることを認識しなければ
ならない。アプリケーション・システム／４００では、
使用中テーブルはその仮想アドレスによって認識される
ので、認識が容易になった。

競合を軽減する他の方法は、シャドウ・ページを使用す
るものである。上記のシャドウ・ページが不在の場合、
互いに面対称の関係にある２つのテーブルを設けること
により、入出力の競合が軽減される。最初のテーブルは
、読取り及び更新用に使用される。最初のテーブルは、
使用中マネージャの要求で明示的に補助記憶装置に書き
込まれることはない。すべての更新は最初のテーブルか
らシャドウにコピーされる。テーブル項目を強制しなけ
ればならないとき、シャドウ部分が補助記憶装置に書き
込まれる。これにより、最初のテーブルは、入出力トラ
フィックに関わらず、無制限利用可能なままとなり、参
照及び高レベルの並行性が可能となる最初のテーブルで
、保証される必要がない更新が行なわれる場合、更新の
コピーは、そのページに対する保証される必要がある更
新が行なわれるまで延期される。競合は、最初のテーブ
ルからシャドウに更新がコピーされている間だけに制限
される。

本発明を好ましい実施例に関して説明したが、他の実施
例も本発明の範囲内に含まれることを認識されたい。順
次探索することなくスロットを識別するという利点は、
上記の特定のハッシュ以外の方法によっても実現できる
。上記の原子的動作に代わる方法もある。さらに、マル
チプロセッサ環境では、使用するアドレス方式に応じて
、使用中テーブルをプロセッサ間で分割しても、１つの
プロセッサにすべて納めてもよい。

Ｆ．発明の効果 本発明を用いれば、データベースまたはファイル等の回
復動作を効率化することができる。

【図面の簡単な説明】

第１図は、複数処理環境における使用中テーブル・マネ
ージャの論理構成図である。 第２図は、第１図のテーブル・マネージャの島レベル流
れ図である。 第３図は、使用中テーブルの項目中のフィールドの構成
図である。 第４図は、複数の項目をもつ使用中テ・−ブルの構成図
である。 第５図は、入出力動作に関するカウンタを示す使用中テ
ーブルの複数部分の連続した一連の構成図である。 １２、１４・・・・データベース・ファイル、１６、１
８・・・・ヘッダ、１７・・・・２次記憶装置、１９・
・・・メモリ・ブロック、２Ｌ　２２、２４・・・・処
理、２６、２７、２８・・・・プロセッサ、３０・・・
・使用中マネージャ、３２・・・・使用中テーブル、３
４・・・・スロット、４０・・・・ヘッダ。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーシ式ン 代理人　　弁理士　　頓　　宮　　孝　　一（外１名） 第２図 １０３ａ １０３ｂ １０３ｅ

Claims (4)

【特許請求の範囲】
1. （１）オブジェクトを使用中テーブルのスロットに割り
   当てる手段、 オブジェクトのヘッダにスロット・アドレスを挿入する
   手段、 同時アクセスを防ぐためにテーブルの個々のスロットを
   ロックする手段、 テーブル中でオブジェクト使用の指示を行なう手段、及
   び 各オブジェクトごとに望ましい回復活動を示すように使
   用の指示を修正する手段、 を含む使用中テーブル・マネージャ。
2. （２）プロセスによって使用されているオブジェクトを
   識別するフィールドを有するスロットを含む、使用中テ
   ーブルを管理する方法であって、 ａ、使用中テーブルのスロットにオブジェクトを割り当
   てるステップ、 ｂ、オブジェクトのヘッダにスロット・アドレスを挿入
   するステップ、 ｃ、スロットの修正中に使用中テーブルの個別のスロッ
   トをロックするステップ、 ｄ、使用中テーブル中にオブジェクトの使用の指示を与
   えるステップ、及び ｅ、回復活動が必要かどうかを使用中テーブル中に示す
   ステップ を含む上記方法
3. （３）入出力動作による非揮発性記憶装置への書込みを
   必要とする、揮発性記憶装置に存在する個別に修正可能
   な項目を有するテーブルへの同時アクセスを可能にする
   機構であって、 テーブル上の入出力活動の全体状況を追跡する手段、 各項目を非揮発性記憶装置に書き込む個々の必要を追跡
   する手段、及び 全体状況を、項目が書き込まれたことを検査する個々の
   必要と関連付ける手段 を含む上記機構。
4. （４）複数のプロセスと、 プロセスによってアクセスされる、データベース情報を
   含む複数のオブジェクトと、 ヘッダと、オブジェクトの使用中状況を示すことができ
   る複数のスロットとを有する使用中テーブルと、 オブジェクトを使用中テーブルのスロットに割り当てる
   手段、 オブジェクトのヘッダにスロット・アドレスを挿入する
   手段、 同時アクセスを防ぐためにテーブルの個々のスロットを
   ロックする手段、 テーブル中でオブジェクト使用の指示を与える手段、及
   び 各オブジェクトごとに望ましい回復活動を示すために使
   用の指示を修正する手段 を含む使用中マネージャと、 を含む高度並行データベース・システム。