(57)【要約】【課題】レイテンシの最大値を従来に比して短くすることができるメモリシステムを提供する。【解決手段】実施形態によれば、メモリシステム１は、外部からのデータが書き込まれる複数のブロックを備える不揮発性メモリ２０と、データ書き込み処理およびコンパクション処理の実行を制御するメモリコントローラ１０と、を備える。不揮発性メモリ２０は、ブロックごとにイレースされる。データ書き込み処理は、外部からの要求にしたがって不揮発性メモリ２０にユーザデータを書き込む。コンパクション処理は、不揮発性メモリ中の第１ブロック中の有効データを第２ブロックに移動させ、第１ブロック中の有効データを無効化する。メモリコントローラ１０は、外部からのデータの書き込み要求を受けると、書き込み要求を受けてから前記外部へ応答を返すまでの間でデータ書き込み処理の前または後に設けられる待ち時間の長さを制御する。【選択図】図１
2018156263.tif 000002
【特許請求の範囲】
【請求項１】
外部からのデータが書き込まれる複数のブロックを備え、前記ブロックごとにイレースされる不揮発性メモリと、
データ書き込み処理およびコンパクション処理の実行を制御するメモリコントローラと、前記データ書き込み処理は、外部からの要求にしたがって前記不揮発性メモリにユーザデータを書き込む、前記コンパクション処理は、前記不揮発性メモリ中の第１ブロック中の有効データを第２ブロックに移動させ、前記第１ブロック中の前記有効データを無効化する、
を備え、
前記メモリコントローラは、前記外部からのデータの書き込み要求を受けると、前記書き込み要求を受けてから前記外部へ応答を返すまでの間で前記データ書き込み処理の前または後に設けられる待ち時間の長さを制御するメモリシステム。
【請求項２】
前記メモリコントローラは、前記書き込み要求を受けると、前記不揮発性メモリ中のフリーブロックの容量である消去可能容量を目標値と比較し、比較の結果に応じて、前記データ書き込み処理が完了した後の前記待ち時間をフィードバック制御する、前記フリーブロックは無効データで構成される、請求項１に記載のメモリシステム。
【請求項３】
前記メモリコントローラは、前記書き込み要求を受けると、前記消去可能容量と前記目標値との差、前記消去可能容量の変化量および前記消去可能容量の積分量に基づいて前記待ち時間を決定する請求項２に記載のメモリシステム。
【請求項４】
前記メモリコントローラは、
前記書き込み要求を受けると、前記待ち時間の決定を行い、
前記データ書き込み処理を行い、
前記データ書き込み処理が完了した後、決定された前記待ち時間の間に前記コンパクション処理を行い、
前記待ち時間が経過した後、前記応答を返す請求項２に記載のメモリシステム。
【請求項５】
前記メモリコントローラは、
前記書き込み要求を受けると、前記待ち時間の決定を行い、
決定された前記待ち時間の間に前記コンパクション処理を行い、
前記待ち時間が経過した後、前記データ書き込み処理を行い、
前記データ書き込み処理が完了した後、前記応答を返す請求項２に記載のメモリシステム。
【請求項６】
前記不揮発性メモリは、ＮＡＮＤ型フラッシュメモリである請求項１に記載のメモリシステム。
【請求項７】
外部からのデータが書き込まれる複数のブロックを備え、前記ブロックごとにイレースされる不揮発性メモリを制御するメモリコントローラであって、
データ書き込み処理およびコンパクション処理の実行を制御し、前記データ書き込み処理は、前記外部からの要求にしたがって前記不揮発性メモリにユーザデータを書き込む、前記コンパクション処理は、前記不揮発性メモリ中の第１ブロック中の有効データを第２ブロックに移動させ、前記第１ブロック中の前記有効データを無効化する、
前記外部からのデータの書き込み要求を受けると、前記書き込み要求を受けてから前記外部へ応答を返すまでの間で前記データ書き込み処理の前または後に設けられる待ち時間の長さを制御するメモリコントローラ。
【請求項８】
前記書き込み要求を受けると、前記不揮発性メモリ中のフリーブロックの容量である消去可能容量を目標値と比較し、比較の結果に応じて、前記データ書き込み処理が完了した後の前記待ち時間をフィードバック制御する、前記フリーブロックは無効データで構成される、請求項７に記載のメモリコントローラ。
【請求項９】
前記書き込み要求を受けると、前記消去可能容量と前記目標値との差、前記消去可能容量の変化量変化量および前記消去可能容量の積分量に基づいて前記待ち時間を決定する請求項８に記載のメモリコントローラ。
【請求項１０】
前記書き込み要求を受けると、前記待ち時間の決定を行い、
前記データ書き込み処理を行い、
前記データ書き込み処理が完了した後、決定された前記待ち時間の間に前記コンパクション処理を行い、
前記待ち時間が経過した後、前記応答を返す請求項８に記載のメモリコントローラ。
【請求項１１】
前記書き込み要求を受けると、前記待ち時間の決定を行い、
決定された前記待ち時間の間に前記コンパクション処理を行い、
前記待ち時間が経過した後、前記データ書き込み処理を行い、
前記データ書き込み処理が完了した後、前記応答を返す請求項８に記載のメモリコントローラ。
【請求項１２】
前記不揮発性メモリは、ＮＡＮＤ型フラッシュメモリである請求項７に記載のメモリコントローラ。
【請求項１３】
外部からのデータの書き込み要求を受けると、不揮発性メモリに前記データを書き込むデータ書き込み処理を完了した後に前記書き込み要求に対する応答を返すまでの待ち時間を決定し、前記不揮発性メモリは、複数のブロックを備え、前記ブロックごとにイレースされる、
前記データ書き込み処理を実行し、
前記応答を外部に返し、
前記書き込み要求を受けた後で前記データ書き込み処理の前または後に、前記待ち時間が設けられるメモリシステムの制御方法。
【請求項１４】
前記待ち時間の決定では、前記不揮発性メモリ中のフリーブロックの容量である消去可能容量を目標値と比較し、比較の結果に応じて、前記データ書き込み処理が完了した後の前記待ち時間をフィードバック制御する、前記フリーブロックは無効データで構成される、請求項１３に記載のメモリシステムの制御方法。
【請求項１５】
前記待ち時間の決定では、前記書き込み要求を受けると、前記消去可能容量と前記目標値との差、前記消去可能容量の変化量および前記消去可能容量の積分量に基づいて前記待ち時間を決定する請求項１４に記載のメモリシステムの制御方法。
【請求項１６】
前記待ち時間の間に、コンパクション処理を行う、前記コンパクション処理は、前記不揮発性メモリ中の第１ブロック中の有効データを第２ブロックに移動させ、前記第１ブロック中の前記有効データを無効化する、請求項１３に記載のメモリシステムの制御方法。
【請求項１７】
前記不揮発性メモリは、ＮＡＮＤ型フラッシュメモリである請求項１３に記載のメモリシステムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、メモリシステム、メモリコントローラおよびメモリシステムの制御方法に関する。
【背景技術】
【０００２】
ＮＡＮＤ型フラッシュメモリ（以下、ＮＡＮＤメモリという）を記憶媒体に用いるメモリシステムでは、コンパクション処理を行って、有効データが書かれていないフリーブロックを用意する必要がある。コンパクション処理では、あるブロック中の有効なデータが、整理されて他のブロックに移動される。このとき、コピー元のブロック中のデータは、無効化される。
【０００３】
ホストからのデータを書き込むデータ書き込み処理とコンパクション処理とは、同じ記憶装置を使用しているため、これらの処理を同時に実行することはできない。そこで、データ書き込み処理とコンパクション処理との書き込み比率を予め計算し、この書き込み比率に基づいて、データ書き込み処理とコンパクション処理とが行われる。データ書き込み処理が行われる場合と、データ書き込み処理の後にコンパクション処理が行われる場合とでは、レイテンシと呼ばれるホストからのデータの書き込み時間にバラつきが生じていた。特に、コンパクション処理が行われるときにレイテンシが最大値となり、コンパクション処理が実行される場合には、データ書き込み処理の完了まで長時間待たされる。このように、従来のデータ書き込み処理では、レイテンシが生じない場合と、レイテンシが生じる場合とで、レイテンシの差が大きくなっていた。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１４−５２８９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の一つの実施形態は、レイテンシの最大値を従来に比して短くすることができるメモリシステム、メモリコントローラおよびメモリシステムの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一つの実施形態によれば、メモリシステムは、外部からのデータが書き込まれる複数のブロックを備える不揮発性メモリと、データ書き込み処理およびコンパクション処理の実行を制御するメモリコントローラと、を備える。前記不揮発性メモリは、前記ブロックごとにイレースされる。前記データ書き込み処理は、外部からの要求にしたがって前記不揮発性メモリにユーザデータを書き込む。前記コンパクション処理は、前記不揮発性メモリ中の第１ブロック中の有効データを第２ブロックに移動させ、前記第１ブロック中の前記有効データを無効化する。前記メモリコントローラは、前記外部からのデータの書き込み要求を受けると、前記書き込み要求を受けてから前記外部へ応答を返すまでの間で前記データ書き込み処理の前または後に設けられる待ち時間の長さを制御する。
【図面の簡単な説明】
【０００７】
【図１】図１は、第１の実施形態によるメモリシステムの構成の一例を示すブロック図である。
【図２】図２は、ＣＰＵがファームウェアに基づいて実現する機能構成部を説明する図である。
【図３】図３は、第１の実施形態によるメモリシステムの制御方法の一例を示すフローチャートである。
【図４】図４は、書き込み処理とコンパクション処理との様子を模式的に示す図である。
【図５】図５は、第２の実施形態によるメモリシステムの構成の一例を示すブロック図である。
【図６】図６は、論理ブロックの構成の一例を示す図である。
【図７】図７は、論理ブロックへ格納されるデータを模式的に示す図である。
【図８】図８は、ルートテーブルの構成の一例を示す図である。
【図９】図９は、第２の実施形態によるＲＡＭの構成の一例を模式的に示す図である。
【図１０−１】図１０−１は、第２の実施形態による管理情報の復元処理の手順の一例を示すフローチャートである（その１）。
【図１０−２】図１０−２は、第２の実施形態による管理情報の復元処理の手順の一例を示すフローチャートである（その２）。
【図１１】図１１は、比較例によるＲＡＭの構成の一例を模式的に示す図である。
【図１２−１】図１２−１は、比較例による管理情報の復元処理の手順の一例を示すフローチャートである（その１）。
【図１２−２】図１２−２は、比較例による管理情報の復元処理の手順の一例を示すフローチャートである（その２）。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態にかかるメモリシステム、メモリコントローラおよびメモリシステムの制御方法を詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００９】
（第１の実施形態）
図１は、第１の実施形態によるメモリシステムの構成の一例を示すブロック図である。メモリシステム１は、通信路３を介して外部のホスト２に接続される。ホスト２は、コンピュータである。コンピュータは、たとえば、パーソナルコンピュータ、ポータブルコンピュータ、または携帯通信機器を含む。メモリシステム１は、ホスト２の外部記憶装置として機能する。通信路３のインタフェース規格としては、任意の規格が採用可能である。ホスト２は、メモリシステム１に対して書き込みコマンドおよび読み出しコマンドを発行することができる。書き込みコマンドおよび読み出しコマンドは、アクセス先を指定する論理的なアドレス情報を含む。なお、特許請求の範囲における外部とは、メモリシステム１内の構成要素間を接続する内部配線ではない通信路３を介して接続されるホスト２などのコンピュータである。
【００１０】
メモリシステム１は、メモリコントローラ１０と、ストレージとして用いられるＮＡＮＤメモリ２０と、ＲＡＭ（Random  Access  Memory）３０と、を備える。
【００１１】
ＮＡＮＤメモリ２０は、メモリセルアレイを有する１以上のＮＡＮＤチップによって構成される。メモリセルアレイは、複数のメモリセルがマトリクス状に配列されて構成される。個々のメモリセルアレイは、イレースの単位である物理ブロックを複数配列して構成される。各物理ブロックは、メモリセルアレイに対する読み出しおよび書き込みの単位であるページを複数備える。
【００１２】
ＮＡＮＤメモリ２０においては、物理ブロック単位でイレースされる。したがって、ＮＡＮＤメモリ２０に第１データが格納されている状態でホスト２から第１データと同一の論理アドレスを指定して第２データが書き込まれるとき、第１データがイレースされるのではなく、空のページに第２データが書き込まれるとともに第１データは無効なデータ（以下、無効データという）とされる。このような手法でＮＡＮＤメモリ２０に対する書き込みが行われるため、各物理ブロックに格納されているデータには、無効データと有効なデータ（以下、有効データという）とが混在する。データが有効とは、そのデータが最新の状態であることをいう。同一の論理アドレスが指定されて書き込まれた複数のデータがＮＡＮＤメモリ２０に格納される場合があり、最新の状態とは、その複数のデータのうちのホスト２が最後に書き込んだデータの状態をいう。すなわち、有効データは、ある論理アドレスに対して最新の状態にあるデータのことをいう。データが無効とは、追記によってそのデータが最新でなくなった状態であることをいい、前記複数のデータのうちの、ホスト２が最後に書き込んだデータ以外のデータの状態をいう。なお、１回しか指定されていない論理アドレスがある場合には、その論理アドレスを指定して書き込まれたデータは最新の状態である。なお、物理ブロック中のデータが有効データであるのか無効データであるのかについては、ビットマップまたはフラグを用いて管理してもよいし、あるいはデータをＮＡＮＤメモリ２０に書き込むときに付加されるログに書き込んでもよい。
【００１３】
ＮＡＮＤメモリ２０には、ユーザデータと、管理情報と、が格納される。ユーザデータは、ホスト２からの指示によって書き込まれるデータである。管理情報は、メモリコントローラ１０がＮＡＮＤメモリ２０に対するアクセスを行うための情報であり、翻訳情報およびフリーブロック情報などを含む。翻訳情報は、論理アドレスを物理アドレスに翻訳するための情報である。ある論理アドレスに対してＮＡＮＤメモリ２０の第１物理アドレスに第１データが書き込まれている状態で、同一の論理アドレスが指定されて第２データがＮＡＮＤメモリ２０の第２物理アドレスに書き込みされる場合を考える。このとき、最初の状態の翻訳情報は、ある論理アドレスと第１物理アドレスとが対応付けられている。しかし、第２データの書き込みがされた後には、翻訳情報は、ある論理アドレスと第２物理アドレスとが対応付けられることになる。このように、第１物理アドレスは、翻訳情報で、論理アドレスと対応付けされなくなってしまう。つまり、無効化とは、翻訳情報に含まれる物理アドレスが論理アドレスと対応付けされなくなってしまう状態をいう。フリーブロック情報は、有効データが含まれていないブロックのブロック番号を含む。フリーブロック情報は、たとえばフリーブロックであるブロック番号をリスト形式で表したものである。
【００１４】
ＲＡＭ３０は、管理情報を記憶する。メモリシステム１の起動時においては、ＲＡＭ３０には、ＮＡＮＤメモリ２０から読み出すことができる最新の管理情報が記憶される。ＮＡＮＤメモリ２０へのユーザデータの書き込み、消去、またはコンパクション処理によって、ＲＡＭ３０上の管理情報がメモリコントローラ１０によって更新される。更新された管理情報は、任意のタイミングで、ＮＡＮＤメモリ２０へと保存される。第１の実施形態では、管理情報は、翻訳情報とフリーブロック情報とを含む。また、ＲＡＭ３０は、ホスト２とＮＡＮＤメモリ２０との間のデータ転送のためのバッファとしてメモリコントローラ１０によって使用される。
【００１５】
メモリコントローラ１０は、ＣＰＵ１１ａ〜１１ｃ、ホストＩ／Ｆ１２、ＲＡＭコントローラ１３およびＮＡＮＤコントローラ１４を備える。ＣＰＵ１１ａ〜１１ｃ、ホストＩ／Ｆ１２、ＲＡＭコントローラ１３およびＮＡＮＤコントローラ１４は、バス１５で互いに接続されている。
【００１６】
ホストＩ／Ｆ１２は、通信路３の制御を実行する。また、ホストＩ／Ｆ１２は、ホスト２からのコマンドを受け付ける。さらに、ホストＩ／Ｆ１２は、ホスト２とＲＡＭ３０との間のデータ転送を実行する。
【００１７】
ＲＡＭコントローラ１３は、メモリコントローラ１０がＲＡＭ３０にアクセスするためのコントローラである。
【００１８】
ＮＡＮＤコントローラ１４は、ＣＰＵ１１ａ、ＣＰＵ１１ｂから受信したコマンドをＮＡＮＤメモリ２０へ送信する。また、ＮＡＮＤコントローラ１４は、ＲＡＭ３０とＮＡＮＤメモリ２０との間のデータ転送を実行する。
【００１９】
ＣＰＵ１１ａは、ファームウェアプログラムを実行することによって、メモリコントローラ１０全体の制御を実行する。ＣＰＵ１１ａは、制御の一環として、ホストＩ／Ｆ１２がホスト２から受け付けたコマンドに応じて、ＮＡＮＤメモリ２０に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する。また、コマンドの実行完了後に、コマンドの実行が完了したことを示す応答をホストＩ／Ｆ１２を介してホスト２に送信する。
【００２０】
ＣＰＵ１１ｂは、ファームウェアプログラムを実行することによって、メモリコントローラ１０のコンパクション処理に関する制御を実行する。ＣＰＵ１１ｂは、メモリシステム１のコンパクション処理に応じて、ＮＡＮＤメモリ２０に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する。コンパクション処理は、フリーブロックを生成するための処理である。フリーブロックは、有効データが１つもない状態のブロック、すなわち、無効データで満たされる状態のブロックである。たとえば、コンパクションは、書き込み済みの１以上のブロックから有効データを集めて、集めた有効データを他のブロックに移動する処理である。このようにデータの使用領域を集めて別ブロックに移す処理を行うことで、フリーブロックが生成される。
【００２１】
ＣＰＵ１１ｃは、ファームウェアプログラムを実行することによって、メモリコントローラ１０の書き込み許可速度の制御を実行する。ＣＰＵ１１ｃは、ホスト２から書き込みコマンドを受信すると、書き込みコマンドに対応するデータ書き込み処理が完了した後に、ホストへの応答を返すまでの待ち時間を制御する。具体的には、ＣＰＵ１１ｃは、ホスト２から書き込みコマンドを受信すると、ＮＡＮＤメモリ２０の消去可能容量と目標値とを比較し、比較の結果に基づいて、データ書き込み処理が完了した後にホスト２への応答を返すまでの待ち時間をフィードバック制御する。フィードバック制御は、ＰＩＤ（Proportional-Integral-Derivative）制御を含む。たとえば、ＣＰＵ１１ｃは、消去可能容量と、消去可能容量の変化量と、消去可能容量の積分量と、に基づいて、待ち時間を決定する。
【００２２】
ＣＰＵ１１ｃは、現在の消去可能容量が目標値よりも増えた場合には、待ち時間を短くし、現在の消去可能容量が目標値よりも減った場合には、待ち時間を増やす。現在の消去可能容量は、フリーブロックの総数であり、フリーブロック情報に登録されているフリーブロックの数を数えることで求めることができる。また、現在の消去可能容量は、フリーブロックの総数でもよいし、フリーブロックに含まれるページ総数でもよい。目標値は、ＮＡＮＤメモリ２０中のすべての物理ブロックを使い尽くすことなく、コンパクション処理を効率的に行うことができる消去可能容量である。目標値は、実際のメモリシステム１の平均的な使用状況を想定して、たとえば計算によって求められる。
【００２３】
なお、ここでは、ＣＰＵ１１ｃは、待ち時間を算出しているが、書き込み許可速度でもよい。ホスト２からの書き込みコマンドによるデータ書き込み処理は、データのサイズが一定であるので、一定の時間（書き込み時間）で完了する。そのため、一定のデータサイズと、一定の書き込み時間およびＣＰＵ１１ｃによって算出される待ち時間と、を用いることで書き込み許可速度を算出することができる。待ち時間を短くすることは書き込み許可速度を増やすことに対応し、待ち時間を長くすることは書き込み許可速度を減らすことに対応する。このように、第１の実施形態では、ホスト２からのコマンドを受信する度に、待ち時間が決定されるので、書き込み許可速度をより細かく制御することが可能となる。
【００２４】
ＣＰＵ１１ａは、データ書き込み処理が終了すると、通知された待ち時間だけ待機し、待ち時間が経過すると、応答をホスト２に返す。待ち時間の間は、ホスト２からコマンドを受信しないので、ＣＰＵ１１ａからＮＡＮＤコントローラ１４に対して送信されるコマンドは存在しない。その結果、待ち時間の間は、ＣＰＵ１１ｂがコンパクション処理に関するコマンドをＮＡＮＤコントローラ１４に送信し、ＮＡＮＤコントローラ１４は、コンパクション処理を実行することになる。
【００２５】
図２は、ＣＰＵがファームウェアに基づいて実現する機能構成部を説明する図である。なお、ここでは、本実施形態と関連する処理部について説明する。ＣＰＵ１１ａは、データ制御部１１１と、アドレス制御部１１２と、を備える。データ制御部１１１は、ホスト２からのアクセスコマンドに応じて、当該アクセスコマンドの送信元のホスト２とＮＡＮＤメモリ２０との間のユーザデータの転送を実行する。このとき、アクセスコマンドに含まれるアドレス情報と、ＮＡＮＤメモリ２０上の物理的なデータアドレスと、の間の翻訳情報をアドレス制御部１１２から受け取って、ユーザデータの転送を実行する。また、データ制御部１１１は、アクセスコマンドで指示される処理が完了すると、応答をホスト２へと送信する。本実施形態では、データ制御部１１１は、アクセスコマンドが書き込みコマンドである場合に、データ書き込み処理の後に、ＣＰＵ１１ｃの待ち時間制御部１１５で決定された待ち時間だけ待機した後、応答をホスト２へと送信する。アドレス制御部１１２は、アクセスコマンドに含まれるアドレス情報を、ＮＡＮＤメモリ２０上の物理的なデータアドレスへと翻訳し、翻訳結果をデータ制御部１１１に渡す。また、アドレス制御部１１２は、翻訳情報を更新する。
【００２６】
ＣＰＵ１１ｂは、コンパクション制御部１１３と、アドレス制御部１１４と、を備える。コンパクション制御部１１３は、コンパクション処理の対象のブロックから移動させるユーザデータを選択し、選択したユーザデータを移動先のブロックに移動させるコンパクション処理の実行を制御する。アドレス制御部１１４は、コンパクション処理によって、変更が必要となる管理情報の更新を行う。この管理情報の更新には、コンパクション処理の対象のブロックに記憶されていたユーザデータを無効化する処理、コンパクション処理によって移動されたユーザデータの論理アドレスと物理アドレスとの間の新たな翻訳結果を翻訳情報に登録する処理、およびコンパクション処理によってすべて無効データとなったブロックをフリーブロック情報に登録する処理が含まれる。
【００２７】
ＣＰＵ１１ｃは、待ち時間制御部１１５を備える。待ち時間制御部１１５は、ホスト２から書き込みコマンドを受信すると、消去可能容量あるいはこれに加えて消去可能容量の変化量または消去可能容量の積分量とに基づいて、待ち時間を決定し、ＣＰＵ１１ａに通知する。消去可能容量は、上記したようにフリーブロック情報に登録されているフリーブロックの数（あるいは、フリーブロックの数に１ブロック当たりの記憶容量を乗算したもの）から求めることができる。これによって、ＣＰＵ１１ａにおけるホスト２からの書き込み許可速度が制御される。
【００２８】
つぎに、メモリシステム１の制御方法について説明する。図３は、第１の実施形態によるメモリシステムの制御方法の一例を示すフローチャートである。まず、メモリシステム１のホストＩ／Ｆ１２は、ホスト２からユーザデータの書き込みコマンドを受信する（ステップＳ１１）。ＣＰＵ１１ｃは、フリーブロック情報からその時点での消去可能容量を取得し（ステップＳ１２）、目標値と比較して待ち時間を決定する（ステップＳ１３）。たとえば、ＣＰＵ１１ｃは、消去可能容量が目標値よりも増えた場合には、所定の待ち時間よりも減らし、消去可能容量が目標値よりも減った場合には、所定の待ち時間よりも増やし、消去可能容量が目標値と同じである場合には、所定の待ち時間とする。ＣＰＵ１１ｃは、決定した待ち時間をＣＰＵ１１ａに通知する。
【００２９】
ＣＰＵ１１ａは、待ち時間が通知されると、書き込みコマンドにしたがってユーザデータを書き込むようにＮＡＮＤコントローラ１４に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する（ステップＳ１４）。
【００３０】
ＮＡＮＤコントローラ１４は、コマンドにしたがって、ユーザデータの書き込み処理を実行する（ステップＳ１５）。ユーザデータの書き込み処理が終了した後、ＣＰＵ１１ａは、計時を開始し（ステップＳ１６）、待ち時間が経過したかを判定する（ステップＳ１７）。
【００３１】
ＣＰＵ１１ａが待ちの状態にある間、ＣＰＵ１１ｂは、コンパクション処理に関するコマンドをＮＡＮＤコントローラ１４に送信することができる。つまり、待ち時間が経過していない場合（ステップＳ１７でＮｏの場合）には、ＣＰＵ１１ｂは、コンパクション処理を実行するようにＮＡＮＤコントローラ１４に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する（ステップＳ１８）。ここでは、ＣＰＵ１１ｂは、移動元のブロック内の有効なユーザデータを、移動先のブロック内に書き込むようにＮＡＮＤコントローラ１４に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する。また、ＣＰＵ１１ｂは、このユーザデータの移動に伴う翻訳情報の変更を行い、また、移動元のブロックに有効なユーザデータがなくなった場合には、移動元のブロックのフリーブロック情報への登録を行う。ＮＡＮＤコントローラ１４は、コマンドにしたがって、コンパクション処理を実行する（ステップＳ１９）。
【００３２】
その後、ＣＰＵ１１ａは、待ち時間が経過したかを判定する（ステップＳ２０）。待ち時間が経過していない場合（ステップＳ２０でＮｏの場合）には、ステップＳ１８へと処理が戻る。また、ステップＳ１７またはステップＳ２０で待ち時間が経過した場合（ステップＳ１７またはステップＳ２０でＹｅｓの場合）には、ＣＰＵ１１ａは、書き込みコマンドに対する応答を生成し、ホストＩ／Ｆ１２を介してホスト２に送信する（ステップＳ２１）。以上によって、処理が終了する。
【００３３】
つぎに、比較例と比較した本実施形態の効果について説明する。図４は、書き込み処理とコンパクション処理との様子を模式的に示す図であり、（ａ）は比較例による処理の様子を示し、（ｂ）は第１の実施形態による処理の様子を示す。これらの図で、横軸は時間である。
【００３４】
比較例では、ホストからのデータ書き込み処理とコンパクション処理との書き込み比率（書き込み許可容量）を予め計算して計画して書き込みを行う。たとえば、ある大きさのユーザデータの書き込みを行う場合には、メモリシステムで予め定められた大きさに分割された各ユーザデータについて、書き込みコマンドがホストから出される。このとき、図４（ａ）に示されるように、ＣＰＵ１１ａは送られてくる書き込みコマンドに対応してＮＡＮＤメモリに分割されたユーザデータを書き込み、書き込みが完了するとホストに応答を返す。ＣＰＵ１１ａは、この処理を繰り返す。その後、ユーザデータの書き込み量が予め定められた書き込み許可容量に達すると、ＣＰＵ１１ｂは、コンパクション処理を実行する。そして、コンパクション処理が終了すると、ＣＰＵ１１ａは、ホストに書き込みコマンドに対する応答を返す。
【００３５】
ここで、分割されたユーザデータ１〜（ｎ−１）（ｎは２以上の整数）までは、データ書き込み処理が完了すると、応答を返し、待ち時間を設けずにつぎのデータ書き込み処理を実行している。しかし、ユーザデータｎになると、データ書き込み処理の後にコンパクション処理が行われる結果、Δｔ１１の時間をおいて、応答を返すことになる。書き込み時間をｔ０とすると、ユーザデータ１〜（ｎ−１）の書き込み時のレイテンシは、略ｔ０であるが、ユーザデータｎの書き込み時のレイテンシは、ｔ０＋Δｔ１１となる。つまり、レイテンシにΔｔ１１のバラつきが生じてしまう。また、コンパクション処理が行われる場合のレイテンシが非常に大きくなってしまう。
【００３６】
一方、第１の実施形態では、図４（ｂ）に示されるように、ＣＰＵ１１ｃは、書き込みコマンドが送られてくると、消去可能容量と目標値とを比較し、その差に基づいて、あるいは、これに加えて消去可能容量の変化量または消去可能容量の積分量に基づいて、待ち時間を決定し、決定した待ち時間で書き込み処理をフィードバック制御する。ついで、ＣＰＵ１１ａは、送られてくる書き込みコマンドに対応してＮＡＮＤメモリ２０に分割されたユーザデータを書き込むコマンドをＮＡＮＤコントローラ１４に送信し、書き込みが完了すると、決定された待ち時間だけ待つ。なお、ここでの書き込みの単位は、制御可能な最小単位である。ＣＰＵ１１ｂは、この待ち時間を用いて、コンパクション処理を実行するコマンドをＮＡＮＤコントローラ１４に送信し、コンパクション処理が実行される。ついで、待ち時間が経過すると、ＣＰＵ１１ａは、ホスト２に応答を返す。ＣＰＵ１１ａ〜１１ｃは、この処理を繰り返して実行する。なお、各処理で決定される待ち時間は、その時の消去可能容量およびその変化量によって変化する。
【００３７】
図４（ｂ）では、ユーザデータ１，２，３，・・・，ｎの待ち時間をそれぞれΔｔ１，Δｔ２，Δｔ３，・・・，Δｔｎとする。各ユーザデータ１〜ｎの書き込み処理に要する時間はｔ０で一定である。その結果、ユーザデータ１，２，３，・・・，ｎを書き込むときのレイテンシは、それぞれｔ０＋Δｔ１，ｔ０＋Δｔ２，ｔ０＋Δｔ３，・・・，ｔ０＋Δｔｎとなる。また、各書き込み処理での待ち時間Δｔ１〜Δｔｎの和は、図４（ａ）のコンパクション処理の時間ｔ１１と略同じである。
【００３８】
比較例では、定められたデータ書き込み処理とコンパクション処理との書き込み比率にしたがって、コンパクション処理が行われるので、コンパクション処理が行われるときに発行された書き込みコマンドのレイテンシが大きくなってしまう。一方、第１の実施形態では、データ書き込み処理の後に待ち時間を設けて、この待ち時間でコンパクション処理を行うようにした。つまり、比較例では１回で行っていたコンパクション処理を、第１の実施形態では複数回にわたって行うようにした。これによって、比較例に比してコンパクション処理が分散されるので、比較例の場合に比してレイテンシの最大値を小さくすることができる。また、レイテンシのバラつきを、比較例の場合に比して抑制することができる。
【００３９】
なお、図４では、ユーザデータの書き込み処理について説明を行ったが、書き込み処理に代えて、データ転送時間を用いてもよい。また、上記した説明では、書き込み処理の後に待ち時間が設けられる場合を説明したが、書き込み処理の前に待ち時間が設けられてもよい。
【００４０】
第１の実施形態では、書き込みコマンドを受信すると、消去可能容量またはこれに加えて消去可能容量の変化量、消去可能容量の積分量に基づいて、ホスト２から書き込みコマンドを受けたときの書き込み許可速度をフィードバック制御した。つまり、データ書き込み処理の後に設けられる待ち時間を用いてコンパクション処理を実行するようにした。これによって、比較例に比して、書き込みのレイテンシの最大値を小さくすることができるという効果を有する。また、書き込みコマンドごとのレイテンシのバラつきを抑えることができるという効果を有する。
【００４１】
（第２の実施形態）
メモリシステムでは、ＮＡＮＤメモリのイレースの最小単位となる物理ブロック（メモリセルのアレイ）を複数まとめた論理ブロックという仮想的なブロックを構築し、構築した論理ブロックをイレース、書き込み、読み出しなどの管理単位として用いる場合がある。また、ＮＡＮＤメモリにデータを書き込む場合に、データ部と訂正符号からなるフレームと呼ばれる単位で論理ブロックの先頭のページから順に書き込む。このとき、フレーム内のページを、すべて論理ブロックを構成する各物理ブロックのページで構成することで書き込みの並列化（高速化）を行うことができる。
【００４２】
フレームには、データ部が固定長である固定長フレームと、データ部が可変長である可変長フレームと、がある。固定長フレームは、論理ページと同じサイズである。論理ブロックにデータを書き込む場合、固定長フレームのサイズで書き込むことを基本としつつ、データのサイズが固定長フレームのサイズに満たない場合に可変長フレームで書き込むという組み合わせ方式が提案されている。
【００４３】
ところで、メモリシステムでは、電源オフ前に、ＲＡＭに記憶されている翻訳情報などの管理情報をＮＡＮＤメモリに保存し、起動時に、ＮＡＮＤメモリに保存された管理情報を復元する。正規の手順で電源オフを行った場合だけでなく、不正な電源オフを行った場合であっても、管理情報を整合性のとれた状態に戻すこと、および可能な限り最新のデータが読み出せる状態に復元することが、メモリシステムには求められる。
【００４４】
管理情報を可変長フレームでＮＡＮＤメモリに書き込む場合には、メモリシステムの起動時に管理情報が書き込まれたフレームを特定する処理に時間を要してしまう。特に、不正な電源オフが行われた場合には、書き込みが中途半端なページなどが存在することもあり、管理情報の復元に多くの時間が費やされてしまう。
【００４５】
そこで、第２の実施形態では、フレーム内のデータを並列でＮＡＮＤメモリを構成する物理ブロックに書き込む場合で、かつ可変長フレームでＮＡＮＤメモリに書き込みを行うことができる場合に、メモリシステムの起動時において、整合性のとれた最新の管理情報を特定することができるメモリシステム、メモリコントローラおよびメモリシステムの制御方法について説明する。
【００４６】
図５は、第２の実施形態によるメモリシステムの構成の一例を示すブロック図である。メモリシステム１Ａは、メモリコントローラ１０と、ＮＡＮＤメモリ２０と、ＲＡＭ３０と、を備える。
【００４７】
ＮＡＮＤメモリ２０は、複数のＮＡＮＤチップ２１によって構成される。各ＮＡＮＤチップ２１は、データの消去の単位である物理ブロックを複数配列して構成される。ここでは、異なるＮＡＮＤチップ２１から１つずつ物理ブロックを集めて、仮想的なブロックである論理ブロックを構成する。図６は、論理ブロックの構成の一例を示す図である。ここでは、８つの物理ブロック２１０から１つの論理ブロック２００が構成される。それぞれの物理ブロック２１０は、異なるＮＡＮＤチップ２１に属する。１つの論理ブロック２００が８つの物理ブロック２１０で構成される場合、１つの論理ページ２２０は、８つの物理ページ２３０で構成される。なお、各ＮＡＮＤチップ２１とメモリコントローラ１０との間は、それぞれ異なる信号線２２で接続されており、各ＮＡＮＤチップ２１に独立してアクセスすることができる。
【００４８】
ＮＡＮＤメモリ２０は、第１の実施形態で説明したように、ユーザデータと、管理情報と、を格納する。ユーザデータと管理情報とは、論理ブロックに書き込みが行われる。論理ブロックへのデータの格納のされ方について説明する。なお、ここでは、格納されるデータとして、管理情報を例に挙げる。
【００４９】
図７は、論理ブロックへ格納されるデータを模式的に示す図である。上記したように、１つの論理ブロック２００は、８個の物理ブロック２１０から構成され、１つの論理ページは、８個の物理ページからなるものとする。また、ここでは、パリティ（訂正符号）は２物理ページ分のサイズを有するものとする。論理ブロック２００には、１論理ページ分のサイズ（すなわち、８物理ページ分）を有する固定長フレーム２５１と、１論理ページ分のサイズに満たない（すなわち、７物理ページ以下のサイズの）可変長フレーム２６１〜２６３と、を書き込むことが可能である。固定長フレーム２５１は、６物理ページ分のデータ部Ｄ１と、２物理ページ分のパリティＰ１と、を含む。可変長フレーム２６１〜２６３は、７物理ページ以下のデータ部Ｄ２，Ｄ３，Ｄ４と、２物理ページ分のパリティＰ２，Ｐ２３，Ｐ４と、を含む。
【００５０】
ここで、可変長フレームにおけるパリティについて説明する。図７に示されるように、固定長フレーム２５１のパリティＰ１は、６物理ページ分のデータ部Ｄ１に対して生成されたものである。一方、可変長フレーム２６１〜２６３は、フレームの長さが可変のものである。たとえば論理ページの先頭から保存される可変長フレーム２６１は、データ部Ｄ２とパリティＰ２とを有する。パリティＰ２は、データ部Ｄ２に対して生成されたものである。可変長フレーム２６１のつぎに格納される可変長フレーム２６２は、データ部Ｄ３とパリティＰ２３とを有する。パリティＰ２３は、データ部Ｄ３に対して生成されたものではなく、可変長フレーム２６２が格納される論理ページの先頭からパリティＰ２３の直前までのデータ、すなわちデータ部Ｄ２、パリティＰ２およびデータ部Ｄ３に対して生成されたものである。
【００５１】
固定長フレーム２５１および可変長フレーム２６１〜２６３のデータ部Ｄ１〜Ｄ４は、更新管理情報２７１と、管理情報の格納位置を示すルートテーブル２７２と、を含む。更新管理情報２７１は、管理情報のすべてではなく、管理情報の一部のデータである。更新管理情報２７１は、たとえば管理情報中の更新された内容を含む。
【００５２】
図８は、ルートテーブルの構成の一例を示す図である。ルートテーブル２７２は、メモリシステム１Ａで使用される管理情報のＮＡＮＤメモリ２０上での格納位置を示すテーブル位置情報２７２１と、ルートテーブル２７２であることを示すシグニチャ２７２２と、ルートテーブル２７２のＮＡＮＤメモリ２０上での格納位置であるルートテーブル位置２７２３と、を含む。テーブル位置情報２７２１は、固定長フレーム２５１または可変長フレーム２６１〜２６３に含まれる更新管理情報２７１の格納位置のほかに、今回の更新管理情報の保存の際に更新されなかった管理情報の他の部分のデータのＮＡＮＤメモリ２０上での格納位置を含む。シグニチャ２７２２は、後述する復元処理の際に、可変長フレーム２６１〜２６３が正しく復元されたかを確認するために用いられる。シグニチャ２７２２は、たとえばルートテーブルであることを示すキャラクタ列である。また、ルートテーブル位置２７２３は、後述する復元処理の際に、このルートテーブル位置２７２３に対応する位置にルートテーブル２７２が格納されているかを確認し、可変長フレーム２６１〜２６３が正しく復元されたかを確認するために用いられる。
【００５３】
なお、上記では、複数のＮＡＮＤチップ２１をメモリコントローラ１０に対してそれぞれ独立した信号線２２で接続することによって、並列処理が可能なように構成した。この他にも、各ＮＡＮＤチップ２１に複数のプレーンを設けて、並列処理が可能なように構成してもよい。各ＮＡＮＤチップ２１内に設けられるプレーンは、互いに独立した周辺回路（たとえば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュ等）を備えており、同時に消去／ライト／リードを行うことができる。
【００５４】
ＲＡＭ３０は、第１の実施形態で説明した機能を有するが、第２の実施形態では、メモリシステム１Ａの起動時に、管理情報を復元する情報をさらに記憶する。図９は、第２の実施形態によるＲＡＭの構成の一例を模式的に示す図である。ＲＡＭ３０は、第１フレーム記憶領域３１と、第２フレーム記憶領域３２と、管理情報記憶領域３３と、を有する。
【００５５】
第１フレーム記憶領域３１は、起動時にＮＡＮＤメモリ２０から読み出された前回の電源オフ時に保存された更新管理情報を含む復元対象フレームを記憶する。第２フレーム記憶領域３２は、第１フレーム記憶領域３１に記憶された復元対象フレームのコピーを記憶する。後述する誤り訂正処理では、メモリコントローラ１０（ＥＣＣユニット１６）は、第２フレーム記憶領域３２中の復元対象フレームに対して誤り訂正処理を行う。以下では、第１フレーム記憶領域３１に記憶された復元対象フレームと第２フレーム記憶領域３２に記憶された復元対象フレームとを区別する場合に、第１フレーム記憶領域３１に記憶された復元対象フレームを親復元対象フレームといい、第２フレーム記憶領域３２に記憶された復元対象フレームを娘復元対象フレームという。管理情報記憶領域３３は、第２フレーム記憶領域３２の娘復元対象フレームを正常に読み出せた場合あるいは娘復元対象フレームの誤り訂正が成功した場合に、娘復元対象フレーム中のルートテーブル２７２にしたがって読み出した管理情報を記憶する。
【００５６】
なお、１つのＲＡＭ３０中に第１フレーム記憶領域３１および第２フレーム記憶領域３２を設けてもよいし、第１フレーム記憶領域３１と第２フレーム記憶領域３２とを異なる複数のＲＡＭ３０（チップ）で構成してもよい。
【００５７】
メモリコントローラ１０は、ＣＰＵ１１、ホストＩ／Ｆ１２、ＲＡＭコントローラ１３、ＮＡＮＤコントローラ１４およびＥＣＣユニット１６を備える。ＣＰＵ１１、ホストＩ／Ｆ１２、ＲＡＭコントローラ１３、ＮＡＮＤコントローラ１４およびＥＣＣユニット１６は、バス１５で互いに接続されている。
【００５８】
ＣＰＵ１１は、ファームウェアプログラムを実行することによってメモリコントローラ１０全体の制御を実行する。ＣＰＵ１１は、たとえばホストＩ／Ｆ１２がホスト２から受け付けたコマンドに応じて、ＮＡＮＤメモリ２０に対するコマンドを生成し、ＮＡＮＤコントローラ１４に送信する。
【００５９】
ＥＣＣユニット１６は、ＮＡＮＤメモリ２０に書き込むデータに対して誤り訂正の符号化処理を実施し、パリティを生成する。ＥＣＣユニット１６は、データおよびパリティを含む符号語をＮＡＮＤコントローラ１４に出力する。また、ＥＣＣユニット１６は、ＮＡＮＤメモリ２０から読み出された符号語を用いて誤り訂正の復号化処理を実行し、復号されたデータをＲＡＭ３０に転送する。ＥＣＣユニット１６の誤り訂正能力には上限があり、この上限を超えるビット誤りが発生している場合には、誤り訂正に失敗する。
【００６０】
また、第２の実施形態では、ＣＰＵ１１は、メモリシステム１Ａの起動時に、ＮＡＮＤメモリ２０中の論理ブロックから管理情報を読み出し、管理情報を復元する。このとき、ＣＰＵ１１は、論理ブロック中の最終書き込みページを特定し、最終書き込みページが含まれる論理ページの先頭から最終書き込みページまでの復元対象フレームをＮＡＮＤメモリ２０からＲＡＭ３０の第１フレーム記憶領域３１に読み出す。これによって、第１フレーム記憶領域３１には、親復元対象フレームが記憶される。また、ＣＰＵ１１は、第１フレーム記憶領域３１に記憶された親復元対象フレームを、ＲＡＭ３０の第２フレーム記憶領域３２にコピーする。これによって、第２フレーム記憶領域３２には、娘復元対象フレームが記憶される。
【００６１】
ＥＣＣユニット１６は、第２フレーム記憶領域３２にコピーされた娘復元対象フレームについて、パリティを用いて訂正処理を行い、復元フレームを生成する。
【００６２】
ＣＰＵ１１は、復元フレームから、ルートテーブル２７２を読み出し、ルートテーブル２７２の内容を用いて復元フレームが正しいかをチェックする。復元フレームが正しい場合には、ルートテーブル２７２の内容にしたがって、管理情報をＲＡＭ３０の管理情報記憶領域３３に復元する。一方、復元フレームが正しくない場合には、ＣＰＵ１１は、第２フレーム記憶領域３２の復元フレームを破棄し、第１フレーム記憶領域３１の親復元対象フレームを第２フレーム記憶領域３２にコピーする。ＣＰＵ１１は、娘復元対象フレームの終端ページの位置を、前回仮定したときの位置よりも所定の長さだけ前方に移動する。そして、ＣＰＵ１１とＥＣＣユニット１６とは、上記で説明した処理を行って、終端ページを変更した娘復元対象フレームについて、復元フレームを正しく生成できたかを判定する。
【００６３】
なお、第１の実施形態で説明したものと同一の構成要素には、同一の符号を付してその説明を省略している。
【００６４】
つぎに、管理情報の復元処理について詳細に説明する。図１０−１と図１０−２は、第２の実施形態による管理情報の復元処理の手順の一例を示すフローチャートである。メモリシステム１Ａの電源がオンにされると、ＣＰＵ１１は、ＮＡＮＤメモリ２０中の論理ブロックについて、イレースページ検索を行い、最終書き込みページを特定する（ステップＳ３１）。イレースページ検索は、論理ブロックの最終ページから先頭ページに向かって順にイレースページであるかの問い合わせを行い、イレースページでないページが最初に検出されると、この位置を最終書き込みページとする検索手法である。なお、ＮＡＮＤメモリ２０では、論理ブロックに書き込みを行う際に、先頭ページから昇順に書き込む。
【００６５】
ＣＰＵ１１は、特定した最終書き込みページを、論理ページに書き込まれた可変長フレームの終端ページであると仮定する（ステップＳ３２）。ついで、ＣＰＵ１１は、仮定した可変長フレームからパリティ（訂正符号部分）を減算した位置をルートテーブルとみなす（ステップＳ３３）。上記したように、この例ではパリティは２物理ページ分あるので、仮定した可変長フレームから２物理ページ分減算した位置にルートテーブルが存在するものとみなす。
【００６６】
その後、ＣＰＵ１１は、ＮＡＮＤメモリ２０中の最終書き込みページを含む論理ページの先端から仮定した可変長フレームの終端までを親復元対象フレームとして並列でＲＡＭ３０の第１フレーム記憶領域３１に読み出す（ステップＳ３４）。すなわち、論理ページを構成する複数の物理ページについて、独立して並列に読み出しを行う。
【００６７】
ついで、ＣＰＵ１１は、読み出された親復元対象フレームのルートテーブル２７２を読み出し（ステップＳ３５）、正常に読み出せたかを判定する（ステップＳ３６）。すなわち、ステップＳ３３で仮定したルートテーブル２７２を読み出し、ルートテーブル２７２中のシグニチャ２７２２を正常に読み出すことができ、かつ、ルートテーブル位置２７２３で示される位置にルートテーブル２７２が格納されている場合に、正常に読み出せたものと判定する。また、ルートテーブル２７２中のシグニチャ２７２２が正常に読み出せなかった場合、またはルートテーブル位置２７２３で示される位置にルートテーブル２７２が格納されていなかった場合には、正常に読み出せなかったと判定する。
【００６８】
ＣＰＵ１１は、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ３６でＮｏの場合）には、第１フレーム記憶領域３１中の親復元対象フレームを、娘復元対象フレームとして第２フレーム記憶領域３２にコピーする（ステップＳ３７）。ついで、ＥＣＣユニット１６は、第２フレーム記憶領域３２の娘復元対象フレームに対して訂正処理を行い、復元フレームを生成する（ステップＳ３８）。すなわち、ＥＣＣユニット１６は、仮定した終端から２ページ分のデータをパリティとして、このパリティを用いて、訂正処理を行う。これによって、復元対象フレームは訂正が施され、復元フレームとなる。
【００６９】
その後、ＣＰＵ１１は、復元フレームのルートテーブル２７２を読み出し（ステップＳ３９）、正常に読み出せたかを判定する（ステップＳ４０）。ここでの判定は、ステップＳ３６で説明したものと同様である。判定の結果、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ４０でＮｏの場合）には、ＣＰＵ１１は、第２フレーム記憶領域３２に記憶されている復元フレームを消去する（ステップＳ４１）。
【００７０】
ＣＰＵ１１は、ステップＳ３２での可変長フレームの終端ページの仮定に誤りがあったものとみなし、第１フレーム記憶領域３１の親復元対象フレームで前回仮定された終端ページから１つ前のページを可変長フレームの終端ページと仮定し直す（ステップＳ４２）。ついで、ＣＰＵ１１は、第１フレーム記憶領域３１の仮定し直した可変長フレームからパリティ部分を減算した位置をルートテーブルとみなす（ステップＳ４３）。
【００７１】
その後、ＣＰＵ１１は、第１フレーム記憶領域３１の仮定し直した可変長フレームのルートテーブル２７２を読み出し（ステップＳ４４）、正常に読み出せたかを判定する（ステップＳ４５）。ここでの判定は、ステップＳ３６で説明したものと同様である。判定の結果、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ４５でＮｏの場合）には、第１フレーム記憶領域３１中の親復元対象フレームのうち、先頭からステップＳ４２で仮定された可変長フレームの終端までを、娘復元対象フレームとして第２フレーム記憶領域３２にコピーする（ステップＳ４６）。その後は、ステップＳ３８へと処理が移る。
【００７２】
一方、ステップＳ３６、ステップＳ４０またはステップＳ４５で正常にルートテーブル２７２を読み出せた場合（ステップＳ３６、Ｓ４０またはＳ４５でＹｅｓの場合）には、正常に読み出せたルートテーブル２７２を用いてＮＡＮＤメモリ２０から管理情報をＲＡＭ３０の管理情報記憶領域３３に読み出し（ステップＳ４７）、処理が終了する。
【００７３】
なお、上記した説明では、パリティのサイズを２物理ページ分としているが、実施形態がこれに限定されるものではない。たとえば、パリティのサイズを物理ページの正の整数倍としてもよい。この場合には、ステップＳ４２での可変長フレームの終端ページの仮定のし直しでは、第１フレーム記憶領域３１の読み出されたフレームの前回仮定された終端から１つ前のページとすればよい。
【００７４】
また、ＮＡＮＤメモリ２０へのデータの書き込み単位（ページ）とＮＡＮＤメモリ２０でのデータの最小管理単位とが同じであってもよいし、異なっていてもよい。たとえば、ＮＡＮＤメモリ２０へのデータの書き込み単位を、ＮＡＮＤメモリ２０でのデータの最小管理単位の正の整数倍となるようにしてもよい。このようにすることで、パリティのサイズを物理ページの正の整数分の１倍とすることができる。この場合には、ステップＳ４２での可変長フレームの終端の仮定のし直しでは、第１フレーム記憶領域３１の読み出されたフレームの前回仮定された終端から物理ページの正の整数分の１ページ前とすればよい。
【００７５】
管理情報の復元処理の具体例について、図７を参照しながら説明する。図７では、データＤ５が書き込まれている最中に不正な電源オフが生じたものとする。そのため、データＤ５について、パリティが論理ブロック２００には書き込まれなかったものとする。
【００７６】
この状態からメモリシステム１Ａが起動されると、イレースページ検索によって、最終書き込みページとイレースページとの境界Ｂが取得される。ＣＰＵ１１は、この境界Ｂから１物理ページ分前に遡った部分が可変長フレームの終端ページＴＰ１であると仮定する。そこで、ＣＰＵ１１は、この終端ページＴＰ１から２物理ページ分のパリティを減算した位置（ページ２８１）にルートテーブル２７２が存在するものとみなす。
【００７７】
ここで、図１０のステップＳ３５〜Ｓ４０の処理が実行される。しかし、イレースページ検索で終端ページＴＰ１とされたページには、実際にはパリティではなく、中途半端に書き込まれたデータＤ５が保存されている。そのため、ルートテーブル２７２の読み出しは成功せず、パリティを用いた訂正処理によっても、ルートテーブル２７２の読み出しは成功しない。なお、訂正処理は、第２フレーム記憶領域３２にコピーされた娘復元対象フレームに対して行われる。
【００７８】
ルートテーブル２７２の読み出しが成功しなかったため、第２フレーム記憶領域３２の復元フレームが消去され、前回仮定した終端ページＴＰ１から１つ前のページが新たに仮定し直した終端ページＴＰ２とされる。また、ＣＰＵ１１は、この終端ページＴＰ２から２物理ページ分のパリティを減算した位置（ページ２８２）にルートテーブル２７２が存在するものとみなす。
【００７９】
ここで、ステップＳ４４〜Ｓ４６，Ｓ３８〜Ｓ３９の処理が実行される。仮定し直した終端ページＴＰ２は、可変長フレーム２６３の終端ページと一致するので、ルートテーブル２７２の読み出しは成功する。そのため、論理ページ２２０ａの先頭から仮定し直した終端ページＴＰ２までの可変長フレーム２６３を用いて、管理情報が復元されることになる。
【００８０】
つぎに、比較例での管理情報の復元処理と比較した第１の実施形態の効果について説明する。図１１は、比較例によるＲＡＭの構成の一例を模式的に示す図である。比較例では、ＲＡＭ３０は、フレーム記憶領域３４と、管理情報記憶領域３３と、を有する。フレーム記憶領域３４は、起動時に、ＮＡＮＤメモリ２０から読み出された前回の電源オフ時に保存された管理情報を含む復元対象フレームを記憶する。比較例では、このフレーム記憶領域３４に記憶された復元対象フレームに対して誤り訂正処理が行われる。なお、図８と同一の構成要素には、同一の符号を付して、その説明を省略する。
【００８１】
図１２−１と図１２−２は、比較例による管理情報の復元処理の手順の一例を示すフローチャートである。第１の実施形態のステップＳ３１〜Ｓ３３と同様に、メモリシステム１Ａの電源がオンにされると、ＣＰＵ１１は、ＮＡＮＤメモリ２０の論理ブロックについて、イレースページ検索を行い、最終書き込みページを特定し、特定した最終書き込みページが可変長フレームの終端ページであると仮定する。ついで、ＣＰＵ１１は、仮定した可変長フレームからパリティ部分を減算した位置をルートテーブル２７２とみなす（ステップＳ７１〜Ｓ７３）。
【００８２】
ついで、ＣＰＵ１１は、ＮＡＮＤメモリ２０中の最終書き込みページを含む論理ページの先端から仮定した可変長フレームの終端までを復元対象フレームとして並列でＲＡＭ３０のフレーム記憶領域３４に読み出す（ステップＳ７４）。また、ＣＰＵ１１は、読み出された復元対象フレームのルートテーブル２７２を読み出し（ステップＳ７５）、正常に読み出せたかを判定する（ステップＳ７６）。ここでの判定は、図１０−２のステップＳ３６で説明したものと同様である。
【００８３】
ＥＣＣユニット１６は、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ７６でＮｏの場合）には、フレーム記憶領域３４中の復元対象フレームに対して訂正処理を行い、復元フレームを生成する（ステップＳ７７）。すなわち、ＥＣＣユニット１６は、仮定した終端から２ページ分のデータをパリティとして、このパリティを用いて、訂正処理を行う。これによって、復元対象フレームは、復元フレームとなる。
【００８４】
その後、ＣＰＵ１１は、復元フレームのルートテーブル２７２を読み出し（ステップＳ７８）、正常に読み出せたかを判定する（ステップＳ７９）。ここでの判定は、ステップＳ３６で説明したものと同様である。判定の結果、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ７９でＮｏの場合）には、ＣＰＵ１１は、フレーム記憶領域３４に記憶されている復元フレームを消去する（ステップＳ８０）。
【００８５】
ついで、ＣＰＵ１１は、ステップＳ７２での可変長フレームの終端ページの仮定に誤りがあったものとみなし、フレーム記憶領域３４の復元対象フレームで前回仮定された終端ページから１つ前のページを可変長フレームの終端ページと仮定し直す（ステップＳ８１）。その後、ＣＰＵ１１は、ＮＡＮＤメモリ２０中の最終書き込みページを含む論理ページの先端から仮定し直した可変長フレームの終端までを復元対象フレームとして並列でＲＡＭ３０のフレーム記憶領域３４に読み出す（ステップＳ８２）。
【００８６】
ついで、ＣＰＵ１１は、フレーム記憶領域３４の新たに仮定した可変長フレームからパリティ部分を減算した位置をルートテーブル２７２とみなす（ステップＳ８３）。その後、ＣＰＵ１１は、フレーム記憶領域の仮定した可変長フレームのルートテーブル２７２を読み出し（ステップＳ８４）、正常に読み出せたかを判定する（ステップＳ８５）。ここでの判定は、ステップＳ３６で説明したものと同様である。
【００８７】
判定の結果、ルートテーブル２７２を正常に読み出せなかった場合（ステップＳ８５でＮｏの場合）には、フレーム記憶領域３４中の復元対象フレームのうち、先頭からステップＳ８１で仮定された可変長フレームの終端までを新たな復元対象フレームとして、ステップＳ７７へと処理が移る。
【００８８】
一方、ステップＳ７６、ステップＳ７９またはステップＳ８５で正常にルートテーブル２７２を読み出せた場合（ステップＳ７６、Ｓ７９またはＳ８５でＹｅｓの場合）には、正常に読み出せたルートテーブル２７２を用いてＮＡＮＤメモリ２０から管理情報をＲＡＭ３０の管理情報記憶領域３３に読み出し（ステップＳ８６）、処理が終了する。
【００８９】
比較例では、イレースページ検索の結果得られる復元対象フレームがＮＡＮＤメモリ２０からＲＡＭ３０のフレーム記憶領域３４に読み出され、この読み出されたフレームに対して訂正処理が行われる。そのため、フレームの終端ページの仮定が間違っている場合、フレーム記憶領域３４に読み出されたデータは、誤った訂正符号で訂正が行われた復元フレームとなっているので、復元フレームを破棄し、再度ＮＡＮＤメモリ２０から復元対象フレームをフレーム記憶領域３４に読み出していた。
【００９０】
第２の実施形態では、イレースページ検索の結果得られる復元対象フレームが、ＮＡＮＤメモリ２０からＲＡＭ３０の第１フレーム記憶領域３１に親復元対象フレームとして記憶され、さらに親復元対象フレームが第２フレーム記憶領域３２に娘復元対象フレームとしてコピーされる。そして、娘復元対象フレームに対して訂正処理が行われる。そのため、フレームの終端ページの仮定が間違っている場合には、第２フレーム記憶領域３２の誤った訂正符号で訂正された復元フレームが破棄されるが、第１フレーム記憶領域３１から第２フレーム記憶領域３２へと新たに娘復元対象フレームがコピーされ、仮定し直した条件で再度娘復元対象フレームに対して訂正処理が行われる。ＲＡＭ３０の第１フレーム記憶領域３１に記憶された復元対象フレームを第２フレーム記憶領域３２にコピーする時間は、ＮＡＮＤメモリ２０に保存された復元対象フレームをＲＡＭ３０に読み出す時間に比して非常に短い。そのため、第２の実施形態では、比較例に比してメモリシステム１Ａの起動時間を短縮することができるという効果を有する。特に、フレームの終端の仮定を複数回し直す必要がある場合には、このコピーに要する時間の差がさらに大きくなるので、起動時間の短縮の効果が顕著となる。
【００９１】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９２】
１，１Ａ  メモリシステム、２  ホスト、３  通信路、１０  メモリコントローラ、１３  ＲＡＭコントローラ、１４  ＮＡＮＤコントローラ、１５  バス、１６  ＥＣＣユニット、２０  ＮＡＮＤメモリ、２１  ＮＡＮＤチップ、２２  信号線、３１  第１フレーム記憶領域、３２  第２フレーム記憶領域、３３  管理情報記憶領域、３４  フレーム記憶領域、１１１  データ制御部、１１２，１１４  アドレス制御部、１１３  コンパクション制御部、１１５  待ち時間制御部、２００  論理ブロック、２１０  物理ブロック、２２０，２２０ａ  論理ページ、２３０  物理ページ、２５１  固定長フレーム、２６１〜２６３  可変長フレーム、２７１  更新管理情報、２７２  ルートテーブル、２７２１  テーブル位置情報、２７２２  シグニチャ、２７２３  ルートテーブル位置。
【図１】
2018156263.tif 000003
【図２】
2018156263.tif 000004
【図３】
2018156263.tif 000005
【図４】
2018156263.tif 000006
【図５】
2018156263.tif 000007
【図６】
2018156263.tif 000008
【図７】
2018156263.tif 000009
【図８】
2018156263.tif 000010
【図９】
2018156263.tif 000011
【図１０−１】
2018156263.tif 000012
【図１０−２】
2018156263.tif 000013
【図１１】
2018156263.tif 000014
【図１２−１】
2018156263.tif 000015
【図１２−２】
2018156263.tif 000016