(57)【要約】【課題】長時間の連続的なコンパクション動作をなくすことで、ライトコマンドに対する大きな応答の遅れを防ぐ。【解決手段】ライト制御部による書き込み処理と整理部によるデータ整理は所定の比率をもって交互に実行される。整理部は、所定の比率に対応するデータ整理の最中に、無効である有効無効判定の結果が所定の設定回数連続した場合、今回の有効無効判定処理を終了させる。【選択図】図１
2013200726.tif 000002
【特許請求の範囲】
【請求項１】
ブロック単位で消去が行われる不揮発性半導体メモリと、
ホスト装置からのデータを前記不揮発性半導体メモリのブロックに書き込むライト制御部と、前記不揮発性半導体メモリの整理対象ブロックに記憶された各データが有効か無効かを判定し、有効と判定されたデータを順次選択して新たなブロックへ書き直すデータ整理を行う整理部とを有し、前記ライト制御部による書き込み処理と前記整理部による新たなブロックへ書き直しを所定の比率をもって交互に実行するコントローラと、
を備え、
前記整理部は、前記所定の比率に対応する前記データ整理の最中に、無効である有効無効判定の結果が所定の設定回数連続した場合、今回の有効無効判定処理を終了させる
ことを特徴とする半導体記憶装置。
【請求項２】
前記整理部は、無効である有効無効判定の結果が所定の設定回数連続した場合、無効なダミーデータを前記新たなブロックに書き込むことを特徴とする請求項１に記載の半導体記憶装置。
【請求項３】
ホスト装置から指定された論理アドレスを前記不揮発性半導体メモリでの記憶位置に対応付ける正引き情報を管理するためアドレス変換テーブルを更に備え、
ライト制御部は、データの論理アドレスを含む逆引き情報が付加されたデータを前記不揮発性半導体メモリのブロックに書き込み、
前記整理部は、各データに付加された逆引き情報と前記アドレス変換テーブルの正引き情報とを照合することにより、各データが有効か無効かを判定する
ことを特徴とする請求項１または２に記載の半導体記憶装置。
【請求項４】
ブロック単位で消去が行われる不揮発性半導体メモリと、
ホスト装置からのデータを前記不揮発性半導体メモリのブロックに書き込むライト制御部と、前記不揮発性半導体メモリの整理対象ブロックに記憶された各データが有効か無効かを判定し、有効と判定されたデータを順次選択して新たなブロックへ書き直すデータ整理を行う整理部とを有し、前記ライト制御部による書き込み処理と前記整理部による新たなブロックへ書き直しを所定の比率をもって交互に実行するコントローラと、
を備え、
前記整理部は、前記データ整理が所定時間以上連続した場合、データ整理を中断して前記ライト制御部による書き込み処理を実行させる
ことを特徴とする半導体記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性半導体メモリを備えた半導体記憶装置に関する。
【背景技術】
【０００２】
ＳＳＤ（solid state drive）において、データの消去単位（ブロック）と、データの管理単位が異なる場合、フラッシュメモリの書き換えが進むと、無効な（最新ではない）データによって、ブロックは穴あき状態になる。このような穴あき状態のブロックが増えると、実質的に使用可能なブロックが少なくなり、フラッシュメモリの記憶領域を有効利用できなくなる。そこで、例えば、フラッシュメモリのフリーブロック（内部に有効データを含まない、用途未割り当ての未使用ブロック）が所定の閾値より少なくなった場合、ブロック内の有効データを集めて別のブロックに書き直すコンパクションなどのフラッシュメモリの整理を実行し、用途未割り当てのフリーブロックを確保する。
【０００３】
ＳＳＤに対し、ホスト装置からライト要求が入力されたときに、コンパクションが動作し続けると、ライト要求に対する応答が遅くなる。コンパクションを行なわないとフリーブロックが確保できないなどコンパクションを行なう必要があるときもあるが、コンパクションを行なわなくてもフリーブロックが存在する時は、ライト要求に対する応答を優先するのが望ましい。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２７６７３３号公報
【特許文献２】特開２０１０−１５２７７８号公報
【特許文献３】特開２００８−２５７７７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の一つの実施形態は、長時間の連続的なコンパクション動作をなくすことで、ライトコマンドに対する大きな応答の遅れを防ぐ半導体記憶装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一つの実施形態によれば、半導体記憶装置は、不揮発性半導体メモリとコントローラとを備える。不揮発性半導体メモリでは、ブロック単位で消去が行われる。コントローラは、ホスト装置からのデータを前記不揮発性半導体メモリのブロックに書き込むライト制御部と、前記不揮発性半導体メモリの整理対象ブロックに記憶された各データが有効か無効かを判定し、有効と判定されたデータを順次選択して新たなブロックへ書き直すデータ整理を行う整理部とを有し、前記ライト制御部による書き込み処理と前記整理部による新たなブロックへ書き直しを所定の比率をもって交互に実行する。前記整理部は、前記所定の比率に対応する前記データ整理の最中に、無効である有効無効判定の結果が所定の設定回数連続した場合、今回の有効無効判定処理を終了させる。
【図面の簡単な説明】
【０００７】
【図１】図１は、ＳＳＤの内部構成例を示すブロック図である。
【図２】図２は、アドレス変換テーブルを示す図である。
【図３】図３は、ブロック管理テーブルを示す図である。
【図４】図４は、ブロック管理を概念的に示す図である。
【図５】図５は、データに付加される逆引き情報を示す図である。
【図６】図６は、データの有効無効判定処理を概念的に示す図である。
【図７】図７は、１：Ｎコンパクションを概念的に示す図である。
【図８】図８は、比較例による１：Ｎコンパクションの動作手順例を示すフローチャートである。
【図９】図９は、コンパクション元ブロックの一例を示す図である。
【図１０】図１０は、実施形態による１：Ｎコンパクションの動作手順例を示すフローチャートである。
【図１１】図１１は、実施形態によるダミーデータの書き込みを概念的に示す図である。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態にかかる半導体記憶装置を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。
【０００９】
（第１の実施形態）
図１は、ＳＳＤ（Solid  State  Drive）１００の構成例を示すブロック図である。ＳＳＤ１００は、ＡＴＡインタフェース（ＡＴＡ  Ｉ／Ｆ）などのホストインタフェース２を介してパーソナルコンピュータあるいはＣＰＵなどのホスト装置（以下、ホストと略す）１と接続され、ホスト１の外部記憶装置として機能する。ホスト１は、例えば、パーソナルコンピュータのＣＰＵ、スチルカメラ、ビデオカメラなどの撮像装置のＣＰＵである。ＳＳＤ１００は、ホストインタフェース２と、不揮発性半導体メモリとしてのＮＡＮＤ型フラッシュメモリ（以下、ＮＡＮＤと略す）１０と、ＮＡＮＤ１０よりも高速アクセスが可能でランダムアクセス可能な半導体メモリであるＲＡＭ２０と、ＮＡＮＤコントローラ（ＮＡＮＤＣ）３１と、コントローラ３０とを備える。
【００１０】
ＮＡＮＤ１０は、ホスト１によって指定されたユーザデータ１１を記憶したり、ＲＡＭ２０で管理される管理情報を不揮発管理テーブル１２としてバックアップ記憶する。ＮＡＮＤ１０は、複数のメモリセルがマトリクス状に配列されたメモリセルアレイを有し、個々のメモリセルは上位ページ及び下位ページを使用して多値記憶が可能である。ＮＡＮＤ１０は、複数のメモリチップによって構成され、各メモリチップは、データ消去の単位である物理ブロックを複数配列して構成される。また、ＮＡＮＤ１０では、物理ページごとにデータの書き込み及びデータの読み出しが行われる。物理ブロックは、複数の物理ページによって構成されている。
【００１１】
ＲＡＭ２０は、ホスト１からのデータをＮＡＮＤ１０にライトする際に一時的にデータを保存するためのライトバッファ２５としての記憶領域と、アドレス変換テーブル２１、ブロック管理テーブル２２などの管理情報を記憶、更新するための記憶領域と、ＮＡＮＤ１０からリードされたデータを一時記憶するなどのための作業領域を有する。アドレス変換テーブル２１、ブロック管理テーブル２２などの管理情報は、ＮＡＮＤ１０に記憶されている不揮発管理テーブル１２が起動時などに展開されたものである。
【００１２】
ＮＡＮＤＣ３１は、ＮＡＮＤ１０とのインタフェース処理を行うＮＡＮＤ  Ｉ／Ｆ、誤り訂正回路、ＤＭＡコントローラなどを備えており、ＲＡＭ２０に一時記憶されたデータをＮＡＮＤ１０に書き込んだり、ＮＡＮＤ１０に記憶されているデータを読み出してＲＡＭ２０に転送したりする。
【００１３】
ホスト１はＳＳＤ１００に対し、リードまたはライトする際には、ホストインタフェース２を介して論理アドレスとしてのＬＢＡ（Logical Block Addressing）をＳＳＤ１００に入力する。ＬＢＡは、セクタ（サイズ：例えば５１２Ｂ）に対して０からの通し番号をつけた論理アドレスである。本実施の形態においては、ライトバッファ２５，ＮＡＮＤ１０でデータを管理する単位として、セクタサイズよりも大きく、物理ブロックサイズよりも小さいクラスタという管理単位を定義する。この実施形態では、クラスタという１つの管理単位を使用するが、クラスタよりサイズが大きく、ブロックサイズ以下のサイズである他の管理単位を追加し、２つの管理単位を使用してもよい。この実施形態では、簡単化のためにクラスタサイズは、ページサイズと同じとする。
【００１４】
コントローラ３０は、ブロック管理部３１と、データアクセス部３２とを備える。データアクセス部３２は、リード制御部３３、ライト制御部３４、整理部３５を備える。
【００１５】
ブロック管理部３１は、ブロックの使用状態（使用中であるアクティブブロックであるか未使用であるフリーブロックであるか）を管理するとともに、エラーが多いなど記憶領域として使用できないバッドブロックを識別管理する。ブロック管理部３１は、データアクセス部３２に対して、使用すべきフリーブロックまたはアクティブブロックを通知する。また、ブロック管理部３１は、ホスト１からの書き込みとコンパクションの動作比率を示すギア比（後述する）の制御を行い、このギア比をデータアクセス部３２に通知する。
【００１６】
データアクセス部３２は、ホスト１から指定されたデータのリードライト制御や、ＮＡＮＤ１０の整理（コンパクション）などを実行する。データアクセス部３２は、ブロック供給元であるブロック管理部３１から通知されるフリーブロックを使用してホスト１から指定されたデータのライト制御を行い、またブロック管理部３１から通知されるアクティブブロック（コンパクション元ブロック）およびフリーブロック（コンパクション先ブロック）を使用してコンパクションを実行する。さらに、データ管理部３３は、ブロック管理部３１から通知されたギア比にしたがって、ホスト１からの書き込みとコンパクションを行うことで１：Ｎコンパクション（後述する）を実現する。
【００１７】
リード制御部３３は、ホスト１からリードコマンドおよびリードアドレスとしてのＬＢＡが入力されると、正引きのアドレス変換テーブル２１を参照してＬＢＡに対応するデータをＮＡＮＤ１０から読み出し、読み出したデータをホスト１に送信する。
【００１８】
ライト制御部３４は、ライコマンド、ライトアドレスとしてのＬＢＡ、ライトデータが入力されると、ＬＢＡで指定されたデータをライトバッファ２５に書き込む。ライトバッファ２５に空き領域がない場合は、ライトバッファ２５からデータを追い出して、追い出したデータをブロック管理テーブル２２などを参照してＮＡＮＤ１０に書き込む。この書き込みに応じて、アドレス変換テーブル２１、ブロック管理テーブル２２などを更新する。
【００１９】
整理部３５は、ＮＡＮＤ１０でのデータ整理（コンパクション）を実行する。ＮＡＮＤ１０は、ブロック単位で消去し、ページ単位で追記書き込みを行う記憶デバイスである。そのため、ＮＡＮＤ１０では、上書きはできず、書き込みは常に消去済みの未書き込みなページ領域に対して行われる。書き込みを繰り返していると、未使用なフリーブロックは徐々に無くなっていき、ある時点で新規に使えるフリーブロックが無くなってしまう。また、書き込みを繰り返し行うことにより、有効なデータと無効なデータが混在するブロックや無効なデータのみを含むブロックが発生してくる。そこで、複数のブロックから有効なデータを集めて新規のフリーブロックにデータを移動させるコンパクションを行うことによって、コンパクション元のブロックが無効なデータ領域となり、コンパクション元のブロックをフリーブロックとして使用することができる。コンパクション処理を行うことによって、再びフリーブロックを生成することができ、ＮＡＮＤ１０に対し新たなデータの書き込みを行うことができる。
【００２０】
図２に示すように、ＲＡＭ２０で管理されるアドレス変換テーブル２１には、ＬＢＡのクラスタアドレスと、クラスタデータが記憶されているＮＡＮＤ１０上の記憶位置（物理アドレス：例えばブロック番号＋ブロック内記憶位置）と、当該クラスタにデータが存在するか否かを示すデータ有無フラグとの対応が登録されている。クラスタアドレスとは、ＬＢＡをクラスタサイズで割ったものである。このアドレス変換テーブル２１は、論理アドレスからその論理アドレスに対応するデータが存在する記憶デバイス位置を検索することができ、正引きテーブルとして機能する。４この正引きのアドレス変換テーブル２１は、リード処理などに使用される。また、ＮＡＮＤ１０へのデータの書き込みによって、クラスタアドレスとＮＡＮＤ上の記憶位置との関係が異なった場合、アドレス変換テーブル２１が更新される。
【００２１】
図３に示すように、ＲＡＭ２０で管理されるブロック管理テーブル２２には、ブロック番号毎に、各ブロックがアクティブブロックであるかフリーブロックであるかを示すブロック使用／未使用情報や、エラーが多いなど記憶領域として使用できないバッドブロックを識別する不良ブロックフラグなどが登録されている。このブロック管理テーブル２２を使用して、ＮＡＮＤ１０に対する書き込みの際に使用するフリーブロックを選択する。また、ブロック管理テーブル２２を使用して、コンパクションの際に使用するフリーブロック（コンパクション先ブロック）を選択する。
【００２２】
図４は、ＳＳＤ１００でのブロック管理を概念的に示す図である。ブロックは、前述したように、アクティブブロックとフリーブロックに分類される。例えば、同じＬＢＡのデータを上書きする場合は、つぎのような処理が行われる。論理アドレスＡ１にブロックサイズの有効なデータが保存されており、記憶領域としてはブロックＢ１が使用されていたとする。ホスト１から論理アドレスＡ１のブロックサイズの更新データを上書きするコマンドを受信した場合、フリーブロック（ブロックＢ２とする）を１個確保し、そのフリーブロックにホスト１から受信したデータを書き込む。その後、論理アドレスＡ１とブロックＢ２を関係付ける。その結果、ブロックＢ２はアクティブブロックになり、ブロックＢ１に保存されたデータは無効になるためブロックＢ１はフリーブロックとなる。
【００２３】
このように、ＳＳＤ１００では、同じ論理アドレスＡ１のデータであっても、実際の記録領域として使用されるブロックは書込みの度に変化する。なお、ブロックサイズの更新データ書き込みでは、必ず書き込み先ブロックが変化するが、ブロックサイズ未満の更新データ書き込みでは、同じブロックに更新データが書き込まれることもある。例えばブロックサイズ未満のページデータが更新される場合、当該ブロック内において同じ論理アドレスの旧ページデータが無効化され、新たに書き込まれた最新のページデータが有効ページとして管理される。ブロック内の全データが無効化されると、当該ブロックはフリーブロックとして解放される。
【００２４】
図４において、ホスト１からのデータは、書き込み先ブロック（フリーブロック）に書き込まれる。ホスト１からのデータが書き込まれたブロックはアクティブブロックとなる。アクティブブロックは、ＮＡＮＤ１０の書き換えが進むと、フリーブロックとして解放されたり、コンパクションでの書き込み元のブロックを経てフリーブロックとして解放されたりする。フリーブロックは、その後、ホスト１からのユーザデータをライトするための書き込み先ブロックや、コンパクションにおいてデータをライトするためのコンパクション先ブロックとして利用される。
【００２５】
ここで、アドレス変換テーブル２１では、論理アドレスとしてのＬＢＡからこのＬＢＡに対応するデータのＮＡＮＤ１０で記憶位置を検索する正引きの検索が行われ、このアドレス変換テーブル２１は、リード処理などに使用される。一方、ＮＡＮＤ１０でのデータの記憶位置から論理アドレスとしてのＬＢＡを検索する処理は、逆引きの検索であり、この逆引きの検索は、主に、コンパクションの際に使用される。逆引きのアドレス変換テーブルを用意してもよいが、逆引きのアドレス変換テーブルは、ＮＡＮＤ１０、ＲＡＭ２０で多くの記憶領域を使用するので、この実施形態では、図５に示すように、クラスタデータＤｃｌに、当該クラスタデータの逆引き情報ＧＩを付加し、逆引き情報ＧＩが付加されたクラスタデータＤｃｌをＮＡＮＤ１０に記憶する。
【００２６】
逆引き情報ＧＩは、逆引き情報が付加されるクラスタデータＤｃｌの論理アドレス（ＬＢＡ）を有している。逆引き情報ＧＩとして、ＬＢＡの他に、当該クラスタデータＤｃｌが有効か無効かを示す有効フラグを持たせるようにしてもよいが、そのためには、ＮＡＮＤ１０上で頻繁な有効フラグの更新が発生し、非現実的であるので、ここでは逆引き情報ＧＩとして、有効フラグを持たずＬＢＡのみを持っている場合のクラスタデータＤｃｌの有効無効判定について説明する。
【００２７】
ＬＢＡ＝Ａ０の論理アドレスを持つクラスタデータＧ０をＮＡＮＤ１０上の位置（ページ）Ｐ０に書き込むとする。クラスタデータＧ０に付加される逆引き情報ＧＩは、論理アドレスＡ０を持つ。次に、ＬＢＡ＝Ａ０が異なるデータＧ１によって更新された場合、ＮＡＮＤ１０の場合、書き込み済みの物理的位置に上書きすることはできないため、このデータＧ１は、物理的には異なる位置（ページ）Ｐ１に書き込まれる。クラスタデータＧ１に付加される逆引き情報ＧＩも、論理アドレスＡ０を持つことになる。この段階では、データＧ１が論理アドレスＡ０の最新のデータとなるので、データＧ０は無効データとなり、データＧ１は有効データとなる。しかし、この場合は、逆引き情報ＧＩに有効フラグを持たせないようにしているので、データＧ０に付加される逆引き情報（ＬＢＡ＝Ａ０）と、データＧ１に付加される逆引き情報（ＬＢＡ＝Ａ０）のみを見たのでは、それぞれが自身が論理アドレスＡ０のデータであるという情報を持つのみで、どちらが有効であるかを識別することはできない。
【００２８】
そこで、正引きのアドレス変換テーブル２１と逆引き情報ＧＩを照合し、お互いを指し合っているものが有効データで、片方だけしか指していないものを無効データと判定する有効無効判定を実行する。具体的には、コンパクションの際には、あるブロックのクラスタデータを別のブロックに移動させようとしたとき、無効なデータは移動する必要がなく、有効なデータのみを移動させるので、そのクラスタデータが有効か否かを有効無効判定処理によって判断する。コンパクション対象の各ブロックに含まれる各クラスタデータが無効か有効かを順次判定していくので、まず判定対象のクラスタデータに付加されている逆引き情報ＧＩを読み出し、この逆引き情報ＧＩが指し示している論理アドレス（ＬＢＡ）と一致するアドレス変換テーブル２１のエントリを取り出し、このエントリ内の正引き情報が判定対象のクラスタデータの記憶位置を指し示しているか否かを判定し、指し示しているときに、当該判定対象のクラスタデータが有効であると判定する。しかし、正引き情報が他の記憶位置を指し示しているときは、当該判定対象のクラスタデータが無効であると判定する。このような有効無効判定処理を、コンパクション対象のブロック内の各クラスタデータに関して繰り返し実行することで、所要数の有効なクラスタデータを集める。
【００２９】
図６は、上述したデータＧ０とデータＧ１に関する有効無効判定を示すものである。位置Ｐ０に記憶されているクラスタデータＧ０に付加される逆引き情報ＧＩはＬＢＡ＝Ａ０であるので、アドレス変換テーブル２１のＬＢＡ＝Ａ０のエントリに含まれる正引き情報を取得する。この正引き情報はＬＢＡ＝Ａ０の論理アドレスのデータが位置Ｐ１に存在することを示しているので、逆引き情報と正引き情報の照合結果は不一致となり、このクラスタデータＧ０は無効と判定される。位置Ｐ１に記憶されているクラスタデータＧ１に付加される逆引き情報ＧＩはＬＢＡ＝Ａ０であるので、同様に、アドレス変換テーブル２１のＬＢＡ＝Ａ０のエントリに含まれる正引き情報を取得する。この正引き情報はＬＢＡ＝Ａ０の論理アドレスのデータが位置Ｐ１に存在することを示しているので、逆引き情報と正引き情報の照合結果が一致となり、このクラスタデータＧ０は有効と判定される。
【００３０】
このように、有効無効判定を行うには、読み出し対象のクラスタデータの逆引き情報ＧＩをＮＡＮＤ１０から読み出す必要がある。また、逆引き情報ＧＩと正引きのアドレス変換テーブル２１の照合を行なわなければならず、一定の処理時間が発生する。つまり、クラスタデータを別のブロックに移動するコンパクション処理の実際のデータの移動（読み出しおよび書き込み）が発生しなくても、有効無効判定を繰り返し行うことは一定の処理時間が発生することになる。判定対象のクラスタデータが有効なデータである場合には、コンパクション先ブロックへの書き込みが発生するが、判定対象のクラスタデータが無効なデータだった場合は、コンパクション先ブロックへの書き込みは発生しない。
【００３１】
フリーブロックが多く存在している時は、コンパクションを行う必要がないが、一定量の書き込みがされてフリーブロックが少なくなったときは、コンパクションを行う必要がある。フリーブロックがほとんど無くなってからコンパクションによりフリーブロックを作り出そうとすると、ホスト１からのライトコマンドに対する応答が悪くなる。なぜならば、まず、コンパクションによりフリーブロックを作り出すための処理時間がかかり、その処理時間の経過後にフリーブロックが用意できた時点でホスト１からのデータの書き込みが可能となるからである。
【００３２】
そこで、本実施形態では、ライトコマンドに対する応答速度を極端に低下させないために、ホスト１からのデータ書き込みとコンパクションによる書き込みを一定の割合（比率）で動作させる手法を採用している。ホスト１からのデータ書き込みが１ブロック（１ページ）に対して、コンパクションによる書き込みをＮブロック（Ｎページ）行う手法を、ギア比が１：Ｎのコンパクションという。
【００３３】
ホストデータの書き込み先ブロックをHostDstと呼び、コンパクション先ブロックをCmpDstと呼び、コンパクション元ブロックをCmpSrcと呼ぶ。HostDstに１ページ書くことに対して、CmpDstにＮページ書くことにより、１：Ｎコンパクションが行われる。HostDstに１ブロック分のデータを書く期間をコンパクションタームと呼ぶ。本実施形態では、ページサイズとクラスタサイズを同じとしているので、HostDstに１クラスタデータ書くことに対して、CmpDstにＮクラスタデータを書くことにより、１：Ｎコンパクションが行われる。
【００３４】
フリーブロックがブロック全体のうち、一定量以上の十分な数が存在するときは、コンパクションを行う必要がなく、HostDstに対する書き込みのみを行う。これを１：０コンパクションという。通常、１：０コンパクションから動作開始して、フリーブロックが少なくなってきてアクティブブロックが増えてきたら、１：１や１：２のコンパクションを行う。フリーブロックが少ない場合などコンパクションを多めにしたいときは、１：ＮのＮを大きくする。ところが、Ｎが大きな１：Ｎコンパクションでは、ホストデータのブロックHostDstの全ページへの書き込みが終了しても、コンパクションで次のフリーブロックを確保ができない場合、つまりコンパクション処理でフリーブロックを生成するのが間に合わず、ホストデータの書き込み先ブロックHostDstの確保が待たされる場合、結果的にギア比は０：１となり、ホスト１からの書き込みを一時的に保留され、コンパクション処理のみを行うことになる。このように、ギア比を変えることにより、ホスト１からのデータ書き込みと、コンパクションによる書き込みのバランスを取りながら動作させることが可能となる。例えば、ギア比は、フリーブロックとアクティブブロックの割合から決定する。
【００３５】
ギア比の制御は、ブロック供給元であるブロック管理部３１が行う。ブロック要求元であるデータアクセス部３２は、ブロック管理部３１から与えられたギア比に応じて、ホスト１からのデータの書き込み動作（ライト制御部３４）とコンパクション動作（整理部３５）を行うだけで、整理部３５のコンパクション結果(どの程度フリーブロックが作成できるかなど)に対しての責任は持たない。これにより、データアクセス部３２は、単純な動作処理のみを行なうハードウェアあるいはソフトウェアにて実現できる。
【００３６】
図７は、ギア比が１：３のコンパクションを示している。図７では、４つのアクティブブロックであるコンパクション元ブロックCmpSrc内の有効クラスタデータを３つのフリーブロックであるコンパクション先ブロックCmpDstに移動することで、１つ分のフリーブロックを作成するコンパクションを行っている。この場合は、１：３のコンパクションであるので、ホスト１からのデータを１つのブロックHostDstに書き込むのに対し、コンパクションによる書き込みを３つのブロックCmpDstに行っている。
【００３７】
図８は、比較例による１：Ｎのコンパクション手順を示すものである。まず、ホスト１からのライトデータが１ページ分だけブロックHostDstにライトされる（ステップＳ１００）。つぎに、コンパクション元ブロックCmpSrc内のデータが１ページ分読み出され（ステップＳ１１０）、前述のデータの有効無効判定が行われる（ステップＳ１２０）。データが無効であった場合は（ステップＳ１３０：Ｎｏ）、コンパクション元ブロックCmpSrc内の次のページのデータを読み出され（ステップＳ１１０）、その後同様の有効無効判定が行われる（ステップＳ１２０）。このようにして、有効なデータを発見できるまで有効無効判定が行われる。有効なデータが発見されると（ステップＳ１３０：Ｙｅｓ）、この有効データがコンパクション先ブロックCmpDstに書き込まれる（ステップＳ１４０）。
【００３８】
つぎに、コンパクション先ブロックCmpDstへの書き込みがＮ回繰り返されたか否かが判定され（ステップＳ１５０）、コンパクション先ブロックCmpDstへの書き込みがＮ回未満の場合は、手順がステップＳ１１０に移行される。このようにして、コンパクション先ブロックCmpDstへの書き込みがＮ回終了するまでは、データの有効無効判定と、コンパクション先ブロックCmpDstへのデータ書込みが繰り返される。そして、コンパクション先ブロックCmpDstへのＮ回の書き込みが終了すると、今回のホストデータに関する１：Ｎのコンパクション手順が終了したか否かが判定され（ステップＳ１６０）、終了していない場合は、手順がステップＳ１００に移行されて、今度は、ホスト１からのライトデータが次の１ページ分だけブロックHostDstにライトされる。このような処理が繰り返される。ステップＳ１６０において、今回のホストデータに関する１：Ｎのコンパクション手順が終了したと判定されると、今回のホストデータに関する１：Ｎのコンパクション手順が終了される。
【００３９】
このようにして、基本的には、ブロックHostDstへの１ページ書き込みと、コンパクション先ブロックCmpDstへのＮページの有効データの書き込みとが、交互に行われる。
【００４０】
ところが、コンパクション処理は、前述したコンパクション先ブロックCmpDstの状態（フリーブロック数など）だけでなく、コンパクション元ブロックCmpSrcの状態によっても書き込みの進行状態が変わってくる。図８に示した比較例では、コンパクション元ブロックCmpSrcが有効データで詰まっているときは、ステップＳ１２０、Ｓ１３０の有効無効判定において有効判定が頻繁に発生し、コンパクション先ブロックCmpDstへの書き込み（ステップＳ１４０）は、頻繁に行われる。しかしながら、比較例では、図９に示すように、コンパクション元ブロックCmpSrcに無効データで詰まってて有効データが最後のページ付近にしか存在しない場合は、有効データを発見できるまで、ステップＳ１１０〜Ｓ１３０の有効無効判定処理がループし続ける。
【００４１】
コンパクション処理は、有効なデータを整理して、有効なデータをフリーブロックに詰めて無効なデータ領域を作ることにより、フリーブロックを確保しようというものである。そのため、有効なデータで全て詰まったブロックからデータの引っ越しをしても領域確保の効果がない。むしろ、前述したように、コンパクション元ブロックCmpSrcは、無効なデータ領域が多いほうが、フリーブロックを多く確保するためには、効率がよい。
【００４２】
比較例では、ステップＳ１４０におけるコンパクション先ブロックCmpDstへの書き込みが進まないと、ホストデータのブロックHostDstへの書き込みも進まないため、ホスト１から見るとライトコマンドに対する応答が遅くなるように見える。このように、コンパクション元ブロックCmpSrcに無効なデータが多くあるほうがフリーブロックの作成のためには効率的であるのにもかかわらず、比較例の手法では、コンパクション元ブロックCmpSrcに無効なデータが多く存在した場合、ライトコマンドの応答速度が低下するという問題がある。
【００４３】
そこで、本実施形態では、有効無効判定処理において、無効であるとする判定が所定回数Ｋ以上連続した場合は、有効無効判定処理のループ（ステップＳ１１０〜Ｓ１３０）を脱出させることで、ライトコマンドの応答速度が極端に低下しないようにする。
【００４４】
図１０は、本実施形態の１：Ｎのコンパクション手順を示すものである。図１０は、図８のフローチャートにステップＳ１３１，Ｓ１３２の手順を追加している。ブロック管理部３１は、例えば現在のフリーブロックとアクティブブロックの個数割合からギア比Ｎを決め、このギア比Ｎをデータアクセス部３２に与える。また、ブロック管理部３１は、後述する無効判定の上限回数Ｋを決め、この上限回数Ｋをデータアクセス部３２に与える。データアクセス部３２は、与えられたギア比Ｎを管理下のライト制御部３４および整理部３５に通知する。また、データアクセス部３２は、与えられた上限回数Ｋを整理部３５に通知する。ライト制御部３４および整理部３５は、与えられたギア比Ｎに従って、ＮＡＮＤ２０への書き込み権限を相互に交替しながら、前述の１：Ｎコンパクションを行う。
【００４５】
まず、ライト制御部３４は、ホスト１からのライトデータを１ページ分（＝１クラスタ分）だけブロックHostDstにライトする（ステップＳ１００）。この１ページ分の書き込み処理が終了すると、ライト制御部３４は、ＮＡＮＤ１０への書き込み権限を整理部３５に渡す。
【００４６】
整理部３５は、整理対象ブロックの一つであるコンパクション元ブロックCmpSrc内のデータを１ページ分読み出し（ステップＳ１１０）、この１ページ分のデータに対し前述の有効無効判定を実行する（ステップＳ１２０）。整理部３５はこのデータが有効データであった場合（ステップＳ１３０：Ｙｅｓ）、この有効データをコンパクション先ブロックCmpDstに書き込む（ステップＳ１４０）。しかし、整理部３５は、このデータを無効と判定した場合（ステップＳ１３０：Ｎｏ）、ステップＳ１３０での無効判定が所定回数Ｋ以上繰り返されたか否かを判定する（ステップＳ１３１）。このステップＳ１３１の判定がＮｏである場合は、整理部３５は、手順をステップＳ１１０に移行させて、コンパクション元ブロックCmpSrc内の次のページのデータを読み出す。この後、整理部３５は、同様の有効無効判定が行う（ステップＳ１２０）。このように、整理部３５は、ステップＳ１３０、Ｓ１３１、Ｓ１１０、Ｓ１２０のループを最大Ｋ−１回繰り返すことで、有効なデータを発見できるまで有効無効判定が実行する。有効なデータが発見されると、整理部３５によってこの有効な１ページ分のデータがコンパクション先ブロックCmpDstに書き込まれる（ステップＳ１４０）。
【００４７】
しかし、ステップＳ１３０、Ｓ１３１、Ｓ１１０，Ｓ１２０のループを繰り返している際に、ステップＳ１３１において、ステップＳ１３０での無効判定が所定回数Ｋ以上繰り返されたと判定されると、整理部３５は、図１１に示すように、無効なダミーデータをコンパクション先ブロックCmpDstに１ページ分、書き込む（ステップＳ１３２）。無効なダミーデータとは、当該データが無効であることを識別させる無効フラグを含むものであれば、任意のデータでよい。なお、ステップＳ１３１の判定は、Ｋページ分連続して無効判定結果が出た場合、あるいは、コンパクション先ブロックCmpDstへの有効データの書き込みを１ページでも行うとクリアされるカウンタによって実現可能である。
【００４８】
つぎに、整理部３５は、コンパクション先ブロックCmpDstへの１ページ書き込みがＮ回繰り返されたか否かを判定する（ステップＳ１５０）。コンパクション先ブロックCmpDstへの書き込み回数を計数するとき、ステップＳ１３２での無効ダミーデータの書き込みも１回として計数される。コンパクション先ブロックCmpDstへの書き込みがＮ回未満の場合は、手順がステップＳ１１０に移行される。このようにして、コンパクション先ブロックCmpDstへの書き込みがＮ回終了するまでは、データの有効無効判定と、コンパクション先ブロックCmpDstへの有効データまたは無効ダミーデータの書込みが繰り返される。
【００４９】
そして、コンパクション先ブロックCmpDstへのＮ回の書き込みが終了すると、整理部３５は、今回のホストデータに関する１：Ｎのコンパクション手順が終了したか否かを判定し（ステップＳ１６０）、終了していない場合は、整理部３５は、ＮＡＮＤ１０への書き込みの権限をライト制御部３４に渡す。この結果、手順がステップＳ１００に移行されて、今度は、ライト制御部３４によって、ホスト１からのライトデータが次の１ページ分だけブロックHostDstにライトされる。このような処理が繰り返される。ステップＳ１６０において、今回のホストデータに関する１：Ｎのコンパクション手順が終了したと判定されると、今回のホストデータに関する１：Ｎのコンパクション手順が終了される。
【００５０】
このようにして、基本的には、ブロックHostDstへの１ページ書き込みと、コンパクション先ブロックCmpDstへのＮページの有効データまたは無効ダミーデータの書き込みとが、ギア比に従って交互に行われる。
【００５１】
本実施形態では、図１１に示したように、Ｋページ分連続して無効判定結果が出た場合、無効なダミーデータをコンパクション先ブロックCmpDstに書き込むようにしているので、コンパクションタームのギア比が実質的には崩れることになるが、ホストデータ書込みのためのブロックHostDstとコンパクション先ブロックへの書き込みの進捗比率を守ることが可能となる。
【００５２】
なお、上記実施形態では、ライト制御部３４がホスト１からのデータ書込みを行い、整理部３５がコンパクション処理全般を行うようにしたが、整理部３５がコンパクション元ブロックからのデータ読み出しと、読み出したデータの無効判定処理を行い、ライト制御部３４がホスト１からのデータ書込みと、コンパクション先ブロックへのデータ書込みを行うように、機能分担させたほうが望ましい。このような機能分担を行った場合、本実施形態では、次のような利点がある。本実施形態では、Ｋページ分連続して無効判定結果が出た場合、コンパクション先ブロックCmpDstへの書き込むをスキップせずに、無効なダミーデータをコンパクション先ブロックCmpDstに書き込むという機能を、比較例に対し追加しているが、この機能追加は、整理部３５に対する機能追加のみで済み、ライト制御部３４への機能変更を行わずに済む。すなわち、コンパクション先ブロックCmpDstへの書き込みをスキップさせる場合は、ライト制御部３４への機能変更が必要となるが、無効なダミーデータをコンパクション先ブロックCmpDstに書き込むようにする場合は、整理部３５から無効なダミーデータをライト制御部３４に渡すようにすれば、ライト制御部３４への機能変更は不要となり、ライト制御部３４は、データの中身を知ることなく書く処理に専念することができる。
【００５３】
また、Ｋページ分連続して無効判定結果が出た場合、無効なダミーデータを書き込むようにしているので、そのデータを再度コンパクションするために読み出した時には、有効無効判定の処理時間が少なくなる。
【００５４】
このように本実施形態では、コンパクション元ブロックでのデータの有効無効判定処理において、Ｋページ分連続して無効判定結果が出た場合、今回の有効無効判定処理を終了し、無効なダミーデータをコンパクション先ブロックCmpDstに書き込むようにしているので、ギア比を守りつつライトコマンドへの応答速度を極端に低下させなくすることが可能となる。別言すれば、本実施形態では、上限値Ｋを設定することで、ライトコマンドへの応答遅延の上限を設定することが可能となり、長時間が経過してもフリーブロックを作成することができないというような状況に陥った場合に、コンパクションが延々と動作し続けることを回避することができる。
【００５５】
なお、上記実施形態では、Ｋページ分連続して無効判定結果が出た場合、コンパクション先ブロックCmpDstへ無効なダミーデータを書き込むようにしているが、コンパクション先ブロックCmpDstへの書き込みを単純にスキップするようにしてもよい。
【００５６】
また、多値記録（ＭＬＣ：Ｍｕｌｔｉ  −Ｌｅｖｅｌ  Ｃｅｌｌ）モードと、二値記録（ＳＬＣ：Ｓｉｎｇｌｅ−Ｌｅｖｅｌ  Ｃｅｌｌ）モードでの記録が可能なＳＳＤにおいて、ＳＬＣモードではＭＬＣモードより高速書き込みが可能であるので、ホストからのデータの書き込みはＳＬＣモードで行い、コンパクション先ブロックへの書き込みはＭＬＣモードで行うようにしてもよい。この方式では、最初にＳＬＣモードのブロックをコンパクション元のブロックとして、コンパクション先のブロックにＭＬＣモードでの書き込みを行うコンパクションを行い、フリーブロックが十分に確保できなかった場合に、次に、ＭＬＣモードのブロックをコンパクション元のブロックとして、コンパクション先のブロックにＭＬＣモードでの書き込みを行うコンパクションを行なう。
【００５７】
また、上記実施形態では、逆引き情報ＧＩは、データの論理アドレス（ＬＢＡ）しか持たないようにしたが、逆引き情報ＧＩに、データの有効無効を示す有効フラグを持たせるようにしてもよい。また、上記実施形態では、逆引き情報ＧＩをデータに付加するようにしたが、逆引き情報を管理するテーブルを用意し、この逆引き管理テーブルを用いて逆引き検索を行うようにしてもよい。また、クラスタサイズをページサイズより小さく定義した場合、ページ内の所定のクラスタ内に、ページ内のクラスタデータの逆引き情報をまとめて記憶させるようにしてもよい。
【００５８】
また、図１０に示すフローチャートでは、簡単化のためにページ単位のデータの書き込み（Ｓ１００、Ｓ１３２，Ｓ１４０）、読み出し（Ｓ１１０）を行っているが、書き込み、読み出しの単位は、ページに限らず、クラスタ単位（ページサイズ≠クラスタサイズ）にしてもよく、さらには他の単位を採用しても良い。
【００５９】
（第２の実施形態）
第２の実施形態においては、ギア比１：Ｎのコンパクションを行う際、コンパクションの処理時間を計測し、コンパクション処理時間が閾値Ｔａ以上になった場合、コンパクション処理を強制的に中断させ、ホスト１からのデータ書き込みを実行させる。このような制御によっても、ライトコマンドへの応答速度を極端に低下させなくすることが可能となる。
【００６０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００６１】
１  ホスト装置、２  ホストインタフェース、１０  ＮＡＮＤ、２０  ＲＡＭ、２１  アドレス変換テーブル、２２  ブロック管理テーブル、２５  ライトバッファ、３０  コントローラ、３１  ブロック管理部、３２  データアクセス部、３３  リード制御部、３４  ライト制御部、３５  整理部。
【図１】
2013200726.tif 000003
【図２】
2013200726.tif 000004
【図３】
2013200726.tif 000005
【図４】
2013200726.tif 000006
【図５】
2013200726.tif 000007
【図６】
2013200726.tif 000008
【図７】
2013200726.tif 000009
【図８】
2013200726.tif 000010
【図９】
2013200726.tif 000011
【図１０】
2013200726.tif 000012
【図１１】
2013200726.tif 000013