操作系统实验 存储管理-可变分区存储管理的空间分配与去配_实验室管理系统存储分配

实验四 存储管理-可变分区存储管理的空间分配与去配

一、实验目的
要求掌握存储管理中的典型算法，理解各种存储管理的工作原理，特别是可变分区存储管理中最先适应分配算法、最优适应分配算法、最坏适应分配算法以及空间回收算法的工作原理，试采用C语言编程，模拟实现算法功能。

二、实验要求
设计一个可变式分区分配的存储管理方案，并模拟实现分区的分配和回收过程。
假定主存空间为静态分配。为实现分区的分配和回收，需要已分配分区表和系统空闲分区表描述当前系统状态。已分配分区表包括分区编号、已分配分区长度、分区的起始地址等信息。系统空闲分区表包括分区编号、分区长度、分区的起始地址等信息。用户根据需要提出对主存空间大小的申请，系统按照一定的分配策略，找出能满足请求的空闲区进行分配。如果满足要求，输出分配完成后已分配分区表和空闲区表的信息，否则输出“无空闲区分配”。
用户根据需要释放主存空间，实现空间的回收，并输出空间回收后已分配分区表和空闲区表的信息。

反正代码是写吐了
如果要加很多功能的话还可以加
开源图一乐

/* 
    时间：4月27日~4月28日
   	仅供参考，还请不要复制粘贴
 */

#include <iostream>
#include <string>
#include <queue>
using namespace std;
// 分配表最多容纳100个
#define MAX 100

// 创建进程信息
struct process
{
    int seq;
    // 分区表的单行序号
    int length;
    // 分区表的单行长度
    int begin_address;
    // 分区表的起始地址
    int number;
    // 最后哪个进程被分配的进程编号
};

// 创建可变分区表的结构体，表长和进程信息
struct system_list
{

    process informationArray[MAX];
    int size;
};

// 菜单展示
void display()
{
    cout << "__________________________________" << endl;
    cout << "__________1.设计空闲区信息__________" << endl;
    cout << "__________2.显示空闲区信息______________" << endl;
    cout << "__________3.添加作业队列信息______________" << endl;
    cout << "__________4.显示作业队列信息______________" << endl;
    cout << "__________5.最先分配适应算法________________" << endl;
    cout << "__________6.最优分配适应算法______________" << endl;
    cout << "__________7.最坏分配适应算法_______________" << endl;
    cout << "__________8.主存回收_______________" << endl;
    cout << "__________0.退出系统______________" << endl;
    cout << "__________________________________" << endl;
}

void addInfo(system_list *l)
{
    cout << "下面开始建立空闲分区表" << endl;

    int seq;
    cout << "输入空闲分区的分区编号" << endl;
    cin >> seq;
    l->informationArray[l->size].seq = seq;

    int length;
    cout << "输入空闲分区的可分配区域长度" << endl;
    cin >> length;
    l->informationArray[l->size].length = length;

    int begin_address;
    cout << "输入空闲分区的起始地址（十进制）" << endl;
    cin >> begin_address;
    l->informationArray[l->size].begin_address = begin_address;

    l->informationArray[l->size].number = -1;

    l->size++;
}
void displayInformation(system_list *l)
{
    if (l->size == 0)
    {
        cout << "当前空闲区不空闲" << endl;
        return;
    }
    else
    {
        for (int i = 0; i < l->size; i++)
        {
            cout << "----------------------------------------------------------------------------------" << endl;
            cout << "空闲区序号： " << l->informationArray[i].seq << "\t";
            cout << "空闲区长度： " << l->informationArray[i].length << "\t";
            cout << "空闲区起始地址： " << l->informationArray[i].begin_address << "\t";
            cout << "分配的进程编号： " << l->informationArray[i].number << endl;
            cout << "----------------------------------------------------------------------------------" << endl;
        }
    }
}

// 创建作业队列，运用queue标准库
void pushlist(queue<int> *list)
{
    cout << "请输入你要设计的作业队列需要的内存:" << endl;
    int num;
    cin >> num;
    list->push(num);
}
void displaylist(queue<int> *list)
{
    cout << "----------------队列内容：------------------" << endl;
    int n = 0;
    int pop;
    while (n < list->size())
    {
        cout << "序号为：" << n << "  需求内存为: " << list->front() << endl;
        list->push(list->front());
        list->pop();
        // 没有遍历器，就在出队的同时入队
        n++;
    }
}

