JP5120455B2 - ガーベジコレクションプログラム、及びガーベジコレクション方法、ならびにガーベジコレクションシステム - Google Patents

Description

本発明は、ブロック単位でデータを消去する補助記憶媒体を備える組み込みシステムにおいて、補助記憶媒体内のデータを消去する際にガーベジコレクション処理を行うガーベジコレクションプログラム、及びガーベジコレクション方法、ならびにガーベジコレクションシステムに関するものである。

近年の携帯電話機やカーナビケーションシステムに代表されるように、電子機器の小型化、多機能化、高性能化を可能にしているのは、これら装置内に搭載された組み込みシステムの技術の発達によるところが大きい。

組み込みシステムでは、コストやサイズを抑えるために、安価なＣＰＵや最小限のデータ容量のメインメモリでハードウェアを構成することが重要である。また、組み込みシステムに採用される補助記憶装置として、磁気ディスク装置より小型かつ高速アクセスが可能であり、ある程度の記憶容量のあるＮＡＮＤ型フラッシュメモリ（以下フラッシュメモリと略す）を採用することが多い。

図１３は、従来技術における、フラッシュメモリを用いた組み込みシステムを備える装置の構成の一例を示すブロック図である。組み込みシステムを備えた装置の例として、例えば上述の携帯電話機やカーナビゲーションシステムなどがあげられる。図１３に示す通り、装置１００は、組み込みシステム１０１として、装置内全てのデバイスの動作を制御するＣＰＵ１０２（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＣＰＵ１０２が直接データをやり取りする主記憶媒体であるメインメモリ１０３、データの記憶を行う補助記憶媒体であるフラッシュメモリ１０４を備える。

フラッシュメモリ１０４は、一度データを書き込むと、その書き込まれた領域の部分的な消去が行えず、その領域を含むブロック単位での消去のみが可能である。また消去回数も１０万回に制限されており、頻繁な書き換えを行えない。このような特性を考慮し、フラッシュメモリへの書き込み回数を低減することを目的とした追記型のファイルシステムがある。以下、追記型のファイルシステムを「ファイルシステム」と略す。なお、ファイルシステムにて記憶されるファイルの内容は、フラッシュメモリ上に存在し、メインメモリ上にはファイルを構成するデータのフラッシュメモリ上の位置といった管理情報のみを置いている。これにより、メインメモリの使用量を節約している。以下に、ファイルシステムの概念と、ファイルの読み出し、書き換え動作を説明する。

図１４は、追記型のファイルシステムにおける、データ読み出し処理の概念図である。なお、以下の各図において、同一符号は同一物又は相当物を示しており重複説明は省略する。図１４に示す通り、ファイルシステム１０５のアクセス対象は、メインメモリ１０３、フラッシュメモリ１０４とする。また、メインメモリ１０３には、データへのアクセスの排他制御を行うプログラムである排他機構１０７がロードされている。また、メインメモリ１０３には構成データ（後述にて詳細を説明する）が格納されているファイル１０８、ファイル１０８を構成するデータがフラッシュメモリ１０４のどこに格納されているかの位置情報が格納されているアドレステーブル１０９が保持されている。また、アドレステーブル１０９は、ファイル１０８を構成するデータの一つであるｄａｔａ＃ａが保持されているアドレスを指し示すａアドレスデータ１１３が保持されている。以下、アドレスを指し示すデータをアドレスデータと称す。また、アドレステーブル１０９は、ｄａｔａ＃ｂのアドレスデータであるｂアドレスデータ１１４と、ｄａｔａ＃ｃのアドレスデータであるｃアドレスデータ１１５とを保持しているものとする。

また、ファイル１０８は、アドレステーブル１０９への参照経路であるアクセス経路１１０から１１２を構成データとして保持している。なお、図１４において、アクセス経路１１０はｄａｔａ＃ａのアドレスデータ１１３までの参照経路であり、アクセス経路１１１はｄａｔａ＃ｂのアドレスデータ１１４までの参照経路であり、アクセス経路１１２はｄａｔａ＃ｃのアドレスデータ１１５までの参照経路である。

また、フラッシュメモリ１０４は、消去単位であるブロック１１６Ａ、Ｂ、・・・、Ｎにて構成される。以下、ブロックを総称するときはブロック１１６と称す。ブロック１１６は、フラッシュメモリ１０４の記憶容量によりＡ，Ｂ，Ｃ・・・Ｎと数が異なるものである。なお、図１４においては、ブロック１１６Ａにはｄａｔａ＃ａ１１７、ブロック１１６Ｂにはｄａｔａ＃ｂ１１８、ブロック１１６Ｃにはｄａｔａ＃ｃ１１９が格納されているものとする。また、プログラム１０６は、ファイルに対する読み書きのアクセスを要求するものであり、ここではファイル１０８を読み出すアクセスを行うものとする。また、ファイル１０８は、ここでは、ｄａｔａ＃ａ１１７、ｄａｔａ＃ｂ１１８、ｄａｔａ＃ｃ１１９とで構成されているものとする。

次に従来のフラッシュメモリを使用したファイルシステムのファイルのデータ読み出し動作について説明する。なお、以下に記載する全てのプログラムの動作はＣＰＵ１０２により実行される。

