C语言实现位示图磁盘空间管理：连续、离散分配算法详解

引言

在操作系统中，高效地管理磁盘空间至关重要。位示图作为一种常用的磁盘空间管理技术，具有直观、易于实现等优点。本文将介绍如何使用C语言实现基于位示图的磁盘空间管理，涵盖连续分配和离散分配两种算法，并提供完整的代码示例。

位示图简介

位示图使用一个比特位来表示磁盘上的一个块，'1' 表示该块已被占用，'0' 表示该块空闲。例如，一个 1000 块的磁盘可以使用一个 1000 比特的位示图来表示其空间使用情况。

C语言实现

1. 数据结构

我们使用二维数组 bitmap 来模拟位示图，并定义 MAX_ROW 和 MAX_COL 来表示位示图的行数和列数。c#include <stdio.h>#include <stdlib.h>

#define MAX_ROW 10#define MAX_COL 10

int bitmap[MAX_ROW][MAX_COL]; // 位示图数组int file_blocks = 0; // 文件所占块数

2. 初始化位示图

初始化时，将位示图的所有比特位设置为 '0'，表示所有磁盘块都为空闲状态。c// 初始化位示图void init_bitmap() { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) { bitmap[i][j] = 0; } }}

3. 显示位示图

为了方便观察磁盘空间分配情况，编写一个函数用于显示当前位示图。c// 显示位示图void show_bitmap() { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) { printf('%d ', bitmap[i][j]); } printf(' '); }}

4. 连续分配算法

连续分配算法要求为文件分配连续的磁盘块。实现思路如下：

• 遍历位示图，寻找连续的 '0' 比特位，其数量满足文件所需块数。- 若找到，则将对应比特位设置为 '1'，表示已分配，并返回第一个块号。- 若未找到，则分配失败，返回错误代码。c// 连续分配int allocate_continuous(int file_size, int block_size) { int i, j, k, flag = 0; file_blocks = (file_size + block_size - 1) / block_size; // 计算文件所占块数 for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) { if (bitmap[i][j] == 0) { flag++; if (flag == file_blocks) { // 找到足够的连续空闲块 for (k = j - file_blocks + 1; k <= j; k++) { bitmap[i][k] = 1; // 修改位示图 } return i * MAX_COL + j - file_blocks + 1; // 返回分配的第一个块号 } } else { flag = 0; // 连续块被打断，重新计数 } } flag = 0; // 连续块被打断，重新计数 } return -1; // 没有足够的连续空闲块}

5. 离散分配算法

离散分配算法允许将文件存储在磁盘上不连续的块中。实现思路如下：

• 遍历位示图，寻找 '0' 比特位。- 每找到一个 '0' 比特位，就将其设置为 '1'，表示已分配，并记录块号。- 当找到的块数满足文件所需块数时，返回所有已分配块号的列表（或第一个块号）。c// 离散分配int allocate_discrete(int file_size, int block_size) { int i, j, k, flag = 0; file_blocks = (file_size + block_size - 1) / block_size; // 计算文件所占块数 for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) { if (bitmap[i][j] == 0) { flag++; bitmap[i][j] = 1; // 修改位示图 if (flag == file_blocks) { // 找到足够的离散空闲块 return i * MAX_COL + j - file_blocks + 1; // 返回分配的第一个块号 } } } } return -1; // 没有足够的离散空闲块}

6. 分配和回收磁盘块

以下函数用于模拟分配和回收磁盘块的操作：c// 分配磁盘块int allocate_blocks() { int file_size, block_size; printf('请输入文件大小：'); scanf('%d', &file_size); printf('请输入块大小：'); scanf('%d', &block_size); printf('请选择分配方式（1.连续分配 2.离散分配）：'); int choice; scanf('%d', &choice); int block_num; if (choice == 1) { block_num = allocate_continuous(file_size, block_size); // 连续分配 } else if (choice == 2) { block_num = allocate_discrete(file_size, block_size); // 离散分配 } else { printf('输入不合法！ '); return -1; } if (block_num == -1) { printf('磁盘空间不足！ '); return -1; } printf('文件分配成功，分配的第一个块号为：%d ', block_num); return block_num;}

// 回收磁盘块void free_blocks() { printf('请输入要回收的块号：'); int block_num; scanf('%d', &block_num); if (block_num < 0 || block_num >= MAX_ROW * MAX_COL) { printf('输入不合法！ '); return; } int row = block_num / MAX_COL; int col = block_num % MAX_COL; if (bitmap[row][col] == 0) { printf('该块未被分配！ '); return; } bitmap[row][col] = 0; // 修改位示图 printf('块号 %d 回收成功！ ', block_num);}

7. 主函数

主函数提供一个简单的菜单界面，用于测试上述功能。cint main() { init_bitmap(); // 初始化位示图 int choice; while (1) { printf('请选择操作（1.分配磁盘块 2.回收磁盘块 3.显示位示图 4.退出程序）：'); scanf('%d', &choice); switch (choice) { case 1: allocate_blocks(); // 分配磁盘块 break; case 2: free_blocks(); // 回收磁盘块 break; case 3: show_bitmap(); // 显示位示图 break; case 4: exit(0); // 退出程序 default: printf('输入不合法！ '); break; } } return 0;}

离散分配 vs. 随机分配

在代码中，离散分配和连续分配的区别在于寻找空闲块的方式不同。

• 连续分配 要求找到连续的空闲块来存储文件，这在磁盘碎片化严重时可能导致分配失败。- 离散分配 则允许将文件存储在不连续的块中，更灵活但也可能导致文件访问速度变慢。- 随机分配 是指从所有空闲块中随机选择块进行分配。这种方式实现简单，但可能导致磁盘空间碎片化更加严重，因此实际应用中较少使用。

总结

本文介绍了如何使用C语言实现基于位示图的磁盘空间管理，并详细讲解了连续分配和离散分配两种算法。通过学习本文，你应该对操作系统中的磁盘管理机制有了更深入的了解。