动态分区分配方式的模拟C语言代码和C代码
实验三使用动态分区分配方式的模拟
1、实验目的
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
2、实验内容
(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。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
程序代码——C语言实现
#include
#include
struct node //空闲分区链结点的定义
{
node *before;
node *after;
int size;
int address;
int state;
};
node L;
struct usenode
{
usenode *next;
int num;
int add;
int size;
}U,*n;
void Init() //空闲分区链的初始化
{
node *p;
p=(node *)malloc(sizeof(node));
p->before=&L;
p->after=NULL;
p->size=640;
p->address=0;
p->state=0;
L.after=p;
L.before=NULL;
L.size=0;
U.next=NULL;
n=&U;
}
node *search(int a)
{
node *p=L.after;
if(p==NULL)
{
printf("没有空闲的区域!");
p=NULL;
return p;
}
else
{
while(p!=NULL && a>p->size)
p=p->after;
if(p==NULL)
{
printf("没有找到合适的空闲空间!");
p=NULL;
return p;
}
else
return p;
}
}
void recovery(int a,int b) //内存回收算法
{
node *c,*s,*r=L.after;
node *d=L.after,*e;
usenode *k=U.next,*h=&U;
while(k!=NULL && a!=k->num)
{
h=k;
k=k->next;
}
if(k==NULL)
printf("没有找到这样的作业!");
else
{
h->next=k->next;
if(h->next==NULL)
n=h;
}
while(r!=NULL) //若回收得到的空闲块的前方有空闲块合并此空闲块{
if(k->add==r->address+r->size)
{
r->size=r->size+k->size;
break;
}
else
r=r->after;
}
if(r==NULL) //若回收得到的空闲块的后面有空闲块合并此空闲块{
r=L.after;
while(r!=NULL)
{
if(k->add+k->size==r->address)
{
r->address=k->add;
r->size=r->size+k->size;
break;
}
else
r=r->after;
}
}
while(d!=NULL) //保证空闲链表中没有相邻的空闲空间{
if(d->after!=NULL)
e=d->after;
else
break;
if(d->address+d->size==e->address)
{
d->after=e->after;
while(e->after!=NULL)
e->after->before=d;
d->size=d->size+e->size;
free(e);
break;
}
else
d=d->after;
}
if(r==NULL)
{
r=L.after;
c=(node *)malloc(sizeof(node));
c->size=b;
c->address=k->add;
if(L.after==NULL)
{
c->after=L.after;
c->before=&L;
L.after=c;
}
else
{
r=L.after;
while(r!=NULL)
{
if(r->address>c->address)
{
c->after=r;
c->before=r->before;
r->before->after=c;
r->before=c;
free(k);
return;
}
else
r=r->after;
}
}
}
free(k);
}
void alloc(int a ,int b) //分配内存算法
{
node *p,*q=L.after;
usenode *m;
p=search(b);
if(p==NULL)
return;
m=(usenode *)malloc(sizeof(usenode));//生成一个被占用链表的结点,并插入到该链表的尾部m->add=p->address;
m->size=b;
m->num=a;
m->next=n->next;
n->next=m;
n=m; //保证n始终指向被占用链表的尾部，方便以后新生成结点的插入if(p->size>b) //如果申请空间的大小小于找到空闲空间的大小的处理
{
p->size=p->size-b;
p->address=p->address+b;
}
else //如果申请空间的大小等于找到空闲空间的大小的处理
{
p->before->after=p->after;
if(p->after!=NULL)
p->after->before=p->before;
free(p);
}
}
void sort() //对空闲链表进行排序
{
int max;
node *p,*q,*r,*s;
node a;
p=L.after;
while(p!=NULL) //让指针q指向链表的最后一个结点{
q=p;
p=p->after;
}
if(L.after->after==NULL)
return;
else
{
while(p!=q)
{
s=r=p=L.after;
max=r->size;
while(s!=q->after)
{
if(s->size>max)
{
max=s->size;
r=s;
s=s->after;
}
else
s=s->after;
}
a.size=q->size;
a.address=q->address;
q->size=r->size;
q->address=r->address;
r->size=a.size;
r->address=a.address;
if(q->before->before==&L)
return;
else
q=q->before;
}
}
}
void Print()
{
node *p=L.after;
usenode *q=U.next;
int i=1;
printf("\n空闲区域列表:\n");
printf("FREEID address size\n");
while(p!=NULL)
{
printf("%-10d",i);
printf("%-10d",p->address);
printf("%d\n",p->size);
p=p->after;
i++;
}
if(q==NULL)
return;
else
{
printf("\n已分配区域列表:\n");
printf("WORKID address size\n");
while(q!=NULL)
{
printf("%-10d",q->num);
printf("%-10d",q->add);
printf("%d\n",q->size);
q=q->next;
}
}
}
void firstfit() //首次适应算法
{
int a,b,i;
Init();
Print();
while(1)
{printf("\n1、申请空间\n");
printf("2、释放空间\n");
printf("3、退出首次适应算法\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("请输入申请空间的作业号:");
scanf("%d",&a);
printf("请输入申请空间的大小:");
scanf("%d",&b);
alloc(a,b);
Print();
break;
}
case 2:
{
printf("请输入释放空间的作业号:");
scanf("%d",&a);
printf("请输入释放空间的大小:");
scanf("%d",&b);
recovery(a,b);
Print();
break;
}
case 3:printf("\n");return;
}
}
}
void bestfit()
{
int a,b,i;
Init();
Print();
while(1)
{printf("\n1、申请空间\n");
printf("2、释放空间\n");
printf("3、退出最佳适应算法\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("请输入申请空间的作业号:");
scanf("%d",&a);
printf("请输入申请空间的大小:");
scanf("%d",&b);
alloc(a,b);
sort();
Print();
break;
}
case 2:
{
printf("请输入释放空间的作业号:");
scanf("%d",&a);
printf("请输入释放空间的大小:");
scanf("%d",&b);
recovery(a,b);
sort();
Print();
break;
}
case 3:printf("\n");return;
}
}
}
void main()
{
int i;
while(1)
{
printf("1、首次适应算法\n");
printf("2、最佳适应算法\n");
printf("3、退出\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:firstfit();break;
case 2:bestfit();break;
case 3:return;
}
}
}
运行结果
①开始界面
②首次适应算法
③最佳适应算法
程序代码——C++语言实现
//*************************************************************** //******** 动态分区分配方式的模拟 *********
//***************************************************************
#include
#include
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //最大内存空间为640KB
typedef int Status;
typedef struct freearea//定义一个空闲区说明表结构
{
int ID; //分区号
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;
//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}DuLNode,*DuLinkList;
DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点
Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int,int);//首次适应算法
Status Best_fit(int,int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表
Status Initblock()//开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
return OK;
}
//----------------------- 分配主存 ------------------------- Status alloc(int ch)
{
int ID,request;
cout<<"请输入作业(分区号)：";
cin>>ID;
cout<<"请输入需要分配的主存大小(单位:KB)：";
cin>>request;
if(request<0 ||request==0)
{
cout<<"分配大小不合适，请重试！"< return ERROR; } if(ch==2) //选择最佳适应算法 { if(Best_fit(ID,request)==OK) cout<<"分配成功！"< return OK; } else //默认首次适应算法 { if(First_fit(ID,request)==OK) cout<<"分配成功！"< return OK; } } //------------------ 首次适应算法 ----------------------- Status First_fit(int ID,int request)//传入作业名及申请量 { //为申请作业开辟新空间且初始化 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; while(p) { if(p->data.state==Free && p->data.size==request) {//有大小恰好合适的空闲块 p->data.state=Busy; p->data.ID=ID; return OK; break; } if(p->data.state==Free && p->data.size>request) {//有空闲块能满足需求且有剩余" temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; } p=p->next; } return ERROR; } //-------------------- 最佳适应算法 ------------------------ Status Best_fit(int ID,int request) { int ch; //记录最小剩余空间 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; DuLNode *q=NULL; //记录最佳插入位置 while(p) //初始化最小空间和最佳位置 { if(p->data.state==Free && (p->data.size>request || p->data.size==request) ) { q=p; ch=p->data.size-request; break; } p=p->next; } while(p) { if(p->data.state==Free && p->data.size==request) {//空闲块大小恰好合适 p->data.ID=ID; p->data.state=Busy; return OK; break; } if(p->data.state==Free && p->data.size>request) {//空闲块大于分配需求 if(p->data.size-request { ch=p->data.size-request;//更新剩余最小值 q=p;//更新最佳位置指向 } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else {//找到了最佳位置并实现分配 temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.size=ch; return OK; } } //----------------------- 主存回收 -------------------- Status free(int ID) { DuLNode *p=block_first; while(p) { if(p->data.ID==ID) { p->data.state=Free; p->data.ID=Free; if(p->prior->data.state==Free)//与前面的空闲块相连 { p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; } if(p->next->data.state==Free)//与后面的空闲块相连 { p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; } break; } p=p->next; } return OK; } //--------------- 显示主存分配情况 ------------------ void show() { cout<<"+++++++++++++++++++++++++++++++++++++++\n"; cout<<"+++ 主存分配情况 +++\n"; cout<<"+++++++++++++++++++++++++++++++++++++++\n"; DuLNode *p=block_first->next; while(p) { cout<<"分区号："; if(p->data.ID==Free) cout<<"Free"< else cout< cout<<"起始地址："< cout<<"分区大小："< cout<<"状态："; if(p->data.state==Free) cout<<"空闲"< else cout<<"已分配"< cout<<"——————————————"< p=p->next; } } //----------------------- 主函数--------------------------- void main() { int ch;//算法选择标记 cout<<" 动态分区分配方式的模拟 \n"; cout<<"************************************\n"; cout<<"** 1)首次适应算法 2)最佳适应算法 **\n"; cout<<"************************************\n"; cout<<"请选择分配算法："; cin>>ch; Initblock(); //开创空间表 int choice; //操作选择标记 while(1) { cout<<"********************************************\n"; cout<<"** 1: 分配内存 2: 回收内存 **\n"; cout<<"** 3: 查看分配 0: 退出 **\n"; cout<<"********************************************\n"; cout<<"请输入您的操作："; cin>>choice; if(choice==1) alloc(ch); // 分配内存 else if(choice==2) // 内存回收 { int ID; cout<<"请输入您要释放的分区号："; cin>>ID; free(ID); } else if(choice==3) show();//显示主存 else if(choice==0) break; //退出 else //输入操作有误 { cout<<"输入有误，请重试！"< } } } 课程设计说明书 题目计算器程序设计 起讫日期 2006 年 7月 3日至 2006 年 8月 6日 所在院系软件学院 专业机械+软件班级 04-2 学生姓名偶偶哦学号 指导教师 2006年 8 月日 摘要 当今社会是信息社会，科技经济高速发展的社会！为了更方便人们的工作生活和加速人们处理信息的速度，计算器应运而生。由于它体积小巧，携带方便，价格便宜，构造简单等诸多的优点成为人们生活中的必备品！ 随着科技的发展计算器的种类变得更多，功能变得更强大，体积变得更小！电脑的出现改变人们的生活习惯，很多事情都可以电脑来完成！电脑的更大一个优点就是可以通过软件的应用无限的延伸电脑功能的外延！下面我们将用我们学习的c语言编写一个简易的计算器程序！实现简单的初步的计算功能！ 本程序的编写基础是Tubro 汉化版,它在tubro c的原有基础上实现了多汉字的支持方便了我们的使用。生成的程序可移植性强兼容性好稳定！现在只实现了加、减、乘、除、求幂、求模，求平方根，求Sin，求Cos，求Log10，以及一个时钟原代码。这个系统是基于软件发展的生命周期来研制的，它可以直接输入数学表达式，不需要任何转换，就可以直接输出数学四则运算的结果。但是，每次只能运算一个表达式。不能运算多个表达式。在程序里面在添加一组选择函数即可。本论文主要介绍了本课题的开发背景，开发的过程和所要完成的功能。重点的说明了系统设计思想，设计的步骤、难点技术和解决方案。 关键词：C语言 Tubro c 汉化版计算器时钟 目录 第一章综述 (1) 1．1 课题的现实意义 (1) 1．2 软件环境 (1) 1．3 硬件环境 (1) 第二章系统设计流程图 (2) 2．1 系统流程图 (2) 2．2 主要功能表 (2) 第三章系统分析和设计 (3) 3．1 图形的绘制和输出 (3) 3．2 文本的输出显示 (3) 3．3 计算函数的调用 (4) 3．4 程序的运行和退出 (5) 第四章系统测试 (6) 4．1 系统测试 (6) 4．2 调试 (6) 4．3 错误原因分析一 (6) 4．4 错误原因分析二 (6) 第五章用户使用说明书 (8) 分区分配算法的实现 实验要求： ?分区空闲表要表示出分区号、始址、大小 ?作业序列能够动态输入 ?内存不足，必须有提示功能 ?总结收获体会及对该题解的改进意见和见解 （红色字体为再修改处） 源代码： /********************操作系统实验四:首次适应(first fit)算法的分区分配算法*******************/ #include } } } printf("\n---------首次适应算法按地址从小到大排列后空闲区---------\n"); printf("\t分区号\t\t大小\t\t起始地址\n"); for(i=0;i 可变分区存储管理 设计思路： 整体思路： 可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个 空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所才用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值min size，如果空闲区的大小减去作业需求长度得到的值小于等于min size，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 关于分配留下的内存小碎片问题： 当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于min size，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于 课程设计名称：C语言课程设计课程设计题目：简单计算器程序 目录 第1章需求分析 (1) 1.1设计要求 (1) 1.2任务 (1) 第2章总体设计 (2) 2.1设计简介及设计方案论述 (2) 2.2功能模块层次图 (2) 第3章详细设计 (3) 3.3由（后缀）逆波兰表达式计算中缀表达式原理 (8) 3.3.1算法描述 (8) 第4章调试分析 (10) 4.1程序设计中所遇到的错误及犯错的原因 (10) 4.2错误的解决方法 (10) 第5章用户手册 (11) 总结 (15) 参考文献 (16) 附录（程序清单） (17) 第1章需求分析 1.1 设计要求 （1）用 C 语言数据结构实现程序设计； （2）利用结构体、栈、进行相关信息处理； （2）系统的各个功能模块要求用函数的形式实现； （4）界面简单，可操作性高。 1.2任务 （1）定义一个结构体类型数组，输入0~9 及+、--、*等符号的信息，将其信息存储起来； （2）输入简单的加减乘除算术计算式，并在屏幕上显示逆波兰（后缀式）表达式和计算结果； （3）编写代码； （4）程序分析与调试。 说明： 本课程设计将实现一个简单计算器。在功能上尽量模仿windows 的计算器。系统界面不做牵制要求。该程序能实现标准型中+、-、*、/、（、）、.、的混合运算表达式（一般意义上的中缀表达式），将其转换成逆序波兰表达式（后缀表达式）并计算输出结果。在进行运算后可以选择继续运算或者结束当前运算。即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间，对人们的生活有一定的帮助。 第2章 总体设计 2.1设计简介及设计方案论述 逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相 关的两个运算对象之间，所以，这种表示法也称为中缀表达式。波兰逻辑学家 J.Lukasiewicz 于 1929 年提出了另一种表示表达式的方法。按此方法，每一运算符都置 于其运算对象之后，故称为后缀表达式。 后缀表达式的优点是显而易见的， 编译器在处理时候按照从左至右的顺序读取逆波 兰表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象进行计算，这个过程正好符合了计算机计算的原理。后缀表达式比前缀表达式更加易于转换，并且它的最左面一定为数字，这一点在实 际编程的时候就会体会到它的好处了。 逆波兰表达式有一个更大的优点，就是拆括号，根据运算符的级别将中缀表达式转 换成逆波兰表达式后，运算顺序就已经替代了运算符的级别，这样也避免了括号提高运 算级别的特殊处理。 2.2功能模块层次图 将算术表达式转化为逆波兰表达式 计算逆波兰表达式的值 简单计算器 表 达 式 格 式 转 换 系统 求 值 计 算 系 统 操作系统实验四 【实验题目】：动态分区分配算法 【实验学时】：4学时 【实验目的】 通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。 【实验内容及要求】 问题描述： 设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求： 1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。 2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。 3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m。 4）输出：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法，最终内存空闲分区的分配情况。 实现源代码： #include 动态分区分配算法 一实验内容与要求 内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了三种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最佳适应算法。 要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有首次适应算法，循环首次适应算法，最佳适应算法。特别注意分区回收时，相邻空闲分区需要合并。 (1)参考操作系统教材理解这3种分配算法以及回收算法。 (2)实现3种分配算法以及回收算法。 (3)已知作业申请内存和释放内存的序列，给出内存的使用情况。 (4)作业申请内存和释放内存的序列可以存放在文本文件中。 (5)设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计) (6)可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。 二、需求分析 本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。 动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数 目也是可变的。 分区分配算法： 1.首次适应法： 为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。 特点：优先利用内存中底地址部分的空闲分区 (将所有空闲区,按其地址递增的顺序链接) 2.循环首次适应算法 该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 3.最佳适应算法： 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。 三、概要设计 动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示： typedef struct freearea//定义一个空闲区说明表结构 { int ID; //分区号 long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType; typedef struct DuLNode //double linked list { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList; 使用动态分区分配方式的模拟 1内容 （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。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 2、示例程序： //Tittle: 使用动态分区算法的模拟 //author: XuYongzhen #include 目录 一.课程设计目的 (1) 二.设计环境 (1) 三.设计内容 (1) 四.设计说明 (2) 五.设计程序流程图 (2) 六.调试 (4) (1)错误原因分析一 (4) (2)语法错误 (5) (3)逻辑错误 (5) 七. 调试结果图 (6) 八. 结论与心得体会 (7) 九.附录 (8) 具体代码实现 (8) 十．参考文献 (18) 一.课程设计目的 1.通过一个学期的学习，我认为要学号C语言程序这门课程，不仅要认真阅读课本知识，更重要的是要通过上机实践来巩固我 们的知识，特别是学计算机专业的，我们更应该注重这一环节， 只有这样我们才能成为一个合格的计算机人才。通过这一个课程 设计，进一步来巩固所学的语句，如：循环，和分支结构的运用。还要熟悉四则运算和函数的算法。 2.通过这次课程设计扩展自己的知识面，课本上的东西是远 远不够的，可以通过上网或去图书馆查资料等方式得到一些新的 知识， 3.通过课程设计，加深对课程化设计思想的理解，能进行一 个系统功能分析，并设计一个合理的模块化结构，提高程序开发 能力。 二.设计环境 1.硬件：一台完整的电脑，包括键盘、鼠标，最小硬盘空间1GHz 2.软件：安装有Microsoft visual c++6.0 三.设计内容 以简易计算器为例，通过对简单应用软件计算器的设计，编制、调试，实现 简单的加，减，乘，除等运算，以学习应用MFC库类编写对话框的原理，加深对C++类的学习及应用。 （1）定义一个结构体类型数组，输入0~9及+、--、*等符号的信息，将其信息存入文件中； （2）输入简单的加减乘除算术计算式，并在屏幕上显示计算结果； （3）画出部分模块的流程图； （4）编写代码； （5）程序分析与调试。 四.设计说明 1)包含的功能有：加、减、乘、除运算，开方、平方等功能。 (2)计算器上数字0—9为一个控件数组，加、减、乘、除为一个控件数组，其余为单一的控件。 (3)输入的原始数据、运算中间数据和结果都显示在窗口顶部的同一个标签中。 (4)计算功能基本上是用系统内部函数。 (5)程序可以能自动判断输入数据的正确性，保证不出现多于一个小数点、以0开头等不正常现象。 (6)“CE”按钮可以清除所有已输入的数据从头计算 五.设计程序流程图 南昌大学实验报告 学生姓名：马江涛学号： 8000612091 专业班级：计算机软件121班 实验类型：□验证□综合□设计□创新实验日期： 2014-05-08 实验成绩： 【实验要求】 1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。 2、假设初始状态下，可用内存空间为640K，并依次有下列请求序列： 1)作业1申请130KB。 2)作业2申请60KB。 3)作业3申请100KB。 4)作业2释放60KB。 5)作业4申请200KB。 6)作业3释放100KB。 7)作业1释放130KB。 8)作业5申请140KB。 9)作业6申请60KB。 10)作业7申请50KB。 11)作业6释放60KB。 请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。 3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果； 4、具体要求： （1）对你的程序关键代码处进行注释。 （2）给出实验数据，对结果进行分析，说明对相关知识点的理解。 【实验目的】 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 【实验思路】 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。 最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则 实验一多功能计算器 一、问题描述 设计一个多功能计算器,可以完成基本的计算。 设计要求: 1、具备整型数据、浮点型数据的算术(加、减、乘、除)运算功能。依次输入第一个运算数、运算符(+,-,*,/)、第二个运算数,然后输出结果。结果可以作为下一个运算的第一运算数。按‘C’清屏,按‘R’返回菜单。 例如:输入:2 + 5 输出:7 2、实现单运算符表达式计算的功能。输入的操作数可以包含整数或浮点数。输入表达式如下: 例如:输入:2+5 输出:7 二、算法说明 1.数据结构说明(可以图示说明,也可以文字说明) 本程序主要根据选择菜单编写了六个自定义函数,用于在main()函数中调用,在main()中,用一个字符变量num1来记录下菜单选项的标号,根据num1的值来决定调用哪个函数。 程序要完成的功能及所要用到的函数如下: 下面就是整个程序的流程图: 2.算法说明(即函数说明) void suanshuyunsuan() //做算术运算时调用的函数 void suanshuyunsuan2() //选择继续做算术运算调用的函数,将上次运算的结果做为下次算术运算的第一个操作数//判断算术运算就是否继续 void panduan() //判断算术运算就是否继续 void biaodashiyunsuan() //单运算符表达式实现函数 void qingping() //清除屏幕 void fanhuicaidan() //显示菜单 三、测试结果(这部分需文字与图示结合) 1.第一组测试用例 (1)测试输入: 测试目的:测试算术运算的功能 结果输出: (2)再一次输入:1测试目的:测试算术运算就是否能继续 结果输出: (3)这时输入:0 测试目的:退出算术运算 结果输出: 动态分区分配管理系统 学院 专业 学号 学生姓名 指导教师姓名 2014年3月14 日 目录 1程序设计的内容和相关的要求---------------------------------2 2程序总的功能说明--------------------------------------------3 3程序的模块的说明--------------------------------------------4 4程序设计的流程图--------------------------------------------5 5程序的操作说明及运行结果-----------------------------------7 6源程序-------------------------------------------------------11 7心得体会----------------------------------------------------27 1程序设计的内容和相关的要求： 课程设计的目的：操作系统课程设计是计算机学院重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 ● 进一步巩固和复习操作系统的基础知识。 ● 培养学生结构化程序、模块化程序设计的方法和能力。 ● 提高学生调试程序的技巧和软件设计的能力。 ● 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能 力。 实现的任务：编写一个动态分区分配程序。 设计内容： 用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法 1.首次适应算法 2.循环首次适应算法 设计要求： 1.内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的； 2.作业数量、作业大小、进入内存空间、运行时间需要通过界面进行输入； 3.可读取样例数据（要求存放在外部文件夹中）进行作业数量、作业大小、进图内存时间、运行时间的初始化； 4.根据作业进图内存的时间，采用简单的先进先出原则进行从外村到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。（为了简化，不考虑cpu的调度与切换，运行时间为作业在内存中驻留的时间）； 5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示； 6.采用可视化界面，可随时暂停显示当前内存分配和使用情况图。 2程序总的功能说明： 本程序可以从界面直接输入作业并进行动态的内存分配，也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去； 实验三使用动态分区分配方式的模拟 1、实验目的 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 2、实验内容 (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。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 程序代码——C语言实现 #include void Init() //空闲分区链的初始化 { node *p; p=(node *)malloc(sizeof(node)); p->before=&L; p->after=NULL; p->size=640; p->address=0; p->state=0; L.after=p; L.before=NULL; L.size=0; U.next=NULL; n=&U; } node *search(int a) { node *p=L.after; if(p==NULL) { printf("没有空闲的区域!"); p=NULL; return p; } else { while(p!=NULL && a>p->size) p=p->after; if(p==NULL) { printf("没有找到合适的空闲空间!"); p=NULL; return p; } else return p; } } void recovery(int a,int b) //内存回收算法 { C++语言编写。。 #include char *base; }stack_char; stack_num S_num;//定义 stack_char S_char;//定义 char fu[18] = {'\n', ')', '+', '-', '*', '/', '%', '^', 'Q', 'L', 'C', 'S', 'T', 'c', 's', 't', '('}; int compare[1000];//表现出各运算符号的优先级 double shu[1000];//存储"数"的数组 double dai_result;//运算的结果，是为了处理M运算(简介函数里有M的定义) int biao = 0;//和dia_result一样，为了处理M运算 char line[SIZE];//输入的所要计算的表达式 void init()//初始化 { compare[fu[0]] = -2;//用数字的大小表现出符号的优先级 compare[fu[1]] = -1; compare[fu[2]] = 2; compare[fu[3]] = 2; compare[fu[4]] = 4; compare[fu[5]] = 4; compare[fu[6]] = 4; 课程设计报告 课程设计题目：循环首次适应的动态分区分配算法模拟 专业：计算机科学与技术 班级：10204102 姓名：谱 学号: 10204102 指导教师:高小辉 2013年1月11 日 目录 一．循环首次适应算法 (3) 1. 概述 (3) 2．需求分析 (3) 二．实验指导 (4) 1.基本思想 (4) 2．数据结构 (4) 三．运行环境 (6) 四．流程图 (6) 五．循环首次适应算法代码 (5) 六．调试结果 (11) 七、总结 (14) 八．参考文献 (14) 一．循环首次适应算法 1.概述： 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。 2. 需求分析 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。 空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。 作业完成时，需要释放作业所占空间，此时要考虑到四种情况： (1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一 分区的大小。 (2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址 作为新空闲区的首址。 (3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空 闲分区的表项和首址。 (4)回收区单独存在。 二、实验指导 1．基本思想 动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。 2．数据结构 动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。 c++动态分区分配算法模拟(操作系统课程 设计) 课程设计 课程设计名称：操作系统课程设计 专业班级： 学生姓名： 学号： 指导教师： 课程设计时间：6月13日-——6月17日 计算机科学专业课程设计任务书 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 1：需求分析 （1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放 130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请 50KB；作业6释放60 KB。采用首次适应算法进行内存块的分配和回 收，同时显示内存块分配和回收后空闲内存分区链的情况。 2：概要设计 （1）数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系 统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的 各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业 总数，已分配的内存块数，剩余的内存块数。 （2）主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函 数，循环处理11个作业步。 （3）分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于 /*9.3.2 源程序*/ /***pcb.c***/ #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 32767 typedef struct node /*设置分区描述器*/ { int address,size; struct node *next; }RECT; /*函数原型*/ RECT *assignment(RECT *head,int application); void acceptment1(RECT *head,RECT *back1); void acceptment2(RECT *head,RECT *back1) ; int backcheck(RECT *head,RECT *back1); void print(RECT *head); /*变量声明*/ RECT *head,*back,*assign1,*p; int application1,maxblocknum; char way; /*主函数*/ main() { char choose[10]; int check; head=malloc(sizeof(RECT)); /*建立可利用区表的初始状态*/ p=malloc(sizeof(RECT)); head->size=MAX; head->address=0; head->next=p; maxblocknum=1; p->size=MAX; p->address=0; p->next=NULL; print(head); /*输出可利用表初始状态*/ printf("Enter the way(best or first(b/f)\n");/*选择适应策略*/ scanf("%c",&way); do{ printf("Enter the assign or accept(as/ac)\n"); scanf("%s",choose); /*选择分配或回收*/ if(strcmp(choose,"as")==0) /*as为分配*/ { printf("Input application:\n"); 实验四动态分区分配算法实验报告及程序 ————————————————————————————————作者：————————————————————————————————日期： 实验报告四动态分区分配算法 班级学号姓名 一、实验目的 动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法，分别是 1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。 二、实验环境 普通的计算机一台，编译环境Microsoft Visual C++ 6.0 三、算法思想 1．数据结构 （1）分区开始地址startaddress （2）分区大小size （3）分区状态state 2．功能介绍 （1）首次适应算法 在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 （2）循环首次适应算法 该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 C语言制作简单计算器 一、项目介绍 我们要用c语言做一个简单的计算器，进行加、减、乘、除操作。本程序涉及的所有数学知识都很简单，但输入过程会增加复杂性。我们需要检查输入，确保用户没有要求计算机完成不可能的任务。还必须允许用户一次输入一个计算式，例如：32.4+32 或者9*3.2 项目效果图 编写这个程序的步骤如下： ?获得用户要求计算机执行计算所需的输入。 ?检查输入，确保输入可以理解。 ?执行计算。 ?显示结果。 三、解决方案 1.步骤1 获得用户输入是很简单的，可以使用printf()和scanf()。下面是读取用户输入的程序代码： #include 动态分区分配存储管理系统 一、设计目的与内容 用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算 法 1）首次适应算法 2）循环首次适应算法 1. 内存中有0-100M 的空间为用户程序空间，最开始用户空间是空闲的。 2. 作业数量、作业大小、进入内存时间、运行时间需要通过界面进行输入。 3. 可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、进入内存时间、 运行时间的初始化。 4. 根据作业进入内存的时间，采用简单的先进先出原则进行从外存到内存的调度，作业具 有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。 5. 能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作。 二、算法的基本思想 1、定义基本结构： 1作业结构： typedef struct JOB { int num; //作业号 int size; //作业大小 int ctime; //作业进入时间 int rtime; //作业运行时间 int state; //作业状态 }Job ; 2)分区结构： typedef struct DuLNode { int ID; //分区号 int start; //开始地址 int size; //大小 int state; //0=尚未使用1=使用2=释放 struct DuLNode *prior;//前驱指针 struct DuLNode *next; //后即指针 }DuLNode, * DuLinkList; 2、基本操作： int Firstfit(int);//首次适应算法 int Next_fit(int); //循环首次适应算法 void showJob(int); //显示作业表 void showPartiton(DuLinkList);//显示分区表 DuLinkList InitpartitionList(DuLinkList &p);//初始化 void huishou(DuLinkList pl3,DuLinkList &pl);//回收函数 int Putin(int &n);//输入函数，输入作业相关信息 3、首次适应算法 空闲分区链以地址递增的次序链接，分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，取消的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。 4、循环首次适应算法 在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。c语言程序设计课程计算器设计报告
分区分配算法的实现
动态分区式存储管理
C语言课程设计 简单计算器程序
操作系统实验四实验报告动态分区分配算法
动态分区分配算法资料
动态分区分配方式模拟
C语言简易计算器的实现
实验报告-动态分区分配算法
C语言实现计算器功能
动态分区分配管理系统
动态分区分配方式的模拟C语言代码和C代码
大学计算机c语言计算器源代码
循环首次适应的动态分区分配算法模拟
最新c++动态分区分配算法模拟(操作系统课程设计)
存储管理分区分配算法
实验四动态分区分配算法实验分析报告及程序
C语言制作简单计算器
动态分区分配存储管理系统
- 动态分区分配方式的模拟实验报告模板
- 动态分区分配方式的模拟实验报告模板
- 动态分区分配方式的模拟实验报告模板
- 存储管理——动态分区分配回收算法的模拟
- 存储管理动态分区分配算法的模拟
- 采用首次适应算法实现动态分区分配过程的模拟
- 循环首次适应的动态分区分配算法模拟
- A.5动态分区分配方式的模拟实验报告
- 实验四 动态分区分配方式内存管理模拟
- c++动态分区分配算法模拟(操作系统课程设计
- 动态分区分配方式模拟
- 实验四--动态分区分配方式的模拟-答案
- 使用动态分区分配方式的模拟
- 动态分区分配方式的模拟实验报告材料实用模板
- 存储管理---动态分区分配算法的模拟
- 最新c++动态分区分配算法模拟(操作系统课程设计)
- 动态分区分配方式的模拟
- 动态分区分配与回收算法的模拟
- 操作系统实验—动态分区分配算法
- 动态分区分配方式的模拟