JPH10283230A - ファイルデータ格納装置およびプログラムを記録した機械読み取り可能な記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 二次記憶装置上の記憶領域を複数のサイズの
ブロックに仕切り、複数のブロックサイズが混在した状
態で運用できるようにする。 【解決手段】 複数のブロックサイズを指定した構築指
示に従って、サイズ別空き領域確保手段１０２及び空き
領域管理情報構築手段１０３は、二次記憶装置２００上
にブロックサイズ別の空きブロックを確保し、各ブロッ
クサイズ別に空きブロックを管理する空き領域管理情報
を作成して二次記憶装置２００に記録する。運用時、フ
ァイルのデータ等を書き込むために空きブロックが必要
な場合、ブロックサイズ決定手段１０６は、書き込むべ
きデータに応じて必要なブロックサイズを決定し、空き
ブロック抽出手段１０７は、この決定されたブロックサ
イズの空きブロックを前記空き領域管理情報から抽出
し、ブロック割り当て手段１０８は、この抽出されたブ
ロックを、指定されたファイルの所属とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、二次記憶装置上に
論理ファイルを形成しデータを格納するファイルデータ
格納装置に関し、特に複数のブロックサイズによる運用
を可能とし、記憶領域の無駄を節約するファイルデータ
格納装置に関する。

【０００２】

【従来の技術】１つの二次記憶装置を、複数の仮想的な
記憶装置（論理ファイル、または単にファイル）として
見せるための機構として、ＵＮＩＸのファイルシステム
など様々なファイルデータ格納機構がある。なお、ＵＮ
ＩＸのファイルシステムに関する文献としては、例えば
「ＵＮＩＸカーネルの設計」共立出版や、「ＵＮＩＸ
４.3ＢＳＤの設計と実装」丸善や、「ＵＮＩＸ Ｉｎｔ
ｅｒｎａｌｓ：Ｔｈｅ Ｎｅｗ Ｆｒｏｎｔｉｅｒｓ」
Ｐｒｉｎｃｅ−Ｈａｌｌなどがある。

【０００３】これらのファイルデータ格納機構では、二
次記憶装置上の記憶領域をブロックと呼ばれる固定サイ
ズの区画に仕切り、各ブロックを各ファイルの記憶領域
として割り付けることにより、論理的な複数のファイル
を１つの二次記憶装置上に実現する。

【０００４】各ブロックのファイルへの割り付けを固定
的に決めると、各ファイルの容量が固定的に制限されて
しまう。そこで、ほとんどのファイルデータ格納機構で
は、各ブロックのファイルへの割り付けを動的に行って
いる。これにより、各ファイルの容量制限に自由度を持
たせ、全ファイルの容量の合計が全体の容量に制限され
るようにしている。

【０００５】各ブロックのファイルへの割り付けを動的
に行うため、ＵＮＩＸのファイルシステムなどでは、フ
ァイルに割り付けられていないブロックを空きブロック
として一括管理する。

【０００６】或るファイルにデータを格納する際に、必
要な数の空きブロックを獲得し、それらのブロックをそ
のファイルの所属として割り付ける。これにより、デー
タの格納のために必要な容量だけが、そのファイルに割
り付けられることになる。

【０００７】逆に、或るファイルに格納されているデー
タが必要なくなった際には、そのデータを消去するだけ
でなく、そのファイルの所属として割り付けられている
ブロックを解放し、空きブロックとしての一括管理に戻
す。

【０００８】以上により、二次記憶装置の容量を動的に
各ファイルに割り当てることができる。

【０００９】しかし、従来のファイルデータ格納機構で
は、ブロックのサイズを固定的に一定の値に決めること
しかできなかった。このことによる問題を以下に説明す
る。

【００１０】１つのファイルに格納できるデータ量を増
やすには、１つのファイルに割り付けるブロックの数を
増やす方法と、ブロックのサイズ自体を大きくする方法
がある。

【００１１】まず、１つのファイルに割り付けるブロッ
ク数を増やす場合を考える。この場合、各ファイルにど
のブロックが割り付けられているかなどを記録する管理
データ（ファイル管理データ）が増大し、ファイル中の
データにアクセスする際に、ファイル管理情報の参照が
増える。このため、ファイル中のデータにアクセスする
時間が長くなってしまうという問題がある。

【００１２】また、ファイルの管理情報が増大すると、
このファイル管理情報も二次記憶装置上に記録されるた
め、実際のデータを記録するための二次記憶装置の容量
がその分だけ減少することにもなる。

【００１３】次に、ブロックサイズを大きくした場合を
考える。大きなファイルのデータにアクセスする際に
は、管理情報の参照も少なく、二次記憶装置へのＩ／Ｏ
回数も減るため、アクセス時間は短縮される。

【００１４】しかし、小さいファイルのデータやファイ
ルの管理情報など、ブロックサイズと比較して小さなデ
ータでも同じサイズのブロックに格納されるため、ブロ
ックの一部にしか有効なデータが格納されず、記憶領域
が無駄になってしまうという問題がある。

【００１５】

【発明が解決しようとする課題】従来の技術における第
１の問題点は、ファイル中に格納できるデータ量の拡大
を、ブロック数の増大によって実現した場合、ファイル
の管理情報が増大し、ファイル中のデータへのアクセス
時間が長くなることにあった。

【００１６】更に、この場合、二次記憶装置中のファイ
ル管理情報の占める容量が増大し、その分だけ二次記憶
装置に記憶できる実際のデータ量が減少することも問題
であった。

【００１７】従来の技術における第２の問題点は、ファ
イル中に格納できるデータ量の拡大を、ブロックサイズ
の拡大によって実現した場合、小データも同じ大サイズ
のブロックに格納されるため、ブロックの一部しか記憶
のために有効に利用されず、大部分の記憶領域が無駄に
なるということにあった。

【００１８】そこで本発明の第１の目的は、ブロックの
サイズを複数用意し、書き込むデータに応じてブロック
サイズを使い分けることにより、巨大ファイルへの高速
アクセスを実現しながら、二次記憶装置上の記憶領域を
有効に利用し得るようにすることにある。

【００１９】また本発明の第２の目的は、複数のブロッ
クサイズについて、二次記憶装置上に占める記憶領域の
割合を動的に変更し得るようにして、記憶領域全体のよ
り一層の有効利用を可能とすることにある。

【００２０】

【課題を解決するための手段】本発明は、上記第１の目
的を達成するために、二次記憶装置上に複数の論理ファ
イルを構成するファイルデータ格納装置において、前記
二次記憶装置を制御する入出力制御部に、複数のブロッ
クサイズを指定した構築指示に従って、二次記憶装置上
にブロックサイズ別の空きブロックを確保し、かつ、各
ブロックサイズ別に空きブロックの情報を管理する空き
領域管理情報を作成して二次記憶装置に記録する構築部
と、二次記憶装置上に書き込むべきデータに応じて必要
なブロックサイズを決定するブロックサイズ決定手段
と、該ブロックサイズ決定手段で決定されたブロックサ
イズの空きブロックの情報を前記空き領域管理情報から
抽出する空きブロック抽出手段と、該空きブロック抽出
手段で抽出されたブロックを、指定されたファイルの所
属とするブロック割り当て手段と、ファイルに割り当て
られているブロックをそのファイルの所属から取り除く
ブロック解放手段と、該ブロック解放手段で解放された
ブロックの情報をそのブロックのブロックサイズに対応
する空き領域管理情報に登録する空きブロック登録手段
とを備えている。

