操作系統(tǒng)之文件系統(tǒng)2

1、11.2Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nFile-System Structure 文件系統(tǒng)結(jié)構(gòu)文件系統(tǒng)結(jié)構(gòu)nFile-System Implementation 文件系統(tǒng)實(shí)現(xiàn)文件系統(tǒng)實(shí)現(xiàn)nDirectory Implementation 目錄結(jié)構(gòu)實(shí)現(xiàn)目錄結(jié)構(gòu)實(shí)現(xiàn)nAllocation Methods 空間分配方法空間分配方法nFree-Space Management 空閑磁盤空間管理空閑磁盤空間管理nEfficiency and Performance

2、 效率與性能nRecovery 恢復(fù)nLog-Structured File Systems 基于日志的文件系統(tǒng)nNFS 網(wǎng)絡(luò)文件系統(tǒng)nExample: WAFL File System11.3Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n文件系統(tǒng)的整體結(jié)構(gòu)（目錄+文件）都是存放在磁盤里的n為什么選擇磁盤來(lái)存儲(chǔ)文件系統(tǒng)數(shù)據(jù)？因?yàn)槠涮攸c(diǎn)l可以原地重寫。4 從磁盤上讀一塊，修改該塊，然后將它寫回原來(lái)的位置l可以直接訪問(wèn)磁盤上的任意一塊信息。4方便地按順序或者隨機(jī)的方式訪問(wèn)文

3、件4從對(duì)某一塊的訪問(wèn)，換到對(duì)另一個(gè)塊的訪問(wèn)，只需要簡(jiǎn)單移動(dòng)讀寫磁頭，并等待磁盤轉(zhuǎn)動(dòng)即可完成11.4Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n文件系統(tǒng)的兩個(gè)設(shè)計(jì)問(wèn)題l(1)如何定義文件系統(tǒng)對(duì)用戶的接口4定義文件及其屬性4文件所允許的操作4組織文件的目錄結(jié)構(gòu)l(2)如何創(chuàng)建數(shù)據(jù)結(jié)構(gòu)來(lái)將文件系統(tǒng)的邏輯結(jié)構(gòu)映射到外存空間11.5Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition,

4、Jan 1, 2005n文件系統(tǒng)的兩個(gè)設(shè)計(jì)問(wèn)題l(1)如何定義文件系統(tǒng)對(duì)用戶的接口4定義文件及其屬性4文件所允許的操作4組織文件的目錄結(jié)構(gòu)l(2)如何創(chuàng)建數(shù)據(jù)結(jié)構(gòu)來(lái)將文件系統(tǒng)的邏輯結(jié)構(gòu)映射到外存空間11.6Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.7Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.8Silberschatz, Galvi

5、n and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.9Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.10Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nFile control block storage structure consisting of inf

6、ormation about a filen文件控制塊 關(guān)于文件的信息的存儲(chǔ)結(jié)構(gòu)11.11Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nBoot Control Block 引導(dǎo)控制塊l包含引導(dǎo)操作系統(tǒng)所需的信息nVolume Control Block 卷（分區(qū)）控制塊l包含卷（或分區(qū)）的詳細(xì)信息，如分區(qū)的磁盤塊數(shù)、塊的大小、空閑塊數(shù)量等n每個(gè)文件系統(tǒng)的目錄結(jié)構(gòu)l用來(lái)組織文件數(shù)據(jù)n每個(gè)文件的FCB（File Control Block）l包含文件的詳細(xì)信息，諸如文件權(quán)

7、限、擁有者、大小和數(shù)據(jù)塊的位置等。11.12Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nIn-Memory File System Structures 文件系統(tǒng)的內(nèi)存內(nèi)信息包括l一個(gè)安裝表，包括所有已經(jīng)安裝的卷（或分區(qū)）的信息l一個(gè)目錄結(jié)構(gòu)緩存，用來(lái)保存進(jìn)來(lái)訪問(wèn)過(guò)的目錄信息l全局范圍的打開(kāi)文件表，包括系統(tǒng)中所有被打開(kāi)文件的FCB副本和其他信息l單個(gè)進(jìn)程的打開(kāi)文件表這些內(nèi)存中的信息是一些緩存信息，其存在的目的是提高性能。它們?cè)谖募到y(tǒng)安裝時(shí)被加載，在文件系統(tǒng)被卸載時(shí)丟

