JPH08511369A - レードディスクサブシステムを備えた、ファイルシステムのファイル割り当て方法 - Google Patents

Abstract

(57)【要約】 本発明は、レードサブシステム（１０３０）におけるデータブロックの配列の正確な情報を送り出すことができるレードアレー（１０３０）を備えたファイルシステムの一体化方法に関する。このシステムは、ディスク割り当てを行うため、公知のレードディスクレイアウトを用いる。本発明は、個別のカレント書き込み位置（ＣＷＬ）ポインタをディスクアレー（１０３０）の各ディスク（１０２２）に用い、それらのポインタは書き込みが行なわれる毎にディスク上を進んでゆく。用いられているアルゴリズムには、二つの主要な目的がある。第一の目的は、ＣＷＬポインタをできる限り互いに接近した位置に保つことにより、ストライプに複数のブロックを同時に書き込み、レード（１０３０）の効率を上げることである。第二の目的は、あるファイルの隣接したブロックを同じディスク（１０２２）に割り当て、読出動作の効率を上げることである。第一の目的は、最も低い位置にあるＣＷＬポインタに基づいてディスク上への書き込が行なわれることにより達成される。第二の目的は、新しいファイルにスペース割り当てがおこなわれる際、またはあるファイルに同じディスク（１０２２）のＮ個のブロックに割り当てがおこなわれたときのみに、別のディスクが選択されることにより達成される。その結果、ＣＷＬポインタは異なったディスク（１０２４）上でもＮブロック以上離れることはなく、大きなファイルも、同じディスクにＮ個の連続するブロックに収めることができる。

Description

