操作系统实验_首次适应算法与循环首次适应算法

操作系统的内存分配算法操作系统的内存管理是计算机系统中一个重要的组成部分。

内存分配算法决定了如何合理地利用系统的内存资源，以达到高效、安全、稳定的运行。

本文将介绍几种常见的内存分配算法，包括首次适应算法、循环首次适应算法、最佳适应算法以及快速适应算法。

首次适应算法（First Fit Algorithm）首次适应算法是一种简单而常见的内存分配算法。

它从内存空闲列表的头部开始寻找第一个适合分配的内存块。

当找到满足要求的内存块后，将该块划分为两部分，一部分用于分配给请求的程序，另一部分保留为剩余空闲块。

这种算法的优点是分配速度较快，缺点是可能会导致内存碎片的产生。

循环首次适应算法（Next Fit Algorithm）循环首次适应算法是首次适应算法的一种改进版本。

与首次适应算法不同的是，循环首次适应算法从上一次分配的位置开始搜索空闲块，直到找到一个满足要求的内存块为止。

这样可以避免每次都从头开始搜索，提高了查找的效率。

同样，这种算法也可能导致内存碎片的产生。

最佳适应算法（Best Fit Algorithm）最佳适应算法是为了解决内存碎片问题而提出的一种分配算法。

该算法会在内存空闲列表中查找最小且能满足要求的空闲块，并将该块分配给请求的程序。

这样可以尽量充分利用内存资源，减少内存碎片的产生。

但是，最佳适应算法的缺点是分配速度相对较慢，因为需要遍历整个内存空闲列表。

快速适应算法（Quick Fit Algorithm）快速适应算法是一种综合了首次适应算法和最佳适应算法的策略。

它将内存空闲列表分成了多个不同大小的链表，每个链表分别存储相应大小的空闲块。

当有程序请求内存时，快速适应算法会直接从对应大小的链表中查找可用的空闲块进行分配，以提高分配的速度。

这个算法在时间效率和空间效率上都较为出色，但是需要付出额外的存储开销。

总结不同的内存分配算法各有优缺点，选择合适的算法取决于具体的应用场景和系统需求。

首次适应算法和循环首次适应算法适用于内存分配需求频繁变化的场景。

首次适应算法最佳适应算法最坏适应算法首次适应算法（First Fit Algorithm）是一种常见的内存分配算法，用于管理计算机的物理内存。

它的核心思想是将内存按照从低地址到高地址的顺序进行划分，每次分配内存时从低地址开始，找到第一个足够大的空闲块来满足需求。

首次适应算法的实现相对简单，它只需要维护一个空闲内存块链表，其中存储了空闲块的起始地址和大小。

当需要分配一块内存时，首次适应算法会遍历链表，找到第一个大小足够的空闲块并将其划分为两部分：一部分用于分配，另一部分作为一个新的空闲块。

同样，当需要释放一块已分配的内存时，首次适应算法会查找内存中是否存在相邻的空闲块，若有则合并。

首次适应算法的优点是简单、高效，分配内存的时间复杂度为O(n)，其中n是空闲内存块的数量。

然而，首次适应算法也存在一些问题。

首先，它可能会导致内存碎片的产生。

当分配的内存大小比较小且频繁时，会导致大量的小块空闲内存，造成内存碎片化。

其次，由于首次适应算法是按顺序空闲块来找到最适合的块，因此可能会导致较大的块被拆分成多个小块，从而降低内存的利用率。

最佳适应算法（Best Fit Algorithm）是一种改进的内存分配算法，旨在解决首次适应算法中存在的问题。

最佳适应算法的核心思想是在每次分配内存时，选择最小的能满足需求的空闲块。

最佳适应算法的实现与首次适应算法类似，但不同之处在于它需要在遍历空闲块链表时记录下最小的满足条件的块。

当找到最小的空闲块后，将其划分为分配块和新的空闲块。

最佳适应算法的优点是减少了内存碎片的产生。

通过选择最小的能满足需求的空闲块，可以更好地利用内存。

然而，最佳适应算法的缺点是实现复杂度较高。

由于需要在空闲块链表中查找最小的块，分配内存的时间复杂度为O(n)，其中n是空闲内存块的数量。

最坏适应算法（Worst Fit Algorithm）是一种与最佳适应算法相反的内存分配算法。

它的核心思想是在每次分配内存时，选择最大的能满足需求的空闲块。

首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法是关于操作系统内存管理中内存分配策略的四种典型算法。

以下是对它们的简要解释：1. 首次适应算法（First-fit）：在内存分配时，首次适应算法从内存区域的起始部分开始搜索，找到第一个能满足请求大小的空闲内存块，并将其分配给请求者。

