Chapter 5B: File System

Implementation

Operating System Concepts– 8th Edition Silberschatz, Galvin and Gagne ©2009
 Chapter 11: File System Implementation
● File-System Structure
● File-System Implementation
● Directory Implementation
● Allocation Methods
● Free-Space Management
● Efficiency and Performance
● Recovery
● NFS
● Example: WAFL File System

Operating System Concepts – 8th Edition 11.2 Silberschatz, Galvin and Gagne ©2009
 Objectives
● 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-offs

Operating System Concepts – 8th Edition 11.3 Silberschatz, Galvin and Gagne ©2009
 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 – storage structure consisting of information about a file
● Device driver controls the physical device
● File system organized into layers

Operating System Concepts – 8th Edition 11.4 Silberschatz, Galvin and Gagne ©2009
 Layered File System

Operating System Concepts – 8th Edition 11.5 Silberschatz, Galvin and Gagne ©2009
 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 – 8th Edition 11.6 Silberschatz, Galvin and Gagne ©2009
 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
● 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 40 types, with extended file system ext2 and ext3
leading; plus distributed file systems, etc)
● New ones still arriving – ZFS, GoogleFS, Oracle ASM, FUSE

Operating System Concepts – 8th Edition 11.7 Silberschatz, Galvin and Gagne ©2009
 File-System Implementation
● 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
● Per-file File Control Block (FCB) contains many details about the file
● Inode number, permissions, size, dates
● NFTS stores into in master file table using relational DB structures

Operating System Concepts – 8th Edition 11.8 Silberschatz, Galvin and Gagne ©2009
 A Typical File Control Block

Operating System Concepts – 8th Edition 11.9 Silberschatz, Galvin and Gagne ©2009
 In-Memory File System Structures
● Mount table storing file system mounts, mount points, file system types

● 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 – 8th Edition 11.10 Silberschatz, Galvin and Gagne ©2009
 In-Memory File System Structures

Operating System Concepts – 8th Edition 11.11 Silberschatz, Galvin and Gagne ©2009
 Partitions and Mounting
❖ Partition can be a volume containing a file system (“cooked”) or raw – just a sequence of
blocks with no file system
❖ Boot block can point to boot volume or boot loader set of blocks that contain enough
code to know how to load the kernel from the file system
➢ Or a boot management program for multi-os booting
❖ Root partition contains the OS, other partitions can hold other Oses, other file systems,
or be raw
➢ Mounted at boot time
➢ Other partitions can mount automatically or manually
❖ At mount time, file system consistency checked
➢ Is all metadata correct?
■ If not, fix it, try again
■ If yes, add to mount table, allow access

Operating System Concepts – 8th Edition 11.12 Silberschatz, Galvin and Gagne ©2009
 Virtual File Systems
● Virtual File Systems (VFS) on Unix 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
● Separates file-system generic operations from implementation details
● Implementation can be one of many file systems types, or network file system
4 Implements vnodes which hold inodes or network file details
● Then dispatches operation to appropriate file system implementation routines
● The API is to the VFS interface, rather than any specific type of file system

Operating System Concepts – 8th Edition 11.13 Silberschatz, Galvin and Gagne ©2009
 Schematic View of Virtual File System

Operating System Concepts – 8th Edition 11.14 Silberschatz, Galvin and Gagne ©2009
 Directory Implementation
❖ Linear list of file names with pointer to the data blocks
➢ Simple to program
➢ Time-consuming to execute
■ Linear search time
■ 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 – 8th Edition 11.15 Silberschatz, Galvin and Gagne ©2009
 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 – 8th Edition 11.16 Silberschatz, Galvin and Gagne ©2009
 Contiguous Allocation
● Mapping from logical to physical

LA/512

Block to be accessed = Q + starting address

Displacement into block = R

Operating System Concepts – 8th Edition 11.17 Silberschatz, Galvin and Gagne ©2009
 Contiguous Allocation of Disk Space

Operating System Concepts – 8th Edition 11.18 Silberschatz, Galvin and Gagne ©2009
 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
● FAT (File Allocation Table) variation
● Beginning of volume has table, indexed by block number
● Much like a linked list, but faster on disk and cacheable
● New block allocation simple

Operating System Concepts – 8th Edition 11.19 Silberschatz, Galvin and Gagne ©2009
 Linked Allocation
● Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk

block
pointer
=

Operating System Concepts – 8th Edition 11.20 Silberschatz, Galvin and Gagne ©2009
 Linked Allocation
● Mapping

Q
LA/51
1
R

Block to be accessed is the Qth block in the linked chain of blocks representing the file.
Displacement into block = R + 1

Operating System Concepts – 8th Edition 11.21 Silberschatz, Galvin and Gagne ©2009
 Linked Allocation

Operating System Concepts – 8th Edition 11.22 Silberschatz, Galvin and Gagne ©2009
 File-Allocation Table

Operating System Concepts – 8th Edition 11.23 Silberschatz, Galvin and Gagne ©2009
 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 – 8th Edition 11.24 Silberschatz, Galvin and Gagne ©2009
 Example of Indexed Allocation

Operating System Concepts – 8th Edition 11.25 Silberschatz, Galvin and Gagne ©2009
 Indexed 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 bytes and block size of 512 bytes.
We need only 1 block for index table

Q
LA/512
R

Q = displacement into index table

R = displacement into block

Operating System Concepts – 8th Edition 11.26 Silberschatz, Galvin and Gagne ©2009
 Indexed 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)

Q1
LA / (512 x 511)
R1
Q1 = block of index table
R1 is used as follows:

Q2
R1 / 512
R2
Q2 = displacement into block of index table
R2 displacement into block of file:

Operating System Concepts – 8th Edition 11.27 Silberschatz, Galvin and Gagne ©2009
 Indexed Allocation – Mapping (Cont.)
● Two-level index (4K blocks could store 1,024 four-byte pointers in outer index -> 1,048,567 data blocks and file
size of up to 4GB)

Q1
LA / (512 x 512)
R1

Q1 = displacement into outer-index

R1 is used as follows:

Q2
R1 / 512
R2
Q2 = displacement into block of index table
R2 displacement into block of file:

Operating System Concepts – 8th Edition 11.28 Silberschatz, Galvin and Gagne ©2009
 Indexed Allocation – Mapping (Cont.)

outer-index

index table file

Operating System Concepts – 8th Edition 11.29 Silberschatz, Galvin and Gagne ©2009
 Combined Scheme: UNIX UFS
(4K bytes per block, 32-bit addresses)
Note: More index
blocks than can
be addressed
with 32-bit file
pointer

Operating System Concepts – 8th Edition 11.30 Silberschatz, Galvin and Gagne ©2009
 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

Operating System Concepts – 8th Edition 11.31 Silberschatz, Galvin and Gagne ©2009
 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

Block number calculation

(number of bits per word) *

(number of 0-value words) +
offset of first 1 bit

CPUs have instructions to return offset within word of first “1” bit

Operating System Concepts – 8th Edition 11.32 Silberschatz, Galvin and Gagne ©2009
 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 256 MB)
if clusters of 4 blocks -> 64MB of memory

● Easy to get contiguous files

● 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 – 8th Edition 11.33 Silberschatz, Galvin and Gagne ©2009
 Linked Free Space List on Disk

Operating System Concepts – 8th Edition 11.34 Silberschatz, Galvin and Gagne ©2009
 Free-Space Management (Cont.)
● Grouping
● Modify linked list to store address of next n-1 free blocks in first free block, plus a pointer to next block that
contains free-block-pointers (like this one)

● Counting
● Because space is frequently contiguously used and freed, with contiguous-allocation allocation, extents, or
clustering
4 Keep address of first free block and count of following free blocks
4 Free space list then has entries containing addresses and counts

Operating System Concepts – 8th Edition 11.35 Silberschatz, Galvin and Gagne ©2009
 Efficiency and Performance
● Efficiency dependent on:
● Disk allocation and directory algorithms
● Types of data kept in file’s directory entry
● Pre-allocation or as-needed allocation of metadata structures
● Fixed-size or varying-size data structures

Operating System Concepts – 8th Edition 11.36 Silberschatz, Galvin and Gagne ©2009
 Efficiency and Performance (Cont.)

● Performance
● Keeping data and metadata close together
● Buffer cache – separate section of main memory for frequently used blocks
● Synchronous writes sometimes requested by apps or needed by OS
4 No buffering / caching – writes must hit disk before acknowledgement
4 Asynchronous writes more common, buffer-able, faster
● Free-behind and read-ahead – techniques to optimize sequential access
● Reads frequently slower than writes

Operating System Concepts – 8th Edition 11.37 Silberschatz, Galvin and Gagne ©2009
 Page Cache
● A page cache caches pages rather than disk blocks using virtual memory techniques and addresses

● Memory-mapped I/O uses a page cache

● Routine I/O through the file system uses the buffer (disk) cache

● This leads to the following figure

Operating System Concepts – 8th Edition 11.38 Silberschatz, Galvin and Gagne ©2009
 I/O Without a Unified Buffer Cache

Operating System Concepts – 8th Edition 11.39 Silberschatz, Galvin and Gagne ©2009
 Unified Buffer Cache
● A unified buffer cache uses the same page cache to cache both memory-mapped pages and ordinary
file system I/O to avoid double caching

● But which caches get priority, and what replacement algorithms to use?

Operating System Concepts – 8th Edition 11.40 Silberschatz, Galvin and Gagne ©2009
 I/O Using a Unified Buffer Cache

Operating System Concepts – 8th Edition 11.41 Silberschatz, Galvin and Gagne ©2009
 Recovery
● Consistency checking – compares data in directory structure with data blocks on disk, and tries to fix
inconsistencies
● Can be slow and sometimes fails

● Use system programs to back up data from disk to another storage device (magnetic tape, other
magnetic disk, optical)

● Recover lost file or disk by restoring data from backup

Operating System Concepts – 8th Edition 11.42 Silberschatz, Galvin and Gagne ©2009
 End of Chapter 5B

Operating System Concepts– 8th Edition Silberschatz, Galvin and Gagne ©2009
 Free-Space Management (Cont.)
● Need to protect:
● Pointer to free list
● Bit map
4 Must be kept on disk
4 Copy in memory and disk may differ
4 Cannot allow for block[i] to have a situation where bit[i] = 1 in memory and bit[i] = 0 on disk
● Solution:
4 Set bit[i] = 1 in disk
4 Allocate block[i]
4 Set bit[i] = 1 in memory

Operating System Concepts – 8th Edition 11.44 Silberschatz, Galvin and Gagne ©2009