运行时内存的划分

目标代码存放在固定大小的 代码区

大小可确定的变量、全局变量存放在固定大小的 静态区(可读可写)

存放活动记录(或称为栈帧),主要是一些短生命周期的数据。每个线程有自己的栈。

存放编译时大小无法确定的数据(而指向这些数据的指针,比如数组的首地址,则存放在栈中),通常是长生命周期的数据。线程之间可以共享堆。

过程起源于为了节省内存而可独立编译的程序片段。

一个过程的每一次执行称为一个活动

每次活动时记录的状态称为活动记录。每个活动记录中有一系列的域。

用一棵树存放程序运行过程中所有的活动状态,称为活动树

活动树和程序行为间存在对应关系:

1)过程调用的序列和活动树的前序遍历相对应;

2)过程返回的序列和活动树的后序遍历相对应;

3)亲节点是未结束活动,且路径顺序即调用顺序

假定控制流(当前状态)位于某个过程的特定活动中,且该活动对应于活动树上的某个结点 N。那么当前尚未结束的(即活跃的)活动就是结点 N 及其祖先结点对应的活动。这些活动被调用的顺序就是他们从根节点到 N 的路径上的出现顺序。这些活动将按照这个顺序的反序返回。

根据这样的性质,使得我们可以通过 实现程序控制。

活动记录(栈帧)中各种域的作用

如下:

# 名称 作用
1 临时数据 存放表达式中间结果
2 局部数据 存放局部数据。详见下文。
3 机器状态 调用前的状态,如之前的寄存器等,以便恢复现场
4 访问链 指向外层的作用域栈帧。由于只和代码有关,又叫静态链
5 控制链 指向调用方的(上一个)栈帧(比如 RSP,存放上个帧栈顶)由于在运行过程中不断压栈时形成,又叫动态链
6 实参 用于存放主调函数为被调用函数所提供的实参信息
7 返回值 被调用函数用来为主调函数存放返回值的域

image_up_1640841939cc3497cc.jpg

斜体 表示非必须的 在实际实现时,返回值和部分实参通过寄存器传递。多数数据放在栈中。

变量的存储和分配

不可嵌套声明语言

例如 C,函数内不能再声明函数。这类语言的嵌套深度为 1:

(1)全局变量放在静态区。访问时使用固定地址。 (2)其它变量放在栈顶。一定是栈顶活动的局部变量。

可嵌套声明语言

这种情况下,比如 p 嵌套 q,则 p 的局部变量 lp 对于 q 而言是可访问的。这类语言的嵌套深度 > 1. 解决方法是访问链。

function p(params) {
    let lp = 0;
    function q() {
        return lp + 1;
    }
    lp = q();    
}

如嵌套顺序:$m \supset n \supset p \supset q$ , q 中引用了变量 $a$ ,那么 q 需要由内向外寻找 $a$ 的第一个声明。

为了实现这样的功能,增加 访问链域,指向当前过程的直接外围过程的最近一次活动记录的局部数据域起始位置。

而寻找声明的过程,就是沿着 访问链 溯源的过程。

浅访问:即不需要一直溯源,在上级可以找到声明。修改后,上级负责同步到更上一级。

深访问:即一直溯源,开销更大,一致性更好。

类比缓存的直写和回写

传参机制

表达式 a [i] := a [j]a := b 中,

  • a [i] a 代表存储单元的地址,即左值
  • a [j] b 代表存储单元的内容,即右值

传值调用

传值调用(call-by-value):

这是函数式语言中唯一的参数传递机制,无任何副作用,仅相当于用参数的右值替换过程中的对应项。

例子:

int max(int x, int y) {    
    bool ret = x > y ? x : y;
    x = 10; // 这一句不会产生任何效果
    return ret;
}

原因在于,传递 x,y 时,其值被放到临时寄存器。所以即便修改,也只修改了临时寄存器。

引用调用

引用调用(call-by-reference)

下面的函数实现交换 x, y。& 表明要进行引用调用。这要求 x, y 的空间必须已经分配好。

void swap(int &x, int &y)
{
   int temp;
   temp = x; /* 保存地址 x 的值 */
   x = y;    /* 把 y 赋值给 x */
   y = temp; /* 把 x 赋值给 y  */
  
   return;
}

C++ 支持引用调用,C 不支持。

实现机制:

  1. 如果实参是具有左值的名字或表达式, 则传递这个左值本身。
  2. 如果实参是没有左值的表达式(如 a+b 或 2 等),则分配临时空间,计算完成后传递此临时空间地址

复制恢复

复制恢复(copy-restore)

体会 copy in, copy out—— 这种机制能够做到 “看上去传递了引用,其实是传递了值”。

例:

int y;
calling_procedure()
{
   y = 10;          // 1
   copy_restore (y); // 2 传递 y 的值
   printf y;        // 7 prints 99 
}
copy_restore (int x) // 3 x 是从外面复制进来的
{     
   x = 99; // 4 外面的 y 依旧是 10
   y = 0;  // 5 外面的 y 变成 0
           // 6 把 x 的值复制出去,变成外面的 y 的值
}
program copy_ref(input, output);
var a, b: integer;
procedure exchange(var x, y: integer);
    var temp: integer;
    begin
        temp:=x;
        x:=y;
        y:=temp
    end;
begin
    a:=1; b:=2;
    exchange(a,b);    
    writeln('a=',a); writeln('b=',b)
end

结果:

a = 2
b = 1

实现原理:

  • 过程调用时,调用过程对实参求值,将实参的右值传递给 被调用过程,写入其活动记录的参数域中 (copy in), 并记 录与形参相应的实参的左值。
  • 被调用过程执行时,对形参的操作在自己的活动记录的参 数域空间上进行。
  • 控制返回时,被调用过程根据所记录的实参的左值把形参 的当前右值复制到相应实参的存储空间中 (copy out) 。 当 然,只有具有左值的那些实参的值被复制出来。

传名调用

传名调用(call-by-name)是一种 “宏展开” 式的调用。

下面的 scala 代码用 => 指明传名调用策略:

object Test {
   def main(args: Array[String]) {
        delayed(time());
   }

   def time() = {
      println ("获取时间,单位为纳秒")
      System.nanoTime
   }
   def delayed( t: => Long ) = {
      println ("在 delayed 方法内")
      println ("参数:" + t)
      t
   }
}

我们展开看,它其实相当于:

   def main(args: Array[String]) {
        println ("在 delayed 方法内")
        println ("参数:" + time ())
        time()
   }
#define MAX(X,Y) X>Y?X:Y

main(){
    int a = 1>2?1:2
    int b = MAX(2,3)
}

因此运行结果:

$scala Test
在 delayed 方法内
获取时间,单位为纳秒
参数: 1197731527425877
获取时间,单位为纳秒