首次适应算法的优点是分配速度较快，但可能导致内存空间碎片化。

2. 循环首次适应算法（Next-fit）：循环首次适应算法类似于首次适应算法，但它在内存分配时保留上一次搜索的位置。

下一次分配时，算法将从上次停止的位置开始搜索，直到找到合适的空闲内存块或返回到起始位置。

这种方法可以在整个内存空间中分散分配过程，进一步改善内存碎片化问题。

3. 最佳适应算法（Best-fit）：最佳适应算法在分配内存时，会查找所有可用的空闲内存块，并分配能够最紧密地满足请求大小的内存块。

该策略试图使分配后的剩余空间尽量小，以减少内存浪费。

然而，最佳适应算法通常需要更多的搜索时间，并可能导致过多的小内存碎片。

4. 最坏适应算法（Worst-fit）：最坏适应算法与最佳适应算法相反，它在分配内存时选择最大的可用内存块。

这种策略试图保持较大的连续空闲内存块，以便满足大型请求。

然而，最坏适应算法可能导致大量空间浪费，并需要较长的搜索时间。

这些内存分配算法都有各自的优缺点。

在实际的操作系统实现中，可能会根据需求和上下文使用多种算法的组合来优化内存管理。

实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。

【实验原理】首次适应（first fit，FF）算法FF算法要求空闲分区链以地址递增的次序链接。

在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区即可。

然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。

若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。

循环首次适应（next fit，NF）算法为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。

【实验内容】实现主存空间的分配与回收：1.采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收；2.采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回收。

数据结构和符号说明：typedef struct PCB//进程控制块{char ProgressName[10]; //进程名称int Startaddress; //进程开始地址int ProgressSize; //进程大小int ProgressState = 0; //进程状态};typedef struct FREE //空闲区结构体{int Free_num; //空闲区名称int Startaddress; //空闲区开始地址int Endaddress; //空闲区结束地址int Free_Space; //空闲区大小};算法流程图：首次适应算法循环首次适应算法程序代码及截图：主界面：首次适应算法，初始空闲区：插入进程：插入3个进程：空闲区信息：删除进程2：删除后空闲区状况：再插入一个进程，可以看到其其初始地址为100：循环首次适应算法,插入3个进程删除进程2后：再插入进程A，发现其从上次找到的空闲分区的下一个空闲分区开始查找，其初始地址为750而不是200：。

实验四实验报告【实验题目】：动态分区分配算法【实验目的】通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。

【实验内容】问题描述：设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。

假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, …,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。

程序要求如下：1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。

2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。

3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。

4）输出：最终内存空闲分区的分配情况。

实现提示：用C++语言实现提示：1）程序中变量定义参考（根据需要可添加）如下：const int MaxNumber=100;int FreePartition[MaxNumber];int FirstPartition[MaxNumber];int CycleFirstPartition[MaxNumber];int BestPartition[MaxNumber];int WorstPartition[MaxNumber];int ProcessNeed[MaxNumber];int PartitionNum,ProcessNum;2）页面置换的实现过程如下：变量初始化；空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法；根据用户选择的算法进行动态分区分配；输出所有进程分配后的空闲分区分配情况。

操作系统实验报告三存储器管理实验操作系统实验报告三：存储器管理实验一、实验目的本次存储器管理实验的主要目的是深入理解操作系统中存储器管理的基本原理和方法，通过实际操作和观察，掌握内存分配与回收的算法，以及页面置换算法的工作过程和性能特点，从而提高对操作系统资源管理的认识和实践能力。

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

三、实验内容1、内存分配与回收算法实现首次适应算法（First Fit）最佳适应算法（Best Fit）最坏适应算法（Worst Fit）2、页面置换算法模拟先进先出页面置换算法（FIFO）最近最久未使用页面置换算法（LRU）时钟页面置换算法（Clock）四、实验原理1、内存分配与回收算法首次适应算法：从内存的起始位置开始，依次查找空闲分区，将第一个能够满足需求的空闲分区分配给进程。

最佳适应算法：在所有空闲分区中，选择能够满足需求且大小最小的空闲分区进行分配。

最坏适应算法：选择空闲分区中最大的分区进行分配。

2、页面置换算法先进先出页面置换算法：选择最早进入内存的页面进行置换。

最近最久未使用页面置换算法：选择最近最长时间未被访问的页面进行置换。

时钟页面置换算法：给每个页面设置一个访问位，在页面置换时，从指针指向的页面开始扫描，选择第一个访问位为0 的页面进行置换。

