JP4675985B2 - メモリシステム - Google Patents

Description

本発明は、不揮発性半導体メモリを備えたメモリシステムに関する。

コンピュータシステムに用いられる外部記憶装置として、ＮＡＮＤ型フラッシュメモリなどの不揮発性半導体メモリを搭載したＳＳＤ（Solid State Drive）が注目されている。フラッシュメモリは、磁気ディスク装置に比べ、高速、軽量などの利点を有している。

ＳＳＤ内には、複数のフラッシュメモリチップ、ホスト装置からの要求に応じて各フラッシュメモリチップのリード/ライト制御を行うコントローラ、各フラッシュメモリチップとホスト装置との間でデータ転送を行うためのバッファメモリ、電源回路、ホスト装置に対する接続インタフェースなどを備えている（例えば、特許文献１）。

不揮発性半導体メモリには、ＮＡＮＤ型フラッシュメモリのように、データを記憶させる場合にブロック単位で一度データを消去してからその後に書き込みを行うもの、ページ単位で書き込み／読み出しを行うものなど、消去／書き込み／読み出しの単位が固定されているものがある。

一方、パーソナルコンピュータなどのホスト機器がハードディスクをはじめとする２次記憶装置に対してデータの書き込み／読み出しを行う単位は、セクタと呼ばれる。セクタは、半導体記憶装置の消去／書き込み／読み出しの単位とは独立に定められる。

例えば、不揮発性半導体メモリのブロックの大きさ（ブロックサイズ）は、５１２ｋＢ、ページの大きさ（ページサイズ）は、４ｋＢであるのに対して、ホスト機器のセクタの大きさ（セクタサイズ）は、５１２Ｂのように定められている。

このように、不揮発性半導体メモリの消去／書き込み／読み出しの単位は、ホスト機器の書き込み／読み出しの単位よりも大きい場合がある。

そこで、不揮発性半導体メモリを用いてハードディスクのようなパーソナルコンピュータの２次記憶装置を構成する場合、ホスト機器としてのパーソナルコンピュータからの小さなサイズのデータは、不揮発性半導体メモリのブロックサイズ、ページサイズに適合させて書き込みを行う必要がある。

また、パーソナルコンピュータなどのホスト機器が記録するデータは、時間的局所性、及び領域的局所性を兼ね備えている（例えば、非特許文献１参照。）。そのため、データを記録する際に外部から指定されたアドレスにそのまま記録していくと、特定の領域に短時間に書き換え、すなわち消去処理が集中し、消去回数の偏りが大きくなる。そのため、ＮＡＮＤ型フラッシュメモリでは、データ更新箇所を均等に分散させるウェアレベリングと呼ばれる処理が行われる。

ウェアレベリング処理では、例えば、ホスト機器から指定される論理アドレスを、データ更新箇所が均等に分散された不揮発性半導体メモリの物理アドレスにアドレス変換している。

ＮＡＮＤ型フラッシュメモリを用いて大容量の２次記憶装置を構成する場合においては、上記アドレス変換を行う場合に、データ管理の単位が小さいサイズ（例えば、ページサイズ）であると、管理テーブルのサイズが大きくなって、２次記憶装置のコントローラの主記憶メモリに納まらなくなり、アドレス変換が高速にできなくなるという問題がある。このように、２次記憶装置としてのＮＡＮＤ型フラッシュメモリの大容量化に伴い管理テーブルのサイズは必然的に大きくなるため、管理テーブルをできるだけ小容量にするための手法が求められている。

また、上述したように、データの消去単位（ブロック）と、データの管理単位が異なる場合、フラッシュメモリの書き換えが進むと、無効な（最新ではない）データによって、ブロックは穴あき状態になる。このような穴あき状態のブロックが増えると、実質的に使用可能なブロックが少なくなり、フラッシュメモリの記憶領域を有効利用できない。これに対応して、有効な最新のデータを集めて、違うブロックに書き直すコンパクションと呼ばれる処理が行われることがある（例えば、特許文献２参照。）。このコンパクション処理においては、その手法によっては処理時間が長くなるので、コンパクションの処理時間を短くするための手法が求められている。

特許第３６８８８３５号公報 特開２００５−２２２５５０号公報 David A. Patterson and John L. Hennessy, "Computer Organization and Design: The Hardware/Software Interface", Morgan Kaufmann Pub, 2004/8/31

本発明は、コンパクションの処理時間を短縮化することが可能なメモリシステムを提供する。

本願発明の一態様に係るメモリシステムは、データ消去単位であるブロックを複数有する不揮発性の半導体記憶素子と、前記ブロック内の有効なデータを前記ブロックのサイズよりも小さい所定の管理単位で選択して、異なるブロック内に書き直すコンパクション処理を実行するコントローラと、を具備し、前記コントローラは、前記コンパクション処理を実行する際には、前記ブロックに含まれる有効な前記管理単位のデータの個数毎に前記ブロックをリンクドリスト形式で管理する管理テーブル内から、前記コンパクション処理の対象とするブロックを検索し、検索したブロックを用いてコンパクション処理を実行することを特徴とする。

本発明によれば、コンパクションの処理時間を短縮化することが可能なメモリシステムを提供できる。

以下、本発明の実施の形態について図面を参照して説明する。なお、以下の説明において、同一の機能および構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。

先ず、本明細書で用いる用語について定義しておく。
・物理ページ：ＮＡＮＤメモリチップ内部において一括して書き込み／読み出しが可能な単位のこと。物理ページサイズは、例えば４ｋＢ。ただし、主データ（ユーザデータなど）に対してＳＳＤ内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、４ｋＢ＋冗長ビット（例えば、数１０Ｂ）が同時にメモリセルに書き込まれる単位となるが、説明の便宜上、上記のように定義する。
・論理ページ：ＳＳＤ内で設定される書き込み／読み出し単位であり、１以上の物理ページに対応付けられている。論理ページサイズは、例えば８ビットノーマルモードでは、４ｋＢ、３２ビット倍速モードでは、３２ｋＢ。ただし、冗長ビットは含まないものとする。
・物理ブロック：ＮＡＮＤメモリチップ内部において独立して消去可能な最小単位のことであり、複数の物理ページから構成される。物理ブロックサイズは、例えば５１２ｋＢ。ただし、主データに対してＳＳＤ内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、５１２ｋＢ＋冗長ビット（例えば、数１０ｋＢ）が同時に消去される単位となるが、説明の便宜上、上記のように定義する。
・論理ブロック：ＳＳＤ内で設定される消去単位であり、１以上の物理ブロックに対応付けられている。論理ブロックサイズは、例えば８ビットノーマルモードでは、５１２ｋＢ、３２ビット倍速モードでは、４ＭＢ。ただし、冗長ビットは含まないものとする。
・セクタ：ホストからの最小アクセス単位のこと。セクタサイズは、例えば５１２Ｂ。
・クラスタ：ＳＳＤ内で「小さなデータ」を管理する管理単位。クラスタサイズはセクタサイズ以上であり、クラスタサイズの２以上の自然数倍が論理ページサイズとなるように定められる。
・トラック：ＳＳＤ内で「大きなデータ」を管理する管理単位。クラスタサイズの２以上の自然数倍がトラックサイズに、かつ、トラックサイズの２以上の自然数倍が論理ブロックサイズとなるように定められる。
・フリーブロック（ＦＢ）：用途未割り当てのＮＡＮＤ型フラッシュメモリ上の論理ブロックのこと。用途を割り当てる際に消去してから使用する。
・バッドブロック（ＢＢ）：ＮＡＮＤ型フラッシュメモリ上の、誤りが多いなど記憶領域として使用できない物理ブロックのこと。例えば、消去動作が正常に終了しなかった物理ブロックがバッドブロックＢＢとして登録される。
・書き込み効率：所定期間内における、ホストから書き込んだデータ量に対する、論理ブロックの消去量の統計値のこと。小さいほどＮＡＮＤ型フラッシュメモリの消耗度が小さい。
・有効クラスタ：最新のデータを保持しているクラスタ。
・無効クラスタ：最新ではないデータを保持しているクラスタ。
・有効トラック：最新のデータを保持しているトラック。
・無効トラック：最新ではないデータを保持しているトラック。
・コンパクション：管理対象内の論理ブロックから、有効クラスタや有効トラックのみを取り出して、新しい論理ブロックに書き直すこと。

［第１の実施形態］
図１は、ＳＳＤ（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）＋log ₂ ｎビット（ｎ-way））×ｍビット（ｍ-line）で構成されている。ＷＣトラック管理テーブル２４はリンクドリスト構造を有しており、ＷＣ２１中に存在する論理トラックアドレスに関する情報のみがエントリされている。

・トラック管理テーブル３０（正引き）
つぎに、図１２を用いてトラック管理テーブル３０について説明する。トラック管理テーブル３０は、論理トラックアドレス単位でＭＳ１１上の論理的なデータ位置を管理するためのテーブルであり、クラスタ単位でＦＳ１２やＩＳ１３にデータが保持されている場合には、それらに関する基本情報と、詳細情報へのポインタも保持している。論理トラックアドレス３０ａをインデックスとした配列形式で構成される。論理トラックアドレス３０ａをインデックスとした各エントリは、クラスタビットマップ３０ｂ、論理ブロックＩＤ３０ｃ＋論理ブロック内トラック位置３０ｄ、クラスタテーブルポインタ３０ｅ、ＦＳクラスタ数３０ｆ、ＩＳクラスタ数３０ｇなどの情報で構成されている。トラック管理テーブル３０は、論理トラックアドレスをインデックスとして、その論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックＩＤ（記憶デバイス位置に対応）などの所要情報を得るので、正引きテーブルとして機能する。

クラスタビットマップ３０ｂは、１つの論理トラックアドレス範囲に属する２ ^{（ｋ−ｉ）} 個のクラスタをクラスタアドレス昇順に例えば８分割したビットマップであり、８個の各ビットは、２ ^{（ｋ−ｉ−３）} 個のクラスタアドレスに対応するクラスタがＭＳ１１に存在するか、ＦＳ１２もしくはＩＳ１３に存在するかを示している。ビットが“０”の場合は、その検索対象のクラスタは確実にＭＳ１１内に存在することを示し、ビットが“１”の場合は、そのクラスタはＦＳ１２もしくはＩＳ１３に存在する可能性があることを示している。

論理ブロックＩＤ３０ｃは、当該論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックＩＤを識別するための情報である。論理ブロック内トラック位置３０ｄは、論理ブロックＩＤ３０ｃで指定された論理ブロック中における当該論理トラックアドレス（３０ａ）に対応するトラックの記憶位置を示すものである。１論理ブロックは最大２ ^ｉ 個の有効トラックで構成されるので、論理ブロック内トラック位置３０ｄは、ｉビットで２ ^ｉ 個のトラック位置を識別する。

クラスタテーブルポインタ３０ｅは、リンクドリスト構造を有するＦＳ／ＩＳ管理テーブル４０の各リストの先頭エントリへのポインタである。クラスタビットマップ３０ｂの検索で、当該クラスタがＦＳ１２／ＩＳ１３に存在する可能性があることを示していた場合、クラスタテーブルポインタ３０ｅを用いてＦＳ／ＩＳ管理テーブル４０の検索を実行する。ＦＳクラスタ数３０ｆは、ＦＳ１２内に存在する有効クラスタ数を示している。ＩＳクラスタ数３０ｇは、ＩＳ１３内に存在する有効クラスタ数を示している。

・ＦＳ／ＩＳ管理テーブル４０（正引き）
つぎに、図１３を用いてＦＳ／ＩＳ管理テーブル４０について説明する。ＦＳ／ＩＳ管理テーブル４０は、論理クラスタ単位でＦＳ１２（ＦＳＩＢ１２ａも含む）もしくはＩＳ１３に保持されているデータの位置を管理するためのテーブルである。図１３に示すように、論理トラックアドレス毎に独立したリンクドリスト形式で構成され、各リストの先頭エントリへのポインタは、前述したように、トラック管理テーブル３０のクラスタテーブルポインタ３０ｅのフィールドに保持されている。図１３では、２つの論理トラックアドレス分のリンクドリストが示されている。各エントリは、論理クラスタアドレス４０ａ、論理ブロックＩＤ４０ｂ、論理ブロック内クラスタ位置４０ｃ、ＦＳ／ＩＳブロックＩＤ４０ｄ、nextポインタ４０ｅから構成されている。ＦＳ／ＩＳ管理テーブル４０は、論理クラスタアドレス４０ａから、その論理クラスタアドレスに対応する論理クラスタが記憶されている論理ブロックＩＤ４０ｂ、論理ブロックン内クラスタ位置４０ｃ（記憶デバイス位置に対応）などの所要情報を得るので、正引きテーブルとして機能する。

論理ブロックＩＤ４０ｂは、当該論理クラスタアドレス４０ａに対応する論理クラスタが記憶されている論理ブロックＩＤを識別するための情報である。論理ブロック内クラスタ位置４０ｃは、論理ブロックＩＤ４０ｂで指定された論理ブロック中における当該論理クラスタアドレス４０ａに対応するクラスタの記憶位置を示すものである。１論理ブロックは最大２ ^ｋ 個の有効クラスタで構成されるので、論理ブロック内クラスタ位置４０ｃは、ｋビットで２ ^ｋ 位置を識別する。ＦＳ／ＩＳブロックＩＤ４０ｄは、後述するＦＳ／ＩＳ論理ブロック管理テーブル４２のインデックスであるＦＳ／ＩＳブロックＩＤが登録されている。ＦＳ／ＩＳブロックＩＤは、ＦＳ１２またはＩＳ１３に所属する論理ブロックを識別するための情報であり、このＦＳ／ＩＳ管理テーブル４０でのＦＳ／ＩＳブロックＩＤ４０ｄは、後述するＦＳ／ＩＳ論理ブロック管理テーブル４２とのリンクのために登録されている。nextポインタ４０ｅは、論理トラックアドレス毎にリンクされる同じリスト内の次のエントリへのポインタを示している。

