九章节运行时存储空间组织

《九章节运行时存储空间组织》由会员分享，可在线阅读，更多相关《九章节运行时存储空间组织（57页珍藏版）》请在装配图网上搜索。

1、第九章第九章 运行时存储空间的组织运行时存储空间的组织本章内容本章内容 讨论一个活动记录中的数据安排讨论一个活动记录中的数据安排 程序执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式 存储器的组织与存储分配的策略存储器的组织与存储分配的策略名字名字存储单元存储单元状态状态值值环境环境9.1 9.1 目标程序运行时的活动目标程序运行时的活动9.1.1 9.1.1 过程的过程的活动活动活动活动过程的一次执行称为过程的一次过程的一次执行称为过程的一次活动。活动。活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间,后

2、者称为活动记录。后者称为活动记录。活动的生存期活动的生存期 过程过程P一个活动的生存期，指的是从执行该过程体一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执第一步操作到最后一步操作之间的操作序，包括执行行P时调用其它过程花费的时间。时调用其它过程花费的时间。9.1 9.1 目标程序运行时的活动目标程序运行时的活动9.1.2 参数传递参数传递传地址（传地址（call by reference）把实在参数的地址传递给相应的形式参数。把实在参数的地址传递给相应的形式参数。传值（传值（call by value）把实在参数的值计算出来并存放在一个被调把实在参数的值计算

3、出来并存放在一个被调用段可以拿得到的地方。被调用段开始工作用段可以拿得到的地方。被调用段开始工作时，首先把这些值抄进自己的形式单元中，时，首先把这些值抄进自己的形式单元中，然后就好像使用局部名一样使用这些形式单然后就好像使用局部名一样使用这些形式单元。元。9.1 9.1 目标程序运行时的活动目标程序运行时的活动 传名（传名（call by name）：）：也称为也称为“换名换名”过程调用的作用相当于把被调用段的过过程调用的作用相当于把被调用段的过程体抄到调用出现的位置，把其中任一程体抄到调用出现的位置，把其中任一出现的形式参数都替换成相应的实在参出现的形式参数都替换成相应的实在参数（文字替换）

4、。数（文字替换）。9.2 9.2 运行时存储器的划分运行时存储器的划分9.2.1 运行时存储器的划分运行时存储器的划分 编译程序为了使它编译后得到的目标程序能编译程序为了使它编译后得到的目标程序能够运行，要从操作系统中获得一块存储空间。够运行，要从操作系统中获得一块存储空间。对这块提供运行的空间应该进行划分以便存对这块提供运行的空间应该进行划分以便存放，其中包括生成的目标代码、数据对象和跟放，其中包括生成的目标代码、数据对象和跟踪过程活动的控制栈。目标代码的大小在编译踪过程活动的控制栈。目标代码的大小在编译时可以确定，所以编译程序可以把它放在一个时可以确定，所以编译程序可以把它放在一个静态确定

5、的区域。静态确定的区域。运行时存储器的划分：运行时存储器的划分：目目 标标 代代 码码静静 态态 数数 据据栈栈堆堆9.2.2 活动记录活动记录（Activation Record）为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录活动记录。活动记录一般包含如下内容：临时单元内情向量局部变量形式单元静态链动态链返回地址9.2.3 存储分配策略存储分配策略1 静态分配静态分配静态分配策略静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。2 动态分配动态分配栈式动态分配策略栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行

6、时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。堆式动态分配策略堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。9.2 9.2 运行时存储器的划分运行时存储器的划分 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归9.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留9

7、.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量9.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式9.2

8、9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递9.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问

9、非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递9.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递 存储块能否在程序

10、控制下动态地分配存储块能否在程序控制下动态地分配9.2 9.2 运行时存储器的划分运行时存储器的划分影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递 存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配 存储块是否必须显式地释放存储块是否必须显式地释放9.3 9.3 静态存储

