File Systems
Open in the Padhaiko app5.1 File concepts: Name, structure, types, access, attributes, operations
A file is a named collection of correlated information recorded on non-volatile secondary storage (such as an SSD, magnetic disk, or tape). From the user's perspective, a file is the smallest logical unit of persistent storage: programs read inputs from files and write outputs to files without managing physical sectors or blocks directly.
The file system is the part of the operating system that manages files and directories. It provides a standardized I/O interface across diverse storage hardware, protects data against loss or unauthorized modification, and supports concurrent access by multiple users and processes.
File Naming
When a process creates a file, it assigns a name so that other processes can later locate and open it even after the creating process terminates.
File Naming Conventions
- Length and Characters: Modern operating systems typically support file names up to characters (older systems like MS-DOS restricted names to characters plus a -character extension). Digits and punctuation such as hyphens, underscores, or periods are permitted, while path separators (
/in UNIX/Linux,\in Windows) and null bytes are reserved. - Case Sensitivity: UNIX/Linux file systems are case-sensitive (
Report.txt,report.txt, andREPORT.TXTdenote three distinct files), whereas Windows (FAT32/NTFS default) is case-preserving but case-insensitive (all three refer to the same file). - Extensions: A suffix following a dot (e.g.,
.c,.pdf,.exe) indicates the file's format or intended application. UNIX treats extensions mainly as conventions, whereas Windows associates them with default applications.
File Structure
Operating systems structure files internally in one of three logical ways:
| Structure | Organization | Characteristics & Use Cases |
|---|---|---|
| Byte Sequence | Unstructured stream of bytes | Used by UNIX/Linux and Windows; the OS imposes no internal format, giving user programs complete flexibility. |
| Record Sequence | Sequence of fixed-length records | Historically used for punch-card readers and line printers (e.g., CP/M -byte records); read/write operations transfer one record at a time. |
| Tree | Hierarchy of variable-length records sorted by a key field | Used in mainframe data-processing systems; supports fast key-based searching and insertion. |
File Types
To prevent inappropriate operations (such as executing a plain text document or writing to a directory as raw data), operating systems classify files into distinct types:
Categories of Files (UNIX and Windows)
- Ordinary (Regular) Files: Contain user data, source code, documents, databases, or compiled binary executables. Users can create, read, modify, append, and delete them.
- ASCII / Text files: Lines of readable characters editable by standard text tools.
- Binary files: Internal byte sequences structured for specific programs (e.g., object code, executables with magic numbers).
- Directory Files: System-managed files that hold mappings from human-readable file names to their underlying file identifiers (such as i-node numbers or starting block addresses).
- Special (Device) Files: Represent physical or virtual I/O devices so programs can interact with hardware using standard file operations (
open,read,write):- Character special files: Transfer data one character (byte) at a time—used for serial ports, keyboards, terminals, and printers.
- Block special files: Transfer data in fixed-size blocks—used for disks, SSDs, and tape drives.
File Access Methods
Files store information that must later be retrieved into memory. Two primary access patterns exist:
| Aspect | Sequential Access | Random (Direct) Access |
|---|---|---|
| Access Order | Bytes or records are read strictly in order from start to finish; skipping ahead requires reading or rewinding past earlier data | Any byte offset or record can be read or written directly out of order |
| Typical Medium | Originally designed for magnetic tapes | Designed for magnetic disks and SSDs |
| Positioning | Automatic internal pointer advances on every read/write | Explicit seek operation moves the file pointer to a target byte offset or key |
| Applications | Streaming logs, compilers reading source files, tape backups | Databases, airline reservation systems, indexed file lookups |
File Attributes
In addition to its name and data payload, every file has metadata called file attributes maintained by the file system:
| Attribute | Purpose |
|---|---|
| Name | Symbolic identifier in human-readable form. |
| Identifier | Unique numeric tag (e.g., i-node number) used internally by the OS. |
| Type | Distinguishes regular files, directories, device files, or symbolic links. |
| Location | Pointer to the device and physical disk blocks holding the file. |
| Size | Current length of the file in bytes (and allocated block count). |
| Protection | Access-control flags (read, write, execute) for owner, group, and others. |
| Timestamps & Flags | Creation, last modification, and last access times, plus OS flags (hidden, read-only, archive, system). |
File Operations
An operating system exposes system calls to create, manipulate, and destroy files safely:
Fundamental File Operations
Create: Allocates metadata/directory entry for a new empty file without data.Delete: Removes the directory entry and reclaims allocated disk blocks when the file is no longer needed.Open: Locates the file by path, verifies permissions, and loads its attributes/block locations into an in-memory open-file table, returning a file descriptor/handle.Close: Flushes buffered modifications and frees the open-file table entry once access finishes.Read: Copies bytes from the current file position into a process buffer and advances the pointer.Write: Writes data from a buffer at the current file position, overwriting or extending the file.Append: Restricted write that adds data strictly at the end of the file.Seek: Repositions the file pointer to a specified offset without transferring data, enabling random access.Get Attributes/Set Attributes: Reads or updates metadata such as permissions and timestamps.Rename: Changes the file's directory name without copying its underlying data blocks.
5.2 Directory structures: Paths and hierarchies (Linux/Windows)
A directory is a symbol table that translates human-readable file names into internal file system references (such as i-node numbers or starting block pointers).
Single-Level vs. Hierarchical Directory Systems
| Aspect | Single-Level Directory | Hierarchical (Tree-Structured) Directory |
|---|---|---|
| Structure | One flat root directory holds every file on the volume | Tree of directories and subdirectories branching from a root |
| Naming Collisions | All files must have globally unique names—unusable for multi-user systems | Identical file names can coexist in different directories (e.g., /alice/lab.c and /bob/lab.c) |
| Organization | Simple and fast lookup for tiny file counts | Natural grouping by user, project, and purpose |
| Usage | Early systems (e.g., CDC 6600) and simple embedded devices (cameras, basic MP3 players) | All modern general-purpose OSs (Linux, Windows, macOS) |
Path Names: Absolute vs. Relative
In a directory tree, a file is uniquely identified by a path name—the sequence of directory names leading to it.
- Absolute Path Name: Starts at the root of the file system and traces every directory down to the target file. An absolute path is unambiguous regardless of where the user currently is.
- Relative Path Name: Interpreted relative to the process's current working directory (
.denotes the current directory;..denotes the parent directory). For example, if the working directory is/usr/ast, the relative pathmailboxrefers to/usr/ast/mailbox.
Linux vs. Windows Directory Hierarchies
| Feature | Linux (POSIX / VFS) | Windows (NTFS / Win32) |
|---|---|---|
| Root Concept | Single unified tree rooted at / (additional partitions/devices are mounted onto subdirectories such as /mnt or /home). | Per-drive trees identified by drive letters (C:\, D:\), each partition having its own root. |
| Path Separator | Forward slash (/) | Backslash (\), though Win32 APIs also accept / internally. |
| Absolute Path Example | /home/arya/docs/notes.txt | C:\Users\arya\Documents\notes.txt |
| Relative Path Example | ../docs/notes.txt | ..\Documents\notes.txt |
| Case Sensitivity | Case-sensitive (File.txt file.txt). | Case-insensitive by default (File.txt file.txt). |
| Standard Top-Level Layout | /bin, /etc, /home, /usr, /var, /dev, /tmp | C:\Windows, C:\Program Files, C:\Users |
5.3 File system implementation: Inodes, allocation methods (Contiguous, linked, indexed)
A disk is divided into partitions, each holding an independent file system. On traditional MBR disks, sector holds the Master Boot Record (MBR) and partition table; when booted, the MBR loads the boot block (first block of the active partition), which boots the OS. Immediately following is the superblock, containing key file system metadata (magic number identifying the file system type, total block count, free-block counts, and administrative parameters), followed by free-space bitmaps/lists, metadata structures (such as i-nodes), the root directory, and data blocks.
The central design problem in file system implementation is mapping each file to the disk blocks that store its data. Four classic allocation strategies exist:
1. Contiguous Allocation
Every file is stored as a single consecutive run of disk blocks. A directory entry needs only two numbers: the starting block address and the file length in blocks.
2. Linked List Allocation
Each disk block reserves its first word as a pointer to the next block of the file; the directory entry stores only the address of the first block (and optionally the last block).
3. Linked List Allocation Using a Table in Memory (FAT)
Both weaknesses of on-disk linked allocation are solved by moving all block pointers out of the disk blocks and placing them in an in-memory File Allocation Table (FAT) indexed by block number. Each entry holds the next block number in the chain, terminated by an end-of-file marker (e.g., or 0x0FFFFFFF).
- Advantages: The full disk block is available for user data (a clean power of two), and random access follows the pointer chain entirely in RAM with zero extra disk I/O before reading the target block.
- Disadvantages: The entire FAT must remain in main memory while the volume is mounted. As disk capacity grows, the table size grows linearly with the total number of blocks.
4. Indexed Allocation and I-Nodes
Instead of keeping a disk-wide block table in RAM, indexed allocation associates a per-file index structure with each file. In UNIX-style systems, this structure is called an i-node (index-node).
I-Node Architecture
An i-node is a fixed-size per-file data structure stored on disk that holds:
- File attributes: size, owner UID, group GID, permission mode bits, link count (number of directory entries pointing to this i-node), and timestamps (creation, last access, last modification).
- Direct block pointers: Disk addresses of the first data blocks (e.g., or direct blocks), allowing small files to be accessed without extra index lookups.
- Indirect block pointers (for large files):
- Single indirect block: Points to a disk block filled with addresses of data blocks.
- Double indirect block: Points to a block of addresses of single indirect blocks.
- Triple indirect block: Points to a block of addresses of double indirect blocks.
Because an i-node only needs to be loaded into memory while its file is open, if each i-node occupies bytes and at most files are open simultaneously, the OS reserves only bytes of RAM—independent of whether the disk is or .
| Aspect | FAT (Linked Table in RAM) | I-Node (Indexed Allocation) |
|---|---|---|
| RAM Usage | Proportional to total disk blocks (must stay in RAM for the whole disk) | Proportional to currently open files () |
| Random Access | pointer hops in RAM, then disk read | direct or – indirect block reads |
| Directory Entry | Stores file name, attributes, and starting block number | Stores just file name and i-node number (supports hard links) |
| Scalability | Poor for multi-terabyte volumes | Scales cleanly to very large disks and huge files via multi-level indirection |
5.4 File system performance: Factors affecting efficiency
Because mechanical disk access (milliseconds) is orders of magnitude slower than RAM access (nanoseconds), file systems rely on three primary optimizations to maximize throughput and reduce latency:
Core File System Performance Techniques
- Caching (Buffer / Block Cache): A pool of disk blocks kept in RAM. Every read checks the cache first via a hash table keyed by
(device, disk_address)(with collision chaining). Cache misses load the block from disk into the cache and place it on a doubly linked exact LRU (Least Recently Used) list so the least recently used block can be evicted (and written back if dirty) when space is needed. - Block Read-Ahead (Prefetching): When a file is read sequentially, after delivering block , the file system checks whether block is in the cache and asynchronously schedules a disk read for so it is ready before the process requests it. Read-ahead is disabled for random-access files because prefetching unused blocks wastes disk bandwidth and pollutes the cache.
- Reducing Disk-Arm Motion (Locality & Layout):
- Bitmap placement: Keeping a free-space bitmap in RAM lets the allocator pick a free block in the same cylinder as the previous block.
- Block clustering: Allocating storage in clusters of consecutive blocks (e.g., or sectors at a time) keeps sequential data contiguous.
- Cylinder groups: Rather than putting all i-nodes at the start of the disk (which forces long seeks between i-nodes and data), the disk is partitioned into cylinder groups, each with its own i-nodes, free-space bitmap, and data blocks so a file's i-node and data reside in the same group.
- SSD Considerations (Wear Leveling): Solid-state drives have no moving arm, making random reads as fast as sequential reads. However, flash blocks can endure only a finite number of program/erase cycles, so SSD controllers and flash-aware file systems apply wear leveling to distribute writes evenly across all physical blocks.
5.5 Example file systems: NTFS, EXT4, FAT32, NFS
Modern operating systems choose different file systems depending on whether the storage is removable media, a local OS volume, or a shared network drive.
FAT32 (File Allocation Table 32)
Evolved from the MS-DOS FAT file system (which used -byte fixed directory entries storing name, attributes—read-only, archive, hidden, system—timestamps, starting cluster, and size), FAT32 uses active bits per cluster entry (top bits reserved) in an in-memory/on-disk allocation table.
- Strengths: Extremely simple, lightweight, and universally supported across Windows, Linux, macOS, embedded devices, USB flash drives, and SD cards.
- Limits: Maximum single file size is ( bytes); no native journaling, POSIX/ACL permissions, or built-in encryption.
EXT4 (Fourth Extended File System)
The default local file system for most Linux distributions, descending from the UNIX i-node architecture (ext2 ext3 ext4):
- Extents: Replaces traditional single-block indirect maps with extent trees (describing contiguous runs of up to per extent with blocks), dramatically reducing metadata overhead and fragmentation for large files.
- Journaling: Writes metadata (and optionally data) changes to a circular journal before committing them in place, enabling rapid crash recovery without scanning the whole disk (
fsck). - Allocation Optimizations: Uses delayed allocation (buffers writes until flush time to allocate contiguous blocks) and multiblock allocation, supporting volumes up to and files up to (with blocks).
NTFS (New Technology File System)
The standard local file system of modern Windows operating systems:
- Master File Table (MFT): Everything—including metadata and the MFT itself—is stored as a file described by MFT records. Very small files fit directly inside the MFT record (resident attributes), eliminating separate data-block seeks; larger files store lists of contiguous data runs (extents).
- Reliability & Security: Features metadata journaling (via ), rich Access Control Lists (ACLs) per file/directory, built-in compression, Encrypting File System (EFS) support, hard/symbolic links, and Alternate Data Streams (ADS).
NFS (Network File System)
A distributed (network) file system originally developed by Sun Microsystems that lets client machines mount and access directories stored on remote servers transparently over a network (TCP/UDP, typically via RPC):
- Architecture: Uses a Virtual File System (VFS) layer on the client so local system calls (
open,read,write) forward remote operations to the NFS server transparently. - Statefulness & Caching: NFSv3 is stateless (each request carries full file handle and offset, simplifying server crash recovery), whereas NFSv4 is stateful (adds file locking, compound RPCs, stronger Kerberos security, and built-in caching delegations).
| Feature | FAT32 | EXT4 | NTFS | NFS |
|---|---|---|---|---|
| Primary Role | Removable media, EFI system partition | Linux local disk volumes | Windows local disk volumes | Network shared storage (client-server) |
| Core Metadata | File Allocation Table + -byte directory entries | I-nodes with extent trees | Master File Table (MFT) with data runs | Server's local FS exposed via RPC/VFS |
| Max File Size | ( blocks) | (implementation; format) | Depends on underlying server FS & protocol | |
| Journaling | No | Yes | Yes () | Delegated to server's local FS |
| Permissions / ACLs | Basic flags (Read-only, Hidden, System, Archive) | POSIX rwx + POSIX ACLs | Fine-grained Windows ACLs + EFS | UID/GID mapping (v3) / Kerberos + ACLs (v4) |
Worked Out Examples
5.1
A disk partition has a capacity of and uses a block size of . If the file system uses an in-memory File Allocation Table (FAT) where each block entry occupies , calculate the total number of blocks and the RAM required to hold the entire FAT.
Converting disk capacity and block size to bytes:
Calculating the total number of disk blocks:
Computing the memory required for the FAT: Each block requires one -byte entry in the table:
The partition contains () blocks, and the in-memory FAT occupies of RAM continuously while the volume is mounted.
5.2
A UNIX-style file system uses disk blocks and -byte disk block addresses. Each i-node contains direct block pointers, single indirect pointer, double indirect pointer, and triple indirect pointer. Determine the maximum possible file size supported by this i-node structure.
Finding how many block pointers fit inside one indirect block:
Counting addressable data blocks at each level:
- Direct pointers: blocks
- Single indirect pointer: blocks
- Double indirect pointer: blocks
- Triple indirect pointer: blocks
Converting total blocks to bytes and :
The maximum supported file size is blocks, which equals (approximately ).
5.3
Suppose a file has logical blocks (indexed to ), and its directory entry, FAT, or i-node is already loaded in main memory. How many disk block reads are required to access logical block under:
- Contiguous allocation
- Linked list allocation (pointers stored inside disk blocks)
- Linked list allocation using an in-memory FAT
- UNIX i-node allocation ( direct, single indirect, double indirect)
Contiguous allocation: Because blocks are consecutive starting at disk block , the target address is computed directly as . Only disk read is needed to fetch logical block .
On-disk linked list allocation: The directory entry holds only the disk address of logical block . To discover the pointer to block , the OS must read blocks sequentially from disk, and then read block itself:
In-memory FAT allocation: Traversing the chain from block to block takes pointer lookups strictly inside RAM (zero disk reads), followed by disk read to fetch logical block .
UNIX i-node allocation: Logical blocks through use the direct pointers. Block lies in the single indirect range (), so the OS performs disk read to load the single indirect block and disk read to fetch data block , totaling disk reads.
Disk reads required for logical block : Contiguous = , On-disk Linked = , In-memory FAT = , I-node = .
Exercises
Exercise — File Systems
Differentiate between ordinary files, directory files, and special (device) files (including character vs. block special files). Also compare sequential access and random access.
Classifying file types:
- Ordinary files store user data, text, databases, or executable binaries; processes can create, read, modify, and delete their contents.
- Directory files store tables mapping file names to file identifiers (i-node numbers or starting block addresses); the OS manages their internal format.
- Special files represent physical or virtual I/O devices as entries in the file hierarchy:
- Character special files stream data byte-by-byte (e.g., terminals, serial ports, printers).
- Block special files transfer data in fixed-size blocks (e.g., HDDs, SSDs, tape drives).
Comparing sequential vs. random access:
- Sequential access reads or writes records/bytes strictly in order from the start of the file (typical of magnetic tapes and log streams).
- Random access uses a
seekoperation to jump directly to any byte offset or key without reading preceding data (essential for databases and OS executables on disks/SSDs).
Ordinary files hold user data/programs, directory files map names to metadata, and special files expose I/O devices as character (byte-stream) or block (fixed-block) interfaces. Sequential access reads strictly from start to end, whereas random access uses seek to jump directly to arbitrary offsets.
Explain absolute and relative path names in a hierarchical directory system, and contrast how Linux and Windows organize directory hierarchies and path syntax.
Absolute vs. relative paths:
- An absolute path traces the full directory path starting from the root directory (unique and independent of the current working directory).
- A relative path starts from the process's current working directory, using
.for the current directory and..for the parent directory.
Linux vs. Windows directory hierarchies:
- Linux: Uses a single unified tree rooted at
/where additional drives/partitions are mounted onto existing directories (e.g.,/mnt/usb). Paths use forward slashes (/) and are case-sensitive. - Windows: Uses separate trees per drive/partition identified by drive letters (
C:\,D:\). Paths conventionally use backslashes (\) and are case-insensitive (while preserving case).
An absolute path starts from the root, whereas a relative path starts from the working directory. Linux uses one unified /-rooted, case-sensitive tree with / separators, while Windows uses per-drive letter trees (C:\), \ separators, and case-insensitive names.
A disk uses blocks and -byte FAT entries.
- Compute the total number of blocks and the RAM required to store the FAT.
- Compare this with an i-node file system where each i-node is and at most files can be open simultaneously.
Calculating total disk blocks and FAT RAM:
With per FAT entry:
Calculating open-file i-node table RAM: Only open files need their i-nodes resident in memory:
Comparing memory scaling: The FAT consumes regardless of how many files are open, whereas the i-node table consumes only (over less RAM) and stays fixed even if the disk grows to multiple terabytes.
The disk has blocks, requiring of RAM for the FAT versus only for open i-nodes.
A file system uses i-nodes containing direct block pointers, single indirect pointer, and double indirect pointer (no triple indirect pointer). If the block size is () and each block address takes , calculate the maximum file size in bytes and in .
Computing pointers per indirect block:
Summing addressable data blocks:
- Direct blocks:
- Single indirect blocks:
- Double indirect blocks:
Computing maximum file size:
The maximum file size is (approximately ).
Explain three techniques used by operating systems to improve file system performance: buffer caching, block read-ahead, and cylinder groups. When can block read-ahead degrade performance?
Buffer (block) caching: Frequently accessed disk blocks are kept in a RAM pool indexed by a hash table (device, block_number) and maintained on a doubly linked exact-LRU list. Cache hits avoid millisecond-scale disk seeks entirely.
Block read-ahead and when it hurts: When reading sequentially, delivering block triggers an asynchronous prefetch of block so it arrives in cache before needed. However, if the application performs random access, prefetched blocks are never used—wasting disk I/O bandwidth and evicting useful cached blocks.
Cylinder groups: Placing all i-nodes at the start of the disk forces long head seeks between an i-node and its data blocks. Dividing the disk into cylinder groups—each holding its own i-nodes, free bitmap, and data blocks—keeps a file's metadata and data physically close, minimizing seek time.
Buffer caching serves repeated reads from RAM via hash + LRU lists; block read-ahead prefetches block for sequential reads (but hurts random access by wasting bandwidth and polluting the cache); cylinder groups co-locate i-nodes with nearby data blocks to cut disk-arm seek distances.
Compare FAT32, EXT4, NTFS, and NFS with respect to metadata structure, journaling support, access control, and primary use case.
Comparing local file systems (FAT32, EXT4, NTFS):
- FAT32: Uses a File Allocation Table and -byte directory entries; no journaling or per-user ACLs; capped at per file; ideal for cross-platform USB drives and embedded media.
- EXT4: Linux default; extends UNIX i-nodes with extent trees, delayed allocation, metadata journaling, and POSIX permissions/ACLs.
- NTFS: Windows default; stores file records in the Master File Table (MFT) (embedding tiny files inside MFT records), supports metadata journaling, rich Windows ACLs, compression, and EFS encryption.
Comparing network file system (NFS):
- NFS: Client-server distributed file system using RPC and the client's VFS layer to mount remote directories transparently; relies on the server's underlying local file system for storage and journaling, while adding network security (e.g., Kerberos in NFSv4) and caching/locking semantics.
FAT32 is lightweight and portable (no journaling/ACLs, file limit); EXT4 (Linux) uses i-node extent trees, journaling, and POSIX ACLs; NTFS (Windows) uses the MFT, journaling, fine-grained ACLs, and EFS; NFS is a network file system exposing remote server directories over RPC/VFS.