7_运行时环境（PPT63页)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2009-machunyan,*,第,7,章 运行时环境,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第7章 运行时环境(存储空间,),当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息,例如为源程序中出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。,目标代码要从操作系统得到一块存储区，用于它的运行。,存储分配是在运行阶段进行的，但,编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：,函数调用分析.,txt,),目标代码运行时，,存储空间的组织,称为目标代码的,运行时环境,。,第7章 运行时环境(存储空间,)(,续,),运行时环境有三个类型：完全静态环境(,fully static environment),、基于栈的环境(,stack-based environment)，,以及完全动态环境(,fully dynamic environment)。,这3种类型的混合形式也是可能的。,第7章 运行时环境(存储空间,)(,续,),7.1 程序执行时的存储器组织,7.3 基于栈的运行时环境,7.4 动态存储器,7.5 参数存储机制,7.,2,完全静态的运行时环境,第7章 运行时环境(存储空间,),7.1程序执行时的存储器组织,目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:,由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。,7.1程序执行时的存储器组织（续）,代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，在编译时所有目标代码的地址都是可计算的，程序执行结束后代码区域内存由系统释放。,全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量,)；,编译器可以确定其所占用存储空间的大小，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序执行结束后由系统释放。,本章案例分析,.doc,7.1程序执行时的存储器组织（续）,栈区：,函数中的形参和在函数中定义的局部变量以及局部临时变量（,C,、,C+,、,Java,），这些变量,分配在栈区，,每次函数执行的时候会在栈中为函数的执行分配相应的存储区，而在函数执行完毕后，释放相应的存储区。,编译器“知道”存在栈中的具体数据所占内存大小和内存分配和释放的“时刻”；,堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从,heap,中分配多少空间，也不需要知道从,heap,上分配的空间究竟需要存在多久。,在,c,中由,malloc,，,free,运算产生释放的存储空间，在,c+,中 由,new,和,delete,运算符作用的存储空间，以及在,Java,中由,new,分配的存储空间都在堆中进行分配。,7.1程序执行时的存储器组织（续）,machunyan,西北工业大学软件与微电子学院,10,10,7.1程序执行时的存储器组织（续）,在,C,语言中, 采用以函数（或过程）为单位的动态存储分配方案：,当一函数被调用时，就在栈顶为该函数分配所需的数据空间(过程活动记录)，当一个函数工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。,函数的活动记录(,activation record,AR,)是一段连续的存储区，用于存放函数的一次执行所需要的信息，当调用或激活函数时，必须为被调用函数的活动记录分配空间。,活动记录存放的信息至少应包括以下几个部分：,存放主调函数为被调函数提供的实参信息;,存放目标程序临时变,量的值;,存放本次执行中的局部数据,用于指向主调函数的,活动记,录的控制链,和返回地址,;,7.1程序执行时的存储器组织（续）,7.1程序执行时的存储器组织（续）,实参,返回地址,控制链,临时变量和局部数据,实参,返回地址,控制链,临时变量和局部数据,调用者的活动记录,被调用者的活动记录,调用者的职责,C,语言所调用函数的活动记录示例,(,函数调用分析中的举例,),控制链：指向调用函数活动记录的一个地址。,b:2,a:1,该函数调用结束时的返回地址(,00401014),主调函数的控制链,c:3,栈底,栈顶,7.1程序执行时的存储器组织（续）,当前函数的控制链,7.1 程序执行时的存储器组织,7.2 完全静态的运行时环境,7.3,基于栈的运行时环境,7.4 动态存储器,7.5 参数存储机制,第7章 运行时环境(存储空间,),7.2 完全静态的运行时环境,在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：,每个数据名所需的存储空间的大小都是常量,不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构,过程不可递归调用,整个程序,存储器如,右所示：,7.2 完全静态的运行时环境（续）,7.1 程序执行时的存储器组织,7.2 完全静态的运行时环境,7.3 基于栈的运行时环境,7.4 动态存储器,7.5 参数存储机制,第7章 运行时环境(存储空间,),7.3 基于栈的运行时环境,在一个,所有函数都是全局的,、函数,定义不允许嵌套,，但允许函数递归调用的程序设计语言(例如,C,语言)中，基于栈的动态运行时环境有两个指针,：,sp:,栈顶部(,top of stack,),指针；对于,x86,系统来说，它采用,sp,或,esp,寄存器存储栈顶部的地址；,注：用它只可访问栈顶,7.3 基于栈的运行时环境（续）,fp,(frame point,)：,控制链指针，即存储,当前活动记录的控制链（即一个地址）,，,对于,x86,系统，它采用,bp,或,ebp,寄存器,存储,当前活动记录的控制链，其作用如下：,1.通过该指针可以访问主调函数的活动记录；即允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。,2.通过该指针可以访问当前执行函数的实参和局部变量；,b:2,a:1,该函数调用结束时的返回地址(,cs:eip) 00401014,主调函数的控制链(,main.ebp),void _stdcall f_stdcall(int a,int b),int c;,c=a+b;,c:3,esp,栈底,栈顶,ebp,7.3 基于栈的运行时环境（续）,当一个函数被调用时，,在栈顶为该函数分配所需的数据空间(过程活动记录,),如下：,将,实参,的值压入在该函数对应的,新活动记录,中。,将被调函数执行完毕后的,返回地址,压入在,新的活动记录,中。,完成到被调用的过程代码一个转移。,将主调函数的,fp,作为,控制链压入到新的活动记录,中。,改变,fp,以使其,指向新的活动记录,(将,sp,复制到,fp,中),将该函数的,局部变量,和,局部临时变量,压入到新的活动记录中。,7.3 基于栈的运行时环境（续）,b:2,a:1,该函数调用结束时的返回地址(,cs:eip) 00401014,主调函数的控制链(,main.fp),C,语言当前执行函数的活动记录示例：,c:3,sp,栈底,栈顶,fp,7.3 基于栈的运行时环境（续）,当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：, 将,fp,复制到,sp,中。, 将控制链装载到,fp,中。, 完成到返回地址主调函数的一个转移。, 改变,sp,以弹出实参。,7.3 基于栈的运行时环境（续）,例：计算两个非负整数最大公约数的,c,代码如下：,#,include ,int x,y;,int gcd(int u,int v), if(v= =0) return u;,else return gcd(v,u%v),main(), scanf(“%d%d”,printf(“%dn”,gcd(x,y);,return 0;,7.3 基于栈的运行时环境（续）,x:15,y:10,全局/静态区域,main,的活动记录,sp,fp,v:10,u:15,返回地址,main,的,fp,第一次调用,gcd,时的活动记录,sp,fp,第二次调用,gcd,时的活动记录,v:5,u:10,返回地址,第一次调用,gcd,时的,fp,第三次调用,gcd,时的活动记录,v:0,u:5,返回地址,第二次调用,gcd,时的,fp,sp,fp,sp,fp,栈生长方向,自由空间,7.3 基于栈的运行时环境（续）,例：考虑下列程序清单的,c,代码。,int x=2;,void g(int);,void f(int n),static int x=1;,g(n);,x- -;,void g(int m),int y=m-1;,if (y0),f(y);,x- -;,g(y);,main(),g(x);,return 0;,画出至第二次对,g,调用时，程序的运行时环境：,7.3 基于栈的运行时环境（续）,x:2,x（from f）:1,全局/静态区域,main,的活动记录,sp,fp,m:2,返回地址,main,的,fp,y:1,第一次调用,g,时,的活动记录,fp,sp,第一次调用,f,时,的活动记录,n:1,返回地址,第一次调用,g,时的,fp,sp,fp,第二次调用,g,时的,活动记录,m:1,返回地址,第一次调用,f,时的,fp,y:0,fp,sp,栈生长方向,自由空间,7.3 基于栈的运行时环境（续）,目标代码的生成必须,支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码,。,对名字的访问,局部临时变量,嵌套声明,如何处理可变长度的问题,7.3 基于栈的运行时环境（续）,对名字的访问：,在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的,，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。,对函数参数和局部变量而言，在大多数的语言中，如果函数的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定，,每个实参和局部声明的偏移量可由编译程序计算,。,m:2,返回地址,控制链,y:1,fp,mOffset,yOffset,mOffset=+8,yOffset=-4,高端地址,低端地址,对名字的访问：（续）,例：考虑下面的,C,过程,Viod f(int x,char c),int a10;,double y;,c,x,返回地址,控制链,a9,a1,a0,y,fp,cOffset,aOffset,xOffset,yOffset,xOffset=+8,cOffset=+12,aOffset=-40,yOffset=-48,现在对,ai,访问，要求计算地址：,(-40+4*,i)(fp),对名字的访问：（续）,对,f,调用的活动记录为：,目标代码的生成必须,支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码,。,对名字的访问,局部临时变量,嵌套声明,如何处理可变长度的问题,7.3 基于栈的运行时环境（续）,局部临时变量：,考虑,C,表达式：,xi=(i+j)*(i/k+f(j),，在这个表达式从左到右的求值计算中，在对,f,的调用过程中需要保存中间结果：,xi,的地址、,i+j,的和、,i/k,的商。,这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者,可将它们作为临时变量存储在对,f,调用之前的运行时栈中,。如下所示：,返回地址,控制链,xi,的地址,i+j,的结果,i/j,的结果,fp,(栈的其余部分,),sp,临时栈,调用,f（,将要创建的）时的,新活动记录,包含表达式过程的活动记录,自由空间,局部临时变量：（续）,目标代码的生成必须,支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码,。,对名字的访问,局部临时变量,嵌套声明,如何处理可变长度的问题,7.3 基于栈的运行时环境（续）,嵌套声明也出现了与局部临时变量同样的问题。考虑以下的,C,代码：,Void p(int x,double y), char a;,int i;,A: double x;,int j;,B: char *a;,int k;,嵌套声明：,x:,y:,返回地址,控制链,a:,i:,x,:,j,:,fp,(栈的其余部分,),sp,块,A,的分配区,调用,p,时的活动记录,自由空间,嵌套声明：（续）,一个简单的处理办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。当进入块,A,后，运行时栈如下所示：,x:,y:,返回地址,控制链,a:,i:,a,:,k,:,fp,(栈的其余部分,),sp,块,B,的分配区,调用,p,时的活动记录,自由空间,当进入块,B,后，运行时栈如下所示：,嵌套声明：（续）,目标代码的生成必须,支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码,。,对名字的访问,局部临时变量,嵌套声明,如何处理可变长度的问题,7.3 基于栈的运行时环境（续）,处理可变长度的数据,有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的一种情况如下：, 调用中的自变量的数量可根据调用的不同而不同。,printf(,“,%d%s, n, prompt);,printf(,“,%d %d %d,”,3,4,50);,通常，,C,编译程序一般通过把调用的自变量按相反顺序(,in reverse order),压入到运行时栈来处理这一点。,printf(“%d %d %d” ,3,4,50);,设置一指针,ap,；,让,ap,指向第一个可变参数,(,地址为,ebp+,控制链所占的空间,+,返回地址所占的空间,+,固定参数所占的空间,),，即,3,所在的空间；,返回,3,，,ap,的值加,4,即指向,4,所在的存储空间,通过指针,ap,的移动读取所有的可变参数，根据固定参数“,%d %d %d”,，该字符串中每出现一个“,%d”,就执行一次；固定参数指出了后面的可,变参数的个数；,清除变量,ap,。,处理可变长度的数据,(,续,),7.1 程序执行时的存储器组织,7.2 完全静态的运行时环境,7.3 基于栈的运行时环境,7.4 动态存储器,7.5 参数存储机制,第7章 运行时环境(存储空间,),7.4.1对象类型,在大多数面向对象的语言中，对象都有构造函数和,析构函数，它们分别在创建对象和释放对象时被调,用。假定我们有一对象类,A，,它有方法,m1,m2,以及字段,a1,和,a2。,那么类,A,对象的运行时表示有包含,字段,a1,和,a2,记录组成：,a1,a2,m1_A,m2_A,另外，编译程序维护着一张类,A,的编译时方法表：,7.4 动态存储器,在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方法,m2_A,可以翻译为,c,语言中的函数。,void m2_A(class_A *this, int i),方法,m2_A,的程序体，通过,this-x,访问 任一对,象字段,x,方法的调用,a .m2(3),可以翻译成,m2_A(&a,3),7.4 动态存储器（续）,继承特性,现在假定类,B,通过增添方法,m3,和字段,b1,来扩展类,A,那么类,B,的运行时表示如下：,a1,a2,m1_A,m2_A,b1,另外类,B,的方法编译时表如下：,m3_B,7.4 动态存储器（续）,方法重载,假定上例中类,B,重新定义了方法,m2，,那么,A,中方法,m2,的定义既是它唯一的声明也是它的第一次定义，而它在类,B,中的定义为重定义。,为使名字既可以反映声明它的类，也可以反映定义它的类。方法的名字可有三部分组成：,方法名、声明方法的类名、定义方法类名,。各部分之间用下划线（,）分开。因此在类,A,中声明在类,B,中定义的方法,m2,其名字记为,m2_A_B。,方法重载影响方法的编译时表，现在类,A,的方法的编译时表如下：,m1_A_A,m2_A_A,m1_A_A,m2_A_B,m3_B_B,类,B,的方法的编译时表如右：,7.4 动态存储器（续）,现在假定,a,是类,A,的一个对象，而,b,是类,B,的一个对象,方法调用,a.m2(),将翻译成对,m2_A_A,的调用，而方法调用,b.m2(),将翻译成对,m2_A_B,的调用。,2_A_A,在类,A,中声明和定义。,m2_A_B,在类,A,中生明，在类,B,中定义。,m2_A_A,翻译形式为：,void m2_A_A(Class_A *this, int i);,m2_A_B,的翻译形式为：,void m2_A_B(Class_B *this, int i);,7.4 动态存储器（续）,多态性,当类,B,继承类,A,，并且该语言允许,“,类,B,的指针,”,类型的指针,能够赋给一个,“,类,A,的指针,”,类型的变量时，那么该语言,支持多态型。例如：,Class B *b=,;,Class A *a=b;,则第二行被翻译成：,class A *a=convert_ptr_to_B_to_ptr_to_A(b);,现在，过程,convert_ptr_to_B_to_ptr_to_A(),为一编译,时类型的操作,它将指向子类,B,的一个对象指针转换为指,向其父类,A,对象的指针。因为类,B,的对象也是从类,A,的字,段开始，因而指针的值并不需要改变，唯一影响的是改,变了指针的类型：,7.4 动态存储器（续）,a1,a2,b1,指向,B,的指针,指向,B,中,A,的指针,现在同一指针指向了不同类的对象,7.4 动态存储器（续）,7.4 动态存储器（续）,动态绑定,：类型,class A*,的指针,p,可能引用了类,B,的一个对象，动态绑定认为如果实际上为类,B,的对象，那就应该调用,m2_A_B,如果实际为,A,的对象，那么就应该调用,m2_A_A.,对于方法调用,p-m2(3),p,是一指向类,A,对象指针，可以将,p-m2(3),被翻译成如下形式：,switch(dynamic_type_of(p),case Dynamic_class_A: m2_A_A(p,3);,case Dynamic_class_B:,m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);,当,p,为一指向类,B,对象指针时，可以将,p-m2(3),翻译为：,m2_A_B(p,3);,对于上述的翻译方法，每一个对象的类型信息实现为一个,指向分派表的指针，如下图所示,(分派表是存储方法地址,的记录，下图分派表存储的是方法,m1_A_A， m2_A_B,和,m1_B_B,的地址),a1,a2,b1,指向,B,的指针,指向,B,中,A,的指针,m1_A_A,m2_A_B,m3_B_B,类,B,对象的表示,分派表,B-object,B-class,7.4 动态存储器（续）,7.4.2 堆管理,7.4 动态存储器（续）,对于允许程序为变量在运行时动态申请和释放存储空间的语言,采用堆式分配是最有效的解决方案.,堆式分配的基本思想是,为运行的程序划出适当大的空间(称为堆,Heap),每当程序申请空间时,就从堆的空闲区找出一块空间分配给程序,每当释放时则回收之.,堆分配的必要性,7.4 动态存储器（续）,在,C,中处理链表等结构时,常常随机地插入或删除一些结点,利用指针变量和结构类型,可动态地生成新结点(使用,malloc(),函数), 或删除之(使用,free(),函数).,例如,struct node char data; struct node *next;,定义了链表的结点,下面函数可在表的尾部添加新结点:,void Append(struct node *head,char ch) struct node *p=head;,while(*p) p=p-next; p-next=malloc(sizeof(struct node);,p-next-data=ch; p-next-next=NULL;,还可用下面的函数在表头删除一结点:,void Delete(struct node *head) struct node *p=head;,if(*p) head =head-next; free(p); ,堆存储管理的实现,7.4 动态存储器（续）,将存储空间划分为若干存储块;用户可随机地申请或释放一个或多个块;,在存储空间中建立两个队列:空闲队列和忙队列,空闲队列拉成链,链首用,FREE,指针指明,忙队列用一(已占块)记录表记录各占用块的首址及大小信息(也可用链进行记录).,申请时可按需要找到合适的块分配之(分配策略有最佳分配或随机分配等);,释放时将该块插入到空闲队列(能合并时可合并),并从占用记录表中删除相应的项.,7.1 程序执行时的存储器组织,7.2 完全静态的运行时环境,7.3 基于栈的运行时环境,7.4 动态存储器,7.5 参数存储机制,第7章 运行时环境(存储空间,),7.5 参数传递机制,void inc2( int x),/* incorrect! */, +x;+x; ,void inc2( int* x),/* now ok */, +(*x);+(*x); ,值传递,：,值传递的处理方法是：进入过程时,送入形参对应的形式单元的是相应实参的值,；过程体中对形参的任何赋值都按对形式单元的直接访问来产生代码。形参和实参不是同一个存储单元。,因此,一旦把实参之值送入对应形式单元之后,在执行过程体期间,除了以实参值作为形参的初值进行运算之外,将,不再与实参发生任何联系。由此可见, 过 程执行的结果决不会改变实参之值。,void inc2( int &x),/* C+ reference parameter */, +x;+x; ,7.5 参数传递机制（续）,引用传递,：,将实参的地址写入相应的形式单元，过程体中对形式参数的任何引用或赋值,都按对相应形式单元间接访问的寻址方式为其产生代码,。所以，执行过程时,对形参的赋值将会影响相应实参之值。,在,C+,中，是通过在参数说明中使用特殊字符&来得到引用传递：,7.5 参数传递机制（续）,引用传递不要求复制被传递的值，这与值传递不同。当要,复制的值是一个较大的结构,时，在这种情况下，引用传递能够做到值传递而无需覆盖值的拷贝。,当要,复制的值是一个较大的结构,时，如果,禁止实参变量的值有任何变化,，在,C+,中可将调用写作：,void f(const MuchData &x),其中的,MuchData,是带有大型结构的数据类型。这仍是引用传递，但是编译程序还必须执行一个静态检查：,x,从不出现在一个赋值的左边或是被改变。,已知,C,程序：,#,include ,int i, b4;,void func( int x, int y), i=2; x +=2 ; b i =15; y+=3; b i+1=20; ,void main( ),for( i=0; i4; i+) bi=i;,i=1;,func(bi, bi+1);,for(i=0;i4;i+) printf(“ %d ”, bi);,printf(“ %dn”, i );,1,给出该程序的输出结果；,2若,C,语言采用的是引用调用的形实结合方式，,输出结果又如何？,7.5 参数传递机制（续）,值结果传递,在过程中复制和使用实参的值，然后当过程退出时，再将形参的最终值复制回实参变量的地址。因此，这个方法有时也被称为复制进，复制出，或复制存储。,在调用,p,之后，若使用了引用传递，则,a,的值为3；若使用了值结果传递，则,a,的值为2。,例如，在以下的代码中(,C,语法)：,void p(int x, int y), +x;,+ + y ;,main( ), int a=1;,p(a,a);,return 0;,7.5 参数传递机制（续）,名字传递,实参的名称或是它在调用点上的结构表示取代了它对应的形式参数的名字。,main( ),i = 1;,a1=1;,a2=2;,p(ai);,return 0;,int i;,int a10;,void p(int x), +i;,+x ;,对,p,的调用的结果是将,a2,设置为,3,并保持,a1,不变。,7.5 参数传递机制（续）,小结,什么是活动记录？请给出,C,语言活动记录的内容。,设有,c,语言程序,:,main(),printf,(“%d,n”,f,(3);,f(,int,x),if(x=1),return 1;,else,return x*f(x-1);,试给出运行该程序在返回主函数之前运行栈的活动,记录示意图。,