(57)【要約】【課題】無駄な回復処理を回避し得る適切な判定が可能で、効率の良い回復処理を実現することが可能で、装置の寿命を向上させることができる記憶装置およびコンピュータシステム、並びに記憶装置のデータ処理方法を提供する。【解決手段】制御部３２は、フラッシュメモリ３５，３６の書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、待機状態に入った際、または回復処理用の所定コマンドを受けた際に、回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する。【選択図】図４
2008146253.tif 000002
【特許請求の範囲】
【請求項１】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する
記憶装置。
【請求項２】
第２メモリを有し、
各消去ブロックごとの無効化されたページ数をカウントしたカウンタテーブルが設けられており、少なくともその一部が上記第２メモリ内に格納されており、
上記制御部は、
上記回復作業の対象ブロックを、上記カウンタテーブルを参照することで選定する
請求項１記載の記憶装置。
【請求項３】
上記カウンタテーブルは分割されてフラッシュメモリ内に保存されており、
上記制御部は、
上記選択の際にその一部を上記第２メモリ内に読み出して参照する
請求項２記載の記憶装置。
【請求項４】
上記カウンタテーブルは複数の小カウンタテーブルに分割されており、当該小カウンタテーブルごとの、カウンタ値の分布状態を示すテーブルが上記第２メモリ内に格納されており、
上記制御部は、
上記テーブルを参照することで適当な小カウンタテーブルを選択し、上記小カウンタテーブルを参照することで回復作業の対象ブロックを選択する
請求項２記載の記憶装置。
【請求項５】
上記制御部は、
上記回復すべきブロックの選択においては、上記カウンタテーブルから無効ページ数が既定値に達したブロックを検索し、回復対象として選択する
請求項２記載の記憶装置。
【請求項６】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業を実施するか否かを自律的に判定し、その結果に応じて回復作業を実行する
記憶装置。
【請求項７】
第２メモリを有し、
無効化された総ページ数を示す第一のカウンタ及び未使用ブロック総数を示す第二のカウンタが上記第２メモリ内に設けられており、
上記制御部は、
回復作業の実行判定時には少なくとも上記第一および第二のカウンタを参照し、その結果に応じて回復作業を実行する
請求項６記載の記憶装置。
【請求項８】
上記制御部は、
上記判定を、
Ｎｄｐ≧α・Ｎｕｐ＋β
の判定式を用いて実施し、これが真であれば回復作業を実行する
請求項６記載の記憶装置。
Ｎｄｐ：無効化された総ページ数
Ｎｕｐ：未使用ページ総数あるいは未使用ブロック総数
α、β：判定係数
【請求項９】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
待機状態に入った際、または回復処理用の所定コマンドを受けた際には、上記回復作業を実施するか否かを自律的に判定し、さらに回復対象となるブロックを自律的に選定し、その結果に応じて回復作業を実行する
記憶装置。
【請求項１０】
待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記制御部は、
無効ページ数が既定値以上に達したブロックを検索し、そのようなブロックがあれば回復処理を実行し、
当該記憶装置の状態を検査して、さらに回復処理を実施するか否かを判定し、
上記判定の結果回復処理を実施する場合は、複数のブロックにおける無効ページ数を検査し、無効ページ数が大きなブロックを優先的に選択して、回復処理を実施する
請求項９記載の記憶装置。
【請求項１１】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、
上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
システムがアイドル状態に入った際、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する
コンピュータシステム。
【請求項１２】
第２メモリを有し、
各消去ブロックごとの無効化されたページ数をカウントしたカウンタテーブルが設けられており、少なくともその一部が上記第２メモリ内に格納されており、
上記制御部は、上記回復作業の対象ブロックを、上記カウンタテーブルを参照することで選定する
請求項１１記載のコンピュータシステム。
【請求項１３】
上記制御部は、
上記回復すべきブロックの選択においては、上記カウンタテーブルから無効ページ数が既定値に達したブロックを検索し、回復対象として選択する
請求項１２記載のコンピュータシステム。
【請求項１４】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、
上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記該フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
システムがアイドル状態に入った際、上記回復作業を実施するか否かを自律的に判定し、その結果に応じて回復作業を実行する
コンピュータシステム。
【請求項１５】
無効化された総ページ数を示す第一のカウンタおよび未使用ブロック総数を示す第二のカウンタがＲＡＭ内に設けられており、
上記制御部は、
回復作業の実行判定時には少なくとも上記第一および第二のカウンタを参照し、その結果に応じて回復作業を実行する
請求項１４記載のコンピュータシステム。
【請求項１６】
主記憶媒体としてフラッシュメモリと、
上記フラッシュメモリのアクセスの制御を行う制御部と、
上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記制御部は、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
システムがアイドル状態に入った際、上記回復作業を実施するか否かを自律的に判定し、さらに回復対象となるブロックを自律的に選定し、その結果に応じて回復作業を実行する
コンピュータシステム。
【請求項１７】
上記制御部は、システムがアイドル状態に入った際、
無効ページ数が既定値以上に達したブロックを検索し、そのようなブロックがあれば回復処理を実行し。
当該記憶装置の状態を検査して、さらに回復処理を実施するか否かを判定し、
上記判定の結果回復処理を実施する場合は、複数のブロックにおける無効ページ数を検査し、無効ページ数が大きなブロックを優先的に選択して、回復処理を実施する、
動作を自立的に実行する
請求項１６記載のコンピュータシステム。
【請求項１８】
主記憶媒体としてフラッシュメモリを有する記憶装置のデータ処理方法であって、
上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、
上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、
無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、
待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する
記憶装置のデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性メモリを含む記憶装置およびコンピュータシステム、並びに記憶装置のデータ処理方法に関するものである。
【背景技術】
【０００２】
近年、デジタルスチルカメラやモバイルコンピュータ機器の記憶媒体として、フラッシュメモリが注目されている。
【０００３】
フラッシュメモリは、トンネリングやホットエレクトロン加速を用いて、電子にゲート絶縁膜を通過させ、それらを浮遊ゲートやトラップ層に注入し、セルトランジスタの閾値を変化させることでデータを記憶させる半導体メモリである。積層ゲート構造やＭＮＯＳ構造等を用いたトランジスタ１つのみでメモリセルを構成できるため、安価かつ大容量のメモリを実現できる。
その代表例として、ＮＡＮＤ型フラッシュメモリが挙げられる。
【０００４】
図１は、ＮＡＮＤ型フラッシュメモリの内部構成例を示す図である。
図１のＮＡＮＤ型フラッシュメモリは、ビット線ＢＬ１〜ＢＬｎに接続された複数のメモリユニット１−１〜１−ｎがアレイ状に（縦横）に配列されている。
たとえば、選択用トランジスタ２のゲートが選択ゲート線ＳＬ１に接続され、選択用トランジスタ３のゲートが選択ゲート線ＳＬ２に接続されている。また、各メモリセルＮ０〜Ｎ１５のゲートがワード線ＷＬ０〜ＷＬ１５に接続されている。
【０００５】
各メモリセルＮ０〜Ｎ１５は積層ゲート構造を持ち、浮遊ゲートへの電荷蓄積量にしたがってデータを記憶する。すなわち、浮遊ゲートに多くの電子が蓄積されていると、トランジスタの閾値が上昇するので、チャージされたビット線ＢＬ１〜ＢＬｎからのメモリユニット１（−１〜−ｎ）への電流貫通の有無を、センスアンプ等を含むアクセス回路４で検出してデータ判定を行う。
【０００６】
このようなＮＡＮＤ型フラッシュメモリは、メモリセル毎にビット線へのコンタクト領域を設ける必要もないので、特に大容量で安価な記憶装置の媒体に適している。
【０００７】
ところで、一般にフラッシュメモリのプログラム速度は非常に遅く、セルあたり数百マイクロ（μ）秒を必要とする。またデータの上書きはできないので、プログラムに先立って消去を行う必要があり、これには数ｍ秒もの時間がかかる。このような問題に対しては、多くのメモリセルを並列処理することで対処している。
【０００８】
すなわち、たとえば同一ワード線ＷＬ０に接続され、ページ単位を成すメモリセル群５を、同時一括に書き込み、さらに互いにメモリユニットを共有するページ群で構成されるセルブロック６を全て一括で消去することにより、プログラムの転送速度を向上させている。
【０００９】
具体的には、たとえば非特許文献１には１ＧｂのＮＡＮＤ型フラッシュメモリが掲載されており、ページサイズを２ｋバイト、消去ブロックサイズを１２８ｋＢとしている。すなわち、一つのメモリアレイ内で１２８ｋバイトのメモリセル群を並列消去し、そこにメモリセルを２ｋバイト毎に並列でプログラムしていくことによって、１０ＭＢ／ｓのプログラム転送速度を実現している。
【００１０】
なお、同じＮＡＮＤ型フラッシュメモリにおいても、微細化や多値化の進展により、メモリの内部構成にはさまざまなバリエーションが存在する。
しかしメモリとしてみれば、そのアクセスはページと呼ばれる一括書き込み／読み出しの単位と、ブロックもしくは消去ブロックと呼ばれる一括消去単位を用いて実行され、ブロックが複数のページを含む構成であることは変わらない。
【００１１】
または、メモリデバイスが複数のフラッシュメモリチップを有し、それら複数チップを同時に動作させて並列書き込みを実施することもある。その場合、各々のチップにおけるページの集合体がメモリデバイスにおける実ページを構成し、それがこのメモリデバイスの一括書き込みの単位となる。このとき、各々のチップにおいて対応する消去ブロックの集合体もメモリデバイスの実消去ブロックを構成し、それらがメモリデバイスにおける一括消去単位となる。したがって、このようなメモリデバイスにおいても、一括消去単位である実消去ブロックは、互いに独立した書き込み単位たる実ページを複数含んで構成される。
【００１２】
なお、通常ＮＡＮＤ型フラッシュの各ページは、たとえば２ｋバイトのユーザーデータ格納領域に対して６４バイトの予備領域を有している。この予備領域には、ＮＡＮＤ型フラッシュを使用するシステム側で、パリティビット等の各種管理データを格納することが可能である。この予備領域への書き込みは、通常ユーザーデータ領域への書き込みと一括で行なう必要があり、両者は常にセットとして扱われる。
【００１３】
また、近年微細化に伴う内部構造と書き込みメカニズムの変化から、ブロック内の各ページの書き込み順序にも制約がつくようになった。則各ページの書き込みは下位アドレスから上位アドレスへの順方向に制限されており、逆方向の書き込みは禁止されている。たとえば一旦どこかのページに書き込みを実施したら、同一ブロック内のそれより下位のアドレスが未書き込みの状態でも、そこにデータを書き込むことはできない。
【非特許文献１】ＩＳＳＣＣ２００２予稿集のｐ１０６、セッション６．４
【特許文献１】特開平８−３２８７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
近年、ハードディスクの消費電力の大きさや、シーク時間の長さ、耐衝撃性や携帯性等の問題を解消すべく、フラッシュメモリにその代替が期待されている。
しかし上述の如く、フラッシュメモリにはアクセス単位を大きくしないと高速化できないという欠点がある。また、データの上書きができないので、書き換えには必ず消去が必要であり、その際の消去ブロックはさらに大きい。このようにアクセス単位に対して消去単位が数十倍大きいのは、消去時間が長く、かつ書き込み時に非選択セルにディスターブが生じるフラッシュメモリには一般的な仕様である。しかし、これによりその書き込み効率は著しく悪化する。
【００１５】
たとえば消去ブロック内の１ページのみを書き換える際の手順を図２に示す。現在最も頻繁に使用されているのは、消去ブロック単位でアドレス変換を実施するやり方である。
この場合、アドレス変換テーブル２７の論理ブロックアドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ＝ＬＢＡ）をインデックスとして、対応する消去ブロックのフラッシュメモリ上のアドレスである物理ブロックアドレス（Ｐｈｉｓｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ＝ＰＢＡ）を取得することができる。
【００１６】
たとえば、ホストまたはアプリケーションが“０ｘ５５”のブロックアドレスへのアクセスを要求した場合、そのアドレスはテーブルにより“０ｘ６Ｂ”に変換され、フラッシュメモリ２０の消去ブロック２１にアクセスが実施される。
【００１７】
このような管理下におけるフラッシュメモリ上のデータ更新手順は以下の通りである。
１．予め予備の消去済みブロック２５を用意しておく。その物理アドレスは“０ｘＡＡ”とする。
２．論理ブロックアドレス“０ｘ５５”が指定され、対応する物理ブロックアドレス”０ｘ６Ｂ”が取得され、ブロック２１内のページ２２にアクセスがなされたとする。この時フラッシュメモリの書き換え対象ブロック２１から、別途設けられたページバッファ２４を介して、予備ブロック２５にデータを順次コピーしていく。
３．更新対象となるページ２２のコピー時には、ページバッファ２４上で所望の箇所を更新してコピーを行ない、コピー先ページ２６にそれが反映される。
４．有効なページデータのコピーが全て完了したら、アドレス変換テーブル２７上で、ブロック２１と予備ブロック２５のアドレスを張り替える。
５．最後に元ブロック２１の消去を実施する。
【００１８】
このような手順によって、以降論理ブロックアドレス“０ｘ５５”に対しては、物理ブロックアドレス“０ｘＡＡ”に対応する消去ブロック、すなわち予備ブロック２５がアクセスされるようになり、全体との整合性が保たれる。
【００１９】
しかしこの場合、１ページを更新するために、ブロック２１のデータ全体を予備ブロック２７に退避させる作業が必要であり、そのためにブロック２１内の全データのページバッファ２４への読み出しと、予備ブロック２５への書き込みが必要になる。したがって現実の転送性能は著しく低いものになってしまう。
このような事情から、フラッシュメモリを用いた現在の記憶装置は、特に書き込み時においては、ハードディスクをはるかに下回る転送性能しか得られていない。
【００２０】
また、消去ブロック内の書き込み順序にも制限がついた場合、問題はさらに深刻となる。一般のファイルシステムにおいては、セクタ間の書き込み順序に保証はなされない。
したがって、消去ブロック途中から書き込みがなされることがしばしばあるが、その場合、ブロック内におけるそれより下位のアドレス領域が空いていても、そこにデータは書き込めなくなる。したがって、後でそれらの領域に書き込み要求が出ると、書き換えと同様の処理が必要となり、前述のデータ退避や消去、書き込みを繰り返さざるを得なくなってしまう。このような問題は単に転送性能を悪化させるのみならず、フラッシュメモリの消去回数を増加させ、その寿命まで低下させてしまう。
【００２１】
一方このような問題を解決すべく、追記型の記憶システムが提案されている。このようなシステムにおいては、書き換えは、更新データを空き領域に追記し、元のデータを無効化することで実施される。
より具体的には、ページ単位で論理アドレスを物理アドレスに対応させるアドレス変換テーブルを用い、書き換えは対照データの物理アドレスを変更し、記憶メディアの空き領域に追記することで実施する。
【００２２】
たとえば、特許文献１には、アドレス変換テーブルを用いた追記型記憶システムにおける管理方法の詳細が記載されている。図３に一例を示す。
アドレス変換テーブル２８からは、論理ページアドレス（Ｌｏｇｉｃａｌ  Ｐａｇｅ  Ａｄｄｒｅｓｓ  ＝ＬＰＡ）をインデックスとして、対応するページのフラッシュメモリ上のアドレスである物理ページアドレス（Ｐｈｉｓｉｃａｌ  Ｐａｇｅ  Ａｄｄｒｅｓｓ  ＝ＰＰＡ）を取得することができる。
たとえば、ホストから指定された論理ページアドレス“０ｘ５５０２”への書き込みに対して、アドレステーブルを用いてページ単位でアドレス変換を実施し、フラッシュメモリ上の物理ページアドレス“０ｘ６Ｂ０５”を取得する。これによりブロック２１内の対応するページ領域２２へアクセスが実施される。
【００２３】
一方、同ページに更新を行なう際には、フラッシュメモリ内で直接かきこめる適当な空きページ領域が検索される。たとえば物理ブロックアドレス“０ｘＡＡ”に相当する消去済み空きブロック２５の先頭ページ領域２９が適切な書き込み先として選択された場合、ページ領域２２のデータのみがページバッファ２４を介して更新され、ページ領域２９に書き込まれる。この際論理ページアドレス“０ｘ５５０２”はページ領域２９の物理アドレス“０ｘＡＡ００”にリマッピングされる。ページ領域２２上の旧データは、当面そのまま残して無効扱いとしておく。
【００２４】
このような管理を実施すれば、フラッシュメモリ内に空き領域が存在する限りは、各ページデータの更新に対して１ページ分のデータ書き込みで良い。したがって、高速に書き換えを実施することができる。その間消去の必要も無いので、フラッシュメモリの書き換え回数も大幅に低減でき、その寿命も向上させることができる。
【００２５】
しかし、このような追記型記憶システムでは、無効化した元データ領域が無駄になる。したがって、そのような領域は消去して、再度書き込みが可能となるよう回復処理を行いたい。
しかしその場合、消去ブロックが複数のページ領域を含むと、無効化されたページ領域と同じ消去ブロック内に有効データを含むページ領域が存在するケースが多発する。このようなブロックを回復させるには、消去前に有効ページのみを、他のブロックに退避させる必要がある。
【００２６】
上述のような回復処理は、ホストからのデータアクセスに応じて実施されるのが普通であった。たとえばホストが書き込み対象としたブロックに十分な空き領域が無い場合、そのブロックに対して回復処理が実施される。あるいはデータアクセスでページが無効化された際、そのページを含むブロックが検査され、その状態に応じて、そのブロックに回復処理が実施される等である。
【００２７】
しかし、そのような対処では、データアクセスに余分な作業が付帯し、アクセスパフォーマンスが劣化してしまう。したがってこのような回復作業は、記憶装置の待機時、またはシステムのアイドル時に、ユーザーに意識されることなく実施されるのが望ましい。
【００２８】
また、このような回復作業は、待機時やアイドル時にやみくもに実行すれば良いというものではなく、
１．どのブロックを回復対象として選択するか？
２．いつ回復作業を実施するか？
を適切に判定する必要がある。
【００２９】
たとえば回復対象たるブロックに有効データを含むページが多ければ、その分退避すべきページが増える上、無効状態から消去済み状態へ回復するページ数は減少する。したがって作業の効率は非常に悪くなる。
【００３０】
本発明は、無駄な回復処理を回避し得る適切な判定が可能で、効率の良い回復処理を実現することが可能で、装置の寿命を向上させることができる記憶装置およびコンピュータシステム、並びに記憶装置のデータ処理方法を提供することにある。
【課題を解決するための手段】
【００３１】
本発明の第１の観点の記憶装置は、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する。
【００３２】
好適には、第２メモリを有し、各消去ブロックごとの無効化されたページ数をカウントしたカウンタテーブルが設けられており、少なくともその一部が上記第２メモリ内に格納されており、上記制御部は、上記回復作業の対象ブロックを、上記カウンタテーブルを参照することで選定する。
【００３３】
好適には、上記カウンタテーブルは分割されてフラッシュメモリ内に保存されており、上記制御部は、上記選択の際にその一部を上記第２メモリ内に読み出して参照する。
【００３４】
好適には、上記カウンタテーブルは複数の小カウンタテーブルに分割されており、当該小カウンタテーブルごとの、カウンタ値の分布状態を示すテーブルが上記第２メモリ内に格納されており、上記制御部は、上記テーブルを参照することで適当な小カウンタテーブルを選択し、上記小カウンタテーブルを参照することで回復作業の対象ブロックを選択する。
【００３５】
好適には、上記制御部は、上記回復すべきブロックの選択においては、上記カウンタテーブルから無効ページ数が既定値に達したブロックを検索し、回復対象として選択する。
【００３６】
本発明の第２の観点の記憶装置は、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業を実施するか否かを自律的に判定し、その結果に応じて回復作業を実行する。
【００３７】
好適には、第２メモリを有し、無効化された総ページ数を示す第一のカウンタ及び未使用ブロック総数を示す第二のカウンタが上記第２メモリ内に設けられており、上記制御部は、回復作業の実行判定時には少なくとも上記第一および第二のカウンタを参照し、その結果に応じて回復作業を実行する。
【００３８】
好適には、上記制御部は、上記判定を、Ｎｄｐ≧α・Ｎｕｐ＋βの判定式を用いて実施し、これが真であれば回復作業を実行する。ただし、Ｎｄｐは無効化された総ページ数、Ｎｕｐは未使用ページ総数あるいは未使用ブロック総数、α、βは判定係数を示す。
【００３９】
本発明の第３の観点の記憶装置は、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、待機状態に入った際、または回復処理用の所定コマンドを受けた際には、上記回復作業を実施するか否かを自律的に判定し、さらに回復対象となるブロックを自律的に選定し、その結果に応じて回復作業を実行する。
【００４０】
好適には、待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記制御部は、無効ページ数が既定値以上に達したブロックを検索し、そのようなブロックがあれば回復処理を実行し、当該記憶装置の状態を検査して、さらに回復処理を実施するか否かを判定し、上記判定の結果回復処理を実施する場合は、複数のブロックにおける無効ページ数を検査し、無効ページ数が大きなブロックを優先的に選択して、回復処理を実施する。
【００４１】
本発明の第４の観点のコンピュータシステムは、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、システムがアイドル状態に入った際、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する。
【００４２】
本発明の第５の観点のコンピュータシステムは、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記該フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、システムがアイドル状態に入った際、上記回復作業を実施するか否かを自律的に判定し、その結果に応じて回復作業を実行する。
【００４３】
本発明の第６の観点のコンピュータシステムは、主記憶媒体としてフラッシュメモリと、上記フラッシュメモリのアクセスの制御を行う制御部と、上記フラッシュメモリのデータにアクセス可能な処理装置と、を有し、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記制御部は、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、システムがアイドル状態に入った際、上記回復作業を実施するか否かを自律的に判定し、さらに回復対象となるブロックを自律的に選定し、その結果に応じて回復作業を実行する。
【００４４】
本発明の第７の観点は、主記憶媒体としてフラッシュメモリを有する記憶装置のデータ処理方法であって、上記フラッシュメモリは各々独立した消去領域であるブロックを複数有し、各ブロックは各々独立した書き込み／読み出し領域であるページを複数含み、上記フラッシュメモリの書き換えは、更新後データを未使用ページに追記し、更新前データを含むページを無効化することで実施し、無効化されたページを含む消去ブロックから有効なページのデータを他のブロックにコピーし、しかる後に元ブロックを消去して、無効ページを未使用ページに回復させ、待機状態に入った際、または回復処理用の所定コマンドを受けた際に、上記回復作業の対象となるブロックを自律的に選定し、該当ブロックに回復作業を実行する。
【００４５】
本発明によれば、待機時に自動的に、或いはホストからの回復処理の実行コマンドに応じて、無効ページの回復処理を実行する。さらにその際、記憶装置自体が内部状態を検査して、回復作業の対象となるブロックを自律的に選定する機能を持っている。無効ページの多いブロックを迅速に検索し、そのようなブロックに優先的に回復処理を施す。
【発明の効果】
【００４６】
本発明によれば、フラッシュメモリにおける無効ページの回復作業を最適な時期に最適なブロックに対して施すことができ、フラッシュメモリの使用効率を極限まで向上させることが出来る。これによってアクセスパフォーマンスを向上させ、装置の寿命を向上させ、さらに電力消費を削減できる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の実施形態を図面に関連付けて説明する。
【００４８】
図４は、本発明の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。
【００４９】
本コンピュータシステムＣＯＭＳＹＳは、記憶装置３０、およびホストシステム（処理装置）５０を主構成要素として有している。
記憶装置３０は、インターフェース回路（Ｉ／Ｆ）３１、制御回路３２、内部バス３３、ページバッファ３４、ＮＡＮＤ型フラッシュメモリ３５，３６、制御回路３７、およびメモリバス３８を有する。
制御回路３２は、第２メモリとしてのＲＡＭ４０を含み、ＲＡＭ４０にはワーキングエリア４１が設けられ、アドレス変換テーブル４２、検索テーブル４３、カウンタテーブル４４、ライトポインタ４５、無効ページ総数のカウンタ４６、未使用ページカウンタ４７が構築されている。
ホストシステム５０は、ＣＰＵ、ＲＡＭ、ＲＯＭ、システムバス等を含んで構成されている。
【００５０】
記憶装置３０の内部においては、３２ビットのメモリバス３８に、１６ビットの入出力を持つ２チップの８ＧｂＮＡＮＤ型フラッシュメモリ（フラッシュメモリチップという場合もある）３５，３６が並列接続されている。２つのチップは読み出しや書き込みにおいて、同時並列にアクセスされる。すなわち、メモリバス３８は１６ビットバスを２チャンネル備えた構成となっている。各々のフラッシュメモリは書き込みや読み出しのアクセスをたとえば４ｋＢのページ単位で行う。したがって、実ページサイズとしては８ｋＢが一括アクセスされることになる。
ページバッファ３４はアクセスされたページ領域のデータを一時記憶する。フラッシュメモリ３５，３６とページバッファ３４との間のデータの送受は、制御回路３７で制御されている。
さらに、制御回路３７は、必要に応じて転送データにＥＣＣ符号化によるエラー補正を施したり、フラッシュメモリ内の欠陥ブロックの管理を実施する。両フラッシュメモリ３５，３６は，ページバッファ３４を介して記憶装置の内部バス３３との間でデータを入出力する。
すなわち、ページバッファ３４、ＮＡＮＤ型フラッシュメモリ３５，３６、制御回路３７、およびメモリバス３８の回路群は実質的に一つのフラッシュメモリデバイス（フラッシュメモリモジュールという場合もある）３９を構成し、記憶装置３０の内部バス３３に接続されているとみなすことができる。その総容量は１６Ｇｂ（２ＧＢ）であり、実ページサイズは８ｋＢである。すなわち装置内には２５６ｋ個のページデータが格納される。
【００５１】
さらに、内部バス３３にはインターフェース回路３１、および制御回路３２が接続されている。
インターフェース回路３１は、ＡＴＡやＰＣＩエクスプレス等の規格にしたがってホストシステム５０との間で、データやコマンドの送受を行う。
制御回路３２は、記憶装置の内部においてページバッファ３４とインターフェース回路３１の間のデータの送受を管理する。
制御回路３２に内蔵されたＲＡＭ４０には、プログラムを実行するためのコードエリアやワーキングエリア４１が設けられており、さらにページ単位の仮想アドレスを管理するアドレス変換テーブル４２、正常な空きブロックを検索する検索テーブル４３、各ブロックの無効ページ数を管理するカウンタテーブル４４、ライトポインタ４５、無効ページ総数のカウンタ４６、未使用ページカウンタ４７等が構築されている。
【００５２】
本コンピュータシステムＣＯＭＳＹＳにおいては、ホストシステム５０は内蔵するＣＰＵによって制御され、アプリケーションやオペレーティングシステム（ＯＳ）の要求に応じて、記憶装置３０を介して、フラッシュメモリデバイス３９にユーザーデータを保存する。
制御回路３２はその間のデータ授受に介在し、アドレス変換テーブル４２等を用いてアドレス変換を伴うアクセス管理を実施する。
【００５３】
記憶装置３０は、ハードディスクと同様に５１２バイト（Ｂｙｔｅ）のセクタをアクセス単位とする。
記憶装置内部では簡単のため、１６進数のアドレスが次のように割り振られるとする。
たとえば、外部入力アドレスが“０ｘ０５５０２Ｃ”であった場合、上位２４ビットの“０ｘ０５５０２”はページアドレスであり、最大１Ｍページを管理できる。一方、下位４ビットの“０ｘＣ”はページ領域内のセクタドレスであり、１ページ中には１６のセクタが含まれる。
本記憶装置はページバッファ３４内のデータを選択することで、１セクタ単位のランダムアクセスが可能である。
【００５４】
以下、このような記憶装置３０の内部動作を説明する。
本実施形態ではページ単位の仮想アドレス管理が採用されている。
【００５５】
図５は、アドレス変換テーブル４２、検索テーブル４３、およびカウンタテーブル４４の構成例を示す図である。また、図６は、そのようなテーブルを使用したデータアクセスのフローを示す図である。記憶装置３０の内部におけるフラッシュメモリデバイス３９への具体的アクセスは、図６のフロー図にしたがって、以下のような手順で実行される。
【００５６】
＜データの読み出し動作＞
ステップＳＴ１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ００５５０２Ｃ”のセクタドレスが入力されると、制御回路３２は論理ページアドレス部（ＬＰＡ）“０ｘ００５５０２”をインデックスにアドレス変換テーブル４２を参照し、アクセス対象たるユーザーデータの物理ページアドレスＰＰＡ“０ｘ００６０Ｂ０”を取得する。
【００５７】
ステップＳＴ２：
上記物理ページアドレスをもって、フラッシュメモリデバイス３９がアクセスされ、ページバッファ３４内にユーザーデータが格納されたページグループが読み出される。その後セクタドレス“０ｘＣ”に相当する部分がページバッファ３４から選択的にホストに出力され、読み出し動作が完了する。
さらにデータの更新は以下のように実施する。同じ“０ｘ００５５０２Ｃ”のセクタを更新するとする。
【００５８】
＜データの更新（書き込み）動作＞
ステップＳＴ１，ＳＴ２：
読み出し時と同様に、フラッシュメモリデバイス３９より読み出した所望のデータをページバッファ３４に格納する。
【００５９】
ステップＳＴ３：
ページバッファ上で所望のセクタ箇所を更新する。
【００６０】
ステップＳＴ４：
更新したユーザーデータのフラッシュメモリデバイス３９への書き込み先として、ＲＡＭ４０内に常駐した検索テーブル４３およびライトポインタ４５から、適当なページ領域の物理ページアドレスＰＰＡが選択される。
【００６１】
ここでは簡単のため、物理ページアドレスは、上位１６ビットの物理ブロックアドレス部（Ｐｈｉｓｉｃａｌ  Ｂｌｏｃｋ  Ａｂｂｒｅｓｓ  ：ＰＢＡ）と下位８ビットのページオフセット部よりなるとする。この時各消去ブロックは２５６ページ（２８）より構成される。
検索テーブル４３には、各ブロックごとにそれらが現在使用されているか、もしくは消去済みの空き状態であるかが、“Ｕｓｅｄ  Ｆｌａｇ”でマークされている。さらに欠陥ブロックの場合、“Ｄｅｆｅｃｔ  Ｆｌａｇ”が“１”となっている。
【００６２】
データの書き込みは、消去済みブロックの先頭ページから順に実行されていく。前回の書き込んだページの物理アドレスはライトポインタ４５に示されており、それがインクリメントされていくことで、書き込み先のページが下位アドレスから順次選択される。選択がブロックの末尾に達したら、それ以降のブロックの“Ｕｓｅｄ  Ｆｌａｇ”と“Ｄｅｆｅｃｔ  Ｆｌａｇ”がスキャンされ、次の未使用かつ良品のブロックが検出されて、その先頭ページが選択される。
【００６３】
ライトポインタ４５の値は現在“０ｘ００ＡＡ０１”であり、制御回路３２はまずユーザーデータの書き込み先として、それをインクリメントした物理ページアドレス“０ｘ００ＡＡ０２”を選択する。
【００６４】
ステップＳＴ５：
上記物理ページアドレスをもって、フラッシュメモリデバイス３９がアクセスされ、ページバッファ３４内のユーザーデータがフラッシュメモリデバイス３９に一括書き込みされる。
書き込みが完了すると、アドレス変換テーブル４２が更新され、論理ページアドレスＬＰＡ“０ｘ００５５０２”に対応する物理ページアドレスＰＰＡは“０ｘ００ＡＡ０２”に更新される。これに伴って旧物理ページアドレス“０ｘ００６０Ｂ０”に相当するページ領域は無効となる。
【００６５】
ステップＳＴ６：
回復判定用の各種パラメータが更新される。すなわち、上記無効ページ発生に対応して、カウンタテーブル４４の、物理ブロックアドレス“０ｘ００６０”に対応するカウンタ値を“０ｘ１０”から“０ｘ１１”にインクリメントする。さらに無効ページ総数のカウンタ４６を“０ｘ０００２Ａ５”から“０ｘ０００２Ａ６”にインクリメントする。また、上記ページ書き込みに対応して、未使用ページカウンタ４７の値を一つデクリメントする。
【００６６】
ところで、上述の如き追記型書き込みを実施した場合、更新前のデータが格納されていた物理ページアドレス“０ｘ００６０Ｂ０”に相当するページ領域はアドレス変換テーブル４２の物理アドレスフィールドから削除され、外からアクセスできなくなる。すなわち無効化される。
しかし、それらにはデータが書き込まれており、そのままでは空き領域として使用することもできない。上述のような書き換えを何度も繰り返すと、多くの無効ページ領域が発生する。それらは再度空き領域として使用できるよう、消去して回復させる必要がある。またその場合、消去ブロック“０ｘ００６０”に残された他の有効データは退避させる必要がある。
【００６７】
このような回復処理は、たとえばまず対象ブロック内の有効データを、更新の際と同様に一旦ページバッファに読み出してから、他のブロックの空き領域に追記で書き込んでいき、それによって実質的な退避を行なえば良い。すなわち有効ページを仮更新することで、その元領域を全て無効化する。その後対象ブロックを消去することによって、回復処理が実施される。
【００６８】
図７（Ａ）〜（Ｃ）には消去ブロック５１，５２内部の有効データを退避し、無効ページ領域を実質的に回復させる手順を、概念的に図解している。
【００６９】
ステップＳＴ１１：
上述の如く追記による書き換えが進行し、消去ブロック５１、５２には、一度データが書き込まれた後、更新によって無効化されたページ領域群５６、５８が、有効なページ領域群５５、５７、５９と共存しているとする。
ここで有効ページ領域のデータを残しつつ、無効化領域を空き領域に回復させる必要がある。
一方、５３、５４は現在ライトポインタ４５によって選択されて、追記用の空き領域として使用している消去ブロックを示し、ページ領域６０まで書き込みがなされている。
【００７０】
ステップＳＴ１２：
有効なページ領域群５５、５７、５９のデータを消去ブロック５３、５４内の空きページ領域群６１、６２、６３に下詰めにして順番にコピーしていく。
一方、無効なページ領域群５６、５８はコピーしない。各ページの有効／無効の判定は、たとえばデータ書き込み時に冗長部に論理ページアドレスを記載しておき、それと物理ページアドレスとの対応が、アドレス変換テーブル４２と一致するか否かをチェックすることで実施する。
有効ページの場合、対象ページ内のデータ全体をページバッファ３４に読み込み、消去ブロック５３、５４に書き込むとともに、アドレス変換テーブル４２を更新する。すなわち各々のページ領域の論理アドレスに対応する物理アドレスフィールドに、コピー先の物理ページアドレスを登録していく。
この操作は、すなわち有効ページ領域群５５、５７、５９を追記方式で書き換える作業に等しい。これにより有効ページ領域群５５、５７、５９は全て無効化される。
またこの作業に伴って、回復判定用の各種パラメータも更新される。すなわち各ページの処理ごとに、カウンタテーブル４４の該当ブロックのカウンタ値と無効ページカウンタ４６がインクリメントされ、未使用ページカウンタ４７がデクリメントされる。
実際には書き換えずコピーするのみであるが、この作業によって消去ブロック５１、５２内の全てのページは無効化され、有効ページ領域のデータは消去ブロック５３、５４に実質的に退避させられる。
【００７１】
ステップＳＴ１３：
消去ブロック５１、５２を消去する。これに伴って検索テーブル４３における該当ブロックの“Ｕｓｅｄ  Ｆｌａｇ”はゼロにリセットされる。これによってその内部は全て空き領域となり、後の追記に使用することが可能になる。
回復判定用の各種パラメータもそれに併せて更新される。すなわちカウンタテーブル４４の該当ブロックのカウンタ値はゼロにリセットされ、無効ページカウンタ４６も１ブロック分のページ数だけデクリメントされる。未使用ページカウンタ４７は１ブロック分のページ数だけインクリメントされる。
これをもって無効領域５６、５８は実効的に回復される。
【００７２】
このように無効ページ領域の回復処理は、各有効ページ領域のコピーによる退避処理と、元消去ブロックの消去よりなる。また、回復対象となる消去ブロック内の有効ページに通常の更新処理と同様の手順でダミーの更新を施し、それをもってページの退避を実行すれば、回復処理時の有効ページ退避を通常の書き込みアルゴリズムに統合させることが可能である。この場合、制御が容易になるばかりではなく、フラッシュメモリへの書き込みの均一化等、書き込み時の信頼性向上のための各種工夫を回復処理にも適用することができ、記憶装置の総合的な信頼性を向上させることができる。
【００７３】
ところで、上記回復処理は、記憶装置の待機時やシステムのアイドル時に実施することで、ユーザーからその存在を隠蔽できる。この場合たとえば、待機状態に入ると自動的に回復処理を実施する機能を記憶装置３０に設けたり、またはシステムがアイドル状態になるとホストシステム５０が回復処理用のコマンドを送信し、それに応じて記憶装置３０が回復処理を実行する。
この際、本当に回復処理を実行すべきか否かを判定し、かつ回復処理の対象ブロックを選定する機能が、システム中のどこかに必要となる。たとえばフラッシュメモリ内に多くの未使用領域が残っており、僅かな無効ページしか存在しない状態で無理に回復処理を実行しても、殆ど効果は得られない。むしろ無駄な書き込みや消去が発生してしまい、電力消費が増える上、フラッシュメモリの寿命を縮めてしまう。
一方、いつまでも回復作業をせぬまま放置すると、ユーザーから書き込みコマンドを受けた際に未使用領域が不足してしまい、まずは回復作業から実行しなければならなくなる。これは大きなアクセスレイテンシとなって、システムのパフォーマンスを劣化させてしまう。
【００７４】
ここでは上記回復処理と、それを実行するか否かの判定、及び回復対象ブロックの選択をひとまとまりの作業グループとみなして回復シーケンスと呼ぶ。回復シーケンスは記憶装置３０に実装されており、ホストシステム５０からの回復処理実行コマンドに応じて、あるいは記憶装置が待機状態に入った際に自動的に実行される。
【００７５】
上記一連の作業を回復シーケンスとして図８に示す。たとえば記憶装置３０は、待機状態に入った際、まず回復処理が必要か否かを判定する。それはたとえば装置内の無効ページ総数や空きページ総数等をチェックすることで実施され、回復処理が必要と判定された場合、以下の回復シーケンスを実行する。
【００７６】
ステップＳＴ２１：
まず、カウンタテーブル４４をスキャンして、即時回復が可能なブロックを検索する。たとえばカウンタ値が”０ｘＦＦ”のブロックは全てのページが無効化されており、有効ページを退避すること無しに、消去のみで回復できる。すなわち既に最も効率よく回復処理を実行できる状態になっており、回復処理を遅らせてもこれ以上ブロック内の無効ページは増えない。このようなブロックは即時回復処理を実施した方が良い。
なお、即時消去の基準はたとえば”０ｘＦ０”以上とする等、一定値以上として幅を持たせても良い。このようなブロックも僅かな退避処理で消去することができ、効率良く回復処理が実施できる。検索して即時回復が可能なブロックがなければ、次の判定作業に進む。
【００７７】
ステップＳＴ２２：
ステップＳＴ２１で即時回復可能なブロックが検出されたら、そのブロックを回復対象として、図７のような回復処理を実施する。なお、全てのページが無効化されたブロックに対しては、無効化判定と退避処理を最初から省略し、最初から消去のみを実施して、各種テーブルや判定パラメータを更新しても良い。
【００７８】
ステップＳＴ２３：
即時回復可能なブロックが検出されなくなったら、その先さらに回復処理を実施するか否かの判定を行う。なおここに残った使用済みブロックは、回復を遅らせることで無効ページが増えていき、より効率良く回復処理を実施できるようになるかも知れない。したがって、記憶装置の状態を検査して、ここで回復処理を実施するのが妥当か否かを見極める必要がある。
具体的には、記憶装置における回復処理の実施効果は、装置内の無効ページ数が多いほど高くなる。すなわち無効ページ総数のカウンタ４６の値が大きいほど、回復処理の妥当性が増す。また同様に、記憶装置における回復処理の緊急性は、未使用領域が少ない程高くなる。すなわち未使用ページ総数のカウンタ４７の値が小さいほど、回復処理の妥当性が増す。したがって無効ページカウンタ４６、未使用ページ総数のカウンタ４７あるいはその双方を参照して、適当なアルゴリズムを持って回復処理の妥当性を判定するのが望ましい。
【００７９】
ステップＳＴ２４： 
回復処理の実施が妥当と判定された場合は、なるべく効率的に回復処理を実施できるブロックを検索する。カウンタテーブル４４を検査することで、たとえば最も無効化ページ数の多いブロックを抽出し、それを回復対象として選択する。
【００８０】
ステップＳＴ２５： 
ステップＳＴ２４で選択されたブロックを回復対象として、図７のような回復処理を実施する。
【００８１】
ところで、ステップＳＴ２３における判定のアルゴリズムとしては、たとえば以下のようなものが挙げられる。
無効ページ総数が多くても、未使用ページ総数が多ければ、ユーザーが書き込む余裕は十分残っており、回復処理の緊急性は低い。逆に未使用ページ総数が少ない場合も、無効ページが殆どなければ、それは記憶装置の殆どの領域が有効データで埋め尽くされた状態を示しており、回復処理を無理に実施しても効果が得られない。したがって判定には双方の相関関係を使用する。この場合判定には最も単純な一次の相関式を用いるのが適当であろう。すなわち以下の判定式が真であれば回復処理の実施が妥当と判定される。
【００８２】
Ｎｄｐ≧α・Ｎｕｐ＋β
ここで、
Ｎｄｐ：無効化された総ページ数、すなわちカウンタ（４８）の値、
Ｎｕｐ：未使用ページ総数、すなわちカウンタ（４９）の値、
α、β：判定係数、
をそれぞれ示す。
【００８３】
たとえばα＝１、β＝０とすれば、無効化されたページ総数が未使用ページ総数以上になると、回復処理を実行する。判定係数は実験的に最適な値を導出しても良く、記憶装置の使用目的にしたがって調整しても良い。
また、使用中にケースに応じて判定係数を変えても良い。たとえば上のケースで一度回復処理が妥当と判定され、回復処理が実行されれば、αが１から０．５に変わる。この場合は、無効化されたページ総数が未使用ページの半分未満になるまで回復処理が進行することになる。
また、カウンタ４７は未使用ページ総数ではなく、それと略リニアな相関を持つ未使用ブロック総数をカウントしても良い。これは検索テーブル４３の”Ｕｓｅｄ  Ｆｌａｇ”が”０”となっているブロックの総数である。この場合、係数α、βをそれに合わせて変更すれば良い。
【００８４】
また、ステップＳＴ２４の選択アルゴリズムでは、必ずしも全ブロック中から無効化ページ数が最多のブロックを正確に抽出する必要はない。基本的には複数ブロックから無効化ページ数が多いブロックを優先的に抽出する工程を含めば、不作為に選択するより効率の良い回復が可能である。
たとえば限られたブロックアドレスの範囲内のみを検索したり、無効化ページ数について“０ｘＥ０〜０ｘＦＦ”“０ｘＣ０〜０ｘＤＦ”“０ｘＡ０〜０ｘＢＦ”・・・とラフなカテゴリ分けを行い、同じカテゴリに属するブロックは同等に扱って、カテゴリレベルで順位付けを行っても良い。
【００８５】
ところで、ストレージの容量が巨大化すると、カウンタテーブル４４のサイズも大きくなる。カウンタテーブル４４は２バイトのフィールドを持つので、たとえばブロック数が６４ｋあれば、サイズは１２８ｋバイトに達する。この時、
・テーブルを格納すべきＲＡＭ容量が大きくなる。
・検索対象が増えるので、カウンタ値の大きなブロックの検索に時間がかかる。
という二つの問題が発生する。
【００８６】
図９ではＲＡＭ容量の問題に対処して、カウンタテーブルをフラッシュメモリ内に保存する、第２の実施形態を示す。記憶装置のハードウエア構成は図４と同様であるが、フラッシュメモリ３５、３６は周辺回路とともに一体化した一つのフラッシュメモリデバイス３９として扱われ、６４ｋ個の消去ブロックを有し、その物理アドレスＰＢＡは“０ｘ００００”〜“０ｘＦＦＦＦ”となっている。各ブロックは２５６ページで構成されており、各ページの実サイズは８ｋＢである。すなわちフラッシュメモリデバイス３９あるいは記憶装置３０の容量は約１２８ＧＢと巨大化している。
【００８７】
カウンタテーブルは６４分割されてフラッシュメモリデバイス３９に保存されており、各小テーブルは１ｋブロックの領域をカバーしている。保存には一つのブロックが動的に確保され、ブロック内の各ページに１個ずつの小テーブルが格納される。余った空きページは書き換え用に使用される。
各小テーブルのフラッシュメモリデバイス３９内の格納場所は、ＲＡＭに常駐した二次テーブル７０に記載されている。ここではＰＢＡ“０ｘ０５２１”にカウンタテーブル保存用のブロックが確保されており、各テーブルごとに格納先のページオフセット（ブロック内のページ位置）が記載されている。二次テーブル７０の容量は６６バイトである。
【００８８】
たとえばＰＢＡ“０ｘ１０６０”のブロックにおける無効化ページ数を取得する場合は、以下の手順で行なう。
【００８９】
ステップＳＴ３１：
二次テーブル７０からＰＢＡ“０ｘ１０６０”を含む小テーブルの格納場所を取得する。これは＃４の小テーブルが該当し、そのアドレスＰＰＡは“０ｘ０５２１０１”である。
【００９０】
ステップＳＴ３２：
上記アドレスでフラッシュメモリデバイス３９をアクセスし、小テーブル７１を読み出してＲＡＭ内に格納する。
【００９１】
ステップＳＴ３３：
小テーブル７１からＰＢＡ“０ｘ１０６０”のカウンタ値“０ｘ１０”を取得する。
なおその後小テーブル７１が書き換えられた場合、それは再度フラッシュメモリデバイス３９に書き戻す必要がある。この時はカウンタテーブル用に確保したＰＢＡ“０ｘ０５２１”のブロック内に空きページを探し、そこに書き込んで二次テーブル７０の対応ページオフセット値を更新する。
【００９２】
なお、このようにカウンタテーブルをフラッシュメモリデバイス３９に格納すると、そのアクセス速度はＲＡＭよりはるかに遅いので、カウンタ値の大きなブロックの検索はさらに困難となる。この対処例を図１０に示す。
【００９３】
図１０において、分布テーブル７２は上記実施形態で分割した小テーブルごとの、所属ブロックのカウンタ値の分布状態を示している。
各ブロックの無効化ページ数のカウンタ値は、値の大小に応じて８つのカテゴリに分類されている。カテゴリごとにカウンタ値が該当するブロックの数が示されており、たとえば＃１の小テーブルにおいてはカウンタ値が”０ｘＦＦ”のブロックが４つ存在する。各フィールドは２バイト（最大１ｋブロックをカバー）なので、このテーブルの総容量は１０２４バイトと小さく、ＲＡＭに常駐させることができる。なお、このフィールドの値はブロックの有無のみを示すフラグでも良い。その場合ＲＡＭの占有領域は僅か６４バイトである。
【００９４】
たとえば全てのページが無効化され、カウンタ値が“０ｘＦＦ”となったブロックを検索する場合、以下の手順で行なう。
【００９５】
ステップＳＴ４１：
まず、分布テーブル７２において、小テーブルの先頭＃０からカウンタ値が“０ｘＦＦ”のカテゴリをスキャンし、値が”１”以上の小テーブルを検索する。ここでは＃１の小テーブルが該当した。すなわち＃１の小テーブル内には、カウンタ値“０ｘＦＦ”のブロックが４個存在することが確認された。
【００９６】
ステップＳＴ４２：
図９の二次テーブル７０から＃１の小テーブルの格納場所を取得し、フラッシュメモリデバイス３９をアクセスして該当テーブル７３をＲＡＭ内に格納する。
【００９７】
ステップＳＴ４３：
小テーブル７３のカウンタ値を先頭からスキャンして“０ｘＦＦ”のブロックを検索する。これによってＰＢＡ“０ｘ０５２０”のブロックが該当ブロックとして抽出された。
【００９８】
このようにして、たとえば図８の回復シーケンスのステップＳＴ２１において、カウンタ値“０ｘＦＦ”の即時回復可能ブロックが検索される。上のようにして抽出されたブロックにはステップＳＴ２２の処理で消去が施される。ステップＳＴ２４でカウンタ値の最も大きなカテゴリのブロックを検索する場合も、手順は同様である。検索を２段階で実施することで、迅速かつ的確に所望のブロックを抽出できる。
【００９９】
ところでここまでは、独立した記憶装置の内部に、アドレス変換等各種制御を実装する場合について説明してきた。しかしアドレス変換テーブルの管理と関連処理を、ホスト側の制御で実施することも可能である。このような形態は、特にフラッシュメモリが内部に組み込まれた、安価なコンピュータシステムに適している。そのようなコンピュータシステムの例を図１１に示す。
【０１００】
図１１は、アドレス変換テーブルの管理と関連処理を、ホスト側の制御で実施するコンピュータシステムの構成例を示す図である。
【０１０１】
この場合、ホストシステム８０ｂは、ＣＰＵ８１ｂとシステムメモリ８２ｂを含む。
ＣＰＵ８１ｂは３２ビットのシステムバス８３ｂを介してシステムメモリであるＲＡＭ８２ｂと接続されている。さらに、システムバス８３ｂにはブリッジ回路８４ｂが接続されており、ブリッジ回路８４ｂに繋がる３２ビットのデータバス３８ｂには、１６ビットの入出力を持つ２チップのＮＡＮＤ型フラッシュメモリ３５ｂ，３６ｂが並列接続されている。２つのチップは読み出しや書き込みにおいて、同時並列にアクセスされる。アクセスされたページ領域を一時記憶するページバッファ３４ｂは、ブリッジ回路８４ｂに内蔵されている。
【０１０２】
ブリッジ回路８４ｂは、ＣＰＵ８１ｂから各種コマンドを受け取り、フラッシュメモリ３５ｂ、３６ｂとＣＰＵ８１ｂまたはシステムメモリ８２ｂとの間のデータのやり取りを、ページバッファ３４ｂを用いて媒介する。また必要に応じて転送データにＥＣＣ符号化によるエラー補正を施す。
ブリッジ回路８４ｂが受け取るコマンドは、たとえばフラッシュメモリ３５ｂ、３６ｂの所定のページへのアクセスの他、同フラッシュメモリの所定ブロックの消去、および所定ページの指定アドレスへのコピー、フラッシュメモリのリセット等である。
【０１０３】
一方、システムメモリ８２ｂ内には上記フラッシュ記憶システムを制御するためのドライバ８６ｂが常駐している。このドライバ８６ｂは、ＯＳやアプリケーションからの記憶装置へのアクセスを受け、同じメモリ中に構成されたアドレス変換テーブル４２ｂを参照してアクセス時のページアドレスを変換する。
また、データ更新時には検索テーブル４３ｂとライトポインタ４５ｂを参照して書き込み先ページアドレスを決定し、更新用データとともにフラッシュメモリへの書き込み命令をブリッジ回路８４ｂに送信する。
【０１０４】
すなわちこのようなケースでは、ＣＰＵ８１ｂとシステムメモリ８２ｂよりなるホストシステム８５ｂ自体が図３における制御回路３２の役割を代替し、アドレス変換テーブルの管理と無効ページ領域の回復処理を実施する。すなわちドライバ８６ｂは各種テーブルやポインタを使用し、ＯＳやアプリケーションから論理アドレスを受け、物理アドレスＰＰＡを生成してブリッジ回路８４ｂにコマンドを送信することで、フラッシュメモリ３５ｂ、３６ｂの各種アクセスを実施する。
【０１０５】
なお、これらアドレス変換テーブル４２ｂ、検索テーブル４３ｂ、およびライトポインタ４５ｂには、たとえば図５に示したテーブル４２、４３、よびポインタ４５と同様のものが使用される。
【０１０６】
このようなシステムにおいても本発明の概念は同様に適用することが可能である。すなわちホストシステム８０ｂには、さらにＲＡＭ８２ｂ内に、各ブロックの無効ページ数を管理するカウンタテーブル４４ｂが構築されている。さらに無効ページ総数のカウンタ（４８ｂ）や未使用ページ総数のカウンタ（４９ｂ）が構築されている。
【０１０７】
ここでシステムがアイドル状態になると、ドライバ８６ｂは自律的にカウンタテーブル４４ｂから無効化ページ数の多いブロックを検索し、取得したブロックを対象として回復処理を実行する。すなわちブロック内の有効ページを他ブロックの未使用ページにコピーし、しかる後に対象ブロックを消去して未使用状態にする。カウンタテーブル４４ｂには、たとえば図５のテーブル４４と同様の構成が使用できる。
【０１０８】
より具体的には、カウンタテーブル４４ｂからカウンタ値たる無効化ページ数が既定値以上のブロックを検索し、該当ブロックに対して回復処理を実行する。
あるいはカウンタテーブル上で複数のブロックについてカウンタ値を比較し、値の大きいものを優先して回復処理を実行する。
【０１０９】
また、システムがアイドル状態になると、ドライバ８６ｂは自律的に無効ページ総数のカウンタ４６ｂと未使用ページ総数のカウンタ４７ｂを参照し、上記回復処理を実行するか否かの判定を行う。それはたとえば以下の判定式を用い、それが真であれば回復処理が実行される。
【０１１０】
Ｎｄｐ≧α・Ｎｕｐ＋β
ここで、
Ｎｄｐ：無効化された総ページ数、すなわちカウンタ（４８ｂ）の値、
Ｎｕｐ：未使用ページ総数、すなわちカウンタ（４９ｂ）の値、
α、β：判定係数、
をそれぞれ示す。
【０１１１】
また、これらの判定と回復処理は回復シーケンスとして統合することができる。回復シーケンスは、前述の実施形態と同様に、図８の手順に沿って実行すれば良い。すなわち本実施例のコンピュータシステムは、システムのアイドル時に以下の手順で回復シーケンスを実行する。
【０１１２】
ステップＳＴ２１：
まず、カウンタテーブル４４ｂから、無効ページ数が既定値を越えたブロックを検索する。
【０１１３】
ステップＳＴ２２：
上記検索で該当ブロックがあれば、それに回復処理を施す。
【０１１４】
ステップＳＴ２３：
さらに回復処理を実施するか否かを、無効ページ総数のカウンタ４６ｂあるいは未使用ページ総数のカウンタ４７ｂを参照して判定する。
【０１１５】
ステップＳＴ２４：
回復処理を実施する場合は、カウンタテーブル４４ｂ上で複数のブロックについてカウンタ値を比較し、その対象ブロックを選定する。
【０１１６】
ステップＳＴ２５：
上記選定ブロックに対して回復処理を実施する。
【図面の簡単な説明】
【０１１７】
【図１】ＮＡＮＤ型フラッシュメモリの内部構成例を示す図である。
【図２】フラッシュメモリにおける消去ブロック内の書き換え手順を説明するための図である。
【図３】フラッシュメモリにおける書き込みとマッピング手順を説明するための図である。
【図４】本発明の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。
【図５】アドレス変換テーブル、検索テーブル、およびカウンタテーブルの構成例を示す図である。
【図６】記憶装置の内部におけるフラッシュメモリデバイスへの具体的アクセス処理を説明するためのフローチャートである。
【図７】消去ブロック内部の有効データを退避し、無効ページ領域を実質的に回復させる手順を概念的に示す図である。
【図８】回復シーケンスを説明するためのフローチャートである。
【図９】消去カウンタテーブルの分割と格納を説明するための図である。
【図１０】カウンタ値の検索処理について説明するための図である。
【図１１】アドレス変換テーブルの管理と関連処理を、ホスト側の制御で実施するコンピュータシステムの構成例を示す図である。
【符号の説明】
【０１１８】
３０・・・記憶装置、３１・・・インターフェース回路、３２・・・制御回路、３３・・・内部バス、３４・・・ページバッファ、３５，３６・・・ＮＡＮＤ型フラッシュメモリ、３７・・・制御回路、３８・・・メモリバス、３９・・・フラッシュメモリデバイス（フラッシュメモリモジュール）、４０・・・ＲＡＭ、４１・・・ワーキングエリア、４２，４２ｂ・・・アドレス変換テーブル、４３，４３ｂ・・・、検索テーブル、４４，４４ｂ・・・無効カウンタテーブル、４５，４５ｂ・・・消去カウンタテーブル、４６，４６ｂ・・・ライトポインタ、５０，８０ｂ・・・ホストシステム。
【図１】
2008146253.tif 000003
【図２】
2008146253.tif 000004
【図３】
2008146253.tif 000005
【図４】
2008146253.tif 000006
【図５】
2008146253.tif 000007
【図６】
2008146253.tif 000008
【図７】
2008146253.tif 000009
【図８】
2008146253.tif 000010
【図９】
2008146253.tif 000011
【図１０】
2008146253.tif 000012
【図１１】
2008146253.tif 000013