【免费下载】 循环首次适应算法、首次适应算法、最佳适应算法 C语言版

#include<stdio.h>#include<stdlib.h>#define N 3typedef struct table //分区表{int num ; //分区号int size ;//空闲去的大小int firstadd; //起始地址struct table *next;} spare;typedef struct input{char name[10];int size;}job;//读取进程int scanfb(job Job[N]){int m,i;FILE *rf;rf=fopen("course.txt","r");fscanf(rf,"%d",&m);for(i=0;i<m;i++)fscanf(rf,"%s%d",&Job[i].name,&Job[i].size);fclose(rf);//for(i=0;i<m;i++)//printf("\t%s\t%d\t",Job[i].name,Job[i].size);return m;}//按照空闲区的大小排序void sort(spare *Q){spare *p,*q,*r,*t;p=Q;q=Q->next;//printf(" \t%d\t%d\t%d \n",q->num,q->size,q->firstadd);r=Q->next->next;q->next=NULL;//printf(" \t%d\t%d\t%d \n",r->num,r->size,r->firstadd);while(r!=NULL){p=Q;q=Q->next;while(q!=NULL&&r->size>q->size){p=q;q=q->next;}t=r;r=r->next;t->next=NULL;t->next=q;p->next=t;}}//输出链表void print(spare *Q){int i=1;spare *q,*p;q=Q->next;while(q!=NULL){printf(" \t第%d行\t%d\t%d\t%d \n",i++,q->num,q->size,q->firstadd);q=q->next;}printf("\n");}//最佳适应算法void bestfit(spare *Q,job Job[N]){int i=0;spare *q,*p;do{p=Q;q=Q->next;while(q!=NULL&&q->size<Job[i].size){p=q;q=q->next;}if(p==NULL)printf("\n内存不足,%dK大小的作业需要等待内存资源!\n",Job[i].size);if(q!=NULL){q->size=q->size-Job[i].size;q->firstadd=q->firstadd+Job[i].size;if(q->size==0){p->next=q->next;free(q);}}i++;sort(Q);}while(q!=NULL);}void main(){job Job[N];spare *Q,*p,*q,*r,*m;int i,n;FILE *rf;rf = fopen("input.txt", "r") ; /*只读打开文件*/fscanf(rf,"%d",&n); /*读入个数*/Q=(spare *)malloc(sizeof(spare));Q->next=NULL;p=Q;q=(spare *)malloc(sizeof(spare));fscanf(rf,"%d%d%d",&(q->num),&(q->size),&(q->firstadd));q->next=NULL;p->next=q;//printf(" %d %d %d \n",q->num,q->size,q->firstadd);for(i=1;i<n;i++){r=Q->next;m=Q;p=q;q=(spare *)malloc(sizeof(spare));fscanf(rf,"%d%d%d",&(q->num),&(q->size),&(q->firstadd));//printf(" %d %d %d \n",q->num,q->size,q->firstadd);q->next=NULL;while(r!=NULL&&r->size<q->size){m=r;r=r->next;//printf(" %d %d %d \n",q->num,q->size,q->firstadd);}q->next=r;m->next=q;//printf(" %d %d %d \n",q->num,q->size,q->firstadd);}print(Q);scanfb(Job);//sort(Q);bestfit(Q,Job);printf("\n----最佳适应算法分区分配后的空闲区----\n");print(Q);}。

首次适应分配算法首次适应分配算法是一种常用的内存分配算法，它被广泛应用于操作系统和计算机体系结构中。

本文将详细介绍首次适应分配算法的原理、具体步骤以及优缺点。

首次适应分配算法的原理是将系统中的可用内存划分为不同大小的分区，每个分区表示一块可用内存。

当有新的作业需要分配内存时，首次适应分配算法会从分区链表中找到第一个满足需求大小的分区，然后将其分配给该作业。

具体步骤如下：1.初始化：将整个内存分区初始化为一个空闲的分区链表，即所有可用内存都是一个大的空闲分区。

2.作业请求分配：当有新的作业请求内存时，首次适应分配算法会遍历分区链表，找到第一个满足作业内存需求的分区。

3.分配内存：如果找到了合适的分区，首次适应分配算法会将该分区划分为两个部分，一个部分用于分配给作业，另一个部分作为剩余的空闲分区。

4.更新分区链表：当分配完成后，首次适应分配算法会更新分区链表，将已分配的分区从链表中删除，同时将剩余的空闲分区加入到链表中。

5.释放内存：当作业运行结束，需要释放内存时，首次适应分配算法会将该分区标记为未分配，并将其与相邻的空闲分区合并。

首次适应分配算法的优点包括：1.实现较为简单：首次适应分配算法是一种比较简单的内存分配算法，容易理解和实现。

2.分配速度较快：由于首次适应分配算法从分区链表的头部开始查找合适的分区，因此可以很快地找到第一个满足需求的分区。

3.内存利用率较高：首次适应分配算法在分配内存时会选择较小的空闲分区来满足作业的需求，从而可以更充分地利用内存空间。

首次适应分配算法也存在一些缺点：1.外部碎片：由于首次适应分配算法分配的是第一个满足需求的分区，可能会导致一些较大的空闲分区无法利用，从而产生外部碎片。

2.分区搜索时间开销：由于首次适应分配算法是线性搜索分区链表，当分区链表较长时，搜索的时间开销较大。

综上所述，首次适应分配算法是一种简单且高效的内存分配算法。

它能够快速找到第一个满足需求的分区，并充分利用内存空间。

操作系统习题答案GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8-内存1通常情况下，在下列存储管理方式中，（）支持多道程序设计、管理最简单，但存储碎片多；（）使内存碎片尽可能少，而且使内存利用率最高。

Ⅰ．段式；Ⅱ．页式；Ⅲ．段页式；Ⅳ．固定分区；Ⅴ．可变分区正确答案：Ⅳ；Ⅰ2为使虚存系统有效地发挥其预期的作用，所运行的程序应具有的特性是（）。