8、棄。11.13Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.14Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nRaw Disk 原始磁盤l沒(méi)有任何文件系統(tǒng)的磁盤分區(qū)nRoot Partition 根分區(qū)l安裝了文件系統(tǒng)，并且裝有操作系統(tǒng)內(nèi)核或其他系統(tǒng)文件的分區(qū)11.15Silberschatz, Galvin and Gagne 2005Op

9、erating System Concepts 7th Edition, Jan 1, 2005nVirtual File Systems (VFS) provide an object-oriented way of implementing file systems. 虛擬文件系統(tǒng)是按照面向?qū)ο蟮脑O(shè)計(jì)理念來(lái)提供操作系統(tǒng)的多文件系統(tǒng)支持nVFS allows the same system call interface (the API) to be used for different types of file systems. VFS提供一套統(tǒng)一的文件系統(tǒng)訪問(wèn)接口11.16Silber

10、schatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.17Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nLinear list of file names with pointer to the data blocks.lsimple to programltime-consuming to execute最為簡(jiǎn)單的目錄實(shí)現(xiàn)方法： 使用存儲(chǔ)文件名和數(shù)據(jù)塊指針的線

11、性列表。nHash Table linear list with hash data structure.ldecreases directory search timelcollisions situations where two file names hash to the same locationlfixed size哈希表可以帶來(lái)目錄查找方面的效率改善。11.18Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nAn allocation method refe

12、rs to how disk blocks are allocated for files: 如何把磁盤分配給nContiguous allocation 連續(xù)空間分配連續(xù)空間分配nLinked allocation 鏈接式分配鏈接式分配nIndexed allocation 索引分配索引分配11.19Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.20Silberschatz, Galvin and Gagne 2005Operating System Concep

13、ts 7th Edition, Jan 1, 200511.21Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nMany newer file systems (I.e. Veritas File System) use a modified contiguous allocation scheme 很多新文件系統(tǒng)采用了連續(xù)空間分配方法的一個(gè)變種，稱為基于“擴(kuò)展”的連續(xù)空間分配nExtent-based file systems allocate disk blocks

14、in extents 磁盤塊被劃分成若干extents（擴(kuò)展）nAn extent is a contiguous block of disks (每個(gè)擴(kuò)展是一段連續(xù)的磁盤空間)lExtents are allocated for file allocationlA file consists of one or more extents. 一個(gè)文件由1個(gè)或多個(gè)擴(kuò)展組成11.22Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005文件名 始址 末址jeep 9 25文件目錄01

15、234567891011121314151617181920212223242526272829303111016-12511.23Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nEach file is a linked list of disk blocks: blocks may be scattered anywhere on the disk. 每個(gè)磁盤塊中留出一個(gè)指針地址，用來(lái)進(jìn)行塊間鏈接pointerblock =11.24Silberschatz, Gal

16、vin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nSimple need only starting address 鏈接方式實(shí)現(xiàn)簡(jiǎn)單，一個(gè)文件只需要記錄其起始地址（起始?jí)K號(hào)）nFree-space management system no waste of space 空間空間管理 - 浪費(fèi)較少nNo random access 缺點(diǎn)：不支持隨機(jī)訪問(wèn)11.25Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition,

17、Jan 1, 2005n文件分配表 FATn在MS-DOS，OS/2操作系統(tǒng)中使用nFAT將磁盤上的若干個(gè)連續(xù)的分區(qū)分為一簇n將盤塊中的鏈接字按簇號(hào)的順序集中起來(lái)，將盤塊中的鏈接字按簇號(hào)的順序集中起來(lái)，構(gòu)成盤文件映射表構(gòu)成盤文件映射表/ /文件分配表文件分配表nFAT16 : 16FAT16 : 16位的文件分配表位的文件分配表l鏈接字為鏈接字為1616位（決定了簇號(hào)的范圍）位（決定了簇號(hào)的范圍）nFAT32 : 32FAT32 : 32位的文件分配表位的文件分配表l鏈接字為鏈接字為3232位（決定了簇號(hào)的范圍）位（決定了簇號(hào)的范圍）11.26Silberschatz, Galvin and

