用位示图管理磁盘存储空间

操作系统存储相关：用位示图管理磁盘存储空间。

问题描述

  1. 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。
  2. 位示图由若干字节构成，每位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”表示该块为空闲。
  3. 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共8个柱面，每个柱面有2个磁道（盘面），每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：
    • 柱面号 = 字节号
    • 磁道号 = 位数 / 4
    • 物理记录号 = 位数 % 4
  4. 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。归还块在位示图中的位置计算如下：
    • 字节号 = 柱面号
    • 位数 = 磁道号 * 4 + 物理记录号

要求

  1. 能接受来自键盘的空间申请及释放请求，能显示或打印程序运行前和运行后的位示图
  2. 分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来

代码实现

1
#include<iostream>
2
using namespace std;
3
#define MAX_SIZE 8 // 柱面数
4
5
// 初始化位示图
6
void init_bitmap(int bitmap[MAX_SIZE][MAX_SIZE]) {
7
    int cylinder, track, record; // 柱面号，磁道号，物理记录号
8
    char order; // 指令: 继续 or 退出
9
    cout << "是否需要初始化已分配空间(y or n)?" << endl;
10
    cin >> order;
11
    if(order == 'n')
12
        return;
13
    cout << "**位示图初始化**" << endl;
14
    while(true) {
15
        cout << "请输入已分配空间的柱面号, 磁道号和物理记录号(用空格分隔): ";
16
        cin >> cylinder >> track >> record;
17
        bitmap[cylinder][4*track+record] = 1; // 已分配的空间
18
        cout << "继续(c) or 退出(q): ";
19
        cin >> order;
20
        if(order == 'q')
21
            return;
22
    }
23
}
24
25
// 分配空间
26
void allocate(int bitmap[MAX_SIZE][MAX_SIZE]) {
27
    bool flag = false; // 判断是否有可分配空间
28
    for(int i=0; i<MAX_SIZE; i++)
29
        for(int j=0; j<MAX_SIZE; j++)
30
            if(bitmap[i][j] == 0) {
31
                bitmap[i][j] = 1; // 分配空间
32
                cout << "成功分配空间: 第" << i << "柱面 "; // 柱面号==字节号
33
                cout << "第" << j / 4 << "磁道 "; // 磁道号==位数/4
34
                cout << "第" << j % 4 << "物理记录" << endl; // 物理记录号==位数%4
35
                return;
36
            }
37
    cout << "磁盘空间不足，分配失败" << endl;
38
}
39
40
// 回收空间
41
void recover(int bitmap[MAX_SIZE][MAX_SIZE]) {
42
    int cylinder, track, record; // 柱面号，磁道号，物理记录号
43
    cout << "请输入柱面号, 磁道号和物理记录号(用空格分隔): ";
44
    cin >> cylinder >> track >> record;
45
    if(bitmap[cylinder][4*track+record] == 0)
46
        cout << "该空间未分配，回收失败" << endl;
47
    else {
48
        cout << "成功回收空间: 第" << cylinder << "字节 第"  << 4*track+record << "位" << endl;
49
        bitmap[cylinder][4*track+record] = 0;
50
    }
51
}
52
53
// 显示位示图
54
void show_bitmap(int bitmap[MAX_SIZE][MAX_SIZE]) {
55
    for(int i=0; i<MAX_SIZE; i++) {
56
        for(int j=0; j<MAX_SIZE; j++)
57
            printf("%4d", bitmap[i][j]);
58
        cout << endl;
59
    }
60
}
61
62
// 用位示图管理磁盘存储空间
63
void BitMap() {
64
    // 位示图数组
65
    int bitmap[MAX_SIZE][MAX_SIZE];
66
    // 将bitmap全置为0
67
    memset(bitmap, 0, sizeof(bitmap));
68
    // 初始化位示图
69
    init_bitmap(bitmap);
70
    // 循环运行
71
    char order; // 指令
72
    while(true) {
73
        cout << "请输入(a:分配, r:回收, s:显示, q:退出): " << endl << "> ";
74
        cin >> order;
75
        switch(order) {
76
            case 'a': allocate(bitmap); break;
77
            case 'r': recover(bitmap); break;
78
            case 's': show_bitmap(bitmap); break;
79
            case 'q': cout << "Bye" << endl; return;
80
            default: cout << "请输入正确的指令!" << endl; break;
81
        }
82
    }
83
}
84
85
int main() {
86
    cout << "**用位示图管理磁盘存储空间**" << endl;
87
    BitMap();
88
89
    return 0;
90
}