1

次のノードへの参照をテーブルに格納する代わりに、従来のリンク リストのように、つまり次のポインタを使用して格納できないのはなぜでしょうか?

4

3 に答える 3

3

これはアライメントによるものです。FAT (およびその他のほぼすべてのファイル システム) は、基になるストレージの 1 つまたは複数のセクター全体にファイル データを格納します。基礎となるストレージはセクター全体の読み取りと書き込みしかできないため、このような割り当てにより、ファイルの内容への効率的なアクセスが可能になります。

インターリーブの問題

プログラムがファイルに何かを保存したい場合、保存するデータが 1MB などのバッファーを提供します。ファイルのデータ セクタが次のセクタへのポインタも保持nextする必要がある場合は、このポインタ情報を実際のユーザー データとインターリーブする必要があります。そのため、ファイル システムは別のバッファ (提供された 1MB よりもわずかに大きい) を構築する必要があります。出力セクタごとに、ユーザー データの一部と対応するnextポインタをコピーし、この新しいバッファをストレージに提供します。これはやや非効率的です。ファイル システムがファイル データを常に新しいセクタに格納しない限り (ほとんどの場合は格納しない)、これらのnextポインタの書き換えも冗長になります。

より大きな問題は、ファイルに対して読み取り操作が試行された場合です。ファイルはテープ デバイスのように機能します。ファイルのプライマリ メタデータで最初のセクターの場所のみが知られているため、セクター 1000 に到達するために、ファイル システムはそれより前のすべてのセクターを順番に読み取る必要があります。セクター 0 を読み取り、セクター 0 を見つけます。ロードされたセクタ 1 のアドレスnextポインタ、セクタ 1 の読み取りなど。通常のシーク時間はランダム I/O あたり約 10 ミリ秒 (ハードディスク ドライブを想定) であり、セクタ 1000 に到達するには約 10 秒かかります。セクターが順番に並べられていても、ファイル システム ドライバーがセクター N のデータを処理している間、ディスク ヘッドは次のセクターを飛んでおり、セクター N+1 の読み取りが発行されたときには手遅れになる可能性があり、ディスク全体を回転させる必要があります。次のセクターを再度読み取ることができるようになる前に、1 回転 (7200 RPM ドライブの場合は 8.3ms) します。ただし、オンディスクキャッシュはこれに役立ちます。

単一のセクターの書き込みは、通常、アトミック操作です (ハードウェアに依存します)。停電後にセクターを読み取ると、古い内容または中間状態のない新しい内容が返されます。通常、データベース アプリケーションは、どの書き込みがアトミックかを知る必要があります。ファイル システムがファイル データとメタデータを同じセクターにインターリーブする場合、実際のセクター サイズよりも小さいサイズをアプリケーションに報告する必要があります。たとえば、512 バイトと言う代わりに 504 を報告する必要があるかもしれません。しかし、セクター サイズは通常、アプリケーションによって 2 のべき乗であると想定されるため、報告することはできません。報告されたセクター サイズが異なるファイル システム。

より良いアプローチ

nextすべてのポインターが隣接するセクターに格納されるため、FAT 形式の方が適しています。FAT12、FAT16、およびそれほど大きくない FAT32 ボリュームの場合、テーブル全体がメモリに収まるほど小さいです。FAT は依然としてファイルのブロックをリンク リストに記録するため、効率的なランダム アクセスを行うには、実装でファイルごとにチェーンをキャッシュする必要があります。十分な大きさのボリューム (十分な大きさのファイルを扱うことができる) では、そのようなキャッシュはもはやメモリに収まらない可能性があります。

ext3は直接ブロックと間接ブロックを使用します。この単純な形式は、FAT が必要とする前処理の必要性を回避し、間接ブロックが必要な場合に I/O ごとの追加読み取りの量を最小限に抑えます。これらの追加の読み取りはオペレーティング システムによってキャッシュされるため、多くの場合、オーバーヘッドは無視できます。

他のバリアントも可能であり、さまざまなファイル システムで使用されます。

ランダムノート

完全を期すために、一部のハードディスク ドライブは、ファイル システムが 512 バイトのファイル データと数バイトのメタデータを同じセクターにパックできるように、わずかに大きいセクター サイズ (たとえば 520 バイト) でフォーマットできます。しかし、上記の理由から、ファイルの次のセクターのアドレスを格納するためにそのような形式を使用した人はいないと思います。これらの追加のバイトをより有効に活用できます。追加のチェックサムとタイムスタンプが思い浮かびます。タイムスタンプは、一部の RAID システムのパフォーマンスを向上させるために使用されていると思います。それでもそのような使用法はまれであり、ほとんどのソフトウェアはそれらとまったく連携できません。

一部のファイル システムでは、個別のセクターを占有することなく、十分に小さいファイルのコンテンツをファイル メタデータに直接保存できます。ReiserFSには物議を醸すテール パッキングがあります。これはここでは重要ではありません。大きなファイルでも、ストレージ セクターへの適切なマッピングが有効です。

于 2014-03-15T14:05:36.163 に答える
0

最新の OS では、ファイル システムの次のデータ ブロックへのポインタ以上のものを必要とします: 属性 (暗号化、圧縮、非表示など)、セキュリティ記述子 (ACL リスト項目)、さまざまなハードウェアのサポート、バッファリング。これは、優れたファイル システムが行う機能のごく一部にすぎません。

ウィキペディアでファイル システムを見て、最新のファイル システムが他に何をしているのかを確認してください。

于 2014-03-15T10:07:42.520 に答える