1. The Problem It Solves (Start With Motivation)

To understand why Linked Allocation was introduced, we first need to examine the limitations of Contiguous Allocation.

In Contiguous Allocation, a file must occupy consecutive disk blocks.

Example:

File A

10 → 11 → 12 → 13 → 14

This approach provides excellent performance, but it creates two major problems in real systems.

Problem 1: External Fragmentation

Over time, files are created and deleted repeatedly.

Disk space becomes fragmented:

Free Space:

5–6

10–12

20–21

Although total free space may be sufficient, a large file cannot be allocated unless a single continuous region exists.

This leads to allocation failures despite having enough free storage.

Problem 2: File Growth

Suppose a file occupies:

10 → 11 → 12

and later needs additional space.

If block 13 is already occupied:

10 → 11 → 12 | X

the file cannot grow naturally.

The operating system must either:

• Move the entire file

• Preallocate excessive space

• Perform compaction

All of these are expensive operations.

Need for a Better Approach

Instead of forcing blocks to remain adjacent, why not allow them to be stored anywhere?

The operating system only needs a way to remember the correct order.

This idea leads to Linked Allocation.

Key Insight

Linked Allocation removes the requirement of physical continuity and replaces it with logical connectivity.

2. What is Linked Allocation?

Linked Allocation is a file allocation technique in which a file is stored as a linked list of disk blocks.

Each block contains:

• File data

• Pointer to the next block

Definition

A file is represented as a chain of disk blocks linked together through pointers.

Key Idea

Block → Block → Block → Block → NULL

The file's order is determined by pointers rather than physical placement.

Example

A file may occupy:

10 → 25 → 3 → 19 → NULL

Notice:

10
25
3
19

are completely unrelated physical locations.

Yet they form one logical file.

Important Observation

The file appears continuous to the user even though its blocks are scattered throughout the disk.

Key Insight

Physical adjacency is no longer required.

3. Structure of a Linked File

Unlike contiguous allocation, blocks can reside anywhere on the disk.

Example

Disk Layout

Block 3   → File A
Block 10  → File A
Block 19  → File A
Block 25  → File A

Logical File Structure

10 → 25 → 3 → 19 → NULL

Directory Entry

Instead of storing:

Start Block
Length

the OS stores:

File Name
Start Block

Example:

project.txt

Start Block = 10

From this starting block, the operating system can locate every remaining block through pointer traversal.

Key Insight

Only the address of the first block is needed.

4. How the OS Stores and Finds a File

Step 1: File Creation

Suppose a new file is created:

create("report.txt")

The operating system finds any available free block.

Example:

Block 10

This becomes the starting block.

Step 2: Allocate Additional Blocks

The next available blocks may be:

25
3
19

These are not necessarily adjacent.

Step 3: Build the Chain

The OS stores pointers:

Block 10 → Pointer = 25

Block 25 → Pointer = 3

Block 3 → Pointer = 19

Block 19 → Pointer = NULL

Step 4: Store Metadata

Directory Entry:

File Name = report.txt

Start Block = 10

No length information is required for navigation.

Final Structure

report.txt

10 → 25 → 3 → 19 → NULL

Key Insight

The file system follows pointers to reconstruct the logical order of the file.

5. What Happens During a Read Operation?

Consider:

read(fd, buffer, size);

Internally, the operating system performs several steps.

Step 1: Locate File

Using the directory entry:

report.txt → Start Block = 10

Step 2: Read First Block

OS loads:

Block 10

The block contains:

Data
Pointer = 25

Step 3: Follow Pointer

OS reads:

Block 25

which contains:

Data
Pointer = 3

Step 4: Continue Traversal

Block 3 → Pointer = 19

Block 19 → Pointer = NULL

Step 5: End of File

When:

Pointer = NULL

the file ends.

Read Flow

Directory
    ↓
Start Block
    ↓
Block 10
    ↓
Block 25
    ↓
Block 3
    ↓
Block 19
    ↓
NULL

Key Insight

Reading a linked file is equivalent to traversing a linked list stored on disk.

6. Visual Understanding

Physical Disk

0   1   2   3   4   5
F   F   F   A   F   F

6   7   8   9   10
F   F   F   F    A

11 12 13 14 15
F  F  F  F  F

19 → A

25 → A

Logical File

10 → 25 → 3 → 19 → NULL

Another Representation

[Data|25]
      ↓
[Data|3]
      ↓
[Data|19]
      ↓
[Data|NULL]

Important Observation

Logical order and physical order are completely independent.

7. Why Sequential Access Works Well

Linked allocation naturally supports sequential access.

Example

Reading a file:

Block 1
↓
Block 2
↓
Block 3
↓
Block 4

matches the linked structure.

