JP3827682B2 - フラッシュメモリ、そのためのマッピング制御装置及び方法 - Google Patents

Description

本発明は、フラッシュメモリ、そのためのマッピング制御装置及び方法に関し、特に、所定の状態変移アルゴリズムを基盤として、プロセスから要求される論理演算により変更されるブロックの状態情報をフラッシュメモリに更新し、書き込み／読み出し演算の際に参照するようにして、効率的なメモリアクセスを可能にするものに関する。

フラッシュメモリは、データの書き込みと削除が自在なＲＡＭ（ランダム・アクセス・メモリ）の長所と、電源の供給無しでも、格納されているデータを保存するＲＯＭ（リード・オンリ・メモリ）の長所を共に有しており、最近、デジタルカメラ、ＰＤＡ、ＭＰ３プレーヤーのような携帯用電子機器の保存媒体として広く用いられている。
この種のフラッシュメモリは、既存のＲＡＭ、不揮発性保存装置、マグネチックのように、特定の位置に保存されたデータを任意にアクセスすることができるが、データを修正または削除する方法においては、既存の保存装置とは異なり、ブロックを基本単位としてアクセスが行われる。

即ち、以前のデータを修正または削除しようとする場合、該当データを含むブロックを削除した後、データを書き換えなければならず、例えば、文字やアルファベットを１つずつ修正せず、「削除」キーを押して全ての単語を削除した後、さらに修正することのようである。
以下、使用する用語において、物理的に連続したアドレスを有するバイトをセクタといい、セクタは、フラッシュメモリに対する読み出し／書き込み演算の基本単位であり、複数のセクタで構成されるブロックは、フラッシュメモリにおいて一度の削除演算で消すことができる削除演算の基本単位である。

このようなフラッシュメモリでは、書き込み前削除(erase before write)により、フラッシュメモリに書き込まれたデータの物理アドレス(Physical Address)が変更されても、同一の論理アドレス(Logical Address)でフラッシュメモリに書き込まれたデータにアクセスすることができるように、論理‐物理マッピング(logical-physical mapping)方法を支援する。
即ち、マッピング技法は、特定のデータに対する論理アドレスと物理アドレス間のマッピング情報を所定のマッピングテーブルで管理することをいい、セクタマッピング方法、ブロックマッピング方法、及び混合方法に大別される。

図１Ａは、従来のセクタマッピング方法によるフラッシュメモリアクセス構造を示す概略図である。
図示のように、セクタマッピング方法は、フラッシュメモリのセクタ単位でマッピング情報を維持し、論理セクタ情報を用いたフラッシュメモリの物理セクタアクセスを可能にするものである。

例えば、所定のデータに対して、書き込み動作の要求と共に論理セクタ番号(Logical Sector Number: LSN)が９番と指定されると、フラッシュメモリアクセス装置では、マッピングテーブルを参照してＬＳＮの９番に相応する物理セクタ番号(Physical Sector Number: PSN)であるＰＳＮ６番を検索する。
その後、フラッシュメモリの６番セクタに該当データを書き込むが、若し、該当セクタに他のデータが書き込まれていると、フラッシュメモリの空いている物理セクタにデータを書き込み、マッピングテーブルにおいてＬＳＮ９番に相応するＰＳＮを変更する。

図１Ｂは、従来のブロックマッピング方法によるフラッシュメモリアクセス構造を示す概略図である。
図示のように、ブロックマッピング方法は、フラッシュメモリのブロック単位でマッピング情報を保持し、論理セクタ情報を論理ブロック情報に変換させた後、論理ブロック情報とオフセット情報を用いたフラッシュメモリの物理セクタアクセスを可能にするものである。

例えば、所定のデータに対して、書き込み動作の要求と共にＬＳＮが９番と指定されると、フラッシュメモリアクセス装置では、論理セクタ番号９番の論理ブロック番号(Logical Block Number: LBN)の９／４＝２を求めた後、マッピングテーブルを参照してＬＢＮに相応する物理ブロック番号(Physical Block Number: PBN)を求める。
このとき、論理ブロックのオフセットと物理ブロックのオフセットとを一致させて算出されたＰＢＮである１番において、オフセット１に相応するセクタにデータを書き込む。

若し、該当のセクタに他のデータが書き込まれていると、オフセットを一致させてフラッシュメモリの空いている物理セクタにデータを書き込み、マッピングテーブルにおいてＬＢＮ２番に相応するＰＢＮを変更する。
このとき、既存のＰＢＮに残っている有効なデータを新たなＰＢＮにオフセットを一致させてコピーしなければならない。

図１Ｃは、従来の混合マッピング方法によるフラッシュメモリアクセス構造を示す概略図である。
図示のように、混合マッピング方法は、ブロックマッピング方法のように、ブロック単位のマッピングを行った後、物理ブロック内でセクタマッピング情報を保存することにより、セクタマッピングの性質を得る方法である。
例えば、所定のデータに対して、書き込み動作の要求と共にＬＳＮが９番と指定されると、フラッシュメモリアクセス装置では、論理セクタ番号９番のＬＢＮの９／４＝２を求めた後、マッピングテーブルを参照してＬＢＮに相応するＰＢＮ１番を得る。

