动态分区分配管理系统学院专业学号学生姓名指导教师姓名2014年3月14 日目录1程序设计的内容和相关的要求---------------------------------2 2程序总的功能说明--------------------------------------------3 3程序的模块的说明--------------------------------------------4 4程序设计的流程图--------------------------------------------5 5程序的操作说明及运行结果-----------------------------------7 6源程序-------------------------------------------------------11 7心得体会----------------------------------------------------271程序设计的内容和相关的要求：课程设计的目的：操作系统课程设计是计算机学院重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。

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

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

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

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

实现的任务：编写一个动态分区分配程序。

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

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

2程序总的功能说明：本程序可以从界面直接输入作业并进行动态的内存分配，也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。

首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。

只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

循环首次首次适应算法（Next-first）：在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划一块与要求大小相等的内存空间分配给作业。

内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。

并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。

3程各模块的功能说明：（1）界面显示函数：showInterface(PL p,Job job)；显示操作界面showJob(Job job)；显示作业链表；showPartitiion(PL pl)显示分区链表（2）执行练习的功能函数：copyJob(Job p)；作业链表复制函数函数InitpartitionList(PL &p)；链表初始化分区函数函数CreateJoblist(Job &job,int count)；创建作业链表函数InsertNode(Job p,Job &job)；按时间顺序创建链表函数InitpartitionList(PL &p)；初始化分区链表函数（3）文件函数openFile()；打开文件函数ReadFile()；读取文件函数RandomParameter()；随即参数读入文件函数main()///主函数4程序设计的流程图：总体设计流程图：首次适应算法：回收函数：五程序操作说明书及结果：在vc++6.0环境中运行本程序，先进行编译，然后再进行链接，在进行执行将会出现显示界面。