【００２１】このように構成されたファイルデータ格納
装置においては、複数のブロックサイズを指定した構築
指示が与えられると、その構築指示に従って構築部が、
二次記憶装置上にブロックサイズ別の空きブロックを確
保し、かつ、各ブロックサイズ別に空きブロックの情報
（例えばブロック番号）を管理する空き領域管理情報を
作成して二次記憶装置に記録する。その後、実際の運用
が開始され、或るファイルのデータやファイル管理情報
などを記録するために空きブロックが必要になると、ブ
ロックサイズ決定手段が二次記憶装置上に書き込むべき
データに応じて必要なブロックサイズを決定し、空きブ
ロック抽出手段がこの決定されたブロックサイズの空き
ブロックの情報を前記空き領域管理情報から抽出し、ブ
ロック割り当て手段がこの抽出されたブロックを、指定
されたファイルの所属とする。また、或るファイルに所
属していたブロックが不要になった場合、ブロック解放
手段が、そのファイルに割り当てられているブロックを
そのファイルの所属から取り除き、空きブロック登録手
段がこの解放されたブロックの情報をそのブロックのブ
ロックサイズに対応する空き領域管理情報に登録する。

【００２２】また本発明は上記第２の目的をも達成する
ために、以下の空きブロック分割手段およびブロック結
合手段のうち少なくとも一方の手段を入出力制御部に備
えている。

【００２３】複数のブロックサイズのうち最小サイズ以
外のブロックサイズの空きブロックを抽出し、該抽出し
たブロックを該ブロックサイズより小さなブロックサイ
ズの空きブロックに分割する空きブロック分割手段。複
数のブロックサイズのうち最大サイズ以外のブロックサ
イズの空きブロックを複数個集めて、それより大きなブ
ロックサイズのブロック１個分に結合するブロック結合
手段。

【００２４】ブロックサイズ別のブロック数を固定にす
ると、実際の運用状態によっては特定のブロックサイズ
に利用が集中し、そのブロックサイズの空きブロックが
枯渇する恐れがある。このような場合、空きブロック分
割手段を備える構成にあっては、複数のブロックサイズ
のうち最小サイズ以外のブロックサイズの空きブロック
を抽出し、この抽出したブロックを該ブロックサイズよ
り小さなブロックサイズの空きブロックに分割するた
め、余っている大サイズの空きブロックを小サイズの空
きブロックに流用することができ、小サイズの空きブロ
ックの枯渇を防止することができる。他方、ブロック結
合手段を備える構成にあっては、複数のブロックサイズ
のうち最大サイズ以外のブロックサイズの空きブロック
を複数個集めて、それより大きなブロックサイズのブロ
ック１個分に結合するため、余っている小サイズの空き
ブロックを大サイズの空きブロックに流用することがで
き、大サイズの空きブロックの枯渇を防止することがで
きる。

【００２５】また別の発明にあっては、前記入出力制御
部に、各ブロックサイズ別の占有状況を管理するブロッ
クサイズ別占有率管理手段を備え、前記空きブロック分
割手段は、空きブロックの分割により各ブロックサイズ
別の占有状況が所定の条件を満たさなくなる場合には、
空きブロックの分割を行わない構成を有し、前記ブロッ
ク結合手段は、空きブロックの結合により各ブロックサ
イズ別の占有状況が所定の条件を満たさなくなる場合に
は、空きブロックの結合を行わない構成を有している。
これによって、ブロックサイズ別の記憶領域の占有率を
所望の範囲内に維持することができ、大きなサイズのブ
ロックの分割が際限なく繰り返されることにより、大き
なサイズのブロックが枯渇したり、その逆に、小さなサ
イズのブロックの結合が際限なく繰り返されることによ
り、小さなサイズのブロックが枯渇したりすることを防
止することができる。

【００２６】

【発明の実施の形態】次に本発明の実施の形態の例につ
いて図面を参照して詳細に説明する。

【００２７】図１は本発明のファイルデータ格納装置の
一実施例のブロック図である。この例のファイルデータ
格納装置は、磁気ディスク装置等で構成された二次記憶
装置２００と、これを制御する入出力制御部１００と、
記録媒体３００とから構成されている。

【００２８】入出力制御部１００は、本実施例の場合、
構築指示解析手段１０１と、サイズ別空き領域確保手段
１０２と、空き領域管理情報構築手段１０３と、ファイ
ル書き込み読み出し手段１０４と、キャッシュ１０５
と、ブロックサイズ決定手段１０６と、空きブロック抽
出手段１０７と、ブロック割り当て手段１０８と、ブロ
ック解放手段１０９と、空きブロック登録手段１１０と
を含んでいる。

【００２９】このような入出力制御部１００は、例えば
メモリおよび演算処理装置から構成されるデータ処理装
置で実現することができる。

【００３０】記録媒体３００は、磁気ディスク，半導体
メモリその他の記録媒体であり、ここに記録されたプロ
グラムは入出力制御部１００を構成するデータ処理装置
に読み込まれ、データ処理装置の動作を制御し、データ
処理装置を、上記各手段として機能させる。

【００３１】以下、本実施例の各部の機能をその全体の
動作を通じて説明する。

【００３２】一般にファイルデータ格納装置の運用を管
理する利用者を管理者と呼び、一般の利用者とは区別す
る。管理者は、ファイルデータ格納装置を一般の利用者
が利用できる状態としたり、運用中にファイルデータ格
納装置の記憶領域がどれほど使用されているかなどを監
視，管理する。

【００３３】二次記憶装置２００をファイルデータ格納
用として用いるために、管理者は、二次記憶装置２００
上にファイルデータ格納機構を構築する。この際、ブロ
ックのサイズをどれほどにするかなどの構成を決定して
おく。本発明においては、複数のブロックサイズが使用
できるため、管理者は、使用するブロックサイズを複数
種類決定する。使用する複数種類のブロックサイズは任
意であるが、本実施例では、最小のブロックサイズ以外
のブロックサイズが、最小サイズの整数倍となるように
決定しておく。

【００３４】管理者は、使用するブロックサイズを複数
種類決定すると、図示しないキーボード等の入力装置か
ら、それらのブロックサイズを指定した構築指示を入出
力制御部１００に投入する。構築指示は、例えばＵＮＩ
Ｘにおけるコマンドのような形で実現される。この場
合、ブロックサイズの指定は、コマンドのパラメータで
与えることができる。

【００３５】投入された構築指示は、構築指示解析手段
１０１で解析され、ブロックサイズの情報がサイズ別空
き領域確保手段１０２に伝達される。このサイズ別空き
領域確保手段１０２と後段の空き領域管理情報構築手段
１０３とで、二次記憶装置２００上にブロックサイズ別
の空きブロックを確保し、且つ各ブロックサイズ別に空
きブロックを管理する空き領域管理情報を作成して二次
記憶装置２００に記録する構築部が構成される。

【００３６】まず、サイズ別空き領域確保手段１０２
は、二次記憶装置２００上に各ブロックサイズ毎の空き
領域（空き容量）を確保する。その処理の一例を図２に
示す。

【００３７】サイズ別空き領域確保手段１０２は、構築
指示解析手段１０１から渡された複数のブロックサイズ
の内から最大のブロックサイズを取り出し（Ｓ１）、こ
の最大ブロックサイズで二次記憶装置２００上の記憶領
域を仕切って、各ブロックに一意な番号を割り付ける
（Ｓ２）。次に、各ブロックサイズに割り当てるべき空
き領域の割合を決定し、ステップＳ２で仕切ってできた
ブロックの総数から、各ブロックサイズ毎に割り当てる
べきブロック数を計算する（Ｓ３）。ここで、各ブロッ
クサイズに割り当てるべき空き領域の割合は予め静的に
決定しておく方法以外に、構築指示の１つのパラメータ
としてブロックサイズと共に指定する方法がある。