まず、プログラム１０６によるファイル１０８に対する読み出し指示を受けたファイルシステム１０５は、排他機構１０７に排他制御指示を行うことでファイル１０８を排他し、ファイル１０８に対する他のプロセスが干渉不可能な状態とする（排他処理）。次に、ファイルシステム１０５は、ファイル１０８に格納されている構成データより必要なデータを特定する。なお、ここでの必要データはｄａｔａ＃ａ１１７とする。次に、ファイルシステム１０５は、アクセス経路１１０を経てアドレステーブル１０９よりｄａｔａ＃ａ１１７のアドレスデータ１１３を取得し、フラッシュメモリ１０４からｄａｔａ＃ａ１１７をプログラム１０６に出力する。

ファイルシステム１０５は、プログラム１０６から要求されたファイル１０８のデータを出力後、排他機構１０７に排他制御の解除指示を行うことでファイル１０８の排他を解除し、データの読み出しは完了となる。

上述した動作により、フラッシュメモリを使用したファイルシステムによるファイルのデータ読み出しが行われる。

次に、ファイルシステム１０５におけるファイルのデータ内容変更処理について説明する。

図１５は、追記型ファイルシステムにおける、データ書き換え処理の概念図である。なお、データ内容を変更するデータはｄａｔａ＃ａ１１７であり、このｄａｔａ＃ａ１１７を変更したものがｄａｔａ＃ｉ１２１である。また、プログラム１２０は、ｄａｔａ＃ａ１１７をｄａｔａ＃ｉ１２１へ変更をするプログラムである。

まず、プログラム１２０によるファイル１０８に対する書き換え指示を受けたファイルシステム１０５は、排他機構１０７によりファイル１０８を排他し、排他処理を行う。次に、ファイルシステム１０５は、プログラム１２０の指示に基づきｄａｔａ＃ａ１１７の内容を変更し、変更後の内容ｄａｔａ＃ｉ１２１をフラッシュメモリ１０３の空き領域に書き込む。ｄａｔａ＃ｉ１２１の書き込み後、ファイルシステム１０５は、ｄａｔａ＃ｉ１２１の位置情報であるｉアドレスデータ１２２をアドレステーブル１０９へ追加する。位置情報追加後、ファイルシステム１０５は、ファイル１０８からｉアドレスデータ１２２へのアクセス経路１２３を追加し、古い内容のｄａｔａ＃ａ１１７は不要な為、ファイル１０８からのアクセス経路１１０を削除する。ここで、ファイルシステム１０５は、ｄａｔａ＃ａ１１７が不要であることを示すために、ａアドレスデータ１１３に状態フラグをマークする。この状態フラグがマークされると、ｄａｔａ＃ａ１１７へのアクセスが出来なくなり、読み書き不可となり、無効データとなる。状態フラグのマーク後、ファイルシステム１０５は、排他機構１０７によりファイル１０８の排他を解除し、データ内容変更は完了となる。

上述した動作により、フラッシュメモリを使用したファイルシステムのファイルのデータ内容変更が行われる。

しかしながら、上述したファイルのデータ内容変更を繰り返すと、フラッシュメモリ上に不要なデータ（無効なデータ。以下同様）が貯まり、フラッシュメモリの容量を浪費してしまう。その為、フラッシュメモリ上の不要なデータを集めて削除するガーベジコレクション（Ｇａｒｂａｇｅ Ｃｏｌｌｅｃｔｉｏｎ、以下ＧＣと略す）プログラムが必要となる。フラッシュメモリはブロック単位でのみ消去が可能であり、消去を行うにはブロック全体を不要なデータで埋める必要がある。上述したＧＣプログラムは、対象のブロック内に点在する有効なデータを他のブロックに移動（コピー）を行うことにより、対象のブロックの消去を可能にするものである。なお、ＧＣは、一般的にはＲＯＭに格納されているものであり、装置起動後にメインメモリに展開されるものである。以下に、ＧＣプロセスのファイルシステムに対する処理を説明する。

図１６から図１９は、ＧＣプログラムの動作の概念を示す図である。なお、図１６から図１９において、ＧＣプログラムの対象ブロックをブロック１１６Ａとし、ブロック１１６Ａは、必要データとしてｄａｔａ＃ａ１１７、ｄａｔａ＃ｂ１１８、ｄａｔａ＃ｃ１１９と、不要データ１２４にて構成されているものとする。また、ブロック１１６Ｂは必要データであるｄａｔａ＃ｘ１２５で構成され、空き領域１２６が存在するものとする。

まず、ＧＣプログラムは、図１６に示されている初期状態から、図１７に示す通り、必要データであるｄａｔａ＃ａ１１７、ｄａｔａ＃ｂ１１８、ｄａｔａ＃ｃ１１９の複製データ（ｄａｔａ＃ａ'１２７、ｄａｔａ＃ｂ'１２８、ｄａｔａ＃ｃ'１２９）を、空き領域のある別ブロックであるブロック１１６Ｂに作成する。複製データを作成することにより、ＧＣプログラムは、図１８に示す通り、ブロック１１６Ａを不要データ１２４のみと判断する。次にＧＣプログラムは、不要データ１２４のみとなったブロック１１６Ａ内の不要データ１２４を消去することにより、図１９に示す通り、ブロック１１６Ａの全てが空き領域として使用可能状態とする。

