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

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

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

3、态存储分配静态存储分配”。由于每个由于每个FORTRAN FORTRAN 程序段可以独立编译，运行前由程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。装入程序把各段连成可运行的整体。通常按数据区组织存储通常按数据区组织存储: :每个程序段定义一个局部数据区，用来存放程序段每个程序段定义一个局部数据区，用来存放程序段中未出现在中未出现在COMMONCOMMON里的局部名的值。里的局部名的值。每个公用块定义一个公用数据区，用来存放公用块每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。里各个名字的值。每个数据区有一个编号，地址分配时，在符号表中，每个数据区有一个编号，地址分配

4、时，在符号表中，对每个数据名登记：对每个数据名登记： （所属数据区编号，在该区中的相对位置）（所属数据区编号，在该区中的相对位置）8.3.1 FORTRAN8.3.1 FORTRAN数据区数据区数据区数据区= =局部区局部区(1(1个个/ /程序段程序段) )全局区全局区主程序主程序子程序子程序1子程序子程序n编编译译目标代码目标代码 常常 数数 局部数据区局部数据区主主程程序序. . . .无名公共区无名公共区有名公共区有名公共区1有名公共区有名公共区m.1.1.各数据区编号，并统计各数据区编号，并统计 长度，便于分配空间；长度，便于分配空间； 2.2.数据区仅分配地址，构数据区仅分配地址，

5、构 成映象成映象( (虚空间虚空间) )，真正，真正 的空间运行时才建立，的空间运行时才建立， 并可以使用；并可以使用；全局区全局区目标代码目标代码 常常 数数 局部数据区局部数据区子子程程序序 1目标代码目标代码 常常 数数 局部数据区局部数据区子子程程序序 n局部数据区的内容：局部数据区的内容： 返回地址：存放此程序段结束时的返回地址。返回地址：存放此程序段结束时的返回地址。寄存器保护区：调用本程序段时寄存器中的信息，当寄存器保护区：调用本程序段时寄存器中的信息，当 本程序段结束后，可以恢复到调用前的状态；本程序段结束后，可以恢复到调用前的状态；形式单元：存放实在参数的地址或值。形式单元：

6、存放实在参数的地址或值。FORTRAN语言语言 采用两种方式共存的形式。采用两种方式共存的形式。 传地址：一个单元，存放地址；传地址：一个单元，存放地址； 得结果：二个单元，存放地址、值；得结果：二个单元，存放地址、值；数组：按列存放；数组：按列存放；临时变量：语义分析引入。临时变量：语义分析引入。临时变量临时变量数组数组简单变量简单变量形式单元形式单元寄存器保护区寄存器保护区返回地址返回地址地地址址名名字字N NA AM ME E性性质质A AT TT TR RI IB BU UT TE ED DA A A AD DD DR RS SW WA AP P子子程程序序，二二目目A A哑哑，实实变

7、变量量k ka aB B哑哑，实实变变量量k ka a+ +2 2T T实实变变量量k ka a+ +4 4寄存器保护区寄存器保护区返回地址返回地址ATBa临时变量临时变量数组数组简单变量简单变量形式单元形式单元寄存器保护区寄存器保护区返回地址返回地址例：子程序段：例：子程序段：SUBROUTINE SWAP(A,B)SUBROUTINE SWAP(A,B)T=AT=AA=BA=BB=TB=TRETURNRETURNENDEND设：实型量占设：实型量占2 2个机器字个机器字8.3.2 8.3.2 公共语句、等价语句介绍公共语句、等价语句介绍数据对象的物理存储空间管理，对程序的空间利用数据对象的

8、物理存储空间管理，对程序的空间利用效率有很大的影响，效率有很大的影响，COMMON COMMON 和和E QUIVALENCE E QUIVALENCE 这两这两个语句提供了足够强大的控制存储空间的功能。个语句提供了足够强大的控制存储空间的功能。COMMON COMMON ：处理不同程序单位之间的数据共享。通：处理不同程序单位之间的数据共享。通常常用于在不同程序单位之间进行数据的批量传递，它用于在不同程序单位之间进行数据的批量传递，它比采用参数传递的方式效率要高。比采用参数传递的方式效率要高。 EQUIVALENCE EQUIVALENCE ： * *）处理同一个程序单元中的多个对象共享一个存

9、）处理同一个程序单元中的多个对象共享一个存 储空间，以节省内存。储空间，以节省内存。 因此，主程序和过程之间；过程相互之间不同因此，主程序和过程之间；过程相互之间不同 变量不能用变量不能用EQUIVALENCEEQUIVALENCE语句来指定共用存储语句来指定共用存储 单元。单元。 * *）允许用两个或更多的变量名代表同一个量。）允许用两个或更多的变量名代表同一个量。 COMMONCOMMON、EQUVILENCEEQUVILENCE： 这两个语句功能过于强大，这两个语句功能过于强大，滥用会导致对程序的理解和维护变得非常困难。滥用会导致对程序的理解和维护变得非常困难。FORTRANFORTRA

10、N语言存储空间的模式描述：语言存储空间的模式描述：1).1).存储单位：存储单个存储单位：存储单个FORTRANFORTRAN数据值的内存空间数据值的内存空间; ; integer,real,boolean integer,real,boolean：占一个机器字：占一个机器字; ; Complex( Complex(复数复数),double(),double(双精度实型双精度实型) )： 占两个相继的机器字占两个相继的机器字; ;例：例：INTEGER I, J, K(3) COMPLEX X REAL A IJK(1) K(2) K(3)AX数据区数据区2).2).存储序列：存储序列： 任意

11、多个连续的数据单位就构成了一个存储序列；任意多个连续的数据单位就构成了一个存储序列； 一个数组对象构成一个存储序列；一个数组对象构成一个存储序列； 一个公用块构成一个存储序列；一个公用块构成一个存储序列； 等价语句中的等价列表的所有对象构成一等价语句中的等价列表的所有对象构成一 个存储序列；个存储序列；3).3).两个数据对象如果共享了同一个存储序列，那么它两个数据对象如果共享了同一个存储序列，那么它 们就称为具有存储关联的关系。如果它们只是共享们就称为具有存储关联的关系。如果它们只是共享 了同一个存储序列的部分存储单位，那么它们称为了同一个存储序列的部分存储单位，那么它们称为 具有部分存储关

12、联的关系。具有部分存储关联的关系。公共区：一块有名字的、被共享的存储空间。公共区：一块有名字的、被共享的存储空间。 无名公共区：一个；无名公共区：一个； 有名公共区：多个；有名公共区：多个；公共语句：公共语句： COMMON /COMMON /公共块名公共块名1/ 1/ 变量名表变量名表1 , 1 , / /公共块名公共块名2/2/变量名表变量名表2. 2. 其中：其中： * *) )变量名不得是哑元、可分配数组、自动对象等。变量名不得是哑元、可分配数组、自动对象等。 * *) )不同程序单元中不同程序单元中, ,同一公用区中的变量名可以不同。同一公用区中的变量名可以不同。 按位置一一对应共享

13、同一存储单元中的数值。按位置一一对应共享同一存储单元中的数值。 * *) COMMON) 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无名区无名区XYDEF(1) F(2) F(3) F(4)F(5)I Q(1) Q(2) Q(3) Q(4) Q(5)B1区区ABCF(1) F(2) F(3)

14、 F(4)F(5)X(1) X(2) X(3) X(4)B2区区P(1) P(2) P(3)YZ无名区无名区B1区区 B2区区主主9 93 30 0子子1 16 65 53 3子子2 20 04 44 4最终最终长度长度9 95 54 4F F、Q Q部分部分存储关联存储关联X X、I I存存储关联储关联COMMON /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 COMMO

15、N /COM/K(5),L(4) DATA K/8,7,10,4,13/ END 答案：答案： -1 3 -6 9 -1 3 -6 9 COMCOM区区主程序主程序 FIBFIBDATADATAM(1)M(1)J(1)J(1)K(1)K(1)8 8M(2)M(2)J(2)J(2)K(2)K(2)7 7M(3)M(3)J(3)J(3)K(3)K(3)1010M(4)M(4)J(4)J(4)K(4)K(4)4 4M(5)M(5)J(5)J(5)K(5)K(5)1313N(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)K

16、(3)K(3) -6-6 L(3)L(3)N(4)N(4)K(4)K(4)9 9L(4)L(4)等价语句：等价语句：EQUIVALENCE (EQUIVALENCE (变量名表变量名表1),(1),(变量名表变量名表2), 2), 其中：其中： 1 1等价语句是说明语句，应出现在执行语句之前；等价语句是说明语句，应出现在执行语句之前； 2 2每一个每一个 ( (变量名表变量名表) )，称为一个等价片；，称为一个等价片； 3 3等价片中的名字称为等价元。等价元可以是简单等价片中的名字称为等价元。等价元可以是简单 变量或下标为常数的下标变量。变量或下标为常数的下标变量。例：例：INTEGER I,