五、实验步骤1、内存分配与回收算法实现定义内存分区结构体，包括分区起始地址、大小、是否已分配等信息。

实现首次适应算法、最佳适应算法和最坏适应算法的函数。

编写测试程序，创建多个进程，并使用不同的算法为其分配内存，观察内存分配情况和空闲分区的变化。

2、页面置换算法模拟定义页面结构体，包括页面号、访问位等信息。

实现先进先出页面置换算法、最近最久未使用页面置换算法和时钟页面置换算法的函数。

编写测试程序，模拟页面的调入和调出过程，计算不同算法下的缺页率，比较算法的性能。

首次适应算法实验报告引言首次适应算法（First Fit）是一种内存分配算法，用于解决操作系统中的内存管理问题。

在该算法中，操作系统将可用的内存空间分为若干个大小不等的分区，当一个新的作业需要分配内存时，算法通过在空闲分区列表中查找第一个能够满足作业大小的分区，找到第一个合适的位置将作业分配到该分区。

本次实验旨在通过调试和运行一个模拟的内存管理系统，了解首次适应算法的实现原理，并比较它与其他内存分配算法的性能差异。

实验环境- 操作系统：Windows 10- 开发语言：C++实验步骤和结果分析1. 设计数据结构我们首先设计了一个表示内存分区的数据结构`Partition`，包括以下成员变量：- `start`：表示分区的起始地址- `size`：表示分区的大小- `allocated`：表示分区是否已经分配给作业然后，我们设计了一个表示内存管理系统的数据结构`Memory`，包括以下成员变量：- `partitions`：表示分区列表，使用一个动态数组存储所有分区- `size`：表示内存总大小2. 实现首次适应算法在内存管理系统的实现中，我们通过设计一个`allocate`方法来实现首次适应算法的分配过程。

该方法接受一个作业的大小作为参数，返回一个指向分配的分区的指针。

如果找不到合适的分区，则返回`nullptr`。

首次适应算法的实现原理如下：- 遍历所有的分区，查找第一个未分配且大小大于作业大小的分区。

- 如果找到合适的分区，则将分区的`allocated`属性设置为`true`，表示已分配，并返回该分区的指针。

- 如果没有找到合适的分区，则返回`nullptr`。

3. 测试并分析结果在测试阶段，我们通过运行一系列的分配和释放操作来模拟作业的动态运行过程。

为了更好地观察内存的分配情况，我们将内存分为等大小的分区，并以图表的方式显示。

通过对不同大小的作业进行分配和释放测试，我们得到了如下结果：从上图可以看出，首次适应算法根据作业的大小选择不同的分区进行分配，确保了尽可能多地利用内存空间。

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

⼆、实验要求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、学会可变式分区管理的原理是即在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。

3、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区没有时应将空闲区一分为二。

为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。

4、当一个作业执行完成时，作业所占用的分区应归还给系统。

作业的释放区与空闲区的邻接分以下四种情况考虑：①释放区下邻（低地址邻接）空闲区；②释放区上邻（高地址邻接）空闲区③释放区上下都与空闲区邻接；④释放区与空闲区不邻接。