次に、ＰＢＮ１番の空いているセクタにデータを書き込み、ＬＳＮ９番を書き込む。
このような従来のマッピング技法の中でセクタマッピング方法は、フラッシュメモリのセクタ単位でマッピング情報を保持するためのマッピング情報が多すぎて、実際にフラッシュメモリに応用するには困難であるとの問題点があった。
このため、最近の技術は、マッピング情報を少しでも不要とするブロックマッピング方法を基盤としている。

しかし、ブロックマッピング方法は、オフセットを一致させなければならないので、同一のセクタに対する書き込み演算が多く行われる場合、新たなブロックを割り当てられて、同一のセクタにデータを書き込まなければならず、該当セクタだけでなく、同一のブロックの他のセクタの有効なデータもコピーしなければならないので、書き込みと削除の演算が多く行われ、システムの性能を顕著に低下させるとの問題点があった。

また、混合マッピング方法は、ブロックマッピングを経た後、セクタマッピング情報を保存するので、オフセットを一致させなくてもよいものの、セクタマッピング情報を書き込むために所定のメモリ空間を確保しなければならないため、ブロックマッピング技法に比べてメモリ要求量が多くなるという問題点があった。
このような従来技術の問題点を補完するために既に提案されている、韓国公開特許公報第２００２‐９２４８７号（発明の名称：フラッシュメモリの管理方法）は、所定のログブロックを割り当ててデータ更新過程での書き込み演算が要求されるデータをログブロックに書き込みをさせることにより、データの更新が多い環境でもシステムの性能が低下しないようにしたが、ログブロックに書き込まれているデータをデータブロックに移動させる過程での書き込み／削除演算が要求されるため、繰り返しの書き込み演算によるフラッシュメモリのシステム性能の低下を防止するための方法としては不十分であった。

従って、プロセッサから要求される書き込み演算による書き込みと削除演算の回数を減らすことにより、フラッシュメモリシステムの性能を向上させることができるフラッシュメモリアクセス方法が要望されている。

本発明は、上記問題点に鑑みなされたものであり、プロセッサから要求される論理演算により変更されるブロックの状態情報を、所定の状態遷移アルゴリズムにより、フラッシュメモリに書き込み、書き込み／読み出し演算の際に参照させる効率的なフラッシュメモリアクセスのためのマッピングアルゴリズムを提供することを目的とする。
また、オフセットが一致しなくても、既存のブロックマッピングアルゴリズムによるフラッシュメモリアクセス方法を用いたフラッシュメモリアクセスを可能にすることを他の目的とする。
また、状態遷移アルゴリズムを用いた状態情報により削除演算過程を最小化し、フラッシュメモリシステムの全体性能を高めることをさらに他の目的とする。

上記の目的を達成するため、本発明は、ブロックの状態を示すブロック状態情報により、フラッシュメモリに対する所定の論理演算実行の際に論理演算が行われるセクタを決定し、決定されたセクタをアクセスするものである。
また、決定されたセクタをアクセスした結果に応じて変更されるブロック状態情報を所定の状態遷移アルゴリズムにより更新するものである。

また、本発明による状態遷移アルゴリズムは、所定の論理演算に応じて変更されるブロックの状態を示すものであり、状態は、ブロックにデータが書き込まれていない第１の状態と、第１の状態において所定のデータをセクタオフセットを一致させて書き込みをした第２の状態と、第１の状態において所定のデータをセクタオフセットを一致させずに書き込みをした第３の状態と、ブロックの全体に前記第２の状態のデータが書き込まれた第４の状態と、第３の状態または第４の状態において有効なデータが新たなブロックに移され、以前のブロックに書き込まれているデータが有効でない第５の状態とを含むことを特徴とする。

以下、本発明の構成と動作を一実施形態によって説明するために、第１の状態はフリー（以下、Ｆという）、第２の状態はＭ、第３の状態はＮ、第４の状態はソース（以下、Ｓという）、第５の状態はオールド（以下、Ｏという）と称し、それぞれのブロック状態情報を有するブロックをＦブロック、Ｍブロック、Ｎブロック、Ｓブロック、Ｏブロックと称する。

本発明の一実施形態によるフラッシュメモリは、所定のセクタからなるブロック単位で領域が区分され、ブロックの状態を示し、論理演算が行われるセクタを決定するのに用いられるブロック状態情報を含むことを特徴とする。
本発明の一実施形態によるフラッシュメモリのためのマッピング制御装置は、所定のセクタからなるブロックを単位として領域が区分され、前記ブロックの状態を示すブロック状態情報を含むフラッシュメモリと、フラッシュメモリに対する所定の論理演算が要求されると、前記ブロック状態情報により前記論理演算が行われるセクタを決定し、所定の状態遷移アルゴリズムにより前記ブロック状態情報を更新するプロセッサとを備えることを特徴とする。

本発明の一実施形態によるフラッシュメモリのためのマッピング制御方法は、フラッシュメモリの特定の論理セクタに対し、所定の論理演算が要求されると、マッピングテーブルを参照して前記論理セクタに該当する物理ブロックを検索するステップと、物理ブロックのブロック状態情報により前記論理演算が行われるセクタを決定するステップと、決定されるセクタをアクセスして前記論理演算を行うステップとを含むことを特徴とする。

本発明によると、フラッシュメモリに要求される論理セクタに対する書き込み／読み出し演算において、所定の状態遷移アルゴリズムにより該当の演算が行われるセクタを決定することにより、フラッシュメモリの特定の論理ブロックに対する書き込み演算の際に要求される削除演算を最小化し、フラッシュメモリシステムの性能を最大化することができる。

