JPH083798B2

JPH083798B2 - メモリ割当て方法

Info

Publication number: JPH083798B2
Application number: JP60089858A
Authority: JP
Inventors: ロランド・ウインフレツド・ロイ
Original assignee: ウオング・ラボラトリ−ズ・インコ−ポレ−テツド
Priority date: 1984-06-28
Filing date: 1985-04-25
Publication date: 1996-01-17
Anticipated expiration: 2011-01-17
Also published as: EP0166148B1; DE3586956T2; EP0166148A2; CA1237530A; US4849878A; AU575182B2; AU3940285A; EP0166148A3; DE3586956D1; JPS6115243A

Description

【発明の詳細な説明】産業上の利用分野本発明は、メモリを含む計算機ベース・システムに関
し、より詳細には、斯かるシステムのハードデイスクメ
モリに於けるスペースの割当て及びデータの圧縮に関す
る。

発明の背景大型小型を問わず、コンピユータシステムは全て、そ
の一部としてメモリを有している。このメモリは、静的
及び動的形式をとる。動的メモリの内容は、斯かるメモ
リへの電力が遮断された時に失なわれる。静的メモリの
内容は、電力が遮断されても失われず、例えばROM（読
出し専用メモリ）、フロツピイデイスケツト磁気メモ
リ、大容量ハードデイスク磁気メモリ、及びバブルメモ
リ等の様々な形を静的メモリはとる。ハードデイスク磁
気メモリはフアイル記憶のためにコンピユータシステム
に用いられることが多く、これらのフアイルには通常固
定量の記憶スペースが割当てられている。当技術では、
他のフアイルを追跡するメモリ中の管理フアイルがそれ
自身を分析し、ハードデイスクにもつと多くの遊休メモ
リスペースを割当て、必要に応じてそれを使用するよう
な構成を必要とする。

先行技術に於ては、データを記憶するための与えられ
た量のメモリスペースがフアイルに割当てられるのが一
般的であり、そのメモリスペース量は、融通性がないた
め、たとえ全てのスペースが必要でなくても、残りのス
ペースが浪費されてしまう。従つて、この融通性のない
メモリスペースに記憶されている２進情報を圧縮する実
質的な必要性は何ら存在しない。従つて、当技術に於て
は、デイスクに記憶され得るデータの量を最大にするた
めに、ハードデイスクメモリに記憶されているデータを
圧縮する技術が必要である。

発明の概要本発明の教示によると、次のようなハードデイスクメ
モリフアイル管理システムが開示されている。即ち、当
技術に於て公知の多くのフアイル管理機能を実行し、更
にデイスクフアイル管理システムによつて用いられる管
理フアイルの範囲即ちサイズを、それが満たされ更に多
くのメモリスペースを必要とする時に拡張可能とし、ま
たデイスクフアイル管理システムフアイルに記憶されて
いるデータを圧縮して、これにより記憶され得る情報量
を最大にするハードデイスクメモリフアイル管理システ
ムである。この新規な自己拡張フアイル機能を実行する
ために、デイスクフアイル管理システムは、各フアイル
に対して現在とられているメモリの合計量の記録を保持
し、各フアイルに対して取つておかれている未使用の即
ち空いているメモリの量の記録を保持し、自己拡張によ
つて自動的にデイスクフアイル管理システムフアイルに
加えられるべき遊休ハードデイスクメモリの量を示す数
を保存し、如何なるフアイルにもまだ割当てられていな
いハードデイスクメモリ上の使用可能な即ち空いている
スペースの記録を保持する。フアイル管理システムフア
イルが一ぱいに近づくと、そのフアイルに対して拡張さ
れるべき旨の要求が発生する。次に、このフアイル管理
システムはデイスク上の使用可能な即ち空いているメモ
リの所定量を突き止め（locate）且つこれを管理システ
ムフアイルに割当てる。この後、管理システムフアイル
のサイズ、そのフアイルに於ける遊休即ち空きメモリの
量、及びデイスク上の割当てられていないメモリの量に
関して保存された情報が管理システムフアイルへのデイ
スクメモリスペースの追加を反映するために、自動的に
更新される。管理システムフアイルが再び一ぱいになる
と、この新規の自己拡張フアイル機能は繰返される。

これらの諸フアイルに記憶されるべきデータは、記憶
される前に、32ビツト２進数の形をとる特定の数を２進
情報即ちデータから減算することによつて圧縮される。
これにより、記憶されるべき２進数の２進ビツトの数は
対応して減少する。圧縮を解くことによつて元の情報即
ちデータを再構成することができるようにするために、
保存されている圧縮された数の２ビツトが２進数の形を
とる元の情報即ちデータから減算された数を示す。これ
は、この時点で、減算された数を圧縮された数に加え、
これにより圧縮されない数を復元するためである。これ
らの２ビツトはまた、この数の圧縮されたサイズの合計
を示す。

実施例の詳細な説明第８図には、大量のデータ及びフアイルを記憶するた
めの大容量記憶手段としてハードデイスクメモリ86を含
む現行技術の処理装置システムのブロツク図が示されて
いる。このシステムは、複数のキーボード付ビデオ端末
装置81及び82を含んでいる。これらのビデオ端末装置
は、データ及び指令を処理装置に入力し且つ処理の結果
であるあるいはシステムのメモリ85あるいは86に記憶さ
れているデータを視覚的に表示するための入力／出力デ
バイスとして用いられる。この処理装置はまた、中央処
理装置83を含んでおり、この中央処理装置83には、バス
84を経由して端末装置81及び82が当技術において公知の
方法でもつて接続されている。これらの端末装置はま
た、内蔵プロセツサを有している。この内蔵プロセツサ
は図示されてはいないが、表示技術に於ては公知であ
る。中にオペレーテイング・システム及び応用プログラ
ムが記憶されており且つプロセツサ83によつてバツフア
記憶装置として用いられるメモリ85が配設されている。
ハードデイスクメモリ86も配設されており、このメモリ
は、データ等のフアイルの記憶に用いられる大容量記憶
デバイスである。ハードデイスク86は、デイスクフアイ
ル管理システムの制御下でプロセツサ83によつて作動さ
れ、端末装置81及び82を利用している処理装置のユーザ
の要求に応じて情報を記憶したり検索する。当技術に於
てよく知られているようにデータをフロツピイデイスク
から読み出したりフロツピイデイスクに書き込んだりす
るためにフロツピイデイスクユニツト87も配設されてい
る。フロツピイデイスクは当技術に於てよく知られてい
るようにプログラム及びデータの代替のメモリ記憶装置
として利用されている。端末装置81及び82の一方に於け
るユーザの要求に応じて、ビデオ表示装置10に表示され
ている表示のハードコピー出力あるいはハードデイスク
メモリ86のフアイルからのハードコピー出力を得るため
にプリンタ89を配設されている。第８図に示されている
この処理装置はまた、このシステムを他のシステム及び
記憶手段と通信せしめデータを転送し且つ当技術では公
知の他の機能を実行する通信インターフエース89を有し
ている。

上記のパラグラフに全体的に述べた型式の処理装置
は、「管理通信端末システム」として登録されている米
国特許出願第440,668号に記載されている。この特許出
願は、本明細書に参考として引用されている。本発明を
用いることのできるデイスクフアイル管理システムが、
本発明の詳細な説明と共に以下に述べられている。

デイスクフアイル管理システムが必要とされるのは、
当技術に於てよく理解されているようにハードデイスク
メモリ86に情報を記憶し且つこのメモリから情報を検索
することに関する監視機能を実行するためである。メモ
リの諸部分を特定のシステムユーザに割当てること、ど
んなデータがデイスクのどこに記憶されているかという
ことについてのインデツクスを保持すること、及びデイ
スクから情報を読み出し且つデイスクに情報を書き込む
こと等の機能はデイスクオペレーテイングシステムによ
つて実行される機能の例である。しかしながら、ユーザ
がそれらに割当てられたメモリの量を満たすと、割当て
られたメモリの量を拡張することはかなり困難になる。
先行技術に於ける代替手段は、特定のシステムユーザに
メモリの量を割当てて、このメモリを先着順に使わせる
ことではない。このことは、ユーザを１つのデイスクの
フアイルにまとめ且つ／又はそのデイスクの与えられた
領域にまとめたい場合は問題を生ずる。フアイルが与え
られたデイスクに且つ多くのデイスクにわたつて広がれ
ば広がる程、検索時間は許容不可能なレベル迄増大する
可能性がある。従つて、特定のユーザに割当てられたハ
ードデイスクメモリの諸部分を有することが好都合であ
り、前に割当てられた量のハードデイスクメモリが一ぱ
いになろうとしている時に容易に増大する量の割当てら
れたメモリを有することが切に望まれる。

