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

Description

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

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

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

どのオブジェクトが使用中であるかに関する情報は、各
オブジェクト自体の内部に維持することが可能である
が、これは、システム再開時に、各オブジェクトをすべ
て２次記憶装置から主記憶装置にページングし、検査す
る必要があるので望ましくない。これは時間がかかり過
ぎる。もう一つの方法は、オブジェクト・ディレクトリ
に使用中状況を記録するものである。これも、探索する
ディレクトリがシステム内に多数あることがあり、また
すべてのオブジェクトをディレクトリに入れる必要があ
るわけではない（ＩＢＭアプリケーション・システム４
００／（ＴＭ）ではそうである。回復を必要とするオブ
ジェクトのうちにはディレクトリに記憶されてないもの
がある）ので非実用的である。さらに、多くのコンピュ
ータ・システムは、減多に使用されない眠っているオブ
ジェクトを大量に格納している。オブジェクトが回復処
理を必要とするかどうかを決定するために、クラッシュ
に直面してこうしたすべてのオブジェクトを徹底的に検
査するのは非効率的である。その代わりに、潜在的な回
復処理のために探索しなければならないオブジェクトの
数を最小に抑える機構を提供することが望ましい。

ＩＢＭシステム／３８では、使用中テーブルは多くの項
目から構成され、各項目が１つのオブジェクトに対応し
ていた。そのテーブル自体が１つのオブジェクトであ
り、単一プロセスでロックすることができた。このた
め、テーブルに対して実行される動作が直列化され、シ
ステムの大きなネックになる。オブジェクトが高速で繰
返し使用され、また使用から外されるときは特にそうで
あった。またこのテーブルは線形方式で探索されてい
た。大きなテーブルでは、線形探索は非効率的であっ
た。テーブルが修正される度にテーブルがディスクに書
き込まれていた。この結果、入出力線上のトラフィック
が高率になった。こうした同期書込み動作は、入出力ト
ラフィックの高い時間には大きなシステムのネックとな
っていた。このテーブルのもう１つの限界は、あるオブ
ジェクトが使用中であるかどうかしか指示しないことで
あった。単に読取り中のオブジェクトは、変更が行なわ
れないので回復する必要はない。

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

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

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

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

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

Ｄ．課題を解決するための手段 単一のシステム規模のテーブルはスロットを有し、各ス
ロットは、マシンが突然に終了した場合に各オブジェク
トはどの潜在的な回復動作を受けなければならないかを
示すのに十分な情報とともに、使用中のオブジェクトの
アドレスを含んでいる。各スロットは、データベース・
オブジェクトやファイルなど１つのオブジェクトに対応
する。データベース・オブジェクトが少なくとも１回使
用されると、それは好ましい同期点としてテーブル中の
スロットを割り当てられる。同期点とは、そのオブジェ
クトに関する活動は記憶されるスロットである。そのオ
ブジェクトが使用されなくなった期間でも、そのスロッ
トはその好ましい同期点のままである。使用中テーブル
に戻る直接のリンクをもたらすため、スロット・アドレ
スがオブジェクトのヘッダ中に含まれている。

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

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

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

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

Ｅ．実施例 Ｅ−１概要 本発明の論理形式の構成図を第１図に１０で一般的に示
す、データベース・ファイル１２、１４など複数のオブ
ジェクトが、データベース情報を含んでいる。オブジェ
クト１２、１４は、カプセル化されたデータであること
が好ましい。このカプセルは、データを記述する情報を
含むヘッダ１６、１８を含む。ヘッダ１６、１８は、そ
のオブジェクトがデータまたはプログラミングまたは様
々な形式の情報を含むことを示すことができる。ＩＢＭ
システム／３８及びアプリケーション・システム／４０
０は、それらが処理する情報の大半をオブジェクトの形
にカプセル化する。オブジェクトは、１つまたは複数の
５１２バイト・ページに記憶されている。そのページは
通常２次記憶装置１７上に存在しており、記憶装置管理
ブロック２０により周知の方式でメモリ及びプロセッサ
１９との間でページングされる。アドレス方式は、単一
の仮想アドレス範囲が２次記憶装置１７のすべてに使用
されるという、単一レベル記憶形式のものであることが
好ましい。メモリ・ブロック１９は、プロセッサ及びメ
モリ１９のラベルがつけてある。これは、プロセッサの
記憶装置に存在しそのプロセッサ中で実行されるプログ
ラムとデータの論理表示として使用される。

