操作系统实验二存储管理动态分区分配及回收算法

课程名称操作系统计算机科学与技术分院信1001—2班组学号实验者姓名实验日期2013年4月11日评分教师签名实验二存储管理动态分区分配及回收算法一、实验目的通过分区管理实验，了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，并懂得在操作系统的支持下建立自己的应用系统。二、实验要求本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并掌握分配算法的特点，提高编程技巧和对算法的理解和掌握。三、实验过程1．准备（一）主程序1、定义分区描述器node，包括3个元素：（1）adr——分区首地址（2）size——分区大小（3）next——指向下一个分区的指针2、定义3个指向node结构的指针变量：（1）head1——空闲区队列首指针（2）back1——指向释放区node结构的指针（3）assign——指向申请的内存分区node结构的指针3、定义1个整形变量：free——用户申请存储区的大小（由用户键入）（二）过程1、定义check过程，用于检查指定的释放块（由用户键入）的合法性2、定义assignment1过程，实现FirstFitAlgorithm3、定义assignment2过程，实现BestFitAlgorithm4、定义acceptment1过程，实现FirstFitAlgorithm的回收算法5、定义acceptment2过程，实现BestFitAlgorithm的回收算法6、定义print过程，打印空闲区队列（三）执行程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。（四）输出要求每执行一次，输出一次空闲区队列情况，内容包括：编号首址终址大小2.主要流程和源代码实验二源代码#includestdio.h#includestdlib.h#includestring.h#defineMAX_SIZE32767typedefstructnode{intid;intadr;intsize;structnode*next;}Node;Node*head1,*head2,*back1,*back2,*assign;intrequest;intcheck(intadd,intsiz,charc){Node*p,*head;intcheck=1;if(add0||siz0)check=0;/*地址和大小不能为负*/if(c=='f'||c=='F')head=head1;elsehead=head2;p=head-next;while((p!=NULL)&&check)if(((addp-adr)&&(add+sizp-adr))||((add=p-adr)&&(addp-adr+p-size)))check=0;elsep=p-next;if(check==0)printf(\t输入释放区地址或大小有错误！！！\n);returncheck;}voidinit(){Node*p;head1=(Node*)malloc(sizeof(Node));head2=(Node*)malloc(sizeof(Node));p=(Node*)malloc(sizeof(Node));head1-next=p;head2-next=p;p-size=MAX_SIZE;p-adr=0;p-next=NULL;p-id=0;}Node*assignment1(intnum,intreq){Node*before,*after,*ass;ass=(Node*)malloc(sizeof(Node));before=head1;after=head1-next;ass-id=num;ass-size=req;while(after-sizereq){before=before-next;after=after-next;}if(after==NULL){ass-adr=-1;}else{if(after-size==req){before-next=after-next;ass-adr=after-adr;}else{after-size-=req;ass-adr=after-adr;after-adr+=req;}}returnass;}voidacceptment1(intaddress,intsiz,intrd){Node*before,*after;intinsert=0;back1=(Node*)malloc(sizeof(Node));before=head1;after=head1-next;back1-adr=address;back1-size=siz;back1-id=rd;back1-next=NULL;while(!insert&&after){//将要被回收的分区插入空闲区（按首址大小从小到大插入）if((after==NULL)||((back1-adr=after-adr)&&(back1-adr=before-adr))){before-next=back1;back1-next=after;insert=1;}else{before=before-next;after=after-next;}}if(insert){if(back1-adr==before-adr+before-size){//和前边分区合并before-size+=back1-size;before-next=back1-next;free(back1);}elseif(after&&back1-adr+back1-size==after-adr){//和后边分区合并back1-size+=after-size;back1-next=after-next;back1-id=after-id;free(after);after=back1;}printf(\t首先分配算法回收内存成功！\n);}elseprintf(\t首先分配算法回收内存失败！\n);}Node*assignment2(intnum,intreq){Node*before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node));q=(Node*)malloc(sizeof(Node));before=head2;after=head2-next;ass-id=num;ass-size=req;while(after-sizereq){before=before-next;after=after-next;}if(after==NULL){ass-adr=-1;}else{if(after-size==req){before-next=after-next;ass-adr=after-adr;}else{q=after;before-next=after-next;ass-adr=q-adr;q-size-=req;q-adr+=req;before=head2;after=head2-next;if(after==NULL){before-next=q;q-next=NULL;}else{while((after-size)(q-size)){before=before-next;after=after-next;}before-next=q;q-next=after;}}}return(ass);}voidacceptment2(intaddress,intsiz,intrd){Node*before,*after;intinsert=0;back2=(Node*)malloc(sizeof(Node));before=head2;after=head2-next;back2-adr=address;back2-size=siz;back2-id=rd;back2-next=NULL;if(head2-next==NULL){//空闲队列为空head2-next=back2;head2-size=back2-size;}else{//空闲队列不为空while(after){if(back2-adr==after-adr+after-size){//和前边空闲分区合并before-next=after-next;after-size+=back2-size;back2=after;}else{before=before-next;after=after-next;}}before=head2;after=head2-next;while(after){if(after-adr==back2-adr+back2-size){//和后边空闲区合并before-next=after-next;back2-size+=after-size;}else{before=before-next;after=after-next;}}before=head2;after=head2-next;while(!insert){//将被回收的块插入到恰当的位置（按分区大小从小到大）if(after==NULL||((after-sizeback2-size)&&(before-sizeback2-size))){before-next=back2;back2-next=after;insert=1;break;}else{before=before-next;after=after-next;}}}if(insert)printf(\t最佳适应算法回收内存成功！\n);elseprintf(\t最佳适应算法回收内存失败！！\n);}voidprint(charchoice)//输出空闲区队列信息{Node*p;if(choice=='f'||choice=='F')p=head1-next;elsep=head2-next;if(p){printf(\n空闲区队列的情况为：\n);printf(\t编号\t首址\t终址\t大小\n);while(p){printf(\t%d\t%d\t%d\t%d\n,p-id,p-adr,p-adr+p-size-1,p-size);p=p-next;}}}voidmenu()//菜单及主要过程{charchose;intch,num,r,add,rd;while(1){system(cls);printf(选择最先适应算法请输入F，选择最佳适应算法请输入B，退出程序请输入E\n\n);printf(请输入你的选择:);scanf(%c,&chose);if(chose=='e'||chose=='E')exit(0);else{system(cls);while(1){if(chose=='f'||chose=='F')printf(最先适应算法(First-Fit)模拟:\n);if(chose=='b'||chose=='B')printf(最佳适应算法(Best-Fit)模拟:\n);printf(1.分配内存,2.回收内存,3.查看内存,4.返回\n\n);printf(请输入你的选择:);scanf(%d,&ch);fflush(stdin);switch(ch){case1:printf(输入申请的分区大小：);scanf(%d,&r);if(chose=='f'||chose=='F')assign=assignme