ハードデイスクメモリを含む任意のメモリに記憶され
得る情報即ちデータの量を最大にするために、記憶する
前にデータに対してデータ圧縮技術を用いることが好ま
しい。当技術では多くのデータ圧縮技術が公知であり用
いられており、これらの技術はいろいろな利点及び欠点
を有しているが、それらは全て斯かる技術を選択する上
で相殺されてしまうにちがいない。１つの技術を用いて
データを圧縮し、次に別の技術を用いてこのデータを更
に圧縮するために再処理することは、あるとしても、非
常に少ない。本明細書ではそれ自身良好なデータ圧縮を
行うデイスクフアイル管理システムフアイルに記憶する
ためのデータ圧縮方法が教示されているが、このフアイ
ルからの圧縮データ出力は、他の技術を用いて更に圧縮
し、より高いデータ圧縮を達成することができる。

ハードデイスクメモリ86に記憶された２進情報即ち２
進データは、階層木構造フオーマツトに記憶されてい
る。斯かる形の記憶様式の場合、情報を記憶するのに固
定された量のメモリ即ちメモリのブロツクが用いられ
る。そして、情報を記憶するのに必要な多数のブロツク
が用いられる。例えばあるドキユメントを表わし得る１
組の２進情報を記憶している複数のブロツクは１本の電
気的連糸のビードのように全て互いに関連して結び合つ
ている。これは、１つのブロツクがアクセスされた時
に、論理的なブロツク数の直前且つ直後のブロツクを含
み、これにより直前のブロツク及び直後のブロツクもま
たアクセスされるようにするためである。この論理的な
ブロツク数とは、上のパラグラフに簡単に述べられた且
つ本明細書に更に詳細に述べられる後続のブロツクの２
進情報のためのアドレスがそれから得られるメモリ中の
位置の論理的数である。ヘツダを含む２進語の各グルー
プは、ハードデイスクメモリ86の512バイトブロツクの
メモリに記憶される。ハードデイスクメモリ86の各フア
イルはまた、このフアイルに関する管理情報を記憶する
ための多数の512バイトブロツクのメモリを用いてい
る。この管理情報は、とりわけ、デイスクメモリ中の関
連ドキユメント及び論理アドレスの識別を示している。

ハードデイスクメモリ86に記憶されるべきドキユメン
トを表わしている２進情報は、それぞれが16個の２進ビ
ツトからなる512個の２進語の多数のグループに分解さ
れる。斯かる16ビツト２進語のグループの各々は、ドキ
ユメントを表わす２進情報のための識別タグの１つの形
であるヘツダと結合し、これによりできるだけ512バイ
トに近い複合グループのデータを構成する。このヘツダ
はまた、メモリの隣接ブロツクの論理アドレスを含んで
いる。このシステムはまた、フアイルに関する管理情報
を記憶するための多数の512ブロツクのメモリを用いて
いる。この管理情報は、関連ドキユメントと及びこの情
報のための第１ブロツクのデータが記憶されているデイ
スクメモリ中の論理アドレスの名称を示している。更
に、ハードデイスクメモリに関する他の２進情報を記憶
するために他のブロツクのメモリがこのデイスクフアイ
ル管理システムによつて用いられる。他の２進情報と
は、例えば、各フアイルのうちどの位のメモリが用いら
れたかということ、各特定のフアイル中のどの位のメモ
リがまだ記憶するために用いられるかということ、本発
明の教示に従つてVTOCフアイルが自己拡張する時にこの
VTOCフアイルに加えられるべきハードデイスクの使用し
ていないメモリの増分量、及び任意のフアイルに割当て
られていないデイスクメモリスペースの量及び論理アド
レス等である。

スパース配列ビツトマツプ使用データベースの名称を
有する米国特許出願第490,814号が本明細書に参考とし
て引用されており、この特許出願は、データベース組織
に用いられる木構造を教示している。

第１図に示されるように、メモリの各ブロツクは、ヘ
ツダ20を有し且つインデツクスを記憶する目的のために
用いられる場合は、インデツクスブロツク30、あるいは
データを記憶する目的のために用いられる場合は、デー
タブロツク40のどちらかを含むために包括的に構成され
ている。ヘツダ20の組織の詳細については、第２図に示
されており、以下に述べられる。インデツクスブロツク
30の詳細については第３図に述べられており、以下に説
明される。データブロツク40の詳細については第４図に
示されており、以下に説明される。

第２図には、ヘツダ20内の２進データの組織が示され
ている。第２図に示されるように、ヘツダ20は、本明細
書に於て以下ブロツクセグメントと呼ばれるブロツク状
に配置されている４つの基本成分を有している。これら
のブロツクセグメントはまた、当業者によつてフイール
ドと呼ばれることもある。これらのブロツクセグメント
は、情報がブロツクのメモリに記憶されている組織即ち
順序を表わしている。ブロツクセグメント21は２バイト
即ち全部で16個の２進ビツトを含んでおり、このブロツ
クセグメント21は関連バイトブロツクのメモリに記憶さ
れている８ビツトバイトの数を示す２進数を記憶するの
に用いられる。これは本質的に、このシステムにこのブ
ロツクがどの位一ぱいになつているかを示している。こ
れは、このシステムがブロツクの空のバイト中のゼロを
読み出して２進語を有する情報と解釈しないようにする
ためである。全てのゼロがブロツクセグメント21に記憶
されると、デイスクフアイル管理システムに、このブロ
ツクはその中に何も記憶していない「空いて」いるブロ
ツクであることを示す。インデツクス又はデータ情報を
表わす２進情報の後続の記憶のために１つの「空き」ブ
ロツクが用いられる。ブロツクセグメント21に記憶され
ているこの２つの８ビツト２進語がそこに記憶されてい
る全てのゼロ以外のものを有する時は、このシステム
は、このブロツクがインデツクス又はデータ情報の記憶
のために用いられていることを知り、この場合は、この
ブロツクに記憶されているバイト数以外のその中に記憶
された２進数からの情報を得る。上に述べた目的のため
に最高順位ビツトの16ビツトが用いられる。この最高順
位のビツトがゼロである時は、システムは、このビツト
が読み出されるメモリのブロツクがインデツクスブロツ
クであることを知る。同様にして、この最高順位のビツ
トが１である場合、システムは、このビツトが読み出さ
れるメモリのブロツクがデータブロツクであることを知
る。

ブロツクセグメント22はまた、２つのバイト、即ち全
部で16個の２進ビツトを含んでおり、このブロツクセグ
メント22は、このヘツダが記憶されているメモリブロツ
クの論理ブロツク数を示す２つの８ビツト２進数を記憶
するのに用いられる。この論理ブロツク数はデイスクメ
モリ86に於ける論理アドレスであり、この論理ブロツク
数はメモリ中のブロツクを突き止めるのに用いられる。
次のブロツクセグメント23は、２つの８ビツトバイト、
即ち全部で16個の２進ビツトを含んでおり、このセグメ
ント23は、メモリ木構造に於て同一レベルにあるブロツ
クのメモリの論理ブロツク数を示す２進数を記憶するの
に用いられる。ヘツダ20中の最終のブロツクセグメント
は、これもまた２つのバイト、即ち全部で16個の２進ビ
ツトを含むブロツク24であり、このブロツク24は、関連
メモリ木構造に於て同一レベルにあるメモリの前のブロ
ツクの論理ブロツク数を示す２進数を記憶するのに用い
られる。ヘツダが取り付けられているメモリ86のブロツ
クが同一レベルにある第１ブロツクである場合、ブロツ
クセグメント24には全てのゼロが記憶されている。そう
でない場合は、同一レベルにあるメモリの先行するブロ
ツクの論理アドレスである２進数がそこに記憶される。
メモリ86に於けるデータの記憶に関する木構造に於ける
「レベル」の概念は、第７図の説明によつて更に理解さ
れる。今述べたヘツダ20は、ハードデイスクメモリ86に
於けるメモリのブロツクに記憶される２進語のグループ
に構成するためにインデツクス情報又はデータ情報の前
端に予め固定される。