以下、本発明の好ましい実施形態を、添付図面に基づいて詳しく説明する。
先ず、本発明によるフラッシュメモリとそのためのマッピング制御装置を含むフラッシュメモリ基盤システムの構成と動作について添付図面に基づいて詳しく説明する。
図２は、本発明の一実施形態によるフラッシュメモリ基盤システムを示す概略図である。
図示のように、システムは、フラッシュメモリ１００と、システムメモリ３００と、プロセッサ５００とからなる。

フラッシュメモリ１００は、削除演算の基本単位であるブロックで構成され、各ブロックは書き込み／読み出し演算の基本単位である複数のセクタからなる。
また、フラッシュメモリ１００は、各ブロックの状態を示し、書き込み／読み出し等の論理演算が行われるセクタを決定するのに用いられるブロック状態情報を含む。
ブロック状態情報は、フラッシュメモリ１００に関する情報を書き込むメタブロック(Meta Block)に書き込み、または各ブロックの保存領域の中で所定領域（例えば、スペア）を割り当てられて書き込む。

システムメモリ３００は、フラッシュメモリアクセスのためのアクセスコードを含むものであって、ＲＡＭまたはＲＯＭのような現地実行(eXecute‐In‐Place: XIP)が可能なメモリが用いられる。
プロセッサ５００は、システムメモリ３００に書き込まれているフラッシュメモリアクセスコードを用いて、フラッシュメモリ１００をアクセスするものであって、所定の論理演算が要求されると、論理セクタのアドレスをフラッシュメモリアクセスのための物理ブロックアドレスに変換し、物理ブロックアドレスを通じて該当ブロックのブロック状態情報により論理演算が行われるセクタを決定して論理演算を行うものである。

また、プロセッサ５００は、所定の論理演算が要求されると、所定の状態遷移アルゴリズムを通じて論理演算により変更される各ブロックのブロック状態情報を決定し、決定されたブロック状態情報によりフラッシュメモリ１００に書き込まれている該当ブロックのブロック状態情報を更新する。
各ブロック状態情報により、各ブロックは、ブロックにデータが書き込まれていないＦブロックと、Ｆブロックにおいて所定のデータをセクタオフセットを一致させて書き込みをしたＭブロックと、Ｍブロックにおいて所定のデータをセクタオフセットを一致させずに書き込みをしたＮブロックと、ブロック全体にＭブロックのデータが書き込まれたＳブロックと、ＮブロックまたはＳブロックにおいて有効なデータが新たなブロックに移され、以前のブロックに書き込まれたデータが有効でないＯブロックとからなる。

状態遷移アルゴリズムは、現在、Ｍブロックが全部使用中であれば、新たに要求される書き込み演算を行うためにＦブロックをさらに割り当て、既存のＭブロックをＳブロックに遷移させた後、新たなデータをＦブロックに書き込むスワップマージ(swap merge)演算を行う。

また、状態遷移アルゴリズムは、現在、Ｎブロックが全部使用中であれば、新たに要求される書き込み演算を行うために新たなＦブロックをさらに割り当て、既存のＮブロックに書き込まれたデータの中で有効なデータのみをＦブロックに書き込み、既存のＮブロックをＯブロックに遷移させるスマートマージ(smart merge)演算を行う。
このようなスマートマージ演算により、新たなＦブロックに書き込まれるデータは、セクタオフセットが一致され、ＦブロックはＭブロックに遷移させられ、Ｏブロックは所定の削除演算によりＦブロックに遷移させられる。

図３は、本発明の一実施形態によるフラッシュメモリ基盤システムのソフトウェアの構造を示す概略図である。
図示のように、本発明によるソフトウェアの構造は、システムのファイルシステムにより所定のファイルに対する論理演算を行う応用プログラムモジュール(Applications)と、応用プログラムモジュールで行われる論理演算により要求されるフラッシュメモリのデータをアクセスするフラッシュメモリマッピング制御装置モジュールと、フラッシュメモリマッピング制御装置モジュールのアクセス制御により相応するデータを書き込みまたは読み出しをするフラッシュメモリモジュール(Flash Memory)とで構成される。

フラッシュメモリマッピング制御装置モジュールは、応用プログラムモジュールから要求される論理演算によりフラッシュメモリモジュールにアクセスし、フラッシュメモリをアクセスするファイルシステムと、ファイルシステムでのフラッシュメモリアクセスができるように、所定の論理セクタ番号（ＬＳＮ）をフラッシュメモリ上の実際のアドレスである物理アドレスに変更させるフラッシュ変換階層(Flash Translation Layer: FTL)とからなる。

図４は、本発明の一実施形態による状態遷移アルゴリズムの状態遷移過程を示す状態遷移図である。
図示のように、フラッシュメモリ１００の所定ブロックに対する状態遷移過程は、ブロックに何らのデータも書き込まれていないＦブロックから始める。
Ｆブロックに対する書き込み演算がプロセッサ５００により要求されると、プロセッサ５００では書き込み演算を行うセクタを決定し、書き込み演算が要求されるデータのセクタオフセットが一致させることにより、プロセッサ５００ではブロック状態情報をＦブロックからＭブロックに遷移させる（ａ）。

