存储空间组织-3节-缩减版

1、存储空间组织-3节-缩减版 8.3 静态存储分配静态存储分配FORTRAN语言语言 如果编译时能确定一个程序在运行时所需的存贮空如果编译时能确定一个程序在运行时所需的存贮空 间大小，则可以在编译时安排目标程序的全部数据间大小，则可以在编译时安排目标程序的全部数据 空间，并确定每个数据项的单元地址。这种存贮空空间，并确定每个数据项的单元地址。这种存贮空 间分配方法称为间分配方法称为 “静态存储分配静态存储分配”。 静态存储分配特点静态存储分配特点 1). 1). 编译时刻确定存储位置；编译时刻确定存储位置； 2). 2). 目标程序执行时不必进行存储管理。目标程序目标程序执行时不必进行存储管理。

2、目标程序 代码特别简单、高效。代码特别简单、高效。 存储空间组织-3节-缩减版 FORTRANFORTRAN语言的特点：（语言的特点：（FORTRAN 77FORTRAN 77） 1). 1). 过程不允许递归调用过程不允许递归调用 一个过程的两个活动的生存期不相交一个过程的两个活动的生存期不相交，因此，因此一一 个过程的所有活动可以使用同一个活动记录个过程的所有活动可以使用同一个活动记录； 2). 2). 每个数据名所需的存储空间大小是常数，没有每个数据名所需的存储空间大小是常数，没有 可变数组等；可变数组等； 3). 3). 数据名的性质完全确定；不能动态地建立数据数据名的性质完全确定；不

3、能动态地建立数据 结构；结构； 因此可以采用因此可以采用“静态存储分配静态存储分配”。 存储空间组织-3节-缩减版 由于每个由于每个FORTRAN FORTRAN 程序段可以独立编译，运行前由程序段可以独立编译，运行前由 装入程序把各段连成可运行的整体。装入程序把各段连成可运行的整体。 通常按数据区组织存储通常按数据区组织存储: : 每个程序段定义一个局部数据区，用来存放程序每个程序段定义一个局部数据区，用来存放程序 段中未出现在段中未出现在COMMONCOMMON里的局部名的值。里的局部名的值。 每个公用块定义一个公用数据区，用来存放公用每个公用块定义一个公用数据区，用来存放公用 块里各个名

4、字的值。块里各个名字的值。 每个数据区有一个编号，地址分配时，在符号表每个数据区有一个编号，地址分配时，在符号表 中，对每个数据名登记：中，对每个数据名登记： （所属数据区编号，在该区中的相对位置）（所属数据区编号，在该区中的相对位置） 存储空间组织-3节-缩减版 8.3.1 8.3.1 FORTRAN数据区数据区 数据区数据区= =局部区局部区(1(1个个/ /程序段程序段) )全局区全局区 主程序主程序 子程序子程序1 子程序子程序n 编编 译译 目标代码目标代码 常常 数数 局部数据区局部数据区 主主 程程 序序 . . . . . . . 无名公共区无名公共区 有名公共区有名公共区1

5、有名公共区有名公共区m . 1.1.各数据区编号，并统计各数据区编号，并统计 长度，便于分配空间；长度，便于分配空间； 2.2.数据区仅分配地址，构数据区仅分配地址，构 成映象成映象( (虚空间虚空间) )，真正，真正 的空间运行时才建立，的空间运行时才建立， 并可以使用；并可以使用； 全局区全局区 目标代码目标代码 常常 数数 局部数据区局部数据区 子子 程程 序序 1 目标代码目标代码 常常 数数 局部数据区局部数据区 子子 程程 序序 n 存储空间组织-3节-缩减版 局部数据区的内容：局部数据区的内容： 返回地址：存放此程序段结束时的返回地址。返回地址：存放此程序段结束时的返回地址。 寄

