JP4682261B2 - 不揮発性メモリおよびクラスベースの更新ブロック置換規則のための方法 - Google Patents
不揮発性メモリおよびクラスベースの更新ブロック置換規則のための方法 Download PDFInfo
- Publication number
- JP4682261B2 JP4682261B2 JP2009528456A JP2009528456A JP4682261B2 JP 4682261 B2 JP4682261 B2 JP 4682261B2 JP 2009528456 A JP2009528456 A JP 2009528456A JP 2009528456 A JP2009528456 A JP 2009528456A JP 4682261 B2 JP4682261 B2 JP 4682261B2
- Authority
- JP
- Japan
- Prior art keywords
- block
- update
- memory
- blocks
- sector
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
- G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
- G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/72—Details relating to flash memory management
- G06F2212/7202—Allocation control and policies
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Human Computer Interaction (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
- Read Only Memory (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
本発明は、一般的には、不揮発性半導体メモリに関し、さらに詳しくは、データを記憶するために同時に開放中のブロックのプールの置換を管理するための改良されたシステムを伴うメモリブロック管理システムを有するものに関する。
電荷を不揮発的に記憶することができる固体メモリであり、特に、小形形状のファクタカードとしてパッケージ化されたＥＥＰＲＯＭおよびフラッシュＥＥＰＲＯＭの形態を取るものが、最近、様々な移動および携帯装置、とりわけ情報機器および一般消費者向け電子製品における記憶装置の選択肢となってきている。同じく固体メモリであるＲＡＭ（ランダムアクセスメモリ）とは異なり、フラッシュメモリは不揮発性であり、電源を切った後でもその記憶したデータを保持する。また、ＲＯＭ（読み出し専用メモリ）とは異なり、フラッシュメモリは、ディスク記憶装置と同様に書き換え可能である。高いコストにもかかわらず、フラッシュメモリは、大容量記憶装置の利用の際にますます使用されるようになっている。従来の大容量記憶装置は、ハードドライブおよびフロッピーディスクなどの回転磁気媒体に基づき、移動および携帯環境には不適切である。というのは、ディスクドライブはかさばりがちであり、機械的な故障が生じやすく、大きな待ち時間および高電力という要件を有するからである。これらの望ましくない属性により、ディスクをベースとした記憶装置は、ほとんどの移動および携帯の利用において実用的でないものとなっている。他方、フラッシュメモリは、埋め込み形および着脱可能なカードの形態の両方で、小さいサイズ、低電力消費、高速および高い信頼性という特徴が理由で、移動および携帯環境に理想的なほど適している。
フラッシュＥＥＰＲＯＭは、消去可能な不揮発性メモリであること、およびメモリセルに新たなデータを書き込むまたは「プログラム」するという点で、ＥＥＰＲＯＭ（電気的に消去可能でプログラム可能な読み出し専用メモリ）に類似している。両方とも、フローティング（未接続の）導電ゲートを使用し、電界効果トランジスタの構造であり、半導体基板におけるソース領域とドレイン領域と間のチャネル領域を覆って位置している。そして、コントロールゲートがフローティングゲートを覆って設けられる。トランジスタのしきい値電圧特性は、フローティングゲート上に保持された電荷量によって制御される。すなわち、フローティングゲート上の電荷の所定のレベルについて、トランジスタが「オン」に転換されてソース領域とドレイン領域との間が導通することができるようにする前にコントロールゲートに印加されなければならない対応する電圧（しきい値）がある。特に、フラッシュＥＥＰＲＯＭなどのフラッシュメモリは、メモリセルの全ブロックを同時に消去することができる。
フローティングゲートは、ある範囲の電荷を保持することができるので、しきい値電圧ウィンドウ内の任意のしきい値電圧レベルにプログラムすることができる。しきい値電圧ウィンドウのサイズは、装置の最小および最大しきい値レベルによって区切られ、さらにフローティングゲート上にプログラムすることができる電荷の範囲に対応している。しきい値ウィンドウは、一般的には、メモリデバイスの特徴、動作状態、および履歴に依存している。ウィンドウ内の各別個の分解可能なしきい値電圧レベルの範囲は、原則的には、セルの限定的なメモリ状態を指定するために使用されてもよい。しきい値電圧が２つの別個の領域に分割される場合には、各メモリセルは１ビットのデータを記憶することができることになる。同様に、しきい値電圧ウィンドウが２つ以上の別個の領域に分割される場合には、各メモリセルは、１ビット以上のデータを記憶することができることになる。
メモリセルとしての役割を果たすトランジスタは、典型的には、２つの機構のうちの１つによって「プログラムされた」状態にプログラムされる。「熱い電子注入」において、ドレインに印加された高い電圧が基板チャネル領域にわたって電子を加速させる。同時に、コントロールゲートに印加された高い電圧が、熱い電子を薄いゲート誘電体を通ってフローティングゲートへ引き寄せる。「トンネル注入」において、高い電圧が基板に対するコントロールゲートに印加される。このように、電子は、基板から介在フローティングゲートへと引き寄せられる。メモリの状態を変化させるために、メモリセルの最初に消去される電荷蓄積ユニットに電子を注入することによってメモリに対する書き込みを行うことを説明するために、「プログラム」という用語を従来使用してきたが、この用語は、現在では、「書き込み」または［記録する」などといった、より一般的な用語と交換可能に使用されてきている。
メモリデバイスの消去は、数多くの機構によって行われてもよい。例えば、ＥＥＰＲＯＭについて、高い電圧をコントロールゲートに関連した基板に印加して、フローティングゲート内の電子を薄い酸化物層を通じて基板チャネル領域へと通すようにすることによって（すなわち、ファウラー・ノルドハイムトンネル現象）、メモリセルは電気的に消去可能である。典型的には、ＥＥＰＲＯＭは、バイト毎に消去可能である。フラッシュＥＥＰＲＯＭについて、メモリは、すべて一度に電気的に消去可能であるか、または１回につき１つ以上の最小の消去可能なブロックを電気的に消去可能であり、最小の消去可能なブロックは、１つ以上のセクタからなってもよく、各セクタは、５１２バイト以上のデータを記憶してもよい。
メモリデバイスは、典型的には、カードに実装されてもよい１つ以上のメモリチップを備える。各メモリチップは、デコーダまたは消去、書き込み、および読み出し回路のような周辺回路によってサポートされたメモリセルのアレイを備える。より高性能のメモリデバイスは、高機能および高レベルのメモリ動作およびインターフェイスを行うコントローラも搭載されている。
商業的に成功している数多くの不揮発性固体メモリデバイスが現在使用されている。これらのメモリデバイスはフラッシュＥＥＰＲＯＭであってもよく、または他の種類の不揮発性メモリセルを使用してもよい。フラッシュメモリおよびそれを製造するシステムおよび方法の例は、米国特許第５，０７０，０３２号（特許文献１）、第５，０９５，３４４号（特許文献２）、第５，３１５，５４１号（特許文献３）、第５，３４３，０６３号（特許文献４）、および第５，６６１，０５３号（特許文献５）、第５，３１３，４２１号（特許文献６）、および第６，２２２，７６２号（特許文献７）に記載されている。特に、ＮＡＮＤストリング構造のフラッシュメモリデバイスは、米国特許第５，５７０，３１５号（特許文献８）、第５，９０３，４９５号（特許文献９）、第６，０４６，９３５号（特許文献１０）に記載されている。また、不揮発性メモリデバイスは、電荷を蓄積するための誘電体層を有するメモリセルからも製造される。前に説明した導電性のフローティングゲート素子の代わりに、誘電体層が使用される。誘電体蓄積素子を使用するこのようなメモリデバイスは、エイタンらによる「ＮＲＯＭ：新規の局所化されたトラッピング、２ビット不揮発性メモリセル」，米国電子電気学会（ＩＥＥＥ）電子デバイスレター，第２１巻，第１１号，２０００年１１月，５４３〜５４５ページ ("NROM: A Novel Localized Trapping, 2-Bit Nonvolatile Memory Cell", IEEE Electron Device Letter, vol. 21, no. 11, November 2000, pp. 543-545)（非特許文献１）に記載されている。ＯＮＯ誘電体層が、ソースおよびドレイン拡散間のチャネルにわたって延在している。１データビットに対する電荷は、ドレインに隣接する誘電体層にて局在化され、他のデータビットについての電荷は、ソースに隣接する誘電体層にて局在化される。例えば、米国特許第５，７６８，１９２号（特許文献１１）および第６，０１１，７２５号（特許文献１２）は、２つの二酸化シリコン層間に挟まれたトラッピング誘電体を有する不揮発性メモリセルを開示している。多状態のデータ記憶装置は、誘電体内の空間的に別個の電荷蓄積領域のバイナリ状態を別個に読み出すことによって実施される。
読み出しおよびプログラミング性能を改善するために、アレイ内の複数の電荷蓄積素子またはメモリトランジスタが、並列に読み出しまたはプログラムされる。よって、メモリ素子の「ページ」が、一緒に読み出されるか、またはプログラムされる。既存のメモリ構成において、列は、典型的には、いくつかのインターリーブされたページを含むか、または１つのページを構成することもある。あるページのすべてのメモリ素子が、一緒に読み出されるか、またはプログラムされることもある。
フラッシュメモリシステムにおいて、消去動作は、読み出しおよびプログラミング動作よりも非常に長くかかる場合がある。よって、かなりのサイズの消去ブロックがあることが望ましい。このように、消去時間は、メモリセルの大きな集合体にわたって償却される。
フラッシュメモリの性質は、データが消去されたメモリ位置に書き込まれなければならないということに基づいている。ホストからのある論理アドレスのデータを更新すべき場合、１つのやり方は、更新データを同一の物理メモリ位置に書き換えるというものである。すなわち、論理／物理アドレスマッピングは変化しない。しかし、これは、この物理位置を含む消去ブロック全体が最初に消去されてから、更新されたデータで書き換えられなければならないということを意味する。この更新方法は、消去ブロック全体が消去され、かつ書き換えられる必要があるので効率が悪く、更新すべきデータが消去ブロックの小さい部分のみを占める場合には特に効率が悪い。また、メモリブロックの消去リサイクルが高い頻度で生じる結果となり、この種のメモリデバイスの限られた耐久性の観点から望ましくない。
フラッシュメモリシステムの他の問題点は、システム制御およびディレクトリデータと関係がある。データは、様々なメモリ動作の過程で生成かつアクセスされる。よって、効率的な取り扱いおよび素早いアクセスが性能に直接影響を与えることになる。フラッシュメモリは記憶装置用を意図し、かつ不揮発性であるので、フラッシュメモリ内のこの種のデータを保持するのが望ましい。しかし、コントローラとフラッシュメモリとの間の介在ファイル管理システムによって、データは直接にはアクセスすることができない。また、システム制御およびディレクトリデータは、アクティブかつ断片化しがちであり、大規模なブロック消去を伴うシステムへの記憶には役に立たない。従来、この種のデータは、コントローラＲＡＭに設定され、コントローラによる直接アクセスを可能としている。メモリデバイスの電源投入後、コントローラＲＡＭに配置すべき必要なシステム制御およびディレクトリ情報をコンパイルするために、初期化の処理によって、フラッシュメモリを走査することができる。この処理は時間がかかり、フラッシュメモリの容量が増加しているのでいっそうのコントローラＲＡＭの容量が要求される。
米国特許第６，５６７，３０７号（特許文献１３）は、メモ帳としての役割を果たす複数の消去ブロック内に更新データを記録し、また様々なブロック内の有効なセクタを最終的に統合化し、かつこのセクタを論理的な順次順序で再構成した後にセクタを書き換えることを含む大きな消去ブロック内のセクタ更新を扱う方法を開示している。このように、ブロックは、ごくわずかな更新の度に消去され、かつ書き込まれる必要はない。
国際公開特許出願第ＷＯ０３／０２７８２８号（特許文献１４）および国際公開特許出願第ＷＯ００／４９４８８号（特許文献１５）は共に、論理セクタアドレスを区画に分割することを含む、大きな消去ブロック内での更新を扱うメモリシステムを開示している。小さな区画の論理アドレス範囲が、ユーザデータ用の他の区画とは別に、アクティブなシステム制御データ用に確保される。このように、システム制御データを独自の区画内で操作すれば、他の区画内の関連するユーザデータと相互に作用しないことになる。更新は論理セクタレベルであり、書き込みポインタは、書き込むべきブロック内の対応する物理セクタを指す。マッピング情報は、ＲＡＭ内にバッファリングされ、最終的にはメインメモリ内のセクタ割り当てテーブルに記憶される。論理セクタの最新バージョンによって、既存のブロック内のすべての以前のバージョンは廃止されることになり、既存のブロックは、部分的に廃止される。部分的に廃止されたブロックを許容することができる数に維持するために、ガーベッジコレクションが行われる。
従来技術のシステムは、更新データを数多くのブロックに渡って分散させる傾向にあるか、または更新データによって数多くの既存ブロックを部分的に廃止する場合もある。その結果、部分的に廃止されたブロックに対して大量のガーベッジコレクションが必要となることが多く、これは効率的でなく、メモリの早すぎる老化を生じさせる。また、非順次更新に比べて、順次更新を扱う体系化された効率的なやり方がない。
したがって、大容量かつ高性能の不揮発性メモリに対する一般的な要求がある。特に、大きなブロックにおけるメモリ動作を前述した問題なく行うことのできる大容量不揮発性メモリを有するための要求がある。
"NROM: A Novel Localized Trapping, 2-Bit Nonvolatile Memory Cell", IEEE Electron Device Letter, vol. 21, no. 11, November 2000, pp. 543-545
不揮発性メモリシステムは、物理メモリ位置の物理グループに組織化される。各物理グループ（メタブロック）は、一単位として消去可能であり、データの論理グループを記憶するために使用することができる。メモリ管理システムは、論理グループの更新データを記録する専用のメタブロックを割り当てることにより、データの論理グループの更新を行うことができる。更新メタブロックは、更新データを受信した順序で記録し、記録が当初記憶された通りの正確な論理順序であるか（順次）、またはそうでないか（カオス的）についての制限はない。最終的には、更新メタブロックは閉鎖されて、さらに記録することができなくなる。いくつかの処理のうちの１つが生じることになるが、元メタブロックを置換する、正確な順序の一杯となったメタブロックが結局は生じることになる。カオス的な場合には、ディレクトリデータが、頻繁な更新の助けとなるようなやり方で、不揮発性メモリに保持される。このシステムは、複数の論理グループが並行して更新されることをサポートする。
本発明の一特徴により、データを論理グループ毎に更新することができる。よって、論理グループが更新されている最中は、論理ユニットの分配（および更新によって廃止されるメモリユニットの分散）は、その範囲が限定される。これは、論理グループが物理ブロック内に正常に含まれている場合に特に当てはまる。
論理グループの更新中に、典型的には１つまたは２つのブロックが、更新論理ユニットをバッファリングするように割り当てられる必要がある。よって、ガーベッジコレクションは、比較的少ない数のブロックに渡ってのみ行えばよい。カオス的ブロックのガーベッジコレクションは、統合化またはコンパクト化によって行われてもよい。
更新処理の経済性は、順次更新に比較してカオス的（非順次）更新に割り当てられる必要のある追加のブロックがないようにする更新ブロックの一般的な処理において、さらに明らかである。すべての更新ブロックは、順次更新ブロックとして割り当てられ、どの更新ブロックも、カオス的更新ブロックに変更可能である。実際、順次からカオス的への更新ブロックの変更は任意である。
システムリソースの効率的な使用により、複数の論理グループを並行して更新することができる。これは、効率性をさらに増し、オーバーヘッドを減少させる。
本発明の一態様によれば、ブロック管理システムを伴う不揮発性メモリにおいて、データを記録するために同時に開放されている更新ブロックの第１の所定最大数までサポートするシステムのために、改良されたブロック置換手法が実施される。更新ブロックは、主に連続更新ブロックであって、当該連続更新ブロックにおいて、データが論理的に連続した順序で記録されているが、そのブロック数は、データが論理的に連続した順序で記録されないカオス的更新ブロックであることが許容された第２の所定最大数までである。更新ブロックの新規の割り当てによって更新ブロックのプールが第１または第２の所定最大数を超えるような場合にはいつでも、当該制限に従うようにプール内の既存の更新ブロックのうちの１つが閉鎖および削除されることになる。更新ブロックを閉鎖する前に、そのデータは連続ブロックに統合される。この改良された手法は、連続的な更新が過度のカオス的ブロック統合数を生じさせ得る状況を回避するためのものである。これは、連続更新ブロックとカオス的更新ブロックとをそれぞれの置換または統合プールに分離することによって達成される。特に、連続更新によって新規の更新ブロックの割り当てが第１の所定最大数を超える場合には、プール内の最も長時間使用されていない連続更新ブロックが、空きを作るために優先される。
現行システムにおいて、一般的に、ユーザデータと制御データという２つの種類のデータがある。ユーザデータは、ホストからメモリシステムへ、典型的には論理的に連続した順序で送られる。連続更新ブロックは、ホストからの連続書き込み動作を最適に扱うように割り当てられる。ユーザデータは、とりわけ論理データに対する後続の更新がある場合には、論理的に不連続な順序である場合がある。カオス的更新ブロックは、不連続な順序でデータを最適に扱うために作成される。カオス的または不連続データの他のソースとしては、ユーザデータを記憶する過程で生成されるファイルおよびディレクトリ情報などといった、ファイルシステムまたはメモリシステムによって保持される制御データがある。
同時に開放されている更新ブロックの最大数までサポートするという実際上のシステム制限に従う従来の手法は、連続的かカオス的かどうかに関わらず、プール内の最も長時間使用されていない更新ブロックを閉鎖するものであった。
本願の手法は、従来の手法を改良するものであって、基本的には、連続的な書き込み動作中に、新規の割り当て用に空きを作るためにプール内の更新ブロックを閉鎖する必要がある場合には、プール内の最も長時間使用されていない連続更新ブロックが閉鎖される。これにより、連続的な書き込み動作およびランダムな書き込み動作を扱うために様々な更新ブロックを効果的に活用することが確実になる。特に、ホストによる大規模な連続書き込み動作によってＦＡＴおよびディレクトリ情報を含むカオス的更新ブロックを閉鎖せざるを得なくなる場合があるといった非効率な状況を回避する。この大規模な書き込み動作が終わると再び更新されるようなＦＡＴおよびディレクトリ情報を記憶するために、さらなるカオス的ブロックが実質上まもなく作成されることになる。改良された置換ポリシーを作成することによって、置換および統合プールの分離が規定され、開放された連続ブロックまたは開放されたカオス的ブロックとなり得るブロックの連続的な書き込みおよび統合中に、カオス的ブロックを統合する際のさらなるオーバーヘッドを防止して、後続のＦＡＴおよびディレクトリ更新を管理する。
本願の手法を一般的にいうと、更新ブロックが連続または不連続データのいずれを記憶しているか、または、ある予め定められた種類のシステムデータを記憶しているかどうかなどといった属性のセットに基づいて、更新ブロックを分類するものである。限られた数の更新ブロックのプールを実装するにあたって、更新ブロックの各クラスは、当該クラス用にサポートされた最大数を超えるような場合の置換に関する独自の規則を有することになる。
例えば、連続更新ブロックおよび不連続更新ブロックは、２つの異なるクラスである。これら各クラス用の置換規則は同一であり、すなわち、最もアクティブでないものを新規のものに置換する。よって、連続更新ブロックのプールを超えるような場合には、新規のものがプールに導入される前に、プール内の最もアクティブでないものが閉鎖および削除されることになる。不連続更新ブロックのプールについても同様である。
一般的に、各クラスは、他のクラスから独立した独自の置換規則を有する。置換規則の例として、対応するクラスによっては、最も長時間アクセスされていないもの、直近にアクセスされたもの、最も頻繁にアクセスされていないもの、最も頻繁にアクセスされているものなどを置換する。
本発明のさらなる特徴および利点は、添付の図面と共に理解される以下の好ましい実施形態の説明から理解されるだろう。
図１から図２０は、本願の様々な態様が実施されるようなブロック管理を伴うメモリシステムの例を示す。同様のメモリシステムが、Gorobetsらによる「Non-Volatile Memory and Method with Control Data Management 」という米国公開特許出願第２００５／０１４４３６５号（特許文献１６）に記載されている。
図１は、本発明を実施するのに適切なメモリシステムの主要ハードウェアの構成要素を概略的に示す。メモリシステム２０は、典型的には、ホストインターフェイスを通じてホスト１０と共に動作する。メモリシステムは、典型的には、メモリカードの形式を取るか、または埋め込み形メモリシステムである。メモリシステム２０は、動作がコントローラ１００によって制御されるメモリ２００を含む。メモリ２００は、１つ以上の集積回路チップに渡って分散された不揮発性メモリセルの１つ以上のアレイからなる。コントローラ１００は、インターフェイス１１０と、プロセッサ１２０と、オプションのコプロセッサ１２１と、ＲＯＭ１２２（読み出し専用メモリ）と、ＲＡＭ１３０（ランダムアクセスメモリ）と、オプションのプログラム可能な不揮発性メモリ１２４とを含む。インターフェイス１１０は、ある構成要素をコントローラからホストへとインターフェイスさせ、他の構成要素をメモリ２００とインターフェイスさせる。不揮発性ＲＯＭ１２２および／またはオプションの不揮発性メモリ１２４に記憶されたファームウェアは、コントローラ１００の機能を実施するためにプロセッサ１２０に対して符号を提供する。誤り訂正符号は、プロセッサ１２０またはオプションのコプロセッサ１２１によって処理されてもよい。代替の実施形態において、コントローラ１００は、状態マシン（図示せず）によって実施される。さらに他の実施形態において、コントローラ１００は、ホスト内で実施される。
論理および物理ブロック構造
図２は、本発明の好ましい実施形態に係る、セクタ（またはメタブロック）の物理グループに組織化され、コントローラのメモリマネージャによって管理されたメモリを示す。メモリ２００は、メタブロックに組織化され、各メタブロックは、共に消去可能な物理セクタＳ0 ，．．．，ＳN-1 のグループである。
図２は、本発明の好ましい実施形態に係る、セクタ（またはメタブロック）の物理グループに組織化され、コントローラのメモリマネージャによって管理されたメモリを示す。メモリ２００は、メタブロックに組織化され、各メタブロックは、共に消去可能な物理セクタＳ0 ，．．．，ＳN-1 のグループである。
ホスト１０は、ファイルシステムまたはオペレーティングシステムの下でアプリケーションを実行する場合に、メモリ２００にアクセスする。典型的には、ホストシステムは、データを論理セクタ単位でアドレス指定し、例えば、各セクタは、５１２バイトのデータを含んでもよい。また、ホストが、論理クラスタ単位でメモリシステムに対して読み出しまたは書き込みを行うのが通常であり、各クラスタは、１つ以上の論理セクタからなる。ホストシステムによっては、より低いレベルのメモリ管理をホスト側で行うためにオプションのホスト側メモリマネージャが存在する場合がある。多くの場合、読み出しまたは書き込み動作中に、ホスト１０は、実質的に、メモリシステム２０に対してコマンドを発行して、データの論理セクタのストリングを含むセグメントを連続するアドレスと共に読み出しまたは書き込みを行う。
フラッシュメモリ２００のメタブロック内のホスト論理セクタのデータの記憶および検索を管理するために、メモリ側メモリマネージャが、メモリシステム２０のコントローラ１００内で実施される。好ましい実施形態において、メモリマネージャは、メタブロックの消去、読み出し、書き込み動作を管理するための数多くのソフトウェアモジュールを含む。また、メモリマネージャは、フラッシュメモリ２００とコントローラＲＡＭ１３０との間の動作に関連したシステム制御およびディレクトリデータを保持する。
図３Ａ（ｉ）〜（ｉｉｉ）は、本発明の好ましい実施形態に係る、論理グループとメタブロックとの間のマッピングを概略的に示す。物理メモリのメタブロックは、論理グループのデータのＮ個の論理セクタを記憶するためのＮ個の物理セクタを有する。図３Ａ（ｉ）は、論理グループＬＧi からのデータを示し、論理セクタは、連続論理順序０，１，．．．，Ｎ−１である。図３Ａ（ｉｉ）は、同一の論理順序のメタブロック内に記憶されている同じデータを示す。このように記憶される場合に、メタブロックは、「順次」であるといわれる。一般的に、メタブロックは、異なる順序で記憶されたデータを有してもよく、その場合は、メタブロックは、「非順次」または「カオス的」であるといわれる。
論理グループの最小のアドレスと、それがマッピングされるメタブロックの最小アドレスとの間には、オフセットがあることがある。この場合、論理セクタアドレスは、メタブロック内の論理グループの末尾から先頭へ戻るループとして折り返す。例えば、図３Ａ（ｉｉｉ）では、メタブロックは、その最初の位置が論理セクタｋのデータで始まるように記憶する。最終論理セクタＮ−１に達すると、セクタ０に戻り、最終的には、その最終物理セクタに論理セクタｋ−１に関連したデータを記憶する。好ましい実施形態において、メタブロックの最初の物理セクタに記憶されたデータの最初の論理セクタアドレスを識別するといった、任意のオフセットの識別のために、ページタグが使用される。２つのブロックは、ページタグだけが異なる場合、その論理セクタを同様の順序で記憶しているものと考えられる。
図３Ｂは、論理グループとメタブロックと間のマッピングを概略的に示す。各論理グループは、データが現在更新中の少数の論理グループを除いて、固有のメタブロックにマッピングされる。論理グループが更新された後、別のメタブロックにマッピングされてもよい。マッピング情報は、論理／物理ディレクトリのセットに維持され、これについては、詳細に後述する。
メタブロックマッピングに対する他の種類の論理グループも予期される。例えば、可変サイズのメタブロックが、本願と同日にAlan Sinclair によって出願された「Adaptive Metablocks 」という同時継続出願中の共有された米国特許出願（特許文献１７）に開示されている。同時継続出願の開示全体は、本願明細書において参照により援用されている。
本発明の特徴の１つは、システムは単一の論理区画で動作し、メモリシステムの論理アドレス範囲にわたる論理セクタのグループは同一に扱われることである。例えば、システムデータを含むセクタと、ユーザデータを含むセクタとは、論理アドレス空間内のどこにでも分散することができる。
従来技術のシステムとは異なり、高頻度かつ小サイズの更新を伴うデータを含む可能性が高い論理アドレス空間セクタに局在化させるための、システムセクタ（すなわち、ファイル割り当てテーブルに関連するセクタ、ディレクトリ、またはサブディレクトリ）の特別な分割またはゾーニングはない。代わりに、セクタの論理グループを更新するこの手法は、システムセクタに典型的なアクセスパターンおよびファイルデータに典型的なアクセスパターンを効率的に扱うことになる。
図４は、物理メモリにおける構造を含むメタブロックの配列を示す。フラッシュメモリは、一単位として共に消去可能なメモリセルのブロックを備える。このような消去ブロックは、フラッシュメモリの消去の最小単位、またはメモリの最小消去ユニット（ＭＥＵ）である。最小消去ユニットは、メモリのハードウェア設計パラメータであるが、複数のＭＥＵの消去をサポートするメモリシステムによっては、１つ以上のＭＥＵを備える「超ＭＥＵ」を構成することができる。フラッシュＥＥＰＲＯＭについて、ＭＥＵは１つのセクタを備えてもよいが、複数のセクタが好ましい。図に示されている例では、Ｍ個のセクタを有する。好ましい実施形態において、各セクタは、５１２バイトのデータを記憶することができ、ユーザデータ部分と、システムまたはオーバーヘッドデータを記憶するためのヘッダ部分とを有する。メタブロックがＰ個のＭＥＵから構成されている場合には、各ＭＥＵはＭ個のセクタを含み、そして、各メタブロックは、Ｎ＝Ｐ＊Ｍ個のセクタを有することになる。
メタブロックは、システムレベルでは、例えば共に消去可能なセクタといった、メモリ位置のグループを表す。フラッシュメモリの物理アドレス空間は、メタブロックを消去の最小単位とした、メタブロックのセットとして扱われる。本願明細書において「メタブロック」および「ブロック」という用語は、媒体管理のためのシステムレベルにおける消去の最小単位を規定するために類義語として使用され、「最小消去ユニット」またはＭＥＵは、フラッシュメモリの消去の最小単位を示すために使用される。
メタブロックを形成するための最小消去ユニット（ＭＥＵ）のリンク付け
プログラミング速度および消去速度を最大限にするために、複数のＭＥＵにある複数のページの情報が並列にプログラミングされるように、かつ複数のＭＥＵが並列に消去されるようにすることによって、並行処理ができる限り活用される。
プログラミング速度および消去速度を最大限にするために、複数のＭＥＵにある複数のページの情報が並列にプログラミングされるように、かつ複数のＭＥＵが並列に消去されるようにすることによって、並行処理ができる限り活用される。
フラッシュメモリにおいて、ページは、１回の動作で共にプログラムすることができるメモリセルの集まりである。ページは、１つ以上のセクタを備えていてもよい。また、メモリアレイは、１つ以上のプレーンに分割されてもよく、１つのプレーン内の１つのＭＥＵのみが１度にプログラムまたは消去されてもよい。最後に、プレーンは、１つ以上のメモリチップに渡って分散されていてもよい。
フラッシュメモリにおいて、ＭＥＵは、１つ以上のページを備えていてもよい。フラッシュメモリチップ内のＭＥＵは、プレーンに組織化されてもよい。各プレーンからの１つのＭＥＵは並行してプログラムまたは消去されてもよいので、各プレーンから１つのＭＥＵを選択することによって複数のＭＥＵメタブロックを形成するのが得策である（以下の図５Ｂ参照）。
図５Ａは、互いに異なるプレーンの最小消去ユニットのリンク付けから構成されるメタブロックを示す。ＭＢ０，ＭＢ１，．．．などの各メタブロックは、メモリシステムの互いに異なるプレーンからのＭＥＵから構成され、互いに異なるプレーンは、１つ以上のチップにわたって分散されていてもよい。図２に示されているメタブロックリンクマネージャ１７０は、各メタブロックについてのＭＥＵのリンク付けを管理する。各メタブロックは、初期フォーマット処理中に構成され、その構成成分であるＭＥＵを、ＭＥＵのうちの１つに障害があるまで、システムの寿命がある限り保持する。
図５Ｂは、１つの最小消去ユニット（ＭＥＵ）が、メタブロックへのリンク付けのために各プレーンから選択される、一実施形態を示す。
図５Ｂは、１つの最小消去ユニット（ＭＥＵ）が、メタブロックへのリンク付けのために各プレーンから選択される、一実施形態を示す。
図５Ｃは、１つより多くの最小消去ユニット（ＭＥＵ）が、メタブロックへのリンク付けのために各プレーンから選択される、別の実施形態を示す。別の実施形態において、１つより多くのＭＥＵが各プレーンから選択されて超ＭＥＵが形成されてもよい。例えば、超ＭＥＵは、２つのＭＥＵから形成されてもよい。この場合、読み出しまたは書き込み動作について１つより多くのパスを利用してもよい。
ＭＥＵをメタブロックにリンク付けまたは再リンク付けすることは、本願と同日にCarlos Gonzales らによって出願された「Adaptive Deterministic Grouping of Blocks into Multi-Block Structures 」という同時継続出願中の共有された米国特許出願（特許文献１８）に開示されている。同時継続出願の開示全体は、本願明細書において参照により援用されている。
メタブロック管理
図６は、コントローラおよびフラッシュメモリにおいて実施されるようなメタブロック管理システムの概略ブロック図である。メタブロック管理システムは、コントローラ１００において実施された様々な機能モジュールを備え、様々な制御データ（ディレクトリデータを含む）をフラッシュメモリ２００およびコントローラＲＡＭ１３０内に階層的に分散されたテーブルおよびリストに保持する。コントローラ１００内に実装された機能モジュールは、インターフェイスモジュール１１０と、論理／物理アドレス変換モジュール１４０と、更新ブロックマネージャモジュール１５０と、消去ブロックマネージャモジュール１６０と、メタブロックリンクマネージャモジュール１７０とを含む。
図６は、コントローラおよびフラッシュメモリにおいて実施されるようなメタブロック管理システムの概略ブロック図である。メタブロック管理システムは、コントローラ１００において実施された様々な機能モジュールを備え、様々な制御データ（ディレクトリデータを含む）をフラッシュメモリ２００およびコントローラＲＡＭ１３０内に階層的に分散されたテーブルおよびリストに保持する。コントローラ１００内に実装された機能モジュールは、インターフェイスモジュール１１０と、論理／物理アドレス変換モジュール１４０と、更新ブロックマネージャモジュール１５０と、消去ブロックマネージャモジュール１６０と、メタブロックリンクマネージャモジュール１７０とを含む。
インターフェイス１１０により、メタブロック管理システムは、ホストシステムとインターフェイスすることができる。論理／物理アドレス変換モジュール１４０は、論理アドレスをホストから物理メモリ位置へマッピングする。更新ブロックマネージャモジュール１５０は、データの所定の論理グループについて、メモリにおけるデータ更新動作を管理する。消去ブロックマネージャモジュール１６０は、メタブロックの消去動作と、新規の情報を記憶するためのメタブロック割り当てとを管理する。メタブロックリンクマネージャモジュール１７０は、セクタの最小消去可能ブロックのサブグループのリンク付けを管理して、所定のメタブロックを構成する。これらのモジュールの詳細な説明は、それぞれの欄で行う。
動作中に、メタブロック管理システムは、アドレス、制御および状態情報などの制御データを生成して、それと共に動作する。制御データのほとんどが小さなサイズの頻繁に変化するデータであることが多いので、大きなブロック構造のフラッシュメモリ内では簡単かつ効率的に記憶および保持することができない。より静的な制御データを不揮発性フラッシュメモリに記憶させ、より変化するより少ない量の制御データをコントローラＲＡＭに位置づけるという階層的分散手法を使用することで、さらに効率的な更新およびアクセスを行う。電源遮断または障害時には、この手法により、揮発性コントローラＲＡＭ内の制御データは、不揮発性メモリ内の小さなセットの制御データを走査することによって、迅速に再構築することができる。これが可能なのは、本発明が、データの所定の論理グループの予想される動作に関連するブロックの数を制限しているからである。加えて、存続が必要とされる制御データのいくつかは、セクタ毎に更新可能な不揮発性のメタブロックに記憶され、新規のセクタを生じさせる各更新が、以前の更新に代わって記録される。セクタインデックス付け手法を制御データのために使用して、メタブロック内のセクタ毎の更新を追跡する。
不揮発性フラッシュメモリ２００は、比較的静的な大量の制御データを記憶する。これには、グループアドレステーブル（ＧＡＴ）２１０と、カオス的ブロックインデックス（ＣＢＩ）２２０と、消去済みブロックリスト（ＥＢＬ）２３０と、ＭＡＰ２４０とが含まれる。ＧＡＴ２１０は、セクタの論理グループと、その対応するメタブロックとの間のマッピングを追跡する。マッピングは、更新を受けるもの以外は変化しない。ＣＢＩ２２０は、更新中の論理的な非順次セクタのマッピングを追跡する。ＥＢＬ２３０は、消去されたメタブロックのプールを追跡する。ＭＡＰ２４０は、フラッシュメモリ内のすべてのメタブロックの消去状態を示すビットマップである。
揮発性コントローラＲＡＭ１３０は、頻繁に変化およびアクセスされる制御データの小さな部分を記憶する。これには、割り当てブロックリスト（ＡＢＬ）１３４と、クリア済みブロックリスト（ＣＢＬ）１３６とが含まれる。ＡＢＬ１３４は、更新データを記録するためにメタブロックの割り当てを追跡し、ＣＢＬ１３６は、割り当て解除および消去されたメタブロックを追跡する。好ましい実施形態において、ＲＡＭ１３０は、フラッシュメモリ２００に記憶された制御データについてのキャッシュとしての役割を果たす。
更新ブロックマネージャ
（図２に示されている）更新ブロックマネージャ１５０は、論理グループの更新を扱う。本発明の一態様によれば、更新を受けているセクタの各論理グループには、更新データを記録するために、専用の更新メタブロックが割り当てられる。好ましい実施形態において、論理グループの１つ以上のセクタの任意のセグメントが、更新ブロックに記録されることになる。更新ブロックは、順次順序または非順次（カオス的としても知られる）順序のいずれかで更新データを受信するように管理される。カオス的更新ブロックでは、セクタデータを論理グループ内で任意の順序で更新することができ、また個別のセクタの任意の繰り返しがあってもよい。特に、順次更新ブロックは、いずれのデータセクタの移転の必要なく、カオス的更新ブロックになりえる。カオス的データ更新には、ブロックの所定の割り当ては必要ない。任意の論理アドレスでの非順次書き込みが自動的に対処される。よって、従来技術のシステムとは異なり、論理グループの様々な更新セグメントが論理的な順次順序であってもまたは非順次順序であっても、特殊な処理はない。一般的な更新ブロックは、ホストによって要求された順序で様々なセグメントを記憶するために、単に使用されることになる。例えば、ホストシステムデータまたはシステム制御データがカオス的に更新されがちな場合でも、ホストシステムデータに対応する論理アドレス空間の領域を、ホストユーザデータを伴う領域と別々に扱う必要はない。
（図２に示されている）更新ブロックマネージャ１５０は、論理グループの更新を扱う。本発明の一態様によれば、更新を受けているセクタの各論理グループには、更新データを記録するために、専用の更新メタブロックが割り当てられる。好ましい実施形態において、論理グループの１つ以上のセクタの任意のセグメントが、更新ブロックに記録されることになる。更新ブロックは、順次順序または非順次（カオス的としても知られる）順序のいずれかで更新データを受信するように管理される。カオス的更新ブロックでは、セクタデータを論理グループ内で任意の順序で更新することができ、また個別のセクタの任意の繰り返しがあってもよい。特に、順次更新ブロックは、いずれのデータセクタの移転の必要なく、カオス的更新ブロックになりえる。カオス的データ更新には、ブロックの所定の割り当ては必要ない。任意の論理アドレスでの非順次書き込みが自動的に対処される。よって、従来技術のシステムとは異なり、論理グループの様々な更新セグメントが論理的な順次順序であってもまたは非順次順序であっても、特殊な処理はない。一般的な更新ブロックは、ホストによって要求された順序で様々なセグメントを記憶するために、単に使用されることになる。例えば、ホストシステムデータまたはシステム制御データがカオス的に更新されがちな場合でも、ホストシステムデータに対応する論理アドレス空間の領域を、ホストユーザデータを伴う領域と別々に扱う必要はない。
セクタの完全な論理グループのデータは、１つのメタブロック内に論理的な順次順序で記憶されるのが好ましい。このように、記憶された論理セクタに対するインデックスは、予め規定されている。メタブロックが所定の順序で所定の論理グループのすべてのセクタを記憶している場合、これは「変化なし(intact)」といわれる。更新ブロックに関して、更新データを論理的な順次順序で最終的に充填する場合、更新ブロックは、元メタブロックを容易に置換する更新された変化なしのメタブロックとなる。他方、更新ブロックが更新データを、変化なしのブロックとは異なる論理的な順序で充填する場合、更新ブロックは、非順次またはカオス的更新ブロックであり、順序がばらばらのセグメントは、変化なしのブロックと同一の順序で論理グループの更新データが最終的には記憶されるように、さらに処理されなければならない。好ましい場合において、このセグメントは、１つのメタブロック内の論理的な順次順序である。さらなる処理には、元ブロック内の変化していないセクタを伴う更新ブロック内の更新されたセクタを、さらに他の更新メタブロックに統合化することを伴う。統合化された更新ブロックは、その後、論理的な順次順序となり、元ブロックを置換するために使用することができる。何らかの所定の条件下では、統合化処理に先立って、１つ以上のコンパクト化処理がある。コンパクト化処理は、カオス的更新ブロックのセクタを、置換するカオス的更新ブロックに単純に再記録し、同じ論理セクタの以前の更新によって廃止された重複する論理セクタを削除することはない。
更新手法により、複数の更新スレッドを、所定の最大限まで並行して実行することができる。各スレッドは、専用の更新メタブロックを使用して更新を受けている論理グループである。
順次データ更新
ある論理グループに属するデータを最初に更新する場合、論理グループの更新データについての更新ブロックとして、メタブロックが専用に割り当てられる。更新ブロックが割り当てられるのは、コマンドがホストから受信されて、既存のメタブロックがそのすべてのセクタを変化なく記憶している論理グループの１つ以上のセクタのセグメントを書き込む場合である。最初のホスト書き込み動作の場合、データの最初のセグメントが更新ブロックに記録される。各ホスト書き込みは連続論理アドレスを伴う１つ以上のセクタのセグメントであるので、最初の更新は、その性質上常に順次的であることとなる。後続のホスト書き込みでは、同一の論理グループ内の更新セグメントが、ホストから受信された順序で更新ブロックに記録される。ブロックは、順次更新ブロックとして管理され続けるのに対し、関連する論理グループ内でホストによって更新されたセクタは、論理的に順次的であり続ける。この論理グループ内で更新されたすべてのセクタは、このブロックが閉鎖されるか、カオス的更新ブロックに変換されるかのいずれかとなるまで、この順次更新ブロックに書き込まれる。
ある論理グループに属するデータを最初に更新する場合、論理グループの更新データについての更新ブロックとして、メタブロックが専用に割り当てられる。更新ブロックが割り当てられるのは、コマンドがホストから受信されて、既存のメタブロックがそのすべてのセクタを変化なく記憶している論理グループの１つ以上のセクタのセグメントを書き込む場合である。最初のホスト書き込み動作の場合、データの最初のセグメントが更新ブロックに記録される。各ホスト書き込みは連続論理アドレスを伴う１つ以上のセクタのセグメントであるので、最初の更新は、その性質上常に順次的であることとなる。後続のホスト書き込みでは、同一の論理グループ内の更新セグメントが、ホストから受信された順序で更新ブロックに記録される。ブロックは、順次更新ブロックとして管理され続けるのに対し、関連する論理グループ内でホストによって更新されたセクタは、論理的に順次的であり続ける。この論理グループ内で更新されたすべてのセクタは、このブロックが閉鎖されるか、カオス的更新ブロックに変換されるかのいずれかとなるまで、この順次更新ブロックに書き込まれる。
図７Ａは、２つの別個のホスト書き込み動作の結果、順次更新ブロックへ順次順序で書き込まれる論理グループ内のセクタの一例を示し、この論理グループについての元ブロック内の対応するセクタは廃止になる。ホスト書き込み動作＃１において、論理セクタＬＳ５〜ＬＳ８内のデータが更新中である。ＬＳ５’〜ＬＳ８’として更新されたデータは、新規に割り当てられた専用の更新ブロックに記録される。
便宜上、論理グループ内の更新すべき第１のセクタは、第１の物理セクタ位置から開始する専用更新ブロックに記録される。一般的に、更新すべき第１の論理セクタは、必ずしもグループの論理的に第１番目のセクタではないので、論理グループの最初と、更新ブロックの最初との間にはオフセットがあることがある。このオフセットは、図３Ａに関連して前に説明したように、ページタグとして知られている。後続のセクタは、論理的な順次順序で更新される。論理グループの最後のセクタが書き込まれる場合、グループアドレスは折り返して、書き込みシーケンスを、グループの最初のセクタで継続する。
ホスト書き込み動作＃２において、論理セクタＬＳ９〜ＬＳ１２内のデータのセグメントが更新中である。ＬＳ９’〜ＬＳ１２’として更新されたデータは、専用の更新ブロック内の、最後の書き込みが終了した場所に直接続く位置に記録される。２つのホスト書き込みは、更新データが論理的な順次順序で、すなわち、ＬＳ５’〜ＬＳ１２’のようにして、更新ブロックに記録されたようなものとして理解することができる。更新ブロックが順次更新ブロックとみなされるのは、論理的な順次順序で充填されているからである。更新ブロックに記録された更新データによって、元ブロック内の対応するデータが廃止される。
カオス的データ更新
カオス的更新ブロック管理は、関連論理グループ内でホストによって更新された任意のセクタが論理的に非順次の場合に、既存の順次更新ブロックについて開始される。カオス的更新ブロックは、関連する論理グループ内の論理セクタが任意の順序でかつ任意の繰り返し量で更新されてもよいようなデータ更新ブロックの形式を取る。これは、ホストによって書き込まれたセクタが、更新中の論理グループ内の以前書き込んだセクタに対して論理的に非順次である場合に、順次更新ブロックからの変換によって作成される。この論理グループ内のその後の更新されたすべてのセクタは、グループ内の論理セクタアドレスが何であれ、カオス的更新ブロック内の次に使用可能なセクタ位置に書き込まれる。
カオス的更新ブロック管理は、関連論理グループ内でホストによって更新された任意のセクタが論理的に非順次の場合に、既存の順次更新ブロックについて開始される。カオス的更新ブロックは、関連する論理グループ内の論理セクタが任意の順序でかつ任意の繰り返し量で更新されてもよいようなデータ更新ブロックの形式を取る。これは、ホストによって書き込まれたセクタが、更新中の論理グループ内の以前書き込んだセクタに対して論理的に非順次である場合に、順次更新ブロックからの変換によって作成される。この論理グループ内のその後の更新されたすべてのセクタは、グループ内の論理セクタアドレスが何であれ、カオス的更新ブロック内の次に使用可能なセクタ位置に書き込まれる。
図７Ｂは、５つの別個のホスト書き込み動作の結果、カオス的更新ブロックへカオス的順序で書き込まれる論理グループ内のセクタの一例を示し、この論理グループについての元ブロック内の取り替えられたセクタと、カオス的更新ブロック内の複製セクタとは廃止になる。ホスト書き込み動作＃１において、元メタブロックに記憶されている所定の論理グループの論理セクタＬＳ１０〜ＬＳ１１が更新される。更新された論理セクタＬＳ１０’〜ＬＳ１１’は、新規に割り当てられた更新ブロックに記憶される。この点で、更新ブロックは、順次的である。ホスト書き込み動作＃２において、論理セクタＬＳ５〜ＬＳ６がＬＳ５’〜ＬＳ６’に更新されて、更新ブロック内の最終の書き込みに直接続く位置に記録される。これにより、更新ブロックは、順次的からカオス的なものへと変換される。ホスト書き込み動作＃３において、論理セクタＬＳ１０が再び更新中であり、更新ブロックの次の位置にＬＳ１０’’として記録される。この点で、更新ブロック内のＬＳ１０’’は、元ブロック内のＬＳ１０に取って代わる以前の記録内のＬＳ１０’に取って代わる。ホスト書き込み動作＃４において、論理セクタＬＳ１０内のデータは再び更新されて、更新ブロックの次の位置にＬＳ１０’’’として記録される。よって、ＬＳ１０’’’が、論理セクタＬＳ１０についての現在における最新かつ唯一の有効データとなる。ホスト書き込み動作＃５において、論理セクタＬＳ３０内のデータが更新中であり、更新ブロックにＬＳ３０’として記録される。よって、この例は、任意の順序および任意の繰り返しによって、論理グループ内のセクタをカオス的更新ブロックに書き込むことができることを示す。
強制的順次更新
図８は、２つの別個のホスト書き込み動作の結果としての、論理アドレスに不連続性を有する、順次更新ブロックへ順次順序で書き込まれる論理グループ内のセクタの一例を示す。ホスト書き込み＃１において、論理セクタＬＳ５〜ＬＳ８における更新データは、ＬＳ５’〜ＬＳ８’として専用の更新ブロック内に記録される。ホスト書き込み＃２において、論理セクタＬＳ１４〜ＬＳ１６における更新データは、最終の書き込みに続く更新ブロック内にＬＳ１４’〜ＬＳ１６’として記録されている。しかし、ＬＳ８とＬＳ１４との間にアドレスジャンプがあり、ホスト書き込み＃２は、通常、更新ブロックを非順次的にすることになる。アドレスジャンプは重要ではないので、１つのオプションとしては、ホスト書き込み＃２を実行する前に、介在セクタのデータを元ブロックから更新ブロックへコピーすることによってパディング動作（＃２Ａ）をまず行うというものである。このように、更新ブロックの順次的性質が維持される。
図８は、２つの別個のホスト書き込み動作の結果としての、論理アドレスに不連続性を有する、順次更新ブロックへ順次順序で書き込まれる論理グループ内のセクタの一例を示す。ホスト書き込み＃１において、論理セクタＬＳ５〜ＬＳ８における更新データは、ＬＳ５’〜ＬＳ８’として専用の更新ブロック内に記録される。ホスト書き込み＃２において、論理セクタＬＳ１４〜ＬＳ１６における更新データは、最終の書き込みに続く更新ブロック内にＬＳ１４’〜ＬＳ１６’として記録されている。しかし、ＬＳ８とＬＳ１４との間にアドレスジャンプがあり、ホスト書き込み＃２は、通常、更新ブロックを非順次的にすることになる。アドレスジャンプは重要ではないので、１つのオプションとしては、ホスト書き込み＃２を実行する前に、介在セクタのデータを元ブロックから更新ブロックへコピーすることによってパディング動作（＃２Ａ）をまず行うというものである。このように、更新ブロックの順次的性質が維持される。
図９は、本発明の一般的な一実施形態に係る、データの論理グループを更新するための更新ブロックマネージャによる処理を示すフロー図である。更新処理は、以下のステップを含む。
ステップ２６０：メモリはブロックに組織化され、各ブロックは共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものである。
ステップ２６２：データは論理グループに組織化され、各論理グループは、論理ユニットに分割される。
ステップ２６４：標準的な場合、論理グループのすべての論理ユニットは、第１の所定の順序、好ましくは論理的な順次順序に従って、元ブロックのメモリユニットに記憶される。このように、ブロック内の個々の論理ユニットをアクセスするためのインデックスがわかる。
ステップ２７０：データの所定の論理グループ（例えば、ＬＧx ）について、ＬＧx 内で論理ユニットを更新するための要求が行われる（一例として、論理ユニット更新が挙げられる。一般的には、更新は、ＬＧx 内の１つ以上の連続論理ユニットのセグメントとなる）。
ステップ２７２：要求された更新論理ユニットが、ＬＧx の更新の記録専用の第２のブロックに記憶されることになる。記録順序は、第２の順序であり、典型的には、更新が要求された順序に従う。本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。第２の順序によっては、第２のブロックは、順次的なものである場合も、カオス的なものである場合もある。
ステップ２７４：処理がステップ２７０にループバックするにつれて、第２のブロックは、論理ユニットが記録されるように要求し続ける。閉鎖のための所定の条件が具体化すると、第２のブロックは閉鎖されて、さらなる更新を受信しなくなる。この場合、処理は２７６へ進む。
ステップ２７６：閉鎖された第２のブロックが元ブロックと同様の順序でその更新論理ユニットを記録しているかどうかについて決定が行われる。図３Ａに関して説明したように、ページタグ分だけ異なる論理ユニットを記録している場合には、２つのブロックは同様の順序であるとみなされる。２つのブロックが同様の順序である場合は、処理はステップ２８０へ進み、そうでなければ、ステップ２９０において、何らかのガーベッジコレクションを行う必要がある。
ステップ２８０：第２のブロックは第１のブロックと同一の順序なので、第２のブロックは、元ブロックである第１のブロックを置換するために使用される。更新処理は、その後、ステップ２９９で終了する。
ステップ２９０：所定の論理グループの各論理ユニットの最新バージョンが、第２のブロック（更新ブロック）および第１のブロック（元ブロック）から収集される。所定の論理グループの統合化された論理ユニットは、その後、第１のブロックと同様の順序で第３のブロックに書き込まれる。
ステップ２９２：第３のブロック（統合化されたブロック）は第１のブロックと同様の順序であるので、第３のブロックは、元ブロックである第１のブロックを置換するために使用される。更新処理は、その後、ステップ２９９で終了する。
ステップ２９９：閉鎖処理によって変化のない更新ブロックが作成されると、これが所定の論理グループにとっての新規の標準ブロックとなる。論理グループについての更新スレッドは終了される。
ステップ２６０：メモリはブロックに組織化され、各ブロックは共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものである。
ステップ２６２：データは論理グループに組織化され、各論理グループは、論理ユニットに分割される。
ステップ２６４：標準的な場合、論理グループのすべての論理ユニットは、第１の所定の順序、好ましくは論理的な順次順序に従って、元ブロックのメモリユニットに記憶される。このように、ブロック内の個々の論理ユニットをアクセスするためのインデックスがわかる。
ステップ２７０：データの所定の論理グループ（例えば、ＬＧx ）について、ＬＧx 内で論理ユニットを更新するための要求が行われる（一例として、論理ユニット更新が挙げられる。一般的には、更新は、ＬＧx 内の１つ以上の連続論理ユニットのセグメントとなる）。
ステップ２７２：要求された更新論理ユニットが、ＬＧx の更新の記録専用の第２のブロックに記憶されることになる。記録順序は、第２の順序であり、典型的には、更新が要求された順序に従う。本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。第２の順序によっては、第２のブロックは、順次的なものである場合も、カオス的なものである場合もある。
ステップ２７４：処理がステップ２７０にループバックするにつれて、第２のブロックは、論理ユニットが記録されるように要求し続ける。閉鎖のための所定の条件が具体化すると、第２のブロックは閉鎖されて、さらなる更新を受信しなくなる。この場合、処理は２７６へ進む。
ステップ２７６：閉鎖された第２のブロックが元ブロックと同様の順序でその更新論理ユニットを記録しているかどうかについて決定が行われる。図３Ａに関して説明したように、ページタグ分だけ異なる論理ユニットを記録している場合には、２つのブロックは同様の順序であるとみなされる。２つのブロックが同様の順序である場合は、処理はステップ２８０へ進み、そうでなければ、ステップ２９０において、何らかのガーベッジコレクションを行う必要がある。
ステップ２８０：第２のブロックは第１のブロックと同一の順序なので、第２のブロックは、元ブロックである第１のブロックを置換するために使用される。更新処理は、その後、ステップ２９９で終了する。
ステップ２９０：所定の論理グループの各論理ユニットの最新バージョンが、第２のブロック（更新ブロック）および第１のブロック（元ブロック）から収集される。所定の論理グループの統合化された論理ユニットは、その後、第１のブロックと同様の順序で第３のブロックに書き込まれる。
ステップ２９２：第３のブロック（統合化されたブロック）は第１のブロックと同様の順序であるので、第３のブロックは、元ブロックである第１のブロックを置換するために使用される。更新処理は、その後、ステップ２９９で終了する。
ステップ２９９：閉鎖処理によって変化のない更新ブロックが作成されると、これが所定の論理グループにとっての新規の標準ブロックとなる。論理グループについての更新スレッドは終了される。
図１０は、本発明の好ましい実施形態に係る、データの論理グループを更新するための更新ブロックマネージャによる処理を示すフロー図である。更新処理は、以下のステップを含む。
ステップ３１０：データの所定の論理グループ（例えば、ＬＧx ）について、ＬＧx 内で論理セクタを更新するための要求が行われる（一例として、セクタ更新が挙げられる。一般的には、更新は、ＬＧx 内の１つ以上の連続論理セクタのセグメントととなる）。
ステップ３１２：ＬＧx に専用の更新ブロックがまだ存在しない場合、ステップ４１０へ進み、論理グループについて新規の更新スレッドを開始する。これは、論理グループの更新データを記録するのに専用の更新ブロックを割り当てることによって達成されることになる。開放されている更新ブロックが既にあれば、ステップ３１４へ進み、更新ブロックに対する更新セクタの記録を開始する。
ステップ３１４：現在の更新ブロックが既にカオス的（すなわち、非順次的）である場合には、そのままステップ５１０へ進み、要求された更新セクタをカオス的更新ブロックに記録する。現在の更新ブロックが順次的である場合、ステップ３１６へ進み、順次更新ブロックの処理を行う。
ステップ３１６：本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。しかし、論理グループは、最終的にはそのデータを論理的な順次順序でメタブロックに記憶させるので、更新ブロックをできるだけ順次的に維持するのが望ましい。そうすれば、更新ブロックが閉鎖されてさらなる更新ができなくなった場合、ガーベッジコレクションは必要ないので、必要とされる処理が少なくなる。
ステップ３１０：データの所定の論理グループ（例えば、ＬＧx ）について、ＬＧx 内で論理セクタを更新するための要求が行われる（一例として、セクタ更新が挙げられる。一般的には、更新は、ＬＧx 内の１つ以上の連続論理セクタのセグメントととなる）。
ステップ３１２：ＬＧx に専用の更新ブロックがまだ存在しない場合、ステップ４１０へ進み、論理グループについて新規の更新スレッドを開始する。これは、論理グループの更新データを記録するのに専用の更新ブロックを割り当てることによって達成されることになる。開放されている更新ブロックが既にあれば、ステップ３１４へ進み、更新ブロックに対する更新セクタの記録を開始する。
ステップ３１４：現在の更新ブロックが既にカオス的（すなわち、非順次的）である場合には、そのままステップ５１０へ進み、要求された更新セクタをカオス的更新ブロックに記録する。現在の更新ブロックが順次的である場合、ステップ３１６へ進み、順次更新ブロックの処理を行う。
ステップ３１６：本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。しかし、論理グループは、最終的にはそのデータを論理的な順次順序でメタブロックに記憶させるので、更新ブロックをできるだけ順次的に維持するのが望ましい。そうすれば、更新ブロックが閉鎖されてさらなる更新ができなくなった場合、ガーベッジコレクションは必要ないので、必要とされる処理が少なくなる。
要求された更新が更新ブロックの現在の順次順序に従うかどうかについての決定がなされる。更新が順次的に従う場合、ステップ５１０へ進み、順次更新が行われ、更新ブロックは順次的なままである。他方、更新が順次的に従わない（カオス的更新の）場合、他の動作が行われないならば、順次更新ブロックをカオス的なものに変換する。
一実施形態において、状況を守るためにこれ以上何もせず、処理は直接ステップ３７０へ進み、更新ブロックをカオス的なものにする更新が許容される。
一実施形態において、状況を守るためにこれ以上何もせず、処理は直接ステップ３７０へ進み、更新ブロックをカオス的なものにする更新が許容される。
オプションの強制的順次処理
他の実施形態において、強制的順次処理ステップ３２０が、保留中のカオス的更新の観点から順次更新ブロックをできるだけ保存するためにオプションとして行われる。２つの状況があり、どちらも、欠落したセクタを元ブロックからコピーして、更新ブロック上に記録された論理セクタの順次順序を維持するものである。第１の状況は、更新によって短いアドレスジャンプが生じることである。第２の状況は、更新ブロックを順次的に保つために、更新ブロックを早く閉鎖することである。強制的順次処理ステップ３２０は、以下のサブステップを含む。
ステップ３３０：更新によって、所定の量ＣB より大きい論理アドレスジャンプが生じる場合、処理はステップ３５０の強制的順次更新処理へと進み、そうでなければ、処理はステップ３４０へと進んで、強制的順次閉鎖の資格があるかどうかの検討を行う。
ステップ３４０：充填されていない物理セクタ数が、更新ブロックのサイズの半分が典型的な値である所定の設定パラメータＣC を超える場合、更新ブロックは、比較的使用されず、早く閉鎖されることはない。処理はステップ３７０へ進み、更新ブロックは、カオス的となる。他方、更新ブロックがおおむね充填されている場合、既に十分に使っているとみなされるので、ステップ３６０へと進み、強制的順次閉鎖となる。
ステップ３５０：強制的順次更新により、現在の順次更新ブロックを、アドレスジャンプが所定量ＣB を超えない限り順次的なままとすることができる。基本的には、更新ブロックの関連する元ブロックからのセクタがコピーされて、アドレスジャンプによるギャップを埋める。よって、順次更新ブロックは、ステップ５１０へ進んで現在の更新を順次記録する前に、介在アドレス内のデータで埋められることになる。
ステップ３６０：強制的順次閉鎖により、現在の順次的な更新ブロックを、カオス的なものに変換するよりも保留中のカオス的更新によって既におおむね充填されていれば、閉鎖することができる。カオス的または非順次更新は、前述したアドレスジャンプ例外、逆方向アドレス遷移、またはアドレス反復の対象ではなく、順方向アドレス遷移を伴うものとして規定される。順次更新ブロックがカオス的更新によって変換されるのを防止するために、更新ブロックの未書き込みのセクタ位置が、更新ブロックの関連した元の部分的に廃止されたブロックからセクタをコピーすることによって充填される。元ブロックは、その後完全に廃止されて、消去することができる。現在の更新ブロックは、現在では、フルセットの論理セクタを有するので、元メタブロックを置き換える変化のないメタブロックとして閉鎖される。処理は、ステップ４３０へと進み、ステップ３１０において最初に要求された保留中のセクタ更新の記録を受け付けるために、新規の更新ブロックをその位置に割り当てる。
他の実施形態において、強制的順次処理ステップ３２０が、保留中のカオス的更新の観点から順次更新ブロックをできるだけ保存するためにオプションとして行われる。２つの状況があり、どちらも、欠落したセクタを元ブロックからコピーして、更新ブロック上に記録された論理セクタの順次順序を維持するものである。第１の状況は、更新によって短いアドレスジャンプが生じることである。第２の状況は、更新ブロックを順次的に保つために、更新ブロックを早く閉鎖することである。強制的順次処理ステップ３２０は、以下のサブステップを含む。
ステップ３３０：更新によって、所定の量ＣB より大きい論理アドレスジャンプが生じる場合、処理はステップ３５０の強制的順次更新処理へと進み、そうでなければ、処理はステップ３４０へと進んで、強制的順次閉鎖の資格があるかどうかの検討を行う。
ステップ３４０：充填されていない物理セクタ数が、更新ブロックのサイズの半分が典型的な値である所定の設定パラメータＣC を超える場合、更新ブロックは、比較的使用されず、早く閉鎖されることはない。処理はステップ３７０へ進み、更新ブロックは、カオス的となる。他方、更新ブロックがおおむね充填されている場合、既に十分に使っているとみなされるので、ステップ３６０へと進み、強制的順次閉鎖となる。
ステップ３５０：強制的順次更新により、現在の順次更新ブロックを、アドレスジャンプが所定量ＣB を超えない限り順次的なままとすることができる。基本的には、更新ブロックの関連する元ブロックからのセクタがコピーされて、アドレスジャンプによるギャップを埋める。よって、順次更新ブロックは、ステップ５１０へ進んで現在の更新を順次記録する前に、介在アドレス内のデータで埋められることになる。
ステップ３６０：強制的順次閉鎖により、現在の順次的な更新ブロックを、カオス的なものに変換するよりも保留中のカオス的更新によって既におおむね充填されていれば、閉鎖することができる。カオス的または非順次更新は、前述したアドレスジャンプ例外、逆方向アドレス遷移、またはアドレス反復の対象ではなく、順方向アドレス遷移を伴うものとして規定される。順次更新ブロックがカオス的更新によって変換されるのを防止するために、更新ブロックの未書き込みのセクタ位置が、更新ブロックの関連した元の部分的に廃止されたブロックからセクタをコピーすることによって充填される。元ブロックは、その後完全に廃止されて、消去することができる。現在の更新ブロックは、現在では、フルセットの論理セクタを有するので、元メタブロックを置き換える変化のないメタブロックとして閉鎖される。処理は、ステップ４３０へと進み、ステップ３１０において最初に要求された保留中のセクタ更新の記録を受け付けるために、新規の更新ブロックをその位置に割り当てる。
カオス的更新ブロックへの変換
ステップ３７０：保留中の更新が順次順序でなく、オプションとして、強制的順次条件が満たされていない場合、処理がステップ５１０へ進むときに非順次アドレスを有する保留中の更新セクタが更新ブロックへ記録されるようにするために、順次更新ブロックは、カオス的なものに変換されることが許容される。カオス的更新ブロックの最大数が存在する場合に、変換が進む前に、最近最もアクセスされていないカオス的更新ブロックを閉鎖する必要がある。よって、カオス的更新ブロックの最大数が超えないようにする。最近最もアクセスされていないカオス的更新ブロックの識別は、ステップ４２０において説明した一般的な場合と同一であるが、カオス的更新ブロックだけに制約される。このときにカオス的更新ブロックを閉鎖することは、ステップ５５０において説明したような統合化によって達成される。
ステップ３７０：保留中の更新が順次順序でなく、オプションとして、強制的順次条件が満たされていない場合、処理がステップ５１０へ進むときに非順次アドレスを有する保留中の更新セクタが更新ブロックへ記録されるようにするために、順次更新ブロックは、カオス的なものに変換されることが許容される。カオス的更新ブロックの最大数が存在する場合に、変換が進む前に、最近最もアクセスされていないカオス的更新ブロックを閉鎖する必要がある。よって、カオス的更新ブロックの最大数が超えないようにする。最近最もアクセスされていないカオス的更新ブロックの識別は、ステップ４２０において説明した一般的な場合と同一であるが、カオス的更新ブロックだけに制約される。このときにカオス的更新ブロックを閉鎖することは、ステップ５５０において説明したような統合化によって達成される。
システム制約を受ける新規の更新ブロックの割り当て
ステップ４１０：消去メタブロックを更新ブロックとして割り当てる処理は、所定のシステム制約が超えているかどうかを判断することから開始する。リソースは有限であるため、メモリ管理システムは、典型的には、更新ブロックの所定の最大数ＵMAX が並行して存在することを許容する。この制限は、順次更新ブロックとカオス的更新ブロックとの総計であり、設計パラメータである。好ましい実施形態において、この制限は、例えば、最大８つの更新ブロックである。また、システムリソースに対するさらなる高い需要により、並行して開放されているカオス的更新ブロックの最大数に対する対応する所定の制限があってもよい（例えば、４つ）。
よって、ＵMAX 個の更新ブロックが既に割り当てられていれば、次の割り当て要求は、既存の割り当てられたものの１つが閉鎖された後にはじめて満足することができるようになる。処理はステップ４２０へ進む。開放更新ブロックの数がＣA を下回る場合には、処理は直接ステップ４３０へ進む。
ステップ４１０：消去メタブロックを更新ブロックとして割り当てる処理は、所定のシステム制約が超えているかどうかを判断することから開始する。リソースは有限であるため、メモリ管理システムは、典型的には、更新ブロックの所定の最大数ＵMAX が並行して存在することを許容する。この制限は、順次更新ブロックとカオス的更新ブロックとの総計であり、設計パラメータである。好ましい実施形態において、この制限は、例えば、最大８つの更新ブロックである。また、システムリソースに対するさらなる高い需要により、並行して開放されているカオス的更新ブロックの最大数に対する対応する所定の制限があってもよい（例えば、４つ）。
よって、ＵMAX 個の更新ブロックが既に割り当てられていれば、次の割り当て要求は、既存の割り当てられたものの１つが閉鎖された後にはじめて満足することができるようになる。処理はステップ４２０へ進む。開放更新ブロックの数がＣA を下回る場合には、処理は直接ステップ４３０へ進む。
ステップ４２０：更新ブロックＣA の最大数を超える場合には、最近最もアクセスされていない更新ブロックが閉鎖されて、ガーベッジコレクションが行われる。最近最もアクセスされていない更新ブロックは、最近最もアクセスされていない論理ブロックに関連した更新ブロックとして識別される。最近最もアクセスされていないブロックを決定する目的で、アクセスは、論理セクタの書き込みと、オプションで読み出しとを含む。開放更新ブロックのリストが、アクセス順に保持され、初期化の際には、アクセス順序は何ら想定されていない。更新ブロックの閉鎖は、更新ブロックが順次的な場合のステップ３６０および５３０、ならびに更新ブロックがカオス的な場合のステップ５４０に関連して説明したのと同様の処理に従う。閉鎖により、ステップ４３０において新規の更新ブロックを割り当てる空間ができる。
ステップ４３０：割り当て要求は、新規のメタブロックを所定の論理グループＬＧx に専用の更新ブロックとして割り当てることで満足される。その後、処理はステップ５１０へ進む。
ステップ４３０：割り当て要求は、新規のメタブロックを所定の論理グループＬＧx に専用の更新ブロックとして割り当てることで満足される。その後、処理はステップ５１０へ進む。
更新データの更新ブロックへの記録
ステップ５１０：要求された更新セクタは、更新ブロックの次に使用可能な物理位置上に記録される。その後、処理はステップ５２０へ進み、更新ブロックを閉鎖する機が熟したかどうかが判断される。
ステップ５１０：要求された更新セクタは、更新ブロックの次に使用可能な物理位置上に記録される。その後、処理はステップ５２０へ進み、更新ブロックを閉鎖する機が熟したかどうかが判断される。
更新ブロックの閉鎖
ステップ５２０：さらなる更新を受け付けるための空間が更新ブロックにまだある場合には、ステップ５７０へ進む。そうでない場合には、ステップ５２２へ進み、更新ブロックを閉鎖する。現在の要求された書き込みが、ブロックが有する空間よりも多くの論理セクタを書き込もうとするものである場合に、更新ブロックを満たす実装例として２つのものがある。第１の実装例において、書き込み要求は２つの部分に分割され、第１の部分がブロックの最終物理セクタまで書き込む。その後、ブロックは閉鎖され、書き込みの第２の部分が、次に要求された書き込みとして扱われることになる。他方の実装例において、要求された書き込みは、ブロックが残りのセクタが埋め込まれて閉鎖されている間は保留される。要求された書き込みは、次に要求された書き込みとして扱われることになる。
ステップ５２２：更新ブロックが順次的であれば、ステップ５３０へと進み、順次閉鎖となる。更新ブロックがカオス的であれば、ステップ５４０へと進み、カオス的閉鎖となる。
ステップ５２０：さらなる更新を受け付けるための空間が更新ブロックにまだある場合には、ステップ５７０へ進む。そうでない場合には、ステップ５２２へ進み、更新ブロックを閉鎖する。現在の要求された書き込みが、ブロックが有する空間よりも多くの論理セクタを書き込もうとするものである場合に、更新ブロックを満たす実装例として２つのものがある。第１の実装例において、書き込み要求は２つの部分に分割され、第１の部分がブロックの最終物理セクタまで書き込む。その後、ブロックは閉鎖され、書き込みの第２の部分が、次に要求された書き込みとして扱われることになる。他方の実装例において、要求された書き込みは、ブロックが残りのセクタが埋め込まれて閉鎖されている間は保留される。要求された書き込みは、次に要求された書き込みとして扱われることになる。
ステップ５２２：更新ブロックが順次的であれば、ステップ５３０へと進み、順次閉鎖となる。更新ブロックがカオス的であれば、ステップ５４０へと進み、カオス的閉鎖となる。
順次更新ブロックの閉鎖
ステップ５３０：更新ブロックが順次的かつ満杯であるので、そこに記憶された論理グループには変化がない。メタブロックは変化がなく、元のものを置換する。このとき、元ブロックは完全に廃止され、消去されてもよい。その後、処理はステップ５７０へと進み、所定の論理グループに対する更新スレッドは終了する。
ステップ５３０：更新ブロックが順次的かつ満杯であるので、そこに記憶された論理グループには変化がない。メタブロックは変化がなく、元のものを置換する。このとき、元ブロックは完全に廃止され、消去されてもよい。その後、処理はステップ５７０へと進み、所定の論理グループに対する更新スレッドは終了する。
カオス的更新ブロックの閉鎖
ステップ５４０：更新ブロックは非順次的に充填され、いくつかの論理セクタの複数の更新を含む場合もあるので、ガーベッジコレクションが行われて、内部の有効なデータを救い出す。カオス的更新ブロックは、コンパクト化または統合化のいずれかが行われることになる。どちらの処理を行うかは、ステップ５４２において決定される。
ステップ５４２：コンパクト化を行うか、または統合化を行うかは、更新ブロックの重なり具合に依存する。論理セクタが複数回更新されていれば、その論理アドレスは非常に重なっている。更新ブロックに記録された同一の論理セクタの複数のバージョンがあることになり、最後に記録されたバージョンのみが、この論理セクタについて有効なものである。複数のバージョンを有する論理セクタを含む更新ブロックにおいて、別個の論理セクタの数は、論理グループの数よりはるかに少ないことになる。
ステップ５４０：更新ブロックは非順次的に充填され、いくつかの論理セクタの複数の更新を含む場合もあるので、ガーベッジコレクションが行われて、内部の有効なデータを救い出す。カオス的更新ブロックは、コンパクト化または統合化のいずれかが行われることになる。どちらの処理を行うかは、ステップ５４２において決定される。
ステップ５４２：コンパクト化を行うか、または統合化を行うかは、更新ブロックの重なり具合に依存する。論理セクタが複数回更新されていれば、その論理アドレスは非常に重なっている。更新ブロックに記録された同一の論理セクタの複数のバージョンがあることになり、最後に記録されたバージョンのみが、この論理セクタについて有効なものである。複数のバージョンを有する論理セクタを含む更新ブロックにおいて、別個の論理セクタの数は、論理グループの数よりはるかに少ないことになる。
好ましい実施形態において、更新ブロック内の別個の論理セクタの数が、論理グループの大きさの半分が典型的な値である所定の設計パラメータＣD を超える場合には、閉鎖処理はステップ５５０において統合化を行い、そうでなければ、処理はステップ５６０においてコンパクト化を行う。
ステップ５５０：カオス的更新ブロックが統合化されることになる場合、元ブロックと更新ブロックとが、統合化されたデータを含む新規の標準メタブロックに置換されることになる。統合化後、更新スレッドはステップ５７０において終了する。
ステップ５６０：カオス的更新ブロックがコンパクト化されることになる場合、コンパクト化されたデータを保持する新規の更新ブロックに置換されることになる。コンパクト化後、コンパクト化された更新ブロックの処理は、ステップ５７０において終了する。代わりに、更新ブロックが再び書き込まれるまで、コンパクト化を遅らせることもでき、これにより、介在する更新がないのに統合化に続いてコンパクト化が生じる可能性を排除する。新規の更新ブロックは、その後、ＬＧx における更新への次の要求がステップ５０２において生じるときに、所定の論理ブロックのさらなる更新を行う際に使用されることになる。
ステップ５７０：閉鎖処理によって変化のない更新ブロックが作成される場合には、それが所定の論理グループの新規の標準ブロックになる。この論理グループの更新スレッドは終了することになる。閉鎖処理によって既存のものを置換する新規の更新ブロックが作成される場合には、この新規の更新ブロックは、所定の論理グループに対して要求される次の更新を記録するために使用されることになる。更新ブロックが閉鎖されない場合には、処理は、ＬＧx 内の更新に対する次の要求がステップ３１０に生じる場合に継続する。
ステップ５５０：カオス的更新ブロックが統合化されることになる場合、元ブロックと更新ブロックとが、統合化されたデータを含む新規の標準メタブロックに置換されることになる。統合化後、更新スレッドはステップ５７０において終了する。
ステップ５６０：カオス的更新ブロックがコンパクト化されることになる場合、コンパクト化されたデータを保持する新規の更新ブロックに置換されることになる。コンパクト化後、コンパクト化された更新ブロックの処理は、ステップ５７０において終了する。代わりに、更新ブロックが再び書き込まれるまで、コンパクト化を遅らせることもでき、これにより、介在する更新がないのに統合化に続いてコンパクト化が生じる可能性を排除する。新規の更新ブロックは、その後、ＬＧx における更新への次の要求がステップ５０２において生じるときに、所定の論理ブロックのさらなる更新を行う際に使用されることになる。
ステップ５７０：閉鎖処理によって変化のない更新ブロックが作成される場合には、それが所定の論理グループの新規の標準ブロックになる。この論理グループの更新スレッドは終了することになる。閉鎖処理によって既存のものを置換する新規の更新ブロックが作成される場合には、この新規の更新ブロックは、所定の論理グループに対して要求される次の更新を記録するために使用されることになる。更新ブロックが閉鎖されない場合には、処理は、ＬＧx 内の更新に対する次の要求がステップ３１０に生じる場合に継続する。
前述した処理からわかるように、カオス的更新ブロックが閉鎖される場合には、そこに記録された更新データがさらに処理される。特に、その有効データに対しては、他のカオス的ブロックへコンパクト化する処理か、またはその関連する元ブロックに統合化して新たな標準順次ブロックを形成する処理によって、ガーベッジコレクションが行われる。
図１１Ａは、図１０に示されているカオス的更新ブロックを閉鎖する統合化処理をより詳細に示すフロー図である。カオス的更新ブロックの統合化は、更新ブロックが閉鎖されている場合、例えば、更新ブロックが最終物理セクタ位置に書き込みがなされた状態で一杯である場合に行われる、２つの予想される処理のうちの１つである。統合化は、ブロックに書き込まれた別個の論理セクタの数が所定の設計パラメータＣD を超える場合に選ばれる。図１０に示されている統合化処理ステップ５５０は、以下のサブステップを備える。
ステップ５５１：カオス的更新ブロックが閉鎖されている場合に、それを置換する新規のメタブロックが割り当てられることになる。
ステップ５５２：廃止されたセクタはすべて無視して、カオス的更新ブロックおよびその関連する元ブロック内の各論理セクタの最新バージョンを収集する。
ステップ５５４：収集された有効なセクタを新規のメタブロックに論理的な順次順序で記録して、変化のないブロック、すなわち、論理グループのすべての論理セクタが順次順序で記録されているブロックを形成する。
ステップ５５６：元ブロックを新規の変化のないブロックに置換する。
ステップ５５８：閉鎖された更新ブロックおよび元ブロックを消去する。
ステップ５５１：カオス的更新ブロックが閉鎖されている場合に、それを置換する新規のメタブロックが割り当てられることになる。
ステップ５５２：廃止されたセクタはすべて無視して、カオス的更新ブロックおよびその関連する元ブロック内の各論理セクタの最新バージョンを収集する。
ステップ５５４：収集された有効なセクタを新規のメタブロックに論理的な順次順序で記録して、変化のないブロック、すなわち、論理グループのすべての論理セクタが順次順序で記録されているブロックを形成する。
ステップ５５６：元ブロックを新規の変化のないブロックに置換する。
ステップ５５８：閉鎖された更新ブロックおよび元ブロックを消去する。
図１１Ｂは、図１０に示されているカオス的更新ブロックを閉鎖するためのコンパクト化処理をより詳細に示すフロー図である。コンパクト化は、ブロック内の別個の論理セクタの数が所定の設計パラメータＣD を下回る場合に選ばれる。図１０に示されているコンパクト化処理ステップ５６０は、以下のサブステップを備える。
ステップ５６１：カオス的更新ブロックがコンパクト化されている最中に、それを置換する新規のメタブロックが割り当てられる。
ステップ５６２：コンパクト化されるべき既存のカオス的更新ブロック内の各論理セクタの最新バージョンを収集する。
ステップ５６４：収集されたセクタを新規更新ブロックに記録して、コンパクト化されたセクタを有する新規の更新ブロックを形成する。
ステップ５６６：既存の更新ブロックをコンパクト化されたセクタを有する新規の更新ブロックに置換する。
ステップ５６８：閉鎖された更新ブロックを消去する。
ステップ５６１：カオス的更新ブロックがコンパクト化されている最中に、それを置換する新規のメタブロックが割り当てられる。
ステップ５６２：コンパクト化されるべき既存のカオス的更新ブロック内の各論理セクタの最新バージョンを収集する。
ステップ５６４：収集されたセクタを新規更新ブロックに記録して、コンパクト化されたセクタを有する新規の更新ブロックを形成する。
ステップ５６６：既存の更新ブロックをコンパクト化されたセクタを有する新規の更新ブロックに置換する。
ステップ５６８：閉鎖された更新ブロックを消去する。
論理およびメタブロック状態
図１２Ａは、様々な動作下における、論理グループの予想されるすべての状態と、その状態間で予想される遷移とを示す。
図１２Ｂは、論理グループの予想される状態を列挙する表である。論理グループの状態は、以下のように規定される。
１．変化なし：論理グループ内のすべての論理セクタが、論理的な順次順序で、ページタグ折り返しなどを使用して、１つのメタブロックに書き込まれている。
２．未書き込み：論理グループ内の論理セクタが全く書き込まれていない。論理グループは、グループアドレステーブルにおいて未書き込みとして印付けされ、割り当てられたメタブロックはない。このグループ内のすべてのセクタに対するホスト読み出しに応答して、予め定められたデータパターンが返される。
３．順次更新：論理グループ内のいくつかのセクタが、論理的な順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。
４．カオス的更新：論理グループ内のいくつかのセクタが、論理的な非順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。グループ内のセクタは、１回より多く書き込まれてもよく、最新のバージョンが、以前のすべてのバージョンを置換することになる。
図１２Ａは、様々な動作下における、論理グループの予想されるすべての状態と、その状態間で予想される遷移とを示す。
図１２Ｂは、論理グループの予想される状態を列挙する表である。論理グループの状態は、以下のように規定される。
１．変化なし：論理グループ内のすべての論理セクタが、論理的な順次順序で、ページタグ折り返しなどを使用して、１つのメタブロックに書き込まれている。
２．未書き込み：論理グループ内の論理セクタが全く書き込まれていない。論理グループは、グループアドレステーブルにおいて未書き込みとして印付けされ、割り当てられたメタブロックはない。このグループ内のすべてのセクタに対するホスト読み出しに応答して、予め定められたデータパターンが返される。
３．順次更新：論理グループ内のいくつかのセクタが、論理的な順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。
４．カオス的更新：論理グループ内のいくつかのセクタが、論理的な非順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。グループ内のセクタは、１回より多く書き込まれてもよく、最新のバージョンが、以前のすべてのバージョンを置換することになる。
図１３Ａは、様々な動作下における、メタブロックの予想されるすべての状態と、その状態間で予想される遷移とを示す。
図１３Ｂは、メタブロックの予想される状態を列挙する表である。メタブロックの状態は、以下のように規定される。
１．消去済み：メタブロック内のすべてのセクタは消去される。
２．順次更新：メタブロックには、セクタが論理的な順次順序でページタグなどを使用して部分的に書き込まれている。すべてのセクタは、同一の論理グループに属する。
３．カオス的更新：メタブロックには、セクタが論理的な非順次順序で部分的または一杯に書き込まれている。任意のセクタは１回より多く書き込むことができる。すべてのセクタは、同一の論理グループに属する。
４．変化なし：メタブロックは、論理的な順次順序でページタグなどを使用して一杯に書き込まれている。
５．オリジナル：メタブロックは、以前は変化なしであったが、少なくとも１つのセクタがホストデータ更新によって廃止されている。
図１３Ｂは、メタブロックの予想される状態を列挙する表である。メタブロックの状態は、以下のように規定される。
１．消去済み：メタブロック内のすべてのセクタは消去される。
２．順次更新：メタブロックには、セクタが論理的な順次順序でページタグなどを使用して部分的に書き込まれている。すべてのセクタは、同一の論理グループに属する。
３．カオス的更新：メタブロックには、セクタが論理的な非順次順序で部分的または一杯に書き込まれている。任意のセクタは１回より多く書き込むことができる。すべてのセクタは、同一の論理グループに属する。
４．変化なし：メタブロックは、論理的な順次順序でページタグなどを使用して一杯に書き込まれている。
５．オリジナル：メタブロックは、以前は変化なしであったが、少なくとも１つのセクタがホストデータ更新によって廃止されている。
図１４（Ａ）〜１４（Ｊ）は、論理グループの状態と、物理メタブロックとに対する様々な動作の効果を示す状態図である。
図１４（Ａ）は、第１の書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。ホストは、依然未書き込みの論理グループの１つ以上のセクタを、新規に割り当てられた消去済みメタブロックに、論理的な順次順序で書き込む。論理グループおよびメタブロックは、順次更新状態になる。
図１４（Ｂ）は、第１の変化なし動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、すべてのセクタが順次的にホストによって書き込まれると、変化なしとなる。この遷移は、カードが残りの未書き込みのセクタを予め定められたデータパターンで埋めることによって、グループを充填する場合も生じうる。メタブロックは変化なしとなる。
図１４（Ｃ）は、第１のカオス的動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、少なくとも１つのセクタが非順次的にホストによって書き込まれると、カオス的となる。
図１４（Ｄ）は、最初のコンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧ブロックから新規のカオス的メタブロックへコピーされ、旧ブロックは、その後消去される。
図１４（Ｅ）は、最初の統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧カオス的ブロックから移動されて、新規に割り当てられたブロックに論理的な順次順序で充填される。ホストによって書き込みされていないセクタには、予め定められたデータパターンが充填される。旧カオス的ブロックは、その後消去される。
図１４（Ａ）は、第１の書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。ホストは、依然未書き込みの論理グループの１つ以上のセクタを、新規に割り当てられた消去済みメタブロックに、論理的な順次順序で書き込む。論理グループおよびメタブロックは、順次更新状態になる。
図１４（Ｂ）は、第１の変化なし動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、すべてのセクタが順次的にホストによって書き込まれると、変化なしとなる。この遷移は、カードが残りの未書き込みのセクタを予め定められたデータパターンで埋めることによって、グループを充填する場合も生じうる。メタブロックは変化なしとなる。
図１４（Ｃ）は、第１のカオス的動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、少なくとも１つのセクタが非順次的にホストによって書き込まれると、カオス的となる。
図１４（Ｄ）は、最初のコンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧ブロックから新規のカオス的メタブロックへコピーされ、旧ブロックは、その後消去される。
図１４（Ｅ）は、最初の統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧カオス的ブロックから移動されて、新規に割り当てられたブロックに論理的な順次順序で充填される。ホストによって書き込みされていないセクタには、予め定められたデータパターンが充填される。旧カオス的ブロックは、その後消去される。
図１４（Ｆ）は、順次書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。ホストは、変更なしの論理グループの１つ以上のセクタを、論理的な順次順序で、新規に割り当てられた消去済みブロックに書き込む。論理グループおよびメタブロックは、順次更新状態となる。以前変更なしであったメタブロックは、元メタブロックとなる。
図１４（Ｇ）は、順次充填動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、そのすべてのセクタが順次的にホストによって書き込まれる場合に、変化なしとなる。これは、順次更新論理グループを変化無しとするために、元ブロックからの有効なセクタで充填する場合にも生じることがあり、その後、元ブロックは消去される。
図１４（Ｈ）は、非順次書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、少なくとも１つのセクタが非順次的にホストによって書き込まれる場合に、カオス的となる。非順次的セクタの書き込みは、更新ブロック内または対応する元ブロック内のいずれかの有効なセクタを廃止することがあってもよい。
図１４（Ｉ）は、コンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧ブロックから新規のカオス的メタブロックへコピーされて、旧ブロックは、その後消去される。元ブロックは、影響を受けない。
図１４（Ｊ）は、統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧カオス的ブロックおよび元ブロックからコピーされて、新規に割り当てられた消去ブロックは論理的な順次順序で充填される。その後、旧カオス的ブロックおよび元ブロックは消去される。
図１４（Ｇ）は、順次充填動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、そのすべてのセクタが順次的にホストによって書き込まれる場合に、変化なしとなる。これは、順次更新論理グループを変化無しとするために、元ブロックからの有効なセクタで充填する場合にも生じることがあり、その後、元ブロックは消去される。
図１４（Ｈ）は、非順次書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、少なくとも１つのセクタが非順次的にホストによって書き込まれる場合に、カオス的となる。非順次的セクタの書き込みは、更新ブロック内または対応する元ブロック内のいずれかの有効なセクタを廃止することがあってもよい。
図１４（Ｉ）は、コンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧ブロックから新規のカオス的メタブロックへコピーされて、旧ブロックは、その後消去される。元ブロックは、影響を受けない。
図１４（Ｊ）は、統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧カオス的ブロックおよび元ブロックからコピーされて、新規に割り当てられた消去ブロックは論理的な順次順序で充填される。その後、旧カオス的ブロックおよび元ブロックは消去される。
更新ブロックの追跡および管理
図１５は、割り当てのための開放または閉鎖された更新ブロックおよび消去ブロックの状況を追跡するための割り当てブロックリスト（ＡＢＬ）の構造の好ましい実施形態を示す。割り当てブックリスト（ＡＢＬ）６１０は、コントローラＲＡＭ１３０に保持され、消去されたブロックの割り当て、割り当てられた更新ブロック、関連するブロック、および制御構造の管理を行うことができ、また正確な論理／物理アドレス変換を可能にする。好ましい実施形態において、ＡＢＬは、消去済みブロックのリストと、開放更新ブロックリスト６１４と、閉鎖更新ブロックリスト６１６とを含む。
図１５は、割り当てのための開放または閉鎖された更新ブロックおよび消去ブロックの状況を追跡するための割り当てブロックリスト（ＡＢＬ）の構造の好ましい実施形態を示す。割り当てブックリスト（ＡＢＬ）６１０は、コントローラＲＡＭ１３０に保持され、消去されたブロックの割り当て、割り当てられた更新ブロック、関連するブロック、および制御構造の管理を行うことができ、また正確な論理／物理アドレス変換を可能にする。好ましい実施形態において、ＡＢＬは、消去済みブロックのリストと、開放更新ブロックリスト６１４と、閉鎖更新ブロックリスト６１６とを含む。
開放更新ブロックリスト６１４は、開放更新ブロックの属性を伴う、ＡＢＬ内のブロックエントリのセットである。開放更新ブロックリストは、現在開放されている各データ更新ブロック毎に１つのエントリを有する。各エントリは、以下の情報を保持する。ＬＧは、現在の更新メタブロックが専用である論理グループアドレスである。順次／カオス的は、更新ブロックが順次またはカオス的更新データで充填されているかどうかを示す状態である。ＭＢは、更新ブロックのメタブロックアドレスである。ページタグは、更新ブロックの最初の物理位置に記録された開始論理セクタである。書き込まれたセクタ数は、更新ブロックに現在書き込まれたセクタの数を示す。ＭＢ0 は、関連する元ブロックのメタブロックアドレスである。ページタグ0 は、関連する元ブロックのページタグである。
閉鎖更新ブロックリスト６１６は、割り当てブロックリスト（ＡＢＬ）のサブセットである。閉鎖更新ブロックの属性を伴う、ＡＢＬ内のブロックエントリのセットである。閉鎖更新ブロックリストは、閉鎖されたデータ更新ブロック毎に１つのエントリを有するが、そのエントリは、論理的に主要物理ディレクトリに更新されていない。各エントリは、以下の情報を保持する。ＬＧは、現在の更新ブロックが専用である論理グループアドレスである。ＭＢは、更新ブロックのメタブロックアドレスである。ページタグは、更新ブロックの最初の物理位置に記録された開始論理セクタである。ＭＢ0 は、関連する元ブロックのメタブロックアドレスである。
カオス的ブロックのインデックス付け
順次更新ブロックは、論理的に順次順序でデータを記憶しているので、ブロック内の任意の論理セクタは、容易に位置決定することができる。カオス的更新ブロックは、その論理セクタを順序がばらばらに記憶し、論理セクタの複数の更新生成物を記憶してもよい。各有効な論理セクタがカオス的更新ブロックのどこにあるかを追跡するために、追加の情報を保持しなければならない。
順次更新ブロックは、論理的に順次順序でデータを記憶しているので、ブロック内の任意の論理セクタは、容易に位置決定することができる。カオス的更新ブロックは、その論理セクタを順序がばらばらに記憶し、論理セクタの複数の更新生成物を記憶してもよい。各有効な論理セクタがカオス的更新ブロックのどこにあるかを追跡するために、追加の情報を保持しなければならない。
好ましい実施形態において、カオス的ブロックのインデックス付けのデータ構造は、カオス的ブロックにおけるすべての有効なセクタの追跡および高速アクセスを可能にする。カオス的ブロックのインデックス付けは、論理アドレス空間の小さな領域を独立して管理するものであり、システムデータと、ユーザデータのホット領域を効率的に扱う。インデックス付けデータ構造により、性能が大幅な影響を受けないように、本質的にインデックス付け情報が、更新が稀であるという要件でフラッシュメモリ内に保持することができる。他方、カオス的ブロックに現在書き込まれているセクタのリストは、コントローラＲＡＭにおけるカオス的セクタリストに保持される。また、フラッシュメモリからのインデックス情報のキャッシュが、アドレス変換のためのフラッシュセクタアクセス数を最小限にするために、コントローラＲＡＭに保持される。カオス的ブロック毎のインデックスが、フラッシュメモリ内のカオス的ブロックインデック（ＣＢＩ）内に記憶される。
図１６Ａは、カオス的ブロックインデックス（ＣＢＩ）セクタのデータフィールドを示す。カオス的ブロックインデックスセクタ（ＣＢＩセクタ）は、カオス的更新ブロックにマッピングされた論理グループ内のセクタ毎のインデックスを含み、カオス的更新ブロックまたはその関連する元ブロック内の論理グループの各セクタの位置を規定する。ＣＢＩセクタは、カオス的ブロック内の有効セクタを追跡するためのカオスブロックインデックスフィールドと、カオスブロックについてのアドレスパラメータを追跡するためのカオス的ブロック情報フィールドと、ＣＢＩセクタを記憶するメタブロック（ＣＢＩブロック）内の有効なＣＢＩセクタを追跡するためのセクタインデックスフィールドとを含む。
図１６Ｂは、カオス的ブロックインデックス（ＣＢＩ）セクタが専用のメタブロックに記録されている一例を示す。専用のメタブロックを、ＣＢＩブロック６２０と称する。ＣＢＩセクタが更新されると、ＣＢＩブロック６２０内の次に使用可能な物理セクタ位置に書き込まれる。したがって、ＣＢＩセクタの複数のコピーがＣＢＩブロック内に存在し、最後に書き込まれたコピーのみが有効である。例えば、論理グループＬＧ1 についてのＣＢＩセクタは３回更新され、最後に書き込まれたコピーのみが有効なものである。ＣＢＩブロック内の各有効セクタの位置は、ブロック内の最後に書き込まれたＣＢＩセクタ内のインデックスのセットによって識別される。この例において、ブロック内に最後に書き込まれたＣＢＩセクタは、ＬＧ136 についてのＣＢＩセクタであり、そのインデックスのセットは、以前のすべてのものに取って代わる有効なものである。ＣＢＩブロックが最終的にＣＢＩセクタで満杯になると、ブロックは、制御書き込み動作中に、すべての有効セクタを新規のブロック位置に書き換えることによってコンパクト化される。その後、一杯のブロックは、消去される。
ＣＢＩセクタ内のカオス的ブロックインデックスフィールドは、カオス的更新ブロックにマッピングされた論理グループまたはサブグループ内の各論理セクタについてのインデックスエントリを含む。各インデックスエントリは、対応する論理セクタについての有効データが位置するカオス的更新ブロック内のオフセットを示す。予約されたインデックス値は、論理セクタについての有効データがカオス的更新ブロック内に存在しないことを示し、関連する元ブロック内の対応するセクタが有効であることを示す。いくつかのカオス的ブロックインデックスフィールドエントリのキャッシュが、コントローラＲＡＭに保持される。
ＣＢＩセクタ内のカオス的ブロック情報フィールドは、システム内に存在するカオス的更新ブロック毎に１つのエントリを含み、ブロックについてのアドレスパラメータ情報を記録する。このフィールド内の情報は、ＣＢＩブロック内に最後に書き込まれたセクタにおいて有効であるのみである。この情報は、ＲＡＭ内のデータ構造にも存在する。
カオス的更新ブロック毎のエントリは、３つのアドレスパラメータを含む。１つ目は、カオス的更新ブロックに関連する論理グループの論理アドレス（または論理グループ番号）である。２つ目は、カオス的更新ブロックのメタブロックアドレスである。３つ目は、カオス的更新ブロック内に最後に書き込まれたセクタの物理アドレスのオフセットである。オフセット情報は、ＲＡＭ内にデータ構造を再構築するために、初期化中のカオス的更新ブロックの走査のための開始点を設定する。
セクタインデックスフィールドは、ＣＢＩブロックにおける有効ＣＢＩセクタ毎のエントリを含む。各許可されたカオス的更新ブロックに関する最も最近書き込まれたＣＢＩセクタが位置するＣＢＩブロック内のオフセットを規定する。インデックス内のオフセットの予約値は、許可されたカオス的更新ブロックが存在しないことを示す。
図１６Ｃは、カオス的更新を受けている所定の論理グループの論理セクタのデータに対するアクセスを示すフロー図である。更新処理中に、更新データがカオス的更新ブロックに更新データを記録し、変化していないデータは、論理グループに関連する元メタブロック内に留まる。カオス的更新下で論理グループの論理セクタをアクセスする処理は、以下のようである。
ステップ６５０：所定の論理グループの所定の論理セクタの位置決定を開始する。
ステップ６５２：ＣＢＩブロック内の最終書き込みＣＢＩセクタを位置決定する。
ステップ６５４：最終書き込みＣＢＩセクタのカオス的ブロック情報フィールドを検索することによって、所定の論理グループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ６６２の前であればいつでも行うことができる。
ステップ６５８：最終書き込みＣＢＩセクタが所定の論理グループ宛であれば、ＣＢＩセクタは位置決定される。ステップ６６２へ進む。そうでなければ、ステップ６６０へ進む。
ステップ６６０：最終書き込みＣＢＩセクタのセクタインデックスフィールドを検索することによって、所定の論理グループについてのＣＢＩセクタを位置決定する。
ステップ６６２：位置決定されたＣＢＩセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。
ステップ６５０：所定の論理グループの所定の論理セクタの位置決定を開始する。
ステップ６５２：ＣＢＩブロック内の最終書き込みＣＢＩセクタを位置決定する。
ステップ６５４：最終書き込みＣＢＩセクタのカオス的ブロック情報フィールドを検索することによって、所定の論理グループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ６６２の前であればいつでも行うことができる。
ステップ６５８：最終書き込みＣＢＩセクタが所定の論理グループ宛であれば、ＣＢＩセクタは位置決定される。ステップ６６２へ進む。そうでなければ、ステップ６６０へ進む。
ステップ６６０：最終書き込みＣＢＩセクタのセクタインデックスフィールドを検索することによって、所定の論理グループについてのＣＢＩセクタを位置決定する。
ステップ６６２：位置決定されたＣＢＩセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。
図１６Ｄは、論理グループがサブグループに分割されている代替の実施形態に係る、カオス的更新を受けている所定の論理グループの論理セクタのデータに対するアクセスを示すフロー図である。ＣＢＩセクタの容量は有限なので、論理セクタの所定の最大数を追跡することができるのみである。論理グループが単一のＣＢＩセクタが扱えるより多くの論理セクタを有する場合には、論理グループは、ＣＢＩセクタがそれぞれ割り当てられた複数のサブグループに分割される。一例において、各ＣＢＩセクタは、２５６個のセクタと、８個までのカオス的更新ブロックとからなる論理グループを追跡するのに十分な容量を有する。論理グループが２５６セクタを超えるサイズを有する場合には、２５６セクタのサブグループのそれぞれための別個のＣＢＩセクタが論理グループ内に存在する。８個までのサブグループのためのＣＢＩセクタが論理グループ内に存在してもよく、サイズで２０４８個のセクタまでの論理グループに対してサポートを提供する。
好ましい実施形態において、インデックスの管理を促進するために、間接インデックス付け手法が取られる。セクタインデックスの各エントリは、直接および間接フィールドを有する。
好ましい実施形態において、インデックスの管理を促進するために、間接インデックス付け手法が取られる。セクタインデックスの各エントリは、直接および間接フィールドを有する。
直接セクタインデックスは、特定のカオス的更新ブロックに関連するすべての予想されるＣＢＩセクタが位置するＣＢＩブロック内のオフセットを規定する。このフィールドの情報は、最後に書き込まれた、この特定のカオス的更新ブロックに関連するＣＢＩセクタにおいてのみ有効である。インデックス内のオフセットの予約値は、ＣＢＩセクタが存在しないことを示す。というのは、カオス的更新ブロックに関連する対応する論理サブグループが、存在しないか、または更新ブロックが割り当てられて以来更新されていないからである。
間接セクタインデックスは、各許可されたカオス的更新ブロックに関連する最も最近書き込まれたＣＢＩセクタが位置するＣＢＩブロック内のオフセットを規定する。インデックス内のオフセットの予約値は、許可された更新ブロックが存在しないことを示す。
図１６Ｄは、以下のような、カオス的更新下の論理グループの論理セクタをアクセスする処理を示す。
ステップ６７０：各論理グループを複数のサブグループに分割して、ＣＢＩセクタを各サブグループに割り当てる。
ステップ６８０：所定の論理グループの所定のサブグループの所定の論理セクタの位置決定を開始する。
ステップ６８２：ＣＢＩブロック内の最終書き込みＣＢＩセクタを位置決定する。
ステップ６８４：最終書き込みＣＢＩセクタのカオス的ブロック情報フィールドを検索することによって、所定のサブグループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ６９６の前であればいつでも行うことができる。
ステップ６８６：最終書き込みＣＢＩセクタが所定の論理グループ宛である場合には、ステップ６９１へ進む。そうでなければ、ステップ６９０へ進む。
ステップ６９０：最終書き込みＣＢＩセクタの間接セクタインデックスフィールドを検索することによって、所定の論理グループについての複数のＣＢＩセクタの最終書き込みを位置決定する。
ステップ６９１：所定の論理グループについてのサブグループの１つに関連したＣＢＩセクタが少なくとも位置決定されている。続く。
ステップ６９２：位置決定されたＣＢＩセクタが所定のサブグループ宛である場合には、この所定のサブグループについてのＣＢＩセクタが位置決定される。ステップ６９６へ進む。そうでなければ、ステップ６９４へ進む。
ステップ６９４：現在の位置決定されたＣＢＩセクタの直接セクタフィールドを検索することによって、所定のサブグループについてのＣＢＩセクタを位置決定する。
ステップ６９６：所定のサブグループについてのＣＢＩセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。
ステップ６７０：各論理グループを複数のサブグループに分割して、ＣＢＩセクタを各サブグループに割り当てる。
ステップ６８０：所定の論理グループの所定のサブグループの所定の論理セクタの位置決定を開始する。
ステップ６８２：ＣＢＩブロック内の最終書き込みＣＢＩセクタを位置決定する。
ステップ６８４：最終書き込みＣＢＩセクタのカオス的ブロック情報フィールドを検索することによって、所定のサブグループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ６９６の前であればいつでも行うことができる。
ステップ６８６：最終書き込みＣＢＩセクタが所定の論理グループ宛である場合には、ステップ６９１へ進む。そうでなければ、ステップ６９０へ進む。
ステップ６９０：最終書き込みＣＢＩセクタの間接セクタインデックスフィールドを検索することによって、所定の論理グループについての複数のＣＢＩセクタの最終書き込みを位置決定する。
ステップ６９１：所定の論理グループについてのサブグループの１つに関連したＣＢＩセクタが少なくとも位置決定されている。続く。
ステップ６９２：位置決定されたＣＢＩセクタが所定のサブグループ宛である場合には、この所定のサブグループについてのＣＢＩセクタが位置決定される。ステップ６９６へ進む。そうでなければ、ステップ６９４へ進む。
ステップ６９４：現在の位置決定されたＣＢＩセクタの直接セクタフィールドを検索することによって、所定のサブグループについてのＣＢＩセクタを位置決定する。
ステップ６９６：所定のサブグループについてのＣＢＩセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。
図１６Ｅは、各論理グループが複数のサブグループに分割される実施形態についての、カオス的ブロックインデックス付け（ＣＢＩ）セクタおよびその機能の例を示す。論理グループ７００は、その変化のないデータを、元メタブロック７０２内に記憶する。その後、論理グループは、専用のカオス的更新ブロック７０４の割り当てを伴う更新を受ける。この例において、論理グループ７００は、サブグループＡ，Ｂ，Ｃ，Ｄのようなサブグループに分割され、各サブグループは２５６個のセクタを有する。
サブグループＢ内のｉ番目のセクタを位置決定するために、ＣＢＩブロック６２０内の最終書き込みＣＢＩセクタを最初に位置決定する。最終書き込みＣＢＩセクタのカオス的ブロック情報フィールドは、所定の論理グループについてのカオス的更新ブロック７０４を位置決定するためのアドレスを提供する。同時に、これは、カオス的ブロックに書き込まれた最終セクタの位置をも提供する。この情報は、走査および再構築の際に有用である。
最終書き込みＣＢＩセクタが所定の論理グループの４つのＣＢＩセクタのうちの１つであることがわかると、このセクタが確かにｉ番目の論理セクタを含む所定のサブグループＢについてのＣＢＩセクタかどうかをさらに確認することになる。そうであれば、ＣＢＩセクタのカオス的ブロックインデックスは、ｉ番目の論理セクタについてのデータを記憶するメタブロック位置を指すことになる。セクタ位置は、カオス的更新ブロック７０４または元ブロック７０２のいずれかでありうる。
最終書き込みＣＢＩセクタが所定の論理グループの４つのＣＢＩセクタのうちの１つではあるが、正確にはサブグループＢについてのＣＢＩセクタではないことがわかると、その直接セクタインデックスを検索して、サブグループＢについてのＣＢＩセクタを位置決定する。この正確なＣＢＩセクタが位置決定されると、そのカオス的ブロックインデックスを検索して、カオス的更新ブロック７０４および元ブロック７０２の中のｉ番目の論理セクタを位置決定する。
最終書き込みＣＢＩセクタが所定の論理グループの４つのＣＢＩセクタのうちのいずれでもないことがわかると、その間接セクタインデックスを検索して、４つのうちの１つを位置決定する。図１６Ｅに示されている例において、サブグループＣについてのＣＢＩセクタを位置決定する。その後、サブグループＣについてのこのＣＢＩセクタは、その直接セクタインデックスを検索して、サブグループＢについての正確なＣＢＩセクタを位置決定する。図に示されている例では、カオス的ブロックインデックスを検索すると、ｉ番目の論理セクタが変化していないことがわかり、その有効データが元データ内で位置決定される。
同様の検討が、所定の論理グループのサブグループＣ内のｊ番目の論理セクタを位置決定することにも適用される。図に示されている例では、最終書き込みＣＢＩセクタが所定の論理グループの４つのＣＢＩセクタのうちのいずれでもないことがわかる。その間接セクタインデックスは、所定のグループについての４つのＣＢＩセクタのうちの１つを指す。また、４つのうちの指された最終書き込み分は、確かにサブグループＣについてのＣＢＩセクタであることがわかる。そのカオス的ブロックインデックスを検索すると、ｊ番目の論理セクタが、カオス的更新ブロック７０４内の指定された位置に位置決定されることがわかる。
カオス的セクタのリストが、システム内の各カオス的更新ブロックについてのコントローラＲＡＭ内にある。各リストは、関連するＣＢＩセクタがフラッシュメモリ内で最後に更新されたときからの、カオス的更新ブロック内に書き込まれたセクタの記録を含む。特定のカオス的更新ブロックについての論理セクタアドレスの数は、カオス的セクタリスト内に保持することができ、８から１６というのが典型的な値の設計パラメータである。このリストの最適なサイズは、カオス的データ書き込み動作についてのオーバーヘッドに対する影響と、初期化中のセクタ走査時間とを調整して決定される。
システム初期化中に、各カオス的更新ブロックを必要に応じて走査して、関連するＣＢＩセクタのうちの１つについての以前の更新以来書き込まれた有効なセクタを識別する。各カオス的更新ブロックについてのコントローラＲＡＭ内のカオス的セクタリストが構築される。各ブロックは、最終書き込みＣＢＩセクタ内のカオス的ブロック情報フィールドで規定された最終セクタアドレスから走査されればよい。
カオス的更新ブロックが割り当てられると、ＣＢＩセクタが、すべての更新された論理サブグループに対応するように書き込まれる。カオス的更新ブロックについての論理および物理アドレスは、カオス的ブロックインデックスフィールド内の空白エントリと共に、セクタ内の使用可能なカオス的ブロック情報フィールド内に書き込まれる。カオス的セクタリストは、コントローラＲＡＭにおいて開放される。
カオス的更新ブロックが閉鎖されると、ＣＢＩセクタが、セクタ内のカオス的ブロック情報フィールドから除去されたブロックの論理および物理アドレスと共に書き込まれる。ＲＡＭ内の対応するカオス的セクタリストは、使用されなくなる。
カオス的更新ブロックが閉鎖されると、ＣＢＩセクタが、セクタ内のカオス的ブロック情報フィールドから除去されたブロックの論理および物理アドレスと共に書き込まれる。ＲＡＭ内の対応するカオス的セクタリストは、使用されなくなる。
コントローラＲＡＭ内の対応するカオス的セクタリストは、カオス的更新ブロックに書き込まれたセクタの記録を含むように修正される。コントローラＲＡＭ内のカオス的セクタリストが、カオス的更新ブロックに対するさらなるセクタ書き込みの記録について使用可能な空間を有していない場合には、更新されたＣＢＩセクタが、リスト内のセクタに関連する論理サブグループについて書き込まれ、リストはクリアされる。
ＣＢＩブロック６２０が満杯になると、有効なＣＢＩセクタが割り当てられた消去済みブロックにコピーされ、以前のＣＢＩブロックは消去される。
ＣＢＩブロック６２０が満杯になると、有効なＣＢＩセクタが割り当てられた消去済みブロックにコピーされ、以前のＣＢＩブロックは消去される。
アドレステーブル
図２に示されている論理／物理アドレス変換モジュール１４０は、ホストの論理アドレスをフラッシュメモリ内の対応する物理アドレスに関連付ける役割を担う。論理グループと物理グループ（メタブロック）との間のマッピングが、不揮発性フラッシュメモリ２００および揮発性だが動作が速いＲＡＭ１３０（図１参照）に分散されたテーブルおよびリストのセット内に記憶される。アドレステーブルは、フラッシュメモリに保持され、メモリシステム内の各論理グループについてのメタブロックアドレスを含む。加えて、最近書き込まれたセクタについての論理／物理アドレス記録は、ＲＡＭに一時的に保持される。これらの揮発性記録は、電源投入後にシステムを初期化するときに、フラッシュメモリ内のブロックリストおよびデータセクタヘッダから再構築することができる。よって、フラッシュメモリ内のアドレステーブルは、たまに更新されればよく、制御データについてのオーバーヘッド書き込み動作の割合が減ることになる。
図２に示されている論理／物理アドレス変換モジュール１４０は、ホストの論理アドレスをフラッシュメモリ内の対応する物理アドレスに関連付ける役割を担う。論理グループと物理グループ（メタブロック）との間のマッピングが、不揮発性フラッシュメモリ２００および揮発性だが動作が速いＲＡＭ１３０（図１参照）に分散されたテーブルおよびリストのセット内に記憶される。アドレステーブルは、フラッシュメモリに保持され、メモリシステム内の各論理グループについてのメタブロックアドレスを含む。加えて、最近書き込まれたセクタについての論理／物理アドレス記録は、ＲＡＭに一時的に保持される。これらの揮発性記録は、電源投入後にシステムを初期化するときに、フラッシュメモリ内のブロックリストおよびデータセクタヘッダから再構築することができる。よって、フラッシュメモリ内のアドレステーブルは、たまに更新されればよく、制御データについてのオーバーヘッド書き込み動作の割合が減ることになる。
論理グループについてのアドレス記録の階層は、開放更新ブロックリストと、ＲＡＭ内の閉鎖更新ブロックリストと、フラッシュメモリに保持されたグループアドレステーブル（ＧＡＴ）とを含む。
開放更新ブロックリストは、更新されたホストセクタデータについて現在開放されているデータ更新ブロックのコントローラＲＡＭ内のリストである。あるブロックに対するエントリは、ブロックが閉鎖されると、閉鎖更新ブロックリストに移動される。閉鎖更新ブロックリストは、閉鎖されているデータ更新ブロックのコントローラＲＡＭ内のリストである。リスト内のエントリのサブセットは、制御書き込み動作中に、グループアドレステーブル内のセクタに移動される。
開放更新ブロックリストは、更新されたホストセクタデータについて現在開放されているデータ更新ブロックのコントローラＲＡＭ内のリストである。あるブロックに対するエントリは、ブロックが閉鎖されると、閉鎖更新ブロックリストに移動される。閉鎖更新ブロックリストは、閉鎖されているデータ更新ブロックのコントローラＲＡＭ内のリストである。リスト内のエントリのサブセットは、制御書き込み動作中に、グループアドレステーブル内のセクタに移動される。
グループアドレステーブル（ＧＡＴ）は、メモリシステム内のホストデータのすべての論理グループについてのメタブロックアドレスのリストである。ＧＡＴは、論理アドレスに従って順次的に並べられた、論理グループ毎に１つのエントリを含む。ＧＡＴ内のｎ番目のエントリは、アドレスｎの論理グループについてのメタブロックアドレスを含む。好ましい実施形態において、このテーブルは、フラッシュメモリ内にあるテーブルであり、メモリシステム内のすべての論理グループについてのメタブロックアドレスを規定するエントリを伴うセクタ（ＧＡＴセクタと称する）のセットを含む。ＧＡＴセクタは、フラッシュメモリ内の１つ以上の専用制御ブロック（ＧＡＴブロックと称する）内にある。
図１７Ａは、グループアドレステーブル（ＧＡＴ）セクタのデータフィールドを示す。ＧＡＴセクタは、例えば、１２８個の連続する論理グループのセットについてのＧＡＴエントリを含むのに十分な容量を有してもよい。各ＧＡＴセクタは、２つの構成要素、すなわち、ある範囲内の各論理グループのメタブロックアドレスについてのＧＡＴエントリのセットと、ＧＡＴセクタインデックスとを含む。第１の構成要素は、論理アドレスに関連するメタブロックを位置決定するための情報を含む。第２の構成要素は、ＧＡＴブロック内のすべての有効なＧＡＴセクタを位置決定するための情報を含む。各ＧＡＴエントリは、３つのフィールド、すなわち、メタブロック番号と、図３Ａ（ｉｉｉ）に関連して前に規定したようなページタグと、メタブロックが再リンクされたかどうかを示すフラグとを有する。ＧＡＴセクタインデックスは、ＧＡＴブロック内の有効なＧＡＴセクタの位置を列挙する。このインデックスは、各ＧＡＴセクタ内にあるが、ＧＡＴブロック内の次に書き込まれたＧＡＴセクタのバージョンによって取って代わられる。よって、最終書き込みＧＡＴセクタ内のバージョンのみが有効である。
図１７Ｂは、グループアドレステーブル（ＧＡＴ）セクタが１つ以上のＧＡＴブロックに記録されている一例を示す。ＧＡＴブロックは、ＧＡＴセクタを記録する専用のメタブロックである。ＧＡＴセクタが更新される場合には、ＧＡＴブロック７２０内の次に使用可能な物理セクタ位置に書き込まれる。したがって、ＧＡＴセクタの複数のコピーがＧＡＴブロック内に存在することがあり、最後に書き込まれたコピーのみが有効である。例えば、ＧＡＴセクタ４５は、少なくとも２回更新され、最終バージョンが有効なものである。ＧＡＴブロック内の各有効セクタの位置は、ブロック内の最終書き込みＧＡＴセクタ内のインデックスのセットによって識別される。この例において、ブロック内の最終書き込みＧＡＴセクタは、ＧＡＴセクタ５６であり、そのインデックスのセットは、すべての以前のものにとって代わる有効なものである。ＧＡＴブロックが、ＧＡＴセクタで最終的に満杯になった場合には、ブロックは、すべての有効なセクタを新規のブロック位置に書き換えることによって、制御書き込み動作中にコンパクト化される。その後、一杯のブロックは消去される。
前に説明したように、ＧＡＴブロックは、論理アドレス空間のある領域におけるグループの論理的に連続したセットについてのエントリを含む。ＧＡＴブロック内のＧＡＴセクタは、それぞれ、１２８個の連続する論理グループについての論理／物理マッピング情報を含む。ＧＡＴブロックが対象とするアドレス範囲内のすべての論理グループについてのエントリを記憶するのに必要な数多くのＧＡＴセクタは、ブロック内の全セクタ位置のほんのわずかを占めるに過ぎない。したがって、あるＧＡＴセクタは、ブロック内の次に使用可能なセクタ位置に書き込まれることによって更新されてもよい。すべての有効なＧＡＴセクタおよびそれらのＧＡＴブロック内の位置のインデックスが、直近の書き込みＧＡＴセクタ内のインデックスフィールドに保持される。有効なＧＡＴセクタによって占められたＧＡＴブロック内の僅かな合計セクタは、システム設計パラメータであり、典型的には２５％である。しかし、ＧＡＴブロック毎に最大６４個の有効ＧＡＴセクタがある。論理容量が大きいシステムにおいて、１つ以上のＧＡＴブロックにＧＡＴセクタを記憶する必要がある場合がある。この場合、各ＧＡＴブロックは、固定的な範囲の論理グループに関連付けられる。
ＧＡＴ更新は、制御書き込み動作の一部として行われ、割り当てのためのブロックがＡＢＬになくなったときにトリガされる（図１８参照）。これは、ＡＢＬ充填動作およびＣＢＬを空にする動作と並行して行われる。ＧＡＴ更新動作中に、１つのＧＡＴセクタは、閉鎖更新ブロックリスト内の対応するエントリからの情報で更新されたエントリを有する。ＧＡＴエントリが更新されると、対応するエントリはどれでも、閉鎖更新ブロックリスト（ＣＵＢＬ）から除去される。例えば、更新すべきＧＡＴセクタは、閉鎖更新ブロックリスト内の最初のエントリに基づいて選択される。更新されたセクタは、ＧＡＴブロック内の次に使用可能なセクタ位置に書き込まれる。
更新されたＧＡＴセクタに使用可能なセクタ位置がなくなったときに、ＧＡＴ書き換え動作は、制御書き込み動作中に生じる。新たなＧＡＴブロックが割り当てられ、ＧＡＴインデックスによって規定された有効なＧＡＴセクタは、順次順序で一杯のＧＡＴブロックからコピーされる。その後、一杯のＧＡＴブロックは消去される。
ＧＡＴキャッシュは、ＧＡＴセクタ内の１２８個のエントリの再分割部分内のエントリの、コントローラＲＡＭ１３０内のコピーである。ＧＡＴキャッシュエントリの数は、システム設計パラメータであり、典型的な値は３２である。該当セクタの再分割部分についてのＧＡＴキャッシュは、エントリがＧＡＴセクタから読み出される度に作成される。複数のＧＡＴキャッシュが保持される。その数は、設計パラメータであり、典型的な値は４である。ＧＡＴキャッシュは、最近最も使用されていないことに基づいて、異なるセクタの再分割部分についてのエントリで上書きされる。
消去済みメタブロックの管理
図２に示されている消去ブロックマネージャ１６０は、ディレクトリおよびシステム制御情報を保持するためのリストのセットを使用して、消去ブロックを管理する。これらのリストは、コントローラＲＡＭ１３０およびフラッシュメモリ２００に分散されている。消去されたメタブロックがユーザデータの記憶のため、またはシステム制御データ構造の記憶のために割り当てられなければならない場合には、コントローラＲＡＭに保持された割り当てブロックリスト（ＡＢＬ）（図１５参照）内の次に使用可能なメタブロック番号が選択される。同様に、メタブロックが廃棄後に消去される場合には、その番号が、同じくコントローラＲＡＭに保持されたクリア済みブロックリスト（ＣＢＬ）に追加される。比較的静的なディレクトリおよびシステム制御データが、フラッシュメモリ内に記憶される。これらには、消去済みブロックリストと、フラッシュメモリ内のすべてのメタブロックの消去された状態のビットマップ（ＭＡＰ）リストとが含まれる。消去済みブロックリストおよびＭＡＰは、個別のセクタに記憶され、ＭＡＰブロックとして知られる専用のメタブロックに記録される。これらのリストは、コントローラＲＡＭおよびフラッシュメモリに分散されて、消去済みメタブロックの使用を効率的に管理するための消去済みブロック記録の階層を提供する。
図２に示されている消去ブロックマネージャ１６０は、ディレクトリおよびシステム制御情報を保持するためのリストのセットを使用して、消去ブロックを管理する。これらのリストは、コントローラＲＡＭ１３０およびフラッシュメモリ２００に分散されている。消去されたメタブロックがユーザデータの記憶のため、またはシステム制御データ構造の記憶のために割り当てられなければならない場合には、コントローラＲＡＭに保持された割り当てブロックリスト（ＡＢＬ）（図１５参照）内の次に使用可能なメタブロック番号が選択される。同様に、メタブロックが廃棄後に消去される場合には、その番号が、同じくコントローラＲＡＭに保持されたクリア済みブロックリスト（ＣＢＬ）に追加される。比較的静的なディレクトリおよびシステム制御データが、フラッシュメモリ内に記憶される。これらには、消去済みブロックリストと、フラッシュメモリ内のすべてのメタブロックの消去された状態のビットマップ（ＭＡＰ）リストとが含まれる。消去済みブロックリストおよびＭＡＰは、個別のセクタに記憶され、ＭＡＰブロックとして知られる専用のメタブロックに記録される。これらのリストは、コントローラＲＡＭおよびフラッシュメモリに分散されて、消去済みメタブロックの使用を効率的に管理するための消去済みブロック記録の階層を提供する。
図１８は、消去済みブロックの使用およびリサイクルのための制御およびディレクトリ情報の分配および流れを示す概略ブロック図である。制御およびディレクトリデータは、コントローラＲＡＭ１３０内か、フラッシュメモリ２００内に常駐するＭＡＰブロック７５０内のいずれかに保持されるリストに保持される。
好ましい実施形態において、コントローラＲＡＭ１３０は、割り当てブロックリスト（ＡＢＬ）６１０と、クリア済みブロックリスト（ＣＢＬ）７４０とを保持する。図１５に関連して前に説明したように、割り当てブロックリスト（ＡＢＬ）は、ユーザデータの記憶のため、またはシステム制御データ構造の記憶のために最近割り当てられたのがどのメタブロックかを追跡する。新規の消去済みメタブロックを割り当てる必要がある場合には、割り当てブロックリスト（ＡＢＬ）内の次に使用可能なメタブロック番号が選択される。同様に、クリア済みブロックリスト（ＣＢＬ）を使用して、割り当て解除および消去された更新メタブロックを追跡する。ＡＢＬおよびＣＢＬは、比較的アクティブな更新ブロックを追跡する際の迅速なアクセスおよび容易な操作のために、コントローラＲＡＭ１３０（図１参照）に保持される。
割り当てブロックリスト（ＡＢＬ）は、消去済みメタブロックのプールと、消去済みメタブロックを更新ブロックにする割り当てとを追跡する。よって、これらの各メタブロックは、ＡＢＬ保留割り当ての消去済みブロックか、開放更新ブロックか、閉鎖更新ブロックかどうかを指定する属性によって記述されてもよい。図１８は、消去済みＡＢＬリスト６１２と、開放更新ブロックリスト６１４と、閉鎖更新ブロックリスト６１６とを含むＡＢＬを示す。加えて、開放更新ブロックリスト６１４に関連付けられているのは、関連する元ブロックリスト６１５である。同様に、閉鎖更新ブロックリストに関連付けられているのは、関連消去済みの元ブロックリスト６１７である。図１５において前に示したように、これらの関連リストは、それぞれ、開放更新ブロックリスト６１４および閉鎖更新ブロックリスト６１６のサブセットである。消去済みＡＢＬブロックリスト６１２、開放更新ブロックリスト６１４、および閉鎖更新ブロックリスト６１６は、すべて、割り当てブロックリスト（ＡＢＬ）６１０のサブセットであり、それぞれの中のエントリは、それぞれ対応する属性を有する。
ＭＡＰブロック７５０は、フラッシュメモリ２００内の消去管理記録を記憶するのに専用のメタブロックである。ＭＡＰブロックは、時系列のＭＡＰブロックセクタを記憶し、各ＭＡＰセクタは、消去ブロック管理（ＥＢＭ）セクタ７６０またはＭＡＰセクタ７８０のいずれかである。メタブロックが廃棄されて、消去済みブロックが割り当てで使い尽くされてリサイクルされるにつれて、関連する制御およびディレクトリデータは、ＭＡＰブロック内で更新される論理セクタに含まれるのが好ましく、更新データの各インスタンスは、新規のブロックセクタに記録される。ＥＢＭセクタ７６０およびＭＡＰセクタ７８０の複数のコピーがＭＡＰブロック７５０内に存在してもよく、その最新バージョンのみが有効である。有効ＭＡＰセクタの位置へのインデックスは、ＥＭＢブロック内のフィールド内に含まれる。有効なＥＭＢセクタが、制御書き込み動作中のＭＡＰブロック内にいつも最後に書き込まれる。ＭＡＰブロック７５０が一杯の場合には、すべての有効セクタを新規のブロック位置に書き換えることによって、制御書き込み動作中にコンパクト化される。その後、一杯のブロックは消去される。
各ＥＢＭセクタ７６０は、消去済みブロックリスト（ＥＢＬ）７７０を含み、これは、消去済みブロックの母集団のサブセットのアドレスのリストである。消去済みブロックリスト（ＥＢＬ）７７０は、消去済みメタブロック番号を含むバッファとしての役割を果たし、ＥＢＬから、メタブロック番号が周期的に取り出されてＡＢＬを再充填し、ＥＢＬに対して、メタブロック番号が周期的に追加されてＣＢＬを再び空にする。ＥＢＬ７７０は、使用可能ブロックバッファ（ＡＢＢ）７７２、消去済みブロックバッファ（ＥＢＢ）７７４、および消去済みブロックバッファ（ＣＢＢ）７７６のためのバッファとしての役割を果たす。
使用可能ブロックバッファ（ＡＢＢ）７７２は、前回のＡＢＬ充填動作のすぐ後に続くＡＢＬ６１０内のエントリのコピーを含む。これは、実質上、ＡＢＬ充填動作直後のＡＢＬのバックアップコピーである。
消去済みブロックバッファ（ＥＢＢ）７７４は、ＭＡＰセクタ７８０から、または（後述する）ＣＢＢリスト７７６からのいずれかから先に転送され、かつＡＢＬ充填動作中にＡＢＬ６１０へ転送に使用可能である消去済みブロックアドレスを含む。
クリアされたブロックバッファ（ＣＢＢ）７７６は、ＣＢＬを空にする動作中にＣＢＬ７４０から転送され、かつＭＡＰセクタ７８０またはＥＢＢリスト７７４へ後に転送される消去済みブロックのアドレスを含む。
消去済みブロックバッファ（ＥＢＢ）７７４は、ＭＡＰセクタ７８０から、または（後述する）ＣＢＢリスト７７６からのいずれかから先に転送され、かつＡＢＬ充填動作中にＡＢＬ６１０へ転送に使用可能である消去済みブロックアドレスを含む。
クリアされたブロックバッファ（ＣＢＢ）７７６は、ＣＢＬを空にする動作中にＣＢＬ７４０から転送され、かつＭＡＰセクタ７８０またはＥＢＢリスト７７４へ後に転送される消去済みブロックのアドレスを含む。
各ＭＡＰセクタ７８０は、ＭＡＰと称されるビットマップ構造を含む。ＭＡＰは、フラッシュメモリ内のメタブロック毎に１ビットを使用し、これは、各ブロックの消去状態を示すために使用される。ＡＢＬ、ＣＢＬ、またはＥＢＭ内の消去済みブロックリスト内に列挙されたブロックアドレスに対応するビットは、ＭＡＰ内において消去済み状態に設定されない。
有効データ構造を含まず、かつＭＡＰ内の消去済みブロック、消去済みブロックリスト、ＡＢＬ、またはＣＢＬとして指定されていないブロックはどれでも、ブロック割り当てアルゴリズムによって決して使用されず、従ってホストまたは制御データ構造の記憶のためにアクセスすることはできない。これにより、アクセス可能なフラッシュメモリアドレス空間から障害位置のあるブロックを除外するための簡単な機構が提供される。
図１８に示されている階層により、消去済みブロック記録を効率的に管理することができるようになり、コントローラのＲＡＭ内に記憶されたブロックアドレスリストの完全なセキュリティを提供する。消去済みブロックエントリが、これらのブロックアドレスリストと、１つ以上のＭＡＰセクタ７８０との間で、稀に交換される。これらのリストは、電源が切られた後のシステム初期化中に、消去済みブロックリスト、およびフラッシュメモリ内のセクタに記憶されたアドレス変換テーブル内の情報と、フラッシュメモリ内のわずかな数の参照済みデータブロックの限定的な走査とを介して再構築される。
消去済みメタブロック記録の階層を更新するために採用されたアルゴリズムにより、消去済みブロックが、ＭＡＰブロック７５０からのアドレス順序のブロックのバーストと、ブロックがホストによって更新された順序を反映するＣＢＬ７４０からのブロックアドレスのバーストとをインターリーブする順序で使用するために割り当てられる結果となる。メタブロックサイズおよびシステムメモリ容量のほとんどについて、１つのＭＡＰセクタは、システム内のすべてのメタブロックについてのビットマップを提供する。この場合、消去済みブロックは、このＭＡＰセクタに記録されるとおりのアドレス順序での使用のために常に割り当てられる。
消去ブロック管理動作
前に説明したように、ＡＢＬ６１０は、使用のために割り当てられるであろう消去済みメタブロック、およびデータ更新ブロックとして最近割り当てられたメタブロックについてのアドレスエントリを有するリストである。ＡＢＬ内のブロックアドレスの実際の数は、上限と下限という、システム設計の変数の間にある。製造中にフォーマットされたＡＢＬエントリの数は、カードの種類と容量との関数である。加えて、システムの寿命の終わりが近づくとＡＢＬ内のエントリの数が減少するのは、使用可能な消去済みブロックの数が寿命内でのブロックの障害によって減少するためである。例えば、充填動作の後、ＡＢＬ内のエントリは、以下の目的のために使用可能なブロックを指定してもよい。ブロック毎に１つのエントリを有する部分的に書き込まれたデータ更新ブロックについてのエントリであり、同時に開放されている更新ブロックの最大数についてのシステム制限を越えないもの。データ更新ブロックとして割り当てるための消去済みブロックについての１個から１２個の間のエントリ。制御ブロックとして割り当てるための消去済みブロックについての４つのエントリ。
前に説明したように、ＡＢＬ６１０は、使用のために割り当てられるであろう消去済みメタブロック、およびデータ更新ブロックとして最近割り当てられたメタブロックについてのアドレスエントリを有するリストである。ＡＢＬ内のブロックアドレスの実際の数は、上限と下限という、システム設計の変数の間にある。製造中にフォーマットされたＡＢＬエントリの数は、カードの種類と容量との関数である。加えて、システムの寿命の終わりが近づくとＡＢＬ内のエントリの数が減少するのは、使用可能な消去済みブロックの数が寿命内でのブロックの障害によって減少するためである。例えば、充填動作の後、ＡＢＬ内のエントリは、以下の目的のために使用可能なブロックを指定してもよい。ブロック毎に１つのエントリを有する部分的に書き込まれたデータ更新ブロックについてのエントリであり、同時に開放されている更新ブロックの最大数についてのシステム制限を越えないもの。データ更新ブロックとして割り当てるための消去済みブロックについての１個から１２個の間のエントリ。制御ブロックとして割り当てるための消去済みブロックについての４つのエントリ。
ＡＢＬ充填動作
ＡＢＬ６１０が割り当てによって使い尽くされると、再充填される必要があることになる。ＡＢＬを充填する動作は、制御書き込み動作中に生じる。これは、ブロックを割り当てなければならない場合にトリガされるが、ＡＢＬには、データ更新ブロックとして割り当てるため、またはいくつかの他の制御データ更新ブロックのために使用可能な消去済みブロックエントリが十分には含まれていない。制御書き込み中に、ＡＢＬ充填動作は、ＧＡＴ更新動作と並行して行われる。
ＡＢＬ６１０が割り当てによって使い尽くされると、再充填される必要があることになる。ＡＢＬを充填する動作は、制御書き込み動作中に生じる。これは、ブロックを割り当てなければならない場合にトリガされるが、ＡＢＬには、データ更新ブロックとして割り当てるため、またはいくつかの他の制御データ更新ブロックのために使用可能な消去済みブロックエントリが十分には含まれていない。制御書き込み中に、ＡＢＬ充填動作は、ＧＡＴ更新動作と並行して行われる。
以下の動作が、ＡＢＬ充填動作中に生じる。
１．現在のデータ更新ブロックの属性を有するＡＢＬエントリは保持される。
２．閉鎖データ更新ブロックの属性を有するＡＢＬエントリは、このブロックについてのエントリが並行ＧＡＴ更新動作において書き込み中でなければ保持され、書き込み中であれば、このエントリはＡＢＬから除去される。
３．割り当てられていない消去ブロックについてのＡＢＬエントリは保持される。
４．ＡＢＬは、エントリの除去によって生じたギャップを除去するためにコンパクト化され、エントリの順序が維持される。
５．ＡＢＬは、ＥＢＢリストから次に使用可能なエントリをつけることによって完全に充填される。
６．ＡＢＢリストは、ＡＢＬ内の現在のエントリで上書きされる。
１．現在のデータ更新ブロックの属性を有するＡＢＬエントリは保持される。
２．閉鎖データ更新ブロックの属性を有するＡＢＬエントリは、このブロックについてのエントリが並行ＧＡＴ更新動作において書き込み中でなければ保持され、書き込み中であれば、このエントリはＡＢＬから除去される。
３．割り当てられていない消去ブロックについてのＡＢＬエントリは保持される。
４．ＡＢＬは、エントリの除去によって生じたギャップを除去するためにコンパクト化され、エントリの順序が維持される。
５．ＡＢＬは、ＥＢＢリストから次に使用可能なエントリをつけることによって完全に充填される。
６．ＡＢＢリストは、ＡＢＬ内の現在のエントリで上書きされる。
ＣＢＬを空にする動作
ＣＢＬは、消去済みブロックエントリの数に対するＡＢＬと同じ制限を有する、コントローラＲＡＭ内の消去済みブロックアドレスのリストである。ＣＢＬを空にする動作は、制御書き込み動作中に生じる。したがって、この動作は、ＡＢＬ充填／ＧＡＴ更新動作、またはＣＢＩブロック書き込み動作と並行して行われる。ＣＢＬを空にする動作において、エントリはＣＢＬ７４０から除去されて、ＣＢＢリスト７７６に書き込まれる。
ＣＢＬは、消去済みブロックエントリの数に対するＡＢＬと同じ制限を有する、コントローラＲＡＭ内の消去済みブロックアドレスのリストである。ＣＢＬを空にする動作は、制御書き込み動作中に生じる。したがって、この動作は、ＡＢＬ充填／ＧＡＴ更新動作、またはＣＢＩブロック書き込み動作と並行して行われる。ＣＢＬを空にする動作において、エントリはＣＢＬ７４０から除去されて、ＣＢＢリスト７７６に書き込まれる。
ＭＡＰ交換動作
ＭＡＰセクタ７８０およびＥＢＭセクタ７６０内の消去ブロック情報間のＭＡＰ交換動作は、ＥＢＢリスト７７４が空の場合に、制御書き込み動作中に周期的に生じてもよい。システム内のすべての消去済みメタブロックは、ＥＢＭセクタ７６０内に記録され、ＭＡＰセクタ７８０はなく、ＭＡＰ交換は行われない。ＭＡＰ交換動作中に、ＥＢＢ７７４に消去済みブロックを入力するＭＡＰセクタは、送信元ＭＡＰセクタ７８２とみなされる。逆に、ＣＢＢ７７６から消去済みブロックを受信するＭＡＰセクタは、送信先ＭＡＰセクタ７８４とみなされる。ＭＡＰセクタが１つだけ存在する場合は、以下に規定するように、送信元および送信先ＭＡＰセクタの両方としての役割を果たす。
ＭＡＰセクタ７８０およびＥＢＭセクタ７６０内の消去ブロック情報間のＭＡＰ交換動作は、ＥＢＢリスト７７４が空の場合に、制御書き込み動作中に周期的に生じてもよい。システム内のすべての消去済みメタブロックは、ＥＢＭセクタ７６０内に記録され、ＭＡＰセクタ７８０はなく、ＭＡＰ交換は行われない。ＭＡＰ交換動作中に、ＥＢＢ７７４に消去済みブロックを入力するＭＡＰセクタは、送信元ＭＡＰセクタ７８２とみなされる。逆に、ＣＢＢ７７６から消去済みブロックを受信するＭＡＰセクタは、送信先ＭＡＰセクタ７８４とみなされる。ＭＡＰセクタが１つだけ存在する場合は、以下に規定するように、送信元および送信先ＭＡＰセクタの両方としての役割を果たす。
以下の動作が、ＭＡＰ交換中に行われる。
１．送信元ＭＡＰセクタが、増分ポインタに基づいて選択される。
２．送信先ＭＡＰセクタが、送信元ＭＡＰセクタ内ではない最初のＣＢＢエントリ内のブロックアドレスに基づいて選択される。
３．送信先ＭＡＰセクタが、ＣＢＢ内の該当エントリによって規定されたように更新され、当該エントリは、ＣＢＢから除去される。
４．別個の送信元ＭＡＰセクタが存在しなければ、更新された送信先ＭＡＰセクタが、ＭＡＰブロックに書き込まれる。
５．送信元ＭＡＰセクタが、ＣＢＢ内の該当エントリによって規定されたように更新され、当該エントリは、ＣＢＢから除去される。
６．ＣＢＢ内の残りのエントリが、ＥＢＢに付加される。
７．ＥＢＢには、送信元ＭＡＰセクタから規定された消去済みブロックアドレスができる限り充填される。
８．更新済みの送信元ＭＡＰセクタが、ＭＡＰブロック内に書き込まれる。
９．更新済みのＥＢＭセクタが、ＭＡＰブロック内に書き込まれる。
１．送信元ＭＡＰセクタが、増分ポインタに基づいて選択される。
２．送信先ＭＡＰセクタが、送信元ＭＡＰセクタ内ではない最初のＣＢＢエントリ内のブロックアドレスに基づいて選択される。
３．送信先ＭＡＰセクタが、ＣＢＢ内の該当エントリによって規定されたように更新され、当該エントリは、ＣＢＢから除去される。
４．別個の送信元ＭＡＰセクタが存在しなければ、更新された送信先ＭＡＰセクタが、ＭＡＰブロックに書き込まれる。
５．送信元ＭＡＰセクタが、ＣＢＢ内の該当エントリによって規定されたように更新され、当該エントリは、ＣＢＢから除去される。
６．ＣＢＢ内の残りのエントリが、ＥＢＢに付加される。
７．ＥＢＢには、送信元ＭＡＰセクタから規定された消去済みブロックアドレスができる限り充填される。
８．更新済みの送信元ＭＡＰセクタが、ＭＡＰブロック内に書き込まれる。
９．更新済みのＥＢＭセクタが、ＭＡＰブロック内に書き込まれる。
リスト管理
図１８は、様々なリスト間の制御およびディレクトリ情報の分配および流れを示す。便宜のために、リストの要素間でエントリを移動する動作、またはエントリの属性を変更する動作は、［Ａ］から［Ｏ］として図１８に示され、以下のようなものである。
［Ａ］消去済みブロックがホストデータについての更新ブロックとして割り当てられる場合には、そのエントリのＡＢＬ内にある属性は、消去済みＡＢＬブロックから開放更新ブロックに変更される。
［Ｂ］消去されたブロックが制御ブロックとして割り当てられる場合には、ＡＢＬ内のそのエントリが除去される。
［Ｃ］ＡＢＬエントリが開放更新ブロック属性と共に作成される場合には、更新中の論理グループについての元メタブロックアドレスを記録するために、関連する元ブロックフィールドがエントリに付加される。この情報は、ＧＡＴから取得される。
［Ｄ］更新ブロックが閉鎖されると、そのエントリのＡＢＬ内にある属性は、開放更新ブロックから閉鎖更新ブロックへ変更される。
［Ｅ］更新ブロックが閉鎖されると、その関連する元ブロックは消去されて、ＡＢＬ内にあるそのエントリ内の関連する元ブロックフィールドの属性は、消去済み元ブロックに変更される。
［Ｆ］ＡＢＬ充填動作中、同一の制御書き込み動作中にＧＡＴ内でアドレスが更新された閉鎖更新ブロックはどれでも、そのエントリがＡＢＬから除去される。
［Ｇ］ＡＢＬ充填動作中、閉鎖更新ブロックについてのエントリがＡＢＬから除去されると、その関連する消去済みの元ブロックについてのエントリが、ＣＢＬへ移動される。 ［Ｈ］制御ブロックが消去されると、それについてのエントリが、ＣＢＬへ追加される。
［Ｉ］ＡＢＬ充填動作中、消去済みブロックエントリが、ＥＢＢリストからＡＢＬへ移動され、消去済みＡＢＬブロックの属性が与えられる。
［Ｊ］ＡＢＬ充填動作中のすべての該当ＡＢＬエントリの修正後、ＡＢＬ内のブロックアドレスが、ＡＢＢリスト内のブロックアドレスに取って代わる。
［Ｋ］制御書き込み中にＡＢＬ充填動作と並行して、ＣＢＬ内の消去済みブロックについてのエントリが、ＣＢＢリストへ移動される。
［Ｌ］ＭＡＰ交換動作中、すべての該当エントリが、ＣＢＢリストからＭＡＰ送信先セクタへ移動される。
［Ｍ］ＭＡＰ交換動作中、すべての該当エントリが、ＣＢＢリストからＭＡＰ送信元セクタへ移動される。
［Ｎ］ＭＡＰ交換動作中の［Ｌ］および［Ｍ］に続いて、すべての残りのエントリが、ＣＢＢリストからＥＢＢリストへ移動される。
［Ｏ］ＭＡＰ交換動作中の［Ｎ］に続いて、可能であれば、［Ｍ］において移動されたもの以外のエントリが、ＭＡＰ送信元セクタから移動されて、ＥＢＢリストを充填する。
図１８は、様々なリスト間の制御およびディレクトリ情報の分配および流れを示す。便宜のために、リストの要素間でエントリを移動する動作、またはエントリの属性を変更する動作は、［Ａ］から［Ｏ］として図１８に示され、以下のようなものである。
［Ａ］消去済みブロックがホストデータについての更新ブロックとして割り当てられる場合には、そのエントリのＡＢＬ内にある属性は、消去済みＡＢＬブロックから開放更新ブロックに変更される。
［Ｂ］消去されたブロックが制御ブロックとして割り当てられる場合には、ＡＢＬ内のそのエントリが除去される。
［Ｃ］ＡＢＬエントリが開放更新ブロック属性と共に作成される場合には、更新中の論理グループについての元メタブロックアドレスを記録するために、関連する元ブロックフィールドがエントリに付加される。この情報は、ＧＡＴから取得される。
［Ｄ］更新ブロックが閉鎖されると、そのエントリのＡＢＬ内にある属性は、開放更新ブロックから閉鎖更新ブロックへ変更される。
［Ｅ］更新ブロックが閉鎖されると、その関連する元ブロックは消去されて、ＡＢＬ内にあるそのエントリ内の関連する元ブロックフィールドの属性は、消去済み元ブロックに変更される。
［Ｆ］ＡＢＬ充填動作中、同一の制御書き込み動作中にＧＡＴ内でアドレスが更新された閉鎖更新ブロックはどれでも、そのエントリがＡＢＬから除去される。
［Ｇ］ＡＢＬ充填動作中、閉鎖更新ブロックについてのエントリがＡＢＬから除去されると、その関連する消去済みの元ブロックについてのエントリが、ＣＢＬへ移動される。 ［Ｈ］制御ブロックが消去されると、それについてのエントリが、ＣＢＬへ追加される。
［Ｉ］ＡＢＬ充填動作中、消去済みブロックエントリが、ＥＢＢリストからＡＢＬへ移動され、消去済みＡＢＬブロックの属性が与えられる。
［Ｊ］ＡＢＬ充填動作中のすべての該当ＡＢＬエントリの修正後、ＡＢＬ内のブロックアドレスが、ＡＢＢリスト内のブロックアドレスに取って代わる。
［Ｋ］制御書き込み中にＡＢＬ充填動作と並行して、ＣＢＬ内の消去済みブロックについてのエントリが、ＣＢＢリストへ移動される。
［Ｌ］ＭＡＰ交換動作中、すべての該当エントリが、ＣＢＢリストからＭＡＰ送信先セクタへ移動される。
［Ｍ］ＭＡＰ交換動作中、すべての該当エントリが、ＣＢＢリストからＭＡＰ送信元セクタへ移動される。
［Ｎ］ＭＡＰ交換動作中の［Ｌ］および［Ｍ］に続いて、すべての残りのエントリが、ＣＢＢリストからＥＢＢリストへ移動される。
［Ｏ］ＭＡＰ交換動作中の［Ｎ］に続いて、可能であれば、［Ｍ］において移動されたもの以外のエントリが、ＭＡＰ送信元セクタから移動されて、ＥＢＢリストを充填する。
論理／物理アドレス変換
フラッシュメモリ内の論理セクタの物理位置を位置決定するために、図２に示されている論理／物理アドレス変換モジュール１４０は、論理／物理アドレス変換を行う。最近更新された論理グループを除いて、大量の変換を、フラッシュメモリ２００またはコントローラＲＡＭ１３０内のＧＡＴキャッシュ内にあるグループアドレステーブル（ＧＡＴ）を使用して行うことになる可能性がある。最近更新された論理グループについてのアドレス変換は、主にコントローラＲＡＭ１３０内にある更新ブロックについてのアドレスリストを検索することを必要とすることになる。したがって、論理セクタアドレスについての論理／物理アドレス変換のための処理は、セクタが位置する論理グループに関連したブロックの種類に依存する。ブロックの種類には、変化のないブロックと、順次データ更新ブロックと、カオス的データ更新ブロックと、閉鎖データ更新ブロックとがある。
フラッシュメモリ内の論理セクタの物理位置を位置決定するために、図２に示されている論理／物理アドレス変換モジュール１４０は、論理／物理アドレス変換を行う。最近更新された論理グループを除いて、大量の変換を、フラッシュメモリ２００またはコントローラＲＡＭ１３０内のＧＡＴキャッシュ内にあるグループアドレステーブル（ＧＡＴ）を使用して行うことになる可能性がある。最近更新された論理グループについてのアドレス変換は、主にコントローラＲＡＭ１３０内にある更新ブロックについてのアドレスリストを検索することを必要とすることになる。したがって、論理セクタアドレスについての論理／物理アドレス変換のための処理は、セクタが位置する論理グループに関連したブロックの種類に依存する。ブロックの種類には、変化のないブロックと、順次データ更新ブロックと、カオス的データ更新ブロックと、閉鎖データ更新ブロックとがある。
図１９は、論理／物理アドレス変換の処理を示すフローチャートである。基本的には、対応するメタブロックおよび物理セクタは、論理セクタアドレスを使用して、最初に、開放更新ブロックリストおよび閉鎖更新ブロックリストなどの様々な更新ディレクトリを検索することによって、位置決定される。関連するメタブロックが更新処理の一部でない場合、ディレクトリ情報がＧＡＴによって提供される。論理／物理アドレス変換は、以下のステップを含む。
ステップ８００：論理セクタアドレスが与えられる。
ステップ８１０：コントローラＲＡＭ内の開放更新ブロックリスト６１４（図１５および１８参照）内の所定の論理アドレスが検索される。検索が失敗すると、ステップ８２０へ進み、そうでなければ、ステップ８３０へ進む。
ステップ８２０：閉鎖更新ブロックリスト６１６内の所定の論理アドレスを検索する。検索が失敗すると、所定の論理アドレスはどの更新処理の一部でもないことになり、ＧＡＴアドレス変換のためのステップ８７０へ進む。そうでなければ、閉鎖更新ブロックアドレス変換のためのステップ８６０へ進む。
ステップ８３０：所定の論理アドレスを含む更新ブロックが順次であれば、順次更新ブロックアドレス変換のためのステップ８４０へ進む。そうでなければ、カオス的更新ブロックアドレス変換のためのステップ８５０へ進む。
ステップ８４０：順次更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８５０：カオス的更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８６０：閉鎖更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８７０：グループアドレステーブル（ＧＡＴ）変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８８０：メタブロックアドレスを物理アドレスに変換する。変換方法は、メタブロックが再リンクされているかどうかに依存する。
ステップ８９０：物理セクタアドレスが取得される。
ステップ８００：論理セクタアドレスが与えられる。
ステップ８１０：コントローラＲＡＭ内の開放更新ブロックリスト６１４（図１５および１８参照）内の所定の論理アドレスが検索される。検索が失敗すると、ステップ８２０へ進み、そうでなければ、ステップ８３０へ進む。
ステップ８２０：閉鎖更新ブロックリスト６１６内の所定の論理アドレスを検索する。検索が失敗すると、所定の論理アドレスはどの更新処理の一部でもないことになり、ＧＡＴアドレス変換のためのステップ８７０へ進む。そうでなければ、閉鎖更新ブロックアドレス変換のためのステップ８６０へ進む。
ステップ８３０：所定の論理アドレスを含む更新ブロックが順次であれば、順次更新ブロックアドレス変換のためのステップ８４０へ進む。そうでなければ、カオス的更新ブロックアドレス変換のためのステップ８５０へ進む。
ステップ８４０：順次更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８５０：カオス的更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８６０：閉鎖更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８７０：グループアドレステーブル（ＧＡＴ）変換を使用して、メタブロックアドレスを取得する。ステップ８８０へ進む。
ステップ８８０：メタブロックアドレスを物理アドレスに変換する。変換方法は、メタブロックが再リンクされているかどうかに依存する。
ステップ８９０：物理セクタアドレスが取得される。
様々なアドレス変換処理について、以下により詳細に説明する。
順次更新ブロックアドレス変換（ステップ８４０）
順次更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、開放更新ブロックリスト６１４内の情報から直接達成される（図１５および１８）。
１．リスト内の「ページタグ」フィールドおよび「書き込みセクタの数」フィールドから、対象論理セクタが更新ブロックにあるか、またはその関連する元ブロックにあるかどうかを判断する。
２．対象論理セクタに適切なメタブロックアドレスが、リストから読み出される。
３．メタブロック内のセクタアドレスが、適切な「ページタグ」フィールドから決定される。
順次更新ブロックアドレス変換（ステップ８４０）
順次更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、開放更新ブロックリスト６１４内の情報から直接達成される（図１５および１８）。
１．リスト内の「ページタグ」フィールドおよび「書き込みセクタの数」フィールドから、対象論理セクタが更新ブロックにあるか、またはその関連する元ブロックにあるかどうかを判断する。
２．対象論理セクタに適切なメタブロックアドレスが、リストから読み出される。
３．メタブロック内のセクタアドレスが、適切な「ページタグ」フィールドから決定される。
カオス的更新ブロックアドレス変換（ステップ８５０）
カオス的更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。
１．ＲＡＭ内のカオス的セクタリストから、セクタが最近書き込まれたセクタであると判断される場合には、アドレス変換は、このリスト内のその位置から直接達成されてもよい。
２．ＣＢＩブロック内の直近に書き込まれたセクタは、そのカオス的ブロックデータフィールド内に、対象論理セクタアドレスに該当するカオス的更新ブロックの物理アドレスを含む。また、その間接セクタインデックスフィールド内に、このカオス的更新ブロックに関連する最終書き込みＣＢＩセクタのＣＢＩブロック内のオフセットを含む（図１６Ａ〜１６Ｅ参照）。
３．これらのフィールド内の情報は、ＲＡＭ内にキャッシュされ、後続のアドレス変換中にセクタを読み出す必要をなくしている。
４．間接セクタインデックスフィールドによってステップ３において識別されたＣＢＩセクタが読み出される。
５．直近にアクセスされたカオス的更新サブグループについての直接セクタインデックスフィールドは、ＲＡＭ内にキャッシュされ、同一のカオス的更新ブロックに対する繰り返しのアクセスのためのステップ４における読み出しを行う必要をなくしている。
６．ステップ４または５において読み出された直接セクタインデックスフィールドは、対象論理セクタアドレスを含む論理サブグループに関連するＣＢＩセクタを識別する。
７．対象論理セクタアドレスについてのカオス的ブロックインデックスエントリは、ステップ６において識別されたＣＢＩセクタから読み出される。
８．直近に読み出されたカオス的ブロックインデックスフィールドは、コントローラＲＡＭ内にキャッシュされてもよく、同一の論理サブグループに対する繰り返しのアクセスのためのステップ４およびステップ７における読み出しを行う必要をなくしている。
９．カオス的ブロックインデックスエントリは、カオス的更新ブロックまたは関連する元ブロックのいずれかの内に対象論理セクタの位置を規定する。対象論理セクタの有効コピーが元ブロック内にあれば、元メタブロックおよびページタグ情報を使用して位置決定される。
カオス的更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。
１．ＲＡＭ内のカオス的セクタリストから、セクタが最近書き込まれたセクタであると判断される場合には、アドレス変換は、このリスト内のその位置から直接達成されてもよい。
２．ＣＢＩブロック内の直近に書き込まれたセクタは、そのカオス的ブロックデータフィールド内に、対象論理セクタアドレスに該当するカオス的更新ブロックの物理アドレスを含む。また、その間接セクタインデックスフィールド内に、このカオス的更新ブロックに関連する最終書き込みＣＢＩセクタのＣＢＩブロック内のオフセットを含む（図１６Ａ〜１６Ｅ参照）。
３．これらのフィールド内の情報は、ＲＡＭ内にキャッシュされ、後続のアドレス変換中にセクタを読み出す必要をなくしている。
４．間接セクタインデックスフィールドによってステップ３において識別されたＣＢＩセクタが読み出される。
５．直近にアクセスされたカオス的更新サブグループについての直接セクタインデックスフィールドは、ＲＡＭ内にキャッシュされ、同一のカオス的更新ブロックに対する繰り返しのアクセスのためのステップ４における読み出しを行う必要をなくしている。
６．ステップ４または５において読み出された直接セクタインデックスフィールドは、対象論理セクタアドレスを含む論理サブグループに関連するＣＢＩセクタを識別する。
７．対象論理セクタアドレスについてのカオス的ブロックインデックスエントリは、ステップ６において識別されたＣＢＩセクタから読み出される。
８．直近に読み出されたカオス的ブロックインデックスフィールドは、コントローラＲＡＭ内にキャッシュされてもよく、同一の論理サブグループに対する繰り返しのアクセスのためのステップ４およびステップ７における読み出しを行う必要をなくしている。
９．カオス的ブロックインデックスエントリは、カオス的更新ブロックまたは関連する元ブロックのいずれかの内に対象論理セクタの位置を規定する。対象論理セクタの有効コピーが元ブロック内にあれば、元メタブロックおよびページタグ情報を使用して位置決定される。
閉鎖更新ブロックアドレス変換（ステップ８６０）
閉鎖更新ブロックに関連した論理ブロックループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、閉鎖ブロック更新リスト内の情報から直接達成することができる（図１８参照）。
１．対象論理グループに割り当てられたメタブロックアドレスは、リストから読み出される。
２．メタブロック内のセクタアドレスは、リスト内の「ページタグ」フィールドから決定される。
閉鎖更新ブロックに関連した論理ブロックループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、閉鎖ブロック更新リスト内の情報から直接達成することができる（図１８参照）。
１．対象論理グループに割り当てられたメタブロックアドレスは、リストから読み出される。
２．メタブロック内のセクタアドレスは、リスト内の「ページタグ」フィールドから決定される。
ＧＡＴアドレス変換（ステップ８７０）
論理グループが開放または閉鎖ブロック更新リストのいずれかによって参照されない場合には、ＧＡＴ内のそのエントリは有効である。ＧＡＴによって参照される論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。
１．ＲＡＭ内の使用可能なＧＡＴキャッシュの範囲を評価して、対象論理グループについてのエントリがＧＡＴキャッシュ内に含まれるかどうかを判断する。
２．対象論理グループがステップ１において見つかった場合、ＧＡＴキャッシュは、メタブロックアドレスおよびページタグを含む全グループアドレス情報を含み、対象論理セクタアドレスの変換が可能となる。
３．対象アドレスがＧＡＴキャッシュ内にない場合、ＧＡＴインデックスを対象ＧＡＴブロックについて読みだして、対象論理グループアドレスに関するＧＡＴセクタの位置を識別しなければならない。
４．最後にアクセスされたＧＡＴブロックについてのＧＡＴインデックスは、コントローラＲＡＭ内に保持され、フラッシュメモリからセクタを読み出す必要なくアクセスされてもよい。
５．各ＧＡＴブロックについてのメタブロックアドレスのリストと、各ＧＡＴブロック内に書き込まれたセクタの数とが、コントローラＲＡＭ内に保持される。必要なＧＡＴインデックスがステップ４において使用可能でない場合、フラッシュメモリからすぐに読み出されてもよい。
６．対象論理グループアドレスに関するＧＡＴセクタは、ステップ４またはステップ６において取得されたＧＡＴインデックスによって規定されたＧＡＴブロック内のセクタ位置から読み出される。ＧＡＴキャッシュが、対象エントリを含むセクタの再分割部分によって更新される。
７．対象セクタアドレスは、対象ＧＡＴエントリ内のメタブロックアドレスおよび「ページタグ」フィールドから取得される。
論理グループが開放または閉鎖ブロック更新リストのいずれかによって参照されない場合には、ＧＡＴ内のそのエントリは有効である。ＧＡＴによって参照される論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。
１．ＲＡＭ内の使用可能なＧＡＴキャッシュの範囲を評価して、対象論理グループについてのエントリがＧＡＴキャッシュ内に含まれるかどうかを判断する。
２．対象論理グループがステップ１において見つかった場合、ＧＡＴキャッシュは、メタブロックアドレスおよびページタグを含む全グループアドレス情報を含み、対象論理セクタアドレスの変換が可能となる。
３．対象アドレスがＧＡＴキャッシュ内にない場合、ＧＡＴインデックスを対象ＧＡＴブロックについて読みだして、対象論理グループアドレスに関するＧＡＴセクタの位置を識別しなければならない。
４．最後にアクセスされたＧＡＴブロックについてのＧＡＴインデックスは、コントローラＲＡＭ内に保持され、フラッシュメモリからセクタを読み出す必要なくアクセスされてもよい。
５．各ＧＡＴブロックについてのメタブロックアドレスのリストと、各ＧＡＴブロック内に書き込まれたセクタの数とが、コントローラＲＡＭ内に保持される。必要なＧＡＴインデックスがステップ４において使用可能でない場合、フラッシュメモリからすぐに読み出されてもよい。
６．対象論理グループアドレスに関するＧＡＴセクタは、ステップ４またはステップ６において取得されたＧＡＴインデックスによって規定されたＧＡＴブロック内のセクタ位置から読み出される。ＧＡＴキャッシュが、対象エントリを含むセクタの再分割部分によって更新される。
７．対象セクタアドレスは、対象ＧＡＴエントリ内のメタブロックアドレスおよび「ページタグ」フィールドから取得される。
メタブロック／物理アドレス変換（ステップ８８０）
メタブロックが再リンクされていることをメタブロックアドレスに関連したフラグが示されている場合、該当ＬＴセクタがＢＬＭブロックから読み出されて、対象セクタアドレスについての消去ブロックアドレスであると決定する。そうでなければ、消去ブロックアドレスは、メタブロックアドレスから直接決定される。
メタブロックが再リンクされていることをメタブロックアドレスに関連したフラグが示されている場合、該当ＬＴセクタがＢＬＭブロックから読み出されて、対象セクタアドレスについての消去ブロックアドレスであると決定する。そうでなければ、消去ブロックアドレスは、メタブロックアドレスから直接決定される。
制御データ管理
図２０は、メモリ管理の動作中に、制御データ構造に対して行われる動作の階層を示す。データ更新管理動作は、ＲＡＭ内にある様々なリストに対して作用する。制御書き込み動作は、様々な制御データセクタおよびフラッシュメモリ内の専用ブロックに対して作用し、またＲＡＭ内のリストとデータを交換する。
図２０は、メモリ管理の動作中に、制御データ構造に対して行われる動作の階層を示す。データ更新管理動作は、ＲＡＭ内にある様々なリストに対して作用する。制御書き込み動作は、様々な制御データセクタおよびフラッシュメモリ内の専用ブロックに対して作用し、またＲＡＭ内のリストとデータを交換する。
データ更新管理動作が、ＲＡＭ内で、ＡＢＬ、ＣＢＬ、およびカオス的セクタリストに対して行われる。ＡＢＬは、消去済みブロックが更新ブロックまたは制御ブロックとして割り当てられる場合、または更新ブロックが閉鎖される場合に更新される。ＣＢＬは、制御ブロックが消去される場合、または閉鎖更新ブロックについてのエントリがＧＡＴに書き込まれる場合に更新される。更新カオス的セクタリストは、セクタがカオス的更新ブロックに書き込まれる場合に更新される。
制御書き込み動作によって、ＲＡＭ内の制御データ構造からの情報がフラッシュメモリ内の制御データ構造に書き込まれ、必要があれば、フラッシュメモリおよびＲＡＭ内の他の補助制御データ構造を更新する結果となる。これは、更新ブロックとして割り当てるべき消去済みブロックについてのエントリをＡＢＬがこれ以上含まない場合、またはＣＢＩブロックが書き換えられる場合にトリガされる。
好ましい実施形態において、ＡＢＬ充填動作、ＣＢＬを空にする動作、およびＥＢＭセクタ更新動作は、各制御書き込み動作中に行われる。ＥＢＭセクタを含むＭＡＰブロックが一杯になると、有効ＥＢＭおよびＭＡＰセクタが、割り当てられた消去済みブロックにコピーされ、以前のＭＡＰブロックは消去される。
各制御書き込み動作中に、１つのＧＡＴセクタが書き込まれ、かつ閉鎖更新ブロックリストがそれに従って修正される。ＧＡＴブロックが一杯になると、ＧＡＴ書き換え動作が行われる。
ＣＢＩセクタが、前に説明したように、あるカオス的セクタ書き込み動作後に書き込まれる。ＣＢＩブロックが一杯になると、有効なＣＢＩセクタが、割り当てられた消去済みブロックにコピーされ、以前のＣＢＩブロックは消去される。
ＭＡＰ交換動作が、前に説明したように、ＥＢＭセクタ内のＥＢＢリスト内に消去済みブロックエントリがこれ以上ない場合に行われる。
ＣＢＩセクタが、前に説明したように、あるカオス的セクタ書き込み動作後に書き込まれる。ＣＢＩブロックが一杯になると、有効なＣＢＩセクタが、割り当てられた消去済みブロックにコピーされ、以前のＣＢＩブロックは消去される。
ＭＡＰ交換動作が、前に説明したように、ＥＢＭセクタ内のＥＢＢリスト内に消去済みブロックエントリがこれ以上ない場合に行われる。
ＭＡＰアドレス（ＭＡＰＡ）セクタは、ＭＡＰブロックの現在アドレスを記録し、ＭＡＰブロックが書き換えられる度に専用のＭＡＰＡブロックに書き込まれる。ＭＡＰＡブロックが一杯になると、有効なＭＡＰＡセクタは、割り当てられた消去ブロックにコピーされ、以前のＭＡＰＡブロックは消去される。
ブートセクタが、ＭＡＰＡブロックが書き換えられる度に現在のブートブロック内に書き込まれる。ブートブロックが一杯になると、有効なブートセクタは、ブートブロックの現在のバージョンからバックアップバージョンへコピーされ、その後、現在のバージョンとなる。以前の現在のバージョンは消去されて、バックアップバージョンとなり、そこに有効なブートセクタは書き戻される。
ブートセクタが、ＭＡＰＡブロックが書き換えられる度に現在のブートブロック内に書き込まれる。ブートブロックが一杯になると、有効なブートセクタは、ブートブロックの現在のバージョンからバックアップバージョンへコピーされ、その後、現在のバージョンとなる。以前の現在のバージョンは消去されて、バックアップバージョンとなり、そこに有効なブートセクタは書き戻される。
制御データの整合性および管理
制御データの例として、図２０に関して説明したような、メモリブロック管理システムに関するディレクトリ情報およびブロック割り当て情報がある。前述したように、制御データは、高速ＲＡＭおよびより低速な不揮発性メモリブロックの両方において保持される。頻繁に変化する制御データはいずれも、不揮発性メタブロックに記憶された対応する情報を更新するために、周期的な制御書き込みを伴うＲＡＭに保持される。このように、制御データは、頻繁なアクセスを必要としない、不揮発だが低速のフラッシュメモリに記憶される。図２０に示されているＧＡＴ、ＣＢＩ、ＭＡＰ、ＭＡＰＡのような制御データ構造の階層をフラッシュメモリ内に保持する。よって、制御書き込み動作により、ＲＡＭ内の制御データ構造からの情報が、フラッシュメモリ内の対応する制御データ構造を更新する。
制御データの例として、図２０に関して説明したような、メモリブロック管理システムに関するディレクトリ情報およびブロック割り当て情報がある。前述したように、制御データは、高速ＲＡＭおよびより低速な不揮発性メモリブロックの両方において保持される。頻繁に変化する制御データはいずれも、不揮発性メタブロックに記憶された対応する情報を更新するために、周期的な制御書き込みを伴うＲＡＭに保持される。このように、制御データは、頻繁なアクセスを必要としない、不揮発だが低速のフラッシュメモリに記憶される。図２０に示されているＧＡＴ、ＣＢＩ、ＭＡＰ、ＭＡＰＡのような制御データ構造の階層をフラッシュメモリ内に保持する。よって、制御書き込み動作により、ＲＡＭ内の制御データ構造からの情報が、フラッシュメモリ内の対応する制御データ構造を更新する。
図２０に関して説明したように、ブロック管理システムは、その動作中にフラッシュメモリ内の制御データのセットを保持する。制御データのこのセットは、ホストデータと同様に、メタブロックに記憶される。このように、制御データ自体はブロック管理されることになり、更新を受けるので、ガーベッジコレクション動作も受けることになる。
また、低階層のデータが高階層のデータよりも頻繁に更新される、制御データの階層が存在することについて説明した。例えば、すべての制御ブロックは、書き込むためのＮ個の制御セクタを有すると想定すると、制御更新および制御ブロック移転の以下のシーケンスが普通は偶然にも生じる。図２０を再び参照すると、各Ｎ個のＣＢＩ更新によって、ＣＢＩブロックが充填されて、ＣＢＩ移転（書き換え）およびＭＡＰ更新がトリガされる。カオス的ブロックが閉鎖されると、ＧＡＴ更新もトリガされる。各ＧＡＴ更新は、ＭＡＰ更新をトリガする。各Ｎ個のＧＡＴ更新によって、ブロックが充填されて、ＧＡＴブロック移転がトリガされる。加えて、ＭＡＰブロックが一杯になると、ＭＡＰブロック移転およびＭＡＰＡブロック（ＭＡＰＡブロックがあればであるが、そうでなければ、ＢＯＯＴブロックはＭＡＰを直接ポイントする）更新もトリガされる。加えて、ＭＡＰＡブロックが一杯になると、ＭＡＰＡブロック移転、ＢＯＯＴブロック更新、およびＭＡＰ更新もトリガされる。加えて、ＢＯＯＴブロックが一杯になると、他のＢＯＯＴブロックに対するアクティブなＢＯＯＴブロック移転がトリガされる。
更新ブロック置換手法
本発明の他の態様によれば、ブロック管理システムを伴う不揮発性メモリにおいて、データを記録するために同時に開放されている更新ブロックの第１の所定最大数までサポートするシステムのために、改良されたブロック置換手法が実施される。更新ブロックは、主に連続更新ブロックであって、当該連続更新ブロックにおいて、データが論理的に連続した順序で記録されているが、そのブロック数は、データが論理的に連続した順序で記録されないカオス的更新ブロックであることが許容された第２の所定最大数までである。更新ブロックの新規の割り当てによって更新ブロックのプールが第１または第２の所定最大数を超えるような場合にはいつでも、当該制限に従うようにプール内の既存のブロックのうちの１つが閉鎖および削除されることになる。更新ブロックを閉鎖する前に、そのデータは連続ブロックに統合される。この改良された手法は、連続的な更新が過度のカオス的ブロック統合数を生じさせ得る状況を回避するためのものである。これは、連続更新ブロックとカオス的更新ブロックとをそれぞれの置換または統合プールに分離することによって達成される。特に、連続更新によって新規の更新ブロックの割り当てが第１の所定最大数を超える場合には、プール内の最も長時間使用されていない連続更新ブロックが、空きを作るために優先される。
本発明の他の態様によれば、ブロック管理システムを伴う不揮発性メモリにおいて、データを記録するために同時に開放されている更新ブロックの第１の所定最大数までサポートするシステムのために、改良されたブロック置換手法が実施される。更新ブロックは、主に連続更新ブロックであって、当該連続更新ブロックにおいて、データが論理的に連続した順序で記録されているが、そのブロック数は、データが論理的に連続した順序で記録されないカオス的更新ブロックであることが許容された第２の所定最大数までである。更新ブロックの新規の割り当てによって更新ブロックのプールが第１または第２の所定最大数を超えるような場合にはいつでも、当該制限に従うようにプール内の既存のブロックのうちの１つが閉鎖および削除されることになる。更新ブロックを閉鎖する前に、そのデータは連続ブロックに統合される。この改良された手法は、連続的な更新が過度のカオス的ブロック統合数を生じさせ得る状況を回避するためのものである。これは、連続更新ブロックとカオス的更新ブロックとをそれぞれの置換または統合プールに分離することによって達成される。特に、連続更新によって新規の更新ブロックの割り当てが第１の所定最大数を超える場合には、プール内の最も長時間使用されていない連続更新ブロックが、空きを作るために優先される。
現行システムにおいて、一般的に、ユーザデータと制御データという２つの種類のデータがある。ユーザデータは、ホストからメモリシステムへ、典型的には論理的に連続した順序で送られる。連続更新ブロックは、ホストからの連続書き込み動作を最適に扱うように割り当てられる。ユーザデータは、とりわけ論理データに対する後続の更新がある場合には、論理的に不連続な順序である場合がある。カオス的更新ブロックは、不連続な順序でデータを最適に扱うために作成される。カオス的または不連続データの他のソースとしては、ユーザデータを記憶する過程で生成されるファイルおよびディレクトリ情報などといった、ファイルシステムまたはメモリシステムによって保持される制御データがある。
同時に開放されている更新ブロックの最大数までサポートするという実際上のシステム制限に従う従来の手法は、連続的かカオス的かどうかに関わらず、プール内の最も長時間使用されていない更新ブロックを閉鎖するものであった。
本願の手法は、従来の手法を改良するものであって、基本的には、連続的な書き込み動作中に、新規の割り当て用に空きを作るためにプール内の更新ブロックを閉鎖する必要がある場合には、プール内の最も長時間使用されていない連続更新ブロックが閉鎖される。これにより、連続的な書き込み動作およびランダムな書き込み動作を扱うために様々な更新ブロックを効果的に活用することが確実になる。特に、ホストによる大規模な連続書き込み動作によってＦＡＴおよびディレクトリ情報を含むカオス的更新ブロックを閉鎖せざるを得なくなる場合があるといった非効率な状況を回避する。この大規模な書き込み動作が終わると再び更新されるようなＦＡＴおよびディレクトリ情報を記憶するために、さらなるカオス的ブロックが実質上まもなく作成されることになる。改良された置換ポリシーを作成することによって、置換および統合プールの分離が規定され、開放された連続ブロックまたは開放されたカオス的ブロックとなり得るブロックの連続的な書き込みおよび統合中に、カオス的ブロックを統合する際のさらなるオーバーヘッドを防止して、後続のＦＡＴおよびディレクトリ更新を管理する。
同時に開放されている更新ブロックの最大数までサポートするという実際上のシステム制限については前に述べた。例えば、図１０に関連して説明した一実施形態において、ステップ４１０は、更新データを受け付けるために同時に開放され得る更新ブロックの最大数ＵMAX を超えることになるかどうかをテストする。ＵMAX を超えることになる場合には、更新ブロックのうちで最もアクティブでないものが、連続更新ブロックであるのかカオス的更新ブロックであるのかに関わらず、ステップ４２０において閉鎖されることになり、所定の制限内にシステムを維持する。
図２１は、ブロック管理システム用の更新ブロック数に対する２つの所定の規制を概略的に示す。更新ブロック総数に対する包括的な規制（ＵMAX ）があり、これは、カオス的更新ブロックＮC の数と連続更新ブロックＮS の数との合計によって与えられる。カオス的更新ブロックは、より多くのリソースを要し、カオス的ブロックインデックス（ＣＢＩ）をさらに保持することを必要とするので、カオス的更新ブロックの最大数（「ＵCMAX」）に対する規制もある。よって、第１の規制は、更新ブロック総数ＮC ＋ＮS ≦ＵMAX であることを要する。第２の規制は、カオス的更新ブロック数ＮC ≦ＵCMAXであることを要する。
図２２は、様々なメモリ装置用に最適化された２つの規制の組み合わせの典型例を示す。ある組み合わせは、ＵMAX 「ダッシュ」ＵCMAXによって指定される。例えば、「３−１」は、更新プール内の最大３つの更新ブロックを許容し、そのうち１つまでのみがカオス的更新ブロックであるブロック管理システムを指定する。同様に、「７−３」は、最大７つの更新ブロックまでをサポートし、そのうち３つまでがカオス的更新ブロックであり得るブロック管理システムを指定する。一般的に、小さいメモリ容量を有する単純なメモリシステムほど、制限が厳しくなり、最大数が小さくなることになる。
図２３Ａ、図２３Ｂおよび図２３Ｃは、従来の置換手法における第１の状況に係る、新規の更新ブロックを更新ブロックのプールに導入するためのイベントのシーケンスを概略的に示す。
図２３Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１２０１のＳ３のような連続更新ブロックであるという第１の状況を示す。
図２３Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１２０１のＳ３のような連続更新ブロックであるという第１の状況を示す。
新規の更新ブロックを割り当てる必要がある場合には、空きを作るために、更新プール内の既存の更新ブロックのうちの１つが閉鎖される必要があることになる。例えば、プール内の既存の更新ブロックによってサービス提供されていないセクタの論理グループについて連続データをホストが書き込む場合には、当該データを記録するために、新規の更新ブロックを割り当てる必要がある。
図２３Ｂは、従来の手法に係る、新規の更新ブロック用に空きを作るために最もアクティブでない更新ブロックを閉鎖することを概略的に示す。最もアクティブでないブロックは、この場合では偶然にも１２０１のＳ３であり、閉鎖されて更新ブロックのプールから削除されることになる。
図２３Ｃは、空きを作るために閉鎖された更新ブロックが削除された後、新たに割り当てられた更新ブロックをプールに導入することを概略的に示す。この場合、データを論理的に連続した順序で記録するために、新規に割り当てられた更新ブロックである１２１２のＳ６が、連続プール１２００に導入されることになる。このように、許容される更新ブロックの最大数であるＵMAX を超えることはない。
図２４Ａ、図２４Ｂ、および図２４Ｃは、従来の置換手法における第２の状況に係る、新規の更新ブロックを更新ブロックのプールに導入するためのイベントのシーケンスを概略的に示す。
図２４Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１３０１のＣ４のようなカオス的更新ブロックであるという第２の状況を示す。
図２４Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１３０１のＣ４のようなカオス的更新ブロックであるという第２の状況を示す。
図２４Ｂは、従来の手法に係る、新規の更新ブロック用に空きを作るために最もアクティブでない更新ブロックを閉鎖することを概略的に示す。最もアクティブでないブロックは、この場合では偶然にも１３０１のＣ４であり、閉鎖されて更新ブロックのプールから削除されることになる。
図２４Ｃは、空きを作るために閉鎖された更新ブロックが削除された後、新たに割り当てられた更新ブロックをプールに導入することを概略的に示す。この場合、データを論理的に連続した順序で記録するために、新規に割り当てられた更新ブロックである１２１２のＳ６が、連続プール１２００に導入されることになる。このように、許容される更新ブロックの最大数であるＵMAX を超えることはない。
図２５Ａおよび図２５Ｂは、図１０、図２３Ｂおよび図２４Ｂにおいて先に説明した手法におけるＵMAX およびＵCMAX制限の保持をそれぞれ示す。２つの制限は、典型的には同時に課せられる。
図２５Ａは、図１０のステップ４１０ならびに図２３Ｂおよび図２４Ｂに先に示す手法であって、新規の割り当てが所定の制限を超えるような場合にはいつでも、最も長時間アクセスされていない更新ブロックが閉鎖される手法を示す。
ステップ１２５２：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１２５４：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１２５６：新規の更新ブロックの割り当てが当該所定数を超えるようになる場合にはいつでも、直近にアクセスされた更新ブロックのうちの１つを閉鎖して、新規更新ブロック用に空きを作る。
ステップ１２５２：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１２５４：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１２５６：新規の更新ブロックの割り当てが当該所定数を超えるようになる場合にはいつでも、直近にアクセスされた更新ブロックのうちの１つを閉鎖して、新規更新ブロック用に空きを作る。
図２５Ｂは、図１０のステップ３７０に先に示す手法であって、カオス的更新ブロック数が所定の制限を超える場合にはいつでも、最も長時間アクセスされていないカオス的（不連続）更新ブロックが閉鎖される手法を示す。
ステップ１３５４：データの論理ユニットを論理的に不連続な順序で記憶するための開放更新ブロックのうち、更新ブロックの第２の所定数まで割り当てる。
ステップ１３５６：不連続更新ブロックの数が第２の所定数を超えるようになる場合にはいつでも、最も長時間アクセスされていない不連続更新ブロックのうちの１つを閉鎖して、第２の所定数を超えないようにする。
ステップ１３５４：データの論理ユニットを論理的に不連続な順序で記憶するための開放更新ブロックのうち、更新ブロックの第２の所定数まで割り当てる。
ステップ１３５６：不連続更新ブロックの数が第２の所定数を超えるようになる場合にはいつでも、最も長時間アクセスされていない不連続更新ブロックのうちの１つを閉鎖して、第２の所定数を超えないようにする。
この従来の手法の欠点の１つは、状況によって、カオス的更新ブロックを過度に閉鎖してしまうことにつながり得ることである。連続書き込みによって、新規に割り当てられた連続ブロック用にプール内に空きを作るために制御データを含むカオス的ブロックが早期に閉鎖されてしまう場合、特に非効率である。例えば、閉鎖されたカオス的更新ブロックである１３１０のＣ４がＦＡＴおよびディレクトリ情報を記録していた場合には、連続書き込みがなされたらすぐに当該機能をサービス提供するために、置換が直ちに必要になる。これは、制御データを記録するための置換更新ブロック用に空きを作るために、現在プール内にある最もアクティブでない更新ブロックをもう一度閉鎖することになる。
本発明のこの態様によれば、更新ブロックの所定の最大数を超えないように更新ブロックを閉鎖するこの手法は、最も長時間使用されていない更新ブロックを単に選択することから、カオス的更新ブロックが過度に閉鎖される事例を減少させる手法へとさらに洗練されている。好ましい一実施形態において、連続データを記録するために更新ブロックが割り当てられ、空きを作るために更新ブロックのプール内の１つが閉鎖される場合には、プール内の最もアクティブでない連続更新ブロックが閉鎖される。
図２６Ａ、図２６Ｂおよび図２６Ｃは、改良された本願の置換手法に係る、新規更新ブロックを更新ブロックのプールに導入するためのイベントのシーケンスを概略的に示す。
図２６Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１３０１のＣ４のようなカオス的更新ブロックであるという、図２４Ａにおけるのと同様の状況を示す。さらに、この例は、連続ブロック１２０２のＳ３が連続プール１２００のうち最もアクティブでないことを示す。
図２６Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１３０１のＣ４のようなカオス的更新ブロックであるという、図２４Ａにおけるのと同様の状況を示す。さらに、この例は、連続ブロック１２０２のＳ３が連続プール１２００のうち最もアクティブでないことを示す。
図２６Ｂは、本願の改良された手法に係る、新規の更新ブロック用に空きを作るためにプール内の更新ブロックのうちの１つを閉鎖することを概略的に示す。連続更新に関連した新規の割り当てであって、プール内の更新ブロック数が既に最大である場合、新規に割り当てられた更新ブロック用に空きを作るために、プール内の更新ブロックのうちの１つを閉鎖しなければならなくなる。しかし、この場合、最もアクティブでないブロックは、１３０１のＣ４であり、これはカオス的ブロックであるので、パスされることになる。代わりに、連続プール１２００内で最もアクティブな更新ブロックが閉鎖されることになる。この例において、閉鎖されて更新ブロックプールから削除されることになるのは１２０２のＳ３である。
図２６Ｃは、空きを作るために閉鎖された更新ブロックが削除された後、新たに割り当てられた更新ブロックをプールに導入することを概略的に示す。この場合、データを論理的に連続した順序でデータを記録するために、新規に割り当てられた更新ブロックである１２１２のＳ６が、連続プール１２００に導入されることになる。このように、許容される更新ブロックの最大数であるＵMAX を超えることはない。
図２７Ａ、図２７Ｂ、および図２７Ｃは、本願の改良された置換手法に係る、新規のカオス的更新ブロックを更新ブロックのプールに導入するためのイベントのシーケンスを概略的に示す。
図２７Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１２０１のＳ６のような連続更新ブロックであることを示す。さらに、この例は、カオス的ブロックである１３０２のＣ４を、カオス的プール１３００のうちで最もアクティブでないものとすることを示す。
図２７Ａは、図２２において説明したような「５−２」構成の更新プールを概略的に示す。この例において、更新プールは、最大５つの許容更新ブロックで完全に埋められている。更新プールは、３つの連続更新ブロックＳ１、Ｓ２およびＳ３を含む連続プール１２００と、最大２つのカオス的または不連続更新ブロックＣ４およびＣ５を含むカオス的プール１３００とにさらに分割される。この例は、最もアクティブでないブロックが偶然にも１２０１のＳ６のような連続更新ブロックであることを示す。さらに、この例は、カオス的ブロックである１３０２のＣ４を、カオス的プール１３００のうちで最もアクティブでないものとすることを示す。
図２７Ｂは、本願の改良された手法に係る、新規の更新ブロック用に空きを作るためにプール内の更新ブロックのうちの１つを閉鎖することを概略的に示す。新規のカオス的更新ブロックが既に一杯のカオス的プール１３００に導入される場合、空きを作るためにカオス的プール内の更新ブロックのうちの１つが閉鎖されなければならなくなる。この例において、カオス的プール１３００は、最大２つのカオス的更新ブロックを既に含んでいる。さらなるカオス的更新ブロックが作成されると、例えば既存の連続更新ブロックである１２２０のＳ１をカオス的ブロックに変換する場合には、カオス的ブロックのうちの１つを削除しなければ、カオス的ブロックの最大数を超える。この場合、空きを作るために、最もアクティブでないカオス的ブロックである１３０２のＣ４が閉鎖されて、カオス的プール１３００から削除される。
図２７Ｃは、空きを作るために他のカオス的更新ブロックが閉鎖および削除された後、新規のカオス的更新ブロックをプールに導入することを概略的に示す。この場合、Ｓ１が、連続プール１２００内の連続更新ブロック１２２０から、カオス的プール１３００内のカオス的ブロックである１３２０のＣ６に変換されている。このように、許容されるカオス的更新ブロックの最大数であるＵCMAXを超えることはない。
図２８は、第１の実施形態に係る、連続更新中に更新ブロックの限られたセットを管理する本願の改良された手法を示すフローチャートである。
ステップ１４００：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４０２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１４０６：連続データを書き込むための書き込みコマンドに応じて、データの論理ユニットを連続順序で更新ブロックに書き込む。
ステップ１４０８：データの連続論理ユニットをさらに書き込むために閉鎖される更新ブロックについて満たされた所定の条件に応じて、新規の更新ブロックを割り当てて書き込みを継続し、新規の割り当てが第１の所定数を超えるようであれば、最も長時間アクセスされていない連続順序の更新ブロックを、最も長時間アクセスされていない不連続な順序の更新ブロックのいずれよりも優先的に閉鎖する。
ステップ１４００：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４０２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１４０６：連続データを書き込むための書き込みコマンドに応じて、データの論理ユニットを連続順序で更新ブロックに書き込む。
ステップ１４０８：データの連続論理ユニットをさらに書き込むために閉鎖される更新ブロックについて満たされた所定の条件に応じて、新規の更新ブロックを割り当てて書き込みを継続し、新規の割り当てが第１の所定数を超えるようであれば、最も長時間アクセスされていない連続順序の更新ブロックを、最も長時間アクセスされていない不連続な順序の更新ブロックのいずれよりも優先的に閉鎖する。
図２９は、第２の実施形態に係る、２つの所定の制限を有する更新ブロックの限られたセットを管理する本願の改良された手法を示すフローチャートである。
ステップ１４１０：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４１２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１４１６：データの論理ユニットを論理的に不連続な順序で記憶するための開放更新ブロックのうち、更新ブロックの第２の所定数まで割り当てる。
ステップ１４１８：論理的に連続した順序でデータを記憶するための更新ブロックの導入が第１の所定数を超えるようになる場合にはいつでも、論理的に連続した順序のデータを含む最も長時間アクセスされていない更新ブロックを閉鎖して、導入された更新ブロック用に空きを作る。
ステップ１４２０：論理的に不連続な順序でデータを記憶するための更新ブロックの導入が第２の所定数を超えるようになる場合にはいつでも、論理的に不連続な順序のデータを含む最も長時間アクセスされていない更新ブロックを閉鎖して、導入された更新ブロック用に空きを作る。
ステップ１４１０：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４１２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定数まで割り当てる。
ステップ１４１６：データの論理ユニットを論理的に不連続な順序で記憶するための開放更新ブロックのうち、更新ブロックの第２の所定数まで割り当てる。
ステップ１４１８：論理的に連続した順序でデータを記憶するための更新ブロックの導入が第１の所定数を超えるようになる場合にはいつでも、論理的に連続した順序のデータを含む最も長時間アクセスされていない更新ブロックを閉鎖して、導入された更新ブロック用に空きを作る。
ステップ１４２０：論理的に不連続な順序でデータを記憶するための更新ブロックの導入が第２の所定数を超えるようになる場合にはいつでも、論理的に不連続な順序のデータを含む最も長時間アクセスされていない更新ブロックを閉鎖して、導入された更新ブロック用に空きを作る。
本願の手法を一般的にいうと、更新ブロックが連続または不連続データのいずれを記憶しているか、または、ある予め定められた種類のシステムデータを記憶しているかどうかなどといった属性のセットに基づいて、更新ブロックを分類するものである。限られた数の更新ブロックのプールを実装するにあたって、更新ブロックの各クラスは、当該クラス用にサポートされた最大数を超えるような場合の置換に関する独自の規則を有することになる。
例えば、連続更新ブロックおよび不連続更新ブロックは、２つの異なるクラスである。これら各クラス用の置換規則は同一であり、すなわち、最もアクティブでないものを新規のものに置換する。よって、連続更新ブロックのプールを超えるような場合には、新規のものがプールに導入される前に、プール内の最もアクティブでないものが閉鎖および削除されることになる。不連続更新ブロックのプールについても同様である。
一般的に、各クラスは、他のクラスから独立した独自の置換規則を有する。置換規則の例として、対応するクラスによっては、最も長時間アクセスされていないもの、直近にアクセスされたもの、最も頻繁にアクセスされていないもの、最も頻繁にアクセスされているものなどを置換する。
図３０は、クラスベースの置換規則を有する更新ブロックの限られたセットを管理する本願の改良された手法を示すフローチャートである。
ステップ１４３０：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４３２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定最大数までのプールを提供する。
ステップ１４３６：更新ブロックを属性のセットに基づいて分類するための予め定められたクラスのセットを提供し、各クラスは関連する所定最大数の更新ブロックまでのサブプールをサポートする。
ステップ１４３８：それぞれのサブプール内の置換されるべき更新ブロックを特定するために、予め定められたクラスのセットに対応する置換規則のセットを提供する。
ステップ１４４０：プール内の更新ブロックを対応するサブプールにグループ化する。
ステップ１４４２：同一のクラスの他の更新ブロックが導入されつつある場合にはいつでも、関連する所定最大数の更新ブロックを含むサブプール内にある最もアクティブでない更新ブロックを閉鎖および削除する。
ステップ１４３０：不揮発性メモリをブロックに組織化し、各ブロックは共に消去可能なデータを記憶するためのものである。
ステップ１４３２：データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定最大数までのプールを提供する。
ステップ１４３６：更新ブロックを属性のセットに基づいて分類するための予め定められたクラスのセットを提供し、各クラスは関連する所定最大数の更新ブロックまでのサブプールをサポートする。
ステップ１４３８：それぞれのサブプール内の置換されるべき更新ブロックを特定するために、予め定められたクラスのセットに対応する置換規則のセットを提供する。
ステップ１４４０：プール内の更新ブロックを対応するサブプールにグループ化する。
ステップ１４４２：同一のクラスの他の更新ブロックが導入されつつある場合にはいつでも、関連する所定最大数の更新ブロックを含むサブプール内にある最もアクティブでない更新ブロックを閉鎖および削除する。
本願明細書において参照されたすべての特許、特許出願、論文、書籍、明細書、他の出版物、書類、および事物は、あらゆる目的のためにその全体が本願明細書において参照により援用されている。任意の援用されている出版物、書類、および事物と、本願明細書の文章との間に用語の定義または用法における矛盾または不一致がある場合には、本願明細書における用語の定義または用法に従う。
本発明の様々な態様をある実施形態に関して説明してきたが、本発明は、添付の特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解できよう。
Claims (23)
- 共に消去可能なデータの論理ユニットを記憶するためのブロックから各々なる、複数のブロックに組織化された不揮発性メモリにおける、データを前記メモリに記憶する方法であって、
データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックとして、第１の所定ブロック数まで割り当てるステップと、
データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定最大数までのプールを提供するステップと、
更新ブロックを属性のセットに基づいて分類するための予め定められたクラスのセットを提供するステップであって、各クラスは、関連する所定最大数の更新ブロックまでのサブプールをサポートするステップと、
対応する置換規則のセットを前記予め定められたクラスのセットに提供して、それぞれのサブプール内の置換されるべき前記更新ブロックを特定するステップと、
前記プール内の前記更新ブロックを対応するサブプールにグループ化するステップと、
同一のクラスの他の更新ブロックが導入されつつある場合にはいつでも、前記関連する所定最大数の更新ブロックを含むサブプール内にある最もアクティブでない更新ブロックを閉鎖および削除するステップであって、前記削除される更新ブロックは、同一のクラス用の前記対応する置換規則に従って選択されるステップと、
を含む方法。 - 請求項１記載の方法において、
前記属性のセットは、論理的に連続した順序でデータを記憶するブロックを含む方法。 - 請求項１記載の方法において、
前記属性のセットは、論理的に不連続な順序でデータを記憶するブロックを含む方法。 - 請求項１記載の方法において、
前記属性のセットは、前記メモリを動作させることに関連したシステムデータを記憶するブロックを含む方法。 - 請求項１記載の方法において、
前記メモリは、フラッシュＥＥＰＲＯＭである方法。 - 請求項１記載の方法であって、
前記メモリは、ＮＡＮＤ構造を有する方法。 - 請求項１記載の方法において、
前記メモリは、着脱可能なメモリカード上にある方法。 - 請求項１記載の方法において、
前記不揮発性メモリは、フローティングゲート構造のメモリセルを有する方法。 - 請求項１記載の方法において、
前記不揮発性メモリは、誘電体層構造のメモリセルを有する方法。 - 請求項１〜９のいずれか一項に記載の方法において、
前記メモリは、１ビットのデータをそれぞれ記憶するメモリセルを有する方法。 - 請求項１〜９のいずれか一項に記載の方法において、
前記メモリは、１ビット以上のデータをそれぞれ記憶するメモリセルを有する方法。 - 不揮発性メモリであって、
ブロックに組織化されたメモリであって、各ブロックは、共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものであるメモリと、
データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定最大数までのプールと、
更新ブロックを属性のセットに基づいて分類するための予め定められたクラスのセットであって、各クラスは、関連する所定最大数の更新ブロックまでのサブプールをサポートするセットと、
それぞれのサブプール内の置換されるべき前記更新ブロックを特定するための、前記予め定められたクラスのセットに対応する置換規則のセットと、
クラス毎に更新ブロックを含むサブプールのセットと、
前記ブロックの動作を制御するためのコントローラであって、前記動作は、
同一のクラスの他の更新ブロックが導入されつつある場合にはいつでも、前記関連する所定最大数の更新ブロックを含むサブプール内にある更新ブロックを閉鎖および削除し、前記削除される更新ブロックは、同一のクラス用の前記対応する置換規則に従って選択されることを含むコントローラと、
を備える不揮発性メモリ。 - 請求項１２記載のメモリにおいて、
前記属性のセットは、論理的に連続した順序でデータを記憶するブロックを含むメモリ。 - 請求項１２記載のメモリにおいて、
前記属性のセットは、論理的に不連続な順序でデータを記憶するブロックを含むメモリ。 - 請求項１２記載のメモリにおいて、
前記属性のセットは、前記メモリを動作させることに関連したシステムデータを記憶するブロックを含むメモリ。 - 請求項１２記載のメモリであって、
前記メモリは、フラッシュＥＥＰＲＯＭであるメモリ。 - 請求項１２記載のメモリにおいて、
前記メモリは、ＮＡＮＤ構造を有するメモリ。 - 請求項１２記載のメモリにおいて、
前記メモリは、着脱可能なメモリカード上にあるメモリ。 - 請求項１２記載のメモリにおいて、
前記不揮発性メモリは、フローティングゲート構造のメモリセルを有するメモリ。 - 請求項１２記載のメモリにおいて、
前記不揮発性メモリは、誘電体層構造のメモリセルを有するメモリ。 - 不揮発性メモリであって、
ブロックに組織化されたメモリであって、各ブロックは、共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものであるメモリと、
データの論理ユニットの更新を記憶するために同時に開放中の更新ブロックの第１の所定最大数までのプールと、
更新ブロックを属性のセットに基づいて分類するための予め定められたクラスのセットであって、各クラスは、関連する所定最大数の更新ブロックまでのサブプールをサポートするセットと、
それぞれのサブプール内の置換されるべき前記更新ブロックを特定するための、前記予め定められたクラスのセットに対応する置換規則のセットと、
クラス毎に更新ブロックを含むサブプールのセットと、
同一のクラスの他の更新ブロックが導入されつつある場合にはいつでも、前記関連する所定最大数の更新ブロックを含むサブプール内にある更新ブロックを閉鎖するおよび削除する手段であって、前記削除される更新ブロックは、同一のクラス用の前記対応する置換
規則に従って選択される手段と、
を備える不揮発性メモリ。 - 請求項１２〜２１のいずれか一項に記載のメモリにおいて、
前記メモリは、１ビットのデータをそれぞれ記憶するメモリセルを有するメモリ。 - 請求項１２〜２１のいずれか一項に記載のメモリにおいて、
前記メモリは、１ビット以上のデータをそれぞれ記憶するメモリセルを有するメモリ。
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US11/532,467 US7774392B2 (en) | 2006-09-15 | 2006-09-15 | Non-volatile memory with management of a pool of update memory blocks based on each block's activity and data order |
| US11/532,456 US7779056B2 (en) | 2006-09-15 | 2006-09-15 | Managing a pool of update memory blocks based on each block's activity and data order |
| PCT/US2007/078311 WO2008033952A2 (en) | 2006-09-15 | 2007-09-12 | Non-volatile memory and method for class-based update block replacement rules |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JP2010503929A JP2010503929A (ja) | 2010-02-04 |
| JP2010503929A5 JP2010503929A5 (ja) | 2010-10-28 |
| JP4682261B2 true JP4682261B2 (ja) | 2011-05-11 |
Family
ID=39185714
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2009528456A Expired - Fee Related JP4682261B2 (ja) | 2006-09-15 | 2007-09-12 | 不揮発性メモリおよびクラスベースの更新ブロック置換規則のための方法 |
Country Status (4)
| Country | Link |
|---|---|
| JP (1) | JP4682261B2 (ja) |
| KR (1) | KR101430097B1 (ja) |
| TW (1) | TWI340899B (ja) |
| WO (1) | WO2008033952A2 (ja) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR101526497B1 (ko) * | 2008-11-27 | 2015-06-10 | 삼성전자주식회사 | 시스템 온 칩 및 이에 대한 정보 처리 방법 |
| JP5175703B2 (ja) * | 2008-12-11 | 2013-04-03 | 株式会社東芝 | メモリデバイス |
| US8688894B2 (en) * | 2009-09-03 | 2014-04-01 | Pioneer Chip Technology Ltd. | Page based management of flash storage |
| KR101678868B1 (ko) | 2010-02-11 | 2016-11-23 | 삼성전자주식회사 | 플래시 주소 변환 장치 및 그 방법 |
| WO2018116105A1 (en) * | 2016-12-21 | 2018-06-28 | nChain Holdings Limited | Computer-Implemented Systems and Methods To Enable Complex Functionality On A Blockchain While Preserving Security-Based Restrictions On Script Size and Opcode Limits |
| TWI659373B (zh) * | 2018-02-14 | 2019-05-11 | 財團法人工業技術研究院 | 區塊鏈系統及應用其的方法 |
| KR102696159B1 (ko) * | 2019-12-12 | 2024-08-19 | 엘지전자 주식회사 | 펌웨어 제공 장치 및 그 제공 방법 |
| TWI821152B (zh) * | 2021-02-23 | 2023-11-01 | 慧榮科技股份有限公司 | 儲存裝置、快閃記憶體控制器及其控制方法 |
| TWI808384B (zh) * | 2021-02-23 | 2023-07-11 | 慧榮科技股份有限公司 | 儲存裝置、快閃記憶體控制器及其控制方法 |
| CN115878729B (zh) * | 2023-03-03 | 2023-05-02 | 湖北省楚天云有限公司 | 一种基于联盟链的节点区块存储分配优化方法及系统 |
| CN119668523B (zh) * | 2025-02-14 | 2025-06-03 | 合肥康芯威存储技术有限公司 | 一种存储器及其闪存块的分配方法 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100389867B1 (ko) * | 2001-06-04 | 2003-07-04 | 삼성전자주식회사 | 플래시 메모리 관리방법 |
| US7139864B2 (en) * | 2003-12-30 | 2006-11-21 | Sandisk Corporation | Non-volatile memory and method with block management system |
| JP2007280108A (ja) * | 2006-04-07 | 2007-10-25 | Sony Corp | 記憶媒体制御装置、記憶媒体制御方法、プログラム |
| US7779056B2 (en) * | 2006-09-15 | 2010-08-17 | Sandisk Corporation | Managing a pool of update memory blocks based on each block's activity and data order |
-
2007
- 2007-09-12 JP JP2009528456A patent/JP4682261B2/ja not_active Expired - Fee Related
- 2007-09-12 KR KR1020097007548A patent/KR101430097B1/ko not_active Expired - Fee Related
- 2007-09-12 WO PCT/US2007/078311 patent/WO2008033952A2/en active Application Filing
- 2007-09-14 TW TW096134607A patent/TWI340899B/zh not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| KR101430097B1 (ko) | 2014-08-13 |
| WO2008033952A2 (en) | 2008-03-20 |
| TWI340899B (en) | 2011-04-21 |
| WO2008033952A3 (en) | 2008-10-02 |
| TW200837562A (en) | 2008-09-16 |
| KR20090079197A (ko) | 2009-07-21 |
| JP2010503929A (ja) | 2010-02-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4938460B2 (ja) | 不揮発性メモリおよびブロック管理システムを伴う方法 | |
| US7774392B2 (en) | Non-volatile memory with management of a pool of update memory blocks based on each block's activity and data order | |
| JP4682261B2 (ja) | 不揮発性メモリおよびクラスベースの更新ブロック置換規則のための方法 | |
| US7779056B2 (en) | Managing a pool of update memory blocks based on each block's activity and data order | |
| US20080091871A1 (en) | Non-volatile memory with worst-case control data management | |
| US20080091901A1 (en) | Method for non-volatile memory with worst-case control data management | |
| EP1702338B1 (en) | Robust data duplication and improved update method in a multibit non-volatile memory | |
| JP2010507147A (ja) | 最悪の場合におけるデータ管理を伴う不揮発性メモリおよびそのための方法 | |
| KR20060134011A (ko) | 메모리 플레인 배열을 갖춘 비휘발성 메모리 및 방법 | |
| EP1704479B1 (en) | Non-volatile memory and method with phased program failure handling | |
| JP2007519996A6 (ja) | 不揮発性メモリおよびフェーズ化されたプログラム障害処理を伴う方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100909 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20100909 |
|
| A871 | Explanation of circumstances concerning accelerated examination |
Free format text: JAPANESE INTERMEDIATE CODE: A871 Effective date: 20100909 |
|
| A975 | Report on accelerated examination |
Free format text: JAPANESE INTERMEDIATE CODE: A971005 Effective date: 20101005 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20101207 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20101207 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20110111 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20110207 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 4682261 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140210 Year of fee payment: 3 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140210 Year of fee payment: 3 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |