第四章存储器管理4.1 程序的装入和链接将一个用户源程序变为一个可执行程序，通常都要经过以下几个步骤：编译：由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；链接：由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的可装入模块(Load Module)。

4.1.1 程序的装入将一个装入模块装入内存时，可以有以下两种方式：绝对地址装入方式(Absolute Loading Mode)可重定位装入方式(Relocation Loading Mode)动态运行时装入方式(Dynamic Run-time Loading)1. 绝对装入方式在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。

装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。

程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。

此种程序一般有特殊用途，比如启动程序。

2.可重定位装入方式绝对装入方式只能将目标模块装入到内存中事先指定的位置。

在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，因此，绝对装入方式只适用于单道程序环境。

在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。

此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位。

示例在用户程序的1000号单元处有一条指令LOAD 1，2500，该指令的功能是将2500单元中的整数365取至寄存器1。

静态地址重定位把在装入时对目标程序中指令和数据的修改变换过程称为重定位。

又因为地址变换通常是在装入时一次完成的，装入以后不再改变，故称为静态地址重定位。

静态地址重定位装入方式，可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；但并不允许程序运行时在内存中移动位置。

3. 动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。

因此，装入内存后的所有地址都仍是相对地址。

4.1.2 程序的链接源程序经过编译后，可得到一组目标模块，再利用链接程序将这组目标模块链接形成装入模块。

根据链接时间的不同，可把链接分成如下三种：(1)静态链接(Static Linking)。

(2)装入时动态链接(Load-time Dynamic Linking) 。

(3)运行时动态链接(Run-time Dynamic Linking) 。

1.静态链接在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。

我们把这种事先进行链接的方式称为静态链接方式。

2.装入时动态链接这是指将用户源程序编译后所得到的一组目标模块，在装人内存时，采用边装入边链接的链接方式。

装入时动态链接方式有以下优点：(1)便于修改和更新。

若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块，是件非常容易的事。

(2)便于实现对目标模块的共享。

采用装入时动态链接方式时，OS则很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。

3.运行时动态链接这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。

是对上述在装入时链接方式的一种改进。

这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。

凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

4.2 连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。

这种分配方式曾被广泛应用于20世纪60~70年代的OS中，它至今仍在内存分配方式中占有一席之地。

可把连续分配方式进一步分为：单一连续分配、固定分区分配、动态分区分配和可重定位分区分配。

4.2.1单一连续分配这是最简单的一种存储管理方式。

采用这种存储管理方式时，可把内存分为系统区和用户区两部分：系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。

只能用于单用户、单任务的操作系统中。

4.2.2 固定分区分配固定分区式分配是最简单的一种可运行多道程序的存储管理方式。

它将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。

用户空间划分为几个分区，便允许有几道作业并发运行。

当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。

1.划分分区的方法(1)分区大小相等。

其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。

(2)分区大小不等。

可根据程序的大小为之分配适当的分区。

分区表与内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配) 。

当有一用户程序要装入时，由内存分配程序检索分区表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。

分区管理内存示例固定分区管理说明固定分区分配，是最早的多道程序的存储管理方式，用于60年代的IBM360的MFT操作系统中。

由于每个分区的大小固定，必然会造成存储空间的浪费。

进程并发度受分区个数的限制。

程序大小受限分区大小的限制。

4.2.3 动态分区分配动态分区分配是根据进程的实际需要，动态地为之分配内存空间。

在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作等问题。

1.分区分配中的数据结构常用的数据结构有以下两种形式：(l)空闲分区表。

在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。

每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。

(2)空闲分区链。

空闲分区链可以是双向的，也可以是单向的。

单向空闲分区链单向空闲分区链则是利用每个内存空闲区的头几个单元存放本空闲区的大小以及下个空闲区的起始地，从而把所有的空闲区链接起来。

最后一个的链指针为NULL表示结束。

系统再设置一链首指针让其指向第一个空闲区。

管理程序可通过链首指针查到所有的空闲区。

采用空闲链法管理空闲区，查找时要比可用表困难，但由于空闲链指针是利用的空闲区自身的单元，所以不占用额外的内存区。

双向空闲分区链如图4-5所示，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。

为了检索方便，在分区尾部重复设置状态位和分区大小表目。

当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。

双向空闲分区链示意图（略）。

2. 分区分配算法(1) 首次适应算法FF（First Fit）(2) 下次适应算法（Next Fit）循环首次适应算法(3) 最佳适应算法（Best Fit）(4) 最坏适应法（Worst Fit）首次适应算法首次适应算法算法要求空闲分区链以地址递增的次序链接。

在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。

若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败。

该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。

这给为以后到达的大作业分配大的内存空间创造了条件。

其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。

下次适应算法在首次适应法的基础上，继续查找若找到合适的则分配。

为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到链首，直到本次开始位置。

该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会造成缺乏大的空闲分区。

循环首次适应算法也是这个意思。

最佳适应算法所谓“最佳”是指每次为作业分配内存时，总是把能满是要求、又是最小的空闲分区分配给作业，避免“大材小用”。

为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。

这样，第一次找到的能满足要求的空间区，必然是最佳的。

孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定，因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多程和用的小空闲区。

每次分配之后，还要调整分区链。

最坏适应算法最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或空闲链。

当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若小于所需的，则分配失败，否则从空闲区可用表或自由链中分配相应的存储空间给用户。

然后修改和调整空闲区可用表或自由链。

3. 分区分配操作1）分区分配2）分区回收1）分区分配系统应利用某种分配算法，从空闲分区链(表)中查找所需大小的分区。

若找到且可再分，从找到分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中；若不能再分，则整个分配给需求者。

然后，将分配区的首址返回给调用者。

若找不到，则失败。

分区分配流程图2）分区回收刚释放的空闲分区，与相邻分区可能以下4种关系之一：a)该空闲区的上下两相邻分区都是空闲区;b)该空闲区的上相邻区是空闲区;c)该空闲区的下相邻区是空闲区：d)两相邻区都不是空闲区。

对于以上情况，都要调整空闲分区链。

4.2.4可重定位分区分配1. 动态重定位的引入在单一连续分配、固定分区分配和动态分区分配方式中，内存的分配太零乱了，剩余的空闲分区也太分散了，不便于再利用，更不能装入大作业。

若能将内存中的正在使用区域放在一起，则自然的空闲分区也就拼接在一起了。

但由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。