JPH0317142B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の背景〕 本発明はワード・プロセシング・システムに係
り、更に詳細に説明すればデータ・セツトの更新
中に媒体エラー又はシステム電源の障害等が生じ
たとき直接アクセス記憶デバイス（DASD）の記
憶データを回復することに係る。

本発明に関係する先行技術には、次のようなも
のがある。

(a) IBM OS／６システムは、デイスケツトに
文書を記憶し且つデイスケツト上の文書を探し
出すために、非常に簡単なフオーマツトを使用
している。各デイスケツトでは正確に32個のデ
ータ・セツト（ジヨブ）が常に利用可能であ
り、その割振りはデイスケツトのトラツクに応
じて行われるようになつている。デイスケツト
上の文書を探し出すために使用されるデイスケ
ツト・インデツクスの全体は十分に小さいの
で、これをシステム・メモリーに一度に保持す
ることができる。IBM OS／６システムのボ
リユーム・インデツクスは、デイスケツトに冗
長的に記録されている。IBM OS／６システ
ムのデイスケツト・インデツクスは、デイスケ
ツトがその駆動機構へ挿入されるとき、システ
ム・メモリへコピーされるようになつている。
従つて、このインデツクスを検索する動作は、
性能上の問題を惹起しない。

このアプローチの１つの問題は、１デイスケ
ツトあたり正確に32個のジヨブが利用可能でな
ければならないという点にある。一般に、ワー
ド・プロセシング・システムは可変数のデー
タ・セツトを所与のデイスケツト・ボリユーム
に記憶することを必要とするものであり、従つ
て32個以上のデータ・セツトが操作員に利用可
能でなければならない。このことは、１つの記
憶ボリユームが大容量の内部ハード・デイスク
であるようなワード・プロセシング・システム
について特にあてはまる。

このアプローチの他の問題は、デイスケツト
上のスペースが各トラツク単位で特定のデー
タ・セツトへ割振られる、という点にある。つ
まり、平均的な状況では、デイスケツト上の無
駄なスペース（割振られてはいるがデータを実
際に記憶するように使用されていないスペー
ス）は実際に使用されている各ジヨブあたり1/
２トラツクにも達する。言いかえれば、所与の
デイスケツトで利用可能な70トラツクのうち最
大16トラツクが無駄となるのである。

(b) IBMデイスプレイライター・システムは、
拡張ヘツダ・ベル（EHL）と呼ばれるデイス
ケツト・インデツクスとデータ・セツト・ラベ
ル（DSL）と呼ばれるデータ・セツト・イン
デツクスから成る２レベルのデイスケツト・イ
ンデツクスを利用している。EHLはデイスケ
ツト上にあるデータ・セツトの位置を示し、
DSLは既存の各データ・セツトごとに１つず
つ設けられる。EHLは一定サイズであり、
DSLのサイズは対応するデータ・セツトのサ
イズに依存する。文書の或るページを探し出す
には、該当するDSLの開始点から適当な点ま
で探索することにより、このページがデイスケ
ツトのどこに置かれているかを探し出すことが
必要である。

このアプローチの問題は、デイスケツト上の
EHL又はDSL領域における媒体エラーに対し
非常にもろい、という点にある。もしEHLを
保持する媒体セクタを適正に読取ることができ
なければ、このEHLブロツクによつてアクセ
スされるすべてのデータ・セツト及び後続の
EHLブロツクによつてアクセスされるすべて
のデータ・セツトが失われ、従つて操作員はも
はやこれらのデータ・セツトをアクセスするこ
とができない。DSLについても、同様の問題
が生ずる。すなわち、もし或るDSLセクタを
デイスケツトから適正に読出すことができなけ
れば、このDSLブロツク及びそのすべての後
続ブロツクが失われるので、これらのDSLセ
クタによつてアクセスされるすべてのレコード
も同様に失われことになる。

前掲のIBM OS／６システム及びIBMデイ
スプレイライター・システムの他の問題は、デ
イスケツト上の或る物理セクタにエラーのない
ことが、デイスケツトを使用する際の不可欠の
条件である、という点にある。このことはシリ
ンダ０（ホーム位置にある読取／書込ヘツドで
アクセスされるデイスケツト・トラツク）につ
いてあてはまり、ここにはボリユームの残りの
内容を解釈するように標準アーキテクチヤに従
つて構成された或る種の情報を格納することが
必要である。言いかえれば、もし或るデイスケ
ツトのトラツクでエラーが検出されれば、この
デイスケツトをそれ以上使用することができな
いのである。

(c) IBM 3730は、データ・セツト・インデツク
スをデータとともに揮発性の作業記憶に分散式
に記憶させている。各データ・ブロツクは制御
領域を有し、この制御領域には前のブロツク及
び次のブロツクの位置情報が保持されている。
このように現ブロツクは常に前のブロツク及び
次のブロツクを指定しているので、順次アクセ
スについてはこれを非常に高速に行うことがで
きる。

このアプローチの問題は、（データ・セツト
の中間部に置かれたブロツクを直接的に参照す
るようなランダム・アクセスが遅いという点に
ある。というのは、そうするためには先行する
すべてのブロツクを読取らねばならないからで
ある。従つて、ランダム・アクセス時の性能を
向上させるには、ランダム・アクセス用に設定
された他のデータ・セツト・インデツクスを必
要とすることになろう。

〔発明の概要〕

従つて、本発明の目的は、データ・セツト・イ
ンデツクスを保存することにより、媒体エラーの
ために失われやすい操作データの量を減少させる
とともに、媒体エラーや電源の障害若しくは他の
異常な条件に起因するデータ・セツト若しくはボ
リユーム・インデツクスの不完全な更新の後に回
復される操作データの量を増大させることにあ
る。

前記及び他の目的並びに利点は、本発明によつ
て達成される。簡単に言えば、本発明に従つた方
法及び装置は、情報をアクセスする際に、すなわ
ちDASDから情報を取出すか又はDASDへ情報を
書込む際に、ボリユーム上の重要（クリチカル）
情報を保護するように編成されている。ここで、
重要情報とは、これを失うと相当量の操作データ
が失われ、そしてかかるデータを再び作成するの
に操作員が相当の時間を必要とする。そのような
情報である。本発明の目的は、次の２つの方法を
通して達成される。

第１に、通常のシステム動作中に、データ・セ
ツト・インデツクス又はボリユーム・インデツク
スが更新されねばならない場合、重要情報のセク
タが２つのコピーの形で記憶ボリユームへ書込ま
れる。第１のコピーは上位レベルのインデツクス
によつて指示された位置に置かれ、第２のコピー
は第１のコピーから一定距離だけ離れた位置に置
かれる。従つて、もし第１のコピーが置かれたボ
リユーム上の位置が知られているならば、媒体エ
ラーのために第１のコピーを適正に取出すことが
できない場合でも、第２のコピーを探し出すこと
ができる。

第２に、たとえば或るデータ・セツトの更新が
終了していない場合にデータ・セツト又はボリユ
ーム・インデツクスでエラーが検出されたとき
は、できるだけ多くの情報を回復するようにすべ
てのボリユーム及びデータ・インデツクスがスキ
ヤンされる。このスキヤニング技法は、データ・
セツト・インデツクスに欠陥がないことを仮定し
た通常の記憶アクセス方式（SAM）の動作に使
用されるスキヤニング技法よりも一層完全であ
り、インデツクス構造中のエラーのために通常の
高性能探索ルーチンが探し出すことができないよ
うなデータであつてもこれを探し出すことができ
るのである。

〔実施態様の説明〕

第１図を参照するに、図示されたワード・プロ
セシング・システム１０はキーボード１２を包
み、これは入力されたテキスト及び指令をチヤネ
ル１４を介してプロセツサ１６へ転送する。プロ
セツサ１６はメモリ・バス１８へ接続され、該メ
モリ・バスはCRTデイスプレイ２０、デイスケ
ツト又はハード・デイスクの如き１以上の直接ア
クセス記憶デバイス（以下DASDと略す）２２、
プリンタ２４及びランダム・アクセス式のシステ
ム・メモリ（以下メモリと略す）２６へ接続され
る。

操作員がキーボード１２を介してテキスト・ス
トリームを入力すると、このテキストの各ページ
はメモリ２６に記憶され且つそこで処理される。
テキスト・ストリームがメモリ２６に受取られる
場合、このストリームはデイスプレイ２０にも供
給される。キーボード１２を介して入力された
後、テキストはDASD２２に記憶されるか又はプ
リンタ２４によつて印刷されうる。

メモリ２６は多数のデータ領域を含み、また記
憶されたテキストを処理するための複数の機能プ
ログラムを含んでいる。テキスト及びそれに関係
する制御機能はテキスト記憶バツフア（以下
TSBと略す）２８に記憶される。

TSB制御ブロツク３０はTSB２８のデータ領
域として使用され、チヤネル３２を介してTSB
２８へ接続される。キーボード１２を介して各文
字が入力される場合、この文字はキーストロー
ク・サービス・ルーチンの集合３４を介してメモ
リ２６に受取られる。キーストローク制御ブロツ
ク３６は１つのデータ領域であつて、受取られた
文字を処理するための所定のキーストローク・サ
ービス・ルーチンを決定する。このため、キース
トローク制御ブロツク制御ブロツク３６はチヤネ
ル３８を介してキーストローク・サービス・ルー
チン３４へ連結される。さらにキーストローク・
サービス・ルーチン３４はチヤネル４０を介して
TSB２８へ連結され、そしてチヤネル４２を介
してTSB制御ブロツク３へ連結される。

テキストがTSB２８へ移動されるか又はそこ
から移動されねばならないことをTSB制御ブロ
ツク３０が指示する場合、この移動要求はチヤネ
ル４６を介して記憶アクセス方式（以下SAMと
略す）ルーチン４４へ通知される。SAMルーチ
ン４４は、DASD２２とメモリ２６との間のすべ
てのデータ移動を制御するために使用される。
（キーボード１２、デイスプレイ２０又はプリン
タ２４との通信が必要とされる場合には、SAM
ルーチン４４の代わりにそれぞれのアクセス方式
ルーチンが使用されるが、これらは本発明の要旨
に関係ないので以下省略する。）キーストロー
ク・サービス・ルーチン３４は、チヤネル４８及
びSAMインタフエース制御ブロツク５０を介し
て、SAMルーチンへ他の制御情報及びデータを
通信する。（キーボード１２、デイスプレイ２０
又はプリンタ２４との通信が必要とされる場合に
は、SAMインタフエース制御ブロツク５０の代
わりにそれぞれのアクセス方式に対応するインタ
フエース制御ブロツクが使用される。）このSAM
サービス要求を完了した場合、SAMインターフ
エース制御ブロツク５０は処理を継続するために
キーストローク・サービス・ルーチン３４によつ
て使用されるべき他の情報及びデータを保持して
いる。SAMインタフエース制御ブロツク５０は
チヤネル５２を介してSAMルーチン４４へ接続
される。

SAMブロツク５４はメモリ・バス１８を介し
てDASD２２と接続され、PASD２２とメモリ２
６との間のデータ転送に対する転送点として使用
される。（キーボード１２、デイスプレイ２０又
はプリンタ２４との通信が必要とされる場合に
は、SAMブロツク５４の代わりにそれぞれのア
クセス方式に対応するブロツクが使用される。）
SAMブロツク５４はチヤネル５６を介してTSB
２８と接続される。SAMルーチン４４はチヤネ
ル５８を介してSAMブロツク５４中のデータを
アクセスすることがきる。SAMブロツク５４は
チヤネル６０を介してSAMインタフエース制御
ブロツク５０へ連結されているが、これはキース
トローク・サービス・ルーチン３４へ情報及びデ
ータを通信するためである。

SAM内部制御ブロツク６２は、DASD２２に
関する現在のステータス及び情報を保持するため
に設けられている。（キーボード１２、デイスプ
レイ２０又はプリンタ２４との通信が必要とされ
る場合には、ブロツク６２の代わりにそれぞれの
対応ブロツクが使用される。）DASD２２とSAM
内部制御ブロツク６２との間の情報転送は、チヤ
ネル６４及びSAMブロツク５４を介して行われ
る。SAM内部制御ブロツク６２中の情報はチヤ
ネル６６を介してSAMルーチン４４へ通信され、
該ルーチンによつて管理される。SAM内部制御
ブロツク６２は、SAMルーチン４４及びSAMブ
ロツク５４の動作に必要なフラグ及びステータス
情報を記憶するために使用される。

ここで、第１図を参照してワード・プロセシン
グ・システム１０の動作を簡単に説明すると、操
作員がキーボード１２を介して各キーストローク
を入力する場合、これに対応する信号がチヤネル
１４を介してプロセツサ１６へ転送され、かくて
該プロセツサはこのキーストローク指令をメモリ
２６へ記入する。このようにしてキーストローク
指令を受取ると、キーストローク・サービス・ル
ーチン３４のうちでこの特定の指令を処理すべき
所定のルーチンが選択される。当該キーストロー
ク指令はそれが制御指令又はグラフイツク・エン
トリのどちらであるかに応じて処理され、そして
その処理結果はTSB２８へ記入される。これら
のグラフイツク及び指令がTSB２８に順次に累
積されるる間、テキスト情報はデイスプレイ２０
に供給される。TSB２８が必要なテキスト及び
指令を保持するに十分でない危険がある場合、キ
ーストローク・サービス・ルーチン３４はSAM
インタフエース制御ブロツク５０に制御情報を記
憶することにより、SAMルーチン４４をして
DASD２２へ情報ブロツク（レコード）を転送さ
せるようにする。

操作員は、制御指令を通して、メモリ２６、デ
イスプレイ２０、DASD２２及びプリンタ２４の
間で情報を転送させることができる。また選択さ
れたページをDASD２２からメモリ２６へ呼出す
ことができるので、操作員はテキストを変更及び
訂正してこれをDASD２２へ再び記入したり、プ
リンタ２４で印刷させることができる。

第２図には、プロセツサ１６の代表的なハード
ウエア要素が詳細に図示されている。プロセツサ
１６は市販されているものでよく、たとえばイン
テル社のマイクロプロセツサ８０８６を使用する
ことができる。

このようなプロセツサ１６は制御ユニツト８０
を含み、該ユニツトはキーボード１２、DASD２
２又はプリンタ２４からデバイス・バス８２に生
ぜられるような割込信号に応答する。また、制御
ユニツト８０はデータ及びアドレス転送用の内部
バス８４へ接続され、該バスはプロセツサ１６の
他のユニツトへ相互接続されている。