・ＭＳ論理ブロック管理テーブル３５（逆引き）
つぎに、図１４を用いてＭＳ論理ブロック管理テーブル３５について説明する。ＭＳ論理ブロック管理テーブル３５は、ＭＳ１１に用いられている論理ブロックに関する情報（どの論理トラックが記憶されているか、追記可能か等）を一元管理するためのテーブルである。なお、ＭＳ論理ブロック管理テーブル３５には、ＦＳ１２（ＦＳＩＢ１２も含む）、ＩＳ１３に所属する論理ブロックに関する情報も登録されている。ＭＳ論理ブロック管理テーブル３５は、論理ブロックＩＤ３５ａをインデックスとした配列形式で構成され、エントリ数は１２８ＧＢのＮＡＮＤメモリ１０の場合は、３２Ｋエントリまで持つことができる。各エントリは、２ⁱトラック分のトラック管理ポインタ３５ｂ、有効トラック数３５ｃ、書き込み可能先頭トラック３５ｄ、Validフラグ３５ｅから構成されている。このＭＳ論理ブロック管理テーブル３５は、記憶デバイス位置に対応する論理ブロックＩＤ３５ａから、この論理ブロックに記憶されている論理トラックアドレスなどの所要情報を得るので、逆引きテーブルとして機能する。

トラック管理ポインタ３５ｂは、論理ブロックＩＤ３５ａで指定される当該論理ブロック内の２ⁱ個のトラック位置毎に対応する論理トラックアドレスを保持する。この論理トラックアドレスを用いて、論理トラックアドレスをインデックスとするトラック管理テーブル３０を検索することができる。有効トラック数３５ｃは、論理ブロックＩＤ３５ａで指定される当該論理ブロックに記憶されているトラックのうちの有効なものの個数（最大２ⁱ個）を示している。書き込み可能先頭トラック位置３５ｄは、論理ブロックＩＤ３５ａで指定される当該論理ブロックが追記中のブロックであった場合における追記可能なトラック先頭位置（０〜２ⁱ−１、追記終了時は２ⁱ）を示している。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フラグ３５ｅなどを参照することにより、ＦＳ１２内に無効となった論理ブロックが存在する場合、そのブロックを無効なフリーブロックＦＢとする。
２．ＦＳＩＢ１２ａでフルに成ったブロックをＦＳ１２に追い出す。具体的には、前述したＦＳ／ＩＳ構造管理テーブル（図示せず）を更新して、該当ブロックをＦＳＩＢ管理下からＦＳ管理下に移し変える。
３．ＦＳ１２に割り当てられている論理ブロックの個数がＦＳ１２として許容されるブロック数の上限値を越えるような状況が発生するか否かを判断し、発生している場合に、以下の追い出しを実行する。
４．まず追い出し対象の最古の論理ブロック中のクラスタデータのうちＩＳ１３に移動せずに、直接ＭＳ１１に移動すべきものを決定する（実際には、ＭＳの管理単位がトラックであるので、トラック単位での決定）。
（ア）追い出し対象の論理ブロック中の有効クラスタをページの先頭から順にスキャンする。
（イ）クラスタが属するトラックがＦＳ中に何個の有効クラスタを保有しているか、トラック管理テーブル３０のＦＳクラスタ数３０ｆのフィールドを参照して検索する。
（ウ）トラック内有効クラスタ数が所定の閾値（例えば２ ^ｋ−ｉ 個の５０％）以上だった場合、そのトラックをＭＳへの追い出し候補とする。
５．ＭＳ１１に追い出すべきトラックをＭＳＩＢ１１ａに対して書き込む。
６．追い出しトラックが残っている場合、さらにＭＳＩＢ１１への追い出しを実行する。
７．上記２〜４の処理の後も追い出し対象の論理ブロックに有効なクラスタが存在している場合、この論理ブロックをＩＳ１３にＭｏｖｅする。
なお、ＦＳ１２からＭＳＩＢ１１ａへの追い出しが発生したときには、その直後、ＭＳ１１での前述したＣＩＢ処理が実行される（ステップＳ３５０）。

ＩＳ１３のＣＩＢ処理
つぎに、ＩＳ１３でのＣＩＢ処理について説明する（ステップＳ３６０）。上記したＦＳ１２からＩＳ１３へのブロック移動によって論理ブロックがＩＳ１３に追加されるが、これにともなって複数個の論理ブロックで構成されるＩＳ１３に対して管理可能なブロック数の上限を超えてしまう状況が発生する。このような状況が発生した場合、ＩＳ１３では、まずＭＳ１１への１〜複数個の論理ブロックの追い出しを行った後、ＩＳコンパクションを実行する。具体的には、次のような手順を実行する。
１．ＩＳ１３に含まれるトラックをトラック内の有効クラスタ数×有効クラスタ係数でソートし、積の値が大きいトラック２ ^ｉ＋１ 個(２論理ブロック分)を集めてＭＳＩＢ１１ａに追い出す。
２．有効クラスタ数が最も少ない２ ^ｉ＋１ 個の論理ブロックの合計有効クラスタ数が例えば、所定の設定値である２ ^ｋ 個（１論理ブロック分）以上ある場合は、上のステップを繰り返す。
３．上記の追い出しを行った後、有効クラスタ数の少ない論理ブロックから順にクラスタを２ ^ｋ 個集め、ＩＳ１３内でコンパクションを行う。
４．コンパクション元の論理ブロックのうち有効クラスタがなくなったものを無効なフリーブロックＦＢとして返還する。
なお、ＩＳ１３からＭＳＩＢ１１ａへの追い出しが発生したときには、その直後、ＭＳ１１での前述したＣＩＢ処理が実行される（ステップＳ３７０）。

図２０は、各構成要素間のデータの流れにおける入力と出力の組み合わせ、およびそのデータの流れが何をトリガとして発生するかを示すものである。ＦＳ１２は、基本的には、ＷＣ２１からのクラスタ追い出しによってデータが書き込まれるが、ＷＣ２１からＦＳ１２への追い出しに付随してクラスタ内セクタ穴埋め（クラスタ穴埋め）が必要な場合は、ＦＳ１２、ＩＳ１３、ＭＳ１１からのデータがコピーされる。ＷＣ２１では、ＷＣクラスタ管理テーブル２５のタグ中のセクタ位置ビットマップ２５ｂによって当該クラスタアドレス中の２ ^{（ｌ−ｋ）} 個のセクタの有無を識別させることによってセクタ（５１２Ｂ）単位の管理をすることが可能である。これに対し、ＮＡＮＤメモリ１０での機能要素であるＦＳ１２、ＩＳ１３の管理単位はクラスタであり、ＭＳ１１の管理単位は、トラックである。このように、ＮＡＮＤメモリ１０での管理単位は、セクタより大きいため、ＷＣ２１からＮＡＮＤメモリ１０に対して、データを書き込む際に、書き込まれるデータと同一クラスタアドレスのデータがＮＡＮＤメモリ１０中に存在する場合、ＷＣ２１からＮＡＮＤメモリ１０に書き込まれるクラスタ中のセクタと、ＮＡＮＤメモリ１０中に存在する同一クラスタアドレス内のセクタとをマージしてから、ＮＡＮＤメモリ１０に書き込む必要がある。

この処理が、図２０に示したクラスタ内セクタ穴埋め処理（クラスタ穴埋め）と、トラック内セクタ穴埋め（トラック穴埋め）であり、これらの処理を行わないと、正しいデータが読み出せなくなる。そこで、ＷＣ２１からＦＳＩＢ１２ａまたはＭＳＩＢ１１ａにデータを追い出す際には、ＷＣクラスタ管理テーブル２５を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ２５ｂを参照し、セクタ位置ビットマップ２５ｂが全て“１”でない場合は、ＮＡＮＤメモリ１０に含まれる同一クラスタまたは同一トラック中のセクタとマージする、クラスタ内セクタ穴埋めまたはトラック内セクタ穴埋めを行う。この処理には、ＤＲＡＭ２０の作業領域が使用され、ＤＲＡＭ２０の作業領域からＭＳＩＢ１１ａに書き込まれたり、ＦＳＩＢ１２ａに書き込まれたりする。

ＩＳ１３は、基本的には、ＦＳ１２からのブロック追い出しによってデータが書き込まれる（Ｍｏｖｅ）か、ＩＳ内部のコンパクションによってデータが書き込まれる。ＭＳ１１は、全ての箇所からデータが書き込まれ得る。その際、ＭＳ１１は、トラック単位にしかデータを書き込めないために、ＭＳ自身のデータによる穴埋めが発生しうる。また、トラック単位の書き込みを行う際には、他のブロックにある断片化されたデータも受動マージによって書き込まれることになる。さらにＭＳ１１は、ＭＳコンパクションによる書き込みもある。なお、受動マージにおいては、ＷＣ２１、ＦＳ１２またはＩＳ１３の３つの構成要素のうちの１つの構成要素からＭＳ１１へのトラック追い出しまたは論理ブロック追い出し（２ ^ｉ トラック分の追い出し）が発生した際、１つの構成要素での追い出し対象のトラック（または論理ブロック）に含まれる他の２つの構成要素内の有効クラスタおよびＭＳ１１内の有効クラスタが、ＤＲＡＭ２０の作業領域に集められて、ＤＲＡＭ２０の作業領域から１トラック分のデータとしてＭＳＩＢ１１ａに書き込まれる。

つぎに、本実施形態をより詳細に説明する。図２１は、図６に示したＮＡＮＤメモリ１０の書き込み処理に係わるより詳細な機能構成を示すものである。重複する説明は、省略する。

・ＦＳ構成
ＦＳ部１２Ｑは、ＦＳＩＢ１２ａとＦＳ１２によって構成されている。ＦＳ１２は、多数の論理ブロック分の容量を有し、論理ブロック単位でＦＩＦＯ構造が管理されている。ＦＳ１２の前段には、ＷＣ２１から追い出されたデータが入力されるＦＳインプットバッファ（ＦＳＩＢ）１２ａが設けられている。ＦＳＩＢ１２ａは、ＦＳフルブロックバッファ（ＦＳＦＢ）１２ａａと、ＦＳ追記バッファ（ＦＳ追記ＩＢ）１２ａｂとを備えている。ＦＳＦＢ１２ａａは、１〜複数個の論理ブロック分の容量を有し、またＦＳ追記ＩＢ１２ａｂも１〜複数個の論理ブロック分の容量を有する。ＷＣ２１からの追い出しデータが１論理ブロック分あればＦＳＦＢ１２ａａに対する論理ブロック単位のデータコピーが行われ、そうでなければＦＳ追記ＩＢ１２ａｂに対して論理ページ単位の追記書き込みが行われる。

・ＩＳ構成
ＩＳ部１３Ｑは、ＩＳ１３と、ＩＳインプットバッファ（ＩＳＩＢ）１３ａと、ＩＳコンパクションバッファ１３ｃによって構成されている。ＩＳＩＢ１３ａは、１〜複数個の論理ブロック分の容量を有し、ＩＳコンパクションバッファ１３ｃは例えば１論理ブロック分の容量を有し、ＩＳ１３は、多数の論理ブロック分の容量を有する。ＩＳ１３は、例えば、論理ブロック単位で、ＦＳ１２と同様、ＦＩＦＯ構造が管理されている。ＩＳコンパクションバッファ１３ｃは、ＩＳ部１３Ｑでのコンパクションを行うためのバッファである。

前述したように、ＩＳ部１３Ｑは、ＦＳ部１２Ｑと同様クラスタ単位でデータの管理を行う。ＦＳ部１２ＱからＩＳ部１３Ｑに対して論理ブロックの移動、すなわちＦＳ１２からの追い出しが発生すると、以前ＦＳ部１２Ｑの管理対象であった追い出し対象の論理ブロックはポインタの付け替えによりＩＳ部１３（詳細には、ＩＳＩＢ１３ａ）の管理対象ブロックとなる。このＦＳ部１２ＱからＩＳ部１３Ｑへの論理ブロックの移動により、ＩＳ１３のブロック数が所定の上限値を超えると、ＩＳ１３からＭＳ部１１Ｑへのデータ追い出しおよびＩＳコンパクション処理が実行され、ＩＳ部１３Ｑのブロック数は規定値に戻される。

・ＭＳ構成
ＭＳ部１１Ｑは、ＭＳＩＢ１１ａと、トラック前段バッファ（ＴＦＳ）１１ｂと、ＭＳ１１によって構成されている。ＭＳＩＢ１１ａは、１〜複数個（この実施の形態では４個）のＭＳフルブロックインプットバッファ（以下ＭＳＦＢ）１１ａａと、１〜複数個（この実施の形態では２個）の追記インプットバッファ（以下ＭＳ追記ＩＢ）１１ａｂとを備えている。１つのＭＳＦＢ１１ａａは、１論理ブロック分の容量を有する。ＭＳＦＢ１１ａａは、論理ブロック単位の書き込み時に用いられる。１つのＭＳ追記ＩＢ１１ａｂは、論理ブロック分の容量を有する。ＭＳ追記ＩＢ１１ａｂは、トラック単位の追記書き込み時に用いられる。