Ｍブロックは、プロセッサ５００による書き込み演算により、ＳブロックまたはＮブロックに遷移される。即ち、Ｍブロックにセクタオフセットが一致するデータに対する書き込み演算が繰り返され、書き込み可能なセクタが存在しなくなると、スワップマージ演算を行ってＦブロックをさらに割り当て、ＭブロックをＳブロックに遷移する（ｂ）。
また、Ｍブロックに、以前にデータが書き込まれたセクタに対する書き込み演算が要求されると、プロセッサ５００では、任意のセクタを書き込み演算が行われるセクタと決定し、ブロック状態情報をＭブロックからＮブロックに遷移し（ｃ）、決定されたセクタにデータを書き込む。

Ｓブロックのデータがもう有効でなくなると、プロセッサ５００ではブロック状態情報をＳブロックからＯブロックに遷移する（ｄ）。
また、Ｎブロックにセクタオフセットが一致しないデータに対する書き込み演算が繰り返され、書き込み可能なセクタが存在しなくなると、スマートマージ演算を行って有効なデータのみを新たに割り当てられるＦブロックに書き込み、ブロック状態情報をＮブロックからＯブロックに遷移する（ｅ）。

Ｏブロックは、プロセッサ５００による所定の削除演算によりＦブロックに遷移する（ｆ）。
参考として、前述した本発明の一実施形態によるフラッシュメモリとそのためのマッピング制御装置は、各モジュールが全てハードウェアで構成されても、一部のモジュールがソフトウェアで構成されても、または全体のモジュールがソフトウェアで構成されていてもよい。

従って、本発明の一実施形態によるフラッシュメモリとそのためのマッピング制御装置がハードウェアまたはソフトウェアで構成されるものは、本発明の思想から外れるものではなく、本発明の思想を逸脱しない範囲内で、ソフトウェア及び／またはハードウェアで構成されることによる修正と変更が実施可能であることは明らかである。

次に、本発明によるフラッシュメモリ基盤システムを用いてフラッシュメモリをアクセスするフラッシュメモリマッピング制御方法について、添付図面に基づいて詳しく説明する。
本発明によるフラッシュメモリマッピング制御過程の説明において、初期化過程は既存の処理過程と同一であるので、その説明は省略する。
従って、先ず、本発明によるマッピング制御方法による書き込み演算過程を説明してから、マッピング制御方法による読み出し演算過程について説明する。

１．書き込み演算過程
図５は、本発明の一実施形態による書き込み演算過程を概略的に示すフローチャートである。
図示のように、先ずプロセッサ５００では、所定の論理セクタ番号を有するデータに対する書き込み演算が要求されると、指定された論理セクタ番号（以下、論理セクタという）から論理ブロック番号（以下、論理ブロックという）を算出する。

その後、プロセッサ５００では、初期化過程で得られるマッピングテーブルから算出された論理ブロックに相応する物理ブロック番号（以下、物理ブロックという）を検索し、該当物理ブロックのブロック状態情報によりマージ演算が必要か否かを判別する（Ｓ１）。
即ち、該当物理ブロックに対して繰り返される書き込み演算により、該当物理ブロックに書き込み可能なセクタが存在しない場合、新たなデータを書き込むブロックを割り当てるために、スワップまたはスマートマージ演算が要求されるか否かを判断することである。

判別の結果、マージ演算が必要であれば、該当物理ブロックの特性によりマージ演算を行う（Ｓ２）。
即ち、プロセッサ５００では、マッピングテーブルに書き込まれた該当物理ブロックの現在状態がＭブロックであれば、ＭブロックをＳブロックに遷移するスワップマージを行い、該当物理ブロックの現在状態がＮブロックであれば、新たにＦブロックを割り当てた後、Ｎブロックから有効なデータのみを検出して書き込みをした後、ＦブロックをＭブロックに遷移するスマートマージを行う。

判別の結果、マージ演算が不要であるか、またはマージ演算が行われると、プロセッサ５００では、マッピングテーブルから書き込み演算が要求される論理ブロックがＭブロックまたはＮブロックを有するか否かを判別する（Ｓ３）。
判別の結果、論理ブロックがＭブロックまたはＮブロックを有すると、プロセッサ５００は、ＭブロックまたはＮブロックにおいて、書き込み演算が要求されるデータのオフセット情報と一致するセクタを検索し、該当セクタが空いているか否かを判別する（Ｓ４）。

判別の結果、該当セクタが空いていると、プロセッサ５００は、該当セクタに書き込み演算が要求されたデータを書き込み（Ｓ５）、判別の結果、該当セクタが空いていなければ、該当ブロックがＭブロックであるか否かを判別する（Ｓ６）。
判別の結果、該当ブロックがＭブロックであると、該当物理ブロックのブロック状態情報をＮブロックに遷移し（Ｓ７）、判別の結果、該当ブロックがＭブロックでなく、またはＭブロックからＮブロックに遷移されると、プロセッサ５００は、Ｎブロックから任意のセクタを選択し、セクタオフセットが一致しない状態でデータを書き込む（Ｓ８）。

判別の結果、論理ブロックがＭブロックまたはＮブロックを有していなければ、プロセッサ５００は、算出された論理ブロックに相応する物理ブロックにデータが全く書き込まれておらず、またはマージ演算が行われたものであるので、新たにデータを書き込むＦブロックを割り当てる（Ｓ９）。
その後、プロセッサ５００は、割り当てられたＦブロックをＭブロックに遷移させ（Ｓ１０）、Ｍブロックにおいて書き込み演算が要求されたデータをセクタオフセットが一致するように書き込む（Ｓ１１）。

