首次适应算法实验报告

1 需求分析1）本程序要求实现对内存的动态分配与回收的模拟，同时，在内存的分配时还必须使用首次适应算法，最后，还要显示内存块分配和回收后空闲内存分区链的情况。

2）要实现对作业的内存分配，首先要有一个对作业进行创建和分配内存的模块，其中，该模块在分配内存时要使用首次适应算法；要实现对内存的回收，要有一个内存回收的模块，其中，该模块在回收内存时要考虑内存回收的四种情况；最后，还要有一个能显示内存空闲分区链的情况的模块。

2 概要设计1）首次适应算法的结构如图1：图1 首次适应算法的结构图2）数据结构：struct Fq{int size,o,no;Fq *before,*next;};其中，Fq表示结构体的名字（类型），size表示分区的可用空间大小，o表示该分区的状态（是否已分配），no表示该分区中的作业标志，*before表示该结点的向前指针，*next表示该结点的向后指针。

3）各种函数说明：void alloc(int b,int no,Fq *p)；对作业no进行内存分配的功能函数；其中，参数b表示需求的内存大小，参数no表示作业的编号，参数*p表示空闲分区链的第一个非空结点的指针；void free(Fq *c)；将地址为c的分区的内存回收；其中，参数*c表示要回收内存的结点；void create(Fq *head)；创建新作业的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数alloc（）使用；void cha(Fq *head)；查看内存中的空闲分区链的子函数；其中，参数*head表示空闲分区链的链首指针；void hui(Fq *head)；回收内存的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数free（）使用；3 运行环境1）操作系统: Windows XP ( 32位 / DirectX 11 )2）电脑: X86 兼容台式电脑处理器: 英特尔 Pentium(奔腾) 双核 E5300 @ 2.60GHz内存: 2 GB4 开发工具和编程语言1）开发工具：Visual C++ 6.0；2）编程语言：C++语言；5 详细设计1）程序结构如图2：图2 程序结构图2）●主菜单模块：void main()//主函数{Fq *head=new Fq;head->next=new Fq;head->next->size=MAXSIZE;head->next->o=0;head->next->next=NULL;int choice=0;do{cout<<"请选择你要进行的操作："<<endl;cout<<"1、创建新作业 2、查看空闲分区链 3、回收内存空间 0、退出"<<endl;cin>>choice;switch(choice){case 1: create(head);break;case 2: cha(head);break;case 3: hui(head);break;case 0: break;default: cout<<"输入错误！"<<endl;}}while(choice!=0);}●创建新作业模块：void create(Fq *head)//创建作业子函数{Fq *p=head->next;p->before=head;int no=0,b=0;cout<<"请输入要创建的作业的编号：";cin>>no;cout<<"请输入作业的需求空间大小：";cin>>b;alloc(b,no,p);//此处调用功能函数alloc()}●查看空闲分区链模块：void cha(Fq *head)//查看内存中的空闲分区链的子函数{Fq *p=head->next;p->before=head;int i=0;cout<<"空闲分区链的情况为："<<endl;while(p!=NULL){if(p->o==0){cout<<"空闲分区"<<++i<<" "<<p->size<<"K"<<endl;}p=p->next;}}●回收内存空间模块：void hui(Fq *head)//回收内存的子函数{Fq *p=head->next;p->before=head;int no=0;cout<<"请输入要回收内存的作业号：";cin>>no;while(p!=NULL){if(p->no==no){free(p);//此处调用功能函数free()cout<<"作业"<<no<<"的内存已回收！"<<endl;return ;}else p=p->next;}}●内存分配功能函数模块：void alloc(int b,int no,Fq *p)//对作业no进行内存分配的子函数{while(p!=NULL){if(p->o==1) {p=p->next;}else{if(p->size>b){if(p->size-b<=min_size){p->o=1;p->no=no;}else{Fq *q=new Fq;Fq *r;r=p->before;r->next=q;q->before=r;q->next=p;p->before=q;q->size=b;p->size=p->size-b;q->no=no;q->o=1;}cout<<"内存分配成功！"<<endl;return ;}else p=p->next;}}cout<<"内存分配失败！"<<endl;}●内存回收功能函数模块：void free(Fq *c)//将地址为c的分区内存回收{if(c->before->o==0&&c->next->o==0){Fq *r=c->before,*s=c->next->next;r->size=(r->size+c->size+c->next->size);r->next=s;if(s!=NULL) s->before=r;}if(c->before->o==0&&c->next->o!=0){c->before->size=c->before->size+c->size;c->before->next=c->next;c->next->before=c->before;}if(c->next->o==0&&c->before->o!=0){Fq *r=c->next->next;c->size=c->size+c->next->size;c->next=c->next->next;if(r!=NULL) r->before=c;c->o=0;}else c->o=0;}6 调试分析1）内存分配功能函数模块：刚开始对作业分配内存时，只是将空闲分区的大小以及前后向指针进行修改，而没有对分配给作业的内存进行设置；这样，尽管内存的空闲分区大小已经变小，但是，以后却无法对已分配的内存空间以及作业进行修改；于是，我经过思考后，决定将分配给作业的内存空间也设置为一个分区，只不过不是空闲的分区，通过状态标识符o来与空闲分区进行区别。

