Please enable JavaScript.
Coggle requires JavaScript to display documents.
File System Implementation (Free-Space Management (Space Maps (Used in ZFS…
File System Implementation
File-System Structure
Disk provides in-place rewrite and random access
File control block
File structure
Logical storage unit
Collection of related information
Device driver
File system resides on secondary storage (disks)
Provides efficient and convenient access to disk by allowing data to be stored, located retrieved easily
Provided user interface to storage, mapping logical to physical
File system organized into layers
File System Layers
Device drivers
manage I/O devices at the I/O control layer
Basic file system
File organization module understands files, logical address, and physical blocks
Translates logical block # to physical block #
Manages free space, disk allocation
Logical file system manages metadata information
Translates file name into file number, file handle, location by maintaining file control blocks
Directory management
Protection
In-Memory File System Structures
Plus buffers hold data blocks from secondary storage
Open returns a file handle for subsequent use
The following figure illustrates the necessary file system structures provided by the operating systems
Data from read eventually copied to specified user process memory address
Mount table storing file system mounts, mount points, file system types
Partitions and Mounting
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
Root partition contains the OS
Mounted at boot time
Other partitions can mount automatically or manually
Partition can be a volume containing a file system
Virtual File Systems
Allows the same system call interface
Separates file-system generic operations from implementation details
Implementation can be one of many file systems types, or network file system
Then dispatches operation to appropriate file system implementation routines
Provide an object-oriented way of implementing file systems
Directory Implementation
Linear list of file names with pointer to the data blocks
Time-consuming to execute
Simple to program
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
Allocation Methods
Contiguous allocation
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
Extent-Based Systems
Extent-based file systems allocate disk blocks in extents
contiguous block of disks
Extents are allocated for file allocation
A file consists of one or more extents
Linked
No external fragmentation
Each block contains pointer to next block
File ends at nil pointer
No compaction, external fragmentation
Free space management system called when new block needed
Reliability can be a problem
Locating a block can take many I/Os and disk seeks
Indexed
Need index table
Random access
Each file has its own index block(s) of pointers to its data blocks
Dynamic access without external fragmentation, but have overhead of index block
Performance
Linked good for sequential, not random
Declare access type at creation
Best method depends on file access type
Indexed more complex
Adding instructions to the execution path to save one disk I/O is reasonable
Free-Space Management
Bit vector or bit map
Bit map requires extra space
File system maintains free-space list to track available blocks/clusters
Easy to get contiguous files
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
Counting
Because space is frequently contiguously used and freed, with contiguous-allocation allocation, extents, or clustering
Space Maps
Used in ZFS
Consider meta-data I/O on very large file systems
Divides device space into metaslab units and manages metaslabs
Each metaslab has associated space map
But records to log file rather than file system
Efficiency and Performance
Performance
Keeping data and metadata close together
Free-behind and read-ahead
Synchronous writes sometimes requested by apps or needed by OS
Reads frequently slower than writes
Buffer cache – separate section of main memory for frequently used blocks
Efficiency dependent
Types of data kept in file’s directory entry
Disk allocation and directory algorithms
Pre-allocation or as-needed allocation of metadata structures
Fixed-size or varying-size data structures
Cache
Page Cache
Routine I/O through the file system uses the buffer (disk) cache
caches pages rather than disk blocks using virtual memory techniques and addresses
Memory-mapped I/O uses a page cache
Unified Buffer Cache
uses the same page cache to cache both memory-mapped pages and ordinary file system I/O to avoid double caching
Recovery
Recover lost file or disk by restoring data from back
Use system programs to back up data from disk to another storage device
Consistency checking
NFS
An implementation and a specification of a software system for accessing remote files across LANs
The implementation is part of the Solaris and SunOS operating systems running on Sun workstations using an unreliable datagram protocol
Interconnected workstations viewed as a set of independent machines with independent file systems
A remote directory is mounted over a local file system directory
Specification of the remote directory for the mount operation is nontransparent
Subject to access-rights accreditation, potentially any file system