２．読み出し演算過程
図６は、本発明の一実施形態による読み出し演算過程を概略的に示すフローチャートである。
図示のように、先ずプロセッサ５００は、所定の論理セクタ番号を有するデータに対する読み出し演算が要求されると、指定された論理セクタから論理ブロックを算出する。
その後、プロセッサ５００は、初期化過程で得られるマッピングテーブルから算出された論理ブロックに相応する物理ブロックを検索し、読み出し演算が要求される論理ブロックがＭブロックまたはＮブロックを有するか否かを判別する（Ｓ１０）。

判別の結果、論理ブロックがＭブロックまたはＮブロックを有していなければ、プロセッサ５００は、マッピングテーブルにより論理ブロックがＳブロックを有するか否かを判別する（Ｓ１１）。
判別の結果、論理ブロックがＳブロックを有すると、プロセッサ５００は、Ｓブロックにおいて、読み出し演算が要求されたデータのオフセット情報と一致するセクタを検索し、該当セクタに書き込まれたデータを読み出す（Ｓ１２）。

判別の結果、論理ブロックがＳブロックを有していなければ、プロセッサ５００は、読み出し演算が要求されたデータがフラッシュメモリ１００に存在しないものと判断し、読み出しミスのメッセージを発生させる（Ｓ１３）。
判別の結果、論理ブロックがＭブロックまたはＮブロックを有すると、プロセッサ５００は、論理ブロックに相応する物理ブロックがＭブロックを有するか否かを判別する（Ｓ１４）。

判別の結果、論理ブロックに相応する物理ブロックがＭブロックを有していなければ、プロセッサ５００は、Ｎブロックに読み出し演算が要求された論理セクタに該当するセクタが存在するか否かを判別する（Ｓ１５）。
判別の結果、Ｎブロックに該当セクタが存在すると、Ｎブロックの該当セクタに書き込まれたデータを読み出し（Ｓ１６）、判別の結果、Ｎブロックに該当セクタが存在しなければ、論理ブロックに相応する物理ブロックがＳブロックを有するか否かを判別する（Ｓ１７）。

判別の結果、論理ブロックに相応する物理ブロックがＳブロックを有すると、該当セクタに書き込まれたデータを読み出し（Ｓ１８）、判別の結果、論理ブロックに相応する物理ブロックがＳブロックを有していなければ、フラッシュメモリ１００に読み出し演算が要求されたデータが存在しないものと判断し、読み出しミスのメッセージを発生させる（Ｓ１９）。
判別の結果、論理ブロックに相応する物理ブロックがＭブロックであると、プロセッサ５００は、読み出し演算が要求されたセクタがＭブロックに存在するか否かを判別する（Ｓ２０）。

判別の結果、該当セクタがＭブロックに存在すると、Ｍブロックの該当セクタからデータを読み出し（Ｓ２１）、判別の結果、該当セクタがＭブロックに存在しなければ、読み出し演算が要求された論理ブロックがＳブロックを有するか否かを判別する（Ｓ２２）。
判別の結果、論理ブロックがＳブロックを有していなければ、プロセッサ５００は、読み出し演算が要求されたデータがフラッシュメモリ１００に存在しないものと判断し、読み出しミスのメッセージを発生させる（Ｓ２３）。

判別の結果、論理ブロックがＳブロックを有すると、プロセッサ５００は、Ｓブロックにおいて、読み出し演算が要求されたデータのオフセット情報と一致するセクタを検索し、該当セクタに書き込まれたデータを読み出す（Ｓ２４）。
次に、このような本発明の一実施形態によるフラッシュメモリと、そのためのマッピング制御装置及び方法について添付図面に基づいて詳しく説明する。

図７は、本発明の一実施形態によるマッピングテーブルを用いる書き込み演算過程を示す概略図である。
本発明によるマッピングテーブルにおいて、論理ブロックは最大２つ以下の物理ブロックと対応され、２つの物理ブロックは、Ｓ状態のブロックとＭ状態またはＮ状態のブロックと組み合わされてもよい。

若し、図７に示すように、論理セクタ９（ＬＳＮ＝９）のデータに対する書き込み演算が要求されると、プロセッサ５００では、論理セクタ９の論理ブロック及びオフセット値を算出する（ＬＢＮ：９／４＝２、Ｏｆｆｓｅｔ：１）。
この場合、プロセッサ５００では、マッピングテーブルを参照して算出された論理ブロック（ＬＢＮ＝２）に相応する物理ブロック及び状態を検索する（ａ）。
その後、プロセッサ５００では、該当物理ブロックのブロック状態情報からマージ演算が必要か否かを判別する。

若し、該当物理ブロックが１であり、現在、Ｍ状態として全てのセクタにデータが書き込まれていると、プロセッサ５００では、ＭブロックをＳブロックに遷移し、データ書き込みみのためのＦブロックを割り当てるスワップマージ演算を行う。
スワップマージ演算によって新たなＦブロックに物理ブロック２（ＰＢＮ＝２）が割り当てられると、プロセッサ５００では、書き込み演算が要求されたデータを新たに割り当てられた物理ブロック２にオフセット値を一致させて書き込み、マッピングテーブルにおいて論理ブロック（ＬＢＮ＝２）に相応する物理ブロック及び状態情報を更新する。

