Question Answer

File Organisation and Access Mechanisms in Operating Systems

In an operating system, file organisation describes how a file’s data blocks are laid out on secondary storage (like a hard disk), while access mechanisms (or access methods) explain how processes read and write data from those files. Choosing the right organisation and access method affects speed, space usage, and reliability.

Why File Organisation Matters

• Performance: Faster reads/writes and lower seek times.
• Space Efficiency: Reduced fragmentation and overhead.
• Reliability: Lower risk of data loss or broken chains.
• Use-Case Fit: Optimised for sequential logs, random lookups, multimedia, etc.

Common File Organisation (Allocation) Methods

1) Contiguous Allocation

All blocks of a file are stored next to each other on disk.

[Start Block] [Block+1] [Block+2] ... [Block+n]   (all consecutive)

• How it works: Directory stores start block and file length.
• Advantages: Fast sequential and random access; minimal seek time.
• Disadvantages: External fragmentation; difficult to grow files.
• Best for: Static files with known size (e.g., read-only media, large contiguous media files).

2) Linked Allocation

Each file is a linked list of disk blocks scattered anywhere on the disk.

Block A -> Block F -> Block K -> Block Q -> ...
(stored in block pointer fields)

• How it works: Each block stores a pointer to the next block (FAT uses a table of next pointers).
• Advantages: No external fragmentation; easy file growth.
• Disadvantages: Poor random access (must follow the chain); pointer overhead; potential reliability issues if a pointer is corrupted.
• Best for: Sequential workloads (logs, simple append-only files).

3) Indexed Allocation

Each file has an index block (or multiple) that stores addresses of its data blocks.

Index Block:
  [b7, b13, b29, b4, ...]  --> directly point to data blocks

• How it works: Directory stores a pointer to the index block. Data blocks can be anywhere.
• Advantages: Supports direct/random access; avoids external fragmentation.
• Disadvantages: Extra space for indexes; may need multi-level indexes for large files.
• Best for: Mixed workloads requiring both sequential and random access (e.g., general-purpose OS files).

(Note) Extent-Based Allocation

Modern systems often allocate in extents (contiguous runs of blocks), balancing performance and flexibility. Files can grow by adding more extents.

Access Mechanisms (Access Methods)

1) Sequential Access

• Concept: Read/write data in order, from beginning to end.
• Operations: Read next, write next; file pointer moves forward.
• Use cases: Logs, streams, text processing, backup/restore.
• Works best with: Any organisation, but especially linked and contiguous.

2) Direct (Random) Access

• Concept: Jump to any position/record and read or write there.
• Operations: Seek to offset, then read/write.
• Use cases: Databases, index lookups, large files needing quick jumps.
• Works best with: Contiguous or indexed allocation (fast address calculation).

3) Indexed Access (Index-Assisted)

• Concept: Use an index structure to map a logical record number to its physical block quickly.
• Implementation: Index block(s), multi-level indexes, or tree-based structures.
• Use cases: Large files, mixed workloads, frequent random lookups.
• Works best with: Indexed allocation; can emulate direct access without contiguity.

How Organisation Influences Access

• Contiguous allocation: Excellent for sequential and direct access; resizing is hard.
• Linked allocation: Good for sequential; poor for direct/random due to pointer chasing.
• Indexed allocation: Good for both sequential and direct; small indexing overhead.

Small Example: Reading the 10th Record

Assume: fixed-size records, record size = R, block size = B.

Sequential access:
  - Start at record 1; read next until record 10 (simple, but O(n)).

Direct access (contiguous):
  - Byte offset = (10 - 1) * R
  - Physical block = start_block + floor(offset / B)
  - Read the block; take the record at offset % B (O(1)).

Indexed access:
  - Look up block number in index for record 10
  - Read that block; fetch record (O(1) with 1-level index).

Key Points for Exams

• Define file organisation (layout on disk) and access mechanisms (how data is read/written).
• Name and explain three organisations: contiguous, linked, indexed (pros/cons, use cases).
• Describe access methods: sequential, direct, indexed; when to use each.
• Map organisation to access: contiguous (best overall), linked (sequential), indexed (flexible).
• Mention fragmentation and growth issues; note extent-based allocation as a practical compromise.