File Allocation
File allocation is the method used by an operating system/file system to decide which disk blocks are assigned to a file and how those blocks are organized.
In simple words:
File allocation determines where a file's data is stored on the storage device.
For example, suppose a file needs 5 blocks:
File A ↓ Needs 5 blocks
The filesystem must decide whether to store them like:
[10][11][12][13][14]
or:
[10] → [25] → [7] → [31] → [42]
or using an index:
Index Block ├── 10 ├── 25 ├── 7 ├── 31 └── 42
These are different file allocation methods.
1. Why Is File Allocation Needed?
Storage devices are divided into blocks.
For example:
Disk Block 0 Block 1 Block 2 Block 3 Block 4 Block 5 ... Block 999
Suppose:
video.mp4 = 10 MB
The filesystem needs to find enough blocks to store it.
It must answer:
- Which blocks belong to the file?
- Where is the first block?
- Where is the next block?
- How can the OS find all blocks?
- Can the file grow?
- How quickly can the file be accessed?
2. Main File Allocation Methods
The traditional methods are:
File Allocation │ ├── Contiguous Allocation ├── Linked Allocation └── Indexed Allocation
Modern filesystems may use more advanced methods such as:
Extent-Based Allocation
Let's understand each in detail.
3. Contiguous Allocation
In contiguous allocation, all blocks belonging to a file are stored next to each other.
Example:
Disk: 0 1 2 3 4 5 6 7 8 ------------------------------------ A A A A A
File A occupies:
Block 1 → 2 → 3 → 4 → 5
The filesystem only needs to store:
Starting block = 1 Length = 5
So:
File A: Start = 1 Length = 5 blocks
4. Example of Contiguous Allocation
Suppose:
File A = 4 blocks
Disk:
Block: 0 1 2 3 4 5 6 7 8 A A A A
Metadata:
Start = 1 Length = 4
To find block 3 of the file:
Physical block = Start + offset
Therefore:
1 + 3 = 4
5. Advantages of Contiguous Allocation
1. Very fast sequential access
Because blocks are next to each other:
1 → 2 → 3 → 4 → 5
2. Fast direct access
If:
Start = 100
and we need logical block 7:
100 + 7 = 107
Very simple.
3. Low metadata overhead
Only starting block and length may be sufficient.
4. Good locality
Related file data is physically close together.
6. Disadvantages of Contiguous Allocation
The major problem is external fragmentation.
Suppose the disk looks like:
A A A _ _ B B B _ _ C C
There may be enough total free space:
2 + 2 = 4 blocks
but a new file requires:
4 consecutive blocks
There isn't one continuous region of 4 blocks.
This is external fragmentation.
7. File Growth Problem
Suppose:
File A: [10][11][12][13]
Now the file grows and needs 3 more blocks.
[10][11][12][13][14][15][16]
But suppose blocks 14–16 are already occupied.
The filesystem may need to:
1. Move the entire file OR 2. Find another large contiguous region
Moving large files is expensive.
8. Linked Allocation
In linked allocation, file blocks can be located anywhere on the disk.
Each block contains a pointer/reference to the next block.
Example:
File A: [10] → [25] → [7] → [31] → [18]
The blocks do not need to be adjacent.
9. Linked Allocation Example
Suppose:
Block 10: Data + pointer → 25 Block 25: Data + pointer → 7 Block 7: Data + pointer → 31 Block 31: Data + pointer → 18 Block 18: Data + NULL
So:
10 → 25 → 7 → 31 → 18
The filesystem needs to know the first block:
Start = 10
Then it follows the pointers.
10. Advantages of Linked Allocation
1. No external fragmentation
Blocks can be anywhere:
10 → 50 → 3 → 80
2. Easy file growth
A new block can be added anywhere.
10 → 50 → 3 → 80 → 42
3. Efficient use of free space
The file doesn't require one large contiguous area.
11. Disadvantages of Linked Allocation
1. Poor random access
Suppose you need block 50.
You may have to follow:
10 ↓ 25 ↓ 7 ↓ 31 ↓ ... ↓ 50
This can be slow.
2. Pointer overhead
Each block needs space for a pointer.
+--------------------------+ | Data | | Next block pointer | +--------------------------+
3. Reliability issue
If a pointer is corrupted:
10 → 25 → 7 → X
the remaining part of the file may become difficult to access.
12. FAT and Linked Allocation
A famous example related to linked allocation is the File Allocation Table (FAT).
Instead of storing the next-block pointer inside every data block, the filesystem keeps allocation information in a table.
Example:
FAT Block Next ---------------- 10 25 25 7 7 31 31 18 18 EOF
So:
10 → 25 → 7 → 31 → 18
The FAT stores the chain.
FAT variants include:
FAT12 FAT16 FAT32
13. Indexed Allocation
In indexed allocation, a separate index block stores the addresses of all data blocks belonging to a file.
Example:
File A | ↓ Index Block ┌───────────────┐ │ 10 │ │ 25 │ │ 7 │ │ 31 │ │ 18 │ └───────────────┘ ↓ ↓ ↓ Data blocks
The index tells the filesystem where the file's data blocks are located.
14. Example of Indexed Allocation
Suppose:
Index block = 100
Contents:
Index Block 100: Entry 0 → Block 10 Entry 1 → Block 25 Entry 2 → Block 7 Entry 3 → Block 31 Entry 4 → Block 18
Then:
File Block 0 → Physical Block 10 File Block 1 → Physical Block 25 File Block 2 → Physical Block 7 File Block 3 → Physical Block 31 File Block 4 → Physical Block 18
15. Advantages of Indexed Allocation
1. Supports direct access
The filesystem can directly look up a block through the index.
2. No external fragmentation
Blocks can be anywhere.
3. Easy file growth
New blocks can be added and their addresses placed in the index structure.
16. Disadvantages of Indexed Allocation
1. Index block overhead
The index itself consumes storage.
File data + Index block
2. Large files need large indexes
A single index block may not contain enough addresses.
This leads to more sophisticated structures.
17. Multi-Level Indexing
For very large files, filesystems can use multiple levels of indexing.
Conceptually:
Root Index | ┌─────────┼─────────┐ ↓ ↓ ↓ Index 1 Index 2 Index 3 ↓ ↓ ↓ Blocks Blocks Blocks
This allows much larger files to be addressed.
18. Unix/Linux Inode-Based Allocation
Linux filesystems such as ext2/ext3/ext4 use inodes to store file metadata and references to file data.
Conceptually:
Inode | ┌───────┼────────┐ ↓ ↓ ↓ Direct Indirect ... blocks blocks
Historically, Unix inode structures are often taught using:
Direct blocks Single indirect Double indirect Triple indirect
Modern filesystems such as ext4 also use extents, which are more efficient for many large files.
19. Extent-Based Allocation
An extent describes a contiguous range of blocks.
Instead of storing:
Block 100 Block 101 Block 102 Block 103 Block 104
the filesystem can represent the range as:
Start = 100 Length = 5
So:
Extent = [100 – 104]
This greatly reduces metadata for large contiguous regions.
20. Why Extents Are Useful
Suppose a large file uses:
100–199 500–599 900–999
Instead of storing 300 individual block numbers:
300 block references
the filesystem could store:
Extent 1 → start 100, length 100 Extent 2 → start 500, length 100 Extent 3 → start 900, length 100
Much less metadata.
21. Ext4 and Extents
Modern ext4 uses extents for file block mapping.
Conceptually:
File ↓ Inode ↓ Extent tree ↓ Physical block ranges
This is more scalable than representing every block individually for large files.
22. Comparison of Allocation Methods
| Feature | Contiguous | Linked | Indexed |
|---|---|---|---|
| Blocks adjacent? | Yes | No | No |
| External fragmentation | Yes | No | No |
| Random access | Excellent | Poor | Good |
| Sequential access | Excellent | Good | Good |
| File growth | Difficult | Easy | Easy |
| Metadata overhead | Low | Pointer overhead | Index overhead |
| Complexity | Simple | Moderate | Moderate |
| Main issue | Fragmentation | Random access | Index space |
23. Contiguous vs Linked vs Indexed
Contiguous
[10][11][12][13][14]
Think: "Together"
Linked
[10] → [25] → [7] → [31]
Think: "Chain"
Indexed
Index / | | \ 10 25 7 31
Think: "Table of addresses"
24. File Allocation and Fragmentation
Contiguous allocation
Main problem:
External fragmentation
Example:
AA__BBB__CC____
There may be enough total free blocks but not enough consecutive blocks.
Linked allocation
No external fragmentation requirement because blocks can be anywhere.
But:
Scattered blocks ↓ Poor locality ↓ Potentially slower access
Indexed allocation
Also doesn't require contiguous file blocks.
But:
Index structures ↓ Extra storage
25. File Growth Comparison
Suppose:
Current file: A A A A
The file needs 3 more blocks.
Contiguous
Needs:
A A A A A A A
If the next blocks aren't free, the file may need to move.
Linked
Simply add blocks:
A → A → A → A → A → A → A
Indexed
Add new block references:
Index ├── A ├── A ├── A ├── A ├── A ├── A └── A
$# 26. Sequential vs Random Access
This is a very important exam comparison.
Sequential access
Block 1 ↓ Block 2 ↓ Block 3 ↓ Block 4
Contiguous allocation is excellent here.
Random access
Need Block 100
Indexed allocation can locate it directly through an index.
Linked allocation may require following a long chain.
Therefore:
Random Access: Contiguous → Excellent Indexed → Good Linked → Poor
27. Free-Space Management
File allocation depends on knowing which blocks are free.
Common methods:
Bitmap
Block: 0 1 2 3 4 5 6 7 Status: 1 1 0 1 0 0 1 0
For example:
1 = allocated 0 = free
Free list
Free: 2 → 4 → 5 → 7
The filesystem uses this information to allocate blocks to new files.
28. File Allocation and Disk Performance
Allocation strategy can affect performance.
For HDDs:
Nearby blocks ↓ Less disk-head movement ↓ Better performance
For SSDs, there is no mechanical disk head, so the performance characteristics are different, although locality and filesystem allocation still matter for many reasons.
29. File Allocation Table — FAT
FAT uses a table to keep track of file block chains.
Simplified:
FAT Block Next -------------- 10 12 12 18 18 25 25 EOF
File:
10 → 12 → 18 → 25
This is why FAT is associated with linked allocation.
30. Inode Allocation
In Unix-like filesystems:
Filename ↓ Directory entry ↓ Inode ↓ Block mapping ↓ Data
For modern ext4:
Inode ↓ Extent tree ↓ Physical block ranges
So the inode is an important bridge between file metadata and file data locations.
31. File Allocation vs Memory Allocation
Don't confuse these.
File allocation
Allocates:
Disk/SSD blocks
to:
Files
Memory allocation
Allocates:
RAM
to:
Processes
Comparison:
| File Allocation | Memory Allocation |
|---|---|
| Storage | RAM |
| Files | Processes |
| Disk blocks | Memory blocks |
| Filesystem | Memory manager |
| Contiguous/linked/indexed | First fit/best fit/worst fit etc. |
32. Important Exam Numerical Concept
Suppose:
Block size = 4 KB File size = 10 KB
Number of blocks required:
ceil(10 / 4) = ceil(2.5) = 3 blocks
Storage used:
3 × 4 KB = 12 KB
Internal unused space:
12 KB - 10 KB = 2 KB
So:
The file requires 3 blocks, with 2 KB unused in the final block.
33. Another Numerical Example
Suppose a file requires:
8 blocks
and the filesystem uses contiguous allocation.
If the disk has:
Free blocks: 10,11,12,13,14,15,16,17
Then the file can be allocated as:
Start = 10 Length = 8
Data:
10 11 12 13 14 15 16 17
Very efficient.
But if free blocks are:
10, 11, 20, 21, 30, 31, 40, 41
there are 8 free blocks total, but no 8 consecutive blocks.
Contiguous allocation fails without rearrangement.
Linked/indexed allocation can still allocate the file.
34. Modern File Allocation
Modern filesystems usually don't simply use the three classical methods exactly as taught in textbooks.
They use more sophisticated structures.
Examples:
NTFS
Uses structures such as the:
Master File Table (MFT)
ext4
Uses:
Inodes Extents Block groups
XFS
Uses:
Extent-based allocation Allocation groups B-trees
The basic goal remains the same:
Map file data to physical storage efficiently and reliably.
35. Complete File Allocation Flow
Application ↓ Create / Write File ↓ Filesystem ↓ Check Free Space ↓ Choose Allocation Method ↓ Allocate Storage Blocks ↓ Store Mapping Information ↓ Write File Data ↓ Update Metadata ↓ Storage Device
🧠 Exam Revision
Definition
File allocation is the method used by a filesystem to assign disk blocks to files and maintain information about the locations of those blocks.
Three classical methods
1. Contiguous ↓ [10][11][12][13] 2. Linked ↓ [10] → [25] → [7] → [31] 3. Indexed ↓ Index → 10, 25, 7, 31
Main differences
Contiguous → Fast → Simple → External fragmentation → Difficult growth Linked → Easy growth → No external fragmentation → Poor random access → Pointer overhead Indexed → Good random access → Easy growth → No external fragmentation → Index overhead
🧠 Memory trick
Contiguous = Together
Linked = Chain
Indexed = Address List
And for modern filesystems:
Extent = Start block + number of consecutive blocks