数据结构 动态存储管理 第八章动态存储管理 主讲：张昱 重点：内存空间的分配与回收算法，以 yuzhang@ustc.edu 及可利用空间表的结构。 0551-3603804 难点：无用单元收集算法的理解与掌 握。 /35 2/35 第八章动态存储管理 8.1概述(1) 8.1概述 。程序中的变量如何存储管理？ 。早期，由程序员自己先成： 8.2可利用空间表及分配方法 在执行痕序之前，光高将厕机悬语言成江铺语言感写的在序情远到 内存的个国定区城上，并预先给变量和分配好对应的内存地 8.3边界标识法 址绝对成湘时地址) 8.4伙伴系统 ,有了高级语言后，程序员不需直接和内存地址打交道： 变量对应的内年地址复是电城座在城是盛热：时进折分靴 8.5无用单元收集 ·操作系统 存情管理是操作系械和铺泽瘦序的一 木热且广垂的问L 8.6存储紧缩 ·单用户操作系统：内存空可藏切分为素绿区（供系线超序使用）和用 户区（供单一的用户程序所使用） 多道程序设计：多个用户程序共率一个内存区城，每个用户程序 用的内存就由操作系统来进行分配。 3/35 4/35 图 8.1概述(2) 8.1概述(3) ■动态存储管理的基本问题 ·系统如何用用户提出的“请求”分配内存？ 。如何回收那些用户不再使用而“释放”的内存，以备新的 动态存储管理系统刷开工时 空闲块 “请求”产生时重新进行分配？ 用户提出的“请求”： 不☑不N 。可能是进入系统的一个作业 。也可能是程序执行过程中的一个动态变量 占用块 系能运行初期 系统每次分配给用户都是一个地址连续的内存区。称已分 配给用户使用的地址连续的内存区为“占用块”，称未曾分 不N ■ 配的地址违续的内存区为“可利用空间块”或“空闲块”。 系能运行若干时间之后 5/35 图 6/35 图1 1/35 数据结构——动态存储管理 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/35 重点：内存空间的分配与回收算法，以 及可利用空间表的结构。 难点：无用单元收集算法的理解与掌 握 。 第八章 动态存储管理 3/35 第八章 动态存储管理 8.1 概述 8.2 可利用空间表及分配方法 8.3 边界标识法 8.4 伙伴系统 8.5 无用单元收集 8.6 存储紧缩 4/35 8.1 概述(1) „ 程序中的变量如何存储管理？ „ 早期，由程序员自己完成： 在执行程序之前，先需将用机器语言或汇编语言编写的程序输送到 内存的某个固定区域上，并预先给变量和数据分配好对应的内存地 址(绝对或相对地址) „ 有了高级语言后，程序员不需直接和内存地址打交道： 变量对应的内存地址都是由编译程序在编译或执行时进行分配 „ 操作系统 „ 单用户操作系统：内存空间被划分为系统区(供系统程序使用)和用 户区(供单一的用户程序所使用) „ 多道程序设计：多个用户程序共享一个内存区域，每个用户程序使 用的内存就由操作系统来进行分配。 存储管理是操作系统和编译程序的一 个复杂且重要的问题！ 5/35 8.1 概述(2) „ 动态存储管理的基本问题 „ 系统如何用用户提出的“请求”分配内存？ „ 如何回收那些用户不再使用而“释放”的内存，以备新的 “请求”产生时重新进行分配？ 用户提出的“请求”： „ 可能是进入系统的一个作业 „ 也可能是程序执行过程中的一个动态变量 系统每次分配给用户都是一个地址连续的内存区。称已分 配给用户使用的地址连续的内存区为“占用块”，称未曾分 配的地址连续的内存区为“可利用空间块”或“空闲块”。 6/35 8.1 概述(3) U1 U2 U3 U4 U5 U6 U7 U8 系统运行初期 U1 U3 U4 U6 U8 系统运行若干时间之后 占用块 动态存储管理系统刚开工时 空闲块