ＭＳＦＢ１１ａａには、ＷＣ２１から追い出された論理ブロック、またはＦＳ１２から追い出された論理ブロック、またはＩＳ１３から追い出された論理ブロックがＣｏｐｙされる。１つのＭＳＦＢ１１ａａにＣｏｐｙされた論理ブロックは、ＴＦＳ１１ｂを経ることなくＭＳ１１に直接Ｍｏｖｅされる。このＭＳ１１へのＭｏｖｅ後は、フリーブロックＦＢがＭＳＦＢ１１ａａとして割り当てられる。

ＭＳ追記ＩＢ１１ａｂには、ＷＣ２１から追い出されたトラック、またはＦＳ１２から追い出されたトラックが追記的にＣｏｐｙされる。このようなトラック単位で追記書き込みされるＭＳ追記ＩＢ１１ａｂのうちでフルになった論理ブロックは、ＴＦＳ１１ｂにＭｏｖｅされる。このＴＦＳ１１ｂへのＭｏｖｅ後は、フリーブロックＦＢがＭＳ追記ＩＢ１１ａｂとして割り当てられる。

ＴＦＳ１１ｂは、前述したように、多数の論理ブロック分の容量を有し、ＭＳ追記ＩＢ１１ａｂとＭＳ１１との間に介在するＦＩＦＯ構造を有するバッファである。ＦＩＦＯ構造を持つＴＦＳ１１ｂの入力側には、トラック単位で追記書き込みされるＭＳ追記ＩＢ１１ａｂのうちでフルになった論理ブロックがＭｏｖｅされ、またＭＳ１１内のコンパクション処理によって形成された論理ブロックが、ＭＳコンパクションバッファ１１ｃからＭｏｖｅされる。ＭＳコンパクションバッファ１１ｃは、ＭＳ１１でのコンパクションを行うためのバッファである。なお、ＭＳ１１内部のコンパクション処理によって、ＭＳ内トラックがＭＳコンパクションバッファ１１ｃに書き込まれる際には、書き込み対象のトラックに含まれるＷＣ２１、ＦＳ部１２Ｑ、ＩＳ部１３Ｑ内の有効クラスタがＤＲＡＭ２０の作業領域を介してＭＳコンパクションバッファ１１ｃに書き込まれる、受動マージが行われる。本実施の形態においては、ＭＳＩＢ１１ａおよびＴＦＳ１１ｂに登録されている論理ブロックについては、コンパクション対象に含めない。

図２２は、データ管理部１２０のより詳細な機能構成を示すものである。データ管理部１２０は、前述したように、ＤＲＡＭ２０に記憶したデータの管理を行うＤＲＡＭ層管理部１２０ａと、ＮＡＮＤメモリ１０に記憶したデータの管理を行う論理ＮＡＮＤ層管理部１２０ｂと、ＮＡＮＤメモリ１０を物理記憶デバイスとして管理する物理ＮＡＮＤ層管理部１２０ｃとから構成される。

ＤＲＡＭ層管理部１２０ａは、ＲＣクラスタ管理テーブル２３、ＷＣクラスタ管理テーブル２５、ＷＣトラック管理テーブル２４を備え、これら管理テーブに基づいてＤＲＡＭ層の管理を行う。論理ＮＡＮＤ層管理部１２０ｂは、トラック管理テーブル３０、ＭＳブロック管理テーブル３５、ＦＳ／ＩＳ管理テーブル４０、ＦＳ／ＩＳ論理ブロック管理テーブル４２、ＦＳ／ＩＳ内クラスタ管理テーブル４４の他に、ＭＳ構造管理テーブル６０、ＦＳ／ＩＳ構造管理テーブル６５を備え、これらの管理テーブルに基づいてＮＡＮＤメモリ１０の論理ＮＡＮＤ層の管理を行う。物理ＮＡＮＤ層管理部１２０ｃは、論物変換テーブル５０の他に、バッドブロック管理テーブル（ＢＢ管理テーブル）２００、予約ブロック管理テーブル（ＲＢブロック管理テーブル）２１０、フリーブロック管理テーブル（ＦＢ管理テーブル）２２０、アクティブブロック管理テーブル（ＡＢ管理テーブル）２３０を備え、これらの管理テーブルを用いてＮＡＮＤメモリ１０の物理ＮＡＮＤ層の管理を行う。

・物理ＮＡＮＤ層
まず、物理ＮＡＮＤ層について説明する。前述したように、３２ビット倍速モードでは、４ｃｈ（ｃｈ０、ｃｈ１、ｃｈ２、ｃｈ３）を並列で動作させ、更に、ＮＡＮＤメモリチップの備える倍速モードを利用して消去／書き込み／読み出しを行う。図２３に示すように、４つの並列動作要素１０ａ〜１０ｄ内の各ＮＡＮＤメモリチップは、例えば、プレーン０、プレーン１の２つの領域（District）に分割されている。なお、分割数は２に限定されるものではない。プレーン０およびプレーン１は、互いに独立した周辺回路（例えば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュ等）を備えており、ＮＡＮＤコントローラ１１２から入力されるコマンドに基づき、同時に消去／書き込み／読み出しを行うことが可能である。ＮＡＮＤメモリチップの倍速モードでは、上記プレーン０およびプレーン１を並列制御することにより、高速書き込みを実現している。

物理ブロックサイズは５１２ｋＢであるので、３２ビット倍速モードでは、４ｃｈの並列動作および２つのプレーンに対する同時アクセスにより、その消去単位は５１２ｋＢ×４×２＝４ＭＢとなる。すなわち、この３２ビット倍速モードでは、結果的に、８プレーンが並列動作することになる。

図２４は、論物変換テーブル５０の他の例を示すものである。図２４に示す論物変換テーブル５０は、図１７に示した論物変換テーブル５０に対し、論理ブロックＩＤ５０ａに対応する論理ブロックが消去された時刻を示す消去時刻５０ｅのフィールドが更に追加されている。消去時刻５０ｅとしては、例えば、ＮＡＮＤメモリチップ内の論理ブロックに対して消去動作が行われた回数を計測することで得られる値、或いは、ＮＡＮＤコントローラ１１２の通電時間等を利用すればよい。消去時刻５０ｅは、後述するＦＢ管理テーブル２２０でのフリーブロックＦＢ管理に利用される。

ＢＢ管理テーブル２００は、物理ブロック（５１２ｋＢ）単位でバッドブロックＢＢを管理するためのテーブルである。ＢＢ管理テーブル２００は、図２５に示すように、例えば、４(チャネル)×２(プレーン/チャネル)個のチャネル内プレーン毎に、（物理ブロック数／プレーン）×（ＮＡＮＤメモリチップ数／１並列動作要素）個数分の物理ブロックに関する情報をもつ二次元配列形式で構成されており、各エントリには、各物理ブロックに対する物理ブロックＩＤ２００ａが保持されている。

本実施形態の場合、１ＮＡＮＤメモリチップは２ＧＢサイズであり、第１番目のチップのプレーン０には、「０」〜「２０４７」の物理ブロックＩＤが割り当てられ、第１番目のチップのプレーン１には、「２０４８」〜「４０９５」の物理ブロックＩＤが割り当てられる。物理ＮＡＮＤ層管理部１２０ｃは、使用中に発生したバッドブロックＢＢをＢＢ管理テーブル２００に登録する際には、ソートはせずに対応するチャネル内プレーンＩＤ（ＩＤ＃０〜ＩＤ＃７）の最後尾の有効エントリの直後に順に追加する。

ＲＢ管理テーブル２１０は、８個の物理ブロック単位（５１２ｋＢ）で４ＭＢ論理ブロックを形成する際に余ったブロック（予約ブロックＲＢ）を管理するためのテーブルであり、ＢＢ管理テーブル２００と同様のフォーマットで管理される。対応するチャネル内プレーンＩＤごとにＦＩＦＯ管理とすることで、最も古く登録された予約ブロックから優先して利用する。

ＦＢ管理テーブル２２０は、４ＭＢ論理ブロック単位で現在用途未割り当てのフリーブロックＦＢを管理するためのテーブルであり、フリーブロックＦＢとなった順にソートされたＦＩＦＯ形式のリストである。各エントリは、論理ブロックＩＤを保持する。コンパクション処理などにより、ＦＢ管理テーブル２２０に返却されたフリーブロックＦＢは、リストの最後尾に追加され、フリーブロックＦＢ割り当ては、リストの先頭ブロックを返すことで行う。

ＦＢ管理テーブルは、図２６に示すように、返却ＦＩＦＯリスト２２０ａと、割り当てリスト２２０ｂとの２段構成になっている。返却ＦＩＦＯリスト２２０ａは、消去時刻５０ｅ順に整列しており、割り当てリスト２２０ｂは、消去回数５０ｃの少ない論理ブロックほどリストの先頭に位置する。これは、短い時間間隔で消去動作を繰り返すことを防ぐための構成である。不要になり、ＦＢ管理テーブル２２０に返却された論理ブロックは、返却ＦＩＦＯリスト２２０ａの最後尾に追加され、一定の期間にここに保持される。

返却ＦＩＦＯリスト２２０ａから押し出された論理ブロックは、その消去回数５０ｃに応じて割り当てリスト２２０ｂの途中に挿入される。論理ＮＡＮＤ層管理部１２０ｂからフリーブロックＦＢの割り当てを要求されると、論理ＮＡＮＤ層管理部１２０ｃは、割り当てリスト２２０ｂの先頭から取り出し、割り当てを行う。

上記ＦＢ管理テーブルにより、全ての論理ブロックの消去回数、消去間隔が概ね等しくなるように、消去する論理ブロックを均等に分散させる（ウェアレベリング処理）ことが可能となる。ＮＡＮＤ型フラッシュメモリの寿命は、消去回数の他に、消去処理の間隔にも依存しており、その間隔が長いほどリテンション特性が良く、寿命が延びることが知られている。これは、消去間隔が短いとリテンション特性が悪く、寿命が損なわれることも示している。また、短い間隔で書き込みを行ったとしても、相応の長期間消去を行わなければリテンション特性が回復することも知られている。

ＡＢ管理テーブル２３０は、フリーブロックＦＢから割り当てられた、用途が割り当てられた論理ブロック（アクティブブロックＡＢ）のリストであり、ＦＢ管理テーブル２２０と同様に、各エントリは、論理ブロックＩＤを保持する。登録順序が古い論理ブロックほど先頭に位置することになる。ＡＢ管理テーブルは、例えば、リフレッシュ処理に使用される。

リフレッシュ処理とは、書き込んだデータの経年変化や読み出し処理に伴うデータ破損であるリードディスターブの影響で、ＳＳＤ１００の誤り訂正能力を超える誤りが発生することを防止するための技術である。具体的には、例えば、誤り訂正能力を超える誤りが発生する前に、記憶してあるデータを読み出して誤り訂正を行い、その後再びＮＡＮＤ型フラッシュメモリにデータを書き直すという処理を行う。例えば、読み出し回数５０ｄの多いブロック、ＡＢ管理テーブル２３０の先頭ブロックなどをリフレッシュ処理の監視対象とすることができる。

物理ＮＡＮＤ層管理部１２０ｃは、以下のような論理ブロック−物理ブロック管理を行う。先ず、図２７を用いて論物変換テーブル５０を用いた、論理ブロックＩＤと８個の物理ブロックＩＤとの対応関係について説明する。

前述したように、論物変換テーブル５０の物理ブロックＩＤ５０ｂのフィールドには、論物変換テーブル５０のインデックスである論理ブロックＩＤ５０ａに対応付けられた８個の物理ブロックＩＤが登録されている。図２７は、ＮＡＮＤメモリ１０の論理ブロックＩＤと物理ブロックＩＤとの対応関係を示すものであり、１つの区画が１物理ブロックを表している。各物理ブロックに物理ブロックＩＤが割り当てられている。論理ブロックＬ０は、例えば、１行３列、２行２列、３行２列、４行２列、５行２列、６行２列、７行２列、８行３列の８個の物理ブロックで構成されている。また、破線ＢＬ１で囲まれた論理ブロックＬ１は、例えば、１行４列、２行３列、３行３列、４行３列、５行３列、６行３列、７行３列、８行４列の８個の物理ブロックで構成されているとする。

この後、例えば、論理ブロックＬ１の４行３列の物理ブロックが、記憶領域として使用できないバッドブロックＢＢとして、ＢＢ管理テーブル２００に登録されたとする。これを検知した物理ＮＡＮＤ層管理部１２０ｃは、ＲＢ管理テーブル２１０から、このバッドブロックＢＢとして登録された物理ブロックと同一チャネルで同一プレーンの予約ブロックＲＢを当該バッドブロックＢＢに対する入れ替え候補として選択する。図２７の場合は、隣接する４行４列の物理ブロック（予約ブロックＲＢ）が４行３列のＢＢに対する入れ替え候補として選択されている。

物理ＮＡＮＤ層管理部１２０ｃは、論物変換テーブル５０の論理ブロックＬ１に対応する論理ブロックＩＤ５０ａのエントリを検索し、このエントリ中の物理ブロックＩＤ５０ｂのフィールドに含まれる８個の物理ブロックＩＤのうちの４行３列に対応するバッドブロックＢＢの物理ブロックＩＤを、ＲＢ管理テーブル２１０から選択した４行４列のＲＢに対応する物理アドレスＩＤに変更する。これにより、この後、論理ブロックＬ１は、一点鎖線で囲まれた１行４列、２行３列、３行３列、４行４列、５行３列、６行３列、７行３列、８行４列の８個の新たな物理ブロックの組み合わせで構成されることになる。この論理ブロックＬ１の論理ブロックＩＤが「Ｌ１」であるとする。

