动态分区分配存储管理系统学院专业学号学生姓名指导老师2014年3月19日目录一、设计目的与内容 (4)1、设计目的 (3)2、设计内容 (3)3、设计要求 (3)二、算法的基本思想 (3)1、首次适应算法 (3)2、循环首次适应算法 (3)三、主要功能模块流程图 (4)1、主函数流程图 .......................................................................................................................... .42、首次适应算法流程图.............................................................................................................. .53、循环首次适应算法流程图 ..................................................................................................... .6四、系统测试 ......................................................................................................................................... .7输入界面，按要求输入： (7)五、结论 (8)六、源程序 (9)一、设计目的与内容设计的目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。

●进一步巩固和复习操作系统的基础知识。

●培养学生结构化程序、模块化程序设计的方法和能力。

●提高学生调试程序的技巧和软件设计的能力。

●提高学生分析问题、解决问题以及综合利用C 语言进行程序设计的能力。

设计内容：用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法1.首次适应算法2.循环首次适应算法设计要求：1.内存中有0-100M 的空间为用户程序空间，最开始用户空间是空闲的2.作业数量、作业大小、进入内存时间、运行时间需要通过界面进行输入3.可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、进入内存时间、运行时间的初始化4.根据作业进入内存的时间，采用简单的先进先出原则进行从外存到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。

（为了简化，不考虑CPU 的调度与切换，运行时间为作业在内存中驻留的时间）5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示6.采用可视化界面，可随时暂停显示当前内存分配和使用情况图。

二、算法的思想1、首次适应算法空闲分区链以地址递增的次序链接，分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，取消的空闲分区仍留在空闲链中。

若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。

2、循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业三、主要功能模块流程图主函数首次适应算法：循环首次适应算法四、系统测试程序运行实例如下：输入界面，按要求输入：五、结论作业采用数组形式进行存储，起初想用数组模拟分区，但划分记录比较不易，时间空间复杂度较大，容易混乱，遂决定用链表形式模拟分区情况。

