(57)【要約】【課題】ガーベッジコレクションの実行回数を低減する。【解決手段】記憶制御装置１０は、制御部１１と記憶部１２を含む。記憶部１２は、ソリッドステートドライブが備える記憶領域を有し、ページ単位でデータを記憶可能な記憶領域である。制御部１１は、記憶部１２の容量から複数ページの領域が割り当てられた予備記憶領域を確保し、予備記憶領域に更新データを書き込む。また、制御部１１は、元データが記憶されていたデータ記憶領域のページを無効化し、データの更新回数毎に、異なる予備記憶領域に更新データを書き込む。制御部１１は、データ記憶領域および予備記憶領域の複数ページの領域をブロックに分けてブロック単位で管理する。【選択図】図１
2019212099.tif 000002
【特許請求の範囲】
【請求項１】
半導体記憶メモリの記憶領域であってページ単位でデータを書き込み可能な前記記憶領域を制御対象とする記憶制御装置において、
前記記憶領域のうちデータ記憶領域に記憶されているデータを更新するとき、前記データの更新回数に応じてページ単位で確保された予備記憶領域に、対応する更新回数の更新データを書き込むデータ更新処理を行う制御部、
を有する記憶制御装置。
【請求項２】
前記制御部は、複数ページの領域からなるブロック単位で前記データ記憶領域および前記予備記憶領域を管理する請求項１記載の記憶制御装置。
【請求項３】
前記制御部は、前記データ記憶領域のうちの無効ページの数をカウントし、前記無効ページの数の１ブロック分がＮ個の前記データ記憶領域に跨ることを検出した場合、Ｎ−１個の前記予備記憶領域を確保し、Ｎ個の前記データ記憶領域の有効ページをＮ−１個の前記予備記憶領域にコピーして前記有効ページを無効化する請求項２記載の記憶制御装置。
【請求項４】
前記制御部は、前記データ記憶領域のうち、有効ページの数が最小の第１のデータ記憶領域と、未使用ページを含む第２のデータ記憶領域とを検出した場合、前記有効ページを前記未使用ページにコピーし、前記有効ページを無効化し消去して前記第１のデータ記憶領域を前記予備記憶領域にする請求項１記載の記憶制御装置。
【請求項５】
前記制御部は、前記データ記憶領域および前記予備記憶領域の無効ページをブロック単位で消去した消去カウントを管理し、前記データ記憶領域のうちの最小消去カウントの第１のブロックに記憶される有効ページを、前記予備記憶領域のうちの最大消去カウントの第２のブロックにコピーして前記第１のブロックに記憶されていた前記データを消去し、前記データの消去後の前記第１のブロックを前記予備記憶領域に組み込み、前記データのコピー後の前記第２のブロックを前記データ記憶領域に組み込む請求項２記載の記憶制御装置。
【請求項６】
半導体記憶メモリの記憶領域であってページ単位でデータを書き込み可能な前記記憶領域のうちデータ記憶領域に記憶されているデータを更新するとき、前記データの更新回数に応じてページ単位で確保された予備記憶領域に、対応する更新回数の更新データを書き込むデータ更新処理を行う、
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶制御装置およびプログラムに関する。
【背景技術】
【０００２】
ストレージシステムは、複数の記憶装置を有して、情報処理で扱う大量のデータを記録管理する。近年では、記憶装置として、ＨＤＤ（Hard Disk Drive）よりも高速なＳＳＤ（Solid State Drive）を用いたストレージシステムの採用が広がっている。
【０００３】
ＳＳＤは、不揮発性のフラッシュメモリをベースとする。フラッシュメモリの代表的なものには、ＮＡＮＤ（否定論理積）論理回路を格子状に並べて配置したＮＡＮＤ型フラッシュメモリがある。
【０００４】
ＮＡＮＤ型フラッシュメモリは、磁気ディスクに比べて高速であり、モータ等の駆動部を要しないため故障率が低く、また低消費電力である等の特徴を有している。
一方、ＮＡＮＤ型フラッシュメモリは、磁気ディスクのようなデータの上書き処理を行うことができない。このため、ＮＡＮＤ型フラッシュメモリは、データ更新を行う場合、実際のデータ書き込み量が、書き込みデータのサイズよりも大きくなる可能性がある。このような現象は、ライトアンプリフィケーション（Write Amplification：書き込み増幅）と呼ばれている。
【０００５】
ライトアンプリフィケーションは、チップ素子への書き込みを増加させるので、システムのパフォーマンスの低下やデバイス寿命の短縮化の原因となる。このため、ライトアンプリフィケーションを抑制するための技術が開発されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−１４６２５３号公報
【特許文献２】特開２０１５−００１９０９号公報
【特許文献３】特開２０１２−０５８７７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ライトアンプリフィケーションを抑制するため、ガーベッジコレクション（Garbage Collection）と呼ばれる処理が行われる。ガーベッジコレクションは、実行中のプログラムが使用しなくなったメモリ領域や、プログラム間の隙間のメモリ領域などを集めて、連続して利用可能なメモリ領域（スペアメモリ領域）を確保する処理である。
【０００８】
ＮＡＮＤ型フラッシュメモリにガーベッジコレクションの機能を備えることで、更新データは、ガーベッジコレクションによって生成されたスペアメモリ領域に書き込まれるので、ライトアンプリフィケーションを抑制することができる。
【０００９】
しかし、ガーベッジコレクションの実行回数が多いと、スペアメモリ領域を生成するための書き込み処理が増大して、本来書き込みたいデータ量よりも、フラッシュメモリ上で実際に書き込まれるデータ量が増大してしまう可能性がある。
【００１０】
１つの側面では、本発明は、ガーベッジコレクション処理の実行回数の低減を図った記憶制御装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記課題を解決するために、記憶制御装置が提供される。記憶制御装置は、半導体記憶メモリの記憶領域であってページ単位でデータを書き込み可能な記憶領域を制御対象とし、記憶領域のうちデータ記憶領域に記憶されているデータを更新するとき、データの更新回数に応じてページ単位で確保された予備記憶領域に、対応する更新回数の更新データを書き込むデータ更新処理を行う制御部を有する。
【００１２】
また、上記課題を解決するために、コンピュータに上記記憶制御装置と同様の制御を実行させるプログラムが提供される。
【発明の効果】
【００１３】
１側面によれば、ガーベッジコレクション処理の実行回数を低減することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】記憶制御装置を説明するための図である。
【図２】記憶制御装置を説明するための図である。
【図３】記憶制御装置を説明するための図である。
【図４】記憶制御装置を説明するための図である。
【図５】記憶制御装置を説明するための図である。
【図６】記憶制御装置を説明するための図である。
【図７】記憶制御装置を説明するための図である。
【図８】ＮＡＮＤ型フラッシュメモリの記憶領域の一例を示す図である。
【図９】ブロック単位のデータ更新処理を説明するための図である。
【図１０】ガーベッジコレクション処理を説明するための図である。
【図１１】ＳＳＤのハードウェア構成の一例を示す図である。
【図１２】全体動作のフローチャートの一例を示す図である。
【図１３】アドレス変換テーブルの構成の一例を示す図である。
【図１４】データブロックヘッダテーブルの構成の一例を示す図である。
【図１５】スペアブロックヘッダテーブルの構成の一例を示す図である。
【図１６】ブロックテーブルの構成の一例を示す図である。
【図１７】ガーベッジコレクション処理におけるテーブル相関の一例を示す図である。
【図１８】ウェアレベリング処理におけるテーブル相関の一例を示す図である。
【図１９】スペアブロックを獲得する際の判定動作のフローチャートの一例を示す図である。
【図２０】スペアブロック獲得処理のフローチャートの一例を示す図である。
【図２１】ガーベッジコレクション処理のフローチャートの一例を示す図である。
【図２２】ガーベッジコレクション処理のフローチャートの一例を示す図である。
【図２３】ガーベッジコレクション処理の具体例を説明するための図である。
【図２４】ガーベッジコレクション処理の具体例を説明するための図である。
【図２５】ガーベッジコレクション処理の具体例を説明するための図である。
【図２６】ガーベッジコレクション処理の具体例を説明するための図である。
【図２７】ガーベッジコレクション処理の具体例を説明するための図である。
【図２８】ガーベッジコレクション処理の具体例を説明するための図である。
【図２９】ガーベッジコレクション処理の具体例を説明するための図である。
【図３０】ガーベッジコレクション処理の具体例を説明するための図である。
【図３１】ガーベッジコレクション処理の具体例を説明するための図である。
【図３２】ウェアレベリング処理のフローチャートの一例を示す図である。
【図３３】テーブル相関上でウェアレベリング処理の動作を示す図である。
【図３４】テーブル相関上でウェアレベリング処理の動作を示す図である。
【図３５】テーブル相関上でウェアレベリング処理の動作を示す図である。
【図３６】ページ更新処理のフローチャートの一例を示す図である。
【図３７】ページ更新処理でデータ書き込みを行う際のテーブル処理の一例を示す図である。
【図３８】ページ更新処理による無効フラグの設定およびデータブロックの移動の一例を示す図である。
【図３９】ページ更新処理による無効フラグの設定およびデータブロックの移動の一例を示す図である。
【図４０】更新回数毎の未更新ページ数および更新ページ数のイメージ図である。
【図４１】更新ページ数および更新回数の関係の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本実施の形態について図面を参照して説明する。
図１から図７を用いて記憶制御装置の構成およびガーベッジコレクションの低減化の一例について説明する。図１から図７は記憶制御装置を説明するための図である。記憶制御装置１０は、制御部１１と記憶部１２を含む。
【００１６】
記憶部１２は、ＳＳＤが備える記憶領域を有し、ページ単位でデータを記憶可能な記憶領域である。ページ単位でデータを記憶するデータ記憶領域を有する。
制御部１１は、当該記憶領域を制御対象とする。制御部１１は、記憶領域のうちデータ記憶領域に記憶されているデータを更新するとき、ページ単位で確保した予備記憶領域に更新データを書き込み、データ記憶領域に記憶されている更新前のデータを無効化するデータ更新処理を、データ（ページ）の更新回数毎に異なる予備記憶領域に対して行う。
【００１７】
図１から図７に示す例を用いて動作について説明する。なお、図中のデータブロックＤｂ０はデータ記憶領域に含まれ、スペアブロックＳｐ０は予備記憶領域に含まれる。
〔ステップＳ１（図１）〕記憶部１２は、データブロックＤｂ０を有している。データブロックＤｂ０は１５個のブロック（図中太線枠）を含むとする。また、制御部１１は、記憶部１２の容量から所定割合のスペアブロックＳｐ０を確保する。
【００１８】
スペアブロックＳｐ０は６個のブロックを含むとする（スペアブロックｓ１、・・・、ｓ６とする）。なお、データブロックＤｂ０およびスペアブロックＳｐ０共に、１ブロックを６ページとする。
【００１９】
初期状態（１回目のデータ更新）において、データブロックＤｂ０の全ページは有効ページ（使用中（参照中）ページ）であり、スペアブロックＳｐ０の全ページは未使用ページであるとする。
【００２０】
〔ステップＳ２ａ（図２）〕制御部１１は、データブロックＤｂ０に記憶されている１回目の更新データ［１］を、スペアブロックｓ１、ｓ２、ｓ３に書き込む。
〔ステップＳ２ｂ（図２）〕制御部１１は、データブロックＤｂ０において、更新データ［１］が記憶されていたページを無効化する。
【００２１】
〔ステップＳ３（図３）〕制御部１１は、データブロックＤｂ０において、ガーベッジコレクション処理を行って、データブロックＤｂ０の無効ページを消去し（無効ページに記憶されているデータを消去し）、有効ページと未使用ページとをそれぞれ集約する。
【００２２】
〔ステップＳ４ａ（図４）〕制御部１１は、スペアブロックｓ１、ｓ２、ｓ３に記憶されている２回目の更新データ［２］をスペアブロックｓ４に書き込む。
〔ステップＳ４ｂ（図４）〕制御部１１は、スペアブロックｓ１、ｓ２、ｓ３において、更新データ［２］が記憶されていたページを無効化する。
【００２３】
〔ステップＳ５（図５）〕制御部１１は、スペアブロックＳｐ０において、ガーベッジコレクション処理を行って、スペアブロックｓ３の無効ページを消去し、有効ページと未使用ページとをそれぞれ集約する。
【００２４】
〔ステップＳ６ａ（図６）〕制御部１１は、スペアブロックｓ４に記憶されている３回目の更新データ［３］をスペアブロックｓ５に書き込む。
〔ステップＳ６ｂ（図６）〕制御部１１は、スペアブロックｓ４において、更新データ［３］が記憶されていたページを無効化する。
【００２５】
〔ステップＳ７（図７）〕制御部１１は、スペアブロックＳｐ０において、ガーベッジコレクション処理を行って、スペアブロックｓ４の無効ページを消去し、有効ページと未使用ページとをそれぞれ集約する。
【００２６】
このように、記憶制御装置１０は、予備記憶領域に更新データを書き込んで、元データが記憶されていた記憶領域のページを無効化し、データ更新回数   毎に、異なる予備記憶領域に更新データを書き込む。
【００２７】
これにより、記憶制御装置１０は、データ（ページ）の更新回数が多くなるにつれ、無効ページは同じブロックに集まるようになるため、ガーベッジコレクション処理の実行回数を低減することが可能になる。したがって、ガーベッジコレクション処理の実行回数が低減するので、ライトアンプリフィケーションの抑制が可能になる。
【００２８】
次に記憶部１２をＮＡＮＤ型フラッシュメモリに適用した実施の形態について説明する（記憶制御装置１０は例えば、パソコンやサーバ内のＳＳＤに適用される）。最初に、ＮＡＮＤ型フラッシュメモリの記憶領域の構成、書き込み動作および課題について、図８から図１０を用いて説明する。
【００２９】
図８はＮＡＮＤ型フラッシュメモリの記憶領域の一例を示す図である。ＮＡＮＤ型フラッシュメモリの記憶領域は、セル（cell）、ページおよびブロックと呼ばれる単位で分けられている。セルは、データを格納する最小単位の記憶領域である。ページは、複数のセルを有する記憶領域である。ブロックは、複数のページを有する記憶領域である。
【００３０】
上記のような単位の記憶領域を有するＮＡＮＤ型フラッシュメモリは、書き込み処理および読み出し処理はページ単位で行われる。ただし、書き込みに関しては、ページが未使用状態であれば、データをそのまま書き込めるが、ページが使用済みである場合、ＨＤＤのように上書き処理を行うことができない。すなわち、ＨＤＤのような上書きによるデータ更新処理を行うことができない。
【００３１】
このため、ＮＡＮＤ型フラッシュメモリでは、セルが存在するページを含むブロック全体を読み出しておいてから、そのブロックを消去し（消去はブロック単位で行われる）、消去が行われたブロックに対して、書き換えたブロックのデータを書き込むという処理が行われる。
【００３２】
＜ブロック単位のデータ更新およびライトアンプリフィケーション＞
図９はブロック単位のデータ更新処理を説明するための図である。ブロックＢ０は、３０セルを有し、６ページ（ページＰ０、・・・、Ｐ５）で形成されている。このブロックＢ０に対し、ページＰ２が使用済みであって、該ページＰ２にデータが書き込まれるとする。
【００３３】
〔ステップＳ１１〕ＮＡＮＤ型フラッシュメモリのブロックＢ０内のデータ（全データ）がキャッシュメモリ（例えば、ＤＲＡＭ（Dynamic Random Access Memory））上にコピーされる。
【００３４】
〔ステップＳ１２〕ＤＲＡＭ上で、ページＰ２に新規データが書き込まれたブロックＢ０ａが生成される。
〔ステップＳ１３〕ＮＡＮＤ型フラッシュメモリ上で、ブロックＢ０内のデータが消去される。
【００３５】
〔ステップＳ１４〕新規データが書き込まれているブロックＢ０ａが、データが消去されたブロックＢ０に書き込まれることにより、ＮＡＮＤ型フラッシュメモリ上で新規データが書き込まれたブロックＢ０−１が生成される。
【００３６】
このように、ＮＡＮＤ型フラッシュメモリは上書き処理ができないため、別の領域（図９の例ではＤＲＡＭ）にブロック内のデータを一旦退避させ、退避させたブロックに新規データが書き込まれる。そして、ＮＡＮＤ型フラッシュメモリ上で消去が実行されたブロックに対し、新規データが書き込まれたブロックを書き込む処理が実行される。
【００３７】
ＮＡＮＤ型フラッシュメモリでは、データ更新を行う場合、このような処理が行われるので、例えば、１ビットのデータを変更するにも、そのデータを含むブロック全体を削除して、１ブロック分のデータの書き込み直しを行うことになる。
【００３８】
したがって、ブロック単位での書き込みになるため、本来書き込みたいデータ量より実際に書き込まれるデータ量が増幅するライトアンプリフィケーションが生じる。
なお、ライトアンプリフィケーションの度合いを示す係数は、例えば、（ＮＡＮＤ型フラッシュメモリへの書き込みデータ量）／（ホストが要求する書き込みデータ量）で表される（１であれば書き込み増幅なし）。係数の値が大きくなると書き込み性能が劣化し、書き込み回数の上限（寿命）に達しやすくなる。
【００３９】
＜ガーベッジコレクション処理＞
ライトアンプリフィケーションを改善するため、ガーベッジコレクション処理が行われる。ガーベッジコレクション処理は、ブロックの中の有効ページと無効ページを整理し、ブロック内の全ページを無効状態にした上で消去処理を実行して、未使用なページからなるスペアブロックを生成する。
【００４０】
図１０はガーベッジコレクション処理を説明するための図である。ブロックＢ１は、ページＰ０、・・・、Ｐ５を有し、ページＰ０、Ｐ３、Ｐ５を無効ページ、ページＰ１、Ｐ２、Ｐ４を有効ページとする。
【００４１】
また、ブロックＢ２は、ページＰ０、・・・、Ｐ５を有し、ページＰ０、Ｐ１、Ｐ３、Ｐ４を未使用ページ、ページＰ２、Ｐ５を有効ページとする。
ブロックＢ１、Ｂ２に対し、ブロックＢ１のページＰ１、Ｐ２、Ｐ４をブロックＢ２へ移行してページの集約を行い、有効ページが移行された後のブロックＢ１の全データを消去する。これにより、未使用なページからなるスペアブロックＢ１ａが生成される。
【００４２】
このようなガーベッジコレクション処理を行ってスペアブロックを生成することにより、更新データは、スペアブロックに書き込まれるので、ライトアンプリフィケーションを抑制することができる。
【００４３】
しかし、ガーベッジコレクション処理の実行回数が増加すると、スペアブロックを生成するための書き込み処理が増大するので、ガーベッジコレクション処理を行っても、結果的にライトアンプリフィケーションの抑制につながらない可能性がある。
【００４４】
本発明はこのような点に鑑みてなされたものであり、ガーベッジコレクション処理の実行回数を低減して、ライトアンプリフィケーションの抑制を図るものである。
＜ハードウェア構成＞
図１１はＳＳＤのハードウェア構成の一例を示す図である。ＳＳＤ１０ａは、図１の記憶制御装置１０の機能を有する。ＳＳＤ１０ａはプロセッサ１００によって装置全体が制御されている。プロセッサ１００には、バス１０３を介して複数の周辺機器が接続されている。
【００４５】
プロセッサ１００は、マルチプロセッサであってもよい。プロセッサ１００は、例えば、ＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＰＬＤ（Programmable Logic Device）である。またプロセッサ１００は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００４６】
メモリ１０１は、ＳＳＤ１０ａの主記憶装置として使用される。メモリ１０１には、プロセッサ１００に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０１には、プロセッサ１００による処理に要する各種メッセージが格納される。
【００４７】
また、メモリ１０１は、ＳＳＤ１０ａの補助記憶装置としても使用され、ＯＳのプログラム、アプリケーションプログラム、各種メッセージおよびテーブル情報が格納される。
テーブル情報は、フラッシュメモリ１０５から読み出され、メモリ１０１に保持され、メモリ１０１上で更新され、フラッシュメモリ１０５上にバックアップされる。さらに、メモリ１０１は、フラッシュメモリ１０５から読み出したデータ、またはフラッシュメモリ１０５に書き込むデータを、一時的に保持する。
【００４８】
バス１０３に接続されている周辺機器としては、ネットワークインタフェース１０２およびフラッシュメモリインタフェース１０４がある。
ネットワークインタフェース１０２は、ホスト２０とのインタフェース制御を行い、ホスト２０との間で行われるデータ、アドレス情報、ステータス情報、外部コマンド（ホスト２０が処理の実行を指示するためのコマンド）等の送受信を制御する。
【００４９】
ネットワークインタフェース１０２は、ホスト２０から供給されるデータ等を取り込み、データ等をホスト２０に供給する。また、ネットワークインタフェース１０２は例えば、ＮＩＣ（Network Interface Card）、無線ＬＡＮ（Local Area Network）カード等の機能を有してもよい。ネットワークインタフェース１０２で受信されたデータ等はプロセッサ１００に出力される。
【００５０】
フラッシュメモリインタフェース１０４は、フラッシュメモリ１０５とのインタフェース制御を行い、フラッシュメモリ１０５との間で行われるデータ、アドレス情報、ステータス情報、内部コマンド等の送受信を制御する。
【００５１】
以上のようなハードウェア構成によって、ＳＳＤ１０ａの処理機能を実現することができる。例えば、ＳＳＤ１０ａは、プロセッサ１００が読み取り可能な記録媒体に記録されたプログラムを実行することで、本発明の制御を行うことができる。
【００５２】
ＳＳＤ１０ａに実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、ＳＳＤ１０ａに実行させるプログラムを補助記憶装置に格納しておくことができる。
【００５３】
プロセッサ１００は、補助記憶装置内のプログラムの少なくとも一部を主記憶装置にロードし、プログラムを実行する。また、光ディスク、メモリ装置、メモリカード等の可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えば、プロセッサ１００からの制御により、補助記憶装置にインストールされた後、実行可能となる。またプロセッサ１００が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００５４】
なお、図１に示した制御部１１は、プロセッサ１００、ネットワークインタフェース１０２およびフラッシュメモリインタフェース１０４で実現され、図１に示した記憶部１２は、メモリ１０１およびフラッシュメモリ１０５で実現される。
【００５５】
＜全体動作フロー＞
図１２は全体動作のフローチャートの一例を示す図である。
〔ステップＳ２１〕制御部１１は、ページ更新要求をホスト２０から受信する。
【００５６】
〔ステップＳ２２〕制御部１１は、スペアブロックの獲得が要か否かを判定する。スペアブロック獲得が要の場合はステップＳ２３へ処理が進み、不要の場合はステップＳ２８へ処理が進む。
【００５７】
〔ステップＳ２３〕制御部１１は、スペアブロックの獲得処理を行う。
〔ステップＳ２４〕制御部１１は、スペアブロックの残りが閾値を超えたか否かを判定する。閾値を超えた場合（スペアブロックの残りが少なくなった場合）はステップＳ２５へ処理が進み、閾値を超えない場合はステップＳ２８へ処理が進む。
【００５８】
〔ステップＳ２５〕制御部１１は、ガーベッジコレクション処理を実行する。
〔ステップＳ２６〕制御部１１は、ウェアレベリング（wear leveling）処理が要か否かを判定する。ウェアレベリング処理が要の場合はステップＳ２７へ処理が進み、不要の場合はステップＳ２８へ処理が進む。
【００５９】
なお、ウェアレベリングとはフラッシュメモリの書き換え回数の平準化を行う処理である。通常、フラッシュメモリにおいてデータの書き換えおよび消去を繰り返すとセルが劣化する。このため、ウェアレベリングを行うことで、特定のブロックのみにデータの書き込み、消去が集中するといったムラをなくしてセル劣化を回避する。
【００６０】
〔ステップＳ２７〕制御部１１は、ウェアレベリング処理を実行する。
〔ステップＳ２８〕制御部１１は、ページ更新処理を実行する。
＜テーブルの仕様＞
制御部１１は、データブロックおよびスペアブロックの複数ページの領域をブロック単位のテーブルで管理する。制御部１１は、記憶部１２に各種テーブルを生成して、上記のガーベッジコレクション処理およびウェアレベリング処理を行う。
【００６１】
制御部１１が生成するテーブルには、アドレス変換テーブル、データブロックヘッダテーブル、スペアブロックヘッダテーブルおよびブロックテーブルがある。以下、各テーブルについて説明する。
【００６２】
図１３はアドレス変換テーブルの構成の一例を示す図である。アドレス変換テーブル２は、データブロックヘッダアドレス、スペアブロックヘッダアドレス、最大ページ更新カウントおよび消去カウントデータブロックアドレスを有する。さらに、アドレス変換テーブル２は、ページの論理アドレス、ページの物理アドレスおよびページ更新カウントを有する。
【００６３】
データブロックヘッダアドレスは、先頭／最後のデータブロックヘッダテーブルのアドレスを示す。スペアブロックヘッダアドレスは、スペアブロックヘッダテーブルのアドレスを示す。
【００６４】
最大ページ更新カウントは、ページ更新カウントのうちで最大の更新カウントを示す。消去カウントデータブロックアドレスは、消去カウントの少ない順にデータブロックを並べた場合の先頭／最後のデータブロックアドレスを示す。
【００６５】
ページの論理アドレスは、各ページの論理アドレスが小さい順に格納される。ページの物理アドレスは、ページの論理アドレスに対応する物理アドレスである。ページの更新カウントは、ページの論理アドレスに対応する更新カウントを示す。
【００６６】
図１４はデータブロックヘッダテーブルの構成の一例を示す図である。データブロックヘッダテーブル３は、次のヘッダアドレス、ページ更新カウント、保有ブロック数、先頭のブロックアドレス、有効ページ総計、無効ページ総計、未使用ページ総計、未使用ページ先頭アドレスおよび前のヘッダアドレスを有する。
【００６７】
次のヘッダアドレスは、ページ更新カウントが次に大きいデータブロックヘッダテーブルのアドレスを示す（最大の場合は０とする）。ページ更新カウントは、データブロックヘッダテーブル毎に存在する各ページ更新カウントの値を示す。
【００６８】
保有ブロック数は、ページ更新カウント毎に獲得されたブロック数を示す。先頭のブロックアドレスは、ページ更新カウント毎に獲得されたブロックは互いにリンクされており、その先頭アドレスを示す。
【００６９】
有効ページ総計は、ページ更新カウント毎に獲得されたブロックのうちの有効ページの総計を示す。無効ページ総計は、ページ更新カウント毎に獲得されたブロックのうちの無効ページの総計を示す。
【００７０】
未使用ページ総計は、ページ更新カウント毎に獲得されたブロックのうちの未使用ページの総計を示す。未使用ページ先頭アドレスは、未使用ページのうちの先頭アドレスを示す。前のヘッダアドレスは、ページ更新カウントが次に小さいデータブロックヘッダテーブルのアドレスを示す（最小の場合は０とする）。
【００７１】
図１５はスペアブロックヘッダテーブルの構成の一例を示す図である。スペアブロックヘッダテーブル４は、保有ブロック数、先頭のブロックアドレス、最後のブロックアドレスおよび最大消去カウントを有する。
【００７２】
保有ブロック数は、現時点のスペアブロック総数を示す。先頭のブロックアドレスは、互いにリンクされているスペアブロックの先頭アドレスを示す。最後のブロックアドレスは、互いにリンクされているスペアブロックの最後アドレスを示す。最大消去カウントは、スペアブロックのうちの最大消去カウントを示す。
【００７３】
図１６はブロックテーブルの構成の一例を示す図である。ブロックテーブル５は、次のブロックアドレス（データブロック）、次のブロックアドレス（消去カウント）、ブロックの物理アドレスおよびＤＡＴＡ／ＳＰＡＲＥ識別を有する。
【００７４】
さらに、ブロックテーブル５は、消去カウント、有効ページ数、無効ページ数、未使用ページ数、未使用ページ先頭アドレス、フラグ／論理ページアドレス、前のブロックアドレス（データブロック）および前のブロックアドレス（消去カウント）を有する。
【００７５】
次のブロックアドレス（データブロック）は、データブロックの場合、同じ更新カウントで次に無効ページが少ないブロックのアドレスを示す（最後の場合は０とし、スペアブロックの場合は参照なし）。次のブロックアドレス（消去カウント）は、次に消去カウントが多いブロックのアドレスを示す（最後の場合は０とする）。
【００７６】
ブロックの物理アドレスは、当該ブロックの物理アドレスを示す。ＤＡＴＡ／ＳＰＡＲＥ識別は、当該ブロックテーブルは、データブロックおよびスペアブロック共通で使用されるため、その識別を示す。
【００７７】
消去カウントは、当該ブロックを消去した数の累計を示す。有効ページ数は、当該ブロックの有効ページ数を示し、スペアブロックの場合は参照されない。無効ページ数は、当該ブロックの無効ページ数を示し、スペアブロックの場合は参照されない。
【００７８】
未使用ページ数は、当該ブロックの未使用ページ数を示し、スペアブロックの場合は参照されない。未使用ページ先頭アドレスは、当該ブロックの未使用ページ先頭アドレスを示し、スペアブロックの場合は参照されない。
【００７９】
フラグ／論理ページアドレスは、データブロック内の全ページの有効／無効／未使用状態をページの先頭から表現するフラグを示す。有効ページの場合は論理ページアドレスが記述される。スペアブロックの場合は参照されない。
【００８０】
前のブロックアドレス（データブロック）は、データブロックの場合、同じ更新カウントで次に無効ページが多いブロックのアドレスを示す（先頭の場合は０とする）。前のブロックアドレス（消去カウント）は、次に消去カウントが少ないブロックのアドレスを示す（先頭の場合は０とする）。
【００８１】
＜テーブル相関＞
上記で説明した各種テーブルは互いにリンク付けられる。図１７、図１８を用いてテーブル相関について説明する。図１７はガーベッジコレクション処理におけるテーブル相関の一例を示す図である。ガーベッジコレクション処理で使用される場合の各テーブルの相関関係を示している。
【００８２】
データブロックヘッダテーブル３−１、・・・、３−４は互いにリンクしている。矢印ａ１は、更新カウントが小から大への方向を示し、矢印ａ２は、更新カウントが大から小への方向を示す。アドレス変換テーブル２は、先頭のデータブロックヘッダテーブル３−１、最後のデータブロックヘッダテーブル３−４、およびスペアブロックヘッダテーブル４にリンクしている。
【００８３】
また、同じ更新カウントのデータブロックヘッダテーブルに対して、ブロックテーブルがリンクする。図１７の例では、同じ更新カウントのデータブロックヘッダテーブル３−１に対し、ブロックテーブル５ｄ１、５ｄ２、５ｄ３、５ｄ４がリンクし、同じ更新カウントのデータブロックヘッダテーブル３−２に対し、ブロックテーブル５ｄ５、５ｄ６、５ｄ７がリンクしている。
【００８４】
また、同じ更新カウントのデータブロックヘッダテーブル３−３に対し、ブロックテーブル５ｄ８、５ｄ９がリンクし、同じ更新カウントのデータブロックヘッダテーブル３−４に対し、ブロックテーブル５ｄ１０がリンクしている。矢印ａ３は無効ページ数が多から少への方向を示す。
【００８５】
一方、スペアブロックヘッダテーブル４に対して、ブロックテーブル５ｓ１、・・・、５ｓ４が互いにリンクしている。矢印ａ４は、消去カウントが小から大への方向を示す。
なお以降では、図１７に示す同じ更新カウントのブロックテーブルのリンクをデータブロックプール、スペアブロックのリンクをスペアブロックプールと呼ぶ場合がある。
【００８６】
図１８はウェアレベリング処理におけるテーブル相関の一例を示す図である。ウェアレベリング処理で使用される場合の各テーブルの相関関係を示している。アドレス変換テーブル２は、ブロックテーブル５ｄ１、５ｄ１０およびスペアブロックヘッダテーブル４にリンクしている。また、ブロックテーブル５ｄ１、・・・・、５ｄ１０がシリアルにリンクしている。
【００８７】
一方、スペアブロックヘッダテーブル４に対して、ブロックテーブル５ｓ１、・・・、５ｓ４が互いにリンクしている。矢印ｂ１は、消去カウントが小から大への方向を示す。なお、以降では、図１８に示すブロックテーブル５ｄ１、・・・・、５ｄ１０のリンクを消去カウントプールと呼ぶ場合がある。
【００８８】
＜スペアブロック獲得に関する動作フロー＞
次に図１９、図２０を用いて、スペアブロック獲得に関する動作フローについて説明する。図１９はスペアブロックを獲得する際の判定動作のフローチャートの一例を示す図である。図１２に示したステップＳ２２の詳細フローを示している。
【００８９】
〔ステップＳ２２ａ〕制御部１１は、論理アドレスのページ更新カウントをインクリメント（＋１）する。
〔ステップＳ２２ｂ〕制御部１１は、更新カウントが最大ページ更新カウントを超えたか否かを判定する。更新カウントが最大ページ更新カウントを超えた場合はステップＳ２２ｃへ処理が進み、超えない場合はステップＳ２２ｄへ処理が進む。
【００９０】
〔ステップＳ２２ｃ〕制御部１１は、最大ページ更新カウントをインクリメントし、最大カウント用のデータブロックヘッダを作成する。ステップＳ２３へ処理が進む。
〔ステップＳ２２ｄ〕制御部１１は、未使用ページ総計が０か否かを判定する。０の場合はステップＳ２３へ処理が進み、０でない場合は終了する。
【００９１】
〔ステップＳ２３〕制御部１１は、図１２に示したスペアブロックの獲得処理（Ｓ２３）を行う。
図２０はスペアブロック獲得処理のフローチャートの一例を示す図である。図１２に示したステップＳ２３の詳細フローを示している。
【００９２】
〔ステップＳ２３ａ〕制御部１１は、スペアブロックヘッダからスペアブロックプールの最初のブロックを獲得し、スペアブロックのリンクから外し、ヘッダテーブルの保有ブロック数をデクリメントする（−１）する。
【００９３】
〔ステップＳ２３ｂ〕制御部１１は、獲得したブロックを同じ更新カウントのブロックプールの最後に加え、同じ更新カウントのヘッダテーブルを修正する。
〔ステップＳ２３ｃ〕制御部１１は、獲得したブロックの消去カウントと消去カウントプールの最後の消去カウントとを比較する。
【００９４】
〔ステップＳ２３ｄ〕制御部１１は、比較にもとづいて、獲得したブロックの消去カウントの方が小さいか否かを判定する。獲得したブロックの消去カウントの方が小さい場合、ステップＳ２３ｅへ処理が進み、小さくない場合はステップＳ２３ｆへ処理が進む。
【００９５】
〔ステップＳ２３ｅ〕制御部１１は、次に消去カウントが小さい消去カウントプールのデータブロックと比較する。ステップＳ２３ｄへ処理が戻る。
〔ステップＳ２３ｆ〕制御部１１は、獲得したブロックを消去カウントプールの消去カウントがより小さいデータブロックの後にリンクする。
【００９６】
〔ステップＳ２３ｇ〕制御部１１は、獲得したデータブロックの内容を更新する（スペアブロックの獲得の具体例は上述の図１から図７の動作の流れを参照）。
＜ガーベッジコレクション処理の動作フロー＞
図２１、図２２はガーベッジコレクション処理のフローチャートの一例を示す図である。図１２に示したステップＳ２５の詳細フローを示している。
【００９７】
〔ステップＳ２５ａ〕制御部１１は、データブロックヘッダの無効ページ総計が１ブロック以上あるか否かを判定する。１ブロック以上ある場合はステップＳ２５ｃへ処理が進み、１ブロック以上ない場合はステップＳ２５ｂへ処理が進む。
【００９８】
〔ステップＳ２５ｂ〕制御部１１は、次にページ更新カウントの小さいデータブロックヘッダがあるか否かを判定する。ある場合はステップＳ２５ａへ処理が戻り、ない場合はステップＳ２５ｊへ処理が進む。
【００９９】
〔ステップＳ２５ｃ〕制御部１１は、ブロックテーブルリンク先頭から無効ページをカウントし、１ブロック分がＮ個のデータブロックに跨るかを調べる。
〔ステップＳ２５ｄ〕制御部１１は、Ｎ−１個のスペアブロックを獲得し、Ｎ個のデータブロックの有効ページをスペアブロックにコピーし、Ｎ個のデータブロックを消去し、それぞれの消去カウントをインクリメントする。
【０１００】
〔ステップＳ２５ｅ〕制御部１１は、各ページの新たな物理アドレスをアドレス変換テーブル２の対応する論理アドレスに反映する。
〔ステップＳ２５ｆ〕制御部１１は、獲得したスペアブロックをデータブロックプールの最後に組み込む。
【０１０１】
〔ステップＳ２５ｇ〕制御部１１は、消去したデータブロックの消去カウントがスペアブロックプールの消去カウントより小さいか否かを判定する。小さい場合はステップＳ２５ｈへ処理が進み、小さくない場合はステップＳ２５ｉへ処理が進む。
【０１０２】
〔ステップＳ２５ｈ〕制御部１１は、比較するスペアブロックを１つ前に移動する。ステップＳ２５ｇへ処理が戻る。
〔ステップＳ２５ｉ〕制御部１１は、消去したデータブロックをスペアブロックプールの消去カウントがより小さいスペアブロックの後にリンクする。
【０１０３】
〔ステップＳ２５ｊ〕制御部１１は、未使用ページ総計が、データブロックヘッダの最小有効ページブロック（＝（１ブロックのページ）−（最大無効ページ数））以上であるか否かを判定する。未使用ページ総計がデータブロックヘッダの最小有効ページブロック以上の場合、ステップＳ２５ｍへ処理が進み、そうでない場合はステップＳ２５ｋに処理が進む。
【０１０４】
〔ステップＳ２５ｋ〕制御部１１は、次にページ更新カウントの大きいデータブロックヘッダがあるか否かを判定する。ある場合はステップＳ２５ｊに戻り、ない場合は終了する。
【０１０５】
〔ステップＳ２５ｍ〕制御部１１は、有効ページが最小のブロックから有効ページを未使用ページがあるブロックにコピーする。
〔ステップＳ２５ｎ〕制御部１１は、各ページの新たな物理アドレスをアドレス変換テーブル２の対応する論理アドレスに反映する。
【０１０６】
〔ステップＳ２５ｏ〕制御部１１は、コピー元のデータブロックを消去、消去カウントをインクリメントし、データブロックプールから削除する。
〔ステップＳ２５ｐ〕制御部１１は、消去したデータブロックの消去カウントがスペアブロックプールの消去カウントより小さいか否かを判定する。小さい場合はステップＳ２５ｑへ処理が進み、小さくない場合はステップＳ２５ｒへ処理が進む。
【０１０７】
〔ステップＳ２５ｑ〕制御部１１は、比較するスペアブロックを１つ前に移動する。ステップＳ２５ｐへ処理が戻る。
〔ステップＳ２５ｒ〕制御部１１は、消去したデータブロックをスペアブロックプールの消去カウントがより小さいスペアブロックの後にリンクする。
【０１０８】
＜ガーベッジコレクション処理の具体例＞
次に図２３から図３１を用いてガーベッジコレクション処理の具体例について説明する。図２３から図２７はガーベッジコレクション処理の具体例を説明するための図である。図２１に示した動作フローの具体例を示している。
【０１０９】
まず、ガーベッジコレクション処理では、無効ページ総計が１ブロック以上のデータブロックヘッダを、更新カウントが大きい順に探索する（図１７の矢印ａ２の方向）。なお、１ブロック＝６ページとする。
【０１１０】
〔状態Ｓｔ１１（図２３）〕更新前の４つのデータブロックの状態を示すブロックテーブルｄ１、・・・、ｄ４がリンクしている。各データブロックの物理アドレスをＡ１、Ａ２、Ａ３、Ａ４とする。
【０１１１】
ブロックテーブルｄ１において、次のブロックアドレスはＡ２、当該データブロックの物理アドレスはＡ１であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＤＡＴＡである。また、当該データブロックのページＰ０、Ｐ３、Ｐ４、Ｐ５は無効ページ、ページＰ１、Ｐ２は有効ページである。さらに、前のブロックアドレスは、当該データブロックは先頭なので０が設定される。
【０１１２】
ブロックテーブルｄ２において、次のブロックアドレスはＡ３、当該データブロックの物理アドレスはＡ２であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＤＡＴＡである。また、当該データブロックのページＰ０、Ｐ１、Ｐ２、Ｐ３は無効ページ、ページＰ４、Ｐ５は有効ページである。さらに、前のブロックアドレスはＡ１である。
【０１１３】
ブロックテーブルｄ３において、次のブロックアドレスはＡ４、当該データブロックの物理アドレスはＡ３であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＤＡＴＡである。また、当該データブロックのページＰ０、Ｐ３は無効ページ、ページＰ１、Ｐ２、Ｐ４、Ｐ５は有効ページである。さらに、前のブロックアドレスはＡ２である。
【０１１４】
ブロックテーブルｄ４において、次のブロックアドレスは、当該データブロックは最後なので０が設定され、当該データブロックの物理アドレスはＡ４であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＤＡＴＡである。また、当該データブロックのページＰ３は無効ページ、ページＰ０、Ｐ１は未使用ページ、ページＰ２、Ｐ４、Ｐ５は有効ページである。さらに、前のブロックアドレスはＡ３である。
【０１１５】
ここで、制御部１１は、ブロックテーブルリンクの先頭から無効ページをカウントし、無効ページ１ブロック分が２個のデータブロックに跨っていることを検出する（図２１のステップＳ２５ｃ）。
【０１１６】
〔状態Ｓｔ１２（図２４）〕制御部１１は、スペアブロックを１個確保し、２個のデータブロックの有効ページをスペアブロックにコピーする（図２１のステップＳ２５ｄ）。確保したスペアブロックの物理アドレスをＡ５とする。
【０１１７】
ブロックテーブルｓｂ１は、確保したスペアブロックの状態を示している。ブロックテーブルｓｂ１において、次のブロックアドレスは空欄であり、当該スペアブロックの物理アドレスはＡ５であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＳＰＡＲＥである。
【０１１８】
また、当該スペアブロックのページＰ０、Ｐ１は未使用であり、ページＰ２、Ｐ３、Ｐ４、Ｐ５にデータブロックの有効ページがコピーされている（テーブル管理上では、有効ページの論理ページアドレスがコピーされることになる）。前のブロックアドレスは空欄になる。
【０１１９】
〔状態Ｓｔ１３（図２５）〕制御部１１は、アドレス変換テーブル２上で、スペアブロックにコピーした有効ページの論理アドレスに対応させて、該有効ページの新たな物理アドレスを反映（更新）する（図２１のステップＳ２５ｅ）。
【０１２０】
〔状態Ｓｔ１４（図２６）〕制御部１１は、有効ページをコピーしたスペアブロックをデータブロックプールの最後に組み込む（図２１のステップＳ２５ｆ）。なお、テーブル管理上では、スペアブロックのブロックテーブルｓｂ１がデータブロックのブロックテーブルの最後に組み込まれてリンクし、新たなデータブロックプールができる。
【０１２１】
図２３に示したブロックテーブルｄ３は、データブロックプール内の先頭にきてブロックテーブルｄ３−１となる。ブロックテーブルｄ３−１では、前のブロックアドレスは０になる。
【０１２２】
また、図２３に示したブロックテーブルｄ４は、ブロックテーブルｄ３−１にリンクしてブロックテーブルｄ４−１になる。ブロックテーブルｄ４−１では、次のブロックアドレスはＡ５、前のブロックアドレスはＡ３になる。
【０１２３】
さらに、ブロックテーブルｄ４−１の最後に、スペアブロックのブロックテーブルｓｂ１にもとづくブロックテーブルｄ５が組み込まれる。ブロックテーブルｄ５において、当該データブロックの物理アドレスはＡ５であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＤＡＴＡである。また、当該データブロックのページＰ０、Ｐ１は未使用、ページＰ２、Ｐ３、Ｐ４、Ｐ５は有効ページである。さらに、前のブロックアドレスはＡ４である。
【０１２４】
〔状態Ｓｔ１５（図２７）〕制御部１１は、コピー元のデータブロックを消去し、消去カウントに１を加えたスペアブロックを、スペアブロックプールの消去カウントがより小さいスペアブロックの後にリンクする（図２１のステップＳ２５ｇ、Ｓ２５ｈ、Ｓ２５ｉ）。
【０１２５】
ブロックテーブルｓｂ２は、スペアブロック（元はブロックテーブルｄ１のデータブロック）の状態を示している。ブロックテーブルｓｂ２において、次のブロックアドレスはＡ２であり、当該スペアブロックの物理アドレスはＡ１であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＳＰＡＲＥである。また、消去カウントはインクリメントされ（＋１）、ページＰ０、・・・、Ｐ５は未使用である。前のブロックアドレスは空欄になる。
【０１２６】
ブロックテーブルｓｂ３は、スペアブロック（元はブロックテーブルｄ２のデータブロック）の状態を示している。ブロックテーブルｓｂ３において、次のブロックアドレスは最後なので０であり、当該スペアブロックの物理アドレスはＡ２であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＳＰＡＲＥである。また、消去カウントはインクリメントされ、ページＰ０、・・・、Ｐ５は未使用である。前のブロックアドレスはＡ１になる。
【０１２７】
図２８から図３１はガーベッジコレクション処理の具体例を説明するための図である。図２２に示した動作フローの具体例を示している。
〔状態Ｓｔ２１（図２８）〕更新前の４つのデータブロックの状態を示すブロックテーブルｄ１、・・・、ｄ４がリンクしている（図２３の状態Ｓｔ１１と同じ）。制御部１１は、有効ページが最小のブロックから、有効ページを未使用ページがあるブロックにコピーする（図２２のステップＳ２５ｍ）。
【０１２８】
〔状態Ｓｔ２２（図２９）〕制御部１１は、未使用ページがあるブロックにコピーした有効ページに対し、アドレス変換テーブル２上で、該有効ページの論理アドレスに対応する新たな物理アドレスを反映（更新）する（図２２のステップＳ２５ｎ）。
【０１２９】
〔状態Ｓｔ２３（図３０）〕制御部１１は、コピー元のデータブロックを削除し、該データブロックのブロックテーブルをデータブロックプールから削除する（図２２のステップＳ２５ｏ）。ブロックテーブルｄ１が削除されたので、ブロックテーブルｄ２−２、ｄ３、ｄ４−２がリンク付けられる。
【０１３０】
ブロックテーブルｄ２−２は、前のブロックアドレスは０になる。ブロックテーブルｄ４−２は、ページＰ０、Ｐ１に有効ページがコピーされている。
〔状態Ｓｔ２４（図３１）〕制御部１１は、コピー元のデータブロックを消去し、消去カウントに１を加えたスペアブロックを、スペアブロックプールの消去カウントがより小さいスペアブロックの後にリンクする（図２２のステップＳ２５ｐ、Ｓ２５ｑ、Ｓ２５ｒ）。当該スペアブロックのブロックテーブルｓｂ５がリンク付けされている。
【０１３１】
ブロックテーブルｓｂ５は、スペアブロック（元はブロックテーブルｄ１のデータブロック）の状態を示している。ブロックテーブルｓｂ５において、次のブロックアドレスは最後なので０であり、当該スペアブロックの物理アドレスはＡ１であり、ＤＡＴＡ／ＳＰＡＲＥ識別はＳＰＡＲＥである。また、消去カウントはインクリメントされ、ページＰ０、・・・、Ｐ５は未使用である。前のブロックアドレスは空欄になる。
【０１３２】
＜ウェアレベリング処理＞
次に図３２から図３５を用いてウェアレベリング処理について説明する。図３２はウェアレベリング処理のフローチャートの一例を示す図である。図１２に示したステップＳ２７の詳細フローを示している。
【０１３３】
〔ステップＳ２７ａ〕制御部１１は、アドレス変換テーブル２の最小消去カウントと、スペアブロックヘッダの最大消去カウントとの差が閾値より大きいか否かを判定する。閾値より大きい場合はステップＳ２７ｂへ処理が進み、閾値より小さい場合は終了する。
【０１３４】
〔ステップＳ２７ｂ〕制御部１１は、最小消去カウントのデータブロックの有効ページを最大消去カウントのスペアブロックにコピーする。
〔ステップＳ２７ｃ〕制御部１１は、各ページの新たな物理アドレスをアドレス変換テーブル２の対応する論理アドレスに反映する。
【０１３５】
〔ステップＳ２７ｄ〕制御部１１は、コピー元のデータブロックを消去する。
〔ステップＳ２７ｅ〕制御部１１は、消去したデータブロックをスペアブロックプールに組み込み、コピーしたスペアブロックをデータブロックに組み込む。
【０１３６】
図３３、図３４、図３５はテーブル相関上でウェアレベリング処理の動作を示す図である。
〔ステップＳ３１（図３３）〕制御部１１は、データブロックの最小消去カウントと、スペアブロックの最大消去カウントを比較する。
【０１３７】
〔ステップＳ３２（図３４）〕制御部１１は、閾値より大きい場合、最小消去カウントのデータブロックの有効ページを最大消去カウントのスペアブロックにコピーする。
〔ステップＳ３３（図３５）〕制御部１１は、データブロックの各ページを消去し、消去したデータブロックをスペアブロックプールに組み込み、コピーしたスペアブロックをデータブロックに組み込む。このような制御を行うことで、テーブル管理上で効率よくウェアレベリング処理を行うことができる。
【０１３８】
＜ページ更新処理＞
次に図３６から図３９を用いてページ更新処理について説明する。図３６はページ更新処理のフローチャートの一例を示す図である。図１２に示したステップＳ２８の詳細フローを示している。
【０１３９】
〔ステップＳ２８ａ〕制御部１１は、データブロックヘッダの未使用ページ先頭アドレスにデータを書き込み、対応するブロックテーブルのページに論理ページアドレスを入れる。
【０１４０】
〔ステップＳ２８ｂ〕制御部１１は、更新前の対応するブロックテーブルのページに無効フラグを立て、無効ページ数をインクリメントする。
〔ステップＳ２８ｃ〕制御部１１は、データブロックプールの前データブロックより無効ページ数が多いかを判定する。無効ページ数が多い場合はステップＳ２８ｄへ処理が進み、無効ページ数が少ない場合はステップＳ２８ｅへ処理が進む。
【０１４１】
〔ステップＳ２８ｄ〕制御部１１は、比較するデータブロックを１つ前に移動する。ステップＳ２８ｃへ処理が戻る。
〔ステップＳ２８ｅ〕制御部１１は、データブロックプールの無効ページ数が多い順にデータブロックを移動する。
【０１４２】
〔ステップＳ２８ｆ〕制御部１１は、アドレス変換テーブル２の対応する論理アドレスの物理アドレスを更新する。
＜ページ更新処理の具体例＞
図３７はページ更新処理でデータ書き込みを行う際のテーブル処理の一例を示す図である。３つのデータブロックの状態を示すブロックテーブルｄ１１、・・・、ｄ１３がリンクしている。なお、テーブル構成の見方は、上述したので以降説明は省略する。
【０１４３】
ブロックテーブルｄ１２のページＰ０が未使用であった場合、ページＰ０にデータを書き込むとする。この場合、制御部１１は、データブロックヘッダの未使用ページの先頭アドレスの領域にデータを書き込む。また、制御部１１は、対応するブロックテーブルのページに書き込んだデータの論理アドレスを挿入する（図３６のステップＳ２８ａ）。
【０１４４】
図３８、図３９はページ更新処理による無効フラグの設定およびデータブロックの移動の一例を示す図である。３つのデータブロックの状態を示すブロックテーブルｄ２１、・・・、ｄ２３がリンクしている。
【０１４５】
図３８において、ブロックテーブルｄ２３に対応するブロックに対し、ページＰ１が有効ページから無効ページになったとする。制御部１１は、ブロックテーブルｄ２３において、有効ページから無効ページになったページの欄に無効（無効フラグ）を設定する（図３６のステップＳ２８ｂ）。
【０１４６】
図３９において、制御部１１は、データブロックプールの無効ページが多い順にデータブロックを移動する。この例では、ブロックテーブルｄ２３を１つ前に移動することにより、ブロックテーブルｄ２１−１、ｄ２３−１、ｄ２２−１がリンク付けられる（図３６のステップＳ２８ｅ）。その後、制御部１１は、アドレス変換テーブル２の対応する論理アドレスの物理アドレスを更新する（図３６のステップＳ２８ｆ）。
【０１４７】
なお、移動前に対する変更箇所において、ブロックテーブルｄ２１−１は、次のブロックアドレスがＡ４になる。ブロックテーブルｄ２３−１は、次のブロックアドレスがＡ３であり、ページＰ１は無効ページになり、前のブロックアドレスがＡ２になる。ブロックテーブルｄ２２−１は、次のブロックアドレスが０、前のブロックアドレスがＡ４になる。
【０１４８】
＜効果＞
フラッシュメモリのページ更新において、長期間で見れば、すべてのページは更新される可能性があるが、短期間（例えば１日）で見れば、更新されるデータは限られる。
【０１４９】
図４０は更新回数毎の未更新ページ数および更新ページ数のイメージ図である。縦軸は更新ページ数、横軸は更新回数である。グラフＧ１が直線で減少していたら、更新回数の多いページはいずれ０になってしまう。したがって、ある値に収束する曲線となるため更新回数が多くなるにつれて、未更新ページは０に近づく。つまり、ブロック内のページの多くが更新されるため、「無効」なページは同じデータブロックに集まるようになる。その結果、ガーベッジコレクション処理の実行を最小限にすることができ、ライトアンプリフィケーションを抑制することができる。
【０１５０】
図４１は更新ページ数および更新回数の関係の一例を示す図である。縦軸は更新ページ数、横軸は更新回数である。ここで、更新回数の取り方、スペアブロックの割合について考察すると、例えば、１００００ブロックの製品を例にとると、更新ページ数のグラフＧ２は、（更新回数）×（更新ページ数（ブロック単位））＝１００００と近似する。（更新ページ数）が１ブロックになるためには、（更新回数）＝１００００となる。
【０１５１】
スペアブロックをデータブロックの４％の４００ブロックとすると、更新回数１００００までを２０等分に分ければ、それぞれで使用するスペアブロックの最大は２０と見積もられるため、グラフＧ２に示されるように、スペアブロックが不足することはない。
【０１５２】
上記で説明した本発明の記憶制御装置１０およびＳＳＤ１０ａの処理機能は、コンピュータによって実現することができる。この場合、記憶制御装置１０およびＳＳＤ１０ａが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１５３】
処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリ等がある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等がある。光ディスクには、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）／ＲＷ（Rewritable）等がある。光磁気記録媒体には、ＭＯ（Magneto Optical disk）等がある。
【０１５４】
プログラムを流通させる場合、例えば、そのプログラムが記録されたＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１５５】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。
【０１５６】
また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。また、上記の処理機能の少なくとも一部を、ＤＳＰ、ＡＳＩＣ、ＰＬＤ等の電子回路で実現することもできる。
【０１５７】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１５８】
１０  記憶制御装置
１１  制御部
１２  記憶部
Ｄｂ０  データブロック
Ｓｐ０、ｓ１、ｓ２、ｓ３、ｓ４、ｓ５、ｓ６  スペアブロック
【図１】
2019212099.tif 000003
【図２】
2019212099.tif 000004
【図３】
2019212099.tif 000005
【図４】
2019212099.tif 000006
【図５】
2019212099.tif 000007
【図６】
2019212099.tif 000008
【図７】
2019212099.tif 000009
【図８】
2019212099.tif 000010
【図９】
2019212099.tif 000011
【図１０】
2019212099.tif 000012
【図１１】
2019212099.tif 000013
【図１２】
2019212099.tif 000014
【図１３】
2019212099.tif 000015
【図１４】
2019212099.tif 000016
【図１５】
2019212099.tif 000017
【図１６】
2019212099.tif 000018
【図１７】
2019212099.tif 000019
【図１８】
2019212099.tif 000020
【図１９】
2019212099.tif 000021
【図２０】
2019212099.tif 000022
【図２１】
2019212099.tif 000023
【図２２】
2019212099.tif 000024
【図２３】
2019212099.tif 000025
【図２４】
2019212099.tif 000026
【図２５】
2019212099.tif 000027
【図２６】
2019212099.tif 000028
【図２７】
2019212099.tif 000029
【図２８】
2019212099.tif 000030
【図２９】
2019212099.tif 000031
【図３０】
2019212099.tif 000032
【図３１】
2019212099.tif 000033
【図３２】
2019212099.tif 000034
【図３３】
2019212099.tif 000035
【図３４】
2019212099.tif 000036
【図３５】
2019212099.tif 000037
【図３６】
2019212099.tif 000038
【図３７】
2019212099.tif 000039
【図３８】
2019212099.tif 000040
【図３９】
2019212099.tif 000041
【図４０】
2019212099.tif 000042
【図４１】
2019212099.tif 000043