4.1 调度的层次 4.2 Linux交换调度 4.3 Linux进程调度 4.4 小结 习题 第4章 调 度 4.1 调度的层次 4.2 Linux交换调度 4.3 Linux进程调度 4.4 小结 习题

设计操作系统的主要目标是充分利用硬件资源使其发挥最大的效能。处理机（CPU）资源，又是其中最重要的一项，让它尽可能处于工作状态，是操作系统管理功能的关键。调度针对的主要是处理机资源的分配问题，因而处理机管理的核心是调度。 处理机调度的主要指标有：周转时间、吞吐量、响应时间和设备利用率等。根据不同的使用场合、不同的系统需求，选取合适的调度算法，采用不同的管理侧重点，使系统达到预期的性能指标是调度管理的主要任务。 本章首先介绍处理机调度的层次和目标，然后，以单处理机微机系统为背景，具体讨论Linux系统交换调度和进程调度的基本原理和实现方法。

4.1 调度的层次 处理机调度也是分层次的，按照调度发生频率依次是：作业调度、交换调度、进程调度和线程调度。 4.1 调度的层次 处理机调度也是分层次的，按照调度发生频率依次是：作业调度、交换调度、进程调度和线程调度。 作业调度，是针对用户提交的作业，在已经输入的作业中，按照某种策略，选取合适的作业投入运行。 交换调度，又称中级调度。针对系统中已经开始运行的进程，把内存中暂时不会执行的内容交换到外部存储器的特定区域中，而把外存中处于就绪状态的进程交换到内存中，准备投入执行。 进程调度，控制进程在执行、就绪、等待等各种状态之间转换经历的过程。特别是从就绪到执行的转换，系统从处于就绪状态的所有进程中选择合适的一个，分配处理机资源，投入执行。

线程调度，系统内核针对线程的调度情况，选中就绪线程并占有处理机，转入执行状态。 参看图4.1。 图4.1 Linux系统调度层次示意图

Linux系统高级调度非常简洁，或者也可以说没有作业调度的概念，作业一旦输入，就直接进入内存，建立相应的进程，进入下一级的调度。交换调度主要涉及系统存储管理的内容，一方面根据正在执行进程的要求，把所需要的页换入内存，同时按照一定的规则保证系统总是有足够的空闲内存页面，一旦发现系统空闲页面低于某一个临界值，就把内存中的页面按照一定的算法清除掉一部分，直接丢弃或者是交换到外部存储器中。Linux系统中的内核级线程和进程在表示、管理调度方面没有差别，系统也没有专门的线程调度，采用进程调度统一处理进程和内核级线程。因此，本章主要讨论Linux系统中的交换调度和进程调度的内容。

4.2 Linux交换调度 Linux系统的内存主要采用称为请求页式管理的动态管理方法。当某一个程序开始运行时，一个新的进程创建，整个可执行文件映像和该程序引用的所有相关共享库同时装入进程的虚拟地址空间中。Linux在建立进程的时候，整个执行文件映像并没有装入物理内存，只是链接到进程的虚拟地址空间中，进程只分配到极少的内存页面，占用很少的物理空间。在整个进程生命周期中，进程所拥有的内存页面总是动态变化的。管理好内存页面和外部存储器，正确地模拟内存特殊区域的工作，保证系统有足够的内存，让尽可能多的进程并发执行，是Linux交换调度的主要任务。

请求页式管理被认为是按照进程执行的需要而分配和使用内存的，因此也称为按需调页。为了解决进程执行所需要的页面，围绕着进程的虚拟内存结构，系统首先确定哪些虚页需要执行但它还不在内存中，然后分配必需的内存页面并把所需的页换入内存。 确定虚页是通过查找页目录和页表中相关的属性标志来实现的。虚页换入内存时，首先需要解决缺页的调入方式，其次要保证有足够的空闲内存页面，这就需要使用适当的策略来淘汰占据内存的页，这种策略称为置换算法。Linux系统采用记龄（aging）置换算法，Linux系统根据访问次数来决定是否适合换出，优先换出那些很长时间没有被访问的页面。

