汇编网

帐号密码


多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页首页上一页下一页尾页

算法讲堂
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。现本栏目的内容处于不断添加中，请随时关注。

算法讲堂－》首次适应算法和最佳适应算法【讲解】

    首次适应算法和最佳适应算法是动态存储分配解决方案研究的内容，所以本文对这两种算法的讨论是通过研究动态存储管理来进行的。
一、存储管理的基本问题：
        存储管理讨论的基本问题是：
        1)、系统如何应用户的“请求”执行内存分配动作？
        2)、系统如何对用户不再使用后“释放”的内存执行回收动作，以保证为新的“用户请求”提供内存分配？
        内存的分配可以以静态方式进行，内存空间被分割为固定大小的若干内存块，用户的请求到达只要找到一块空闲的内存块予以分配即可，很显然静态存储分配的好处主要是实现比较方便，效率高，程序执行中系统需要做的事情比较简单。然而实际情况下提出“请求”的用户可能是进入系统的一个作业，也可能是程序执行过程中的一个动态变量。“请求”需要获得的内存容量大小不一，这种做法造成了对程序大小的严格的限制，使某些问题不能够合理的解决，此外，也会造成内存空间的浪费。动态存储管理就是确定如何满足一个个内存“请求”，如何更合理的使用有限的内存空间的一种内存分配解决方案，它以能够依据用户的请求依次进行内存空间的分配和回收，能够尽可能少的使用有限的空闲内存空间，最大限度的保证后续“请求”的可满足性为最终目的。
二、关于动态分配方案的分析：
        通常我们将已分配给用户是用的一段连续的内存空间称为“占用块”，将未分配给任何用户的一段连续的内存空间称为“可利用空间块”或者“空闲块”，我们在这里的描述将使用“占用块”和“空闲块”这两个概念。
        整个内存区在没有任何用户进入和运行的情况下只有一个空闲块，即整个可供用户“请求”使用的用户内存区域。随着不断的有用户请求进入系统，并依次获得系统为其分配的内存，使得整个内存区域逐渐被分割成两大部分：低地址区域包含若干占用块；高低址区域是空闲内存区域。经过一段时间后，有的用户运行结束，它们所占用的内存区释放后转变为一个个空闲块，这就使整个内存区域呈现出占用块和空闲块交错相隔的状态。而此时，如果再有新的用户“请求”到达，那么，系统如何为这个“请求”进行内存分配呢？
        在肯定动态存储管理的前提下，我们可以采取两种方案解决这个问题，一种解决方案是系统继续把高地址的空闲块分配给用户，而不理会低地址区域是否有结束执行的用户释放的内存块，直到剩余的高地址区域的空闲块不能满足新的用户“请求”，分配操作无法再进行下去时，才去回收结束执行的用户释放的内存块，并重新组织内存，进而完成内存分配。另一种解决方案是一旦有用户释放内存，就将这块内存回收，并重新组织内存。每当有新的用户“请求”到达，系统都从低地址处开始为其找出一个合适的空闲块予以分配。
        后面我们只讨论第二种方案，这种方案的实现要求系统建立一张记录所有空闲块的“可利用空间表”，其形式不拘，可以是“目录表”，也可以采用“链表”的形式。
三、几种动态分配算法：
1、基于可利用空间表的3种分配算法：
        1)最先适应算法（或首次适应或首次拟合算法）；
        2)最佳适应算法（或最佳拟合算法，节点从小到大排序）；
        3)最差适应算法（或最差拟合算法，节点从大到小排序）。
2、算法描述：
        可利用空间表的节点结构如下图：

        首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。
        最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户“请求”，从而使整个链表逐渐趋向于节点大小差别甚远的状态。这种分配算法适合请求分配内存大小范围较广的系统，此算法比较费时间。
        最差适应算法将可利用空间表中一个大小不小于“请求”且是链表中最大的空闲块的一部分分配给用户。要求节点从大到小排序。分配时不需查询，回收时要查询，以便插入到适当位置。这种算法将使链表的节点大小逐渐趋于均匀，适合请求分配内存大小范围较窄的系统，此算法最费时间。
        再说说首次适应算法，这种分配算法具有随机性，它介于最佳适应算法和最差适应算法之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放回收的信息的情况。
        由此可见，不同的情形应当采取不同的分配算法，我们需要考虑的因素一般有以下几种：
        1)用户的逻辑要求；
        2)“请求”分配量的大小分布；
        3)分配和释放的频率；
        4)效率对系统的重要性，等等。
        在实际的算法实现当中还应考虑在回收用户释放的内存块后对内存空间的重新组织，合并连续的内存块，即“节点合并”的问题。因为系统在不断的分配和回收过程中，使得大的空闲块逐渐被分割成小的占用块，然后又重新成为空闲块被系统回收，如此反复，地址相邻的两块空闲块却分别作为链表中的节点存在，导致出现较大的用户“请求”时，虽然有足够的空闲空间，但是他们分布在多个空闲块内，对系统是透明的，分配无法进行。为了使内存空间得到更有效的利用，就要求在回收内存块后对内存空间进行重新组织，合并连续的内存空间，使至最大限度的满足将来的分配需求。
四、算法应用：
        动态存储管理涉及的一般算法在各个领域都有所体现，比如经典的装箱问题就是这方面的实际应用问题。在此我们只讨论了这些算法在动态存储管理过程中的细节问题。
五、学习建议及练习任务：
        动态存储管理的算法是操作系统设计的一个重要问题，学习和研究它们能够为我们在操作系统等方面的深入研究提供一定的理论依据和实践感知。主要是要搞清楚诸多算法的基本思想和应用环境。
        学习之余我们不妨对经典的装箱问题进行研究和实现，以达到深入感知这些算法的目的。

[07/10/24]

Email: asmedu@163.com