【实验内容】#include<stdio.h>#include<iostream>#include<string>using namespace std;const int MAXJOB=100;//定义表最大记录数typedef struct node{int front;int length;char data[20];}job;job frees[MAXJOB];//定义空闲区表int free_quantity;job occupys[MAXJOB];//定义已分配区表int occupy_quantity;//初始化函数void initial(){int i;for(i=0;i<MAXJOB;i++){frees[i].front=-1;frees[i].length=0;strcpy(frees[i].data,"free");occupys[i].front=-1;occupys[i].length=0;strcpy(occupys[i].data," ");}free_quantity=0;occupy_quantity=0;}//创建空闲分区表int creatfree(){FILE *fp;char fname[20];cout<<"请输入空闲区数据文件来源的文件名:"; cin>>fname;if((fp=fopen(fname,"r"))==NULL){cout<<"错误,文件打不开,请检查文件名"<<endl; }else{while(!feof(fp)){fscanf(fp,"%d\t%d\n",&frees[free_quanti ty].front,&frees[free_quantity].length);free_quantity++;}cout<<"空闲的分区表已建立！\n";return 1;}return 0;}void sort()//将free空间安首地址从小到大的顺序排列{int i,j,p;for(i=0;i<free_quantity-1;i++){p=i;for(j=i+1;j<free_quantity;j++){if(frees[j].front<frees[p].front){p=j;}}if(p!=i){frees[free_quantity]=frees[i];frees[i]=frees[p];frees[p]=frees[free_quantity];}}}//显示函数void show(){int i;cout<<endl<<"----------------------------------------------------------"<<endl;cout<<"当前空闲表:"<<endl;cout<<" 起始地址长度状态"<<endl;for(i=0;i<free_quantity;i++){cout.setf(2);cout.width(12);cout<<frees[i].front;cout.width(10);cout<<frees[i].length;cout.width(8);cout<<frees[i].data<<endl;}cout<<endl<<"----------------------------------------------------------"<<endl;cout<<"当前已分配表:"<<endl;cout<<" 起始地址长度占用作业名"<<endl;for(i=0;i<occupy_quantity;i++){cout.setf(2);cout.width(12);cout<<occupys[i].front;cout.width(10);cout<<occupys[i].length;cout.width(8);cout<<occupys[i].data<<endl;}cout<<endl<<"----------------------------------------------------------"<<endl;}//最先适应分配算法void assign(){char job_name[20];int job_length;int i,j,flag,t;cout<<"请输入新申请内存空间的作业名和空间大小:";cin>>job_name;cin>>job_length;flag=0;for(i=0;i<free_quantity;i++){if(frees[i].length>=job_length)//如果空闲空间I的长度〉作业长度{flag=1; //空闲标志位就置1 }}if(flag==0){cout<<endl<<"对不起,当前没有能满足你申请长度的空闲内存,请稍候再试！"<<endl;}else{t=0;i=0;while(t==0)//为空闲区间的时候{if(frees[i].length>=job_length){t=1;}i++;//如果空闲空间I的长度不大于作业长度，I加一，判断下一个空间}i--;occupys[occupy_quantity].front=frees[i] .front;strcpy(occupys[occupy_quantity].data,jo b_name);occupys[occupy_quantity].length=job_len gth;occupy_quantity++;if(frees[i].length>job_length)//如果空间的长度大于作业的长度，{frees[i].front+=job_length;frees[i].length-=job_length;}else{for(j=i;j<free_quantity-1;j++){frees[j]=frees[j+1];}free_quantity--;cout<<"内存空间成功:)"<<endl;}}}//撤消作业void cancel(){char job_name[20];int i,j,flag,p=0;int front;int length;cout<<"请输入要撤消的作业名:";cin>>job_name;flag=-1;for(i=0;i<occupy_quantity;i++){if(!strcmp(occupys[i].data,job_name))//当输入作业名匹配时{flag=i;front=occupys[i].front;length=occupys[i].length;}}if(flag==-1){cout<<"没有这个作业名"<<endl;}else{//加入空闲表for(i=0;i<free_quantity;i++){if((frees[i].front+frees[i].length)==fr ont)//上空{if(((i+1)<free_quantity)&&(frees[i+1].f ront==front+length))//下空{frees[i].length=frees[i].length+frees[i +1].length+length;for(j=i+1;j<free_quantity;j++){frees[j]=frees[j+1];}free_quantity--;p=1;}else{frees[i].length+=length;p=1;}}if(frees[i].front==(front+length))//下空上不空{frees[i].front=front;frees[i].length+=length;//第i 个空闲区间的长度=第i个空闲区间的长度+lengthp=1;}}if(p==0)//上下空闲区都不空{frees[free_quantity].front=front;frees[free_quantity].length=length;free_quantity++;}//删除分配表中的该作业for(i=flag;i<occupy_quantity;i++){occupys[i]=occupys[i+1];}occupy_quantity--;}}void main(){int flag=0;int t=1;int chioce=0;cout<<"*********** xxxxxxxxx***********\n"; initial();flag=creatfree();while(flag==1){sort();cout<<" 可变分区存储管理模拟系统"<<endl;cout<<" 1.申请空间 "<<endl;cout<<" 2.撤消作业 "<<endl;cout<<" 3.显示空闲表和分配表"<<endl;cout<<" 0.退出"<<endl;cout<<"请选择:";cin>>chioce;switch(chioce){case 1:assign();break;case 2:cancel();break;case 3:show();break;case 0:flag=0;break;default:cout<<"选择错误!"<<endl;}}}实验结果显示：【实验小结】本实验难度在两个方面，一是首次最佳适应算法assign()，这里我用的是结构体数组来存储空闲分区；二是对已分配分区的释放，这里同样采取结构体数组来存储已分配分区，用cancle（）函数来实现。

首次适应算法和循环首次适应算法一、实验目的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）和循环首次适应算法（Next Fit）。

首次适应算法（First Fit）是指在分配内存空间时，从内存空间的起始位置开始查找，找到第一个大小大于等于所需空间的空闲分区进行分配。