【００３８】例えば構築指示で指定されたブロックサイ
ズが、Ａ，Ｂ，Ｃの３種類であり、Ａが最も大きなサイ
ズで、次にＢが大きく、Ｃが最も小さいサイズとし、各
ブロックサイズに割り当てるべき領域の割合がＡ：Ｂ：
Ｃ＝４：５：３であった場合、二次記憶装置２００の記
憶領域をブロックサイズＡで仕切り、このとき例えば図
３に示すように合計１２個のブロックができたとする
と、図示するように二次記憶装置２００の先頭アドレス
（０）のブロックから順に、各ブロックに０，１，…，
１１と連続するブロック番号を割り付け、各ブロックサ
イズに割り当てるブロック数として同図（ｂ）に示すブ
ロック数を求める。なお、このような０から連続する番
号を割り付けることにより、ブロック番号にブロックサ
イズＡを乗じることで、そのブロックの先頭アドレスが
求まり、ブロック番号で各ブロックを一意に識別するこ
とができる。

【００３９】次に空き領域管理情報構築手段１０３は、
サイズ別空き領域確保手段１０２で仕切られてできた最
大サイズのブロックを、上記算出された各ブロックサイ
ズ毎の割り当てブロック数に従って個々のブロックサイ
ズ毎に割り振り、かつ最大サイズ以外のブロックサイズ
に割り振ったブロックは分割することにより当該ブロッ
クサイズの大きさにすると共に一意なブロック番号を割
り付ける。そして、各ブロックサイズ毎に、空きブロッ
クを管理する空き領域管理情報を作成して二次記憶装置
２００に記録する。その処理の一例を図４に示す。

【００４０】空き領域管理情報構築手段１０３は、サイ
ズ別空き領域確保手段１０２で仕切られてできた最大サ
イズのブロックの全ブロック番号を集合Ｕに入れ（Ｓ１
１）、まず最大のブロックサイズに注目する（Ｓ１
２）。そして、サイズ別空き領域確保手段１０２で決定
された最大ブロックサイズへの割り当て数に応じた数の
ブロック番号を集合Ｕから取り出し（Ｓ１３）、最大ブ
ロックサイズ用の空き領域管理情報を作成して二次記憶
装置２００に記録する（Ｓ１４）。

【００４１】次に、未処理のブロックサイズが残ってい
るか否かを調べ（Ｓ１５）、残っていれば、次にサイズ
の大きなブロックサイズに注目を移し（Ｓ１６）、集合
Ｕに含まれる各ブロック番号のブロックをＮ分割し、こ
の分割してできた個々のブロックの番号を計算し、集合
Ｕを一旦空にした後、その集合Ｕに今回計算したブロッ
ク番号の全てを格納する（Ｓ１７）。ここで、Ｎは、次
式に示す値である。 Ｎ＝直前に注目していたブロックサイズ／現在注目しているブロックサイズ …（１）

【００４２】そして、サイズ別空き領域確保手段１０２
で決定された当該ブロックサイズへの割り当て数に応じ
た数のブロック番号を集合Ｕから取り出し（Ｓ１３）、
当該ブロックサイズ用の空き領域管理情報を作成して二
次記憶装置２００に記録する（Ｓ１４）。

【００４３】他方、ステップＳ１５で未処理のブロック
サイズが残っていないと判断したときは、処理を終了す
る。

【００４４】空き領域管理情報構築手段１０３の動作
を、図３を参照して説明すると以下のようになる。

【００４５】先ず、ブロック番号０〜１１を集合Ｕに入
れる（Ｓ１１）。最大ブロックサイズＡに注目し（Ｓ１
２）、それに割り当てるべきブロック数「４」に応じ
て、集合Ｕから４つのブロック番号を取り出す（Ｓ１
３）。ブロック番号は先頭から順に取り出しても良い
し、ランダムに取り出しても良い。今の場合、ブロック
番号０，１，２，３を取り出したとする。次に、最大ブ
ロックサイズＡ用の空き領域管理情報を作成し、二次記
憶装置２００に記録する（Ｓ１４）。ここで、最大ブロ
ックサイズＡ用に作成した空き領域管理情報は、このブ
ロックサイズＡ用に割り当てた何れか１つまたは複数の
ブロックに格納する。

【００４６】次に、ブロックサイズＢに注目を移し（Ｓ
１６）、Ｎ＝ブロックサイズＡ／ブロックサイズＢ＝２
とすると、集合Ｕに含まれる各ブロック番号４〜１１の
ブロックを図３（ｃ）に示すように２等分し、個々のブ
ロック番号を以下のように計算して、集合Ｕに格納する
（Ｓ１７）。 分割後のブロック番号＝分割前のブロック番号×Ｎ＋ｎ …（２） 但し、ｎ＝０，…，（Ｎ−１）

【００４７】従って、分割後の各ブロックの番号は図３
（ｃ）に付記したようになる。ここで、分割後のブロッ
ク番号にブロックサイズＢを乗じると、そのブロックの
先頭アドレスが求まるため、各ブロック番号が各ブロッ
クを一意に識別する情報となる。

【００４８】そして、サイズ別空き領域確保手段１０２
で決定されたブロックサイズＢの割り当てブロック
「５」に応じて、最大サイズのブロック数にして５個、
当該ブロックサイズＢのサイズにして５×２、つまり１
０個のブロック番号を集合Ｕから取り出す（Ｓ１３）。
この取り出しも先頭から順であってもランダムであって
も良い。ここでは、ブロック番号８〜１７の１０個が取
り出されたとする。次に、ブロックサイズＢ用の空き領
域管理情報を作成し、二次記憶装置２００に記録する
（Ｓ１４）。ブロックサイズＢ用に作成した空き領域管
理情報も、このブロックサイズＢ用に割り当てた何れか
１つまたは複数のブロックに格納する。

【００４９】次に、ブロックサイズＣに注目を移し（Ｓ
１６）、Ｎ＝ブロックサイズＢ／ブロックサイズＣ＝２
とすると、集合Ｕに含まれる各ブロック番号１８〜２３
のブロックを図３（ｄ）に示すように２等分し、個々の
ブロック番号を前記式（２）で計算して、集合Ｕに格納
する（Ｓ１７）。従って、分割後の各ブロックの番号は
図３（ｄ）に付記したようになる。ここで、分割後のブ
ロック番号にブロックサイズＣを乗じると、そのブロッ
クの先頭アドレスが求まるため、各ブロック番号が各ブ
ロックを一意に識別する情報となる。

【００５０】そして、サイズ別空き領域確保手段１０２
で決定されたブロックサイズＣの割り当てブロック
「３」に応じて、最大サイズのブロック数にして３個、
当該ブロックサイズＣのサイズにして３×２×２、つま
り１２個のブロック番号を集合Ｕから取り出す（Ｓ１
３）。この場合、集合Ｕに格納されている全てのブロッ
ク番号３６〜４７が取り出される。次に、ブロックサイ
ズＣ用の空き領域管理情報を作成し、二次記憶装置２０
０に記録する（Ｓ１４）。ブロックサイズＣ用に作成し
た空き領域管理情報も、このブロックサイズＣ用に割り
当てた何れか１つまたは複数のブロックに格納する。

【００５１】図５は上述したサイズ別空き領域確保手段
１０２および空き領域管理情報構築手段１０３の具体例
による動作の模式図である。図５において、１０２１は
サイズ別空き領域確保手段１０２が最大ブロックサイズ
に対して割り当てたブロック番号の集合を示し、１０３
１，１０３２，１０３３は空き領域管理情報構築手段１
０３が各ブロックサイズＡ，Ｂ，Ｃに対して割り当てた
最大ブロックサイズのブロック番号の集合を示す。１０
３４はブロックサイズＡ用の空き領域管理情報であり、
二次記憶装置２００上の例えばブロック番号０のブロッ
クに格納される。１０３５は、ブロックサイズＢに割り
当てられた最大サイズのブロックをブロックサイズＢに
分割して得た個々のブロックのブロック番号の集合であ
り、１０３６はブロックサイズＢ用の空き領域管理情報
で、二次記憶装置２００上の例えばブロック番号８のブ
ロックに格納される。１０３７は、ブロックサイズＣに
割り当てられた最大サイズのブロックをブロックサイズ
Ｃに分割して得た個々のブロックのブロック番号の集合
であり、１０３８はブロックサイズＣ用の空き領域管理
情報で、二次記憶装置２００上の例えばブロック番号３
６，３７のブロックに跨がって格納される。