複数のプロセス２１、２２、２３が、データベース・フ
ァイルの探索やそこでのデータの更新などの作業を実行
するため、オブジェクトにアクセスする。プロセスは、
プロセッサ及びメモリ１９、並びに２次記憶装置１７に
接続されたプロセッサ２６、２７、２８にも存在する。
オブジェクトにアクセスするため、任意のプロセッサに
存在するプロセスは、使用中マネージャ３０を呼び出
し、オブジェクトの仮想アドレスと実行すべき動作のタ
イプを供給する。使用中マネージャ３０は、オブジェク
トが１つまたは複数のプロセスによって使用されている
かどうかに関する情報を含む複数のスロット３４を含む
使用中テーブル３２を生成して維持する。プロセスから
呼出しを受け取ると、使用中マネージャ３０は、仮想ア
ドレスを用いてオブジェクト１４のヘッダにアクセス
し、スロット・アドレス１８を含むフィールドを見る。
スロット・アドレスがゼロの場合、使用中マネージャ
は、使用中テーブルのスロット・アドレスに到達するた
め、オブジェクトの仮想アドレスのハッシュを実行す
る。そのアドレスがオブジェクト・ヘッダに挿入され
て、使用中テーブルの好ましいスロットまたは項目を識
別する。このスロットは、好ましい同期点として動作す
る。使用中状況の変更に関する次の活動は、そのオブジ
ェクト上で使用中動作を実行する前に、このスロットを
ロックする。

他の普通のハッシュの場合と同じく、複数の仮想アドレ
スが単一のスロット・アドレスにマップされる。次いで
使用中マネージャは、オブジェクトの仮想アドレスをス
ロット項目に挿入し、そのオブジェクトが使用中である
ことを示すフラグをセットする。そのオブジェクトがプ
ロセスによって修正される可能性がある場合、スロット
項目の更新フラグがそう指示するようにセットされる。
異常システム終了の場合、このフラグは、オブジェクト
が正確であることを保証するため、回復中に使用され
て、どのオブジェクトが回復動作を必要とするのかを示
す。

スロットが使用中マネージャによってアクセスされる
間、そのスロットは、他のプロセスによる使用からロッ
クされる。使用中テーブルの各ページに３２バイト（１
バイト当り８ビット）のスロットが１６個ある。ページ
上のどのスロットがすでに占有されているかを示す。使
用中マネージャによってセットされるビット・マップも
各ページにある。２つのオブジェクトが同じスロットに
ハッシュする場合、可能ならそのオブジェクトの１つが
同じページ上の新しいスロットを割り当てられる。ビッ
ト・マップは、どのスロットが利用可能かを検査するた
めに使用される。同じページに利用可能なスロットがな
い場合、使用中テーブルの上端のヘッダ４０は、利用可
能なスロットを有するページの別のマップを含む。使用
中マネージャ３０はまた使用中テーブル３２のサイズも
制御する。使用中マネージャ３０は、テーブルの使用量
に基づいてスロットを追加するが、空間を節約するた
め、使用中テーブルの使用が減少するにつれてスロット
の数を減らすことができる。その結果、使用される資源
割振りの柔軟性が増大して、システムの性能が向上す
る。

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

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

