《第10章 存储管理》由会员分享，可在线阅读，更多相关《第10章 存储管理（29页珍藏版）》请在金锄头文库上搜索。
1、第10章 存储管理,2,存储管理,存储管理是程序员、语言实现者和语言设计者考虑的中心问题之一。 语言中含有对使用的存储管理技术的某种期望和限制。 如：在Fortran中，有对子程序非递归调用的限制。 但Fortran中是允许递归调用的，它的实现需要返回点的运行时栈（需要动态存储管理）。 如没有递归调用，Fortran可只用静态存储管理实现。 虽然每个语言设计通常允许某种存储管理技术的使用，但机制的细节、在软硬件中的表示却是实现者的任务。 程序对存储的直接控制较少，只能通过不同语言特性的使用产生间接影响。,3,10.1 需要存储的运行时元素,被翻译用户程序的代码段：两种形式（可执行机器代码或某种
2、中间形式）。 系统运行时程序支持用户程序执行系统程序，包括：简单的库例程、运行时的软件解释器或翻译器、控制运行时存储管理的例程等。通常形式为硬件可执行的机器代码。 用户定义的数据结构和常量。 子程序返回点：子程序可在程序中任何点被调用，需分配存储的内容包括：返回点、协同例程恢复点、被调度子程序的事件通知等。,4,需要存储的运行时元素（续）,引用环境指标识符关联 表达式计值的临时空间用于存放中间结果。当递归存在时，临时空间需要可能是无限的。 输入、输出缓冲用于外部介质间数据的交换。 其他零散系统数据表、I/O状态信息、以及各种状态信息。,5,需要存储的运行时元素（续）,除此之外，有些操作也需要存
3、储空间： 子程序调用和返回操作子程序激活记录、局部引用环境、及其他数据。而返回操作需要释放这些存储。 数据结构创建和后除操作 允许动态创建数据结构时，需要动态分配存储操作。 部件插入和删除操作 这些操作需要显式的存储管理。许多其他操作需要其他隐蔽存储管理发生，大多涉及分配和回收。,6,10.2 程序员和系统控制的存储管理,程序员被允许在何种程度上直接控制存储管理？ C允许程序员通过Malloc和free控制存储。 而很多高级语言不允许程序员直接控制存储。 程序员控制存储管理的困难是两方面的：会大大增加程序员的负担，也会干扰必须的系统管理。 没有任何高级语言允许程序员全面管理存储。一方面，他不可
4、能管理系统数据，最多只能管理局部数据。另一方面，对程序员来说也是危险的，因为可能导致微妙的错误。 程序员管理存储的优点在于： 系统很难确定什么时候存储可被有效地分配和释放。 而程序员可以精确地知道什么时候某特定结构是需要的，什么时候不再需要。 这种程度的确定是一个争议的话题，涉及性能、灵活性和安全间的权衡。,7,存储管理阶段,有三个基本方面： 初始分配：在执行开始时，每个存储片可能是自由的或被分配使用，如果自由，则可在执行过程中分配，存储管理需要保持自由存储区的轨迹。 恢复：被分配过的存储块可能重新可用。因此，必须收回，简单的回收可以是堆栈指针的重定位，复杂的可以是垃圾回收。 合并和重用：回收
5、的存储可能是立即可重用的，也可能需先将小碎片合并为大的存储块。重用和初始分配的机制一样。,8,10.3 静态存储管理,静态分配是最简单的分配形式在翻译时分配并在执行中保持不变。 通常，代码段和系统程序是静态分配的，静态分配不需要运行时存储管理，无需回收和重用。 一般在Fortran的实现中，所有存储都是静态分配的。 静态存储分配效率高，因为不需要为运行时存储管理花费时间和空间。 翻译器可为所有数据项生成直接的左值，但不适合递归子程序调用。在递归中，数据结构大小依赖于计算或输入数值。,9,10.4 基于栈的存储管理,最简单的运行时存储管理技术是堆栈。 在执行开始时，自由存储为内存中的顺序块，按栈
6、方式进行管理，分配和回收均在一端进行。 栈指针被用于控制存储管理，总是指向栈顶，即下一个可用的存储位置，被视为被用存储和自由存储的分界点。 合并（compaction）作为释放存储动作的一部份自动发生。 因为需要存储的程序和数据元素是和子程序激活紧紧关联的，这是一个严格嵌套的子程序调用的后进先出结构。当子程序被调用，则在栈顶创建一个新的激活记录。 大多数Pascal实现采用一个单一的中央激活记录栈，再加上静态分配的系统程序和子程序代码区域。,10,PASCAL中存储组织,图 (a)是典型的Pascal子程序激活记录结构 图 (b)是Pascal运行时存储组织。,11,基于栈的存储管理,LISP
7、实现中栈略有不同。 子程序（函数）调用也是严格嵌套，栈用于激活记录。 每个激活记录包含一个返回点及表达式计值和参数传递的临时区域。 局部引用环境也可能在同一栈中分配，但允许程序员直接操纵这些关联的情形除外。 因此，它们通常存放在分开的栈中，表示为了一个链接表，称为A表。 LISP实现需要一个堆存储区域，通过自由空间表和垃圾回收来管理。,12,执行时的LISP存储组织,13,10.5 堆存储管理,堆是一个存储块，其中片段被以某种相对无结构的方式分配和释放。 堆管理的需要来自当语言允许在程序执行中任意点分配和回收存储。 堆存储管理技术可分为两类：根据分配元素是定长或变长。,14,堆存储管理：固定长
8、元素,针对定长的堆管理。 假定定长的元素占据N个字，通常N为1或2，假定堆为连续区域。通常被概念地分为K个元素，每个长度为N，KN是总尺寸。 初始时K个元素被链接在一起形成一自由空间表。 每次从头部分配，也从头部回收。,15,堆存储管理：固定长元素,自由空间表结构,16,堆存储管理：固定长元素,恢复：引用记数和垃圾回收 将新的自由存储连到自由空间表是简单的；只要它可被标记和恢复即可。但标识和恢复是相当困难的，需要确定堆中哪个元素可再用。 有三种解决方案： 程序员或系统显示归还这是最简单的恢复技术。 引用计数 垃圾回收,17,定长堆存储管理：恢复（1）,程序员或系统显示归还 元素被显式地标识为“
9、free”并归还给自由空间表。 对用于系统目的的元素，每个系统例程负责归还空间，通过显式的free调用。 显式归是一种很自然的恢复技术，但它并不总是可行的，问题来自于“垃圾”和“悬空引用”。 如垃圾增多，可用存储将逐步减少，直至程序不能再运行。 悬空引用可能引发错误，使剩余的存储空间丢失，或使其他空间被看成自由空间。,18,定长堆存储管理：恢复（1）,显示归还 对运行时系统要避免垃圾和悬空引用是非常困难的。为克服这些问题，引用记数（检查指向给定元素的指针数，使得不会产生悬空引用）和垃圾回收（允许创建垃圾，但不允许悬空引用）是变通方法。,19,定长堆存储管理：恢复（2）,引用记数 在每个元素中，
10、使用额外空间作为引用记录器，记下指向该元素的指针数。初始分配一个元素其指针记数为1，每次新有指针指向它，则计数加1，每次有指针被删去，则计数减1。当记数为0时，则可能回收。 在大多数情况下，该方法可以避免垃圾和悬空引用。 引用计数还可以对程序显式使用free操作进行保护。如记数不为0，则忽略free操作。,20,定长堆存储管理：恢复（2）,引用记数 引用计数最大的困难是维护代价大，并会降低执行效率。 例：考虑P：=Q，P、Q均为指针，如考虑计数，则操作步骤为： 1、访问P指向的元素，将其引用数减1。 2、测试结果如为0，归还该元素到自由空间表。 3、拷贝Q中左值到P。 4、访问Q指向的元素，将
11、其引用数增1。 本技术在并行处理系统中是常用的。,21,定长堆存储管理：恢复（3）,垃圾回收 悬空引用远比垃圾更为危险，但二者是相关的。悬空引用是由于过早释放空间而产生的，垃圾则是由于过晚还未释放。同时解决两个总是通常代价太大。 基本策略是允许垃圾产生以避免悬空引用。当自由空间表耗尽且需要更多的存储时，计算暂时挂起，执行额外的垃圾回收过程。,22,定长堆存储管理：恢复（3）,垃圾回收 回收涉及两个阶段： 1.标记：此时，堆中的活动元素（是可访问数据结构的一部分）需被标记。每个元素中有一个位，初始现为“on”，标志算法将活动元素的标志位设为“off”。 2.Sweep（扫除）：顺序扫描堆，凡是“
12、off”的元素被略过，“on”元素被回收。 其中，标记部分是困难的，检查一个元素并不一定能正确地推断出其状态。 什么时候一个堆元素是活动的？ 当有来自堆外的指针或来自另一个活动的堆元素的指针。,23,定长堆存储管理：恢复（3）,垃圾回收 对这个标记过程有三个关键假设： 1、任何活动元素必须从堆外开始的指针链可达。 2、必须可以标识堆外的每个指向堆中元素的指针。 3、必须可以标识任何堆元素中的指针域（指向其他堆元素）。 LISP满足这三个假设，因而允许垃圾回收。如这些假设不会满足，则将可能无法标志某些元素。如C中，假设2、3不成立。 在LISP中，每个堆元素有相同格式，有两个指针域和一个系统数据
13、位串，这些指针在相同位置，满足假设3。 只有少量的系统数据结构包含到堆的指针，从这些结构开始标记，可保证所有外部指针的标识，满足假设2。 不可能到达一个堆元素而不通过堆外开始的指针链，满足假设1。,24,定长堆存储管理：恢复（3）,LISP堆和存储分配 f1(x,y,z)=(cons x (f2 y z) f2(v,w)=(cons v w),25,堆存储管理：可变长元素,涉及可变长元素的分配和回收的堆存储管理更为困难。这种情况发生在如下情形，如：空间用于对程序员定义的结构的分配，任务的激活记录等。 主要困难是回收空间的再利用问题，因为回收的块可能大小不适合使用。 初始分配和重用 对定长元素，
14、可将整个堆分成一组元素，然后基于自由空间表进行分配。 对变长元素，我们希望将堆作为尽可能大的自由存储块，使用堆指针来完成分配。,26,堆存储管理：可变长元素,初始分配和重用 当堆指针最终到达堆的尾部，归还的自由空间必须被重用，有两种重用可能性： 1、使用自由空间表，查找表中适当大小的块来分配。 2、通过将所有活动元素移向堆的一端而合并自由空间，使自由空间作为一个单块，设置堆指针指向该块的开始。,27,变长堆存储管理,直接从自由空间表重用 当请求一N字元素时，扫描自由空间表中N字块或多于N字的块。N字块可直接使用，多于N字块需分成两个块，其中N字块被使用，剩余块归还自由空间表。 1、最先适用方法
15、：使用最先找到的N字块或多于N字块。 2、最好适用方法：选用自由表中最小的N字块或多于N字块。 如将自由空间表中元素按大小排序，可使分配更为高效，然而，代价将花在排序过程中。,28,变长堆存储管理,带变长块的恢复 大致和定长块的恢复差不多，也存在垃圾和悬空引用问题。 垃圾回收仍是可用技术，标记的方法差不多，但回收会有困难。 回收需扫描元素，现在的问题是元素间边界的确定。 最简单的方法：结合标志位（在每个块的第一个字中），维护存储块的长度。根据块长度确定边界，相邻块可先合并。 垃圾回收也可在每次回收时将回收块都合并起来，从而不需自由空间表，只要一个堆指针。,29,变长堆存储管理,合并和内存片数问题。 变长元素分配带来的问题就是内存片段问题。 自由空间最初是一整块，最后变成碎片。 因此，有必要将其合并成大的块以便再用。 有两种合并方法： 1、部分合并：活动块不能被移动（或移动代价太高），只有相邻块可合并。 2、完全合并：活动块可移动到堆的一端，使自由空间在另一端形成连续块。,