11、分配静态存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。要运行时的任何支持。9.3 9.3 静态存储分配静态存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。要运行时的任何支持。绑定的生存期是程序的整个运行时间。绑定的生存期是程序的整个运行时间。9.3 9.3 静态存储分配静态存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。要运行时的任何支持。绑定的生存期是程序的整个运行时间。

12、绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。制上一次离开时的一样。9.3 9.3 静态存储分配静态存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。要运行时的任何支持。绑定的生存期是程序的整个运行时间。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。制上一次离开时的一样。每个活动记录的大小是固定的。每个活动记录的大小是固定的。9.3 9.3 静态存储分配

13、静态存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。要运行时的任何支持。绑定的生存期是程序的整个运行时间。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。制上一次离开时的一样。每个活动记录的大小是固定的。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已过程调用时保存信息的地址在编译时也是已知的。知的。9.3 9.3 静态存储分配静态存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许9.

14、3 9.3 静态存储分配静态存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许 数据对象的长度和它在内存中位置的限制，数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的必须是在编译时可以知道的9.3 9.3 静态存储分配静态存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许 数据对象的长度和它在内存中位置的限制，数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的必须是在编译时可以知道的 数据结构不能动态建立数据结构不能动态建立9.3 9.3 静态存储分配静态存储分配 如果在编译时就能够确定一个程序在

15、运行时如果在编译时就能够确定一个程序在运行时所需的存储空间的大小，则在编译时就能够安所需的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。配方法叫做静态分配。FORTRAN程序的特点是：不允许过程的递程序的特点是：不允许过程的递归性；每个数据名所需的存储空间大小都是常归性；每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组）量（即不许含可变体积的数据，如可变数组）；并且所有数据名的性质是完全确定的（不允；并且

16、所有数据名的性质是完全确定的（不允许那种需在运行时动态确定其性质的名字）。许那种需在运行时动态确定其性质的名字）。9.4 9.4 简单的栈式存储分配简单的栈式存储分配 这种语言没有分程序结构，过程定义不许嵌这种语言没有分程序结构，过程定义不许嵌套，但允许过程的递归调用。套，但允许过程的递归调用。C就是这样的就是这样的一种语言。一种语言。9.4.1 C的活动记录的活动记录 C的活动记录有以下四个项目。的活动记录有以下四个项目。连接数据，有两个：连接数据，有两个：（1）老）老SP值，即前一活动记录的地址；值，即前一活动记录的地址；（2）返回地址。）返回地址。参数个数。参数个数。形式单元（存放实在参

17、数的值或地址）。形式单元（存放实在参数的值或地址）。过程的局部变量、数组内情向量和临时工过程的局部变量、数组内情向量和临时工 作单元。作单元。9.4.2 C的过程调用、过程进入、数组空间分的过程调用、过程进入、数组空间分配和过程返回配和过程返回 9.5 嵌套过程语言的栈式实现嵌套层次：嵌套层次：如过程如过程 Q是在层数为是在层数为 i的过程的过程 P内定义，并内定义，并且且 P是包围是包围 Q的最小过程，那么的最小过程，那么Q的层数就的层数就为为 i1。sortreadarrayexchangequicksortpartition9.5 嵌套过程语言的栈式实现过程过程嵌套深度嵌套深度sort1

18、readarray2exchange2quicksort2partition39.5 嵌套过程语言的栈式实现过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度度作为该名字的嵌套深度9.5 嵌套过程语言的栈式实现栈式分配栈式分配栈式分配策略在下列情况下行不通：栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持过程活动停止后，局部名字的值还必须维持9.5 嵌套过程语言的栈式实现栈式分配栈式分配栈式分配策略在下列情况下

19、行不通：栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动活得更长，被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流此时活动树不能正确描绘程序的控制流9.5 嵌套过程语言的栈式实现栈式分配栈式分配栈式分配策略在下列情况下行不通：栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动活得更长，被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流此时活动树不能正确描绘程序的控制流 不遵

20、守栈式规则的不遵守栈式规则的有有Pascal语言和语言和C语言的动语言的动态变量态变量 Java禁止程序员自己释放空间禁止程序员自己释放空间 9.6 堆式动态存储分配 堆式的动态存储 如果一个程序语言允许用户自由地申请数据空间和退还数据空间，或者不仅有过程而且有进程（process）的程序结构，那么，由于空间的使用未必服从“先请后还，后请先还”的原则，因此，栈式的动态分配方案就不适用了。在这种情况下通常使用一种称之为堆式的动态存储分配方案。9.6 堆式动态存储分配9.6.1堆式动态存储分配的实现1.定长块管理 堆式存储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，

21、每块中指定一个链域，按照邻块的顺序把所有块链成一个链表 9.6 堆式动态存储分配2.变长块管理（1）首次满足法：只要在空闲块链表中找到满足需要的一块，就进行分配。（2）最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户，则系统在分配前首先要对空闲块链表从头至尾扫描一遍，然后从中找出一块不小于申请块且最接近于申请块的空闲块分配。（3）最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部分分配给用户。9.6 堆式动态存储分配9.6.2 隐式存储回收 隐式存储回收要求用户程序和支持运行的回收子程序并行工作，因为回收子程序需要知道分配给用户程序的存储块何时不再使用。例例

22、题题 1一个一个C语言程序及其在语言程序及其在X86/Linux操作系统上的编译结操作系统上的编译结果如下。果如下。根据所生成的汇编程序来解释程序中四个变根据所生成的汇编程序来解释程序中四个变量的存储分配、作用域、生存期和置初值方式等方面量的存储分配、作用域、生存期和置初值方式等方面的区别。的区别。static long aa=10;short bb=20;func()static long cc=30;short dd=40;例例 题题 1.data|.align 4.align 4|.type cc.2,object.type aa,object|.size cc.2,4.size aa,

23、4|cc.2:aa:|.long 30.long 10|.text.globl bb|.align 4.align 2|.globl func.type bb,object|func:.size bb,2|.bb:|movw$40,-2(%ebp).value 20|.例例 题题 2main()char*cp1,*cp2;cp1=12345;cp2=abcdefghij;strcpy(cp1,cp2);printf(cp1=%sncp2=%sn,cp1,cp2);运行结果是：运行结果是：cp1=abcdefghijcp2=ghij为什么为什么cp2所指的串被修改了？所指的串被修改了？例例 题题

24、 2因为常量串因为常量串“12345”和和“abcdefghij”连续分配在常连续分配在常数区数区执行前：执行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2例例 题题 2因为常量串因为常量串“12345”和和“abcdefghij”连续分配在常连续分配在常数区数区执行前：执行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2执行后执行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2例例 题题 2因为常量串因为常量串“12345”和和“abcdefghij”连续分配在常连续分配在常数

25、区数区执行前：执行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2执行后执行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2现在的编译器大都把程序中的串常量单独存放在一个现在的编译器大都把程序中的串常量单独存放在一个只读的数据段中。只读的数据段中。例例 题题 3下面的程序运行时输出下面的程序运行时输出3个整数。试从运行环个整数。试从运行环境和境和printf的实现来分析，为什么此程序会有的实现来分析，为什么此程序会有3个整数输出？个整数输出？main()printf(“%d,%d,%dn”);例例 题题 4func(i

26、,j,f,e)short i,j;float f,e;short i1,j1;float f1,e1;printf(&i,&j,&f,&e);printf(&i1,&j1,&f1,&e1);main()short i,j;float f,e;func(i,j,f,e);Address of i,j,f,e=36,42,44,54（八进制八进制数）数）Address of i1,j1,f1,e1=26,24,20,14 例例 题题 4func(i,j,f,e)Sizes of short,int,long,float,short i,j;float f,e;double=2,4,4,4,8 sh

