Chapter 14: File System Implementation

Chapter 14: File SystemImplementationOperating System Concepts – 10th EditionSilberschatz, Galvin and Gagne 2018

Chapter 14: File System Implementation File-System Structure File-System Operations Directory Implementation Allocation Methods Free-Space Management Efficiency and Performance Recovery Example: WAFL File SystemOperating System Concepts – 10th Edition14.2Silberschatz, Galvin and Gagne 2018

Objectives Describe the details of implementing local file systems anddirectory structures Discuss block allocation and free-block algorithms and trade-offs Explore file system efficiency and performance issues Look at recovery from file system failures Describe the WAFL file system as a concrete exampleOperating System Concepts – 10th Edition14.3Silberschatz, Galvin and Gagne 2018

File-System Structure File structure Logical storage unit Collection of related informationFile system resides on secondary storage (disks) Provided user interface to storage, mapping logical to physical Provides efficient and convenient access to disk by allowing datato be stored, located retrieved easilyDisk provides in-place rewrite and random access I/O transfers performed in blocks of sectors (usually 512 bytes) File control block (FCB) – storage structure consisting of informationabout a file Device driver controls the physical device File system organized into layersOperating System Concepts – 10th Edition14.4Silberschatz, Galvin and Gagne 2018

Layered File SystemOperating System Concepts – 10th Edition14.5Silberschatz, Galvin and Gagne 2018

File System Layers Device drivers manage I/O devices at the I/O control layer Given commands like “read drive1, cylinder 72, track 2, sector10, into memory location 1060” outputs low-level hardwarespecific commands to hardware controller Basic file system given command like “retrieve block 123”translates to device driver Also manages memory buffers and caches (allocation, freeing,replacement) Buffers hold data in transit Caches hold frequently used dataFile organization module understands files, logical address, andphysical blocks Translates logical block # to physical block # Manages free space, disk allocationOperating System Concepts – 10th Edition14.6Silberschatz, Galvin and Gagne 2018

File System Layers (Cont.) Logical file system manages metadata information Translates file name into file number, file handle, location bymaintaining file control blocks (inodes in UNIX) Directory management ProtectionLayering useful for reducing complexity and redundancy, butadds overhead and can decrease performanceTranslates filename into file number, file handle, location by maintaining filecontrol blocks (inodes in UNIX) Logical layers can be implemented by any coding methodaccording to OS designerOperating System Concepts – 10th Edition14.7Silberschatz, Galvin and Gagne 2018

File System Layers (Cont.) Many file systems, sometimes many within an operatingsystem Each with its own format (CD-ROM is ISO 9660; Unix hasUFS, FFS; Windows has FAT, FAT32, NTFS as well asfloppy, CD, DVD Blu-ray, Linux has more than 130 types,with extended file system ext3 and ext4 leading; plusdistributed file systems, etc.) New ones still arriving – ZFS, GoogleFS, Oracle ASM,FUSEOperating System Concepts – 10th Edition14.8Silberschatz, Galvin and Gagne 2018

File-System Operations We have system calls at the API level, but how do we implementtheir functions? Boot control block contains info needed by system to boot OSfrom that volume Needed if volume contains OS, usually first block of volumeVolume control block (superblock, master file table) containsvolume details On-disk and in-memory structuresTotal # of blocks, # of free blocks, block size, free blockpointers or arrayDirectory structure organizes the files Names and inode numbers, master file tableOperating System Concepts – 10th Edition14.9Silberschatz, Galvin and Gagne 2018

File-System Implementation (Cont.) Per-file File Control Block (FCB) contains many details aboutthe file typically inode number, permissions, size, dates NFTS stores into in master file table using relational DBstructuresOperating System Concepts – 10th Edition14.10Silberschatz, Galvin and Gagne 2018

In-Memory File System Structures Mount table storing file system mounts, mount points, file systemtypes system-wide open-file table contains a copy of the FCB of eachfile and other info per-process open-file table contains pointers to appropriateentries in system-wide open-file table as well as other info The following figure illustrates the necessary file system structuresprovided by the operating systems Figure 12-3(a) refers to opening a file Figure 12-3(b) refers to reading a file Plus buffers hold data blocks from secondary storage Open returns a file handle for subsequent use Data from read eventually copied to specified user processmemory addressOperating System Concepts – 10th Edition14.11Silberschatz, Galvin and Gagne 2018

In-Memory File System StructuresOperating System Concepts – 10th Edition14.12Silberschatz, Galvin and Gagne 2018

Directory Implementation Linear list of file names with pointer to the data blocks Simple to program Time-consuming to execute Linear search timeCould keep ordered alphabetically via linked list or useB treeHash Table – linear list with hash data structure Decreases directory search time Collisions – situations where two file names hash to thesame location Only good if entries are fixed size, or use chained-overflowmethodOperating System Concepts – 10th Edition14.13Silberschatz, Galvin and Gagne 2018

