以下に、本発明の実施の形態によるフラ� ��シュメモリのファイルシステムについて図� ��を参照しながら説明を行う。図1は、本発明 の第1の実施の形態によるファイルシステム� �適用可能な機器の一例として示す電子機器� �一構成例を示す機能ブロック図である。図1� ��示すように、本実施の形態による電子機器A は、全体を制御する制御装置(CPU)1と、機器を 制御するためのプログラムやデータファイル などを格納する不揮発性のフラッシュメモリ 3と、RAMなどの揮発性のメモリ5と、データの� ��出力が行われるデータ入出力手段15と、ユ� �ザが入力を行う入力手段7と、入力されたデ� ��タが処理されて出力されるその出力に基づ� ��情報を表示する表示手段11と、を有してい� �。

 上記電子機器におけるファイルシステム� ��は、ファイルがフラッシュメモリの領域の� ��こを使用しているかというファイル構成情� ��を、フラッシュメモリの特定の領域に記憶� ��るのではなく、マウント処理(ファイルシス テムの初期化処理)時にファイル構成情報を� �モリ5上に再構成するようにするものであり� ��これをNAND型フラッシュメモリに適用する場 合の実施例について以下に詳細に説明する。 図2は、NAND型フラッシュメモリの領域構成例� ��示す図である。図2に示すように、ファイル Xは、一つ以上のブロックYからなり、ブロッ� ��Yは、ページZから構成されている。このよ� �に、NAND型フラッシュメモリは、複数のブロ� ��クからなり、また、ブロックは複数のペー� ��からなる。図3は、ブロック情報のバリエー ションを示す図である。例えば、ファイルX� �ブロックA、B、C(Y)から構成されるとして、� �ータ23に付加されるブロック情報25・27・31・ 33は、図3(A)のように各ブロックA、B、Cで同じ ものを保持しておいても、図3(B)に示すよう� �ブロックによって異なるものを保持してお� �てもよい。図3(B)の場合では、ファイルを構� ��する先頭ブロック(ブロックA’:矢印の一番� ��に存在するブロック、矢印はアクセス順を� ��す)にのみ、ファイル名とファイルサイズと からなるブロック情報21を持つようになって� ��る。

 データの書き込みの際には、それに先立� ��消去を行う必要がある。消去はブロック単� ��で行われ、書き込みはページ単位で行われ� ��。また、ページは、通常のデータを書き込� ��データ領域と、冗長データを書き込むOOB(Out  Of Band)領域にわけられるのが一般的である� ��OOB領域には、データ領域に書かれたデータ� ��誤りを訂正する誤り訂正符号を格納する領� ��と、そのブロックがバッドブロックである� ��どうかを示す領域などを有している。

 これは、NAND型フラッシュメモリの特性上 、書き込み時に誤ったデータを書いてしまう ことがあり、このままでは、次にそれを読み 出した場合、誤ったデータが読み出されてし まうため、その誤りを訂正するための訂正符 号を格納する領域が備わっているためである 。訂正符号だけでは訂正しきれない程度の誤 りが発生する場合には、それが発生するペー ジを含むブロックをバッドブロックとして扱 う。バッドブロックは、その先頭ページのOOB 領域でバッドブロックであることが記されて いる。バッドブロックは、製造工程によって 最初からバッドブロックになっているものと 、消去と書き込みを繰り返すことで劣化が進 み、後天的にバッドブロックになるものがあ る。

 以下に、本明細書において使用される用� ��についての定義を示す。

1)フリーブロック:消去済みのブロック。こ の状態でデータの書き込みが行えるブロック である。

2)妥当ブロック:本ファイルシステムにより 書き込まれたデータを保持しているブロック 。ファイルを構成するブロックと成りえる。

3)無効ブロック:フリーブロックでも妥当ブ ロックでもないブロック。消去が必要なブロ ックである。ブロックへの書き込み中に電源 断されたか、もしくは、本ファイルシステム において、消去が必要と判断して明示的に無 効ブロックとしたかのいずれかである。

4)バッドブロック:物理的に使用不可能なブ ロックである。出荷時から存在する初期バッ ドブロックと、書き込みを繰り返しているう ちに発生する後天的なバッドブロックがある 。いずれも、OOBのある部分にその情報がマー クされており、正常なブロックとの判別は可 能である。なお、上記3つのブロックは正常� �ブロックに関してのことである。

5)フリーブロックリスト:フリーブロックを 格納しているリストであり、RAM上に存在する リストである。

6)チェックブロックリスト:妥当ブロックを 格納しているリストであり、RAM上に存在する リストである。

7)イレースブロックリスト:無効ブロック、 および、妥当ブロックの中でも消去可能なブ ロックを格納しているリストであり、RAM上に 存在するリストである。

8)バッドブロックリスト:バッドブロックを 格納しているリストであり、RAM上に存在する リストである。

9)妥当ファイル/妥当ファイル候補:必要十� �な妥当ブロックから構成され、本ファイル� �ステムのデータ構造に従ったファイルと判� �されるファイルである。同名のファイルも� �在する。妥当ファイル候補は、ブロックは� �っているが一部データが不足している可能� �があるファイルである。妥当ファイルは妥� �ファイル候補のサブセットとなる。

10)不完全ファイル:本ファイルシステムの� �ータ構造に従っていない異常なファイルと� �断されるファイルである。構成ブロックが� �足しているファイル、必要なデータが書き� �まれていないファイルなどが該当する。

11)有効ファイル:妥当ファイルの一つであ� �、妥当ファイルの中に同名のファイルが存� �する場合、最後に正常に書き込まれたファ� �ルを指す。同名のファイルが存在しない場� �は、そのファイル自身である。ただし、「� �去を示すファイル」ではないものとする。

12)無効ファイル:妥当ファイルのうちでも� �有効ファイルではないファイルである。こ� �より新しい同名のファイルが存在している� �、もしくは「消去を示すファイル」である� �

13)ファイルID:ファイルの書き込み時にファ イルに付与される、本ファイルシステム内で ユニークなIDである。再利用されない。例え� ��、次に付与するファイルID = 過去に付与し た最大ファイルID + 1などとする。

14)ブロックID:ブロックを識別するための通 し番号。

15)ブロック番号:ファイル内のブロックの� �し番号。

