编译原理课件：8-第八章_存储空间组织-6节

1、8.6 堆式存储管理堆式存储管理程序语言允许用户程序动态申请和释放空间，如：程序语言允许用户程序动态申请和释放空间，如： C C语言语言: : malloc malloc：在动态存储区中分配一块连续区域：在动态存储区中分配一块连续区域； calloccalloc：在动态存储区中分配：在动态存储区中分配n n块连续区域块连续区域； freefree：释放一块动态存储区空间；：释放一块动态存储区空间； PASCALPASCAL语言语言: : New New、GetMemGetMem：在动态存储区中分配一块连续区域：在动态存储区中分配一块连续区域； DisposeDispose、FreeMemFre

2、eMem：释放一块动态存储区空间；：释放一块动态存储区空间；当程序语言允许用户程序动态申请和释放空间时，当程序语言允许用户程序动态申请和释放空间时，数据存储空间的请求与释放不再遵循后进先出的原数据存储空间的请求与释放不再遵循后进先出的原则，因此，栈式存储分配不能满足这些数据的存储则，因此，栈式存储分配不能满足这些数据的存储要求。引入要求。引入“堆堆”。堆：堆：通常是一片连续的足够大的存储区，通常是一片连续的足够大的存储区， 当用户程序动态申请时，就从堆中分配一小块当用户程序动态申请时，就从堆中分配一小块 存储区给用户程序；存储区给用户程序； 用户程序使用完，再用释放命令将此存储区用户程序使用完

3、，再用释放命令将此存储区 退还给堆。退还给堆。8.6.1 8.6.1 堆式存储管理需解决的主要问题堆式存储管理需解决的主要问题 1. 1.用户程序申请空间（长度用户程序申请空间（长度=N=N） a)a)找到空闲块，长度找到空闲块，长度NN，取出，取出N N个单元分配；个单元分配； b)b)尽快找到符合该条件的空间，提高分配效率；尽快找到符合该条件的空间，提高分配效率； 为满足为满足b),b),常采用常采用“最先遇到的最先遇到的NN的空闲块，分配的空闲块，分配”。 2.2.碎片碎片 由于用户申请空间是分多步提出的，每次分配，都由于用户申请空间是分多步提出的，每次分配，都 会将现有的空闲块一分为二

4、，因此一段时间后，会会将现有的空闲块一分为二，因此一段时间后，会 有很多碎片。当碎片很多时，虽然碎片的总和大于有很多碎片。当碎片很多时，虽然碎片的总和大于 申请空间，但无法分配给申请者（不连续）。申请空间，但无法分配给申请者（不连续）。 8.6.2 8.6.2 堆式存储管理技术堆式存储管理技术1 1、定长块管理、定长块管理 把堆空间分成长度相等的若干块，每块中指定一个链，把堆空间分成长度相等的若干块，每块中指定一个链， 将相邻的空闲块拉成一条链，将相邻的空闲块拉成一条链，availableavailable指向链头。指向链头。 分配分配：按块分配，从：按块分配，从availableavaila

5、ble处开始分配处开始分配。 归还归还：插到链头，：插到链头， 即即availableavailable处。处。占用占用占用占用占用占用空闲空闲空闲空闲空闲空闲 (分配后分配后)available available占用占用空闲空闲占用占用空闲空闲空闲空闲空闲空闲available归还：归还：2 2、变长块管理、变长块管理根据用户程序申请分配空间的大小，分配长度不同根据用户程序申请分配空间的大小，分配长度不同的存储块。初始时，堆空间是一个整块；的存储块。初始时，堆空间是一个整块；管理程序将所有空闲块拉成一条链。管理程序将所有空闲块拉成一条链。 分配：分配：管理程序找到一个长度管理程序找到一个长

