PadhaikoAll subjects

File Systems

Operating System (ENCT 254)

Open in the Padhaiko app

5.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.

Definition

File Naming Conventions

File Structure

Operating systems structure files internally in one of three logical ways:

Logical File Structures
StructureOrganizationCharacteristics & Use Cases
Byte SequenceUnstructured stream of bytesUsed by UNIX/Linux and Windows; the OS imposes no internal format, giving user programs complete flexibility.
Record SequenceSequence of fixed-length recordsHistorically used for punch-card readers and line printers (e.g., CP/M -byte records); read/write operations transfer one record at a time.
TreeHierarchy of variable-length records sorted by a key fieldUsed 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:

Definition

Categories of Files (UNIX and Windows)

  1. 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).
  2. 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).
  3. 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:

AspectSequential AccessRandom (Direct) Access
Access OrderBytes or records are read strictly in order from start to finish; skipping ahead requires reading or rewinding past earlier dataAny byte offset or record can be read or written directly out of order
Typical MediumOriginally designed for magnetic tapesDesigned for magnetic disks and SSDs
PositioningAutomatic internal pointer advances on every read/writeExplicit seek operation moves the file pointer to a target byte offset or key
ApplicationsStreaming logs, compilers reading source files, tape backupsDatabases, 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:

Common File Attributes
AttributePurpose
NameSymbolic identifier in human-readable form.
IdentifierUnique numeric tag (e.g., i-node number) used internally by the OS.
TypeDistinguishes regular files, directories, device files, or symbolic links.
LocationPointer to the device and physical disk blocks holding the file.
SizeCurrent length of the file in bytes (and allocated block count).
ProtectionAccess-control flags (read, write, execute) for owner, group, and others.
Timestamps & FlagsCreation, 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:

Definition

Fundamental File Operations


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

AspectSingle-Level DirectoryHierarchical (Tree-Structured) Directory
StructureOne flat root directory holds every file on the volumeTree of directories and subdirectories branching from a root
Naming CollisionsAll files must have globally unique names—unusable for multi-user systemsIdentical file names can coexist in different directories (e.g., /alice/lab.c and /bob/lab.c)
OrganizationSimple and fast lookup for tiny file countsNatural grouping by user, project, and purpose
UsageEarly 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.

  1. 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.
  2. 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 path mailbox refers to /usr/ast/mailbox.

Linux vs. Windows Directory Hierarchies

Linux vs. Windows Directory Structures and Paths
FeatureLinux (POSIX / VFS)Windows (NTFS / Win32)
Root ConceptSingle 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 SeparatorForward slash (/)Backslash (\), though Win32 APIs also accept / internally.
Absolute Path Example/home/arya/docs/notes.txtC:\Users\arya\Documents\notes.txt
Relative Path Example../docs/notes.txt..\Documents\notes.txt
Case SensitivityCase-sensitive (File.txt file.txt).Case-insensitive by default (File.txt file.txt).
Standard Top-Level Layout/bin, /etc, /home, /usr, /var, /dev, /tmpC:\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).

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).

Definition

I-Node Architecture

An i-node is a fixed-size per-file data structure stored on disk that holds:

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 .

AspectFAT (Linked Table in RAM)I-Node (Indexed Allocation)
RAM UsageProportional 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 EntryStores file name, attributes, and starting block numberStores just file name and i-node number (supports hard links)
ScalabilityPoor for multi-terabyte volumesScales 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:

Definition

Core File System Performance Techniques

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Definition

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.

Definition

EXT4 (Fourth Extended File System)

The default local file system for most Linux distributions, descending from the UNIX i-node architecture (ext2 ext3 ext4):

Definition

NTFS (New Technology File System)

The standard local file system of modern Windows operating systems:

Definition

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):

Comparison of FAT32, EXT4, NTFS, and NFS
FeatureFAT32EXT4NTFSNFS
Primary RoleRemovable media, EFI system partitionLinux local disk volumesWindows local disk volumesNetwork shared storage (client-server)
Core MetadataFile Allocation Table + -byte directory entriesI-nodes with extent treesMaster File Table (MFT) with data runsServer's local FS exposed via RPC/VFS
Max File Size ( blocks) (implementation; format)Depends on underlying server FS & protocol
JournalingNoYesYes ()Delegated to server's local FS
Permissions / ACLsBasic flags (Read-only, Hidden, System, Archive)POSIX rwx + POSIX ACLsFine-grained Windows ACLs + EFSUID/GID mapping (v3) / Kerberos + ACLs (v4)

Worked Out Examples

Example 5.1

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:

Answer:

The partition contains () blocks, and the in-memory FAT occupies of RAM continuously while the volume is mounted.

Example 5.2

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 :

Answer:

The maximum supported file size is blocks, which equals (approximately ).

Example 5.3

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:

  1. Contiguous allocation
  2. Linked list allocation (pointers stored inside disk blocks)
  3. Linked list allocation using an in-memory FAT
  4. 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.

Answer:

Disk reads required for logical block : Contiguous = , On-disk Linked = , In-memory FAT = , I-node = .


Exercises

Exercise — File Systems

Question 1

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 seek operation to jump directly to any byte offset or key without reading preceding data (essential for databases and OS executables on disks/SSDs).
Answer:

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.

Question 2

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).
Answer:

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.

Question 3

A disk uses blocks and -byte FAT entries.

  1. Compute the total number of blocks and the RAM required to store the FAT.
  2. 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.

Answer:

The disk has blocks, requiring of RAM for the FAT versus only for open i-nodes.

Question 4

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:

Answer:

The maximum file size is (approximately ).

Question 5

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.

Answer:

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.

Question 6

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.
Answer:

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.

Past exam questions for Operating System

← Memory ManagementSecurity and System Administration →