最佳适应算法-源程序代码

#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．磁盘管理功能题目二虚拟存储器各页面置换算法的实现与比较内容：设计一个虚拟存储区和内存工作区，通过产生一个随机数的方法得到一个页面序列，假设内存给定的页面数由键盘输入，分别计算使用下述各方法时的内存命中率：先进先出算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）、最少访问页面算法（LFU）等。

题目三文件系统设计通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能及内部实现。

内容：为Linux系统设计一个简单的二级文件系统，以实现下列功能：1．可以实现下列几条命令（1）login 用户登录（2）dir 文件目录列表（3）creat 创建文件（4）delete 删除文件（5）open 打开文件（6）close 关闭文件（7）read 读文件（8）write 写文件2．实验提示（1）首先确定文件系统的数据结构：主目录、子目录及活动文件等。

主目录和子目录都以文件的形式存放在磁盘，这样便于查找和修改。

（2）用户创建的文件，可以编号存储于磁盘上。

如file0、file1、file2……等，并以编号作为物理地址，在目录中进行登记。

[清华大学《操作系统教程》张丽芬编著题目四设计一个按时间片轮转法进程CPU调度的程序。

提示：（1）假设系统有5个进程，每个进程用一个进程控制块PCB来代表，PCB中包含进程名、链接指针、到达时间、估计运行时间、进程状态表。

其中，进程名即为进程进标识。

（2）为每一个进程设计一个要示运行时间和到达时间。

（3）按照进程到达的先后顺序排成一个循环队列，再设一个队首指针指向第一个到达的进程首址。

（4）执行处理机调度时，开始选择队首的第一个进程运行。

另外再设一个当前运行进程指针，指向当前正运行的进程。

（5）由于本实验是模拟实验，所以对被选中进程并不实际启运运行，只是执行：a.估计驼行时间减1b.输出当前运行进程的名字。

课程设计题目动态分区管理的主存分配模拟设计--最优适应法、最差适应法学院计算机科学与技术学院专业计算机科学与技术专业班级计算机1002班姓名刘浪浪指导教师杨克俭2013 年 1 月20 日课程设计任务书学生姓名：刘浪浪专业班级：计科1002班指导教师：杨克俭工作单位：计算机科学与技术学院题目: 动态分区管理的主存分配模拟设计--最优适应法、最差适应法初始条件：1．预备内容：阅读操作系统的内存管理章节内容，理解动态分区的思想，并体会各分配算法的具体实施方法。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．采用指定算法模拟动态分区管理方式的主存分配。

能够处理以下的情形：⑴随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。

内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。

时间安排：设计安排一周：周1、周2：完成程序分析及设计。

周2、周3：完成程序调试及测试。

周4、周5：验收、撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日一、题目动态分区管理的主存分配模拟设计--最优适应法、最差适应法二、主要任务1．采用指定算法模拟动态分区管理方式的主存分配。

实验题目：存储器内存分配设计思路：1.既然是要对内存进行操作，首先对和内存相关的内容进行设置我使用的是用自定义的数据结构struct来存放内存中一个内存块的内容包括：始地址、大小、状态（f:空闲u:使用e:结束）之后采用数组来存放自定义的数据类型，这样前期的准备工作就完成了2.有了要加工的数据，接下来定义并实现了存放自定义数据类型的数组的初始化函数和显示函数，需要显示的是每个内存块的块号、始地址、大小、状态3.接着依此定义三种动态分区分配算法首次适应算法、最佳适应算法和最差适应算法4.对定义的三种算法逐一进行实现①首次适应算法：通过遍历存放自定义数据类型的数组，找到遍历过程中第一个满足分配大小的内存块块号i，找到之后停止对数组的遍历，将i之后的块号逐个向后移动一个，然后将满足分配大小的内存块i分为两块，分别是第i块和第i+1块，将两块的始地址、大小、状态分别更新，这样便实现了首次适应算法②最佳适应算法：和首次适应算法一样，首先遍历存放自定义数据类型的数组，找到满足分配大小的内存块后，对内存块的大小进行缓存，因为最佳适应是要找到最接近要分配内存块大小的块，所以需要遍历整个数组，进而找到满足分配大小要求的而且碎片最小的块i，之后的操作和首次遍历算法相同③最差适应算法：和最佳适应算法一样，区别在于，最佳适应是找到最接近要分配内存块大小的块，而最差适应是要找到在数组中，内存最大的块i，找到之后的操作和最佳适应算法相同，因此不在这里赘述。

5.定义并实现释放内存的函数通过块号找到要释放的内存块，把要释放的内存块状态设置成为空闲，查看要释放的块的左右两侧块的状态是否为空闲，如果有空闲，则将空闲的块和要释放的块进行合并（通过改变块的始地址、大小、状态的方式）6.定义主函数，用switch来区分用户需要的操作，分别是：①首次适应②最佳适应③最差适应④释放内存⑤显示内存⑥退出系统实验源程序加注释：#include<bits/stdc++.h>#define MI_SIZE 100 //内存大小100typedef struct MemoryInfomation//一个内存块{int start; //始地址int Size; //大小char status; //状态 f:空闲 u:使用 e：结束} MI;MI MList[MI_SIZE];void InitMList() //初始化{int i;MI temp = { 0,0,'e' };for (i = 0; i < MI_SIZE; i++){MList[i] = temp;}MList[0].start = 0; //起始为0MList[0].Size = MI_SIZE;//大小起始最大MList[0].status = 'f'; //状态起始空闲}void Display() //显示{int i, used = 0;printf("\n---------------------------------------------------\n");printf("%5s%15s%15s%15s", "块号", "始地址", "大小", "状态");printf("\n---------------------------------------------------\n");for (i = 0; i < MI_SIZE && MList[i].status != 'e'; i++){if (MList[i].status == 'u'){used += MList[i].Size;}printf("%5d%15d%15d%15s\n", i, MList[i].start, MList[i].Size, MList[i].status == 'u' ? "使用" : "空闲");}printf("\n----------------------------------------------\n");}void FirstFit(){int i, j, flag = 0;int request;printf("最先适应算法：请问你要分配多大的内存\n");scanf("%d", &request);for (i = 0; i < MI_SIZE && MList[i].status != 'e'; i++){if (MList[i].Size >= request && MList[i].status == 'f') {if (MList[i].Size - request <= 0){MList[i].status = 'u';}else{for (j = MI_SIZE - 2; j > i; j--){MList[j + 1] = MList[j];}MList[i + 1].start = MList[i].start + request; MList[i + 1].Size = MList[i].Size - request;MList[i + 1].status = 'f';MList[i].Size = request;MList[i].status = 'u';flag = 1;}break;}}if (flag != 1 || i == MI_SIZE || MList[i].status == 'e'){printf("没有足够大小的空间分配\n");}Display();}void BadFit(){int i, j = 0, k = 0, flag = 0, request;printf("最坏适应算法：请问你要分配多大的内存\n");scanf("%d", &request);for (i = 0;i < MI_SIZE - 1 && MList[i].status != 'e';i++){if (MList[i].Size >= request && MList[i].status == 'f') {flag = 1;if (MList[i].Size > k){k = MList[i].Size;j = i;}}}i = j;if (flag == 0){printf("没有足够大小的空间分配\n");j = i;}else if (MList[i].Size - request <= 0){MList[i].status = 'u';}else{for (j = MI_SIZE - 2;j > i;j--){MList[j + 1] = MList[j];}MList[i + 1].start = MList[i].start + request;MList[i + 1].Size = MList[i].Size - request;MList[i + 1].status = 'f';MList[i].Size = request;MList[i].status = 'u';}Display();}void M_Release() //释放内存{int i, number;printf("\n请问你要释放哪一块内存:\n");scanf("%d", &number);if (MList[number].status == 'u'){MList[number].status = 'f';if (MList[number + 1].status == 'f')//右边空则合并{MList[number].Size += MList[number].Size;for (i = number + 1; i < MI_SIZE - 1 && MList[i].status != 'e'; i++) { //i后面的每一个结点整体后移if (i > 0){MList[i] = MList[i + 1];}}}if (number > 0 && MList[number - 1].status == 'f')//左边空则合并{MList[number - 1].Size += MList[number].Size;for (i = number; i < MI_SIZE - 1 && MList[i].status != 'e'; i++){MList[i] = MList[i + 1];}}}else{printf("该块内存无法正常释放\n");}Display();}void BestFit(){int i, j = 0, t, flag = 0, request;printf("最佳适应算法：请问你要分配多大的内存\n");scanf("%d", &request);t = MI_SIZE;for (i = 0; i < MI_SIZE && MList[i].status != 'e'; i++){if (MList[i].Size >= request && MList[i].status == 'f'){flag = 1;if (MList[i].Size < t){t = MList[i].Size;j = i;}}}i = j;if (flag == 0){printf("没有足够大小的空间分配\n");j = i;}else if (MList[i].Size - request <= 0){MList[i].status = 'u';}else {for (j = MI_SIZE - 2; j > i; j--){MList[j + 1] = MList[j];}MList[i + 1].start = MList[i].start + request;MList[i + 1].Size = MList[i].Size - request;MList[i + 1].status = 'f';MList[i].Size = request;MList[i].status = 'u';}Display();}int main(){int x;InitMList();while (1){printf(" \n"); printf(" 1.首次适应\n");printf(" 2.最佳适应\n");printf(" 3.最差适应\n"); printf(" 4.释放内存\n"); printf(" 5.显示内存\n"); printf(" 6.退出系统\n"); printf("请输入1-6：");scanf("%d", &x);switch (x){case 1:FirstFit();break;case 2:BestFit();break;case 3:BadFit();break;case 4:M_Release();break;case 5:Display();break;case 6:exit(0);}}return 0;}实验测试结果记录：1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：1最先适应算法：请问你要分配多大的内存10---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 使用1 10 90 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：1最先适应算法：请问你要分配多大的内存25---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 使用1 10 25 使用2 35 65 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：1最先适应算法：请问你要分配多大的内存15---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 使用1 10 25 使用2 35 15 使用3 50 50 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：1最先适应算法：请问你要分配多大的内存20---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 使用1 10 25 使用2 35 15 使用3 50 20 使用4 70 30 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：4请问你要释放哪一块内存:---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 空闲1 10 25 使用2 35 15 使用3 50 20 使用4 70 30 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：4请问你要释放哪一块内存:2---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 10 空闲1 10 25 使用2 35 15 空闲3 50 20 使用4 70 30 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：2最佳适应算法：请问你要分配多大的内存5---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 5 使用1 5 5 空闲2 10 25 使用3 35 15 空闲4 50 20 使用5 70 30 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：3最坏适应算法：请问你要分配多大的内存25---------------------------------------------------块号始地址大小状态---------------------------------------------------0 0 5 使用1 5 5 空闲2 10 25 使用3 35 15 空闲4 50 20 使用5 70 25 使用6 95 5 空闲----------------------------------------------1.首次适应2.最佳适应3.最差适应4.释放内存5.显示内存6.退出系统请输入1-6：总结与自评：总结：分区存储管理是操作系统进行内存管理的一种方式。

使用最佳适应算法设计主存的分配和回收程序c语言最佳适应算法是一种主存分配与回收策略，旨在有效利用计算机主存资源，最大化系统性能和用户体验。

这篇文章将详细介绍最佳适应算法的原理和实现，并使用C语言编写相应的主存分配和回收程序。

首先，我们需要了解最佳适应算法是如何工作的。

最佳适应算法基于以下两个基本原则：1. 内存分配：当我们需要分配一块内存时，最佳适应算法会在主存中寻找能够容纳所需大小的最小空闲块，并将其分配给请求者。

这意味着最佳适应算法会尽可能地减少浪费的空间。

2. 内存回收：当一块内存被释放后，最佳适应算法会尝试与相邻的空闲块进行合并，以形成更大的连续空闲块。

这样做可以最大化主存资源的利用率。

有了这些基本原则作为指导，接下来我们将通过实现一个主存分配和回收模拟程序来展示最佳适应算法的工作原理。

我们将使用C语言来编写这个程序。

首先，我们需要定义一个数据结构来表示主存中的内存块。

这个数据结构应该包含当前内存块的起始地址、大小和是否已分配的标志。

下面是相应的代码：ctypedef struct {int start_address;int size;int allocated;} MemoryBlock;接下来，我们需要定义一个数据结构来管理主存中的所有内存块。

我们可以使用一个数组来存储这些内存块。

此外，我们还需要跟踪主存中的空闲块数目。

下面是相应的代码：c#define MAX_BLOCKS 100MemoryBlock memory[MAX_BLOCKS];int num_free_blocks = 1;在程序初始化阶段，我们需要初始化主存数据结构，即将整个主存划分为一个初始的空闲块。

下面是相应的代码：cvoid initialize_memory(int size) {memory[0].start_address = 0;memory[0].size = size;memory[0].allocated = 0;}接下来，我们需要实现主存分配函数。

使用最佳适应算法对内存实现模拟动态分区管理摘要：内存动态分区管理的算法是操作系统课程中一个重要内容，理解和学习不同的分区算法能够为深入学习操作系统等知识提供一定的理论知识和实践依据。

本文采用c语言程序设计出最佳适应算法来模拟计算机内存分区管理，减少内存分配时产生的碎片，以此提高操作系统的稳定性。

关键词： c语言；模拟；内存分区；分配管理；最佳适应算法中图分类号：tp301 文献标识码：a 文章编号：1006-4311（2013）16-0214-021 模拟算法的设计思想计算机操作系统的最佳适应算法（best fit）是动态内存分区分配算法的一种[1]。

它能够从全部空闲区找出满足作业要求并且最小的空闲分区，这种算法能够让产生的碎片尽量缩小。

为了提高寻找速度，这种算法要求将所有的空闲区按其内容以从小到大的顺序形成一个空闲分区链。

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

最佳适应算法利用的思想就是将地址相邻近的自由区与回收区进行有效地合并，通过初始化空闲区、分配空闲区、回收空闲区实现模拟的内存管理，从而尽量减少碎片的产生，并尽可能的利用内存空间。

2 模拟算法的设计2.1 定义空闲分区链结构初始化时内存分配最大值定义为35670。

全局变量申明：设置分区描述器：2.2 主函数主函数main（）包括：建立头结点head；定义内存分配申请1和回收内存2的选择，如果输入1则输入申请的内存大小并调用分配函数assign1=assignment（head，application1），若assign1->address==-1则分配不成功，则调用printf（）函数输出“申请失败”，否则分配成功，用assign1->address进行分配；输入2将调用printf（）函数提示“输入回收区的首地址和回收区的大小”，然后用语句check=backcheck（head，back）函数判断申请是否合法，若输入合法，则调用do-while循环语句多次查找适应的节点，并再次调用printf（）函数输出回收结果。

学号专业姓名实验日期教师签字成绩实验报告【实验名称】采用可变式分区管理，使用首次获最佳适应算法实现内存分配与回收【实验目的与原理】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（）函数来实现。

首次适应算法代码首次适应算法是一种基于最少访问原则的页面置换算法，其核心思想是将最近最少使用（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` 表示所有进程都成功分配到分区。

GDOU-B-11-112 广东海洋大学学生实验报告书（学生用表）实验名称_____________ 课程名称操作系统课程号_______学院（系）软件学院专业________ 班级________________学生姓名_____________ 学号_____________ 实验地点___________ 实验日期__________一、实验目的修改MINIX操作系统内存管理的源程序，将MINIX的首次适应算法改为最佳适应和最差适应算法，对修改之后的MINIX源代码进行重新编译和重新启动，以测试你修改的正确性。

二、实验内容1、打开Minix3，进入alloc.c所在目录2、修改原算法为最佳适应算法(BEST_FIT)和最差适应算法(WORST_FIT)的程序如下:#i nclude "pm.h"#in clude <mini x/com.h>#in clude <mini x/call nr.h>#in clude <sig nal.h>#i nclude <stdlib.h>#i nclude "mproc.h"#in clude "../../ker nel/c on st.h"#in clude "../../ker nel/con fig.h"#in clude "../../kernel/type.h"#defi ne NR_HOLES (2*NR_PROCS)#defi ne NIL_HOLE (struct hole *) 0PRIVATE struct hole{ struct hole *h_n ext; phys_clicks h_base; phys_clicks h_le n; /* pointer to next entry on the list */ /* where does the hole begi n? */ /* how big is the hole? */} hole[NR_HOLES];PRIVATE u32_t high_watermark=0;PRIVATE struct hole *hole_head; /* pointer to first hole */PRIVATE struct hole *free_slots;/* ptr to list of un used table slots */#defi ne s ((phys_clicks) -1)FORWARD _PROTOTYPE( void del_slot, (struct hole *prev_ptr, struct hole *hp)); FORWARD _PROTOTYPE( void merge, (struct hole *hp) );#defi ne s() (0)/* max # en tries in hole table *//*alloc_mem*/PUBLIC phys_clicks alloc_mem(clicks)phys_clicks clicks; /* amount of memory requested */ #defi ne USING_BEST_FIT#ifdef USING_BEST_FIT{〃先找到第一个满足要求的空洞，〃再以第一个为标准寻找最适合的空洞。