动态存储管理.pptVIP

第12章　动态存储管理; 存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。 动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、边界标识法、无用单元的收集和压缩存储等内容。 ;12.1 概述;J0;现在讨论，在图12.1（b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？ ;为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。如图12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表。 ;0;12．2可利用空间表及分配方法;由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在表头即可。这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为“固定分区管理”。 ;tag; 第三种情况是系统在运行期间分配给用户的内存块大小不固定，可以随请求而变。此时，可利用空间表中的结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属于这种类型，这种存储管理实际上就是操作系统中的可变分区管理方法。系统初始状态下，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变。;tag;（1）最先适应分配算法，这种方法又称为首次适配法。每次分配时，总是顺序查找可利用空间链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。 ; 上述三种分配方法的选取一般需要考虑以下因素：用户的逻辑要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等。;12．3边界标识法;12．3．1 可利用空间表的结构 ; 为方便操作，可利用空间表可??织成双重循环链表。head中的llink和rlink分别指向链表中的前趋结点和后继结点，表中不设表头结点，表头指针pav可以指向表中任一结点，即任何一个结点都可看成是链表中的第一个结点；表头指针为空则表明可利用空间表为空。 ;12．3．2分配算法 ;用户作业；反之，只分配其中n个字的内存块。同时，为了避免修改指针，在分配部分空间时约定将结点中的高地址部分分配给用户。; 例如，对图12.6所示的可利用空间表进行分配一个大小为500个字的存储单元后可利用空间表的状态如图12.7所示，此时，表头指针pav指向了下一个结点。;12．3．3回收算法 ; 若释放块的左、右邻区均为占用块，则处理最为简单，只要将此新的空闲块作为一个结点插入到可利用空间表中即可；若只有左邻区是空闲块，则应将回收块与其左邻区合并成一个结点；若只有右邻区是空闲块，则应将回收块与其右邻区合并成一个结点；若左、右邻区都是空闲块，则应将三块合起来成为一个结点留在可利用空间表中。;12．4无用单元的收集;s=t; 执行的结果是使执行s=malloc（20）为用户分配的结点成为无用单元，无法得到使用。 ; 因此，要及时释放共享结点所占的空间，必须给每个结点增设一个共享计数器，记录本结点被几个链共享，当结点从某一链中被删除时，就将此计数器减1，反之在插入时计数器加1，一旦该计数器被减到0时，说明该结点在结构中不再有用，便可以回收。 ;“标志”算法通过周游广义表给每个有用结点记上标志，相应地所有无用结点由于不带标志，因此只要扫描一遍内存就可通过标志判断哪些是有用结点，哪些是无用结点，这样便可将所有的无用单元收回至可利用空间表。;mark; 算法12.3给出了标志算法。算法初始时，所有结点的mark和tag字段都置为0，指针变量t指向广义表的根结点。算法执行中，p指向当前处理的结点，r指向p所指结点的前趋结点。算法结束时，所有广义表中的有用结点中的mark字段被置成“1”。;12．5存储压缩 ;实施“存储压缩“通常有两种做法，一种是一旦有用户释放存储块即进行回收压缩；另一种是在程序执行过程中不回收用户随时释放的存储块，而是在可利用空间不够分配或在进行无用单元的收集时进行“存储压缩”。 ; 存储压缩的过程比较复杂，不仅要改变结点的物理地址，同时还要修改结点中的全部指针。实际上，存储压缩是有条件的，当某个有用块中的程序正在执行与外设相关的输入输出操作时不能进行程序的移动（具体的原因在操作系统相关课程中学习）。此处，可以通过以下三个步骤来实现存储压缩： （1）给有用结点分配新地址