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

Abstract

【課題】管理テーブルの検索処理を高速化する。
【解決手段】第１の論理単位位置内における第２、第３の記憶部を第４の単位で分割した第２の論理単位位置と、第２の論理アドレスのエントリへのリンク情報とを含む情報を管理する正引きの第１の管理テーブルと、第２の記憶部の第１の論理単位位置内における第２の記憶部を第５の単位で分割した第３の論理単位位置と第４の管理テーブルのインデックスへのリンク情報とを含む情報を管理する複数の管理テーブルを有する正引きの第２の管理テーブルと、第２、第３の記憶部で使用されている第２の論理アドレスに関する情報を含む情報を管理する逆引きの第３の管理テーブルと、第２の記憶部の当該第１の論理単位位置内における第３の論理単位位置毎に第２の管理テーブルの第３の論理アドレスへのリンク情報を保持することで、第３の論理アドレスを含む情報を管理する第４の管理テーブルとを備える。
【選択図】図８

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フラグ３５ｅなどの書き込みの際の追い出し処理、コンパクション処理などに必要な情報を保持している。ＭＳ論理ブロック管理テーブル３５が、特許請求の範囲でいうところの第３の管理テーブルに対応する。

図１５に示す逆引きのＦＳ／ＩＳ論理ブロック管理テーブル４２は、ＦＳ／ＩＳブロックＩＤ４２ａをインデックスとして、ＦＳ部１２ＱまたはＩＳ部１３Ｑとして利用されている論理ブロック内に、どの論理クラスタアドレスが記憶されているかを示す情報を管理するためのテーブルであり、そのためにＦＳ／ＩＳ内クラスタ管理テーブル４４へのポインタ（Ａ３参照）であるブロック内クラスタテーブル４２ｃのフィールドを有している。また、ＦＳ／ＩＳ論理ブロック管理テーブル４２は、ＦＳ／ＩＳブロックＩＤ４２ａをインデックスとして、有効クラスタ数４２ｄ、書き込み可能先頭ページ４２ｅ、Validフラグ４２ｆなどの書き込みの際の追い出し処理、コンパクション処理などに必要な情報を保持している。

図１６に示す逆引きのＦＳ／ＩＳ内クラスタ管理テーブル４４では、ＦＳ部１２Ｑ、ＩＳ部１３Ｑとして利用されている１論理ブロック中の各クラスタ位置（ＮＡＮＤメモリ１０をクラスタ単位で分割した単位の位置）が、テーブル上のエントリ位置に対応して管理されている。また、各エントリ４４ａの内容は、当該クラスタ位置にどの論理クラスタが記憶されているかが識別できるように、ＦＳ／ＩＳ管理テーブル４０で管理される該当論理クラスタアドレスを含むリスト（リンクドリスト中の１つのリスト）へのリンク情報としてのポインタ（Ａ４参照）が登録されている。ＦＳ／ＩＳ論理ブロック管理テーブル４２およびＦＳ／ＩＳ内クラスタ管理テーブル４４が特許請求の範囲でいうところの第４の管理テーブルに対応する。

このようにＮＡＮＤメモリ１０内のトラック管理においては、トラック管理テーブル３０のインデックスとしての論理トラックアドレス３０ａと、ＭＳ論理ブロック管理テーブル３５のトラック管理ポインタ３５ｂのフィールドとをリンクさせて、トラック管理テーブル３０を正引きのテーブルとして構成するとともにＭＳ論理ブロック管理テーブル３５を逆引きのテーブルとして構成したので、書き込み処理の際に、追い出し、コンパクション、テーブル更新などの各種処理を実行するときの管理テーブルの検索処理を高速化することが可能となる。

例えば、ＭＳコンパクションの際には、論理トラックの格納位置が変化するが、これに応じて、ＭＳ論理ブロック管理テーブル３５と、トラック管理テーブル３０を変更する必要がある。すなわち、論理トラックの格納位置が変化に応じてＭＳ論理ブロック管理テーブル３５の対応するインデックスの各フィールド（トラック管理ポインタ３５ｂ，有効トラック数３５ｃ、書き込み可能先頭トラック位置３５ｄなど）を変更しさらに、この後で、トラック管理テーブル３０内の論理ブロックＩＤ３０ｃ、論理ブロック内トラック位置３０ｄなどの所要の情報も変更する必要がある。

このような状況下で、本実施の形態においては、ＭＳ論理ブロック管理テーブル３５のトラック管理ポインタ３５ｂのフィールドに、論理トラック自体を登録するのではなく、トラック管理テーブル３０のインデックスへのポインタを登録しているので、検索を行うことなくトラック管理テーブル３０の該当インデックスのエントリへ飛び、該当エントリ内の所要情報を変更することが可能となる。これに対し、トラック管理ポインタ３５ｂのフィールドに、該当する論理トラックアドレス自体を登録するようにした場合は、ＭＳ論理ブロック管理テーブル３５の該当エントリの変更作業を行った後、トラック管理テーブル３０のインデックスを１つづつ辿りながら、該当する論理トラックアドレス３０ａを検索する処理を行わなければならず、この検索の後、該当する論理トラックアドレス４０ａのエントリ内の所要情報を変更することになり、本実施の形態に比べ管理テーブルの更新作業速度が大幅に落ちることになる。

また、ＮＡＮＤメモリ１０のクラスタ管理においては、ＦＳ／ＩＳ論理ブロック管理テーブル４２のブロック内クラスタテーブル４２ｃからＦＳ／ＩＳ内クラスタ管理テーブル４４へリンクさせるとともに、ＦＳ／ＩＳ内クラスタ管理テーブル４４のエントリ４４ａとＦＳ／ＩＳ管理テーブル４０とをリンクさせて、ＦＳ／ＩＳ内クラスタ管理テーブル４４を正引きのテーブルとして構成するとともに、ＦＳ／ＩＳ論理ブロック管理テーブル４２およびＦＳ／ＩＳ内クラスタ管理テーブル４４を逆引きのテーブルとして構成したので、書き込み処理の際に、追い出し、コンパクション、テーブル更新などの各種処理を実行するときの管理テーブルの検索処理を高速化することが可能となる。

例えば、ＩＳコンパクションを行う際に、論理クラスタの格納位置が変化するが、これに応じて、ＦＳ／ＩＳ論理ブロック管理テーブル４２、ブロック内クラスタテーブル４２ｃおよびＦＳ／ＩＳ内クラスタ管理テーブル４４を変更する必要がある。すなわち、論理クラスタの格納位置が変化に応じてＦＳ／ＩＳ論理ブロック管理テーブル４２の対応するインデックスの各フィールド（論理ブロックＩＤ４２ｂ，ブロック内クラスタテーブル４２ｃ、有効クラスタ数４２ｄ、書き込み可能先頭ページ４２ｅなど）を変更するとともに、ＦＳ／ＩＳ内クラスタ管理テーブル４４の各エントリの登録データを変更し、さらに、この後で、ＦＳ／ＩＳ管理テーブル４０の該当論理クラスタアドレス内の、論理ブロックＩＤ４０ｂ、論理ブロック内クラスタ位置４０ｃなどの所要の情報も変更する必要がある。

このような状況下で、本実施の形態においては、ＦＳ／ＩＳ内クラスタ管理テーブル４４の各エントリに、論理クラスタアドレス自体を登録するのではなく、ＦＳ／ＩＳ管理テーブル４０で管理される該当論理クラスタアドレスを含むリストへのポインタ４４ａ（Ａ４参照）を登録しているので、検索を行うことなくＦＳ／ＩＳ内クラスタ管理テーブル４４の該当エントリからＦＳ／ＩＳ管理テーブル４０の該当論理クラスタアドレスを含むリストへ飛び、該当リスト内の所要情報を変更することが可能となる。これに対し、ＦＳ／ＩＳ内クラスタ管理テーブル４４の各エントリに、該当する論理クラスタアドレス自体を登録するようにした場合は、ＦＳ／ＩＳ内クラスタ管理テーブル４４の各エントリの変更作業を行った後、ＦＳ／ＩＳ管理テーブル４０でリンクドリストを１つづつ辿りながら、該当する論理クラスタアドレス４０ａを検索する処理を行わなければならず、この検索の後、該当する論理クラスタアドレス４０ａの内の所要情報を変更することになり、本実施の形態に比べ管理テーブルの更新作業速度が大幅に落ちることになる。

また、本実施の形態においては、トラック管理テーブル３０は、ＦＳ／ＩＳ管理テーブル４０の先頭エントリへのリンク情報としてのポインタであるクラスタテーブルポインタ３０ｅを有し、かつＦＳ／ＩＳ管理テーブル４０は、論理トラックアドレス毎に独立なリンクドリストとなっており、これにより検索処理を高速化しつつ、管理テーブルとして必要なメモリ量を削減することができる。例えば、クラスタ管理するＦＳ／ＩＳ管理テーブル４０がリンクドリストでなく通常のテーブル（現在クラスタ管理で管理されているクラスタアドレスと格納位置で構成）であったとすると、ＦＳ部１２ＱまたはＩＳ部１３Ｑ上に存在するクラスタを検索するのに、最悪の場合、このテーブル全体を検索しなくてはいけない場合があり、検索に極端に時間がかかる場合がある。検索を速くするために、ＬＢＡ領域に対応する全てのクラスタアドレスのエントリを持つテーブルを用意することも考えられるが、管理テーブルのサイズが極端に大きくなる。これに対し、本実施の形態においては、論理トラックアドレスでインデックスされているトラック管理テーブル３０は、論理トラックアドレス毎に独立なリンクドリストとなっているＦＳ／ＩＳ管理テーブル４０の先頭エントリへのポインタをもつようにしているので、検索処理を高速化しつつ、管理テーブルに要するメモリ量も節約することが可能となる。

このように本実施の形態においては、トラック、クラスタ単位にそれぞれ、正引き、逆引きのテーブルを持たせ、かつこれらテーブルをリンクさせるようにしたので、管理テーブルの検索処理速度を高速化することが可能となる。また、本実施の形態では、ＷＣトラック管理テーブル２４、ＦＳ／ＩＳ管理テーブル４０をリンクドリストで構成したので、テーブル更新作業が軽減され、また管理テーブルを小容量することが可能となる。

なお、本実施の形態で言うところのセクタが特許請求の範囲の第１の単位に対応し、同様に、ページが第２の単位に対応し、ブロックが第３の単位に対応し、トラックが第４の単位に対応し、クラスタが第５の単位に対応し、セクタ単位のＬＢＡが第１の論理アドレスに対応し、トラックアドレスが第２の論理アドレスに対応し、クラスタアドレスが第３の論理アドレスに対応し、論理ブロック位置（論理ブロックＩＤ）が第１の論理単位位置に対応し、論理トラック位置が第２の論理単位位置に対応し、論理クラスタ位置が第３の論理単位位置に対応している。これら第１〜第５の単位としては、上記実施の形態で示したセクタ、ページ、ブロック、トラック、クラスタに限ることなく他の任意の単位を採用するようにしてもよい。

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

符号の説明

１ ホスト装置、１０ ＮＡＮＤメモリ、１１、メインストレージ領域（ＭＳ）、１１ａ ＭＳ入力バッファ（ＭＳＩＢ）、１１ｂ トラック前段ストレージ領域（ＴＦＳ）、１２ 前段ストレージ領域（ＦＳ）、１２ａ ＦＳ入力バッファ（ＦＳＩＢ）、１３ 中段ストレージ領域（ＩＳ）、２０ ＤＲＡＭ、２１ ライトキャッシュ（ＷＣ）、２２ リードキャッシュ（ＲＣ）、３０ トラック管理テーブル、３５ ＭＳ論理ブロック管理テーブル、４０ ＦＳ／ＩＳ管理テーブル、４２ ＦＳ／ＩＳ論理ブロック管理テーブル、４４ ＦＳ／ＩＳ内クラスタ管理テーブル。