次に、マウント処理について図面を参照し ながら説明する。

 本実施の形態によるファイルシステムは� ��ファイル構成情報を特定のブロックに記録� ��ず、各ブロックに対して、ブロック情報付� ��手段によりブロック情報を付加し、このブ� ��ック情報を記録しておくことで、マウント� ��にブロック情報からファイル構成情報再構� ��手段によりファイル構成情報を構築するこ� ��を特徴とする。すなわち、マウント処理に� ��いて、すべての有効なブロックのブロック� ��報を読み込み、同一のファイルIDを持つブ� �ックを集める。そして、正しくファイルが� �構成できるブロックから、ファイル構成情� �を生成する。

 尚、ブロック情報付加手段は、ブロック� ��の書き込みデータの生成時に、該当するブ� ��ックに対してブロックに関する情報を付加� ��る手段であり、一般的にはプログラムによ� ��制御装置が行うのが一般的だが、専用のハ� ��ドウエアにより付加するようにしても良い� ��図3に示すブロックの構成例では、既にブロ ック情報が付加された後の状態が示されてい る。

 ファイル構成情報再構築手段は、マウン� ��時に、上記ブロック情報に基づいてファイ� ��構成情報を再構成する手段であり、一般的� ��はプログラムにより制御装置が行うことに� ��るが、専用のハードウエアにより再構成す� ��ようにしても良い。図7に示すフローチャー トでは、ブロックを取り出してから再構成が 終了するまでのプログラムが示されている。 この処理がファイル再構成手段による処理に 相当する。

 ファイルIDは、ファイルID付与手段により 、付与される。ファイルID付与手段は、ファ� ��ル書き込み時に、ファイルを識別するため� ��システム内でユニークなファイルIDを付与� �る手段である。なお、ファイルIDは、ブロッ ク情報付加手段により、ブロック情報の一つ として、ブロックに書き込まれる。

 マウントの第一段階では、領域内の全て� ��ブロックをスキャンし、フリーブロック、� ��当ブロック、無効ブロック、バッドブロッ� ��を判断して、それぞれのリストにブロック� ��つなぐ。

 より具体的には、各ブロックの先頭ページ� ��OOB領域にバッドブロックであることが記録� ��れているか、記録されていない場合、ブロ� ��クに所定のマジックナンバーが書き込まれ� ��いるかどうかで判断する。マジックナンバ� ��が書き込まれるのはデータ領域でもOOB領域� ��もどちらでもよいが、ブロックがバッドブ� ��ックであるかどうかを判断するためにはOOB� ��域を読み込む必要があるため、マジックナ� ��バーもOOB領域に書き込んでおけば同時に判� ��でき処理が簡単になる。したがって、各ブ� ��ックの先頭ページと最終使用ページのOOB領� ��にマジックナンバーが書かれているかどう� ��で判断する。ブロックチェック手段は、ブ� ��ックの有効性を判断するために、このよう� ��判断を行う手段であり、一般的にはプログ� ��ムにより制御装置が行うことになるが、専� ��のハードウエアによってチェックするよう� ��してもよい。このような判断を行えるよう� ��するために、ブロックへのデータの書き込� ��を行う際に、マジックナンバー付加手段に� ��り、マジックナンバーとそのブロックの使� ��ページ数がOOB領域に書き込まれる。マジッ� ��ナンバー付加手段は、一般的にはプログラ� ��により制御装置が行うことになるが、専用� ��ハードウエアにより付加するようにしても� ��い。また、消去済みのブロックは、通常、� ��ットが全て1となる(マジックナンバーとし� �は、それが16ビットであれば0xffffとなる)。� �のとき、判断基準は次の表1に示すようにな� ��。

 ここで、以下のようにすることで、マウ� ��ト時のブロックの有効性の判断を高速化す� ��ことができる。図8を参照しながら説明を行 う。高速化の一手法は、ブロックの2カ所以� �に上述のマジックナンバーを書き込むため� �マジックナンバー領域を設けることで達成� �きる。すなわち、ブロックの有効性を判断� �るには、データが正しく書き込まれたかど� �かを確認すればよい。ブロック全体を読み� �んでデータの整合性をチェックするのは時� �がかかるため、データがブロックの先頭か� �順番に書き込まれていくのであれば、先頭� �近と最後付近で正しいデータが書き込まれ� �いるか確認するだけでよいことになる。そ� �で、ブロックの先頭付近と最後付近にマジ� �クナンバーを記載する領域を設けておく。� �のマジックナンバーだけを読むことで、ブ� �ックの有効性を高速に判断することができ� �。さらに、ブロック書き込み中の電源断の� �無の判断も容易となる。

 図8(A)は、上記手法を実現するためのブロ ック構成例を示す図である。図8(A)に示すよ� �に、ブロックYは、データ1領域73aと、マジッ クナンバー1領域71aと、データ2領域73bと、マ� ��ックナンバー2領域71bと、データ3領域73cと� �ページ順で構成されている。マジックナン� �ーはデータ領域にあってもOOB領域にあって� �よいので、図ではデータ領域とOOB領域の区� �はしていない。しかし、マジックナンバー� �OOB領域にあるほうが望ましいので、OOB領域� �書き込まれているものとする。また、マジ� �クナンバー1領域71aはブロックの先頭ページ� ��、マジックナンバー2領域71bはブロックの先 頭以外のページに、それぞれ存在するとする 。上記表1に記載した判断基準に基づいて、� �ブロックの先頭ページのOOB領域にバッドブ� �ックであることが記録されているか、記録� �れていない場合、各ブロックの先頭ページ� �最終使用ページのOOB領域にマジックナンバ� �が書かれているかどうかでブロックの有効� �のチェックを行う。

 図8(B)は、4種類のブロック1~4までについ� �の構成例を示す図である。ブロック1~4まで� �は、図8(A)のように、ブロックの2カ所以上に 上述のマジックナンバーを書き込むためのマ ジックナンバー領域を設けている。ここでは 、有効なマジックナンバーを0x1234として説明 する。ブロック1では、マジックナンバー1領� ��71aと、マジックナンバー2領域71bと、に、有 効を示すマジックナンバーが記載されている 。従って、ブロック1は有効ブロックと判断� �ることができる。ブロック2においては、マ� ��ックナンバー1領域71aに有効を示すマジック ナンバーが記載されているが、マジックナン バー2領域71bは0xffffが記載されている。この� �ロックは、ブロックの書き込み中に電源断� �生じたと考えられる。従って、ブロック2は� ��効ブロックと判断することができる。ブロ� ��ク3においては、マジックナンバー1領域71a� �、マジックナンバー2領域71bとの両方に、0xff ffが記載されており、フリーブロックである� ��判断することができる。ブロック4において は、マジックナンバー2領域71bに有効を示す� �ジックナンバーが記載されているが、マジ� �クナンバー1領域71aは0x0000が記載されている� ��このブロックは、ファイルシステムが明示� ��にブロックを無効化したものと考えられる� ��従って、ブロック4は無効ブロックと判断す ることができる。

 尚、先頭ページと最終使用ページとの2箇 所で判断を行うのは、ブロックへの書き込み はページ単位で行われるため、一箇所のマジ ックナンバーを確認するだけでは、ブロック 書き込み中の電源断を検出できないからであ る。データがブロックの先頭ページにだけし か書き込まれていないブロックに関しては、 先頭ページと最終使用ページとが等しくなる ので、先頭ページ以外のページにもマジック ナンバーを書き込むようにして、それを、最 終使用ページのマジックナンバーの代わりに 用いて判断する。

 また、このように、2つのページのマジッ クナンバーを判断することにより、少なくと も、先頭ページのデータは正しいデータであ ることが保証される。その理由は、ブロック 内に複数のページを連続して書き込む場合に 、先頭ページから順番に書き込んで行き、ペ ージを書き込むたびに書き込んだデータが正 しいかベリファイを行っていれば、先頭ペー ジが正しく書き込めない限り、以降のページ に書き込みに行くことはないからである。す なわち、データ2、またはデータ3の書き込み� ��に電源断が生じたとしても、マジックナン� ��ー領域71aとマジックナンバー領域71bが有効� ��あることが判定できれば、マジックナンバ� ��領域71aの前にあるデータ1は有効であること が保証される。データ1の領域に重要な情報� �記憶させておけば、少なくともこの情報は� �常なデータとして利用することができる。� �お、ページのベリファイはページベリファ� �手段により行われる。ページベリファイ手� �は、ページへのデータの書き込み時に、書� �込んだデータが正しく書き込めているかの� �リファイを行う手段であり、一般的にはプ� �グラムにより制御装置が行うことになるが� �専用のハードウエアによってベリファイす� �ようにしてもよい。

 マウントの第二段階では、チェックブロ� ��クリスト内の妥当ブロックを解析し、妥当� ��ァイル候補、もしくは、不完全ファイルを� ��構成する。基本的に妥当ブロックは、妥当� ��ァイル候補か不完全ファイルかどちらかの� ��成要素となるはずである。

 具体的にファイルを再構成するには、各ブ� ��ックの先頭ページに、以下の表2に示すよう なブロック情報を付加してデータを書き込ん でおく。上述したように、妥当ブロックの先 頭ページはデータが正しいことが保証されて いるので、ブロック情報が正しいかどうかの チェックは省いてもよい。

 尚、ファイル名とファイルサイズに関し� ��は、ブロック情報において必須ではなく含� ��なくてもよい。その場合は、データの先頭� ��これらを付加しておけばよい(図3のブロッ� �情報のバリエーションを参照)。

 より具体的なファイル構成情報の生成例� ��ついて図面を参照しながら説明を行う。図4 は、本実施の形態によるファイルシステムに おけるブロックの一構成例を示す図である。 図4に示すように、ブロックYは、太線で囲ま� ��たブロック情報領域と、それ以外のデータ� ��域53とを含んでいる。ブロック情報41は、フ ァイル名43とファイルサイズ45とファイルシ� �テムが付与する一意のファイルID47とファイ� ��におけるブロックのつながりの順番を示す� ��ロック番号51とを含んでいる。尚、このう� �、ブロック情報41の必須項目41aは、ファイル IDとブロック番号とであり、これにより、ブ� ��ックがどこに属するかについての構成を知� ��ことができる。

 図5は、例として示したブロック1から6ま� ��に関するブロック構成例を示す図である。� ��ロック1は、ファイルID47が“456”であり、� �ロック番号51が2/2である。2/2は、2つあるブ� �ックのうちの2番目であることを示す。ブロ� ��ク2は、ファイルID47が“123”であり、ブロ� �ク番号51が1/3である。ブロック3は、ファイ� �ID47が“789”であり、ブロック番号51が2/4で� �る。ブロック4は、ファイルID47が“123”であ り、ブロック番号51が3/3である。ブロック5は 、ファイルID47が“123”であり、ブロック番� �51が2/3である。ブロック6は、ファイルID47が� ��456”であり、ブロック番号51が1/2である。

 図6は、ファイル構成情報の構成例と、フ ァイル構成情報から再生成できるファイルの 構成例を示す図である。図6(A)に示すように� �ファイル構成情報61は、ファイルID45と、ブ� �ックリスト57とを有している。図6(B)に示す� �うに、ファイルID=123のファイル1のブロック� ��ストは、矢印AR1、2、3の順番で繋がれてい� �ブロック2、ブロック5、ブロック4により構� �されていることがわかる。一方、ファイルID =456のファイル2は、矢印AR11、12の順番で繋が� ��ているブロック6、ブロック1により構成さ� �ていることがわかる。

 次に、ファイル構成情報再構築の処理の� ��れを図7(A)、(B)を参照しながら説明する。ス テップS1においてファイル再構成を開始する� ��ステップS2において、ブロックを取り出し� �ステップS3において、取り出したブロックが 有効なブロックであるか否かを、ブロックチ ェック手段を用いて判定する。有効なブロッ クでない場合には(N)、ステップS8に進む。有� ��のブロックである場合には(Y)ステップS4に� �み、ブロック情報を読み込む。ステップS5に おいて読み込んだブロック情報に記載されて いるファイルIDが新規なファイルIDであるか� �かを判定する。新規ファイルIDである場合に は(Y)、ステップS6においてファイルIDを登録� �、ステップS7に進む。新規ファイルIDでない� ��合にも(N)ステップS7に進み、該当ファイルID にこのブロックを追加する。次いで、ステッ プS8において全ブロックの処理が完了したか� ��かを判定する。全ブロックの処理が完了し� ��いない場合には(N)ステップS2に戻る。全ブ� �ックの処理が完了した場合には(Y)、ファイ� �の構成情報の生成処理を終了する。これら� �情報は、RAMのファイル構成情報格納領域に� �録する。この時点で登録されるファイルは� �不完全ファイル、もしくは、妥当ファイル� �補となっている。

 次いで、ファイルの構成情報に基づいて� ��れらのファイルから妥当ファイル候補を抽� ��する処理について説明する。ステップS9に� �いて、RAMのファイル構成情報格納領域に登� �されている情報を読み出してファイルIDを取 り出し、このファイルIDを持つファイルにお� ��て全ブロックが存在するか否かを判定する( ステップS10)。全ブロックが存在する場合に� �(Y)ステップS11に進み、該当するファイルIDの ファイル構成情報を有効にし、全ブロックが 存在するのではない場合(N)とともに、ステッ プS12に進み、全ファイルIDについて処理が完� ��しているか否かを判断し、NOの場合にはス� �ップS9に戻って同様の処理を繰り返す。全フ ァイルIDについて処理が完了して場合(Y)には� ��ステップS13においてファイルの再構成を完� ��する。尚、ステップS1からステップS8までの 処理と、ステップS9からステップS13までの処� ��は、並行処理としても良い。以上のように� ��ることで、ファイル構成情報の作成と再構� ��とを簡単に行うことができる。ファイル構� ��情報をフラッシュメモリに記憶するのでは� ��いため、ブロック情報のみに基づいて、フ� ��イルを再構成する際に、同じ領域における� ��き込み、読み出しを避けることができる。

 尚、妥当ファイル候補でないものは不完� ��ファイルとなる。マウントの第三段階では� ��再構成された妥当ファイル候補から有効フ� ��イルを選び出す。有効ファイルは、妥当フ� ��イルとなる妥当ファイル候補であり、妥当� ��ァイル中に同名のファイルがなければその� ��ァイルとし、同名のファイルがあれば、最� ��に書き込まれたファイルとする。また、有� ��ファイルは、「消去を示すファイル」では� ��いことも条件となる。なお、同名のファイ� ��が存在すること、同名の最後に書き込まれ� ��ファイルを判断すること、および、「消去� ��示すファイル」に関しては後述する。

 ブロックへの書き込みでベリファイが必� ��な場合、ベリファイ中に電源断があるとそ� ��ブロックが本当に正しく書き込めたかどう� ��がわからないという問題がある。ファイル� ��複数のブロックから構成されている場合に� ��最終ブロックで電源断が発生すると、最終� ��ロックの書き込み正当性が判断できず、フ� ��イル内容が異常になる可能性がある。そこ� ��、本実施の形態によるファイルシステムに� ��いては、ファイルの書き込みはファイル内� ��いずれかのブロックに書き込み完了フラグ� ��書くことで完了とすることを特徴とする。� ��ァイル内のどこかのブロックに、ファイル� ��体の書き込み完了を意味するフラグを書き� ��む領域を設けておけば、そのフラグをチェ� ��クするだけでファイルの書き込みが正常に� ��われたかどうかを簡単に判断できる。従っ� ��、ファイル書き込みの際の電源断による不� ��全ファイルの検出を容易にすることができ� ��。図9(A)は、このようなブロック構成例を示 す図である。図示するように、ブロックYは� �データ領域81と、書き込み完了フラグ領域83� ��を有している。図9(B)は、ブロックAからブ� �ックFまでの6つのブロックの構成例を示す図 である。ブロックA~Cは、ファイル1に含まれ� �ブロックであり、ブロックD~Fは、ファイル2� ��含まれるブロックである。ここで、各ファ� ��ル1、2の先頭ブロックの最終ページには、� �き込み完了を示す書き込み完了フラグを記� �するための書き込み完了フラグ領域83aが設� �られている。書き込み完了フラグ領域はど� �に設けてもよいが、先頭ブロックにあるの� �好ましい。図10(A)に示すように、ブロックA� �B、Cからなるファイル1は、最終ブロックで� �るブロックCまで正常に書き込まれており、� ��ロックAの最終ページに書き込み完了フラグ 領域83aに有りと記載されているため、ファイ ルの書き込みが正常に行われたことがわかる 。一方、図10(B)に示すように、ファイル2は、 ブロックD、E、Fからなるが、ブロックDの最� �ページに設けられた書き込み完了フラグ領� �83bにはフラグが記載されておらず、これを� �ってファイルの書き込みが未完であると判� �することができる。すなわち、妥当ファイ� �候補が妥当ファイルであるか否かを判断す� �ために、ファイルを構成するブロックのう� �ファイルの先頭ブロックに関しては、その� �ァイル全体のブロックの書き込みが完了し� �ことを示すデータ(書き込み完了フラグ)を書 き込む領域83を別途設けておくことが特徴と� ��る。

 実装の一例としては、先頭ブロックの最� ��ページはファイルのデータを書き込むため� ��は使用せずに、この書き込み完了フラグを� ��き込むために使用する。このようにするこ� ��で、あるファイルの先頭のブロックに書き� ��み完了フラグが書かれているかどうかを調� ��ることにより、そのブロックを先頭ブロッ� ��とするファイルの全てのブロックが正常に� ��き込まれているか否かを判断することがで� ��る。この書き込み完了フラグが書き込まれ� ��いる妥当候補ファイルを妥当ファイルとす� ��。なお、書き込み完了フラグは、完了フラ� ��書き込み手段により、ファイルの書き込み� ��了後に、書き込まれる。また、マウント時� ��は、完了フラグ読み込み手段により読み込� ��れ、ファイルの書き込みが完了したかどう� ��を判断するために用いられる。これら、書� ��込みと読み込み、および、判断は、一般的� ��はプログラムにより制御装置が行うことに� ��るが、専用のハードウエアによってこれら� ��行うようにしてもよい。

 有効ファイルを構成するブロックはチェ� ��クブロックリストから外す。有効ファイル� ��構成するブロックとならなかったブロック� ��、チェックブロックリストから外されイレ� ��スブロックリストにつながれる。すなわち� ��無効ファイルと不完全ファイルを構成する� ��ロックである。これらのブロックは再利用� ��れることになる。なお、イレースブロック� ��ストにつなぐ際には、そのブロックへの書� ��込みが古く行われたものから順につなぐよ� ��にする。

 上記、一連の処理によって、マウント終� ��後には、フリーブロックはフリーブロック� ��ストに、消去が必要な、もしくは、消去が� ��能なブロックはイレースブロックリストに� ��ながれていることになる。

 次に、ファイルの書き込み処理について� ��24を参照しながら説明する。まず、ステッ� �S101において、書き込み処理を開始する。次� ��で、ステップS102において、ファイルID付与� ��段を用いて、ファイルIDを取得する。ステ� �プS103において、フリーブロックリストが空� ��否かを判定する。フリーブロックリストが� ��であれば(YES)、ステップS104に進み、フリー� ��ロックリストではなくイレースブロックリ� ��トからブロックを取り出し、ステップS106に おいてブロックを消去し、ステップS107にお� �てブロック情報を生成する。ステップS103でN Oの場合にはステップS105に進み、フリーブロ� ��クリストからブロックを取り出し、ステッ� ��S107に進みブロック情報を生成する。

 次いで、ステップS108においてブロック情 報とデータをブロックへ書き込み、ステップ S109において、書き込みデータが残っている� �否かを判定する。次いで、ステップS110にお� ��て、完了フラグ書き込み手段を用いて、書� ��込み完了フラグを先頭ブロックに書き込み� ��ステップS111においてファイルIDを更新(ファ イルIDを消費したことを、ファイルID付与手� �に示す)し、ステップS112において、ファイル 構成情報に新ファイルを追加する。ステップ S113において、旧ファイルが存在するか否か� �判定し、存在すれば(YES)ステップS114に進み� �ファイル構成ブロックをイレースブロック� �ストに追加し、ステップS115においてファイ� ��構成情報から旧ファイルを削除し、書き込� ��を終了する(ステップS116)。旧ファイルが存� ��しない場合には、そのまま処理を終了する( ステップS116)。ここで、ステップS110からステ ップS115は、後述するファイル更新手段の手� �を示している。すなわち、書き込みが完了� �たファイルと同名の旧ファイルがある場合� �は、そのファイルを無効とするとともに、� �たなファイルを有効とする処理である。旧� �ァイルがない場合には、新たなファイルが� �効になるだけである。ステップS110からステ� ��プS115の処理は、一般的には、プログラムに より制御装置が行うことになるが、専用のハ ードウエアによってこれらを行うようにして もよい。

 以上に説明したように、ファイルの書き� ��みに使用するブロックは、フリーブロック� ��ストから取り出す。フリーブロックリスト� ��ブロックがない場合は、イレースブロック� ��ストからブロックを取り出し、消去を行い� ��フリーブロックリストに入れた後、フリー� ��ロックリストから取り出す。このような手� ��にしておけば、フリーブロックリストのブ� ��ックが尽きてからイレースブロックリスト� ��ブロックを再利用するようになるため、全� ��域が初期化された状態から、全領域のブロ� ��クに書き込みを行うまでの間では、ブロッ� ��が再利用されることはない。また、イレー� ��ブロックリストにつながれているブロック� ��、書き込まれた順番でつながれており、つ� ��ぐときも書き込まれた順番でつなぐ。した� ��って、イレースブロックリスト内の特定の� ��ロックが何度も再利用されるというような� ��とはおこらない。

 上記ステップS110において、書き込み完了 フラグをファイルの先頭ブロックに書き込ん だ時点で、ファイルの書き込みが正常に行わ れたものとなる。すなわち、ステップS110以� �に電源断が発生した場合、書き込んだブロ� �クは不完全ファイルを構成するものとなる� �、もしくは、無効ブロックとなるかのどち� �かであり、次回のマウント処理において、� �れらは、イレースブロックリストにつなが� �ることになる。このとき、不完全ファイル� �おいても、ファイルIDは付与されているため 、このファイルはイレースブロックリストの 最後尾につながれる。無効ブロックに関して はイレースブロックリストの先頭につながれ る。この場合、書き込みが行われなかったこ とに等しい。

 ステップS110以降に電源断が行われた場合 、ステップ114およびステップ115の処理は必要 があれば次回のマウント処理で必ず行われる ため、特に考慮する必要はない。

 次に、ファイルの更新処理について説明� ��る。

 一般的なファイルシステムでは、ファイ� ��を更新する場合には、そのファイルが記録� ��れている部分を直接書き換えるか、別名で� ��ァイルを作成した後にファイル名を変更す� ��か、といった方法が取られる。しかしなが� ��、これらの方法では、書き換え中に電源断� ��発生した場合や、ファイル名を変更中に電� ��断が発生した場合には、データの不整合や� ��ァイルの消失といった危険性が伴う。一方� ��フラッシュメモリは書き換えを行うために� ��ブロック全体の消去を行う必要があり、一� ��分だけの書き換えは無駄が多く、また、書� ��換えの回数にも制限があることから、上述� ��ような方法は向いていない。

 そこで、本実施の形態によるファイルシ� ��テムにおいては、ファイルシステム内に同� ��のファイルが存在することを許し、有効な� ��ァイルは最後に書き込まれたファイルであ� ��とし、また、新しいファイルの書き込み完� ��を待ってから古いファイルを無効化するこ� ��を特徴とする。これにより、ファイル更新� ��際の電源断に起因する上記のような危険性� ��排除することができる。これらの処理はフ� ��イル更新手段により行われる。

 次に、図面を参照しながら、より詳細に� ��明を行う。図11は、ファイル書き込み前の� �ァイル構成情報の例を示す図である。図11に 示すように、ファイル1におけるファイル書� �込み前の構成情報は、ファイル名が‘AA’で あり、このファイル名AAのファイル1は、AR1の 矢印とそれに続くAR2の矢印で示すようにブロ ックAとブロックBとから構成されている。図1 2に示すファイル書き込み中の構成情報(1)は� �図示するように、このファイル1を更新する� ��めにファイル書き込む場合に、ファイル1の 他にファイル1と同名のファイル2を作成する� ��このファイル2に含まれるブロックCは、フ� �イル書き込みがまだ完了していないため、� �ラグ領域83bにはフラグが立っていない(無し) 。図13に示すファイル書き込み中の構成情報( 2)は、図示するように、ファイル2に関して、 ブロックCとブロックDとをつなげる。この状� ��では、ファイル書き込みがまだ完了してい� ��いため、フラグ領域83bにはフラグが立って� ��ない。

 図14は、ファイル書き込み完了直後の構� �情報例を示す図である。図14に示すように、 ファイル2において、ブロックDをつなげた後� ��、矢印AR31で示すように、フラグ書き込み領 域83aにフラグを立てる(有りとする)。これ以� ��であれば、フラグ有りになっているため、� ��源断が生じた場合でもファイル2が存在する 。従って、ファイル構成情報更新例に示すよ うに、ファイル1を無効化処理したとしても� �ファイル2を引き続き利用することで、ファ� ��ル1からファイル2への更新を行うことがで� �る。この状態でRAMへのファイル構成情報の� �き込みを行う。

 このように、同名ファイルの存在を許容� ��同名ファイルで更新することにより、途中� ��電源断が生じても、更新前のファイルと更� ��後のファイルの両方のファイルを消失する� ��険性がなく、安全にファイルの更新を行う� ��とができる。

 次に、ファイルの消去処理について説明� ��る。本実施の形態によるファイルシステム� ��おいては、ファイルの消去は“ファイルを� ��去したことを示すファイル”を書き込むこ� ��で行うことを特徴とする。ファイルを消去� ��るには、ファイル構成情報からそのファイ� ��の構成情報を取り除けばよいが、ファイル� ��成情報はRAM上に存在するため、その状態で� ��源断が起こった場合、次回のマウント処理� ��消去されたはずファイルが復活してしまう� ��したがって、ファイル構成情報を消去する� ��けでなく、そのファイルを構成するブロッ� ��を消去する必要がある。しかしながら、複� ��のブロックからなるファイルを消去する場� ��や、消去に時間がかかるデバイスにとって� ��、このような処理では時間がかかってしま� ��。そこで、ファイルを構成するブロックを� ��去する代わりに、ファイルを消去したこと� ��示すファイルを書き込むことにし、そのフ� ��イル、および、そのファイルにより消去さ� ��たファイルは利用者に見せないようにする� ��このようにしておけば、電源断が起こった� ��合でも、次回のマウント処理で消去された� ��ァイルが復活することはない。ここで、例� ��ば、ファイルを消去したことを示すファイ� ��として、同名のサイズが0のファイルを書き 込むようにすれば、たかだか1ブロック分の� �き込みだけですむため、消去を高速に行う� �とが可能となる。

 図16(A)は、消去を示すファイル書き込み� �の構成情報の例を示す図である(“ファイル� ��去のファイル”書き込み前の構成情報)。図 16(A)に示すように、消去を示すファイル書き� ��み前においては、ファイル名‘AA’45を有す るファイル1は、矢印AR1、AR2、AR3でそれぞれ� �番に繋がれているブロックA、B、Cから構成� �れていることがわかる。ここで、図16(B)に示 すように、複数のブロックからなるファイル 1を消去する場合に、ブロックDのみを含むフ� ��イル2を生成する。このファイル2は、ファ� �ル消去のファイルであり、サイズが0のファ� ��ルである(“ファイル消去のファイル”書き 込み完直後の構成情報)。ファイル2のフラグ� ��き込み領域83aには、書き込み完了を示すフ� ��グが付される。そして、サイズ0のファイル 2でファイル1を上書きすることにより、利用� ��には見えない形でファイル1が消去できるこ とになる。この場合に、同じ名前‘AA’のフ� ��イルがあった場合に、最後に書き込まれた� ��ァイル2が有効となる。すなわち、図16(C)に� ��すように、ファイル1とファイル2とを無効� �することにより実質的にファイル1を消去す� ��ことが簡単に行うことが可能となる。すな� ��ち、ファイル消去の高速化が可能となる。

 このように、ファイルの消去は、「消去� ��示すファイル」を書き込むことで実現する� ��とができる。たとえば、上記では、同名の� ��ァイルサイズが0のファイルにその役割をま かせているが、特に限定はしない。但し、「 消去を示すファイル」は利用者には見せない ほうが好ましい。書き込み手順は、通常のフ ァイルの書き込みとほぼ同じであるが、ファ イルの書き込み後に、「消去を示すファイル 」を構成するブロックをイレースブロックリ ストにつなげるという処理が加わる。

 図25に、処理のフローチャート図を示す� �まず、ステップS121において、消去処理を開� ��する。次いで、ステップS122においてファイ ルIDを取得する。ステップS123において、フリ ーブロックリストが空か否かを判定する。フ リーブロックリストが空であれば(YES)、ステ� ��プS124に進み、フリーブロックリストではな くイレースブロックリストからブロックを取 り出し、ステップS126においてブロックを消� �し、ステップS127においてブロック情報を生� ��する。この時、ファイルサイズは0とする。 ステップS123でNOの場合にはステップS125に進� �、フリーブロックリストからブロックを取� �出し、ステップS127に進みブロック情報を生� ��する。この時、ファイルサイズは0とする。 次いで、ステップS128においてブロック情報� �データをブロックへ書き込み、ステップS129� ��おいて、書き込みデータが残っているか否� ��を判定する。次いで、ステップS130において 、書き込み完了フラグを先頭ブロックに書き 込み、ステップS131においてファイルIDを更新 し、ステップS132において、ファイル構成ブ� �ックをイレースブロックリストに追加し、� �テップS133において、旧ファイル構成ブロッ� ��をイレースブロックリストに追加し、ステ� ��プS134においてファイル構成情報から旧ファ イルを削除し、書き込みを終了する(ステッ� �S135)。

 尚、上記ステップS130において、書き込み 完了フラグをファイルの先頭ブロックに書き 込んだ時点で、ファイルの書き込みが正常に 行われたものとなる。すなわち、ステップS13 0以前に電源断が発生した場合、書き込んだ� �ロックは不完全ファイルを構成するものと� �るか、もしくは、無効ブロックとなるかの� �ちらかであり、次回のマウント処理におい� �、それらは、イレースブロックリストにつ� �がれることになる。このとき、不完全ファ� �ルにおいても、ファイルIDは付与されている ため、このファイルはイレースブロックリス トの最後尾につながれる。無効ブロックに関 してはイレースブロックリストの先頭につな がれる。この場合、消去は行われなかったこ とに等しい。

 ステップS130以降に電源断が行われた場合 でも、有効なファイルは最後に書き込まれた ファイルと決めておく限り、ステップ132から ステップ134の処理は必要があれば次回のマウ ント処理で必ず行われるため、特に考慮する 必要はない。

 次に、ファイルIDの付与方法、ならびに� �ブロックの再利用方法について説明する。

 マウント時に、ブロックに付与されたフ� ��イルIDに基づいて、ファイルを再構成し、� �効なファイルを抽出する方法はすでに述べ� �。また、同名のファイルがある場合、最後� �書き込まれたファイルが有効なファイルで� �るとしておくことで、ファイルの書き込み� �や消去時に電源断があっても不具合が発生� �ない方法を述べた。さらに、有効でないフ� �イルを構成するブロックに関しては、その� �ァイルが書き込まれた順番で再利用する方� �を述べた。

 これらの方法はそれぞれ独立しているが� ��ユニークなファイルIDに基づいて、ファイ� �の書き込み順が判断できるようにしておけ� �、一度に全てを満たすことができる。特に� �ファイルIDは再利用することなく、ファイル の書き込みが行われるごとに新たなものを割 り当て、さらに、ファイルIDは、単調増加、� ��たは、単調減少するものが好ましい。

 そこで、本実施の形態によるファイルシ� ��テムにおいては、ファイルID付与手段が付� �するファイルIDは、過去に割り当てた最大フ ァイルID+1とし、ファイルIDの大きさに基づい て、ファイルの書き込まれた順番を判断する ファイル書き込み順判定手段を設けることを 特徴とする。

 ファイル書き込み中の電源断で生成され� ��、あるいは、ファイルの更新や削除により� ��要がなくなった、無効なファイルを構成す� ��ブロックは、そのまま放置しておき、新た� ��書き込みでブロックが必要となったときに� ��そのようなブロックを再利用するという方� ��では、特定のブロックが何度も再利用され� ��ことがないようにするのが望ましい。ファ� ��ル(ブロック)にファイルIDを割り当てておく と、不要な古いブロックから再利用させるこ とが可能となる。マウント時もそれにならう ようにする。これにより、ブロック再利用時 に、適切なブロック割り当てが可能となると いう利点がある。すなわち、ウエアレベリン グが可能となる。

 図17は、本実施の形態によるファイルシ� �テムにおける、ウエアレベリング対応のフ� �イル書き込み時のブロック接続例を示す図� �ある(ファイル書き込み前の構成情報)。図17( A)は、ファイル書き込み前の構成情報の例を� ��す図である。図17(A)に示すように、イレー� �ブロックリストは、ブロックA(AR1)、ブロッ� �B(AR2)、ブロックC(AR3)、ブロックD(AR4)、ブロ� �クG(AR4)と繋がれているリストとなっている� �一方、ファイル1は、ファイル名‘BB’のフ� �イルであって、ブロックE(AR5)、ブロックF(AR6 )とつながれて構成されている。ここで、ブ� �ックAからブロックGへとファイルIDが大きく� ��っている。

 図17(B)は、ファイル書き込み完了直後の� �ァイル構成情報の例を示す図である(ファイ� ��書き込み完直後の構成情報)。ブロックは、 図17(A)のイレースブロックリストにつながれ� ��いるブロックのうちのファイルIDが小さい� �ロック(ブロックAからGに向けてファイルIDが 大きい)から再利用を行うようにする。ファ� �ル1は図17(A)の構成と同じであり、ファイル2� ��、ファイル1と同名‘BB’であり、ブロック� ��号の小さな順番にイレースブロックリスト� ��らブロックAとブロックBとを利用する。

 次いで、図17(C)に示すように、ファイル� �成情報を更新する。すなわち、ファイル1は� ��ァイル情報を消去(無効化)し、それまで含� �れていたブロックをイレースブロックリス� �に挿入する(ファイル構成情報更新)。イレー スブロックのリストには、ブロックEとブロ� �クFとは、ファイル書き込み順判定手段によ� ��判定されたファイルIDの大きさの順番に基� �いてブロックDとブロックGとの間に挿入され る。そして、ファイル2は、ブロックAとブロ� ��クBとから構成される。

 尚、ファイル2をさらに更新すると、ブロ ックAとブロックBとは、ファイルIDがブロッ� �Gよりも大きくなるため、イレースブロック� ��ストにおいてはブロックGの後につながれる ことになる。

 書き込み処理について、再び図24を参照� �ながら説明する。まず、ステップS101におい� ��、書き込み処理を開始する。次いで、ステ� ��プS102においてユニークなファイルIDを取得� ��る。ここで、新たに取得するファイルIDは� �ファイルシステムが過去に割り当てた最大� �ァイルID+1とする。ステップS103において、フ リーブロックリストが空か否かを判定する。 フリーブロックリストが空であれば(YES)、ス� ��ップS104に進み、フリーブロックリストでは なくイレースブロックリストからブロックを 取り出し、ステップS106においてブロックを� �去し、ステップS107においてブロック情報を� ��成する。ステップS103でNOの場合にはステッ� ��S105に進み、フリーブロックリストからブロ ックを取り出し、ステップS107に進みブロッ� �情報を生成する。

 次いで、ステップS108においてブロック情 報とデータをブロックへ書き込み、ステップ S109において、書き込みデータが残っている� �否かを判定する。次いで、ステップS110にお� ��て、書き込み完了フラグを先頭ブロックに� ��き込み、ステップS111においてファイルIDを� ��新し、ファイルシステムにファイルIDを消� �したことを伝える。ステップS112において、� ��ァイル構成情報に新ファイルを追加する。� ��テップS113において、旧ファイルが存在する か否かを判定し、存在すれば(YES)ステップS114 に進み旧ファイル構成ブロックをイレースブ ロックリストに追加し、ステップS115におい� �ファイル構成情報から旧ファイルを削除し� �書き込みを終了する(ステップS116)。旧ファ� �ルが存在しない場合には、そのまま処理を� �了する(ステップS116)。上記ファイルの書き� �み処理で説明したように、ファイルを書き� �むために使用するブロックは、フリーブロ� �クリストから取得している。フリーブロッ� �リストにブロックがない場合は、イレース� �ロックリストからブロックを取り出し、ブ� �ックを消去した後、フリーブロックリスト� �つなげ、フリーブロックリストから取得し� �いる。

 これが意味するところは、NAND型フラッシ ュメモリの領域全体を初期化した状態では、 全てのブロックがフリーブロックリストにつ ながれており、それらを使い切った後、初め て、イレースブロックリストにあるブロック が再利用されるということである。また、イ レースブロックリストにあるブロックは、フ ァイルIDの順番でつながれている。ファイルI Dが同じブロックに関しては、その中でもブ� �ック番号の順番につながれている。すなわ� �、再利用されるブロックというのは、消去� �能なブロックのうち、最も以前に書き込み� �行われたブロックということになる。

 次いで、マウント処理の流れについて図1 8を参照しながら説明を行う。ステップS61に� �いて、ファイルの再構成処理を開始する。� �いで、ステップS62においてブロックを取り� �し、ステップS63において、取り出したブロ� �クが有効なブロックであるか否かを判定す� �。有効でない場合には(NO)ステップS69に進む� ��有効な場合には(YES)、ステップS64において� �ロック情報を読み込み、ステップS65におい� �新規ファイルIDであるか否かを判定する。新 規ファイルIDでない場合には(NO)、ステップS68 に進む。新規ファイルIDであれば(YES)、ステ� �プS66においてファイルIDを登録し、ステップ S67においてファイルIDを更新し、ステップS68� ��進む。ステップS68においては、該当ファイ� ��IDに取り出したブロックを追加する。

 ステップS69においては、全ブロックの処� ��が完了したかどうかを判定し、NOの場合に� �ステップS62に戻る。YESの場合には、ステッ� �S70に進み、登録されたファイルIDを大きな順 に取り出す。すなわち、ステップS70では、フ ァイル書き込み順判定手段を用いて、最後に 書き込まれたファイルから順に抽出し、以降 の処理を続けることになる。ステップS71にお いて、全ブロックが存在するか否かを判定し 、YESであればステップS72に進み同名ファイル が存在するか否かを判定する。次いで、ステ ップS73において該当ファイルIDのファイル構� ��情報を有効にし、ステップS75に進む。NOで� �れば、ステップS74に進み、本ファイル構成� �ロックをファイルIDの順番にイレースブロッ クリストに挿入し、ステップS75に進む。ステ ップS75においては、全ファイルIDの処理が完� ��したか否かを判定し、NOであればステップS7 0に戻り、YESであればステップS76において再� �成を終了する。

 以上のようにすれば、ファイルの書き込� ��中に電源断が発生した場合、その書き込み� ��消費されたブロックは次回のマウント処理� ��に、イレースブロックリストの最後につな� ��れることになる。なぜなら、イレースブロ� ��クリストのブロックはファイルIDの順番で� �ながれており、電源断が発生した最後の書� �込みで使用したファイルIDは、その時点で最 大であったからである。これは、それらのブ ロックが再利用されるのは、ファイル書き込 み時点でのイレースブロックリストのブロッ クを使い切ってからということに他ならない 。つまり、特定ブロックだけが何度も再利用 されるということを防ぐことができる。

 ここまで、バッドブロックの扱いに関し� ��、特に言及しなかったので、ここで簡単に� ��明する。

 NAND型フラッシュメモリには、出荷時から 存在する初期バッドブロックと、消去や書き 込みを繰り返しているうちに磨耗がおきて発 生する後天的なバッドブロックがある。これ らは、データを正しく読み出すことができな い可能性のあるブロックであり、使用を控え る必要がある。このようなブロックにはOOB領 域に自身がバッドブロックであることが記録 されている。このようなバッドブロックはマ ウント処理時に検出できるので、これらはバ ッドブロックリストに入れて、以後は使用し ないようにすればよい。

 初期バッドブロックは出荷時にバッドブ� ��ックであることが記録されているが、後天� ��なバッドブロックは書き込み時に検出し、� ��録しなければならない。すなわち、ブロッ� ��にデータを書き込んだ後、もう一度同じブ� ��ックを読み込み、ベリファイを行えばよい� ��このとき、書き込みと読み込みは正常に行� ��れたにもかかわらず、ベリファイにおいて� ��ラーが出たものが、後天的なバッドブロッ� ��となる。このようなブロックは、先頭ペー� ��のOOB領域にバッドブロックであることを記� ��しバッドブロックリストに入れるとともに� ��以後は、使用しないようにすればよい。一� ��、OOB領域にバッドブロックであることが記� ��されると、電源断後のマウント処理におい� ��も、そのブロックはバッドブロックである� ��とが検出できるので、使用されることはな� ��。

 以上に説明したように、本実施の形態に� ��るファイルシステムにおいては、高速なフ� ��イル処理を行うことができる。また、ウエ� ��レベリングが可能になる。さらに、ファイ� ��書き込み中に電源断が発生してもファイル� ��報を再構成可能でありファイルの損失や破� ��も生じないという利点がある。

 次に、本発明の第2の実施の形態によるフ ァイルシステムについて説明する。第1の実� �の形態では、ファイルの消去に関しては、� �消去を示すファイル」を書き込むことで実� �しているが、セキュリティの面から、実際� �、物理的にデータを消去したいという要求� �あることが考えられる。

 この場合に、ファイルの消去時には、「� ��去を示すファイル」を書き込む代わりに、� ��際にそのファイルが使用しているブロック� ��消去するという方法もある。しかしながら� ��ブロックを消去した後に電源断が発生する� ��、これらのブロックは次回電源投入の際の� ��ァイルシステムのマウント処理時にフリー� ��ロックとみなされるため、それらのブロッ� ��がすぐに再利用されてしまう。さらに、再� ��用されたこれらのブロックが構成するファ� ��ルが消去された後に電源断が発生すると、� ��び、これらのブロックがすぐに再利用され� ��ことになる。

 すなわち、ファイルの書き込み、そのフ� ��イルの消去、電源断、電源投入、というサ� ��クルを繰り返すと、特定のブロックが何度� ��繰り返し利用されることになり、書き込み� ��数に制限があるフラッシュメモリにとって� ��都合が悪い。

 そこで、本発明の第2の実施の形態による ファイルシステムにおいては、ファイルの消 去は「ファイルを消去したことを示すファイ ル」を書き込むことで行うとともに、過去の ファイルに関してはブロックの消去も行う。 このとき、消去されるブロックのブロックID� ��前記ファイルにも付加することを特徴とす� ��。すなわち、ファイルの消去は、「消去を� ��すファイル」を書き込むことと、消去した� ��ファイルが利用しているブロックを実際に� ��去することと、「消去を示すファイル」の� ��に、実際に消去されるブロックのブロックI Dを付加しておくことで実現する。さらには� �消去したブロックと、「消去を示すファイ� �」を構成するブロックは、イレースブロッ� �リストに順につなぐ。このようにしておけ� �、消去されたブロックが再利用される前に� �源断があった場合でも、次回のマウント処� �時には、消去されたブロックをフリーブロ� �クリストではなく、イレースブロックリス� �の適切な位置につなぐことができる。なぜ� �ら、「消去を示すファイル」を構成するブ� �ックは、マウント処理時にイレースブロッ� �リストにつながれるので、そのようなブロ� �クがあれば、そのファイルに付加されてい� �消去したブロックの情報を取り出し、その� �前に挿入することで、電源断時のイレース� �ロックリストを再構成できるからである。� �体的には、図19(A)に示すように、ファイル消 去前の構成情報として、イレースブロックリ ストにブロックAとブロックBとブロックCとブ ロックDとブロックGとが、AR1~4までのように� �ながっているとする。また、ファイル名45が ‘BB’であるファイル1が、ブロックEとブロ� �クFから構成されているとする。

 ここで、図19(B)に示すように、ファイル� �去中の構成情報として、ファイル1を消去す� ��と、ファイル1を構成していたブロックEと� �ロックFがイレースブロックリストにつなが� ��、ブロックAから構成された、「消去を示す ファイル」であるファイル2が新たに生成さ� �る。このとき、ブロックAはイレースブロッ� ��リストの先頭のブロックが取り出されたも� ��である。さらに、ブロックAには、ブロック EとブロックFを消去したという情報を付加し� ��おく。この後、実際に、ブロックEとブロッ クFを消去する。

 最終的には、図19(C)に示すように、ファ� �ル消去後の構成情報として、イレースブロ� �クリストは図19(B)のものにブロックAが加わ� �た状態になる。

 ブロックAには、ブロックEとブロックFと� ��消去したという情報を格納しておくため、� ��源断が起こった場合でもイレースブロック� ��ストの再構築は可能になる。

 図26を用いて、消去処理のフローを説明� �る。まず、ステップS141において、消去処理� ��開始する。次いで、ステップS142においてフ ァイルIDを取得する。ステップS143において、 フリーブロックリストが空か否かを判定する 。フリーブロックリストが空であれば(YES)、� ��テップS144に進み、フリーブロックリストで はなくイレースブロックリストからブロック を取り出し、ステップS146においてブロック� �消去し、ステップS147においてブロック情報� ��生成する。この時、ファイルサイズは0とす る。ステップS143でNOの場合にはステップS145� �進み、フリーブロックリストからブロック� �取り出し、ステップS147に進みブロック情報� ��生成する。この時、ファイルサイズは0とす る。次いで、ステップS148においてブロック� �報とデータをブロックへ書き込む。このと� �、データとして、実際に消去すべきブロッ� �のブロックIDを付加しておく。次にステップ S149において、書き込みデータが残っている� �否かを判定する。次いで、ステップS150にお� ��て、書き込み完了フラグを先頭ブロックに� ��き込み、ステップS151においてファイルIDを� ��新し、ステップS152において旧ファイル構成 ブロックをイレースブロックリストに追加し 、ステップS153においてイレースブロックリ� �ト内にある同名のファイルを構成するブロ� �クを消去し、ステップS154において消去した� ��ロックをイレースブロックリストの最後に� ��なぎなおし、ステップS155においてファイル 構成ブロックをイレースブロックリストに追 加するとともに、ステップS156においてファ� �ル構成情報から旧ファイルを削除し、書き� �みを終了する(ステップS157)。

 ステップS154において、消去したブロック をイレースブロックリストにつなぎなおす(� �後に追加する)ことで、このまま電源断が発� ��しない限りは、イレースブロックリストに� ��初からあったブロックを使いつくすまで、� ��れらの消去したブロックが使用されること� ��ない。一方、途中で電源断があった場合は� ��マウント処理時、次に説明する手順で、こ� ��らのブロックをフリーブロックリストから� ��レースブロックリストにつなぎなおすこと� ��でき、イレースブロックリストを電源断が� ��生した状態に戻すことができる。これによ� ��、ファイルの消去時にブロックの消去を行� ��た場合でも、同一のブロックだけが何度も� ��利用されることを防ぐことができる。

 次に、マウント処理の流れについて図20� �参照しながら説明を行う。まず、ステップS8 1において再構成を開始し、ステップS82にお� �てブロックを取り出す。ステップS83におい� �フリーブロックであるか否かを判定する。� �リーブロックであれば(YES)、ステップS92に進 み、フリーブロックリストに追加しステップ S90に進む。フリーブロックでなければ(NO)、� �テップS84において、有効なブロックかどう� �を判定する。有効なブロックであれば(YES)ス テップS85に進み、有効なブロックでなければ (NO)ステップS91においてイレースブロックリ� �トに追加し、ステップS90に進む。ステップS8 5においては、ブロック情報を読み込み、ス� �ップS86において、新規ファイルIDであるか否 かを判定する。新規ファイルIDであればステ� ��プS87でファイルIDを登録し、ステップS88で� �当ファイルIDにブロックを追加する。次いで 、ステップS90において、全ブロックの処理が 完了したか否かを判定し、NOであればステッ� ��S82に戻り、YESであれば、図21のステップに� �行する。

 図21は、図20に続く処理の流れを示すフロ ーチャート図である。ステップS90でYESであれ ば、ステップS91に進み、登録されたファイル IDを大きな順(新しく作成された順番)で取り� �す。ステップS92において、全ブロックが存� �するか否かを判定し、NOの場合にはステップ S100に進み、ファイル構成ブロックをイレー� �ブロックリストに追加し、ステップS96に移� �する。ステップS92においてYESの場合には、� �テップS93において同名ファイルが登録済み� �あるか否かを判定し、NOであれば、ステップ S94に進み該当ファイルIDのファイル構成情報� ��有効にし、ステップS95において、消去ファ� ��ルであるか否かを判定し、NOであれば、ス� �ップS96に進む。ステップS93でYESの場合には� �ステップS98に進み、消去ファイルであるか� �かを判定する。NOの場合にはステップS100に� �む。YESの場合には、ステップS99に進み、本� �ァイルで記録されているブロックをフリー� �ロックリストから取り出しイレースブロッ� �リストに追加しステップS100に進む。ステッ� ��S96において全IDの処理が完了したか否かを� �定し、完了していなければ(NO)ステップS91に� ��り、完了していれば(YES)、ステップS97にお� �て再構成処理を終了する。

 なお、ステップS100にて、イレースブロッ クリストに追加されるブロックとは、ステッ プS92から来る、全ブロックが存在しないファ イルを構成するブロック、ステップS98から来 る、妥当なファイルであるが同名の新しいフ ァイルが存在する場合のそのファイルを構成 するブロック、ステップS95から来る、最も新 しい消去ファイルを構成するブロックであり 、すなわち、全ブロックが存在する有効なフ ァイルであり、かつ、消去ファイルでないフ ァイルを構成するブロック以外のブロックが 、イレースブロックリストにつながれること になる。

 上述を基本形とすると、これの発展形と� ��て、上記ステップS148において、「消去を示 すファイル」には消去するブロックのブロッ クIDだけでなく、そのブロックのファイルID� �ブロック番号も付加しておき、また、上記� �テップS152において、イレースブロックにつ� ��げるときは、ファイルIDとブロック番号の� �番でイレースブロックリストにブロックを� �なげ、さらに、上記ステップS154において、� ��ロックを消去した後、つなぎなおすことは� ��ないという方法も考えられる。この場合は� ��電源断発生後のマウント時、消去されたブ� ��ックをフリーブロックリストからイレース� ��ロックリストにつなぎなおす際には、ブロ� ��ク番号と一緒に保存されているファイルID� �ブロック番号を用いてつなぎなおすことで� �やはり、イレースブロックリストを電源断� �あった状態に戻すことができる。この方法� �は、ブロックの再利用の順番が、ファイル� �去時にブロックを消去しない場合と完全に� �じ順番になりわかりやすいというメリット� �ある反面、実装が少し複雑になるというデ� �リットがある。

 基本形でも発展形でも、同一のブロック� ��けが何度も再利用されるということはない� ��で、目的に合うように、どちらの方法を選� ��してもよい。

 以上に説明したように、本実施の形態に� ��るファイルシステムにおいては、高速なフ� ��イル処理を行うことができる。また、ウエ� ��レベリングが可能になる。さらに、ファイ� ��書き込み中に電源断が発生してもファイル� ��報を再構成可能でありファイルの損失や破� ��も生じない。また、ファイルの消去では実� ��にデータを消去するため、セキュリティの� ��でも安心できるという利点がある。