テーブルを拡大する場合、そのテーブルに対するすべて
のアクセスがロックされる。次に、使用中マネージャ
は、まだ割り当てられていないスロットがもはや見つか
らないとき、さらに３２Ｋの記憶域を求める要求を記憶
管理ブロック２０に出す。要求された記憶域を受け取る
と、ヘッダ中のテーブルのサイズが更新されて、テーブ
ル全体に及ぶロックが解除される。

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

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

ＨＡＳＨ（オブジェクトＩＤ）＝（オブジェクトＩＤ＊
素数）ｍｏｄｕｌｏ初期割振り 複数のデータベース・オブジェクトが同じ同期スロット
にハッシュできるので、初期テーブル・サイズが、使用
中になっているオブジェクトの間でどのぐらい競合が見
られるかについての決定的な要因となる。この実施態様
では、１００８項目という初期テーブル・サイズを使用
した。この場合、使用中テーブル上で最高１００８の並
行動作が可能である。テーブルの初期サイズは、３２Ｋ
バイトに選択する。これは、単一の入出力動作で２次記
憶装置に書き込める最高量とも対応する。３２Ｋバイト
記憶域をもう１つのテーブルに追加すると、実際には１
０２４個の新しいスロットが追加される。というのは、
追加の３２Ｋバイト記憶域には新しいテーブル・ヘッダ
は不必要であるからである。コンピュータ・システムの
性能特性に応じて、他のテーブル・サイズも本発明の範
囲内に含まれることは明らかである。

ヘッダ４０はまた、オブジェクトに対する実際の変更の
前に２次記憶装置に書き込むべきスロットの範囲を示す
下限ポインタ４２と上限ポインタ４４も含む。これらの
ポインタは実際にはヘッダ４０に存在するが、図では、
スロットの範囲を示すため実際のスロットを指すように
なっている。言い換えれば、この範囲外のスロット中の
データは、そのテーブルが最後に２次記憶装置に書き込
まれて以降に変更されなかった（更新フラグが０ないし
１に変更されていない）。この機能により、使用中テー
ブルに対する各修正ごとに入出力動作を必要とするので
はなく、単一の入出力動作で使用中テーブルの最近修正
されたすべてのスロットを単一バンドルとして書き込む
ことが可能となる。ヘッダはまた、実行が計画されてい
るディスク書込みを識別する入出力開始番号も含む。こ
れらの計画された開始は、個々のスロット中の項目内に
存在する対応する入出力開始番号と調整される。使用中
マネージャによる入出力開始番号と項目の比較によっ
て、どのスロットがすでに２次記憶装置に書き込まれた
かが明らかになる。

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

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

使用中テーブル・マネージャの主な任務は、テーブルの
揮発性の主記憶装置コピーに追加されたすべてのオブジ
ェクトが、システムのクラッシュ後にテーブルのＤＡＳ
Ｄコピーに現れるようにすることである。テーブルは手
記憶装置で修正されるので、新しく割り振られた使用中
の項目を非揮発性記憶装置に書き込まなければならない
（強制するとも言う）。この動作を、項目の保証と言
う。使用中マネージャは、最小の入出力動作及びテーブ
ル上の資源競合でこれらの機能を実行する。本明細書で
は、揮発性記憶装置とは、内容を失うことがあり得る記
憶装置を言う。重要なことは、２次記憶装置が使用中テ
ーブルのバックアップ・コピーとして使用できることで
ある。

