CSMC 412Operating SystemsProf. Ashok K Agrawala© 2006 Ashok AgrawalaSet 11October 2006 1CMSC 412 Set 11File System Implementation• File-System Structure• File-System Implementation • Directory Implementation• Allocation Methods• Free-Space Management • Efficiency and Performance• Recovery• Log-Structured File Systems• NFS• Example: WAFL File SystemOctober 2006 2CMSC 412 Set 11Objectives• To describe the details of implementing local file systems and directory structures• To describe the implementation of remote file systems• To discuss block allocation and free-block algorithms and trade-offsOctober 2006 3CMSC 412 Set 11File-System Structure• File structure– Logical storage unit– Collection of related information• File system resides on secondary storage (disks)• File system organized into layers• File control block – storage structure consisting of information about a fileOctober 2006 4CMSC 412 Set 11Layered File SystemOctober 2006 5CMSC 412 Set 11A Typical File Control BlockOctober 2006 6CMSC 412 Set 11In-Memory File System Structures• The following figure illustrates the necessary file system structures provided by the operating systems.• Figure 12-3(a) refers to opening a file.• Figure 12-3(b) refers to reading a file.October 2006 7CMSC 412 Set 11In-Memory File System StructuresOctober 2006 8CMSC 412 Set 11Virtual File Systems• Virtual File Systems (VFS) provide an object-oriented way of implementing file systems.• VFS allows the same system call interface (the API) to be used for different types of file systems.• The API is to the VFS interface, rather than any specific type of file system.October 2006 9CMSC 412 Set 11Schematic View of Virtual File SystemOctober 2006 10CMSC 412 Set 11Directory Implementation• Linear list of file names with pointer to the data blocks.– simple to program– time-consuming to execute• Hash Table – linear list with hash data structure.– decreases directory search time– collisions – situations where two file names hash to the same location– fixed sizeOctober 2006 11CMSC 412 Set 11Allocation Methods• An allocation method refers to how disk blocks are allocated for files:• Contiguous allocation• Linked allocation• Indexed allocationOctober 2006 12CMSC 412 Set 11Contiguous Allocation• Each file occupies a set of contiguous blocks on the disk• Simple – only starting location (block #) and length (number of blocks) are required• Random access• Wasteful of space (dynamic storage-allocation problem)• Files cannot growOctober 2006 13CMSC 412 Set 11Contiguous Allocation• Mapping from logical to physicalLA/512QRBlock to be accessed = ! + starting addressDisplacement into block = ROctober 2006 14CMSC 412 Set 11Contiguous Allocation of Disk SpaceOctober 2006 15CMSC 412 Set 11Extent-Based Systems• Many newer file systems (I.e. Veritas File System) use a modified contiguous allocation scheme• Extent-based file systems allocate disk blocks in extents• An extent is a contiguous block of disks– Extents are allocated for file allocation– A file consists of one or more extents.October 2006 16CMSC 412 Set 11Linked Allocation• Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.pointerblock =October 2006 17CMSC 412 Set 11Linked Allocation (Cont.)• Simple – need only starting address• Free-space management system – no waste of space • No random access• MappingBlock to be accessed is the Qth block in the linked chain of blocks representing the file.Displacement into block = R + 1File-allocation table (FAT) – disk-space allocation used by MS-DOS and OS/2.LA/511QROctober 2006 18CMSC 412 Set 11Linked AllocationOctober 2006 19CMSC 412 Set 11File-Allocation TableOctober 2006 20CMSC 412 Set 11Indexed Allocation• Brings all pointers together into the index block.• Logical view.index tableOctober 2006 21CMSC 412 Set 11Example of Indexed AllocationOctober 2006 22CMSC 412 Set 11Indexed Allocation (Cont.)• Need index table• Random access• Dynamic access without external fragmentation, but have overhead of index block.• Mapping from logical to physical in a file of maximum size of 256K words and block size of 512 words. We need only 1 block for index table.LA/512QRQ = displacement into index tableR = displacement into blockOctober 2006 23CMSC 412 Set 11Indexed Allocation – Mapping (Cont.)• Mapping from logical to physical in a file of unbounded length (block size of 512 words).• Linked scheme – Link blocks of index table (no limit on size).LA / (512 x 511)Q1R1Q1= block of index tableR1is used as follows:R1/ 512Q2R2Q2= displacement into block of index tableR2displacement into block of file:October 2006 24CMSC 412 Set 11Indexed Allocation – Mapping (Cont.)• Two-level index (maximum file size is 5123)LA / (512 x 512)Q1R1Q1= displacement into outer-indexR1is used as follows:R1/ 512Q2R2Q2= displacement into block of index tableR2displacement into block of file:October 2006 25CMSC 412 Set 11Indexed Allocation – Mapping (Cont.)outer-indexindex tablefileOctober 2006 26CMSC 412 Set 11Combined Scheme: UNIX (4K bytes per block)October 2006 27CMSC 412 Set 11Free-Space Management• Bit vector (n blocks)…0 1 2 n-1bit[i] = 0 block[i] free1 block[i] occupiedBlock number calculation(number of bits per word) *(number of 0-value words) +offset of first 1 bitOctober 2006 28CMSC 412 Set 11Free-Space Management (Cont.)• Bit map requires extra space– Example:block size = 212bytesdisk size = 230bytes (1 gigabyte)n = 230/212= 218bits (or 32K bytes)• Easy to get contiguous files • Linked list (free list)– Cannot get contiguous space easily– No waste of space• Grouping • CountingOctober 2006 29CMSC 412 Set 11Free-Space Management (Cont.)• Need to protect:– Pointer to free list– Bit map• Must be kept on disk• Copy in memory and disk may differ• Cannot allow for block[i] to have a situation where bit[i] = 1 in memory and bit[i] = 0 on disk– Solution:• Set bit[i] = 1 in disk• Allocate block[i]• Set bit[i] = 1 in memoryOctober 2006 30CMSC 412 Set 11Directory Implementation• Linear list of file names with pointer to the data blocks– simple to program– time-consuming to execute• Hash Table – linear list with hash data structure– decreases directory search time– collisions – situations where two file names hash to the same location– fixed
View Full Document
Unlocking...