以上の処理を経て、ＧＣプログラムはフラッシュメモリのデータ整理を行う。次に、上述したＧＣプログラムによるデータ整理処理におけるファイルシステムの概念を説明する。なお、ここでのデータ整理処理とは、ブロック１１６Ａ上のｄａｔａ＃ａ１１７を他のブロックへ移動する処理を表す。

図２０は、追記型ファイルシステムにおける、ＧＣプログラムの動作の概念図である。なお、ｄａｔａ＃ａ'１３１はｄａｔａ＃ａ１１７のコピーである。また、ＧＣプログラムはファイルシステム１０５に含まれ、ＧＣプログラムがファイルシステム１０５の機能の一部を担うものとして説明する。

まず、ＧＣプログラム１３０は、ファイルシステム１０５内の排他機構１０７に対しファイル１０８の排他を指示し、排他処理を行う。次にＧＣプログラム１３０は、ｄａｔａ＃ａ１１７の内容を読み出し、フラッシュメモリ１０４の空き領域にｄａｔａ＃ａ'１３１としてコピーし、アドレステーブル１０９にｄａｔａ＃ａ'１３１の位置情報であるａ'アドレスデータ１３２を追加する。位置情報追加後、ＧＣプログラム１３０は、ファイル１０８からａ'アドレスデータ１３２へのアクセス経路１３３を追加し、古い内容のｄａｔａ＃ａ１１７は不要な為、ファイル１０８からのアクセス経路１１０を削除する。アクセス経路１１０削除後、ＧＣプログラム１３０は、ｄａｔａ＃ａ１１７が不要であることを示すために、ａアドレスデータ１１３に状態フラグをマークし、排他機構１０７に対しファイル１０８への排他解除を指示し、データ整理は完了となる。

なお、本発明の関連ある従来技術として、不揮発性固体メモリ（フラッシュメモリ）を使用する上で避けることのできないガーベジコレクションを、所定のモードにおいて、他の不揮発性固体メモリ又は記録媒体にデータの書き込みを中断することなく並行して実行し、さらにホスト装置へのデータ転送に影響を及ぼすことなく並行して実行する技術が知られている（例えば、特許文献１参照）。
特開２００７−１９３８８３号公報

しかしながら、上述したＧＣプログラムは、フラッシュメモリ上のデータを移動するだけなので、他のプロセスへ影響を与えないように行いたいが、ＧＣプログラムによってファイルが排他されている最中に、他のプログラムによるそのファイルへのアクセスが発生すると、他のプロセスは待機を余儀なくされ、処理が遅延されてしまう。

本発明は上述した問題点を解決するためになされたものであり、データを移動する際の排他時間を低減するガーベジコレクションプログラム、及びガーベジコレクション方法、ならびにガーベジコレクションシステムを提供することを目的とする。

また、上述した課題を解決するため、本発明の一態様は、ブロック単位でのみデータ消去が可能な第１記憶装置のうちの、有効なデータと無効なデータとが混在する第１ブロックから、有効なデータを前記第１記憶装置とは別の記憶装置である第２記憶装置へコピーする第１複写ステップと、前記第１複写ステップでコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第１排他指示ステップと、前記第１排他指示ステップに基づく排他制御が行われた後、前記第１複写ステップにてコピーされるコピー元の有効なデータから、前記第１複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第１切替ステップと、前記第１切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第１排他解除指示ステップと、前記第１複写ステップにてコピーされたコピー先の有効なデータを、前記第２記憶装置から前記第１記憶装置のブロックであって前記第１ブロックとは別のブロックである第２ブロックに有効なデータをまとめるようコピーする第２複写ステップと、前記第２複写ステップにてコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第２排他指示ステップと、前記第２排他指示ステップに基づく排他が行われた後、前記第２複写ステップにてコピーされるコピー元の有効なデータから、前記第２複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第２切替ステップと、前記第２切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第２排他解除指示ステップとをコンピュータに実行させる。

また、上述した課題を解決するため、本発明の一態様は、ブロック単位でのみデータ消去が可能な第１記憶装置のうちの、有効なデータと無効なデータとが混在する第１ブロックから、有効なデータを前記第１記憶装置とは別の記憶装置である第２記憶装置へコピーする第１複写ステップと、前記第１複写ステップでコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第１排他指示ステップと、前記第１排他指示ステップに基づく排他が行われた後、前記第１複写ステップにてコピーされるコピー元の有効なデータから、前記第１複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第１切替ステップと、前記第１切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第１排他解除指示ステップと、前記第１複写ステップにてコピーされたコピー先の有効なデータを、前記第２記憶装置から前記第１記憶装置のブロックであって前記第１ブロックとは別のブロックである第２ブロックに有効なデータをまとめるようコピーする第２複写ステップと、前記第２複写ステップにてコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第２排他指示ステップと、前記第２排他指示ステップに基づく排他が行われた後、前記第２複写ステップにてコピーされるコピー元の有効なデータから、前記第２複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第２切替ステップと、前記第２切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第２排他解除指示ステップとを行う。