制御ユニツト８０はメモリ２６からの取出命令
に応答して制御信号を発生し、該制御信号をプロ
セツサ１６の他のユニツトへ供給する。これらの
制御信号は制御線８６を介して種々のユニツトへ
供給されるが、第２図では制御線８６は演算論理
ユニツト（ALU）８８へ直線的に接続されるよ
うに図示されているに過ぎない。制御ユニツト８
０と他のユニツトとの同期動作は、外部クロツク
源（図示せず）からプロセツサ１６へ供給される
クロツク・パルス入力によつて達成される。外部
クロツク源によつて発生されたクロツク・パルス
は、バス９０を介して他のユニツトへそれぞれ転
送される。

プロセツサ１６で処理すべきデータ及び命令
は、バス制御ユニツト９２を介して入力される。
また処理すべきデータがプログラムＩ／Ｏ制御ユ
ニツト９４から入力されることもある。バス制御
ユニツト９２はメモリ２６の記憶要素を相互接続
するとともに、Ｉ／Ｏ制御ユニツト９４又はメモ
リ２６から受取られたデータを処理するための命
令を受取る。かくて、Ｉ／Ｏ制御ユニツト９４は
キーボード１２、DASD２２又はメモリ２６から
のデータを受取るのに対し、バス制御ユニツト９
２はメモリ２６から命令及び／又はデータを受取
る。しかしながら、メモリ２６の互いに異なるセ
クシヨンを命令メモリ及びデータ・メモリとして
使用することも可能であるという点に注意すべき
である。

プロセツサ１６からのデバイス制御情報は、プ
ログラムＩ／Ｏ制御ユニツト９４を介してＩ／Ｏ
データ・バス９８に供給される。キーボード１２
又は他のデバイスからＩ／Ｏデータ・バス９８に
供給される入力データは、メモリ・バス１８及び
内部バス８４を介して制御ユニツト８０へ供給さ
れる命令の制御下で、ALU８８によつて最初に
処理される。ALU８８は線８６上の制御信号に
応答してこの命令に従つた演算を遂行するととも
に、その結果をスクラツチ・レジスタ１０２に記
憶することができる。

もちろん、ALU８８と他のユニツトとの間で
他の種々のデータ転送を行うことも可能である。
たとえば、ALU８８から内部バス８４を介しプ
ログラム・カウンタ１０４、データ・ポインタ・
レジスタ１０６又はステータス・レジスタ１１０
へデータを転送することが可能である。

プロセツサ１６の特定の動作は、メモリ・バス
１８にある命令及びデータと双方向性のＩ／Ｏデ
ータ・バス９８にある入力データとによつて決定
される。たとえば、プロセツサ１６は受取られた
命令に応答して、スクラツチ・レジスタ１０２中
の記憶データを、レジスタ１０６，１０８又は１
１０のうち任意のレジスタへ転送する。第２図に
図示されているプロセツサ１６のかかる動作は当
業者には明らかであるし、またこれは本発明の要
旨には関係がないので、以下では各動作の説明を
省略する。

DASD２２上の記憶媒体に記憶されたページ
は、複数のレコード（適当なサイズを有するるテ
キスト単位）へ区分される。レコードは最大のサ
イズを有する。かくて、各ページは少くとも１つ
のレコードから成り、多くの場合はそれ以上のレ
コードから成る。各ページ中のレコード数及び各
文書中のページ数は不定であり、当該データ・セ
ツトを記憶すべき記憶ボリユームの容量によつて
制限されるに過ぎない。ワード・プロセシング・
システム１０では、各データ・セツトはDASD２
２中の単一のデイスケツトに記憶されるか又はハ
ード・デイスクに記憶される。もしワード・ブロ
セシング・システム１０へ記入中の或る文書が単
一のデイスケツトに収まりきらなければ、操作員
は現在のデイスケツト又はハード・デイスクに対
する記入動作を終了するとともに、他のデイスケ
ツト上の別のデータ・セツトにこの文書を継続し
て記入するようにしなければならない。

DASD２２上の記憶媒体は、当技術分野では周
知のように、複数のセクタへ区分される。セクタ
の概念は当技術分野では周知であると考えられる
ので、本発明を理解するのにその詳細な説明は不
要であろう。ワード・プロセシング・システム１
０では、記憶媒体上の各セクタは一意的な論理セ
クタ番号を割振られている。但し、これらの論理
セクタ番号はゼロから始まる連続的な正の整数で
ある。論理セクタ番号の各々が記憶ボリユーム上
にある唯１つの物理領域に対応する限り、特定の
論理セクタ番号が記憶媒体上のどの物理領域に対
応するかということは、本発明を理解する上で重
要なことではない。複数の論理セクタ番号が連続
的な整数である場合は、これらの論理セクタは連
続的であるとみなされる。

第３図には、或るテキスト文書がDASD２２上
の１つのデータ・セツト１２０へ編成されている
１つの例が示されている。例示したデータ・セツ
ト１２０は、データ・セツト・インデツクス１２
２と３つのテキスト・ページ、即ちページ１（１
２４）、ページ２（１２６）及びページ３（１２８）
から成る。ページ１（１２４）は３つのレコード、
即ちレコード０（１３０）、レコード１（１３２）
及びレコード２（１３４）を有する。ページ２（１
２６）は単一のレコード０（１３０）を有するに
過ぎない。ページ３（１２８）はつのレコード、
即ちレコード０（１３６）及びレコード１（１３
８）を有する。

データ・セツト・インデツクス１２２は、デー
タ・セツト１２０の前記ページが置かれている記
憶媒体上の位置を決定するために第２図のSAM
ルーチン４４によつて使用される。データ・セツ
ト・インデツクス１２２は文書の各ページごとに
１つのインデツクス・エントリを含み、この例で
はページ１ないしページ３にそれぞれ対応するイ
ンデツクス・エントリ１４０，１４２及び１４４
を含んでいる。

所望のページを速かに探し出すことができるよ
うに、各ページ・インデツクス・エントリは該エ
ントリによつて参照されるページを識別するため
の１つのページ・キーを含む。かくて、この例で
は、ページ１・キー１４６、ページ２・キー１４
８及びページ３・キー１５０が含まれている。た
とえば、ページ２（１２６）を探し出すためには、
そのキーとページ１・キー１４６を単に比較する
だけでページ１・インデツクス・エントリ１４０
が適切でないことがわかる。ワード・プロセシン
グ・システム１０では、各データ・セツト・イン
デツクス中のすべてのページ・キーは一意的でな
ければならない。

或るページの各レコードは、そのインデツク
ス・エントリのレコード記述子を通して探し出さ
れる。各レコードは、記憶ボリユームにある連続
的な１組の論理セクタに記憶される。或るレコー
ドに割振られる論理セクタの数は、このレコード
を保持するに必要なセクタの最小の数に対応す
る。これらのセクタは全体としてそのまま割振ら
れるのである。レコード記述子は、当該レコード
を保持する記憶媒体上の論理セクタのうち、最小
の論理セクタ番号を有する論理セクタ位置を指示
する。またレコード記述子は、当該レコードの長
さも指示する。たとえば第３図では、ページ１・
レコード０（１３０）に対するレコード記述子は、
ページ１・インデツクス・エントリ１４０におい
てレコード０・記述子１５２として設けられてい
る。ページ１（１２４）の残りのレコードは、レ
コード１・記述子１５４及びレコード２・記述子
１５６によつて記述される。単のレコードを保持
するページ２（１２６）の記憶媒体上の位置は、
ページ２・インデツクス・エントリ１４２に設け
られたレコード０・記述子１５８によつて決定さ
れる。前述と同様に、ページ３・インデツクス・
エントリ１４４はレコード０・記述子１６０及び
レコード１・記述子１６２を含み、これらによつ
てページ３のレコード０（１３６）及びレコード
１（１３８）をそれぞれ探し出す。

ワード・プロセシング・システム１０のDASD
２２に記憶されたデータ・セツトのデータ・セツ
ト・インデツクス１２２は、複数のノード（節）
へ区分される。このようにして区分された各イン
デツクス・ノードは、それぞれ１つの論理セクタ
に記憶される。もし、当該データ・セツトへテキ
ストを追加したとき１つのインデツクス・ノード
に置かれる情報の量が１つの論理セクタに記憶可
能な量を越えるようになれば、このインデツク
ス・ノードを２つ以上のインデツクス・ノードへ
分割し、そして分割後の各インデツクス・ノード
をそれぞれ１つの論理セクタに保持させるように
することができる。すべてのデータ・セツトはそ
れぞれ少くとも１つのインデツクス・ノードを有
する。

各データ・セツトごとに、ルート・ノード（根
幹の節）と呼ばれる一意的な１つのインデツク
ス・ノードがある。これに対し、リーフ・ノード
（葉の節）と呼ばれるインデツクス・ノードがあ
るが、このリーフ・ノードはそのインデツクス・
エントリによつてページを直接的に参照するよう
なものである。第４Ａ図に例示されたデータ・セ
ツト・インデツクスは十分に小さく、必要とされ
る単一のリーフ・ノードとルート・ノードが同じ
ノードであるので、ルート／リーフノード１７０
と呼ばれる。ルート／リーフ・ノード１７０は、
データ・セツト・プロフイル１７２とインデツク
ス構成要素１７４を含む。データ・セツト・プロ
フイル１７２は、全体として当該データ・セツト
に関係する情報及びステータスを保持する。デー
タ・セツト名１７６は、操作員がアクセスすべき
文書を選択することを可能にするようなテキス
ト・グラフイツクを保持する。データ・セツト・
コメント１７８は当該文書に関する記述情報の追
加スペースを与えるので、操作員がデータ・セツ
ト名１７６の１部として記入したくない情報をこ
こに置くことができる。

第４Ｂ図では、ルート／リーフ・ノード１７０
のインデツクス構成要素１７４に関する一層詳細
な情報が示されている。リーフ・ノードのインデ
ツクス構成要素１８０は、当該文書のページを直
接的にポイントするような複数のインデツクス・
エントリを含む。図示の例では、インデツクス構
成要素１８０は、ページＮ１・インデツクス・エ
ントリ１８２及びページＮ２・インデツクス・エ
ントリ１８４を含む。但し、Ｎ１及Ｎ２は当該文
書における１対の連続ページのページ番号を表わ
す。ページＮ１・インデツクス・エントリ１８２
は、ページＮ１・キー１８６とページＮ１中の各
レコードごとに１つのレコード記述子、即ちこの
例ではレコード０・記述子１８８及びレコード
１・記述子１９０を保持する。同様に、ページＮ
２・インデツクス・エントリ１７７はページＮ
２・キー１８１を保持し、そしてレコード０・記
述子１８２及びレコード１・記述子１８３を保持
する。

所与のインデツクス構成要素では、そのインデ
ツクス・エントリはページ・キーの昇順に記憶さ
れている。従つて、もし当該文書中のページＮ１
及びＮ２が同じリーフ・ノードで参照され、そし
てページＮ１の直後にページＮ２が続くのであれ
ば、ページＮ１・インデツクス・エントリ１７６
の直後にページＮ２・インデツクス・エントリ１
７７が続くように配列される。

第４Ｃ図には、第４Ａ図のノード・ヘツダ１７
１が一層詳細に図示されている。ノード・ヘツダ
１７１は、データ・セツト・インデツクスの一部
として当該インデツクス・ノードに関する情報を
与える。第４Ｃ図に示したフオーマツトはすべて
のインデツクス・ノードに共通であるが、各フイ
ードの内容はデータ・セツトごとに異なることが
あり、また同じデータ・セツトでもインデツク
ス・ノードごとに異なることがある。ノード長１
８４は当該インデツクス・ノードで使用可能なデ
ータの全体的長さを保持する。ノード長の値と
DASD２２のセクタ・サイズとの差は、当該イン
デツクス・ノードが充満する前の残存スペース量
を指示する。

オブジエクト識別子（ID）１８５はこのイン
デツクス・ノードが属するデータ・セツトのタイ
プを示し、これはオブジエクト属性１８６及びオ
ブジエクト・タイプ１８７から成る。オブジエク
ト・タイプ１８７はデータ・セツトの一般的なタ
イプを示す。たとえば、すべてのテキスト文書は
同じオブジエクト・タイプを有する。オブジエク
ト属性１８６は、このインデツクス・ノードが或
る下位レベルのデータ・セツトはデータセツトの
インデツクス（デイレクトリ）のどちらに属する
のはということを示す。

ノード階層１８８は、インデツクス・ノードの
タイプを示す。インデツクス・ノードの種々のタ
イプには、ルート・ノード（主面なデータ・セツ
ト・ノード）、リーフ・ノード（データ・セツト
のレコードを直接的にポイントするノード）、ル
ート／リーフ・ノード（ルート・ノード及びリー
フ・ノードの組合せ）及び中間ノードがある。第
４Ａ図は、小さなデータ・セツトに対するルー
ト／リーフ・ノード１７０を示す。

ノード・レベル１８９は、当該ノードがデー
タ・セツト中で占めるレベルを示す。リーフ・ノ
ードは常にノード・レベル値として０を有し、こ
のことはルート・リーフ・ノードにもあてはま
る。というのは、当該ノードがルート・ノードで
あると同時に、リーフ・ノードでもあるからであ
る。もし当該データ・セツトが複数のインデツク
ス・ノードを必要とするような大きなものであれ
ばインデツクス中の任意のノードに対するノー
ド・レベルはリーフ・レベルからの距離を示す。
かくて、ルート・ノードのノード・レベルは常に
当該データ・セツトにおけるレベルの最大数を示
す。なぜなら、SAMルーチン４４はルート・ノ
ードから任意のリーフ・ノードへのレベル数が等
しいことを保証するからである。

トリーID１９０はノード・ヘツダの最終部分
であり、記憶ボリユーム上の当該データ・セツト
について一意的であるようなデータ・セツトID
を保持する。同じデータ・セツトにあるすべての
インデツクス・ノードは同じトリーIDを有し、
異なるデータ・セツトに属するインデツクス・ノ
ードは異なるトリーIDを有する。トリーIDはデ
ータ・セツトの作成時に割振られ、同じDASD２
２に同じデータ・セツトが存在する限り再び割振
られることはない。

操作員が当該文書に多くのテキスト・レコード
及びページを追加する場合には、ルート／リー
フ・ノード１７０のインデツクス構成要素１７４
は結果的にこれらのエントリを保持することがで
きなくなる。このような場合、ルート／リーフ・
ノード１７０は適当に分割され、たとえば第５Ａ
図に示すように、１つのルート・ノード２００、
１つのリーフ・ノードＡ（２０２）及び１つのリ
ーフ・ノードＢ（２０４）へ分割される。ルー
ト・ノード２００は、ルート／リーフ・ノード１
７０と同じデータ・セツト・プロフイル１７２と
ルート／中間インデツクス構成要素２０５を含
む。リーフ・ノードＡ（２０２）はリーフ・ノー
ド・チエーン２０６及びインデツクス構成要素２
０８を含み、一方、リーフ・ノードＢ（２０４）
はリーフ・ノード・チエーン２１０及びインデツ
クス構成要素２１２を含む。第４Ｃ図を参照する
に、第５Ａ図に示したルート・ノード２００のノ
ード・レベル１８９は値１を有し、リーフ・ノー
ド２０２及び２０４のノード・レベル１８９は値
０を有する。

