2.3 操作系统内核

操作系统内核是整个操作系统的灵魂，主要负责整个系统的内存管理、进程调度和文件管理等，以下将一一进行介绍。

在单任务操作系统中，内存被分成两部分，一部分给了操作系统的驻留程序，另一部分则给了用户进程。而在多任务操作系统中，后一部分需要继续细分给不同的进程，这个工作是由操作系统的内存管理机制实现的。

一个操作系统的内存管理效率对它的性能有着很重要的影响。一般而言，希望内存在通过有效的分配之后能够容纳更多的任务以提高CPU的利用率。

2.3.1 内存管理功能

一般而言，内存管理需要完成以下功能：二次定址、保护、共享、逻辑组织和物理组织，下面给予简单阐述。

首先，进程调入、调出内存存在随机性，需要内存管理提供二次定址功能使得任务在再次调入内存时能够和先前一样正常运行。

其次，不同的进程为了自己的正常运行需要有私有空间，内存管理需要提供相应的保护机制以容许这种私有空间的存在。

再次，为了能够协同完成更高级的功能，不同进程之间需要有不同形式的交互，例如访问对方数据、使用对方进程代码等，而内存管理所完成的共享功能可以保证其顺利实现。

另外，计算机采用的是线性存储设备，而计算机程序本身为了完成自身的逻辑任务就有了适合自己特点的逻辑划分，如果操作系统或计算机硬件能够实现逻辑划分和线性存储之间的顺利转换，则对程序本身实现的相对独立性等方面不无裨益。因此，内存管理需要提供相应的逻辑组织功能。

最后，需要指出的一点就是，计算机存储设备是多样的，如何合理地管理这些存储设备以提高操作系统性能也是内存管理的功能要求，这就是内存管理的物理组织功能。

2.3.2 内存分割

计算机程序最终是要装载到内存中才能运行的，这就涉及到多个进程如何在内存中合理占用空间的问题，也就是内存分割的问题。从操作系统产生到发展至今，已经提出了不少内存分割机制，诸如固定分割、动态分割、分页和分段等。

1.固定分割

固定分割（Fixed Partitioning），顾名思义，就是将内存固定划分为若干大小相同或不同的区域，当程序装入时，选择与其大小最相近的一个区域将其载入即可。这种方式的缺点就是引入了内部碎片（Internal Fragmentation），即每个程序需要占用一整块区域，而它的大小很难与区域大小完全相符，区域多出来的部分也无法被其他程序使用，从而造成内存资源的浪费。

2.动态分割

为了克服固定分割机制的缺陷，提出了动态分割（Dynamic Partitioning）机制。其中心思想就是内存分割出来的区域大小具有一定的随意性，它可以在内存空间允许的情况下根据装入程序的大小在内存中分割出相同大小的一片区域并装入该程序，这样就避免了每个分区内部碎片产生的可能。但是当内存中没有分配的区域不足于装载任何程序的时候就产生了内存资源的浪费，这样的浪费叫做外部碎片（External Fragmentation）。

3.分页

固定分割会导致内部碎片，而动态分割会导致外部碎片，都可能造成内存资源的巨大浪费。这时候我们在想，能否把内存平均分割成大小相对较小的一些区域，这些区域通常被叫做页帧（Page Frame），然后把它们分配给需要装载的程序。但问题是当页帧较小时，可能任何程序都要比它大很多，产生无法装载。这个时候我们在想，是否可以将程序本身也分割成与内存分区大小一致的程序段，这样就可以装入内存运行了，这就是分页机制的基本思想。我们可以很容易地想到，这样的内存分割方法不会产生外部碎片，而内部碎片也只可能在程序的最后一个程序段装入内存分区时产生，因为它们的大小一般是不相同的。但是由于内存分区相对较小，这样的话，内存空间的利用率仍然可以很高。

在分页（Paging）机制中，程序在载入内存时需要实现一个程序所在的虚拟内存空间地址（逻辑地址）到物理内存空间地址（物理地址）的转换，这个转换通常是由一个或若干个查表动作来完成的，这个表即所谓的分页表。

4.分段

在分页机制中，程序本身也被顺序分割成与内存分区大小相同的程序段。程序的这种分割方法缺乏直观性，分段（Segmentation）机制的引入则克服了这个缺点。在分段机制中，程序及其数据被分割成了若干有意义的段，如通常所讲的程序段、数据段等，而这些段是大小不一的。

从这点来看，分段机制和动态分割机制类似。不同的是在分段机制中，每个程序可以占有若干个不同的内存分区，而这些分区可以是不连续的。不过，分段机制和动态分割机制一样存在外部碎片问题，但不存在像固定分割机制和分页机制那样的内部碎片问题。

在分页机制中，程序在载入内存时同样需要实现一个程序所在的虚拟内存空间地址（逻辑地址）到物理内存空间地址（物理地址）的转换，这个转换通常是由一个查表动作来完成的，而这个表即所谓的分段表。

2.3.3 虚拟内存

虚拟内存机制基于分页技术或者分页与分段两种技术的结合，它是现代操作系统的一个显著特征。虚拟内存技术的实现需要由硬件支持，并要得到操作系统的配合，从而才能够提供给每个进程一个几乎不受限制的虚拟内存空间。

虚拟内存机制的实现不仅需要操作系统方面的软件支持，而且需要有相应的硬件支持，例如地址转换功能支持等。

