Loading learning content...
Imagine organizing a library where every book must occupy consecutive shelves—War and Peace takes shelves 47 through 52, and no other book can interrupt that sequence. This is the essence of contiguous allocation in file systems: files occupy a sequence of adjacent blocks on the storage device, with no gaps or fragmentation within the file.
This simple, intuitive approach was the first allocation strategy used in early file systems and remains relevant today for specific use cases. Understanding contiguous allocation is essential because it reveals the fundamental trade-offs in storage management—trade-offs that every modern file system must navigate, even when using more sophisticated allocation schemes.
By the end of this page, you will understand the precise mechanics of contiguous allocation, how directory entries store file locations, the mathematical relationship between file position and disk address, and why this deceptively simple approach creates both exceptional performance and significant management challenges.
Contiguous allocation is a file allocation strategy where each file occupies a set of contiguous (physically adjacent) blocks on the disk. If a file requires n blocks and starts at block b, then the file occupies blocks b, b+1, b+2, ..., b+n-1.
The Fundamental Principle:
The contiguous allocation method requires that each file occupy a set of blocks that are consecutive on the disk. This is the simplest and most natural allocation strategy, mirroring how physical objects (books on a shelf, cars in a parking lot) occupy space.
How It Works:
| Component | Description | Implementation |
|---|---|---|
| Starting Block | The first block number where the file begins | Stored in directory entry; absolute disk address |
| Length (Block Count) | Number of consecutive blocks the file occupies | Stored in directory entry; integer value |
| Block Sequence | The implicit set of blocks b, b+1, ..., b+n-1 | Computed from start + length; never stored explicitly |
| Directory Entry | Metadata structure holding file information | Contains filename, start block, length, attributes |
Contiguous allocation was used in early operating systems including IBM's OS/360 and DEC's RT-11. These systems often required users to declare the maximum file size at creation time—a constraint that modern users would find unacceptable but was reasonable given the hardware limitations and usage patterns of the era.
In contiguous allocation, the directory entry for each file is remarkably simple—it needs to store only the starting block address and the length (number of blocks). This minimalist approach yields both simplicity and efficiency.
Directory Entry Components:
A typical directory entry in a contiguous allocation system contains:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
/* * Directory Entry Structure for Contiguous Allocation * * This structure represents how a file system using contiguous * allocation stores file metadata in directory entries. */ #include <stdint.h>#include <time.h> #define MAX_FILENAME_LENGTH 255#define BLOCK_SIZE 4096 /* 4 KB blocks - typical modern size */ /* File type enumeration */typedef enum { FILE_TYPE_REGULAR = 0x01, FILE_TYPE_DIRECTORY = 0x02, FILE_TYPE_SYMLINK = 0x03, FILE_TYPE_DEVICE = 0x04} file_type_t; /* Permission bits (Unix-style) */typedef struct { uint16_t owner_read : 1; uint16_t owner_write : 1; uint16_t owner_exec : 1; uint16_t group_read : 1; uint16_t group_write : 1; uint16_t group_exec : 1; uint16_t other_read : 1; uint16_t other_write : 1; uint16_t other_exec : 1; uint16_t reserved : 7;} file_permissions_t; /* * Contiguous Allocation Directory Entry * * Note how simple this is compared to linked or indexed allocation: * - Only TWO fields needed to locate ALL file data: start_block + length * - No pointers, no index blocks, no FAT entries to follow */typedef struct { /* File identification */ char filename[MAX_FILENAME_LENGTH + 1]; /* Null-terminated filename */ /* ====== THE KEY FIELDS FOR CONTIGUOUS ALLOCATION ====== */ uint64_t start_block; /* Starting block number on disk */ uint32_t block_count; /* Number of contiguous blocks */ /* ======================================================= */ /* File metadata */ uint64_t file_size; /* Actual file size in bytes */ file_type_t file_type; /* Type of file */ file_permissions_t perms; /* Permission bits */ /* Ownership */ uint32_t owner_uid; /* User ID of owner */ uint32_t owner_gid; /* Group ID of owner */ /* Timestamps */ time_t created_time; /* File creation time */ time_t modified_time; /* Last modification time */ time_t accessed_time; /* Last access time */ } contiguous_dir_entry_t; /* * Example: Calculating disk address from file position * * Given: file starts at block 1000, position = 10,500 bytes * Block size = 4096 bytes * * Block offset = position / BLOCK_SIZE = 10500 / 4096 = 2 * Byte offset within block = position % BLOCK_SIZE = 10500 % 4096 = 2308 * * Disk block = start_block + block_offset = 1000 + 2 = 1002 * Disk address = (disk_block * BLOCK_SIZE) + byte_offset * = (1002 * 4096) + 2308 = 4,106,500 */static inline uint64_t calculate_disk_address( const contiguous_dir_entry_t *entry, uint64_t file_position) { /* Calculate which block within the file */ uint32_t block_offset = file_position / BLOCK_SIZE; /* Calculate offset within that block */ uint32_t byte_offset = file_position % BLOCK_SIZE; /* Bounds check: ensure we're within the file's allocated blocks */ if (block_offset >= entry->block_count) { return (uint64_t)-1; /* Error: position beyond file */ } /* Calculate absolute disk block number */ uint64_t disk_block = entry->start_block + block_offset; /* Return absolute disk byte address */ return (disk_block * BLOCK_SIZE) + byte_offset;} /* * Example usage: * * contiguous_dir_entry_t myfile = { * .filename = "data.bin", * .start_block = 1000, * .block_count = 100, // 100 blocks = 400 KB * .file_size = 409600, * ... * }; * * // To read byte 50,000 of the file: * uint64_t disk_addr = calculate_disk_address(&myfile, 50000); * // disk_addr = block 1000 + (50000/4096) = block 1012, offset 688 * // Absolute address = 1012 * 4096 + 688 = 4,145,840 */The Elegance of Two Numbers:
The beauty of contiguous allocation lies in its simplicity. With just two pieces of information—start and length—the file system can:
This minimal metadata footprint means directory entries are small, more entries fit in a single block, and directory operations are fast.
Understanding how logical file positions translate to physical disk addresses is fundamental to comprehending contiguous allocation's efficiency.
The Address Translation Formula:
Given a file with starting block S and a request to access byte position P within the file:
Block Number = S + floor(P / block_size)
Offset within Block = P mod block_size
Absolute Disk Address = Block_Number × block_size + Offset
This calculation is O(1)—constant time regardless of file size or position being accessed. No pointer chains to follow, no index blocks to read, no tables to consult.
| File Position | Start Block | Calculation | Result Block | Offset |
|---|---|---|---|---|
| 0 bytes | 100 | 100 + (0 ÷ 4096) | Block 100 | 0 |
| 4,096 bytes | 100 | 100 + (4096 ÷ 4096) | Block 101 | 0 |
| 10,000 bytes | 100 | 100 + (10000 ÷ 4096) = 100 + 2 | Block 102 | 1,808 |
| 1 MB (1,048,576) | 100 | 100 + (1048576 ÷ 4096) = 100 + 256 | Block 356 | 0 |
| 1 GB (1,073,741,824) | 100 | 100 + (1073741824 ÷ 4096) | Block 262,244 | 0 |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
/* * Complete Address Translation Implementation * * Demonstrates the mathematical elegance of contiguous allocation: * - O(1) address calculation for any file position * - No disk I/O required to compute addresses * - Trivial bounds checking */ #include <stdio.h>#include <stdint.h>#include <stdbool.h> #define BLOCK_SIZE_BYTES 4096#define SECTOR_SIZE_BYTES 512#define SECTORS_PER_BLOCK (BLOCK_SIZE_BYTES / SECTOR_SIZE_BYTES) typedef struct { uint64_t block_number; /* Logical block number */ uint32_t block_offset; /* Byte offset within the block */ uint64_t absolute_address; /* Absolute byte address on disk */ uint64_t sector_number; /* Physical sector (for disk driver) */ uint32_t sector_offset; /* Offset within sector */} disk_location_t; typedef struct { uint64_t start_block; /* First block of the file */ uint32_t block_count; /* Total blocks allocated */ uint64_t file_size_bytes; /* Actual file size */} file_allocation_t; /** * Translates a logical file position to physical disk location. * * This function demonstrates WHY contiguous allocation enables * such fast random access: the entire calculation is pure arithmetic * with no disk I/O, no pointer chasing, no indirection. * * @param file File allocation information * @param position Byte position within the file (0-indexed) * @param location Output: physical disk location * @return true if position is valid, false otherwise */bool translate_position( const file_allocation_t *file, uint64_t position, disk_location_t *location) { /* Step 1: Bounds check - is this position within the file? */ if (position >= file->file_size_bytes) { return false; /* Position beyond end of file */ } /* Step 2: Calculate which block within the file contains this position */ uint64_t block_index = position / BLOCK_SIZE_BYTES; /* Step 3: Verify block is within allocated range */ if (block_index >= file->block_count) { return false; /* Position in unallocated region */ } /* Step 4: Calculate the absolute disk block number */ location->block_number = file->start_block + block_index; /* Step 5: Calculate offset within the block */ location->block_offset = position % BLOCK_SIZE_BYTES; /* Step 6: Calculate absolute disk address (byte-addressable) */ location->absolute_address = (location->block_number * BLOCK_SIZE_BYTES) + location->block_offset; /* Step 7: Calculate sector-level addressing (for disk driver) */ location->sector_number = (location->block_number * SECTORS_PER_BLOCK) + (location->block_offset / SECTOR_SIZE_BYTES); location->sector_offset = location->block_offset % SECTOR_SIZE_BYTES; return true;} /** * Example: Reading a range of bytes from a file * * This shows how contiguous allocation enables efficient planning * of read operations - we know exactly which blocks to read before * issuing any I/O. */typedef struct { uint64_t first_block; uint64_t last_block; uint32_t first_block_offset; uint32_t last_block_offset; uint32_t total_blocks;} read_plan_t; bool plan_read_operation( const file_allocation_t *file, uint64_t start_position, uint64_t byte_count, read_plan_t *plan) { /* Validate range */ uint64_t end_position = start_position + byte_count - 1; if (end_position >= file->file_size_bytes) { return false; } /* Calculate block range */ plan->first_block = file->start_block + (start_position / BLOCK_SIZE_BYTES); plan->last_block = file->start_block + (end_position / BLOCK_SIZE_BYTES); plan->first_block_offset = start_position % BLOCK_SIZE_BYTES; plan->last_block_offset = end_position % BLOCK_SIZE_BYTES; plan->total_blocks = plan->last_block - plan->first_block + 1; return true;} /* Demonstration */void demonstrate_address_calculation(void) { file_allocation_t example_file = { .start_block = 1000, .block_count = 500, /* 500 blocks = 2 MB */ .file_size_bytes = 2000000 /* ~1.9 MB actual data */ }; printf("File: starts at block 1000, 500 blocks, 2MB size\n"); printf("Block size: 4096 bytes\n\n"); /* Test various positions */ uint64_t test_positions[] = {0, 100, 4096, 4097, 100000, 1000000}; int num_tests = sizeof(test_positions) / sizeof(test_positions[0]); for (int i = 0; i < num_tests; i++) { disk_location_t loc; uint64_t pos = test_positions[i]; if (translate_position(&example_file, pos, &loc)) { printf("Position %8lu -> Block %6lu, Offset %4u\n", pos, loc.block_number, loc.block_offset); } } /* Plan a read operation */ printf("\nPlanning read of 10,000 bytes starting at position 50,000:\n"); read_plan_t plan; if (plan_read_operation(&example_file, 50000, 10000, &plan)) { printf(" Read blocks %lu through %lu (%u blocks)\n", plan.first_block, plan.last_block, plan.total_blocks); printf(" First block offset: %u, Last block offset: %u\n", plan.first_block_offset, plan.last_block_offset); }}The ability to compute any file location with simple arithmetic means contiguous allocation achieves O(1) random access with ZERO additional disk I/O for address resolution. Compare this to linked allocation (O(n) traversal) or indexed allocation (potentially multiple index block reads). For read-intensive workloads on static files, this is optimal.
To truly understand contiguous allocation, we must visualize how files are physically arranged on the disk. Each file occupies an unbroken sequence of blocks, and the disk can be viewed as a linear array of blocks with files occupying various segments.
Visual Representation:
Consider a disk with 100 blocks (numbered 0-99) containing several files:
| File Name | Start Block | Block Count | Size (bytes) |
|---|---|---|---|
| FileA.dat | 4 | 10 | 40,960 |
| FileB.dat | 20 | 15 | 61,440 |
| FileC.dat | 40 | 20 | 81,920 |
| FileD.dat | 70 | 15 | 61,440 |
Key Observations from This Layout:
This visualization immediately reveals the fundamental challenge of contiguous allocation: external fragmentation. The free space becomes scattered across the disk, making it impossible to allocate large files even when sufficient total space exists.
In the layout above, 36% of the disk is free, yet we cannot create any file larger than 15 blocks. This is external fragmentation—free space exists but isn't usable because it's not contiguous. This fundamental limitation drives the need for either compaction (expensive) or alternative allocation strategies (linked, indexed).
When a new file is created, the file system must find a contiguous sequence of free blocks large enough to hold it. This is the contiguous allocation problem—identical to the memory allocation problem we encounter in contiguous memory allocation.
Common Allocation Strategies:
The same algorithms used for memory allocation apply:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247
/* * Contiguous Block Allocation Algorithms * * Implementation of the four classic allocation strategies. * These are used when creating new files or extending existing ones. */ #include <stdio.h>#include <stdint.h>#include <stdbool.h>#include <limits.h> #define TOTAL_BLOCKS 10000#define INVALID_BLOCK UINT64_MAX /* Free space entry in the free list */typedef struct free_extent { uint64_t start_block; uint32_t block_count; struct free_extent *next;} free_extent_t; /* Free space manager state */typedef struct { free_extent_t *free_list; uint64_t next_fit_position; /* For Next Fit algorithm */ uint64_t total_free_blocks; uint32_t free_extent_count;} free_space_manager_t; /** * First Fit Allocation * * Time Complexity: O(n) where n = number of free extents * Behavior: Allocates from the first hole that fits * Pros: Fast (stops at first match) * Cons: Fragments the beginning of the disk */uint64_t allocate_first_fit(free_space_manager_t *mgr, uint32_t blocks_needed) { free_extent_t *current = mgr->free_list; free_extent_t *prev = NULL; while (current != NULL) { if (current->block_count >= blocks_needed) { /* Found a suitable hole */ uint64_t allocated_start = current->start_block; if (current->block_count == blocks_needed) { /* Exact fit: remove this extent entirely */ if (prev == NULL) { mgr->free_list = current->next; } else { prev->next = current->next; } mgr->free_extent_count--; /* free(current); -- Memory management */ } else { /* Partial allocation: shrink this extent */ current->start_block += blocks_needed; current->block_count -= blocks_needed; } mgr->total_free_blocks -= blocks_needed; return allocated_start; } prev = current; current = current->next; } return INVALID_BLOCK; /* No suitable hole found */} /** * Best Fit Allocation * * Time Complexity: O(n) - must scan entire list * Behavior: Finds the smallest hole that fits * Pros: Minimizes wasted space per allocation * Cons: Creates many tiny, useless fragments */uint64_t allocate_best_fit(free_space_manager_t *mgr, uint32_t blocks_needed) { free_extent_t *current = mgr->free_list; free_extent_t *best = NULL; free_extent_t *best_prev = NULL; free_extent_t *prev = NULL; uint32_t best_size = UINT32_MAX; /* Scan entire list to find smallest sufficient hole */ while (current != NULL) { if (current->block_count >= blocks_needed && current->block_count < best_size) { best = current; best_prev = prev; best_size = current->block_count; /* Optimization: exact fit is optimal, stop early */ if (best_size == blocks_needed) { break; } } prev = current; current = current->next; } if (best == NULL) { return INVALID_BLOCK; } uint64_t allocated_start = best->start_block; if (best->block_count == blocks_needed) { if (best_prev == NULL) { mgr->free_list = best->next; } else { best_prev->next = best->next; } mgr->free_extent_count--; } else { best->start_block += blocks_needed; best->block_count -= blocks_needed; } mgr->total_free_blocks -= blocks_needed; return allocated_start;} /** * Worst Fit Allocation * * Time Complexity: O(n) - must scan entire list * Behavior: Finds the largest hole and allocates from it * Pros: Leaves larger remaining fragments * Cons: Quickly consumes large holes that might be needed */uint64_t allocate_worst_fit(free_space_manager_t *mgr, uint32_t blocks_needed) { free_extent_t *current = mgr->free_list; free_extent_t *worst = NULL; free_extent_t *worst_prev = NULL; free_extent_t *prev = NULL; uint32_t worst_size = 0; while (current != NULL) { if (current->block_count >= blocks_needed && current->block_count > worst_size) { worst = current; worst_prev = prev; worst_size = current->block_count; } prev = current; current = current->next; } if (worst == NULL) { return INVALID_BLOCK; } uint64_t allocated_start = worst->start_block; if (worst->block_count == blocks_needed) { if (worst_prev == NULL) { mgr->free_list = worst->next; } else { worst_prev->next = worst->next; } mgr->free_extent_count--; } else { worst->start_block += blocks_needed; worst->block_count -= blocks_needed; } mgr->total_free_blocks -= blocks_needed; return allocated_start;} /** * Next Fit Allocation * * Time Complexity: O(n) worst case, but often faster in practice * Behavior: Like First Fit, but resumes from last allocation position * Pros: Distributes fragmentation evenly, often faster than First Fit * Cons: May miss good holes at the beginning of the list */uint64_t allocate_next_fit(free_space_manager_t *mgr, uint32_t blocks_needed) { free_extent_t *current = mgr->free_list; free_extent_t *prev = NULL; bool wrapped = false; /* Skip to the next-fit starting position */ while (current != NULL && current->start_block < mgr->next_fit_position) { prev = current; current = current->next; } /* If we've gone past the list, wrap to beginning */ if (current == NULL) { current = mgr->free_list; prev = NULL; wrapped = true; } free_extent_t *start = current; while (true) { if (current != NULL && current->block_count >= blocks_needed) { uint64_t allocated_start = current->start_block; /* Update next-fit position for future allocations */ mgr->next_fit_position = allocated_start + blocks_needed; if (current->block_count == blocks_needed) { if (prev == NULL) { mgr->free_list = current->next; } else { prev->next = current->next; } mgr->free_extent_count--; } else { current->start_block += blocks_needed; current->block_count -= blocks_needed; } mgr->total_free_blocks -= blocks_needed; return allocated_start; } prev = current; current = (current != NULL) ? current->next : NULL; /* Wrap around to beginning */ if (current == NULL && !wrapped) { current = mgr->free_list; prev = NULL; wrapped = true; } /* We've checked everything */ if (current == start || (current == NULL && wrapped)) { break; } } return INVALID_BLOCK;}| Algorithm | Time | Fragmentation Pattern | Best Use Case |
|---|---|---|---|
| First Fit | O(n) avg, fast in practice | Concentrates at disk start | General purpose, quick allocation |
| Best Fit | O(n) always | Many tiny fragments | When minimizing per-allocation waste matters |
| Worst Fit | O(n) always | Reduces large holes quickly | Rarely optimal; theoretical interest |
| Next Fit | O(n) worst, often better | Distributed evenly | Circular allocation patterns |
Implementing contiguous allocation requires careful attention to several practical concerns that affect both correctness and performance.
Free Space Tracking:
The file system must maintain a record of which disk regions are free. Common approaches include:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164
/* * Bitmap-Based Free Space Management * * A bitmap is simple and efficient for contiguous allocation: * - Each bit represents one block * - Fast block status check: O(1) * - Finding contiguous space: O(n) scan */ #include <stdio.h>#include <stdint.h>#include <stdbool.h>#include <string.h> #define TOTAL_BLOCKS 1000000 /* 1 million blocks */#define BITS_PER_WORD 64#define BITMAP_SIZE ((TOTAL_BLOCKS + BITS_PER_WORD - 1) / BITS_PER_WORD) typedef struct { uint64_t bitmap[BITMAP_SIZE]; uint64_t total_blocks; uint64_t free_blocks;} bitmap_allocator_t; /* Initialize bitmap with all blocks free */void bitmap_init(bitmap_allocator_t *alloc) { memset(alloc->bitmap, 0, sizeof(alloc->bitmap)); alloc->total_blocks = TOTAL_BLOCKS; alloc->free_blocks = TOTAL_BLOCKS;} /* Check if a specific block is free */static inline bool is_block_free(bitmap_allocator_t *alloc, uint64_t block) { uint64_t word_index = block / BITS_PER_WORD; uint64_t bit_index = block % BITS_PER_WORD; return (alloc->bitmap[word_index] & (1ULL << bit_index)) == 0;} /* Mark a block as allocated */static inline void mark_allocated(bitmap_allocator_t *alloc, uint64_t block) { uint64_t word_index = block / BITS_PER_WORD; uint64_t bit_index = block % BITS_PER_WORD; alloc->bitmap[word_index] |= (1ULL << bit_index); alloc->free_blocks--;} /* Mark a block as free */static inline void mark_free(bitmap_allocator_t *alloc, uint64_t block) { uint64_t word_index = block / BITS_PER_WORD; uint64_t bit_index = block % BITS_PER_WORD; alloc->bitmap[word_index] &= ~(1ULL << bit_index); alloc->free_blocks++;} /** * Find a contiguous region of free blocks using word-level optimization. * * Key insight: If a bitmap word is all 1s (0xFFFFFFFFFFFFFFFF), * we know all 64 blocks in that word are allocated, so skip it entirely. */uint64_t find_contiguous_blocks( bitmap_allocator_t *alloc, uint32_t blocks_needed) { uint64_t consecutive = 0; uint64_t start_block = 0; for (uint64_t block = 0; block < alloc->total_blocks; block++) { /* Word-level optimization: skip fully allocated words */ if (block % BITS_PER_WORD == 0) { uint64_t word_idx = block / BITS_PER_WORD; if (alloc->bitmap[word_idx] == UINT64_MAX) { /* All 64 bits set = all allocated, skip entire word */ consecutive = 0; continue; } } if (is_block_free(alloc, block)) { if (consecutive == 0) { start_block = block; } consecutive++; if (consecutive >= blocks_needed) { /* Found sufficient contiguous space! */ /* Mark all blocks as allocated */ for (uint64_t i = 0; i < blocks_needed; i++) { mark_allocated(alloc, start_block + i); } return start_block; } } else { consecutive = 0; } } return UINT64_MAX; /* Failed: no contiguous region found */} /** * Free a contiguous region (when file is deleted) */void free_contiguous_blocks( bitmap_allocator_t *alloc, uint64_t start_block, uint32_t block_count) { for (uint32_t i = 0; i < block_count; i++) { mark_free(alloc, start_block + i); }} /** * Fragmentation statistics */typedef struct { uint32_t free_extent_count; /* Number of free regions */ uint64_t largest_extent; /* Size of largest free region */ uint64_t total_free_blocks; /* Total free space */ double fragmentation_ratio; /* 1 - (largest / total) */} fragmentation_stats_t; void calculate_fragmentation( bitmap_allocator_t *alloc, fragmentation_stats_t *stats) { stats->free_extent_count = 0; stats->largest_extent = 0; stats->total_free_blocks = 0; uint64_t current_extent = 0; for (uint64_t block = 0; block < alloc->total_blocks; block++) { if (is_block_free(alloc, block)) { current_extent++; stats->total_free_blocks++; } else { if (current_extent > 0) { stats->free_extent_count++; if (current_extent > stats->largest_extent) { stats->largest_extent = current_extent; } current_extent = 0; } } } /* Handle trailing free extent */ if (current_extent > 0) { stats->free_extent_count++; if (current_extent > stats->largest_extent) { stats->largest_extent = current_extent; } } /* Calculate fragmentation ratio */ if (stats->total_free_blocks > 0) { stats->fragmentation_ratio = 1.0 - ((double)stats->largest_extent / stats->total_free_blocks); } else { stats->fragmentation_ratio = 0.0; }}For a 1 TB disk with 4 KB blocks, you have 256 million blocks. The bitmap requires 256 million bits = 32 MB. This 32 MB bitmap can be kept in memory for fast allocation decisions, or stored on disk with portions cached. Modern systems typically keep the entire allocation bitmap in RAM.
Despite its fragmentation challenges, contiguous allocation remains the optimal choice for certain scenarios. Understanding when it excels helps us appreciate its continued relevance.
Ideal Use Cases:
We've established the foundational understanding of contiguous allocation in file systems. Let's consolidate our learning:
start + (position / block_size).What's Next:
Now that we understand the structure of contiguous allocation, we'll explore its greatest strength in detail: fast sequential access. We'll examine why reading a contiguously allocated file is significantly faster than other allocation methods, diving into disk mechanics, prefetching, DMA optimization, and real performance measurements.
You now understand the fundamentals of contiguous block allocation—how files occupy consecutive disk blocks, how addresses are calculated in constant time, and how directory entries store the minimal metadata needed. Next, we'll see why this layout delivers exceptional sequential access performance.