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

8.3静态存储分配FORTRAN语言,如果编译时能确定一个程序在运行时所需的存贮空间大小，则可以在编译时安排目标程序的全部数据空间，并确定每个数据项的单元地址。这种存贮空间分配方法称为“静态存储分配”。静态存储分配特点1).编译时刻确定存储位置；2).目标程序执行时不必进行存储管理。目标程序代码特别简单、高效。,FORTRAN语言的特点：（FORTRAN77）1).过程不允许递归调用一个过程的两个活动的生存期不相交，因此一个过程的所有活动可以使用同一个活动记录；2).每个数据名所需的存储空间大小是常数，没有可变数组等；3).数据名的性质完全确定；不能动态地建立数据结构；因此可以采用“静态存储分配”。,由于每个FORTRAN程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储:每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记：（所属数据区编号，在该区中的相对位置）,8.3.1FORTRAN数据区,数据区=局部区(1个/程序段)全局区,编译,.,.,.,1.各数据区编号，并统计长度，便于分配空间；2.数据区仅分配地址，构成映象(虚空间)，真正的空间运行时才建立，并可以使用；,局部数据区的内容：返回地址：存放此程序段结束时的返回地址。寄存器保护区：调用本程序段时寄存器中的信息，当本程序段结束后，可以恢复到调用前的状态；形式单元：存放实在参数的地址或值。FORTRAN语言采用两种方式共存的形式。传地址：一个单元，存放地址；得结果：二个单元，存放地址、值；数组：按列存放；临时变量：语义分析引入。,寄存器保护区,返回地址,A,T,B,a,例：子程序段：SUBROUTINESWAP(A,B)T=AA=BB=TRETURNEND设：实型量占2个机器字,8.3.2公共语句、等价语句介绍,数据对象的物理存储空间管理，对程序的空间利用效率有很大的影响，COMMON和EQUIVALENCE这两个语句提供了足够强大的控制存储空间的功能。COMMON：处理不同程序单位之间的数据共享。通常用于在不同程序单位之间进行数据的批量传递，它比采用参数传递的方式效率要高。,EQUIVALENCE：*）处理同一个程序单元中的多个对象共享一个存储空间，以节省内存。因此，主程序和过程之间；过程相互之间不同变量不能用EQUIVALENCE语句来指定共用存储单元。*）允许用两个或更多的变量名代表同一个量。COMMON、EQUVILENCE：这两个语句功能过于强大，滥用会导致对程序的理解和维护变得非常困难。,FORTRAN语言存储空间的模式描述：1).存储单位：存储单个FORTRAN数据值的内存空间;integer,real,boolean：占一个机器字;Complex(复数),double(双精度实型)：占两个相继的机器字;,例：INTEGERI,J,K(3)COMPLEXXREALA,数据区,2).存储序列：任意多个连续的数据单位就构成了一个存储序列；一个数组对象构成一个存储序列；一个公用块构成一个存储序列；等价语句中的等价列表的所有对象构成一个存储序列；3).两个数据对象如果共享了同一个存储序列，那么它们就称为具有存储关联的关系。如果它们只是共享了同一个存储序列的部分存储单位，那么它们称为具有部分存储关联的关系。,公共区：一块有名字的、被共享的存储空间。无名公共区：一个；有名公共区：多个；公共语句：COMMON/公共块名1/变量名表1,/公共块名2/变量名表2.其中：*)变量名不得是哑元、可分配数组、自动对象等。*)不同程序单元中,同一公用区中的变量名可以不同。按位置一一对应共享同一存储单元中的数值。*)COMMON语句是说明语句，必须在可执行语句之前。,主:common/X,Ycommon/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,ZComplxY,Z,F、Q部分存储关联,X、I存储关联,COMMON/COM/M(5),N(4)CALLFIBWRITE(*,(1X,4I3)NENDSUBROUTINEFIBCOMMON/COM/J(5),K(4)DO10I=1,4K(I)=J(I+1)J(I)10CONTINUEENDBLOCKDATACOMMON/COM/K(5),L(4)DATAK/8,7,10,4,13/END,答案：-13-69,等价语句：EQUIVALENCE(变量名表1),(变量名表2),其中：1）等价语句是说明语句，应出现在执行语句之前；2）每一个(变量名表)，称为一个等价片；3）等价片中的名字称为等价元。等价元可以是简单变量或下标为常数的下标变量。,例：INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X，A(2,3),(I,J,A(1,2),K(2),等价片,4）等价片中的每一个等价元都被分配到同一个存储单元，只要某一个等价元赋予某值，其它的等价元也就同时具有相同的值。如有赋值：I=2则J,A(1,2)值也为2。（注意：这种效果不是数学上的等值，而是由于共享一个存储单元而得到的方便。),INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3),(I,J,A(1,2),K(2),5).不同等价片中若有相同名字(包括数组名)，则称为等价相关，应将其合并，让更多等价元共享存储单元。(如A)6).若两个数组的某一个元素等价，则数组的其他元素也产生等价关系（如A,K）,INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X，A(2,3),(I,J,A(1,2),K(2),例：INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3),(I,J,A(1,2),K(2),7).占用单元数不同的名字等价时，占用单元少的名字和占用单元多的名字的前半部分占用同一单元；(X,A),存储区,公共语句与等价语句同时出现：.若一个名字与公共区中元素等价，则该名字分配到公共区；.等价语句不能改变公共语句确定好的次序和位置，但可以用EQUIVALENCE语句来扩大公共区；,DIMENSIONA(4),B(4)COMMONA,CEQUIVALENCE(A(3),B(1),公共语句与等价语句同时出现：.等价语句不能改变公共语句确定好的次序和位置，等价元素位置不得小于公共区起始位置（否则称为“冒头”）,DIMENSIONA(4),B(4)COMMONA,CEQUIVALENCE(A(1),B(2),B是由等价语句带进来的，但B的元素向前越过了公用区的第一个存储单元“冒头”,PROGRAMMAINCOMMON/A1/X,Y,ZCOMMONS1,S2EQUIVALENCE(X,X3)S1=2.0S2=3.0CALLS(X1,X2)PRINT*,X,Y,ZPRINT*,X1,X2,X3PRINT*,S1,S2END,SUBROUTINES(Y1,Y2)COMMON/A1/A,B,C/Q1A=A+3.0B=B+4.0C=C+5.0Y1=A+BY2=C-AQ1=Q1+2.0END,BLOCKDATACOMMON/A1/P,Q,RDATAP,Q,R/3*1.0/END,1.01.01.0,2.03.0,4.05.06.0,9.02.0,4.0,输出：4.05.06.09.02.04.04.03.0,A1区,无名区,局部区,例：SUBROUTINESS(I)；INTEGERK,T,Q,S；REALB(5),C(6),MCOMMON/Y,Z,DCOMPLEXD(2)EQUIVALENCE(Z,C(1),(C(3),S),(Q,B(2),(T,B(4),8.3.3公共语句的处理,1).新增公共块表(COMLIST)，主要栏目项如下：,2).符号表中增加一个栏目项CMP，将同一公共区中的元素按出现顺序拉成一条链(指向同一条公共链的下一个元素)；,COMMONX,YCOMMON/B1/A,B,C/D,E,F(100),无名公共区：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：相对位移量，用来指出各等价元存储首地址之间的地址相对关系。,INTEGERI,J,K(3)REALX,YEQUIVALENCE(X,Y),(I,J,K(2),形式化的归并算法P251,公用区地址分配算法P252,局部区等价环分配算法P253,局部区地址分配算法,SubroutineSS(I)IntegerK,T,QRealB(5),C(6)Common/Y,Z,DComplexD(2)RealMEquivalence(Z,C(1),(Q,B(2),(T,B(4),SubroutineSS(I)IntegerK,T,QRealB(5),C(6)Common/Y,Z,DComplexD(2)RealMEquiv(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=1mj则将Ij分配给T，将T的作用域S标记到Ij上。3）若不存在这样的Ij(T与所有已分配单元的作用域都冲突)，则分配一个新的单元Ik+1,作用域S标记到Ik+1.,方案,例：X:=A+B-(C