また、上述した課題を解決するため、本発明の一態様は、ブロック単位でのみデータ消去が可能な第１記憶装置のうちの、有効なデータと無効なデータとが混在する第１ブロックから、有効なデータを前記第１記憶装置とは別の記憶装置である第２記憶装置へコピーする第１複写部と、前記第１複写部でコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第１排他指示部と、前記第１排他指示部に基づく排他が行われた後、前記第１複写部にてコピーされるコピー元の有効なデータから、前記第１複写部にてコピーされたコピー先の有効なデータへアクセス経路を切り替える第１切替部と、前記第１切替部によるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第１排他解除指示部と、前記第１複写部にてコピーされたコピー先の有効なデータを、前記第２記憶装置から前記第１記憶装置のブロックであって前記第１ブロックとは別のブロックである第２ブロックに有効なデータをまとめるようコピーする第２複写部と、前記第２複写部にてコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第２排他指示部と、前記第２排他指示部に基づく排他が行われた後、前記第２複写部にてコピーされるコピー元の有効なデータから、前記第２複写部にてコピーされたコピー先の有効なデータへアクセス経路を切り替える第２切替部と、前記第２切替部によるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第２排他解除指示部とを備える。

本実施の形態に係る、ＧＣプログラムを備えた装置の構成の一例を示すブロック図である。 本実施の形態に係る追記型ファイルシステムの概念図である。 本実施の形態に係る、ＧＣプログラムの動作の一例を示すフローチャートである。 本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。 本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。 本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。 本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。 本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。 本実施の形態に係る、追記型ファイルシステムにおける他プログラムにより、ファイルが書き換えられ、必要データが不要データとなった場合（Ｓ１０３、ＮＯ）のＧＣプログラムの動作後の概念図である。 本実施の形態に係る、追記型ファイルシステムにおける他プログラムにより、ファイルが書き換えられ、必要データが不要データとなった場合（Ｓ１０８、ＮＯ）のＧＣプログラムの動作後の概念図である。 本実施の形態に係るＧＣプログラム処理と、従来技術のＧＣプログラム処理の比較図である。 本実施の形態に係る、ＧＣシステムの構成の一例を示すブロック図である。 従来技術における、フラッシュメモリを用いた組み込みシステムを備える装置の構成の一例を示すブロック図である。 追記型ファイルシステムにおける、データ読み出し処理の概念図である。 追記型ファイルシステムにおける、データ書き換え処理の概念図である。 ＧＣプログラムの動作の概念を示す図である。 ＧＣプログラムの動作の概念を示す図である。 ＧＣプログラムの動作の概念を示す図である。 ＧＣプログラムの動作の概念を示す図である。 追記型ファイルシステムにおける、ＧＣプログラムの動作の概念図である。

以下、本発明の実施の形態について図面を参照しつつ説明する。尚、ＧＣプログラムは上述同様、ファイルシステムに含まれ、ＧＣプログラムがファイルシステムの機能の一部を担うものとして説明する。

まず、本実施の形態に係るＧＣプログラムの構成について説明する。図１は、本実施の形態に係る、ＧＣプログラムを備えた装置の構成の一例を示すブロック図である。図１に示す通り、装置１は、組み込みシステム２として、装置１の動作を制御するＣＰＵ３、ＣＰＵ３がデータをやり取りする主記憶媒体であるメインメモリ４（第２記憶装置）、データの記憶を行う補助記憶媒体であるフラッシュメモリ５（第１記憶装置）、組み込みシステム２を制御するプログラムを格納している起動ＲＯＭ８０を備える。なお、本実施形態では、装置１は例として、携帯電話機やカーナビケーションシステム等の組み込み機器やパーソナルコンピュータ等、フラッシュメモリを搭載した、または搭載可能である装置であるものとする。

また、本実施の形態において、ＧＣプログラム６は、組み込みシステム２を制御する他のプログラムと一緒に起動ＲＯＭ８０に格納されているものとし、装置１起動後にメインメモリ４へ読み込まれるものである。また、ＧＣプログラム６は、コピー管理プログラム７と、排他指示プログラム８と、アクセス管理プログラム９と、判断プログラム１０とを備えるものである。

なお、コピー管理プログラム７は、フラッシュメモリ５に格納されているデータのコピー及びデータのアドレスデータをメインメモリ４上に作成するプログラムである。排他指示プログラム８は、メインメモリ４にロードされる排他機構にファイルの排他及び排他解除を指示し、ＧＣプログラム以外のフラッシュメモリ５へのアクセスを禁止及び許可するプログラムである。アクセス管理プログラム９は、メインメモリ４に展開されるファイルとアドレステーブル間のアクセス経路を作成及び削除を行い、アクセス経路を切り替えるプログラムである。判断プログラム１０は、メインメモリ４及びフラッシュメモリ５内のデータがＧＣの対象となるデータであるか、対象でないデータであるかの判断を行うプログラムである。なお、上述した排他機構、ファイル、アドレステーブルについては、後述にて詳細を説明する。

図２は、本実施の形態に係る、追記型ファイルシステムの概念図である。図２に示す通り、ファイルシステム１１は、メインメモリ４、フラッシュメモリ５に保持されているデータのアクセスを制御、管理を行う。また、メインメモリ４には、構成データが格納されているファイル１２、ファイルの構成データがフラッシュメモリ５のどこに格納されているかのアドレスデータが格納されているアドレステーブル１４が保持されている。なお、アドレステーブル１４は、有効なデータあるいは対象データであるｄａｔａ＃ａ１７のアドレスデータであるａアドレスデータ１５を保持しているものとする。

