ch9-10 运行时环境_(张素琴).ppt

1、1，第10章，目标程序运行时的存储组织，2，1。存储组织，为了使目标程序运行，编译器从操作系统获得一个内存存储区，其中包含：1。生成的目标代码空间；2。目标代码操作所需的数据空间，包括用户定义的变量和常数、临时工作单元、过程调用所需的联系单元以及输入和输出缓冲区；3。用于保存过程活动跟踪的控制堆栈。3，对象代码，静态数据，堆栈，活动记录，堆，1。编译后知道目标代码的大小。例如帕斯卡，C，Fortran；2.静态数据区存储可以确定编译时占用空间大小的数据；3.堆栈区：用于存储变量数据和控制信息，以管理过程活动记录，如帕斯卡，C语言。2。运行时的内存划分：数据空间，4，3。活动记录。对于pasca

2、l语言，当一个进程在操作过程中被调用时，它的活动记录被构造在栈顶；活动所需的每个信息数据项都有相同的生命周期，因此将它组织到活动记录中是很自然的。当这个过程的活动完成时，从栈顶弹出它。流程活动所需的信息被组织成一个连续的存储单元，称为活动记录。返回值、实参数、控制链、访问链、保存机器状态、局部变量、临时变量、临时变量：编译生成。保存机器状态：调用点的调用进程活动的机器状态，包括计数器和各种寄存器的值。本地数据：流程中定义的本地数量。访问链：指该活动要访问的非本地数据所在的活动记录。控制链：指向主音过程中活动记录的第一个地址。形式单元，上下文向量，连接数据，本地数据，sp，top，Pascal的

3、活动记录，6，函数环境将名称映射到l值，4，名称和存储之间的绑定，并引入两个函数，环境和状态。环境将名称映射到存储单元；状态将存储位置映射到存储在那里的值。函数状态将l值(左值)映射到r值(右值)。如下图所示。名称和存储单元的绑定是指将源程序中的数据名称映射到目标机器的存储单元的过程。7，名称，存储单元，值，存储分配，程序运行，环境，状态，l值，r值，图表：从名称到值的两阶段映射，8，编译后，知道每个进程的活动记录的长度，并将其填入相应的进程符号表中；在运行时，哪个进程被调用位于运行堆栈的顶部，并且该进程的活动记录被提升。名称所需的存储空间量由其类型决定；多字节对象以连续字节存储，第一个字节的

4、地址作为对象的地址；9，10.1三种不同的数据空间管理方法，3 .1静态存储分配：FORTRAN 3 .2堆栈存储分配：PASCAL，C 3 .3堆栈存储分配： PASCAL，C，其中分配策略由源语言的语义决定。10，10.1 .1静态存储分配，如Fortran语言，每个子程序中的局部变量相互独立，不会在不同子程序之间引用或分配。每个变量的存储空间大小是恒定的，整个程序所需的数据空间总量在编译时完全确定，这样每个变量的存储空间可以静态分配。在编译时运行时确定每个数据项在存储空间中的位置，并且该绑定在运行时不会改变。11，限制：1。知道数据对象的大小以及它们在编译时对内存位置的约束；2。该过程不

5、能递归调用；3.无法动态建立数据结构。与静态分配不同，本地名称在每个活动开始时绑定到新的存储单元，在活动结束时，活动记录从堆栈中弹出，本地名称的存储空间被释放。对于具有递归调用、变量数组和允许用户申请和释放内存空间的高级语言，有必要使用动态内存管理技术来管理内存，这主要包括两种动态内存分配方法：堆栈和堆。、10.1.2动态存储分配、13、基于堆栈存储分配原则：存储空间被组织成堆栈，活动记录的推送和弹出分别对应活动的开始和结束。每当一个子程序被调用时，它需要的数据存储空间被分配在栈顶，这部分内存存储数据空间在子程序运行时被释放；子程序的数据空间：(1)在这个过程中这个活动中有生命周期的数据对象，

6、如局部变量、参数单元、临时变量等。(2)用于管理活动记录的信息，如当A呼叫B和A被中断时，A的当前寄存器和返回地址。执行完成后，根据堆栈中的信息回复操作。适用于帕斯卡、c和Algol语言。数据空间的使用遵循“先应用后发布，再应用后发布”的原则。10.1.3堆栈动态存储分配，14，如果一种编程语言允许用户自由申请内存数据空间并返回数据空间机制，如新的，在c中删除。空间使用不符合“先申请后释放，再申请后释放”，所以堆栈存储分配不能使用。需要堆存储。堆是一个足够大的存储空间。每当需要时，就从这个空间中分配一块，并在用完时返回堆中。经过一段时间的运行，运行空间被分成许多块，需要进行整理。10.1.4堆

7、动态存储分配，15.2堆栈存储分配的实现，条件：c满足上述条件，c程序结构，全局数据描述Main()主数据描述Void R() R数据描述Void Q() Q数据描述，不允许嵌套定义，允许递归调用，10.2.1简单堆栈存储分配的实现，并且假设调用序列可以静态地确定为全局数据，活动记录的主，全局静态数据区，活动记录的Q，活动记录的R，top，sp，所以这些非主呼叫，主呼叫，然后主呼叫，教科书p235图11。程序运行时，存储组织为：17，C，每个子程序的活动记录：旧sp，返回地址，参数号n，形式单元，简单变量，内部信息向量，临时工作单元，SP，TOP，旧SP为控制链，调用该进程的进程的最新活动记录

8、的开始指针。0，1，2，指针SP指向正在运行的进程活动记录的起始点，TOP指向被占用的堆栈顶部单元，18，4，被调用方初始化其本地数据并开始执行。被叫方存储寄存器值和其他状态信息。2呼叫者将返回地址和旧的sp值存储在被呼叫者的活动记录中，然后呼叫者更改TOP的值。目标代码需要完成以下任务：1 .调用者评估真实参数，并将它们传输到被调用过程的活动记录的参数字段。19，返回序列，返回目标代码完成的任务如下：1。被调用方将返回值放在调用方的活动记录附近；2.使用状态字段中的信息，被呼叫者恢复sp和其他寄存器，并根据返回地址将它们传送到呼叫者的代码。3调用者将返回值复制到他自己的活动记录中。，20，R

9、的返回语句：return(E) E是返回值，把它放在临时单元中，然后恢复调用站点：top=sp-1 x=1sp(返回地址)sp=0sp跳转x(转到q的下一条指令)，首先：把它发送到一个特定的寄存器，21，程序排序；var a: array0.整数的10；x:integer开始a=0；快速排序；结束，程序快速排序(m，n :整数)；var k，v:integer开始吧。endquicksort，函数分区(y，z : integer): integer；var i，j:integer开始v交换(I，j)；结束；程序交换(I，j:整数)；开始x:=ai。ai:=aj。aj:=x端；1、2、3、10.

10、2.2嵌套过程语言(pascal语言)的堆栈实现、2、过程读数组；Var I整数；开始。嵌套定义关系sort readarray交换快速排序分区，22，过程readarray和交换引用最外层的一个过程描述；过程交换指的是最外层过程描述的X；1.对非本地名称、本地变量和形式参数的访问可以通过上一节中的方法来处理。通过访问非本地名称要解决的问题是如何通过：找到所有外部过程活动记录的地址。嵌套描述深度：主程序为1，23，跟踪外部进程最新活动记录的方法为：访问链，1。访问链和活动记录。访问链是一个活动记录字段，它来自当前进程、控制链(旧的SP)、返回地址、访问链、参数数、实际参数单位、向量内临时单位的

11、简单变量、SP、top、访问链、活动记录、24、TOP、执行顺序的活动记录排序快速排序分区交换、SP、交换、分区的活动记录、快速排序、排序活动记录、嵌套定义关系排序读数组交换快速排序分区、25、程序p；变量a，x :整数开始a=0；s。结束，程序Q(b :整数)；Var i:integer。开始吧。R(1，x)；结束，程序R(u :整数；var v:integer) Var c，d:integer开始如果u=1，那么R(u 1，v)；v=(a c)*(b-d)；结束，程序变量c，I :整数；开始a=1；q(c)；结束，1，2，2，3，类分配：写p调用s，s调用Q，Q调用r运行时数据堆栈，26，

12、程序主；Var a，b，c:实数。Beginx结束。程序x；Var d，e: real。从10:y开始；11:z结束；程序y。Var f，g:real。开始结束，程序z Var h，I，j:real开始y；结束；1，2，3，3，课堂练习2:当主程序调用X时，在以下时间给出数据堆栈。(1)标记为10的语句已经开始但尚未执行；(2)标记为11的语句已经开始，但尚未执行。27，10.3参数转移(课堂讨论)，P244-245，10.3.1值转移，P245-246，10.3.2地址转移，作业：p248 ex5，ex6，28，10。4如果是通用变量名：名称、类型、存储位置和范围，如果是过程名，还包括参数号

13、、类型、传递方法和返回值类型。符号表是一种数据结构。每个标识符在符号表中都有一条记录、名称、标记、信息列、id1、id2、初始、位置、固定长度标识符、29。符号表的实现，固定长度标识符：使用线性链表，不定标识符：使用一个单独的数组lexeme来存储标识符字符串，符号表在lexeme的起始位置存储标识符和相应的标记。I f EOS I n t EOS p o s I t o n EOS I n I t I a l EOS，I f，I n t，id 1，id 2，30，变量：类型(int，float，double，boolean，char.)种类(简单变量、数组、记录、过程名称)长度(所需存储单元数)偏移(存储单元的相对地址，如果是数组，记录内部矢量表)嵌套深度，31。程序：它是程序的外部程序吗？如果是函数，递归类型是什么？形式参数？32岁。关于符号表的进一步讨论：1 .符号表的数字结构(一)线性表；哈希表；树形结构。2.对符号表的操作：(a)插入；查找；(c)删除)。33，符号表中名称的属性信息包括两个方面：符号表必须维护源程序中的范围信息，源程序中的范围规则因语言而异。对于一种语言，根据符号表采用的数据结构，有不同的方