运行时的存储组织与分配

1、1 运行时的存储组织与分配编译程序编译程序必须为源程序中所出现的量必须为源程序中所出现的量(常量常量,变量及数组变量及数组等等等等)分配运行时的存储空间分配运行时的存储空间.分配方案选择的是否得当分配方案选择的是否得当将关系到资源的合理使用将关系到资源的合理使用, ,从从而会影响到程序的运行效率而会影响到程序的运行效率. .存储分配的策略有存储分配的策略有与与两类两类.适合于无动态申请内存适合于无动态申请内存,无可变长数组无可变长数组,无递归无递归调用的程序调用的程序.如如等等.分配适用面广是目前最常用的分配方案分配适用面广是目前最常用的分配方案又有又有栈式分配栈式分配与与堆式分配堆式分配两种

2、两种.2:3w 目标代码的长度在编译时就可确定目标代码的长度在编译时就可确定,可放在可放在内内;w 对于在编译时已知大小的数据对象对于在编译时已知大小的数据对象(如如等等等等), 也可放在也可放在内内;w 为提高运行效率为提高运行效率,应尽可能多地分配应尽可能多地分配. 的分配一般可全部放在的分配一般可全部放在内内.w 像像这类语言的实现这类语言的实现,由于子程序允许由于子程序允许地调地调用用,因此应用一因此应用一来动态地管理内存分配来动态地管理内存分配.w 另外另外和和 还允许还允许的内存的内存,这种数据的这种数据的空间可由空间可由实现实现.4 活动记录w 执行过程时所需进行的信息管理，是通

3、过实现的，连续存储在块中，其内容见右图。w 以过程为单位的动态存储分配方案：n当一过程被调用时，就把其压入运行时存储栈顶，返回时弹出之。5 存放目标程序临时变量的值存放目标程序临时变量的值; 存放本次执行中的局部数据、简单变量、存放本次执行中的局部数据、简单变量、数组内情向量等数组内情向量等; 保存在调用该过程前有关机器状态的信保存在调用该过程前有关机器状态的信息息,包括各种寄存器的当前值及返回地址等包括各种寄存器的当前值及返回地址等; 为访问其它活动记录中所存放的非局为访问其它活动记录中所存放的非局部数据提供链地址部数据提供链地址(PASCAL中用到中用到); 用于指向主调过程的活动记录用于

4、指向主调过程的活动记录; 存放主调过程为被调过程提供的实参信息存放主调过程为被调过程提供的实参信息; 被调过程用来为主调过程存放返回值的域被调过程用来为主调过程存放返回值的域;6w 每个每个都可分为都可分为和和. 用于存放在编译时就能确定其体积的用于存放在编译时就能确定其体积的量量,如如简单变量、常界数组简单变量、常界数组等等; 适用于存放只有在运行时才能确定其适用于存放只有在运行时才能确定其体积的量体积的量,如如可变数组可变数组等等.w 虽然虽然可变数组可变数组的体积在动态运行时才能确定的体积在动态运行时才能确定,但但其地址的访问却在编译时就可确定其地址的访问却在编译时就可确定,即通过即通过

5、的的来访问来访问.因为与它的体积因为与它的体积有关的信息有关的信息(如如)是在是在存放的存放的.77.2 w 7.1节所示的数据区的组织节所示的数据区的组织,各自各自使用了不同的存储分配策略使用了不同的存储分配策略:87.2.1 w 若在编译阶段就能确定源程序中各个数据实体的存储空若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的间大小，则可以采用较简单的w 适合适合的语言应具备下述条件：的语言应具备下述条件：。w 满足上述条件的语言有满足上述条件的语言有等。等。w 由于过程调用无递归，过程的由于过程调用无递归，过程的可直接安排在程可直接安排在程序代码之后，执行时不必进

6、行运行时的存储管理。序代码之后，执行时不必进行运行时的存储管理。9语言的程序中各程序段均可独立进程序中各程序段均可独立进行编译；行编译；w 在编译时，为程序段中的量分配单元的在编译时，为程序段中的量分配单元的方法是，为每个量确定一个整数对方法是，为每个量确定一个整数对，其中，其中 指明数据区编号，指明数据区编号， 指明指明该存储单元在数据区相对于首单元的偏该存储单元在数据区相对于首单元的偏移量，并把此对填入符号表中。移量，并把此对填入符号表中。w 各数据区首单元地址各数据区首单元地址，待各程，待各程序段全部编译完后再由连接程序指定。序段全部编译完后再由连接程序指定。局部数据区内容见右图。局部数

7、据区内容见右图。101112345617231015182212适用于允许递归调用的程适用于允许递归调用的程序设计语言序设计语言;w 引入一运行栈引入一运行栈,w 为让过程能访问本次调用记录中数为让过程能访问本次调用记录中数据据,可设一指针可设一指针指向当前正在执行指向当前正在执行的过程之调用记录的某一特定单元的过程之调用记录的某一特定单元.w 访问本过程量访问本过程量 可通过访问地址可通过访问地址实现实现.其中其中, 是是 的相对地址的相对地址SPSP13当被调过程执行结束后，程序返回到当被调过程执行结束后，程序返回到，此时，此时，将恢复为调用前的状态；将恢复为调用前的状态；为了能够恢复原有

8、状态，每次调用发生时，应将为了能够恢复原有状态，每次调用发生时，应将原来的原来的值保存起来（作为被调过程的值保存起来（作为被调过程的的一项内容）；的一项内容）；为保证过程返回时能够从调用点正确执行下去，为保证过程返回时能够从调用点正确执行下去，应把应把保存在保存在中。中。14都被视为过程的一都被视为过程的一次次。一过程一过程 的一次的一次的的，。在在中，一过程中，一过程 调用过程调用过程 ，无论无论 是否调用其它过程，控制将最是否调用其它过程，控制将最终返回到终返回到 ，即，即 的活动是的活动是 的的。15w 综上所述，若综上所述，若是两个过程的活动，则它们的是两个过程的活动，则它们的生存期生

9、存期。w 可通过一棵树（称为可通过一棵树（称为）来描述控制进入）来描述控制进入和离开活动的途径，在树中：和离开活动的途径，在树中：16program aaa; procedure B(s1,s2); begin end; procedure D(s3,s4); begin end; procedure C(s5,s6); begin end; procedure A(s7,s8); begin end;begin end.1718 w 当程序语言允许在运行时为变量当程序语言允许在运行时为变量,采用采用是最有效的解决方案是最有效的解决方案.,为正运行的程序划出适当大的空为正运行的程序划出适当大的

10、空间间(称为称为),每当程序申请空间时每当程序申请空间时,就从堆的就从堆的找出一块空间分配给程序找出一块空间分配给程序,每当释放时则回收之每当释放时则回收之.w 在处理链表结构时在处理链表结构时,常常随机地插入或删除一些结点常常随机地插入或删除一些结点,利利用指针变量和结构类型用指针变量和结构类型,可动态地生成新结点可动态地生成新结点(使用使用函数函数), 或删除之或删除之(使用使用函数函数).19w 例如例如 struct char data; struct *next;定义了链表的定义了链表的结点结点,下面函数可在表尾添加新结点下面函数可在表尾添加新结点: w 还可用下面的函数删除表头结点还可用下