(57)【要約】【課題】書き換え可能な不揮発性メモリ内の各物理ブロックに対する書き込み回数を効率的に満遍なく平均化できるようにする。【解決手段】ＣＰＵ１１は、フラッシュメモリ１２内の物理ブロックへの書き込みに応じて書き込み回数テーブル１４１の対応エントリ中の書き込み回数を＋１する。このテーブル１４１内の、書き込み回数がチェック回数に達したブロックと交換された物理ブロックに対応するエントリには、交換済フラグが立てられている。テーブル１４１のエントリ中の書き込み回数を＋１した結果、書き込み回数がチェック回数に達すると、ＣＰＵ１１はテーブル１４１を参照して交換済フラグが立っていないブロックのうち最も書き込み回数が少ないブロックを探す。ＣＰＵ１１は探したブロックとチェック回数に達したブロックとを交換し、テーブル１４内の、探したブロックに対応するエントリに交換済フラグを立てる。【選択図】    図１
2004326523.tif 000002
【特許請求の範囲】
【請求項１】
物理ブロック単位でのデータの書き込みが可能な第１の不揮発性メモリと、
前記第１の不揮発性メモリ内の各物理ブロックに対する書き込みの回数を示す書き込み回数情報であって、当該物理ブロックが他の物理ブロックと交換されて、当該両ブロック間で論理ブロックアドレスと物理ブロックアドレスとの対応関係が入れ換えられるブロック交換が発生したことを示す交換済フラグ情報が付加可能な書き込み回数情報を記憶する第１の書き込み回数テーブル、及び論理ブロックアドレスを当該論理ブロックアドレスに割り当てられている前記第１の不揮発性メモリ内の物理ブロックを示す物理ブロックアドレスに変換するための変換情報を記憶する第１のアドレス変換テーブルが保存される、バイト単位でのデータの書き込みが可能な第２の不揮発性メモリと、
前記第１の書き込み回数テーブル及び前記第１のアドレス変換テーブルが第２の書き込み回数テーブル及び第２のアドレス変換テーブルとしてコピーされる揮発性メモリと、
前記第１の不揮発性メモリ内の物理ブロックへのデータ書き込みに応じて、前記第２の書き込み回数テーブル内の対応する書き込み回数情報を更新する書き込み回数更新手段と、
前記第１の不揮発性メモリ内の物理ブロックへのデータ書き込みに応じて更新された前記書き込み回数情報の示す書き込み回数が所定のチェック回数に達した場合、前記第２の書き込み回数テーブルを参照して、前記交換済フラグ情報が付加されていない物理ブロックのうち、最も書き込み回数が少ない物理ブロックを探し、当該最も書き込み回数が少ない物理ブロックと前記チェック回数に達した物理ブロックとを交換するブロック交換手段であって、前記交換された物理ブロックのうち、前記最も書き込み回数が少ない物理ブロックに対応する、前記第２の書き込み回数テーブル内の書き込み回数情報に前記交換済フラグ情報を付加するブロック交換手段と、
前記第１の書き込み回数テーブル及び前記第１のアドレス変換テーブルを最新の状態を表すように予め定められたタイミングで更新するテーブル更新手段と
を具備することを特徴とする書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項２】
前記ブロック交換の発生時に、前記第２の書き込み回数テーブルを参照して、前記交換済フラグ情報が付加された書き込み回数情報に対応する物理ブロックの数をカウントし、当該物理ブロック数が前記第１の不揮発性メモリの全ブロック数の半分となった特定状態を検出する手段と、
前記検出手段により前記特定状態が検出される毎に、前記第２の書き込み回数テーブル内の全ての前記交換済フラグ情報をクリアする手段と、
前記チェック回数を、前記第１の不揮発性メモリの寿命を表す書き込み回数Ｍを定数Ｄで除したＭ／Ｄを単位に（Ｍ／Ｄ）×１から（Ｍ／Ｄ）×Ｄまで、Ｍ／Ｄずつ段階的に増加する手段であって、前記検出手段により前記特定状態が検出される毎に前記チェック回数をＭ／Ｄだけ増加する手段と
を更に具備することを特徴とする請求項１記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項３】
前記Ｄの値がＭ／Ｄ≫Ｄを満たすことを特徴とする請求項２記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項４】
前記第１の不揮発性メモリに対する物理ブロック単位のデータ書き込みの履歴を表す書き込み履歴情報を前記第２の不揮発性メモリに記録する書き込み履歴記録手段と、
前記テーブル更新手段による前記第１の書き込み回数テーブル及び前記第１のアドレス変換テーブルの更新完了に応じて、前記第２の不揮発性メモリに記録されている前記書き込み履歴情報を消去する手段とを更に具備し、
前記テーブル更新手段は、前記第２の不揮発性メモリに記録されている前記書き込み履歴情報に従って、前記予め定められたタイミングで前記第１の書き込み回数テーブル及び前記第１のアドレス変換テーブルを更新することを特徴とする請求項１記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項５】
前記書き込み履歴情報は、物理ブロックアドレスと、当該物理ブロックアドレスで指定される物理ブロックへの書き込みが行われたことを示す第１の制御コード、及び当該物理ブロックが他の物理ブロックと交換されたことを示す第２の制御コードを含む複数の制御コードの１つとを含むことを特徴とする請求項４記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項６】
前記第１の不揮発性メモリの領域を、論理的に、ユーザ領域と当該ユーザ領域内の不良ブロックと交替して用いられる物理ブロックを提供する交替領域とに分けて管理する手段と、
前記第１の不揮発性メモリ内の物理ブロックへのアクセス時に当該物理ブロックが不良ブロックであることを検出する手段と、
前記不良ブロックの検出に応じて当該不良ブロックを前記交替領域内の有効な物理ブロックに交替するブロック交替手段とを更に具備し、
前記書き込み履歴情報は、物理ブロックアドレスと、当該物理ブロックアドレスで指定される物理ブロックへの書き込みが行われたことを示す第１の制御コード、当該物理ブロックが他の物理ブロックと交換されたことを示す第２の制御コード、当該物理ブロックが前記交替領域内の有効な物理ブロックと交替されたことを示す第３の制御コードを含む複数の制御コードの１つとを含むことを特徴とする請求項４記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項７】
前記予め定められたタイミングが前記記憶装置の電源投入時であることを特徴とする請求項４記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項８】
前記予め定められたタイミングが前記第２の不揮発性メモリに一定量の前記書き込み履歴情報が溜まった時点であることを特徴とする請求項４記載の書き換え可能な不揮発性メモリを備えた記憶装置。
【請求項９】
記憶装置の記憶媒体として用いられ、物理ブロック単位でのデータの書き込みが可能な記憶装置用不揮発性メモリの制御方法において、
データ書き込みの対象となった物理ブロックが他の物理ブロックと交換されて、当該両ブロック間で論理ブロックアドレスと物理ブロックアドレスとの対応関係が入れ換えられるブロック交換が発生した場合に、前記記憶装置用不揮発性メモリ内の各物理ブロックに対する書き込みの回数を管理するための書き込み回数テーブルのエントリのうち、当該データ書き込みの対象となった物理ブロックと交換された前記他の物理ブロックに対応するエントリに設定されている書き込み回数情報にブロック交換が発生したことを示す交換済フラグ情報を付加するステップと、
前記記憶装置用不揮発性メモリ内の物理ブロックへのデータ書き込みに応じて、前記書き込み回数テーブル内の対応するエントリに設定されている書き込み回数情報を更新するステップと、
更新後の前記書き込み回数情報の示す書き込み回数が所定のチェック回数に達した場合、前記書き込み回数テーブルを参照して、前記交換済フラグ情報が付加されていない物理ブロックのうち、最も書き込み回数が少ない物理ブロックを探し、当該最も書き込み回数が少ない物理ブロックと前記チェック回数に達した物理ブロックとを交換するステップと
を具備することを特徴とする記憶装置用不揮発性メモリの制御方法。
【請求項１０】
前記ブロック交換の発生時に、前記書き込み回数テーブルを参照して、前記交換済フラグ情報が付加された書き込み回数情報に対応する物理ブロックの数をカウントし、当該物理ブロック数が前記記憶装置用不揮発性メモリの全ブロック数の半分となった特定状態を検出するステップと、
前記特定状態が検出される毎に、前記書き込み回数テーブル内の全ての前記交換済フラグ情報をクリアするステップと、
前記チェック回数を、前記記憶装置用不揮発性メモリの寿命を表す書き込み回数Ｍを定数Ｄで除したＭ／Ｄを単位に（Ｍ／Ｄ）×１から（Ｍ／Ｄ）×Ｄまで、Ｍ／Ｄずつ段階的に増加するステップであって、前記特定状態が検出される毎に前記チェック回数をＭ／Ｄだけ増加するステップと
を更に具備することを特徴とする請求項９記載の記憶装置用不揮発性メモリの制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、物理ブロック単位で書き込みが行われる書き換え可能な不揮発性メモリを記憶媒体として用いた記憶装置に係り、特に当該不揮発性メモリの各ブロック毎の書き込み回数を平均化するのに好適な、書き換え可能な不揮発性メモリを備えた記憶装置及び記憶装置用不揮発性メモリの制御方法に関する。
【０００２】
【従来の技術】
書き換え可能な不揮発性メモリとしてフラッシュメモリが良く知られている。このフラッシュメモリ、例えばブロック単位でデータの書き込みが可能なフラッシュメモリは近年、大容量化、低価格化が進んでいる。このため、この種のフラッシュメモリは、当該フラッシュメモリを記憶媒体として備えた記憶装置、例えば外部記憶装置としての利用が拡大しつつある。フラッシュメモリはバッテリバックアップが不要であることから、記憶装置には大変有用である。
【０００３】
しかし、フラッシュメモリは、書き込みの寿命が限られる欠点を内在する（例えば、特許文献１参照）。ここでいう「寿命」とはブロック毎の消去の回数である。フラッシュメモリにブロック単位でデータを書き込むときには、まず書き込みの対象となるブロックのデータを消去する必要がある。ところが、この消去によりメモリチップの劣化が起こる。このため、フラッシュメモリの同一ブロックに、ある回数の書き込み行われると、当該ブロックに正常に書き込みができなくなる。ここで、「書き込み回数」は「消去＋書き込み」の回数をいい、「消去」の回数を含む。
【０００４】
フラッシュメモリを使用して構成される記憶装置では、当該フラッシュメモリの領域の一部分だけに書き込みが集中することがある。この場合、書き込みが集中するフラッシュメモリの領域の一部分の寿命が尽きるだけではなく、それにより、当該フラッシュメモリに未だ書き込みの回数の少ない領域が残っているにも拘わらずにフラッシュメモリ全体の寿命を終息させる可能性がある。
【０００５】
このため、フラッシュメモリの寿命を最大限延ばすためには、フラッシュメモリへの書き込みを当該メモリの領域全体に亘って平均化する必要がある。その平均化のための方法として、従来は、ブロック単位の書き込みの回数を記憶しておき、書き込み回数の多いブロックと少ないブロックとを交換（スワップ）する方法が知られている（例えば、特許文献２参照）。
【０００６】
【特許文献１】
特開平５−１５０９１３号公報（段落０００３）
【０００７】
【特許文献２】
特開平１０−９１５３５号公報（段落００１６乃至段落００２４、図３）
【０００８】
【発明が解決しようとする課題】
上記した従来技術では、書き込み回数の多いブロックと少ないブロックとの交換（スワップ）が、書き込み回数の差によって行われる。しかし、この方法では、交換のための無駄な書き込みが多数発生して性能の低下を招くと共に、寿命に悪影響を及ぼすという問題がある。また、この場合書き込み回数の少ないブロックに書き換えが集中し、結果としてフラッシュメモリ内の各ブロックを満遍なく使用することができず、未だ書き込み可能なブロックが残っているにも拘わらずにフラッシュメモリ全体の寿命を終息させてしまうという問題がある。
【０００９】
本発明は上記事情を考慮してなされたものでその目的は、書き換え可能な不揮発性メモリ内の各物理ブロックに対する書き込み回数を効率的に満遍なく平均化できる、書き換え可能な不揮発性メモリを備えた記憶装置及び記憶装置用不揮発性メモリの制御方法を提供することにある。
【００１０】
【課題を解決するための手段】
本発明の１つの観点によれば、書き換え可能な不揮発性メモリを備えた記憶装置が提供される。この記憶装置は、物理ブロック単位でのデータの書き込みが可能な第１の不揮発性メモリと、この第１の不揮発性メモリ内の各物理ブロックに対する書き込みの回数を示す書き込み回数情報であって、当該物理ブロックが他の物理ブロックと交換されて、当該両ブロック間で論理ブロックアドレスと物理ブロックアドレスとの対応関係が入れ換えられるブロック交換が発生したことを示す交換済フラグ情報が付加可能な書き込み回数情報を記憶する第１の書き込み回数テーブル、及び論理ブロックアドレスを当該論理ブロックアドレスに割り当てられている上記第１の不揮発性メモリ内の物理ブロックを示す物理ブロックアドレスに変換するための変換情報を記憶する第１のアドレス変換テーブルとが保存される、バイト単位でのデータの書き込みが可能な第２の不揮発性メモリと、上記第１の書き込み回数テーブル及び上記第１のアドレス変換テーブルが第２の書き込み回数テーブル及び第２のアドレス変換テーブルとしてコピーされる揮発性メモリと、上記第１の不揮発性メモリ内の物理ブロックへのデータ書き込みに応じて、上記第２の書き込み回数テーブル内の対応する書き込み回数情報を更新する書き込み回数更新手段と、上記第１の不揮発性メモリ内の物理ブロックへのデータ書き込みに応じて更新された上記書き込み回数情報の示す書き込み回数が所定のチェック回数に達した場合、上記第２の書き込み回数テーブルを参照して、上記交換済フラグ情報が付加されていない物理ブロックのうち、最も書き込み回数が少ない物理ブロックを探し、当該最も書き込み回数が少ない物理ブロックと上記チェック回数に達した物理ブロックとを交換するブロック交換手段であって、交換された物理ブロックのうち、上記最も書き込み回数が少ない物理ブロックに対応する、上記第２の書き込み回数テーブル内の書き込み回数情報に上記交換済フラグ情報を付加するブロック交換手段と、上記第１の書き込み回数テーブル及び上記第１のアドレス変換テーブルを最新の状態を表すように予め定められたタイミングで更新するテーブル更新手段とを備えることを特徴とする。
【００１１】
このように、上記構成の記憶装置においては、チェック回数に達した物理ブロックを他の物理ブロックと交換した際に、当該他の物理ブロックに対応する、書き込み回数テーブル（第２の書き込み回数テーブル）内の書き込み回数情報に交換済フラグ情報が付加される。また、上記構成の記憶装置においては、チェック回数に達した物理ブロックと交換する物理ブロックとして、書き込み回数テーブルで書き込み回数が管理されている物理ブロックのうちの単に最も書き込み回数が少ない物理ブロックではなくて、交換済フラグ情報が付加されていない物理ブロックのうちで、最も書き込み回数が少ない物理ブロックが用いられる。これにより、交換されたばかりの物理ブロックと交換される（つまり、１つの物理ブロックが多重に交換される）不具合が発生するのを防止でき、第１の不揮発性メモリ内の各物理ブロックに対する書き込み回数を効率的に満遍なく平均化できる。
【００１２】
ここで、ブロック交換の発生時に、書き込み回数テーブルを参照して、交換済フラグ情報が付加された書き込み回数情報に対応する物理ブロックの数をカウントし、当該物理ブロック数が上記第１の不揮発性メモリの全ブロック数の半分となった特定状態を検出する手段と、この特定状態が検出される毎に、第２の書き込み回数テーブル内の全ての交換済フラグ情報をクリアする手段と、上記チェック回数を、第１の不揮発性メモリの寿命を表す書き込み回数Ｍを定数Ｄで除したＭ／Ｄを単位に（Ｍ／Ｄ）×１から（Ｍ／Ｄ）×Ｄまで、Ｍ／Ｄずつ段階的に増加する手段であって、上記特定状態が検出される毎に上記チェック回数をＭ／Ｄだけ増加する手段とを追加するとよい。
【００１３】
このような構成の記憶装置においては、各物理ブロックの書き込み回数を段階的にチェックしながら交換していくことによって、各物理ブロックの平均化がこまめに行われるため、全ブロックをより一層効率的に満遍なく平均化することができる。
【００１４】
また、上記第１の不揮発性メモリに対する物理ブロック単位のデータ書き込みの履歴を表す書き込み履歴情報を上記第２の不揮発性メモリに記録する書き込み履歴記録手段と、上記テーブル更新手段による上記第１の書き込み回数テーブル及び上記第１のアドレス変換テーブルの更新完了に応じて、上記第２の不揮発性メモリに記録されている書き込み履歴情報を消去する手段とを追加し、上記第２の不揮発性メモリに記録されている書き込み履歴情報に従って、上記予め定められたタイミングで上記第１の書き込み回数テーブル及び第１のアドレス変換テーブルが更新される構成とするとよい。
【００１５】
このような構成の記憶装置においては、第２の不揮発性メモリに対する書き込みの回数を少なくできるため、当該第２の不揮発性メモリ自体の寿命が第１の不揮発性メモリより先に尽きてしまうのを防止できる。
【００１６】
【発明の実施の形態】
以下、本発明の実施の形態につき図面を参照して説明する。図１は本発明の一実施形態に係るフラッシュメモリを備えた記憶装置の構成を示すブロック図である。図１の記憶装置は、ＣＰＵ１１と、２種のフラッシュメモリ１２及び１３と、ワークメモリ１４と、ＥＣＣ回路１５と、インタフェース（Ｉ／Ｆ）１６と、外部バス１７と、内部バス１８とを備えている。
【００１７】
ＣＰＵ１１は記憶装置全体を制御する主コントローラとして機能する。フラッシュメモリ１２は記憶装置の記憶媒体として用いられる、ＮＡＮＤ型フラッシュメモリに代表される、ブロック単位で読み書きするタイプの書き換え可能な不揮発性メモリ（第１の不揮発性メモリ）である。このタイプのフラッシュメモリ（不揮発性メモリ）は、当該メモリ内の、メモリセルアレイとデータレジスタ（一般にセクタサイズ＝５１２バイト程度の大きさがあり、データバスに直結している）との間を数μ〜数十μ秒でデータ転送できる。このため、上記タイプのフラッシュメモリ１２は、ファイル単位でアクセスする外部記憶装置の媒体として最適である。
【００１８】
フラッシュメモリ１２の領域（物理領域）は、Ｔ個のブロック（物理ブロック）から構成される。このフラッシュメモリ１２のＴ個のブロックの物理アドレス、即ち物理ブロックアドレス（ＰＢＡ）が、先頭のブロックから順番に０，１，…，Ｔ−１であるものとする。通常、１つのブロックは複数のセクタ（ＨＤＤのセクタに対応）から構成される。１ブロックのサイズは、一般に数十Ｋバイト程度である。
【００１９】
フラッシュメモリ１２の論理アドレス空間は、図２に示すように、ユーザ領域１２１と交替領域１２２とに分けて管理される。ここでは、図１の記憶装置を利用するホスト装置から認識可能なフラッシュメモリ１２の論理アドレス空間上、論理ブロックアドレス０〜ＬＸ−１までがユーザ領域１２１として定義され、ＬＸ〜Ｔ−１までが交替領域１２２として定義される。ＬＸは、交替領域１２２の先頭の論理ブロックアドレスを示すポインタ（交替領域ポインタ）である。交替領域１２２内の論理ブロックに対応する物理ブロックは、ユーザ領域１２１内の論理ブロックに対応する物理ブロックが不良ブロックの場合に、当該不良ブロックと交替するのに用いられる。ユーザ領域１２１及び交替領域１２２内の論理ブロックの論理アドレス、即ち論理ブロックアドレス（ＬＢＡ）は、フラッシュメモリ１の物理領域内の任意の物理ブロックに割り当てられる。交替領域１２２は、物理的に固定された領域ではない。
【００２０】
フラッシュメモリ１３は、ＮＯＲ型フラッシュメモリに代表される、バイト単位で読み書きするタイプの書き換え可能な不揮発性メモリ（第２の不揮発性メモリ）である。フラッシュメモリ１３は、主として、書き込み回数テーブル１３１と、アドレス変換テーブル１３２と、書き込み履歴１３３とを保存するのに用いられる。フラッシュメモリ１３の消去の単位は、フラッシュメモリ１２と同様にブロックである。
【００２１】
書き込み回数テーブル１３１は、フラッシュメモリ１３の物理ブロック毎に、当該物理ブロックに対する書き込みの回数を示す書き込み回数情報を記録するのに用いられる。この書き込み回数テーブル１３１のデータ構造例を図３に示す。ここでは、書き込み回数テーブル１３１の各エントリには、物理アドレス（物理ブロックアドレス）が０，１，２，…のように、先頭アドレス０から順に割り当てられている。つまり書き込み回数テーブル１３１のエントリｉ（ｉ＝０，１，２，…）は、物理アドレス（物理ブロックアドレス）ｉに予め対応付けられている。書き込み回数テーブル１３１の各エントリｉには、４バイト（３２ビット）が割り当てられる。この３２ビットのエントリｉ中のビット２９〜０の３０ビットは、当該エントリｉに対応する物理ブロックアドレスｉの物理ブロックにおける書き込み回数を表す。また、３２ビットのエントリｉ中のビット３１（ＭＳＢ）は、当該エントリｉに対応する物理ブロックアドレスｉの物理ブロックを論理的に他の物理ブロックと交換したことを示す交換済フラグとして用いられる。ブロック交換については後述する。また、３２ビットのエントリｉ中のビット３０は、当該エントリｉに対応する物理ブロックアドレスｉのブロックが不良ブロックであることを示す不良ブロックフラグとして用いられる。図３の例では、物理ブロックアドレス０の物理ブロックは交換済であり、物理ブロックアドレス１の物理ブロックは交替処理されていることが示されている。
【００２２】
アドレス変換テーブル１３２は、論理アドレス（論理ブロックアドレス）を当該論理アドレスに割り当てられている物理ブロックのアドレス、即ち物理アドレス（物理ブロックアドレス）に変換するための変換情報を記録したマッピングテーブルである。アドレス変換テーブル１３２のデータ構造例を図４に示す。ここでは、アドレス変換テーブル１３２の各エントリには、論理アドレス（論理ブロックアドレス）が０，１，２，…のように、先頭アドレス０から順に割り当てられている。つまりアドレス変換テーブル１３２のエントリｉ（ｉ＝０，１，２，…）は、論理アドレス（論理ブロックアドレス）ｉに予め対応付けられている。アドレス変換テーブル１３２のエントリｉには、論理アドレスｉに割り当てられている物理ブロックのアドレス、つまり物理アドレス（物理ブロックアドレス）が格納される。
【００２３】
書き込み履歴１３３は、フラッシュメモリ１３へのブロック単位の書き込み、ブロック単位の交換（ブロック交換）、及びブロック単位の交替（ブロック交替）の履歴を、対応する物理アドレス（物理ブロックアドレス）により表す。この書き込み履歴１３３のデータ構造例を図５に示す。図５から明らかなように、本実施形態において書き込み履歴１３３を構成し、物理アドレスを記録する各レコードには、４バイト、即ち３２ビット（ビット３１〜０の３２ビット）が割り当てられる。この３２ビット中のビット２７〜０の２８ビットは物理アドレス（物理ブロックアドレス）を表し、ビット３１〜２８の４ビットは制御コードを表す。各レコード中の制御コードは、“１”で当該レコード（中の物理アドレス）で示される物理ブロックへの書き込みを、“２”で当該レコードで示される物理ブロックと次のレコードで示される物理ブロックとが交換されたことを、“３”で当該レコードで示される物理ブロックが交替処理されたことを、それぞれ示す。なお、この制御コードの数値は１６進数値である。
【００２４】
物理ブロックの交換とは、２つの物理ブロックをＰＢ１及びＰＢ２とし、その物理ブロックＰＢ１及びＰＢ２が割り当てられている論理ブロックアドレスを、それぞれＬＢＡ１及びＬＢＡ２とすると、論理ブロックアドレスＬＢＡ１及びＬＢＡ２が割り当てられる物理ブロックを論理的に交換して（入れ換えて）、それぞれＰＢ２及びＰＢ１とすることをいう。つまり、物理ブロックの交換とは、２つの物理ブロック間で論理ブロックアドレスと物理ブロックアドレスとの対応関係が入れ換えられることをいう。一方、物理ブロックの交替処理とは、ある論理ブロックアドレスに割り当てられている物理ブロックが不良の場合に、当該論理ブロックアドレスに割り当てられる物理ブロックを、不良ブロックから、交替領域１２２に交替用として予め確保されている物理ブロックに交替することをいう。
【００２５】
図５の例では、レコード０及び１により、物理ブロックアドレス１２３４５及び２３４で指定されるブロックへのデータ書き込みが正常に行われたことが示されている。また、レコード２及び３により、物理ブロックアドレス９８７６及び５４３２でそれぞれ示される物理ブロックが論理的に交換されたことが示されている。また、レコード４により、上記交換された物理ブロックアドレス５４３２のブロックでエラーが発生したために、そのエラーブロックが交替領域１２２内のブロックと交替されたことが示され、レコード５により、物理ブロックアドレス１１１１で指定される交替先のブロックにデータが正常に書き込まれたことが示されている。
【００２６】
ワークメモリ１４は例えばＲＡＭであり、ＣＰＵ１１のワーク領域、及びブロック交換時にユーザデータを一時的に保持しておくための領域として用いられる。ワークメモリ１４はまた、例えば図１の記憶装置の電源投入時（立ち上げ時）に、フラッシュメモリ１３に保存されている書き込み回数テーブル１３１及びアドレス変換テーブル１３２のそれぞれコピーである、書き込み回数テーブル１４１及びアドレス変換テーブル１４２を保持する領域としても用いられる。ＣＰＵ１１は、このワークメモリ１４に格納されている書き込み回数テーブル１４１及びアドレス変換テーブル１４２を参照・更新する。フラッシュメモリ１３に保存されている書き込み回数テーブル１３１及びアドレス変換テーブル１３２を参照・更新しない理由は２つある。第１は、フラッシュメモリ１３はＲＡＭ構成のワークメモリ１４と異なってアクセス速度が遅く、テーブル参照・更新に時間がかかりすぎるためである。第２は、テーブル１３１及び１３２を直接更新するのでは、フラッシュメモリ１３自体の寿命がフラッシュメモリ１２より先に尽きてしまうからである。
【００２７】
ＥＣＣ回路１５は、フラッシュメモリ１２に書き込まれるデータに例えばセクタ単位で付加されるエラー訂正符号（Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）を生成する。ＥＣＣ回路１５はまた、フラッシュメモリ１２から読み出されるデータのエラー検出・エラー訂正を、当該データにセクタ単位で付加されているエラー訂正符号をもとにセクタ単位で行う。
【００２８】
Ｉ／Ｆ１６は、図１の記憶装置の外部インターフェースのコントローラである。Ｉ／Ｆ１６は、外部インターフェースが例えばＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）の場合には、ＳＣＳＩコントローラである。この場合、外部バス１７はＳＣＳＩバスである。内部バス１８は、ＣＰＵ１１と、フラッシュメモリ１２及び１３と、ワークメモリ１４と、ＥＣＣ回路１５と、Ｉ／Ｆ１６とを相互接続する。
【００２９】
次に、図１の記憶装置の動作について、（１）データ書き込み、（２）ブロック交換、（３）ブロック交替、（４）電源投入時処理、（５）テーブル更新を例に順に説明する。
【００３０】
（１）データ書き込み
まず、図１の記憶装置中のフラッシュメモリ１２へのデータ書き込みについて、図６のフローチャートを参照して説明する。今、図１の記憶装置を利用するホスト装置から外部バス１７を介して、例えば論理ブロックアドレスＬＢＡ１で指定されるブロックへのデータの書き込みが要求されたものとする。この場合、ＣＰＵ１１は、ワークメモリ１４に格納されているアドレス変換テーブル１４２中の、論理ブロックアドレスＬＢＡ１に対応するエントリを参照することにより、論理ブロックアドレスＬＢＡ１を当該エントリに設定されている物理ブロックアドレスに変換する（ステップＳ１）。この物理ブロックアドレスをＰＢＡ１と表現する。
【００３１】
次に、ＣＰＵ１１はワークメモリ１４にアクセスして、物理ブロックアドレスＰＢＡ１に対応する書き込み回数テーブル１４１内のエントリを参照し、そのエントリに設定されている書き込み回数（つまりＰＢＡ１で指定される物理ブロックへの書き込みの回数）が（Ｍ／Ｄ）・ｎ（ｎの初期値は１）に一致するか否かを調べることで、ブロック交換が必要か否かを判定する（ステップＳ２）。ここで、Ｍはフラッシュメモリ１２の書き込みの寿命であり、具体的には許容される書き込みの回数を示す。本実施形態では、このＭ回をＤ等分し、Ｍ／Ｄ回（チェック回数）を単位に、即ち、Ｍ／Ｄ回（ｎ＝１）、（Ｍ／Ｄ）×２回（ｎ＝２）、（Ｍ／Ｄ）×３回（ｎ＝３）、…（Ｍ／Ｄ）×Ｄ回（ｎ＝Ｄ）のそれぞれにおいて、書き込み回数の平均化を行う。例えば寿命を１０万回（Ｍ＝１０万）、Ｄを１０とすると、１０万／１０＝１０，０００回毎に書き込み回数の平均化が行われることになる。Ｄの値は、大きいほど、より満遍なく平均化が行える。しかし、Ｄの値を大きくしすぎると、ブロック交換による書き換え回数が増えるため寿命に悪影響を及ぼす。そこで、
Ｍ／Ｄ≫Ｄ
とするのが望ましい。上記例ではＭ／Ｄ＝１００００，Ｄ＝１０であることから、１００００≫１０である。
【００３２】
もし、物理ブロックアドレスＰＢＡ１で指定される物理ブロックへの書き込み回数が（Ｍ／Ｄ）・ｎ（ここでは、ｎ＝１とする）に一致するならば、ＣＰＵ１１は後述するブロック交換処理（ステップＳ３）を実行する。これに対し、上記書き込み回数が（Ｍ／Ｄ）・ｎに一致しないなら、ＣＰＵ１１は、ＰＢＡ１で指定されるフラッシュメモリ１２内の物理ブロックに、ホストから要求されたデータを書き込む（ステップＳ４）。この際、書き込みデータには、ＥＣＣ回路１５により例えばセクタ単位で生成されるエラー訂正符号が付加される。このエラー訂正符号が付加された書き込みデータは、データ書き込み終了後に読み出され、ＥＣＣ回路１５による周知のエラー検出・訂正処理に用いられる。もし、ＥＣＣ回路１５によるエラー検出・訂正処理の結果、エラー（ＥＣＣエラー）となり、つまりステップＳ４での書き込みに失敗し、ＰＢＡ１で指定された物理ブロックが不良であると判定された場合（ステップＳ５）、ＣＰＵ１１は後述するブロック交替処理（ステップＳ６）を実行する。
【００３３】
一方、ステップＳ４での書き込みに成功した場合（ステップＳ５）、ＣＰＵ１１はワークメモリ１４にアクセスして、ＰＢＡ１に対応する書き込み回数テーブル１４１内のエントリを参照し、そのエントリに設定されている書き込み回数を１インクリメントする（ステップＳ７）。本実施形態では、ＰＢＡ１で指定された物理ブロックが不良であると判定された場合、その不良ブロックはブロック交替処理の対象となることから、その不良ブロックの書き込み回数を１インクリメントする処理を省略している。しかし、不良ブロックと判定された場合にも、当該ブロックの書き込み回数を１インクリメントしてもよい。また、このインクリメント処理が、データ書き込み直後に行われる構成としてもよい。
【００３４】
次にＣＰＵ１１は、制御コード＝１とＰＢＡ１とを含むレコードｉ（ｉの初期値は０）を生成して、フラッシュメモリ１３に保存されている書き込み履歴１３３に追加する（ステップＳ８）。そしてＣＰＵ１１は、ｉを１インクリメントして（ステップＳ９）、データ書き込み処理を終了する。このｉはワークメモリ１４の所定領域に格納されており、次に生成すべきレコードの位置を示すレコードポインタである。
【００３５】
（２）ブロック交換
次に、図１の記憶装置におけるブロック交換処理（ステップＳ３）について、図７及び図８のフローチャートを参照して説明する。物理ブロックアドレスＰＢＡ１で指定される物理ブロックへのデータの書き込みの回数が（Ｍ／Ｄ）・ｎ回となっている場合（ステップＳ２）、ＣＰＵ１１はブロック交換処理（ステップＳ３）を次のように実行する。
【００３６】
まずＣＰＵ１１は、ＰＢＡ１で指定される物理ブロックとの間で交換の対象となる物理ブロックを次のように探す。即ちＣＰＵ１１は、ワークメモリ１４に格納されている書き込み回数テーブル１４１を参照し、交換済フラグが立っていないエントリのうち、最も少ない書き込み回数が設定されているエントリを探すことで、そのエントリに対応する物理ブロックアドレスの物理ブロックを探す（ステップＳ１１）。つまり、ＣＰＵ１１はステップＳ１１において、交換済フラグが立っていない物理ブロックのうち、最も書き込み回数が少ない物理ブロックを探す。この物理ブロックの物理ブロックアドレスがＰＢＡ２であるものとする。ＣＰＵ１１はまた、上記ステップＳ１１において、ワークメモリ１４に格納されているアドレス変換テーブル１４２を逆引きすることにより、物理ブロックアドレスＰＢＡ２が設定されているエントリに対応する論理ブロックアドレスＬＢＡ２を求める。
【００３７】
次にＣＰＵ１１は、アドレス変換テーブル１４２を参照し、論理ブロックアドレスＬＢＡ１，ＬＢＡ２に対応するエントリに設定されている物理ブロックアドレスを入れ換えて、それぞれＰＢＡ２，ＰＢＡ１に変更する（ステップＳ１２）。これにより、論理ブロックアドレスＬＢＡ１，ＬＢＡ２に割り当てられる物理ブロックが交換される。つまり、論理ブロックアドレスＬＢＡ１には、書き込み回数が（Ｍ／Ｄ）・ｎ回に達した物理ブロックアドレスＰＢＡ１の物理ブロックに代えて、交換済フラグが立っていないブロックのうち、最も書き込み回数が少ない、物理ブロックアドレスＰＢＡ２の物理ブロックが割り当てられる。一方、論理ブロックアドレスＬＢＡ２には、物理ブロックアドレスＰＢＡ２の物理ブロックに代えて、書き込み回数が（Ｍ／Ｄ）・ｎ回に達した物理ブロックアドレスＰＢＡ１の物理ブロックが割り当てられる。
【００３８】
次にＣＰＵ１１は、上記のブロック交換を書き込み履歴１３３に反映させるために、次の処理を行う。ここで、書き込み履歴１３３には、レコード０〜ｉ−１が記録されているものとする。まずＣＰＵ１１は、制御コード＝２とＰＢＡ１とを含むレコードｉを生成し、当該レコードｉをフラッシュメモリ１３に保存されている書き込み履歴１３３に追加する（ステップＳ１３）。次にＣＰＵ１１は、制御コード＝２とＰＢＡ２とを含むレコードｉ＋１を生成し、当該レコードｉ＋１をフラッシュメモリ１３に保存されている書き込み履歴１３３に追加する（ステップＳ１４）。そしてＣＰＵ１１は、レコードｉを指すレコードポインタｉを２だけ（２レコード分）インクリメントする（ステップＳ１５）。
【００３９】
次にＣＰＵ１１は、物理ブロックアドレスＰＢＡ２の物理ブロックの内容、つまり（ＰＢＡ２）を、ワークメモリ１４の所定領域に退避（コピー）する（ステップＳ１６）。次にＣＰＵ１１は、ＰＢＡ１で指定される物理ブロックに本来書き込むべきデータを、ＰＢＡ２で指定されるフラッシュメモリ１２内の物理ブロックに書き込む（ステップＳ１７）。もし、このステップＳ１７での書き込みに失敗し、ＰＢＡ２で指定された物理ブロックが不良であると判定された場合（ステップＳ１８）、ＣＰＵ１１はブロック交替処理（ステップＳ１９）を実行する。
【００４０】
一方、ステップＳ１７での書き込みに成功した場合（ステップＳ１８）、ＣＰＵ１１はワークメモリ１４にアクセスして、ＰＢＡ２に対応する書き込み回数テーブル１４１内のエントリを参照し、そのエントリに設定されている書き込み回数を１インクリメントする（ステップＳ２０）。またＣＰＵ１１は、このＰＢＡ２に対応する書き込み回数テーブル１４１内のエントリに交換済フラグを立てる（ステップＳ２１）。このように交換済フラグは、ブロック交換の対象となった２つの物理ブロックのうち、書き込み回数の少ない方のブロックに対応する書き込み回数テーブル１４１内のエントリに立てられる。
【００４１】
次にＣＰＵ１１は、書き込み回数テーブル１４１の全エントリを参照して、交換済フラグが立っているブロック（に対応するエントリ）の数をカウントする（ステップＳ２２）。そしてＣＰＵ１１は、交換済フラグが立っているブロックの数がフラッシュメモリ１２の全ブロック数の半分であるか否かを判定する（ステップＳ２３）。もし、交換済フラグが立っているブロックの数が全ブロック数の半分であるならば、ＣＰＵ１１はフラッシュメモリ１２内の全てのブロックが交換されたものと判断する。この場合、ＣＰＵ１１は、書き込み回数テーブル１４１内の全ての交換済フラグを一旦クリアする（ステップＳ２４）。そしてＣＰＵ１１は、チェック回数の単位を表すｎを１インクリメントする（ステップＳ２５）。これにより、インクリメント前のｎが１であったなら、このインクリメントの結果、今までＭ／Ｄ回だったチェック回数が（Ｍ／Ｄ）×２回となる。このｎの値は、フラッシュメモリ１３の所定位置に格納されている。
【００４２】
ＣＰＵ１１は、ｎを１インクリメントするとステップＳ２６に進む。またＣＰＵ１１は、交換済フラグが立っているブロックの数が全ブロック数の半分に達していなければ（ステップＳ２３）、そのままステップＳ２６に進む。ステップＳ２６において、ＣＰＵ１１は、ワークメモリ１４に退避されている、ステップＳ１７でのデータ書き込み直前に物理ブロックアドレスＰＢＡ２に格納されていたデータ、つまり旧（ＰＢＡ２）のデータを、ＰＢＡ１で指定されるフラッシュメモリ１２内の物理ブロックに書き込む（ステップＳ２６）。もし、このステップＳ２６での書き込みに失敗し、ＰＢＡ１で指定された物理ブロックが不良であると判定された場合（ステップＳ２７）、ＣＰＵ１１はブロック交替処理（ステップ２８）を実行する。一方、ステップＳ２６での書き込みに成功した場合（ステップＳ２７）、ＣＰＵ１１はワークメモリ１４にアクセスして、ＰＢＡ１に対応する書き込み回数テーブル１４１内のエントリを参照し、そのエントリに設定されている書き込み回数を１インクリメントする（ステップＳ２８）。これにより、ステップＳ３のブロック交換処理は終了する。
【００４３】
次に、ブロック交換の具体例と交換済フラグを設ける理由とについて、図９乃至図１２を参照して説明する。まず、図９に示すように、論理ブロックアドレス０〜９に割り当てられている１０個の物理ブロックが存在し、且つ値の小さな論理ブロックアドレスに割り当てられる物理ブロックほど書き込み回数が多いものとする。つまり、値の小さな論理ブロックアドレスほど書き込みが頻繁に発生する傾向があるものとする。この場合、１０個の物理ブロックの書き込み回数を平均化するには、論理ブロックアドレス０と９にそれぞれ割り当てられる物理ブロック、論理ブロックアドレス１と８にそれぞれ割り当てられる物理ブロック、論理ブロックアドレス２と７にそれぞれ割り当てられる物理ブロック、…というように、交換の対象となる物理ブロックを、書き込み回数が一番多いブロックと一番少ないブロック、２番目に多いブロックと２番目に少ないブロック、…のように組み合わせるのがよい。
【００４４】
図１０は、論理ブロックアドレス０に割り当てられている物理ブロックＰａの書き込み回数がＭ／Ｄ回となったため、当該物理ブロックＰａを、論理ブロックアドレス９に割り当てられている物理ブロックＰｂと交換した状態を示す。このブロック交換により、論理ブロックアドレス０に割り当てられる物理ブロックは、一番書き込みが多かった物理ブロックＰａから一番書き込み回数の少ない物理ブロックＰｂとなる。
【００４５】
その後、次に書き込みが多かった物理ブロックＰｃの書き込み回数がＭ／Ｄ回に達したとする。もし交換済フラグを設けずに、物理ブロックＰｃをその時点で書き込み回数が一番少ない物理ブロックと交換するならば、図１１に示すように、先ほど交換したばかりの物理ブロックＰｂと交換することになる。この場合、論理ブロックアドレス１に割り当てられる物理ブロックは書き込み回数が一番少ない物理ブロックＰｂとなるものの、書き込みが頻繁に発生する論理ブロックアドレス０に割り当てられる物理ブロックは書き込み回数がＭ／Ｄ回となった物理ブロックＰｃとなってしまう。これでは最初に行った交換が無駄になってしまう。
【００４６】
そこで本実施形態では、このような無駄を防ぐために交換済フラグを設け、書き込み回数がＭ／Ｄ回となったために一度交換されたブロックが再度交換されることを禁止している。この様子を図１２に示す。図１２の例では、物理ブロックＰｃは、交換済フラグが立っていない物理ブロックのうち、最も書き込み回数の少ない物理ブロックＰｄと交換される。なお、交換フラグが立っている物理ブロックの書き込み回数がＭ／Ｄ回になった場合には、そのブロックは、別の交換フラグの立っていないブロックと交換可能である。
【００４７】
本実施形態では、前述したように、ブロック交換に伴うステップＳ２１の処理の結果、交換済フラグの立っているブロックの数が全ブロック数の半分になった時点、つまりフラッシュメモリ１２内の全てのブロックが交換された時点で、書き込み回数テーブル１４１内の全ての交換済フラグがクリアされる（ステップＳ２２〜Ｓ２４）。そして、ブロック交換の判定に用いられるチェック回数（書き込み回数）の単位を表すｎが１インクリメントされる。これにより、チェック回数が１単位分、つまりＭ／Ｄ回だけ加算され、例えば今までチェック回数がＭ／Ｄ回であったならば、チェック回数は（Ｍ／Ｄ）×２回となる。以降、書き込み・ブロック交換が繰り返される。そして、交換済フラグの立ったブロックの数が全ブロック数の半分になる都度、全ての交換済フラグをクリアしながら、チェック回数が（Ｍ／Ｄ）×３、（Ｍ／Ｄ）×４…のように、Ｍ／Ｄずつ増加される。このように本実施形態においては、ブロック全体の書き込み回数を段階的にチェックしながら交換していくことによって、一部のブロックだけが寿命になることを防ぎ、全ブロックをより効率的に満遍なく平均化することができる。
【００４８】
（３）ブロック交替
次に、図１の記憶装置における、ブロック交替処理（例えば、ステップＳ６）について、図１３のフローチャートを参照して説明する。今、物理ブロックアドレスＰＢＡ１で指定される物理ブロックへのデータの書き込みに失敗し、当該物理ブロックが不良であると判定されたものとする（ステップＳ５）。この場合、ＣＰＵ１１はブロック交替処理（ステップＳ６）を次のように実行する。
【００４９】
まずＣＰＵ１１は、書き込み回数テーブル１４１を参照し、ＰＢＡ１に対応する書き込み回数テーブル１４１内エントリに不良ブロックフラグを立てる（ステップＳ３１）。次にＣＰＵ１１は、制御コード＝３とＰＢＡ１とを含むレコードｉを生成し、当該レコードｉをフラッシュメモリ１３に保存されている書き込み履歴１３３に追加する（ステップＳ３２）。
【００５０】
次にＣＰＵ１１は、現時点における交替領域１２２の先頭の論理ブロックアドレス（交替領域ポインタ）であるＬＸに対応する、アドレス変換テーブル１４２内のエントリを参照することにより、当該ＬＸを当該エントリに設定されている物理ブロックアドレスに変換する（ステップＳ３３）。この物理ブロックアドレス、つまり論理ブロックアドレスＬＸに割り当てられている物理ブロックの物理ブロックアドレスをＰＸと表現する。次にＣＰＵ１１は、書き込み回数テーブル１４１中の、物理ブロックアドレスＰＸに対応するエントリを参照する（ステップＳ３４）。そしてＣＰＵ１１は、ＰＸに対応する書き込み回数テーブル１４１中のエントリに不良ブロックフラグが立っているか否かを判定する（ステップＳ３５）。
【００５１】
もし、ＰＸに対応する書き込み回数テーブル１４１中のエントリに不良ブロックフラグが立っているならば、ＣＰＵ１１はＰＸで指定される物理ブロックは不良ブロックであると判断する。この場合、先のステップＳ５で不良ブロックであると判定された（ＰＢＡ１で指定される）物理ブロックを、ＰＸで指定される物理ブロックに交替することはできない。そこでＣＰＵ１１は、ＬＸを１インクリメントし（ステップＳ３６）、そのインクリメント後の論理ブロックアドレスＬＸに割り当てられている物理ブロックについて、不良ブロックであるか否かを判定するための処理（ステップＳ３３〜Ｓ３５）を再び実行する。このＬＸの値は、ワークメモリ１４及びフラッシュメモリ１３の所定位置に格納されている。但し、参照・更新されるのはワークメモリ１４内のＬＸであり、フラッシュメモリ１３内のＬＸは通常は参照・更新されない。フラッシュメモリ１３内のＬＸの参照・更新については後述する。
【００５２】
一方、ＰＸに対応する書き込み回数テーブル１４１中のエントリに不良ブロックフラグが立っていないならば、ＣＰＵ１１はＰＸで指定される物理ブロックは正常なブロックであると判断する。この場合、ＣＰＵ１１はアドレス変換テーブル１４２を参照し、論理ブロックアドレスＬＢＡ１に対応するエントリに設定されている物理ブロックアドレスをＰＸに変更する（ステップＳ３７）。これにより、論理ブロックアドレスＬＢＡ１に割り当てられる物理ブロックが、物理ブロックアドレスがＰＢＡ１の不良ブロックから、交替領域１２２に確保されていた、物理ブロックアドレスがＰＸの物理ブロックに交替される。そこでＣＰＵ１１は、交替領域１２２の先頭の論理ブロックアドレスを示す交替領域ポインタＬＸを１インクリメントする（ステップＳ３８）。
【００５３】
次にＣＰＵ１１は、ＰＢＡ１で指定される物理ブロックにステップＳ４で書き込んだのと同一のデータを、ＰＸで指定されるフラッシュメモリ１２内の物理ブロックに書き込む（ステップＳ３９）。もし、ステップＳ３９での書き込みに失敗し、ＰＸで指定された物理ブロックが不良であると判定された場合（ステップＳ４０）、ＣＰＵ１１は上記ステップＳ６と同様のブロック交替処理（ステップＳ４１）を実行する。一方、ステップＳ３９での書き込みに成功した場合（ステップＳ４０）、ＣＰＵ１１はＰＸに対応する書き込み回数テーブル１４１内のエントリを参照し、そのエントリに設定されている書き込み回数を１インクリメントする（ステップＳ４２）。これにより、ステップＳ６のブロック交替処理は終了する。
【００５４】
ここでは、フラッシュメモリ１２内の物理ブロックへのデータの書き込みに失敗して、当該ブロックが不良ブロックと判定された場合に実行されるブロック交替処理について説明した。しかし、フラッシュメモリ１２内の物理ブロックへのデータ書き込み以外のアクセス時、つまり当該ブロックからのデータの読み出し時に、当該ブロックが不良ブロックであると判定された場合にも、上述のブロック交替処理は行われる。但し、エラー訂正不可能な不良ブロックについては、当該不良ブロックのデータが確定できない。この場合、エラー訂正不可能な不良ブロックを交替処理の対象外とするか、交替ブロックにダミーデータを書き込めばよい。
【００５５】
（４）電源投入時処理
次に、図１の記憶装置の電源が投入（ＯＮ）された際の処理について図１４のフローチャートを参照して説明する。まずＣＰＵ１１は、電源投入時の初期化処理の中で、フラッシュメモリ１３に保存されている書き込み回数テーブル１３１及びアドレス変換テーブル１３２をワークメモリ１４の所定領域にそれぞれ書き込み回数テーブル１４１及びアドレス変換テーブル１４２としてコピーする（ステップＳ５１，Ｓ５２）。
【００５６】
次にＣＰＵ１１は、フラッシュメモリ１３に確保されている書き込み履歴用領域にアクセスすることにより、当該領域内に書き込み履歴１３３が保存されている（残されている）か否かを判定する（ステップＳ５３）。
【００５７】
もし、書き込み履歴１３３が保存されている場合、当該書き込み履歴１３３は、現在フラッシュメモリ１３に保存されている書き込み回数テーブル１３１及びアドレス変換テーブル１３２が最も最近に更新された後の書き込み履歴を示す。この場合、ＣＰＵ１１は、書き込み履歴１３３を時系列順に参照することにより、書き込み回数テーブル１３１及びアドレス変換テーブル１３２を更新する（ステップＳ５４）。つまり、ＣＰＵ１１は書き込み履歴１３３の内容を書き込み回数テーブル１４１及びアドレス変換テーブル１４２に反映させる。
【００５８】
次にＣＰＵ１１は、その時点においてワークメモリ１４に格納されている書き込み回数テーブル１４１及びアドレス変換テーブル１４２、即ち書き込み履歴１３３の内容が反映されていない、更新前の書き込み回数テーブル１３１及びアドレス変換テーブル１３２のコピーを、それぞれ更新後の最新の書き込み回数テーブル１３１及びアドレス変換テーブル１３２で置き換えて、新たなを書き込み回数テーブル１４１及びアドレス変換テーブル１４２とする（ステップＳ５５）。そしてＣＰＵ１１は、書き込み履歴１３３をフラッシュメモリ１３から消去して、電源投入時の処理を終了する（ステップＳ５６）。この場合、レコードポインタｉは初期値０に設定される。
【００５９】
一方、書き込み履歴１３３が保存されていない場合、現在フラッシュメモリ１３に保存されている書き込み回数テーブル１３１及びアドレス変換テーブル１３２の内容は、フラッシュメモリ１２の最新の状態を表している。この場合、書き込み回数テーブル１３１及びアドレス変換テーブル１３２のコピーである、ワークメモリ１４上の書き込み回数テーブル１４１及びアドレス変換テーブル１４２の内容もフラッシュメモリ１２の最新の状態を表している。そこでＣＰＵ１１は、そのまま電源投入時の処理を終了する。
【００６０】
本実施形態では、上記したように、書き込み回数テーブル１３１及びアドレス変換テーブル１３２を更新する前に、その更新前の書き込み回数テーブル１３１及びアドレス変換テーブル１３２をワークメモリ１４にコピーしている。その理由は、フラッシュメモリ１３上で当該書き込み回数テーブル１３１及びアドレス変換テーブル１３２を更新した際に、更新に失敗しても、元の状態に戻せるようにするためである。なお、書き込み回数テーブル１３１及びアドレス変換テーブル１３２のコピーである、ワークメモリ１４上の書き込み回数テーブル１４１及びアドレス変換テーブル１４２を対象に、書き込み履歴１３３に従う更新処理を行うようにしてもよい。この場合、更新後の書き込み回数テーブル１４１及びアドレス変換テーブル１４２で、フラッシュメモリ１３上の書き込み回数テーブル１３１及びアドレス変換テーブル１３２を書き換えて、新たな書き込み回数テーブル１３１及びアドレス変換テーブル１３２とすればよい。但し、テーブル全体の更新となるため、フラッシュメモリ１３の寿命が先に尽きる虞がある。
【００６１】
（５）テーブル更新
次に、図１の記憶装置におけるテーブル更新処理（ステップＳ５４）について、図１５のフローチャートを参照して説明する。まずＣＰＵ１１は、ワークメモリ１４上の所定領域に初期値０のレコードポインタｉを設定する（ステップＳ６１）。次にＣＰＵ１１は、フラッシュメモリ１３に保存されている書き込み履歴１３３中のレコードのうち、レコードポインタｉの指定するレコードｉを参照する（ステップＳ６２）。そしてＣＰＵ１１は、レコードｉ中の制御コードが１，２，３のいずれであるかを判別する（ステップＳ６３）。
【００６２】
もし、レコードｉ中の制御コードが１の場合、ＣＰＵ１１はフラッシュメモリ１３に保存されている書き込み回数テーブル１３１にアクセスし、当該レコードｉ中の物理ブロックアドレスＰＢＡｉに対応する書き込み回数テーブル１３１内のエントリに設定されている書き込み回数を１インクリメントする（ステップＳ６４）。これにより、レコードｉで示されるＰＢＡｉの物理ブロックへの書き込みが、書き込み回数テーブル１３１の対応エントリに反映される。
【００６３】
次にＣＰＵ１１はワークメモリ１４上のレコードポインタｉを１インクリメントする（ステップＳ６５）。ＣＰＵ１１は、このインクリメント後のレコードポインタｉの指定するレコードｉが書き込み履歴１３３中に存在するか否かを判定する（ステップＳ６６）。もし、レコードｉが書き込み履歴１３３中に存在するならば、ＣＰＵ１１はステップＳ６２の処理に戻る。
【００６４】
一方、レコードｉ中の制御コードが２の場合（ステップＳ６３）、ＣＰＵ１１は書き込み履歴１３３中の次のレコード（ｉ＋１）を参照する（ステップＳ６７）。次にＣＰＵ１１は、レコード（ｉ＋１）中の物理ブロックアドレスＰＢＡ（ｉ＋１）で、フラッシュメモリ１３に保存されているアドレス変換テーブル１３２を逆引きすることにより、当該ＰＢＡ（ｉ＋１）に対応する論理ブロックアドレスＬＢＡ（ｉ＋１）を求める（ステップＳ６８）。即ちＣＰＵ１１は、物理ブロックアドレスＰＢＡ（ｉ＋１）が設定されているアドレス変換テーブル１３２内エントリに対応する論理ブロックアドレスＬＢＡ（ｉ＋１）を求める。
【００６５】
次にＣＰＵ１１は、論理ブロックアドレスＬＢＡｉ，ＬＢＡ（ｉ＋１）に対応するアドレス変換テーブル１３２内の両エントリに設定されている物理ブロックアドレスを、それぞれＰＢＡ（ｉ＋１），ＰＢＡｉに変更する（ステップＳ６９）。これにより、論理ブロックアドレスＬＢＡｉ，ＬＢＡ（ｉ＋１）に割り当てられる物理ブロックが交換されたことが、アドレス変換テーブル１３２の対応エントリに反映される。
【００６６】
またＣＰＵ１１は、ＰＢＡ（ｉ＋１）に対応する書き込み回数テーブル１３１内エントリに交換済フラグを立てると共に、当該エントリに設定されている書き込み回数を１インクリメントする（ステップＳ７０）。これにより、ＰＢＡ（ｉ＋１）の物理ブロックが、書き込み回数が（Ｍ／Ｄ）・ｎ回となったブロックと交換され、そのＰＢＡ（ｉ＋１）の物理ブロックにデータが書き込まれたことが、書き込み回数テーブル１３１の対応エントリに反映される。またＣＰＵ１１は、ＰＢＡｉに対応する書き込み回数テーブル１３１内エントリに設定されている書き込み回数を１インクリメントする（ステップＳ７１）。これにより、書き込み回数が（Ｍ／Ｄ）・ｎ回となったために、ＰＢＡ（ｉ＋１）の物理ブロックと交換された（本来、データを書き込むべき）ＰＢＡｉの物理ブロックに、当該ＰＢＡ（ｉ＋１）の物理ブロックの元の内容が書き込まれたことが、書き込み回数テーブル１３１の対応エントリに反映される。
【００６７】
次にＣＰＵ１１はワークメモリ１４上のレコードポインタｉを２インクリメントする（ステップＳ７２）。ＣＰＵ１１は、このインクリメント後のレコードポインタｉの指定するレコードｉが書き込み履歴１３３中に存在するならば（ステップＳ６６）、ステップＳ６２の処理に戻る。
【００６８】
一方、レコードｉ中の制御コードが３の場合（ステップＳ６３）、ＣＰＵ１１は当該レコードｉ中の物理ブロックアドレスＰＢＡｉに対応する書き込み回数テーブル１３１内エントリに不良ブロックフラグを立てる（ステップＳ７３）。これにより、ＰＢＡｉの物理ブロックが不良ブロックとしてブロック交替処理の対象となったことが、書き込み回数テーブル１３１の対応エントリに反映される。
【００６９】
次にＣＰＵ１１は、ＰＢＡｉでアドレス変換テーブル１３２を逆引きすることにより、当該ＰＢＡｉに対応する論理ブロックアドレスＬＢＡｉを求める（ステップＳ７４）。続いてＣＰＵ１１は書き込み履歴１３３中の次のレコード（ｉ＋１）を参照する（ステップＳ７５）。もし、レコード（ｉ＋１）中の制御コードが１であるならば、ＣＰＵ１１は、論理ブロックアドレスＬＢＡｉに対応するアドレス変換テーブル１３２内のエントリに設定されている物理ブロックアドレスをレコード（ｉ＋１）中の物理ブロックアドレスＰＢＡ（ｉ＋１）に変更する（ステップＳ７６）。またＣＰＵ１１は、ＰＢＡ（ｉ＋１）に対応する書き込み回数テーブル１３１内エントリに設定されている書き込み回数を１インクリメントする（ステップＳ７７）。これにより、ＬＢＡｉに割り当てられる物理ブロックがＰＢＡ（ｉ＋１）の物理ブロックに交替され、そのＰＢＡ（ｉ＋１）の物理ブロックにデータが書き込まれたことが、アドレス変換テーブル１３２及び書き込み回数テーブル１３１の対応エントリに反映される。
【００７０】
次にＣＰＵ１１はワークメモリ１４上のレコードポインタｉを２インクリメントする（ステップＳ７２）。ＣＰＵ１１は、このインクリメント後のレコードポインタｉの指定するレコードｉが書き込み履歴１３３中に存在するならば（ステップＳ６６）、ステップＳ６２の処理に戻る。なお、図１５のフローチャートでは省略されているが、レコードｉ中の制御コードが３で、次のレコード（ｉ＋１）中の制御コードが２または３の場合には、上記ステップＳ６３で制御コードが２または３であると判定された場合と同様の動作が行われる。但し、制御コードが２または３の上記次のレコード（ｉ＋１）をレコードｉと置き換える必要がある。
【００７１】
ＣＰＵ１１は、上述の処理を書き込み履歴１３３中の全レコードについて繰り返し実行すると（ステップＳ６６）、当該書き込み履歴１３３の内容が全て書き込み回数テーブル１３１及びアドレス変換テーブル１３２に反映されたとして、テーブル更新処理を終了する。
【００７２】
ところで、図１の記憶装置を含むシステムが、無停止で連続的に運転するシステムである場合、当該記憶装置の電源が投入される回数は極めて少ない。この場合、時間の経過と共に書き込み履歴１３３のレコード数が増加する。しかし、フラッシュメモリ１３内に書き込み履歴１３３用に確保できる領域には限りがある。そこで本実施形態では、書き込み履歴１３３のレコード数が予め定められた値に達したときにも、電源投入時と同様の処理（図１４のフローチャートと同様の処理）を行って、書き込み履歴１３３の内容を書き込み回数テーブル１３１及びアドレス変換テーブル１３２に反映して、当該書き込み履歴１３３を消去する。
【００７３】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【００７４】
【発明の効果】
以上詳述したように本発明によれば、物理ブロック単位でのデータの書き込みが可能な不揮発性メモリを記憶装置の記憶媒体と使用した場合に、当該不揮発性メモリの一部分の領域に偏った書き込みを回避して、当該不揮発性メモリへの書き込みを全ブロックに満遍なく平均化でき、これにより当該不揮発性メモリの寿命の最大限化を実現できる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るフラッシュメモリを備えた記憶装置の構成を示すブロック図。
【図２】図１中のフラッシュメモリ１２の論理アドレス空間に割り当てられるユーザ領域１２１と交替領域１２２とを示す図。
【図３】図１中の書き込み回数テーブル１３１のデータ構造例を示す図。
【図４】図１中のアドレス変換テーブル１３２のデータ構造例を示す図。
【図５】図１中の書き込み履歴１３３のデータ構造例を示す図。
【図６】同実施形態におけるフラッシュメモリ１２へのデータ書き込みを説明するためのフローチャート。
【図７】同実施形態におけるブロック交換処理を説明するためのフローチャートの一部を示す図。
【図８】同実施形態におけるブロック交換処理を説明するためのフローチャートの残りを示す図。
【図９】ブロック交換の具体例を説明するための図。
【図１０】ブロック交換の具体例を説明するための図。
【図１１】ブロック交換の具体例と交換済フラグを設ける理由とを説明するための図。
【図１２】ブロック交換の具体例と交換済フラグを設ける理由とを説明するための図。
【図１３】同実施形態におけるブロック交替処理を説明するためのフローチャート。
【図１４】同実施形態における電源投入時処理を説明するためのフローチャート。
【図１５】同実施形態におけるテーブル更新処理を説明するためのフローチャート。
【符号の説明】
１１…ＣＰＵ、１２…フラッシュメモリ（第１の不揮発性メモリ）、１３…フラッシュメモリ（第２の不揮発性メモリ）、１４…ワークメモリ、１５…ＥＣＣ回路、１３１…書き込み回数テーブル（第１の書き込み回数テーブル）、１３２…アドレス変換テーブル（第１のアドレス変換テーブル）、１３３…書き込み履歴、１４１…書き込み回数テーブル（第２の書き込み回数テーブル）、１４２…アドレス変換テーブル（第２のアドレス変換テーブル）。
【図１】
2004326523.tif 000003
【図２】
2004326523.tif 000004
【図３】
2004326523.tif 000005
【図４】
2004326523.tif 000006
【図５】
2004326523.tif 000007
【図６】
2004326523.tif 000008
【図７】
2004326523.tif 000009
【図８】
2004326523.tif 000010
【図９】
2004326523.tif 000011
【図１０】
2004326523.tif 000012
【図１１】
2004326523.tif 000013
【図１２】
2004326523.tif 000014
【図１３】
2004326523.tif 000015
【図１４】
2004326523.tif 000016
【図１５】
2004326523.tif 000017