Allocation Methods - Contiguous An allocation method refers to how disk blocks are allocated forfiles: Contiguous allocation – each file occupies set of contiguousblocks Best performance in most cases Simple – only starting location (block #) and length (numberof blocks) are required Problems include finding space for file, knowing file size,external fragmentation, need for compaction off-line(downtime) or on-lineOperating System Concepts – 10th Edition14.14Silberschatz, Galvin and Gagne 2018

Contiguous Allocation Mapping from logical to physicalQLA/512RBlock to be accessed Q startingaddressDisplacement into block ROperating System Concepts – 10th Edition14.15Silberschatz, Galvin and Gagne 2018

Extent-Based Systems Many newer file systems (i.e., Veritas File System) use amodified 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 extentsOperating System Concepts – 10th Edition14.16Silberschatz, Galvin and Gagne 2018

Allocation Methods - Linked Linked allocation – each file a linked list of blocks File ends at nil pointer No external fragmentation Each block contains pointer to next block No compaction, external fragmentation Free space management system called when new blockneeded Improve efficiency by clustering blocks into groups butincreases internal fragmentation Reliability can be a problem Locating a block can take many I/Os and disk seeksOperating System Concepts – 10th Edition14.17Silberschatz, Galvin and Gagne 2018

Linked Allocation Each file is a linked list of disk blocks: blocks may be scatteredanywhere on the diskblock pointerMappingLA/511QRBlock to be accessed is the Qth block in the linked chain of blocksrepresenting the file.Displacement into block R 1Operating System Concepts – 10th Edition14.19Silberschatz, Galvin and Gagne 2018

Linked AllocationOperating System Concepts – 10th Edition14.20Silberschatz, Galvin and Gagne 2018

File-Allocation TableOperating System Concepts – 10th Edition14.21Silberschatz, Galvin and Gagne 2018

Allocation Methods - Indexed Indexed allocation Each file has its own index block(s) of pointers to its data blocksLogical viewindex tableOperating System Concepts – 10th Edition14.22Silberschatz, Galvin and Gagne 2018

Example of Indexed AllocationOperating System Concepts – 10th Edition14.23Silberschatz, Galvin and Gagne 2018

Combined Scheme: UNIX UFS4K bytes per block, 32-bit addressesMore index blocks than can be addressed with 32-bit file pointerOperating System Concepts – 10th Edition14.28Silberschatz, Galvin and Gagne 2018

Performance Best method depends on file access type Contiguous great for sequential and random Linked good for sequential, not random Declare access type at creation - select either contiguous or linked Indexed more complex Single block access could require 2 index block reads then datablock read Clustering can help improve throughput, reduce CPU overheadFor NVM, no disk head so different algorithms and optimizationsneeded Using old algorithm uses many CPU cycles trying to avoid nonexistent head movement With NVM goal is to reduce CPU cycles and overall path neededfor I/OOperating System Concepts – 10th Edition14.29Silberschatz, Galvin and Gagne 2018

Free-Space Management File system maintains free-space list to track available blocks/clusters Bit vector or bit map (n blocks) (Using term “block” for simplicity)0 12n-1bit[i] 1 block[i] free0 block[i] occupiedBlock number calculation(number of bits per word) *(number of 0-value words) offset of first 1 bitCPUs have instructions to return offset within word of first “1” bitOperating System Concepts – 10th Edition14.31Silberschatz, Galvin and Gagne 2018

Free-Space Management (Cont.) Bit map requires extra space Example:block size 4KB 212 bytesdisk size 240 bytes (1 terabyte)n 240/212 228 bits (or 32MB)if clusters of 4 blocks - 8MB of memory Easy to get contiguous filesOperating System Concepts – 10th Edition14.32Silberschatz, Galvin and Gagne 2018

Linked Free Space List on Disk Linked list (free list) Cannot get contiguousspace easily No waste of space No need to traverse theentire list (if # free blocksrecorded)Operating System Concepts – 10th Edition14.33Silberschatz, Galvin and Gagne 2018

Free-Space Management (Cont.) Grouping Modify linked list to store address of next n-1 free blocks in firstfree block, plus a pointer to next block that contains free-blockpointers (like this one)Counting Because space is frequently contiguously used and freed, withcontiguous-allocation allocation, extents, or clustering Keep address of first free block and count of following freeblocksFree space list then has entries containing addresses andcountsOperating System Concepts – 10th Edition14.34Silberschatz, Galvin and Gagne 2018

Free-Space Management (Cont.) Space Maps Used in ZFS Consider meta-data I/O on very large file systems Divides device space into metaslab units and manages metaslabs Uses counting algorithmBut records to log file rather than file system Given volume can contain hundreds of metaslabsEach metaslab has associated space map Full data structures like bit maps couldn’t fit in memory - thousands of I/OsLog of all block activity, in time order, in counting formatMetaslab activity - load space map into memory in balanced-treestructure, indexed by offset Replay log into that structure Combine contiguous free blocks into single entryOperating System Concepts – 10th Edition14.35Silberschatz, Galvin and Gagne 2018

TRIMing Unused Blocks HDDS overwrite in place so need only free list Blocks not treated specially when freed Keeps its data but without any file pointers to it, until overwrittenStorage devices not allowing overwrite (like NVM) suffer badly with samealgorithm Must be erased before written, erases made in large chunks (blocks,composed of pages) and are slow TRIM is a newer mechanism for the file system to inform the NVMstorage device that a page is free Can be garbage collected or if block is free, now block can beerasedOperating System Concepts – 10th Edition14.36Silberschatz, Galvin and Gagne 2018