6、存器保护区：寄存器保护区：调用本调用本程序段时寄存器中的信息，当程序段时寄存器中的信息，当 本程序段结束后，可以恢复到调用前的状态；本程序段结束后，可以恢复到调用前的状态； 形式单元：存放实在参数的地址或值。形式单元：存放实在参数的地址或值。FORTRANFORTRAN语言语言 采用两种方式共存的形式。采用两种方式共存的形式。 传地址：一个单元，存放地址；传地址：一个单元，存放地址； 得结果：二个单元，存放地址、值；得结果：二个单元，存放地址、值； 数组：按列存放；数组：按列存放； 临时变量：语义分析引入。临时变量：语义分析引入。 临时变量临时变量 数组数组 简单变量简单变量 形式单元形式单元

7、 寄存器保护区寄存器保护区 返回地址返回地址 存储空间组织-3节-缩减版 地地址址名名字字 N NA AM ME E 性性质质 A AT TT TR RI IB BU UT TE ED DA A A AD DD DR R S SW WA AP P子子程程序序，二二目目 A A哑哑，实实变变量量k ka a B B哑哑，实实变变量量k ka a+ +2 2 T T实实变变量量k ka a+ +4 4 寄存器保护区寄存器保护区 返回地址返回地址 A T B a 临时变量临时变量 数组数组 简单变量简单变量 形式单元形式单元 寄存器保护区寄存器保护区 返回地址返回地址 例：子程序段：例：子程序段：

8、SUBROUTINE S)SUBROUTINE S) T=AT=A A=BA=B B=TB=T RETURNRETURN ENDEND 设：实型量占设：实型量占2 2个机器字个机器字 存储空间组织-3节-缩减版 8.3.2 8.3.2 公共语句、等价语句介绍公共语句、等价语句介绍 数据对象的物理存储空间管理，对程序的空间利用数据对象的物理存储空间管理，对程序的空间利用 效率有很大的影响，效率有很大的影响，COMMON COMMON 和和E QUIVALENCE E QUIVALENCE 这两这两 个语句提供了足够强大的控制存储空间的功能。个语句提供了足够强大的控制存储空间的功能。 COMMON

9、COMMON ：处理不同程序单位之间的数据共享。通常处理不同程序单位之间的数据共享。通常 用于在不同程序单位之间进行数据的批量传递，它用于在不同程序单位之间进行数据的批量传递，它 比采用参数传递的方式效率要高。比采用参数传递的方式效率要高。 存储空间组织-3节-缩减版 EQUIVALENCE EQUIVALENCE ： * *）处理同一个程序单元中的多个对象共享一个存）处理同一个程序单元中的多个对象共享一个存 储空间，以节省内存。储空间，以节省内存。 因此，主程序和过程之间；过程相互之间不同因此，主程序和过程之间；过程相互之间不同 变量不能用变量不能用EQUIVALENCEEQUIVALENC

10、E语句来指定共用存储语句来指定共用存储 单元。单元。 * *）允许用两个或更多的变量名代表同一个量。）允许用两个或更多的变量名代表同一个量。 COMMONCOMMON、EQUVILENCEEQUVILENCE： 这两个语句功能过于强大，这两个语句功能过于强大， 滥用会导致对程序的理解和维护变得非常困难。滥用会导致对程序的理解和维护变得非常困难。 存储空间组织-3节-缩减版 FORTRANFORTRAN语言存储空间的模式描述：语言存储空间的模式描述： 1).1).存储单位：存储单个存储单位：存储单个FORTRANFORTRAN数据值的内存空间数据值的内存空间; ; integer,real,bo

11、olean integer,real,boolean：占一个机器字：占一个机器字; ; Complex( Complex(复数复数),double(),double(双精度实型双精度实型) )： 占两个相继的机器字占两个相继的机器字; ; 例：例：INTEGER I, J, K(3) COMPLEX X REAL A IJK(1) K(2) K(3)A X 数据区数据区 存储空间组织-3节-缩减版 2).2).存储序列：存储序列： 任意多个连续的数据单位就构成了一个存储序列；任意多个连续的数据单位就构成了一个存储序列； 一个数组对象构成一个存储序列；一个数组对象构成一个存储序列； 一个公用块构

12、成一个存储序列；一个公用块构成一个存储序列； 等价语句中的等价列表的所有对象构成一等价语句中的等价列表的所有对象构成一 个存储序列；个存储序列； 3).3).两个数据对象如果共享了同一个存储序列，那么它两个数据对象如果共享了同一个存储序列，那么它 们就称为具有存储关联的关系。如果它们只是共享们就称为具有存储关联的关系。如果它们只是共享 了同一个存储序列的部分存储单位，那么它们称为了同一个存储序列的部分存储单位，那么它们称为 具有部分存储关联的关系。具有部分存储关联的关系。 存储空间组织-3节-缩减版 公共区：一块有名字的、被共享的存储空间。公共区：一块有名字的、被共享的存储空间。 无名公共区：

13、一个；无名公共区：一个； 有名公共区：多个；有名公共区：多个； 公共语句：公共语句： COMMON /COMMON /公共块名公共块名1/ 1/ 变量名表变量名表1 , 1 , / /公共块名公共块名2/2/变量名表变量名表2. 2. 其中：其中： * *) )变量名不得是哑元、可分配数组、自动对象等。变量名不得是哑元、可分配数组、自动对象等。 * *) )不同程序单元中不同程序单元中, ,同一公用区中的变量名可以不同。同一公用区中的变量名可以不同。 按位置一一对应共享同一存储单元中的数值。按位置一一对应共享同一存储单元中的数值。 * *) COMMON) COMMON语句是说明语句，必须在可

14、执行语句之前。语句是说明语句，必须在可执行语句之前。 存储空间组织-3节-缩减版 主主: 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 无名区无名区XYDEF(1) F(2) F(3) F(4)F(5) I Q(1) Q(2) Q(3) Q(4) Q(5) B1 区区 ABC F(1) F(2) F(3) F(4)F(5) X(1) X(2) X(3) X(4) B2 区区 P(1)

15、P(2) P(3) YZ 无名区无名区B1区区 B2区区 主主9 93 30 0 子子1 16 65 53 3 子子2 20 04 44 4 最终最终 长度长度 9 95 54 4 F F、Q Q部分部分 存储关联存储关联 X X、I I存存 储关联储关联 存储空间组织-3节-缩减版 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

16、/K(5),L(4) DATA K/8,7,10,4,13/ END 答案：答案： -1 3 -6 9-1 3 -6 9 COMCOM区区 主程序主程序 FIBFIBDATADATA M(1)M(1)J(1)J(1)K(1)K(1)8 8 M(2)M(2)J(2)J(2)K(2)K(2)7 7 M(3)M(3)J(3)J(3)K(3)K(3)1010 M(4)M(4)J(4)J(4)K(4)K(4)4 4 M(5)M(5)J(5)J(5)K(5)K(5)1313 N(1)N(1)K(1)K(1) -1-1 L(1)L(1) N(2)N(2)K(2)K(2)3 3L(2)L(2) N(3)N(3

17、)K(3)K(3) -6-6 L(3)L(3) N(4)N(4)K(4)K(4)9 9L(4)L(4) 存储空间组织-3节-缩减版 等价语句：等价语句： EQUIVALENCE (EQUIVALENCE (变量名表变量名表1),(1),(变量名表变量名表2),2), 其中：其中： 1 1）等价语句是说明语句，应出现在执行语句之前；）等价语句是说明语句，应出现在执行语句之前； 2 2）每一个）每一个 ( (变量名表变量名表) )，称为一个等价片；，称为一个等价片； 3 3）等价片中的名字称为等价元。等价元可以是简单）等价片中的名字称为等价元。等价元可以是简单 变量或下标为常数的下标变量。变量或下

