File Allocation
When you’re programming, you simply do a malloc. Or, if you are dealing with a Vector (C++), you resize to double the size of the array. This is in main memory.
But how do you do allocation in secondary memory, where storage is more permanent?
- Many of these ideas transfer over from Memory Partitioning
First, see Record Blocking to understand how records are converted into blocks.
There are 4 main ways that are introduced:
- Preallocation
- Contiguous Allocation
- Chained Allocation
- Indexed Allocation
Preallocation
This is like mallocing the max size of the file.
- Need the maximum size for the file at the time of creation
- Difficult to reliably estimate the maximum potential size of the file
- Tend to overestimate file size so as not to run out of space
Contiguous Allocation
- Single set of blocks is allocated to a file at the time of creation
- Only a single entry in the file allocation table (Starting block and length of the file)
- External fragmentation will occur (Need to perform compaction)
Chained Allocation
- Allocation on basis of individual block
- Each block contains a pointer to the next block in the chain
- Only single entry in the file allocation table
- Starting block and length of file
- No external fragmentation
- Best for sequential files
- No accommodation of the principle of locality
Indexed Allocation
- File allocation table contains a separate one-level index for each file
- The index has one entry for each portion allocated to the file
- The file allocation table contains block number for the index
Indexed allocation supports both sequential and direct access to the file and thus is the most popular form of file allocation.
