(57)【要約】本発明は、パフォーマンスが高められたフラッシュメモリ管理のシステムおよび方法を提供する。フラッシュメモリ管理システムは、信頼性および寿命を改善すると同時によいパフォーマンスレベルを維持する形でフラッシュメモリ使用を効率的に管理し、割り振る能力を提供する。フラッシュメモリ管理システムには、空きブロック機構、ディスク保守機構、および不良ブロック検出機構が含まれる。空きブロック機構は、書込みのためのあまり使用されていないブロックの選択を容易にするために、空きブロックの効率的なソートを提供する。ディスク保守機構は、プロセッサアイドル時間中にフラッシュメモリブロックを効率的にクリーニングする能力を提供する。不良ブロック検出機構は、フラッシュメモリのブロックがいつ不良になる可能性が高いかよりよく検出する能力を提供する。フラッシュ状況機構は、フラッシュディスク内のデータの内容および状況を記述する情報を、高速アクセスメモリに記憶する。新バンク検出機構は、フラッシュメモリの新しいバンクがシステムにいつ追加されるか自動的に検出する能力を提供する。これらの機構が、一緒に、フラッシュメモリを使用するシステムの動作効率を改善できるフラッシュメモリ管理システムを提供する。
2005528696.tif 000002
【特許請求の範囲】
【請求項１】
ａ）プロセッサと、
ｂ）前記プロセッサに結合されたメモリと、
ｃ）前記メモリに常駐し、前記プロセッサによって実行されるフラッシュメモリ管理システムであって、
書込みのためにフラッシュメモリの空きブロックを突き止める空きブロック機構であって、空きブロックリスト内のフラッシュメモリブロックのうちで空きブロックリストウィンドウによって定義される部分を探索する空きブロック管理機構と、
クリーニングのためにフラッシュメモリのブロックを突き止めるディスク保守機構であって、前記ブロックリスト内のフラッシュメモリブロックのうちでブロックリストウィンドウによって定義される部分を評価するディスク保守機構と、
不良になる可能性が高いフラッシュメモリのブロックを突き止める不良ブロック検出機構であって、エラーアクティビティについて前記フラッシュメモリブロックを監視し、前記エラーアクティビティが事前定義の閾値を超えたときブロックを不良と指定する不良ブロック検出機構と、
を含むフラッシュメモリ管理システムと、
を含む装置。
【請求項２】
前記空きブロック機構は、さらに、前記空きブロックリストウィンドウを、前記空きブロックリスト上の異なる位置に移動する、請求項１に記載の装置。
【請求項３】
前記ディスク保守機構は、さらに、前記ブロックリストウィンドウを、前記ブロックリスト上の異なる位置に移動する、請求項１に記載の装置。
【請求項４】
前記空きブロック機構は、パフォーマンス要件に従って前記空きブロックリストのサイズを調整する、請求項１に記載の装置。
【請求項５】
ディスク保守機構は、コストエージタイムズ式を使用して、前記ブロックリストウィンドウ内の前記ブロックの前記部分を評価する、請求項１に記載の装置。
【請求項６】
前記フラッシュメモリ管理システムは、さらに、フラッシュメモリの新しいバンクがいつ追加されたか判定する新バンク検出機構を含み、前記新バンク検出機構は、前記ブロックリストおよび前記空きブロックリストに前記新しいバンクからのブロックを追加する、請求項１に記載の装置。
【請求項７】
前記フラッシュメモリ管理システムは、さらに、フラッシュ状況機構を含み、前記フラッシュ状況機構は、前記フラッシュメモリ管理システムのスタートアップ時に前記メモリに状況情報を記憶する、請求項１に記載の装置。
【請求項８】
複数のフラッシュメモリブロックを含むフラッシュメモリシステムを管理する方法であって、
ａ）前記フラッシュメモリブロックのうちで空きブロックリストウィンドウによって定義される部分を探索することによって、書込みのために前記フラッシュメモリの空きブロックを突き止める工程と、
ｂ）前記フラッシュメモリブロックのうちでブロックリストウィンドウによって定義される部分を評価することによって、クリーニングのために前記フラッシュメモリのブロックを突き止める工程と、
ｃ）エラーアクティビティについて前記フラッシュメモリブロックを監視し、前記エラーアクティビティが事前定義の閾値を超えたときブロックを不良と指定することによって、不良になる可能性が高いフラッシュメモリのブロックを突き止める工程と、
を含む方法。
【請求項９】
前記空きブロックリストウィンドウを前記空きブロックリスト上の異なる位置に移動し、前記フラッシュメモリブロックのうちで前記異なる位置の前記空きブロックリストウィンドウによって定義される部分を探索する工程をさらに含む、請求項８に記載の方法。
【請求項１０】
前記ブロックリストウィンドウを空きブロックリスト上の異なる位置に移動し、前記フラッシュメモリブロックのうちで前記異なる位置の前記ブロックリストウィンドウによって定義される部分を評価する工程をさらに含む、請求項８に記載の方法。
【請求項１１】
パフォーマンス要件に従って前記空きブロックリストのサイズを調整する工程をさらに含む、請求項８に記載の方法。
【請求項１２】
不良になる可能性が高いフラッシュメモリのブロックを突き止める前記工程は、コストエージタイムズ式を使用して、前記ブロックリストウィンドウ内の前記ブロックの前記部分を評価することを含む、請求項８に記載の方法。
【請求項１３】
フラッシュメモリの新しいバンクがいつ追加されたか判定する工程をさらに含む、請求項８に記載の方法。
【請求項１４】
前記フラッシュメモリシステムのスタートアップ時に状況情報を記憶する工程をさらに含む、請求項８に記載の方法。
【請求項１５】
ａ）フラッシュメモリ管理プログラムであって、
書込みのためにフラッシュメモリの空きブロックを突き止める空きブロック機構であって、空きブロックリスト内のフラッシュメモリブロックのうちで空きブロックリストウィンドウによって定義される部分を探索する空きブロック管理機構と、
クリーニングのためにフラッシュメモリのブロックを突き止めるディスク保守機構であって、前記ブロックリスト内のフラッシュメモリブロックのうちでブロックリストウィンドウによって定義される部分を評価するディスク保守機構と、
不良になる可能性が高いフラッシュメモリのブロックを突き止める不良ブロック検出機構であって、エラーアクティビティについて前記フラッシュメモリブロックを監視し、前記エラーアクティビティが事前定義の閾値を超えたときブロックを不良と指定する不良ブロック検出機構と、
を含むフラッシュメモリ管理プログラムと、
ｂ）前記プログラムを担持する信号担持媒体と、
を含むプログラム製品。
【請求項１６】
前記信号担持媒体は、記録可能媒体を含む、請求項１５に記載のプログラム製品。
【請求項１７】
前記信号担持媒体は、伝送媒体を含む、請求項１５に記載のプログラム製品。
【請求項１８】
前記空きブロック機構は、さらに、前記空きブロックリストウィンドウを、前記空きブロックリスト上の異なる位置に移動する、請求項１５に記載のプログラム製品。
【請求項１９】
前記ディスク保守機構は、さらに、前記ブロックリストウィンドウを、前記ブロックリスト上の異なる位置に移動する、請求項１５に記載のプログラム製品。
【請求項２０】
前記空きブロック機構は、パフォーマンス要件に従って前記空きブロックリストのサイズを調整する、請求項１５に記載のプログラム製品。
【請求項２１】
ディスク保守機構は、コストエージタイムズ式を使用して、前記ブロックリストウィンドウ内の前記ブロックの前記部分を評価する、請求項１５に記載のプログラム製品。
【請求項２２】
前記フラッシュメモリ管理プログラムは、さらに、フラッシュメモリの新しいバンクがいつ追加されたか判定する新バンク検出機構を含み、前記新バンク検出機構は、前記ブロックリストおよび前記空きブロックリストに前記新しいバンクからのブロックを追加する、請求項１５に記載のプログラム製品。
【請求項２３】
前記フラッシュメモリ管理プログラムは、さらに、フラッシュ状況機構を含み、前記フラッシュ状況機構は、前記フラッシュメモリ管理プログラムのスタートアップ時にメモリに状況情報を記憶する、請求項１５に記載のプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステムに関し、より詳細には、コンピュータシステムのフラッシュメモリに関する。
【背景技術】
【０００２】
（政府利益に関する記述）
米国政府は、本発明の全額支払済のライセンスを有し、限られた状況で、本発明の米国航空宇宙局（ＮＡＳＡ）によって認められた契約番号ＮＡＳ  １５−１００００、Ｂｏｅｉｎｇ下請け契約番号９４０Ｓ９００１の条件によって提供される合理的な条件で特許所有者に他者へのライセンス交付を要求する権利を有する。
【０００３】
（背景技術）
現代生活は、ますますコンピュータに依存するようになりつつある。コンピュータは、極端に洗練されたデバイスに進化し、多くの異なる応用例で見出すことができる。この応用例には、自動車、電話機、および他のエレクトロニクスなどの日用デバイスに見られる特定用途向けコンピュータから、ＰＤＡ、パーソナルコンピュータ、サーバ、およびメインフレームの形で見られる汎用コンピュータまでのすべてが含まれる。
【０００４】
現代のコンピュータシステムの主要なコンポーネントの１つが、メモリである。多くの異なるタイプのメモリ製品が、コンピュータシステムで一般に使用されている。コンピュータで使用されるほとんどのメモリが、揮発性であり、これは、情報を記憶するのに電力が必要であることを意味する。電源がオフにされた場合、揮発性メモリに記憶された情報は、失われる。ある応用例では、コンピュータシステム内の一部のメモリは、電源がオフにされたときでも情報を保持できなければならない。これらの応用例のために、電源がオフにされたとき失うことができない情報を記憶するために不揮発性メモリが使用される。
【０００５】
一般的なタイプの不揮発性メモリの１つは、フラッシュと呼ばれる。フラッシュメモリは、コンピュータシステムでの制御コードの記憶など、さまざまな応用例に使用されている。フラッシュメモリでは、電荷が各セルのフローティングゲートにたくわえられ、電荷のレベルによって、セルの値が決定される。フラッシュメモリでは、メモリセルのセクションが単一のアクションまたは「フラッシュ」で消去されるように、メモリが編成される。この消去には、電子が薄い誘電体層を貫通して、各メモリセルに関連するフローティングゲートから電荷が除去されるトンネル現象が使用される。
【０００６】
フラッシュメモリは、それを管理するソフトウェアに関する難点を導入する複数の動作特性を有する。たとえば、フラッシュメモリは、書き込む前に消去しなければならない。さらに、書込みのセクションサイズ（一般にページと称する）は、しばしば、消去のセクションサイズ（一般にブロックと称する）と異なる。たとえば、フラッシュメモリシステムは、２ｋバイトのページサイズを有し、したがって２ｋ増分での書込みが許容されるが、６４ｋバイトのブロックサイズを有し、一度に６４ｋセクション全体の消去だけが許容される場合がある。もう１つの難点は、フラッシュメモリは一般に寿命が限られ、故障の前に消去回数が制限されることである。最後に、フラッシュメモリは、いくつかの状況で、早期に故障する。
【０００７】
フラッシュメモリのこれらの特性のすべてが、いくつかの応用例で難点を導入し、対処されなければならない。過去のこれらの難点に対処する試みは、許容できない性能劣化につながった。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、コンピュータシステムでのフラッシュメモリの動作および使用を制御する、改善されたパフォーマンス管理システムが必要である。
【課題を解決するための手段】
【０００９】
本発明は、改善されたパフォーマンスを有するフラッシュメモリ管理のシステムおよび方法を提供する。フラッシュメモリ管理システムは、信頼性および寿命を改善すると同時によいパフォーマンスレベルを維持する形でフラッシュメモリ使用を効率的に管理し、割り振る能力を提供する。
【００１０】
フラッシュメモリ管理システムには、空きブロック機構、ディスク保守機構、および不良ブロック検出機構が含まれる。空きブロック機構は、書込みのためのあまり使用されていないブロックの選択を容易にするために、空きブロックの効率的なソートを提供する。ディスク保守機構は、フラッシュメモリブロックを効率的にクリーニングする能力を提供する。不良ブロック検出機構は、フラッシュメモリのブロックがいつ不良になる可能性が高いか検出する能力を提供する。これらの機構が、一緒に、フラッシュメモリを使用するシステムの動作効率を改善できるフラッシュメモリ管理システムを提供する。
【００１１】
これらの機構のほかに、フラッシュ状況を追跡し、新しいバンクの検出を容易にする追加物を、フラッシュメモリ管理システムに含めることができる。
本発明の前述および他の目的、特徴、および長所は、添付図面に示された本発明の好ましい実施形態の以下の特定の説明から明白になる。
【００１２】
なお、本発明の好ましい例示的実施形態を、添付図面に関して以下で説明する。図面では、同一の符号が同一の要素を示す。
【発明を実施するための最良の形態】
【００１３】
本発明は、パフォーマンスが高められたフラッシュメモリ管理のシステムおよび方法を提供する。フラッシュメモリ管理システムは、信頼性および寿命を改善すると同時によいパフォーマンスレベルを維持する形でフラッシュメモリ使用を効率的に管理し、割り振る能力を提供する。
【００１４】
フラッシュメモリ管理システムには、空きブロック機構、ディスク保守機構、不良ブロック検出機構、新バンク検出機構、およびフラッシュ状況機構が含まれる。空きブロック機構は、書込みのためのあまり使用されていないブロックの選択を容易にするために、空きブロックの効率的なソートを提供する。ディスク保守機構は、プロセッサアイドル時間中にフラッシュメモリブロックを効率的にクリーニングする能力を提供する。不良ブロック検出機構は、フラッシュメモリのブロックがいつ不良になる可能性が高いか検出する能力を提供する。フラッシュ状況機構は、フラッシュディスク内のデータの内容および状況を記述する情報を、高速アクセスメモリに記憶する。新バンク検出機構は、フラッシュメモリの新しいバンクがシステムにいつ追加されるか自動的に検出する能力を提供する。これらの機構が、一緒に、フラッシュメモリを使用するシステムの動作効率を改善できるフラッシュメモリ管理システムを提供する。
【００１５】
図１に移ると、例示的なコンピュータシステム１００が示されている。コンピュータシステム１００には、本発明を実施するのに使用できるコンピュータシステムの全般的な特徴が示されている。もちろん、これらの特徴は、単に例示であり、本発明を、より多数のまたは異なる特徴を含めることができる異なるタイプのハードウェアを使用して実施できることを理解されたい。例示的なコンピュータシステム１００には、プロセッサ１１０、ストレージインターフェース１３０、ストレージデバイス１９０、バス１７０、およびメモリ１８０が含まれる。本発明の好ましい実施形態によれば、メモリシステム１００に、フラッシュメモリ管理システムおよびフラッシュメモリ１５０が含まれる。
【００１６】
プロセッサ１１０は、システム１００の計算機能および制御機能を実行する。プロセッサ１１０には、すべてのタイプのプロセッサを含めることができ、マイクロプロセッサなどの単一の集積回路を含めることができ、あるいは、処理ユニットの機能を達成するために協力して働く適切な数の集積回路デバイスおよび／または回路ボードを含めることができる。さらに、プロセッサ１１０に、別々のコンピュータシステムで実施される複数のプロセッサを含めることができる。動作中に、プロセッサ１１０は、メモリ１８０に含まれるプログラムを実行し、したがって、コンピュータシステム１００の全般的な動作を制御する。
【００１７】
メモリ１８０は、あらゆるタイプの適切なメモリとすることができる。これには、ＳＤＲＡＭなどのさまざまなタイプのダイナミックランダムアクセスメモリ（ＤＲＡＭ）、さまざまなタイプのスタティックＲＡＭ（ＳＲＡＭ）、およびさまざまなタイプの不揮発性メモリ（ＰＲＯＭ、ＥＰＲＯＭ、およびフラッシュ）が含まれる。メモリ１８０を、単一のタイプのメモリコンポーネントとすることができ、あるいは、多数の異なるタイプのメモリコンポーネントからなるものとすることができることを理解されたい。さらに、メモリ１８０およびプロセッサ１１０を、集合的にシステム１００を含む複数の異なるコンピュータにまたがって分散することができる。
【００１８】
バス１７０は、システム１００のさまざまなコンポーネントの間で、プログラム、データ、状況、および他の情報または信号を送るように働く。バス１７０は、コンピュータシステムとコンポーネントを接続する適切な物理的手段または論理的手段とすることができる。これには、直接ハードワイヤ接続、光ファイバ、赤外線、および無線のバス技術が含まれるが、これに制限はされない。
【００１９】
ストレージインターフェース１３０は、記憶装置をコンピュータシステムにインターフェースする方法を表す。ストレージデバイス１６０は、ハードディスクドライブ、フロッピディスクドライブ、および光ディスクドライブなどの直接アクセス記憶装置を含む適切なタイプの記憶装置とすることができる。図１からわかるように、ストレージデバイス１６０に、光ディスク１９５を使用してデータを記憶するＣＤタイプデバイスを含めることができる。
【００２０】
本発明の好ましい実施形態によれば、メモリシステム１００に、フラッシュメモリ管理システムおよびフラッシュメモリ１５０が含まれる。フラッシュメモリ管理システムは、フラッシュメモリ１５０を使用するシステムの動作効率を改善できる機能を提供する。フラッシュメモリ１５０に、任意の適切なタイプおよび組合せのフラッシュメモリを含めることができる。コンピュータシステムの好ましい実施形態に、通常、より大きいシステム全体の一部として一緒に統合されるハードウェアおよびソフトウェアの組合せとして設計された組込みシステムが含まれることに留意されたい。
【００２１】
本発明について完全に機能するコンピュータシステムに関して説明するが、本発明の機構がさまざまな形のプログラム製品として配布可能であること、また、本発明が、配布の実行に使用される信号担持媒体の特定のタイプにかかわらずに同等に適用されることを当業者なら理解することを理解されたい。信号担持媒体の例に、フロッピディスク、ハードドライブ、メモリカード、および光ディスク（たとえば光ディスク１９５）などの記録可能媒体と、無線通信リンクを含むディジタル通信リンクおよびアナログ通信リンクなどの伝送媒体が含まれる。
【００２２】
図２に移ると、フラッシュメモリ管理システムが、より詳細に示されている。フラッシュメモリ管理システムに、空きブロック機構、ディスク保守機構、不良ブロック検出機構、フラッシュ状況機構、および新バンク検出機構が含まれる。空きブロック機構は、書込みのためのあまり使用されていないブロックの選択を容易にするために、空きブロックの効率的なソートを提供する。ディスク保守機構は、プロセッサアイドル時間中にフラッシュメモリブロックを効率的にクリーニングする能力を提供する。不良ブロック検出機構は、フラッシュメモリのブロックがいつ不良になる可能性が高いか検出する能力を提供する。フラッシュ状況機構は、フラッシュディスク内のデータの内容および状況を記述する情報を、高速アクセスメモリに記憶する。新バンク検出機構は、フラッシュメモリの新しいバンクがシステムにいつ追加されるか自動的に検出する能力を提供する。これらの機構が、一緒に、フラッシュメモリを使用するシステムの動作効率を改善できるフラッシュメモリ管理システムを提供する。
【００２３】
空きブロック機構は、空きブロックの効率的なソートを提供する。フラッシュメモリは、メモリが故障し始める前に可能な消去および書込みの回数が限られた、制限された寿命を有する。このゆえに、平均寿命を最大にするために、ブロックの使用量を等化することが重要である。これを達成するために、空きブロック機構は、消去され、書込みの準備ができている物理ブロックのソートされていないリストを含む空きブロックリストを管理する。これらのブロックは、ユーザアプリケーションが書込み動作を要求する時の選択の候補である。ユーザブロックが消去されたとき、そのブロックが、空きブロックリストの末尾に追加される。
【００２４】
空きブロック機構は、消去カウントに基づいて空きブロックリストからブロックを選択する。最小の消去カウントを有するメモリブロックを選択することによって、すべてのメモリブロックの間での摩耗レベリングが最適化される。したがって、空きブロックリストは、ソートされず、そのままになるが、すべてのブロック要求について、最小の消去カウントのブロックが、所与のウィンドウサイズについて返される。
【００２５】
空きブロックリスト内の効率的な探索を容易にするために、空きブロック機構は、ウィンドウ付き探索ルーチンを実施する。ウィンドウ付き探索ルーチンでは、空きブロックリストのうちで探索される部分が定義される。探索ルーチンは、最小の消去カウントを有するフラッシュメモリブロックを、空きブロックリストのウィンドウ部分から探索する。空きブロックリストのうちのウィンドウ内の部分だけが、所与の探索要求について探索されるので、探索の性能が改善される。
【００２６】
空きブロック機構は、探索の間に空きブロックリスト内のウィンドウの位置を調整する。これによって、空きブロックリスト全体を経時的にカバーできるようになり、効率的な摩耗レベリングが助長される。
【００２７】
空きブロック機構によって使用されるウィンドウのサイズは、リアルタイムパフォーマンス制約に基づいて、探索されるブロックの数を最適化するために調整することができる。ウィンドウが大きいほど、各探索中に検査される空きブロックの数が増える。ウィンドウが小さいほど、高速に探索を実行できるようになる。したがって、ウィンドウのサイズを調整することによって、空きブロック機構は、性能に関する必要とメモリブロックの摩耗レベリングの必要のバランスをとることができる。
【００２８】
ディスク保守機構は、プロセッサアイドル時間中にフラッシュメモリブロックを効率的にクリーニングする能力を提供する。フラッシュメモリでは、書込みのセクションサイズ（一般にページと称する）は、しばしば、消去のセクションサイズ（一般にブロックと称する）と異なる。たとえば、フラッシュメモリシステムは、２ｋバイトのページサイズを有し、したがって２ｋ増分での書込みが許容されるが、６４ｋバイトのブロックサイズを有し、６４ｋセクション全体の消去だけが許容される場合がある。フラッシュメモリは、メモリが故障し始める前に可能な消去の回数が限られた、制限された寿命を有するので、フラッシュメモリのブロックが受ける消去の回数を最小にすることが重要である。具体的には、ブロックの書込みおよび消去をほぼ均等に行い、その結果、全体的な摩耗が、すべてのブロックにまたがって分布するようにすることが重要である。
【００２９】
ディスク保守機構は、高パフォーマンス結果を提供できる効率的な形での摩耗レベリングを提供する。これを容易にするために、ディスク保守機構は、ブロックリストを使用する。ブロックリストは、システム内の欠陥のないユーザブロックの順序付きリストである。ブロックリスト内のブロックは、フラッシュメモリ管理システムのユーザによる使用のために使用可能なブロックである。このリストは、本質的に静的であり、変更は、欠陥を有するようになったのでブロックが除去されたとき限って発生する。
【００３０】
フラッシュブロックをいつ消去すべきかを判定するために、ディスク保守機構は、コストエージタイムズ（Ｃｏｓｔ  Ａｇｅ  Ｔｉｍｅｓ、ＣＡＴ）式を使用して、ブロックリスト内のブロックのウィンドウ付きスキャンを実施する。もちろん、既知のグリーディ（Ｇｒｅｅｄｙ）アルゴリズムおよび費用便益アルゴリズムなどの他の適切なアルゴリズムを使用することもできる。シャン（Ｍｅｉ−Ｌｉｎｇ  Ｃｈｉａｎｇ）、リー（Ｐａｕｌ  Ｃ．  Ｈ．  Ｌｅｅ）、およびチャン（Ｒｕｅｉ−Ｃｈｕａｎ  Ｃｈａｎｇ）共著、「Ｄａｔａ  Ｍａｎａｇｅｍｅｎｔ  ｉｎ  ａ  Ｆｌａｓｈ  Ｍｅｍｏｒｙ  Ｂａｓｅｄ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｅｒ」を参照されたい。
【００３１】
フラッシュブロック内のすべてのページが書き込まれたとき、そのブロックは、消去されるまで書き込むことができない。データのページが、ユーザによって更新されたとき、そのデータの前のフラッシュ位置は、古くなる。ブロック内のかなりの数のページが、古くなったとき、そのブロックは、クリーニングの候補になる。具体的には、ＣＡＴ式が、クリーニングについてブロックを評価するのに使用される。ブロックが、ＣＡＴ判断基準を満足する場合に、そのブロックが、消去され、空きブロックリストに追加される。有効なデータがブロック内に残っている場合に、そのデータは、まず、消去の前に別のブロックに移植される。ＣＡＴアルゴリズムでは、書込み要求を満足できることを保証するのに十分な数のブロックが、空きブロックリストで使用可能であることが保証される。
【００３２】
フラッシュメモリ消去の判定に使用するのに適するＣＡＴ式の例が、シャン（Ｍｅｉ−Ｌｉｎｇ  Ｃｈｉａｎｇ）、リー（Ｐａｕｌ  Ｃ．  Ｈ．  Ｌｅｅ）、およびチャン（Ｒｕｅｉ−Ｃｈｕａｎ  Ｃｈａｎｇ）共著、「Ｃｌｅａｎｉｎｇ  Ｐｏｌｉｃｉｅｓ  ｉｎ  Ｍｏｂｉｌｅ  Ｃｏｍｐｕｔｅｒｓ  Ｕｓｉｎｇ  Ｆｌａｓｈ  Ｍｅｍｏｒｙ」に記載されている。ＣＡＴ式では、ブロック内の有効なページ数、ブロック内のデータの年齢、およびブロックが消去された回数に基づいて、消去されるブロックが選択される。ウィンドウ付きスキャンによって、ブロックリスト内のブロックのうちで、ＣＡＴ式を使用する消去について評価される部分が定義される。ＣＡＴ式は、消去についてウィンドウ内のブロックを評価するのに使用される。ブロックのうちで、ウィンドウ内の部分だけが、毎回評価され、したがって、ＣＡＴ式のパフォーマンスが改善される。
【００３３】
ディスク保守機構は、評価の間にウィンドウの位置を調整する。これによって、ウィンドウをブロックのリスト全体にわたって移動できるようになり、やはり、効率的な摩耗レベリングが助長される。
【００３４】
ディスク保守機構によって使用されるウィンドウのサイズは、評価に使用可能な時間中に評価されるブロックの数を最適化するために調整することができる。ウィンドウが大きいほど、毎回評価できるブロックの数が増える。ウィンドウが小さいほど、高速に評価を実行できるようになる。したがって、ウィンドウのサイズを調整することによって、ディスク保守機構が、パフォーマンスの必要とメモリブロックの摩耗レベリングの必要のバランスをとることができる。
【００３５】
ディスク保守機構は、バックグラウンドで、プロセッサアイドル時間中にクリーニングおよびデータ移植に関してブロックを評価するのに使用することができる。ディスク保守をバックグラウンドで実行することによって、ブロック使用状況のより複雑な評価が可能になる。さらに、これによって、無効なデータで実質的に一杯のブロックからユーザデータを選択的に移植できるようになり、そのブロックを消去できるようになる。
【００３６】
不良ブロック検出機構は、ブロックが故障する可能性が高いかどうかを判定し、その結果、故障が完了する前にそのブロックをサービスから除去できるようにするのに使用される。普通のフラッシュメモリ動作では、小さい比率のフラッシュブロックが、一般的に故障する。不良ブロック検出機構は、ブロックが故障しつつある時を検出し、そのブロック内の有効なデータを新しいブロックに移動する。不良ブロック検出機構は、すべての欠陥ブロックのリストを維持し、故障しつつあるブロックが検出されたとき、そのブロックを不良ブロックリストに追加する。別々の不良ブロックリストを、システム内のフラッシュバンクごとに維持することができる。ブロックが、欠陥があると決定されたとき、そのブロックは、不良ブロックリストに追加され、もはや使用のために使用可能でなくなる。
【００３７】
不良ブロック検出機構は、フラッシュメモリシステム内の検出されたエラーを検査し、他の原因から生じたエラーを区別することによって、故障しつつあるブロックを監視する。不良ブロック検出機構は、重み付きの式を使用して、観察されたエラーがメモリの故障しつつあるブロックを示すかどうかを評価する。
【００３８】
検出機構の好ましい実施形態は、エラー検出および訂正（ＥＤＡＣ）システムによって記録されるエラーならびに書込みおよび消去に関するあるエラー状況を検査する。このエラーには、ページの読取り中に観察される訂正可能ＥＤＡＣエラー、ページの読取り中の訂正不能ＥＤＡＣエラー、ページの書込み中のフラッシュデバイスエラー（ＦＤＥ）、およびブロックの消去中に発生するすべてのエラーを含めることができる。
【００３９】
これらのエラーのうちで、読取り中の訂正不能ＥＤＡＣエラーだけが、一般に、ユーザデータの消失をもたらす。他の３つのエラーは、訂正可能であるか、データが成功裡に書き込まれたとみなされる前に発生する。しかし、これらのエラーのすべてが、故障しつつあるブロックを示す可能性がある。不良ブロック検出機構は、これらのエラーを追跡して、訂正不能ＥＤＡＣエラーが読取りイベントで発生する前に、ブロックがいつ故障するか予測する。
【００４０】
不良ブロック検出機構は、故障しつつあるブロックを示すイベントと、一時エラーなどの他の障害を区別する。一時エラーは、スプリアス電気的活動によって起こされるエラーなど、性質において一時的であるエラーである。この一時エラーでは、フラッシュメモリブロックの後続アクセスが、普通の挙動をもたらす。たとえば、宇宙および他のイオン化環境での使用のために設計されたデバイスで、フラッシュデバイスの放射硬化によって、放射に起因する永久的損傷からデバイスが保護される。しかし、これらのデバイスでは、放射が、シングルイベントアップセット（Ｓｉｎｇｌｅ  Ｅｖｅｎｔ  Ｕｐｓｅｔ、ＳＥＵ）などの一時エラーを引き起こす可能性がある。ＳＥＵエラーは、フラッシュブロックの故障を表さない。というのは、このエラーが、放射硬化されたフラッシュデバイスでは発生せず、保護されないフラッシュデータレジスタおよび状況レジスタで発生するからである。したがって、ＳＥＵから生じるハードウェアエラーは、欠陥としてのブロックのマッピングを引き起こさない。不良ブロック検出機構は、ブロックが不良であることを決定することなしに、ＳＥＵなど適度な数の一時エラーを許容することと、あまりに多くの非一時エラーが発生するのを許さないこととの間でバランスをとらなければならない。
【００４１】
これを実施するために、不良ブロック検出機構は、さまざまな条件が満たされたとき、ブロックを不良と決定する。たとえば、一実施形態で、２つの連続するブロック消去に続くエラーが発生したとき、ブロックが不良と決定される。たとえば、最初の試行と再試行の両方がエラーをもたらす時である。複数のエラーによって、エラーのありそうな原因としての一時エラーが排除される。
【００４２】
もう１つの実施形態で、ハードウェアエラーカウンタが、フラッシュブロックごとに維持されて、フラッシュ読取りエラーとフラッシュ書込みエラーの組み合わされたカウントが保持される。ハードウェアエラーカウンタがある閾値に達したとき、ブロックが、欠陥とみなされ、すべての有効なデータが移植される。１つの例で、訂正可能ＥＤＡＣエラーによって、ハードウェアエラーカウンタが１つ増分され、訂正不能ＥＤＡＣエラーによって、２つ増分される。ＦＤＥエラーによって、ハードウェアエラーカウンタが２つ増分される。例として、閾値に４がセットされる。したがって、４つの訂正可能エラー、２つの訂正不能エラー、１つの訂正不能エラーと２つの訂正可能エラー、または１つの訂正不能エラーと１つのＦＤＥが、ブロックが不良とみなされる前に発生し得る。そのようなエラーの重み付きの評価を使用することによって、故障しつつあるブロックの早期検出がもたらされると同時に、ＳＥＵに関する適度な許容範囲がもたらされる。
【００４３】
フラッシュ状況機構によって、フラッシュディスクのデータの内容および状況を記述した情報がフラッシュ状況テーブルに記憶される。フラッシュ状況テーブルは、システム内の各フラッシュブロックの状況を記述したデータ構造である。このテーブルの目的は、より低速のフラッシュメモリから読み取るのではなく、ＲＡＭに記憶されたフラッシュ情報のすばやいアクセスを可能にすることである。このテーブルは、システム内のすべてのフラッシュページをスキャンすることによって、システムスタートアップ中に移植することができる。このテーブルは、システム動作中に、新しいフラッシュページが書き込まれ、消去されたとき更新することができる。このテーブルには、ブロック使用（たとえば、システムまたはユーザ）、欠陥状況、ハードウェアエラーカウント、ブロックが割り当てられたデータクラスタ化領域、ブロック内の次の空きページ、ブロック内の無効なページの数、どのページに有効なデータが含まれるか、ならびにブロックの消去カウントおよび年齢などの情報を含めることができる。
【００４４】
フラッシュ状況テーブルの情報は、空きブロック機構によって、摩耗レベリングを容易にするのに使用される。同様に、バックグラウンドディスク保守機構は、このテーブルにアクセスして、消去すべきブロックを決定し、書込みの準備ができているブロックのソートされたリストを構築する。
【００４５】
新バンク検出機構は、フラッシュメモリの新しいバンクがシステムにいつ追加されるか自動的に検出する能力を提供する。新バンク検出機構は、製造中に検出された不良ブロックについて新しバンクをスキャンし、これらの不良ブロックを不良ブロックリストに追加する。新しいバンクは、その新しいブロックを空きブロックリストに追加し、ページを書込みに使用可能にすることによって、システムに統合される。
【００４６】
新しいフラッシュバンクがシステム内で検出されたとき、不良ブロックリストが、このバンクについて作成されて、工場からの不良ブロックが追跡される。この不良ブロックリストは、システムスタートアップ時に読み取られ、通常動作中に、他のブロックが不良になったとき更新される。不良ブロックリストによって、システムに、どのブロックが使用可能であり、どのブロックをデータの記憶に使用してはならないかが知らされる。したがって、新バンク検出機構は、新しいバンクを自動的に検出し、この新しいバンクのアクセスをサポートするのに必要なシステム構造を生成する。この特徴の存在によって、新たに挿入されたフラッシュバンクを処理するために特殊なテストプログラムを実行する必要がなくなる。
【００４７】
したがって、本発明は、高められ改善されたパフォーマンスを有するフラッシュメモリ管理のシステムおよび方法を提供する。フラッシュメモリ管理システムは、信頼性および寿命を改善すると同時によいパフォーマンスレベルを維持する形でフラッシュメモリ使用を効率的に管理し、割り振る能力を提供する。
【００４８】
本明細書に記載の実施形態および実施例は、本発明およびその特定の応用例を最もよく説明し、これによって当業者が本発明を作り、使用するのを可能にするために提示されたものである。しかし、前述の説明および例が、図示および例示のためだけに提示されたことを、当業者は理解するであろう。示された説明は、網羅的であること、または開示された正確な形態に本発明を制限することを意図されたものではない。請求項の趣旨から逸脱せずに、上記の教示に鑑みて、多数の修正形態および変形形態が可能である。
【図面の簡単な説明】
【００４９】
【図１】コンピュータシステムを示す概略図である。
【図２】フラッシュメモリ管理システムを示す概略図である。
【図１】
2005528696.tif 000003
【図２】
2005528696.tif 000004
【手続補正書】
【提出日】平成17年1月14日(2005.1.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ａ）プロセッサと、
ｂ）前記プロセッサに結合されたメモリと、
ｃ）前記メモリに常駐し、前記プロセッサによって実行されるフラッシュメモリ管理システムであって、
書込みのためにフラッシュメモリの空きブロックを突き止める空きブロック機構であって、空きブロックリスト内のフラッシュメモリブロックのうちで空きブロックリストウィンドウによって定義される部分を探索する空きブロック管理機構と、
クリーニングのためにフラッシュメモリのブロックを突き止めるディスク保守機構であって、前記ブロックリスト内のフラッシュメモリブロックのうちでブロックリストウィンドウによって定義される部分を評価するディスク保守機構と、
不良になる可能性が高いフラッシュメモリのブロックを突き止める不良ブロック検出機構であって、エラーアクティビティについて前記フラッシュメモリブロックを監視し、前記エラーアクティビティが事前定義の閾値を超えたときブロックを不良と指定する不良ブロック検出機構と、
を含むフラッシュメモリ管理システムと、
を含む装置。
【請求項２】
複数のフラッシュメモリブロックを含むフラッシュメモリシステムを管理する方法であって、
ａ）前記フラッシュメモリブロックのうちで空きブロックリストウィンドウによって定義される部分を探索することによって、書込みのために前記フラッシュメモリの空きブロックを突き止める工程と、
ｂ）前記フラッシュメモリブロックのうちでブロックリストウィンドウによって定義される部分を評価することによって、クリーニングのために前記フラッシュメモリのブロックを突き止める工程と、
ｃ）エラーアクティビティについて前記フラッシュメモリブロックを監視し、前記エラーアクティビティが事前定義の閾値を超えたときブロックを不良と指定することによって、不良になる可能性が高いフラッシュメモリのブロックを突き止める工程と、
を含む方法。
【請求項３】
前記空きブロックリストウィンドウを前記空きブロックリスト上の異なる位置に移動し、前記フラッシュメモリブロックのうちで前記異なる位置の前記空きブロックリストウィンドウによって定義される部分を探索する工程をさらに含む、請求項２に記載の方法。
【国際調査報告】
2005528696.tif 000005
2005528696.tif 000006
2005528696.tif 000007