リーフ・ノードＡ（２０２）及びリーフ・ノー
ドＢ（２０４）のインデツクス構成要素２０８及
び２１２は、第４Ａ図におけるルート／リーフ・
ノード１７０のインデツクス構成要素１７４（詳
細については第４Ｂ図のインデツクス構成要素１
８０を参照のこと）と同じ情報を保持する。第５
Ａ図の例では、インデツクス構成要素１８０は２
つのインデツクス構成要素２０８及び２１２に分
割されており、ページＮ１及びその前にあるすべ
てのページのインデツクス・エントリがリーフ・
ノードＡ（２０２）のインデツクス構成要素２０
８に記憶されるのに対し、ページＮ２ないしＺ
（当該文書の最終ページ）のインデツクス・エン
トリはリーフ・ノードＢ（２０４）のインデツク
ス構成要素２１２に記憶される。このことは、ペ
ージＮ１・インデツクス・エントリ１８２がイン
デツクス構成要素２０８中の最後のインデツク
ス・エントリであり、そしてページＮ２・インデ
ツクス・エントリ１８４がインデツクス構成要素
２１２中の最初のインデツクス・エントリである
ことを暗示する。この例では、ページＺは当該文
書の最終ページであるから、ページＺ・インデツ
クス・エントリ２１４はインデツクス構成要素２
１２の最後のインデツクス・エントリである。

第５Ａ図及び第５Ｂ図に示されたインデツクス
構造によれば、所望のページに対するリーフ・ノ
ードを速やかに選択することができる。ルート・
ノードのインデツクス構成要素を探索し且つ所望
のページのキーを各インデツクス・エントリのキ
ーと比較する間、所望のページのキーよりも大き
いページ・キーを保持するルート・ノード２００
中の最初のインデツクス・エントリは、所望のペ
ージ（但し、当該文書中に存在するものとする）
を探し出すに必要なインデツクス・エントリを保
持すべき特定のリーフ・ノードを参照する。

一般にスクローリングと呼ばれるような文書の
順次的な表示又は訂正を容易にするために、リー
フ・ノード・チエーンが設けられている。これに
よれば、表示点又は訂正点が適切なリーフ・ノー
ドのインデツクス構成要素の終りで参照されるレ
コードに到達する場合は、当該文書のルート・ノ
ードを参照することなく次位（又は前位）のリー
フ・ノードを探し出すことができる。リーフ・ノ
ードＡ（２０２）のリーフ・ノード・チエーン２
０６は２つの論理セクタ番号（LSN）、すなわち
前位リーフ・LSN２１６及び次位リーフ・LSN
２１８を含む。第５Ａ図の例では、リーフ・ノー
ドＡ（２０２）は当該文書の第１ページに対する
インデツクス・エントリを保持するので、その前
位リーフは存在しない。従つて、その前位リー
フ・LSN２１６は、SAMルーチン４４によつて
無効な論理セクタ番号として認識されるような値
にセツトされる。リーフ・ノードＡ（２０２）の
次位リーフ・LSN２１８は、リーフ・ノードＢ
（２０４）の論理セクタ番号を保持する。同様に、
リーフ・ノードＢ（２０４）のリーフ・ノード・
チエーン２１０にある前位リーフ・LSN２２０
はリーフ・ノードＡ（２０２）の論理セクタ番号
保持する。また、リーフ・ノードＢ（２０４）は
当該文書の最終ページに対するインデツクス・エ
ントリを保持しているので、次位リーフ・LSN
２２２は無効な論理セクタ番号を保持する。

ルート・ノード２００は、当該データ・セツト
のインデツクスの開始点である。従つて、ルー
ト／中間インデツクス構成要素２１６のインデツ
クス・エントリは、記憶ボリユームに置かれたリ
ーフ・ノードＡ（２０２）及びリーフ・ノードＢ
（２０４）を探し出すことを可能にする。リー
フ・ノードＡ（２０２）では、ページＮ１・イン
デツクス・エントリ１８２はリーフ・ノードＡ
（２０２）によつて参照される最終ページを参照
する。このことは、ページＮ１キー１８６（第４
Ｂ図）がインデツクス構成要素２０８中で最大の
キーであることを意味する。従つて、これはリー
フ・ノードＡ（２０２）のハイ・キーと呼ばれる。
同様に、リーフ・ノードＢ（２０４）のページ
Ｚ・インデツクス・エントリ２１４に置かれたキ
ーはそのインデツクス構成要素２１２中のいずれ
のキーよりも大きいので、このページＺ・キーが
リーフ・ノードＢ（２０４）のハイ・キーとなる。

第５Ｂ図は、ルート・ノード２００のルート／
中間インデツクス構成要素２１６を一層詳細に示
す。第５Ａ図の２つのリーフ・ノードが存在する
から、ルート／中間インデツクス構成要素２１６
にも２つのインデツクス・エントリが存在する。
リーフ・ノードＡのインデツクス・エントリ２２
４はページＮ１・キー１８６及びリーフ・ノード
ＡのLSN２２６を含み、後者はリーフ・ノード
Ａ（２０２）の論理セクタ番号を保持する。同様
に、リーフ・ノードＢのインデツクス・エントリ
２３２には、ページＺ・キー２２８及びリーフ・
ノードＢのLSN２３０が含まれる。

ここで、リーフ・ノードＡ及びＢのインデツク
ス・エントリ２２４及び２３２は第３図のレコー
ド記述子とは異なりり、レコードに関する情報や
インデツクス・ノードの長さを保持していない、
ということを注意すべきである。インデツクス・
ノードは常に単一の論理セクタであり、そしてル
ート／中間インデツクス構成要素２１６は常にイ
ンデツクス・ノード（第５Ａ図のリーフ・ノー
ド）を参照するから、これらのインデツクス・ノ
ードの長さは常に同じであり、従つて前述のよう
な情報をインデツクス・エントリから省略するこ
とができる。

所与のリーフ・ノードでは、既存のインデツク
ス・エントリへ新しいページ又はレコードのイン
デツクス・エントリを挿入したり又は追加するこ
とが頻繁に起こる。従つて、新しいコード又はペ
ージを追加する場には、既存のリーフ・ノードの
スペースが不足することがある。このようにスペ
ースが不足するリーフ・ノードは、分割と呼ばれ
るSAM動作によつて２つのリーフ・ノードと置
換されることになる。ルート・ノードのインデツ
クス構成要素は、分割前にはリーフ・ノードごと
に１つのインデツクス・エントリ（たとえば、リ
ーフ・ノードＢのインデツクス・エントリ２３
２）を保持する。分割後には、このインデツク
ス・エントリは２つのインデツクス・エントリ、
すなわち新しい２つのリーフ・ノードの各々ごと
に１つのインデツクス・エントリによつて置換さ
れねばならない。この動作は１つのルート・ノー
ドを１つのルート・ノードと２つのリーフ・ノー
ドへ分割する動作の単なる拡張にすぎないので、
以下ではその説明を省略する。

操作員が非常に大きな文書を作成するためにグ
ラフイツク文字及び指令を記入すると、相当量の
リーフ・ノードが追加されることがあるが、この
ような場合にはルート・ノードのインデツクス構
成要素２１６におけるスペースが足りなくなつ
て、他のリーフ・ノードのインデツクス・エント
リを収容しきれなくなる。従つて、この時点でル
ート・ノード２００を再び分割しなければならな
い。なぜなら、ルート・ノード２００はリーフ・
ノードを参照しているので、新しいリーフ・ノー
ドを作成することができないからである。（リー
フ・ノードはそのリーフ・ノード・チエーンの外
部にある他のリーフ・ノードを参照しない）。そ
のかわりに、中間ノードと呼ばれる他のタイプの
ノードが作成されるのである。

第６図を参照するに、図示されたルート・ノー
ド２４０は第５Ａ図のルート・ノード２００に置
換わつたものであり、これは第５Ｂ図のものと同
じ構造のルート／中間インデツクス構成要素２４
２を含んでいる。しかしながら、このインデツク
ス構成要素２４２のインデツクス・エントリはリ
ーフ・ノードの論理セクタ番号を維持するかわり
に、中間ノードＩ（２４４）及び中間ノードＪ（２
４６）の論理セクタ番号を保持している。中間ノ
ードＩ（２４４）にはインデツクス構成要素２４
８があり、これはリーフ・ノードＢ（２５６）リ
ーフ・ノードＣ（２５８）及びリーフ・ノード
（２６０）を参照するためのリーフ・インデツク
ス・エントリ２５０，２５２及び２５４をそれぞ
れ含んでいる。かくて、第６図は３レベルのイン
デツクス・トリーを例示しており、そこではルー
ト・ノード２４０のノード・レベル値は２であ
り、中間ノードＩ（２４４）及びＪ（２４６）のノ
ード・レベル値は１であり、そしてすべてのリー
フ・ノードのノード・レベル値は依然として０で
ある。インデツクス構成要素２４８中のインデツ
クス・エントリは、第５Ｂ図に示したリーフ・ノ
ードＡのインデツクス・エントリ２２４と同じ構
造を有する。中間ノードＪ（２４６）中のインデ
ツクス構成要素２６２は、インデツクス構成要素
２４８と同様の構造を有する。

第６図の隣接するリーフ・ノード間の接続２６
４は、第５Ａ図の２０６及び２１０の如きリー
フ・ノード・チエーンを表わす。

従つて、第６図に示された一般的なインデツク
ス構造によれば、SAMルーチン４４は２つの異
なる方法で、すなわち文書の表示又は訂正方法に
応じて、所望のページ又はレコードを探し出すこ
とができる。たとえば、リーフ・ノードＤ（２６
０）で参照される或るページの最初のレコードを
探し出すために、SAMルーチン４４はDASD２
２からルート・ノード２４０を取出し且つそのイ
ンデツクス構成要素２４２を探索することによ
り、中間ノードＩ（２４４）が該当する中間ノー
ドであることを決定する。次いで、中間ノードＩ
（２４４）が記憶媒体から取出され、そしてリー
フ・ノードＤ（２６０）が前述と同様に適切なリ
ーフ・ノードとして選択される。記憶媒体からリ
ーフ・ノードＤ（２６０）を取出した後、所望の
ページのキーを探し出すためにリーフ・ノードＤ
（２６０）のインデツクス構成要素が探索される。

一方、もし操作員がリーフ・ノードＣ（２５８）
で参照される最終レコードの終りにあつて、テキ
ストの次のレコード（リーフ・ノードＤで参照さ
れる）へのスクロールを望んでいれば、記憶媒体
上のリーフ・ノードＤ（２６０）を直接探し出す
ためにリーフ・ノードＣ（２５８）中のリーフ・
ノード・チエーンを使用することができる。すな
わち、この場合にはルート・ノード及び中間ノー
ドを再び取出したり、探索することは全く必要な
いのである。

第４Ａ図ないし第６図に例示されたインデツク
ス構造は、ボリユームを複数のインデツクスの階
層として構成することによつて、単一のデータ・
セツトからボリユーム全体まで一般化することが
できる。第７図は、ボリユーム・インデツクスを
ブロツク図の形式で例示する。この例では、記憶
ボリユームは３つのデータ・セツトを有し、その
うち２つのデータ・セツトは同じタイプ（たとえ
ば、テキスト文書）のものであり、残りのデー
タ・セツトはそれとは異なるタイプのものであ
る。

媒体制御レコード２８０は各記憶ボリユームご
とに設けられ、ボリユーム・ラベル（ボリユーム
名）の如き対応ボリユームの全体に関する情報を
保持する。媒体制御レコード２８０には、ボリユ
ーム上のデータに関する情報を与えるために、ヘ
ツダ１フイールド２８１が設けられる。特に、ヘ
ツダ１フイールド２８１は（媒体制御レコード２
８０かアンカー２８４への矢印によつて示される
ような）アンカー位置ポインタ２８２を含み、こ
れはボリユーム上のアンカー２８４の位置を示
す。

アンカー２８４は第１レベルのボリユーム・イ
ンデツクス情報である。アンカー２８４の機能
は、データ処理システムのDASD記憶ボリユーム
に置かれたボリユーム目録に似ている。ワード・
プロセシング・システム１０では、アンカー２８
４は１つのデータ・セツト・インデツクスとして
構成される。特に、アンカーのフオーマツトはル
ート／リーフ・ノードのフオーマツト（第４Ａ図
参照）と同じである。しかしながら、第４Ａ図の
ように文書のレコード及びページを参照するかわ
りに、アンカー２８４はボリユーム情報又は他の
データ・セツトを参照する。他のインデツクス・
ノードと同様に、アンカー２８４は下位レベルの
データを参照するためのインデツクス構成要素２
８５を含んでいる。

アンカー２８４のインデツクス構成要素２８５
は、第４Ｂ図に示したインデツクス構成要素１７
３と同様のフオーマツトを有する。アンカー２８
４では、そのインデツクス・エントリのキーは
（ページＮ１・キー１７８と同様に）データ・セ
ツトタイプから構成される。かくて、アンカー２
８４には、記憶ボリユーム上の一意的なデータ・
セツト・タイプごとに１つのインデツクス・エン
トリが存在する。

媒体割振マツプ２８６は、記憶媒体上の各セク
タの割振ステータスを示す。ワード・プロセシン
グ・システム１０では、媒体割振マツプ２８６は
媒体上の各セクタごとに１つの指示を保持する。
この指示は、或るデータ・セツトへ割振るために
対応するセクタが利用できるか否かを示す。既存
のインデツクス・ノード及びデータ・セツト・レ
コードに対するこれらの指示は、対応するセクタ
が既に割振られており、従つて利用できないこと
を示す。この種の媒体割振技法は当該技術分野で
は周知であると考えられるので、ワード・プロセ
シング・システム１０の媒体割振マツプをを管理
するために実際に使用される技法については、そ
の説明を省略する。アンカー・インデツクス構成
要素２８５中の媒体割振マツプ２８６に対するイ
ンデツクス・エントリはそのキーとして該媒体割
振マツプ２８６へ割振られた一意的なデータ・セ
ツト・タイプを有し、そして（たとえば第４Ｂ図
のレコード記述子１７９の如き）レコード記述子
として論理セクタ番号２８７及びボリユーム上の
媒体割振マツプ２８６の長さを有する。

第７図の例では、データ・セツトＡ（２８８）
がそのタイプを有するボリユーム上の唯１つのデ
ータ・セツトであると仮定する。従つて、アンカ
ー・インデツクス構成要素２８５中のインデツク
ス・エントリは、データ・セツトＡ（２８８）の
データ・セツト・タイプから構成されたキーと、
データ・セツトＡ（２８８）のルート・ノードの
論理セクタ番号を示す論理セクタ番号２８９から
成る。