その後、物理ＮＡＮＤ層管理部１２０ｃは、ＦＢ管理テーブル２２０から新たなフリーブロックＦＢを確保する。この確保したフリーブロックＦＢの論理ブロックＩＤが「Ｌ３」であるとする。物理ＮＡＮＤ層管理部１２０ｃは、論物変換テーブル５０を用いて論理ブロックＩＤの入れ替えを実行する。具体的には、論理ブロックＩＤ「Ｌ１」に対し、論理ブロックＩＤが「Ｌ３」である新たなフリーブロックＦＢに対応付けられた８個の物理ブロックを対応付け、さらに論理ブロックＩＤ「Ｌ３」に対し、前述の物理ブロックの組み合わせが変更された一点鎖線で囲まれた１行４列、２行３列、３行３列、４行４列、５行３列、６行３列、７行３列、８行４列の８個の物理ブロックを対応付ける。消去回数５０ｃ、読み出し回数５０ｄ、消去時刻５０ｅも論理ブロックＩＤ入れ替えに伴い入れ替える。その後、論理ブロックＩＤ「Ｌ３」を、ＦＢ管理テーブル２２０に登録する。

一方、バッドブロックＢＢに対して入れ替え可能な予約ブロックＲＢが存在しない場合には以下のような処理を行う。例えば、論理ブロックＬ１の４行３列の物理ブロックがバッドブロックＢＢとしてＢＢ管理テーブル２００に登録されたとし、さらに、このバッドブロックＢＢに対しては同一チャネルかつ同一プレーン内に予約ブロックＲＢが存在しない場合には、まず、論理ブロックＬ１内の４行３列を除く、１行４列、２行３列、３行３列、５行３列、６行３列、７行３列、８行４列の７個の物理ブロックをＲＢ管理テーブル２１０に登録する。その後は、前記同様、ＦＢ管理テーブル２２０から新たなフリーブロックＦＢを確保し、前記同様の論理ブロックＩＤの入れ替えを実行した後、ＦＢ管理テーブル２２０から取得した論理ブロックＩＤを使用不可とする。

このように、物理ＮＡＮＤ層管理部１２０ｃは、バッドブロックＢＢが発生した場合でも、論理ブロックＩＤの入れ替えを実行しているので、論理ＮＡＮＤ層管理部１２０ｂで使用する論理ブロックＩＤは、バッドブロックＢＢの発生の前後で変化しない。したがって、複数の物理ブロックの少なくとも１つをバッドブロックとして登録する場合であっても、ＬＢＡ論理アドレスと論理ブロックとの対応関係は変更されず、論理ＮＡＮＤ層管理部１２０ｂでの管理テーブルの書き換えのオーバーヘッドを回避することができる。

つぎに、３２ビット倍速モードでの消去処理について説明する。物理ＮＡＮＤ層管理部１２０ｃは、ＮＡＮＤメモリ１０のデータが論理ブロック単位で消去されるごとに、図２４に示す論物変換テーブル５０の消去された論理ブロックに対応する論理ブロックＩＤ中の消去回数５０ｃのフィールドを１カウントアップするとともに、消去時刻５０ｅを最新のデータに更新する。

・論理ＮＡＮＤ層
つぎに、図２８、図２９を用いて論理ＮＡＮＤ層での管理に使用されるＭＳ構造管理テーブル６０およびＦＳ／ＩＳ構造管理テーブル６５について説明する。図２８に示すＭＳ構造管理テーブル６０は、ＭＳ部１１Ｑの構造を管理するための領域と、状態情報を保存するための領域とを有する。ＭＳ構造管理テーブル６０は、ＭＳＦＢ１１ａａ、ＭＳ追記ＩＢ１１ａｂ、ＴＦＳ１１ｂとして割り当てられた論理ブロックＩＤを管理するＭＳバッファ管理テーブル６１と、ＭＳコンパクション時のソート処理を高速化するために、有効トラック数が少なくなった論理ブロックＩＤを保持する有効トラック数別論理ブロックＩＤリスト６２と、状態情報としての最大論理ブロック数ＭＢＬおよび有効論理ブロック数ＶＢＬを管理する領域６３、６４とを備える。

ＭＳ構造管理テーブル６０では、ＭＳＦＢ１１ａａ用、ＭＳ追記ＩＢ１１ａｂ用、ＴＦＳ１１ｂ用に、それぞれ所要エントリ数の固定フィールド６１ａ〜６１ｃが用意され、各固定フィールド６１ａ〜６１ｃに論理ブロックＩＤが記録される。ＴＦＳ１１ｂ用のフィールド６１ｃは、リンクドリスト構造を有し、ＦＩＦＯ構造を有するＴＦＳ１１ｂに対するＦＩＦＯ的な管理が行われている。

有効トラック数別論理ブロックＩＤリスト６２では、有効トラック数が１個の論理ブロック用として所要数のエントリが用意され、有効トラック数が２個の論理ブロック用として所要数のエントリが用意され、…、有効トラック数が２ ^ｉ −１の論理ブロック用として所要数のエントリが用意されており、各エントリには、論理ブロックＩＤが記録される。ＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドがサーチされることによって有効トラック数別論理ブロックＩＤリスト６２は、常に最新の状態に更新される。なお、有効トラック数別論理ブロックＩＤリスト６２には、ＭＳＩＢ１１ａ、ＴＦＳ１１ｂとしてＭＳバッファ管理テーブル６１に登録されている論理ブロックについては、エントリされない。

状態情報としての最大論理ブロック数ＭＢＬ用の固定フィールド６３には、ＭＳ部１１Ｑが取得するのを許容されている論理ブロック数である最大論理ブロック数ＭＢＬが記録される。状態情報としての有効論理ブロック数ＶＢＬ用の固定フィールド６４には、ＭＳ部１１Ｑとして現在管理されている論理ブロック数としての有効論理ブロック数ＶＢＬが記録される。

図２９に示すＦＳ／ＩＳ構造管理テーブル６５は、ＦＳ部１２ＱおよびＩＳ部１３Ｑの構造を管理するための領域を有する。ＦＳ／ＩＳ構造管理テーブル６５は、ＦＳＩＢ１２ａおよびＦＳ追記ＩＢ１２ａｂとして割り当てられた論理ブロックＩＤを管理するＦＳ入力バッファ管理テーブル６６と、ＦＳ１２のＦＩＦＯ構造を管理するＦＳＦＩＦＯ管理テーブル６７と、ＩＳＩＢ１３ａとして割り当てられた論理ブロックＩＤを管理するＩＳ入力バッファ管理テーブル６８と、ＩＳ１３のＦＩＦＯ構造を管理するＩＳＦＩＦＯ管理テーブル６９とを備える。

ＦＳ入力バッファ管理テーブル６６は、ＦＳＦＢ１２ａａ用、ＦＳ追記ＩＢ１２ａｂ用に、それぞれ所要エントリ数の固定フィールド６６ａ、６６ｂが用意され、各固定フィールド６６ａ、６６ｂにＦＳ／ＩＳ論理ブロック管理テーブル４２のインデックスであるＦＳ／ＩＳブロックＩＤ４２ａが登録される。ＩＳ入力バッファ管理テーブル６８は、ＩＳＩＢ１３ａ用に所要エントリ数の固定フィールドが用意され、各固定フィールドに、ＦＳ／ＩＳブロックＩＤ４２ａが登録される。ＦＳＦＩＦＯ管理テーブル６７には、ＦＳ１２のＦＩＦＯ構造を形成する論理ブロック数分のエントリが固定フィールドに用意され、ＦＳＦＩＦＯ管理テーブル６７の各固定フィールドには、ＦＳ／ＩＳブロックＩＤ４２ａが登録される。ＩＳＦＩＦＯ管理テーブル６９には、ＩＳ１３のＦＩＦＯ構造を形成する論理ブロック数分のエントリが固定フィールドに用意され、各固定フィールドには、ＦＳ／ＩＳブロックＩＤ４２ａが登録される。

つぎに、先の図１９を用いて説明した、２ステージ（ＷＣＦ処理およびＣＩＢ処理）に分割された書き込み処理が実行されるときの、ＷＣ２１からＭＳＩＢ１１ａへのＣｏｐｙ処理に伴う各管理テーブルの更新処理を説明する。なお、ここでは、ＷＣ２１からＭＳ追記ＩＢ１１ａｂへのトラック単位のＣｏｐｙが発生した場合について説明する。ＤＲＡＭ層管理部１２０ａでは、ＷＣトラック管理テーブル２４を先頭から順にチェックし、追い出し確定トラックに対応する論理トラックアドレス２４ａが登録されたトラックエントリ中のway−lineビットマップ２４ｃを参照し、way−lineビットマップ２４ｃのｍ×ｎのエントリ中のValidビットが“１”のエントリに対応するＷＣクラスタ管理テーブル２５中のエントリにおける状態フラグ２５ａをValidからＮＡＮＤへの追い出し待ちにし、論理ＮＡＮＤ層管理部１２０ｂに対し追い出し要求を通知する。

一方、論理ＮＡＮＤ層管理部１２０ｂでは、図２８に示すＭＳ構造管理テーブル６０のＭＳバッファ管理テーブル６１および図１４に示すＭＳ論理ブロック管理テーブル３５を参照し、ＭＳ追記ＩＢ１１ａｂの状態をチェックする。すなわち、ＭＳバッファ管理テーブル６１のＭＳ追記ＩＢ用のフィールド６１ｂからＭＳ追記ＩＢ１１ａｂが既に存在していると判断されたときは、ＭＳ追記ＩＢ用のフィールド６１ｂに登録されている論理ブロックＩＤについての書き込み可能トラック数に関する情報をＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドから取得し、該取得した書き込み可能トラック数をＤＲＡＭ層管理部１２０ａに通知する。

また、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳバッファ管理テーブル６１のＭＳ追記ＩＢ用のフィールド６１ｂからＭＳ追記ＩＢ１１ａｂが存在していないと判断されたときは、物理ＮＡＮＤ層管理部１２０ｃに対し、フリーブロックＦＢの獲得要求を出して、フリーブロックＦＢを該ＦＢとして割り当てられた論理ブロックＩＤと共に取得する。そして、取得したフリーブロックＦＢの書き込み可能トラック数２ ^ｉ をＤＲＡＭ層管理部１２０ａに通知する。

ＤＲＡＭ層管理部１２０ａでは、論理ＮＡＮＤ層管理部１２０ｂから通知された書き込み可能トラック数だけ、ＷＣトラック管理テーブル２４からトラックを選択し、さらに前述のトラック内セクタ穴埋めと受動マージを行うか否かを判断する。ここでは、トラック内セクタ穴埋めを行う必要はないとする。ＤＲＡＭ層管理部１２０ａは、追い出すトラックがＮＡＮＤメモリ１０に存在しているか否かをチェックして受動マージを行うか否かを調べるために、論理ＮＡＮＤ層管理部１２０ｂに対し追い出しを行う論理トラックアドレスなどの所要の情報を通知する。

この通知を受けると、論理ＮＡＮＤ層管理部１２０ｂは、トラック管理テーブル３０のインデックスである論理トラックアドレス３０ａ、必要な場合はさらにＦＳ／ＩＳ管理テーブル４０を検索し、ＮＡＮＤメモリ１０側に追い出しを行う論理トラックアドレスと同一の論理トラックが存在しているかをサーチし、このサーチ結果を物理ＮＡＮＤ層管理部１２０ｃに通知する。これによって、物理ＮＡＮＤ層管理部１２０ｃによって、受動マージを伴うあるいは受動マージを伴わないＷＣ２１からＭＳ追記ＩＢ１１ａｂへの追い出しが行われる。

物理ＮＡＮＤ層管理部１２０ｃから、ＷＣ２１→ＭＳ追記ＩＢ１１ａｂの追い出し終了が通知されると、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ追記ＩＢ１１ａｂとしてあらたなフリーブロックＦＢを物理ＮＡＮＤ層管理部１２０ｃから取得した場合は、物理ＮＡＮＤ層管理部１２０ｃから与えられたフリーブロックＦＢの論理ブロックＩＤに対応するＭＳ論理ブロック管理テーブル３５のエントリのValidフラグ３５ｅをValidにし、ＭＳバッファ管理テーブル６１のＭＳ追記ＩＢ用のフィールド６１ｂに論理ブロックＩＤを登録し、ＭＳ構造管理テーブル６０の有効論理ブロック数ＶＢＬをインクリメントする。

また、論理ＮＡＮＤ層管理部１２０ｂは、トラック管理テーブル３０を更新する。すなわち、ＷＣ２１からＭＳ追記ＩＢ１１ａｂへ追い出されたトラックに対応する論理トラックアドレス３０ａのエントリに対し、クラスタビットマップ３０ｂ、論理ブロックＩＤ３０ｃおよび論理ブロック内トラック位置３０ｄなどの所要情報を登録する。

受動マージが行われていない場合は、前述のように、トラック管理テーブル３０の対応する論理トラックエントリに所要情報を登録する。また、ＷＣ２１から追い出された新しいトラックに関するデータをＭＳ論理ブロック管理テーブル３５の書き込みを行った論理ブロックＩＤに対応するエントリに対し登録する。ＭＳ論理ブロック管理テーブル３５への登録としては、ＭＳ論理ブロックに格納されたトラックに対応するトラック管理テーブル３０のインデックスとしての論理トラックアドレス（トラック管理ポインタ３５ｂ）の更新と、有効トラック数３５ｃの更新と、書込み可能先頭トラック３５ｄの更新などがある。