第３図には、４つのブロツクセグメントからなるイン
デツクスブロツク30が示されている。ブロツクセグメン
ト31、32及び33は、１つ以上のブロツクのメモリに記憶
されるドキユメントの名称を記憶するのに用いられる。
しかし、この名称は圧縮された状態で記憶される。ブロ
ツクセグメント31は、共通キー長と呼ばれ、ブロツクセ
グメント32は、非共通キー長と呼ばれる。多数のドキユ
メントが記憶されているフアイル中には、インデツクス
ヘツダが英数字の順序で記憶されている。例えば、「ワ
ンド（WAND）」と呼ばれるドキユメントが既にハードデ
イスクメモリ86の与えられたフアイルに記憶されてお
り、このシステムは、「ワング（WANG）」と呼ばれる別
のドキユメントを同一のフアイルに記憶しようとしてい
ると仮定しよう。これらの２つのドキユメントの各々の
記憶は、インデツクスヘツダ20をブロツク30と共に且つ
データヘツダ20をデータブロツク40と共に記憶するため
の多数のメモリブロツクを必要とする。デイスクフアイ
ル管理システムは先ず、記憶されるべき新しいドキユメ
ントの名称「ワング」を見て次にこの「ワンド」ドキユ
メントのためのインデツクスヘツダ及びブロツクを突き
止める。このシステムは、最初の３つの数字WANがこれ
らの２つのドキユメントの間では共通であることを決定
する。従つて、この「ワング」ドキユメントに対するブ
ロツクセグメント31は、先行する「ワンド」フアイルと
共通する３つの文字「WAN」を示す３の共通キー長をそ
こに記憶している。非共通キー長と呼ばれるインデツク
スブロツク30のブロツクセグメント32には、「ワンド」
ドキユメントと「ワング」ドキユメントの間には１つの
英数字文字だけが異なつていることを示す２進数１が記
憶されている。次に、この１つの非共通文字「Ｇ」に対
する２進法表示がブロツクセグメント33に記憶される。
この様にして、ドキユメントの名称「ワング」が圧縮さ
れた状態で記憶され、従つて、このシステムはメモリ86
中のドキユメントを突き止めることができる。

更に例を挙げると、それぞれが、BOND、TEXT、TEST、
WANDの名称をもつ４つのドキュメントが当初メモリに記
憶されていると仮定する。また、これらのドキュメント
は、この順番に記憶されているとする。ここで、WANGの
名称を有するドキュメントがメモリに加えられるとする
と、メモリの内部は、次のようになる。31〜33は、ブロ
ックセグメントである。

次に、BAND、TOTE、MASTの名称のドキュメントが次の
リストのようにメモリ内に記憶されているとする。

このリストで見られるように、アルファベットの特定
の文字で始まる最初のドキュメントの名称を記憶するこ
とによつて、共通キー長はゼロとなり、非共通キー長は
その名称の中の文字の数となり、名称全体が非共通キー
長のブロックに記憶される。非共通キー長のセグメント
（33）の内容を、ブロック・セグメント（31）及び（3
1）との関係で検討すれば、データ・プロセッサは、ド
キュメントのアルファベット順のそれぞれのグループの
最初を容易に判断できるし（共通キー長＝０）、また、
アルファベット順に記憶されたドキュメントのそれぞれ
の（圧縮された）名称を認識できる。

インデツクスブロツク30中の４番目のブロツクセグメ
ントは、次ブロツク数Ｆ低レベルと呼ばれ、同一キー
（「ワング」）から始まる次の低いレベルのブロツクの
論理ブロツク数を示す。メモリ86に於けるデータの記憶
に関する木構造に於ける「レベル」の概念は、第７図の
説明によつてよりよく理解されよう。

第４図には、５個のブロツクセグメント41乃至45から
なるデータブロツク40が示されている。ブロツクセグメ
ント41、42及び43は、１つ以上のブロツクのメモリに記
憶されるドキユメントの名称を記憶するのに用いられ
る。しかしこの名称は圧縮された状態で記憶される。ブ
ロツクセグメント41は、共通キー長と呼ばれ、ブロツク
セグメント42は非共通キー長と呼ばれ、ブロツクセグメ
ント43は、非共通キー長と呼ばれる。これらのブロツク
セグメントは、上のインデツクスブロツク30の所で述べ
たブロツクセグメントと同等であるため、ここでは改め
て述べることはしない。データ長と呼ばれるブロツクセ
グメント44には、この特定のデータブロツク40に記憶さ
れているドキユメントの１部あるいは全てを表わしてい
るデータの２進語の数を示す２進数が記憶されている。
ブロツクセグメント45には、２進形式でドキユメントの
全て又は１部分を表わしている実際のデータが記憶され
ている。以下に更に詳しく述べる理由によつて、ブロツ
クセグメント45に記憶されている２進情報は基本的に二
重に記憶されている。即ち、データがデイスクメモリか
ら読み出されて編集される時は、ブロツクセグメント45
の半分から読み出されて、次に編集され、次にブロツク
セグメント45の他の半分に戻されて記憶される。データ
が読み出されて例えば編集される毎に、このデータが読
み出されるブロツクセグメント45の半分は交代する。斯
くして、このデータの直前のデータはデータの損失に備
えて節約され、これによりデータの全損失が防止され
る。前に述べたように、メモリの１つのブロツクに於け
る全ての８ビツトバイトは満たされない。これが、デー
タブロツク40の前端に付けられているヘツダ20のブロツ
クセグメント21に２進数、即ち“ブロツク中の使用バイ
トの数”を記憶することの目的である。

バージョン管理に関しては、本明細書の以下のブロッ
クセグメント51に関する記載の箇所で説明する。

このディスクファイル管理システムはまた、ディスク
上の全てのメモリブロックを、それらがファイルに割り
当てられているか否か及びそれらがインデクス、データ
ブロックあるいは空きブロックであるかどうかにかかわ
らず追跡するという管理タスクを有している。更に、デ
イスク上の各フアイルに関する管理情報も記載される。
これらの管理機能は、それ自身のVTOC（Volume Table o
f confents）フアイルを用いるデイスクフアイル管理シ
ステムによつて達成される。第５図、第６図及び第７図
は、このVTOCフアイルの組織を示しており、これらの図
面は以下に詳しく説明される。

デイスクフアイル管理システムに於て、VTOCフアイル
は前に述べた管理機能を達成する上で用いられるメモリ
の多数のブロツクである。これらのブロツクはインデツ
クス、データあるいはフリーブロツクとなり得るが、こ
れらは管理情報の損失に対するシステム・クラツシユ防
御を提供するためにバデイブロツク（buddy block）構
成に全て組織される。このバデイブロツク構成の場合、
１つのインデツクスブロツクあるいはメモリブロツクの
内容は本質的に二重にされ、隣接のメモリブロツクに記
憶される。VTOCフアイル中のバデイブロツクのメモリが
アクセスされると、記憶された情報即ちデータはこのバ
デイブロツクの最初の512バイト部分から読み出され、
編集等の処理をされ、修正された新しい情報即ちデータ
は次にメモリ中の同一のバデイブロツク対の第２の512
バイトブロツク部分に記憶される。この時点に於て、前
の情報即ちデータは、このバデイブロツク対の最初のブ
ロツク部分にあり、新しい情報即ちデータはこのバデイ
ブロツク対の第２のブロツク部分にある。情報即ちデー
タが読み出されて編集あるいは更新される次の時点で
は、この情報即ちデータはこのバデイブロツク対の第２
の部分から読み出され、更新された後、このバデイブロ
ツク対の最初の部分に記憶される。どの時点に於てもシ
ステムがクラツシユし且つ読み出されているあるいは読
み出されて来たデータが損失を得けるかあるいは破壊さ
れる場合、少なくとも前の情報即ちデータは依然として
存在する。

データブロツクを用いてVTOCフアイルに記憶される管
理データ・レコードには５つの型がある。それらは、1.
使用可能インデツクス・レコード、2.空きエクステント
・レコード、3.使用されたエクステントデータ・レコー
ド、4.連鎖レコード、及び5.属性データ・レコードであ
る。これらのデータ・レコードは各々、これらのブロツ
クが読み出される時にデイスクフアイル管理システムに
上に挙げられた型のブロツクを示す識別子をデータブロ
ツクに記憶している。

前に述べたように、VTOCフアイルを含むハードデイス
クメモリ上の全てのフアイルは、このフアイルにデータ
／情報を記憶するのに用いられる割当てられた512バイ
トブロツクのメモリを有しており、各フアイル中の割当
てられたメモリの空いている即ち未使用のブロツクのリ
ストが、データ即ち情報をフアイルに記憶するのに必要
になる時に、この割当てられたメモリのブロツクを選択
し且つ突き止める目的のために維持される。VTOCに割当
てられた空いている即ち未使用メモリブロツクのリスト
は以下に詳細に述べられるデータブロツクインデツクス
60a、60bに維持される。VTOCフアイル以外のものに割当
てられたブロツクのメモリに対しては、記録は以下によ
り詳細に述べられる使用されたエクステントデータ・レ
コードに維持される。

