存储管理---动态分区分配算法的模拟
一、设计任务
完成存储器动态分区分配算法的模拟实现。
二、设计思想在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法 (首次适应算法，最佳适应算法，最后适应算法，最坏适应算法) ，实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接，等等相关的内容。
三、预期目的
让我们了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，并懂得在操作系统的支持下建立自己的应用系统。操作系统课程设计，对于训练学生掌握程序设计、熟悉上机操作和程序调试技术都有重要作用。重点培养学生的思维能力、设计能力、创新能力和排错能力。
四、设计方案首先是对相关知识的掌握，例如数据结构，计算方法，组成原理以及操作系统等。在这些基本知识的基础上进行扩展，用语言的形式从函数，数据结构原代码，原程序等方面来达到自己想要的目的。该设计就是要达到对各个细节的问题的解决将各个数据块连接起来，最终达到存储器动态分区分配算法的模拟实现。
五、数据结构
1．设计合理的数据结构来描述存储空间：
1) 对于未分配出去的部分，用空闲分区链表来描述
struct freeList
{
int startAddress; /*
int size; /*
struct freeList *next; /* }
2) 对于已经分配出去的部分，由装入内存的作业占据
struct usedList
{分区起始地址*/ 分区大小*/ 分区链表指针*/
}
以上将存储空间分为空闲可占用两部分，在 usedlist 中设 jobID 而 不设 size ，可以在不增加空间复杂度 (与 freelist 相比)的同时更方便 的实现可变分区存储管理(从后面的一些函数的实现上可以得出这个结 论)。
尽管设置 joblist 增加了空间复杂度，但它的存在，使得该程序可 以方便的直接利用D 盘中的JOB 文件。该文件可以认为是一个和其他进 程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在 操作系统设计中体现的很多。
2． 实现分区存储管理的内存分配功能，选择适应算法(首次适 应算法，最佳适应算法，最后适应算法，最坏适应算法) 。
基本原理分析：
1) Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。
2) Worst fit ：将空闲分区按大小从大到小排序，从头找到大小合适的分 区。 3) First fit :将空闲分区按起始地址大小从小到大排序，…… 4) Last fit :将空闲分区按起始地址大小从大到小排序，…… 由此，可将
空闲分区先做合适的排序后用对应的适应算法给作业分配存
储空间。排序函数 order (bySize 为零则按分区大小排序，否则按分区起 始地址；inc 为零从小到大排序，否则从大到小排序；通过 empty 指针返回 结果)。
void order(struct freeList **empty,int bySize,int inc)
{
struct freeList *p,*q,*temp; int startAddress,size;
for(p = (*empty) -> next;p;p = p -> next)
{ /*按bySize 和inc 两个参数寻找合适的节点，用temp 指向它*/
for(temp = q = p;q;q = q -> next)
/* int startAddress;
int jobID; /* struct usedList *next; /* }
3) 将作业组织成链表。 struct
jobList {
int id; int size; */
int status; /* finished . */
分区起始地址 */ 分区中存放作业 ID */ 分区链表指针 */
作业 ID */
作业大小(需要的存储空间大小)
struct jobList *next;
/* /* 作业状态 0 : new job ,1 : in the memory , 2 :
/* 作业链表指针 */
{
switch(bySize)
{
case 0 : switch(inc)
{
case 0:if(q->size < temp->size)
temp = q;break;
default:if(q->size > temp->size)
temp = q;break;
} break;
default: switch(inc)
{
case 0:if(q->startAddress temp->startAddress)
temp = q;break;
default:if(q->startAddress temp->startAddress)
temp = q;break;
} break;
}
} /* 交换节点的成员值if(temp != p)
{
startAddress = p->startAddress;
size = p->size;
p->startAddress = temp->startAddress;
p->size = temp->size;
temp->startAddress = startAddress; temp->size =
size;
}
}
}
3．实现分区存储管理的内存回收算法。
void insertFreeNode(struct freeList **empty,int startAddress,int 插入回收的空节点分区，处理回收分区与空闲分区的四种邻接关系。{
struct freeList *p,*q,*r;
for(p = *empty;p -> next;p = p -> next) ;
/* 处理链表尾部的邻接情况
if(p == *empty || p -> startAddress + p -> size < startAddress)
/* 与尾部不相邻*/ {
makeFreeNode(&r,startAddress,size);
*/
size) */
}
/* 通过 r 指针返回创建的空闲节点 */
/* 插入独立的空闲节点 */
+ p -> size == startAddress) /* 与尾部上邻 */
/* 合并尾部节点 */ == q -> startAddress) /* 与首节点下邻
{
q -> startAddress = startAddress; /* q -> size += size;
}
else if(startAddress + size < q -> startAddress)
/* 与首节点不相邻 */
{
makeFreeNode(&r,startAddress,size); r -> next = (*empty) -> next; (*empty) -> next = r;
}
else
{ /* 处理链表中间的邻接情况 */ while(q -> next && q -> startAddress <
startAddress)
{
p = q;
q = q -> next;
}
if(p -> startAddress + p -> size == startAddress &&\
q -> startAddress == startAddress + size) /* 上下邻，合并节点 */ { p -> size += size + q -> size; p -> next = q -> next; free(q); /* 删除多余节点 */ }
else if(p -> startAddress + p -> size == startAddress &&\ q ->
startAddress != startAddress + size)
/* 上邻，增加节点的大小 */ {
p -> size += size;
else if(p -> startAddress + p -> size != startAddress &&\
q -> startAddress == startAddress + size) /*
下邻 */
{
q -> startAddress = startAddress; /* 修改节点起始地址 */
1
q -> size += size;
/*
修改节点的大小 */
} else
{
/*
上下不相邻 */
r -> next = p -> next; p -> next = r; return ;
}
if(p -> startAddress
{
p -> size += size;
return ;
}
q = (*empty) -> next;
if(startAddress + size
/* 处理链表首节点的邻接情况
*/ */
合并首节点 */
makeFreeNode(&r,startAddress,size);
r -> next = p -> next;
p -> next = r;
} }
}
4．当碎片产生时，进行碎片的拼接。
void moveFragment(struct jobList *jobs,struct freeList **empty,struct usedList **used)
{
int size,status; struct usedList *p;
int address = memoryStartAddress;
/* 全局变量，初始化时分配存储空间始址*/ if((*empty)->next == NULL) /* 空闲分区链表为空，提示并返回*/ {
printf("\nThe memory was used out at all.\nMay be you should finish some jobs first or press any key to try again !");
getch(); return;
}
for(p = (*used) -> next;p;p = p-> next)
/* 循环的修改占用分区的始址*/ {
p -> startAddress = address; getJobInfo(jobs,p -> jobID,&size,&status);
/* 由作业ID 获得作业大小*/ address += size;
} (*empty)->next->startAddress = address;
/* 修改空闲分区的首节点始址、大小*/ (*empty) -> next -> size = memorySize -
(address memoryStartAddress);
(*empty) -> next -> next = NULL; /* 删除首节点后的所有节点*/
}
5．空闲分区队列显示：int showFreeList(struct freeList *empty)
6．作业占用链表显示：int showUsedList(struct jobList
*jobs,struct usedList *used)
从头到尾显示used 链，同时通过其中的作业ID 在jobs 中查对应的大小。
7.从键盘输入作业到D盘的JOB文件：void inputJob(void)
8．从JOB 文件中读出作业并创建作业链表：int makeJobList(struct jobList **jobs)
9. 显示作业链表：int showJobList(struct jobList *jobs)
10. 更新作业链表中作业的状态：int updateJobFile(struct jobList
*jobs)
11. 根据作业链表更新JOB 文件：int updateJobFile(struct jobList
*jobs)
12. 为作业分配存储空间、状态必须为0：int allocate(struct freeList
**empty,int size)
13. 结束一个作业号为id的作业，释放存储空间(由*startAddress返
回空间的起始地址) ：i n t finishJob(struct usedList **used,int id,int
*startAddress)
14. 插入释放的空间到used 链表中(作业号为id，startAddress 由函数
13 返回)：
void insertUsedNode(struct usedList **used,int id,int startAddress)
15. 获取作业的信息：void getJobInfo(struct jobList *jobs,int id,int *size,int *status )
16. 初始化存储空间起始地址、大小：void iniMemory(void)
17. 选择适应算法：char selectFitMethod(void)
18. 根据参数startAddress 、size 创建空闲节点，由empty 指针返回：
void makeFreeNode(struct freeList **empty,int startAddress,int size)
19. 以要求的方式打开文件：void openFile(FILE **fp,char
*filename,char *mode)
20. 出现严重错误时显示信息并结束程序； void errorMessage(void)
六、算法流程
1、Dynamic Zonal Memory Management
其中 1 、 Initializiation. 按顺序利用了 openFile() 、 iniMemory() 、 makeFreeNode()、inputJob()(选择利用 D 盘JOB 文件时提供作业信息)、
makeJobList()、allocate 。、insertUsedNode()(选择利用 D 盘 JOB 文件时先 将状态为 1 的作业放到存储空间中，以恢复上次的模拟实验，或使本次模拟时 不出错) selectFitMethod() 等自编函数。
2、 Put job into memory(allocate memory) 按顺序利用了 showJobList() (选 手动逐个为作业分配存储空间时) 、 openFile() 、 order() 、 allocate() 、
errorMessage() 、insertUsedNode() 、updateJobStatus()updateJobFile() 函 数 3、 Finish job(reuse memory) 按顺序利用了 openFile() 、showUsedList() 、 getJobInfo() 、insert FreeNode() 、updateJobStatus() 、updateJobFile() 、 errorMessage() 等自编函数。
4、 Showcurrent free list 按顺序利用了 openFile() 、showFreeList() 函数。
5、 Showcurrent memoryused by jobs 按顺序利用了 openFile() 、showUsedList() 函数。
6、 Movefragme nt together 按顺序禾 U 用了 ope nF ile() 、moveFragme nt()函数。
7、 E xit 按顺序利用了 openFile() 、 exit(0) 函数。
七、程序清单
1 、原程序
#include
int memoryStartAddress = -1; int memorySize = -1; struct jobList
{
int id; /* int size; /* int status;
/* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */ struct jobList *next; /* 作业链表指针 */ };
struct freeList
{
作业 ID */ 作业大小（需要的存储空间大小） */