下载文档原格式
学号P7*******专业计算机科学与技术姓名实验日期2017/11/23教师署名成绩实验报告【实验名称】鉴于次序搜寻的动向分划分派算法( 二 )【实验目的】理解在连续分区动向的储存管理方式下，怎样实现储存空间的分派与回收。
采纳可变式分区管理，使用最正确适应算法实现主存空间的分配与回收。
采纳可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。
【实验原理】C++语言程序设计数据结构最正确适应算法最坏适应算法数据结构和符号说明1、bool ROM[N]; //定义主存信息，假如内存被占用，则标志为1，不然标记为 0，设置内存单元为10242、pcb num[20];//定义作业数组，最大支持20 个作业3、typedef struct Pcb //定义作业结构体，包含名称，开始时间，大小，能否履行状态{char name[10];int start;int size;int state=0;} pcb;主要函数：void find_free_rom()；//找寻安闲区void sort1()；//对安闲区进行排序从小到大void sort1()；//对安闲区进行排序从大到小void show()；//显示函数void insert_pcb1(pcb &a)；//最正确适应算法void insert_pcb2(pcb &a)；//最坏适应算法void init();//初始化函数算法流程图：最正确适应算法：开始安闲区登记安闲区表依据从小到大排序插入作业信息目前安闲区指针为第一块安闲区作业大小小于等于目前安闲区是插入目前作业改正安闲区登记，改正作业表持续插入是否输出相应信息否能否达大最后一个安闲区是否目前安闲区指针插入失败加一结束最坏适应算法：开始安闲区登记安闲区表依据从大到小排序插入作业信息目前安闲区指针为第一块安闲区作业大小小于等于目前安闲区是插入目前作业改正安闲区登记，改正作业表持续插入是否输出相应信息否能否达大最后一个安闲区是否目前安闲区指针加一插入失败结束#include<stdio.h>#include<string.h>#define N 1024bool ROM[N];int p=0;int count=0;int free_rom_counter=0;//安闲区数量typedef struct Pcb //进度结构体{char name[10];int start; intsize;//大小int state=0; //状态} pcb;pcb num[20];//进度数组typedef struct安闲区结构体Free_rom// {int num;int start;int end;int space;//安闲区大小} Free_room;Free_rom free_rom[100];//安闲区数组void show()//显示安闲区信息{printf("****************************************************************\n\n");printf(" 安闲区名 \t 开始地点 \t\t 大小 \t\t 结束地点 \t\t\n"); for (int i=1; i<= free_rom_counter; i++)printf("%d\t\t%d\t\t\t%d\t\t%d\t\t\n",free_rom[ i].num,free_rom[ i].s tart, free_rom[ i].space,free_rom[ i].end);printf("\n");printf("****************************************************************\n\n");}void find_free_rom()//找寻安闲区，更新安闲区数组{free_rom_counter=0;int i,j,p;for(i=0; i<N; i++)if(ROM[i]==0){p=i;for(j=i; j<N; j++){if(ROM[j]==0){i=j;continue;}if(ROM[j]==1)//找到就更新信息{free_rom_counter++;free_rom[ free_rom_counter].num= free_rom_counter;free_rom[ free_rom_counter].start=p;free_rom[ free_rom_counter].end=j-1;free_rom[ free_rom_counter].space=j-p;i=j+1;break;}}if(j==N&&ROM[j-1]==0)//对最后一个内存进行特别办理{free_rom_counter++;free_rom[ free_rom_counter].num= free_rom_counter;free_rom[ free_rom_counter].start=p;free_rom[ free_rom_counter].end=j-1;free_rom[ free_rom_counter].space=j-p;}}}void sort1()//最正确适应算法对安闲区从小到大排序{find_free_rom();Free_rom a;for(int i=1; i<free_rom_counter; i++)for(int j=1; j<free_rom_counter; j++)if( free_rom[j].space> free_rom[j+1].space){a=free_rom[j];free_rom[j]=free_rom[j+1];free_rom[j+1]=a;}}void sort2()//最坏适应算法对安闲区从大到小排序{find_free_rom();Free_rom a;for(int i=1; i<free_rom_counter; i++)for(int j=1; j<free_rom_counter; j++)if( free_rom[j].space< free_rom[j+1].space){a=free_rom[j];free_rom[j]=free_rom[j+1];free_rom[j+1]=a;}}void init()//初始化{for(int i=0; i<N; i++)ROM[i]=0;}void input(pcb输入&a)// {char name[10];printf("输入进度名 \n");scanf("%s",&);printf("输入进度大小 \n");scanf("%d",&a.size);}void insert_pcb1(pcb &a)//最正确适应算法插入进度{find_free_rom();sort1();int i,j,k;for(i=1; i<=free_rom_counter; i++)//判断插入if(a.size<= free_rom[i].space){for(j=free_rom[i].start;ROM[j]=1;a.state=1;a.start=free_rom[i].start;num[count++]=a;break;j<free_rom[i].start+a.size;j++) }if(i==free_rom_counter+1)// printf("可用空间不足插入失败!\n");}void insert_pcb2(pcb &a)//最坏适应算法插入find_free_rom();sort2();int i,j,k;for(i=1; i<=free_rom_counter; i++)if(a.size<= free_rom[i].space){{for(j=free_rom[i].start;j<free_rom[i].start+a.size;j++)//找寻ROM[j]=1;a.state=1;a.start=free_rom[i].start;num[count++]=a;break;}if(i==free_rom_counter+1)//插入失败printf("可用空间不足 !\n");}void Delete(pcb &a)//内存中开释进度{int i;for(i=a.start; i<a.start+a.size; i++)ROM[i]=0;// 更新内存信息，更新进度状态数组a.state=0;printf("删除成功 \n");find_free_rom();}int main()//主函数{init();find_free_rom();int choose1;int choose;char name[10];printf("1、最正确适应算法 \n");//主界面printf("2、最坏初次适应算法 \n");scanf("%d",&choose1);pcb a;do{printf("\n\n1、插入进度 \n");printf("2、删除进度 \n");printf("3、显示进度信息 \n");printf("4、显示空余内存信息\n");scanf("%d",&choose);if(choose==1)//选择{input(a);if(choose1==1)insert_pcb1(a);else insert_pcb2(a);}else if(choose==2){printf("输入删除进度的名字 \n");scanf("%s",&name);for(int i=0; i<count; i++)if( !strcmp(num[i].name,name))Delete(num[i]);}else if(choose==3){printf("****************************************************************\n\n");printf("进程名 \t\t开始地址\t\t大小\t\t结束地点\t\t\n");//输出内存信息for(int i=0; i<count; i++)if(num[i].state!=0)printf("%s\t\t%d\t\t\t%d\t\t%d\t\t\n",num[i].name,num[i].start,num[i] .size,num[i].size+num[i].start-1);printf("\n****************************************************************\n\n");}else if(choose=4){find_free_rom();show();}else break;}while(1);return 0;}截图：结构以下安闲区：此时插入一个进度G，大小为80H，应插入到第二块安闲区再插入一个大小为30 的进度 H，应插入到第三块中再插入一个小进度，大小为5，插入到第二块安闲区，查察进度信息和安闲区信息：最正确适应算法建立。
#include<stdio.h>#define getpch(type) (type*)malloc(sizeof(type))struct LNode{ int size;int start;int end;struct LNode *next;struct LNode *front;}*L; /*L为头指针*/typedef struct LNode LN;LN *find;int n;void InsertList(int size,int start){ // 在带头结点的单链线形表头结点后插入LN *p,*s,*t;p=L;t=p->next;s=getpch(LN); //生成新结点s->size=size;s->start=start;s->end=start + size ;s->next=t; //插入L中p->next=s;if(t) t->front=s;s->front=p;}//end of InsertListvoid PrintList() /*打印*/{LN *p; int i;p=L->next;printf("\n空闲区号长度起始位置终止位置\n");for(i=1;i<=n;i++){printf(" %3d\t %3d\t%3d\t %4d\n",i,p->size, p->start,p->end);p=p->next;}}void BFSortList() /*最佳适应算法的排序*/{LN *p,*s,*t;int min_size,i;int size,start,end;t=L->next;p=L->next;for(i=0;i<n;i++){s=p->next;min_size = p->size;while(s){if(min_size > s->size){min_size=s->size;t=s;}s=s->next;}size=t->size;start=t->start;end=t->end;t->size=p->size;t->start=p->start;t->end=p->end;p->size=size;p->start=start;p->end=end;t=p->next;p=p->next;}}// end of BF_SortListvoid SortList() /*首次和循环首次适应算法的排序*/ {LN *p,*s,*t;int min_start,i;int size,start,end;t=L->next;p=L->next;for(i=0;i<n;i++){s=p->next;min_start = p->start;while(s){if(min_start > s->start){min_start=s->start;t=s;}s=s->next;}size=t->size;start=t->start;end=t->end;t->size=p->size;t->start=p->start;t->end=p->end;p->size=size;p->start=start;p->end=end;t=p->next;p=p->next;}}// end of BF_SortListvoid GetFree() /*生成空闲分区链*/{int size,start,i;L=getpch(LN); /*生成一个表头结点*/ L->next=NULL;L->front=NULL;printf("请输入空闲区数:");scanf("%d",&n);for(i=1;i<=n;i++){printf("请输入第%2d空闲区的大小和始址:",i);scanf("%3d,%3d",&size,&start);InsertList(size,start);}printf("\n按任意键继续");//printf("\n空闲链表情况:\n");//PrintList();}// end of GetFreevoid Assign(int size) /*最佳适应算法和首次适应算法空闲分区的分配*/ {LN *p,*t;p=L->next;t=L;while(p){if(size > p->size){p=p->next;t=t->next;if(!p){printf("没有足够大的空闲区分配！分配不成功");}}else{p->size = p->size - size;p->start= p->start + size ;if(p->size==0){t->next = p->next ;p->next->front=t;n--;free(p);}printf("分配成功！\n");printf("分配后的空闲链表情况如下:\n");PrintList();break;}}}// end of FF_Assignint flag=-1;void NF_Assign(int size)/*循环首次适应算法的分配*/{LN *p,*t;int i=n;p=find->next;t=find;while(p){if(size > p->size){p=p->next;t=t->next;if(!p){printf("没有足够大的空闲区分配！分配不成功");}}else{p->size = p->size - size;p->start= p->start + size ;find=p;if(p->size==0){t->next = p->next;p->next->front=t;n--;free(p);}printf("分配成功！\n");flag=1;printf("分配后的空闲链表情况如下：\n");Print(L);break;}}if(flag==-1){ p=L->next;t=L;while(p!=find){if(size > p->size){p=p->next;t=t->next;if(!p){printf("没有足够大的空闲区分配！分配不成功");}else{p->size = p->size - size;p->start= p->start + size ;find=t;if(p->size==0){t->next = p->next ;p->next->front=t;n--;free(p);}printf("分配成功！\n");printf("分配后的空闲链表情况如下：");PrintList(L);break;}}}}// end of NF_Assignvoid Recover(int start, int end) /*回收*/{LN *p,*t;int size,flag=0;size=end-start;p=L->next;t=p->next;while(p){if(t && p->end==start && t->start==end)//回收区在两个空闲区中间{p->size = p->size + size + t->size;p->end = t->end;p->next=t->next;t->next->front=p;free(t);SortList(L);flag=1;break;}else if(p->end == start)//回收区在空闲区下方{flag=1;p->size = p->size + size;p->end = p->end + size ;SortList(L);break;}else if( p->start == end)//回收区在空闲区上方{p->size= p->size +size;p->start=start;SortList(L);flag=1;break;}p=p->next;if(p)t=p->next;}//回收区不与任何一个空闲区相邻if(flag==0){ InsertList(size,start); n++;}printf("回收后的空闲链表情况如下:");PrintList();printf("\n按任意键继续");}void main(){int start,end,size;int m;GetFree();getch();system("cls");/*清屏*/printf("请选择服务类型:\n");printf("\t1:首次适应算法\n");printf("\t2:循环首次适应算法\n");printf("\t3:最佳适应算法\n");printf("\t4:回收内存\n");printf("\t0:退出\n");printf("\t输入您要的选项:");scanf("%d",&m); if(m==2) find=L;while(m){switch(m){case 1: SortList(); printf("\n空闲链表情况:\n");PrintList();printf("请输入进程需要的空闲区大小:");scanf("%d",&size);Assign(size); printf("\n按任意键继续");break;case 2: SortList(); printf("\n空闲链表情况:\n");PrintList();printf("请输入进程需要的空闲区大小:");scanf("%d",&size);NF_Assign(size);printf("\n按任意键继续");break;case 3: BFSortList(); printf("\n空闲链表情况:\n");PrintList();printf("请输入进程需要的空闲区大小:");scanf("%d",&size);Assign(size);printf("\n按任意键继续");break;case 4: printf("请输入回收区的首地址和中止地址:");scanf("%3d,%3d",&start,&end);Recover(start,end);break;case 0: exit(0);default : printf("\n\t\t输入错误,请重新输入"); getch();}getch();system("cls");/*清屏*/printf("请选择服务类型:\n");printf("\t1:首次适应算法\n");printf("\t2:循环首次适应算法\n");printf("\t3:最佳适应算法\n");printf("\t4:回收内存\n");printf("\t0:退出\n");printf("\t输入您要的选项:");scanf("%d",&m);}}。
首次适应算法和最佳适应算法是动态存储分配解决方案研究的内容，所以本文对这两种算法的讨论是通过研究动态存储管理来进行的。
一、存储管理的基本问题：存储管理讨论的基本问题是：1)、系统如何应用户的“请求”执行内存分配动作？2)、系统如何对用户不再使用后“释放”的内存执行回收动作，以保证为新的“用户请求”提供内存分配？内存的分配可以以静态方式进行，内存空间被分割为固定大小的若干内存块，用户的请求到达只要找到一块空闲的内存块予以分配即可，很显然静态存储分配的好处主要是实现比较方便，效率高，程序执行中系统需要做的事情比较简单。
然而实际情况下提出“请求”的用户可能是进入系统的一个作业，也可能是程序执行过程中的一个动态变量。
“请求”需要获得的内存容量大小不一，这种做法造成了对程序大小的严格的限制，使某些问题不能够合理的解决，此外，也会造成内存空间的浪费。
动态存储管理就是确定如何满足一个个内存“请求”，如何更合理的使用有限的内存空间的一种内存分配解决方案，它以能够依据用户的请求依次进行内存空间的分配和回收，能够尽可能少的使用有限的空闲内存空间，最大限度的保证后续“请求”的可满足性为最终目的。
二、关于动态分配方案的分析：通常我们将已分配给用户是用的一段连续的内存空间称为“占用块”，将未分配给任何用户的一段连续的内存空间称为“可利用空间块”或者“空闲块”，我们在这里的描述将使用“占用块”和“空闲块”这两个概念。
整个内存区在没有任何用户进入和运行的情况下只有一个空闲块，即整个可供用户“请求”使用的用户内存区域。
随着不断的有用户请求进入系统，并依次获得系统为其分配的内存，使得整个内存区域逐渐被分割成两大部分：低地址区域包含若干占用块；高低址区域是空闲内存区域。
经过一段时间后，有的用户运行结束，它们所占用的内存区释放后转变为一个个空闲块，这就使整个内存区域呈现出占用块和空闲块交错相隔的状态。
而此时，如果再有新的用户“请求”到达，那么，系统如何为这个“请求”进行内存分配呢？在肯定动态存储管理的前提下，我们可以采取两种方案解决这个问题，一种解决方案是系统继续把高地址的空闲块分配给用户，而不理会低地址区域是否有结束执行的用户释放的内存块，直到剩余的高地址区域的空闲块不能满足新的用户“请求”，分配操作无法再进行下去时，才去回收结束执行的用户释放的内存块，并重新组织内存，进而完成内存分配。
题4、静态链接是在（ ）进行的；而动态链接是在（ ）或（ ）进行的，其中在（ ）进行链接，可使得内存利用率最高。
Ⅰ．编译某段程序时；Ⅱ．装入某段程序时；Ⅲ．调用某段程序时；Ⅳ．紧凑时（即内存紧缩）；Ⅴ．装入程序之前。
A）Ⅰ；Ⅱ；Ⅲ；ⅢB）Ⅲ；Ⅳ；Ⅴ；ⅣC）Ⅴ；Ⅱ；Ⅲ；ⅢD）Ⅰ；Ⅴ；Ⅲ；Ⅴ5、由连续分配方式发展为分页存储管理方式；再由分页系统发展为分段系统，进而又发展为段页式系统的主要动力是（ ）。
Ⅰ．提高内存利用率；Ⅱ．提高系统吞吐量；Ⅲ．满足编程需要；Ⅳ．既满足编程要求，又提高内存利用率。
A）ⅠB）ⅡC）ⅢD）Ⅳ6、在动态分区式内存管理中，倾向于优先使用低址部分空闲区的算法是（ ）；能使内存空间中空闲区分布得较均匀的算法是（ ）；每次分配时，把既能满足要求，又是最小的空闲区分配给进程的算法是（ ）。
Ⅰ．最佳适应算法；Ⅱ．最坏适应算法；Ⅲ．首次适应算法；Ⅳ．循环首次适应算法（即Next fit）。
A）Ⅲ；Ⅳ；ⅠB）Ⅳ；Ⅰ；ⅡC）Ⅲ；Ⅰ；ⅣD）Ⅳ；Ⅰ；Ⅱ7、在首次适应算法中，要求空闲分区按（ ）的顺序形成空闲分区链；在最佳适应算法中是按（ ）的顺序形成空闲分区链；最坏适应算法是按（ ）的顺序形成空闲链。
Ⅰ．空闲区起始地址递增；Ⅱ．空闲区起始地址递减；Ⅲ．空闲区大小递增；Ⅳ．空闲区大小递减。
A）Ⅰ；Ⅲ；Ⅱ B）Ⅰ；Ⅲ；ⅣC）Ⅲ；Ⅳ；ⅡD）Ⅲ；Ⅰ；Ⅱ8、对外存对换区的管理应以（ ）为主要目标，对外存文件区的管理应以（ ）为主要目标。
Ⅰ．提高系统吞吐量；Ⅱ．提高存储空间的利用率；Ⅲ．降低存储费用；Ⅳ．提高换入换出速度。
A）Ⅰ；ⅡB）Ⅲ；ⅣC）Ⅳ；ⅡD）Ⅰ；Ⅲ9、在页式存储管理中，其虚拟地址空间是（ ）的：在段式存储管理中，其虚拟地址空间是（ ）的；在段页式存储管理中，其虚拟地址空间是（ ）的。
Ⅰ．一维；Ⅱ．二维；Ⅲ．三维；Ⅳ．层次。
A）Ⅰ；Ⅱ；ⅡB）Ⅱ；Ⅲ；ⅣC）Ⅲ；Ⅳ；ⅠD）Ⅳ；Ⅰ；Ⅱ第 2 页共 8 页题18、在请求分页系统的页表增加了若干项，其中状态位供（）参考。
最佳适应算法最佳适应算法是从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。
找到：满足要求的自由分区分配排序：从小到大含义最佳适应算法（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。
为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
该算法保留大的空闲区，但造成许多小的空闲区。
应用问题Best fit算法等价于装箱问题，举例如下：装箱问题：有体积为V的箱子N个，体积为Vi的物品M个，求使得物品全部能够装入箱子，箱子数量的最小值。
假设 V=6 M=10，V1，V2，...,V10分别为：3 4 4 3 5 1 2 5 3 1。
计算过程如下：第一步按物品体积降序排序：5 5 4 4 3 3 3 2 1 1第二步：取未装箱的最大值5装入第一个箱子。
第三步：判断第一个箱子是否已满，不满且剩余空间为1，搜寻剩下体积小于等于1的物品填入箱子1，箱子1填满。
第四步：重复第二，第三步，直到所有物品装入箱子为止，得到箱子数量为6. 6即时本例N的最小值。
最坏适应算法特点：扫描整个空闲分区或链表优点：可使剩下的空闲分区不至于太小最坏适应算法(worst fit)最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。
该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
优点:可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利，同时该算法查找效率很高。
缺点:会使存储器中缺乏大的空闲分区。
首次适应算法首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。
为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。
c模拟内存分配算法（⾸次适应算法，最佳适应算法，最坏适应算法）#include<bits/stdc++.h>using namespace std;/*定义内存的⼤⼩为100*/#define MEMSIZE 100/*如果⼩于此值，将不再分割内存*/#define MINSIZE 2/*内存分区空间表结构*/typedef struct _MemoryInfomation{/*起始地址*/int start;/*⼤⼩*/int Size;/*状态 F:空闲(Free) U:占⽤(Used) E 结束(End)*/char status;} MEMINFO;/*内存空间信息表*/MEMINFO MemList[MEMSIZE];/*显⽰内存状态*/void Display(){int i,used=0;//记录可以使⽤的总空间量printf("\n---------------------------------------------------\n");printf("%5s%15s%15s%15s","Number","start","size","status");printf("\n---------------------------------------------------\n");for(i=0; i<MEMSIZE&&MemList[i].status!='e'; i++){if(MemList[i].status=='u'){used+=MemList[i].Size;}printf("%5d%15d%15d%15s\n",i,MemList[i].start,MemList[i].Size,MemList[i].status=='u'?"USED":"FREE");}printf("\n----------------------------------------------\n");printf("Totalsize:%-10d Used:%-10d Free:%-10d\n",MEMSIZE,used,MEMSIZE-used);}/*初始化所有变量*/void InitMemList(){int i;MEMINFO temp= {0,0,'e'};//初始化空间信息表for(i=0; i<MEMSIZE; i++){MemList[i]=temp;}//起始地址为0MemList[0].start=0;//空间初始为最⼤MemList[0].Size=MEMSIZE;//状态为空闲MemList[0].status='f';}/*最先适应算法*//*算法原理分析：将空闲的内存区按其在储存空间中的起始地址递增的顺序排列，为作业分配储存空间时，从空闲区链的始端开始查找，选择第⼀个满⾜要求的空闲区，⽽不管它究竟有多⼤优点:1.在释放内存分区的时候，如果有相邻的空⽩区就进⾏合并，使其成为⼀个较⼤的空⽩区2.此算法的实质是尽可能的利⽤储存器的低地址部分，在⾼地址部分则保留多的或较⼤的空⽩区，以后如果需要较⼤的空⽩区，就容易满⾜缺点：1.在低地址部分很快集中了许多⾮常⼩的空⽩区，因⽽在空⽩区分配时，搜索次数增加，影响⼯作效率。
首次适应算法代码首次适应算法是一种基于最少访问原则的页面置换算法，其核心思想是将最近最少使用（Least Recently Used，简称LRU）的页面替换出主存。
该算法在操作系统中广泛应用于虚拟内存的页面置换过程中，可以有效地提高系统的响应速度和效率。
```python# 首次适应算法def first_fit(processes, size):# 初始化分区列表partition = [0] * len(processes)# 查找首次适应的空闲分区for j in range(len(partition)):if partition[j] == 0:# 判断分区大小是否足够容纳该进程if processes[i] <= size[j]:partition[j] = processes[i]break# 如果没有空闲分区，返回Falseelse:return False# 如果所有进程都成功分配到分区，返回Truereturn True```在上述代码中，我们首先定义了一个名为 `first_fit` 的函数，该函数接受两个参数：进程列表 `processes` 和分区大小列表 `size`。
进程列表 `processes` 就是指所有要进行分配的进程，而分区大小列表 `size` 则是指主存中所有可用的分区大小。
接下来，我们使用一个长度为 `len(processes)` 的列表 `partition` 来记录每个进程最终分配到的分区。
列表中的每个元素都代表一个分区，如果该分区的值为0，说明该分区是空闲的。
然后，我们使用两个嵌套的 `for` 循环遍历进程列表和分区列表。
在内部 `for` 循环中，我们查找首次适应的空闲分区，并判断该分区是否足够容纳该进程。
如果找到了合适的分区，我们就将该进程分配到该分区，并跳出循环。
如果所有分区都被占用，我们就返回 `False` 表示分配失败。
在主体部分的外部，我们返回 `True` 表示所有进程都成功分配到分区。
动态分区分配算法仿真，循环首次适应算法、最佳适应算法、最坏适应算法#include<iostream>#include<iomanip>//在输入输出流中用到控制符#include<windows.h>//用到了SetConsoleTextAttribute函数#define minsize 2//事先规定的不再切割的剩余分区大小为2using namespace std;struct Node{int name;int start;int size;int state;Node *pre;Node *next;};typedef struct Dlinklist{Node *head;}Dlist;//===================Dlist pro,fre;int memory,name,size,fit;Node *temp=NULL;//temp是NestFit算法中的起始查寻指针//===================void initDlist(Dlist &L)//创建带有头结点的双向链表{L.head=new Node;L.head->next=L.head->pre=NULL;}void MemoryInit()//初始化两个链表{initDlist(pro); //process链表initDlist(fre); //free block链表Node *p=new Node;p->name=0;p->start=0;p->state=0;p->size=memory;p->next=NULL;//这里曾错写成p->pre..............p->pre=fre.head;//这里曾漏写fre.head->next=p;}int getLength(Dlist &L)//返回链表的长度，即元素的个数int m=0;Node *p=L.head->next;while(p!=NULL){m++;p=p->next;}return m;}void arrangeSmaller(Dlist &L)//冒泡排序，链表按size进行排序，从小到大{int length=getLength(L);for(int i=0; i<length-1; i++)//当链表中的元素个数>=2的时候才排序{Node *p=L.head->next;Node *q=p->next;inta,b,c,d;//===================================================================== =====for(int j=0; j<length-1-i; j++){if(p->size>q->size) //交换位置，如果前面的大于后面的，使小的上浮，如果两个相等，则还是原来在前的保持在前{a=p->size;p->size=q->size;q->size=a;b=p->name;p->name=q->name;q->name=b;c=p->start;p->start=q->start;q->start=c;d=p->state;//============================================================== ============p->state=q->state;q->state=d;}p=p->next;q=p->next;}}void arrangeBigger(Dlist &L)//链表按size进行排序，从大到小{int length=getLength(L);for(int i=0; i<length-1; i++){Node *p=L.head->next;Node *q=p->next;int a,b,c,d;for(int j=0; j<length-1-i; j++){if(p->size<q->size){a=p->size;p->size=q->size;q->size=a;b=p->name;p->name=q->name;q->name=b;c=p->start;p->start=q->start;q->start=c;d=p->state;//============================================================== ============p->state=q->state;q->state=d;}p=p->next;q=p->next;}}}void arrangeStart(Dlist &L)//链表按start递增排序{int length=getLength(L);for(int i=0; i<length-1; i++){Node *p=L.head->next;Node *q=p->next;int a,b,c,d;for(int j=0; j<length-1-i; j++){if(p->start>q->start){a=p->size;p->size=q->size;q->size=a;b=p->name;p->name=q->name;q->name=b;c=p->start;p->start=q->start;q->start=c;d=p->state;//============================================================== ============p->state=q->state;q->state=d;}p=p->next;q=p->next;}}}void DlistInsert(Dlist &L,Node e) //在头结点之后插入元素，即L.head->next指向e {Node *p=new Node;p->name=;p->size=e.size;p->start=e.start;p->state=e.state;if(L.head->next!=NULL)//这是个值得注意的地方，L.head->next==NULL，则没有指针L.head->next->pre，如果这里不加判断的话，会出错L.head->next->pre=p;p->next=L.head->next;p->pre=L.head;L.head->next=p;//双向链表，插入一个新的元素，如果元素不是插入在链尾，则一共要修改四次指针}void DlistDelete(Node *p,Node &e)//传递指针p，删除指针p指向的链表元素，用Node 型变量e记录该元素的相关数据{=p->name;e.start=p->start;e.size=p->size;e.state=p->state;p->pre->next=p->next;//这里曾写成=p->pre....if(p->next!=NULL)p->next->pre=p->pre;//这里曾写成p->next->pre=p，留意delete(p); //删除一个元素修改一次或两次指针}//=======================void Green(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_GREEN);}void Red(){ SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_RED);}void White(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FORE GROUND_GREEN|FOREGROUND_BLUE);}void Yellow(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_RED|FOREGROUND_GREEN);}//=======================void BestOrWorst(){arrangeStart(fre);//先按地址递增排序if(fit==1)arrangeSmaller(fre);//再按size递增排序，当两个空闲区的size一样时，由于先按地址递增排序了，所以还是地址低的在前。
最佳适应算法源程序代码#include <iostream.h>#include <iomanip.h>//全局变量float minsize=5;int count1=0;int count2=0;#define M 10 //假定系统允许的空闲区表最大为m #define N 10 //假定系统允许的最大作业数量为n//已分配表的定义struct{float address; //已分分区起始地址float length; //已分分区长度，单位为字节int flag; //已分配区表登记栏标志，"0"表示空栏目}used_table[N]; //已分配区表对象名//空闲区表的定义：struct{float address; //空闲区起始地址float length; //空闲区长度，单位为字节int flag; //空闲区表登记栏标志，用"0"表示空栏目，用"1"表示未分配}free_table[M]; //空闲区表对象名//函数声明void initialize(void);int distribute(int, float);int recycle(int);void show();//初始化两个表void initialize(void){int a;for(a=0; a<=N-1; a++)used_table[a].flag=0; //已分配表的表项全部置为空表项free_table[0].address=1000;free_table[0].length=1024;free_table[0].flag=1; //空闲区表的表项全部为未分配}//最优分配算法实现的动态分区int distribute(int process_name, float need_length){int i, k=-1; //k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i<=M-1) //循环找到最佳的空闲分区{if(free_table[i].flag==1 && need_length <=free_table[i].length){count++;if(count==1||free_table[i].length < free_table[k].length)k=i;}i=i+1;}if(k!=-1){if((free_table[k].length-need_length)<=minsize) //整个分配{free_table[k].flag=0;ads=free_table[k].address;len=free_table[k].length;}else{ //切割空闲区ads=free_table[k].address;len=need_length;free_table[k].address+=need_length;free_table[k].length-=need_length;}i=0;//循环寻找内存分配表中标志为空栏目的项while(used_table[i].flag!=0){i=i+1;}if(i<=N-1) //找到，在已分配区表中登记一个表项{used_table[i].address=ads;used_table[i].length=len;used_table[i].flag=process_name;count1++;}else //已分配区表长度不足{if(free_table[k].flag == 0) //将已做的整个分配撤销{free_table[k].flag=1;free_table[k].address=ads;free_table[k].length=len;}else //将已做的切割分配撤销{free_table[k].address=ads;free_table[k].length+=len;}cout<<"内存分配区已满，分配失败！\n";return 0;}}else{cout <<"无法为该作业找到合适分区！\n";return 0;}return process_name;}int recycle(int process_name){int y=0;float recycle_address, recycle_length;int i, j, k; //j栏是下邻空闲区，k栏是上栏空闲区int x;//在内存分配表中找到要回收的作业while(y<=N-1&&used_table[y].flag!=process_name) { y=y+1;}if(y<=N-1) //找到作业后，将该栏的标志置为'0'{recycle_address=used_table[y].address;recycle_length=used_table[y].length;used_table[y].flag=0;count2++;}else //未能找到作业，回收失败{cout<<"该作业不存在！\n";return 0;}j=k=-1;i=0;while(!(i>=M||(k!=-1&&j!=-1))) //修改空闲分区表{if(free_table[i].flag==1){if((free_table[i].address+free_table[i].length)==recycle_address)k=i; //判断是否有上邻接if((recycle_address+recycle_length)==free_table[i].address)j=i; //判断是否有下邻接}i=i+1;}//合并空闲区if(k!=-1) //回收区有上邻接{if(j!=-1){ //回收区也有下邻接，和上下邻接合并free_table[k].length+=free_table[j].length+recycle_length;free_table[j].flag=0; //将第j栏的标记置为'0' }else //不存在下邻接，和上邻接合并free_table[k].length+=recycle_length;}else if(j!=-1){ //只有下邻接，和下邻接合并free_table[j].length+=recycle_length;free_table[j].address=recycle_address;}else{ //上下邻接都没有x=0;while(free_table[x].flag!=0)x=x+1; //在空闲区表中查找一个状态为'0'的栏目if(x<=M-1){ //找到后，在空闲分区中登记回收的内存free_table[x].address=recycle_address;free_table[x].length=recycle_length;free_table[x].flag=1;}else{ //空闲表已满，执行回收失败used_table[y].flag=process_name;cout<<"空闲区已满，回收失败！\n";return 0;}}return process_name;}void show() //程序执行时输出模拟的内存分配回收表{cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++++++ 空闲区+++++++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";for(int i=0;i<=count2;i++)if(free_table[i].flag!=0)cout<<"初始地址："<<free_table[i].address<<" "<<"长度："<<free_table[i].length<<" "<<"状态："<<free_table[i].flag<<endl;cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++++++ 已分配区++++++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";for(int j=0;j<count1;j++)if(used_table[j].flag!=0)cout<<"初始地址："<<used_table[j].address<<" "<<"长度："<<used_table[j].length<<" "<<"作业名："<<used_table[j].flag<<endl;}void main() //主函数调用各功能函数对所有工作进行测试{int choice; //用来选择将要进行的操作int job_name;float need_memory;bool exitFlag=false;cout<<" 动态分区分配方式的模拟\n";cout<<"************************************\n";cout<<"请选择操作类型：\n";initialize(); //开创空闲区和已分配区两个表while(!exitFlag){cout<<"********************************************\n";cout<<"** 1: 分配内存2: 回收内存**\n";cout<<"** 3: 查看分配0: 退出**\n";cout<<"********************************************\n";cout<<"请输入您的操作：";cin>>choice;switch(choice){case 0:exitFlag=true; //退出操作break;case 1:cout<<"请输入作业号和所需内存：";cin>>job_name>>need_memory;if(job_name!=0&&need_memory!=0)distribute(job_name, need_memory); // 分配内存else if(job_name==0)cout<<"作业号不能为零!\n请重新选择操作：\n";else if(need_memory==0)cout<<"内存分配数不能为零!\n请重新选择操作：\n";break;case 2:int ID;cout<<"请输入您要释放的作业号：";cin>>ID;if(ID!=0)recycle(ID); //回收内存elsecout<<"作业名不能为零!\n请重新选择操作：\n";break;case 3:show();break;}}}Welcome To Download !!!欢迎您的下载，资料仅供参考！。
实验四操作系统-动态分区分配算法萨斯的发生的v设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。
假设内存中空闲分区个数为n,空闲分区大小分别为P l,…，P n,在动态分区分配过程中需要分配的进程个数为m （m<n）,它们需要的分区大小分别为S i,…，S m,分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。
程序要求如下：1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。
2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。
3）输入：空闲分区个数n,空闲分区大小P i,…,P n,进程个数m, 进程需要的分区大小S i,…，S m,算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。
4）输出：最终内存空闲分区的分配情况。
代码实现：#include<iostream>#include<fstream>#include<iomanip>using namespace std;const int MaxNumber=100;int FreePartition[MaxNumber];// 空闲分区大小int FirstPartition[MaxNumber];//1-首次适应算法int CycleFirstPartition[MaxNumber];//2-循环首次适应算法int BestPartition[MaxNumber];//3-最佳适应算法int WorstPartition[MaxNumber];//4-最坏适应算法int ProcessNeed[MaxNumber];// 进程需要的分区大小int PartitionNum,ProcessNum;char ProcessName[MaxNumber];// 进程名char ProcessPartition[MaxNumber];// 进程分配的序列int Partition[MaxNumber];char str[MaxNumber][MaxNumber];void FirstFit(int n,int m);void NextFit(int n,int m);void BestFit(int n,int m);void WorstFit(int n,int m);void Print(int n, int m);void Print2(int n, int m);//======================================================== void FirstFit(int n, int m){cout<<"选择了首次适应算法！"<<endl;cout<<endl;int i,j,k=0;for(i=0; i<n; i++){FirstPartition[i] = FreePartition[i];}for(j=0; j<m; j++){for(i=0; i<n; i++){if(ProcessNeed[j]<=FirstPartition[i]){ProcessPartition[j]=i;//str[i][k] = ProcessName[j];FirstPartition[i] = FirstPartition[i]-ProcessNeed[j]; break;}}}Print(n,m);cout<<"空间序号:"<<" ";for(i=0; i<n; i++)(cout<<T<<setw(m-1)<<"空间”<<(i+1);}cout<<endl;cout<<"分区大小:"<<" ";for(i=0; i<n; i++)(cout<<T<<setw(m)<<setiosflags(ios::left)<<FreePartition[i];}cout<<endl;cout<<"剩余分区大小:";for(i=0; i<n; i++)(cout<<"|"<<setw(m)<<setiosflags(ios::left)<<FirstPartition[i];}cout<<endl;Print2(n,m);}void NextFit(int n, int m)(cout<<"选择了循环首次适应算法!"<<endl;cout<<endl;int i,j,flag=0;for(i=0; i<n; i++)(CycleFirstPartition[i] = FreePartition[i];}for(j=0; j<m; j++)(for(i=flag; i<n; i++)(if(ProcessNeed[j]<=CycleFirstPartition[i])(ProcessPartition[j]=i;CycleFirstPartition[i] = CycleFirstPartition[i]-ProcessNeed[j];flag = i+1;if(i==n-1)(flag=O;)break;)))Print(n,m);cout«"空间序号:for(i=0; i<n; i++){cout«"|"«setw(m-1)«"空间"«(i+1);)cout«endl;cout«"分区大小："vv"for(i=0; i<n; i++){cout«"|"«setw(m)«setiosflags(ios::left)«FreePartition[i];)cout«endl;cout«"剩余分区大小:";for(i=0; i<n; i++){cout«"|"«setw(m)«setiosflags(ios::left)«CycleFirstPartition[i];)cout«endl;Print2(n,m);)void BestFit(int n, int m){cout«"选择了最佳适应算法!"«endl;cout«endl;int i j,flag=O,temp,id=O,flag1 =0;for(i=0; i<n; i++){BestPartition[i] = FreePartition[i];)while(flag1<m){flag = 0;for(i=0; i<n; i++)Partition[i]=0;}for(i=0; i<n; i++)(if(ProcessNeed[flag1]<=BestPartition[i])(Partition[flag]=i;flag += 1;}}temp = BestPartition[Partition[0]];id = Partition]。
第三章 内存管理内存管理内存的基础知识什么是内存？有何作用？内存可存放数据程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾内存中也有一个一个的“小房间”，每个小房间就是一个“存储单元”如果计算机“按字节编址”则每个存储单元大小为1字节，即1B，即8个二进制位如果字长为16位的计算机“按字编址”，则每个存储单元大小为1个字；每个字的大小为16个二进制位内存从0开始，每个地址对应一个存储单元进程运行的基本原理指令的工作原理操作码+若干参数〔可能包含地址参数）可见，我们写的代码要翻译成CPU能识别的指令。
这些指令会告诉cPU应该去内存的哪个地址读/写数据，这个数据应该做什么样的处理。
在这个例子中，我们默认让这个进程的相关内容从地址#0开始连续存放，指令中的地址参数直接给出了变量x的实际存放地址（物理地址）逻辑地址（相对地址）vs物理地址（绝对地址）程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址)，即相对于进程的起始地址而言的地址三种装入方式绝对装入编译时产生绝对地址在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。
装入程序按照装入模块中的地址，将程序和数据装入内存。
绝对装入只适用于单道程序环境可重定位装入（静态重定位）装入时将逻辑地址转换为物理地址编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。
可根据内存的当前情况，将装入模块装入到内存的适当位置。
装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）特点在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。
作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间动态运行时装入（动态重定位）运行时将逻辑地址转换为物理地址，需设置重定位寄存器编译、链接后的装入模块的地址都是从0开始的。
首次适应算法
首次适应算法（First Fit Algorithm）是一种计算机算法，用于实
现内存动态分配，它允许程序的内存占用量在不同的时间段发生变化。
首
次适应算法的基本思想是查找可以满足内存请求的第一个可用块并分配给它。
它是按照顺序搜索可用分区，从最初开始搜索，找出第一个分区可以
容纳所需空间，并将其分配给请求进程；如果不能找到足够大的可用分区，则失败。
这种算法可以有效地利用内存，但它可能会产生多个空闲块，占
用更多的空间，并造成内存碎片化问题。
因此，首次适应算法的一个缺点
是可能会引起内存碎片化，增加空间开销。
一、选择题1．当cpu执行操作系统代码时，称处理机处于（ B ）A.执行态B.管态C.目态D.就绪态2．以下关于操作系统的说法不正确的是（ D）A. 操作系统是在硬件基础上的第一层软件B. 操作系统是计算机系统资源的管理者C. 操作系统的核心是常驻内存的。
D. 随着第一台电子计算机的诞生操作系统也出现了。
3．操作系统的两个最基本特征是（ A ）A.并发和共享B.并发和异步C.虚拟和共享D.虚拟和异步4．下列各项工作步骤中，哪个不是创建进程所必需的步骤（ B）A. 建立一个PCB B. 由CPU调度程序为进程调度CPUC. 为进程分配内存等必要资源D.将PCB连接入进程就绪队列5.临界区是（ D）A. 一个缓冲区B.一段共享数据区C.一个互斥资源D.一段程序6．在UNIX系统中，用户是通过什么读取磁盘文件中的数据的？（B ）A.作业申请表 B.系统调用 C.原语 D.中断7．以下关于锁机制的不正确说法是（ A ）A. 锁机制既能用于互斥，也能用于同步B. 锁机制中锁变量X=0,表示资源可用；X=1表示资源正在使用C. 关锁原语要反复测试X的状态D.开锁原语unlock（x）：x：=0；8.关于死锁的结论正确的是（C）A. 参与死锁的进程最多是两个第 1 页共12 页B.一旦出现死锁, 系统中所有进程都不能运行C.参与死锁的所有进程都占有资源.D. 参与死锁的所有进程都在等待资源9. 能够使CPU从I/O事务中完全解脱出来的数据传送控制方式是（D）A.程序直接控制B.中断控制C.DMA控制D.通道控制10．中断优先级从高到低排列正确的是（A ）A.机器故障—访管中断—外部中断B.程序性中断—I/O中断—访管中断C.访管中断—I/O中断—外部中断D.I/O中断—机器故障中断—程序性中断二、名词解释题1. 中断: 中断是现代计算机系统中基本设施之一,它起着通讯联络作用,协调系统对各种外部事件的响应和处理.中断是实现多道程序的必要条件.2. 通道: 通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入，输出操作可与CPU并行操作3. 快表: 介于内存与寄存器之间的存储机制4. 原语: 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。
内存1通常情况下,在下列存储管理方式中，（)支持多道程序设计、管理最简单，但存储碎片多；( )使内存碎片尽可能少，而且使内存利用率最高。
Ⅰ．段式;Ⅱ.页式；Ⅲ．段页式；Ⅳ．固定分区；Ⅴ.可变分区ﻩ正确答案：Ⅳ；Ⅰ２为使虚存系统有效地发挥其预期的作用,所运行的程序应具有的特性是( ）。
正确答案：该程序应具有较好的局部性（Ｌocaｌity) ﻭ3提高内存利用率主要是通过内存分配功能实现的，内存分配的基本任务是为每道程序(）。
使每道程序能在不受干扰的环境下运行，主要是通过( ）功能实现的。
Ⅰ.分配内存;Ⅱ．内存保护;Ⅲ.地址映射;Ⅳ.对换;Ⅴ.内存扩充;Ⅵ.逻辑地址到物理地址的变换；Ⅶ.内存到外存间交换;Ⅷ.允许用户程序的地址空间大于内存空间。
正确答案: Ⅰ;Ⅱﻭ4适合多道程序运行的存储管理中,存储保护是ﻩ正确答案:为了防止各道作业相互干扰ﻭ5下面哪种内存管理方法有利于程序的动态链接( )？正确答案：分段存储管理6在请求分页系统的页表增加了若干项，其中状态位供（）参考。
ﻩ正确答案：程序访问7从下面关于请求分段存储管理的叙述中,选出一条正确的叙述（)。
ﻩﻩ正确答案：分段的尺寸受内存空间的限制,但作业总的尺寸不受内存空间的限制ﻩ8虚拟存储器的特征是基于（）。
ﻩ正确答案：局部性原理ﻩﻭ９实现虚拟存储器最关键的技术是(）。
ﻩ正确答案：请求调页（段）ﻩ10“抖动”现象的发生是由（)引起的。
ﻩ正确答案：置换算法选择不当11在请求分页系统的页表增加了若干项，其中修改位供( ）参考。
ﻩﻩﻩ正确答案: 换出页面ﻩ12 虚拟存储器是ﻩ正确答案：程序访问比内存更大的地址空间１3测得某个请求调页的计算机系统部分状态数据为:CPＵ利用率20％,用于对换空间的硬盘的利用率９7.７%,其他设备的利用率5％。
由此断定系统出现异常。
此种情况下（)能提高CPU的利用率。
ﻩ正确答案：减少运行的进程数14在请求调页系统中，若逻辑地址中的页号超过页表控制寄存器中的页表长度，则会引起（）。
【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）（编码⽔平较菜，写博客也只是为了个⼈知识的总结和督促⾃⼰学习，如果有错误，希望可以指出）今天测试，发现⼀点问题：1.最佳插⼊算法：对于插⼊的时候忘记修改temp.next.front的指向2.回收头节点的时候现在多了⼀种判断。
判断头节点的下⼀个是否为空。
对如果不为空⽽且后⾯的空闲的话，做出了处理。
原来则没有这⼀情况。
1.动态分区分配算法：为了实现动态分区分配，通常将系统中的空闲分区链接成⼀个链。
所谓顺序查找是指依次搜索空闲分区链上的空闲分区，去寻找⼀个⼤⼩能满⾜要求的分区。
--------计算机操作系统（第四版）2.动态分区算法主要包括四种：（1）.⾸次适应算法（first fit，FF）：要求，空闲分区链以地址递增的顺序链接。
每次从链⾸开始，直到找到第⼀个能满⾜要求的空闲分区为⽌。
简单来说，就是，每次都从第⼀个开始顺序查找，找到⼀块区域可以满⾜要求的。
优点：优先利⽤内存中低址部分的空闲分区，从⽽保留了⾼址部分的⼤空闲区，这为以后到达的⼤作业分配⼤的内存空间创造了条件。
缺点：低址部分不断被划分，会留下许多难以利⽤的，很⼩的空闲分区，称为碎⽚。
⽽每次查找⼜都是从低址部分开始的，这⽆疑⼜会增加查找可⽤空闲分区时的开销。
（2）.循环⾸次适应算法（next fit，NF）：与FF算法区别就是，不是每次都从⾸次开始，⽽是从上次找到的空闲分区的下⼀个空闲分区开始。
（第⼀次查找的话也是从⾸页开始）。
特点：能使内存中的空闲区分布得较均匀。
(3）.最佳适应算法（best，BF）：将所有空闲分区按照空闲分区容量⼤⼩从⼩到⼤的顺序连接起来，形成⼀个空闲分区链。
即，每次都是找空间容量不但可以满⾜要求的空闲区，⽽且该空闲分区的容量还要最接近要求的容量⼤⼩。
优点：每次分配给⽂件的都是最合适该⽂件⼤⼩的分区。
首次适应算法,最佳适应算法,最坏适应算法源代码[宝典] 首次适应算法,最佳适应算法,最坏适应算法源代码#include<iostream.h> #include<stdlib.h>#define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成#define ERROR 0 //出错#define MAX_length 640 //最大内存空间为640KBtypedef int Status;int flag;typedef struct freearea//定义一个空闲区说明表结构{long size; //分区大小long address; //分区地址int state; //状态 }ElemType;// 线性表的双向链表存储结构 typedef struct DuLNode {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);//首次适应算法Status Best_fit(int); //最佳适应算法 Status Worst_fit(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.state=Free;return OK;}//分配主存Status alloc(int ch){int request = 0;cout<<"请输入需要分配的主存大小(单位:KB):"; cin>>request;if(request<0 ||request==0){cout<<"分配大小不合适，请重试～"<<endl;return ERROR;}if(ch==2) //选择最佳适应算法{if(Best_fit(request)==OK) cout<<"分配成功～"<<endl; else cout<<"内存不足，分配失败～"<<endl;return OK;}if(ch==3) //选择最差适应算法{if(Worst_fit(request)==OK) cout<<"分配成功～"<<endl; else cout<<"内存不足，分配失败～"<<endl;return OK;}else //默认首次适应算法{if(First_fit(request)==OK) cout<<"分配成功～"<<endl; else cout<<"内存不足，分配失败～"<<endl;return OK;}}//首次适应算法Status First_fit(int request){//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); 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;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 request){int ch; //记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); 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) ) {if(q==NULL){q=p;ch=p->data.size-request;}else if(q->data.size > p->data.size){q=p;ch=p->data.size-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.size==request){q->data.state=Busy;return OK;}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;}return OK;}//最差适应算法Status Worst_fit(int request){int ch; //记录最大剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.size=request;temp->data.state=Busy;LNode *p=block_first->next; DuDuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最大空间和最佳位置{if(p->data.state==Free && (p->data.size>=request) ) {if(q==NULL){q=p;ch=p->data.size-request;}else if(q->data.size < p->data.size){q=p;ch=p->data.size-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.size==request){q->data.state=Busy;return OK;}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;}return OK;}//主存回收Status free(int flag){DuLNode *p=block_first;for(int i= 0; i <= flag; i++)if(p!=NULL)p=p->next;elsereturn ERROR;p->data.state=Free;if(p->prior!=block_first &&p->prior->data.state==Free)//与前面的空闲块相连{p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;p=p->prior;}if(p->next!=block_last && p->next->data.state==Free)// 与后面的空闲块相连{p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;}if(p->next==block_last && p->next->data.state==Free)//与最后的空闲块相连{p->data.size+=p->next->data.size;p->next=NULL;}return OK;}//显示主存分配情况void show(){int flag = 0;cout<<"\n主存分配情况:\n";cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n";DuLNode *p=block_first->next;cout<<"分区号\t起始地址\t分区大小\t状态\n\n";while(p){cout<<" "<<flag++<<"\t";cout<<" "<<p->data.address<<"\t\t";cout<<" "<<p->data.size<<"KB\t\t";if(p->data.state==Free) cout<<"空闲\n\n";else cout<<"已分配\n\n";p=p->next;}cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n"; }//主函数void main(){int ch;//算法选择标记cout<<"请输入所使用的内存分配算法:\n";cout<<"(1)首次适应算法\n(2)最佳适应算法\n(3)最差适应算法\n"; cin>>ch;while(ch<1||ch>3){cout<<"输入错误，请重新输入所使用的内存分配算法:\n";cin>>ch;}Initblock(); //开创空间表int choice; //操作选择标记while(1){show();cout<<"请输入您的操作:";cout<<"\n1: 分配内存\n2: 回收内存\n0: 退出\n";cin>>choice;if(choice==1) alloc(ch); // 分配内存else if(choice==2) // 内存回收{int flag;cout<<"请输入您要释放的分区号:"; cin>>flag;free(flag);}else if(choice==0) break; //退出else //输入操作有误{cout<<"输入有误，请重试～"<<endl; continue;}}}。
