一、实验目的
为了合理地分配和使用这些存储空间，当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间和使用情况，找出足够的空闲区域给申请者。当作业撤离归还主存资源时，则存储管理要收回占用的主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助我们理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。
用高级语言完成一个主存空间的分配和回收模拟程序，以加深对内存分配方式及其算法的理解。
二、 实验内容
2.1 模拟包括3部分：
1）实现特定的内存分配算法
2）实现内存回收模拟
3）每种内存分配策略对应的碎片数统计
2.2 固定分区存储管理
假设内存容量为120KB，并且分别划分成8,16,32,64KB大小的块各一块。
一个进程所需要的内存为0到100个KB。同时假设一个进程在运行过程中所需内存的大小不变。
模拟五个进程到达请求分配与运行完回收情况,输出主存分配表.
2.3 动态分区分配存储管理
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、下次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。
（1）在程序运行过程，由用户指定申请与释放。
（2）设计一个已占用分区表，以保存某时刻主存空间占用情况。
（3）设计一个空闲分区表，以保存某时刻主存空间剩余情况。
（4）用两个表的变化情况,反应各进程所需内存的申请与释放情况。
三、实验方法、步骤及结果测试
1、源程序
#include<iostream.h>
2 #include<stdlib.h>
3 #define Free 0 //空闲状态
4 #define Busy 1 //已用状态
5 #define OK 1 //完成
6 #define ERROR 0 //出错
7 #define MAX_length 32767 //最大内存空间为32767KB
8 typedef int Status;
9 int n=0;
10 typedef struct freearea//定义一个空闲区说明表结构
11 {
12 int ID; //分区号
13 long size; //分区大小
14 long address; //分区地址
15 int state; //状态
16 }ElemType;
17
18 //---------- 线性表的双向链表存储结构 ------------
19 typedef struct DuLNode //double linked list
20 {
21 ElemType data;
22 struct DuLNode *prior; //前趋指针
23 struct DuLNode *next; //后继指针
24 }DuLNode,*DuLinkList;
25
26 DuLinkList block_first; //头结点
27 DuLinkList block_last; //尾结点
28
29 Status alloc(int);//内存分配
30 Status free(int); //内存回收
31 Status First_fit(int,int);//首次适应算法
32 Status Best_fit(int,int); //最佳适应算法
33 void show();//查看分配
34 Status Initblock();//开创空间表
35
36 Status Initblock()//开创带头结点的内存空间链表
37 {
38 block_first=(DuLinkList)malloc(sizeof(DuLNode));
39 block_last=(DuLinkList)malloc(sizeof(DuLNode));
40 block_first->prior=NULL;
41 block_first->next=block_last;
42 block_last->prior=block_first;
43 block_last->next=NULL;
44 block_last->data.address=0;
45 block_last->data.size=MAX_length;
46 block_last->data.ID=0;
47 block_last->data.state=Free;
48 return OK;
49 }
50
51 //----------------------- 分 配 主 存 -------------------------
52 Status alloc(int ch)
53 {
54 int ID,request;
55 cout<<"请输入作业(分区号)：";
56 cin>>ID;
57 cout<<"请输入需要分配的主存大小(单位:KB)：";
58 cin>>request;
59 if(request<0 ||request==0)
60 {
61 cout<<"分配大小不合适，请重试!"<<endl;
62 return ERROR;
63 }
64
65 if(ch==2) //选择最佳适应算法
66 {
67 if(Best_fit(ID,request)==OK) cout<<"分配成功!"<<endl;
68 else cout<<"内存不足，分配失败!"<<endl;
69 return OK;
70 }
71 else //默认首次适应算法
72 {
73 if(First_fit(ID,request)==OK) cout<<"分配成功!"<<endl;
74 else cout<<"内存不足，分配失败!"<<endl;
75 return OK;
76 }
77 }
78 //------------------ 首次适应算法 -----------------------
79 Status First_fit(int ID,int request)//传入作业名及申请量
80 {
81 //为申请作业开辟新空间且初始化
82 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
83 temp->data.ID=ID;
84 temp->data.size=request;
85 temp->data.state=Busy;
86 DuLNode *p=block_first->next;
87 while(p)
88 {
89 if(p->data.state==Free && p->data.size==request)
90 {//有大小恰好合适的空闲块
91 p->data.state=Busy;
92 p->data.ID=ID;
93 return OK;
94 break;
95 }
96 if(p->data.state==Free && p->data.size>request)
97 {//有空闲块能满足需求且有剩余"
98 temp->prior=p->prior;
99 temp->next=p;
100 temp->data.address=p->data.address;
101 p->prior->next=temp;
102 p->prior=temp;
103 p->data.address=temp->data.address+temp->data.size;
104 p->data.size-=request;
105 return OK;
106 break;
107 }
108 p=p->next;
109 }
110 return ERROR;
111 }
112 //-------------------- 最佳适应算法 ------------------------
113 Status Best_fit(int ID,int request)
114 {
115 int ch; //记录最小剩余空间
116 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
117 temp->data.ID=ID;
118 temp->data.size=request;
119 temp->data.state=Busy;
120 DuLNode *p=block_first->next;
121 DuLNode *q=NULL; //记录最佳插入位置
122 while(p) //初始化最小空间和最佳位置
123 {
124 if(p->data.state==Free && (p->data.size>request || p->data.size==request) )
125 {
126 q=p;
127 ch=p->data.size-request;
128 break;
129 }
130 p=p->next;
131 }
132 while(p)
133 {
134 if(p->data.state==Free && p->data.size==request)
135 {//空闲块大小恰好合适
136 p->data.ID=ID;
137 p->data.state=Busy;
138 return OK;
139 break;
140 }
141 if(p->data.state==Free && p->data.size>request)
142 {//空闲块大于分配需求
143 if(p->data.size-request<ch)//剩余空间比初值还小
144 {
145 ch=p->data.size-request;//更新剩余最小值
146 q=p;//更新最佳位置指向
147 }
148 }
149 p=p->next;
150 }
151 if(q==NULL) return ERROR;//没有找到空闲块
152 else
153 {//找到了最佳位置并实现分配
154 temp->prior=q->prior;
155 temp->next=q;
156 temp->data.address=q->data.address;
157 q->prior->next=temp;
158 q->prior=temp;
159 q->data.address+=request;
160 q->data.size=ch;
161 return OK;
162 }
163 }
164 //----------------------- 主 存 回 收 --------------------
165 Status free(int ID)
166 {
167 DuLNode *p=block_first;
168 while(p)
169 {
170 if(p->data.ID==ID)
171 {
172 p->data.state=Free;
173 p->data.ID=Free;
174 if(p->prior->data.state==Free)//与前面的空闲块相连
175 {
176 p->prior->data.size+=p->data.size;
177 p->prior->next=p->next;
178 p->next->prior=p->prior;
179 }
180 if(p->next->data.state==Free)//与后面的空闲块相连
181 {
182 p->data.size+=p->next->data.size;
183 p->next->next->prior=p;
184 p->next=p->next->next;
185 }
186 break;
187 }
188 p=p->next;
189 }
190 return OK;
191 }
192 //--------------- 显示主存分配情况 ------------------
193 void show()
194 {
195 cout<<"***********-----------------************\n";
196 cout<<"**** 主 存 分 配 情 况 ****\n";
197 cout<<"***********-----------------************\n";
198 DuLNode *p=block_first->next;
199 while(p)
200 {
201 cout<<"分 区 号：";
202 if(p->data.ID==Free) cout<<"Free"<<endl;
203 else cout<<p->data.ID<<endl;
204 cout<<"起始地址："<<p->data.address<<endl;
205 cout<<"分区大小："<<p->data.size<<" KB"<<endl;
206 cout<<"状 态：";
207 if(p->data.state==Free) cout<<"空 闲"<<endl;
208 else cout<<"已分配!"<<endl;
209 cout<<"-----------------------"<<endl;
210 p=p->next;
211 }
212 }
213 //----------------------- 主 函 数---------------------------
214 void main()
215 {
216 int ch,d=0;//算法选择标记
217 cout<<"1.首次适应算法 2.最佳适应算法 0.退出\n";
218 cout<<"请选择分配算法：";
219 cin>>ch;
220 if(ch==0||ch==1||ch==2) d++;
221 while(d==0)
222 {
223 cout<<"请选择正确的数字0 ,1 或2"<<endl;
224 cin>>ch;
225 if(ch==0||ch==1||ch==2) d++;
226 }
227 if(ch==0) exit(0);
228 if(n==0) Initblock(); //开创空间表
229 int choice; //操作选择标记
230 while(1)
231 {
232 cout<<"********************************************\n";
233 cout<<"** 1: 分配内存 2: 回收内存 **\n";
234 cout<<"** 3: 查看分配 0: 返 回 **\n";
235 cout<<"********************************************\n";
236 cout<<"请输入您的操作 ：";
237 cin>>choice;
238 if(choice==1)
239 {
240 alloc(ch); // 分配内存
241 n++;
242 }
243 else if(choice==2) // 内存回收
244 {
245 int ID;
246 cout<<"请输入您要释放的分区号：";
247 cin>>ID;
248 free(ID);
249 n++;
250 }
251 else if(choice==3)
252 {
253 show();//显示主存
254 n++;
255 }
256 else if(choice==0)
257 {
258 main(); //退出
259 n++;
260 }
261 else //输入操作有误
262 {
263 cout<<"输入有误，请重试!\n"<<endl;
264 continue;
265 }
266 }
267 }
原文：http://www.cnblogs.com/Keico/p/5089107.html