按照显示界面上显示的提示进行操作，就可以实现相应的功能：六源程序：#include<time.h>#include <conio.h>#include<stdio.h>#include<stdlib.h>#include <windows.h>#define MemorySize 100//为空闲分区分配的最大空间（按题目要求）int workload;//输入作业的数量；typedef struct jobList{int id; // 作业的nameint size; // 作业大小（需要的存储空间大小）int intime; //进入时间int runtime; //运行时间int state; //作业的状态（0表示等待，1表示执行，2表示结束并释放）struct jobList *next; // 作业链表指针} *Job;typedef struct partitionList{int id;int startAddress; //分区起始地址int size; //分区大小int state; //分区的状态struct partitionList *prior;struct partitionList *next; // 分区链表指针}*PL;FILE *fp;/************************打开文件***************************/void openFile(){if((fp=(fopen("D:\\作业文件.txt","w")))==NULL){printf("无法打开文件!\n");exit(0);}}/************************读取文件****************************/void ReadFile(){if((fp=(fopen("D:\\作业文件.txt","r")))==NULL){printf("无法打开文件!\n");exit(0);}}/************将随机产生进程的参数写入文件********************/void RandomParameter(){openFile();for(int i=0;i<workload;i++){fprintf(fp,"%d %d %d %d %d\n",i+1,rand()%80,rand()%20,rand()%10+1,0);}fclose(fp);}/**********************显示分区函数**********************/void showPartitiion(PL pl){printf("\t***************************************\n");printf("\t* StartAddr\tid\tsize state *\n");printf("\t***************************************\n");while(pl){printf("\t* %d\t\t%d\t%d\t%d *",pl->startAddress,pl->id,pl->size,pl->state);printf("\n");pl=pl->next;}printf("\t***************************************\n");Sleep(1000);if(kbhit()==1)system(“pause”);}/******************按进入时间顺序创建一个作业链表*********************/void InsertNode(Job p,Job &job) //将创建的新结点插入到链表中{Job q1,q2;q1=job;q2=job->next;int i=0;if(!q2){p->next=q2;q1->next=p;}while(q2!=NULL&&q2->intime<p->intime){q1=q2;q2=q2->next;i=1;}if(!q2&&i==1){p->next=q2;q1->next=p;}if(q2!=NULL&&p->intime<=q2->intime){p->next=q2;q1->next=p;}}Job CreateJoblist(Job &job,int count)//创建作业链表{job=(Job)malloc(sizeof(jobList));if(!job)exit(0);job->next=NULL;Job p;printf("id\tsize\tintime\truntime\n");for(int i=0;i<count;i++){p=(Job)malloc(sizeof(jobList));if(!p)exit(0);scanf("%d\t%d\t%d\t%d",&p->id,&p->size,&p->intime,&p->runtime);p->state=0;if(p->size>100){printf("作业过大不能为之分配内存，请重新输入的作业：\n");scanf("%d\t%d\t%d\t%d",&p->id,&p->size,&p->intime,&p->runtime);p->state=0;InsertNode(p,job);}elseInsertNode(p,job);}return job;}/******************从外部文件读入数据并进行作业初始化*****************/Job ReadInitJob(Job &job){ReadFile();job=(Job)malloc(sizeof(jobList));if(!job)exit(0);job->next=NULL;Job p;for(int i=0;i<workload;i++){p=(Job)malloc(sizeof(jobList));if(!p)exit(0);fscanf(fp,"%d %d %d %d %d",&p->id,&p->size,&p->intime,&p->runtime,&p->state);InsertNode(p,job);}return job;}/*********************初始化分区链表***********************/PL InitpartitionList(PL &p){p=(PL)malloc(sizeof(partitionList));if(!p)exit(0);p->size=MemorySize;printf("输入分区首地址:");scanf("%d",&p->startAddress);p->state=0;p->id=0;p->next=NULL;p->prior=NULL;return p;}/*************将一个作业链表复制到另一个链表***************/Job copyJob(Job p){Job q,L,s=p,r;L=(Job)malloc(sizeof(jobList));L->next=NULL;r=L;s=s->next;while(s){q=(Job)malloc(sizeof(jobList));q->id=s->id;q->state=0;q->intime=s->intime;q->runtime=s->runtime;q->size=s->size;r->next=q;q->next=NULL;r=q;s=s->next;}return L;}/*************将一个分区链表复制到另一个链表***************/PL copypartition(PL p){PL q,L,s=p,r;L=(PL)malloc(sizeof(partitionList));L->next=NULL;r=L;s=s->next;while(s){q=(PL)malloc(sizeof(partitionList));q->size=s->size;q->startAddress=s->startAddress;q->state=s->state;r->next=q;q->next=NULL;r=q;s=s->next;}return L;}/*********************作业链表*********************/void showJob(Job job){job=job->next;printf("\n将作业按进入时间排序表示:\n");printf("\t******************************************\n");printf("\t* id\tsize\tintime\truntime\tstate *\n");printf("\t******************************************\n");while(job){printf("\t* %d\t%d\t%d\t%d\t%d *",job->id,job->size,job->intime,job->runtime,job->state);printf("\n");job=job->next;}printf("\t******************************************\n");printf("\n");}/***********************回收内存*************************/void Recover(PL pl3,PL &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->startAddress=pl3->prior->startAddress;pl3->state=0;pl3->id=0;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;}else{pl3->prior=pl3->prior->prior;pl=pl3;pl3=pl;}}else if(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->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->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->startAddress=pl->startAddress;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;}else{ pl3->prior=NULL;pl=pl3;pl3=pl;}}else{pl3->state=0;}}else if(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->startAddress=pl3->prior->startAddress;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 CycleFirstFit(PL pl,Job job){int t=0;int n=workload;while(t+1&&n){PL pl1=pl,pl2;printf("时钟:%d\n",t);Job job1=job;job1=job1->next;Job j1=job;j1=j1->next;Job j2=job;j2=j2->next;Job j3=job;j3=j3->next;PL pl3=pl;while(j2){if(j2->intime+j2->runtime==t){printf("作业id:%d运行结束,释放内存!",j2->id);n=n-1;j2->state=2;showJob(job);showPartitiion(pl);}j2=j2->next;}while(j1){if(j1->intime==t){printf("作业id:%d开始运行,对其分配!",j1->id);j1->state=1;}j1=j1->next;}while(job1){if(t==job1->intime){while(pl1&&(pl1->size<job1->size||pl1->state==1)) pl1=pl1->next;if(pl1){pl2=(PL)malloc(sizeof(partitionList));pl2->startAddress=pl1->startAddress+job1->size;pl2->state=0;pl2->id=0;pl2->size=pl1->size-job1->size;if(pl2->size>5){pl1->size=job1->size;pl1->state=1;pl1->id=job1->id;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=pl;}else{pl1->state=1;pl1->id=job1->id;}showJob(job);showPartitiion(pl);}else{printf("内存不足,将作业:%d置于等待状态!等待内存释放在进行分配!\n",job1->id);Job j=job1;while(j){j->intime+=1;j->state=0;j=j->next;}Job jj=job;jj=jj->next;while(jj){if(jj->state==2){while(pl3){if(pl3->id=jj->id)pl3->state=0;pl3=pl3->next;}}jj=jj->next;}pl3=pl;Recover(pl3,pl);}}job1=job1->next;}t=t+1;Sleep(500);}PL p=pl;while(p){p->state=0;p=p->next;}showJob(job);showPartitiion(pl);printf("所有进程分配完毕!\n");}/**********************循环首次算法**********************/void FirstFit(PL pl,Job job){int t=0;int n=workload;while(t+1&&n){PL pl1=pl,pl2;printf("时钟:%d\n",t);Job job1=job;job1=job1->next;Job j1=job;j1=j1->next;Job j2=job;j2=j2->next;Job j3=job;j3=j3->next;PL pl3=pl;while(j2){if(j2->intime+j2->runtime==t){printf("作业id:%d运行结束,释放内存!\n",j2->id);n=n-1;j2->state=2;pl3=pl;while(pl3){if(pl3->id==j2->id)pl3->state=0;pl3=pl3->next;}showJob(job);showPartitiion(pl);//进程运行结束时进行内存回收}j2=j2->next;}while(j1){if(j1->intime==t){printf("作业id:%d开始运行,对其进行分配!",j1->id);j1->state=1;}j1=j1->next;}while(job1){if(t==job1->intime){while(pl1&&(pl1->size<job1->size||pl1->state==1)) pl1=pl1->next;if(pl1){pl2=(PL)malloc(sizeof(partitionList));pl2->startAddress=pl1->startAddress+job1->size;pl2->state=0;pl2->id=0;pl2->size=pl1->size-job1->size;if(pl2->size>=5)//碎片最大值设为 5{pl1->size=job1->size;pl1->state=1;pl1->id=job1->id;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=pl;}else{pl1->state=1;pl1->id=job1->id;}showJob(job);showPartitiion(pl);}else{printf("内存不足,将作业:%d置于等待状态!等待内存释放在进行分配!\n",job1->id);Job j=job1;while(j){j->intime+=1;j->state=0;j=j->next;}pl3=pl;Recover(pl3,pl);}}job1=job1->next;}t=t+1;Sleep(500);}PL p=pl;while(p){p->state=0;p=p->next;}showJob(job);showPartitiion(pl);printf("所有进程分配完毕!\n");}/************************界面显示*************************/ void showInterface(PL p,Job job){int a,con=0;Job j1,j2;while(1){printf("\t1.首次适应\n\n");printf("\t2.循环首次适应\n\n");printf("\t3.退出\n请选择:\n");if(con==0||con==1)scanf("%d",&a);switch(a){case 1:InitpartitionList(p);j1=copyJob(job);FirstFit(p,j1);break;case 2:InitpartitionList(p);j2=copyJob(job);CycleFirstFit( p,j2);break;case 3:exit(0);break;}printf("重新选用算法(输入1),退出本次作业操作(输入3)\n");scanf("%d",&con);if(con==1)con=1;if(con==2)con=0;if(con==3)break;}}void main()///主函数{PL p;Job job;int m,con=0;system("color 3A");while(1){ printf("1.从显示界面上输入作业:\n\n");printf("2.文件读入:\n\n");printf("3.退出:\n");if(con==0||con==1)scanf("%d",&m);switch(m){case 1:printf("输入作业数目:");scanf("%d",&workload);job=CreateJoblist(job,workload);showJob(job);showInterface(p,job);break;case 2:printf("输入作业数目:");scanf("%d",&workload);RandomParameter();job=ReadInitJob(job);showJob(job);showInterface(p,job);break;case 3:exit(0);break;}printf("返回操作界(输入1)，退出程序操作(输入3)\n");scanf("%d",&con);if(con==1)con=1;if(con==2)con=0;if(con==3)break;}}七．实验心得与体会：在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序。