这种算法简单直观，但可能会导致碎片化问题，因为较小的空闲分区可能无法被充分利用。

最佳适应算法（Best Fit）则是在分配内存空间时，从所有满足大小要求的空闲分区中选择最小的一个进行分配。

这种算法可以最大限度地减少碎片化，但可能会导致空闲分区的搜索时间较长。

最差适应算法（Worst Fit）与最佳适应算法相反，它在分配内存空间时选择最大的满足大小要求的空闲分区进行分配。

这种算法可以减少外部碎片，但同样可能导致空闲分区的搜索时间较长。

循环首次适应算法（Next Fit）是首次适应算法的一种改进，它从上一次分配结束的位置开始查找下一个符合要求的空闲分区进行分配。

这种算法可以减少搜索时间，但可能会导致内存空间的不均匀利用。

这四种分区算法各有优缺点，选择合适的算法取决于具体的应用场景和需求。

在实际应用中，需要根据系统的特点和性能要求来选择合适的分区算法，以实现对存储空间的高效管理和利用。

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

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

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

原来则没有这⼀情况。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首次适应和循环首次适应算法模拟内存分配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;}。

临近适应算法和循环首次适应算法一、临近适应算法（Next Fit Algorithm）临近适应算法是根据空闲分区在分区链表中的位置来选择合适的空闲分区来分配请求的内存。

具体来说，当收到一个内存请求时，该算法会从上次分配的位置开始遍历空闲分区链表，找到第一个满足大小要求的空闲分区进行分配。

然而，临近适应算法也存在一些缺点。

首先，由于每次都从上次结束的位置开始遍历，造成了空闲分区链表的不均衡，可能导致部分内存碎片无法被合并。

其次，由于无法预测未来的内存请求情况，所以无法确保分配的空闲分区是最合适的，可能导致内存利用率低。

适用场景：临近适应算法适用于内存请求分布较为均匀的情况，且对内存利用率要求不高的场景。

比如，对于一些简单的嵌入式系统或小型应用，由于内存请求较少且分布较均匀，所以临近适应算法可以很好地满足需求。

二、循环首次适应算法（First Fit Algorithm）循环首次适应算法是按照空闲分区在分区链表中的顺序来选择合适的空闲分区进行内存分配。

具体来说，当收到一个内存请求时，该算法会从链表的头开始遍历，找到第一个满足大小要求的空闲分区进行分配。

循环首次适应算法的优点是容易理解和实现。

由于分配的分区总是从链表的头开始，因此可以尽可能提高内存利用率，并且不会造成太多的内存碎片。

然而，循环首次适应算法也存在一些缺点。

首先，由于分配的分区总是从链表的头开始，容易造成链表的前端产生大量的小空闲分区，导致内存的浪费。

其次，当有大内存请求到来时，可能无法找到足够大的空闲分区，从而导致内存分配失败。

适用场景：循环首次适应算法适用于内存请求分布较为不均匀的情况，且对内存碎片要求较高的场景。

比如，对于一些大型应用或服务器系统，由于内存请求较多且分布较不均匀，循环首次适应算法可以更好地满足需求。

综上所述，临近适应算法和循环首次适应算法都是常用的内存分配算法，适用于不同的场景。

临近适应算法适用于内存请求分布较为均匀、对内存利用率要求不高的场景，而循环首次适应算法适用于内存请求分布较为不均匀、对内存碎片要求较高的场景。

#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);}}。

首次适应算法实验报告操作操作系统大作业题目：首次适应算法分配内存学号：1207300142 学生姓名：张鲁云班级：计科121首次适应算法分配内存一、问题描述在内存分配中，动态分区是根据实际的进程需求，动态地为之分配空间。

而首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。

可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。

用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。

二、运行环境VC6.0三、算法思想。

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

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

若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败四、实验目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。

本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。

头结点的前驱指针指向空头结点的后继指针指向尾结点尾结点的前驱指针指向头结点 尾结点的后继指针指向空 尾结点的地址是 0 分区大小是最大分区 状态是空表示五、 首次适应算法分配内存 算法概要(1) 结构体Typedef struct freearea// 定义一个空闲区说明表结构 { long size; // 分区大小 long address; // 分区地址int state; // 状态}ElemType; // 线性表的双向链表存储结构Typedef struct DuLNode{ ElemType data;structDuLNode *prior; // 前趋指针structDuLNode *next; // 后继指针} DuLNode,*DuLinkList;Status Initblock(intMAX_length)// 开创带头结点的内存空间链表 { block_first=(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; }(2)主要函数说明：void alloc() ；进行内存分配的功能函数。