ＷＣ２１とＭＳ１１との受動マージが行われたとすると、トラック管理テーブル３０中のマージ元トラックに対応する論理トラックアドレス３０ａのエントリ中の論理ブロックＩＤ３０ｃおよび論理ブロック内トラック位置３０ｄなどの所要情報が更新される。具体的には、論理ブロックＩＤ３０ｃがＭＳ１１に存在していたときの論理ブロックＩＤからＭＳ追記ＩＢ１１ａｂに対応する論理ブロックＩＤに変更され、論理ブロック内トラック位置３０ｄが追記書き込み状態に応じて変更される。

さらに、ＭＳ論理ブロック管理テーブル３５中のマージ元の論理ブロックに対応するエントリにおけるトラック管理ポインタ３５ｂのフィールドの該当箇所を削除し、有効トラック数３５ｃをデクリメントし、さらにＭＳ構造管理テーブル６０の有効トラック数別論理ブロックＩＤリスト６２を更新する。マージ元の論理ブロックに対応するエントリにおける有効トラック数３５ｃがデクリメントにより０になった場合は、ＭＳ構造管理テーブル６０の有効論理ブロック数ＶＢＬをデクリメントし、物理ＮＡＮＤ層管理部１２０ｃに対しこの書き込み不可能な無効なフリーブロックＦＢを返却する。そして、この返却した論理ブロックに対応するエントリのValidフラグ３５ｅをInValidにする。さらに、前述と同様にして、ＷＣ２１から追い出された新しいトラックに関するデータをＭＳ論理ブロック管理テーブル３５に登録する。

また、物理ＮＡＮＤ層管理部１２０ｃから、ＷＣ２１→ＭＳ追記ＩＢ１１ａｂの追い出し終了が通知されたとき、論理ＮＡＮＤ層管理部１２０ｂは、ＤＲＡＭ層管理部１２０ａに対し追い出し終了を通知する。この通知を受けたＤＲＡＭ層管理部１２０ａでは、ＷＣクラスタ管理テーブル２５中の追い出されたトラックに所属する全クラスタに対応するエントリ中の状態フラグ２５ａはInvalid（使用可能）とされ、この後これらエントリに対する書き込みが可能となる。また、ＷＣトラック管理テーブル２４中の追い出されたトラックに対応するリストについては、例えば直前リストのnextポインタ２４ｄが変更または削除されて、無効化される。

つぎに、ＣＩＢ処理について説明する。ＷＣＦ処理が終了すると、ＷＣＦ処理によって書き込まれたＦＳＩＢ１２ａのデータをＦＳ１２にＭｏｖｅする処理と、ＷＣＦ処理によって書き込まれたＭＳＩＢ１１ａのデータをＭＳ１１またはＴＦＳ１１ｂにＭｏｖｅする処理などを含むＣＩＢ処理が実行される。以下、図３０のフローチャートを用いてＣＩＢ処理の詳細手順について説明する。

・ＭＳ部１１ＱのＣＩＢ処理
まず、図１９のステップＳ３３０で説明したＭＳ部１１Ｑでの第１回目のＣＩＢ処理について詳述する。論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ構造管理テーブル６０のＭＳバッファ管理テーブル６１のＭＳＦＢ用フィールド６１ａ、ＭＳ追記ＩＢ用のフィールド６１ｂに登録されている論理ブロックＩＤについての有効トラック数の情報をＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドから取得し、ＭＳＩＢ１１ａのＭＳＦＢ１１ａａまたはＭＳ追記ＩＢ１１ａｂに全トラック書き込み済みのフルになったブロックが一つ以上存在するか否かを調べ（ステップＳ４００）、ＭＳＩＢ１１ａにフルになったブロックが一つ以上存在する場合に、以下の処理を行う。ステップＳ４００の判定がＮＯである場合は、手順はステップＳ４４０に移行する。

ステップＳ４００の判断がＹＥＳの場合、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃを参照することにより、ＭＳ内に有効トラック数３５ｃが０となった無効論理ブロックが存在するか否かを調べ、ＭＳ内に無効論理ブロックが存在する場合、該無効論理ブロックを物理ＮＡＮＤ層管理部１２０ｃに返却する（ステップＳ４０５）。返却された無効論理ブロックに対応するＭＳ論理ブロック管理テーブル３５のエントリはValidフラグ３５ｅがInValidにされ、ＭＳ構造管理テーブル６０の有効論理ブロック数ＶＢＬがデクリメントされる。つぎに、ＭＳＦＢ１１ａａ中のフルになった論理ブロックは、直接ＭＳ１１にＭｏｖｅされ、ＭＳ追記ＩＢ１１ａｂ中のフルになった論理ブロックはＴＦＳ１１ｂにＭｏｖｅされる（ステップＳ４０７）。このＭｏｖｅ処理は、具体的には、ＭＳ構造管理テーブル６０のＭＳバッファ管理テーブル６１のＭＳＦＢ用フィールド６１ａ、ＭＳ追記ＩＢ用のフィールド６１ｂに登録されている該当する論理ブロックＩＤを削除するのみである。

つぎに、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ構造管理テーブル６０の状態情報としての有効論理ブロック数ＶＢＬを最大論理ブロック数ＭＢＬと比較する（ステップＳ４１０）。この比較の結果、有効論理ブロック数ＶＢＬが最大論理ブロック数ＭＢＬを越えている場合、論理ＮＡＮＤ層管理部１２０ｂは、書き込み可能なフリーブロックＦＢが不足していると判断し、以下のＭＳコンパクション処理を１ブロックずつ実行して、全て無効なトラックで構成された物理ＮＡＮＤ層管理部１２０ｃに返却するべき無効論理ブロックを増やし、有効論理ブロック数ＶＢＬを最大ブロック数未満ＭＢＬとする（ステップＳ４２０）。なお、ステップＳ４１０の判定において、書き込み可能なＦＢが不足していない場合は、手順はステップＳ４４０に移行される。

ＭＳコンパクション処理には、前述したように、２ ^ｉ トラックＭＳコンパクションと、２ ^ｉ トラック未満ＭＳコンパクションとの２種類がある。２ ^ｉ トラックＭＳコンパクションでは、ＭＳコンパクションバッファ１１ｃが使用されて、コンパクション後の論理ブロックは、ＴＦＳ１１ｂの先頭にＭｏｖｅされる。２ ^ｉ トラック未満ＭＳコンパクションでは、トラック単位に、ＭＳ追記ＩＢ１１ａｂにＣｏｐｙされる。

まず、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ構造管理テーブル６０の有効トラック数別論理ブロックＩＤリスト６２を参照することで、有効トラック数の少ない論理ブロックから、トラックを２ ^ｉ 個集めて、集めたトラックを２ ^ｉ 個ずつ、書き込み可能なフリーブロックＦＢとして物理ＮＡＮＤ層管理部１２０ｃから取得したＭＳコンパクションバッファ１１ｃに対しＣｏｐｙする、２ ^ｉ トラックＭＳコンパクションを実行する。

具体的には、論理ＮＡＮＤ層管理部１２０ｂは、物理ＮＡＮＤ層管理部１２０ｃに対し、フリーブロックＦＢの獲得要求を出して、フリーブロックＦＢを該フリーブロックＦＢとして割り当てられた論理ブロックＩＤと共に取得する。そして、コンパクション対象として選択した複数のトラックをこのフリーブロックＦＢにＣｏｐｙするよう、物理ＮＡＮＤ層管理部１２０ｃに対し、要求する。なお、このコンパクション対象のトラックがＷＣ２１、ＦＳ部１２Ｑ、ＩＳ部１３Ｑに有効クラスタを持つ場合にはそれらもマージしてＭＳコンパクションバッファ１１ｃに集められる、前述の受動マージが実行される。

物理ＮＡＮＤ層管理部１２０ｃからコンパクションの終了が通知されると、論理ＮＡＮＤ層管理部１２０ｂは、トラック管理テーブル３０のコンパクションが行われたトラックに対応する論理トラックアドレス３０ａを持つエントリにおける、論理ブロックＩＤ３０ｃを物理ＮＡＮＤ層管理部１２０ｃから取得したフリーブロックＦＢの論理ブロックＩＤに更新し、さらに論理ブロック内トラック位置３０ｄを更新する。

また、ＭＳコンパクションバッファ１１ｃとして使用した、物理ＮＡＮＤ層管理部１２０ｃから取得したフリーブロックＦＢの論理ブロックＩＤをＭＳ論理ブロック管理テーブル３５に新たなエントリとして登録し、エントリ中の各フィールドに所要の情報を登録する。この登録としては、トラック管理ポインタ３５ｂの更新と、有効トラック数３５ｃの更新と、書込み可能先頭トラック３５ｄの更新などがある。

また、ＭＳ構造管理バッファ６０のＭＳバッファ管理テーブル６１のＴＦＳ用フィールド６１ｃのＦＩＦＯ構造（リンクドリスト）の先頭に、ＭＳコンパクションバッファ１１ｃとして使用した論理ブロックＩＤを登録することで、ＭＳコンパクションの結果、有効な２ ^ｉ 個のトラックを含む１論理ブロックで構成されたＭＳコンパクションバッファ１１ｃを、ＴＦＳ１１ｂの先頭（最も古い位置）にＭｏｖｅする。なお、ＴＦＳ１１ｂがフルになったら、最も古い先頭のブロックがＭＳ１１にＭｏｖｅされる。

つぎに、ＭＳ１１中のコンパクション元の古いトラックデータを無効化する。具体的には、ＭＳ論理ブロック管理テーブル３５中のコンパクション元の論理ブロックに対応するエントリにおけるトラック管理ポインタ３５ｂのフィールドの該当箇所を削除し、有効トラック数３５ｃをデクリメントし、さらにＭＳ構造管理テーブル６０の有効トラック数別論理ブロックＩＤリスト６２を更新する。有効トラック数３５ｃがデクリメントにより０になった場合は、ＭＳ構造管理テーブル６０の有効論理ブロック数ＶＢＬをデクリメントし、物理ＮＡＮＤ層管理部１２０ｃに対しこの無効論理ブロックを返却する。そして、この返却した論理ブロックに対応するＭＳ論理ブロック管理テーブル３５のエントリはValidフラグ３５ｅがInValidにされる。

このようなコンパクション処理および無効論理ブロックＦＢの返却処理が終了すると、有効論理ブロック数ＶＢＬと最大論理ブロック数ＭＢＬを比較し、有効論理ブロック数ＶＢＬが最大論理ブロック数ＭＢＬを越えている場合は、再度、有効トラックを２ ^ｉ 個集める２ ^ｉ トラックＭＳコンパクションを実行する。また、有効論理ブロック数ＶＢＬが最大論理ブロック数ＭＢＬを越えている状態で、有効トラックを２ ^ｉ 個集める２ ^ｉ トラックＭＳコンパクションが不可能になった場合は、２ ^ｉ トラック未満ＭＳコンパクションが実行される。

この２ ^ｉ トラック未満ＭＳコンパクションでは、コンパクション対象の２ ^ｉ トラックに満たない個数のトラックをＭＳ追記ＩＢ１１ａｂにコピーすることで、無効な２ ^ｉ トラックで構成された無効論理ブロックを生成し、生成した無効論理ブロックを物理ＮＡＮＤ層管理部１２０ｃに返却することで、有効論理ブロック数ＶＢＬを減少させる。２ ^ｉ トラック未満ＭＳコンパクションについての、管理テーブルの更新については、その説明を省略する。

・ＦＳ１２のＣＩＢ処理
つぎに、図１９のステップＳ３４０で説明したＦＳ１２でのＣＩＢ処理について詳述する。論理ＮＡＮＤ層管理部１２０ｂは、ＦＳ／ＩＳ構造管理テーブル６５のＦＳ入力バッファ管理テーブル６６のＦＳＦＢ用フィールド６６ａ、ＦＳ追記ＩＢ用のフィールド６６ｂに登録されている論理ブロックＩＤについての有効クラスタ数の情報を、ＦＳ／ＩＳ論理ブロック管理テーブル３２の有効クラスタ数４２ｄのフィールドから取得し、ＦＳＩＢ１２ａのＦＳＦＢ１２ａａまたはＦＳ追記ＩＢ１２ａｂに全ページ（全クラスタ）書き込み済みのフルになった論理ブロックが一つ以上存在するか否かを調べ（ステップＳ４４０）、ＦＳＩＢ１２ａにフルになった論理ブロックが一つ以上存在する場合に、以下の処理を行う。ステップＳ４４０の判定がＮＯである場合は、手順はここで終了する。

ステップＳ４４０の判断がＹＥＳの場合、論理ＮＡＮＤ層管理部１２０ｂは、ＦＳ／ＩＳ構造管理テーブル６５およびＦＳ／ＩＳ論理ブロック管理テーブル４２の有効クラスタ数４２ｄを参照することにより、ＦＳ部１２Ｑ内に有効クラスタ数４２ｄが０である無効論理ブロックが存在するか否かを調べ、ＦＳ部１２Ｑ内に無効論理ブロックが存在する場合、該無効論理ブロックを物理ＮＡＮＤ層管理部１２０ｃに返却する（ステップＳ４４５）。