VTOCフアイル中の１つのブロツクのメモリが使用可能
インデツクスレコードであることをこのシステムが知る
ためには、使用可能インデツクス・レコードのデータブ
ロツク40のブロツクセグメント41、42及び43に記憶され
ている「キー」は次のように編成される。この「キー」
は値X₀₁であり、この後に開始インデツクス番号が続
く。このX₀₁は、このブロツクがVTOCフアイル中で得ら
れるインデツクス・レコードであることをこのシステム
に示し、これに対して、開始インデツクス番号は、フア
イル管理システムにフアイル識別名に割当てられ得る範
囲の数の初めを示す。即ち、１つのフアイルのASCII識
別名にはVTOCフアイルシステムに用いられた数値識別名
が割当てられる。

フアイル管理システムはまた、VTOCフアイルを含む如
何なるフアイルにも割当てられなかつた空いている即ち
未割当ブロツクを追跡する。これは、デイスクフアイル
管理システムが空いているメモリブロツクを突き止めて
この空きメモリブロツクを、ブロツクをさらに必要とし
自動的にこれを要求する如何なるフアイルにも割当てる
ことができるようにするように行なわれる。この空きメ
モリブロツク即ち未割当メモリブロツク情報は、空きエ
クステント・レコードを用いてVTOCフアイル中に維持さ
れる。実際のオペレーシヨンの場合は、この空いている
即ち未使用ブロツクのメモリは隣接ブロツクの可変サイ
ズ・グループ中のメモリに位置する。隣接メモリブロツ
クの斯かるグループの各々には空きエクステント・レコ
ードが用いられる。VTOCフアイル中のメモリの１ブロツ
クが空きエクステント・レコードであることをこのシス
テムが知るためには、データブロツク40のブロツクセグ
メント41、42及び43に記憶されている「キー」は次のよ
うに編成される。この「キー」は、値X₀₂であり、開始
ブロツク番号が後に続く。このX₀₂は、このブロツクが
空きエクステント・レコードであることをこのシステム
に示し、これに対し、この開始ブロツク番号は、この空
きエクステント・レコードが関連する隣接メモリブロツ
クの範囲に於けるメモリの最初のブロツクのメモリ中の
論理アドレスをフアイル管理システムに示す。このX₀₂
型「キー」に於ける開始ブロツク番号は、ブロツクセグ
メント41、42及び43の所で前に述べたように更に圧縮さ
れる前に初期的に圧縮され得る。X₀₂型空きエクステン
ト・レコードのデータブロツク40のブロツクセグメント
44にはある数が記憶されており、この数の値は、同一の
データブロツクのブロツクセグメント45に記憶されてい
るデータの量をシステムに示す。このブロツク数は、こ
のデータブロツクのブロツクセグメント45に記憶されて
いる数であり、この数は、この「キー」に於て識別され
た空きブロツクの範囲即ちエクステントに於ける最初の
空きメモリブロツクの論理アドレスに続くメモリブロツ
クの範囲に於けるメモリの空きブロツクの数をこのシス
テムに示す。このようにして、空きエクステント・レコ
ードによつて識別されたブロツクの範囲即ちエクステン
トに於けるメモリの最後の使用可能ブロツクが決定可能
である。インデツクス・レコードに於て識別されたメモ
リの幾つかが使用されるために選択された後データブロ
ツクセグメント45に記憶されている数はこの空きエクス
テント・レコードによつて網羅される残りの空いている
メモリのみを反映するように変化する。ブロツクセグメ
ント45に於ける使用可能数もまた圧縮され得る。

使用されたエクステントデータ・レコードは、ハード
デイスクメモリに於て論理的に互いに隣接している且つ
VTOCフアイルを除くこのデイスク上の任意のフアイルに
於けるメモリブロツクとして実際に用いられているメモ
リブロツクのエクステント即ち範囲に関する情報を記憶
するのに用いられる。この型の記録に対する「キー」
は、値X₀₃であり、この後にフアイル識別及びエクステ
ント識別が続く。このX₀₃は、VTOCフアイルを含むこの
デイスク上の任意のフアイルに於けるインデツクス即ち
データブロツクとして実際に用いられているメモリブロ
ツクのエクステント即ち範囲に関する情報を記憶するた
めにこのブロツクが用いられることをこのシステムに示
す。このフアイル識別は、このフアイルを識別する数で
あり、このフアイルのメモリブロツクの範囲は識別され
たフアイルと関連しており、使用可能インデツクス・レ
コードから得られ、連鎖レコードに記憶される。エクス
テント識別もまた、識別されたフアイル内のメモリブロ
ツクの範囲即ちエクステントの１つの数をこのシステム
に示す数である。即ち、各フアイルに於けるメモリブロ
ツクの各範囲即ちエクステントは、エクステント識別で
ある別々の数を有している。１つのフアイル中に５つの
範囲即ちエクステントがある場合、そのフアイルに対し
ては５つの使用されたエクステントデータ・レコードが
あり、その各々は「キー」のエクステント識別部に記憶
された数１乃至５を有している。任意のフアイル中の隣
接するメモリブロツクの範囲即ちエクステントの合計の
数は、本明細書に於て更に述べられるようにこの管理レ
コードのどこか他に記憶される。このX₀₃記録「キー」
に於けるフアイル識別及びエクステント識別は、ブロツ
クセグメント41、42及び43の所で前に述べたように更に
圧縮される前に、初期的に圧縮され得る。１つの使用さ
れたエクステント・レコードのデータブロツク40のブロ
ツクセグメント44に記憶された数は、開始ブロツク、及
びブロツク数を記憶するブロツクセグメント45に記憶さ
れている情報の量を示す。この開始ブロツクは、この使
用されたエクステント・レコードに関連するメモリブロ
ツクの範囲即ちエクステントに於ける最初の使用ブロツ
クのメモリの論理アドレスをこのシステムに示す数であ
り、このブロツク数は、このシステムがこの範囲に於け
る全てのブロツクの論理アドレスを決定できるようにす
るために、このメモリに於て互いに隣接しているブロツ
クの範囲即ちエクステントに於けるメモリブロツクの数
を示す数である。今述べた開始ブロツク及びブロツク数
もまた本明細書に教示されるように圧縮され得る。

連鎖レコードは、データブロツクに記憶される第４の
型のレコードであり、このレコードは、フアイル名、ラ
イブラリ記録に関する識別情報及びフアイル名、ライブ
ラリ記録に関する連鎖情報を記憶するのに用いられる。
即ち、上記の各々のASCII名と識別数の間には対応があ
り、この数がフアイル、ライブラリ及びドキユメントを
識別するために全てのVTOC記録にわたつて使用される。
フアイル又はライブラリあたりこれらの連鎖レコードが
１つ存在する。この型の記録に対するキーは、X₀₄であ
り、この後にノード識別及びノード名が続く。この値X
₀₄は、それが連鎖レコードであることをこのシステムに
示している。ノード識別は、記憶されたドキユメントが
その一部であるライブラリを識別する数である。ドキユ
メントがライブラリに記憶されていない場合、ゼロがこ
こに入る。このX₀₄記録「キー」に於けるノード識別
は、ブロツクセグメント41、42及び３の所で前に述べた
ように更に圧縮される前に、初期的に圧縮され得る。ノ
ード名は、この連鎖レコードが関連するフアイル、ライ
ブラリ又はドキユメントのASCII名である。前に述べた
ように、このデータブロツクのブロツクセグメント44に
は、同一ブロツクのブロツクセグメント45に記憶されて
いるデータの長さを示すデータ・レングス数が記憶され
ている。ブロツクセグメント45に記憶されているデータ
自身は、１つの数を上記のASCII識別に等しくするのに
用いられる。ブロツクセグメント45に記憶されているデ
ータは、１つのプレフイツクス（接頭部）であり、この
後に、デイレクトリ識別あるいはフアイル識別が続く。
このプレフイツクスは、この連鎖レコードがライブラリ
に割当てられている場合はX₀₀であり、連鎖レコードが
フアイルに割当てられている場合はX₀₁である。このX₀₀
あるいはX₀₁のどちらかの後には、上記のようにこのシ
ステムによつてASCII名に等しくされる割当てられた数
が続く。現時点に於てこのライブラリあるいはフアイル
をデイスクフアイル管理システムに対して識別する割合
て数は、属性又は範囲／エクステント記録に連鎖するの
に用いられ、且つ次のレベルのエレメントの位置を突き
止めるのに用いられる。この記録には後方の連鎖は何も
記憶されておらず、後方連鎖は、必要に応じてシステム
によつて引き出される。この識別数は、使用可能インデ
ツクス・レコードから割当てられる。データブロツク中
のデイレクトリ識別及びフアイル識別もまた圧縮され得
る。