18、Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.27Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005FAT16文件系統(tǒng)文件系統(tǒng)FAT32文件系統(tǒng)文件系統(tǒng)磁盤大小磁盤大小扇區(qū)扇區(qū)/簇簇字節(jié)數(shù)字節(jié)數(shù)/簇簇磁盤大小磁盤大小扇區(qū)扇區(qū)/簇簇字節(jié)數(shù)字節(jié)數(shù)/簇簇4.116MB21k32.5260MB1512=128MB 42k=8GB84k=256MB 84k=16GB168k=512MB 168k=32GB3

19、216k32GB6432k=2GB6432k11.28Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n在FAT16中一簇最大64個(gè)扇區(qū)，為什么FAT16能管理的磁盤分區(qū)為2G？11.29Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nBrings all pointers together into the index block.索引表的邏輯表示1

20、1.30Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.31Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005outer-indexindex tablefile11.32Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.33

21、Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n基于位圖（位向量, bitmap, bit vector）的空閑空間管理n基于鏈接方式的空閑空間管理n組 n計(jì)數(shù)11.34Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n位示圖法通過(guò)位示圖進(jìn)行文件存儲(chǔ)空間的分配與回收。l字位為0，表示對(duì)應(yīng)的文件存儲(chǔ)空間的物理塊是空閑的；l字位為1，表示對(duì)應(yīng)的文件存儲(chǔ)空間

22、的物理塊已被占用。n為了找到N個(gè)自由塊，需要搜索位示圖，找到N個(gè)“0”位，再經(jīng)過(guò)一次簡(jiǎn)單的換算就可以得到對(duì)應(yīng)的地址。1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 10 1 1 1 1 1 1 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 1 0 1 1 1 0 00 1 1 1 1 1 1 0 0 0 0 0 0 1 1 10 1 1 1 1 1 1 0 0 0 1 0 0 0 1 00 0 1 1 1 0 0 1 1 1 0 1 1 1 1 10 1 2 3 4 5 6 7 8 9 10111213141501234511.35Silberschatz,

23、 Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n位示圖的尺寸是固定的，通常比較小，可以保存在主存中。n存儲(chǔ)分配時(shí)，在該圖中尋找與0相應(yīng)的塊，然后把位示圖中相應(yīng)位置“1”。n釋放時(shí)，只要把位示圖中相應(yīng)位清0。n因此，存儲(chǔ)空間的分配和回收工作都比較方便。11.36Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n但某些情況下位示圖可能很大，不宜保存在主存中。n例：一個(gè)16GB的磁盤

24、，若數(shù)據(jù)塊大小為512字節(jié)，則位示圖大小為16*230/(8*512)=222=4MB，大約需要8000個(gè)磁盤扇區(qū)的存儲(chǔ)空間。n此時(shí)，可把該圖放入輔存中，只把其中一段裝入主存，并先用該段進(jìn)行分配，待它填滿時(shí)（即所有的位均變成“1”），再與外存中的另一段交換。11.37Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n即使內(nèi)存足夠大，可以存放全部或絕大部分位示圖數(shù)據(jù)，搜索一個(gè)很大的位示圖將會(huì)降低文件系統(tǒng)的性能。n尤其是當(dāng)磁盤空間快要用完時(shí)，剩下的空閑磁盤塊很少時(shí)，文件系統(tǒng)的性

25、能將嚴(yán)重降低。n解決方法：分組l化整為零，將磁盤空間劃分成若干個(gè)分組，為每一組維護(hù)一個(gè)相對(duì)比較小的bitmap11.38Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.39Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n將n個(gè)空閑塊的地址放在第1個(gè)空閑塊中n這n個(gè)空閑塊中的前n-1個(gè)塊確實(shí)為空，而最后一個(gè)塊則包含另外n個(gè)空閑塊的地址n如此繼續(xù)n這

26、時(shí)對(duì)空閑鏈表的一個(gè)改進(jìn)11.40Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005n通常，可能有多個(gè)連續(xù)塊需要同時(shí)分配或釋放l特別對(duì)于連續(xù)空間分配方法n維護(hù)空閑空間的時(shí)候，記錄第一個(gè)塊的地址和緊跟第一塊的空閑塊的數(shù)量nn空閑空間表的每個(gè)條目包括l磁盤某個(gè)空閑空間區(qū)的起始地址l連續(xù)的空閑塊的數(shù)量11.41Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nEf

