网站地图 | RSS订阅 老铁博客 - 上海SEO优化|上海网站建设|蜘蛛池出租|站群代搭建
你的位置:首页 » 网站建设 » 正文

第10章目标程序运行时存储

2019-8-6 12:47:13 | 作者:老铁SEO | 0个评论 | 人浏览

  第10章目标程序运行时存储_电脑基础知识_IT/计算机_专业资料。第10章目标程序运行时存储

  第10章 目标程序运行时的组织 ? 教学要求:本章介绍目标程序运行时的 存储组织方式,包括静态存储分配和动 态存储分配。 要求掌握各种存储组织形 式的基本方法。 ? 教学重点:静态分配策略和动态分配策 略的基本思想,嵌套过程语言栈式分配, 活动记录、运行时栈的组织。 10.1 概述 ? 从逻辑上看,代码生成前,编译程序必须 进行目标程序运行环境的设计和数据空间 的分配 ? 数据空间包括:用户定义的各种类型的数 据对象(变量和常量)所需的存储空间, 作为保留中间结果和传递参数的临时工作 单元,调用过程时所需的连接单元,组织 输入/输出所需的缓冲区。 ? 存储管理复杂度取决于源语言本身,具体包括: ? ? 允许的数据类型的多少? 语言中允许的数据项是: 静态确定?动态确定? ? 程序决定名字的作用域的规则和结构 段结构? 过程定义不嵌套?只允许过程递归调用? 分程序结构: 分程序嵌套?过程定义嵌套? 1、存储组织:编译程序对目标程序运行时的 组织(运行环境和分配存储)。如通常存储 区布局可为: 目标代码区 静态数据区 Stack 静态数据区用以存放编译时能确定所 占用空间的数据。 堆/栈用于存放可变数据以及管理过 程活动的控制信息。 目标代码区用以存放目标代码,这是 固定长度的,即编译时能确定的。 heap 三种数据区对应着下述三种不同的分配策略 2、存储分配策略: ? (1)静态存储分配——在编译时能确定目 标程序运行中所需的全部数据空间的大小, 编译时安排好目标程序运行时的全部数据 空间,确定每个数据对象的存储位置。 注:1、程序结构特点:不允许递归调用,而 且不含有可变数组。(如FORTRAN语言)。 2、基本策略:在编译时,根据各类数据 所需的存储空间大小以及存储方式规定, 在符号表中建立“名字-地址”对应关系, 然后根据这些对应关系进行变量名的地址 分配。 (2)动态存储分配——在运行阶段动态地 为源程序中的量分配存储空间。(栈式、堆 式) 注:1)若某程序设计语言允许过程递归调 用,而且允许使用可变数组,那么在编译时 就不可能完全为其数据项目分配存储单元, 必须采取动态存储分配策略。 ? 2)动态分配数据单元时一般使用栈,即栈 式存储管理。 ? 栈式: 简单的栈式分配方案 ? 嵌套过程的栈式分配方案 ? 分程序结构的存储分配方案 3、过程活动:一个过程的活动指的是该过程 的一次执行。 4、活动记录(AR):一个过程的一次执行所 需要的信息使用一个连续的存储区来管理, 这个区(块)叫做一个活动记录。此记录含 有连接数据、形式单元、局部变量、局部数 组的内情向量和临时工作单元等。 每个过程的活动记录内容(非嵌套语言) TOP? 临时单元 内情向量 局部变量 形式单元 2 1 参数个数 动态链 对任何局部变量X的引 用可表示为变址访问: dx[SP] dx: 变量X相对于活 动记录起点的地址, 在编译时可确定。 SP? 0 返回地址 每个过程的活动记录内容(嵌套语言) TOP? 临时单元 内情向量 局部变量 形式单元 静态链 动态链 返回地址 ?连接数据 ?返回地址 ?动态链:指向调用该 2 1 SP? 0 过程的最新活动记录 地址的指针。 ?静态链:指向直接外 层最新活动记录地址 的指针,用来访问非 局部数据。 每个过程的活动记录内容 TOP? 临时单元 内情向量 局部变量 形式单元 2 1 静态链 动态链 SP? 0 返回地址 形式单元:存放相 应的实参的地址或 值。 ? 局部数据区:局部 变量、内情向量、 临时工作单元(如 存放对表达式求值 的结果)。 ? 临时单元 TOP 内情向量 局部变量 形式单元 静态链 动态链 返回地址 访问信息 连接数据(控制信息) SP SP为当前活动记录的起始位置。 TOP为栈顶单元。分别放在两个寄 存器中。 活动记录的填写 1、 call P 被翻译成: 临时单元 内情向量 局部变量 1[TOP]:=SP JSR P (保护现行SP) (转子指令) 形式单元 参数个数 返回地址 TOP? SP ? 老SP 调用过程的 活动记录 2、转进过程P后,首先应执行下述指令: SP:=TOP+1 1[SP]:=返回地址 TOP:=TOP+L (定义新的SP) (保护返回地址) (新TOP) TOP? 临时单元 内情向量 局部变量 L:过程P的活动记录所需单元数, 在编译时可确定。 形式单元 参数个数 返回地址 老SP SP? TOP? 调用过程的活动记录 3、 过程返回时,应执行下列指令: TOP:=SP-1 (恢复调用前TOP) X:=2[TOP] (把返回地址取到X中) SP:=0[SP] (恢复调用前SP) 临时单元 TOP? UJ X (按X返回) 内情向量 局部变量 形式单元 参数个数 返回地址 SP? TOP? SP? 老SP 调用过程的活动记录 10.2 栈式存储分配的实现 一、简单的栈式存储分配的实现 ? 程序结构特点:没有分程序结构,过程定义不嵌 套,过程可递归调用。 ? 简单栈式分配方案:把存储区组织成一个栈,运 行时每进入一个过程,就把它的活动记录压入栈, 形成过程工作时的临时数据区,该过程结束时取 消该数据区。 例: Main( ) { Main中的数据说明 } proc R( ) { R中的数据说明 } … proc Q( ) { Q中的数据说明 } ? 主程序→过程Q → 过程R TOP? SP? R的活动记录 Q的活动记录 主程序活动记录 全局数据区 TOP R的数组区 R的活动记录 SP Q的活动记录 主程序全局 数据区 分配了数组区之后的运行栈 二、嵌套过程语言的栈式分配的实现 1、程序结构特点:语言的定义允许嵌套, 一个过程可以引用包围它的任一外层过 程所定义的标识符(如变量,数组或过 程等)(如PASCAL语言) 。 ? 如何才能引用外层数据? 2、关键:设法跟踪每个外层过程的最新活动 记录AR的位置。 ? 跟踪办法: (1) 用静态链。 (2) 用DISPLAY表。 ? PASCAL –PASCAL程序本身可以看成是一个操作 系统所调用的过程,过程可以嵌套和 递归。 –一个PASCAL过程: 过程头; 说明段(由一系列的说明语句组成); begin 执行体(由一系列的执行语句组成); end –作用域:一个名字能被使用的区域范围 称作这个名字的作用域。 –允许同一个标识符在不同的过程中代表 不同的名字。 –名字作用域规则--最近嵌套原则 ?一个在子程序B1中说明的名字X只在 B1中有效(局部于B1); ?如果B2是B1的一个内层子程序且B2中 对标识符X没有新的说明,则原来的 名字X在B2中仍然有效。如果B2对X重 新作了说明,那么,B2对X的任何引 用都是指重新说明过的这个X。 program main var A, B : real; … procedure P1 var B:boolean; … begin … end procedure P2 var A:integer; … begin … end begin … end A(real) A(integr) B(real) B(bool) 非局部名字的访问的实现 ? 主程序的层次为0;在i层中定义的过程, 其层次为i+1; ? 过程运行时,必须知道其所有外层过程的 当前活动记录的起始地址。 (1) 用静态链 ? 在过程活动记录中增设静态链,指向包含 该过程的直接外层过程的最新活动记录的 起始位置。见P223-224 过 程 定 义 的 嵌 套 执 行 顺 序 main p1 p2 p3 P2活动记录 存取链(静态链) 控制链(动态链) P4活动记录 存取链(静态链) 控制链(动态链) P3活动记录 存取链(静态链) p4 main →p3 →p3 →p4 控制链(动态链) P3活动记录 存取链(静态链) 控制链(动态链) main活动记录 →p2 2、用Display表 Display表---嵌套层次显示表 当前激活过程的层次为K,它的 Display表含有K+1个单元,依次存放着现 行层,直接外层…直至最外层的每一过程 的最新活动记录的基地址。 说明:1、由于过程的层数可以静态确定,因 此每个过程的Display表的体积在编译时即 可以确定。 2、某过程p是在层次为i的过程q内定 义的,并且q是包围p的直接外层,那么p的 过程层数为i+1。 procedure P2; program P; var s,t:integer; var x,y: integer; ... ... procedure P21; procedure P1; begin var i,j:integer; ... ... end; procedure P11(a,b:integer); ... begin ... begin ... call P1 ... end; end; begin ... begin ... call P11(i,j); ... call P2; ... end; end. 主程序P ?过程 P2 ?过程 P1 ?过程 P11 3 2 1 5 Display 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 b a RA j i P11 的活 动记 录 P1的 活动 记录 P2的 活动 记录 P的 活动 记录 RA t s RA y x 例: program main(i,0); …… proc R(c,d); …… end /*R*/ proc P (a); …… proc Q (b); …… R(x,y); end /*Q*/ …… Q(z); end /*P*/ …… P(W); …… R(U,V); …… end /*main*/ 程序结构图 R 主 P Q call R call Q call P call R 用Display表的方案 (1)主程序---(2)P---(3)Q---(4)R top top display d[0] display d[1] 主程序的 sp 活动记录 d[0] P的 sp 活动记录 主程序的 活动记录 (2) (1) 用Display表的方案 (1)主程序---(2)P---(3)Q---(4)R top display top display sp d[2] d[1] d[0] sp Q的 活动记录 P的 活动记录 主程序的 活动记录 d[1] d[0] R的 活动记录 Q的 活动记录 P的 活动记录 主程序的 活动记录 (3) (4) DISPLAY表的维护和建立 ? 为便于组织存储区,将display作为活动记录的一 部分,其相对地址在编译时是完全可以确定的。 ? 假设过程P1可调用P2,为了能在P2中建立P2的 display,在P1调用P2时设法把P1的display地址 作为连接数据之一(全局display地址)传送给P2, 因此连接数据包括: 老SP值(动态链) 返回地址 全局display地址 ? d 4 3 …… DISPLAY 形式单元 参数个数 ? 当过程的层次为n, 它的display为n+1 个值。 ? 一个过程被调用 时,从调用过程的 DISPLAY表中自下向 上抄录n个SP值,再 加上本层的SP值。 2 1 0 全局DISPLAY地址 返回地址 老SP 10.3 堆式存储分配 ?堆:通常是一片连续的足够大的存储区,当需要 时,就从堆中分配一小块存储区;用完就及时退 还给堆。 ?注:在高级语言中有些数据存储空间的请求与释 放不再遵循后进先出的原则,而且是全局性的。 为此,需要让运行程序持有一块专用的全局存储 空间来满足这些数据的存储要求。这种存储空间 就是堆。 10.4 参数传递 (1)procedure exchangel(i,j:integer); (2) var x:integer; (3) begin; (4) x:=a[i]; a[i]:=a[j]; a[j]:=x (5) end; 带有非局部变量和形参的PASCAL过程 非局变量a[i]和a[j]的值进行交换,i,j为 形参 传值的实现 ? 1.形式参数当作过程的局部变量处理, 即在被调过程的活动记录中开辟了形参 的存储空间,这些存储位置即是我们所 说的形式单元(用以存放实参)。 ? 2.调用过程计算实参的值,并将其放在 对应形式单元开辟的空间中。 ? 3.被调用过程执行时,就像使用局部变 量一样使用这些形式单元。 (1)program reference(input,output); (2)var a,b:integer; (3)procedure swap({var} x,y:integer); (4) var temp:integer; (5) begin (6) temp:=x; (7) x:=y; (8) y:=temp (9) end; (10)begin (11) a:=1; b:=2; (12) swap(a,b); (13) writeln(‘a=‘,a);writeln(‘b=‘,b) (14)end. 带有过程swap的PASCAL程序 传地址的实现 把实在参数的地址传递给相应的形参,即 调用过程把一个指向实参的存储地址的指针 传递给被调用过程相应的形参: 1.实在参数是一个名字,或具有左值的表达式 ----传递左值 2.实在参数是无左值的表达式----计算值,放 入一存储单元,传此存储单元地址 3.目标代码中,被调用过程对形参的引用变成 对传递给被调用过程的指针的间接引用 (1)swap(x,y) (2)int *x,*y; (3){ int temp; (4)temp=*x; *x=*y; *y=temp; (5) } (6)main( ) (7){ int a=1,b=2; (8) swap(&a, (9) printf(“a is now %d,b is now %d\n”,a,b);} 在一个值调用过程中使用指针的C程序, 在C程序中无传地址所以用指针实现。 嵌套过程作为参数传递 ? ? ? ? ? ? ? ? ? ? ? (1)program param(input,output); (2)procedure b(function h(n:integer):integer); (3) begin writeln(h(2)) end{b}; (4)procedure c; (5) var m:integer; (6) function f(n:integer):integr; (7) begin f:=m+n end{f}; (8)begin m := 0; b(f) end {c}; (9)begin (10) c (11)end 存取链 f的活动记录 f,存取链 存取链 b的活动记录 M 存取链 c的活动记录 Param的活动记录 作业 (1)对以下的Pascal程序画出过程C第二次被调用时的运 行栈,控制链和存取链. (2)如果把存取链改成DISPLAY,重新做(1) program env; procedure A; var x :integer; procedure B; procedure C; begin x:=2; B end; (c过程) begin C end; (B过程) begin B end ; (A过程) begin A end; (main)

  • 本文来自: 老铁博客,转载请保留出处!欢迎发表您的评论
  • 相关标签:目标程序  
  • 已有0位网友发表了一针见血的评论,你还等什么?

    必填

    选填

    记住我,下次回复时不用重新输入个人信息

    必填,不填不让过哦,嘻嘻。

    ◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。