しかしながら、データ・セツトＢ（２８９）及
びデータ・セツトＣ（２９０）は、同じデータ・
セツト・タイプを有するものと仮定する。或るイ
ンデツクス構成要素中のキーは一意的でなければ
ならず、そしてデータ・セツトＢ（２８９）及び
データ・セツトＣ（２９０）のデータ・セツト・
タイプから構成されるキーは同等であるから、こ
の要件のために他のレベルのインデツクスが導か
れる。デイレクトリ２９１は下位レベルのデー
タ・セツトに対するデータ・セツト・インデツク
スである。デイレクトリ２９１のデータ・セツ
ト・タイプは、該デイレクトリが参照するすべて
のデータ・セツト・タイプと同じである。従つ
て、アンカー・インデツクス構成要素２８５中の
インデツクス・エントリはデイレクトリ２９１の
データ・セツト・タイプから導かれたキーを使用
し、そして論理セクタ番号を介してデイレクト
リ・ルート・ノードを参照する。

デイレクトリ・インデツクス構成要素２９３は
データ・セツトのルート・ノードを参照する。イ
ンデツクス構成要素２９３中のインデツクス・エ
ントリに対するキーは、（第４Ａ図における各デ
ータ・セツトのルート・ノードのデータ・セツ
ト・プロフイル１７２に保持される如き）デー
タ・セツト名である。ワード・プロセシング・シ
ステム１０では、単一の記憶媒体上のデータ・セ
ツトは一意的なデータ・セツト名を有さなければ
ならない。従つて、デイレクトリ・インデツクス
構成要素２９３中のキーは一意的である。

他のすべてのデータ・セツト・インデツクスと
同様に、データ・セツトの数が増加してこれと同
じデータ・セツト・タイプのすべてのデータ・セ
ツトに対するインデツクス・エントリが単一のル
ート／リーフ・ノードに収まりきらなくなつた場
合には、デイレクトリ２９１を複数のレベルへ拡
張することができる。しかしながら、ワード・プ
ロセシング・システム１０における一意的なデー
タ・セツト・タイプの数は限られているので、ル
ート／リーフ・ノードより大きくなるようにアン
カー２８４を拡張する必要はない。

第８図には、第１図にしたSAM内部制御ブロ
ツク６２の一部が詳細に図示されている。ユニツ
ト制御ブロツク／記憶（以下UCSと略す）３０
０はデバイス・ステータス、動作ステータス及び
制御情報を保持するとともに、データ・セツト及
びボリユーム・インデツクスをアクセス及び更新
するためのバツフア領域を与える。ここで、ボリ
ユームとは、ワード・プロセシング・システム１
０へ接続された単一のデイスケツト又はハード・
デイスクの如きDASD２２を意味する。ワード・
プロセシング・システム１０の処理に利用可能な
各ボリユームはそれ自体のUCS３００を有する。

デバイス・ステータス領域３０２は、DASD２
２に対する実際のＩ／Ｏ動作を制御するために、
SAMルーチン４４によつて使用されるデータ及
び制御情報を保持する。また、この領域３０２
は、キーストローク・サービス・ルーチン３４か
らの要求を処理している間にアクセスすべき利用
可能なボリユームを決定するために、SAMルー
チン４４４によつて使用される。

ボリユームのデータ・セツト・インデツクス・
バツフア３０４は、アンカーと呼ばれる第１レベ
ルのボリユーム・インデツクスを保持する。この
バツフアはDASD２２中のボリユームに対するア
ンカー２８４（第７図）を保持する。アンカーは
メモリ２６に維持されるが、これはボリユーム上
で或るデータ・セツトを探し出さねばならない場
合にDASD２２からの入力動作を排除するためで
ある。ボリユーム・インデツクス中のキーがデー
タ・セツトのタイプ（たとえば、テキスト文書）
及びデータ・セツト名（第４Ａ図の１７６を参
照）から成る場合には、ボリユーム上の或るデー
タ・セツトを探し出す動作はデータ・セツト中の
或るページを探し出す動作に非常に似ている。

参照番号３０６，３０８及び３１０によつて識
別されるインデツクス・ノード・バツフア１ない
し３はバルフア領域であつて、DASD２２との転
送が行われている間にデータ・セツト・インデツ
クス・ノード又はボリユーム・インデツクス・ノ
ードを処理するために使用される。インデツク
ス・ノード・バツフア１ないし３の各々は、１つ
のインデツクス・ノードを保持することができ
る。１以上のインデツクス・ノード・バツフアが
設けられているのは、インデツクスの探索及び分
割動作を容易するためである。

媒体割振マツプ・バツフア３１２は、記憶ボリ
ユームに対する媒体割振マツプのスペースを与え
る。このバツフアは、DASD２２中の媒体割振マ
ツプ２８６（第７図参照）のコピーを保持する。

UCS３００の残りの領域は内部ステータス及
び制御情報を保持するとともに、中間的な種々の
計算結果等を保持するために使用される。この種
の動作は本発明の要旨に関係ないので、以下では
その説明を省略する。

第８図には、第１図のSAMインタフエース制
御ブロツク５０が詳細に示されている。SAMル
ーチン４４によつて与えられる動作のうち本発明
に関係する動作は、アクセスに際しデータ・セツ
トをオープンする事、DASD２２からメモリ２６
へ１以上のレコードを読取る事、そしてメモリ２
６からDASD２２へ１以上のレコードを書込むこ
とである。

キーストローク・サービス・ルーチン３４によ
つて要求されるSAMルーチン４４の各サービス
毎に、１つの記憶事象制御ブロツク（以下SECB
と略す）３３０が必要である。実際にSECB３０
０に割振られるメモリ２６中の領域は、要求を行
うキーストローク・サービス・ルーチン３４によ
つて決定される。第１図にチヤネル４６は、この
ようにして割振られたSECB３３０の領域を
SAMルーチン４４へ渡すために使用される。

SECB３３０では、要求された特定の動作を開
始するためにSAMルーチン４４に必要なすべて
の情報を見出すことができる。指令及びオプシヨ
ン領域３３２は要求された主要な動作指令（たと
えば、ボリユーム回復）を指示するとともに、当
該要求を修正しうる指令オプシヨンを指示する。
指令及びオプシヨン指示領域３３２は、特定の指
令を処理すべきSAMサービス・ルーチンを生ず
ために使用される。

回復バツフア位置領域３０４は、メモリ２６に
おけるグローバル回復バツフア３４０の位置を保
持する。SECB３３０と同様に、グローバル回復
バツフア３４０へ実際に割振られるメモリ２６中
の領域はキーストローク・サービス・ルーチン３
４によつて選択される。グローバル回復バツフア
３４０は、エラー検出後にボリユーム及びデー
タ・セツト・インデツクスを検査又は再構成する
ことが必要な場合に、SAMルーチン４４によつ
て使用される。

記憶ボリユーム上にあるデータ・セツト及びデ
ータ・レコードの保護及び復には、２つの段階が
ある。すなわち、媒体エラーに起因するデータの
損失を防止するために行われる予防段階と、可能
なエラーが検出された場合に行われるデータ・セ
ツト及びボリユーム・インデツクスのスキヤン段
階とがある。

媒体エラーが検出されるのは、データの取出時
にこのデータがワード・プロセシング・システム
によつて有効として認識されないような場合であ
る。ワード・プロセツシング・システム１０にお
ける媒体エラーには、DASD２２に共通のエラー
があり、これらのエラーは媒体表面の汚れ、媒体
の磨滅、等が原因で生ずることがある。

ワード・プロセシング・システム１０では、媒
体エラーに起因するデータの致命的な損失を防止
するために、ボリユーム上にある重要（クリチカ
ル）データを重複して記録するようにしている。
これは冗長又は重複記録として知られている。も
ちろんあらゆるデータの２つのコピーを記憶ボリ
ユームに記録することも可能であるが、このアプ
ローチは記憶ボリユームの実効容量を実際の容量
の半分に減少させるという欠点を有する。従つ
て、ワード・プロセシング・システム１０では、
記録される全情報のうちのサブセツトを重要情報
として指定し、これを冗長記録することによつて
保護するようにしている。ここで重要情報とは、
再び作成したり又はワード・プロセシング・シス
テム１０へ再び記入するのに操作員が多大の労力
を必要とする、そのような情報をいう。

ボリユームの実効容量を減少させないようにす
るにはすべての情報を重要情報として指定するこ
とはできないので、ワード・プロセシング・シス
テム１０で適用される最初の規則は、データ・セ
ツト中のデータ・レコードが重要情報ではない、
とするものである。個別的なデータ・レコードが
失われたとしても、これを回復するにはキーボー
ド１２を介してデータ再び記入するだけで済むか
らである。従つて、データ・セツト・インデツク
ス・ノード又はボリユーム・インデツクス・ノー
ドだけが重要情報であるとみなされる。

第７図を参照するに、もし媒体制御レコード２
８０を正しく取出すことができなければ、アンカ
ー及びすべてのデータ・セツトを探し出すことが
できない。従つて、媒体制御レコード２８０は重
要情報あるとみなされる。ワード・プロセシン
グ・システム１０では、媒体制御レコード２８０
は常に論理セクタ番号０及び論理セクタ番号17に
記録される。これらの論理セクタ番号はデバイ
ス・タイプ（デイスケツト又はハード・デイスク
２２）とは無関係である。媒体制御レコード２８
０の２つのコピーの内容は同じである。

媒体制御レコード２８０と同様に、アンカー２
８４も重要情報であるとみなされるる。なぜな
ら、アンカー２８４を読取ることができなけれ
ば、いかなるデータ・セツトをも探し出すことが
できないからである。従つて、各記憶ボリユーム
にはアンカー２８４の２つのコピーが記憶され
る。アンカー２８４の２つのコピーの内容は同じ
である。

媒体制御レコード２８０を読取る前に、ワー
ド・プロセシング・システム１０はこの媒体制御
レコード２８０の１次及び２次コピーの位置（論
理セクタ番号）を知つていなければならない。媒
体制御レコード２８０はアンカーLSN２８２を
保持しているので、このアンカーを記憶ボリユー
ム上の欠陥がない任意の論理セクタに記憶するこ
とができ、また元の論理セクタに更新されたコピ
ーを正しく記憶することができなければ、そこか
ら移動することもできる。このような場合は、ア
ンカーの最終位置を反映するように媒体制御レコ
ードを変更することだけが必要である。

システム性能を改良するためには、冗長的に記
録される情報の両コピーを互いに物理的に接近し
てボリユーム上に置くことにより、DASD２２の
読取り／書込みヘツドがこれらの間を移動するに
要する時間を最小にすることが望ましい。一方、
単一の欠陥又は障害によりこれらの両コピーに対
するアクセスが妨げられないようにするために
は、これらのコピーを互いに離れて配置すること
が望ましい。さらに、これらのフアクタ（性能、
リスクの減少）の相対重要度は、ボリユームの内
容に応じて、ボリユームごとに異なる、というこ
とがある。

媒体制御レコード２８０はまれにしかアクセス
されないので、かかる柔軟性はワード・プロセシ
ング・システム１０ではさほど重要ではない。従
つて、システム論理が複雑になることを避けるた
めに、本発明の実施態様ではすべての記憶ボリユ
ームについて一定の位置が選択された。アンカー
の第２コピーの位置を柔軟に設定することができ
るように、媒体制御レコード２８０へ第２位置領
域を追加し、これにより記憶ボリユームにおける
アンカー２８４の第コピーの位置を規定するよう
にした。

第１０Ａ図には、第７図の媒体制御レコード２
８０およびアンカー２８４に夫々第２コピーを設
けたものが示されている。媒体制御レコードの１
次コピー３６０は論理セクタ０に記録され、その
２次コピー３６２は論理セクタ１７に記録され
る。１次コピー・ヘツダ１・フイールド３６４及
び２次コピー・ヘツダ１・フイールド３６６は、
両者共に１次アンカー３６８の媒体位置を保持す
る。媒体制御レコードの各コピーには、２次アン
カー・ポインタ（以下BUAPと略す）を呼ばれ
るフイールドが追加される。これらのフイール
ド、即ち１次コピーBUAP３７２及び２次コピ
ーBUAP３７４は、アンカー３７０の２次コピ
ーの位置を保持する。

第４図ないし第７図を参照するに、もし或るデ
ータ・セツトのルート・ノードをワード・プロセ
シング・システム１０によつて正しく取出すこと
ができなければ、このデータ・セツト中のデー
タ・レコードを記憶ボリユームで探し出すことは
できず、かくてこのデータは操作員からすれば失
われることになる。従つて、すべてのデータ・セ
ト・ノードは重要であると考えられるので、記憶
ボリユームに冗長的に記録されねばならない。こ
のことは特にデイレクトリのルート・ノードにあ
てはまる。というのは、デイレクトリ・ルート・
ノードをアクセスすることができなければ、この
デイレクトリによつて参照されるすべてのデー
タ・セツト（特定のデータ・セツト・タイプを有
するすべてのデータ・セツト）はワード・プロセ
シング・システム１０及び操作員に対し失われる
ことになるからである。

たとえば、第７図のデイレクトリ２９１につい
て説明すると、もし同じタイプを有するデータ・
セツトが相当あつてデイレクトリ２９１が（第５
Ａ図又は第６図に示すように）複数レベルになれ
ば、デイレクトリ・インデツクスにおけるリー
フ・ノードの消失は幾つかのデータ・セツトのル
ート・ノードをもはや探し出すことができないこ
とを意味する。かくて、ワード・プロセシング・
システム１０では、デイレクトリのリーフ・ノー
ドもまた重要なインデツクス・ノードとみなされ
る。

第４Ｂ図及び第５Ｂ図に関連する前述の説明、
特にレコード記述子１７９及びリーフ・ノード
LSN２２６の説明を参照するに、下位レベル
（データ・レコード又はインデツクス・ノード）
の位置は論理セクタ番号によつて与えられる。前
述の重要ノードのうち或るノードの１次コピーが
エラーなしで取出される場合は、２次コピーが探
し出されねばならない。或るデータ・セツト・イ
ンデツクスを探索する動作の性能は当該データ・
セツト中のレベルの数に関係しており、そして該
レベルの数は当該データ・セツト中のデータ・レ
コードの数及び個別的なインデツクス・エントリ
のサイズによつて決定される。もし重要セクタを
参照するようなインデツクス・エントリの各々に
余分の論理セクタ番号が追加されるならば、この
ことは所与のレベル数を有するデータ・セツト中
に一層数の少ないレコードを記憶しうることを意
味する。これらのインデツクス・エントリは、既
に１次コピーの論理セクタ番号を保持する。ワー
ド・プロセシング・システム１０では、２次コピ
ーは１次コピーから一定数の論理セクタだけ離れ
て置かれるように規定されている。言いかえれ
ば、２次コピーの論理セクタ番号と１次コピーの
論理セクタ番号との間の差は、この記憶ボリユー
ムについては一定である。