Sequential Read Flow

Start
 ↓
Next
 ↓
Next
 ↓
Next

This makes linked allocation suitable for workloads where data is consumed in order.

Examples:

• Audio playback

• Video streaming

• Log processing

• Backup reading

Key Insight

Sequential traversal follows the linked structure naturally.

8. Why Random Access Performs Poorly

This is the most important limitation.

Suppose we need:

5th Block

of the file.

In contiguous allocation:

Physical Block = Start + Offset

Direct calculation is possible.

In linked allocation:

Start
 ↓
1st
 ↓
2nd
 ↓
3rd
 ↓
4th
 ↓
5th

Every previous block must be visited.

Time Complexity

O(n)

for accessing the nth block.

Example

To reach block 100:

1 → 2 → 3 → ... → 100

must be traversed.

Key Insight

Random access is inefficient because there is no direct mapping.

9. Strengths of Linked Allocation

9.1 No External Fragmentation

Since blocks can be anywhere:

Free Block = Usable Block

There is no need to find a large continuous region.

Benefit

Efficient utilization of disk space.

9.2 Easy File Growth

Suppose:

10 → 25 → 3

File expands.

OS finds:

Block 50

and simply appends:

10 → 25 → 3 → 50

Benefit

No relocation required.

9.3 Better Space Utilization

Even highly fragmented disks remain usable.

Benefit

Reduced wasted space.

9.4 Simpler Allocation Decisions

The OS only needs:

Any Free Block

rather than:

Large Continuous Region

Benefit

Allocation becomes easier.

10. Weaknesses of Linked Allocation

10.1 Pointer Overhead

Each block stores:

[ Data | Pointer ]

Part of every block is consumed by pointer information.

Example

If:

Block Size = 1024 Bytes

Pointer = 4 Bytes

then:

1020 Bytes = Data

4 Bytes = Pointer

Impact

Storage efficiency decreases.

Key Insight

Pointers consume usable disk space.

10.2 Reliability Risk

Suppose:

10 → 25 → 3 → 19

and pointer in block 25 becomes corrupted.

Result:

10 → 25 → ?

Blocks:

3
19

become unreachable.

Impact

A single damaged pointer can destroy access to the remaining file.

Key Insight

Linked allocation has poor fault tolerance.

10.3 Poor Locality of Reference

Blocks may be scattered:

10
↓
200
↓
5
↓
800

Disk head constantly moves between locations.

Impact

• Higher seek time

• Lower throughput

• Reduced caching effectiveness

Key Insight

Physical scattering hurts performance.

10.4 No Efficient Random Access

To reach:

Block N

all previous blocks must be traversed.

Impact

Unsuitable for:

• Databases

• Index systems

• Large record-based applications

Key Insight

This is the most serious limitation of linked allocation.

11. FAT (File Allocation Table) – A Practical Improvement

Traditional linked allocation stores pointers inside data blocks.

This introduces:

• Pointer overhead

• Additional disk accesses

To improve performance, FAT systems move pointers into a centralized table.

Basic Idea

Instead of:

Block 10 → 25

inside the block,

store:

FAT[10] = 25

Example

FAT[10] = 25

FAT[25] = 3

FAT[3] = 19

FAT[19] = END

File Structure

10 → 25 → 3 → 19 → END

but pointers reside in memory.

Advantages

Data Blocks Store Only Data

[ DATA ]

No pointer overhead.

Faster Traversal

FAT lookup occurs in RAM.

Benefit

Reduced disk accesses.

Trade-Off

The FAT table can become very large and must remain cached for good performance.

Key Insight

FAT preserves linked allocation while improving traversal efficiency.

12. When Linked Allocation Is Actually Used

Linked allocation is not the dominant modern allocation method, but it remains important in specific environments.

FAT File Systems

Used in:

• USB drives

• SD cards

• Older Windows systems

Why?

Simple design and low implementation complexity.

Embedded Systems

Systems with limited resources often favor simple allocation mechanisms.

Benefit

Lower implementation overhead.

Sequential Workloads

Examples:

• Media streaming

• Log processing

• Backup archives

Benefit

Sequential traversal is efficient.

Educational and Historical Systems

Linked allocation remains important for understanding file system evolution.

Benefit

Foundation for FAT and related systems.

13. Linked Allocation at a Glance

Final Insight

Linked Allocation stores a file as a chain of disk blocks connected through pointers. Because blocks can be located anywhere on the disk, it completely eliminates external fragmentation and makes file growth extremely easy. However, this flexibility comes at the cost of poor random access, pointer overhead, and reduced reliability. Modern systems often improve upon linked allocation through the File Allocation Table (FAT), which stores pointers centrally while retaining the core idea of linking scattered blocks into a logical file.