また、ファイル１２は、構成データとしてアドレステーブル１４への参照経路であるアクセス経路１３が保持される。なお、アクセス経路１３は、ｄａｔａ＃ａ１７に対応するアクセス経路である。また、フラッシュメモリ５は、消去単位であるブロック１６Ａ（第１ブロック）、１６Ｂ（第２ブロック）、・・・、にて構成される。以降、ブロックを総称するときばブロック１６と称す。このブロック１６の数は、フラッシュメモリ５の記憶容量によってＡ，Ｂ，Ｃ・・・Ｎと数が異なるものである。なお、図２においては、ブロック１６Ａにはｄａｔａ＃ａ１７が格納されているものとする。また、ファイル１２は、ここでは、ｄａｔａ＃ａ１７にて構成されているものとする。

次に、本実施の形態に係るＧＣプログラムのデータ整理処理の動作の概要について説明する。なお、本実施の形態において、データ整理処理は、フラッシュメモリ５内に格納されている有効なデータを別ブロックへ移動し、有効なデータと無効なデータを整理する処理を表す。なお、ブロック１６Ａ上のｄａｔａ＃ａ１７をデータ整理処理の対象とする。図３は、本実施の形態に係る、ＧＣプログラムの動作の一例を示すフローチャートである。また、図４から図８は、本実施の形態に係る、追記型ファイルシステムにおけるＧＣプログラムの動作の概念図である。

まず、ＧＣプログラム６は、判断プログラム１０により、移動の対象となるｄａｔａ＃ａ１７のデータが必要なデータ、つまりガーベジコレクション対象でない有効なデータか否かの判断を行う（Ｓ１０１，第１判断ステップ）。以下、ガーベジコレクション対象でない有効なデータを「必要データ」と称する。尚、判断プログラム１０は、アドレステーブル１４に保持されているａアドレスデータ１５の状態フラグがマークされているか否かで、対象データが必要データであるか否かを判断する。ｄａｔａ＃ａ１７に関する状態フラグがマークされていない場合、対象データが必要データであると判断され（Ｓ１０１、ＹＥＳ）、ＧＣプログラム６は、図４に示す通り、コピー管理プログラム７により、ｄａｔａ＃ａ１７をフラッシュメモリ５から読み出し、メインメモリ４上にｄａｔａ＃ａ’’１８としてコピーを作成し、メインメモリ４の所定の領域にａ’’アドレスデータ１９を書き込む（Ｓ１０２，第１複写ステップ）。ａ’’アドレスデータ１９の書き込み後、判断プログラム１０は、ｄａｔａ＃ａ１７を参照しているファイルがファイルシステム１１内にあるか判断を行う（Ｓ１０３，第２判断ステップ）。なお、図４に示されている排他機構２０に関しては後述にて説明する。

ｄａｔａ＃ａ１７を参照しているファイルがファイルシステム１１内にある場合（Ｓ１０３、ＹＥＳ）、図５に示す通り、排他指示プログラム８は、排他機構２０に対しファイル１２を排他するよう指示をする（Ｓ１０４，第１排他指示ステップ）。なお、排他機構２０は、上述した排他機構１０７の機能を有するプログラムである。ファイル１２の排他後、ＧＣプログラム６は、アクセス管理プログラム９により、ｄａｔａ＃ａ１７へのアクセス経路１３を解除し、メインメモリ４上に作成したａ’’アドレスデータ１９へのアクセス経路２１を作成する（Ｓ１０５，第１切替ステップ）。この時点でフラッシュメモリ５上のｄａｔａ＃ａ１７は不要なデータとなるので、ＧＣプログラム６はａアドレスデータ１５に状態フラグをマークし、排他指示プログラム８の排他機構２０への排他解除指示により、ファイル１２への排他を解除する（Ｓ１０６，第１排他解除指示ステップ，第１フラグ設置ステップ）。なお、ａアドレスデータ１５への状態フラグのマークは、排他解除後に行ってもよい。

ファイル１２への排他の解除後、ＧＣプログラム６は、図６に示す通り、コピー管理プログラム７により、ｄａｔａ＃ａ’’１８をフラッシュメモリ５上の新しいブロック１６Ｂへｄａｔａ＃ａ’２２としてコピーを行い、ｄａｔａ＃ａ’２２の位置情報であるａ’アドレスデータ２３をアドレステーブル１４へ書き込む（Ｓ１０７，第２複写ステップ）。なお、ここではブロック１６Ｂへコピーを行ったが、空きの領域のあるブロックであれば何処へコピーしてもよい。書き込み後、判断プログラム１０は、ｄａｔａ＃ａ’’１８が必要であるか判断を行う（Ｓ１０８，第３判断ステップ）。すなわち、状態フラグのマークがなされているかの判断を行う。

