disk organization
Summary
File block allocation
| Method | Core Idea | Access Type | Storage Overhead | Advantages | Disadvantages |
|---|---|---|---|---|---|
| contiguous allocation | file stored in consecutive blocks | sequential + random | minimal (start + length) | - simple file tracking - fast access | - external fragmentation - hard to grow files |
| linked list allocation | each block points to the next block | sequential | pointer per block | - no external fragmentation - easy file growth | - slow random access - pointer overhead - reliability issues if pointer lost/incorrect |
| FAT allocation | links stored in a central FAT | sequential | FAT | - faster random access - easier traversal | - FAT can be large |
| indexed allocation | each file has an index block containing pointers to all its blocks | random + sequential | index block per file | - fast direct access - less memory overhead, only index block of opened file needs to be in memory | - index block overhead - waste for small files - multi-level index for large files |
Concept
- disk - 1D array of logical blocks
- logical blocks are mapped into disk sectors
Master Boot Record(MBR)
- at sector 0
- has a partition table
- followed by one or more partitions
- contains:
- OS boot-up info
Partition
- contain the actual files
- contains:
- partition details - number of blocks
- directory structure
- file info
- file data
Allocating files
- files are a set of logical blocks
- implementation needs to:
- keep track of logical blocks
- allow efficient access
- effectively use disk space
- using fixed blocks -> always has internal fragmentation
Contiguous allocation
- allocate consecutive blocks to each file
- file info stores first block and size
