程序运行时的存储组织及管理课件

《程序运行时的存储组织及管理课件》由会员分享，可在线阅读，更多相关《程序运行时的存储组织及管理课件（26页珍藏版）》请在装配图网上搜索。

1、1S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理编译程序在编译阶段要为源程序中出现的变量、常量等组编译程序在编译阶段要为源程序中出现的变量、常量等组织好在织好在运行阶段的存储空间运行阶段的存储空间将这种组织形式通过生成的将这种组织形式通过生成的目标代码目标代码体现出来体现出来为运行阶段实现存储为运行阶段实现存储奠定基础奠定基础2教学目标教学目标 要求明确静态存储分配和动态存储分配的要求明确静态存储分配和动态存储分配的含义含义 了解栈式动态存储分配

2、和活动记录的含义了解栈式动态存储分配和活动记录的含义及组成及组成 了解堆式动态存储分配的分配方式和管理了解堆式动态存储分配的分配方式和管理技术技术38.1 8.1 程序运行时的存储组织程序运行时的存储组织8.2 8.2 静态存储分配静态存储分配8.3 8.3 栈式动态存储分配栈式动态存储分配8.4 8.4 堆式动态存储分配堆式动态存储分配教学内容教学内容4运行时存储空间的划分运行时存储空间的划分代码空间代码空间数据空间数据空间目标代码区目标代码区静态数据区静态数据区运行栈区运行栈区 运行堆区运行堆区5p目标代码的长度在编译时就可确定目标代码的长度在编译时就可确定,可放在可放在内内;p对于在编译

3、时已知大小的数据对象对于在编译时已知大小的数据对象(如如等等等等),也可放在也可放在内内;p为提高运行效率为提高运行效率,应尽可能多地分配应尽可能多地分配。的分配一般可全部放在的分配一般可全部放在内内.p像像这类语言的实现这类语言的实现,由于子程序允许由于子程序允许地调用地调用,因此应用一因此应用一来动态地管理内存分配来动态地管理内存分配.p另外另外和和 还允许还允许的内存的内存,这种数这种数据的空间可由据的空间可由实现实现.6 临时变量临时变量 内情向量内情向量 形式单元形式单元 动态链动态链 返回地址返回地址 静态链静态链 局部变量局部变量 连接连接数据区数据区 局部局部数据区数据区 SP

4、 TOP7p若在编译阶段就能确定源程序中各个数据实若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的体的存储空间大小，则可以采用较简单的p采用静态存储分配的语言必须满足下列条件：采用静态存储分配的语言必须满足下列条件：1 1）不允许过程有递归调用。不允许过程有递归调用。2 2）不允许有可变大小的数据项，如可变数组或可不允许有可变大小的数据项，如可变数组或可变字符串。变字符串。3 3）不允许用户动态建立数据实体。不允许用户动态建立数据实体。满足上述条件的语言有满足上述条件的语言有FORTRANFORTRAN、BASICBASIC等。等。81)1)隐式参数隐式参数主要用于和

5、主调模块的通讯，在主要用于和主调模块的通讯，在一般情况下这个参数可以是主调过程的返回一般情况下这个参数可以是主调过程的返回地址，或在不能利用寄存器返回函数值时传地址，或在不能利用寄存器返回函数值时传回函数返回值。这些信息不会在程序中明显回函数返回值。这些信息不会在程序中明显地出现，所以称为隐式参数。地出现，所以称为隐式参数。2)2)形式参数形式参数部分存放相应实在参数的地址或部分存放相应实在参数的地址或值。值。3)3)程序变量部分程序变量部分将作为简单变量、数组、记将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空录以及编译程序所产生的临时变量的存储空间。间。9在在编译阶段编译阶段

6、由由编译程序编译程序实现对存储空间的管理，为源实现对存储空间的管理，为源程序中的变量分配存储单元。程序中的变量分配存储单元。在编译时能够确定变量在运行时的数据空间大小在编译时能够确定变量在运行时的数据空间大小运行时不改变运行时不改变在目标程序在目标程序运行阶段运行阶段由由目标程序目标程序实现对存储空间的组实现对存储空间的组织与管理，为源程序中的变量分配存储单元。织与管理，为源程序中的变量分配存储单元。在目标程序运行时进行分配在目标程序运行时进行分配 编译时为运行阶段设计好存储组织形式，即为每编译时为运行阶段设计好存储组织形式，即为每个数据项安排好它在数据区中的相对位置个数据项安排好它在数据区中

7、的相对位置1011下面我们通过一段下面我们通过一段C C程序的运行来说明运行栈的变化情况。设有程序的运行来说明运行栈的变化情况。设有C C程序如下：程序如下：real x;块块1int m1(int ind)块块2 int x;x=m2(ind+1);int m2(int j)块块3 int f10;块块4 bool test1;main()块块5 int x;x=2;printf(%dn,m1(x/5);(a)(b)(c)(d)(e)121 1、参数区参数区 参数区保存的内容包括：1)隐式参数隐式参数：隐式参数常包含下列几项：返回地址：主调程序中调用语句的下一条可执行语句的地址。指向前一个活

8、动记录起始位置的指针：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确保控制返回主调过程时，能使运行环境恢复到调用前的格局。函数返回值：有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法。2)显式参数显式参数：显式参数区是形式参数的通讯区。形式参数的传递有传值、传地址、传名等方法。有些语言如PASCAL语言即可传值、也可传地址。C语言采用的是传值的方式，这种参数传递方法，实在参数的值将赋给形式参数。当程序运行进入一个程序块时，就要在运行栈中为当程序运行进入一个程序块时，就要在运行栈中为此程序块添加一个活动记录。活动记录中除了存储此程序块添加一个活动记录。活动记录中除了存储