返却された論理ブロックのエントリはＭＳ論理ブロック管理テーブル３５およびＦＳ／ＩＳ論理ブロック管理テーブル４２から削除される。つぎに、ＦＳＦＢ１２ａａ中のフルになった論理ブロックは、ＦＳ１２にＭｏｖｅされ、ＦＳ追記ＩＢ１２ａｂ中のフルになった論理ブロックもＦＳ１２にＭｏｖｅされる（ステップＳ４４７）。このＭｏｖｅ処理は、具体的には、ＦＳ／ＩＳ構造管理テーブル６５のＦＳ入力バッファ管理テーブル６６のＦＳＦＢ用フィールド６６ａ、ＦＳ追記ＩＢ用のフィールド６６ｂに登録されている該当する論理ブロックＩＤを削除するのみである。

つぎに、論理ＮＡＮＤ層管理部１２０ｂは、ＦＩＦＯ構造を有するＦＳ１２の論理ブロック数が、ＦＳ１２として許容される所定の最大論理ブロック数ＢＬfsmaxを越えているか否かを判断する（ステップＳ４５０）。具体的には、ＦＳＦＩＦＯ管理テーブル６７から算出した論理ブロック数が予め設定した最大論理ブロック数ＢＬfsmaxを越えているか否かを判断する。

この比較の結果、算出した論理ブロック数が最大論理ブロック数ＢＬfsmaxを越えている場合、論理ＮＡＮＤ層管理部１２０ｂは、書き込み可能なフリーブロックＦＢが不足していると判断し、そのときの状態に応じて、以下の、ＭＳ１１への例えば２論理ブロック分ずつの追い出し処理（ステップＳ４６０）と、ＩＳ１３への１論理ブロック分の追い出し処理を実行する（ステップＳ５００）。なお、ステップＳ４５０の判定において、ＦＳ１２内がフルでない場合は、ＦＳ１２からＭＳＩＢ１１ａへの追い出し処理と、ＦＳ１２からＩＳＩＢ１３ａへの追い出し処理を行うことなく、手順をここで終了する。

ＦＳ１２からＭＳＩＢ１１ａへの追い出し処理では、まず、ＦＳ１２からＩＳ部１３Ｑを経ることなくＭＳＩＢＳ１１ａに直接移動する論理ブロックがあるか否かを判断する（ステップＳ４５５）。具体的には、ＦＳ１２のＦＩＦＯの先頭にある最古の論理ブロック中のクラスタを順に１つずつチェックし、当該クラスタが属するトラックがＦＳ部１２Ｑ中に何個の有効クラスタを保有しているか、トラック管理テーブル３０のＦＳクラスタ数３０ｆのフィールドを参照して検索する。そして、トラック内有効クラスタ数が所定の閾値（例えば２ ^{ｋ−ｉ−１} 個）以上だった場合、その論理トラックをＭＳＩＢ１１ａへの追い出し確定トラックとする。

上記の検索は、以下のルートを経る。
１．ＦＳ／ＩＳ構造管理テーブル６５のＦＳＦＩＦＯ管理テーブル６５からＦＩＦＯの先頭にある最古のＦＳ／ＩＳブロックＩＤを得る。
２．このＦＳ／ＩＳブロックＩＤに対応するＦＳ／ＩＳ論理ブロック管理テーブル４２のエントリ中のブロック内クラスタテーブル４２ｃのフィールドからＦＳ／ＩＳ内クラスタ管理テーブル４４へのインデックスを得る。
３．ＦＳ／ＩＳ内クラスタ管理テーブル４４において、取得したインデックスで指定された１論理ブロック内の各エントリからＦＳ／ＩＳ管理テーブル４０へのポインタを１つ取得して、ＦＳ／ＩＳ管理テーブル４０の該当リンクに飛ぶ。
４．飛び先の該当リンクが所属する該当論理トラックアドレスを得る。
５．取得した論理トラックアドレスを使ってトラック管理テーブル３０の該当エントリ中のＦＳクラスタ数３０ｆのフィールドをチェックする。
６．３〜５が繰り返される。

ＦＳ１２からＭＳ１１への追い出しは、例えば２論理ブロックずつ行われる。すなわち、論理ＮＡＮＤ層管理部１２０ｂは、上記トラック内有効クラスタ数が所定の閾値（例えば２ ^{ｋ−ｉ−１} 個）以上のトラックを、２論理ブロック分集め、該集めた２論理ブロック分のトラックをＭＳＩＢ１１ａのＭＳＦＢ１１ａａに追い出す（ステップＳ４６０）。この追い出しの際、追い出しトラック中のＦＳ１２内に存在しないクラスタについては、ＷＣ２１、ＩＳ部１３Ｑ、およびＭＳ１１から読み出してマージする前述の受動マージが実行される。

ただし、ＭＳＩＢ１１ａへの追い出し確定トラックが、２論理ブロック分存在しない場合は、１論理ブロックをＭＳＩＢ１１ａのＭＳＦＢ１１ａａに追い出し、１論理ブロック分に満たない個数のトラックをＭＳ追記ＩＢ１１ａｂに対してトラック単位に追記書き込みする（ステップＳ４６０）。同様に、ＭＳＩＢ１１ａへの追い出し確定トラックが、１論理ブロック分存在しない場合は、１論理ブロック分に満たない個数のトラックをＭＳ追記ＩＢ１１ａｂに対してトラック単位に追記書き込みする（ステップＳ４６０）。その後、ＦＩＦＯ構造のＦＳ１２の先頭論理ブロックに有効なクラスタが残っていない場合には、先頭論理ブロックを無効論理ブロックとして、物理ＮＡＮＤ層管理部１２０ｃに返却する。

・ＭＳ１１のＣＩＢ処理（図１９：ステップＳ３５０）
このようにして、ＦＳからＭＳＩＢ１１ａへの追い出しが発生すると、つぎに、ＭＳ部１１ＱのＣＩＢ処理が再び実行される（ステップＳ４８０）。このステップＳ４８０のＭＳ部１１ＱのＣＩＢ処理は、先の第１回目のＭＳ部１１ＱでのＣＩＢ処理（ステップＳ４００〜Ｓ４２０）と同様なので、重複する説明は省略する。このＭＳ部１１ＱでのＣＩＢ処理の後、論理ＮＡＮＤ層管理部１２０ｂは、ＦＳ１２からＭＳＩＢ１１ａへの追い出し条件が成立するか否かを、前記同様にして調べる（ステップＳ４５５）。この追い出し条件が成立すると、前述した、ＦＳ１２からＭＳＩＢ１１ａへの２論理ブロックの追い出し、およびＭＳ１１でのＣＩＢ処理が、再度実行される。このような処理が、ステップＳ４５５の判断がＮＯになるまで繰り返される。

・ＦＳ１２のＣＩＢ処理
ステップＳ４５５の判断がＮＯになると、論理ＮＡＮＤ層管理部１２０ｂは、つぎに、ＦＳ１２からＩＳＩＢ１３ａへの追い出し条件が、成立するか否かを判断する（ステップＳ４９０）。具体的には、上記ＦＳ１２からＭＳＩＢ１１ａへの追い出し処理の際に、チェックされたＦＩＦＯ構造を有するフル状態のＦＳ１２の先頭論理ブロックに有効なクラスタが残っている場合に、ステップＳ４９０でのＦＳ１２からＩＳ１３への追い出し条件が成立したとして、ＦＳ１２からＩＳＩＢ１３ａへの追い出しを実行する。

すなわち、ステップＳ４９０で条件が成立した場合は、ＭＳＩＢ１１ａへの追い出しトラックに含まれないクラスタだけを含む先頭論理ブロックをＩＳＩＢ１３ａへＭｏｖｅする（ステップＳ５００）。このステップＳ５００においては、例えば１論理ブロックの追い出しが実行される。そして、状態によっては、その後、ステップＳ５２０〜Ｓ５８５の手順を経た後、ステップＳ５９０の判断により、ステップＳ５００でのＦＳ１２からＩＳＩＢ１３ａへの追い出しが再度発生することもある。

ステップＳ５００での再追い出しがある状態とは、例えば、ＦＳＩＢ１２ａに複数のフルになった論理ブロックを有するバッファ（ＦＳＦＢ１２ａａまたはＦＳ追記ＩＢ１２ａｂ）が存在する状態において、ＦＩＦＯ構造を有するＦＳ１２がフルであった場合には、ＦＳＩＢ１２ａからＦＳ１２へのフルになったブロックのＭｏｖｅに伴い、ＦＳ１２からＭＳＩＢ１１ａまたはＩＳＩＢ１３ａへの複数のブロックの追い出しが発生する状態である。このような条件下で、ＦＳ１２からＩＳＩＢ１３ａへの複数の論理ブロックの追い出しが発生する可能性がある。

・ＩＳのＣＩＢ処理（図１９ステップＳ３６０）
つぎに、ステップＳ４９０での条件が成立したときに、ＩＳ１３で行われる追い出し処理およびコンパクション処理の詳細について、図３０の他に、図３１のフローチャートを参照して説明する。まず、論理ＮＡＮＤ層管理部１２０ｂは、前記と同様にして、ＩＳ部１３Ｑ内に無効論理ブロックが存在するか否かを調べ、ＩＳ部１３Ｑ内に無効論理ブロックが存在する場合、該無効論理ブロックを物理ＮＡＮＤ層管理部１２０ｃに返却する（ステップＳ５２０）。返却された論理ブロックのエントリに対応するＭＳ論理ブロック管理テーブル３５およびＦＳ／ＩＳ論理ブロック管理テーブル４２のエントリはValidフラグ３５ｅおよび４２ｆがそれぞれInValidにされる。

つぎに、論理ＮＡＮＤ層管理部１２０ｂは、ＦＩＦＯ構造を有するＩＳ１３の論理ブロック数が、ＩＳ１３として許容される所定の最大論理ブロック数ＢＬismaxを越えているか否かを判断する（ステップＳ５３０）。具体的には、ＩＳＦＩＦＯ管理テーブル６９から算出した論理ブロック数が予め設定した最大論理ブロック数ＢＬｉsmaxを越えているか否かを判断する。

この比較の結果、算出した論理ブロック数が最大論理ブロック数ＢＬismaxを越えている場合、論理ＮＡＮＤ層管理部１２０ｂは、書き込み可能なフリーブロックＦＢが不足していると判断し、ＩＳ１３から例えば２論理ブロック分のトラックをＭＳＩＢ１１ａのＭＳＦＢ１１ａａに追い出す（ステップＳ５４０）。なお、ステップＳ５３０の判定において、ＩＳ１３がフルでない場合は、ＭＳＩＢ１１ａへの追い出し処理などを行うことなく、ＩＳＩＢ１３ａ中のフルになった論理ブロックを、ＩＳ１３ｂへＭｏｖｅする（ステップＳ５８５）。

ステップＳ５４０の追い出しの際には、図１２に示したトラック管理テーブル３０などを用いて、図３１に示す追い出しトラックの選別処理を実行する。図３１において、論理ＮＡＮＤ層管理部１２０ｂは、選別処理（サイクリックサーチ処理、以下単にサーチ処理という）を開始すると（ステップＳ７００）、前回のサーチの際に検索済み最終トラックとしてステップＳ７４０において記憶したトラック管理テーブル３０のインデックスである論理トラックアドレス３０ａの次の論理トラックアドレスからサーチを開始する（ステップＳ７１０）。

サーチが初回（第１サイクル）である場合は、トラック管理テーブル３０の最初のエントリからサーチを開始する（ステップＳ７１０）。また、ステップＳ７４０で記憶した検索済みトラックがトラック管理テーブル３０の最終エントリ（図１２のトラックｎ）である場合は、ステップＳ７１０での次のトラック検索では、先頭エントリ（図１２のトラック０）に戻る。

このサーチにおいては、トラック管理テーブル３０の当該エントリ中のＩＳクラスタ数３０ｇのフィールド（当該論理トラック中の有効クラスタ数）を参照し、当該エントリＩＳ１３内に有効クラスタを保持している場合は、図示しない新規検索トラックリストに当該エントリの論理トラックアドレスを登録する（ステップＳ７２０）。つぎに、新規検索トラックリストに登録されたトラックの個数を所定の閾値Ｌと比較し、登録数が閾値Ｌより少ない場合は、手順をステップＳ７１０に移行し、トラック管理テーブル３０の次のエントリを前述と同様にして調べる。

このような処理を繰り返すことにより、新規検索トラックリストに閾値Ｌ個分の論理トラックアドレスを登録する（ステップＳ７３０ Ｙｅｓ）。そして、最後に新規検索トラックリストに登録した論理トラックアドレスに対応するトラック管理テーブル３０のエントリ（インデックス）を検索済み最終トラックとして記憶して、今回サイクルの検索を終了する（ステップＳ７４０）。

つぎに、論理ＮＡＮＤ層管理部１２０ｂは、前回落選の論理トラック（図示せず）がリストされている落選トラックリストがあるか否かを判断する（ステップＳ７５０）。初回サイクルの際は、落選トラックリストが存在しないので、新規検索トラックリストと新規追加ブロック内トラックリスト（図示せず）との２つのリストに基づいて２ ^ｉ＋１ 個の論理トラックを選出する（ステップＳ７６０）。新規追加ブロック内トラックリストとは、図３０のステップＳ５００で、ＦＳ１２からＩＳ部１３Ｑに追い出されたブロック（ＦＳ／ＩＳ構造管理テーブル６５のＩＳ入力バッファ管理テーブル６８にエントリされている）に含まれるトラックに関するリストである。

初回サイクルの際は、このような２つのリストを用いて、追い出し候補の２ ^ｉ＋１ 個のトラックを選出する。この選出には、前述したように、トラック内の有効クラスタ数と、有効クラスタ係数とを用いた選出基準（スコア値）Ｓが用いられる。
スコア値Ｓ＝トラック内の有効クラスタ数×有効クラスタ係数
有効クラスタ係数は、トラックがＭＳ部１１Ｑ内で無効トラックが存在する論理ブロックに存在するか否かによって重み付けされる数であり、存在したほうが存在しない場合より数が大きいとする。