// 冒泡排序：让地址从低到高排序
void bubble_address(system_list *l)
{
    process temp;
    for (int i = 0; i < l->size - 1; i++)
    {
        for (int j = 0; j < l->size - i - 1; j++)
        {
            if (l->informationArray[j].begin_address > l->informationArray[j + 1].begin_address)
            {
                temp = l->informationArray[j];
                l->informationArray[j] = l->informationArray[j + 1];
                l->informationArray[j + 1] = temp;
            }
        }
    }
}
// 最先适应分配算法
void frist_fit_allocated(system_list *l, queue<int> *list)
{
    // 先将地址进行冒泡排序
    bubble_address(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 选择排序，将空闲区容量从低到高排序
void select_length(system_list *l)
{
    for (int i = 0; i < l->size; i++)
    {
        for (int j = i + 1; j < l->size; j++)
        {
            if (l->informationArray[i].length > l->informationArray[j].length)
            {
                swap(l->informationArray[i], l->informationArray[j]);
            }
        }
    }
}
// 最优适应分配算法
void frist_best_allocated(system_list *l, queue<int> *list)
{
    // address sort the select
    select_length(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 冒泡排序，让空闲区容量从高到低
void fast_length(system_list *l)
{
    for (int i = 0; i < l->size - 1; i++)
    {
        for (int j = 0; j < l->size - 1 - i; j++)
        {
            if (l->informationArray[j].length < l->informationArray[j + 1].length)
            {
                swap(l->informationArray[j], l->informationArray[j + 1]);
            }
        }
    }
}
void frist_terrible_allocated(system_list *l, queue<int> *list)
{
    fast_length(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 重点来了：主存回收-----------------------------------------------------------
void retrieve(system_list *l)
{
    bubble_address(l);
    cout << "地址排序结果" << endl;
    displayInformation(l);
    l->informationArray[l->size].begin_address = -100;
    l->informationArray[l->size + 1].begin_address = -100;
    l->informationArray[l->size + 2].begin_address = -100;
    int i = 1;
    while (l->informationArray[i].begin_address != -100)
    {
        // 上面有空间，下面有空间
        if (l->informationArray[i].begin_address - 1 == l->informationArray[i - 1].begin_address && l->informationArray[i].begin_address + 1 == l->informationArray[i + 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i + 1].length > 0 && l->informationArray[i - 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length + l->informationArray[i + 1].length;
            while (2)
            {
                for (int j = i; j < l->size; j++)
                {
                    l->informationArray[j] = l->informationArray[j + 1];
                }
                l->size--;
            }
        }

        // 上面有空间
        else if (l->informationArray[i].begin_address - 1 == l->informationArray[i - 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i - 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length;
            for (int j = i; j < l->size; j++)
            {
                l->informationArray[j] = l->informationArray[j+1];
            }
            l->size--;
        }
        // 下面有空间
        else if (l->informationArray[i].begin_address + 1 == l->informationArray[i + 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i + 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length;
            for (int j = i + 1; j < l->size; j++)
            {
                l->informationArray[j] = l->informationArray[j + 1];
            }
            l->size--;
        }
        i++;
    }
    cout<<"+++++++++++++++++++++++++回收结果++++++++++++++++++++++++++++++++++"<<endl;
    displayInformation(l);
    cout << "没有可以回收的空间啦" << endl;
}

int main()
{
    int select = 0;
    system_list l;
    queue<int> list;
    l.size = 0;
    cout << "请输入你的选择" << endl;
    while (true)
    {

        display();
        cin >> select;
        switch (select)
        {
            // 1~2输入空闲区信息
        case 1:
        {
            cout << "请按照提示输入信息" << endl;
            int num;
            cout << "请输入你要设定空闲区的个数" << endl;
            cin >> num;
            while (num)
            {
                addInfo(&l);
                num--;
            }
            cout << "添加完毕，请开始你的表演吧！" << endl;
        }
        break;

        case 2:
        {
            displayInformation(&l);
        }
        break;

        // 3~4输入作业队列信息
        case 3:
        {
            cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~开始作业队列的输入~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << endl;
            cout << "请按照提示输入信息" << endl;
            int num1;
            cout << "请输入你要设定进入空闲区进程的的个数" << endl;
            cin >> num1;
            while (num1)
            {
                pushlist(&list);
                num1--;
            }
            cout << "添加完毕" << endl;
        }
        break;
        case 4:
        {
            displaylist(&list);
        }
        break;
        // 最先适应分配算法。
        case 5:
            frist_fit_allocated(&l, &list);
            break;
        // 最优适应分配算法
        case 6:
            frist_best_allocated(&l, &list);
            break;
        // 最坏适应分配算法
        case 7:
            frist_terrible_allocated(&l, &list);
            break;
        case 8:
            retrieve(&l);
            break;

        case 0:
            cout << "不欢迎下次的使用" << endl;
            return 0;
        default:
            break;
        }
    }
}

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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399