ｄａｔａ＃ａ’’１８が必要データと判断した場合、ＧＣプログラム６は、図７に示す通り、排他指示プログラム８による排他機構１９への指示により、再びファイル１２をロックし（Ｓ１０９，第２排他指示ステップ）、アクセス管理プログラム９により、ａ’’アドレスデータ１９へのアクセス経路２１を解除し、ａ’アドレスデータ２３へのアクセス経路２４を作成する（Ｓ１１０，第２切替ステップ）。アクセス経路２４作成後、ＧＣプログラム６は、図８に示す通り、排他指示プログラム８による排他機構２０への指示により、ファイル１２の排他を解除し（Ｓ１１１，第２排他解除ステップ）、ｄａｔａ＃ａ’’１８及びａ’’アドレスデータ１９は不要なので、これらを削除する（Ｓ１１２，第１削除ステップ）。なお、この削除は、ｄａｔａ＃ａ’’１８及びａ’’アドレスデータ１９が、フラッシュメモリ５上でなく、メインメモリ４上に存在する為、ブロック単位を意識することなく実行することができる。また、ｄａｔａ＃ａ’’１８及びａ’’アドレスデータ１９の削除は、ファイル１２の排他の解除（Ｓ１１１）以前、すなわち、アクセス経路２４作成後に行ってもよい。以上で必要データの移動は完了する。

また、図３におけるステップＳ１０１において、ｄａｔａ＃ａ１７のデータが不要データであった場合（Ｓ１０１、ＮＯ）、すなわち、ａアドレスデータ１５に状態フラグのマークなされていた場合、ｄａｔａ＃ａ１７はガーベジコレクションでの消去対象のデータであるため、移動させる必要がない。よって、移動の対象とならない為、ＧＣプログラム６は処理を終了する。

図３のフローでは、アドレスを切り替えるときのみにファイルに対する排他を行っている。よってデータのブロック間の移動処理が実行されている全期間中に排他がなされている従来のものよりも、排他を行う期間を短縮できる。

なお、本実施の形態においては、データ整理処理について詳細を説明したが、ＧＣプログラム６は、上述したデータ整理を繰り返すことで、フラッシュメモリ５上の必要データを整理し、不要データのみとなったブロック１６内のデータを消去できる。

また、排他を必要時にのみ行っているため、ＧＣプログラム６の処理中に、他プログラムがファイル１２のデータ内容、つまりフラッシュメモリ５上のデータを書き換える可能性がある。データ内容が書き換えられたまま、ＧＣプログラム６が処理を続けると、書き換えられる前の不要なデータをフラッシュメモリ５内に増加させることに繋がってしまう。かかる書き換えが行われるタイミングは、排他制御がされていない図３におけるステップＳ１０２〜Ｓ１０３の間とステップＳ１０７〜Ｓ１０８の間である。下記に、ステップＳ１０２〜Ｓ１０３の間とステップＳ１０７〜Ｓ１０８の間において、必要データが書き換えられた場合におけるＧＣプログラム６の処理を説明する。

まず、図３におけるステップＳ１０３において、ｄａｔａ＃ａ１７のデータを参照しているファイルが無かった場合、つまりａアドレスデータ１５に状態フラグがマークされていた場合は、ＧＣプログラム６がｄａｔａ＃ａ１７を読み出している最中に、他プログラムにより、ファイル１２が変更され、ｄａｔａ＃ａ１７が不要とされた状態である。

図９は、本実施の形態に係る、追記型ファイルシステムにおける他プログラムにより、ファイルが書き換えられ、必要データが不要データとなった場合（Ｓ１０３、ＮＯ）のＧＣプログラムの動作後の概念図である。図９に示される他プログラム２５は、ｄａｔａ＃ａ１７をｄａｔａ＃ｉ２７へ変更するものであり、ｉアドレスデータ２６は、ｄａｔａ＃ｉ２７のフラッシュメモリ５における位置情報である。図９に示すように、ＧＣプログラム６が、ｄａｔａ＃ａ’’１８のコピー中に、他プログラム２５の指示により、ファイルシステム１１は、ｄａｔａ＃ａ１７をｄａｔａ＃ｉ２７へ書き換え、ａアドレスデータ１５に状態フラグをマークし、ｉアドレスデータ２６へアクセス経路を書き換える。その後、ＧＣプログラム６が、ｄａｔａ＃ａ’’１８のコピーを終え、判断プログラム１０により、メインメモリ４上のａアドレスデータ１５の状態フラグを確認する。ここでａアドレスデータ１５に状態フラグがマークされているため（Ｓ１０３、ＮＯ）、ＧＣプログラム６は、ｄａｔａ＃ａ’’１８及びａ’’アドレスデータ１９を削除し（Ｓ１１２，第２削除ステップ）、処理を終了する。

また、図３におけるステップＳ１０８において、ｄａｔａ＃ａ’’１７のデータが不要データであった場合、つまりａ’’アドレスデータ１９に状態フラグがマークされていた場合は、ＧＣプログラム６がｄａｔａ＃ａ’２２の書き込みをしている最中に、他プログラムにより、ファイル１１が変更され、ｄａｔａ＃ａ’’１７が不要とされた状態である。