有効クラスタ数は、トラック管理テーブル３０のＩＳクラスタ数３０ｇのフィールドを見ることで取得することができる。また、有効クラスタ係数は、トラック管理テーブル３０とトラック管理ポインタ３５ｂのフィールドでリンクしているＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドを見ることで取得することができる。

論理ＮＡＮＤ層管理部１２０ｂは、新規追加ブロック内トラックリストに含まれる複数のトラックから、上記スコア値Ｓが上位のＭ個（所定の設定値）のトラックを選択する。選択されたＭ個のトラックに、先のサーチによって新規検索トラックリストに登録されたＬ個のトラックを加え、これらＬ＋Ｍ個のトラック中から、スコア値Ｓが高い２ ^ｉ＋１ 個のトラックを、ＭＳ１１への追い出しを行うトラックとして選出する。そして、Ｌ＋Ｍ個のトラックのなかで、選出された２ ^ｉ＋１ 個のトラック以外のトラックを、前述の落選トラックリストに登録する。

２回目以降のサイクルの際は、落選トラックリストと、新規検索トラックリストと、新規追加ブロック内トラックリストとの３つのリストに基づいて２ ^ｉ＋１ 個のトラックを選出する（ステップＳ７７０）。なお、２回目以降の、追い出しを行うか否かは、後述する図３０のステップＳ５７０の判断に応じて決められる。３つのリストを用いた選出処理では、落選トラックリストに含まれる複数のトラックから、スコア値Ｓが上位のＮ個（所定の設定値）のトラックを選択し、新規追加ブロック内トラックリストに含まれる複数のトラックから、スコア値Ｓが上位のＭ個（所定の設定値）のトラックを選択し、これらＮ＋Ｍ個のトラックに、さらに今回２回目以降のサイクルの際に得られた新規検索トラックリストに登録されたＬ個のトラックを加え、これらＬ＋Ｍ＋Ｎ個のトラック中から、スコア値Ｓが高い２ ^ｉ＋１ 個のトラックを、ＭＳ１１への追い出しを行うトラックとして選出する。そして、Ｌ＋Ｍ＋Ｎ個の論理トラックのなかで、選出された２ ^ｉ＋１ 個のトラック以外のトラックを、次回サイクルに使用する落選トラックリストに登録する。

つぎに、図３０のステップＳ５４０に戻って説明する。前述のようにして、２論理ブロック分のトラックの追い出し候補が選出されると、論理ＮＡＮＤ層管理部１２０ｂは、該選出された２論理ブロック分のトラック（すなわち２ ^ｉ＋１ 個のトラック）をＭＳＩＢ１１ａのＭＳＦＢ１１ａａに追い出す（ステップＳ５４０）。この追い出しの際、追い出しトラック中のＩＳ部１３Ｑ内に存在しないクラスタについては、ＷＣ２１およびＦＳ部１２、およびＭＳ１１から読み出してマージする前述の受動マージが実行される。なお、上記では、有効クラスタ数とＭＳに穴あきブロックが存在しているか否かの係数とに基づくスコア値Ｓによって追い出しトラックを選出するようにしているが、有効クラスタ数のみによって追い出しトラックを選出するようにしてもよい。

・ＭＳのＣＩＢ処理（図１９ステップＳ３７０）
このようにして、ＩＳ１３からＭＳＩＢ１１ａへの追い出しが発生すると、つぎに、ＭＳ１１のＣＩＢ処理が再び実行される（ステップＳ５６０）。このステップＳ５６０のＭＳ１１のＣＩＢ処理は、先の第１回目のＭＳ１１でのＣＩＢ処理（ステップＳ４００〜Ｓ４２０）と同様なので、重複する説明は省略する。

・ＩＳのＣＩＢ処理
つぎに、論理ＮＡＮＤ層管理部１２０ｂは、ＩＳ１３からＭＳＩＢ１１ａに対する追い出しを再度実行するか否かを判断する（ステップＳ５７０）。すなわち、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ論理ブロック管理テーブル３５およびＦＳ／ＩＳ論理ブロック管理テーブル４２の有効クラスタ数４２ｄのフィールドなどを用いて、ステップＳ５４０での追い出しを行った後のＩＳ１３内の論理ブロックを有効クラスタ数の少ない順にソートし、最も有効クラスタ数の少ない２つの論理ブロックの合計有効クラスタ数が、所定の設定値である２ ^ｋ 個（１論理ブロック分）以上ある場合は、ＩＳ１３からＭＳＩＢ１１ａへの追い出し条件が成立したと判断する（ステップＳ５７０）。

ＩＳ１３からＭＳＩＢ１１ａへの追い出し条件が成立した場合は、手順をステップＳ５４０に移行し、図３１のステップＳ７００〜Ｓ７５０およびＳ７７０の処理を実行することで、上記の２論理ブロック分の追い出し処理を再度実行する。ステップＳ５７０の判断がＹＥＳである限り、ＩＳ１３からＭＳＩＢ１１ａへの２論理ブロック分の追い出し処理と、ＭＳ１１でのＣＩＢ処理が繰り返し実行される。そして、ステップＳ５７０の判断がＮＯとなった場合は、ＩＳ１３でのコンパクション処理が実行される（ステップＳ５８０）。

ＩＳコンパクション処理では、ＭＳ論理ブロック管理テーブル３５およびＦＳ／ＩＳ論理ブロック管理テーブル４２の有効クラスタ数４２ｄのフィールドなどを用いて、ＩＳ部１３Ｑ内の有効クラスタの少ない論理ブロックから順にクラスタを１論理ブロック分、すなわち２ ^ｋ 個集め、これら２ ^ｋ 個のクラスタをＩＳコンパクションバッファ１３ｃにＣｏｐｙする。このＣｏｐｙ処理が終了すると、論理ＮＡＮＤ層管理部１２０ｂは、コンパクション元（Ｃｏｐｙ元）の論理ブロックのうち有効クラスタがなくなったものを無効論理ブロックとして物理ＮＡＮＤ層管理部１２０ｃに返却し、コンパクション処理によって有効クラスタが詰まった論理ブロックで構成されるＩＳコンパクションバッファ１３ｃをＩＳ１３にＭｏｖｅする。

このコンパクションの後、ＩＳＩＢ１３ａ中のフルになった論理ブロックはＩＳ１３にＭｏｖｅされる（ステップＳ５８５）。このＭｏｖｅ処理は、具体的には、ＦＳ／ＩＳ構造管理テーブル６５のＩＳ入力バッファ管理テーブル６８のＩＳＩＢ用フィールドに登録されている該当する論理ブロックＩＤを削除するのみである。

この後、論理ＮＡＮＤ層管理部１２０ｂは、前述したＦＳ１２からＩＳＩＢ１３ａへの追い出し条件が成立しているか否かを判断し（ステップＳ５９０）、このＦＳ１２からＩＳＩＢ１３ａへの追い出し条件が成立している場合は、手順をステップＳ５００に移行し、上述した手順を再度繰り返す。また、論理ＮＡＮＤ層管理部１２０ｂは、ＩＳコンパクション処理の終了後、ＦＳ１２からＩＳＩＢ１３ａへの追い出し条件が成立していないと判断した場合は、これで今回の書き込み処理を終了する。以上が、書き込み処理の詳細である。

つぎに、本実施の形態の要部について詳細に説明する。前述したように、２ ^ｉ トラックＭＳコンパクションまたは２ ^ｉ トラック未満ＭＳコンパクションを行なう際には、予めＭＳ論理ブロック管理テーブル３５の有効トラック数３５ｃのフィールドなどを参照することにより、ＭＳＩＢ１１ａおよびＴＦＳ１１ｂに含まれないＭＳ１１中の論理ブロックのうち無効にされたトラックを持つものを、論理ブロック内の有効トラック数でソートしている。そこで、以下ではＭＳ１１中の論理ブロックを有効トラック数によって効率良く管理し、コンパクションを高速化する方法について説明する。

前述したように、ＭＳ１１のコンパクションには、図１４に示したＭＳ論理ブロック管理テーブル３５が使用される。本実施の形態では、ＭＳ１１のコンパクションの処理時間を短縮化するために、論理ブロック内の有効トラック数を、有効トラック数ごとのリンクドリスト（リンクリスト）で管理する。具体的には、ＭＳ論理ブロック管理テーブル３５内で、有効トラック数ごとのリンクドリストが形成される。

図３２は、有効トラック数ごとのリンクドリストを有したＭＳ論理ブロック管理テーブルの一例を示す図である。図３２に示すように、ここでのＭＳ論理ブロック管理テーブル３５は、論理ブロックＩＤ３５ａをインデックスとした配列形式で構成され、各エントリは、トラック管理ポインタ３５ｂ、有効トラック数３５ｃ、書き込み可能先頭トラック３５ｄ、Validフラグ３５ｅの他に、prevポインタ３５ｇとnextポインタ３５ｈとが追加されて構成されている。

前述したように、有効トラック数３５ｃは、論理ブロックＩＤ３５ａで指定される当該論理ブロックに記憶されているトラックのうちの有効なものの個数（最大２ ^ｉ 個）を示している。

また、ＭＳ論理ブロック管理テーブル３５では、prevポインタ３５ｇとnextポインタ３５ｈとによって、有効トラック数毎にリンクドリスト構造が形成されている。nextポインタ３５ｈは、有効トラック数毎にリンクされる次のエントリへのポインタを示し、prevポインタ３５ｇは、有効トラック数毎にリンクされる１つ前のエントリへのポインタを示している。

図３３は、リンクドリストの構造を説明するための図である。有効トラック数１、有効トラック数２、…、有効トラック数２ ^ｉ の各リンクドリストは、同様の構造を有しているので、ここではリンクドリストの一例として有効トラック数１のリンクドリストについて説明する。

ＭＳ論理ブロック管理テーブル３５は、有効トラック数１のリスト先頭ポインタを有している。リスト先頭ポインタは、ＭＳ論理ブロック管理テーブル３５の各有効トラック数の先頭エントリへのポインタである。ＭＳ論理ブロック管理テーブル３５の末尾には、リンクドリスト管理用の特別なエントリ（図示せず）を設けておき、このエントリに各有効トラック数に対応するリスト先頭ポインタを格納しておく。

有効トラック数１の論理ブロックＩＤを検索する場合には、まず有効トラック数１のリスト先頭ポインタに基づいて、有効トラック数１の先頭のエントリを検索する。図３３では、ブロック０が有効トラック数１の先頭のエントリである場合を示している。

ＭＳ論理ブロック管理テーブル３５では、各論理ブロックＩＤ３５ａがprevポインタ３５ｇやnextポインタ３５ｈと対応付けられており、prevポインタ３５ｇやnextポインタ３５ｈによって、前のエントリや次のエントリが示されている。

図３３では、ブロック０のnextポインタ３５ｈが、有効トラック数１の次のエントリ（ブロック０の次のエントリ）としてブロック８のエントリを示している。また、ブロック８のnextポインタ３５ｈは、有効トラック数１の次のエントリ（ブロック８の次のエントリ）としてブロックＸのエントリを示している。また、ブロックＸのprevポインタ３５ｇは、有効トラック数１の１つ前のエントリとしてブロック８のエントリを示している。また、ブロック８のprevポインタ３５ｇは、有効トラック数１の１つ前のエントリとしてブロック０のエントリを示している。

論理ＮＡＮＤ層管理部１２０ｂは、有効トラック数１の先頭のエントリとしてブロック０を検索すると、ブロック０のnextポインタ３５ｈに基づいて、有効トラック数１の次のエントリとしてブロック８を検索する。さらに、論理ＮＡＮＤ層管理部１２０ｂは、有効トラック数１のエントリとしてブロック８を検索すると、ブロック８のnextポインタ３５ｈに基づいて、有効トラック数１の次のエントリとしてブロックＸを検索する。このように、論理ＮＡＮＤ層管理部１２０ｂは、有効トラック数１のエントリを順番に検索し、検索したエントリの論理ブロックを用いてコンパクション処理を行なう。

図３３では、有効トラック数１の論理ブロックを検索する場合について説明したが、ＭＳ論理ブロック管理テーブル３５では、有効トラック数が１個の論理ブロック、有効トラック数が２個の論理ブロック、…、有効トラック数が２ ^ｉ 個（１論理ブロック分）の論理ブロックがそれぞれリンクドリスト構造を有している。したがって、論理ＮＡＮＤ層管理部１２０ｂは、有効トラック数ごとに論理ブロックを検索することが可能である。

このように、ＭＳ論理ブロック管理テーブル３５内から有効トラック数ごとに論理ブロックを検索できるので、コンパクションに用いる適切な論理ブロック（有効トラック数の少ない論理ブロック）をＭＳ論理ブロック管理テーブル３５から高速に見つけ出すことが可能となる。リンクドリストがない場合に、有効トラック数の少ない論理ブロックを抽出するには、例えばＭＳ論理ブロック管理テーブル３５を論理ブロック０から順番にサーチする作業が必要になる。しかしながら、この方法では、ＭＳ論理ブロック管理テーブル３５内を最後までサーチしないと、最適解が得られない可能性がある。

また、有効トラック数毎に論理ブロックを抽出する方法として、図２８に示した有効トラック数別論理ブロックＩＤリスト６２を用いる方法がある。この方法では、論理ＮＡＮＤ層管理部１２０ｂが、ＭＳ１１内でのコンパクションを行なう前に、ＭＳ１１中の論理ブロック（論理ブロックＩＤ）を有効トラック数によってソートしておかなければならない。