4.2.1 交换空间 现代操作系统中普遍采用基于虚拟存储器的概念来统一管理内存和外存，实现逻辑上的大容量存储空间。 从内存中换出的页面保存在外存的交换空间中，Linux系统提供两种不同类型的外存保存方式。一种是利用整个块设备，比如磁盘的一个分区，这样的分区具有特殊的格式，通常称为交换区或交换设备。另一种是利用文件系统中特殊的文件，这种文件具有固定的长度，称为交换文件。

Linux系统可以同时管理多个交换空间，最大个数由参数MAX-SWAPFILES指定(默认值是8)，在文件include/linux/swap.h中定义。交换空间按照优先级排序，当需要分配一个交换页面时，Linux首先使用仍然拥有空间、拥有最高优先级的交换空间，交换区和交换文件都可以用来存储内存中换出的页，达到扩充内存的目的。使用交换区的交换存取过程中，系统直接针对磁盘进行。交换文件是文件系统中的特殊文件，在文件系统建立之后创建。在实际使用过程中，通常以交换区为主，以交换文件为辅。首先设置能够满足日常工作需要的交换区，当需要更多交换空间的时候，临时增加几个交换文件，这样，不再需要时可以方便地撤消交换文件。

4.2.2 进程的内存组织 Linux系统中进程虚拟存储空间管理的基本单位是虚拟存储段（Vitual Memory Area， VMA），用vm-area-struct 结构来描述。一个VMA段是某个进程的一段连续的虚拟空间，这段存储空间的所有单元（页）拥有相同的特征，这些特征可以包括访问权限、保护情况可加锁情况等等，同时，还定义了一组建立在这个数据结构基础上的对内存的操作方法，这些操作方法具体实现进程对虚拟存储段的操作，见图4.2。进程的虚拟内存实际是由一组指向vm-area-struct 结构的指针的链表来具体实现的，链表的头接点记录在该进程所指向的mm-struct结构中。

图4.2 vm-area-struct 数据结构示意图

当可执行程序映射到进程的虚拟地址空间时，系统建立一系列 vm-area-struct结构来描述虚拟内存区域的起始点和终止点，每一个结构代表可执行程序的一个部分，可能是可执行代码，也可能是初始化的变量或未初始化的数据。随着整个vm-area-struct结构组成的链表的生成，这个结构所描述的虚拟内存区域上的标准操作函数也由Linux初始化。 进程映射到虚拟空间中并开始执行后，因为只有很少一部分被装入了物理内存，因此不久进程就会存取尚未装入物理内存的虚拟内存页，这时，处理器向Linux报告一个页故障及其对应的故障原因，根据实际情况，系统必须把进程执行所需要的内容装入到物理内存，换入工作开始了。

4.2.3 换入 进程内存页的换入是从缺页故障开始的，这种页故障出现的原因可能有两种，第一种情况是程序出现内存访问错误；另一种情况就是正常的缺页中断，虚拟地址有效，但其所对应的页当前不在物理内存中，这时，操作系统必须从磁盘映像或交换空间中将所需的页装入物理内存。 进程运行过程中遇到缺页中断后，系统保存当前进程的现场，当前进程进入等待状态。Linux系统转入缺页中断处理程序，根据处理器提供的缺页地址信息（在I386系统中是控制寄存器CR2），系统必须迅速地找到用来表示出现缺页的虚拟存储区所对应的vm-area-struct结构。

为了实现快速查找出现页故障虚拟内存相应的vm-area-struct结构的位置目标，Linux内核把所有vm-area-struct结构组成一个AVL树。如果搜索不到缺页所对应的内存区域，则说明进程访问了非法存储区，该虚拟地址是无效的，系统向进程发送SIGSEGV信号。 接着，系统进行缺页访问模式合法性检测。因为进程也有可能在虚拟地址上进行的操作非法而产生页故障。这时操作系统会同样发送内存错误信号SIGSEGV给该进程。有关页的访问控制信息包含在页表项中。

