8-第八章存储空间组织-3节-缩减版.ppt

§8.3 静态存储分配FORTRAN语言,如果编译时能确定一个程序在运行时所需的存贮空间大小，则可以在编译时安排目标程序的全部数据空间，并确定每个数据项的单元地址。这种存贮空间分配方法称为 “静态存储分配”。 静态存储分配特点 1). 编译时刻确定存储位置； 2). 目标程序执行时不必进行存储管理。目标程序 代码特别简单、高效。,FORTRAN语言的特点：（FORTRAN 77） 1). 过程不允许递归调用 一个过程的两个活动的生存期不相交，因此一 个过程的所有活动可以使用同一个活动记录； 2). 每个数据名所需的存储空间大小是常数，没有 可变数组等； 3). 数据名的性质完全确定；不能动态地建立数据 结构； 因此可以采用“静态存储分配”。,由于每个FORTRAN 程序段可以独立编译，运行前由 装入程序把各段连成可运行的整体。 通常按数据区组织存储: 每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。 每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。 每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记： （所属数据区编号，在该区中的相对位置）,§8.3.1 FORTRAN数据区,数据区=局部区(1个/程序段)全局区,编 译,. . .,.,.,1.各数据区编号，并统计 长度，便于分配空间； 2.数据区仅分配地址，构 成映象(虚空间)，真正 的空间运行时才建立， 并可以使用；,局部数据区的内容： 返回地址：存放此程序段结束时的返回地址。 寄存器保护区：调用本程序段时寄存器中的信息，当 本程序段结束后，可以恢复到调用前的状态； 形式单元：存放实在参数的地址或值。FORTRAN语言 采用两种方式共存的形式。 传地址：一个单元，存放地址； 得结果：二个单元，存放地址、值； 数组：按列存放； 临时变量：语义分析引入。,寄存器保护区,返回地址,A,T,B,a,例：子程序段： SUBROUTINE SWAP(A,B) T=A A=B B=T RETURN END 设：实型量占2个机器字,§8.3.2 公共语句、等价语句介绍,数据对象的物理存储空间管理，对程序的空间利用效率有很大的影响，COMMON 和E QUIVALENCE 这两个语句提供了足够强大的控制存储空间的功能。 COMMON ：处理不同程序单位之间的数据共享。通常 用于在不同程序单位之间进行数据的批量传递，它 比采用参数传递的方式效率要高。,EQUIVALENCE ： *）处理同一个程序单元中的多个对象共享一个存 储空间，以节省内存。 因此，主程序和过程之间；过程相互之间不同 变量不能用EQUIVALENCE语句来指定共用存储 单元。 *）允许用两个或更多的变量名代表同一个量。 COMMON、EQUVILENCE： 这两个语句功能过于强大，滥用会导致对程序的理解和维护变得非常困难。,FORTRAN语言存储空间的模式描述： 1).存储单位：存储单个FORTRAN数据值的内存空间; integer,real,boolean：占一个机器字; Complex(复数),double(双精度实型)： 占两个相继的机器字;,例：INTEGER I, J, K(3) COMPLEX X REAL A,数据区,2).存储序列： 任意多个连续的数据单位就构成了一个存储序列； 一个数组对象构成一个存储序列； 一个公用块构成一个存储序列； 等价语句中的等价列表的所有对象构成一 个存储序列； 3).两个数据对象如果共享了同一个存储序列，那么它 们就称为具有存储关联的关系。如果它们只是共享 了同一个存储序列的部分存储单位，那么它们称为 具有部分存储关联的关系。,公共区：一块有名字的、被共享的存储空间。 无名公共区：一个； 有名公共区：多个； 公共语句： COMMON /公共块名1/ 变量名表1 , /公共块名2/变量名表2. 其中： *)变量名不得是哑元、可分配数组、自动对象等。 *)不同程序单元中,同一公用区中的变量名可以不同。 按位置一一对应共享同一存储单元中的数值。 *) COMMON语句是说明语句，必须在可执行语句之前。,主: common /X,Y common /B1/A,B,C/D,E,F(5),子1: common /I,Q(5) common /B1/F(5)/B2/P(3),子2: common /B1/X(4) common /B2/Y,Z Complx Y,Z,F、Q部分存储关联,X、I存储关联,COMMON /COM/M(5),N(4) CALL FIB WRITE(*,'(1X,4I3)')N END SUBROUTINE FIB COMMON /COM/J(5),K(4) DO 10 I=1,4 K(I)=J(I+1) J(I) 10 CONTINUE END BLOCK DATA COMMON /COM/K(5),L(4) DATA K/8,7,10,4,13/ END,答案： -1 3 -6 9,等价语句： EQUIVALENCE (变量名表1),(变量名表2), 其中： 1）等价语句是说明语句，应出现在执行语句之前； 2）每一个 (变量名表)，称为一个等价片； 3）等价片中的名字称为等价元。等价元可以是简单 变量或下标为常数的下标变量。,例：INTEGER I, J, K(3) COMPLEX X REAL A(3,3) EQUIVALENCE (X，A(2,3) ,(I,J,A(1,2),K(2),等价片,4）等价片中的每一个等价元都被分配到同一个存储单 元，只要某一个等价元赋予某值，其它的等价元 也就同时具有相同的值。 如有赋值：I=2 则 J,A(1,2)值也为2。 （注意：这种效果不是数学上的等值，而是由于 共享一个存储单元而得到的方便。),INTEGER I, J, K(3) COMPLEX X REAL A(3,3) EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2),5).不同等价片中若有相同名字(包括数组名)，则 称为等价相关，应将其合并，让更多等价元共 享存储单元。(如A) 6).若两个数组的某一个元素等价，则数组的其他 元素也产生等价关系（如A, K）,INTEGER I, J, K(3) COMPLEX X REAL A(3,3) EQUIVALENCE (X，A(2,3) ) , (I, J, A(1,2), K(2) ),例：INTEGER I,J,K(3) COMPLEX X REAL A(3,3) EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2),7).占用单元数不同的名字等价时，占用单元少的 名字和占用单元多的名字的前半部分占用同一 单元；(X,A),存储区,公共语句与等价语句同时出现： .若一个名字与公共区中元素等价，则该名字分 配到公共区； .等价语句不能改变公共语句确定好的次序和位 置，但可以用EQUIVALENCE语句来扩大公共区；,DIMENSION A(4),B(4) COMMON A,C EQUIVALENCE(A(3),B(1),公共语句与等价语句同时出现： .等价语句不能改变公共语句确定好的次序和位 置，等价元素位置不得小于公共区起始位置 （否则称为“冒头” ）,DIMENSION A(4),B(4) COMMON A,C EQUIVALENCE (A(1),B(2),B是由等价语句带进来的，但B的元素向前越过了公用区的第一个存储单元 “冒头”,PROGRAM MAIN COMMON /A1/X,Y,Z COMMON S1,S2 EQUIVALENCE(X,X3) S1=2.0 S2=3.0 CALL S(X1,X2) PRINT *,X,Y,Z PRINT *, X1,X2,X3 PRINT *,S1,S2 END,SUBROUTINE S(Y1,Y2) COMMON /A1/A,B,C/Q1 A=A+3.0 B=B+4.0 C=C+5.0 Y1=A+B Y2=C-A Q1=Q1+2.0 END,BLOCK DATA COMMON /A1/P,Q,R DATA P,Q,R/3*1.0/ END,1.0 1.0 1.0,2.0 3.0,4.0 5.0 6.0,9.0 2.0,4.0,输出：4.0 5.0 6.0 9.0 2.0 4.0 4.0 3.0,A1区,无名区,局部区,例：SUBROUTINE SS(I)； INTEGER K, T, Q, S ； REAL B(5), C(6), M COMMON / Y, Z, D COMPLEX D(2) EQUIVALENCE (Z,C(1),(C(3),S),(Q,B(2),(T,B(4),§8.3.3 公共语句的处理,1).新增公共块表(COMLIST)，主要栏目项如下：,2).符号表中增加一个栏目项CMP， 将同一公共区中的元素按出现 顺序拉成一条链(指向同一条公 共链的下一个元素)；,COMMON X, Y COMMON /B1/A, B, C / / D, E, F(100),无名公共区： XYDEF B1区： ABC Length栏：地址分配时确定,§8.3.4 等价语句的处理,1). 主要工作： 找出存在等价关系的等价元，将它们构成等价环； 指出各等价元的首地址关系，以便进行内存分配。,EQUIVALENCE (X,Y), (I,J,K(2),等价元的首地址关系 X首地址=Y首地址, I首地址=J首地址=K的首地址+1,2).实现方式：在符号表中增设两栏：EQ和OFFSET。 EQ：等价环形链，指向下一个等价元的入口； 若为null，则说明该名字不是等价元； （若等价环中只有一个等价元，则指向自身） OFFSET：相对位移量，用来指出各等价元存储 首地址之间的地址相对关系。,INTEGER I,J,K(3) REAL X,Y EQUIVALENCE (X,Y),(I,J,K(2),形式化的归并算法P251,公用区地址分配算法 P252,局部区等价环分配算法 P253,局部区地址分配算法,Subroutine SS(I) Integer K, T, Q Real B(5), C(6) Common / Y, Z, D Complex D(2) Real M Equivalence (Z, C(1) , (Q, B(2), (T, B(4),Subroutine SS(I) Integer K, T, Q Real B(5), C(6) Common / Y, Z, D Complex D(2) Real M Equiv (Z, C(1) , (Q,B(2), (T,B(4),§8.3.6 临时变量的地址分配,1、临时变量：编译程序引入，存放中间结果。 2、临时变量的作用域： 定值(赋值)=最后一次被引用。 3、地址分配原则： 若两个临时变量的作用域不相交，则它们可 分配在同一单元中。 临时变量名均分配在局部数据区。,1) 对临时变量T，求出T的作用域S； 2) 依次检查已分配单元I1 , I2 , Ik , 若存在Ij ,S与Ij已有变量的作用域均不相交， 即：SSj,p = p=1 mj 则将Ij分配给T，将T的作用域S标记到Ij上。 3）若不存在这样的Ij (T与所有已分配单元的作用域都 冲突)，则分配一个新的单元Ik+1,作用域S标记到Ik+1 .,方案,例：X:=A+B-(C+D)+(E+F)*(G+H)翻译后得：,a a+1 a+2 a+3 a+2 a+1 a,T5 (5)(6),T6 (6)(7),T7 (7)(8),分配方案： 前提：临时变量定值一次，引用一次，临时变量的 作用域是嵌套的或不相交的。 （产生中间代码的方法必须保证这一点）。 用“栈”存放临时单元的值，需要的临时变量的单元数等于最大的嵌套层数。 定值：分配栈顶单元； 引用：收回栈顶单元；,例：X:=A+B-(C+D)+(E+F)*(G+H)翻译后得：,各四元式，对应的 临时变量的地址,