Theory
The Librarian's Nightmare
Imagine a library with millions of books, but no shelf labels or a master catalog. If a new book arrives, you just toss it into any random empty gap. To find a book later, you would have to scan every single shelf in the building. This is exactly what a computer would face without Disk Space Management. The OS must act as the librarian, maintaining a strict record of where every file starts, ends, and which empty sectors are available to hold new data.
Theory
Three Ways to File Your Data
To store files on a disk, the OS uses one of three primary strategies to manage how clusters (blocks of disk space) are allocated to files:
1. Contiguous Allocation: The OS finds a large, unbroken stretch of free blocks. Like parking a car in a row of adjacent spots. It's incredibly fast to read because the disk head doesn't need to 'jump' around.
2. Linked Allocation: The OS stores files in scattered, non-adjacent blocks. Each block contains a tiny pointer to the address of the next block. It is like a scavenger hunt: you find the first piece, which tells you where the second piece is hidden.
3. Indexed Allocation: The OS creates a dedicated 'Index Block' (like a table of contents) that holds a list of all the addresses where the file parts are stored. You check the index once and then jump directly to the data blocks.
Theory
The Grocery Shopping Analogy
Think of Contiguous as buying a bulk pack of items in one box. It's efficient to carry, but hard to fit if you only have tiny shelf gaps. Think of Linked Allocation as a shopping list where each item tells you the aisle number for the next item, so you have to walk all over the store. Indexed Allocation is like having a perfectly organized digital map of the entire store; you just look at the map once and walk straight to exactly what you need.
Think first
The Fragmentation Trap
If I keep saving and deleting files using Contiguous Allocation, what happens to the free space on my hard drive over time? (Hint: Think about tiny gaps between used blocks).
Show the answer
You end up with 'External Fragmentation.' You might have 500MB of free space total, but it is broken into thousands of tiny, non-adjacent 1KB gaps. You cannot save a 10MB file, even though you have 500MB of 'free space,' because you cannot find a single contiguous chunk large enough to hold it.
Theory
Visualizing Allocation
Picture a tiny 12-block disk (blocks 0 to 11) storing one 4-block file three ways:
- Contiguous: blocks 4, 5, 6, 7, one unbroken run.
- Linked: blocks 2 to 9 to 5 to 11, each block storing the address of the next.
- Indexed: block 3 is the index holding the list (2, 9, 5, 11); read it once, then jump straight to any piece.
Same file, three completely different maps, and every trade-off in this lesson follows from these pictures.
Quiz
Which disk space allocation method is the most prone to external fragmentation?
- Linked Allocation
- Indexed Allocation
- Contiguous Allocation
- Random Allocation
Show the answer
Contiguous Allocation
Contiguous allocation requires a large, unbroken stretch of space. As files of different sizes are created and deleted, the disk becomes pockmarked with small, unusable holes, causing significant external fragmentation.
Formula
Comparison Summary for Exams
Keep this 'cheat sheet' in mind for your exams:
• Contiguous: Fast access, but suffers from severe external fragmentation.
• Linked: No external fragmentation, but slow (must follow pointers) and vulnerable to pointer loss (if one pointer breaks, the rest of the file is lost).
• Indexed: Supports direct access and avoids fragmentation, but the Index Block itself consumes extra storage space.
Theory
Disk Space Accounting
Beyond allocation, the OS must keep track of free space using a Bit Map (or Bit Vector). Each bit on the map represents a disk block: a '1' means the block is free, and a '0' means it is occupied. When the OS needs space, it just scans the bit map for a '1', marks it as '0', and saves the data. It's a highly efficient way to manage gigabytes of data with just a small table in memory!
Summary
Key takeaways
- Disk space management is the OS's ledger for tracking used vs. free storage sectors.
- Contiguous allocation is fast but leads to heavy fragmentation.
- Linked allocation solves fragmentation by chaining blocks but sacrifices access speed.
- Indexed allocation provides the best balance by using an index block for direct address lookup.
- Bit maps are the standard, efficient data structure used by the OS to track free/busy blocks on a disk.