下载文档原格式
动态分区存储管理方式的主存分配回收总结动态分区存储管理是一种常见的主存分配回收技术，它通过动态创建并分配大小不等的存储块来管理主存空间，以满足不同进程的需求。
这种管理方式在操作系统中起着至关重要的作用，因此本文将对动态分区存储管理的主存分配回收进行总结，从原理、特点、优缺点及其在实际应用中的情况进行阐述。
一、原理动态分区存储管理是基于分区的主存管理机制，它将主存空间划分为多个不等大小的分区，每个分区可以被分配给一个进程使用。
当系统收到一个新进程的请求时，它会根据需要的主存大小为进程分配一个合适大小的分区。
当进程执行完毕，系统会回收该进程所占用的分区，使得该空间可以再次被分配给其他进程使用。
在动态分区存储管理中，主要有两种分配方式：首次适应算法和最佳适应算法。
首次适应算法是从第一个满足大小要求的分区开始进行分配；而最佳适应算法是从所有满足大小要求的分区中选择最小的分区进行分配。
这两种分配方式都有自己的优点和局限性，但它们都是基于动态分区存储管理的基本原理。
二、特点1.灵活性动态分区存储管理可以根据进程的需求动态地分配和回收主存空间，提高了主存的利用率和效率。
进程可以根据需要申请和释放主存空间，而无需预先分配固定大小的空间。
2.节省空间动态分区存储管理可以尽可能地利用主存中的碎片空间，减少了外部碎片的浪费。
这种管理方式能够充分利用主存空间，提高了主存的利用率。
3.多样性动态分区存储管理可以适应不同大小的进程需求，能够根据进程的大小灵活地进行分区分配，满足了不同进程的需求。
三、优缺点1.优点（1）提高了主存的利用率和效率。
（2）灵活地分配和回收主存空间，满足不同进程的需求。
（3）节省了主存空间，减少了碎片的浪费。
2.缺点（1）会产生外部碎片，影响了分区空间的利用率。
（2）分配和回收过程中可能产生较大的开销，影响了系统的性能。
四、在实际应用中的情况动态分区存储管理在操作系统中得到了广泛的应用，特别是在多道程序设计和实时系统中。
存储管理动态分区分配及回收算法存储管理是计算机系统中的重要组成部分，它负责管理和分配计算机中的物理内存资源。
在计算机系统中，通过动态分区分配和回收算法来实现对这些资源的有效利用。
本文将介绍动态分区分配和回收算法的原理、主要算法以及优缺点。
动态分区分配是一种灵活、动态的内存分配方式，它根据进程的需求动态地分配内存空间。
动态分区分配算法有多种，其中最常用的有首次适应算法、最佳适应算法和最坏适应算法。
首次适应算法（First Fit）是最常用的分配算法之一、它从低地址开始寻找第一个满足要求的空闲分区来分配进程。
这种算法的优点是简单、高效，但是可能会产生大量的碎片空间，降低内存的利用率。
最佳适应算法（Best Fit）是在所有空闲分区中找到一个大小最适合进程的分区来分配。
它的主要思想是选择一个更接近进程大小的空闲分区，以减少碎片空间的产生。
然而，这种算法的缺点是需要遍历整个空闲分区链表，因此效率相对较低。
最坏适应算法（Worst Fit）与最佳适应算法相反，它选择一个大小最大的空闲分区来分配进程。
这种算法的好处是可以尽可能地保留大块的碎片空间，以便后续分配使用。
但是，它也会导致更多的碎片空间浪费。
动态分区的回收算法是用于回收被释放的内存空间并合并相邻的空闲分区，以尽量减少碎片空间的产生。
常见的回收算法有合并相邻空闲分区算法和快速回收算法。
合并相邻空闲分区算法会在每次有分区被回收时，检查是否有相邻的空闲分区可以合并。
如果有，就将它们合并为一个大的空闲分区。
这样可以最大程度地减少碎片空间，提高内存的利用效率。
快速回收算法是一种将被释放的分区插入到一个空闲分区链表的头部，而不是按照地址顺序进行插入的算法。
这样可以减少对整个空闲分区链表的遍历时间，提高回收的效率。
总结起来，动态分区分配和回收算法在存储管理中起着重要的作用。
首次适应算法、最佳适应算法和最坏适应算法是常用的动态分区分配算法，它们各自有着不同的优缺点。
实验三存储管理动态分区存储管理
实验目的
•熟悉并掌握动态分区分配的各种算法。
•熟悉并掌握动态分区中分区回收的各种情
况，并能够实现分区合并。
实验内容及要求
•用高级语言模拟实现动态分区存储管理，要求：
–分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。
熟悉并掌握各种算法的空闲区组织方式。
–分区的初始化——可以由用户输入初始分区的大小。
（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）–分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。
–分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。
（注意：不存在的作业号要给出错误提示！）–分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）
实验报告要求
•实验报告应包含但不限于以下内容：–设计图（结构图/流程图）和源代码;
–使用的编程语言和系统环境;
–结果截图;
–对结果截图的解释性说明。
注意事项
•三个动态分区分配算法可以使用一套程序，差别只在空闲分区链(表)的排序策略。
•至少完成一个分配算法。
•需完成回收算法。
动态分区分配存储管理系统一、设计目的与内容用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法1）首次适应算法2）循环首次适应算法1.内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的。
2.作业数量、作业大小、进入内存时间、运行时间需要通过界面进行输入。
3.可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、进入内存时间、运行时间的初始化。
4.根据作业进入内存的时间，采用简单的先进先出原则进行从外存到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。
5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作。
二、算法的基本思想1、定义基本结构：1作业结构：typedefstructJOB{intnum;//作业号intsize;//作业大小intctime;//作业进入时间intrtime;//作业运行时间intstate;//作业状态}Job;2）分区结构：typedefstructDuLNode{intID;//分区号intstart;//开始地址intsize;//大小intstate;//0=尚未使用1=使用2=释放structDuLNode*prior;〃前驱指针structDuLNode*next;//后即指针}DuLNode,*DuLinkList;2、基本操作：intFirstfit(int);//首次适应算法intNext_fit(int);//循环首次适应算法voidshowJob(int);//显示作业表voidshowPartiton(DuLinkList);//显示分区表DuLinkListInitpartitionList(DuLinkList&p);//初始化voidhuishou(DuLinkListpl3,DuLinkList&pl);//回收函数intPutin(int&口)；//输入函数，输入作业相关信息3、首次适应算法空闲分区链以地址递增的次序链接，分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，取消的空闲分区仍留在空闲链中。
实验题目：存储器内存分配设计思路：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：总结与自评：总结：分区存储管理是操作系统进行内存管理的一种方式。
动态分区管理方式及动态分区算法一、动态分区概述在操作系统中，内存管理是一个非常重要的部分。
在实际的应用中，程序的内存需求是会发生变化的，因此需要一种灵活的内存管理方式来满足不同程序的内存需求。
动态分区管理方式应运而生，它可以根据程序的需求，灵活地分配和回收内存空间，是一种高效的内存管理方式。
二、动态分区管理方式动态分区管理方式是指将内存划分为多个大小不等的分区，每个分区都可以被分配给进程使用，当进程终止时，分区将被回收。
动态分区管理方式通常通过动态分区算法来实现，下面将介绍几种常见的动态分区算法。
三、首次适应算法首次适应算法是最简单和最直观的动态分区分配算法。
它的基本思想是在空闲分区链表中按照位置区域顺序查找第一个能够满足进程大小需求的空闲分区，并将其分配给进程。
首次适应算法的优点是实现简单，分区利用率较高，但缺点是会产生大量的不连续碎片。
四、最佳适应算法最佳适应算法是在空闲分区链表中查找满足进程大小需求的最小空闲分区，并将其分配给进程。
最佳适应算法的优点是可以减少外部碎片，缺点是查找适合的空闲分区会花费较长的时间。
五、最坏适应算法最坏适应算法是在空闲分区链表中查找满足进程大小需求的最大空闲分区，并将其分配给进程。
最坏适应算法的优点是能够产生较小的碎片，但缺点是会导致剩余分区较多，影响分区利用率。
六、动态分区管理方式的优缺点动态分区管理方式相比于静态分区管理方式有很多优点，比如可以灵活地满足不同程序的内存需求，可以动态地合并和分割分区，提高了内存的利用率等。
但是动态分区管理方式也有一些缺点，比如会产生碎片，分配和回收内存的开销较大等。
七、结语动态分区管理方式及其算法在实际应用中有着广泛的应用，通过合理选择动态分区算法，可以提高内存的利用率，改善系统性能。
也需要注意动态分区管理方式可能产生的碎片问题，可以通过内存紧缩等手段来解决。
希望本文对读者有所帮助。
动态分区管理方式及动态分区算法八、碎片问题与解决方法在动态分区管理方式中，经常会出现碎片问题，包括内部碎片和外部碎片。
存储管理的基本模式存储管理是操作系统中重要的组成部分，负责管理计算机系统中的内存和外部存储器。
存储管理的基本模式主要有以下几种：1. 固定分区固定分区是一种简单的存储管理方式，它将内存分为若干个固定大小的区域，每个区域对应一个进程或任务。
每个进程只能在自己的区域中运行，不能访问其他区域的内存。
这种方式在一定程度上限制了进程的自由度，但由于实现简单，在一些简单系统中仍然被采用。
优点：实现简单，安全可靠。
缺点：分区数量固定，造成内存浪费，且不利于大内存程序的运行。
适用场景：适用于内存较小、任务数量固定的系统。
2. 动态分区动态分区是一种更为灵活的存储管理方式，它根据进程或任务的实际需要，动态地分配内存空间。
这种方式能够更好地利用内存资源，提高内存利用率。
优点：内存利用率高，适用于大内存程序。
缺点：实现相对复杂，需要操作系统进行更多的管理操作。
适用场景：适用于内存较大、任务数量不确定的系统。
3. 页式管理页式管理是一种将内存分为若干个页（page）的存储管理方式。
每个页的大小固定，可以存放一个进程或任务的一部分。
页式管理通过将程序分割成多个页面，实现了内存的离散分配。
优点：内存利用率高，可以实现多道程序运行。
缺点：实现相对复杂，需要处理页面置换和缺页等问题。
适用场景：适用于内存较大、任务数量不确定的系统。
4. 段式管理段式管理将内存分为若干个段（segment），每个段的大小不固定，可以存放一个进程或任务的一部分。
段式管理通过将程序分割成多个段，实现了内存的逻辑分段。
优点：便于多道程序运行，可以实现分段保护和分段共享。
缺点：实现相对复杂，需要处理段之间的地址映射和保护等问题。
适用场景：适用于内存较大、任务数量不确定的系统。
5. 段页式管理段页式管理结合了页式管理和段式管理的优点，将内存分为若干个段，每个段又包含若干个页。
这种方式可以实现内存的逻辑分段和离散分配，同时提高了内存的利用率和多道程序运行能力。
存储管理动态分区分配及回收算法存储管理是操作系统中非常重要的一部分，它负责对计算机系统的内存进行有效的分配和回收。
动态分区分配及回收算法是其中的一种方法，本文将详细介绍该算法的原理和实现。
动态分区分配及回收算法是一种将内存空间划分为若干个动态分区的算法。
当新的作业请求空间时，系统会根据作业的大小来分配一个合适大小的分区，使得作业可以存储在其中。
当作业执行完毕后，该分区又可以被回收，用于存储新的作业。
动态分区分配及回收算法包括以下几个步骤：1.初始分配:当系统启动时，将整个内存空间划分为一个初始分区，该分区可以容纳整个作业。
这个分区是一个连续的内存块，其大小与初始内存大小相同。
2.漏洞表管理:系统会维护一个漏洞表，用于记录所有的可用分区的大小和位置。
当一个分区被占用时，会从漏洞表中删除该分区，并将剩余的空间标记为可用。
3.分区分配:当一个作业请求空间时，系统会根据作业的大小，在漏洞表中查找一个合适大小的分区。
通常有以下几种分配策略：- 首次适应(First Fit): 从漏洞表中找到第一个满足作业大小的分区。
这种策略简单快速，但可能会导致内存碎片的产生。
- 最佳适应(Best Fit): 从漏洞表中找到最小的满足作业大小的分区。
这种策略可以尽量减少内存碎片，但是分配速度相对较慢。
- 最差适应(Worst Fit): 从漏洞表中找到最大的满足作业大小的分区。
这种策略可以尽量减少内存碎片，但是分配速度相对较慢。
4.分区回收:当一个作业执行完毕后，系统会将该分区标记为可用，并更新漏洞表。
如果相邻的可用分区也是可合并的，系统会将它们合并成一个更大的分区。
总结来说，动态分区分配及回收算法是一种对计算机系统内存进行有效分配和回收的方法。
通过合理的分配策略和回收机制，可以充分利用内存资源，提高系统性能。
然而，如何处理内存碎片问题以及选择合适的分配策略是需要仔细考虑的问题。
动态分区分配算法动态分区分配算法是计算机在处理大型计算问题时分配内存的一种算法。
它由英国计算机科学家考克·拉伦斯（C. Alan Rees）和美国计算机科学家杰弗里·布朗（Geoffrey Brown）于1959年提出，发展到今天，仍然是当前计算机内存管理中应用最为广泛的算法之一。
据统计，它在数据处理和科学计算中应用最为广泛，比例达到90％以上。
动态分区分配算法建立在虚拟存储器系统于单一空间中的理论上，它会将虚拟存储器空间分割成多个区块，即所谓的“分区”，在这些“分区”中每一个“分区”被认为是一个独立的内存块，它可以被视作内存的一个物理分割实体。
确定分区个数以及每个分区的大小，称为分区的方法的决定步骤。
分区的决定步骤有固定分区、可变分区和动态分区等。
固定分区分配法要求在系统安装前确定程序分区的规模，在整个运行期间该规模是不变的，因此片面此法解决不了内存非连续性的问题。
可变分区分配法将内存空间分割成几个大小不等的可变尺寸的分区，这种算法的原理还是以空间的划分为两个分区，它有效解决了内存空间划分的非连续性问题，但受到固定分区的分配量的限制，因此它的可扩大性也有所限制。
动态分区分配算法可以根据运行时不断地选择最终分区的大小，以获得最优的内存分配方案，它扩展了计算机系统中内存空间的使用，同时能够满足多台机器大型程序精确分配内存大小的要求，它可以更好地充分利用计算机系统中的内存。
动态分区分配算法是一种比较强大的算法，它能够根据实际情况提供充分利用空间的储存形式，处理实时物理系统的大型问题，并在很大的程度上提高了工作效率，节约价值，以及满足多台机器大型软件应用程序的需要。
动态分区分配存储管理系统一、设计目的与内容用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法1）首次适应算法2）循环首次适应算法1. 内存中有0-100M 的空间为用户程序空间，最开始用户空间是空闲的。
2. 作业数量、作业大小、进入内存时间、运行时间需要通过界面进行输入。
3. 可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、进入内存时间、运行时间的初始化。
4. 根据作业进入内存的时间，采用简单的先进先出原则进行从外存到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。
5. 能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作。
二、算法的基本思想1、定义基本结构：1作业结构：typedef struct JOB{int num; //作业号int size; //作业大小int ctime; //作业进入时间int rtime; //作业运行时间int state; //作业状态}Job;2)分区结构：typedef struct DuLNode{int ID; //分区号int start; //开始地址int size; //大小int state; //0=尚未使用1=使用2=释放struct DuLNode *prior;//前驱指针struct DuLNode *next; //后即指针}DuLNode, * DuLinkList;2、基本操作：int Firstfit(int);//首次适应算法int Next_fit(int); //循环首次适应算法void showJob(int); //显示作业表void showPartiton(DuLinkList);//显示分区表DuLinkList InitpartitionList(DuLinkList &p);//初始化void huishou(DuLinkList pl3,DuLinkList &pl);//回收函数int Putin(int &n);//输入函数，输入作业相关信息3、首次适应算法空闲分区链以地址递增的次序链接，分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，取消的空闲分区仍留在空闲链中。
若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。
4、循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。
三、主要功能模块流程图主函数：首次适应算法：循环首次适应算法四、系统测试程序运行实例如下：1、输入界面，按要求输入：2、选择算法及分区首地址：3、运行结束后显示，并继续选择：4、退出：五、结论作业采用数组形式进行存储，起初想用数组模拟分区，但划分记录比较不易，时间空间复杂度较大，容易混乱，遂决定用链表形式模拟分区情况。
基本能运行符合要求，能模拟出动态分区过程及最终结果。
六、源程序及系统文件使用说明#include <stdio.h>#include <stdlib.h>#include <iostream.h>#include <windows.h>#define Free 0#define Use 1#define MAX_length 100 //最大内存空间为100MB//--------------作业结构体数组----------------------------typedef struct JOB{int num; //作业号int size; //作业大小int ctime; //作业进入时间int rtime; //作业运行时间int state; //作业状态}Job;typedef struct DuLNode{int ID; //分区号int start; //开始地址int size; //大小int state; //0=尚未使用1=使用2=释放struct DuLNode *prior;//前驱指针struct DuLNode *next; //后即指针}DuLNode, * DuLinkList;//-------------------------------------------------------------------------------int Firstfit(int);//首次适应算法int Next_fit(int); //循环首次适应算法void showJob(int); //显示作业表void showPartiton(DuLinkList);//显示分区表//-----------------------------------------------------------------------------//---------------------------全局变量-------------------------------------------int f;Job *a; //排序后Job *temp;//-----------------------------功能函数------------------------------------------- void delay(){for(int x = 10000;x>0;x--)for(int y = 1000;y>0;y--);}//--------------------------------------------------------------------------------//------------------------初始化--------------------------------------------------- DuLinkList InitpartitionList(DuLinkList &p){p=(DuLinkList)malloc(sizeof(DuLNode));//申请空间if(!p)exit(0);p->size=100; //初始化大小printf("输入分区首地址:");scanf("%d",&p->start);p->state=0; //状态置空闲p->ID=0; //分区号p->next=NULL;p->prior=NULL;return p;}//------------------------------------------------------------------------------//-----------------------------输入函数--------------------------------------------- int Putin(int &n){int i;Job temp;printf("请输入任务数目:");scanf("%d",&n);a=(Job*)malloc(n*sizeof(Job));A=(Job*)malloc(n*sizeof(Job));for(i=0;i<n;i++){printf("\n");printf("信息输入:\n\n");printf("作业号:");scanf("%d",&a[i].num);printf("作业大小:");scanf("%d",&a[i].size);printf("作业进入时间:");scanf("%d",&a[i].ctime);printf("作业运行时间:");a[i].state=0; //默认状态为FreeA[i] = a[i];}for(int j = 0;j < n;j++)for(i = j;i< n;i++)if(a[j].ctime > a[i].ctime){temp = a[j];a[j] = a[i];a[i] = temp;}//冒泡排序freopen("data.txt","w",stdout);for (i = 0;i < n;i++){printf("%d %d %d %d\n",a[i].num,a[i].size,a[i].ctime,a[i].rtime);}fclose(stdout);freopen("CON","w",stdout);printf("保存成功\n\n");return 1;}//---------------------------------------------------------------------------------------- //-----------------------------读文件----------------------------------------------------- int order(int &n){Job temp;printf("Input the number of the task:\n");scanf("%d",&n);a=(Job*)malloc(n*sizeof(Job));freopen("data.txt","r",stdin);for(int i=0;i<n;i++){scanf("%d",&a[i].num);scanf("%d",&a[i].size);scanf("%d",&a[i].ctime);scanf("%d",&a[i].rtime);}fclose(stdin);freopen("CON","r",stdin);for(int j = 0;j < n;j++)for(i = j;i< n;i++)if(a[j].ctime > a[i].ctime){temp = a[j];a[i] = temp;}return 1;}//------------------------------------------------------------------------//-------------------------显示分区-------------------------------void showPartition(DuLinkList pl){printf("\n\t\t\t分区表\n");printf("\t---------------------------------------\n");printf("\t 开始地址\t分区号\t大小状态\n");printf("\t---------------------------------------\n");while(pl){printf("\t %d\t\t%d\t%d\t",pl->start,pl->ID,pl->size);if(pl->state == 0)printf("空闲\n");if(pl->state == 1)printf("已分配\n");pl=pl->next;}printf("\t---------------------------------------\n");}//-------------------------------------------------------------------------//---------------------------------回收函数---------------------------------void huishou(DuLinkList pl3,DuLinkList &pl){while(pl3){if(pl3->state==0){if(pl3->next&&pl3->prior&&pl3->prior->state==0&&pl3->next->state==1){pl3->size+=pl3->prior->size;pl3->start=pl3->prior->start;pl3->state=0;pl3->ID=0;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;}else{pl3->prior=pl3->prior->prior;pl3=pl;}}else if(pl3->prior&&pl3->next&&pl3->next->state==0&&pl3->prior->state==1) {pl3->size+=pl3->next->size;pl3->state=0;pl3->ID=0;if(pl3->next->next){pl3->next->next->prior=pl3;pl3->next=pl3->next->next;}else{pl3->next=pl3->next->next;}}else if(!pl3->prior){if(pl3->next->state==0){pl3->size+=pl3->next->size;pl3->state=0;pl3->ID=0;if(pl3->next->next)pl3->next->next->prior=pl3;pl3->next=pl3->next->next;}else{pl3->state=0;}}else if(!pl3->next){if(pl3->prior->state==0){pl3->size+=pl3->prior->size;pl3->state=0;pl3->ID=0;pl3->start=pl->start;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;}else{ pl3->prior=NULL;pl=pl3;pl3=pl;}}else{pl3->state=0;}}else if(pl3->next&&pl3->prior&&pl3->next->state==0&&pl3->prior->state==0){pl3->size=pl3->size+pl3->next->size+pl3->prior->size;pl3->state=0;pl3->ID=0;pl3->start=pl3->prior->start;if(pl3->next->next)pl3->next->next->prior=pl3;if(pl3->prior->prior){pl3->prior->prior->next=pl3;pl3->next=pl3->next->next;pl3->prior=pl3->prior->prior;}else{pl3->next=pl3->next->next;pl3->prior=pl3->prior->prior;pl=pl3;pl3=pl;}}}pl3=pl3->next;}}//--------------------------------------------------------------------------------------//----------------------------------首次适应算法---------------------------------------void Firstfit(DuLinkList block_first,int n){int t=1;int num=n;while(t&&num){DuLinkList pl1=block_first,pl2,pl3=block_first;printf("时钟:%d\n",t);DuLNode *p=block_first;DuLNode *q=block_first;for(int m=0;m<n;m++){if(t==a[m].ctime+a[m].rtime){num-=1;a[m].state=2;while(q){if(q->ID==a[m].num){q->state=Free;}q=q->next;}showJob(n);showPartition(block_first);}}for( m=0;m<n;m++){if(a[m].ctime==t){a[m].state=1;printf("作业:%d开始运行,对其分配!",a[m].num);}}for( m=0;m<n;m++){if(t==a[m].ctime){while(pl1&&(pl1->state == 1||pl1->size<a[m].size)) pl1=pl1->next;if(pl1){pl2=(DuLinkList)malloc(sizeof(DuLNode));pl2->start=pl1->start+a[m].size;pl2->state=0;pl2->ID=0;pl2->size=pl1->size-a[m].size;if(pl2->size>5){pl1->size=a[m].size;pl1->state=1;pl1->ID=a[m].num;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=block_first;}else{pl1->state=1;pl1->ID=a[m].num;}showJob(n);showPartition(block_first);}else{cout<<"内存不足，等待释放"<<endl;for(int i=m;i<n;i++){a[i].ctime+=1;}p=block_first;huishou(p, block_first);}}}t+=1;}}//---------------------------------------------------------------//---------------------------显示作业----------------------------void showJob(int n){printf("\n\t\t\t作业表:\n");printf("\t--------------------------------------------------------------\n");printf("\t 作业号\t大小\t进入时间\t运行时间\t状态\n");printf("\t--------------------------------------------------------------\n");for(int m=0;m<n;m++){printf("\t %d\t %d\t%d\t %d\t",a[m].num,a[m].size,a[m].ctime,a[m].rtime);if(a[m].state == 0)printf(" 等待\n");if(a[m].state == 1)printf(" 装入\n");if(a[m].state == 2)printf(" 结束\n");}printf("\t--------------------------------------------------------------\n");}//---------------------------------------------------------------------//-------------------- 循环首次适应算法------------------------void Nextfit(DuLinkList block_first,int n){int t=1;int num=n;DuLinkList flag;flag=block_first;while(t&&num){DuLinkList pl1=block_first,pl2,pl3=block_first;printf("时钟:%d\n",t);DuLNode *p=block_first;DuLNode *q=block_first;for(int m=0;m<n;m++){if(t==a[m].ctime+a[m].rtime){num-=1;a[m].state=2;while(q){if(q->ID==a[m].num){q->state=Free;}q=q->next;}showJob(n);showPartition(block_first);}}for( m=0;m<n;m++){if(a[m].ctime==t){a[m].state=1;printf("作业:%d开始运行,对其分配!",a[m].num);}}for( m=0;m<n;m++){if(t==a[m].ctime){while(flag&&(flag->state == 1||flag->size<a[m].size)) flag=flag->next;pl1=flag;if(pl1){pl2=(DuLinkList)malloc(sizeof(DuLNode));pl2->start=pl1->start+a[m].size;pl2->state=0;pl2->ID=0;pl2->size=pl1->size-a[m].size;if(pl2->size>5){pl1->size=a[m].size;pl1->state=1;pl1->ID=a[m].num;if(pl1->next)pl1->next->prior=pl2;pl2->next=pl1->next;pl2->prior=pl1;pl1->next=pl2;pl1=block_first;}else{pl1->state=1;pl1->ID=a[m].num;}flag=pl2;showJob(n);showPartition(block_first);}else{cout<<"内存不足，等待释放"<<endl;for(int i=m;i<n;i++){a[i].ctime+=1;}p=block_first;huishou(p, block_first);flag=block_first;}}}t+=1;}}//-------------------------------------------------------------------------------------//----------------------------界面输入---------------------------------------------void inputchoice(int &ch){cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<"1------>首次适应算法"<<endl;cout<<"2------>循环首次适应算法"<<endl;cout<<"3------>退出"<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<"请输入选择："<<endl;scanf("%d",&ch);}//--------------------------------------------------------------------------------------void main(){ DuLinkList p;int n,ch;ch = 0;f = 1;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<" 动态分区分配存储管理系统"<<endl;cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<" 请输入作业信息："<<endl;Putin(n);while(f){inputchoice(ch);switch(ch){case 1:InitpartitionList(p);Firstfit(p,n);ch = 0;break;case 2:InitpartitionList(p);Nextfit(p, n);ch = 0;break;case 3:f = 0;break;}}}。