第５の型のデータ・レコードは、属性データ・レコー
ドであり、このデータ・レコードはデータブロツクのキ
ー部に於て識別されるフアイル又はライブラリの属性情
報を記憶するのに用いられる。フアイル、ライブラリ及
びドキユメントに関する管理情報、例えば、フアイルの
作成者の名称、保護のクラス、作成された日附、修正さ
れた日附、フアイルに於て用いられるメモリブロツクの
数、及びフアイルに於ける使用可能なメモリブロツクの
数は、この型のデータ・レコードブロツクに記憶され
る。この型のデータレコードのキーには、値X₀₅があ
り、この後にはデイレクトリ識別あるいはフアイル識別
のどちらかが続き、次に属性識別が続く。このデイレク
トリ識別は、前に述べた連鎖レコードに於ける同一名の
フイールドに割当てられ且つ入力されたものと同一の数
であるデイレクトリ識別数あるいは、前に述べた連鎖レ
コードに於ける同一名のフイールドに割当てられ且つ入
力された同一数のフアイル識別数からなる。このX₀₅キ
ーに於て、デイレクトリ識別あるいはフアイル識別及び
属性識別は、前もつて圧縮され、次にブロツクセグメン
ト41、42及び43の所で前に述べたように圧縮される状態
で更に圧縮され得る。ブロツクセグメント44に記憶され
ているデータ長はデータブロツクのブロツクセグメント
45に記憶されているデータの長さである。ブロツクセグ
メント45には、この属性データ・レコードが関連するフ
アイル、ライブラリイあるいはドキユメントに関する、
上記及びその他の属性を識別する数である属性値が記憶
されている。この属性値情報も本明細書に教示されるよ
うに圧縮可能である。

第５図には、本明細書において前記したバデイ・ブロ
ツク対のオペレーシヨンを示す制御ブロツク50が示され
ている。前に述べたように、バデイ・ブロツクを用いる
と、デイスクフアイル管理システムの管理情報の損失に
対するシステムクラツシユ防御が行なわれる。ブロツク
60、53、54及び55は、バデイ・ブロツクとして用いら
れ、従つて、ブロツク60a及び60b、53a及び53b、54a及
び54b並びに55a及び55bとして示されている。このバデ
イブロツク構成の場合、１つのメモリブロツクの内容
は、完全に複写されており、別のメモリブロツクに記憶
されている。第５図のバデイブロツク54及び55の間の破
線は、デイスクフアイル管理システムの要求に応じて、
多数のバデイブロツク１乃至ｎが存在することを表わし
ている。使用され得るバデイブロツクの正確な数は、ブ
ロツクセグメント51に記憶されるバデイブロツクマツプ
内のビツトの数によつて制限されるだけである。このバ
デイブロツクマツプは次のパラグラフに述べられる。バ
デイブロツク53、54及び55として用いられるメモリのブ
ロツクは、必ずしもハードデイスクメモリ86に於て互い
に隣接して記憶されず、且つ、ブロツクセグメント51及
び52に用いられるメモリのブロツクに隣接して記憶され
る必要はない。ブロツクセグメント51乃至55並びに60
は、ハードデイスクメモリ86上のどこにあつてもよい。
更に、全てのバデイブロツクは、データ記憶に現在用い
られていないデータブロツク、インデツクスブロツクあ
るいは空きブロツクであり得る。全てのバデイブロツク
は、制御ブロツク50によつて表わされるように論理的に
のみ関連している。

ブロツクセグメント51は、メモリの512バイトのブロ
ツクであつて、VTOCフアイルに管理情報を記憶するバデ
イブロツクとしてデイスクフアイル管理システムによつ
て用いられるメモリの各ブロツクに対する１つの２進ビ
ツトを含むバデイブロツクマツプとして用いられる。バ
デイブロツク対の最初のブロツクである、メモリの１つ
のブロツクが直近の時点で書き込まれた部分である時
は、このブロツクマツプに於ける関連ビツトは、「１」
をその中に書き込んでいる。ここで銘記されるように、
バデイブロツクは１グループとして更新され、このバデ
イブロツクマツプ自体は、一連の記録更新の後にのみ更
新される。１つのバデイブロツク対の第１ブロツクが直
近の時点で書き込まれた部分である時は、このバデイブ
ロツクマツプに於ける関連ビツトは「０」をその中に書
き込んでいる。バデイブロツクを読み出す前に、デイス
クフアイル管理システムは最初にブロツクセグメント51
に於けるバデイブロツクマツプを調査し、このバデイブ
ロツク対のどのブロツクが最新の形の記憶データを有し
ているかを決定し、次にこの最新データを読み出す。読
み出されたデータが編集されあるいは他の処理を施され
た後、このデータは上記のようにこのバデイブロツク対
の他のブロツクに戻つて復元する。このバデイブロツク
マツプは、更新され、前のゼロは１に変化する。あるい
はその逆も同じである。このようにして、このシステム
は常に、１つのバデイブロツク対のどの部分が読み出さ
れるべき最新の材料を有しているかを知る。システムク
ラツシユがある場合は、データの完全な損失はない。管
理データの任意のデータの前の形は常に、バデイブロツ
ク対の１ブロツクに於て使用可能である。

制御ブロツク50に於けるブロツクセグメント60a及び6
0bは、バデイブロツク対であり、その中には、第６図に
於て更に詳細に示され且つ次のパラグラフに於てより詳
細に説明されるブロツクインデツクスが記憶されてい
る。前に述べられたように、バデイブロツク１乃至ｎを
表わすブロツクセグメント53乃至55はインデツクスブロ
ツク及びデータブロツクとして用いられ、あるいは管理
情報の記憶にまた用いられていない空きブロツクであり
得る。

第６図には、VTOCフアイルメモリブロツクを追跡する
管理タスクのためにデイスクフアイル管理システムによ
つて用いられるブロツクインデツクス60が示されてい
る。ブロツクインデツクス60を用いて達成される１つの
主な管理タスクは、VTOCフアイルに於いて空いている即
ち使用可能ブロツクのメモリの数を追跡することにあ
る。更に、ハードデイスクメモリ86上の各フアイルに関
する管理情報は、第５図に於てブロツクセグメント53乃
至55として示されているバデイブロツク１乃至ｎに記憶
されている。第６図に於て、ブロツクセグメントは表示
を簡単にするために二列で示されている。

ブロツクインデツクス60のブロツクセグメント61は、
それがVTOCフアイルの一部であることを識別するために
エントリ「1107VTOC」を含んでいる。ブロツクセグメン
ト62は、「バージヨン数」と呼ばれ、デイスクフアイル
管理システムの現在のバージヨンを識別するエントリを
含んでいる。ブロツクセグメント63は、「フアイル中の
ブロツクの数」と呼ばれ、現在VTOCフアイルに割当てら
れているデイスク上のメモリブロツクの数を識別する数
を含んでいる。ブロツクセグメント64は、「マツプ中の
ビツト数」と呼ばれ、ブロツクセグメント51に於けるバ
デイブロツクマツプのメモリのビツト数を示す数を含ん
でいる。この数は、各バデイブロツク対がこのバデイブ
ロツクマツプの中に１ビツトを有していなければならな
いためにVTOCフアイルに割当てられ得るバデイブロツク
対の最大数を示している。ブロツクセグメント65は、
「バデイブロツクの数」と呼ばれ、その中には、インデ
ツクス即ちデータ情報の記憶のためにまだ用いられてい
ないVTOCフアイルに割当てられたハードデイスクに於け
る空いている即ち使用可能メモリブロツクの数を示す数
が記憶されている。VTOCフアイルに割当てられた空きブ
ロツクが用いられると、ブロツクセグメント65に記憶さ
れた数が更新され、これによりVTOCフアイル中の空きメ
モリブロツクの現在の数を正しく反映する。ブロツクセ
グメント66は「拡張されたブロツク寸法」と呼ばれ、こ
の中には、このフアイルがそれに割当てられたメモリの
未使用のブロツクの殆んど全てを使用しそうになつた
時、ハードデイスクメモリ86上のVTOCフアイルに加えら
れるべき、如何なるフアイルにも割当てられていないメ
モリの未使用ブロツクの数を示す数が記憶されている。
これは、本発明を実施する際、即ちハードデイスクメモ
リ86上のVTOCフアイルの自己拡張をこのフアイルが満た
される時にする際用いられる。ブロツクセグメント67
は、「第１データブロツクのブロツク数」と呼ばれ、デ
ータを記憶するのに用いられるVTOCフアイルに於ける最
初のバデイブロツク対の位置を識別する論理アドレスで
ある。これは、第５図のバデイブロツク53乃至55の１つ
である。ブロツクセグメント68は、「第１空きブロツク
のブロツク数」と呼ばれ、VTOCフアイルにインデツクス
即ちデータを記憶するのに未使用のVTOCフアイルに於け
る最初の空きバデイブロツク対の位置を識別する論理ア
ドレスである。VTOCフアイルに於けるこれらの空きブロ
ツクは、最初の空きブロツクのアドレスを用いて、この
システムが全ての空きブロツクを見い出すことができる
ように共に連鎖される。ブロツクセグメント69は、「最
後の空きブロツクのブロツク数」と呼ばれ、VTOCフアイ
ルにインデツクス即ちデータを記憶するのに未使用のVT
OCフアイルに於ける最後の空きバデイブロツク対の位置
を識別する論理アドレスである。ブロツクセグメント69
には、フアイルに割当てられるように使用可能なブロツ
クの範囲の最後のブロツク数が記憶されている。ブロツ
ク68及び69に記憶されている数によつて、このシステム
はメモリの空きブロツクがハードデイスクメモリ86に於
てどの位の数存在し且つどこに位置しているかを知る。
ブロツクセグメント91は、「フアイルに於けるインデツ
クスレベルの数」と呼ばれ、VTOCフアイル構造に於ける
インデツクスレベルの数を識別する数である。これは第
７図を見るとよく理解される。第７図は、VTOCフアイル
に於けるインデツクスブロツク及びデータブロツクの例
示的な組織を示している。１つのブロツクメモリから読
み出されたデータをインデツクス又はデータであると正
しく解釈するためにインデツクスブロツクのレベルが幾
つあるかをデイスクフアイル管理システムが知るため
に、この情報がデイスクフアイル管理システムに必要に
なる。第７図には、二列のインデツクスブロツクがあ
る。第１の列、即ち上の列は根インデツクス記憶ブロツ
ク11を示し、これに対して２番目の即ち中間列は、２つ
のインデツクス記憶ブロツク12を示している。第１即ち
根レベルを除く木構造の各レベルには２つより多いブロ
ツクが存在し得る。この根インデツクス記憶ブロツク
は、計数されず、従つて斯かる例に対してブロツクセグ
メント91に記憶される数は数１である。根インデツクス
記憶ブロツクを含む３列のインデツクスブロツクがあつ
た場合は、数２が第６図のブロツクセグメント91に入
る。初期的には、即ちVTOCフアイルが大きくなる前に
は、根インデツクス記憶ブロツク11しかなくインデツク
ス記憶ブロツク12は存在せず、従つてブロツクセグメン
ト91に於ける数は上に与えられた例につきゼロとなる。

