第12章 动态存储管理,概述,可利用空间表及分配方法,存储压缩,边界标识法,无用单元的收集,存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、边界标识法、无用单元的收集和压缩存储等内容12.1 概述,动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“新求”产生时重新进行分配？,在单用户操作系统中，整个内存空间被划分成两个区域：系统区和用户区，系统区供系统程序使用，用户区供单一的用户程序所使用当计算机采用了多道程序设计技术后，需要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位置此时不能由程序员自已来确定，否则将出现多道程序竞争同一存储空间的情况可利用空间块 或空闲块,占用块,现在讨论，在图12.1（b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？,通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存是否已空闲，直到分配无法进行,另一种策略是用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。
为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表此表的结构可以是目录表也可以是链表如图12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表12．2可利用空间表及分配方法,操作系统既可借助目录表结构也可借助链表结构实现动态存储分配，本节将对采用链表的情况进行讨论根据系统运行的不同情况，可利用空间表可以有三种不同的结构形式：,第一种情况是系统运行期间所有用户请求分配的存储量大小相同对此类系统，可以在系统开始运行时将内存的用户区域按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在表头即可这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为“固定分区管理”第二种情况是系统运行期间用户请求分配的存储量有若干大小的固定规格对此系统，可将用户存储空间分割成不同规格的若干块，并将大小相同的空闲块组织在同一个可利用空间表中，即同一链表中的结点大小相同…,,,,av2,,,,0,1,,,,,0,1,,,,,0,1 ^,,,,…,,,,av4,,,,0,2,,,,,0,2,,,,,0,2 ^,,,,…,,,,av8,,,0 空闲块1 占用块0 结点大小为2KB 1 结点大小为4KB 2 结点大小为8KB,tag=,type=,,,例:,第三种情况是系统在运行期间分配给用户的内存块大小不固定，可以随请求而变。
此时，可利用空间表中的结点即空闲块的大小也是随意的通常，操作系统中的可利用空间表属于这种类型，这种存储管理实际上就是操作系统中的可变分区管理方法系统初始状态下，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变由于链表中结点大小不同，结点的结构可包含四个域，即：标志域（tag），用于区分此块是否为空闲块、大小域（size），用于指示空闲块的存储量、链域（link），用于指示可利用空间链表中的下一个结点、存储空间域（space），它是一个大小为size的连续存储空间由于可利用空间表中的结点大小不同，因此相应的分配与回收过程较为复杂假设某用户需大小为n的内存，而可利用空间表中仅有一块大小为m≥n的空闲块，则只需将其中大小为n的一部分分配给申请的用户，同时将剩余大小为m-n的部分作为一个结点留在链表中即可当可利用空间表中存在多个空间大小不小于n的空闲块时，一般可采用以下三种不同的分配策略1）最先适应分配算法，这种方法又称为首次适配法每次分配时，总是顺序查找可利用空间链表，找到第一个能满足长度要求的空闲区为止。
分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区2）最优适应分配算法这种分配算法每次从空闲区中挑选一个能满足作业要求的最小分区，这样可保证不去分割一个更大的区域，使装入大作业比较容易得到满足3）最坏适应分配算法最坏适应分配算法总是挑选一个能满足作业要求的最大的空闲区分割给作业使用，这样可使剩下的空闲区不至于太小，这种算法对中、小作业是有利的上述三种分配方法的选取一般需要考虑以下因素：用户的逻辑要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等无论采用何种分配方法在进行回收系统空闲块时需要考虑“结点合并”的问题，即当系统在不断进行分配和回收的过程中，大的空闲块逐渐被分割成小的占用块，当用户程序将某一占用块释放重新成为空闲块时，如果将它作为一个独立的空闲块插入到链表中，将出现两个或多个地址相邻的空闲块作为几个结点独立放在可利用空间表中，显然这不利于以后出现的大容量作业的请求为了更有效地利用内存，就要求系统在回收时应考虑将地址相邻的空闲块合并成尽可能大的结点12．3边界标识法,边界标识法是操作系统中用以进行动态分区分配的一种存储管理方法，它属于12.2节中介绍的第三种情况，即用户请求的内存块大小不固定，随不同的请求而变化。
系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按最先适应分配算法进行，也可按最优适应分配算法进行系统的特点在于：在每个内存区的头部和底部两个边界上分别设有标识，以识别该区域为占有块或空闲块，使得在回收用户释放的空闲块时容易判别在物理位置上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块12．3．1 可利用空间表的结构,它表示一个空闲块整个结点由三部分组成其中space为一段地址连续的存储单元，是可以分配给用户的内存区域，它的大小保存在head中的size域中它以头部head和底部foot作为它的两个边界；在head和foot中分别设有标志域tag，且设定空闲块中tag的值为“0”，占用块中tag的值为“1”；foot位于结点底部，因此它的地址是随结点中space空间的大小而变的为方便操作，可利用空间表可组织成双重循环链表head中的llink和rlink分别指向链表中的前趋结点和后继结点，表中不设表头结点，表头指针pav可以指向表中任一结点，即任何一个结点都可看成是链表中的第一个结点；表头指针为空则表明可利用空间表为空12．3．2分配算法,本节以最先适应分配算法来说明边界标识法的应用。
实现时，可以从表头指针pav所指的第一个结点开始进行查询，找到第一个容量不小于请求分配的存储量的空闲块即可进行分配为了使整个系统更有效地运行，在边界标识法中可做如下两条约定：,（1）假设找到的某个待分配的空闲块的容量为m个字，若每次只从中分配n（n
12．3．3回收算法,当用户释放占用块，系统需立即回收以备新的请求产生时进行再分配为了使物理地址毗邻的空闲块结合成一个尽可能大的结点，首先需要检查刚释放的占用块的左、右紧邻是否为空闲块采用边界标识法实现动态存储管理时每个内存区（无论是占用块或空闲块）的边界上都设有标志值，因此很容易区分刚释放的占用块的左、右紧邻是否为空闲块或占用块若释放块的左、右邻区均为占用块，则处理最为简单，只要将此新的空闲块作为一个结点插入到可利用空间表中即可；若只有左邻区是空闲块，则应将回收块与其左邻区合并成一个结点；若只有右邻区是空闲块，则应将回收块与其右邻区合并成一个结点；若左、右邻区都是空闲块，则应将三块合起来成为一个结点留在可利用空间表中12．4无用单元的收集,可利用空间表虽然方便地实现了存储空间的动态管理，但它的主要特点是应用户的请求而分配内存，在用户释放存储空间时进行回收因此，在这类存储管理系统中，用户必须明确给出“请求”和“释放”的信息但用户难免在某些时候会因为疏漏或其它原因致使系统没有进行回收而产生“无用单元”的问题此处，“无用单元”指的是那些用户不再使用而系统又没有回收的结构或变量例如，下列C程序段 s=malloc（20）； t=malloc（12）； …,s=t; 执行的结果是使执行s=malloc（20）为用户分配的结点成为无用单元，无法得到使用。
另外，由于数据结构本身的原因也有可能造成无用单元的产生，如广义表中存在着共享和递归成份，对共享结点来说，当该结点从某一条链上删除时它可能还链接在别的关系中，并不能立即释放该结点的空间，所以只有在全部链接关系中都被删除时，该结点才是无用结点，该结点所占用的空间才成为无用单元可以回收因此，要及时释放共享结点所占的空间，必须给每个结点增设一个共享计数器，记录本结点被几个链共享，当结点从某一链中被删除时，就将此计数器减1，反之在插入时计数器加1，一旦该计数器被减到0时，说明该结点在结构中不再有用，便可以回收这种处理方法的缺点是增加了额外的存储开销，同时也使程序的处理变得更加复杂有时少量无用单元的存在并不会影响系统的正常运行，但是当无用单元积累到一定阶段，就要求系统去找出这些无用单元，并把它们送回到可利用空间表中去在这里关键的问题是如何从整个存储空间中找出那些无用单元标志”算法通过周游广义表给每个有用结点记上标志，相应地所有无用结点由于不带标志，因此只要扫描一遍内存就可通过标志判断哪些是有用结点，哪些是无用结点，这样便可将所有的无用单元收回至可利用空间表实际运行的系统中结点的大小可能不等，但这并不影响“标志”算法，标志算法只要求找到结点的开始地址和其中描述结点之间关系的几个字段，并不关心结点中其它信息的长短。
因此，可以假设所有结点的结构如图12.8所示其中，link1和link2是两个指向同类型结点的指针，其意义可以解释为广义表的双链表示法mark是一标志位，初值为0，执行标志算法后，将全部有用结点的mark字段值置为1，其值继续保持为0的则为无用单元tag也是一个标志位，初值为0，在标志算法执行过程中，周游到本结点所对应的子表时被置成“1”，返回以后再恢复成“0”size字段表示本结点的长度，它主要在回收和压缩算法中起作用，在标志算法中它并不起作用算法12.3给出了标志算法算法初始时，所有结点的mark和tag字段都置为0，指针变量t指向广义表的根结点算法执行中，p指向当前处理的结点，r指向p所指结点的前趋结点算法结束时，所有广义表中的有用结点中的mark字段被置成“1”。