18、标为常数的下标变量。 例：例：INTEGER I, J, K(3)INTEGER I, J, K(3) COMPLEX XCOMPLEX X REAL A(3,3) REAL A(3,3) EQUIVALENCE EQUIVALENCE (X(X，A(2,3)A(2,3) , ,(I,J,A(1,2),K(2)(I,J,A(1,2),K(2) 等价片等价片 存储空间组织-3节-缩减版 4 4）等价片中的每一个等价元都被分配到同一个存储单）等价片中的每一个等价元都被分配到同一个存储单 元，只要某一个等价元赋予某值，其它的等价元元，只要某一个等价元赋予某值，其它的等价元 也就同时具有相同的值。也就

19、同时具有相同的值。 如有赋值：如有赋值：I=2 I=2 则则 J,A(1,2)J,A(1,2)值也为值也为2 2。 （注意：这种效果不是数学上的等值，而是由于（注意：这种效果不是数学上的等值，而是由于 共享一个存储单元而得到的方便。共享一个存储单元而得到的方便。) ) INTEGER I, J, K(3) INTEGER I, J, K(3) COMPLEX XCOMPLEX X REAL A(3,3) REAL A(3,3) EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2) EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2) 存储空间组织

20、-3节-缩减版 5).5).不同等价片中若有相同名字不同等价片中若有相同名字( (包括数组名包括数组名) )，则，则 称为等价相关，应将其合并，让更多等价元共称为等价相关，应将其合并，让更多等价元共 享存储单元。享存储单元。( (如如A)A) 6).6).若两个数组的某一个元素等价，则数组的其他若两个数组的某一个元素等价，则数组的其他 元素也产生等价关系（如元素也产生等价关系（如A, KA, K） INTEGER I, J, K(3) COMPLEX X REAL A(3,3) EQUIVALENCE (X，A(2,3) ) , (I, J, A(1,2), K(2) ) 存储空间组织-3节-

21、缩减版 例：例：INTEGER I,J,K(3)INTEGER I,J,K(3) COMPLEX X COMPLEX X REAL A(3,3) REAL A(3,3) EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2)EQUIVALENCE (X,A(2,3),(I,J,A(1,2),K(2) X A(1,1)A(2,1) A(3,1) A(1,2)A(2,2)A(3,2)A(1,3)A(2,3) A(3,3) I J K(1)K(2)K(3) 7).7).占用单元数不同的名字等价时，占用单元少的占用单元数不同的名字等价时，占用单元少的 名字和占用单元多的名字的前半