正确答案：该程序应具有较好的局部性(Locality)3提高内存利用率主要是通过内存分配功能实现的，内存分配的基本任务是为每道程序（）。

使每道程序能在不受干扰的环境下运行，主要是通过（）功能实现的。

Ⅰ．分配内存；Ⅱ．内存保护；Ⅲ．地址映射；Ⅳ．对换；Ⅴ．内存扩充；Ⅵ．逻辑地址到物理地址的变换；Ⅶ．内存到外存间交换；Ⅷ．允许用户程序的地址空间大于内存空间。

正确答案：Ⅰ；Ⅱ4适合多道程序运行的存储管理中，存储保护是正确答案：为了防止各道作业相互干扰5下面哪种内存管理方法有利于程序的动态链接（）正确答案：分段存储管理6在请求分页系统的页表增加了若干项，其中状态位供（）参考。

正确答案：程序访问7从下面关于请求分段存储管理的叙述中，选出一条正确的叙述（）。

正确答案：分段的尺寸受内存空间的限制，但作业总的尺寸不受内存空间的限制8虚拟存储器的特征是基于（）。

正确答案：局部性原理9实现虚拟存储器最关键的技术是（）。

正确答案：请求调页(段)10“抖动”现象的发生是由（）引起的。

正确答案：置换算法选择不当11 在请求分页系统的页表增加了若干项，其中修改位供（）参考。

正确答案：换出页面12 虚拟存储器是正确答案：程序访问比内存更大的地址空间13测得某个请求调页的计算机系统部分状态数据为：CPU利用率20％，用于对换空间的硬盘的利用率97.7％，其他设备的利用率5％。

由此断定系统出现异常。

此种情况下（）能提高CPU的利用率。

首次适应算法和最佳适应算法是动态存储分配解决方案研究的内容，所以本文对这两种算法的讨论是通过研究动态存储管理来进行的。

一、存储管理的基本问题：存储管理讨论的基本问题是：1)、系统如何应用户的“请求”执行内存分配动作？2)、系统如何对用户不再使用后“释放”的内存执行回收动作，以保证为新的“用户请求”提供内存分配？内存的分配可以以静态方式进行，内存空间被分割为固定大小的若干内存块，用户的请求到达只要找到一块空闲的内存块予以分配即可，很显然静态存储分配的好处主要是实现比较方便，效率高，程序执行中系统需要做的事情比较简单。

然而实际情况下提出“请求”的用户可能是进入系统的一个作业，也可能是程序执行过程中的一个动态变量。

“请求”需要获得的内存容量大小不一，这种做法造成了对程序大小的严格的限制，使某些问题不能够合理的解决，此外，也会造成内存空间的浪费。

动态存储管理就是确定如何满足一个个内存“请求”，如何更合理的使用有限的内存空间的一种内存分配解决方案，它以能够依据用户的请求依次进行内存空间的分配和回收，能够尽可能少的使用有限的空闲内存空间，最大限度的保证后续“请求”的可满足性为最终目的。

二、关于动态分配方案的分析：通常我们将已分配给用户是用的一段连续的内存空间称为“占用块”，将未分配给任何用户的一段连续的内存空间称为“可利用空间块”或者“空闲块”，我们在这里的描述将使用“占用块”和“空闲块”这两个概念。

整个内存区在没有任何用户进入和运行的情况下只有一个空闲块，即整个可供用户“请求”使用的用户内存区域。

随着不断的有用户请求进入系统，并依次获得系统为其分配的内存，使得整个内存区域逐渐被分割成两大部分：低地址区域包含若干占用块；高低址区域是空闲内存区域。

经过一段时间后，有的用户运行结束，它们所占用的内存区释放后转变为一个个空闲块，这就使整个内存区域呈现出占用块和空闲块交错相隔的状态。

而此时，如果再有新的用户“请求”到达，那么，系统如何为这个“请求”进行内存分配呢？在肯定动态存储管理的前提下，我们可以采取两种方案解决这个问题，一种解决方案是系统继续把高地址的空闲块分配给用户，而不理会低地址区域是否有结束执行的用户释放的内存块，直到剩余的高地址区域的空闲块不能满足新的用户“请求”，分配操作无法再进行下去时，才去回收结束执行的用户释放的内存块，并重新组织内存，进而完成内存分配。

动态分区分配算法仿真，循环首次适应算法、最佳适应算法、最坏适应算法#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一样时，由于先按地址递增排序了，所以还是地址低的在前。

题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、在请求分页系统的页表增加了若干项，其中状态位供（）参考。

⒈计算机系统中存储器一般分为哪两级？各有什么特点？答：计算机系统中存储器一般分为主存储器和辅助存储器两级。

主存储器简称主存，又称为内存，它由自然数顺序编址的单元(通常为字或字节)所组成，是处理机直接存取指令和数据的存储器，它速度快，但容量有限。

辅助存储器简称辅存，又称为外存，它由顺序编址的“块”所组成，每块包含若干个单元，寻址与交换以块为单位进行，处理机不能直接访问它，它须经过专门的启动入出过程与内存交换信息，它存取速度较慢，但容量远大于内存，实际上，现代计算机系统中用户的数据(或信息)都是保存在外存中。

⒉存储管理的目的是什么？答：存储管理要实现的目的是：为用户提供方便、安全和充分大的存储空间。

所谓方便是指将逻辑地址和物理地址分开，用户只在各自逻辑地址空间编写程序，不必过问物理空间和物理地址的细节，地址的转换由操作系统自动完成；安全则是指同时驻留在内存的多道用户程序相互之间不会发生干扰，也不会访问操作系统所占有的空间。

充分大的存储空间是指利用虚拟存储技术，从逻辑上对内存空间进行扩充，从而可以使用户在较小内存里运行较大程序。

⒊存储管理的任务是什么？答：存储管理是计算机操作系统软件的一部分，它负责完成对主存储器的地址转换，对主存储器进行分配与去配，解决多用户对主存储器的共享和保护，通过软件手段，实现对主存储器容量的扩充。

⒋地址转换可分为哪三种方式？比较这三种方式的优缺点。