図１０は、本実施の形態に係る、追記型ファイルシステムにおける他プログラムにより、ファイルが書き換えられ、必要データが不要データとなった場合（Ｓ１０８、ＮＯ）のＧＣプログラムの動作後の概念図である。図１０に示すように、ＧＣプログラム６が、ｄａｔａ＃ａ’２２のコピー中に、他プログラム２５の指示により、ファイルシステム１１は、ｄａｔａ＃ａ’’１８をｄａｔａ＃ｉ２７へ書き換え、ａ’’アドレスデータ１９に状態フラグをマークし、ｉアドレスデータ２６へアクセス経路を書き換える。その後、ＧＣプログラム６が、ｄａｔａ＃ａ’２２のコピーを終え、判断プログラム１０は、メインメモリ４上のａ’’アドレスデータ１９の状態フラグを確認する。ここでａ’’アドレスデータ１９に状態フラグがマークされているため（Ｓ１０８、ＮＯ）、ＧＣプログラム６は、ａ’アドレスデータ２３に状態フラグをマークし（Ｓ１１３，第２フラグ設置ステップ）、ｄａｔａ＃ａ’’１８及びａ’’アドレスデータ１９を削除し（Ｓ１１２，第３削除ステップ）、処理を終了する。

上述した本実施の形態に係るＧＣプログラム動作の一例において、従来技術との動作の比較を下記に説明する。

図１１は、本実施の形態に係るＧＣプログラム処理と、従来技術のＧＣプログラム処理の比較図である。なお、図に向かって左が従来のＧＣプログラム処理を表し、右側が本実施の形態に係るＧＣプログラム処理を表す。図１１に示される２８は、ファイル１２の排他処理、２９は、ｄａｔａ＃ａ１７の読み出し処理、３０は、ｄａｔａ＃ａ１７のコピーであるｄａｔａ＃ａ’２２の作成処理、３１は、ｄａｔａ＃ａ’２２のアクセス経路作成処理、３２は、排他解除処理を表す。また、３３は、ｄａｔａ＃ａ１７のコピーであるｄａｔａ＃ａ’’１８の作成処理（Ｓ１０２）、３４は、ｄａｔａ＃ａ’’１８のアクセス経路作成処理（Ｓ１０５）、３５は、ｄａｔａ＃ａ’’１８のコピーであるｄａｔａ＃ａ’２２の作成処理（Ｓ１０７）を表す。また、図１１におけるハッチング部は、フラッシュメモリ５へのＧＣプログラム６のアクセスを表し、矢印部はファイル１２の排他区間を表す。

図１１に示すように、従来技術では、排他する区間に処理時間のかかるフラッシュメモリ５からのデータの読み出し、および書込みといったアクセス動作が含まれているが、本実施の形態では、排他区間にフラッシュメモリへのアクセスが含まれておらず、ＧＣプログラム６による排他時間が低減することができる。

また、本実施の形態における、ＧＣシステムの構成について詳細を下記に説明する。

図１２は、本実施の形態に係る、ＧＣシステムの構成の一例を示すブロック図である。図１２に示される通り、ＧＣシステム３６は、起動ＲＯＭ８０内に、ＧＣプログラム６を排除し、ＧＣ処理部３７（第１フラグ設定部，第２フラグ設定部，削除部）を新たに備えるものである。ＧＣ処理部３７は、コピー管理部３８（第１複写部，第２複写部）と、排他指示部３９（第１排他指示部，第１排他解除指示部，第２排他指示部，第２排他解除指示部）と、アドレス管理部４０（第１切替部，第２切替部）と、判断部４１（第１判断部，第２判断部）とを備える。なお、ＧＣプログラム６と、ＣＰＵ３、メインメモリ４、フラッシュメモリ５、起動ＲＯＭ８０等のハードウェア資源とが協働することで図１２に示されているＧＣ処理部３７が実現される。また、コピー管理プログラム７と上述のハードウェア資源とが協働することで、コピー管理部３８が実現され、排他指示プログラム８と上述のハードウェア資源とが協働することで、排他指示部３９が実現される。また、アドレス管理プログラムと上述のハードウェア資源とが協働することで、図１２に示されているアドレス管理部４０が実現され、判断プログラム１０と上述のハードウェア資源とが協働することで、判断部４１が実現される。

このような構成によれば、上述したＧＣプログラム６のデータ整理処理の一連の作業を行うシステムを提供することができる。

本実施の形態によれば、コピー管理プログラム７とアクセス管理プログラム９により、メインメモリ４上へ必要データであるｄａｔａ＃ａ１７のバックアップを作成することでＧＣプログラム６の実行中でも、他プログラムのファイル１２へのアクセスが可能となる。また、排他指示プログラム８がアクセス経路の切替え時のみ排他を行うことにより、ファイル１２が排他される区間の外側へ、処理時間のかかるフラッシュメモリ５へのアクセスを出すことができ、ファイル１２の排他時間を最小限に抑えることができる。また、対象データのバックアップ単位は、１データ分である為、メインメモリ４の容量が小さいシステムでも実行が可能である。

本発明は、その要旨または主要な特徴から逸脱することなく、他の様々な形で実施することができる。そのため、前述の実施の形態は、あらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には、何ら拘束されない。更に、特許請求の範囲の均等範囲に属する全ての変形、様々な改良、代替および改質は、全て本発明の範囲内のものである。

更に、上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、ＧＣシステムを構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。

本発明によれば、データを移動する際の排他時間を低減するガーベジコレクション装置、ガーベジコレクションプログラム、及びガーベジコレクション方法、ならびにガーベジコレクションシステムを提供することができる。

