File Allocation Methods in Operating Systems: Contiguous, Linked and Indexed Worked Examples

Compare contiguous, linked and indexed allocation by tracing the same file across disk blocks. Then calculate growth costs and a two-level index lookup.

KnowledgeGate Team

Exam prep & CS education

Updated 14 Nov 20266 min read
File Allocation Methods in Operating Systems: Contiguous, Linked and Indexed Worked Examples

Contiguous, linked and indexed allocation map the same file with different metadata, block maps, access paths and growth rules. A 13,000-byte file uses different block maps under each method; growing it to 20,000 bytes changes the allocation metadata, and a two-level index determines the lookup path.

What file allocation must record and why the method matters

A file is a logical byte sequence; a disk block is a fixed-size physical unit. Logical blocks 0, 1, 2, and so on map to physical blocks, so file metadata must recover that mapping.

Ask: Where are the blocks? How is one found? What happens as the file grows? A bitmap or free list selects free blocks; the allocation method records ownership and access paths.

Contiguous allocation stores start block plus run length; linked allocation connects scattered blocks by pointers; indexed allocation holds data-block addresses in an index block. File Systems and I/O for GATE connects pathname resolution, open-file state, inode levels and device timing. The 13,000-byte trace isolates allocation layouts, growth updates and a two-level index lookup. The CS Fundamentals map places file allocation within the wider subject.

Compare contiguous, linked and indexed allocation before calculating

Compare the trade-offs side by side.

Method

Directory metadata

Sequential access

Random access

Growth

Main cost

Contiguous

Start block + length

Direct arithmetic

Direct arithmetic

Needs adjacent space

External fragmentation

Linked

First block, optionally last block

Follows pointers well

Slow in ordinary linked allocation

Add any free block

Pointer space

Indexed

Index-block address

Direct lookup through index

Direct lookup through index

Add any free data block

Index metadata, possibly multiple levels

External fragmentation means free space exists, but not as the required adjacent run. Internal waste lies inside the final allocated block. Linked and indexed allocation avoid adjacent-run constraints but retain block and metadata overhead.

A FAT-style table changes linked access and space accounting. Here, each linked data block contains one next pointer.

Worked example: store the same 13,000-byte file three ways

Let results.bin contain 13,000 bytes. Blocks are fixed-size 4,096-byte units, pointers are 4 bytes, and the target is zero-based logical data block 2, the third data block. Block numbers are illustrative; all offsets and indices are zero-based. Assume no cache, directory metadata available, and no directory-lookup or free-space-map cost.

For contiguous and indexed allocation:

ceil(13,000 / 4,096) = 4 data blocks

4 x 4,096 = 16,384 bytes of data-block capacity

16,384 - 13,000 = 3,384 unused bytes in the last data block

For contiguous allocation, the directory stores start=20, length=4, covering physical blocks 20, 21, 22, 23. Logical block 2 maps as 20 + 2 = physical block 22 and needs one data-block read.

In linked allocation, each block reserves 4 bytes for its next pointer, leaving 4,096 - 4 = 4,092 payload bytes. Therefore, ceil(13,000 / 4,092) = 4 blocks. The chain is 20 -> 41 -> 7 -> 32 -> EOF. Payload capacity is 4 x 4,092 = 16,368 bytes, leaving 16,368 - 13,000 = 3,368 unused payload bytes; four pointer fields occupy 16 bytes. Reaching logical block 2 means reading 20, 41, then target 7: three block reads.

For indexed allocation, the directory points to index block 50, containing index[0]=20, index[1]=41, index[2]=7, and index[3]=32. The file uses four data blocks plus one index block. Logical block 2 reads block 50, then data block 7: two reads, or one if the index is cached. The four live entries use 16 bytes. Block 50 is metadata, not file data.

Three block maps for the same 13,000-byte file: contiguous blocks 20 to 23, the linked chain 20-41-7-32, and index block 50.

Grow the file and expose each method's trade-off

Grow results.bin to exactly 20,000 bytes. Contiguous and indexed allocation require ceil(20,000 / 4,096) = 5 data blocks. Their last-block waste is 5 x 4,096 - 20,000 = 20,480 - 20,000 = 480 bytes.

Linked allocation also needs five blocks because ceil(20,000 / 4,092) = 5. Its 5 x 4,092 = 20,460 payload bytes leave 20,460 - 20,000 = 460 unused payload bytes. Five pointer fields reserve 20 bytes.

Contiguous allocation extends run 20-23 only if block 24 is free. Otherwise, this simplified model relocates the file to run 60-64 and sets start=60, length=5; real implementations may differ.

Linked allocation appends free block 55: change block 32 from EOF to next=55, then store EOF in block 55. Indexed allocation adds block 55 as index[4]=55 in index block 50, which does not move.

Indexed-allocation capacity and a two-level lookup numerical

For a separate example, use a 1,024-byte block and a 4-byte pointer. One index block holds 1,024 / 4 = 256 pointers. A single-level index addresses 256 data blocks, giving 256 x 1,024 = 262,144 bytes = 256 KiB of file data.

In a two-level index, the outer block has 256 pointers to inner blocks, each holding 256 data-block pointers. Maximum file data is 256 x 256 x 1,024 = 67,108,864 bytes = 64 MiB; index blocks are metadata and excluded.

Because 530,000 exceeds the single-level 262,144-byte capacity, one index block cannot address this offset.

Resolve zero-based byte offset 530,000:

  • Logical block number: floor(530,000 / 1,024) = 517.

  • In-block displacement: 530,000 mod 1,024 = 592.

  • Outer index: floor(517 / 256) = 2.

  • Inner index: 517 mod 256 = 5.

The path is outer index entry 2 -> inner index entry 5 -> data block. With no cache, it costs two index-block reads plus one data-block read; with both indexes cached, only the data read remains.

Two-level index lookup of byte offset 530,000: outer entry 2, inner entry 5, logical block 517, displacement 592.

Exam-style question forms and the traps that change the answer

Typical questions identify a method from metadata, count blocks, translate a logical block or byte offset, compare access under cache assumptions, update metadata after growth, or distinguish waste, fragmentation and pointer overhead. Use File Systems & Allocation MCQs for practice.

Wrong move

Correct check

Use floor(13,000 / 4,096) = 3

Allocation needs ceil, so 4 blocks are required.

Map contiguous logical block 2 to start+3

Zero-based mapping gives 20 + 2 = 22.

Call index block 50 a fifth data block

It is metadata, not file data.

Say linked random access jumps straight to block 7

Without a FAT or cached chain, traverse 20 -> 41 -> 7.

Use 4,096 payload bytes in the linked model

The 4-byte pointer leaves 4,092 payload bytes.

Call all unused bytes external fragmentation

The 3,384 last-block bytes are internal waste.

File allocation maps logical blocks to physical blocks; disk scheduling orders pending device requests. File systems and disk scheduling in OS works a separate seek-order calculation across FCFS, SSTF, SCAN and C-SCAN. Syllabus coverage and paper patterns differ between examinations, so check what is currently in scope for the exam you are sitting.

File allocation methods: the short version and next step

Recall: contiguous = start + arithmetic + adjacent growth; linked = first block + pointer traversal + easy scattered growth; indexed = index lookup + direct access + metadata block. With no cache, logical block 2 needs 1 read in contiguous, 3 in linked and 2 in indexed allocation.

Redraw the three layouts from memory and check that logical block 2 lands on physical blocks 22, 7, and 7 for contiguous, linked and indexed allocation, then explain why linked allocation needs three reads while indexed needs two. Zero to Hero: Complete CS Course extends the same block-mapping skills into a sequenced core-CS path.