基本能运行符合要求，能模拟出动态分区过程及最终结果六．源程序#include <stdio.h>#include <stdlib.h>#include <iostream.h>#include <windows.h>#define Free 0#define Use 1#define MAX_length 100 //最大内存空间为100MB#define MaxNumber 100int FreePartition[MaxNumber]={16,16,8,32,64,32,8,16,64};//空闲分区int ProcessNeed[MaxNumber]={7,18,9,20,35,8};//每个进程需求int FirstPartition[MaxNumber];//首次int CycleFirstPartition[MaxNumber];//循环int PartitionNumber=9,ProcessNum=6;//空闲分区数及进程数bool v();bool v(){int j;cout<<"首次适应算法"<<endl;// FirstPartitionMethod();for(int i=0;i<ProcessNum;i++)//进程for(j=0;j<ProcessNum;j++)//分区{if(FreePartition[j]>=ProcessNeed[i]){ FirstPartition[i] =j;FreePartition[j]-=ProcessNeed[i];break;}}// c_out(FirstPartition);for(i=0;i<ProcessNum;i++)cout<<FreePartition[i]<<" ";cout<<endl;// Beginning();FreePartition[0]=16; FreePartition[1]=16;FreePartition[2]=8;FreePartition[3]=32;FreePartition[4]=64;FreePartition[5]=32;FreePartition[6]=8;FreePartition[7]=16;FreePartition[8]=64;cout<<"循环首次适应算法"<<endl;//CycleFirstPartitionMethod();j=0;for(i=0;i<ProcessNum;i++)//进程for(;;)//分区{if(FreePartition[j]>=ProcessNeed[i]){ CycleFirstPartition[i]=j;FreePartition[j]-=ProcessNeed[i];break;}j++;j=j%PartitionNumber;}//c_out(CycleFirstPartition);for(i=0;i<ProcessNum;i++)cout<<CycleFirstPartition[i]<<" ";cout<<endl;return 1;}//--------------作业结构体数组----------------------------typedef struct JOB{int num; //作业号int size; //作业大小int ctime; //作业进入时间int rtime; //作业运行时间int state; //作业状态}Job;typedef struct DuLNode{int ID; //分区号int start; //开始地址int size; //大小int state; //0=尚未使用1=使用2=释放struct DuLNode *prior;//前驱指针struct DuLNode *next; //后即指针}DuLNode, * DuLinkList;//------------------------------------------------------------------------------- int Firstfit(int);//首次适应算法int Next_fit(int); //循环首次适应算法void showJob(int); //显示作业表void showPartiton(DuLinkList);//显示分区表//-----------------------------------------------------------------------------//---------------------------全局变量------------------------------------------- int f;Job *A; //排序前Job *a; //排序后Job *temp;//-----------------------------功能函数------------------------------------------- void delay(){for(int x = 10000;x>0;x--)for(int y = 1000;y>0;y--);}//-------------------------------------------------------------------------------- //------------------------初始化--------------------------------------------------- DuLinkList InitpartitionList(DuLinkList &p){p=(DuLinkList)malloc(sizeof(DuLNode));//申请空间if(!p)exit(0);p->size=100; //初始化大小printf("输入分区首地址:");scanf("%d",&p->start);p->state=0; //状态置空闲p->ID=0; //分区号p->next=NULL;p->prior=NULL;return p;}//------------------------------------------------------------------------------//-----------------------------输入函数--------------------------------------------- int Putin(int &n){int i;Job temp;printf("请输入任务数目:");scanf("%d",&n);a=(Job*)malloc(n*sizeof(Job));A=(Job*)malloc(n*sizeof(Job));for(i=0;i<n;i++){printf("\n");printf("信息输入:\n\n");printf("作业号:");scanf("%d",&a[i].num);printf("作业大小:");scanf("%d",&a[i].size);printf("作业进入时间:");scanf("%d",&a[i].ctime);printf("作业运行时间:");scanf("%d",&a[i].rtime);a[i].state=0; //默认状态为Free A[i] = a[i];}for(int j = 0;j < n;j++)for(i = j;i< n;i++)if(a[j].ctime > a[i].ctime){temp = a[j];a[j] = a[i];a[i] = temp;}//冒泡排序freopen("data.txt","w",stdout);for (i = 0;i < n;i++){printf("%d %d %d %d\n",a[i].num,a[i].size,a[i].ctime,a[i].rtime);}fclose(stdout);freopen("CON","w",stdout);printf("保存成功\n\n");return 1;}//----------------------------------------------------------------------------------------//-----------------------------读文件-----------------------------------------------------int order(int &n){Job temp;printf("Input the number of the task:\n");scanf("%d",&n);a=(Job*)malloc(n*sizeof(Job));freopen("data.txt","r",stdin);for(int i=0;i<n;i++){scanf("%d",&a[i].num);scanf("%d",&a[i].size);scanf("%d",&a[i].ctime);scanf("%d",&a[i].rtime);}fclose(stdin);freopen("CON","r",stdin);for(int j = 0;j < n;j++)for(i = j;i< n;i++)if(a[j].ctime > a[i].ctime){temp = a[j];a[j] = a[i];a[i] = temp;}return 1;}//------------------------------------------------------------------------ //-------------------------显示分区-------------------------------void showPartition(DuLinkList pl){printf("\n\t\t\t分区表\n");printf("\t---------------------------------------\n");printf("\t 开始地址\t分区号\t大小状态\n");printf("\t---------------------------------------\n");while(pl){printf("\t %d\t\t%d\t%d\t",pl->start,pl->ID,pl->size);if(pl->state == 0)printf("空闲\n");if(pl->state == 1)printf("已分配\n");pl=pl->next;}printf("\t---------------------------------------\n");}//------------------------------------------------------------------------- //---------------------------------回收函数--------------------------------- void huishou(DuLinkList pl3,DuLinkList &pl)//pl3是分区链表指针pl头{while(pl3){if(pl3->state==0){if(pl3->next&&pl3->prior&&pl3->prior->state==0&&pl3->next->state= =1)//{pl3->size+=pl3->prior->size;pl3->start=pl3->prior->start;pl3->state=0;pl3->ID=0;if(pl3->prior->prior){pl3->prior->prior->next=pl3;//pl3与最前一个pl3->prior=pl3->prior->prior;//}else{pl3->prior=pl3->prior->prior;//pl3指向空pl=pl3;pl3=pl;//pl3与头}}elseif(pl3->prior&&pl3->next&&pl3->next->state==0&&pl3->prior->state==1){pl3->size+=pl3->next->size;pl3->state=0;pl3->ID=0;if(pl3->next->next){pl3->next->next->prior=pl3;//建立新链表pl3与最后一个结点pl3->next=pl3->next->next;//}else{pl3->next=pl3->next->next;//指向空}}else if(!pl3->prior){if(pl3->next->state==0){pl3->size+=pl3->next->size;pl3->state=0;pl3->ID=0;if(pl3->next->next)pl3->next->next->prior=pl3;//pl3与最后pl3->next=pl3->next->next;//}else{pl3->state=0;}}else if(!pl3->next){if(pl3->prior->state==0){pl3->size+=pl3->prior->size;pl3->state=0;pl3->ID=0;pl3->start=pl->start;if(pl3->prior->prior){pl3->prior->prior->next=pl3;//pl3与最前pl3->prior=pl3->prior->prior;//}else{ pl3->prior=NULL;//pl3指向空pl=pl3;//pl3与头pl3=pl;//}}else{pl3->state=0;}}elseif(pl3->next&&pl3->prior&&pl3->next->state==0&&pl3->prior->state==0) {pl3->size=pl3->size+pl3->next->size+pl3->prior->size;pl3->state=0;pl3->ID=0;pl3->start=pl3->prior->start;if(pl3->next->next)pl3->next->next->prior=pl3;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->next=pl3->next->next;//指向空pl3->prior=pl3->prior->prior;}else{pl3->next=pl3->next->next;//指向空pl3->prior=pl3->prior->prior;//指向头pl=pl3;pl3=pl;}}}pl3=pl3->next;}}//--------------------------------------------------------------------------------------//----------------------------------首次适应算法---------------------------------------void Firstfit(DuLinkList block_first,int n){int t=1;int num=n;while(t&&num){DuLinkList pl1=block_first,pl2,pl3=block_first;printf("时钟:%d\n",t);DuLNode *p=block_first;DuLNode *q=block_first;for(int x=0;x<n;x++){ if(t==a[x].ctime+a[x].rtime)a[x].state=2;}for(int m=0;m<n;m++){if(t==a[m].ctime+a[m].rtime){num-=1;a[m].state=2;//0 等待1 装入2结束while(q){if(q->ID==a[m].num)//分区号等于作业号时{q->state=Free;//在作业完成时，作业号等于分区号时空闲}q=q->next;}showJob(n);showPartition(block_first);}}for( m=0;m<n;m++){if(a[m].ctime==t){a[m].state=1;printf("作业:%d开始运行,对其分配!",a[m].num);}}for( m=0;m<n;m++){if(t==a[m].ctime){while(pl1&&(pl1->state == 1||pl1->size<a[m].size)) pl1=pl1->next;if(pl1){pl2=(DuLinkList)malloc(sizeof(DuLNode));pl2->start=pl1->start+a[m].size;pl2->state=0;pl2->ID=0;pl2->size=pl1->size-a[m].size;if(pl2->size>5){pl1->size=a[m].size;pl1->state=1;pl1->ID=a[m].num;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=block_first;}else{pl1->state=1;pl1->ID=a[m].num;}showJob(n);showPartition(block_first);}else{cout<<"内存不足，等待释放"<<endl;for(int i=m;i<n;i++){a[i].ctime+=1;}p=block_first;huishou(p, block_first);}}}t+=1;}}//---------------------------------------------------------------//---------------------------显示作业----------------------------void showJob(int n){printf("\n\t\t\t作业表:\n");printf("\t--------------------------------------------------------------\n");printf("\t 作业号\t大小\t进入时间\t运行时间\t状态\n");printf("\t--------------------------------------------------------------\n");for(int m=0;m<n;m++){printf("\t %d\t %d\t%d\t %d\t",a[m].num,a[m].size,a[m].ctime,a[m].rtime);if(a[m].state == 0)printf(" 等待\n");if(a[m].state == 1)printf(" 装入\n");if(a[m].state == 2)printf(" 结束\n");}printf("\t--------------------------------------------------------------\n"); }//---------------------------------------------------------------------//-------------------- 循环首次适应算法------------------------ void Nextfit(DuLinkList block_first,int n){int t=1;int num=n;DuLinkList flag;flag=block_first;while(t&&num){DuLinkList pl1=block_first,pl2,pl3=block_first;printf("时钟:%d\n",t);DuLNode *p=block_first;DuLNode *q=block_first;for(int m=0;m<n;m++){if(t==a[m].ctime+a[m].rtime){num-=1;a[m].state=2;while(q){if(q->ID==a[m].num){q->state=Free;}q=q->next;}showJob(n);showPartition(block_first);}}for( m=0;m<n;m++){if(a[m].ctime==t){a[m].state=1;printf("作业:%d开始运行,对其分配!",a[m].num);}}for( m=0;m<n;m++){if(t==a[m].ctime){while(flag&&(flag->state == 1||flag->size<a[m].size)) flag=flag->next;pl1=flag;if(pl1){pl2=(DuLinkList)malloc(sizeof(DuLNode));pl2->start=pl1->start+a[m].size;pl2->state=0;pl2->ID=0;pl2->size=pl1->size-a[m].size;if(pl2->size>5){pl1->size=a[m].size;pl1->state=1;pl1->ID=a[m].num;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=block_first;}else{pl1->state=1;pl1->ID=a[m].num;}flag=pl2;showJob(n);showPartition(block_first);}else{cout<<"内存不足，等待释放"<<endl;for(int i=m;i<n;i++){a[i].ctime+=1;}p=block_first;huishou(p, block_first);flag=block_first;}}}t+=1;}}//-------------------------------------------------------------------------------------//----------------------------界面输入--------------------------------------------- void inputchoice(int &ch){cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~"<<endl;cout<<"1------>首次适应算法"<<endl;cout<<"2------>循环首次适应算法"<<endl;cout<<"3------>退出"<<endl;cout<<"4------>显示"<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~"<<endl;cout<<"请输入选择："<<endl;scanf("%d",&ch);}//--------------------------------------------------------------------------------------void main(){ DuLinkList p;int n,ch;ch = 0;f = 1;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~"<<endl;cout<<" 动态分区分配存储管理系统"<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~"<<endl;cout<<" 请输入作业信息："<<endl;Putin(n);while(f){inputchoice(ch);switch(ch){_ case 1:InitpartitionList(p);Firstfit(p,n);ch = 0;break;case 2:InitpartitionList(p);Nextfit(p, n);ch = 0;break;case 3:f = 0;break;case 4:v();break;}}}_。