第６図に於けるブロツクインデツクス60の残りのブロ
ツクセグメントは、各々２つのブロツクセグメントから
なる組にまとめられる。ブロツクセグメント対92及び9
3、あるいは94及び95は、実例であり、反復される。即
ち、バデイブロツク対あるいはバデイブロツクマツプが
記憶されているメモリのブロツクの各エクステント即ち
範囲に対しては一対となつている。各対のブロツクセグ
メントの最初のブロツクセグメント92あるいは94は「ア
ドレスエクステントの最初のブロツク」と呼ばれ、その
中には、バデイブロツクマツプ及びバデイブロツク対が
記憶されている隣接ブロツクのメモリのエクステント即
ち範囲のハードデイスクメモリ86に於ける開始論理アド
レスが記憶されている。ブロツクセグメント93及び95は
「アドレスフアイルの長さ」と呼ばれ、ブロツクセグメ
ント92及び94の関連対に於けるアドレスから開始するバ
デイブロツクとして用いられる隣接メモリブロツクのエ
クステント即ち数を記憶するのに用いられる。VTOCフア
イリング構成にはこれらのバデイブロツク対が64のエク
ステントまで存在する。

第７図には、VTOCフアイリング構成に於けるインデツ
クスレコードとデータ・レコードとの相関関係及び連鎖
が示されている。これは基本的な木記憶構造である。こ
れらの記録は、ヘツダ20、インデツクスブロツク30、及
びデータブロツク40からなつている。これらのものは全
て前に述べられており、これらのインデツクス・レコー
ド及びデータ・レコードを形成するための基本的なエレ
メントである。木のトツプには、根インデツクス記憶ブ
ロツク11がある。VTOCフアイルに於ける任意のものを探
索するにあたり、デイスクフアイル管理システムはブロ
ツク11から開始しなければならない。最も単純な形の場
合、根インデツクス記憶ブロツク11は、１つのメモリ記
憶ブロツクに於けるヘツダ20及び１つのインデツクスブ
ロツク30からなる。これはこのブロツクのメモリを満た
さないので、第７図に示すようなインデツクスブロツク
30を１つ以上加えて拡張する余裕がある。この最も単純
な例の場合、ブロツク11に於けるヘツダ20のブロツクセ
グメント23及び24は、インデツクスブロツクが１つだけ
しかないためそこにゼロを記憶しており、木構造に於て
それと同一レベルにある他の論理ブロツクはあり得な
い。ブロツク11に於けるインデツクスブロツク30のブロ
ツクセグメント34に記憶された論理アドレスは、第７図
に示すような木構造に於ける第２層にある別のインデツ
クス記憶ブロツク12の代わりに、第７図の１つのデータ
記憶ブロツク13に直接指し示している。データ記憶ブロ
ツク13の数が大きくなると、中間インデツクス記憶ブロ
ツク12が必要になり、根インデツクス記憶ブロツク11内
のインデツクスブロツク30に於けるブロツクセグメント
34に記憶されている「次のブロツク数‐下位レベル」は
この最初の中間インデツクス記憶ブロツク12の論理アド
レスを有する。

中間インデツクス記憶ブロツク12の構成は、根インデ
ツクス記憶ブロツク11の構成と類似している。第２図に
示された型及び本明細書に於て前に述べられた型のヘツ
ダ20が存在し、第３図に示された同一型及び本明細書に
於て前に説明された同一型の多数のインデツクスブロツ
ク30が存在する。第７図に示す各データ記憶ブロツク13
に対しては中間レベルインデツクス記憶ブロツク12に於
てインデツクスブロツク30が存在する。各中間レベルイ
ンデツクス記憶ブロツク12は、１つのブロツクのメモリ
であり、そのメモリのブロツクを使いきるまでヘツダ20
及び多数のインデツクスブロツク30を記憶することがで
きる。この後、データブロツク40が更に形成されると、
そのメモリのブロツクを使いきるまで多数のインデツク
スブロツク30を他にまた取り扱うことのできる第２の中
間レベルインデツクス記憶ブロツク12が必要になる。し
かしながら、第２の中間レベルインデツクス記憶ブロツ
ク12に対しては、第７図に示すように別のインデツクス
30が「ブロツクＢに対するインデツクス」として根イン
デツクス記憶ブロツク11に必要になる。各々の付加的な
中間レベルインデツクス記憶ブロツク12に対しては、ブ
ロツク11の構成要素であるブロツクのメモリが満たされ
るまで別のインデツクス30が根インデツクス記憶ブロツ
ク11に必要になる。中間レベルインデツクス記憶ブロツ
ク12の場合、その中の各インデツクスブロツク30（１、
２乃至ｎ）に於て、「次のブロツク数‐下位レベル」と
呼ばれるブロツクセグメント34は、第７図に示すように
関連のデータブロツク40を指し示している論理アドレス
をそこに記憶している。例えば、インデツクス記憶ブロ
ツクＡ（12）に於けるインデツクスブロツクｎ（30）は
データ記憶ブロツク（13）に於けるデータブロツク（4
0）のインデキシングを与えている。各データ記憶ブロ
ツク13もメモリの１つのブロツクであり、満たされる
と、別のデータ記憶ブロツク13が更に記憶されるために
必要となる。各後続のブロツク13は、前のブロツク13と
後続のブロツク13に連鎖される。

VTOCフアイルメモリ木構造が第７図に示す例示的な形
である時、２つのインデツクス記憶ブロツク（12）即
ち、ブロツクＡ及びＢが存在する。これらはこの木構造
に於て同一中間レベルである。更に、第７図に示すよう
に、６つのデータ記憶ブロツク13が存在する。尚、この
内３つは１つのインデツクス記憶ブロツク12に関連し、
他の３つは他方のインデツクス記憶ブロツク12に関連し
ている。これらの６つのデータ記憶ブロツク12は、全て
記憶木構造に於て同一の下位レベルにある。１つより多
いメモリブロツクが木構造の中間レベル及び下位レベル
の各々にあるため、これらのブロツクの水平連鎖が必要
になる。この水平連鎖は、インデツクス記憶ブロツク12
とデータ記憶ブロツク13の両方の先頭にあるヘツダ20に
よつて行なわれる。第２図を見ると、インデツクス記憶
ブロツクＡ（12）の先頭にあるヘツダ20は、「同一レベ
ルにある次のブロツクの論理ブロツク数」と呼ばれるブ
ロツクセグメント23と「同一レベルにある前のブロツク
論理ブロツク数」と呼ばれるブロツクセグメント24を有
している。第７図に示す木構造に於ける中間レベルの場
合、インデツクス記憶ブロツクＡ（12）に於けるヘツダ
20のブロツクセグメント23は、インデツクス記憶ブロツ
クＢ（12）に対する論理ブロツク数をそこに記憶してい
る。前のインデツクス記憶ブロツク12が存在しないた
め、インデツクス記憶ブロツクＡ（12）に於けるヘツダ
20のブロツクセグメント24には全てのゼロが記憶され
る。斯くして、インデツクス記憶ブロツクＡ（12）は水
平レベルに於て前方にインデツクス記憶ブロツクＢ（1
2）と連鎖される。

