C语言位示图实现磁盘空间管理

简介

位示图是一种常用的数据结构，用于表示和管理资源的分配状态。在操作系统中，位示图常被用于磁盘空间管理，其中每一位代表一个磁盘块，'1'表示已分配，'0'表示空闲。

本文将介绍如何使用C语言实现基于位示图的磁盘空间管理，包括以下内容：

• 位示图的初始化
• 连续分配算法
• 离散分配算法
• 盘块的回收

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_ROW 100 // 最大行数
#define MAX_COL 100 // 最大列数

int bitmap[MAX_ROW][MAX_COL]; // 位示图数组
int row, col; // 行数和列数

// 初始化位示图
void init_bitmap() {
    printf('请输入位示图的行数和列数（以空格分隔）：');
    scanf('%d %d', &row, &col);
    if (row > MAX_ROW || col > MAX_COL) {
        printf('超过最大行数或列数！\n');
        exit(1);
    }
    printf('请输入位示图的初始状态（0表示空闲，1表示已分配）：\n');
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            scanf('%d', &bitmap[i][j]);
        }
    }
}

// 显示位示图
void show_bitmap() {
    printf('当前位示图状态：\n');
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            printf('%d ', bitmap[i][j]);
        }
        printf('\n');
    }
}

// 连续分配盘块
int allocate_contiguous(int size) {
    int start = -1; // 连续空闲区的起始位置
    int count = 0; // 连续空闲区的长度
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (bitmap[i][j] == 0) { // 如果当前位置为空闲
                if (start == -1) { // 如果是第一个空闲位置
                    start = j; // 记录起始位置
                }
                count++; // 连续空闲区长度增加
                if (count == size) { // 如果连续空闲区长度达到要求
                    for (int k = start; k < start + size; k++) {
                        bitmap[i][k] = 1; // 修改位示图
                    }
                    return start; // 返回起始位置
                }
            } else { // 如果当前位置已分配
                start = -1; // 连续空闲区起始位置重置
                count = 0; // 连续空闲区长度重置
            }
        }
        start = -1; // 连续空闲区起始位置重置
        count = 0; // 连续空闲区长度重置
    }
    return -1; // 分配失败，返回-1
}

// 离散分配盘块
int allocate_dispersed(int size) {
    int count = 0; // 空闲位置计数器
    int pos[size]; // 空闲位置数组
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (bitmap[i][j] == 0) { // 如果当前位置为空闲
                pos[count++] = i * col + j; // 记录空闲位置
                if (count == size) { // 如果空闲位置数达到要求
                    for (int k = 0; k < size; k++) {
                        int r = pos[k] / col; // 计算行号
                        int c = pos[k] % col; // 计算列号
                        bitmap[r][c] = 1; // 修改位示图
                    }
                    return pos[0]; // 返回第一个空闲位置
                }
            }
        }
    }
    return -1; // 分配失败，返回-1
}

// 回收盘块
void recycle_blocks() {
    printf('请选择回收方式（1：按文件回收，2：按盘块回收）：');
    int choice;
    scanf('%d', &choice);
    if (choice == 1) { // 按文件回收
        printf('请输入要回收的文件占用的盘块号（以空格分隔）：');
        int start, size;
        scanf('%d %d', &start, &size);
        if (start < 0 || start >= row * col || size <= 0) {
            printf('盘块号或大小不合法！\n');
            return;
        }
        int r = start / col; // 计算起始位置的行号
        int c = start % col; // 计算起始位置的列号
        for (int i = r; i < r + size; i++) {
            for (int j = 0; j < col; j++) {
                bitmap[i][j] = 0; // 修改位示图
            }
        }
        printf('回收成功！\n');
    } else if (choice == 2) { // 按盘块回收
        printf('请输入要回收的盘块号（以空格分隔）：');
        int block;
        scanf('%d', &block);
        if (block < 0 || block >= row * col) {
            printf('盘块号不合法！\n');
            return;
        }
        int r = block / col; // 计算行号
        int c = block % col; // 计算列号
        if (bitmap[r][c] == 0) { // 如果该盘块已空闲
            printf('该盘块已空闲！\n');
            return;
        }
        bitmap[r][c] = 0; // 修改位示图
        printf('回收成功！\n');
    } else {
        printf('选择不合法！\n');
    }
}

int main() {
    init_bitmap();
    show_bitmap();
    int choice;
    do {
        printf('请选择操作（1：分配盘块，2：回收盘块，0：退出）：');
        scanf('%d', &choice);
        switch (choice) {
            case 1: {
                printf('请选择分配方式（1：连续分配，2：离散分配）：');
                int method;
                scanf('%d', &method);
                printf('请输入要分配的盘块数：');
                int size;
                scanf('%d', &size);
                int start;
                if (method == 1) {
                    start = allocate_contiguous(size);
                } else if (method == 2) {
                    start = allocate_dispersed(size);
                } else {
                    printf('选择不合法！\n');
                    break;
                }
                if (start == -1) {
                    printf('分配失败！\n');
                } else {
                    printf('分配成功！分配的盘块号为：');
                    for (int i = start; i < start + size; i++) {
                        printf('%d ', i);
                    }
                    printf('\n');
                    show_bitmap();
                }
                break;
            }
            case 2: {
                recycle_blocks();
                show_bitmap();
                break;
            }
            case 0: {
                printf('退出程序！\n');
                break;
            }
            default: {
                printf('选择不合法！\n');
                break;
            }
        }
    } while (choice != 0);
    return 0;
}

使用示例

假设我们有一个 5x5 的磁盘空间，初始状态如下：

0 0 0 1 1
0 1 0 0 0
1 1 0 1 0
0 0 1 1 1
1 0 0 0 0

1. 连续分配 3 个盘块：

   • 程序会找到第一块连续空闲区域（第 0 行，第 0-2 列），并将其分配出去。

   • 位示图变为：

     1 1 1 1 1
     0 1 0 0 0
     1 1 0 1 0
     0 0 1 1 1
     1 0 0 0 0
     

2. 离散分配 2 个盘块：

   • 程序会找到两个空闲盘块（例如，第 1 行第 0 列和第 1 行第 2 列），并将其分配出去。

   • 位示图变为：

     1 1 1 1 1
     1 1 1 0 0
     1 1 0 1 0
     0 0 1 1 1
     1 0 0 0 0
     

3. 回收盘块 1-3：

   • 程序会将第 0 行第 1-3 列的盘块标记为空闲。

   • 位示图变为：

     1 0 0 0 1
     1 1 1 0 0
     1 1 0 1 0
     0 0 1 1 1
     1 0 0 0 0
     

总结

本文介绍了如何使用C语言和位示图实现磁盘空间管理。我们讨论了两种常见的分配算法：连续分配和离散分配，并提供了相应的代码实现。此外，我们还演示了如何回收已分配的盘块。

需要注意的是，这只是一个简单的示例，实际的磁盘空间管理要复杂得多，需要考虑更多因素，例如文件系统、磁盘调度算法等。