存储器管理实验实验报告一、实验目的存储器管理是操作系统的重要组成部分，本次实验的目的在于深入理解存储器管理的基本原理和方法，通过实际操作和观察，掌握存储器分配与回收的算法，以及页面置换算法的实现和性能评估。

二、实验环境本次实验使用的操作系统为 Windows 10，编程语言为 C+＋，开发工具为 Visual Studio 2019。

三、实验内容与步骤（一）存储器分配与回收算法实现1、首次适应算法（1）原理：从空闲分区链的首地址开始查找，找到第一个满足需求的空闲分区进行分配。

（2）实现步骤：建立空闲分区链表，每个节点包含分区的起始地址、大小和状态（已分配或空闲）。

当有分配请求时，从链表头部开始遍历，找到第一个大小满足需求的空闲分区。

将该分区进行分割，一部分分配给请求，剩余部分仍作为空闲分区留在链表中。

若找不到满足需求的空闲分区，则返回分配失败。

2、最佳适应算法（1）原理：从空闲分区链中选择与需求大小最接近的空闲分区进行分配。

（2）实现步骤：建立空闲分区链表，每个节点包含分区的起始地址、大小和状态。

当有分配请求时，遍历整个链表，计算每个空闲分区与需求大小的差值。

选择差值最小的空闲分区进行分配，若有多个差值相同且最小的分区，选择其中起始地址最小的分区。

对选中的分区进行分割和处理，与首次适应算法类似。

3、最坏适应算法（1）原理：选择空闲分区链中最大的空闲分区进行分配。

（2）实现步骤：建立空闲分区链表，每个节点包含分区的起始地址、大小和状态。

当有分配请求时，遍历链表，找到最大的空闲分区。

对该分区进行分配和处理。

（二）页面置换算法实现1、先进先出（FIFO）页面置换算法（1）原理：选择在内存中驻留时间最久的页面进行置换。

（2）实现步骤：建立页面访问序列。

为每个页面设置一个进入内存的时间戳。

当发生缺页中断时，选择时间戳最早的页面进行置换。

2、最近最久未使用（LRU）页面置换算法（1）原理：选择最近一段时间内最长时间未被访问的页面进行置换。

最佳适应算法实验报告一、实验目的了解首次适应算法、最佳适应方法、最差适应算法二、实验方法修改Minix操作系统的内存分配源码，实现最佳适应算法三、实验任务修改Minix操作系统中的内存分配源码，将首次适应算法更改为最佳适应算法。

重新编译系统映像文件，观察实验结果。