27、ort i1,j1;float f1,e1;printf(&i,&j,&f,&e);printf(&i1,&j1,&f1,&e1);main()short i,j;float f,e;func(i,j,f,e);Address of i,j,f,e=36,42,44,54（八进制数）八进制数）Address of i1,j1,f1,e1=26,24,20,14例例 题题 4func(i,j,f,e)Sizes of short,int,long,float,short i,j;float f,e;double=2,4,4,4,8 short i1,j1;float f1,e1;printf(&

28、i,&j,&f,&e);printf(&i1,&j1,&f1,&e1);main()为什么为什么4 4个形式参数个形式参数i,j,f,e的地址的地址 间隔和它们类型的大小不一致间隔和它们类型的大小不一致 short i,j;float f,e;func(i,j,f,e);Address of i,j,f,e=36,42,44,54（八进制数）八进制数）Address of i1,j1,f1,e1=26,24,20,14例例 题题 4 C语言编译器是不做实在参数和形式参数的个数和语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的类型是否一致的检查的，由程序员自

29、己保证它们的一致性一致性。例例 题题 4 C语言编译是不做实在参数和形式参数的个数和类语言编译是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一型是否一致的检查的，由程序员自己保证它们的一致性致性。但是对于形式参数和实在参数是不同的整型，或者但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果能得到正确的结果，条件是，当需要把高级别类型条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。数据向低级别类型数据转换时，不出现溢出。例例 题题 4 C语言编译器是不

30、做实在参数和形式参数的个数和语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的类型是否一致的检查的，由程序员自己保证它们的一致性。一致性。但是对于形式参数和实在参数是不同的整型，或者但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果能得到正确的结果，条件是，当需要把高级别类型条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。数据向低级别类型数据转换时，不出现溢出。当整型或实型数据作为实在参数时，将它们分别提当整型或实型数据作为实在参数时，将它们分

31、别提升升到到long和和double类型的数据再传递到被调用函数类型的数据再传递到被调用函数例例 题题 4 C语言编译器是不做实在参数和形式参数的个数和语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的类型是否一致的检查的，由程序员自己保证它们的一致性一致性。但是对于形式参数和实在参数是不同的整型，或者但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果能得到正确的结果，条件是，当需要把高级别类型条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。数

32、据向低级别类型数据转换时，不出现溢出。当整型或实型数据作为实在参数时，将它们分别提当整型或实型数据作为实在参数时，将它们分别提升到升到long和和double类型的数据再传递到被调用函数类型的数据再传递到被调用函数 被调用函数根据形式参数所声明的类型，决定是否被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换要将实在参数向低级别类型转换。例例 题题 4低地址低地址放高位放高位高地址高地址放低位放低位shortlong长整型和短整型长整型和短整型floatdoublee双精度型和浮点型双精度型和浮点型例例 题题 4e，8个字节个字节在在main函数函数中参数压栈中参数压栈时

33、的观点时的观点在在func函数中函数中存取形式参数存取形式参数时的观点时的观点4个字节，起始地址个字节，起始地址544个字节，起始地址个字节，起始地址442个字节，起始地址个字节，起始地址422个字节，起始地址个字节，起始地址36f，8个字节个字节j，4个字节个字节i，4个字节个字节栈的栈的增长增长方向方向参数在栈中的情况参数在栈中的情况例例 题题 5main()func();printf(Return from funcn);func()char s4;strcpy(s,12345678);printf(%sn,s);例例 题题 5main()func();printf(Return fro

34、m funcn);func()char s4;strcpy(s,12345678);printf(%sn,s);在在X86/Linux操作系统上的运行结果如下：操作系统上的运行结果如下：12345678Return from funcSegmentation fault(core dumped)例例 题题 5main()func();printf(Return from funcn);func()char s4;strcpy(s,12345678);printf(%sn,s);.返址返址控制链控制链变量变量sebp esp 栈栈低低高高例例 题题 5main()func();printf(Return from funcn);func()char s4;strcpy(s,123456789);printf(%sn,s);123456789Segmentation fault(core dumped).返址返址控制链控制链变量变量sebp esp 栈栈低低高高