存储器管理---动态分区分配算法的模拟
一、 设计任务：
编写程序完成“存储器管理－动态分区分配算法”的模拟，设计主界面来灵活选择各算法，其中包括首次适应算法，最佳适应算法，最坏适应算法以及回收算法。
二、 设计目的：
通过课程设计，进一步理解内存分配算法的思想，并在此基础上熟练编程语言的具体的操作。
三、 设计思想：
内存管理有空区表管理空闲得空间，空区表记录某个空闲块的大小和首地址信息，建立空区表的双向链表，对空区链表的操作达到内存分配的管理。
四、 设计方案：
建立空区表的双向链表结构，建立已分配表的双向链表结构；
分别建立最先适应、循环最先适应、最佳适应和最差适应得类结构；
采用C++Builder作界面设计；设计界面如下：若图片无法显示请联系QQ3710167
一、 核心代码：
作业数据类型的定义
#ifndef Job_H
#define Job_H
typedef struct Job
{
int size;//作业大小
int address;//作业首地址
AnsiString name;//作业名(AnsiString是C++Builder的字符串类型)
}Job;
#endif
若图片无法显示请联系QQ3710167
最先适应算法的代码：
#ifndef Firstfit_H
#define Firstfit_H
#include "Job.h"
//最先适应算法头文件
class first_fit_link;
class linknode
{
friend class first_fit_link;
private:
int size;//作业大小
int address;//作业首地址
linknode * forward;
linknode * next;
public:
{
size=s;
address=a;
forward=f;
next=n;
}
};
class first_fit_link
{
private:
linknode * head;//头指针 11
存储器管理---动态分区分配算法的模拟
linknode * rear;//尾指针
linknode * work;//标记指针
public:若图片无法显示请联系QQ3710167
first_fit_link()//初始化
{
head=NULL;
rear=NULL;
work=NULL;
}
~first_fit_link()//析构函数
{
linknode * point1;
while(head!=NULL)
{
point1=head;
head=head->next;
delete point1;
}
}
void init(int address,int size);//初始化建空区表
Job returnjob();//返回链表元素
int allot(int size);//分配,成功返回地址，否则返回无穷大
void free(int address,int size);//释放
bool over();//判断是否输出完节点元素
};
//空区表的建立
void first_fit_link::init(int address,int size)
{
if(head==NULL)//如果是空链，新建一个链
{
head=rear=work=new linknode(size,address,NULL,NULL);//申请新的节点
}
else
{
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(address
address)
{
point2=new linknode(size,address,NULL,NULL);
if(point1==head)//如果是首部，则改动头指针
{
point2->next=head;
head->forward=point2;
head=point2;
work=point2;
}
else//如果插入点在链中
{
point2->forward=point1->forward;
point2->next=point1;
point1->forward->next=point2;
point1->forward=point2;
}
break;//插入完成，退出
}
else
{
point1=point1->next;//寻找下一个位置
}
}
if(point1==NULL)//如果插入点在链尾，改动尾指针
{
point2=new linknode(size,address,rear,NULL);
rear->next=point2;
rear=point2;
}
}
}
//分配函数，如果分配成功，返回作业地址，否则返回1000
int first_fit_link::allot(int size)
{
int address=1000;
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(sizesize)//如果申请空间小于该节点，对该节点改动
{
address=point1->address;
point1->size=point1->size-size;
point1->address=point1->address+size;
return address;//分配成功，返回address
}
if(size==point1->size)//如果申请空间与该节点大小一致，删除该节点
{
if(point1==head)//如果是头节点
{
address=head->address;
point2=head;
head=head->next;
head->forward=NULL;
work=head;
delete point2;
return address;//分配成功，返回address
}
{
address=rear->address;
point2=rear;
rear=rear->forward;
rear->next=NULL;
delete point2;
}
if(point1!=head&&point1!=rear)
{
address=point1->address;
point2=point1->forward;
linknode * point3=point1->next;
point2->next=point3;
point3->forward=point2;
delete point1;
return address;//分配成功，返回address
}
}
point1=point1->next;//寻找下一个位置
}
if(point1==NULL)
{
return address;//没有合适的空间，分配不成功，返回1000
}
}
//释放空间函数
void first_fit_link::free(int address,int size)
{
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(addressaddress)
{
if(point1==head)//如果point1是头指针
{
if((address+size)==point1->address)
{
head->address=address;
head->size=head->size+size;
break;
}
else
{
point2=new linknode(size,address,NULL,head);
head->forward=point2;
head=point2;
break;
}
}
if((point1->forward->address+point1->forward->size)==address)//如果与前一个相邻
{
if((address+size)==point1->address)//如果同时与后一个相邻, 合并三者，删除point1
{
point2=point1->forward;
point2->size=point2->size+size+point1->size;
if(point1==rear)//如果point1是尾指针
{
rear=point2;
delete point1;
break;
}
else
{
point2->next=point1->next;
delete point1;
break;
}
}
else
{ //只与前一个相邻，则与前一个合并
point1->forward->size=point1->forward->size+size;
存储器管理---动态分区分配算法的模拟
break;
}
}
if((address+size)==point1->address)//如果与后一个相邻
{
point1->size=point1->size+size;//与后一个合并
break;
}
//如果前后都不相邻，申请新的节点
point2=new linknode(size,address,point1->forward,point1);
point1->forward->next=point2;
point1->forward=point2;
}
point1=point1->next;
}
if(point1==NULL)//
{
if((rear->address+rear->size)==address)//如果与rear相邻
{
rear->size=rear->size+size;
}
else
{ //另立新的rear
point2=new linknode(size,address,rear,NULL);
rear->next=point2;
rear=point2;
}
}
}
//判断是否输出完节点
bool first_fit_link::over()
{
{
work=head;
return true;
}
else
{
return false;
}
}
//返回链表元素
Job first_fit_link::returnjob()
{
linknode * point1=work;
Job pointNum;
if(point1!=NULL)
{
pointNum.size=point1->size;
}
work=work->next;
return pointNum;
}
#endif
最佳适应算法代码
#ifndef Bestfit_H
#define Bestfit_h
#include "Job.h"
//最佳适应算法头文件
class bestfit_link;
class bestnode
{
friend class bestfit_link;
private:
int size;//作业大小
int address;//作业首地址
bestnode * forward;
bestnode * next;
public:
bestnode(int s,int a,bestnode * f,bestnode * n)//初始化
{
size=s;
address=a;
forward=f;
next=n;
}
};
class bestfit_link
{
private:
bestnode * head;//头指针
bestnode * rear;//尾指针
bestnode * work;//标记指针
public:
bestfit_link()//初始化
{
head=NULL;
rear=NULL;
work=NULL;
}
~bestfit_link()//析构函数
{
bestnode * point1;
while(head!=NULL)
{
point1=head;
head=head->next;
delete point1;
}
}
Job returnjob();//返回链表元素
bool over();//判断是否输出完节点元素
int allot(int size);//分配
};
//分配函数，如果分配成功，返回作业地址，否则返回1000
int bestfit_link::allot(int size)
{
int address=1000;
bestnode * point1=head;
bestnode * point2;
while(point1!=NULL)
{
if(sizesize)//如果申请空间小于该节点，对该节点改动
{
address=point1->address;
point1->size=point1->size-size;
point1->address=point1->address+size;
return address;//分配成功，返回address
}
{
if(point1==head)//如果是头节点
{
address=head->address;
point2=head;
存储器管理---动态分区分配算法的模拟
head=head->next;
head->forward=NULL;
work=head;若图片无法显示请联系QQ3710167
delete point2;
return address;//分配成功，返回address
}
if(point1==rear)//如果是尾节点
{
address=rear->address;
point2=rear;
rear=rear->forward;
rear->next=NULL;
delete point2;
return address;//分配成功，返回address
}
if(point1!=head&&point1!=rear)
{
address=point1->address;
point2=point1->forward;
bestnode * point3=point1->next;
point2->next=point3;
point3->forward=point2;
delete point1;
return address;//分配成功，返回address
}
若图片无法显示请联系QQ3710167
}
}
if(point1==NULL)
{
return address;//没有合适的空间，分配不成功，返回1000
}
}
//按空间大小递增建立链表
{
if(head==NULL)
{
head=rear=work=new bestnode(size,address,NULL,NULL);
}
else
{
bestnode * point1=head;
bestnode * point2;
while(point1!=NULL)
{
if(size<=point1->size)
{
if(point1==head)//如果是首部，则改动头指针
{
point2->next=head;
head->forward=point2;
head=point2;
work=point2;
}
else//如果插入点在链中
{若图片无法显示请联系QQ3710167
point2->forward=point1->forward;
point2->next=point1;
point1->forward->next=point2;
point1->forward=point2;
}
break;//插入完成，退出
}
else
{
point1=point1->next;//寻找下一个位置
}
}
if(point1==NULL)//如果插入点在链尾，改动尾指针
{
rear->next=point2;
rear=point2;
}
}
}
//判断是否输出完节点
bool bestfit_link::over()
{
if(work==NULL)
{
work=head;
return true;
}
else
{
return false;
}
}
//返回链表元素
Job bestfit_link::returnjob()
{
bestnode * point1=work;
Job pointNum;
if(point1!=NULL)
{
pointNum.size=point1->size;
}若图片无法显示请联系QQ3710167
work=work->next;
return pointNum;
}
#endif
总 结
张的总结：
程序设计在于有耐心，要细心。本次课程设计让我体会到一个程序员的枯燥与无奈，面对一台“笨”电脑，要把任何细节、任何“突发”情况考虑得仔仔细细，就像是让一头猪算“1+1=？”……
在把核心代码通过可视化界面实现，需要建立许多接口函数。由输入接口接受数据，需要入口函数；把核心代码运算的结果输出到界面，需要出口函数。而且体会到可视化程序的设计，能更好的理解程序的运行机制，有助于更好的设计程序。
赵的总结：
经过这次操作系统的课程设计，我重新将c语言的知识复习了一遍，对c的认识也有了更一步的提高，受益颇深。在这个过程中，遇到了许多意向不到的问题，自己感觉最主要的就是在下笔写程序之前，一定要认真思考，将要解决的问题和可能出现的问题充分考虑到，从整体上形成一个清晰的流程图，这样以后的编程工作才能变得更加有意义，否则会事倍功半的，将会在编程工作中遇到许多逻辑上的错误和考虑不周到而导致的错误。
虽然我设计的仅仅是核心的东西,但是就是这仅有的几个设计，也让我对c语言的一些知识的运用更熟练，包括对常用库函数的了解，函数间的参数传递，字符串、链表、类、结构体的运用等。两个人的配合也让我认识到了, “合作”在编写程序这个过程中的重要性,只有通过好好的配合才能达到最好的效果，否则会越配合越乱，没有结果。这次设计，可以说是一个挑战，因为从来没有写过这么长的程序，当然遇到的问题也是相当多的，但最终算是完成了任务吧，感触颇深，让自己看清楚了自己，也有了一丝信心。让我明白了：这年头，怕就怕“认真”两个字！
