File Systems in Operating System – Allocation Methods, Directory Structure & Inodes
What You Will Learn
- File concept: attributes, operations, and file types
- Directory structures: single-level, two-level, tree, DAG
- File allocation methods: contiguous, linked, indexed
- Inode structure and block pointer calculation
- FAT file system and its limitations
- Free space management: bitmap, linked list, grouping
- GATE PYQs with full solutions
GATE Weightage: 1–3 marks most years. Focus on allocation methods, inode calculations, and access time questions.
1. File Concept and Attributes
A file is a named collection of related information stored on secondary storage. The file system in an operating system manages how files are stored, retrieved, and organised on disk.
File Attributes
| Attribute | Description |
|---|---|
| Name | Human-readable identifier (stored in directory entry) |
| Identifier | Unique tag (inode number) used internally by OS |
| Type | File extension or magic number |
| Location | Pointer to file’s location on device |
| Size | Current size in bytes |
| Protection | Read/write/execute permissions |
| Timestamps | Created, last modified, last accessed |
File Operations
- Create: allocate space, add directory entry
- Open: search directory, load FCB (File Control Block) into memory
- Read/Write: transfer data between disk and memory buffer
- Seek: reposition the file pointer (no disk I/O)
- Delete: remove directory entry, free disk blocks
- Truncate: erase content but keep file attributes
Open File Table
When a file is opened, the OS maintains two tables:
- Per-process open file table: file descriptor, current position pointer, access mode
- System-wide open file table: FCB, inode, reference count (how many processes have it open)
2. Directory Structures
A directory maps file names to their metadata (inode numbers or FCB pointers). File systems in operating systems support several directory organisations.
Single-Level Directory
All files in one directory. Simple but no grouping possible; file name conflicts if multiple users. Used in very early systems.
Two-Level Directory
Separate directory per user. Eliminates name conflicts between users but no sub-grouping within a user’s files.
Tree-Structured Directory
The standard in modern OS (Unix, Windows). Arbitrary depth of directories. Each file has an absolute path from root. Supports current working directory for relative paths.
Acyclic Graph (DAG) Directory
Allows files or sub-directories to be shared — a file can appear in multiple directories. Implemented via:
- Hard links: multiple directory entries point to the same inode. Both entries are equal — no “original.” Deleting one does not delete the file (reference count must reach 0).
- Symbolic (soft) links: a special file that contains the path to another file. Can span file systems; becomes dangling if the target is deleted.
General Graph Directory
Allows cycles — difficult to guarantee traversal terminates. Requires garbage collection to reclaim unreachable files. Not used in practice.
3. File Allocation Methods
File allocation methods determine how disk blocks are assigned to files. This is the most important topic in file systems for GATE CS.
3.1 Contiguous Allocation
Each file occupies a set of contiguous disk blocks. The directory entry stores the starting block number and length.
| Property | Detail |
|---|---|
| Directory entry | (start, length) |
| Sequential access | Excellent — just read next block |
| Random access | Excellent — start + offset |
| External fragmentation | Yes — free blocks scattered after deletions |
| Internal fragmentation | Minimal (last block may be partially used) |
| Growing files | Problem — adjacent blocks may not be free |
Block = start + b (for block size = 1 unit)
3.2 Linked Allocation
Each disk block has a pointer to the next block. Directory entry stores only (start, end) block numbers. The last block has a NULL pointer.
| Property | Detail |
|---|---|
| External fragmentation | None — any free block can be used |
| Sequential access | Good — follow pointers |
| Random access | Poor — must traverse chain from start |
| Reliability | Low — broken pointer corrupts rest of file |
| Pointer overhead | Each block loses a few bytes for the pointer |
FAT (File Allocation Table) is a variation where pointers are stored in a separate table in memory rather than in each block, enabling faster random access.
3.3 Indexed Allocation
Each file has an index block containing pointers to all its data blocks. The directory entry stores only the index block number.
| Property | Detail |
|---|---|
| External fragmentation | None |
| Sequential access | Good |
| Random access | Excellent — index block → data block directly |
| Index block overhead | Wastes one block per file for index |
| Maximum file size | Limited by index block size |
Multi-level index: For large files, an index block can point to other index blocks (similar to Unix inode’s indirect blocks).
If block size = B bytes, pointer size = p bytes:
Max pointers per index block = B / p
Max file size = (B / p) × B bytes
Pointers per index block = 4096 / 4 = 1024
Max file size with single-level index = 1024 × 4 KB = 4 MB
4. Inode Structure (Unix)
The inode (index node) is the fundamental data structure of Unix-like file systems. Each file has exactly one inode. The inode stores all file metadata except the file name (which lives in the directory entry).
Inode Block Pointer Structure
| Pointer Type | Typical Count | Levels of Indirection |
|---|---|---|
| Direct pointers | 12 | 0 — point directly to data blocks |
| Single indirect | 1 | 1 — points to a block of pointers |
| Double indirect | 1 | 2 — points to block of pointers to blocks of pointers |
| Triple indirect | 1 | 3 — three levels of indirection |
Pointers per block (k) = B / p
Max file size =
(12 + k + k² + k³) × B bytes
Disk accesses for offset in Nth block:
• Direct (block 1–12): 1 inode read + 1 data read = 2
• Single indirect: 1 inode + 1 indirect block + 1 data = 3
• Double indirect: 1 + 2 + 1 = 4
• Triple indirect: 1 + 3 + 1 = 5
Block size = 4 KB = 4096 B, pointer = 4 B
k = 4096 / 4 = 1024
Max file size = (12 + 1024 + 1024² + 1024³) × 4 KB
= (12 + 1024 + 1,048,576 + 1,073,741,824) × 4096 bytes
≈ 4 TB (triple indirect dominates)
Disk Accesses (No Cache)
To read byte at offset within data block 13 (first single-indirect block):
- Read inode (1 access)
- Read single-indirect block (1 access)
- Read actual data block (1 access)
Total = 3 disk accesses
5. FAT File System
FAT (File Allocation Table) is a variant of linked allocation where the linked list is replaced by a table stored at the beginning of the disk. Each entry in the FAT corresponds to one cluster (group of sectors).
| FAT Entry Value | Meaning |
|---|---|
| 0 | Free cluster |
| –2 (EOF marker) | Last cluster of file |
| N (any other value) | Next cluster number in file’s chain |
| –1 (BAD) | Bad sector, do not use |
FAT Variants
| Type | Cluster entry size | Max volume size |
|---|---|---|
| FAT12 | 12 bits | ~32 MB |
| FAT16 | 16 bits | ~2 GB |
| FAT32 | 28 bits (4 reserved) | ~2 TB |
FAT Limitations
- No file permissions or ownership (no Unix security model)
- No journaling (prone to corruption on crash)
- Entire FAT must fit in memory
- Max file size 4 GB (FAT32) due to 32-bit file size field
6. Free Space Management
The file system must track which disk blocks are free for allocation. Four main approaches are used in operating systems.
6.1 Bit Vector (Bitmap)
One bit per block: 0 = free, 1 = allocated. Stored in reserved area of disk.
- Pro: Simple; finding contiguous free blocks is easy (word-level operations)
- Con: Entire bitmap must be in memory for efficiency; large for big disks
For 1 TB disk with 4 KB blocks: 1 TB / 4 KB = 256 M blocks → 256 M / 8 = 32 MB bitmap
6.2 Linked Free Space List
Free blocks are linked together. OS maintains a pointer to the first free block; each free block contains a pointer to the next.
- Pro: No wasted space for the list itself
- Con: Cannot easily find contiguous free space; traversal is slow
6.3 Grouping
First free block stores addresses of n free blocks. The last of those n blocks stores addresses of another n free blocks, and so on.
6.4 Counting
Stores (first free block address, count of contiguous free blocks). Works well when free blocks tend to be contiguous (e.g., after a large file is deleted).
7. Disk Access Time Calculations
Understanding disk access time is essential for GATE problems involving file system performance.
Seek Time: Time to move read/write head to correct track
Rotational Latency: Time for disk to rotate so sector is under head
Average Rotational Latency = (1/2) × (1/RPM) × 60 seconds
Transfer Time: Time to read/write the data
Transfer Time = Data size / Transfer rate
Rotational latency = (1/2) × (60/7200) × 1000 ms = (1/2) × 8.33 ms = 4.17 ms
Transfer time = 4 KB / (100 MB/s) = 4096 / (100 × 10⁶) s ≈ 0.04 ms
Total = 5 + 4.17 + 0.04 ≈ 9.21 ms per disk access
Number of Disk Accesses for File Read
| Allocation | Sequential read of n blocks | Random access of 1 block |
|---|---|---|
| Contiguous | 1 (seek to start) + n transfers | 1 seek + 1 read |
| Linked | n seeks (one per block) | n seeks on average |
| Indexed (direct) | 1 (index) + n reads | 2 (index + data) |
| Inode single-indirect | 1 (inode) + 1 (indirect) + n reads | 3 |
8. GATE Examples
GATE 2014: A file system uses an inode with 10 direct block pointers and one single indirect, one double indirect, and one triple indirect pointer. The disk block size is 1 KB and disk block address is 32 bits. The maximum possible file size is approximately:
View Solution
Block size = 1 KB = 1024 B, pointer = 4 B
Pointers per block k = 1024 / 4 = 256
Direct: 10 blocks = 10 KB
Single indirect: 256 blocks = 256 KB
Double indirect: 256² = 65,536 blocks = 64 MB
Triple indirect: 256³ = 16,777,216 blocks = 16 GB
Total ≈ 16 GB
GATE 2016: Consider a file stored using an indexed allocation scheme. The index block occupies one disk block. If each index entry is 4 bytes and the disk block size is 512 bytes, what is the maximum file size?
View Solution
Index block size = 512 B, pointer = 4 B
Entries in index block = 512 / 4 = 128
Max file size = 128 × 512 B = 65,536 B = 64 KB
Answer: 64 KB
GATE 2010: A FAT (File Allocation Table) based file system has a volume of 4 GB. If cluster size is 4 KB and each FAT entry is 4 bytes, what is the size of the FAT?
View Solution
Total clusters = 4 GB / 4 KB = 4 × 2³⁰ / 4 × 2¹⁰ = 2²⁰ = 1,048,576
FAT size = 1,048,576 × 4 bytes = 4,194,304 bytes = 4 MB
Answer: 4 MB
9. Common Mistakes
- Confusing inode with directory entry: The inode does NOT store the file name. The file name lives in the directory entry which maps name → inode number.
- Forgetting inode read in disk access count: To access any file, the inode must be read first (unless cached). Always add 1 for inode read.
- Hard link vs symbolic link: A hard link increments the inode’s reference count; deleting the original doesn’t destroy the file. A symbolic link stores a path; if the target is deleted, the link becomes dangling.
- FAT random access: FAT enables faster random access than pure linked allocation because the FAT is kept in memory; you don’t need to read disk blocks to traverse the chain.
- Contiguous allocation and fragmentation: Contiguous allocation suffers from external (not internal) fragmentation — free space gets fragmented between files.
- Double-indirect disk accesses: Reading from a double-indirect block requires: 1 (inode) + 1 (double-indirect block) + 1 (single-indirect block) + 1 (data block) = 4 accesses total.
10. Frequently Asked Questions
What are the three file allocation methods in operating systems?
The three methods are contiguous, linked, and indexed allocation. Contiguous gives best access speed but suffers external fragmentation. Linked eliminates fragmentation but is slow for random access. Indexed (used in Unix inodes) combines no fragmentation with fast random access and is the standard in modern file systems.
What is an inode in a file system?
An inode is a data structure in Unix-like file systems storing all file metadata (size, permissions, timestamps, block pointers) except the file name. Each file has exactly one inode identified by an inode number. The inode uses direct, single-indirect, double-indirect, and triple-indirect pointers to support files of varying sizes efficiently.
What is the difference between FAT and inode-based file systems?
FAT uses a centralised table in memory where entries link clusters into file chains — simple but limited in scalability and lacking permissions. Inode-based systems (ext4) store per-file metadata in distributed inodes, support Unix permissions, journaling, and scale to terabytes. Modern Windows uses NTFS (similar to inodes via MFT records); modern Linux uses ext4.
How does free space management work in file systems?
The OS tracks free disk blocks using a bitmap (one bit per block, efficient for finding contiguous space), a free list (linked free blocks, minimal overhead), grouping (first free block points to n free blocks), or counting (address + count of contiguous free blocks). Most modern file systems like ext4 use bitmaps stored in reserved disk areas.
What is the difference between absolute and relative path in OS?
An absolute path starts from the root directory and fully specifies the file location (e.g., /home/user/file.txt). A relative path is resolved from the current working directory (e.g., ../docs/file.txt). The OS maintains a CWD per process, prepending it to resolve relative paths. Absolute paths are unambiguous; relative paths are shorter but context-dependent.