file systems

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 

2014-01-12 09:27:23發表 2015-10-18 13:11:02修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統

數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net