1
第七章 运行时的存储组织与分配
编译程序 必须为源程序中所出现的量 (常量,变量及数组
等等 )分配运行时的存储空间,
分配方案选择的是否得当 将关系到资源的合理使用,从
而会影响到程序的运行效率,
存储分配的策略有 静态分配 与 动态分配 两类,
静态分配 适合于无动态申请内存,无可变长数组,无递归
调用的程序,如 FORTRAN,BASIC等,
动态存储 分配适用面广是目前最常用的分配方案
动态分配 又有 栈式分配 与 堆式分配 两种,
2
7.1 存储组织
? 运行时内存的划分
运行时,系统为目标程序分配的存储空
间按用途可划分为下面几个部分,
1.目标代码区, 存放目标程序 ;
2.静态数据区, 存放编译 时可确定的占
用存储空间大小的数据 ;
3.运行栈区, 运行时才能分配存储空间
的数据区 ;
4.堆区, 用于用户动态申请存储空间
目标代码区
静态数据区
运行栈区
↓
…
↑
堆区
动
态
数
据
区
3
存储分配策略
? 目标代码的长度在编译时就可确定,可放在 静态区 内 ;
? 对于在编译时已知大小的数据对象 (如 常量,全局变量,
静态变量 等等 ),也可放在 静态区 内 ;
? 为提高运行效率,应尽可能多地分配 静态数据空间,
FORTRAN,BASIC的分配一般可全部放在 静态区 内,
? 像 PASCAL,C这类语言的实现,由于子程序允许 递归 地调
用,因此应用一 数据栈 来动态地管理内存分配,
? 另外 PASCAL和 C还允许 动态地申请 的内存,这种数据的
空间可由 堆式分配 实现,
4
7.1.2 活动记录
? 执行过程时所需进行的信息管
理，是通过 活动记录 实现的，
活动记录 连续存储在块中，其
内容见右图。
? 以过程为单位的动态存储分配
方案,
? 当一过程被调用时，就把其 活动
记录 压入运行时存储栈顶，返回
时弹出之 。
返回的值
实参
任选的控制链
任选的存取链
保存的机器状态
局部数据
临时变量
5
活动记录 的组成
1,临时变量域 存放目标程序临时变量的值 ;
2,局部数据域 存放本次执行中的局部数据、简单变量、
数组内情向量等 ;
3,机器状态域 保存在调用该过程前有关机器状态的信
息,包括各种寄存器的当前值及返回地址等 ;
4,任选的存取链 为访问其它活动记录中所存放的非局
部数据提供链地址 (PASCAL中用到 );
5,任选的控制链 用于指向主调过程的活动记录 ;
6,实在参数 存放主调过程为被调过程提供的实参信息 ;
7,返回值域 被调过程用来为主调过程存放返回值的域 ;
6
活动记录 的组成 (续 )
? 每个 活动记录 都可分为 定长部分 和 可变部分,
? 定长部分 用于存放在编译时就能确定其体积的
量,如 简单变量、常界数组 等 ;
? 可变部分 适用于存放只有在运行时才能确定其
体积的量,如 可变数组 等,
? 虽然 可变数组 的体积在动态运行时才能确定,但
其地址的访问却在编译时就可确定,即通过 活动
记录 的 首地址 +偏移量 来访问,因为与它的体积
有关的信息 (如 内情向量 )是在 定长部分 存放的,
7
7.2 运行时的分配策略
? 7.1节所示的数据区的组织,各自
使用了不同的存储分配策略,
? 静态分配 ;
? 栈式分配 (亦称栈式动态分配 );
? 堆式分配 (亦称堆式动态分配 ),
目标代码区
静态数据区
运行栈区
↓
…
↑
堆区
动
态
数
据
区
8
7.2.1 静态分配
? 若在编译阶段就能确定源程序中各个数据实体的存储空
间大小，则可以采用较简单的 静态存储管理
? 适合 静态管理 的语言应具备下述条件,
? 数组上下界是常数；
? 过程调用不允许递归；
? 不允许动态建立数据实体 。
? 满足上述条件的语言有 FORTRAN,BASIC等。
? 由于过程调用无递归，过程的 活动记录 可直接安排在程
序代码之后，执行时不必进行运行时的存储管理。
9
FORTRAN语言的
静态存储分配
? FORTRAN程序中各程序段均可独立进
行编译；
? 在编译时，为程序段中的量分配单元的
方法是，为每个量确定一个整数对
(m,n)，其中 m指明数据区编号,n指明
该存储单元在数据区相对于首单元的偏
移量，并把此对填入符号表中。
? 各数据区首单元地址 暂不确定,待各程
序段全部编译完后再由连接程序指定。
? FORTRAN局部数据区内容见右图。
临时变量
数组
简单变量
形式单元
隐参数 （返回
地址、寄存器
内容等）
10
各程序段数据区的分配
各段局部数据区的分配有两种方案,
(1)不考虑各段间的调用关系,各自独立占有互不相交的
空间 ;
(2)划定一连续空间,在定义各局部数据区时,根据相互间
的调用 (或不调用 )关系,安排最合理的分配方案
11
1
2 3
4 5 6
17 23 10
15 18
22
优化分配方案实例
程序段间调用关系的有向图
简单方案占用 105个单元
程序 4
(0~16)
程序 6
(0~9)
程序 5
(0~22)
程序 2
(17~31)
程序 3
(23~40)
程序 1
(41~62)
优化方案,
占用 63单元
为各程序段分配数据区
算法见 P276程序 7-1
12
7.2.2 栈式分配
? 栈式分配 适用于允许递归调用的程
序设计语言 ;
? 引入一运行栈,每调用一次过程,就把
该过程的相应调用记录压入栈,过程
执行完毕后再将其弹出栈 ;
? 为让过程能访问本次调用记录中数
据,可设一指针 SP指向当前正在执行
的过程之调用记录的某一特定单元,
? 访问本过程量 X可通过访问地址
SP+dx实现,其中,dx是 X的相对地址
主过程
调用记录
SP
调用 P前
主过程
调用记录
调用 P后
过程 P
调用记录
SP
13
当被调过程执行结束后，程序返回到 主调过程,
此时,SP将恢复为调用前的状态；
为了能够恢复原有状态，每次调用发生时，应将
原来的 SP值保存起来（作为被调过程的 调用记录
的一项内容）；
为保证过程返回时能够从调用点正确执行下去，
应把 调用点的机器状态 保存在 调用记录 中。
14
活动树
过程体的每次执行 都被视为过程的一
次 活动 。
一过程 P的一次 活动 的 生存期, 是在
执行该过程体的第一步和最后一步之
间的一系列步骤的总执行时间 （包括
P调用其它过程的执行时间） 。
在 PASCAL中，一过程 P调用过程 Q，
无论 Q是否调用其它过程，控制将最
终返回到 P，即 Q的活动是 P的 子活动 。
主
程
序
P Q
其
它
过
程
15
活动树
? 综上所述，若 A,B是两个过程的活动，则它们的
生存期 要么是不重叠的，要么是嵌套的 。
? 可通过一棵树（称为 活动树 ）来描述控制进入
和离开活动的途径，在树中,
(1)每个 结点 代表一过程的一次活动 ;
(2)根结点 代表主程序的活动 ;
(3)结点 A是 结点 B的 父结点,iff控制从活动 A进入 B;
(4)结点 A在 结点 B的左边,iff A的生存期在 B的生存期之
前,
16
program aaa;
… …
procedure B(s1,s2); begin … end;
procedure D(s3,s4); begin … end;
procedure C(s5,s6);
begin B(s5,s6);D(s5,s6) end;
procedure A(s7,s8);
begin B(s7,s8);C(s7,s8) end;
begin A(a1,a2); … … end,
主程序 aaa
A(a1,a2)
B(a1,a2) C(a1,a2)
B(a1,a2) D(a1,a2)
活动树反映了活动记录
在栈中的变化
活动树的例子
17
18
7.2.3 堆式分配
? 当程序语言允许在运行时为变量 动态申请和释放存储空
间,采用 堆式分配 是最有效的解决方案,
? 堆式分配 的基本思想是,为正运行的程序划出适当大的空
间 (称为 堆 Heap),每当程序申请空间时,就从堆的 空闲区
找出一块空间分配给程序,每当释放时则回收之,
? 在处理链表结构时,常常随机地插入或删除一些结点,利
用指针变量和结构类型,可动态地生成新结点 (使用
malloc()函数 ),或删除之 (使用 free()函数 ),
19
堆式分配举例
? 例如 struct node {char data; struct node *next;}定义了链表的
结点,下面函数可在表尾添加新结点,
void Append(head,ch)
struct node *head; char ch; {struct node *p=head;
while(p->next!=NULL) p=p->next;
p->next=malloc(sizeof(struct node));
p->next->data=ch; p->next->next=NULL;}
? 还可用下面的函数删除表头结点,
void Delete (head)
struct node *head; { struct node *p=head;
if(p!=NULL) { head =head->next; free(p);} }
20
堆式存储管理的实现
? 将存储空间 划分为若干存储块 ;用户可随机地申请或释
放一个或多个块 ;
? 在存储空间中建立两个队列,空闲队列和忙队列,空闲队
列拉成 链,链首用 FREE指针指明,忙队列用一 (已占块 )记
录表 记录各占用块的首址及大小信息 (也可用链进行记
录 ),
? 申请时可按需要找到合适的块分配之 (分配策略有最佳分
配或随机分配等 );
? 释放时将该块插入到空闲队列 (能合并时可合并 ),并从占
用记录表中删除相应的项,
第七章 运行时的存储组织与分配
编译程序 必须为源程序中所出现的量 (常量,变量及数组
等等 )分配运行时的存储空间,
分配方案选择的是否得当 将关系到资源的合理使用,从
而会影响到程序的运行效率,
存储分配的策略有 静态分配 与 动态分配 两类,
静态分配 适合于无动态申请内存,无可变长数组,无递归
调用的程序,如 FORTRAN,BASIC等,
动态存储 分配适用面广是目前最常用的分配方案
动态分配 又有 栈式分配 与 堆式分配 两种,
2
7.1 存储组织
? 运行时内存的划分
运行时,系统为目标程序分配的存储空
间按用途可划分为下面几个部分,
1.目标代码区, 存放目标程序 ;
2.静态数据区, 存放编译 时可确定的占
用存储空间大小的数据 ;
3.运行栈区, 运行时才能分配存储空间
的数据区 ;
4.堆区, 用于用户动态申请存储空间
目标代码区
静态数据区
运行栈区
↓
…
↑
堆区
动
态
数
据
区
3
存储分配策略
? 目标代码的长度在编译时就可确定,可放在 静态区 内 ;
? 对于在编译时已知大小的数据对象 (如 常量,全局变量,
静态变量 等等 ),也可放在 静态区 内 ;
? 为提高运行效率,应尽可能多地分配 静态数据空间,
FORTRAN,BASIC的分配一般可全部放在 静态区 内,
? 像 PASCAL,C这类语言的实现,由于子程序允许 递归 地调
用,因此应用一 数据栈 来动态地管理内存分配,
? 另外 PASCAL和 C还允许 动态地申请 的内存,这种数据的
空间可由 堆式分配 实现,
4
7.1.2 活动记录
? 执行过程时所需进行的信息管
理，是通过 活动记录 实现的，
活动记录 连续存储在块中，其
内容见右图。
? 以过程为单位的动态存储分配
方案,
? 当一过程被调用时，就把其 活动
记录 压入运行时存储栈顶，返回
时弹出之 。
返回的值
实参
任选的控制链
任选的存取链
保存的机器状态
局部数据
临时变量
5
活动记录 的组成
1,临时变量域 存放目标程序临时变量的值 ;
2,局部数据域 存放本次执行中的局部数据、简单变量、
数组内情向量等 ;
3,机器状态域 保存在调用该过程前有关机器状态的信
息,包括各种寄存器的当前值及返回地址等 ;
4,任选的存取链 为访问其它活动记录中所存放的非局
部数据提供链地址 (PASCAL中用到 );
5,任选的控制链 用于指向主调过程的活动记录 ;
6,实在参数 存放主调过程为被调过程提供的实参信息 ;
7,返回值域 被调过程用来为主调过程存放返回值的域 ;
6
活动记录 的组成 (续 )
? 每个 活动记录 都可分为 定长部分 和 可变部分,
? 定长部分 用于存放在编译时就能确定其体积的
量,如 简单变量、常界数组 等 ;
? 可变部分 适用于存放只有在运行时才能确定其
体积的量,如 可变数组 等,
? 虽然 可变数组 的体积在动态运行时才能确定,但
其地址的访问却在编译时就可确定,即通过 活动
记录 的 首地址 +偏移量 来访问,因为与它的体积
有关的信息 (如 内情向量 )是在 定长部分 存放的,
7
7.2 运行时的分配策略
? 7.1节所示的数据区的组织,各自
使用了不同的存储分配策略,
? 静态分配 ;
? 栈式分配 (亦称栈式动态分配 );
? 堆式分配 (亦称堆式动态分配 ),
目标代码区
静态数据区
运行栈区
↓
…
↑
堆区
动
态
数
据
区
8
7.2.1 静态分配
? 若在编译阶段就能确定源程序中各个数据实体的存储空
间大小，则可以采用较简单的 静态存储管理
? 适合 静态管理 的语言应具备下述条件,
? 数组上下界是常数；
? 过程调用不允许递归；
? 不允许动态建立数据实体 。
? 满足上述条件的语言有 FORTRAN,BASIC等。
? 由于过程调用无递归，过程的 活动记录 可直接安排在程
序代码之后，执行时不必进行运行时的存储管理。
9
FORTRAN语言的
静态存储分配
? FORTRAN程序中各程序段均可独立进
行编译；
? 在编译时，为程序段中的量分配单元的
方法是，为每个量确定一个整数对
(m,n)，其中 m指明数据区编号,n指明
该存储单元在数据区相对于首单元的偏
移量，并把此对填入符号表中。
? 各数据区首单元地址 暂不确定,待各程
序段全部编译完后再由连接程序指定。
? FORTRAN局部数据区内容见右图。
临时变量
数组
简单变量
形式单元
隐参数 （返回
地址、寄存器
内容等）
10
各程序段数据区的分配
各段局部数据区的分配有两种方案,
(1)不考虑各段间的调用关系,各自独立占有互不相交的
空间 ;
(2)划定一连续空间,在定义各局部数据区时,根据相互间
的调用 (或不调用 )关系,安排最合理的分配方案
11
1
2 3
4 5 6
17 23 10
15 18
22
优化分配方案实例
程序段间调用关系的有向图
简单方案占用 105个单元
程序 4
(0~16)
程序 6
(0~9)
程序 5
(0~22)
程序 2
(17~31)
程序 3
(23~40)
程序 1
(41~62)
优化方案,
占用 63单元
为各程序段分配数据区
算法见 P276程序 7-1
12
7.2.2 栈式分配
? 栈式分配 适用于允许递归调用的程
序设计语言 ;
? 引入一运行栈,每调用一次过程,就把
该过程的相应调用记录压入栈,过程
执行完毕后再将其弹出栈 ;
? 为让过程能访问本次调用记录中数
据,可设一指针 SP指向当前正在执行
的过程之调用记录的某一特定单元,
? 访问本过程量 X可通过访问地址
SP+dx实现,其中,dx是 X的相对地址
主过程
调用记录
SP
调用 P前
主过程
调用记录
调用 P后
过程 P
调用记录
SP
13
当被调过程执行结束后，程序返回到 主调过程,
此时,SP将恢复为调用前的状态；
为了能够恢复原有状态，每次调用发生时，应将
原来的 SP值保存起来（作为被调过程的 调用记录
的一项内容）；
为保证过程返回时能够从调用点正确执行下去，
应把 调用点的机器状态 保存在 调用记录 中。
14
活动树
过程体的每次执行 都被视为过程的一
次 活动 。
一过程 P的一次 活动 的 生存期, 是在
执行该过程体的第一步和最后一步之
间的一系列步骤的总执行时间 （包括
P调用其它过程的执行时间） 。
在 PASCAL中，一过程 P调用过程 Q，
无论 Q是否调用其它过程，控制将最
终返回到 P，即 Q的活动是 P的 子活动 。
主
程
序
P Q
其
它
过
程
15
活动树
? 综上所述，若 A,B是两个过程的活动，则它们的
生存期 要么是不重叠的，要么是嵌套的 。
? 可通过一棵树（称为 活动树 ）来描述控制进入
和离开活动的途径，在树中,
(1)每个 结点 代表一过程的一次活动 ;
(2)根结点 代表主程序的活动 ;
(3)结点 A是 结点 B的 父结点,iff控制从活动 A进入 B;
(4)结点 A在 结点 B的左边,iff A的生存期在 B的生存期之
前,
16
program aaa;
… …
procedure B(s1,s2); begin … end;
procedure D(s3,s4); begin … end;
procedure C(s5,s6);
begin B(s5,s6);D(s5,s6) end;
procedure A(s7,s8);
begin B(s7,s8);C(s7,s8) end;
begin A(a1,a2); … … end,
主程序 aaa
A(a1,a2)
B(a1,a2) C(a1,a2)
B(a1,a2) D(a1,a2)
活动树反映了活动记录
在栈中的变化
活动树的例子
17
18
7.2.3 堆式分配
? 当程序语言允许在运行时为变量 动态申请和释放存储空
间,采用 堆式分配 是最有效的解决方案,
? 堆式分配 的基本思想是,为正运行的程序划出适当大的空
间 (称为 堆 Heap),每当程序申请空间时,就从堆的 空闲区
找出一块空间分配给程序,每当释放时则回收之,
? 在处理链表结构时,常常随机地插入或删除一些结点,利
用指针变量和结构类型,可动态地生成新结点 (使用
malloc()函数 ),或删除之 (使用 free()函数 ),
19
堆式分配举例
? 例如 struct node {char data; struct node *next;}定义了链表的
结点,下面函数可在表尾添加新结点,
void Append(head,ch)
struct node *head; char ch; {struct node *p=head;
while(p->next!=NULL) p=p->next;
p->next=malloc(sizeof(struct node));
p->next->data=ch; p->next->next=NULL;}
? 还可用下面的函数删除表头结点,
void Delete (head)
struct node *head; { struct node *p=head;
if(p!=NULL) { head =head->next; free(p);} }
20
堆式存储管理的实现
? 将存储空间 划分为若干存储块 ;用户可随机地申请或释
放一个或多个块 ;
? 在存储空间中建立两个队列,空闲队列和忙队列,空闲队
列拉成 链,链首用 FREE指针指明,忙队列用一 (已占块 )记
录表 记录各占用块的首址及大小信息 (也可用链进行记
录 ),
? 申请时可按需要找到合适的块分配之 (分配策略有最佳分
配或随机分配等 );
? 释放时将该块插入到空闲队列 (能合并时可合并 ),并从占
用记录表中删除相应的项,
