空き領域の管理の仕組み

質問

linuxのファイルシステム(ext2/3)がどのようにHDDの開き領域を管理しているかに興味があります。
ファイルの削除によってできた断片的なパーティション上の空き空間をどのように管理し、そして新しいファイルのために割り当てているのでしょうか？

XFSはB+木を用いているとのことですが、具体的な実装について書かれている記事を見つけられません。例えば何をkeyとして・何をdataとして空き領域を探索しているのでしょうか？

ext2/3, xfs, fat等ファイルシステムは問いません。
具体的な仕組みをご存知の方、またそのような解説サイトをご存知の方、アドバイスをお願いします。

回答No.3

tropic_snow

ext2はビットマップで管理していると思っていいんじゃないでしょうか。

参考URL：

http://www.atmarkit.co.jp/flinux/rensai/fs02/fs02b.html

回答No.2

Tacosan

使っているかどうかを, ビットマップで持つというファイルシステムはあるはずです.
つまり, あるクラスタを使っていれば 1, 使っていなければ 0 とすることで, 「そのクラスタを今使っているかどうか」が簡単にわかる, ってしくみです.

お礼

ビットマップとなると、ある程度の大きさを１つのブロックとして扱い、容量分のビットマップ領域をあらかじめ用意しておくというイメージでしょうか。

こちらの方法であれば断片的な空き空間がつながった場合に認識しやすそうですね（隣り合うビットが連続して00となるだけなので）

ご回答ありがとうございます。

回答No.1

gyrocompas

Ｕｎｉｘ全般としては、
「Ｕｎｉｘシステムプログラミング」羽山博著（オーム社）
の第３章ファイルシステムに、わかりやすく解説されております。

Ｕｎｉｘファイルシステム理解のためのキーワードは
「ｉノード」ですな。

ext2/3も上記方式をモディファイしたものでしょう。
この書物は、今後Ｕｎｉｘとつきあうなら、
所有しておいても損はないと思います。
（ひょっとして、改訂版が出ているかも）

ｆａｔについては
「実用マクロアセンブラ」河西朝雄著（技術評論社）
第７章テクニカル情報にあります。

お礼

ご回答ありがとうございます。
紹介して頂いた著書をさっそく調べてみようと思います。

ところで、質問の投稿後にメモリの空き領域について検索していたら，
http://www.ylw.mmtr.or.jp/~trustno1/legos/legos_4.html
という記事を見つけました。

空き領域自体をリスト構造でつなげるといったアイデアのようです。
（次の空き領域の位置情報を、その空き領域自体に持たせる）
ファイルシステムも同じ方法を取っているかどうかはわかりませんが、思いもしない方法で思わず感心してしまいました。