这两项检测通过之后，就表明该虚拟地址有效。对有效的虚拟地址，必须区分页所在的位置。如果页表项是无效但非空，则说明该页处于交换空间中，操作系统要从交换空间装入页，否则，页面就位于磁盘的可执行映像中。默认情况下，Linux会分配一个新的物理页面并建立一个有效的页表项，更新页表项的相关属性信息，把所需要的页面装入内存。 这时，所需的页装入了物理内存，页表项也同时被更新，然后进程就可以继续执行了。这就是请求页式管理的请求调页过程。 处理缺页故障过程中操作系统唤醒另外的进程占有处理机资源，当前进程转入等待状态。换入结束后，进程转入就绪状态，参与处理机资源的竞争。

4.2.4 换出 系统为了保证有足够的空闲物理内存，必须及时把内存中暂时不会用到的物理页面淘汰掉，或者说置换出去，可能是置换到交换空间，也可能直接扔掉，这取决于页面本身的访问情况。 Linux系统提供内核交换进程kswapd来实现页面淘汰功能。kswapd进程号为5，属于一种特殊的进程，Linux中称为内核线程，内核线程不是通常意义的线程，它是具有高优先级的实时进程，不共享其他进程的内容，本身没有虚拟存储空间，运行于内核态，直接访问物理空间，这种特性决定了它可以快速地使用内存，提高整个内存管理的效率。属于这个类型的进程还有init和bdflush等等。

内核线程kswapd主要是保证系统中总是有足够的空闲页面，保持整个存储管理子系统高效地运行。这个线程周期性地运行，可以保证系统总能及时释放足够多的内存页面。 交换内核线程kswapd周期性地被唤醒，首先检测现有的空闲内存页面数据，Linux系统使用固定的值作为空闲页面的警戒值。 交换内核线程kswapd是高优先级实时进程，依次通过三种途径缩减已使用的内存页面——一是缩减page cache和buffer cache；二是换出SYSTEM Ⅴ 共享内存占用的页面；三是换出或者丢弃其他进程占用的页面。释放一部分页面之后，系统再次拥有足够多的空闲页面，交换内核线程转入等待状态。

缩减page cache和buffer cache是Linux操作系统首选的释放页面途径。page cache是系统为了提高磁盘文件访问速度而设置的，磁盘文件中正在访问的一部分以页为单位映射到内存中。buffer cache是系统块设备使用的缓冲区，其目标是提高块设备的访问速度。在释放物理内存时，淘汰cache页面是最简便的办法。 如果缩减page cache和buffer cache没有得到足够多的空闲页面，就采取第二步措施，换出SYSTEM Ⅴ共享内存。共享页面由多个进程访问，只能换出到交换空间中，而且共享页面同时涉及到多个进程，因此在换出过程中必须依次对每一个进程的页表进行修改，这也需要多次访问内存，增加了工作量。

上述两种措施仍然没有得到足够的空闲页面时，系统就要对所有进程进行扫描，寻找适合换出的候选进程。好的候选进程应该有一个或多个可以丢弃或换出的页面，系统选择其中部分页面丢弃或换出。 Linux系统采用记龄（aging）置换算法。Linux系统根据访问次数来决定是否适合换出，优先换出那些很长时间没有访问的页面。与前两种途径相比，换出或者丢弃其他进程占用的页面的效率最低。 总的来看，请求页式存储管理方法在进程建立时只分配少量内存，通过页面的交换来保证进程运行的时候能够得到需要的页面，可以同时在内存中安排多个进程。但是，内存利用率的提高是以牺牲系统时间开销为代价换来的。

4.3 Linux进程调度 Linux系统中同时在内存中安排多个进程，这些进程相互之间竞争处理机的使用权。系统的低级调度，即进程级调度就是要按照一定的策略，从所有处于就绪状态的进程中选择最应该执行的进程，把CPU分配给它，开始执行。Linux系统的内核级线程也按照进程来对待，使用进程调度统一处理进程和内核级线程。