Ｅ−２ロック方法 使用中テーブル・マネージャは、テーブルの各項目内に
存在するロック・フィールドを使用して、各スロットが
一時に１つのプロセスによってしかアクセスされないよ
うにする。これを項目のロッドと言う。項目の書式は第
３図に示されており、後で説明する。ロック・フィール
ドは次の２つの値を持つ。ロック値（Ｌｏｃｋｅｄ）
− あるプロセスが同期のためにこの項目を使用してい
る。非ロック値（Ｕｎｌｏｃｋｅｄ） − 項目がどの
プロセスによってもロックされていない。僅かなオーバ
ーヘッドのみで高レベルの並行性を実現するため、デー
タに対して原子的動作（複数ＣＰＵ環境で、あるＣＰＵ
によるこうしたロック・フィールドの修正が、部分的に
完了した状態では隣接するＣＰＵから決して見えないよ
うな、分割不能に見える動作）を実行するハードウェア
命令を利用する。項目のロック・フィールドを検査して
変更する好ましい方法は、こうした命令（アプリケーシ
ョン・システム／４００プロセッサでは半ワード比較後
交換(Compare and Swap Halfword)命令と呼ばれてい
る）を使用して、ロック・フィールドを修正する。同じ
く良好な別法は、一部のハードウェア・プラットフォー
ムで利用できるテスト後セット(Test and Set)命令を使
用するものである。複数処理環境において記憶装置オペ
ランドの分割不能な検査及び設定を実行する、同様の命
令が、大半の現代のコンピュータ・システム及びマイク
ロ・プロセッサに存在する。

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

下記の表２に示す擬似コードは、テーブル項目の排他的
制御を獲得する論理を記載したものである。排他的制御
が達成されると、その項目はロックされたと言われる。
ｅｎｔｒｙ ａｄｄｒｅｓｓ→ロックという表記は、ポ
インタ値（ｅｎｔｒｙ ａｄｄｒｅｓｓ）の参照解除を
意味し、ｅｎｔｒｙ ａｄｄｒｅｓｓと呼ばれる変数に
よってアドレスされる使用中テーブル項目の好ましい同
期スロット内に存在するロック・フィールドに対するア
ドレス可能性を与える。以下のコードでは、リテラル
“Ｌｏｃｋｅｄ”はスロットの１つの状態を表し、リテ
ラル“Ｕｎｌｏｃｋｅｄ”は他方の状態を表す。表２の
論理は、（あるオブジェクトに対する好ましい同期スロ
ットなどの）使用中テーブル項目の排他的制御を獲得す
る方法を示している。

次の表３の論理は、使用中テーブル項目の排他的制御を
放棄する方法を示したのである。このルーチンは、処理
を呼び出し中のプロセスにより項目がすでに排他的に保
持されており、したがって比較後交換の成否の検査が不
要な場合にのみ使用される。

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

Ｅ−３使用中テーブルの動作 本節では、並行環境で使用中テーブルに対して動作を実
行する方法について説明する。

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

プロセスが、オブジェクトの使用を始めるときに、使用
中マネージャが呼び出されてＩＮＣＲ（使用カウント増
分）動作を実行する。そのオブジェクトがすでに使用中
ではなくなっていた場合、第３図に５０で示す新しいテ
ーブル項目がそのオブジェクトに割り振られて、１の使
用カウント５８で初期設定される。一方、オブジェクト
が他のプロセスによってすでに使用中である場合は、Ｉ
ＮＣＲ動作は、ただスロット・アドレスを用いて、事前
に存在する好ましスロットにマップして、そこに記憶さ
れたカウント５８を増分するだけである。使用カウント
に関する０から１及び１から０への遷移だけが、オブジ
ェクトの回復状態の真の変化を意味する。クラッシュに
直面して十分な回復情報を提供するために、この０から
１への遷移が、非揮発性２次記憶装置に効率的に到達し
なければならない。０から１への遷移が行なわれるとき
は、更新フラグ６４もスロット項目中でセットされる。

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

単一レベル記憶マシンの好ましい実施態様では、オブジ
ェクト識別子（ＩＤ）６０は、単なるオブジェクトのア
ドレスである。多レベル記憶マシンでは、これは単にフ
ァイル名などの識別子でもよい。更新フラグ６４は回復
中に、オブジェクトが特殊な回復活動を実行する必要が
あるかどうかを決定するために使用される。更新フラグ
がオンである場合、オブジェクトの回復が実行される。
ロック・フラグ６６は、その項目がどの時点でも複数の
プロセスによって変更されないようにするために使用さ
れる。これは、表２と表３に記載した項目獲得機能及び
項目解放機能によって使用される。

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

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

