---
title: "File system layers; linked list vs index"
subject: "Operating System"
chapter: 5
key: "semester_6/operating_system:fs-layers-linked-list-vs-index"
source: https://www.bctengineer.com/q/semester_6/operating_system/fs-layers-linked-list-vs-index
site: BCT Engineering
---

# File system layers; linked list vs index

Operating System · Chapter 5: File Systems

- Asked in: 2072 Magh, 4+5 marks
- Video: [Linked allocation and Indexed allocation of Disk Space (Module 4 Lecture 5)](https://www.youtube.com/watch?v=htqjU0IHZ_Q) — Operating System 18EC641 - Dr. Umesh Dixit
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/fs-layers-linked-list-vs-index
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-5

## Question

Explain the role of each layer in a file system. Compare and contrast the linked list allocation and linked list allocation using index method.

## Short answer

Layers: application, logical (metadata), file-organization (logical-to-physical mapping), basic (block I/O, caching), I/O control. Linked list allocation stores the next pointer in each data block, wasting space and making random access slow. FAT (linked list using index) keeps all pointers in a memory table, enabling faster random access but requiring memory proportional to disk blocks.

## Answer

#### Layers of a file system and their roles
```text
 +-----------------------------+
 | Application programs        |
 +-----------------------------+
 | Logical file system         |
 +-----------------------------+
 | File-organization module    |
 +-----------------------------+
 | Basic file system           |
 +-----------------------------+
 | I/O control (device drivers)|
 +-----------------------------+
 | Devices (disk)              |
 +-----------------------------+
```
1. **Application programs:** request file services through system calls (open, read, write).
2. **Logical file system:** manages metadata: directory structure, file control blocks (i-nodes), names, protection and security.
3. **File-organization module:** knows files and their logical blocks and physical blocks; translates logical block addresses to physical ones; handles allocation methods and free-space management.
4. **Basic file system:** issues generic commands to the device driver ("read block 123"); manages buffers and caches of blocks.
5. **I/O control:** device drivers and interrupt handlers that transfer data between memory and disk using low-level commands for the controller.
6. **Devices:** the physical disk.
Layering reduces duplication and eases design, though it adds overhead.

#### Linked list allocation vs linked list with index (FAT)
| Point | Linked list | Linked list using index (FAT) |
|---|---|---|
| Where pointers are | In each data block | In a table (FAT) kept in memory |
| Usable data per block | Block size - pointer | Whole block |
| Random access | Slow, each block read from disk | Faster, the chain is followed in memory |
| Memory required | None | The whole table (entries = number of blocks) |
| Reliability | One damaged pointer loses the rest of the file | The table can be duplicated; one copy damaged is recoverable |
| Scalability | Good for any disk size | Poor for big disks (large table) |
| Example | Original Alto/early systems | MS-DOS FAT12/16/32 |

Both avoid external fragmentation and allow files to grow; the indexed version is quicker but needs memory.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which layer of a file system manages metadata such as directory structure, file control blocks (i-nodes) and protection?
   A. Logical file system
   B. Basic file system
   C. I/O control
   D. File-organization module
   Answer: A. The logical file system handles metadata: directories, FCBs, names, protection and security. (Key point: Logical file system)

2. Which layer translates logical block addresses to physical ones and handles allocation and free-space management?
   A. Logical file system
   B. File-organization module
   C. I/O control (device drivers)
   D. Application programs
   Answer: B. The file-organization module knows logical and physical blocks and performs the translation plus allocation and free-space management. (Key point: File-organization module)

3. What is the main structural difference between plain linked allocation and linked allocation with an index (FAT)?
   A. FAT stores the whole file in contiguous blocks
   B. FAT puts all pointers in the directory entry on disk only
   C. FAT keeps the pointers in a table in memory instead of inside each data block
   D. Plain linked allocation keeps pointers in a table in memory
   Answer: C. In plain linked allocation each block holds a pointer to the next; FAT moves all pointers to a table kept in memory. (Key point: Where pointers are kept)

4. Why is random access faster with FAT than with plain linked allocation?
   A. Blocks are stored contiguously so no chain is needed
   B. Each block stores its own index number
   C. The disk head does not need to seek at all
   D. The chain of blocks is followed in memory instead of reading each block from disk
   Answer: D. Plain linked allocation must read every block from disk to find the next pointer; FAT follows the chain in the in-memory table. (Key point: Random access in FAT)

## Related in Operating System

- [File system layout; i-node vs linked list](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layout-inode-vs-linked-list) — Operating System, chapter 5
- [File system vs virtual memory; contiguous allocation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-vs-virtual-memory-contiguous-tape) — Operating System, chapter 5
- [Linked list file system; block size impact](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-linked-list-block-size) — Operating System, chapter 5
- [File allocation and access methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-allocation-access-methods) — Operating System, chapter 5
- [File allocation methods; free space management](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-allocation-free-space-methods) — Operating System, chapter 5, asked 2×
- [File and attributes; allocation methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-attributes-allocation-methods) — Operating System, chapter 5

## Related in other subjects

- [Compare and contrast pollution in a city](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Acompare-contrast-pollution-city-nepal) — Communication English, chapter 1
- [Switching, circuit vs packet, X.25 layers](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aswitching-define-compare-x25-layers) — Data Communication, chapter 7
- [Operating system layers](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aos-layers) — Distributed System, chapter 3
- [DS vs centralized; layers of transparency](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ads-over-centralized-transparency) — Distributed System, chapter 1