下载文档原格式
用首次适应算法实现内存分配与回收首次适应算法（First Fit）是一种常用的内存分配算法，它将内存分为若干个大小相等的块，并按顺序进行分配。
当有一个进程请求内存时，首次适应算法从头开始，找到第一个大小能够满足这个进程需要的空闲块，将其分配给该进程。
以下是使用首次适应算法实现内存分配与回收的一种简单示例：1.假设整个内存大小为M字节，每个块的大小为N字节，内存被分为M/N个块。
2. 定义一个长度为(M/N)的布尔数组block，表示每个块的分配状态，初始时所有元素都为false，表示空闲状态。
3. 当一个进程请求分配S字节的内存时，首次适应算法从第一个块开始遍历数组block，直到找到一个大小大于等于S的空闲块。
4. 如果找到了合适的空闲块，将该块标记为已分配（设置为true），并返回该块的起始地址；否则，返回分配失败的标识。
5. 当一个进程释放已分配的内存时，可以根据该内存的起始地址计算出对应的块索引，将对应的block元素设置为false，表示该块变为空闲状态。
以下是一个简单的C++代码示例，演示了使用首次适应算法进行内存分配与回收的实现：```cpp#include <iostream>using namespace std;const int M = 1000; // 总内存大小const int N = 100; // 块大小bool block[M/N] = { false }; // 内存块分配状态//首次适应内存分配算法int allocateMemory(int size)int numBlocks = M / N; // 块数量int numNeeded = size / N;if (size % N != 0)numNeeded++;}for (int i = 0; i < numBlocks; i++)bool found = true;for (int j = i; j < i + numNeeded; j++)if (j >= numBlocks ， block[j] == true)found = false;break;}}if (found)for (int j = i; j < i + numNeeded; j++)block[j] = true;}return i * N;}}return -1; // 分配失败//内存回收void deallocateMemory(int startAddr, int size)int startIndex = startAddr / N;int numBlocks = size / N;if (size % N != 0)numBlocks++;}for (int i = startIndex; i < startIndex + numBlocks; i++) block[i] = false;}int maiint size1 = 200; // 请求200字节内存int size2 = 300; // 请求300字节内存int addr1 = allocateMemory(size1);int addr2 = allocateMemory(size2);if (addr1 != -1)cout << "分配内存成功，起始地址：" << addr1 << endl; } elsecout << "分配内存失败" << endl;}if (addr2 != -1)cout << "分配内存成功，起始地址：" << addr2 << endl; } elsecout << "分配内存失败" << endl;}deallocateMemory(addr1, size1);deallocateMemory(addr2, size2);return 0;```这段代码实现了一个简单的内存分配与回收示例。
操作系统实验报告完成日期：2011-12-5用首次适应算法模拟内存的分配和回收一、实验目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。
本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。
在熟练掌握计算机分区存储管理方式的原理的基础上，编程模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
二、实验内容与数据结构：(1)可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调整的。
当需要装入一个作业时，根据作业需要的贮存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。
随着作业的装入、完成，主存空间被分割成许多大大小小的分区。
有的分区被分配作业占用，有的分区空闲，例如，某时刻主存空间占用情况如图所示：为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如下图所示。
(2)当有一个新作业要求装入贮存时，必须查空闲区说明表，从中找出一个足够大的空闲区。
有时找到的空闲区可能大于作业的需求量，这时应将空闲区一分为二。
一个分给作业，另一个仍作为空闲区留在空闲区表中。
为了尽量减少由于分割造成的碎片，尽可能分配地地址部分的空闲区，将较大的空闲区留在高地址端，以利于大作业的装入。
为此在空闲区表中，按空闲区首地址从低到高进行登记。
(3)当一个作业执行完成时，作业所占用的分区应归还给系统。
在归还时，要考虑相邻空间区合并问题。
作业的释放区与空闲区的邻接分以下4种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空闲区不邻接；二、实验要求1.内存大小初始化2.可以对内存区进行动态分配，采用首次适应算法来实现3.可以对已分配的内存块进行回收，并合并相邻的空闲内存块。
第1篇一、实验目的1. 理解操作系统内存分配的基本原理和常用算法。
2. 掌握动态分区分配方式中的数据结构和分配算法。
3. 通过编写程序，实现内存分配和回收功能。
二、实验环境1. 操作系统：Linux2. 编程语言：C语言3. 开发工具：GCC编译器三、实验原理1. 内存分配的基本原理操作系统内存分配是指操作系统根据程序运行需要，将物理内存分配给程序使用的过程。
内存分配算法主要包括以下几种：（1）首次适应算法（First Fit）：从内存空间首部开始查找，找到第一个满足条件的空闲区域进行分配。
（2）最佳适应算法（Best Fit）：在所有满足条件的空闲区域中，选择最小的空闲区域进行分配。
（3）最坏适应算法（Worst Fit）：在所有满足条件的空闲区域中，选择最大的空闲区域进行分配。
2. 动态分区分配方式动态分区分配方式是指操作系统在程序运行过程中，根据需要动态地分配和回收内存空间。
动态分区分配方式包括以下几种：（1）固定分区分配：将内存划分为若干个固定大小的分区，程序运行时按需分配分区。
（2）可变分区分配：根据程序大小动态分配分区，分区大小可变。
（3）分页分配：将内存划分为若干个固定大小的页，程序运行时按需分配页。
四、实验内容1. 实现首次适应算法（1）创建空闲分区链表，记录空闲分区信息，包括分区起始地址、分区大小等。
（2）编写分配函数，实现首次适应算法，根据程序大小查找空闲分区，分配内存。
（3）编写回收函数，回收程序所占用的内存空间，更新空闲分区链表。
2. 实现最佳适应算法（1）创建空闲分区链表，记录空闲分区信息。
（2）编写分配函数，实现最佳适应算法，根据程序大小查找最佳空闲分区，分配内存。
（3）编写回收函数，回收程序所占用的内存空间，更新空闲分区链表。
3. 实验结果分析（1）通过实验，验证首次适应算法和最佳适应算法的正确性。
（2）对比两种算法在内存分配效率、外部碎片等方面的差异。
五、实验步骤1. 创建一个动态内存分配模拟程序，包括空闲分区链表、分配函数和回收函数。
南通大学操作系统实验课实验报告学生姓名所在院系专业学号指导教师南通大学2014年 5 月 16 日主存空间的分配与回收——首次适应法一、实验目的主存是中央处理机能直接存取指令和数据的存储器，能否合理而有效地使用它，在很大程度上将影响整个计算机系统的性能。
本实验主要熟悉主存的管理方法以及相应的分配与回收算法。
所谓分配，就是解决多道程序或多进程如何共享主存空间的问题，以便各个进程能获得所希望的主存空间，正确运行。
所谓回收，就是当进程运行完成时，将其所占用的主存空间归还给系统。
二、实验要求采用空闲区链法管理空闲区，并增加已分配区表。
分配算法采用首次适应法。
三、设计思路：（1）采用空闲区链法管理空闲区，并增加已分配区表。
分配算法采用首次适应法（内存空闲区的地址按照从小到大的自然顺序排列），实现内存的分配与回收。
（2）设计一个进程申请序列以及进程完成后的释放顺序，实现主存的分配与回收。
（3）进行分配时应该考虑这样3种情况：进程申请的空间小于、等于或大于系统空闲区的大小。
回收时应该考虑这样4种情况：释放区上邻、下邻、上下都邻和都不邻接空闲区。
（4）每次的分配与回收都要求把记录内存使用情况的各种数据结构的变化情况以及各进程的申请、释放情况显示出来。
四、主要思想（1）输入主存空间的最大长度n创建最大长度总和为n的若干空闲区的主存空闲区链；（2）输入待存作业的长度x，从链头开始找第一个合适作业的空闲区：分区长度小于x时，指针后移，继续寻找；分区长度等于x时，分配空间，修改作业分区；分区长度大于x 时，分配空间，修改分区数据。
五、流程图1.空闲区链的首次适应算法分配流程图2.空闲区链的首次适应算法回收流程图六、调试结果1.内存的分配2.内存的回收3.内存清空七、总结与感悟说实话我操作系统学得不是很好，一开始看到题目觉得自己要完成这个实验有些难度。
好在老师提醒书上有另一道类似题目的程序代码，另外书上也有首次适应法的流程图，可以给我们一些提示。
实验四操作系统存储管理实验报告一、实验目的本次实验的主要目的是深入理解操作系统中存储管理的基本原理和方法，通过实际操作和观察，掌握内存分配与回收、页面置换算法等关键概念，并能够分析和解决存储管理中可能出现的问题。
二、实验环境本次实验在装有 Windows 操作系统的计算机上进行，使用了 Visual Studio 等编程工具和相关的调试环境。
三、实验内容（一）内存分配与回收算法实现1、首次适应算法首次适应算法从内存的起始位置开始查找，找到第一个能够满足需求的空闲分区进行分配。
在实现过程中，我们通过建立一个空闲分区链表来管理内存空间，每次分配时从表头开始查找。
2、最佳适应算法最佳适应算法会选择能够满足需求且大小最小的空闲分区进行分配。
为了实现该算法，在空闲分区链表中，分区按照大小从小到大的顺序排列，这样在查找时能够快速找到最合适的分区。
3、最坏适应算法最坏适应算法则选择最大的空闲分区进行分配。
同样通过对空闲分区链表的排序和查找来实现。
（二）页面置换算法模拟1、先进先出（FIFO）页面置换算法FIFO 算法按照页面进入内存的先后顺序进行置换，即先进入内存的页面先被置换出去。
在模拟过程中，使用一个队列来记录页面的进入顺序。
2、最近最久未使用（LRU）页面置换算法LRU 算法根据页面最近被使用的时间来决定置换顺序，最近最久未使用的页面将被置换。
通过为每个页面设置一个时间戳来记录其最近使用的时间，从而实现置换策略。
3、时钟（Clock）页面置换算法Clock 算法使用一个环形链表来模拟内存中的页面，通过指针的移动和页面的访问标志来决定置换页面。
四、实验步骤（一）内存分配与回收算法的实现步骤1、初始化内存空间，创建空闲分区链表，并为每个分区设置起始地址、大小和状态等信息。
2、对于首次适应算法，从链表表头开始遍历，找到第一个大小满足需求的空闲分区，进行分配，并修改分区的状态和大小。
3、对于最佳适应算法，在遍历链表时，选择大小最接近需求的空闲分区进行分配，并对链表进行相应的调整。
实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。
【实验原理】首次适应（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：。
一、实验目的通过本次实验，加深对内存分配与回收机制的理解，掌握内存分配算法和回收策略，并能够运用所学知识解决实际内存管理问题。
二、实验内容1. 确定内存空间分配表；2. 采用首次适应算法实现内存分配；3. 采用最佳适应算法实现内存分配；4. 采用最坏适应算法实现内存分配；5. 实现内存回收功能；6. 对比分析不同内存分配算法的优缺点。
三、实验步骤1. 创建一个内存空间模拟程序，用于演示内存分配与回收过程；2. 定义内存空间分配表，记录内存块的起始地址、大小和状态（空闲或占用）；3. 实现首次适应算法，在内存空间分配表中查找第一个满足条件的空闲内存块，分配给请求者；4. 实现最佳适应算法，在内存空间分配表中查找最接近请求大小的空闲内存块，分配给请求者；5. 实现最坏适应算法，在内存空间分配表中查找最大的空闲内存块，分配给请求者；6. 实现内存回收功能，当内存块释放时，将其状态更新为空闲，并合并相邻的空闲内存块；7. 对比分析不同内存分配算法的优缺点，包括分配时间、内存碎片和内存利用率等方面。
四、实验结果与分析1. 首次适应算法：该算法按照内存空间分配表的顺序查找空闲内存块，优点是分配速度快，缺点是容易产生内存碎片，且内存利用率较低；2. 最佳适应算法：该算法查找最接近请求大小的空闲内存块，优点是内存利用率较高，缺点是分配速度较慢，且内存碎片较多；3. 最坏适应算法：该算法查找最大的空闲内存块，优点是内存利用率较高，缺点是分配速度较慢，且内存碎片较多。
五、实验结论通过本次实验，我们掌握了内存分配与回收的基本原理和算法，了解了不同内存分配算法的优缺点。
在实际应用中，我们需要根据具体需求选择合适的内存分配算法，以优化内存管理，提高系统性能。
六、实验心得1. 内存分配与回收是计算机系统中重要的组成部分，对系统性能有着重要影响；2. 熟练掌握内存分配算法和回收策略，有助于解决实际内存管理问题；3. 在实际应用中，应根据具体需求选择合适的内存分配算法，以优化内存管理，提高系统性能。
操作系统实验报告三存储器管理实验操作系统实验报告三：存储器管理实验一、实验目的本次存储器管理实验的主要目的是深入理解操作系统中存储器管理的基本原理和方法，通过实际操作和观察，掌握内存分配与回收的算法，以及页面置换算法的工作过程和性能特点，从而提高对操作系统资源管理的认识和实践能力。
二、实验环境本次实验使用的操作系统为 Windows 10，编程语言为 C+＋，开发工具为 Visual Studio 2019。
三、实验内容1、内存分配与回收算法实现首次适应算法（First Fit）最佳适应算法（Best Fit）最坏适应算法（Worst Fit）2、页面置换算法模拟先进先出页面置换算法（FIFO）最近最久未使用页面置换算法（LRU）时钟页面置换算法（Clock）四、实验原理1、内存分配与回收算法首次适应算法：从内存的起始位置开始，依次查找空闲分区，将第一个能够满足需求的空闲分区分配给进程。
最佳适应算法：在所有空闲分区中，选择能够满足需求且大小最小的空闲分区进行分配。
最坏适应算法：选择空闲分区中最大的分区进行分配。
2、页面置换算法先进先出页面置换算法：选择最早进入内存的页面进行置换。
最近最久未使用页面置换算法：选择最近最长时间未被访问的页面进行置换。
时钟页面置换算法：给每个页面设置一个访问位，在页面置换时，从指针指向的页面开始扫描，选择第一个访问位为0 的页面进行置换。
五、实验步骤1、内存分配与回收算法实现定义内存分区结构体，包括分区起始地址、大小、是否已分配等信息。
实现首次适应算法、最佳适应算法和最坏适应算法的函数。
编写测试程序，创建多个进程，并使用不同的算法为其分配内存，观察内存分配情况和空闲分区的变化。
2、页面置换算法模拟定义页面结构体，包括页面号、访问位等信息。
实现先进先出页面置换算法、最近最久未使用页面置换算法和时钟页面置换算法的函数。
编写测试程序，模拟页面的调入和调出过程，计算不同算法下的缺页率，比较算法的性能。
代码实现如下：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define n 64 //定义内存的大小int a[n],count=0;//数组a用来保存内存使用状况1为已分配0为未分配，count用来记name数组中元素个数char name[n];//已分配内存的名称（字符类型）typedef struct linknode{char pid;int start;int length;struct linknode *left,*right;}de_node; //进程节点结构体定义//head1表示未分配内存队列头指针，head2便是已分配进程队列头指针de_node *head1,*head2=NULL;struct linknode* creat()//创建一个进程节点{int len,flag1=1;//用于表示进程是否可以创建char id;struct linknode* p;p = (de_node *)malloc(sizeof(de_node));//试图在系统内存中开辟空间创建一个进程if (p==NULL) //p为空，说明系统没有可用内存用于创建此模拟进程{ printf("系统没有足够的内存可供使用！\n");//输出return(NULL);//返回空指针}printf("请输入进程id(字符类型)和长度:");//为进程输入id和分配的长度scanf("%c %d",&id,&len);fflush(stdin);//清除输入缓存if((id>='a'&&id<='z'||id>='A'&&id<='Z')&&(len>0)){for(int i=0;i<count;i++)//判断输入的进程名，如果已使用，返回空指针，并释放p指针if(name[i]==id){printf("此名称进程已存在！！");flag1=0;//标志位为0，表示下面对p指向内容不做修改free(p);return NULL;}if(len==0) {//如果输入要分配的进程长度为0，释放p,返回空指针printf("输入长度为0！\n");free(p);return(NULL);}if(flag1){//标志位1，可以对p指向内容进行修改p->pid=id; //idp->start=0; //初始开始内存位置，在以后会修改p->length=len;//长度p->left=NULL;//左指针p->right=NULL;//右指针name[count++]=id;//将id存入数组，count自加return(p);}//返回创建的进程的地址}else {printf("输入进程格式有误\n");free(p);return (NULL);}}//分配内存空间void distribute(de_node *p){ de_node *q=head1,*temp;int flag=0;do{//do_while循法//判断当前指向的内存空间的长度是否满足p所申请的长度,大于就分配if(q->length>=p->length) {p->start=q->start;//把进程的内存开始地址指向内存的可用开始地址处q->start+=p->length;//可用地址起始改变q->length-=p->length;//可用内存长度修改for(int i=p->start;i<p->start+p->length;i++)//将已分配的内存空间全部置1 a[i]=1;flag=1;//表示内存可分配//队列不止一个进程，第一个满足条件，并且刚好分配完，修改指针指向if(q->length==0&&q->right!=q) { if(q==head1)//如果第一个满足，修改头指针指向head1=q->right;q->left->right=q->right;q->right->left=q->left;free(q);//把这个已分配完的空间指针释放}}if(flag==1)//已做完处理直接跳出循环break;if(flag==0)//当前指向的内存不满足，指向下一个，继续判断是否满足q=q->right;}while(q!=head1);//搜索一遍可用内存序列if(flag==0){//没有可用的内存printf("没有满足的内存！\n");count--;//由于创建时加1，但在分配内存时失败，把1又减掉free(p);//把这个未分配到内存的进程释放}if(flag==1){//表示上面已分配好内存，并已修改内存链表，下面修改已分配内存的进程队列temp=head2;//把已分配内存的进程队列赋值给临时指针if(temp==NULL)//如果还还没有存在的任何的进程，说明当前是第一个{ head2=p;//让头指针指向第一个进程p->left=p;//双向队列第一个左右指针都指向自己p->right=p;//双向队列第一个左右指针都指向自己}else if(temp!=NULL){//已存在队列，把当前直接链到第一个，与上面的区别是指针指向head2=p;//让头指针指向p指向的进程p->left=temp->left;//p进程左边为原来第一个的左边p->right=temp;//p进程右边指向第一个temp->left->right=p;//原来第一个的左边为ptemp->left=p;//原来第一个的左边的进程为p}}}//对进程的回收void reclaim(){ char id;int flag=0;de_node *q=head2,*p=head1;if(head2==NULL)//表示当前没有进程{ printf("已没有进程！\n");}else {//已分配内存队列如果不为空printf("输入要回收的进程id：");//输入要回收进程的idscanf("%c",&id);fflush(stdin);for(int i=0;i<count;i++)//双重循环把要回收的进程找出来，并把记录的id去掉if(name[i]==id){//判断当前的进程是否满足要求for(int j=i;j<count;j++)name[j]=name[j+1];//向前覆盖name[j+1]=NULL;//置空count--;//减一}//判断是否总共只有一个进程且是够刚好也满足条件if(q->pid==id&&q->right==q&&head2==q){ head2=NULL;//把已分配队列直接置空flag=1;//表示找到满足条件的进程}if(flag==0){//上面的都没找到do{if(q->pid==id){//如果找到if(q==head2)head2=q->right;q->left->right=q->right;//修改指针指向q->right->left=q->left;flag=1;break;}else q=q->right;}while(q!=head2);}//如果找到或是遍历一遍结束if(flag==0) printf("没有此进程号！！！\n");//没有找到满足的进程if(flag==1){//表示找到了for(int i=q->start;i<q->start+q->length;i++)//释放占有的内存a[i]=0;//接下来修改可用内存的队列，while(q->start>p->start&&p->right!=head1){//从第一个开始找到回收回来的内存开始地址大的那个队列p=p->right;}if(p==head1)//表示比第一个的开始还小，那么就要修改头地址head1=q;//其他情况不用修改头地址，只需找到应该的位置，把此进程插进去q->left=p->left;//修改指针的指向q->right=p;p->left->right=q;p->left=q;if(q->start+q->length==p->start)//可以与后面合并的情况{ q->length+=p->length;//修改指针的指向p->right->left=q;q->right=p->right;free(p);}if(q->left->start+q->left->length==q->start)//可以与前面合并的情况{ q->left->length+=q->length;//修改指针的指向q->left->right=q->right;q->right->left=q->left;free(q);}}}}//打印输出void print(){ de_node *q=head2,*p=head1;if(count==0)printf("没有进程占有内存。
\n");else{ printf("输出进程id号：\n");for(int i=0;i<count;i++)printf("%c\t",name[i]);}printf("\n");printf("输出内存当前使用情况：\n");for(int j=0;j<n;j++)printf("%d %d\t",j,a[j]);printf("\n");printf("内存初始名称为i,回收后可能会变，可以查看回收来自那个进程\n");do //输出可用内存序列{ if(p!=NULL){ printf("进程id:%c 开始地址:%d 长度%d\n",p->pid,p->start,p->length);p=p->right;}}while(p!=head1);printf("\n");printf("已分配进程队列：\n");do //已分配进程队列{if(q!=NULL){printf("进程id:%c 开始地址:%d 长度%d\n",q->pid,q->start,q->length);q=q->right;}}while(q!=head2);}//主函数void main(){ int x;de_node *point,*p1;//创建内存的初始状态point=(struct linknode*)malloc(sizeof(struct linknode)); head1=point;point->pid='i';point->start=0;point->length=n;head1->left=point;head1->right=point;print();while(1){printf(" ------MENU-------\n");printf("1----distribute(分配)\n");printf("2----reclaim(回收)\n");printf("3----view (浏览)\n");printf("4----exit(退出)\n");printf("请输入上面的选项(1--4):\n");scanf("%d",&x);fflush(stdin);switch(x){case 1:{ p1=creat();if(p1==NULL) printf("创建进程失败。