Claims (10)

1. ブロック単位でのみデータ消去が可能な第１記憶装置のうちの、有効なデータと無効なデータとが混在する第１ブロックから、有効なデータを前記第１記憶装置とは別の記憶装置である第２記憶装置へコピーする第１複写ステップと、
   前記第１複写ステップでコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第１排他指示ステップと、
   前記第１排他指示ステップに基づく排他制御が行われた後、前記第１複写ステップにてコピーされるコピー元の有効なデータから、前記第１複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第１切替ステップと、
   前記第１切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第１排他解除指示ステップと、
   前記第１複写ステップにてコピーされたコピー先の有効なデータを、前記第２記憶装置から前記第１記憶装置のブロックであって前記第１ブロックとは別のブロックである第２ブロックに有効なデータをまとめるようコピーする第２複写ステップと、
   前記第２複写ステップにてコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第２排他指示ステップと、
   前記第２排他指示ステップに基づく排他が行われた後、前記第２複写ステップにてコピーされるコピー元の有効なデータから、前記第２複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第２切替ステップと、
   前記第２切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第２排他解除指示ステップと、
   をコンピュータに実行させるガーベジコレクションプログラム。
2. 請求項１に記載のガーベジコレクションプログラムにおいて、
   前記第１切替えステップにより、コピー元の有効なデータから、コピー先の有効なデータへアクセス経路を切り替えた後、コピー元の有効なデータを無効なデータとなるよう所定のフラグを設置する第１フラグ設置ステップを更にコンピュータに実行させるガーベジコレクションプログラム。
3. 請求項１に記載のガーベジコレクションプログラムにおいて、
   前記第２排他解除指示ステップにより前記排他機構が排他制御の解除を行った後、前記第１複写ステップによりコピーされたコピー先の有効なデータを削除する第１削除ステップを更にコンピュータに実行させるガーベジコレクションプログラム。
4. 請求項１に記載のガーベジコレクションプログラムにおいて、
   前記第１複写ステップにより、前記第１ブロックから前記有効なデータを前記第２記憶装置へコピーする前に、対象データが有効なデータであるか、無効なデータであるか判断を行う第１判断ステップを更にコンピュータに実行させるガーベジコレクションプログラム。
5. 請求項１に記載のガーベジコレクションプログラムにおいて、
   前記第１複写ステップにより、前記第１ブロックから前記有効なデータを前記第２記憶装置へコピーした後、前記第１ブロックのコピー元である有効なデータが有効なデータのままであるか、無効なデータとなったかを判断する第２判断ステップを更にコンピュータに実行させるガーベジコレクションプログラム。
6. 請求項５に記載のガーベジコレクションプログラムにおいて、
   前記第２判断ステップにより、前記有効なデータが有効なデータのままであると判断された場合、前記第１排他指示ステップをコンピュータに実行させるガーベジコレクションプログラム。
7. 請求項１に記載のガーベジコレクションプログラムにおいて、
   前記第２複写ステップにより、前記第２記憶装置の有効なデータを、前記第２ブロックにコピーした後、前記第２記憶装置のコピー元の有効なデータが有効なデータのままであるか、無効なデータとなったかを判断する第３判断ステップを更にコンピュータに実行させるガーベジコレクションプログラム。
8. 請求項７に記載のガーベジコレクションプログラムにおいて、
   前記第３判断ステップにより、前記第２記憶装置のコピー元の有効なデータが有効なデータのままであると判断された場合、前記第２排他指示ステップをコンピュータに実行させるガーベジコレクションプログラム。
9. ブロック単位でのみデータ消去が可能な第１記憶装置のうちの、有効なデータと無効なデータとが混在する第１ブロックから、有効なデータを前記第１記憶装置とは別の記憶装置である第２記憶装置へコピーする第１複写ステップと、
   前記第１複写ステップでコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第１排他指示ステップと、
   前記第１排他指示ステップに基づく排他が行われた後、前記第１複写ステップにてコピーされるコピー元の有効なデータから、前記第１複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第１切替ステップと、
   前記第１切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第１排他解除指示ステップと、
   前記第１複写ステップにてコピーされたコピー先の有効なデータを、前記第２記憶装置から前記第１記憶装置のブロックであって前記第１ブロックとは別のブロックである第２ブロックに有効なデータをまとめるようコピーする第２複写ステップと、
   前記第２複写ステップにてコピーされるコピー元の有効なデータへのアクセスを排他制御するよう排他機構へ指示する第２排他指示ステップと、
   前記第２排他指示ステップに基づく排他が行われた後、前記第２複写ステップにてコピーされるコピー元の有効なデータから、前記第２複写ステップにてコピーされたコピー先の有効なデータへアクセス経路を切り替える第２切替ステップと、
   前記第２切替ステップによるアクセス経路の切替後、前記排他機構へ排他制御を解除するよう指示する第２排他解除指示ステップと、
   を備えるガーベジコレクション方法。
10. 請求項９に記載のガーベジコレクション方法において、
    前記第１切替えステップにより、コピー元の有効なデータから、コピー先の有効なデータへアクセス経路を切り替えた後、コピー元の有効なデータを無効なデータとなるよう所定のフラグを設置する第１フラグ設置ステップを更に備えるガーベジコレクション方法。

Images