(57)【要約】システムリソースの使用量を低減しつつフラッシュ媒体（１２）のデータ記憶ユニットの消耗を平準化する方法。静的領域内の静的データを他の物理的位置へ移動させるプロセスを用いるアルゴリズムにより静的領域が静的なまま残らないことが保証される。フラッシュデータ・マネージャが書き込みまたは消去動作（１０）を何度も繰り返した後で、最終的に全データユニットが選択されるまで順次選択するようなプロセス（１１）により、データユニットを選択し、次いで選択されたデータユニットは自由ユニット位置へ移動され（１６）、選択されたデータは消去される。
2004522230.tif 000002
【特許請求の範囲】
【請求項１】
フラッシュ記憶媒体における消耗平準化の方法であって、
ｉ．フラッシュデータ・マネージャによる特定回数の動作につき少なくとも１回、前記消耗平準化方法を起動する工程と、
ｉｉ．最終的に全ユニットが選択されるまで順次選択する仕方で、前記媒体内のユニットを選択する工程と、
ｉｉｉ．前記選択されたユニットのデータを前記媒体から前記媒体内の自由ユニットへ移動させて、前記選択されたユニットを消去する工程と
を含む方法。
【請求項２】
前記特定回数は、
ａ．消去動作回数をカウントして、前記カウントが所与の回数の倍数になった時点を判定する工程と、
ｂ．書き込み動作回数をカウントして、前記カウントが所与の回数の倍数になった時点を判定する工程と、
ｃ．所与の成功確率に基づいて、各消去動作に対するランダムプロセスを生成する工程と、
ｄ．所与の成功確率に基づいて、各書き込み動作に対するランダムプロセスを生成する工程と
からなる群から選択された一つの方法で生成される、請求項１に記載の方法。
【請求項３】
フラッシュ媒体が受ける書き込みおよび消去動作の回数に比べて発生頻度が低くなるよう設計された仕方で前記特定の回数の生成を行う工程をさらに含む、請求項２に記載の方法。
【請求項４】
前記ユニットを選択する工程は、
ｉ．特定の選択順序を設定する工程と、
ｉｉ．選択対象の各ユニットに対して等しい確率が与えられるように、ランダムプロセスによりユニットを選択する工程と
からなる群から選択された仕方で行なわれる、請求項１に記載の方法。
【請求項５】
前記選択されたユニットは静的ユニットである、請求項１に記載の方法。
【請求項６】
フラッシュ記憶媒体内のどの消去ユニットも、それを含むフラッシュ記憶媒体の寿命の大半にわたり静的なままではないことを保証する機構であって、
ｉ．データを保存するフラッシュ記憶媒体と、
ｉｉ．前記フラッシュ記憶媒体内のどの消去ユニットも、前記フラッシュ記憶媒体の寿命の大半にわたり静的なままではないことを保証する、コンピュータにより実行可能なコードと
を含む機構。
【請求項７】
フラッシュ記憶媒体内のすべての消去ユニットが、それを含むフラッシュ記憶媒体の寿命の大半の間に少なくとも１回の消去動作を受けることを保証する機構であって、
ｉ．データを保存するフラッシュ記憶媒体と、
ｉｉ．前記フラッシュ記憶媒体内のすべての消去ユニットが、前記フラッシュ記憶媒体の寿命の大半にわたり少なくとも１回の消去動作を受けることを保証する、コンピュータにより実行可能なコードと
を含む機構。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明はフラッシュメモリにおける静的領域の消耗平準化を向上させる方法に関する。
【０００２】
【関連技術の説明】
フラッシュメモリは不揮発性であって、電源がなくても記録されたデータを保存可能である。さらに、フラッシュメモリの消去および再書き込み可能な性能を利用するコンピュータ・プログラムにより、フラッシュメモリに保存されたデータを変更することができる。これらの基本性能によりフラッシュアレイはコンピュータシステムにおける標準的な記憶媒体、すなわちフラッシュディスクとしての役割を果たすようになった。当技術分野においてこれを実現する種々の方法が記載されており、このような方法は広範に利用されている。このような方法の例としては、Ａｍｉｒ  Ｂａｎによる米国特許第５，４０４，４８５号（フラッシュファイルシステム）およびＡｍｉｒ  Ｂａｎによる米国特許第５，９３７，４２５号（ページモードフラッシュ技術向けに最適化されたフラッシュファイルシステム）があり、共に全文を本明細書に援用している。これら２件の特許は、ユニットへのデータの保存や消去を調停する等、フラッシュファイルシステムを管理するシステムおよび方法を記載している。しかし、これらの特許は頻繁に消去されるユニットと稀にしか消去されないユニットを区別しないため、消耗平準化の手段を提供しない。
【０００３】
フラッシュ素子は通常、いくつかの連続したゾーンに分けられていて、それぞれ個別に消去可能である。このようなゾーンは当技術分野でユニット、ブロックまたはセクタ等さまざまな呼び方で知られているが、本明細書では明快にすべくユニット、あるいは消去ユニットと呼ぶことにする。
【０００４】
フラッシュメモリ技術の限界は、ユニットを消去できる回数がフラッシュセルの物理特性により本質的に制限される点である。ユニットを繰り返し消去すればユニット内のセルが消耗し、消去された状態と書き込まれた状態を区別する機能の低下につながり、その結果ユニットの消去にかかる時間が長くなって、データの書き込みや消去に散発的な誤りが出現し、ついにはユニットの消去や書き込み機能が失なわれかねない。
【０００５】
消耗の影響は本来統計的であり、フラッシュ素子が消耗に耐える性能は書き込み／消去耐性と呼ばれる数値を用いてフラッシュ素子のベンダーが表記している。この数値は、各フラッシュユニットが重大な誤動作を起こすことなく消去できる最小または平均回数である。ベンダーによる耐性回数は現在、数万〜１００万回の範囲にある。
【０００６】
耐性限界によりフラッシュディスクの寿命が制約される。可能な限り寿命が長いことが有利であるが、これはフラッシュディスクへのアクセスパターンに依存する。１個のユニットまたは少数のユニットへの書き込みを頻繁に繰り返せばまもなく誤動作が発現し、媒体の使用可能な寿命がすぐに尽きてしまう。一方、書き込みを媒体の全ユニットにわたり均等に分散させることができれば、各ユニットは消去に耐え得る最大回数近くまで持ち、その結果、誤動作の発現を可能な限り遅らせて、媒体の寿命を最長にできる。
【０００７】
フラッシュディスク・マネージャは通常、自身に備わったアルゴリズムにより新規データを書き込む物理的位置を決める裁量を与えられており、異なるフラッシュユニットが必ず同じ回数消去されるよう設計された仕方で書き込まれたデータを配置するという事実を利用する。このような手順は当技術分野で消耗平準化として知られている。ある種のマネージャはユニットが消去された回数をそのユニット内のレジスタに記録して、各ユニットの消去回数の分散が所与の小さい定数を超えないことを保証するスキームを強制する。他のものは、対象ユニットの選択に無作為抽出を利用し、統計および大数の法則に依存してフラッシュ媒体全体にわたって消耗が均等に保たれるようにする。
【０００８】
しかし、そのような消耗平準化方法に特有の問題として静的領域がある。静的領域とは、全くまたは殆ど変わらないデータを含むフラッシュ素子上の物理的位置である。このようなデータはオペレーティング・システムコードまたはアプリケーション／プログラムコードから構成されていてもよく、通常は一度インストールされたら全くまたは殆ど変わらない。フラッシュディスクのさまざま利用法において、このようなデータはフラッシュ媒体の主要な部分を占める。
【０００９】
消耗平準化方法は、新規データを書き込む位置を選択する際に制御を行なうため、静的領域に生じる消耗には影響を及ぼさない。これらの領域には決して書き込みが行なわれないため、選択不可能である。フラッシュ媒体のアクティブなユニットには消耗平準化が有効であるのに対し、静的ユニット、すなわち静的領域のユニットは消耗が極めて少ないままである。これは、例えば静的領域が媒体の半分を占める場合、有効寿命が半分に減るため、フラッシュ媒体全体の寿命を著しく縮めることになる。
【００１０】
さらに、静的領域には以下のような種々の問題がある：
１．ユニットによる長期間にわたるフラッシュディスク使用のパターン追跡を含む静的領域の識別。これは履歴管理を支援する制御構造およびアルゴリズムを必要とする困難なプロセスである。
２．静的ユニットから別の位置へのデータの移動は、データを新しい位置に書き込んで前の位置を消去するための時間をとる。これが頻繁に行なわれた場合、フラッシュディスクのスループットの低下させる性能オーバーヘッドが現れる。
３．静的領域が存在するにもかかわらず長時間にわたり、媒体全体にわたる消耗の平準化を保証すること。
【００１１】
当分野におけるいくつかの実施例としては、本明細書に全文を援用するＷｅｌｌｓらによる米国特許第５，３４１，３３９号はフラッシュＥＥＰＲＯＭメモリにおける消耗平準化の方法を記載している。それによればフラッシュメモリ・アレイの寿命が著しく延びる。Ｗｅｌｌｓらによる発明の方法は、フラッシュメモリ・アレイの異なる部分のスイッチングを監視し、その後均等化する工程を提供する。本発明によれば、これらおよびその他の目的が、別々に消去可能なブロックに分けられたフラッシュＥＥＰＲＯＭメモリ・アレイをクリアするプロセスにより実現され、そのプロセスで選択されたブロック上のすべての有効なデータは最初にアレイの他のブロックに書き込まれ、次いでそのブロックが消去され、本改良は、各ブロックが含む無効セクタの個数と各ブロックが受けたスイッチング動作の回数との比較に基づいてクリアすべき選択ブロックを決定する工程を含む。このようにして、記録用の予約ユニットの維持と、消耗平準化の維持が共に実現される。しかし、各ユニットの消去回数カウントの保持も含め、そのようなシステムを維持するには相当のシステムリソースを必要とする。さらに、Ｗｅｌｌｓは実際には静的領域を扱っていない。同氏は、クリア動作時に消去回数カウントに重みを与えることを示唆している。実際には、静的な領域ではクリアすべきものが無いため、これはパラメータに重みを設定するだけでは済まない。Ｗｅｌｌｓは、クリアを必要としないが静的であるユニットに対して“クリア”を強制する必須な工程を省いている。
【００１２】
本明細書に全文を援用したＡｓｓａｒらによる米国特許第５，３８８，０８３号、第５，４８５，５９５号および第５，４７９，６３８号に、消耗平準化のためのフラッシュメモリ大容量記憶装置アーキテクチャの種々の適用例を記載している。これらの特許によれば、大容量記憶装置のどの部分も、他の部分よりも多い回数消去されないようアルゴリズムが提供される。これにより大容量記憶装置のどのブロックであっても、誤動作により他のブロックよりも早く使用不可になることが防止され、その結果大容量記憶装置全体の寿命が延びる。
【００１３】
従って、カウンタは各ブロックの消去回数を追跡する。カウンタ用に書き込み可能最大回数も提供される。あるブロックの消去回数が最大値より１だけ小さい値に達すると、そのブロックは最後の１回消去されて、その時点で消去回数が最も少ない別のファイルが書き込まれる。そのブロックはまた、消去禁止フラグがセットされることによりそれ以上消去できなくなる。全ブロックが最大回数に達した後で、すべての消去回数カウンタおよび禁止フラグがクリアされて第二のアルゴリズムが繰り返される。このように、すべてのブロックは、他のどのブロックよりも際立って多い回数消去されることがなくなる。しかし、Ｗｅｌｌｓらの発明と同様に、本発明も精緻な監視および許可構造を維持するために相当のシステムリソースを必要とする。さらに本発明は、クリアを必要としないが静的であるユニットに対しクリアを強制する必須工程を省いている。
【００１４】
このように、システムを最小限に抑えつつフラッシュ媒体の寿命を最大化させるべく静的領域を効果的かつ経済的に扱う、改良された消耗平準化アルゴリズムに対するニーズが広範に認識されており、かつそれを実現することが極めて有用である。
【００１５】
【発明の概要】
本発明によれば、フラッシュ媒体の全ユニットにおける消耗平準化に影響する改良された方法を提供する。これは、静的領域を実際には静的のままにしておかず、消耗平準化を実現すべく同領域内にある静的データを他の物理的位置へ確実に移動させるアルゴリズムを提供することにより可能となる。
【００１６】
本発明は以下の方法を提供する：
１．フラッシュデータ・マネージャにより所与の多数回書き込みまたは消去動作が行なわれる度に１回ずつ、以下の工程に従って本発明の消耗平準化方法を開始する。
２．最終的に全ユニットが選択されるまで順次選択する仕方で周期的に媒体のユニットを選択する。
３．選択されたユニットデータを別の自由ユニットへ移動して、選択されたユニットを消去する。
【００１７】
本発明は添付の図面を参照して、実施例によってのみ説明される。
【００１８】
【好適な実施態様の説明】
本発明はフラッシュ媒体における消耗平準化に影響する方法に関する。これは、システムリソースの使用を最小限に抑えつつ消耗平準化が実現されるべく、静的領域を実際には静的のままにしておかず、同領域内の静的データを確実に他の物理的位置に移動するアルゴリズムを提供することにより可能となる。
【００１９】
以下の説明は、当業者が特定の用途とその必要条件に応じて本発明を実施および利用できるよう提示するものである。好適な実施態様に対する種々の変更は当業者には明らかであり、ここで規定する一般原理は他の実施態様にも適用できる。従って、本発明は例示および説明された特定の実施態様に限定されるものではなく、開示された原理および新規な特徴と整合する最も広い範囲に含まれる。
【００２０】
具体的には、本発明はフラッシュメモリ素子内の静的ブロックの消耗平準化を向上させるべく利用可能である。
【００２１】
従って、本発明は静的および非静的領域における消耗平準化の解決策を提供し、その消耗平準化は以下のように実現される：
ｉ．どの領域が静的であるかを認識する必要がない。
ｉｉ．性能低下が極めて小さい。
ｉｉｉ．ユニット間の消耗の分散を小さくすべく効率的な消耗平準化を行なう。
【００２２】
本発明に基づくシステムと方法の原理および動作は、図面および付随する説明を参照することでさらによく理解されよう。ただし、図面は説明目的のためにのみ提供されており、限定的な意図はない。図面からわかるように、本方法は以下のとおりである：
１．フラッシュデータ・マネージャによりある程度多くの回数の書き込みまたは消去動作が行なわれる度に少なくとも１回行なわれ、本発明の消耗平準化方法１２を以下の工程に基づいて行なう。例えば、以下のようにユニット消去動作１０００回につき１回行なってもよい：
ａ．書き込みまたは消去動作をカウントして（１０）、カウントが１０００等、所与の数の倍数になったら起動する。
ｂ．各書き込みまたは消去動作に対して、成功確率が１０００分の１等の所与の確率であるランダムプロセスを生成し（１１）、引き続き消耗平準化方法を起動する。
２．最終的に全ユニットが選択されるまで順次選択する仕方で媒体内のユニットを選択する（１５）。選択は以下のいずれかの方法である。
ａ．例えばユニットが物理的順序で最初から最後まで選択される等、特定の選択順序を設定して（１３）、先行ユニットが最後のものでない限り選択されたユニットが先に選択されたユニットに続き、その場合次に選択されたユニットが最初の物理的順序になるようにする。
ｂ．ランダムプロセスによりユニットを選択して（１４）、各ユニットが選択される確率を等しくする。
３．選択されたユニットのデータを別の自由ユニットへ移動して（１６）、選択されたユニットを消去する。
【００２３】
多くのフラッシュ管理アルゴリズムにおいて、工程３はガーベージ・コレクション・アルゴリズム（米国特許第５，４０４，４８５号、第５，９３７，４２５号、および第５，３４１，３３９号に見られるように当技術分野で公知である）の一環として既に存在するため、これらのアルゴリズムにおいて、上述のプロシージャは既存のプロシージャを起動させる別のケースである。工程３は、選択されたユニットからデータを他所へ移動させたり、その動作を引き起こす効果を有する任意の類似のアルゴリズムであってよいことに留意されたい。例えば、優先順位付けのためにユニットのガーベージ・コレクションを行なうフラッシュマネージャにおいて、工程３は単に選択されたユニットの優先順位を上げて、次の移動の有力候補にするためだけでもよい。
【００２４】
本方法の発生率が低いため、それによるオーバーヘッドは性能に重要な影響を及ぼさない。一方、発生率が低くても、各ユニットについて媒体寿命全期間にわたり数百回発生するならば、以下の理由で十分有効である：
ａ．媒体寿命全期間にわたりユニットが平均的に数百回適用されるべく選択された場合、全く選択されない確率は非常に低いために無視できる。
ｂ．選択されている静的ユニットは、非静的ユニットになる確率が高い。その理由は、静的領域は１回しか書き込まれないのに対し、非静的領域は何度も書き込まれるため、非静的領域への書き込み回数は静的領域への書き込みよりはるかに多いからである。従って、自由になったユニットが後で非静的データにより満杯になることがあり得る。
ｃ．選択された静的データは、元々非静的であった領域へ移動される確率が高い（自由ユニットはほぼ常に非静的領域に発生し、これの唯一の例外は、現行方法の稀な適用を通して起こることである）。
ｄ．媒体寿命全期間にわたり各ユニットは平均的に数百回選択されるという事実は、各物理ユニットが統計的に、静的および非静的な役割を同じ割合で果たすことが期待できることを意味する。
【００２５】
１個のユニットが１００，０００〜１，０００，０００回の書き込み／消去に耐え得ると仮定すれば、上述の例のように１０００回消去する度に本方法を適用することは、各ユニットが平均的に１００〜１０００回選択されることになるため、ユニットの寿命全期間にわたり静的／非静的状態を入れ替える効果を発揮する。
【００２６】
本方法により静的ユニットだけでなく、全ユニットが選択されることに留意されたい。既にアクティブなユニットを選択しても何ら有害でも有益でもない。既にアクティブなユニットを選択することによるオーバーヘッドは、プロシージャ全体のオーバーヘッドが小さいため問題にならず、媒体内の静的領域を識別するのに必要なオーバーヘッドと履歴管理が軽減される。
【００２７】
【発明の利点】
本発明は、必要なシステムリソースを大幅に減少させながらフラッシュ素子内の静的のユニットを含む全ユニットの消耗平準化を向上させる方法を提供する。本方法は単純なアルゴリズムを適用することで動作可能であり、相当な消耗平準化の実行がユーザーにとり明白であって、システムオーバーヘッドへの影響は無視できる程度である。
【００２８】
上述した本発明の実施態様は、例示と説明を目的として提示するものである。これが全てを尽くしている訳ではなく、また本発明を開示内容のとおりに限定することは意図していない。上述の開示内容から各種の変更や変形が可能であることに留意されたい。本発明の範囲は上の詳細な説明ではなく、添付の特許請求の範囲により限定されることを意図している。
【図面の簡単な説明】
【図１】本発明の方法の説明図である。
【図１】
2004522230.tif 000003
【国際公開パンフレット】
2004522230.tif 000004
2004522230.tif 000005
2004522230.tif 000006
2004522230.tif 000007
2004522230.tif 000008
2004522230.tif 000009
2004522230.tif 000010
2004522230.tif 000011
2004522230.tif 000012
2004522230.tif 000013
2004522230.tif 000014
2004522230.tif 000015
2004522230.tif 000016
2004522230.tif 000017
2004522230.tif 000018
2004522230.tif 000019
【国際調査報告】
2004522230.tif 000020
2004522230.tif 000021
2004522230.tif 000022