(57)【特許請求の範囲】
【請求項１】
それぞれが２つ以上の物理ページを含む複数の物理グループにグループ化された複数の物理ページを含む第１の物理ブロックを備える不揮発性メモリと、
それぞれが２つ以上の論理ページを含む複数の論理グループにグループ化された複数の論理ページに対応する第１の論理ブロックを前記第１の物理ブロックにマッピングするコードデバイスと、
入力データが前記第１の論理ブロックの第１の論理グループ内の第１の論理ページに関連付けられている事に応答して、前記入力データを、前記第１の物理ブロックの第１の物理グループに含まれる第１の物理ページに書き込むコードデバイスと、を含み、
前記入力データを書き込むコードデバイスが、受信された入力データが前記第１の論理ブロックの第２の論理グループ内の第１の論理ページに関連付けられていることに応答して、第２の物理グループに含まれる第１の物理ページにも入力データを書き込み、かつ、受信された入力データが前記第１の論理グループ内の第２の論理ページと関連付けられていることに応答して、前記第１の物理ブロックの第３の物理グループ内の第２の物理ページにも入力データを書き込み、
更に、前記第１の論理グループからのデータ取り出しを要求する読み出し指令に応答して、データを、前記第３の物理グループ内の第２の物理ページ及び、前記第１の物理グループ内の第１の物理ページから取り出すコードデバイスと、
を備えるメモリ・システム。
【請求項２】
請求項１記載のメモリ・システムであって、前記第１の物理グループが、前記第１の物理グループ内の各物理ページと関連付けられた冗長領域に格納されるグループ識別子により識別され、前記取り出すコードデバイスが、
前記第１の物理グループの第１及び第２の物理ページから前記グループ識別子を取得するコードデバイスと、
前記第１及び第２の物理ページの前記グループ識別子が前記第１の論理ブロックのマッピングをマッチングしたのに応答して、前記第１及び第２の物理ページからデータを読み出すコードデバイスと、
を含むメモリ・システム。
【請求項３】
請求項１記載のメモリ・システムであって、更に、
前記コードデバイスを格納するメモリと、
前記コードデバイスを処理するプロセッサと、
を備えるメモリ・システム。
【請求項４】
請求項１記載のメモリ・システムであって、前記不揮発性メモリがフラッシュメモリであるメモリ・システム。
【請求項５】
請求項４記載のメモリ・システムであって、前記フラッシュメモリがＮＡＮＤフラッシュメモリであるメモリ・システム。
【請求項６】
請求項１記載のメモリ・システムであって、前記コードデバイスがソフトウェア・コードデバイスであるメモリ・システム。
【請求項７】
請求項１記載のメモリ・システムであって、前記コードデバイスがファームウェア・コードデバイスであるメモリ・システム。
【請求項８】
それぞれが２つ以上のページを含む複数のグループに、第１のブロック内でグループ化された複数のページを含む第１のブロックを備える不揮発性メモリと、
前記第１のブロック内の複数のグループの内の第１のグループがデータ・セットを受信するために利用可能か否かを決定するコードデバイスと、
前記第１のグループが前記データ・セットを受信するために利用可能であると決定したコードデバイスに応答して、前記データ・セットを、前記第１のグループに含まれる第１のページに書き込むコードデバイスと、
前記第１のグループが前記データ・セットを受信するために利用可能ではないと決定したコードデバイスに応答して、前記第１のブロック内の複数のグループの内の第２のグループが前記データ・セットを受信するために利用可能か否かを決定するコードデバイスと、
前記第２のグループが前記データ・セットを受信するために利用可能であると決定したコードデバイスに応答して、前記データ・セットを、前記第２のグループに含まれる第２のページに書き込むコードデバイスと、
前記第２のグループが前記データ・セットを受信するために利用可能ではないと決定されたときに、前記不揮発性メモリに含まれる第２のブロック内が前記データ・セットを受信するために利用可能か否かを決定するコードデバイスと、
前記第２のブロックが前記データ・セットを受信するために利用可能であると決定したコードデバイスに応答して、前記複数のページのうちの幾つかの内容を、前記第２のブロックにコピーするコードデバイスと、
前記第２のブロックが前記データ・セットを受信するために利用可能であると決定したコードデバイスに応答して、前記データ・セットを前記第２のブロックに書き込むコードデバイスと、
を備えるメモリ・システム。
【請求項９】
請求項８記載のメモリ・システムであって、更に、
前記第１のグループを決定するコードデバイスと、
前記第２のグループを決定するコードデバイスと、
を備えるメモリ・システム。
【請求項１０】
請求項８記載のメモリ・システムであって、前記第１のグループが前記データ・セットを受信するために利用可能なときを決定する前記コードデバイスが、前記第１のページが前記データ・セットを受信するのに適切であるか否かを決定するコードデバイスを含むメモリ・システム。
【請求項１１】
請求項８記載のメモリ・システムであって、前記データが論理ページと関連付けられ、前記第１のブロックが第１の物理ブロックであるメモリ・システム。
【請求項１２】
不揮発性メモリの第１の物理ブロックにデータを書き込むコンピュータによって実行される方法であって、前記第１の物理ブロックが、複数の物理グループにグループ化された複数の物理ページを含み、前記複数の物理グループの各物理グループが、２つ以上の物理ページを含む方法において、
それぞれが２つ以上の論理ページを含む複数の論理グループにグループ化された複数の論理ページとして構成された第１の論理ブロックを前記第１の物理ブロックにマッピングするステップと、
前記第１の論理ブロックの第１の論理グループ内の第１の論理ページと関連付けられた入力データの受信に応答して、前記第１の物理ブロックの第１の物理グループ内に含まれる第１の物理ページに前記入力データを書き込むステップと、
前記第１の論理ブロックの第２の論理グループ内の第１の論理ページと関連付けられた入力データの受信に応答して、第２の物理グループ内に含まれる第１の物理ページに前記入力データを書き込むステップと、
次に、前記第１の論理ブロックの前記第１の論理グループ内の第２の論理ページと関連付けられた入力データの受信に応答して、前記第１の物理ブロックの第３の物理グループ内に含まれる第２の物理ページに前記入力データを書き込むステップと、
次に、前記第１の論理グループからの、データ取り出しを要求する読み出し指令に応答して、データを、前記第３の物理グループ内の第２の物理ページ及び、前記第１の物理グループ内の第１の物理ページから取り出すステップと、を備える方法。
【請求項１３】
請求項１２記載の方法であって、前記第１及び第３の物理グループ内の前記第１及び第２の物理ページが、前記第１及び第２の物理ページと関連付けられた冗長領域に格納されているグループ識別子により識別される、方法。
【請求項１４】
請求項１３記載の方法であって、前記取り出すステップが、
前記第１及び第２の物理ページから、グループ識別子を取得するステップと、
前記第１及び第２の物理ページの前記グループ識別子が前記第１の論理ブロックのマッピングをマッチングしたのに応答して、前記第１及び第２の物理ページからデータを読み出すステップと
を備える方法。
【請求項１５】
不揮発性メモリに関連付けられ、２つ以上の物理ページを含む複数の物理グループ内にグループ化されている複数の物理ページを含む第１の物理ブロックにデータを書き込むコンピュータによって実行される方法であって、
論理ブロックの第１論理グループに含まれる複数の論理ページの内の１つである、第１の論理ページと関連付けられた第１のデータ・セットを識別するステップと、
前記第１の物理グループが前記第１の論理グループに関連付けられるか否か決定するステップと、
前記第１の物理グループが前記第１の論理グループと関連付けられることが決定されたことに応答して、前記第１の物理グループ内に含まれる第１の物理ページが、前記第１のデータ・セットを収容するために利用可能か否かを決定するステップと、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能であると決定されたことに応答して、前記第１のデータ・セットを、前記第１の物理ページに書き込むステップと、
前記第１の物理グループが前記第１の論理グループと関連付けられないことが決定されたことに応答して、前記第１の物理グループが利用可能であるか否かを決定するステップと、
前記第１の物理グループが利用可能であると決定されたことに応答して、前記第１の物理グループを前記第１の論理グループと関連付けるステップと、
前記第１のデータ・セットを、前記第１の物理グループと関連付けられた第２の物理ページに書き込むステップと、
を備える方法。
【請求項１６】
請求項１５記載の方法であって、更に、
前記第１の論理グループと関連付けられた第２のデータ・セットを識別するステップと、
前記第２のデータ・セットを、前記第１の物理グループと関連付けられた第３の物理ページに書き込むステップと、
を備える方法。
【請求項１７】
請求項１６記載の方法であって、更に、
前記第３の物理ページが、前記第２のデータ・セットを収容するために利用可能であるときを決定するステップであって、前記第３の物理ページが、前記第２のデータ・セットを収容するために利用可能であるとの決定に応答して、前記第２のデータ・セットが前記第３の物理ページに書き込まれるステップ
を備える方法。
【請求項１８】
不揮発性メモリに関連付けられ、前記第１の物理ブロック内の２つ以上の物理ページを含む複数の物理グループ内にグループ化されている複数の物理ページを含む第１の物理ブロックにデータを書き込むコンピュータによって実行される方法であって、
第１のデータ・セットを、論理ブロックの第１の論理グループ内に含まれる複数の論理ページの内の１つである第１の論理ページに関連付けるステップと、
前記第１の論理グループと関連付けられた前記第１の物理ブロック内の前記複数の物理グループの第１の物理グループを識別するステップと、
次に、前記第１の物理グループ内に含まれる第１の物理ページが前記第１のデータ・セットを収容するために利用可能であるか否かを決定するステップと、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能であると決定されたことに応答して、前記第１のデータ・セットを前記第１の物理ページに書き込むステップと、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能ではないと決定されたことに応答して、前記第１の物理ブロック内の前記複数の物理グループに含まれる第２の物理グループが利用可能であるか否かを決定するステップと、
次に、前記第１のデータ・セットを、前記第２の物理グループと関連付けられた第２の物理ページに書き込むステップと、
を備える方法。
【請求項１９】
請求項１８記載の方法であって、更に、
前記第２の物理グループが利用可能であるとの決定に応答して、前記第２の物理グループを前記第１の論理グループと関連付けるステップ
を備える方法。
【請求項２０】
不揮発性メモリに関連付けられ、２つ以上の物理ページを含む複数の物理グループ内にグループ化されている複数の物理ページを含む第１の物理ブロックにデータを書き込むコンピュータによって実行される方法であって、
論理ブロックの第１論理グループに含まれる複数の論理ページの内の１つである、第１の論理ページと関連付けられた第１のデータ・セットを識別するステップと、
前記第１の物理グループが前記第１の論理グループに関連付けられるか否か決定するステップと、
前記第１の物理グループが前記第１の論理グループと関連付けられることが決定されたことに応答して、前記第１の物理グループ内に含まれる第１の物理ページが、前記第１のデータ・セットを収容するために利用可能か否かを決定するステップと、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能であると決定されたことに応答して、前記第１のデータ・セットを、前記第１の物理ページに書き込むステップと、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能ではないと決定されたことに応答して、前記複数の物理グループに含まれる第２の物理グループが利用可能であるか否かを決定するステップと、
前記第１のデータ・セットを、前記第２の物理グループと関連付けられた第２の物理ページに書き込むステップと、
前記第２の物理ブロックが利用可能であると決定されたことに応答して、更に、
前記第２の物理グループが利用可能ではないと決定されたことに応答して、前記不揮発性メモリに関連付けられた第２の物理ブロックが、前記第１のデータ・セットを収容するために利用可能であるか否かを決定するステップと、
前記第１の物理ブロックに含まれる前記複数の物理ページの前記内容のいくつかを、前記第２の物理ブロックに含まれる物理ページにコピーするステップと、
前記第１のデータ・セットを、前記第２の物理ブロックと関連付けられた第３の物理ページに書き込むステップと、
を備える方法。
【請求項２１】
請求項２０記載の方法であって、更に、前記第１の物理ブロックを消去するステップを備える方法。
【請求項２２】
請求項２０記載の方法であって、前記第２の物理ブロックと関連付けられた前記第３の物理ページが、前記第２の物理ブロックに含まれる第３の物理グループの一部であり、該第３の物理グループが２つ以上の物理ページを含む方法。
【請求項２３】
請求項２２記載の方法であって、更に、前記第３の物理グループを前記第１の論理グループと関連付けるステップを含む方法。
【請求項２４】
それぞれが２つ以上の物理ページを含む複数の物理グループにグループ化された複数の物理ページを有する第１の物理ブロックを備える不揮発性メモリと、
論理ブロックの第１論理グループに含まれる複数の論理ページの内の１つである、第１の論理ページと関連付けられた第１のデータ・セットを識別し、更に、前記第１の物理グループが前記第１の論理グループに関連付けられるか否か決定し、前記第１の物理グループが前記第１の論理グループと関連付けられることが決定されたことに応答して、前記第１の物理グループ内に含まれる第１の物理ページが、前記第１のデータ・セットを収容するために利用可能か否かを決定し、そして、前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能であると決定されたことに応答して、前記第１のデータ・セットを、前記第１の物理ページに書き込むように構成されたモジュールと、
を備え、
前記モジュールが、更に、
前記第１の物理グループが前記第１の論理グループと関連付けられないことが決定されたことに応答して、前記第１の物理グループが利用可能であるか否かを決定し、前記第１の物理グループが利用可能であると決定されたことに応答して、前記第１の物理グループを前記第１の論理グループと関連付け、前記第１のデータ・セットを、前記第１の物理グループと関連付けられた第２の物理ページに書き込むよう構成されるメモリ。
【請求項２５】
請求項２４記載のメモリ・システムであって、前記モジュールが、更に、前記第１の論理グループと関連付けられた第２のデータ・セットを識別し、
前記第２のデータ・セットを、前記第１の物理グループと関連付けられた第３の物理ページに書き込むよう構成されるメモリ・システム。
【請求項２６】
請求項２５記載のメモリ・システムであって、前記モジュールが、更に、前記第３の物理ページが前記第２のデータ・セットを収容するために利用可能であるときを決定するよう構成され、前記第３の物理ページが前記第２のデータ・セットを収容するために利用可能であることが決定されたときに、前記第２のデータ・セットが前記第３の物理ページに書き込まれるメモリ・システム。
【請求項２７】
請求項２４記載のメモリ・システムであって、前記モジュールが、前記第１の物理グループから、前記第１の物理グループを識別するよう構成されたグループ識別子を取得し、該グループ識別子が前記第１の論理グループと関連付けられているか否かを決定することにより、前記第１の物理グループが前記第１の論理グループと関連付けられているか否かを決定するよう構成されるメモリ・システム。
【請求項２８】
請求項２４記載のメモリ・システムであって、前記不揮発性メモリがＮＡＮＤフラッシュメモリであるメモリ・システム。
【請求項２９】
それぞれが２つ以上の物理ページを含む複数の物理グループにグループ化された複数の物理ページを有する第１の物理ブロックを備える不揮発性メモリと、
論理ブロックの第１論理グループに含まれる複数の論理ページの内の１つである、第１の論理ページと関連付けられた第１のデータ・セットを識別し、更に、前記第１の物理グループが前記第１の論理グループに関連付けられるか否か決定し、前記第１の物理グループが前記第１の論理グループと関連付けられることが決定されたことに応答して、前記第１の物理グループ内に含まれる第１の物理ページが、前記第１のデータ・セットを収容するために利用可能か否かを決定し、そして、前記第１の物理ページが前記第１のデータ・セットを収容するために利用可能であると決定されたことに応答して、前記第１のデータ・セットを、前記第１の物理ページに書き込むように構成されたモジュールと、
を備え、
前記モジュールが、更に、
前記第１の物理ページが前記第１のデータ・セットを収容するために利用不可能であることが決定されたことに応答して、前記複数の物理グループ内に含まれる第２の物理グループが利用可能であるか否かを決定し、前記第２の物理グループが利用可能であると決定されたことに応答して、前記第２の物理グループを前記第１の論理グループと関連付け、前記第１のデータ・セットを、前記第２の物理グループと関連付けられた第２の物理ページに書き込むよう構成され、
更に、第２の物理ブロックを備え、前記モジュールが、更に、
前記第２の物理グループが利用可能ではないと決定されたことに応答して、前記不揮発性メモリと関連付けられた前記第２の物理ブロックが、前記第１のデータ・セットを収容するために利用可能であるときを決定し、前記第２の物理ブロックが利用可能であると決定されたことに応答して、前記第１の物理ブロックに含まれる前記複数の物理ページの内容のいくつかを、前記第２の物理ブロックに含まれる物理ページにコピーし、前記第２の物理ブロックが利用可能であると決定されたことに応答して、前記第１のデータ・セットを、前記第２の物理ブロックと関連付けられた第３の物理ページに書き込むよう構成されるメモリ・システム。
【請求項３０】
請求項２９記載のメモリ・システムであって、前記モジュールが、更に、前記第１の物理ブロックを消去するよう構成されるメモリ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本発明は、「不揮発性記憶システムにおける劣化の平準化」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，７３９号、「不揮発性メモリ・システムにおける最も頻繁に消去されるブロックの追跡」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，６７０号、「不揮発性メモリ・システムにおける最も消去されないブロックの追跡」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，８２４号、「論理ブロックをスプリットする方法及び装置」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，６３１号、「共通論理ブロックに関連付けられている物理ブロックを解決するための方法及び装置」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，７６２号、「不揮発性記憶システムにおける消去カウントの保持」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，６９６号、「消去カウント・ブロックを管理する方法及び装置」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，６２６号、及び「不揮発性メモリにおける複数ページの読み取り及び書き込み操作を実行する方法及び装置」という名称の２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，８０４号と関連し、これらの出願はそれぞれ、参照により全体が本明細書に援用される。
【０００２】
発明の背景
１．発明の分野
本発明は、一般に、大容量デジタル・データ記憶システムに関する。より詳細には、本発明は、フラッシュメモリのブロックに効率的に書き込みを行うシステム及び方法に関する。
【０００３】
２．関連技術の説明
フラッシュメモリ記憶システムのような不揮発性メモリ・システムは、物理的サイズが小さく、不揮発性メモリが繰返しプログラムされる能力を有するために、利用が増加している。フラッシュメモリ記憶システムの小さな物理的サイズのおかげで、急速に普及しつつあるデバイス内で、そのような記憶システムを簡単に利用することができる。フラッシュメモリ記憶システムを利用するデバイスには、デジタルカメラ、デジタルカムコーダ、デジタル音楽プレーヤー、携帯型パソコン、及び全地球位置測位システムが含まれるが、それらに限定されるものではない。フラッシュメモリ記憶システムに含まれる不揮発性メモリは繰返し再プログラムできるため、フラッシュメモリ記憶システムを再利用することができる。
【０００４】
一般に、フラッシュメモリ記憶システムは、フラッシュメモリ・カード及びフラッシュメモリ・チップセットを含む。フラッシュメモリ・チップセットは、一般に、フラッシュメモリ部品及びコントローラ部品を含む。典型的に、フラッシュメモリ・チップセットは、組み込みシステム内に組み込まれるよう構成される。このような組立て体又はホスト・システムのメーカーは、典型的に、フラッシュメモリを他の部品と一緒に部品の形態で入手し、フラッシュメモリと他の部品とをホスト・システムに組立てる。
【０００５】
図１ａに示すように、ファイル・システム内において、メモリ１０は、システム又はディレクトリ領域１２とデータ領域１４とに効果的に分割される。システム領域１２は、一般に、ルート・ディレクトリと、ファイル・アロケーション・テーブル（ＦＡＴ）とを備え、データ・ファイルは典型的にはデータ領域１４に含まれる。ファイル・システムは、システム領域１２に対しては、データをセクタ単位で、例えば一度に１ページずつ書き込むことができるが、データ領域１４に対しては、データをクラスタ単位で、例えば一度に複数ページずつ書き込むことができる。一般的にはデータ領域１４と関連付けられるファイルの最小サイズである、各クラスタのサイズは、異なり得る。例えば、ウィンドウズ（登録商標）又はＤＯＳシステムを実行するシステムの全体において、クラスタは、約４〜２５６ページを含むサイズとされる。
【０００６】
論理ブロック、即ちファイル・システムと関連付けられたブロックに関連する任意の更新は、物理ブロックが論理ブロックにマッピングされるフラッシュメディアへと、効果的に伝播される。図１ｂは、フラッシュメディアの論理ブロックと物理ブロックとの間のマッピングの図表表現である。論理ブロック５２は、それぞれが物理ブロック５４のページにマッピグされる複数のページを含み、論理ブロック５２に関連付けられたページが更新されると、物理ブロック５４に更新が書き込まれる。
【０００７】
例えば論理ページであるページが更新されると、該ページが関連付けられている物理ブロックに書き込みがなされる。従来、ブロックは、「固定的な」方法又は「ランダムな」方法により書き込まれ得る。ブロックが固定的な方法で書き込まれる場合、ページは、ブロックの対応するページ・オフセットに書き込まれる。図２ａに示すように、論理ブロック・ページ２１４が更新される場合、論理ブロック・ページ２１４に関連付けられた内容は、一般的には、物理ブロック２１０内の対応するページ２１８に書き込まれる。例えば、論理ブロック・ページ２１４が物理ブロック・ページ２１８ｈと対応し、物理ブロック・ページ２１８ｈが利用可能である場合、論理ブロック・ページ２１４の内容が物理ブロック・ページ２１８ｈに書き込まれ得る。物理ブロック・ページ２１８ｈが利用可能である場合、ブロック２１０には、物理ブロック・ページ２１８ｈより上のページ番号を有するページであって、書き込まれたページ２１８が有効に存在しないことがわかる。
【０００８】
ブロック２１０に書き込まれたページ２１８であって、書き込まれるべき内容を有する論理ブロック・ページよりも高いページ番号を持つページが存在している場合、ブロック２１０が固定的な方法で書き込まれるように構成されると、論理ブロック・ページの内容は、ブロック２１０に書き込まれない。より高いページ番号がフラッシュメモリに書き込まれた後で、より低いページ番号を書き込むことは、「順序を外れた」書き込み処理になる。当業者に理解されるように、フラッシュメモリによっては、この種の処理を許していない。そのため、論理ブロック・ページの内容は、ページ２１８の内容とともに、新しいブロックに書き込まれる。図２ｂは、例えば図２ａのブロック２１０のような古いブロックと、古いブロックの内容を収容するよう構成された新しいブロックとの図表表現である。論理ブロック・ページ２３４の内容が固定的な方法で物理ブロックに書き込まれる場合、ブロック２１０即ち現在のブロックが書き込まれてよいか否かが決定される。論理ページ２３４が、ブロック２１０において利用可能なページよりも低いページ番号を有する場合、論理ページ２３４の内容はブロック２１０に書き込まれない。言い換えれば、論理ブロック２３４と対応するページ・オフセットを有する物理ページ２１８が、例えば既に書き込まれていて利用可能ではない場合、一般に、論理ページ２３４の内容を書き込み可能とするために新しい物理ページ２３０が入手される必要がある。
【０００９】
論理ブロック２３４は、物理ブロック２１０のページ２１８ｃに対応するため、ブロック２３０が入手される際、ページ２１８の内容は、一般に、ページ２１８ｃの内容を除いて、物理ブロック２３０の対応するページ２３８にコピーされる。ページ２１８ｃの内容をページ２３８ｃにコピーする代わりに、論理ブロック２３４の内容がページ２３８ｃにコピーされる。従って、コピー又は書き込みの処理の後に、ページ２３８ａ、ページ２３８ｂ、及びページ２３８ｄ〜２３８ｇは、それぞれ、ページ２１８ａ、ページ２１８ｂ、及びページ２１８ｄ〜２１８ｇの内容を含むが、ページ２３８ｃは論理ページ２３４と関連付けられた内容を含む。ブロック２３０に書き込まれた後で、ブロック２１０は消去されてもよい。
【００１０】
対応するページ・オフセットを有するページが、書き込まれるページに対するブロックにおいて利用可能である場合、固定的な方法でのブロックへの書き込みは、一般に効率的である。しかし、対応するページ・オフセットを有するページが、書き込まれるために利用可能ではない場合、ブロック内に利用可能なページがあるとしても、一般的に、書き込み処理を完了させるためには、新しいブロックが取得されなければならない。新しいブロックの取得は、かなりの量の計算のオーバーヘッドを消費し、典型的には、新しいブロックに内容をコピーするコピー処理、及び古いブロックを消去する消去処理が実行されなければならない。当業者に理解されるように、このような処理、特に書き込み及び消去の処理は、比較的費用がかかる。
【００１１】
固定的な方法即ちブロックへの固定的な書き込みの代わりに、ブロックにデータを書き込むランダムな方法が実現され得る。ランダムな方法でブロックへの書き込みが為される場合、任意の論理ページと実質的に関連付けられた内容は、ブロック内の次に利用可能なページ・スペースに書き込まれる。図３において、ブロックにデータを書き込むランダムな方法が説明される。論理ブロック・ページ３１４の内容が物理ブロック３１０に書き込まれ、ブロック３１０内に利用可能なページ３１８がある場合、論理ブロック・ページ３１４の内容は、次に続く利用可能なページ３１８に書き込まれる。例えば、論理ページ３１４ａの内容はページ３１８ｈに書き込まれ、論理ページ３１４ｂの内容はページ３１８ｉに書き込まれる。
【００１２】
論理ページ３１４ｂがページ３１８ｃに対応するとしても、ページ３１８ｉがブロック３１０において次に利用可能なページである場合には、論理ページ３１４ｂの更新された内容はページ３１８ｉに書き込まれることが理解されるべきである。論理ページ３１４がどうしても読み取られる必要がある場合、一般には、ブロック３１０内において、論理ページ３１４ｂと関連付けられた最新の内容を含むものとして、ページ３１８ｉを特定する必要がある。図示される通り、ページ３１８ｉがブロック３１０の最後のページである場合、論理ページ３１４ｂと関連付けられた内容を含むものとしてページ３１８ｉを特定するためには、ブロック３１０の全てを読む必要があり、従って、比較的多数の読み出し処理が必要となる。論理ページ３１４ｂと関連付けられた内容にアクセスするためにブロック３１０の実質的に全てを読み取るのは、比較的時間がかかるかもしれない。論理ページ３１４のような論理ページと関連付けられた内容の位置を特定しアクセスするために必要な読み取り処理の回数を減らすよう、全体システムのメモリ又はフラッシュメモリを利用して、ページ３１８及びページ３１８の内容に関する情報を得る技術があるが、そのような技術は、全体システムの、より詳細には、全体システムで実行するソフトウェアのメモリ要件を増大させる。
【００１３】
従って、物理ブロックと関連付けられたページを、効率的に書き込み、アクセスすることを可能とするハイブリッドな方法及び装置が望ましい。つまり、比較的頻繁なブロックの消去や比較的多くの読み込み処理を実質的に行わずに、ブロック内のページが効率的に書き込まれ、容易にアクセスされるようにするために、固定及びランダムの両方の処理を利用するハイブリッドなシステムが求められている。
【００１４】
発明の概要
本発明は、ブロック内のページに効率的にアクセスできるようにするシステム及び方法に関する。本発明の１つの態様によれば、不揮発性メモリの第１のブロックにデータを書き込む方法であって、第１のブロックが、複数のグループにグル−プ化された複数のページを含み、複数のグループのそれぞれが、２つ又はそれ以上のページを含む方法において、複数のグループのうちの第１のグループが、データを受信するために利用可能であるときを決定するステップを含む方法が提供される。第１のグループがデータを受信するために利用可能であると決定されたとき、第１のグループに含まれる第１のページにデータが書き込まれる。該方法は、また、第１のグループがデータを受信するために利用可能ではないと決定された場合に、複数のグループのうちの第２のグループが、データを受信するために利用可能であるときを決定するステップと、第２のグループがデータを受信するために利用可能であると決定されたときに、第２のグループに含まれる第２のページにデータを書き込むステップとを備える。
【００１５】
１つの実施の形態において、該方法は、また、第２のグループがデータを受信するために利用可能ではないと決定された場合に、データを受信するために第２のブロックが利用可能であるときを決定するステップを備える。もう１つの実施の形態において、データは論理ページと関連付けられ、第１のブロックは第１の物理ブロックである。
【００１６】
ページが書き込まれる際に、新しい物理ブロックの代わりに物理ブロック内のページのグループが得られるよう、ブロック内のページをグループ化することは、ページ書き込みに関する全体としての効率性を改良する。言い換えれば、新しいブロック内のグループが利用可能である可能性があるために、データを書き込むために新しいブロックが入手されなければならない可能性を低減することができる。そのため、書き込み処理がより効率的になる。少なくとも、例えば新しいブロックが入手された後でブロックを消去するために利用される消去処理のような消去処理の発生が、かなり低減され得るからである。更に、特定のページの位置を特定するためにブロック全体を読み取る代わりに、特定のページを特定するためにグループが調べられるため、特定のページに格納されたデータのセットを読み取る読み取り処理がより効率的になる。例えば、ページのグループが特定のページを含まないと決定される場合、該グループのページを個別に読み取る必要はない。即ち、実質的には、特定のページを含むグループのページだけを読み取ればよい。グループの概念を適用することにより、読み取り処理は、有効にランダムな方法において発生する読み取り処理よりも高速になる。それは、実質的に、同一のグループのページのみを調べればよいからである。グループの概念と関連づけられた書き込み処理は、従来の固定的な処理よりも高速である。単一の物理ブロックにおいて、書き込まれるべきページに対して、より多くの場所があるからである。従って、新しいブロックを割当てて古いブロックを消去する必要性が低減される。
【００１７】
本発明のもう１つの態様によれば、不揮発性メモリの一部であるメモリ・ブロックは、少なくとも第１のページ・セットと第２のページ・セットとに分割された複数のページを含む。メモリ・ブロックは、また、第１のグループを含む。第１のグループは第１のページ・セットを含み、第１のグループを識別し第１のグループに格納される第１のグループ識別子を有する。更に、メモリ・ブロックは、また、第２のグループを含み、該グループは、第２のページ・セットを含み、第２のグループを識別する第２のグループ識別子を有する。第２のグループ識別子は第２のグループに格納される。１つの実施の形態において、第１のページ・セットに含まれるページの順序は、実質的に、第１のグループの始まりに対して固定されており、第２のページ・セットに含まれるページの順序は、実質的に、第２のグループの始まりに対して固定されている。
【００１８】
本発明の更にもう１つの態様によれば、不揮発性メモリの第１の物理ブロックにデータを書き込む方法であって、第１の物理ブロックが、２つ又はそれ以上の物理ページからなる複数の物理グループにグループ化された複数の物理ページを含む方法が提供される。該方法は、第１の論理ページと関連付けられた第１のデータ・セットを識別するステップと、複数の物理グループのうちの第１の物理グループが第１の論理グループと関連付けられているときを決定するステップとを含む。第１の論理ページは、論理ブロックの第１の論理グループに含まれる複数の論理ページのうちの１つである。該方法は、また、第１の物理グループが第１の論理グループと関連付けられることが決定された場合に、第１の物理グループに含まれる第１の物理ページが、第１のデータ・セットを収容するために利用可能であるときを決定するステップと、第１の物理ページが第１のデータ・セットを収容するために利用可能であると決定された場合に、第１のデータ・セットを第１の物理ページに書き込むステップとを備える。
【００１９】
１つの実施の形態によれば、第１の物理ブロックにデータを書き込む方法は、また、第１の物理ページが第１のデータ・セットを収容するために利用可能ではないことが決定された場合に、複数の物理グループに含まれる第２の物理グループが利用可能であるときを決定するステップと、第１のデータ・セットを第２の物理グループと関連付けられた第２の物理グループに書き込むステップとを備える。そのような実施の形態において、該方法は、更に、第２の物理グループが利用可能ではないと決定された場合に、不揮発性メモリと関連付けられた第２の物理ブロックが、第１のデータ・セットを収容するために利用可能であるときを決定するステップを備える。
【００２０】
本発明の上記の及び他の利点は、以下の詳細な説明を読み、図面の様々な図表を検討することにより明らかになる。
発明の詳細な説明
本発明は、添付の図面とともに以下の説明を参照することにより最も良く理解される。
【００２１】
更新されたページの格納又は書き直しに必要とされるオーバーヘッド及び時間の全体量を低減することにより、例えば、組み込み型不揮発性メモリ・チップを備える全体ホスト・システムのような全体システムを、一層効率的に動作させることが可能となる。ページが他の最近書き込まれたページよりも低いページ番号を有する場合に、物理ブロックと関連付けられたページが更新されるたびに新しい物理ブロックを取得することは、かなりの量のシステム資源を消費し、結果として、比較的非効率的になり得る。一方、実質的に任意のページをブロックの次に利用可能なスペースに書き込めるようにすると、結果として、特定のページの位置を特定するために、過剰な数の読み取り処理が実行されることになり得る。
【００２２】
物理ブロック内に少なくとも１つの利用可能なグループがある場合に、物理ブロックにページを書き込むために、新しい物理ブロックの代わりに物理ブロック内のグループが取得されるようブロック内でページをグループ化することにより、ページの書き込みに関する全体の効率が一般に改良され得る。言い換えれば、新しいブロック内のグループが利用可能である可能性があるために、データの書き込みを可能とするために新しいブロックが取得されなければならない可能性が低減される。グループ又はサブ・ブロックを利用することにより、ブロックは、一般に、一層効率的に割当てられる。
【００２３】
物理ブロック内のページのグループ化の恩恵を受けることができるフラッシュメモリ・システム、又は、より詳細には、不揮発性メモリ・デバイスは、一般に、フラッシュメモリ・カード及びチップ・セットを含む。典型的に、フラッシュメモリ・システムは、ホスト・システムがフラッシュメモリ・システムにデータを書き込み、又はフラッシュメモリ・システムからデータを読み出すよう、ホスト・システムと組み合せて利用される。しかし、幾つかのフラッシュメモリ・システムは、図４ｃを用いて以下に説明するように、組み込み型フラッシュメモリと、実質的に組み込み型フラッシュメモリのコントローラとして動作するようホスト上で実行するソフトウェアとを含む。図４ａは、例えばコンパクトフラッシュ（登録商標）・メモリ・カードのような不揮発性メモリ・デバイスを含む一般的なホスト・システムを示す。ホスト又はコンピュータ・システム１００は、一般に、マイクロプロセッサ１０８、ランダム・アクセス・メモリ（ＲＡＭ）１１２、入出力回路１１６が通信することを可能とするシステム・バス１０４を含む。ホスト・システム１００は、一般に、例えば説明のために図示されていないディスプレイ装置やネットワーク装置のような、他の要素を含み得ることが理解されるべきである。
【００２４】
一般に、ホスト・システム１００は、静止画情報、音声情報及びビデオ画像情報を含むがそれらに限定されない情報を取得することが可能である。そのような情報は、リアルタイムで取得され、無線によりホスト・システム１００に送信される。ホスト・システム１００は実質的に任意のシステムであってよく、典型的には、デジタル・カメラ、ビデオ・カメラ、無線通信端末、オーディオ・プレーヤー、又はビデオ・プレーヤーである。しかし、ホスト・システム１００は、一般に、実質的には、データ又は情報を格納し取り出す任意のシステムであってよいことが理解されるべきである。
【００２５】
ホスト・システム１００は、また、データを取得するのみ、又はデータを取り出すのみのシステムであってもよい。つまり、ホスト・システム１００は、１つの実施の形態において、データを格納する専用のシステムであってもよく、又は、データを読み取る専用のシステムであってもよい。例として、ホスト・システム１００は、データを書き込み又は蓄積するためだけに構成されるメモリ・ライターであってもよい。代わりに、ホスト・システム１００は、典型的にはデータの読み取り又は取り出しのために構成され、データの取得のためには構成されないＭＰ３プレーヤーのような装置であっても良い。
【００２６】
１つの実施の形態においては取り外し可能な不揮発性メモリ・デバイスである不揮発性メモリ・デバイス１２０は、バス１０４とインターフェースをとって情報を格納するよう構成される。インターフェース・ブロック１３０は、オプションとして、不揮発性メモリ１２０がバス１０４と間接的にインターフェースをとることを可能とする。入出力回路ブロック１１６が存在する場合、該回路は、当業者に理解されるように、バス１０４へのローディングを低減するよう動作する。不揮発性メモリ・デバイス１２０は、不揮発性メモリ１２４と、オプションとしてのメモリ制御システム１２８とを含む。１つの実施の形態において、不揮発性メモリ・デバイス１２０は、単一のチップ又はダイ上で実現される。代わりに、不揮発性メモリ・デバイス１２０は、マルチ・チップ・モジュールにより、又は、チップ・セットを形成し不揮発性メモリ・デバイス１２０とともに利用される複数の別個の部品により実現される。不揮発性メモリ・デバイス１２０の１つの実施の形態を、図４ｂに関して、以下により詳細に説明する。
【００２７】
例えばＮＡＮＤフラッシュメモリのようなフラッシュメモリなどの不揮発性メモリ１２４は、データが必要に応じてアクセスされ、読み取られるように、データを記憶するよう構成される。不揮発性メモリ１２４のデータには消去不可能なものもあるが、不揮発性メモリ１２４に記憶されたデータは、適切に消去されてもよい。データを記憶し、読み取り、消去する処理は、一般に、メモリ制御システム１２８により制御されるか、メモリ制御システム１２８がない場合には、マイクロプロセッサ１０８により実行されるソフトウェアにより制御される。不揮発性メモリ１２４の動作は、不揮発性メモリ１２４のセクションを実質的に等しく劣化させることにより、不揮発性メモリ１２４の寿命が実質的に最大化されるよう管理される。
【００２８】
不揮発性メモリ・デバイス１２０を、一般に、オプションとしてのメモリ制御システム１２８即ちコントローラを含むものとして説明した。不揮発性メモリ・デバイス１２０は、大抵の場合、不揮発性メモリ１２４の機能と、メモリ制御システム１２８即ちコントローラの機能とのために、別個のチップを含み得る。例えば、ＰＣカード、コンパクトフラッシュ（登録商標）・カード、マルチメディア・カード、及びセキュア・デジタル・カードを含むがそれらに限定されない不揮発性メモリ・デバイスは、別個のチップで実現されるコントローラを含み、他の不揮発性メモリ・デバイスは、別個のチップで実現されるコントローラを含まない。不揮発性メモリ・デバイス１２０がメモリとコントローラとの別個のチップを含まない実施の形態において、メモリ及びコントローラの機能は、当業者に理解されるように、単一のチップに統合されてもよい。代わりに、メモリ制御システム１２８の機能は、例えば、不揮発性メモリ・デバイス１２０がメモリ・コントローラ１２８を含まない上記の実施の形態のように、マイクロプロセッサ１０８により提供されてもよい。
【００２９】
図４ｂは、不揮発性メモリ・デバイス１２０を、本発明の１つの実施の形態に従って、より詳細に説明する。上記の通り、不揮発性メモリ・デバイス１２０は不揮発性メモリ１２４を含み、更にメモリ制御システム１２８を含んでもよい。例えばメモリ１２４が組み込み型ＮＡＮＤデバイスである場合には、不揮発性メモリ・デバイス１２０は制御システム１２８を含まなくてもよいが、メモリ１２４と制御システム１２８即ちコントローラとは、不揮発性メモリ・デバイス１２０の主要部品であり得る。メモリ１２４は、半導体基板上に形成されたメモリ・セルのアレイであり、メモリ・セルの個々の記憶素子に２つ又はそれ以上のレベルの電荷のうちの１つを格納することにより、個々のメモリ・セルに１つ又はそれ以上のビットのデータが格納される。不揮発性のフラッシュの電気的消去可能プログラム可能読み取り専用メモリ（ＥＥＰＲＯＭ）は、そのようなシステムに利用される一般的なメモリの種別の一例である。
【００３０】
制御システム１２８は、存在する場合に、バス１５を介してホスト・コンピュータと、又はデータ記憶のためにメモリ・システムを用いる他のシステムと通信する。バス１５は、一般に、図４ａのバス１０４の一部である。制御システム１２８は、また、メモリ・セル・アレイ１１を含むメモリ１２４の動作を制御して、ホストが提供するデータを書き込み、ホストが要求するデータを読み出し、メモリ１２４を動作させる際に様々なハウスキーピング機能を実行する。制御システム１２８は、一般に、関連付けられた不揮発性ソフトウェア・メモリ、様々な論理回路、及びそれらに類するものを有する汎用マイクロプロセッサを含む。また、特定のルーチンの性能を制御するために、しばしば、１つ又はそれ以上の状態機器を含む。
【００３１】
メモリ・セル・アレイ１１は、典型的に、アドレス・デコーダ１７を介して、制御システム１２８又はマイクロプロセッサ１０８によりアドレス指定される。デコーダ１７は、制御システム１２８によりアドレス指定されるメモリ・セルのグループにデータをプログラムし、該グループからデータを読み取り、該グループを消去するために、アレイ１１のゲート及びビット線に適切な電圧を印加する。追加の回路１９は、セルのアドレス指定されたグループにプログラムされているデータに応じて、アレイの素子に印加される電圧を制御するプログラミング・ドライバを含み得る。回路１９は、また、メモリ・セルのアドレス指定されたグループからデータを読み取るために必要なセンスアンプ及び他の回路を含み得る。アレイ１１にプログラムされるデータ、又はアレイ１１から最近読み出されたデータは、図示される通り制御システム１２８内に置かれるバッファ・メモリ２１に格納される。制御システム１２８は、また、命令及び状態データを一時的に格納するための様々なレジスタ、及びそれに類するものを含み得る。
【００３２】
アレイ１１は、多数のブロック０〜Ｎのメモリ・セルに分割される。フラッシュＥＥＰＲＯＭに一般的であるように、ブロックは消去の最小単位である。つまり、各ブロックは、一緒に消去される最小数のメモリ・セルを含む。各ブロックは、典型的に、幾つかのページに分割される。当業者が理解するように、ページは、プログラミングの最小単位であり得る。つまり、基本的なプログラム動作は、メモリ・セルの最低でも１ページにデータを書き込み、最低でも１ページからデータを読み取る。典型的に、各ページには、データの１つ又はそれ以上のセクタが格納される。図４ｂに示す通り、１つのセクタはユーザ・データ及びオーバーヘッド・データを含む。オーバーヘッド・データは、典型的に、該セクタのユーザ・データから算出されたエラー訂正コード（ＥＣＣ）を含む。制御システム１２８の部分２３は、データがアレイ１１にプログラムされる際にＥＣＣを計算し、アレイ１１からデータが読み取られる際にＥＣＣを検査する。代わりに、ＥＣＣは、関連するユーザ・データとは別のページ又は別のブロックに格納されてもよい。
【００３３】
ユーザ・データのセクタは、典型的に、磁気ディスク・ドライブのセクタ・サイズに対応する５１２バイトである。説明している実施の形態において、オーバーヘッド・データは、典型的に、追加の１６バイトである。データの１つのセクタが１ページに含まれることが最も一般的ではあるが、代わりに、２つ又はそれ以上のセクタが１ページを形成してもよい。一般に、任意の数のページがブロックを形成することが可能である。例えば、ブロックは、８ページから５１２、１０２４又はそれ以上までのページにより形成されることが可能である。ブロックの数は、メモリ・システムが所望のデータ記憶容量を提供するよう選択される。アレイ１１は、典型的には、幾つかのサブ・アレイ（図示せず）に分割され、該サブ・アレイは、様々なメモリ操作の実行における並列度を高めるために、互いに或る程度独立して動作するある割合のブロックを含む。複数のサブ・アレイを利用する例は、参照により全体が本明細書に援用される米国特許第５，８９０，１９２号に記載されている。
【００３４】
１つの実施の形態において、不揮発性メモリは、例えばホスト・システムのようなシステムに埋め込まれる。図４ｃは、組み込み型不揮発性メモリを含むホスト・システムを図示する。ホスト又はコンピュータ・システム１５０は、一般に、ホスト・システム１５０の他の要素（図示せず）の中でもマイクロプロセッサ１５８、ＲＡＭ１６２及び入出力回路１６６が通信することを可能にするシステム・バス１５４を含む。
【００３５】
フラッシュメモリなどの不揮発性メモリ１７４により、ホスト・システム１５０に情報を蓄積することが可能となる。インターフェース１８０は、不揮発性メモリ１７４とバス１５４との間に提供されて、不揮発性メモリ１７４からの情報の読み取り、及び不揮発性メモリ１７４への情報の書き込みを可能とする。
【００３６】
不揮発性メモリ１７４は、不揮発性メモリ１７４を制御するよう構成されたソフトウェア及びファームウェアのいずれか又は両方を有効に動作させるマイクロプロセッサ１５８により管理される。つまり、マイクロプロセッサ１５８は、例えばソフトウェア・コードデバイス又はファームウェア・コードデバイスのような、不揮発性メモリ１７４を制御するコードデバイス（図示せず）を実行する。そのようなコードデバイスは、マイクロプロセッサ１５８内部のＣＰＵとともにパッケージ化されたフラッシュメモリであっても、別個のフラッシュＲＯＭであっても、以下に記載される内部の不揮発性メモリ１７４であってもよく、不揮発性メモリ１７４の物理ブロックがアドレス指定されることを可能とし、情報を該物理ブロックに格納し、該ブロックから読み出し、該ブロックから消去することを可能とする。
【００３７】
一般に、データを書き込む際、ユーザは、ファイル・システムを利用してデータを有効に書き込む。ファイル・システムは、データを、論理ブロックと関連付け、より詳細には、記憶媒体と関連付けられた物理ブロックにマッピングされた論理ブロックのページと関連付ける。図５は、本発明の１つの実施の形態に従って、論理ブロックを備えるファイル・システムと、物理ブロックを備える媒体とを図示する。ファイル・システム５１４の論理ブロック５１０は、任意の数のページ５１８を含む。例えば論理ブロック５１０ａである論理ブロックに含まれるページ５１８の数は、消去ユニットのサイズに依存する。例えば、最小消去ユニットが約３２ページを含む場合、図示した通り、約３２ページが論理ブロック５１０ａに含まれる。
【００３８】
組み込み型フラッシュメモリのような媒体５３４の物理ブロック５３０は、幾つかのページ５３８を含む。当業者が理解するように、物理ブロック５３０に含まれるページ５３８の数は、典型的に、論理ブロック５３０に含まれるページ５１８の数と同じである。
【００３９】
図５に関して以下に説明する通り、データ・マネージャ又はデータ管理ソフトウェアを利用することにより、論理ブロック５１０が物理ブロック５３０にマッピングされる。論理ブロック５１０と物理ブロック５３０とのマッピングは、それぞれ１対１のマッピングであり、即ち、論理ブロックアドレスにおける第１の論理ブロック５１０が、実質的に論理ブロックアドレスと同じである物理ブロックアドレスにある第１の物理ブロック５３０ａにマッピングされる。しかし、論理ブロック５１０と物理ブロック５３０とのマッピングでは、大抵の場合、論理ブロックアドレスにおける第１の論理ブロック５１０ａは、第１の物理ブロック５３０ａにマッピングされず、代わりに、例えば物理ブロック５３０ｃのような、論理ブロック・アドレスとは異なる物理ブロックアドレスを有する別の物理ブロックにマッピングされるようになる。
【００４０】
例えば、論理ブロックは論理ページ０〜３１と対応付けられ、物理ブロックは物理ページ０〜３１と対応付けられるように、論理ブロックと関連付けられたページアドレスのセットは、物理ブロックと関連付けられたページアドレスのセットと全て有効に対応するが、所与の論理ページアドレスと対応付けられた内容は、必ずしも、対応する物理ページアドレスに置かれるわけではない。論理ブロックと関連付けられて格納され、物理的には物理ブロックに格納される所望の内容へのアクセスを促進するために、ブロックと関連付けられたページは、複数のグループ又はサブ・ブロックにグループ化される。論理ブロックと関連付けられたページ及び物理ブロックと関連付けられたページのいずれか又は両方は、グループ又はユニットにグループ化される。図６は、本発明の１つの実施の形態に従ってグループに配置されたページを備えるブロックを図示する。ブロック６００はページ６０４を含む。ブロック６００は一般に、任意の数のページ６０４を含み得ることが理解されるべきである。
【００４１】
ページ６０４はグループ６０８に配置される。一般に、ブロック６００内のグループ６０８の数、及びグループ６０８内のページ６０４の数は、広範に変更することが可能である。典型的に、グループ６０８内のページ６０４の数は、実質的に任意のクラスタ・サイズを収容可能となるよう選択される。例えば、幾つかのシステムにおいて、クラスタ・サイズは約４ページ６０４であり得る。クラスタ・サイズが約４ページ６０４であるとき、グループ６０８内のページ６０４の数は４の倍数になり得る。例えば、グループ６０８ごとに４又は８個のページ６０４があり得る。
【００４２】
当業者に理解されるように、クラスタは、一般に、ファイルの最小サイズと考えられる。従って、ファイル・システムが実質的に１バイトのみをファイルに書き込もうとする場合でも、当該ファイルにはクラスタ全体が有効に割当てられる。以降のファイルは、典型的に、他のクラスタに書き込まれる。
【００４３】
図６に戻って、図示されている実施の形態において、個々のグループ６０８は、４つのページ６０４を含む。各グループ６０８内のページ６０４の順序は、各グループ６０８の始まりについて固定されている。例えば、グループ６０８ａ内のページ６０４ａ〜ｄの順序は、グループ６０８ｂにおけるページ６０４ｅ〜ｈと同様に固定されている。各グループ６０８内におけるページ６０４の順序は、各グループ６０８の始まりについて固定されているが、ブロック６００内のグループ６０８の順序は一般に固定されていない。
【００４４】
個々の論理ページ及び物理ページは、一般に、冗長領域及びデータ領域を含む。説明されている実施の形態において、冗長領域即ちオーバーヘッド領域は、特定のページが所属するグループを識別するバイトであるグループ識別子を含むがそれに限定されない、約１６バイトまでの情報を含む。図７は、本発明の実施の形態に従うページの図表表現である。ページ７００は、冗長領域７０６及びデータ領域７１０を含む。一般に、ページ７００は約５２８バイトを含み、そのうちの約１６バイトが冗長領域７０６に含まれ、約５１２バイトがデータ領域７１０に含まれる。冗長領域７０６はページ７００の最後のバイトに関連付けられてもよいが、図示されている実施の形態において、冗長領域７０６はページ７００の最初のバイトに関連付けられる。
【００４５】
データ領域７１０は、例えばユーザ・データの内容であるデータ内容７１２を格納するよう構成される。冗長領域７０６は、ページ７００を追跡可能とする情報を含むよう構成される。例えば、冗長領域７０６は、ページ７００がその一部となるグループ、即ちブロック内のグループを識別するグループ識別子７１４を含む。グループの識別を促進するために、グループ識別子７１４は、冗長領域７０６と関連付けられた最初のバイト、即ちページ７００と関連付けられた最初のバイトであってよい。
【００４６】
グループ識別子７１４が特定のグループの識別子と合致するまでページ７００が読み取られないような場合、典型的に、グループ識別子７１４が読み取られ、例えば、グループ識別子７１４が特定のグループと関連付けられた識別子と合致するか否かを決定する全体システム内のソフトウェア又はファームウェアを用いて、チェックがなされる。グループ識別子７１４はページ７００と関連付けられた最初のバイトであるため、グループ識別子７１４の読み取りは、比較的小さなオーバーヘッドを要求し、比較的効率的である。グループ識別子７１４が特定のグループの識別子と合致する場合、冗長領域７０６の残りとともにデータ７１２が読み取られる。一方、グループ識別子７１４が特定のグループの識別子と合致しない場合、データ７１２及び冗長領域７０６の残りは読み取られない。
【００４７】
実質的にグループ識別子７１４が特定のグループの識別子と合致する場合にのみ、ページ７００と関連付けられた全ビットを読み取ることにより、グループ識別子７１４が特定のグループの識別子と合致しない場合に、約５２７バイトのデータの送信と典型的に関連付けられる送信時間を、実質的に削減することができる。言い換えれば、グループ識別子７１４が特定のグループの識別子と合致しない場合、ページ７００の残りのバイトの読み取り又は送信と関連付けられる時間が、有効に削減される。
【００４８】
代わりに、例えばグループ識別子７１４が特定のグループの識別子と合致する場合のように、残りのバイトが読み取られるべきである場合、アクセス時間、即ちデータの読み取り命令が発行されてからデータがフラッシュメモリから転送される用意ができるまでに経過する時間は、有効に節約される。冗長領域７０６は、データ領域７１０の後に置かれても良い。冗長領域７０６がデータ領域７１０の後に置かれる場合、読み取り処理が最適化されないとしても、上記の通りブロックの消去処理の数が少なくなるために、一般に、書き込み処理の性能は高められる。
【００４９】
図８ａは、本発明の実施の形態に従ってそれぞれグループに分割される論理ブロック及び物理ブロックの図表表現である。論理ブロック８０２及び物理ブロック８０６は、それぞれ、グループ８１０及びグループ８１４に均等に分割される。１つの実施の形態において、グループ８１０、８１４の数は、典型的に２の累乗である。例えば、論理ブロック８０２には、１、２、４又は８個のグループ８１０があり得る。
【００５０】
論理ブロック８０２及び物理ブロック８０６は、それぞれ３２個のページを含むが、論理ブロック８０２及び物理ブロック８０６内のページ数は大幅に変わり得ることが理解されるべきである。論理ブロック８０２の各グループ８１０は８個のページを含み、例えば、グループ８１０ｃは８個のページ８２６を含む。物理ブロック８０６の各グループ８１４は８個のページを含み、例えばグループ８１４ａは８個のページ８３４を含む。典型的には、グループ８１０、８１４のそれぞれにおけるページの順序は、実質的に固定されている。例えば、グループ８１０ｃにおいて、第１のページ８２６ａは実質的に「ページ０」として固定され、８番目のページ８２６ｈは実質的に「ページ７」として固定される。このように、グループ８１４ａが「グループ０」でありグループ８１４ｄが「グループ３」であるようにグループ８１４が並べられている場合、物理ブロック８０６全体としての「ページ３０」への書き込みは、グループ８１４ｄの「ページ６」８４６ｇへの書き込みと実質的に同じである。
【００５１】
一般に、物理ブロック８０６内のグループ８１４の順序は、ランダムであってよい。グループ８１４の実際のグループ番号は、図７について先に論じた通り、ページの冗長領域に格納される。グループ８１４ａのページ８３４に格納されるグループ番号は、ページ８３４を、グループ８１４ａに含まれるものとして識別するよう構成される。同様に、ページ８３８に格納されたグループ番号は、ページ８３８を、グループ８１４ｂに含まれるものとして識別し、ページ８４２に格納されたグループ番号は、ページ８４２を、グループ８１４ｃに含まれるものとして識別し、ページ８４６に格納されたグループ番号は、ページ８４６を、グループ８１４ｄに含まれるものとして識別する。
【００５２】
図示される通り、物理グループ８１４ａ即ち物理「グループ０」におけるページ８３４のデータ領域は、論理グループ８１０ｄと関連付けられたデータを格納するよう構成される。物理グループ８１４ｃのページ８４２は、また、論理グループ８１０ｄと関連付けられたデータを格納するよう構成される。論理グループ８１０ｃと関連付けられたデータは、物理グループ８１４ｂのページ８３８のデータ領域に格納されるよう構成される。特に、図示されている実施の形態において、論理グループ８１０ｄと関連付けられたデータは物理グループ８１４ａに書き込まれ、論理グループ８１０ｃと関連付けられたデータは物理グループ８１４ｂに書き込まれる。物理グループ８１４ｂが書き込まれた後、論理グループ８１０ｄと関連付けられたデータは、再び、今度は物理グループ８１４ｃに書き込まれる。
【００５３】
図８ｂは、本発明の実施の形態に従って、物理ブロック８０６の物理ブロック８１４が、グループの関連付けが図８ａに示された通りになるよう書き込まれる例を図示する。ユーザは、８６０に示されるように、論理グループ８１０ｄの論理「ページ１」８３０ｂと関連付けられたデータを、物理グループ８１４ａに、より詳細には物理グループ８１４ａの物理「ページ１」８３４ｂに書き込むよう選択し得る。物理「ページ１」８３４ｂが書き込まれると、ユーザは、８６２に示すように、論理「ページ３」８３０ｄと関連付けられたデータを、物理グループ８１４ａの物理「ページ３」８３４ｄに書き込み得る。
【００５４】
次のユーザ命令が、論理グループ８１０ｃと関連付けられたデータを書き込むものである場合、追加のページ８３４が物理グループ８１４ａ内で利用可能であったとしても、論理グループ８１０ｃと関連付けられたデータは、実質的に空の物理グループ８１４、又は実質的に消去された状態である物理グループ８１４に書き込まれる。例えば、グループ８１０ｃの論理「ページ２」８２６ｃと関連付けられたデータは、８６４に示すように、グループ８１４ｂの物理「ページ２」８３８ｃに書き込まれる。論理グループ８１０ｃと関連付けられた他のページは、８６６及び８６８に示す通り、グループ８１４ｂに書き込まれる。
【００５５】
論理ブロック８１０ｃと関連付けられたデータが書き込まれた後で、ユーザは、論理ブロック８１０ｄと関連付けられたデータを再び書き込むことを決定し得る。そのため、グループ８１０ｄの論理「ページ５〜７」８３０ｆ〜ｈと関連付けられたデータは、８７０、８７２、８７４に示される通り、グループ８１４ｃの適切な物理ページ８４２に書き込まれる。典型的に、論理「ページ５〜７」８３０ｆ〜ｈと関連付けられたデータは、物理グループ８１４ａには書き込まれない。なぜなら、物理グループ８１４ｂが既に書き込まれているという事実のために順序を外れた書き込み違反が発生するからであり、グループ８１４ｂの後にグループ８１４ａへ書き込むことは一般的には許可されないからである。結果として、論理グループ８１０ｄと関連付けられたデータは、物理グループ８１４ａ及び物理グループ８１４ｃに配置される。
【００５６】
論理ブロック８０２と関連付けられた、より高い全体論理ブロックアドレスと関連付けられたデータは、より低い全体論理ブロックアドレスと関連付けられたデータよりも、低い全体物理ブロックアドレスを有する物理ブロック８０６の物理ページに格納されてもよい。例えば、論理ページ８３０ｂと関連付けられた全体論理ブロックアドレスは、論理ページ８２６ｃと関連付けられた全体論理ブロックアドレスより高くても良いが、論理ページ８３０ｂと関連付けられた内容は、論理ページ８２６ｃと関連付けられた内容が書き込まれる物理ページ８３８ｃより低い全体物理ブロックアドレスを有し得る物理ページ８３４ｂに書き込まれてもよい。
【００５７】
先に書き込まれたページが上書きされる場合、例えば、論理「ページ１」８３０ｂが「ページ１」８３４に書き込まれ、物理グループ８１４ｂが書き込まれた後のいずれかの時点に、論理「ページ１」８３０ｂと関連付けられたデータが物理グループ８１４ｄ（図示せず）に書き込まれる場合、「ページ１」８３４ｂのデータ領域に格納された内容は無効と考えられる。そのため、論理「ページ１」８３０ｂと関連付けられた内容を検索する命令は、対応する物理ページが見つかるまで物理ブロック８０６を有効に逆方向に検索する。言い換えれば、物理グループ８１４ｄが最初に検索され、物理グループ８１４ｃ、物理グループ８１４ｂ、及び物理グループ８１４ａが続いて検索される。逆方向の検索は、一般に、最新のデータへのアクセスを可能とする。
【００５８】
図示される通り、物理グループ８１４ａ〜ｃが書き込まれた後、物理グループ８１４ｄは、実質的に割当てられずに残される。論理グループ８１０ｂが書き込まれる場合、論理グループ８１０ｂと関連付けられたデータは、物理グループ８１４ｄに書き込まれる。つまり、物理グループ８１４ｄは、図８ｃに示す通り、論理グループ８１０ｂに有効に割当てられる。論理グループ８１０ｂと関連付けられたデータは、物理グループ８１４ｄに書き込まれ、論理グループ８１０ｃと関連付けられたデータは、物理グループ８１４ｂに書き込まれる。論理グループ８１０ｄは、物理グループ８１４ａ及び物理グループ８１４ｃと関連付けられる。
【００５９】
物理グループ８１４ｄが論理グループ８１０ｂに割当てられ、論理グループ８１０ｂと関連付けられたデータが物理グループ８１４ｄのデータ領域に書き込まれる場合、論理グループ８１０ｄと関連付けられたデータが再度書き込まれる際には、データを書き込んでもよい利用可能な物理グループ８１４は存在しない。そのため、新しい、例えば予備の物理ブロックが、論理ブロック８０２に対応する物理ブロックとなるよう有効に取得される。言い換えれば、例えば現在の物理ブロックである物理ブロック８０６と関連付けられた実質的に全ての現在のデータと、新しいユーザ・データとが新しい物理ブロックに統合されるよう、新しい物理ブロックが割当てられる。
【００６０】
図８ｄは、本発明の１つの実施の形態に従う統合処理の後における、論理ブロック即ち図８ａ〜ｃの論理ブロック８０２と、新しい物理ブロックとの関連付けを図示する。図８ｃの物理ブロック８０６の内容と、論理ブロック８０２と関連付けられた新しいユーザ・データとが、新しい物理ブロック８８０に統合される場合、例えば有効に上書きされたページのような、空のページ及び無効なページは、新しい物理ブロック８８０に書き込まれないことが理解されるべきである。更に、図８ｃの物理ブロック８０６に利用可能なスペースがないために新しい物理ブロック８８０が割当てられることを促したデータのような新しいデータは、新しいデータと対応する既存のデータを効果的に無効とする。即ち、新しいデータは、新しいデータと同じ論理ページに関連付けられた既存のデータを無効とする。
【００６１】
統合が起こって新しいデータが新しい物理ブロック８８０に書き込まれると、論理ブロック８０２と新しい物理ブロック８８０との関連付けは、論理ブロック８０２のグループ８１０ｂと関連付けられたデータが物理グループ８８４ａに格納され、論理ブロック８０２のグループ８１０ｃと関連付けられたデータが物理グループ８８４ｂに格納され、論理ブロック８０２のグループ８１０ｄと関連付けられたデータが物理グループ８８４ｃに格納されるようになる。物理グループ８８４ｄは、物理グループ８８４ｄが必要とされるまで、実質的に消去状態に留まる。当業者に理解されるように、データが統合され、又は新しい物理ブロック８８０に書き込まれると、図８ａの元の物理ブロック８０６は消去され、予備の物理ブロックとして利用可能にされる。
【００６２】
ページと関連付けられたグループ識別子にアクセスする読み取り処理が一層効率的に行われるようにするため、現在のブロック内のページが読み取られ又は書き込まれる際に、現在作業中のブロック情報のテーブルが、例えば図４ｃのＲＡＭ１６２に構築される。図９は、本発明の実施の形態に従う現在作業中のブロックの情報テーブルの図表表現である。情報テーブル９５０は、グループ番号９５４を格納するよう構成される。ページが読み取られると、そのページのグループ番号９５４が情報テーブル９５０に格納される。グループ番号９５４を格納することは、典型的に、同じブロック、即ちグループ番号９５４が情報テーブル９５０に格納されているページを含むブロックへの次回の読み取り要求に対して、読み取り回数を低減するために役立つ。典型的に、実質的に現在作業中のブロックに関する情報は、情報テーブル９５０に保持される。全体システムにおけるＲＡＭ要求を実質的に最小化するため、情報テーブル９５０は、現在アクセスされているブロックについてのみ構築されてもよい。別のブロックがアクセスされた場合、情報テーブル内にある情報は、新しいブロックの情報により有効に置換される。
【００６３】
図１０ａ及び１０ｂは、論理グループの一部である論理ページと関連付けられた内容を、物理グループの一部である物理ページに書き込む１つの方法と関連付けられたステップを、本発明の１つの実施の形態に従って図示する。内容を物理ページに書き込む処理１０００は、物理ページに書き込まれるべき内容が識別されるステップ１００４において開始する。つまり、書き込まれるべき新しいデータであって、例えば論理ページ「Ａ」である論理ページと関連付けられるデータが、取得又は識別される。
【００６４】
書き込まれるべき内容が識別されると、ステップ１００８において、論理ページ「Ａ」と対応する物理グループがあるか否かが決定される。言い換えれば、論理ページ「Ａ」、又は、より一般的には論理ページ「Ａ」を含む論理グループが、最後に割当てられた又は関連付けられた物理グループと同一であるか否かが決定される。最後に割当てられた物理グループが論理ページ「Ａ」を含むことが決定されると、ステップ１０１２において、割当てられた物理グループにおいて、論理ページ「Ａ」と関連付けられた内容を書き込むことができる適切なページが利用可能であるか否かが決定される。適切なページがあるか否かの決定には、論理ページ「Ａ」と関連付けられた内容が割当てられた物理グループに書き込まれる場合に、順番を外れた書き込み違反が起こるか否かの決定が含まれ得る。決定には、また、論理ページ「Ａ」と関連付けられた内容にとって利用可能である割当てられた物理グループに、書き込まれていないページがあるか否かの決定が含まれ得る。
【００６５】
ステップ１０１２において、割当てられた物理グループに対し適切なページが利用可能であることが決定されると、論理ページ「Ａ」と関連付けられたデータ又は内容は、ステップ１０１６において適切なページに書き込まれる。データを物理ページに書き込むために、実質的に任意の適切な方法が利用されてもよい。データが書き込まれると、データを物理グループの物理ページに書き込む処理が完了する。
【００６６】
代わりに、ステップ１０１２において、割当てられた物理グループにおいて適切なページが利用可能ではないことが決定されると、割当てられた物理グループのページが一杯であるか、又は、順番外れの書き込み違反を起こさないような適切なページが利用可能ではないことが示される。そのため、処理の流れはステップ１０１２から１０２０へ進み、物理ブロック内に利用可能な物理グループがあるか否かが決定される。言い換えれば、ステップ１０２０において、物理ブロック内に、まだ特定の論理グループと関連付けられていないグループがあるか否かが決定される。
【００６７】
利用可能な物理グループがあると決定された場合、利用可能な物理グループは、ステップ１０２４において、論理ページ「Ａ」を含む論理グループに有効に割当てられる。利用可能な物理グループが論理グループに割当てられると、論理ページ「Ａ」と関連付けられたデータ又は内容は、ステップ１０２８において、新しく割当てられた物理グループの適切なページに書き込まれる。データが書き込まれると、物理グループの物理ページにデータを書き込む処理が完了する。
【００６８】
ステップ１０２０、及び、論理ページ「Ａ」に割り当てられた物理ブロック内に利用可能な物理グループがあるか否かの決定に戻って、適切な物理グループがないと判断された場合、論理ページ「Ａ」と関連付けられたデータ又は内容が、物理ブロック即ち現在の物理ブロックに書き込まれないかもしれないことが示される。そのため、処理の流れはステップ１０３２に進み、利用可能な予備の物理ブロックがあるか否かが決定される。利用可能な予備の物理ブロックがないと決定されると、ステップ１０３６において、論理ページ「Ａ」と関連付けられたページが書き込まれないことを示す例外が投げられる。例外が投げられると、データを物理グループの物理ページに書き込む処理は終了し、典型的には失敗の表示が報告される。コントローラのソフトウェア又はファームウェアの設計により、通常、フラッシュメモリの寿命がすっかり終わるまで利用されない限り、このような状況が実質的に発生しないよう防止される。
【００６９】
一方、ステップ１０３２において、予備の物理ブロックが利用可能であると決定されると、予備の物理ブロックは、ステップ１０４０において、論理ページ「Ａ」を含む論理ブロックに利用されるよう割当てられる。その後、ステップ１０４４において、論理ページ「Ａ」を含む論理ブロックに先に割当てられた「古い」物理ブロックからの有効なデータは、「新しい」即ち予備の物理ブロック内のグループと統合される。加えて、新しいデータ、即ちステップ１００４において取得された論理ページ「Ａ」と関連付けられた内容は、予備の物理ブロックと関連付けられたグループのページに書き込まれる。古い物理ブロックからの有効なデータが予備の物理ブロックに統合された後、ステップ１０４８において、古い物理ブロックが消去される。古い物理ブロックの消去は、例えば古い物理ブロックが実質的に寿命の終わりに到達していない場合に、古い物理ブロックが実質的に予備の物理ブロックとして利用されることを可能とする。古い物理ブロックが消去されると、物理グループの物理ページへのデータの書き込み処理が終了する。
【００７０】
一般に、ブロック内のページのグループ化と関連付けられる機能は、例えばプログラム・コードデバイス又はホスト・システムに対するファームウェアとして、ソフトウェアにより提供される。劣化の平準化を可能とするために、ホスト・システムに提供されるソフトウェア又はファームウェアと関連付けられた適切なシステム構造の１つの実施の形態が、図１１に示される。システム構造９００は、一般に、アプリケーション・インターフェース・モジュール９０４、システム・マネージャ・モジュール９０８、データ・マネージャ・モジュール９１２、データ保全マネージャ９１６、及びデバイス・マネージャ／インターフェース・モジュール９２０を含み得るがそれらに限定されない様々なモジュールを含む。一般に、システム構造９００は、例えば図４ａのプロセッサ１０８のようなプロセッサによりアクセスされ得るソフトウェア・コードデバイス又はファームウェアを用いて実現される。
【００７１】
一般に、アプリケーション・インターフェース・モジュール９０４は、ホスト、オペレーティング・システム又は直接にユーザと通信するよう構成される。アプリケーション・インターフェース・モジュール９０４は、また、システム・マネージャ・モジュール９０８及びデータ・マネージャ・モジュール９１２とも通信する。ユーザがフラッシュメモリの読み取り、書き込み又はフォーマットを要望する際、ユーザは、オペレーティング・システムに要求を送信し、該要求はアプリケーション・インターフェース・モジュール９０４に渡される。アプリケーション・インターフェース・モジュール９０４は、該要求を、要求に応じてシステム・マネージャ・モジュール９０８又はデータ・マネージャ・モジュール９１２に渡す。
【００７２】
システム・マネージャ・モジュール９０８は、システム初期化サブモジュール９２４、消去カウント・ブロック管理サブモジュール９２６、及び電力管理ブロック・サブモジュール９３０を含む。システム初期化サブモジュール９２４は、一般に、初期化要求が処理されることを可能とするよう構成され、典型的には、消去カウント・ブロック管理サブモジュール９２６と通信する。消去カウント・ブロック管理サブモジュール９２６は、ブロックの消去カウントを格納する機能と、個々の消去カウントを用いて平均消去カウントを計算し更新する機能とを含む。消去カウントの使用は、参照により全文が本明細書に援用される、２００２年１０月２８日出願に係る係属中の米国特許出願第１０／２８１，７３９号に記載されている。
【００７３】
アプリケーション・インターフェース・モジュール９０４と通信することに加え、システム・マネージャ・モジュール９０８は、データ・マネージャ・モジュール８１２及びデバイス・マネージャ／インターフェース・モジュール９２０とも通信する。システム・マネージャ・モジュール９０８及びアプリケーション・インターフェース・モジュール９０４と通信するデータ・マネージャ・モジュール９１２は、論理セクタを物理セクタへと有効に変換するセクタ・マッピングを提供する機能を含む。つまり、データ・マネージャ・モジュール９１２は、論理ブロックを物理ブロックにマッピングするよう構成される。データ・マネージャ・モジュール９１２は、オペレーティング・システムとファイル・システムとのインターフェース層と関連付けられた機能を含み、ブロック内のグループの管理を可能とする。
【００７４】
システム・マネージャ・モジュール９０８、データ・マネージャ９１２、及びデータ保全マネージャ９１６と通信するデバイス・マネージャ／インターフェース・モジュール９２０は、典型的に、フラッシュメモリ・インターフェースを提供し、例えば入出力インターフェースのようなハードウェア抽象化に関連付する機能を含む。データ保全マネージャ・モジュール９１６は、他の機能と共に、ＥＣＣ処理を提供する。
【００７５】
本発明の幾つかの実施の形態のみを説明したが、本発明は、本発明の趣旨又は範囲を逸脱することなく、多くの他の具体的な形態で実現可能であることが理解されるべきである。例えば、論理ブロック内の論理グループと、物理ブロック内の対応する物理グループとは、実質的に同じサイズであるものとして説明されたが、論理グループと物理グループとは一般にサイズが異なってもよい。言い換えれば、論理グループに含まれるページ数と、該論理グループに対応する物理グループに含まれるページ数とは、必ずしも同じではない。
【００７６】
本発明の様々な方法と関連付けられたステップは、広範に変更されることが可能である。一般に、ステップを追加、削除、再順序付け又は変更してもよい。従って、本例は、例示であって限定的ではないと考えられるべきであり、本発明は、本明細書で与えられた詳細に限定されるものではなく、特許請求の範囲以内において修正されることが可能である。
【図面の簡単な説明】
【００７７】
【図１ａ】図１ａは、ファイル・システムにより有効に分割されたメモリを図示する。
【図１ｂ】図１ｂは、論理ブロックと物理ブロックとのマッピングを図示する。
【図２ａ】図２ａは、論理ブロックが固定的な方法である場合に、関連づけられた内容を収容するよう構成された物理ブロックを図示する。
【図２ｂ】図２ｂは、例えば図２ａのブロック２１０のような古い物理ブロックと、古いブロックの内容を収容するよう構成された新しい物理ブロックとを図示する。
【図３】図３は、論理ブロックと関連づけられた内容がランダムな方法で書き込まれる物理ブロックを図示する。
【図４ａ】図４ａは、不揮発性メモリを含む一般的なホスト・システムを図示する。
【図４ｂ】図４ｂは、例えば図４ａのメモリ・デバイス１２０であるメモリ・デバイスを図示する。
【図４ｃ】図４ｃは、組み込み型不揮発性メモリを含むホスト・システムを図示する。
【図５】図５は、本発明の１つの実施の形態に従った、論理ブロックを備えるファイル・システムと、物理ブロックを備えるメディアとを図示する。
【図６】図６は、本発明の１つの実施の形態に従ってグループに構成されたページを備えるブロックを図示する。
【図７】図７は、本発明の１つの実施の形態に従ったページを図示する。
【図８ａ】図８ａは、本発明の１つの実施の形態に従ってそれぞれ複数のグループに分割される、論理ブロック及び物理ブロックを図示する。
【図８ｂ】図８ｂは、論理ブロック及び物理ブロック、即ち図８ａの論理ブロック８０２及び物理ブロック８０６を図示し、本発明の１つの実施の形態に従って、物理ブロック内のグループが書き込まれる方法を示す。
【図８ｃ】図８ｃは、論理ブロック及び物理ブロック、即ち図８ａの論理ブロック８０２及び物理ブロック８０６を図示し、ブロック内のグループが、本発明の実施の形態に従って関連付けられる方法を示す。
【図８ｄ】図８ｄは、本発明の１つの実施の形態に従う統合処理の後の論理ブロック即ち図８ａ〜ｃの論理ブロック８０２と、物理ブロックとの関連づけを図示する。
【図９】図９は、本発明の１つの実施の形態に従う、現在の作業ブロック情報テーブルを図示する。
【図１０ａ】図１０ａは、本発明の１つの実施の形態に従って、論理グループの一部である論理ページと関連づけられた内容を、物理グループの一部である物理ページに書き込む１つの方法と関連づけられたステップを示す処理フロー図である。
【図１０ｂ】図１０ｂは、本発明の１つの実施の形態に従って、論理グループの一部である論理ページと関連づけられた内容を、物理グループの一部である物理ページに書き込む１つの方法と関連づけられたステップを示す処理フロー図である。
【図１１】図１１は、本発明の１つの実施の形態に従うシステム構造のブロック図である。
【図１ａ】
0004611024.tif 000002
【図１ｂ】
0004611024.tif 000003
【図２ａ】
0004611024.tif 000004
【図２ｂ】
0004611024.tif 000005
【図３】
0004611024.tif 000006
【図４ａ】
0004611024.tif 000007
【図４ｂ】
0004611024.tif 000008
【図４ｃ】
0004611024.tif 000009
【図５】
0004611024.tif 000010
【図６】
0004611024.tif 000011
【図７】
0004611024.tif 000012
【図８ａ】
0004611024.tif 000013
【図８ｂ】
0004611024.tif 000014
【図８ｃ】
0004611024.tif 000015
【図８ｄ】
0004611024.tif 000016
【図９】
0004611024.tif 000017
【図１０ａ】
0004611024.tif 000018
【図１０ｂ】
0004611024.tif 000019
【図１１】
0004611024.tif 000020