フラッシュファイルシステムの基礎と最適化技術

ガーベジコレクション

ガーベジコレクションは文字通りゴミ集めということです。
フラッシュファイルシステムでのゴミとは、更新された元の領域のことです。
つまり、フラッシュファイルシステムでは、データをオーバライトして更新することができないので、別の場所に更新したデータを書き込むことによって更新処理を行います。
このときに元のデータは必要でなくなるのでゴミとなります。
ゴミを放置すると、フラッシュメモリに空がなくなり、データを書き込めなくなるために、状況に応じてガーベジコレクションを行う必要があります。

ガーベジコレクションには「スペアブロック」というものが必要になります。
スペアブロックはイレーズブロックのうちデータを書き込まないもので、ガーベジコレクションのために使用する特別なイレーズブロックです。
スペアブロックは論理ブロック番号を持ちません。

先ほどの “test.dat” を書き込んだ場合の図において、ファイル “test.dat” のデータが更新されたとすると、MS-FFSでは新規にFileInfo, Extentを割り付けます。
そして、旧FileInfoから新FileInfoにSecondaryPtrを使用してリンクを張ります。

このようにすることによってデータの更新を行います。
SecondaryPtrは構造体が更新された時に更新後の構造体へのリンクを張るときに使用するポインタです。
このとき、旧Extentは不要になります。不要になった構造体はマークされます。マークはASのStatusに設定されます。

その様子を下図に示します。
ファイルのデータが更新されるたびに、同様の操作がおこなわれます。

このようにして、データの更新ごとにフラッシュメモリ上にゴミがたまっていきます。
データの更新だけでなく、ファイルやディレクトリの削除によってもゴミは発生します。

たとえば、”test.dat” が削除されたとすると、FileEntry, FileInfo, Extentは不要になります。
不要になった構造体はマークされます。

このゴミを消去してデータを書き込めるようにするためにガーベジコレクションを行います。

次に、ガーベジコレクションの方法について説明します。

ガーベジコレクションの基本的な操作は、

1. スペアブロックを用意する。
2. イレーズブロックから有効なデータだけをスペアブロックにコピーする。
3. 元のイレーズブロックを消去してスペアブロックとする。
4. 元のスペアブロックに元の論理ブロック番号を設定し元のイレーズブロックにする。

となっています。

注意が必要なのは、スペアブロックが元の論理ブロックになり、論理ブロックがスペアブロックになるということです。
物理的に位置の違うスペアブロックが論理ブロックになれるのは、BASに論理ブロック番号を持っているからです。
これによって、物理的にどこに存在していても、論理ブロック番号によってポインタの一貫性がたもたれるようになっています。

MS-FFSの場合、ASのStatusにその要素が管理している領域の状態が格納されているので、この状態を見ることによって、無効なデータ領域かどうか判断がつきます。
この Statusの情報を利用して、ガーベジコレクションを行います。
さらに、MS-FFSではイレーズブロックの断片化を避けるために、イレーズブロックからスペアブロックにコピーする際に、イレーズブロックの先頭からつめてコピーしていきます。
そして、ASも同時にスペアブロックにコピーします。
この時Offsetの値はスペアブロック上での新しいオフセット値を設定することになります。

先ほどの図の状態からスペアブロックに有効なデータをコピーすると下図のようになります。

ただし、ASはコピーの際に前につめられません。そのままの位置を保ちます。
これは、ポインタにインデックス情報が格納されているからです。
インデックスがずれてしまうと正しくリンクをたどることができなくなるかです。
また、イレーズブロックのサイズがすべて同じでなければならないと言った理由もここにあります。

つまり、ガーベジコレクションは有効なデータをスペアブロックににコピーしてスペアブロックを元の論理ブロックとするため、もしイレーズブロックのサイズが違っていたら論理ブロックの入れ替えができなくなるのです。

次にガーベジコレクションの起動方式について説明します。
ガーベジコレクションの起動方式にはフォアグラウンドとバックグラウンドがあります。
特徴としては次のようになります。

• フォアグラウンド
  • オンデマンド方式とも呼ばれ、データをイレーズブロックに書き込んでいき、データの書込みに十分なサイズの空領域がなくなった時点で、データの書込みを一時中断して、ガーベジコレクションを起動する。
    そして、空領域を作成し、中断していたデータの書込みを再開する方式である。
  • この方式の特徴は、必要になるまでガーベジコレクションを実行しないので、 CPUに負担をかけないことである。
  • しかし、データの書込み最中にガーベジコレクションが起動されることもありうるので、データ書込みのパフォーマンスを見積もることが難しい。
• バックグラウンド
  • この方式のガーベジコレクションは、フラッシュファイルシステムがイレーズブロックの汚れ具合を判断し、必要に応じてガーベジコレクションを自動的に起動する。
    このようにして、常にイレーズブロックに空領域がある状態にしておく方式である。
    この方式では、ある基準にしたがって自動的にガーベジコレクションを起動するので、CPUに負荷をかけてしまうことになる。
    そのためシステム内の他の処理部分との調整が必要になる。
  • また、ガーベジコレクションの対象となるブロックの選択基準などの条件が、 フラッシュメモリの実際の状態と合っていないと、無用なブロック消去を発生させてしまうこともある。

ガーベジコレクションはシステムのパフォーマンスに影響をあたえる処理なので、起動方式、消去ブロックの選択条件などに注意する必要があります。

次ページ：消去回数の平均化

ページ: 1 2 3 4 5 6