4.3.1 初始化过程及进程树 我们以Intel 386系列计算机为例，介绍Linux系统的启动过程， 现假定系统已经完成了正常安装。打开计算机电源，计算机首先从固化在主板ROM中的BIOS开始启动，BOIS对计算机的硬件进行一系列的检测，然后从指定设备的指定位置，把boot loader读入系统内存并把控制权转交给boot loader，接着，在boot loader的控制下，系统启动代码被读入内存并进行初始化工作，控制权转交给系统初始化代码后，引导整个操作系统进入内存并控制整个系统，设置各种表格和数据结构，初始化可运行队列的时候建立系统的0号进程，然后创建系统最初的进程——init进程，该进程的进程号为1。

init进程启动内核交换线程等系统内核线程，然后根据系统提供的参数，启动相应的终端管理进程，在每一个终端屏幕上显示login字样，等待用户的登录，整个启动过程到此结束，参看图4.3。用户登录过程中，init进程启动login进程对用户的账号和密码进行验证，通过之后，由login进程启动shell命令解释进程，为用户提供操作系统的接口，接受用户的输入，解释执行用户命令，执行过程中又会创建新的进程。

图4.3 Linux系统启动过程

Linux系统的所有进程共同构成一个完整的进程树，如图4 Linux系统的所有进程共同构成一个完整的进程树，如图4.3所示。从init进程开始， init进程是所有其他进程的祖先。init产生终端管理进程mingetty，mingetty产生login，login产生用户的shell进程，然后shell产生其他用户进程，因此，其他所有进程都是由init或者它的子孙创建而来。同样，在进程结束之后，父进程也要负责该进程的最后回收工作，如果某一个进程创建了子进程之后，由于某种原因先于子进程终止，由它创建的子进程成为孤儿进程，孤儿进程的祖父进程就要负责回收工作，依此类推。最后，在系统要关机之前，init进程还要负责结束所有的进程，卸载所有文件系统并终止处理器的指令执行。

4.3.2 进程的组织 为了管理进程，Linux系统采用多种方式来组织处于各种状态的进程。 系统中每创建一个新的进程，就给它分配一个进程控制块（PCB）， PCB是系统感知、控制进程的静态实体。系统访问PCB的频率非常高，因此所有进程的PCB都直接存放在物理内存中。Linux系统中使用一个称为task的数组来保存所有PCB的指针，Linux通过task数组来管理系统中所有的进程。每一个进程都有一个惟一标识自己的进程号PID，进程号和进程在task数组中的位置（数组元素的下标）之间是不同的。

同时，系统中所有的进程还构成一个双向循环队列，整个队列通过进程控制块中的两个指针next-task和prev-task来维护。某个进程在整个进程树中的位置，也通过PCB中指针描述。 为了方便进程的调度，系统把所有可运行的进程组织成一个可运行队列，系统通过当前（current）指针来区别就绪状态和执行状态，每一个CPU都有一个当前指针，指向正在使用该CPU的进程。可运行队列也是一个双向循环队列，队列中指向前后接点的指针同样存放在PCB中，它们是next-run和prev-run。系统的调度函数根据一定的规则，查找整个可运行队列，在其中寻找最值得执行的进程，给它（或它们）分配CPU，投入执行。

Linux系统内部把所有进程分为三类，空闲线程、内核线程和用户进程。空闲线程是系统中一个特殊的具有标志作用的进程，它是task数组的0号元素task\[0\]，它的进程号也是0，在源代码中记作init-task，只有当整个系统中没有进程可以运行时，空闲线程才会执行，它始终位于系统可运行队列中，也是该队列的头结点，同时它也是所有进程组成的队列的头结点。内核线程也是比较特殊的进程，它处于核心态，没有虚拟地址空间，拥有很高的优先权，一般用来完成系统管理任务，内核交换进程kswapd就是其中之一。用户进程包括所有其他进程和线程，可以在用户态和核心态两种模式下运行。

注意，空闲进程init-task和系统中的1号进程init在表达上很相象，但二者完全不同，空闲进程是进程组织、调度过程中的关键性标志，它本身不完成任何任务，它不会退出也不会进入等待状态，而init进程是系统启动后第一个有用的进程，它负责启动系统中相关进程，在系统要关机之前，init进程还要负责结束所有的进程，它是系统中整个进程树的祖先。

4.3.3 进程调度时机 调度函数是Linux系统中执行最为频繁的一个，它的主要目标就是选择合适的进程占有CPU，实现程序的多道执行，充分提高CPU的利用率。调度函数通过对每个进程PCB中相关信息查询，按照一定的算法，在可运行队列选择进程。如果选中的进程并不是当前占有处理机的进程，调度函数还负责保存当前进程的执行现场（进程上下文），然后恢复选中进程的进程上下文使之顺利执行。 Linux系统中没有设置专门的调度进程，在需要调度的时候，调用一个特定的调度函数来完成调度功能。一般来讲，Linux系统中的进程调度发生的时机有下面几种。

(1) 用户利用系统提供的函数调用创建一个新的进程时，系统把它加到可运行队列中，返回该进程的进程号。这时，调度函数开始执行，这样的方案可以保证系统具有很好的响应特性。 (2) 当正在执行的进程申请某种暂时无法获得的资源或者为了与其他进程保持同步，需要等待某个事件的发生，进程的PCB进入相应的等待事件队列中，进程转入等待状态； 当正在执行的进程完成了任务或者得到特定的信号而退出，转入僵死状态。这两种进程状态转换完成后，进程主动放弃CPU资源，调用调度函数，选择新的进程来使用CPU。这种情况下，及时的调度在一定程度上可以提高CPU资源的利用率。

(3) 对于分时系统，每个进程执行完一定的时间片之后，就必须交出CPU资源，这时，也要发生调度，这样的方案可以保证一定的公平性。 (4) 我们知道，Linux系统提供了两级保护，用户进程可以在用户态和核心态这两种处于不同保护模式的情况下运行，具有不同的特权级别，可以访问的地址空间不同。用户进程可以在这两种模式之间进行切换，用户态通过中断或函数调用就可以转入核心态，其中中断是应进程外部发来的信息的要求而转入核心态，函数调用则是进程内部要求转入核心态。而从核心态切换到用户态，则需要一定的硬件支持。当进程从核心态返回到用户态时，将会调用调度函数，发生调度。

从本质上来看，这些情况可以归结为两类时机，一是进程本身自动放弃处理机发生调度，这包括进程转换到等待和僵死状态，这类调度是用户进程可以预测的；二是由核心态转入用户态时发生调度，这类调度发生最为频繁。系统调用完成和内核处理完中断之后系统是由核心态转入用户态，时间片用完本身也是系统发送的时钟中断，本质上也是一种中断，而可运行队列加入新的进程的工作只能由内核操作完成，无疑是发生于内核态。

4.3.4 进程调度算法 操作系统所采用的进程调度算法取决于系统最初的设计目标，它决定了系统对资源，特别是CPU资源的分配策略，直接决定着系统的特性。Linux系统采用相当简单但效率很高的调度算法，具有很好的响应特性，它提供了三种调度算法：POSIX操作系统标准规定的用于实时进程的先进先出算法（FIFO，First In First Out）和轮转算法（RR，Round Robin），用于普通进程的可抢占式动态优先级算法（Preemptive Scheduling）。

Linux先进先出调度算法按照实时进程进入可运行队列的先后顺序，依次把每一个进程投入执行，只有前面的进程执行完成或者自动放弃CPU（比如进入等待状态），下一个进程才可以执行。这样的算法实现简单，在一般意义下也还算公平合理，但是，如果一个执行很短的进程不小心排在一个执行时间很长的进程之后，那就可能要花费比执行时间长很多倍的时间来等待，显然是不可接受的。Linux系统的先进先出算法同时也考虑了进程的优先级，具有相同优先级的进程采用FIFO算法，如果有更高的优先级出现，调度函数就要选择具有高优先级的进程使用处理机，在新进程被加入到可运行队列之后出现的调度时机实际就可以解决这种问题。

