Arya

第七章 运行存储分配 note
[+] 明天除夕,虽然一点过年的感觉都没有就是咯[+] 出门买面包吧,晚上回来再学一点,说好的新年之前要看完,就一...
扫描右侧二维码阅读全文
03
2019/02

第七章 运行存储分配 note

[+] 明天除夕,虽然一点过年的感觉都没有就是咯
[+] 出门买面包吧,晚上回来再学一点,说好的新年之前要看完,就一定要做到啊

第七章 运行存储分配 note

运行存储分配概述

运行存储分配策略

  • 编译器在工作过程中,必须为源程序出现的一些数据对象分配运行时的存储空间
  • 对于那些在编译时刻就可以确定大小的数据对象,可以在编译时刻就为它们分配存储空间,这样的分配策略称为静态存储分配策略
  • 反之,如果不能在编译时完全确定数据对象的大小,就要采用动态存储分配的策略。即在编译时仅产生各种必要的信息,而在运行时刻,再动态地分配数据对象的存储空间
    栈式存储分配
    堆式分配存储

这里的静态动态分别对应编译时刻运行时刻

运行时的内存划分

Image7-6.png

  • 生成的目标代码的大小在编译时刻就可以确定,因此目标代码可以存放在静态代码区,通常静态代码区位于存储的低端
  • 对于那些在编译时刻就能确定大小的数据,我们可以把它们放在静态数据区
  • 为了使运行时刻的空间利用率最大化,另外两个区被存放在剩余地址空间的相对两端,且这两个区是动态的,它们的大小随着程序的运行而变化

中存放着一种称为活动记录的数据结构,活动记录在过程调用时进栈,在过程返回时出栈;区用来管理这些具有长生命周期数据对象

活动记录

  • 使用过程(或函数、方法)作为用户自定义动作的单元的语言,其编译器通常以过程为单位分配存储空间
  • 过程体的每次执行称为该过程的一个活动(activation)
  • 过程每执行一次,就为它分配一块连续存储区,用来管理过程一次执行所需的信息,这块连续存储区称为活动记录( activation record)

活动记录的一般形式

Image7-7.png

其中控制链是一个指针

静态存储分配

  • 在静态存储分配中,编译器为每个过程确定其活动记录在目标程序中的位置
  • 这样,过程中每个名字的存储位置就确定了
  • 因此,这些名字的存储地址可以被编译到目标代码中
  • 过程每次执行时,它的名字都绑定到同样的存储单元

静态存储分配的限制条件
适合静态存储分配的语言必须满足以下条件

  • 数组上下界必须是常数
  • 不允许过程的递归调用
  • 不允许动态建立数据实体

满足这些条件的语言有BASICFORTRAN

常用的静态分配方法有

  • 顺序分配法
  • 层次分配法

顺序分配法

  • 按照过程出现的先后顺序逐段分配存储空间
  • 各过程的活动记录占用互不相交的存储空间

接下来举了一个例子

Image7-8.png

这个图表示了这些过程之间的调用关系,如1可调用2和3,3可调用6和5,2可调用4和16

根据以上规定,我们可以得出存储区域的分配方式

过程存储区域
10~21
222~36
337~54
455~71
572~94
695~104

共需要105个存储单元

综上,顺序分配法的优缺点分别是:
优点:处理上简单
缺点:对内存空间的使用不够经济合理

层次分配法
通过对过程间的调用关系进行分析,凡属无相互调用关系并列过程,尽量使其局部数据共享存储空间

Image7-9.png

依然是这个例子

按照现在分配方式则,如下:

Image7-10.png

以调用的过程中所占的最大存储单元为起点,占用连续的存储单元

层次分配算法
Bn:过程调用关系矩阵

  • B i =1: 表示第i个过程调用第j个过程
  • B i =0 :表示第i个过程不调用第j个过程

Image7-11.png

Image7-12.png

栈式存储分配

  • 有些语言使用过程函数方法作为用户自定义动作的单元,几乎所有针对这些语言的编译器都把它们的(至少一部分的)运行时刻存储以的形式进行管理,称为栈式存储分配
  • 当一个过程被调用时,该过程的活动记录被压入栈;当过程结束时,该活动记录被弹出
  • 这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间,而且允许以如下方式为一个过程编译代码:它的非局部变量相对地址总是固定的,和过程调用序列无关

活动树

  • 用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树
  • 树中的每个结点对应于一个活动根结点是启动程序执行的main过程的活动
  • 在表示过程p的某个活动的结点上,其子结点对应于被p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序,自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束

接下来举一个快排例子

Image7-13.png

当一个过程是递归的时候,常常会有该过程的多个活动记录同时出现在栈中

Image7-14.png

蓝线指向的是已经执行完毕的活动,红线指向的是处于活跃状态的活动,黑线指向的是未执行的活动。上面只给出了蓝色线条部分的控制。可以看出:

  • 每个活跃的活动都有一个位于控制栈中的活动记录
  • 活动树的的活动记录位于栈底
  • 程序控制所在的活动的记录位于栈顶
  • 栈中全部活动记录的序列对应于在活动树中到达当前控制所在的活动结点的路径

这里也给出了设计活动记录的一些原则

Image7-15.png

调用序列和返回序列

