(57)【要約】【課題】追い出し処理の判断を高速に行い、書き込み処理を高速化する。【解決手段】キャッシュメモリと、不揮発性半導体メモリと、不揮発性半導体メモリにおいてセクタ単位の自然数倍である第１の管理単位でデータを記憶する第１の手段及び第１の管理単位の２以上の自然数倍である第２の管理単位でデータを記憶する第２の手段を有するコントローラと、を具備し、コントローラは、キャッシュメモリに保持されるデータを、第１の管理単位のアドレスで管理する第３の手段及び第２の管理単位のアドレスで管理する第４の手段を有し、キャッシュメモリに保持されるデータが所属する第２の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する。【選択図】図６
2011103144.tif 000002
【特許請求の範囲】
【請求項１】
セクタ単位の書き込みデータを保持可能なキャッシュメモリと、
ページ単位でデータ書き込みを行い、前記ページ単位の２以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、
前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第１の管理単位でデータを記憶する第１の手段、前記不揮発性半導体メモリにおいて前記第１の管理単位の２以上の自然数倍である第２の管理単位でデータを記憶する第２の手段、前記キャッシュメモリに保持されるデータを前記第１の管理単位のアドレスで管理する第３の手段、及び前記キャッシュメモリに保持されるデータを前記第２の管理単位のアドレスで管理する第４の手段を有するコントローラと、を具備し、
前記キャッシュメモリは、前記第１の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第１の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、
前記第１の手段は、前記第１の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第１の管理単位のデータの記憶位置とを関連付ける情報を含む第１の管理テーブルを備え、
前記第２の手段は、前記第２の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第２の管理単位のデータの記憶位置を関連付ける情報を含む第２の管理テーブルを備え、
前記第３の手段は、前記エントリに登録された前記第１の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第１の管理単位のアドレスが所属する前記第２の管理単位のアドレスを含む第３の管理テーブルを備え、
前記第４の手段は、前記キャッシュメモリにおける前記第２の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第２の管理単位のアドレス中で前記第１の管理単位の有効データが保持されている位置を含む第４の管理テーブルを備え、
前記コントローラは、
前記キャッシュメモリに保持されるデータが所属する前記第２の管理単位のアドレスの個数が所定の閾値を超えた場合、または、前記キャッシュメモリへのデータ書き込み処理を実行する際に前記第２の管理テーブルにおいて最後の空きウェイが使用される場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行し、
前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する場合に、前記第４の管理テーブルに登録された順序が最も古い前記第２の管理単位のアドレスを選択し、前記キャッシュメモリにおいて当該第２の管理単位のアドレスに含まれるデータを追い出し処理の対象とし、
追い出し対象として選択した前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第１の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第２の管理単位のデータとして前記不揮発性半導体メモリに記憶する、
ことを特徴とするメモリシステム。
【請求項２】
セクタ単位の書き込みデータを保持可能なキャッシュメモリと、
ページ単位でデータ書き込みを行い、前記ページ単位の２以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、
前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第１の管理単位でデータを記憶する第１の手段及び前記第１の管理単位の２以上の自然数倍である第２の管理単位でデータを記憶する第２の手段を有するコントローラと、を具備し、
前記コントローラは、
前記キャッシュメモリに保持されるデータを、前記第１の管理単位のアドレスで管理する第３の手段及び前記第２の管理単位のアドレスで管理する第４の手段を有し、前記キャッシュメモリに保持されるデータが所属する前記第２の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する、
ことを特徴とするメモリシステム。
【請求項３】
前記コントローラは、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する場合に、前記第４の手段に登録された順序が最も古い前記第２の管理単位のアドレスを選択し、当該第２の管理単位のアドレスに含まれるデータを追い出し処理の対象とすることを特徴とする請求項２に記載のメモリシステム。
【請求項４】
前記第１の手段は、前記第１の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第１の管理単位のデータの記憶位置とを関連付ける情報を含む第１の管理テーブルを備えることを特徴とする請求項２に記載のメモリシステム。
【請求項５】
前記第２の手段は、前記第２の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第２の管理単位のデータの記憶位置を関連付ける情報を含む第２の管理テーブルを備えることを特徴とする請求項２に記載のメモリシステム。
【請求項６】
前記キャッシュメモリは、前記第１の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第１の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、
前記第３の手段は、前記エントリに登録された前記第１の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第１の管理単位のアドレスが所属する前記第２の管理単位のアドレスを含む第３の管理テーブルを備えることを特徴とする請求項２に記載のメモリシステム。
【請求項７】
前記第４の手段は、前記キャッシュメモリにおける前記第２の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第２の管理単位のアドレス中で前記第１の管理単位の有効データが保持されている位置を含む第４の管理テーブルを備えることを特徴とする請求項２に記載のメモリシステム。
【請求項８】
前記コントローラは、前記キャッシュメモリへのデータ書き込み処理を実行する際に前記第２の管理テーブルにおいて最後の空きウェイが使用される場合、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項６に記載のメモリシステム。
【請求項９】
前記コントローラは、前記第２の管理単位のアドレス毎に前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項７に記載のメモリシステム。
【請求項１０】
前記コントローラは、追い出し対象として選択した前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第１の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第２の管理単位のデータとして前記不揮発性半導体メモリに記憶することを特徴とする請求項９に記載のメモリシステム。
【請求項１１】
セクタ単位の書き込みデータを保持可能なキャッシュメモリと、
ページ単位でデータ書き込みを行い、前記ページ単位の２以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、
前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第１の管理単位でデータを記憶する第１の手段及び前記第１の管理単位の２以上の自然数倍である第２の管理単位でデータを記憶する第２の手段を有するコントローラと、を具備し、
前記キャッシュメモリは、前記第１の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第１の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、
前記コントローラは、前記キャッシュメモリへのデータ書き込み処理を実行する際に最後の空きウェイが使用される場合、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とするメモリシステム。
【請求項１２】
前記コントローラは、前記キャッシュメモリに保持されるデータを、前記第１の管理単位のアドレスで管理する第３の手段及び前記第２の管理単位のアドレスで管理する第４の手段を有することを特徴とする請求項１１に記載のメモリシステム。
【請求項１３】
前記第１の手段は、前記第１の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第１の管理単位のデータの記憶位置とを関連付ける情報を含む第１の管理テーブルを備えることを特徴とする請求項１１に記載のメモリシステム。
【請求項１４】
前記第２の手段は、前記第２の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第２の管理単位のデータの記憶位置を関連付ける情報を含む第２の管理テーブルを備えることを特徴とする請求項１１に記載のメモリシステム。
【請求項１５】
前記第３の手段は、前記エントリに登録された前記第１の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第１の管理単位のアドレスが所属する前記第２の管理単位のアドレスを含む第３の管理テーブルを備えることを特徴とする請求項１２に記載のメモリシステム。
【請求項１６】
前記第４の手段は、前記キャッシュメモリにおける前記第２の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第２の管理単位のアドレス中で前記第１の管理単位の有効データが保持されている位置を含む第４の管理テーブルを備えることを特徴とする請求項１２に記載のメモリシステム。
【請求項１７】
前記コントローラは、前記キャッシュメモリに保持されるデータが所属する前記第２の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項１２に記載のメモリシステム。
【請求項１８】
前記コントローラは、前記第２の管理単位のアドレス毎に前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項１２に記載のメモリシステム。
【請求項１９】
前記コントローラは、追い出し対象として選択した前記第２の管理単位のアドレスに含まれる前記第１の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第１の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第２の管理単位のデータとして前記不揮発性半導体メモリに記憶することを特徴とする請求項１８に記載のメモリシステム。
【請求項２０】
前記不揮発性半導体メモリは、ＮＡＮＤ型フラッシュメモリであることを特徴とする請求項１乃至請求項１９に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュメモリなどの不揮発性半導体記憶素子を用いて構成されるメモリシステムに関する。
【背景技術】
【０００２】
コンピュータシステムに用いられる外部記憶装置として、ＮＡＮＤ型フラッシュメモリなどのフラッシュメモリを搭載したＳＳＤ（Solid State Drive）が注目されている。フラッシュメモリは、磁気ディスク装置に比べ、高速、軽量などの利点を有している。
【０００３】
ＳＳＤ内には、複数のフラッシュメモリチップ、ホスト装置からの要求に応じて各フラッシュメモリチップのリード/ライト制御を行うコントローラ、各フラッシュメモリチップとホスト装置との間でデータ転送を行うためのバッファメモリ、電源回路、ホスト装置に対する接続インタフェースなどを備えている（例えば、特許文献１）。
【０００４】
ＮＡＮＤ型フラッシュメモリのように、不揮発性半導体記憶素子には、データを記憶させる場合に、ブロックと呼ばれる単位で一度データを消去してからその後に書き込みを行うものがあったり、ページと呼ばれる単位で読み出し／書き込みを行うものがあったり、消去／読み出し／書き込みの単位が固定されていたりするものがある。
【０００５】
一方、パーソナルコンピュータなどのホスト機器がハードディスクをはじめとする二次記憶装置に対してデータの読み出し／書き込みを行う単位は、セクタと呼ばれる。セクタは、半導体記憶素子の消去／読み出し／書き込みの単位とは独立に定められる。
【０００６】
例えば、半導体記憶素子のブロックの大きさ（ブロックサイズ）は、５１２キロバイト、ページの大きさ（ページサイズ）は、４キロバイトであるのに対して、ホスト機器のセクタの大きさ（セクタサイズ）は、５１２バイトのように定められている。
【０００７】
このように、半導体記憶素子の消去／読み出し／書き込みの単位は、ホスト機器の読み出し／書き込みの単位よりも大きい場合がある。
【０００８】
このような半導体記憶素子を用いてハードディスクのようなパーソナルコンピュータの二次記憶装置を構成する場合、ホスト機器としてのパーソナルコンピュータからの小さなサイズのデータは、半導体記憶素子のブロックサイズ、ページサイズに適合させてアドレス変換を行う必要がある。
【０００９】
また、フラッシュメモリは、データの書き込みに先立って行うブロックの消去回数の増加に応じてセルの劣化が進行していく傾向があるため、半導体記憶素子内の全てのセルの消去回数が概ね等しくなるように、データ更新箇所を半導体記憶素子内で均等に分散させるウェアレベリングと呼ばれる処理が行われる。
【００１０】
このようなフラッシュメモリを用いて大容量の二次記憶装置を構成する場合においては、上記のようなアドレス変換を行う場合に、データ管理の単位が小さいサイズ（例えば、ページサイズ）であると、管理テーブルのサイズが大きくなって、二次記憶装置のコントローラの主記憶メモリに納まらなくなり、アドレス変換が高速にできなくなるという問題がある。このように、二次記憶装置としてのＮＡＮＤ型フラッシュメモリの大容量化に伴い管理テーブルのサイズは必然的に大きくなるが、管理テーブルをできるだけ小容量化し、また管理テーブルによる検索処理を高速化するための手法が求められている。
【００１１】
また、ＳＳＤにおいては、特許文献２に示されるように、フラッシュメモリとホスト装置との間に、キャッシュメモリを介在させて、フラッシュメモリでの書き込み回数（消去回数）を減らすように構成されていることが多い。キャッシュメモリにホスト装置からの書き込みが発生した際に、キャッシュメモリが満杯の場合は、キャッシュメモリからフラッシュメモリへのデータ追い出しを行ってから、キャッシュメモリにデータを書き込むことになる。このように書き込み用のキャシュメモリの場合は、読み出し用のキャッシュメモリとは異なって、フラッシュメモリへの追い出し処理が発生するため、処理が複雑となり、その管理テーブルのサイズは大型化するとともに、管理テーブルの検索処理に時間がかかるという問題がある。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特許第３６８８８３５号公報
【特許文献２】特表２００７−５２８０７９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、ライトキャッシュの管理テーブルのためのメモリ量を削減するとともに、ラ
イトキャッシュの管理テーブルによる検索処理の高速化を図るメモリシステムを提供する
ことを目的とする。
【課題を解決するための手段】
【００１４】
本願発明の一態様によれば、セクタ単位の書き込みデータを保持可能なキャッシュメモリと、ページ単位でデータ書き込みを行い、前記ページ単位の２以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第１の管理単位でデータを記憶する第１の手段及び前記第１の管理単位の２以上の自然数倍である第２の管理単位でデータを記憶する第２の手段を有するコントローラと、を具備し、前記コントローラは、前記キャッシュメモリに保持されるデータを、前記第１の管理単位のアドレスで管理する第３の手段及び前記第２の管理単位のアドレスで管理する第４の手段を有し、前記キャッシュメモリに保持されるデータが所属する前記第２の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、追い出し処理の判断を高速に行うことができ、書き込み処理を高速化することができ、また管理テーブル量を削減することができる。
【図面の簡単な説明】
【００１６】
【図１】ＳＳＤの構成例を示すブロック図。
【図２】ＮＡＮＤメモリチップに含まれる１個のブロックの構成例と、４値データ記憶方式でのしきい値分布を示す図。
【図３】ドライブ制御回路のハードウェア的な内部構成例を示すブロック図。
【図４】プロセッサの機能構成例を示すブロック図。
【図５】ＮＡＮＤメモリおよびＤＲＡＭ内に形成された機能構成を示すブロック図。
【図６】ＷＣからＮＡＮＤメモリへの書き込み処理に係わるより詳細な機能ブロック図。
【図７】ＬＢＡ論理アドレスを示す図。
【図８】データ管理部内の管理テーブルの構成例を示す図。
【図９】ＲＣクラスタ管理テーブルの一例を示す図。
【図１０】ＷＣクラスタ管理テーブルの一例を示す図。
【図１１】ＷＣトラック管理テーブルの一例を示す図。
【図１２】トラック管理テーブルの一例を示す図。
【図１３】ＦＳ／ＩＳ管理テーブルの一例を示す図。
【図１４】ＭＳ論理ブロック管理テーブルの一例を示す図。
【図１５】ＦＳ／ＩＳ論理ブロック管理テーブルの一例を示す図。
【図１６】ＦＳ／ＩＳ内クラスタ管理テーブルの一例を示す図。
【図１７】論物変換テーブルの一例を示す図。
【図１８】読み出し処理の動作例を示すフローチャート。
【図１９】書き込み処理の動作例を示すフローチャート。
【図２０】各構成要素間のデータの流れにおける入力と出力の組み合わおよびその発生要因を示す図。
【発明を実施するための形態】
【００１７】
以下に添付図面を参照して、この発明にかかるメモリシステムの最良な実施の形態を詳細に説明する。
【００１８】
（実施の形態）
以下、本発明の実施の形態について図面を参照して説明する。なお、以下の説明において、同一の機能および構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【００１９】
先ず、本明細書で用いる用語について定義しておく。
・物理ページ：ＮＡＮＤメモリチップ内部において一括して書き込み／読み出しが可能な単位のこと。物理ページサイズは、例えば４ｋＢ。ただし、主データ（ユーザデータなど）に対してＳＳＤ内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、４ｋＢ＋冗長ビット（例えば、数１０Ｂ）が同時にメモリセルに書き込まれる単位となるが、説明の便宜上、上記のように定義する。
・論理ページ：ＳＳＤ内で設定される書き込み／読み出し単位であり、１以上の物理ページに対応付けられている。論理ページサイズは、例えば８ビットノーマルモードでは、４ｋＢ、３２ビット倍速モードでは、３２ｋＢ。ただし、冗長ビットは含まないものとする。
・物理ブロック：ＮＡＮＤメモリチップ内部において独立して消去可能な最小単位のことであり、複数の物理ページから構成される。物理ブロックサイズは、例えば５１２ｋＢ。ただし、主データに対してＳＳＤ内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、５１２ｋＢ＋冗長ビット（例えば、数１０ｋＢ）が同時に消去される単位となるが、説明の便宜上、上記のように定義する。
・論理ブロック：ＳＳＤ内で設定される消去単位であり、１以上の物理ブロックに対応付けられている。論理ブロックサイズは、例えば８ビットノーマルモードでは、５１２ｋＢ、３２ビット倍速モードでは、４ＭＢ。ただし、冗長ビットは含まないものとする。
・セクタ：ホストからの最小アクセス単位のこと。セクタサイズは、例えば５１２Ｂ。  ・クラスタ：ＳＳＤ内で「小さなデータ」を管理する管理単位。クラスタサイズはセクタサイズ以上であり、クラスタサイズの２以上の自然数倍が論理ページサイズとなるように定められる。
・トラック：ＳＳＤ内で「大きなデータ」を管理する管理単位。クラスタサイズの２以上の自然数倍がトラックサイズに、かつ、トラックサイズの２以上の自然数倍が論理ブロックサイズとなるように定められる。
・フリーブロック（ＦＢ）：用途未割り当てのＮＡＮＤ型フラッシュメモリ上の論理ブロックのこと。用途を割り当てる際に消去してから使用する。
・バッドブロック（ＢＢ）：ＮＡＮＤ型フラッシュメモリ上の、誤りが多いなど記憶領域として使用できない物理ブロックのこと。例えば、消去動作が正常に終了しなかった物理ブロックがバッドブロックＢＢとして登録される。
・書き込み効率：所定期間内における、ホストから書き込んだデータ量に対する、論理ブロックの消去量の統計値のこと。小さいほどＮＡＮＤ型フラッシュメモリの消耗度が小さい。
・有効クラスタ：最新のデータを保持しているクラスタ。
・無効クラスタ：最新ではないデータを保持しているクラスタ。
・有効トラック：最新のデータを保持しているトラック。
・無効トラック：最新ではないデータを保持しているトラック。
・コンパクション：管理対象内の論理ブロックから、有効クラスタや有効トラックのみを取り出して、新しい論理ブロックに書き直すこと。
【００２０】
［第１の実施形態］
図１は、ＳＳＤ（Solid State Drive）１００の構成例を示すブロック図である。ＳＳＤ１００は、ＡＴＡインタフェース（ＡＴＡ  Ｉ／Ｆ）２などのメモリ接続インタフェースを介してパーソナルコンピュータあるいはＣＰＵコアなどのホスト装置１と接続され、ホスト装置１の外部メモリとして機能する。また、ＳＳＤ１００は、ＲＳ２３２Ｃインタフェース（ＲＳ２３２Ｃ  Ｉ／Ｆ）などの通信インタフェース３を介して、デバッグ用／製造検査用機器２００との間でデータを送受信することができる。ＳＳＤ１００は、不揮発性半導体メモリとしてのＮＡＮＤ型フラッシュメモリ（以下、ＮＡＮＤメモリと略す）１０と、コントローラとしてのドライブ制御回路４と、揮発性半導体メモリとしてのＤＲＡＭ２０と、電源回路５と、状態表示用のＬＥＤ６と、ドライブ内部の温度を検出する温度センサ７と、フューズ８とを備えている。
【００２１】
電源回路５は、ホスト装置１側の電源回路から供給される外部直流電源から複数の異なる内部直流電源電圧を生成し、これら内部直流電源電圧をＳＳＤ１００内の各回路に供給する。また、電源回路５は、外部電源の立ち上がりまたは立ち下がりを検知し、パワーオンリセット信号を生成して、ドライブ制御回路４に供給する。フューズ８は、ホスト装置１側の電源回路とＳＳＤ１００内部の電源回路５との間に設けられている。外部電源回路から過電流が供給された場合フューズ８が切断され、内部回路の誤動作を防止する。
【００２２】
ＮＡＮＤメモリ１０は、この場合、４並列動作を行う４つの並列動作要素１０ａ〜１０ｄを有し、１つの並列動作要素は、２つのＮＡＮＤメモリパッケージを有する。各ＮＡＮＤメモリパッケージは、積層された複数のＮＡＮＤメモリチップ（例えば、１チップ＝２ＧＢ）によって構成されている。図１の場合は、各ＮＡＮＤメモリパッケージは、積層された４枚のＮＡＮＤメモリチップによって構成されており、ＮＡＮＤメモリ１０は６４ＧＢの容量を有する。各ＮＡＮＤメモリパッケージが、積層された８枚のＮＡＮＤメモリチップによって構成されている場合は、ＮＡＮＤメモリ１０は１２８ＧＢの容量を有することになる。
【００２３】
ＤＲＡＭ２０は、ホスト装置１とＮＡＮＤメモリ１０間でのデータ転送用キャッシュおよび作業領域用メモリとして機能する。また、ＤＲＡＭ２０の代わりに、ＦｅＲＡＭを使用しても良い。ドライブ制御回路４は、ホスト装置１とＮＡＮＤメモリ１０との間でＤＲＡＭ２０を介してデータ転送制御を行うとともに、ＳＳＤ１００内の各構成要素を制御する。また、ドライブ制御回路４は、状態表示用ＬＥＤ６にステータス表示用信号を供給するとともに、電源回路５からのパワーオンリセット信号を受けて、リセット信号およびクロック信号を自回路内およびＳＳＤ１００内の各部に供給する機能も有している。
【００２４】
各ＮＡＮＤメモリチップは、データ消去の単位である物理ブロックを複数配列して構成されている。図２（ａ）は、ＮＡＮＤメモリチップに含まれる１個の物理ブロックの構成例を示す回路図である。各物理ブロックは、Ｘ方向に沿って順に配列された（ｐ＋１）個のＮＡＮＤストリングを備えている（ｐは、０以上の整数）。（ｐ＋１）個のＮＡＮＤストリングにそれぞれ含まれる選択トランジスタＳＴ１は、ドレインがビット線ＢＬ０〜ＢＬｐに接続され、ゲートが選択ゲート線ＳＧＤに共通接続されている。また、選択トランジスタＳＴ２は、ソースがソース線ＳＬに共通接続され、ゲートが選択ゲート線ＳＧＳに共通接続されている。
【００２５】
各メモリセルトランジスタＭＴは、半導体基板上に形成された積層ゲート構造を備えたＭＯＳＦＥＴ（Metal Oxide Semiconductor Field Effect Transistor）から構成される。積層ゲート構造は、半導体基板上にゲート絶縁膜を介在して形成された電荷蓄積層（浮遊ゲート電極）、および電荷蓄積層上にゲート間絶縁膜を介在して形成された制御ゲート電極を含んでいる。メモリセルトランジスタＭＴは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じてデータを記憶する。メモリセルトランジスタＭＴは、１ビットを記憶するように構成されていてもよいし、多値（２ビット以上のデータ）を記憶するように構成されていてもよい。
【００２６】
また、メモリセルトランジスタＭＴは、浮遊ゲート電極を有する構造に限らず、ＭＯＮＯＳ（Metal-Oxide-Nitride-Oxide-Silicon）型など、電荷蓄積層としての窒化膜界面に電子をトラップさせることでしきい値調整可能な構造であってもよい。ＭＯＮＯＳ構造のメモリセルトランジスタＭＴについても同様に、１ビットを記憶するように構成されていてもよいし、多値（２ビット以上のデータ）を記憶するように構成されていてもよい。
【００２７】
各ＮＡＮＤストリングにおいて、（ｑ＋１）個のメモリセルトランジスタＭＴは、選択トランジスタＳＴ１のソースと選択トランジスタＳＴ２のドレインとの間に、それぞれの電流経路が直列接続されるように配置されている。すなわち、複数のメモリセルトランジスタＭＴは、隣接するもの同士で拡散領域（ソース領域若しくはドレイン領域）を共有するような形でＹ方向に直列接続される。
【００２８】
そして、最もドレイン側に位置するメモリセルトランジスタＭＴから順に、制御ゲート電極がワード線ＷＬ０〜ＷＬｑにそれぞれ接続されている。従って、ワード線ＷＬ０に接続されたメモリセルトランジスタＭＴのドレインは選択トランジスタＳＴ１のソースに接続され、ワード線ＷＬｑに接続されたメモリセルトランジスタＭＴのソースは選択トランジスタＳＴ２のドレインに接続されている。
【００２９】
ワード線ＷＬ０〜ＷＬｑは、物理ブロック内のＮＡＮＤストリング間で、メモリセルトランジスタＭＴの制御ゲート電極を共通に接続している。つまり、ブロック内において同一行にあるメモリセルトランジスタＭＴの制御ゲート電極は、同一のワード線ＷＬに接続される。この同一のワード線ＷＬに接続される（ｐ＋１）個のメモリセルトランジスタＭＴは１ページ（物理ページ）として取り扱われ、この物理ページごとにデータの書き込みおよびデータの読み出しが行われる。
【００３０】
また、ビット線ＢＬ０〜ＢＬｐは、ブロック間で、選択トランジスタＳＴ１のドレインを共通に接続している。つまり、複数のブロック内において同一列にあるＮＡＮＤストリングは、同一のビット線ＢＬに接続される。
【００３１】
図２（ｂ）は、例えば、１個のメモリセルトランジスタＭＴに２ビットの記憶を行う４値データ記憶方式でのしきい値分布を示す模式図である。４値データ記憶方式では、上位ページデータ“ｘ”と下位ページデータ“ｙ”で定義される４値データ“ｘｙ”の何れか１つをメモリセルトランジスタＭＴに保持可能である。
【００３２】
この、４値データ“ｘｙ”は、メモリセルトランジスタＭＴのしきい値電圧の順に、例えば、データ“１１”、“０１”、“００”、“１０”が割り当てられる。データ“１１”は、メモリセルトランジスタＭＴのしきい値電圧が負の消去状態である。
【００３３】
下位ページ書き込み動作においては、データ“１１”（消去状態）のメモリセルトランジスタＭＴに対して選択的に、下位ビットデータ“ｙ”の書き込みによって、データ“１０”が書き込まれる。上位ページ書き込み前のデータ“１０”のしきい値分布は、上位ページ書き込み後のデータ“０１”とデータ“００”のしきい値分布の中間程度に位置しており、上位ページ書き込み後のしきい値分布よりブロードであってもよい。上位ページ書き込み動作においては、データ“１１”のメモリセルと、データ“１０”のメモリセルに対して、それぞれ選択的に上位ビットデータ“ｘ”の書き込みが行われて、データ“０１”およびデータ“００”が書き込まれる。
【００３４】
図３は、ドライブ制御回路４のハードウェア的な内部構成例を示すブロック図である。ドライブ制御回路４は、データアクセス用バス１０１、第１の回路制御用バス１０２、および第２の回路制御用バス１０３を備えている。第１の回路制御用バス１０２には、ドライブ制御回路４全体を制御するプロセッサ１０４が接続されている。第１の回路制御用バス１０２には、ＮＡＮＤメモリ１０に記憶された各管理プログラム（ＦＷ：ファームウエア）をブートするブート用プログラムが格納されたブートＲＯＭ１０５がＲＯＭコントローラ１０６を介して接続されている。また、第１の回路制御用バス１０２には、図１に示した電源回路５からのパワーオンリセット信号を受けて、リセット信号およびクロック信号を各部に供給するクロックコントローラ１０７が接続されている。
【００３５】
第２の回路制御用バス１０３は、第１の回路制御用バス１０２に接続されている。第２の回路制御用バス１０３には、図１に示した温度センサ７からのデータを受けるためのＩ２Ｃ回路１０８、状態表示用ＬＥＤ６にステータス表示用信号を供給するパラレルＩＯ（ＰＩＯ）回路１０９、ＲＳ２３２Ｃ  Ｉ／Ｆ３を制御するシリアルＩＯ（ＳＩＯ）回路１１０が接続されている。
【００３６】
ＡＴＡインタフェースコントローラ（ＡＴＡコントローラ）１１１、第１のＥＣＣ（Error Checking and Correction）回路１１２、ＮＡＮＤコントローラ１１３、およびＤＲＡＭコントローラ１１４は、データアクセス用バス１０１と第１の回路制御用バス１０２との両方に接続されている。ＡＴＡコントローラ１１１は、ＡＴＡインタフェース２を介してホスト装置１との間でデータを送受信する。データアクセス用バス１０１には、データ作業領域作業領域およびファームウェア展開領域として使用されるＳＲＡＭ１１５がＳＲＡＭコントローラ１１６を介して接続されている。ＮＡＮＤメモリ１０に記憶されているファームウェアは起動時、ブートＲＯＭ１０５に記憶されたブート用プログラムによってＳＲＡＭ１１５に転送される。
【００３７】
ＮＡＮＤコントローラ１１３は、ＮＡＮＤメモリ１０とのインタフェース処理を行うＮＡＮＤ  Ｉ／Ｆ１１７、第２のＥＣＣ回路１１８、およびＮＡＮＤメモリ１０−ＤＲＡＭ２０間のアクセス制御を行うＤＭＡ転送制御用ＤＭＡコントローラ１１９を備えている。第２のＥＣＣ回路１１８は第２の訂正符号のエンコードを行い、また、第１の誤り訂正符合のエンコードおよびデコードを行う。第１のＥＣＣ回路１１２は、第２の誤り訂正符号のデコードを行う。第１の誤り訂正符号、第２の誤り訂正符号は、例えば、ハミング符号、ＢＣＨ（Bose Chaudhuri Hocqenghem）符号、ＲＳ(Reed Solomon)符号、或いはＬＤＰＣ（Low Density Parity Check）符号等であり、第２の誤り訂正符号の訂正能力は、第１の誤り訂正符号の訂正能力よりも高いとする。
【００３８】
図１および図３に示したように、ＮＡＮＤメモリ１０においては、４つの並列動作要素１０ａ〜１０ｄが各８ビットの４チャネル（４ｃｈ）を介して、ドライブ制御回路４内部のＮＡＮＤコントローラ１１２に並列接続されている。４つの並列動作要素１０ａ〜１０ｄを単独動作させるか、並列動作させるか、ＮＡＮＤメモリチップの備える倍速モード（Multi Page Program / Multi Page Read / Multi Block Erase）を使用するか否か、という組み合わせにより、下記３種類のアクセスモードが提供される。
（１）８ビットノーマルモード
１ｃｈだけ動作させ、８ビット単位でデータ転送を行うモードである。物理ページサイズ（４ｋＢ）で書き込み／読み出しが行われる。また、物理ブロックサイズ（５１２ｋＢ）で消去が行われる。１つの物理ブロックに対して１つの論理ブロックが対応付けられ、論理ブロックサイズは５１２ｋＢとなる。
（２）３２ビットノーマルモード
４ｃｈ並列で動作させ、３２ビット単位でデータ転送を行うモードである。物理ページサイズ×４（１６ｋＢ）で書き込み／読み出しが行われる。また、物理ブロックサイズ×４（２ＭＢ）で消去が行われる。４つの物理ブロックに対して１つの論理ブロックが対応付けられ、論理ブロックサイズは２ＭＢとなる。
（３）３２ビット倍速モード
４ｃｈ並列で動作させ、更に、ＮＡＮＤメモリチップの倍速モードを利用して書き込み／読み出しを行うモードである。物理ページサイズ×４×２（３２ｋＢ）で書き込み／読み出しが行われる。また、物理ブロックサイズ×４×２（４ＭＢ）で消去が行われる。８つの物理ブロックに対して１つの論理ブロックが対応付けられ、論理ブロックサイズは４ＭＢとなる。
【００３９】
４ｃｈ並列動作する３２ビットノーマルモードまたは３２ビット倍速モードでは、並列動作する４または８物理ブロックが、ＮＡＮＤメモリ１０としての消去単位となり、並列動作する４または８物理ページが、ＮＡＮＤメモリ１０としての書き込み単位および読み出し単位となる。以下の動作では、基本的に３２ビット倍速モードを使用し、例えば、１論理ブロック＝４ＭＢ＝２ｉトラック＝２ｊページ＝２ｋクラスタ＝２ｌセクタとして説明する（ｉ、ｊ、ｋ、ｌは自然数、かつ、ｉ＜ｊ＜ｋ＜ｌの関係が成立する）。
【００４０】
３２ビット倍速モードでアクセスされる論理ブロックは４ＭＢ単位であり、８個（２×４ｃｈ）の物理ブロック（１物理ブロック＝５１２ＫＢ）が対応付けられている。物理ブロック単位で管理されるバッドブロックＢＢが発生すると、そのバッドブロックＢＢは使用不可になるので、そのようなときには、論理ブロックに対応付けられた８個の物理ブロックの組み合わせが、バッドブロックＢＢを含まないように変更される。
【００４１】
図４は、プロセッサ１０４により実現されるファームウェアの機能構成例を示すブロック図である。プロセッサ１０４により実現されるファームウェアの各機能は、大きく、データ管理部１２０、ＡＴＡコマンド処理部１２１、セキュリティ管理部１２２、ブートローダ１２３、初期化管理部１２４、デバッグサポート部１２５に分類される。
【００４２】
データ管理部１２０は、ＮＡＮＤコントローラ１１２、第１のＥＣＣ回路１１４を介して、ＮＡＮＤメモリ１０−ＤＲＡＭ２０間のデータ転送、ＮＡＮＤメモリ１０に関する各種機能を制御する。ＡＴＡコマンド処理部１２１は、ＡＴＡコントローラ１１０、およびＤＲＡＭコントローラ１１３を介して、データ管理部１２０と協動してＤＲＡＭ２０−ホスト装置１間のデータ転送処理を行う。セキュリティ管理部１２２は、データ管理部１２０およびＡＴＡコマンド処理部１２１と協動して各種のセキュリティ情報を管理する。
【００４３】
ブートローダ１２３は、パワーオン時、各管理プログラム（ファームウェア）をＮＡＮＤメモリ１０からＳＲＡＭ１２０にロードする。初期化管理部１２４は、ドライブ制御回路４内の各コントローラ／回路の初期化を行う。デバッグサポート部１２５は、外部からＲＳ２３２Ｃインタフェースを介して供給されたデバッグ用データを処理する。主に、データ管理部１２０、ＡＴＡコマンド処理部１２１、およびセキュリティ管理部１２２が、ＳＲＡＭ１１４に記憶される各管理プログラムをプロセッサ１０４が実行することによって実現される機能部である。
【００４４】
本実施形態では、主としてデータ管理部１２０が実現する機能について説明する。データ管理部１２０は、ＡＴＡコマンド処理部１２１が記憶デバイスであるＮＡＮＤメモリ１０やＤＲＡＭ２０に対して要求する機能の提供（ホスト装置からのWrite要求、Cache Flush要求、Read要求等の各種コマンドへの応答）と、アドレス領域とＮＡＮＤメモリ１０との対応関係の管理および管理情報の保護と、ＤＲＡＭ１０およびＮＡＮＤメモリ１０を利用した高速で効率の良いデータ読み出し／書き込み機能の提供、ＮＡＮＤメモリ１０の信頼性の確保などを行う。
【００４５】
図５は、ＮＡＮＤメモリ１０およびＤＲＡＭ２０内に形成された機能ブロックを示すものである。ホスト１とＮＡＮＤメモリ１０との間には、ＤＲＡＭ２０上に構成されたライトキャッシュ（ＷＣ）２１およびリードキャッシュ（ＲＣ）２２が介在している。ＷＣ２１はホスト装置１からのWriteデータを一時保存し、ＲＣ２２はＮＡＮＤメモリ１０からのReadデータを一時保存する。ＮＡＮＤメモリ１０内の論理ブロックは、書き込み時のＮＡＮＤメモリ１０に対する消去の量を減らすために、データ管理部１２０により、前段ストレージ領域（ＦＳ：Front Storage）１２、中段ストレージ領域（ＩＳ:Intermediate Storage）１３およびメインストレージ領域（ＭＳ：Main Storage）１１という各管理領域に割り当てられている。ＦＳ１２は、ＷＣ２１からのデータを「小さな単位」であるクラスタ単位に管理するものであり、小データを短期間保存する。ＩＳ１３は、ＦＳ１２から溢れたデータを「小さな単位」であるクラスタ単位に管理するものであり、小データを長期間保存する。ＭＳ１１は、ＷＣ２１、ＦＳ１２、ＩＳ１３からのデータを「大きな単位」であるトラック単位で長期間記憶する。例えば、記憶容量は、ＭＳ＞ＩＳ、ＦＳ＞ＷＣの関係となる。
【００４６】
小さな管理単位を、ＮＡＮＤメモリ１０の記憶領域全てに適用すると、後述する管理テーブルのサイズが肥大化し、ＤＲＡＭ２０に収まらないので、小さな管理単位で管理するのは、最近書き込まれたばかりのデータと、ＮＡＮＤメモリ１０への書き込み効率が悪い小さなデータのみとするようにＮＡＮＤメモリ１０の各ストレージを構成している。
【００４７】
図６は、ＷＣ２１からＮＡＮＤメモリ１０への書き込み処理（ＷＲ処理）に係わるより詳細な機能ブロック図を示すものである。ＦＳ１２の前段には、ＷＣ２１からのデータをバッファリングするＦＳインプットバッファ（ＦＳＩＢ）１２ａが設けられている。また、ＭＳ１１の前段には、ＷＣ２１、ＦＳ１２、またはＩＳ１３からのデータをバッファリングするＭＳインプットバッファ（ＭＳＩＢ）１１ａが設けられている。また、ＭＳ１１には、トラック前段ストレージ領域（ＴＦＳ）１１ｂが設けられている。ＴＦＳ１１ｂは、ＭＳＩＢ１１ａとＭＳ１１の間に介在するＦＩＦＯ（First in First out）構造を有するバッファであり、ＴＦＳ１１ｂに記録されたデータは、ＭＳＩＢ１１ａから直接ＭＳ１１に書き込まれるデータよりも更新頻度が高いデータである。ＭＳ１１、ＭＳＩＢ１１ａ、ＴＦＳ１１ｂ、ＦＳ１２、ＦＳＩＢ１２ａ、およびＩＳ１３には、ＮＡＮＤメモリ１０内の各論理ブロックの何れかが割り当てられている。
【００４８】
つぎに、図５、図６の各構成要素の具体的な機能構成について詳述する。ホスト装置１はＳＳＤ１００対し、ReadまたはWriteする際には、ＡＴＡインタフェースを介して論理アドレスとしてのＬＢＡ（Logical Block Addressing）を入力する。ＬＢＡは、図７に示すように、セクタ（サイズ：５１２Ｂ）に対して０からの通し番号をつけた論理アドレスである。本実施の形態においては、図５の各構成要素であるＷＣ２１、ＲＣ２２、ＦＳ１２、ＩＳ１３、ＭＳ１１の管理単位として、ＬＢＡの下位（ｌ−ｋ＋１）ビット目から上位のビット列で構成される論理クラスタアドレスと、ＬＢＡの下位（ｌ−ｉ＋１）ビットから上位のビット列で構成される論理トラックアドレスとを定義する。１クラスタ＝２（ｌ−ｋ）セクタで、１トラック＝２（ｋ−ｉ）クラスタである。
【００４９】
・リードキャッシュ（ＲＣ）２２
ＲＣ２２について説明する。ＲＣ２２は、ＡＴＡコマンド処理部１２１からのRead要求に対して、ＮＡＮＤメモリ１０（ＦＳ１２、ＩＳ１３、ＭＳ１１）からのReadデータを一時的に保存するための領域である。ＲＣ２２は、本実施形態では例えば、ｍ-line、ｎ-way（ｍは２（ｋ−ｉ）以上の自然数、ｎは２以上の自然数）セットアソシアティブ方式で管理されており、１エントリに１クラスタ分のデータを保持できる。論理クラスタアドレスのＬＳＢ（ｋ−ｉ）ビットでlineが決定される。なお、ＲＣ２２は、フルアソシアティブ方式で管理されていても良いし、単純なＦＩＦＯ方式で管理されていてもよい。
【００５０】
・ライトキャッシュ（ＷＣ）２１
ＷＣ２１について説明する。ＷＣ２１は、ＡＴＡコマンド処理部１２１からのWrite要求に対して、ホスト装置１からのWriteデータを一時的に保存するための領域である。ｍ-line、ｎ-way（ｍは２（ｋ−ｉ）以上の自然数、ｎは２以上の自然数）セットアソシアティブ方式で管理されており、１エントリに１クラスタ分のデータを保持できる。論理クラスタアドレスのＬＳＢ（ｋ−ｉ）ビットでlineが決定される。例えば、way１〜wayｎの順で書き込み可能なwayが検索される。また、ＷＣ２１に登録されているトラックは最も古く更新された順が分かるように後述するＷＣトラック管理テーブル２４のＦＩＦＯ構造によってＬＲＵ（Least Recently Used）で管理される。なお、ＷＣ２１は、フルアソシアティブ方式で管理されていても良い。また、ＷＣ２１は、ＲＣ２２とline数、way数が互いに異なっていてもよい。
【００５１】
Write要求により書き込まれたデータは、一旦ＷＣ２１上に格納される。ＷＣ２１からＮＡＮＤメモリ１０へ追い出すデータの決定方法は以下のルールに従う。
（i）タグによって決定されたlineの書き込み可能なwayが最後の(本実施形態では、ｎ個目の)空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうち、ＬＲＵに基づいて最も古く更新されたトラックを追い出し確定する。
（ii）ＷＣ２１に登録されている異なるトラックの個数が所定数を超えた場合、ＬＲＵ順で、当該トラックに属するＷＣ中のクラスタ数が所定数未満のトラックの追い出しを確定する。
【００５２】
以上の方針で追い出すトラックを決定する。その際、追い出すのは同一トラックに含まれる全てのデータであり、追い出されるデータ量が、例えばトラックサイズの５０％を超えていればＭＳ１１へ、超えていなければＦＳ１２へ追い出す。
【００５３】
さらに（i）の条件でトラック追い出しが発生した場合で、ＭＳ１１へ追い出す場合は、追い出されるトラック数が２ｉ個（もともと２ｉ個以上のときは２ｉ＋１個）になるまで、ＷＣ２１内のトラックのうち上記追い出されるデータ量がトラックサイズの５０％を超えるという条件を満たすトラックを上記(i)のポリシーで選択して追い出し候補に追加する。別言すれば、追い出されるトラックが２ｉ個未満の場合、ＷＣ中のトラックの古いものから２ｉ個になるまで、２（ｋ−ｉ−１）個以上有効クラスタをもつトラックを選択して追い出し候補に追加する。
【００５４】
また、（i）の条件でトラック追い出しが発生した場合で、ＦＳ１２に追い出す場合は、追い出されるクラスタ数が２ｋ個になるまでＷＣ２１内のトラックのうちＬＲＵ順に上記追い出されるデータ量がトラックサイズの５０％未満であるという条件を満たすトラックを探してそのクラスタを追い出し候補に追加する。別言すれば、ＷＣ中のトラックを古い順に辿って２（ｋ−ｉ−１）個未満の有効クラスタしかもたないトラックからクラスタを取り出していき、有効クラスタ数が２（ｋ−ｉ−１）個になったら、それらクラスタをＦＳＩＢ１２ａに論理ブロック単位で追い出しする。ただし、２（ｋ−ｉ−１）個見つからなかった場合は、ＦＳＩＢ１２ａに論理ページ単位で追い出しする。なお、ＦＳ１２への追い出しを論理ブロック単位とするか、論理ページ単位とするかの有効クラスタ数の閾値は、２（ｋ−ｉ−１）個という１論理ブロック分の値にかぎるわけではなく、１論理ブロック分より若干少ない値であってもよい。
【００５５】
また、ＡＴＡコマンド処理部１２１からのCache Flush要求では、ＷＣ２１の内容が全て、上記と同じ条件（追い出されるデータ量がトラックサイズの５０％を超えていればＭＳ１１へ、超えていなければＦＳ１２へ）で、ＦＳ１２もしくはＭＳ１１に対して追い出される。
【００５６】
・前段ストレージ領域（ＦＳ）１２
つぎに、ＦＳ１２について説明する。ＦＳ１２はクラスタ単位でデータを管理されるＦＩＦＯである。ＦＳ１２は、ここを通過しているデータは、後段のＩＳ１３よりも更新頻度が高いとみなすためのバッファである。すなわち、ＦＳ１２のＦＩＦＯ構造においては、ＦＩＦＯ中を通過中の有効クラスタ（最新クラスタ）は、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、ＦＳ１２を通過中のクラスタは、ＦＳ１２からＩＳ１３やＭＳ１１に追い出されたクラスタよりも、更新頻度が高いとみなすことができる。
【００５７】
ＦＳ１２を設けることで、後段のＩＳ１３におけるコンパクション処理に更新頻度の高いデータが紛れ込む可能性を低減している。無効化によって古いクラスタを保持していた論理ブロック自体の持つ有効クラスタ数が０となった場合、その論理ブロックは開放され、フリーブロックＦＢに割り当てられる。また、論理ブロックが無効化された場合、新たなフリーブロックＦＢを取得し、ＦＳ１２に割り当てる。
【００５８】
ＷＣ２１からＦＳ１２に対してクラスタデータの移動が発生すると、そのクラスタはＦＳＩＢ１２ａに割り当てられた論理ブロックに対して書き込まれる。ＦＳＩＢ１２ａ中に全てのページの書き込みが完了したブロックが存在する場合、後述するＣＩＢ処理によってそれらのブロックはＦＳＩＢ１２ａからＦＳ１２にＭｏｖｅされる。このＦＳＩＢ１２ａからＦＳ１２へのＭｏｖｅの際に、ＦＳ１２のブロック数がＦＳ１２として許容される所定の上限値を超えると、最も古いブロックがＦＳ１２からＩＳ１３またはＭＳ１１に追い出されることになる。例えば、トラック内の有効クラスタの割合が５０％以上のトラックは、ＭＳ１１（ＴＦＳ１１ｂ）への書き込みを行い、有効クラスタが残ったブロックを、ＩＳ１３へＭｏｖｅする。
【００５９】
ＮＡＮＤメモリ１０内の構成要素間のデータ移動には、ＭｏｖｅとＣｏｐｙの二通りがある。Ｍｏｖｅは、後述する管理テーブルのポインタの付け替えを行うだけで、実際のデータの書き換えは行わない方法である。Ｃｏｐｙは、一方の構成要素に格納されているデータを、ページ単位、トラック単位、ブロック単位で他方の構成要素に実際に書き換える方法である。
【００６０】
・中段ストレージ領域（ＩＳ）１３
つぎに、ＩＳ１３について説明する。ＩＳ１３は、ＦＳ１３と同様にクラスタ単位でデータの管理が行われる。前述したように、ＩＳ１３に格納されたデータは、更新頻度が低いデータとみなすことができる。ＦＳ１２からＩＳ１３に対して論理ブロックの移動（Ｍｏｖｅ）、すなわちＦＳ１２からの追い出しが発生すると、以前ＦＳ１２の管理対象であった追い出し対象の論理ブロックはポインタの付け替えによりＩＳ１３の管理対象ブロックとなる。このＦＳ１２からＩＳ１３への論理ブロックの移動により、ＩＳ１３のブロック数がＩＳ１３として許容される所定の上限値を超えると、すなわちＩＳ内の書き込み可能なフリーブロックＦＢの数が閾値を下回ると、ＩＳ１３からＭＳ１１へのデータ追い出しおよびコンパクション処理が実行され、ＩＳ１３のブロック数は規定値に戻される。
【００６１】
ＩＳ１３では、トラック内の有効クラスタ数を使って以下のような、追い出し処理およびコンパクション処理を、実行する。
・トラックをトラック内の有効クラスタ数×有効クラスタ係数(トラックがＭＳ１１内で無効トラックが存在する論理ブロックに存在するか否かによって重み付けされる数であり、存在したほうが存在しない場合より数が大きい)順にソートし、積の値が大きいトラック２ｉ＋１個(２論理ブロック分)を集めて論理ブロックサイズの自然数倍にしてＭＳＩＢ１１ａに追い出す。
・有効クラスタ数が最も少ない２つの論理ブロックの合計有効クラスタ数が例えば、所定の設定値である２ｋ個（１論理ブロック分）以上ある場合は、上のステップを繰り返す(ＩＳ内の２つの論理ブロックから、フリーブロックＦＢを作れるようになるまで行うため)。
・有効クラスタ数の少ない論理ブロックから順にクラスタを２ｋ個集め、ＩＳ１３内でコンパクションを行う。
なお、ここでは有効クラスタ数が最も少ない２つの論理ブロックを選択するとしたが、この数は２つに限定されず、２つ以上の数であればよい。また、所定の設定値は、選択する論路ブロック数よりも１つ少ない論理ブロック数に収容可能なクラスタ数以下であればよい。
【００６２】
・メインストレージ領域（ＭＳ）１１
つぎに、ＭＳ１１について説明する。ＭＳ１１はトラック単位でデータの管理を行う。ＭＳ１１に格納されたデータは、更新頻度が低いとみなすことができる。ＷＣ２１、ＦＳ１２、ＩＳ１３からＭＳ１１に対してトラックデータのＣｏｐｙまたはＭｏｖｅが発生すると、そのトラックはＭＳＩＳ１１ａに割り当てられた論理ブロックに対して書き込まれる。一方で、トラック中の一部のデータ（クラスタ）のみがＷＣ等から書き込まれるような場合には、既存のＭＳ中のトラックデータと新しいデータをマージして新しいトラックデータを作った上でＭＳＩＢ１１ａに書き込む、後述する受動マージが行われる。ＭＳ１１内に無効トラックが蓄積し、ＭＳ１１に割り当てられている論理ブロックの個数がＭＳ１１として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックＦＢを作る。
【００６３】
ＭＳ１１のコンパクション処理は、例えば、論理ブロック内の有効トラック数のみに注目した以下の方法を実施する。
・有効トラックが少ない論理ブロックから順番に、無効トラックを合わせることによって無効なフリーブロックＦＢが作れるようになるまで選択する。
・選択した論理ブロックに収容されたトラックを、ＷＣ２１、ＦＳ１２、ＩＳ１３内のデータと統合する受動マージを行いながらコンパクションを実行する。
・２ｉトラック統合できた論理ブロックは、ＴＦＳ１１ｂに出力し（２ｉトラックＭＳコンパクション）、２ｉトラックに満たない個数のトラックは、ＭＳＩＢ１１ａに出力して（２ｉトラック未満コンパクション）、より多くの無効なフリーブロックＦＢを作る。
【００６４】
ＴＦＳ１１ｂは、トラック単位でデータを管理されるＦＩＦＯである。ＴＦＳ１１ｂは、ここを通過しているデータは、後段のＭＳ１１よりも更新頻度が高いとみなすためのバッファである。すなわち、ＴＦＳ１１ｂのＦＩＦＯ構造においては、ＦＩＦＯ中を通過中の有効トラック（最新トラック）は、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、ＴＦＳ１１ｂを通過中のトラックは、ＴＦＳ１１ｂからＭＳ１１に追い出されたトラックよりも、更新頻度が高いとみなすことができる。
【００６５】
図８は、データ管理部１２０が図５および図６に示した各構成要素を制御管理するための管理テーブルを示すものである。データ管理部１２０は、前述したように、ＡＴＡコマンド処理部１２１とＮＡＮＤメモリ１０とをブリッジする機能を有し、ＤＲＡＭ２０に記憶したデータの管理を行うＤＲＡＭ層管理部１２０ａと、ＮＡＮＤメモリ１０に記憶したデータの管理を行う論理ＮＡＮＤ層管理部１２０ｂと、ＮＡＮＤメモリ１０を物理記憶デバイスとして管理する物理ＮＡＮＤ層管理部１２０ｃとから構成される。ＲＣクラスタ管理テーブル２３、ＷＣトラック管理テーブル２４、ＷＣクラスタ管理テーブル２５は、ＤＲＡＭ層管理部１２０ａにより制御される。トラック管理テーブル３０、ＦＳ／ＩＳ管理テーブル４０、ＭＳ論理ブロック管理テーブル３５、ＦＳ／ＩＳ論理ブロック管理テーブル４２、ＦＳ／ＩＳ内クラスタ管理テーブル４４は、論理ＮＡＮＤ層管理部１２０ｂにより管理される。論物変換テーブル５０は、物理ＮＡＮＤ層管理部１２０ｃにより管理される。
【００６６】
ＲＣ２２は、逆引きテーブルであるＲＣクラスタ管理テーブル２３によって管理される。逆引きテーブルでは、記憶デバイスの位置からその位置に記憶されている論理アドレスを検索することができる。ＷＣ２１は、逆引きテーブルであるＷＣクラスタ管理テーブル２５および正引きテーブルであるＷＣトラック管理テーブル２４によって管理される。正引きテーブルでは、論理アドレスからその論理アドレスに対応するデータが存在する記憶デバイス位置を検索することができる。
【００６７】
ＮＡＮＤメモリ１０内のＦＳ１２（ＦＳＩＢ１２ａ）、ＩＳ１３、ＭＳ１１（ＴＦＳ１１ｂ、ＭＳＩＢ１１ａ）は、トラック管理テーブル３０、ＦＳ／ＩＳ管理テーブル４０、ＭＳ論理ブロック管理テーブル３５、ＦＳ／ＩＳ論理ブロック管理テーブル４２、ＦＳ／ＩＳ内クラスタ管理テーブル４４によってその論理アドレスが管理される。また、ＮＡＮＤメモリ１０内のＦＳ１２（ＦＳＩＢ１２ａ）、ＩＳ１３、ＭＳ１１（ＴＦＳ１１ｂ、ＭＳＩＢ１１ａ）は、論物変換テーブル５０によって論理アドレスと物理アドレスとの変換が行われる。これらの各管理テーブルは、ＮＡＮＤメモリ１０上の領域に記憶されており、ＳＳＤ１００の初期化時にＮＡＮＤメモリ１０からＤＲＡＭ２０上に読み込まれて、使用される。
【００６８】
・ＲＣクラスタ管理テーブル２３（逆引き）
まず、図９を用いてＲＣクラスタ管理テーブル２３について説明する。ＲＣ２２は、前述したように、論理クラスタアドレスＬＳＢ（ｋ−ｉ）ビットでインデックスされるｎ-wayセットアソシアティブ方式で管理されている。ＲＣクラスタ管理テーブル２３は、ＲＣ（クラスタサイズ×ｍ-line×ｎ-way）２２の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ２３ａと、論理トラックアドレス２３ｂによって構成されている。状態フラグ２３ａには、当該エントリを使用しても良いか否か（有効／無効）を示すValidビットの他に、当該エントリがＮＡＮＤメモリ１０からの読み出し待ちか否かを示すビット、当該エントリがＡＴＡコマンド処理部１２１への読み出し待ちか否かを示すビットなどが含まれる。ＲＣクラスタ管理テーブル２３は、ＤＲＡＭ２０上のタグ記憶位置からＬＢＡに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。
【００６９】
・ＷＣクラスタ管理テーブル２５（逆引き）
つぎに、図１０を用いてＷＣクラスタ管理テーブル２５について説明する。ＷＣ２１は、前述したように、論理クラスタアドレスＬＳＢ（ｋ−ｉ）ビットでインデックスされるｎ-wayセットアソシアティブ方式で管理されている。ＷＣクラスタ管理テーブル２５は、ＷＣ（クラスタサイズ×ｍ-line×ｎ-way）２１の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ２５ａと、セクタ位置ビットマップ２５ｂと、論理トラックアドレス２５ｃによって構成されている。
【００７０】
状態フラグ２５ａには、当該エントリを使用しても良いか否か（有効／無効）を示すValidビットの他に、当該エントリがＮＡＮＤメモリ１０への追い出し待ちか否かを示すビット、当該エントリがＡＴＡコマンド処理部からの書き込み待ちか否かを示すビットなどが含まれる。セクタ位置ビットマップ２５ｂは、１クラスタに含まれる２（ｌ−ｋ）セクタのうちのどのセクタに有効なデータを保持しているかを２（ｌ−ｋ）ビットに展開して示すものである。このセクタ位置ビットマップ２５ｂによって、ＷＣ２１において、ＬＢＡと同じセクタ単位の管理を行うことができる。ＷＣクラスタ管理テーブル２５は、ＤＲＡＭ２０上のタグ記憶位置からＬＢＡに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。
【００７１】
・ＷＣトラック管理テーブル２４（正引き）
つぎに、図１１を用いてＷＣトラック管理テーブル２４について説明する。ＷＣトラック管理テーブル２４は、ＷＣ２１上に格納されているクラスタをトラック単位でまとめた情報を管理するものであり、ＦＩＦＯ的な機能を有するリンクドリスト構造によってトラック間のＷＣ２１に登録された順序（ＬＲＵ）を表現している。なお、ＷＣ２１で最後に更新された順序によってＬＲＵを表現するようにしてもよい。各リストのエントリは、論理トラックアドレス２４ａ、当該論理トラックアドレスに含まれるＷＣ２１中の有効クラスタ数２４ｂ、way-lineビットマップ２４ｃおよび次のエントリへのポインタを示すnextポインタ２４ｄから構成されている。ＷＣトラック管理テーブル２４は、論理トラックアドレス２４ａから所要情報を得るので、正引きテーブルとして機能する。
【００７２】
way-lineビットマップ２４ｃは、ＷＣ２１中で当該論理トラックアドレスに含まれる有効クラスタがＷＣ２１中のｍ×ｎのエントリ中のどのエントリに格納されているか示すマップ情報であり、有効クラスタが格納されているエントリではValidビットが”１”になっている。このway-lineビットマップ２４ｃは、例えば、（１ビット（Valid）＋log2ｎビット（ｎ-way））×ｍビット（ｍ-line）で構成されている。ＷＣトラック管理テーブル２４はリンクドリスト構造を有しており、ＷＣ２１中に存在する論理トラックアドレスに関する情報のみがエントリされている。
【００７３】
・トラック管理テーブル３０（正引き）
つぎに、図１２を用いてトラック管理テーブル３０について説明する。トラック管理テーブル３０は、論理トラックアドレス単位でＭＳ１１上の論理的なデータ位置を管理するためのテーブルであり、クラスタ単位でＦＳ１２やＩＳ１３にデータが保持されている場合には、それらに関する基本情報と、詳細情報へのポインタも保持している。論理トラックアドレス３０ａをインデックスとした配列形式で構成される。論理トラックアドレス３０ａをインデックスとした各エントリは、クラスタビットマップ３０ｂ、論理ブロックＩＤ３０ｃ＋論理ブロック内トラック位置３０ｄ、クラスタテーブルポインタ３０ｅ、ＦＳクラスタ数３０ｆ、ＩＳクラスタ数３０ｇなどの情報で構成されている。トラック管理テーブル３０は、論理トラックアドレスをインデックスとして、その論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックＩＤ（記憶デバイス位置に対応）などの所要情報を得るので、正引きテーブルとして機能する。
【００７４】
クラスタビットマップ３０ｂは、１つの論理トラックアドレス範囲に属する２（ｋ−ｉ）個のクラスタをクラスタアドレス昇順に例えば８分割したビットマップであり、８個の各ビットは、２（ｋ−ｉ−３）個のクラスタアドレスに対応するクラスタがＭＳ１１に存在するか、ＦＳ１２もしくはＩＳ１３に存在するかを示している。ビットが“０”の場合は、その検索対象のクラスタは確実にＭＳ１１内に存在することを示し、ビットが“１”の場合は、そのクラスタはＦＳ１２もしくはＩＳ１３に存在する可能性があることを示している。
【００７５】
論理ブロックＩＤ３０ｃは、当該論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックＩＤを識別するための情報である。論理ブロック内トラック位置３０ｄは、論理ブロックＩＤ３０ｃで指定された論理ブロック中における当該論理トラックアドレス（３０ａ）に対応するトラックの記憶位置を示すものである。１論理ブロックは最大２ｉ個の有効トラックで構成されるので、論理ブロック内トラック位置３０ｄは、ｉビットで２ｉ個のトラック位置を識別する。
【００７６】
クラスタテーブルポインタ３０ｅは、リンクドリスト構造を有するＦＳ／ＩＳ管理テーブル４０の各リストの先頭エントリへのポインタである。クラスタビットマップ３０ｂの検索で、当該クラスタがＦＳ１２／ＩＳ１３に存在する可能性があることを示していた場合、クラスタテーブルポインタ３０ｅを用いてＦＳ／ＩＳ管理テーブル４０の検索を実行する。ＦＳクラスタ数３０ｆは、ＦＳ１２内に存在する有効クラスタ数を示している。ＩＳクラスタ数３０ｇは、ＩＳ１３内に存在する有効クラスタ数を示している。
【００７７】
・ＦＳ／ＩＳ管理テーブル４０（正引き）
つぎに、図１３を用いてＦＳ／ＩＳ管理テーブル４０について説明する。ＦＳ／ＩＳ管理テーブル４０は、論理クラスタ単位でＦＳ１２（ＦＳＩＢ１２ａも含む）もしくはＩＳ１３に保持されているデータの位置を管理するためのテーブルである。図１３に示すように、論理トラックアドレス毎に独立したリンクドリスト形式で構成され、各リストの先頭エントリへのポインタは、前述したように、トラック管理テーブル３０のクラスタテーブルポインタ３０ｅのフィールドに保持されている。図１３では、２つの論理トラックアドレス分のリンクドリストが示されている。各エントリは、論理クラスタアドレス４０ａ、論理ブロックＩＤ４０ｂ、論理ブロック内クラスタ位置４０ｃ、ＦＳ／ＩＳブロックＩＤ４０ｄ、nextポインタ４０ｅから構成されている。ＦＳ／ＩＳ管理テーブル４０は、論理クラスタアドレス４０ａから、その論理クラスタアドレスに対応する論理クラスタが記憶されている論理ブロックＩＤ４０ｂ、論理ブロックン内クラスタ位置４０ｃ（記憶デバイス位置に対応）などの所要情報を得るので、正引きテーブルとして機能する。
【００７８】
論理ブロックＩＤ４０ｂは、当該論理クラスタアドレス４０ａに対応する論理クラスタが記憶されている論理ブロックＩＤを識別するための情報である。論理ブロック内クラスタ位置４０ｃは、論理ブロックＩＤ４０ｂで指定された論理ブロック中における当該論理クラスタアドレス４０ａに対応するクラスタの記憶位置を示すものである。１論理ブロックは最大２ｋ個の有効クラスタで構成されるので、論理ブロック内クラスタ位置４０ｃは、ｋビットで２ｋ位置を識別する。ＦＳ／ＩＳブロックＩＤ４０ｄは、後述するＦＳ／ＩＳ論理ブロック管理テーブル４２のインデックスであるＦＳ／ＩＳブロックＩＤが登録されている。ＦＳ／ＩＳブロックＩＤは、ＦＳ１２またはＩＳ１３に所属する論理ブロックを識別するための情報であり、このＦＳ／ＩＳ管理テーブル４０でのＦＳ／ＩＳブロックＩＤ４０ｄは、後述するＦＳ／ＩＳ論理ブロック管理テーブル４２とのリンクのために登録されている。nextポインタ４０ｅは、論理トラックアドレス毎にリンクされる同じリスト内の次のエントリへのポインタを示している。
【００７９】
・ＭＳ論理ブロック管理テーブル３５（逆引き）
つぎに、図１４を用いてＭＳ論理ブロック管理テーブル３５について説明する。ＭＳ論理ブロック管理テーブル３５は、ＭＳ１１に用いられている論理ブロックに関する情報（どの論理トラックが記憶されているか、追記可能か等）を一元管理するためのテーブルである。なお、ＭＳ論理ブロック管理テーブル３５には、ＦＳ１２（ＦＳＩＢ１２も含む）、ＩＳ１３に所属する論理ブロックに関する情報も登録されている。ＭＳ論理ブロック管理テーブル３５は、論理ブロックＩＤ３５ａをインデックスとした配列形式で構成され、エントリ数は１２８ＧＢのＮＡＮＤメモリ１０の場合は、３２Ｋエントリまで持つことができる。各エントリは、２iトラック分のトラック管理ポインタ３５ｂ、有効トラック数３５ｃ、書き込み可能先頭トラック３５ｄ、Validフラグ３５ｅから構成されている。このＭＳ論理ブロック管理テーブル３５は、記憶デバイス位置に対応する論理ブロックＩＤ３５ａから、この論理ブロックに記憶されている論理トラックアドレスなどの所要情報を得るので、逆引きテーブルとして機能する。
【００８０】
トラック管理ポインタ３５ｂは、論理ブロックＩＤ３５ａで指定される当該論理ブロック内の２i個のトラック位置毎に対応する論理トラックアドレスを保持する。この論理トラックアドレスを用いて、論理トラックアドレスをインデックスとするトラック管理テーブル３０を検索することができる。有効トラック数３５ｃは、論理ブロックＩＤ３５ａで指定される当該論理ブロックに記憶されているトラックのうちの有効なものの個数（最大２i個）を示している。書き込み可能先頭トラック位置３５ｄは、論理ブロックＩＤ３５ａで指定される当該論理ブロックが追記中のブロックであった場合における追記可能なトラック先頭位置（０〜２i−１、追記終了時は２i）を示している。Validフラグ３５ｅは、当該論理ブロックエントリがＭＳ１１（ＭＳＩＢ１１ａも含む）として管理されている
場合に“１”である。
【００８１】
・ＦＳ／ＩＳ論理ブロック管理テーブル４２（逆引き）
つぎに、図１５を用いてＦＳ／ＩＳ論理ブロック管理テーブル４２について説明する。ＦＳ／ＩＳ論理ブロック管理テーブル４２は、ＦＳ／ＩＳブロックＩＤ４２ａをインデックスとした配列形式で構成され、ＦＳ１２またはＩＳ１３として利用されている論理ブロックに関する情報（論理ブロックＩＤとの対応、ＦＳ／ＩＳ内クラスタ管理テーブル４４へのインデックス、追記可能か等）を管理するためのテーブルである。ＦＳ／ＩＳ論理ブロック管理テーブル４２は、主にＦＳ／ＩＳ管理テーブル４０中のＦＳ／ＩＳブロックＩＤ４０ｄを用いてアクセスされる。各エントリは、論理ブロックＩＤ４２ｂ、ブロック内クラスタテーブル４２ｃ、有効クラスタ数４２ｄ、書き込み可能先頭ページ４２ｅ、Validフラグ４２ｆから構成されている。このＭＳ論理ブロック管理テーブル３５は、記憶デバイス位置に対応するＦＳ／ＩＳブロックＩＤ４２ａから、この論理ブロックに記憶されている論理クラスタなどの所要情報を得るので、逆引きテーブルとして機能する。
【００８２】
論理ブロックＩＤ４２ｂには、ＭＳ論理ブロック管理テーブル３５に登録された論理ブロックの中で、ＦＳ１２（ＦＳＩＢ１２も含む）、ＩＳ１３に所属している論理ブロックに対応する論理ブロックＩＤが登録される。ブロック内クラスタテーブル４２ｃには、論理ブロック中の各クラスタ位置にどの論理クラスタアドレスで指定される論理クラスタが記録されているかを示す後述するＦＳ／ＩＳ内クラスタ管理テーブル４４へのインデックスが登録される。有効クラスタ数４２ｄは、ＦＳ／ＩＳブロックＩＤ４２ａで指定される当該論理ブロックに記憶されているクラスタのうちの有効なものの個数（最大２ｋ個）を示している。書き込み可能先頭ページ位置４２ｅは、ＦＳ／ＩＳブロックＩＤ４２ａで指定される当該論理ブロックが追記中のブロックであった場合における追記可能な先頭ページ位置（０〜２ｊ−１、追記終了時は２ｊ）を示している。Validフラグ４２ｆは、この論理ブロックエントリがＦＳ１２（ＦＳＩＢ１２も含む）またはＩＳ１３として管理されている場合に“１”である。
【００８３】
・ＦＳ／ＩＳ内クラスタ管理テーブル４４（逆引き）
つぎに、図１６を用いてＦＳ／ＩＳ内クラスタ管理テーブル４４について説明する。ＦＳ／ＩＳ内クラスタ管理テーブル４４は、ＦＳ１２もしくはＩＳ１３として利用されている論理ブロック中の各クラスタ位置にどの論理クラスタが記録されているのかを示すテーブルである。１論理ブロックあたり、２ｊページ×２（ｋ−ｊ）クラスタ＝２ｋ個のエントリを持ち、当該論理ブロック内のクラスタ位置の０番目〜２ｋ−１番目に対応する情報が連続領域に配置される。さらにこの２ｋ個の情報を含むテーブルがＦＳ１２およびＩＳ１３に所属する論理ブロック数（Ｐ個）分だけ保持されており、ＦＳ／ＩＳ論理ブロック管理テーブル４２のブロック内クラスタテーブル４２ｃは、このＰ個のテーブルに対する位置情報（ポインタ）となっている。連続領域に配される各エントリ４４ａの位置は、１論理ブロック中のクラスタ位置を示し、また各エントリ４４ａの内容は、当該クラスタ位置にどの論理クラスタが記憶されているかが識別できるように、ＦＳ／ＩＳ管理テーブル４０で管理される該当論理クラスタアドレスを含むリストへのポインタが登録されている。すなわち、エントリ４４ａは、リンクドリストの先頭を指し示すのではなく、リンクドリスト中の該当論理クラスタアドレスを含む１つのリストへのポインタが登録されている。
【００８４】
・論物変換テーブル５０（正引き）
つぎに、図１７を用いて論物変換テーブル５０について説明する。論物変換テーブル５０は、論理ブロックＩＤ５０ａをインデックスとした配列形式で構成され、エントリ数は、１２８ＧＢのＮＡＮＤメモリ１０の場合は、最大３２Ｋエントリまで持つことができる。論物変換テーブル５０は、論理ブロックＩＤと物理ブロックＩＤとの変換、寿命に関する情報を管理するためのテーブルである。各エントリは、物理ブロックアドレス５０ｂ、消去回数５０ｃ、読み出し回数５０ｄから構成される。この論物変換テーブル５０は、論理ブロックＩＤから物理ブロックＩＤ（物理ブロックアドレス）などの所要情報を得るので、正引きテーブルとして機能する。
【００８５】
物理ブロックアドレス５０ｂは、１つの論理ブロックＩＤ５０ａに所属する８個の物理ブロックＩＤ（物理ブロックアドレス）を示している。消去回数５０ｃは、当該論理ブロックＩＤの消去回数を示している。バッドブロック（ＢＢ）管理は、物理ブロック（５１２ＫＢ）単位に行われるが、消去回数の管理は、３２ビット倍速モードによる１論理ブロック（４ＭＢ）単位に管理される。読み出し回数５０ｄは、当該論理ブロックＩＤの読み出し回数を示している。消去回数５０ｃは、例えば、ＮＡＮＤ型フラッシュメモリの書き換え回数を平準化するウェアレベリング処理で利用することが可能である。読み出し回数５０ｄは、リテンション特性の劣化した物理ブロックに保持されるデータの再書き込みを行うリフレッシュ処理で利用することが可能である。
【００８６】
図８に示した管理テーブルを管理対象毎にまとめると次のようになる。
ＲＣ管理：ＲＣクラスタ管理テーブル
ＷＣ管理：ＷＣクラスタ管理テーブル、ＷＣトラック管理テーブル
ＭＳ管理：トラック管理テーブル３０、ＭＳ論理ブロック管理テーブル３５
ＦＳ/ＩＳ管理：トラック管理テーブル３０、ＦＳ/ＩＳ管理テーブル４０、ＭＳ論理ブロック管理テーブル３５、ＦＳ/ＩＳ論理ブロック管理テーブル４２、ＦＳ/ＩＳ内クラスタ管理テーブル４４
【００８７】
なお、ＭＳ構造管理テーブル（図示せず）において、ＭＳ１１，ＭＳＩＢ１１ａ、ＴＦＳ１１ｂを含めたＭＳ領域の構造を管理しており、具体的には、ＭＳ１１、ＭＳＩＢ１１ａ、ＴＦＳ１１ｂに割り当てた論理ブロックなどを管理している。また、ＦＳ/ＩＳ構造管理テーブル（図示せず）において、ＦＳ１２、ＦＳＩＢ１２ａ、ＩＳ１３を含めたＦＳ/ＩＳ領域の構造を管理しており、具体的には、ＦＳ１２、ＦＳＩＢ１２ａ、ＩＳ１３に割り当てた論理ブロックなどを管理している。
【００８８】
・Read処理
つぎに、図１８に示すフローチャートを参照して、読み出し処理について説明する。ＡＴＡコマンド処理部１２１から、Readコマンドおよび読み出しアドレスとしてのＬＢＡが入力されると、データ管理部１２０は、図９に示したＲＣクラスタ管理テーブル２３と図１０に示したＷＣクラスタ管理テーブル２５を検索する（ステップＳ１００）。具体的には、ＬＢＡのクラスタアドレスのＬＳＢ（ｋ−ｉ）ビット（図７参照）に対応するlineをＲＣクラスタ管理テーブル２３とＷＣクラスタ管理テーブル２５から選択し、選択したlineの各wayにエントリされている論理トラックアドレス２３ｂ、２５ｃをＬＢＡのトラックアドレスと比較し（ステップＳ１１０）、一致したwayが存在している場合は、キャッシュヒットとし、ヒットしたＲＣクラスタ管理テーブル２３またはＷＣクラスタ管理テーブル２５の該当line、該当wayに対応するＷＣ２１またはＲＣ２２のデータを読み出して、ＡＴＡコマンド処理部１２１に送る（ステップＳ１１５）。
【００８９】
データ管理部１２０は、ＲＣ２２またはＷＣ２１でヒットしなかった場合は（ステップＳ１１０）、検索対象のクラスタがＮＡＮＤメモリ１０のどこに格納されているかを検索する。データ管理部１２０は、まず、図１２に示したトラック管理テーブル３０を検索する（ステップＳ１２０）。トラック管理テーブル３０は、論理トラックアドレス３０ａでインデックスされているため、ＬＢＡで指定された論理トラックアドレスに一致する論理トラックアドレス３０ａのエントリだけをチェックする。
【００９０】
まず、チェックしたいＬＢＡの論理クラスタアドレスに基づいてクラスタビットマップ３０ｂから対応するビットを選択する。対応するビットが“０”を示していれば、そのクラスタは確実にＭＳ内に最新のデータが存在していることを意味する（ステップＳ１３０）。この場合は、このトラックが存在する論理ブロックＩＤおよびトラック位置を、同じ論理トラックアドレス３０ａのエントリ中の論理ブロックＩＤ３０ｃと論理ブロック内トラック位置３０ｄから得て、さらにＬＢＡのクラスタアドレスのＬＳＢ（ｋ−ｉ）ビットを利用して、トラック位置からのオフセットを算出することで、ＮＡＮＤメモリ１０内の当該クラスタアドレスに対応するクラスタデータが格納されている位置を算出することができる。具体的には、論理ＮＡＮＤ層管理部１２０ｂでは、上記のようにしてトラック管理テーブル３０から取得した論理ブロックＩＤ３０ｃと論理ブロック内トラック位置３０ｄと、ＬＢＡの論理クラスタアドレスのＬＳＢ（ｋ−ｉ）ビットを物理ＮＡＮＤ層管理部１２０ｃに与える。
【００９１】
物理ＮＡＮＤ層管理部１２０ｃでは、論理ブロックＩＤ３０ｃに対応する物理ブロックアドレス（物理ブロックＩＤ）を、論理ブロックＩＤをインデックスとしている図１７に示す論物変換テーブル５０から取得し（ステップＳ１６０）、さらに取得した物理ブロックＩＤ中のトラック位置（トラック先頭位置）を論理ブロック内トラック位置３０ｄから算出し、さらにＬＢＡのクラスタアドレスのＬＳＢ（ｋ−ｉ）ビットから、前記算出した物理ブロックＩＤ中のトラック先頭位置からのオフセットを算出することで、物理ブロック中のクラスタデータを取得することができる。ＮＡＮＤメモリ１０のＭＳ１１から取得されたクラスタデータは、ＲＣ２２を介してＡＴＡコマンド処理部１２１に送られる（ステップＳ１８０）。
【００９２】
一方、ＬＢＡのクラスタアドレスに基づくクラスタビットマップ３０ｂの検索で、対応するビットが“１”を示していた場合は、そのクラスタがＦＳ１２またはＩＳ１３に格納されている可能性がある（ステップＳ１３０）。この場合は、トラック管理テーブル３０の該当する論理トラックアドレス３０ａのエントリ中のクラスタテーブルポインタ３０ｅのエントリを取り出し、このポインタを用いてＦＳ／ＩＳ管理テーブル４０の該当する論理トラックアドレスに対応するリンクドリストを順次検索する（ステップＳ１４０）。具体的には、該当する論理トラックアドレスのリンクドリスト中のＬＢＡの論理クラスタアドレスに一致する論理クラスタアドレス４０ａのエントリを検索し、一致する論理クラスタアドレス４０ａのエントリが存在した場合は（ステップＳ１５０）、一致したリスト中の論理ブロックＩＤ４０ｂおよび論理ブロック内クラスタ位置４０ｃを取得し、前述と同様にして、論物変換テーブル５０を用いて物理ブロック中のクラスタデータを取得する（ステップＳ１６０、Ｓ１８０）。具体的には、取得した論理ブロックＩＤに対応する物理ブロックアドレス（物理ブロックＩＤ）を、論物変換テーブル５０から取得し（ステップＳ１６０）、さらに取得した物理ブロックＩＤ中のクラスタ位置を、論理ブロック内クラスタ位置４０ｃのエントリから取得した論理ブロック内クラスタ位置から算出することで、物理ブロック中のクラスタデータを取得することができる。ＮＡＮＤメモリ１０のＦＳ１２またはＩＳ１３から取得されたクラスタデータは、ＲＣ２２を介してＡＴＡコマンド処理部１２１に送られる（ステップＳ１８０）。
【００９３】
このＦＳ／ＩＳ管理テーブル４０の検索によって、検索対象のクラスタが存在しなかった場合は（ステップＳ１５０）、再度トラック管理テーブル３０のエントリを検索してＭＳ１１上の位置を確定する（ステップＳ１７０）。
【００９４】
・Write処理
つぎに、図１９に示すフローチャートを参照して、書き込み処理について説明する。ＦＵＡ（ＤＲＡＭキャッシュをバイパスしてＮＡＮＤへの直接書き込みを行う）でないWriteコマンドにより書き込まれたデータは必ず一旦ＷＣ２１上に格納され、その後条件に応じてＮＡＮＤメモリ１０に対して書き込まれることになる。書き込み処理では、追い出し処理、コンパクション処理が発生する可能性がある。この実施の形態では、書き込み処理を、ライトキャッシュフラッシュ処理（以下ＷＣＦ処理）と、クリーンインプットバッファ処理（以下ＣＩＢ処理）との２ステージに大きく分割している。ステップＳ３００からステップＳ３２０までは、ＡＴＡコマンド処理部１２１からのWrite要求からＷＣＦ処理までを示しており、ステップＳ３３０〜最終ステップまでがＣＩＢ処理を示している。
【００９５】
ＷＣＦ処理は、ＷＣ２１にあるデータをＮＡＮＤメモリ１０（ＦＳ１２のＦＳＩＢ１２ａまたはＭＳ１１のＭＳＩＢ１１ａ）にｃｏｐｙする処理であり、ＡＴＡコマンド処理部１２１からのWrite要求もしくはCache Flush要求単体は、この処理のみで完結することができる。これにより処理が開始されたＡＴＡコマンド処理部１２１のWrite要求の処理遅延を最大でもＷＣ２１の容量分のＮＡＮＤメモリ１０への書き込み時間に限定することができるようになる。
【００９６】
ＣＩＢ処理は、ＷＣＦ処理によって書き込まれたＦＳＩＢ１２ａのデータをＦＳ１２にＭｏｖｅする処理と、ＷＣＦ処理によって書き込まれたＭＳＩＢ１１ａのデータをＭＳ１１にＭｏｖｅする処理とを含む。ＣＩＢ処理を開始すると、連鎖的にＮＡＮＤメモリ１０内の各構成要素（ＦＳ１２、ＩＳ１３、ＭＳ１１など）間のデータ移動やコンパクション処理が発生する可能性があり、処理全体に要する時間は状態によって大きく変化する。
【００９７】
まず、ＷＣＦ処理の詳細について説明する。ＡＴＡコマンド処理部１２１から、Writeコマンドおよび書き込みアドレスとしてのＬＢＡが入力されると、ＤＲＡＭ層管理部１２０は、図１０に示したＷＣクラスタ管理テーブル２５を検索する（ステップＳ３００，Ｓ３０５）。ＷＣ２１の状態は、図１０に示したＷＣクラスタ管理テーブル２５の状態フラグ２５ａ（例えば３ビット）によって規定されている。状態フラグ２５ａは、最も典型的には、Invalid（使用可能）→ＡＴＡからの書き込み待ち→Valid（使用不可）→ＮＡＮＤへの追い出し待ち→Invalid（使用可能）という順に状態が遷移していく。まず、ＬＢＡのクラスタアドレスＬＳＢ（ｋ−ｉ）ビットから書き込み先のlineを決定し、決定したlineのｎ個のwayを検索する。決定したlineのｎ個のway中に、入力されたＬＢＡと同じ論理トラックアドレス２５ｃが格納されている場合は（ステップＳ３０５）、このエントリに上書きするのでこのエントリをクラスタ書き込み用に確保する（Valid（使用不可）→ＡＴＡからの書き込み待ち）。
【００９８】
そして、ＤＲＡＭ層管理部１２０ａは、該当エントリに対応するＤＲＡＭアドレスをＡＴＡコマンド処理部１２１に通知する。ＡＴＡコマンド処理部１２１による書き込みが終了すると、ＷＣクラスタ管理テーブル２５の該当エントリの状態フラグ２５ａをValid（使用不可）にし、さらにセクタ位置ビットマップ２５ｂおよび論理トラックアドレス２５ｃの欄に所要のデータを登録する。また、ＷＣトラック管理テーブル２４を更新する。具体的には、ＷＣトラック管理テーブル２４の各リスト中に既に登録済みの論理トラックアドレス２４ａと同じＬＢＡアドレスが入力された場合は、該当するリストのＷＣクラスタ数２４ｂ、way−lineビットマップ２４ｃを更新するとともに、当該リストが最新のリストとなるようにnextポインタ２４ｄを変更する。また、ＷＣトラック管理テーブル２４の各リスト中に登録済みの論理トラックアドレス２４ａと異なるＬＢＡアドレスが入力された場合は、新たに新しい論理トラックアドレス２４ａ、ＷＣクラスタ数２４ｂ、way−lineビットマップ２４ｃ、nextポインタ２４ｄの各エントリを有するリストを作成し、最新のリストとして登録する。以上のようなテーブル更新を行って、書き込み処理が完了する（ステップＳ３２０）。
【００９９】
一方、決定したlineのｎ個のway中に、入力されたＬＢＡと同じ論理トラックアドレス２５ｃが格納されていない場合は、ＮＡＮＤメモリへの追い出しが必要であるか否かを判断する（ステップＳ３０５）。すなわち、まず、決定したline中の書き込み可能なwayが最後のｎ個目のwayであるか否かを判断する。書き込み可能なwayとは、Invalid（使用可能）の状態フラグ２５ａをもつwayかあるいはValid（使用不可）でかつＮＡＮＤへの追い出し待ちの状態フラグ２５ａを持つwayである。状態フラグ２５ａが、ＮＡＮＤへの追い出し待ちであるとは、追い出しが開始されて追い出しの終了待ちであることを意味する。そして、書き込み可能なwayが最後のｎ個目のwayでない場合であって、かつ書き込み可能なwayが、Invalid（使用可能）の状態フラグ２５ａをもつwayである場合は、このエントリをクラスタ書き込み用に確保する（Invalid（使用可能）→ＡＴＡからの書き込み待ち）。そして、該当エントリに対応するＤＲＡＭアドレスをＡＴＡコマンド処理部１２１に通知し、ＡＴＡコマンド処理部１２１によって書き込みを実行させる。そして、前記同様、ＷＣクラスタ管理テーブル２５およびＷＣトラック管理テーブル２４を更新する（ステップＳ３２０）。
【０１００】
また、書き込み可能なwayが最後のｎ個目のwayでない場合であって、かつ書き込み可能なwayが、Valid（使用不可）でかつＮＡＮＤへの追い出し待ちの状態フラグ２５ａを持つwayである場合は、このエントリをクラスタ書き込み用に確保する（Valid（使用不可）でかつＮＡＮＤへの追い出し待ち→Valid（使用不可）でかつＮＡＮＤへの追い出し待ちかつＡＴＡからの書き込み待ち）。そして、追い出しが終了すると、状態フラグ２５ａをＡＴＡからの書き込み待ちにし、さらに、該当エントリに対応するＤＲＡＭアドレスをＡＴＡコマンド処理部１２１に通知し、ＡＴＡコマンド処理部１２１によって書き込みを実行させる。そして、前記同様、ＷＣクラスタ管理テーブル２５およびＷＣトラック管理テーブル２４を更新する（ステップＳ３２０）。
【０１０１】
以上の処理は、ＡＴＡコマンド処理部１２１からからの書き込み要求が入力された際に、追い出し処理をトリガしなくてもよい場合である。一方、この後の説明は、書き込み要求が入力された時点後に、追い出し処理をトリガする場合である。ステップＳ３０５において、決定したline中の書き込み可能なwayが最後のｎ個目のwayである場合は、前述したＷＣ２１からＮＡＮＤメモリ１０へ追い出すデータの決定方法の（i）の箇所で説明した条件、すなわち、
（i）  タグによって決定されたlineの書き込み可能なwayが最後の(本実施形態では、ｎ個目の)空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうちＬＲＵに基づいて最も古く更新されたトラックを追い出し確定する、
に基づいて追い出すトラックすなわちＷＣ２１内エントリを選択する。
【０１０２】
ＤＲＡＭ層管理部１２０ａは、以上の方針で追い出すトラックを決定すると、前述したように、その際追い出すのは同一トラックに含まれるＷＣ２１中の全クラスタであり、追い出されるクラスタ量がトラックサイズの５０％を超えていれば、すなわち追い出し確定トラックのうちＷＣ中に有効クラスタ数が２（ｋ−ｉ−１）個以上ある場合は、ＭＳＩＢ１１ａへ追い出しを行い（ステップＳ３１０）、超えていなければ、すなわち追い出し確定トラックのうちＷＣ中に有効クラスタ数が２（ｋ−ｉ−１）個未満である場合は、ＦＳＩＢ１２ａへと追い出す（ステップＳ３１５）。ＷＣ２１からＭＳＩＢ１１ａへの追い出し、ＷＣ２１からＦＳＩＢ１２ａへの追い出しの詳細は、後述する。選択された追い出しエントリの状態フラグ２５ａは、Valid（使用不可）からＮＡＮＤメモリ１０への追い出し待ちに移行される。
【０１０３】
この追い出し先の判定は、ＷＣトラック管理テーブル２４を用いて実行される。すなわち、ＷＣトラック管理テーブル２４には、論理トラックアドレス毎に、有効なクラスタ数を示すＷＣクラスタ数２４ｂのエントリが登録されており、このＷＣクラスタ数２４ｂのエントリを参照することでＷＣ２１からの追い出し先を、ＦＳＩＢ１２ａ、ＭＳＩＢ１１ａの何れにするかを決定する。また、way−lineビットマップ２４ｃに、当該論理トラックアドレスに所属する全てのクラスタがビットマップ形式で登録されているので、追い出しを行う際には、このway−lineビットマップ２４ｃを参照することで、容易に、追い出すべき各クラスタのＷＣ２１での記憶位置を知ることができる。
【０１０４】
また、上記書き込み処理中または書き込み処理後、前述の下記条件、
（ii）ＷＣ２１に登録されているトラックの数が所定数を超えた場合、
が成立した場合も、上記同様にしてＮＡＮＤメモリ１０への追い出し処理を実行する。
【０１０５】
ＷＣ→ＭＳＩＢ（Ｃｏｐｙ）
つぎに、上記有効クラスタ数（有効クラスタ数が２（ｋ−ｉ−１）個以上）に基づく判定によりＷＣ２１からＭＳＩＢ１１ａへの追い出しが発生したときは、前述したように、次のような手順を実行する（ステップＳ３１０）。
１.ＷＣクラスタ管理テーブル２５を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ２５ｂを参照し、セクタ位置ビットマップ２５ｂが全て“１”でない場合は、ＮＡＮＤメモリ１０に含まれる同一クラスタ中のセクタとマージする、後述のクラスタ内セクタ穴埋めを行う。また、トラック中のＷＣ２１内に存在しないクラスタについてはＮＡＮＤメモリ１０から読み出してマージする、受動マージ処理を実行する。
２．追い出し確定トラックが２ｉ個未満の場合、ＷＣ２１中のトラックの古いものから２ｉ個になるまで２（ｋ−ｉ−１）個以上有効クラスタを持つ追い出し確定トラックを追加する。
３．Ｃｏｐｙされるトラックが２ｉ個以上あれば、２ｉ個ずつを組として、ＭＳＩＢ１１ａに対して論理ブロック単位に書き込みを行う。
４．２ｉ個組みに出来なかったトラックをＭＳＩＢ１１ａに対してトラック単位に書き込みを行う。
５．Ｃｏｐｙ終了後に既にＦＳ、ＩＳ、ＭＳ上に存在していたクラスタ、トラックのうちコピーされたトラックに属するものを無効化する。
【０１０６】
このようなＷＣ２１からＭＳＩＢ１１ａへのＣｏｐｙ処理に伴う各管理テーブルの更新処理について説明する。ＷＣクラスタ管理テーブル２５中の追い出されたトラックに所属するＷＣ２１中の全クラスタに対応するエントリ中の状態フラグ２５ａはInvalidとされ、この後これらエントリに対する書き込みが可能となる。また、ＷＣトラック管理テーブル２４中の追い出されたトラックに対応するリストについては、例えば直前のリストのnextポインタ２４ｄが変更または削除されて、無効化される。
【０１０７】
一方、ＷＣ２１からＭＳＩＢ１１ａに対するトラック移動が発生すると、これに伴いトラック管理テーブル３０およびＭＳ論理ブロック管理テーブル３５が更新される。まず、トラック管理テーブル３０のインデックスである論理トラックアドレス３０ａを検索することで、移動されたトラックに対応する論理トラックアドレス３０ａが既に登録されているか否かを判定する。既に登録されている場合は、該当インデックスのクラスタビットマップ３０ｂ（ＭＳ１１側への移動であるので、該当ビットを全て“０”にする）、論理ブロックＩＤ３０ｃ＋論理ブロック内トラック位置３０ｄのフィールドを更新する。移動されたトラックに対応する論理トラックアドレス３０ａが未登録の場合は、該当する論理トラックアドレス３０ａのエントリに対し、クラスタビットマップ３０ｂ、論理ブロックＩＤ３０ｃ＋論理ブロック内トラック位置３０ｄを登録する。また、トラック管理テーブル３０の変更に応じて、ＭＳ論理ブロック管理テーブル３５における、論理ブロックＩＤ３５ａ、該当トラック管理ポインタ３５ｂ、有効トラック数３５ｃ、書き込み可能先頭トラック３５ｄなどのエントリを必要に応じて更新する。
【０１０８】
なお、他の領域（ＦＳ１２やＩＳ１３）等からＭＳ１１に対してトラック書き込みが発生した場合、もしくはＭＳ１１内部のコンパクション処理によるＭＳ内トラック書き込みが発生した場合、書き込み対象のトラックに含まれるＷＣ２１内有効クラスタも同時にＭＳに書き込まれる。ＷＣ２１からＭＳ１１への書き込みとしてこのような受動的マージも存在する。そのような受動的マージが行われた場合は、それらのクラスタはＷＣ２１上から削除（無効化）されることになる。
【０１０９】
ＷＣ→ＦＳＩＢ（Ｃｏｐｙ）
つぎに、上記有効クラスタ数（有効クラスタ数が２（ｋ−ｉ−１）個未満）に基づく判定によりＷＣ２１からＦＳＩＢ１２ａへの追い出しが発生したときは、前述したように、次のような手順を実行する。
１．ＷＣクラスタ管理テーブル２５における追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ２５ｂを参照し、セクタ位置ビットマップ２５ｂが全て“１”でない場合は、ＮＡＮＤメモリ１０に含まれる同一クラスタ中のセクタとマージする、クラスタ内セクタ穴埋めを行う。
２．ＷＣ内のトラックを古い順に辿って２（ｋ−ｉ−１）個未満の有効クラスタしか持たないトラックからクラスタを取り出して行き、有効クラスタ数が２ｋ個になったらそれら全クラスタをＦＳＩＢ１２ａに論理ブロック単位に書き込む。
３．２ｋ個見つからなかった場合には、有効クラスタ数が２（ｋ−ｉ−１）個未満の全てのトラックを必要な論理ページ数分だけＦＳＩＢ１２ａに書き込む。
４．Ｃｏｐｙ終了後に既にＦＳ、ＩＳ上に存在していたクラスタのうちコピーされたのと同じものを無効化する。
【０１１０】
このようなＷＣ２１からＦＳＩＢ１２ａへのＣｏｐｙ処理に伴う各管理テーブルの更新処理について説明する。ＷＣクラスタ管理テーブル２５中の追い出されたトラックに所属するＷＣ２１中の全クラスタに対応するエントリ中の状態フラグ２５ａはInvalidとされ、この後これらエントリに対する書き込みが可能となる。また、ＷＣトラック管理テーブル２４中の追い出されたトラックに対応するリストについては、例えば直前のリストのnextポインタ２４ｄが変更または削除されて、無効化される。一方、ＷＣ２１からＦＳＩＢ１２ａに対するクラスタ移動が発生すると、これに伴いトラック管理テーブル３０のクラスタテーブルポインタ３０ｅ、ＦＳクラスタ数３０ｆなどを更新するとともに、ＦＳ／ＩＳ管理テーブル４０の論理ブロックＩＤ４０ｂ、論理ブロック内クラスタ位置４０ｃなどを更新する。なお、もともとＦＳ１２に存在していなかったクラスタについては、ＦＳ／ＩＳ管理テーブル４０のリンクドリストへのリストが追加される。この更新に伴い、ＭＳ論理ブロック管理テーブル３５、ＦＳ／ＩＳ論理ブロック管理テーブル４２、およびＦＳ／ＩＳ内クラスタ管理テーブル４４の該当個所を更新する。
【０１１１】
ＣＩＢ処理
上記のようなＷＣＦ処理が終了すると、つぎに、論理ＮＡＮＤ層管理部１２０ｂは、ＷＣＦ処理によって書き込まれたＦＳＩＢ１２ａのデータをＦＳ１２にＭｏｖｅする処理と、ＷＣＦ処理によって書き込まれたＭＳＩＢ１１ａのデータをＭＳ１１にＭｏｖｅする処理などを含むＣＩＢ処理を実行する。ＣＩＢ処理を開始すると、前述したように、連鎖的に各ブロック間のデータ移動やコンパクション処理が発生する可能性があり、処理全体に要する時間は状態によって大きく変化する。このＣＩＢ処理においては、基本的には、先ずＭＳ１１でのＣＩＢ処理が行われ（ステップＳ３３０）、つぎに、ＦＳ１２でのＣＩＢ処理が行われ（ステップＳ３４０）、つぎに再びＭＳ１１でのＣＩＢ処理が行われ（ステップＳ３５０）、つぎにＩＳ１３でのＣＩＢ処理が行われ（ステップＳ３６０）、最後に再びＭＳ１１でのＣＩＢ処理が行われる（ステップＳ３７０）。なお、ＦＳ１２からＭＳＩＢ１１ａへの追い出し処理、あるいはＦＳ１２からＩＳ１３への追い出し処理、あるいはＩＳ１３からＭＳＩＢ１１ａへの追い出し処理の際に、手順にループが発生した場合は、上記順番通りにならない場合もある。ＭＳ１１、ＦＳ１２およびＩＳ１３でのＣＩＢ処理を別々に説明する。
【０１１２】
ＭＳ１１のＣＩＢ処理
まず、ＭＳ１１でのＣＩＢ処理について説明する（ステップＳ３３０）。ＷＣ２１、ＦＳ１２、ＩＳ１３からＭＳ１１に対してトラックデータの移動が発生すると、そのトラックデータはＭＳＩＢ１１ａに書き込まれる。ＭＳＩＢ１１ａへの書き込み完了後は、前述したように、トラック管理テーブル３０を更新してトラックが配置される論理ブロックＩＤ３０ｃとブロック内トラック位置３０ｄなどを変更する（Ｍｏｖｅ）。ＭＳＩＢ１１ａに新たなトラックデータが書き込まれた場合、もともとＭＳ１１もしくはＴＦＳ１１ｂに存在していたトラックデータは無効化される。この無効化処理は、ＭＳ論理ブロック管理テーブル３５における古いトラック情報が保存されていた論理ブロックのエントリからトラックを無効化することで実現する。具体的には、ＭＳ論理ブロック管理テーブル３５の該当エントリ中のトラック管理ポインタ３５ｂのフィールド中の該当トラックのポインタが削除され、有効トラック数が−１される。このトラック無効化によって１論理ブロック中の全てのトラックが無効になった場合は、Validフラグ３５ｅが無効化される。このような無効化などにより、ＭＳ１１のブロックは無効なトラックを含んだものが発生し、これが繰り返されるとブロックの利用効率が低下して、使用可能な論理ブロックに不足が生じることがある。
【０１１３】
データ管理部１２０は、このような事態が発生して、ＭＳ１１に割り当てられている論理ブロックの個数がＭＳ１１として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックＦＢを作る。無効なフリーブロックＦＢは、物理ＮＡＮＤ層管理部１２０ｃに返却される。そして、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ１１に割り当てられている論理ブロックの個数を減らした後、新たに書き込み可能なフリーブロックＦＢを物理ＮＡＮＤ層管理部１２０ｃから取得する。コンパクション処理とは、コンパクション対象の論理ブロックが持つ有効クラスタを新しい論理ブロックに集めたり、あるいはコンパクション対象の論理ブロック中の有効トラックを他の論理ブロックにＣｏｐｙしたりすることで、物理ＮＡＮＤ層管理部１２０ｃに返却する無効なフリーブロックＦＢを作り、論理ブロックの利用効率を向上させるための処理である。なお、コンパクションを行う際には、コンパクション対象となったトラック領域に対して、ＷＣ、ＦＳ、ＩＳ上の有効なクラスタが存在する場合、それらを全てマージする受動マージを実行する。また、ＴＦＳ１１ｂに登録されている論理ブロックについては、コンパクション対象に含めない。
【０１１４】
以下に、ＭＳＩＢ１１ａにフルに成ったブロックが存在する場合を発生条件とした、ＭＳＩＢ１１ａからＭＳ１１またはＴＦＳ１１ｂへの追い出しとコンパクション処理の一例について具体的に説明する。
１．ＭＳ論理ブロック管理テーブル３５のValidフラグ３５ｅを参照することにより、ＭＳ１１内に無効となった論理ブロックが存在する場合、そのブロックを無効なフリーブロックＦＢとする。
２．ＭＳＩＢ１１ａでフルに成った論理ブロックをＭＳ１１に追い出す。具体的には、前述したＭＳ構造管理テーブル（図示せず）を更新して、該当論理ブロックをＭＳＩＢ管理下からＭＳ管理下に移し変える。
３．ＭＳ１１に割り当てられている論理ブロックの個数がＭＳ１１として許容されるブロック数の上限値を越えるような状況が発生するか否かを判断し、発生している場合に、以下のＭＳコンパクションを実行する。
４．ＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドなどを参照することにより、ＴＦＳ１１ｂに含まれない論理ブロックのうち無効にされたトラックを持つものを、有効トラック数でソートする。
５．有効トラック数の少ない論理ブロックから、トラックを集めてコンパクションを実施する。この際にまず、１論理ブロック分（２ｉトラック）ずつＣｏｐｙしてコンパクションを実施する。なお、コンパクション対象のトラックがＷＣ２１、ＦＳ１２、ＩＳ１３に有効クラスタを持つ場合にはそれらもマージする。
６．コンパクション元の論理ブロックを無効なフリーブロックＦＢとする。
７．コンパクションして有効な２ｉトラックで構成された１論理ブロックができたら、ＴＦＳ１１ｂの先頭にＭｏｖｅする。
８．論理ブロック内の有効トラックを他の論理ブロックにＣｏｐｙして、無効なフリーブロックＦＢが作れる場合は、２ｉトラック未満の個数の有効トラックをＭＳＩＢ１１ａに対し、トラック単位で追記書き込みする。
９．コンパクション元の論理ブロックを無効なフリーブロックＦＢとする。
１０．ＭＳ１１に割り当てられている論理ブロックの個数がＭＳ１１として許容されるブロック数の上限値を下回ると、ＭＳコンパクション処理を終了する。
【０１１５】
ＦＳ１２のＣＩＢ処理
つぎに、ＦＳ１２でのＣＩＢ処理について説明する（ステップＳ３４０）。ＷＣ２１からＦＳＩＢ１２ａへのクラスタ書き込み処理によって全ページ書き込み済みの論理ブロックがＦＳＩＢ１２ａ中に作られた場合、ＦＳＩＢ１２ａ中のそれらのブロックは、ＦＳＩＢ１２ａからＦＳ１２に対してＭｏｖｅされる。このＭｏｖｅにともなって複数の論理ブロックで構成されるＦＩＦＯ構造のＦＳ１２から古い論理ブロックが追い出される状況が発生する。
【０１１６】
ＦＳＩＢ１２ａからＦＳ１２に対する追い出しおよびＦＳ１２からのブロック追い出しは、具体的には、次のように実現される。
１．ＦＳ／ＩＳ論理ブロック管理テーブル４２のValidフラグ３５ｅなどを参照することにより、ＦＳ１２内に無効となった論理ブロックが存在する場合、そのブロックを無効なフリーブロックＦＢとする。
２．ＦＳＩＢ１２ａでフルに成ったブロックをＦＳ１２に追い出す。具体的には、前述したＦＳ／ＩＳ構造管理テーブル（図示せず）を更新して、該当ブロックをＦＳＩＢ管理下からＦＳ管理下に移し変える。
３．ＦＳ１２に割り当てられている論理ブロックの個数がＦＳ１２として許容されるブロック数の上限値を越えるような状況が発生するか否かを判断し、発生している場合に、以下の追い出しを実行する。
４．まず追い出し対象の最古の論理ブロック中のクラスタデータのうちＩＳ１３に移動せずに、直接ＭＳ１１に移動すべきものを決定する（実際には、ＭＳの管理単位がトラックであるので、トラック単位での決定）。
（ア）追い出し対象の論理ブロック中の有効クラスタをページの先頭から順にスキャンする。
（イ）クラスタが属するトラックがＦＳ中に何個の有効クラスタを保有しているか、トラック管理テーブル３０のＦＳクラスタ数３０ｆのフィールドを参照して検索する。
（ウ）トラック内有効クラスタ数が所定の閾値（例えば２ｋ−ｉ個の５０％）以上だった場合、そのトラックをＭＳへの追い出し候補とする。
５．ＭＳ１１に追い出すべきトラックをＭＳＩＢ１１ａに対して書き込む。
６．追い出しトラックが残っている場合、さらにＭＳＩＢ１１への追い出しを実行する。
７．上記２〜４の処理の後も追い出し対象の論理ブロックに有効なクラスタが存在している場合、この論理ブロックをＩＳ１３にＭｏｖｅする。
なお、ＦＳ１２からＭＳＩＢ１１ａへの追い出しが発生したときには、その直後、ＭＳ１１での前述したＣＩＢ処理が実行される（ステップＳ３５０）。
【０１１７】
ＩＳ１３のＣＩＢ処理
つぎに、ＩＳ１３でのＣＩＢ処理について説明する（ステップＳ３６０）。上記したＦＳ１２からＩＳ１３へのブロック移動によって論理ブロックがＩＳ１３に追加されるが、これにともなって複数個の論理ブロックで構成されるＩＳ１３に対して管理可能なブロック数の上限を超えてしまう状況が発生する。このような状況が発生した場合、ＩＳ１３では、まずＭＳ１１への１〜複数個の論理ブロックの追い出しを行った後、ＩＳコンパクションを実行する。具体的には、次のような手順を実行する。
１．ＩＳ１３に含まれるトラックをトラック内の有効クラスタ数×有効クラスタ係数でソートし、積の値が大きいトラック２ｉ＋１個(２論理ブロック分)を集めてＭＳＩＢ１１ａに追い出す。
２．有効クラスタ数が最も少ない２ｉ＋１個の論理ブロックの合計有効クラスタ数が例えば、所定の設定値である２ｋ個（１論理ブロック分）以上ある場合は、上のステップを繰り返す。
３．上記の追い出しを行った後、有効クラスタ数の少ない論理ブロックから順にクラスタを２ｋ個集め、ＩＳ１３内でコンパクションを行う。
４．コンパクション元の論理ブロックのうち有効クラスタがなくなったものを無効なフリーブロックＦＢとして返還する。
なお、ＩＳ１３からＭＳＩＢ１１ａへの追い出しが発生したときには、その直後、ＭＳ１１での前述したＣＩＢ処理が実行される（ステップＳ３７０）。
【０１１８】
図２０は、各構成要素間のデータの流れにおける入力と出力の組み合わせ、およびそのデータの流れが何をトリガとして発生するかを示すものである。ＦＳ１２は、基本的には、ＷＣ２１からのクラスタ追い出しによってデータが書き込まれるが、ＷＣ２１からＦＳ１２への追い出しに付随してクラスタ内セクタ穴埋め（クラスタ穴埋め）が必要な場合は、ＦＳ１２、ＩＳ１３、ＭＳ１１からのデータがコピーされる。ＷＣ２１では、ＷＣクラスタ管理テーブル２５のタグ中のセクタ位置ビットマップ２５ｂによって当該クラスタアドレス中の２（ｌ−ｋ）個のセクタの有無を識別させることによってセクタ（５１２Ｂ）単位の管理をすることが可能である。これに対し、ＮＡＮＤメモリ１０での機能要素であるＦＳ１２、ＩＳ１３の管理単位はクラスタであり、ＭＳ１１の管理単位は、トラックである。このように、ＮＡＮＤメモリ１０での管理単位は、セクタより大きいため、ＷＣ２１からＮＡＮＤメモリ１０に対して、データを書き込む際に、書き込まれるデータと同一クラスタアドレスのデータがＮＡＮＤメモリ１０中に存在する場合、ＷＣ２１からＮＡＮＤメモリ１０に書き込まれるクラスタ中のセクタと、ＮＡＮＤメモリ１０中に存在する同一クラスタアドレス内のセクタとをマージしてから、ＮＡＮＤメモリ１０に書き込む必要がある。
【０１１９】
この処理が、図２０に示したクラスタ内セクタ穴埋め処理（クラスタ穴埋め）と、トラック内セクタ穴埋め（トラック穴埋め）であり、これらの処理を行わないと、正しいデータが読み出せなくなる。そこで、ＷＣ２１からＦＳＩＢ１２ａまたはＭＳＩＢ１１ａにデータを追い出す際には、ＷＣクラスタ管理テーブル２５を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ２５ｂを参照し、セクタ位置ビットマップ２５ｂが全て“１”でない場合は、ＮＡＮＤメモリ１０に含まれる同一クラスタまたは同一トラック中のセクタとマージする、クラスタ内セクタ穴埋めまたはトラック内セクタ穴埋めを行う。この処理には、ＤＲＡＭ２０の作業領域が使用され、ＤＲＡＭ２０の作業領域からＭＳＩＢ１１ａに書き込まれたり、ＦＳＩＢ１２ａに書き込まれたりする。
【０１２０】
ＩＳ１３は、基本的には、ＦＳ１２からのブロック追い出しによってデータが書き込まれる（Ｍｏｖｅ）か、ＩＳ内部のコンパクションによってデータが書き込まれる。ＭＳ１１は、全ての箇所からデータが書き込まれ得る。その際、ＭＳ１１は、トラック単位にしかデータを書き込めないために、ＭＳ自身のデータによる穴埋めが発生しうる。また、トラック単位の書き込みを行う際には、他のブロックにある断片化されたデータも受動マージによって書き込まれることになる。さらにＭＳ１１は、ＭＳコンパクションによる書き込みもある。なお、受動マージにおいては、ＷＣ２１、ＦＳ１２またはＩＳ１３の３つの構成要素のうちの１つの構成要素からＭＳ１１へのトラック追い出しまたは論理ブロック追い出し（２ｉトラック分の追い出し）が発生した際、１つの構成要素での追い出し対象のトラック（または論理ブロック）に含まれる他の２つの構成要素内の有効クラスタおよびＭＳ１１内の有効クラスタが、ＤＲＡＭ２０の作業領域に集められて、ＤＲＡＭ２０の作業領域から１トラック分のデータとしてＭＳＩＢ１１ａに書き込まれる。
【０１２１】
つぎに、本実施の形態の要部について説明する。前述したように、ＷＣ２１の管理には、図１０に示したＷＣクラスタ管理テーブル２５と、図１１に示したＷＣトラック管理テーブル２４が使用される。ＷＣクラスタ管理テーブル２５は、前述したように、セットアソシアティブ方式でＷＣ２１の各エントリのタグをクラスタ単位に管理するためのテーブルであり、各タグに、通常の論理トラックアドレス２５ｃの他に、複数ビットの状態フラグ２５ａと、セクタ位置ビットマップ２５ｂとを追加している。
【０１２２】
また、ＷＣトラック管理テーブル２４は、前述したように、ＷＣ２１上に格納されているクラスタをトラック単位でまとめた情報を管理するものであり、ＦＩＦＯ的な機能を有するリンクドリスト構造によって論理トラックアドレス間のＷＣ２１に登録された順序（ＬＲＵ）を表現しており、各エントリには、当該論理トラックアドレスに含まれるＷＣ２１中の有効クラスタ数を示すＷＣクラスタ数２４ｂと、ＷＣ２１中で当該論理トラックアドレスに含まれる有効クラスタがＷＣ２１中のｍ×ｎのエントリ中のどのエントリに格納されているか示すWay-lineビットマップ２４ｃおよび次の論理トラックアドレスの位置を示すnextポインタ２４ｄとが含まれる。
【０１２３】
ＷＣ２１への書き込み処理が終了すると、ＷＣトラック管理テーブル２４においては、前述したように、該当する論理トラックアドレス２４ａ、ＷＣクラスタ数、way−lineビットマップ２４ｃなどがデータ管理部１２０の論理ＮＡＮＤ層１２０ｂによって更新されると共に、論理トラックアドレス間のＷＣ２１に登録された順序がリンクドリストのＦＩＦＯ構造によって変更される。
【０１２４】
ＷＣ２１への書き込みの際、前述した（ｉ）の条件、すなわち最後の空きwayが使用されるという条件が成立した場合は、ＬＲＵ順にリンクしているＷＣトラック管理テーブル２４を検索することで、該当lineに登録されたトラックのうち、最も古く更新されたトラックを追い出し確定するが、この追い出しの際、追い出しを確定した同一トラックに含まれる全てのＷＣ２１内のクラスタを追い出し確定とする。ＷＣトラック管理テーブル２４のway−lineビットマップ２４ｃには、当該論理トラックアドレスに所属する全てのクラスタがビットマップ形式で登録されているので、このway−lineビットマップ２４ｃを参照することで、容易に、追い出すべき各クラスタのＷＣ２１での記憶位置を知ることができ、追い出し処理を高速化することができる。
【０１２５】
また、ＷＲコマンド処理中に、前述した（ｉｉ）の条件、すなわちＷＣ２１に登録されているトラックの数（異なる論理トラックアドレスの個数）が所定数を超えるという条件が成立した場合は、ＬＲＵ順で、当該トラックに属するＷＣ中のクラスタ数が所定数未満のトラックの追い出しを確定するようにしているが、（ｉｉ）の条件は、ＷＣトラック管理テーブル２４に登録されたリストの個数、則ちＷＣ２１に登録されている論理トラックアドレス２４ａの個数を計数することで、簡単に導出することができる。また、（ｉｉ）の条件が成立した場合にも、追い出しを確定した同一トラックに含まれる全てのＷＣ２１内のクラスタを追い出し確定とするが、この追い出しの際にも、このway−lineビットマップ２４ｃを参照することで、容易に、追い出すべき各クラスタのＷＣ２１での記憶位置を知ることができ、追い出し処理を高速化することができる。さらに、当該トラックに属するＷＣ中のクラスタ数が所定数未満のトラックを検索する際には、ＷＣトラック管理テーブル２４のＷＣクラスタ数２４ｂのフィールドを参照することで、容易かつ高速に該当トラックを決定することができる。
【０１２６】
追い出し処理がトリガされると、前述したように、その際追い出すのは同一トラックに含まれるＷＣ２１中の全クラスタであり、追い出されるクラスタ量がトラックサイズの５０％を超えていればＭＳ１１のＭＳＩＢ１１ａへ、超えていなければＦＳ１２のＦＳＩＢ１２ａへと追い出す。この追い出し先の判定にも、ＷＣトラック管理テーブル２４のＷＣクラスタ数２４ｂのフィールドを参照することでＷＣ２１からの追い出し先を、ＦＳＩＢ１２ａ、ＭＳＩＢ１１ａの何れにするかを容易に即座に決定することができ、追い出し処理を高速することができる。
【０１２７】
このように本実施の形態においては、ＷＣトラック管理テーブル２４によって、論理トラックアドレス間のＷＣ２１に登録された時間的順序、論理トラックアドレス内の有効クラスタ数、論理トラックアドレスに所属する各クラスタのＷＣ２１での記憶位置などを含む論理トラックアドレス毎の情報の管理を行うようにしているので、ＷＣ２１での書き込み処理、追い出し処理を高速化することができ、またＷＣ２１の管理テーブルのためのメモリ量を削減することができる。
【０１２８】
また、本実施の形態においては、ＷＲコマンド処理中に、最後の空きwayが使用された場合に、ＷＣ２１での追い出しを行うようにしているので、wayが満杯になる前に追い出しが行われることになり、これにより書き込み処理の待ち時間が極端に長くなる状態がなくなり、書き込み処理の高速化に寄与する。
【０１２９】
また、本実施の形態においては、ｎwayのセットアソシアティブのキャッシュ構成において、ＷＣ２１に登録されている論理トラックの数が所定数を超えた場合に、ＷＣでの追い出しを行うようにしているので、登録される論理トラック数が増加して追い出し処理に時間がかかるようになる前に追い出しが行われることになり、これにより書き込み処理の待ち時間が極端に長くなる状態がなくなり、書き込み処理の高速化に寄与する。
【符号の説明】
【０１３０】
１０  ＮＡＮＤメモリ、２１  ＷＣ（ライトキャッシュ）、２４  ＷＣトラック管理テーブル、２５  ＷＣクラスタ管理テーブル、３０  トラック管理テーブル、４０  ＦＳ/ＩＳ管理テーブル、１２０  データ管理部、１２０ａ  ＤＲＡＭ層管理部。
【図１】
2011103144.tif 000003
【図２】
2011103144.tif 000004
【図３】
2011103144.tif 000005
【図４】
2011103144.tif 000006
【図５】
2011103144.tif 000007
【図６】
2011103144.tif 000008
【図７】
2011103144.tif 000009
【図８】
2011103144.tif 000010
【図９】
2011103144.tif 000011
【図１０】
2011103144.tif 000012
【図１１】
2011103144.tif 000013
【図１２】
2011103144.tif 000014
【図１３】
2011103144.tif 000015
【図１４】
2011103144.tif 000016
【図１５】
2011103144.tif 000017
【図１６】
2011103144.tif 000018
【図１７】
2011103144.tif 000019
【図１８】
2011103144.tif 000020
【図１９】
2011103144.tif 000021
【図２０】
2011103144.tif 000022