Linux轮转算法的基本原理是给每一个进入可运行队列的实时进程分配固定大小的CPU处理时间（称为时间片），按照它们在队列中的顺序依次开始执行，如果一个进程的时间片用完之后还没有完成要求的任务，它必须交出CPU的使用权并且重新排到可运行队列的尾部，等待下一次调度，原来排在它后面的进程投入执行。这样的算法，可以保证每个进程就绪之后的等待时间和占用CPU的时间成比例，更加公平。Linux系统使用的RR算法也考虑了进程的优先级，具有相同优先级的进程采用RR算法，而具有更高优先级的实时进程拥有首先使用CPU的权利。这样的方案，可以保证具有高优先级的紧迫型实时进程很快得到响应。

从上面的描述可以看到，Linux提供的实际是软件实时。

时间片是系统中比较关键的一个参数，它的大小直接影响系统的性能。I386系统采用段页式存储管理，进程的切换效率比较低，针对这种情况，Linux 时间片默认值为200ms，用户可以针对不同的进程设置时间片的值。 事实上，Linux系统中并没有根据进程的调度策略分别管理进程，而是把所有可运行进程都集中于同一个队列中，三种调度算法在实现过程中合为一种，使用同一段程序。下一节，我们就来探讨Linux进程调度的具体过程。

4.3.5 进程调度过程 Linux系统的调度过程简洁而高效。整个调度过程大概可以分为五个部分。首先检测中断，如果有中断运行时，调度过程到此为止，直接退出，如果没有中断运行，关中断，在调度的过程中将不再允许中断。其次处理系统的内核例程。然后对当前进程做相关处理：如果当前进程是时间片用完的进程按照轮转法调度，系统重新赋予时间片并把它移到队列的尾部；如果进程因为等待某个事件而转入等待状态引起调度，调度过程中发现事件已经发生，进程仍然转入就绪状态；如果进程处于其他非可运行态的话，就要从可运行队列中删除。这些都是为开始调度而进行的准备工作。

接着调度函数遍历整个可运行队列，从中找到最值得运行的进程，该进程的权值（goodness）最大。如果该进程不是当前进程，系统需要进行进程上下文切换，如果正好就是当前进程，这一部分就可以跳过去。最后打开中断，选中的进程开始执行。 整个调度过程的核心就是如何计算一个进程的权值。在Linux系统中，决定进程权值的相关参数有四个，它们都记录在进程控制块中： (1) policy，策略，一个给定进程采用的调度算法称为该进程的调度策略。进程的调度策略是从父进程那里继承来的，但是也可以通过特定系统调用来改变。

(2) priority，优先级，确切地讲是静态优先级。记载了进程最多可以拥有的时间片，从父进程那里继承过来，只能由用户通过系统调用来修改。 (3) counter，计数器，它实际上是进程的动态优先级。它表示进程在当前时间片中剩余的时间量。它的初值等于静态优先级，在进程执行期间，随时间不断减少，当它小于或等于0时，表明进程的时间片用完，重新设置为0，并引起调度。 (4) rt-priority，实时优先级。实时进程的优先级，标志实时进程优先权的高低。取值范围为0~99，取0时表示不是实时进程。

系统在进行调度时，首先确定该进程的调度策略，依据就是policy的值，然后根据不同的策略，选用适当的算法具体计算相应的权值，权值是衡量一个进程是否执行的惟一标准。 衡量实时进程执行的依据就是实时优先级。具体的计算公式为： goodness=1000+rt-priority （4.1） 对于采用实时FIFO策略的进程，具有高实时优先级的进程将一直执行，直到进入僵死状态、进入等待状态或者是被具有更高实时优先级的进程夺去处理机。采用实时RR策略的进程，时间片用完之后，将被放到可运行队列的尾部，等待下一次调度，处理机由下一个具有相同实时优先级的进程使用。

普通进程的调度策略标记为SCHED-OTHER，采用抢占式动态优先级调度策略。选择执行的依据是进程的动态优先级。进程创建之初，动态优先级和静态优先级具有相同的值，随着进程的执行，动态优先级慢慢减小，如果一个普通进程时间片用完的话，它的动态优先级就是0，而且要等到其他所有进程的动态优先级为0时才用静态优先级的值来初始化。这种情况下所有普通进程权值的计算公式都是： goodness=counter+priority （4.2） 因此，在调度中，用完时间片的普通进程被选中的可能性很小，这就给其他进程，特别是新建进程使用处理机的机会。