第１０Ａ図を参照するに、アンカーのインデツ
クス構成要素３７６にはシヤドウ・オフセツト・
フイールド３７８が設けられている。シヤドウ・
オフセツト３７８は、１次コピーの論理セクタ番
号と２次コピーの論理セクタ番号との間の差を示
す。かくて、もしボリユーム・アンカーをアクセ
スすることできれば、当該ボリユームに対するシ
ヤドウ・オフセツトを１次コピーの論理セクタ番
号と加算することによつて重要なインデツクス・
ノードの２次コピーの論理セクタ番号を計算する
ことができる。こうすることにより、ワード・プ
ロセシング・システム１０は、種々のボリユーム
に対するボリユーム内容に基づいて（性能及びリ
スクの減少に基づいて）、最良のオフセツトを選
択することができる。メモリ２６に設けられた
UCS３００のボリユーム・データ・セツト・イ
ンデツクス・バツフア３０４ではアンカーのコピ
ーが利用可能であるから、SAMルーチン４４は
必要に応じて重要情報の２次コピーを常に探し出
すことができる。

前述のように、すべてのルート・ノードは重要
なセクタであるとみなされ、冗長的に記録され
る。また、デイレクトリのリーフ・ノードも重要
なセクタとみなされる。他のリーフ・ノードは、
データ・セツトのタイプに応じて、重要であると
みなされる。たとえば、テキスト文書のリーフ・
ノードは文書中の多くのテキスト・ページを参照
するので、かかるリーフ・ノードを重要であると
みなすことができる。一方、ワード・プロセシン
グ・システム１０のプログラム・デイスケツトに
置かれたプログラム・データ・セツトのリーフ・
ノードは重要であるとはみなされない。というの
は、任意のプログラム・データの消失はそのプロ
グラム・デイスケツトを無効にし、そして他のプ
ログラム・デイスケツトをその販売元から簡単に
入手することができるからである。かくて、当該
データ・セツトの内容に応じて、或るリーフ・ノ
ードは重要であるとみなされ、他のリーフ・ノー
ドは重要であるとはみなされない。

第１０Ｂ図は、第４Ｂ図に示したルート・ノー
ド１７０のデータ・セツト・プロフイル１７２を
一層詳細に示す。データ・セツト・プロフイル３
９０には、４つの構成要素、すなわちデータ及び
インデツクス属性３９２、データ・セツト名３９
３、データ・セツト・コメント３９４及びデー
タ・セツト・ステータス３９５がある。データ及
びインデツクス属性３９２は、データ・セツト・
インデツクス及び当該インデツクス・ノードのイ
ンデツクス構成要素におけるインデツクス・エン
トリの構造に関する完全な記述を、SAMルーチ
ン４４のために含んでいる。特に、リーフ・シヤ
ドウ指示は、当該データ・セツトに対するリー
フ・ノードが冗長的に記録されるべきか否かを指
定する。従つて、リーフ・ノードが重要であるか
否かは特定のデータ・セツトごとに指定すること
ができる。ワード・プロセシング・システム１０
では、キーストローク・サービス・ルーチン３４
は一般に同じデータ・タツト・タイプを有するデ
ータ・セツトを同等に扱う。かくて、すべてのテ
キスト文書はそれらのリーフ・ノードをシヤドウ
化、すなわち２重化される。SAMルーチン４４
では、すべてのデータ・セツトのルート・ノード
はリーフ・ノードをシヤドウ化すべきか否かを指
定する。

第１１Ａ図には、インデツクス・ノード読取り
に関係するる本発明の論理的動作が流れ図の形式
で示されている。この手順はインデツクス・ノー
ド読取サービス・ルーチン・ステツプ４００で開
始する。ステツプ４０２では、このインデツク
ス・ノード読取手順を遂行せしめるような他の手
順によつて供給される論理セクタ番号を使用し
て、当該インデツクス・ノードの１次コピーが読
取られる。もしステツプ４０３のテストによりこ
のインデツクス・ノードがDASD２２から正常に
取出されたことがわかれば、インデツクス・ノー
ド読取完了がステツプ４０５の戻りコードを介し
て通知され、かくてこの手順は次のインデツク
ス・ノード読取りが必要となるまでステツプ４０
７で終了する。戻りコードは当該技術分野では周
知であるばかりか、本発明の要旨とも関係がない
ので、以下ではその説明を省略する。

もしステツプ４０３でエラーが検出されたなら
ば、予測されたインデツクス・ノードのタイプが
ステツプ４０９で調べられる。もしルート・ノー
ドが予測されたならば、このルート・ノードは最
初に冗長的に記録されたので、ステツプ４１１で
ボリユーム・シヤドウ・オフセツトを１次コピー
の論理セクタ番号へ加算することによつて２次コ
ピーの論理セクタ番号が計算され、続いてステツ
プ４１３でこの２次コピーが読取られる。もしス
テツプ４１４で２次コピーの取出エラーが検出さ
れなければ、読取完了がステツプ４０５の戻りコ
ードを介して通知され、そしてこの手順は前述の
ようにステツプ４０７で終了する。もしステツプ
４１４でエラーが検出されたならば、ステツプ４
１６の戻りコードを介して読取エラーが通知さ
れ、そしてこの手順は前述のようにステツプ４０
７で終了する。

もしステツプ４０９で予測されたインデツク
ス・ノードがルート・ノードでないことがわかれ
ば、リーフ・ノードが予測されたか否かを決定す
るために、この予測ノードはステツプ４１８で調
べられる。もし予測されたインデツクス・ノード
がリーフ・ノードでなければ（中間ノードが予測
された場合）、これは１次コピーがステツプ４０
２で正常に読取られなかつたことを意味するか
ら、前述のようにステツプ４１６を介して読取エ
ラーが通知される。これと同じことは、予測され
たリーフ・ノードが（第１０Ｂ図のデータ・セツ
ト・プロフイル３９０におけるリーフ・シヤドウ
指示３９７に従つて）２重化されていないことが
ステツプ４２０で判明した場合にもあてはまる。
予測されたリーフ・ノードが２重化されているこ
とがステツプ４２０でわかれば、これは予測され
たルート・ノードと同様にステツプ４１１及び４
１３を通して処理される。

第１１Ｂ図には、インデツクス・ノード書込み
に関係する本発明の論理的動作が流れ図の形式で
示されている。この手順はインデツクス・ノード
書込サービス・ルーチン・ステツプ４２５で開始
する。ステツプ４２７では、このインデツクス・
ノード書込手順を行わしめる他の手順によつて供
給された論理セクタ番号を使用して、当該インデ
ツクス・ノードの１次コピーが書込まれる。もし
ステツプ４２９のテストにより当該インデツク
ス・ノードがルート・ノードであることがわかる
か、又はステツプ４３１及び４３３のテストによ
り当該インデツクス・ノードがリーフ・ノードで
あり且つこのリーフ・ノードが２重化されるべき
ことがわかれば、ステツプ４３５ではボリユー
ム・シヤドウ・オフセツトを１次コピーの論理セ
クタ番号へ加算することによつて２次コピーの論
理セクタ番号が計算され、続くステツプ４３６で
はこの２次コピーが書込まれる。次いで、この手
順は次のインデツクス・ノード書込要求が受取ら
れるまでステツプ４３８で終了する。

もしステツプ４２９及び４３１で当該インデツ
クス・ノードがルート・ノードではなくリーフ・
ノードであることがわかるか、又はステツプ４３
３でリーフ・ノードを現データ・セツトにおいて
２重化すべきでないことがわかれば、ステツプ４
２７では１次コピーだけが書込まれたことになる
ので、この手順は前述のようにステツプ４３８で
終了する。

第１０Ａ図〜第１０Ｂ図に示した構造及び第１
１Ａ図〜第１１Ｂ図に示した手順は、記憶ボリユ
ームの記憶容量を若干余分に利用するだけで、操
作員に対する相当量のデータが消失するリスクを
減少させるとともに、記憶媒体上の任意の物理セ
クタにおけるエラーのない動作に完全に依存する
ことを排除するために、ワード・プロセシング・
システム１０がどのように柔軟に利用されるか、
ということを示している。

ワード・プロセシング・システム１０の通常の
動作中、SAMルーチン４４はデータ・セツト・
インデツクス構造が完全で且つ正しいことを仮定
する。もし記憶媒体エーが存在せず、しかも異常
なシステム終了が存在しなければ、この仮定は
DASD２２上で利用可能な任意のデータ・セツト
に対す適正なアクセスを保証するに十分である。

しかしながら、DASD２２で使用される記憶媒
体については、記憶ボリユームに正常に記憶され
たデータを（媒体エラーのために）アクセスでき
ないことがある。第６図を参照するに、リーフ・
ノードＣ（２５８）のインデツクス構成要素中に
あるインデツクス・エントリによつて参照される
ようなデータ・レコードをアクセスしなければな
らない場合には、一般に、記憶ボリユーム上のデ
ータ・レコードを探し出してアクセスする前に、
ルート・ノードをスキヤンすること、中間ノード
Ｉ（２４４）を探し出し、取出し且つスキヤンす
ること、そしてリーフ・ノードＣ（２５８）を探
し出し、取出し且つスキヤンすることが必要であ
る。

第１０図及び第１１図に示した構造及び手順
は、媒体エラーのためにルート・ノード又はリー
フ・ノードをアクセスすることができないような
状況を著しく減少させる。しかしながら、中間ノ
ードは２重化によつては保護されない。ここで注
意すべきは、もし任意のリーフ・ノードを探し出
すことができるならば、他の任意のリーフ・ノー
ドも第６図のリーフ・ノード・チエーン２６４を
介して探し出すことができる、という点である。
もし中間ノードＩ（２４４）の取出中に読取エラ
ーが検出されたならば、中間ノードＪ（２４６）
を取出し、次いでリーフ・ノードＦ（２６６）を
取出し、さらにリーフ・ノードＣ（２５８）が探
し出されるまで、第５Ａ図に示したリーフ・ノー
ド・チエン２０６の前位リーフLSN２１６を介
して前位リーフ・ノードを順次に探し出すことが
できる。

このような代替的スキヤニングを達成するため
の一般的手順をSAMルーチン４４に追加すると、
通常の処理ルーチンが著しく複雑になる。また、
メモリ２６の記憶要件も著しく厳しくなる。とい
うのは、メモリ２６の全容量は制限されており、
従つてSAMルーチン４４のサイズ及び複雑さを
制限することが一層望ましいからである。

ワード・プロセシング・システム１０で採用さ
れた媒体エラー・アプローチの全容は、次のとお
りである。第１０Ｂ図を参照するに、各データ・
セツトのルート・ノードはデータ・セツト・プロ
フイル３９０を含んでおり、該プロフイルの１構
成要素はデータ・セツト・ステータス３９５であ
る。ワード・プロセシング・システム１０では、
データ・セツト・ステータスは３種類の状態（ク
ローズ、更新オープン、損傷）のうち１つをとり
うる。

当該技術分野におけDASDに対する殆んどの記
憶アクセス方式と同様に、キーストローク・サー
ビス・ルーチン３４は或るデータ・セツトのレコ
ードに対するアクセス要求を発する前に該デー
タ・セツトのオープン要求を記憶アクセス方式へ
与えなければならない。第１２Ａ図には、オープ
ン・ステータス検査に関係する本発明の論理的動
作が流れ図の形式で示されている。

この手順はオープン・ステータス検査サービ
ス・ルーチン・ステツプ４５０で開始する。ステ
ツプ４５１では、データ・セツト・ルートを読取
るためにインデツクス・ノード読取手順が行わ
れ、続くステツプ４５３では、データ・セツト・
プロフイル中のデータ・セツト・ステータスが探
し出される。もしステツプ４５４のテストにより
当該データ・セツトがクローズされていないこと
がわかれば、このデータ・セツトは正しいことが
保証される。従つて、このデータ・セツトの利用
不能性がステツプ４５８の戻りコードを介して通
知され、そしてこの手順は次のオープン・ステー
タス検査が要求されるまでステツプ４５８で終了
する。

もしステツプ４５４のテストにより当該デー
タ・セツトの現ステータスがアクセスを許容する
ものであることがわかれば、ステツプ４６０では
このアクセス要求のタイプがテストされる。もし
この要求が更新タイプ（データ・セツト・インデ
ツクス及び／又はレコードの追加、置換又は削
除）のものでなければ、このデータ・セツトの利
用可能性がステツプ４６２の戻りコードを介して
通知され、そしてこの手順は前述のようにステツ
プ４５８で終了する。一方、もしこの要求が更新
タイプのものであれば、ステツプ４６４で当該デ
ータ・セツトの現ステータスは更新オープンへ変
更され、そしてステツプ４６６ではインデツク
ス・ノード書込手順が行われる。

かくて、当該データセツトに未解決の問題又は
エラーが検出されなかつた場合のみ、オープンを
行うためのSAMルーチン４４がこのデータ・セ
ツトをアクセスすることができるのである。

或るデータ・セツトのオープンに成功した後、
全てのデータ・セツト・インデツクスが正しいこ
と及びすべてのインデツクス・ノードがエラーな
しで読取られうること（第１１Ａ図及び第１１Ｂ
図の手順により、通常の処理中に重要セクタの読
取りエラーを回復する場合を含む）を仮定して、
ワード・プロセシング・システム１０の通常の動
作が進行する。もし通常のSAMルーチン４４の
処理中に要求されたインデツクス・ノード又は論
理セクタが媒体エラーのために利用不能であるこ
とがわかれば、キーストローク・サービス・ルー
チン３４へエラー指示が戻される。キーストロー
ク・サービス・ルーチン３４がクローズ要求を発
した場合、このエラー指示は、プログラム状況が
解決されるまで後のアクセスから保護するため
に、記憶ボリユーム上に保存されねばならない。

第１２Ｂ図には、クローズ・ステータスに関係
する本発明の論理的動作が流れ図の形式で示され
ている。この手順はクローズ・ステータス・サー
ビス・ルーチン・ステツプ４７５で開始する。ス
テツプ４７６では、ルート・ノードにあるデー
タ・セツト・プロフイル３９０（第１０Ｂ図参
照）のデータ・セツト・ステータス３９５が探し
出される。もしステツプ４７８で当該データ・セ
ツトの前のエラー指示が検出されるならば、この
データ・セツト・ステータスはステツプ４８０で
損傷状態へセツトされ、そしてステツプ４８１で
はこのルート・ノードを記憶ボリユームへ書込む
ためにインデツクス・ノード書込手順が行なわれ
る。然る後、この手順は次のクローズ・ステータ
スが要求されるまでステツプ４８３で終了する。