【００５２】図６は各ブロックサイズＡ，Ｂ，Ｃへのブ
ロックの別の割り当て例を示す。この例は、各ブロック
サイズＡ，Ｂ，Ｃのブロックを二次記憶装置２００中に
散在させて割り当てた例を示す。

【００５３】図７は個々のブロックサイズ用の空き領域
管理情報の構成例とその二次記憶装置への格納例とを示
す図である。この例の空き領域管理情報は空きブロック
のブロック番号のリストである。空きブロック数が多い
場合、リスト長はそれに比例して長くなる。前述したよ
うに空き領域管理情報も二次記憶装置２００上のブロッ
クに記録されるため、リスト長の長い空き領域管理情報
は複数のブロックに跨がって記録される。この場合、リ
ストは複数のリスト部分に分割されて各ブロックに記録
される。このとき、各ブロックに格納されるリスト部分
の先頭には次のリスト部分が記録され、リスト自体が鎖
構造となる。なお、先頭のリスト部分を格納するブロッ
クの番号は、例えば、割り当て，解放の対象とならない
特定のブロックに記録されて管理される。このような空
き領域管理情報は、前述したように各ブロックサイズ毎
に１つずつ用意され、各々のブロックサイズのブロック
を１つまたは複数使って二次記憶装置２００に記録され
る。

【００５４】以上がファイルデータ格納機構の構築時の
動作である。以下、運用時の各手段の機能とその動作と
を説明する。

【００５５】ファイルデータ格納機構の構築時には、二
次記憶装置２００上のブロックは管理情報を格納するブ
ロック以外は全て空き領域となっている。この状態から
利用者が或るファイルに対してデータの書き込みなどを
行っていく。

【００５６】図１のファイル書き込み読み出し手段１０
４は、上位装置（例えば中央処理装置）からの要求に従
ってファイルの書き込み，読み出しなどを司る部分であ
る。或るファイルにデータを書き込む場合、そのファイ
ルの管理情報や実際のデータを格納するための空きブロ
ックが必要となる。ファイル書き込み読み出し手段１０
４は、空きブロックが必要になると、ブロックサイズ決
定手段１０６に対して、その空きブロックを使うファイ
ル名などの情報を渡して空きブロックの要求を出す。

【００５７】ブロックサイズ決定手段１０６は、二次記
憶装置２００上に書き込むべきデータに応じて必要なブ
ロックサイズを決定する。ブロックサイズを決定する基
準には幾つかの実現例が考えられる。

【００５８】１つの例は、書き込まれるデータの種類に
応じて固定的にブロックサイズを決定してしまう方法で
ある。二次記憶装置２００に書き込むデータには、利用
者が書き込みを要求したデータ以外に、ファイルの管理
情報などの管理情報があり、ファイルの管理情報などは
情報量が比較的少ないため小サイズのブロックで足りる
からである。このような方法を実施する場合は、空きブ
ロックの要求時に、ファイル書き込み読み出し手段１０
４はそのブロックに書き込もうとしているデータの種類
をブロックサイズ決定手段１０６に通知する。ブロック
サイズ決定手段１０６はこのデータの種類を確認し、そ
れに応じてどのブロックサイズを使用するかを決める。

【００５９】別の１つの例は、書き込まれるデータのサ
イズに応じてブロックサイズを決める方法である。ファ
イルの管理情報などはデータのサイズがほぼ固定してい
るので前述の方法でも有効であるが、利用者が要求する
書き込みデータはサイズに大きなバラツキがあるため、
有効でない。書き込まれるデータのサイズに応じてブロ
ックサイズを決定すれば、このような問題は解消され
る。この方法を実施する場合、空きブロックの要求時
に、ファイル書き込み読み出し手段１０４はそのブロッ
クに書き込もうとしているデータのサイズをブロックサ
イズ決定手段１０６に通知する。ブロックサイズ決定手
段１０６は、複数用意されたブロックサイズから、過不
足のないブロックサイズを選択する。

【００６０】さて、ブロックサイズ決定手段１０６でブ
ロックサイズが決定されると、ファイル書き込み読み出
し手段１０４から渡されたファイル名と共にそのブロッ
クサイズが空きブロック抽出手段１０７に通知される。
空きブロック抽出手段１０７は、通知されたブロックサ
イズの空きブロックを１つ抽出し、その後段のブロック
割り当て手段１０８は、この抽出された空きブロック
を、通知されたファイル名のファイルの所属とし、制御
をファイル書き込み読み出し手段１０４に戻す。ファイ
ル書き込み読み出し手段１０４は、このファイルの所属
となった空きブロックに対してデータの書き込みを行
う。

【００６１】次に、空きブロック抽出手段１０７および
ブロック割り当て手段１０８の動作を説明するが、本実
施例の入出力制御部１００は処理の高速化を図るために
キャッシュ１０５を有しており、このキャッシュ１０５
に管理情報の一部をキャッシングするようにしている
為、まず、キャッシュ１０５について説明しておく。

【００６２】図８は、キャッシュ１０５に格納される情
報の例を示す。この例では、二次記憶装置２００を大ブ
ロックと小ブロックの２種類のブロックサイズで使用し
ており、その為に空き領域管理情報は大ブロック用と小
ブロック用との２種類ある。キャッシュ１０５には、そ
の各々の空き領域管理情報の一部（先頭のリスト部分）
がキャッシングされる。同様に、現在２つのファイル
α，βが生成されているとすると、その各々のファイル
の管理情報が二次記憶装置２００に記録されているた
め、キャッシュ１０５には、各ファイルの管理情報の一
部がキャッシングされる。

【００６３】さて、空きブロック抽出手段１０７の処理
例を説明する。図９にその処理例を示す。空きブロック
抽出手段１０７は、ブロックサイズ決定手段１０６から
ブロックサイズが指定されると、この指定されたブロッ
クサイズの空き領域管理情報の先頭のリスト部分がキャ
ッシュ１０５上に無ければ、そのリスト部分を二次記憶
装置２００からキャッシュ１０５上に読み込み（Ｓ２
１，Ｓ２２）、ステップＳ２３へ進む。先頭のリスト部
分が既にキャッシュ１０５上に存在すれば、ステップＳ
２２をスキップしてステップＳ２３へ進む。なお、指定
されたブロックサイズの空き領域管理情報が存在しない
場合、そのブロックサイズの空きブロックが１つも無い
ことになる。この場合の対処としては、例えば別のサイ
ズの空きブロックで代用する等の方法が採用できる。

【００６４】次に先頭のリスト部分が空か否か、つまり
リスト部分が次のリスト部分を含むブロックのブロック
番号を格納するエントリだけで空きブロックの番号を格
納したエントリが１つもないか否かを判定し（Ｓ２
３）、空でなければ、そのリスト内のブロック番号を１
つ取り出し、そのエントリをクリアし、取り出したブロ
ック番号を空きブロック番号としてブロック割り当て手
段１０８に通知し（Ｓ２４）、処理を終える。

【００６５】他方、リスト部分が空であった場合、当該
リスト部分が書き込まれていた二次記憶装置２００上の
ブロックのブロック番号を内部に一時的に記録し（Ｓ２
５）、次のリスト部分があればそれを二次記憶装置２０
０からキャッシュ１０５上に読み込み（Ｓ２６）、上記
記録しておいたブロック番号を空きブロック番号として
ブロック割り当て手段１０８に通知し（Ｓ２７）、処理
を終える。図１０はこのときの動作の模式図である。前
述したように或るブロックサイズ用の空き領域管理情報
はそのブロックサイズのブロックに格納してあるため、
空き領域管理情報を格納するブロックが空きになったと
きそれを空きブロックとして利用するわけである。