同様にして、インデツクス記憶ブロツクＢ（12）は、
後方にインデツクス記憶ブロツクＡ（12）に対して連鎖
されるが、後続のブロツク12が存在しないため前方には
連鎖されない。より詳細に説明すると、インデツクス記
憶ブロツクＢ（12）に於けるヘツダ20のブロツクセグメ
ント23は、第７図に次の即ち後続のブロツク12が存在し
ないためそこに全てのゼロを記憶している。しかしなが
ら、インデツクス記憶ブロツクＢ（12）に於けるヘツダ
20のブロツクセグメント24は、後方連鎖を達成するため
にインデツクス記憶ブロツクＡ（12）の論理アドレスを
そこに記憶している。斯くして、インデツクス記憶ブロ
ツクＢ（12）は、水平レベルに於て後方にインデツクス
記憶ブロツクＡ（12）に対して連鎖される。

第７図に示される木構造の底のレベルに於て、全ての
データ記憶ブロツク13は、インデツクス記憶ブロツクと
同じように前方に及び後方に連鎖される。データ記憶ブ
ロツク13に対しては既に述べられているため詳細には立
ち入らないが、データブロツク１（50）は、後方連鎖を
有しておらず、しかしデータブロツク２（40）に対して
前方に連鎖される。データブロツク２（40）は、データ
ブロツクｎ（40）に対して前方に且つデータブロツク１
（50）に対して後方に連鎖される。最後に、データブロ
ツクｎ（40）は、前方には連鎖されないが、データブロ
ツク２（40）に対して後方に連鎖される。データブロツ
ク１、２及びｎは、データブロツクｎ＋１、ｎ＋２、及
びｎ＋Ｘに対しては全然連鎖されない。データブロツク
ｎ＋１、ｎ＋２、及びｎ＋Ｘは今述べたように、同様に
して前方に及び後方に互いに連鎖されるが、データ記憶
ブロツク１、２、及びｎに対しては連鎖されない。

本発明の教示による自己拡張フアイルの特徴を与える
ためのデイスクフアイル管理システムのオペレーシヨン
は、本明細書の説明の各所に記載され、従つてある特定
の場所には集中されていない。従つて、読者は本発明を
完全に理解するところまでは至つていないかもしれな
い。本発明をよりよく理解するために前に行なつた説明
から本発明の簡潔な復習を行うことにする。第６図のブ
ロツクインデツクス60のところでは、VTOCフアイルの排
他的使用に割当てられたメモリのブロツクの合計数がブ
ロツクセグメント63に記憶されている状態が述べられて
いた。ブロツクセグメント65には、データを記憶するの
にまだ用いられていなかつたVTOCフアイルに於けるメモ
リのブロツクの合計数が記憶されている。これらの２つ
の数の差はデータを記憶するのに既に用いられているVT
OCフアイルに於けるメモリのブロツクの数である。ブロ
ツクセグメント65に於て識別された空きメモリブロツク
の数が所定数を下回ると、デイスクフアイル管理システ
ムは、ブロツクセグメント66に記憶された数をとり、こ
れによりいかなるフアイルにも排他的に割当てられてい
ないメモリのブロツクの量を得てそれらをVTOCフアイル
に於ける排他的使用のために転送する。ブロツクセグメ
ント63及び65に記憶された数はこのようにして更新され
る。VTOCフアイルにおける排他的使用又はその他のフア
イルに対し転送するハードデイスクメモリ86上の使用可
能ブロツクを突き止めるために、デイスクフアイル管理
システムは、これまで述べてきた空きエクステント・レ
コードであつてその中にハードデイスクメモリ86上のメ
モリの空きブロツクの論理アドレス及び数量に関する情
報が記憶されている空きエクステント・レコードに進
む。VTOCフアイル以外のフアイルに対しては、各フアイ
ルに割当てられたメモリブロツクの数及びデータを各フ
アイルに記憶するのに既に用いられたメモリブロツクの
数を含む各特定のフアイルに関する情報が属性データ・
レコードに記憶されている。これらの２つの数の差は、
各特定のフアイルに割当てられた空きメモリブロツクの
残りの数である。このシステムがVTOCフアイルに割当て
られた空きブロツクの数も少なすぎると決定すると、フ
アイルの自己拡張が開始される。属性データ・レコード
には、そのメモリ容量が自己拡張される時にVTOCフアイ
ルに加えられるべきメモリのブロツクの数を示す数も記
憶されている。このシステムは、このエクステント数を
用い、前に述べられた空きエクステント・レコードに再
び進み、如何なる特定のフアイルにも排他的に割当てら
れていない空きメモリブロツクを識別する。これらの空
きブロツクの特定の数は、拡張されているフアイルの排
他的使用のために転送され、この空きエクステント・レ
コード及び属性データ・レコードは修正されて、特定フ
アイルの排他的使用のためのメモリのブロツクの転送を
反映する。

本明細書のあらゆる所に指摘されたように特定の情報
即ちデータが圧縮される。これらの例は、VTOCフアイル
に於て用いられた５つの型のレコードで特に指摘され
た。先行技術に於ては、特定データを記憶するための与
えられた量のスペースが割当てられるのが一般的であ
り、このスペースの量は融通性のないものであるため、
たとえ全てのスペースが必要でなくても、残りのスペー
スが浪費される。従つて、これらの硬直したブロツクセ
グメントに記憶された２進情報を圧縮する実際の必要性
は何ら存在しない。本発明の技術を用いると、この浪費
されたスペースは最小化され、ブロツクセグメントのビ
ツト又はバイトのサイズは未使用メモリスペースの量を
減らすために可変となつている。２進情報を記憶するの
に実際に必要となる量のメモリスペースのみが用いられ
ている。更に、記憶されるべき２進情報が圧縮される。
この圧縮を達成するために、デイスクフアイル管理シス
テムは任意の種類の情報を表わし得る、記憶されるべき
２進数を分析して、これにより４つの２進数のサイズの
範囲のどれにこの数が入るかを決定する。これらの範囲
は、ゼロ乃至63、64乃至16447、16448乃至4210751、及
び4210752乃至1077952575となっている。更に、デイス
クフアイル管理システムは、この数が入る上記の範囲に
応じて、記憶されるべき情報から与えられた数を減算す
る。ゼロ乃至63の最下位範囲に入る、記憶されるべき小
さい２進数字に対しては、この２進数からゼロが引か
れ、２つのビツト00がこの圧縮されない数の先頭に立
つ。プレフイツクス00を有する未圧縮数は、次に８ビツ
トバイトとして記憶される。後の時間に於て読み出され
る際に、デイスクフアイル管理システムは先ず最初の２
ビツトを読み出し、それらが00であることからこの数が
８ビツトとして記憶されたことを決定し、従つてそのま
ま読み出された２進数を即ちプレフイツクス00が引かれ
た数を用いる。

64乃至16447の次の範囲に入る、記憶されるべき少し
大きい２進数字に対しては、数量64がこの２進数字から
減算され、これによりこれを圧縮し、２つのビツト01が
圧縮された数の先頭に立つ。このプレフイツクス01を有
する圧縮数は、次に２つのビツトバイトとして記憶され
る。後の時点に於て読み出される際に、デイスクフアイ
ル管理システムは最初に、最初の２つのビツトを読み出
し、それらが01であることからこの数が量64を減算する
ことによつて圧縮されたことを決定し、次にこの量64を
読み出された数に戻して加えて、これにより圧縮プロセ
スを逆に行なう。次にこのシステムはプレフイツクス01
を引かれた圧縮を解かれた数を用いる。

