(57)【特許請求の範囲】
【請求項１】
データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリから所定のデータを読出す方法において、
(a)  前記ログブロックを管理するためのデータ構造のログポインタテーブルに要請されたページの論理アドレスのうちブロックアドレス部分が記録されたエントリーを検索する段階と、
(b)  検索されたエントリーに前記要請されたページの論理アドレスの記録有無を確認する段階と、
(c)  検索されたエントリーに記録された対応ログブロックの物理アドレスと、検索された論理アドレスの前記検索されたエントリーでの記録位置を参照して前記ログブロックの該当ページに接近する段階とを含むことを特徴とするフラッシュメモリ読出し方法。
【請求項２】
前記(c)段階は、
前記ログブロックの該当ページへの接近に際して前記検索された論理アドレスの前記検索されたエントリーでの記録位置と同じ位置のページに接近することを特徴とする請求項１に記載のフラッシュメモリ読出し方法。
【請求項３】
データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、
(a)  第１データブロックのページと前記第１データブロックに対応する第１ログブロックのページの配列順序が同一で、一対一対応する場合、前記第１ログブロックを第２データブロックに遷移させる段階と、
(b)  アドレス変換情報を更新する段階とを含み、
前記(a)段階の前に、
(a０)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、データを復旧するための復旧情報を記録する段階をさらに含み、
(c)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、前記復旧情報に基づいてデータを復元する段階をさらに含み、
前記復旧情報は、ログブロックまたはデータブロックに割当てられるための領域である自由ブロックのリスト、ログブロックのリスト、前記ログブロックを管理するためのデータ構造のログポインタテーブルを含み、
前記ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが構成されており、各エントリーには対応データブロックの論理アドレスと該当ログブロックの物理アドレスとがマッピングされており、該当ログブロック内の各ページの物理的配列順序によって該当データブロックの要請されたページの論理アドレスが記録されていることを特徴とするフラッシュメモリの管理方法。
【請求項４】
前記ログポインタテーブルは前記ログブロックが記録されたログブロック領域をスキャンして必要な情報を得て構成されることを特徴とする請求項３に記載のフラッシュメモリの管理方法。
【請求項５】
データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、
(a)  第１ログブロックに存在するページが全て一回ずつのみ書込み要請された場合、前記第１ログブロックの自由ページに対応する第１データブロックの該当ページをコピーして第２データブロックを生成する段階と、
(b)  アドレス変換情報を更新する段階とを含み、
前記(a)段階以前に、
(a０)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、データを復旧するための復旧情報を記録する段階をさらに含み、
(c)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、前記復旧情報に基づいてデータを復元する段階をさらに含み、
前記復旧情報は、ログブロックまたはデータブロックに割当てられるための領域である自由ブロックのリスト、ログブロックのリスト、前記ログブロックを管理するためのデータ構造のログポインタテーブルを含み、
前記ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが構成されており、各エントリーには対応データブロックの論理アドレスと該当ログブロックの物理アドレスがマッピングされており、該当ログブロック内の各ページの物理的配列順序によって該当データブロックの要請されたページの論理アドレスが記録されていることを特徴とするフラッシュメモリの管理方法。
【請求項６】
前記ログポインタテーブルは前記ログブロックが記録されたログブロック領域をスキャンして必要な情報を得て構成されることを特徴とする請求項５に記載のフラッシュメモリの管理方法。
【請求項７】
データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、
(a)  データが記録されていない自由ブロックに第１ログブロックに存在する最新ページをコピーし、残りの自由ページに対応する第１データブロックの該当ページをコピーして第２データブロックを生成する段階と、
(b)  アドレス変換情報を更新する段階とを含み、
前記(a)段階以前に、
(a０)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、データを復旧するための復旧情報を記録する段階をさらに含み、
(c)  前記(a)段階または(b)段階の実行中にシステムが中断された場合に備えて、前記復旧情報に基づいてデータを復元する段階をさらに含み、
前記復旧情報は、ログブロックまたはデータブロックに割当てられるための領域である自由ブロックのリスト、ログブロックのリスト、前記ログブロックを管理するためのデータ構造のログポインタテーブルを含み、
前記ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが構成されており、各エントリーには対応データブロックの論理アドレスと該当ログブロックの物理アドレスがマッピングされており、該当ログブロック内の各ページの物理的配列順序によって該当データブロックの要請されたページの論理アドレスが記録されていることを特徴とするフラッシュメモリの管理方法。
【請求項８】
前記ログポインタテーブルは前記ログブロックが記録されたログブロック領域をスキャンして必要な情報を得て構成されることを特徴とする請求項７に記載のフラッシュメモリの管理方法。
【請求項９】
データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、
(a)  フラッシュメモリの所定領域を割当て、割当てられた領域に復旧情報として前記データブロック及び前記ログブロックのリスト、及び前記ログブロックを管理するためのデータ構造を記録する段階と、
(b)  システムが中断される場合、前記復旧情報に基づいて現在フラッシュメモリに記録された状態を点検してエラーの発生有無を確認する段階と、
(c)  エラーが発生した場合、前記復旧情報に基づいてデータを復元する段階とを含み、
前記復旧情報は自由ブロックのリストをさらに含み、
前記ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが構成されており、各エントリーには対応データブロックの論理アドレスと該当ログブロックの物理アドレスとがマッピングされており、該当ログブロック内の各ページの物理的配列順序によって該当データブロックの要請されたページの論理アドレスが記録されていることを特徴とするフラッシュメモリの管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はフラッシュメモリに係り、特にフラッシュメモリに基づいたシステムにおいてフラッシュメモリの管理方法に関する。
【０００２】
【従来の技術】
フラッシュメモリは電気的にデータを消去/書込み可能な不揮発性記憶素子である。マグネチックディスクメモリに基づいた貯蔵装置に比べてフラッシュメモリに基づいた貯蔵装置は省エネルギー性に優れ、小型であるためにマグネチックディスクメモリの代案として研究及び開発が活発に進められている。特に、フラッシュメモリはデジタルカメラ、モビルホン、PDA(Personal Digital Assistant)のようなモビルコンピューティング機器のための貯蔵装置として脚光を浴びると予想される。
【０００３】
しかし、フラッシュメモリはデータの再書込みが自由なマグネチックディスクメモリとは異なってデータの再書込みが不可能である。フラッシュメモリにデータを再書込むためにはまずデータを消去しなければならない。すなわち、メモリセルを書込み可能な初期状態に復帰させねばならない。このような作業を消去という。消去は一般に書込みに比べて非常に長時間がかかる。また、消去は書込みよりさらに大きなブロック単位で行われるために書込みが要請されない部分までも共に消去される結果となりうる。誤って消去された部分は再書込みを通じて復元しなければならないために、最悪の場合にデータ一つの書込み要請が一つの消去と消去された単位だけの書込みを必要とする。これにより消去と書込みの実行単位の不一致によって書込みの実行性能は読出しのそれに比べて顕著に劣り、かつ機械動作による必然的な遅延を伴うマグネチックディスク基盤の貯蔵装置のそれより低い。したがって、フラッシュメモリに基づいた貯蔵装置の設計において書込みの性能改善は核心技術に該当する。
【０００４】
米国特許No.５,３８８,０８３は要請された書込みが、先行すべきである消去によって遅延されることを防止するために消去を行わず、空間に書込む代わりに使用者が要請した論理アドレスをフラッシュメモリ上の物理アドレスに変換するカム(CAM)構造を提案している。しかし、カム構造を具現するためには高価な回路を必要とする。米国特許No.５,４８５,５９５は書込みが要請された場合に消去を行わず、空間に書込む代わりに各ページの付加領域に論理アドレスを記入し、付加領域に記録された論理アドレスを順次に検索して読出しを行う方式を提案している。しかし、このようなアドレス変換メカニズムはNANDタイプのフラッシュメモリのように読出しの単位が大きな場合には分散貯蔵されたアドレス変換情報を読出すのに長時間がかかって実効性が低い問題点がある。
【０００５】
米国特許No.５,８４５,３１３は貯蔵装置を初期化する時、フラッシュメモリに貯蔵された論理アドレスをスキャニングして別のRAMに直接アドレス変換を行える線形的なアドレス変換テーブルを構築する方法を提示している。しかし、アドレス変換テーブルを貯蔵するためには大容量RAMが必要である。例えば、全体貯蔵容量が３２MBで、ページの大きさが５１２Bのフラッシュメモリ基盤貯蔵装置のアドレス変換テーブルを貯蔵するためには６５,５３６のページ当り２Bが必要なので総１２８KBのRAMが必要となる。このような要求量はモビル機器など資源の貴重な小規模システムにおいては過度に大きい。
【０００６】
米国特許No.５,４０４,４８５は書込みのために新たなブロック(交替ブロック)を割当て、割当てられたブロックに書込みを行う方式を提案している。しかし、これによれば書込みのために新たなブロックが割当て続けられるので同一なページが記録された相異なるバージョンの複数個のブロックが存在することになる。すなわち、暗黙に全てのブロック毎に少なくとも１つの交替ブロックが存在することを要求してフラッシュメモリの容量が相当減ることになる。また、新たなブロックに使われるページは常に以前のブロックのそれと同じ位置に書込まれるべきなので、特定ページに対してのみ頻繁な更新が行われ、残りページは更新がほとんど行われない場合、特定ページの内容のみが相異なるだけで残りページの内容は同一な交替ブロックが複数個存在することになってフラッシュメモリの貯蔵空間の浪費が激しくなる問題点がある。これに、モビル機器などの小規模システムに適さない。
【０００７】
【発明が解決しようとする課題】
したがって、本発明の目的は、フラッシュメモリの性能を改善させうるフラッシュメモリ基盤システム及びその管理方法を提供することである。
本発明の他の目的は、電源遮断などの非常時に一貫性あるデータの復元が可能なフラッシュメモリ基盤システム及びその管理方法を提供することである。
本発明のさらに他の目的は、FAT(File Allocation Table)に基づいたDOSファイルシステムのように特定ページに対するデータ更新が頻繁な環境でもシステムの性能が低下しないフラッシュメモリ基盤システム及びその管理方法を提供することである。
【０００８】
【課題を解決するための手段】
前記目的は、フラッシュメモリに所定データを書込む方法において、(a)  書込みが行われて所定のデータが記録されているページに書込みを要請される段階と、(b)  前記ページが含まれるデータブロックに対応するように備えられたログブロックに書込みを行う段階と、(c)  前記ページに書込みを再び要請される段階と、(d)  前記ログブロック内の空いている自由ページに書込みを行う段階とを含むことを特徴とするフラッシュメモリ書込み方法によって達成される。
【０００９】
前記(b)段階は、(b１１)  空いている自由ページに書込みを行う段階を含んだり、(b２１)  前記ログブロックを割当てる段階と、(b２２)  前記書込みが要請されたページの前記データブロックでの位置と同じ位置の自由ページに書込みを行う段階を含むことが望ましい。
また、フラッシュメモリに所定データを書込む方法において、(a)  所定ページに書込みを要請される段階と、(b)  前記ページが含まれた第１データブロックに対応する第１-１ログブロックを割当てる段階と、(c)  前記第１-１ログブロック内の空いている自由ページに書込みを行う段階と、(d)  前記ページに書込みを再び要請される段階と、(e)  前記第１-１ログブロック内の空いている自由ページに書込みを行う段階とを含むことを特徴とするフラッシュメモリ書込み方法によっても達成される。
【００１０】
前記(b)段階は、(b１)  第２データブロック及びこれに対応する第２ログブロックに基づいて第３データブロックを生成するブロック併合を行う段階と、(b２)  前記第２データブロックに対する消去を行い得られた自由ブロックを前記第１ログブロックに割当てる段階とを含むことが望ましい。前記(b１)段階は、前記第１-１ログブロックを割当てるための自由ブロックが存在しない時に行われたり、前記第１データブロックに対応する既存のログブロックが全て使用中である場合に行われることが望ましい。
【００１１】
また、前記(b１)段階は、(b１１)前記第２ログブロックのページと前記第２データブロックのページの配列順序が同一で、一対一対応する場合、前記第２ログブロックを前記第３データブロックに遷移させる交換併合を行う段階を含んだり、(b１２)  前記第２ログブロックに存在するページが全て一回ずつだけ書込み要請された場合、前記第２ログブロックの自由ページに前記第２データブロックの該当ページをコピーして前記第３データブロックを生成するコピー併合を行う段階を含んだり、(b１３)  データが記録されていない自由ブロックに前記第２ログブロックに存在する最新ページをコピーし、残りの自由ページに前記第２データブロックの該当ページをコピーして前記第３データブロックを生成する単純併合を行う段階とを含むことがさらに望ましい。
【００１２】
前記(e)段階は、(e１)  前記第１-１ログブロック内に自由ページが存在しない場合、新しい第１-２ログブロックを割当てる段階と、(e２)  前記第１-２ログブロック内の自由ページに書込みを行う段階を含み、前記(e１)段階は、(e１１)前記第１-１ログブロックのページと前記第１データブロックのページの配列順序が同一で、一対一対応する場合、前記第１-１ログブロックを第２データブロックに遷移させる交換併合を行う段階と、(e１２)  前記第１データブロックに対する消去を行い得られた自由ブロックを前記第１-２ログブロックに割当てる段階を含んだり、(e２１)  前記第１-１ログブロックに存在するページが全て一回ずつだけ書込み要請された場合、前記第１-１ログブロックの自由ページに前記第１データブロックの該当ページをコピーして第２データブロックを生成するコピー併合を行う段階と、(e２２)前記第１データブロックに対する消去を行い得られた自由ブロックを前記第１-２ログブロックに割当てる段階を含んだり、(e３１)  自由ブロックに前記第１-１ログブロックに存在する最新ページをコピーし、残りの自由ページに前記第１データブロックの該当ページをコピーして第２データブロックを生成する単純併合を行う段階と、(e３２)前記第１データブロックまたは前記第１-１ログブロックに対する消去を行い得られた自由ブロックを前記第１-２ログブロックに割当てる段階とを含むことが特に望ましい。
【００１３】
前記(e２)段階は、(e２１)書込みが要請されたページの前記データブロックでの位置と同じ位置の自由ページに書込みを行う段階を含むことが望ましい。
一方、本発明の他の分野によれば、前記目的はフラッシュメモリから所定データを読出す方法において、(a)ログポインタテーブルに要請されたページの論理アドレスのうちブロックアドレス部分が記録されたエントリーを検索する段階と、(b)検索されたエントリーに前記要請されたページの論理アドレスの記録有無を確認する段階と、(c)検索されたエントリーに記録された対応ログブロックの物理アドレスと、検索された論理アドレスの前記検索されたエントリーでの記録位置を参照して前記ログブロックの該当ページに接近する段階を含むことを特徴とするフラッシュメモリ読出し方法によっても達成される。
【００１４】
前記(c)段階は、前記ログブロックの該当ページへの接近に際して前記検索された論理アドレスの前記検索されたエントリーでの記録位置と同じ位置のページに接近することが望ましい。
一方、本発明の他の分野によれば、前記目的は、データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、(a)第１データブロックのページと前記第１データブロックに対応する第１ログブロックのページの配列順序が同一で、一対一対応する場合、前記第１ログブロックを第２データブロックに遷移させる段階と、(b)アドレス変換情報を更新する段階を含むことを特徴とするフラッシュメモリの管理方法によっても達成される。
【００１５】
また、データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、(a)第１ログブロックに存在するページが全て一回ずつだけ書込み要請された場合、前記第１ログブロックの自由ページに対応第１データブロックの該当ページをコピーして第２データブロックを生成する段階と、(b)アドレス変換情報を更新する段階を含むことを特徴とするフラッシュメモリの管理方法によっても達成される。
【００１６】
また、データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、(a)データが記録されていない自由ブロックに第１ログブロックに存在する最新ページをコピーし、残りの自由ページに対応第１データブロックの該当ページをコピーして第２データブロックを生成する段階と、(b)  アドレス変換情報を更新する段階とを含むことを特徴とするフラッシュメモリの管理方法によっても達成される。
【００１７】
前記(a)段階の前に(a０)  前記(a)段階または(b)段階の実行中にシステムが中断される場合、データを復旧するための復旧情報を記録する段階をさらに含むことが望ましい。
前記フラッシュメモリの管理方法は、(c)  前記(a)段階または(b)段階の実行中にシステムが中断される場合、前記復旧情報を参照してデータを復元する段階をさらに含むことが望ましい。
【００１８】
前記復旧情報は、前記自由ブロックのリスト、ログブロックのリスト、前記ログブロックを管理するためのデータ構造のログポインタテーブルを含み、前記ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが構成されており、各エントリーには対応データブロックの論理アドレスと該当ログブロックの物理アドレスとがマッピングされており、該当ログブロック内の各ページの物理的配列順序によって該当データブロックの要請されたページの論理アドレスが記録されている。
【００１９】
また、前記目的は、データブロック、及び前記データブロックを更新するためのデータを書込むためのログブロックを含むフラッシュメモリを管理する方法において、(a)フラッシュメモリの所定領域を割当て、割当てられた領域に復旧情報として前記データブロック及び前記ログブロックのリスト、及び前記ログブロックを管理するためのデータ構造を記録する段階と、(b)システムが中断される場合に前記復旧情報に基づいて現在のフラッシュメモリに記録された状態を点検してエラーの発生有無を確認する段階と、(c)エラーが発生した場合に前記復旧情報に基づいてデータを復元する段階をさらに含むことを特徴とするフラッシュメモリの管理方法によっても達成される。
【００２０】
【発明の実施の形態】
以下、添付した図面に基づいて本発明の望ましい実施形態を説明する。
図１は本発明の望ましい実施形態に係るフラッシュメモリ基盤システムのブロック図である。
図１を参照すれば、システムはフラッシュメモリ１、ROM２、RAM３及びプロセッサ４を具備する。通常、プロセッサ４はROM２に記録されているプログラムコードと結合してフラッシュメモリ１またはRAM２に対する一連の読出しまたは書込み命令を発する。フラッシュメモリ１には本発明のフラッシュメモリの管理方法による書込み/読出しが行われる。ROM２とRAM３にはプロセッサ４で行われる応用プログラムコードまたは関連データ構造が貯蔵される。
【００２１】
図２は本発明によってフラッシュメモリ１に備えられ、一般のデータが貯蔵されるためのブロックを説明するための参考図である。
図２を参照すれば、フラッシュメモリ１には複数個のデータブロックと少なくとも一部のデータブロックに対応するように備えられるログブロックが存在する。「データブロック」は一般のデータを貯蔵するブロックを示し、「ログブロック」はデータブロックの所定部分を修正しようとする場合に割当てられて修正内容を記録する用途として活用されるブロックを示す。したがって、ログブロックは唯一のデータブロックに対応して該当データブロックの修正されたページを貯蔵する。ログブロックに貯蔵されているページはデータブロックに貯蔵されている該当ページより優先的に参照される。このように優先的に参照されるページを本明細書では「有効ページ」という。さらに、物理的に有効なデータが記録されていたとしても有効ページによりその内容が無視されるページは論理的な意味で「無効ページ」と称する。
【００２２】
図３はログブロックとデータブロックとに対する読出しを説明するための参考図である。
図３を参照すれば、使用者から論理アドレスと共に所定ページに対する読出しが要請されるとプロセッサ４はRAM３に記録されているログポインタテーブルを参照して該当ログブロックの存否を確認し、存在する場合にそのログブロックに要請されたページが有効に貯蔵されているか否かを確認する。要請されたページが有効に貯蔵されていればログブロックの該当ページを読出し、そうでなければ該当データブロックに記録された該当ページを読出す。ログポインタテーブルは後述する。
【００２３】
図４は本発明の一実施形態に係るフラッシュメモリ１の領域分割を説明するための参考図である。図４を参照すれば、フラッシュメモリ１はマップ領域、ログブロック領域、データブロック領域、及び自由ブロック領域に分割しうる。マップ領域にはアドレス変換情報が貯蔵され、ログブロック領域はログブロックに割当てられるための領域であり、データブロック領域は一般のデータが記録される領域であり、自由ブロック領域はログブロックまたはデータブロックに割当てられるための領域である。ここで、各領域は論理的に分割された領域を意味する。したがって、物理的には混ぜられて不連続に存在しうる。特に、データブロック領域、ログブロック領域、及び自由ブロック領域がそうである。
【００２４】
図５は本発明の他の実施形態に係るフラッシュメモリ１の領域分割を説明するための参考図である。図５を参照すれば、フラッシュメモリ１はマップ領域、チェックポイント領域、ログブロック領域、データブロック領域、及び自由ブロック領域に分割しうる。本実施形態では図４の領域分割に比べてチェックポイント領域が新たに備えられている。チェックポイント領域にはデータ復旧のために必要な復旧情報が記録される。一方、図４の場合と同様に、マップ領域にはアドレス変換情報が貯蔵され、ログブロック領域はログブロックに割当てられるための領域であり、データブロック領域は一般のデータが記録される領域であり、自由ブロック領域はログブロックまたはデータブロックに割当てるための自由領域である。マップ領域に記録されるアドレス変換情報及びチェックポイント領域に記録される復旧情報についての詳細な説明は後述する。
【００２５】
「ログポインタテーブル」はログブロックの管理のためのデータ構造である。ログポインタテーブルには対応データブロックの論理アドレス、該当ログブロックの物理アドレス、及びログブロック内の各ページの物理的配列順序によって該当データブロックの更新されたページのオフセット値(要請されたページの論理アドレス)が記録される。ログポインタテーブルは本実施形態によってRAM３に構築されるべきなので、プロセッサ４がログブロック領域をスキャンして構成する。図６を参照すれば、ログポインタテーブルにはログブロックに対応する数だけのログポインタテーブルエントリーが配置されている。該当ページの論理アドレスと共に書込みまたは読出し命令が要請されるとプロセッサ４はログポインタテーブルを参照して該当エントリーの存否によってログブロックまたはデータブロックに接近することになる。
【００２６】
図７はログポインタテーブルエントリーの構造図である。
図７を参照すれば、ログポインタテーブルエントリーにはデータブロックの論理アドレスlog_blkと該当ログブロックの物理アドレスphy_blkが記録されている。また、データブロックのページの記録順に該当ログブロック内の対応ページの論理アドレスpage#０、page#１、‥、page#Nが記録されている。
【００２７】
例えば、１つのブロックに１６のページが存在する場合、論理アドレスが０２ＦＦ(１６進数)であれば、前の三桁０２Ｆはブロックアドレスを意味し、最後の一桁Ｆは該当ブロックに存在するページのオフセット値となる。したがって、ログポインタテーブルのlog_blkのうち０２Ｆの有無を検索して対応ログブロックの存否を確認しうる。対応ログブロックが存在すれば要請されたページの論理アドレス０２FF、またはオフセット値Fの記録有無を確認して該当ログブロック内の更新されたページの位置がわかる。例えば、もし、page#０がFならばログブロック内の最初の物理的ページに要請されたページが記録されている。
【００２８】
このように、要請された論理アドレス中の一部、すなわちブロックアドレス部分だけを使用してログブロックの存否を確認して該当ログブロックに接近することを「ブロックアドレッシング」と定義し、要請された論理アドレス全体(またはオフセット値)を使用して該当ログブロックのページにアクセスすることを「ページアドレッシング」と定義する。このように、本発明はブロックアドレッシングとページアドレッシングとを共に採用して同じページが何回も更新されても１つのログブロックにこれを全て記録しうる。
【００２９】
図８はログポインタテーブルとフラッシュメモリ１の参照関係図である。
図８に示されたように、log_blkを参照して該当データブロックに対するログブロックの存否を検索し、phy_blkを参照して対応ログブロックが記録された位置がわかる。また、ログポインタテーブルエントリーには本実施形態によって該当ログブロックの各ページの論理アドレスpage#０、page#１、‥、page#１５が記録されうる。本実施形態での各ブロックには１６のページが含まれる。
【００３０】
原則的に更新されたページはログブロックに記録されるに当たって該当データブロックの対応ページと同じ位置に記録される。実際に、ログブロックに更新されたページが最初に記録される場合にはデータブロックの該当ページと同じ位置に記録されうる。しかし、以後には必ずしもそうではない。すなわち、該当データブロックの所定ページが、残りのページが一回ずつ更新される前に再更新されるべき場合には該当ログブロックの残り空間に記録される。
【００３１】
図９は消去可能ブロックを説明するための参考図である。
データブロックのページが全て一回ずつのみ更新されればログブロックのページは図８に示されたように、該当データブロックの各ページに一対一に対応する。このような場合にはログブロックが該当データブロックのあらゆる内容を含んでいるので該当データブロックを消去してもデータの損失は生じない。このようにこれ以上有効なデータを有してない(完全にシャドーされた)データブロックは「消去可能ブロック」と言う。消去されたブロックは「自由ブロック」という。消去可能ブロックは何時でも消去可能で、自由ブロックは必要に応じてデータブロックまたはログブロックに割当てられる。
【００３２】
一方、本発明では「ブロック併合」が行われる。ブロック併合は原則的に書込むが反復されてログブロックに書込み可能なページが存在しなくなるとなされる。この場合、ブロック併合を通じてログブロックと該当データブロックとを合せて新たなデータブロックを生成し、既存のログブロックは消去して自由ブロックに作る。
【００３３】
特に、データブロックの全てのページが一回ずつのみ更新されてログブロックとデータブロックのページ配列が同一な場合に行われるブロック併合は「交換併合」と言う。
ログブロックのページと該当データブロックのページの配列が一致しない場合には「単純併合」が行われる。さらに、ログブロックが現在全て使用中であるために新たに要請された書込みを行うためにログブロックが再び割当てられるべき場合にも行われる。この場合には併合対象となるログブロックがまだ使われていない自由ページを有しうる。
【００３４】
もし、ログブロックに存在するページが一回ずつのみ更新された場合であれば、空ページをデータブロックの該当ページとして満たすことによってログブロックをデータブロックに遷移させ、このようなブロック併合を「コピー併合」という。つまり、ブロック併合は、交換併合、単純併合、及びコピー併合の３種がある。
交換併合は、図９のようにデータブロックの全てのページが一回ずつのみ更新されたログブロックをそのままデータブロックに遷移させることによって行われる。ブロックの遷移はデータブロックまたはログブロックに記録されたデータのコピーなしにアドレス変換情報のみを更新することによってなされる。すなわち、マップ領域に記録されたアドレス変換情報を更新して使用者が要請した論理アドレスに対して該当ログブロックがマッピングされるようにする。マップ領域にはブロックアドレッシングを可能にするために各ブロック毎のアドレス変換情報が記録されている。ここで、無効ページは前述したように有効ページによってその内容が無視されるページという意味で使われたものであり、実際の具現においては物理的に有効なページで有り得る。
【００３５】
単純併合により、図１０のように、新たな自由ブロックの同一な位置にデータブロックの有効ページ及び該当ログブロックの有効ページを記録して新たなデータブロックが生成される。これに既存のデータブロックとログブロックとは消去可能ブロックとなる。
コピー併合は、図１１に示されたように、既存のデータブロックに記録された有効ページをログブロックの自由ページにコピーすることによってなされる。既存のデータブロックは消去可能ブロックに遷移される。ブロック併合における無効ページとは、前述したように最初に参照されないページという意味で使われたものであり、実際の具現においては物理的に有効なページで有り得る。
【００３６】
図１２は本発明に係るブロック併合の実行におけるブロックの遷移関係を示す関係図である。
図１２を参照すれば、自由ブロックはログブロックまたはデータブロックに遷移される。ログブロックは交換併合またはコピー併合を通じてデータブロックに遷移されたり、単純併合を通じて消去可能ブロックに遷移される。データブロックは交換併合、単純併合及びコピー併合を通じて消去可能ブロックに遷移されうる。消去可能ブロックは消去されてから再び自由ブロックに遷移される。
【００３７】
ブロック併合を行うためにはフラッシュメモリ１に存在する自由ブロックと消去可能ブロックに対するリストを有しなければならない。自由ブロックと消去可能ブロックのリストはRAM３にログポインタテーブルと共に記録されるデータ構造であって、マップ領域またはチェックポイント領域に記録されうる。
自由ブロックのリスト、消去可能ブロックのリスト、及びログポインタテーブルはシステムが初期化される時、RAM３に復元されるべきである。チェックポイント領域はこれらの迅速で完全な復旧のために必要な復旧情報が記録されるために本発明の一実施形態によって割当てられた領域である。チェックポイント領域が設定される場合、ここには復旧情報として前述した自由ブロックのリスト、消去可能ブロックのリスト、及びログブロックのリストが貯蔵される。特に、チェックポイント領域にはブロック併合の実行中システムの暴走や突然の電源遮断等で情報が損傷することを防止するために、ブロック併合を行う前に何れかのブロック併合を行い、その結果何れのブロックが何れのブロックに遷移されるかを記述するプランログが貯蔵される。プランログには実行しようとするブロック併合の種類、自由ブロックからデータブロックに遷移されるブロック、自由ブロックからログブロックに遷移されるブロック、データブロックから自由ブロックに遷移されるブロック、ログブロックから自由ブロックに遷移されるブロックの物理的なアドレスが記録される。チェックポイント領域にはアドレス変換情報の構築のために必要な情報(例えば、アドレス変換情報が貯蔵された位置)も記録される。チェックポイント領域自体の位置はフラッシュメモリ１の既定のブロックに記録される。
【００３８】
前記構成によって本発明の望ましい実施形態に係るフラッシュメモリの管理方法を説明すれば次の通りである。以下、本発明に係るフラッシュメモリの管理方法をシステム初期化に伴うデータ構造構築及び復旧方法、読出し方法及び書込み方法に分けて記述する。
まず、システム初期化に伴うフラッシュメモリの管理方法はデータ構造構築及び復旧方法を意味する。すなわち、書込み及び読出しに必要なデータ構造(自由ブロックのリスト、消去可能ブロックのリスト、ログブロックのリスト及びログポインタテーブル)及びアドレス変換情報を構築し、該構築された情報の一貫性(integrity)検査を行って復旧作業が必要な場合、復旧情報に基づいて復旧作業を行うことを意味する。図１のシステムが初期化されるとプロセッサ４はRAM３にログポインタテーブル、自由ブロックのリスト、消去可能ブロックのリスト、及びログブロックのリストを構築せねばならない。このためにプロセッサ４はフラッシュメモリ１のチェックポイント領域の最近に記録されたページから復旧情報を読取る。復旧情報が順次に記録される場合にはチェックポイント領域で最初に発見される自由ページ(空ページ)の直前に位置したページに最新の復旧情報が記録されるからである。ただし、前述した最近に記録されたページの識別が可能なかぎり復旧情報の記録順序は必要に応じて変更されうる。
【００３９】
ログポインタテーブルは復旧情報に指定されたログブロックの全てのページをスキャニングしてページ毎に付加されている領域に貯蔵された論理アドレスを読出すことによって構築されうる。マップ領域でもアドレス変換情報は順次に記録されるので最後に記録されたページ(最初の自由ページの直前に位置したページ)を最終変更されたものと見なしてこれに基づいてアドレス変換情報を構築しうる。自由ブロックリストと消去可能ブロックリストも復旧情報に基づいてそのまま復旧が可能である。
【００４０】
次いで、プランログを参照して構築した情報(自由ブロックのリスト、消去可能ブロックのリスト、ログブロックのリスト及びログポインタテーブル)を検証する。換言すれば、ブロック併合の実行中、システム動作が中断された場合などが生じて構築した情報と実際状況とが合うか否かを検査すべきである。具体的に、システム動作が中断される場合は、第１、チェックポイント領域への復旧情報の書込み中、第２、ブロック併合の実行中、第３、マップ領域へのアドレス変換情報の更新中、第４、消去中、の４つに分類でき、それぞれの場合に構築された情報と実際状況とが合うか否かを検査し、合わない場合に復旧する方法は次の通りである。
【００４１】
１．チェックポイント領域への復旧情報の書込み中にシステム動作が中断された場合:チェックポイント領域の最初の自由ページを探し、このページが実際の自由ページか否かをデータを読出して確認する。もし、自由ページが空いていないとチェックポイント領域への復旧情報の書込み中にシステムの動作が中断されたと判断しうる。この場合、実際データが書込みの実行前であるために別の復旧手続きを踏む必要がなく、ただ最終的に記録された復旧情報を無視する。
【００４２】
２．ブロック併合の実行中にシステム動作が中断された場合:プランログにデータブロックに遷移されるものと記載されたブロックの全てのページに正しくデータが記録されているか(有効か)否かを検査する。もし、１つのページでも有効でなければブロック併合途中にシステム動作が中断されたと判断しうる。この場合にはブロック併合を再実行することによってデータを正しく復旧しうる。
【００４３】
３．アドレス変換情報の更新中にシステム動作が中断された場合:プランログにデータブロックに遷移されるものと記録されたブロックから論理アドレスを読取ってマップ領域に記録された情報と一致するか否かを確認する。一致しなければアドレス変換情報の更新中にシステム動作が中断されたものと見なせる。この場合、データブロックから得た論理アドレスと該当物理アドレスとに基づいてアドレス変換情報を修正することによって復元しうる。
【００４４】
４．消去中にシステム動作が中断された場合:プランログに自由ブロックに遷移されるものと記録されたブロックが実際の自由ブロックなのか否かを検査する。自由ブロックでなければ(ページが全て空いていないならば)空いていないブロックに対して消去を再実行する。
システム初期化に伴うフラッシュメモリの管理方法を通じて前述したように必要なデータ構造を構築し、一貫性検査まで完了すると読出し及び書込みを行える。
【００４５】
図１３は本発明に係る読出し方法を説明するためのフローチャートである。
理解のために読出し方法を説明すれば、プロセッサ４はログブロックから要請されたページの存否を検索し、検索されたログブロックから該当ページを読取る。
さらに具体的に、まずプロセッサ４は要請されたページの論理アドレスに基づいてログポインタテーブルを順次に検索して見合うエントリーの有無を確認する(１３０１段階)。要請されたページの論理アドレスはブロックアドレッシング部分とページアドレッシング部分とで結合されているためにブロックアドレッシング部分を参照してエントリーを検索する。見合うエントリーが発見されると(１３０２段階)、発見されたエントリーを検索して要請されたページの存否を確認する(１３０３段階)
【００４６】
該当ページが発見されればこれを読出す(１３０５段階)。この際、同じページが２つ以上発見されれば同じオフセット値を有するものを除いて最後に発見されたのを最新のものと見なしてログブロックの該当ページを読出す。見合うエントリーが発見されないか(１３０２段階)、或いは対応ログブロックに該当ページが存在しない場合(１３０４段階)、要請された論理アドレスに基づいてデータブロック内の該当ページを読出す(１３０６段階)。
【００４７】
図１４は本発明に係る書込み方法を説明するためのフローチャートである。
理解のために書込み方法を説明すれば、まずプロセッサ４はログブロックから要請されたページの存否を検索し、ログブロックが存在する場合にログブロックに要請されたページと同じ位置のページが使用可能な状態なのか否かを検査する。使用可能ならば該当ページに書込みを行い、そうでない場合にはログブロックの使用可能な他のページに書込みを行い、ログブロックに使用可能なページが存在しなければログブロックを新たに割当てて同じ位置に書込みを行う。
【００４８】
より具体的に、プロセッサ４は要請されたページの論理アドレスに基づいてログポインタテーブルを検索する(１４０１段階)。エントリーが発見されれば(１４０２段階)、該当ログブロックが存在するということを意味するのでエントリーを検索して要請されたページと同じオフセット値を有するページが使用可能なのかを判断し(１４０３段階)、使用可能ならば該当ページに書込みを行う(１４０４段階)。ここで、使用可能なページとは、ログブロックの該当ページにまだ書込みが実行されない空ページ(自由ページ)をいう。自由ページの存否はエントリーを検索して該当ページが有効か否か(優先的に参照されているか、すなわちデータが記録されているか)と判断しうる。次いで、ログポインタテーブルの該当エントリーに書込みが行われたページの論理アドレスに対応する物理アドレスを記入する。この場合、使用者の書込み要請はフラッシュメモリに対する１つの書込みだけで完了される。
【００４９】
対応ログブロックは発見されたがオフセット値が同じページが既に使われたならば(１４０３段階)、ログブロック内に他の自由ページが割当てられるかを確認し(１４０６段階)、割当てられた自由ページに書込みを行う(１４０７段階)。２つ以上の自由ページが存在するならばログブロックの開始地点から順次に検索して最近のページを割当てられる。次いで、ログポインタテーブルの対応エントリーに要請されたページの論理アドレスに対応するように、割当てられたページの物理アドレスを記録する(１４０５段階)。
【００５０】
ログポインタテーブルを検索した結果、要請されたページに対する対応エントリーが発見されないと新たなログブロックが割当て可能か否かを確認する(１４０８段階)。新たなログブロックに割当てられる自由ブロックが残っていると、その中の１つを新たなログブロックに割当て(１４０８段階)、自由ブロックが残っていない場合、ブロック併合を通じて自由ブロックを生成した後、生成された自由ブロックを新たなログブロックに割当てる(１４０９段階)。割当てられたログブロックにおいて書込みが要請されたページと同じオフセット値を有するページに書込みを行う(１４１０段階)。次いで、ログポインタテーブルに対応エントリーを生成する(１４０５段階)。
【００５１】
図１５は図１４のブロック併合を説明するためのフローチャートである。
ブロック併合は前述したようにログブロック内のページ配置状態によって各々異なる方法で行われる。より具体的に、プロセッサ４はログブロックの全てのページが対応データブロックのそれと同一な位置にあるかを確認し(１５０１段階)、そうであればログブロックの全てのページが有効なのかを確認する(１５０２段階)。
【００５２】
ログブロックの全てのページがデータブロックのそれと同一に配置されており、全て有効であれば交換併合が行われる。一方、プロセッサ４は交換併合を行う前にチェックポイント領域に復旧情報を記録する(１５０３段階)。但し、１５０３段階は実行されないことがある。実行の如何はシステム設計者の選択事項である。交換併合のために、プロセッサ４は前記ログブロックを新たなデータブロックになるようにマップ領域のアドレス変換情報を更新する(１５０４段階)。すなわち、ログブロックが新たなデータブロックに遷移されると使用者の観点で論理アドレスに対応する物理アドレスが変更されるのでアドレス変換情報の更新が必要となる。実際に、マップ領域の最初の自由ページに更新されたアドレス変換情報を記録すればよい。同様にマップ領域も順次に記録され、それ以上の自由ページがない場合には自由ブロックをマップ領域に割当てて記録する。自由ブロックの割当て方法は図１４の説明と同一に行われる。これに、データブロックは消去可能ブロックに遷移され、よってデータブロックを消去してからチェックポイント領域に記録された自由ブロックリストを更新する(１５０５段階)。
【００５３】
ログブロックの何れか１ページでもデータブロックのそれと同一に配置されていないと単純併合が行われる。同様に、プロセッサ４は単純併合を行う前にチェックポイント領域に復旧情報を記録する(１５０６段階)。１５０６段階またシステム設計者の選択事項である。次いで、自由ブロックを割当てられ、ここにログブロックの有効ページをコピーし(１５０７段階)、残り部分はデータブロックの該当ページを記録した後(１５０８段階)、自由ブロックが新たなデータブロックになるようにマップ領域のアドレス変換情報を更新する(１５０９段階)。自由ブロックの割当て方法は図１４の説明と同一に行われる。一方、ログブロックとデータブロックは消去可能ブロックに遷移され、よってログブロックとデータブロックとを消去した後、チェックポイント領域に記録された自由ブロックリストを更新する(１５１０段階)。
【００５４】
ログブロックの全てのページがデータブロックのそれと同一に配置されているが、データブロックの一部ページがログブロックに存在しなければコピー併合が行われる。同様に、プロセッサ４はコピー併合を行う前にチェックポイント領域に復旧情報を記録する(１５１１段階)。１５１１段階またシステム設計者の選択事項である。次いで、データブロックの有効ページを読取ってログブロックにコピーする(１５１２段階)。次いで、ログブロックを新たなデータブロックになるようにマップ領域のアドレス変換情報を更新し(１５０４段階)、データブロックを消去した後、チェックポイント領域に記録された自由ブロックリストを更新する(１５０５段階)。
【００５５】
このように、データ更新のためのログブロックが発見されていない場合には、自由ブロックを割当てられ、ログブロックに遷移させ、ここに書込みを行う。自由ブロックが１つだけ残ってログブロックを割当てられない場合には、既存のログブロックのうち任意の１つを選択してブロック併合を行うことによって新たな自由ブロックを確保してから、ログブロックを割当てるべきである。このような状況ではブロック併合にかかるコストとブロックの今後の使用可能性を考慮して適切な選択がなされなければならない。今後の使用可能性は実行しようとする応用プログラムの特徴に従属しうる。本発明では交替アルゴリズムに対して特に規定しない。従って、本発明を具現するためにLRUのような一般化された交替アルゴリズムを使用しても良い。
【００５６】
【発明の効果】
前述したように、本発明は、フラッシュメモリの性能を改善させうるフラッシュメモリの管理方法を提供する。従来は１つのデータブロックの一部を更新するために残りの部分までコピーしたり、大規模のアドレス変換情報を必要とした。しかし、本発明によれば同じページに連続的に書込みが要請される場合にも１つのログブロック内で処理可能なのでフラッシュメモリ資源の効率性を向上させうる。さらに、ブロック併合実行中に電源遮断などによってシステムが中断される場合にも一貫性あるデータの復元が可能である。
【図面の簡単な説明】
【図１】  本発明の望ましい実施形態に係るフラッシュメモリ基盤システムのブロック図である。
【図２】  本発明によってフラッシュメモリに備えられて一般のデータが貯蔵されるブロックを説明するための参考図である。
【図３】  ログブロックとデータブロックとに対する読出しを説明するための参考図である。
【図４】  本発明の一実施形態に係るフラッシュメモリの領域分割を説明するための参考図である。
【図５】  本発明の他の実施形態に係るフラッシュメモリの領域分割を説明するための参考図である。
【図６】  ログポインタテーブルを説明するための参考図である。
【図７】  ログポインタテーブルエントリーの構造図である。
【図８】  ログポインタテーブルとフラッシュメモリの参照関係図である。
【図９】  消去可能ブロックを説明するための参考図である。
【図１０】  単純併合の概念図である。
【図１１】  コピー併合の概念図である。
【図１２】  本発明に係るブロック併合の実行におけるブロックの遷移関係を示す関係図である。
【図１３】  本発明に係る読出し方法を説明するためのフローチャートである。
【図１４】  本発明に係る書込み方法を説明するためのフローチャートである。
【図１５】  図１４のブロック併合を説明するためのフローチャートである。
【符号の説明】
１…フラッシュメモリ
２…ＲＯＭ
３…ＲＡＭ
４…プロセッサ
【図１】
0003708047.tif 000002
【図２】
0003708047.tif 000003
【図３】
0003708047.tif 000004
【図４】
0003708047.tif 000005
【図５】
0003708047.tif 000006
【図６】
0003708047.tif 000007
【図７】
0003708047.tif 000008
【図８】
0003708047.tif 000009
【図９】
0003708047.tif 000010
【図１０】
0003708047.tif 000011
【図１１】
0003708047.tif 000012
【図１２】
0003708047.tif 000013
【図１３】
0003708047.tif 000014
【図１４】
0003708047.tif 000015
【図１５】
0003708047.tif 000016