(57)【要約】【課題】  本発明はガーベッジコレクション高速化方法に関し、フラッシュメモリの利用効率を改善することができ、かつフラッシュメモリの寿命を延ばすことができるガーベッジコレクション高速化方法を提供することを目的としている。【解決手段】  一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、書き換えの発生しない固定データをブロック単位に区切り、該ブロック内に不要データが発生しないように構成する。【選択図】    図２
2006235960.tif 000002
【特許請求の範囲】
【請求項１】
一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、書き換えの発生しない固定データをブロック単位に区切り、
該ブロック内に不要データが発生しないようにすることを特徴とするガーベッジコレクション高速化方法。
【請求項２】
一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリを実装している移動機若しくは端末装置において、システム内部の全プロセスがアイドル状態となった場合に、全ページが不要データとなっているブロックの消去を行なうことを特徴とするガーベッジコレクション高速化方法。
【請求項３】
一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、１ブロック当たりのページ数と１ブロック消去する際に更新される管理データのページ数の比率により、該ファイルシステムにおいて妥当な論理ページ数を算出することを特徴とするガーベッジコレクション高速化方法。
【請求項４】
前記固定データを格納しているブロックの消去回数が不変とならないように、任意のタイミングでデータの入れ替えを行ない、消去回数の平均化を行なうことを特徴とする請求項１記載のガーベッジコレクション高速化方法。
【請求項５】
前記固定データを格納しているブロックのデータ書き換えが発生しても、固定データを格納している全てのブロックの消去回数を同一のものとし、かつブロック内のデータ属性を不変とすることを特徴とする請求項１記載のガーベッジコレクション高速化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はガーベッジコレクション高速化方法に関し、更に詳しくはフラッシュメモリを各種データの記憶用途として使用している移動機若しくは端末装置におけるガーベッジコレクション高速化方法に関する。ここで、ガーベッジコレクションとは、ある特定のブロックを再書き込みができるようにする一連の処理をいう。
【０００２】
フラッシュメモリは、不揮発性のメモリとして電源供給が失われてもデータを保持することが可能であり、かつデータを消去すれば再書き込みも行なえることから、例えばディジタルカメラ等の記憶手段として、利用が拡大されてきている。
【背景技術】
【０００３】
フラッシュメモリは、データの上書きが不可能であるため、ブロック内に不要データが発生することになる。図１７はフラッシュメモリのブロック内データ構成を示す図である。図において、１はブロックで、複数設けられている。これらブロックには、固定データ、可変データ、不要データが記憶される。
【０００４】
固定データは、プログラムデータ等、上書きされることのないデータである。不要データとはならない。可変データは、電話帳／メールのような上書きされる可能性のあるデータである。不要データは、可変データが上書きされた場合等に発生する消去対象データである。
【０００５】
前記不要データは、ガーベッジコレクションにて回収する必要があり、それにより再利用が可能となる。また、フラッシュメモリには消去回数に上限があるため、ウエアレベリングによる延命も行なっている。ここで、ウエアレベリングとは、各ブロックの消去回数がほぼ等しくなるようにバランスさせ、データの書き込み回数を調整することをいう。
【０００６】
従来のこの種のシステムとしては、上位装置から見たアクセス単位である論理ブロックを、フラッシュメモリの物理ブロックに割り当てる場合に、論理ブロックへのライト処理に際して、各論理ブロック単位にそのライト回数を計数管理し、物理ブロックの消去処理に際して、各物理ブロック単位にその消去回数を計数管理し、複数の論理ブロックを各々のライト回数により複数の論理ブロックグループに分類し、複数の物理ブロックを各々の消去回数により複数の物理ブロックグループに分類し、ライト回数の多い論理ブロックグループに属する論理ブロックへのライト処理に伴い当該論理ブロックを物理ブロックへ割り当てる際に、当該論理ブロックを消去回数の少ない物理ブロックグループに属する物理ブロックに割り当てる技術が知られている（例えば特許文献１参照）。
【０００７】
また、フラッシュメモリ内のデータ入れ替え時にホストからのアクセスがあっても、問題なくデータ領域の入れ替えを可能とした技術が知られている（例えば特許文献２参照）。
【特許文献１】特許第３５０７１３２号公報（段落００２１〜００４６、図１〜図１０）
【特許文献２】特開２００３−２１６５０６号公報（段落００１２〜００２２、図１〜図５）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
現在のファイルシステムにおいては、以下のような問題がある。
図１７のようにブロック内のデータ構成が固定データ、可変データ混在となってしまうため、ガーベッジコレクションにおける有効データ移動の際、固定データもその対象となり、処理能力の低下につながっている。前述した特許文献１記載の発明では、各データの上書き回数を管理することで、書き込み先のブロックを決定する方法を採っている。しかしながら、この発明では、以下に示すような問題がある。
１）初回書き込み時において、データの属性を決定することができないため、固定データのみを格納したブロックを生成することが困難である。
２）初回書き込み時において、データの属性を決定することができないため、初期状態では図１７と同様なデータ構成となってしまう。そのため、ある程度の上書きが発生しない限りガーベッジコレクションの高速化は望めない。
３）移動機のような携帯端末においては、補助電源が存在しないため、上書き回数を管理するデータはフラッシュメモリ上に存在する必要がある。そのため、データの上書きが頻繁に発生するようなシステムにおいては、著しくフラッシュメモリの寿命を縮めることになる。
【０００９】
フラッシュメモリのような上書きが行えないデバイスにおいては、ガーベッジコレクションの際に発生する有効データのコピー処理にて使用する空き領域を事前に確保しておく必要がある。このため、一般的に利用可能な論理ページ数は全物理ページ数の約７０％程度と言われているが、その値はフラッシュメモリの性能や使用するアプリケーションの要求仕様により大きく変わってしまう。従って、妥当な論理ページ数を算出することがフラッシュメモリの利用効率改善につながるが、その算出方法がないという問題がある。
【００１０】
本発明はこのような課題に鑑みてなされたものであって、フラッシュメモリの利用効率を改善することができ、かつフラッシュメモリの寿命を延ばすことができるガーベッジコレクション高速化方法を提供することを目的としている。
【課題を解決するための手段】
【００１１】
前述した課題を解決するためには、以下に示すような処理が必要となる。
１）ファイルシステムに対する書き込み要求時、データの属性を各アプリケーションが指定することで、初回書き込み時から固定データのみを保存したブロックを生成する。また、本ブロックはガーベッジコレクションの対象から外す。
２）固定データを保存しているブロックは、ガーベッジコレクションの対象外としているため、該ブロックの消去回数が増えることがない。従って、最大のブロック消去回数が一定値に達した場合、固定データ格納ブロックのデータを消去回数の大きいブロックへ移動する。
３）ファイルシステムに対する書き込み要求時、データの属性を各アプリケーションが指定することで、初回書き込み時から頻繁に更新されるデータと、殆ど更新されないデータを意識したブロック構成でデータを保存する。
４）フラッシュメモリの性能や使用するアプリケーションの要求仕様を元に妥当な論理ページ数を算出する。
【００１２】
このように構成することにより、ガーベッジコレクションの高速化と、フラッシュメモリの寿命を延ばすことが可能となる。また、フラッシュメモリの性能や使用するアプリケーションの要求仕様を意識し、それらの条件を満たした論理ページ数を算出する計算式を提供することで、今まで以上にフラッシュメモリを有効利用することができる。
【００１３】
（１）請求項１記載の発明は、一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、書き換えの発生しない固定データをブロック単位に区切り、該ブロック内に不要データが発生しないようにすることを特徴とする。
【００１４】
（２）請求項２記載の発明は、一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、該ページ毎にデータの書き込みを可能とするフラッシュメモリを実装している移動機若しくは端末装置において、システム内部の全プロセスがアイドル状態となった場合に、全ページが不要データとなっているブロックの消去を行なうことを特徴とする。
【００１５】
（３）請求項３記載の発明は、一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、１ブロック当たりのページ数と１ブロック消去する際に更新される管理データのページ数の比率により、該ファイルシステムにおいて妥当な論理ページ数を算出することを特徴とする。
【００１６】
（４）請求項４記載の発明は、前記固定データを格納しているブロックの消去回数が不変とならないように、任意のタイミングでデータの入れ替えを行ない、消去回数の平均化を行なうことを特徴とする。
【００１７】
（５）請求項５記載の発明は、前記固定データを格納しているブロックのデータ書き換えが発生しても、固定データを格納している全てのブロックの消去回数を同一のものとし、かつブロック内のデータ属性を不変とすることを特徴とする。
【００１８】
（６）また、この発明において、前記フラッシュメモリに保存するデータの属性を頻繁に更新されるデータと、殆ど更新されないデータに細分化し、各ブロック内部のデータ構成を不要データの多いブロックと少ないブロックとを意図的に作成することを可能とすることを特徴とする。
【００１９】
（７）また、この発明において、前記固定データ以外の属性を持ったデータにおいて、該データのサイズがブロックサイズの整数倍であった場合、ブロック単位の書き込みを行なうようにすることを特徴とする。
【発明の効果】
【００２０】
（１）請求項１記載の発明によれば、ブロック内に固定データで不要データが発生しないようにすることで、ガーベッジコレクションの対象から外し、ガーベッジコレクションの高速化を図ることができる。
【００２１】
（２）請求項２記載の発明によれば、アイドル状態において全ページが不要データとなっているブロックの消去を行なうことで、ガーベッジコレクションの高速化を図ることができる。
【００２２】
（３）請求項３記載の発明によれば、１ブロック当たりのページ数と１ブロック消去する際に更新される管理データのページ数の比率により、該ファイルシステムにおいて妥当な論理ページ数を算出することができる。
【００２３】
（４）請求項４記載の発明によれば、各ブロックの消去回数がほぼ等しくなるように、任意のタイミングでブロックの入れ替えを行なうことで、高速な処理を実現することが可能となる。
【００２４】
（５）請求項５記載の発明によれば、固定データを格納しているブロックのデータ書き換えが発生しても、固定データを格納している全てのブロックの消去回数を同一のものとし、かつブロック内のデータ属性を不変とすることで、ガーベッジコレクションの効率を向上させることができる。
【００２５】
（６）また、この発明において、フラッシュメモリに保存するデータの属性を頻繁に更新されるデータと、殆ど更新されないデータに細分化し、各ブロック内部のデータ構成を不要データの多いブロックと少ないブロックとを意図的に作成することで、ガーベッジコレクションの効率を向上させることができる。
【００２６】
（７）また、この発明において、固定データ以外の属性を持ったデータにおいて、該データのサイズがブロックサイズの整数倍であった場合、ブロック単位の書き込みを行なうようにすることで、ガーベッジコレクションの効率を向上させることができる。
【発明を実施するための最良の形態】
【００２７】
図１は本発明を実施するためのフラッシュメモリのデバイス構造を示す図である。対象となるフラッシュメモリは、ページ単位の書き込みとブロック単位の消去が可能となっている。ここでは、フラッシュメモリは２０４８のブロックからなり、各ブロックは３２ページ単位となっている。各ページの容量は、例えば５１２バイトである。
【００２８】
特性としては、上書き／ページ消去が不可能であるため、データを書き換える際は、空きページへ書き込む必要がある。書き込み時間は０．２ｍｓ、消去時間は２．０ｍｓ、消去回数は例えば最大１０万回程度である。
【００２９】
図２はファイルシステムの第１の構成例を示す図で、図１に示したフラッシュメモリを対象としている。ファイルシステム１０とアプリケーション２０とフラッシュメモリ３０とがそれぞれ接続されている。ファイルシステム１０内には、論理ページと物理ページの対応関係を示す論理物理変換テーブル１１が設けられている。
【００３０】
アプリケーション２０からファイルシステム１０に対して論理ページ５を指定してリード要求が発行される。ファイルシステム１０は、論理物理変換テーブル１１を参照して論理ページ５に対応する物理ページを指定する。ここでは、論理ページ５に対応する物理ページは４５であるので、ファイルシステム１０はフラッシュメモリ３０に対して物理ページ４５のデータリード要求を発行する。物理ページ４５のデータは、読み出されてアプリケーション２０に渡される。
【００３１】
図３はファイルシステムの第２の構成例を示す図であり、アプリケーションからの書き込み要求に対して、どの物理ページへデータを書き込むかを決定する空きページテーブルの構成図を示している。図２と同一のものは、同一の符号を付して示す。ファイルシステム１０では、アプリケーション２０からの書き込み要求（論理ページ番号３）のデータを、どの物理ページへ書き込むかを空きページテーブル１２を用いて決定する。空きページテーブル１２には、現在空きページである物理ページ番号が記憶されている。
【００３２】
空きページは、消去回数の少ないブロックに属するページ番号から順に格納されている。そのため、空きページ番号は空きページテーブル１２の先頭から取り出すことになる。空きページテーブル１２の先頭から取得した物理ページ番号３１へデータをライト要求により格納した後は、論理物理変換テーブル１１（図２参照）上に格納されている論理ページ番号３の参照先を物理ページ番号３から３１へ変更する。
【００３３】
図４はファイルシステムの第３の構成例を示す図であり、各ブロック内の不要ページ数を管理している不要ページテーブルの構成図を示している。図２と同一のものは、同一の符号を付して示す。１３は、各ブロック内の不要ページ数を管理している不要ページテーブルを示す。ファイルシステム２０からライト要求（論理ページ３）が発生したものとする。このライト要求がデータの上書き（つまり、論理物理変換テーブル１１に差分）が発生した場合に、上書き元の物理ページ番号３を不要ページ扱いとするため、該当するブロック１の不要ページ数を１増加させる。なお、論理物理変換テーブル１１より論理ページ３に対応する物理ページは３から３１に変更されている。そこで、フラッシュメモリ３０の物理ページ３１にデータが書き込まれることになる。
【００３４】
図５はファイルシステムの第４の構成例を示す図であり、各ブロックの消去回数を管理している消去回数テーブルの構成図を示している。図２と同一のものは、同一の符号を付して示す。１４は消去回数を記憶する消去回数テーブル、１９はガーベッジコレクションである。フラッシュメモリは、データの上書きが行えないため、ガーベッジコレクション１９を起動することで、空き領域の生成（回収）を行なうことになる。
【００３５】
例えばガーベッジコレクションにてブロック２の消去が発生した場合、ファイルシステム１０では、消去回数テーブル１４における該当ブロック番号の消去回数を１増加させることで、各ブロックの消去回数を管理している。例えば、不要ページテーブル１３（図４参照）を用い、最も効率のよいブロック消去（回収）を行なっている。
【００３６】
つまり、図４のようなデータ構成の場合、ブロック番号２の内部は全て不要ページとなっており、有効データの移動を行わなくてもブロック消去が可能であるため、該ブロックの消去動作が優先的に行われることになる。即ち、ファイルシステム１０は、不要ページテーブルを参照し、最も効率よく削除処理の行なえるブロックを検索する。この場合、ブロック２は全て不要ページであり、有効ページの移動が発生しないので、最も効率的である。ガーベッジコレクションでブロック番号２の消去を行なうように指令すると、ファイルシステム１０はフラッシュメモリ３０のブロック番号２の領域をブロック消去する。ブロック消去が終了したら、ファイルシステム１０に対して消去完了通知を発行する。
【００３７】
図６は固定データの管理方法を示す図である。固定データは、プログラムデータ等のような上書きの発生しないものを指し、ユーザアプリケーション２０が書き込み要求時に該固定データの属性を指定する必要がある。ファイルシステム１０では、アプリケーション２０からの書き込み要求（論理ページ３３）に対して、FlashWrite（）のパラメータを参照し、固定データの書き込み要求（EFsDataKindConst）であった場合には、固定データ格納ブロックにデータ（＆ｄａｔａ）を保存する。
【００３８】
その際、固定データブロックを新規に作成する必要がある場合には、固定データ管理テーブル１５に対して、該当ブロック番号を追加登録する。固定データ管理テーブル１５に登録されているブロックには、不要ページが発生することがないため、自動的にガーベッジコレクションの対象から外れることになる。これにより、該ブロックの内部構造が崩れる（固定データ以外のデータが紛れ込む）ことはなくなる。
【００３９】
また、固定データ管理テーブル１５は揮発メモリ上に保持することも可能であるが、その場合には、FlashWrite（）のタイミング以外に、移動機若しくは端末装置の立ち上がり（ブート処理）にて、FlashSetType（）を呼び出し、固定データ管理テーブル１５の再作成を行なう必要がある。固定データ管理テーブル１５は、システム立ち上げ時にデータ属性をアプリケーション２０が設定することで、揮発メモリに保持することも可能である。また、このテーブルに登録したブロックは、ガーベッジコレクションの対象から外し、ブロック入れ替えの対象として扱う。
【００４０】
図７はブロック間データ入れ替えの説明図である。図５、図６と同一のものは、どういつの符号を付して示す。図において、１４は消去回数テーブル、１５ａは旧固定データ管理テーブル、１５ｂは新固定データ管理テーブル、１９はガーベッジコレクションである。固定データを格納しているブロックは、その特性上、ガーベッジコレクションでの消去対象となることはなく、消去回数は常に不変となってしまう。フラッシュメモリには、消去回数に限界があるため、このようなブロックが存在することは、ウエアレベリングの観点から問題となる。従って、任意のタイミングで固定データを別ブロックへ移動する必要がある。
【００４１】
以下、ブロック間移動を行なう消去回数の基準値を１０００回として説明する。ガーベッジコレクションにてブロック１２９が消去されると、該ブロックの消去回数は１０００回となりブロック入れ替えの対象となる。ファイルシステム１０では、上記のような入れ替え対象ブロックが発生した時点で、ブロック間データ入れ替え処理を起動する。
【００４２】
先ず、固定データ管理テーブルの情報を更新するための新たな固定データ管理テーブル（新固定データ管理テーブル１５ｂ）を作成する。その後、旧固定データ管理テーブル１５ａに登録されているブロック１のデータを全てブロック１２９へ移動する。移動後は、旧固定データ管理テーブル１５ａからブロック１の情報を消去し、新固定データ管理テーブル１５ｂに新たな固定データブロック１２９を登録する。
【００４３】
更に、次回の消去動作にてブロック１３２が消去された場合には、ブロック２のデータを移動することになる。このように旧固定データ管理テーブル１５ａに登録されている全てのブロックデータを消去回数１０００のブロックへ移動した時点で、ブロック間データ入れ替え処理は終了となり、旧固定データ管理テーブル１５ａは完全に消去される。このように実装することで、入れ替え対象となるブロックの検索処理は不要となり、高速な処理を実現することができる。
【００４４】
図８は固定データの上書き処理シーケンスを示す図である。プログラムの書き換え等により、固定データの上書きが発生した場合の処理シーケンスを示している。通常、固定データは上書きされないことを前提としているが、アプリケーションソフトの不具合によってプログラムの書き換えが発生する場合がある。このような場合の処理シーケンスとなる。図において、２０はアプリケーション、１０はファイルシステム、４０はデータ書き換え行なうドライバである。
【００４５】
ファイルシステム１０では、アプリケーション２０からの書き込み要求のあった論理ページ３３に対応する物理ページが存在するかを論理物理変換テーブルを用いてチェックする（Ｓ１）。存在すれば、固定データの上書き要求と判断し、その他のページ（論理番号３４〜６４）をコピー対象として管理後、論理ページ３３のデータを新規ブロック１０へ保存する（Ｓ２）。この時点で固定データ管理テーブルへブロック１０は追加される。
【００４６】
論理ページ３３がブロック１０へ保存されたら、保存完了をファイルシステム１０へ通知する（Ｓ３）。ファイルシステム１０は、この保存完了を受けて、アプリケーション２０へ保存完了通知を行なう（Ｓ４）。アプリケーション２０からは書き込み要求がなされる（Ｓ５）。
【００４７】
その後も、ファイルシステムとしては、後続の論理ページ３４〜６４が更新されることを期待するが、仮に論理ページ３４〜６４以外の書き込み要求が発生した場合には、論理ページ３４〜６４は変更なしと見なし、同一データをブロック１０へコピーする（Ｓ６）論理ページ３４〜６４の移動が完了していないので、先にブロック１０へコピーすることになる。ドライバ４０で保存が完了したら、保存完了通知をファイルシステム１０に対して出す（Ｓ７）。移動が完了したら、ブロック２を固定データ管理テーブルから削除し、論理ページ７０の保存要求を行なう（Ｓ８）。ここで、論理ページ７０の書き込み処理は、以上の固定データの移動が完了した後に行なうことになる。
【００４８】
このように、固定データ管理テーブルからブロック２の削除処理を最後に行なうことで、固定データ移動中に電源断が発生した場合でも、次回の立ち上がり処理にて、ブロック２内にあるコピー途中のデータをブロック１０へ移動することが可能となる。即ち、固定データを格納しているブロックのデータ書き換えが発生しても、固定データを格納している全てのブロックの消去回数を同一のものとし、かつブロック内のデータ属性を不変とすることで、ガーベッジコレクションの効率を向上させることができる。また、固定データの上書き要求が発生した時点では、他の固定データ格納ブロックと同じ消去回数のブロックに保存することは不可能であるが、他の方式と組み合わせることで、ある程度の期間は要するが、問題を解決することは可能となる。
【００４９】
図９は固定データ以外の保存方法の説明図であり、「頻繁に更新されるデータ」と、「殆ど更新されないデータ」の保存方法の説明図である。ファイルシステム１０では、アプリケーション２０から書き込み要求のあったデータ属性（EFsDataKindFreq／EFsDataKindNotFreq）を参照し、データ（＆data）の保存先を消去回数の少ないページ番号を集めた空きページテーブル１２から取得するか、消去回数の多いページ番号を集めた空きページテーブル１２から取得するかを決定する。
【００５０】
「頻繁に更新されるデータ」は上書き回数が多いため、この属性のデータを保存しているブロックには不要ページが多く発生する。不要ページの多いブロックは、ガーベッジコレクションの対象となり、ブロック消去が行われる確率が高いため、消去回数の少ないブロックに保存する。「殆ど更新されないデータ」は、逆に上書き回数が少なくブロックが消去される確率が低いため、消去回数の多いブロックに保存することになる。
【００５１】
データ属性は、ファイルシステム１０にて提供するＡＰＩ（FlashWrite（））のパラメータとして設定されるため、ある程度ユーザの意向を反映させることが可能である。例えば、通常は電話帳、ｉアプリ等のようなデータ種別のみで判断するが、ｉアプリの中でも頻繁に更新されるもの／殆ど更新されないものが存在する。そこで、上位アプリケーションにて各データの更新回数を管理し、その条件を加えてデータ属性を決定することも可能である。
【００５２】
このように、データの属性をユーザが意識し、保存要求を行なうことで、ファイルシステムでは、初回書き込み時から該データの上書き頻度を認識することができる。その結果、ガーベッジコレクションにおける処理能力（効率）を常に高めることができる。
【００５３】
図１０は空きページテーブル作成方法の説明図である。図９に示す保存方法について使用する消去回数の少ない空きページテーブルと消去回数の多い空きページテーブルの作成方法である。ここでは、最大消去回数を１０００回、最小消去回数を５００回とする。空きページテーブル１２は、物理ページへの書き込み要求が発生する度に１ページ分ずつ消費されるため、ファイルシステム１０では、ブロック消去が発生した場合、対象ブロックの消去回数が最大値であれば消去回数の多い空きページテーブル、最小値であれば消去回数の少ない空きページテーブルへ追加登録する。
【００５４】
仮に、空きページテーブル１２への補充が間に合わない場合は、最大／最小の消去回数と消去回数テーブル１４を元に最小限のページ登録を行なう。そのため、頻繁に消費されることになる消去回数の少ない空きページテーブル１２は、消去回数の多い空きページテーブル１２に比べてサイズを大きくしていることが望ましい。
【００５５】
図１０では、説明のために最大消費回数と最小消費回数の差を大きくしたが、実用上はウエアレベリングが機能するため、最大値と最小値の差は殆どなくなる。従って、最大／最小の消去回数を元に空きページテーブル１２へ登録するブロック番号を消去回数テーブル１４から検索する処理が起動した場合でも、処理能力が低下することはない。
【００５６】
図１１はブロックサイズでの保存方法の説明図である。図９と同一のものは、同一の符号を付して示す。フラッシュメモリのページサイズは５１２バイトであるため、画像データのような１ページに収まらないデータも当然存在する。アプリケーション２０では、そのような場合、FlashPlurWrite（）によって複数ページ（ブロック）書き込み要求を行なう。通常のFlashWrite（）では、空きページテーブルから空いているページを取得し、そこへ保存するため、ブロック１０／１１のように分割して保存されてしまう。
【００５７】
それに対して、FlashPlurWrite（）では、新規に空きブロック２０を取得し、そこへ一括書き込みを行なうため、次回、該データの上書きが発生した場合、ブロック２０内は全て不要ページとなり、ガーベッジコレクションが効率よく行なえることになる。
【００５８】
図１２はブロックサイズでの保存処理のフローを示す図である。ファイルシステムでは、複数ページの書き込み要求（FlashPlurWrite（））が発生した場合（Ｓ１）、その要求ページ数をチェックする（Ｓ２）。図１２の例では、要求ページ数は３４ページである。ページ数が３２ページ（１ブロック）以上であれば、データ属性（EFsDataKindFreq）から適当な空きブロックを検索する（Ｓ３）。
【００５９】
空きブロックが検索されたら、最小消去回数から保存可能なブロックを検索する（Ｓ４）。次に、ブロック単位でのデータ保存を行なう（Ｓ５）。そして、残ったデータはFlashWrite（）のループ処理で保存する（Ｓ６）。ステップＳ３で適当な空きブロックがない場合には、最大消去回数から保存可能なブロックを検索してステップＳ５に進む（Ｓ７）。
【００６０】
なお、本発明におけるファイルシステムでは、空きページテーブルへの登録はブロック単位で行われており、かつ先頭ページから順次消費されるため、全てのブロックにおいて、先頭ページが空きであれば、他のページも全て空きとなる。つまり、空きブロックの検索処理は各ブロックの先頭ページのチェックを行なうのみでよいため、非常に高速に処理することが可能である。
【００６１】
図１３はアイドル状態でのブロック消去シーケンスを示す図である。このシーケンスは、システム内の全プロセスがアイドル状態になった場合に、ブロック消去を行なうためのシーケンスである。図において、２０はアプリケーション、５０はアプリケーション２０を管理するカーネル、６０はブロック消去プロセス、１０はファイルシステム、４０はデータの書き込みを行なうドライバである。カーネル５０では、全てのプロセスが待ち状態に移行すると（Ｓ１）。ブロック消去プロセス６０を起動しプログラム実行状態となる（Ｓ２）。
【００６２】
ここで、ブロック消去プロセス６０の優先度を最低レベルとすることで、他の全てのプロセスがＣＰＵを解放すれば、自動的に起動されるようになる。ブロック消去プロセス６０が起動されると、該ブロック消去プロセス６０は、ファイルシステム１０に対してブロック消去要求を発行する（Ｓ３）。ファイルシステム１０では、この要求を受け取ると、不要ページテーブルから３２ページ全て不要ページとなっているブロックを１つだけ検索する。
【００６３】
そして、該当ブロックを検索した後は、ドライバ４０へ１ブロック消去要求を発行し（Ｓ４）、この場合、可能な限り処理時間を短かくするため、１ブロックの消去のみを行なう。ドライバ４０はファイルシステム１０へ消去完了通知を発行する（Ｓ５）。ファイルシステム１０は、この消去完了通知を受けると、ブロック消去プロセス６０に消去完了通知を発行する（Ｓ６）。
【００６４】
ブロック消去プロセス６０は、この際、アプリケーション２０が実行可能状態となっている可能性があるため、一度ＣＰＵを解放する（Ｓ７）。この際、有効ページの移動が発生するようなガーベッジコレクションは起動させないようにする。これは、ブロック消去中に他プロセスが実行待ち状態になっていた場合でも、即座に処理を戻せるようにするためである。そして、アプリケーション２０を実行状態へ移行させる（Ｓ８）。
【００６５】
この処理によれば、アイドル状態において全ページが不要データとなっているブロックの消去を行なうことで、ガーベッジコレクションの高速化を図ることができる。
図１４は論理ページ数の算出方法の説明図である。一般的に、論理ページ数は全物理ページ数の約７０％が妥当な値と言われているが、その値はフラッシュメモリの性能や使用するアプリケーションの要求仕様により大きく変わってくる。例えば、図１４において、ある条件にて論理ページの割合を７０％とした場合のガーベッジコレクションの性能は、以下のようになる。
１ブロック消去するのに要する時間＝
有効ページの移動時間＋ブロック消去時間＋管理テーブル更新時間
＝２２（ページ）×０．２（ｍｓ）＋２．０（ｍｓ）＋３（ページ）×０．２（ｍｓ）
＝７．０（ｍｓ）
ここで、ブロック消去によって更新される管理テーブルとは、論理物理変換テーブル、消去回数テーブル、不要ページテーブルの３つである。
【００６６】
上記により、７ページの空き領域を確保するのに要する時間は、７．０ｍｓとなる。従って、１ページの空き領域を確保するのに要する時間は、１．０ｍｓとなる。
また、論理ページの割合を５０％とした場合には以下のようになる。
１ブロック消去するのに要する時間＝
有効ページの移動時間＋ブロック消去時間＋管理テーブル更新時間
＝１６（ページ）×０．２（ｍｓ）＋２．０（ｍｓ）＋３（ページ）×０．２（ｍｓ）
＝５．８（ｍｓ）
上記により、１３ページの空き領域を確保するのに要する時間は、５．８ｍｓとなる。従って、１ページの空き領域を確保するのに要する時間は、０．４ｍｓとなる。
【００６７】
つまり、０．４ｍｓで１ページの空き領域を確保したい場合には、論理ページの割合を７０％ではなく、５０％まで落とす必要がある。
以上の結果より、論理ページの割合をＰ、空きページを１つ回収するのに要する時間をＴ、１ブロック消去すると更新される管理テーブル数をＭ、１ブロック当たりのページ数をｎ、ページ書き込みに要する時間をａ、ブロック消去に要する時間をｂとすると、
１ブロック消去するのに要する時間            ：ａｎＰ＋ａＭ＋ｂ  （１）
１ブロック消去することで回収できるページ数  ：ｎ（１−Ｐ）−Ｍ  （２）
（１）、（２）式により、１ページ空き領域を確保するのに要する時間Ｔは、
ａｎＰ＋ａＭ＋ｂ：ｎ（１−Ｐ）−Ｍ＝Ｔ：１                      （３）
の比で表わすことができる。よって、（３）式をＴについて解くと以下のようになる。
Ｔ＝（ａｎＰ＋ａＭ＋ｂ）／｛ｎ（１−Ｐ）−Ｍ｝                    （４）
となる。また、論理ページの割合Ｐは、
Ｐ＝｛ｎＴ−Ｍ（Ｔ＋ａ）−ｂ｝／ｎ（Ｔ＋ａ）                      （５）
にて表わすことができる。
【００６８】
このように、本発明によれば、１ブロック当たりのブロック数と１ブロック消去する際に更新される管理データのページ数の比率により、該ファイルシステムにおいて妥当な論理ページ数を算出することができる。
【００６９】
図１５は固定データあり／なしの場合の不要ページ発生数の説明図である。固定データの概念を取り入れない（固定データ０％）場合、１ブロック当たりの不要ページ数は１０ページとなる。それに対し、固定データを２０％とした場合、固定データ数は、
６５５３６（ページ）×０．２＝１３１０７（ページ）
となる。固定データを格納するブロックには不要ページが発生せず、上書きも行なわれないため、論理ページの割合は以下のように求められる。
【００７０】
（４５８７５−１３１０７）÷（６５５３６−１３１０７）≒６２（％）  （６）
（６）式より、固定データ２０％の場合における１ブロック当たりの不要ページ数を算出すると、
３２（ページ）×（１．００−０．６２）≒１２（ページ）
となり、固定データなしの場合に比較して２ページ不要ページが増えることが分かる。これは１ブロック消去した場合に回収できるページ数が２増加し、かつ有効ページの移動回数が２減少したことを指しており、それだけガーベッジコレクションが高速になったことを意味している。
【００７１】
また、ガーベッジコレクションの処理能力は十分であるが、使用可能な論理ページが不足している場合は、
（６５５３６−１３１０７）×０．７≒３６７００（ページ）
と、（４５８７５−１３１０７）から３９３２ページ分、使用可能なメモリを増やすことも可能である。これを百分率で表わすと、
（３６７００＋１３１７０）÷（５２４２９＋１３１０７）≒７６（％）
となり、固定データなしの場合より、６％多くメモリを使用することが可能になることが分かる。
【００７２】
図１６はガーベッジコレクションの処理能力と管理テーブル数の関係を示す図である。（４）式において、Ｐを０．７、ｎを３２、ａを０．２、ｂを２．０とし、ＴをＭの関数として表すと次式のようになる。
【００７３】
Ｔ＝（０．２Ｍ＋６．５）／（９．８−Ｍ）            （７）
これをグラフで表すと図１６に示すようなものとなり、Ｔの値はＭの値により指数関数的に増加することが分かる。これは（７）式の分母（９．８−Ｍ）の９．８が重要なファクタとなっており、この値は論理ページの割合Ｐにより大きく左右される。図１４，図１５では、説明上、フラッシュメモリに保存している管理テーブル数を誤差の範囲として考慮していなかったが、前記特許文献１にある上書き回数管理テーブルのように、多種多様な管理テーブルをフラッシュメモリ上で管理すると、誤差の範囲では収まらなくなり、９．８に相当する値はより小さくなり、ガーベッジコレクションの処理能力を著しく低下させる原因となってしまう。図１６において、領域Ａでは管理テーブル数Ｍが増加する程、ガーベッジコレクションの処理能力は指数関数的に低下することが分かる。
【００７４】
（付記１）  一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、書き換えの発生しない固定データをブロック単位に区切り、
該ブロック内に不要データが発生しないようにすることを特徴とするガーベッジコレクション高速化方法。
【００７５】
（付記２）  一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリを実装している移動機若しくは端末装置において、システム内部の全プロセスがアイドル状態となった場合に、全ページが不要データとなっているブロックの消去を行なうことを特徴とするガーベッジコレクション高速化方法。
【００７６】
（付記３）  一度にメモリ消去できる最小の単位をブロックとし、該ブロック内部を複数のページに分割し、
該ページ毎にデータの書き込みを可能とするフラッシュメモリにおいて、１ブロック当たりのページ数と１ブロック消去する際に更新される管理データのページ数の比率により、該ファイルシステムにおいて妥当な論理ページ数を算出することを特徴とするガーベッジコレクション高速化方法。
【００７７】
（付記４）  前記固定データを格納しているブロックの消去回数が不変とならないように、任意のタイミングでデータの入れ替えを行ない、消去回数の平均化を行なうことを特徴とする付記１記載のガーベッジコレクション高速化方法。
【００７８】
（付記５）  前記固定データを格納しているブロックのデータ書き換えが発生しても、固定データを格納している全てのブロックの消去回数を同一のものとし、かつブロック内のデータ属性を不変とすることを特徴とする付記１記載のガーベッジコレクション高速化方法。
【００７９】
（付記６）  前記フラッシュメモリに保存するデータの属性を頻繁に更新されるデータと、殆ど更新されないデータに細分化し、各ブロック内部のデータ構成を不要データの多いブロックと少ないブロックとを意図的に作成することを可能とする付記１記載のガーベッジコレクション高速化方法。
【００８０】
（付記７）  前記固定データ以外の属性を持ったデータにおいて、該データのサイズがブロックサイズの整数倍であった場合、ブロック単位の書き込みを行なうようにすることを特徴とする付記１記載のガーベッジコレクション高速化方法。
【図面の簡単な説明】
【００８１】
【図１】本発明を実施するためのフラッシュメモリのデバイス構造を示す図である。
【図２】ファイルシステムの第１の構成例を示す図である。
【図３】ファイルシステムの第２の構成例を示す図である。
【図４】ファイルシステムの第３の構成例を示す図である。
【図５】ファイルシステムの第４の構成例を示す図である。
【図６】固定データの管理方法を示す図である。
【図７】ブロック間データ入れ替えの説明図である。
【図８】固定データの上書き処理シーケンスを示す図である。
【図９】固定データ以外の保存方法の説明図である。
【図１０】空きページテーブル作成方法の説明図である。
【図１１】ブロックサイズでの保存方法の説明図である。
【図１２】ブロックサイズでの保存処理フローを示す図である。
【図１３】アイドル状態でのブロック消去シーケンスを示す図である。
【図１４】論理ページ数の算出方法の説明図である。
【図１５】固定データあり／なしの場合の不要ページ発生数の説明図である。
【図１６】ガーベッジコレクションの処理能力と管理テーブル数の関係を示す図である。
【図１７】フラッシュメモリのブロック内データ構成を示す図である。
【符号の説明】
【００８２】
１０  ファイルシステム
１１  論理物理変換テーブル
２０  アプリケーション
３０  フラッシュメモリ
【図１】
2006235960.tif 000003
【図２】
2006235960.tif 000004
【図３】
2006235960.tif 000005
【図４】
2006235960.tif 000006
【図５】
2006235960.tif 000007
【図６】
2006235960.tif 000008
【図７】
2006235960.tif 000009
【図８】
2006235960.tif 000010
【図９】
2006235960.tif 000011
【図１０】
2006235960.tif 000012
【図１１】
2006235960.tif 000013
【図１２】
2006235960.tif 000014
【図１３】
2006235960.tif 000015
【図１４】
2006235960.tif 000016
【図１５】
2006235960.tif 000017
【図１６】
2006235960.tif 000018
【図１７】
2006235960.tif 000019