16448乃至4210751の次の範囲に入る、記憶されるべき
更に大きな２進数に対しては、数量16448が２進数から
減算され、これによりこれを圧縮し、２つのビツト10が
圧縮数の先頭に立つ。このプレフイツクス10を有する圧
縮数は次に３つの８ビツトバイトとして記憶される。後
の時点に於て読み出される際、デイスクフアイル管理シ
ステムは先ず最初の２つのビツトを読み出し、それらが
10であることから数量16448を減算することによつてこ
の数が圧縮されたことを決定し、次にこの量を読み出さ
れた数に戻して加え、これによりこの圧縮プロセスを逆
に行なう。次にこのシステムはこのプレフイツクス10を
引いた圧縮を解かれた数を使用する。

4210752乃至1077952575の次の範囲に入る。記憶され
るように期待された最大の２進数に対しては、数量4210
752がこの２進数から減算され、これを圧縮し、２つの
ビツト11が圧縮数の前に置かれる。このプレフイツクス
11を有する圧縮数は次に、３つの８ビツトバイトとして
記憶される。後の時点に於て読み出される際、デイスク
フアイル管理システムは先ず最初の２つのビツトを読み
出し、それらが11であることから数量421052を減算する
ことによつてこの数が圧縮されたことを決定し、次にこ
の量を読み出された数に戻して加え、これによりこの圧
縮プロセスを逆にする。次にこのシステムは、プレフイ
ツクス11を引き圧縮を解かれた数を使用する。

上記の様式に従つて、デイスクフアイル管理システム
はまた、ハードデイスクメモリに記憶されるべき２進情
報を圧縮し、これによりそこに記憶できる情報を最大化
する。

今迄述べてきたのは本発明に係る好ましい実施例では
あるが、当業者にとつては、本発明の教示が本発明の精
神及び範囲から逸脱することなく多くの異なつた方法で
応用できることが明白である。例えば、本発明の自己拡
張フアイルは、与えられた量のメモリが特定の記憶機能
に割当てられる即ち専用される場合の如何なるメモリの
応用にも適用することができるが、特定のフアイリング
機能は時々付加的な量の専用メモリを必要とする。更
に、本明細書に教示されているデータ圧縮技術は殆んど
如何なるデータ記憶オペレーシヨンにも適用され得る。

【図面の簡単な説明】

第１図は、本発明を用いているデイスクフアイルシステ
ムに情報を記憶するのに用いられる一般的な記憶エレメ
ントの全体の組織図。第２図は、本発明を用いているデ
イスクフアイル管理システムを実施するのに用いられる
記憶エレメントのヘツダに対する情報の組織図。第３図
は、本発明を用いているデイスクフアイル管理システム
によつて用いられるインデツクス記憶エレメントのため
のヘツダと結合されるインデツクスブロツクの情報の組
織図。第４図は、本発明を用いているデイスクフアイル
管理システムによつて用いられるデータ記憶エレメント
を構成するためにヘツダと結合されるデータブロツクの
ための情報の組織図。第５図は、本発明を用いているデ
イスクフアイル管理システムフアイルの全体を表わす制
御ブロツク中の情報の組織図。第６図は、本発明を用い
ているフアイル管理システムによつて用いられる制御ブ
ロツク中のブロツクインデツクスの情報の組織図。第７
図は、本発明を用いているフアイル管理システム中のイ
ンデツクスとデータ記憶ブロツクとの相関関係を示す
図。第８図は、本発明を用いることができるハードデイ
スクメモリを含む計算機ベースシステムの略ブロツク
図。 20…ヘツダ、21…ブロツク中の使用バイトの数、22…こ
のブロツクの論理ブロツク数、23…同一レベルにある次
のブロツクの論理ブロツク数、24…同一レベルにある前
のブロツクの論理ブロツク数、30…インデツクスブロツ
ク又はデータブロツク、31…共通キー長、32…非共通キ
ー長、33…非共通キー値、34…次のブロツク数‐下位レ
ベル、40…データブロツク、41…共通キー長、42…非共
通キー長、43…非共通キー値、44…データ長、45…デー
タ、50…制御ブロツク、51…バデイブロツクマツプ、60
…ブロツクインデツクス、81、82…キーボード付ビデオ
端末装置、83…プロセツサ、85…メモリ、86…ハードデ
イスクメモリ、87…フロツピデイスクユニツト、88…プ
リンタ、89…通信インターフエース。

Claims

【特許請求の範囲】

【請求項１】データが多数の個別のメモリファイルの中
の適当なものに記憶され、各メモリファイルには該メモ
リファイルにデータを記憶するために該メモリファイル
で排他的に使用するある量のメモリブロックが割り当て
られている、というメモリ構成と共に用いられるメモリ
割当て方法であって、そのメモリ割当て方法を用いて、
どのメモリファイルにも割り当てられていないメモリブ
ロックを必要に応じて自動的にメモリファイルに割り当
てる、メモリ割当て方法において、どのメモリファイルにも割り当てられていないメモリブ
ロックに関する第１の記録をとるステップと、各メモリファイルで排他的に使用するために割り当てら
れているが未だデータの記憶のために使用されていない
メモリブロックに関する第２の記録をとるステップと、前記第２の記録を解析して、そのメモリファイルで排他
的に使用するために割り当てられたメモリブロックの中
で未使用のものの量が所定のレベルを下回っている第１
のメモリファイルを捜し出すステップと、どのメモリファイルにも割り当てられていないメモリブ
ロックに関する前記第１の記録において、前記第１のメ
モリファイルの排他的使用に供されるべきある量のメモ
リブロックを、その量が前記所定レベルを下回る場合に
は、捜し出すステップと、前記捜し出されたメモリブロックを前記第１のメモリフ
ァイルの排他的使用に供するステップと、を含んでおり、少なくとも前記第１の記録と前記第２の
記録とは複数のメモリブロックに重複して記憶され、更
に、前記第１の記録と前記第２の記録との完全な消失を
防止するための保護を提供するために、前記重複して記
憶されたメモリブロックの中の第１のメモリブロックと
第２のメモリブロックとに交互に書き込みを行って、ど
ちらのメモリブロックに最後に書き込みが行なわれたか
に関する記録を維持するステップを含むことを特徴とす
るメモリ割当方法。
【請求項２】特許請求の範囲第１項記載の方法におい
て、前記第１のメモリファイルの排他的使用に供される
べきメモリブロックの量を示す数を記憶するステップを
更に含むことを特徴とする方法。
【請求項３】特許請求の範囲第２項記載の方法におい
て、どのメモリファイルにも未だ割り当てられていない
メモリブロックの数が前記記憶された数に等しいメモリ
ブロックの量だけ減少したという事実を反映して、前記
捜し出されたメモリブロックが前記第１のメモリファイ
ルに供された後で、前記第１の記録を修正するステップ
を更に含むことを特徴とする方法。
【請求項４】特許請求の範囲第３項記載の方法におい
て、前記第１のメモリファイルに割り当てられたメモリ
ブロックの数が前記記憶された数に等しいメモリブロッ
クの量だけ増加したという事実を反映して、前記捜し出
されたメモリブロックが前記第１のメモリファイルに供
された後で、前記第２の記録を修正するステップを更に
含むことを特徴とする方法。
【請求項５】特許請求の範囲第４項記載の方法におい
て、前記個別のメモリファイルのそれぞれで排他的に使
用するために割り当てられたメモリブロックに関する第
３の記録をとるステップを更に含むことを特徴とする方
法。
【請求項６】特許請求の範囲第５項記載の方法におい
て、前記第１のメモリファイルに割り当てられたメモリ
ブロックの数が前記記憶された数に等しいメモリブロッ
クの量だけ増加したという事実を反映して、前記捜し出
されたメモリブロックが前記第１のメモリファイルに供
された後で、前記第３の記録を修正するステップを更に
含むことを特徴とする方法。
【請求項７】特許請求の範囲第１項記載の方法におい
て、前記第１のメモリファイルの使用に排他的に供され
るメモリブロックの中の未使用のものの数が前記所定レ
ベルを下回る場合には前記第１のメモリファイルのメモ
リブロックのサイズを拡張する要求信号を発生するステ
ップを更に含み、どのメモリファイルにも割当てられて
いないメモリブロックに関する前記第１の記録において
前記第１のメモリファイルの排他的使用に供されるべき
ある量のメモリブロックを捜し出す前記ステップが前記
発生された要求信号に応答して実行されることを特徴と
する方法。
【請求項８】特許請求の範囲第６項記載の方法におい
て、各メモリブロックは、供されたのであれば、そのメ
モリブロックがどのファイルに供されたのかに関する情
報を記憶する第１のスペースを有しており、更に、割り
当てられていないメモリブロックの前記量が前記第１の
メモリファイルでの排他的使用に供されるときに前記第
１のメモリファイルのアイデンティティを前記捜し出さ
れたメモリブロックの前記第１のスペースに書き込むス
テップを含むことを特徴とする方法。