9、局部变量外，还包括一个参数区和一个局部变量外，还包括一个参数区和一个displaydisplay区。区。图图8.38.3表示了一个典型的活动记录的概貌。表示了一个典型的活动记录的概貌。132 2、DisplayDisplay（嵌套层次显示表）区（嵌套层次显示表）区displaydisplay区用于保存对当前正在执行的模区用于保存对当前正在执行的模块来说是全局的程序变量区的信息，它由块来说是全局的程序变量区的信息，它由一系列地址指针所组成，每一个指针指向一系列地址指针所组成，每一个指针指向一个程序块的活动记录的开始位置，而这一个程序块的活动记录的开始位置，而这个程序块对于当前正在执行的程序块来说

10、个程序块对于当前正在执行的程序块来说是全局的。是全局的。210例如，令过程例如，令过程R R的外层为的外层为Q Q，Q Q的外层为的外层为P P，则过程，则过程R R运行运行时时displaydisplay表的内容应为：表的内容应为：14图图8.48.4给出了图给出了图8.2(e)8.2(e)的运行的运行栈中各活动记录的内容。栈中各活动记录的内容。块块4 4的活动记录如下：的活动记录如下：DISPLAYDISPLAY区：区：指针指针d1d1和和d2d2，分，分别指向全局变量区的地址别指向全局变量区的地址Abp0Abp0和和Abp3Abp3。隐式参数区：隐式参数区：有两个参数，第有两个参数，第一

11、个是返回地址，因块一个是返回地址，因块4 4不是不是一个独立的函数，是一嵌套的一个独立的函数，是一嵌套的块程序，所以，没有返回地址，块程序，所以，没有返回地址，同样也没有形参，第同样也没有形参，第2 2个参数个参数Abp3Abp3表示在运行栈中，前一个表示在运行栈中，前一个活动记录是开始地址为活动记录是开始地址为Abp3Abp3的的m2m2活动记录。活动记录。局部数据区：局部数据区：f f和和testtest。块块4活动记录活动记录abp4abp4 m2活动记录活动记录abp3 m1活动记录活动记录abp2 main活动记录活动记录abp1abp015下面程序的运行结果是什么？如果把第下面程序

12、的运行结果是什么？如果把第6行的行的(i+1)*fact()改成改成fact()*(i+1)的话，则程序的运行结果的话，则程序的运行结果是有什么变化？试分析为什么会有这两种不同的结果。是有什么变化？试分析为什么会有这两种不同的结果。int fact()int fact()staticstatic int i=5;int i=5;if(i=0)return 1;if(i=0)return 1;else else i-;i-;return(return(i+1)(i+1)*fact()fact(););/第第6 6行行 main()main()printf(factor of 5!=%dn,fac

13、t();printf(factor of 5!=%dn,fact();16p当程序语言允许在运行时为变量当程序语言允许在运行时为变量，采用，采用是最有效的解决方案。是最有效的解决方案。，为正运行的程序划出适，为正运行的程序划出适当大的空间当大的空间(称为称为)，每当需要时可从堆的，每当需要时可从堆的中分得一块，用完之后再退还给堆。中分得一块，用完之后再退还给堆。p如如C C语言中的语言中的mallocmalloc和和freefree函数。函数。p如如C+C+语言中的语言中的newnew和和deletedelete函数。函数。1718(a)程序运行初期：程序运行初期：(b)运行一段时间后：运行一

14、段时间后：当有新请求分配内存时，有两种当有新请求分配内存时，有两种策略分配策略分配空间：空间：系统继续从高地址的空闲块中进行分配，而不查看已分配给系统继续从高地址的空闲块中进行分配，而不查看已分配给用户的内存区是否已空闲，直到分配无法进行用户的内存区是否已空闲，直到分配无法进行(即剩余的空闲块即剩余的空闲块不能满足分配的请求不能满足分配的请求)时，系统才去回收所有用户不再使用的空时，系统才去回收所有用户不再使用的空闲块。闲块。1)用户使用一旦结束，便将所占内存区释放成空闲块。同时，用户使用一旦结束，便将所占内存区释放成空闲块。同时，每当新的用户请求分配内存时，系统需要巡视整个内存中所有每当新的

15、用户请求分配内存时，系统需要巡视整个内存中所有空闲块，并从中找出一个空闲块，并从中找出一个“合适合适”的空闲块加以分配。的空闲块加以分配。190 10000 20000 30000(a)内存状态(b)可利用空间目录 10000HEAD 10000 20000 30000(c)可利用空间链表图8.7堆式存储管理的可利用空间表 20200000300000#010000HEAD 10000 20000 30000212223p最优满足法：最优满足法：产生内存碎片，保留了大内存块，产生内存碎片，保留了大内存块，以备响应后面可能发生的对大存储空间的请求。以备响应后面可能发生的对大存储空间的请求。p最差满足法：最差满足法：使链表中的结点空间大小趋于均匀，使链表中的结点空间大小趋于均匀，因此，它适用于请求分配的内存大小范围较窄的因此，它适用于请求分配的内存大小范围较窄的系统。系统。p首次满足法：首次满足法：分配随机，适用于事先对系统运行分配随机，适用于事先对系统运行期间可能出现的内存分配和释放情况不能准确把期间可能出现的内存分配和释放情况不能准确把握的场合。握的场合。242526