C++模拟实现可变内存分区管理

发表于 | 分类于

实验目的

体会可变分区内存管理方案，掌握此方案的内存分配过程、内存回收过程和紧凑算法的实现。

实验内容

编制一个程序模拟实现可变分区内存管理。实验时，假设系统内存容量为 1000KB 。分配时使用 malloc(pid, length) 函数实现，作业释放内存时使用 mfree(handle)函数实现，内存情况输出用 mlist()函数实现。

编写主界面

编写主界面，界面上有三个选项：分配内存、回收内存、查看内存。选择分配内存时，要求输入作业的进程号和作业长度，然后使用 malloc 函数分配内存，并报告内存分配结果。回收内存时要求输入进程号，使用 mfree 函数实现回收。查看内存时，使用 mlist 函数实现输出内存使用情况和空闲情况。

编写 malloc(pid, length) 函数

编写 malloc(pid, length)函数，实现进程 pid 申请 length KB 内存，要求程序判断是否能分配，如果能分配，要把分配内存的首地址 handle 输出到屏幕上。不能分配则输出字符串“NULL”。要考虑不能简单分配时，是否符合紧凑的条件，如符合则采用紧凑技术。然后再分配。分配时可在最佳适应算法、最差适应算法和首次适应算法中任选其一。

编写 mfree(handle) 函数

编写mfree(handle)函数，释放首地址为handle 的内存块。释放成功返回Success，否则返回 Failure。

编写 mlist() 函数

编写 mlist()函数，要求输出内存使用情况和空闲情况。输出的格式为：

1
ID	Address	Length	Process

ID 内存分区号

Address 该分区的首地址

Length 分区长度

Process 如果使用，则为使用的进程号，否则为NULL

实现

mfree(handle) 函数应该考虑 4 种情况：

  1. 要释放的内存块前后内存块都是已分配内存块；
  2. 要释放的内存块前是空闲内存块；
  3. 要释放的内存块前是空闲内存块；
  4. 要释放的内存块前后都是空闲内存块；

在这里实现的时候释放时不考虑前后内存块的情况，直接标为空闲状态，合并留待需要紧凑时再实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int memory = 1000;  // 内存容量
int mid = 0;        // 内存块数量

struct FreeBlock {
    int id;         // 内存分区号
    int address;    // 该分区的首地址
    int length;     // 分区长度
    FreeBlock(int id, int address, int length) {
        this->id = id;
        this->address = address;
        this->length = length;
    }
};

struct AllocatedBlock {
    int id;         // 内存分区号
    int address;    // 该分区的首地址
    int pid;        // 进程 ID
    int length;     // 分区长度
    AllocatedBlock(int id, int address, int pid, int length) {
        this->id = id;
        this->address = address;
        this->pid = pid;
        this->length = length;
    }
};

vector<FreeBlock*> free_blocks;
vector<AllocatedBlock*> allocated_blocks;

void malloc(int pid, int length);
void mlist();
void mfree(int address);
void compact(int pid, int length);

int main() {
    string action;
    int pid, length, address;

    FreeBlock *free_block = new FreeBlock(0, 0, 1000);     // 初始化空闲分区
    free_blocks.push_back(free_block);
    do{
        printf("Do something: ");
        cin >> action;
        if(action=="malloc"){
            cin >> pid >> length;
            malloc(pid,length);
        }
        else if(action=="mfree"){
            cin >> address;
            mfree(address);
        }
        else if(action=="mlist"){
            mlist();
        }
        else if(action=="exit"){
            break;
        }
        else{
            printf("Valid Input:\n  malloc pid length\n  mfree handle\n  mlist\n");
        }
    }while(true);

    // 测试用
    // malloc(12, 200);
    // malloc(242, 200);
    // malloc(124, 100);
    // malloc(24, 200);
    // malloc(41, 100);
    // malloc(432, 50);
    // malloc(34, 50);
    // malloc(235, 50);
    // mlist();
    // mfree(200);
    // mfree(700);
    // mlist();
    // malloc(32, 300);
    // mlist();

    return 0;
}

//使用首次适应算法分配内存
void malloc(int pid, int length) {
    if (length>memory) {
        printf("failed!\n");
        return;
    }
    int flag = 1;     // 标志是否需要使用紧凑算法
    for (auto it = free_blocks.begin(); it != free_blocks.end(); it++) {
        FreeBlock *mb = *it;
        if (mb->length > length) {
            AllocatedBlock *allocated_block = new AllocatedBlock(mb->id, mb->address, pid, length);
            allocated_blocks.push_back(allocated_block);
            memory -= length;
            mb->id = ++mid;
            mb->address += length;
            mb->length -= length;
            flag = 0;
            break;
        }
        else if (mb->length == length) {
            AllocatedBlock *allocated_block = new AllocatedBlock(mb->id, mb->address, pid, length);
            allocated_blocks.push_back(allocated_block);
            it = free_blocks.erase(it);
            flag = 0;
            break;
        }
    }
    if (flag) {
        compact(pid, length);
    }
}

// 紧凑算法
void compact(int pid, int length) {
    FreeBlock *fb1 = *free_blocks.begin();
    FreeBlock *mb = *(free_blocks.begin() + 1);
    int min = fb1->address - mb->address;
    auto a = free_blocks.begin() + 1;
    for (auto it = free_blocks.begin() + 1; it != free_blocks.end(); it++) {
        FreeBlock *mb = *it;
        if ((fb1->address - mb->address) < min) {
            //*fb2 = *mb;
            a = it;
        }
    }
    FreeBlock *fb2 = *a;
    int offset = 0;
    for (auto it = allocated_blocks.begin(); it != allocated_blocks.end(); it++) {
        AllocatedBlock *mb = *it;
        if (mb->address > fb2->address) {
            mb->id--;
            mb->address -= fb2->length;
            offset += mb->length;
        }
    }
    fb1->id = --mid;
    fb1->address = fb2->address + offset;
    fb1->length = fb1->length + fb2->length;
    a = free_blocks.erase(a);
    malloc(pid, length);
}

void mlist() {
    puts("ID\tAddress\tLength\tProcess");
    for (auto it = allocated_blocks.begin(); it != allocated_blocks.end(); it++) {
        AllocatedBlock *mb = *it;
        printf("%d\t%d\t%d\t%d\n", mb->id, mb->address, mb->length, mb->pid);
    }
    for (auto it = free_blocks.begin(); it != free_blocks.end(); it++) {
        FreeBlock *mb = *it;
        printf("%d\t%d\t%d\t%s\n", mb->id, mb->address, mb->length, "NULL");
    }
}

void mfree(int address) {
    bool dirty = true;
    for (auto it = free_blocks.begin(); it != free_blocks.end(); it++) {
        FreeBlock *mb = *it;
        if (mb->address == address) {
            dirty = false;
            cout << "This block has been freed before!" << endl;
            break;
        }
    }
    for (auto it = allocated_blocks.begin(); it != allocated_blocks.end(); it++) {
        AllocatedBlock *mb = *it;
        if (mb->address == address) {
            dirty = false;
            FreeBlock *free_block = new FreeBlock(mb->id, mb->address, mb->length);
            free_blocks.push_back(free_block);
            memory += mb->length;
            it = allocated_blocks.erase(it);
            break;
        }
    }
    if (dirty) {
        cout << "Could not found this address!" << endl;
    }
}