File System Implementation

Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018
 Outline

§ File-System Structure
§ File-System Operations
§ Directory Implementation
§ Allocation Methods
§ Free-Space Management
§ Efficiency and Performance
§ Recovery

Operating System Concepts – 10th Edition 14.2 Silberschatz, Galvin and Gagne ©2018
 Objectives

§ Describe the details of implementing local file systems and

directory 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

Operating System Concepts – 10th Edition 14.3 Silberschatz, Galvin and Gagne ©2018
 File-System Structure
§ File structure
• Logical storage unit
• Collection of related information
§ File system resides on secondary storage (disks)
• Provided user interface to storage, mapping logical to physical
• Provides efficient and convenient access to disk by allowing
data to be stored, located retrieved easily
§ Disk 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
information about a file
§ Device driver controls the physical device
§ File system organized into layers

Operating System Concepts – 10th Edition 14.4 Silberschatz, Galvin and Gagne ©2018
 Layered File System

Operating System Concepts – 10th Edition 14.5 Silberschatz, 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, sector 10,
into memory location 1060” outputs low-level hardware specific
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 data
§ File organization module understands files, logical address, and
physical blocks
§ Translates logical block # to physical block #
§ Manages free space, disk allocation

Operating System Concepts – 10th Edition 14.6 Silberschatz, Galvin and Gagne ©2018
 File System Layers (Cont.)

§ Logical file system manages metadata information

• Translates file name into file number, file handle, location
by maintaining file control blocks (inodes in UNIX)
• Directory management
• Protection
§ Layering useful for reducing complexity and redundancy, but
adds overhead and can decrease performance
§ Logical layers can be implemented by any coding method
according to OS designer

Operating System Concepts – 10th Edition 14.7 Silberschatz, Galvin and Gagne ©2018
 File System Layers (Cont.)

§ Many file systems, sometimes many within an operating system

• Each with its own format (CD-ROM is ISO 9660; Unix has UFS,
FFS; Windows has FAT, FAT32, NTFS as well as floppy, CD,
DVD Blu-ray, Linux has more than 130 types, with extended file
system ext3 and ext4 leading; plus distributed file systems, etc.)
• New ones still arriving – ZFS, GoogleFS, Oracle ASM, FUSE

Operating System Concepts – 10th Edition 14.8 Silberschatz, Galvin and Gagne ©2018
 File-System Operations

§ We have system calls at the API level, but how do we implement their
functions?
• On-disk and in-memory structures
§ Boot control block contains info needed by system to boot OS from
that volume
• Needed if volume contains OS, usually first block of volume
§ Volume control block (superblock, master file table) contains
volume details
• Total # of blocks, # of free blocks, block size, free block pointers or
array
§ Directory structure organizes the files
• Names and inode numbers, master file table

Operating System Concepts – 10th Edition 14.9 Silberschatz, Galvin and Gagne ©2018
 File-System Implementation (Cont.)

§ Per-file File Control Block (FCB) contains many details about

the file
• typically inode number, permissions, size, dates
• NFTS stores into in master file table using relational DB
structures

Operating System Concepts – 10th Edition 14.10 Silberschatz, Galvin and Gagne ©2018
 In-Memory File System Structures

§ Mount table storing file system mounts, mount points, file system
types
§ system-wide open-file table contains a copy of the FCB of each file
and other info
§ per-process open-file table contains pointers to appropriate entries
in system-wide open-file table as well as other info
§ 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
§ Plus buffers hold data blocks from secondary storage
§ Open returns a file handle for subsequent use
§ Data from read eventually copied to specified user process memory
address

Operating System Concepts – 10th Edition 14.11 Silberschatz, Galvin and Gagne ©2018
 In-Memory File System Structures

Operating System Concepts – 10th Edition 14.12 Silberschatz, Galvin and Gagne ©2018
 Directory Implementation

§ Linear list of file names with pointer to the data blocks

• Simple to program
• Time-consuming to execute
4 Linear search time
4 Could keep ordered alphabetically via linked list or use B+
tree
§ Hash Table – linear list with hash data structure
• Decreases directory search time
• Collisions – situations where two file names hash to the same
location
• Only good if entries are fixed size, or use chained-overflow
method

Operating System Concepts – 10th Edition 14.13 Silberschatz, Galvin and Gagne ©2018
 Allocation Methods - Contiguous

§ An allocation method refers to how disk blocks are allocated for files:
§ Contiguous allocation – each file occupies set of contiguous blocks
• Best performance in most cases
• Simple – only starting location (block #) and length (number of
blocks) are required
• Problems include finding space for file, knowing file size, external
fragmentation, need for compaction off-line (downtime) or on-
line

Operating System Concepts – 10th Edition 14.14 Silberschatz, Galvin and Gagne ©2018
 Contiguous Allocation

§ Mapping from logical to physical

Operating System Concepts – 10th Edition 14.15 Silberschatz, Galvin and Gagne ©2018
 Extent-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

Operating System Concepts – 10th Edition 14.16 Silberschatz, 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 block needed
• Improve efficiency by clustering blocks into groups but increases
internal fragmentation
• Reliability can be a problem
• Locating a block can take many I/Os and disk seeks

Operating System Concepts – 10th Edition 14.17 Silberschatz, Galvin and Gagne ©2018
 Linked Allocation

Operating System Concepts – 10th Edition 14.19 Silberschatz, Galvin and Gagne ©2018
 File-Allocation Table

Operating System Concepts – 10th Edition 14.20 Silberschatz, Galvin and Gagne ©2018
 Allocation Methods - Indexed
§ Indexed allocation
• Each file has its own index block(s) of pointers to its data blocks

§ Logical view

index table

Operating System Concepts – 10th Edition 14.21 Silberschatz, Galvin and Gagne ©2018
 Example of Indexed Allocation

Operating System Concepts – 10th Edition 14.22 Silberschatz, Galvin and Gagne ©2018
 Combined Scheme: UNIX UFS
4K bytes per block, 32-bit addresses

More index blocks than can be addressed with 32-bit file pointer

Operating System Concepts – 10th Edition 14.27 Silberschatz, 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 data
block read
• Clustering can help improve throughput, reduce CPU overhead
§ For NVM, no disk head so different algorithms and optimizations
needed
• Using old algorithm uses many CPU cycles trying to avoid non-
existent head movement
• With NVM goal is to reduce CPU cycles and overall path needed
for I/O

Operating System Concepts – 10th Edition 14.28 Silberschatz, Galvin and Gagne ©2018
 Free-Space Management

§ File system maintains free-space list to track available

blocks/clusters
• (Using term “block” for simplicity)
§ Bit vector or bit map (n blocks)
0 1 2 n-1
…
!"#
1 Þ block[i] free
bit[i] =
0 Þ block[i] occupied

Operating System Concepts – 10th Edition 14.30 Silberschatz, Galvin and Gagne ©2018
 Free-Space Management (Cont.)

§ Bit map requires extra space

• Example:
block size = 4KB = 212 bytes
disk size = 240 bytes (1 terabyte)
n = 240/212 = 228 bits (or 32MB)
if clusters of 4 blocks -> 8MB of memory

§ Easy to get contiguous files

Operating System Concepts – 10th Edition 14.31 Silberschatz, Galvin and Gagne ©2018
 Linked Free Space List on Disk

§ Linked list (free list)

• Cannot get contiguous
space easily
• No waste of space
• No need to traverse the
entire list (if # free
blocks recorded)

Operating System Concepts – 10th Edition 14.32 Silberschatz, Galvin and Gagne ©2018