もしステツプ４７８での前のエラーが検出され
なければ、ステツプ４８５は当該データ・セツト
の現ステータスが検査される。もし現アクセス・
タイプが更新でなければ、この手順は前述のよう
にステツプ４８３で終了する。もし現アクセス・
タイプが更新であれば、ステツプ４８７では当該
データ・セツトのステータスがクローズ状態へ変
更され、続くステツプ４８８では当該ルート・ノ
ードを記憶ボリユームへ書込むためにインデツク
ス・ノード書込手順が行われ、そして前述のよう
にステツプ４８３でこの手順が終了する。

第１２Ａ図及び第１２Ｂ図に関連して詳述した
これらの手術によれば、SAMルーチン４４は、
未解決の問題を有していそうなデータ・セツトへ
のアクセスを禁止し、通常の処理手順によつては
解決できない問題（媒体上に冗長的に記録された
重複コピーをアクセスすることによつても解決で
きないエラー）を検出するとともに、データ・セ
ツトで検出された未解決の問題の指示を記憶ボリ
ユームに保存する。

ワード・プロセシング・システム１０の通常の
動作環境では、予測不能な電源障害が不正なデー
タ・セツト・インデツクスに結びつくことがあ
る。もし或るインデツクスの更新中にワード・プ
ロセシング・システム１０へ供給される外部電源
が故障すれば、不正なデータ・セツト又はボリユ
ーム・インデツクス構造が生ずることがある。

第１３図には、第６図に示したものと類似する
データ・セツト・インデツクスの一部が例示され
ている。ルート・ノード５００は、中間ノードＩ
（５０２）を参照する処のインデツクス・エント
リを含む。中間ノードＩ（５０２）は、リーフ・
ノードＢ（５０４）、リーフ・ノードＣ（５０６）
及びリーフ・ノード（５０８）を参照する。リー
フ・ノード・チエーン５１０及び５１２は、第６
図のリーフ・ノード・チエーン２６４と同じ機能
を有する。

もしリーフ・ノードＣ（５０６）にインデツク
ス・エントリを記憶さるべきデータ・セツトへレ
コードが追加され、そしてリーフ・ノードＣ（５
０６）がこれらの追加レコードのインデツクス・
エントリを保持するに十分なスペースを有してい
なければ、リーフ・ノードＣ（５０６）に置換わ
るべき２つの新しいリーフ・ノード、すなわちリ
ーフ・ノードＣ１（５１４）及びリーフ・ノード
Ｃ２（５１６）を作成しなければならない。リー
フ・ノードＢ（５０４）及びリーフ・ノードＣ（５
０６）を結合するリーフ・ノード・チエーン５１
０は、リーフ・ノード・チエーン５１８と対応す
るようにリーフ・ノードＢ（５０４）で変更され
ねばならない。同様に、リーフ・ノードＤ（５０
８）は、リーフ・ノード・チエーン５１２をリー
フ・ノード・チエーン５２０で置換えるように変
更されねばならない。さらに、中間ノードＩ（５
０２）中のリーフＣ・インデツクス・エントリ５
２２は、２つの新しいインデツクス・エントリ、
すなわちリーフ・ノードＣ１（５１４）及びリー
フ・ノードＣ２（５１６）の各々ごとに１つの新
しいインデツクス・エントリで置換えられねばな
らない。

データ・レコードを記憶ボリユームへ書込んだ
り、インデツクス・ノードの読取り及び書込みを
行うプロセスは、瞬間的なものではない。従つ
て、インデツクス更新プロセスの任意のステツプ
で、ワード・プロセシング・システム１０の外部
電源が故障することがある。

たとえば、リーフ・ノードＣ１（５１４）及び
リーフ・ノードＣ２（５１６）が記憶ボリユーム
に記憶され且つリーフ・ノードＢ（５０４）及び
リーフ・ノードＤ（５０８）のリーフ・ノード・
チエーンが更新された場合、中間ノードＩ（５０
２）を変更して記憶ボリユームに書戻す前に、ワ
ード・プロセシング・システム１０の外部電源が
故障することがある。

この外部電源が復元される場合、ルート・ノー
ド５００のデータ・セツトに対応して記憶ボリユ
ームに置かれたデータ・セツト・インデツクスは
正しくない。リーフ・ノードＢ（５０４）及びリ
ーフ・ノードＤ（５０８）は、リーフ・ノードＣ
１（５１４）及びリーフ・ノードＣ２（５１６）
へそれぞれ連鎖される。中間ノードＩ（５０２）
はリーフ・ノードＣ（５０６）に対するインデツ
クス・エントリを保持するが、これはもはや当該
データ・セツト・インデツクスの一部ではない。
中間ノードＩ（５０２）は、当該データ・セツ
ト・インデツクスの一部であるべきリーフ・ノー
ドＣ１（５１４）及びリーフ・ノードＣ２（５１
６）に対するインデツクス・エントリを含んでい
ない。かくて、当該データ・セツトは未解決の問
題を含むことになる。

このような未解決の問題の検出は、第１２Ａ図
に関連して説明した構造及び手順に既に包含され
ている。第１３図に示したデータ・セツトが（当
該データ・セツトに新しいレコードを挿入する前
に必要とされるような）更新アクセスのために選
択された場合、第１２Ａ図に示したオープン・ス
テータス検査手順によりデータ・セツト・ステー
タスを更新状態へセツトされた当該データ・セツ
トのルート・ノード５００が記憶ボリユームへ書
込まれる。ワード・プロセシング・システム１０
への電源が復元した後は、このデータ・セツト・
インデツクスに関する未解決の問題が書込まれる
まで、オープン・ステータス手順によつて以後の
アクセスが禁止される。これは現データ・セツ
ト・ステータスが更新状態へセツトされているた
めである。

第１３図に関連して説明した外部電源の故障後
は、記憶ボリユーム上に他の未解決の問題が存在
する。第７図は、ボリユーム上に置かれた媒体割
振マツプを示す。性能上の理由で、UCS３００
（第８図）に置かれた媒体割振マツプのコピーは
割振りが変更されるたびにボリユーム上に記憶さ
れるのではなく、インデツクス及びデータ・セツ
ト・レコードの変更が完了したとき離散的なイン
ターバルで記憶される。

第１３図の例では、記憶ボリユームに置かれた
媒体割振マツプ中の割振指示のうちリーフ・ノー
ドＣ１（５１４）及びリーフ・ノードＣ２（５１
６）を保持する論理セクタに対する割振指示は、
依然としてこれらの論理セクタが将来の割振りの
ために利用可能であることを示す。もしこれらの
論理セクタがボリユーム上の割振要求を満足させ
るように後で使用されるならば、異なる情報がリ
ーフ・ノードＣ１（５１４）、リーフ・ノードＣ
２（５１６）又はその両方に置換わることがあ
る。この場合、リーフ・ノードＣ１（５１４）及
びリーフ・ノードＣ２（５１６）にインデツク
ス・エントリを有していたすべてのレコードは、
操作員から見れば失われてしまうことになる。

リーフノードＣ（５０６）を保持す論理セクタ
の場合は、記憶ボリユーム上の媒体割振マツプに
おいてこの論理セクタが既に割振られたものとし
て指示されているという点で、それほど重要でな
い問題が存在する。リーフ・ノードＣ（５０６）
中の情報はもはや必要ないからら、リーフ・ノー
ドＣ（５０６）を保持する論理セクタは将来の割
振りに利用可能でなければならない。

前述の媒体割振マツプの問題は、全体として記
憶ボリユームに関係する。新しいリーフ・ノード
Ｃ１（５１４）及びＣ２（５１６）の損失を防ぐ
ために、この問題が解決されるまでボリユームに
対する更新アクセスは全体として禁止されねばな
らない。というのは、ボリユーム上にある論理セ
クタの新しい割振要求は、単一の媒体割振マツプ
について行われるからである。

潜在的な問題の検出はボリユーム・アンカー中
のボリユーム更新指示によつて行われるが、これ
はデータ・セツトのルート・ノードに置かれたデ
ータ・セツト・ステータスと似ている。或るデー
タ・セツトがタイプ更新のためにオープンを要求
した場合、アンカー中のステータスはこの事実を
反映するようにセツトされる。任意のデータ・セ
ツトが更新のためにオープンされている場合、た
とえ元のデータ・セツトがクローズのために要求
されたとしても、アンカー・ステータスは更新ス
テータスを反映する。更新アクセスのためにオー
プンされた最後のデータ・セツトがクローズされ
る場合にのみ、アンカー・ステータスは、ボリユ
ーム・インデツクス（媒体割振マツプを含む）が
検出された未解決の問題を含まないことを反映す
るように、更新されるのである。

検出された未解決の問題を前述の機構を通して
解決することは、回復手順によつて行われる。こ
の回復手順は、媒体エラーによつて生ぜられたデ
ータ・セツト又はボリユーム・インデツクス中の
未解決の問題を解決するとともに、外部電源の故
障に起因するシステム処理の異常終了によつて生
ぜられるような問題をも解決することができなけ
ればならない。所与の記憶ボリユームでは、前述
のすべての問題が同時に生ずることがありうる。

論理セクタの現在の割振状態を正確に反映する
ように当該ボリユームに対する媒体割振マツプを
構成するためには、或るデータ・セツト又はボリ
ユーム・インデツクスへ実際に割振られたすべて
のセクタを探し出す必要がある。このことは、シ
ステム・アンカを起点として直接的又は間接的に
到達することができる各インデツクス・ノード中
のすべてのインデツクス・エントリを調べること
を意味する。第７図を参照するに、このことは次
のもの、すなわちアンカー２８４、媒体割振マツ
プ２８６、データ・セツトＡ（２８８）、デイレク
トリ２９１、データ・セツトＢ（２８９）又はデ
ータ・セツトＣ（２９０）へ割振られたすべての
論理セクタを探し出すことを意味する。第１３図
を参照するるに、このことは或るデータ・セツト
の有効なインデツクス・ノード及びデータ・レコ
ードのみが割振られたものとみなされ、そしてリ
ーフ・ノードＣは有効なインデツクス・ノードと
はみなされないことを意味する。第６図を参照す
るに、中間ノードＪ（２４６）、リーフ・ノードＦ
（２６６）及びリーフ・ノード・チエーン２６４
の存在は、たとえ中間ノードＩ（２６４）が回復
中に適正にアクセスできないとしても、リーフ・
ノードＣ（２５８）を間接的に探し出すことがで
きるということを意味する。中間ノードＩ（２４
４）とともに失われたインデツクス・エンントリ
は、回復の一部として、１つ又はそれ以上の既存
の又は新しい中間ノードで再構成されねばならな
い。

ワード・プロセシング・システム１０にとつて
非常に重要な回復の１側面は、性能である。すな
わち、第４図ないし第７図に示したボリユーム・
インデツクス構造によつて利用可能にされるすべ
ての情報源を使用して、できるだけ多くの操作デ
ータを回復することが肝要である。一方、操作員
が通常のワード処理タスクを継続することができ
るように、回復手順はできるだけ速やかに完了さ
れねばならない。特に、、DASD２２で行われる
Ｉ／Ｏ動作の数は最小でなければならない。媒体
割振マツプを再構成するためにはすべてのボリユ
ーム及びデータ・セツト・インデツクス・ノード
を少くとも１回アクセスすることが必要であるか
ら、最良の場合ですら或るインデツクス・ノード
の読取り及び書込みを１回行わねばならない。

ワード・プロセシング・システム１０中の
SAMルーチン４４は、種々のデータ・セツト及
びデータ・タイプを処理するように設計された一
般的なアクセス方式手順から成る。各データ・セ
ツト・タイプのデータ・レコードを処理するため
の一意的なキーストローク・サービス・ルーチン
が既に存在するので、SAMルーチン４４中の回
復手順は実際のデータ・レコードを処理する必要
はない。ボリユーム上の或るデータ・レコードを
探し出したり、該レコードへ割振られた論理セク
タ番号を決定するには、当該データ・セツトのイ
ンデツクス・ノード（リーフ・ノード）をアクセ
スするだけでよく、データ・レコードを実際にア
クセスする必要はない。従つて、SAMルーチン
４４中の回復手順はデータ・レコードを読取り又
は書込みのためにアクセスしない。キーストロー
ク・サービス・ルーチン３４は、ボリユーム上に
置かれたボリユーム及びデータ・セツト・インデ
ツクス中のすべての問題をSAMルーチン４４が
解決した後、損傷を受けたデータ・セツト中のデ
ータ・レコードを調べなければならない。しかし
ながら、損傷を受けた可能性があるデータ・セツ
ト中のデータ・レコードのみが調べられねばなら
ない。言いかえれば、SAMルーチン４４中の回
復手順を開始する際に、ルート・ノードのデー
タ・セツト・ステータスがクローズ状態にセツト
されているようなデータ・セツトのデータ・レコ
ードは、キーストローク・サービス・ルーチン３
４によつて調べる必要はない。通常の場合、或る
ボリユームにはこのような損傷をうけたデータ・
セツトが１つ又は２つあるにすぎない。このこと
は操作員に対する全体的なデータ回復手順の性能
を著しく改善する。

第１４図には、SAMルーチン４４の回復部分
を構成す複数の手順と、これらの手順の間の関係
が示されている。

ボリユーム／アンカー回復手順５２５は、ボリ
ユーム回復のためにキーストローク・サービス・
ルーチン３４からSAMルーチン４４へ与えられ
る要求に応答して行われる。この手順５２５は、
グローバル回復バツフアにすべての回復内部パラ
メータを初期設定し、アンカーの回復を制御する
とともに、回復の結果をUCS３００（第８図）
又は記憶ボリユームに分散記憶させる。アンカー
を回復するためには、インデツクス構成要素中の
各インデツクス・エントリは一度に１つずつ処理
される。アンカー中の各インデツクス・エントリ
は１つのデータ・セツトを参照するから（但し、
ボリユーム／アンカー回復手順で処理される媒体
マツプ・エントリを除く）、このプロセスは線５
２７によつて示されるようにデータ・セツト／ル
ート・ノード回復手順５２６へ要求を発する。

データ・セツト／ルート・ノード回復手順５２
６は、単一のデータ・セツトの回復を制御する。
この手順の主たる機能は、データ・セツト名を含
むこともあるデータ・セツト・ルートの有効性を
検査すること、データ・セツト・プロフイル中の
無効な値をワード・プロセシング・システム１０
によつて実際にサポートされているルート・ノー
ド又はデータ・セツトではない論理セクタの指示
として検査すること、残りのデータ・セツト・イ
ンデツクスを回復するために他の回復手順へ要求
を発すること、そしてデータ・セツト・インデツ
クス中にある下位レベルのインデツクス・ノード
の回復の結果としてルート・ノードを更新するこ
とである。