２つの主要ソースから、こうしたテーブルに対して競合
が発生する可能性が大きい。すなわち同時に同じスロッ
トをロックしようとする試み、及び他のジョブがこのペ
ージを２次記憶装置に書き出そうと試みているのと同時
にテーブルのページを修正しようとする試みである。低
オーバヘッドの比較後交換機構を上記の並列ロック手順
と併用して、第１の問題に対処する。後でより詳しく説
明するように、バンドル書込み動作と併用して自由スロ
ット配置を慎重に選択すると、第２の問題が軽減され
る。さらに別の方法は、新しいスロットを割り当てる必
要があるときに、テーブルの以前に修正されたどのペー
ジが依然として入出力の最中であるかに関する知識によ
って、自由スロット配置が影響を受けるという機構を設
けるものである。

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

下記の表８の擬似コードは、表６から呼び出され、使用
中テーブルを調べて使用中のオブジェクトを指す項目が
見つかったケースを記述したものである。すなわち、使
用中の項目に記憶されたオブジェクト識別子が、使用中
のオブジェクトのオブジェクト、 ＩＤと同じである。

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

使用中マネージャの減分機能を用いると、もはやオブジ
ェクトにアクセスする必要がないとき、プロセスはオブ
ジェクトの活動ユーザのカウントを減少させる。この機
能は、（データベース・ファイルがクローズされるとき
に発生することがあるように）ユーザがもはやオブジェ
クトを使用していないことを記録するためのものであ
る。オブジェクトを共用するユーザが１人減ったことを
示すために使用カウントが減分される。そのオブジェク
トに関連する使用カウントがゼロになると、その項目
は、オン・ページ・スロット割振りビット・マップの適
切なビットをオフにすることによって割振りが解除され
る。表１０に、減分機能（ＤＥＣＲ）の擬似コードを示
す。

使用中マネージャは、使用中テーブルの項目を見つけて
割り振る。その割振りが必要になるのは、ＩＮＣＲ機能
が使用中のオブジェクト以外のオブジェクトにすでに割
り振られたｓｙｎｃｈ項目を選択するときである。使用
中テーブルの構造は第４図に示してある。使用中テーブ
ル構造には異なる３つの部分がある。使用中テーブル制
御情報ヘッダ８０は、最初及び最後の項目アドレスを含
む。そのアドレスは、ensure required範囲、テーブル
指示サイズ及びテーブル中の項目数の値を指定する。さ
らにテーブル全体について発行された入出力書込み動作
のカウントが含まれている。このテーブルは使用中項目
のセクションを含み、このセクションは複数のオブジェ
クトについての使用中状況情報を保持する複数のスロッ
ト（項目）を含む。項目セクションは、５１２バイトの
論理ページ８２、８４、８６から構成され、各ページは
好ましい実施例では１６個の項目を含む。各ページは別
々にＤＡＳＤに書き込める。各ページは、自己完結型の
項目割振りビット・マップ８８、９０、９２の形の項目
割振り情報を有する。項目ビット・マップはページの各
項目の状況を示す１６ビットを含む。

テーブルのヘッダ８０中のページ割振りビット・マップ
は、そのテーブルのどのページが利用可能な項目をもつ
かを示す。ページ割振りビット・マップのｊ番目のビッ
トは、テーブルの項目セクションのｊ番目の論理ページ
を表す。各ビットは、使用中項目セクションのページの
割振り状態を表す。そのビットは、それが表すページが
満杯である場合、１の値を持つ。０の値は、論理ページ
上に利用可能な空間がまだあることを意味する。