过程调用和过程返回都需要执行一些代码来管理活动记录栈,保存或恢复机器状态等

  • 实现过程调用的代码段称为调用序列,调用序列为一个活动记录在栈中分配空间,并在此记录的字段中填写信息
  • 实现过程返回的代码段称为返回序列,返回序列用于恢复机器状态,使得调用过程能够在调用结束之后继续执行* 一个调用代码序列中的代码通常被分割到调用过程(调用者)和被调用过程(被调用者)中。返回序列也是

调用序列
接下来举一个调用过程和被调用过程各做完成调用序列的一个过程

Image7-16.png

返回序列

Image7-17.png

调用者和被调用者之间的任务划分

Image7-18.png

变长数据的存储分配

  • 现代程序设计语言中,在编译时刻不能确定大小的对象将被分配在区。但是,如果他们是过程的局部对象,也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因:可以避免对他们的空间进行垃圾回收,也就减少了相应的开销
  • 只有一个数据对象局部于某个过程,且当此过程技术使它变得不可访问,才可以使用栈为这个对象分配空间

这里也举了一个例子

Image7-19.png

非局部数据的访问

一个过程除了可以使用过程自身定义的局部数据以外,还可以使用过程外定义的非局部数据
语言可以分为两种类型

  • 支持过程嵌套声明的语言
    可以在一个过程中声明另一个过程
    例:Pascal
  • 不支持过程嵌套声明的语言
    不可以在一个过程中声明另一个过程
    例:C

分别举例

Image7-20.png

Image7-21.png

无过程嵌套声明时的数据访问

变量的存储分配和访问

  • 全局变量被分配在静态区,使用静态确定的地址访问它们
  • 其它变量一定是栈顶活动的局部变量。可以通过运行时刻栈的top_sp指针访问它们

有过程嵌套声明时的数据访问

嵌套深度

  • 过程的嵌套深度
    不内嵌在任何其它过程中的过程,设其嵌套深度为1
    如果一个过程p在一个嵌套深度为i的过程中定义,则设定p的嵌套深度为i +1
  • 变量的嵌套深度
    将变量声明所在过程的嵌套深度作为该变量的嵌套深度

举了一个Pascal语言的例子

Image7-22.png

访问链(Access Links)

  • 静态作用域规则:只要过程b的声明嵌套在过程a的声明中,过程b就可以访问过程a中声明的对象
  • 可以在相互嵌套的过程的活动记录之间建立一种称
    为访问链(Access link)的指针,使得内嵌的过程可以访问外层过程中声明的对象
    如果过程b在源代码中直接嵌套在过程a中(b的嵌套深度比a的嵌套深度多1),那么b的任何活动中的访问链都指向最近的a

访问链的建立

Image7-23.png

其中s不可以调用p,因为p并不是直接定义在s中

Image7-24.png

Image7-25.png

堆式存储分配

  • 堆式存储分配是把连续存储区域分成,当活动记录或其它对象需要时就分配
  • 块的释放可以按任意次序进行,所以经过一段时间后,对可能包含交错的正在使用已经释放

堆式分配的示意图

Image7-26.png

申请
设当前自由块总长为M,欲申请长度为n
如果存在若干个长度大于或等于n的存储块,可按以下策略之一进行存储分配

  • 取长度m满足需求的第1个自由块,将长度为m-n的剩余部分仍放在自由链中
  • 取长度m满足需求的最小的自由块
  • 取长度m满足需求的最大的自由块

如果不存在长度大于或等于n的存储块

  • 如果M≥n,将自由块在堆中进行移位和重组(对各有关部分都需作相应的修改,是一件十分复杂和困难的工作)
  • 如果M<n,则应采用更复杂的策略来解决堆的管理问题

释放
只需将被释放的存储块作为新的自由块插入自由链中,并删除已占块记录表中相应的记录即可

为实现堆式存储管理,必须完成大量的辅助操作,如排序、查表、填表、插入、删除、……而且其空间和时间的开销较大

符号表

符号表的组织:
为每个作用域(程序块)建立一个独立的符号表

Image7-27.png

当前栈顶的活动是p(1,3),假设我们要在过程p中访问数据a,首先我们在p所在的符号表中查找名字a,如果没有找到,我们就沿着指针来到外围过程quicksort所在的符号表,那么栈顶的符号p也沿着访问链来到了过程q所在的活动记录,这时候我们就在过程q的符号表中中查找a,没找到的话,就沿着指针来到的最外围的过程s的符号表,最终找到a

Image7-28.png

简单的阐述一下3种情况

Image7-29.png

标识符的基本处理方法
当在某一层的声明语句中识别出一个标识符(id的定义性出现)时,以此标识符查相应于本层的符号表

  • 如果查到,则报错并发出诊断信息“id重复声明

    • 否则,在符号表中加入新登记项,将标识符及有关信息填入

当在可执行语句部分扫视到标识符时( id的应用性出现)

  • 首先在该层符号表中查找该id,如果找不到,则到直接外层符号表中去查,如此等等,一旦找到,则在表中取出有关信息并作相应处理
  • 如果查遍所有外层符号表均未找到该id,则报错并发出诊断信息“id未声明

符号表的建立

嵌套过程声明语句的文法

P→D
D→D D | proc id;D S | id:T;

在允许嵌套过程声明的语言中,局部于每个过程的名字可以使用第6章介绍的方法分配相对地址;当看到嵌套的过程p时,应暂时挂起外围过程q声明语句的处理

Image7-30.png

Last modification:February 3rd, 2019 at 05:55 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment