(57)【特許請求の範囲】
【請求項１】
コンピュータのメモリ・デバイスに関するメモリ管理システムであって、
書き込みのために複数のフリー・メモリ・ブロックを含むフリー・ブロック・データ構造を備え、
前記フリー・ブロック・データ構造がブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序で前記フリー・メモリ・ブロックをソートし、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を個別に受信するように構成され、新しいユーザ書き込み要求からのユーザ書き込みデータがより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若いフリー・メモリ・ブロックに配置され、再配置要求からの再配置データが前記最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置されるようになっており、
前記フリー・ブロック・データ構造からの前記ユーザ書き込みデータを保持するユーザ書き込みメモリ・ブロックを受信するように構成されたユーザ書き込みデータ構造と、
前記フリー・ブロック・データ構造からの前記再配置データを保持する再配置メモリ・ブロックを受信するように構成された再配置データ構造と、
消去のために前記ユーザ書き込みブロックおよび再配置ブロックのうちの少なくとも１つを選択するように構成されたガーベッジ・コレクション・プール構造とをさらに備え、
前記選択されたブロックは消去されると前記フリー・ブロック・データ構造に移動される、メモリ管理システム。
【請求項２】
前記ユーザ書き込みデータ構造内の前記ユーザ書き込みメモリ・ブロックが最も大きい残存未消費耐久サイクル・カウントを有し、前記再配置データ構造内の前記再配置メモリ・ブロックが最も小さい残存未消費耐久サイクル・カウントを有する、請求項１記載のシステム。
【請求項３】
前記選択されたブロックが所定のルールに基づいてガーベッジ・コレクションのために選択される、請求項１記載のシステム。
【請求項４】
前記選択されたブロックがユーザ書き込みメモリ・ブロックのウインドウおよび再配置メモリ・ブロックのウインドウから選択される、請求項３記載のシステム。
【請求項５】
前記ユーザ書き込みメモリ・ブロックの前記ウインドウのサイズが前記再配置メモリ・ブロックの前記ウインドウのサイズと等しい、請求項４記載のシステム。
【請求項６】
前記ユーザ書き込みメモリ・ブロックの前記ウインドウのサイズが前記再配置メモリ・ブロックの前記ウインドウのサイズと等しくない、請求項４記載のシステム。
【請求項７】
コンピュータのメモリ・デバイスに関するメモリ管理システムであって、
書き込みのために複数のフリー・メモリ・ブロックを含むフリー・ブロック・データ構造を備え、
前記フリー・ブロック・データ構造がブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序で前記フリー・メモリ・ブロックをソートし、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を受信するように構成され、新しいユーザ書き込み要求からのユーザ書き込みデータがより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若いフリー・メモリ・ブロックに配置され、再配置要求からの再配置データが前記最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置されるようになっており、
前記フリー・ブロック・データ構造からの前記ユーザ書き込みデータを保持するメモリ・ブロックと前記フリー・ブロック・データ構造からの前記再配置データを保持するメモリ・ブロックとを受信し、ガーベッジ・コレクションの候補として直ちに選択されないように前記メモリ・ブロックを遅延させるように構成された遅延ブロック・データ構造と、
前記遅延ブロック・データ構造からメモリ・ブロックを受信し、消去のために前記メモリ・ブロックのうちの少なくとも１つを選択するように構成されたガーベッジ・コレクション・プール構造とをさらに備え、
前記選択されたメモリ・ブロックは消去されると前記フリー・ブロック・データ構造に移動される、メモリ管理システム。
【請求項８】
前記遅延ブロック・データ構造が先入れ先出し（ＦＩＦＯ）待ち行列である、請求項７記載のシステム。
【請求項９】
ユーザ書き込みページを保持するメモリ・ブロックまたは再配置データ・ページを保持するメモリ・ブロックのいずれかが前記遅延ブロック・データ構造の一方の側で受信され、ユーザ書き込みページを保持するメモリ・ブロックまたは再配置データ・ページを保持するメモリ・ブロックのいずれかが前記遅延ブロック・データ構造の反対側で前記遅延ブロック・データ構造から押し出されて前記ガーベッジ・コレクション・プール構造に押し込まれる、請求項８記載のシステム。
【請求項１０】
メモリ・デバイス内のメモリ・ブロックを管理するコンピュータによって実装される方法であって、
ブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序で書き込みのためにフリー・メモリ・ブロックを維持管理し、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を受信することと、
前記新しいユーザ書き込み要求からのユーザ書き込みデータをより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若いフリー・メモリ・ブロックに配置することと、
前記再配置書き込み要求からの再配置データを前記最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置することと、
前記ユーザ書き込みデータを保持するユーザ書き込みメモリ・ブロックと前記再配置データを保持する再配置メモリ・ブロックを維持管理することと、
消去のために前記ユーザ書き込みメモリ・ブロックまたは前記再配置メモリ・ブロックのうちの少なくとも１つを選択することを含む、方法。
【請求項１１】
前記ユーザ書き込みメモリ・ブロックまたは前記再配置メモリ・ブロックのうちの少なくとも１つを選択することが、
個別に管理されているユーザ書き込みメモリ・ブロックのウインドウおよび再配置メモリ・ブロックのウインドウから少なくとも１つのメモリ・ブロックを選択することを含む、請求項１０記載の方法。
【請求項１２】
前記ユーザ書き込みメモリ・ブロックまたは前記再配置メモリ・ブロックのうちの少なくとも１つを選択することが、
ユーザ書き込みメモリ・ブロックと再配置メモリ・ブロックの組み合わせによって形成されたウインドウから少なくとも１つのメモリ・ブロックを選択することを含む、請求項１０記載の方法。
【請求項１３】
前記ユーザ書き込みメモリ・ブロックの前記ウインドウのサイズが前記再配置メモリ・ブロックの前記ウインドウのサイズと等しい、請求項１１記載の方法。
【請求項１４】
前記ユーザ書き込みメモリ・ブロックの前記ウインドウのサイズが前記再配置メモリ・ブロックの前記ウインドウのサイズと等しくない、請求項１１記載の方法。
【請求項１５】
請求項１０ないし請求項１４の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ・ストレージ・デバイスに関し、より具体的には、データ配置（data placement）、ガーベッジ・コレクション（garbage collection）、および摩耗平準化（wear-leveling）プロセスを介してフラッシュベースのソリッド・ステート・ドライブ（ＳＳＤ）デバイスの書き込み−消去耐久寿命（write-erase endurance lifetime）を改善するためのメモリ管理システムおよび方法に関する。
【背景技術】
【０００２】
現在、ＮＡＮＤフラッシュ・メモリに基づくＳＳＤデバイスは、ノートブックからエンタープライズ・ストレージ・システムに及ぶコンピュータ・アーキテクチャにおいて１次ストレージとして使用されている。これらのデバイスは、回転式のハード・ディスク（ＨＤＤ）より数桁分優れたランダム入出力パフォーマンスおよびアクセス待ち時間を提供する。その上、ＳＳＤは、電力消費量を著しく低減し、頑強性および耐衝撃性を劇的に改善する。ＮＡＮＤフラッシュ・メモリはブロック単位で編成され、各ブロックは固定数のページで構成され、そのブロックは消去動作用の基本単位であり、読み取りおよび書き込みはページ単位で処理される。あるブロック内のあるページにデータを書き込む前に（そのページはそのデータでプログラミングされる）、そのブロックをあらかじめ消去しなければならない。ＳＳＤにおいて消去単位としてより大きいブロックを有し、読み取りおよび書き込み単位としてより小さいページを有することにより、「書き込み増幅（write amplification）」が発生し、サービス・ユーザ（servicing user）がホスト・システムから書き込むときにＳＳＤはオーバヘッド・ハウスキーピング書き込みを行わなければならない。ＮＡＮＤフラッシュ・メモリでは、書き込み−消去サイクル・カウントが限られている。典型的に、単一レベル・セル（ＳＬＣ）に基づくフラッシュ・チップは１０５のプログラム消去サイクルに耐え、マルチレベル・セル（ＭＬＣ）に基づくフラッシュ・チップは１０４のプログラム消去サイクルに耐える。
【０００３】
フラッシュ・メモリは、たとえば、パフォーマンス上の理由で書き込み時再配置（relocate-on-write）（すなわち、非所定位置書き込み（out-of-place write））を使用する。その代わりに所定位置書き込み（write-in-place）を使用する場合、データが更新されるブロック全体の読み取り、消去、および再プログラミング（すなわち、書き込み）が必要であるためにフラッシュは長い待ち時間を示すことになる。非所定位置更新の管理は、各ユーザ・ページ書き込みに割り当てられる論理ブロック・アドレス（ＬＢＡ）とフラッシュ・メモリ内の物理ページ・アドレスである物理ブロック・アドレス（ＰＢＡ）とのマッピングを伴う。
【０００４】
書き込み時再配置はガーベッジ・コレクション・プロセスを必要とし、その結果、追加の読み取りおよび書き込み動作に関するパフォーマンス上のペナルティが発生する。ガーベッジ・コレクションの結果として行われる読み取りおよび書き込み動作の数はブロック使用率によって決まる。
【０００５】
フラッシュ・メモリ・ブロックは、もはや消去または書き込みできなくなるまで書き込み−消去サイクルの数が増進することによって最終的に摩耗する。したがって、可能な限り多くのユーザ書き込みに対応するために（すなわち、耐久性を最大限にするために）可能な限り多くのブロックからなるサイクル予算を使い果たすように摩耗平準化技法が使用される。「摩耗平準化不足（wear-leveling insufficiency）」と呼ばれるように、ガーベッジ・コレクションがもはやフリー・ブロックを返せなくなったときに、ＳＳＤデバイスはいくつかの未消費サイクル予算を残して最終的に動かなくなる可能性がある。
【０００６】
フラッシュ・メモリ・ブロックの不均一な摩耗は主に作業負荷における空間的局所性による。ブロックの摩耗は徐々にアンバランスな状態が増してくる。新しいブロックから古いブロックへコールド・データ（cold data）（すなわち、頻繁に更新されないデータ）のマイグレーションを強制的に行い、ホット・データ（hot data）を保持するためにより新しいブロックを解放することにより不均一な摩耗のこの原因に対処するために、静的摩耗平準化が一般的に使用される。静的摩耗平準化による書き込み増幅の増加は、どのくらい頻繁にコールド・データが動き回るかによって決まる。ユーザ書き込みに加えて、ガーベッジ・コレクションと摩耗平準化の両方が書き込み動作に寄与し、このため、対応可能なユーザ書き込みの総数によって測定することができる書き込み−消去耐久寿命は、使用可能な全サイクル予算、書き込み増幅、ならびに摩耗平準化不足により最終的に未消費のサイクル予算によって決まる。
【０００７】
現在では、摩耗平準化は、フラッシュベースのＳＳＤデバイスの耐久寿命を改善するための標準的な方法として認識されている。しかし、ＳＳＤデバイスの耐久寿命は、摩耗平準化だけでなく、データ配置およびガーベッジ・コレクションにも依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、データ配置、ガーベッジ・コレクション、および摩耗平準化プロセスを介してフラッシュベースのＳＳＤの書き込み−消去耐久寿命を改善する方法およびシステムを提供する。
【課題を解決するための手段】
【０００９】
本発明の一実施形態により、コンピュータのメモリ・デバイスに関するメモリ管理システムが提供される。このシステムは、書き込みのために複数のフリー・メモリ・ブロックを含むフリー・ブロック・データ構造を備え、このフリー・ブロック・データ構造はブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序でフリー・メモリ・ブロックをソートするように構成される。フリー・ブロック・データ構造は、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を個別に受信するようにさらに構成され、新しいユーザ書き込み要求からのユーザ書き込みデータがより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若い（youngest）フリー・メモリ・ブロックに配置され、再配置要求からの再配置データが最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置されるようになっている。このシステムは、フリー・ブロック・データ構造からのユーザ書き込みデータを保持するユーザ書き込みメモリ・ブロックを受信するように構成されたユーザ書き込みデータ構造と、フリー・ブロック・データ構造からの再配置データを保持する再配置メモリ・ブロックを受信するように構成された再配置データ構造と、消去のためにユーザ書き込みブロックおよび再配置ブロックのうちの少なくとも１つを選択するように構成されたガーベッジ・コレクション・プール構造とをさらに備え、選択されたブロックは消去されるとフリー・ブロック・データ構造に移動される。
【００１０】
本発明の他の実施形態により、コンピュータのメモリ・デバイスに関するメモリ管理システムが提供される。このシステムは、書き込みのために複数のフリー・メモリ・ブロックを含むフリー・ブロック・データ構造を備え、このフリー・ブロック・データ構造はブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序でフリー・メモリ・ブロックをソートするように構成される。また、フリー・ブロック・データ構造は、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を受信するように構成され、新しいユーザ書き込み要求からのユーザ書き込みデータがより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若いフリー・メモリ・ブロックに配置され、再配置要求からの再配置データが最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置されるようになっている。このシステムは、フリー・ブロック・データ構造からのユーザ書き込みデータを保持するメモリ・ブロックと再配置データを保持するメモリ・ブロックとを受信し、ガーベッジ・コレクションの候補として直ちに選択されないようにこれらのメモリ・ブロックを遅延させるように構成された遅延ブロック・データ構造と、遅延ブロック・データ構造からメモリ・ブロックを受信し、消去のためにそのメモリ・ブロックのうちの少なくとも１つを選択するように構成されたガーベッジ・コレクション・プール構造とをさらに備え、選択されたメモリ・ブロックは消去されるとフリー・ブロック・データ構造に移動される。
【００１１】
本発明のさらに他の実施形態により、コンピュータのメモリ・デバイス内のメモリ・ブロックを管理するコンピュータによって実装される方法が提供される。この方法は、ブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序で書き込みのためにフリー・メモリ・ブロックを維持管理し、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を受信することと、新しいユーザ書き込み要求からのユーザ書き込みデータをより小さいブロック書き込み−消去耐久サイクル・カウントを有する最も若いフリー・メモリ・ブロックに配置することと、再配置書き込み要求からの再配置データを最も若いフリー・メモリ・ブロックより大きいブロック書き込み−消去耐久サイクル・カウントを有する最も古いフリー・メモリ・ブロックに配置することと、ユーザ書き込みデータを保持するユーザ書き込みメモリ・ブロックと再配置データを保持する再配置メモリ・ブロックを維持管理することと、消去のためにユーザ書き込みメモリ・ブロックまたは再配置メモリ・ブロックのうちの少なくとも１つを選択することを含む。
【００１２】
本発明の他の実施形態により、上述の方法を実装するコンピュータ・プログラムも提供される。
【００１３】
追加の特徴および利点は本発明の諸技法により実現される。本発明のその他の実施形態および態様は、本明細書に詳細に記載され、請求された本発明の一部と見なされる。これらの利点および特徴により本発明をさらに理解するために、以下の説明および添付図面を参照されたい。
【００１４】
本発明と見なされる主題については、本明細書の末尾にある特許請求の範囲において詳しく指摘され、明瞭に請求されている。本発明の上記その他の特徴および利点は、添付図面に併せて示されている以下の詳細な説明から明らかである。
【図面の簡単な説明】
【００１５】
【図１】本発明の諸実施形態内で実装可能なフラッシュ・メモリ管理システムを示すブロック図である。
【図２】本発明の代替諸実施形態内で実装可能なフラッシュ・メモリ管理システムを示すブロック図である。
【図３】本発明の諸実施形態内で実装可能な、メモリ・デバイス内のメモリ・ブロックを管理するための方法を示す流れ図である。
【図４】本発明の諸実施形態内で実装可能な汎用コンピュータのブロック図である。
【発明を実施するための形態】
【００１６】
次に図１に関連して説明すると、本発明の一実施形態内で実装可能なフラッシュ・メモリ管理システムが示されている。本発明の一実施形態では、フラッシュベースのＳＳＤデバイスの書き込み−消去耐久寿命を改善するために、分離および予測に基づくデータ配置、ガーベッジ・コレクション、および摩耗平準化プロセスを使用する。システム１０では、動的データは静的データを有するブロックより速くブロックを摩耗する傾向があるという予測に基づいて、動的データ・ページを有するブロックを静的データ・ページ（すなわち、更新数が少ないページ）を有するブロックから動的に分離し、したがって、動的データ・ページはより小さいブロック書き込み−消去耐久サイクル・カウント（すなわち、より大きい残存未消費サイクル・カウント）を有するより若いブロックに配置され、静的データ・ページは、可能なときには必ず、より古いブロックに配置される。
【００１７】
図１に示されている通り、コンピュータ（図４に描写されているもの）のメモリ・デバイスに関するメモリ管理システム１０が提供される。システム１０は、書き込みのために複数のフリー・メモリ・ブロック１４を含むフリー・ブロック・データ構造１２（すなわち、フリー・ブロック・プール）を含む。フリー・ブロック・プール１２はブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序でフリー・メモリ・ブロック１４をソートする。たとえば、本発明の一実施形態により、フリー・メモリ・ブロック１４はブロック書き込み−消去耐久サイクル・カウントに基づいて昇順にソートされ、最左端のフリー・メモリ・ブロック１４が最も小さい書き込み−消去耐久サイクル・カウントを有し、最右端のフリー・メモリ・ブロック１４が最も大きい書き込み−消去耐久サイクル・カウントを有するようになっている。すなわち、フリー・メモリ・ブロック１４は、ブロック書き込み−消去耐久カウントに基づいて最も若いものから最も古いものへソートされる。本発明の一実施形態により、フリー・ブロック・プール１２は、既存のデータを更新するためにシステム１０のユーザを介して新しいユーザ書き込み要求を受信し、既存のデータを再配置するために（システム１０内の）ガーベッジ・コレクション・プロセスを介して再配置書き込み要求を個別に受信する。本発明の一実施形態により、再配置データ・ページはユーザ・データ・ページに比較してより「静的」であると見なすことができるので、システム１０はユーザ書き込みデータ・ストリームを再配置データ・ストリームから分離する。
【００１８】
本発明の一実施形態により、システム１０が異なる書き込み−消去サイクル予算を有するブロックを含む場合、たとえば、単一レベル・セル（ＳＬＣ）とマルチレベル・セル（ＭＬＣ）のフラッシュの混合が存在する場合、フリー・ブロック・プール１２はそのブロックの残存書き込み−消去耐久サイクル・カウントに応じて編成され、最も大きい残存（未消費）書き込み−消去耐久サイクル・カウントを有するブロックが左（すなわち、最も若いブロック）になる。
【００１９】
さらに、図１に示されている通り、システム１０は、ユーザ書き込みデータ構造１６（すなわち、ユーザ書き込みブロック・プール）と再配置データ構造２０（すなわち、再配置ブロック・プール）とを含む。本発明の一実施形態により、最左端のフリー・メモリ・ブロック１４がユーザ書き込みデータ・ページで満たされたときに、メモリ・ブロック１４はフリー・ブロック・プール１２から除去され、ユーザ書き込みブロック・プール１６に押し込まれる。さらに、最右端のメモリ・ブロック１４が再配置データ・ページで満たされたときに、そのブロックはフリー・ブロック・プール１２から除去され、再配置ブロック・プール２０に押し込まれる。本発明の一実施形態により、ユーザ書き込みブロック・プール１６と再配置ブロック・プール２０はいずれもデータ構造によって管理することができ、この実施形態では、そのプールは待ち行列データ構造によって管理され、新たに満たされたブロックが各待ち行列の末尾に配置されることを意味する。したがって、ユーザ書き込みデータ構造１６はフリー・ブロック・プール１２からのユーザ書き込みデータ・ページを保持するユーザ書き込みメモリ・ブロック１８を受信し、再配置ブロック・プール２０はメモリ・ブロック・プール１２からの再配置データ・ページを保持する再配置メモリ・ブロック２２（すなわち、最後のメモリ・ブロック）を受信する。すなわち、本発明の一実施形態により、ユーザ書き込みデータ・ページはフリー・ブロック・プール１２内の最も若いブロックに配置され、再配置データ・ページはフリー・ブロック・プール１２内の最も古いブロックに配置される。
【００２０】
本発明の一実施形態により、システム１０は、ユーザ書き込みブロック・プール１６または再配置ブロック・プール２０からのユーザ書き込みメモリ・ブロック１８および再配置メモリ・ブロック２２のうちのいくつかのメモリ・ブロックの組み合わせから少なくとも１つのブロックを選択するガーベッジ・コレクション・プール構造２４をさらに含む。
【００２１】
本発明の一実施形態により、メモリ・ストレージ・デバイスのフラッシュ・コントローラは、上述のデータ構造ならびにガーベッジ・コレクション・プール構造２４の諸機能を制御することができる。本発明の一実施形態により、ウィンドウ表示されたガーベッジ・コレクション・プロセスは、選択のための所定のルールに基づいて実装される。ガーベッジ・コレクション・プロセスは、最小数のフリー・メモリ・ブロック１４を保証するためにフリー・ブロック・プール１２内のフリー・メモリ・ブロック１４の数をモニターすることによってトリガされる。ガーベッジ・コレクション・プロセスは、ユーザ書き込みブロック・プール１６内の最左端から始まるユーザ書き込みメモリ・ブロック１８のウィンドウおよび再配置ブロック・プール２０内の最左端から始まる再配置メモリ・ブロック２２のウィンドウ内でメモリ・ブロックを捜す。
【００２２】
本発明の一実施形態により、ガーベッジ・コレクションのために選択すべきブロックは、ユーザ書き込みブロック・プール１６または再配置ブロック・プール２０から得ることができる。本発明の一実施形態により、ガーベッジ・コレクション・プロセスは、ｓ＋ｔ個のブロックからなるウィンドウについて実行することができ、ｓ個の候補ブロックはユーザ書き込みブロック・プール１６からのものであり、ｔ個の候補ブロックは再配置ブロック・プール２０からのものであり、ｓ個のブロックとｔ個のブロックは各データ構造１６および２０の先頭からのものであり、それ以前にプールに入っているブロックである。本発明の一実施形態により、ユーザ書き込みブロック・プール１６内のｓ個の候補ブロックのウィンドウ・サイズと、再配置ブロック・プール２０内のｔ個の候補ブロックのウィンドウ・サイズは、等しい場合もあれば、等しくない場合もある。
【００２３】
本発明の一実施形態により、ガーベッジ・コレクション・プロセスは、所定のルールによりｓ＋ｔ個のガーベッジ・コレクション・ウィンドウからリサイクルのためのブロックを選択することによって実行される。本発明の諸実施形態内で実装可能なルールがいくつかある。たとえば、本発明の一実施形態は、高い再利用効率を維持しながら良好なレベルの摩耗平準化を達成するために、以下のルールに基づいて行われる。
【００２４】
システム１０内のすべてのブロックがＮｐ個のページを有し、ガーベッジ・コレクションの時点での平均残存（未消費）サイクル・カウントがＡである場合。以下のルールを使用して、ガーベッジ・コレクションのためにｊ*番目のブロックを選択すると、以下の式のようになる。
ｊ＝０，．．．，（ｓ＋ｔ）−１である場合にｊ*＝ａｒｇ ｍａｘ（ＷＩｊ＋Ｄｊ）
ここで、Ｗは１より大きい整数値を取る適切な重み係数であり、Ｄｊ＝ｍａｘ（Ｃｊ−Ａ，０）であり、Ｉｊはガーベッジ・ウィンドウ内のｓ＋ｔ個のブロックのうちのｊ番目のブロック上の無効データ・ページの数であり、ｊ＝０，．．．，（ｓ＋ｔ）−１であり、Ｃｊはそれぞれのブロックの残存（未消費）耐久サイクル・カウントを表す。本発明の一実施形態により、Ｗは、システム１０の耐久寿命を最大限にするためにシミュレーションを介して選択することができる。
【００２５】
ガーベッジ・コレクションのためのブロックを選択すると、ガーベッジ・コレクションはまず、そのブロック上のページのうち、依然として有効なデータ・ページであるページをすべて読み取り、そのページを他のブロックに書き込む。ガーベッジ・コレクションからの書き込み要求は、再配置書き込み要求と呼ばれ、図１に示されている通り、最も古いフリー・メモリ・ブロック１４に配置される。ＬＢＡ対ＰＢＡのマップは、どのデータ・ページが有効または無効であるかをガーベッジ・コレクションに知らせるものである。データ・ページは、ユーザによって更新され、他の場所に書き込まれると、無効になる。選択されたブロックのすべての有効データ・ブロックが再配置されると、選択されたブロックは消去される。正常に消去されると、選択されたブロックは、ユーザ書き込みブロック・プール１６または再配置ブロック・プール２０から除去され、フリー・ブロック・プール１２に入れられる。
【００２６】
ウィンドウ表示されたガーベッジ・コレクション・プロセスの実装によって書き込み増幅および摩耗平準化不足が低減され、それにより、フラッシュベースのストレージ・デバイスの書き込み−消去耐久寿命が改善される。
【００２７】
本発明の他の実施形態により、ユーザ書き込みブロック・プール１６および再配置ブロック・プール２０からの候補ブロックの数を変更することができる。たとえば、システム１０が大量消費のユーザ書き込み作業負荷によって使用中である場合、一時的にリサイクル効率を最大限にするためにユーザ書き込みブロック・プール１６からのブロックのみを含むようにガーベッジ・コレクション・ウィンドウを変更することができる。これに反して、システム１０がアイドル状態である場合、ガーベッジ・コレクション・ウィンドウは、大部分が再配置ブロック・プール２０から選択されたブロックと、ユーザ書き込みブロック・プール１６から選択されたわずか数個のブロックとを含むことができ、それにより、摩耗平準化プロセスを加速することができる。本発明は、図１に示されているシステムに限定されず、必要に応じて様々になる可能性がある。代替フラッシュ・メモリ管理については図２に関連して以下に述べる。
【００２８】
図１に示されているようにユーザ書き込みブロック・プール１６と再配置ブロック・プール２０を個別に管理する代わりに、以下に論じるように、本発明の他の実施形態により、この２つのプール１６、２０をマージし、図２に示されているように一緒に管理することができる。
【００２９】
図２は、本発明の代替諸実施形態内で実装可能なフラッシュ・メモリ管理システムを示すブロック図である。図２に示されている通り、新たに書き込まれたブロックがガーベッジ・コレクション・プール構造に入るのを遅延させるために、遅延ブロック・データ構造（すなわち、（先入れ先出し（ＦＩＦＯ）待ち行列）を有するフラッシュ・メモリ管理システム１００が提供される。フラッシュ・メモリ管理システム１００は、データを書き込むために複数のフリー・メモリ・ブロック１１４を含むフリー・ブロック・データ構造１１２を含む。フリー・ブロック・データ構造１１２は、図１に示されているものと同様に構成される。フリー・ブロック・データ構造１１２は、ブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序でフリー・メモリ・ブロック１１４をソートし、既存のデータを更新するためのユーザ書き込み要求と、既存のデータをフリー・メモリ・ブロック１１４上に再配置するための再配置書き込み要求を受信する。さらに、システム１００は、フリー・ブロック・データ構造１１２からのユーザ書き込みデータ・ページ（より動的である可能性がある）を保持する最初の（すなわち、最も若い）メモリ・ブロック１１８と、フリー・ブロック・データ構造１１２からの再配置データ・ページ（同等に静的である可能性がある）を保持する最後の（最も古い）メモリ・ブロック１１８を受信する遅延ブロック・データ構造１１６を含む。上述の通り、本発明の一実施形態により、遅延ブロック・データ構造１１６はＦＩＦＯ待ち行列にすることができ、ユーザ書き込みデータ・ページまたは再配置データ・ページのいずれかを保持する新たに満たされたブロック１１８は一方の側で遅延ブロック・データ構造１１６に押し込まれる。一方の側でブロック１１８が遅延ブロック・データ構造１１６に押し込まれるたびに、もう一方の側（すなわち、反対側）でブロック１１８が遅延ブロック・データ構造１１６から押し出され、そのブロック１１８は、図２に示されている通り、ガーベッジ・コレクション・プール構造１２２に入る。したがって、ガーベッジ・コレクション・プール構造１２２は、遅延ブロック・データ構造１１６からメモリ・ブロック１１８を受信し、ガーベッジ・コレクションのためにメモリ・ブロック１１８のうちの少なくとも１つを選択する。データ・ページが再配置され、ブロック１１８が消去されると、選択されたブロック１１８はデータを書き込むためにフリー・ブロック・データ構造１１２に移動する。メモリ・デバイス内のメモリ・ブロックを管理するための方法については図３に関連して以下に述べる。
【００３０】
図３は、本発明の諸実施形態内で実装可能な、メモリ・デバイス内のメモリ・ブロックを管理するための方法を示す流れ図である。図３の動作３００では、ブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序で（たとえば、最も若いものから最も古いものへ）書き込みのためにフリー・メモリ・ブロックが維持管理される。既存のデータを更新するための新しいユーザ書き込み要求は、既存のデータをフリー・メモリ・ブロック上に再配置するための再配置書き込み要求とともに受信される。本発明の一実施形態により、ブロック書き込み−消去耐久サイクル・カウントに基づいて昇順にソートすることによってフリー・メモリ・ブロックが維持管理され、最左端のフリー・メモリ・ブロックが最も若いものになり、最右端のフリー・メモリ・ブロックが最も古いものになり、すなわち、最小量の残存（未消費）サイクル・カウントを有するようになる。
【００３１】
プロセスは動作３００から動作３１０に移行し、そこで新しいユーザ書き込み要求からのユーザ書き込みデータが最も若いフリー・メモリ・ブロックに配置される。最も若いフリー・メモリ・ブロックをユーザ書き込みページで満たすと、最も若いメモリ・ブロック（すなわち、この時点ではユーザ書き込みメモリ・ブロック）はフリー・ブロック・プールから除去され、それが維持管理されるユーザ書き込みブロック・プールに押し込まれる。本発明の一実施形態により、フリー・ブロック・プール内では、２番目に若いメモリ・ブロックがこの時点で最も若いメモリ・ブロックとして現れ、ユーザ書き込み要求を保持するために使用される。
【００３２】
本発明の一実施形態により、関係するデータ・ページが頻繁に更新されるのかどうかを判断することができる。あるデータ・ページがあまり頻繁に更新されない場合、そのページは、再配置要求と同様に、最も古いフリー・、メモリ・ブロックに配置される。
【００３３】
プロセスは動作３１０から動作３１２に移行し、そこで再配置要求からの再配置データ・ページが最も古いフリー・メモリ・ブロックに配置され、そのフリー・メモリ・ブロックは最も東新頻度が低いデータを有する。最も古いフリー・メモリ・ブロックが再配置データ・ページで満たされると、最も古いフリー・メモリ・ブロック（すなわち、この時点では再配置メモリ・ブロック）はフリー・ブロック・プールから除去され、それが維持管理される再配置ブロック・プールに入る。
【００３４】
本発明の一実施形態により、ユーザ書き込みブロック・プールと再配置ブロック・プールはいずれも待ち行列データ構造によって管理することができ、すなわち、新たに満たされたブロックは待ち行列の一方の端部から入り、待ち行列のもう一方の端部にはガーベッジ・コレクション・ウィンドウが設定される。
【００３５】
プロセスは動作３１２から動作３１４に移行し、そこでユーザ書き込みメモリ・ブロックおよび再配置メモリ・ブロックのメモリ・ブロックのうちの少なくとも１つがガーベッジ・コレクションのために選択される。本発明の一実施形態により、所定のルールに基づいて消去のためのウィンドウにより少なくとも１つのメモリ・ブロックが選択される。本発明の一実施形態により、個別に管理されているユーザ書き込みメモリ・ブロックのウィンドウおよび再配置ブロックのウィンドウから少なくとも１つのメモリ・ブロックが選択される。他の実施形態により、一緒に管理されているユーザ書き込みメモリ・ブロックと再配置メモリ・ブロックの組み合わせによって形成されたウィンドウから少なくとも１つのメモリ・ブロックを選択することもできる。すなわち、図２に示されている通り、ユーザ書き込みブロック・プールは再配置ブロック・プールとマージされる。
【００３６】
一般に、本明細書に記載されているように、本発明の諸実施形態によりメモリ・デバイス内のメモリ・ブロックを管理するためのフラッシュ・メモリ管理システムおよび方法は汎用コンピュータによって実施され、その方法は汎用コンピュータによって使用するための取り外し可能メディアまたはハード・メディア上で１組の命令としてコード化することができる。図４は、本発明の諸実施形態を実施するために適した汎用コンピュータの概略ブロック図である。図４では、コンピュータ・システム４００は、少なくとも１つのマイクロプロセッサまたは中央演算処理装置（ＣＰＵ）４０５を有する。ＣＰＵ４０５は、システム・バス４１０を介して、ランダム・アクセス・メモリ（ＲＡＭ）４１５、読み取り専用メモリ（ＲＯＭ）４２０、取り外し可能データ／プログラム・ストレージ・デバイス４３０および大容量データ／プログラム・ストレージ・デバイス４３５を接続するための入出力（Ｉ／Ｏ）アダプタ４２５、キーボード４４５およびマウス４５０を接続するためのユーザ・インターフェース・アダプタ４４０、データ・ポート４６０を接続するためのポート・アダプタ４５５、ならびにディスプレイ・デバイス４７０を接続するためのディスプレイ・アダプタ４６５に相互接続される。
【００３７】
ＲＯＭ４２０はコンピュータ・システム４００用の基本オペレーティング・システムを収容している。オペレーティング・システムは、代わって、ＲＡＭ４１５または当業者に知られている他の場所に常駐することができる。取り外し可能データ／プログラム・ストレージ・デバイス４３０の例としては、フレキシブル・ディスク・ドライブおよび磁気テープ・ドライブなどの磁気メディアならびにCD−ROMドライブなどの光メディアを含む。大容量データ／プログラム・ストレージ・デバイス４３５の例としては、ハード・ディスクおよびフラッシュ・メモリなどの不揮発性メモリを含む。キーボード４４５およびマウス４５０に加えて、トラックボール、書き込みタブレット、圧力パッド、マイクロホン、ライト・ペン、および位置感知画面ディスプレイなどのその他のユーザ入力装置をユーザ・インターフェース４４０に接続することもできる。ディスプレイ・デバイスの例としては、ブラウン管（ＣＲＴ）および液晶ディスプレイ（ＬＣＤ）を含む。
【００３８】
適切なアプリケーション・インターフェースを有するコンピュータ・プログラムは、当業者によって作成し、本発明の実施を単純化するためにシステムまたはデータ／プログラム・ストレージ・デバイス上に保管することができる。動作時に、本発明を実施するために作成されたコンピュータ・プログラムまたはそれに関する情報は、適切な取り外し可能データ／プログラム・ストレージ・デバイス４３０上にロードされ、データ・ポート４６０を介し七供給され、キーボード４４５を使用してタイプ入力される。
【００３９】
したがって、上記を考慮すると、本発明の方法の実施形態は、コンピュータまたはコントローラで実装されるプロセスおよびこれらのプロセスを実施するための装置の形を取ることができる。また、本発明は、フレキシブル・ディスケット、ＣＤ−ＲＯＭ、ハード・ディスク、または任意のその他のコンピュータ可読記憶媒体などの有形メディアに記録された命令を含むコンピュータ・プログラム・コードの形で具体化することもでき、コンピュータ・プログラム・コードがコンピュータまたはコントローラにロードされ、それによって実行されたときに、そのコンピュータは本発明を実施するための装置になる。また、本発明は、たとえば、記憶媒体に保管されるか、コンピュータまたはコントローラにロードされるか、またはそれによって実行されるか、あるいはその両方であるか、電気配線またはケーブリング、光ファイバ、電磁放射などの何らかの伝送媒体によって伝送されるかにかかわらず、コンピュータ・プログラム・コードまたは信号の形で実施することもでき、コンピュータ・プログラム・コードがコンピュータにロードされ、それによって実行されたときに、そのコンピュータは本発明を実施するための装置になる。汎用マイクロプロセッサ上で実装されると、コンピュータ・プログラム・コード・セグメントは、特定の論理回路を作成するようにマイクロプロセッサを構成する。実行可能命令の技術的効果は、上記の模範的な方法を実装することである。
【００４０】
本発明の諸実施形態は、データ配置（すなわち、分離およびソート）、ガーベッジ・コレクション、および摩耗平準化を介してコンピュータ・システムのメモリ・デバイス内のメモリ・ブロックを管理するためのフラッシュ・メモリ管理システムおよび方法を含む。したがって、このシステムは比較的古いブロックに静的データを移動し、比較的若いブロックに動的データを移動することを開示しているので、本発明は書き込み増幅を低減するという利点を提供する。また、本発明は、必要な書き込み動作を低減することによってメモリ・デバイスのパフォーマンスおよびメモリ・デバイスの耐久寿命を改善しながら、様々なブロックのサイクル・カウント使用のバランスを取り、起こりうるすべてのアンバランスを修正することにより摩耗平準化を達成する。
【００４１】
以下の特許請求の範囲のすべての手段またはステップならびに機能要素に対応する構造、材料、行為、およびそれと同等のものは、具体的に請求されているようにその他の請求要素と組み合わせて機能を実行するための任意の構造、材料、または行為を含むためのものである。本発明の説明は、例示および解説のために提示されたものであり、網羅するためまたは開示された形式に本発明を限定するためのものではない。多くの変更および変形は、本発明の範囲および精神を逸脱せずに当業者にとって明白なものになる。この実施形態は、本発明の原理および実用的な適用例を最も良く説明するため、ならびにその他の当業者が企図された特定の用途に適した様々な変更を含む様々な実施形態について本発明を理解できるようにするために、選択され記載されたものである。
【００４２】
本明細書に描写されている流れ図は一例に過ぎない。この図またはそこに記載されているステップ（または動作）については、本発明の精神を逸脱せずに多くの変形が存在する可能性がある。たとえば、これらのステップは、異なる順序で実行される場合もあれば、ステップが追加、削除、または変更される場合もある。これらの変形はいずれも、請求された本発明の一部と見なされる。
【００４３】
本発明の好ましい実施形態について説明してきたが、当業者であれば、現在および将来のいずれでも、以下に示す特許請求の範囲の範囲内に入る様々な改良および機能強化を行うことができることが理解されるであろう。これらの特許請求の範囲は、最初に記述した本発明に関する適切な保護を維持するものと解釈しなければならない。
【要約】【課題】コンピュータのメモリ・デバイスのメモリ・ブロックを管理するためのメモリ管理システムおよび方法を提供する。
【解決手段】このシステムは、書き込みのためにフリー・メモリ・ブロックを含み、ブロック書き込み−消去耐久サイクル・カウントに基づいて所定の順序でフリー・メモリ・ブロックをソートし、既存のデータを更新するための新しいユーザ書き込み要求と、既存のデータを再配置するための再配置書き込み要求を個別に受信するフリー・ブロック・データ構造と、フリー・ブロック・データ構造からのユーザ書き込みデータ（すなわち、頻繁に更新される任意のページ）を保持する最も新しいブロックを受信するためのユーザ書き込みブロック・プールと、フリー・ブロック・データ構造からの再配置データ（すなわち、頻繁に更新されない任意のページ）を保持する最も古いブロックを受信するための再配置ブロック・プールと、ガーベッジ・コレクションのためにユーザ書き込みブロックおよび再配置ブロックのうちの少なくとも１つを選択するためのガーベッジ・コレクション・プール構造とを含み、選択されたブロックは再配置および消去されるとフリー・ブロック・データ構造に戻される。
【選択図】  図３【図１】
0005089823.tif 000002
【図２】
0005089823.tif 000003
【図３】
0005089823.tif 000004
【図４】
0005089823.tif 000005