第４図ないし第６図の例によつて示されるよう
に、データ・セツト・インデツクスは単一レベル
（ルート／リーフ・ノード）から成ることもある
し、２レベル（ルート・ノード及びリーフ・ノー
ド）又は３レベル以上（ルート・ノード、１レベ
ル以上の中間ノード、リーフ・ノード）から成る
こともある。これらの３つのケースに対する回復
手順は若干相違している。

ルート／リーフ・ノードの場合は、単一ノード
のみを考えればよく、リーフ・チエーンは関係な
い。この場合、データ・セツト／ルート回復は、
ルート／リーフ・ノードのインデツクス構成要素
中のインデツクス・エントリを処理するために、
線５２８によつて示すように単一リーフ回復手順
５２９へ要求を発する。

データ・セツトが２以上のレベルを有する場合
は、リーフ・ノードが直近上位レベルのインデツ
クス・エントリによつて正確に参照されないこと
がる。或るリーフ・ノードを２つのリーフ・ノー
ドへ分割するプロセスの間に行われるノード作成
及び更新の順序は注意深く管理されており、かく
てリーフ・ノード・チエーン２０６（第５Ａ図）
中の次位リーフLSN２１８は記憶ボリユームに
置かれた当該データ・セツトのすべてのリーフ・
ノードについて正しい。第１３図を参照するに、
リーフ・ノードＢ（５０４）中の次位リーフLSN
は、リーフ・ノードＣ１（５１４）及びリーフ・
ノードＣ２（５１６）がボリユームへ書込まれた
後にだけ、記憶ボリユーム上で更新される。

リーフ・レベル回復手順５３２は、リーフ・ノ
ードを回復する際の順序づけを制御する。この手
順は、リーフ・ノード・チエーンの前位リーフ
LSN及び次位リーフLSNを使用することにより、
リーフ・ノード・チエーンを介して探し出すこと
ができるデータ・セツト・インデツクス中のすべ
てのリーフ・ノードが正しいシーケンスで回復に
含まれることを保証する。たとえば、データ・セ
ツト／ルート・ノード回復手順から線５３３を介
してリーフ・レベル回復手順５３２へ要求が発せ
られる場合、指定されたリーフ・ノードが開始点
として使用される。リーフ・レベル回復手順５３
２は、リーフ・ノード・チエーンの前位リーフ
LSNを使用することにより、左端のリーフ・ノ
ードが（当該データ・セツトについてリーフ・レ
ベル回復手順５３２へ与えられる最初の要求のた
めに）見出されるか又は既に回復されたリーフ・
ノードが探し出されるまで、前位リーフ・ノード
を順次にスキヤンする。リーフ・ノードはこの点
から回復され、そして元の要求のリーフ・ノード
に到達するまで上位レベルのインデツクス・ノー
ドへ追加される。

当該データ・セツトが１レベル以上の中間イン
デツクス・ノードを有する場合、データ・セツ
ト／ルート・ノード回復手順５２６はそのインデ
ツクス・エントリの各々ごとに線５３６を介して
中間ノード回復手順５３５へ要求を発する。中間
ノード回復手順５３５の機能は、要求を発したノ
ードのインデツクス・エントリを線５３７を介し
てリーフ・レベル回復手順５３２へ順次に与える
ことである。中間ノードにはチエーンは存在しな
いから、中間ノード回復手順５３５は要求された
中間ノードだけを考慮する。

ワード・プロセシング・システム１０は、２レ
ベル以上の中間ノードを有するデータ・セツトを
許容する。このようなデータ・セツトでは、最上
位レベルの中間ノードは他の中間ノードを参照す
るインデツクス・エントリを保持する。このこと
が生ずる場合、中間ノード回復手順５３５は線５
３８を介してそれ自体へ再帰的要求を発するが、
この再帰的要求はそれとは異なる中間ノードを参
照するものである。

第７図に示したように、アンカーのインデツク
ス・エントリはデータ・セツトのルート・ノード
及びデイレクトリのルート・ノードを参照する。
データ・セツト・インデツクスの構造とデイレク
トリ・インデツクスの構造は、同等である。従つ
て、これらの両インデツクスについて同じ１組の
回復手順が使用される。当該インデツクスがデー
タ・セツト・インデツクスである場合、単一リー
フ回復手順５２９は、インデツクス・エントリで
参照される論理セクタが再構成中の媒体割振マツ
プで割振られているものとして指示されることを
保証しなければならない。

しかしながら、デイレクトリ・インデツクスに
ついては、各インデツクス・エントリは同じデー
タ・セツト・タイプを有するデータ・セツトのル
ート・ノードを参照する。デイレクトリのリー
フ・ノード・インデツクス・エントリの有効性を
検査することは、該エントリが参照するデータ・
セツトを回復することを必要とする。従つて、単
一リーフ回復手順５９は各データ・セツトごとに
線５４０を介してデータ・セツト／ルート・ノー
ド回復手順５２６へ再帰的要求をを発するととも
に、データ・セツト／ルート・ノード回復手順５
２６によつて戻される有効性指示に基づてデイレ
クトリ・リーフ・ノードを更新する。ワード・プ
ロセシング・システム１０では、１レベルのデイ
レクトリ・データ・セツトが存在するにすぎな
い。デイレクトリ・リーフ・ノード中のインデツ
クス要素で参照される明白なデイレクトリ・ルー
ト・ノードは無効データ・セツトとみなされ、そ
してデイレクトリ・リーフ中のインデツクス要素
は削除される。かくて、データ・セツト／ルー
ト・ノード回復手順５２６へ与えられる再帰的要
求それ自体が、他の再帰的要求を生ぜしめること
はない。

第１５図には、ボリユーム回復に関係する本発
明の論理的動作が流れ図の形式で示されている。
この手順は、ボリユーム回復サービス・ルーチ
ン・ステツプ５５０で終了する。ステツプ５５１
では、構文規則及びルート・ノードで許容される
サポート値に従つて、アンカーが検査される。ア
ンカーは既にメモリ２６に置かれており、一層詳
細にはUCS３００（第８図）のボリユーム・デ
ータ・セツト・インデツクス３０４に置かれてい
る。もしアンカーが無効であることがわかれば、
当該ボリユームがサポートされていないことがス
テツプ５５３の戻りコードを介して通知され、そ
して次のボリユーム回復要求が受取られるまでこ
の手順はステツプ５５５で終了する。

もしアンカーが有効であれば、ステツプ５５７
ではUCS３００中の媒体割振マツプ・バツフア
３１２からグローバル回復バツフア３４０中の媒
体割振マツプ・バツフア１（３４２）へ元の媒体
割振マツプがコピーされる。媒体割振マツプ・バ
ツフア２（３４４）は、媒体制御レコードの２コ
ピーへ割振られる論理セクタを除き、利用可能を
すべての論理セクタを指示するように初期設定さ
れる。最初のアンカー・インデツクス・エントリ
は、ステツプ５５８で探し出される。

もしステツプ５６０のテストにより現在のアン
カー・インデツクス要素が（アンカー又は媒体割
振マツプではない）真のデータ・セツトを参照す
るものであることがわかれば、ステツプ５６２で
はデータ・セツト回復手順が行われる。続くステ
ツプ５６３では、当該データ・セツトが有効なデ
ータ・セツトであるか否かを決定するために、ス
テツプ５６２からの戻りコードがテストされる。
もし当該データ・セツトが有効でなければ、ステ
ツプ５６５ではアンカーからそのインデツクス・
エントリが削除されるる。

このインデツクス・エントリがステツプ５６０
ないし５６５で処理された場合、ステツプ５６７
で次のアンカー・インデツクス・エントリが探し
出される。もしステツプ５６８のテストによりア
ンカーの終りにまだ到達していないことがわかれ
ば、次のインデツクス・エントリについてステツ
プ５６０ないし５６７が再び行われる。最後のア
ンカー・インデツクス・エントリが処理された場
合、前述のようにステツプ５５５でこの手順を終
了する前にステツプ５７０の戻りコードを介して
回復完了が通知される。

媒体割振マツプを再構成する場合には、次の３
つの事項が考慮される。すなわち、回復中に割振
り済み（利用不能）であることを見出されたすべ
ての論理セクタをマークすること、複数のインデ
ツクス・エントリが同一の論理セクタを参照する
を禁止すること、そして回復プロセス中に新しい
インデツクス・ノードが作成される場合には新し
い割振りを見つけること、がそれである。

第１５図のステツプ５５７では、２つの媒体割
振マツプが準備される。グローバル回復バツフア
３４０の媒体割振マツプ・バツフア２（３４４）
に置かれた媒体割振フツプはすべての論理セクタ
が利用可能であるように初期設定される。

回復中に遭遇した任意のインデツクス・エント
リで或る論理セクタが参照される場合、まず媒体
割振マツプ・バツフア２（３４４）中の現セク
タ・ステータスが検査される。もしこのセクタが
既り割振られていれば、このセクタは回復手順に
おいて以前に遭遇したものであるから、それ以上
の処理を行うことなく、そのレコード記述子（リ
ーフ・ノード）又はインデツクス・エントリ（中
間ノード若しくはルート・ノード）が削除され
る。このステツプは、回復手順の終了時には、ど
の論理セクタも記憶ボリユーム上のボリユーム又
はデータ・セツト・インデツクスにある１より多
いインデツクス・エントリで参照されることはな
い、ということを保証する。

一方、もしこの論理セクタが以前に探し出され
ていなければ（媒体割振マツプ・バツフア２中の
ステータスが割振りのための利用可能性を示す場
合）、このステータスは媒体割振マツプ・バツフ
ア１（３４２）及びバツフア２（３４４）で割振
状態へ変更される。回復手順の終了時にすべての
データ・セツト及びボリユーム・インデツクスが
処理されている場合は、当該インデツクスのイン
デツクス要素で参照されるすべての論理セクタは
媒体割振マツプ・バツフア２（３４４）で割振状
態へマークされる。

或るデータ・セツトを処理している間、特に当
該手順が読取エラーに遭遇するる場合、又は第１
３図に示すように或るインデツクス・ノードの分
割中に異常な外部電源の故障に遭遇する場合は、
当該インデツクスの上位レベルにおける分割プロ
セスを完了するために新しい論理セクタの割振り
が必要となることがある。UCS３００から媒体
割振マツプ・バツフア１（３４２）へコピーされ
た元の媒体割振マツプが、この新しい割振りを見
つけるために使用される。

ワード・プロセシング・システム１０で通常の
動作を行つている間に論理セクタの割振りを行う
には、まず媒体割振マツプの始点（最小の論理セ
クタ番号）で探索を開始し、フアースト・フイツ
ト（first−fit）アルゴリズムに従つた割振りが
満足されうるまで、この探索を継続して行う。す
べての割振りは媒体割振マツプの始点で開始する
ので、記憶ボリユーム上で実際に利用可能な任意
のスペースは最大の論理セクタ番号を有する論理
セクタに集中する傾向がある。従つて、利用可能
な１つの論理セクタ又は連続的な１組の論理セク
タを探し出すために、媒体割振マツプ・バツフア
１（３４２）はその媒体割振マツプの終りから逆
方向に（すなわち最大の論理セクタ番号から最小
の論理セクタ番号の方へ）探索される。回復は新
しいインデツクス・ノード（個々の論理セクタ）
を生成するにすぎないから、記憶ボリユームの断
片化は問題ではない。もしこの探索中に利用可能
な或るセクタが見出されるならば、このセクタが
回復手順によつてまだ処理されていないような或
るインデツクス・エントリへ実際に割振られてい
る確率は低い。かくて、記憶ボリユームにもはや
余分のスペースがないという場合だけが、問題を
生ぜしめるのである。丁度割振られたばかりのセ
クタを参照する後のインデツクス・エントリは、
その遭遇時に前述のように削除される。

第１６Ａ図には、データ・セツト回復に関係す
る本発明の論理的動作が流れ図の形式で示されて
いる。この手順は、データ・セツト回復サービ
ス・ルーチン・ステツプ５７５で開始する。ステ
ツプ５７６では、このデータ・セツトを回復する
ために使用されるデータ・セツト領域バツフアが
適正に初期設定される。

次に、ルート・ノードの検査が行われる。ステ
ツプ５７８では、ルート・ノードの構文及びプロ
フイル中のサポート値が検査される。もし当該デ
ータ・セツトの回復を要求する手順（単一リーフ
回復手順のみ）によつてデータ・セツト名が供給
されたならば、このデータ・セツト名はステツプ
５８０でルート・ノードのデータ・セツト・プロ
フイルに置かれたデータ・セツト名と比較され
る。続くステツプ５８２では、現ルートが無効な
第２レベルのデイレクトリ（デイレクトリ・リー
フ・ノードで参照されるデイレクトリ）であるか
否かを決定するるために、現ルート及び現環境が
検査される。もしステツプ５７８，５８０又は５
８０のテスト結果について問題があれば、ステツ
プ５８４の戻りコードを介して無効データ・セツ
トが通知され、そしてこの手順は次のデータ・セ
ツト回復要求が受取られるまでステツプ５８６で
終了する。

もしルート・ノードの構文及び環境に対するす
べての検査に成功すれば、ステツプ５８８でルー
ト回復手順が行われる。次いで、ステツプ５８９
の戻りコードを介して当該データ・セツトの回復
完了が通知され、そしてこの手順はステツプ５８
６で前述のように終了する。

第１６Ｂ図には、第９図のグローバル回復バツ
フア３４０に設けられたデータ・セツト領域１バ
ツフア（３４６）及びデータ・セツト領域２バツ
フア（３８４）が一層詳細に示されている。デー
タ・セツト領域バツフア６００は、５種類のフイ
ールドを含む。

データ・セツト情報領域６００は、当該デー
タ・セツトの回復を全体として順序づけるため
に、当該データ・セツトの現回復ステータスを保
持する。またデータ・セツト情報領域６０１は、
当該データ・セツト中の下位レベルにあるインデ
ツクス・ノードの有効性を検査するために原イン
デツクス・ノード・ヘツダを保持するとともに、
データ・セツト・プロフイルのデータ及びインデ
ツクス属性要素から与えられる使用頻度の大きい
パラメータを保持する。

ルート・レベル・バツフア６０２は、当該デー
タ・セツトのルートを回復するための作業記憶域
を与える。中間レベル・バツフア１（６０３）及
びバツフア２（６０４）は、当該データ・セツト
の中間レベルを回復するために割振られている。
リーフ・レベル・バツフア６０６は、リーフ・レ
ベルを回復するための作業記憶域を与える。ルー
ト・リーフ・ノードのデータ・セツト・インデツ
クスについては、データ・セツト回復手順におい
てルート・レベル・バツフア６０２のみが実際に
使用され、他のレベル・バツフアは使用されな
い。２レベルのデータ・セツトについては、ルー
ト・レベル・バツフア６０２及びリーフ・レベ
ル・バツフア６０６だけが使用される。それ以上
のレベルを有するデータ・セツトの場合は、中間
レベル・バツフア１（６０３）及びバツフア２
（６０４）の少くとも一方が必要となる。

