一、目的和要求
1. 实验目的
用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。
2．实验要求
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。
（1）设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。
（2）或在程序运行过程，由用户指定申请与释放。
（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。
二、实验内容
编写并调试一个模拟的内存分配与回收程序，使用首次适应算法、循环首次适应算法对内存空间的分配与回收。
三、实验方法、步骤及结果测试
1. 源程序名：a.cpp
可执行程序名：a.exe
2. 原理分析
（1）编写该程序首先要给定一个一定空间大小的内存，即申请空闲区空间最大值，并且要定义空间的各分区的作业标号、分区起始地址、分区长度，单位为字节、分区表的状态位、前向指针、后向指针、已分配分区表、空闲分区等。
（2）通过定义空间分区后，还要定义空间分区链表并对其进行初始化，对空闲分区和已分配分区进行链表访问，对于空闲分区可以分配给新进来的进程使用，对于已分配的分区，则等进程执行结束后在回收空间，恢复空闲区。通过链表的访问实现整个空间分区的分配与回收。
3. 主要程序段及其解释：
1 #include2 #include 3 #include 4 #include 5 #define minisize 1 6 typedef struct freeTable 7 { 8 char proID[6]; 9 int startAddr; /*空闲区起始地址*/ 10 int length; /*空闲区长度，单位为字节*/ 11 int flag; /*空闲区表登记栏标志，用"0"表示空表项，用"1"表示未分配*/ 12 struct freeTable *next; 13 } 14 freeTabNode; /*空闲区表结点*/ 15 freeTabNode *freeTab; 16 void InitFreeTab() 17 { 18 freeTabNode *f,*temp; 19 f=(freeTabNode *)malloc(sizeof(freeTabNode)); 20 strcpy(f->proID,"OS"); 21 f->startAddr=0; 22 f->length=5;f->flag=0; 23 freeTab=f; 24 f=(freeTabNode *)malloc(sizeof(freeTabNode));; 25 strcpy(f->proID,"1"); 26 f->startAddr=5; 27 f->length=5;f->flag=0; 28 freeTab->next=f; 29 temp=f; 30 f=(freeTabNode *)malloc(sizeof(freeTabNode)); 31 strcpy(f->proID,"3"); 32 f->startAddr=10; 33 f->length=4;temp->flag=0; 34 temp->next=f; 35 temp=temp->next; 36 f=(freeTabNode *)malloc(sizeof(freeTabNode)); 37 f->startAddr=14; 38 f->length=12; 39 f->flag=1; 40 temp->next=f; 41 temp=temp->next; 42 f=(freeTabNode *)malloc(sizeof(freeTabNode)); 43 strcpy(f->proID,"2"); 44 f->startAddr=26; 45 f->length=6;f->flag=0; 46 temp->next=f;temp=temp->next; 47 f=(freeTabNode *)malloc(sizeof(freeTabNode)); 48 f->startAddr=32; 49 f->length=96; 50 f->flag=1; 51 f->next=NULL; 52 temp->next=f; 53 } 54 void allocate(char PName[],int PLength) 55 { 56 freeTabNode *f,*temp; f=freeTab; 57 while(f) /*寻找空间大于PLength的最小空闲区登记项k*/ 58 { 59 if(f->length>=PLength&&f->flag==1) break; 60 f=f->next; 61 } 62 if(!f)/*未找到可用空闲区，返回*/ 63 { 64 printf("无可用空闲区\n"); 65 return; 66 } /*找到可用空闲区，开始分配*/ 67 if(f->length-PLength<=minisize) 68 { /*空闲区大小与要求分配的空间差小于minisize大小，空闲区全部分配*/ 69 strcpy(f->proID,PName); 70 f->flag=0; /*修改成空表目状态*/ 71 } 72 else 73 { /*若空闲区大小与要求分配的空间差大于minisize大小，从中划出一部分分配*/ 74 f->length=f->length-PLength; 75 temp=(freeTabNode *)malloc(sizeof(freeTabNode)); 76 strcpy(temp->proID,PName); 77 temp->startAddr=f->startAddr+f->length; 78 temp->length=PLength; 79 temp->flag=0; 80 temp->next=NULL; 81 temp->next=f->next; 82 f->next=temp; 83 } 84 return; 85 }/*主存分配函数结束*/ 86 void reclaim(char PName[]) 87 { /*回收作业名为PName的作业所占主存空间*/ 88 freeTabNode *front,*rear,*temp; 89 temp=freeTab; /*寻找空闲表中对应登记项*/ 90 if(strcmp(PName,"OS")==0) 91 { 92 printf("ERROR!"); 93 return; 94 } 95 while((strcmp(temp->proID,PName)!=0||temp->flag==1)&&temp) 96 temp=temp->next; 97 if(!temp)/*在已分配表中找不到名字为PName的作业*/ 98 { 99 printf("找不到该作业\n"); return; 100 } /*寻找回收分区的空闲上下邻，上邻表目front，下邻表目rear*/ 101 rear=temp->next; 102 front=freeTab; 103 while(front) 104 { 105 if(front->next==temp) 106 break; 107 front=front->next; 108 }/*找到回收分区的上邻表目*/ 109 if(rear==NULL) 110 { 111 if(front->flag==1) 112 { 113 front->length+=temp->length; 114 front->next=NULL;115 free(temp); 116 } 117 else temp->flag=1; 118 } 119 else 120 {121 if(front->flag==1&&rear->flag==1) /* 上邻空闲区，下邻空闲区，三项合并*/ 122 { 123 front->length=front->length+rear->length+temp->length; 124 front->next=rear->next; free(temp); 125 free(rear); 126 } 127 else if(front->flag==1&&rear->flag==0)128 { /*上邻空闲区，下邻非空闲区，与上邻合并*/ 129 front->length+=temp->length; 130 front->next=rear; free(temp); 131 } 132 else if(front->flag==0&&rear->flag==1) /*上邻非空闲区，下邻为空闲区，与下邻合并*/ 133 { 134 temp->length+=rear->length; 135 temp->next=rear->next; 136 free(rear); 137 temp->flag=1; 138 } 139 else /*上下邻均为非空闲区，回收区域直接作修改*/ 140 temp->flag=1;141 } 142 } 143 main( ) 144 { 145 int a; 146 freeTabNode *freeNode; 147 char PName[6]; 148 int PLength; 149 InitFreeTab(); /*空闲分区表初始化：*/ 150 while(1) { 151 printf("**选择功能项**\n"); 152 printf("\t0--退出\n\t1--分配主存\n\t2--回收主存\n\t3--显示主存\n"); 153 printf("选择项(0~3) :"); 154 scanf("%d",&a); 155 switch(a) { 156 case 0: 157 exit(0); /*a=0程序结束*/ 158 case 1: /*a=1分配主存空间*/ 159 printf("要分配的作业名PName:"); 160 scanf("%s",PName); 161 printf("\n和作业所需内存大小PLength(>1K): "); 162 scanf("%d",&PLength); 163 allocate(PName,PLength);/*分配主存空间*/ 164 break; 165 case 2: /*a=2回收主存空间*/ 166 printf("输入要回收分区的作业名:"); 167 scanf("%s",PName); 168 reclaim(PName);/*回收主存空间*/ 169 break;170 case 3: /*a=3显示主存情况*/ 171 printf("--------------------------------------\n"); 172 printf("内存分区表:\n"); 173 printf("\t\t进程标识 起始地址 分区长度\t状态\n"); 174 freeNode=freeTab; /*打印空闲区表*/ 175 while(freeNode) 176 { 177 if(freeNode->flag==1) 178 printf("\t\t 空 \t%5d\t%6d\t\t 空 闲 \n",freeNode->startAddr,freeNode->length); 179 else 180 printf("\t\t%s\t%5d\t%6d\t\t 空 表 目 \n",freeNode->proID,freeNode->startAddr,freeNode->length); 181 freeNode=freeNode->next; 182 } 183 getchar(); 184 break; 185 default:printf("没有该选项\n"); 186 }/*case*/ 187 }/*while*/ 188 }/*main()*/
四、运行结果
五、实验总结
这个实验的原理是书本上的知识，老师也在课堂上讲过，觉得理解并不难,但是不知道怎么觉得实验并不简单