答：由逻辑地址转化为物理地址的地址转换过程，按照转换的时间不同，可以分为3种方式：①绝对装入方式②静态重定位方式③动态重定位方式（第二问略）⒌可变分区常用的分区算法有哪几种？它们各自的特点是什么？答：首次适应算法、循环首次适应算法、最佳适应算法、最差适应算法（第二问略）⒍试用类C语言写首次适应算法的分配过程。

答：firstmatch(n){p=Free;while(p!=NULL){if(p->size>=n){if(p->size-n>=size)p->size=p->size-n;a=p;p=p+n;elsea=p;remove(Free,p);}elsep=p->next}return a}⒎什么叫紧凑？为什么要进行紧凑？答：为了解决碎片问题，可采用的一种方法是，将内存中的所有作业进行移动，使它们相邻接。

最佳适应算法最佳适应算法是从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。

找到：满足要求的自由分区分配排序：从小到大含义最佳适应算法（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` 表示所有进程都成功分配到分区。

⾸次适应与循环⾸次适应算法实现⼀、实验内容编程实现⾸次适应与循环⾸次适应算法。

⼆、实验要求1.任选⼀种⾼级语⾔实现；三、实验过程1、 设计思想⾸次适应算法(FF):将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链⾸开始查找，将满⾜需求的第⼀个空闲分区分配给作业。

循环⾸次适应算法（NF）：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下⼀个空闲分区开始查找，将满⾜需求的第⼀个空闲分区分配给作业2、 数据结构public class FreeArea {private int address;//内存地址private int size;//空闲区⼤⼩public FreeArea() {}public FreeArea(int address, int size) {this.address = address;this.size = size;}public int getAddress() {return address;}public void setAddress(int address) {this.address = address;}public int getSize() {return size;}public void setSize(int size) {this.size = size;}}4、运⾏结果：四、实验代码RR.Hpackage com.hu;import java.util.Scanner;public class MemoAlloc {public static void main(String[] args) {System.out.println("======⾸次适应算法======");FreeArea freeArea[]= init();FF(freeArea);System.out.println("=====循环⾸次适应算法=====");FreeArea freeArea1[]= init();NF(freeArea1);}public static void FF(FreeArea freeArea[]){//⾸次适应算法Scanner scanner = new Scanner(System.in);System.out.println("请输⼊要分配的内存⼤⼩：");int size = scanner.nextInt();for (int i =0;i<freeArea.length;i++){if (size<=freeArea[i].getSize()){//若分配内存⼤⼩⼩于空闲分区⼤⼩则分配成功System.out.println("分配内存成功");freeArea[i].setSize(freeArea[i].getSize()-size);//修改空闲分区⼤⼩break;}if (i== freeArea.length-1&&size>freeArea[i].getSize()) System.out.println("分配失败");}}public static void NF(FreeArea freeArea[]){//循环⾸次适应Scanner scanner = new Scanner(System.in);System.out.println("请输⼊要分配的内存⼤⼩：");int size = scanner.nextInt();boolean isWhile=true;int ProcessNum =0;int j=0;for (int i=ProcessNum;i< freeArea.length;i++,j++){if (size <= freeArea[i].getSize() ) {//若分配内存⼤⼩⼩于空闲分区⼤⼩则分配成功System.out.println("分配内存成功");freeArea[i].setSize(freeArea[i].getSize() - size);ProcessNum = j+1;//下⼀次查找时从本次找到的空闲分区的下⼀个分区开始找break;}else if (ProcessNum!=0 && i== freeArea.length-1&&size>freeArea[i].getSize()){ProcessNum=0;//若开始查找时不是从链⾸开始，最后⼀个空闲分区⼤⼩仍不能满⾜要求，则返回第⼀个空闲分区}else if(ProcessNum==0&&i== freeArea.length-1&&size>freeArea[i].getSize()){System.out.println("分配失败");//若开始查找时是从链⾸开始，最后⼀个空闲分区⼤⼩仍不能满⾜要求，则分配失败};}}public static FreeArea[] init(){//空闲区初始化并排序System.out.println("初始化空闲区并分配内存地址与⼤⼩");Scanner scanner = new Scanner(System.in);FreeArea[] freeAreas = new FreeArea[5];for (int i=0;i<freeAreas.length;i++){System.out.println("请输⼊内存地址与⼤⼩：");freeAreas[i] = new FreeArea(scanner.nextInt(),scanner.nextInt());}FreeArea t;for (int i = 0;i<freeAreas.length;i++){for (int j = 0;j<freeAreas.length-1;j++){if(freeAreas[j].getAddress()>freeAreas[j+1].getAddress()){t = freeAreas[j+1];freeAreas[j+1]=freeAreas[j];freeAreas[j]=t;}}}return freeAreas;}}五、实验总结通过本次实验我更加了解了循环⾸次适应与⾸次适应算法，⾸次适应算法优先利⽤低地址部分空闲分区，保留了⾼地址部分的⼤空闲区，缺点是低址部分不断被划分，会留下很多难以利⽤的⼩的外部碎⽚，每次都从低地址部分开始查会增加查找时的开销。

首次适应算法和循环首次适应算法一、实验目的1、加深操作系统内存管理过程的理解2、掌握内存分配算法的基本应用二、实验要求1.在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选取一分区分配给该作业2.上机时独立完成编辑，调试程序。

三、实验任务请同学们用C/C++实现一个完整的（可变）动态分区管理器，包括分配，回收，分区碎片整理等。

希望同学们实现如下功能：n 初始化功能：内存状态设置为初始状态。

n 分配功能：要求至少使用两种算法，用户可以选择使用。

n 回收功能：n 空闲块的合并：即紧凑功能，用以消除碎片。

当做碎片整理时，需要跟踪分配的空间，修改其引用以保证引用的正确性。

n 显示当前内存的使用状态，可以使用表格或图形。

四、实验指导1．基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。

显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。

2．数据结构动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。

另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。

其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。

这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。

本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。

基本的模拟方法有两种：（1）、先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。

（2）、不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。

程序代码：#include<iostream>using namespace std;intFreePartition[100];//空闲分区块数组intFirstPartition[100];//首次适应算法数组intCycleFirstPartition[100];//循环首次适应算法数组intProcessNeed[100];//每个作业的大小intPartitionNum,ProcessNum;//分区块数，作业数//首次适应算法void First(){inti,j;charstr;for(i=0;i<PartitionNum;i++){FirstPartition[i]=FreePartition[i];}for(i=0;i<ProcessNum;i++)//找出第一块满足作业的分区for(j=0;j<PartitionNum;j++){if(ProcessNeed[i]>FirstPartition[j])continue;else{FirstPartition[j]-=ProcessNeed[i];//找到后把分区大小减去作业的大小?? ? ? ? ? ? ? ?str='A'+i;cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl; break;}}cout<<endl;cout<<"分配之后剩余情况："<<endl;?? ?for(i=0;i<PartitionNum;i++)cout<<FirstPartition[i]<<" ";cout<<endl<<endl;}//循环首次适应算法voidCycleFirst(){inti,j=1;charstr;for(i=0;i<PartitionNum;i++){CycleFirstPartition[i]=FreePartition[i]; }for(i=0;i<ProcessNum;i++)//for(j=0;j<PartitionNum;j++){j=j-1;while(j<PartitionNum){if(ProcessNeed[i]>CycleFirstPartition[j])//continue;j++;else{CycleFirstPartition[j]-=ProcessNeed[i];str='A'+i;cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl; break;}//j++;//cout<<j<<" ";if(j==PartitionNum&&i!=ProcessNum){i=-1;}}}cout<<endl;cout<<"分配之后剩余情况："<<endl;for(i=0;i<PartitionNum;i++)cout<<CycleFirstPartition[i]<<" ";cout<<endl<<endl;}void main(){inti;cout<<"输入分区块数："<<endl;cin>>PartitionNum;cout<<"输入每个分区的大小："<<endl;for(i=0;i<PartitionNum;i++)cin>>FreePartition[i];cout<<"输入作业数："<<endl;cin>>ProcessNum;cout<<"输入每个作业的大小："<<endl;for(i=0;i<ProcessNum;i++)cin>>ProcessNeed[i];cout<<"------------首次适应算法-----------------"<<endl;First();cout<<"------------循环首次适应算法-------------"<<endl;?? ?CycleFirst();六、实验总结在一开始老师布置这次的实验题目时，自己根本不知道要干什么，因为在上课时对动态分区分配这节内容不是太了解，所以在上机时不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。

操作系统实验-首次适应算法与循环首次适应算法首次适应算法循环首次适应算法程序代码及截图：#include<stdio.h>#include<string.h>#define N 1024bool ROM[N];//设置内存块int p=0;//循环首次使用需要标记当前的空闲区块typedef struct Pcb//作业数据结构{char name[10];int start;int size;int state=0;} pcb;int free_rom_counter=0;pcb num[20]; //作业队列typedef struct Free_rom //空闲区结构体{int num;int start;int end;int space;} Free_room;Free_rom free_rom[100];//设置空闲区数组为100个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 init()//初始化{for(int i=0; i<N; i++)ROM[i]=0;}void show(){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]. start, free_rom[ i].space,free_rom[ i].end);}void insert_pcb1(pcb &a)//首次适应算法来实现作业调度{int i,j,k;for(i=0; i<N; i++)if(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<N; j++)//查询第一个空闲区，并判断是否适合插入作业if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1){a.start=i;//设置作业的开始内存a.state=1;//标记作业在内存中for(k=i; k<i+a.size&&j<N; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d,结束地址为%d\n",,a.start,a.start+a.size-1);return;}}if(i==N)//未查询到合适的区域printf("插入失败，无可用空间\n");}void insert_pcb2(pcb &a)//循环首次适应算法来实现作业调度{int i,j,k;for(i=p; i<N; i++)//从所标记的当前区域开始查询，查询到末内存 {if(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<N; j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//找到合适的空闲区{a.start=i;a.state=1;for(k=i; k<i+a.size&&j<N; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d,结束地址为%d\n",,a.start,a.start+a.size-1);p=i+a.size;return;}}}for(i=0; i<p; i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<p; j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//成功找到结束，并标记当前P为现在的作业的尾部{a.start=i;a.state=1;for(k=i; k<i+a.size&&j<p; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d\n",,a.start);p=i+a.size;break;}}if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句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");}int main(){init();int count=0;int choose1,choose;char name[10];pcb a;printf("1、首次适应算法\n");printf("2、循环首次适应算法\n");scanf("%d",&choose1);do{printf("\n\n1、插入进程\n");printf("2、删除进程\n");printf("3、显示进程的信息\n");printf("4、显示空闲区\n");scanf("%d",&choose);if(choose==1){printf("输入进程名\n");scanf("%s",&);printf("输入进程大小\n");scanf("%d",&a.size);if(choose1==1)insert_pcb1(a);else insert_pcb2(a);num[count++]=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("进程名\t\t开始地址\t\t大小\t\t结束地址\t\t\n");//输出内存信息for(int i=0; i<count-1; i++)for(int j=i; j<count-1; j++)if(num[j].start>num[j+1].start){a=num[j];num[j]=num[j+1];num[j+1]=a;}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);}else if(choose==4){find_free_rom();show();}else break;}while(1);return 0;}首次适应算法：本实验共采用1024个内存进行模拟，首先对内存初始化，得到一个大的空闲区：相继插入3个进程：分别插入进程A B C,大小分别为100,200,300 此时查询进程信息和查询空闲区信息有一块大小为424 起始地址为600的空闲区在进行插入D删除B此时有两块空闲区插入一个150大小的进程，他的起始地址应为100此时空闲区只有2块，一块大小为50，删除C 进程，构造一块大空闲区再插入一个进程为100大小,此时两块空闲区都满足，此时应从第一块插入再插入一个大于两块空闲区大小的进程，此时无可用空间首次适应算法完成。

首次适应分配算法首次适应（First Fit）分配算法是一种常用的内存分配算法，在操作系统中被广泛应用于动态分区管理。

它的主要思想是将内存分成若干个分区，每个分区有不同的大小，当一个进程请求分配内存时，首次适应算法会从头开始查找，找到第一个能满足需求的分区进行分配。

以下将详细介绍首次适应分配算法的原理、特点以及应用。

首次适应分配算法的原理是根据内存分区的起始地址从小到大进行查找。

当一个进程请求分配内存时，首次适应算法会从内存的起始地址开始遍历，找到第一个空闲分区，并分配给该进程。

如果找不到满足需求的分区，则分配失败。

首次适应分配算法的特点有以下几个方面。

首先，它是一种简单且高效的算法，因为它只需要遍历一次内存分区即可完成分配。

其次，它能够充分利用碎片化的内存空间，减少内存的浪费。

然而，首次适应算法也存在一些问题，比如会产生外部碎片，导致内存利用率降低。

另外，由于它从头开始遍历，可能会导致分配时间较长，尤其是当分区较多时。

首次适应分配算法在操作系统中有着广泛的应用。

首先，它被用于动态分区管理，可以有效地管理内存资源，满足不同进程的内存需求。

其次，它也被应用于虚拟内存管理，在虚拟内存中，内存被划分成若干个页，当一个进程请求分配内存时，首次适应算法可以找到合适的页进行分配。

此外，首次适应算法也可以用于磁盘空间管理、文件分配等方面。

尽管首次适应分配算法有着诸多优点和应用场景，但也存在一些限制和不足之处。

首先，由于它从头开始遍历，分配时间较长，当分区较多时，会影响系统的响应速度。

其次，它容易产生外部碎片，导致内存利用率降低。

另外，由于首次适应算法只考虑了分区的起始地址，没有考虑分区的大小，可能会导致大的分区无法被充分利用。

为了克服首次适应分配算法的一些缺点，人们提出了其他的内存分配算法，如最佳适应（Best Fit）算法、最坏适应（Worst Fit）算法等。

最佳适应算法会选择最小且能满足需求的分区进行分配，可以减少外部碎片的产生；最坏适应算法会选择最大的分区进行分配，可以充分利用大的分区。

【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）（编码⽔平较菜，写博客也只是为了个⼈知识的总结和督促⾃⼰学习，如果有错误，希望可以指出）今天测试，发现⼀点问题：1.最佳插⼊算法：对于插⼊的时候忘记修改temp.next.front的指向2.回收头节点的时候现在多了⼀种判断。

判断头节点的下⼀个是否为空。

对如果不为空⽽且后⾯的空闲的话，做出了处理。

原来则没有这⼀情况。

1.动态分区分配算法：为了实现动态分区分配，通常将系统中的空闲分区链接成⼀个链。

所谓顺序查找是指依次搜索空闲分区链上的空闲分区，去寻找⼀个⼤⼩能满⾜要求的分区。

--------计算机操作系统（第四版）2.动态分区算法主要包括四种：（1）.⾸次适应算法（first fit，FF）：要求，空闲分区链以地址递增的顺序链接。

每次从链⾸开始，直到找到第⼀个能满⾜要求的空闲分区为⽌。

简单来说，就是，每次都从第⼀个开始顺序查找，找到⼀块区域可以满⾜要求的。

优点：优先利⽤内存中低址部分的空闲分区，从⽽保留了⾼址部分的⼤空闲区，这为以后到达的⼤作业分配⼤的内存空间创造了条件。

缺点：低址部分不断被划分，会留下许多难以利⽤的，很⼩的空闲分区，称为碎⽚。

⽽每次查找⼜都是从低址部分开始的，这⽆疑⼜会增加查找可⽤空闲分区时的开销。

（2）.循环⾸次适应算法（next fit，NF）：与FF算法区别就是，不是每次都从⾸次开始，⽽是从上次找到的空闲分区的下⼀个空闲分区开始。

（第⼀次查找的话也是从⾸页开始）。

特点：能使内存中的空闲区分布得较均匀。

(3）.最佳适应算法（best，BF）：将所有空闲分区按照空闲分区容量⼤⼩从⼩到⼤的顺序连接起来，形成⼀个空闲分区链。

即，每次都是找空间容量不但可以满⾜要求的空闲区，⽽且该空闲分区的容量还要最接近要求的容量⼤⼩。

优点：每次分配给⽂件的都是最合适该⽂件⼤⼩的分区。

存储管理动态分区分配算法的模拟一(题目: 存储管理--- 动态分区分配算法的模拟二(任务: 设计主界面以灵活选择某算法，且以下算法都要实现:首次适应算法、循环首次适应算法、最佳适应算法;。

三(思想: 对任务进行构思和设想。

(1) 首次适应算法:FF算法要求空闲分区链以地址递增的次序链接。

在分配内存时，从链首开始顺巡查找，直到找到一个大小能够满足要求的空闲分区为止; 然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区间仍留在空闲链中。

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

该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。

这给为以后到达的大作业分配大的内存空间创造了条件。

(2) 循环首次适应算法该算法是由首次适应算法演变而成的。

在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。

为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个( 链尾)空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。

(3) 最佳适应算法是将最小的空闲分区分配给作业，避免"大材小用"。

为了加速寻找，该算法要求将所有的空闲分区按照某容量以从小到大的顺序形成一空闲分区链。

这样，第一次找到的能满足要求的空闲区，必然是最佳的。

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

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

四(目的: 在构思中提出要达到的目的。

(1) 按照首次适应算法对内存进行分配，得到(2) 按照循环首次适应算法对内存(3) 按照最佳适应算法对内存进行分配(4) 在作业完成时，释放作业所在内存块，使其能够再次被利用五(方案: 对构思的细化，提出粗略的方案。

首次适应和循环首次适应算法模拟内存分配2008-07-01 09:40/********************************内存管理模拟程序*******************************/#include<iostream.h>#include<stdio.h>#include<math.h>#include<stdlib.h>#include <time.h>#include <windows.h>/*定义宏*/#define TotalMemSize 1024 /*划分的物理块的大小，地址范围0~1023*/#define MinSize 2 /*规定的不再分割的剩余分区的大小*/#define getpch(type) (type*)malloc(sizeof(type))/*定义内存块*/typedef struct memBlock{struct memBlock *next;/*指向下一个块*/int stAddr; /*分区块的初始地址*/int memSize; /*分区块的大小*/int status; /*分区块的状态，0：空闲，1：以被分配*/}MMB;/*定义全局变量*/MMB *idleHead=NULL; /*空闲分区链表的头指针*/MMB *usedHead=NULL; /*分配分区链表的头指针*/MMB *usedRear=NULL; /*分配分区链表的链尾指针*/MMB *np; /*循环首次适应算法中指向即将被查询的空闲块*/int idleNum=1;/*当前空闲分区的数目*/int usedNum=0;/*当前已分配分区的数目*/MMB *memIdle=NULL; /*指向将要插入分配分区链表的空闲分区*/MMB *memUsed=NULL; /*指向将要插入空闲分区链表的已分配分区*/int flag=1;/*标志分配是否成功，1：成功*//*函数声明*/void textcolor (int color);/*输出着色*/void InitMem();/*初始化函数*/int GetUseSize(float miu,float sigma); /*获得请求尺寸*/MMB *SelectUsedMem(int n);/*选择待释放的块*/void AddToUsed();/*将申请到的空闲分区加到分配分区链表中*/int RequestMemff(int usize); /*请求分配指定大小的内存,首次适应算法*/int RequestMemnf(int usize); /*请求分配指定大小的内存,循环首次适应算法*/void AddToIdle();/*将被释放的分配分区加到空闲分区链表中(按地址大小）*/ void ReleaseMem(); /*释放指定的分配内存块*//*主函数*/void main(){int sim_step;float miu,sigma; /*使随机生成的请求尺寸符合正态分布的参数*/int i;int a;char c;MMB *p;/* double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0; double aveStep=0,aveSize=0,aveRatio=0;int step=0,usesize=0; */textcolor(11);printf("\n\t\t内存管理模拟程序\n\n");/* InitMem();*/while(true){double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;double aveStep=0,aveSize=0,aveRatio=0;int step=0,usesize=0;InitMem();textcolor(12);printf("\n\n首次适应算法：0");printf("\n循环首次适应算法：1\n");textcolor(11);printf("\n请选择一种算法：");scanf("%d",&a);textcolor(15);printf("\n输入一定数量的步数：(sim_step)");scanf("%d",&sim_step);printf("\n 输入使随机生成的请求尺寸符合正态分布的参数：miu,sigma ");scanf("%f,%f",&miu,&sigma);for(i=1;i<=sim_step;i++){textcolor(10);printf("\n\n#[%d]\n",i);do{usesize=GetUseSize(miu,sigma);while((usesize<0)||(usesize>TotalMemSize)){usesize=GetUseSize(miu,sigma);}textcolor(13);printf("\n\n申请的内存尺寸为：%d",usesize);printf("\n此时可用的空闲分区有%d 块情况如下：",idleNum);p=idleHead;textcolor(15);while(p!=NULL){printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);p=p->next;}TotalSize+=usesize;if(a==0)step=RequestMemff(usesize);elsestep=RequestMemnf(usesize);TotalStep+=step;n++;}while(flag==1);p=usedHead;while(p!=NULL){TotalUSize+=p->memSize;printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);p=p->next;}textcolor(11);if(TotalUSize!=0){Ratio=TotalUSize/TotalMemSize;TotalUSize=0;printf("\n内存利用率NO.%d :%f%c",i,100*Ratio,'%');}else{Ratio=0;printf("\n内存利用率NO.%d :%c%c",i,'0','%');}TotalRatio+=Ratio;ReleaseMem();}if(n!=0){textcolor(10);aveStep=TotalStep/n;aveSize=TotalSize/n;aveRatio=TotalRatio/sim_step;printf("\n平均搜索步骤：%f",aveStep);printf("\n平均请求尺寸：%f",aveSize);printf("\n平均内存利用率：%f",aveRatio);}}}// 输出着色/////////////////////////////////////////void textcolor (int color){SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color ); }/******************************函数名：InitMem()用途：把内存初始化为一整块空闲块****************************************/void InitMem(){MMB *p;p=getpch(MMB);p->memSize=TotalMemSize;p->stAddr=0;p->status=0;p->next=NULL;idleHead=p;np=idleHead;usedHead=NULL;usedRear=NULL;idleNum=1;usedNum=0;flag=1;memIdle=NULL;memUsed=NULL;}/******************************函数名：GetUseSize(float miu,float sigma)用途：获得请求尺寸；参数说明：float miu,float sigma ：正态分布的参数返回值:申请尺寸的大小；****************************************************/ int GetUseSize(float miu,float sigma){float r1,r2;float u,v,w;float x,y;do{r1=rand()/32767.0;r2=rand()/32767.0;u=2*r1-1;v=2*r2-1;w=u*u+v*v;}while(w>1);x=u*sqrt(((-log(w))/w));y=v*sqrt(((-log(w))/w));return miu+sigma*x;}/******************************函数名：*SelectUsedMem(int n)用途：选择待释放的块(0~n-1)返回值：指向待释放的块的指针；****************************************************/ MMB *SelectUsedMem(int n){MMB *p;int i,j;if(n>0){i = rand()%n ;textcolor(5);printf("\n\n当前已分配分区总数为：%d",n);printf("\n待释放块的序号为：%d\n",i );p=usedHead;if(p!=NULL){for(j=i;j>0;j--)p=p->next;return(p);}elsereturn(NULL);}else{printf("\n当前没有可释放的资源！\n");}}/******************************函数名：AddToUsed()用途：将申请到的空闲分区加到分配分区链表中***************************************************************/ void AddToUsed(){MMB *p;memIdle->status=1;if(usedHead==NULL){usedHead=memIdle;usedRear=usedHead;}else{usedRear->next=memIdle;usedRear=memIdle;}usedNum++;printf("\n当前分配分区共有%d块！",usedNum);p=usedHead;while(p!=NULL){printf("\n始址:%d \t 尺寸：%d",p->stAddr,p->memSize);p=p->next;}}/******************************函数名：RequestMemff(int usize)参数说明：usize：请求尺寸的大小；用途：请求分配指定大小的内存,首次适应算法返回值：搜索步骤***************************************************************/ int RequestMemff(int usize){MMB *p1,*p2,*s;int step;int suc=0;int size1,size2;if(idleHead==NULL){flag=0;textcolor(12);printf("\n分配失败！");return 0;}else{if((idleHead->memSize)>usize){size1=(idleHead->memSize)-usize;if(size1<=MinSize){memIdle=idleHead;idleHead=idleHead->next;memIdle->next=NULL;idleNum--;}else{s=getpch(MMB);s->memSize=usize;s->stAddr=idleHead->stAddr;s->status=1;s->next=NULL;memIdle=s;idleHead->memSize=idleHead->memSize-usize;idleHead->stAddr=idleHead->stAddr+usize;}flag=1;textcolor(12);printf("\n分配成功！");AddToUsed();}else{p1=idleHead;step=1;p2=p1->next;while(p2!=NULL){if((p2->memSize)>usize){size2=(p2->memSize)-usize;if(size2<=MinSize){p1->next=p2->next;memIdle=p2;memIdle->next=NULL;idleNum--;}else{s=getpch(MMB);s->memSize=usize;s->stAddr=p2->stAddr;s->status=1;s->next=NULL;memIdle=s;p2->memSize=p2->memSize-usize;p2->stAddr=p2->stAddr+usize;}flag=1;suc=1;textcolor(12);printf("\n分配成功！");AddToUsed();p2=NULL;}{p1=p1->next;p2=p2->next;step++;}}if(suc==0){flag=0;textcolor(12);printf("\n分配失败！");}}}return step;}/******************************函数名：AddToIdle()用途：将被释放的分配分区加到空闲分区链表中(按地址递增顺序排列）***************************************************************/ void AddToIdle(){MMB *p1,*p2;int insert=0;if((idleHead==NULL)){idleHead=memUsed;idleNum++;np=idleHead;}else{int Add=(memUsed->stAddr)+(memUsed->memSize);if((memUsed->stAddr<idleHead->stAddr)&&(Add!=idleHead->stAddr)) {memUsed->next=idleHead;idleHead=memUsed;idleNum++;}else{if((memUsed->stAddr<idleHead->stAddr)&&(Add==idleHead->stAddr)) {idleHead->stAddr=memUsed->stAddr;idleHead->memSize+=memUsed->memSize;}else{p1=idleHead;p2=p1->next;while(p2!=NULL){if(memUsed->stAddr>p2->stAddr){p1=p1->next;p2=p2->next;}else{int Add1=p1->stAddr+p1->memSize;int Add2=p2->stAddr-memUsed->memSize;if((Add1==memUsed->stAddr)&&(memUsed->stAddr!=Add2)){p1->memSize=p1->memSize+memUsed->memSize;}if((Add1!=memUsed->stAddr)&&(memUsed->stAddr==Add2)){p2->memSize=p2->memSize+memUsed->memSize;p2->stAddr=memUsed->stAddr;}if((Add1!=memUsed->stAddr)&&(memUsed->stAddr!=Add2)){memUsed->next=p2;p1->next=memUsed;if(np->stAddr==p2->stAddr)np=p1->next;idleNum++;}if((Add1==memUsed->stAddr)&&(memUsed->stAddr==Add2)){p1->memSize=p1->memSize+memUsed->memSize+p2->memSize;p1->next=p2->next;if((np->stAddr)==(p2->stAddr))np=p1;idleNum--;}p2=NULL;insert=1;}}if(insert==0){p1->next=memUsed;idleNum++;}}}}}/******************************函数名：ReleaseMem()用途：释放指定的分配内存块***************************************************************/ void ReleaseMem(){MMB *q1,*q2;MMB *s;if(usedNum==0){printf("\n当前没有分配分区!");return;}else{s=SelectUsedMem(usedNum);if(s!=NULL){if(s->stAddr==usedHead->stAddr){memUsed=usedHead;usedHead=usedHead->next;memUsed->next=NULL;AddToIdle();usedNum--;}else{q1=usedHead;q2=q1->next;while(q2!=NULL){if(q2->stAddr!=s->stAddr){q1=q1->next;q2=q2->next;}else{q1->next=q2->next;memUsed=q2;memUsed->next=NULL;if(q1->next==NULL)usedRear=q1;AddToIdle();usedNum--;q2=NULL;}}}}}}/******************************函数名：RequestMemnf(int usize)参数说明：usize：请求尺寸的大小；用途：请求分配指定大小的内存,循环首次适应算法返回值：搜索步骤***************************************************************/ int RequestMemnf(int usize){MMB *p2,*p,*s;int step;int iNum=0;int suc=0;int size1,size2,size3;if(idleHead==NULL){flag=0;printf("\n分配失败！");return 0;}else{iNum=idleNum;while(iNum>0){iNum--;if((np->memSize)>usize){/*指针指向的空闲块满足条件,且正好为头指针*/if(np->stAddr==idleHead->stAddr){size1=(idleHead->memSize)-usize;if(size1<=MinSize){memIdle=idleHead;idleHead=idleHead->next;memIdle->next=NULL;idleNum--;}else{s=getpch(MMB);s->memSize=usize;s->stAddr=idleHead->stAddr;s->status=1;s->next=NULL;memIdle=s;idleHead->memSize=idleHead->memSize-usize;idleHead->stAddr=idleHead->stAddr+usize;}if((idleHead==NULL)||(idleHead->next==NULL))np=idleHead;elsenp=idleHead->next;}else/*指针指向的空闲块满足条件,不为头指针*/{size2=(np->memSize)-usize;if(size2<=MinSize) /*从空闲链表中删除*/{p=idleHead;while(p->next->stAddr!=np->stAddr)p=p->next;p->next=np->next;memIdle=np;memIdle->next=NULL;np=p;idleNum--;}else{s=getpch(MMB);s->memSize=usize;s->stAddr=np->stAddr;s->status=1;s->next=NULL;memIdle=s;np->memSize=np->memSize-usize;np->stAddr=np->stAddr+usize;}if(np->next==NULL)np=idleHead;elsenp=np->next;}step=1;flag=1;suc=1;textcolor(12);printf("\n分配成功！");AddToUsed();iNum=0;}else /*当前指针指向的空闲区不满足条件*/ {step=1;p2=np->next;if(p2==NULL){np=idleHead;iNum--;}else{if((p2->memSize)>usize){size3=(p2->memSize)-usize;if(size3<=MinSize){np->next=p2->next;memIdle=p2;memIdle->next=NULL;idleNum--;}else{s=getpch(MMB);s->memSize=usize;s->stAddr=p2->stAddr;s->status=1;s->next=NULL;memIdle=s;p2->memSize=p2->memSize-usize;p2->stAddr=p2->stAddr+usize;}flag=1;suc=1;printf("\n分配成功！");AddToUsed();if(p2->next==NULL)np=idleHead;elsenp=p2->next;p2=NULL;iNum=0;}else{np=np->next;p2=p2->next;iNum--;step++;}}}// iNum--;}if(suc==0){flag=0;textcolor(12);printf("\n分配失败！");}}return step;}。

#iiiclude<iostieam>#iiiclude<stdlib.h> using namespace std;#define Free 0 〃空闲状态#define Busy 1 〃已用状态#define OK 1 〃完成#define ERROR。

〃出错#define MAXJength 512 //最大内存空间为512KB typedef int Status; hit flag;typedef stnict fieeaiea//定义一个空闲区说明表结构{long size; 〃分区大小long adckess; 〃分区地址mt state; 〃状态JElemType;//线性表的双向链表存储结构typedef stnict DuLNode{ElemType data;stiuct DuLNode *prior; 〃前趋指针stnict DuLNode *next; 〃后继指针}DuLNode,*DuLinkList;DuLnikList block_fkst; 〃头结点DuLnikList blockjast; 〃尾结点Status alloc(int);//内存分配Status See(int); 〃内存回收Status Fust_fit(iiit);//W 次适应算法Status Best_fit(mt); 〃最佳适应算法void show。

;〃查看分配Status InitblockO；〃开创空间表Status Irntblock。

〃开创带头结点的内存空间链表 {block_fust=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_fiist->prioi-NULL;block_fiist->next=block_last; block_last->pnor=block_fiist;block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX」ength;block_last->data.state=Free;return OK;}〃分配主存Status alloc(mt ch) (hit request = 0;coutvv”请输入需要分配的主存大小(单位:KB)： "；ciii»request;ifi(request<0 ||request==O) (coutvv”分配大小不合适，请重试！”《endl;retuin ERROR:}if(ch==2 ”/选择最佳适应算法(if(Best_fit(iequest)=OK) coutw”分配成功！"<<endl; elsecout«H内存不足，分配失败！ "<<endl;return OK;}else 〃默认首次适应算法(if(Fiist_fit(request)==OK) coutw”分酉已成功！H«endl; elsecout«H内存不足，分配失败！ "<<endl;return OK;} }〃首次适应算法Status request)(〃为申请作业开辟新空间且初始化DuLnikList temp=(DuLnikList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_fiist->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->pnor;temp->next=p;temp->data.addiess=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(mt request) (mt ch; 〃记录最小剩余空间DuLnikList temp=(DuLnikList)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 ifi(q->data.size > p->data.size)q=p;ch=p->data.size-request;) p=p->next;}if(q=NULL) i-eturn ERROR;//没有找到空闲块else if(q->data.size==request)(q->data .state=Bu sy;return OK;} elsetemp->prior=q->pnor;temp->next=q;temp->data.address=q->data.addiess;q->pnor->next=temp;q->pnor=temp;q->data.addiess+=request;q->data.size=ch;return OK;}return OK;}〃主存回收Status fiee(int flag) (DuLNode *p=block_first;fbr(int i= 0; i <= flag; i++)if(p?=NULL)p=p->next;elsereturn ERROR:p->data .state=Free;if(p->pnor?=block_fust && p->prior->data.state=Free)//与前面的空闲块相连 ( p->pnor->data.size+=p->data.size;p->pnor->next=p->next;p->next->piioi-p->piior;p=p->piior;if(p->next!=block_last && p->next->data.state=Free)//与后面的空闲块相连 ( p->data.size+=p->next->data.size;p->next->next->prioi -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";DuLNode *p=block_first->next;coutw"分区号\t起始地址\t分区大小\t状态\n\iT;wliile(p)(cout«" M«flag++«M\t H;cout«M M«p->data.addiess«,l\t\t H;cout«M "«p->data.size«H KB\t\t n;if(p->data.state==Fiee) coutw”空闲WW”；else coutw” 已分配\n\n”；p=p->next;}cout〈v”++++++++++++++++++++++++++++++++++++++++++++++W\iT; }〃主函数hit(mt ch;//算法选择标记coutvv”请输入所使用的内存分配算法：证”；coutv V”( 1)首次适应算法\n(2)最佳适应算法\n” ；ciii»ch;while(ch<l ||ch>2)coutvv”输入错误，请重新输入所使用的内存分配算法：\1之cin»ch;}Imtblock(); 〃开创空间表mt choice; 〃操作选择标记wlule(l)(showQ;coutvv”请输入您的操作：”；cout«H\iil:申请内存\112:释放内存W0:退出\n"；cm»choice;if(choice==l) alloc(ch); // 申请内存else if(choice=2) // 释放回收mt flag;coutvv”请输入您要释放的分区号：”；cin»flag;fiee(flag);}else if(choice=0) break; //退出else//输入操作有误coutvv”输入有误，请重试！“<<endl;contmue;。