【００６６】次にブロック割り当て手段１０８の動作に
ついて説明する。図１１にその処理例を示す。ブロック
割り当て手段１０８は、空きブロック抽出手段１０７か
らブロック番号とその所属させるべきファイルとが指定
されると、指定されたファイルの管理情報がキャッシュ
１０５上に無ければ、そのファイルの管理情報を二次記
憶装置２００からキャッシュ１０５上に読み込み（Ｓ３
１，Ｓ３２）、ステップＳ３３へ進む。そのファイルの
管理情報が既にキャッシュ１０５上に存在すれば、ステ
ップＳ３２をスキップしてステップＳ３３へ進む。ステ
ップＳ３３では、キャッシュ上のファイルの管理情報に
対し、割り当てるブロックの番号を、ブロックサイズと
の関係がわかる形で記録する（Ｓ３３）。ここで、ブロ
ックサイズとの関係がかわる形で記録する方法の例とし
ては、ブロック番号と共にブロックサイズを記録する方
法や、ファイル管理情報内で各ブロックサイズ別にブロ
ック番号が区分けされている場合には、該当する場所に
ブロック番号を記録する方法などがある。

【００６７】以上のようにしてファイル書き込み読み出
し手段１０４は、空きブロックのブロック番号を取得
し、そのブロック番号から計算で求まる二次記憶装置２
００上のアドレスに存在する空きブロックに対してデー
タの書き込みを行う。データの書き込みが行われたブロ
ックは、前述したように該当ファイルの管理下に所属し
ており、そのファイルの管理情報によって、該当ファイ
ルのどのデータがどのブロックサイズのどのブロックに
書かれているかが管理されるため、当該データの読み出
しを行うことができる。

【００６８】次に、ファイルのデータが利用者にとって
必要なくなった場合の動作について説明する。この場
合、該当するブロック中のデータを消去するだけでな
く、データが空になった空きブロックを二次記憶装置２
００上の空き領域として管理しなければならない。そこ
で、ブロック解放手段１０９によって該当するブロック
をファイルの管理下から除去し、更に、この空きブロッ
クを、空きブロック登録手段１１０によって、二次記憶
装置２００上の空き領域としての管理下に戻す。これに
より、データ消去されたブロックは空きブロックとして
管理され、別のデータ書き込みに際して再利用すること
ができる。以下、ブロック解放および空きブロック登録
について説明する。

【００６９】ファイルデータを消去する際、ファイル書
き込み読み出し手段１０４は、該当するデータを含むブ
ロックのブロック番号，その所属するファイル名および
ブロックサイズをブロック解放手段１０９に指定し、そ
の解放を要求する。ブロック解放手段１０９はこれに応
じて当該ブロックを解放する処理を行う。

【００７０】図１２にブロック解放手段１０９の処理の
一例を示す。ブロック解放手段１０９は、ファイル書き
込み読み出し手段１０４から指定されたファイルの管理
情報がキャッシュ１０５上に無ければ、そのファイルの
管理情報を二次記憶装置２００からキャッシュ１０５上
に読み込み（Ｓ４１，Ｓ４２）、ステップＳ４３へ進
む。そのファイルの管理情報が既にキャッシュ１０５上
に存在すれば、ステップＳ４２をスキップしてステップ
Ｓ４３へ進む。ステップＳ４３では、キャッシュ１０５
上のファイルの管理情報から、解放するブロックのブロ
ック番号をクリアし、空きブロック登録手段１１０に対
してそのブロック番号およびブロックサイズを通知す
る。

【００７１】ブロック解放手段１０９によって解放され
たブロックは、空きブロック登録手段１０８によって、
空きブロックとしての一括管理下に戻される。図１３に
空きブロック登録手段１１０の処理例を示す。空きブロ
ック登録手段１１０は、解放ブロックのブロックサイズ
用の空き領域管理情報の先頭のリスト部分がキャッシュ
１０５上に無ければ、そのリスト部分を二次記憶装置２
００からキャッシュ１０５上に読み込み（Ｓ５１，Ｓ５
２）、ステップＳ５３へ進む。先頭のリスト部分が既に
キャッシュ１０５上に存在すれば、ステップＳ５２をス
キップしてステップＳ５３へ進む。

【００７２】次に先頭のリスト部分が一杯か否か、つま
りリスト部分の全エントリが使用されており、当該リス
ト部分を格納するブロックに新たなブロック番号を登録
するエントリがないか否かを判定し（Ｓ５３）、一杯で
なければ、そのリスト内のエントリに解放ブロックのブ
ロック番号を登録する（Ｓ５４）。

【００７３】他方、キャッシュ上のリスト部分が一杯で
あった場合、当該リスト部分を、解放ブロックの二次記
憶装置２００の位置に書き出し（Ｓ５５）、キャッシュ
上のリスト部分をクリアし、前記書き出したリスト部分
を格納したブロックのブロック番号を、リスト部分の先
頭に設定した空のリスト部分をキャッシュ上に生成し、
そのリスト内のエントリに解放ブロックのブロック番号
を登録する（Ｓ５６）。図１４はこのときの動作の模式
図である。前述したように或るブロックサイズ用の空き
領域管理情報の各リスト部分はそのブロックサイズのブ
ロックに格納してあるため、キャッシュ上のリスト部分
が一杯になったときそれを格納する空きブロックとし
て、今回解放の対象となったブロックを利用するわけで
ある。

【００７４】なお、指定されたブロックサイズの空き領
域管理情報が存在しない場合、そのブロックサイズの空
きブロックが現在１つも存在しないことを意味する。こ
のときは、今回の解放ブロックを空き領域管理情報の先
頭のリスト部分を格納するブロックとして使用する。

【００７５】図１５は本発明のファイルデータ格納装置
の別の実施例のブロック図である。この例のファイルデ
ータ格納装置が図１の実施例のファイルデータ格納装置
と相違するところは、入出力制御部１００に、空きブロ
ック分割手段１１１とブロックサイズ別占有率管理手段
１１２とを付加した点にある。先の実施例と同様に入出
力制御部１００は例えばメモリおよび演算処理装置から
構成されるデータ処理装置で実現することができ、記録
媒体３００に記録されたプログラムが入出力制御部１０
０を構成するデータ処理装置に読み込まれ、データ処理
装置の動作を制御し、データ処理装置を、各手段として
機能させる。

【００７６】図１の実施例のファイルデータ格納装置に
あっては、二次記憶装置２００上に占める各ブロックサ
イズ毎の領域の割合が、データ構造構築の時点で固定的
に決まってしまうため、小さなブロックサイズの空きブ
ロックが足りなくなると、それより大きなブロックサイ
ズの空きブロックがいくら余っていても、それ以上デー
タを二次記憶装置２００に書き込むことができないか、
大きなブロックサイズの空きブロックで代用する必要が
ある。

【００７７】これを避けるためには、想定される二次記
憶装置２００の利用状況を踏まえて、データ構造構築時
に、各ブロックサイズに対してどのような割合で領域を
確保するかを綿密に計画する必要がある。このため、想
定される利用状況を決定することができない様々な利用
方法に対応することができない。

【００７８】そこで、本実施例では、小さなブロックが
足りなくなると大きなブロックを分割して利用し、ブロ
ックサイズ毎の割合を柔軟に変化させる。以下、図１の
実施例との相違点を中心に本実施例の動作を説明する。

【００７９】ブロックサイズ別占有率管理手段１１２
は、各ブロックサイズ別の占有状況を管理している。こ
れは例えば、各ブロックサイズ別にそのブロック総数を
保持することで管理される。各ブロックサイズのブロッ
ク総数の初期値は、データ構造の構築時における各ブロ
ックサイズ毎の空きブロック総数である。以後、ブロッ
クサイズ別占有率管理手段１１２は、空きブロック分割
手段１１１からの通知に従って、各ブロックサイズ別の
ブロック総数を増減し、常に最新の占有状況を管理す
る。

