第十一章 编译系统和运行时系统

发表于 更新于

通常,除了编译器外，还需要些其他工具的帮助，才能得到可执行的目标程序 .这些工具包括预处理器、汇编器和连接器等。对于FORTRAN和C等语言来说,这些工具都较简单和明量。了解这些工具有助于掌握从源程序到可执行目标程序的实际处理过程,这些知识对于参与大型软件系统的开发是很有用的。本章介绍C语言编译系统。此外，目标代码运行时,还需要一些工具的支撑， 如动态连接程序、无用单元收集程序等，这些工具的集合称为运行时系统。本章还介绍Java语言的运行时系统及其无用单元收集程序。

11.1 C语言编译系统

C源程序可以分成若干个模块，分别进行预处理、编译和汇编、形成可重定位的目标文件。目标文件和必要的库文件连接成一个可执行的目标文件， gcc和cc是编译驱动程序的名字 。

11.1.1 预处理器

  • gcc首先调用预处理器cpp，将源程序文件翻译成一个ASCII中间文件，它是经修改后的源程序
  • cpp实现以下功能：
    • 文件包含
    • 宏展开
    • 条件编译

      11.1.2 汇编器

  • GCC系统的编译器cc1产生汇编代码
  • 最简单的汇编器对输入进行两遍扫描
  • 一遍扫描完成汇编代码到可重定位目标代码的翻译也是完全可能的
  • 用gcc -S main.c可以得到汇编文件main.s
  • 用as -o main.o main.s可以将main.s汇编成可重定位目标文件main.o

    11.1.3 连接器

  • 目标模块或目标文件的形式
    • 可重定位的目标文件
    • 可执行的目标文件
    • 共享目标文件
      • 一种特殊的可重定位目标文件
      • 在装入程序或运行程序时，动态地装入到内存并连接
  • 连接是一个收集、组织程序所需的不同代码和数据的过程，以便程序能被装入内存并被执行
  • 连接的时机
    • 编译时
    • 装入时
    • 运行时
    • 静态连接器
    • 动态连接器

      11.1.4 目标文件的格式

  • 目标文件格式随系统不同而不同
  • 介绍Unix的ELF（Executable and Linkable Format）格式
  • Linux、System V Unix的后期版本、BSD Unix变体和Sun Solaris，都使用Unix的ELF格式

    11.1.5 符号解析

  • 将每个符号引用正确地与某可重定位模块的符号表中的一个符号定义相关联，从而确定各个符号引用的位置
  • 在所有输入模块中都找不到被引用符号的定义，则打印错误消息并结束连接
  • 需要定义解析规则
    • 解析规则：函数和已初始化的全局变量称为强符号；未初始化的全局变量称为弱符号
    • 不允许有多重的强符号定义
    • 出现一个强符号定义和多个弱符号定义时，选择强符号的定义
    • 出现多个弱符号定义时，选择任意一个弱符号的定义

      11.1.6 静态库

  • 将相关的可重定位目标模块打包成一个文件,作为连接器的输入
  • 连接器仅复制库中被应用程序引用的模块

    11.1.7 可执行目标文件及装入

  • 可执行目标文件与可重定位目标文件格式类似
  • 可执行目标文件的装入由加载器完成

    11.1.8 动态连接

  • 静态库
    周期性地被维护和更新
    内存可能有多份printf和scanf的代码
  • 共享库
    在运行时可以装到任意的内存位置，被内存中的进程共享

    11.2 Java语言的运行系统

    11.2.1 Java虚拟机语言简介

  • Java程序首先由Java编译器把它编译成字节码，也就是JVML程序。
  • 常量池: 各种字符串常量,类似于传统程序设计语言中的符号表
  • 类成员信息: 域信息表和方法信息表
  • JVML指令序列

    11.2.2 Java虚拟机

    Java虚拟机一般由以下几个部分构成：
    • 类加载器（字节码验证器）
    • 解释器或/和编译器
    • 包括无用单元收集器和线程控制模块在内的运行支持系统，
    • 另外还有一些标准类和应用接口的class文件库

      11.2.3 即时编译器

  • 当一个类的某个方法第一次被调用时，虚拟机才激活即时编译器将它编译成机器代码生成的代码的执行速度可以达到解释执行的10倍
  • 但是执行过程不得不等待编译的结束，因此使得执行时间变长
  • 很多虚拟机都会使用快速解释器和优化编译器的组合或者是简单编译器和复杂编译器的组合

    11.3 无用单元收集

  • 无用单元收集器需要根据数据的活跃性来判断哪些是无用单元
  • 活跃性分析采用稳妥策略，是通过根集以及从根集开始的可达性来定义活跃性
  • 因此从实现的角度，无用单元是那些不可能从程序变量经指针链到达的堆分配记录
  • 无用单元收集可能需要来自编译器、操作系统和硬件方面的支持

    11.3.1 标记和清扫

  • 方法概述：首先标记堆上所有可达记录，然后回收未被标记的记录
    • 根集包含了全局变量、活动记录栈中的局部变量和被活跃着的过程使用的寄存器
    • 堆上活跃记录的集合是从根集开始的任何一条指针路径上的记录的集合
    • 任何图遍历算法，都可用于标记所有的可达记录
    • 清扫从堆的首地址开始, 逐个记录地考察整个堆, 寻找未被标记的记录, 把它们链成一个空闲链表
  • 传统的标记和清扫方法的问题
    • 碎片问题：当要分配一个n字节大小的记录时，发现有很多小于n字节的空闲块存在，但就是没有合适的空闲块可分配给这个记录
    • 引用局部性问题：使用块和空闲块相互交织，使得当前要使用的各个活跃记录被分散到很多的虚拟内存页中，这些页在内存中可能被频繁地换进换出

      11.3.2 引用计数

  • 方法概述：通过记住有多少指针指向每个记录来直接完成标记，引用计数存在各记录中
    • 编译器需要在每个出现指针存储的地方生成额外的指令，以调整一些引用计数器的值
    • 当一个记录的引用计数值为0的时候，就可以把该记录加入空闲链表
    • 被回收记录本身的指针域都要一一检查，它们所指向的记录的引用计数值也都要减1
  • 引用计数方法的问题
    • 碎片和引用局部性问题仍然存在
    • 并非总有效：对于循环的数据结构会失效，因为这些记录的引用计数也永远不可能减到零
    • 代价高，因为每当执行指针存储的时候，都需要执行额外的指令来调整一些引用计数
    • 引用计数收集已经被跟踪型收集代替，标记和清扫收集方法就是一种跟踪型收集方法

      11.3.3 拷贝收集

  • 方法概述
    • 这个算法和标记和清除算法一样，也遍历可达记录所组成的有向图，只不过它在遍历的同时进行清扫，并且这种清扫主要是拷贝活跃记录
    • 这种方法将堆空间分成大小相等的两块，每块都是连续的区域
  • 优缺点
    • 从理论上来说，只要有足够的内存，可得到很高的效率
    • 可以将活跃数据紧缩在一起，碎片情况消失，引用局部性得到改善
    • 需要的空间是实际需要空间的两倍
    • 拷贝大记录的代价太大

      11.3.4 分代收集

  • 原理
    • 很多程序在运行过程中，新建记录很可能很快死去，不会出现对它的拷贝；反过来，一个记录在几次收集后还可到达的话，那么很可能还会活跃到许多次收集后
    • 收集器应该将精力集中到“年轻”的数据上，因为这里有相对高的无用单元比率
  • 基本做法
    • 堆被分成代，最年轻的记录在G0代，Gi (i > 0)代中的记录比Gi1代中的任何记录都要老。越年轻的代越被频繁地收集
    • 对G0代进行收集时，这时的根集不仅仅是程序变量，它还包括G1, G2,…中指向G0的指针。幸好，老记录指向年轻得多的记录的情况极少出现，通常是较新的记录指向老记录
    • 为了避免确定G0的根集时在G1, G2,…中查找，需要编译器提供一些支持，方法有多种

      11.3.5 渐增式收集

  • 缘由
    • 虽然收集时间的总和只占整个程序运行时间很小的百分比，但是收集器仍然有可能偶尔将运行程序中断相对长的时间，对于交互式程序和实时程序来说，这一点是难以接受的
  • 改进
    • 渐增式收集：程序运行和无用单元收集交错进行
    • 困难在于，当收集器在做遍历以得到一个可达记录图时，运行程序并没有停止修改可达记录图

      11.3.6 编译器与收集器之间的相互影响

  • 对收集器的底层有下面这些基本要求
    • 能确定堆上分配的记录大小
    • 能定位包含在堆记录里的指针
    • 能定位所有在全局变量中的指针
    • 能在程序中任何可进行收集的地方找到所有在活动记录栈中和寄存器中的指针
    • 能找到所有由指针运算所产生的值指向的记录
    • 能在记录被移动时，更新所有涉及到的指针值
  • 很多所需信息只有在编译时能够获得