1.概念
file system structrue
主要包括以下
file
邏輯的儲存單位
file system
儲存單位是block
使用不同的資料結構來表達檔案
ex:FAT32,NTFS,ext2,ext3, ISO9660,googleFS, oracle ASM,ZFS
FCB(file control block)
記錄檔案的資訊
…
file system layer
layer2(user space)
application programs
layer1(kernel space)
logical file system:
管理metadata information,FCB maintain
diretory structure和protection
file-organization module
管理free space,disk allocation
轉換logical block address到physical block address
basic file system:
負責scheduling,disk caching,buffering,
buffers應用在資料傳輸,caches應用在資料的使用
控制device的標準命令,ex:retrieve block 123
I/O control:
負責device driver,interrupt handler, 管理I/O devices
執行low-level I/O命令,ex:read drive1, cylinder 72,track 2, sector 10
layer0
devices
……
2.常見file system structures
disk file system structures
主要由以下構成
boot control block :
包含開機資訊
partition(volume) control block/super block
包含volume細節,像是blocks數量,大小和free-block和free-fcb的計算
directory structure
用來organzie files,包括file names,並關聯到FCB
file control block
data block
block一般是512byte
file control block
一般會包含以下資訊
file permissions
file dates ex:create,access,write
file owner,group, ACL
file size
file data blocks
……
memory file system structures
主要用於提昇performance
通常由以下構成
in-memory mount table
包括每一個已掛載的volumen資訊
in-memory directory-structure cache
用於讀取,保存最近在存取的directories
system-wide open-file table
用於寫入,包含所有已開啟檔案的一份FCB副本
per-process open-file table
用於寫入,負責儲存指標
buffers
用於讀取或寫入file system block
…
virtual file systems
允許不同的system call介面(API)用在不同類型的file system
結構主要如下
layer2 (user space)
file system interface
layer1 (kernel space)
VFS interface
file system:包含各種file system
storage:包括disk, network disk,…等
………………………………………………………………………………………….
3.directory implementation
directory-file結構
大致如下
0_empty, filename_a, pointer to FCB1
1_used, filename_b, pointer to FCB2
2_used, filename_c, pointer to FCB3
…omit…
directory implementation兩大做法
linear list
目錄管理方便
實作容易
search速度慢
hash table
以key做檔名
search速度快
可能發生collisions(碰撞問題)
hash table大小固定，變大時要另外做rehashing處理
…………………………………………………………………………
4.allocation methods
空間分配,也稱disk blocks
主要有三大方法
contiguous allocation(連續式空間分配)
linked allocation
indexed allocation
…
contiguous allocation
每個檔案都會佔用一組disk上的連續空間
優點
存取速度快 , support random access
缺點
會有external fragmentation,要另外花時間compacts(重新聚集)以空出可使用的連續空間
建立檔案時要判斷需要保留多少空間，太小無法擴充，太大浪費空間
logical address為1024
ex:IBM的VM/CMS
contiguous allocation directory結構
大致如下
file1, start 0, length 4
file2, start 6, length 2
…omit…
….
linked allocation
每個檔案都是disk上的linked list, 靠指標來串接
優點
無external fragmentaion
建立檔案時不用煩腦要保留多少空間的問題，空間效率好
缺點
指標移動時，若距離過遠，讀寫頭移動較頻繁，讀取會較浪費時間
not support random access
reliability low: 若其中一個指標消失，整個linked會斷掉，除非用double linked list解決
指標會佔用到空間
logical address為1020,因為要保留4個byte做指標
linked allocation directory結構
大致如下
file, start, end
file1, start 2, end 10 //根據block2尋找下一個blcok
…omit…
ps:
linked資訊儲存在block
每個block會根據linked資訊找到下一個block位置
大致如下
block2:16
block16:1
block1:10
block10:-1
FAT(file allocation table)
based on linkd allocation
keep 2 fat on disk,一個是原本的linked allocation directory,另一個記錄block的linked資訊
優點
support random access
improve reliability:
應用在微軟的file system,像是FAT12,16,32
數字表示table可支援的項目數量
ex:FAT32=8kb*2^32=33tb
…
indexed allocation
把所有指標集中起來放在index block
index block可以快取方式存在memory,但資料區段仍然散佈在disk的各地方
優點
支援random access
無external fragentation
缺點
但要另外準備空間存index table，比linked allocation還要多
會有index block不夠的問題
logical address為1024
indexed allocation directory結構
大致如下
file , index block
paper, 19 //在第19個block會記載所有該檔案的block
…omit…
file size of unbounded length
解決一個檔案一個index block不夠的問題
主要有三種方式
linked scheme
multi-level index: ex:two-level index
combined scheme ex: UNIX i-node
multi-level index
若使用4kb的block,可以儲存1024個4byte指標
若是two-level index，則可以儲存1024^2個4byte指標
combined scheme
使用15個index如下
direct blocks(直接區段)：使用12個index
記載該檔案的block
若一個block為4kb,那就有48kb的資料可直接存取
inderect block(間接區段)
記載檔案block的位置,並分為以下
single indirect block(單層間接區段)：使用1個index
double indirect block(雙層間接區段)：使用1個index
triple indirect block(三層間接區段)：使用1個index
…………………………………………………………………………………..
5.其他補充
…………………………………………
free-space management
主要使用方法有
bit/vector
linked free space list
bit vector/bit map
效率高,但要額外佔主記憶體空間
用來表示block為free或occupied
主要放入memory並在關機時寫入disk保存
ex:
bit map大小?
block size=2^12 bytes
disk size=2^30 byte
bit map大小=2^30/2^12=2^18 bits(32KB)
linked free space list
效率差,較難取得連續空間
簡省空間
…………………………………………
efficiency 空間利用率
取決於
allocation methods
directory algorithms
performance 效能
取決於
disk cache
free-behind和read -ahead:一種加速連續存取的技術
virtual disk/RAM disk
…………………………………
log structured file systems
會將每個對檔案系統的動作視為一個transactions,所有transactions被寫到log
若檔案系統crash,這種檔案系統復原最快
ex:ntfs, ext3
…
network file systems/sun nfs
用於存取遠端檔案的file system
遠端目錄可被掛載本地file system目錄
NFS architecture
unix file-system interface:open,read,write,…等
VFS(virtual file system) layer: 呼叫nfs protocol procedures
NFS service layer:實作nfs protocol
nfs protocol
屬於rpc(remote procedure calls),工作包括searching,reading,…等
NFS servers屬於stateless,但在v4版本為stateful
主要使用udp/ip
…………………………………………………………………………………………………….
6.popular filesysem
Windows
FAT(12,16,32)
https://systw.net/note/af/sblog/more.php?id=300
NTFS, journal file system, unicode
https://systw.net/note/af/sblog/more.php?id=301
Linux
ext2, not journal file system
ext3, journal file system
Mac OS X(based on BSD unix)
HFS, filename encoding in macroman
HFS plus, filename encoding in unicode, journal file system
Sun Solaris 10
ZFS, supporting multiple HD combination
ps
tool for file system analysis
sleuth kit
FTK imager
disk editor