下载文档原格式
动态分区分配算法描述一、引入动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？二、首次适应算法（First Fit）算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
三、最佳适应算法（Best Fit）算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。
因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。
因此这种方法会产生很多的外部碎片。
四、最坏适应算法(Worst Fit)又称最大适应算法（Largest Fit）算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
重新排序：空闲分区按容量递减次序链接缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。
如果之后有“大进程”到达，就没有内存分区可用了。
五、邻近适应算法（Next Fit）算法思想：首次适应算法每次都从链头开始查找的。
这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。
如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
实验题目：存储器内存分配设计思路：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：总结与自评：总结：分区存储管理是操作系统进行内存管理的一种方式。
动态分区管理方式及动态分区算法一、动态分区概述在操作系统中，内存管理是一个非常重要的部分。
在实际的应用中，程序的内存需求是会发生变化的，因此需要一种灵活的内存管理方式来满足不同程序的内存需求。
动态分区管理方式应运而生，它可以根据程序的需求，灵活地分配和回收内存空间，是一种高效的内存管理方式。
二、动态分区管理方式动态分区管理方式是指将内存划分为多个大小不等的分区，每个分区都可以被分配给进程使用，当进程终止时，分区将被回收。
动态分区管理方式通常通过动态分区算法来实现，下面将介绍几种常见的动态分区算法。
三、首次适应算法首次适应算法是最简单和最直观的动态分区分配算法。
它的基本思想是在空闲分区链表中按照位置区域顺序查找第一个能够满足进程大小需求的空闲分区，并将其分配给进程。
首次适应算法的优点是实现简单，分区利用率较高，但缺点是会产生大量的不连续碎片。
四、最佳适应算法最佳适应算法是在空闲分区链表中查找满足进程大小需求的最小空闲分区，并将其分配给进程。
最佳适应算法的优点是可以减少外部碎片，缺点是查找适合的空闲分区会花费较长的时间。
五、最坏适应算法最坏适应算法是在空闲分区链表中查找满足进程大小需求的最大空闲分区，并将其分配给进程。
最坏适应算法的优点是能够产生较小的碎片，但缺点是会导致剩余分区较多，影响分区利用率。
六、动态分区管理方式的优缺点动态分区管理方式相比于静态分区管理方式有很多优点，比如可以灵活地满足不同程序的内存需求，可以动态地合并和分割分区，提高了内存的利用率等。
但是动态分区管理方式也有一些缺点，比如会产生碎片，分配和回收内存的开销较大等。
七、结语动态分区管理方式及其算法在实际应用中有着广泛的应用，通过合理选择动态分区算法，可以提高内存的利用率，改善系统性能。
也需要注意动态分区管理方式可能产生的碎片问题，可以通过内存紧缩等手段来解决。
希望本文对读者有所帮助。
动态分区管理方式及动态分区算法八、碎片问题与解决方法在动态分区管理方式中，经常会出现碎片问题，包括内部碎片和外部碎片。
实验五动态分区分配算法的模拟为了更好地理解动态分区分配算法的工作原理，我们可以进行一次模拟实验。
在实验中，我们将模拟一个内存分区，并使用动态分区分配算法来管理这些分区。
首先，让我们定义一个内存大小为1000字节的分区。
我们假设这个内存中包含几个已分配的分区和几个空闲的分区。
我们使用首次适应算法来进行分区的首次适应分配。
首先，我们将整个内存空间标记为空闲状态，并创建一个初始的空闲链表。
我们假设初始时只有一个空闲分区，大小为1000字节，起始地址为0。
现在，假设有一个进程请求分配一个250字节大小的内存空间。
我们首先检查空闲链表，找到一个大小大于等于250字节的空闲分区。
在这种情况下，我们发现第一个空闲分区的大小是1000字节，所以我们将它拆分成250字节的已分配分区和750字节的空闲分区。
我们在已分配分区上标记一个进程编号，并将空闲分区加入空闲链表。
接下来，假设我们的进程需要申请500字节的内存空间。
在这种情况下，我们需要查找一个大小大于等于500字节的空闲分区。
我们发现第一个可用的空闲分区大小是750字节，我们将它拆分为已分配的500字节和剩余的250字节的空闲分区。
然后，我们假设有进程释放了先前分配的250字节的内存空间。
当一个进程释放分配的内存空间时，我们需要合并相邻的空闲分区。
在这种情况下，释放的分区位于地址0，大小为250字节，并且其下一个分区是地址500，大小为500字节的空闲分区。
因此，我们将这两个分区合并为一个大小为750字节的空闲分区。
接下来，我们假设另一个进程将请求600字节的内存空间。
根据首次适应算法，我们将在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将分配200字节的空闲分区和分配400字节的空闲分区拆分为600字节的已分配分区和空闲分区。
最后，假设一个进程请求200字节的内存空间。
根据首次适应算法，我们在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将250字节的空闲分区拆分为200字节的已分配分区和50字节的空闲分区。
动态分区分配方式首次适应算法首次适应算法的思想是，当进程请求分配内存时，从空闲内存中找到第一个大小足够的空闲分区来满足进程需求。
因此，首次适应算法的时间复杂度与空闲分区的数量有关，但是分配成功的速度相对较快。
首先，我们需要建立一个空闲分区链表，其中记录了每个空闲分区的起始地址和大小。
初始状态下，整个内存空间是一个空闲分区。
当进程请求分配内存时，首次适应算法按照分区链表的顺序遍历空闲分区，找到第一个大小满足进程需求的分区。
具体操作如下：1.遍历空闲分区链表，找到第一个空闲分区大小大于等于进程请求大小的分区。
如果找到了满足条件的分区，则进行下一步；如果遍历完成仍未找到满足条件的分区，则进行内存紧缩或置换策略，为进程分配内存。
2.将找到的空闲分区进行分割，分为已分配给进程的部分和剩余的空闲部分。
已分配给进程的部分可以是与进程请求大小相等的分区，也可以是稍大的分区，以便于使用剩余空间。
3.更新空闲分区链表。
将已分配给进程的部分从链表中删除，将剩余的空闲分区插入链表中的适当位置。
4.返回已分配给进程的内存起始地址。
当进程释放内存时，可以通过合并相邻的空闲分区来优化内存空间的利用率。
1.遍历空闲分区链表，找到与释放的内存分区相邻的空闲分区。
2.将相邻的空闲分区进行合并，得到一个更大的空闲分区。
3.更新空闲分区链表。
首次适应算法的优点是简单有效，适用于动态内存分配的场景。
但是它也存在一些缺点，比如可能会造成内存碎片，不够高效地利用内存空间。
此外，首次适应算法相对于其他分配算法，如最佳适应算法和最坏适应算法，可能需要更多的时间来适合的空闲分区。
总结来说，首次适应算法是动态分区分配中常用的算法之一，其主要思想是按照分区链表的顺序第一个大小满足进程需求的空闲分区来分配内存。
虽然存在一些缺点，但在实际应用中，首次适应算法被广泛使用。
动态分区分配算法动态分区分配算法是在计算机内存管理中使用的一种内存分配策略。
在动态分区分配算法下，内存被划分为多个大小不一的分区，每个分区可以用来存储不同大小的进程。
当一个进程需要内存时，系统会选择一个合适的分区来满足其需求。
动态分区分配算法有多种实现方式，常用的包括最先适应算法、最佳适应算法和最坏适应算法。
最先适应算法（First Fit）是最简单和最常用的动态分区分配算法之一、该算法从内存起始位置开始查找合适的分区，一旦找到一个大小大于等于所需内存大小的空闲分区，就将该进程分配给这个分区并将分区大小减去所需内存大小。
这种算法的优点是实现简单、分区利用率高，但它可能会导致较小的分区被浪费掉，从而导致外部碎片的产生。
最佳适应算法（Best Fit）是另一种常用的动态分区分配算法。
该算法从所有空闲分区中选择一个大小最适合所需内存大小的分区来分配。
相比于最先适应算法，最佳适应算法能够更好地利用内存分区，减少外部碎片的产生。
然而，该算法的实现相对复杂，并且容易产生许多较小的空闲分区，导致分区利用率降低。
最坏适应算法（Worst Fit）是另一种动态分区分配算法。
该算法选择一个大小最大的空闲分区来分配给进程，这样可以留下更多较小的空闲分区，以备将来的进程使用。
然而，最坏适应算法可能会导致较大的分区被浪费掉，从而导致外部碎片的产生。
同样，该算法的实现也相对复杂，并且分区利用率相对较低。
动态分区分配算法的选择取决于特定的应用和场景。
最先适应算法在分配速度和分区利用率方面可能更优，但可能会产生较多的外部碎片。
最佳适应算法能够更好地利用内存分区，但实现复杂，容易产生较小的空闲分区。
最坏适应算法留下较小的空闲分区，但分区利用率较低。
因此，在选择动态分区分配算法时，需要权衡这些因素，并根据特定需求进行选择。
动态分区分配算法在现代操作系统中起着重要的作用，可以有效管理内存资源，提高系统的性能和效率。
同时，动态分区分配算法也是操作系统中的一个重要研究领域，不断有新的技术和算法被提出来优化内存管理，满足日益复杂的应用需求。
动态分区分配⼀．⽬的1.通过这次实验，加深对动态分区分配的理解，进⼀步掌握⾸次适应算法和最佳适应算法的理解。
了解动态分区分配⽅式中使⽤的数据结构和分配算法，进⼀步加深对动态分区存储管理⽅式及其实现过程的理解。
提⾼学⽣设计实验、发现问题、分析问题和解决问题的能⼒。
2.学会可变式分区管理的原理是在处理作业过程中建⽴分区，使分区⼤⼩正好适合作业的需求。
3.当⼀个作业执⾏完成后，作业所占的分区应归还给系统。
⼆．原理⾸次适应算法以空闲分区链为例来说明采⽤FF算法时的分配情况。
FF算法要求空闲分区链以地址递增的次序链接。
在分配内存时，从链⾸开始顺序查找，直⾄找到⼀个⼤⼩能满⾜要求的分区为⽌；然后再按照作业的⼤⼩，从该分取中划出⼀块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。
若从链⾸直到链尾都不能找到⼀个能满⾜要求的分区，则此次内存分配失败，返回。
该算法倾向于优先利⽤内存中低地址部分的空闲分区，从⽽保留了⾼址部分的⼤空闲区。
这给为以后到达的⼤作业分配⼤的内存空间创造了条件，其缺点是低址部分不断被划分，会留下许多难以利⽤的、很⼩的空闲分区，⽽每次查找⼜都是从低址部分开始，这⽆疑会增加查找可⽤空闲分区时的开销。
最佳适应算法所谓“最佳”是指每次为作业分配内存时，总是把能满⾜要求、⼜是最⼩的空闲分区分配给作业，避免“⼤材⼩⽤”。
为了加速寻找，该算法要求将所有的空闲分区按其容量以从⼩到⼤的顺序形成以空闲分区链。
这样，第⼀次找到的能满⾜要求的空闲区，必然是最佳的。
孤⽴地看，最佳适应算法似乎是最佳的，然⽽在宏观上却不⼀定。
因为每次分配后所割下来的剩余部分总是最⼩的，这样，在存储器中会留下许多难以利⽤的开销。
三．实验流程图⾸次适⽤算法最佳适⽤算法四.程序清单(VS 2013)#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>enum STATE{ Free, Busy};struct subAreaNode{ int addr; // 起始地址 int size; // 分区⼤⼩ int taskId; // 作业号 STATE state; // 分区状态 subAreaNode *pre; // 分区前向指针 subAreaNode *nxt; // 分区后向指针}subHead;// 初始化空闲分区链void intSubArea(){ // 分配初始分区内存 subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode)); // 给⾸个分区赋值 fir->addr = 0; fir->size = 1000; // 内存初始⼤⼩ fir->state = Free; fir->taskId = -1; fir->pre = &subHead; fir->nxt = NULL; // 初始化分区头部信息 subHead.pre = NULL; subHead.nxt = fir;}// ⾸次适应算法int firstFit(int taskId, int size){ subAreaNode *p = subHead.nxt; while (p != NULL) { if (p->state == Free && p->size >= size) { // 找到要分配的空闲分区 if (p->size - size <= 10) { // 整块分配 p->state = Busy; p->taskId = taskId; } else { // 分配⼤⼩为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode)); node->addr = p->addr + size; node->size = p->size - size; node->state = Free; node->taskId = -1; // 修改分区链节点指针 node->pre = p; node->nxt = p->nxt; if (p->nxt != NULL) { p->nxt->pre = node; } p->nxt = node; // 分配空闲区间 p->size = size; p->state = Busy; p->taskId = taskId; } printf("内存分配成功！\n"); return1; } p = p->nxt; } printf("找不到合适的内存分区，分配失败...\n"); return0;}// 最佳适应算法int bestFit(int taskId, int size){ subAreaNode *tar = NULL; int tarSize = 1000 + 1; subAreaNode *p = subHead.nxt; while (p != NULL) { // 寻找最佳空闲区间 if (p->state == Free && p->size >= size && p->size < tarSize) { tar = p; tarSize = p->size; } p = p->nxt; } if (tar != NULL) { // 找到要分配的空闲分区 if (tar->size - size <= 10) { // 整块分配 tar->state = Busy; tar->taskId = taskId; } else { // 分配⼤⼩为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode)); node->addr = tar->addr + size; node->size = tar->size - size; node->state = Free; node->taskId = -1; // 修改分区链节点指针 node->pre = tar; node->nxt = tar->nxt; if (tar->nxt != NULL) tar->nxt->pre = node; } tar->nxt = node; // 分配空闲区间 tar->size = size; tar->state = Busy; tar->taskId = taskId; } printf("内存分配成功！\n"); return1; } else { printf("找不到合适的内存分区，分配失败...\n"); return0; }}int freeSubArea(int taskId) // 回收内存{ int flag = 0; subAreaNode *p = subHead.nxt, *pp; while (p != NULL) { if (p->state == Busy && p->taskId == taskId) { flag = 1; if ((p->pre != &subHead && p->pre->state == Free)&& (p->nxt != NULL && p->nxt->state == Free)) { // 情况1：合并上下两个分区 // 先合并上区间 pp = p; p = p->pre; p->size += pp->size; p->nxt = pp->nxt; pp->nxt->pre = p; free(pp); // 后合并下区间 pp = p->nxt; p->size += pp->size; p->nxt = pp->nxt; if (pp->nxt != NULL) { pp->nxt->pre = p; } free(pp); } else if ((p->pre == &subHead || p->pre->state == Busy)&& (p->nxt != NULL && p->nxt->state == Free)) { // 情况2：只合并下⾯的分区 pp = p->nxt; p->size += pp->size; p->state = Free; p->taskId = -1; p->nxt = pp->nxt; if (pp->nxt != NULL) { pp->nxt->pre = p; } free(pp); } else if ((p->pre != &subHead && p->pre->state == Free)&& (p->nxt == NULL || p->nxt->state == Busy)) { // 情况3：只合并上⾯的分区 pp = p; p = p->pre; p->size += pp->size; p->nxt = pp->nxt; if (pp->nxt != NULL) { pp->nxt->pre = p; } free(pp); } else { // 情况4：上下分区均不⽤合并 p->state = Free; p->taskId = -1; } } p = p->nxt; } // 回收成功 printf("内存分区回收成功...\n"); return1; } else { // 找不到⽬标作业，回收失败 printf("找不到⽬标作业，内存分区回收失败...\n"); return0; }}// 显⽰空闲分区链情况void showSubArea(){ printf("*********************************************\n"); printf("** 当前的内存分配情况如下： **\n"); printf("*********************************************\n"); printf("** 起始地址 | 空间⼤⼩ | ⼯作状态 | 作业号 **\n"); subAreaNode *p = subHead.nxt; while (p != NULL) { printf("**-----------------------------------------**\n"); printf("**"); printf(" %3d k |", p->addr); printf(" %3d k |", p->size); printf(" %s |", p->state == Free ? "Free" : "Busy"); if (p->taskId > 0) { printf(" %2d ", p->taskId); } else { printf(""); } printf("**\n"); p = p->nxt; } printf("*********************************************\n");}int main(){ int option, ope, taskId, size; // 初始化空闲分区链 intSubArea(); // 选择分配算法 while (1) { printf("\n\n"); printf("\t****************请选择要模拟的分配算法******************\n"); printf("\n\n"); printf("\t \t 0 ⾸次适应算法 \n"); printf("\n\n"); printf("\t \t 1 最佳适应算法 \n"); printf("\n\n"); printf("\t\t\t\t你的选择是:"); scanf("%d", &option); if (option == 0) { printf("你选择了⾸次适应算法，下⾯进⾏算法的模拟\n"); break; } else if (option == 1) { printf("你选择了最佳适应算法，下⾯进⾏算法的模拟\n"); break; } else { printf("错误：请输⼊ 0/1\n\n"); } } // 模拟动态分区分配算法 while (1) { printf("\n"); printf("*********************************************\n"); printf("** 1: 分配内存 2: 回收内存 0: 退出 **\n"); printf("*********************************************\n"); scanf("%d", &ope); if (ope == 0) break; // 模拟分配内存 printf("请输⼊作业号： "); scanf("%d", &taskId); printf("请输⼊需要分配的内存⼤⼩(KB)： "); scanf("%d", &size); if (size <= 0) { printf("错误：分配内存⼤⼩必须为正值\n"); continue; } // 调⽤分配算法 if (option == 0) { firstFit(taskId, size); } else { bestFit(taskId, size); } // 显⽰空闲分区链情况 showSubArea(); } else if (ope == 2) { // 模拟回收内存 printf("请输⼊要回收的作业号： "); scanf("%d", &taskId); freeSubArea(taskId); // 显⽰空闲分区链情况 showSubArea(); } else { printf("错误：请输⼊ 0/1/2\n"); } } printf("分配算法模拟结束\n"); system("pause"); return0;}动态分区分配五.实验结果截图经过多次内存后：回收作业1和作业4后:此时分两种情况分别模拟⾸次使⽤算法和最佳使⽤算法为作业6分配40KB内存：模拟⾸次适应算法：最佳适⽤算法:六.结果分析通过多个分区分配，当回收作业1释放100K空间，回收作业4释放80K空间后，再为作业6分配40K空间。
