文件分配方式
文件分配方式是文件系统管理存储空间的核心技术，它决定了文件如何在存储设备上组织和访问。不同的分配方式在性能、空间利用率和实现复杂度方面各有优劣。
文件分配的基本概念
什么是文件分配
**文件分配（File Allocation）**是指文件系统为文件分配存储空间的方式，它决定了文件数据在存储设备上的物理组织方式。
分配的基本单位
- 扇区（Sector）：磁盘的最小读写单位，通常为 512 字节
- 块（Block）：文件系统分配的基本单位，通常为 4KB 或更大
- 簇（Cluster）：某些文件系统使用的分配单位
分配策略的目标
- 高效访问：支持快速的文件读写操作
- 空间利用：最大化存储空间的利用率
- 碎片管理：最小化存储碎片
- 扩展性：支持文件大小的动态变化
连续分配（Contiguous Allocation）
连续分配是最简单的文件分配方式，文件的所有数据块在存储设备上连续存放。
基本原理
// 连续分配的数据结构
struct contiguous_file {
int start_block; // 起始块号
int block_count; // 块数量
int file_size; // 文件大小
char filename[256]; // 文件名
};
// 文件分配表
struct allocation_table {
struct contiguous_file files[MAX_FILES];
int file_count;
int free_blocks[MAX_BLOCKS];
int free_block_count;
};
分配算法
首次适应算法（First Fit）
// 首次适应算法实现
int first_fit_allocate(int file_size, int block_size) {
int blocks_needed = (file_size + block_size - 1) / block_size;
int consecutive_blocks = 0;
int start_block = -1;
for (int i = 0; i < TOTAL_BLOCKS; i++) {
if (is_block_free(i)) {
if (consecutive_blocks == 0) {
start_block = i;
}
consecutive_blocks++;
if (consecutive_blocks >= blocks_needed) {
// 找到足够的连续块
mark_blocks_used(start_block, blocks_needed);
return start_block;
}
} else {
consecutive_blocks = 0;
}
}
return -1; // 没有找到足够的连续空间
}
最佳适应算法（Best Fit）
// 最佳适应算法实现
int best_fit_allocate(int file_size, int block_size) {
int blocks_needed = (file_size + block_size - 1) / block_size;
int best_start = -1;
int best_size = INT_MAX;
int current_start = -1;
int current_size = 0;
for (int i = 0; i < TOTAL_BLOCKS; i++) {
if (is_block_free(i)) {
if (current_start == -1) {
current_start = i;
}
current_size++;
} else {
if (current_size >= blocks_needed && current_size < best_size) {
best_start = current_start;
best_size = current_size;
}
current_start = -1;
current_size = 0;
}
}
if (best_start != -1) {
mark_blocks_used(best_start, blocks_needed);
return best_start;
}
return -1;
}
最坏适应算法（Worst Fit）
// 最坏适应算法实现
int worst_fit_allocate(int file_size, int block_size) {
int blocks_needed = (file_size + block_size - 1) / block_size;
int worst_start = -1;
int worst_size = 0;
int current_start = -1;
int current_size = 0;
for (int i = 0; i < TOTAL_BLOCKS; i++) {
if (is_block_free(i)) {
if (current_start == -1) {
current_start = i;
}
current_size++;
} else {
if (current_size >= blocks_needed && current_size > worst_size) {
worst_start = current_start;
worst_size = current_size;
}
current_start = -1;
current_size = 0;
}
}
if (worst_start != -1) {
mark_blocks_used(worst_start, blocks_needed);
return worst_start;
}
return -1;
}
优缺点分析
优点
- 顺序访问快：文件数据连续存储，顺序访问效率高
- 实现简单：分配和释放算法简单
- 随机访问快：可以直接计算任意位置的地址
缺点
- 外部碎片：删除文件后留下难以利用的小块空间
- 预分配问题：需要预先知道文件大小
- 扩展困难：文件扩展时需要重新分配空间
适用场景
- 文件大小相对固定的系统
- 顺序访问为主的应用
- 存储空间充足的环境
链接分配（Linked Allocation）
链接分配使用链表结构组织文件数据，每个数据块包含指向下一个块的指针。
基本原理
// 链接分配的数据块结构
struct linked_block {
char data[BLOCK_SIZE - 4]; // 数据部分
int next_block; // 指向下一个块的指针
int is_last; // 是否为最后一个块
};
// 文件控制块
struct linked_file {
int first_block; // 第一个数据块
int last_block; // 最后一个数据块
int file_size; // 文件大小
char filename[256]; // 文件名
};
分配实现
// 链接分配的文件创建
int create_linked_file(const char* filename, int file_size) {
int blocks_needed = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
int first_block = -1;
int current_block = -1;
int prev_block = -1;
// 分配第一个块
first_block = allocate_free_block();
if (first_block == -1) return -1;
current_block = first_block;
// 分配后续块
for (int i = 1; i < blocks_needed; i++) {
int next_block = allocate_free_block();
if (next_block == -1) {
// 分配失败，释放已分配的块
free_linked_blocks(first_block);
return -1;
}
// 设置前一个块的指针
set_next_block(current_block, next_block);
prev_block = current_block;
current_block = next_block;
}
// 设置最后一个块
set_next_block(current_block, -1);
set_last_block_flag(current_block, 1);
// 创建文件控制块
struct linked_file* file = create_file_control_block(filename, first_block, current_block, file_size);
return file->file_id;
}
文件访问
// 链接分配的文件读取
int read_linked_file(int file_id, char* buffer, int offset, int size) {
struct linked_file* file = get_file_control_block(file_id);
if (file == NULL) return -1;
int current_block = file->first_block;
int bytes_read = 0;
int current_offset = 0;
// 定位到起始块
while (current_offset < offset && current_block != -1) {
current_block = get_next_block(current_block);
current_offset += BLOCK_SIZE;
}
// 读取数据
while (bytes_read < size && current_block != -1) {
int bytes_to_read = min(BLOCK_SIZE, size - bytes_read);
int block_offset = (offset + bytes_read) % BLOCK_SIZE;
read_block_data(current_block, buffer + bytes_read, block_offset, bytes_to_read);
bytes_read += bytes_to_read;
current_block = get_next_block(current_block);
}
return bytes_read;
}
优缺点分析
优点
- 无外部碎片：每个块都可以独立分配
- 动态扩展：文件可以动态增长
- 空间利用率高：所有空闲块都可以被利用
缺点
- 随机访问慢：需要遍历链表才能访问指定位置
- 可靠性差：一个块损坏会影响整个文件
- 空间开销：每个块需要存储指针信息
变种：文件分配表（FAT）
FAT 是链接分配的一种改进，将指针信息集中存储在文件分配表中。
// FAT文件分配表结构
struct fat_entry {
int next_block; // 下一个块号
int is_free; // 是否空闲
int is_bad; // 是否为坏块
int is_eof; // 是否为文件结束
};
struct fat_file_system {
struct fat_entry fat_table[MAX_BLOCKS];
int root_directory_start;
int free_block_count;
};
索引分配（Indexed Allocation）
索引分配为每个文件创建一个索引块，索引块中存储文件所有数据块的地址。
基本原理
// 索引分配的数据结构
struct index_block {
int block_addresses[MAX_BLOCKS_PER_INDEX]; // 数据块地址
int block_count; // 块数量
int next_index_block; // 下一个索引块
};
struct indexed_file {
int index_block; // 索引块号
int file_size; // 文件大小
char filename[256]; // 文件名
};
单级索引
// 单级索引分配
int create_indexed_file(const char* filename, int file_size) {
int blocks_needed = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
// 分配索引块
int index_block = allocate_free_block();
if (index_block == -1) return -1;
struct index_block* index = get_index_block(index_block);
index->block_count = 0;
index->next_index_block = -1;
// 分配数据块
for (int i = 0; i < blocks_needed; i++) {
int data_block = allocate_free_block();
if (data_block == -1) {
// 分配失败，释放已分配的块
free_indexed_blocks(index_block);
return -1;
}
index->block_addresses[i] = data_block;
index->block_count++;
}
// 创建文件控制块
struct indexed_file* file = create_indexed_file_control_block(filename, index_block, file_size);
return file->file_id;
}
多级索引
// 多级索引结构
struct multi_level_index {
int primary_index; // 主索引块
int secondary_indexes[MAX_SECONDARY_INDEXES]; // 二级索引块
int secondary_count; // 二级索引块数量
int tertiary_indexes[MAX_TERTIARY_INDEXES]; // 三级索引块
int tertiary_count; // 三级索引块数量
};
// 多级索引文件访问
int read_multi_level_file(int file_id, char* buffer, int offset, int size) {
struct indexed_file* file = get_indexed_file_control_block(file_id);
if (file == NULL) return -1;
struct multi_level_index* index = get_multi_level_index(file->index_block);
int bytes_read = 0;
int current_offset = offset;
while (bytes_read < size && current_offset < file->file_size) {
int block_number = current_offset / BLOCK_SIZE;
int data_block = get_data_block_address(index, block_number);
if (data_block == -1) break;
int bytes_to_read = min(BLOCK_SIZE, size - bytes_read);
int block_offset = current_offset % BLOCK_SIZE;
read_block_data(data_block, buffer + bytes_read, block_offset, bytes_to_read);
bytes_read += bytes_to_read;
current_offset += bytes_to_read;
}
return bytes_read;
}
优缺点分析
优点
- 随机访问快：通过索引可以直接定位到任意块
- 无外部碎片：支持动态分配
- 支持大文件：多级索引可以支持非常大的文件
缺点
- 空间开销：索引块占用额外空间
- 实现复杂：多级索引的实现较为复杂
- 索引块限制：单级索引有块数量限制
混合分配方式
Unix inode 结构
Unix 系统采用混合分配方式，结合直接块、间接块和多级间接块。
// Unix inode结构
struct inode {
int file_size;
int direct_blocks[12]; // 直接块
int single_indirect; // 一级间接块
int double_indirect; // 二级间接块
int triple_indirect; // 三级间接块
int link_count;
int access_time;
int modify_time;
int create_time;
};
// 计算文件块地址
int get_block_address(struct inode* inode, int block_number) {
if (block_number < 12) {
// 直接块
return inode->direct_blocks[block_number];
} else if (block_number < 12 + BLOCKS_PER_INDEX) {
// 一级间接块
int index_block = inode->single_indirect;
int offset = block_number - 12;
return get_index_block_entry(index_block, offset);
} else if (block_number < 12 + BLOCKS_PER_INDEX + BLOCKS_PER_INDEX * BLOCKS_PER_INDEX) {
// 二级间接块
int index_block = inode->double_indirect;
int offset = block_number - 12 - BLOCKS_PER_INDEX;
int secondary_index = get_index_block_entry(index_block, offset / BLOCKS_PER_INDEX);
return get_index_block_entry(secondary_index, offset % BLOCKS_PER_INDEX);
} else {
// 三级间接块
// 类似二级间接块的处理
return -1;
}
}
性能分析
// 不同分配方式的性能比较
struct allocation_performance {
char method[32];
int sequential_read_speed; // 顺序读取速度
int random_read_speed; // 随机读取速度
int space_efficiency; // 空间利用率
int implementation_complexity; // 实现复杂度
};
struct allocation_performance performance_table[] = {
{"连续分配", 100, 100, 70, 10},
{"链接分配", 60, 20, 95, 30},
{"索引分配", 80, 90, 85, 60},
{"混合分配", 90, 85, 90, 80}
};
总结
不同的文件分配方式各有优劣，现代文件系统通常采用混合分配方式以平衡性能、空间利用率和实现复杂度。理解这些分配方式的特点对于设计高效的文件系统和进行系统优化具有重要意义。
在后续章节中，我们将学习文件访问控制、文件系统类型等更高级的概念。