《操作系统教学课件OS_11》由会员分享，可在线阅读，更多相关《操作系统教学课件OS_11（33页珍藏版）》请在金锄头文库上搜索。
1、Chapter 11 File System ImplementationOperating System.School of Software. HUSTChapter 11: File System ImplementationlFile System StructurelFile System Implementation lDirectory ImplementationlAllocation MethodslFree-Space Management lRecovery (恢复)lLog-Structured File Systems(基于日志的文件系统)lNFSOperating
2、System.School of Software. HUSTObjectives (P411)lTo describe the details of implementing local file systems and directory structures.lTo describe the implementation of remote file systems.lTo discuss block allocation and free-block algorithms and trade-offs.Operating System.School of Software. HUSTF
3、ile-System Structure (P412)lFile structurenLogical storage unitnCollection of related informationlFile system resides on secondary storage (disks).lFile system organized into layers.lFile control block storage structure consisting of information about a file.Operating System.School of Software. HUST
4、Layered File System (P412)Operating System.School of Software. HUSTA Typical File Control Block (P415)Operating System.School of Software. HUSTIn-Memory File System Structures (P416)lThe following figure illustrates the necessary file system structures provided by the operating systems.lFigure 11-3(
5、a) refers to opening a file.lFigure 11-3(b) refers to reading a file.Operating System.School of Software. HUSTIn-Memory File System Structures (P416)Operating System.School of Software. HUSTVirtual File Systems (P417)l(P417) Two questionslVirtual File Systems (VFS) provide an object-oriented way of
6、implementing file systems.lVFS allows the same system call interface (the API) to be used for different types of file systems.lThe API is to the VFS interface, rather than any specific type of file system. (see figure 11.4)Operating System.School of Software. HUSTSchematic View of Virtual File Syste
7、m (P418)Operating System.School of Software. HUSTDirectory Implementation (P420)lLinear list of file names with pointer to the data blocks.nsimple to programntime-consuming to executelHash Table linear list with hash data structure.ndecreases directory search timencollisions situations where two fil
8、e names hash to the same locationnfixed sizeOperating System.School of Software. HUSTAllocation Methods (P420)lAn allocation method refers to how disk blocks are allocated for files:lContiguous allocation （连续分配）lLinked allocation （链接分配）lIndexed allocation （索引分配）Operating System.School of Software. H
9、USTContiguous Allocation (P421)lEach file occupies a set of contiguous blocks on the disk.lSimple only starting location (block #) and length (number of blocks) are required.lRandom access （随机存取）lWasteful of space (dynamic storage-allocation problem)lFiles cannot growOperating System.School of Softw
10、are. HUSTContiguous Allocation of Disk Space (P421)Operating System.School of Software. HUSTExtent-Based Systems (P423)lMany newer file systems (I.e. Veritas File System) use a modified contiguous allocation scheme.lExtent-based file systems allocate disk blocks in extents.lAn extent is a contiguous
11、 block of disks.nExtents are allocated for file allocationnA file consists of one or more extents.Operating System.School of Software. HUSTLinked Allocation (P423)lEach file is a linked list of disk blocks: blocks may be scattered(分散) anywhere on the disk.pointerblock =Operating System.School of Sof
12、tware. HUSTLinked Allocation (Cont.) (P423)lEach file is a linked list of disk blocks;lThe blocks may be scattered anywhere on the disk.lEach block contains a pointer to the next block.lSimple need only starting address.lFree-space management system no waste of space .Operating System.School of Soft
13、ware. HUSTLinked Allocation (P424)Operating System.School of Software. HUSTLinked Allocation (Cont.) (P424)Disadvantages of Linked Allocation: (Detail-P424)lNo random accesslSpace required for the pointers.lreliabilityOperating System.School of Software. HUSTFile-Allocation Table (P425)File-allocati
14、on table (FAT) disk-space allocation used by MS-DOS and OS/2.lThe directory entry contains the block number of the first block of the file.lThe table entry indexed by that block number contains the block number of the next block in the file.Operating System.School of Software. HUSTFile-Allocation Ta
15、ble (P425)Operating System.School of Software. HUSTFile-Allocation Table (P425)lResult in a significant number of disk head seeks, unless the FAT is cached.lA benefit is that random-access time is improved.Operating System.School of Software. HUSTIndexed Allocation (P425)lBrings all pointers togethe
16、r into the index block.lLogical view.index tableOperating System.School of Software. HUSTExample of Indexed Allocation (P426)Operating System.School of Software. HUSTCombined Scheme: UNIX (4K bytes per block) (P428)Operating System.School of Software. HUSTFree-Space Management (P429)lBit vector (n blocks)012n-1biti =0 blocki occupied1 blocki freel Bit map requires extra space. Example: block size = 212 bytes disk size = 230 bytes 字节 (1 gigab
