《ch910运行时环境(张素琴).ppt》由会员分享，可在线阅读，更多相关《ch910运行时环境(张素琴).ppt（34页珍藏版）》请在三一办公上搜索。
1、1,第10章 目标程序运行时的存储组织,2,1.存储组织,为了使目标程序运行，编译程序从操作系统得到一块内存存储区，存储区容纳:,1.生成的目标代码空间;,2.目标代码运行需要的数据空间，包括用户定义的变量和常量，临时工作单元，过程调用所需的联系单元，输入输出缓冲区;,3.用于保存过程活动踪迹的一个控制栈。,3,目标代码,静态数据,栈,活动记录,堆,1.编译后知道目标代码的大小。如 Pascal,C，Fortran；2.静态数据区存放编译时就能确定所占用空间大小的数据；3.栈堆区:用于存放可变数据以及管理过程活动记录的控制信息，如Pascal,C语言。,2.运行时刻内存的划分：,数据空间,4,
2、3.活动记录,对于pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；,一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。,当这个过程的活动执行完后，把它从栈顶弹出。,把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。,5,返回值,实在参数,控制链,访问链,保存机器状态,局部变量,临时变量,临时变量：编译产生。,保存机器状态：调用过程的活动在调用点的机器状态，包括计数器，各种寄存器的值。,局部数据：过程中定义的 局部量。,访问链：指向本活动要访问的非局部数据所在的活动记录.,控制链:指向主调过程的活动记录的首地址。,形
3、式单元,内情向量,连接数据,局部数据,sp,top,Pascal的活动记录,6,函数environment把一个名字映射为一个l-value（左-值）,4.名字与存储的绑定,引进两个函数，environment和state。environment把名字映射到一个存储单元上；,state把存储单元映射到那里所存放的值上。,而函数state把一个l-value（左-值）映射为一个r-value（右-值）。,如下图所示。,名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。,7,名字,存储单元,值,存储分配,程序运行,environment,state,l-value,r-val
4、ue,图：从名字到值的两个阶段映射,8,编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程符号表中；,运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录。,一个名字所需的存贮空间的数量是由它的类型确定的；,多字节对象存放于连续的字节中，以第一个字节的地址作为该对象的地址；,9,10.1 数据空间的三种不同管理方法,3.1 静态存储分配:FORTRAN3.2 栈式存储分配:PASCAL,C3.3 堆式存储分配:PASCAL,C,采用哪种分配策略是由源语言的语义决定的。,10,10.1.1 静态存储分配,如Fortran语言，各子程序段中的局部变量彼此独立，不会在不同子程序间引用
5、、赋值，每个变量的存储空间大小都是常量，整个程序所需的数据空间的总量在编译时完全确定，从而每个变量的内存空间可以静态分配。,在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。,11,限制：,1.在编译时刻知道数据目标的大小和它们在内存位置上 约束；,2.不能递归调用过程；,3.不能动态地建立数据结构。,12,与静态分配不同的是，在每次活动开始时把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，局部名字的存储空间随之释放。,对于具备递归调用、可变数组、允许用户申请和释放内存空间的高级语言，就需要采用动态存储管理技术管理内存，主要包括两种动
6、态存储分配方式：栈和堆式。,10.1.2 动态存储分配,13,基于栈存储分配的原理：存储空间被组织成栈，活动记录的推入和弹出，分别对应于活动的开始和结束。每当调用一个子程序时，它所需的数据存储空间就分配在栈顶，当该子程序运行结束就释放这部分内存存储数据空间；子程序的数据空间:(1)生存期在本过程本次活动中的数据对象，如局部变量、参数单元、临时变量等；(2)用于管理活动记录的信息，如当A调用B时，A被中断，则A当前寄存器和返回地址等信息。当执行完，便根据栈中信息回复的运行。适合Pascal、C、Algol语言。数据空间使用遵从“先申请后释放，后申请先释放”。,10.1.3 栈式动态存储分配,14
7、,如果一个程序语言让用户自由申请内存数据空间和退还数据空间的机制,如C+中的new,delete。空间使用不遵从“先申请后释放，后申请先释放”，这样就不能使用栈式存储分配方式。需要使用堆式存储方式。堆是一片足够 大的存贮空间，每当需要时，就从这片空间中分配一块，用完时，再归还给堆。经过一段时间运行后，运行空间被划分成许多块，需要整理。,10.1.4 堆式动态存储分配,15,10.2 栈式存贮分配的实现,条件：,C满足上述条件,C程序结构,全局数据说明Main()Main数据说明Void R()R数据说明Void Q()Q数据说明,不允许嵌套定义,允许递归调用,10.2.1 简单栈式存贮分配的实
8、现,16,假设调用顺序：,对于全局数据，,main的活动记录,全局静态数据区,Q的活动记录,R的活动记录,top,sp,是可以静态确定的，,因此在编译时就可确定这些非局部数据的存贮分配,main调用Q，Q调用R,Main调用Q，Q调用Q,Main调用Q，然后main调用R,课本p235图10.8,程序运行时存贮组织为：,17,C每个子程序的活动记录:,老SP,返回地址,参数个数 n,形式单元,简单变量,内情向量,临时工作单元,SP,TOP,老sp即是控制链，调用该过程的那个过程最新活动记录的起始指针。,0,1,2,指针SP指向现正运行过程活动记录的起点,TOP指向已经占有的栈顶单元,18,4被
9、调用者初始化其局部数据并开始执行。,3被调用者存放寄存器值和其它状态信息。,2调用者在被调用者的活动记录中存放返回地址和老sp之值，之后调用者改变 TOP的值。,目标代码需要完成任务：,1.调用者对实在参数求值，并把它们传送给 被调用过程的活动记录的参数域。,19,返回序列，return目标代码完成的任务是：,1被调用者将返回值放入临近主调者的活动记录的地方,2利用状态域中的信息，被调用者恢复 sp和其它寄存器，并且按返回地址转 移到调用者的代码之中。,3调用者复制返回值到自己的活动记录中。,20,R的返回语句：return(E)E为返回值，放在临时单元中,接下来恢复调用现场：top=sp-1
10、 x=1sp(返回地址)sp=0sp jump x(转向Q的下一条指令),首先：将送入特定寄存器,21,Program sort;var a:array0.10 of integer;x:integer;Begin a=0;quicksort;end,Procedure quicksort(m,n:integer);var k,v:integer;Begin.endquicksort,function partition(y,z:integer):integer;var i,j:integer;Begin a v exchange(i,j);end;,Procedure exchange(i,
11、j:integer);Begin x:=ai;ai:=aj;aj:=x end;,1,2,2,3,10.2.2 嵌套过程语言的栈式实现(pascal语言),2,Procedure readarray;Var I integer;Begin aend;,嵌套定义关系sort readarray exchange quicksort partition,22,过程readarray和exchange引用了最外层过程说明的a；过程exchange引用了最外层过程说明的x；,一、非局部名字的访问,局部变量和形参可以用上节的方法处理,非局部名字的访问所要解决的问题就是:如何找到所有外层过程活动记录的地址
12、.,嵌套说明深度：主程序为1,23,跟踪外层过程最新活动记录的方法：,访问链,1、访问链和活动记录,访问链为活动记录的一个域,它是从一个过程当前活动记录指向其定义的直接外层的活动记录首地址的一个指针。,控制链(老SP),返回地址,访问链,参数个数,实参单元,临时单元内情向量简单变量,SP,TOP,访问链,活动记录,24,top,执行顺序sort quicksort quicksort partition exchange,sp,exchange的活动记录,partition的活动记录,quicksort的活动记录,quicksort的活动记录,sort活动记录,嵌套定义关系sort reada
13、rray exchange quicksort partition,25,Program p;Var a,x:integerBegin a=0;S;end,Procedure Q(b:integer);Var i:integer;Begin.R(1,x);.end,Procedure R(u:integer;var v:integer)Var c,d:integer;Begin If u=1 then R(u+1,v);v=(a+c)*(b-d);end,Procedure SVar c,i:integer;Begin a=1;Q(c);end,1,2,2,3,课堂作业：写出p调用S，S调用Q
14、,Q调用R运行时数据栈,26,Program main;Var a,b,c:real;Beginx;end.,Procedure x;Var d,e:real;Begin10:y;11:z;end;,Procedure y;Var f,g:real;Begin end,Procedure zVar h,i,j:real;Begin y;end;,1,2,3,3,课堂练习2：当主程序调用x时，给出以下时刻数据栈的情况。(1)已经开始但尚未执行完标号为10的语句；(2)已经开始但尚未执行完标号为11的语句.,27,10.3 参数传递（课堂讨论）,P244-245,10.3.1 传值,P245-24
15、6,10.3.2 传地址,作业：p248 ex5,ex6,28,10.4 符号表(书ch9),编译器的一个基本功能是记录源程序中使用的标识符并收集与每个标识符相关的各种属性信息，,并将它们记载到符号表中。,若是普通变量名：名字、类型、存贮位置、作用域,若是过程名：还包括参数个数、类型、传递方法及返回值类型,符号表是一个数据结构。,每个标识符在符号表中都有一条记录,名字,记号,信息栏,id1,id2,initial,position,固定长标识符,29,符号表的实现,固定长标识符：采用线性链表,不定长标识符：使用单独的数组lexemes存放标识符的字符串,符号表中存放标识符在lexemes的起始
16、位置和相应记号,i f eos i n t eos p o s i t i o n eos i n i t i a l eos,If,int,id1,id2,30,符号表中信息栏的内容：,变量：类型(int、float、double、boolean、char.）种属（简单变量、数组、记录、过程名）长度（所需存贮单元数）偏移量（存贮单元相对地址，若为数组，则记录内情向量表）嵌套深度,31,过程：是否为程序的外部过程 若为函数，类型是什么 是否递归？形式参数？.,32,关于符号表的进一步讨论：1.符号表的数椐结构（a）线性表；(b)散列表；（c）树结构。2.符号表上的运算：（a）插入（insert
17、）；（b）查找（lookup）；（c)删除(delete).,33,.符号表中名字的属性信息由两方面组成:,符号表必须维持源程序中的作用域信息,源程序中的作用域规则因语言而异.对一种语言，根椐符号表采用的数据结构，维持源程序中的作用域信息方法不同。,（b）经分析加工得到的有用信息，例如，对于变量来说，嵌套深度，在活动记录中的偏移量等。,（a）名字在源程序中的属性信息，例如，名字源程序表示，种类，类型等；,34,作业：1.书p229 ex2.2.阅读教材p17和p27,节2.7 PL0语言目标代码解释执行时的存储分配 3.阅读p451对应的C语言程序 void interpret()，base()4.阅读P440-442有关符号表操作的函数enter,position,constdeclaration,vardeclaration,
