运行时存储空间的组织.ppt

第九章 运行时存储空间的组织,本章内容讨论一个活动记录中的数据安排程序执行过程中，所有活动记录的组织方式存储器的组织与存储分配的策略,9.1 目标程序运行时的活动,9.1.1 过程的活动活动过程的一次执行称为过程的一次活动。活动记录过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录(Activation Record)活动的生存期 过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间。,9.1 目标程序运行时的活动,9.1.2 参数传递传地址（传引用）（call by reference）把实在参数的地址传递给相应的形式参数。传值（call by value）把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始工作时，首先把这些值抄进自己的形式单元中，然后就好像使用局部名一样使用这些形式单元。,9.1 目标程序运行时的活动,传名（call by name）：也称为“换名”过程调用的作用相当于把被调用段的过程体抄到调用出现的位置，把其中任一出现的形式参数都替换成相应的实在参数（文字替换）。,9.2 运行时存储器的划分,9.2.1 运行时存储器的划分 编译程序为了使它编译后得到的目标程序能够运行，要分配逻辑存储空间。程序运行时操作系统为进程分配物理存储，并完成逻辑物理空间的映射。对逻辑空间应该进行划分，其中包括生成的目标代码、数据对象和跟踪过程活动的控制栈（运行时成为进程的code,data和stack区）。目标代码的大小在编译时可以确定，所以编译程序可以把它放在一个静态确定的区域。,运行时存储器的划分：地址空间共多大？,9.2.2 活动记录（Activation Record）为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录。活动记录一般包含如下内容：临时单元内情向量局部变量形式单元静态链动态链返回地址,9.2.3 存储分配策略1 静态分配静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。2 动态分配栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配,9.3 静态存储分配,静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。,9.3 静态存储分配,静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。,9.3 静态存储分配,静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。,9.3 静态存储分配,静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。,9.3 静态存储分配,静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的。,9.3 静态存储分配,静态分配给语言带来限制递归过程不被允许,9.3 静态存储分配,静态分配给语言带来限制递归过程不被允许数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的,9.3 静态存储分配,静态分配给语言带来限制递归过程不被允许数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的数据结构不能动态建立,9.4 简单的栈式存储分配,过程定义不许嵌套，但允许过程的递归调用。C就是这样的一种语言。,9.4.1 C的活动记录 C的活动记录有以下四个项目。连接数据，有两个：（1）老SP值，即前一活动记录的地址；（2）返回地址。参数个数。形式单元（存放实在参数的值或地址）。过程的局部变量、数组内情向量和临时工 作单元。,9.4.2 C的过程调用、过程进入和过程返回void main()int e1=30;int e2=20;int e3=plus(e1+1,e2);int plus(int a,int b)return a+b;,Stack grows down,high addresses to low%esp points to lowest allocated position on stackPushl%esp=4,write word to memory%esp points toPoplRead word from memory%esp points to,%esp+=4 Call instructionPushes%eip(pointer to next instruction)Jumps to targetRetPops into%eip(returns to next next instruction after call)ar_c.asm,9.5 嵌套过程语言的栈式实现,嵌套层次：如过程 Q是在层数为 i的过程 P内定义，并且 P是包围 Q的最小过程，那么Q的层数就为 i1。sortreadarrayexchangequicksortpartition,9.5 嵌套过程语言的栈式实现,过程嵌套深度sort1readarray2exchange2quicksort2partition3,9.5 嵌套过程语言的栈式实现,过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度,9.5 嵌套过程语言的栈式实现,1)静态链图9.15的程序p260活动记录中的静态链思考：能允许P直接调用R么？2)display把被调用过程到主程序的最新活动记录地址集中在一起，形成display，放在被调用过程的活动记录中。访问速度比静态链快。p263的display,9.6 堆式动态存储分配,堆式的动态存储 如果一个程序语言允许用户自由地申请数据空间和退还数据空间，由于空间的使用未必服从“先请后还，后请先还”的原则，因此，栈式的动态分配方案就不适用了。在这种情况下通常使用一种称之为堆式的动态存储分配方案。,9.6 堆式动态存储分配,9.6.1堆式动态存储分配的实现1.定长块管理 堆式存储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表,9.6 堆式动态存储分配,2.变长块管理（1）首次满足法：只要在空闲块链表中找到满足需要的一块，就进行分配。（2）最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户，则系统在分配前首先要对空闲块链表从头至尾扫描一遍，然后从中找出一块不小于申请块且最接近于申请块的空闲块分配。（3）最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部分分配给用户。,9.6 堆式动态存储分配,9.6.2 隐式存储回收 garbage collection回收子程序需要知道分配给用户程序的存储块何时不再使用。程序变量和堆上的对象构成有向图。程序变量是根。如果存在从某个根到它的路径，则该结点是可达的(reachable)。,9.6 堆式动态存储分配,1)标记(mark)阶段标记所有可达的存储对象。所有未标记的对象必然是垃圾。2）回收(sweep)阶段把所有未标记的存储对象收回到空闲表；然后清除所有的标记。,例 题,int*f()int a=100;return,例 题,int*f()int a=100;return 程序运行结果？ctest1.asm,