(57)【要約】      （修正有）【課題】不揮発性メモリにおける空き領域の確保の効率化を図ることが可能な管理装置、管理方法、およびプログラムを提供する。【解決手段】不揮発性メモリにおけるデータの書き込み、読み出し、消去を、ブロックのサイズの整数分の１かつページのサイズの整数倍のトランスレーションユニット（ＴＵ）単位で論理アドレス−物理アドレス変換を行うことによって管理し、未書き込みの物理ＴＵを増やすフォールド処理を行う管理部を備え、管理部は、フォールド処理を開始した場合には、書き込み済みの有効な物理ＴＵのデータを、未書き込みの物理ＴＵがあるブロックのうちの、先頭の物理ＴＵが未書き込みであるブロックへとコピーし、フォールド処理によって増えた未書き込みの物理ＴＵのサイズがブロックのサイズ以上となるまで、フォールド処理を繰り返す。【選択図】図１６
2012133655.tif 000002
【特許請求の範囲】
【請求項１】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の１、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、
前記管理部は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理装置。
【請求項２】
前記管理部は、前記フォールド処理を行った後、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、前記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーする、請求項１に記載の管理装置。
【請求項３】
前記管理部における前記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、
前記管理部は、前記判定部において前記開始条件を満たすと判定された場合に、選択的に前記フォールド処理を行う、請求項１、または２のいずれか１項に記載の管理装置。
【請求項４】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている前記ブロックの数が所定の閾値より大きいまたは前記閾値以上であることを前記開始条件として、前記判定を行う、請求項３に記載の管理装置。
【請求項５】
前記判定部は、さらに、前記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを前記開始条件として、前記判定を行う、請求項４に記載の管理装置。
【請求項６】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない前記ブロックの数が所定の閾値より小さいまたは前記閾値以下であることを前記開始条件として、前記判定を行う、請求項３に記載の管理装置。
【請求項７】
前記管理部は、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、前記ブロックのサイズの所定の整数倍以上となるまで前記フォールド処理を繰り返す、請求項１、または２のいずれか１項に記載の管理装置。
【請求項８】
前記管理部は、前記不揮発性メモリにおける前記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、前記フォールド処理におけるコピー元のブロックとして選択する、請求項１、または２のいずれか１項に記載の管理装置。
【請求項９】
前記管理部は、前記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが前記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、前記フォールド処理の対象から除外する、請求項１、または２のいずれか１項に記載の管理装置。
【請求項１０】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項１、または２のいずれか１項に記載の管理装置。
【請求項１１】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項１、または２のいずれか１項に記載の管理装置。
【請求項１２】
前記管理部は、前記フォールド処理を行う場合には、繰り返し行われる前記フォールド処理においてコピー元となる全てのブロックにおける前記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した前記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した前記物理トランスレーションユニットのデータをコピーする、請求項１、または２のいずれか１項に記載の管理装置。
【請求項１３】
前記不揮発性メモリをさらに備える、請求項１、または２のいずれか１項に記載の管理装置。
【請求項１４】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の１、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップと、
を有し、
前記管理するステップでは、前記判定するステップにおいて前記開始条件を満たすと判定された場合に、前記フォールド処理が選択的に行われ、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理方法。
【請求項１５】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の１、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、
前記管理手段は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、管理装置、管理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ＮＡＮＤフラッシュメモリ（flash  memory）などのような電気的にデータの書き込み、読み出し、消去が可能な不揮発性メモリ（nonvolatile  memory）の大容量化が進んでいる。ここで、ＮＡＮＤフラッシュメモリのような上記不揮発性メモリにおける書き込みは、各ビットを“１”から“０”へと一方向に書き換えることによって行われる。そのため、上記不揮発性メモリにおいて新たにデータを書き込む場合には、一旦、消去を行って全てのビットを“１”にした上で、書き込みを行う必要がある。また、上記不揮発性メモリにおいては、データの書き込み／読み出しの最小単位は「ページ」であり、消去の最小単位は、複数のページが集まった「ブロック」である。上記のように、消去の最小単位である「ブロック」のサイズは、書き込みの最小単位である「ページ」のサイズよりも例えば数十倍程大きいので、上記不揮発性メモリにおけるデータの書き換えをより効率的に行うためには、何らかの仕組みが必要となる。
【０００３】
このような中、不揮発性メモリにおけるデータの書き換えの効率化を図るための技術が開発されている。ブロックサイズの整数分の１かつページサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行って、不揮発性メモリのアクセス管理を行い、ブロックの内容のうち、使用中の物理トランスレーションユニットを、別の未使用の物理トランスレーションユニットがあるブロックにコピーし、元のブロックを消去することにより、元のブロックに含まれていた無効の物理トランスレーションユニットの数だけ、新たに未使用の物理トランスレーションユニットを増やす技術としては、例えば、特許文献１が挙げられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−１１６６０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
不揮発性メモリにおけるデータの書き換えの効率化を図るための従来の技術（以下、単に「従来の技術」と示す。）は、不揮発性メモリにおけるあるブロックの物理トランスレーションユニットのデータをコピーし、当該ブロック（コピー元のブロック）を消去する。よって、従来の技術を用いる場合には、ブロック内に、書き込み済みの無効な物理トランスレーションユニット（無効なデータが記録されている物理トランスレーションユニット）が多ければ多いほど、データを書き込み可能な空き容量を増やすことが可能である。
【０００６】
ここで、空き領域を効率的に確保することは、例えば、不揮発性メモリをデータの記録媒体として使用するユーザ（以下、単に「ユーザ」と示す場合がある。）からみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、ＮＡＮＤフラッシュメモリなどのような不揮発性メモリの長寿命化に寄与する。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていない。
【０００７】
本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、不揮発性メモリにおける空き領域の確保の効率化を図ることが可能な、新規かつ改良された管理装置、管理方法、およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明の第１の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の１、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、上記管理部は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理装置が提供される。
【０００９】
かかる構成により、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【００１０】
また、上記管理部は、上記フォールド処理を行った後、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、上記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーしてもよい。
【００１１】
また、上記管理部における上記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、上記管理部は、上記判定部において上記開始条件を満たすと判定された場合に、選択的に上記フォールド処理を行ってもよい。
【００１２】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている上記ブロックの数が所定の閾値より大きいまたは上記閾値以上であることを上記開始条件として、上記判定を行ってもよい。
【００１３】
また、上記判定部は、さらに、上記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを上記開始条件として、上記判定を行ってもよい。
【００１４】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない上記ブロックの数が所定の閾値より小さいまたは上記閾値以下であることを上記開始条件として、上記判定を行ってもよい。
【００１５】
また、上記管理部は、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、上記ブロックのサイズの所定の整数倍以上となるまで上記フォールド処理を繰り返してもよい。
【００１６】
また、上記管理部は、上記不揮発性メモリにおける上記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、上記フォールド処理におけるコピー元のブロックとして選択してもよい。
【００１７】
また、上記管理部は、上記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが上記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、上記フォールド処理の対象から除外してもよい。
【００１８】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【００１９】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【００２０】
また、上記管理部は、上記フォールド処理を行う場合には、繰り返し行われる上記フォールド処理においてコピー元となる全てのブロックにおける上記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した上記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した上記物理トランスレーションユニットのデータをコピーしてもよい。
【００２１】
上記不揮発性メモリをさらに備えていてもよい。
【００２２】
上記目的を達成するために、本発明の第２の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の１、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップとを有し、上記管理するステップでは、上記判定するステップにおいて上記開始条件を満たすと判定された場合に、上記フォールド処理が選択的に行われ、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理方法が提供される。
【００２３】
かかる方法を用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【００２４】
上記目的を達成するために、本発明の第３の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の１、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、上記管理手段は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、プログラムが提供される。
【００２５】
かかるプログラムを用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【発明の効果】
【００２６】
本発明によれば、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【図面の簡単な説明】
【００２７】
【図１】不揮発性メモリにおける前提を説明するための説明図である。
【図２】不揮発性メモリにおける前提を説明するための説明図である。
【図３】従来の技術における問題を説明するための説明図である。
【図４】従来の技術における問題を説明するための説明図である。
【図５】従来の技術における問題を説明するための説明図である。
【図６】従来の技術における問題を説明するための説明図である。
【図７】本発明の実施形態に係る管理装置がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。
【図８】本発明の実施形態に係る管理装置におけるマルチフォールド処理の一例を示す説明図である。
【図９】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図１０】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図１１】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図１２】本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。
【図１３】本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【図１４】本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【図１５】本発明の実施形態に係る第１のマルチフォールド処理の一例を示す説明図である。
【図１６】本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【図１７】本発明の実施形態に係る第２のマルチフォールド処理の一例を示す説明図である。
【図１８】本発明の実施形態に係る管理装置の構成の一例を示すブロック図である。
【図１９】本発明の実施形態に係る管理装置のハードウェア構成の一例を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書および図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２９】
また、以下では、下記に示す順序で説明を行う。
１．本発明の実施形態に係る管理方法
２．本発明の実施形態に係る管理装置
３．本発明の実施形態に係るプログラム
【００３０】
（本発明の実施形態に係る管理方法）
本発明の実施形態に係る管理装置（以下、「管理装置１００」と示す場合がある。）の構成について説明する前に、本発明の実施形態に係る不揮発性メモリの管理方法について説明する。以下では、管理装置１００が、本発明の実施形態に係る管理方法に係る処理を行うものとして説明する。また、以下では、本発明の実施形態に係る管理装置１００の管理対象の不揮発性メモリが、ＮＡＮＤフラッシュメモリである場合を例に挙げて説明する。なお、本発明の実施形態に係る管理装置１００の管理対象の不揮発性メモリが、ＮＡＮＤ型のフラッシュメモリに限られないことは、言うまでもない。
【００３１】
［前提］
本発明の実施形態に係る管理方法に係る処理について説明する前に、管理装置１００の管理対象の不揮発性メモリにおける前提について説明する。
【００３２】
図１、図２は、不揮発性メモリにおける前提を説明するための説明図である。図１に示すように、不揮発性メモリは、データの書き込み／読み出しの最小単位である「ページ」と、複数のページからなる消去の最小単位である「ブロック」とで構成される。
【００３３】
また、不揮発性メモリには、製造時などの段階において「不良ブロック」とよばれるデータの記録ができないブロック（使用できないブロック）が存在する。そのため、管理装置１００は、不揮発性メモリの不良ブロックを避けて、データの読み書きを行わなければならない。
【００３４】
また、不揮発性メモリの各ブロックにおいては、それぞれのブロックに含まれるページに番号（ページを識別するための番号）が付されており、ＮＡＮＤフラッシュメモリのような不揮発性メモリの多くは、図２のＡに示すように、当該番号が小さいページの順にデータが書き込まれる。そして、ＮＡＮＤフラッシュメモリのような不揮発性メモリの多くは、例えば図２のＢに示すように、ランダムな順番でページにデータが書き込まれることは、禁止される。
【００３５】
また、不揮発性メモリの各ブロックには、書き換えの回数に上限（いわゆる寿命）があることから、不揮発性メモリの長寿命化を図るためには、特定のブロックに書き換えが偏らないようにする必要がある。
【００３６】
不揮発性メモリは、例えば上記のような特徴を有する。ここで、ユーザの利便性を損ねないためには、例えば、上記不良ブロックや消去の処理をユーザに意識させないことが望ましい。そのため、不揮発性メモリの管理には、例えば、不揮発性メモリを使用する側（例えばファイルシステム）からの要求を解釈して、書き込み操作、読み出し操作など、不揮発性メモリを操作するための命令に変換する論理−物理変換層（レイヤー）が用いられる。
【００３７】
［従来の技術における問題］
次に、従来の技術における問題について、より具体的に説明する。図３〜図６は、従来の技術における問題を説明するための説明図である。
【００３８】
上述したように、従来の技術では、ブロックのサイズよりも小さい単位であるトランスレーションユニット（以下、「ＴＵ」と示す場合がある。）で論理アドレス−物理アドレス変換を行っている。ここで、図３に示すように、トランスレーションユニットは、ブロックのサイズの整数分の１のサイズであり、かつ、ページのサイズの整数倍のサイズである。すなわち、ブロックは、複数のトランスレーションユニットを含み、トランスレーションユニットは、複数のトランスレーションユニットを含む。
【００３９】
また、従来の技術では、トランスレーションユニットを、不揮発性メモリ上の実際のトランスレーションユニット（以下、「物理トランスレーションユニット」または「物理ＴＵ」と示す場合がある。）と、アドレス変換されて不揮発性メモリを使用する側に提供されるトランスレーションユニット（以下、「論理トランスレーションユニット」または「論理ＴＵ」、「ＬＴＵ」と示す場合がある。）とに分類する。上記によって、従来の技術では、例えば、ファイルシステムにおける読み書きの単位と、トランスレーションユニットを一致させるなど、データの読み書きのサイズを柔軟に設定することが可能となる。
【００４０】
また、従来の技術におけるデータの書き換えは、図４に示すように、データが記録されていない物理トランスレーションユニットにデータを追記することによって行われる。より具体的には、書き換え前のデータが記録されていた物理トランスレーションユニットＰ１を無効な状態へと更新し（図４のＣ）、書き換えを行う新たなデータを、データが記録されていない物理トランスレーションユニットＰ２に書き込むことによって（図４のＤ）、データの書き換えが行われる。上記によって、不揮発性メモリでは、図４の物理トランスレーションユニットＰ２に示すように、最新のデータが記録されてる状態の物理トランスレーションユニット（以下、「書き込み済みの有効な物理トランスレーションユニット」と示す場合がある。）と、消去対象の古いデータが記録されている状態の物理トランスレーションユニット（以下、「書き込み済みの無効な物理トランスレーションユニット」と示す場合がある。）とが生じる。
【００４１】
以下では、物理トランスレーションユニットにおいて、最新のデータが記録されてる状態を「ＩＮＵＳＥ」と示し、消去対象の古いデータが記録されている状態を「ＤＩＲＴＹ」と示す場合がある。また、以下では、データの記録がされていない物理トランスレーションユニットを「未書き込みの物理トランスレーションユニット」と示す場合があり、物理トランスレーションユニットにおいて消去後に（または初期時に）データが記録されていない状態を「ＣＬＥＡＮ」と示す場合がある。
【００４２】
上述したように、ＮＡＮＤフラッシュメモリのような不揮発性メモリは、ブロック単位でしかデータの消去を行うことができない。そのため、ブロックを構成する一部の物理トランスレーションユニットに、例えば図４の物理トランスレーションユニットＰ１に示すような“書き込み済みの無効な物理トランスレーションユニット”があったとしても、当該ブロック内に“書き込み済みの有効な物理トランスレーションユニット”が存在した場合には、消去を行うことができない。よって、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける“書き込み済みの無効な物理トランスレーションユニット”の数が増え、また、データの書き込みが可能な物理トランスレーションユニット（例えば、ＣＬＥＡＮな物理トランスレーションユニット）の数が減ってしまう。つまり、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける空き領域が減ることとなる。
【００４３】
そこで、従来の技術では、データの書き込みが可能な物理トランスレーションユニットの数を増やして、不揮発性メモリにおける空き領域を確保するために、フォールド処理を行う。ここで、フォールド処理とは、ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす処理である。
【００４４】
図５は、フォールド処理の概要を示している。図５（ａ）はフォールド処理前のブロックＢ１、およびブロックＢ２状態を示しており、図５（ｂ）はフォールド処理中のブロックＢ１、およびブロックＢ２状態を示している。そして、図５（ｃ）はフォールド処理後のブロックＢ１、およびブロックＢ２状態を示している。フォールド処理では、コピー元のブロックＢ１の“書き込み済みの有効な物理トランスレーションユニット”がコピー先のブロックＢ２にコピーされ、コピーされた物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”に更新される（図５（ｂ））。そして、フォールド処理では、コピー元のブロックＢ１を消去する（図５（ｃ））。図５に示すように、フォールド処理が行われることによって“未書き込みの物理トランスレーションユニット”が増えていることが分かる。よって、フォールド処理が行われることによって、不揮発性メモリにおける空き領域を増やすことが可能となる。
【００４５】
従来の技術は、例えば、不揮発性メモリデータが書き込まれた後、データが記録されているブロック（ＩＮＵＳＥ、またはＤＩＲＴＹの物理トランスレーションユニットを含むブロック。以下、「使用中のブロック」と示す場合がある。）の総数が閾値を超えた以上となったとき（または、閾値以上となったとき）に、上記フォールド処理を１回だけ行う。よって、従来の技術を用いる場合には、不揮発性メモリにおける空き領域を増やすことが可能である。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていないので、効率的に不揮発性メモリの空き領域を確保することはできない。
【００４６】
図６は、従来の技術に係るフォールド処理の一例を示しており、不揮発性メモリの各ブロックの状態を時系列（図６（ａ）〜図６（ｈ））で示している。ここで、図６は、使用中のブロックが６（閾値の一例）より大きくなったとき（開始条件）にフォールド処理が行われ、フォールド処理が１回で終了する（停止条件）場合を示している。以下では、図６に示す処理を、従来の技術を用いる管理装置（以下、「従来の管理装置１０」と示す場合がある。）が行うものとして説明する。
【００４７】
図６（ａ）の状態においてＬＴＵ３の書き換えが行われると（図６（ｂ））、上記開始条件が満たされ、従来の管理装置１０は、フォールド処理を行う（図６（ｃ））。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置１０は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【００４８】
また、図６（ｃ）の状態においてＬＴＵ４の書き換えが行われると（図６（ｄ））、従来の管理装置１０は、上記開始条件を満たすか否かを判定する。図６（ｄ）の状態では、上記開始条件は満たされていないので、従来の管理装置１０は、フォールド処理を行わない。
【００４９】
図６（ｄ）の状態においてＬＴＵ８の書き換えが行われると（図６（ｅ））、上記開始条件が満たされ、従来の管理装置１０は、フォールド処理を行う（図６（ｆ））。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置１０は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【００５０】
そして、図６（ｆ）の状態においてＬＴＵ９の書き換えが行われると（図６（ｇ））、上記開始条件が満たされ、従来の管理装置１０は、フォールド処理を行う（図６（ｈ））。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置１０は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【００５１】
図６（ａ）〜図６（ｈ）に示すように、従来の管理装置１０は、開始条件を満たすごとにフォールド処理を１回だけ行う。その結果、図６（ｈ）に示すように、書き換えが行われたＬＴＵ３、ＬＴＵ４、ＬＴＵ８、およびＬＴＵ９は、複数のブロックに分散して書き込まれることとなる。ここで、不揮発性メモリを使用する側が、例えばＦＡＴ（File  Allocation  Table）システムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン（書き換え順序）で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。また、例えば、論理トランスレーションユニットのサイズとＦＡＴのクラスタのサイズとが同一である場合などには、上記の可能性はより高くなる。なお、本発明の実施形態に係るファイルシステムは、ＦＡＴに限られず、例えば、ＮＴＦＳ（NT  File  System）やｅｘｔ４（fourth  extended  file  system）などが挙げられる。
【００５２】
ここで、例えば、不揮発性メモリに対するデータの書き換えが、図６に示す論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで行われた場合には、図６（ｈ）に示すＬＴＵ３、ＬＴＵ４、ＬＴＵ８、およびＬＴＵ９に対応する物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。
【００５３】
しかしながら、図６（ｈ）に示すように、ＬＴＵ３、ＬＴＵ４、ＬＴＵ８、およびＬＴＵ９は、複数のブロックに分散して書き込まれているので、不揮発性メモリにおいて“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在することは期待できない。したがって、“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在しない状態でフォールド処理を行ったとしても、不揮発性メモリの空き領域を十分に確保することができないので、従来の技術を用いたとしても、効率的に不揮発性メモリの空き領域を確保することはできるとは限らない。
【００５４】
［本発明の実施形態に係る管理方法の概要］
本発明の実施形態に係る管理装置１００は、従来の技術と同様に、不揮発性メモリにおけるデータの書き込み、読み出し、消去を、トランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理する。
【００５５】
また、管理装置１００は、従来の技術と同様に、フォールド処理を行うことによって不揮発性メモリの空き領域を確保するが、管理装置１００は、従来の技術がフォールド処理を１回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。以下では、本発明の実施形態に係るフォールド処理を、フォールド処理を複数回繰り返し行いうることから、「マルチフォールド処理」と示す場合がある。ここで、本発明の実施形態に係る所定の停止条件としては、例えば、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ以上となるまで”や、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズの所定の整数倍以上となるまで”などが挙げられる。
【００５６】
また、管理装置１００は、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。
【００５７】
図７は、本発明の実施形態に係る管理装置１００がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。管理装置１００は、データが記録されていないブロックを選択し、当該ブロックにおける先頭の物理トランスレーションユニット（付された番号が最も小さい物理トランスレーションユニット）から順に、データの書き込みを行う。そして、管理装置１００は、データの書き込みを行っている書き込み対象のブロック（以下、「書き込み対象ブロック」または「ＰＴＵブロック」と示す場合がある。）を構成する全ての物理トランスレーションユニットの書き込みが完了したときに、データが記録されていないブロックを新たに選択して、当該ブロックにデータを書き込む。以下では、データの書き込みの対象となる物理トランスレーションユニットを「ＰＴＵ」と示す場合がある。また、以下では、データの書き込みを行う各時点において、データの書き込みの対象となっている物理トランスレーションユニットを「書き込み対象現在物理トランスレーションユニット」または「書き込み対象ＰＴＵ」と示す場合がある。つまり、本発明の実施形態に係る書き込み対象ブロックとは、書き込み対象現在物理トランスレーションユニットが含まれるブロックを指すこととなる。
【００５８】
より具体的には、管理装置１００は、例えば下記の（１）の処理（開始条件判定処理）、および（２）の処理（フォールド処理）を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。
【００５９】
（１）開始条件判定処理
管理装置１００は、フォールド処理を開始するための開始条件を満たすか否かを判定する。
【００６０】
ここで、本発明の実施形態に係る開始条件としては、例えば、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロックの数が所定の閾値より大きい（または所定の閾値以上である。以下、同様とする。）ことが挙げられる。直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであることを開始条件のひとつとすることによって、管理装置１００は、図７に示すように、“書き込み済みの有効な物理トランスレーションユニット”のデータを、ブロックの先頭の物理トランスレーションユニットへとコピーすることが可能となる。また、データが書き込まれているブロックの数が所定の閾値より大きいことを開始条件のひとつとすることによって、管理装置１００は、不揮発性メモリの空き容量が一定値未満（または、一定値以下）となったときに、空き容量の確保を行うことができる。
【００６１】
また、管理装置１００は、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていないブロックの数が所定の閾値より小さい（または閾値以下である。以下、同様とする。）ことを開始条件とすることもできる。データが書き込まれていないブロックの数が所定の閾値より小さいことを開始条件のひとつとすることによって、例えば、不揮発性メモリにおいて不良ブロックが増えた結果データを記録可能な絶対容量が小さくなったとしても、空き容量の確保を行うことが可能となる。
【００６２】
なお、本発明の実施形態に係る開始条件は、上記に限られない。例えば、管理装置１００は、上記２つの開始条件の双方を組み合わせた条件（上記２つの開始条件の論理和）を、開始条件することが可能である。また、管理装置１００は、上述した開始条件それぞれに対して、さらに、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと（言い換えれば、システムがいわゆるアイドル状態にあること）を、条件として加えてもよい。不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを開始条件のひとつとすることによって、管理装置１００は、データの書き込み、読み出し、消去に係る処理と、フォールド処理とが同時期に行われることを回避することが可能となる。よって、管理装置１００は、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【００６３】
（２）フォールド処理
上記（１）の処理（開始条件判定処理）において開始条件を満たすと判定された場合には、管理装置１００は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ（合計サイズ）が、ブロックのサイズを基準とする所定のサイズ以上となるまで、フォールド処理を繰り返す（マルチフォールド処理）。
【００６４】
ここで、「フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ（合計サイズ）が、ブロックのサイズを基準とする所定のサイズ以上となる」ことは、（２）の処理（フォールド処理）における処理の停止条件の一例である。また、本発明の実施形態に係るブロックのサイズを基準とする所定のサイズとしては、例えば、ブロックのサイズや、ブロックのサイズの整数倍のサイズが挙げられる。本発明の実施形態に係るブロックのサイズを基準とする所定のサイズは、例えば、予め規定されたサイズであってもよいし、ユーザ操作に基づいて適宜設定されたサイズであってもよい。また、本発明の実施形態に係るサイズは、例えば［Ｂｙｔｅ］、［ＫＢｙｔｅ］で表されるが、本発明の実施形態に係るサイズは、上記に限られない。
【００６５】
また、管理装置１００は、フォールド処理を行った後、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れるか否かを判定してもよい。上記判定を行った場合において割り切れないと判定したときには、管理装置１００は、端数のサイズに対応する“未書き込みの物理トランスレーションユニット”のサイズ分、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。管理装置１００が、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、（２）の処理（フォールド処理）後の不揮発性メモリにおいては、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットとなる。よって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、フォールド処理によりコピーするデータとユーザの書き換えデータとを、ブロック間で分離することができ、その結果、ユーザのアクセスパターンがブロック内に保存される。したがって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、より効率的に空き容量の確保を行うことが可能となる。
【００６６】
管理装置１００は、上記のように停止条件を満たすまでフォールド処理を繰り返す。ここで、本発明の実施形態に係る管理装置１００におけるフォールド処理について説明する。管理装置１００は、フォールド処理として、ブロックの内容のうち、“書き込み済みの有効な物理トランスレーションユニット”のデータを、“未書き込みの物理トランスレーションユニット”があるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた“書き込み済みの無効な物理トランスレーションユニット”の数分、“未書き込みの物理トランスレーションユニット”を増やす処理を行う。つまり、管理装置１００は、基本的に従来の技術と同様の処理を、フォールド処理として行う。
【００６７】
また、管理装置１００は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド処理におけるコピー元のブロックとして選択する。上記のようにフォールド処理におけるコピー元のブロックを選択することによって、フォールド処理後に増える“未書き込みの物理トランスレーションユニット”の数をより増やすことが可能となるので、管理装置１００は、不揮発性メモリの空き容量の確保をより効率的に行うことができる。
【００６８】
なお、管理装置１００におけるブロックの選択方法は、上記に限られない。例えば、管理装置１００は、フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外してもよい。管理装置１００は、上記のように特定のブロックを除外した上で、ブロックを選択することによって、不揮発性メモリの空き容量の確保をより効率的に行うことが可能となる。なお、上記選択方法を用いた場合の効果については、後述する。
【００６９】
また、管理装置１００は、例えば、不揮発性メモリにおけるブロックの中に“書き込み済みの無効な物理トランスレーションユニット”の数が最も多いブロックが複数存在する場合には、当該ブロックの中からランダムにブロックを選択してもよい。上記のようにブロックの選択をランダムに行うことによって、不揮発性メモリの空き容量の効率的な確保に加え、不揮発性メモリの長寿命化を図ることが可能となる。
【００７０】
管理装置１００は、例えば上記のようにフォールド処理におけるコピー元のブロックを選択することによって、不揮発性メモリの空き容量の効率的な確保を実現する。
【００７１】
また、管理装置１００は、フォールド処理を行う場合において、“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番を、例えば下記の（ａ）〜（ｃ）のように行う。
【００７２】
（ａ）第１の順番
管理装置１００は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。つまり、管理装置１００は、ブロック何の先頭の“書き込み済みの有効な物理トランスレーションユニット”のデータから順にコピーする。第１の順番を用いることによって、例えば、過去の論理トランスレーションユニットの書き込み順序を保存することが可能となる。
【００７３】
（ｂ）第２の順番
管理装置１００は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。より具体的には、管理装置１００は、例えば、対応する論理トランスレーションユニットに付された番号が小さい順にソートを行い、ソートされた順番で、当該論理トランスレーションユニットに対応する“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。ここで、例えばＦＡＴファイルシステムでは、空クラスタの割り当てをクラスタ番号が小さい順に行う。よって、例えば上記クラスタ番号と論理トランスレーションユニットに付された番号とが一致している場合には、管理装置１００は、不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【００７４】
（ｃ）第３の順番
管理装置１００は、繰り返し行われるフォールド処理（マルチフォールド処理）においてコピー元となる全てのブロックにおける“書き込み済みの有効な物理トランスレーションユニット”を特定する。ここで、管理装置１００は、例えば仮想的にマルチフォールド処理を行うことによって、上記特定を行う。そして、管理装置１００は、特定した物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した物理トランスレーションユニットのデータをコピーする。上記第３の順番でコピーを行うことによって、管理装置１００は、上記第２の順番でコピーを行う場合よりも、さらに不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【００７５】
管理装置１００は、例えば上記（ａ）〜（ｃ）に示す順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。なお、本発明の実施形態に係る“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番は、上記に限られない。例えば、管理装置１００は、任意の順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーすることも可能である。
【００７６】
管理装置１００は、（２）の処理（フォールド処理）として、例えば上記のようなフォールド処理を停止条件を満たすまで繰り返し行うこと（マルチフォールド処理を行うこと）によって、不揮発性メモリの空き容量を確保する。
【００７７】
管理装置１００は、例えば、上記（１）の処理（開始条件判定処理）、および（２）の処理（マルチフォールド処理）を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。なお、上記では、管理装置１００が上記（１）の処理（開始条件判定処理）を行った後に、（２）の処理（フォールド処理）を行うことを示したが、管理装置１００における処理は、上記に限られない。例えば、管理装置１００は、上記（１）の処理（開始条件判定処理）の結果によらず、（２）の処理（フォールド処理）を行うことも可能である。上記の例としては、例えば、管理装置１００が備える操作部（後述する）から伝達される操作信号や、ユーザ操作に応じてリモート・コントローラなどの外部操作装置（図示せず）から送信される外部操作信号に基づいて、（２）の処理（マルチフォールド処理）を行う場合が挙げられる。
【００７８】
次に、管理装置１００がマルチフォールド処理を行うことによる効果について説明する。図８は、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理の一例を示す説明図である。ここで、図８は、図６と同様に、不揮発性メモリの各ブロックの状態を時系列（図８（ａ）〜図８（ｇ））で示している。また、図８は、マルチフォールド処理の開始条件が、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロック（使用中のブロック）の数が使用中のブロックが７（所定の閾値の一例）以上となったときである場合を示している。また、図８は、マルチフォールド処理の停止条件が、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることである場合を示している。
【００７９】
図８（ａ）の状態においてＬＴＵ３の書き換えが行われると（図８（ｂ））、管理装置１００は、上記開始条件が満たされているか否かを判定する。図８（ｂ）の状態では、上記開始条件は満たされていないので、管理装置１００は、フォールド処理を行わない。
【００８０】
図８（ｂ）の状態においてＬＴＵ４の書き換えが行われると（図８（ｃ））、管理装置１００は、上記開始条件が満たされているか否かを判定する。図８（ｃ）の状態では、上記開始条件は満たされていないので、管理装置１００は、フォールド処理を行わない。
【００８１】
図８（ｃ）の状態においてＬＴＵ８の書き換えが行われると（図８（ｄ））、管理装置１００は、上記開始条件が満たされているか否かを判定する。図８（ｄ）の状態では、上記開始条件は満たされていないので、管理装置１００は、フォールド処理を行わない。
【００８２】
図８（ｄ）の状態においてＬＴＵ９の書き換えが行われると（図８（ｅ））、管理装置１００は、上記開始条件が満たされているか否かを判定する。ＬＴＵ９の書き換えによって、上記開始条件が満たされるので、管理装置１００は、１回目のフォールド処理を行う（図８（ｆ））。
【００８３】
フォールド処理を行うと、管理装置１００は、上記停止条件を満たしているか否かを判定する。図８（ｆ）の状態では、上記停止条件は満たされていないので、管理装置１００は、２回目のフォールド処理を行う（図８（ｇ））。そして、管理装置１００は、上記停止条件を満たしているか否かを判定する。
【００８４】
図８（ｇ）の状態では、１ブロックのサイズに該当するサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。よって、管理装置１００は、マルチフォールド処理を終了する。
【００８５】
ここで、図８（ｇ）に示すように、マルチフォールド処理が行われることによって、書き換えを行ったＬＴＵ３、ＬＴＵ４、ＬＴＵ８、およびＬＴＵ９が、同一のブロックに集約されていることが分かる。ここで、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行った上記ブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置１００は、図６に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。また、図８に示す例では、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合に、管理装置１００は、書き換えを行った上記ブロックの消去を行えばよいので、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【００８６】
管理装置１００は、例えば図８に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【００８７】
なお、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理は、図８に示す例に限られない。例えば、図８では、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズと一致する場合を示したが、当該ブロックのサイズを超えることも想定される。そこで、次に、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理の他の例として、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における例について説明する。
【００８８】
図９は、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理の他の例を示す説明図である。ここで、図９は、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における処理の一例を示している。また、図９は、図８と同様に、不揮発性メモリの各ブロックの状態を時系列（図９（ａ）〜図９（ｄ））で示している。また、図９は、管理装置１００が、図８と同様の開始条件、停止条件にてフォールド処理を行う例を示している。
【００８９】
図９（ａ）の状態においてＬＴＵ１２の書き換えが行われると（図９（ｂ））、管理装置１００は、開始条件が満たされているか否かを判定する。ＬＴＵ１２の書き換えによって開始条件が満たされるので、管理装置１００は、１回目のフォールド処理を行う（図９（ｂ））。
【００９０】
フォールド処理を行うと、管理装置１００は、停止条件を満たしているか否かを判定する。図９（ｂ）の状態では、停止条件は満たされていないので、管理装置１００は、２回目のフォールド処理を行う（図９（ｃ））。そして、管理装置１００は、停止条件を満たしているか否かを判定する。
【００９１】
図９（ｃ）の状態では、１ブロックのサイズより大きなサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。また、図９（ｃ）の状態では、図８（ｇ）の状態と異なり、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れない。上記の場合、管理装置１００は、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分（図９（ｃ）の例では、１つの物理トランスレーションユニットのサイズ）、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”であるＬＴＵ０のデータをコピーする（図９（ｄ））。
【００９２】
図９（ｄ）に示すように、１ブロックのサイズ（ブロックのサイズを基準とする所定のサイズの一例）を超えるサイズ分を、“書き込み済みの有効な物理トランスレーションユニット”のデータで埋めることによって、マルチフォールド処理後の不揮発性メモリの状態が、図８（ｇ）と同様の状態となる。よって、管理装置１００は、図９に示す処理を行う場合においても、図８に示すマルチフォールド処理と同様に、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、管理装置１００は、将来的行うフォールド処理において書き換えを行った上記ブロックの消去を行えばよいので、図８に示すマルチフォールド処理と同様に、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【００９３】
なお、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理は、図８、図９に示す例に限られない。例えば、管理装置１００は、さらにフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを基準とする所定のサイズを超えることを、停止条件として、マルチフォールド処理を行うことも可能である。
【００９４】
図１０は、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理の他の例を示す説明図である。また、図１０は、図８と同様に、不揮発性メモリの各ブロックの状態を時系列（図１０（ａ）〜図１０（ｃ））で示している。また、図１０は、管理装置１００が、図８と同様の開始条件にてフォールド処理を行う例を示している。
【００９５】
図１０（ａ）の状態においてＬＴＵ１２の書き換えが行われると（図１０（ｂ））、管理装置１００は、開始条件が満たされているか否かを判定する。ＬＴＵ１２の書き換えによって開始条件が満たされるので、管理装置１００は、１回目のフォールド処理を行う（図１０（ｂ））。
【００９６】
フォールド処理を行うと、管理装置１００は、さらにフォールド処理を行った場合に、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えるか否かを判定する（停止条件の判定）。ここで、管理装置１００は、例えば仮想的にフォールド処理を行うことによって、上記判定を行う。ここで、図１０（ｂ）の状態において２回目のフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えてしまう（図１０（ｃ））。よって、管理装置１００は、２回目のフォールド処理を行うことなく、不揮発性メモリが図１０（ｂ）の状態のときに、マルチフォールド処理を終了する。
【００９７】
管理装置１００が上記のような停止条件でマルチフォールド処理を行うことによって、次に書き換えられるデータが分断されることを防止することが可能となる。よって、管理装置１００は、上記のような停止条件でマルチフォールド処理を行うことによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【００９８】
なお、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理は、図８〜図１０に示す例に限られない。例えば、管理装置１００は、上述したように、フォールド処理を行う場合において、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することも可能である。
【００９９】
図１１は、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理の他の例を示す説明図である。ここで、図１１は、上記のように特定のブロックを除外した上で、ブロックを選択する場合における処理の一例を示している。また、図１１は、図８と同様に、不揮発性メモリの各ブロックの状態を時系列（図１１（ａ）〜図１１（ｈ））で示している。また、図１１は、管理装置１００が、図８と同様の開始条件、停止条件にてフォールド処理を行う例を示している。また、図１１は、（ｉ）ＬＴＵ０〜ＬＴＵ１１の書き込み、（ｉｉ）ＬＴＵ１３、ＬＴＵ１４の書き込みの割り込み、（ｉｉｉ）ＬＴＵ０〜ＬＴＵ１１の上書き、が行われる場合における処理の一例を示している。
【０１００】
図１１（ａ）は、ＬＴＵ０〜ＬＴＵ１１が書き込まれた直後（上記（ｉ）の直後）の不揮発性メモリの状態を示している。また、図１１（ｂ）は、図１１（ａ）の状態においてＬＴＵ１３、ＬＴＵ１４が書き込まれた直後（上記（ｉｉ）の直後）の不揮発性メモリの状態を示している。
【０１０１】
図１１（ｂ）の状態において、ＬＴＵ０およびＬＴＵ１の書き込みが行われると（図１１（ｃ））、管理装置１００は、開始条件が満たされているか否かを判定する。ＬＴＵ０およびＬＴＵ１の書き換えによって開始条件が満たされるので、管理装置１００は、１回目のフォールド処理を行う（図１１（ｄ））。このとき、管理装置１００は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック（図１１における左端のブロック）を、フォールド処理の対象から除外する。図１１（ｄ）では、図１１における左端から４番目のブロックがフォールド処理の対象として選択された場合を示している。
【０１０２】
１回目のフォールド処理を行うと、管理装置１００は、停止条件を満たしているか否かを判定する。図１１（ｄ）の状態では、停止条件は満たされていないので、管理装置１００は、２回目のフォールド処理を行う（図１１（ｅ））。このとき、管理装置１００は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック（図１１における左端のブロック）を、フォールド処理の対象から除外する。図１１（ｅ）では、図１１における左端から６番目のブロックがフォールド処理の対象として選択された場合を示している。
【０１０３】
２回目のフォールド処理を行うと、管理装置１００は、上記停止条件を満たしているか否かを判定する。図１１（ｅ）の状態では、停止条件は満たされているので、管理装置１００は、マルチフォールド処理を終了する。
【０１０４】
次に、図１１（ｅ）の状態において、ＬＴＵ２およびＬＴＵ３の書き込みが行われると（図１１（ｆ））、管理装置１００は、開始条件が満たされているか否かを判定する。図１１（ｆ）の状態は開始条件を満たしていないので、管理装置１００は、フォールド処理を行わない。また、図１１（ｆ）に示す状態では、図１１における左端のブロックに含まれる全ての物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となっているので、管理装置１００は、図１１における左端のブロックを消去する（図１１（ｇ））。
【０１０５】
また、図１１（ｇ）の状態において、ＬＴＵ４およびＬＴＵ５の書き込みが行われると（図１１（ｈ））、管理装置１００は、開始条件が満たされているか否かを判定する。図１１（ｈ）の状態は開始条件を満たしていないので、管理装置１００は、フォールド処理を行わない。
【０１０６】
管理装置１００は、ＬＴＵ６〜ＬＴＵ１１についても、図１１（ｆ）〜図１１（ｈ）と同様に書き換えを行う。ここで、図１１（ｆ）〜図１１（ｈ）に示すように、管理装置１００は、ＬＴＵ２〜ＬＴＵ５の書き換えにおいてはフォールド処理を行っておらず、消去を行うことによって、書き換えを行っている。したがって、管理装置１００は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、不揮発性メモリの空き領域の確保の効率化を図ると共に、より効率的なデータの書き換えを実現することができる。
【０１０７】
また、例えばサイズが大きなファイルの上書きを行うようなケースでは、過去に行われた論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。よって、管理装置１００は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、上記のようにサイズが大きなファイルの上書きを行うようなケースにおいても、図１１に示すように、より効率的なデータの書き換えを実現することができる。
【０１０８】
管理装置１００は、例えば図８〜図１１に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理装置１００におけるマルチフォールド処理が、図８〜図１１に示す例に限られないことは、言うまでもない。
【０１０９】
［本発明の実施形態に係る、管理方法に係る処理の具体例］
次に、上述した本発明の実施形態に係る管理方法に係る処理について、より具体的に説明する。図１２は、本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。以下では、管理方法に係る処理を管理装置１００が行うものとして説明する。
【０１１０】
管理装置１００は、指定されたデータを書き込む（Ｓ１００：書き込み処理）。
【０１１１】
〔書き込み処理の一例〕
図１３は、本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【０１１２】
管理装置１００は、直前に書き込まれた物理ＴＵが、ブロックにおける最後の物理ＴＵであるか否かを判定する（Ｓ２００）。ステップＳ２００においてブロックにおける最後の物理ＴＵであると判定されない場合には、管理装置１００は、上記ブロックの次のＰＴＵを、書き込み対象ＰＴＵとして設定し（Ｓ２０２）、後述するステップＳ２０６からの処理を行う。
【０１１３】
また、ステップＳ２００においてブロックにおける最後の物理ＴＵであると判定された場合には、管理装置１００は、ブロックにおける先頭の物理ＴＵが“未書き込みの物理ＴＵ”であるブロックを選択し、選択したブロックの先頭の物理ＴＵを、書き込み対象ＰＴＵとして設定する（Ｓ２０４）。
【０１１４】
ステップＳ２０２またはステップＳ２０４において書き込み対象ＰＴＵが設定されると、管理装置１００は、当該書き込み対象ＰＴＵに指定されたデータを書き込む（Ｓ２０６）。そして、管理装置１００は、論理アドレス−物理アドレス変換に係る、論理アドレス−物理アドレス変換テーブル（論物変換テーブル）および物理ＴＵ状態マップを更新する（Ｓ２０８）。
【０１１５】
管理装置１００は、例えば図１３に示す処理を行うことによって、データの書き込みを行う。なお、本発明の実施形態に係る書き込み処理が、図１３に示す例に限られないことは、言うまでもない。
【０１１６】
再度図１２を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップＳ１００においてデータの書き込みが行われると、管理装置１００は、フォールド処理の開始条件を満たすか否かを判定する（Ｓ１０２）。
【０１１７】
ステップＳ１０２においてフォールド処理の開始条件を満たすと判定されない場合には、管理装置１００は、管理方法に係る処理を終了する。なお、本発明の実施形態に係る管理方法に係る処理は、一度終了すれば完了する類の処理ではなく、データの書き込みが発生するごとに繰り返し行われる。
【０１１８】
また、ステップＳ１０２においてフォールド処理の開始条件を満たすと判定された場合には、管理装置１００は、マルチフォールド処理を行う（Ｓ１０６）。
【０１１９】
〔マルチフォールド処理の一例〕
図１４は、本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【０１２０】
管理装置１００は、第１のマルチフォールド処理を行う（Ｓ３００）。ここで、本発明の実施形態に係る第１のマルチフォールド処理とは、例えば、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることを停止条件とするマルチフォールド処理である。
【０１２１】
＜第１のマルチフォールド処理の一例＞
図１５は、本発明の実施形態に係る第１のマルチフォールド処理の一例を示す説明図である。
【０１２２】
管理装置１００は、“ｎ_ｃｌｅａｎ”の値をｎ_ｃｌｅａｎ＝０（ゼロ）に設定し、“ｎ_ｃｏｐｙ_ｍａｘ”の値をｎ_ｃｏｐｙ_ｍａｘ＝Ｍ（Ｍは、ブロックに含まれる物理ＴＵ数よりも十分に大きい値。）に設定する（Ｓ４００）。ここで、“ｎ_ｃｌｅａｎ”とは、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を保持するために用いられる。また、“ｎ_ｃｏｐｙ_ｍａｘ”は、後述するフォールド処理において判定に用いられる。また、ステップＳ４００の処理は、“ｎ_ｃｌｅａｎ”の値を初期化する処理に該当する。
【０１２３】
ステップＳ４００において初期化処理が行われると、管理装置１００は、フォールド処理を実行する（Ｓ４０２）。
【０１２４】
｛フォールド処理の一例｝
図１６は、本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【０１２５】
管理装置１００は、“ｎ_ｃｏｐｙ”の値をｎ_ｃｏｐｙ＝０（ゼロ）に設定する（Ｓ５００）。ここで、“ｎ_ｃｏｐｙ”は、データをコピーした物理ＴＵ数を保持するための、一種のカウンタである。また、ステップＳ５００の処理は、“ｎ_ｃｏｐｙ”の値を初期化する処理に該当する。
【０１２６】
ステップＳ５００の処理が行われると、管理装置１００は、フォールド処理の対象となるブロック（以下、「フォールド対象ブロック」と示す。）を選択する（Ｓ５０２）。ここで、管理装置１００は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド対象ブロックとして選択するが、選択方法は、上記に限られない。
【０１２７】
ステップＳ５０２においてフォールド対象ブロックが選択されると、管理装置１００は、フォールド対象ブロックから未コピーの“書き込み済みの有効な物理ＴＵ”を選択する（Ｓ５０４）。ステップＳ５０４において未コピーの“書き込み済みの有効な物理ＴＵ”を選択すると、管理装置１００は、選択した物理ＴＵ内のデータを読み込み（Ｓ５０６）、読み込んだデータを、コピー先のブロックにおける未書き込みのＰＴＵにコピーする（Ｓ５０８）。そして、管理装置１００は、“ｎ_ｃｏｐｙ”の値を、ｎ_ｃｏｐｙ＝ｎ_ｃｏｐｙ＋１に更新する（Ｓ５１０）。
【０１２８】
ステップＳ５１０の処理が行われると、管理装置１００は、フォールド対象ブロックが含むすべての書き込み済みの有効な物理ＴＵのデータのコピーが完了したか否かを判定する（Ｓ５１２）。
【０１２９】
ステップＳ５１２においてデータのコピーが完了したと判定されない場合には、管理装置１００は、「ｎ_ｃｏｐｙ≧ｎ_ｃｏｐｙ_ｍａｘ」であるか否かを判定する（Ｓ５１４）。第１のマルチフォールド処理では、“ｎ_ｃｏｐｙ_ｍａｘ”の値としてＭ（Ｍは、ブロックに含まれる物理ＴＵ数よりも十分に大きい値。）が設定されているので、管理装置１００は、ステップＳ５０４からの処理を繰り返す。また、後述する第２のマルチフォールド処理では、“ｎ_ｃｏｐｙ_ｍａｘ”の値が、Ｍ以外の値に設定されうるので、管理装置１００は、ステップＳ５１４の判定結果に応じて選択的にステップＳ５０４からの処理を繰り返す。
【０１３０】
また、ステップＳ５１２においてデータのコピーが完了したと判定された場合には、管理装置１００は、フォールド対象ブロックを消去して（Ｓ５０６）、フォールド処理を終了する。
【０１３１】
管理装置１００は、例えば図１６に示す処理を行うことによって、フォールド処理を実現する。なお、本発明の実施形態に係るフォールド処理が、図１６に示す例に限られないことは、言うまでもない。
【０１３２】
再度図１５を参照して、本発明の実施形態に係る第１のマルチフォールド処理の一例について説明する。ステップＳ４０２においてフォールド処理が行われると、管理装置１００は、“ｎ_ｃｌｅａｎ”の値に、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を加える（Ｓ４０４）。そして、管理装置１００は、“ｎ_ｃｌｅａｎ”の値が、１ブロックあたりの物理ＴＵ数以上であるか否かを判定する（Ｓ４０６）。
【０１３３】
ステップＳ４０６において、“ｎ_ｃｌｅａｎ”の値が１ブロックあたりの物理ＴＵ数以上であると判定されない場合には、管理装置１００は、ステップＳ４０２からの処理を繰り返す。
【０１３４】
また、ステップＳ４０６において、“ｎ_ｃｌｅａｎ”の値が１ブロックあたりの物理ＴＵ数以上であると判定された場合には、管理装置１００は、第１のマルチフォールド処理を終了する。
【０１３５】
管理装置１００は、例えば図１５に示す処理を行うことによって、第１のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第１のマルチフォールド処理が、図１５に示す例に限られないことは、言うまでもない。
【０１３６】
再度図１４を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップＳ３００の処理が行われると、管理装置１００は、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの合計サイズが、１ブロックのサイズを超えたか否かを判定する（Ｓ３０２）。ここで、管理装置１００は、例えば、“ｎ_ｃｌｅａｎ”の値が１ブロックあたりの物理ＴＵ数を超えている場合に、１ブロックのサイズを超えたと判定するが、ステップＳ３０２における判定方法は、上記に限られない。
【０１３７】
ステップＳ３０２において１ブロックのサイズを超えたと判定されない場合には、管理装置１００は、第２のマルチフォールド処理を行う（Ｓ３０４）。ここで、本発明の実施形態に係る第２のマルチフォールド処理とは、例えば図９に示すように、１ブロックのサイズ（ブロックのサイズを基準とする所定のサイズの一例）を超えるサイズ分を“書き込み済みの有効な物理トランスレーションユニット”のデータで埋める、マルチフォールド処理である。
【０１３８】
＜第２のマルチフォールド処理の一例＞
図１７は、本発明の実施形態に係る第２のマルチフォールド処理の一例を示す説明図である。
【０１３９】
管理装置１００は、“ｎ_ｅｘｅｓｓ”の値をｎ_ｅｘｅｓｓ＝ｎ_ｃｌｅａｎ−（１ブロックあたりの物理ＴＵ数）に設定し、“ｎ_ｃｏｐｙ”の値をｎ_ｃｏｐｙ＝０（ゼロ）に設定する（Ｓ６００）。ここで、“ｎ_ｅｘｅｓｓ”とは、１ブロックのサイズを超えたサイズ分に相当する物理ＴＵ数を示す。また、ステップＳ６００の処理は、“ｎ_ｃｏｐｙ”の値を初期化する処理に該当する。
【０１４０】
ステップＳ６００の処理が行われると、管理装置１００は、“ｎ_ｃｏｐｙ_ｍａｘ”の値をｎ_ｃｏｐｙ_ｍａｘ＝ｎ_ｅｘｅｓｓ−ｎ_ｃｏｐｙに設定する（Ｓ６０２）。
【０１４１】
ステップＳ６０２の処理が行われると、管理装置１００は、フォールド処理を実行する（Ｓ６０４）。ここで、管理装置１００は、フォールド処理として例えば図１６に示す処理を行う。
【０１４２】
ステップＳ６０４の処理が行われると、管理装置１００は、“ｎ_ｃｏｐｙ”の値を、ｎ_ｃｏｐｙ＝ｎ_ｃｏｐｙ＋（フォールド処理においてコピーされた物理ＴＵ数）に更新する（Ｓ６０６）。
【０１４３】
ステップＳ６０６の処理が行われると、管理装置１００は、ｎ_ｃｏｐｙ＝ｎ_ｅｘｅｓｓであるか否かを判定する（Ｓ６０８）。ステップＳ６０８においてｎ_ｃｏｐｙ＝ｎ_ｅｘｅｓｓであると判定されない場合には、管理装置１００は、ステップＳ６０２からの処理を繰り返す。
【０１４４】
また、ステップＳ６０８においてｎ_ｃｏｐｙ＝ｎ_ｅｘｅｓｓであると判定された場合には、管理装置１００は、第２のマルチフォールド処理を終了する。
【０１４５】
管理装置１００は、例えば図１７に示す処理を行うことによって、第２のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第２のマルチフォールド処理が、図１７に示す例に限られないことは、言うまでもない。
【０１４６】
再度図１４を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップＳ３０２において１ブロックのサイズを超えたと判定されない場合には、管理装置１００は、マルチフォールド処理を終了する。
【０１４７】
管理装置１００は、例えば図１４に示す処理を行うことによって、マルチフォールド処理を実現する。なお、本発明の実施形態に係るマルチフォールド処理は、図１４に示す例に限られない。例えば、管理装置１００は、マルチフォールド処理として、図１５に示す第１のマルチフォールド処理のみを行ってもよい。
【０１４８】
再度図１２を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップＳ１０６においてマルチフォールド処理が終了すると、管理装置１００は、管理方法に係る処理を終了する。
【０１４９】
管理装置１００は、例えば図１２に示す処理を行うことによって、上述した本発明の実施形態に係る管理方法を実現することができる。したがって、管理装置１００は、例えば図１２に示す処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理方法に係る処理が、図１２に示す例に限られないことは、言うまでもない。
【０１５０】
（本発明の実施形態に係る管理装置）
次に、上述した本発明の実施形態に係る管理方法に係る処理を行うことが可能な、本発明の実施形態に係る管理装置１００の構成について説明する。
【０１５１】
図１８は、本発明の実施形態に係る管理装置１００の構成の一例を示すブロック図である。管理装置１００は、例えば、不揮発性メモリ１０２と、制御部１０４とを備える。
【０１５２】
また、管理装置１００は、例えば、ＲＯＭ（Read  Only  Memory。図示せず）や、ＲＡＭ（Random  Access  Memory。図示せず）、ユーザが操作可能な操作部（図示せず）、様々な画面を表示画面に表示する表示部（図示せず）、外部装置と通信を行うための通信部（図示せず）などを備えていてもよい。管理装置１００は、例えば、データの伝送路としてのバス（bus）により上記各構成要素間を接続する。
【０１５３】
ＲＯＭ（図示せず）は、制御部１０４が使用するプログラムや演算パラメータなどの制御用データを記憶する。ＲＡＭ（図示せず）は、制御部１０４により実行されるプログラムなどを一時的に記憶する。操作部（図示せず）としては、例えば後述する操作デバイスが挙げられ、表示部（図示せず）としては、例えば後述する表示デバイスが挙げられる。また、通信部（図示せず）としては、例えば後述する通信インタフェースが挙げられる。
【０１５４】
〔管理装置１００のハードウェア構成例〕
図１９は、本発明の実施形態に係る管理装置１００のハードウェア構成の一例を示す説明図である。図１９を参照すると、管理装置１００は、例えば、ＭＰＵ１５０と、ＲＯＭ１５２と、ＲＡＭ１５４と、記録媒体１５６と、入出力インタフェース１５８と、操作入力デバイス１６０と、表示デバイス１６２と、通信インタフェース１６４とを備える。また、管理装置１００は、例えば、データの伝送路としてのバス１６６で各構成要素間を接続する。
【０１５５】
ＭＰＵ１５０は、ＭＰＵ（Micro  Processing  Unit）や、制御機能などの各種機能を実現するための各種回路が集積された集積回路などで構成され、管理装置１００全体を制御する制御部１０４として機能する。また、ＭＰＵ１５０は、管理装置１００において、後述する判定部１１０、および管理部１１２としての役目を果たすこともできる。
【０１５６】
ＲＯＭ１５２は、例えばＭＰＵ１５０が使用するプログラムや演算パラメータなどの制御用データを記憶し、また、ＲＡＭ１５４は、例えばＭＰＵ１５０により実行されるプログラムなどを一次的に記憶する。
【０１５７】
記録媒体１５６は、管理装置１００における記憶手段であり、不揮発性メモリ１０２として機能する。記録媒体１５６には、例えば、アプリケーションや様々なデータなどが記憶される。ここで、記録媒体１５６としては、例えば、フラッシュメモリなどが挙げられる。また、記録媒体１５６は、管理装置１００から着脱可能であってもよい。
【０１５８】
入出力インタフェース１５８は、例えば、操作入力デバイス１６０や、表示デバイス１６２を接続する。操作入力デバイス１６０は、操作部（図示せず）として機能し、また、表示デバイス１６２は、表示部（図示せず）として機能する。ここで、入出力インタフェース１６０としては、例えば、ＵＳＢ（Universal  Serial  Bus）端子や、ＤＶＩ（Digital  Visual  Interface）端子、ＨＤＭＩ（High-Definition  Multimedia  Interface）端子、各種処理回路などが挙げられる。また、操作入力デバイス１６０は、例えば、管理装置１００上に備えられ、管理装置１００の内部で入出力インタフェース１５８と接続される。操作入力デバイス１６０としては、例えば、ボタン、方向キー、ジョグダイヤルなどの回転型セレクター、あるいは、これらの組み合わせなどが挙げられる。また、表示デバイス１６２は、例えば、管理装置１００上に備えられ、管理装置１００の内部で入出力インタフェース１５８と接続される。表示デバイス１６２としては、例えば、液晶ディスプレイ（Liquid  Crystal  Display；ＬＣＤ）や有機ＥＬディスプレイ（organic  ElectroLuminescence  display。または、ＯＬＥＤディスプレイ（Organic  Light  Emitting  Diode  display）ともよばれる。）などが挙げられる。なお、入出力インタフェース１５８が、管理装置１００の外部装置としての操作入力デバイス（例えば、キーボードやマウスなど）や表示デバイス（例えば、外部ディスプレイなど）と接続することも可能であることは、言うまでもない。また、表示デバイス１６２は、例えばタッチスクリーンなどのように、表示とユーザ操作とが可能なデバイスであってもよい。
【０１５９】
通信インタフェース１６４は、管理装置１００が備える通信手段であり、ネットワークを介して（あるいは、直接的に）外部装置と無線／有線で通信を行うための通信部（図示せず）として機能する。ここで、通信インタフェース１６４としては、例えば、通信アンテナおよびＲＦ（Radio  Frequency）回路（無線通信）や、ＬＡＮ端子および送受信回路（有線通信）などが挙げられる。なお、本発明の実施形態に係る通信インタフェース１６４は、上記に限られず、例えば、ネットワークに対応する構成をとることができる。
【０１６０】
管理装置１００は、例えば図１９に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。なお、本発明の実施形態に係る管理装置１００のハードウェア構成は、図１９に示す構成に限られない。例えば、管理装置１００は、本発明の実施形態に係る管理方法に係る処理を行う機能（例えば、後述する判定部１１０および管理部１１２が有する機能）を実現するためのＩＣ（Integrated  Circuit）であってもよい。
【０１６１】
再度図１８を参照して、管理装置１００の構成の一例について説明する。不揮発性メモリ１０２は、管理装置１００が備える記憶手段である。ここで、不揮発性メモリ１０２としては、例えば、フラッシュメモリなどが挙げられる。不揮発性メモリ１０２は、制御部１０４（より具体的には、後述する判定部１１０、および管理部１１２）によって、データの書き込み、読み出し、消去などが管理される。
【０１６２】
制御部１０４は、例えば、ＭＰＵなどで構成され、管理装置１００全体を制御する役目を果たす。また、制御部１０４は、判定部１１０と、管理部１１２とを備え、本発明の実施形態に係る管理方法に係る処理を主導的に行う役目を果たす。
【０１６３】
判定部１１０は、上記（１）の処理（開始条件判定処理）を主導的に行う役目を果たす。より具体的には、判定部１１０は、フォールド処理を開始するための開始条件を満たすか否かを判定する。そして、判定部１１０は、当該開始条件を満たすと判定した場合に、例えばフォールド処理を開始させるための処理開始要求（一種のトリガ）を管理部１１２へ伝達する。
【０１６４】
管理部１１２は、上記（２）の処理（フォールド処理）を主導的に行う役目を果たす。より具体的には、管理部１１２は、例えば、上記処理開始要求が伝達された場合にフォールド処理を選択的に開始する。また、管理部１１２は、例えば、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。また、管理部１１２は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ（ブロックのサイズを基準とする所定のサイズの一例）以上となるまで、フォールド処理を繰り返す。
【０１６５】
制御部１０４は、例えば、判定部１１０、および管理部１１２を備えることによって、上記（１）の処理（開始条件判定処理）、（２）の処理（フォールド処理）を行う。したがって、制御部１０４は、例えば、判定部１１０、および管理部１１２を備えることによって、上述した本発明の実施形態に係る管理方法に係る処理を実現することができるので、不揮発性メモリ１０２における空き領域の確保の効率化を図ることができる。
【０１６６】
なお、本発明の実施形態に係る制御部１０４の構成は、図１８に示す例に限られない。例えば、本発明の実施形態に係る制御部１０４は、判定部１１０を備えない構成をとることもできる。上記の構成の場合であっても、本発明の実施形態に係る管理装置１００は、例えば操作部（図示せず）から伝達される、フォールド処理の開始を要求する操作信号に基づいて、上記（２）の処理（フォールド処理）を行うことが可能である。
【０１６７】
管理装置１００は、例えば図１８に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。したがって、管理装置１００は、不揮発性メモリ１０２における空き領域の確保の効率化を図ることができる。
【０１６８】
なお、本発明の実施形態に係る管理装置１００の構成は、図１８に示す構成に限られない。例えば、本発明の実施形態に係る管理装置１００は、不揮発性メモリ１０２を備えず、有線／無線で接続された外部装置が備える不揮発性メモリにおけるデータの書き込み、読み出し、消去などを管理する構成であってもよい。上記の構成の場合であっても、本発明の実施形態に係る管理装置１００は、外部装置が備える不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【０１６９】
以上のように、本発明の実施形態に係る管理装置１００は、従来の技術がフォールド処理を１回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行う（マルチフォールド処理）。ここで、不揮発性メモリを使用する側が、例えばＦＡＴシステムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン（書き換え順序）で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。管理装置１００がマルチフォールド処理を行うことによって、上記のように将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行ったブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置１００は、例えば図６に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。
【０１７０】
また、管理装置１００は、不揮発性メモリの空き領域をより効率的に確保することができるので、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、ＮＡＮＤフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【０１７１】
また、管理装置１００は、データの書き込みに係る条件を含む開始条件を満たしたときにフォールド処理を行うので、マルチフォールド処理を、例えば、データの書き込みを行う際に分散して行うことが可能である。よって、管理装置１００は、バックグラウンドの処理としてフォールド処理を行わなくてもよいので、例えば、バックグラウンドの処理としてフォールド処理が突然行われることによる他の処理への影響（例えば処理パフォーマンスの低下など）を防止することができる。
【０１７２】
さらに、管理装置１００は、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと（言い換えれば、システムがいわゆるアイドル状態にあること）を開始条件とすることが可能である。よって、上記の場合には、管理装置１００は、システムのアイドル状態を有効に活用することができる。
【０１７３】
以上、本発明の実施形態として管理装置１００を挙げて説明したが、本発明の実施形態は、かかる形態に限られない。本発明の実施形態は、例えば、不揮発性メモリを用いる記憶装置、ＰＣ（Personal  Computer）やサーバなどのコンピュータ、テレビ受像機などの表示装置、携帯電話などの携帯型通信装置、映像／音楽再生装置（または映像／音楽記録再生装置）、ゲーム機など、様々な機器に適用することができる。また、本発明の実施形態は、例えば、上記のような様々な機器に組み込まれる記録媒体の制御ＩＣに適用することもできる。
【０１７４】
（本発明の実施形態に係るプログラム）
コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム（例えば、上記（１）の処理（開始条件判定処理）および（２）の処理（フォールド処理）や、上記（２）の処理（フォールド処理）など、本発明の実施形態に係る管理方法に係る処理を実現するためのプログラム）によって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラムによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、ＮＡＮＤフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【０１７５】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１７６】
例えば、本発明の実施形態に係る管理装置は、図１８に示す判定部１１０、および管理部１１２を個別に備える（例えば、それぞれを個別の処理回路で実現する）ことができる。
【０１７７】
また、上記では、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム（コンピュータプログラム）が提供されることを示したが、本発明の実施形態は、さらに、上記プログラムをそれぞれ記憶させた記録媒体も併せて提供することができる。
【０１７８】
上述した構成は、本発明の実施形態の一例を示すものであり、当然に、本発明の技術的範囲に属するものである。
【符号の説明】
【０１７９】
１０、１００    管理装置
１０２    不揮発性メモリ
１０４    制御部
１１０    判定部
１１２    管理部
【図１】
2012133655.tif 000003
【図２】
2012133655.tif 000004
【図３】
2012133655.tif 000005
【図４】
2012133655.tif 000006
【図５】
2012133655.tif 000007
【図６】
2012133655.tif 000008
【図７】
2012133655.tif 000009
【図８】
2012133655.tif 000010
【図９】
2012133655.tif 000011
【図１０】
2012133655.tif 000012
【図１１】
2012133655.tif 000013
【図１２】
2012133655.tif 000014
【図１３】
2012133655.tif 000015
【図１４】
2012133655.tif 000016
【図１５】
2012133655.tif 000017
【図１６】
2012133655.tif 000018
【図１７】
2012133655.tif 000019
【図１８】
2012133655.tif 000020
【図１９】
2012133655.tif 000021