下载文档原格式
循环首次适应的动态分区分配算法模拟1.初始化内存空间为一个整体的空闲块。
2.当进程请求内存空间时，多次内存空闲块的循环链表，直到找到一个合适大小的空闲块为止。
3.如果找到了合适的空闲块，则将其划分为两个部分，一个部分给予进程使用，另一个部分保留为新的空闲块。
4.如果未找到合适的空闲块，则表示内存空间不足，需要进行深度缺页异常处理。
以下是一个循环首次适应算法的模拟过程：1.假设一个内存空间大小为1000KB，初始时为一个整体的空闲块。
2.进程A请求100KB的内存空间，开始内存空闲块链表。
3.如果找到合适的空闲块（大小≥100KB），则将其划分为两个部分，一个部分分配给进程A，另一个部分保留为新的空闲块。
4.进程B请求200KB的内存空间，继续内存空闲块链表。
5.如果找到合适的空闲块（大小≥200KB），则将其划分为两个部分，一个部分分配给进程B，另一个部分保留为新的空闲块。
6.进程C请求150KB的内存空间，继续内存空闲块链表。
7.找到合适的空闲块（大小≥150KB），将其划分为两个部分，一个部分分配给进程C，另一个部分保留为新的空闲块。
8.进程D请求300KB的内存空间，继续内存空闲块链表。
但此时已经循环了一次，仍未找到合适的空闲块。
9.进行深度缺页异常处理，即向操作系统申请更多的内存空间。
10.操作系统分配一块500KB的空闲块给进程D。
11.继续内存空闲块链表，找到合适的空闲块（大小≥300KB）。
12.将其划分为两个部分，一个部分分配给进程D，另一个部分保留为新的空闲块。
13.进程E请求250KB的内存空间，继续内存空闲块链表。
14.找到合适的空闲块（大小≥250KB），将其划分为两个部分，一个部分分配给进程E，另一个部分保留为新的空闲块。
15.当所有进程运行完毕后，剩余的空闲块可以继续加入链表，供下一次的分配请求使用。
总结起来，循环首次适应算法通过循环链表合适大小的空闲块来满足进程的内存需求，能够最大限度地利用内存空间，避免了内存碎片的产生。
动态分区分配算法描述一、引入动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？二、首次适应算法（First Fit）算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
三、最佳适应算法（Best Fit）算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。
因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。
因此这种方法会产生很多的外部碎片。
四、最坏适应算法(Worst Fit)又称最大适应算法（Largest Fit）算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
重新排序：空闲分区按容量递减次序链接缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。
如果之后有“大进程”到达，就没有内存分区可用了。
五、邻近适应算法（Next Fit）算法思想：首次适应算法每次都从链头开始查找的。
这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。
如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
内存分配---FF、BF、WF三种算法动态分区分配是根据进程的实际需要，动态的为之分配内存空间。
⽽在实现可变分区分配时，将涉及到分区分配中所⽤的数据结构、分区分配算法和分区的分配与内存回收的过程。
分区分配中的数据结构：（1）描述空闲块的数据结构。
（2）内存块的描述。
#define PROCESS_NAME_LEN 32 //进程名长度#define MIN_SLICE 10 //最⼩碎⽚的⼤⼩#define DEFAULT_MEM_SIZE 1024 //内存⼤⼩#define DEFAULT_MEM_START 0 //起始位置//内存分配算法#define MA_FF 1#define MA_BF 2#define MA_WF 3//描述每⼀个空闲块的数据结构struct free_block_type{int size; //空闲块⼤⼩int start_addr; //空闲块起始位置struct free_block_type *next; //指向下⼀个空闲块};//指向内存中空闲块链表的⾸地址struct free_block_type *free_block= NULL;//每个进程分配到的内存块的描述struct allocated_block{int pid;int size; //进程⼤⼩int start_addr; //进程分配到的内存块的起始地址char process_name[PROCESS_NAME_LEN]; //进程名struct allocated_block *next; //指向下⼀个进程控制块};//进程分配内存块链表的⾸指针struct allocated_block *allocated_block_head= NULL;int free_block_count= 0; //空闲块的个数int mem_size= DEFAULT_MEM_SIZE; //内存⼤⼩int current_free_mem_size= 0; //当前空闲内存⼤⼩int ma_algorithm= MA_FF; //当前分配算法static int pid= 0;int flag= 0; //设置内存⼤⼩标志，表⽰内存⼤⼩是否设置分区分配算法：（1）⾸次适应算法（First 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.更新空闲分区链表。
首次适应算法的优点是简单有效，适用于动态内存分配的场景。
但是它也存在一些缺点，比如可能会造成内存碎片，不够高效地利用内存空间。
此外，首次适应算法相对于其他分配算法，如最佳适应算法和最坏适应算法，可能需要更多的时间来适合的空闲分区。
总结来说，首次适应算法是动态分区分配中常用的算法之一，其主要思想是按照分区链表的顺序第一个大小满足进程需求的空闲分区来分配内存。
虽然存在一些缺点，但在实际应用中，首次适应算法被广泛使用。
动态分区分配算法一实验内容与要求内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。
在本实验中运用了三种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最佳适应算法。
要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有首次适应算法，循环首次适应算法，最佳适应算法。
特别注意分区回收时，相邻空闲分区需要合并。
(1)参考操作系统教材理解这3种分配算法以及回收算法。
(2)实现3种分配算法以及回收算法。
(3)已知作业申请内存和释放内存的序列，给出内存的使用情况。
(4)作业申请内存和释放内存的序列可以存放在文本文件中。
(5)设计简单的交互界面，演示所设计的功能。
(可以使用MFC进行界面的设计)(6)可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。
二、需求分析本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。
加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。
主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。
动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。
并使分区的大小正好适应作业的需要。
因此系统中分区的大小是可变的，分区的数目也是可变的。
分区分配算法：1.首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。
特点：优先利用内存中底地址部分的空闲分区 (将所有空闲区,按其地址递增的顺序链接)2.循环首次适应算法该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
3.最佳适应算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。
三、概要设计动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：typedef struct freearea//定义一个空闲区说明表结构{int ID; //分区号long size; //分区大小long address; //分区地址int state; //状态}ElemType;typedef struct DuLNode //double linked list{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针}DuLNode,*DuLinkList;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，id为分配的作业号，size表示分配的内存大小。
流程图：四、详细设计#include <iostream>#include<stdio.h>#include <fstream>#include<stdlib.h>using namespace std;#define Free 0 //空闲状态#define Busy 1 //已用状态#define OK 1 //完成#define ERROR 0 //出错#define MAX_length 640 //最大内存空间为640KBtypedef int Status;typedef struct freearea//定义一个空闲区说明表结构{int ID; //分区号long size; //分区大小long address; //分区地址int state; //状态}ElemType;//---------- 线性表的双向链表存储结构------------ typedef struct DuLNode //double linked list{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针}DuLNode,*DuLinkList;DuLinkList block_first; //头结点DuLinkList block_mid;DuLinkList block_last; //尾结点Status alloc(int);//内存分配Status alloc2(int);//内存分配2Status free(int); //内存回收Status First_fit(int,int); //首次适应算法Status CycleFirst_fit(int,int);//循环首次适应算法Status Best_fit(int,int); //最佳适应算法void show();//查看分配Status Initblock();//开创空间表int ID,request;long adds=0;Status Initblock()//开创带头结点的内存空间链表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_mid=(DuLinkList)malloc(sizeof(DuLNode));block_first->prior=NULL;block_first->next=block_mid;block_mid->next=block_last;block_mid->prior=block_first;block_last->prior=block_mid;block_last->next=NULL;block_mid->data.address=0;block_mid->data.size=MAX_length;block_mid->data.ID=0;block_mid->data.state=Free;return OK;}//----------------------- 分配主存-------------------------Status alloc(int ch){if(request<0 ||request==0){cout<<"分配大小不合适，请重试！"<<endl;return ERROR;}switch(ch){case 1:if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;ID=0;request=0;return OK;case 2:if(CycleFirst_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;ID=0;request=0;return OK;break;case 3:if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;ID=0;request=0;return OK;break;default:cout<<"********ERROR!********";}}Status alloc2(int ch){int ID,request;cout<<"请输入作业(分区号)：";cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：";cin>>request;if(request<0 ||request==0){cout<<"分配大小不合适，请重试！"<<endl;return ERROR;}switch(ch){case 1:if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;break;case 2:if(CycleFirst_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;break;if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;break;default:cout<<"********ERROR!********";}}//------------------ 首次适应算法-----------------------Status First_fit(int ID,int request)//传入作业名及申请量{//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p){if(p->data.state==Free && p->data.size==request){//有大小恰好合适的空闲块p->data.state=Busy;p->data.ID=ID;return OK;break;}if(p->data.state==Free && p->data.size>request){//有空闲块能满足需求且有剩余"temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;}p=p->next;}return ERROR;}//------------------ 循环首次适应算法-----------------------Status CycleFirst_fit(int ID,int request)//传入作业名及申请量{//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p){if(p->data.state==Free && p->data.size==request){//有大小恰好合适的空闲块p->data.state=Busy;p->data.ID=ID;return OK;break;}if(p->data.state==Free && p->data.size>request&&p->data.address==adds){//有空闲块能满足需求且有剩余"temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;adds=p->data.address;p->data.size-=request;cout<<adds<<endl;return OK;break;}if(request>p->next->data.size&&p->next->data.state==Free){if(First_fit(ID,request)==OK)return OK;}p=p->next;}return ERROR;}//-------------------- 最佳适应算法------------------------ Status Best_fit(int ID,int request){int ch; //记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最小空间和最佳位置{if(p->data.state==Free &&(p->data.size>request || p->data.size==request) ) {q=p;ch=p->data.size-request;break;}p=p->next;}while(p){if(p->data.state==Free && p->data.size==request){//空闲块大小恰好合适p->data.ID=ID;p->data.state=Busy;return OK;break;}if(p->data.state==Free && p->data.size>request){//空闲块大于分配需求if(p->data.size-request<ch)//剩余空间比初值还小{ch=p->data.size-request;//更新剩余最小值q=p;//更新最佳位置指向}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else{//找到了最佳位置并实现分配temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}}//----------------------- 主存回收--------------------Status free(int ID){DuLNode *p=block_first;while(p){if(p->data.ID==ID){p->data.state=Free;p->data.ID=Free;if(p->prior->data.state==Free&&p->next->data.state==Free)//前后都有空闲块{p->prior->data.size+=p->data.size;p->prior->data.size+=p->next->data.size;p->prior->next=p->next->next;p->next->next->prior=p->prior;adds=p->prior->data.address;cout<<"回收成功\n";break;}if(p->prior->data.state==Free)//与前面的空闲块相连{p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;adds=p->prior->data.address;}if(p->next->data.state==Free)//与后面的空闲块相连{p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;adds=p->prior->data.address;}cout<<"回收成功\n";break;}p=p->next;}return OK;}//--------------- 显示主存分配情况------------------void show(){cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++ 主存分配情况+++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";DuLNode *p=block_first->next;while(p){cout<<"分区号：";if(p->data.ID==Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分区大小："<<p->data.size<<" KB"<<endl;cout<<"状态：";if(p->data.state==Free) cout<<"空闲"<<endl;else cout<<"已分配"<<endl;cout<<"——————————————"<<endl;p=p->next;if(p==block_last){break;}}}//----------------------- 主函数---------------------------void main(){int OpNum;int Sqe[100][100];FILE *fp;fp=fopen("input.txt","r");if(!fp){cout<<"无法打开文件input.txt";exit(1);}fscanf(fp,"%d",&OpNum);for(int ii=0;ii<OpNum;ii++){for(int jj=0;jj<3;jj++)fscanf(fp,"%d",&Sqe[ii][jj]);}int ch;//算法选择标记cout<<" 动态分区分配方式的模拟\n";cout<<"************************************\n";cout<<"** 1.首次适应算法**\n";cout<<"** 2.循环首次适应算法**\n";cout<<"** 3.最佳适应算法**\n";cout<<"** 0.退出程序**\n";cout<<"************************************\n";cout<<"请选择分配算法：";cin>>ch;if(ch==0)exit(0);Initblock(); //开创空间表int choice; //操作选择标记for(int nn=0;nn<OpNum;nn++){cout<<"************************************\n";cout<<"** 1.下一操作**\n";cout<<"** 2.查看分配**\n";cout<<"** 0.退出程序**\n";cout<<"************************************\n";cout<<"请输入您的操作：";cin>>choice;if(choice==1){ID=Sqe[nn][0];request=Sqe[nn][2];if(Sqe[nn][1]==0){cout<<"作业"<<ID<<"申请"<<request<<"KB内存"<<endl;alloc(ch);//操作符为0，则开始分配内存}if(Sqe[nn][1]==1){cout<<"作业"<<ID<<"释放"<<request<<"KB内存"<<endl;free(ID);//操作符为1，则释放内存}}else if(choice==2) // 显示主存{show();nn--;}else if(choice==0) break; //退出}show();cout<<endl<<"主存已分配完毕。