【発明の詳細な説明】 レードディスクサブシステムを備えた、ファイルシステムのファイル割り当て方 法 発明の背景 １．発明の分野 本発明は、情報を記憶するディスクアレイを用いたファイルシステムの分野に 関する。２．従来技術 一般に、コンピュータシステムにおいては、種々の情報（例えばデータおよび ／またはアプリケーションプログラム等）を記憶するためのディスクドライブな どの多くの２次メモリを必要とする。従来のコンピュータシステムにおいては１ つの“ウインチェスター”スタイルのハードディスクドライブを用い、大量のデ ータを永久記憶する構成がとられている。コンピュータやそれに付属のプロセッ サのパーフォーマンスがコード化されるに伴い、大容量のディスクドライブの必 要性やデータ伝送レートのスピード化が望まれるようになった。この要望に歩調 を合わせるため、ディスクドライブパーフォーマンスにおける改良がなされてき た。例えば、データやトラック密度の増加や、メディアの改良や、１つのディス クドライブにおけるヘッドの数やディスクの数の増加等がデータ伝送レートのス ピード化に寄与してきた。 １つのディスクドライブでもって２次記憶装置を構成することの欠点は、より 多くの容量やパーフォーマンスが必要となったときにドライブの取り替えが必要 となることによる出費がある。他の欠点としては、リダンダンシィ（余裕）の無 さであり、単一のディスクドライブにおいてバックアップをとるための容量不足 がある。１つのディスクドライブが故障し、機能しなくなり、または置き換える ことができなくなれば、そのシステムは使うことができなくなる。 単一のディスクドライブシステムにおける上述の欠点を無くしたり軽減するた めに試みられた一つの従来技術として、並列につながれた複数のドライブを使用 するものがある。この場合、データはいくつかの大きな塊に分けられ、複数のド ライブから平行に、かつ同時にアクセスすることもできるし、複数のドライブの うち１つのドライブだけからシーケンシャルにアクセスすることもできる。この ようにディスクドライブを並列に組み合わせたシステムは、“安価なディスクに よる余剰アレイ（redundant array of inexpensive disks）”略してレード（Ｒ ＡＩＤ）アレイと呼ばれている。このレードシステムは、大きな１つのディスク ドライブシステムと同じ記憶容量を低価格で提供するものである。更に、アレイ の並列処理により、高速のデータ伝送レートを達成することができる。 レードシステムにおいては、アレイに追加のディスクドライブを加えることに より、段階的に記憶容量を増やしていくことが可能となる。ディスクが故障して もレードシステムが備わっていれば、システム全体を止めることなくそのディス クを取り替えることが可能となる。また、故障したディスクに残っているデータ は、エラー訂正技術を用いることによりリカバリーすることも可能である。 あるレードには６つのディスクアレイが備わっており、それらはレードレベル ０からレードレベル５として呼ばれている。各レードレベルには利点や欠点があ る。以下の説明においては、単にレードレベル４および５について説明する。し かしながら、異なったレードレベルについての詳しい説明はパターソン（Patter son）他著の「安価なディスクを用いた余剰アレイの考察（A Case for Redundan t Arrays of Inexpensive Disks（ＲＡＩＤ））」ＡＣＭ ＳＩＧＭＯＤ会議， １９８８年６月に記載されている。この文献は本願の内容の一部を構成するもの としてここに引用する。 図１は従来技術のレードレベル４を有するシステムを示す。このシステムは、 コンピュータシステムまたはホストコンピュータに通信チャンネル１３０を介し て接続されたＮ個のディスク１１２〜１１８を有する。図示した例においては、 データは、４キロバイトのブロックまたはセグメントごとに各ハードディスクに 記憶される。ディスク１１２は、システムのためのパリティディスク、ディスク １１４〜１１８はデータディスク０〜Ｎ−１である。レードレベル４は、図１に 示すようにアレーにおけるすべてのディスクに亘ってデータブロックを配るディ スクストライプ方式を用いる。このシステムにおいては、第一のブロックを第一 のドライブに乗せ、残りのＮ−１個のドライブについても順番に巡回するよう構 成されている。レードレベル４はパリティ用に別のドライブを用い、パリティは ストライプと呼ばれる複数のデータブロックからなるグループ毎にエラー訂正情 報を有する。図１に示すディスクストライプ方式は、一度に大量のデータの読み 書きを行うことが出来るシステムである。各ドライブの一つのセグメントは、同 時に読むことができ、大きなファイルにより速くデータアクセスすることができ る。 レードレベル４のシステムにおいては、複数のブロックからなるファイルはＮ 個のディスク１１２〜１１８に“ストライプ”として記憶される。すなわち、ス トライプとは複数のデータブロックのグループであり、各ブロックはＮ個のディ スクの１つに記憶されることになる。図１において、第１および第２ストライプ １４０，１４２はそれぞれ点線で示されている。第１ストライプ１４０はパリテ ィ０ブロックおよびデータブロック０〜Ｎ−１から構成される。図に示す例にお いては、第１のデータブロック０はＮ個のディスクアレイのうちディスク１１４ に記憶される。第２のデータブロック１はディスク１１６に記憶され、以下同様 にして記憶が続く。そして、最後のデータブロックＮ−１はディスク１１８に記 憶される。当業者によく知られた技術を用いて、ストライプ１４０に対しパリテ ィチェックが行われ、その結果がディスク１１２にパリティブロックとして記憶 される。同様にストライプ１４２にはＮ−１個のデータブロックが含まれ、デー タブロックＮはディスク１１４に、データブロックＮ＋１はディスク１１６に、 そしてデータブロック２Ｎ−１はディスク１１８に記憶される。４ストライプ１ ４２のパリティチェックが行われ、その結果はディスク１１２にパリティブロッ ク１として記憶される。 図１に示すように、レードレベル４にはパリティディスクドライブが含まれ、 そこにはシステムの各ストライプのエラー訂正情報が含まれている。もし、シス テムにおいてエラーが発生すれば、レードアレイの全てのドライブを用いてシス テムにおけるエラーを訂正する必要がある。通常は１つのドライブにのみアクセ スされるので、レードレベル４は少量のデータを読むのには適している。レード レベル４のアレイはいつでもデータを読むことができるが、エラーがあるときは そのようにはいかない。一方、レードレベル４のアレイは、アレイにデータを書 き込む場合はいつもパリティドライブと協動する。 レードレベル５アレイのシステムも、レードレベル４のシステムと同様にパリ ティを利用する。しかしながら、パリティセクターを常に同じ１つのドライブに 記憶するようなことはしない。レードレベル５においては、パリティブロックの 位置を順次ずらし、Ｎ個からなるディスクアレイの全てのディスクに記憶される ようにする。したがって、レードレベル５のシステムはレードレベル４のシステ ムに比べ、パリティデータのアクセスをＮ−１個のディスクドライブに分散させ 、１ブロック単位でアクセスできるようにした点において改良がなされている。 第１の複数のブロックのセットに対しては、パリティブロックは最初のドライブ に記憶されるようになっている。第２の複数のブロックのセットにおいては、パ リティブロックは第２のディスクドライブに記憶されるようになっている。この ような記憶形態が繰り返され、各セットにパリティブロックが設けられることに なるが、パリティ情報は単一のディスクドライブに記憶されるということは起こ らない。レードレベル４のアレイと同様レードレベル５のアレイも必要とされる データのみを読み出すことができ、そこにエラーが含まれていることもあり得る 。レードレベル５のシステムにおいては、複数のブロックを含むグループに対す るパリティ情報が１つのディスクに収集されることがないので、アレイの複数の 異なったドライブに一度に書き込むことも可能となる。したがって、読み書き動 作はレード４アレイよりもレード５アレイの方がより高速に行うことが可能であ る。 図２はレードレベル５のシステムを備えた従来例のブロック図である。このシ ステムは伝送チャンネル１３０によりコンピュータシステムまたはホストコンピ ュータ１２０に接続されるＮ個のディスク２１２〜２１８で構成される。ストラ イ プ２４０においては、パリティブロックは第１ディスク２１２に記憶される。デ ータブロック０は第２ディスク２１４に記憶され、データブロック１は第３ディ スク２１６に記憶され、以下同様に記憶が行われる。そして、最後にデータブロ ックＮ−１はディスク２１８に記憶される。ストライプ２１２においては、デー タブロックＮは第１ディスク２１２に記憶される。第２のパリティブロック１は 第２ディスク２１４に記憶される。データブロックＮ＋１はディスク２１６に記 憶され、以下同様な記憶が行われる。最後に、データブロック２Ｎ−１はディス ク２１８に記憶される。Ｍ−１番目のストライプ２４４では、データブロックＭ Ｎ−Ｎは第１ディスク２１２に記憶される。データブロックＭＮ−Ｎ＋１は第２ ディスク２１４に記憶される。データブロックＭＮ−Ｎ＋２は第３ディスク２１ ６に記憶され、以下同様の記憶が行われる。最後に、パリティブロックＭ−１は Ｎ番目のディスク２１８に記憶される。したがって、図２に示すようにレードレ ベル５のシステムはレードレベル４のシステムと同様なパリティ情報を記憶する が、レードレベル５のシステムにおいてはパリティブロックの位置が順次ずらさ れ、ディスク２１２〜２１８に行き亙るようになっている。 レードレベル５においてはパリティはディスクのアレイにわたって分配される 。この結果、全体のディスクに亙る多重検索を行う必要がある。これはレードア レイの大きさを段階的に増やしていくことを禁止する。何故なら、パリティの構 成により所定量のディスクを一度に増やす必要があるからである。 レードサブシステムの上に載る従来のファイルシステムにおいては、レードア レイを１つの大きな複数のブロックの集合体として認識し、それらブロックはレ ードアレイを横切る方向に順次番号付けが行われる。１つのファイルに含まれる 複数のデータブロックは、複数のデータディスクに亙って分配して記憶され、各 ストライプをできるだけ一杯にした形で記憶され、それぞれのデータブロックは ストライプにおける異なったディスク上に記憶されることになる。第１のストラ イプにＮ−１個のデータブロックがレードアレイのＮ−１個のデータディスクの 全てに割り当てられれば、残りのデータブロックは次のストライプに同様なやり 方で割り当てられ、１つのファイルの全体が収まるまで以下同様にして、レード アレイ上に記憶が続けられる。このようにして、１つのファイルはレードシステ ムの複数のデータディスクに亙って記憶され１本のストライプを構成し、同様な ストライプを複数用いることにより記憶がなされる。なお、１本のストライプに はＮ−１個のデータブロックが含まれている。これでは、１つのファイルにアク セスするためにはＮ−１のディスクに亙ってアクセスする必要があり、Ｎ−１個 のディスクに検索をかける必要があるという欠点を生ずる。したがって、別の従 来例によるファイルシステムにあっては、１つのファイルの全てのブロックを単 一のディスクに書き込むことを行うものがある。しかしこれでは、１つのファイ ルについて１つのデータディスクのみに対して検索が行われ、残りのＮ−２個の ディスクが十分活用されていないという欠点が生ずる。 ファイルシステム自身には、それが記憶されるレードサブシステムについての 情報は一切有しておらず、かかるレードサブシステムを単なる１つの大きなディ スクとして受け止めている。このような状況の基では、単一のデータブロックの みが１つのストライプに書き込まれ、パリティを計算するためには４つのＩ／Ｏ （入出力）動作を必要とするので、大きなペナルティを生ずることになる。例え ば、引き算によりパリティを行う場合、４回のＩ／Ｏ動作を必要とする。４つの ディスクからなるリードアレイにおいて、１つのディスクがパリティディスクで あれば、１つのストライプに対し３つのデータブロックを書き込み、そしてその データブロックに対するパリティチェックを行うことは、７５％（４本のうち３ 本のディスクのみを利用しているから）の効率しか得られず、１本のストライプ に１つのデータブロックにのみ書き込む操作においては２５％の効率しか得られ ない。 この割り当てアルゴリズムはストライプ全体をできる限り全て利用するもので あり、ファイルの実質的な部分をディスク上に連続した位置に記憶しようとする ものである。このシステムはファイルをディスク上にランダムにちりばめて記憶 することをできるだけ避けるようにしたものであり、複数のディスクの検索を必 要とするものである。もし１２キロバイトのファイルが４キロバイトのブロック 毎に３つの個別のディスク（１本のストライプ上）に亙って記憶されたならば、 ファイルにアクセスするためには３つの個別のアクセスが必要となる。他のクラ イエントがファイルシステムからファイルを取り出そうと試みるためキューを発 している間にこのことが行われる。 発明の要約 この発明はレードアレイ技術を伴うファイルシステムの改良に関する。本発明 はレードシステムにおけるデータブロックの配列に関する情報をレード層からフ ァイルシステムへ情報を送る構成に関する。ファイルシステムはこの情報を検査 し、更にレードシステムに書き込まれたブロックの位置の最適化を図るためにそ の情報を利用する。この発明は種々ある番号付け手順よりも優れた番号付け手順 を採用するレードサブシステムを備えたものである。この発明は大きな一塊の情 報を先読みすることにより、そしてストライプを一度に書き込むことにより、レ ードシステムへの書き込みを最適なものにするものである。 より効率の良い動作を得るためにレードアレイにとっては効率の良くないアク セスパターンを避けるため、ここに改良されたレード機能を有するファイルシス テムの開発が、書き込み割り当て方法に照らして行われた。したがって、この発 明においてはレードディスク配置の明白な知識が用いられ、ディスクの割り当て の計画がなされる。本発明においては、ディスクアレイの各ディスクに対し個別 の現在書き込みが行われている位置を示すカレント書き込み位置ポインタが用い られる。これらのカレント書き込み位置ポインタは書き込みが行われる度にポイ ントされているディスクが移り変わっていく。この発明において用いられたアル ゴリズムは、現在の書き込み位置ポインタをできる限り同じストライプに近い位 置に保持するようにし、複数のブロックをストライプに同時に書き込むことがで きるよう、レードの効率の改良を図るものである。本発明はまた、ファイルにお ける隣接したブロックの配置を同じディスクになるように工夫され、データが読 み出される際に効率の改善が図られるよう構成されている。 本発明においては、最下位のカレント書き込み位置ポインタを用いてディスク にデータを書き込む。本発明においてはまた、新しいファイルのためのスペース を割り当て始めるとき、または１つのファイルにつき同じディスクが十分に利用 されたときにのみ新しいディスクを選ぶようになっている。ここで十分に利用さ れたときとは、ブロックの十分な数を言い、一塊のブロックの全てのブロックで あり、一塊とはファイルにおける一連の複数のブロックのうちのある数Ｎ個に相 当するものである。複数のブロックが集まった一塊は、ファイルにおいてＮ個ず つに区切られて並べられたものである。したがって、複数のカレント書き込み位 置ポインタは異なったディスク上であってもＮブロック以上離散することはない 。したがって、大きいファイルは同じディスク上にＮ個の連続したブロックを有 することとなる。 図面の簡単な説明 図１は従来のレードレベル４サブシステムのブロック図、 図２は従来のレードレベル５サブシステムのブロック図、 図３は本発明に基づき、ＷＡＦＬファイルシステムと一体構成されるレードア レイを使用してファイルを割り当てるための動作を示すフローチャート、 図４は図３のステップ３３０の詳細を示すフローチャート、 図５は図４のステップ４９０の詳細を示すフローチャート、 図６はＷＡＦＬｉノードにより参照されるバッファのツゥリー構造を示す概略 図、 図７はよごれｉノードのリストを示す概略図、 図８は図７に示したｉノード７２０によって参照されるバッファのトリー構造 の割り当てを示す概略図、 図９Ａ−９Ｊは、図５に基づくディスクスペースの割り当てを示す概略図、お よび 図１０は本発明に係るシステムの概略図である。 本発明の詳細な説明 レードアレイを用いたファイルシステムにおいて、ファイルを割り当てる方法 について説明する。以下の説明において、種々の具体的データ、例えばポインタ の数やその特性、ディスクブロックの大きさ等、を用いて説明がなされるが、こ れらは、本発明をより完全に理解するためのものである。言うまでもなく、本発 明はこれらの具体的データに限定されるものではなく、これら以外の値であって も達成することができるものである。また、公知の内容等についてはその説明を 簡単にし、発明の内容が不必要に不明瞭なものとならないよう配慮されている。 ネットワークシステムに用いられるコンピュータについては、各ハードディス クはそのネットワークの動作スピードより早いスピードで動作するものとする。 したがって、ガイドシステムにおいては独立した複数のヘッドを用いるのが好ま しい。これによりレードアレイの個別の複数のディスクに記憶された異なったフ ァイルに複数のクライエントが同時にアクセスすることが可能となる。これによ り、レードシステムにおいてデータの引き出しおよび記憶のためのアクセス時間 が非常に短縮できる。 図１０は本発明に係るシステムを示すもので、レードサブシステムからなる。 コンピュータ１０１０は中央演算装置（ＣＰＵ）１０１２およびメモリ１０１４ からなる。ＣＰＵ１０１２はバス１０１６を介してメモリ１０１２に接続されて いる。バス１０１６によりコンピュータ１０１０はレードコントローラ１０２０ に接続されている。バス１０１６はまた、コンピュータ１０１０をネットワーク コントローラ１０４０に接続する。レードコントローラ１０２０は、レードアレ イ１０３０を構成するパリティディスク１０２０とデータディスク１０２２〜１ ０２４にバス１０２６を介して接続される。コンピュータ１０１０はＷＡＦＬフ ァイルシステムにおけるファイルの位置割り当てを行うものであって、ＷＡＦＬ ファイルシステムはレードコントローラ１０２０とディスク１０２０−１０２４ からなるレードディスクサブシステムと一体構成される。 本発明はレードアレイ１０３０において改良されたブロックの割り当て方法を 提供するものである。このシステムはパリティディスク１０２０を含むレードア レイであって、Ｎ個のディスク１０３０からなるレードレベル４型のアレイ１０ ３０を利用するものである。残りのディスク１０２２〜１０２４は複数のデータ ブロックを記憶するデータディスクである。このレードシステムのストライプは 複数の４キロバイトブロックからなり、各４キロバイトブロックはアレイの異な ったディスクに記憶される。ストライプのそれぞれのブロックはディスクの同じ 対応した位置に記憶される。広い意味では、ファイルは情報を記憶する構成であ って、データは一定の大きさのブロックに分割されたものであると言える。例え ば、本発明においてファイルシステムは４キロバイトのブロックを用いてデータ をディスクに記憶する。なお、言うまでもなく、本発明においては種々のブロッ クサイズ（例えば５１２，１０２４，２０４８バイト等）のものを用いることが でき、いずれも本発明に含まれるものである。したがって、例えば、１５キロバ イトのファイルについては４キロバイトのデータブロックが４つ必要となり、１ キロバイトのファイルについては４キロバイトのデータブロックが１つ必要とな る。 本発明においては複数のデータブロックからなるファイルは、１つのレードア レイにおける１つのディスクに所定数のブロックからなる複数のグループに割り 当てられる。これは１バイト毎、もしくはデータブロック（例えば４キロバイト のブロック）毎にＮ−１個のデータディスクに亙って書き込まれる従来のレード システムとは異なるものである。本発明の好ましい実施形態においては、一つの データディスクの上には最大８データブロック（３２キロバイト）からなるグル ープが割り当てられる。ファイルが割り当てられ、個別のディスクへと送り込ま れる。 本発明の重要なポイントは、最大数の異なったファイルに対し、各ディスクに おいて最大３２キロバイトの“チャンク（塊）”のデータブロックを同時に記憶 することができる方法を提供することである。理想的には複数のディスクに亙っ て形成される各ストライプは、Ｎ−１個の異なったファイルをＮ−１個のディス クに並列にデータブロックを同時に書き込んで、それが満たされるようになる。 本発明におけるファイルシステムとレードを一体化する概念は、全てのディス クにおける全ての腕がどこにあるかの知識をレードから与えるものであって、そ れにより書き込みの順番を制御することを提案するものである。したがって、い ずれの時点においても、最大のグループの書き込みを行うことができ、パリティ ディスクを“ホット（活動化）”にする必要がなく、レードアレイ全体を通して パリティディスクを見つけ出す必要がない。システムの障害となっていた“ホッ ト”は問題とはならない。何故なら同じ数だけの書き込みを行うことができるか らである。最も好ましい状況は書き込みを行う際、ストライプにおける全てのブ ロックが空きの状態であり、３つのデータディスクに対して行われる３つの書き 込みについてパリティチェックがなされる場合である。しかし、通常のケースに おいてはストライプにおける１つまたは複数のデータブロックが既にデータで満 たされている。これは以前から存在する他のデータがレードサブシステムに記憶 されているからである。したがって、通常のファイルシステムにおいては、例え ば２つは第１ストライプに書き込まれ、第２および第３ストライプのそれぞれに １つが書き込まれ、第４ストライプに３つが書き込まれるという場合である。し たがって、この場合４本のストライプに亙って書き込まれた７つのデータブロッ クについて４つのパリティ計算を行う必要がある。 本発明はストライプ全体を書き込もうとするとともに、１つのディスクに各フ ァイルを記憶するようにするものである。したがって、パリティディスクにある ヘッドはディスク全体を検索することは必要ない。もし、ヘッドを１つのシリン ダに設ければ、データをディスクからより高速に読み出すことができ、ディスク 毎に多数のトラックに亙って検索する必要がなくなる。これはまた、それぞれの ディスクドライブに設けた１つのシリンダにより１／４メガバイトのデータまた はそれ以上のデータを記憶することができるという利点があり、１つのトラック にファイルの大きな“チャンク（塊）”を書き込むことが可能となる。例えば、 ９０％満たされたファイルシステムであっても、まだ更に２５０キロバイトのシ リンダに２５ＫＢのデータを記憶することが可能である。この場合、隣のシリン ダにおいてもディスクが１／４回転する間検索することができ、１つのディスク に更に ２５ＫＢ書き込むことも可能である。したがって、９０％満たされたファイルシ ステムであっても、５０ＫＢより以下の容量を有するファイルはレードアレイに おける１つのディスクの隣接トラックに速やかに記憶することが可能となる。し たがって、もしファイルをディスクに記憶することがわかっておれば、ディスク は検索のために“ホット”になる必要はない。システムにおける他のディスク以 上により多くの書き込みや検索を経験する必要はない。レードアレイの各ディス クには匹敵する程度の書き込みがある。更に、読み出しの際、割り当て要求であ るファイルのキューは他のディスクのキューに順位が遅らされることはない。 ファイルシステムにはレード層と通信することができるデータ構成を有する。 レード層からはファイルシステムに情報が送られ、レード層のシステムがどのよ うな形態になっているかを知らせる。ファイルシステムのデータ構造はレードシ ステムにおける各ディスクについての情報のアレイが含まれる。同じストライプ に複数のファイルブロックを書き込むことの重要性の理由は他にもある。すなわ ちレードにおいてブロックが更新された場合、１つのデータブロックに書き込み を行う場合４つのディスクのＩ／Ｏが必要となるからである。効率の点からすれ ば、１つのブロックを書き込みに、そして２つのブロックを読み取りに用いるよ りも、ストライプに対し３つのブロックを書き込んだ方が好ましい。 個別のディスクのバンド幅よりもネットワークの必要性が高くなるにつれて、 十分な先の情報を読み取ることが好ましく、１つのファイルにアクセスする場合 でも、先に別のディスクにアクセスしておくのが好ましい。これはＦＤＤＩおよ びＡＴＭ等の大きなファイルや高速のネットワークを利用する場合に特に有益で ある。 本発明では、各ディスクに対しディスクの現在の書き込み位置を指定するカレ ント書き込み位置ポインタを設けている。カレント書き込み位置ポインタはディ スクの最終点に到達するまでディスク上で順次その位置がずれていくように構成 され、最終点に到達した後はポインタはディスクの開始点にまで戻ってくる。レ ードアレイの全てのディスクのカレント書き込み位置ポインタはできる限り互い に接近した位置に保たれるようになっている。したがって、各ディスクにおいて ブロック位置の割り当てが順次下の方に移ってくると、レードアレイの処理が行 われるにしたがってストライプが満たされていくこととなる。同じ１つのディス クにファイルを連続して並べるためには、同じ１つのディスクに所定量のブロッ クを割り当てる必要がある。 複数のファイルをグループにまとめるためには、割り当てアルゴリズムはバッ ファを必要とし、ファイルブロックの連続したグループは各ディスクに書き込む ことができると同時に、処理が行われている間はストライプを同時に満たすよう にすることができる。したがって、ファイルはレードシステムに送られて来れば 直ちに書き込みが行われるのではなく、まずバッファに一時的に溜められ、続い てディスクに割り当てられるようになる。最も簡単な形態においては、割り当て アルゴリズムはバッファから（ランダムにもしくはその他の手順で）ファイルを 選出し、書き込み位置ポインタの位置が最も遅れた位置にあるディスクをリード アレイから選び出し、そのディスクから所定量の連続したブロック（４ＫＢを８ ブロック）であって使用可能なものを探し、そのファイルを書き込むためにそれ らブロックを割り当てる。ＮＦＳシステムにおいては、ファイルサーバに送られ てくるファイル要求は通常８ＫＢのデータの単位で送られてくる。本発明におい ては３２ＫＢのセグメント分のデータを先んじて読み出し、そのデータ量は各デ ィスクに連続して書き込むことができるファイルデータ量と同等な量である。こ の方法の基本的概念によれば、各ディスクに連続して記憶可能なデータ量は、各 ディスクにおいて先行して読むことができるデータ量に相当する。もしブロック がディスク上連続して並んでいなければ、中間にスペースが存在することとなり 、書き込み位置ポインタを進めるにはそれをとばして進めなければならない。カ レント書き込み位置ポインタが現在の最下点を越えて移動したとき、ストライプ におけるファイルシステムによりブロックはレードサブシステムに送り込まれる 。したがって、データブロックは互いに一体となってストライプとしてレードサ ブシステムに書き込まれ、より好ましいシステムの特性を得ることができる。こ れは、 通常のファイルシステムの下にレードサブシステムを配置する従来のシステムと は異なるものである。従来のシステムにおいては最適な環境を得るため、ファイ ルシステムとレードサブシステムの層の間に大きなキャッシュ（cache）を用い ることが試みられていた。そしてそのキャッシュはファイルサイズと同じ大きさ のストライプを見つけるように設計されていた。したがって、従来のレードサブ システムにおいては、ファイルシステムのブロックをどこに配置するかの制御を することができなかった。ほとんどのユニックス（ＵＮＩＸ）のファイルシステ ムにおいては、ファイルを望み通りの位置に並べることはできず、決められた位 置に順番に並べるだけであった。したがって、１メガバイトのキャッシュを有す る従来のシステムにおいては、１メガバイトの“チャンク”（キャッシュサイズ ）のデータのグループが、例えば１０ギガバイトの大きなレードシステムにラン ダムに送り込まれたとき、連続して並べられるようなことはまずあり得なかった 。 本発明においては８の単位（３２ＫＢ）の１つのファイルにアクセスする場合 、ディスク間におけるスワッピング（データの行き来）をほとんど無くすことが できる。任意場所書き込みファイルシステムレイアウト（Write Anywhere File-system L ayout） 本発明は任意場所書き込みファイルシステムレイアウト（Write Anywhere Fil e-system Layout）（ＷＡＦＬ）と名付けられたファイルシステムを採用するも のである。広い意味では、ＷＡＦＬはファイルシステムレイアウトの情報が記憶 されているメタ（超）−データを記憶するファイルを利用するものである。この ファイルシステムはフラグメントを一切用いない４キロバイトのブロックを用い るブロック単位で構成されるものである。ＷＡＦＬファイルシステムにおける複 数のファイルは全てｉノードにより表され、ｉノードには各ファイルのサイズ、 位置、制作者、その他ファイルに関する情報が含まれている。第３に、ディレク トリはこのシステムにおいては単なるファイルであり、それらファイルは特別に フォーマットがなされている。このＷＡＦＬにおいて２つの重要な中核（in-cor e）とな るデータ構造はＷＡＦＬｉノードとＷＡＦＬバッファである。ＷＡＦＬｉノード はファイルシステムにおいて特別のファイルを示すものである。それにはディス ク上のｉノードの全ての情報の外、他の情報が含まれる。ＷＡＦＬバッファは、 メモリになるファイルの１つの４キロバイトデータブロックを記憶するものであ る。ＷＡＦＬｉノード 図６はＷＡＦＬｉノード６１０の概略図を示す。ここにおいてファイルは間接 ＷＡＦＬバッファ６２０〜６２４と、直接ＷＡＦＬバッファ６３０〜６３４から 構成される。ＷＡＦＬインコア（中核的）ｉノード６１０は、スタンダードｉノ ード情報６１０Ａ（汚れたバッファ（dirty buffers）のカウントを含む）、Ｗ ＡＦＬバッファデータ構造６１０Ｂ、１６個のバッファポインタ６１０Ｃ、およ びスタンダードオンディスクｉノード６１０Ｄを含むものである。インコアＷＡ ＦＬｉノード６１０は約３００バイトの大きさを有する。オンディスクｉノード は１２８バイトの大きさを有する。ＷＡＦＬバッファデータ構造６１０Ｂは２つ のポインタを有し、第１番目のポインタは１６個のバッファポインタ６１０Ｃを 参照し、第２番目のポインタはオンディスクブロックナンバー６１０Ｄを参照す る。 各ｉノード６１０には汚れバッファのカウントを有し、それが参照される。ｉ ノード６１０は、汚れｉノードのリストおよび／または汚れバッファを有するｉ ノードのリストに加えられることができる。ｉノードによって参照される全ての 汚れバッファは、ディスクに書き込まれることが予定されたものか、既にディス クに書き込まれたものである場合、ｉノード６１０に対する汚れバッファのカウ ントは０にセットされる。ｉノード６１０はそのフラッグ（すなわち汚れバッフ ァを含まないことを示すフラッグ）により再キューされる。このｉノード６１０ は次のｉノードが処理される前にクリアされる。 ＷＡＦＬバッファ構造は直接ＷＡＦＬバッファ６２０により構成される。ＷＡ ＦＬバッファ６２０は、ＷＡＦＬバッファデータ構造６２０Ａと、１０２４個の ＷＡＦＬバッファポインタを有する４ＫＢバッファ６２０Ｂと、１０２４個のオ ンディスクブロックナンバーを有する４ＫＢバッファ６２０Ｃからなる。１０２ ４個のオンディスクブロックナンバーはディスクからブロックの正確な内容を参 照する。バッファ６２０Ｃの１０２４個のポインタは子ブロックとして導入され 、キャッシュにおいてバッファ６２０に記憶される。ＷＡＦＬバッファデータ構 造は５６バイトの容量を有し、２つのポインタを備えている。ＷＡＦＬバッファ データ構造６２０Ａの１つのポインタは４ＫＢバッファ６２０Ｂを参照し、第２ 番目のポインタはバッファ６２０Ｃを参照する。図６において、ＷＡＦＬｉノー ド６１０の１６個のバッファポインタ６１０Ｃは、１６個の単一−間接ＷＡＦＬ バッファ６２０〜６２４をポイントする。さらに、ＷＡＦＬバッファ６２０は１ ０２４個の直接ＷＡＦＬバッファ構造６３０〜６３４を参照する。ＷＡＦＬバッ ファ６３０は直接ＷＡＦＬバッファを表すものである。 ＷＡＦＬバッファ６３０はＷＡＦＬバッファデータ構造６３０Ａと、オンディ スク４ＫＢデータブロックに対応するキャッシュメモリを含む４ＫＢ直接バッフ ァ６３０Ｂからなる。直接ＷＡＦＬバッファ６３０は、間接ＷＡＦＬバッファ６ ２０にあるバッファ６２０Ｃのような４ＫＢバッファを含まない。ＷＡＦＬバッ ファデータ構造６３０Ａの第２バッファポインタは０にされ、第２４ＫＢバッフ ァをポイントすることはない。これによりメモリの非効率的な使用が避けられる 。何故なら、メモリスペースはそうでなければ未使用バッファとして認識される からである。 図６に示すＷＡＦＬファイルシステムにおいては、ＷＡＦＬ中核ｉノード構造 ６１０はＷＡＦＬバッファ構造６２０〜６２４および６３０〜６３４のツゥリー 構造を参照する。これは、間接および／または直接ブロックをポイントしている ブロックナンバーからなるスタンダードのｉノードによって参照されるディスク 上のブロックのツゥリー構造と同様なものである。したがって、ＷＡＦＬｉノー ド６１０は、１６個のボリュームブロックナンバーからなるオンディスクｉノー ド６１０Ｄのみからなるのではなく、ＷＡＦＬバッファ構造６２０〜６２４およ び６３０〜６３４をポイントする１６個のバッファポインタ６１０Ｃをも含むも のである。ＷＡＦＬバッファ６３０〜６３４はボリュームブロックナンバーによ り参照されるブロックであって、キャッシュされた内容のものを含む。 ＷＡＦＬ中核ｉノード６１０は１６個のバッファポインタ６１０Ｃを含む。そ して、１６個のバッファポインタ６１０ＣはＷＡＦＬバッファ構造６１０Ｂによ り参照され、このＷＡＦＬバッファ構造６１０ＢはＷＡＦＬバッファ６２０〜６ ２４および６３０〜６３４のツゥリー構造の根幹（ルート）を成すものである。 したがって、各ＷＡＦＬｉノード６１０は、１つのＷＡＦＬバッファ構造６１０ Ｂを含み、このＷＡＦＬバッファ構造６１０Ｂはｉノード６１０の１６個のバッ ファポインタ６１０Ｃをポイントするものである。これは、再帰的に実行される （後で説明）バッファのツゥリーを扱うアルゴリズムを簡単なものにする。もし 、ｉノード６１０の１６個のバッファポインタ６１０ＣがＷＡＦＬバッファコー ド６１０Ｂにより表されていなければ、バッファ６２０〜６２４および６３０〜 ６３４の全ツゥリーに対して動作する機能的アルゴリズムを実行することは難し くなる。汚れブロックを有するｉノードのリスト ＷＡＦＬファイルシステムのＷＡＦＬ中核ｉノード（すなわち図６に示すＷＡ ＦＬｉノード６１０）はそのステータスにより異なったリンクのリストで保全さ れる。汚れデータを含むｉノードは図７に示すように、汚れｉノードリストに加 えられる。従来から知られているように、汚れていない有効なデータを含むｉノ ードは別のリストに加えられ、有効なデータを全くもたないｉノードはさらに別 なリストに加えられる。本発明においては汚れデータブロックを有するｉノード のリストを利用するので、割り当て書き込みを行う必要がある全てのｉノードを 見つけ出す機能を容易にすることができる。 図７は本発明に係る汚れｉノードのリスト７１０の概略図である。汚れｉノー ドのリスト７１０はＷＡＦＬ中核ｉノード７２０〜７５０からなる。図７に示す ように、各ＷＡＦＬ中核ｉノード７２０〜７５０は、それぞれポインタ７２０Ａ 〜７５０Ａを有し、それによりリスト中にリンクされた他のｉノードをポイント する。例えは、ＷＡＦＬｉノード７２０〜７５０はそれぞれ２０４８，２１５２ ，２８７８，３４４８，３７１２で示されるメモリ位置に記憶されている。した がってｉノード７２０のポインタ７２０Ａはアドレス２１５２を有する。これに よりＷＡＦＬｉノード７２２がポイントされる。さらに、ＷＡＦＬｉノード７２ ２はそこに書かれたアドレス２８７８を用いてＷＡＦＬｉノード７３０をポイン トする。続いてＷＡＦＬｉノード７３０はＷＡＦＬｉノード７４０をポイントし 、ＷＡＦＬｉノード７４０はｉノード７５０をポイントする。ＷＡＦＬｉノード ７５０のポインタ７５０Ａには何も記憶されていないので、これ以後はいずれの ｉノードをもポイントすることはない。すなわちこれが汚れｉノードのリスト７ １０に挙げられた最後のｉノードであることがわかる。 リスト７１０の各ｉノードは図６で示したバッファのツゥリー構造からなるフ ァイルを表す。各ｉノード７２０〜７５０により参照される少なくとも１つのバ ッファは汚れバッファである。汚れバッファは修正されたデータを含み、その修 正されたデータはＷＡＦＬシステムにおける新しいディスクの位置に書き込まら れなければならない。ＷＡＦＬは常に汚れバッファをディスク上の新たな位置に 書き込む。図７に示す汚れｉノードのリスト７１０は単一にリンクされたリスト として示されているが、当業者には容易であるようにＷでリンクされたリストや 他の適切なデータ構造をとるようにしてもよい。 ＷＡＦＬシステムとは異なり、ＦＦＳにおいては、バッファは、バッファに記 憶されたディスクブロックの物理的ブロック数に基づいて把手されたキャッシュ に保持される。この方法は、新しいデータが書き込まれるや否や、ディスクスペ ースは常に割り当て可能な状態にあるディスクシステムについては良好に行うこ とができる。しかしながら、ＷＡＦＬのようにメガバイト級やそれ以上のデータ がディスク上に書き込まれる前にキャッシュに集められるようなシステムについ ては全く機能しない。ファイル割り当てアルゴリズム 図３は本発明に係るファイル割り当て方法を示すフローチャートである。この アルゴリズムはステップ３１０のスタートから始まる。ステップ３２０において 汚れブロックを有するｉノードのリストから汚れブロックを含むｉノードが選択 される。ステップ３３０において、ｉノードで表されたバッファのツゥリー構造 がディスク上に割り当て書き込みがなされる。判定ブロック３４０においては、 汚れリストにある全てのｉノードが処理されたかどうかの判定が行われる。もし 判定結果が偽（ＮＯ）であれば、ステップ３２０に戻る。しかし、判定ブロック ３４０の結果が真（ＹＥＳ）であれば、ステップ３５０へ進む。ステップ３５０ において、全ての書き込みが行われていないストライプはディスク上に送出され る。そしてステップ３６０でこのアルゴリズムは終了する。キャッシュにあるフ ァイルが割り当てのために選択されれば、まずダイレクトリィの割り当てが行わ れる。次に、ファィルは一番使っていなかったところの選定（lest-recently-us ed（ＬＲＵ）basis）に基づいて割り当てが行われる。 図４は、ディスクにバッファのツゥリー構造の形で割り当てられたバッファを 書き込む図３のステップ３３０のフローチャートが示されている。図３のステッ プ３３０では、ｉノードを参照したバッファのツゥリー構造はライトアロケート （Write Allocate）（ｉノードのルートバッファポインタ）と名付けられたアル ゴリズムによって割り当て書き込みが行われる。１６個のバッファポインタ６１ ０Ｃを参照するＷＡＦＬｉノード６１０のバッファデータ構造６１０Ｂにあるポ インタはアルゴリズムに送られる。図４においてこのアルゴリズムはステップ４ １０から開始される。ステップ４１０でバッファポインタがライトアロケートア ルゴリズムに送られる。判断ブロック４２０では、バッファポインタの子バッフ ァのすべてが処理されたかどうかが判定される。判断ブロック４２０の結果が真 （ＹＥＳ）であれば、ステップ４３０へ進む。ステップ４３０において再帰的ア ルゴリズムにより呼び出し処理に戻る。従ってライトアロケーションアルゴリズ ムは図３に示す判断ブロック３４０である呼び出し処理まで戻る。別の方法とし ては、図４に示す判断ブロック４８０に戻り、再帰的な呼び出し（後に説明）を 行うこと も可能である。 判断ブロック４２０の結果が偽（ＮＯ）であれば、ステップ４４０へ進む。ス テップ４４０においてバッファポインタにより参照されるバッファの子バッファ が取り込まれる。判断ブロック４５０ではこの取り込んだ子バッファが最下位の ものかどうかの判定が行われる。判断ブロック４５０の結果が偽（ＮＯ）であれ ば、ステップ４６０へ進む。ステップ４６０ではライトアロケートアルゴリズム が子バッファポインタを用いて再帰的に呼び出される。続いて、判断ブロック４ ８０が実行される。判断ブロック４５０の結果が真（ＹＥＳ）であれば、ステッ プ４８０へ進む。判断ブロック４８０では、子バッファが汚れているか否かの判 定が行われる。判断ブロック４８０の結果が真（ＹＥＳ）であれば、ステップ４ ９０へ進む。ステップ４９０では、アロケートスペース（子バッファポインタ） と呼ばれるアルゴリズムを呼び出し、子バッファのためのディスクスペースが割 り当てられる。その後判断ブロック４２０に戻る。判断ブロック４８０の判断結 果が偽（ＮＯ）であれば、判断ブロック４２０が続いて実行される。図４に示さ れるアルゴリズムについては、すべての子バッファに対して深さ優先−ポストビ ジト−トラバーサル（depth−first post−visit traversal）が実行され、汚れ たものについては新しいディスクスペースが割り当てられる。ポストビジトトラ バーサルが必要なのは、子バッファにスペースを割り当てることにより親バッフ ァが変わるからである。 図５は、図４に示したステップ４９０であってディスク上にスペースを割り当 てる工法を詳しく説明するフローチャートである。ステップ５１０において、ス ペースを割り当てるアルゴリズムが、すでにディスク上にスペースが割り当てら れたバッファのバッファポインタに送られる。判断ブロック４２０において、今 回のバッファは、前回のバッファとは異なったファイルから作られたバッファか 、または前回のバッファとも異なった先読みチャンクからのバッファかの判断が 成される。判断ブロック５２０の結果が真（ＹＥＳ）であれば、ステップ５３０ へ進む。ステップ５３０では書き込まれるべきディスクが選定される。ここで選 ばれ るディスクは、最下位のカレント書き込み位置ポインタ（current-write locati on（ＣＷＬ）pointer）を参照して行われる。優先的に書き込みが行われるディ ホルトディスクは、ポインタの値が１番低い値のものである。その後ステップ５ ４０が実行される。判断ブロックの結果が偽（ＮＯ）であれば、ステップ５４０ へ進む。 ステップ５４０で、バッファとして使用される古いブロックはフリーにされる 。バッファに使用される古いブロックがフリーにされるためには、ブロックマッ プ（blkmap）ファイルを更新し、特定されたブロックのエントリーにはそのブロ ックがアクティブファイルシステムによりもはや使用されていない旨が表示され る。これはblkmapファイルの特定ブロックにおけるエントリーの部分をビット０ （０）で一掃することにより達成される。ステップ５５０において、選ばれたデ ィスク上にカレントブロックが割り当てられる。これは、plkmapファイルにおい て割り当てたように、書き込みが行われるべきディホルトディスクのＣＷＬポイ ンタをマークし、blkmapファイルを走査して次のＣＷＬポインタを見け出し、選 ばれたディスクのブロックに達することにより行われる。ステップ５５０は、図 ５に示すアルゴリズムに新しく割り当てられたブロックを支持する。 ステップ５６０において、ディスク上において割り当てられたブロックはバッ ファに当てられる。ステップ５７０において、そのバッファは選ばれたディスク における書き込み可能なバッファのリストの一つに加えられる。ステップ５８０ において、可能な場合はストライプを書き込む。ストライプ５８０において、完 全なストライプの一部を構成しているバッファがあるか否かをディスクバッファ ９に基づいてチェックする。それらのバッファはグループとしてレードサブシス テムに送られ、出来るだけ効率よく一体となった形で書き込まれる。ステップ５ ９０でアルゴリズムは呼び出しアルゴリズムに戻る。 ブロックがフリーにされたり割り当てられたりするに従って、ステップ５３０ 〜５５０では、フリーブロック管理機能（free block management functions） が用いられる。これらの機能により、現在書き込まれたディスクや各ディスクに おいてどれが次のフリーブロックになるか等の経過を保持するグローバルな変数 等 を保全する。またこれらは、blkmapファイルのエントリーを更新する。ファイル システムが開始されれば、ＣＷＬポインタは初期化され、ディスク上の最初のフ リーブロックをポイントする。フリーブロックが順次使われるの従って、ＣＷＬ ポインタは進められ、これはディスクの終端に到達するまで繰り返し行われる。 この時点において、選択はディスクの最初のフリーブロックに戻る。 ステップ５６０〜５８０はディスク入力／出力（Ｉ／Ｏ）機能についての動作 である。これらの機能は各ディスクにおけるＩ／Ｏ動作を管理する。各ディスク にはディスクへの書き込み待ちのバッファに対するキューがある。ストライプ上 に完成されたデータが生成されれば、バッファはキュー状態から開放され、ディ スクのＩ／Ｏサブシステムに書き込まれる。すべてのディスクのＣＷＬポインタ の値がストライプのブロックをパスすれば、１本のストライプが完成される。す なわち、例えばＣＷＬポインタの値がそれぞれ２３１、２２８、２３５である３ つのデータディスクがあった場合、最も低い値である２２８以下の値を有するス トライプはすべて完成されたものであると言える。 図３および図４で説明したように、図５に示すスペース割り当てアルゴリズム は処理される汚れバッファのいずれに対しても呼び込まれる。図３および図４に 示すアルゴリズムは１ファイルずつ処理を行い、それらファイルは順次処理が行 われる。従って、汚れバッファのためのスペース割り当てアルゴリズムはランダ ムに呼ばれるのではなく、各ファイルに対して複数の汚れバッファについて呼ば れることとなる。 本願発明においては、リードアレイにグループ化されたブロックをディスク上 で割り当てる際、２つの制約条件を満たす必要がある。第１の制約条件は、先読 み機能を改良するため、同じディスク上にファイルの一連のブロックを割り当て ることである。第２の制約条件は、リードアレイの書き込み機能を改良するため 、ストライプにおけるすべてのフリーブロックを同時に割り当てることである。 このアルゴリズムにおいては、割り当てのため特定のファイルを選択し、汚れ ブロックをファイル上に割り当てるためリードアレイからディスクを選択し、フ ァ イルの一連の汚れブロック用にディスク上において一連のフリーブロックを割り 当てることにより第１の制約条件を満たしている。またこのアルゴリズムにおい ては、０から始め、ブロック割り当てが起こるたびに現在の書き込みデータをイ ンクリメントさせ、ディスクの終端までこのインクリメントを繰り返し、各ディ スクにおいて現在の書き込み位置の情報を正しく保つことにより第２の制約条件 が満たされる。リードアレイにおけるすべてのディスクの現在の書き込み位置を 互いに近い値になるようにすることにより、同じストライプにおけるブロックは ほぼ同じ時に割り当てが行われる。現在の書き込み位置情報を互いに接近した値 に保つための一つの方法として、ディスク上で割り当てるブロックを常に現在の 書き込み情報が１番低い値のものを選ぶようにする方法がある。 ストライプ毎のブロックをレードに送るためには要求を遅らす必要がある。な ぜなら、ディスク間において必ずしも同じ現在書き込み位置情報を有していると は限らないからである。従って、各ディスク毎に書き込むべきバッファのキュー が備わっている。ディスク上のブロックナンバーがすべてのディスクにおける現 在の書き込み位置情報の最低値より小さい値を有するバッファは書き込みに最も 適したバッファである。本願発明においては、レードアレイにおけるすべてのデ ィスクをスキャンし、同じ現在書き込み位置情報を有するブロック（すなわち同 じストライプにあるバッファ）を見付け、ストライプ毎のバッファをレードサブ システムに送り込むことができるようにする。この点については以下にさらに詳 述する。 汚れバッファを有するｉノードの処理 図７に示す汚れｉノードのリスト７１０は、図３に示すフローチャートに基づ き以下のように処理される。ステップ３２０において、ｉノード７２０は汚れｉ ノードのリスト７１０から選びだされる。ＷＡＦＬ中核ｉノード７２０により参 照されるバッファのツゥリー構造はステップ３３０において割り当て書き込みが なされる。判断ブロック３４０において汚れｉノードのリスト７２０にあるすべ てのｉノードが処理されたか否かが判断される。判断ブロック３４０の結果が偽 （Ｎ Ｏ）であれば、ステップ３２０へ進む。ステップ３２０では、汚れバッファを有 する次のｉノード７２２が選ばれる。ｉノード７２２はリスト７１０における前 のｉノード７２０によって参照される。ステップ３３０においてＷＡＦＬ中核ｉ ノード７２２によって参照されるバッファのツゥリー構造は割り当て書き込みさ れる。判断ブロック３４０において、汚れｉノードのリスト７１０にあるすべて のｉノードが処理されたか否かが判断される。判断ブロック３４０の結果が偽（ ＮＯ）であったとする。この場合はｉノード７３０および７４０は同様な方法で 処理される。ステップ３３０においてｉノード７４０が割り当て書き込みが成さ れれば、判断ブロック３４０において汚れリストにおけるすべてのｉノードが処 理されたか否かがチェックされる。判断ブロック３４０の結果が偽（ＮＯ）であ れば、ステップ３２０に進む。 ステップ３２０においてｉノード７４０によりポイントされるｉノード７５０ が汚れｉノードのリスト７１０から選出される。ステップ３３０においてｉノー ド７５０はリスクに割り当て書き込みされる。判断ブロック３４０において、汚 れｉノードのリスト７１０におけるすべてのｉノードが処理されたか否かが判定 される。ここでポインタ７５０Ａは空である。従って、ｉノード７５０はリスト ７１０においては次のｉノードの指定を行うことはない。従って、判断ブロック ３４０の結果は真（ＹＥＳ）となり、続いてステップ３５０が実行される。ステ ップ３５０においては、書き込まれていないストライプはすべてディスクへ一気 に送出される。従って、ステップ３５０において汚れｉノードのリスト７１０に おける汚れｉノード７２０〜７５０のすべてについて割り当て書き込みが行われ たとすれば、キュー状態にあるバッファや未完成のストライプは以下に説明する ように、すべて強制的にディスクに送り出される。ステップ３６０においてこの アルゴリズムは終了する。 バッファのツゥリー構造の割り当て書き込み 図８は、ｉノード８１０により参照されるバッファ８２０〜８５０，８６０Ａ 〜８６０Ｆ，８７０Ａ〜８７０Ｄのツゥリー構造の割り当てを示すものである。 ＷＡＦＬｉノード８１０は１６個のバッファポインタ８１０Ａと、１６個のバッ ファポインタ８１０Ａを参照するＷＡＦＬバッファデータ構造８１０Ｂで構成さ れる。図８において、間接バッファ８２０および８３０は汚れており、間接バッ ファ８４０〜８５０はクリーンである。同様に直接バッファ８６０Ａ〜８６０Ｂ および８６０Ｄは汚れており、直接８７０Ｂも汚れている。残りのすべてのバッ ファはクリーンである。ここでは、図６で示したＷＡＦＬバッファの簡単化され たものが示されている。この図８における簡単化されたブロック図は図５に示す アルゴリズムを説明するためのものである。 図８において、ＷＡＦＬｉノード８１０はＷＡＦＬバッファ８２０〜８５０， ８６０Ａ〜８６０Ｆ，８７０Ａ〜８７０Ｄのツゥリー構造を参照する。ＷＡＦＬ ｉノード８１０の１６個のバッファポインタ８１０ＡはＷＡＦＬバッファ構造８ １０により参照される。続いて、バッファポインタ８１０Ａは間接ＷＡＦＬバッ ファポインタ８２０〜８５０のそれぞれを参照する。図８において、バッファポ インタ８１０Ａは汚れＷＡＦＬバッファ８２０、汚れＷＡＦＬバッファ８３０、 クリーンＷＡＦＬバッファ８４０、クリーンＷＡＦＬバッファ８５０を参照する 。間接ＷＡＦＬバッファのそれぞれは、１０２４個の直接ＷＡＦＬバッファ（図 ６に示すディスク上のボリュームブロックナンバー６２０Ｃと共に）を参照する １０２４個のバッファポインタから構成される。直接ＷＡＦＬバッファ８６０Ａ 〜８６０Ｂおよび８６０Ｄは汚れている。間接ＷＡＦＬバッファ８２０により参 照される直接ＷＡＦＬバッファ８６０Ｃおよび８６０Ｅ〜８６０Ｆはクリーンで ある。間接ＷＡＦＬバッファ８３０により参照される直接ＷＡＦＬバッファ８７ ０Ｂも汚れている。直接ＷＡＦＬバッファ８７０Ａおよび８７０Ｃ〜８７０Ｄ。 すべての子バッファに対し深さ優先ポストビジトトラバーサルを行う一方、汚 れＷＡＦＬバッファを新しいブロックに割り当てる方法を図４を参照しながら以 下に述べる。ステップ４１０において割り当て書き込みアルゴリズムは、ＷＡＦ Ｌｉノード８１０の１６個のバッファポインタ８１０Ａを参照するＷＡＦＬｉノ ード８１０のＷＡＦＬバッファ構造８１０Ｂのバッファポインタをパスする。判 断 ブロック４２０において、ＷＡＦＬバッファ構造８１０Ｂに含まれるバッファポ インタのすべての子バッファ（この場合間接ＷＡＦＬバッファ８２０〜８５０） のすべてが処理されたか否かが判断される。判断ブロック４２０の結果が偽（Ｎ Ｏ）であったとする。ステップ４４０において間接ＷＡＦＬバッファ８２０が８ １０ＢにおけるＷＡＦＬバッファポインタの子バッファであるとして取り込まれ る。判断ブロック４５０において、問接ＷＡＦＬバッファポインタ４５０がツゥ リー構造における残っているものの中で最下位のものか否かが判断される。判断 ブロック４５０の結果が偽（ＮＯ）であれば、ステップ４６０へ進む。ステップ ４６０では、間接ＷＡＦＬバッファ８２０のバッファポインタをパスすることに より割り当て書き込みアルゴリズムが呼び込まれる。従って、割り当て書き込み アルゴリズムが再帰的に呼び込まれる。 ステップ４１０において、間接ＷＡＦＬバッファ８２０のバッファポインタを パスすることにより割り当て書き込みアルゴリズムが呼び込まれる。判断ブロッ ク４２０において、間接ＷＡＦＬバッファポインタ８２０のすべての直接ＷＡＦ Ｌバッファ８６０Ａ〜８６０Ｆが処理されたか否かが判断される。判断ブロック ４２０の結果が偽（ＮＯ）であったとする。ステップ４４０において、直接ＷＡ ＦＬバッファ８６０Ａが取得される。判断ブロック４５０において直接ＷＡＦＬ バッファ８４０はツゥリー構造において残っているものの内の最下位のものであ るか否かが判断される。判断ブロック４５０の結果が真（ＹＥＳ）であれば、判 断ブロック４８０へ進む。判断ブロック４８０では、直接ＷＡＦＬバッファ８６ ０Ａは汚いか否かが判断される。ここでは判断ブロック４８０からは真（ＹＥＳ ）の結果が得られる。なぜなら、直接ＷＡＦＬバッファ８６０Ａは汚れているか らである。ステップ４９０において、ＷＡＦＬバッファ８６０Ａのバッファポイ ンタを図５に示すスペース割り当てアルゴリズムへパスすることにより直接ＷＡ ＦＬバッファ８６０Ａのスペースが割り当てられる。直接ＷＡＦＬバッファ８６ ０Ａのスペースが割り当てられれば、判断ブロック４２０へと進む。 判断ブロック４２０では、直接ＷＡＦＬバッファ８２０の子バッファのすべて が処理されたか否かが判断される。判断ブロック４２０の結果が偽（ＮＯ）であ ったとする。ステップ４４０で直接ＷＡＦＬバッファ８６０Ｂが取り込まれる。 判断ブロック４５０において、直接ＷＡＦＬバッファ８６０Ｂはツゥリー構造に 残っているレベルの内の最下位のものであるか否かが判断される。判断ブロック ４５０の結果が真（ＹＥＳ）であったとする。判断ブロック４８０において、直 接ＷＡＦＬバッファ８６０Ｂは汚いか否かが判断される。判断ブロック４８０の 結果が真（ＹＥＳ）であるので、ステップ４９０において直接ＷＡＦＬバッファ ８６０Ｂにディスクスペースが割り当てられる。ステップ４９０においてスペー スの割り当ての呼び出しが完了すれば、次に判断ブロック４２０へ進む。 判断ブロック４２０において、間接ＷＡＦＬバッファ８２０のすべての子バッ ファが処理されたか否かが判断される。判断ブロック４２０の結果はここでは偽 （no）となる。ブロック４４０において、直接ＷＡＦＬバッファ８６０Ｃが取り 込まれる。判断ブロック４５０において、直接ＷＡＦＬバッファ８６０Ｃがツゥ リー構造において残っているレベルの内で最も低いレベルであるか否かが判断さ れる。判断ブロック４５０の結果はここでは真（yes）である。判断ブロック４ ８０において、直接ＷＡＦＬバッファ８６０Ｃが汚れているか否かが判断される 。ここでは直接ＷＡＦＬバッファ８６０は修正されておらず、したがってクリー ンであるので判断ブロック４８０の結果は偽（no）である。続いて判断ブロック ４２０が実行される。図４に示すこの間接ＷＡＦＬバッファ８２０の子バッファ に対するスペースの割り当てプロセスは、直接ＷＡＦＬバッファ８６０Ｆ（１０ ２４番目のバッファ）が処理されるまで続行される。直接ＷＡＦＬバッファ８６ ０Ｆ（間接ＷＡＦＬバッファ８２０の最後の子バッファ）はクリーンであるので 、判断ブロック４８０の結果は偽（no）である。続いて判断ブロック４２０が実 行される。判断ブロック４２０において、間接ＷＡＦＬバッファ８２０の子バッ ファ（直接ＷＡＦＬバッファ８６０Ａ〜８６０Ｆ）のすべてが処理されたか否か が判断される。ここでは判断ブロック４２０の結果は真（yes）であるので、ス テップ４３０において呼び出しアルゴリズムが実行される。 ステップ４３０において、再起的呼び出しにより判断ブロック４８０が実行さ れる。判断ブロック４８０において、子バッファ（間接ＷＡＦＬ８２０）が汚い か否かが判断される。判断ブロック４８０の結果はここでは真（yes）であるの で、続いてステップ４９０が実行される。ステップ４９０において、間接ＷＡＦ Ｌバッファ８２０のバッファポインタをパスさせてスペース割り当てアルゴリズ ムを呼び出すことにより間接ＷＡＦＬバッファ８２０に対しディスクスペースが 割り当てられる。ステップ４９０の処理が終わると、判断ブロック４２０が実行 される。判断ブロック４２０において、ＷＡＦＬｉノード８１０のＷＡＦＬバッ ファ構造８１０Ｂに含まれるバッファポインタのすべての子バッファ（間接ＷＡ ＦＬバッファ８２０〜８５０）について処理が終わったか否かが判断される。判 断ブロック４２０の結果はここでは偽（no）である。ステップ１４０において、 間接ＷＡＦＬバッファ８３０が取り込まれる。判断ブロック４５０において間接 ＷＡＦＬバッファ８３０がツゥリー構造に残っているレベルの最も低いレベルで あるか否かが判断される。判断ブロック４５０の結果が偽（no）であるので、続 いてステップ４６０が実行される。ステップ４６０において間接ＷＡＦＬバッフ ァ８３０のバッファポインタをパスすることにより割り当て書き込みアルゴリズ ムが再起的に呼び込まれる。その後図４に示すアルゴリズムを実行するステップ ４１０が開始される。 ステップ４１０において間接ＷＡＦＬバッファ８３０のバッファポインタは割 り当て書き込みアルゴリズムにパスされる。判断ブロック４２０において、間接 ＷＡＦＬバッファ８３０のすべての子バッファ（直接ＷＡＦＬバッファ８７０Ａ 〜８７０Ｄ）が処理されたか否かが判断される。判断ブロック４２０の結果はこ こでは偽（no）であるので、続いてステップ４４０が実行される。ステップ４４ ０において、直接ＷＡＦＬバッファ８７０Ａ（間接ＷＡＦＬバッファ８３０の子 バッファ）が取り込まれる。判断ブロック４５０において、直接ＷＡＦＬバッフ ァ８７０Ａがツゥリー構造における残りのレベルにおける最下位のレベルである か否かが判断される。判断ブロック４５０の結果は真（yes）であるので、続い て判断 ブロック４８０が実行される。判断ブロック４８０において、直接ＷＡＦＬバッ ファ８７０Ａが修正され、したがって汚れた子バッファであるか否かが判断され る。判断ブロック４８０の結果は偽（no）である。なぜなら直接ＷＡＦＬバッフ ァ８７０Ａはクリーンであるからである。続いて判断ブロック４２０が実行され る。 判断ブロック４２０において、間接ＷＡＦＬバッファ８３０の次の子バッファ （直接ＷＡＦＬバッファ８７０Ｂ）が処理されたか否かが判断される。判断ブロ ック４２０の結果が偽（no）であるので、続いてステップ４４０が実行される。 ステップ４４０において、直接ＷＡＦＬバッファ８７０Ｂが取り込まれる。判断 ブロック４５０において、直接ＷＡＦＬバッファ８７０Ｂがツゥリー構造に残っ ているレベルの最下位レベルであるか否かが判断される。判断ブロック４５０の 結果は真（yes）であるので、続いて判断ブロック４８０が実行される。判断ブ ロック４８０において、直接ＷＡＦＬバッファ８７０Ｂが汚れバッファであるか 否かが判断される。判断ブロック４８０の結果が真（yes）であるので、続いて ステップ４９０が実行される。ステップ４９０において直接ＷＡＦＬバッファ８ ７０Ｂのバッファポインタを用いてスペース割り当てアルゴリズムが呼び込まれ ることにより直接ＷＡＦＬバッファ８７０Ｂに対しディスクスペースが割り当て られる。その後判断ブロック４２０が実行される。 親の間接ＷＡＦＬバッファ８３０の残りのクリーンな直接ＷＡＦＬバッファ８ ７０Ｃ〜８７０Ｄは、図４に示すアルゴリズムにより処理される。間接ＷＡＦＬ バッファ８３０の子である残りの直接ＷＡＦＬバッファ８７０Ｃ〜８７０Ｄはク リーンであるので、これらのバッファに対してはディスクスペースは割り当てら れない。判断ブロック４８０において直接ＷＡＦＬバッファ８７０Ｂが汚れてい るか否かの判断がなされるが、その結果は偽（no）である。続いて判断ブロック ４２０が実行される。判断ブロック４２０において間接ＷＡＦＬバッファ８３０ のすべての子バッファ（直接ＷＡＦＬバッファ８７０Ａ〜８７０Ｄ）が処理され たか否かが判断される。判断ブロック４２０の結果が真（yes）であるので、続 いてステップ４３０が実行される。ステップ４３０において、呼び出しアルゴリ ズムが 実行される。続いて判断ブロック４８０が実行される。判断ブロック４８０にお いて間接ＷＡＦＬバッファ８３０が汚れているか否かが判断される。判断ブロッ ク４８０の結果は真（yes）であるので、続いて４９０が実行される。ステップ ４９０において、間接ＷＡＦＬバッファ８３０のバッファポインタをパスし、ス ペース割り当てアルゴリズムを呼び出すことにより、間接ＷＡＦＬバッファ８３ ０に対しディスクスペースが割り当てられる。その後判断ブロック４２０が実行 される。 判断ブロック４２０において、ＷＡＦＬｉノード８１０のＷＡＦＬバッファ構 造８１０Ｂに含まれるバッファポインタの子バッファ（間接ＷＡＦＬバッファ８ ２０〜８５０）のすべてが処理されたか否かが判断される。したがって、間接Ｗ ＡＦＬバッファ８４０〜８５０は、間接ＷＡＦＬバッファ８５０が処理されるま で、上述したように割り当て書き込みアルゴリズムにより再起的に処理される。 判断ブロック４８０において間接ＷＡＦＬバッファ８５０が汚いが否かが判断 されれば、この判断ブロック４８０の結果は偽（no）となる。なぜなら間接ＷＡ ＦＬバッファ８５０はクリーンだからである。その後判断ブロック４２０は実行 される。判断ブロック４２０においてＷＡＦＬｉノード８１０のＷＡＦＬバッフ ァ構造８１０Ｂに含まれるバッファポインタのすべての子バッファ（間接ＷＡＦ Ｌバッファ８２０〜８５０）が処理されたか否かが判断される。判断ブロック４ ２０の結果は真（yes）であるので、この場合は図３に示す主アルゴリズム、す なわち呼び出しアルゴリズムが実行される。したがって、ツゥリー構造における すべてのバッファ、すなわち間接ＷＡＦＬバッファ８２０〜８５０、およびＷＡ ＦＬｉノード８１０（ｉノード８１０は図７に示す汚れｉノードのリスト７１０ のＷＡＦＬｉノード７２０に相当する）により参照される直接ＷＡＦＬバッファ ８６０Ａ〜８６０Ｆおよび８７０Ａ〜８７０Ｄが処理される。図８に示すように ＷＡＦＬｉノード８１０により参照されるツゥリー構造におけるすべてのバッフ ァの深さ優先ポストビジテッドトラバーサルが実行される。このようにして汚れ 子バッファに対し新しいディスクスペースの割り当てが行なわれる。上述したご とく、間接 ＷＡＦＬバッファ８２０が最初に訪問（visit）される。続いて間接ＷＡＦＬバ ッファ８２０の子バッファが順次処理される。間接ＷＡＦＬバッファ８２０の直 接ＷＡＦＬバッファ８６０Ａ〜８６０Ｆはツゥリー構造における残りのレベルの 内の最下位レベルに相当するので、それらが順次処理される。直接ＷＡＦＬバッ ファ８６０Ａは汚れた子バッファであるので、それに対しディスクスペースの割 り当てが行なわれる。これは、直接ＷＡＦＬバッファ８６０Ａ内に含まれた数字 １によって示されるものである。続いて、直接ＷＡＦＬバッファ８６０Ｂ（数字 ２によって示される）に対しディスクスペースの割り当てが行なわれる。直接Ｗ ＡＦＬバッファ８６０Ｃはクリーンであるので、図４のステップ４９０において ディスクスペースの割り当ては行なわれない。このようにして、直接ＷＡＦＬバ ッファ８６０Ａ〜８６０Ｆは、もしそれらが汚れているのであれば、ディスクス ペースの割り当てが行なわれる。 間接ＷＡＦＬバッファ８２０の直接ＷＡＦＬバッファ８６０Ａ〜８６０Ｆが、 一旦処理されると、間接ＷＡＦＬバッファ８２０に対しディスクスペースの割り 当てが行なわれる。これは汚れバッファであるのでディスクスペースの割り当て はステップ４９０において行なわれる。同様に、直接ＷＡＦＬバッファ８７０Ｂ についてもディスクスペースの割り当てが行なわれる。続いて、直接ＷＡＦＬバ ッファ８７０Ｂの親バッファ（間接ＷＡＦＬバッファ８３０）に対しディスクス ペースの割り当てが行なわれる。割り当てはこれで終了したわけだが、バッファ をディスクに書き込む順番は次の通りである。直接ＷＡＦＬバッファ８６０Ａ， ８６０Ｂ，８６０Ｄ；間接ＷＡＦＬバッファ８２０；直接ＷＡＦＬバッファ８７ ０Ｂ；および間接ＷＡＦＬバッファ８３０。 汚れバッファに対するディスクスペースの割り当て 図９Ａはメモリに記憶されたキャシュ９２０と、パリティディスクとデータデ ィスク０〜３で構成されるレードアレイのディスクスペース９１０が示されてい る。図５に示したスペース割り当てアルゴリズムについて、図９の４つのファイ ル９４０〜９４６を参照しながらさらに詳述する。最初、データディスク０〜３ のＣ ＷＬポインタは同じブロックにセットされている。カレント書き込み位置ポイン タ９３０Ａ〜９３０Ｄはそれぞれデータディスク０〜３のデータブロック９５０ Ｂ〜９５０Ｅを参照する。図９に示すように４つのファイル９４０〜９４６はキ ャシュ９２０に含まれている。最初のファイル９４０は２つの汚れブロックＦ１ −０、Ｆ１−１で構成される。第２のファイル９４２は１６個の汚れブロックＦ ２−０からＦ２−１５で構成される。第３のファイル９４４は４つの汚れブロッ クＦ３−０からＦ３−３で構成される。第４のファイル９４６は２つの汚れブロ ックＦ４−０、Ｆ４−１で構成される。ディスクスペース９１０のデータディス ク０〜３において×印は割り当てがなされたブロックを示す。さらに、キャシュ ９２０にはデータディスク０〜３のそれぞれに対応する４つのディスクキュー９ ２０Ａ〜９２０Ｄが示されている。 図７に示すように、４つのファイル９４０〜９４６のそれぞれは汚れｉノード のリスト７１０にあるｉノードを参照する。たとえば、図７において、ｉノード ７２０は第１のファイル９４０を参照する。汚れｉノードのリスト７１０の他の ｉノード７２２、７３０、７４０は、それぞれファイル９４２〜９４６を参照す る。汚れｉノードのリスト７１０にあるこれらのｉノードは、上述したごとく処 理される。以下、ディスク上におけるブロックの割り当て、およびディスクへの ストライプの書き込みについて図５を参照しながら説明する。 図９Ａに示すように、データディスク０〜３のカレント書き込み位置９３０Ａ 〜９３０Ｄは、データブロック９５０Ｂ〜９５０Ｅをそれぞれ参照する。これは ブロック９５０Ｂ〜９５０Ｅのそれぞれの左下コーナにある小さな箱により支持 される。同様に図９Ａに示すように、データディスク０〜３のキュー９２０Ａ〜 ９２０Ｄは空である。図９Ａにおいて、ディスクブロックに付された×印は、デ ィスクスペース９１０においてすでに割り当てが行なわれたブロックであること を示す。垂直に延びるコロムのそれぞれは、データディスク０〜３のそれぞれの ディスクスペース９１０におけるシリンダに対応する。スペース割り当てアルゴ リズムにより処理される最初のファイルは９４０である。 ステップ５１０においてファイル９４０のバッファＦ１−０のバッファポイン タはアルゴリズムにパスされる。判断ブロック５２０において、バッファＦ１− ０は前回のバッファとは異なったファイルにあるのかどうか、または前回のバッ ファとは異なった先読みチャンクにあるのかどうかについて判定される。判定ブ ロック５２０は、ここではバッファＦ１−０は異なったファイルにあるので真（ yes）を出力する。ステップ５３０においてデータディスク０が書き込みのため に選択される。ステップ５４０においてバッファＦ１−０で前回割り当てられた ブロックはフリーにされる。ステップ５５０において、データディスク０のデー タブロック９５２はバッファＦ１−０用に選ばれたディスク上に割り当てる。ま た、ＣＷＬ９３０Ａは進められ、ディスク上の次のフリーな位置を参照する。ス テップ５６０において、ディスクブロック９５２Ｂは、ファイル９４０のバッフ ァＦ１−０に当てられる。ステップ５７０においてバッファＦ０−０は、データ ディスク０のための書き込み可能なバッファのリスト９２０Ａに加えられる。ス テップ５８０において、ＣＷＬに対しそれがファイルシステムの中における最下 位のＣＷＬか否かが判断される。ここではこれは真ではないので、続いて５９０ が実行される。 ファイル９４０において別のバッファＦ１−１は汚れているので、スペース割 り当てアルゴリズムは再び呼び出される。続いてステップ５１０が実行され、バ ッファＦ１−１のポインタがアルゴリズムへパスされる。判断ブロック５２０に おいて、バッファＦ１−１は、前回のバッファ（この場合は、バッファＦ１−０ ）から異なったファイルにあるか否か、または前回のバッファとは異なった先読 みチャンクにあるか否かが判断ざれる。判断ブロック５２０の結果は偽（no）で あるので、続いてステップ５４０が実行される。したがって、バッファＦ１−１ はバッファＦ１−０が書かれたディスクと同じディスクに書き込みがなされる。 図９Ｂに示すように、データブロック９５４Ｂが割り当てられるので、データデ ィスク０において次に割り当てられることができるフリーなブロックはブロック ９５６Ｂである。ステップ５４０において、バッファＦ１−１の前回割り当てら れたブロッ クはフリーにされる。ステップ５４０において、データディスク上にあるブロッ ク９５６Ｂは、バッファＦ１−１用として割り当てられる。ステップ５６０にお いて、ブロック９５６Ｂは、バッファＦ１−１用として割り当てられる。ステッ プ５７０において、バッファＦ１−１は、データディスク０のキュー９２０Ａに 当てられる。データディスク０のＣＷＬ９３０Ａは、データディスク０のブロッ ク９５６Ｂを参照する。ステップ５８０において、ストライプが完成され、ディ スクに送られるのに準備ができたかどうかが判断されるが、この時点ではストラ イプがまだ完成されていない。続いてステップ５９０が実行される。 図９Ｂに示すように、第１のファイル９４０にディスクスペースが割り当てら れたが、バッファＦ１−０およびＦ１−１は、まだディスク上に書き込まれてい ない。それらはデータディスク０のキュー９２０Ａのメモリに記憶されたままで ある。 図９Ｃにおいて、次のファイル９４２がディスクスペース９１０に割り当てら れる。第２のファイル９４２は、１６個の汚れブロックＦ２−０からＦ２−１５ で構成される。ファイル９４２の最初のバッファＦ２−０は、ステップ５１０に おいてアルゴリズムへパスされる。判断ブロック５２０において、バッファＦ２ −０は、前回のバッファ（この場合はバッファＦ１−１）から異なったファイル にあるか否か、または前回のバッファとは異なった先読みチャンクにあるか否か が判断される。ここではバッファＦ２−０は、異なったファイルにあるので、判 断ブロック５２０の結果は真（yes）となる。ステップ５３０において、データ ディスク１が書き込み用として選択される。ステップ５４０において、前に割り 当てられたブロックはフリーにされる。ステップ５５０において、ブロック９５ ２Ｃは、データディスク１の上に割り当てられる。ステップ５６０において、ブ ロック９５２Ｃは、ファイル９４２のバッファＦ２−０に当てられる。ステップ ５７０において、データディスク１のための書き込み可能バッファのリスト９２ ０Ｂに、バッファＦ２−０が加えられる。ステップ５８０において、ストライプ がディスクに書き込み可能かどうかの判断がなされる。しかしながら、この時点 におい ては書き込まれるべきブロックはレードアレイにおける最下位のＣＷＬよりも低 いブロックではないので、ストライプは書き込み可能な状態ではないことがわか る。したがって、続いてステップ５１０のアルゴリズムが実行される。 図４に示すアルゴリズムは、Ｆ２−１のための汚れファイルバッファのポイン タを、図５に示すステップ５１０Ａへパスする。判断ブロック５２０において、 バッファＦ２−１は、前回のバッファ（Ｆ２−０）から異なったファイルにある か否か、または前回のバッファとは異なった先読みチャンクにあるか否かが判断 される。判断ブロック５２０の結果は偽（no）であるので、続いてステップ５４ ０が実行される。ステップ５４０において、ブロック９５４Ｃがフリーにされる 。ステップ５５０において、データディスク１のブロック９５４Ｃが割り当てら れる。ステップ５６０において、ブロック９５４ＣがバッファＦ２−１に割り当 てられる。ステップ５７０において、バッファＦ２−１は、データディスク１の ための書き込み可能なバッファのリスト９２０Ｂに加えられる。ステップ５８０ において、データディスク１のＣＷＬ９３０Ｂは、ブロック９５４Ｃに進められ る。次に、ストライプがディスクに書き込み可能かどうかの判断がなされる。し かしながら、ここではデータディスク１のＣＷＬ９３０Ｂはディスクスペース９ １０におけるＣＷＬポインタの最下位のものではないので、ストライプの書き込 みは可能でない。したがって、続いてステップ５９０が実行される。 図５に示すアルゴリズムに従い、バッファＦ２−２からＦ２−６は、ディスク 上のスペースが割り当てられる。８番目のバッファＦ２−７のためにスペース割 り当てアルゴリズムが呼びだされれば、判断ブロック５２０において、バッファ Ｆ２−７は、前回のバッファ（Ｆ２−６）から異なったファイルにあるか否か、 または前回のバッファとは異なった先読みチャンクにあるか否かが判断される。 判断ブロック５２０の結果は偽（no）であるので、続いてステップ５４０が実行 される。ステップ５４０ではブロック９６８Ｃがフリーにされる。ステップ５５ ０で、ブロック９６８Ｃがデータディスク１に割り当てられる。ステップ５６０ において、ブロック９６８ＣがバッファＦ２−７に割り当てられる。ステップ５ ７０に おいて、バッファＦ２−７は、データディスク１のための書き込み可能バッファ のリスト９２０Ｂに加えられる。ステップ５８０において、もし可能な場合はス トライプの書き込みがなされる。ここでブロック９７０は、すでに割り当てられ ているので、データディスク１のＣＷＬ９３０Ｂは、ブロック９７０へ進められ る。データディスク１のブロック９７０Ｃは、ディスクスペース９１０における 最下位のＣＷＬではないので、ディスクにストライプは書き込みはまだなされな い。 図５のステップ５１０において、ファイル９４２のバッファＦ２−８用のバッ ファポインタがパスされることにより、スペース割り当てアルゴリズムが呼び出 される。判断ブロック５２０においてバッファＦ２−８は前回のバッファ（Ｆ２ −７）から異なったファイルにあるか否か、または前回のバッファ（Ｆ２−７） とは異なった先読みチャンクにあるか否かが判断される。ファイル９４２の８個 のバッファＦ２−０からＦ２−７は、前回の先読みチャンクの１部であり、すで にスペースの割り当てが行なわれていたので、判断ブロック５２０の結果は真（ yes）となる。ステップ５３０において、データディスク２が書き込み用として 選択される。これは図９Ｂに示されている。 ステップ５３０において、最も低いカレント書き込み位置情報を有するディス クを見つけることにより、ディスクの選択がなされる。もし複数のディスクが最 も低いカレント書き込み位置情報を有していたのであれば、最初に位置するもの が選択される。 ステップ５４０において、バッファＦ２−８の前に割り当てられたブロックが フリーにされる。ステップ５５０においてブロック９５２Ｄは、データディスク ２上に割り当てられる。ステップ５６０において、ブロック９５２Ｄは、バッフ ァＦ２−８に当てられる。ステップ５７０において、データディスク２のキュー ９２０ＣにバッファＦ２−８が加えられる。ステップ５８０において、可能な場 合はストライプの書き込みがなされる。しかしながら、ここではバッファＦ２− ８のためのディスクにストライプを一気に送り出すための準備はできていない。 し たがってステップ５１０が実行される。 ステップ５１０において、ファイル９４２のバッファＦ２−９のためのポイン タは、スペース割り当てアルゴリズムにパスされる。判断ブロック５２０におい て、バッファＦ２−９は、前回のバッファ（Ｆ２−８）から異なったファイルに あるか否か、または前回のバッファとは異なった先読みチャンクにあるか否かが 判断される。ここでは、バッファＦ２−９は前回のバッファＦ２−８と同じファ イルで同じ先読みチャンクにあるので、判断ブロック５２０の結果は偽（no）で ある。ステップ５４０において、データディスク２のブロック９５４Ｄは、バッ ファＦ２−９のためにフリーにされる。ステップ５５０において、ブロック９５ ４Ｄは、データディスク２上に割り当てられる。ステップ５６０において、デー タディスク２のブロック９５４Ｄは、バッファＦ２−９に当てられる。ステップ ５７０において、バッファＦ２−９は、データディスク２のための書き込み可能 なバッファのリスト９２０Ｃに加えられる。ステップ５８０において、ディスク にストライプの書き込みが試みられるが、この時点ではまだストライプの書き込 みは可能ではない。 図９Ｄに示すように、ディスクブロック９５２Ｄから９６８Ｄは、ファイル９ ４２のバッファＦ２−８からＦ２−１５のために割り当てられる。図５に示すア ルゴリズムに基づき、汚れバッファＦ２−８からＦ２−１５のためにブロックが 割り当てられるので、バッファＦ２−８からＦ２−１５は、データディスク２の ための書き込み可能なバッファのリスト９２０Ｃに加えられる。ステップ５８０ において、システムは、ディスクにストライプの書き込みを試みる。しかしなが ら、この時点ではまだ完全なストライプを書き込みすることができない。ステッ プ５９０において呼び出しアルゴリズムが実行される。 汚れｉノードのリスト７１０にあるｉノードを参照して得られる第３のファイ ルは、９４４である。ファイル９４４は、４つの汚れブロックＦ３−０からＦ３ −３で構成される。ファイル９４４の汚れバッファＦ３−０からＦ３−３は、ス ペース割り当てアルゴリズムにより処理される。ファイル９４４の汚れバッファ の 割り当てを、図９Ｅから９Ｆを参照しながら説明する。ステップ５１０において 、スペース割り当てアルゴリズムは、ファイル９４４のバッファＦ３−０のバッ ファポインタにパスされる。判断ブロック５２０において、ファイル９４４のバ ッファＦ３−０は、前回のバッファ（ファイル９４２のバッファＦ２−１５）か ら異なったファイルにあるか否か、または前回のバッファとは異なった先読みチ ャンクにあるか否かが判断される。判断ブロック５２０はここではバッファＦ３ −０が異なったファイルにあるので、真（yes）を出力する。ステップ５３０に おいて、１番低いＣＷＬ（データブロック９５０Ｅについて示された図９Ｄを参 照）を有するデータディスク３が、書き込み用のディスクとして選択される。ス テップ５４０において、バッファＦ３−０のために前回割り当てられたブロック は、フリーにされる。これは、ブロック９５２Ｅのためのblkmapファイルのすべ てを更新して、ブロック９５２Ｅが、もはやアクティブファイルシステムによっ て利用されるものではないことを示すことにより達成される。ステップ５４０に おいて、データディスク３の現在の（カレント）ブロック９５２Ｅが割り当てら れる。これはデータディスク３のカレント書き込み位置（ＣＷＬ）９３０Ｄを、 データブロック９５２Ｅに進めることにより達成される。ステップ５６０におい て、ブロック９５２Ｅは、ファイル９４４のバッファＦ３−０に当てられる。ス テップ５７０において、バッファＦ３−０は、データディスク３のための書き込 み可能なバッファのリスト９２０Ｄに加えられる。 ステップ５８０において、可能な場合は、ストライプがディスクに書き込まれ る。これはデータディスク０〜３のバッファ９２０Ａ〜９２０Ｄをチェックして 、完成したストライプがあるか否かを見ることにより、達成される。図９Ｅにお いて、完成されたストライプは、バッファＦ１−０、Ｆ２−０、Ｆ２−８、Ｆ３ −０からなるディスクキュー９２０Ａ〜９２０Ｄに含まれる。これらのバッファ は、１つのグループとしてレードサブシステムに送り出され、効率よく書き込み がなされる。この状態は図９Ｅに示されており、ストライプ９８０は、パリティ ブロック９５２Ａと、データディスク０〜３のデータブロック９５２Ｂ〜９５２ Ｅに書 き込まれる。ここでストライプは点線で囲まれて示されている。したがって、バ ッファＦ１−０は、データディスク０のブロック９５２Ｂに書き込まれる。同様 に、バッファＦ２−０、Ｆ２−８、Ｆ３−０は、それぞれブロック９５２Ｃ、９ ５２Ｄ、９５２Ｅに書き込まれる。図９Ｅに示すように、データディスク３の最 も低いカレント書き込み位置（ＣＷＬ）９３０Ｄは、ブロック９５２Ｅに位置し ている。ストライプ５８０がディスクに書き込まれることにより、バッファＦ１ −０、Ｆ２−０、Ｆ２−８、Ｆ３−０は、キュー９２０Ａ〜９２０Ｄから削除さ れる。これは図９Ｅに示されている。続いて呼び出しルーチンであるステップ５ ９０が実行される。 ファイル９４４のバッファＦ３−１のバッファポインタは、ステップ５１０に おけるスペース割り当てアルゴリズムにパスされる。判断ブロック５２０におい て、バッファＦ３−１は、前回のバッファから異なったファイルにあるか否か、 または前回のバッファとは異なった先読みチャンクにあるか否かが判断される。 判断ブロック５２０の結果は偽（no）であるので、続いてステップ５４０が実行 される。ステップ５４０において、バッファＦ３−１に前回割り当てられたブロ ックは、フリーにされる。ステップ５５０において、ブロック９５４Ｅがデータ ディスク３に割り当てられる。データディスク３のカレント書き込み位置９３０ Ｄは、図９Ｅに示すブロック９５２Ｅから、図９Ｆに示すブロック９５６Ｅに進 められる。カレント書き込み位置９３０Ｄは、ブロック９５６Ｅに進められ、こ れは現在割り当てられたブロック９５４Ｅを下に越えることになる。なぜなら、 ブロック９５６Ｅはすでに割り当て（ブロックにおいて×印で示されている部分 ）がなされているからである。ステップ５６０において、ブロック９５４Ｅは、 ファイル９４４のバッファＦ３−１に当てられる。ステップ５７０において、バ ッファＦ３−１はデータディスク３のための書き込み可能なバッファのリスト９ ２０Ｄに加えられる。ステップ５８０において、２つのストライプ９８２、９８ ４は、ディスクに書き込まれる。これはデータディスク０および３にある最も低 いカレント書き込み位置９３０Ａ、９３０Ｄが、データブロック９５６Ｂ、９５ ６Ｅを参照 することによりなされる。図９Ｆに示すように、バッファＦ２−１、Ｆ２−９、 Ｆ３−１で構成されるストライプ９８２は、ブロック９５４Ｃから９５４Ｅに書 き込まれる。同様にストライプ９８４もディスクに書き込まれる。ストライプ９ ８２および９８４がディスクに書き込まれれば、対応するバッファは、リスト９ ２０Ａ〜９２０Ｄから削除される。ステップ５９０において呼び出しアルゴリズ ムが次に実行される。 同様に、図５に示すアルゴリズムにより、ファイル９４４のバッファＦ３−２ 、Ｆ３−３には、ディスクブロック９５８Ｅ、９６０Ｅが割り当てられる。図９ Ｇに示すように、ファイル９４４のバッファＦ３−２、Ｆ３−３は、データディ スク３のリスト９２０Ｄに割り当てられる。ファイル９４４に対しカレント書き 込み位置９３０Ｄは、データディスク３のブロック９６０Ｅに進められる。図９ Ｇに示すように、最も低いカレント書き込み位置は、データブロック９５６Ｂを 参照するデータディスク０のカレント書き込み位置９３０Ａである。他のカレン ト書き込み位置９３０Ｂ〜９３０Ｄは、データディスク１〜３のブロック９７０ Ｃ、９６８Ｄ、９６０Ｅを参照する。さらに図９Ｇに示すように、データディス ク０のキュー９２０Ａは空である。データディスク１のための書き込み可能なバ ッファのリスト９２０Ｂには、ファイル９４２のバッファＦ２−３からＦ２−７ がある。データディスク２のリスト９２０Ｃは、ファイル９４２の残りの汚れバ ッファＦ２−１１からＦ２−１５がある。データディスク３のリスト９２０Ｄに はファイル９４４の汚れバッファＦ３−２からＦ３−３がある。 汚れバッファＦ４−０からＦ４−１からなる第４のファイル９４６は、図５に 示すアルゴリズムを用いてディスクスペースの割り当てがなされる。ステップ５ １０において、ファイル９４６の汚れバッファＦ４−０は、スペース割り当てア ルゴリズムにパスされる。判断ブロック５２０において、バッファＦ４−０は前 回のバッファ（Ｆ３−３）から異なったファイルにあるか否か、または前回のバ ッファとは異なった先読みチャンクにあるか否かが判断される。ここではバッフ ァＦ４−０は異なったファイルにあるので、判断ブロック５２０の結果は真（ye s） となる。ステップ５３０において、ディスクスペース９１０における最も低いカ レント書き込み位置がどこにあるかの判断がなされる。図９Ｇに示すように、最 も低いカレント書き込み位置は、データディスク０のブロック９５６Ｄを参照す る、カレント書き込み位置９３０Ａであることがわかる。したがって、ステップ ５３０において、データディスク０が書き込み用に選択される。ステップ５４０ において、データディスク０のバッファＦ４−０に前回割り当てられたブロック は、フリーにされる。ステップ５５０において、ブロック９５８Ｂは、データデ ィスク０に割り当てられる。これによりデータディスク０のカレント書き込み位 置９３０Ａは、ブロック９５６Ｂから９５８Ｂへ進められる。これは図９Ｈにお いて、左下コーナにおける実線で示されている。ステップ５６０において、ブロ ック９５８Ｂは、バッファＦ４−０に割り当てられる。ステップ５７０において 、バッファＦ４−０は、データディスク０のための書き込み可能なバッファのリ スト９２０Ａに加えられる。ステップ５８０において、バッファＦ４−０、Ｆ２ −１１、Ｆ３−２で構成されるストライプ９８６は、ディスクに書き込まれ、こ れはバッファはキュー９２０Ａ、９２０Ｃ〜９２０Ｄから削除される。ステップ ５９０において続いて呼び出しアルゴリズムが実行される。 図９１において、ファイル９４６の汚れブロック４Ｆ−１は、ステップ５１０ におけるスペース割り当てアルゴリズムへパスされる。判断ブロック５２０にお いて、今回のバッファは前回のバッファから異なったファイルにあるか否か、ま たは前回のバッファとは異なった先読みチャンクにあるか否かが判断される。判 断ブロック５２０の結果は偽（no）であるので、続いてステップ５４０が実行さ れる。ステップ５４０で前回に割り当てられたブロックがフリーにされる。ステ ップ５５０においてデータディスク０のブロック９６０Ｂが割り当てられる。こ れにより、データディスクのカレント書き込み位置９３０Ａは、ブロック９５８ Ｂから９６０Ｂへ進められる。ステップ５６０において、割り当てられたブロッ ク９６０Ｂは、バッファＦ４−１に当てられる。ステップ５７０において、ファ イル９４６のバッファＦ４−１は、データディスク０のための書き込み可能なバ ッ ファのリスト９２０Ａに加えられる。ステップ５８０において、ストライプ９８ ８がディスクに書き込まれる。これは、ストライプ９８８に、最も低いカレント 書き込み位置９３０Ａを含むブロック９６０Ａ〜９６０Ｅが含まれるからである 。バッファＦ４−１、Ｆ２−３、Ｆ２−１２、Ｆ３−３は、それぞれリスト９２ ０Λ〜９２０Ｄから削除される。ステップ５９０において続いて呼び出しアルゴ リズムが実行される。図９１に示すように、データディスク０〜３のカレント書 き込み位置９３０Ａ〜９３０Ｄは、ブロック９６０Ｂ、９７０Ｃ、９６８Ｄ、９ ６０Ｅを参照する。最も低い位置にあるカレント書き込み位置９３０Ａより、さ らに低い位置に割り当てられたブロックは、図９１に示すようにディスクに送り 出される。しかしながら、データディスク１、２のリスト９２０Ｂ、９２０Ｃに 加えられたファイル９４２の汚れバッファＦ２−４からＦ２−７、およびＦ２− １３からＦ２−１５は、ディスクＡから送出されないで残されている。 図９Ｊは、すべての汚れｉノードにブロック割り当てがなされた後、残された 未書き込みのバッファ、すなわちファイル９４４のバッファＦ２−４からＦ２− ７、およびＦ２−１３からＦ２−１５のディスクへの送り出しを示す。この例に おいては、すべてのデータディスク０〜３のカレント書き込み位置９３０Ａ〜９ ３０Ｄは、図９１の最も高いカレント書き込み位置９３０Ｂにまで進められてい る。したがってキュー９２０Ａ〜９２０Ｄは空にされる。カレント書き込み位置 ９３０Ｂは、データディスク１のブロック９７０Ｃを参照する。この動作は、図 ３のステップ３５０が実行されることにより、すべての未書き込みのストライプ がディスクに送り込まれる。ステップ３５０において、カレント書き込み位置９ ３０Ａ〜９３０Ｄをグループの内で最も大きな値を有するものに進めることによ り、ディスクにまだ送り込まれていないバッファであってデータディスク０〜３ のキュー９２０Ａ〜９２０Ｄにあるすべてのバッファは、強制的にディスクに送 り込まれる。 上述したごとく、本発明はレードアレイのディスクレイアウトの手順を用いな がら、レードアレイへの書き込み割り当てを最適なものにするものである。レー ドレイアウトの手順には、ディスクに書き込まれるべきバッファのディスクブロ ックや、ストライプに関する情報が含まれる。これは図９Ａ〜９Ｊに示されてい る。本発明は、レードアレイ技術を有するファイルシステムを、より完全なもの にするものである。レード層は、レードサブシステムにおけるデータブロックの 配列に関する、より詳しい情報をファイルシステムに送るものである。ファイル システムはこの情報を審査し、それらがレードシステムに書き込まれるのに従い 、ブロックの位置を最適なものにするのに用いられる。レードシステムへの書き 込みの最適化は先読みチャンクをより良いものにすると共に、ストライプ全体を 書き込むことにより達成される。 ストライプの負荷感知式書き込み 上述したＷＡＦＬファイルシステムのためのレードアレイに書き込み割り当て するための方法は、“循環書き込み”アルゴリズムを用いたものである。この方 法は、ディスクを循環してバッファをレードアレイに書き込むもので、１本のス トライプのすべてのディスクブロックに割り当てが行なわれるものである。スト ライプへの順次書き込みは、少なくとも１つのブロックがフリーにされなければ ならないという点を除いて、ストライプにおいて割り当てられるフリーブロック の数に依存するものではない。このようにして、ストライプへの書き込み割り当 ては、レードアレイにおけるディスクの最後まで進められる。ディスクの最後に 達すれば、書き込み割り当ては、ディスクの始めに戻り、そこから続けられる。 本発明の別の実施の形態においては、ディスクへのデータ書き込みへの速さが 、通常のしきい値を越えれば、“負荷感知式書き込み”により、ディスクへの書 き込みが行なわれるものである。データ書き込みの速さが通常のしきい値を越え れば、本発明では、ディスクの書き込みをストライプの書き込みの効率に依存す るように、ディスク書き込みの処理を行う。レードアレイにおける各ディスクの エリアに割り当てられたブロックのパターンによって、ディスクのある部分につ いては、他の部分より、より容易に書き込みがなされることがある。たとえば、 データディスク上のストライプに割り当てられたブロックがない場合は、レード アレイにス トライプを書き込むことは非常に効率的である。 図９Ｅに示すように、ストライプ９８０に対し４つのディスクブロック９５２ Ｂ〜９５２Ｅを書き込むことは、レードアレイおいて最も効率よく書き込みが行 なわれる。具体例においては、４つのバッファＦ１−０、Ｆ２−０、Ｆ２−８、 Ｆ３−０は、実質的に同じ時間Ｔ_WRITEにディスクに書き込みが行なわれる。し たがって、４ＫＢバッファを用いることにより、所定の時間Ｔ_WRITEに１６ＫＢ のデータをディスクに書き込むことが可能である。これは、図９Ｆで示すレード アレイの３つのブロック９５４Ｃ〜９５４Ｅに、バッファＦ２−１、Ｆ２−９、 Ｆ３−１からなるストライプ９８２を書き込むことと対照的である。この場合の 書き込み速さは、所定時間Ｔ_WRITEに１２ＫＢのデータを書き込むことができる 。したがってストライプ９８２の書き込み速さは、ストライプ９８０の最大書き 込み速さの７５％である。最悪の場合、レードアレイのストライプには、単一の 割り当てられていないディスクブロックのみが存在するだけである。この単一ブ ロックへの書き込みは、４つのディスクブロックに書き込む最大速さの２５％で 書き込みをなすことが可能である。したがって、１つのフリーブロックのみでス トライプに書き込みを行うことは非効率的である。 循環書き込みを行う負荷感知式書き込みにおいては、レードサブシステムがビ ジーであれば、非効率的なストライプはスキップされる。すなわち、多くの書き 込まれるべきフリーブロックを有するストライプが、割り当てのために選択され る。システムの負荷が軽い場合にのみ非効率的なストライプの書き込みが許され る。これは、システムの負荷が重たい場合に、より多くの効率のよいストライプ を残しておくために行なわれるものである。したがって、同じシーケンスにおい て、ブロックと汚れファイルの特定のセットを書き込む循環式書き込み方法とは 異なり、負荷感知式循環書き込み方法は、負荷の重さによってその動作を変える ものである。たとえば、５メガバイト／秒の最大書き込み速さを有するレードシ ステムにおいては、本発明においては、１０秒のインターバルに１秒当たり２． ５メガバイトの平均速さで書き込みを行なうシステムであれば、３または４個の フリーブロックを有するストライプを書き込む。 本発明においては、レードディスクシステムを備えたファイルシステムを、よ り効率よく動作させるためには、上述の負荷感知式循環書き込み方法により大き な規模のアルゴリズムを加えることも可能である。以上詳述したごとく、レード アレイのレイアウトに関する情報を、ファイルシステムに与えることは、この利 点を受ける規模の大きなアルゴリズムも可能とするものである。 以上のように、レードアレイを用いたファイルシステムにおいてファイルを割 り当てる方法が説明された。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 マルコム、マイケル アメリカ合衆国カリフォルニア州94022、 ロス・アルトス、サウス・アバロン・ドラ イブ48番 (72)発明者 ラウ、ジェイムズ アメリカ合衆国カリフォルニア州95014、 カパチノ、アップランド・ウェイ11570番 (72)発明者 ラキチス、バイロン アメリカ合衆国カリフォルニア州94043、 マウンテン・ビュー、ノース・ウィッシマ ン・ナンバー130、100番 【要約の続き】 たはあるファイルに同じディスク（１０２２）のＮ個の ブロックに割り当てがおこなわれたときのみに、別のデ ィスクが選択されることにより達成される。その結果、 ＣＷＬポインタは異なったディスク（１０２４）上でも Ｎブロック以上離れることはなく、大きなファイルも、 同じディスクにＮ個の連続するブロックに収めることが できる。

Claims (1)

1. 【特許請求の範囲】 １．ファイルシステムにおいてファイルの割り当てを行なう方法であって、 （a）汚れブロックを有するｉノードのリストから、少なくとも１つの汚れブ ロックを有するｉノードを選択し、 （b）レードアレイにおける記憶手段に、該ｉノードを参照することにより、 割り当てられたバッファのツゥリー構造を書き込み、 （c）ｉノードのリストのすべてのｉノードが未処理であれば、上記ステップa −bを繰り返し実行し、ｉノードのリストにあるすべてのｉノードが処理された か否かを判断し、レードアレイにすべての未書き込みストライプを送り出すよう にしたことを特徴とする方法。