上記のように、使用中テーブルは論理ページに分割さ
れ、各ページは１６個の項目を含む。第３図に示したオ
ブジェクトに関連する使用中状況情報に加えて、各論理
ページの第１項目は、オン・ページ項目割振りビット・
マットと呼ばれる、１６ビットのフィールドをも含む。
一番左側のビットは、ビット・マップを含む周囲の論理
ページ上の第１項目の割振り状況を表す。たとえば、左
から２番目のビットは、論理ページの第２項目の割り振
り状況を表し、以下同様にして、オン・ページ項目ビッ
ト・マップの一番右側のビットは、論理ページの１６番
目の項目の割振り状況を表す。オン・ページ項目ビット
・マップのｉ番目のビットは変更できるのは、そのペー
ジ上の対応する項目が前記の項目獲得手順を用いてロッ
クされているときである。オン・ページ項目ビット・マ
ップへのすべてのアクセスは、望ましいビットだけが変
更されることを保証するため、比較後交換などの原子的
命令を用いて実行することが好ましい。

Ｅ−４項目の割振り ＩＮＣＲ機能から理解できるように、項目を割り振ろう
と試みる際の最初のステップは、オブジェクトを同期項
目にマップし、同期項目が使用できるかどうかを検査す
ることである。考慮すべき最初のケースは、異なるオブ
ジェクトにまだ割り振られていない項目に関するもので
ある。その後、それが割り振られ、オン・ページ項目割
振りビット・マップが更新される。この割振りの結果、
論理ページが満杯になると、そのページが満杯でない状
態から満杯な状態になったので、ページ割振りビット・
マップ８０の対応するビットがトグルされる。ビットの
トグルは、すべてのプロセッサが次にそのビットにアク
セスするときに正確なデータを受け取るように、原子的
に行なわれる。あるページが、あるプロセスの活動のた
めに満杯にされつつあり、同時に他のプロセスが同じペ
ージ上の項目を解放することがあり得る。このビットの
トグルにより、２つの動作が完了したとき正確な状況が
存在すことが保証される。

第２のケースは、好ましい同期項目が他のオブジェクト
にすでに割り振られているときに発生する。この例で
は、オン・ページ項目割振りビット・マップ８８が、同
じページの利用可能な項目を見つけるために検査され
る。これが重要なのは、プロセッサが、すでに１つのペ
ージ・フォールトを起こして、２次記憶装置から同期点
を含むページを主記憶に持ってきていることがあるから
である。主記憶装置にすでに入れられた同じ論理ページ
から代替スロットを選択することを試みることにより、
追加のページ・フォールトを回避することが望ましい。
同期項目と同じページ上の項目が利用可能な場合、その
項目がロックされ、上記のケース１の場合と同様に割り
振られる。したがって、ページ・フォールトは容易に回
避される。

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

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

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

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

ページが選択された後に項目を割り振ろうと試みること
は、かなり容易であり、表１２に示されている。しかし
テーブル・マネージャは並行動作するので、１つの興味
深いアイデアがある。オン・ページ項目ビット・マップ
８８を検査して候補項目を決定する。この検査を行なう
には、比較後交換命令を用いてビット・マップの最も最
近のスナップショットを得る。そのスナップショットを
検査して、このページの最初の未割振り項目を見つけ
る。ページ上の未割振り項目は、オン・ページ項目ビッ
ト・マップ中で１の値で示される。ハードウェア命令を
使って、ビット・マップの最初の１ビットを見つける。
最初の１ビットを見つけるための他の多くの代替手段は
当業者には明らかである。次のステップは、ビット・マ
ップのスナップショットから示された項目の排他的制御
を得ることである。この時点で、並行して実行中のプロ
セスが、自由であると考えられていた項目の排他的制御
を有する場合、遅延に遭遇することがあり得る。したが
って、この項目に対するロックが最終的に許可されたと
き、ビット・マップの新しい原子的スナップショットを
獲得しなければならない。この新しいスナップショット
を検査して、ロックされた項目に対応するビットが、依
然として１で、未割振りであることを意味することを確
認する。そうである場合、そのビットがオフになり、ｎ
ｅｗ ｅｎｔｒｙがこの新しい項目に設定される。

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

