{"id":704,"date":"2015-10-18T15:35:00","date_gmt":"2015-10-18T07:35:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=704"},"modified":"2023-11-04T15:43:58","modified_gmt":"2023-11-04T07:43:58","slug":"file-systems","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/704","title":{"rendered":"File Systems"},"content":{"rendered":"\n

1.\u6982\u5ff5<\/strong><\/h2>\n\n\n\n

file system structrue<\/strong>
\u4e3b\u8981\u5305\u62ec\u4ee5\u4e0b
file<\/strong>
\u908f\u8f2f\u7684\u5132\u5b58\u55ae\u4f4d
file system<\/strong>
\u5132\u5b58\u55ae\u4f4d\u662fblock
\u4f7f\u7528\u4e0d\u540c\u7684\u8cc7\u6599\u7d50\u69cb\u4f86\u8868\u9054\u6a94\u6848
ex:FAT32,NTFS,ext2,ext3, ISO9660,googleFS, oracle ASM,ZFS
FCB(file control block)<\/strong>
\u8a18\u9304\u6a94\u6848\u7684\u8cc7\u8a0a<\/p>\n\n\n\n

…<\/p>\n\n\n\n

file system layer<\/strong>
layer2(user space)
\u3000application programs<\/strong>
layer1(kernel space)
\u3000logical file system:<\/strong>
\u3000\u7ba1\u7406metadata information,FCB maintain
\u3000diretory structure\u548cprotection
\u3000file-organization module<\/strong>
\u3000\u7ba1\u7406free space,disk allocation
\u3000\u8f49\u63dblogical block address\u5230physical block address
\u3000basic file system:<\/strong>
\u3000\u8ca0\u8cacscheduling,disk caching,buffering,
\u3000buffers\u61c9\u7528\u5728\u8cc7\u6599\u50b3\u8f38,caches\u61c9\u7528\u5728\u8cc7\u6599\u7684\u4f7f\u7528
\u3000\u63a7\u5236device\u7684\u6a19\u6e96\u547d\u4ee4,ex:retrieve block 123
\u3000I\/O control:<\/strong>
\u3000\u8ca0\u8cacdevice driver,interrupt handler, \u7ba1\u7406I\/O devices
\u3000\u57f7\u884clow-level I\/O\u547d\u4ee4,ex:read drive1, cylinder 72,track 2, sector 10
layer0
\u3000devices<\/strong><\/p>\n\n\n\n

……<\/p>\n\n\n\n

2.\u5e38\u898bfile system structures<\/strong><\/h2>\n\n\n\n

disk file system structures<\/strong>
\u4e3b\u8981\u7531\u4ee5\u4e0b\u69cb\u6210
boot control block :<\/strong>
\u5305\u542b\u958b\u6a5f\u8cc7\u8a0a
partition(volume) control block\/super block<\/strong>
\u5305\u542bvolume\u7d30\u7bc0,\u50cf\u662fblocks\u6578\u91cf,\u5927\u5c0f\u548cfree-block\u548cfree-fcb\u7684\u8a08\u7b97
directory structure<\/strong>
\u7528\u4f86organzie files,\u5305\u62ecfile names,\u4e26\u95dc\u806f\u5230FCB
file control block
data block<\/strong>
block\u4e00\u822c\u662f512byte<\/p>\n\n\n\n

file control block<\/strong>
\u4e00\u822c\u6703\u5305\u542b\u4ee5\u4e0b\u8cc7\u8a0a
file permissions
file dates ex:create,access,write
file owner,group, ACL
file size
file data blocks<\/p>\n\n\n\n

……<\/p>\n\n\n\n

memory file system structures<\/strong>
\u4e3b\u8981\u7528\u65bc\u63d0\u6607performance
\u901a\u5e38\u7531\u4ee5\u4e0b\u69cb\u6210
in-memory mount table<\/strong>
\u5305\u62ec\u6bcf\u4e00\u500b\u5df2\u639b\u8f09\u7684volumen\u8cc7\u8a0a
in-memory directory-structure cache<\/strong>
\u7528\u65bc\u8b80\u53d6,\u4fdd\u5b58\u6700\u8fd1\u5728\u5b58\u53d6\u7684directories
system-wide open-file table<\/strong>
\u7528\u65bc\u5beb\u5165,\u5305\u542b\u6240\u6709\u5df2\u958b\u555f\u6a94\u6848\u7684\u4e00\u4efdFCB\u526f\u672c
per-process open-file table<\/strong>
\u7528\u65bc\u5beb\u5165,\u8ca0\u8cac\u5132\u5b58\u6307\u6a19
buffers<\/strong>
\u7528\u65bc\u8b80\u53d6\u6216\u5beb\u5165file system block<\/p>\n\n\n\n

…<\/p>\n\n\n\n

virtual file systems<\/strong>
\u5141\u8a31\u4e0d\u540c\u7684system call\u4ecb\u9762(API)\u7528\u5728\u4e0d\u540c\u985e\u578b\u7684file system
\u7d50\u69cb\u4e3b\u8981\u5982\u4e0b
layer2 (user space)
\u3000file system interface
layer1 (kernel space)
\u3000VFS interface
\u3000file system:\u5305\u542b\u5404\u7a2efile system
\u3000storage:\u5305\u62ecdisk, network disk,…\u7b49<\/p>\n\n\n\n

………………………………………………………………………………………….<\/p>\n\n\n\n

3.directory implementation<\/strong><\/h2>\n\n\n\n

directory-file\u7d50\u69cb<\/strong>
\u5927\u81f4\u5982\u4e0b
0_empty, filename_a, pointer to FCB1
1_used, filename_b, pointer to FCB2
2_used, filename_c, pointer to FCB3
…omit…<\/p>\n\n\n\n

directory implementation\u5169\u5927\u505a\u6cd5
linear list<\/strong>
\u3000\u76ee\u9304\u7ba1\u7406\u65b9\u4fbf
\u3000\u5be6\u4f5c\u5bb9\u6613
\u3000search\u901f\u5ea6\u6162
hash table<\/strong>
\u3000\u4ee5key\u505a\u6a94\u540d
\u3000search\u901f\u5ea6\u5feb
\u3000\u53ef\u80fd\u767c\u751fcollisions(\u78b0\u649e\u554f\u984c)
\u3000hash table\u5927\u5c0f\u56fa\u5b9a\uff0c\u8b8a\u5927\u6642\u8981\u53e6\u5916\u505arehashing\u8655\u7406<\/p>\n\n\n\n

…………………………………………………………………………<\/p>\n\n\n\n

4.allocation methods<\/strong><\/h2>\n\n\n\n

\u7a7a\u9593\u5206\u914d,\u4e5f\u7a31disk blocks
\u4e3b\u8981\u6709\u4e09\u5927\u65b9\u6cd5
\u3000contiguous allocation(\u9023\u7e8c\u5f0f\u7a7a\u9593\u5206\u914d)
\u3000linked allocation
\u3000indexed allocation<\/p>\n\n\n\n

…<\/p>\n\n\n\n

contiguous allocation \u3000<\/strong>
\u6bcf\u500b\u6a94\u6848\u90fd\u6703\u4f54\u7528\u4e00\u7d44disk\u4e0a\u7684\u9023\u7e8c\u7a7a\u9593
\u512a\u9ede
\u3000\u5b58\u53d6\u901f\u5ea6\u5feb , support random access
\u7f3a\u9ede
\u3000\u6703\u6709external fragmentation,\u8981\u53e6\u5916\u82b1\u6642\u9593compacts(\u91cd\u65b0\u805a\u96c6)\u4ee5\u7a7a\u51fa\u53ef\u4f7f\u7528\u7684\u9023\u7e8c\u7a7a\u9593
\u3000\u5efa\u7acb\u6a94\u6848\u6642\u8981\u5224\u65b7\u9700\u8981\u4fdd\u7559\u591a\u5c11\u7a7a\u9593\uff0c\u592a\u5c0f\u7121\u6cd5\u64f4\u5145\uff0c\u592a\u5927\u6d6a\u8cbb\u7a7a\u9593
logical address\u70ba1024
ex:IBM\u7684VM\/CMS<\/p>\n\n\n\n

contiguous allocation directory\u7d50\u69cb<\/strong>
\u5927\u81f4\u5982\u4e0b
file1, start 0, length 4
file2, start 6, length 2
…omit…<\/p>\n\n\n\n

….<\/p>\n\n\n\n

linked allocation<\/strong>
\u6bcf\u500b\u6a94\u6848\u90fd\u662fdisk\u4e0a\u7684linked list, \u9760\u6307\u6a19\u4f86\u4e32\u63a5
\u512a\u9ede
\u3000\u7121external fragmentaion
\u3000\u5efa\u7acb\u6a94\u6848\u6642\u4e0d\u7528\u7169\u8166\u8981\u4fdd\u7559\u591a\u5c11\u7a7a\u9593\u7684\u554f\u984c\uff0c\u7a7a\u9593\u6548\u7387\u597d
\u7f3a\u9ede
\u3000\u6307\u6a19\u79fb\u52d5\u6642\uff0c\u82e5\u8ddd\u96e2\u904e\u9060\uff0c\u8b80\u5beb\u982d\u79fb\u52d5\u8f03\u983b\u7e41\uff0c\u8b80\u53d6\u6703\u8f03\u6d6a\u8cbb\u6642\u9593
\u3000not support random access
\u3000reliability low: \u82e5\u5176\u4e2d\u4e00\u500b\u6307\u6a19\u6d88\u5931\uff0c\u6574\u500blinked\u6703\u65b7\u6389\uff0c\u9664\u975e\u7528double linked list\u89e3\u6c7a
\u3000\u6307\u6a19\u6703\u4f54\u7528\u5230\u7a7a\u9593
logical address\u70ba1020,\u56e0\u70ba\u8981\u4fdd\u75594\u500bbyte\u505a\u6307\u6a19<\/p>\n\n\n\n

linked allocation directory\u7d50\u69cb<\/strong>
\u5927\u81f4\u5982\u4e0b
file, start, end
file1, start 2, end 10 \/\/\u6839\u64dablock2\u5c0b\u627e\u4e0b\u4e00\u500bblcok
…omit…
ps:
linked\u8cc7\u8a0a\u5132\u5b58\u5728block<\/strong>
\u6bcf\u500bblock\u6703\u6839\u64dalinked\u8cc7\u8a0a\u627e\u5230\u4e0b\u4e00\u500bblock\u4f4d\u7f6e
\u5927\u81f4\u5982\u4e0b
block2:16
block16:1
block1:10
block10:-1<\/p>\n\n\n\n


FAT(file allocation table)<\/strong>
based on linkd allocation
keep 2 fat on disk,\u4e00\u500b\u662f\u539f\u672c\u7684linked allocation directory,\u53e6\u4e00\u500b\u8a18\u9304block\u7684linked\u8cc7\u8a0a
\u512a\u9ede
\u3000support random access
\u3000improve reliability:
\u61c9\u7528\u5728\u5fae\u8edf\u7684file system,\u50cf\u662fFAT12,16,32
\u3000\u6578\u5b57\u8868\u793atable\u53ef\u652f\u63f4\u7684\u9805\u76ee\u6578\u91cf
\u3000ex:FAT32=8kb*2^32=33tb<\/p>\n\n\n\n

…<\/p>\n\n\n\n

indexed allocation<\/strong>
\u628a\u6240\u6709\u6307\u6a19\u96c6\u4e2d\u8d77\u4f86\u653e\u5728index block
index block\u53ef\u4ee5\u5feb\u53d6\u65b9\u5f0f\u5b58\u5728memory,\u4f46\u8cc7\u6599\u5340\u6bb5\u4ecd\u7136\u6563\u4f48\u5728disk\u7684\u5404\u5730\u65b9
\u512a\u9ede
\u3000\u652f\u63f4random access
\u3000\u7121external fragentation
\u7f3a\u9ede
\u3000\u4f46\u8981\u53e6\u5916\u6e96\u5099\u7a7a\u9593\u5b58index table\uff0c\u6bd4linked allocation\u9084\u8981\u591a
\u3000\u6703\u6709index block\u4e0d\u5920\u7684\u554f\u984c
logical address\u70ba1024<\/p>\n\n\n\n

indexed allocation directory\u7d50\u69cb<\/strong>
\u5927\u81f4\u5982\u4e0b
file , index block
paper, 19 \/\/\u5728\u7b2c19\u500bblock\u6703\u8a18\u8f09\u6240\u6709\u8a72\u6a94\u6848\u7684block
…omit…<\/p>\n\n\n\n

file size of unbounded length<\/strong>
\u89e3\u6c7a\u4e00\u500b\u6a94\u6848\u4e00\u500bindex block\u4e0d\u5920\u7684\u554f\u984c
\u4e3b\u8981\u6709\u4e09\u7a2e\u65b9\u5f0f
\u3000linked scheme
\u3000multi-level index: ex:two-level index
\u3000combined scheme ex: UNIX i-node<\/p>\n\n\n\n

multi-level index<\/strong>
\u82e5\u4f7f\u75284kb\u7684block,\u53ef\u4ee5\u5132\u5b581024\u500b4byte\u6307\u6a19
\u82e5\u662ftwo-level index\uff0c\u5247\u53ef\u4ee5\u5132\u5b581024^2\u500b4byte\u6307\u6a19<\/p>\n\n\n\n

combined scheme<\/strong>
\u4f7f\u752815\u500bindex\u5982\u4e0b
direct blocks(\u76f4\u63a5\u5340\u6bb5)\uff1a\u4f7f\u752812\u500bindex
\u3000\u8a18\u8f09\u8a72\u6a94\u6848\u7684block
\u3000\u82e5\u4e00\u500bblock\u70ba4kb,\u90a3\u5c31\u670948kb\u7684\u8cc7\u6599\u53ef\u76f4\u63a5\u5b58\u53d6
inderect block(\u9593\u63a5\u5340\u6bb5)
\u3000\u8a18\u8f09\u6a94\u6848block\u7684\u4f4d\u7f6e,\u4e26\u5206\u70ba\u4ee5\u4e0b
\u3000single indirect block(\u55ae\u5c64\u9593\u63a5\u5340\u6bb5)\uff1a\u4f7f\u75281\u500bindex
\u3000double indirect block(\u96d9\u5c64\u9593\u63a5\u5340\u6bb5)\uff1a\u4f7f\u75281\u500bindex
\u3000triple indirect block(\u4e09\u5c64\u9593\u63a5\u5340\u6bb5)\uff1a\u4f7f\u75281\u500bindex<\/p>\n\n\n\n


…………………………………………………………………………………..<\/p>\n\n\n\n

5.\u5176\u4ed6\u88dc\u5145<\/strong><\/h2>\n\n\n\n

…………………………………………<\/p>\n\n\n\n


free-space management
\u4e3b\u8981\u4f7f\u7528\u65b9\u6cd5\u6709
\u3000bit\/vector
\u3000linked free space list<\/p>\n\n\n\n

bit vector\/bit map<\/strong>
\u6548\u7387\u9ad8,\u4f46\u8981\u984d\u5916\u4f54\u4e3b\u8a18\u61b6\u9ad4\u7a7a\u9593
\u7528\u4f86\u8868\u793ablock\u70bafree\u6216occupied
\u4e3b\u8981\u653e\u5165memory\u4e26\u5728\u95dc\u6a5f\u6642\u5beb\u5165disk\u4fdd\u5b58
ex:
bit map\u5927\u5c0f?
block size=2^12 bytes
disk size=2^30 byte
bit map\u5927\u5c0f=2^30\/2^12=2^18 bits(32KB)<\/p>\n\n\n\n

linked free space list<\/strong>
\u6548\u7387\u5dee,\u8f03\u96e3\u53d6\u5f97\u9023\u7e8c\u7a7a\u9593
\u7c21\u7701\u7a7a\u9593<\/p>\n\n\n\n

…………………………………………<\/p>\n\n\n\n

efficiency \u7a7a\u9593\u5229\u7528\u7387<\/strong>
\u53d6\u6c7a\u65bc
allocation methods
directory algorithms<\/p>\n\n\n\n

performance \u6548\u80fd<\/strong>
\u53d6\u6c7a\u65bc
disk cache
free-behind\u548cread -ahead:\u4e00\u7a2e\u52a0\u901f\u9023\u7e8c\u5b58\u53d6\u7684\u6280\u8853
virtual disk\/RAM disk<\/p>\n\n\n\n

…………………………………<\/p>\n\n\n\n

log structured file systems<\/strong>
\u6703\u5c07\u6bcf\u500b\u5c0d\u6a94\u6848\u7cfb\u7d71\u7684\u52d5\u4f5c\u8996\u70ba\u4e00\u500btransactions,\u6240\u6709transactions\u88ab\u5beb\u5230log
\u82e5\u6a94\u6848\u7cfb\u7d71crash,\u9019\u7a2e\u6a94\u6848\u7cfb\u7d71\u5fa9\u539f\u6700\u5feb
ex:ntfs, ext3<\/p>\n\n\n\n

…<\/p>\n\n\n\n

network file systems\/sun nfs<\/strong>
\u7528\u65bc\u5b58\u53d6\u9060\u7aef\u6a94\u6848\u7684file system
\u9060\u7aef\u76ee\u9304\u53ef\u88ab\u639b\u8f09\u672c\u5730file system\u76ee\u9304<\/p>\n\n\n\n

NFS architecture<\/strong>
unix file-system interface:open,read,write,…\u7b49
VFS(virtual file system) layer: \u547c\u53ebnfs protocol procedures
NFS service layer:\u5be6\u4f5cnfs protocol<\/p>\n\n\n\n

nfs protocol<\/strong>
\u5c6c\u65bcrpc(remote procedure calls),\u5de5\u4f5c\u5305\u62ecsearching,reading,…\u7b49
NFS servers\u5c6c\u65bcstateless,\u4f46\u5728v4\u7248\u672c\u70bastateful
\u4e3b\u8981\u4f7f\u7528udp\/ip<\/p>\n\n\n\n

…………………………………………………………………………………………………….<\/p>\n\n\n\n

6.popular filesysem<\/p>\n\n\n\n

Windows<\/strong>
\u3000FAT(12,16,32)
\u3000https:\/\/systw.net\/note\/af\/sblog\/more.php?id=300<\/a>
\u3000NTFS, journal file system, unicode
\u3000https:\/\/systw.net\/note\/af\/sblog\/more.php?id=301<\/a>
Linux<\/strong>
\u3000ext2, not journal file system
\u3000ext3, journal file system
Mac OS X(based on BSD unix)<\/strong>
\u3000HFS, filename encoding in macroman
\u3000HFS plus, filename encoding in unicode, journal file system
Sun Solaris 10<\/strong>
\u3000ZFS, supporting multiple HD combination <\/p>\n\n\n\n

ps
tool for file system analysis<\/strong>
sleuth kit
FTK imager
disk editor <\/p>\n","protected":false},"excerpt":{"rendered":"

1.\u6982\u5ff5 file system structrue\u4e3b\u8981\u5305\u62ec …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[22],"tags":[],"class_list":["post-704","post","type-post","status-publish","format-standard","hentry","category-operationsystem"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/704","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=704"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/704\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=704"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=704"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=704"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}