Claims (3)

1. ホスト装置に対し第１の単位で読み出し／書き込みが行われる揮発性の半導体記憶素子から構成される第１の記憶部と、
   前記第１の単位の自然数倍である第２の単位で読み出し／書き込みが行われ、前記第２の単位の２以上の自然数倍である第３の単位で消去が行われる不揮発性の半導体記憶素子から構成される第２の記憶部と、
   前記第３の単位の自然数分の１である第４の単位で読み出し／書き込みが行われ、前記第３の単位で消去が行われる不揮発性の半導体記憶素子から構成される第３の記憶部と、
   ホスト装置から前記第１の単位で前記第１の記憶部に書き込まれた複数のデータを前記第２の記憶部に書き込み、前記第１の記憶部に書き込まれた複数のデータを前記第４の単位で前記第３の記憶部に書き込み、前記第２の記憶部に書き込まれた複数のデータを前記第４の単位で前記第３の記憶部に書き込む、書き込み処理と、前記第２の記憶部を第４の単位の自然数分の１である第５の単位で管理し、前記第３の記憶部を第４の単位で管理する管理処理と、前記第１、第２の記憶部に記憶されたデータを読み出して前記第１の記憶部を介して前記ホスト装置に転送する読み出し処理を実行するコントローラと、
   を備えるメモリシステムであって、
   ホスト装置から指定される第１の単位でアラインされた第１の論理アドレスを前記第４の単位でアラインした第２の論理アドレスをインデックスとして、前記第２、第３の記憶部を前記第３の単位で分割した第１の論理単位位置内における前記第２、第３の記憶部を前記第４の単位で分割した第２の論理単位位置と、第２の管理テーブルの対応する第２の論理アドレスのエントリへのリンク情報とを含む情報を管理する正引きの第１の管理テーブルと、
   前記第２の論理アドレスのエントリ毎に、ホスト装置からの論理アドレスを前記第５の単位でアラインした第３の論理アドレス単位で、前記第２の記憶部の第１の論理単位位置内における前記第２の記憶部を前記第５の単位で分割した第３の論理単位位置と第４の管理テーブルのインデックスへのリンク情報とを含む情報を管理する複数の管理テーブルを有する正引きの第２の管理テーブルと、
   前記第１の論理単位位置をインデックスとして、前記第１の管理テーブルのインデックスとしての第２の論理アドレスへのリンク情報を保持することで、前記第２、第３の記憶部で使用されている前記第２の論理アドレスに関する情報を含む情報を管理する逆引きの第３の管理テーブルと、
   前記第１の論理単位位置に対応する情報をインデックスとして、第２の記憶部の当該第１の論理単位位置内における第３の論理単位位置毎に前記第２の管理テーブルの第３の論理アドレスへのリンク情報を保持することで、第２の記憶部の第１の論理単位位置内における第３の論理単位位置に対応する第３の論理アドレスを含む情報を管理する第４の管理テーブルと、
   前記第１の論理単位位置毎に、該第１の論理単位位置に対応付けられた前記第２、第３の記憶部の物理的な位置を管理する第５の管理テーブルと、
   を備え、コントローラは、前記第１の〜第５の管理テーブルに基づいて前記書き込み処理、管理処理および読み出し処理を実行することを特徴とするメモリシステム。
2. 前記第２の管理テーブルにおいて、複数の管理テーブルは、リンクドリスト形式で構成されていることを特徴とする請求項１に記載のメモリシステム。
3. 前記第１の単位はセクタであり、前記第２の単位はページであり、前記第３の単位はブロックであり、前記第４の単位はトラックであり、前記第５の単位はクラスタであり、前記第１の論理アドレスはセクタアドレスであり、前記第２の論理アドレスはトラックアドレスであり、前記第３の論理アドレスはクラスタアドレスであり、第１の論理単位位置は論理ブロック位置であり、前記第２の論理単位位置は論理トラック位置であり、前記第３の論理単位位置は論理クラスタ位置であることを特徴とする請求項１または２に記載のメモリシステム。

Images