即ち、プロセッサ５００は、マッピングテーブルにおいて論理ブロック（ＬＢＮ＝２）に対する物理ブロック（ＰＢＮ＝１）のブロック状態をＭ→Ｓと、新たに割り当てられた物理ブロック（ＰＢＮ＝２）のブロック状態をＦ→Ｍと更新する。
例えば、図８Ａに示すように、フラッシュメモリ１００の一つのブロックが４つのセクタからなる場合、プロセッサ５００では、所定の論理セクタに対する書き込み演算がセクタオフセット０、１、２、３、０の順に要求されると、論理セクタから論理ブロックを算出する。

その後、プロセッサ５００は、マッピングテーブルを参照して算出された論理ブロックに該当する物理ブロックを検索し、検索された物理ブロックのブロック状態情報を確認し、ブロック状態情報により書き込み演算が行われるセクタを決定する。
若し、該当物理ブロックがＦブロックであれば、プロセッサ５００は、オフセット情報により該当物理ブロックにデータを書き込む。
即ち、プロセッサ５００は、ブロック状態情報をＦブロックからＭブロックに遷移した後、セクタオフセットの順によって０、１、２、３、０の順に該当物理ブロックの各セクタにデータを書き込む。

この場合、１つのブロックが４つのセクタからなるので、０、１、２、３のセクタにデータが書き込まれると、該当ブロックに書き込み可能なセクタが存在しなくなるので、プロセッサ５００では、スワップマージ演算によりＦブロックをさらに割り当て、ブロック状態情報をＭブロックからＳブロックに遷移する（１）。
その後、プロセッサ５００は、さらに割り当てられたＦブロックのブロック状態情報をＦブロックからＭブロックに遷移させた後、セクタオフセット０のデータを該当セクタに書き込む（２）。

他の実施形態として、図８Ｂに示すように、プロセッサ５００では、所定の論理セクタに対する書き込み演算がセクタオフセット０、１、２、３、０、１、２、３、０の順に要求されると、論理セクタから論理ブロックを算出する。
その後、プロセッサ５００は、 マッピングテーブルを参照して算出された論理ブロックに該当する物理ブロックを検索し、検索された物理ブロックのブロック状態情報を確認し、ブロック状態情報によって書き込み演算が行われるセクタを決定する。

若し、該当物理ブロックがＦブロックであれば、プロセッサ５００は、オフセット情報によって該当物理ブロックにデータを書き込む。
即ち、プロセッサ５００は、ブロック状態情報をＦブロックからＭブロックに遷移した後、セクタオフセットの順によって０、１、２、３、０、１、２、３、０の順に該当物理ブロックの各セクタにデータを書き込む。

この場合、１つのブロックが４つのセクタからなるので、０、１、２、３のセクタにデータが書き込まれると、該当ブロックに書き込み可能なセクタが存在しなくなるので、プロセッサ５００では、スワップマージ演算によりＦブロックをさらに割り当て、ブロック状態情報をＭブロックからＳブロックに遷移させる（１）。
その後、プロセッサ５００は、さらに割り当てられたＦブロックのブロック状態情報をＦブロックからＭブロックに遷移させた後、セクタオフセット０、１、２、３のデータをさらに割り当てられたＭブロックの該当セクタに書き込む。

その後、プロセッサ５００は、該当ブロックに書き込み可能なセクタが存在しなくなるので、Ｓブロックのデータがもう存在しなくなり、これによって、Ｓブロックのブロック状態情報をＳブロックからＯブロックに遷移させた後、スワップマージ演算によりＦブロックをさらに割り当て、以前にさらに割り当てられたブロックのブロック状態情報をＭブロックからＳブロックに遷移させる（２）。
その後、プロセッサ５００は、またさらに割り当てられたＦブロックのブロック状態情報をＦブロックからＭブロックに遷移させた後、セクタオフセット０のデータを該当セクタに書き込む（３）。

また他の実施形態として、図８Ｃに示すように、プロセッサ５００では、所定の論理セクタに対する書き込み演算がセクタオフセット０、０、０、０、１の順に要求されると、論理セクタから論理ブロックを算出する。
その後、プロセッサ５００は、 マッピングテーブルを参照して算出された論理ブロックに該当する物理ブロックを検索し、検索された物理ブロックのブロック状態情報を確認し、ブロック状態情報によって書き込み演算が行われるセクタを決定する。

若し、該当物理ブロックがＦブロックであれば、プロセッサ５００は、オフセット情報によって該当物理ブロックにデータを書き込む。
即ち、プロセッサ５００は、ブロック状態情報をＦブロックからＭブロックに遷移した後、セクタオフセットの順によって０、０、０、０、１の順に該当物理ブロックの各セクタにデータを書き込む。

この場合、２番目の書き込み演算を行う過程において、物理ブロックの該当セクタに既にデータが書き込まれているので、プロセッサ５００は、物理ブロックのブロック状態情報をＭブロックからＮブロックに遷移させた後、任意のセクタを選択し、書き込み演算が要求されたデータを書き込む。
このようにセクタオフセットが一致しない書き込み演算が繰り返され、該当物理ブロックに書き込み可能なセクタが存在しなくなると、プロセッサ５００では、スマートマージ演算によりＦブロックをさらに割り当て、ＮブロックをＯブロックに遷移させる（１）。

その後、プロセッサ５００は、さらに割り当てられたＦブロックのブロック状態情報をＦブロックからＭブロックに遷移させた後、Ｎブロックに書き込まれているデータの中で有効なデータのみを検出してＭブロックの該当セクタに書き込む。
即ち、Ｏブロックに書き込まれているセクタオフセット０のデータのうち、最終に書き込まれたデータのみを読み出し、さらに割り当てられたＭブロックのセクタ０に書き込み、セクタオフセット１のデータを該当セクタに書き込む（２）。

以上、本発明について図示された一実施形態により詳述したが、これは、一例に過ぎず、その技術の分野における通常の知識を有する者であれば、これから種々の変形と均等な他の実施形態が可能なことが理解されるべきである。従って、本発明の真正な技術的な保護範囲は、上記した請求の範囲の技術的思想により定められるものである。

従来のフラッシュメモリアクセス方法を制御方式による演算過程を示すフラッシュメモリブロック図である。 従来のフラッシュメモリアクセス方法を制御方式による演算過程を示すフラッシュメモリブロック図である。 従来のフラッシュメモリアクセス方法を制御方式による演算過程を示すフラッシュメモリブロック図である。 本発明の一実施形態によるフラッシュメモリ基盤のシステムを示す概略図である。 本発明の一実施形態によるフラッシュメモリ基盤のシステムのソフトウェアの構造を示す概略図である。 本発明の一実施形態による状態遷移アルゴリズムの状態遷移の過程を示す状態遷移図である。 本発明の一実施形態による書き込み演算過程を概略的に示すフローチャートである。 本発明の一実施形態による読み出し演算過程を概略的に示すフローチャートである。 本発明の一実施形態によるマッピングテーブルを用いる書き込み演算過程を示す概略図である。 本発明の一実施形態によるフラッシュメモリのブロック遷移の過程を示す概略図である。 本発明の一実施形態によるフラッシュメモリのブロック遷移の過程を示す概略図である。 本発明の一実施形態によるフラッシュメモリのブロック遷移の過程を示す概略図である。

符号の説明

１００…フラッシュメモリ
３００…システムメモリ
５００…プロセッサ

Claims (26)

1. 所定のセクタからなるブロック単位で領域が区分され、
   前記ブロックの状態を示し、書き込み／読み出しが行われるセクタを決定するのに用いられるブロック状態情報を含み、
   前記ブロック状態情報は、所定の状態遷移アルゴリズムにより決定されることを特徴とするフラッシュメモリ。
2. 前記状態が、前記ブロックにデータが書き込まれていない第１の状態と、
   前記第１の状態において所定のデータをセクタオフセットを一致させて書き込みをした第２の状態と、
   前記第１の状態において所定のデータをセクタオフセットを一致させずに書き込みをした第３の状態と、
   前記ブロックの全体に前記第２の状態のデータが書き込まれた第４の状態と、
   前記第３の状態または第４の状態において有効なデータが新たなブロックに移され、以前のブロックに書き込まれたデータが有効でない第５の状態と
   を含むことを特徴とする請求項１に記載のフラッシュメモリ。
3. 前記状態遷移アルゴリズムは、前記第４の状態において新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当てるスワップマージ演算を行うことを特徴とする請求項２に記載のフラッシュメモリ。
4. 前記状態遷移アルゴリズムは、前記第３の状態において該当ブロックの全てのセクタが使用中であれば、新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当て、既存のブロックに書き込まれているデータの中で有効なデータのみを検出し、前記割り当てられたブロックに書き込むスマートマージ演算を行うことを特徴とする請求項２に記載のフラッシュメモリ。
5. 前記スマートマージ演算は、前記有効なデータが書き込まれると、前記割り当てられたブロックのブロック状態情報を第１の状態から第２の状態に遷移させ、既存のブロックのブロック状態情報を第３の状態から第５の状態に遷移させることを特徴とする請求項４に記載のフラッシュメモリ。
6. 前記第５の状態は、削除演算により前記第１の状態に遷移させられることを特徴とする請求項２に記載のフラッシュメモリ。
7. 前記ブロック状態情報は、前記フラッシュメモリに関する情報を書き込むメタブロックに書き込まれたり、前記各ブロックに書き込まれたりすることを特徴とする請求項１に記載のフラッシュメモリ。
8. 所定のセクタからなるブロックを単位として領域が区分され、前記ブロックの状態を示すブロック状態情報を含むフラッシュメモリと、
   前記フラッシュメモリに対する書き込み／読み出しが要求されると、要求された論理アドレスをマッピングテーブルを参照して物理ブロックアドレスに変換し、この物理ブロックアドレスのブロック状態情報により前記書き込み／読み出しが行われるセクタを決定し、所定の状態遷移アルゴリズムにより前記ブロック状態情報を更新するプロセッサと
   を備えることを特徴とするフラッシュメモリのためのマッピング制御装置。
9. 前記ブロック状態情報は、前記フラッシュメモリに関する情報を書き込むメタブロックに書き込まれたり、前記各ブロックに書き込まれたりすることを特徴とする請求項８に記載のフラッシュメモリのためのマッピング制御装置。
10. 前記プロセッサは、前記ブロック状態情報により決定されるセクタに所定のデータを書き込み、または前記セクタからデータを読み出し、前記更新されるブロック状態情報により削除演算を通じて有効でないブロックのデータを削除することを特徴とする請求項８に記載のフラッシュメモリのためのマッピング制御装置。
11. 前記状態は、前記ブロックにデータが書き込まれていない第１の状態と、
    前記第１の状態において所定のデータをセクタオフセットを一致させて書き込みをした第２の状態と、
    前記第１の状態において所定のデータをセクタオフセットを一致させずに書き込みをした第３の状態と、
    前記ブロックの全体に前記第２の状態のデータが書き込まれた第４の状態と、
    前記第３の状態または第４の状態において有効なデータが新たなブロックに移され、以前のブロックに書き込まれたデータが有効でない第５の状態と
    を含むことを特徴とする請求項８に記載のフラッシュメモリのためのマッピング制御装置。
