(57)【特許請求の範囲】
【請求項１】
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理手段と、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対する断片化解消処理を開始する断片化解消処理手段と、
を備え、
前記断片化解消処理手段は、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される記憶制御装置。
【請求項２】
前記第１閾値および前記第２閾値は、少なくとも、前記記憶媒体に含まれる前記論理アドレス領域の総数と、前記記憶媒体に含まれる有効なデータが格納されている前記論理アドレス領域の数と、前記記憶媒体に対する単位時間当たりの書き込みデータ量に相当する前記論理アドレス領域の数と、前記記憶媒体に含まれる断片化されて記憶されていると判定された前記論理アドレス領域のデータの平均更新間隔と、を考慮して算出される、請求項１に記載の記憶制御装置。
【請求項３】
前記第１閾値と前記第２閾値とは同じ数に設定され、
前記断片化解消処理手段は、断片化されて記憶されていると推定された前記論理アドレス領域の数が前記同じ数となるように前記断片化解消処理を行なう、請求項１または２に記載の記憶制御装置。
【請求項４】
前記断片化管理手段は、断片化されて記憶されていると推定された前記論理アドレス領域について、前記断片化解消処理を行なう優先順位をさらに設定し、
前記断片化解消処理手段は、前記優先順位にしたがって前記断片化解消処理を行なう、請求項１乃至３のいずれか１項に記載の記憶制御装置。
【請求項５】
前記優先順位は、前記論理アドレス領域のデータを更新する更新頻度の低い順に設定される、請求項４に記載の記憶制御装置。
【請求項６】
前記断片化管理手段は、各々の前記論理アドレス領域を再分割した再分割領域に対するWrite処理または削除処理の発生分布に基づいて、前記論理アドレス領域のデータが断片化されて記憶されていると推定する、請求項１乃至５のいずれか１項に記載の記憶制御装置。
【請求項７】
前記断片化管理手段は、前記再分割領域への初めてのWrite処理または削除処理が発生した回数を断片化発生数として累積し、前記断片化発生数が第３閾値を上回る場合に前記論理アドレス領域のデータが断片化されて記憶されていると推定する、請求項６に記載の記憶制御装置。
【請求項８】
前記断片化解消処理手段は、断片化されて記憶されている前記論理アドレス領域のデータを読み出して、同じ前記論理アドレス領域への再格納をすることによって、前記断片化解消処理を行う、請求項１乃至７のいずれか１項に記載の記憶制御装置。
【請求項９】
前記断片化解消処理手段は、前記断片化解消処理中、他の書き込みを制限する、請求項８に記載の記憶制御装置。
【請求項１０】
前記記憶媒体は、追記形式で記憶素子に対するデータ格納を行う記憶媒体であり、ＳＳＤ（Solid State Drive）とＳＭＲ(Shingled Magnetic Recording)を採用したＨＤＤとを含む、請求項１乃至９のいずれか１項に記載の記憶制御装置。
【請求項１１】
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理ステップと、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対して断片化解消処理を開始する断片化解消処理ステップと、
を含み、
前記断片化解消処理ステップにおいては、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される記憶制御方法。
【請求項１２】
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理ステップと、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対して断片化解消処理を開始する断片化解消処理ステップと、
をコンピュータに実行させる記憶制御プログラムであって、
前記断片化解消処理ステップにおいては、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される記憶制御プログラム。
【請求項１３】
記憶媒体と、
論理アドレス空間の論理アドレス領域を指定して、前記記憶媒体へのアクセスを行うアクセス手段と、
前記アクセス手段において指定された論理アドレス領域に基づいて、前記記憶媒体からのデータの読み出しおよび前記記憶媒体へのデータの書き込みを行う記憶制御手段と、
を備えた情報処理システムであって、
前記記憶制御手段は、
前記アクセス手段が前記記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理手段と、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対する断片化解消処理を開始し、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで、前記断片化解消処理を継続する断片化解消処理手段と、
を備え、
前記断片化解消処理手段は、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、記憶制御装置、記憶制御方法および記憶制御プログラムに関する。
【背景技術】
【０００２】
近年、記憶素子にNANDフラッシュメモリ（以下、NANDフラッシュと称す）を用いたＳＳＤ(Solid State Drive)が記憶媒体として普及している。また、従来から記憶媒体として用いられるＨＤＤ(Hard Disk Drive)についても、大容量化技術としてＳＭＲ(Shingled Magnetic Recording)を採用したＨＤＤが普及しつつある。これらの記憶媒体で用いられる記憶素子は、記憶領域に対してデータを非連続に格納することが困難である。そのため、これらの記憶媒体の多くは、計算機からのデータアクセスを容易にするために、記憶領域に対して追記形式でデータを格納する。
【０００３】
このような追記形式では、記憶媒体を使用するホストコンピュータから指定された格納先のアドレスによらず、データを空き領域に対して連続的に格納する。そのため、記憶媒体は、外部のホストコンピュータが参照するアドレス空間と、記憶素子上の物理的な記憶領域との対応関係を管理する。更新または削除などによって無効化されたデータを格納した記憶領域は、外部のホストコンピュータが参照するアドレス空間と対応しない、空き領域として再利用される。
【０００４】
しかし、追記形式でデータを格納する記憶媒体において、空き領域をそのまま再利用することは不可能である。例えば、ＳＳＤで用いられるNANDフラッシュでは、データの更新時に格納済の古いデータを消去(Erase)して初期化を行う必要がある。このNANDフラッシュに対するEraseは、ReadおよびWriteの最小単位であるページを複数含んだ、ブロックを単位として行う。ＳＭＲを採用したＨＤＤでも同様に、ゾーンと呼ばれる連続的にデータを格納する領域を再利用する前に、ゾーン全体の初期化が必要である。つまり、初期化対象の記憶領域は有効なデータが含まれない、連続した空き領域であることが求められる。
【０００５】
そのため、追記形式でデータを格納するＳＳＤやＳＭＲを採用したＨＤＤなどの記憶媒体では、空き領域を回収して再利用可能な連続した空き領域を確保するＧＣ(Garbage Collection：ガベージコレクション)が行われる。ＧＣでは連続した空き領域を確保するために、回収対象の記憶領域に含まれる有効なデータを事前に用意した他の書き込み可能な記憶領域に移動して、移動元の記憶領域を空き領域に変更する。記憶媒体内のＧＣに伴うデータの移動量は、回収対象の記憶領域に含まれる有効なデータ量に比例するため、回収対象領域の有効データ量の増加に従いホストコンピュータからのデータを格納するために使用可能な容量が減少する。つまり、記憶媒体に格納されたデータ容量の増加、もしくはデータの格納、更新を繰り返して記憶媒体内の空き領域の断片化が進行すると、回収対象の記憶領域に含まれる有効なデータ量が増加することで、ホストコンピュータから格納されるデータ量に対するＧＣの頻度が増加する。ＧＣ頻度の増加は記憶媒体内のデータ移動に伴う、ホストコンピュータから記憶媒体に対するアクセス性能の低下を引き起こす。
【０００６】
記憶媒体内のＧＣ頻度の増加による性能低下を防ぐ方法として、記憶領域で発生した断片化を事前に解消する方法が挙げられる。具体的には、記憶媒体がホストコンピュータに対して提供する論理アドレス空間上で連続に格納されたデータを、記憶素子上の連続した領域に再格納することで、データおよび空き領域の断片化を解消できる。例えば、特許文献１や非特許文献１では、ＳＳＤがホストコンピュータに提供する論理アドレス空間を分割した領域ごとに書き込みの頻度が低い領域の再書き込みを行うことで、断片化を解消してＳＳＤ内部の断片化解消処理の頻度を低減するための方法が示されている。記憶媒体内部において記憶領域の断片化を解消して、空き領域の分散を防ぎ連続した空き領域が発生しやすい状態とすることで、回収対象の記憶領域に含まれる有効なデータ量を削減する。その結果、回収対象の記憶領域における有効なデータ量の削減によって、ホストコンピュータからのデータを格納可能な容量が増加して、ＧＣの頻度低減が実現される。
【０００７】
例えば、特許文献１に示された技術では、記憶媒体がホストコンピュータに対して提供する論理アドレス空間を分割した領域毎の書き込み頻度を用いて断片化解消を行う領域を決定する。また、非特許文献１では、ＳＳＤに対してランダムWriteが行われた場合の、外部から書き込まれたデータ量に対するＳＳＤ内部で行われるＧＣに伴うデータ移動量の比率について、確率モデルを用いた計算方法を示している。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第5550741号
【非特許文献】
【０００９】
【非特許文献１】X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka. " Write amplification analysis in flash-based solid state drives. " In Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, pp.1-9
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、追記形式でデータを格納する記憶媒体に対して断片化解消処理を行う上記文献に記載の技術では、断片化解消処理の効果とコストの見積もりとによる、断片化解消対象の領域の決定は実施されていない。例えば、特許文献１に示された技術では、各領域の断片化を解消した場合のＧＣに与える影響は考慮されていない。また、非特許文献１では、ホストコンピュータからのデータ格納が一様かつランダムに行われることを仮定しており、アプリケーション等によって異なるホストコンピュータからのWriteアクセスパターンの変化、およびＳＳＤ内部のデータ格納状況に応じた計算は困難である。
【００１１】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明に係る記憶制御装置は、
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理手段と、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対する断片化解消処理を開始する断片化解消処理手段と、
を備え、
前記断片化解消処理手段は、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される。
【００１３】
上記目的を達成するため、本発明に係る記憶制御方法は、
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理ステップと、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対して断片化解消処理を開始する断片化解消処理ステップと、
を含み、
前記断片化解消処理ステップにおいては、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される。
【００１４】
上記目的を達成するため、本発明に係る記憶制御プログラムは、
ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理ステップと、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対して断片化解消処理を開始する断片化解消処理ステップと、
をコンピュータに実行させる記憶制御プログラムであって、
前記断片化解消処理ステップにおいては、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される。
【００１５】
上記目的を達成するため、本発明に係るシステムは、
記憶媒体と、
論理アドレス空間の論理アドレス領域を指定して、前記記憶媒体へのアクセスを行うアクセス手段と、
前記アクセス手段において指定された論理アドレス領域に基づいて、前記記憶媒体からのデータの読み出しおよび前記記憶媒体へのデータの書き込みを行う記憶制御手段と、
を備えた情報処理システムであって、
前記記憶制御手段は、
前記アクセス手段が前記記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、前記記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された前記論理アドレス領域の数を管理する断片化管理手段と、
断片化されて記憶されていると推定された前記論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された前記論理アドレス領域に対する断片化解消処理を開始し、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで、前記断片化解消処理を継続する断片化解消処理手段と、
を備え、
前記断片化解消処理手段は、断片化されて記憶されていると推定された前記論理アドレス領域の数が第２閾値を下回るまで前記断片化解消処理を継続し、
前記第１閾値および前記第２閾値は、前記断片化解消処理による前記記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される。
【発明の効果】
【００１６】
本発明によれば、断片化解消処理によって得られる記憶媒体内のＧＣによるデータ移動の削減効果を高め、記憶媒体のアクセス性能の向上および長寿命化を図ることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１実施形態に係る記憶制御装置の構成を示すブロック図である。
【図２】本発明の第２実施形態に係る記憶制御装置を含む情報処理システムの構成を示すブロック図である。
【図３】本発明の第２実施形態に係る記憶制御装置の機能構成を示すブロック図である。
【図４Ａ】本発明の第２実施形態に係る更新頻度管理テーブルの構成を示す図である。
【図４Ｂ】本発明の第２実施形態に係る断片化状態管理テーブルの構成を示す図である。
【図４Ｃ】本発明の第２実施形態に係る断片化解消対象リストの構成を示す図である。
【図４Ｄ】本発明の第２実施形態に係る断片化推定テーブルおよび断片化解消処理管理テーブルの構成を示す図である。
【図４Ｅ】本発明の第２実施形態に係る断片化推定条件設定テーブルおよび断片化解消処理条件設定テーブルの構成を示す図である。
【図５】本発明の第２実施形態に係る記憶制御部を含むホストコンピュータのハードウェア構成を示すブロック図である。
【図６】本発明の第２実施形態に係る記憶制御部の処理手順を示すフローチャートである。
【図７】本発明の第２実施形態に係るＲｅａｄ処理の手順を示すフローチャートである。
【図８】本発明の第２実施形態に係るＷｒｉｔｅ処理の手順を示すフローチャートである。
【図９】本発明の第２実施形態に係る断片化推定処理の手順を示すフローチャートである。
【図１０】本発明の第２実施形態に係る断片化解消処理の手順を示すフローチャートである。
【図１１】本発明の第３実施形態に係る記憶制御装置の機能構成を示すブロック図である。
【図１２】本発明の第３実施形態に係る断片化解消対象リストの構成を示す図である。
【図１３】本発明の第４実施形態に係る記憶制御部を含む情報処理システムの構成を示すブロック図である。
【図１４】本発明の第５実施形態に係る記憶制御部を含む情報処理システムの構成を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。
【００１９】
なお、本明細書で使用される文言「チャンク」は、ホストコンピュータなどの記憶媒体へのアクセス部における論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域を示す。例えば、記憶媒体がＳＳＤの場合は数10Ｍバイト単位、記憶媒体がＳＭＲを採用したＨＤＤの場合は数100Ｍバイト単位で分割した各々の論理アドレス領域を示す。また、本明細書では、ＧＣで回収した記憶領域に対する、ホストコンピュータからWriteされたデータの格納に使用可能な容量の比率を、「回収効率」と定義する。
【００２０】
［第１実施形態］
本発明の第１実施形態としての記憶制御装置１００について、図１を用いて説明する。記憶制御装置１００は、記憶媒体のデータの記憶を制御する装置である。
【００２１】
図１に示すように、記憶制御装置１００は、断片化管理部１０１と、断片化解消処理部１０２と、を含む。断片化管理部１０１は、ホストコンピュータが記憶媒体１１０にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域のデータが、記憶媒体１１０の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定された論理アドレス領域の数を管理する。断片化解消処理部１０２は、断片化されて記憶されていると推定された論理アドレス領域の数が第１閾値を超えた場合に、断片化されて記憶されていると推定された論理アドレス領域に対する断片化解消処理を開始する。
【００２２】
本実施形態によれば、論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域の断片化状態をホストコンピュータから推定し、断片化状態の論理アドレス領域の数に基づいて断片化解消処理をする。これにより、断片化解消処理によって得られる記憶媒体内のＧＣによるデータ移動の削減効果を高め、記憶媒体のアクセス性能の向上および長寿命化を図ることができる。
【００２３】
［第２実施形態］
次に、本発明の第２実施形態に係る記憶制御装置について説明する。本実施形態に係る記憶制御装置は、ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域である各チャンクのデータが、断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定されたチャンク数を管理する。そして、チャンク数が断片化解消処理開始条件を超えた場合に、断片化されて記憶されていると推定されたチャンクに対する断片化解消処理を開始し、チャンク数が断片化解消処理終了条件を下回るまで、断片化解消処理を継続する。なお、本実施形態においては、チャンク数が断片化解消処理終了条件を下回るまで断片化解消処理を継続する場合を説明するが、チャンク数が断片化解消処理開始条件を超えた場合に、断片化されて記憶されていると推定されたチャンクに対する断片化解消処理を開始する構成により、本実施形態の効果を奏することができる。
【００２４】
《本実施形態の技術的概要》
以下、本実施形態の技術的概要について、説明する。
【００２５】
記憶媒体内における記憶領域の断片化解消処理は、記憶素子に対するデータの再格納で実現される。すなわち、断片化解消処理を行ったデータ量に比例した、記憶素子に対する書き込みがコストとして発生する。断片化解消処理に伴う書き込みは、ホストコンピュータからのアクセス要求に対する処理の妨げによる性能低下を引き起こす。例えば、記憶媒体がＳＳＤである場合、記憶素子として使用されるNANDフラッシュのErase処理の回数制限に由来する寿命が存在する。つまり、ＳＳＤに対する断片化解消処理では性能低下に加えて寿命の消費が発生する。特に低コストのＳＳＤを中心に寿命の短いNANDフラッシュが使用されるため、格納データ量の削減による長寿命化が求められる。
【００２６】
本実施形態においては、断片化解消処理の実行に伴う記憶媒体の性能低下、および寿命消費の課題を解決する。断片化解消処理は、ＧＣにおける空き領域の回収効率を高めることで、記憶媒体内部のＧＣに伴うデータ移動量を削減する効果を持つ一方で、断片化解消処理を行ったデータの容量に比例した再格納が行われる。つまり、記憶媒体における断片化解消処理によって得られる効果とコストとを比較し、効果がコストを上回るように断片化解消処理を実行する必要がある。また、断片化解消処理の効果を高めるためには、断片化解消処理を行う対象となるデータに対して効果とコストとを正確に見積もる必要がある。
【００２７】
追記形式でデータ格納を行うＳＳＤやＳＭＲを採用したＨＤＤなどの記憶媒体において、断片化解消処理によって得られる効果を高めるため、記憶媒体に対する断片化解消処理による効果から断片化解消処理に伴うコストを差し引いた効果が最大化されるように、断片化解消処理を行う論理アドレス領域を決定する。そのため、記憶媒体における格納データの断片化状況、および、ホストコンピュータから記憶媒体に対するアクセスの状況を基に、断片化解消処理がもたらすＧＣに伴うデータ移動量の削減効果を推測する。
【００２８】
本実施形態においては、記憶媒体における格納データの書き込み、断片化の状況を管理するために、記憶媒体がホストコンピュータに対して提供する論理アドレス空間を一定のサイズごとに分割したチャンクを定義し、チャンクごとに格納データの断片化、更新、削除の状況を管理する。
【００２９】
まず、記憶媒体上のデータに対するWrite要求、もしくは、削除要求を検出すると、Write要求が格納、更新の対象とするチャンクを特定する。記憶媒体に対する削除要求は、例えばＴＲＩＭ(ＡＴＡ: Advanced Technology Attachmentプロトコルの場合)またはＵＮＭＡＰ(ＳＣＳＩ:Small Computer System Interfaceプロトコルの場合）と呼ばれる、当該論理アドレスの範囲が表すデータが不要であることを記憶媒体に通知するコマンドである。そして特定したチャンクに対する断片化状況、および更新、削除状況を表す情報を更新する。次に、チャンク毎の格納データの断片化、更新、削除の状況を表す情報を参照して、記憶媒体内の各チャンクについて断片化解消処理の必要有無を決定し、断片化解消処理が必要なチャンク数を算出する。併せて断片化解消処理が必要と判断されたチャンクについて、断片化解消処理の優先順位を決定する。そして、断片化解消処理が必要なチャンク数と、事前に決定した断片化解消処理の開始を判断するための基準値となるチャンク数とを比較して、断片化が発生したチャンク数が開始の基準値を上回る場合は、記憶媒体におけるデータの断片化が進んだ結果ＧＣによる空き領域の回収効率が低下した状態と判断して、優先順位の高いチャンクから断片化解消処理を開始する。断片化解消処理を開始した後は、断片化した状態のチャンク数と、事前に決定した断片化解消処理の終了を判断するための基準値となるチャンク数とを比較して、断片化が発生したチャンク数が終了の基準値を下回る場合に断片化解消処理を終了する。
【００３０】
ここで、断片化解消処理の実行開始、終了を判断する断片化状態のチャンク数の基準値は、断片化解消処理によるＧＣ処理のデータ移動量削減効果からチャンクの再格納に伴う総Write量を差し引いた、断片解消処理のコスト考慮後の効果が最大化されるように、記憶媒体ごとに設定する。また、記憶媒体における断片化に伴う性能低下を防ぐことを目的として本実施形態を用いる場合に、例えば、記憶媒体に関する断片化したチャンク数に対する性能の実測値等を基にして決定したチャンク数を基準値として設定してもよい。
【００３１】
断片解消処理を行う対象のチャンクは、各チャンクにおける断片化、更新、削除の状況を表す情報から算出される優先度に基づいて決定する。例えば、各チャンクの更新、削除の頻度に着目すると、更新頻度の高いチャンクは断片化解消処理を行った後に再び断片化を引き起こしやすいため、断片化解消処理の効果が低いと言える。そのため、更新、削除の頻度が低いチャンクから優先的に断片化解消処理の対象として選択することで、断片化解消処理の効果を高めることができる。また、各チャンクに格納されたデータの更新について、更新されたデータのセクタ数を併せて考慮することで、断片化解消処理の効果の高いチャンクをより正確に選択可能である。更新頻度が一定である場合、更新されたセクタ数が多いチャンクであるほど断片化が進んでおり、断片化解消処理の効果が高いと言える。
【００３２】
（本実施形態の構成および動作の概要）
本実施形態の記憶制御部においては、ホストコンピュータが記憶媒体にアクセスする際に用いる論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域であるチャンクのデータが、記憶媒体の内部で使用される物理アドレス空間において複数の物理アドレス領域に断片化されて記憶されているか否かを推定し、断片化されて記憶されていると推定されたチャンク数を管理する。そして、断片化されて記憶されていると推定されたチャンク数が断片化解消処理開始条件（第１閾値）を超えた場合に、断片化されて記憶されていると推定されたチャンクに対する断片化解消処理を開始し、断片化されて記憶されていると推定されたチャンク数が断片化解消処理終了条件（第２閾値）を下回るまで、断片化解消処理を継続する。
【００３３】
ここで、第１閾値および第２閾値は、断片化解消処理による記憶媒体の内部のガベージコレクション（ＧＣ）に伴うデータ移動が削減されるように設定される。例えば、記憶媒体に含まれる論理アドレス領域の総数と、記憶媒体に含まれる有効なデータが格納されている論理アドレス領域の数と、記憶媒体に対する単位時間当たりの書き込みデータ量に相当する論理アドレス領域の数と、記憶媒体に含まれる断片化されて記憶されていると判定された論理アドレス領域のデータの平均更新間隔と、を考慮して算出される。また、第１閾値と第２閾値とが同じ数に設定されて、断片化されて記憶されていると推定されたチャンク数が同じ数となるように断片化解消処理を行なう。
【００３４】
また、断片化されて記憶されていると推定されたチャンクについて、断片化解消処理を行なう優先順位をさらに設定し、優先順位にしたがって断片化解消処理を行なう。ここで、優先順位は、チャンクのデータを更新する更新頻度の低い順に設定される。
【００３５】
また、各々のチャンクを再分割した再分割領域に対するWrite処理または削除処理の発生分布に基づいて、チャンクのデータが断片化されて記憶されていると推定する。すなわち、再分割領域への初めてのWrite処理または削除処理が発生した回数を断片化発生数として累積し、断片化発生数が断片化推定条件（第３閾値）を上回る場合にチャンクのデータが断片化されて記憶されていると推定する。
【００３６】
また、断片化解消処理においては、断片化されて記憶されているチャンクのデータを読み出して、同じチャンクへの再格納をする。その場合、断片化解消処理中、他の書き込みを制限する。本実施形態が適用される記憶媒体は、追記形式で記憶素子に対するデータ格納を行う記憶媒体であり、ＳＳＤとＳＭＲを採用したＨＤＤとを含む。
【００３７】
《情報処理システム》
図２は、本実施形態に係る記憶制御装置としての記憶制御部２２０を含む情報処理システム２００の構成を示すブロック図である。
【００３８】
図２を参照すると、本実施形態の情報処理システム２００は、１台以上のホストコンピュータ２１０と、記憶媒体２４０と、ホストコンピュータ２１０と記憶媒体２４０とを接続するネットワーク２５０を含む。なお、記憶媒体２４０は、複数の記憶媒体に分散してネットワークに接続されていてもよい。
【００３９】
ホストコンピュータ２１０は、ＯＳ (Operating System)２１１およびＯＳ２１１上で動作するソフトウェアであるアプリケーション２１２と、本実施形態の記憶制御部２２０と、を備える。記憶制御部２２０は、ＯＳ２１１およびアプリケーション２１２の処理における、記憶媒体２４０へのReadおよびWriteを含むアクセス処理を制御する。
【００４０】
記憶媒体２４０は、NANDフラッシュを記憶素子として用いたＳＳＤやＳＭＲを採用したＨＤＤなどの追記形式の記憶媒体である。なお、記憶媒体２４０は、媒体本体２４１とキャッシュメモリ２４２とを有してもよい。また、ネットワーク２５０の形態は特に限定されず、ホストコンピュータ２１０と記憶媒体２４０とが直接接続される形態であってもよい。また、ホストコンピュータ２１０はネットワーク２５０によって接続された複数の装置、あるいは、システムで構成されてもよい。
【００４１】
《記憶制御装置の機能構成》
図３は、本実施形態に係る記憶制御装置としての記憶制御部２２０の機能構成を示すブロック図である。
【００４２】
図３を参照すると、記憶制御部２２０は、アクセス実行部３１０と、断片化管理部３２０と、断片化解消処理部３３０と、を備える。
【００４３】
《アクセス実行部》
アクセス実行部３１０は、ホストコンピュータ２１０で動作するＯＳ２１１またはアプリケーション２１２からのアクセス要求を受け取り、記憶媒体２４０に対して必要なアクセス処理を行う。Write要求の場合は、Writeキュー３１１を介して記憶媒体２４０に対してWrite処理を実行する。また、アクセス実行部３１０は、断片化解消処理部３３０によって指示された記憶媒体２４０上の領域に対してデータを読み出して、再格納処理を行う。記憶媒体２４０の領域に対するデータの読み出しは、記憶媒体２４０に対して直接要求を行う以外に、不図示の記憶媒体２４０に対するキャッシュメモリに対して要求を行うことでも代用できる。
【００４４】
《断片化管理部》
断片化管理部３２０は、アクセス実行部３１０により、記憶媒体２４０へのWrite要求または削除要求による更新を監視して、各チャンクの断片化を推定し、断片化と推定されたチャンクのリストを生成して、管理する。
【００４５】
図３において、断片化管理部３２０は、更新監視部３２１と、更新頻度管理テーブル３２２と、断片化状態管理テーブル３２３と、断片化解消対象推定部３２４と、断片化解消対象リスト３２５と、を備える。
【００４６】
（更新監視部）
更新監視部３２１は、ホストコンピュータ２１０で動作するソフトウェア、ＯＳから記憶媒体２４０に対するWrite要求、および削除要求を監視して、記憶媒体２４０におけるアクセス先の論理アドレス、およびアクセスのサイズからアクセス先のチャンクを特定する。そして、特定したチャンクに対応する更新頻度管理テーブル３２２のエントリに格納された更新頻度の情報を更新する。また、断片化状態管理テーブル３２３のチャンクに対応するエントリについても、アクセス実行部３１０が受け取ったWrite要求によってチャンク内の断片化発生有無、断片化の状態を表す情報を更新する。
【００４７】
（更新頻度管理テーブル）
更新頻度管理テーブル３２２は、記憶媒体内の各チャンクに対するエントリを持ち、チャンク内のデータに対して更新または削除が行われた頻度によって表される更新頻度の情報を管理する更新頻度管理機能を果たす。更新頻度管理テーブル３２２は、記憶媒体２４０の論理アドレス空間上の各チャンクに対する一定時間毎の更新頻度の情報を格納するエントリを持ち、各エントリの更新頻度の情報は一定時間間隔でリセットされる。
【００４８】
図４Ａは、本実施形態に係る更新頻度管理テーブル３２２の構成を示す図である。更新頻度管理テーブル３２２の各エントリは、チャンクＩＤ４１１に対応付けて、一定時間内の更新または削除の頻度を表す更新頻度４１２を記憶する。
【００４９】
なお、更新頻度管理テーブル３２２の各エントリに格納されるデータの形式は、図４Ａに示した形式に限定されず、例えば更新頻度４１２の代わりに最終更新時刻を持ち、各チャンクに関する更新頻度の多少を判断する形式であってもよい。この場合は、一定時間毎の更新頻度のリセットは不要である。また、更新頻度４１２や最終更新時刻以外の情報を持ち、更新頻度よりも詳細な各チャンクの更新履歴を管理する形式であってもよい。
【００５０】
（断片化状態管理テーブル）
断片化状態管理テーブル３２３は、記憶媒体内の各チャンクに対するエントリを持ち、チャンク全体の連続的なデータの格納または断片化解消処理の実行以降に、チャンク内のデータに対する更新、削除に伴い断片化が発生しているか表す情報を管理する断片化状態管理機能を果たす。断片化状態管理テーブル３２３は、記憶媒体２４０の論理アドレス空間上の各チャンクのデータに対する断片化の発生数、および断片化が発生したアドレスの分布に関する情報を格納するエントリを持つ。また、各エントリは、対応するチャンクについて断片化解消対象推定部３２４による断片化解消対象の判定、および断片化解消対象の優先順位の必要があるかを表す、断片化状態の変化を表すフラグを持つ。
【００５１】
図４Ｂは、本実施形態に係る断片化状態管理テーブル３２３の構成を示す図である。断片化状態管理テーブル３２３の各エントリは、チャンクＩＤ４２１に対応付けて、チャンク内における断片化の発生数を表した断片化発生数４２２と、チャンクをさらに細分化した領域毎の断片化の発生有無を表す断片化分布情報４２３と、断片化状態の変化を表す状態変化フラグ４２４とを記憶する。
【００５２】
更新監視部３２１は、Writeまたは削除対象のチャンクについて、更新、削除先のアドレスに対応するチャンクを細分化した領域を特定し、断片化が発生した領域と判断して断片化分布情報４２３における、対応したビットがセットされていない状態であればセットする。また、断片化分布情報４２３において新たにセットされたビット数の分だけ断片化発生数４２２を更新する。加えて、更新監視部３２１は更新、削除先のチャンクに対応するエントリについて断片化発生数４２２と断片化分布情報４２３とが変更されており、かつ、状態変化フラグ４２４がセットされていない場合は、状態変化フラグ４２４をセットする。
【００５３】
なお、断片化状態管理テーブル３２３の各エントリに格納されるデータの形式は、図４Ｂに示した形式に限定されず、例えば断片化分布情報４２３はチャンク内を細分化した分割領域毎の断片化有無をビットマップで表す形式以外に、細分化した分割領域について、断片化が発生した領域を識別可能な情報を列挙する形式であってもよい。また、例えば断片化発生数４２２と断片化分布情報４２３とによってチャンク内の断片化度合を表す形式ではなく、断片化発生数４２２を省略して、断片化分布情報４２３においてセットされたビット数によって断片化発生数４２２の代わりとする形式であってもよい。あるいは、より単純にチャンクに対するWriteアクセスの有無によって断片化の有無のみを表す形式であってもよい。さらに、図４Ｂには断片化状態管理テーブル３２３が更新頻度管理テーブル３２２と独立して示されているが、単体の一体化されたテーブルで構成されていてもよい。
【００５４】
（断片化解消対象リスト）
断片化解消対象リスト３２５は、断片化解消対象推定部３２４によって断片化解消対象に決定された、記憶媒体２４０の論理アドレス空間上のチャンクを断片化解消処理の優先度順に格納する。また、断片化解消対象リスト３２５は、断片化解消対象推定部３２４によって格納された、断片化解消対象のチャンク数を管理する。
【００５５】
図４Ｃは、本実施形態に係る断片化解消対象リスト３２５の構成を示す図である。断片化解消対象リスト３２５は、断片化解消対象のチャンク数を表す断片化解消対象数４３１と、断片化解消処理の対象となる各チャンクについて、記憶媒体２４０の各チャンクを一意に示すチャンクＩＤ４３２と、各チャンクの断片化解消処理の優先順位を表す優先順位４３３とを記憶する。
【００５６】
なお、断片化解消対象リスト３２５のデータの形式は、図４Ｃに示した形式に限定されず、例えばチャンクＩＤ４３２を断片化解消処理の優先順位で整列したリストを作成することで、優先順位４３３を省略できる。
【００５７】
（断片化解消対象推定部）
断片化解消対象推定部３２４は、更新頻度管理テーブル３２２および断片化状態管理テーブル３２３が管理する、各チャンクの更新または削除の履歴および断片化状態の情報を参照して、記憶媒体２４０の論理アドレス空間の各チャンクについて、断片化解消処理が必要か否かの推定を行う断片化解消対象推定機能を果たす。また、断片化解消処理が必要と推定されたチャンクについて、断片化解消処理の優先順位を決定し、断片化解消処理対象のチャンク数を算出する。
【００５８】
まず、断片化解消対象推定部３２４は各チャンクに対して断片化状態管理テーブル３２３に格納された断片化発生数４２２を参照し、事前に定めた一定の基準値を上回るチャンクを断片化解消処理が必要と判定する。次に、チャンクについて断片化解消処理が必要と判定された場合に、チャンクについて断片化発生数４２２、および更新頻度管理テーブル３２２の対応するエントリに格納された更新頻度４１２や最終更新時刻を参照して、断片化解消処理の優先順位を決定する。そして、断片化解消対象推定部３２４は、チャンクを表す番号と決定された優先順位とを、それぞれチャンクＩＤ４３２と優先順位４３３として断片化解消対象リスト３２５に格納し、断片化解消対象数４３１の値を加算する。
【００５９】
なお、断片化解消対象推定部３２４における、各チャンクに対する断片化解消処理の必要性の判定基準は必ずしも基準値との比較に限定されない。例えば、優先順位の決定よりも前に各チャンクの更新頻度４１２や最終更新時刻を参照して、更新頻度が一定以上に高いチャンクは断片化を解消しても再度断片化が発生する可能性が高く断片化解消の効果が低いため、断片化が必要なチャンクから除外してもよい。
【００６０】
また、各チャンクの断片化発生数４２２と比較する基準値については、例えば記憶媒体２４０内部のＧＣアルゴリズムによるデータ移動対象となりうるチャンクに限定することが可能である。具体的には、記憶媒体２４０が用いるＧＣアルゴリズムがデータ移動を最小化するように回収対象の領域を選択する場合、記憶媒体２４０の論理アドレス空間のサイズに対する記憶素子の余剰容量の割合をＰとすると、必ず空き領域の割合がＰ以上の領域が回収対象に選択される。そこで、断片化発生数４２２を参照して、各チャンクの細分化した領域のうち断片化したデータ量の割合を計算し、計算結果がＰ未満となる場合に断片化解消対象から除外されるように基準値を設定することで、ＧＣによるデータ移動の対象となり得ないチャンクを断片化解消対象から除外できる。
【００６１】
《断片化解消処理部》
図３において、断片化解消処理部３３０は、断片化解消対象リスト３２５と、断片化解消条件設定部３３１と、断片化解消処理制御部３３２と、再格納制御部３３３と、を備える。なお、断片化解消対象リスト３２５は、断片化管理部３２０と共有され、断片化解消対象のチャンク情報を受け取る。
【００６２】
（断片化解消条件設定部）
断片化解消条件設定部３３１は、断片化解消処理制御部３３２が記憶媒体２４０に対する断片化解消処理の開始、終了を判定するために必要な、記憶媒体２４０に含まれる断片化状態のチャンク数の基準値を管理し、設定する断片化解消条件設定機能を果たす。断片化解消条件設定部３３１は、基準値のチャンク数を、記憶媒体２４０内部のＧＣに伴うデータ移動の削減量から、断片化解消処理におけるチャンクの再格納に伴う総Write量を差し引いた、断片解消処理に関するコスト考慮後の効果の推測結果が最大となるように計算する。あるいは、ユーザから指定された記憶媒体の性能条件を満たすチャンク数の算出結果が設定される。
【００６３】
断片化解消処理の実行開始、実行停止の判断基準となる、断片化が発生したチャンク数の算出は、記憶媒体上の各チャンクに対してＧＣが行われた場合の空き領域の回収効率に基づき決定する。ＧＣにおける空き領域の回収効率は、ＧＣによって新たに格納可能となるホストコンピュータからのWriteデータ量と記憶媒体内部のデータ移動量の比率を表す。記憶媒体内部でＧＣに伴い移動の対象となるデータは、更新、削除によって断片化した状態で格納されたデータである。一方で、断片化解消処理を行った後に更新や削除が行われていないチャンクのデータは、断片化が発生せずに連続的に格納されているため、ＧＣによる移動対象のデータに含まれない。つまり、ＧＣにおける移動の対象となりうるデータの総容量は記憶媒体内の断片化が発生した状態のチャンク数で表される。
【００６４】
また、ＧＣによる空き領域の回収効率から、断片化解消処理によるＧＣのデータ移動量の削減効果を計算できる。まず、空き領域の回収効率を用いてホストコンピュータからのWriteデータ量に対するＧＣの発生頻度を計算する。計算された発生頻度と、データの新規格納から更新または削除までの期間の情報を用いることで、ＧＣに伴うデータ移動量を計算可能である。より具体的にはチャンク毎の更新頻度管理テーブル３２２に格納された更新頻度４１２の情報を利用して、各チャンクのデータが格納されてから更新または削除されるまでの平均期間を求められる。平均期間を断片化状態のチャンク数とＧＣ処理の発生頻度、すなわちＧＣ処理の平均発生間隔で割ることで各チャンクのデータがＧＣ処理における移動対象となる回数の期待値の形で、ＧＣに伴うデータ移動量を求められる。
【００６５】
さらに、ＧＣに伴うデータ移動量の差を断片化解消処理の前後で計算することで、断片化解消処理におるデータ移動量の削減量を計算できる。加えて断片化解消処理に必要なコストは、チャンクサイズ分のデータの記憶媒体２４０に対する格納である。コストを考慮することで、断片化解消処理による記憶媒体内部のＧＣに伴うデータ移動の削減量から、断片化解消処理におけるチャンクの再格納に伴う総Write量を差し引いた値を断片解消処理のコスト考慮後の効果が求められる。この効果が最大となるように、実行開始、停止の判断基準である断片化状態のチャンク数を設定すればよい。
【００６６】
（断片化解消処理制御部）
断片化解消処理制御部３３２は、断片化解消処理が停止した状態では、断片化解消条件設定部３３１から断片化解消処理の開始条件となるチャンク数の情報を取得して、断片化解消処理が必要なチャンク数が開始条件のチャンク数を上回る場合は優先順位の高いチャンクから順番に断片化解消処理を開始する。一方、断片化解消処理を開始した状態では、断片化解消条件設定部３３１から断片化解消処理の終了条件となるチャンク数の情報を取得して、断片化解消処理が必要なチャンク数が停止条件のチャンク数を下回る場合は、断片化解消処理を終了する断片化解消処理制御機能を果たす。
【００６７】
断片化解消処理制御部３３２は、断片化解消処理が停止した状態では断片化解消対象リスト３２５の断片化解消対象数４３１を参照して、断片化解消条件設定部３３１によって設定された断片化解消処理の開始条件となるチャンク数を比較する。比較の結果、算出されたチャンク数が断片化解消処理の開始条件となるチャンク数を上回る場合は、断片化解消処理を開始状態として、チャンクＩＤ４３２および優先順位４３３を参照して優先順位が高く設定されたチャンクから順番に断片化解消処理の対象としてチャンクの情報を再格納制御部３３３に通知する。一方で、断片化解消処理を開始した状態では断片化解消対象リスト３２５の断片化解消対象数４３１を参照して、断片化解消条件設定部３３１によって設定された断片化解消処理の停止条件となるチャンク数を比較する。比較の結果、算出されたチャンク数が断片化解消処理の停止条件となるチャンク数を下回る場合は、断片化解消処理を停止状態として断片化解消処理を終了する。
【００６８】
（再格納制御部）
再格納制御部３３３は、断片化解消処理の対象となったチャンクのデータを記憶媒体から読み出すためのRead要求、およびRead要求によって読み出されたチャンクのデータを記憶媒体の同一チャンクに再格納するためのWrite要求の発行を制御して、断片化解消処理を実行する再格納制御機能を果たす。
【００６９】
再格納制御部３３３は、断片化解消処理制御部３３２から通知された断片化解消処理対象のチャンクについて、対応するデータを記憶媒体２４０から読み出すためのRead要求を行うようにアクセス実行部３１０に対して指示する。また、Read要求によって読み出されたデータを記憶媒体２４０に再格納するためのWrite要求の発行をアクセス実行部３１０に対して指示することで、チャンクの断片化解消処理を実施する。記憶媒体２４０からのデータの読み出しは、記憶媒体２４０に対して直接Read要求を行う以外に、記憶媒体２４０に対するキャッシュメモリ２４２に対して要求を行うことでも代用できる。
【００７０】
（断片化推定テーブルおよび断片化解消処理管理テーブル）
図４Ｄは、本実施形態に係る断片化推定テーブル４４０および断片化解消処理管理テーブル４５０の構成を示す図である。なお、断片化推定テーブル４４０および断片化解消処理管理テーブル４５０における断片化推定条件（第３閾値）や断片化解消処理開始条件（第１閾値）および断片化解消処理終了条件（第２閾値）は、最初に設定された固定値であっても、随時、環境変化に応じて算出される更新値であってもよい。
【００７１】
断片化推定テーブル４４０は、断片化解消対象推定部３２４が断片化解消対象となるチャンクを断片化推定条件（第３閾値）に基づいて推定するために使用される。また、断片化推定テーブル４４０は、断片化解消対象推定部３２４が断片化していると推定したチャンクの断片化解消処理を行なう優先順位を設定するために使用される。
【００７２】
断片化推定テーブル４４０は、チャンクＩＤ４４１に対応付けて、チャンク容量４４２や断片化発生数４４３などの断片化推定のためのパラメータを記憶する。そして、断片化推定条件（第３閾値）４４４に基づいて推定された断片化有無フラグ４４５を記憶する。本実施形態においては、断片化推定条件（第３閾値）４４４は断片化発生数の基準値であり、断片化発生数４４３と断片化推定条件（第３閾値）４４４との大小によりチャンクの断片化が推定される。
【００７３】
そして、本実施形態においては、断片化推定テーブル４４０は、断片化と推定されたチャンクの更新頻度４４６の、他の断片化と推定されたチャンクの更新頻度との比較に基づいて、断片化解消処理の優先順位４４７が設定される。
【００７４】
断片化解消処理管理テーブル４５０は、断片化解消処理制御部３３２が断片化解消条件設定部３３１からの断片化解消処理開始条件（第１閾値）と断片化解消処理終了条件（第２閾値）とに基づいて、断片化解消処理の開始または終了を制御するために使用される。
【００７５】
断片化解消処理管理テーブル４５０は、断片化解消対象リスト３２５の断片化解消対象数４３１からの断片化チャンク数４５１と、断片化解消処理開始条件（第１閾値）４５２との比較に対応して、断片化解消処理開始フラグ４５３を設定する。また、断片化解消処理管理テーブル４５０は、断片化チャンク数４５１と、断片化解消処理終了条件（第２閾値）４５４との比較に対応して、断片化解消処理終了フラグ４５５を設定する。
【００７６】
（断片化推定条件設定テーブルおよび断片化解消処理条件設定テーブル）
図４Ｅは、本実施形態に係る断片化推定条件設定テーブル４６０および断片化解消処理条件設定テーブル４７０の構成を示す図である。
【００７７】
断片化推定条件設定テーブル４６０は、断片化解消対象推定部３２４が断片化推定条件（第３閾値）を設定するために使用される。断片化推定条件設定テーブル４６０は、断片化推定条件設定パラメータ４６１に基づいて、断片化推定条件設定アルゴリズム４６２に従って生成された、断片化推定条件（第３閾値）４６３を記憶する。なお、断片化推定条件設定パラメータ４６１として、チャンク容量、チャンク分割数、分割領域容量などを示したが、これに限定されない。
【００７８】
断片化解消処理条件設定テーブル４７０は、断片化解消条件設定部３３１が断片化解消処理開始条件（第１閾値）と断片化解消処理終了条件（第２閾値）とを設定するために使用される。断片化解消処理条件設定テーブル４７０は、断片化解消条件設定パラメータ４７１に基づいて、断片化解消条件設定アルゴリズム４７２に従って生成された、断片化解消処理開始条件（第１閾値）４７３と断片化解消処理終了条件（第２閾値）４７４を記憶する。なお、断片化解消条件設定パラメータ４７１として、記憶媒体のチャンク総数（Ｃ）、有効データ格納チャンク数（Ａ）、断片化状態チャンク数（Ｂ）、単位時間当りのWriteデータ量（Ｗ）、チャンクの平均更新間隔（Ｔ）などを示したが、これに限定されない。
【００７９】
《ホストコンピュータのハードウェア構成》
図５は、本実施形態に係る記憶制御部２２０を含むホストコンピュータのハードウェア構成を示すブロック図である。なお、図５においては、記憶制御部２２０はホストコンピュータ２１０のソフトウェア処理として図示するが、記憶制御部２２０を、ホストコンピュータ２１０とは独立したワンチップのコンピュータで実現してもよい。
【００８０】
図５で、ＣＰＵ(Central Processing Unit)５１０は演算制御用のプロセッサであり、プログラムを実行することで図３の記憶制御部２２０の機能構成部を実現する。ＲＯＭ(Read Only Memory)５２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。また、通信制御部５３０は、ネットワーク２５０を介して記憶媒体２４０や他の装置と通信する。なお、ＣＰＵ５１０は１つに限定されず、複数のＣＰＵであっても、あるいは画像処理用のＧＰＵ(Graphics Processing Unit)を含んでもよい。また、通信制御部５３０は、ＣＰＵ５１０とは独立したＣＰＵを有して、ＲＡＭ(Random Access Memory)５４０の領域に送受信データを書き込みあるいは読み出しするのが望ましい。また、ＲＡＭ５４０とストレージ５５０との間でデータを転送するＤＭＡＣ(Direct Memory Access Controller)を設けるのが望ましい（図示なし）。さらに、入出力インタフェース５６０は、ＣＰＵ５１０とは独立したＣＰＵを有して、ＲＡＭ５４０の領域に入出力データを書き込みあるいは読み出しするのが望ましい。したがって、ＣＰＵ５１０は、ＲＡＭ５４０にデータが受信あるいは転送されたことを認識してデータを処理する。また、ＣＰＵ５１０は、処理結果をＲＡＭ５４０に準備し、後の送信あるいは転送は通信制御部５３０やＤＭＡＣ、あるいは入出力インタフェース５６０に任せる。
【００８１】
ＲＡＭ５４０は、ＣＰＵ５１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ５４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。論理アドレス５４１は、ＯＳ２１１またはアプリケーション２１２から記憶媒体２４０にアクセスしたアドレスである。断片化推定条件４６３は、断片化解消対象推定部３２４が各チャンクを断片化したと推定するための閾値である。断片化推定テーブル４４０は、図４Ｄに示した、断片化解消対象推定部３２４が各チャンクを断片化したと推定するために使用するテーブルである。断片化解消処理条件４７３／４７４は、断片化解消処理制御部３３２が断片化解消処理を開始または終了するための閾値である。断片化解消処理管理テーブル４５０は、図４Ｄに示した、断片化解消処理制御部３３２が断片化解消処理を開始または終了するために使用するテーブルである。読み出し情報５４５は、ＯＳ２１１またはアプリケーション２１２からの要求に基づき記憶媒体２４０からReadした情報である。読み込み情報５４６は、ＯＳ２１１またはアプリケーション２１２からの要求に基づき記憶媒体２４０にWriteする情報である。入出力データ５４７は、入出力インタフェース５６０を介して入出力されるデータである。送受信データ５４８は、通信制御部５３０を介して送受信されるデータである。アプリケーション使用領域５４９は、記憶制御以外の処理でアプリケーションが使用するエリアである。
【００８２】
ストレージ５５０には、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。更新頻度管理テーブル３２２は、図４Ａに示した、各チャンクの更新頻度を管理するためのテーブルである。断片化状態管理テーブル３２３は、図４Ｂに示した、各チャンクの断片化状態を管理するためのテーブルである。断片化解消対象リスト３２５は、図４Ｃに示した、断片化解消対象のチャンク数と、断片化解消処理の優先順位を記憶するリストである。断片化推定条件設定アルゴリズム４６２は、図４Ｅに示した、断片化推定条件を生成するためのアルゴリズムである。断片化解消条件設定アルゴリズム４７２は、図４Ｅに示した、断片化解消処理の開始条件または終了条件を生成するためのアルゴリズムである。
【００８３】
ストレージ５５０には、以下のプログラムが格納される。ＯＳ２１１は、本ホストコンピュータ２１０の全体を制御する基礎プログラムである。アプリケーション２１２は、現在、本ホストコンピュータ２１０が実行中のプログラムである。記憶制御プログラム５５２は、ＯＳ２１１やアプリケーション２１２からの記憶媒体２４０へのアクセスを受けて、本実施形態のアクセス制御を実現するプログラムである。Read制御モジュール５５３は、記憶制御プログラム５５２における、記憶媒体２４０からのReadを制御するモジュールである。Write制御モジュール５５４は、記憶制御プログラム５５２における、記憶媒体へのWriteを制御するモジュールである。断片化管理モジュール５５５は、各チャンクの断片化状態を監視して、断片化状態と推定されるチャンク数を管理するためのモジュールである。断片化解消処理モジュール５５６は、断片化状態と推定されるチャンク数に基づいて断片化解消処理を制御して、断片化状態を解消するために各チャンクにおける再配置を行なうモジュールである。
【００８４】
入出力インタフェース５６０は、入出力機器との入出力データをインタフェースする。入出力インタフェース５６０には、表示部５６１、操作部５６２、が接続される。また、入出力インタフェース５６０には、さらに、記憶媒体２４０が接続されてもよい。さらに、音声出力部であるスピーカや、音声入力部であるマイク、あるいは、ＧＰＳ位置判定部が接続されてもよい。
【００８５】
なお、図５のＲＡＭ５４０やストレージ５５０には、ホストコンピュータ２１０が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【００８６】
《記憶制御部の処理手順》
図６は、本実施形態に係る記憶制御部２２０の処理手順を示すフローチャートである。このフローチャートは、図５のＣＰＵ５１０がＲＡＭ５４０を使用して実行し、図３の機能構成部を実現する。
【００８７】
ホストコンピュータ２１０の記憶制御部２２０は、ステップＳ６０１において、各チャンクの断片化推定のために閾値、および、チャンク数に基づいて断片化解消処理を開始または終了する閾値を設定する、閾値設定処理を実行する。閾値はあらかじめ算出された固定閾値であっても、現在のホストコンピュータ２１０や記憶媒体２４０の状態に基づいて動的に算出された閾値であってもよい。
【００８８】
記憶制御部２２０は、ステップＳ６１１において、ＯＳ２１１またはアプリケーション２１２からのRead要求であるか否かを判定する。Read要求であれば、記憶制御部２２０は、ステップＳ６１３において、記憶媒体２４０からのRead処理を実行する。Read要求でなければ、記憶制御部２２０は、ステップＳ６２１において、ＯＳ２１１またはアプリケーション２１２からのWrite要求であるか否かを判定する。Write要求であれば、記憶制御部２２０は、ステップＳ６２３において、記憶媒体２４０へのWrite処理を実行する。
【００８９】
Read要求でもWrite要求でもなければ、記憶制御部２２０は、ステップＳ６３１において、断片化管理のタイミングであるか否かを判定する。断片化管理のタイミングであれば、記憶制御部２２０は、ステップＳ６３３において、断片化管理処理を実行する。Read要求でもWrite要求でも断片化管理タイミングでもなければ、記憶制御部２２０は、ステップＳ６４１において、断片化解消のタイミングであるか否かを判定する。断片化解消のタイミングであれば、記憶制御部２２０は、ステップＳ６４３において、断片化解消処理を実行する。
【００９０】
なお、図６においては、シーケンスに処理を実行するように示したが、各処理を並列に独立して実行してもよい。また、断片化管理タイミングや断片化解消タイミングは任意のタイミングであっても、他の処理と関連したタイミングであってもよい。例えば、断片化管理タイミングは、ステップＳ６２３のWrite処理の完了時であってもよい（Writeキュー３１１を参照して行なう）。また、断片化解消タイミングは、ステップＳ６３３の断片化管理処理に引き続いたタイミングであってもよい（Writeキュー３１１を参照して行なう）。
【００９１】
（閾値設定処理）
ステップＳ６０１における閾値設定処理においては、断片化解消処理開始条件（第１閾値）および断片化解消処理終了条件（第２閾値）と、断片化推定条件（第３閾値）と、が設定される。なお、断片化解消処理開始条件（第１閾値）および断片化解消処理終了条件（第２閾値）は同じ閾値であってもよい。
【００９２】
断片化解消処理開始条件（第１閾値）は、断片化解消処理（Ｓ６４３）において、断片化解消処理を開始するための閾値（断片化と推定されたチャンク数の上限基準値）であり、断片化解消処理終了条件（第２閾値）は、断片化解消処理を終了するための閾値（断片化と推定されたチャンク数の下限基準値）である。また、断片化推定条件（第３閾値）は、断片化管理処理（Ｓ６３３）において、各チャンクが断片化解消対象であるか否かの推定のための閾値（各チャンクの断片化発生数の基準値）である。
【００９３】
なお、ステップＳ６０１における閾値設定処理においては、あらかじめ算出された固定閾値を設定してもよいし、後述する算出アルゴリズムに従って、取得した条件パラメータに基づいて閾値を動的に算出して、設定してもよい。
【００９４】
（Ｒｅａｄ処理）
図７は、本実施形態に係るＲｅａｄ処理（Ｓ６１３）の手順を示すフローチャートである。図７は、図６のステップＳ６１３において、例えば、ＯＳからRead要求を受け取り、要求されたデータを返す手順である。
【００９５】
記憶制御部２２０のアクセス実行部３１０は、ホストコンピュータ２１０で動作するソフトウェアやＯＳからのRead要求を受け取ると、記憶媒体２４０に対して要求先のアドレスについてデータのReadを行い、結果をアクセス元のソフトウェアやＯＳに返して処理を終了する（ステップＳ７０１）。
【００９６】
以上のステップＳ７０１の処理を行い、本実施形態においてホストコンピュータ２１０で動作するソフトウェアやＯＳからRead要求を受け取り、要求されたデータを返す動作が完了する。
【００９７】
（Ｗｒｉｔｅ処理）
図８は、本実施形態に係るＷｒｉｔｅ処理（Ｓ６２３）の手順を示すフローチャートである。図８は、例えば、図６のステップＳ６２３において、ホストコンピュータ２１０で動作するソフトウェア、ＯＳから発行されたWrite要求または削除要求の処理を行う手順である。
【００９８】
記憶制御部２２０のアクセス実行部３１０は、ホストコンピュータ２１０で動作するソフトウェア、ＯＳからのWrite要求または削除要求を受け取ると、更新監視部３２１に対してWriteまたは削除要求の情報を伝える（ステップＳ８０１）。更新監視部３２１は、アクセス実行部３１０から受け取ったアクセス要求に関する、記憶媒体２４０のアクセス先の論理アドレスとサイズとからアクセス先となる論理アドレス空間上のチャンクを特定する（ステップＳ８０３）。
【００９９】
更新監視部３２１は、ステップＳ８０３で特定したチャンクに対応する、更新頻度管理テーブル３２２のエントリに格納された更新頻度４１２の値を１つ加算する（ステップＳ８０５）。更新監視部３２１は、アクセス実行部３１０から受け取ったアクセス要求に関する、記憶媒体２４０のアクセス先の論理アドレスとサイズとから、アクセス先についてチャンクを細分化した領域の単位で特定する。そして、ステップＳ８０３で特定したチャンクに対応する、断片化状態管理テーブル３２３のエントリに格納された断片化分布情報４２３において、アクセス先の領域に対応するビットがセットされているか確認する（ステップＳ８０７）。
【０１００】
ステップＳ８０７の確認の結果、ステップＳ８０３で特定したチャンクに対応する、断片化状態管理テーブル３２３に格納された、アクセス先の領域に対応する断片化分布情報４２３のビットが全てセットされていた場合（ステップＳ８０９のＮｏ判定）、ステップＳ８１３の処理を実行する。Ｓ８０７の確認の結果、ステップＳ８０３で特定したチャンクに対応する、断片化状態管理テーブル３２３のエントリに格納された、アクセス先の領域に対応する断片化分布情報４２３のビットにセットされていないビットが存在する場合（ステップＳ８０９のＹｅｓ判定）、更新監視部３２１は、断片化分布情報４２３のアクセス先領域に対応するビットをセットする。また、対応するエントリに格納された断片化状態管理テーブル３２３の断片化発生数４２２の値について、断片化分布情報４２３において新たにセットしたビット数を加算する。さらに、更新監視部３２１は、対応するエントリの状態変化フラグ４２４をセットする（ステップＳ８１１）。
【０１０１】
アクセス実行部３１０は、ステップＳ８０１で受け取ったアクセス要求を記憶媒体２４０に発行し、記憶媒体２４０から完了応答を受け取ると、アクセス要求元であるホストコンピュータ２１０で動作するソフトウェア、ＯＳに完了応答を返して処理を終了する（ステップＳ８１３）。
【０１０２】
以上のステップＳ８０１からＳ８１３までの処理を行い、ホストコンピュータ２１０で動作するソフトウェア、ＯＳから発行されたWrite要求または削除要求の処理を行う動作が完了する。ステップＳ８０１からＳ８１３の処理順序は、必ずしも図８に示した順序である必要はない。例えば、ステップＳ８０１からＳ８１１、およびステップＳ８１３の処理は同時期に実行、あるいは順序を入れ替えた実行が可能である。また、ステップＳ８０５、およびステップＳ８０７からＳ８１１の処理についても同時期の実行、あるいは順序を入れ替えた実行が可能である。
【０１０３】
（断片化推定処理）
図９は、本実施形態に係る断片化推定処理（Ｓ６３３）の手順を示すフローチャートである。断片化推定処理においては、断片化解消が必要なチャンクを推定し、断片化解消処理の優先順位を設定する。
【０１０４】
記憶制御部２２０の断片化解消対象推定部３２４は、任意のタイミングで、記憶媒体２４０の論理アドレス空間における先頭のチャンクに着目し、断片化解消処理が必要であるか判定を開始する（ステップＳ９０１）。断片化解消対象推定部３２４は、現在着目中のチャンクに対応する断片化状態管理テーブル３２３のエントリの状態変化フラグ４２４を参照する（ステップＳ９０３）。
【０１０５】
着目中のチャンクに対応する状態変化フラグ４２４がセットされていない場合（ステップＳ９０５のＮｏ判定）、ステップＳ９１９以降の処理を実行する。着目中のチャンクに対応する状態変化フラグ４２４がセットされている場合（ステップＳ９０５のＹｅｓ判定）、断片化解消対象推定部３２４は、現在着目中のチャンクに対応する断片化状態管理テーブル３２３のエントリの断片化発生数４２２を参照して、事前に定めた一定の断片数の基準値と比較する（ステップＳ９０７）。なお、断片数の基準値は、断片化解消対象推定部３２４に関する上記説明における方法で事前に設定する。
【０１０６】
ステップＳ９０７の比較結果で、断片化発生数４２２が基準値未満の場合（ステップＳ９０９のＮｏ判定）、ステップＳ９１９以降の処理を実行する。ステップＳ９０７の比較結果で、断片化発生数４２２が基準値以上の場合（ステップＳ９０９のＹｅｓ判定）、断片化解消対象推定部３２４は、着目中のチャンクに対応する更新頻度管理テーブル３２２のエントリに格納された更新頻度４１２を参照する（ステップＳ９１１）。
【０１０７】
断片化解消対象推定部３２４は、断片化解消対象リスト３２５に格納されたチャンクＩＤ４３２で表される各チャンクに対応した、更新頻度管理テーブル３２２に格納された更新頻度４１２を参照し、各チャンクと、現在着目中のチャンクについて、更新頻度の少ない順番にソートする（ステップＳ９１３）。そして、断片化解消対象推定部３２４は、現在着目中のチャンクに対応する番号を断片化解消対象リスト３２５における新たなチャンクＩＤ４３２として追加する。また、ステップＳ９１３におけるソート結果に基づき、断片化解消対象リスト３２５に登録された各チャンク番号に対応する優先順位４３３を更新する（ステップＳ９１５）。
【０１０８】
断片化解消対象推定部３２４は、現在着目中のチャンクに対応する断片化状態管理テーブル３２３のエントリの状態変化フラグ４２４をリセットする（ステップＳ９１７）。断片化解消対象推定部３２４は、現在着目中のチャンクが記憶媒体２４０の論理アドレス空間における末尾のチャンクであるか確認する（ステップＳ９１９）。
【０１０９】
現在着目中のチャンクが、記憶媒体２４０の論理アドレス空間における末尾のチャンクではない場合（ステップＳ９２１のＮｏ判定）、断片化解消対象推定部３２４は、着目するチャンクを記憶媒体２４０の論理アドレス空間における直後のアドレスに対応するチャンクに変更して、ステップＳ９０３から処理を再実行する（ステップＳ９２３）。現在着目中のチャンクが、記憶媒体２４０の論理アドレス空間における末尾のチャンクである場合（ステップＳ９２１のＹｅｓ判定）、断片化解消が必要なチャンクを判定し、断片化解消処理の優先順位を決定する処理を終了する。
【０１１０】
以上のステップＳ９０１からＳ９２３までの処理を行い、断片化解消が必要なチャンクを判定し、断片化解消処理の優先順位を決定する動作が完了する。ステップＳ９０１からＳ９２３までの処理順序は、必ずしも図９に示した手順である必要はない。例えば、ステップＳ９０１およびステップＳ９２３において断片化状態管理テーブル３２３のエントリの状態変化フラグ４２４を確認して、着目するチャンクとして断片化状態が変化したチャンクを直接指定できれば、ステップＳ９０３およびＳ９０５のＮｏ判定の処理を省略できる。
【０１１１】
（断片化解消処理）
図１０は、本実施形態に係る断片化解消処理（Ｓ６４３）の手順を示すフローチャートである。断片化解消処理では、断片化解消対象のチャンクに対する断片化解消処理の開始、実行、停止を行う。
【０１１２】
記憶制御部２２０の断片化解消処理制御部３３２は、任意のタイミングで、断片化解消対象リスト３２５から断片化解消対象数４３１を参照して、記憶媒体２４０の断片化解消対象のチャンク数を取得する（ステップＳ１００１）。断片化解消処理制御部３３２は、ステップＳ１００１で取得した断片化解消処理対象のチャンク数と、断片化解消条件設定部３３１が設定した断片化解消処理の開始条件となるチャンク数（第１閾値）とを比較する（ステップＳ１００３）。
【０１１３】
断片化解消対象のチャンク数が断片化解消処理の開始条件のチャンク数を下回る場合（ステップＳ１００５のＮｏ判定）、断片化解消処理を終了する。なお、本断片化解消処理が独立して並列に実行される場合は、ステップＳ１００１からの処理を再実行する。断片化解消対象のチャンク数が断片化解消処理の開始条件のチャンク数以上の場合（ステップＳ１００５のＹｅｓ判定）、断片化解消処理制御部３３２は、断片化解消対象リスト３２５から優先順位４３３が最も高いチャンクＩＤ４３２を抽出し、再格納制御部３３３に通知する（ステップＳ１００７）。
【０１１４】
再格納制御部３３３は、ステップＳ１００７で通知されたチャンクのデータを読み出すためのRead要求、およびRead要求で読み出されたデータを再格納するためのWrite要求を断片化解消処理としてアクセス実行部３１０を介して実行する（ステップＳ１００９）。
【０１１５】
断片化解消処理制御部３３２は、ステップＳ１００７で通知したチャンクに対する再格納処理が完了すると、断片化解消対象リスト３２５から対応するチャンクＩＤ４３２、優先順位４３３の情報を削除し、断片化解消対象数４３１の値を１つ減算する（ステップＳ１０１１）。断片化解消処理制御部３３２は、断片化状態管理テーブル３２３の断片化解消処理が終了したチャンクに対応するエントリに格納された断片化発生数４２２、断片化分布情報４２３の各ビット、状態変化フラグ４２４を全て０“ゼロ”にリセットする（ステップＳ１０１３）。
【０１１６】
断片化解消処理制御部３３２は、ステップＳ１０１１で減算した断片化解消対象数４３１の値と、断片化解消条件設定部３３１が設定した断片化解消処理の停止条件となるチャンク数（第２閾値）とを比較する（ステップＳ１０１５）。断片化解消対象数４３１が断片化解消処理の停止条件のチャンク数を上回る場合（ステップＳ１０１７のＮｏ判定）、ステップＳ１００７からの断片化解消の処理を再実行する。
【０１１７】
断片化解消対象数４３１が断片化解消処理の停止条件のチャンク数以下の場合（ステップＳ１０１７のＹｅｓ判定）、断片化解消処理を終了する。なお、本断片化解消処理が独立して並列に実行される場合は、ステップＳ１００１からの処理を再実行する。
【０１１８】
以上のステップＳ１００１からＳ１０１７までの処理を行い、断片化解消処理の対象のチャンクに対する断片化解消処理の実行、停止を行う動作を実行する。ステップＳ１００１からＳ１０１７までの処理順序は、必ずしも図１０に示した順序である必要はない。例えば、ステップＳ１００７からＳ１００９、ステップＳ１０１１、ステップＳ１０１３の各処理は同時期に実行、あるいは順序を入れ替えた実行が可能である。また、ステップＳ１００５の判定において、断片化解消対象のチャンク数が断片化解消処理の開始条件のチャンク数を上回る場合にＹｅｓ判定、断片化解消処理の開始条件のチャンク数以下の場合にＮｏ判定としてもよい。同様に、ステップＳ１０１７の判定において断片化解消対象のチャンク数が断片化解消処理の停止条件のチャンク数を下回る場合にＹｅｓ判定、断片化解消処理の停止条件のチャンク数以上の場合にＮｏ判定としてもよい。
【０１１９】
《閾値の設定方法》
以下、閾値の設定方法の具体例を説明する。しかし、本実施形態の閾値は、これらの設定方法に限定されるものではない。
【０１２０】
（各チャンクの断片化推定条件）
図９のステップＳ９０７において、断片化発生数４４３と比較する断片化推定条件（第３閾値）４４４は、例えば以下の手順で決定する。
【０１２１】
まず、記憶媒体内部の記憶素子の総物理容量に対する、記憶媒体の使用容量の割合αを算出する。記憶媒体に格納されたデータが記憶素子上に均等に分散した状態で格納された場合、記憶媒体の各領域に含まれる有効なデータの割合はαで表される。つまり、記憶媒体内部でＧＣが効率的に動作する場合に、回収される記憶領域に含まれる有効なデータの割合は必ずα以下で表される。
【０１２２】
よって、断片化を判定するチャンクに含まれる分割領域について、更新によって断片化状態となった分割領域の割合が(１−α)未満のチャンクのデータは断片化の度合が低く、ＧＣによる回収対象とならない。チャンクに含まれる分割領域数をＮとすると、チャンクの断片化を判断するための断片化数である断片化推定条件４４４を｛（１−α）×Ｎ｝とすれば、断片化が進んだチャンクのみを断片化状態であると判定できる。
【０１２３】
（断片化解消処理開始条件／断片化解消処理停止条件）
図１０のステップＳ１００５およびステップＳ１０１７において、断片化解消対象数４３１と比較する断片化解消処理の開始条件および停止条件のチャンク数は、断片化解消条件設定部３３１によって、例えば以下の手順で決定する。なお、以下の手順では、断片化解消処理の開始条件および停止条件のチャンク数を同様にする例を説明する。
【０１２４】
記憶媒体２４０に含まれる物理的な記憶素子の総容量をチャンク数に換算した、総チャンク数をＣと定義する。まず、断片化解消条件設定部３３１は、記憶媒体２４０の論理アドレス空間の使用状況から、有効なデータを格納するチャンク数Ａを算出する。記憶媒体２４０に含まれるチャンクにおいて、更新によって断片化状態であるチャンクの数をＢとした場合、有効なデータが格納されており、なおかつ更新が行われない、すなわち記憶媒体２４０内部のＧＣにおいて回収対象とならないチャンクの数は（Ａ−Ｂ）で求められる。よって、記憶媒体２４０においてＧＣによる回収の対象となる記憶素子の総容量は、チャンク数に換算すると｛Ｃ−（Ａ−Ｂ）｝＝Ｃ−Ａ＋Ｂで表される。つまり、断片化状態であるＢ個のチャンクに含まれるデータを、Ｃ−Ａ＋Ｂ個のチャンクの総容量に相当する記憶素子に追記形式で格納することになる。各チャンクに対して均等に更新が行われると仮定した場合、記憶媒体２４０のＧＣ処理における回収効率をＥと定義すると、Ｅ＝（Ｃ−Ａ＋Ｂ−Ｂ）／（Ｃ−Ａ＋Ｂ）＝（Ｃ−Ａ）／（Ｃ−Ａ＋Ｂ）で表される。
【０１２５】
ホストコンピュータ２１０の記憶媒体２４０に対する単位時間あたりのWriteデータ量をチャンク数に換算した値をＷとすると、記憶媒体２４０の内部ではＧＣにおいて単位時間あたりにＷ／Ｅ個のチャンクに対する回収処理が発生する。記憶媒体２４０の物理素子に対してＧＣによる記憶領域の回収が均等に行われる場合、記憶領域２に含まれる断片化状態の各チャンクに含まれるデータがＧＣに伴う移動処理の対象となる時間間隔をＲとすると、Ｒ＝（Ｃ−Ａ＋Ｂ）／（Ｗ／Ｅ）＝（Ｃ−Ａ）／Ｗで表される。
【０１２６】
続いて、断片化解消条件設定部３３１は、記憶媒体２４０に含まれる各チャンクのデータの平均更新頻度から、記憶媒体２４０に含まれる断片化状態の各チャンクが更新されてから次に更新されるまでの平均更新間隔Ｔを算出する。断片化状態のチャンクに含まれるデータが、次に更新されるまでの間に記憶媒体２４０内部のＧＣに伴う移動処理の対象となる回数の期待値は、Ｔ／Ｒ＝Ｔ・Ｗ／（Ｃ−Ａ）で表される。また、断片化状態の各チャンクに関する、更新されるまでの間にＧＣに伴って移動されるデータの総容量をチャンク数で表すと、ＧＣによる1回のデータ移動処理によって１−Ｅチャンク分のデータが移動する。そのため、各チャンクのデータが更新されるまでのＧＣによる総データ移動量Ｍをチャンク数で表すと、Ｍ＝（１−Ｅ）・（Ｔ／Ｒ）＝Ｂ・Ｔ・Ｗ／｛（Ｃ−Ａ＋Ｂ）・（Ｃ−Ａ）｝で表される。
【０１２７】
一方で、断片化状態のチャンクに対して、断片化状態を解消するためにチャンク全体を記憶媒体２４０に対して再格納した場合、記憶媒体２４０に対してチャンクのサイズに等しいWriteが発生する。つまり、断片化状態のチャンクに対する、更新されるまでのＧＣによる総データ移動量Ｍに対してＭ＞１が成り立つ場合に、断片化解消処理を行うことで記憶媒体２４０に対する格納データ量を削減できる。よって、記憶媒体２４０における記憶素子の総容量を表すチャンク数Ｃが既知であり、記憶媒体２４０における、有効なデータを格納するチャンク数Ａ、ホストコンピュータ２１０からの単位時間あたりのWriteデータ量をチャンク数に換算した値Ｗ、断片化状態の各チャンクが更新されてから次に更新されるまでの平均更新間隔Ｔが事前に求められている場合、断片化解消条件設定部３３１は更新によって断片化状態であるチャンクの数Ｂについて、Ｍ＞１が成り立つ最小の整数値を基準として、図１０のステップＳ１００５およびステップＳ１０１７で用いる断片化解消処理の開始および停止条件のチャンク数を決定できる。
【０１２８】
また、断片化解消条件設定部３３１は、Ａ、Ｗ、Ｔについて事前の計測結果を用いて開始条件、停止条件のチャンク数を算出するだけでなく、更新監視部３２１による記憶媒体２４０に対するWrite要求の監視結果を基に、動的に算出してホストコンピュータ２１０から記憶媒体２４０に対するWrite要求の状況に合わせて断片化解消処理の開始条件、停止条件を最適化することが可能である。例えば、有効なデータを格納するチャンク数Ａ、およびホストコンピュータ２１０からの単位時間あたりのWriteデータ量を表すＷは、更新監視部３２１による記憶媒体２４０に対するWrite、消去要求を監視することで算出可能である。加えて、各チャンクの平均更新間隔Ｔは、更新頻度管理テーブル３２２から記憶媒体２４０の各チャンクの更新頻度４１２を取得することで動的に算出可能である。
【０１２９】
なお、上記算出された断片化解消条件のチャンク数を、開始条件および終了条件の共通の閾値として使用して、閾値のチャンク数Ｂとなるように制御することもできるが、開始条件（第１閾値）と終了条件（第２閾値）とを次のように異なるチャンク数に設定することもできる。
【０１３０】
（１）例えば、開始判定のチャンク数Ｂから事前に定めた一定数Ｘ(０≦Ｘ≦Ｂ)を減算した値(Ｂ−Ｘ)を終了判定のチャンク数とする。例えばＸ＝１０とすると、開始から終了までの間に１０個のチャンクに対して断片化解消処理を行うことになる。
（２）開始判定のチャンク数Ｂから事前に定めた一定の割合ｐ(０≦ｐ≦１)を掛けた値である(Ｂ×ｐ)を終了判定のチャンク数とする。
【０１３１】
終了条件の設定は、上記の２種類の方法に限定されず他の方法による設定も可能である。例えば、上記例では算出された断片化解消条件のチャンク数をそのまま開始条件の閾値としたが、算出されたチャンク数に制御されるように、開始条件を(Ｂ＋ｙ)、終了条件を(Ｂ−ｚ)、ｙ＋ｚ＝１０などとすることも考えられる。
【０１３２】
また、本実施形態においては、断片化解消処理開始条件、および／または、断片化解消処理停止条件や、断片化推定条件を条件パラメータに従って算出した。しかし、ホストコンピュータ側のＯＳやアプリケーションなどに応じたチャンク数やチャンク容量を含む過去の条件パラメータおよび条件（閾値や基準値とも称す）と、条件設定による効果との組み合わせの履歴を対応付けて蓄積しておき、新たな条件パラメータを参照して適切な条件設定を設定してもよい。
【０１３３】
本実施形態によれば、論理アドレス空間を一定サイズの単位で分割した各々の論理アドレス領域の断片化状態をホストコンピュータから推定し、断片化状態の論理アドレス領域の数に基づいて断片化解消処理の開始および終了を制御する。これにより、記憶媒体における一定のアクセス性能維持に必要となる、追記形式の記憶領域に対する断片化解消処理の頻度を最小化するように、断片化解消対象の記憶領域を推定することができる。したがって、断片化解消処理に伴うデータ再格納のコストを考慮したうえで、断片化解消処理によって得られる追記形式の記憶媒体内のＧＣによるデータ移動の削減効果を高めることができ、記憶媒体のアクセス性能の向上および長寿命化を図ることができる。
【０１３４】
［第３実施形態］
次に、本発明の第３実施形態に係る記憶制御装置について説明する。本実施形態に係る記憶制御装置は、上記第２実施形態と比べると、断片化解消対象のチャンクが優先順位を有しない点で異なる。その他の構成および動作は、第２実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１３５】
《記憶制御装置の機能構成》
図１１は、本実施形態に係る記憶制御装置１１００の機能構成を示すブロック図である。なお、図１１において、図３と同様の機能構成部には同じ参照番号を付して、重複する説明を省略する。
【０１３６】
断片化管理部１１２０は、更新頻度管理テーブル３２２を有しない。また、断片化解消対象推定部１１２４は、断片化解消対象のチャンクに更新頻度による優先順位を設定しない、断片化解消対象リスト１１２５を生成する。
【０１３７】
また、断片化解消処理部１１３０の断片化解消処理制御部１１３２は、断片化解消条件設定部１１３１の条件に従って、優先順位の設定されていない断片化解消対象リスト１１２５から任意のチャンクを選択して、再格納制御部３３３に再配置を指示する。
【０１３８】
なお、断片化解消条件設定部１１３１において、断片化解消処理の開始条件のみを設定し、断片化解消処理制御部１１３２により断片化解消処理の開始のみを判定する構成であってもよい。
【０１３９】
（断片化解消対象リスト）
図１２は、本実施形態に係る断片化解消対象リスト１１２５の構成を示す図である。なお、図１２において、図４Ｃと同様の構成要素には同じ参照番号を付して、重複する説明を省略する。
【０１４０】
断片化解消対象リスト１１２５は、断片化解消対象に推定されたチャンクのチャンクＩＤ４３２をリストし、各チャンクへの断片化解消処理の優先順位はリストされていない。      
【０１４１】
本実施形態においては、図４Ａの更新頻度４１２による優先順位の設定は行なわれない。したがって、図９に示した断片化管理処理のフローチャートにおいて、ステップＳ９１１〜Ｓ９１５をスルーする。また、図１０に示した断片化解消処理のフローチャートにおいて、ステップＳ１００７では優先順位を考慮せず任意の断片化解消対象のチャンクが再格納制御部３３３に通知される。
【０１４２】
本実施形態によれば、記憶制御装置の構成を簡略化して、簡単な構成によりチャンクの断片化状態を再配置により解消することができる。
【０１４３】
［第４実施形態］
次に、本発明の第４実施形態に係る記憶制御装置を記憶制御部としてホストコンピュータ内に含む情報処理システムについて説明する。本実施形態に係る情報処理システムは、上記第２実施形態および第３実施形態と比べると、断片化が著しいと推定される領域へのWrite処理を代替するためのバッファを有する点で異なる。その他の構成および動作は、第２実施形態、第３実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１４４】
《情報処理システム》
図１３は、本実施形態に係る記憶制御部１３２０を含む情報処理システム１３００の構成を示す図である。なお、図１３において、図２と同様の構成要素には同じ参照番号を付して、重複する説明を省略する。
【０１４５】
図１３の情報処理システム１３００は、バッファ１３６０を含む。バッファ１３６０は、記憶媒体２４０に対するWriteデータのうち、断片化頻度の高いチャンクに対するWrite要求に対応したデータを格納する。バッファ１３６０は、ＤＲＡＭ(Dynamic Random Access Memory)などの記憶媒体２４０より高性能な記憶媒体を用いる以外に、記憶媒体２４０と同様にＳＳＤやＳＭＲを採用したＨＤＤなどを用いることも可能である。また、バッファ１３６０は、記憶媒体２４０の一部領域を割り当てた形でもよい。
【０１４６】
ホストコンピュータ１３１０は、第２実施形態の処理に加えて、記憶媒体２４０またはバッファ１３６０へのWrite処理を制御する記憶制御部１３２０を有する。
【０１４７】
本実施形態によれば、断片化発生頻度の高い領域に対するWriteデータをバッファとして用意した記憶領域に格納して、あらかじめ断片化の発生頻度が高いと推定されたチャンクへの格納を回避することにより、さらに記憶媒体のアクセス性能の向上および長寿命化を図ることができる。
【０１４８】
［第５実施形態］
次に、本発明の第５実施形態に係る記憶制御装置を記憶制御部としてホストコンピュータ内に含む情報処理システムについて説明する。本実施形態に係る情報処理システムは、上記第２実施形態乃至第４実施形態と比べると、記憶制御部が記憶媒体側にある点、あるいは、ネットワークを介してホストコンピュータの外部にある点で異なる。その他の構成および動作は、第２実施形態から第４実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１４９】
《情報処理システムの構成》
図１４は、本実施形態に係る記憶制御部１４４３または１４２０を含む情報処理システム１４００の構成を示す図である。なお、図１４において、図２と同様の構成要素には同じ参照番号を付して、重複する説明を省略する。
【０１５０】
図１４においては、ホストコンピュータ１４１０は本実施形態の記憶制御部を有しない。一例として、本実施形態の記憶制御部１４４３は、記憶媒体１４４０に搭載されている。また、他の例として、本実施形態の記憶制御部１４２０は、ネットワーク２５０を介して独立した装置として接続されている。かかる記憶制御部１４４３または１４２０は、ソフトウェアで実現されても、ワンチップのプロセッサで実現されてもよい。
【０１５１】
本実施形態によれば、第２乃至第４実施形態のようにホストコンピュータによる処理に限定されず、記憶媒体への書き込みにおけるチャンクの断片化状態を推定して、断片化状態を再配置により解消することで、記憶媒体のアクセス性能の向上、長寿命化を図ることができる。
【０１５２】
［他の実施形態］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【０１５３】
また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する情報処理プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされるプログラム、あるいはそのプログラムを格納した媒体、そのプログラムをダウンロードさせるＷＷＷ(World Wide Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、上述した実施形態に含まれる処理ステップをコンピュータに実行させるプログラムを格納した非一時的コンピュータ可読媒体（non-transitory computer readable medium）は本発明の範疇に含まれる。
【図１】
0006668785.tif 000002
【図２】
0006668785.tif 000003
【図３】
0006668785.tif 000004
【図４Ａ】
0006668785.tif 000005
【図４Ｂ】
0006668785.tif 000006
【図４Ｃ】
0006668785.tif 000007
【図４Ｄ】
0006668785.tif 000008
【図４Ｅ】
0006668785.tif 000009
【図５】
0006668785.tif 000010
【図６】
0006668785.tif 000011
【図７】
0006668785.tif 000012
【図８】
0006668785.tif 000013
【図９】
0006668785.tif 000014
【図１０】
0006668785.tif 000015
【図１１】
0006668785.tif 000016
【図１２】
0006668785.tif 000017
【図１３】
0006668785.tif 000018
【図１４】
0006668785.tif 000019