(57)【要約】      （修正有）【課題】フラッシュメモリ用のファイルシステムの無駄なデータ書き換えを減らして、動作速度を向上し、フラッシュメモリの寿命を延ばす。【解決手段】ガーベジコレクションの際に変更不要なノードのうち、フラッシュメモリ先頭にあるガーベジコレクション処理の対象にならない部分を含めないように、headポインタとtailポインタの指すアドレスがフラッシュメモリの末尾に達した場合にフラッシュメモリの先頭アドレスに最も近い変更必要なノードのアドレスへと復帰する。【選択図】図１０
2008191797.tif 000002
【特許請求の範囲】
【請求項１】
一時記憶手段と、
ノードを書き込む前記一時記憶手段上のアドレスを保持する書き込み位置記憶手段と、
ファイルシステムのガベージコレクション処理の開始アドレスを保持するガベージコレクション開始位置記憶手段と、
ファイル変更を要求された場合には、前記ファイルの変更した差分を内容とするノードを生成し、前記書き込み位置記憶手段に記憶されたアドレスに、生成した前記ノードを書き込み、前記書き込み位置記憶手段の内容を、書き込んだ前記ノードの次のアドレスに更新するファイル変更処理を行い、
ファイルの読み出しを要求された場合には、前記一時記憶手段から前記ノードを読み出し、読み出した前記ノードの内容である変更の差分を累積し、前記変更の差分を累積した結果をファイルの内容として返すファイル読み出し処理を行い、
前記書き込み位置記憶手段とガベージコレクション開始位置記憶手段との差が所定の値以下になった場合にはガベージコレクション処理を行なう制御手段とを備え、
前記制御手段は、ガベージコレクションを行う際に、
前記ガベージコレクション開始位置記憶手段の内容が前記一時記憶手段の末尾のアドレスに達した場合の復帰処理として、前記一時記憶手段に前記一時記憶手段の先頭のアドレスを設定して、前記一時記憶手段の内容であるアドレスのノードを確認し、
確認した前記ノードの内容が全て有効である場合には、
前記一時記憶手段の内容を前記ノードの次のアドレスに更新した後に、再度前記ノードを確認することを特徴とするファイルシステム。
【請求項２】
一時記憶手段と、
ノードを書き込む前記一時記憶手段上のアドレスを保持する書き込み位置記憶手段と、
ファイルシステムのガベージコレクション処理の開始アドレスを保持するガベージコレクション開始位置記憶手段と、
ファイル変更を要求された場合には、前記ファイルの変更した差分を内容とするノードを生成し、前記書き込み位置記憶手段に記憶されたアドレスに、生成した前記ノードを書き込み、前記書き込み位置記憶手段の内容を、書き込んだ前記ノードの次のアドレスに更新するファイル変更処理を行い、
ファイルの読み出しを要求された場合には、前記一時記憶手段から前記ノードを読み出し、読み出した前記ノードの内容である変更の差分を累積し、前記変更の差分を累積した結果をファイルの内容として返すファイル読み出し処理を行い、
前記書き込み位置記憶手段とガベージコレクション開始位置記憶手段との差が所定の値以下になった場合にはガベージコレクション処理を行なう制御手段とを備え、
前記制御手段は、ガベージコレクションを行う際に、
前記ガベージコレクション開始位置記憶手段の内容が前記一時記憶手段の末尾のアドレスに達した場合の復帰処理として、前記一時記憶手段に前記一時記憶手段の先頭のアドレスを設定して、前記一時記憶手段の内容であるアドレスのノードを確認し、
確認した前記ノードの内容が無効、又は一部無効である場合には、
前記一時記憶手段の内容を前記ガベージコレクション開始位置記憶手段にコピーすることを特徴とするファイルシステム。
【請求項３】
前記一時記憶手段はフラッシュメモリであることを特徴とする請求項１又は請求項２に記載のファイルシステム
【請求項４】
前記フラッシュメモリは、ウェアレベリングの機能を持つことを特徴とする請求項３に記載のファイルシステム。
【請求項５】
前記フラッシュメモリを読み書きするデバイスドライバとして、ウェアレベリングの機能を持つデバイスドライバ使用することを特徴とする請求項４に記載のファイルシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータやマイクロプロセッサが利用するファイルシステムに関する。
【背景技術】
【０００２】
近年、デジタル家電などの組込機器用のＯＳにおいても、記憶装置を効率よく利用するためにファイルシステムを備える例が増えてきている。組込機器においてはフラッシュメモリを利用した記憶装置が多く用いられるが、フラッシュメモリは消去して再書込みできる回数が有限であるなどの特性を持つため、ファイルシステムにもその特性を考慮することが求められる。
【０００３】
また携帯型機器では電源が不安定でファイルの書込み中に突然の電源断が起きるおそれがあるため、ファイルシステムには、そのような場合でも内容の整合性を回復する能力が求められる。
【０００４】
それらの要求に応えるファイルシステムの例として非特許文献１に見られるjffs2がある。jffs2はこれらの要求に応えるために、ジャーナリングと、ウェアレベリングの２つの機能を持つ。
【０００５】
以下、この２つの機能の動作を説明する。
【０００６】
ジャーナリングとは、ファイルシステムがファイルの変更の履歴を記録する機能であり、突然の電源断があった後でファイルシステムの整合性を回復するために、この履歴を利用する。
【０００７】
jffs2におけるジャーナリングでは、ファイルそのものは記録せず、変更の履歴のみを記録する。履歴にはファイルの変更部分が差分として含まれており、ファイルを読み出す際には、そのファイルに関係した最も古い履歴を元に、それ以後の全ての履歴中の差分を上書きしていき、最終的に最新のファイルの内容を再現する。
【０００８】
なお、jffs2では、管理を容易にするために履歴は数kバイト程度のサイズのノードに記録する。そのため、大きなファイルは、その内容をノードに記録できるサイズに分割し、便宜上、それらのノードの内容を追記していった結果として表現される。また、各ノードには管理情報が付加され、その管理情報にはノードのバージョン番号、ノードの属するファイル、ノードが保持する内容がファイル内で占める占有範囲に関する情報が含まれている。
【０００９】
また、バージョン番号は全てのノードに振られた通し番号であり、各ノードの新旧の順序を判定するのに利用する。また、占有範囲の情報があることにより、ノードが不規則な順に読み出された場合や、ファイルの途中のみを変更した場合にも、正しくファイルの内容を再現できる。
【００１０】
また、複数のノードの間で占有範囲が重複し、より新しいノードで上書きされるために最終的なファイルに内容が全く反映されないノードは無効なノードと呼ぶ。反対に、一部のみでも最終的なファイルに内容が反映されるノードは有効なノードと呼ぶ。有効なノードであっても、その占有範囲の全てが最終的なファイルの内容に反映される場合と、占有範囲の一部のみが最終的なファイルの内容に反映され、それ以外の部分が無効となっている場合がある。
【００１１】
jffs2はノードの管理情報を読み出すために、毎回フラッシュメモリにアクセスする代わりにノードデータベースを使用する。jffs2は、ファイルシステムをマウントする際にフラッシュメモリ内を走査し、全てのノードの管理情報と、ノードのフラッシュメモリ上でのアドレスをノードデータベースに保存する。また、新しいノードを書き込むか、既存のノードを破棄した場合にもノードデータベースの内容を更新する。
【００１２】
次に、フラッシュメモリ用ファイルシステムに求められる、ウェアレベリング機能について説明する。
【００１３】
ウェアレベリングとは、フラッシュメモリ内のブロックの書き換え回数を均一にする機能であり、この機能が必要となる理由を説明するために、次にフラッシュメモリの書き換えの特性について説明する。
【００１４】
フラッシュメモリは、書込みをする前に内容を消去する必要があり、この消去が出来る消去可能回数は１万〜１００万回程度の有限の値である。フラッシュメモリは、使用上の利便性のために、その記憶領域を数ｋ〜数十ｋバイト程度のブロックに分割し、このブロック単位で消去を行うことにより、特定のブロックの消去回数が上限に達して使用不可となっても、他の消去回数の少ないブロックを引き続き使用可能としている。なお、ブロックの消去回数の上限は統計的にしか分からず、特定のブロックの残りの書き換え可能回数は、実際に使用不可となるまで知ることが出来ない。
【００１５】
フラッシュメモリは上記のような特性を持つため、もし特定のブロックに書き換えが集中すると、そのブロックは他のブロックよりも先に使用不可となり、フラッシュメモリ全体では利用可能な容量が減ってしまう。そのため、フラッシュメモリを搭載した製品が寿命となるまでの間、フラッシュメモリの容量を一定以上に保つためには、ウェアレベリングによってできるだけ各ブロックの書き換え回数を均一にすることが重要となる。
【００１６】
jffs2におけるウェアレベリングは、tailポインタとheadポインタによって書き込みと有効なノードのアドレスを管理することによって行う。jffs2において、tailポインタは、次にノードを書き込むべきフラッシュメモリ上のアドレスを保持しており、headポインタは最も古い有効なノードのあるアドレスを保持している。次に図２、および図３を用いて、このtailポインタとheadポインタを使用したノードの書き込みとガベージコレクション処理の動作を説明する。
【００１７】
図２は、jffs2によって使用中のフラッシュメモリ内のノードの配置の例を示す模式図であり、(a)はノードの配置の一例であり、(b)は新しいノードを書き込んだ直後のノードの配置の一例であり、(c)はtailポインタを更新した後のノードの配置の一例であり、(d)はノードの配置の一例であり、１はフラッシュメモリであり、１１はフラッシュメモリの先頭であり、１２はフラッシュメモリの末尾であり、１３はheadポインタが指すアドレスであり、１４はtailポインタが指すアドレスであり、１０１は有効なノードが存在しない範囲であり、１０２は有効なノードが存在する範囲であり、５１は新しく書き込んだノードである。
【００１８】
図３は、ガベージコレクションの際のノードの配置の変化を示す模式図であり、(a)はガベージコレクション処理の前の配置の一例であり、(b)はガベージコレクション処理によってノードを破棄した後の配置の一例であり、(c)はガベージコレクション処理によってノードを変更して書き写した後の配置の一例であり、(d)はガベージコレクション処理によってノードを変更せずに書き写した後の配置の一例であり、１はフラッシュメモリであり、１１はフラッシュメモリの先頭であり、１２はフラッシュメモリの末尾であり、１３はheadポインタが指すアドレスであり、１４はtailポインタが指すアドレスであり、１０１は有効なノードが存在しない範囲であり、１０２は有効なノードが存在する範囲であり、５２ａはノードであり、５２ｂはノードであり、５２ｃはノードである。
【００１９】
まず図２を用いて、tailポインタの使用法を説明する。フラッシュメモリ１内のノードの配置は一例として図２(a)に示すようになる。このフラッシュメモリ１にノードを書き込む際は、tailポインタの指すアドレス１４に図２(b)に示すようにノード５１として書き込む。書き込み後、図２(c)に示すように、tailポインタの内容をノード５１の次のアドレスに更新し、これにより、ノード５１は有効なノードとなる。
【００２０】
ノードの書き込みを繰り返すとtailポインタの指すアドレス１４はフラッシュメモリ１の末尾１２に近づくが、末尾１２に達した後はtailポインタの指すアドレス１４をフラッシュメモリ１の先頭１１に復帰してファイルシステムの動作を続ける。図２(d)に示した例では、tailポインタがフラッシュメモリ１の先頭１１に復帰した後もノードの書込みを続け、そのため、有効なノードが存在する範囲１０２は先頭１１に近い側と末尾１２に近い側に分かれている。
【００２１】
次に図３を用いて、ガベージコレクションの際のheadポインタの使用法を説明する。
【００２２】
図３(a)はガベージコレクション処理前のノードの配置の一例である。有効なノードが存在しない範囲１０１は消去して書込みのために再利用出来る領域であるが、フラッシュメモリ１へ書込みを続けるとこの範囲は次第に狭まり、新しいノードの書込みが出来なくなる。
【００２３】
有効なノードが存在する範囲１０２には無効となったノードや一部分が無効となったノードが含まれ、ガベージコレクション処理は次の手順で、これらの無効となったノードや無効となった部分を集め、書込みのための領域を増やす。ガベージコレクション処理は、tailポインタの指すアドレス１４とheadポインタの指すアドレス１３の差が一定以下になることをきっかけに始める。
【００２４】
ガベージコレクション処理では、jffs2はheadポインタの指すアドレス１３のノード５２ａを調べ、ノード５２ａが無効であるか、または無効な部分を持つかによって次の処理を行う。
【００２５】
ノード５２ａが無効なノードである場合には、ノード５２ａを破棄し、単にheadポインタの指すアドレス１３をノード５２ａの次のアドレスに更新する。この処理の後のノードの配置は図３(b)のようになり、ノード５２ａのサイズだけ、有効なノードが存在しない範囲１０１が広がる。
【００２６】
ノード５２ａが無効な部分を持つノードである場合には、ノード５２ａの内容を最終的なファイルの内容で上書き更新し、tailポインタの指すアドレス１４に新しいノード５２ｂとして書き込む。この後、headポインタの指すアドレス１３をノード５２ａの次のアドレスに更新する。この処理の後のノードの配置は図３(c)のようになり、有効なノードが存在しない範囲１０１の大きさは変わらないが、ノード５２ｂの内容は全て最終的なファイルの内容に反映される有効なノードになり、反対にノード５２ｂと占有範囲が重複するノードは、無効なノードとなるか、または無効な部分を持ったノードとなり、無効なノードとなった場合は以降のガベージコレクションにより破棄される。
【００２７】
なお、ノード５２ｂがノードのサイズの上限に収まるならば、ノード５２ｂの占有範囲を広げて上書き更新することもできる。この場合、ノード５２ｂと占有範囲が重複するノードが無効となる機会が増える。
【００２８】
ノード５２ａが、無効な部分のない有効なノードである場合には、ノード５２ａを単にtailポインタの指すアドレス１４に新しいノード５２ｃとして書き写し、headポインタの指すアドレス１３をノード５２ａの次のアドレスに更新する。この処理の後のノードの配置は図３(d)のようになる。
【００２９】
上記のガベージコレクション処理は所望の空き容量が得られるまで続けられる。
【００３０】
上記で、無効な部分のないノードは、ガベージコレクションの際に内容を変更せずに書き写されるだけのノードであり、以下、変更不要のノードと呼ぶことにする。また、無効な部分を持つノードはガベージコレクションの際に内容の変更が必要であり、破棄される無効なノードと合わせて、以下、変更必要なノードと呼ぶことにする。
【００３１】
上記のガベージコレクション処理の際に、headポインタの指すアドレス１３がフラッシュメモリ１の末尾１２に達したならば、headポインタの指すアドレス１３をフラッシュメモリ１の先頭１１に復帰してファイルシステムの動作を続ける。
【００３２】
上記のように、有効なノードの配置をheadポインタで管理し、フラッシュメモリへの書き込みはtailポインタで管理し、このtailポインタがフラッシュメモリのアドレスの全範囲を走査して行くため、フラッシュメモリの全てのアドレスへの書き込み回数は均一になり、ウェアレベリングを実現できる。
【００３３】
なお、ウェアレベリングの実現方法としては、jffs2のようにファイルシステムにその機能を持たせる方法だけでなく、特許文献１に見られるように、メモリチップにハードウェア的にウェアレベリング機能を持たせる方法や、非特許文献２に見られるように、ファイルシステムよりも下位のデバイスドライバで実現する方法もある。
【００３４】
【非特許文献１】JFFS : The Journalling Flash File System   David Woodhouse Red Hat, Inc.
【非特許文献２】UBI - Unsorted Block Images   Thomas Gleixner,Frank Haverkamp,Artem Bityutskiy IBM corp.
【特許文献１】特開２００１−６７２５８
【発明の開示】
【発明が解決しようとする課題】
【００３５】
従来例であるjffs2においては、ガベージコレクションの際に、内容を変更する必要の無い変更不要のノードはフラッシュメモリ内を移動するだけであり、ガベージコレクションの目的である容量の確保には寄与しない。特に、変更頻度の低いファイルがファイルシステム中に多数あると、ガベージコレクションの際に変更不要なノードも多数になり、ガベージコレクション処理は所望の空き容量を確保するために繰り返し行われ、処理時間が増え、また書き換え回数も増える。このため、フラッシュメモリの寿命を縮めてしまうことにもなる。
【００３６】
本発明の課題は、jff2のガベージコレクション処理の際に発生する無駄なノードの移動を減らし、これによりガベージコレクション処理動作を速くすることと、フラッシュメモリの寿命を延ばすことが可能なファイルシステムを得ることにある。
【課題を解決するための手段】
【００３７】
上記課題を解決するため、headポインタとtailポインタの指すアドレスがフラッシュメモリの末尾に達した場合にフラッシュメモリの先頭アドレスに最も近い変更必要なノードのアドレスへと復帰する。
【発明の効果】
【００３８】
本発明によれば、ガベージコレクションの際に変更不要なノードのうち、フラッシュメモリ先頭にあるものは、ガベージコレクション処理の対象とならない。また、フラッシュメモリ先頭から変更不要なノードが連続している連続領域内のノードもガベージコレクション処理の対象とならない。よって、ガベージコレクションの対象を減らすことができるため、処理動作を速くすることと、フラッシュメモリの寿命を延ばすことが可能となる。
【００３９】
なお、上記連続領域内のノードは、ノードの変更が必要となるまでフラッシュメモリ上で位置を変えない。また連続領域の外にある変更不要なノードも、ガベージコレクションの際に上記の連続領域に接する位置に書き写されれば連続領域に組み込まれ、次回以降のガベージコレクション処理の対象から外れる。よって、ガベージコレクションを繰り返すうちに変更不要なノードは上記の連続領域に集められ、まとめてガベージコレクションの対象から外れるため、本発明の効果がいっそう高くなる。
【００４０】
なお、いったん連続領域に集められたノードであっても、そのノードが属するファイルが変更され、ノードの変更が必要になれば、次回にheadポインタとtailポインタが復帰する際にそのノードのアドレスに復帰するため、再びガベージコレクションの対象となる。その際、一時的に連続領域が減るため、ガベージコレクションの対象が増え、本発明の効果が減じられるが、前記したように、ガベージコレクションが繰り返されるうちに変更不要なノードが再び連続領域に集まる。
【００４１】
以上を繰り返すうちに、変更頻度の低いファイルに属するノードはフラッシュメモリの先頭に近い位置に配置され、変更頻度の高いファイルに属するノードはフラッシュメモリの末尾に近い位置に配置され、変更頻度の低いファイルに変更があった場合でも、ガベージコレクションの際に影響が及ぶノードを最小化するように自然と最適化される。
【００４２】
本発明により、ガベージコレクションによる書き換え処理はフラッシュメモリの末尾に近い位置に集中し、これはウェアレベリングの目的に反する動作であるが、特許文献１や非特許文献２に見られる技術を併用することでウェアレベリングを行うことが出来る。
【発明を実施するための最良の形態】
【００４３】
以下において、本実施の形態を図面を用いて説明する。なお、本発明は、図示例に限定されるものではない。
【００４４】
まず、図１を用いて、本実施の形態に係るファイルシステムの構成を説明する。
【００４５】
フラッシュメモリ１は、デバイスドライバ２から特定のプロトコルでアドレスとデータを指定されることにより、指定されたアドレスにデータを書き込み、または読み出しをする。デバイスドライバ２はフラッシュメモリ１に直接読み書きするソフトウェアコンポーネントであり、フラッシュメモリの品種ごとの違いを吸収して、統一したインターフェースをファイルシステム３に提供する。ファイルシステム３はデバイスドライバ２の提供するインターフェースを利用して、ノードをフラッシュメモリ１へ読み書きする。アプリケーション４は、ファイルシステム３に対してファイルの読み書きを要求する。
【００４６】
ファイルシステム３は、ファイルシステム制御部３１とノードデータベース３２とheadポインタ３３とtailポインタ３４と復帰処理用ポインタ３５とからなる。
【００４７】
ノードデータベース３２は、フラッシュメモリ１内にある全てのノードの管理情報と、そのノードのフラッシュメモリ１内でのアドレスを保持しており、その初期値は、本ファイルシステムをマウントする際にファイルシステム制御部３１がフラッシュメモリ１内の全ノードを走査することで得る。
【００４８】
ノードの管理情報には、少なくともノードのバージョン番号と、ノードの属するファイル名と、ノードが保持する内容がファイル内で占める占有範囲に関する情報が含まれており、ファイルシステム制御部３１は、ファイルを読み出す際にノードデータベース３２を参照することで、そのファイルを再現するのに必要な全てのノードを特定し、そのノードの格納されたアドレスを得られる。
【００４９】
またファイルシステム制御部３１は、ノードデータベース３２を参照することで、複数のノードの占有範囲が重複していることも検出でき、重複した範囲の内容としてどちらのノードの内容を使用すべきかをノードのバージョン番号から判定できる。
【００５０】
headポインタ３３はフラッシュメモリ１内でガベージコレクションを開始するアドレスを保持しており、tailポインタ３４は次にノードを書き込むべきフラッシュメモリ１内のアドレスを保持している。tailポインタ３４の初期値は、ノードデータベース３２が初期値を得た時点で、ノードデータベース３２中で最も新しいノードの、次のアドレスを設定する。headポインタ３３の初期値は、tailポインタ３４の初期値が決定した時点で、tailポインタ３４の示すアドレスからフラッシュメモリ内の末尾に向けてノードを走査していき、初めて見つかった有効なノードの次のアドレスを設定する。
【００５１】
復帰処理用ポインタ３５は、headポインタ３３とtailポインタ３４の指すアドレスがフラッシュメモリ１の末尾に達した場合に、headポインタ３３とtailポインタ３４の内容を適切なアドレスへと復帰させる復帰処理のために使用する。
【００５２】
次に図４を用いて、本実施の形態に係るファイルシステムの書き込み動作を説明する。
【００５３】
図４(a)の６はアプリケーション４が書込みを要求したファイルであり、アプリケーション４は書き込み要求とともにファイル６をファイルシステム制御部３１に送る。ファイルシステム制御部３１は、ファイル６の内容をノードに格納可能なサイズに分割し、管理情報７を付加して図４(b)に示すノード５３ａ、ノード５３ｂ、ノード５３ｃを生成する。次に、ファイルシステム制御部３１は各ノードをデバイスドライバ２に送り、書込みを要求する。デバイスドライバ２の書込み処理の結果、ノード５３ａ、ノード５３ｂ、ノード５３ｃは、例えば図５(c)に示す配置のように、フラッシュメモリ１上に配置される。
【００５４】
また、ファイルシステム制御部３１は、前記生成したノードの管理情報７と、ノードを書き込んだアドレスをノードデータベース３２に登録し、tailポインタ３４の内容を、最後に書き込んだノードの次のアドレスへと更新する。
【００５５】
以上の動作で本実施の形態に係るファイルシステム３はファイルを書き込む。
【００５６】
次に図５を用いて、本実施の形態に係るファイルシステムが既存のファイルを書き換える動作を説明する。
【００５７】
アプリケーション４はファイル６の一部の書き換えをファイルシステム制御部３１に要求し、変更部分６１を書き換え要求とともにファイルシステム制御部３１に送る。ファイルシステム制御部３１は、変更部分６１をノードに格納可能なサイズに分割し、管理情報７を付加して図５(b)に示すノード５３ｄを生成する。次に、ファイルシステム制御部３１はノード５３ｄをデバイスドライバ２に送り、書込みを要求する。
【００５８】
デバイスドライバ２の書込み処理の結果、ノード５３ｄは、例えば図６(c)に示す配置のように、フラッシュメモリ１上に配置される。
【００５９】
また、ファイルシステム制御部３１は、前記生成したノードの管理情報７と、ノードを書き込んだアドレスをノードデータベース３２に登録し、tailポインタ３４の内容を、最後に書き込んだノードの次のアドレスへと更新する。
【００６０】
以上の動作で本実施の形態に係るファイルシステム３はファイルを書き換える。
【００６１】
次に図６を用いて、本実施の形態に係るファイルシステムがファイルを読み出す動作を説明する。
【００６２】
まず、アプリケーション４がファイル６の読み出し要求をファイルシステム制御部３１に送る。ファイルシステム制御部３１はノードデータベース３２を参照し、指定されたファイル６に属するノード５３ａ、ノード５３ｂ、ノード５３ｃ、ノード５３ｄを特定し、これらのノードのバージョン番号と、ノードの占有範囲と、ノードのフラッシュメモリ１内でのアドレスを得る。
【００６３】
次にファイルシステム制御部３１は、デバイスドライバ２を使って、フラッシュメモリ１内に図６(a)の例のように配置されたノード５３ａ、ノード５３ｂ、ノード５３ｃ、ノード５３ｄを読み出し、各ノードのバージョン番号の古い順に各ノードが保持する内容を占有範囲に配置していく。この過程で、占有範囲が重複しているノードがあれば、バージョン番号の古いノードの重複した部分は、新しいノードの内容で上書きされる。図６(b)の例では、ノード５３ｂの保持する内容の一部と、ノード５３ｃの保持する内容の全てが、ノード５３ｄの保持する内容によって上書きされ、結果として、図６(c)の内容のファイル６を得る。
【００６４】
なお、上記のノード５３ｃの例のように、最終的なファイルの内容に反映されない内容しか持たないノードについては、フラッシュメモリ１から読み出す動作を省略しても良い。
【００６５】
ファイルシステム制御部３１は、上記によって得られたファイル６をアプリケーション４に渡し、読み出し動作は終了する。
【００６６】
次に図７と図８を用いて、本実施の形態に係るファイルシステムのガベージコレクション処理の動作を説明する。
【００６７】
図７において(a)はガベージコレクション開始前のフラッシュメモリ１内のノードの配置を示しており、tailポインタの指すアドレス１４からheadポインタの指すアドレス１３までの間の、有効なノードの無い範囲１０１が一定以下になると、ファイルシステム制御部３１は図８のフローチャートに示す手順でガベージコレクション処理を始める。
【００６８】
まず、図８の処理Ｓ１１において、ファイルシステム制御部３１はノードデータベース３２を参照し、headポインタ３３の指すノード５４ａが属するファイルを特定し、また、特定したファイルに属する全てのノードの管理情報７を取得し、次に処理Ｓ１２に移る。
【００６９】
次に、処理Ｓ１２において、処理Ｓ１１で取得したノードの管理情報７からノード５４ａの内容を判断し、ノード５４ａが無効であるならば処理Ｓ１３に分岐し、ノード５４ａの内容に無効な部分があるならば処理Ｓ１４に分岐し、ノード５４ａの内容が全て有効であれば、処理Ｓ１６に分岐する。
【００７０】
処理Ｓ１３では、なにもせずに処理Ｓ１７に移る。
【００７１】
処理Ｓ１４では、ノード５４ａがファイル内で占有する範囲についてファイルの読み出し処理を行い、前記占有範囲についてファイルの最終的な内容を取得し、次に処理Ｓ１５に移る。なお、前記占有範囲は、ノード５４ａのサイズを越えてノードに収まる最大サイズまで拡張して、ファイルの最終的な内容を取得しても良い。占有範囲を拡張することにより、占有範囲の重複した他のノードを無効とする機会が増えるためである。
【００７２】
処理Ｓ１５では、処理Ｓ１４で取得した内容でノード５４ｂを生成し、tailポインタの指すアドレス１４に書き込み、ノードデータベース３２にノード５４ｂを登録し、tailポインタ３４を更新して次に処理Ｓ１７に移る。
【００７３】
処理Ｓ１６では、ノード５４ａと同じ内容のノード５４ｃを生成し、tailポインタの指すアドレス１４に書き込み、ノードデータベース３２にノード５４ｃを登録し、tailポインタ３４を更新して、次に処理Ｓ１７に移る。
【００７４】
処理Ｓ１７では、headポインタ３３をノード５４ａの次のアドレスへ更新し、ノードデータベース３２からノード５４ａを削除し。処理Ｓ１８に移る。処理Ｓ１７が終了した時点で、フラッシュメモリ１内のノードの配置は、処理Ｓ１３を経由した場合には図７(b)の例のようになり、処理Ｓ１４を経由した場合には図７(c)の例のようになり、処理Ｓ１６を経由した場合には図７(d)の例のようになる。
【００７５】
処理Ｓ１８では、headポインタ３３とtailポインタ３４の差を確認し、所定の値以上であれば終了する。所定の値に満たない場合は処理Ｓ１１に移る。
【００７６】
本実施の形態においては、上記の手順により、ガベージコレクション処理を行う。
【００７７】
次に図９と図１０を用いて、本実施の形態に係るファイルシステムでのheadポインタ３３とtailポインタ３４の復帰処理の動作を説明する。
【００７８】
上記のガベージコレクション処理中にheadポインタの指すアドレス１３がフラッシュメモリ１の末尾１２に達した場合、ファイルシステム制御部３１は次回のガベージコレクション処理を行うために、図１０のフローチャートに示す手順で、headポインタ３３を適切なアドレスに復帰する。
【００７９】
まず、図１０の処理Ｓ２１において、復帰処理用ポインタ３５の内容をフラッシュメモリ１の先頭１１とし、処理Ｓ２２に移る。
【００８０】
処理Ｓ２２では、復帰処理用ポインタ３５の指すノードが属するファイルを、ノードデータベース３２を参照して特定し、また、特定したファイルに属する全てのノードの管理情報７を取得し、処理Ｓ２３に移る。
【００８１】
処理Ｓ２３では、処理Ｓ２２で取得した管理情報から復帰処理用ポインタ３５の指すノードの内容を判断し、復帰処理用ポインタ３５の指すノードの内容が全て有効な変更不要なノードであれば処理Ｓ２４に分岐し、復帰処理用ポインタ３５の指すノードが無効か、または内容に無効な部分がある変更必要なノードならば処理Ｓ２５に分岐する。
【００８２】
処理Ｓ２４では、復帰処理用ポインタ３５の内容を、復帰処理用ポインタ３５の指すノードの次のアドレスに更新し、処理Ｓ２２に移る。
【００８３】
処理Ｓ２５では、復帰処理用ポインタ３５の内容をheadポインタ３３にコピーし、終了する。
【００８４】
図９の例では、上記の手順の結果、復帰処理用ポインタ３５の内容は変更必要なノード５７のアドレス１５となり、headポインタ３３もアドレス１５に復帰する。
【００８５】
また、tailポインタの指すアドレス１４がフラッシュメモリ１の末尾１２に達した場合には、tailポインタ３４はheadポインタ３３と同じアドレス１５に復帰させる。これは、復帰処理用ポインタ３５の内容を破棄せずに保持しておき、tailポインタ３４を復帰する際に利用することで実現できる。
【００８６】
図９において、従来例であるjffs2では、headポインタおよび、tailポインタの指すアドレスはフラッシュメモリ１の全範囲を移動し、フラッシュメモリ１内の全てのノードがガベージコレクション処理の対象となるが、本実施の形態では、headポインタおよび、tailポインタの指すアドレスは範囲１０３の間を移動し、範囲１０３の外にあるノードはガベージコレクション処理の対象とならない。
【００８７】
本発明では、範囲１０３の外にある、ガベージコレクション処理の際に内容を変更せずに無駄に移動するだけのノードをガベージコレクション処理の対象から外すことで、処理時間を短縮し、また無駄な書き換えでフラッシュメモリの寿命を短くすることを防ぐことができる。
【００８８】
本発明は、特にフラッシュメモリを媒体として利用したファイルシステムにおいて有効であるが、フラッシュメモリ以外の媒体にも利用可能である。例えば光ディスクメディアでは、書き換え動作よりも追記動作によってデータを書き込む方が速度などの点で好ましいが、このような媒体に本発明を応用すれば、書き換え動作が少なくなり、高速化が期待できる。
【図面の簡単な説明】
【００８９】
【図１】本実施の形態に係るファイルシステムのソフトウェア内部構成と、周辺のソフトウェア構成を示す構成図である。
【図２】従来例であるjffs2によって使用中のフラッシュメモリ内のノードの配置の例を示す模式図である。
【図３】従来例であるjffs2においてガベージコレクションの際のノードの配置の変化を示す模式図である。
【図４】(a)は書き込み要求されたファイルの模式図であり、(b)はファイルから作成したノードの模式図であり、(c)はフラッシュメモリ上のノードの配置の例を示す模式図である。
【図５】(a)は書き換え要求されたファイルの模式図であり、(b)は変更部分から作成したノードの模式図であり、(c)はフラッシュメモリ上のノードの配置の例を示す模式図である。
【図６】(a)はフラッシュメモリ上のノードの配置の例の模式図であり、(b)は読み出したノードの模式図であり、(c)はノードから再構成したファイルである。
【図７】(a)はガベージコレクション処理の前のノードの配置の一例を示す模式図であり、(b)はガベージコレクション処理によりノードを廃棄した後のノードの配置の一例を示す模式図であり、(c)はガベージコレクション処理によりノードを変更して書き写した後のノードの配置の一例を示す模式図であり、(d)はガベージコレクション処理によりノードを変更せずに書き写した後のノードの配置の一例を示す模式図である。
【図８】本実施の形態に係るファイルシステムのガベージコレクション処理の手順を示すフローチャートである。
【図９】本実施の形態にかかるファイルシステムにおいてheadポインタがフラッシュメモリの末尾から復帰する際のフラッシュメモリ内のノードの配置を示す模式図である。
【図１０】本実施の形態に係るファイルシステムの復帰処理の手順を示すフローチャートである。
【符号の説明】
【００９０】
１…フラッシュメモリ、１１…先頭、１２        …末尾、１３…headポインタの指すアドレス、
１４            …tailポインタの指すアドレス、１５…アドレス、１０１…有効なノードの無い範囲１０２…有効なノードの有る範囲、１０３…範囲、２…デバイスドライバ、３…ファイルシステム、３１…ファイルシステム制御部、３２…ノードデータベース、３３…headポインタ、３４…tailポインタ、３５…復帰処理用ポインタ、４…アプリケーション、５１…ノード、５２ａ…ノード、５２ｂ…ノード、５２ｃ…ノード、５３ａ…ノード、５３ｂ…ノード、５３ｃ…ノード、５３ｄ…ノード、５４ａ…ノード、５４ｂ…ノード、５４ｃ…ノード、５５…変更不要なノード、５６…変更不要なノード、５７…変更必要なノード、６…      ファイル、６１…変更部分、７…管理情報
【図１】
2008191797.tif 000003
【図２】
2008191797.tif 000004
【図３】
2008191797.tif 000005
【図４】
2008191797.tif 000006
【図５】
2008191797.tif 000007
【図６】
2008191797.tif 000008
【図７】
2008191797.tif 000009
【図８】
2008191797.tif 000010
【図９】
2008191797.tif 000011
【図１０】
2008191797.tif 000012