文档介绍：改进进程调度算法
实验目的:
进程调度就是计算机的灵魂。进程调度算法是解决如何使资源分配策略最优
化的关键。本实验通过实现一个被称作公平调度(fair-share scheduling)的进程调度
算法,以便更深刻地理解 Linux 的进程调度机制。
实验内容:
认真阅读实验提示,实现一个公平调度(fair-share scheduling)的进程调度算
法。
实验提示:
一、公平分享的调度策略
Linux 的调度算法是相对独立的一个模块,而且较容易理解。因此很多系统高手都爱对
调度算法做改进。但是可以说调度器是一个非常神秘,难以捉摸的精灵。可能通过改变一个
关键参数你就可以大大提高系统的效率。那下面让我们来进入这个神秘的世界,把握这个莫
测的精灵。
Linux 核心在台式机上有很高的效率。对于一般进程,CPU 的使用时间都是系统平均分
配给每一个进程的,因此这种公平分享都是从进程的角度出发的。让我们来考虑一个 Linux
系统在多用户登录下的情况:用户 Shark 和 Wood 登录到了同一个 Linux 系统上,Shark 开
了 100 多个线程用于图象处理工作,而 Wood 只编译一段 C 代码。对于现今 Linux 系统的调
度策略,系统将大部分的 CPU 时间分配给了 Shark,而 Wood 得到的 CPU 时间不到 1%。这
对于 Wood 来说似乎并不是非常的公平,他定会为此而感到忿忿不平而抱怨系统的低效。因
为用户所感受的系统响应主要依赖于系统的负载以及因此而等待 CPU 的时间。

60
进程使用CPU
50 时间
(jiffies)
40
30
20
10
0
进程0 进程2 进程3 进程4 进程5

图 1 SCHED_OTHER 算法对 CPU 时间的分配
为此,Bach 在 1986 年提出了公平分享调度策略(Fair_Share scheduling)来解决这个问
题。和 Linux 三种内建策略比,公平分享调度策略是一种更抽象的调度策略。它认为 CPU
应该根据拥有进程的组(对 Linux 来说是用户)来分配时间,它实现了从用户角度考虑的公
平原则。例如,假设 Tom,Dick,Harry 分别属于不同的组,它们登录到了一台采用公平分
享调度策略的机器上,Tom 只有一个运行的进程,Dick 有三个,而 Harry 有六个。使用该策
略时,并不是每个进程得到 10%的 CPU 时间,而是每个组分配到 1/3 的 CPU 时间。因此
Tom 唯一的进程得到 33%可用的 CPU 时间,Dick 的每个进程得到 11%可用的 CPU 时间,
而 Harry 的每个进程得到 %可用的 CPU 时间。如果 Betty 属于 Dick 的组,当她登录到该
计算机并创建两个进程之后,Tom 还是能够得到 1/3 的 CPU 时间。而 Dick 和 Betty 的五个
进程就一起平均分用 1/3 的 CPU 时间,每个进程就能分到大约 %的 CPU 时间。Harry 的
六个进程仍然平均使用 %的 CPU 时间。

100
用户占用CPU
80 时间
(jiffies)
60
40
20
0
用户A 用户B 用户C 用户D

图 2 实现公平分享算法的系统对 CPU 时间的分配
由内核的结构来看,实现这个算法有很多种方式。我们可以在与调度相关的程序里做小
小的改动来实现,如改动一些数据结构并改写 schedule()函数。当然也可以做得很复杂,比
如重写 schedule()来实现所需要的结果。但是有一点我们是要必须牢记的,那就是大部分的
Linux 核心都是以短小高效为最高目标。所以,改进的算法必须尽量向这个目标靠拢。
这一章需要完成的实验包括两项内容:第一,实现公平分享算法,并用该算法替换原系
统中的调度算法进行系统进程调度;第二,编写用户级的程序来观察算法的运行情况,验证
公平分享算法的效果。
为此,大家必须先熟悉诸如 SCHED_OTHER 这些术语以及理解什么是实时进程等一些
基本概念。在此基础上,对 Linux 源代码中关于进程调度部分程序的分析也是必不可少的。
完成了这些工作之后,你是不是已经跃跃欲试了呢?那就让我们开始吧。
二、新调度策略的实现

首先,在动手之前需要好好考虑一些问题。因为修改调度算法并不像写应用程序这么轻
松,如果出现任何逻辑上的错误,那我们面临的将是系统死机的威胁。并且调试系统内核代
码的方法较繁琐,调试过程需要重新编译内核。所