6、度NN的块，设大小的块，设大小=M=M， 若若M M与与N N相差不大，全部分配给用户相差不大，全部分配给用户( (减少碎块减少碎块) )。 否则，将其分成两部分，一部分分配，另一部分否则，将其分成两部分，一部分分配，另一部分 作为空闲块放入链中；作为空闲块放入链中； 归还：归还：若归还块和现有空闲块相邻，则合并；若归还块和现有空闲块相邻，则合并； 否则，链入空闲块链中；否则，链入空闲块链中；当有多个空闲块可以满足用户申请空间要求时，当有多个空闲块可以满足用户申请空间要求时，有几种分配策略。有几种分配策略。各策略的区别：分配效率，归还效率。各策略的区别：分配效率，归还效率。a)a)首次满足法首

7、次满足法 在空闲块链中查找，遇到长度在空闲块链中查找，遇到长度NN的空闲块，的空闲块， 就分配。就分配。 适合于：适合于： 系统事先不掌握空间申请情况的系统。系统事先不掌握空间申请情况的系统。效率：效率： 分配时需查询空闲链表，归还时无需查询。分配时需查询空闲链表，归还时无需查询。b)b)最优满足法最优满足法 扫描空闲块链，找到一个容量正好等于或稍大于扫描空闲块链，找到一个容量正好等于或稍大于 申请空间申请空间N N的空闲块，全部分配给用户。若空闲块的空闲块，全部分配给用户。若空闲块 过大，则分成两部分。过大，则分成两部分。 适合于：适合于： 请求分配的空间大小范围较广的系统。请求分配的空间大

8、小范围较广的系统。 效率较低效率较低 分配、归还时，均需要查询空闲链表。分配、归还时，均需要查询空闲链表。c)c)最差满足法最差满足法 将空闲块中将空闲块中 N N 的最大的空闲块，分成两部分，一的最大的空闲块，分成两部分，一部分分配，另一部分作为空闲块放入链中适当位置。部分分配，另一部分作为空闲块放入链中适当位置。空闲块表按空闲块的大小，从大到小排序。空闲块表按空闲块的大小，从大到小排序。适合于：适合于：请求分配的空间大小范围较窄的系统。请求分配的空间大小范围较窄的系统。效率：效率： * * 分配时无需查询。使用一段时间后，空间被分成分配时无需查询。使用一段时间后，空间被分成 若干块，每次分

9、配可能都是一个整的空闲块。若干块，每次分配可能都是一个整的空闲块。 * * 归还时需查询空闲链表，将空闲块插入到空闲块归还时需查询空闲链表，将空闲块插入到空闲块 链表中的适当位置。链表中的适当位置。 8.6.3 8.6.3 存储回收存储回收 1. 1. 回收工作执行时机回收工作执行时机 在堆的可利用空间几乎耗尽，不能满足用户程序的申在堆的可利用空间几乎耗尽，不能满足用户程序的申请要求；或发现可利用空间已降至某个危险点时执行。请要求；或发现可利用空间已降至某个危险点时执行。 2 2. . 原因原因 a) a) 存储区中碎片过多，碎片的总和大于申请空间，存储区中碎片过多，碎片的总和大于申请空间，

10、但无法分配给用户（不连续）；但无法分配给用户（不连续）； b) b) 有些存储块，用户程序使用完后，忘记释放；有些存储块，用户程序使用完后，忘记释放； 3. 3. 回收过程回收过程 a) a) 暂停用户程序的执行；暂停用户程序的执行； b) b) 存储块回收；存储块回收； c) c) 恢复用户程序的执行；恢复用户程序的执行； 4. 4. 存储块回收方案存储块回收方案 a) “a) “碎片过多碎片过多”的情况：的情况： 移动分配给客户的存储块，将所有的空闲块连接移动分配给客户的存储块，将所有的空闲块连接 在一起，形成一片可分配的连续空间。此时，必在一起，形成一片可分配的连续空间。此时，必 须调整运行程序对各占用块的全部引用点。须调整运行程序对各占用块的全部引用点。 b) “b