17、 J, K(3)INTEGER I, J, K(3) COMPLEX X COMPLEX X REAL A(3,3) REAL A(3,3) EQUIVALENCE (X EQUIVALENCE (X，A(2,3) ,(I,J,A(1,2),K(2)A(2,3) ,(I,J,A(1,2),K(2)等价片等价片4 4等价片中的每一个等价元都被分配到同一个存储单等价片中的每一个等价元都被分配到同一个存储单 元，只要某一个等价元赋予某值，其它的等价元元，只要某一个等价元赋予某值，其它的等价元 也就同时具有相同的值。也就同时具有相同的值。 如有赋值：如有赋值：I=2 I=2 那么那么 J,A(1,2)

18、J,A(1,2)值也为值也为2 2。 （留意：这种效果不是数学上的等值，而是由于（留意：这种效果不是数学上的等值，而是由于 共享一个存储单元而得到的方便。共享一个存储单元而得到的方便。) ) 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)5).5).不同等价片中若有相同名字不同等价片中若有相同名字( (包括数组名包括数组名)

19、)，那么，那么 称为等价相关，应将其合并，让更多等价元共称为等价相关，应将其合并，让更多等价元共 享存储单元。享存储单元。( (如如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) )例：例：INTEGER I,J,K(3)INTEGER I,J,K(3) COMPLEX X COMPLEX X REAL A(3

20、,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)XA(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)IJK(1)K(2)K(3)7).7).占用单元数不同的名字等价时，占用单元少的占用单元数不同的名字等价时，占用单元少的 名字和占用单元多的名字的前半部分占用同一名字和占用单元多的名字的前半部分占用同一 单元；单元；(X,A) (X,A) 存储区存储区公共语句与等价语句同时出现：公共语句与等价语句