22、部分占用同一名字和占用单元多的名字的前半部分占用同一 单元；单元；(X,A) (X,A) 存储区存储区 存储空间组织-3节-缩减版 公共语句与等价语句同时出现：公共语句与等价语句同时出现： . .若一个名字与公共区中元素等价，则该名字分若一个名字与公共区中元素等价，则该名字分 配到公共区；配到公共区； . .等价语句不能改变公共语句确定好的次序和位等价语句不能改变公共语句确定好的次序和位 置，但可以用置，但可以用EQUIVALENCEEQUIVALENCE语句来扩大公共区；语句来扩大公共区； A(1)A(1) A(2)A(2) A(3)A(3) A(4)A(4)C C B(1)B(1) B(2

23、)B(2) B(3)B(3) B(4)B(4) DIMENSION A(4),B(4)DIMENSION A(4),B(4) COMMON A,CCOMMON A,C EQUIVALENCE(A(3),B(1)EQUIVALENCE(A(3),B(1) 存储空间组织-3节-缩减版 公共语句与等价语句同时出现：公共语句与等价语句同时出现： . .等价语句不能改变公共语句确定好的次序和位等价语句不能改变公共语句确定好的次序和位 置，等价元素位置不得小于公共区起始位置置，等价元素位置不得小于公共区起始位置 （否则称为（否则称为“冒头冒头” ） A(1)A(1) A(2)A(2) A(3)A(3) A

24、(4)A(4)C C B(1)B(1) B(2)B(2) B(3)B(3) B(4)B(4) DIMENSION A(4),B(4)DIMENSION A(4),B(4) COMMON A,CCOMMON A,C EQUIVALENCE (A(1),B(2)EQUIVALENCE (A(1),B(2) B B是由等价语句带进来的，但是由等价语句带进来的，但B B的元素向前越过了公用区的元素向前越过了公用区 的第一个存储单元的第一个存储单元 “冒头冒头” 存储空间组织-3节-缩减版 PROGRAM MAIN COMMON /A1/X,Y,Z COMMON S1,S2 EQUIVALENCE(X,

25、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 X Y Z X3 A B C P Q R S1 S2 Q1 X1 X2 Y1 Y2 1.0 1.0 1.0 2.0 3.0 4.0 5.0 6.0 9.

26、0 2.0 4.0 输出：输出：4.0 5.0 6.0 9.0 2.0 4.0 4.0 3.0 A1区区 无名区无名区 局部区局部区 存储空间组织-3节-缩减版 例：例：SUBROUTINE SS(I)SUBROUTINE SS(I)； INTEGER K, T, Q, S INTEGER K, T, Q, S ； REAL B(5), C(6), M REAL B(5), C(6), M COMMON / Y, Z, D COMMON / Y, Z, D COMPLEX D(2) COMPLEX D(2) EQUIVALENCE (Z,C(1),(C(3),S),(Q,B(2),(T,B(4

27、)EQUIVALENCE (Z,C(1),(C(3),S),(Q,B(2),(T,B(4) 无无 名名 公公 共共 区区 0 0Y Y 1 1Z ZC(1)C(1) 2 2 D(1)D(1) C(2)C(2) 3 3S SC(3)C(3) 4 4 D(2)D(2) C(4)C(4) 局局 部部 数数 据据 区区 0 0I I 1 1K K 2 2B(1)B(1) 3 3Q QB(2)B(2) 4 4B(3)B(3) 等价片等价片 5 5T TB(4)B(4) 6 6B(5)B(5) 7 7M等价片分配后等价片分配后 存储空间组织-3节-缩减版 8.3.3 公共语句的处理公共语句的处理 1).1

28、).新增公新增公共块共块表表(COMLIST)(COMLIST)，主要栏目项如下：主要栏目项如下： 2).2).符号表中增加一个栏目项符号表中增加一个栏目项CMPCMP， 将同一公共区中的元素按出现将同一公共区中的元素按出现 顺序拉成一条链顺序拉成一条链( (指向同一条公指向同一条公 共链的下一个元素共链的下一个元素) )； COMLISTCOMLIST NAMENAMELENGTHLENGTHFTFTLTLT 公公共块共块名名长度长度链首在符号表链首在符号表 中的入口地址中的入口地址 链尾在符号表链尾在符号表 中的入口地址中的入口地址 符号表符号表 NameName CMPCMP 存储空间组

29、织-3节-缩减版 COMMON X, YCOMMON X, Y COMMON /B1/A, B, C / / D, E, F(100)COMMON /B1/A, B, C / / D, E, F(100) 符号表符号表 NameName DADACMPCMP 1 1X X2 2 2 2Y Y6 6 3 3A AB1B14 4 4 4B BB1B15 5 5 5C CB1B10 0 6 6D D7 7 7 7E E8 8 8 8F F0 0 COMLIST COMLIST NameName LengthLengthFTFTLTLT 1 18 8 B1B13 35 5 无名公共区：无名公共区： X

30、YDEFXYDEF B1B1区：区： ABCABC LengthLength栏：地址分配时确定栏：地址分配时确定 存储空间组织-3节-缩减版 8.3.4 等价语句的处理等价语句的处理 1). 主要工作：主要工作： 找出存在等价关系的等价元，将它们构成等价环；找出存在等价关系的等价元，将它们构成等价环； 指出各等价元的首地址关系，以便进行内存分配。指出各等价元的首地址关系，以便进行内存分配。 EQUIVALENCE (X,Y), (I,J,K(2) EQUIVALENCE (X,Y), (I,J,K(2) X XY YP PI IJ JP PK K 等价元的首地址关系等价元的首地址关系 X X首

31、地址首地址=Y=Y首地址首地址, , I I首地址首地址=J=J首地址首地址=K=K的首地址的首地址+1+1 存储空间组织-3节-缩减版 2).2).实现方式：在符号表中增设两栏：实现方式：在符号表中增设两栏：EQEQ和和OFFSETOFFSET。 EQEQ：等价环形链，指向下一个等价元的入口；：等价环形链，指向下一个等价元的入口； 若为若为nullnull，则说明该名字不是等价元；，则说明该名字不是等价元； （若等价环中只有一个等价元，则指向自身）（若等价环中只有一个等价元，则指向自身） OFFSETOFFSET：相对位移量，用来指出各等价元存储：相对位移量，用来指出各等价元存储 首地址之间

32、的地址相对关系。首地址之间的地址相对关系。 INTEGER I,J,K(3)INTEGER I,J,K(3) REAL X,YREAL X,Y EQUIVALENCE (X,Y),(I,J,K(2)EQUIVALENCE (X,Y),(I,J,K(2) NAMENAME OFFSETOFFSETEQEQ 1 1I I0 03 3 2 2J J0 01 1 3 3K K-1-12 2 4 4X X0 05 5 5 5Y Y0 04 4 X XY YP P I IJ JP PK K 存储空间组织-3节-缩减版 形式化形式化 的归并的归并 算法算法 P251P251 存储空间组织-3节-缩减版 公用

33、区地址分配算法公用区地址分配算法 P252P252 局部区等价环分配算法局部区等价环分配算法 P253 P253 局部区地址分配算法局部区地址分配算法 存储空间组织-3节-缩减版 无无 名名 公公 共共 区区 0 0Y Y 1 1Z ZC(1)C(1) 2 2 D(1)D(1) C(2)C(2) 3 3C(3)C(3) 4 4 D(2)D(2) C(4)C(4) 5 5C(5)C(5) 6 6C(6)C(6) 符符 号号 表表 Name Size DA Addr 1 1I1 10 00 0 2 2K1 10 01 1 3 3T1 10 05 5 4 4Q1 10 03 3 5 5B5 50 0

34、2 2 6 6C6 61281281 1 7 7Y1 11281280 0 8 8Z1 11281281 1 9 9D4 41281282 2 1010M1 10 07 7 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) COMLIST Name Length FTLT 无名无名779 存储空间组织-3节-缩减版 局局 部部 数数 据据 区区 0 0I I 1 1K K 2 2B(1)B(

35、1) 3 3Q QB(2)B(2) 4 4B(3)B(3) 等价片等价片 5 5 T TB(4)B(4) 6 6B(5)B(5) 7 7 M 符符 号号 表表 NameSize DA Addr 1 1I1 10 00 0 2 2K1 10 01 1 3 3T1 10 05 5 4 4Q1 10 03 3 5 5B5 50 02 2 6 6C6 61281281 1 7 7Y1 11281280 0 8 8Z1 11281281 1 9 9D4 41281282 2 1010M1 10 07 7 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) 存储空间组织-3节-缩减版 8.3.6 临时变量的地址分配临时变量的地址分配 1 1、临时变量：编译程序引入，存放中间结果。临时变量：编译程序引入，存放中间结果。 2 2、临时变量的作用域：、临时变量的作用域： 定值定值( (赋值赋值)=)=最后一次被引用。最后一次被引用。 3 3、地址地址分配原则：分配原则： 若两个临时变量的作用域不相交，则它们可若两个临时变量的作用域不相交，则它们可 分配在同一单元中。分配在同一单元中。 临时变量名均分