如果进入调度后，当前普通进程的时间片没有用完，而且仍然位于可运行队列中时，当前进程的权值采用公式（4 如果进入调度后，当前普通进程的时间片没有用完，而且仍然位于可运行队列中时，当前进程的权值采用公式（4.3）计算，除了当前进程之外的所有普通进程仍采用公式（4.2）计算权值。 goodness=counter+priority+1 （4.3） 这样，适当增大当前进程的权值，以增加继续使用处理机的可能，可以避免过分频繁的进程切换。 新的普通进程进入可运行队列后，插入到队列尾部，将引起调度，在都使用相同静态优先级的情况下，新进程的权值很大，因此，如果没有实时进程和其他一直未执行过的就绪进程，新建进程投入执行的可能性相当大。可见，Linux系统所采用的这种调度算法优先保证交互性，系统的响应时间比较短。

实时进程和普通进程相比，总是具有更高的优先级。因此，如果可运行队列中同时存在实时进程和普通进程，实时进程总是可以先使用处理机。 权值是Linux系统进程调度过程中选择进程的惟一标准，程序实现非常简单，参看kernel/sched.c。 在讨论进程调度过程的时候，我们始终认为计算机只有一个处理机，实际上，Linux系统很早就开始支持对称多处理器，这种情况下的调度不在本书的讨论范围之内，有兴趣的读者可以参看源代码和本书的相关参考文献。

4.4 小结 调度主要解决处理机资源的分配问题，系统的调度是分层次的，因此也称为分级调度，按照调度发生的频率分为作业调度、交换调度、进程调度和线程调度，分别由不同的调度程序来完成。 Linux系统采用两级调度，用户作业进入内存，直接参与交换调度，进程和线程采用同样的表示和管理方式，也使用同样的调度函数。

Linux系统采用请求页式内存动态管理方法，根据进程执行的实际需要分配内存页面并换入内容，同时使用内核交换进程kswapd按照记龄（aging）置换算法来实现页面淘汰功能，内核交换进程周期性地执行，通过缩减page cache和buffer cache、换出SYSTEM Ⅴ共享内存占用的页面、换出或者丢弃其他进程占用的页面等三种途径缩减已使用的内存页面，保证系统中总是有足够的空闲页面，保持整个存储管理子系统高效地运行。

调度函数管理系统的可运行队列，该队列中包括正在执行的进程和所有就绪进程，在实际调度中，调度函数查询每个进程PCB中相关信息，按照一定的算法，在可运行队列选择合适进程，进行进程上下文切换，使得选中的进程顺利执行。Linux系统提供了三种调度算法：POSIX操作系统标准规定的用于实时进程的先进先出算法FIFO、轮转算法RR及用于普通进程的可抢占式动态优先级算法。Linux系统用一个简单的函数实现了这三种进程调度算法，它虽然不十分完美，但高效，确实可以适用于大多数情况。

习题 4-1 什么是分级调度？描述Linux系统的分级调度情况。 4-2 什么是交换调度？其主要功能有哪些？Linux的交换调度有什么特点？ 4-3 交换空间是什么？交换区和交换文件有什么区别？如果安装一个用于www服务的Linux系统，你认为交换空间应该怎么设置？为什么？ 4-4 进程调度的功能是什么？Linux的进程调度发生在什么情况下？ 4-5 Linux系统的实时调度与普通调度有何区别？实时FIFO和实时RR调度算法有何区别?分别如何实现？

4-6 Linux在调度算法实现过程中如何保证系统具有良好的交互性？与此同时，它牺牲了哪些方面的性能？ 4-7 如果你是系统的root用户，你将采取什么措施保证你的进程能比别的用户具有更高的或更低的优先权？如果你是普通用户，将采取什么措施？实际操作，能够达到目的吗？ 4-8 访问Linux核心代码站点http://www.kernel.org ，了解Linux核心中调度函数的最新进展及新增特点。