《程序运行时的存储组织及管理课件》由会员分享，可在线阅读，更多相关《程序运行时的存储组织及管理课件（26页珍藏版）》请在金锄头文库上搜索。
1、1S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理编译程序在编译阶段要为源程序中出现的变量、常量等组编译程序在编译阶段要为源程序中出现的变量、常量等组织好在织好在运行阶段的存储空间运行阶段的存储空间将这种组织形式通过生成的将这种组织形式通过生成的目标代码目标代码体现出来体现出来为运行阶段实现存储为运行阶段实现存储奠定基础奠定基础2第八章第八章 程序运行时的存储组程序运行时的存储组织及管理织及管理 教学目标教学目标1.1.要求明确静态存储分配和动态存
2、储分配的要求明确静态存储分配和动态存储分配的含义含义2.2.了解栈式动态存储分配和活动记录的含义了解栈式动态存储分配和活动记录的含义及组成及组成3.3.了解堆式动态存储分配的分配方式和管理了解堆式动态存储分配的分配方式和管理技术技术38.1 8.1 程序运行时的存储组织程序运行时的存储组织8.2 8.2 静态存储分配静态存储分配8.3 8.3 栈式动态存储分配栈式动态存储分配8.4 8.4 堆式动态存储分配堆式动态存储分配教学内容教学内容48.1 程序运行时的存储组织程序运行时的存储组织 运行时存储空间的划分运行时存储空间的划分代码空间代码空间数据空间数据空间目标代码区目标代码区静态数据区静态
3、数据区运行栈区运行栈区运行堆区运行堆区5存储分配策略存储分配策略p目标代码的长度在编译时就可确定目标代码的长度在编译时就可确定,可放在可放在静态区静态区静态区静态区内内;p对于在编译时已知大小的数据对象对于在编译时已知大小的数据对象(如如常量常量常量常量, , , ,全局变量全局变量全局变量全局变量, , , ,静态变量静态变量静态变量静态变量等等等等),也可放在也可放在静态区静态区静态区静态区内内;p为提高运行效率为提高运行效率,应尽可能多地分配应尽可能多地分配静态数据空间静态数据空间静态数据空间静态数据空间。FORTRAN,BASICFORTRAN,BASIC的分配一般可全部放在的分配一般
4、可全部放在静态区静态区静态区静态区内内.p像像PASCAL,CPASCAL,C这类语言的实现这类语言的实现,由于子程序允许由于子程序允许递归递归递归递归地调用地调用,因此应用一因此应用一数据栈数据栈数据栈数据栈来动态地管理内存分配来动态地管理内存分配.p另外另外PASCALPASCAL和和C C还允许还允许动态地申请动态地申请动态地申请动态地申请的内存的内存,这种数据这种数据的空间可由的空间可由堆式分配堆式分配堆式分配堆式分配实现实现.6活动记录（活动记录（active record）pp执行过程时所需进行的信执行过程时所需进行的信执行过程时所需进行的信执行过程时所需进行的信息管理，是通过息管
5、理，是通过息管理，是通过息管理，是通过活动记录活动记录活动记录活动记录实现的，实现的，实现的，实现的，活动记录活动记录活动记录活动记录连续存连续存连续存连续存储在块中，其内容见右图。储在块中，其内容见右图。储在块中，其内容见右图。储在块中，其内容见右图。pp以过程为单位的动态存储以过程为单位的动态存储以过程为单位的动态存储以过程为单位的动态存储分配方案：分配方案：分配方案：分配方案：n n当一过程被调用时，就当一过程被调用时，就当一过程被调用时，就当一过程被调用时，就把其把其把其把其活动记录活动记录活动记录活动记录压入运行压入运行压入运行压入运行时存储栈顶，返回时弹时存储栈顶，返回时弹时存储栈
6、顶，返回时弹时存储栈顶，返回时弹出之。出之。出之。出之。 临时变量临时变量内情向量内情向量形式单元形式单元动态链动态链返回地址返回地址静态链静态链局部变量局部变量连接连接数据区数据区局部局部数据区数据区SPTOP78.2 静态存储分配静态存储分配 p若在编译阶段就能确定源程序中各个数据实若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的体的存储空间大小，则可以采用较简单的静静态存储管理。态存储管理。p采用静态存储分配的语言必须满足下列条件：采用静态存储分配的语言必须满足下列条件：1 1） 不允许过程有递归调用。不允许过程有递归调用。2 2） 不允许有可变大小的数据项，如
7、可变数组或可变不允许有可变大小的数据项，如可变数组或可变字符串。字符串。3 3） 不允许用户动态建立数据实体。不允许用户动态建立数据实体。满足上述条件的语言有满足上述条件的语言有FORTRANFORTRAN、BASICBASIC等。等。88.2 静态存储分配静态存储分配右下图是一个右下图是一个右下图是一个右下图是一个FORTRANFORTRAN程序模块在采用静态存储程序模块在采用静态存储程序模块在采用静态存储程序模块在采用静态存储分配策略时的典型数据区格局。分配策略时的典型数据区格局。分配策略时的典型数据区格局。分配策略时的典型数据区格局。隐式参数隐式参数隐式参数隐式参数（返回地址、寄（返回地
8、址、寄（返回地址、寄（返回地址、寄存器内容等）存器内容等）存器内容等）存器内容等）形式参数形式参数形式参数形式参数简单变量简单变量简单变量简单变量数组数组数组数组临时变量临时变量临时变量临时变量1) 1) 隐隐式式参参数数主主要要用用于于和和主主调调模模块块的的通通讯讯，在在一一般般情情况况下下这这个个参参数数可可以以是是主主调调过过程程的的返返回回地地址址，或或在在不不能能利利用用寄寄存存器器返返回回函函数数值值时时传传回回函函数数返返回回值值。这这些些信信息息不不会会在在程程序序中中明明显显地出现，所以称为隐式参数。地出现，所以称为隐式参数。2) 2) 形形式式参参数数部部分分存存放放相相
9、应应实实在在参参数数的的地地址址或或值。值。3) 3) 程程序序变变量量部部分分将将作作为为简简单单变变量量、数数组组、记记录录以以及及编编译译程程序序所所产产生生的的临临时时变变量量的的存存储储空空间。间。9静态存储分配静态存储分配动态存储分配动态存储分配静态存储分配静态存储分配在在编译阶段编译阶段由由编译程序编译程序实现对存储空间的管理，为源实现对存储空间的管理，为源程序中的变量分配存储单元。程序中的变量分配存储单元。在编译时能够确定变量在运行时的数据空间大小在编译时能够确定变量在运行时的数据空间大小运行时不改变运行时不改变动态存储分配动态存储分配在目标程序在目标程序运行阶段运行阶段由由目
10、标程序目标程序实现对存储空间的组实现对存储空间的组织与管理，为源程序中的变量分配存储单元。织与管理，为源程序中的变量分配存储单元。在目标程序运行时进行分配在目标程序运行时进行分配编译时为运行阶段设计好存储组织形式，即为每个编译时为运行阶段设计好存储组织形式，即为每个数据项安排好它在数据区中的相对位置数据项安排好它在数据区中的相对位置108.3 栈式动态存储分配栈式动态存储分配 pp栈式分配栈式分配栈式分配栈式分配适用于允许递归调用的程序设计语言适用于允许递归调用的程序设计语言适用于允许递归调用的程序设计语言适用于允许递归调用的程序设计语言; ; ; ;pp引入一运行栈引入一运行栈引入一运行栈引
11、入一运行栈, , , ,每调用一次过程每调用一次过程每调用一次过程每调用一次过程, , , ,就把该过程的相就把该过程的相就把该过程的相就把该过程的相应调用记录压入栈应调用记录压入栈应调用记录压入栈应调用记录压入栈, , , ,过程执行完毕后再将其弹出栈过程执行完毕后再将其弹出栈过程执行完毕后再将其弹出栈过程执行完毕后再将其弹出栈; ; ; ;进入时：进入时：进入时：进入时：在栈顶为其分配一个数据区在栈顶为其分配一个数据区在栈顶为其分配一个数据区在栈顶为其分配一个数据区退出时退出时退出时退出时：撤消过程数据区：撤消过程数据区：撤消过程数据区：撤消过程数据区动作：动作：动作：动作：1)1)申请申
12、请申请申请2)2)释放释放释放释放3)3)嵌套调用嵌套调用嵌套调用嵌套调用11下下面面我我们们通通过过一一段段C C程程序序的的运运行行来来说说明明运运行行栈栈的的变变化化情情况况。设设有有C C程序如下：程序如下：realx;块块1intm1(intind)块块2intx;x=m2(ind+1);intm2(intj)块块3intf10;块块4booltest1;main()块块5intx;x=2;printf(%dn,m1(x/5);(a)(b)(c)(d)(e)121 1、 参数区参数区 参数区保存的内容包括：1) 隐式参数隐式参数：隐式参数常包含下列几项： 返回地址：主调程序中调用语句
13、的下一条可执行语句的地址。 指向前一个活动记录起始位置的指针：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确保控制返回主调过程时，能使运行环境恢复到调用前的格局。 函数返回值：有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法 。2) 显式参数显式参数：显式参数区是形式参数的通讯区。 形式参数的传递有传值、传地址、传名等方法。有些语言如PASCAL语言即可传值、也可传地址。C语言采用的是传值的方式，这种参数传递方法，实在参数的值将赋给形式参数。当程序运行进入一个程序块时，就要在运行栈中为当程序运行进入一个程序块时，就要在运行栈中为此程序块添加一个活动记录。活动记录中除了
14、存储此程序块添加一个活动记录。活动记录中除了存储局部变量外，还包括一个参数区和一个局部变量外，还包括一个参数区和一个displaydisplay区。区。图图8.38.3表示了一个典型的活动记录的概貌。表示了一个典型的活动记录的概貌。132 2、DisplayDisplay（嵌套（嵌套层次次显示表）区示表）区displaydisplay区用于保存区用于保存对当前正在当前正在执行的模行的模块来来说是全局的程序是全局的程序变量区的信息，它由一量区的信息，它由一系列地址指系列地址指针所所组成，每一个指成，每一个指针指向一指向一个程序个程序块的活的活动记录的开始位置，而的开始位置，而这个个程序程序块对于
15、当前正在于当前正在执行的程序行的程序块来来说是是全局的。全局的。P P的活动纪录的地址的活动纪录的地址的活动纪录的地址的活动纪录的地址QQ的最新活动纪录的地址的最新活动纪录的地址的最新活动纪录的地址的最新活动纪录的地址RR的现行活动纪录地址的现行活动纪录地址的现行活动纪录地址的现行活动纪录地址210例如，令过程例如，令过程R R的外层为的外层为Q Q，Q Q的外层为的外层为P P，则过程，则过程R R运行运行时时displaydisplay表的内容应为：表的内容应为：14图图8.48.4给出了图给出了图8.2(e)8.2(e)的运行的运行栈中各活动记录的内容。栈中各活动记录的内容。块块4 4的
16、活动记录如下：的活动记录如下：DISPLAYDISPLAY区：区：指针指针d1d1和和d2d2，分，分别指向全局变量区的地址别指向全局变量区的地址Abp0Abp0和和Abp3Abp3。隐式参数区：隐式参数区：有两个参数，第有两个参数，第一个是返回地址，因块一个是返回地址，因块4 4不是不是一个独立的函数，是一嵌套的一个独立的函数，是一嵌套的块程序，所以，没有返回地址，块程序，所以，没有返回地址，同样也没有形参，第同样也没有形参，第2 2个参数个参数Abp3Abp3表示在运行栈中，前一个表示在运行栈中，前一个活动记录是开始地址为活动记录是开始地址为Abp3Abp3的的m2m2活动记录。活动记录。
17、局部数据区：局部数据区：f f和和testtest。 abp2abp2osos无前记录无前记录无前记录无前记录 x xd1d1abp0abp0xxd1d1return2return2abp1abp1indindx xd1d1return3return3j jd1d1d2d2abp3abp3f ftesttest块块4活动记录活动记录abp4abp4m2活动记录活动记录abp3m1活动记录活动记录abp2main活动记录活动记录abp1abp015递归过程的处理递归过程的处理 下面程序的运行结果是什么？如果把第下面程序的运行结果是什么？如果把第6行的行的(i+1)*fact()改成改成fact(
18、)*(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)*fact()(i+1)*fact() ); ); /第第6 6行行 main()main() printf(factor of 5!=%dn,fact(); printf(factor of
19、 5!=%dn,fact(); 168.4 堆式动态存储分配堆式动态存储分配 p当程序语言允许在运行时为变量当程序语言允许在运行时为变量动态申请和释放动态申请和释放动态申请和释放动态申请和释放存储空间存储空间存储空间存储空间，采用，采用堆式分配堆式分配堆式分配堆式分配是最有效的解决方案。是最有效的解决方案。pp堆式分配的基本思想是堆式分配的基本思想是堆式分配的基本思想是堆式分配的基本思想是，为正运行的程序划出适，为正运行的程序划出适当大的空间当大的空间( (称为称为堆堆堆堆HeapHeapHeapHeap) )，每当需要时可从堆的，每当需要时可从堆的空闲区空闲区空闲区空闲区中分得一块，用完之后
20、再退还给堆。中分得一块，用完之后再退还给堆。p如如C C语言中的语言中的mallocmalloc和和freefree函数。函数。p如如C+C+语言中的语言中的newnew和和deletedelete函数。函数。178.4.1 堆分配方式堆分配方式 当当当当运运运运行行行行程程程程序序序序请请请请求求求求一一一一块块块块体体体体积积积积为为为为N N N N的的的的空空空空间间间间时时时时，应应应应该该该该如如如如何何何何分分分分配呢？常采用的方法如下：配呢？常采用的方法如下：配呢？常采用的方法如下：配呢？常采用的方法如下：1 1 1 1） 先先先先遇遇遇遇到到到到哪哪哪哪个个个个大大大大于于于
21、于N N N N的的的的空空空空闲闲闲闲块块块块就就就就从从从从中中中中取取取取出出出出N N N N个个个个单单单单元元元元进行分配。进行分配。进行分配。进行分配。2 2 2 2） 如如如如果果果果在在在在堆堆堆堆中中中中找找找找不不不不到到到到大大大大于于于于N N N N的的的的空空空空闲闲闲闲块块块块，但但但但所所所所有有有有空空空空闲闲闲闲块块块块的的的的总总总总和和和和比比比比N N N N大大大大，就就就就需需需需要要要要将将将将空空空空闲闲闲闲块块块块连连连连接接接接在在在在一一一一起起起起，从而形成大于从而形成大于从而形成大于从而形成大于N N N N的空闲块。的空闲块。的空
22、闲块。的空闲块。如如如如果果果果所所所所有有有有空空空空闲闲闲闲块块块块的的的的总总总总和和和和都都都都小小小小于于于于N N N N，则则则则需需需需要要要要采采采采用用用用更更更更复复复复杂杂杂杂的的的的办办办办法法法法。如如如如废废废废品品品品回回回回收收收收技技技技术术术术，将将将将那那那那些些些些运运运运行行行行程程程程序序序序已已已已经经经经不不不不使使使使用用用用但但但但还还还还没没没没有有有有释释释释放放放放的的的的块块块块、或或或或运运运运行行行行程程程程序序序序目目目目前前前前很很很很少少少少使用的块回收，再重新分配。使用的块回收，再重新分配。使用的块回收，再重新分配。使用
23、的块回收，再重新分配。 188.4.2 堆式存储管理技术堆式存储管理技术 (a)程序运行初期：程序运行初期：(b)运行一段时间后：运行一段时间后：当有新请求分配内存时，有两种当有新请求分配内存时，有两种策略分配策略分配空间：空间：1)系系统统继继续续从从高高地地址址的的空空闲闲块块中中进进行行分分配配，而而不不查查看看已已分分配配给给用用户户的的内内存存区区是是否否已已空空闲闲，直直到到分分配配无无法法进进行行(即即剩剩余余的的空空闲闲块块不不能能满满足足分分配配的的请请求求)时时，系系统统才才去去回回收收所所有有用用户户不不再再使使用用的的空空闲块。闲块。2)用用户户使使用用一一旦旦结结束束
24、，便便将将所所占占内内存存区区释释放放成成空空闲闲块块。同同时时，每每当当新新的的用用户户请请求求分分配配内内存存时时，系系统统需需要要巡巡视视整整个个内内存存中中所所有有空闲块，并从中找出一个空闲块，并从中找出一个“合适合适”的空闲块加以分配。的空闲块加以分配。190 10000 20000 30000(a)内存状态 (b)可利用空间目录 10000HEAD 10000 20000 30000(c)可利用空间链表图8.7堆式存储管理的可利用空间表 201、定长块的管理、定长块的管理pp将总的可被利用的堆存储区划分成大小适当的一将总的可被利用的堆存储区划分成大小适当的一将总的可被利用的堆存储区
25、划分成大小适当的一将总的可被利用的堆存储区划分成大小适当的一系列块。系列块。系列块。系列块。pp这些块通过每块中的这些块通过每块中的这些块通过每块中的这些块通过每块中的LINKLINK域连接起来形成单向域连接起来形成单向域连接起来形成单向域连接起来形成单向线性链表，即可利用空间表，如下图所示。线性链表，即可利用空间表，如下图所示。线性链表，即可利用空间表，如下图所示。线性链表，即可利用空间表，如下图所示。200000300000#010000HEAD100002000030000212、变长块的管理、变长块的管理pp变长块的管理是常用的堆式存储管理方法变长块的管理是常用的堆式存储管理方法变长块
26、的管理是常用的堆式存储管理方法变长块的管理是常用的堆式存储管理方法。pp系统在运行期间分配给用户的内存块的大小不固系统在运行期间分配给用户的内存块的大小不固系统在运行期间分配给用户的内存块的大小不固系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。因此，定，可以随请求而变。因此，定，可以随请求而变。因此，定，可以随请求而变。因此，“ “可利用空间表可利用空间表可利用空间表可利用空间表” ”中中中中的结点，即空闲块的大小也是随意的。的结点，即空闲块的大小也是随意的。的结点，即空闲块的大小也是随意的。的结点，即空闲块的大小也是随意的。pp结点的数据结构如下结点的数据结构如下结点的数据结
27、构如下结点的数据结构如下 TAGTAG：标记，：标记，：标记，：标记，0 0表示空闲，表示空闲，表示空闲，表示空闲，1 1表示占用。表示占用。表示占用。表示占用。SIZESIZE：记录结点大小，指示空闲块的存储量。：记录结点大小，指示空闲块的存储量。：记录结点大小，指示空闲块的存储量。：记录结点大小，指示空闲块的存储量。LINKLINK：指向下一个结点。：指向下一个结点。：指向下一个结点。：指向下一个结点。 SPACESPACE：地址连续的内存空间。：地址连续的内存空间。：地址连续的内存空间。：地址连续的内存空间。 22变长块内存的分配变长块内存的分配pp假设用户请求一个大小为假设用户请求一个
28、大小为假设用户请求一个大小为假设用户请求一个大小为n n的存储块，而的存储块，而的存储块，而的存储块，而“ “可利用可利用可利用可利用空间表空间表空间表空间表” ”中仅有一块大小为中仅有一块大小为中仅有一块大小为中仅有一块大小为mnmn的空闲块，则分的空闲块，则分的空闲块，则分的空闲块，则分配时只需将大小为配时只需将大小为配时只需将大小为配时只需将大小为n n的部分分配给申请的用户，的部分分配给申请的用户，的部分分配给申请的用户，的部分分配给申请的用户，同时将剩余的同时将剩余的同时将剩余的同时将剩余的m-nm-n部分作为一个结点留在链表中部分作为一个结点留在链表中部分作为一个结点留在链表中部分
29、作为一个结点留在链表中即可。即可。即可。即可。pp若可利用空间表中有若干个大于若可利用空间表中有若干个大于若可利用空间表中有若干个大于若可利用空间表中有若干个大于n n的空闲块时，的空闲块时，的空闲块时，的空闲块时，可采用下列方法分配：可采用下列方法分配：可采用下列方法分配：可采用下列方法分配： 11、首次满足法、首次满足法、首次满足法、首次满足法22、最优满足法、最优满足法、最优满足法、最优满足法33、最差满足法、最差满足法、最差满足法、最差满足法238.4.2 堆式存储管理技术堆式存储管理技术pp三种分配方式各有所长三种分配方式各有所长三种分配方式各有所长三种分配方式各有所长p最优满足法：
30、最优满足法：产生内存碎片，保留了大内存块，产生内存碎片，保留了大内存块，以备响应后面可能发生的对大存储空间的请求。以备响应后面可能发生的对大存储空间的请求。p最差满足法：最差满足法：使链表中的结点空间大小趋于均匀，使链表中的结点空间大小趋于均匀，因此，它适用于请求分配的内存大小范围较窄的因此，它适用于请求分配的内存大小范围较窄的系统。系统。p首次满足法：首次满足法：分配随机，适用于事先对系统运行分配随机，适用于事先对系统运行期间可能出现的内存分配和释放情况不能准确把期间可能出现的内存分配和释放情况不能准确把握的场合。握的场合。248.4.2 堆式存储管理技术堆式存储管理技术pp从时间上对三种分
31、配法进行比较从时间上对三种分配法进行比较从时间上对三种分配法进行比较从时间上对三种分配法进行比较253、释放方法、释放方法pp最简单的释放方法是作为一个新的空闲块插入到最简单的释放方法是作为一个新的空闲块插入到最简单的释放方法是作为一个新的空闲块插入到最简单的释放方法是作为一个新的空闲块插入到无序的无序的无序的无序的“ “可利用空间表可利用空间表可利用空间表可利用空间表” ”中。中。中。中。pp将两个连续的块合并成一个块。需要对将两个连续的块合并成一个块。需要对将两个连续的块合并成一个块。需要对将两个连续的块合并成一个块。需要对“ “可利用可利用可利用可利用空间表空间表空间表空间表” ”按块的
32、地址顺序进行组织，同时为了要按块的地址顺序进行组织，同时为了要按块的地址顺序进行组织，同时为了要按块的地址顺序进行组织，同时为了要确定当前释放块的插入位置，还需要对可利用空确定当前释放块的插入位置，还需要对可利用空确定当前释放块的插入位置，还需要对可利用空确定当前释放块的插入位置，还需要对可利用空间表进行搜索。间表进行搜索。间表进行搜索。间表进行搜索。pp有的程序设计语言干脆不做释放的工作，直到内有的程序设计语言干脆不做释放的工作，直到内有的程序设计语言干脆不做释放的工作，直到内有的程序设计语言干脆不做释放的工作，直到内存空间用完为止。存空间用完为止。存空间用完为止。存空间用完为止。26小结小结pp静态存储分配和动态存储分配的含义静态存储分配和动态存储分配的含义pp活动记录的含义及组成活动记录的含义及组成pp静态、动态存储分配的策略静态、动态存储分配的策略
