1
2
3
4
5
6
7
8
9
10
11
12
13
14
（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
- main.cpp
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
#include <iostream>
#include "cdef.h"
// 配置算法，FF为首次适应算法，BF为最佳适应算法
#define ALGORITHM BF
#define MAXSIZE 640
using namespace std;
int job[11][3]={
{1,130,ACT_ALLOC},
{2,60,ACT_ALLOC},
{3,100,ACT_ALLOC},
{2,60,ACT_FREE},
{4,200,ACT_ALLOC},
{3,100,ACT_FREE},
{1,130,ACT_FREE},
{5,140,ACT_ALLOC},
{6,60,ACT_ALLOC},
{7,50,ACT_ALLOC},
{6,60,ACT_FREE}
};
int main(){
Memory memory(ALGORITHM,MAXSIZE);
memory.dump();
for (int i = 0; i < 11; i++)
{
memory.act(job[i][0],job[i][1],job[i][2]);
memory.dump();
}
}
- cdef.cpp
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
//实验2
#define FF 0 //首次适应算法
#define BF 1 //最佳首次算法
#define ACT_FREE 0
#define ACT_ALLOC 1
typedef int ALGORITHM_ID;
typedef struct MemorySlice{
bool isUsed;
int jobID;
int size;
MemorySlice * former;
MemorySlice * next;
}MemorySlice;
class Memory{
public:
Memory(ALGORITHM_ID id,int INITIALMEMORYSIZE){
if (id == FF || id == BF)
{
alloc = AllocAlgo[id];
}
memory = getInitSlice(INITIALMEMORYSIZE);
}
~Memory(){
destory();
}
// 变量
MemorySlice * memory;
void (Memory::*alloc)(int,int);
// 函数
MemorySlice * getInitSlice(int SIZE){
MemorySlice * p = (MemorySlice *)malloc(sizeof(MemorySlice));
p->isUsed = false;
p->jobID = 0;
p->size = SIZE;
p->former = nullptr;
p->next = nullptr;
return p;
}
void destory(){
while(memory!=nullptr){
MemorySlice * t = memory;
memory = memory -> next;
free(t);
}
cout<<endl<<"内存清空完成"<<endl;
}
// 算法
void (Memory::*AllocAlgo[2])(int,int)={&Memory::FFAlloc,&Memory::BFAlloc};
// 首次适应算法
void FFAlloc(int job,int num){
MemorySlice* p = memory;
while (p != nullptr)
{
if (!p->isUsed && p->size > num)
{
break;
}
p = p->next;
}
// 在 p 指向的地方分配
startAlloc(p,job,num);
}
// 最佳适应算法
void BFAlloc(int job,int num){
MemorySlice* best=nullptr;
MemorySlice* p = memory;
while (p != nullptr)
{
if (!p->isUsed && p->size > num)
{
if(best==nullptr || best->size > p->size){
best = p;
}
}
p=p->next;
}
startAlloc(best,job,num);
}
void startAlloc(MemorySlice* p,int job,int num){
if(p==nullptr){
cout<<"job "<<job<<"申请分配"<<num<<"KB失败"<<endl;
return;
}
else{
MemorySlice* ms = (MemorySlice*)malloc(sizeof(MemorySlice));
ms->former = p->former;
ms->size = num;
ms->jobID = job;
ms->isUsed = true;
ms->next = p;
if(ms->former != nullptr){
ms->former->next = ms;
}
else{
// 首部
memory = ms;
}
// 修改 p
p->former = ms;
p->size -= ms->size;
}
}
// 释放内存
void Free(int job,int num){
MemorySlice* p = findMemorySliceByJob(job);
if(p==nullptr){
cout<<"未找到job "<<job<<"分配的内存"<<endl;
return;
}
else{
// free
MemorySlice* former = p->former;
MemorySlice* next = p->next;
if (former != nullptr && former->isUsed == false)
{
// 和former合并 , p-> former
former->size += p->size;
former->next = p->next;
if (p->next != nullptr)
{
p->next->former = former;
}
p = former;
}
if (next != nullptr && next->isUsed == false)
{
// p和 next合并
p->size += next->size;
p->next = next->next;
if(next->next != nullptr){
next->next->former = p;
}
}
p->isUsed = false;
}
}
MemorySlice* findMemorySliceByJob(int num){
MemorySlice* p = memory;
while (p!=nullptr)
{
if (p->jobID == num)
{
return p;
}
p = p->next;
}
return nullptr;
}
// 动作
void act(int job,int num,int ACTION){
if (ACTION == ACT_FREE)
{
cout<<"释放job "<<job<<"的"<<num<<"KB内存"<<endl;
Free(job,num);
}
else if(ACTION == ACT_ALLOC){
cout<<"job "<<job<<"申请"<<num<<"KB内存"<<endl;
(this->*alloc)(job,num);
}
else{
cout<<"未知操作符 "<<ACTION<<endl;
}
}
void dump(){
cout<<"---------------------"<<endl;
MemorySlice* p = memory;
int i = 0;
while (p!=nullptr)
{
cout<<"内存块："<<i<<endl;
if (p->isUsed)
{
cout<<"内存状态："<<"已占用"<<endl<<"作业名："<<p->jobID<<endl;
}
else{
cout<<"内存状态："<<"未使用"<<endl;
}
cout<<"空间大小："<<p->size<<"KB"<<endl;
p = p->next;
i += 1;
cout<<endl;
}
cout<<"---------------------"<<endl;
}
};