【００８０】空きブロック分割手段１１１は、本実施例
の場合、入出力制御部１００の空き時間などを利用し
て、定期的に空き領域管理情報を参照し、複数のブロッ
クサイズのうち最大サイズ以外のブロックサイズの空き
ブロックが予め定められた数以下になっているか否か、
即ち不足しているか否かを調べ、若し不足している場合
には、より大きなブロックサイズの空きブロックを分割
して、不足しているブロックサイズの空きブロックを新
たに生成する。

【００８１】図１６に空きブロック分割手段１１１の処
理例を示す。まず、不足しているブロックサイズより１
つサイズの大きなブロックサイズを選択する（Ｓ６
１）。次に、前記選択したブロックサイズ用の空き領域
管理情報を参照して、その空きブロック数が予め定めら
れた数以上あるか否か、即ち充分な数だけ残っているか
否かを調べる（Ｓ６２）。若し、充分な数だけ残ってい
なければ、それを使用すると、今度はそのブロックサイ
ズの空きブロック数が不足することになるので、処理を
断念する。

【００８２】１つサイズの大きなブロックサイズの空き
ブロック数が充分ある場合、ブロックサイズ別占有率管
理手段１１２で保持されている現在の占有状況を参照
し、空きブロックの分割により各ブロックサイズ別の占
有状況が所定の条件を満たさなくなるか否かを判定し
（Ｓ６３）、満たさなくなる場合は処理を断念する。

【００８３】１つサイズの大きなブロックサイズの空き
ブロック数が充分あり、且つ、空きブロックを分割して
も各ブロックサイズ別の占有状況が所定の条件を満足す
る場合、空きブロック分割手段１１１は、空きブロック
抽出手段１０７にそのブロックサイズを指定して空きブ
ロックの抽出を要求する（Ｓ６４）。このときの空きブ
ロック抽出手段１０７の動作は、要求元がブロックサイ
ズ決定手段１０６の代わりに空きブロック分割手段１１
１となり、抽出したブロック番号をブロック割り当て手
段１０８に通知する代わりに空きブロック分割手段１１
１に通知する点が異なるだけで、その処理は図９と実質
的に同じである。

【００８４】次に空きブロック分割手段１１１は、空き
ブロック抽出手段１０７から通知されたブロック番号か
ら、そのブロック番号のブロックを不足ブロックサイズ
で分割したときの個々のブロックのブロック番号を、例
えば以下の式で計算する（Ｓ６５）。 分割後のブロック番号＝分割前のブロック番号×Ｎ＋ｎ …（４） 但し、Ｎ＝（分割前のブロックのサイズ）／（分割後の
ブロックのサイズ ｎ＝０，…，（Ｎ−１） この式（４）は空き領域管理情報構築手段１０３がデー
タ構造構築時に用いた前記（２）式と同じである。

【００８５】次に空きブロック分割手段１１１は、上記
計算したＮ個のブロック番号を空きブロック登録手段１
１０に通知して、不足ブロックサイズの空き領域管理情
報への登録を要求する（Ｓ６６）。このときの空きブロ
ック登録手段１１０の動作は、要求元がブロック解放手
段１０９の代わりに空きブロック分割手段１１１となる
点が異なるだけで、その処理は図１３と実質的に同じで
ある。そして、空きブロック分割手段１１１は、ブロッ
クサイズ別占有率管理手段１１２に対し、分割したブロ
ックサイズのブロック数を１だけ減じ、分割によってで
きたブロックサイズのブロック数をＮだけ増加するよう
に指示する（Ｓ６７）。

【００８６】図１７は空きブロック分割手段１１１の上
述したような動作を模式的に示している。

【００８７】なお、本実施例では、以下のような各種の
変形が可能である。

【００８８】不足ブロックサイズの１つ上のサイズの空
きブロック数が充分でなかった場合、またはブロックサ
イズ別占有状況が所定の条件を満たさない場合、処理を
断念せず、更に上のサイズの空きブロック数，それを分
割した場合のブロックサイズ別占有状況を調べ、分割可
能ならばそれを分割して充当する。

【００８９】不足ブロックサイズより大きなサイズが複
数存在する場合、ブロック総数の多いブロックサイズを
優先的に分割対象とする。

【００９０】空きブロック抽出手段１０７がブロックサ
イズ決定手段１０６からの要求により該当ブロックサイ
ズの空きブロックを抽出しようとしたときに、当該ブロ
ックサイズの空きブロックが１つも存在しなかった場合
に、空きブロック抽出手段１０７からそのブロックサイ
ズを指定して空きブロック分割手段１１１を起動し、空
きブロック分割手段１１１によって生成された空きブロ
ックを空きブロック抽出手段１０７が抽出するようにす
る。

【００９１】図１８は本発明のファイルデータ格納装置
の更に別の実施例のブロック図である。この例のファイ
ルデータ格納装置が図１５の実施例のファイルデータ格
納装置と相違するところは、入出力制御部１００に、ブ
ロック結合手段１１３と連続ブロック検出手段１１４と
を付加した点にある。先の実施例と同様に入出力制御部
１００は例えばメモリおよび演算処理装置から構成され
るデータ処理装置で実現することができ、記録媒体３０
０に記録されたプログラムが入出力制御部１００を構成
するデータ処理装置に読み込まれ、データ処理装置の動
作を制御し、データ処理装置を、各手段として機能させ
る。

【００９２】図１５の実施例のファイルデータ格納装置
にあっては、大きなブロックを分割して複数の小さなブ
ロックとして使用することにより、小さなブロックの枯
渇は防止できた。しかし、その反対の、大きなブロック
の枯渇は防止できない。

【００９３】そこで、本実施例では、大きなサイズのブ
ロックが足りなくなる前に、小さなサイズの空きブロッ
クを結合して大きなサイズの空きブロックを生成する。
このとき、複数個の小さなサイズの空きブロックを無作
為に抽出しただけでは大きなサイズの１個のブロックに
は結合できない。小さな空きブロックを大きな空きブロ
ックとして結合するためには、連続する小さな空きブロ
ックが必要な数だけあって、それらの小さな空きブロッ
クが大きなブロック１個の中に納まらなければならない
からである。そこで、連続ブロック検出手段１１４によ
って、最大サイズのブロックサイズ以外の各ブロックサ
イズ毎に、より大きなサイズのブロックに結合し得るだ
け空きブロックが連続しているか否かを検出し、連続し
ている場合に、ブロック結合手段１１３がそれらを結合
する。以下、図１５の実施例との相違点を中心に本実施
例の動作を説明する。

【００９４】ブロック結合手段１１３は、本実施例の場
合、入出力制御部１００の空き時間などを利用して、定
期的に空き領域管理情報を参照し、複数のブロックサイ
ズのうち最小サイズ以外のブロックサイズの空きブロッ
ク数が予め定められた数以下になっているか否か、即ち
不足しているか否かを調べ、若し不足している場合に
は、より小さなブロックサイズの空きブロックを複数個
結合して、不足しているブロックサイズの空きブロック
を新たに生成する。

【００９５】図１９にブロック結合手段１１３の処理例
を示す。まず、不足しているブロックサイズより１つサ
イズの小さなブロックサイズを選択する（Ｓ７１）。次
に、前記選択したブロックサイズ用の空き領域管理情報
を参照してその空きブロック数が予め定められた数以上
あるか否か、即ち充分な数だけ残っているか否かを調べ
る（Ｓ７２）。若し、充分な数だけ残っていなければ、
それを使用すると、今度はそのブロックサイズの空きブ
ロック数が不足することになるので、処理を断念する。

【００９６】１つサイズの小さなブロックサイズの空き
ブロック数が充分ある場合、ブロックサイズ別占有率管
理手段１１２で保持されている現在の占有状況を参照
し、空きブロックの結合により各ブロックサイズ別の占
有状況が所定の条件を満たさなくなるか否かを判定し
（Ｓ７３）、満たさなくなる場合は処理を断念する。

