Fileallocation

13 min read2,536 words

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

FeatureContiguousLinkedIndexed
Blocks adjacent?YesNoNo
External fragmentationYesNoNo
Random accessExcellentPoorGood
Sequential accessExcellentGoodGood
File growthDifficultEasyEasy
Metadata overheadLowPointer overheadIndex overhead
ComplexitySimpleModerateModerate
Main issueFragmentationRandom accessIndex 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 AllocationMemory Allocation
StorageRAM
FilesProcesses
Disk blocksMemory blocks
FilesystemMemory manager
Contiguous/linked/indexedFirst 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy