6.2 装载的方式
程序执行时所需要的指令和数据必须在内存中才能够正常运行，最简单的办法就是将程序运行所需要的指令和数据全都装入内存中，这样程序就可以顺利运行，这就是最简单的静态装入的办法。但是很多情况下程序所需要的内存数量大于物理内存的数量，当内存的数量不够时，根本的解决办法就是添加内存。相对于磁盘来说，内存是昂贵且稀有的，这种情况自计算机磁盘诞生以来一直如此。所以人们想尽各种办法，希望能够在不添加内存的情况下让更多的程序运行起来，尽可能有效地利用内存。后来研究发现，程序运行时是有局部性原理的，所以我们可以将程序最常用的部分驻留在内存中，而将一些不太常用的数据存放在磁盘里面，这就是动态装入的基本原理。
覆盖装入（Overlay）和页映射（Paging）是两种很典型的动态装载方法，它们所采用的思想都差不多，原则上都是利用了程序的局部性原理。动态装入的思想是程序用到哪个模块，就将哪个模块装入内存，如果不用就暂时不装入，存放在磁盘中。
注意
按照2009年2月的数据，以一个普通的希捷7200RPM的桌面PC硬盘为例，它拥有8 MB缓存，500 GB的容量，价格是459元。按照每GB的价格来算，DDR2 667内存每GB约150元，而硬盘每GB的价格不到1元，价格大约是内存的1/200。
6.2.1 覆盖装入
覆盖装入在没有发明虚拟存储之前使用比较广泛，现在已经几乎被淘汰了。虽然这种方法很蹩脚，在被虚拟存储惯坏了的现代PC机程序员眼里可能不屑一顾，但是它在计算机发展的初期的确为程序能够在内存受限的机器下正常运行提供了一种解决方案。它所体现的一些思想还是很有意义的。值得一提的是，在一些现代嵌入式的内存受限环境下，特别是诸如DSP等，这种方法或许还有用武之地。
覆盖装入的方法把挖掘内存潜力的任务交给了程序员，程序员在编写程序的时候必须手工将程序分割成若干块，然后编写一个小的辅助代码来管理这些模块何时应该驻留内存而何时应该被替换掉。这个小的辅助代码就是所谓的覆盖管理器（Overlay Manager）。最简单的情况下，一个程序有主模块"main"，main分别会调用到模块A和模块B，但是A和B之间不会相互调用；这三个模块的大小分别是1 024字节、512字节和256字节。假设不考虑内存对齐、装载地址限制的情况，理论上运行这个程序需要有1 792个字节的内存。如果我们采用覆盖装入的办法，那么在内存中可以这样安排，如图6-2所示。
图6-2 简单覆盖载入
由于模块A和模块B之间相互调用依赖关系，我们可以把模块A和模块B在内存中"相互覆盖"，即两个模块共享块内存区域。当main模块调用模块A时，覆盖管理器保证将模块A从文件中读入内存；当模块main调用模块B时，则覆盖管理器将模块B从文件中读入内存，由于这时模块A不会被使用，那么模块B可以装入到原来模块A所占用的内存空间。很明显，除了覆盖管理器，整个程序运行只需要1 536个字节，比原来的方案节省了256字节的空间。覆盖管理器本身往往很小，从数十字节到数百字节不等，一般都常驻内存。
上面的例子是最简单的覆盖情况，但是事实上程序往往不止两个模块，而模块之间的调用关系也比上面的例子要复杂。在多个模块的情况下，程序员需要手工将模块按照它们之间的调用依赖关系组织成树状结构。
按照图6-3的组织关系，模块main依赖于模块A和B，模块A依赖于C和D；模块B依赖于E和F，则它们在内存中的覆盖方式如图中所示。很明显，这个程序的运行方式与前面的例子大同小异，值得注意的是，覆盖管理器需要保证两点。
图6-3 复杂的覆盖载入
- 这个树状结构中从任何一个模块到树的根（也就是main）模块都叫调用路径。当该模块被调用时，整个调用路径上的模块必须都在内存中。比如程序正在模块E中执行代码，那么模块B和模块main必须都在内存中，以确保模块E执行完毕以后能够正确返回至模块B和模块main。
- 禁止跨树间调用。任意一个模块不允许跨过树状结构进行调用。比如上面例子中，模块A不可以调用模块B、E、F；模块C不可以调用模块D、B、E、F等。因为覆盖管理器不能够保证跨树间的模块能够存在于内存中。不过很多时候可能两个子模块都需要依赖于某个模块，比如模块E和模块C都需要另外一个模块G，那么最方便的做法是将模块G并入到main模块中，这样G就在E和C的调用路径上了。
当然，由于跨模块间的调用都需要经过覆盖管理器，以确保所有被调用到的模块都能够正确地驻留在内存，而且一旦模块没有在内存中，还需要从磁盘或其他存储器读取相应的模块，所以覆盖装入的速度肯定比较慢，不过这也是一种折中的方案，是典型的利用时间换取空间的方法。
6.2.2 页映射
页映射是虚拟存储机制的一部分，它随着虚拟存储的发明而诞生。前面我们已经介绍了页映射的基本原理，这里我们再结合可执行文件的装载来阐述一下页映射是如何被应用到动态装载中去的。与覆盖装入的原理相似，页映射也不是一下子就把程序的所有数据和指令都装入内存，而是将内存和所有磁盘中的数据和指令按照"页（Page）"为单位划分成若干个页，以后所有的装载和操作的单位就是页。以目前的情况，硬件规定的页的大小有4 096字节、8 192字节、2 MB、4 MB等，最常见的Intel IA32处理器一般都使用4 096字节的页，那么512 MB的物理内存就拥有512 * 1024 * 1024 / 4 096 = 131 072个页。
为了演示页映射的基本机制，假设我们的32位机器有16 KB的内存，每个页大小为4 096字节，则共有4个页，如表6-1所示。
表6-1
假设程序所有的指令和数据总和为32 KB，那么程序总共被分为8个页。我们将它们编号为P0～P7。很明显，16 KB的内存无法同时将32 KB的程序装入，那么我们将按照动态装入的原理来进行整个装入过程。如果程序刚开始执行时的入口地址在P0，这时装载管理器（我们假设装载过程由一个叫装载管理器的家伙来控制，就像覆盖管理器一样）发现程序的P0不在内存中，于是将内存F0分配给P0，并且将P0的内容装入F0；运行一段时间以后，程序需要用到P5，于是装载管理器将P5装入F1；就这样，当程序用到P3和P6的时候，它们分别被装入到了F2和F3，它们的映射关系如图6-4所示。
图6-4 页映射与页装载
很明显，如果这时候程序只需要P0、P3、P5和P6这4个页，那么程序就能一直运行下去。但是问题很明显，如果这时候程序需要访问P4，那么装载管理器必须做出抉择，它必须放弃目前正在使用的4个内存页中的其中一个来装载P4。至于选择哪个页，我们有很多种算法可以选择，比如可以选择F0，因为它是第一个被分配掉的内存页（这个算法我们可以称之为FIFO，先进先出算法）；假设装载管理器发现F2很少被访问到，那么我们可以选择F2（这种算法可以称之为LUR，最少使用算法）。假设我们放弃P0，那么这时候F0就装入了P4。程序接着按照这样的方式运行。
可能很多读者已经发现了，这个所谓的装载管理器就是现代的操作系统，更加准确地讲就是操作系统的存储管理器。目前几乎所有的主流操作系统都是按照这种方式装载可执行文件的，我们熟悉的Windows对PE文件的装载及Linux对ELF文件的装载都是这样完成的，接着我们将从操作系统的角度来看可执行文件的装载。