硬件支持主要包括地址转换功能，以及一些为了提高软件支持效率而做出的相应的支持，如MMU等。在这里主要介绍虚拟内存机制在操作系统方面的实现。操作系统方面的支持需要考虑3个问题：系统是否需要虚拟内存支持、系统对内存分割机制的选择问题和内存管理算法的选择问题。

前两个问题的回答有赖于硬件支持，而第3个问题则纯属软件问题，主要包括分页的取放、替换和清理方法、驻留部分管理和负荷控制等几个方面，下面给予分别阐述。

（1）分页的取放

当需要某一分页载入内存使用时，分页的取放动作就需要连续发生了。分页的“取”可以有两种方法，一种是只有当它被要求时才会被载入内存；另一种是，即便某个分页未被要求也会被载入内存。后一种方法的出现主要是考虑到计算机系统的外部存储设备的处理速度和其延迟比较大，而程序在外部存储设备中可以通过某种工具（如碎片整理程序）实现连续性存储，一次性读取多个分页，从而提高系统整体性能。分页的“放”在采用分页机制的情况下，不存在算法的选择问题，但是如果采用分段机制的话，则需要做一些考虑，比如说是选择和段大小最接近的一个空闲内存区域放置呢，还是选择第一个适合的空闲内存区域放置等。

（2）分页的替换

当内存区域已经被分页全部占用之后，仍然需要有新的分页载入时，就涉及到了一个选择内存中现有分页中的哪个被替换的问题。谈到分页替换的时候，首先应当了解内存中的某些区域由于被操作系统的某些核心程序所占用，所以是无法被替换的。分页替换有一些基本算法，这其中包括最优算法、LRU算法、FIFO算法和CLOCK算法，下面分别给予简单阐述。

①最优算法

最优算法就是将内存中再次访问时间间隔最长的那个分页替换掉。这种算法由于需要所有分页在任何时间被访问的确切记录，而计算机没法知道未来究竟哪个分页会在什么时间被访问到，因此在现实中是无法实现的。但是它却因为可以给出一个最优答案，所以常常作为其他算法性能评价的一个参考。

②LRU（Least-Recently-Used）算法

LRU（Least-Recently-Used）算法是将内存中在过去时间里最早访问到的那个分页替换掉。通常这种方法在实践中证明是很有效的，并且非常接近最优算法的性能。但是由于需要对每个分页的访问时间进行记录，实现起来存在一定的困难。

③FIFO（First-In-First-Out）算法

FIFO（First-In-First-Out）算法也称为排队算法，遵循先进先出原则，即最先被载入内存的那个分页将被最先替换掉。这种算法比较容易实现，但是其性能相对较差。

④CLOCK算法

CLOCK算法综合了LRU算法的性能优势和FIFO的实现优势，现在很多实际使用的分页替换算法都是它的变种。由于在算法进行过程中，分页的替换犹如在一个时钟盘上旋转轮流选择，因此也就被形象地称为CLOCK（时钟）算法。

最简单的CLOCK算法是这样的：首先需要给每一个页帧增加一个标志位U，该位在对应页帧第一次装入分页时置位为1，而当该页再次被访问时仍然置位为1。在CLOCK算法中所有可以用来替换的页帧顺序组成了一个首尾相连的环，另外需要有一个指针标志下一个候选页帧。当某页被替换后，该指针指向环中的下一个页帧。当需要某页帧被替换时，该指针就在环中顺序移动，直到找到一个其标志位U置位为0的页帧，然后将其替换为需要装载的分页，同时按照上面所讲的规则将该页帧标志位U置位为1，并将指针指向被替换页帧的下一个页帧。在指针顺序移动的过程中，如果遇见标志位U置位为1的页帧，则指针在滑过该页帧的同时，该页帧的标志位U需要被置位为0。

（3）分页的清理

分页的清理是与分页的“取”动作相对的。它所要解决的问题就是当一个被做过修改的分页需要写回外部存储设备的时候，应该采取什么方案。同样也有两种方案，一种是只有当该页要被替换的时候才会被写回，另外一种就是在该页被选择替换之前和其他页一起成批被写回。这两种方法都存在各自的缺点，前者会导致分页替换的额外操作，即被修改分页的回写动作；后者则在成批回写的某分页在内存中再次被修改时出现对该分页的回写属于无用操作的情况。

（4）驻留部分管理

驻留部分管理是指对各进程驻留在内存中的分页的管理，主要包括两个方面，一个是驻留部分大小的选择，一个是分页替换范围的选择。驻留部分大小的选择直接决定了每个进程在内存中将要占用多少页帧，主要包括两种方法：一种是固定分配法，即操作系统根据进程特点分配给固定数目的页帧，这个数目在进程的生存周期中固定不变；一种是可变分配法，即操作系统在进程初始化时根据其特点分配给一定数量的页帧，而在进程运行过程中根据其运行性能例如分页替换的频率来实时决定给该进程分配新的页帧数量，以便提高其运行性能。后者比前者更灵活，从而可以实时改善程序运行性能。分页替换范围的选择也有两种，一种是局部替换，即当某个进程需要加载入新的分页时，新分页只能从操作系统分配给该进程的内存区域中获取可替换的页帧；一种是全局替换，即当上述情况发生时，新分页可以在全部内存区域中寻找可被替换的页帧。后者比起前者更容易实现。

（5）加载控制

加载控制关心的主要是在内存中驻留的进程数量的确定问题。一般而言，当内存中驻留进程的数量过少时，所有进程同时阻塞的情况发生的可能性就会加大，从而导致CPU闲置的可能性增大；当内存中驻留进程的数量过多时，就会导致缺页、中断频繁发生，同样会降低CPU的利用率。