下記の表１３の擬似コードは、ページ割振りビット・マ
ップ８０を使って、候補ページがどのようにして選択さ
れるかを記述したものである。

Ｅ−５入出力の最小化 使用中マネージャは、絶対的に必要なときにだけ項目を
非揮発性記憶装置にセーブするために入出力を実行する
ことによって、入出力を最小にする。これを達成するた
めに、いくつかのフィールドがテーブル・ヘッダに追加
される。まず、強制を必要とするテーブル項目の範囲を
示す「上限」ポインタと「下限」ポインタがある。強制
は、その範囲のテーブル項目が、強制される、すなわち
揮発性の主記憶装置から非揮発性２次記憶装置に書き込
まれるという意味で使用する。これは、ページング環境
で実行される共通動作である。ポインタは、強制を必要
とする項目がないことを示すように初期設定される。テ
ーブル・ヘッダ中にはまた、各入出力が開始される直前
及びそれが完了した直後に増分されるカウント・フィー
ルドがある。このカウント・フィールドはゼロに初期設
定される。これは、そのフィールドが偶数であるときは
入出力は進行中ではなく、奇数であるときは入出力が進
行中であることを意味する。このことは後で利用する。
各テーブル項目はまた入出力カウント・フィールド６８
をも含む。入出力カウントをヘッダ・カウントと比較す
ることにより、特定のスロットの内容が補助記憶装置に
書き込まれたかどうかが容易にかつ効率的に決定でき
る。

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

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

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

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

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

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

時間ｔ５で、最初の入出力動作が完了して、ヘッダ１０
３ｅの入出力カウントが２に更新される。これは、集合
１０４ｅのスロット１と３が非揮発性記憶装置に首尾よ
く書き込まれたことを他のプロセスに伝える働きをす
る。これにより、そのスロット２または４が書き込まれ
ることが必要となるまで、他の入出力は発行されない。

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

第２のロックである入出力ロックは、使用中テーブルに
対する同時入出力動作の数を１つの制限するのに使用さ
れる。これは、きわめて短い時間内に開始される後続要
求が１つの入出力動作に縮小できるようにするためのも
のである。そのシナリオは次の通りである。タスク１が
いくつかの変更を保証するために入出力要求を発行する
（時間ｔ０）。タスク２が、時間ｔ１でいくつかの変更
を行ない、入出力のウィンドウを更新する。タスク１
は、このとき時間ｔ２で入出力ロック及び制限ロックを
獲得する。タスク１に対して入出力動作が実行され、そ
の後タスク２のデータが書き込まれる。タスク２は最後
に入出力の制御を獲得し、入出力動作がすでに完了した
ことを発見する。タスク２は、不必要なのでその入出力
を実行しない。細分性をさらに向上させるため、この方
法を、入出力動作を使用中テーブルの複数のゾーンに同
期させる場合にも適用できる。各ゾーンは、別々のＤＡ
ＳＤ装置上に割り振られる。次に各ゾーンごとに１つの
入出力動作が実行される。これを達成するため、上下限
並びに入出力カウントが、テーブルの各ゾーン（エクス
テント）ごとに複製される。また、制限ロック及び入出
力ロックも各ゾーンごとに必要である。この拡張態様
は、複数の記憶エクステントにわたる大きなテーブルの
性能の向上をもたらす。

この方法の実施は、論理的に２つの機能部分に分けられ
る。最初の部分は、テーブル項目が増分動作を通じて作
用を受けるときに呼び出される。保証情報取扱い更新ル
ーチンが、前述の増分手段から呼び出される。擬似コー
ドは表１４の通りである。