【００９７】１つサイズの小さなブロックサイズの空き
ブロック数が充分あり、かつ、空きブロックを結合して
も各ブロックサイズ別の占有状況が所定の条件を満足す
る場合、ブロック結合手段１１３は、（不足ブロックサ
イズ）／（当該ブロックサイズ）＝Ｎだけ連続している
当該ブロックサイズの空きブロックのブロック番号を、
連続ブロック検出手段１１４を用いて検出する（Ｓ７
４）。

【００９８】連続ブロック検出手段１１４の処理例を図
２０に示す。まず、キャッシュ１０５および二次記憶装
置２００に存在する当該ブロックサイズの空き領域管理
情報を参照して、Ｎの値でちょうど割り切れるブロック
番号のブロックを先頭とするＮ個連続する空きブロック
の有無を調べる（Ｓ８１）。ここで、Ｎは、前述した
（当該ブロックサイズの１つ上のブロックサイズ）／
（当該ブロックサイズ）である。このような連続空きブ
ロックが存在すれば（Ｓ８２）、それらのブロック番号
をその空き領域管理情報から取り除く（Ｓ８３）。これ
により、当該ブロックサイズではそのブロック番号のブ
ロックは空きブロックではなくなる。そして、それらの
ブロック番号をブロック結合手段１１３に通知する（Ｓ
８４）。他方、連続した空きブロックが存在しなければ
（Ｓ８２）、検出失敗をブロック結合手段１１３に通知
する（Ｓ８５）。

【００９９】ブロック結合手段１１３は、Ｎ個連続する
空きブロックの検出に失敗した場合、処理を断念する
（Ｓ７５）。他方、その検出に成功した場合は、検出さ
れたＮ個のブロック番号から結合後のブロックの番号
を、例えば次式によって計算する（Ｓ７６）。 結合後のブロック番号＝［結合前の何れかのブロック番号／Ｎ］ …（５） 但し、Ｎは、（当該ブロックサイズの１つ上のブロック
サイズ）／（当該ブロックサイズ） ［ ］は除算結果の整数部分をとることを意味する。こ
の式（５）は空き領域管理情報構築手段１０３がデータ
構造構築時に用いた前記（２）式と逆の関係を求める式
である。

【０１００】そしてブロック結合手段１１３は、上記計
算したブロック番号を指定して空きブロック登録手段１
１０に登録を要求する（Ｓ７７）。このときの空きブロ
ック登録手段１１０の動作は、要求元がブロック解放手
段１０９の代わりにブロック結合手段１１３となる点が
異なるだけで、その処理は図１３と実質的に同じであ
る。これにより、複数の小さな空きブロックが１つの大
きな空きブロックとして使用可能となる。そして、ブロ
ック結合手段１１３は、ブロックサイズ別占有率管理手
段１１２に対し、結合元のブロックサイズのブロック数
をＮだけ減じ、結合によってできたブロックサイズのブ
ロック数を１だけ増加するように指示する（Ｓ７８）。

【０１０１】次に、連続ブロック検出手段１１４が連続
性検出を容易に行えるような空き領域管理情報の構成例
について説明する。

【０１０２】空き領域管理情報が図７で説明したように
空きブロック番号の単なるリストでも、より大きなサイ
ズに結合できる連続する空きブロックを検出することは
可能であるが、処理に時間がかかってしまう。そこで、
本例では、最大サイズのブロックサイズ用以外の空き領
域管理情報を図２１に示すようなマトリックス構造とす
る。

【０１０３】マトリックスの各列には、［（ブロック番
号）／Ｎ］の値が等しいブロック番号を並べる。但し、
Ｎ＝（１つ上のブロックサイズ）／（当該ブロックサイ
ズ）である。また、マトリックスの各行には、（ブロッ
ク番号）ｍｏｄ Ｎ の値が等しいブロック番号を並べ
る。ここで、ｍｏｄは、左項を右項で割った余りを求め
る演算子である。

【０１０４】空き領域管理情報が上述のようなマトリッ
クス構造である場合、マトリックスの１列が満たされて
いれば、その列に含まれる複数のブロック番号のブロッ
クが１つ上のブロックサイズ１個分のブロックに結合で
きることになるため、連続ブロック検出手段１１４はそ
のような列を検出すれば良い。

【０１０５】また、空き領域管理情報を上述のようなマ
トリックス構造とした場合、空きブロック登録手段１１
０では、或るブロック番号を登録する際、［（ブロック
番号）／Ｎ］の値を求め、等しい値を持つ列を探して挿
入する列を決定する。このとき、若し、等しい値の列が
存在しない場合には、空の列を挿入する。更に、（ブロ
ック番号）ｍｏｄ Ｎ の値を求め、挿入する列を決定
する。

【０１０６】なお、本実施例では、以下のような各種の
変更が可能である。

【０１０７】ブロック結合手段１１３において、不足ブ
ロックサイズの１つ下のサイズの空きブロック数が充分
でないか、ブロック結合によりブロックサイズ別占有状
況が所定の条件を満たさなくなるか、結合に必要な連続
空きブロックが存在しない場合、直ちに処理を断念せ
ず、更に下のサイズについて、空きブロック数が充分
か、ブロック結合によりブロックサイズ別占有状況が所
定の条件を満足するか、結合に必要な連続空きブロック
が存在するかを調べ、何れも満足する場合に、それを分
割して充当する。

【０１０８】不足ブロックサイズより小さなサイズが複
数存在する場合、ブロック総数の多いブロックサイズを
優先的に結合対象とする。

【０１０９】空きブロック分割手段１１１とブロック結
合手段１１３とを合わせ持っているので、中間のブロッ
クサイズの空きブロックの不足時、双方の手段が動作す
る可能性がある。これを防止するために、空きブロック
分割手段１１１とブロック結合手段１１３とで各々使用
できる総空きブロック数，占有状況などの前提条件を比
較し合い、より最適な側の手段が動作するようにする。

【０１１０】空きブロック分割手段１１１を省略し、ブ
ロック結合手段１１３だけでブロック数の動的変更を行
わせる。

【０１１１】空きブロック抽出手段１０７がブロックサ
イズ決定手段１０６からの要求により該当ブロックサイ
ズの空きブロックを抽出しようとしたときに、当該ブロ
ックサイズの空きブロックが１つも存在しなかった場合
に、空きブロック抽出手段１０７からそのブロックサイ
ズを指定してブロック結合手段１１３を起動し、ブロッ
ク結合手段１１１で生成された空きブロックを空きブロ
ック抽出手段１０７が抽出するようにする。このときも
前述と同様に中間のブロックサイズの不足時には空きブ
ロック分割手段１１１を用いる方法と、ブロック結合手
段１１３を用いる方法との２通りの方法があるため、そ
の調整を行う。

【０１１２】以上、本発明について幾つかの実施例を挙
げて説明したが、本発明は前述した実施例に限られず、
その要旨の範囲内で様々な付加変更が可能である。例え
ば、図１の実施例におけるブロック番号の計算例は図１
５および図１８の実施例にも適用できる例を示したが、
図１の実施例では、データ構築時に生成されたブロック
番号が運用中に変更されることはないため、上述した例
に限られず、ブロックサイズ毎に一意であれば任意のブ
ロック番号を割り当てることができる。また、各ブロッ
クを識別するための情報はブロック番号以外の任意の情
報を使用することができる。

【０１１３】

【発明の効果】以上説明したように本発明によれば以下
のような効果を得ることができる。

【０１１４】複数のブロックサイズが混在した運用が行
え、書き込むデータに応じてブロックサイズを使い分け
ることができるので、巨大ファイルへの高速アクセスを
実現しながら、二次記憶装置上の記憶領域を有効に利用
することができる。

【０１１５】空きブロック分割手段を備えた構成にあっ
ては、運用中に小さなブロックサイズの空きブロックが
不足しても、動的に大きなブロックサイズの空きブロッ
クを分割して振り分けることにより、その枯渇を防止で
き、二次記憶装置の記憶領域をより一層有効に利用する
ことができる。

