管理装置、管理方法、およびプログラム
【課題】不揮発性メモリにおける空き領域の確保の効率化を図ることが可能な管理装置、管理方法、およびプログラムを提供する。
【解決手段】不揮発性メモリにおけるデータの書き込み、読み出し、消去を、ブロックのサイズの整数分の1かつページのサイズの整数倍のトランスレーションユニット(TU)単位で論理アドレス−物理アドレス変換を行うことによって管理し、未書き込みの物理TUを増やすフォールド処理を行う管理部を備え、管理部は、フォールド処理を開始した場合には、書き込み済みの有効な物理TUのデータを、未書き込みの物理TUがあるブロックのうちの、先頭の物理TUが未書き込みであるブロックへとコピーし、フォールド処理によって増えた未書き込みの物理TUのサイズがブロックのサイズ以上となるまで、フォールド処理を繰り返す。
【解決手段】不揮発性メモリにおけるデータの書き込み、読み出し、消去を、ブロックのサイズの整数分の1かつページのサイズの整数倍のトランスレーションユニット(TU)単位で論理アドレス−物理アドレス変換を行うことによって管理し、未書き込みの物理TUを増やすフォールド処理を行う管理部を備え、管理部は、フォールド処理を開始した場合には、書き込み済みの有効な物理TUのデータを、未書き込みの物理TUがあるブロックのうちの、先頭の物理TUが未書き込みであるブロックへとコピーし、フォールド処理によって増えた未書き込みの物理TUのサイズがブロックのサイズ以上となるまで、フォールド処理を繰り返す。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、管理装置、管理方法、およびプログラムに関する。
【背景技術】
【0002】
近年、NANDフラッシュメモリ(flash memory)などのような電気的にデータの書き込み、読み出し、消去が可能な不揮発性メモリ(nonvolatile memory)の大容量化が進んでいる。ここで、NANDフラッシュメモリのような上記不揮発性メモリにおける書き込みは、各ビットを“1”から“0”へと一方向に書き換えることによって行われる。そのため、上記不揮発性メモリにおいて新たにデータを書き込む場合には、一旦、消去を行って全てのビットを“1”にした上で、書き込みを行う必要がある。また、上記不揮発性メモリにおいては、データの書き込み/読み出しの最小単位は「ページ」であり、消去の最小単位は、複数のページが集まった「ブロック」である。上記のように、消去の最小単位である「ブロック」のサイズは、書き込みの最小単位である「ページ」のサイズよりも例えば数十倍程大きいので、上記不揮発性メモリにおけるデータの書き換えをより効率的に行うためには、何らかの仕組みが必要となる。
【0003】
このような中、不揮発性メモリにおけるデータの書き換えの効率化を図るための技術が開発されている。ブロックサイズの整数分の1かつページサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行って、不揮発性メモリのアクセス管理を行い、ブロックの内容のうち、使用中の物理トランスレーションユニットを、別の未使用の物理トランスレーションユニットがあるブロックにコピーし、元のブロックを消去することにより、元のブロックに含まれていた無効の物理トランスレーションユニットの数だけ、新たに未使用の物理トランスレーションユニットを増やす技術としては、例えば、特許文献1が挙げられる。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2009−116601号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
不揮発性メモリにおけるデータの書き換えの効率化を図るための従来の技術(以下、単に「従来の技術」と示す。)は、不揮発性メモリにおけるあるブロックの物理トランスレーションユニットのデータをコピーし、当該ブロック(コピー元のブロック)を消去する。よって、従来の技術を用いる場合には、ブロック内に、書き込み済みの無効な物理トランスレーションユニット(無効なデータが記録されている物理トランスレーションユニット)が多ければ多いほど、データを書き込み可能な空き容量を増やすことが可能である。
【0006】
ここで、空き領域を効率的に確保することは、例えば、不揮発性メモリをデータの記録媒体として使用するユーザ(以下、単に「ユーザ」と示す場合がある。)からみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化に寄与する。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていない。
【0007】
本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、不揮発性メモリにおける空き領域の確保の効率化を図ることが可能な、新規かつ改良された管理装置、管理方法、およびプログラムを提供することにある。
【課題を解決するための手段】
【0008】
上記目的を達成するために、本発明の第1の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、上記管理部は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理装置が提供される。
【0009】
かかる構成により、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0010】
また、上記管理部は、上記フォールド処理を行った後、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、上記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーしてもよい。
【0011】
また、上記管理部における上記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、上記管理部は、上記判定部において上記開始条件を満たすと判定された場合に、選択的に上記フォールド処理を行ってもよい。
【0012】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている上記ブロックの数が所定の閾値より大きいまたは上記閾値以上であることを上記開始条件として、上記判定を行ってもよい。
【0013】
また、上記判定部は、さらに、上記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを上記開始条件として、上記判定を行ってもよい。
【0014】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない上記ブロックの数が所定の閾値より小さいまたは上記閾値以下であることを上記開始条件として、上記判定を行ってもよい。
【0015】
また、上記管理部は、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、上記ブロックのサイズの所定の整数倍以上となるまで上記フォールド処理を繰り返してもよい。
【0016】
また、上記管理部は、上記不揮発性メモリにおける上記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、上記フォールド処理におけるコピー元のブロックとして選択してもよい。
【0017】
また、上記管理部は、上記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが上記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、上記フォールド処理の対象から除外してもよい。
【0018】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【0019】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【0020】
また、上記管理部は、上記フォールド処理を行う場合には、繰り返し行われる上記フォールド処理においてコピー元となる全てのブロックにおける上記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した上記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した上記物理トランスレーションユニットのデータをコピーしてもよい。
【0021】
上記不揮発性メモリをさらに備えていてもよい。
【0022】
上記目的を達成するために、本発明の第2の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップとを有し、上記管理するステップでは、上記判定するステップにおいて上記開始条件を満たすと判定された場合に、上記フォールド処理が選択的に行われ、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理方法が提供される。
【0023】
かかる方法を用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0024】
上記目的を達成するために、本発明の第3の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、上記管理手段は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、プログラムが提供される。
【0025】
かかるプログラムを用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【発明の効果】
【0026】
本発明によれば、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【図面の簡単な説明】
【0027】
【図1】不揮発性メモリにおける前提を説明するための説明図である。
【図2】不揮発性メモリにおける前提を説明するための説明図である。
【図3】従来の技術における問題を説明するための説明図である。
【図4】従来の技術における問題を説明するための説明図である。
【図5】従来の技術における問題を説明するための説明図である。
【図6】従来の技術における問題を説明するための説明図である。
【図7】本発明の実施形態に係る管理装置がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。
【図8】本発明の実施形態に係る管理装置におけるマルチフォールド処理の一例を示す説明図である。
【図9】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図10】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図11】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図12】本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。
【図13】本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【図14】本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【図15】本発明の実施形態に係る第1のマルチフォールド処理の一例を示す説明図である。
【図16】本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【図17】本発明の実施形態に係る第2のマルチフォールド処理の一例を示す説明図である。
【図18】本発明の実施形態に係る管理装置の構成の一例を示すブロック図である。
【図19】本発明の実施形態に係る管理装置のハードウェア構成の一例を示す説明図である。
【発明を実施するための形態】
【0028】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書および図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【0029】
また、以下では、下記に示す順序で説明を行う。
1.本発明の実施形態に係る管理方法
2.本発明の実施形態に係る管理装置
3.本発明の実施形態に係るプログラム
【0030】
(本発明の実施形態に係る管理方法)
本発明の実施形態に係る管理装置(以下、「管理装置100」と示す場合がある。)の構成について説明する前に、本発明の実施形態に係る不揮発性メモリの管理方法について説明する。以下では、管理装置100が、本発明の実施形態に係る管理方法に係る処理を行うものとして説明する。また、以下では、本発明の実施形態に係る管理装置100の管理対象の不揮発性メモリが、NANDフラッシュメモリである場合を例に挙げて説明する。なお、本発明の実施形態に係る管理装置100の管理対象の不揮発性メモリが、NAND型のフラッシュメモリに限られないことは、言うまでもない。
【0031】
[前提]
本発明の実施形態に係る管理方法に係る処理について説明する前に、管理装置100の管理対象の不揮発性メモリにおける前提について説明する。
【0032】
図1、図2は、不揮発性メモリにおける前提を説明するための説明図である。図1に示すように、不揮発性メモリは、データの書き込み/読み出しの最小単位である「ページ」と、複数のページからなる消去の最小単位である「ブロック」とで構成される。
【0033】
また、不揮発性メモリには、製造時などの段階において「不良ブロック」とよばれるデータの記録ができないブロック(使用できないブロック)が存在する。そのため、管理装置100は、不揮発性メモリの不良ブロックを避けて、データの読み書きを行わなければならない。
【0034】
また、不揮発性メモリの各ブロックにおいては、それぞれのブロックに含まれるページに番号(ページを識別するための番号)が付されており、NANDフラッシュメモリのような不揮発性メモリの多くは、図2のAに示すように、当該番号が小さいページの順にデータが書き込まれる。そして、NANDフラッシュメモリのような不揮発性メモリの多くは、例えば図2のBに示すように、ランダムな順番でページにデータが書き込まれることは、禁止される。
【0035】
また、不揮発性メモリの各ブロックには、書き換えの回数に上限(いわゆる寿命)があることから、不揮発性メモリの長寿命化を図るためには、特定のブロックに書き換えが偏らないようにする必要がある。
【0036】
不揮発性メモリは、例えば上記のような特徴を有する。ここで、ユーザの利便性を損ねないためには、例えば、上記不良ブロックや消去の処理をユーザに意識させないことが望ましい。そのため、不揮発性メモリの管理には、例えば、不揮発性メモリを使用する側(例えばファイルシステム)からの要求を解釈して、書き込み操作、読み出し操作など、不揮発性メモリを操作するための命令に変換する論理−物理変換層(レイヤー)が用いられる。
【0037】
[従来の技術における問題]
次に、従来の技術における問題について、より具体的に説明する。図3〜図6は、従来の技術における問題を説明するための説明図である。
【0038】
上述したように、従来の技術では、ブロックのサイズよりも小さい単位であるトランスレーションユニット(以下、「TU」と示す場合がある。)で論理アドレス−物理アドレス変換を行っている。ここで、図3に示すように、トランスレーションユニットは、ブロックのサイズの整数分の1のサイズであり、かつ、ページのサイズの整数倍のサイズである。すなわち、ブロックは、複数のトランスレーションユニットを含み、トランスレーションユニットは、複数のトランスレーションユニットを含む。
【0039】
また、従来の技術では、トランスレーションユニットを、不揮発性メモリ上の実際のトランスレーションユニット(以下、「物理トランスレーションユニット」または「物理TU」と示す場合がある。)と、アドレス変換されて不揮発性メモリを使用する側に提供されるトランスレーションユニット(以下、「論理トランスレーションユニット」または「論理TU」、「LTU」と示す場合がある。)とに分類する。上記によって、従来の技術では、例えば、ファイルシステムにおける読み書きの単位と、トランスレーションユニットを一致させるなど、データの読み書きのサイズを柔軟に設定することが可能となる。
【0040】
また、従来の技術におけるデータの書き換えは、図4に示すように、データが記録されていない物理トランスレーションユニットにデータを追記することによって行われる。より具体的には、書き換え前のデータが記録されていた物理トランスレーションユニットP1を無効な状態へと更新し(図4のC)、書き換えを行う新たなデータを、データが記録されていない物理トランスレーションユニットP2に書き込むことによって(図4のD)、データの書き換えが行われる。上記によって、不揮発性メモリでは、図4の物理トランスレーションユニットP2に示すように、最新のデータが記録されてる状態の物理トランスレーションユニット(以下、「書き込み済みの有効な物理トランスレーションユニット」と示す場合がある。)と、消去対象の古いデータが記録されている状態の物理トランスレーションユニット(以下、「書き込み済みの無効な物理トランスレーションユニット」と示す場合がある。)とが生じる。
【0041】
以下では、物理トランスレーションユニットにおいて、最新のデータが記録されてる状態を「INUSE」と示し、消去対象の古いデータが記録されている状態を「DIRTY」と示す場合がある。また、以下では、データの記録がされていない物理トランスレーションユニットを「未書き込みの物理トランスレーションユニット」と示す場合があり、物理トランスレーションユニットにおいて消去後に(または初期時に)データが記録されていない状態を「CLEAN」と示す場合がある。
【0042】
上述したように、NANDフラッシュメモリのような不揮発性メモリは、ブロック単位でしかデータの消去を行うことができない。そのため、ブロックを構成する一部の物理トランスレーションユニットに、例えば図4の物理トランスレーションユニットP1に示すような“書き込み済みの無効な物理トランスレーションユニット”があったとしても、当該ブロック内に“書き込み済みの有効な物理トランスレーションユニット”が存在した場合には、消去を行うことができない。よって、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける“書き込み済みの無効な物理トランスレーションユニット”の数が増え、また、データの書き込みが可能な物理トランスレーションユニット(例えば、CLEANな物理トランスレーションユニット)の数が減ってしまう。つまり、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける空き領域が減ることとなる。
【0043】
そこで、従来の技術では、データの書き込みが可能な物理トランスレーションユニットの数を増やして、不揮発性メモリにおける空き領域を確保するために、フォールド処理を行う。ここで、フォールド処理とは、ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす処理である。
【0044】
図5は、フォールド処理の概要を示している。図5(a)はフォールド処理前のブロックB1、およびブロックB2状態を示しており、図5(b)はフォールド処理中のブロックB1、およびブロックB2状態を示している。そして、図5(c)はフォールド処理後のブロックB1、およびブロックB2状態を示している。フォールド処理では、コピー元のブロックB1の“書き込み済みの有効な物理トランスレーションユニット”がコピー先のブロックB2にコピーされ、コピーされた物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”に更新される(図5(b))。そして、フォールド処理では、コピー元のブロックB1を消去する(図5(c))。図5に示すように、フォールド処理が行われることによって“未書き込みの物理トランスレーションユニット”が増えていることが分かる。よって、フォールド処理が行われることによって、不揮発性メモリにおける空き領域を増やすことが可能となる。
【0045】
従来の技術は、例えば、不揮発性メモリデータが書き込まれた後、データが記録されているブロック(INUSE、またはDIRTYの物理トランスレーションユニットを含むブロック。以下、「使用中のブロック」と示す場合がある。)の総数が閾値を超えた以上となったとき(または、閾値以上となったとき)に、上記フォールド処理を1回だけ行う。よって、従来の技術を用いる場合には、不揮発性メモリにおける空き領域を増やすことが可能である。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていないので、効率的に不揮発性メモリの空き領域を確保することはできない。
【0046】
図6は、従来の技術に係るフォールド処理の一例を示しており、不揮発性メモリの各ブロックの状態を時系列(図6(a)〜図6(h))で示している。ここで、図6は、使用中のブロックが6(閾値の一例)より大きくなったとき(開始条件)にフォールド処理が行われ、フォールド処理が1回で終了する(停止条件)場合を示している。以下では、図6に示す処理を、従来の技術を用いる管理装置(以下、「従来の管理装置10」と示す場合がある。)が行うものとして説明する。
【0047】
図6(a)の状態においてLTU3の書き換えが行われると(図6(b))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(c))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0048】
また、図6(c)の状態においてLTU4の書き換えが行われると(図6(d))、従来の管理装置10は、上記開始条件を満たすか否かを判定する。図6(d)の状態では、上記開始条件は満たされていないので、従来の管理装置10は、フォールド処理を行わない。
【0049】
図6(d)の状態においてLTU8の書き換えが行われると(図6(e))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(f))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0050】
そして、図6(f)の状態においてLTU9の書き換えが行われると(図6(g))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(h))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0051】
図6(a)〜図6(h)に示すように、従来の管理装置10は、開始条件を満たすごとにフォールド処理を1回だけ行う。その結果、図6(h)に示すように、書き換えが行われたLTU3、LTU4、LTU8、およびLTU9は、複数のブロックに分散して書き込まれることとなる。ここで、不揮発性メモリを使用する側が、例えばFAT(File Allocation Table)システムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン(書き換え順序)で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。また、例えば、論理トランスレーションユニットのサイズとFATのクラスタのサイズとが同一である場合などには、上記の可能性はより高くなる。なお、本発明の実施形態に係るファイルシステムは、FATに限られず、例えば、NTFS(NT File System)やext4(fourth extended file system)などが挙げられる。
【0052】
ここで、例えば、不揮発性メモリに対するデータの書き換えが、図6に示す論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで行われた場合には、図6(h)に示すLTU3、LTU4、LTU8、およびLTU9に対応する物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。
【0053】
しかしながら、図6(h)に示すように、LTU3、LTU4、LTU8、およびLTU9は、複数のブロックに分散して書き込まれているので、不揮発性メモリにおいて“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在することは期待できない。したがって、“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在しない状態でフォールド処理を行ったとしても、不揮発性メモリの空き領域を十分に確保することができないので、従来の技術を用いたとしても、効率的に不揮発性メモリの空き領域を確保することはできるとは限らない。
【0054】
[本発明の実施形態に係る管理方法の概要]
本発明の実施形態に係る管理装置100は、従来の技術と同様に、不揮発性メモリにおけるデータの書き込み、読み出し、消去を、トランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理する。
【0055】
また、管理装置100は、従来の技術と同様に、フォールド処理を行うことによって不揮発性メモリの空き領域を確保するが、管理装置100は、従来の技術がフォールド処理を1回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。以下では、本発明の実施形態に係るフォールド処理を、フォールド処理を複数回繰り返し行いうることから、「マルチフォールド処理」と示す場合がある。ここで、本発明の実施形態に係る所定の停止条件としては、例えば、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ以上となるまで”や、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズの所定の整数倍以上となるまで”などが挙げられる。
【0056】
また、管理装置100は、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。
【0057】
図7は、本発明の実施形態に係る管理装置100がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。管理装置100は、データが記録されていないブロックを選択し、当該ブロックにおける先頭の物理トランスレーションユニット(付された番号が最も小さい物理トランスレーションユニット)から順に、データの書き込みを行う。そして、管理装置100は、データの書き込みを行っている書き込み対象のブロック(以下、「書き込み対象ブロック」または「PTUブロック」と示す場合がある。)を構成する全ての物理トランスレーションユニットの書き込みが完了したときに、データが記録されていないブロックを新たに選択して、当該ブロックにデータを書き込む。以下では、データの書き込みの対象となる物理トランスレーションユニットを「PTU」と示す場合がある。また、以下では、データの書き込みを行う各時点において、データの書き込みの対象となっている物理トランスレーションユニットを「書き込み対象現在物理トランスレーションユニット」または「書き込み対象PTU」と示す場合がある。つまり、本発明の実施形態に係る書き込み対象ブロックとは、書き込み対象現在物理トランスレーションユニットが含まれるブロックを指すこととなる。
【0058】
より具体的には、管理装置100は、例えば下記の(1)の処理(開始条件判定処理)、および(2)の処理(フォールド処理)を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。
【0059】
(1)開始条件判定処理
管理装置100は、フォールド処理を開始するための開始条件を満たすか否かを判定する。
【0060】
ここで、本発明の実施形態に係る開始条件としては、例えば、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロックの数が所定の閾値より大きい(または所定の閾値以上である。以下、同様とする。)ことが挙げられる。直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであることを開始条件のひとつとすることによって、管理装置100は、図7に示すように、“書き込み済みの有効な物理トランスレーションユニット”のデータを、ブロックの先頭の物理トランスレーションユニットへとコピーすることが可能となる。また、データが書き込まれているブロックの数が所定の閾値より大きいことを開始条件のひとつとすることによって、管理装置100は、不揮発性メモリの空き容量が一定値未満(または、一定値以下)となったときに、空き容量の確保を行うことができる。
【0061】
また、管理装置100は、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていないブロックの数が所定の閾値より小さい(または閾値以下である。以下、同様とする。)ことを開始条件とすることもできる。データが書き込まれていないブロックの数が所定の閾値より小さいことを開始条件のひとつとすることによって、例えば、不揮発性メモリにおいて不良ブロックが増えた結果データを記録可能な絶対容量が小さくなったとしても、空き容量の確保を行うことが可能となる。
【0062】
なお、本発明の実施形態に係る開始条件は、上記に限られない。例えば、管理装置100は、上記2つの開始条件の双方を組み合わせた条件(上記2つの開始条件の論理和)を、開始条件することが可能である。また、管理装置100は、上述した開始条件それぞれに対して、さらに、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと(言い換えれば、システムがいわゆるアイドル状態にあること)を、条件として加えてもよい。不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを開始条件のひとつとすることによって、管理装置100は、データの書き込み、読み出し、消去に係る処理と、フォールド処理とが同時期に行われることを回避することが可能となる。よって、管理装置100は、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0063】
(2)フォールド処理
上記(1)の処理(開始条件判定処理)において開始条件を満たすと判定された場合には、管理装置100は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ(合計サイズ)が、ブロックのサイズを基準とする所定のサイズ以上となるまで、フォールド処理を繰り返す(マルチフォールド処理)。
【0064】
ここで、「フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ(合計サイズ)が、ブロックのサイズを基準とする所定のサイズ以上となる」ことは、(2)の処理(フォールド処理)における処理の停止条件の一例である。また、本発明の実施形態に係るブロックのサイズを基準とする所定のサイズとしては、例えば、ブロックのサイズや、ブロックのサイズの整数倍のサイズが挙げられる。本発明の実施形態に係るブロックのサイズを基準とする所定のサイズは、例えば、予め規定されたサイズであってもよいし、ユーザ操作に基づいて適宜設定されたサイズであってもよい。また、本発明の実施形態に係るサイズは、例えば[Byte]、[KByte]で表されるが、本発明の実施形態に係るサイズは、上記に限られない。
【0065】
また、管理装置100は、フォールド処理を行った後、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れるか否かを判定してもよい。上記判定を行った場合において割り切れないと判定したときには、管理装置100は、端数のサイズに対応する“未書き込みの物理トランスレーションユニット”のサイズ分、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。管理装置100が、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、(2)の処理(フォールド処理)後の不揮発性メモリにおいては、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットとなる。よって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、フォールド処理によりコピーするデータとユーザの書き換えデータとを、ブロック間で分離することができ、その結果、ユーザのアクセスパターンがブロック内に保存される。したがって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、より効率的に空き容量の確保を行うことが可能となる。
【0066】
管理装置100は、上記のように停止条件を満たすまでフォールド処理を繰り返す。ここで、本発明の実施形態に係る管理装置100におけるフォールド処理について説明する。管理装置100は、フォールド処理として、ブロックの内容のうち、“書き込み済みの有効な物理トランスレーションユニット”のデータを、“未書き込みの物理トランスレーションユニット”があるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた“書き込み済みの無効な物理トランスレーションユニット”の数分、“未書き込みの物理トランスレーションユニット”を増やす処理を行う。つまり、管理装置100は、基本的に従来の技術と同様の処理を、フォールド処理として行う。
【0067】
また、管理装置100は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド処理におけるコピー元のブロックとして選択する。上記のようにフォールド処理におけるコピー元のブロックを選択することによって、フォールド処理後に増える“未書き込みの物理トランスレーションユニット”の数をより増やすことが可能となるので、管理装置100は、不揮発性メモリの空き容量の確保をより効率的に行うことができる。
【0068】
なお、管理装置100におけるブロックの選択方法は、上記に限られない。例えば、管理装置100は、フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外してもよい。管理装置100は、上記のように特定のブロックを除外した上で、ブロックを選択することによって、不揮発性メモリの空き容量の確保をより効率的に行うことが可能となる。なお、上記選択方法を用いた場合の効果については、後述する。
【0069】
また、管理装置100は、例えば、不揮発性メモリにおけるブロックの中に“書き込み済みの無効な物理トランスレーションユニット”の数が最も多いブロックが複数存在する場合には、当該ブロックの中からランダムにブロックを選択してもよい。上記のようにブロックの選択をランダムに行うことによって、不揮発性メモリの空き容量の効率的な確保に加え、不揮発性メモリの長寿命化を図ることが可能となる。
【0070】
管理装置100は、例えば上記のようにフォールド処理におけるコピー元のブロックを選択することによって、不揮発性メモリの空き容量の効率的な確保を実現する。
【0071】
また、管理装置100は、フォールド処理を行う場合において、“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番を、例えば下記の(a)〜(c)のように行う。
【0072】
(a)第1の順番
管理装置100は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。つまり、管理装置100は、ブロック何の先頭の“書き込み済みの有効な物理トランスレーションユニット”のデータから順にコピーする。第1の順番を用いることによって、例えば、過去の論理トランスレーションユニットの書き込み順序を保存することが可能となる。
【0073】
(b)第2の順番
管理装置100は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。より具体的には、管理装置100は、例えば、対応する論理トランスレーションユニットに付された番号が小さい順にソートを行い、ソートされた順番で、当該論理トランスレーションユニットに対応する“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。ここで、例えばFATファイルシステムでは、空クラスタの割り当てをクラスタ番号が小さい順に行う。よって、例えば上記クラスタ番号と論理トランスレーションユニットに付された番号とが一致している場合には、管理装置100は、不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【0074】
(c)第3の順番
管理装置100は、繰り返し行われるフォールド処理(マルチフォールド処理)においてコピー元となる全てのブロックにおける“書き込み済みの有効な物理トランスレーションユニット”を特定する。ここで、管理装置100は、例えば仮想的にマルチフォールド処理を行うことによって、上記特定を行う。そして、管理装置100は、特定した物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した物理トランスレーションユニットのデータをコピーする。上記第3の順番でコピーを行うことによって、管理装置100は、上記第2の順番でコピーを行う場合よりも、さらに不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【0075】
管理装置100は、例えば上記(a)〜(c)に示す順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。なお、本発明の実施形態に係る“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番は、上記に限られない。例えば、管理装置100は、任意の順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーすることも可能である。
【0076】
管理装置100は、(2)の処理(フォールド処理)として、例えば上記のようなフォールド処理を停止条件を満たすまで繰り返し行うこと(マルチフォールド処理を行うこと)によって、不揮発性メモリの空き容量を確保する。
【0077】
管理装置100は、例えば、上記(1)の処理(開始条件判定処理)、および(2)の処理(マルチフォールド処理)を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。なお、上記では、管理装置100が上記(1)の処理(開始条件判定処理)を行った後に、(2)の処理(フォールド処理)を行うことを示したが、管理装置100における処理は、上記に限られない。例えば、管理装置100は、上記(1)の処理(開始条件判定処理)の結果によらず、(2)の処理(フォールド処理)を行うことも可能である。上記の例としては、例えば、管理装置100が備える操作部(後述する)から伝達される操作信号や、ユーザ操作に応じてリモート・コントローラなどの外部操作装置(図示せず)から送信される外部操作信号に基づいて、(2)の処理(マルチフォールド処理)を行う場合が挙げられる。
【0078】
次に、管理装置100がマルチフォールド処理を行うことによる効果について説明する。図8は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の一例を示す説明図である。ここで、図8は、図6と同様に、不揮発性メモリの各ブロックの状態を時系列(図8(a)〜図8(g))で示している。また、図8は、マルチフォールド処理の開始条件が、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロック(使用中のブロック)の数が使用中のブロックが7(所定の閾値の一例)以上となったときである場合を示している。また、図8は、マルチフォールド処理の停止条件が、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることである場合を示している。
【0079】
図8(a)の状態においてLTU3の書き換えが行われると(図8(b))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(b)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0080】
図8(b)の状態においてLTU4の書き換えが行われると(図8(c))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(c)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0081】
図8(c)の状態においてLTU8の書き換えが行われると(図8(d))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(d)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0082】
図8(d)の状態においてLTU9の書き換えが行われると(図8(e))、管理装置100は、上記開始条件が満たされているか否かを判定する。LTU9の書き換えによって、上記開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図8(f))。
【0083】
フォールド処理を行うと、管理装置100は、上記停止条件を満たしているか否かを判定する。図8(f)の状態では、上記停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図8(g))。そして、管理装置100は、上記停止条件を満たしているか否かを判定する。
【0084】
図8(g)の状態では、1ブロックのサイズに該当するサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。よって、管理装置100は、マルチフォールド処理を終了する。
【0085】
ここで、図8(g)に示すように、マルチフォールド処理が行われることによって、書き換えを行ったLTU3、LTU4、LTU8、およびLTU9が、同一のブロックに集約されていることが分かる。ここで、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行った上記ブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置100は、図6に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。また、図8に示す例では、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合に、管理装置100は、書き換えを行った上記ブロックの消去を行えばよいので、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0086】
管理装置100は、例えば図8に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0087】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8に示す例に限られない。例えば、図8では、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズと一致する場合を示したが、当該ブロックのサイズを超えることも想定される。そこで、次に、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例として、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における例について説明する。
【0088】
図9は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。ここで、図9は、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における処理の一例を示している。また、図9は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図9(a)〜図9(d))で示している。また、図9は、管理装置100が、図8と同様の開始条件、停止条件にてフォールド処理を行う例を示している。
【0089】
図9(a)の状態においてLTU12の書き換えが行われると(図9(b))、管理装置100は、開始条件が満たされているか否かを判定する。LTU12の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図9(b))。
【0090】
フォールド処理を行うと、管理装置100は、停止条件を満たしているか否かを判定する。図9(b)の状態では、停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図9(c))。そして、管理装置100は、停止条件を満たしているか否かを判定する。
【0091】
図9(c)の状態では、1ブロックのサイズより大きなサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。また、図9(c)の状態では、図8(g)の状態と異なり、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れない。上記の場合、管理装置100は、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分(図9(c)の例では、1つの物理トランスレーションユニットのサイズ)、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”であるLTU0のデータをコピーする(図9(d))。
【0092】
図9(d)に示すように、1ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)を超えるサイズ分を、“書き込み済みの有効な物理トランスレーションユニット”のデータで埋めることによって、マルチフォールド処理後の不揮発性メモリの状態が、図8(g)と同様の状態となる。よって、管理装置100は、図9に示す処理を行う場合においても、図8に示すマルチフォールド処理と同様に、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、管理装置100は、将来的行うフォールド処理において書き換えを行った上記ブロックの消去を行えばよいので、図8に示すマルチフォールド処理と同様に、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0093】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8、図9に示す例に限られない。例えば、管理装置100は、さらにフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを基準とする所定のサイズを超えることを、停止条件として、マルチフォールド処理を行うことも可能である。
【0094】
図10は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。また、図10は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図10(a)〜図10(c))で示している。また、図10は、管理装置100が、図8と同様の開始条件にてフォールド処理を行う例を示している。
【0095】
図10(a)の状態においてLTU12の書き換えが行われると(図10(b))、管理装置100は、開始条件が満たされているか否かを判定する。LTU12の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図10(b))。
【0096】
フォールド処理を行うと、管理装置100は、さらにフォールド処理を行った場合に、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えるか否かを判定する(停止条件の判定)。ここで、管理装置100は、例えば仮想的にフォールド処理を行うことによって、上記判定を行う。ここで、図10(b)の状態において2回目のフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えてしまう(図10(c))。よって、管理装置100は、2回目のフォールド処理を行うことなく、不揮発性メモリが図10(b)の状態のときに、マルチフォールド処理を終了する。
【0097】
管理装置100が上記のような停止条件でマルチフォールド処理を行うことによって、次に書き換えられるデータが分断されることを防止することが可能となる。よって、管理装置100は、上記のような停止条件でマルチフォールド処理を行うことによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0098】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8〜図10に示す例に限られない。例えば、管理装置100は、上述したように、フォールド処理を行う場合において、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することも可能である。
【0099】
図11は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。ここで、図11は、上記のように特定のブロックを除外した上で、ブロックを選択する場合における処理の一例を示している。また、図11は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図11(a)〜図11(h))で示している。また、図11は、管理装置100が、図8と同様の開始条件、停止条件にてフォールド処理を行う例を示している。また、図11は、(i)LTU0〜LTU11の書き込み、(ii)LTU13、LTU14の書き込みの割り込み、(iii)LTU0〜LTU11の上書き、が行われる場合における処理の一例を示している。
【0100】
図11(a)は、LTU0〜LTU11が書き込まれた直後(上記(i)の直後)の不揮発性メモリの状態を示している。また、図11(b)は、図11(a)の状態においてLTU13、LTU14が書き込まれた直後(上記(ii)の直後)の不揮発性メモリの状態を示している。
【0101】
図11(b)の状態において、LTU0およびLTU1の書き込みが行われると(図11(c))、管理装置100は、開始条件が満たされているか否かを判定する。LTU0およびLTU1の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図11(d))。このとき、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック(図11における左端のブロック)を、フォールド処理の対象から除外する。図11(d)では、図11における左端から4番目のブロックがフォールド処理の対象として選択された場合を示している。
【0102】
1回目のフォールド処理を行うと、管理装置100は、停止条件を満たしているか否かを判定する。図11(d)の状態では、停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図11(e))。このとき、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック(図11における左端のブロック)を、フォールド処理の対象から除外する。図11(e)では、図11における左端から6番目のブロックがフォールド処理の対象として選択された場合を示している。
【0103】
2回目のフォールド処理を行うと、管理装置100は、上記停止条件を満たしているか否かを判定する。図11(e)の状態では、停止条件は満たされているので、管理装置100は、マルチフォールド処理を終了する。
【0104】
次に、図11(e)の状態において、LTU2およびLTU3の書き込みが行われると(図11(f))、管理装置100は、開始条件が満たされているか否かを判定する。図11(f)の状態は開始条件を満たしていないので、管理装置100は、フォールド処理を行わない。また、図11(f)に示す状態では、図11における左端のブロックに含まれる全ての物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となっているので、管理装置100は、図11における左端のブロックを消去する(図11(g))。
【0105】
また、図11(g)の状態において、LTU4およびLTU5の書き込みが行われると(図11(h))、管理装置100は、開始条件が満たされているか否かを判定する。図11(h)の状態は開始条件を満たしていないので、管理装置100は、フォールド処理を行わない。
【0106】
管理装置100は、LTU6〜LTU11についても、図11(f)〜図11(h)と同様に書き換えを行う。ここで、図11(f)〜図11(h)に示すように、管理装置100は、LTU2〜LTU5の書き換えにおいてはフォールド処理を行っておらず、消去を行うことによって、書き換えを行っている。したがって、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、不揮発性メモリの空き領域の確保の効率化を図ると共に、より効率的なデータの書き換えを実現することができる。
【0107】
また、例えばサイズが大きなファイルの上書きを行うようなケースでは、過去に行われた論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。よって、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、上記のようにサイズが大きなファイルの上書きを行うようなケースにおいても、図11に示すように、より効率的なデータの書き換えを実現することができる。
【0108】
管理装置100は、例えば図8〜図11に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理が、図8〜図11に示す例に限られないことは、言うまでもない。
【0109】
[本発明の実施形態に係る、管理方法に係る処理の具体例]
次に、上述した本発明の実施形態に係る管理方法に係る処理について、より具体的に説明する。図12は、本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。以下では、管理方法に係る処理を管理装置100が行うものとして説明する。
【0110】
管理装置100は、指定されたデータを書き込む(S100:書き込み処理)。
【0111】
〔書き込み処理の一例〕
図13は、本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【0112】
管理装置100は、直前に書き込まれた物理TUが、ブロックにおける最後の物理TUであるか否かを判定する(S200)。ステップS200においてブロックにおける最後の物理TUであると判定されない場合には、管理装置100は、上記ブロックの次のPTUを、書き込み対象PTUとして設定し(S202)、後述するステップS206からの処理を行う。
【0113】
また、ステップS200においてブロックにおける最後の物理TUであると判定された場合には、管理装置100は、ブロックにおける先頭の物理TUが“未書き込みの物理TU”であるブロックを選択し、選択したブロックの先頭の物理TUを、書き込み対象PTUとして設定する(S204)。
【0114】
ステップS202またはステップS204において書き込み対象PTUが設定されると、管理装置100は、当該書き込み対象PTUに指定されたデータを書き込む(S206)。そして、管理装置100は、論理アドレス−物理アドレス変換に係る、論理アドレス−物理アドレス変換テーブル(論物変換テーブル)および物理TU状態マップを更新する(S208)。
【0115】
管理装置100は、例えば図13に示す処理を行うことによって、データの書き込みを行う。なお、本発明の実施形態に係る書き込み処理が、図13に示す例に限られないことは、言うまでもない。
【0116】
再度図12を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップS100においてデータの書き込みが行われると、管理装置100は、フォールド処理の開始条件を満たすか否かを判定する(S102)。
【0117】
ステップS102においてフォールド処理の開始条件を満たすと判定されない場合には、管理装置100は、管理方法に係る処理を終了する。なお、本発明の実施形態に係る管理方法に係る処理は、一度終了すれば完了する類の処理ではなく、データの書き込みが発生するごとに繰り返し行われる。
【0118】
また、ステップS102においてフォールド処理の開始条件を満たすと判定された場合には、管理装置100は、マルチフォールド処理を行う(S106)。
【0119】
〔マルチフォールド処理の一例〕
図14は、本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【0120】
管理装置100は、第1のマルチフォールド処理を行う(S300)。ここで、本発明の実施形態に係る第1のマルチフォールド処理とは、例えば、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることを停止条件とするマルチフォールド処理である。
【0121】
<第1のマルチフォールド処理の一例>
図15は、本発明の実施形態に係る第1のマルチフォールド処理の一例を示す説明図である。
【0122】
管理装置100は、“n_clean”の値をn_clean=0(ゼロ)に設定し、“n_copy_max”の値をn_copy_max=M(Mは、ブロックに含まれる物理TU数よりも十分に大きい値。)に設定する(S400)。ここで、“n_clean”とは、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を保持するために用いられる。また、“n_copy_max”は、後述するフォールド処理において判定に用いられる。また、ステップS400の処理は、“n_clean”の値を初期化する処理に該当する。
【0123】
ステップS400において初期化処理が行われると、管理装置100は、フォールド処理を実行する(S402)。
【0124】
{フォールド処理の一例}
図16は、本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【0125】
管理装置100は、“n_copy”の値をn_copy=0(ゼロ)に設定する(S500)。ここで、“n_copy”は、データをコピーした物理TU数を保持するための、一種のカウンタである。また、ステップS500の処理は、“n_copy”の値を初期化する処理に該当する。
【0126】
ステップS500の処理が行われると、管理装置100は、フォールド処理の対象となるブロック(以下、「フォールド対象ブロック」と示す。)を選択する(S502)。ここで、管理装置100は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド対象ブロックとして選択するが、選択方法は、上記に限られない。
【0127】
ステップS502においてフォールド対象ブロックが選択されると、管理装置100は、フォールド対象ブロックから未コピーの“書き込み済みの有効な物理TU”を選択する(S504)。ステップS504において未コピーの“書き込み済みの有効な物理TU”を選択すると、管理装置100は、選択した物理TU内のデータを読み込み(S506)、読み込んだデータを、コピー先のブロックにおける未書き込みのPTUにコピーする(S508)。そして、管理装置100は、“n_copy”の値を、n_copy=n_copy+1に更新する(S510)。
【0128】
ステップS510の処理が行われると、管理装置100は、フォールド対象ブロックが含むすべての書き込み済みの有効な物理TUのデータのコピーが完了したか否かを判定する(S512)。
【0129】
ステップS512においてデータのコピーが完了したと判定されない場合には、管理装置100は、「n_copy≧n_copy_max」であるか否かを判定する(S514)。第1のマルチフォールド処理では、“n_copy_max”の値としてM(Mは、ブロックに含まれる物理TU数よりも十分に大きい値。)が設定されているので、管理装置100は、ステップS504からの処理を繰り返す。また、後述する第2のマルチフォールド処理では、“n_copy_max”の値が、M以外の値に設定されうるので、管理装置100は、ステップS514の判定結果に応じて選択的にステップS504からの処理を繰り返す。
【0130】
また、ステップS512においてデータのコピーが完了したと判定された場合には、管理装置100は、フォールド対象ブロックを消去して(S506)、フォールド処理を終了する。
【0131】
管理装置100は、例えば図16に示す処理を行うことによって、フォールド処理を実現する。なお、本発明の実施形態に係るフォールド処理が、図16に示す例に限られないことは、言うまでもない。
【0132】
再度図15を参照して、本発明の実施形態に係る第1のマルチフォールド処理の一例について説明する。ステップS402においてフォールド処理が行われると、管理装置100は、“n_clean”の値に、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を加える(S404)。そして、管理装置100は、“n_clean”の値が、1ブロックあたりの物理TU数以上であるか否かを判定する(S406)。
【0133】
ステップS406において、“n_clean”の値が1ブロックあたりの物理TU数以上であると判定されない場合には、管理装置100は、ステップS402からの処理を繰り返す。
【0134】
また、ステップS406において、“n_clean”の値が1ブロックあたりの物理TU数以上であると判定された場合には、管理装置100は、第1のマルチフォールド処理を終了する。
【0135】
管理装置100は、例えば図15に示す処理を行うことによって、第1のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第1のマルチフォールド処理が、図15に示す例に限られないことは、言うまでもない。
【0136】
再度図14を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップS300の処理が行われると、管理装置100は、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの合計サイズが、1ブロックのサイズを超えたか否かを判定する(S302)。ここで、管理装置100は、例えば、“n_clean”の値が1ブロックあたりの物理TU数を超えている場合に、1ブロックのサイズを超えたと判定するが、ステップS302における判定方法は、上記に限られない。
【0137】
ステップS302において1ブロックのサイズを超えたと判定されない場合には、管理装置100は、第2のマルチフォールド処理を行う(S304)。ここで、本発明の実施形態に係る第2のマルチフォールド処理とは、例えば図9に示すように、1ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)を超えるサイズ分を“書き込み済みの有効な物理トランスレーションユニット”のデータで埋める、マルチフォールド処理である。
【0138】
<第2のマルチフォールド処理の一例>
図17は、本発明の実施形態に係る第2のマルチフォールド処理の一例を示す説明図である。
【0139】
管理装置100は、“n_exess”の値をn_exess=n_clean−(1ブロックあたりの物理TU数)に設定し、“n_copy”の値をn_copy=0(ゼロ)に設定する(S600)。ここで、“n_exess”とは、1ブロックのサイズを超えたサイズ分に相当する物理TU数を示す。また、ステップS600の処理は、“n_copy”の値を初期化する処理に該当する。
【0140】
ステップS600の処理が行われると、管理装置100は、“n_copy_max”の値をn_copy_max=n_exess−n_copyに設定する(S602)。
【0141】
ステップS602の処理が行われると、管理装置100は、フォールド処理を実行する(S604)。ここで、管理装置100は、フォールド処理として例えば図16に示す処理を行う。
【0142】
ステップS604の処理が行われると、管理装置100は、“n_copy”の値を、n_copy=n_copy+(フォールド処理においてコピーされた物理TU数)に更新する(S606)。
【0143】
ステップS606の処理が行われると、管理装置100は、n_copy=n_exessであるか否かを判定する(S608)。ステップS608においてn_copy=n_exessであると判定されない場合には、管理装置100は、ステップS602からの処理を繰り返す。
【0144】
また、ステップS608においてn_copy=n_exessであると判定された場合には、管理装置100は、第2のマルチフォールド処理を終了する。
【0145】
管理装置100は、例えば図17に示す処理を行うことによって、第2のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第2のマルチフォールド処理が、図17に示す例に限られないことは、言うまでもない。
【0146】
再度図14を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップS302において1ブロックのサイズを超えたと判定されない場合には、管理装置100は、マルチフォールド処理を終了する。
【0147】
管理装置100は、例えば図14に示す処理を行うことによって、マルチフォールド処理を実現する。なお、本発明の実施形態に係るマルチフォールド処理は、図14に示す例に限られない。例えば、管理装置100は、マルチフォールド処理として、図15に示す第1のマルチフォールド処理のみを行ってもよい。
【0148】
再度図12を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップS106においてマルチフォールド処理が終了すると、管理装置100は、管理方法に係る処理を終了する。
【0149】
管理装置100は、例えば図12に示す処理を行うことによって、上述した本発明の実施形態に係る管理方法を実現することができる。したがって、管理装置100は、例えば図12に示す処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理方法に係る処理が、図12に示す例に限られないことは、言うまでもない。
【0150】
(本発明の実施形態に係る管理装置)
次に、上述した本発明の実施形態に係る管理方法に係る処理を行うことが可能な、本発明の実施形態に係る管理装置100の構成について説明する。
【0151】
図18は、本発明の実施形態に係る管理装置100の構成の一例を示すブロック図である。管理装置100は、例えば、不揮発性メモリ102と、制御部104とを備える。
【0152】
また、管理装置100は、例えば、ROM(Read Only Memory。図示せず)や、RAM(Random Access Memory。図示せず)、ユーザが操作可能な操作部(図示せず)、様々な画面を表示画面に表示する表示部(図示せず)、外部装置と通信を行うための通信部(図示せず)などを備えていてもよい。管理装置100は、例えば、データの伝送路としてのバス(bus)により上記各構成要素間を接続する。
【0153】
ROM(図示せず)は、制御部104が使用するプログラムや演算パラメータなどの制御用データを記憶する。RAM(図示せず)は、制御部104により実行されるプログラムなどを一時的に記憶する。操作部(図示せず)としては、例えば後述する操作デバイスが挙げられ、表示部(図示せず)としては、例えば後述する表示デバイスが挙げられる。また、通信部(図示せず)としては、例えば後述する通信インタフェースが挙げられる。
【0154】
〔管理装置100のハードウェア構成例〕
図19は、本発明の実施形態に係る管理装置100のハードウェア構成の一例を示す説明図である。図19を参照すると、管理装置100は、例えば、MPU150と、ROM152と、RAM154と、記録媒体156と、入出力インタフェース158と、操作入力デバイス160と、表示デバイス162と、通信インタフェース164とを備える。また、管理装置100は、例えば、データの伝送路としてのバス166で各構成要素間を接続する。
【0155】
MPU150は、MPU(Micro Processing Unit)や、制御機能などの各種機能を実現するための各種回路が集積された集積回路などで構成され、管理装置100全体を制御する制御部104として機能する。また、MPU150は、管理装置100において、後述する判定部110、および管理部112としての役目を果たすこともできる。
【0156】
ROM152は、例えばMPU150が使用するプログラムや演算パラメータなどの制御用データを記憶し、また、RAM154は、例えばMPU150により実行されるプログラムなどを一次的に記憶する。
【0157】
記録媒体156は、管理装置100における記憶手段であり、不揮発性メモリ102として機能する。記録媒体156には、例えば、アプリケーションや様々なデータなどが記憶される。ここで、記録媒体156としては、例えば、フラッシュメモリなどが挙げられる。また、記録媒体156は、管理装置100から着脱可能であってもよい。
【0158】
入出力インタフェース158は、例えば、操作入力デバイス160や、表示デバイス162を接続する。操作入力デバイス160は、操作部(図示せず)として機能し、また、表示デバイス162は、表示部(図示せず)として機能する。ここで、入出力インタフェース160としては、例えば、USB(Universal Serial Bus)端子や、DVI(Digital Visual Interface)端子、HDMI(High-Definition Multimedia Interface)端子、各種処理回路などが挙げられる。また、操作入力デバイス160は、例えば、管理装置100上に備えられ、管理装置100の内部で入出力インタフェース158と接続される。操作入力デバイス160としては、例えば、ボタン、方向キー、ジョグダイヤルなどの回転型セレクター、あるいは、これらの組み合わせなどが挙げられる。また、表示デバイス162は、例えば、管理装置100上に備えられ、管理装置100の内部で入出力インタフェース158と接続される。表示デバイス162としては、例えば、液晶ディスプレイ(Liquid Crystal Display;LCD)や有機ELディスプレイ(organic ElectroLuminescence display。または、OLEDディスプレイ(Organic Light Emitting Diode display)ともよばれる。)などが挙げられる。なお、入出力インタフェース158が、管理装置100の外部装置としての操作入力デバイス(例えば、キーボードやマウスなど)や表示デバイス(例えば、外部ディスプレイなど)と接続することも可能であることは、言うまでもない。また、表示デバイス162は、例えばタッチスクリーンなどのように、表示とユーザ操作とが可能なデバイスであってもよい。
【0159】
通信インタフェース164は、管理装置100が備える通信手段であり、ネットワークを介して(あるいは、直接的に)外部装置と無線/有線で通信を行うための通信部(図示せず)として機能する。ここで、通信インタフェース164としては、例えば、通信アンテナおよびRF(Radio Frequency)回路(無線通信)や、LAN端子および送受信回路(有線通信)などが挙げられる。なお、本発明の実施形態に係る通信インタフェース164は、上記に限られず、例えば、ネットワークに対応する構成をとることができる。
【0160】
管理装置100は、例えば図19に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。なお、本発明の実施形態に係る管理装置100のハードウェア構成は、図19に示す構成に限られない。例えば、管理装置100は、本発明の実施形態に係る管理方法に係る処理を行う機能(例えば、後述する判定部110および管理部112が有する機能)を実現するためのIC(Integrated Circuit)であってもよい。
【0161】
再度図18を参照して、管理装置100の構成の一例について説明する。不揮発性メモリ102は、管理装置100が備える記憶手段である。ここで、不揮発性メモリ102としては、例えば、フラッシュメモリなどが挙げられる。不揮発性メモリ102は、制御部104(より具体的には、後述する判定部110、および管理部112)によって、データの書き込み、読み出し、消去などが管理される。
【0162】
制御部104は、例えば、MPUなどで構成され、管理装置100全体を制御する役目を果たす。また、制御部104は、判定部110と、管理部112とを備え、本発明の実施形態に係る管理方法に係る処理を主導的に行う役目を果たす。
【0163】
判定部110は、上記(1)の処理(開始条件判定処理)を主導的に行う役目を果たす。より具体的には、判定部110は、フォールド処理を開始するための開始条件を満たすか否かを判定する。そして、判定部110は、当該開始条件を満たすと判定した場合に、例えばフォールド処理を開始させるための処理開始要求(一種のトリガ)を管理部112へ伝達する。
【0164】
管理部112は、上記(2)の処理(フォールド処理)を主導的に行う役目を果たす。より具体的には、管理部112は、例えば、上記処理開始要求が伝達された場合にフォールド処理を選択的に開始する。また、管理部112は、例えば、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。また、管理部112は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)以上となるまで、フォールド処理を繰り返す。
【0165】
制御部104は、例えば、判定部110、および管理部112を備えることによって、上記(1)の処理(開始条件判定処理)、(2)の処理(フォールド処理)を行う。したがって、制御部104は、例えば、判定部110、および管理部112を備えることによって、上述した本発明の実施形態に係る管理方法に係る処理を実現することができるので、不揮発性メモリ102における空き領域の確保の効率化を図ることができる。
【0166】
なお、本発明の実施形態に係る制御部104の構成は、図18に示す例に限られない。例えば、本発明の実施形態に係る制御部104は、判定部110を備えない構成をとることもできる。上記の構成の場合であっても、本発明の実施形態に係る管理装置100は、例えば操作部(図示せず)から伝達される、フォールド処理の開始を要求する操作信号に基づいて、上記(2)の処理(フォールド処理)を行うことが可能である。
【0167】
管理装置100は、例えば図18に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。したがって、管理装置100は、不揮発性メモリ102における空き領域の確保の効率化を図ることができる。
【0168】
なお、本発明の実施形態に係る管理装置100の構成は、図18に示す構成に限られない。例えば、本発明の実施形態に係る管理装置100は、不揮発性メモリ102を備えず、有線/無線で接続された外部装置が備える不揮発性メモリにおけるデータの書き込み、読み出し、消去などを管理する構成であってもよい。上記の構成の場合であっても、本発明の実施形態に係る管理装置100は、外部装置が備える不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0169】
以上のように、本発明の実施形態に係る管理装置100は、従来の技術がフォールド処理を1回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行う(マルチフォールド処理)。ここで、不揮発性メモリを使用する側が、例えばFATシステムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン(書き換え順序)で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。管理装置100がマルチフォールド処理を行うことによって、上記のように将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行ったブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置100は、例えば図6に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。
【0170】
また、管理装置100は、不揮発性メモリの空き領域をより効率的に確保することができるので、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【0171】
また、管理装置100は、データの書き込みに係る条件を含む開始条件を満たしたときにフォールド処理を行うので、マルチフォールド処理を、例えば、データの書き込みを行う際に分散して行うことが可能である。よって、管理装置100は、バックグラウンドの処理としてフォールド処理を行わなくてもよいので、例えば、バックグラウンドの処理としてフォールド処理が突然行われることによる他の処理への影響(例えば処理パフォーマンスの低下など)を防止することができる。
【0172】
さらに、管理装置100は、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと(言い換えれば、システムがいわゆるアイドル状態にあること)を開始条件とすることが可能である。よって、上記の場合には、管理装置100は、システムのアイドル状態を有効に活用することができる。
【0173】
以上、本発明の実施形態として管理装置100を挙げて説明したが、本発明の実施形態は、かかる形態に限られない。本発明の実施形態は、例えば、不揮発性メモリを用いる記憶装置、PC(Personal Computer)やサーバなどのコンピュータ、テレビ受像機などの表示装置、携帯電話などの携帯型通信装置、映像/音楽再生装置(または映像/音楽記録再生装置)、ゲーム機など、様々な機器に適用することができる。また、本発明の実施形態は、例えば、上記のような様々な機器に組み込まれる記録媒体の制御ICに適用することもできる。
【0174】
(本発明の実施形態に係るプログラム)
コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム(例えば、上記(1)の処理(開始条件判定処理)および(2)の処理(フォールド処理)や、上記(2)の処理(フォールド処理)など、本発明の実施形態に係る管理方法に係る処理を実現するためのプログラム)によって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラムによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【0175】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【0176】
例えば、本発明の実施形態に係る管理装置は、図18に示す判定部110、および管理部112を個別に備える(例えば、それぞれを個別の処理回路で実現する)ことができる。
【0177】
また、上記では、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム(コンピュータプログラム)が提供されることを示したが、本発明の実施形態は、さらに、上記プログラムをそれぞれ記憶させた記録媒体も併せて提供することができる。
【0178】
上述した構成は、本発明の実施形態の一例を示すものであり、当然に、本発明の技術的範囲に属するものである。
【符号の説明】
【0179】
10、100 管理装置
102 不揮発性メモリ
104 制御部
110 判定部
112 管理部
【技術分野】
【0001】
本発明は、管理装置、管理方法、およびプログラムに関する。
【背景技術】
【0002】
近年、NANDフラッシュメモリ(flash memory)などのような電気的にデータの書き込み、読み出し、消去が可能な不揮発性メモリ(nonvolatile memory)の大容量化が進んでいる。ここで、NANDフラッシュメモリのような上記不揮発性メモリにおける書き込みは、各ビットを“1”から“0”へと一方向に書き換えることによって行われる。そのため、上記不揮発性メモリにおいて新たにデータを書き込む場合には、一旦、消去を行って全てのビットを“1”にした上で、書き込みを行う必要がある。また、上記不揮発性メモリにおいては、データの書き込み/読み出しの最小単位は「ページ」であり、消去の最小単位は、複数のページが集まった「ブロック」である。上記のように、消去の最小単位である「ブロック」のサイズは、書き込みの最小単位である「ページ」のサイズよりも例えば数十倍程大きいので、上記不揮発性メモリにおけるデータの書き換えをより効率的に行うためには、何らかの仕組みが必要となる。
【0003】
このような中、不揮発性メモリにおけるデータの書き換えの効率化を図るための技術が開発されている。ブロックサイズの整数分の1かつページサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行って、不揮発性メモリのアクセス管理を行い、ブロックの内容のうち、使用中の物理トランスレーションユニットを、別の未使用の物理トランスレーションユニットがあるブロックにコピーし、元のブロックを消去することにより、元のブロックに含まれていた無効の物理トランスレーションユニットの数だけ、新たに未使用の物理トランスレーションユニットを増やす技術としては、例えば、特許文献1が挙げられる。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2009−116601号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
不揮発性メモリにおけるデータの書き換えの効率化を図るための従来の技術(以下、単に「従来の技術」と示す。)は、不揮発性メモリにおけるあるブロックの物理トランスレーションユニットのデータをコピーし、当該ブロック(コピー元のブロック)を消去する。よって、従来の技術を用いる場合には、ブロック内に、書き込み済みの無効な物理トランスレーションユニット(無効なデータが記録されている物理トランスレーションユニット)が多ければ多いほど、データを書き込み可能な空き容量を増やすことが可能である。
【0006】
ここで、空き領域を効率的に確保することは、例えば、不揮発性メモリをデータの記録媒体として使用するユーザ(以下、単に「ユーザ」と示す場合がある。)からみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化に寄与する。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていない。
【0007】
本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、不揮発性メモリにおける空き領域の確保の効率化を図ることが可能な、新規かつ改良された管理装置、管理方法、およびプログラムを提供することにある。
【課題を解決するための手段】
【0008】
上記目的を達成するために、本発明の第1の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、上記管理部は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理装置が提供される。
【0009】
かかる構成により、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0010】
また、上記管理部は、上記フォールド処理を行った後、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、上記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーしてもよい。
【0011】
また、上記管理部における上記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、上記管理部は、上記判定部において上記開始条件を満たすと判定された場合に、選択的に上記フォールド処理を行ってもよい。
【0012】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている上記ブロックの数が所定の閾値より大きいまたは上記閾値以上であることを上記開始条件として、上記判定を行ってもよい。
【0013】
また、上記判定部は、さらに、上記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを上記開始条件として、上記判定を行ってもよい。
【0014】
また、上記判定部は、上記管理部が直近にデータを書き込んだ書き込み先が上記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない上記ブロックの数が所定の閾値より小さいまたは上記閾値以下であることを上記開始条件として、上記判定を行ってもよい。
【0015】
また、上記管理部は、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、上記ブロックのサイズの所定の整数倍以上となるまで上記フォールド処理を繰り返してもよい。
【0016】
また、上記管理部は、上記不揮発性メモリにおける上記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、上記フォールド処理におけるコピー元のブロックとして選択してもよい。
【0017】
また、上記管理部は、上記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが上記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、上記フォールド処理の対象から除外してもよい。
【0018】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【0019】
また、上記管理部は、上記フォールド処理を行う場合には、上記ブロック内の上記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーしてもよい。
【0020】
また、上記管理部は、上記フォールド処理を行う場合には、繰り返し行われる上記フォールド処理においてコピー元となる全てのブロックにおける上記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した上記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した上記物理トランスレーションユニットのデータをコピーしてもよい。
【0021】
上記不揮発性メモリをさらに備えていてもよい。
【0022】
上記目的を達成するために、本発明の第2の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップとを有し、上記管理するステップでは、上記判定するステップにおいて上記開始条件を満たすと判定された場合に、上記フォールド処理が選択的に行われ、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、管理方法が提供される。
【0023】
かかる方法を用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0024】
上記目的を達成するために、本発明の第3の観点によれば、電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、上記ブロックのサイズの整数分の1、かつ上記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、上記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の上記ブロックを消去することによって、コピー元の上記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、上記管理手段は、上記フォールド処理を開始した場合には、上記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、上記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、上記ブロックのサイズ以上となるまで、上記フォールド処理を繰り返す、プログラムが提供される。
【0025】
かかるプログラムを用いることにより、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【発明の効果】
【0026】
本発明によれば、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【図面の簡単な説明】
【0027】
【図1】不揮発性メモリにおける前提を説明するための説明図である。
【図2】不揮発性メモリにおける前提を説明するための説明図である。
【図3】従来の技術における問題を説明するための説明図である。
【図4】従来の技術における問題を説明するための説明図である。
【図5】従来の技術における問題を説明するための説明図である。
【図6】従来の技術における問題を説明するための説明図である。
【図7】本発明の実施形態に係る管理装置がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。
【図8】本発明の実施形態に係る管理装置におけるマルチフォールド処理の一例を示す説明図である。
【図9】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図10】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図11】本発明の実施形態に係る管理装置におけるマルチフォールド処理の他の例を示す説明図である。
【図12】本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。
【図13】本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【図14】本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【図15】本発明の実施形態に係る第1のマルチフォールド処理の一例を示す説明図である。
【図16】本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【図17】本発明の実施形態に係る第2のマルチフォールド処理の一例を示す説明図である。
【図18】本発明の実施形態に係る管理装置の構成の一例を示すブロック図である。
【図19】本発明の実施形態に係る管理装置のハードウェア構成の一例を示す説明図である。
【発明を実施するための形態】
【0028】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書および図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【0029】
また、以下では、下記に示す順序で説明を行う。
1.本発明の実施形態に係る管理方法
2.本発明の実施形態に係る管理装置
3.本発明の実施形態に係るプログラム
【0030】
(本発明の実施形態に係る管理方法)
本発明の実施形態に係る管理装置(以下、「管理装置100」と示す場合がある。)の構成について説明する前に、本発明の実施形態に係る不揮発性メモリの管理方法について説明する。以下では、管理装置100が、本発明の実施形態に係る管理方法に係る処理を行うものとして説明する。また、以下では、本発明の実施形態に係る管理装置100の管理対象の不揮発性メモリが、NANDフラッシュメモリである場合を例に挙げて説明する。なお、本発明の実施形態に係る管理装置100の管理対象の不揮発性メモリが、NAND型のフラッシュメモリに限られないことは、言うまでもない。
【0031】
[前提]
本発明の実施形態に係る管理方法に係る処理について説明する前に、管理装置100の管理対象の不揮発性メモリにおける前提について説明する。
【0032】
図1、図2は、不揮発性メモリにおける前提を説明するための説明図である。図1に示すように、不揮発性メモリは、データの書き込み/読み出しの最小単位である「ページ」と、複数のページからなる消去の最小単位である「ブロック」とで構成される。
【0033】
また、不揮発性メモリには、製造時などの段階において「不良ブロック」とよばれるデータの記録ができないブロック(使用できないブロック)が存在する。そのため、管理装置100は、不揮発性メモリの不良ブロックを避けて、データの読み書きを行わなければならない。
【0034】
また、不揮発性メモリの各ブロックにおいては、それぞれのブロックに含まれるページに番号(ページを識別するための番号)が付されており、NANDフラッシュメモリのような不揮発性メモリの多くは、図2のAに示すように、当該番号が小さいページの順にデータが書き込まれる。そして、NANDフラッシュメモリのような不揮発性メモリの多くは、例えば図2のBに示すように、ランダムな順番でページにデータが書き込まれることは、禁止される。
【0035】
また、不揮発性メモリの各ブロックには、書き換えの回数に上限(いわゆる寿命)があることから、不揮発性メモリの長寿命化を図るためには、特定のブロックに書き換えが偏らないようにする必要がある。
【0036】
不揮発性メモリは、例えば上記のような特徴を有する。ここで、ユーザの利便性を損ねないためには、例えば、上記不良ブロックや消去の処理をユーザに意識させないことが望ましい。そのため、不揮発性メモリの管理には、例えば、不揮発性メモリを使用する側(例えばファイルシステム)からの要求を解釈して、書き込み操作、読み出し操作など、不揮発性メモリを操作するための命令に変換する論理−物理変換層(レイヤー)が用いられる。
【0037】
[従来の技術における問題]
次に、従来の技術における問題について、より具体的に説明する。図3〜図6は、従来の技術における問題を説明するための説明図である。
【0038】
上述したように、従来の技術では、ブロックのサイズよりも小さい単位であるトランスレーションユニット(以下、「TU」と示す場合がある。)で論理アドレス−物理アドレス変換を行っている。ここで、図3に示すように、トランスレーションユニットは、ブロックのサイズの整数分の1のサイズであり、かつ、ページのサイズの整数倍のサイズである。すなわち、ブロックは、複数のトランスレーションユニットを含み、トランスレーションユニットは、複数のトランスレーションユニットを含む。
【0039】
また、従来の技術では、トランスレーションユニットを、不揮発性メモリ上の実際のトランスレーションユニット(以下、「物理トランスレーションユニット」または「物理TU」と示す場合がある。)と、アドレス変換されて不揮発性メモリを使用する側に提供されるトランスレーションユニット(以下、「論理トランスレーションユニット」または「論理TU」、「LTU」と示す場合がある。)とに分類する。上記によって、従来の技術では、例えば、ファイルシステムにおける読み書きの単位と、トランスレーションユニットを一致させるなど、データの読み書きのサイズを柔軟に設定することが可能となる。
【0040】
また、従来の技術におけるデータの書き換えは、図4に示すように、データが記録されていない物理トランスレーションユニットにデータを追記することによって行われる。より具体的には、書き換え前のデータが記録されていた物理トランスレーションユニットP1を無効な状態へと更新し(図4のC)、書き換えを行う新たなデータを、データが記録されていない物理トランスレーションユニットP2に書き込むことによって(図4のD)、データの書き換えが行われる。上記によって、不揮発性メモリでは、図4の物理トランスレーションユニットP2に示すように、最新のデータが記録されてる状態の物理トランスレーションユニット(以下、「書き込み済みの有効な物理トランスレーションユニット」と示す場合がある。)と、消去対象の古いデータが記録されている状態の物理トランスレーションユニット(以下、「書き込み済みの無効な物理トランスレーションユニット」と示す場合がある。)とが生じる。
【0041】
以下では、物理トランスレーションユニットにおいて、最新のデータが記録されてる状態を「INUSE」と示し、消去対象の古いデータが記録されている状態を「DIRTY」と示す場合がある。また、以下では、データの記録がされていない物理トランスレーションユニットを「未書き込みの物理トランスレーションユニット」と示す場合があり、物理トランスレーションユニットにおいて消去後に(または初期時に)データが記録されていない状態を「CLEAN」と示す場合がある。
【0042】
上述したように、NANDフラッシュメモリのような不揮発性メモリは、ブロック単位でしかデータの消去を行うことができない。そのため、ブロックを構成する一部の物理トランスレーションユニットに、例えば図4の物理トランスレーションユニットP1に示すような“書き込み済みの無効な物理トランスレーションユニット”があったとしても、当該ブロック内に“書き込み済みの有効な物理トランスレーションユニット”が存在した場合には、消去を行うことができない。よって、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける“書き込み済みの無効な物理トランスレーションユニット”の数が増え、また、データの書き込みが可能な物理トランスレーションユニット(例えば、CLEANな物理トランスレーションユニット)の数が減ってしまう。つまり、データの書き込みが繰り返されるにつれて、不揮発性メモリにおける空き領域が減ることとなる。
【0043】
そこで、従来の技術では、データの書き込みが可能な物理トランスレーションユニットの数を増やして、不揮発性メモリにおける空き領域を確保するために、フォールド処理を行う。ここで、フォールド処理とは、ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす処理である。
【0044】
図5は、フォールド処理の概要を示している。図5(a)はフォールド処理前のブロックB1、およびブロックB2状態を示しており、図5(b)はフォールド処理中のブロックB1、およびブロックB2状態を示している。そして、図5(c)はフォールド処理後のブロックB1、およびブロックB2状態を示している。フォールド処理では、コピー元のブロックB1の“書き込み済みの有効な物理トランスレーションユニット”がコピー先のブロックB2にコピーされ、コピーされた物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”に更新される(図5(b))。そして、フォールド処理では、コピー元のブロックB1を消去する(図5(c))。図5に示すように、フォールド処理が行われることによって“未書き込みの物理トランスレーションユニット”が増えていることが分かる。よって、フォールド処理が行われることによって、不揮発性メモリにおける空き領域を増やすことが可能となる。
【0045】
従来の技術は、例えば、不揮発性メモリデータが書き込まれた後、データが記録されているブロック(INUSE、またはDIRTYの物理トランスレーションユニットを含むブロック。以下、「使用中のブロック」と示す場合がある。)の総数が閾値を超えた以上となったとき(または、閾値以上となったとき)に、上記フォールド処理を1回だけ行う。よって、従来の技術を用いる場合には、不揮発性メモリにおける空き領域を増やすことが可能である。しかしながら、従来の技術では、空き領域の確保の効率化についての考慮がなされていないので、効率的に不揮発性メモリの空き領域を確保することはできない。
【0046】
図6は、従来の技術に係るフォールド処理の一例を示しており、不揮発性メモリの各ブロックの状態を時系列(図6(a)〜図6(h))で示している。ここで、図6は、使用中のブロックが6(閾値の一例)より大きくなったとき(開始条件)にフォールド処理が行われ、フォールド処理が1回で終了する(停止条件)場合を示している。以下では、図6に示す処理を、従来の技術を用いる管理装置(以下、「従来の管理装置10」と示す場合がある。)が行うものとして説明する。
【0047】
図6(a)の状態においてLTU3の書き換えが行われると(図6(b))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(c))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0048】
また、図6(c)の状態においてLTU4の書き換えが行われると(図6(d))、従来の管理装置10は、上記開始条件を満たすか否かを判定する。図6(d)の状態では、上記開始条件は満たされていないので、従来の管理装置10は、フォールド処理を行わない。
【0049】
図6(d)の状態においてLTU8の書き換えが行われると(図6(e))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(f))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0050】
そして、図6(f)の状態においてLTU9の書き換えが行われると(図6(g))、上記開始条件が満たされ、従来の管理装置10は、フォールド処理を行う(図6(h))。上記フォールド処理が行われることによって上記停止条件が満たされるので、従来の管理装置10は、上記開始条件が再度満たされるまで、フォールド処理を行わない。
【0051】
図6(a)〜図6(h)に示すように、従来の管理装置10は、開始条件を満たすごとにフォールド処理を1回だけ行う。その結果、図6(h)に示すように、書き換えが行われたLTU3、LTU4、LTU8、およびLTU9は、複数のブロックに分散して書き込まれることとなる。ここで、不揮発性メモリを使用する側が、例えばFAT(File Allocation Table)システムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン(書き換え順序)で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。また、例えば、論理トランスレーションユニットのサイズとFATのクラスタのサイズとが同一である場合などには、上記の可能性はより高くなる。なお、本発明の実施形態に係るファイルシステムは、FATに限られず、例えば、NTFS(NT File System)やext4(fourth extended file system)などが挙げられる。
【0052】
ここで、例えば、不揮発性メモリに対するデータの書き換えが、図6に示す論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで行われた場合には、図6(h)に示すLTU3、LTU4、LTU8、およびLTU9に対応する物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。
【0053】
しかしながら、図6(h)に示すように、LTU3、LTU4、LTU8、およびLTU9は、複数のブロックに分散して書き込まれているので、不揮発性メモリにおいて“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在することは期待できない。したがって、“書き込み済みの無効な物理トランスレーションユニット”を多く含むブロックが存在しない状態でフォールド処理を行ったとしても、不揮発性メモリの空き領域を十分に確保することができないので、従来の技術を用いたとしても、効率的に不揮発性メモリの空き領域を確保することはできるとは限らない。
【0054】
[本発明の実施形態に係る管理方法の概要]
本発明の実施形態に係る管理装置100は、従来の技術と同様に、不揮発性メモリにおけるデータの書き込み、読み出し、消去を、トランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理する。
【0055】
また、管理装置100は、従来の技術と同様に、フォールド処理を行うことによって不揮発性メモリの空き領域を確保するが、管理装置100は、従来の技術がフォールド処理を1回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。以下では、本発明の実施形態に係るフォールド処理を、フォールド処理を複数回繰り返し行いうることから、「マルチフォールド処理」と示す場合がある。ここで、本発明の実施形態に係る所定の停止条件としては、例えば、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ以上となるまで”や、“フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズの所定の整数倍以上となるまで”などが挙げられる。
【0056】
また、管理装置100は、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。
【0057】
図7は、本発明の実施形態に係る管理装置100がフォールド処理を開始した場合における不揮発性メモリに対するデータの書き込み順を示す説明図である。管理装置100は、データが記録されていないブロックを選択し、当該ブロックにおける先頭の物理トランスレーションユニット(付された番号が最も小さい物理トランスレーションユニット)から順に、データの書き込みを行う。そして、管理装置100は、データの書き込みを行っている書き込み対象のブロック(以下、「書き込み対象ブロック」または「PTUブロック」と示す場合がある。)を構成する全ての物理トランスレーションユニットの書き込みが完了したときに、データが記録されていないブロックを新たに選択して、当該ブロックにデータを書き込む。以下では、データの書き込みの対象となる物理トランスレーションユニットを「PTU」と示す場合がある。また、以下では、データの書き込みを行う各時点において、データの書き込みの対象となっている物理トランスレーションユニットを「書き込み対象現在物理トランスレーションユニット」または「書き込み対象PTU」と示す場合がある。つまり、本発明の実施形態に係る書き込み対象ブロックとは、書き込み対象現在物理トランスレーションユニットが含まれるブロックを指すこととなる。
【0058】
より具体的には、管理装置100は、例えば下記の(1)の処理(開始条件判定処理)、および(2)の処理(フォールド処理)を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。
【0059】
(1)開始条件判定処理
管理装置100は、フォールド処理を開始するための開始条件を満たすか否かを判定する。
【0060】
ここで、本発明の実施形態に係る開始条件としては、例えば、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロックの数が所定の閾値より大きい(または所定の閾値以上である。以下、同様とする。)ことが挙げられる。直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであることを開始条件のひとつとすることによって、管理装置100は、図7に示すように、“書き込み済みの有効な物理トランスレーションユニット”のデータを、ブロックの先頭の物理トランスレーションユニットへとコピーすることが可能となる。また、データが書き込まれているブロックの数が所定の閾値より大きいことを開始条件のひとつとすることによって、管理装置100は、不揮発性メモリの空き容量が一定値未満(または、一定値以下)となったときに、空き容量の確保を行うことができる。
【0061】
また、管理装置100は、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていないブロックの数が所定の閾値より小さい(または閾値以下である。以下、同様とする。)ことを開始条件とすることもできる。データが書き込まれていないブロックの数が所定の閾値より小さいことを開始条件のひとつとすることによって、例えば、不揮発性メモリにおいて不良ブロックが増えた結果データを記録可能な絶対容量が小さくなったとしても、空き容量の確保を行うことが可能となる。
【0062】
なお、本発明の実施形態に係る開始条件は、上記に限られない。例えば、管理装置100は、上記2つの開始条件の双方を組み合わせた条件(上記2つの開始条件の論理和)を、開始条件することが可能である。また、管理装置100は、上述した開始条件それぞれに対して、さらに、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと(言い換えれば、システムがいわゆるアイドル状態にあること)を、条件として加えてもよい。不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを開始条件のひとつとすることによって、管理装置100は、データの書き込み、読み出し、消去に係る処理と、フォールド処理とが同時期に行われることを回避することが可能となる。よって、管理装置100は、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0063】
(2)フォールド処理
上記(1)の処理(開始条件判定処理)において開始条件を満たすと判定された場合には、管理装置100は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ(合計サイズ)が、ブロックのサイズを基準とする所定のサイズ以上となるまで、フォールド処理を繰り返す(マルチフォールド処理)。
【0064】
ここで、「フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズ(合計サイズ)が、ブロックのサイズを基準とする所定のサイズ以上となる」ことは、(2)の処理(フォールド処理)における処理の停止条件の一例である。また、本発明の実施形態に係るブロックのサイズを基準とする所定のサイズとしては、例えば、ブロックのサイズや、ブロックのサイズの整数倍のサイズが挙げられる。本発明の実施形態に係るブロックのサイズを基準とする所定のサイズは、例えば、予め規定されたサイズであってもよいし、ユーザ操作に基づいて適宜設定されたサイズであってもよい。また、本発明の実施形態に係るサイズは、例えば[Byte]、[KByte]で表されるが、本発明の実施形態に係るサイズは、上記に限られない。
【0065】
また、管理装置100は、フォールド処理を行った後、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れるか否かを判定してもよい。上記判定を行った場合において割り切れないと判定したときには、管理装置100は、端数のサイズに対応する“未書き込みの物理トランスレーションユニット”のサイズ分、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。管理装置100が、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、(2)の処理(フォールド処理)後の不揮発性メモリにおいては、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットとなる。よって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、フォールド処理によりコピーするデータとユーザの書き換えデータとを、ブロック間で分離することができ、その結果、ユーザのアクセスパターンがブロック内に保存される。したがって、上記判定結果に応じて“書き込み済みの有効な物理トランスレーションユニット”のデータを選択的にコピーすることによって、より効率的に空き容量の確保を行うことが可能となる。
【0066】
管理装置100は、上記のように停止条件を満たすまでフォールド処理を繰り返す。ここで、本発明の実施形態に係る管理装置100におけるフォールド処理について説明する。管理装置100は、フォールド処理として、ブロックの内容のうち、“書き込み済みの有効な物理トランスレーションユニット”のデータを、“未書き込みの物理トランスレーションユニット”があるブロックへコピーし、コピー元のブロックを消去することによって、コピー元のブロックに含まれていた“書き込み済みの無効な物理トランスレーションユニット”の数分、“未書き込みの物理トランスレーションユニット”を増やす処理を行う。つまり、管理装置100は、基本的に従来の技術と同様の処理を、フォールド処理として行う。
【0067】
また、管理装置100は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド処理におけるコピー元のブロックとして選択する。上記のようにフォールド処理におけるコピー元のブロックを選択することによって、フォールド処理後に増える“未書き込みの物理トランスレーションユニット”の数をより増やすことが可能となるので、管理装置100は、不揮発性メモリの空き容量の確保をより効率的に行うことができる。
【0068】
なお、管理装置100におけるブロックの選択方法は、上記に限られない。例えば、管理装置100は、フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外してもよい。管理装置100は、上記のように特定のブロックを除外した上で、ブロックを選択することによって、不揮発性メモリの空き容量の確保をより効率的に行うことが可能となる。なお、上記選択方法を用いた場合の効果については、後述する。
【0069】
また、管理装置100は、例えば、不揮発性メモリにおけるブロックの中に“書き込み済みの無効な物理トランスレーションユニット”の数が最も多いブロックが複数存在する場合には、当該ブロックの中からランダムにブロックを選択してもよい。上記のようにブロックの選択をランダムに行うことによって、不揮発性メモリの空き容量の効率的な確保に加え、不揮発性メモリの長寿命化を図ることが可能となる。
【0070】
管理装置100は、例えば上記のようにフォールド処理におけるコピー元のブロックを選択することによって、不揮発性メモリの空き容量の効率的な確保を実現する。
【0071】
また、管理装置100は、フォールド処理を行う場合において、“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番を、例えば下記の(a)〜(c)のように行う。
【0072】
(a)第1の順番
管理装置100は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。つまり、管理装置100は、ブロック何の先頭の“書き込み済みの有効な物理トランスレーションユニット”のデータから順にコピーする。第1の順番を用いることによって、例えば、過去の論理トランスレーションユニットの書き込み順序を保存することが可能となる。
【0073】
(b)第2の順番
管理装置100は、ブロック内の“書き込み済みの有効な物理トランスレーションユニット”のデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする。より具体的には、管理装置100は、例えば、対応する論理トランスレーションユニットに付された番号が小さい順にソートを行い、ソートされた順番で、当該論理トランスレーションユニットに対応する“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。ここで、例えばFATファイルシステムでは、空クラスタの割り当てをクラスタ番号が小さい順に行う。よって、例えば上記クラスタ番号と論理トランスレーションユニットに付された番号とが一致している場合には、管理装置100は、不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【0074】
(c)第3の順番
管理装置100は、繰り返し行われるフォールド処理(マルチフォールド処理)においてコピー元となる全てのブロックにおける“書き込み済みの有効な物理トランスレーションユニット”を特定する。ここで、管理装置100は、例えば仮想的にマルチフォールド処理を行うことによって、上記特定を行う。そして、管理装置100は、特定した物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した物理トランスレーションユニットのデータをコピーする。上記第3の順番でコピーを行うことによって、管理装置100は、上記第2の順番でコピーを行う場合よりも、さらに不揮発性メモリの同一ブロックに、同一ファイルのクラスタが割り当てられる可能性を高めることが可能となる。
【0075】
管理装置100は、例えば上記(a)〜(c)に示す順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする。なお、本発明の実施形態に係る“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーする順番は、上記に限られない。例えば、管理装置100は、任意の順番で“書き込み済みの有効な物理トランスレーションユニット”のデータをコピーすることも可能である。
【0076】
管理装置100は、(2)の処理(フォールド処理)として、例えば上記のようなフォールド処理を停止条件を満たすまで繰り返し行うこと(マルチフォールド処理を行うこと)によって、不揮発性メモリの空き容量を確保する。
【0077】
管理装置100は、例えば、上記(1)の処理(開始条件判定処理)、および(2)の処理(マルチフォールド処理)を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図る。なお、上記では、管理装置100が上記(1)の処理(開始条件判定処理)を行った後に、(2)の処理(フォールド処理)を行うことを示したが、管理装置100における処理は、上記に限られない。例えば、管理装置100は、上記(1)の処理(開始条件判定処理)の結果によらず、(2)の処理(フォールド処理)を行うことも可能である。上記の例としては、例えば、管理装置100が備える操作部(後述する)から伝達される操作信号や、ユーザ操作に応じてリモート・コントローラなどの外部操作装置(図示せず)から送信される外部操作信号に基づいて、(2)の処理(マルチフォールド処理)を行う場合が挙げられる。
【0078】
次に、管理装置100がマルチフォールド処理を行うことによる効果について説明する。図8は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の一例を示す説明図である。ここで、図8は、図6と同様に、不揮発性メモリの各ブロックの状態を時系列(図8(a)〜図8(g))で示している。また、図8は、マルチフォールド処理の開始条件が、直近にデータを書き込んだ書き込み先がブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれているブロック(使用中のブロック)の数が使用中のブロックが7(所定の閾値の一例)以上となったときである場合を示している。また、図8は、マルチフォールド処理の停止条件が、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることである場合を示している。
【0079】
図8(a)の状態においてLTU3の書き換えが行われると(図8(b))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(b)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0080】
図8(b)の状態においてLTU4の書き換えが行われると(図8(c))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(c)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0081】
図8(c)の状態においてLTU8の書き換えが行われると(図8(d))、管理装置100は、上記開始条件が満たされているか否かを判定する。図8(d)の状態では、上記開始条件は満たされていないので、管理装置100は、フォールド処理を行わない。
【0082】
図8(d)の状態においてLTU9の書き換えが行われると(図8(e))、管理装置100は、上記開始条件が満たされているか否かを判定する。LTU9の書き換えによって、上記開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図8(f))。
【0083】
フォールド処理を行うと、管理装置100は、上記停止条件を満たしているか否かを判定する。図8(f)の状態では、上記停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図8(g))。そして、管理装置100は、上記停止条件を満たしているか否かを判定する。
【0084】
図8(g)の状態では、1ブロックのサイズに該当するサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。よって、管理装置100は、マルチフォールド処理を終了する。
【0085】
ここで、図8(g)に示すように、マルチフォールド処理が行われることによって、書き換えを行ったLTU3、LTU4、LTU8、およびLTU9が、同一のブロックに集約されていることが分かる。ここで、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行った上記ブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置100は、図6に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。また、図8に示す例では、将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合に、管理装置100は、書き換えを行った上記ブロックの消去を行えばよいので、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0086】
管理装置100は、例えば図8に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0087】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8に示す例に限られない。例えば、図8では、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズと一致する場合を示したが、当該ブロックのサイズを超えることも想定される。そこで、次に、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例として、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における例について説明する。
【0088】
図9は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。ここで、図9は、マルチフォールド処理の停止条件を満たしたときにおいて、増えた“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えた場合における処理の一例を示している。また、図9は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図9(a)〜図9(d))で示している。また、図9は、管理装置100が、図8と同様の開始条件、停止条件にてフォールド処理を行う例を示している。
【0089】
図9(a)の状態においてLTU12の書き換えが行われると(図9(b))、管理装置100は、開始条件が満たされているか否かを判定する。LTU12の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図9(b))。
【0090】
フォールド処理を行うと、管理装置100は、停止条件を満たしているか否かを判定する。図9(b)の状態では、停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図9(c))。そして、管理装置100は、停止条件を満たしているか否かを判定する。
【0091】
図9(c)の状態では、1ブロックのサイズより大きなサイズ分、“未書き込みの物理トランスレーションユニット”が増えているので、停止条件が満たされている。また、図9(c)の状態では、図8(g)の状態と異なり、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズで割り切れない。上記の場合、管理装置100は、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分(図9(c)の例では、1つの物理トランスレーションユニットのサイズ)、フォールド処理によって“書き込み済みの有効な物理トランスレーションユニット”であるLTU0のデータをコピーする(図9(d))。
【0092】
図9(d)に示すように、1ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)を超えるサイズ分を、“書き込み済みの有効な物理トランスレーションユニット”のデータで埋めることによって、マルチフォールド処理後の不揮発性メモリの状態が、図8(g)と同様の状態となる。よって、管理装置100は、図9に示す処理を行う場合においても、図8に示すマルチフォールド処理と同様に、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、管理装置100は、将来的行うフォールド処理において書き換えを行った上記ブロックの消去を行えばよいので、図8に示すマルチフォールド処理と同様に、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0093】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8、図9に示す例に限られない。例えば、管理装置100は、さらにフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを基準とする所定のサイズを超えることを、停止条件として、マルチフォールド処理を行うことも可能である。
【0094】
図10は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。また、図10は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図10(a)〜図10(c))で示している。また、図10は、管理装置100が、図8と同様の開始条件にてフォールド処理を行う例を示している。
【0095】
図10(a)の状態においてLTU12の書き換えが行われると(図10(b))、管理装置100は、開始条件が満たされているか否かを判定する。LTU12の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図10(b))。
【0096】
フォールド処理を行うと、管理装置100は、さらにフォールド処理を行った場合に、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えるか否かを判定する(停止条件の判定)。ここで、管理装置100は、例えば仮想的にフォールド処理を行うことによって、上記判定を行う。ここで、図10(b)の状態において2回目のフォールド処理を行うと、増える“未書き込みの物理トランスレーションユニット”のサイズがブロックのサイズを超えてしまう(図10(c))。よって、管理装置100は、2回目のフォールド処理を行うことなく、不揮発性メモリが図10(b)の状態のときに、マルチフォールド処理を終了する。
【0097】
管理装置100が上記のような停止条件でマルチフォールド処理を行うことによって、次に書き換えられるデータが分断されることを防止することが可能となる。よって、管理装置100は、上記のような停止条件でマルチフォールド処理を行うことによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えなどのパフォーマンスの向上を図ることができる。
【0098】
なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理は、図8〜図10に示す例に限られない。例えば、管理装置100は、上述したように、フォールド処理を行う場合において、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することも可能である。
【0099】
図11は、本発明の実施形態に係る管理装置100におけるマルチフォールド処理の他の例を示す説明図である。ここで、図11は、上記のように特定のブロックを除外した上で、ブロックを選択する場合における処理の一例を示している。また、図11は、図8と同様に、不揮発性メモリの各ブロックの状態を時系列(図11(a)〜図11(h))で示している。また、図11は、管理装置100が、図8と同様の開始条件、停止条件にてフォールド処理を行う例を示している。また、図11は、(i)LTU0〜LTU11の書き込み、(ii)LTU13、LTU14の書き込みの割り込み、(iii)LTU0〜LTU11の上書き、が行われる場合における処理の一例を示している。
【0100】
図11(a)は、LTU0〜LTU11が書き込まれた直後(上記(i)の直後)の不揮発性メモリの状態を示している。また、図11(b)は、図11(a)の状態においてLTU13、LTU14が書き込まれた直後(上記(ii)の直後)の不揮発性メモリの状態を示している。
【0101】
図11(b)の状態において、LTU0およびLTU1の書き込みが行われると(図11(c))、管理装置100は、開始条件が満たされているか否かを判定する。LTU0およびLTU1の書き換えによって開始条件が満たされるので、管理装置100は、1回目のフォールド処理を行う(図11(d))。このとき、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック(図11における左端のブロック)を、フォールド処理の対象から除外する。図11(d)では、図11における左端から4番目のブロックがフォールド処理の対象として選択された場合を示している。
【0102】
1回目のフォールド処理を行うと、管理装置100は、停止条件を満たしているか否かを判定する。図11(d)の状態では、停止条件は満たされていないので、管理装置100は、2回目のフォールド処理を行う(図11(e))。このとき、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロック(図11における左端のブロック)を、フォールド処理の対象から除外する。図11(e)では、図11における左端から6番目のブロックがフォールド処理の対象として選択された場合を示している。
【0103】
2回目のフォールド処理を行うと、管理装置100は、上記停止条件を満たしているか否かを判定する。図11(e)の状態では、停止条件は満たされているので、管理装置100は、マルチフォールド処理を終了する。
【0104】
次に、図11(e)の状態において、LTU2およびLTU3の書き込みが行われると(図11(f))、管理装置100は、開始条件が満たされているか否かを判定する。図11(f)の状態は開始条件を満たしていないので、管理装置100は、フォールド処理を行わない。また、図11(f)に示す状態では、図11における左端のブロックに含まれる全ての物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となっているので、管理装置100は、図11における左端のブロックを消去する(図11(g))。
【0105】
また、図11(g)の状態において、LTU4およびLTU5の書き込みが行われると(図11(h))、管理装置100は、開始条件が満たされているか否かを判定する。図11(h)の状態は開始条件を満たしていないので、管理装置100は、フォールド処理を行わない。
【0106】
管理装置100は、LTU6〜LTU11についても、図11(f)〜図11(h)と同様に書き換えを行う。ここで、図11(f)〜図11(h)に示すように、管理装置100は、LTU2〜LTU5の書き換えにおいてはフォールド処理を行っておらず、消去を行うことによって、書き換えを行っている。したがって、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、不揮発性メモリの空き領域の確保の効率化を図ると共に、より効率的なデータの書き換えを実現することができる。
【0107】
また、例えばサイズが大きなファイルの上書きを行うようなケースでは、過去に行われた論理トランスレーションユニットのアクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。よって、管理装置100は、直近にデータを書き込んだ論理トランスレーションユニットが直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、フォールド処理の対象から除外することによって、上記のようにサイズが大きなファイルの上書きを行うようなケースにおいても、図11に示すように、より効率的なデータの書き換えを実現することができる。
【0108】
管理装置100は、例えば図8〜図11に示すようなマルチフォールド処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理装置100におけるマルチフォールド処理が、図8〜図11に示す例に限られないことは、言うまでもない。
【0109】
[本発明の実施形態に係る、管理方法に係る処理の具体例]
次に、上述した本発明の実施形態に係る管理方法に係る処理について、より具体的に説明する。図12は、本発明の実施形態に係る管理方法に係る処理の一例を示す流れ図である。以下では、管理方法に係る処理を管理装置100が行うものとして説明する。
【0110】
管理装置100は、指定されたデータを書き込む(S100:書き込み処理)。
【0111】
〔書き込み処理の一例〕
図13は、本発明の実施形態に係るデータの書き込み処理の一例を示す流れ図である。
【0112】
管理装置100は、直前に書き込まれた物理TUが、ブロックにおける最後の物理TUであるか否かを判定する(S200)。ステップS200においてブロックにおける最後の物理TUであると判定されない場合には、管理装置100は、上記ブロックの次のPTUを、書き込み対象PTUとして設定し(S202)、後述するステップS206からの処理を行う。
【0113】
また、ステップS200においてブロックにおける最後の物理TUであると判定された場合には、管理装置100は、ブロックにおける先頭の物理TUが“未書き込みの物理TU”であるブロックを選択し、選択したブロックの先頭の物理TUを、書き込み対象PTUとして設定する(S204)。
【0114】
ステップS202またはステップS204において書き込み対象PTUが設定されると、管理装置100は、当該書き込み対象PTUに指定されたデータを書き込む(S206)。そして、管理装置100は、論理アドレス−物理アドレス変換に係る、論理アドレス−物理アドレス変換テーブル(論物変換テーブル)および物理TU状態マップを更新する(S208)。
【0115】
管理装置100は、例えば図13に示す処理を行うことによって、データの書き込みを行う。なお、本発明の実施形態に係る書き込み処理が、図13に示す例に限られないことは、言うまでもない。
【0116】
再度図12を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップS100においてデータの書き込みが行われると、管理装置100は、フォールド処理の開始条件を満たすか否かを判定する(S102)。
【0117】
ステップS102においてフォールド処理の開始条件を満たすと判定されない場合には、管理装置100は、管理方法に係る処理を終了する。なお、本発明の実施形態に係る管理方法に係る処理は、一度終了すれば完了する類の処理ではなく、データの書き込みが発生するごとに繰り返し行われる。
【0118】
また、ステップS102においてフォールド処理の開始条件を満たすと判定された場合には、管理装置100は、マルチフォールド処理を行う(S106)。
【0119】
〔マルチフォールド処理の一例〕
図14は、本発明の実施形態に係るマルチフォールド処理の一例を示す流れ図である。
【0120】
管理装置100は、第1のマルチフォールド処理を行う(S300)。ここで、本発明の実施形態に係る第1のマルチフォールド処理とは、例えば、フォールド処理によって増えた“未書き込みの物理トランスレーションユニット”のサイズが、ブロックのサイズ以上となることを停止条件とするマルチフォールド処理である。
【0121】
<第1のマルチフォールド処理の一例>
図15は、本発明の実施形態に係る第1のマルチフォールド処理の一例を示す説明図である。
【0122】
管理装置100は、“n_clean”の値をn_clean=0(ゼロ)に設定し、“n_copy_max”の値をn_copy_max=M(Mは、ブロックに含まれる物理TU数よりも十分に大きい値。)に設定する(S400)。ここで、“n_clean”とは、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を保持するために用いられる。また、“n_copy_max”は、後述するフォールド処理において判定に用いられる。また、ステップS400の処理は、“n_clean”の値を初期化する処理に該当する。
【0123】
ステップS400において初期化処理が行われると、管理装置100は、フォールド処理を実行する(S402)。
【0124】
{フォールド処理の一例}
図16は、本発明の実施形態に係るフォールド処理の一例を示す流れ図である。
【0125】
管理装置100は、“n_copy”の値をn_copy=0(ゼロ)に設定する(S500)。ここで、“n_copy”は、データをコピーした物理TU数を保持するための、一種のカウンタである。また、ステップS500の処理は、“n_copy”の値を初期化する処理に該当する。
【0126】
ステップS500の処理が行われると、管理装置100は、フォールド処理の対象となるブロック(以下、「フォールド対象ブロック」と示す。)を選択する(S502)。ここで、管理装置100は、例えば、不揮発性メモリにおけるブロックの中から、“書き込み済みの無効な物理トランスレーションユニット”の数がより多いブロックを、フォールド対象ブロックとして選択するが、選択方法は、上記に限られない。
【0127】
ステップS502においてフォールド対象ブロックが選択されると、管理装置100は、フォールド対象ブロックから未コピーの“書き込み済みの有効な物理TU”を選択する(S504)。ステップS504において未コピーの“書き込み済みの有効な物理TU”を選択すると、管理装置100は、選択した物理TU内のデータを読み込み(S506)、読み込んだデータを、コピー先のブロックにおける未書き込みのPTUにコピーする(S508)。そして、管理装置100は、“n_copy”の値を、n_copy=n_copy+1に更新する(S510)。
【0128】
ステップS510の処理が行われると、管理装置100は、フォールド対象ブロックが含むすべての書き込み済みの有効な物理TUのデータのコピーが完了したか否かを判定する(S512)。
【0129】
ステップS512においてデータのコピーが完了したと判定されない場合には、管理装置100は、「n_copy≧n_copy_max」であるか否かを判定する(S514)。第1のマルチフォールド処理では、“n_copy_max”の値としてM(Mは、ブロックに含まれる物理TU数よりも十分に大きい値。)が設定されているので、管理装置100は、ステップS504からの処理を繰り返す。また、後述する第2のマルチフォールド処理では、“n_copy_max”の値が、M以外の値に設定されうるので、管理装置100は、ステップS514の判定結果に応じて選択的にステップS504からの処理を繰り返す。
【0130】
また、ステップS512においてデータのコピーが完了したと判定された場合には、管理装置100は、フォールド対象ブロックを消去して(S506)、フォールド処理を終了する。
【0131】
管理装置100は、例えば図16に示す処理を行うことによって、フォールド処理を実現する。なお、本発明の実施形態に係るフォールド処理が、図16に示す例に限られないことは、言うまでもない。
【0132】
再度図15を参照して、本発明の実施形態に係る第1のマルチフォールド処理の一例について説明する。ステップS402においてフォールド処理が行われると、管理装置100は、“n_clean”の値に、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの数を加える(S404)。そして、管理装置100は、“n_clean”の値が、1ブロックあたりの物理TU数以上であるか否かを判定する(S406)。
【0133】
ステップS406において、“n_clean”の値が1ブロックあたりの物理TU数以上であると判定されない場合には、管理装置100は、ステップS402からの処理を繰り返す。
【0134】
また、ステップS406において、“n_clean”の値が1ブロックあたりの物理TU数以上であると判定された場合には、管理装置100は、第1のマルチフォールド処理を終了する。
【0135】
管理装置100は、例えば図15に示す処理を行うことによって、第1のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第1のマルチフォールド処理が、図15に示す例に限られないことは、言うまでもない。
【0136】
再度図14を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップS300の処理が行われると、管理装置100は、フォールド処理を行うことによって増えた未書き込みの物理トランスレーションユニットの合計サイズが、1ブロックのサイズを超えたか否かを判定する(S302)。ここで、管理装置100は、例えば、“n_clean”の値が1ブロックあたりの物理TU数を超えている場合に、1ブロックのサイズを超えたと判定するが、ステップS302における判定方法は、上記に限られない。
【0137】
ステップS302において1ブロックのサイズを超えたと判定されない場合には、管理装置100は、第2のマルチフォールド処理を行う(S304)。ここで、本発明の実施形態に係る第2のマルチフォールド処理とは、例えば図9に示すように、1ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)を超えるサイズ分を“書き込み済みの有効な物理トランスレーションユニット”のデータで埋める、マルチフォールド処理である。
【0138】
<第2のマルチフォールド処理の一例>
図17は、本発明の実施形態に係る第2のマルチフォールド処理の一例を示す説明図である。
【0139】
管理装置100は、“n_exess”の値をn_exess=n_clean−(1ブロックあたりの物理TU数)に設定し、“n_copy”の値をn_copy=0(ゼロ)に設定する(S600)。ここで、“n_exess”とは、1ブロックのサイズを超えたサイズ分に相当する物理TU数を示す。また、ステップS600の処理は、“n_copy”の値を初期化する処理に該当する。
【0140】
ステップS600の処理が行われると、管理装置100は、“n_copy_max”の値をn_copy_max=n_exess−n_copyに設定する(S602)。
【0141】
ステップS602の処理が行われると、管理装置100は、フォールド処理を実行する(S604)。ここで、管理装置100は、フォールド処理として例えば図16に示す処理を行う。
【0142】
ステップS604の処理が行われると、管理装置100は、“n_copy”の値を、n_copy=n_copy+(フォールド処理においてコピーされた物理TU数)に更新する(S606)。
【0143】
ステップS606の処理が行われると、管理装置100は、n_copy=n_exessであるか否かを判定する(S608)。ステップS608においてn_copy=n_exessであると判定されない場合には、管理装置100は、ステップS602からの処理を繰り返す。
【0144】
また、ステップS608においてn_copy=n_exessであると判定された場合には、管理装置100は、第2のマルチフォールド処理を終了する。
【0145】
管理装置100は、例えば図17に示す処理を行うことによって、第2のマルチフォールド処理を実現する。なお、本発明の実施形態に係る第2のマルチフォールド処理が、図17に示す例に限られないことは、言うまでもない。
【0146】
再度図14を参照して、本発明の実施形態に係るマルチフォールド処理の一例について説明する。ステップS302において1ブロックのサイズを超えたと判定されない場合には、管理装置100は、マルチフォールド処理を終了する。
【0147】
管理装置100は、例えば図14に示す処理を行うことによって、マルチフォールド処理を実現する。なお、本発明の実施形態に係るマルチフォールド処理は、図14に示す例に限られない。例えば、管理装置100は、マルチフォールド処理として、図15に示す第1のマルチフォールド処理のみを行ってもよい。
【0148】
再度図12を参照して、本発明の実施形態に係る管理方法に係る処理について説明する。ステップS106においてマルチフォールド処理が終了すると、管理装置100は、管理方法に係る処理を終了する。
【0149】
管理装置100は、例えば図12に示す処理を行うことによって、上述した本発明の実施形態に係る管理方法を実現することができる。したがって、管理装置100は、例えば図12に示す処理を行うことによって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。なお、本発明の実施形態に係る管理方法に係る処理が、図12に示す例に限られないことは、言うまでもない。
【0150】
(本発明の実施形態に係る管理装置)
次に、上述した本発明の実施形態に係る管理方法に係る処理を行うことが可能な、本発明の実施形態に係る管理装置100の構成について説明する。
【0151】
図18は、本発明の実施形態に係る管理装置100の構成の一例を示すブロック図である。管理装置100は、例えば、不揮発性メモリ102と、制御部104とを備える。
【0152】
また、管理装置100は、例えば、ROM(Read Only Memory。図示せず)や、RAM(Random Access Memory。図示せず)、ユーザが操作可能な操作部(図示せず)、様々な画面を表示画面に表示する表示部(図示せず)、外部装置と通信を行うための通信部(図示せず)などを備えていてもよい。管理装置100は、例えば、データの伝送路としてのバス(bus)により上記各構成要素間を接続する。
【0153】
ROM(図示せず)は、制御部104が使用するプログラムや演算パラメータなどの制御用データを記憶する。RAM(図示せず)は、制御部104により実行されるプログラムなどを一時的に記憶する。操作部(図示せず)としては、例えば後述する操作デバイスが挙げられ、表示部(図示せず)としては、例えば後述する表示デバイスが挙げられる。また、通信部(図示せず)としては、例えば後述する通信インタフェースが挙げられる。
【0154】
〔管理装置100のハードウェア構成例〕
図19は、本発明の実施形態に係る管理装置100のハードウェア構成の一例を示す説明図である。図19を参照すると、管理装置100は、例えば、MPU150と、ROM152と、RAM154と、記録媒体156と、入出力インタフェース158と、操作入力デバイス160と、表示デバイス162と、通信インタフェース164とを備える。また、管理装置100は、例えば、データの伝送路としてのバス166で各構成要素間を接続する。
【0155】
MPU150は、MPU(Micro Processing Unit)や、制御機能などの各種機能を実現するための各種回路が集積された集積回路などで構成され、管理装置100全体を制御する制御部104として機能する。また、MPU150は、管理装置100において、後述する判定部110、および管理部112としての役目を果たすこともできる。
【0156】
ROM152は、例えばMPU150が使用するプログラムや演算パラメータなどの制御用データを記憶し、また、RAM154は、例えばMPU150により実行されるプログラムなどを一次的に記憶する。
【0157】
記録媒体156は、管理装置100における記憶手段であり、不揮発性メモリ102として機能する。記録媒体156には、例えば、アプリケーションや様々なデータなどが記憶される。ここで、記録媒体156としては、例えば、フラッシュメモリなどが挙げられる。また、記録媒体156は、管理装置100から着脱可能であってもよい。
【0158】
入出力インタフェース158は、例えば、操作入力デバイス160や、表示デバイス162を接続する。操作入力デバイス160は、操作部(図示せず)として機能し、また、表示デバイス162は、表示部(図示せず)として機能する。ここで、入出力インタフェース160としては、例えば、USB(Universal Serial Bus)端子や、DVI(Digital Visual Interface)端子、HDMI(High-Definition Multimedia Interface)端子、各種処理回路などが挙げられる。また、操作入力デバイス160は、例えば、管理装置100上に備えられ、管理装置100の内部で入出力インタフェース158と接続される。操作入力デバイス160としては、例えば、ボタン、方向キー、ジョグダイヤルなどの回転型セレクター、あるいは、これらの組み合わせなどが挙げられる。また、表示デバイス162は、例えば、管理装置100上に備えられ、管理装置100の内部で入出力インタフェース158と接続される。表示デバイス162としては、例えば、液晶ディスプレイ(Liquid Crystal Display;LCD)や有機ELディスプレイ(organic ElectroLuminescence display。または、OLEDディスプレイ(Organic Light Emitting Diode display)ともよばれる。)などが挙げられる。なお、入出力インタフェース158が、管理装置100の外部装置としての操作入力デバイス(例えば、キーボードやマウスなど)や表示デバイス(例えば、外部ディスプレイなど)と接続することも可能であることは、言うまでもない。また、表示デバイス162は、例えばタッチスクリーンなどのように、表示とユーザ操作とが可能なデバイスであってもよい。
【0159】
通信インタフェース164は、管理装置100が備える通信手段であり、ネットワークを介して(あるいは、直接的に)外部装置と無線/有線で通信を行うための通信部(図示せず)として機能する。ここで、通信インタフェース164としては、例えば、通信アンテナおよびRF(Radio Frequency)回路(無線通信)や、LAN端子および送受信回路(有線通信)などが挙げられる。なお、本発明の実施形態に係る通信インタフェース164は、上記に限られず、例えば、ネットワークに対応する構成をとることができる。
【0160】
管理装置100は、例えば図19に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。なお、本発明の実施形態に係る管理装置100のハードウェア構成は、図19に示す構成に限られない。例えば、管理装置100は、本発明の実施形態に係る管理方法に係る処理を行う機能(例えば、後述する判定部110および管理部112が有する機能)を実現するためのIC(Integrated Circuit)であってもよい。
【0161】
再度図18を参照して、管理装置100の構成の一例について説明する。不揮発性メモリ102は、管理装置100が備える記憶手段である。ここで、不揮発性メモリ102としては、例えば、フラッシュメモリなどが挙げられる。不揮発性メモリ102は、制御部104(より具体的には、後述する判定部110、および管理部112)によって、データの書き込み、読み出し、消去などが管理される。
【0162】
制御部104は、例えば、MPUなどで構成され、管理装置100全体を制御する役目を果たす。また、制御部104は、判定部110と、管理部112とを備え、本発明の実施形態に係る管理方法に係る処理を主導的に行う役目を果たす。
【0163】
判定部110は、上記(1)の処理(開始条件判定処理)を主導的に行う役目を果たす。より具体的には、判定部110は、フォールド処理を開始するための開始条件を満たすか否かを判定する。そして、判定部110は、当該開始条件を満たすと判定した場合に、例えばフォールド処理を開始させるための処理開始要求(一種のトリガ)を管理部112へ伝達する。
【0164】
管理部112は、上記(2)の処理(フォールド処理)を主導的に行う役目を果たす。より具体的には、管理部112は、例えば、上記処理開始要求が伝達された場合にフォールド処理を選択的に開始する。また、管理部112は、例えば、フォールド処理を開始した場合には、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーする。また、管理部112は、例えば、フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、ブロックのサイズ(ブロックのサイズを基準とする所定のサイズの一例)以上となるまで、フォールド処理を繰り返す。
【0165】
制御部104は、例えば、判定部110、および管理部112を備えることによって、上記(1)の処理(開始条件判定処理)、(2)の処理(フォールド処理)を行う。したがって、制御部104は、例えば、判定部110、および管理部112を備えることによって、上述した本発明の実施形態に係る管理方法に係る処理を実現することができるので、不揮発性メモリ102における空き領域の確保の効率化を図ることができる。
【0166】
なお、本発明の実施形態に係る制御部104の構成は、図18に示す例に限られない。例えば、本発明の実施形態に係る制御部104は、判定部110を備えない構成をとることもできる。上記の構成の場合であっても、本発明の実施形態に係る管理装置100は、例えば操作部(図示せず)から伝達される、フォールド処理の開始を要求する操作信号に基づいて、上記(2)の処理(フォールド処理)を行うことが可能である。
【0167】
管理装置100は、例えば図18に示す構成によって、上述した本発明の実施形態に係る管理方法に係る処理を行う。したがって、管理装置100は、不揮発性メモリ102における空き領域の確保の効率化を図ることができる。
【0168】
なお、本発明の実施形態に係る管理装置100の構成は、図18に示す構成に限られない。例えば、本発明の実施形態に係る管理装置100は、不揮発性メモリ102を備えず、有線/無線で接続された外部装置が備える不揮発性メモリにおけるデータの書き込み、読み出し、消去などを管理する構成であってもよい。上記の構成の場合であっても、本発明の実施形態に係る管理装置100は、外部装置が備える不揮発性メモリにおける空き領域の確保の効率化を図ることができる。
【0169】
以上のように、本発明の実施形態に係る管理装置100は、従来の技術がフォールド処理を1回だけ行うのに対して、所定の停止条件を満たすまで繰り返しフォールド処理を行う(マルチフォールド処理)。ここで、不揮発性メモリを使用する側が、例えばFATシステムなどのファイルシステムである場合、ある論理トランスレーションユニットのアクセスパターン(書き換え順序)で書き換えが行われたときには、将来的に当該アクセスパターンと同じアクセスパターンで書き換えが行われる可能性が高い。管理装置100がマルチフォールド処理を行うことによって、上記のように将来的に同じ論理トランスレーションユニットのアクセスパターンで書き換えが行われた場合には、書き換えを行ったブロックに含まれる物理トランスレーションユニットが“書き込み済みの無効な物理トランスレーションユニット”となる。したがって、管理装置100は、例えば図6に示すような従来の技術に係るフォールド処理が行われた場合と比較して、不揮発性メモリの空き領域をより効率的に確保することができる。
【0170】
また、管理装置100は、不揮発性メモリの空き領域をより効率的に確保することができるので、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【0171】
また、管理装置100は、データの書き込みに係る条件を含む開始条件を満たしたときにフォールド処理を行うので、マルチフォールド処理を、例えば、データの書き込みを行う際に分散して行うことが可能である。よって、管理装置100は、バックグラウンドの処理としてフォールド処理を行わなくてもよいので、例えば、バックグラウンドの処理としてフォールド処理が突然行われることによる他の処理への影響(例えば処理パフォーマンスの低下など)を防止することができる。
【0172】
さらに、管理装置100は、不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないこと(言い換えれば、システムがいわゆるアイドル状態にあること)を開始条件とすることが可能である。よって、上記の場合には、管理装置100は、システムのアイドル状態を有効に活用することができる。
【0173】
以上、本発明の実施形態として管理装置100を挙げて説明したが、本発明の実施形態は、かかる形態に限られない。本発明の実施形態は、例えば、不揮発性メモリを用いる記憶装置、PC(Personal Computer)やサーバなどのコンピュータ、テレビ受像機などの表示装置、携帯電話などの携帯型通信装置、映像/音楽再生装置(または映像/音楽記録再生装置)、ゲーム機など、様々な機器に適用することができる。また、本発明の実施形態は、例えば、上記のような様々な機器に組み込まれる記録媒体の制御ICに適用することもできる。
【0174】
(本発明の実施形態に係るプログラム)
コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム(例えば、上記(1)の処理(開始条件判定処理)および(2)の処理(フォールド処理)や、上記(2)の処理(フォールド処理)など、本発明の実施形態に係る管理方法に係る処理を実現するためのプログラム)によって、不揮発性メモリにおける空き領域の確保の効率化を図ることができる。また、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラムによって、ユーザからみた、不揮発性メモリにおけるデータの書き換えのパフォーマンスの向上や、NANDフラッシュメモリなどのような不揮発性メモリの長寿命化を図ることができる。
【0175】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【0176】
例えば、本発明の実施形態に係る管理装置は、図18に示す判定部110、および管理部112を個別に備える(例えば、それぞれを個別の処理回路で実現する)ことができる。
【0177】
また、上記では、コンピュータを、本発明の実施形態に係る管理装置として機能させるためのプログラム(コンピュータプログラム)が提供されることを示したが、本発明の実施形態は、さらに、上記プログラムをそれぞれ記憶させた記録媒体も併せて提供することができる。
【0178】
上述した構成は、本発明の実施形態の一例を示すものであり、当然に、本発明の技術的範囲に属するものである。
【符号の説明】
【0179】
10、100 管理装置
102 不揮発性メモリ
104 制御部
110 判定部
112 管理部
【特許請求の範囲】
【請求項1】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、
前記管理部は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理装置。
【請求項2】
前記管理部は、前記フォールド処理を行った後、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、前記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーする、請求項1に記載の管理装置。
【請求項3】
前記管理部における前記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、
前記管理部は、前記判定部において前記開始条件を満たすと判定された場合に、選択的に前記フォールド処理を行う、請求項1、または2のいずれか1項に記載の管理装置。
【請求項4】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている前記ブロックの数が所定の閾値より大きいまたは前記閾値以上であることを前記開始条件として、前記判定を行う、請求項3に記載の管理装置。
【請求項5】
前記判定部は、さらに、前記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを前記開始条件として、前記判定を行う、請求項4に記載の管理装置。
【請求項6】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない前記ブロックの数が所定の閾値より小さいまたは前記閾値以下であることを前記開始条件として、前記判定を行う、請求項3に記載の管理装置。
【請求項7】
前記管理部は、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、前記ブロックのサイズの所定の整数倍以上となるまで前記フォールド処理を繰り返す、請求項1、または2のいずれか1項に記載の管理装置。
【請求項8】
前記管理部は、前記不揮発性メモリにおける前記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、前記フォールド処理におけるコピー元のブロックとして選択する、請求項1、または2のいずれか1項に記載の管理装置。
【請求項9】
前記管理部は、前記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが前記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、前記フォールド処理の対象から除外する、請求項1、または2のいずれか1項に記載の管理装置。
【請求項10】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項11】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項12】
前記管理部は、前記フォールド処理を行う場合には、繰り返し行われる前記フォールド処理においてコピー元となる全てのブロックにおける前記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した前記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した前記物理トランスレーションユニットのデータをコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項13】
前記不揮発性メモリをさらに備える、請求項1、または2のいずれか1項に記載の管理装置。
【請求項14】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップと、
を有し、
前記管理するステップでは、前記判定するステップにおいて前記開始条件を満たすと判定された場合に、前記フォールド処理が選択的に行われ、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理方法。
【請求項15】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、
前記管理手段は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、プログラム。
【請求項1】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理部を備え、
前記管理部は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理装置。
【請求項2】
前記管理部は、前記フォールド処理を行った後、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズで割り切れない場合には、端数のサイズに対応する未書き込みの物理トランスレーションユニットのサイズ分、前記フォールド処理によって書き込み済みの有効な物理トランスレーションユニットのデータをコピーする、請求項1に記載の管理装置。
【請求項3】
前記管理部における前記フォールド処理を開始するための開始条件を満たすか否かを判定する判定部をさらに備え、
前記管理部は、前記判定部において前記開始条件を満たすと判定された場合に、選択的に前記フォールド処理を行う、請求項1、または2のいずれか1項に記載の管理装置。
【請求項4】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれている前記ブロックの数が所定の閾値より大きいまたは前記閾値以上であることを前記開始条件として、前記判定を行う、請求項3に記載の管理装置。
【請求項5】
前記判定部は、さらに、前記不揮発性メモリに対するデータの書き込み、読み出し、消去が行われていないことを前記開始条件として、前記判定を行う、請求項4に記載の管理装置。
【請求項6】
前記判定部は、前記管理部が直近にデータを書き込んだ書き込み先が前記ブロックにおける最終の物理トランスレーションユニットであり、かつ、データが書き込まれていない前記ブロックの数が所定の閾値より小さいまたは前記閾値以下であることを前記開始条件として、前記判定を行う、請求項3に記載の管理装置。
【請求項7】
前記管理部は、前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となったとしてもフォールド処理を停止せず、前記ブロックのサイズの所定の整数倍以上となるまで前記フォールド処理を繰り返す、請求項1、または2のいずれか1項に記載の管理装置。
【請求項8】
前記管理部は、前記不揮発性メモリにおける前記ブロックの中から、書き込み済みの無効な物理トランスレーションユニットの数がより多いブロックを、前記フォールド処理におけるコピー元のブロックとして選択する、請求項1、または2のいずれか1項に記載の管理装置。
【請求項9】
前記管理部は、前記フォールド処理を行う場合には、直近にデータを書き込んだ論理トランスレーションユニットが前記直近の書き込み前に対応していた物理トランスレーションユニットを含むブロックを、前記フォールド処理の対象から除外する、請求項1、または2のいずれか1項に記載の管理装置。
【請求項10】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、物理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項11】
前記管理部は、前記フォールド処理を行う場合には、前記ブロック内の前記書き込み済みの有効な物理トランスレーションユニットのデータを、それぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順にコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項12】
前記管理部は、前記フォールド処理を行う場合には、繰り返し行われる前記フォールド処理においてコピー元となる全てのブロックにおける前記書き込み済みの有効な物理トランスレーションユニットを特定し、特定した前記物理トランスレーションユニットそれぞれに対応する論理トランスレーションユニットそれぞれに付された番号が小さい順に、特定した前記物理トランスレーションユニットのデータをコピーする、請求項1、または2のいずれか1項に記載の管理装置。
【請求項13】
前記不揮発性メモリをさらに備える、請求項1、または2のいずれか1項に記載の管理装置。
【請求項14】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理するステップと、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を開始するための開始条件を満たすか否かを判定するステップと、
を有し、
前記管理するステップでは、前記判定するステップにおいて前記開始条件を満たすと判定された場合に、前記フォールド処理が選択的に行われ、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、管理方法。
【請求項15】
電気的にデータの書き込み、読み出し、消去が可能であり、書き込みおよび読み出しはページ単位で行われ、消去は複数のページを含むブロック単位で行われる不揮発性メモリにおけるデータの書き込み、読み出し、消去を、前記ブロックのサイズの整数分の1、かつ前記ページのサイズの整数倍のトランスレーションユニット単位で論理アドレス−物理アドレス変換を行うことによって管理し、
前記ブロックの内容のうち、書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックへコピーし、コピー元の前記ブロックを消去することによって、コピー元の前記ブロックに含まれていた書き込み済みの無効な物理トランスレーションユニットの数分、未書き込みの物理トランスレーションユニットを増やす、フォールド処理を行う管理手段としてコンピュータを機能させ、
前記管理手段は、
前記フォールド処理を開始した場合には、前記書き込み済みの有効な物理トランスレーションユニットのデータを、未書き込みの物理トランスレーションユニットがあるブロックのうちの、先頭の物理トランスレーションユニットが未書き込みであるブロックへとコピーし、
前記フォールド処理によって増えた未書き込みの物理トランスレーションユニットのサイズが、前記ブロックのサイズ以上となるまで、前記フォールド処理を繰り返す、プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【公開番号】特開2012−133655(P2012−133655A)
【公開日】平成24年7月12日(2012.7.12)
【国際特許分類】
【出願番号】特願2010−286318(P2010−286318)
【出願日】平成22年12月22日(2010.12.22)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
【公開日】平成24年7月12日(2012.7.12)
【国際特許分類】
【出願日】平成22年12月22日(2010.12.22)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
[ Back to top ]