使用中の強制ルーチンは、表１５に示すように、適切な
ときに、テーブル項目を補助記憶装置に書込むことを扱
う。

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

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

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

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

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

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

【図面の簡単な説明】

第１図は、複数処理環境における使用中テーブル・マネ
ージャの論理構成図である。第２図は、第１図のテーブ
ル・マネージャの高レベル流れ図である。 第３図は、使用中テーブルの項目中のフィールドの構成
図である。 第４図は、複数の項目をもつ使用中テーブルの構成図で
ある。 第５図は、入出力動作に関するカウンタを示す使用中テ
ーブルの複数部分の連続した一連の構成図である。 １２、１４……データベース・ファイル、１６、１８…
…ヘッダ、１７……２次記憶装置、１９……メモリ・ブ
ロック、２１、２２、２３……プロセス、２６、２７、
２８……プロセッサ、３０……使用中マネージャ、３２
……使用中テーブル、３４……スロット、４０……ヘッ
ダ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジヨン・ジヨセフ・ブリーゼン アメリカ合衆国ミネソタ州ザンブロタ、ワ ーレン・アヴエニユー330番地 (72)発明者 デヴイド・ローランド・ウエルシユ アメリカ合衆国ミネソタ州ロチエスター、 サウス・イースト・セカンド・ストリート 1112番地 (72)発明者 ラリイ・ウイリアム・ヤングレン アメリカ合衆国ミネソタ州ロチエスター、 アパートメント18‐エフ、ノース・ウエス ト・フオーテイーンフアースト・ストリー ト1505番地 (56)参考文献 特開 昭63−196956（ＪＰ，Ａ) 特開 昭61−91730（ＪＰ，Ａ)

Claims (3)

【特許請求の範囲】
1. 【請求項１】少なくとも一のプロセスによって使用され
   ている複数のオブジェクトの識別子をそれぞれ格納する
   ための複数のスロットを含む、使用中テーブルを管理す
   る方法であって、 ａ．一のオブジェクトのヘッダ内に、前記使用中テーブ
   ルの一のスロットのアドレスを挿入することにより、当
   該一のスロットに当該一のオブジェクトを割り当てるス
   テップ、 ｂ．前記一のオブジェクトのヘッダ内に挿入された前記
   スロット・アドレスを使用して前記一のスロットを選択
   するとともに、当該一のスロットに前記一のオブジェク
   トの識別子を挿入するステップ、 ｃ．前記スロット・アドレスによって選択された前記一
   のスロットに保持されているロック指示を使用して、複
   数のプロセスによる当該一のスロットの同時的アクセス
   を防止するステップ、 ｄ．前記スロット・アドレスによって選択された前記一
   のスロットに、前記一のオブジェクトの使用中指示を与
   えるステップ、及び ｅ．前記スロット・アドレスによって選択された前記一
   のスロットに、前記一のオブジェクトが修正される可能
   性があることを示す更新指示を与えるステップ、 を含む、使用中テーブルの管理方法。
2. 【請求項２】前記使用中指示を与えるステップｄが、 ｄ１．一のプロセスが前記一のオブジェクトのアクセス
   を開始する場合は、前記一のスロットに保持されている
   当該一のオブジェクトの使用中カウントを増分し、 ｄ２．一のプロセスが前記一のオブジェクトのアクセス
   を終了する場合は、前記一のスロットに保持されている
   当該一のオブジェクトの使用中カウントを減分し、 ｄ３．前記使用中カウントがゼロとなる場合は、前記一
   のオブジェクトに対する前記一のスロットの割り当てを
   解除する、 ことを含む、請求項（１）記載の使用中テーブルの管理
   方法。
3. 【請求項３】前記更新指示を与えるステップｅが、 前記使用中カウントがゼロから１に遷移する場合、前記
   一のスロットに保持されている前記一のオブジェクトの
   更新フラグをセットする、 ことを含む、請求項（２）記載の使用中テーブルの管理
   方法。