【学习课件】第十章目标程序运行时的存储组织

第十章目标程序运行时的存储组织编译原理核心课程·运行时内存管理机制详解Contents本章内容概览编译原理中存储管理与过程调用的核心机制，从静态分配到动态堆栈的完整知识脉络。01存储组织概述运行时内存布局与分配策略02静态存储分配编译期确定的内存管理方案03栈式动态存储分配过程调用与递归的核心机制04堆式动态存储分配动态数据结构的内存管理05过程参数传递值传递、引用传递与地址传递CHAPTER01存储组织概述理解目标程序运行时的内存布局与分配策略分类RuntimeStorage运行时存储组织的核心问题编译器在生成目标代码前必须规划内存分配策略，因为程序运行时的数据存储、过程调用和动态对象创建都依赖于合理的内存布局。01编译器职责延伸：代码生成不仅要翻译语法结构，还需为每个数据对象确定存储位置和访问方式，这是目标代码正确执行的前提。存储位置+访问方式02内存预留必要性：程序运行前必须划分代码区、静态数据区、栈区和堆区，各区域承担不同职责，避免运行时内存冲突和数据覆盖。代码区·静态区·栈区·堆区03数据类型决定策略：编译期可确定大小的常量用静态分配，过程局部变量用栈式分配，动态创建的对象用堆式分配，策略选择由数据特性驱动。静态·栈式·堆式DDR5内存条·物理存储介质的具象呈现MEMORYLAYOUT目标程序运行时的内存布局程序运行时内存被划分为代码区、静态数据区、栈区和堆区四个核心区域，各区域按职责分离管理。栈区与堆区相向增长的设计最大化利用了可用内存空间。01代码区存放编译后的机器指令，大小在编译阶段完全确定，运行时只读不可修改。该区域由操作系统保护，防止程序意外或恶意篡改指令内容，确保执行流程的稳定性与安全性。CODESEGMENT·READ-ONLY02静态数据区存储全局变量和static变量，编译时即可确定大小和地址，程序全程存在。该区域细分为已初始化数据段与未初始化数据段（BSS），分别存放不同生命周期的静态数据。STATICDATA·GLOBALSCOPE03栈区管理函数调用的局部变量和上下文，采用后进先出原则，由编译器自动生成管理代码。每次函数调用会压入栈帧，返回时自动弹出，内存分配与释放极为高效。STACK·LIFOAUTO-MANAGED04堆区支持动态内存申请与释放，用于不确定大小的数据对象，需程序员或垃圾回收器显式管理。堆内存从低地址向高地址增长，与栈区相向扩展，形成高效的内存利用模式。HEAP·DYNAMICALLOCATIONMEMORYALLOCATION存储分配策略的分类框架存储分配策略按分配时机分为静态分配与动态分配两大类，动态分配进一步细分为栈式和堆式。三种策略各有适用场景，共同支撑起现代编程语言的内存管理能力。静态分配策略编译时刻确定所有数据对象的存储位置，运行时地址固定不变，适用于大小和生命周期均可预知的数据编译时栈式动态分配运行时按过程调用顺序自动分配和回收内存，后进先出的管理方式天然支持递归和嵌套调用LIFO堆式动态分配运行时按需申请和释放任意大小的内存块，支持动态数据结构如链表、树的创建，但管理复杂度更高按需分配语言特性组合FORTRAN仅用静态分配，C/C++三种策略并用，Java以栈式+堆式为主并由GC自动回收堆内存C++/JavaStorageManagement语言特性对存储管理的影响程序设计语言的数据类型系统、作用域规则和过程嵌套机制直接决定了存储管理的复杂度。支持动态类型、块结构和过程嵌套的语言需要更精密的内存分配和访问机制。01数据类型影响静态类型语言可在编译时确定变量大小，动态类型语言如Python需在运行时分配可变大小的存储空间编译时vs运行时02作用域规则影响块结构语言要求支持嵌套的变量可见性，需要栈式分配来管理不同作用域层次的局部变量栈式分配03过程嵌套影响Pascal等支持过程嵌套的语言需要访问链机制，使内层过程能正确访问外层过程的非局部变量访问链04递归支持需求允许递归调用的语言必须采用栈式分配，每次递归调用需要独立的活动记录保存各自的局部状态活动记录CHAPTER02静态存储分配编译期确定的内存管理方案及其适用条件MemoryAllocation静态存储分配的基本原理静态存储分配在编译阶段为所有数据对象分配固定地址，运行时不再进行内存的分配与回收。这种策略实现简单、执行高效，但对语言特性有严格限制。编译期编译期地址绑定编译器为每个变量确定固定的内存地址，地址信息直接编入目标代码。这种绑定方式使得程序在加载时即可确定所有数据位置，无需运行时计算偏移量，显著降低了启动延迟。核心优势地址解析完全前置，运行时零计算成本零开销运行时零开销程序执行过程中不需要动态分配或回收内存，没有栈操作或堆管理的额外指令。内存布局在编译完成时即已固化，执行效率达到理论最优，特别适用于资源受限的嵌入式系统。性能特征无内存碎片，访问延迟恒定可预测固定地址地址持久不变同一变量在程序多次执行中绑定到相同的存储单元，地址空间布局具有高度可重复性。这一特性便于调试和内存分析，但也限制了程序的灵活性，无法支持递归调用和动态数据结构。典型应用全局变量、静态变量、常量数据段MemoryAllocation静态存储分配的适用条件采用静态存储分配的语言必须满足三个严格条件：数组边界为常量、禁止递归调用、禁止动态创建数据。这些限制保证了所有数据对象的大小和生命周期在编译时完全可确定。DIMENSIONA(100,200)数组边界常量约束数组的上下界必须是编译时常量表达式，不能是变量或运行时计算的表达式。NoRecursion禁止递归调用约束过程中不能直接或间接调用自身，否则无法在编译时为每次调用预分配独立的活动记录空间。Nomalloc/new禁止动态创建约束不允许在运行时申请任意大小的内存块，所有数据结构大小必须在编译时确定。FORTRAN典型语言案例早期FORTRAN采用纯静态分配，全局变量和局部变量都有固定地址，虽然限制多但执行效率极高。StorageAllocation静态分配与动态分配对比分析静态分配以牺牲灵活性换取运行时效率，动态分配以运行时开销换取表达能力。现代编程语言通常结合两种策略，用静态分配处理全局数据，用动态分配处理过程调用和动态对象。对比维度静态存储分配动态存储分配分配时机编译阶段确定所有地址运行阶段按需分配回收运行时开销零开销，无内存管理指令有栈操作或堆管理开销灵活性低，数据大小必须编译时确定高，支持任意大小数据递归支持不支持完整支持动态数据结构不支持完整支持典型语言FORTRAN、早期BASICC/C++、Java、Python静态分配简单高效但限制多，动态分配灵活但有运行时开销，现代语言通常两者结合使用CHAPTER03栈式动态存储分配支持过程调用与递归的核心内存管理机制RUNTIMEMEMORY活动记录的结构与组成活动记录是过程每次执行时分配的连续存储区，包含临时变量、局部数据、机器状态、访问链、控制链、返回值和参数等域。不同语言根据特性需求对活动记录结构进行裁剪。数据域组成01临时变量域—存放表达式计算的中间结果如a+b*c需要先算b*c再与a相加02局部数据域—存放过程内部定义的变量生命周期与过程执行期一致03实在参数域—存放调用者传递的参数值位置靠近调用者活动记录以提高访问效率控制域组成01机器状态域—保存调用前的寄存器值和返回地址确保过程返回后能恢复执行环境02控制链—指向主调过程的活动记录用于过程返回时恢复栈指针到正确位置03访问链—指向词法外层过程的活动记录支持嵌套过程中对非局部变量的访问Runtime·StackLayout活动记录的域排列设计活动记录的域排列遵循效率优先原则：参数和返回值靠近调用者以便快速传递，固定长度项居中，可变长度项置于尾部。01参数与返回值前置放在活动记录开始位置，紧邻调用者活动记录，减少参数传递时的地址计算开销。这种布局使得调用约定中的参数传递更加高效，无需额外的指针运算即可定位参数。02固定长度项居中控制链、访问链、机器状态等固定大小域放在中间，编译时可确定其相对偏移量。静态链接和动态链接的指针位置固定，便于代码生成阶段直接嵌入偏移常量。03可变长度项后置局部数组、动态分配区等编译时大小不确定的数据放在尾部，避免影响前面各域的固定偏移。栈指针向下增长时，这些区域不会挤压固定布局的域。04栈顶指针定位top_sp指向局部数据起始位置作为基地址，所有域的访问通过"基地址+偏移"实现。寄存器间接寻址配合立即数偏移，生成高效的机器代码。RuntimeMemoryLayout变量地址的计算方式变量地址由活动记录首地址D与偏移量offset(x)共同决定，即地址=D+offset(x)。根据D和offset的确定时机，变量分为静态、半静态和动态三类，对应不同的分配策略。地址计算公式变量x的运行时地址=D+offset(x)，其中D为活动记录首地址，offset(x)为变量在记录内的偏移D+offset(x)静态变量D和offset(x)均在编译时确定，地址完全固定，可直接编入目标代码，对应静态存储分配Static半静态变量offset(x)编译时确定，D运行时确定，如普通函数的局部变量，对应栈式动态分配Stack动态变量offset(x)在编译和运行时均不确定，如变长数组或动态对象，需要堆式分配或运行时计算HeapCOMPILERRUNTIME过程调用的调用序列调用序列是过程调用时建立活动记录的一系列操作，包括参数传递、状态保存、链设置和控制转移。调用序列的正确实现是过程能够正确执行和返回的基础。01参数传递—调用者计算实际参数的值，将其放入被调用者活动记录的参数域或通过寄存器传递参数域/寄存器02状态保存—将当前机器状态（寄存器值）保存到被调用者活动记录的机器状态域，以便返回时恢复机器状态域03返回地址保存—将调用指令的下一条指令地址存入活动记录，确保过程执行完毕后能回到正确位置继续执行返回地址04控制链与访问链设置—控制链指向调用者活动记录，访问链指向词法外层活动记录（嵌套语言需要）嵌套语言05栈指针调整与跳转—将栈顶指针移动到被调用者活动记录的局部数据起始位置，然后跳转到过程入口地址栈顶指针Runtime·ReturnSequence过程返回的返回序列返回序列是过程执行完毕后恢复到调用者状态的一系列操作，与调用序列对称。包括返回值处理、状态恢复、栈空间释放和控制转移，确保调用者能够正确继续执行。01返回值处理——将被调用过程的计算结果放入返回值域或指定寄存器，供调用者后续使用02控制链回溯——通过当前活动记录的控制链找到调用者的活动记录位置，确定恢复目标03机器状态恢复——将活动记录中保存的寄存器值恢复到对应寄存器，还原调用前的执行环境04栈空间释放——将栈顶指针回退到调用者活动记录的位置，释放被调用过程占用的全部栈空间05控制转移——根据保存的返回地址跳转回调用者，从调用指令的下一条指令继续执行StackFrameManagement递归调用的栈帧管理示例递归调用时每次调用都创建独立的活动记录，保存各自的参数和局部变量。栈的后进先出特性天然匹配递归的调用-返回顺序，使得每次递归调用互不干扰。01调用阶段栈增长fact(3)→fact(2)→fact(1)依次调用，每个调用在栈顶创建新的活动记录，栈不断向高地址增长。栈增长02独立状态保存每个活动记录保存各自的参数n值和返回地址，fact(3)的n=3、fact(2)的n=2互不影响。参数隔离03返回阶段栈收缩fact(1)返回1后弹出，fact(2)计算2×1=2后弹出，fact(3)计算3×2=6后弹出，栈逐步收缩。逐层返回04递归终止保障每次调用有独立的栈帧，递归深度仅受栈空间大小限制，理论上可支持任意深度的递归。深度无限StaticScope·AccessChain访问链的作用与实现机制访问链指向词法外层过程的活动记录，使内层过程能够访问外层定义的非局部变量。它是支持过程嵌套的语言（如Pascal）实现静态作用域规则的关键机制。01词法作用域需求Pascal等语言允许过程嵌套定义，内层过程需访问外层变量，访问链提供跨层级的访问路径。嵌套定义·跨层级访问02访问链与控制链区别控制链指向动态调用者，访问链指向词法外层；两者在过程作为参数传递时可能指向不同的活动记录。词法vs动态03多级访问实现访问嵌套n层外层的变量需沿访问链跳转n次，每次到达一个新的词法外层活动记录。n次链式跳转04Display表优化为减少访问链遍历开销，可用Display数组直接记录各嵌套层级的活动记录地址，将O(n)访问降为O(1)。O(n)→O(1)COMPILERTECHNOLOGYDisplay表优化：加速非局部变量访问Display表用指针数组记录各嵌套层级活动记录的地址，将访问链的O(n)遍历优化为O(1)直接访问。这是编译器优化嵌套过程变量访问效率的经典技术。Display表结构d[i]指针数组，d[i]指向当前活动的第i层嵌套过程的活动记录，直接定位无需链式遍历d[i]指针数组进入过程时更新进入第k层过程时，保存旧的d[k]值，将d[k]更新为当前活动记录地址，建立新的层级映射层级映射退出过程时恢复退出第k层过程时，将d[k]恢复为之前保存的旧值，确保外层过程的Display映射正确旧值恢复效率对比访问第i层变量只需一次d[i]寻址，而访问链方式需要k-i次跳转，嵌套越深优化效果越显著O(1)寻址CHAPTER04堆式动态存储分配支持动态数据结构的灵活内存管理机制MemoryManagement·HeapAllocation堆式存储分配的基本概念堆式分配允许程序在运行时按需申请和释放任意大小的内存块，不受后进先出约束。它是支持动态数据结构的基础，但管理复杂度高于栈式分配，需要处理内存碎片问题。任意顺序分配释放堆允许以任意顺序申请和归还内存，不受栈式分配后进先出的约束，支持复杂的生命周期管理。无序释放动态数据结构支撑链表、树、图等数据结构需要在运行时动态创建节点，堆式分配提供所需的灵活内存管理。链表·树·图内存碎片问题频繁的分配释放会产生碎片，外部碎片导致空闲空间不连续，内部碎片导致分配块大于实际需求。碎片化典型API示例C语言的malloc/free、C++的new/delete、Java的new配合GC，都是堆式分配的具体实现。malloc/newMemoryManagement堆内存分配算法堆分配算法需要在分配速度和空间利用率之间权衡。首次适配追求速度，最佳适配优化空间利用，最差适配试图平衡两者。实际系统通常采用分层策略结合多种算法。首次适配FirstFit从堆起始位置扫描，找到第一个足够大的空闲块即分配，速度快但可能在堆前部产生碎片速度优先最佳适配BestFit扫描全部空闲块，选择大小最接近请求的块分配，空间利用率高但扫描开销大空间优先最差适配WorstFit选择最大的空闲块分配，剩余部分仍可作为较大块使用，适合大小差异明显的分配请求最大块循环首次适配NextFit从上次分配位置继续扫描，避免重复扫描堆前部，分配速度更均匀均匀扫描MEMORYMANAGEMENT内存碎片问题与解决策略内存碎片分为外部碎片和内部碎片，是堆式分配的核心挑战。紧凑技术可以消除外部碎片但代价高，分离适配通过预分类减少碎片产生，是现代堆管理器的常用策略。碎片类型与成因解决策略外部碎片空闲空间总量充足但分散不连续，无法满足大块分配请求，由频繁的分配释放操作累积产生。典型场景：长时间运行的服务器进程内部碎片分配的内存块略大于实际请求，浪费的空间位于分配块内部，由对齐要求或最小分配粒度导致。典型场景：固定大小的内存池分配紧凑技术Compaction移动已分配块使空闲空间连续，需要更新所有引用指针，通常由垃圾回收器在回收时顺便执行。代价：需要停止世界或增量更新指针分离适配SegregatedFit维护多个按大小分类的空闲链表，不同大小的请求从对应链表分配，减少碎片并提高速度。优势：O(1)分配，现代malloc实现首选MEMORYMANAGEMENT垃圾回收：自动堆内存管理垃圾回收通过可达性分析自动识别并回收不再使用的堆内存对象，避免手动内存管理带来的泄漏和悬空指针问题。这是Java、Python等现代语言内存管理的核心机制。可达性分析原理从根对象出发遍历对象图，所有可达对象标记为存活，不可达对象即为垃圾。根遍历标记-清除算法第一遍标记所有存活对象，第二遍清除未标记对象并回收空间，实现简单但会产生碎片。两遍扫描复制算法将存活对象复制到新内存区域，同时完成紧凑，消除碎片但需要双倍空间和更新引用。零碎片分代回收策略根据对象存活时间分代管理，年轻代频繁回收，老年代较少回收，提高整体回收效率。分代管理CHAPTER05过程参数传递值传递、引用传递与地址传递的实现机制与语义差异ParameterPassing参数传递方式概述参数传递决定了实参与形参之间的数据关系。值传递复制数据保证隔离性，引用传递共享数据提高效率，不同方式在语义、效率和安全性上各有权衡。值传递计算实参值并复制给形参，形参修改不影响实参。安全但有复制开销，C语言默认方式。CallbyValue·C引用传递传递实参的内存地址，形参与实参共享同一存储。修改形参直接影响实参，C++的引用参数。CallbyReference·C++值结果传递进入时复制值到形参，返回时复制结果回实参。结合值传递的隔离性与引用传递的双向通信。CallbyValue-Result名字传递将实参表达式本身传递，每次使用时重新求值。ALGOL60采用，灵活性高但效率低。CallbyName·ALGOL60ParameterPassing值传递的实现与特点值传递将实参的值复制到形参的独立存储空间，保证调用者与被调用者数据隔离。语义清晰安全，但大对象的复制开销是其主要缺点。01实现步骤调用者先计算实参表达式的值，然后将值复制到被调用者活动记录的形参域，形参拥有独立的存储空间。02数据隔离保证形参是实参的副本，被调用过程对形参的任何修改只影响副本，不会改变调用者的原始数据。03复制开销问题对于大型结构体或数组，值传递需要逐字节复制数据，时间和空间开销可能显著影响性能。04C语言的实践C语言所有参数均为值传递，需要修改实参时显式传递指针，通过指针间接访问实现"模拟"引用传递。参数传递机制引用传递的实现与特点引用传递将实参的地址传递给形参，两者共享同一存储空间。传递效率高且支持双向通信，但可能产生意外的副作用，需要程序员谨慎使用。地址传递实现调用者计算实参的内存地址并传递给被调用者，形参存储的是地址值，访问时需要解引用操作。解引用数据共享特性形参与实参指向同一存储位置，被调用过程对形参的修改会直接反映到调用者的实参上。双向通信高效传递优势无论实参对象多大，只需传递一个地址（通常4或8字节），避免了大对象的复制开销。4–8字节副作用风险被调用过程可能意外修改调用者数据，需要const引用等语言机制来约束只读访问，保证安全性。constParameterPassing参数传递方式对比分析不同参数传递