第１６Ｃ図には、第１６Ｂ図のルート・レベ
ル・バツフア６０２が一層詳細に示されている。
ルート・レベル・バツフア６１０は、３種類の部
分を含む。すなわち、現エントリ・オフセツト領
域６１２は当該インデツクス・ノード中の現イン
デツクス・エントリに対するオフセツト及び該エ
ントリ中の種々のパラメータを保持し、作業キ
ー・バツフア領域６１３は後で使用したり又は或
るインデツクス・エントリを作成するために２つ
以下のキーを一時的に保持し、ルート・ノード・
バツフア６１５は回復中のデータ・セツトに対す
るルート・ノードのコピーを保持する。

第１６Ｄ図には、ルート回復に関係する本発明
の論理的動作が流れ図の形式で示されている。こ
の手順は、ルート回復サービス・ルーチン・ステ
ツプ６２５で開始する。ステツプ６２６では、ル
ート・ノード及び２次コピーに対する媒体割振マ
ツプのステータス指示が更新される。なぜなら、
データ・セツトのルート・ノードは、有効な構文
を有し且つ有効な環境で存在するものとして検査
されるからである。もしステツプ６２８のテスト
により当該ルート・ノードがルート／リーフ・ノ
ードであることがわかれば、ステツプ６３０で単
一リーフ回復手順を行うことによつてそのインデ
ツクス要素が回復される。この手順はルート／リ
ーフ・ノード全体の回復を処理するから、それ以
上のことは必要なく、従つてこの手順は次のルー
ト回復要求が受取られるまでステツプ６３２で終
了する。

もし当該インデツクス中に下位レベルがあれ
ば、ステツプ６３４でルート・ノード中の最初の
インデツクス・エントリが探し出される。続くス
テツプ６３６では、下位レベルのうちどのレベル
の回復手順を行うべきかということが決定され
る。もし１より大きければ、最高の中間レベルの
回復を行うために指定された中間レベルバツフア
１（６０３）で中間レベル回復手順が行われる。
さもなければ、リーフ・レベル回復手順が行われ
る。続くステツプ６４０では、選択された回復手
順の終了時にルート・ノード中のインデツクス・
エントリが更新される。

このようにして当該ルート・ノードの現インデ
ツクス・エントリを処理した後、ステツプ６４１
では次のインデツクス・エントリが探し出され
る。もしステツプ６４２のテストにより当該ルー
ト・ノードの終りにまだ達していないことがわか
れば、ステツプ６３６乃至６４１が次のインデツ
クス・エントリについて再び行われる。一方、も
し当該ルート・ノードの終りに達したなば、この
手順は前述のようにステツプ６３２で終了する。

第１７Ａ図には、リーフ・レベル回復に関係す
る本発明の論理的動作が流れ図の形式で示されて
いる。この手順は、リーフ・レベル回復サービ
ス・ルーチン・ステツプ６５０で開始する。ステ
ツプ６５１では、指定されたリーフ・ノード、す
なわち上位レベルのノードに対する回復手順によ
つてサービス要求が発せられたリーフ・ノードが
取出される。

次に、第１３図に例示する如きインデツクス・
エラーの発生が検査される。もしステツプ６５２
のテストにより左端のリーフ・ノード（前位リー
フLSNが無効であるようなリーフ・ノード）が
探し出されなかつたことがわかれば、この左端の
リーフ・ノードを見つけるためにステツプ６５３
で逆方向スキヤン手順が行われる。第６図を参照
するに、このことが生じうるのは、最初の中間ノ
ードＩ（２４４）の取出しが成功せず且つリー
フ・ノードＦ（２６６）が当該データ・セツトで
探し出された最初のリーフ・ノードであるような
場合である。逆方向スキヤンは、現リーフ・ノー
ドよりも低いキー値を有するインデツクス・エン
トリを保持する如きリーフ・ノードを探し出すた
めに、リーフ・ノード・チエーン２０６（第５Ａ
図）の前位リーフLSN２１６を使用する。もし
左端のリーフ・ノードが既に探し出され且つ回復
されているなば、回復に成功した最後のリーフ・
ノードが指定されたリーフ・ノードの直前にある
リーフ・ノードであるか否かを決定するために、
ステツプ６５５でテストが行われる。この関係は
次のように表わされる。

回復された最後のリーフ・ノードのLSN＝指
定されたリーフ・ノードの前位リーフLSN 回復された最後のリーフ・ノードの次位リーフ
LSN＝指定されたリーフ・ノードのLSN もしステツプ６５５のテストによりリーフ・レ
ベルで問題があることがわかれば、回復された最
後のリーフ・ノードについて逆方向スキヤンが行
われる。もしすべてのチエーン値が矛盾を含ま
ず、そしていかなるインデツクス・エラーも指示
されなければ、指定されたリーフ・ノードが回復
すべき次のリーフ・ノードとして維持される。

ステツプ６５８では、現リーフ・ノードは単一
リーフ回復手順を行うことによつて回復される。
続くステツプ６５９では、丁度回復されたばかり
のリーフ・ノードのリーフ・ノード・チエーンか
ら次位リーフLSNが取出される。そもしステツ
プ６６０及び６６２のテストにより指定された元
のリーフ・ノードにまだ達していないことがわか
れば、次のリーフ・ノードが取出され、そしてス
テツプ６５８及び６５９を反復することにより前
述のように回復される。もしステツプ６６０のテ
ストにより指定されたリーフ・ノード回復された
ことがわかれば、このサービス要求についてはそ
れ以上の回復動作は必要ない。もし、ステツプ６
６２でリーフ・ノードのハイ・キーをテストする
ことにより、当該インデツクスにおける指定され
たノードの回復が既に終つていることがわかれば
（第１３図の例では、リーフ・ノードＣが指定ノ
ードであつて、リーフ・ノードＣ１及びＣ２を回
復するような場合）、この指定されたノードは媒
体割振マツプでその論理セクタ割振りを解除する
ことによつて捨てられてしまう。

最後に、上位レベルのインデツクス・ノードで
挿入又は置換を行うために置換インデツクス・エ
ントリが再構成され、そしてこの手順は次のルー
ト回復要求が受取られるまでステツプ６６８で終
了する。

第１７Ｂ図には、逆方向スキヤンに関係する本
発明の論理的動作が流れ図の形式で示されてい
る。この手順は、逆方向スキヤン・サービス・ル
ーチン・ステツプ６７５で開始する。ステツプ６
７７では、現リーフ・ノードのリーフ・ノード・
チエーンから前位リーフLSNが得られる。もし
ステツプ６７９のテストにより前位リーフLSN
が無効であることがわかるか、又はステツプ６８
１のテストによりこの前位リーフLSNが最後に
回復されたリーフLSNであることがわかれば、
この手順は次のルート回復要求が受取られるまで
ステツプ６８５で終了する。

もし左端リーフ又は回復された最後のリーフに
到達していなければ、ステツプ６８３で前位リー
フが取出され、そしてこの新しく取出された前位
リーフ・ノードについてステツプ６７７ないし６
８２が反復される。

第１７Ｃ図には、第１６Ｂ図のデータ・セツト
領域バツフア６００にあるリーフ・レベル・バツ
フア６０６の内容が一層詳細に示されている。リ
ーフ・レベル・バツフア６９０は３種類のセクシ
ヨンを含む。すなわち、現エントリ・オフセツト
領域６９１は当該インデツクス・ノードの現イン
デツクス・エントリに対するオフセツト及び該イ
ンデツクス・エントリ中の種々のパラメータを保
持し、作業キー・バツフア領域６９２は必要に応
じて後で使用したり又は或るインデツクス・エン
トリを作成するために２以下のキーを一時的に保
持し、そして最後に３つのリーフ・ノード・バツ
フア１ないし３（６９３ないし６９５）が設けら
れている。リーフ・ノード・バツフアの数を除く
と、第１７Ｃ図のリーフ・レベル・バツフア６９
０は第１６Ｃ図のルート・レベル・バツフア６１
０と同じフオーマツトを有する。

或るデータ・セツトには唯１つのルート・ノー
ドがあるにすぎないから、１つのルート・ノー
ド・バツフアが必要となるにすぎない。しかしな
がら、第１７Ａ図ないし第１７Ｃ図に関連して説
明したように、逆方向スキヤンの動作中は３つの
異なるインデツクス・ノード、すなわち指定され
た元のリーフ・ノード、左端のリーフ・ノード又
は回復された最後のリーフ・ノード、そして前２
者の間に行われるスキヤンの一部として読取られ
るリーフ・ノードを検討しなければならないこと
がある。リーフ・レベルでは、インデツクス・エ
ントリが追加されることはなく、同じ論理セクタ
の重複割振りの問題に起因して削除されることが
あるにすぎない。従つて、回復手順の間にはリー
フ・レベルで分割が行われることはない。

以上詳述したように、本発明によれば、DASD
上のセクタで記憶媒体エラーが検出された場合で
あつても操作員に対する相当量のデータが失われ
ないように、DASDに記憶されたデータ・セツト
を保護することが可能となる。また、可能なエラ
ーを検出した場合には、正しくなく且つ矛盾性を
含むインデツクスを有するるようなデータ・セツ
トを通常の動作のためにアクセスするのを禁止す
ることができる。さらに、記憶媒体エラーが生じ
たり、又はデータ・セツト・インデツクスの変更
中に電源が故障したためデータ・セツト・インデ
ツクスの更新が正常に完了しない場合には、これ
らの原因に応じて生じうるすべてのインデツク
ス・エラーを解決するためにボリユーム上のすべ
てのインデツクス・ノードをスキヤンすることが
できる。これらのデータ保護及び回復方式を導入
しても、ワード・プロセシング・システム１０の
通常の動作の性能は極くわずか低下するにすぎな
い。

【図面の簡単な説明】

第１図は本発明を包含するワード・プロセシン
グ・システムを示すブロツク図、第２図は第１図
のプロセツサを一層詳細に示すブロツク図、第３
図はデイスケツト又はハード・デイスクの如き直
接アクセス記憶デバイス（DASD）にデータ・セ
ツト（文書）の形式で記憶されたテキストを示す
ブロツク図、第４Ａ図ないし第４Ｃ図は比較的小
さいデータ・セツトに対するデータ・セツト・イ
ンデツクスであつて、１つのルート／リーフ・ノ
ードだけを含むデータ・セツト・インデツクスを
例示するブロツク図、第５Ａ図及び第５Ｂ図は比
較的大きいデータ・セツトに対するデータ・セツ
ト・インデツクスであつて、１つのルート・ノー
ド及び２つのリーフ・ノードを含むデータ・セツ
ト・インデツクスを例示するブロツク数、第６図
は１つのルート・ノード、２つの中間ノード及び
多くのリーフ・ノードを含むデータ・セツト・イ
ンデツクスを例示するブロツク図、第７図はボリ
ユーム及びデータ・セツト・インデツクス間の関
係を例示するブロツク図、第８図は第１図の記憶
アクセス方式（SAM）内部制御ブロツクを一層
詳細に示す図、第９図は第１図のSAMインタフ
エース制御ブロツクを一層詳細に示す図、第１０
Ａ図及び第１０Ｂ図は冗長的に記録された媒体制
御レコード及びボリユーム・アンカーを一層詳細
に示すブロツク図、第１１Ａ図及び第１１Ｂ図は
インデツクス・ノードの読取り及び書込みに関係
する本発明の動作ステツプを示す流れ図、第１２
Ａ図及び第１２Ｂ図はデータ・セツト・ステータ
スを検査及び管理するために行われるデータ・セ
ツトのオープン及びクローズに関係する本発明の
動作ステツプを示す流れ図、第１３図は３レベル
のデータ・セツト・インデツクスにおいて、新し
いリーフ・ノードを中間ノードに反映させること
ができる前に、電源の故障によつてリーフ・レベ
ルの分割動作が中断されるような状況を例示する
ブロツク図、第１４図はボリユーム回復プロセス
の主要な手順及びこれらの手順間の関係を示すブ
ロツク図、第１５図はボリユーム回復手順に関係
する本発明の動作ステツプを示す流れ図、第１６
Ａ図はデータ・セツト回復手順に関係する本発明
の動作ステツプを示す流れ図、第１６Ｂ図は第９
図のデータ・セツト領域を一層詳細に示すブロツ
ク図、第１６Ｃ図は第１６Ｂ図のルート・レベ
ル・バツフアを一層詳細に示すブロツク図、第１
６Ｄ図はルート回復手順に関係する本発明の動作
ステツプを示す流れ図、第１７Ａ図及び第１７Ｂ
図はリーフ・レベル回復手順及び逆方向スキヤン
手順に関係する本発明の動作ステツプをそれぞぞ
れ示す流れ図、第１７Ｃ図は第１６Ｂ図のリー
フ・レベル・バツフアを一層詳細に示す図であ
る。

Claims (1)

1. 【特許請求の範囲】 １ 直接アクセス記憶装置（DASD）ボリユーム
   上の情報が、複数の階層的インデツクス・ノード
   に従い配列された情報処理システムにおいて、媒
   体セクタ上の記憶媒体エラーによる記憶媒体ボリ
   ユームのアクセス不能、またはデータの遺失を軽
   減するためのボリユーム回復方法において、 (a) 最高レベルのインデツクス・ノードに、当該
   記憶ボリユームに対して一定のボリユーム・シ
   ヤドウ・オフセツト値を格納する段階を有し、 (b) 上記ボリユーム・シヤドウーオフセツト値は
   上記記憶ボリユーム上の全ての動作に対して一
   定であり、 (c) さらに、上記記憶ボリユーム上の複数の媒体
   セクタをもつ選択された複数のインデツクスに
   ついて、２つのコピーを記録し、該コピーのう
   ちの第１のものは、所定のインデツクス・ノー
   ドのうちの１つによつて示される論理セクター
   位置に配置され、該コピーのうちの第２のもの
   は、該第１のコピーから、上記最高レベルのイ
   ンデツクス・ノードに格納された上記ボリユー
   ム・シヤドウ・オフセツト値に等しい一定距離
   だけ離れた別の論理セクタに配置される段階
   と、 (d) 記憶媒体エラーにより所与のデータ・セツト
   に対するインデツクスを上記第１のコピーから
   取り出すことができない場合に、上記ボリユー
   ム・シヤドウ・オフセツト値に従い、上記第２
   のコピーから、該所与のデータ・セツトに対す
   るインデツクスを読み取る段階を有する、 ボリユーム回復方法。