Skip to main content

File system layers; linked list vs index

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.

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

Layers of a file system and their roles

 +-----------------------------+
 | 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)

PointLinked listLinked list using index (FAT)
Where pointers areIn each data blockIn a table (FAT) kept in memory
Usable data per blockBlock size - pointerWhole block
Random accessSlow, each block read from diskFaster, the chain is followed in memory
Memory requiredNoneThe whole table (entries = number of blocks)
ReliabilityOne damaged pointer loses the rest of the fileThe table can be duplicated; one copy damaged is recoverable
ScalabilityGood for any disk sizePoor for big disks (large table)
ExampleOriginal Alto/early systemsMS-DOS FAT12/16/32

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 5 questions →