(57)【特許請求の範囲】
【請求項１】
複数のブロックを含み、ブロック単位でのみ消去可能であり、各ブロックは有効ユーザーデータから成る有効セクタと、無効データから成るダーティセクタとを記憶している固体メモリディスクをクリーンアップする方法において、
ａ）総ダーティメモリが総空きメモリと総ダーティメモリとの和の設定されたパーセンテージを越えたときに、固体メモリディスクをクリーンアップする必要があると決定する過程と；
ｂ）クリーンアップすべき第１のブロックを選択する過程と；
ｃ）第１のブロックの中に位置する有効セクタを記憶するのに十分な量のメモリを第２のブロックで割当てる過程と；
ｄ）第１のブロックから第２のブロックへ有効セクタをコピーする過程と；
ｅ）第１のブロックを消去する過程とから成る方法。
【請求項２】
浮動セクタデータを記憶し、複数のブロックを含み、ブロック単位でのみ消去可能であり、各ブロックは有効ユーザーデータから成る有効セクタと、無効データから成るダーティセクタとを記憶している固体メモリディスクをクリーンアップする方法において、
ａ）総ダーティメモリが総空きメモリと総ダーティメモリとの和の設定されたパーセンテージを越えたときに、固体メモリディスクをクリーンアップする必要があると決定する過程と；
ｂ）クリーンアップすべき第１のブロックを選択する過程と；
ｃ）セクタごとに：
１）第１のブロックの今後にコピーされる１群の有効セクタから１つの有効セクタを選択する過程と；
２）前記選択した有効セクタを記憶するのに十分な空きメモリを選択したブロックの中に割当てる過程と；
３）第１のブロックから選択した有効セクタを前記選択したブロックにコピーする過程と；
４）第１のブロックの中の全ての有効セクタがコピーされ終わるまで、過程１）から３）を繰り返す過程と；
ｄ）第１のブロックを消去する過程とから成る方法。
【請求項３】
複数のブロックを含み、ブロック単位でのみ消去可能であり、各ブロックは有効ユーザーデータから成る有効セクタと、無効データから成るダーティセクタとを記憶している固体メモリディスクをクリーンアップする方法において、
ａ）総ダーティメモリが総空きメモリと総ダーティメモリとの和の設定されたパーセンテージを越えたときに、固体メモリディスクをクリーンアップする必要があると決定する過程と；
ｂ）クリーンアップが必要であると決定されたら、クリーンアップすべき第１のブロックを選択する過程と；
ｃ）セクタごとに：
１）第１のブロックの今後にコピーされる１群の有効セクタから１つの有効セクタを選択する過程と；
２）前記選択した有効セクタを記憶するのに十分な空きメモリを選択したブロックの中に割当てる過程と；
３）第１のブロックから選択した有効セクタを前記選択したブロックにコピーする過程と；
４）第１のブロックの中の全ての有効セクタがコピーされ終わるまで、過程１）から３）を繰り返す過程と；
ｄ）第１のブロックを消去する過程とから成る方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はコンピュータ記憶システムの分野に関する。さらに特定すれば、本発明は、固体メモリディスクをクリーンアップする方法に関する。
【０００２】
【従来の技術】
従来のパーソナルコンピュータの大部分は数多くの種類の記憶装置を含んでいる。大容量記憶のためにはハード磁気ディスクドライブを使用するが、他の目的に対しては様々に異なる種類の半導体メモリを使用する。
【０００３】
ハード磁気ディスクドライブの不揮発性はそれらが使用される主要な理由の１つである。ハードドライブはデータの損失なくターンオン、ターンオフ可能であろう。ハードドライブは同心のトラックにデータを記憶する。各々のトラックはいくつかのセクタを含み、各セクタの長さは典型的には５１２バイトである。磁気ディスクドライブへの読取りと書込みはセクタごとにビットストリームの形で起こる。
【０００４】
磁気ディスクドライブに記憶される典型的なユーザーファイルは、ディスクドライブの表面に無作為に位置する多数のセクタを占めている。ファイルに関わるポインタの連鎖を記憶することにより、ファイル割当てテーブル（ＦＡＴ）でファイルの各セクタを位置指定できる。各々のポインタはファイルの次のセクタを指示する。
【０００５】
ハードドライブにはいくつかの欠点がある。ハードドライブの大きさ、特にその高さは、そのようなドライブをポータブルコンピュータやラップトップコンピュータに使用するのは不適なものとしてしまうことが多い。ハードディスクドライブの高さは、多くの場合、コンピュータのサイズを縮小することを制約する要因となっている。また、ハードドライブは相対的に大量の電力を消費するので、バッテリー給電式のコンピュータにはさらに向かない。
ハードドライブは、戸外で使用されるコンピュータで使用するには理想的であるとはいいがたい。磁気ディスクドライブは振動や衝撃の影響をきわめて受けやすい。加えて、磁気ドライブは広い戸外の大半と関連して生じる塵や湿気を許容できない。
【０００６】
固体メモリとも呼ばれる半導体メモリは磁気ディスクドライブの欠点の多くをもたらさない。半導体メモリは小型で頑丈であり、磁気ドライブほど電力を消費しない。
不揮発性半導体メモリの１つの型はＦＬＡＳＨ電気的消去可能プログラム可能読取り専用メモリ（ＦＬＡＳＨメモリ）である。ＦＬＡＳＨメモリはユーザーの側でプログラムでき、一度プログラムされたならば、消去されるまでデータを保持する。ＦＬＡＳＨメモリは一度に１ブロック分のメモリを消去することにより急速に消去される。１ブロックは相対的に大量のデータであり、約６４Ｋバイトである。
【０００７】
ゲートの正味電荷が中性であるとき、ＦＬＡＳＨメモリセルは消去される。消去されたＦＬＡＳＨビットを「１」という。逆に、ゲートの正味電荷が負であるとき、ＦＬＡＳＨメモリセルはプログラムされる。プログラムされたＦＬＡＳＨビットを「０」という。１つの例外はあるが、あらかじめ消去せずにＦＬＡＳＨメモリビットを再プログラムすることは不可能である。どのＦＬＡＳＨビットも、あらかじめ消去せずに０にプログラムできる。
【０００８】
従来のＦＬＡＳＨメモリの中には、プログラミングと消去を書込み状態機械又は指令レジスタにより内部で制御するものがある。プログラミングと消去の内部制御は、ＦＬＡＳＨメモリをプログラムし、消去するために要求される知識と時間を減少させる。ＦＬＡＳＨ消去時間は相対的に遅いままである。消去サイクル時間は１から２秒程度である。書込みのたびに、それに先立って消去がおこらなければならないのであれば、ＦＬＡＳＨメモリを使用して磁気ディスクドライブの書込み時間に近づけることは不可能である。
【０００９】
【発明が解決しようとする課題】
本発明は磁気ディスクドライブの書込み速度に匹敵する固体メモリディスクへの書込みを実現することを目的とする。
【００１０】
【課題を解決するための手段】
固体メモリディスクをクリーンアップする方法を説明する。クリーンアップは、クリーンアップのための焦点ブロックの選択をもって始まる。次に、ユーザーデータを保存するために、宛先ブロックの中でセクタごとにユーザーデータを記憶するためのメモリを割当てる。続いて、ユーザーデータを宛先ブロックにセクタごとにコピーする。その後、有効ユーザーデータを損失することなくダーティセクタを空きメモリに変換して、焦点ブロックを消去する。
説明するクリーンアップ方法はコスト面で有益であると共に、バックグラウンドプロセスとして進行するために固体ディスクの性能に影響を及ぼさない。
【００１１】
本発明のその他の目的、特徴及び利点は、添付の図面及び以下の詳細な説明から明白になるであろう。
添付の図面の図には本発明が限定的な意味ではなく、実例として示されている。図中、図中符号は同様の素子を指示する。
【００１２】
【実施例】
I． 固体ディスクの概要
図１は、パーソナルコンピュータ５０をブロック線図の形で示す。パーソナルコンピュータ５０は中央処理装置５２と、コンピュータのユーザーに情報を視覚表示するモニタ５４とを含む。ユーザーはキーボード５６を使用して、中央処理装置５２に入力を供給する。モニタ５４に表示されているポインタを移動させるときには、マウス５８を動かせば良い。パーソナルコンピュータ５０は磁気ディスクではなく、大容量記憶のための固体ディスク６０を使用する。固体ディスク６０は、不揮発性半導体メモリアレイ６２を制御する本発明の固体ディスク制御装置を含む。不揮発性半導体メモリアレイ６２をＦＬＡＳＨアレイ６２ともいう。
【００１３】
簡単に説明すれば、固体ディスク制御装置は半導体アレイ６２のセクタを「浮動」させることによりセクタデータの記憶を管理する。制御装置は、１つのセクタを記憶するのに十分な空きメモリを割当てセクタ書込み要求に応答することによって、セクタデータを「浮動」させる。次に、そのセクタを割当てられた記憶場所に書込む。その後、同じセクタの以前のコピーの有無を探索し、そのコピーを無効、すなわち、「ダーティ」とマークする。この書込み方法の結果、論理セクタ番号と関連するデータは磁気ディスクドライブでの慣例となっていたようにメモリ内の固定物理場所にとどまるのではなく、固体メモリディスクの周囲を移動、すなわち、浮動するようになる。
【００１４】
本発明は、固体ディスク６０をクリーンアップする方法を含む。すなわち、本発明は、ブロックごとにダーティなセクタを消去することにより利用可能な空きメモリを増加させる方法を含む。通常、クリーンアップは、ＦＬＡＳＨアレイ６２内部のダーティなメモリの量が閾値レベルを越えたときにトリガされるバックグラウンドプロセスである。固体ディスク制御装置はクリーンアップのための焦点ブロックを選択することによりクリーンアップを開始する。次に、ユーザーデータを保存するために、固体ディスク制御装置はその焦点ブロックからユーザーデータの有効セクタをコピーするように準備する。固体ディスク制御装置６４は他のブロックで、ユーザーデータの各セクタを記憶するのに十分なメモリを割当て、次に、ユーザーデータのセクタを割当てられた記憶場所にコピーする。焦点ブロックからユーザーデータの全セクタをコピーした後、固体ディスク制御装置はそのブロックを消去する。
【００１５】
Ａ．ＦＬＡＳＨアレイとブロックファイル構造
固体ディスク制御装置６４の制御の対象であるＦＬＡＳＨアレイ６２を理解することは、固体ディスク制御装置６４をさらに良く理解するうえで助けとなる。ＦＬＡＳＨアレイ６２のプログラム特性と消去特性は固体ディスク制御装置６４に大きな影響を及ぼす。ＦＬＡＳＨアレイ６２内部のＦＬＡＳＨデバイスは一度に１ブロックずつ消去されなければならないが、一度に１バイトずつプログラム可能である。一旦０にプログラムされたならば、まず初めに１ブロック全体を消去しないとＦＬＡＳＨメモリの１ビットを１にプログラムできない。メモリの消去済バイトは書込み可能な状態となっているので、それらのバイトを「空き」という。
【００１６】
ＦＬＡＳＨメモリの消去は低速のプロセスである。データの１つのセクタを書込むたびに１回の消去を実行するのは実用的ではない。５１２バイトである１つのセクタを書込むだけのために１２８Ｋバイトの一対のブロックの全体を消去しなければならないので、書込みは遅くなり、また、電力消費の効率は悪くなってしまうであろう。迅速なセクタ書込みを可能にするために、１つのセクタを書込むたびに、固体ディスク制御装置６４はデータの各セクタを新たな空き記憶場所に書込む。この書込み方法の結果は、１つのセクタ番号と関連してセクタデータのいくつかのバージョンが現れるということになる。セクタデータの最新のバージョンを「グッドセクタ」、「有効セクタ」又は「ユーザーセクタ」という。これに対し、セクタのそれ以前のバージョンは無効であり、「ダーティ」とマークされる。
【００１７】
ＦＬＡＳＨメモリは相対的に高価であるため、ＦＬＡＳＨアレイ６２内部のＦＬＡＳＨメモリの実際の量はユーザーに対して利用可能であるとして挙げられた量を大きく越えることができない。言いかえれば、ＦＬＡＳＨアレイ６２内部の予約メモリの量が不足している場合、書込みに際してのメモリの可用性を確保するために、ダーティなセクタを空きメモリに変換しなければならない。
【００１８】
図２は、ＦＬＡＳＨアレイ６２と、固体ディスク制御装置６４とをブロック線図の形で示す。一実施例では、ＦＬＡＳＨアレイ６２は３０個の１メガバイト×８ＦＬＡＳＨメモリチップを使用する。それらのＦＬＡＳＨメモリは、消去とプログラミングを自動的に制御する書込み状態機械を含む。データ圧縮を使用した場合、それらの３０個のＦＬＡＳＨメモリデバイスは４０メガバイトのメモリディスクとして機能する。各ＦＬＡＳＨチップは一度に８ビットずつデータを入出力する。語ごとの入出力を可能にするために、ＦＬＡＳＨアレイ６２は複数対のＦＬＡＳＨデバイスとして編成されているのであるが、そのうち一対のチップ６６のみが示されている。一対のチップ６６の上位チップ６８は１つの語の上位バイトを記憶し、下位チップ７０は１つの語の下位バイトを記憶する。このように、固体ディスク制御装置６４は各対のチップを単一の１６ビット幅メモリデバイスとして扱うことができる。語ごとの入出力によって、固体ディスクドライブ６０は直列ビットストリームの入出力を使用する磁気ドライブと比較して高速という利点を得ている。
【００１９】
各チップ対は、それぞれが１２８Ｋバイトのメモリを含む１６個のブロックとして編成されている。メモリの各ブロックは多数のデータのセクタを記憶できるので、各ブロックはデータの各セクタを識別し且つ位置指定するためのブロックセクタ変換テーブル（ＢＳＴＴ）８４を含む。
【００２０】
図３は、ブロック８０と、そのブロック及び他の全てのブロックが使用するファイル構造とを示す。ブロック８０は１語幅の構造として表わされているが、実際には２つのＦＬＡＳＨチップに記憶されている。各語の上位バイトは上位チップ６８に記憶され、また、各語の下位バイトは下位チップ７０に記憶されている。
ブロック８０のデータ構造はブロックセクタ変換テーブル８４と、データスペース８６とを含む。ブロックセクタ変換テーブル８４は複数の見出しを記憶している。見出しは１つの論理セクタ番号に関する情報と、その関連データとから成るブロックである。ここでいう論理セクタ番号（ＬＳＮ）はＢＳＴＴの中に記憶されているセクタ番号を指す。セクタ番号はＣＰＵ５２から受信したセクタ識別子であり、ＣＰＵはそのセクタ識別子が１つの固定物理記憶場所に対応するものと考える。ところが、固体ディスク６０が使用する書込み方式のために、ＬＳＮは１つの固定物理記憶場所に対応しない。同様に、固体ディスクで使用する書込み方式のために、いくつかの見出しとＬＳＮが単一のセクタ番号に対応することもあるだろう。
一実施例では、各々の論理セクタ番号は２４ビットの長さである。
【００２１】
ディスクをフォーマットする間、セクタ番号ごとに１つの見出しを作成する。これにより、読取り指令及び書込み指令の実行中にデータのセクタの損失を検出できる。特定の１つのセクタ番号と関連する見出しを見出せないとき、それに関連するデータのセクタが失われてしまったことがわかる。ここでいう「損失」は、ＦＬＡＳＨアレイ６２の欠陥のために消滅するデータのセクタ、又は汚れてしまったために信頼性を失ったデータのセクタを表わす。
【００２２】
各々の見出し８５は周期冗長検査（ＣＲＣ）を含み、それにより、固体ディスク６０は見出し８５の信頼性を判定できる。
見出し８５は、その見出しと関連するセクタデータに関する大量の情報を含む属性語を含んでいる。属性語の中の１つのビットは、セクタ番号が不良トラックの一部としてマークされているか否かを指示する。別のビットは、セクタデータが圧縮されているか否かを指示する。属性語は信頼性に関わる２つのダーティビットを含む。その双方のダーティビットがセットされていれば、見出しと関連するセクタデータは有効であると考え、いずれかのダーティビットがリセットされていれば、ダーティであると考える。属性語はデータ付加ビットをさらに含む。見出しにセクタデータが付加されていない場合、データ付加ビットはリセットされる。これは、フォーマットした後のあらゆる見出しに当てはまる。セクタ番号に関してデータが書込まれたならば、データ付加ビットはセットされる。属性語に含まれている最後の情報は改訂番号である。この改訂番号によって、固体ディスク制御装置６４は、同一のＬＳＮをもつ複数の有効見出しが存在しているときに有効見出しを識別できるのである。
【００２３】
見出し８５に記憶されている最後の情報はブロックセクタオフセット（ＢＳＯ）である。ＢＳＯは見出しと関連するＦＬＡＳＨメモリスペースの始めに対するブロックの最上部からのオフセットである。メモリスペースにデータが記憶されていても、いなくても、そのメモリスペースは１つの見出しに割当てられる。データが見出しに付加されていなければ、割当てられるメモリの量はデータスペース８６のサイズをＢＳＴＴ８４における見出しの最大数で除算したものである。
【００２４】
メモリスペースは、セクタデータが付加されていない見出しに割り当てられなければならない。これは、フォーマットする間にＢＳＴＴ８４の全てがデータ付加のない見出しで充填されているためである。それらのＢＳＴＴ８４と関連するデータスペース８６の全体が空いているとしても、データスペース８６に書込むことは不可能である。これは、単に、それらのブロックのＢＳＴＴに余地がないためである。割当てのために空きメモリを利用できないキャッチ２２状況を回避するために、それらのＢＳＴＴ８４と関連するデータスペース８６の全てはユーザーデータとして分類される。言いかえれば、セクタはダーティビットにより指示されるようにダーティでもなく、空きでもないということになる。データが付加されていない見出しにメモリデータスペース８６を割当て且つそのメモリの量を適切なブロック、適切なチップ及びアレイにある空きメモリの量から減じることにより、データスペース８６の一部がユーザーデータとして指定される。フォーマットした後にデータのセクタを書込んでゆく間に、データが付加されていない見出しはその割当てられたデータスペースと共にダーティとマークされる。最終的に、フォーマットした間に充填されたブロックはクリーンアップされて、そのデータスペースは空きメモリとして利用可能になる。
【００２５】
データ圧縮を使用しない場合、データを付加せずに見出しを書込みできることは重大である。データ圧縮を使用しないときには、クリーンアップのために利用可能である予約はほとんどなく、起こりうるデータのセクタごとに全て固体ディスク６０に書込むことになる。この状況ではクリーンアップ効率はひどく損なわれてしまい、データの断片化が生じるおそれがある。このデータ断片化は今度は数多くのフォアグラウンドクリーンアップをもたらし、固体ディスク全体の性能を劣化させる。
【００２６】
データスペース８６で１つのセクタに関わるデータが別のセクタに関わるデータとぶつかり合うので、各々のＢＳＯは１つのセクタに関わるデータの最上位部分と、別のセクタに関わるデータの最下位部分とを指示する。たとえば、セクタ１のブロックオフセットであるＢＳＯ1 はＬＳＮ1 と関連するデータの始まりを指示する。ＢＳＯ1 はＬＳＮ2 と関連するデータの最下位部分をも指示する。ブロックセクタ変換テーブル８４を見る別の方法は、各々のＬＳＮが２つのブロックセクタオフセットの間にはさまれており、その一方のブロックセクタオフセットはセクタデータの最上位部分を指示し、他方はセクタデータの最下位部分を指示するというものである。ブロックの最下位部分に記憶されているセクタＬＳＮ1 と関連するデータの最下位部分は、ブロックの最下位部分の場所がわかっているために、ＢＳＯにより指示されなくとも良い。
【００２７】
ブロックセクタ変換テーブル８４はデータスペース８６に向かって下方へ成長してゆく。第１の見出しＢＳＴＴ８４はブロック８０の最上位部分に書込まれる。ブロック８０に書込まれる後続する各セクタに関わる見出しは、先の見出しの下方に記憶される。
【００２８】
ＢＳＴＴ８４とは対照的に、データスペース８６は上方へ成長する。ブロック８０に書込まれるデータの第１のセクタはデータスペース８６の最下位部分に書込まれる。データスペース８６に書込まれるデータの次のセクタは先のセクタのすぐ上方に書込まれる。たとえば、ＬＳＮ2 と関連するデータはＬＳＮ1 と関連するデータより低いアドレス範囲の中に位置している。
【００２９】
データスペース８６に記憶しうるセクタの数は、ＢＳＴＴ８４に入り込む前に変動する。この可変性は、セクタデータが圧縮されているときにセクタのサイズが変動するために起こる。データ圧縮を伴うとき、セクタのサイズは２５６語からわずか数語まで変わると思われる。固体ディスク６０がシーク戦略を使用するとすれば、最大限２０４７個のセクタをデータスペース８６に記憶できるであろう。
【００３０】
固体ディスク制御装置６４はＢＳＴＴ８４とデータスペース８６が成長してゆく間に互いにぶつかり合うのを防止する。実際には、固体ディスク制御装置６４はＢＳＴＴ８４とデータスペース８６との間に幾分かのスラック８８が維持されるように保証する。スラック８８は、まだプログラムされていない空きＦＬＡＳＨメモリである。ＦＬＡＳＨメモリの規約に従えば、空いた記憶場所はＦＦＦＦ（１６進数）を記憶する。ブロックセクタ変換テーブル８４のシーク中、スラック８８はＢＳＴＴ８４の終わりに到達したことを指示する。
【００３１】
ブロック８０はブロック属性データ９０をさらに記憶している。そのブロックに特有の情報が記憶される属性データ９０である。たとえば、ブロック属性データ９０は、ブロックが消去されて、そのブロックに書込んだ回数を指示するサイクルカウントを含む。ブロック属性データ９０はブロック欠陥情報を含んでいても良い。
【００３２】
Ｂ．固体ディスク制御装置ハードウェアの概念
再び図２を参照して説明すると、ＦＬＡＳＨアレイ６２の読取り、書込み及びクリーンアップは固体ディスク制御装置６４により制御される。マイクロプロセッサ９２はデータベース９３と、セクタ見出し変換テーブル（ＳＨＴＴ）９４と、ＦＬＡＳＨメモリ９５に記憶されている本発明のアルゴリズムとを使用してそれらのタスクを管理する。データベース９３、ＳＨＴＴ９４及びアルゴリズムについては以下にさらに詳細に説明する。アプリケーション特定集積回路であるウィンドウＡＳＩＣ９６は、マイクロプロセッサ９２の外界に対するウィンドウ並びにＦＬＡＳＨアレイ６２に対するウィンドウとして機能する。ウィンドウＡＳＩＣ９６を介してマイクロプロセッサ９２はＣＰＵ５２から指令を受信すると共に、ＦＬＡＳＨアレイ６２に対する読取りと書込みを実行する。言いかえれば、ウィンドウＡＳＩＣ９６はマイクロプロセッサ９２のアドレス可能メモリスペースを増加させる。ウィンドウＡＳＩＣ９６は４つのウィンドウを含むので、マイクロプロセッサ９２はいくつかのＦＬＡＳＨ記憶場所を繰り返し、急速にアクセスできる。データは、ＣＰＵ５２との間で、ウィンドウＡＳＩＣ９６を介して流れて、セクタバッファ９８に至る。セクタバッファ９８があるために、ＣＰＵ５２に向かうデータの転送はセクタバッファがない場合に可能であるよりも急速に起こりうる。固体ディスク制御装置６４は電荷ポンプ１００を含む。電荷ポンプ１００は５ボルトをプログラミングと消去に必要とされる１２ボルトレベルに変換する。固体ディスク６０に供給される電圧レベルがＦＬＡＳＨアレイ６２の中のＦＬＡＳＨデバイスをプログラムするために必要な１２ボルト電圧レベルより全て低くならない限り、電荷ポンプ１００は必要ではない。
【００３３】
Ｃ．ＦＬＡＳＨアレイデータベースとセクタ見出し変換テーブル
繰り返し使用される情報をランダムアクセスメモリ（ＲＡＭ）に記憶することにより、固体ディスク６０の性能は向上する。この情報は、一般に、ＦＬＡＳＨアレイ６２の現在特性に関連しているので、これをＦＬＡＳＨアレイデータベース９３という。ＦＬＡＳＨアレイデータベース９３の中の情報は、
１．ＦＬＡＳＨアレイ６２内部のダーティな語の総数（ＴＤＦＡ）；
２．各ブロック内部のダーティな語の総数（ＴＤＦＢN）；
３．ＦＬＡＳＨアレイ６２内部の空きの語の総数（ＴＦＦＡ）；
４．各チップ対の中の空きの語の数（ＴＦＦＣM） ；
５．各ブロック内部の空きの語の総数（ＴＦＦＢN）
を含む。
【００３４】
固体ディスク制御装置６４がＦＬＡＳＨアレイデータベース９３をどう使用するかを以下にアルゴリズムごとに説明する。
セクタ見出し変換テーブル（ＳＨＴＴ）９４はセクタ番号を関連するデータのセクタに対するポインタに変換する。ＳＨＴＴ９４を頻繁且つ容易に変更できるように、ＳＨＴＴ９４をＲＡＭに記憶しておくのが好ましい。セクタ見出し変換テーブル９４は、与えられたセクタ番号と関連するデータを直接には指示しない。そうではなく、ＳＨＴＴ９４により供給されるポインタはＢＳＴＴ８４の中、そのセクタ番号と関連する見出しの付近の記憶場所を指示する。
【００３５】
ＳＨＴＴ９４がセクタ番号と関連する見出しを直接には指示しない理由を理解するには、ＢＳＴＴ８４に現れうる見出しをそれぞれ一意性をもってアドレス指定するために必要なビットの数を考えてみれば良い。ＢＳＴＴ８４には、最大限２０４７個の見出しを記憶できる。チップが１５対あり、一対のチップにそれぞれ１６のブロックが含まれているものとすれば、ＦＬＡＳＨアレイ６２は４９１，２８０個の見出しを記憶することができるであろう。それほど多くの見出しを一意性をもって識別するには１９ビットが必要である。１９ビットを記憶するには、３×８個のＲＡＭチップを使用しなければならない。従って、３つのビットを記憶するために、１つのＲＡＭにおける８ビットのうち５つが浪費されるであろう。これは、競合しうる価格の固体メモリディスクを製造しようとする努力の中では高価で、受け入れられない解決方法である。
【００３６】
この１９ビットのジレンマを解決するＳＨＴＴのデザインはいくつかある。図４に示す一実施例では、工業規格の４０ＭＢディスクドライブのデータの数の現れうる８３３００個のセクタの各々に対して１つずつのポインタを記憶する。ＳＨＴＴ９４の各エントリには１６ビットしか記憶されていない。それらのビットのうち４つは、シーク中のセクタデータを記憶しているチップ対を指示する。もう４つのビットはそのセクタを記憶している特定のブロックを指示する。残る８つのビットは、所望の見出しの付近にある見出しに対するブロックの最上位部分からのオフセットを表わす。このオフセットを見出しポインタと呼ぶ。見出しポインタを表わすために８ビットを使用するということは、最大限２０４７個の見出しを位置指定するために２５６個の見出しポインタを利用できることを意味している。そこで、所望の見出しを位置指定するためには、ＢＳＴＴ８４において最大で８個の見出しを走査しなければならない。言いかえれば、ＳＨＴＴ９４ａは１つの特定のセクタ番号と関連するデータを位置指定するために２段の探索を要求するということがある。まず、特定のチップ、ブロック及び見出しポインタを位置指定するためにＳＨＴＴ９４ａを探索する。第２に、セクタ番号と関連する見出しを見出すために、ＢＳＴＴ８４の指示領域を探索する。
【００３７】
図４のＳＨＴＴ９４は固体ディスク６０に記憶されているセクタごとに１つの物理アドレスを記憶する。最新のキャッシュメモリを使用することにより、ＳＨＴＴ９４のエントリの数を減少できる。
【００３８】
ＦＬＡＳＨアレイデータベース９３とＳＨＴＴ９４は不揮発性メモリであるＲＡＭに記憶されること、及び読取りと書込みがデータベース９３とＳＨＴＴ９４に縦続して実行されることを理由として、パワーアップ中にＦＬＡＳＨアレイデータベース９３とＳＨＴＴ９４の双方を生成しなければならない。図５は、ＦＬＡＳＨアレイデータベース９３とＳＨＴＴ９４の双方を作成するためのアルゴリズムを示す。このアルゴリズムを使用すると、ＳＨＴＴ９４とＦＬＡＳＨアレイデータベース９３は、共に、各々のＢＳＴＴ８４を走査することにより生成される。各セクタ番号と関連する見出しの記憶場所と、ブロック中の空きメモリとダーティメモリの量とに注目する。
【００３９】
作成はステップ１１０においてＳＨＴＴ９４の初期設定と共に始まる。セクタ番号ごとの各ポインタを同じ初期値に設定する。一実施例では、その値はＦＦＦＦ（１６進数）である。そのため、ＳＨＴＴ９４を作成した後に初期値と等しいポインタを検索すると、フォーマットする間にセクタ番号ごとに１つの見出しが作成されていることから、そのセクタ番号と関連するデータのセクタが失われてしまっていることがわかる。マイクロプロセッサ９２はステップ１１０からステップ１１１へ分岐する。
【００４０】
ステップ１１１では、ＦＬＡＳＨアレイ中の空きメモリの総量であるＴＦＦＡと、チップごとの空きメモリの総量であるＴＦＦＣM とをその最大値に初期設定する。チップごとの最大空きＦＬＡＳＨは６４Ｋバイト／ブロック* １６ブロック、すなわち、チップ対ごとに２０４８バイトから各ブロックに記憶されているブロック属性データを減じたものである。同様に、ＴＴＦＡmax はチップ対ごとに２０４８Ｋバイト* １５チップ対、すなわち、約３０Ｍバイトである。これを実行したならば、マイクロプロセッサ９２はステップ１１２へ分岐して、ＢＳＴＴ８４を走査し始める。
【００４１】
ステップ１１２では、マイクロプロセッサ９２はＦＬＡＳＨアレイ６２に今後に走査すべきブロックが残っているか否かを判定する。残っていれば、マイクロプロセッサ９２はステップ１１４へ進み、走査すべきブロックＢC を選択する。マイクロプロセッサ９２はステップ１１４からステップ１１５へ分岐する。そこで、現在ブロックの空きメモリの総量ＴＦＦＢC をその最大値に初期設定する。マイクロプロセッサ９２は、次に、ステップ１１６に進む。
ステップ１１６では、マイクロプロセッサ９２は選択したブロックのブロックセクタ変換テーブル８４から次の見出しを読取る。その後、マイクロプロセッサ９２はステップ１１８へ分岐する。
【００４２】
マイクロプロセッサ９２はステップ１１８で現在見出しを分類し始める。マイクロプロセッサ９２は、現在見出しの属性語に含まれているダーティビットを読取ることにより、見出しがダーティとマークされているか否かを判定する。いずれかのダーティビットが論理値０であれば、ＬＳＮと関連するデータはダーティであると考える。データのセクタがダーティであれば、マイクロプロセッサ９２はステップ１２０へ分岐して、ＦＬＡＳＨアレイデータベース９３を更新する。
【００４３】
ステップ１２０では、マイクロプロセッサ９２はダーティセクタのサイズを確定するのであるが、そのサイズはデータ圧縮の結果として変わることもある。セクタのサイズは現在ＬＳＮの両側のブロックセクタオフセットを比較することにより確定される。ダーティセクタのサイズを確定した後、マイクロプロセッサ９２はＴＤＦＡとＴＤＦＢC を更新する。ダーティな語の総数であるＴＤＦＡと、現在ブロックの中のダーティな語の総数であるＴＤＦＢC とをセクタとその見出しのサイズだけ増加させるのである。その後、マイクロプロセッサ９２はステップ１２１へ進む。
マイクロプロセッサ９２はそのＦＬＡＳＨ空き変数を適切に改訂する。現在セクタとその見出しのサイズをＴＦＦＡ、ＴＦＦＢC 及びＴＦＦＣC から減じる。その後、マイクロプロセッサはステップ１１６に戻ることにより、ＦＬＡＳＨアレイデータベース９３とＳＨＴＴ９４の作成を再開する。
【００４４】
これに対し、セクタがダーティでない場合には、マイクロプロセッサ９２はステップ１１８からステップ１２２へ分岐する。そこで、マイクロプロセッサ９２は、ＢＳＴＴ８４の終わりに達したか否かを判定するために、現在見出しの中の属性語を検査する。次の見出しに関わる属性語がＦＦＦＦ（１６進数）であるならば、終わりに達している。この場合、マイクロプロセッサ９２はステップ１１２に戻って、ＢＳＴＴ８４の走査を継続すべきか否かを判定する。他のあらゆるケースにおいては、マイクロプロセッサ９２はステップ１２２からステップ１２４に進む。
【００４５】
ステップ１２４に入るということは、現在見出しがユーザーデータの有効セクタと関連していることを意味している。従って、マイクロプロセッサ９２は空き変数ＴＦＦＡ、ＴＦＦＢC 及びＴＦＦＣC を現在セクタのサイズだけ減少させる。（添字「Ｃ」は「現在」を指示している。）これを実行したならば、マイクロプロセッサ９２はステップ１２６へ進む。
【００４６】
ステップ１２６では、現在見出しに含まれているＬＳＮと等しいセクタ番号を求めてＳＨＴＴ９４のエントリをシークすることにより、現在見出しに関わるＳＨＴＴエントリの改訂を開始する。ＳＨＴＴの現在エントリがＦＦＦＦ（１６進数）であれば、そのセクタ番号に関わる情報は存在していない。マイクロプロセッサ９２はステップ１２８へ分岐することによりこれに対応する。セクタ番号に関わるエントリがＦＦＦＦ以外であれば、いずれの場合にも、そのセクタ番号に関してデータの２つの有効バージョンがあるということになる。物事を分類するために、マイクロプロセッサ９２はステップ１３０へ進む。
【００４７】
まず、より単純な状況、すなわち、現在ＬＳＮに対応するセクタ番号に関わるデータがＳＨＴＴ９４に記憶されていない場合を考える。ステップ１２８では、マイクロプロセッサ９２は現在見出しに関わるチップ、ブロック及び見出しポインタをＳＨＴＴ９４に書込む。これを実行したならば、マイクロプロセッサ９２はステップ１１６に戻って、別の見出しを検査する。
【００４８】
ＳＨＴＴ９４が現在ＬＳＮと関連するセクタ番号に関わるエントリを既に含んでいる場合には、状況はさらに複雑になる。ステップ１３０では、マイクロプロセッサは改訂番号を比較することによりどの見出しが、従って、どのデータのセクタが最も新しいかを判定する。次のステップ１３２では、マイクロプロセッサ９２は先のダーティビットを論理値０にプログラムすることにより、そのデータの先の無効セクタをダーティとマークする。
【００４９】
ステップ１３３では、直前にダーティであるとマークされたセクタを含むブロックと、ＦＬＡＳＨアレイ６２とに関わる総ダーティを反映するために、マイクロプロセッサはデータベース９３を更新する。その更新は、セクタのサイズをＴＤＦＢC 及びＴＤＦＡに加算することにより実行される。
【００５０】
ステップ１３４では、必要に応じて、ＳＨＴＴ９４を最終的に更新する。見出しとステップ１１６で選択したＬＳＮがステップ１３２でダーティとマークされていれば、更新は不要である。そうでなければ、ステップ１１６で選択したＬＳＮに関わるチップ、ブロック及び見出しポインタをＳＨＴＴ９４に書込む。
【００５１】
マイクロプロセッサ９２はステップ１３４からステップ１１６に戻る。そこで、別の見出しを選択する。
ＦＬＡＳＨアレイ６２内部の見出しを走査し終わるたびに、ＳＨＴＴ９４の作成は完了する。１つのセクタ番号に対応する見出しが位置指定されていなければ、ＳＨＴＴ９４の中のポインタは初期値にとどまる。すなわち、ポインタはデータのセクタが失われたことを指示し、ＳＨＴＴ９４はどのデータのセクタをも考慮に入れているのである。
【００５２】
II．固体ディスク制御装置
固体ディスク制御装置６４の心臓部は、ＦＬＡＳＨメモリ９５の中に記憶されている１組のアルゴリズムである。それらのアルゴリズムはＦＬＡＳＨアレイ６２の読取り、書込み及びクリーンアップを制御する。それらのアルゴリズムは、ＣＰＵ５２が工業規格のハード磁気ディスクドライブを取り扱っているかのような錯覚を作り出すのを助ける。
【００５３】
図６のオブジェクト線図は、固体ディスク制御装置６４が使用するアルゴリズムの総体的な編成と相互関係を示す。固体ディスク制御装置６４のアルゴリズムはトップレベルスケジューラ１５０、ホストインタフェース１５２、そして、ＦＬＡＳＨ媒体１５４という３つのクラスに編成されている。トップレベルスケジューラ１５０は他の２つのクラス１５２及び１５４の間でのＣＰＵ９２の処理時間の割当てを処理する。ホストインタフェース１５２はＣＰＵ５２からの工業規格ディスクドライブ指令を解釈し、それらをＦＬＡＳＨ媒体１５４が反応しうる指令に変換する。ＦＬＡＳＨ媒体１５４はＦＬＡＳＨアレイ６２と直接にインタフェースし、ホストインタフェース１５２からの読取りと書込みの要求に応答する。ＦＬＡＳＨ媒体１５４はＦＬＡＳＨアレイ６２のクリーンアップをも管理する。
【００５４】
ホストインタフェース１５２とＦＬＡＳＨ媒体１５４のスケジューリングは相対的に単純なタスクである。固体ディスク６０のパワーアップはトップレベルスケジューラ１５０を始動する。スケジューラは固体ディスク６０を初期設定し、次に、ホストインタフェース１５２を呼び出す。これはＣＰＵ５２に固体ディスク６０のあらゆる資源を割当てる。ホストインタフェース１５２がトップレベルスケジューラ１５０に制御を戻したとき、クリーンアップオブジェクト１６４が呼び出される。クリーンアップが進行中である場合、クリーンアップにはＣＰＵ実行時間の１スライス、一実施例では５００μ秒が割当てられる。クリーンアップがトップレベルスケジューラ１５０に制御を戻すと、ホストインタフェース１５２が再び呼び出される。固体ディスク６０がパワーアップされている間は、トップレベルスケジューラ１５０はそのプロセスを何度も繰り返す。
【００５５】
ホストインタフェース１５２はインタフェース１５６及びセクタバッファ１５８という２つのクラスのアルゴリズムを含む。インタフェース１５６はＡＴ−ＩＤＥハードディスクインタフェースをエミュレートする。インタフェース１５６はＡＴＡ指令割込みを処理し、ＡＴＡ指令をＦＬＡＳＨ媒体１５４により理解可能な指令に変換する。別の実施例においては、ホストインタフェース１５６はＳＣＳＩディスクインタフェース又は他の規格によるディスクドライブインタフェースをシミュレートしても良い。セクタバッファ１５８はセクタバッファ９８の使用を管理する。
【００５６】
簡単に説明すれば、ＦＬＡＳＨ媒体１５４は５種類のアルゴリズム、すなわち、ディスク１６０、セクタ１６２、クリーンアップ１６４、ＦＬＡＳＨパワー１６６及びＦＬＡＳＨアレイインタフェース１６７という５つのサービスを含んでいることになる。ディスク１６０はインタフェース１５６からの読取り要求と書込み要求をサービスする。また、ディスク１６０はディスク１６０からの他の指令を変換し、それらを他のクラス１６２、１６４、１６６及び１６７に移して実行させる。セクタ１６２はＦＬＡＳＨアレイ６２内部に記憶されているセクタに関連する大部分のタスクを実行する。セクタ１６２はディスク１６０とクリーンアップ１６４の双方により使用されるＦＬＡＳＨアレイデータベース９３を維持すると共に、ＦＬＡＳＨアレイ６２の中の空きメモリスペースを割当てる。さらに、セクタ１６２はＦＬＡＳＨアレイ６２からのデータの読取りをＦＬＡＳＨアレイインタフェース１６７と、シーケンサ１６８とを介して制御する。ＦＬＡＳＨパワー１６６は本質的にはデバイスドライバである。すなわち、ＦＬＡＳＨパワーはＦＬＡＳＨアレイ６２に対する読取り又は書込みに必要な電圧レベルを発生するのである。ＦＬＡＳＨアレイインタフェース１６７は、ＦＬＡＳＨ６２の読取りと書込みを直接に制御する低レベルルーチンを処理する。シーケンサ１６８はセクタバッファ９８と、ＦＬＡＳＨアレイ６２との間のデータの移動を処理する。クリーンアップ１６４は、その名が示す通り、ＦＬＡＳＨアレイ６２のクリーンアップを管理する。ＦＬＡＳＨパワー１６６は固体ディスク６０の限定された予定電流を管理するのであるが、一実施例では、この電流はわずか１２０ｍＡである。一対のチップで１つのブロックを消去するのに６０ｍＡまでが必要であるとすれば、電流の効率の良い管理は重要である。
【００５７】
Ａ．ＦＬＡＳＨアレイからのセクタの読取り
簡単に説明すれば、１つのセクタの読取りは３段階のプロセスである。まず初めに、セクタ番号と関連する見出しに対するポインタを求めてＳＨＴＴ９４を探索する。第２に、見出しを位置指定し、その属性語を検査して、付加データが有効であるか否かを知る。第３に、見出しと関連するセクタデータが有効であれば、その記憶場所を確定し、ＣＰＵ５２に戻す。
ディスク１６０により実現される読取りアルゴリズムを図７の流れ図に示す。全ての呼び出し側はセクタ番号を入力する。
【００５８】
ステップ１７０におけるマイクロプロセッサ９２の最初のタスクは、有効性に関わる入力セクタ番号の検査である。工業規格によるディスクドライブの中にあるセクタの最大数で、セクタ番号が有効であるか否かを判定する。たとえば、規格の４０ＭＢドライブは８３３００個のセクタを含む。従って、４０ＭＢドライブの場合、８３３００を越えるセクタ番号はいずれも無効になるであろう。
【００５９】
呼び出し側プログラムが無効セクタ番号を与えていた場合、マイクロプロセッサ９２はステップ１７０からステップ１７２へ分岐する。マイクロプロセッサ９２は、状態語を無効セクタ番号範囲に設定することにより、セクタ番号の無効性を呼び出し側に指示する。次に、マイクロプロセッサ９２はステップ１７４に戻り、制御を呼び出し側に戻す。
【００６０】
これに対し、呼び出し側が有効セクタ番号をもつセクタを読取ることを要求した場合には、マイクロプロセッサ９２はステップ１７０からステップ１７６へ進む。ステップ１７６では、マイクロプロセッサ９２はセクタ番号を取り上げ、セクタ番号と関連するチップ、ブロック及び見出しポインタを求めてＳＨＴＴ９４を探索する。
【００６１】
ステップ１７８では、マイクロプロセッサ９２は要求されたセクタ番号に関わるデータが存在するか否かを判定する。マイクロプロセッサ９２は、ＳＨＴＴ９４から検索した見出しポインタを検査することにより、特定のセクタ番号について見出しが存在するか否かを報知することができても良い。見出しポインタがＦＦＦＦ（１６進数）である場合、フォーマットする間にセクタ番号ごとに１つの見出しを作成していても、セクタ番号に対して有効見出しを見出すのは不可能である。
マイクロプロセッサ９２は、ステップ１７８からステップ１８０へ分岐することにより損失セクタに応答する。そこで、マイクロプロセッサ９２は見出しを見出せなかったことを指示する。次に、マイクロプロセッサ９２はステップ１７４へ分岐して、読取りは完了する。
【００６２】
これに対し、セクタ番号に対する見出しが存在しているのであれば、マイクロプロセッサ９２はステップ１８２へ分岐する。そこで、セクタ１６２は入力されたセクタ番号と関連する見出しをシークする。所望の見出しを位置指定したならば、セクタ１６２はチップ、ブロック及びその見出しに対するオフセットを指示する。セクタ１６２は、所望の見出しを見出せない場合にも指示する。
【００６３】
セクタ１６２がそのシークから復帰したならば、マイクロプロセッサ９２はステップ１８４へ分岐して、シークの成否を判定する。シークアルゴリズムがセクタ番号と関連する見出しを位置指定しなかった場合には、マイクロプロセッサ９２はステップ１８０へ分岐して、そのことを呼び出し側に報知する。これに対し、適切な見出しが位置指定されたならば、マイクロプロセッサ９２はステップ１８６へ分岐する。そこで、ステップ１８２で検索した情報をセクタオブジェクト１６２の読取りサービスにパスする。セクタ番号と関連するデータをセクタバッファ９８にコピーし且つホストＣＰＵ５２に供給する。その後、読取りが完了して、マイクロプロセッサ９２はステップ１７４へ分岐することにより制御を呼び出し側に戻す。
【００６４】
図８は、セクタ番号が与えられたときにセクタデータをシークする方法を示す。このアルゴリズムもセクタ１６２により実現される。
簡単に説明すれば、図８のシークアルゴリズムはセクタ番号と関連するデータを位置指定する２つの方式を有する。第１の方式は、シーク時間を短縮するためにデータのコヒーレンシーに依存する。すなわち、現在シーク中であるデータのセクタは最前に位置指定されたデータのセクタに関連しており且つその付近に位置しているものと仮定する。この方式が、所望のデータのセクタを位置指定しそこなえば、次に２段階方式が使われる。まず、セクタ番号入力ＳＮi に関わるチップ、ブロック及び見出しオフセットを位置指定するために、ＳＨＴＴ９４を探索する。次に、その情報を使用して、呼び出し側により入力されたセクタ番号と等しいＬＳＮをもつ見出しを求めてＢＳＴＴ８４を探索する。
【００６５】
データのセクタの位置指定はステップ１９０で始まる。そこで、マイクロプロセッサ９２は、探索した最前のＢＳＴＴ８４に別の見出しが記憶されているか否かを判定する。記憶されていれば、入力セクタ番号と関連する見出しが同じＢＳＴＴ８４の中にある可能性がある。その場合、マイクロプロセッサ９２はステップ１９２へ進む。しかしながら、最前に位置指定した見出しがそのＢＳＴＴ８４の中で最後に位置指定した見出しであった場合には、入力セクタ番号と関連するデータのセクタを急速に位置指定することは可能ではない。二段階探索を使用しなければならない。その場合には、マイクロプロセッサ９２はステップ２０６へ進み、その二段階探索を開始する。
【００６６】
まず、ステップ１９２に入るときのマイクロプロセッサ９２のアクションについて考える。マイクロプロセッサ９２は、最前に位置指定した見出しのすぐ次に続く見出しを読取る。この見出しの中のＬＳＮを「ＬＳＮL+1」 と指定する。ＬＳＮL+1 をステップ１９４のＳＮi と比較して、現在見出しが所望の見出しであるか否かを判定する。ＬＳＮL+1 がＳＮi と等しくなければ、別の方法でデータのセクタを位置指定しなければならない。その場合には、マイクロプロセッサ９２はステップ２０６へ進む。これに対し、ＬＳＮL+1 がＳＮi と等しい場合には、マイクロプロセッサ９２はステップ１９６へ分岐する。
【００６７】
現在見出しの信頼性を確定するプロセスはステップ１９６をもって始まる。ステップ１９６の間、マイクロプロセッサは現在見出しに関わる周期冗長検査（ＣＲＣ）を生成する。このＣＲＣを「ＣＲＣG」 と呼ぶ。ステップ１９８では、ＣＲＣG を見出し自体に記憶されているＣＲＣであるＣＲＣstoredと比較する。ＣＲＣG ＝ＣＲＣstoredであるとき、現在見出しの中の情報を信頼しうるものと考える。マイクロプロセッサ９２はステップ２０２へ分岐することによりこの状態に応答する。これに対して、ＣＲＣstoredと等しくないために現在見出しが信頼できない場合には、マイクロプロセッサ９２はステップ２０６へ進む。
【００６８】
まず、所望の見出しを位置指定したときのマイクロプロセッサ９２のアクションを考える。マイクロプロセッサ９２は、第１に、ステップ２００で見出しと関連するデータのセクタのサイズを確定する。これは、先に説明した通り、適切なブロックセクタオフセットを使用して実行される。ステップ２０２では、セクタのサイズ、チップ、ブロック及び所望の見出しに対するオフセットを呼び出し側に戻す。
これが成功すれば、ステップ１９０〜２０２から成る方法は１つのデータのセクタを位置指定するために要する時間を、ステップ２０６〜２２２から成る二段階探索と比べて四分の一に短縮する。
【００６９】
二段階探索は、より迅速な方式が失敗に終わった後にステップ２０６から始まる。マイクロプロセッサ９２は、セクタ番号入力ＳＮi と関連するチップ、ブロック及び見出しポインタを求めてＳＨＴＴ９４をシークすることにより第１レベルの探索を実行する。ステップ２０６で検索したチップ、ブロック及び見出しポインタの値をステップ２０８で検査して、ＳＮi について見出しを位置指定することが可能であるか否かを判定する。それらの値が初期値と等しいならば、ＳＮi と関連する見出しは失われていることになる。一実施例では、初期無効値はＦＦＦＦ（１６進数）である。マイクロプロセッサ９２は、ステップ２２４へ分岐することにより、無効のチップ、ブロック及び見出しポインタの値に応答する。そこで、入力セクタ番号と関連する見出しが見出されなかったことを呼び出し側に報知する。これに対し、ＳＨＴＴ９４から検索した値が有効である場合には、マイクロプロセッサ９２はステップ２１０へ進む。
【００７０】
シークの第２の段階は、ステップ２１０で、走査カウントを零に初期設定することによって始まる。走査カウントはシーク中に検査される見出しの番号を追跡する。そこで、マイクロプロセッサ９２は見出しポインタの付近の見出しを読取る。
マイクロプロセッサ９２はステップ２１０からステップ２０８へ進んで、現在走査カウントを最大走査がカウントと比較する。
【００７１】
走査しなければならない見出しの最大数は、ＢＳＴＴ８４中の見出しの最大数を見出しポインタの最大数で除算することにより設定される。たとえば、固定ディスク６０の一実施例では、ＢＳＴＴ８４に記憶される見出しの最大数は２０４７であり、使用する見出しポインタの数は２５６のみである。従って、この実施例では８つまでの見出しを走査しなければならない。走査カウントが最大値より小さいならば、マイクロプロセッサ９２はステップ２１２へ分岐して、所望の見出しの探索を継続する。これに対し、走査カウントが最大値を越えたならば、マイクロプロセッサ９２はステップ２００からステップ２２４へ進む。
【００７２】
まず、走査カウントが最大値より小さいときの状況を考える。マイクロプロセッサ９２はステップ２１４に入り、現在見出しの中に記憶されているＬＳＮを入力セクタ番号と比較する。それら２つが等しいならば、所望の見出しは位置指定されていることになるであろう。そうでなければ、所望のセクタを求める探索を継続しなければならない。
ステップ２２２では、走査カウンタを増分し且つ最前の見出しの下方に位置する別の見出しを読取ることにより、所望のセクタの探索を継続する。そこで、マイクロプロセッサ９２はステップ２１２に戻り、この新たな見出しが所望の見出しであるか否かを判定する。
【００７３】
ＬＳＮが入力セクタ番号と等しいとき、マイクロプロセッサ９２はステップ２１４からステップ２１６へ進む。ステップ２１６では、現在見出しについて周期冗長検査ＣＲＣG を生成する。ステップ２１８では、ＣＲＣG を使用して、見出しに含まれている情報の信頼性をアクセスする。
そこで、マイクロプロセッサ９２は、セクタ番号ＳＮi をブロックに記憶されているＬＳＮと比較することにより、現在見出しがシーク中の見出しであるか否かを判定する。ＬＳＮ＝ＳＮi であれば、マイクロプロセッサ９２はステップ２１６へ進む。
ステップ２１８では、ＣＲＣG を選択した見出しに記憶されているＣＲＣと比較することにより見出しの信頼性を確定する。２つのＣＲＣが等しくない限り、見出しの中の情報を信頼することはできない。
【００７４】
現在見出しが信頼できるものではないならば、マイクロプロセッサ９２はステップ２１８からステップ２２０へ分岐する。現在見出しの中のブロックセクタオフセットを信頼することができないので、２つのデータのセクタは失われる。たとえば、図３に示すように、走査中の見出しがＬＳＮ1 に関わる見出しであったと仮定する。ＢＳＯ1 を信頼できないので、ＬＳＮ1 に関わるデータの始まりも、ＬＳＮ2 に関わるデータの終わりも共に確定することができない。従って、ステップ２２０では、マイクロプロセッサ９２は選択した見出しと、そのすぐ下方にある見出しの双方をダーティにすることにより、２つのデータのセクタを放棄する。次に、マイクロプロセッサ９２はステップ２２２へ進む。
【００７５】
現在見出しを信頼できる場合には、マイクロプロセッサ９２はステップ２１８からステップ２２０へ進む。ステップ２０６に達したならば、マイクロプロセッサ９２はセクタデータを読取るために必要とされる情報を収集し始める。まず、適切なＢＳＯを読取ることによりセクタのサイズを確定する。最後に、ステップ２０２では、セクタのサイズ及び属性語をチップ、ブロック及び見出しに対するオフセットと共に呼び出し側に戻す。次に、マイクロプロセッサ９２はステップ２０４で制御を呼び出し側に戻す。
【００７６】
Ｂ．ＦＬＡＳＨアレイ６２へのセクタの書込み
１つのデータのセクタの書込みは３つの主要なタスクを含む。第１に、そのセクタデータを書込むのに十分な空きメモリを位置指定し且つ予約しなければならない。第２に、同じＬＳＮの中にセクタデータの先のバージョンがあれば、それをダーティとマークし、セクタ見出し変換テーブル９４を更新する。第３に、セクタデータとその見出しを適切なブロックに書込む。
【００７７】
図９は、１つのデータのセクタをＦＬＡＳＨアレイ６２に書込むプロセスの概要を提示している。書込みは、ディスク１６０がＣＰＵ５２から入力セクタ番号ＳＮi を伴う書込み指令を受信したときに始まる。この時点で、ＦＬＡＳＨアレイ６２に書込むべきデータはセクタバッファ９８の中にある。ＬＳＮi 及びＳＨＴＴ９４に記憶されているデータに従って図１０のアルゴリズムを使用すると、いくつかの結果が起こりうる。
【００７８】
まず初めに、ＳＮi が無効であるときの結果を考える。書込み指令を受信したときのマイクロプロセッサ９２の第１のアクションは、ＳＮi を検査することである。これはステップ２３０で実行される。８３３００より大きいＳＮi 又は１より小さいＳＮi は、いずれも、４０ＭＢドライブには書込まれない。
【００７９】
ＳＮｉが無効であるとすれば、マイクロプロセッサ９２はステップ２３０からステップ２３２へ分岐する。そこで、受信したセクタ番号が無効であったことをインタフェース１５６に報知するために、マイクロプロセッサ９２は状態語をセットする。これを実行した後、マイクロプロセッサ９２はステップ２３４へ進む。次に、マイクロプロセッサ９２の制御は呼び出し側プログラムに戻る。
今度は、ＳＮi が有効であり且つその属性語はＳＮi と関連するトラックが不良とマークされたことを指示しているものと仮定する。ＳＮi は有効であるので、マイクロプロセッサ９２はステップ２３０からステップ２３６へ分岐する。
【００８０】
セクタを書込むための準備はステップ２３６で本格的に始まる。マイクロプロセッサ９２は電荷ポンプ１００をイネーブルし、電荷ポンプ１００にＦＬＡＳＨメモリをプログラムするために必要な１２ボルトのレベルを発生させることができる。そこで、マイクロプロセッサ９２は電荷ポンプ１００が１２ボルトに達するまで他のタスクを実行する。
【００８１】
ステップ２３８では、マイクロプロセッサ９２は、セクタデータのより以前のバージョンを求めて、チップ、ブロック及び見出しポインタを位置指定するためのシークアルゴリズムを呼び出す。セクタ番号と関連する情報を位置指定した後、マイクロプロセッサ９２はステップ２４０へ分岐する。
ステップ２４０では、マイクロプロセッサ９２は不良トラックビットがセットされているか否かを判定する。マイクロプロセッサ９２はセクタ属性語を検査することによりこれを実行する。不良トラックビットが表明されていたならば、マイクロプロセッサ９２はステップ２４０からステップ２４２へ進む。
【００８２】
ＳＮi と関連するトラックが不良であるとマークされているので、マイクロプロセッサ９２はセクタデータをＦＬＡＳＨアレイ６２に書込まない。ステップ２４２では、マイクロプロセッサ９２はトラックが不良であることをインタフェース１５６に報知する。その後、マイクロプロセッサ９２はステップ２３４へ分岐することにより制御をインタフェース１５６に戻す。
先の説明からわかるように、ＳＮi が無効であるか又はそれに関連するトラックが不良であるとマークされていたかのいずれかの場合には、データのセクタはＦＬＡＳＨアレイ６２に書込まれない。逆にいえば、セクタデータが良いトラック及び有効なＳＮi と関連しているならば、そのセクタデータはＦＬＡＳＨアレイ６２に書込まれることになる。次に、そのような状況について考えてみる。マイクロプロセッサ９２はステップ２３８からステップ２４４へ分岐することにより応答する。
【００８３】
ステップ２４４では、マイクロプロセッサ９２は電荷ポンプ１００が１２ボルトに達したか否かを判定するために、電荷ポンプ１００に絶えず問合わせる。電荷ポンプ１００が１２ボルトに達するのに要する時間の量は、電荷ポンプ１００が最後にイネーブルされてからどれほどの時間が経過しているかによって異なるので、予測不可能である。電荷ポンプ１００が始動して以来の時間が長いほど、１２ボルトに再び達するために要する時間は短くなる。電荷ポンプ１００が１２ボルトで安定したならば、マイクロプロセッサ９２はステップ２４６へ分岐する。
【００８４】
ステップ２４６では、マイクロプロセッサ９２は同じＬＳＮをもつ以前の見出しをダーティとマークすべきか否かを判定する。マイクロプロセッサ９２は、ステップ２３８のシークによって検索した情報に基づいてこの判定を実行する。見出しが位置指定されていた場合、マイクロプロセッサ９２はステップ２４７へ進み、その見出しをダーティとマークする。その後、マイクロプロセッサ９２はステップ２４８へ進み、以前の見出しがダーティとマークされていたか否か又はタスクがキャッシュされていたか否かを判定する。タスクがキャッシュされていなければ、マイクロプロセッサ９２はステップ２５０へ進む。キャッシュされていれば、マイクロプロセッサ９２はステップ２４９へ分岐する。ダーティとマークすることがキャッシュされていたため、現在書込みの終わりに同じＬＳＮをもつ２つの見出しが現れるであろう。パワー損失後に有効データを区別するために、ステップ２４９では、最も新しいバージョンと関連するＬＳＮに関わる改訂番号を増分する。次に、マイクロプロセッサ９２はステップ２５０へ進む。
【００８５】
マイクロプロセッサ９２は、ＦＬＡＳＨアレイ６２の中のセクタデータの新たなバージョンを書込むプロセスをステップ２５０をもって開始する。マイクロプロセッサ９２はデータのセクタ及び見出しを記憶するのに十分な空きメモリをＦＬＡＳＨアレイ６２の内部で割当てる。これは、以下に詳細に説明する複雑なプロセスである。ここでは、メモリの割当てには、１ブロックのデータスペース８６の中に十分なメモリを位置指定し且つそのメモリスペースを予約済としてマークすることが必要であると述べるだけで十分である。次に、マイクロプロセッサ９２はステップ２５２へ進む。
【００８６】
マイクロプロセッサ９２はステップ２５２及び２５４で見出しの書込みを完了する。まず、ステップ２５２では、見出しについてＣＲＣを生成するのであるが、ダーティビットと改訂番号は事象の経過の中で変化することがあるので、それらは除外される。その後、ステップ２５４では、属性語とＬＳＮをＢＳＴＴ８４に書込む。ＬＳＮをＳＮi と等しくなるように設定する。
マイクロプロセッサ９２は最終的にはステップ２５６で予約したデータスペースにセクタデータを書込む。データと共に、誤り訂正コードＥＣＣをも書込む。
【００８７】
セクタデータの新たなバージョンを確実に書込んだならば、ステップ２５８では、セクタ見出し変換テーブル９４がセクタ番号と関連するセクタデータの最も新しいバージョンを指示するように、マイクロプロセッサ９２はセクタ見出し変換テーブル９４を更新する。
【００８８】
ステップ２６０では、マイクロプロセッサ９２は電荷ポンプ１００をディスエーブルする。電荷ポンプ１００が必要でないときに電荷ポンプをオフすることにより、電力消費は減少する。その結果、固体ディスク６０はポータブルコンピュータやラップトップコンピュータに使用するのに一層適するようになる。これを実行したならば、マイクロプロセッサ９２はステップ２６２へ分岐する。
ステップ２６２の間に、マイクロプロセッサ９２は書込みの結果としてクリーンアップが必要であるか否かの評価を強制する。マイクロプロセッサ９２は、以下に詳細に説明する「Ｅｎａｂｌｅ  ＣＳＭ」と名付けられたサービスを呼び出すことによりこれを実行する。これを実行したならば、マイクロプロセッサ９２はステップ２３４へ進んで、制御を呼び出し側に戻す。
【００８９】
Ｃ．書込み時のメモリスペースの割当て
ＦＬＡＳＨアレイ６２の内部でのメモリスペースの割当ては複雑で重大なタスクである。メモリスペースを割当てなければならないだけでなく、性能劣化を阻止するために適切な記憶場所を選択しなければならない。セクタ書込みについて１つのブロックを選択することは、潜在的に、４つの主要な決定を含む。第１に、書込みを可能にするのに十分なＦＬＡＳＨメモリ予約があるか？第２に、現在セクタを記憶するために現在プロセスが最前に割当てられたブロックの中に十分な空きメモリがあるか？その第２の質問に対する返答がノーであれば、第３と第４の質問を尋ねなければならない。セクタデータを記憶するのに十分な空きＦＬＡＳＨメモリをもつブロックは存在しているか？そのブロックはこのセクタを記憶すべき適切なブロックであるか？
【００９０】
ブロックが適切なブロックであるか否かはいくつかの要因によって決まるので、第４の決定は難しい決定である。第１に、選択されるブロックは使用中のチップの対に含まれることができない。使用中のチップ対で待機することは、ＣＰＵ５２からの指令が従っている速度を遅くしてしまうので、それを回避する。第２に、選択されるブロックはクリーンアップの目標となっているブロックの中にあってはならない。クリーンアップの目標となっているブロックに書込むデータは全く別の場所に位置指定されなければならないであろう。第３に、選択されるブロックは別のプロセスに割当てられたのと同じチップ対の中にあってはならない。これはデータ断片化を回避する。データ断片化は最終的にはフォアグラウンド消去と、電力効率の減少という結果をもたらす。データ断片化は、ＦＬＡＳＨアレイ６２の全体にわたるクリーンセクタ、ダーティセクタ及び空きセクタの無作為な分布を表わす。メモリスペースの予約が少ない場合、データ断片化は固体ディスクの性能には重大な危険である。ＣＰＵ５２により開始された書込みをクリーンアップにより開始された書込みとは異なるチップ対に割当てることにより、ダーティセクタは１つのグループにまとまるようになるであろう。これで、クリーンアップ中にブロックからコピーしなければならないセクタの数は減少するので、電力効率とクリーンアップ性能は向上する。
【００９１】
図１０、１１は、ホスト書込み又はクリーンアップのために使用しうるメモリを割当てるアルゴリズムの流れ図である。図示されているアルゴリズムはセクタ１６２に属する。書込むべきセクタのサイズと、呼び出し側の型とが与えられれば、割当てアルゴリズムは十分なメモリを位置指定し且つ予約する。予約した記憶場所は将来のアルゴリズムによる参照に備えてＲＡＭに記憶される。
【００９２】
図１０、１１の割当てアルゴリズムを使用すると、いくつかの結果が起こりうる。まず、最大の関心をもたらす結果、すなわち、メモリを割当てる場合について考える。その他の結果については後に考慮する。
メモリの割当ては、メモリがクリーンアップのために要求されたのか又はホスト書込みのために要求されたのかを判定することによって始める。クリーンアップが空き物理メモリを要求する場合、マイクロプロセッサ９２はステップ２８２へ進む。これに対し、ホストＣＰＵ５２がメモリを要求した場合には、マイクロプロセッサ９２は利用可能なメモリ予約を考慮して書込みを許可すべきか否かを決定しなければならない。この判定はステップ２７２から２８０で起こる。
【００９３】
マイクロプロセッサ９２は、ステップ２７２で、所望のサイズのセクタを書込んだ後に利用可能な予約はどのようなものになるかを計算することにより、その判定を開示する。ここでいう「予約」はＦＬＡＳＨアレイ６２の中の空きメモリとダーティメモリの双方を指し、また、「セクタのサイズ」はデータと見出しの双方のサイズを含む。次に、利用可能な予約を第１の警告レベルＦＬＡＳＨ  Ｗａｒｎ  １と比較する。一実施例では、ＦＬＡＳＨ  Ｗａｒｎは１９ブロック分の予約を表わす。利用可能な予約がＦＬＡＳＨ  Ｗａｒｎ  １を越えると、マイクロプロセッサ９２はステップ２７３へ進む。そこで、マイクロプロセッサ９２は予約状態が受け入れ可能であることを指示する。その後、マイクロプロセッサ９２はステップ２８２へ進む。これに対し、利用可能な予約がＦＬＡＳＨ  Ｗａｒｎ  １を越えない場合には、マイクロプロセッサ９２はそれらの予約をさらに詳細に検査するように進んでゆく。しかしながら、まず、マイクロプロセッサ９２は、ステップ２７４で予約状態をＦＬＡＳＨ  Ｗａｒｎ  １に設定することにより、予約が第１の警告レベル以下に落ちたことを報知する。
【００９４】
ステップ２７５では、書込み後に残留している利用可能な予約を第２の警告レベルＦＬＡＳＨ  Ｗａｒｎ  ２と比較する。一実施例では、ＦＬＡＳＨ  Ｗａｒｎ  ２は１１ブロック分の予約を表わす。書込み後の利用可能な予約がこの第２の警告レベルを越えているならば、マイクロプロセッサ９２はステップ２８２へ分岐する。そうでない場合には、マイクロプロセッサ９２はステップ２７６へ進む。そこで、予約が第２の警告レベル以下に落ちたことを指示するために予約状態をリセットする。
【００９５】
マイクロプロセッサ９２は、ステップ２７８で、利用可能な予約を第３の警告レベルｓｔａｎｄｂｙと比較することにより、利用可能な予約を再評価する。一実施例ではｓｔａｎｄｂｙは２ブロック分の予約を表わす。書込みの後に利用可能な予約がｓｔａｎｄｂｙを越えるならば、マイクロプロセッサ９２はステップ２８２へ分岐することにより書込みを実行させる。利用可能な予約がｓｔａｎｄｂｙを越えない場合には、マイクロプロセッサ９２はステップ２７９へ進む。そこで、予約状態をｓｔａｎｄｂｙに設定される。その結果、ホストＣＰＵ５２によりセクタが解放されるまで、ＣＰＵ５２によるそれ以上の書込みは許可されなくなる。次に、ステップ３０４で、制御を呼び出し側に戻す。
【００９６】
マイクロプロセッサ９２は、データスペース８６の中に書込むべきセクタデータを記憶するのに十分な空きメモリをもつブロックを探索することをステップ２８２をもって開始する。マイクロプロセッサ９２は１組のブロックチェーンを使用して１つのブロックを探索する。図１２には、そのうち２つのブロックチェーンを示す。象徴的にいうならば、ブロックチェーン３２０は固体ディスク６０中の各チップ対（ＣＰM） のブロック１を一体に連鎖する。同様に、ブロックチェーン３２２は各チップ対（ＣＰM） のブロック１５を一体に連係している。図示してはいないが、ブロック２から１４も同様のチェーンとして連係されている。図示したようにブロックを連鎖させることは必要であるが、データのセクタをチップ対境界にまたがって分布させる。これは受動的な摩耗均等化を実現し、能動的な摩耗均等化をほぼ不要にする。
【００９７】
マイクロプロセッサ９２はＲＡＭに記憶されているポインタと関連してブロックチェーンを使用する。マイクロプロセッサ９２は最前に各呼び出し側に割当てられたチップとブロックを記憶する。次に同一のプロセスがセクタを書込もうとしたときには、割当てアルゴリズムは、まず、そのプロセスに最前に割当てられたブロックを検査する。これは関連するデータ「ファイル」を隣接メモリスペースに保持するのを助けると共に、データ断片化のおそれを減少させるのを助ける。マイクロプロセッサ９２が呼び出し側ごとにブロックを探索するにつれて、呼び出し側のポインタはブロックチェーンを循環してゆく。呼び出し側ごとに、ＲＡＭに記憶されている開始ポインタは異なるので、データ断片化の回避を助ける。各ポインタは独自の速度でブロックチェーンを巡って動く。加えて、各ポインタは、空きメモリの可用度に従って、異なる速度でブロックチェーンからブロックチェーンへと移行する。２つのポインタがチェーン中の同一のブロックを指示することは決してない。
【００９８】
このようにブロックチェーンを理解した上で、図１０、１１の割当てアルゴリズムに従った十分なメモリをもつブロックの位置指定に戻って再び論じる。ステップ２８２では、マイクロプロセッサ９２は利用可能スペースを求めてどのブロックチェーンをも検査したか否かを判定する。まだ、２つ以上のブロックチェーンを検査していないときは、マイクロプロセッサ９２はステップ２８２からステップ２８４へ分岐する。
【００９９】
ステップ２８４では、マイクロプロセッサ９２は利用可能スペースを求めて現在ブロックチェーン中のどのチップをも探索したか否かを判定する。探索していなければ、現在ブロックチェーンからチップを選択する。ブロックチェーンで選択される第１のチップは、同一のプロセスにより最前に割当てられたチップである。従って、ＣＰＵ５２が最前にＣＰ３、ブロック５にセクタを書込んだ場合、次の書込みで検査される第１のブロックはＣＰ３、ブロック５になるであろう。ブロックを選択したならば、マイクロプロセッサ９２はステップ２８６へ分岐する。
【０１００】
ステップ２８６では、現在チップ対が使用中であるか否かを知るために、マイクロプロセッサ９２は現在チップ対の状態レジスタを問い合わせる。そのチップが使用中であれば、マイクロプロセッサ９２はステップ２８８へ分岐する。
ステップ２８８８では、マイクロプロセッサ９２は現在ブロックチェーンにおける次のチップを選択する。たとえば、ステップ２８４でチップ対３、ブロック５が選択された場合には、チップ対４、ブロック５を選択することになる。これを実行したならば、マイクロプロセッサ９２はステップ２８４に戻る。
【０１０１】
ステップ２８４では、マイクロプロセッサ９２は現在ブロックチェーンにおけるどのブロックをも探索したか否かを知るために再び検査を実行する。これは検査すべきチェーンの第２のブロックであるので、マイクロプロセッサ９２は再びステップ２８６へ進む。
ここで、マイクロプロセッサ９２は、現在チップ対が使用中であるか否かを判定する。使用中であるならば、マイクロプロセッサ９２は先に説明したようにステップ２８８及び２８４を通って進む。これに対し、現在チップ対が使用中でない場合には、マイクロプロセッサ９２はステップ２８９へ進む。
【０１０２】
マイクロプロセッサ９２は、現在選択されたチップ対が別の呼び出し側に割当てられているか否かを判定する。マイクロプロセッサ９２は、他の呼び出し側に関してＲＡＭに記憶されているチップ及びブロックを現在選択されたチップ及びブロックと比較することにより、ステップ２８９でこれを実行する。たとえば、呼び出し側はＣＰＵ５２であり且つそれにチップ対４、ブロック４が割り当てられていると仮定する。クリーンアップ状態機械１にチップ対４の１つのブロックが割当てられた場合、マイクロプロセッサ９２はチップ対４の中のメモリスペースをＣＰＵ５２に割当てない。この状況で、マイクロプロセッサ９２はステップ２９０へ進む。
ステップ２９０では、現在ブロックチェーンにおける別のブロックを選択する。マイクロプロセッサ９２はステップ２９２からステップ２８４に戻る。
【０１０３】
以前にそのメモリが割当てられるであろうということを仮定しているので、マイクロプロセッサ９２はステップ２８４、２８６及び２８９を通過することにより、最終的にはステップ２９１に至る。ステップ２９１では、マイクロプロセッサ９２は現在ブロック選択が別のブロックをクリーンアップの目標としているチップの一部であるか否かを判定する。一部であるならば、プログラムのために消去を延期できない限り、現在ブロック選択は望ましくない。そうでない場合には、消去によりセクタの書込みは遅延されるであろう。これを回避するために、マイクロプロセッサ９２はステップ２９２で現在ブロックチェーン中の別のチップを選択する。次に、ステップ２８４〜２９１を再び分岐することにより、そのブロックの適否を判定する。
【０１０４】
クリーンアップに含まれないブロックを位置指定したとき、マイクロプロセッサ９２はステップ２９３に到達する。ここで、マイクロプロセッサ９２は、シーク方式と一致した現在ブロックのＢＳＴＴ８４に別の見出しを書込むことができるか否かを判定する。たとえば、一実施例では、シークごとに最大限８つの見出しを検査し且つ使用する見出しポインタはわずか２５６であるものとすれば、どのＢＳＴＴにも２０４７個の見出しのみを書込めるであろう。最大数の見出しを既にＢＳＴＴ８４に書込んだならば、別のブロックを選択しなければならない。マイクロプロセッサ９２はステップ２９４へ分岐することによりそれを実行する。そうでない場合には、マイクロプロセッサ９２はステップ２９５へ分岐することにより現在ブロックの評価を継続する。
【０１０５】
ステップ２９５では、マイクロプロセッサ９２は、現在ブロックのデータスペース８６の中にセクタを記憶するのに十分なメモリが存在しているか否かを判定する。圧縮によってセクタのサイズは変化するため、この検査が必要なのである。その結果、データスペース８６に記憶できるセクタの数が変化する。データスペース８６が書込むべきセクタを記憶するのに十分なメモリを含んでいない場合、マイクロプロセッサ９２は別のブロックを選択しなければならない。マイクロプロセッサ９２はステップ２９６でこれを実行する。
【０１０６】
セクタを記憶するのに十分な余地をもつブロックを位置指定したならば、マイクロプロセッサ９２はセクタデータを現在ブロックに割当てる前に１つの最後の検査を実行する。ステップ２９７では、ブロックの良否を判定するために、マイクロプロセッサ９２はブロックのブロック属性データ９０を検査する。ブロックが不良であれば、マイクロプロセッサ９２はステップ２９８へ進んで、現在ブロックチェーンにある別のチップを選択する。これに対し、ブロックが合格である場合には、適切なブロックが最終的に見出されたことになる。マイクロプロセッサ９２はステップ２９９へ分岐することにより応答する。
【０１０７】
ステップ２９９では、将来の参照に備えて、マイクロプロセッサ９２は選択したばかりのチップとブロックをＲＡＭに記憶する。
ステップ３００へ分岐することにより、マイクロプロセッサ９２は最終的には書込むべきセクタのためのメモリを割当てる。マイクロプロセッサ９２は、選択したブロックのＢＳＴＴ８４にブロックセクタオフセットを書込むことによりこれを実行する。
マイクロプロセッサ９２はステップ３０１でＦＬＡＳＨアレイデータベース９３を更新する。ＦＬＡＳＨアレイ６２と、チップ及びブロックにおける空きメモリの総量（ＴＦＦＡ，ＴＦＦＣ（ＣM）及びＴＦＦＢ（ＢN））をセクタのサイズだけ減少させる。データベースの更新が完了すると、マイクロプロセッサ９２はステップ３０２へ分岐する。
【０１０８】
最後に、ステップ３０２で、チップ、ブロック及び見出しに対するオフセットを呼び出し側に戻る。ここでいう「見出しに対するオフセット」又は「見出しオフセット」は、ブロックの最上位部分から見出しの最上位部分までのオフセットを表わす。割当てが完了すると、ステップ３０４で制御は呼び出し側に戻る。
【０１０９】
図１０、１１のアルゴリズムを使用してメモリスペースを割当てることができないいくつかの状況がある。おそらくは、固体ディスク６０が待機モードにあるためか又は適切なブロックを位置指定できないために、メモリを割当てられないのであろう。どこで、どのように、メモリの割当てが不可能であるという決定が下されようとも、マイクロプロセッサ９２はステップ３０６へ向かう。
【０１１０】
ステップ３０６では、マイクロプロセッサ９２はメモリの割当てが不可能であることを矯正できるか否かを判定する。それは、メモリスペースを要求した呼び出し側によって決まる。呼び出し側がＣＰＵ５２である場合、マイクロプロセッサ９２はステップ３０８へ進む。これに対し、メモリスペースを要求している呼び出し側が２つのクリーンアップ状態機械の一方である場合には、マイクロプロセッサはステップ３１０へ分岐する。
呼び出し側がＣＰＵ５２である場合、メモリの割当てが不可能であることをフォアグラウンドクリーンアップにより矯正できる。そこで、ステップ３０８では、マイクロプロセッサ９２はフォアグラウンドクリーンアップを開始させる。その結果、ＣＰＵ５２の書込み指令のいずれかに従って動作を実行することになるので、ＣＰＵ５２は相対的に長い時間にわたって待機しなければならない。
【０１１１】
メモリを割当てることができず且つ呼び出し側がクリーンアップ状態機械の一方である場合には、実行すべきことはほとんどない。以下に詳細に説明するように、フォアグラウンドクリーンアップは２つ以上のクリーンアップ状態機械を使用する。一実施例では、フォアグラウンドクリーンアップは２つのクリーンアップ状態機械を使用する。第１のクリーンアップ状態機械はブロックを消去し始めるまで中断なく動作する。消去を開始した時点で、第２のクリーンアップ状態機械が始動する。しかしながら、第１のクリーンアップ状態機械による消去のために余りに多くの数のブロックが利用不可能であるので、第２のクリーンアップ状態機械にメモリを割当てることは不可能であろう。第１のクリーンアップ状態機械によるクリーンアップが完了したときには、大量の空きメモリが形成されているので、これは重大な危険ではない。マイクロプロセッサ９２は、ステップ３１０で、呼び出し側のクリーンアップ状態機械の状態をアイドル状態に変化させることにより、その事象を待機するよう準備する。次に、ステップ３０４で、マイクロプロセッサ９２は制御を呼び出し側に戻す。
【０１１２】
図１３、１４は、ホスト書込みに際して空き物理メモリを割当てる別の方法を流れ図の形で示す。図１０、１１の方法と同様に、書込みを割当てるべきブロックの選択は４つまでの決定を含むと思われる。メモリを割当てるための決定のうち２つは図１０、１１の方法に従って実行されるのとほぼ同じ方式で実行される。それらの決定は、
１．書込みを許可するのに十分な予約メモリが存在しているか？
２．ブロックは書込みを割当てるのに適切なブロックであるか？
の２つである。図１３、１４の方法は、図１０、１１の方法で行われていたように、書込むべきデータのセクタを記憶するのに十分なメモリを有する第１のブロックを選択するのではなく、最も多くの量の空きメモリを有する新たなブロックをホスト書込みの割当てのために選択することにより、ホスト書込みに対するデータのコヒーレンシーを増大させる。最も多くの量の空きメモリをもつブロックを選択する結果として、別のデータのセクタを記憶するのに空きメモリが不十分になるまで書込みは選択したブロックに割当てられるようになるので、より多くの量のホストデータが同じブロックに存在するのである。この割当ての方法はデータのコヒーレンシーを増大させる。
【０１１３】
ステップ１２０２では、要求されたセクタを書込んだ後にフラッシュアレイ６２内部の最小限のメモリ予約が維持されるであろうか否かを判定することにより、空き物理メモリの割当てが始まる。維持されないのであれば、ステップ１２０４で、固体ディスク６０はＦＬＡＳＨ  ＳＴＡＮＤＢＹにあることをホストＣＰＵ５２に報知する。ホストＣＰＵ５２が最小限のメモリ予約に達するのに十分なメモリを解放するまで、それ以上のホスト書込みは許可されない。これに対し、最小限のメモリ予約が利用可能である場合には、マイクロプロセッサ９２はステップ１２０５へ進む。
【０１１４】
データのコヒーレンシーを増大させ且つデータ断片化の可能性を減少させるために、ステップ１２０５で、マイクロプロセッサ９２はホストデータが最前に書込まれたブロックにセクタを割当てようと試みる。簡略にするため、このブロックを「前のブロック」と呼ぶ。まず、マイクロプロセッサ９２はどのブロックが前のブロックであるかを確定し、データベース９３を参照することにより、先のブロックに残っている空きメモリの量を確認する。前のブロックにある空きメモリの量がセクタのサイズ以上である場合、セクタを前のブロックに書込む。その場合、マイクロプロセッサ９２は先のステップ１２６２へ分岐して、前のブロックのメモリを予約する。これに対して、前のブロックの空きメモリが不十分である場合には、マイクロプロセッサ９２はステップ１２０６へ分岐する。
【０１１５】
ステップ１２０６、１２０８及び１２１０では、マイクロプロセッサ９２は１つのブロックの選択で使用される変数を初期設定する。それらのステップの間に、Ｍｏｓｔ  Ｆｒｅｅ  Ｂｌｏｃｋ，Ｍｏｓｔ  Ｆｒｅｅ  Ｃｈｉｐ，Ｇｒｅａｔｅｓｔ  Ｓｃｏｒｅ及びＭｏｓｔ  Ｆｒｅｅを初期設定することになる。Ｍｏｓｔ  ＦｒｅｅはＭｏｓｔ  Ｆｒｅｅ  Ｂｌｏｃｋの中の空きフラッシュメモリの量を表わす。その後、マイクロプロセッサ９２はステップ１２１２へ進む。
【０１１６】
ステップ１２１２はＦＬＡＳＨアレイ６２中の各ブロックのブロックごとの評価を開始する。まず、ステップ１２１４〜１２３０で、各ブロックの適否を判定するために各ブロックを検査する。ブロックが適切であるとわかれば、ステップ１２３２〜１２４０で、そのブロックに関わるスコアを生成することにより、そのブロックにセクタ書込みを割当てる所望度を確定する。次に、ブロックごとのスコアをＧｒｅａｔｅｓｔ  Ｓｃｏｒｅと比較する。そのスコアがＭｏｓｔ  Ｆｒｅｅを越えれば、ステップ１２４４〜１２４８において、現在ブロックの値を反映するために、Ｍｏｓｔ  Ｆｒｅｅ，Ｍｏｓｔ  Ｆｒｅｅ  Ｂｌｏｃｋ及びＧｒｅａｔｅｓｔ  Ｓｃｏｒｅを全て改訂する。
【０１１７】
ブロックの選択は、ステップ１２１２で、全てのブロックを検査したか否か、従って、割当てのために１つのブロックを選択したか否かを判定することにより始まる。マイクロプロセッサ９２は、全てのチップ対を探索したか否かを判定することによりこれを実行する。まず最初にステップ１２１２を通過して、マイクロプロセッサ９２は検査のために１つのブロックを選択し、一対だけではないチップが検査されているために、ステップ１２１４へ分岐する。
【０１１８】
ステップ１２１４では、マイクロプロセッサ９２は、チップ対が使用中であるか否かを知るために、現在を含めた現在チップ対の状態レジスタを問合わせる。そのチップ対が使用中であれば、相対的に長い期間にわたりそのチップ対は利用不可能になる。このため、マイクロプロセッサ９２はステップ１２１２へ分岐して、現在ブロックが使用中のチップ対の一部であるときに別のブロックを選択する。そうでない場合には、マイクロプロセッサ９２はステップ１２１６へ進む。
【０１１９】
ステップ１２１６では、マイクロプロセッサ９２は、現在ブロックがクリーンアップの目標となっている別のブロックを含むチップ対の一部であるか否かを判定する。一部であれば、プログラムのために消去を延期できない限り、現在ブロックを選択することは望ましくない。そうでない場合には、セクタの書込みは消去により遅延されてしまうであろう。これを回避するために、マイクロプロセッサ９２はステップ１２１２に戻って、別のブロックを選択する。クリーンアップの目標となっているチップ対に含まれない現在ブロックが選択されたときには、マイクロプロセッサ９２はステップ１２１８へ進む。
【０１２０】
ステップ１２１８の間、マイクロプロセッサ９２は、現在選択されたブロックチップ対のメモリが最近にクリーンアップ状態機械に割当てられていたか否かを判定する。そのようなブロックの選択はデータ断片化のおそれを大きくするために、ホスト書込みに対しては不適切である。マイクロプロセッサ９２は、クリーンアップ状態機械についてＲＡＭに記憶されているチップ及びブロックを現在選択されたチップ及びブロックと比較することにより、この決定を実行する。たとえば、現在ブロック選択がチップ対４、ブロック４であると仮定する。チップ対４の１つのブロックがクリーンアップ状態機械１に割当てられると、マイクロプロセッサ９２はチップ対４の中のメモリスペースをＣＰＵ５２に割当てない。これらの状況においては、マイクロプロセッサ９２はステップ１２１２へ戻り、別のブロックを選択する。
【０１２１】
ステップ１２２０では、マイクロプロセッサ９２は、ブロックの良否を判定するために、現在ブロックに関わるブロック属性データ９０を検査する。不良であれば、マイクロプロセッサ９２はステップ１２１２へ進み、別のブロックを選択する。これに対し、ブロックが適切なブロックである場合には、マイクロプロセッサ９２は現在ブロックの適否の評価を継続することにより応答する。
ステップ１２３０は、現在ブロックのＢＳＴＴ８４にスペースが残っているか否かをアクセスして、現在ブロックが適切なブロックであるか否かを判定する際の最終ステップである。ＢＳＴＴ８４に最大数の見出しが既に書込まれているならば、別のブロックを選択しなければならない。
【０１２２】
ステップ１２３０からステップ１２３２へ出ることは、現在ブロックがホスト書込みの割当てについて適切であることを意味している。そこで、マイクロプロセッサ９２はいくつかの係数する包含する総スコアにより表わされている現在ブロックの所望度を評価し始める。考慮される第１の係数は、現在ブロックの中の空き語の総数ＴＦＦＢC である。このＴＦＦＢC に第１の重みを乗算するのであるが、第１の重みの値は他の重みの値より相当に大きくすべきである。これはブロックの選択を最大量の空き物理メモリをもつブロックへ向かわせる。
【０１２３】
マイクロプロセッサ９２は、ステップ１２３４へ分岐することにより所望度の評価を継続する。マイクロプロセッサ９２は、ＴＤＦＣとして表わされる現在チップ対の中のダーティメモリの量をＴＰＤＦＣとして表わされる現在チップ対の中のダーティメモリの可能総量から減算することにより、現在ブロックが将来のクリーンアップによる影響を受ける確率を検査する。次に、この演算の剰余に重み２を乗算して、Ｒｕｌｅ  ２を生成する。ＴＤＦＣが小さいほど、Ｒｕｌｅ  ２は大きくなり、現在チップ対がクリーンアップのために直ちに選択される確率は低くなる。
現在ブロックの所望度は現在ブロック中のダーティメモリの量ＴＤＦＢによっても評価される。ステップ１２３５では、ＴＤＦＢに重み３を乗算して、Ｒｕｌｅ  ３を生成する。
【０１２４】
現在ブロックの所望度をアクセスするに際して評価されるもう１つの係数は、アレイ６２中の最大サイクルカウントと比較される現在ブロックの番号サイクルカウントである。「Δサイクルカウント」と表わされるこの係数にステップ１２３６において重み４を乗算する。この係数はブロックの選択をサイクルカウントの少ないブロックへ向かわせ、その結果、受動的摩耗均等化が実現する。
マイクロプロセッサは現在ブロックの所望度の第５の、そして、最後の係数をステップ１２３８でアクセスする。この係数は、現在チップ中の他のいずれかのブロックが割当てられていないかどうかというものである。これも、セクタデータをチップ境界にまたがって拡散させることにより幾分かの摩耗均等化を実現する。この係数に重み５を乗算して、Ｒｕｌｅ  ５を生成する。
【０１２５】
ステップ１２４０では、マイクロプロセッサはＲｕｌｅ  １、Ｒｕｌｅ  ２、Ｒｕｌｅ  ３、Ｒｕｌｅ  ４及びＲｕｌｅ  ５を加算することにより現在ブロックの総スコアを生成する。次に、マイクロプロセッサ９２はこの総スコアをＧｒｅａｔｅｓｔ  Ｓｃｏｒｅと比較する。総スコアがＧｒｅａｔｅｓｔ  Ｓｃｏｒｅを越えていれば、現在ブロックはそれまでに評価したブロックの中で最も望ましいブロックである。従って、ステップ１２４４、１２４６及び１２４８で、現在ブロックの値を反映するために改訂する。その後、マイクロプロセッサ９２はステップ１２１２に戻り、ＦＬＡＳＨアレイ６２の別のブロックを評価する。
【０１２６】
全てのブロックを評価し終わった後、マイクロプロセッサ９２はステップ１２５０へ分岐する。そこで、最も空きの多いブロックの中にＣＰＵ５２が書込みを希望するデータのセクタを記憶するのに十分な空きメモリが存在しているか否かを判定する。存在しているならば、ステップ１２６２へ分岐することにより割当ては進行する。そうでない場合には、マイクロプロセッサ９２はステップ１２６０へ分岐する。
【０１２７】
ステップ１２６０に入るということは、現在セクタを記憶するのに十分な空きメモリをもつブロックを位置指定できるようになる前にＦＬＡＳＨアレイ６２をクリーンアップしなければならないことを意味している。そこで、マイクロプロセッサ９２はフォアグラウンドクリーンアップを開始する。ブロックをクリーンアップしたならば、マイクロプロセッサ９２はステップ１２１２に戻り、割当てのために別のブロックを選択する。
【０１２８】
最終的には、データのセクタを記憶するのに十分なスペースをもつブロックを識別し、マイクロプロセッサ９２はステップ１２６２に到達する。データのセクタに対するメモリスペースの割当ては、本格的には、Ｍｏｓｔ  Ｆｒｅｅ  ＢｌｏｃｋのＢＳＴＴ８４の中の次に利用可能な見出しを識別することにより始まる。次に、ステップ１２６４で、そのセクタに関わる適切なブロックセクタオフセットをその見出しに書込む。その後、アレイ、Ｍｏｓｔ  Ｆｒｅｅ  Ｃｈｉｐ及びＭｏｓｔ  Ｆｒｅｅ  Ｂｌｏｃｋにある空きフラッシュの総量をセクタのサイズだけ減少させる。最後に、ステップ１２６６では、マイクロプロセッサは書込むべきデータのセクタと現在関連しているチップ、ブロック及び見出しに対するオフセットを指示する。
【０１２９】
Ｄ．セクタのバージョンをダーティとマークする動作
図１５は、セクタ１６２により実現される、セクタをダーティとマークする動作のアルゴリズムを流れ図の形で示す。このアルゴリズムは書込みの間、クリーンアップ中及びセクタ見出し変換テーブル９４の作成中に有用である。
【０１３０】
ダーティとマークするアルゴリズムは、ダーティとマークすべきセクタデータに関わるチップ、ブロック及び見出しに対するオフセットという３種類の情報を要求する。この情報を与えられたときのステップ３２０におけるマイクロプロセッサ９２の第１のタスクは、そのバージョンのセクタデータを記憶するチップ対の利用度を確定することである。従って、ステップ３２０では、マイクロプロセッサ９２は適切なチップ対と関連する状態レジスタを読取る。チップ対が使用中であれば、マイクロプロセッサ９２はステップ３２２へ分岐する。これに対して、チップ対が使用中でない場合には、マイクロプロセッサ９２はステップ３２４へ分岐する。
【０１３１】
ステップ３２２に入るということは、所望のセクタが利用不可能であることを表わしている。クリーンアップはチップ対の不利用度についての唯一可能な説明である。クリーンアップを終了するのを待つのではなく、マイクロプロセッサ９２はセクタの前のコピーをダーティとマークするための注釈を象徴的に残す。マイクロプロセッサ９２は、ダーティとマークすべきセクタデータのチップ、ブロック及び見出しに対するオフセットをキャッシュすることにより、これを実行する。クリーンアップが完了したとき、キャッシュを検査し、セクタをダーティとマークする。その後、マイクロプロセッサ９２はステップ３２６へ分岐して、その呼び出し側に制御を戻す。
【０１３２】
セクタデータの前のコピーを記憶しているチップ対が使用中でない場合には、マイクロプロセッサ９２はステップ３２０からステップ３２４へ進む。そこで、マイクロプロセッサ９２はチップブロック及びオフセットにより指示されるセクタのコピーをダーティとマークする。データのセクタは、セクタの見出しの属性語の中のダーティビットを０にセットすることにより、ダーティとマークされる。これを実行したならば、マイクロプロセッサ９２はステップ３２６へ進み、制御を呼び出し側に戻す。
【０１３３】
III． 固体ディスクのクリーンアップ
固体ディスクドライブ６０は、データのセクタが改訂されるたびに、前の記憶場所を消去し且つ改訂したデータをその同じ物理記憶場所に書込むのではなく、そのデータのセクタを新たな記憶場所に書込むことにより、従来の磁気ディスクドライブに近い書込み速度を達成する。これを実行した結果、固体ディスク６０にダーティセクタがまき散らされることになる。ダーティセクタが占めているメモリスペースを回復することはクリーンアップを指定する。若干異なる言いかたをすれば、固体ディスク制御装置６４の書込み慣例によれば、ダーティセクタを空きメモリに変換する必要がある。
【０１３４】
簡単に説明すると、クリーンアップは３つの主要タスクを含む。第１に、クリーンアップの焦点としてブロックを選択する。第２に、有効ユーザーデータのセクタを焦点ブロックから宛先ブロックと呼ばれる他のブロックにコピーする。第３に、全ての有効セクタを焦点ブロックからコピーした後、焦点ブロックを消去し、ダーティセクタを空きメモリに変換する。
クリーンアップは、一般にバックグラウンドプロセスである。ＦＬＡＳＨアレイ６２に対する読取りと書込みは、通常は、バースト単位で起こるので、クリーンアップはバックグラウンドプロセスとしてランすることができる。その結果、マイクロプロセッサ９２が自在にクリーンアップするときの期間は相対的に長い。
【０１３５】
クリーンアップは、クリーンアップ状態機械と呼ばれる有限状態機械により管理される。すなわち、クリーンアップは互いに連鎖する限られた数の状態、すなわち、アルゴリズムを使用して実行される。各々のクリーンアップ状態は次の状態を指示し、各状態を実際には別の状態に連鎖してゆく。各状態はＣＰＵ９２の実行時間として５００μ秒以上を要さない。
バックグラウンドクリーンアップは単一のクリーンアップ状態機械を使用し、ホストインタフェース１５２が不作動状態であるときに限って実行時間を許可される。これとは対照的に、固体ディスク６０のフォアグラウンドクリーンアップの間には、２つのクリーンアップ状態機械が同時にランする。書込み要求に対して空きメモリが不足しているためにＣＰＵ５２からの書込み指令を実行できないとき、クリーンアップはフォアグラウンドタスクになる。
【０１３６】
バックグラウンドクリーンアップとフォアグラウンドクリーンアップは共に固体ディスク制御装置１１４のクリーンアップオブジェクト１６４により処理される。図１５は、クリーンアップオブジェクト１６４の高レベルアルゴリズムをブロック線図の形で示す。アルゴリズムはＣＳＭイネーブル３４０と、クリーンアップ強制３４２と、マルチクリーンアップ強制３４４と、１状態実行３４６と、条件調整までマルチＣＳＭ実行３４８とを含む。
バックグラウンドクリーンアップは、ＣＳＭイネーブルアルゴリズム３４０が呼び出されたときに始まる。ＣＳＭイネーブル３４０は、固体メモリディスク６０にホストが書込むたびに呼び出される。たとえば、ＣＳＭイネーブル３４０は図１０、１１の書込みアルゴリズムステップ２６０で呼び出される。ＣＳＭイネーブル３４０はＣＳＭ次状態ポインタをクリーンアップ状態に設定することによりクリーンアップ状態機械を起動する。
【０１３７】
その第１のクリーンアップ状態の実行は、トップレベルスケジューラ１５０がクリーンアップにＣＰＵ９２の時間を割当てるたびに起こる。トップレベルスケジューラ１５０は１状態実行アルゴリズム３４６を呼び出すことによりこれを実行する。１状態実行３４６はＣＳＭ次状態ポインタにより指示される状態を呼び出す。その状態は、どちらの状態であれ、ＣＰＵ９２の状態を引き渡すのに先立って、次状態ポインタを変更する。従って、トップレベルスケジューラ１５０がクリーンアップに実行時間を割当てるたびに、１状態実行を呼び出すことにより別のステップが実行されるのである。
【０１３８】
フォアグラウンドクリーンアップはクリーンアップ１６４のサービス３４８を呼び出すことによって始まる。条件調整までマルチＣＳＭ実行３４８は、書込み要求に対して空きメモリを割当てることができないときに呼び出される。これは、それ以上の書込みを実行する前に空きメモリを生成する必要があるという決定を表わしている。条件調整までマルチＣＳＭ実行３４８は、２つのクリーンアップ状態機械をイネーブルすることによりこれを実行する。
フォアグラウンドクリーンアップ及びバックグラウンドクリーンアップとは対照的に、クリーンアップ強制３４２とマルチクリーンアップ強制３４４の双方はＣＰＵ５２により呼び出される。クリーンアップ強制３４２は一方のクリーンアップ状態機械をイネーブルし、また、マルチクリーンアップ強制３４４は２つのクリーンアップ状態機械をイネーブルする。
【０１３９】
Ａ．バックグラウンドクリーンアップ
１．バックグラウンドクリーンアップの開始とクリーンアップ状態の連係
バックグラウンドクリーンアップはＣＳＭイネーブル３４０に対する呼び出しによって開始される。ＣＳＭイネーブル３４０の流れ図を図１７に示す。
ステップ３６０におけるマイクロプロセッサ９２の第１のタスクは、クリーンアップ状態機械１が既に活動状態であるか否かを判定することである。活動状態であれば、実行すべきことは何もない。その場合には、マイクロプロセッサ９２は何もせずにステップ３６１へ分岐する。クリーンアップ状態機械１が活動状態でない場合、マイクロプロセッサ９２はステップ３６２へ分岐する。
【０１４０】
ステップ３６２では、マイクロプロセッサ９２はバックグラウンドクリーンアップを開始するために必要な２つの小さなタスクのうち第１のタスクを実行する。そこで、マイクロプロセッサ９２は変数ＣＳＭ１．ｓｔａｔｕｓを活動に設定することによりクリーンアップ状態機械１（ＣＳＭ１）を活動状態にする。これを実行したならば、マイクロプロセッサ９２はステップ３６４へ進む。
次に、マイクロプロセッサ９２はバックグラウンドクリーンアップをセットアップするために要求される第２のタスクを実行する。これは、ＣＳＭ１の次状態ポインタをクリーンアップが必要か否か評価状態３８０に設定することにより実行される。次に、トップレベルスケジューラ１５０が１状態実行３４６を呼び出したときに、バックグラウンドクリーンアップは始まる。そのジョブを実行したならば、マイクロプロセッサ９２はステップ３６１へ分岐する。
【０１４１】
図１８は、クリーンアップ状態機械の状態を互いに連鎖するアルゴリズムである１状態実行３４６の流れ図である。単一のアルゴリズムによって多数の状態を連鎖させるメカニズムは、ＣＳＭ次状態ポインタである。各々のクリーンアップ状態機械は独自の次状態ポインタを有しており、そのポインタはそれぞれの状態の終了時に更新される。
１状態実行３４６に入ると、マイクロプロセッサ９２は、ＣＳＭ２．ｓｔａｔｕｓを検査することにより、第２のクリーンアップ状態機械ＣＳＭ２が活動状態であるか否かを判定する。ＣＳＭ２が活動状態でない場合、マイクロプロセッサ９２はステップ３７０へ直接に分岐する。これに対し、フォアグラウンドクリーンアップがちょうど終了しようとしているときには、その結果、ＣＳＭ２は活動状態になるであろう。この場合、マイクロプロセッサ９２はステップ３６８でＣＳＭ２の別の状態を実行する。次に、ステップ３７４で制御を呼び出し側に戻す。
【０１４２】
ＣＳＭ２がアイドル状態になると、ＣＳＭ１が活動状態であれば、マイクロプロセッサ９２はＣＳＭ１に注意を集中する。マイクロプロセッサ９２はステップ３７０でこの決定を実行する。ＣＳＭ１が非活動状態であれば、実行すべきことは何もないが、ステップ３７４で制御を呼び出し側に戻す。そうでない場合には、ＣＳＭ１の次状態ポインタが指示している状態を実行する。その後、ステップ３７４で制御を呼び出し側に戻す。
【０１４３】
２．クリーンアップ状態機械の状態の概要
クリーンアップ中の事象の連鎖はどのようなものであろうか？簡単にいえば、クリーンアップはその種類にかかわらず３つの主要タスクを含む。第１に、クリーンアップの焦点として１つのブロックを選択する。第２に、良セクタごとに、ユーザーデータを焦点ブロックから宛先ブロックへ置き換える。ユーザーデータの置き換え自体は複数のステップから成るプロセスであって、メモリの割当てと、宛先ブロックへのセクタのコピーと、ＦＬＡＳＨデータベース９３の更新とを要求する。第３に、全てのユーザーデータを焦点ブロックからコピーし終わった後に、焦点ブロックを消去し、ダーティセクタを空きメモリに変換する。
【０１４４】
図１９は、クリーンアップ状態機械の各々の状態を示すことにより、クリーンアップの概要を表わしている。図１９の中の丸印はクリーンアップ状態機械の１つの状態、すなわち、１つのアルゴリズムを表わす。状態間の矢印は、１つの状態の終了時にＣＳＭ次状態ポインタにより指示される次状態を表わす。
バックグラウンドクリーンアップは、状態３８０で、クリーンアップが必要であるか否かを評価することによって始まる。フォアグラウンドクリーンアップと、強制クリーンアップの間には、クリーンアップが必要であるか否かの評価を飛び越す。クリーンアップが必要でなければ、マイクロプロセッサ９２は状態３９６へ分岐する。これはマイクロプロセッサ９２の制御をトップレベルスケジューラ１５０に戻す。これに対し、クリーンアップが必要であると考えられる場合には、いくつかのブロックをクリーンアップする。カウンタにより、選択された数のブロックを指示する。その後、ＣＳＭ次状態ポインタによりマイクロプロセッサ９２は次状態３８２へ指示される。
クリーンアップは、状態３８２で、クリーンアップのために焦点ブロックを選択することによって本格的に始まる。次に、次状態ポインタはマイクロプロセッサ９２を状態３８３へと指示する。
【０１４５】
焦点ブロック中のダーティセクタをクリーンアップするのに先立って、ユーザーデータの有効セクタを安全に再配置しなければならない。このタスクは、焦点ブロック中のユーザーデータのあらゆるセクタが新たな記憶場所へ安全にコピーされ終わるまで、状態３８３、３８４、３８５、３８６及び３８８を通って繰り返し分岐することを要求する。ユーザーデータの再配置は、状態３８４で、ユーザーデータの１つの良セクタに対して新たな物理記憶場所を位置指定することによって始まる。新たな記憶場所として選択されるブロックを宛先ブロックという。この用語に従えば、クリーンアップは１つの焦点ブロックを有するが、宛先ブロックは数多くある。次に、ＣＳＭ次状態ポインタはマイクロプロセッサ９２に状態３８５を指示する。
【０１４６】
状態３８５では、焦点ブロックからセクタバッファ９８へセクタをコピーする。
状態３８６では、マイクロプロセッサ９２は有効セクタの一部をセクタバッファから現在宛先ブロックにコピーする。バックグラウンドクリーンアップがＣＰＵ５２からの読取り指令及び書込み指令への応答に影響を及ぼすのを阻止するという希望に従って、書込み速度が与えられたならば、一度に有効セクタの一部のみをコピーすることになる。従って、１つの有効セクタが宛先ブロックに完全にコピーされる前に、マイクロプロセッサ９２は何度か状態３８６を通過することになるかもしれない。有効セクタが完全にコピーされ終わったならば、ＣＳＭ次状態ポインタはマイクロプロセッサ９２を状態３８８に指示する。
【０１４７】
状態３８８の間、セクタ番号に関わるデータの以前のバージョンがダーティとマークされていなかった場合にセクタ見出し変換テーブル９４が焦点ブロックからコピーしたばかりのセクタの新たな記憶場所を指示するように、マイクロプロセッサ９２はセクタ見出し変換テーブル９４を更新する。マークされていたならば、マイクロプロセッサ９２はコピーしたばかりのセクタのバージョンをダーティとマークする。最終的には、マイクロプロセッサ９２はそのセクタ番号に関わるセクタデータの新たなバージョンと関連する見出しの書込みを終了する。その後、マイクロプロセッサ９２は状態３８４に戻る。
【０１４８】
状態３８３に再び入ると、マイクロプロセッサ９２は焦点ブロック中のあらゆる良セクタを再配置し終わったか否かを判定する。再配置していなければ、再配置のために別の良セクタを選択し、焦点ブロック中の全ての良セクタを再配置し終わるまで、マイクロプロセッサ９２は状態３８４、３８５、３８６、３８８及び３８３を通って分岐する。それが起こったとき、ＣＳＭ次状態ポインタはマイクロプロセッサ９２を状態３９０に指示する。
【０１４９】
マイクロプロセッサ９２は、状態３９０で、焦点ブロックの消去を開始する。マイクロプロセッサ９２は、チップ対に消去指令を発し且つ消去すべきブロックを指示することにより、消去を開始する。これを実行したならば、マイクロプロセッサ９２は状態３９２へ進んで、消去が完了するのを待つ。焦点ブロックを含むチップ対が消去の完了を指示するまで、ＣＳＭは状態３９２にとどまる。
【０１５０】
焦点ブロックを消去したならば、マイクロプロセッサ９２はブロック属性データ９０を更新して、焦点ブロックに戻し、コピーする。これを実行した後、ＣＳＭ次状態ポインタによりマイクロプロセッサ９２に再び状態３８０を指示する。状態３８０に再び入ると、マイクロプロセッサ９２は、別の焦点ブロックを選択すべきか否かを判定するためにブロックカウンタを検査する。選択すべきであれば、先に説明した通りマイクロプロセッサ９２は状態３８２、３８６、３８８、３９０、３９２及び３９４を通って分岐する。そうでない場合には、マイクロプロセッサ９２はステップ３９６へ分岐して、クリーンアップを完了する。
【０１５１】
３．クリーンアップが必要であるか否かの評価
図２０は、ＦＬＡＳＨアレイ６２をクリーンアップすべきか否かを評価するために状態３８０で使用するアルゴリズムを流れ図の形で示す。このアルゴリズムを使用した場合、総ダーティメモリが総メモリ予約の設定されたパーセンテージを越えたときに、バックグラウンドクリーンアップをトリガすることになる。総メモリ予約は総空きメモリ（ＴＦＦＡ）と、総ダーティメモリ（ＴＤＦＡ）との和として定義されている。総予約に対する総ダーティメモリのパーセンテージは固体ディスク６０の性能と電力効率を左右する。
【０１５２】
マイクロプロセッサ９２は、ステップ４００で、評価が必要であるか否かを判定することにより動作を開始する。これは、以後にクリーンアップすべきブロックの数を確定するためにカウンタを検査することによって実行される。零より大きい数は、いずれも、クリーンアップが既にトリガされており、それ以上の評価は不要であることを指示する。マイクロプロセッサ９２が初めて状態３８０に入ったとき、カウンタは零より小さいので、マイクロプロセッサ９２は必然的にステップ４０２へ分岐することになる。
ステップ４０２では、マイクロプロセッサ９２はＦＬＡＳＨアレイ６２の中のダーティメモリの総量を総メモリ予約のパーセンテージとして計算する。
【０１５３】
ステップ４０４では、ステップ４０２で計算したパーセンテージをクリーンアップトリガポイントと比較する。クリーンアップトリガポイントは総メモリ予約の何らかのパーセンテージに固定されていても良いが、あるいは、ＣＰＵ５２の要求に基づいて適応変化されても良い。クリーンアップトリガポイントを適応変化させるためのアルゴリズムについては、後に詳細に説明する。総ダーティメモリがトリガポイントで等しいか又はそれを越える場合にはマイクロプロセッサ９２はステップ４０６へ分岐することによりバックグラウンドクリーンアップを起動する。これに対し、総ダーティメモリのパーセンテージがトリガポイントを越えない場合には、マイクロプロセッサ９２はステップ４０９へ分岐する。クリーンアップは不要であるので、ＣＳＭ１の状態をアイドルに設定する。状態４１０へ分岐することにより、クリーンアップを開始することなく制御をトップレベルスケジューラ１５０に戻す。
【０１５４】
ステップ４０６では、マイクロプロセッサ９２はブロックカウンタをクリーンアップすべきブロックの最大数に設定する。一実施例では、その最大数は３に設定される。これを実行したならば、マイクロプロセッサ９２はステップ４０８へ進む。
ステップ４０８では、マイクロプロセッサ９２はＣＳＭ次状態ポインタをクリーンアッププロセスにおける次の状態である状態３８２へ進める。これを実行したならば、マイクロプロセッサ９２はステップ４１０へ分岐することにより制御をトップレベルスケジューラ１５０に戻す。
【０１５５】
クリーンアップが必要であるか否かを評価するための後続する呼び出しの間に、状態３８０において、マイクロプロセッサ９２はステップ４００でブロックカウンタを検査することによって動作を開始する。ブロックカウンタが零を越えれば、クリーンアップの必要は評価されない。その代わりに、マイクロプロセッサ９２はブロックカウンタを減分し、ステップ４０１へ分岐する。
ステップ４０１では、マイクロプロセッサ９２はＣＳＭ次状態ポインタを状態３８２に指示し、クリーンアップすべきブロックを選択する。次に、マイクロプロセッサ９２は戻りステップ４１０を経て状態３８０から出る。
【０１５６】
図２１は、クリーンアップが必要であるか否かを評価するためにステップ４０４で使用されるトリガポイントを適応変化させるアルゴリズムを流れ図の形で示す。図示したアルゴリズムはセクタ１６２に属している。
ステップ４１２では、マイクロプロセッサ９２はトリガポイントが余りに低く設定されていないかどうか、即ち、ＦＬＡＳＨアレイ６２がダーティになりすぎるようにされていないかどうかを判定する。Ｍを大きな数とするとき、マイクロプロセッサ９２は、最前のＭ回の書込みの中で何回かのフォアグラウンドクリーンアップが起こったか否かを判定することによりこれを実行する。起こっていれば、マイクロプロセッサ９２はステップ４１４へ進む。起こっていなければ、マイクロプロセッサ９２はステップ４１６へ分岐する。
【０１５７】
ステップ４１４では、ＦＬＡＳＨアレイ６２がダーティになりすぎるようにされていたため、マイクロプロセッサ９２はトリガポイントを少量だけ減少させる。これは、ＦＬＡＳＨアレイ６２が将来ダーティになるのを阻止するという効果をもつ。ステップ４１４から、マイクロプロセッサ９２は制御を呼び出し側プログラムに戻す。
【０１５８】
ステップ４１６は、マイクロプロセッサ９２は、ＦＬＡＳＨアレイ６２が余りにクリーンに保持されていないかどうかを考慮する。Ｎを大きな数とするとき、マイクロプロセッサ９２は最前のＮ回の書込みの中のフォアグラウンド消去の回数を評価することによりこれを確定する。非常に長い時間にわたりフォアグラウンド消去が起こっていなければ、マイクロプロセッサ９２はステップ４１８へ分岐する。起こっていたならば、マイクロプロセッサ９２はトリガポイントを変更することなくステップ４２０へ進む。
【０１５９】
ステップ４１８では、マイクロプロセッサ９２はトリガポイントをわずかに増加させる。これにより、バックグラウンドクリーンアップをトリガする前と比べてＦＬＡＳＨアレイ６２はわずかにダーティになり、その結果、クリーンアップ効率は向上する。トリガポイントを調整したならば、ステップ４２０へ分岐することにより、マイクロプロセッサ９２は呼び出し側プログラムに制御を戻す。
【０１６０】
４．クリーンアップすべきブロックの選択
クリーンアップをトリガしたならば、状態３８２では焦点ブロックを選択する。焦点ブロックを選択するときの目標は、最も費用有効性を高くクリーンできるブロックを選択することである。費用有効性のあるクリーンアップは、電力消費が過剰になるほどＦＬＡＳＨアレイ６２をクリーンに保持することと、フォアグラウンドクリーンアップが頻繁に起こるほどＦＬＡＳＨアレイ６２をダーティに保持することである。１つのブロックがクリーンアップに関して費用有効性のある焦点であるか否かを判定するときに、いくつかの係数を考慮すべきである。第１に、そのブロックがどれほどダーティであるかということである。ブロックがダーティになるほど、そのブロックを消去する費用有効性は高い。焦点を選択する場合、決定をフォアグラウンドクリーンアップを最小限に抑える方向に向かわせるために、この係数に最も大きな重みを付ける。第２に、焦点が一部を成しているチップ対にどれほどのメモリがあるかということである。この係数は、プログラムのために消去を延期する能力をもたないＦＬＡＳＨメモリデバイスについてのみ考慮される。消去を延期する能力をもたないＦＬＡＳＨデバイスの場合、単一のブロックの消去中、そのチップ対の中のどのブロックも利用不可能である。このため、同じチップ対の中に大量の空きメモリがある場合に１つの特定のブロックをクリーンアップする所望度は低下する。第３に、焦点ブロックの中にどれほどの有効ユーザーデータ、すなわち、良データが存在しているかということである。これにより、焦点からコピーしなければならないセクタの数は増加するので、焦点として特定の１ブロックを選択する所望度も低下する。逆に言えば、コピーしなければならない良セクタが少ないほど、ブロックをクリーンアップする所望度は高くなる。焦点ブロックを選択するときには、他の係数を考慮しても良い。
【０１６１】
図２２は、先に論じた係数を使用して状態３８２でクリーンアップすべきブロックを選択するためのアルゴリズムを示す。簡単に説明すれば、ＦＬＡＳＨアレイ６２の中のブロックごとに１つのスコアを生成することにより、クリーンアップの焦点として１つのブロックを選択する。このスコアは、各々の係数を適切に重みづけし且つ重みづけした係数を加算することにより生成される。最も高い総スコアを有するブロックをクリーンアップの焦点として選択する。
【０１６２】
ステップ４４０では、全てのブロックを検査し終わったか否か、従って、焦点ブロックを選択したか否かを判定することにより、焦点ブロックの選択が始まる。マイクロプロセッサ９２は、全てのチップ対を探索したか否かを判定することによりこれを実行する。ステップ４４０を始めて通過した後、検査されたチップ対は１つではないため、マイクロプロセッサ９２はステップ４４２へ分岐する。ステップ４４４では、マイクロプロセッサ９２は選択したチップ対の中で検査すべき１つのブロックを選択する。あらゆるブロックを検査したわけではない場合には、次に、マイクロプロセッサ９２はステップ４４８へ進む。
【０１６３】
ステップ４４５では、マイクロプロセッサ９２は、ブロックが現在は別のクリーンアップ状態機械によるクリーンアップの焦点であるチップ対の一部であるか否かを判定する。これにより、クリーンアップの目標となっているチップの中の全てのブロックはいずれかの時点で長期間にわたり利用不可能となるので、現在ブロックは所望度の低い焦点ブロックになる。マイクロプロセッサ９２は、ＲＡＭに記憶されているチップとブロックの情報を検査することにより、チップが別のクリーンアップ状態機械のクリーンアップの目標となっているか否かを判定することができる。この係数に重み１を乗算してＲｕｌｅ  １を生成した後、マイクロプロセッサ９２はステップ４４６へ進む。この第１のスコアは、現在ブロック中のダーティな語の総数ＴＤＦＢC に第１の重みを乗算することにより生成される。この重みの値は後続する重みの値より相当に大きくなければならない。次に、マイクロプロセッサ９２はステップ４４６からステップ４４８へ分岐する。
【０１６４】
マイクロプロセッサ９２は、ステップ４４８で、現在ブロックに関わる第２のスコアを計算する。そこで、選択したチップ対の中の空きＦＬＡＳＨの総量ＴＦＦＣC に第２の重みを乗算する。その後、マイクロプロセッサ９２はステップ４４９へ分岐する。
第３のスコアはステップ４４９で計算される。そこで、現在ブロックが最前に消去されたチップ対の中にあるか否かによって、ブロックの所望度を評価する。その後、マイクロプロセッサ９２はステップ４５０へ分岐する。
【０１６５】
ステップ４５０では、マイクロプロセッサ９２は現在ブロックに関わる第４のスコアを計算する。マイクロプロセッサ９２は、現在ブロック中の良バイトの総数をそのブロックの中のバイトの総数から減算することにより、このスコアを計算し始める。次に、マイクロプロセッサ９２はこの数に第４の重みを乗算する。第４の重みは、焦点ブロックの選択を良さという点では劣るセクタデータを有するブロックを選択することにわずかに偏向させようとするものである。次に、マイクロプロセッサ９２はステップ４５１へ分岐する。第４の重みは第１の重みと比較して相対的に小さい。
【０１６６】
現在ブロックに関わる第５の、そして、最後のスコアはステップ４５１の間に生成される。考慮される第５の係数は選択をサイクルカウントの低いブロック向かわせ、それにより、受動摩耗均等化を行うのである。アレイ６２中の最大サイクルカウントと比較して現在ブロックのサイクルカウントが少ないほど、ブロックの所望度は高くなる。そこで、「Δサイクルカウント」により表わされるこの係数に第５の重みを乗算する。
【０１６７】
ステップ４５２では、マイクロプロセッサ９２は現在ブロックの所望の特性を反映するＲｕｌｅ  １、Ｒｕｌｅ  ４及びＲｕｌｅ  ５を加算することにより、ブロックに関わる総スコアを生成する。Ｒｕｌｅ  ０、Ｒｕｌｅ  ２及びＲｕｌｅ  ３は焦点ブロックの望ましくない特性を指示しているので、この和からそれらを減算する。
ステップ４５４へ進むと、マイクロプロセッサ９２は現在ブロックに関わる総スコアを最大総スコアと比較する。現在ブロックに関わる総スコアが最大総スコアを越えていれば、最大総スコアを上向きに改訂し、マイクロプロセッサ９２はステップ４５６へ進む。これに対し、現在ブロックに関わる総スコアが最大総スコア以下である場合には、マイクロプロセッサ９２はステップ４４４に戻る。
【０１６８】
ステップ４５６では、マイクロプロセッサ９２は現在最大総スコアを有するブロックのチップ、ブロック及びスコアを記憶する。次に、マイクロプロセッサ９２はステップ４４４に戻る。
ステップ４４４に再び入ると、マイクロプロセッサは現在選択したチップ対の中のあらゆるブロックを評価したか否かを決定する。全てのブロックを評価し終わっていなければ、選択したチップ対の中の全ブロックを評価し終わるまで、マイクロプロセッサ９２はステップ４４６、４４８、４５０、４５２、４５４、４５６及び４４４を経て分岐する。選択したチップ対の中のブロックが評価されるたびに、マイクロプロセッサ９２はステップ４４０に戻る。
ステップ４４０は、どのチップ対の中のブロックも検査されたか否かを判定する。検査されていなければ、ＦＬＡＳＨアレイ６２の中の全てのチップ対の全てのブロックを評価し終わるまで、マイクロプロセッサ９２はステップ４４２、４４４、４４６、４５０、４５２、４５４、４５６及び４４０を経て分岐する。次に、マイクロプロセッサ９２はステップ４５８へ進む。
【０１６９】
マイクロプロセッサ９２はクリーンアップの焦点として選択したチップとブロックを焦点ウィンドウに書込む。マイクロプロセッサ９２はステップ４５６で記憶したブロックとチップのアドレスを使用して、これを実行する。その後、マイクロプロセッサはステップ４６０へ進む。
現在の目標に到達したならば、ステップ４６０で、マイクロプロセッサ９２は空き物理セクタを割当てるためにＣＳＭ次状態ポインタを設定する（状態３８４）。
ステップ４６０から、マイクロプロセッサ９２はステップ４６２へ分岐することにより制御をトップレベルスケジューラ１５０に戻る。
【０１７０】
５．クリーンアップのための空き物理セクタの割当て
焦点ブロックを消去するのに先立って、焦点ブロックからユーザーデータの全ての有効セクタをコピーし、宛先ブロックへ再配置しなければならない。再配置プロセスにおける第１のステップは、焦点ブロックに現在入っているユーザーデータのセクタに対してメモリスペースを割当てることである。図２３は、クリーンアップ中、メモリの割込みを管理する状態３８４に関わるアルゴリズムを示す。
【０１７１】
マイクロプロセッサ９２は、ステップ４７２で、焦点ブロック中のあらゆる良セクタを再配置したか否かを判定することにより割当てを開始する。マイクロプロセッサ９２は、次の見出しに到達するまで焦点ブロックのＢＳＴＴ８４を走査してゆくことによってその決定を実行する。見出しの中の属性語がＦＦＦＦ（１６進数）である場合、ユーザーデータのどのセクタも焦点ブロックからコピーされ終わっている。その場合、マイクロプロセッサ９２は状態４８０へ分岐する。全ての有効セクタがコピーされたわけではない場合には、マイクロプロセッサ９２はそのセクタが有効であるか又はダーティであるかを知るために属性語を検査する。ダーティセクタはマイクロプロセッサ９２にＢＳＴＴ８４を次の見出しまで走査させる。マイクロプロセッサ９２は、セクタのサイズを確定し且つステップ４７４へ進むことにより、良セクタに応答する。
【０１７２】
ステップ４７４では、マイクロプロセッサ９２は、図１０、１１の割当てアルゴリズム又は後に説明する別のアルゴリズムを呼び出すことにより、ステップ４７２で識別したセクタに対してメモリを割当てる。
マイクロプロセッサ９２は、ステップ４７６で、ＣＳＭ次状態ポインタを状態３８５にリセットすることにより、状態３８４から出るべく準備する。すなわち、バックグラウンドクリーンアップが実行を再開するとき、焦点ブロックからセクタバッファ９８へのセクタのコピーが始まる。これを実行したならば、マイクロプロセッサ９２はステップ４７８へ分岐することにより制御をトップレベルスケジューラ１５０に戻す。
【０１７３】
焦点ブロックからあらゆる有効セクタがコピーされ終わるまで、マイクロプロセッサ９２は何度も状態４７６に戻る。全セクタをコピーしたならば、マイクロプロセッサ９２はステップ４７２からステップ４８０へ分岐する。ステップ４８０では、マイクロプロセッサ９２は、消去を開始するためにＣＳＭ次状態ポインタを適切に設定することにより、焦点ブロックの消去を開始する。制御を呼び出しプログラムに戻す。
【０１７４】
６．クリーンアップのための空き物理メモリの割当て
図２４は、クリーンアップのために空き物理メモリを割当てる別の方法を流れ図の形で示す。クリーンアップの宛先ブロックとして選択されるブロックは適切であると共に、所望のブロックでもなければならない。ブロックの適否をアクセスするときは、図１０、１１及び図１３、１４に示した割当て方法に関して先に論じたのと本質的に同じ方式を使用する。ただし、所望の宛先ブロックの評価と定義は異なる。最も所望度の高い宛先ブロックは、焦点ブロックからコピーすべきユーザーデータのセクタに最も厳密に適合するブロックである。このように宛先ブロックの所望度を定義すると、ホスト書込みのために大量の空きデータを保存することにより、ユーザーデータのコヒーレンシーは増大する。
【０１７５】
クリーンアップ中のメモリの割当ては、宛先ブロックの選択に際して使用する変数の初期設定をもって始まる。ステップ２２０２及び２２０４では、ＢｅｓｔＦｉｔ  ＢｌｏｃｋとＢｅｓｔ  Ｆｉｔ  Ｃｈｉｐを共に０に設定する。
ステップ２２０６では、マイクロプロセッサ９２は焦点ブロックの中に残っているユーザーデータのセクタを記憶するために必要な空きメモリの量を計算する。従って、一度に１つのセクタに関するメモリのみを割当てるのではあるが、焦点ブロックの中に残っているユーザーデータの全てのセクタを記憶できるブロックに関して所望度を評価することになる（ここでいう「ユーザーデータのセクタ」及び「ユーザーデータ」は空きでもなく、ダーティでもないメモリとして定義されている。）
【０１７６】
ステップ２２０７では、マイクロプロセッサ９２は、考えうる宛先ブロックの評価を開始するのに先立って、もう１つの変数を初期設定する。Ｓｃｏｒｅをいずれかのブロックにおける空きメモリの最大量を表わす最大値に設定する。評価中、所望度が最も高い宛先ブロック、すなわち、利用可能な空きメモリが必要な総空きメモリに最も近いブロックのスコアを指示するために、Ｓｃｏｒｅを改訂する。これを実行したならば、マイクロプロセッサ９２はステップ２２０８へ進む。
各ブロックの宛先ブロックとしての適否は図１３、１４に関して論じたのと同じ方式でステップ２２０８〜２２１６において評価される。従って、それらのステップについては詳細には説明しない。
【０１７７】
最終的には適切なブロックを識別し、マイクロプロセッサ９２はステップ２２１８に至る。そこで、現在ブロックの宛先ブロックとしての所望度を確定する。宛先ブロックとしての所望度を図２４のサービスに従って規定する係数が１つある。それは、現在の空きメモリの量が焦点ブロック中に残っているユーザーデータの全てのセクタを記憶するために必要とされる空きメモリの量とどれほど密接に一致するかということである。変数Ｔｏｔａｌは、焦点ブロックの中のユーザーデータを記憶した後に残っている空きメモリに関して現在ブロックの所望度を測定する。現在ブロック中の空きメモリが多すぎるか又は少なすぎるかに従って、Ｔｏｔａｌは正の数又は負の数になるであろう。次に、マイクロプロセッサ９２はステップ２２２０へ分岐する。
【０１７８】
ステップ２２２０では、マイクロプロセッサ９２は現在ブロックが最も良く適合するとして現在選択されているブロックよりも良く適合するか否かを判定する。言いかえれば、ＴｏｔａｌCurrent Block の絶対値をＳｃｏｒｅの絶対値と比較する。比較に際して絶対値を使用することにより、厳密に必要であるより空きメモリの少なすぎるブロックと、厳密に必要であるより多くの空きメモリを有するブロックの双方が確実に考慮されるのである。ＴｏｔａｌCurrent Block の絶対値がＳｃｏｒｅの絶対値より小さい場合、マイクロプロセッサ９２はステップ２２０８に戻って、別のブロックを評価する。これに対して、現在ブロックが以前のブロックより良く適合しているならば、マイクロプロセッサ９２はステップ２２２２へ分岐して、最良適合値を改訂する。
【０１７９】
ステップ２２２２では、ＳｃｏｒｅをＴｏｔａｌCurrent Block にリセットする。その後ステップ２２２４及び２２２６において、Ｂｅｓｔ  Ｆｉｔ  ＣｈｉｐとＢｅｓｔ  Ｆｉｔ  Ｂｌｏｃｋをそれらが現在ブロックを指示するように改訂する。これを実行したならば、マイクロプロセッサ９２はステップ２２０８に戻って、別のブロックを評価する。
ＦＬＡＳＨアレイ６２中の各ブロックを評価した後、マイクロプロセッサ９２はステップ２２０８からステップ２２２８へ出る。次に、マイクロプロセッサ９２は、Ｂｅｓｔ  Ｆｉｔ  Ｂｌｏｃｋに焦点ブロックから現在移動中であるデータのセクタを記憶するのに十分なメモリがあるか否かを判定する。十分なメモリがなければ、ステップ２２３０で、マイクロプロセッサ９２は現在のクリーンアップ状態機械をアイドル状態とする。十分なメモリがある場合には、マイクロプロセッサ９２はステップ２２３２へ進み、Ｂｅｓｔ  Ｆｉｔ  Ｂｌｏｃｋのメモリを実際に予約するプロセスを開始するのであるが、これは図１０、１１及び図１３、１４に関して先に説明したのと同じ方式で実行される。
【０１８０】
７．良セクタのコピー
焦点ブロックから宛先ブロックへのセクタのコピーは２つのステップから成るプロセスである。まず、焦点ブロックからセクタバッファ９８へ有効なユーザーデータの選択されたセクタをコピーする。第２に、セクタバッファ９８から宛先ブロックへ有効セクタをコピーする。この２ステッププロセスは不要なのであるが、シーケンサ１６８の経路中にある誤り検出回路の誤り検出能力を利用することによって、ユーザーデータの信頼性を改善する。
図２５のアルゴリズムは、焦点ブロックからセクタバッファ９８へのユーザーデータの１セクタのコピーを処理する。まず、ステップ４８０では、セクタをセクタバッファ９８へ移動する。第２に、マイクロプロセッサ９２はセクタの一部をコピーするように次状態ポインタを設定する。次に、ステップ４８４で、制御を呼び出し側に戻す。
【０１８１】
セクタバッファ９８の一時保護から宛先ブロックへのセクタのコピーは、Ｃｏｐｙ  Ｐａｒｔ  ｏｆ  Ｓｅｃｔｏｒと呼ばれる状態３８６で実行される。状態３８６の実行時間が選択された最大実行時間より短くなるように保証するために、状態３８６が実行されるたびに、セクタの一部のみをコピーする。一実施例では、各々の状態の最大実行時間は５００μ秒に限定されている。
【０１８２】
図２６は、セクタバッファ９８から１つのセクタの一部をコピーするためのアルゴリズムを示す。マイクロプロセッサ９２は、ステップ４９０で、セクタの残り部分を最大実行時間の中で宛先ブロックにコピーできるか否かを決定することにより動作を開始する。一実施例では、セクタバッファ９８から以後にコピーすべきバイトの数を２０と比較することにより、マイクロプロセッサ９２はこれを実行する。コピーできる語の最大数は、選択された最大実行時間によって異なる。セクタの残り部分を最大実行時間の中でコピーできないのであれば、マイクロプロセッサ９２はステップ４９２へ分岐する。
ステップ４９２では、マイクロプロセッサ９２はセクタバッファ９８からクリーンアップ状態機械の宛先ウィンドウにより指示される宛先ブロックへ２０バイトをコピーする。その後、マイクロプロセッサ９２はステップ４９４へ分岐する。
【０１８３】
ステップ４９４では、マイクロプロセッサ９２はＣＳＭ次状態ポインタを状態３８６に戻すように指示し、最終的にはセクタの全体がセクタバッファ９８からコピーされるように保証する。マイクロプロセッサ９２がステップ５００へ分岐するとき、制御はトップレベルスケジューラ１５０に戻る。
最後に状態３８６を通過すると、残っている全ての語を最大実行時間の中で宛先ブロックへコピーすることができる。この通過の間に、マイクロプロセッサ９２は状態４９０から状態４９６へ分岐する。
【０１８４】
ステップ４９６では、マイクロプロセッサ９２はセクタバッファ９８に残っている全ての語を宛先ブロックへコピーする。その後、マイクロプロセッサ９２はステップ４９８へ進む。
有効セクタの宛先ブロックへの再配置を完了したならば、マイクロプロセッサ９２はセクタの新たな物理記憶場所を反映するためにセクタ見出し変換テーブル９４を更新すべく準備する。この時点で、マイクロプロセッサ９２は新たなデータのセクタに関わる見出しの書込みをも終了する。これは、ステップ４９８で、ＣＳＭ次状態ポインタを状態３８８にリセットすることにより実行される。セクタのコピーを終了したならば、マイクロプロセッサ９２はステップ５００を経て状態３８６から出る。
【０１８５】
８．セクタをコピーした後のデータベースの更新
ユーザーデータの１セクタが焦点ブロックから宛先ブロックへ完全に再配置されるまで、ＢＳＴＴ８４とＳＨＴＴ９４の更新は遅延される。これにより、セクタが再配置中であっても、ＣＰＵ５２は常に確実にセクタの有効コピーをアクセスできるようになる。従って、セクタの移動中にＣＰＵ５２は自在にそのセクタを再書込みできる。その結果ＦＬＡＳＨアレイ６２の中に同じデータのセクタの３つ以上のバージョンが存在しうるが、その中で、有効であるのは１つのバージョンのみである。これが起こったときには、マイクロプロセッサ９２は状態３８６の間にダーティセクタを有効にコピーし終わっている。状態３８８のＰｏｓｔＣｏｐｙ  Ｄａｔａｂａｓｅ  Ｕｐｄａｔｅ（コピー後データベース更新）アルゴリズムは、どのデータベースを更新すべきか及びどのようにしてそれらのデータベースを更新すべきかを確定することにより、この問題を予想する。
【０１８６】
図２７は、状態３８８の間のデータベースの更新を示す流れ図である。マイクロプロセッサ９２は、ステップ５０２で、ＣＳＭがセクタをコピーしている間にホストがセクタを書込んだか否かを判定することにより、このタスクを開始する。マイクロプロセッサ９２は、再配置したばかりのセクタに関わる見出しがダーティとマークされたか否かを検査することにより、これを判定することができる。この見出しを見出し（ＦＯＣＵＳ）と呼ぶ。これがわかれば、マイクロプロセッサ９２はどの変換テーブルを更新すべきか及びそれらのテーブルをどのように更新すべきをか知る。それには２つの可能性がある。
【０１８７】
まず初めに、見出し（ＦＯＣＵＳ）がダーティとマークされないときの事象の列を考える。この状況においては、宛先ブロックと焦点ブロックの双方に関わるセクタ見出し変換テーブル９４及びブロックセクタ変換テーブル８４を更新しなければならない。これを実行し始めるために、マイクロプロセッサ９２はステップ５０２からステップ５０６へ分岐する。
データベースの更新は宛先ブロックと共に始まる。ステップ５０６では、マイクロプロセッサ９２はＬＳＮは宛先ブロックのＢＳＴＴ８４に書込む。その後、マイクロプロセッサ９２はステップ５０８へ分岐する。
マイクロプロセッサ９２は、ＳＨＴＴ９４の中のセクタのアドレスが焦点ブロックの見出しではなく、宛先ブロックの見出しを指示するように、そのアドレスを変更する。次に、マイクロプロセッサ９２はステップ５１０へ進む。
【０１８８】
ステップ５１０では、マイクロプロセッサ９２は３つの変換テーブル全ての更新を完了する。そこで、マイクロプロセッサ９２は焦点ブロック中の見出しをダーティとマークする。マイクロプロセッサ９２は、図１５のダーティとマークするアルゴリズムを呼び出すことにより、これを実行する。データベースの更新を完了したならば、マイクロプロセッサ９２はステップ５１２へ分岐する。
ステップ５１２に入ることは、１セクタのコピーが完了したことを指示している。マイクロプロセッサ９２は、ステップ５１２で、空き物理セクタを割当てる状態３８４にＣＳＭ次状態ポインタを設定することにより、コピーすべき別の良セクタについて焦点ブロックを走査すべき準備する。
その後、ステップ５１４へ分岐することにより、マイクロプロセッサ９２の制御はトップレベルスケジューラ１５０に戻る。
【０１８９】
セクタが宛先ブロックに再配置されている間にセクタが改訂されると何が起こるか？このセクタは既にダーティとマークされているので、見出し（ＦＯＣＵＳ）を改訂する必要はない。また、ＳＨＴＴ９４は既に改訂されたセクタと関連する見出しを指示しているので、ＳＨＴＴ９４も改訂を要求しない。焦点ブロックの見出しが無効であることを表わすために、宛先ブロックのＢＳＴＴ８４のみを改訂すれば良い。マイクロプロセッサ９２はステップ５０２からステップ５１６へ分岐することにより、このタスクを開始する。
マイクロプロセッサ９２は、図１５のダーティとマークするアルゴリズムを呼び出すことにより、ステップ５１６で宛先ブロックのＢＳＴＴ８４を更新する。先の場合と同様に、マイクロプロセッサ９２はブロック５１４へ分岐することにより制御をトップレベルスケジューラ１５０に戻す。
【０１９０】
９．焦点ブロックの消去
消去を経たダーティセクタから空きメモリへの変換は、焦点ブロックから全ての良セクタをコピーした後に始まる。焦点ブロックの消去は消去を開始することと、次に、消去が終了するのを待つこととを含む。
図２８は、状態３９０において消去を開始するためのアルゴリズムを示す。消去指令を発行するのに先立って、ステップ５２０では、マイクロプロセッサ９２はブロック属性データ９０をセクタバッファ９８にコピーすることにより、ブロック属性データ９０を保存する。
最後に、ステップ５２２では、マイクロプロセッサ９２は焦点ブロックを含むチップ対へ消去指令を発行する。その時点では、待機することを除いて何も実行することは残っていない。
マイクロプロセッサ９２は、ステップ５２４で、ＣＳＭ次状態ポインタを消去完了を待機する状態３９２に設定することにより、長期間の待機を準備する。
【０１９１】
図２９は、消去の完了を待機し且つ検出するために使用されるアルゴリズムを示す。ステップ５３０では、マイクロプロセッサ９２は、チップ対の状態レジスタに問い合わせることにより消去が依然として進行中であるか否かを判定する。状態レジスタが消去は完了していないことを指示している限り、マイクロプロセッサ９２はステップ５３２へ分岐する。そこで、マイクロプロセッサ９２は、ＣＳＭ次状態ポインタを消去完了を待機する状態３９２に設定することにより、その待機を継続すべく準備する。消去が完了したならば、マイクロプロセッサ９２は状態５３４へ分岐し、そこで、ＣＳＭ次状態ポインタを消去後更新状態３９４に設定する。
【０１９２】
１０．消去後データベース更新
焦点ブロックを消去した後、いくつかのタスクが注意を要する。それらのタスクは、図３０に示す消去後データベース更新状態３９４により管理される。
マイクロプロセッサ９２が取り組む第１のタスクは、先の消去によって起こったサイクルカウントの数の増加を反映するために、ＦＬＡＳＨアレイデータベースを更新することである。
マイクロプロセッサ９２が実行する第２のタスクは、消去中にセクタバッファ９８に記憶されていた新たなサイクルカウントをもつブロック属性データ９０を焦点ブロックに復元することである。マイクロプロセッサ９２はこれをステップ５３８で実行する。
【０１９３】
マイクロプロセッサ９２はその最後の更新タスクをステップ５４０で実行する。そこで、ブロックがクリーンアップの焦点であることを指示するために、マイクロプロセッサ９２はＲＡＭに記憶されているセマフォーをクリアする。その結果、図１２の割当てアルゴリズムは、可能であれば、先の焦点ブロックを含むチップ対に再び自在にセクタを割当てできる。
状態３９４から出る前に、マイクロプロセッサ９２はＣＳＭ次状態ポインタを状態３８０、Ｅｖａｌｕａｔｅ  ＩＦ  Ｃｌｅａｎ−Ｕｐ  ｉｓ  Ｎｅｃｅｓｓａｒｙにリセットする。
Ｂ．フォアグラウンドクリーンアップ
フォアグラウンドクリーンアップの目標は、ＦＬＡＳＨアレイ６２の中に大量の空きメモリを迅速に生成することである。フォアグラウンドクリーンアップは、２つのクリーンアップ状態機械を同時に動作させると共に、ＣＰＵ５２に空きメモリを強制的に待機させることにより、その目標を達成する。従って、フォアグラウンドクリーンアップはコンピュータのユーザーに影響を及ぼすことによりバックグラウンドクリーンアップとは異なる。フォアグラウンドクリーンアップは、バックグラウンドクリーンアップと比較してトリガされる方式についても異なっている。活動状態であるとき、バックグラウンドクリーンアップは、ＣＰＵ５２が１つのセクタを書込むたびに、それに続いて開始される。空き物理メモリの割当て中、フォアグラウンドクリーンアップはトリガされる。１つのセクタを書込むのに十分な空きＦＬＡＳＨメモリを割当てることができない場合、条件調整までマルチＣＳＭ実行３４８への呼び出しがフォアグラウンドクリーンアップを実行する。加えて、フォアグラウンドクリーンアップはクリーンアップが必要であるか否かの前述の評価によってバックグラウンドクリーンアップとは異なり、その決定は空きメモリの割当て中に有効に実行される。従って、フォアグラウンドクリーンアップは、クリーンアップすべきブロックを選択することにより開始する。
【０１９４】
図３１は、フォアグラウンドクリーンアップを管理するために使用されるアルゴリズム、条件調整までマルチＣＳＭ実行３４８を示す。このアルゴリズムを使用すると、第１のクリーンアップ状態機械が起動され、消去完了待機状態３９２に到達するまで連続して動作することができる。その時点で、第２のクリーンアップ状態機械が動作され、消去完了待機状態３９２に到達するまで連続して動作することができる。そこで、第１のクリーンアップ状態機械は中断なく焦点ブロックのクリーンアップを完了する。１つのブロックがクリーンになり且つ別のブロックを間もなくクリーンにすべき場合、マイクロプロセッサ９２はＣＰＵ５２からの指令に再び応答する。
【０１９５】
フォアグラウンドクリーンアップはステップ５５０で始まり、そこでは、マイクロプロセッサ９２は第１のクリーンアップ状態機械と、第２のクリーンアップ状態機械の双方について１のブロックカウントに設定する。先の図１９の説明からわかる通り、ブロックカウントはどれほどの数のブロックをクリーンアップするか、従って、クリーンアップがどれほど長く続くかを確定する。双方のブロックカウントを１に設定することにより、フォアグラウンドクリーンアップの実行時間は最短に抑えられる。次に、マイクロプロセッサはステップ５５２へ進む。
【０１９６】
ステップ５５２と共に、マイクロプロセッサ９２は双方のクリーンアップ状態機械を起動するプロセスを開始し、これはステップ５６２まで続く。マイクロプロセッサ９２は、第１のクリーンアップ状態機械ＣＳＭ１の状態を検査することにより、ステップ５５２で、ＣＳＭ１が活動状態であるか否かを判定する。ＣＳＭ１が活動状態でなければ、マイクロプロセッサ９２は状態５５４へ分岐して、ＣＳＭ１を起動する。これに対し、ＣＳＭ１が既に活動状態である場合には、マイクロプロセッサ９２はステップ５５８へ分岐して、第２のクリーンアップ状態機械ＣＳＭ２を起動する。
ステップ５５４では、マイクロプロセッサ９２はＣＳＭ１の状態をアイドルから活動へ変化させる。マイクロプロセッサ９２はステップ５５４から５５６へ進む。
【０１９７】
マイクロプロセッサ９２は、ＣＳＭ１の次状態ポインタをクリーンアップすべきブロックを選択する状態３８２に設定することにより、ＣＳＭ１にクリーンアップを開始させるべく準備する。これを実行したならば、マイクロプロセッサ９２はステップ５５８へ分岐することにより、その注意をＣＳＭ２へ向ける。
ステップ５５８では、マイクロプロセッサ９２はＣＳＭ２が活動状態であるか否かを判定する。活動状態であれば、マイクロプロセッサ９２はステップ５６４へ進み、ＣＳＭ１をランさせ始める。そうでない場合には、マイクロプロセッサ９２はステップ５６０へ分岐する。
ステップ５６０では、マイクロプロセッサ９２はＣＳＭ２を活動状態に設定する。その後、ステップ５６２で、マイクロプロセッサ９２は、ＣＳＭ２の次状態ポインタをクリーンアップすべきブロックを選択する状態３８２に設定することにより、ＣＳＭ２にクリーンアップを開始させるべき準備する。
【０１９８】
２つのクリーンアップ状態機械のセットアップが完了したとき、マイクロプロセッサ９２は最終的には一方を始動することができる。ステップ５６４では、マイクロプロセッサ９４はどちらのクリーンアップ状態機械に実行時間を与えるべきかを判定する。マイクロプロセッサ９２は、ＣＳＭ１がブロックの消去を開始したか否かを判定することによりこれを実行する。ＣＳＭ１が消去を開始していなければ、マイクロプロセッサ９２はステップ５６６へ進む。
ステップ５６６では、マイクロプロセッサ９２はＣＳＭ１の１つの状態を実行する。マイクロプロセッサは、消去完了待機状態３９２までのＣＳＭ１の状態を実行する。マイクロプロセッサ９２はステップ５６６及び５６４を繰り返しループしてゆくことにより状態３９２に到達する。ＣＳＭ１が消去完了待機状態３９２に到達すると、マイクロプロセッサ９２は状態５６８へ分岐することにより、より効果の多い分野に注意を集中する。
【０１９９】
マイクロプロセッサ９２は、ステップ５６８で、ＣＳＭ２がその焦点ブロックのクリーンアップを終了するのにさらに実行時間を要求するか否かを判定する。要求するならば、マイクロプロセッサ９２はステップ５７０へ分岐し、そこで、ＣＳＭ２の単一の状態を実行する。マイクロプロセッサは、消去完了待機状態３９２までのＣＳＭ２の状態を実行する。この時点で、マイクロプロセッサはステップ５７０からステップ５７２へ分岐することにより、再びＣＳＭ１に注意を集中する。
ステップ５７２では、ＣＳＭ１がその焦点ブロックのクリーンアップを完了したか否かを判定する。マイクロプロセッサ９２は、ＣＳＭ１と関連する状態語を検査することによりこれを実行する。ＣＳＭ１がアイドル状態でない場合、マイクロプロセッサ９２はステップ５７４へ分岐して、別のＣＳＭ１状態を実行する。ステップ５７２とステップ５７４の間を往復することにより、マイクロプロセッサ９２はＣＳＭ１により管理されるクリーンアップを最終的に完了する。この時点で、１つのブロックは完全にクリーンアップされ終わっており、別のブロックが間もなくクリーンアップされることになる。既に大量の空きメモリの予約があるので、マイクロプロセッサ９２はステップ５７６へ分岐することにより制御をトップレベルスケジューラ１５０に戻す。これにより、フォアグラウンドクリーンアップは終わる。
【０２００】
Ｃ．強制クリーンアップ
強制クリーンアップは、クリーンアップ状態機械を起動し且つ制御するさらに別の方法である。強制クリーンアップは、コンピュータのユーザーからの指令により開始されるという点で、フォアグラウンドクリーンアップ及びバックグラウンドクリーンアップの双方とは異なっている。この種のクリーンアップでは、ユーザーは状態３８０におけるように空きメモリの総量を評価することなくクリーンアップが必要であると決定する。
固体ディスク制御装置６４は２種類の強制クリーンアップを認識する。一方の型の強制クリーンアップは一方のクリーンアップ状態機械のみを起動する。この型のクリーンアップはＦｏｒｃｅ  Ｃｌｅａｎｕｐ（強制クリーンアップ）と名付けられたサービス３４２により管理される。他方の型のクリーンアップは２つのクリーンアップ状態機械を起動し、ＦｏｒｃｅＭｕｌｔｉ  Ｃｌｅａｎｕｐ（強制マルチクリーンアップ）と呼ばれるサービス３４４により管理される。
【０２０１】
図３２は、強制クリーンアップ３４２のアルゴリズムを示す。強制クリーンアップのタスクは相対的に単純である。すなわち、必要に応じて、ＣＳＭ１を起動し且つ始動するのである。
ステップ５８０では、ＣＳＭ１が活動状態であるか否かを知るためにＣＳＭ１の状態を検査することにより、マイクロプロセッサ９２はそのタスクを開始する。活動状態であれば、マイクロプロセッサ９２はステップ５８６へ分岐する。ＣＳＭ１がアイドル状態である場合には、マイクロプロセッサ９２はステップ５８７へ分岐する。
ステップ５８２では、マイクロプロセッサ９２は、ＣＳＭ１の状態を活動に変化させることによりＣＳＭ１をイネーブルする。次に、クリーンアップが必要であるか否かを評価する状態３８０をバイパスし且つＣＳＭ１の次状態ポインタをクリーンアップすべきブロックを選択する状態３８２に設定することにより、マイクロプロセッサ９２は強制的にクリーンアップを開始させる。それが確実に実行されたならば、マイクロプロセッサ９２はステップ５８４からステップ５８６へ分岐する。
【０２０２】
ステップ５８７では、ＣＳＭ１が既にクリーンアップを開始していなかった場合に、マイクロプロセッサ９２はＣＳＭ１に確実にクリーンアップを開始させる。マイクロプロセッサ９２は、ＣＳＭ１の次状態ポインタを検査し、それがクリーンアップは必要であると評価するのに等しい場合にはステップ５８４へ分岐することにより、これを実行する。これは、クリーンアップが不要であるという評価を全て回避する。
【０２０３】
図３３は、強制マルチクリーンアップ３４４のアルゴリズムを示す。このアルゴリズムのタスクは、必要に応じて双方のクリーンアップ状態機械を起動することである。
強制マルチクリーンアップ３４４の初めと２つのステップは、強制クリーンアップ３４２のステップと全く同じである。ステップ５９０では、マイクロプロセッサ９２はＣＳＭ１が活動状態であるか否かを判定する。活動状態でなければ、ステップ５９２でＣＳＭ１をイネーブルし、ＣＳＭ１の次の状態としてコピーすべきブロックを選択する状態３８２を選択する。これに対し、ＣＳＭ１が既に活動状態である場合には、マイクロプロセッサ９２はステップ５９１へ分岐する。
【０２０４】
ステップ５９１では、マイクロプロセッサ９２はＣＳＭ１がクリーンアップを開始したか否かを判定する。先に説明した通り、ＣＳＭ１を起動するたびにブロックのクリーンアップが開始されるわけではない。次状態ポインタがクリーンアップは必要であるか否かを評価する状態以外の状態を指示する場合、クリーンアップは始まっている。この場合、マイクロプロセッサ９２はステップ５９４へ直接に分岐する。そうでない場合、マイクロプロセッサ９２はステップ５９２へ進む。
マイクロプロセッサ９２は、そこで、ＣＳＭ１の次状態ポインタをクリーンアップすべきブロックを選択する状態にリセットすることにより、ＣＳＭ１に強制的に１つのブロックをクリーンアップさせる。その後、ステップ５９２からステップ５９４への分岐により注意はＣＳＭ２に向かう。
【０２０５】
ステップ５９４では、マイクロプロセッサ９２は第２のクリーンアップ状態機械ＣＳＭ２をイネーブルする。次に、マイクロプロセッサ９２はクリーンアップが必要であるか否かを評価する状態３８０をバイパスし、ＣＳＭ２の次状態ポインタをコピーすべきブロックを選択する状態３８２に設定する。マイクロプロセッサ９２はステップ５９４からステップ５９６へ分岐して、制御をトップレベルスケジューラ１５０に戻す。
【０２０６】
IV．まとめ
固体メモリディスクをクリーンアップする方法を説明した。クリーンアップは、クリーンアップのための焦点ブロックを選択することによって始まる。ユーザーデータのセクタを保存するために、ユーザーデータのセクタを焦点ブロックから宛先ブロックにコピーする。焦点ブロックから全ての有効なユーザーデータをコピーし終わった後、固体ディスク制御装置は焦点ブロックを消去する。
以上の明細書の中では、本発明をその特定の実施例を参照して説明した。しかしながら、特許請求の範囲に記載したようなより広い本発明の趣旨から逸脱せずに様々な変形及び変更を実施しうることは明白であろう。従って、明細書と図面は限定的な意味ではなく、単なる例としてみなされるべきである。
【図面の簡単な説明】
【図１】固体メモリディスクを含むパーソナルコンピュータのブロック線図。
【図２】固体メモリディスクのブロック線図。
【図３】ブロックファイル構造のブロック線図。
【図４】セクタ見出し変換テーブルの第１の実施例のブロック線図。
【図５】パワーアップ時にセクタ見出し変換テーブルを作成するためのアルゴリズムの流れ図。
【図６】固体ディスク制御装置のアルゴリズムのオブジェクト図。
【図７】ディスク読取りの流れ図。
【図８】ブロックセクタ変換テーブルを使用してデータの１セクタをシークするための流れ図。
【図９】１セクタを書込むための流れ図。
【図１０】ＦＬＡＳＨアレイ中でメモリスペースを割当てる第１の方法の流れ図。
【図１１】ＦＬＡＳＨアレイ中でメモリスペースを割当てる第１の方法の流れ図。
【図１２】ブロックチェーンの図。
【図１３】書込み指令に応答してメモリスペースを割当てる方法の流れ図。
【図１４】書込み指令に応答してメモリスペースを割当てる方法の流れ図。
【図１５】ダーティとマークするアルゴリズムの流れ図。
【図１６】クリーンアップ中の様々なサービスのブロック線図。
【図１７】クリーンアップ状態機械をイネーブルするための流れ図。
【図１８】クリーンアップ状態機械の１つの状態を実行するための流れ図。
【図１９】クリーンアップ状態機械の状態の流れ図。
【図２０】クリーンアップをトリガすべきか否かを評価するためのアルゴリズムの流れ図。
【図２１】クリーンアップを適応トリガするためのアルゴリズムの流れ図。
【図２２】クリーンアップすべきブロックを選択するためのアルゴリズムの流れ図。
【図２３】クリーンアップのためにメモリを割当てのための流れ図。
【図２４】クリーンアップのための空き物理メモリを割当てる方法の流れ図。
【図２５】セクタバッファに１セクタをコピーするための流れ図。
【図２６】セクタバッファから宛先ブロックへ１セクタの一部をコピーするための流れ図。
【図２７】１セクタをコピーした後にデータベースを更新するための流れ図。
【図２８】ブロックの消去を開始するための流れ図。
【図２９】ブロックの消去が完了したか否かを判定するための流れ図。
【図３０】ブロック消去後にデータベースを更新するための流れ図。
【図３１】フォアグラウンドクリーンアップに関わる流れ図。
【図３２】強制クリーンアップに関わる流れ図。
【図３３】クリーンアップを強制する別の方法の流れ図。
【符号の説明】
５０  パーソナルコンピュータ
５２  中央処理装置
５４  モニタ
５６  キーボード
５８  マウス
６０  固体ディスク
６２  ＦＬＡＳＨアレイ
６４  固体ディスク制御装置
６６  チップ対
６８  上位チップ
７０  下位チップ
８０ａ、８０ｂ  ブロック
８４  ＢＳＴＴ
８５  見出し
８６  データスペース
９０  ブロック属性データ
９２  マイクロプロセッサ
９３  データベース
９４  ＳＨＴＴ
９５  ＦＬＡＳＨメモリ
９６  ウィンドウＡＳＩＣ
９８  セクタバッファ
１００  電荷ポンプ
１５０  トップレベルスケジューラ
１５２  ホストインタフェース
１５４  ＦＬＡＳＨ媒体
１５６  ホストインタフェース
１５８  セクタバッファ
１６０  ディスク
１６２  セクタ
１６７  ＦＬＡＳＨアレイインタフェース
【図１】
0003672331.tif 000002
【図２】
0003672331.tif 000003
【図３】
0003672331.tif 000004
【図４】
0003672331.tif 000005
【図５】
0003672331.tif 000006
【図６】
0003672331.tif 000007
【図７】
0003672331.tif 000008
【図８】
0003672331.tif 000009
【図９】
0003672331.tif 000010
【図１０】
0003672331.tif 000011
【図１１】
0003672331.tif 000012
【図１２】
0003672331.tif 000013
【図１３】
0003672331.tif 000014
【図１４】
0003672331.tif 000015
【図１５】
0003672331.tif 000016
【図１６】
0003672331.tif 000017
【図１７】
0003672331.tif 000018
【図１８】
0003672331.tif 000019
【図１９】
0003672331.tif 000020
【図２０】
0003672331.tif 000021
【図２１】
0003672331.tif 000022
【図２２】
0003672331.tif 000023
【図２３】
0003672331.tif 000024
【図２４】
0003672331.tif 000025
【図２５】
0003672331.tif 000026
【図２６】
0003672331.tif 000027
【図２７】
0003672331.tif 000028
【図２８】
0003672331.tif 000029
【図２９】
0003672331.tif 000030
【図３０】
0003672331.tif 000031
【図３１】
0003672331.tif 000032
【図３２】
0003672331.tif 000033
【図３３】
0003672331.tif 000034