程序的装入和链接
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
- 编译，由编译程序（Compiler）对用户源程序进行编译，形成若干个目标模块（Object Module）。
- 链接，由链接程序（Linker）将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块（Load Module）
- 装入，由装入程序（Loader）将装入模块装入内存。
连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，该分配方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。
连续分配方式可分为四类：单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配算法。
- 单一连续分配：这是最简单的一种存储管理方式，但是只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分。
固定分区分配：固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样，把用户空间划分为几个分区，便允许有几道作业并发运行，当该作业结束时，又可再从后备作业队列中找到另一个作业调入该分区。
划分分区的方法：
- 分区大小相等
- 分区大小不等
内存分配：为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。
固定分区分配，是最早的多道程序的存储管理方式，由于每个分区的大小固定，必然会造成存储空间的浪费，因而现在已很少将它用于通用计算机中。
动态分区分配（重点）
动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。
分区分配中的数据结构
- 空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。
- 空闲分区链。
分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。目前常用的一下所述的五种分配算法。
1.首次适应算法（first fit）
我们以空闲分区链为例来说明采用 FF 算法时的分配情况。FF 算法要求空闲分区链以
地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要
求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，
余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，
则此次内存分配失败，返回。 该算法倾向于优先利用内存中低址部分的空闲分区，从而保
留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺
点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是
从低址部分开始，这无疑会增加查找可用空闲分区时的开销 。
2.循环首次适应算法（next fit）
该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链
首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满
足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，
应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即
如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其
大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得
更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。
3.最佳适应算法（best fit）
所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区
分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以
从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最
佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后
所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。
4.最坏适应算法（worst fit）
最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给
作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业
有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从
大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算
法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。 最坏适应算法与前面所述的首
次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。
5.快速适应算法（quick fit）
该算法又称为分类搜索法 ，是将空闲分区根据其容量大小进行分类，对于每一类具有
相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区
链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，
并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进
行划分，如 2 KB、4 KB、8 KB 等，对于其它大小的分区，如 7 KB 这样的空闲区，既可以
放在 8 KB 的链表中，也可以放在一个特殊的空闲区链表中。
该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区
链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区
产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。
该算法的缺点是在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空
闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，
或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存
储空间浪费，这是典型的以空间换时间的作法。
分区分配操作
在动态分区存储管理方式中，主要的操作是分配内存和回收内存。
1）分配内存
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大
小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去， 余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图 4-7 示出了
分配流程。
2）回收内存
当进程运行完毕是释放内存时，系统根据回收区的首址，从空闲区链（表）中找到响应的插入点，此时可能出现以下四种情况之一：
(1) 回收区与插入点的前一个空闲分区 F1相邻接，见图 4-8(a)。此时应将回收区与插入
点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1的大小。
(2) 回收分区与插入点的后一空闲分区 F2相邻接，见图 4-8(b)。此时也可将两分区合并，
形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
(3) 回收区同时与插入点的前、后两个分区邻接，见图 4-8(c)。此时将三个分区合并，
使用 F1的表项和 F1的首址，取消 F2的表项，大小为三者之和。
(4) 回收区既不与 F1邻接，又不与 F2邻接。这时应为回收区单独建立一新表项，填写
回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
伙伴系统
固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进
程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空
闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一
种折衷方案。
伙伴系统规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂，k 为整数，
l≤k≤m，其中：21 表示分配的最小分区的大小，2m 表示分配的最大分区的大小，通常 2m
是整个可分配内存的大小。
假设系统的可利用空间容量为 2m个字，则系统开始运行时，整个内存区是一个大小为 2m
的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，
将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独
设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了 k(0≤k≤m)个空闲分区链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2i－1<n≤2i，然
后在空闲分区大小为 2i 的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否
则，表明长度为 2i 的空闲分区已经耗尽，则在分区大小为 2i＋1 的空闲分区链表中寻找。若
存在 2i＋1 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙
伴，其中的一个分区用于分配，而把另一个加入分区大小为 2i 的空闲分区链表中。若大小
为 2i＋1的空闲分区也不存在，则需要查找大小为 2i＋2的空闲分区，若找到则对其进行两次分
割：第一次，将其分割为大小为 2i＋1 的两个分区，一个用于分配，一个加入到大小为 2i＋1
的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为 2i 的两个分区，一个用于
分配，一个加入到大小为 2i 的空闲分区链表中。若仍然找不到，则继续查找大小为 2i＋3 的
空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对 2k的空闲分区进行 k 次分
割才能得到所需分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小
为 2i的空闲分区时，若事先已存在 2i的空闲分区时，则应将其与伙伴分区合并为大小为
2i＋1的空闲分区，若事先已存在 2i＋1的空闲分区时，又应继续与其伙伴分区合并为大小为
2i＋2的空闲分区，依此类推。
在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空
闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需
要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算
法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。
需要指出的是，在当前的操作系统中，普遍采用的是下面将要讲述的基于分页和分段
机制的虚拟内存机制，该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系
统仍不失为一种有效的内存分配和释放的方法，得到了大量的应用。
哈希算法
在上述的分类搜索算法（快速适应算法（quick fit））和伙伴系统中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲愤怒分类较细，则相应的空闲分区链表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空间分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
可重定位分区分配
- 动态重定位的引入
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的区块，即使它们的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。这些不能被利用的小分区称为“零头”或“碎片”。
若想把作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”，见下图，由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
- 动态重定位的实现
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序（数据）在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
图 4-10 示出了动态重定位的实现原理。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态
重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对
程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可
- 动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。如下图：
对换
1.对换的引入
在多道程序环境下，一方面，在内存中某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。为了解决这一问题，在系统中又增设了对换（也称交换）设施。所谓“对换”，是指把内存中暂时不能运行的内存或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。
如果对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”。这种对换被
广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存的利用
率。而如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段
对换”，又统称为“部分对换”。这种对换方法是实现后面要讲到的请求分页和请求分段式
存储管理的基础，其目的是为了支持虚拟存储系统。在此，我们只介绍进程对换，而分页
或分段对换将放在虚拟存储器中介绍。为了实现进程对换，系统必须能实现三方面的功能：
对换空间的管理、进程的换出，以及进程的换入
2．对换空间的管理
在具有对换功能的 OS 中，通常把外存分为文件区和对换区。前者用于存放文件，后者
用于存放从内存换出的进程。由于通常的文件都是较长久地驻留在外存上，故对文件区管理
的主要目标，是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。然而，进
程在对换区中驻留的时间是短暂的，对换操作又较频繁，故对对换空间管理的主要目标，
是提高进程换入和换出的速度。为此，对换区采取的是连续分配方式，较少考虑外存中的碎片问题。
为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外
存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空
闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其
大小，分别用盘块号和盘块数表示。
由于对换分区的分配是采用连续分配方式，因而对换空间的分配与回收，与动态分区
方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法
或最佳适应算法。具体的分配操作，也与图 4-7 中内存的分配过程相同，这里不再赘述。
- 进程的换出和换入
（1）进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收进程所占用的内存空间，并对该进程和进程控制块做相应的修改。
（2）进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久（换出到磁盘上）的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。