21、同时出现： . .若一个名字与公共区中元素等价，则该名字分若一个名字与公共区中元素等价，则该名字分 配到公共区；配到公共区； . .等价语句不能改变公共语句确定好的次序和位等价语句不能改变公共语句确定好的次序和位 置，但可以用置，但可以用EQUIVALENCEEQUIVALENCE语句来扩大公共区；语句来扩大公共区；A(1)A(1) A(2)A(2) A(3)A(3) A(4)A(4)C CB(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,CEQUIVALENC

22、E(A(3),B(1)EQUIVALENCE(A(3),B(1)公共语句与等价语句同时出现：公共语句与等价语句同时出现： . .等价语句不能改变公共语句确定好的次序和位等价语句不能改变公共语句确定好的次序和位 置，等价元素位置不得小于公共区起始位置置，等价元素位置不得小于公共区起始位置 （否则称为（否则称为“冒头冒头” ” ）A(1)A(1) A(2)A(2) A(3)A(3) A(4)A(4)C CB(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,CEQUIV

23、ALENCE (A(1),B(2)EQUIVALENCE (A(1),B(2)B B是由等价语句带进来的，但是由等价语句带进来的，但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 ENDSUBROUTINE S(Y1,Y2) COMMON /A1/A,B,C/Q1 A=A+3.

24、0 B=B+4.0 C=C+5.0 Y1=A+B Y2=C-A Q1=Q1+2.0 ENDBLOCK 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.02.0 3.0 4.0 5.0 6.09.0 2.0 4.0输出：输出：4.0 5.0 6.0 9.0 2.0 4.0 4.0 3.0A1区区无名区无名区局部区局部区例：例：SUBROUTINE SS(I)SUBROUTINE SS(I)； INTEGER K, T, Q, S INTEGER K, T

25、, 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) EQUIVALENCE (Z,C(1),(C(3),S),(Q,B(2),(T,B(4)无无名名公公共共区区0 0Y Y1 1Z ZC(1)C(1)2 2D(1)D(1)C(2)C(2)3 3S SC(3)C(3)4 4D(2)D(2)C(4)C(4)局局部部数数据据区区0 0I I1 1K K

26、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等价片分配后等价片分配后8.3.3 公共语句的处理公共语句的处理1).1).新增公共块表新增公共块表(COMLIST)(COMLIST)，主要栏目项如下：，主要栏目项如下：2).2).符号表中增加一个栏目项符号表中增加一个栏目项CMPCMP， 将同一公共区中的元素按出现将同一公共区中的元素按出现 顺序拉成一条链顺序拉成一条链( (指向同一条公指向同一条公 共链的下一个元素共链的下一个元素) )； COMLISTCOMLISTNAMENAMELENGTHL

27、ENGTHFTFTLTLT公公共块共块名名长度长度链首在符号表链首在符号表中的入口地址中的入口地址链尾在符号表链尾在符号表中的入口地址中的入口地址 符号表符号表NameName CMPCMPCOMMON X, YCOMMON X, YCOMMON /B1/A, B, C / / D, E, F(100)COMMON /B1/A, B, C / / D, E, F(100) 符号表符号表NameNameDADACMPCMP1 1X X2 22 2Y Y6 63 3A AB1B14 44 4B BB1B15 55 5C CB1B10 06 6D D7 77 7E E8 88 8F F0 0 COM

28、LIST COMLISTNameName LengthLengthFTFTLTLT1 18 8B1B13 35 5无名公共区：无名公共区： XYDEFXYDEFB1B1区：区： ABCABCLengthLength栏：地址分配时确定栏：地址分配时确定8.3.4 等价语句的处理等价语句的处理1). 主要工作：主要工作： 找出存在等价关系的等价元，将它们构成等价环；找出存在等价关系的等价元，将它们构成等价环； 指出各等价元的首地址关系，以便进行内存分配。指出各等价元的首地址关系，以便进行内存分配。 EQUIVALENCE (X,Y), (I,J,K(2) EQUIVALENCE (X,Y), (I

29、,J,K(2)X XY YP PI IJ JP PK K等价元的首地址关系等价元的首地址关系 X X首地址首地址=Y=Y首地址首地址, , I I首地址首地址=J=J首地址首地址=K=K的首地址的首地址+1+12).2).实现方式：在符号表中增设两栏：实现方式：在符号表中增设两栏：EQEQ和和OFFSETOFFSET。 EQEQ：等价环形链，指向下一个等价元的入口；：等价环形链，指向下一个等价元的入口； 若为若为nullnull，则说明该名字不是等价元；，则说明该名字不是等价元； （若等价环中只有一个等价元，则指向自身）（若等价环中只有一个等价元，则指向自身） OFFSETOFFSET：相对位

30、移量，用来指出各等价元存储：相对位移量，用来指出各等价元存储 首地址之间的地址相对关系。首地址之间的地址相对关系。INTEGER I,J,K(3)INTEGER I,J,K(3)REAL X,YREAL X,YEQUIVALENCE (X,Y),(I,J,K(2)EQUIVALENCE (X,Y),(I,J,K(2)NAMENAME OFFSETOFFSETEQEQ1 1I I0 03 32 2J J0 01 13 3K K-1-12 24 4X X0 05 55 5Y Y0 04 4X XY YP PI IJ JP PK K形式化形式化的归并的归并算法算法P251P251公用区地址分配算法公

31、用区地址分配算法 P252P252局部区等价环分配算法局部区等价环分配算法 P253 P253局部区地址分配算法局部区地址分配算法无无名名公公共共区区0 0Y Y1 1Z ZC(1)C(1)2 2D(1)D(1)C(2)C(2)3 3C(3)C(3)4 4D(2)D(2)C(4)C(4)5 5C(5)C(5)6 6C(6)C(6)符符号号表表Name Size DA Addr1 1I1 10 00 02 2K1 10 01 13 3T1 10 05 54 4Q1 10 03 35 5B5 50 02 26 6C6 61281281 17 7Y1 11281280 08 8Z1 11281281

32、 19 9D4 41281282 21010M1 10 07 7Subroutine 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) COMLISTName Length FTLT无名无名779局局部部数数据据区区0 0I I1 1K K2 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 7 M符符号号表表NameSize DA Ad

33、dr1 1I1 10 00 02 2K1 10 01 13 3T1 10 05 54 4Q1 10 03 35 5B5 50 02 26 6C6 61281281 17 7Y1 11281280 08 8Z1 11281281 19 9D4 41281282 21010M1 10 07 7Subroutine SS(I)Integer K, T, QReal B(5), C(6)Common / Y, Z, DComplex D(2) Real MEquiv (Z, C(1) , (Q,B(2), (T,B(4) 8.3.6 临时变量的地址分配临时变量的地址分配 1 1、临时变量：编译程序引入

34、，存放中间结果。、临时变量：编译程序引入，存放中间结果。 2 2、临时变量的作用域：、临时变量的作用域： 定值定值( (赋值赋值)=)=最后一次被引用。最后一次被引用。 3 3、地址分配原则：、地址分配原则： 若两个临时变量的作用域不相交，则它们可若两个临时变量的作用域不相交，则它们可 分配在同一单元中。分配在同一单元中。 临时变量名均分配在局部数据区。临时变量名均分配在局部数据区。单元单元已分配给已分配给标记的作用域标记的作用域I1T1,1 , T1,2 , , T1,m1S1,1 , S1,2 , , S1,m1I2T2,1 , T2,2 , , T2,m2 ,TS2,1 , S2,2 , , S2,m2 ,SIkTk,1 , Tk,2 , , Tk,mkSk,1 , Sk,2 , , Sk,mkIk+1TS1) 1) 对临时变量对临时变量T T，求出，求出T T的作用域的作