Skip to main content

File allocation and access methods

Short answer

File allocation methods include contiguous (fast sequential/direct access but external fragmentation and file-size knowledge needed), linked (no fragmentation but slow random access), FAT (pointers in memory for faster random access but scaling issues), and indexed (direct access via i-node, no fragmentation, overhead). Access methods are sequential, direct, and indexed sequential; allocation method affects access efficiency.

Discuss various file allocation and access methods. Compare their advantages and disadvantages.

File allocation methods

The file allocation method decides which disk blocks belong to a file. The main methods are:

1. Contiguous allocation - each file occupies a set of consecutive blocks. The directory stores the start block and length.

 file A: blocks 0-3   file B: blocks 4-6   free 7-...
 [A][A][A][A][B][B][B][ ][ ]
  • Advantages: simple; very fast sequential and direct access (only one seek); only start and length are stored.
  • Disadvantages: external fragmentation (needs compaction); file size must be known in advance; file growth is difficult.

2. Linked-list allocation - each block contains a pointer to the next block; the directory stores the first block.

 [blk 9 |->2] [blk 2 |->14] [blk 14 |->nil]
  • Advantages: no external fragmentation; files can grow easily; no need to know size.
  • Disadvantages: random access is very slow (must follow the chain); the pointer takes space in each block (so the data size is no longer a power of 2); one lost pointer breaks the file (poor reliability).

3. Linked list with a table in memory (FAT) - the pointers are moved out of the data blocks into a File Allocation Table in memory; entry i gives the block after block i.

  • Advantages: full block available for data; random access is faster (chain followed in memory).
  • Disadvantages: the whole table must be in memory (a 1 TB disk with 1 KB blocks needs 10⁹ entries), so it does not scale.

4. Indexed allocation (i-node) - each file has an index block (i-node) that lists the addresses of all its blocks (UNIX adds indirect blocks for large files).

 i-node: [b1][b2][b3]...[single indirect]-->[b..][b..]
  • Advantages: supports direct access, no external fragmentation, only the i-nodes of open files need to be in memory.
  • Disadvantages: index block overhead (even for a small file); very large files need multiple levels of indirection.

File access methods

MethodDescriptionAdvantagesDisadvantages
Sequential accessRecords are read/written in order, one after another (read next, write next, rewind). Used with tapes and editorsSimple; efficient for whole-file processingSlow to reach a particular record
Direct (random) accessThe file is a numbered sequence of fixed-length blocks/records; any block can be read directly (read n, position to n)Fast access to any record; good for databasesNeeds fixed record structure; more complex
Indexed (index sequential) accessAn index holds keys and pointers to blocks; first search the index, then access the recordQuick keyed lookup, supports both sequential and direct accessIndex takes space and has to be maintained

The allocation method affects which access is efficient: contiguous allows both sequential and direct access; linked allocation supports sequential access well but direct access poorly; indexed allocation supports direct access.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 5 questions →