程序的装载方式

程序执行时所需要的指令和数据必须在内存中才能够运行。最简单的就是静态装入：将程序运行所需要的指令和数据全都装入内存中。当程序所需要内存大于物理内存时，无法满足静态装入的要求，这个时候就需要使用动态装入了，其思想是将程序运行时当前不用的模块放在磁盘，使用的模块放在内存。

动态装入典型的两种方法：覆盖装入（Overlay）和页映射（Paging），都利用了程序的局部性原理，将程序最常用的部分驻留在内存中，不太常用的部分存放在磁盘，这样可以有效地提高内存利用率。

1.覆盖载入

覆盖装入在没有发明虚拟存储之前使用比较广泛，现在已经被淘汰。覆盖装入在计算机发展初期内存资源紧张的情况下，为程序的正常运行提供了解决方案，其思想还是值得学习和借鉴的。

覆盖装入的做法是程序员在编写程序的时候必须手工将程序分割成若干块，然后编写一个小的辅助代码来管理这些模块何时应该驻留内存，何时应该被替换掉。这个辅助代码就是所谓的覆盖管理器（Overlay Manager）。如果程序有多个模块，程序员需要手工将模块按照它们之间的调用依赖关系组织成树状结构。

假设一个程序有主模块 main，模块 main 依赖于模块 A 和 B，模块 A 依赖于模块 C 和 D，模块 B 依赖于模块 E 和 F。那么程序运行时，其在内存中的覆盖方式如下图所示。

在这里插入图片描述

以上的覆盖载入方式需要由覆盖管理器来管理，需要满足如下两点： （1）树状结构中，任意一个模块到 main 模块为调用路径，当该模块被调用时，整个调用路径上的所有模块均需要存在于内存。比如程序在模块 E 中执行代码，那么模块 B 和 main 必须都在内存，以确保模块 E 在执行完毕后能够正确返回至模块 B 和 main。 （2）禁止跨树间调用。任意一个模块不允许跨树间调用，比如模块 A 不能调用模块 B、E 和 F，模块 B 也不能调用模块 A、C 和 D，因为覆盖管理器不能保证跨树间的模块同时存在于内存。如果两个子模块都依赖于某个模块，比如模块 E 和 F 都依赖于另一个模块 G，那么可以将模块 G 并入模块 main 中，这样 G 就在 E 和 F 的调用路径上了。

2.页映射

页映射是虚拟存储机制的一部分，它随着虚拟存储的发明而诞生。页映射就是将内存和所有磁盘中的数据和指令按照页为单位划分成若干个页，以后所有的装载和操作的单位就是页。硬件规定页的大小有 4096 字节、8192 字节、2MB、4MB 等。目前主流的 x64 架构的 CPU 均采用 4096 字节大小的页。

假设我们拥有一个内存大小为 16KB 的 64 位机器，每个页大小为 4096 字节，那么共有 4 个页，如下表所示：

假设有一个程序其指令和数据大小总和为 32KB，那么可分为 8 个页，编号为 P0~P7，很明显 16KB 的内存是无法容纳 32KB 的程序的。使用页映射的动态装载的方式，可以让程序正确地运行。假设程序的入口地址在 P0，装载管理器发现程序的 P0 不在内存中，于是将内存 F0 分配给 P0，并且将 P0 的内容装入 F0，运行一段时间后，程序需要使用 P5、P3 和 P6，那么分别将 P5、P3 和 P6 载入 F1、F2 和 F3。其映射关系如下：

在这里插入图片描述

如果程序只需要 P0、P5、P3 和 P6，那么程序可以一直运行下去，但是如果程序后面的执行还需要其他的页，此时装载管理器必须淘汰一页腾出空间载入下一页。选择内存中哪一页来淘汰，可以有多种选择的方式，比如可以淘汰 P0，因为 P0 最先被载入内存，这种方式为先进先出（FIFO，First Input Firt Output）。假如 P1 最近一段时间都没有被使用，那么可以选择淘汰 P1，这种方式为最近最久未使用（LRU，Least Recently Used）。

实际上，这里的装载管理器是现代操作系统的一部分，即存储管理器。目前主流的操作系统都是按照页映射的方式完成程序的装载，比如 Windows 对 PE 文件的装载和 Linux 对 ELF 文件的装载，均采用这种方式。

参考文献

[1] 俞甲子,石凡,等.程序员的自我修养——链接、装载与库[M].北京:电子工业出版社,2009-04.C6.2装载的方式.P153-157