12. 前記状態遷移アルゴリズムは、前記第４の状態において新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当てるスワップマージ演算を行うことを特徴とする請求項１１に記載のフラッシュメモリのためのマッピング制御装置。
13. 前記状態遷移アルゴリズムは、前記第３の状態において該当ブロックの全てのセクタが使用中であれば、新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当て、既存のブロックに書き込まれているデータの中で有効なデータのみを検出し、前記割り当てられたブロックに書き込むスマートマージ演算を行うことを特徴とする請求項１１に記載のフラッシュメモリのためのマッピング制御装置。
14. 前記スマートマージ演算は、前記有効なデータが書き込まれると、前記割り当てられたブロックのブロック状態情報を第１の状態から第２の状態に遷移させ、既存のブロックのブロック状態情報を第３の状態から第５の状態に遷移させることを特徴とする請求項１３に記載のフラッシュメモリのためのマッピング制御装置。
15. 前記第５の状態は、削除演算により前記第１の状態に遷移させられることを特徴とする請求項１１に記載のフラッシュメモリのためのマッピング制御装置。
16. フラッシュメモリの特定の論理セクタに対し、書き込み／読み出しが要求されると、マッピングテーブルを参照して前記論理セクタに該当する物理ブロックを検索するステップと、
    前記物理ブロックのブロック状態情報により前記書き込み／読み出しが行われるセクタを決定するステップと、
    前記決定されるセクタをアクセスして前記書き込み／読み出しを行うステップと
    を含み、
    前記ブロック状態情報は、所定の状態遷移アルゴリズムにより決定されることを特徴とするフラッシュメモリのためのマッピング制御方法。
17. 前記論理セクタに該当する物理ブロックを検索するステップは、
    前記論理セクタから論理ブロックを算出するステップと、
    前記算出された論理ブロックに該当する物理ブロックを前記マッピングテーブルから検索するステップと
    を含むことを特徴とする請求項１６に記載のフラッシュメモリのためのマッピング制御方法。
18. 前記書き込み／読み出しが行われるセクタを決定するステップは、前記物理ブロックのブロック状態情報によりセクタオフセットが一致するセクタを選択することを特徴とする請求項１６に記載のフラッシュメモリのためのマッピング制御方法。
19. 前記書き込み／読み出しが行われるセクタを決定するステップは、前記物理ブロックのブロック状態情報によりセクタオフセットが一致しないセクタを選択することを特徴とする請求項１６に記載のフラッシュメモリのためのマッピング制御方法。
20. 前記決定されるセクタをアクセスして前記書き込み／読み出しを行うステップは、
    前記書き込み／読み出しに応じて変更される前記物理ブロックのブロック状態情報を所定の状態遷移アルゴリズムにより決定するステップと、
    前記決定されたブロック状態情報により、前記物理ブロックのブロック状態情報を更新するステップと
    を含むことを特徴とする請求項１６に記載のフラッシュメモリのためのマッピング制御方法。
21. 前記状態は、前記ブロックにデータが書き込まれていない第１の状態と、
    前記第１の状態において所定のデータをセクタオフセットを一致させて書き込みをした第２の状態と、
    前記第１の状態において所定のデータをセクタオフセットを一致させずに書き込みをした第３の状態と、
    前記ブロックの全体に前記第２の状態のデータが書き込まれた第４の状態と、
    前記第３の状態または第４の状態において有効なデータが新たなブロックに移され、以前のブロックに書き込まれたデータが有効でない第５の状態と
    を含むことを特徴とする請求項２０に記載のフラッシュメモリのためのマッピング制御方法。
22. 前記状態遷移アルゴリズムは、前記第４の状態において新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当てるスワップマージ演算を行うことを特徴とする請求項２１に記載のフラッシュメモリのためのマッピング制御方法。
23. 前記状態遷移アルゴリズムは、前記第３の状態において該当ブロックの全てのセクタが使用中であれば、新たに要求される書き込み演算を行うために、第１の状態のブロックをさらに割り当て、既存のブロックに書き込まれているデータの中で有効なデータのみを検出し、前記割り当てられたブロックに書き込むスマートマージ演算を行うことを特徴とする請求項２１に記載のフラッシュメモリのためのマッピング制御方法。
24. 前記スマートマージ演算は、前記有効なデータが書き込まれると、前記割り当てられたブロックのブロック状態情報を第１の状態から第２の状態に遷移させ、既存のブロックのブロック状態情報を第３の状態から第５の状態に遷移させることを特徴とする請求項２３に記載のフラッシュメモリのためのマッピング制御方法。
25. 前記第５の状態は、削除演算により前記第１の状態に遷移させられることを特徴とする請求項２１に記載のフラッシュメモリのためのマッピング制御方法。
26. 前記ブロック状態情報は、前記フラッシュメモリに関する情報を書き込むメタブロックに書き込まれたり、前記各ブロックに書き込まれたりすることを特徴とする請求項１６に記載のフラッシュメモリのためのマッピング制御方法。

Images