四、实验要点内存分配、首次适应算法、最佳适应算法。

五、实验内容5.1 minix内存分配源码安装好minix操作系统以后，minix系统的源码位于/usr/src目录中。

其中，与内存分配的相关源码则在/usr/src/servers/pm/alloc.c中。

minix系统初始的内存分配算法为首次适应算法。

在minix系统中，空闲的内存空间信息采用链表的信息储存起来，而操作系统分配内存空间的过程则是在这个链表中寻找一个合适空间，返回内存空间的地址，再更改链表中的内存空间信息。

这就是minix系统分配内存的实质。

5.2分析首次适应算法首次适应算法，指的从空闲内存块链表的第一个结点开始查找，把最先找到的满足需求的空闲内存块分配出去。

这种算法的优点是分配所需的时间较短，但这种算法会形成低地址部分形成很多的空间碎片，高地址区保留大量长度较长的空闲内存块。

内存分配的操作在/usr/src/servers/pm/alloc.c源文件中的alloc_mem函数中完成。

在函数的初始位置，定义了两个用于遍历链表的指针变量，两个指针变量的定义如下：registerstruct hole *hp, *prev_ptr;而hole结构体的定义如下：PRIVATE struct hole {struct hole *h_next;phys_clicksh_base;phys_clicksh_len;} hole[NR_HOLES];先分析这个结构体的定义，这个结构体中，有三个变量，h_next是一个指向链表下一个结点的指针变量；h_base则是指向这个链表所表示的空闲内存空间的地址，h_len 则是这个空闲内存空间的长度；phys_clicks的定义可以在/usr/src/include/minix/type.h 中找到，phys_clicks的定义为：typedef unsigned intpyhs_clicks;phys_clicks其实就是无符号的整数类型。

操作系统存储管理实验报告一、实验目的本次实验的目的是通过编写一段程序，实现对内存的分配和回收操作，并验证算法的正确性和性能。

二、实验内容1.实现首次适应算法首次适应算法是一种动态分配的内存管理算法，通过从低地址往高地址内存块，找到第一个满足需求的空闲块进行分配。

具体实现过程如下：（1）初始化内存空间，设置内存块的大小和地址范围；（2）编写一个函数，实现内存的分配操作，根据需求大小找到第一个合适的空闲块，并在其前后设置相应的标志位；（3）编写一个函数，实现内存的回收操作，根据释放块的地址，将其前后的标志位进行合并；（4）模拟应用程序的运行，测试内存的分配和回收操作。

2.实现最佳适应算法最佳适应算法是一种动态分配的内存管理算法，通过整个内存空间，找到最小的满足需求的空闲块进行分配。

具体实现过程如下：（1）初始化内存空间，设置内存块的大小和地址范围；（2）编写一个函数，实现内存的分配操作，遍历整个内存空间，找到满足需求且大小最小的空闲块进行分配；（3）编写一个函数，实现内存的回收操作，根据释放块的地址，将其前后的标志位进行合并；（4）模拟应用程序的运行，测试内存的分配和回收操作。

三、实验结果1.首次适应算法经过测试，首次适应算法能够正确地进行内存的分配和回收操作，并且算法的性能良好。

尽管首次适应算法在分配过程中可能会产生碎片，但是由于它从低地址开始，可以在较短的时间内找到满足需求的空闲块。

在实际应用中，首次适应算法被广泛采用。

2.最佳适应算法经过测试，最佳适应算法能够正确地进行内存的分配和回收操作，并且算法的性能较好。

最佳适应算法会整个内存空间，找到大小最小的满足需求的空闲块。

因此，在分配过程中不会产生很多的碎片，但是算法的执行时间较长。

四、实验总结通过本次实验，我们成功地实现了首次适应算法和最佳适应算法，并对算法的正确性和性能进行了验证。

两种算法在内存的分配和回收过程中都表现出良好的性能，可广泛应用于实际场景中。