《存储空间组织-3节-缩减.ppt》由会员分享，可在线阅读，更多相关《存储空间组织-3节-缩减.ppt（34页珍藏版）》请在三一办公上搜索。
1、8.3 静态存储分配FORTRAN语言,如果编译时能确定一个程序在运行时所需的存贮空间大小，则可以在编译时安排目标程序的全部数据空间，并确定每个数据项的单元地址。这种存贮空间分配方法称为“静态存储分配”。静态存储分配特点 1).编译时刻确定存储位置；2).目标程序执行时不必进行存储管理。目标程序 代码特别简单、高效。,FORTRAN语言的特点：（FORTRAN 77）1).过程不允许递归调用 一个过程的两个活动的生存期不相交，因此一 个过程的所有活动可以使用同一个活动记录；2).每个数据名所需的存储空间大小是常数，没有 可变数组等；3).数据名的性质完全确定；不能动态地建立数据 结构；因此可以
2、采用“静态存储分配”。,由于每个FORTRAN 程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储:每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记：（所属数据区编号，在该区中的相对位置）,8.3.1 FORTRAN数据区,数据区=局部区(1个/程序段)全局区,编译,.,.,.,1.各数据区编号，并统计 长度，便于分配空间；2.数据区仅分配地址，构 成映象(虚空间)，真正 的空间运行时才建立，并可以使用；,局部
3、数据区的内容：返回地址：存放此程序段结束时的返回地址。寄存器保护区：调用本程序段时寄存器中的信息，当 本程序段结束后，可以恢复到调用前的状态；形式单元：存放实在参数的地址或值。FORTRAN语言 采用两种方式共存的形式。传地址：一个单元，存放地址；得结果：二个单元，存放地址、值；数组：按列存放；临时变量：语义分析引入。,寄存器保护区,返回地址,A,T,B,a,例：子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND设：实型量占2个机器字,8.3.2 公共语句、等价语句介绍,数据对象的物理存储空间管理，对程序的空间利用效率有很大的影响，COMMON 和E QUI
4、VALENCE 这两个语句提供了足够强大的控制存储空间的功能。COMMON：处理不同程序单位之间的数据共享。通常用于在不同程序单位之间进行数据的批量传递，它比采用参数传递的方式效率要高。,EQUIVALENCE：*）处理同一个程序单元中的多个对象共享一个存 储空间，以节省内存。因此，主程序和过程之间；过程相互之间不同 变量不能用EQUIVALENCE语句来指定共用存储 单元。*）允许用两个或更多的变量名代表同一个量。COMMON、EQUVILENCE：这两个语句功能过于强大，滥用会导致对程序的理解和维护变得非常困难。,FORTRAN语言存储空间的模式描述：1).存储单位：存储单个FORTRAN
5、数据值的内存空间;integer,real,boolean：占一个机器字;Complex(复数),double(双精度实型)：占两个相继的机器字;,例：INTEGER I,J,K(3)COMPLEX X REAL A,数据区,2).存储序列：任意多个连续的数据单位就构成了一个存储序列；一个数组对象构成一个存储序列；一个公用块构成一个存储序列；等价语句中的等价列表的所有对象构成一 个存储序列；3).两个数据对象如果共享了同一个存储序列，那么它 们就称为具有存储关联的关系。如果它们只是共享 了同一个存储序列的部分存储单位，那么它们称为 具有部分存储关联的关系。,公共区：一块有名字的、被共享的存储空
6、间。无名公共区：一个；有名公共区：多个；公共语句：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/
7、COM/M(5),N(4)CALL FIB WRITE(*,(1X,4I3)N END SUBROUTINE FIBCOMMON/COM/J(5),K(4)DO 10 I=1,4K(I)=J(I+1)J(I)10 CONTINUE ENDBLOCK 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）等价片中的名字称为等价元。等价元可以是简单 变量或下标为常数的下标变量
8、。,例：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).不同等价片中若有相同名字(包括数组名
9、)，则 称为等价相关，应将其合并，让更多等价元共 享存储单元。(如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),存储区,公共语句与等价语句同时出现：.
10、若一个名字与公共区中元素等价，则该名字分 配到公共区；.等价语句不能改变公共语句确定好的次序和位 置，但可以用EQUIVALENCE语句来扩大公共区；,DIMENSION A(4),B(4)COMMON A,CEQUIVALENCE(A(3),B(1),公共语句与等价语句同时出现：.等价语句不能改变公共语句确定好的次序和位 置，等价元素位置不得小于公共区起始位置（否则称为“冒头”）,DIMENSION A(4),B(4)COMMON A,CEQUIVALENCE(A(1),B(2),B是由等价语句带进来的，但B的元素向前越过了公用区的第一个存储单元“冒头”,PROGRAM MAIN COMMO
11、N/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
12、.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,YCOMMON/B1/A,B,C/D,E,F(100)
13、,无名公共区：XYDEFB1区：ABCLength栏：地址分配时确定,8.3.4 等价语句的处理,1).主要工作：找出存在等价关系的等价元，将它们构成等价环；指出各等价元的首地址关系，以便进行内存分配。,EQUIVALENCE(X,Y),(I,J,K(2),等价元的首地址关系 X首地址=Y首地址,I首地址=J首地址=K的首地址+1,2).实现方式：在符号表中增设两栏：EQ和OFFSET。EQ：等价环形链，指向下一个等价元的入口；若为null，则说明该名字不是等价元；（若等价环中只有一个等价元，则指向自身）OFFSET：相对位移量，用来指出各等价元存储 首地址之间的地址相对关系。,INTEGER
14、 I,J,K(3)REAL X,YEQUIVALENCE(X,Y),(I,J,K(2),形式化的归并算法P251,公用区地址分配算法 P252,局部区等价环分配算法 P253,局部区地址分配算法,Subroutine SS(I)Integer K,T,QReal B(5),C(6)Common/Y,Z,DComplex D(2)Real MEquivalence(Z,C(1),(Q,B(2),(T,B(4),Subroutine SS(I)Integer K,T,QReal B(5),C(6)Common/Y,Z,DComplex D(2)Real MEquiv(Z,C(1),(Q,B(2),
15、(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)翻译后得：,aa+1a+2a+3a+2a+1a,T5(5)(6),T6(6)(7),T7(7)(8),分配方案：前提：临时变量定值一次，引用一次，临时变量的 作用域是嵌套的或不相交的。（产生中间代码的方法必须保证这一点）。用“栈”存放临时单元的值，需要的临时变量的单元数等于最大的嵌套层数。定值：分配栈顶单元；引用：收回栈顶单元；,例：X:=A+B-(C+D)+(E+F)*(G+H)翻译后得：,各四元式，对应的临时变量的地址,
