资源描述：
《《数据结构》课件(C语言) 第08章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》第八章动态存储管理可利用空间表及分配方法边界标识法伙伴系统无用单元收集存储紧缩内容和要求可利用空间表、边界标识法、伙伴系统和无用单元收集。要求掌握可利用空间表及分配办法。重点可利用空间表及分配。内容和要求2动态存储管理的基本问题及方法存储管理是一个既复杂而又重要的问题。在后续课程——操作系统和编译技术（或方法、原理）中，将对其作较深入的研究。在数据库技术中，也涉及大量有关存储管理的问题。本章仅就动态存储管理方面一些基本技术进行讨论。在以往的算法描述中，有关存储分配请求、存储回收等项工作往往一带而过，好比是存储“自动满足”又“自动回收”。偶尔亦考虑某一数据结构
2、下判断是否溢出或者是否释放内存空间等问题。这是必要的，主要是为了把当时的重点和核心放在研究数据的逻辑特性、物理表示、算法描述与分析上，而对有关存储管理的问题作了一定的简化。3动态存储管理的基本问题(1)如何按用户提出的“请示”分配内存？(2)如何回收那些用户不再使用而“释放”的内存，以备新的“请示”产生时重新进行分配？(1)由用户来解决；(2)由系统来解决；(3)由系统和用户共同解决。存储管理问题的解决途径动态存储管理的基本问题及方法4在计算机系统中，存储管理的分级(1)操作系统为进程分配所需要的存储空间，以便能在机器上运行。一旦运行结束从系统撤离时，操作系统就回收进程
3、所使用的空间。此类存储管理问题将在《操作系统》课程中讨论。动态存储管理的基本问题及方法(2)进程对数据结构分配及回收存储空间，例如编译进程为变量、数组以及各种表格分配、回收空间。此类存储管理问题将在《编译方法》课程中讨论。(3)数据结构中，对某结构中的元素或子结构分配、回收存储空间。此类存储管理问题将是《数据结构》课程研究的范畴。下面仅限于在数据结构一级上研究存储管理的方法。但其基本思想和方法亦完全适用于其他两个级别。5一些有关存储管理的重要问题(1)由谁来负责存储空间的分配与回收？是用户自身，还是由系统的一个专门子系统为用户分配并发现不再使用的空间而加以回收？(2)分
4、配和释放存储空间的单位是相同还是有大有小？(3)系统何时回收空闲的空间？是及时回收还是定期回收或当存储空间用完时才去回收？(4)是否考虑存储碎片的紧凑问题？(5)当请示存储空间时，满足该请示的最好分配策略是什么？是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至少能满足的空间？(6)怎样安排空闲存储块的次序？随机排列或按地址排列或按容量大小排列？动态存储管理的基本问题及方法6u1u2u3u4u5u6u7u8u1u3u4u6u8(b)系统运行若干时间之后(a)系统运行初期；图8.1动态存储分配过程中的内存状态示例1系统运行期间，动态存储分配过程的初期及系统运行一段
5、时间后的状态示意如下两个术语占用块称已分配给用户使用的地址连续的内存区为占用块。在不同的动态存储管理系统中，请求分配的内存量大小不同，可能小到几个字节，多至若干k字节。但系统每次分配给用户的都是一个地址连续的内存区。空闲块称未曾分配的、地址连续的内存区为空闲块或可利用空间块。不管怎么样的动态存储管理系统，在刚开始工作时，整个内存区是一个空闲块（在编译系统中称之为堆，即堆区域）。动态存储管理的基本问题及方法空闲块占用块此时用户再次请求分配内存，系统将怎样分配？7两种分配策略：(1)系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行
6、，才回收所有空闲块，并重新组织内存，将所有空闲的内存区联接成一个大的空闲块；10,00015,000空闲31,0008,000空闲59,00041,000空闲起始地址内存块大小使用情况目录表(b)动态存储管理的基本问题及方法(2)用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请求分配内存时，系统巡视整个内存区中所有空闲块，从中找出一个合适者分配之。此时，系统需建立一张记录所有空闲块的可利用空间表（目录表或链表）。10,00025,00031,00039,00059,00099,999内存状态(a)示例1可利用空间表的图示形式链表(c)15,00008,00
7、0041,000∧031,00059,00010,000av图8.2动态存储管理过程中的内存状态和可利用空间表8可利用空间表及分配方法可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请示分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收该内存区并将它插入到可利用空间表中。可利用空间表的结构形式结构形式一：结点均含大小相同的空闲块。可利用空间表可以有下列三和不同的结构形式：若系统运行期间所有用户请求分配的存储量大小相同，则系统开始运行时，将归它使用的内存区按所需大小分割成若干大小相同的块