27、ficiency dependent on:ldisk allocation and directory algorithmsltypes of data kept in files directory entry磁盤空間的有效使用主要取決于所使用的磁盤分配磁盤分配和目錄管理算法目錄管理算法保留在文件目錄條目?jī)?nèi)的數(shù)據(jù)類型也需要加以考慮。11.42Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nPerformance 性能ldisk cache separate secti

28、on of main memory for frequently used blockslfree-behind（馬上釋放） and read-ahead(預(yù)先讀取) techniques to optimize sequential accesslimprove PC performance by dedicating section of memory as virtual disk, or RAM disk11.43Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nA

29、 page cache caches pages rather than disk blocks using virtual memory techniquesnMemory-mapped I/O uses a page cachenRoutine I/O through the file system uses the buffer (disk) cachenThis leads to the following figure11.44Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1

30、, 200511.45Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nA unified buffer cache uses the same page cache to cache both memory-mapped pages and ordinary file system I/O11.46Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.

31、47Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nConsistency checking compares data in directory structure with data blocks on disk, and tries to fix inconsistenciesnUse system programs to back up data from disk to another storage device (floppy disk, magnetic

32、tape, other magnetic disk, optical)nRecover lost file or disk by restoring data from backup11.48Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nLog structured (or journaling) file systems record each update to the file system as a transactionnAll transactions ar

33、e written to a logl A transaction is considered committed once it is written to the loglHowever, the file system may not yet be updatednThe transactions in the log are asynchronously written to the file systeml When the file system is modified, the transaction is removed from the lognIf the file sys

34、tem crashes, all remaining transactions in the log must still be performed11.49Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nAn implementation and a specification of a software system for accessing remote files across LANs (or WANs)nThe implementation is part

35、of the Solaris and SunOS operating systems running on Sun workstations using an unreliable datagram protocol (UDP/IP protocol and Ethernet11.50Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nInterconnected workstations viewed as a set of independent machines wit

36、h independent file systems, which allows sharing among these file systems in a transparent mannerlA remote directory is mounted over a local file system directory4 The mounted directory looks like an integral subtree of the local file system, replacing the subtree descending from the local directory

37、lSpecification of the remote directory for the mount operation is nontransparent; the host name of the remote directory has to be provided4 Files in the remote directory can then be accessed in a transparent mannerlSubject to access-rights accreditation, potentially any file system (or directory wit

38、hin a file system), can be mounted remotely on top of any local directory11.51Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nNFS is designed to operate in a heterogeneous environment of different machines, operating systems, and network architectures; the NFS s

39、pecifications independent of these medianThis independence is achieved through the use of RPC primitives built on top of an External Data Representation (XDR) protocol used between two implementation-independent interfacesnThe NFS specification distinguishes between the services provided by a mount

40、mechanism and the actual remote-file-access services 11.52Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.53Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005MountsCascading mounts11.54Silberschatz, Galvin and Gagne 2005Opera

41、ting System Concepts 7th Edition, Jan 1, 2005nEstablishes initial logical connection between server and clientnMount operation includes name of remote directory to be mounted and name of server machine storing itlMount request is mapped to corresponding RPC and forwarded to mount server running on s

42、erver machine lExport list specifies local file systems that server exports for mounting, along with names of machines that are permitted to mount them nFollowing a mount request that conforms to its export list, the server returns a file handlea key for further accessesnFile handle a file-system id

43、entifier, and an inode number to identify the mounted directory within the exported file systemnThe mount operation changes only the users view and does not affect the server side 11.55Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nProvides a set of remote proc

44、edure calls for remote file operations. The procedures support the following operations:lsearching for a file within a directory lreading a set of directory entries lmanipulating links and directories laccessing file attributeslreading and writing filesnNFS servers are stateless; each request has to

45、 provide a full set of arguments(NFS V4 is just coming available very different, stateful)nModified data must be committed to the servers disk before results are returned to the client (lose advantages of caching)nThe NFS protocol does not provide concurrency-control mechanisms11.56Silberschatz, Gal

46、vin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nUNIX file-system interface (based on the open, read, write, and close calls, and file descriptors)nVirtual File System (VFS) layer distinguishes local files from remote ones, and local files are further distinguished according to t

47、heir file-system typeslThe VFS activates file-system-specific operations to handle local requests according to their file-system types lCalls the NFS protocol procedures for remote requestsnNFS service layer bottom layer of the architecturelImplements the NFS protocol11.57Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 200511.58Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Jan 1, 2005nPerformed by breaking the path into component names and p