【０１１６】ブロック結合手段を備えた構成にあって
は、運用中に大きなブロックサイズの空きブロックが不
足しても、動的に小さなブロックサイズの空きブロック
を結合することにより、その枯渇を防止でき、二次記憶
装置の記憶領域をより一層有効に利用することができ
る。

【０１１７】ブロックサイズ別占有率管理手段を備えた
構成にあっては、ブロックサイズ別の記憶領域の占有状
態を所定の条件を満たす範囲内で、ブロック分割，ブロ
ック結合を行わせることができる。

【図面の簡単な説明】

【図１】本発明のファイルデータ格納装置の一実施例の
ブロック図である。

【図２】サイズ別空き領域確保手段の処理の一例を示す
フローチャートである。

【図３】サイズ別空き領域確保手段および空き領域管理
情報構築手段の動作説明図である。

【図４】空き領域管理情報構築手段の処理の一例を示す
フローチャートである。

【図５】サイズ別空き領域確保手段および空き領域管理
情報構築手段の具体例による動作の模式図である。

【図６】各ブロックサイズへのブロックをランダムに割
り当てる例を示す図である。

【図７】個々のブロックサイズ用の空き領域管理情報の
構成例とその二次記憶装置への格納例とを示す図であ
る。

【図８】キャッシュに格納される情報の説明図である。

【図９】空きブロック抽出手段の処理例を示すフローチ
ャートである。

【図１０】空きブロック抽出手段の動作説明図である。

【図１１】ブロック割り当て手段の処理例を示すフロー
チャートである。

【図１２】ブロック解放手段の処理の一例を示すフロー
チャートである。

【図１３】空きブロック登録手段の処理例を示すフロー
チャートである。

【図１４】空きブロック登録手段の動作説明図である。

【図１５】本発明のファイルデータ格納装置の別の実施
例のブロック図である。

【図１６】空きブロック分割手段の処理例を示すフロー
チャートである。

【図１７】空きブロック分割手段の動作説明図である。

【図１８】本発明のファイルデータ格納装置の更に別の
実施例のブロック図である。

【図１９】ブロック結合手段の処理例を示すフローチャ
ートである。

【図２０】連続ブロック検出手段の処理例を示すフロー
チャートである。

【図２１】マトリックス構造の空き領域管理情報の例を
示す図である。

【符号の説明】

１００…入出力制御部 １０１…構築指示解析手段 １０２…サイズ別空き領域確保手段 １０３…空き領域管理情報構築手段 １０４…ファイル書き込み読み出し手段 １０５…キャッシュ １０６…ブロックサイズ決定手段 １０７…空きブロック抽出手段 １０８…ブロック割り当て手段 １０９…ブロック解放手段 １１０…空きブロック登録手段 １１１…空きブロック分割手段 １１２…ブロックサイズ別占有率管理手段 １１３…ブロック結合手段 １１４…連続ブロック検出手段 ２００…二次記憶装置

Claims (7)

【特許請求の範囲】
1. 【請求項１】 二次記憶装置上に複数の論理ファイルを
   構成するファイルデータ格納装置において、 前記二次記憶装置を制御する入出力制御部に、 複数のブロックサイズを指定した構築指示に従って、二
   次記憶装置上にブロックサイズ別の空きブロックを確保
   し、かつ、各ブロックサイズ別に空きブロックの情報を
   管理する空き領域管理情報を作成して二次記憶装置に記
   録する構築部と、 二次記憶装置上に書き込むべきデータに応じて必要なブ
   ロックサイズを決定するブロックサイズ決定手段と、 該ブロックサイズ決定手段で決定されたブロックサイズ
   の空きブロックの情報を前記空き領域管理情報から抽出
   する空きブロック抽出手段と、 該空きブロック抽出手段で抽出されたブロックを、指定
   されたファイルの所属とするブロック割り当て手段と、 ファイルに割り当てられているブロックの情報をそのフ
   ァイルの所属から取り除くブロック解放手段と、 該ブロック解放手段で解放されたブロックをそのブロッ
   クのブロックサイズに対応する空き領域管理情報に登録
   する空きブロック登録手段とを備えることを特徴とする
   ファイルデータ格納装置。
2. 【請求項２】 前記入出力制御部に、複数のブロックサ
   イズのうち最小サイズ以外のブロックサイズの空きブロ
   ックを抽出し、該抽出したブロックを該ブロックサイズ
   より小さなブロックサイズの空きブロックに分割する空
   きブロック分割手段を備えることを特徴とする請求項１
   記載のファイルデータ格納装置。
3. 【請求項３】 前記入出力制御部に、各ブロックサイズ
   別の占有状況を管理するブロックサイズ別占有率管理手
   段を備え、前記空きブロック分割手段は、空きブロック
   の分割により各ブロックサイズ別の占有状況が所定の条
   件を満たさなくなる場合には、空きブロックの分割を行
   わない構成を有することを特徴とする請求項２記載のフ
   ァイルデータ格納装置。
4. 【請求項４】 前記入出力制御部に、複数のブロックサ
   イズのうち最大サイズ以外のブロックサイズの空きブロ
   ックを複数個集めて、それより大きなブロックサイズの
   ブロック１個分に結合するブロック結合手段を備えるこ
   とを特徴とする請求項１記載のファイルデータ格納装
   置。
5. 【請求項５】 前記入出力制御部に、各ブロックサイズ
   別の占有状況を管理するブロックサイズ別占有率管理手
   段を備え、前記ブロック結合手段は、空きブロックの結
   合により各ブロックサイズ別の占有状況が所定の条件を
   満たさなくなる場合には、空きブロックの結合を行わな
   い構成を有することを特徴とする請求項４記載のファイ
   ルデータ格納装置。
6. 【請求項６】 前記入出力制御部に、 複数のブロックサイズのうち最小サイズ以外のブロック
   サイズの空きブロックを抽出し、該抽出したブロックを
   該ブロックサイズより小さなブロックサイズの空きブロ
   ックに分割する空きブロック分割手段と、 複数のブロックサイズのうち最大サイズ以外のブロック
   サイズの空きブロックを複数個集めて、それより大きな
   ブロックサイズのブロック１個分に結合するブロック結
   合手段とを備えることを特徴とする請求項１記載のファ
   イルデータ格納装置。
7. 【請求項７】 二次記憶装置を制御する入出力制御部を
   構成するデータ処理装置を、 複数のブロックサイズを指定した構築指示に従って、二
   次記憶装置上にブロックサイズ別の空きブロックを確保
   し、かつ、各ブロックサイズ別に空きブロックの情報を
   管理する空き領域管理情報を作成して二次記憶装置に記
   録する構築部、 二次記憶装置上に書き込むべきデータに応じて必要なブ
   ロックサイズを決定するブロックサイズ決定手段、 該ブロックサイズ決定手段で決定されたブロックサイズ
   の空きブロックの情報を前記空き領域管理情報から抽出
   する空きブロック抽出手段、 該空きブロック抽出手段で抽出されたブロックを、指定
   されたファイルの所属とするブロック割り当て手段、 ファイルに割り当てられているブロックの情報をそのフ
   ァイルの所属から取り除くブロック解放手段、 該ブロック解放手段で解放されたブロックをそのブロッ
   クのブロックサイズに対応する空き領域管理情報に登録
   する空きブロック登録手段、 複数のブロックサイズのうち最小サイズ以外のブロック
   サイズの空きブロックを抽出し、該抽出したブロックを
   該ブロックサイズより小さなブロックサイズの空きブロ
   ックに分割する空きブロック分割手段、 複数のブロックサイズのうち最大サイズ以外のブロック
   サイズの空きブロックを複数個集めて、それより大きな
   ブロックサイズのブロック１個分に結合するブロック結
   合手段、として機能させるプログラムを記録した機械読
   み取り可能な記録媒体。