一方、本実施の形態では、リンクドリストを用いて有効トラック数の少ない論理ブロックから順番にＭＳ論理ブロック管理テーブル３５内をサーチできるので、コンパクションを効率良く行なうのに必要な、有効トラック数の少ない論理ブロックの集合を容易に見つけることが可能となる。また、コンパクションを行う際に、有効トラック数別論理ブロックＩＤリスト６２が不要となる。このため、狭い領域で効率良くコンパクションに関する管理を行うことが可能となる。

図３４は、有効トラック数ごとのリンクドリストを説明するための図である。同図では、有効トラック数１のリスト先頭ポインタＰ１がブロック０を示し、有効トラック数２のリスト先頭ポインタＰ２がブロック３を示し、有効トラック数２ ^ｉ のリスト先頭ポインタＰｉがブロック１を示している。

有効トラック数１の論理ブロックは、ブロック０、ブロック７の順番でリンクドリストを形成（連結）している。また、有効トラック数２の論理ブロックは、ブロック３、ブロック９、ブロック４、ブロック８の順番でリンクドリストを形成している。また、有効トラック数２ ^ｉ の論理ブロックは、ブロック１、ブロック２、ブロック５、ブロック６の順番でリンクドリストを形成している。

したがって、論理ＮＡＮＤ層管理部１２０ｂが有効トラック数１の論理ブロックを検索すると、ブロック０、ブロック７の順番で論理ブロックを検索でき、有効トラック数２の論理ブロックを検索すると、ブロック３、ブロック９、ブロック４、ブロック８の順番で論理ブロックを検索できる。また、論理ＮＡＮＤ層管理部１２０ｂが有効トラック数２ ^ｉ の論理ブロックを検索すると、ブロック１、ブロック２、ブロック５、ブロック６の順番で論理ブロックを検索できる。

ところで、有効トラック数が少ない論理ブロックを集めてコンパクションを行なうと、無駄なデータの移動が少なくなるので、効率良くコンパクションを行なえる。したがって、本実施の形態では、有効トラック数が少ないものが優先される順番で論理ブロックを抽出し、抽出した順番で論理ブロックのコンパクションを行なう。

具体的には、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ論理ブロック管理テーブル３５内から、リンクドリストを用いて有効トラック数１の論理ブロックを順番に抽出し、有効トラック数１の論理ブロックが２ ^ｉ （１論理ブロック分）集まる場合には、ＭＳコンパクションバッファ１１ｃを介した２ ^ｉ トラックＭＳコンパクションを実行する。そして、論理ＮＡＮＤ層管理部１２０ｂは、ＭＳ論理ブロック管理テーブル３５内から有効トラック数１の論理ブロックが２ ^ｉ 個集まる度に、２ ^ｉ トラックＭＳコンパクションを実行する処理を繰り返す。有効トラック数が１個の論理ブロックを２ ^ｉ 個集めることが不可能な状態になると、論理ＮＡＮＤ層管理部１２０ｂは、論理ブロックから有効トラックを（２ ^ｉ −１）よりも少ない個数だけ集める、ＭＳ追記ＩＢ１１ａｂを介した２ ^ｉ トラック未満コンパクションを実行する。

なお、ここでは有効トラック数２ ^ｉ （最大数）の論理ブロックについてもリンクドリストを形成する場合について説明したが、有効トラック数２ ^ｉ の論理ブロックはコンパクション対象から除外してもよい。この場合、有効トラック数１〜（２ ^ｉ −１）個の各論理ブロックについてリンクドリストを形成すればよい。

なお、prevポインタ３５ｇ、nextポインタ３５ｈ、リスト先頭ポインタは、以下の場合に更新される。
・新規にＴＦＳ１１ｂに論理ブロックが登録されたとき
・新規にＭＳ１１に論理ブロックが登録されたとき
・論理ブロックが持っているトラックと同じアドレスのトラックが他の論理ブロックに再書込みされて、元ブロック側がInvalidateされた場合（有効トラック数が減った場合）
別言すれば、論理ブロックがＭＳ１１に利用され始めてから開放されるまで、有効トラック数が変化するたびに、prevポインタ３５ｇ、nextポインタ３５ｈ、リスト先頭ポインタは、該当するリスト（エントリ）に繋ぎ替えられる。

また、コンパクションが完了した論理ブロックは、ＭＳ論理ブロック管理テーブル３５内のエントリから削除され、コンパクションによって発生した新たな論理ブロックは、ＭＳ論理ブロック管理テーブル３５に登録される。

なお、本実施の形態では、ＭＳ論理ブロック管理テーブル３５内における各有効トラック数の先頭のエントリ（論理ブロックＩＤ）をリスト先頭ポインタによって指定する場合について説明したが、リスト先頭ポインタは無くてもよい。この場合は、検索対象となっている有効トラック数を有したエントリの何れか１つをＭＳ論理ブロック管理テーブル３５から検索し、その後、検索したエントリのprevポインタ３５ｇやnextポインタ３５ｈを用いて検索対象の有効トラック数を有した論理ブロックＩＤを順番に検索する。

また、本実施の形態では、prevポインタ３５ｇとnextポインタ３５ｈとによって、有効トラック数毎にリンクドリスト構造を形成したが、nextポインタ３５ｈのみによって、有効トラック数毎にリンクドリスト構造を形成してもよい。

また、本実施の形態では、ＭＳ論理ブロック管理テーブル３５にリンクドリストを適用して有効トラック数毎に論理ブロックを管理したが、ＦＳ/ＩＳ論理ブロック管理テーブル４２にリンクドリストを適用して有効クラスタ数毎に論理ブロックやＦＳ／ＩＳブロックを管理してもよい。

このように本実施の形態では、ＭＳ論理ブロック管理テーブル３５内で論理ブロックを有効トラック数毎にリンクドリストで管理しているので、有効トラック数毎の論理ブロックをＭＳ１１内から容易かつ迅速に検索できる。また、有効トラック数の少ない論理ブロックから順番にコンパクションを行なうことができるので、無駄なデータ移動を増やすことなく、効率良くコンパクションを行なうことが可能となる。

また、ＭＳ論理ブロック管理テーブル３５内では、各有効トラック数の先頭のエントリをリスト先頭ポインタによって指定しているので、有効トラック数毎の論理ブロックの検索が容易になる。

また、prevポインタ３５ｇとnextポインタ３５ｈとによる双方向リンクドリストによって、有効トラック数毎に論理ブロックを管理しているので、ある論理ブロックの有効ブロック数が減少した際には、その論理ブロックを別のリンクドリストに容易に繋ぎ代えることが可能となる。

ＳＳＤの構成例を示すブロック図。 ＮＡＮＤメモリチップに含まれる１個のブロックの構成例と、４値データ記憶方式でのしきい値分布を示す図。 ドライブ制御回路のハードウェア的な内部構成例を示すブロック図。 プロセッサの機能構成例を示すブロック図。 ＮＡＮＤメモリおよびＤＲＡＭ内に形成された機能構成を示すブロック図。 ＷＣからＮＡＮＤメモリへの書き込み処理に係わるより詳細な機能ブロック図。 ＬＢＡ論理アドレスを示す図。 データ管理部内の管理テーブルの構成例を示す図。 ＲＣクラスタ管理テーブルの一例を示す図。 ＷＣクラスタ管理テーブルの一例を示す図。 ＷＣトラック管理テーブルの一例を示す図。 トラック管理テーブルの一例を示す図。 ＦＳ／ＩＳ管理テーブルの一例を示す図。 ＭＳ論理ブロック管理テーブルの一例を示す図。 ＦＳ／ＩＳ論理ブロック管理テーブルの一例を示す図。 ＦＳ／ＩＳ内クラスタ管理テーブルの一例を示す図。 論物変換テーブルの一例を示す図。 読み出し処理の動作例を示すフローチャート。 書き込み処理の動作例を示すフローチャート。 各構成要素間のデータの流れにおける入力と出力の組み合わおよびその発生要因を示す図。 ＷＣからＮＡＮＤメモリへの書き込み処理に係わるさらにより詳細な機能ブロック図。 データ管理部内の管理テーブルの他の構成例を示す図。 並列動作要素とプレーンとチャネルの関係を示す図。 論物変換テーブルの他の例を示す図。 ＢＢ管理テーブルの一例を示す図。 ＦＢ管理テーブルの内部構成例を示す図。 ＮＡＮＤメモリの論理ブロックと物理ブロックとの対応関係を示す図。 ＭＳ構造管理テーブルの一例を示す図。 ＦＳ／ＩＳ構造管理テーブルの一例を示す図。 書き込み処理の動作例を示す詳細なフローチャート。 ＩＳの追い出し動作例を示すフローチャート。 有効トラック数ごとのリンクドリストを有したＭＳ論理ブロック管理テーブルの一例を示す図。 リンクドリストの構造を説明するための図。 有効トラック数ごとのリンクドリストを説明するための図。

符号の説明

１０ ＮＡＮＤメモリ、１１、メインストレージ（ＭＳ）、１１ａ メインストレージ入力バッファ（ＭＳＩＢ）、１１ａａ フルブロック入力バッファ（ＭＳＦＢ）、１１ａｂ ＭＳ追記入力バッファ（ＭＳ追記ＩＢ）、１１ｂ トラック前段バッファ（ＴＦＳ）、１２ 前段ストレージ（ＦＳ）、１２ａ 前段ストレージ入力バッファ（ＦＳＩＢ）、１３ 中段ストレージ（ＩＳ）、１３ａ 中段ストレージ入力バッファ（ＩＳＩＢ）、１３ａ 中段ストレージ本体（ＩＳ本体）、２０ ＤＲＡＭ、２１ ライトキャッシュ（Ｗ
Ｃ）、２２、リードキャッシュ（ＲＣ）、１２０ データ管理部、 １２０ａ ＤＲＡＭ層管理部、１２０ｂ 論理ＮＡＮＤ層管理部、１２０ｃ 物理ＮＡＮＤ層管理部。

Claims (11)

1. データ消去単位であるブロックを複数有する不揮発性の半導体記憶素子と、
   前記ブロック内の有効なデータを前記ブロックのサイズよりも小さい所定の管理単位で選択して、異なるブロック内に書き直すコンパクション処理を実行するコントローラと、を具備し、
   前記コントローラは、
   前記コンパクション処理を実行する際には、前記ブロックに含まれる有効な前記管理単位のデータの個数毎に前記ブロックをリンクドリスト形式で管理する管理テーブル内から、前記コンパクション処理の対象とするブロックを検索し、検索したブロックを用いてコンパクション処理を実行することを特徴とするメモリシステム。
2. 前記コントローラは、前記コンパクション処理を実行する際には、前記リンクドリストに従って前記管理テーブル内から有効な前記管理単位のデータの個数が少ない順番でブロックを検索し、検索したブロックを用いてコンパクション処理を実行することを特徴とする請求項１に記載のメモリシステム。
3. 前記コントローラは、前記リンクドリストの先頭ポインタとして、前記管理テーブル内の所定のリスト位置に登録されているブロックを設定することを特徴とする請求項１に記載のメモリシステム。
4. 前記コントローラは、前記コンパクション処理を開始する際に、検索対象とする有効な前記管理単位のデータの個数に応じたブロックを前記管理テーブル内から検索し、その後リンクドリストに従って前記管理テーブル内からブロックを検索することを特徴とする請求項１に記載のメモリシステム。
5. 前記コントローラは、前記コンパクション処理を実行する際に、検索したブロック内に含まれる有効な前記管理単位のデータの合計数が前記ブロックのサイズ以上となった場合に、未書き込みのブロックを新たに取得して有効な前記管理単位のデータを書き直すことを特徴とする請求項１に記載のメモリシステム。
6. 前記コントローラは、前記コンパクション処理を実行する際に、検索した前記ブロック内に含まれる有効な前記管理単位のデータの合計数が前記ブロックのサイズに満たない場合に、追記書き込み用の入力バッファに割り当てられているブロックに有効な前記管理単位のデータを書き直すことを特徴とする請求項１に記載のメモリシステム。
7. 前記管理テーブルは、前記ブロックに含まれる有効な前記管理単位のデータの個数毎に、有効な前記管理単位のデータの個数に対応する次のブロックが順番にリンクされた正順方向リンクで繋げられており、
   前記コントローラは、前記正順方向リンクを用いて、前記管理テーブル内から前記コンパクション処理の対象とするブロックを検索することを特徴とする請求項１に記載のメモリシステム。
8. 前記管理テーブルは、前記ブロックに含まれる有効な前記管理単位のデータの個数毎に、有効な前記管理単位のデータの個数に対応する１つ前のブロックが逆順にリンクされた逆順方向リンクで繋げられており、
   前記コントローラは、前記ブロックに含まれる有効な前記管理単位のデータの個数が減少した場合に、前記正順方向リンク及び逆順方向リンクを用いて前記管理テーブル内のエントリを繋ぎかえることを特徴とする請求項７に記載のメモリシステム。
9. 前記ブロックは、前記管理単位の自然数倍のサイズであることを特徴とする請求項１に記載のメモリシステム。
10. 前記ブロックは、書き込み単位である複数のページから構成され、前記管理単位は、前記ページの自然数倍のサイズであることを特徴とする請求項９に記載のメモリシステム。
11. 前記ブロックは、書き込み単位である複数のページから構成され、前記ページは、前記管理単位の自然数倍のサイズであることを特徴とする請求項９に記載のメモリシステム。

Images