(57)【要約】順次書き込み処理のみを行うように制限されているフラッシュデバイスを管理するためのシステム及び方法。書き込み要求が受信された後、データを書き込むために、同じブロック内で最後に書き込んだ部分である以前に書き込んだ物理部分の位置に応じて、フラッシュデバイスの物理部分を位置決めする。したがって、この物理部分は、物理的に、以前に書き込んだ物理部分よりもブロック内における高いアドレスに位置する。すなわち、書き込み処理は、ランダムに選択した位置で行うのではなく、順次書き込み制限に抵触しない位置で行う。この部分は、例えば、ページ等のブロック内の位置であることが好ましく、同じブロック内に書き込むためにページが利用可能である場合、データはそのページに書き込まれる。また、このページは、そのブロック内における、以前に書き込んだどのページよりも高いアドレスに位置することが好ましい。
2005505818.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）各ブロックが複数のページからなる、複数のブロックを含むメモリを持つ少なくとも一つのフラッシュデバイスからなるフラッシュメモリ・システム、
（ｂ）ページ書き込み要求を受信する順序に拘らず、ページ書き込み要求を管理するフラッシュ管理システム、そして
（ｃ）前記ページ書き込み要求を受信する前記順序を、書き込み順序へ変換するモジュールからなるシステムであって、前記ページ書き込み要求を受信する前記順序に拘らず、前記ページ書き込み要求内のデータが、各ブロック内における物理的に連続なページとして書き込まれることを特徴とするシステム。
【請求項２】
前記フラッシュ管理システムが複数の仮想アドレスを含み、前記フラッシュデバイスが複数の物理アドレスを含み、前記フラッシュ管理システムは、各仮想ブロックを一つ以上の物理ブロック内へマッピングすることによって、前記仮想アドレスを前記物理アドレスへマッピングする、請求項１に記載のシステム。
【請求項３】
各ページ書き込み要求が仮想アドレスへのものであり、前記フラッシュ管理システムは、各ブロック内において、後続するページ書き込み処理の各々に対して、次のより高い物理アドレスにページが書き込まれるように、仮想アドレスを物理アドレスへマッピングする、請求項２に記載のシステム。
【請求項４】
物理的に書き込んだページの各々が、対応する仮想ブロック内の対応する仮想ページ番号を伴う、請求項３に記載のシステム。
【請求項５】
前記フラッシュメモリ・システムからデータを読み取るとき、前記仮想ページ番号が、要求仮想ページに対応する最近書き込んだデータを識別する、請求項４に記載のシステム。
【請求項６】
複数の物理ページが同一の仮想ページ番号に関連する場合、前記要求仮想ページに対応する前記物理ページは、データを最近書き込んだ前記物理ページである、請求項５に記載のシステム。
【請求項７】
物理ブロックが仮想ブロックに対応し、前記物理ブロックが空きページを持たず、前記仮想ブロックに対して書き込み要求が受信された場合、前記仮想ブロックに対する新しい物理ブロックが割り当てられて、前記書き込み要求のデータが、前記新しい物理ブロックの第一のページに書き込まれる、請求項３に記載のシステム。
【請求項８】
仮想ブロックに対応する物理ブロックのグループを、もし必要なら、特定な時間に、前記仮想ブロックの仮想ページに対応するデータの少なくとも一部を単一ブロックへコピーすることによって、圧縮して、少なくとも一つの物理ブロックを解放する、請求項７に記載のシステム。
【請求項９】
前記単一のブロックが、新たに割り当てられたブロック、あるいは前記仮想ブロックの最近割り当てられたブロックである、請求項８に記載のシステム。
【請求項１０】
前記ブロックは、前記フラッシュ管理システムが新しい物理ブロックを必要とするとき、そして複数の空きブロックが所定数よりも少ないときに圧縮される、請求項９に記載のシステム。
【請求項１１】
前記ブロックは、圧縮されずに前記仮想ブロックに対応する物理ブロックの前記グループの大きさが、所定数よりも大きくなったときに圧縮される、請求項９に記載のシステム。
【請求項１２】
前記所定数が１であり、前記仮想ブロックが前記物理ブロックに１対１でマッピングされる、請求項１１に記載のシステム。
【請求項１３】
前記フラッシュ管理システムが複数の仮想アドレスを含み、前記フラッシュデバイスが複数の物理アドレスを含み、前記フラッシュ管理システムが、各仮想ページを一つ以上の物理ページ内へマッピングすることによって、前記仮想アドレスを前記物理アドレスへマッピングする、請求項１に記載のシステム。
【請求項１４】
各ページ書き込み要求が仮想アドレスへのものであり、前記フラッシュ管理システムは、後続する各々のページ書き込み処理に対して、前記フラッシュデバイスの少なくとも一部内の、次のより高い物理アドレスにページが書き込まれるように、仮想アドレスを物理アドレスへマッピングする、請求項１３に記載のシステム。
【請求項１５】
物理的に書き込まれたページの各々が、対応する仮想ページ番号を伴う、請求項１４に記載のシステム。
【請求項１６】
前記フラッシュメモリ・システムからデータを読み取るとき、前記仮想ページ番号が、要求仮想ページに対応する最近書き込んだデータを識別する、請求項１５に記載のシステム。
【請求項１７】
複数の物理ページが同一の仮想ページ番号に関連づけられている場合、前記要求仮想ページに対応する前記物理ページは、データが最近書き込まれた前記物理ページである、請求項１６に記載のシステム。
【請求項１８】
前記フラッシュデバイスの少なくとも一部が、書き込むべき空きページ持たず、その部分に対するもう一つの書き込み要求が受信された場合、前記一部の大きさを増加させるために、前記フラッシュデバイスのさらに一部が割り当てられ、その追加の部分の第一のページに、前記書き込み要求のデータが書き込まれる、請求項１４に記載のシステム。
【請求項１９】
特定な時間に、必要ならば、少なくとも一つの仮想ページに対応するデータを新しい位置へコピーすることによって、前記フラッシュデバイスの前記一部を圧縮し、少なくとも一つの物理ページを解放する、請求項１８に記載のシステム。
【請求項２０】
前記フラッシュ管理システムが新しい物理ページを必要とし、そして複数の空きページが所定数よりも少ない場合、前記フラッシュデバイスの前記部分が圧縮される、請求項１９に記載のシステム。
【請求項２１】
圧縮されずに前記部分の大きさが所定数よりも大きくなった場合、前記フラッシュデバイスの前記部分を圧縮する、請求項１９に記載のシステム。
【請求項２２】
ブロック内の順次書き込み処理のみを許容するフラッシュデバイスへ、書き込み処理を行うための書き込み要求を、受信する順序に拘らずに前記書き込み処理を行うための方法であって、
前記フラッシュデバイスの一部へデータを書き込むための書き込み要求を受信すること、なお、前記一部は複数のアドレスを含み、
前記データを書き込むために、前記一部内の以前に書き込んだアドレスに応じて、前記一部内にアドレスの位置を定めること、なお、前記アドレスが、前記以前に書き込んだアドレスに物理的に連続し、そして、
前記書き込み要求の前記データを前記一部に書き込むことからなる方法。
【請求項２３】
前記以前に書き込んだアドレスが、ブロック内における以前に書き込んだページにあり、前記ブロック内に追加のページが利用可能である場合、前記追加のページに前記データが書き込まれ、前記追加のページが、前記以前に書き込んだページよりも高い物理アドレスになる、請求項２２に記載の方法。
【請求項２４】
複数の書き込み要求が受信され、前記ページは、各書き込み要求に対して、各書き込み要求の前記データが、より高い物理アドレスにあるページに書き込まれるように、前記ブロック内に位置決めされる、請求項２３に記載の方法。
【請求項２５】
各物理アドレスが物理ブロック内の物理ページに対応し、前記書き込み要求は、各仮想アドレスが仮想ブロック内の仮想ページに対応する複数の仮想アドレスの少なくとも一つへデータを書き込むためのものであり、前記仮想アドレスが前記物理アドレスにマッピングされる、請求項２４に記載の方法。
【請求項２６】
前記仮想アドレスが、各仮想ブロックを少なくとも一つの物理ブロック内へマッピングすることによって、前記物理アドレスにマッピングされる、請求項２５に記載の方法。
【請求項２７】
複数の仮想アドレスに対する前記複数の書き込み要求がランダムな順番で受信され、書き込むべき前記仮想アドレスがマッピングされた物理ブロックの第一の空き物理ページ内へ、新たに書き込むページの各々を書き込むことによって、複数の書き込み要求のデータが連続的に書き込まれる、請求項２６に記載の方法。
【請求項２８】
物理的に書き込まれたページの各々が、前記仮想ページの前記仮想ブロック内に、対応する仮想ページ番号を伴う、請求項２７に記載の方法。
【請求項２９】
前記仮想ページ番号は、前記フラッシュデバイスからデータを読み取るため、要求仮想ページに対応する最近書き込んだデータを識別する、請求項２８に記載の方法。
【請求項３０】
複数の物理ページが同一の仮想ページ番号を持つ場合、読み取るべき前記物理ページは、最近書き込んだデータを含む前記物理ページである、請求項２９に記載の方法。
【請求項３１】
物理ブロックが、書き込みのために利用可能な物理ページを持たず、そして前記物理ブロックに対応する仮想ブロックに対して書き込み要求が受信された場合、前記仮想ブロックに対して新しい物理ブロックが割り当てられ、前記書き込み要求のデータが前記新しい物理ブロックの第一の物理ページ内へ書き込まれる、請求項２７に記載の方法。
【請求項３２】
さらに、少なくとも一つの物理ブロックを解放する必要がある場合、少なくとも一つの物理ページを新しい物理位置へコピーすることからなる、請求項３１に記載の方法。
【請求項３３】
前記新しい物理位置が、新たに割り当てられた物理ブロック、あるいは前記仮想ブロックの最近割り当てられたブロックである、請求項３２に記載の方法。
【請求項３４】
新しい物理ブロックが必要なとき、そして複数の空き物理ブロックが所定数よりも少ないとき、前記少なくとも一つの物理ページがコピーされる、請求項３２に記載の方法。
【請求項３５】
圧縮されないで仮想ブロックに対応する物理ブロックのグループの大きさが、所定数よりも大きくなったとき、前記少なくとも一つの物理ページがコピーされる、請求項３２に記載の方法。
【請求項３６】
前記所定数が１であり、物理ブロックの前記グループが単に１ブロックのみを含み、前記仮想ブロックが、１対１のマッピングに従って前記物理ブロックにマッピングする、請求項３５に記載の方法。
【請求項３７】
前記仮想アドレスが、各仮想ページを一つ以上の物理ページ内へマッピングすることによって、前記物理アドレスにマッピングされる、請求項２５に記載の方法。
【請求項３８】
複数の仮想アドレスに対する前記複数の書き込み要求がランダムな順番で受信され、書き込むべき仮想アドレスに拘らず、前記物理アドレスの少なくとも一部内における次の空き物理ページ内へ、新たに書き込むページの各々を書き込むことによって、前記複数の書き込み要求のデータが連続的に書き込まれる、請求項３７に記載の方法。
【請求項３９】
前記物理アドレスの前記少なくとも一部が、少なくとも二つの不連続な物理アドレスを含む、請求項３８に記載の方法。
【請求項４０】
物理的に書き込まれたページの各々が、対応する仮想ページ番号を伴う、請求項３８に記載の方法。
【請求項４１】
前記仮想ページ番号が、要求仮想ページに対応する最近書き込まれたデータを識別する、請求項４０に記載の方法。
【請求項４２】
二つの物理ページが同一の仮想ページ番号を持つ場合、前記要求仮想ページに対応する前記物理ページは、データが最近書き込まれた前記物理ページである、請求項４１に記載の方法。
【請求項４３】
前記物理アドレスの前記少なくとも一部が、書き込み要求のデータを書き込むために利用可能なページを持たない場合、前記一部に加えるために新しい部分が割り当てられ、前記データが前記新しい部分の第一のページに書き込まれる、請求項３８に記載の方法。
【請求項４４】
さらに、少なくとも一つの物理ページを解放する必要がある場合、少なくとも一つの物理ページを新しい物理位置へコピーすることからなる、請求項４３に記載の方法。
【請求項４５】
前記新しい物理位置が、新たに割り当てられた物理ブロック内、あるいは前記一部内に既に含まれるブロック内にある、請求項４４に記載の方法。
【請求項４６】
新しい物理ページが必要で、また複数の空き物理ページが所定数よりも少ないとき、前記少なくとも一つの物理ページがコピーされる、請求項４５に記載の方法。
【請求項４７】
圧縮されずに前記一部の大きさが所定数よりも大きくなったとき、前記少なくとも一つの物理ページがコピーされる、請求項４５に記載の方法。
【請求項４８】
書き込んだデータの前記物理位置の連続的な順番を維持するために、少なくとも一つの書き込み要求のデータが、以前に書き込んだデータをコピーすることなく書き込まれる、請求項２２に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、フラッシュデバイスの、より効率的なデータ管理及び保存のためのシステム及び方法に関し、特に、フラッシュデバイスへの情報の保存及び引き出しが、メモリの連続的な物理部分への順次書き込み処理を介して行われるシステム及び方法に関する。
【０００２】
【発明の背景】
フラッシュデバイスは、フラッシュタイプのフローティングゲート・トランジスタから形成した電気的に消去可能な、そしてプログラム可能な読み取り専用メモリ（ＥＥＰＲＯＭ）を含み、機能及び性能においてＥＰＲＯＭメモリに類似する不揮発性メモリであり、メモリの一部を消去するための、回路に組み入れられたプログラム可能な処理を可能にする追加の機能がある。フラッシュデバイスは、従来の保存用磁気ディスクに比べ、安価で、消費電力が少ないという利点がある。しかしながら、フラッシュデバイスでは、メモリの書き込み済み領域を、その領域を先に消去せずに書き直すことは、実際には行われない。フラッシュデバイス内のデータが書き込まれたメモリ領域には、その領域をまず消去しなければデータを書き込むことができないという、フラッシュデバイスのこの制限は、通常の既存のオペレーティング・システムのプログラムとは相容れないものである。
【０００３】
背景技術においては、オペレーティング・システム・プログラムを変更することなく、既存のコンピュータ操作プログラムでフラッシュデバイスを管理できるソフトウェア製品が提案されている。しかし、これらの背景技術プログラムには、すべて欠点がある。例えば、あるプログラムは、フラッシュメモリを「一度の書き込みで何度も読み取る」デバイスとして操作する。この背景技術ソフトウェア製品は、先に書き込んだ記憶位置をリサイクルすることができない。結局すべての位置が書き込まれた場合、ユーザの特定な介入がなければ、これ以上メモリを使用することはできない。背景技術のこれらの欠点を解決するために、米国特許第５，４０４，４８５号にフラッシュ・ファイル・システム（ＦＦＳ）が開示されている。この特許は、本出願と所有者が共通であり、ここに、参照として本文に完全に記載したものとする。ＦＦＳは、フラッシュデバイスへのデータ保存及び処理のためのシステムを提供し、これらのデバイスが磁性ディスクを模倣するようにした。フラッシュデバイスは、先に述べたように、比較的にコストが安価で電力消費量が低いため、特にラップトップ、ポータブル・コンピュータにおけるデータ保存のための選択として好ましい。ＦＦＳは、磁性ディスク記憶装置の代用としてのフラッシュデバイスの機能を向上させる。実に、米国特許第５，４０４，４８５号に開示したＦＦＳは、非常に有用で、データ・レイアウト仕様がＰＣＭＣＩＡ（パソコン・メモリ・カード国際提携）、そしてフラッシュ・トランスレーション・レイヤ（ＦＴＬ）と呼ばれる規格としてＪＥＩＤＡ（日本電子工業振興協会）委員会に採用されている。
【０００４】
ＦＦＳは、本質的に、フラッシュＥＥＰＲＯＭデバイスのための仮想的なマッピングシステムを表す。仮想マップは、フラッシュデバイス内の読み取り／書き込みページの物理アドレスを、そのページの仮想アドレスに関連づける表である。これらのページの各々は、比較的に小さく、５１２バイトであるが、仮想マップ自身のサイズは非常に大きい。ＦＦＳは、また、仮想マップの保存に必要な他のメモリ量を最小にして、フラッシュＥＥＰＲＯＭデバイス上の仮想マップの全体を保存して維持する方法を含む。
【０００５】
上記のように、ＦＦＳは、特に、フラッシュデバイスを磁性ディスク記憶装置の模倣品に変えることに成功したため、産業規格として採用されている。しかし、ＦＦＳは、新しいフラッシュデバイス技術の必要条件の全てを満たすことはできない。ＦＦＳは、特に、ＮＡＮＤ及びＡＮＤフラッシュ技術に関してはそれほどうまく行っていない。したがって、本出願と所有者が同じであり、ここに参照として本文に完全に記載したものとする米国特許第５，９３７，４２５号は、これらの技術に対するフラッシュ管理システムの追加の実施例を開示している。しかしながら、これらの両実施例は、主に、フラッシュメモリの特定なタイプの技術に対して役立つものである。
【０００６】
前記システムを含む典型的なフラッシュ管理システムは、ランダムな順番でユニット内にページを書き込むことが可能であることに依存しているため、これまで空のブロック内へ書き込むべき第一のページが、必ずしも、物理的にも、そのブロック内の第一のページではなく、むしろ中央あるいは終端のページなることがある。このデータ挿入シーケンスは、ランダムな順番で行われる。これは、フラッシュデバイスはブロック内のページの、どのようなページ書き込み順をも許容すると考えられているためである。上記管理システムは、これらのタイプのフラッシュデバイスに対しては非常によく機能する。
【０００７】
このタイプのデータ書き込みメカニズムへの例外は、データのランダムな挿入を避けるフラッシュ管理システムに見られる。これらのシステムは、書き込み処理の各々に対して、新しいブロックを割り当て、この新しいブロックへ既存のブロックから、既に書き込まれているページをコピーし、同時に、その同じブロック内に新しいページを書き込むように処理する。このような方法は、常に連続的に新しいブロックを書き込むことによって、ページ書き込み処理におけるランダムな順番を避けることができるが、ページ書き込み要求それ自体が、ランダムな順で到達する場合、ほぼ全ての書き込み処理に関して新しいブロックを割り当て以前のデータをコピーしなくてはならないため、非常に効率が悪い。したがって、ＦＦＳ等の最も効率的な、現在利用可能なファイル管理システムは、ランダムなページ順で新しいデータを書き込むことに依存している。
【０００８】
しかしながら、フラッシュデバイスは、そのシリコン形状が小型化し続けているため、特性及び作動は、その小さな形状に基づく影響を受けることが増える。特に、書き込みデータのランダムなページ順は、これらの物理的に、よりコンパクトなフラッシュデバイスの処理に対する信頼性を失いつつある。最近、主要なフラッシュ製造業者、東芝（日本）は、０．１６ミクロン処理の技術を用いる次世代ＮＡＮＤフラッシュデバイスが、ランダムなページ順によるデータ挿入ではなく、ブロック内の連続したページ書き込み処理を必要とすることを発表した。これらのデバイスは、市場で広く用いられることが期待されているため、フラッシュメモリ内への順次書き込み処理のみを行う効率的なフラッシュ管理システムを開発する必要がある。
【０００９】
【発明の要約】
背景技術は、順次ページ書き込み処理に制限されたフラッシュデバイスの、効率的な管理のためのメカニズムを教示あるいは示唆していない。さらに、背景技術は、新たに割り当てたブロックにデータを書き込み、同じ処理の一部として、その新しいブロックへ以前に書き込んだページを移動することを必要としないメカニズムを教示あるいは示唆していない。
【００１０】
本発明は、順次ページ書き込み処理に限定されたフラッシュデバイスをサポートするメモリ組織化方法を提供することによって、背景技術のこれらの欠点を克服する。したがって、以前に書き込んだデータの移動を必要とせずに、そして順次書き込み制限を侵害しないで、データをフラッシュデバイスに書き込む。
【００１１】
本発明によれば、下記のものからなるシステムが提供される。（ａ）少なくとも一つのフラッシュデバイスからなるフラッシュメモリ・システム。なお、フラッシュデバイスは、複数のブロックからなるメモリを持ち、各ブロックは複数のページからなる。（ｂ）ページ書き込み要求が受信される順序に拘らず、ページ書き込み要求を管理するフラッシュ管理システム。そして（ｃ）ページ書き込み要求が受信される順序を、書き込み順序へ変換するモジュール。ページ書き込み要求のデータは、ページ書き込み要求の受信順序に拘らず、各ブロック内における物理的に連続したページとして書き込まれる。
【００１２】
以下、用語「物理ユニット」は、消去可能なメモリの最小部分である、メモリの物理メディアあるいはハードウェア上のユニットと定義する。メモリはユニットの整数倍であり、ユニットは、連続なメモリの一部で、大きさが一定で消去可能である。
【００１３】
用語「ページ」は、以下、一つの処理で書き込まれる最小データ量と定義する。用語「ブロック」及び「ユニット」は、物理ユニットと同じ大きさであり、１ブロックが一つ以上のページを含むと定義する。
【００１４】
以下、用語「仮想ユニット」は、物理ユニットと同じ大きさであると定義する。
【００１５】
以下、用語「仮想マップ」は、仮想ブロックあるいはページを、少なくとも一つの対応する物理ブロックあるいはページへ関連づける表を示す。
【００１６】
以下、用語「データを書き込む」は、フラッシュメモリ上にデータを保存する行為を示す。用語「データを読み取る」は、フラッシュメモリからデータを引き出す行為を示す。以下、用語「書き込まれていない」は、書き込まれるデータを保持可能な、物理ブロック等の、メモリのある部分を示す。したがって、用語「書き込まれていない」は、限定せずに、メモリの消去したばかりの部分を含む。
【００１７】
本発明によって組織したフラッシュメモリを持つコンピュータあるいは他の電子装置においては、その装置のオペレーティング・システムは、データの読み取り及び書き込みのために、仮想ユニット及び仮想ページに相互作用する。したがって、仮想ユニット及びページを含む仮想メディアは、オペレーティング・システムがフラッシュメモリ・デバイスに相互作用するためのインタフェースとして機能する。例えば、オペレーティング・システムは、仮想ページへデータを書き込むために、書き込みコマンドを出す。それから、仮想ページを含む仮想ユニットが位置決めされる。それから、仮想マップは、メモリの物理ユニット内に、対応する物理ページの位置を定め、そこに、データが実際に保存される。オペレーティング・システムは、仮想ユニット及び仮想ページがフラッシュメモリの実際のハードウェアであるかのように、読み取り及び書き込みコマンドを出すが、現実は、実際のハードウェアは、フラッシュメモリの物理ユニット及び物理ページに組み込まれている。したがって、オペレーティング・システムは、単に仮想ユニット及びページのみを認識し、ハードウェア自体に直接相互作用しない。このようなインタフェースの利点は、さらに書き込みを行う前に消去処理を行わなければならない等の、フラッシュメモリ固有の欠点を、オペレーティング・システムが物理アドレスではなく仮想アドレスに相互作用することによって克服できるということである。
【００１８】
【好適実施例の説明】
本発明は、フラッシュデバイス・ユニットへ順次書き込み処理のみを行うように制限したフラッシュデバイスを効率良く管理するためのシステム及び方法に関する。書き込み要求の受信後、データ書き込みのためのフラッシュデバイスの物理的な部分を位置決めする。これは、以前に書き込んである物理部分の位置、すなわち、同じブロック内の最後に書き込んだ部分に応じて、この物理部分が、ブロック内で、以前に書き込んである物理部分よりも物理的に高いアドレスを持つように決められる。換言すれば、書き込み処理は、ランダムに選択した位置で行わず、順次書き込み制限を侵害しない位置で行う。この部分は、例えばページ等の、ブロック内の位置であることが好ましい。同じブロック内でページが書き込みに利用できる場合、データはそのページに書き込まれる。この場合も、そのページは、そのブロック内の以前に書き込んであるページよりも高いアドレスに来ることが好ましい。したがって、オプションとして、「連続的に」が、物理的に近接のアドレスに言及することがより好ましいが、この用語は、少なくとも、同じブロック内の以前に書き込んであるどのアドレスよりも高いアドレスを表すことが好ましい。
【００１９】
オプションとして、複数の書き込み要求が受信される場合、その要求がランダムな順番で受信されたとしても、データはランダムに書き込まれないことが好ましい。その代わりに、データは、各物理ユニット内のページの連続的な順番に従って書き込まれることが好ましい。
【００２０】
フラッシュデバイスは、物理アドレスにマッピングされた複数の仮想アドレスを持つことがより好ましい。各物理アドレスは物理ブロック内の物理ページに対応し、各仮想アドレスは仮想ブロック内の仮想ページに対応する。書き込み要求は、物理アドレスへ変換される仮想アドレスへのデータ書き込み要求を含むことが好ましい。オプションとして、仮想アドレスは、各仮想ブロックを一つ以上の物理ブロック内へマッピングすることによって、物理アドレスへマッピングすることが最も好ましい。択一的に、仮想アドレスは、各仮想ページを一つ以上の物理ページへマッピングすることによって、物理アドレスへマッピングすることが最も好ましい。
【００２１】
しかしながら、マッピングのユニットに拘らず、本発明は、書き込まれたデータの物理位置の連続的な順番を維持するために、以前に書き込んであるデータを毎回コピーすることを強いられることはなく、連続的にデータを書き込む処理が可能である。
【００２２】
また、オプションとして、本発明は、少なくとも一つのフラッシュデバイス、そして本発明の上記方法に従って書き込むためのフラッシュデバイスを組織化するフラッシュ管理システムを持つシステムとして具現してもよい。
【００２３】
本発明は、フラッシュデバイスの範囲で説明するが、その意義は、フラッシュデバイスと同じ書き込み、読み取り、そしてユニット消去の特性を持つデータ記憶装置にも適用できることは、本技術に精通した者には明らかである。
【００２４】
本発明によるシステム及び方法の原理及び作用は、図面、そしてその説明文から明確に理解することができる。
【００２５】
さて、図面を参照する。図１は、例えばＮＡＮＤ等の技術による、背景技術である物理ページ・モードフラッシュメモリ・デバイスを概略的に示す。用語「物理デバイス」は、以下、フラッシュメモリ・デバイスの物理メディアを含む実際のハードウェア自体を示す。このような物理メディアは、典型的に、フラッシュＥＥＰＲＯＭユニットから構成されるが、適当な不揮発性プログラマブルメモリ・デバイスで置き換えてもよい。用語「プログラマブル」は、以下、例えばメモリ・デバイスにデータを書き込むこと等によって、変更できることを示す。
【００２６】
フラッシュメモリ物理デバイス１０は、図示のように、少なくとも一つの物理ブロック１２を持つ。物理ブロック１２は、消去可能な物理デバイス１０の最小単位、あるいはその整数倍である。物理ブロック１２は、個々にページ１からｎと定める、整数のページを含む。ｎは整数で、全体としてページ１４と呼ぶ。ページ１４は、ハードウェアの特徴である、物理的なバイト・アドレスの近接するグループから構成される。特に、ページ１４の大きさは、物理デバイス１０の特性による。ユーザ・データは、ページ１４の主要データ領域１６内に保存することができる。各々のページ１４は、また制御データ領域１８を持つ。制御データ領域１８は、典型的に、ページ１４の主な部分から分離したアルゴリズムによってアドレス可能であって、ページ１４の大きさの計算には含めない。さらに下記に説明するが、制御データ領域１８は、フラッシュ・ファイリング・システム自体に関する情報の保存のために便利である。
【００２７】
図２は、基本的なフラッシュメモリ・デバイスを組織化するためのシステムを示す。システム２０は、仮想メディア２２と物理デバイス１０との両方を制御し、仮想マップ２４を介して、仮想メディア２２を物理デバイス１０へ関連づける。仮想メディア２２は複数の仮想ブロック２６を含み、各仮想ブロック２６は複数の仮想ページ２８を持つ。各仮想ブロック２６は仮想アドレスによって指定される。仮想アドレスは、特定の仮想ブロック２６を指定する仮想ブロック番号を含む。各仮想ページ２８は仮想ページ・オフセットによって指定される。同様に、各物理ブロック１２は物理アドレスを持ち、物理アドレスは、特定な物理ブロック１２を指定する物理ブロック番号を含む。各物理ブロック１２は複数の物理ページ１４を持ち、各物理ページ１４は物理ページ・オフセットを持つ。
【００２８】
仮想マップ２４は、少なくとも一つの物理ブロック１２への仮想ブロック２６をマッピングし、択一的に、あるいはさらに、少なくとも一つの物理ページ１４への仮想ページ２８をマッピングする。下記に詳細に説明するが、仮想ブロック２６は物理ブロック１２へマッピングされる、あるいは択一的に、仮想ページ２８は物理ページ１４へマッピングされることが好ましい。これらの二つの代替的なマッピング・システムは、ページあるいはブロックが本発明によるマッピングの基礎を構成するという点で同様である。ページあるいはブロックの基本単位によるマッピングは、連続的にデータを書き込む本発明の方法の処理を変えることはない。
【００２９】
一つの仮想ブロック２６は一つ以上の物理ブロック１２にマッピングすることが可能であり、そして／あるいは一つの仮想ページ２８は一つ以上の物理ページ１４にマッピングすることができることは明らかである。したがって、仮想ブロック２６と物理ブロック１２との対応は、１対１あるいは１対多数であってもよい。
【００３０】
システム２０は次のように機能する。フラッシュメモリ・デバイス（図示せず）を含む電子装置のオペレーティング・システムは、特定の仮想ブロック２６内の特定な仮想ページ２８へ、読み取りコマンドあるいは書き込みコマンド等のコマンドを送信する。仮想マップ２４、あるいは、より好ましくは、仮想マップ２４内に含まれるこれらの機能を行うソフトウェア・モジュールが、次に、物理ブロック１２内の対応する物理ページ１４の位置を定める。しかし、本発明によれば、物理ページ１４は、順次書き込み処理が物理ブロック１２内の物理的に連続なページ１４に対して行われるように、物理ブロック１２内における次の物理的に連続したページ１４である。仮想ページ２８は、仮想ブロック２６内で連続的である必要はなく、実際、ランダムな順番で書き込み処理を受信してもよい。
【００３１】
図３のフローチャートは、本発明による模範的な方法を示す。仮想マップは、少なくとも一つの物理ブロックに各仮想ブロックのマッピングを保存する。フラッシュデバイス（あるいは他のタイプのメモリ）は、メモリの書き込まれていない部分にのみデータを書き込むという特徴を持つと仮定する。この場合、異なるデータをメモリに書き込むことができるように、その前に、書き込まれたメモリの部分を消去しなくてはならない。
【００３２】
マッピングの基本単位は１ブロックであり、各仮想ブロックは一つ以上の物理ブロック内へマッピングされると仮定する。そしてステージ１において、書き込み要求は、データを特定な仮想ページへ書き込む要求を含む。もし少なくとも一つの空きページを持つ対応する物理ブロックの位置を定めることができる（位置判定可能）なら、ステージ２で、対応する物理ブロックの位置を決定する。このステージは、まず、仮想ページを含む仮想ブロックを見つけ、次に、データを書き込むための物理ブロックの位置を定めるために仮想マップを用いることによって行う。次に、ステージ３では、物理ブロック内のページを、その物理ブロック内の、最近データを書き込んだ物理ページの位置に応じて位置決めすることが好ましい。すなわち、選択すべき物理ページは、その物理ブロック内における最近書き込んだ物理ページよりも高いアドレスを持つべきである。一つの可能なアプローチとしては、これに限らないが、選択ページは、オプションとして、その物理ブロック内における最近書き込んだ物理ページに物理的に近接することが好ましい。択一的に、選択ページは、物理的に近接しなくてもよいが、その場合でも、より高いアドレスを持つ。ステージ４では、選択物理ページにデータを書き込む。
【００３３】
仮想ブロック内においてランダムな順番で複数の書き込み要求が受信される場合でも、物理ブロック内では順次ページ書き込み処理のみが行われることが好ましい。したがって、各ページ書き込み要求に対して、データは、そのページに対する書き込み要求がステージ２においてマッピングされた、物理ブロックにおける次の空の物理ページに書き込まれることが好ましい。この場合、次の空の物理ページは、少なくとも、より高いアドレスを持つが、オプションとして、以前に書き込んだページに物理的に近接していることがより好ましい。
【００３４】
オプションとして、物理的に書き込んだページの各々は、物理ページの制御データ領域内に、それに対応する仮想ページ番号が書き込まれる。このような仮想ページ番号は、オプションとして、フラッシュメモリからデータを読み取るための要求仮想ページに対応する、最近書き込んだデータを識別するために用いてもよい。同じ物理ブロック内の複数の物理ページが全く同一の仮想ページ番号を持つ場合は、読み取るべき物理ページは、最近書き込んだデータを含む物理ページであることがより好ましい。複数の物理ページが同一の仮想ページ番号を持つこのような状況は、例えば、オペレーティング・システムが連続的に数回同じ仮想ページに書き込みを求めた場合に起きる可能性がある。各要求は、もう一つの物理ページに書き込むという結果になり、このような物理ページのすべてに関して、同じ仮想ページ番号が与えられる。後にこのページを読み取ろうとするとき、仮想ページ内に保存した最新のデータを得るためには、要求仮想ページ番号を持つページのグループ内における所望の物理ページは、物理ブロック内で最も高いアドレスを持つ物理ページとなる。この物理ページは、本発明の方法に従って最近書き込まれており、したがって最新データを含むページに相違ない。
【００３５】
さて図３に戻る。書き込み要求が受信され、それに対する書き込みに利用可能な物理ページを持つ対応する物理ブロックの位置決定が不可能な場合、フローチャートは、ステージ２Ａ 及び３Ａで示す代替的な行程に進む。仮想ブロックに対して新しい物理ブロックを割り当てることが好ましい（ステージ ２Ａ に示す）。そして、この物理ブロックの第一のページを選択し（ステージ３Ａに示す）、書き込み要求のデータが、ステージ４において、新しい物理ブロックのこの第一の物理ページに書き込まれる。
【００３６】
オプションとして、「圧縮する」、すなわちフラッシュデバイス内の使用保存スペース量を減らすことが好ましく、少なくとも時折行うことがより好ましい。この目的で、少なくとも一つの物理ページの少なくとも最新コピーを、新しい物理位置にコピーして少なくとも一つの物理ユニットを解放することが好ましい。新しい物理位置は、新たに割り当てた物理ブロック内でも、あるいは以前にマッピングした物理ブロック内であってもよい。いずれにしても、このようなコピー処理は、各書き込み処理に対して以前に書き込んだデータのコピーを必要とする背景技術の方法よりも優れていることは明らかである。本発明の方法におけるコピーはオプションであり、各書き込み処理に対して必ず行われるものではない。
【００３７】
例えば、オプションとして、多くの空きスペースが必要な場合、また、空きスペースの量が予め設定した数よりも少ない場合、このコピー処理が行われることが好ましい。この処理は、例えば、空きブロックの数が、ある所定数よりも少ない場合にオプションとして行うことができる。
【００３８】
オプションとして、もう一つの例としては、このコピー処理は、仮想ブロックに対応する物理ブロックのグループの大きさが、所定数よりも大きくなった場合に行うことが好ましい。またオプションとして、この所定数は、物理ブロックのグループが常に１ブロックのみを含むように１に設定され、仮想ブロックが、１対１のマッピングに従って物理ブロックにマッピングされてもよい。
【００３９】
基本マッピング・アイテムとしてブロックではなくページを用いるフラッシュ管理システムにおいて、オプションとして、同様のマッピング方法を行ってもよい。この場合は、仮想ブロックの物理ブロック内へのマッピングを定義することなく、仮想ページが物理ページへマッピングされるが、本発明の範囲内に含まれると考えることができる。このような状況では、また、上記説明のものに類似する方法を採ってもよい。その場合、書き込まれる仮想アドレスに拘らず、適用可能な仮想ユニットに対応する物理ブロックのグループの役割は、フラッシュ物理アドレス空間（近接するしないに拘らず、全アドレス空間あるいはその一部）のサブセットに置き換えることができる。
【００４０】
上記の説明は、単に例として意図したものであり、多くの他の実施例が本発明の範囲内において可能であることは明らかである。
【図面の簡単な説明】
【図１】本発明による物理的なフラッシュメモリ・デバイスの概略図である。
【図２】本発明によるフラッシュメモリ・デバイスを組織化する基本システムを示す図である。
【図３】本発明による模範的な方法を示すフローチャートである。
【図１】
2005505818.tif 000003
【図２】
2005505818.tif 000004
【図３】
2005505818.tif 000005
【国際公開パンフレット】
2005505818.tif 000006
2005505818.tif 000007
2005505818.tif 000008
2005505818.tif 000009
2005505818.tif 000010
2005505818.tif 000011
2005505818.tif 000012
2005505818.tif 000013
2005505818.tif 000014
2005505818.tif 000015
2005505818.tif 000016
2005505818.tif 000017
2005505818.tif 000018
2005505818.tif 000019
2005505818.tif 000020
2005505818.tif 000021
2005505818.tif 000022
2005505818.tif 000023
2005505818.tif 000024
2005505818.tif 000025
2005505818.tif 000026
2005505818.tif 000027
2005505818.tif 000028
2005505818.tif 000029
2005505818.tif 000030
2005505818.tif 000031
2005505818.tif 000032
2005505818.tif 000033
2005505818.tif 000034
【国際調査報告】
2005505818.tif 000035
2005505818.tif 000036